Motr  M0
btree.c
Go to the documentation of this file.
1 /* -*- C -*- */
2 /*
3  * Copyright (c) 2013-2020 Seagate Technology LLC and/or its Affiliates
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  * For any questions about this software or licensing,
18  * please email opensource@seagate.com or cortx-questions@seagate.com.
19  *
20  */
21 
22 
29 #define M0_TRACE_SUBSYSTEM M0_TRACE_SUBSYS_BTREE
30 #include "lib/trace.h"
31 
32 #include "lib/errno.h"
33 #include "lib/finject.h" /* M0_FI_ENABLED() */
34 #include "lib/misc.h" /* offsetof */
35 #include "be/alloc.h"
36 #include "be/btree.h"
37 #include "be/btree_internal.h" /* m0_be_bnode */
38 #include "be/seg.h"
39 #include "be/tx.h" /* m0_be_tx_capture */
40 
41 /* btree constants */
42 enum {
43  BTREE_ALLOC_SHIFT = 0,
44 };
45 
46 enum btree_save_optype {
47  BTREE_SAVE_INSERT,
48  BTREE_SAVE_UPDATE,
49  BTREE_SAVE_OVERWRITE
50 };
51 
52 struct btree_node_pos {
53  struct m0_be_bnode *bnp_node;
54  unsigned int bnp_index;
55 };
56 
57 M0_INTERNAL const struct m0_fid_type m0_btree_fid_type = {
58  .ft_id = 'b',
59  .ft_name = "btree fid",
60 };
61 
62 static struct m0_be_op__btree *op_tree(struct m0_be_op *op);
63 static struct m0_rwlock *btree_rwlock(struct m0_be_btree *tree);
64 
65 static struct be_btree_key_val *be_btree_search(struct m0_be_btree *btree,
66  void *key);
67 
68 static void btree_root_set(struct m0_be_btree *btree,
69  struct m0_be_bnode *new_root)
70 {
71  M0_PRE(btree != NULL);
72 
73  btree->bb_root = new_root;
74  m0_format_footer_update(btree);
75 }
76 
77 /* XXX Shouldn't we set other fields of m0_be_op__btree? */
78 static void btree_op_fill(struct m0_be_op *op, struct m0_be_btree *btree,
79  struct m0_be_tx *tx, enum m0_be_btree_op optype,
80  struct m0_be_btree_anchor *anchor)
81 {
82  struct m0_be_op__btree *tree;
83 
84  M0_PRE(op != NULL);
85 
86  tree = &op->bo_u.u_btree;
87 
88  op->bo_utype = M0_BOP_TREE;
89  tree->t_tree = btree;
90  tree->t_tx = tx;
91  tree->t_op = optype;
92  tree->t_in = NULL;
93  tree->t_anchor = anchor;
94  tree->t_rc = 0;
95 }
96 
97 static struct m0_be_allocator *tree_allocator(const struct m0_be_btree *btree)
98 {
99  return m0_be_seg_allocator(btree->bb_seg);
100 }
101 
102 static inline void mem_free(const struct m0_be_btree *btree,
103  struct m0_be_tx *tx, void *ptr)
104 {
105  M0_BE_OP_SYNC(op,
106  m0_be_free_aligned(tree_allocator(btree), tx, &op, ptr));
107 }
108 
109 /* XXX: check if region structure itself needed outside m0_be_tx_capture() */
110 static inline void mem_update(const struct m0_be_btree *btree,
111  struct m0_be_tx *tx, void *ptr, m0_bcount_t size)
112 {
113  m0_be_tx_capture(tx, &M0_BE_REG(btree->bb_seg, size, ptr));
114 }
115 
116 static inline void *mem_alloc(const struct m0_be_btree *btree,
117  struct m0_be_tx *tx, m0_bcount_t size,
118  uint64_t zonemask)
119 {
120  void *p;
121 
122  M0_BE_OP_SYNC(op,
123  m0_be_alloc_aligned(tree_allocator(btree),
124  tx, &op, &p, size,
125  BTREE_ALLOC_SHIFT,
126  zonemask));
127  M0_ASSERT(p != NULL);
128  return p;
129 }
130 
131 static void btree_mem_alloc_credit(const struct m0_be_btree *btree,
132  m0_bcount_t size,
133  struct m0_be_tx_credit *accum)
134 {
135  m0_be_allocator_credit(NULL, M0_BAO_ALLOC_ALIGNED, size,
136  BTREE_ALLOC_SHIFT, accum);
137 }
138 
139 static void btree_mem_free_credit(const struct m0_be_btree *btree,
140  m0_bcount_t size,
141  struct m0_be_tx_credit *accum)
142 {
143  m0_be_allocator_credit(tree_allocator(btree),
144  M0_BAO_FREE_ALIGNED, 0, 0, accum);
145 }
146 
147 static m0_bcount_t be_btree_ksize(const struct m0_be_btree *btree,
148  const void *key)
149 {
150  const struct m0_be_btree_kv_ops *ops = btree->bb_ops;
151  return ops->ko_ksize(key);
152 }
153 
154 static m0_bcount_t be_btree_vsize(const struct m0_be_btree *btree,
155  const void *data)
156 {
157  const struct m0_be_btree_kv_ops *ops = btree->bb_ops;
158 
159  return ops->ko_vsize(data);
160 }
161 
162 static int be_btree_compare(const struct m0_be_btree *btree,
163  const void *key0, const void *key1)
164 {
165  const struct m0_be_btree_kv_ops *ops = btree->bb_ops;
166  return ops->ko_compare(key0, key1);
167 }
168 
169 static inline int key_lt(const struct m0_be_btree *btree,
170  const void *key0, const void *key1)
171 {
172  return be_btree_compare(btree, key0, key1) < 0;
173 }
174 
175 static inline int key_gt(const struct m0_be_btree *btree,
176  const void *key0, const void *key1)
177 {
178  return be_btree_compare(btree, key0, key1) > 0;
179 }
180 
181 static inline int key_eq(const struct m0_be_btree *btree,
182  const void *key0, const void *key1)
183 {
184  return be_btree_compare(btree, key0, key1) == 0;
185 }
186 
187 /* ------------------------------------------------------------------
188  * Btree internals implementation
189  * ------------------------------------------------------------------ */
190 
191 enum position_t {
192  P_LEFT = -1,
193  P_RIGHT = 1
194 };
195 
196 static struct m0_be_bnode *be_btree_node_alloc(const struct m0_be_btree *btree,
197  struct m0_be_tx *tx);
198 
199 static void btree_node_free(struct m0_be_bnode *node,
200  const struct m0_be_btree *btree,
201  struct m0_be_tx *tx);
202 
203 static void btree_pair_release(struct m0_be_btree *btree,
204  struct m0_be_tx *tx,
205  struct be_btree_key_val *kv);
206 
207 static struct btree_node_pos be_btree_get_btree_node(
208  struct m0_be_btree_cursor *it,
209  const void *key, bool slant);
210 
211 static void be_btree_delete_key_from_node(struct m0_be_btree *tree,
212  struct m0_be_tx *tx,
213  struct btree_node_pos *node_pos);
214 
215 static void be_btree_move_parent_key(struct m0_be_btree *tree,
216  struct m0_be_tx *tx,
217  struct m0_be_bnode *node,
218  enum position_t pos,
219  unsigned int index);
220 
221 static void be_btree_get_max_key_pos(struct m0_be_bnode *node,
222  struct btree_node_pos *pos);
223 
224 static void be_btree_get_min_key_pos(struct m0_be_bnode *node,
225  struct btree_node_pos *pos);
226 
227 static int iter_prepare(struct m0_be_bnode *node, bool print);
228 
240 static bool btree_backlink_invariant(const struct m0_be_btree_backlink *h,
241  const struct m0_be_seg *seg,
242  const uint64_t *parent)
243 {
244  uint64_t *cookie;
245 
246  return
247  _0C(m0_cookie_dereference(&h->bli_tree, &cookie) == 0) &&
248  _0C(m0_be_seg_contains(seg, cookie)) &&
249  _0C(parent == cookie) &&
250  _0C(M0_BBT_INVALID < h->bli_type && h->bli_type < M0_BBT_NR) &&
251  _0C(h->bli_gen == seg->bs_gen);
252 }
253 
262 static bool btree_node_invariant(const struct m0_be_btree *btree,
263  const struct m0_be_bnode *node, bool root)
264 {
265  return
266  _0C(node->bt_header.hd_magic != 0) &&
267  _0C(m0_format_footer_verify(&node->bt_header, true) == 0) &&
268  _0C(btree_backlink_invariant(&node->bt_backlink, btree->bb_seg,
269  &btree->bb_cookie_gen)) &&
270  _0C(node->bt_level <= BTREE_HEIGHT_MAX) &&
271  _0C(memcmp(&node->bt_backlink, &btree->bb_backlink,
272  sizeof node->bt_backlink) == 0) &&
273  /* Expected occupancy. */
274  _0C(ergo(root, 0 <= node->bt_num_active_key &&
275  node->bt_num_active_key <= KV_NR)) &&
276  _0C(ergo(!root, BTREE_FAN_OUT - 1 <= node->bt_num_active_key &&
277  node->bt_num_active_key <= KV_NR)) &&
278  _0C(m0_forall(i, node->bt_num_active_key,
279  node->bt_kv_arr[i].btree_key != NULL &&
280  node->bt_kv_arr[i].btree_val != NULL &&
281  m0_be_seg_contains(btree->bb_seg,
282  node->bt_kv_arr[i].
283  btree_key) &&
284  m0_be_seg_contains(btree->bb_seg,
285  node->bt_kv_arr[i].
286  btree_val))) &&
287  _0C(ergo(!node->bt_isleaf,
288  m0_forall(i, node->bt_num_active_key + 1,
289  node->bt_child_arr[i] != NULL &&
290  m0_be_seg_contains(btree->bb_seg,
291  node->
292  bt_child_arr[i])))) &&
293  /* Keys are in order. */
294  _0C(ergo(node->bt_num_active_key > 1,
295  m0_forall(i, node->bt_num_active_key - 1,
296  key_gt(btree, node->bt_kv_arr[i+1].btree_key,
297  node->bt_kv_arr[i].btree_key))));
298 }
299 
300 /* ------------------------------------------------------------------
301  * Node subtree invariant implementation:
302  * - assuming that the tree is completely in memory;
303  * - child nodes have keys matching parent;
304  *
305  * Note: as far as height of practical tree will be 10-15, invariant can be
306  * written in recusieve form.
307  * ------------------------------------------------------------------ */
308 static bool btree_node_subtree_invariant(const struct m0_be_btree *btree,
309  const struct m0_be_bnode *node)
310 {
311  /* Kids are in order. */
312  return _0C(ergo(node->bt_num_active_key > 0 && !node->bt_isleaf,
313  m0_forall(i, node->bt_num_active_key,
314  key_gt(btree, node->bt_kv_arr[i].btree_key,
315  node->bt_child_arr[i]->
316  bt_kv_arr[node->bt_child_arr[i]->
317  bt_num_active_key - 1].btree_key) &&
318  key_lt(btree, node->bt_kv_arr[i].btree_key,
319  node->bt_child_arr[i+1]->
320  bt_kv_arr[0].btree_key)) &&
321  m0_forall(i, node->bt_num_active_key + 1,
322  btree_node_invariant(btree,
323  node->bt_child_arr[i],
324  false)) &&
325  m0_forall(i, node->bt_num_active_key + 1,
326  btree_node_subtree_invariant(btree,
327  node->bt_child_arr[i])))
328  );
329 }
330 
337 static inline bool btree_invariant(const struct m0_be_btree *btree)
338 {
339  return _0C(m0_format_footer_verify(&btree->bb_header, true) == 0 &&
340  btree_backlink_invariant(&btree->bb_backlink, btree->bb_seg,
341  &btree->bb_cookie_gen));
342 }
343 
344 static void btree_node_update(struct m0_be_bnode *node,
345  const struct m0_be_btree *btree,
346  struct m0_be_tx *tx)
347 {
348  mem_update(btree, tx, node, offsetof(struct m0_be_bnode, bt_kv_arr));
349 
350  if (node->bt_num_active_key > 0) {
351  mem_update(btree, tx, node->bt_kv_arr,
352  sizeof(*node->bt_kv_arr) * node->bt_num_active_key);
353  mem_update(btree, tx, node->bt_child_arr,
354  sizeof(*node->bt_child_arr) *
355  (node->bt_num_active_key + 1));
356  }
357 
358  mem_update(btree, tx, &node->bt_footer, sizeof(node->bt_footer));
359 }
360 
361 static void btree_node_keyval_update(struct m0_be_bnode *node,
362  const struct m0_be_btree *btree,
363  struct m0_be_tx *tx,
364  unsigned int index)
365 {
366  m0_format_footer_update(node);
367  mem_update(btree, tx, &node->bt_kv_arr[index],
368  sizeof node->bt_kv_arr[index]);
369  mem_update(btree, tx, &node->bt_footer, sizeof node->bt_footer);
370 }
371 
375 static void btree_create(struct m0_be_btree *btree,
376  struct m0_be_tx *tx,
377  const struct m0_fid *btree_fid)
378 {
379  m0_format_header_pack(&btree->bb_header, &(struct m0_format_tag){
380  .ot_version = M0_BE_BTREE_FORMAT_VERSION,
381  .ot_type = M0_FORMAT_TYPE_BE_BTREE,
382  .ot_footer_offset = offsetof(struct m0_be_btree, bb_footer)
383  });
384  m0_cookie_new(&btree->bb_cookie_gen);
385  m0_cookie_init(&btree->bb_backlink.bli_tree, &btree->bb_cookie_gen);
386  btree->bb_backlink.bli_gen = btree->bb_seg->bs_gen;
387  btree->bb_backlink.bli_type = btree->bb_ops->ko_type;
388  btree->bb_backlink.bli_fid = *btree_fid;
389  btree_root_set(btree, be_btree_node_alloc(btree, tx));
390  mem_update(btree, tx, btree, sizeof(struct m0_be_btree));
391 
392  /* memory for the node has to be reserved by m0_be_tx_open() */
393  M0_ASSERT(btree->bb_root != NULL);
394 }
395 
396 static void be_btree_set_node_params(struct m0_be_bnode *p_node,
397  unsigned int num_active_key,
398  unsigned int level,
399  bool isleaf)
400 {
401  p_node->bt_num_active_key = num_active_key;
402  p_node->bt_level = level;
403  p_node->bt_isleaf = isleaf;
404 }
405 
413 static struct m0_be_bnode *
414 be_btree_node_alloc(const struct m0_be_btree *btree, struct m0_be_tx *tx)
415 {
416  struct m0_be_bnode *node;
417 
418  /* Allocate memory for the node */
419  node = (struct m0_be_bnode *)mem_alloc(btree, tx,
420  sizeof(struct m0_be_bnode),
421  M0_BITS(M0_BAP_NORMAL));
422  M0_ASSERT(node != NULL); /* @todo: analyse return code */
423 
424  m0_format_header_pack(&node->bt_header, &(struct m0_format_tag){
425  .ot_version = M0_BE_BNODE_FORMAT_VERSION,
426  .ot_type = M0_FORMAT_TYPE_BE_BNODE,
427  .ot_footer_offset = offsetof(struct m0_be_bnode, bt_footer)
428  });
429 
430  be_btree_set_node_params(node, 0, 0, true);
431  node->bt_next = NULL;
432  node->bt_backlink = btree->bb_backlink;
433 
434  m0_format_footer_update(node);
435  mem_update(btree, tx, node, sizeof *node);
436 
437  return node;
438 }
439 
443 static void btree_node_free(struct m0_be_bnode *node,
444  const struct m0_be_btree *btree,
445  struct m0_be_tx *tx)
446 {
447  /* invalidate header so that recovery tool can skip freed records */
448  node->bt_header.hd_magic = 0;
449  M0_BE_TX_CAPTURE_PTR(btree->bb_seg, tx, &node->bt_header.hd_magic);
450  mem_free(btree, tx, node);
451 }
452 
462 static void be_btree_split_child(struct m0_be_btree *btree,
463  struct m0_be_tx *tx,
464  struct m0_be_bnode *parent,
465  unsigned int index)
466 {
467  int i;
468  struct m0_be_bnode *child = parent->bt_child_arr[index];
469  struct m0_be_bnode *new_child = be_btree_node_alloc(btree, tx);
470  M0_ASSERT(new_child != NULL);
471 
472  be_btree_set_node_params(new_child, (BTREE_FAN_OUT - 1),
473  child->bt_level, child->bt_isleaf);
474 
475  /* Copy the latter half keys from the current child to the new child */
476  i = 0;
477  while (i < new_child->bt_num_active_key) {
478  new_child->bt_kv_arr[i] = child->bt_kv_arr[i + BTREE_FAN_OUT];
479  i++;
480  }
481 
482  /* Update the child pointer field */
483  if (!child->bt_isleaf) {
484  for (i = 0; i < BTREE_FAN_OUT; i++) {
485  new_child->bt_child_arr[i] =
486  child->bt_child_arr[i + BTREE_FAN_OUT];
487  }
488  }
489 
490  /* re-calculate checksum after all fields has been updated */
491  m0_format_footer_update(new_child);
492 
493  child->bt_num_active_key = BTREE_FAN_OUT - 1;
494  m0_format_footer_update(child);
495 
496  /* The index of the node to be split should be less than or equal to the
497  number of active keys on the parent node */
498  M0_PRE(index <= parent->bt_num_active_key);
499 
500  /* In the parent node's arr, make space for the new child */
501  for (i = parent->bt_num_active_key + 1; i > index + 1; i--) {
502  parent->bt_child_arr[i] = parent->bt_child_arr[i - 1];
503  parent->bt_kv_arr[i - 1] = parent->bt_kv_arr[i - 2];
504  }
505 
506  /* Update parent */
507  parent->bt_child_arr[index + 1] = new_child;
508  parent->bt_kv_arr[index] = child->bt_kv_arr[BTREE_FAN_OUT - 1];
509  parent->bt_num_active_key++;
510 
511  /* re-calculate checksum after all fields has been updated */
512  m0_format_footer_update(parent);
513 
514  /* Update affected memory regions in tx: */
515  btree_node_update(parent, btree, tx);
516  btree_node_update(child, btree, tx);
517  btree_node_update(new_child, btree, tx);
518 }
519 
529 static void be_btree_insert_into_nonfull(struct m0_be_btree *btree,
530  struct m0_be_tx *tx,
531  struct m0_be_bnode *node,
532  struct be_btree_key_val *kv)
533 {
534  void *key = kv->btree_key;
535  int i = node->bt_num_active_key - 1;
536 
537  while (!node->bt_isleaf)
538  {
539  while (i >= 0 &&
540  key_lt(btree, key, node->bt_kv_arr[i].btree_key))
541  i--;
542  i++;
543 
544  if (node->bt_child_arr[i]->bt_num_active_key == KV_NR) {
545  be_btree_split_child(btree, tx, node, i);
546  if (key_gt(btree, key, node->bt_kv_arr[i].btree_key))
547  i++;
548  }
549  node = node->bt_child_arr[i];
550  i = node->bt_num_active_key - 1;
551  }
552 
553  while (i >= 0 &&
554  key_lt(btree, key, node->bt_kv_arr[i].btree_key)) {
555  node->bt_kv_arr[i + 1] = node->bt_kv_arr[i];
556  i--;
557  }
558  node->bt_kv_arr[i + 1] = *kv;
559  node->bt_num_active_key++;
560 
561  m0_format_footer_update(node);
562  /* Update affected memory regions */
563  btree_node_update(node, btree, tx);
564 }
565 
574 static void be_btree_insert_newkey(struct m0_be_btree *btree,
575  struct m0_be_tx *tx,
576  struct be_btree_key_val *kv)
577 {
578  struct m0_be_bnode *old_root;
579  struct m0_be_bnode *new_root;
580 
581  M0_PRE(btree_invariant(btree));
582  M0_PRE(btree_node_invariant(btree, btree->bb_root, true));
583  M0_PRE_EX(btree_node_subtree_invariant(btree, btree->bb_root));
584  M0_PRE_EX(be_btree_search(btree, kv->btree_key) == NULL);
585 
586  old_root = btree->bb_root;
587  if (old_root->bt_num_active_key != KV_NR) {
588  be_btree_insert_into_nonfull(btree, tx, old_root, kv);
589  } else {
590  new_root = be_btree_node_alloc(btree, tx);
591  M0_ASSERT(new_root != NULL);
592 
593  new_root->bt_level = btree->bb_root->bt_level + 1;
594  btree_root_set(btree, new_root);
595  be_btree_set_node_params(new_root, 0, new_root->bt_level,
596  false);
597  new_root->bt_child_arr[0] = old_root;
598  m0_format_footer_update(new_root);
599  be_btree_split_child(btree, tx, new_root, 0);
600  be_btree_insert_into_nonfull(btree, tx, new_root, kv);
601 
602  /* Update tree structure itself */
603  mem_update(btree, tx, btree, sizeof(struct m0_be_btree));
604  }
605 
606  M0_POST(btree_invariant(btree));
607  M0_POST(btree_node_invariant(btree, btree->bb_root, true));
608  M0_POST_EX(btree_node_subtree_invariant(btree, btree->bb_root));
609 }
610 
619 static void be_btree_get_max_key_pos(struct m0_be_bnode *node,
620  struct btree_node_pos *pos)
621 {
622  while (node != NULL && !node->bt_isleaf)
623  node = node->bt_child_arr[node->bt_num_active_key];
624 
625  pos->bnp_node = node;
626  pos->bnp_index = (node != NULL && node->bt_num_active_key > 0) ?
627  node->bt_num_active_key - 1 : 0;
628 }
629 
638 static void be_btree_get_min_key_pos(struct m0_be_bnode *node,
639  struct btree_node_pos *pos)
640 {
641  while (node != NULL && !node->bt_isleaf)
642  node = node->bt_child_arr[0];
643 
644  pos->bnp_node = node;
645  pos->bnp_index = 0;
646 }
647 
648 static void be_btree_shift_key_vals(struct m0_be_bnode *dest,
649  struct m0_be_bnode *src,
650  unsigned int start_index,
651  unsigned int key_src_offset,
652  unsigned int key_dest_offset,
653  unsigned int child_src_offset,
654  unsigned int child_dest_offset,
655  unsigned int stop_index)
656 {
657  unsigned int i = start_index;
658  while (i < stop_index)
659  {
660  dest->bt_kv_arr[i + key_dest_offset] =
661  src->bt_kv_arr[i + key_src_offset];
662  dest->bt_child_arr[i + child_dest_offset ] =
663  src->bt_child_arr[i + child_src_offset];
664  ++i;
665  }
666 }
667 
679 static struct m0_be_bnode *
680 be_btree_merge_siblings(struct m0_be_tx *tx,
681  struct m0_be_btree *tree,
682  struct m0_be_bnode *parent,
683  unsigned int idx)
684 {
685  struct m0_be_bnode *node1;
686  struct m0_be_bnode *node2;
687 
688  M0_ENTRY("n=%p i=%d", parent, idx);
689 
690  if (idx == parent->bt_num_active_key)
691  idx--;
692 
693  node1 = parent->bt_child_arr[idx];
694  node2 = parent->bt_child_arr[idx + 1];
695 
696  node1->bt_kv_arr[node1->bt_num_active_key++] = parent->bt_kv_arr[idx];
697 
698  M0_ASSERT(node1->bt_num_active_key + node2->bt_num_active_key <= KV_NR);
699 
700  be_btree_shift_key_vals(node1, node2, 0, 0, node1->bt_num_active_key, 0,
701  node1->bt_num_active_key,
702  node2->bt_num_active_key);
703 
704  node1->bt_child_arr[node2->bt_num_active_key+node1->bt_num_active_key] =
705  node2->bt_child_arr[node2->bt_num_active_key];
706  node1->bt_num_active_key += node2->bt_num_active_key;
707 
708  /* re-calculate checksum after all fields has been updated */
709  m0_format_footer_update(node1);
710 
711  /* update parent */
712  be_btree_shift_key_vals(parent, parent, idx, 1, 0, 2, 1,
713  parent->bt_num_active_key - 1);
714 
715  parent->bt_num_active_key--;
716  /* re-calculate checksum after all fields has been updated */
717  m0_format_footer_update(parent);
718 
719  btree_node_free(node2, tree, tx);
720 
721  if (parent->bt_num_active_key == 0 && tree->bb_root == parent) {
722  btree_node_free(parent, tree, tx);
723  btree_root_set(tree, node1);
724  mem_update(tree, tx, tree, sizeof(struct m0_be_btree));
725  } else {
726  /* Update affected memory regions */
727  btree_node_update(parent, tree, tx);
728  }
729 
730  btree_node_update(node1, tree, tx);
731 
732  M0_LEAVE();
733  return node1;
734 }
735 
736 
737 static void be_btree_move_parent_key_to_right_child(struct m0_be_bnode *parent,
738  struct m0_be_bnode *lch,
739  struct m0_be_bnode *rch,
740  unsigned int idx)
741 {
742  unsigned int i = rch->bt_num_active_key;
743 
744  while (i > 0) {
745  rch->bt_kv_arr[i] = rch->bt_kv_arr[i - 1];
746  rch->bt_child_arr[i + 1] = rch->bt_child_arr[i];
747  --i;
748  }
749  rch->bt_child_arr[1] = rch->bt_child_arr[0];
750  rch->bt_kv_arr[0] = parent->bt_kv_arr[idx];
751  rch->bt_child_arr[0] =
752  lch->bt_child_arr[lch->bt_num_active_key];
753  lch->bt_child_arr[lch->bt_num_active_key] = NULL;
754  parent->bt_kv_arr[idx] =
755  lch->bt_kv_arr[lch->bt_num_active_key-1];
756  lch->bt_num_active_key--;
757  rch->bt_num_active_key++;
758 }
759 
760 static void be_btree_move_parent_key_to_left_child(struct m0_be_bnode *parent,
761  struct m0_be_bnode *lch,
762  struct m0_be_bnode *rch,
763  unsigned int idx)
764 {
765  unsigned int i;
766 
767  lch->bt_kv_arr[lch->bt_num_active_key] =
768  parent->bt_kv_arr[idx];
769  lch->bt_child_arr[lch->bt_num_active_key + 1] =
770  rch->bt_child_arr[0];
771  lch->bt_num_active_key++;
772  parent->bt_kv_arr[idx] = rch->bt_kv_arr[0];
773  i = 0;
774  while (i < rch->bt_num_active_key - 1) {
775  rch->bt_kv_arr[i] = rch->bt_kv_arr[i + 1];
776  rch->bt_child_arr[i] = rch->bt_child_arr[i + 1];
777  ++i;
778  }
779  rch->bt_child_arr[i] = rch->bt_child_arr[i + 1];
780  rch->bt_child_arr[i + 1] = NULL;
781  rch->bt_num_active_key--;
782 }
783 
795 static void be_btree_move_parent_key(struct m0_be_btree *tree,
796  struct m0_be_tx *tx,
797  struct m0_be_bnode *parent,
798  enum position_t pos,
799  unsigned int idx)
800 {
801  struct m0_be_bnode *lch;
802  struct m0_be_bnode *rch;
803 
804  M0_ENTRY("n=%p i=%d dir=%d", parent, idx, pos);
805 
806  if (pos == P_RIGHT)
807  idx--;
808 
809  lch = parent->bt_child_arr[idx];
810  rch = parent->bt_child_arr[idx + 1];
811 
812  if (pos == P_LEFT)
813  be_btree_move_parent_key_to_left_child(parent, lch, rch, idx);
814  else
815  be_btree_move_parent_key_to_right_child(parent, lch, rch, idx);
816 
817  /* re-calculate checksum after all fields has been updated */
818  m0_format_footer_update(lch);
819  m0_format_footer_update(rch);
820  m0_format_footer_update(parent);
821 
822  /* Update affected memory regions in tx: */
823  btree_node_update(parent, tree, tx);
824  btree_node_update(lch, tree, tx);
825  btree_node_update(rch, tree, tx);
826 
827  M0_LEAVE();
828 }
829 
839 void be_btree_delete_key_from_node(struct m0_be_btree *tree,
840  struct m0_be_tx *tx,
841  struct btree_node_pos *bnode_pos)
842 {
843  struct m0_be_bnode *bnode = bnode_pos->bnp_node;
844  unsigned int idx;
845 
846  if (bnode->bt_isleaf) {
847  idx = bnode_pos->bnp_index;
848 
849  btree_pair_release(tree, tx, &bnode->bt_kv_arr[idx]);
850 
851  while (idx < bnode->bt_num_active_key - 1) {
852  bnode->bt_kv_arr[idx] = bnode->bt_kv_arr[idx+1];
853  ++idx;
854  }
855  /*
856  * There are chances that last key value might have swapped.
857  * btree_node_update() captures key values based on
858  * bt_num_active_key.
859  * Capture key values here to avoid checksum mismatch.
860  */
861  if(bnode_pos->bnp_index == (bnode->bt_num_active_key - 1)) {
862  mem_update(tree, tx,
863  &bnode->bt_kv_arr[bnode_pos->bnp_index],
864  sizeof
865  bnode->bt_kv_arr[bnode_pos->bnp_index]);
866  }
867 
868  bnode->bt_num_active_key--;
869 
870  /* re-calculate checksum after all fields has been updated */
871  m0_format_footer_update(bnode);
872 
873  if (bnode->bt_num_active_key == 0 && bnode != tree->bb_root)
874  btree_node_free(bnode, tree, tx);
875  else
876  /* Update affected memory regions in tx: */
877  btree_node_update(bnode, tree, tx);
878  }
879 }
880 
881 static void btree_node_child_delete(struct m0_be_btree *btree,
882  struct m0_be_tx *tx,
883  struct m0_be_bnode *node,
884  unsigned index,
885  struct btree_node_pos *child,
886  bool left)
887 {
888  M0_ASSERT(child->bnp_node->bt_isleaf);
889  M0_LOG(M0_DEBUG, "swap%s with n=%p i=%d", left ? "L" : "R",
890  child->bnp_node,
891  child->bnp_index);
892  M0_SWAP(child->bnp_node->bt_kv_arr[child->bnp_index],
893  node->bt_kv_arr[index]);
894  /*
895  * Update checksum for parent, for child it will be updated
896  * in delete_key_from_node().
897  */
898  btree_node_keyval_update(node, btree, tx, index);
899 }
911 static int be_btree_delete_key(struct m0_be_btree *tree,
912  struct m0_be_tx *tx,
913  struct m0_be_bnode *bnode,
914  void *key)
915 {
916  bool outerloop = true;
917  struct m0_be_bnode *righsib;
918  struct m0_be_bnode *leftsib;
919  struct m0_be_bnode *p_node = NULL;
920  struct btree_node_pos child;
921  struct btree_node_pos bnode_pos;
922  int rc = -1;
923  unsigned int iter;
924  unsigned int idx;
925 
926  M0_PRE(btree_invariant(tree));
927  M0_PRE(btree_node_invariant(tree, tree->bb_root, true));
928  M0_PRE_EX(btree_node_subtree_invariant(tree, tree->bb_root));
929 
930  M0_ENTRY("n=%p", bnode);
931 
932  while (outerloop) {
933  while (true) {
934  /* Check if keys are available in bnode */
935  if (bnode->bt_num_active_key == 0) {
936  outerloop = false;
937  break;
938  }
939 
940  /* Retrieve index of the key equal to or greater than*/
941  /* key being searched */
942  iter = 0;
943  while (iter < bnode->bt_num_active_key &&
944  key_gt(tree, key,
945  bnode->bt_kv_arr[iter].btree_key))
946  iter++;
947 
948  idx = iter;
949 
950  /* check if key is found */
951  if (iter < bnode->bt_num_active_key &&
952  key_eq(tree, key, bnode->bt_kv_arr[iter].btree_key))
953  break;
954 
955  /* Reached leaf node, nothing left to search */
956  if (bnode->bt_isleaf) {
957  outerloop = false;
958  break;
959  }
960 
961  p_node = bnode;
962  bnode = bnode->bt_child_arr[iter];
963  if (bnode == NULL) {
964  outerloop = false;
965  break;
966  }
967 
968  if (iter == p_node->bt_num_active_key) {
969  leftsib = p_node->bt_child_arr[iter - 1];
970  righsib = NULL;
971  } else if (iter == 0) {
972  leftsib = NULL;
973  righsib = p_node->bt_child_arr[iter + 1];
974  } else {
975  leftsib = p_node->bt_child_arr[iter - 1];
976  righsib = p_node->bt_child_arr[iter + 1];
977  }
978 
979  if (bnode->bt_num_active_key == BTREE_FAN_OUT - 1 &&
980  p_node) {
981  if (righsib &&
982  (righsib->bt_num_active_key >
983  BTREE_FAN_OUT - 1)) {
984  be_btree_move_parent_key(tree, tx,
985  p_node, P_LEFT, iter);
986  } else if (leftsib &&
987  (leftsib->bt_num_active_key >
988  BTREE_FAN_OUT - 1)) {
989  be_btree_move_parent_key(tree, tx,
990  p_node, P_RIGHT, iter);
991  } else if (leftsib &&
992  (leftsib->bt_num_active_key ==
993  BTREE_FAN_OUT - 1)) {
994  M0_LOG(M0_DEBUG, "mergeL");
995  bnode = be_btree_merge_siblings(tx,
996  tree,
997  p_node,
998  iter-1);
999  } else if (righsib &&
1000  (righsib->bt_num_active_key ==
1001  BTREE_FAN_OUT - 1)) {
1002  M0_LOG(M0_DEBUG, "mergeR");
1003  bnode = be_btree_merge_siblings(tx,
1004  tree,
1005  p_node,
1006  iter);
1007  }
1008  }
1009  }
1010 
1011  if (!outerloop)
1012  break;
1013 
1014  M0_LOG(M0_DEBUG, "found bnode=%p lf=%d nr=%d idx=%d", bnode,
1015  !!bnode->bt_isleaf, bnode->bt_num_active_key, idx);
1016  rc = 0;
1017 
1018  M0_ASSERT(ergo(bnode->bt_isleaf && bnode != tree->bb_root,
1019  bnode->bt_num_active_key > BTREE_FAN_OUT - 1));
1020 
1021  /* Node with the key is found and its leaf node, leaf node has
1022  * keys greater than the minimum required, remove key
1023  */
1024  if (bnode->bt_isleaf &&
1025  (bnode->bt_num_active_key > BTREE_FAN_OUT - 1 ||
1026  bnode == tree->bb_root)) {
1027  M0_LOG(M0_DEBUG, "case1");
1028  bnode_pos.bnp_node = bnode;
1029  bnode_pos.bnp_index = idx;
1030  be_btree_delete_key_from_node(tree, tx, &bnode_pos);
1031  break;
1032  } else {
1033  M0_ASSERT(!bnode->bt_isleaf);
1034  }
1035 
1036  /* Internal node with key is found */
1037  M0_LOG(M0_DEBUG, "case2");
1038  if (bnode->bt_child_arr[idx]->bt_num_active_key >
1039  BTREE_FAN_OUT - 1) {
1040  be_btree_get_max_key_pos(bnode->bt_child_arr[idx],
1041  &child);
1042  btree_node_child_delete(tree, tx, bnode,
1043  idx, &child, false);
1044  bnode = bnode->bt_child_arr[idx];
1045  } else if (bnode->bt_child_arr[idx + 1]->bt_num_active_key >
1046  BTREE_FAN_OUT - 1) {
1047  be_btree_get_min_key_pos(bnode->bt_child_arr[idx + 1],
1048  &child);
1049  btree_node_child_delete(tree, tx, bnode,
1050  idx, &child, true);
1051  bnode = bnode->bt_child_arr[idx + 1];
1052  } else {
1053  M0_LOG(M0_DEBUG, "case2-merge");
1054  bnode = be_btree_merge_siblings(tx, tree, bnode, idx);
1055  }
1056  continue;
1057  }
1058 
1059  M0_POST(btree_invariant(tree));
1060  M0_POST(btree_node_invariant(tree, tree->bb_root, true));
1061  M0_POST_EX(btree_node_subtree_invariant(tree, tree->bb_root));
1062  M0_LEAVE("rc=%d", rc);
1063  return M0_RC(rc);
1064 }
1065 
1066 static void node_push(struct m0_be_btree_cursor *it, struct m0_be_bnode *node,
1067  int idx)
1068 {
1069  struct m0_be_btree_cursor_stack_entry *se;
1070 
1071  M0_ASSERT(it->bc_stack_pos < ARRAY_SIZE(it->bc_stack));
1072  se = &it->bc_stack[it->bc_stack_pos++];
1073  se->bs_node = node;
1074  se->bs_idx = idx;
1075 }
1076 
1077 static struct m0_be_bnode *node_pop(struct m0_be_btree_cursor *it, int *idx)
1078 {
1079  struct m0_be_bnode *node = NULL;
1080  struct m0_be_btree_cursor_stack_entry *se;
1081 
1082  if (it->bc_stack_pos > 0) {
1083  se = &it->bc_stack[--it->bc_stack_pos];
1084  node = se->bs_node;
1085  *idx = se->bs_idx;
1086  }
1087  return node;
1088 }
1089 
1101 struct btree_node_pos
1102 be_btree_get_btree_node(struct m0_be_btree_cursor *it, const void *key, bool slant)
1103 {
1104  int idx;
1105  struct m0_be_btree *tree = it->bc_tree;
1106  struct m0_be_bnode *bnode = tree->bb_root;
1107  struct btree_node_pos bnode_pos = { .bnp_node = NULL };
1108 
1109  it->bc_stack_pos = 0;
1110 
1111  while (true) {
1112  /* Retrieve index of the key equal to or greater than */
1113  /* the key being searched */
1114  idx = 0;
1115  while (idx < bnode->bt_num_active_key &&
1116  key_gt(tree, key, bnode->bt_kv_arr[idx].btree_key)) {
1117  idx++;
1118  }
1119 
1120  /* If key is found, copy key-value pair */
1121  if (idx < bnode->bt_num_active_key &&
1122  key_eq(tree, key, bnode->bt_kv_arr[idx].btree_key)) {
1123  bnode_pos.bnp_node = bnode;
1124  bnode_pos.bnp_index = idx;
1125  break;
1126  }
1127 
1128  /* Return NULL in case of leaf node and did not get key*/
1129  if (bnode->bt_isleaf) {
1130  while (bnode != NULL && idx == bnode->bt_num_active_key)
1131  bnode = node_pop(it, &idx);
1132  if (slant && bnode != NULL) {
1133  bnode_pos.bnp_node = bnode;
1134  bnode_pos.bnp_index = idx;
1135  }
1136  break;
1137  }
1138  /* Move to a child node */
1139  node_push(it, bnode, idx);
1140  bnode = bnode->bt_child_arr[idx];
1141  }
1142  return bnode_pos;
1143 }
1144 
1145 /*
1146  * This function is used to destory the btree
1147  * @param btree The btree to be destroyed
1148  * @param tx The pointer to tx
1149  */
1150 static void be_btree_destroy(struct m0_be_btree *btree, struct m0_be_tx *tx)
1151 {
1152  int i = 0;
1153  struct m0_be_bnode *head;
1154  struct m0_be_bnode *tail;
1155  struct m0_be_bnode *node_to_del;
1156 
1157  head = btree->bb_root;
1158  tail = head;
1159 
1160  head->bt_next = NULL;
1161  tail->bt_next = NULL;
1162  while (head != NULL) {
1163  if (!head->bt_isleaf) {
1164  i = 0;
1165  while (i < head->bt_num_active_key + 1) {
1166  tail->bt_next = head->bt_child_arr[i];
1167  m0_format_footer_update(tail);
1168  tail = tail->bt_next;
1169  tail->bt_next = NULL;
1170  ++i;
1171  }
1172  m0_format_footer_update(tail);
1173  }
1174  node_to_del = head;
1175  head = head->bt_next;
1176  i = 0;
1177  while (i < node_to_del->bt_num_active_key) {
1178  btree_pair_release(btree, tx,
1179  &node_to_del->bt_kv_arr[i]);
1180  ++i;
1181  }
1182  btree_node_free(node_to_del, btree, tx);
1183  }
1184  m0_format_footer_update(head);
1185  btree->bb_backlink.bli_type = M0_BBT_INVALID;
1186  btree_root_set(btree, NULL);
1187  mem_update(btree, tx, btree, sizeof(struct m0_be_btree));
1188 }
1189 
1202 static void btree_truncate(struct m0_be_btree *btree, struct m0_be_tx *tx,
1203  m0_bcount_t limit)
1204 
1205 {
1206  struct m0_be_bnode *node;
1207  struct m0_be_bnode *parent;
1208  unsigned int i;
1209 
1210  /* Add one more reserve for non-leaf node. */
1211  if (limit > 1)
1212  limit--;
1213 
1214  node = btree->bb_root;
1215 
1216  while (node != NULL && limit > 0) {
1217  parent = NULL;
1218  if (!node->bt_isleaf) {
1219  parent = node;
1220  i = node->bt_num_active_key;
1221  node = node->bt_child_arr[i];
1222  }
1223  if (!node->bt_isleaf)
1224  continue;
1225 
1226  while (node->bt_num_active_key > 0 && limit > 0) {
1227  limit--;
1228  node->bt_num_active_key--;
1229  i = node->bt_num_active_key;
1230  btree_pair_release(btree, tx, &node->bt_kv_arr[i]);
1231  }
1232  m0_format_footer_update(node);
1233  if (node->bt_num_active_key > 0)
1234  continue;
1235  /*
1236  * Cleared all keys in the leaf node.
1237  */
1238  if (node == btree->bb_root) {
1239  /*
1240  * Do not destroy tree root. Keep empty
1241  * tree alive. So, we are done.
1242  */
1243  break;
1244  }
1245  btree_node_free(node, btree, tx);
1246  if (parent != NULL) {
1247  /*
1248  * If this is not a root (checked above), sure node has
1249  * a parent.
1250  * If parent is empty, reclassify it to a leaf.
1251  */
1252  i = parent->bt_num_active_key;
1253  /*
1254  * Release parent->bt_num_active_key -1 key-val pair
1255  * after freeing
1256  * node->bt_child_arr[node->bt_num_active_key]
1257  * leaf node
1258  */
1259  if (i > 0)
1260  btree_pair_release(btree, tx,
1261  &parent->bt_kv_arr[i-1]);
1262 
1263  if (limit > 0)
1264  limit--;
1265  if (i == 0)
1266  parent->bt_isleaf = true;
1267  else
1268  parent->bt_num_active_key--;
1269  if (parent == btree->bb_root &&
1270  parent->bt_num_active_key == 0) {
1271  /*
1272  * Cleared the root, but still have 1
1273  * child. Move the root.
1274  */
1275  btree_root_set(btree, parent->bt_child_arr[0]);
1276  mem_update(btree, tx, btree,
1277  sizeof(struct m0_be_btree));
1278  btree_node_free(parent, btree, tx);
1279  } else {
1280  m0_format_footer_update(parent);
1281  }
1282  /* Simplify our life: restart from the root. */
1283  node = btree->bb_root;
1284  }
1285  }
1286  m0_format_footer_update(btree->bb_root);
1287 }
1288 
1289 /*
1290  * This function is used to search a node in the btree
1291  * @param btree The tree to be searched
1292  * @param key Key of the node to be searched
1293  * @return key-value pair
1294  */
1295 static struct be_btree_key_val *be_btree_search(struct m0_be_btree *btree,
1296  void *key)
1297 {
1298  struct m0_be_btree_cursor btree_cursor;
1299  struct btree_node_pos node_pos;
1300  struct be_btree_key_val *key_val = NULL;
1301 
1302  btree_cursor.bc_tree = btree;
1303  node_pos = be_btree_get_btree_node(&btree_cursor, key, false);
1304 
1305  if (node_pos.bnp_node)
1306  key_val = &node_pos.bnp_node->bt_kv_arr[node_pos.bnp_index];
1307 
1308  return key_val;
1309 }
1310 
1319 static void *be_btree_get_max_key(struct m0_be_btree *tree)
1320 {
1321  struct btree_node_pos node;
1322 
1323  be_btree_get_max_key_pos(tree->bb_root, &node);
1324  if (node.bnp_node->bt_num_active_key == 0)
1325  return NULL;
1326  else
1327  return node.bnp_node->bt_kv_arr[node.bnp_index].btree_key;
1328 }
1329 
1338 static void *be_btree_get_min_key(struct m0_be_btree *tree)
1339 {
1340  struct btree_node_pos node;
1341 
1342  be_btree_get_min_key_pos(tree->bb_root, &node);
1343  if (node.bnp_node->bt_num_active_key == 0)
1344  return NULL;
1345  else
1346  return node.bnp_node->bt_kv_arr[0].btree_key;
1347 }
1348 
1349 static void btree_pair_release(struct m0_be_btree *btree, struct m0_be_tx *tx,
1350  struct be_btree_key_val *kv)
1351 {
1352  mem_free(btree, tx, kv->btree_key);
1353 }
1354 
1365 static void btree_save(struct m0_be_btree *tree,
1366  struct m0_be_tx *tx,
1367  struct m0_be_op *op,
1368  const struct m0_buf *key,
1369  const struct m0_buf *val,
1370  struct m0_be_btree_anchor *anchor,
1371  enum btree_save_optype optype,
1372  uint64_t zonemask)
1373 {
1374  m0_bcount_t ksz;
1375  m0_bcount_t vsz;
1376  struct be_btree_key_val new_kv;
1377  struct be_btree_key_val *cur_kv;
1378  bool val_overflow = false;
1379 
1380  M0_ENTRY("tree=%p", tree);
1381 
1382  M0_PRE(M0_IN(optype, (BTREE_SAVE_INSERT, BTREE_SAVE_UPDATE,
1383  BTREE_SAVE_OVERWRITE)));
1384 
1385  switch (optype) {
1386  case BTREE_SAVE_OVERWRITE:
1387  M0_BE_CREDIT_DEC(M0_BE_CU_BTREE_DELETE, tx);
1388  /* fallthrough */
1389  case BTREE_SAVE_INSERT:
1390  M0_BE_CREDIT_DEC(M0_BE_CU_BTREE_INSERT, tx);
1391  break;
1392  case BTREE_SAVE_UPDATE:
1393  M0_BE_CREDIT_DEC(M0_BE_CU_BTREE_UPDATE, tx);
1394  break;
1395  }
1396 
1397  btree_op_fill(op, tree, tx, optype == BTREE_SAVE_UPDATE ?
1398  M0_BBO_UPDATE : M0_BBO_INSERT, NULL);
1399 
1400  m0_be_op_active(op);
1401  m0_rwlock_write_lock(btree_rwlock(tree));
1402  if (anchor != NULL) {
1403  anchor->ba_tree = tree;
1404  anchor->ba_write = true;
1405  vsz = anchor->ba_value.b_nob;
1406  anchor->ba_value.b_addr = NULL;
1407  } else
1408  vsz = val->b_nob;
1409 
1410  if (M0_FI_ENABLED("already_exists"))
1411  goto fi_exist;
1412 
1413  op_tree(op)->t_rc = 0;
1414  cur_kv = be_btree_search(tree, key->b_addr);
1415  if ((cur_kv == NULL && optype != BTREE_SAVE_UPDATE) ||
1416  (cur_kv != NULL && optype == BTREE_SAVE_UPDATE) ||
1417  optype == BTREE_SAVE_OVERWRITE) {
1418  if (cur_kv != NULL && optype != BTREE_SAVE_INSERT) {
1419  if (vsz > be_btree_vsize(tree, cur_kv->btree_val)) {
1420  /*
1421  * The size of new value is greater than the
1422  * size of old value, old value area can not be
1423  * re-used for new value. Delete old key/value
1424  * and add new key/value.
1425  */
1426  op_tree(op)->t_rc =
1427  be_btree_delete_key(tree, tx,
1428  tree->bb_root,
1429  cur_kv->btree_key);
1430  val_overflow = true;
1431  } else {
1432  /*
1433  * The size of new value is less than or equal
1434  * to the size of old value, simply rewrite
1435  * old value in this case.
1436  */
1437  if (val != NULL) {
1438  memcpy(cur_kv->btree_val, val->b_addr,
1439  val->b_nob);
1440  mem_update(tree, tx, cur_kv->btree_val,
1441  val->b_nob);
1442  } else
1443  anchor->ba_value.b_addr =
1444  cur_kv->btree_val;
1445  }
1446  }
1447 
1448  if (op_tree(op)->t_rc == 0 &&
1449  (cur_kv == NULL || val_overflow)) {
1450  /* Avoid CPU alignment overhead on values. */
1451  ksz = m0_align(key->b_nob, sizeof(void*));
1452  new_kv.btree_key =
1453  mem_alloc(tree, tx, ksz + vsz, zonemask);
1454  new_kv.btree_val = new_kv.btree_key + ksz;
1455  memcpy(new_kv.btree_key, key->b_addr, key->b_nob);
1456  memset(new_kv.btree_key + key->b_nob, 0,
1457  ksz - key->b_nob);
1458  if (val != NULL) {
1459  memcpy(new_kv.btree_val, val->b_addr, vsz);
1460  mem_update(tree, tx,
1461  new_kv.btree_key, ksz + vsz);
1462  } else {
1463  mem_update(tree, tx, new_kv.btree_key, ksz);
1464  anchor->ba_value.b_addr = new_kv.btree_val;
1465  }
1466 
1467  be_btree_insert_newkey(tree, tx, &new_kv);
1468  }
1469  } else {
1470 fi_exist:
1471  op_tree(op)->t_rc = -EEXIST;
1472  M0_LOG(M0_NOTICE, "the key entry at %p already exist",
1473  key->b_addr);
1474  }
1475 
1476  if (anchor == NULL)
1477  m0_rwlock_write_unlock(btree_rwlock(tree));
1478  m0_be_op_done(op);
1479  M0_LEAVE("tree=%p", tree);
1480 }
1481 
1482 
1483 /* ------------------------------------------------------------------
1484  * Btree external interfaces implementation
1485  * ------------------------------------------------------------------ */
1486 
1487 M0_INTERNAL void m0_be_btree_init(struct m0_be_btree *tree,
1488  struct m0_be_seg *seg,
1489  const struct m0_be_btree_kv_ops *ops)
1490 {
1491  M0_ENTRY("tree=%p seg=%p", tree, seg);
1492  M0_PRE(ops != NULL);
1493 
1494  m0_rwlock_init(btree_rwlock(tree));
1495  tree->bb_ops = ops;
1496  tree->bb_seg = seg;
1497 
1498  if (!m0_be_seg_contains(seg, tree->bb_root))
1499  tree->bb_root = NULL;
1500  M0_LEAVE();
1501 }
1502 
1503 M0_INTERNAL void m0_be_btree_fini(struct m0_be_btree *tree)
1504 {
1505  M0_ENTRY("tree=%p", tree);
1506  M0_PRE(ergo(tree->bb_root != NULL && tree->bb_header.hd_magic != 0,
1507  btree_invariant(tree)));
1508  m0_rwlock_fini(btree_rwlock(tree));
1509  M0_LEAVE();
1510 }
1511 
1512 M0_INTERNAL void m0_be_btree_create(struct m0_be_btree *tree,
1513  struct m0_be_tx *tx,
1514  struct m0_be_op *op,
1515  const struct m0_fid *btree_fid)
1516 {
1517  M0_ENTRY("tree=%p", tree);
1518  M0_PRE(tree->bb_root == NULL && tree->bb_ops != NULL);
1519  M0_PRE(m0_fid_tget(btree_fid) == m0_btree_fid_type.ft_id);
1520  /* M0_PRE(m0_rwlock_is_locked(tx->t_be.b_tx.te_lock)); */
1521 
1522  btree_op_fill(op, tree, tx, M0_BBO_CREATE, NULL);
1523 
1524  m0_be_op_active(op);
1525  m0_rwlock_write_lock(btree_rwlock(tree));
1526 
1527  btree_create(tree, tx, btree_fid);
1528 
1529  m0_rwlock_write_unlock(btree_rwlock(tree));
1530  op_tree(op)->t_rc = 0;
1531  m0_be_op_done(op);
1532  M0_POST(btree_invariant(tree));
1533  M0_POST(btree_node_invariant(tree, tree->bb_root, true));
1534  M0_POST_EX(btree_node_subtree_invariant(tree, tree->bb_root));
1535  M0_LEAVE();
1536 }
1537 
1538 M0_INTERNAL void m0_be_btree_destroy(struct m0_be_btree *tree,
1539  struct m0_be_tx *tx,
1540  struct m0_be_op *op)
1541 {
1542  M0_ENTRY("tree=%p", tree);
1543  /* XXX TODO The right approach to pursue is to let the user
1544  * destroy only empty trees. So ideally here would be
1545  * M0_PRE(m0_be_btree_is_empty(tree)); */
1546  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
1547  M0_PRE(btree_invariant(tree));
1548  M0_PRE(btree_node_invariant(tree, tree->bb_root, true));
1549  M0_PRE_EX(btree_node_subtree_invariant(tree, tree->bb_root));
1550 
1551  btree_op_fill(op, tree, tx, M0_BBO_DESTROY, NULL);
1552 
1553  m0_be_op_active(op);
1554  m0_rwlock_write_lock(btree_rwlock(tree));
1555 
1556  be_btree_destroy(tree, tx);
1557 
1558  m0_rwlock_write_unlock(btree_rwlock(tree));
1559  op_tree(op)->t_rc = 0;
1560  m0_be_op_done(op);
1561  M0_LEAVE();
1562 }
1563 
1564 M0_INTERNAL void m0_be_btree_truncate(struct m0_be_btree *tree,
1565  struct m0_be_tx *tx,
1566  struct m0_be_op *op,
1567  m0_bcount_t limit)
1568 {
1569  M0_ENTRY("tree=%p", tree);
1570  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
1571  /*
1572  * btree_truncate() violates the invariant, by removing the records from
1573  * the leaf nodes without merging them. The only thing that can be done
1574  * with a tree being truncated, is to truncate it further. Therefore
1575  * tree_invariant() cannot be asserted on entry or exit.
1576  */
1577  btree_op_fill(op, tree, tx, M0_BBO_DESTROY, NULL);
1578 
1579  m0_be_op_active(op);
1580  m0_rwlock_write_lock(btree_rwlock(tree));
1581 
1582  btree_truncate(tree, tx, limit);
1583 
1584  m0_rwlock_write_unlock(btree_rwlock(tree));
1585  op_tree(op)->t_rc = 0;
1586  m0_be_op_done(op);
1587  M0_LEAVE();
1588 }
1589 
1590 static void btree_node_alloc_credit(const struct m0_be_btree *tree,
1591  struct m0_be_tx_credit *accum)
1592 {
1593  btree_mem_alloc_credit(tree, sizeof(struct m0_be_bnode), accum);
1594 }
1595 
1596 static void btree_node_update_credit(struct m0_be_tx_credit *accum,
1597  m0_bcount_t nr)
1598 {
1599  struct m0_be_tx_credit cred = {};
1600 
1601  /* struct m0_be_bnode update x2 */
1602  m0_be_tx_credit_mac(&cred,
1603  &M0_BE_TX_CREDIT_TYPE(struct m0_be_bnode), 2);
1604 
1605  m0_be_tx_credit_mac(accum, &cred, nr);
1606 }
1607 
1608 static void btree_node_free_credit(const struct m0_be_btree *tree,
1609  struct m0_be_tx_credit *accum)
1610 {
1611  btree_mem_free_credit(tree, sizeof(struct m0_be_bnode), accum);
1612  m0_be_tx_credit_add(accum,
1613  &M0_BE_TX_CREDIT_TYPE(uint64_t));
1614  btree_node_update_credit(accum, 1); /* for parent */
1615 }
1616 
1617 /* XXX */
1618 static void btree_credit(const struct m0_be_btree *tree,
1619  struct m0_be_tx_credit *accum)
1620 {
1621  uint32_t height;
1622 
1623  height = tree->bb_root == NULL ? 2 : tree->bb_root->bt_level;
1624  m0_be_tx_credit_mul(accum, 2*height + 1);
1625 }
1626 
1627 static void btree_rebalance_credit(const struct m0_be_btree *tree,
1628  struct m0_be_tx_credit *accum)
1629 {
1630  struct m0_be_tx_credit cred = {};
1631 
1632  btree_node_alloc_credit(tree, &cred);
1633  btree_node_update_credit(&cred, 1);
1634  btree_credit(tree, &cred);
1635 
1636  m0_be_tx_credit_add(accum, &cred);
1637 }
1638 
1639 static void kv_insert_credit(const struct m0_be_btree *tree,
1640  m0_bcount_t ksize,
1641  m0_bcount_t vsize,
1642  struct m0_be_tx_credit *accum)
1643 {
1644  struct m0_be_tx_credit kv_update_cred;
1645 
1646  ksize = m0_align(ksize, sizeof(void*));
1647  kv_update_cred = M0_BE_TX_CREDIT(1, ksize + vsize);
1648  btree_mem_alloc_credit(tree, ksize + vsize, accum);
1649  m0_be_tx_credit_add(accum, &kv_update_cred);
1650 }
1651 
1652 static void kv_delete_credit(const struct m0_be_btree *tree,
1653  m0_bcount_t ksize,
1654  m0_bcount_t vsize,
1655  struct m0_be_tx_credit *accum)
1656 {
1657  btree_mem_free_credit(tree, m0_align(ksize, sizeof(void*)) + vsize,
1658  accum);
1659  m0_be_tx_credit_add(accum,
1660  &M0_BE_TX_CREDIT_TYPE(struct be_btree_key_val));
1661  /* capture parent csum in case values swapped during delete */
1662  m0_be_tx_credit_add(accum,
1663  &M0_BE_TX_CREDIT(1,
1664  sizeof(struct m0_format_footer)));
1665 }
1666 
1667 static void btree_node_split_child_credit(const struct m0_be_btree *tree,
1668  struct m0_be_tx_credit *accum)
1669 {
1670  btree_node_alloc_credit(tree, accum);
1671  btree_node_update_credit(accum, 3);
1672 }
1673 
1674 static void insert_credit(const struct m0_be_btree *tree,
1675  m0_bcount_t nr,
1676  m0_bcount_t ksize,
1677  m0_bcount_t vsize,
1678  struct m0_be_tx_credit *accum,
1679  bool use_current_height)
1680 {
1681  struct m0_be_tx_credit cred = {};
1682  uint32_t height;
1683 
1684  if (use_current_height)
1685  height = tree->bb_root == NULL ? 2 : tree->bb_root->bt_level;
1686  else
1687  height = BTREE_HEIGHT_MAX;
1688 
1689  /* for be_btree_insert_into_nonfull() */
1690  btree_node_split_child_credit(tree, &cred);
1691  m0_be_tx_credit_mul(&cred, height);
1692  btree_node_update_credit(&cred, 1);
1693 
1694  /* for be_btree_insert_newkey() */
1695  btree_node_alloc_credit(tree, &cred);
1696  btree_node_split_child_credit(tree, &cred);
1697  m0_be_tx_credit_add(&cred,
1698  &M0_BE_TX_CREDIT(1, sizeof(struct m0_be_btree)));
1699 
1700  kv_insert_credit(tree, ksize, vsize, &cred);
1701  m0_be_tx_credit_mac(accum, &cred, nr);
1702 }
1703 
1704 static void delete_credit(const struct m0_be_btree *tree,
1705  m0_bcount_t nr,
1706  m0_bcount_t ksize,
1707  m0_bcount_t vsize,
1708  struct m0_be_tx_credit *accum)
1709 {
1710  struct m0_be_tx_credit cred = {};
1711 
1712  kv_delete_credit(tree, ksize, vsize, &cred);
1713  btree_node_update_credit(&cred, 1);
1714  btree_node_free_credit(tree, &cred);
1715  btree_rebalance_credit(tree, &cred);
1716  m0_be_tx_credit_mac(accum, &cred, nr);
1717 }
1718 
1719 
1720 M0_INTERNAL void m0_be_btree_insert_credit(const struct m0_be_btree *tree,
1721  m0_bcount_t nr,
1722  m0_bcount_t ksize,
1723  m0_bcount_t vsize,
1724  struct m0_be_tx_credit *accum)
1725 {
1726  insert_credit(tree, nr, ksize, vsize, accum, false);
1727  M0_BE_CREDIT_INC(nr, M0_BE_CU_BTREE_INSERT, accum);
1728 }
1729 
1730 M0_INTERNAL void m0_be_btree_insert_credit2(const struct m0_be_btree *tree,
1731  m0_bcount_t nr,
1732  m0_bcount_t ksize,
1733  m0_bcount_t vsize,
1734  struct m0_be_tx_credit *accum)
1735 {
1736  insert_credit(tree, nr, ksize, vsize, accum, true);
1737  M0_BE_CREDIT_INC(nr, M0_BE_CU_BTREE_INSERT, accum);
1738 }
1739 
1740 M0_INTERNAL void m0_be_btree_delete_credit(const struct m0_be_btree *tree,
1741  m0_bcount_t nr,
1742  m0_bcount_t ksize,
1743  m0_bcount_t vsize,
1744  struct m0_be_tx_credit *accum)
1745 {
1746  delete_credit(tree, nr, ksize, vsize, accum);
1747  M0_BE_CREDIT_INC(nr, M0_BE_CU_BTREE_DELETE, accum);
1748 }
1749 
1750 M0_INTERNAL void m0_be_btree_update_credit(const struct m0_be_btree *tree,
1751  m0_bcount_t nr,
1752  m0_bcount_t vsize,
1753  struct m0_be_tx_credit *accum)
1754 {
1755  struct m0_be_tx_credit cred = {};
1756  struct m0_be_tx_credit val_update_cred =
1757  M0_BE_TX_CREDIT(1, vsize + sizeof(struct be_btree_key_val));
1758  /* capture parent checksum */
1759  m0_be_tx_credit_add(&val_update_cred,
1760  &M0_BE_TX_CREDIT(1,
1761  sizeof(struct m0_format_footer)));
1762 
1763  /* @todo: is alloc/free credits are really needed??? */
1764  btree_mem_alloc_credit(tree, vsize, &cred);
1765  btree_mem_free_credit(tree, vsize, &cred);
1766  m0_be_tx_credit_add(&cred, &val_update_cred);
1767  m0_be_tx_credit_mac(accum, &cred, nr);
1768 
1769  M0_BE_CREDIT_INC(nr, M0_BE_CU_BTREE_UPDATE, accum);
1770 }
1771 
1772 M0_INTERNAL void m0_be_btree_update_credit2(const struct m0_be_btree *tree,
1773  m0_bcount_t nr,
1774  m0_bcount_t ksize,
1775  m0_bcount_t vsize,
1776  struct m0_be_tx_credit *accum)
1777 {
1778  delete_credit(tree, nr, ksize, vsize, accum);
1779  insert_credit(tree, nr, ksize, vsize, accum, true);
1780  M0_BE_CREDIT_INC(nr, M0_BE_CU_BTREE_UPDATE, accum);
1781 }
1782 
1783 M0_INTERNAL void m0_be_btree_create_credit(const struct m0_be_btree *tree,
1784  m0_bcount_t nr,
1785  struct m0_be_tx_credit *accum)
1786 {
1787  struct m0_be_tx_credit cred = {};
1788 
1789  btree_node_alloc_credit(tree, &cred);
1790  btree_node_update_credit(&cred, 1);
1791  m0_be_tx_credit_mac(accum, &cred, nr);
1792 }
1793 
1794 static int btree_count_items(struct m0_be_btree *tree, m0_bcount_t *ksize,
1795  m0_bcount_t *vsize)
1796 {
1797  struct m0_be_btree_cursor cur;
1798  struct m0_be_op *op = &cur.bc_op;
1799  struct m0_buf start;
1800  int count = 0;
1801  struct m0_buf key;
1802  struct m0_buf val;
1803  int rc;
1804 
1805  *ksize = 0;
1806  *vsize = 0;
1807  if (tree->bb_root != NULL) {
1808  m0_be_btree_cursor_init(&cur, tree);
1809 
1810  M0_SET0(op);
1811  M0_BE_OP_SYNC_WITH(op, m0_be_btree_minkey(tree, op, &start));
1812 
1813  rc = m0_be_btree_cursor_get_sync(&cur, &start, true);
1814 
1815  while (rc != -ENOENT) {
1816  m0_be_btree_cursor_kv_get(&cur, &key, &val);
1817  if (key.b_nob > *ksize)
1818  *ksize = key.b_nob;
1819  if (val.b_nob > *vsize)
1820  *vsize = val.b_nob;
1821  rc = m0_be_btree_cursor_next_sync(&cur);
1822  ++count;
1823  }
1824 
1825  m0_be_btree_cursor_fini(&cur);
1826  }
1827 
1828  return count;
1829 }
1830 
1831 M0_INTERNAL void m0_be_btree_destroy_credit(struct m0_be_btree *tree,
1832  struct m0_be_tx_credit *accum)
1833 {
1834  /* XXX
1835  * Current implementation of m0_be_btree_destroy_credit() is
1836  * not right. First of all, `tree' parameter must be const.
1837  * Secondly, it is user's responsibility to ensure that the
1838  * tree being deleted is empty.
1839  */
1840  struct m0_be_tx_credit cred = {};
1841  int nodes_nr;
1842  int items_nr;
1843  m0_bcount_t ksize;
1844  m0_bcount_t vsize;
1845 
1846  nodes_nr = iter_prepare(tree->bb_root, false);
1847  items_nr = btree_count_items(tree, &ksize, &vsize);
1848  M0_LOG(M0_DEBUG, "nodes=%d items=%d ksz=%d vsz%d",
1849  nodes_nr, items_nr, (int)ksize, (int)vsize);
1850 
1851  kv_delete_credit(tree, ksize, vsize, &cred);
1852  m0_be_tx_credit_mac(accum, &cred, items_nr);
1853 
1854  M0_SET0(&cred);
1855  btree_node_free_credit(tree, &cred);
1856  m0_be_tx_credit_mac(accum, &cred, nodes_nr);
1857 
1858  cred = M0_BE_TX_CREDIT_TYPE(struct m0_be_btree);
1859  m0_be_tx_credit_add(accum, &cred);
1860 }
1861 
1862 M0_INTERNAL void m0_be_btree_clear_credit(struct m0_be_btree *tree,
1863  struct m0_be_tx_credit *fixed_part,
1864  struct m0_be_tx_credit *single_record,
1865  m0_bcount_t *records_nr)
1866 {
1867  struct m0_be_tx_credit cred = {};
1868  int nodes_nr;
1869  int items_nr;
1870  m0_bcount_t ksize;
1871  m0_bcount_t vsize;
1872 
1873  nodes_nr = iter_prepare(tree->bb_root, false);
1874  items_nr = btree_count_items(tree, &ksize, &vsize);
1875  items_nr++;
1876  M0_LOG(M0_DEBUG, "nodes=%d items=%d ksz=%d vsz%d",
1877  nodes_nr, items_nr, (int)ksize, (int)vsize);
1878 
1879  M0_SET0(single_record);
1880  kv_delete_credit(tree, ksize, vsize, single_record);
1881  *records_nr = items_nr;
1882 
1883  M0_SET0(&cred);
1884  btree_node_free_credit(tree, &cred);
1885  m0_be_tx_credit_mac(fixed_part, &cred, nodes_nr);
1886 
1887  cred = M0_BE_TX_CREDIT_TYPE(struct m0_be_btree);
1888  m0_be_tx_credit_add(fixed_part, &cred);
1889  m0_be_tx_credit_add(fixed_part, single_record);
1890 }
1891 
1892 static void be_btree_insert(struct m0_be_btree *tree,
1893  struct m0_be_tx *tx,
1894  struct m0_be_op *op,
1895  const struct m0_buf *key,
1896  const struct m0_buf *val,
1897  struct m0_be_btree_anchor *anchor,
1898  uint64_t zonemask)
1899 {
1900  M0_ENTRY("tree=%p", tree);
1901  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
1902  M0_PRE(key->b_nob == be_btree_ksize(tree, key->b_addr));
1903  M0_PRE((val != NULL) == (anchor == NULL));
1904  M0_PRE(ergo(anchor == NULL,
1905  val->b_nob == be_btree_vsize(tree, val->b_addr)));
1906 
1907  btree_save(tree, tx, op, key, val, anchor, BTREE_SAVE_INSERT, zonemask);
1908 
1909  M0_LEAVE("tree=%p", tree);
1910 }
1911 
1912 M0_INTERNAL void m0_be_btree_save(struct m0_be_btree *tree,
1913  struct m0_be_tx *tx,
1914  struct m0_be_op *op,
1915  const struct m0_buf *key,
1916  const struct m0_buf *val,
1917  bool overwrite)
1918 {
1919  M0_ENTRY("tree=%p", tree);
1920  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
1921  M0_PRE(key->b_nob == be_btree_ksize(tree, key->b_addr));
1922  M0_PRE(val->b_nob == be_btree_vsize(tree, val->b_addr));
1923 
1924  /* We can't be here during DIX Repair, so never use repair zone. */
1925  btree_save(tree, tx, op, key, val, NULL, overwrite ?
1926  BTREE_SAVE_OVERWRITE : BTREE_SAVE_INSERT,
1927  M0_BITS(M0_BAP_NORMAL));
1928 
1929  M0_LEAVE("tree=%p", tree);
1930 }
1931 
1932 M0_INTERNAL void m0_be_btree_insert(struct m0_be_btree *tree,
1933  struct m0_be_tx *tx,
1934  struct m0_be_op *op,
1935  const struct m0_buf *key,
1936  const struct m0_buf *val)
1937 {
1938  be_btree_insert(tree, tx, op, key, val, NULL, M0_BITS(M0_BAP_NORMAL));
1939 }
1940 
1941 M0_INTERNAL void m0_be_btree_update(struct m0_be_btree *tree,
1942  struct m0_be_tx *tx,
1943  struct m0_be_op *op,
1944  const struct m0_buf *key,
1945  const struct m0_buf *val)
1946 {
1947  M0_ENTRY("tree=%p", tree);
1948  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
1949  M0_PRE(key->b_nob == be_btree_ksize(tree, key->b_addr));
1950  M0_PRE(val->b_nob == be_btree_vsize(tree, val->b_addr));
1951 
1952  btree_save(tree, tx, op, key, val, NULL, BTREE_SAVE_UPDATE,
1953  M0_BITS(M0_BAP_NORMAL));
1954 
1955  M0_LEAVE();
1956 }
1957 
1958 M0_INTERNAL void m0_be_btree_delete(struct m0_be_btree *tree,
1959  struct m0_be_tx *tx,
1960  struct m0_be_op *op,
1961  const struct m0_buf *key)
1962 {
1963  int rc;
1964 
1965  M0_ENTRY("tree=%p", tree);
1966  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
1967 
1968  M0_BE_CREDIT_DEC(M0_BE_CU_BTREE_DELETE, tx);
1969 
1970  btree_op_fill(op, tree, tx, M0_BBO_DELETE, NULL);
1971 
1972  m0_be_op_active(op);
1973  m0_rwlock_write_lock(btree_rwlock(tree));
1974 
1975  op_tree(op)->t_rc = rc = be_btree_delete_key(tree, tx, tree->bb_root,
1976  key->b_addr);
1977  if (rc != 0)
1978  op_tree(op)->t_rc = -ENOENT;
1979 
1980  m0_rwlock_write_unlock(btree_rwlock(tree));
1981  m0_be_op_done(op);
1982  M0_LEAVE("tree=%p", tree);
1983 }
1984 
1985 static void be_btree_lookup(struct m0_be_btree *tree,
1986  struct m0_be_op *op,
1987  const struct m0_buf *key_in,
1988  struct m0_buf *key_out,
1989  struct m0_buf *value)
1990 {
1991  struct m0_be_btree_cursor it;
1992  struct btree_node_pos kp;
1993  struct be_btree_key_val *kv;
1994  m0_bcount_t ksize;
1995  m0_bcount_t vsize;
1996 
1997  M0_ENTRY("tree=%p key_in=%p key_out=%p value=%p",
1998  tree, key_in, key_out, value);
1999  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
2000 
2001  btree_op_fill(op, tree, NULL, M0_BBO_LOOKUP, NULL);
2002 
2003  m0_be_op_active(op);
2004  m0_rwlock_read_lock(btree_rwlock(tree));
2005 
2006  it.bc_tree = tree;
2007  kp = be_btree_get_btree_node(&it, key_in->b_addr,
2008  /* slant: */ key_out == NULL ? false : true);
2009  if (kp.bnp_node) {
2010  kv = &kp.bnp_node->bt_kv_arr[kp.bnp_index];
2011 
2012  vsize = be_btree_vsize(tree, kv->btree_val);
2013  if (vsize < value->b_nob)
2014  value->b_nob = vsize;
2015  /* XXX handle vsize > value->b_nob */
2016  memcpy(value->b_addr, kv->btree_val, value->b_nob);
2017 
2018  if (key_out != NULL) {
2019  ksize = be_btree_ksize(tree, kv->btree_key);
2020  if (ksize < key_out->b_nob)
2021  key_out->b_nob = ksize;
2022  memcpy(key_out->b_addr, kv->btree_key, key_out->b_nob);
2023  }
2024  op_tree(op)->t_rc = 0;
2025  } else
2026  op_tree(op)->t_rc = -ENOENT;
2027 
2028  m0_rwlock_read_unlock(btree_rwlock(tree));
2029  m0_be_op_done(op);
2030  M0_LEAVE("rc=%d", op_tree(op)->t_rc);
2031 }
2032 
2033 M0_INTERNAL void m0_be_btree_lookup(struct m0_be_btree *tree,
2034  struct m0_be_op *op,
2035  const struct m0_buf *key,
2036  struct m0_buf *value)
2037 {
2038  be_btree_lookup(tree, op, key, NULL, value);
2039 }
2040 
2041 M0_INTERNAL void m0_be_btree_lookup_slant(struct m0_be_btree *tree,
2042  struct m0_be_op *op,
2043  struct m0_buf *key,
2044  struct m0_buf *value)
2045 {
2046  be_btree_lookup(tree, op, key, key, value);
2047 }
2048 
2049 M0_INTERNAL void m0_be_btree_maxkey(struct m0_be_btree *tree,
2050  struct m0_be_op *op,
2051  struct m0_buf *out)
2052 {
2053  void *key;
2054 
2055  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
2056 
2057  btree_op_fill(op, tree, NULL, M0_BBO_MAXKEY, NULL);
2058 
2059  m0_be_op_active(op);
2060  m0_rwlock_read_lock(btree_rwlock(tree));
2061 
2062  key = be_btree_get_max_key(tree);
2063  op_tree(op)->t_rc = key == NULL ? -ENOENT : 0;
2064  m0_buf_init(out, key, key == NULL ? 0 : be_btree_ksize(tree, key));
2065 
2066  m0_rwlock_read_unlock(btree_rwlock(tree));
2067  m0_be_op_done(op);
2068 }
2069 
2070 M0_INTERNAL void m0_be_btree_minkey(struct m0_be_btree *tree,
2071  struct m0_be_op *op,
2072  struct m0_buf *out)
2073 {
2074  void *key;
2075 
2076  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
2077 
2078  btree_op_fill(op, tree, NULL, M0_BBO_MINKEY, NULL);
2079 
2080  m0_be_op_active(op);
2081  m0_rwlock_read_lock(btree_rwlock(tree));
2082 
2083  key = be_btree_get_min_key(tree);
2084  op_tree(op)->t_rc = key == NULL ? -ENOENT : 0;
2085  m0_buf_init(out, key, key == NULL ? 0 : be_btree_ksize(tree, key));
2086 
2087  m0_rwlock_read_unlock(btree_rwlock(tree));
2088  m0_be_op_done(op);
2089 }
2090 
2091 /* ------------------------------------------------------------------
2092  * Btree external inplace interfaces implementation
2093  * ------------------------------------------------------------------ */
2094 
2095 M0_INTERNAL void m0_be_btree_update_inplace(struct m0_be_btree *tree,
2096  struct m0_be_tx *tx,
2097  struct m0_be_op *op,
2098  const struct m0_buf *key,
2099  struct m0_be_btree_anchor *anchor)
2100 {
2101  struct be_btree_key_val *kv;
2102 
2103  M0_ENTRY("tree=%p", tree);
2104  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
2105  M0_PRE(key->b_nob == be_btree_ksize(tree, key->b_addr));
2106 
2107  btree_op_fill(op, tree, tx, M0_BBO_UPDATE, NULL);
2108 
2109  m0_be_op_active(op);
2110  m0_rwlock_write_lock(btree_rwlock(tree));
2111 
2112  anchor->ba_write = true;
2113  anchor->ba_tree = tree;
2114  kv = be_btree_search(tree, key->b_addr);
2115  if (kv != NULL) {
2116  M0_ASSERT(anchor->ba_value.b_nob <=
2117  be_btree_vsize(tree, kv->btree_val));
2118  anchor->ba_value.b_addr = kv->btree_val;
2119  } else
2120  op_tree(op)->t_rc = -ENOENT;
2121 
2122  m0_be_op_done(op);
2123  M0_LEAVE();
2124 }
2125 
2126 M0_INTERNAL void m0_be_btree_insert_inplace(struct m0_be_btree *tree,
2127  struct m0_be_tx *tx,
2128  struct m0_be_op *op,
2129  const struct m0_buf *key,
2130  struct m0_be_btree_anchor *anchor,
2131  uint64_t zonemask)
2132 {
2133  be_btree_insert(tree, tx, op, key, NULL, anchor, zonemask);
2134 }
2135 
2136 M0_INTERNAL void m0_be_btree_save_inplace(struct m0_be_btree *tree,
2137  struct m0_be_tx *tx,
2138  struct m0_be_op *op,
2139  const struct m0_buf *key,
2140  struct m0_be_btree_anchor *anchor,
2141  bool overwrite,
2142  uint64_t zonemask)
2143 {
2144  M0_ENTRY("tree=%p zonemask=%"PRIx64, tree, zonemask);
2145  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
2146  M0_PRE(key->b_nob == be_btree_ksize(tree, key->b_addr));
2147 
2148  btree_save(tree, tx, op, key, NULL, anchor, overwrite ?
2149  BTREE_SAVE_OVERWRITE : BTREE_SAVE_INSERT, zonemask);
2150 }
2151 
2152 M0_INTERNAL void m0_be_btree_lookup_inplace(struct m0_be_btree *tree,
2153  struct m0_be_op *op,
2154  const struct m0_buf *key,
2155  struct m0_be_btree_anchor *anchor)
2156 {
2157  struct be_btree_key_val *kv;
2158 
2159  M0_ENTRY("tree=%p", tree);
2160  M0_PRE(tree->bb_root != NULL && tree->bb_ops != NULL);
2161 
2162  btree_op_fill(op, tree, NULL, M0_BBO_INSERT, anchor);
2163 
2164  m0_be_op_active(op);
2165  m0_rwlock_read_lock(btree_rwlock(tree));
2166 
2167  anchor->ba_tree = tree;
2168  anchor->ba_write = false;
2169  kv = be_btree_search(tree, key->b_addr);
2170  if (kv == NULL)
2171  op_tree(op)->t_rc = -ENOENT;
2172  else
2173  m0_buf_init(&anchor->ba_value, kv->btree_val,
2174  be_btree_vsize(tree, kv->btree_val));
2175 
2176  m0_be_op_done(op);
2177  M0_LEAVE();
2178 }
2179 
2180 M0_INTERNAL void m0_be_btree_release(struct m0_be_tx *tx,
2181  struct m0_be_btree_anchor *anchor)
2182 {
2183  struct m0_be_btree *tree = anchor->ba_tree;
2184 
2185  M0_ENTRY("tree=%p", tree);
2186  M0_PRE(ergo(anchor->ba_write, tx != NULL));
2187 
2188  if (tree != NULL) {
2189  if (anchor->ba_write) {
2190  if (anchor->ba_value.b_addr != NULL) {
2191  mem_update(tree, tx, anchor->ba_value.b_addr,
2192  anchor->ba_value.b_nob);
2193  anchor->ba_value.b_addr = NULL;
2194  }
2195  m0_rwlock_write_unlock(btree_rwlock(tree));
2196  } else
2197  m0_rwlock_read_unlock(btree_rwlock(tree));
2198  anchor->ba_tree = NULL;
2199  }
2200  M0_LEAVE();
2201 }
2202 
2203 /* ------------------------------------------------------------------
2204  * Btree cursor interfaces implementation
2205  * ------------------------------------------------------------------ */
2206 
2207 static void print_single_node(struct m0_be_bnode *node)
2208 {
2209  int i;
2210 
2211  M0_LOG(M0_DEBUG, "{");
2212  for (i = 0; i < node->bt_num_active_key; ++i) {
2213  void *key = node->bt_kv_arr[i].btree_key;
2214  void *val = node->bt_kv_arr[i].btree_val;
2215 
2216  if (node->bt_isleaf)
2217  M0_LOG(M0_DEBUG, "%02d: key=%s val=%s", i,
2218  (char *)key, (char *)val);
2219  else
2220  M0_LOG(M0_DEBUG, "%02d: key=%s val=%s child=%p", i,
2221  (char *)key, (char *)val, node->bt_child_arr[i]);
2222  }
2223  if (!node->bt_isleaf)
2224  M0_LOG(M0_DEBUG, "%02d: child=%p", i, node->bt_child_arr[i]);
2225  M0_LOG(M0_DEBUG, "} (%p, %d)", node, node->bt_level);
2226 }
2227 
2228 static int iter_prepare(struct m0_be_bnode *node, bool print)
2229 {
2230 
2231  int i = 0;
2232  int count = 0;
2233  unsigned int current_level;
2234 
2235  struct m0_be_bnode *head;
2236  struct m0_be_bnode *tail;
2237  struct m0_be_bnode *child = NULL;
2238 
2239  if (print)
2240  M0_LOG(M0_DEBUG, "---8<---8<---8<---8<---8<---8<---");
2241 
2242  if (node == NULL)
2243  goto out;
2244 
2245  count = 1;
2246  current_level = node->bt_level;
2247  head = node;
2248  tail = node;
2249 
2250  head->bt_next = NULL;
2251  m0_format_footer_update(head);
2252  while (head != NULL) {
2253  if (head->bt_level < current_level) {
2254  current_level = head->bt_level;
2255  if (print)
2256  M0_LOG(M0_DEBUG, "***");
2257  }
2258  if (print)
2259  print_single_node(head);
2260 
2261  if (!head->bt_isleaf) {
2262  for (i = 0; i < head->bt_num_active_key + 1; i++) {
2263  child = head->bt_child_arr[i];
2264  tail->bt_next = child;
2265  m0_format_footer_update(tail);
2266  tail = child;
2267  child->bt_next = NULL;
2268  m0_format_footer_update(child);
2269  }
2270  }
2271  head = head->bt_next;
2272  count++;
2273  }
2274 out:
2275  if (print)
2276  M0_LOG(M0_DEBUG, "---8<---8<---8<---8<---8<---8<---");
2277 
2278  return count;
2279 }
2280 
2281 M0_INTERNAL void m0_be_btree_cursor_init(struct m0_be_btree_cursor *cur,
2282  struct m0_be_btree *btree)
2283 {
2284  cur->bc_tree = btree;
2285  cur->bc_node = NULL;
2286  cur->bc_pos = 0;
2287  cur->bc_stack_pos = 0;
2288 }
2289 
2290 M0_INTERNAL void m0_be_btree_cursor_fini(struct m0_be_btree_cursor *cursor)
2291 {
2292  cursor->bc_tree = NULL;
2293 }
2294 
2295 M0_INTERNAL void m0_be_btree_cursor_get(struct m0_be_btree_cursor *cur,
2296  const struct m0_buf *key, bool slant)
2297 {
2298  struct btree_node_pos last;
2299  struct be_btree_key_val *kv;
2300  struct m0_be_op *op = &cur->bc_op;
2301  struct m0_be_btree *tree = cur->bc_tree;
2302 
2303  btree_op_fill(op, tree, NULL, M0_BBO_CURSOR_GET, NULL);
2304 
2305  m0_be_op_active(op);
2306  m0_rwlock_read_lock(btree_rwlock(tree));
2307 
2308  last = be_btree_get_btree_node(cur, key->b_addr, slant);
2309 
2310  if (last.bnp_node == NULL) {
2311  M0_SET0(&op_tree(op)->t_out_val);
2312  M0_SET0(&op_tree(op)->t_out_key);
2313  op_tree(op)->t_rc = -ENOENT;
2314  } else {
2315  cur->bc_pos = last.bnp_index;
2316  cur->bc_node = last.bnp_node;
2317 
2318  kv = &cur->bc_node->bt_kv_arr[cur->bc_pos];
2319 
2320  m0_buf_init(&op_tree(op)->t_out_val, kv->btree_val,
2321  be_btree_vsize(tree, kv->btree_val));
2322  m0_buf_init(&op_tree(op)->t_out_key, kv->btree_key,
2323  be_btree_ksize(tree, kv->btree_key));
2324  op_tree(op)->t_rc = 0;
2325  }
2326 
2327  m0_rwlock_read_unlock(btree_rwlock(tree));
2328  m0_be_op_done(op);
2329 }
2330 
2331 M0_INTERNAL int m0_be_btree_cursor_get_sync(struct m0_be_btree_cursor *cur,
2332  const struct m0_buf *key,
2333  bool slant)
2334 {
2335  M0_SET0(&cur->bc_op);
2336  return M0_RC(M0_BE_OP_SYNC_RET_WITH(&cur->bc_op,
2337  m0_be_btree_cursor_get(cur, key, slant),
2338  bo_u.u_btree.t_rc));
2339 }
2340 
2341 static int btree_cursor_seek(struct m0_be_btree_cursor *cur, void *key)
2342 {
2343  const struct m0_buf kbuf =
2344  M0_BUF_INIT(be_btree_ksize(cur->bc_tree, key), key);
2345  return m0_be_btree_cursor_get_sync(cur, &kbuf, true);
2346 }
2347 
2348 M0_INTERNAL int m0_be_btree_cursor_first_sync(struct m0_be_btree_cursor *cur)
2349 {
2350  return btree_cursor_seek(cur, be_btree_get_min_key(cur->bc_tree));
2351 }
2352 
2353 M0_INTERNAL int m0_be_btree_cursor_last_sync(struct m0_be_btree_cursor *cur)
2354 {
2355  return btree_cursor_seek(cur, be_btree_get_max_key(cur->bc_tree));
2356 }
2357 
2358 M0_INTERNAL void m0_be_btree_cursor_next(struct m0_be_btree_cursor *cur)
2359 {
2360  struct be_btree_key_val *kv;
2361  struct m0_be_op *op = &cur->bc_op;
2362  struct m0_be_btree *tree = cur->bc_tree;
2363  struct m0_be_bnode *node;
2364 
2365  btree_op_fill(op, tree, NULL, M0_BBO_CURSOR_NEXT, NULL);
2366 
2367  m0_be_op_active(op);
2368  m0_rwlock_read_lock(btree_rwlock(tree));
2369 
2370  node = cur->bc_node;
2371  if (node == NULL) {
2372  op_tree(op)->t_rc = -EINVAL;
2373  goto out;
2374  }
2375 
2376  /* cursor move */
2377  ++cur->bc_pos;
2378  if (node->bt_isleaf) {
2379  while (node && cur->bc_pos >= node->bt_num_active_key)
2380  node = node_pop(cur, &cur->bc_pos);
2381  } else {
2382  for (;;) {
2383  node_push(cur, node, cur->bc_pos);
2384  node = node->bt_child_arr[cur->bc_pos];
2385  cur->bc_pos = 0;
2386  if (node->bt_isleaf)
2387  break;
2388  }
2389  }
2390 
2391  if (node == NULL) {
2392  M0_SET0(&op_tree(op)->t_out_val);
2393  M0_SET0(&op_tree(op)->t_out_key);
2394  op_tree(op)->t_rc = -ENOENT;
2395  goto out;
2396  }
2397  /* cursor end move */
2398 
2399  cur->bc_node = node;
2400 
2401  kv = &node->bt_kv_arr[cur->bc_pos];
2402  m0_buf_init(&op_tree(op)->t_out_val, kv->btree_val,
2403  be_btree_vsize(tree, kv->btree_val));
2404  m0_buf_init(&op_tree(op)->t_out_key, kv->btree_key,
2405  be_btree_ksize(tree, kv->btree_key));
2406 out:
2407  m0_rwlock_read_unlock(btree_rwlock(tree));
2408  m0_be_op_done(op);
2409 }
2410 
2411 M0_INTERNAL void m0_be_btree_cursor_prev(struct m0_be_btree_cursor *cur)
2412 {
2413  struct be_btree_key_val *kv;
2414  struct m0_be_op *op = &cur->bc_op;
2415  struct m0_be_btree *tree = cur->bc_tree;
2416  struct m0_be_bnode *node;
2417 
2418  btree_op_fill(op, tree, NULL, M0_BBO_CURSOR_PREV, NULL);
2419 
2420  m0_be_op_active(op);
2421  m0_rwlock_read_lock(btree_rwlock(tree));
2422 
2423  node = cur->bc_node;
2424 
2425  /* cursor move */
2426  if (node->bt_isleaf) {
2427  --cur->bc_pos;
2428  while (node && cur->bc_pos < 0) {
2429  node = node_pop(cur, &cur->bc_pos);
2430  --cur->bc_pos;
2431  }
2432  } else {
2433  for (;;) {
2434  node_push(cur, node, cur->bc_pos);
2435  node = node->bt_child_arr[cur->bc_pos];
2436  if (node->bt_isleaf) {
2437  cur->bc_pos = node->bt_num_active_key - 1;
2438  break;
2439  } else
2440  cur->bc_pos = node->bt_num_active_key;
2441  }
2442  }
2443 
2444  if (node == NULL) {
2445  M0_SET0(&op_tree(op)->t_out_val);
2446  M0_SET0(&op_tree(op)->t_out_key);
2447  op_tree(op)->t_rc = -ENOENT;
2448  goto out;
2449  }
2450  /* cursor end move */
2451 
2452  cur->bc_node = node;
2453 
2454  kv = &cur->bc_node->bt_kv_arr[cur->bc_pos];
2455  m0_buf_init(&op_tree(op)->t_out_val, kv->btree_val,
2456  be_btree_vsize(tree, kv->btree_val));
2457  m0_buf_init(&op_tree(op)->t_out_key, kv->btree_key,
2458  be_btree_ksize(tree, kv->btree_key));
2459 out:
2460  m0_rwlock_read_unlock(btree_rwlock(tree));
2461  m0_be_op_done(op);
2462 }
2463 
2464 M0_INTERNAL int m0_be_btree_cursor_next_sync(struct m0_be_btree_cursor *cur)
2465 {
2466  M0_SET0(&cur->bc_op);
2467  return M0_BE_OP_SYNC_RET_WITH(&cur->bc_op,
2468  m0_be_btree_cursor_next(cur),
2469  bo_u.u_btree.t_rc);
2470 }
2471 
2472 M0_INTERNAL int m0_be_btree_cursor_prev_sync(struct m0_be_btree_cursor *cur)
2473 {
2474  M0_SET0(&cur->bc_op);
2475  return M0_BE_OP_SYNC_RET_WITH(&cur->bc_op,
2476  m0_be_btree_cursor_prev(cur),
2477  bo_u.u_btree.t_rc);
2478 }
2479 
2480 M0_INTERNAL void m0_be_btree_cursor_put(struct m0_be_btree_cursor *cursor)
2481 {
2482  cursor->bc_node = NULL;
2483 }
2484 
2485 M0_INTERNAL void m0_be_btree_cursor_kv_get(struct m0_be_btree_cursor *cur,
2486  struct m0_buf *key,
2487  struct m0_buf *val)
2488 {
2489  struct m0_be_op *op = &cur->bc_op;
2490  M0_PRE(m0_be_op_is_done(op));
2491  M0_PRE(key != NULL || val != NULL);
2492 
2493  if (key != NULL)
2494  *key = op_tree(op)->t_out_key;
2495  if (val != NULL)
2496  *val = op_tree(op)->t_out_val;
2497 }
2498 
2499 M0_INTERNAL bool m0_be_btree_is_empty(struct m0_be_btree *tree)
2500 {
2501  M0_PRE(tree->bb_root != NULL);
2502  return tree->bb_root->bt_num_active_key == 0;
2503 }
2504 
2505 M0_INTERNAL void btree_dbg_print(struct m0_be_btree *tree)
2506 {
2507  iter_prepare(tree->bb_root, true);
2508 }
2509 
2510 static struct m0_be_op__btree *op_tree(struct m0_be_op *op)
2511 {
2512  M0_PRE(op->bo_utype == M0_BOP_TREE);
2513  return &op->bo_u.u_btree;
2514 }
2515 
2516 static struct m0_rwlock *btree_rwlock(struct m0_be_btree *tree)
2517 {
2518  return &tree->bb_lock.bl_u.rwlock;
2519 }
2520 
2522 #undef M0_TRACE_SUBSYSTEM
2523 
2524 /*
2525  * Local variables:
2526  * c-indentation-style: "K&R"
2527  * c-basic-offset: 8
2528  * tab-width: 8
2529  * fill-column: 80
2530  * scroll-step: 1
2531  * End:
2532  */
2533 /*
2534  * vim: tabstop=8 shiftwidth=8 noexpandtab textwidth=80 nowrap
2535  */
insert_credit
static void insert_credit(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum, bool use_current_height)
Definition: btree.c:1674
btree_node_update
static void btree_node_update(struct m0_be_bnode *node, const struct m0_be_btree *btree, struct m0_be_tx *tx)
Definition: btree.c:344
btree_backlink_invariant
static bool btree_backlink_invariant(const struct m0_be_btree_backlink *h, const struct m0_be_seg *seg, const uint64_t *parent)
Definition: btree.c:240
m0_be_btree_insert_inplace
M0_INTERNAL void m0_be_btree_insert_inplace(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor, uint64_t zonemask)
Definition: btree.c:2126
ptr
static void ptr(struct m0_addb2__context *ctx, const uint64_t *v, char *buf)
Definition: dump.c:440
m0_be_btree_cursor_next
M0_INTERNAL void m0_be_btree_cursor_next(struct m0_be_btree_cursor *cur)
Definition: btree.c:2358
p
static struct m0_addb2_philter p
Definition: consumer.c:40
nr
static size_t nr
Definition: dump.c:1505
M0_PRE
#define M0_PRE(cond)
key_gt
static int key_gt(const struct m0_be_btree *btree, const void *key0, const void *key1)
Definition: btree.c:175
m0_be_seg::bs_gen
uint64_t bs_gen
Definition: seg.h:76
m0_be_btree_delete_credit
M0_INTERNAL void m0_be_btree_delete_credit(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1740
key_eq
static int key_eq(const struct m0_be_btree *btree, const void *key0, const void *key1)
Definition: btree.c:181
btree_node_invariant
static bool btree_node_invariant(const struct m0_be_btree *btree, const struct m0_be_bnode *node, bool root)
Definition: btree.c:262
m0_be_btree_cursor_stack_entry
Definition: btree.h:566
be_btree_lookup
static void be_btree_lookup(struct m0_be_btree *tree, struct m0_be_op *op, const struct m0_buf *key_in, struct m0_buf *key_out, struct m0_buf *value)
Definition: btree.c:1985
btree_truncate
static void btree_truncate(struct m0_be_btree *btree, struct m0_be_tx *tx, m0_bcount_t limit)
Definition: btree.c:1202
m0_be_bnode::bt_kv_arr
struct be_btree_key_val bt_kv_arr[KV_NR]
Definition: btree_internal.h:57
m0_format_header_pack
M0_INTERNAL void m0_format_header_pack(struct m0_format_header *dest, const struct m0_format_tag *src)
Definition: format.c:40
m0_be_btree_backlink::bli_type
uint64_t bli_type
Definition: btree.h:54
be_btree_get_min_key
static void * be_btree_get_min_key(struct m0_be_btree *tree)
Definition: btree.c:1338
NULL
#define NULL
Definition: misc.h:38
be_btree_split_child
static void be_btree_split_child(struct m0_be_btree *btree, struct m0_be_tx *tx, struct m0_be_bnode *parent, unsigned int index)
Definition: btree.c:462
m0_be_btree_op
m0_be_btree_op
Definition: btree.h:139
cur
static struct buffer * cur(struct m0_addb2_mach *mach, m0_bcount_t space)
Definition: addb2.c:791
val
Definition: idx_mock.c:52
ergo
#define ergo(a, b)
Definition: misc.h:293
M0_NOTICE
Definition: trace.h:480
m0_btree_fid_type
M0_INTERNAL const struct m0_fid_type m0_btree_fid_type
Definition: btree.c:57
m0_be_btree_clear_credit
M0_INTERNAL void m0_be_btree_clear_credit(struct m0_be_btree *tree, struct m0_be_tx_credit *fixed_part, struct m0_be_tx_credit *single_record, m0_bcount_t *records_nr)
Definition: btree.c:1862
m0_be_rwlock::bl_u
union m0_be_rwlock::@198 bl_u
m0_be_btree::bb_root
struct m0_be_bnode * bb_root
Definition: btree.h:68
m0_buf::b_addr
void * b_addr
Definition: buf.h:39
m0_be_btree_lookup
M0_INTERNAL void m0_be_btree_lookup(struct m0_be_btree *tree, struct m0_be_op *op, const struct m0_buf *key, struct m0_buf *value)
Definition: btree.c:2033
m0_be_btree_anchor::ba_tree
struct m0_be_btree * ba_tree
Definition: btree.h:464
M0_BE_CU_BTREE_DELETE
Definition: tx_credit.h:72
be_btree_insert_into_nonfull
static void be_btree_insert_into_nonfull(struct m0_be_btree *btree, struct m0_be_tx *tx, struct m0_be_bnode *node, struct be_btree_key_val *kv)
Definition: btree.c:529
m0_be_btree_save_inplace
M0_INTERNAL void m0_be_btree_save_inplace(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor, bool overwrite, uint64_t zonemask)
Definition: btree.c:2136
M0_LOG
#define M0_LOG(level,...)
Definition: trace.h:167
M0_LEAVE
M0_LEAVE()
m0_be_btree_cursor_stack_entry::bs_node
struct m0_be_bnode * bs_node
Definition: btree.h:568
btree_save
static void btree_save(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val, struct m0_be_btree_anchor *anchor, enum btree_save_optype optype, uint64_t zonemask)
Definition: btree.c:1365
level
enum m0_trace_level level
Definition: trace.c:111
m0_fid_type::ft_id
uint8_t ft_id
Definition: fid.h:101
tree_allocator
static struct m0_be_allocator * tree_allocator(const struct m0_be_btree *btree)
Definition: btree.c:97
m0_be_btree::bb_seg
struct m0_be_seg * bb_seg
Definition: btree.h:76
node
static struct net_test_cmd_node * node
Definition: commands.c:72
M0_BE_CU_BTREE_UPDATE
Definition: tx_credit.h:73
m0_be_allocator
Allocator.
Definition: alloc.h:132
M0_BE_OP_SYNC
#define M0_BE_OP_SYNC(op_obj, action)
Definition: op.h:190
m0_buf_init
M0_INTERNAL void m0_buf_init(struct m0_buf *buf, void *data, uint32_t nob)
Definition: buf.c:37
m0_rwlock_write_lock
M0_INTERNAL void m0_rwlock_write_lock(struct m0_rwlock *lock)
Definition: rwlock.c:42
be_btree_vsize
static m0_bcount_t be_btree_vsize(const struct m0_be_btree *btree, const void *data)
Definition: btree.c:154
data
struct m0_bufvec data
Definition: di.c:40
btree_pair_release
static void btree_pair_release(struct m0_be_btree *btree, struct m0_be_tx *tx, struct be_btree_key_val *kv)
Definition: btree.c:1349
value
int const char const void * value
Definition: dir.c:325
btree_rebalance_credit
static void btree_rebalance_credit(const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
Definition: btree.c:1627
m0_be_rwlock::rwlock
struct m0_rwlock rwlock
Definition: format.h:208
m0_fid_tget
M0_INTERNAL uint8_t m0_fid_tget(const struct m0_fid *fid)
Definition: fid.c:133
it
static struct m0_be_emap_cursor it
Definition: extmap.c:46
M0_BBO_CURSOR_PREV
Definition: btree.h:150
M0_BE_TX_CAPTURE_PTR
#define M0_BE_TX_CAPTURE_PTR(seg, tx, ptr)
Definition: tx.h:505
be_btree_move_parent_key
static void be_btree_move_parent_key(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_bnode *node, enum position_t pos, unsigned int index)
Definition: btree.c:795
M0_BBO_MINKEY
Definition: btree.h:147
m0_be_btree_maxkey
M0_INTERNAL void m0_be_btree_maxkey(struct m0_be_btree *tree, struct m0_be_op *op, struct m0_buf *out)
Definition: btree.c:2049
m0_be_btree_is_empty
M0_INTERNAL bool m0_be_btree_is_empty(struct m0_be_btree *tree)
Definition: btree.c:2499
position_t
position_t
Definition: btree.c:191
M0_BITS
#define M0_BITS(...)
Definition: misc.h:236
m0_bcount_t
uint64_t m0_bcount_t
Definition: types.h:77
left
static int left
Definition: locality.c:280
btree_node_child_delete
static void btree_node_child_delete(struct m0_be_btree *btree, struct m0_be_tx *tx, struct m0_be_bnode *node, unsigned index, struct btree_node_pos *child, bool left)
Definition: btree.c:881
btree_node_pos::bnp_node
struct m0_be_bnode * bnp_node
Definition: btree.c:53
BTREE_SAVE_OVERWRITE
Definition: btree.c:49
m0_be_btree_create
M0_INTERNAL void m0_be_btree_create(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_fid *btree_fid)
Definition: btree.c:1512
M0_SET0
#define M0_SET0(obj)
Definition: misc.h:64
M0_BE_TX_CREDIT_TYPE
#define M0_BE_TX_CREDIT_TYPE(type)
Definition: tx_credit.h:97
M0_BAP_NORMAL
Definition: alloc.h:95
m0_be_alloc_aligned
M0_INTERNAL void m0_be_alloc_aligned(struct m0_be_allocator *a, struct m0_be_tx *tx, struct m0_be_op *op, void **ptr, m0_bcount_t size, unsigned shift, uint64_t zonemask)
Definition: alloc.c:1020
m0_be_btree_destroy_credit
M0_INTERNAL void m0_be_btree_destroy_credit(struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
Definition: btree.c:1831
M0_BAO_FREE_ALIGNED
Definition: alloc.h:202
M0_BE_CREDIT_DEC
#define M0_BE_CREDIT_DEC(cr_user, tx)
Definition: tx.h:465
M0_SWAP
#define M0_SWAP(v0, v1)
Definition: arith.h:207
BTREE_FAN_OUT
Definition: btree.h:573
m0_rwlock
Definition: rwlock.h:40
M0_BE_REG
#define M0_BE_REG(seg, size, addr)
Definition: seg.h:148
PRIx64
#define PRIx64
Definition: types.h:61
m0_be_btree_cursor_put
M0_INTERNAL void m0_be_btree_cursor_put(struct m0_be_btree_cursor *cursor)
Definition: btree.c:2480
count
static m0_bcount_t count
Definition: xcode.c:167
be_btree_search
static struct be_btree_key_val * be_btree_search(struct m0_be_btree *btree, void *key)
Definition: btree.c:1295
op_tree
static struct m0_be_op__btree * op_tree(struct m0_be_op *op)
Definition: btree.c:2510
m0_format_footer
Definition: format.h:57
be_btree_shift_key_vals
static void be_btree_shift_key_vals(struct m0_be_bnode *dest, struct m0_be_bnode *src, unsigned int start_index, unsigned int key_src_offset, unsigned int key_dest_offset, unsigned int child_src_offset, unsigned int child_dest_offset, unsigned int stop_index)
Definition: btree.c:648
iter_prepare
static int iter_prepare(struct m0_be_bnode *node, bool print)
Definition: btree.c:2228
m0_be_btree_delete
M0_INTERNAL void m0_be_btree_delete(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key)
Definition: btree.c:1958
m0_be_btree_cursor_fini
M0_INTERNAL void m0_be_btree_cursor_fini(struct m0_be_btree_cursor *cursor)
Definition: btree.c:2290
m0_rwlock_init
M0_INTERNAL void m0_rwlock_init(struct m0_rwlock *lock)
Definition: rwlock.c:32
m0_be_btree
Definition: btree.h:60
be_btree_destroy
static void be_btree_destroy(struct m0_be_btree *btree, struct m0_be_tx *tx)
Definition: btree.c:1150
M0_RC
return M0_RC(rc)
key_lt
static int key_lt(const struct m0_be_btree *btree, const void *key0, const void *key1)
Definition: btree.c:169
op
op
Definition: libdemo.c:64
m0_be_btree_cursor_next_sync
M0_INTERNAL int m0_be_btree_cursor_next_sync(struct m0_be_btree_cursor *cur)
Definition: btree.c:2464
head
static int head(struct m0_sm *mach)
Definition: sm.c:468
btree
static int btree(struct scanner *s, struct rectype *r, char *buf)
Definition: beck.c:1270
M0_BE_TX_CREDIT
#define M0_BE_TX_CREDIT(nr, size)
Definition: tx_credit.h:94
M0_ENTRY
#define M0_ENTRY(...)
Definition: trace.h:170
m0_buf
Definition: buf.h:37
M0_BBO_MAXKEY
Definition: btree.h:146
btree_cursor_seek
static int btree_cursor_seek(struct m0_be_btree_cursor *cur, void *key)
Definition: btree.c:2341
i
int i
Definition: dir.c:1033
m0_be_btree_cursor::bc_node
struct m0_be_bnode * bc_node
Definition: btree.h:587
print
static M0_UNUSED void print(struct m0_be_list *list)
Definition: list.c:186
btree_credit
static void btree_credit(const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
Definition: btree.c:1618
root
struct m0_conf_root * root
Definition: note.c:50
print_single_node
static void print_single_node(struct m0_be_bnode *node)
Definition: btree.c:2207
btree_node_free
static void btree_node_free(struct m0_be_bnode *node, const struct m0_be_btree *btree, struct m0_be_tx *tx)
Definition: btree.c:443
m0_be_btree_update_credit
M0_INTERNAL void m0_be_btree_update_credit(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1750
m0_be_btree_insert_credit2
M0_INTERNAL void m0_be_btree_insert_credit2(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1730
bt_kv_arr
struct be_btree_key_val bt_kv_arr[KV_NR]
Definition: btree_internal.h:595
key
static int key
Definition: locality.c:283
m0_be_btree_create_credit
M0_INTERNAL void m0_be_btree_create_credit(const struct m0_be_btree *tree, m0_bcount_t nr, struct m0_be_tx_credit *accum)
Definition: btree.c:1783
m0_be_btree_insert
M0_INTERNAL void m0_be_btree_insert(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val)
Definition: btree.c:1932
m0_be_bnode::bt_child_arr
struct m0_be_bnode * bt_child_arr[KV_NR+1]
Definition: btree_internal.h:58
m0_be_btree_save
M0_INTERNAL void m0_be_btree_save(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val, bool overwrite)
Definition: btree.c:1912
be_btree_delete_key_from_node
static void be_btree_delete_key_from_node(struct m0_be_btree *tree, struct m0_be_tx *tx, struct btree_node_pos *node_pos)
Definition: btree.c:839
m0_be_btree_lookup_inplace
M0_INTERNAL void m0_be_btree_lookup_inplace(struct m0_be_btree *tree, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor)
Definition: btree.c:2152
btree_create
static void btree_create(struct m0_be_btree *btree, struct m0_be_tx *tx, const struct m0_fid *btree_fid)
Definition: btree.c:375
m0_be_btree_insert_credit
M0_INTERNAL void m0_be_btree_insert_credit(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1720
BTREE_SAVE_INSERT
Definition: btree.c:47
btree_root_set
static void btree_root_set(struct m0_be_btree *btree, struct m0_be_bnode *new_root)
Definition: btree.c:68
m0_be_tx_credit_mac
M0_INTERNAL void m0_be_tx_credit_mac(struct m0_be_tx_credit *c, const struct m0_be_tx_credit *c1, m0_bcount_t k)
Definition: tx_credit.c:88
m0_format_tag
Definition: format.h:62
m0_be_btree_update_inplace
M0_INTERNAL void m0_be_btree_update_inplace(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor)
Definition: btree.c:2095
m0_buf::b_nob
m0_bcount_t b_nob
Definition: buf.h:38
M0_ASSERT
#define M0_ASSERT(cond)
m0_be_btree_destroy
M0_INTERNAL void m0_be_btree_destroy(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op)
Definition: btree.c:1538
bli_type
uint64_t bli_type
Definition: btree.h:56
m0_be_btree_backlink::bli_tree
struct m0_cookie bli_tree
Definition: btree.h:53
btree_dbg_print
M0_INTERNAL void btree_dbg_print(struct m0_be_btree *tree)
Definition: btree.c:2505
m0_be_btree_release
M0_INTERNAL void m0_be_btree_release(struct m0_be_tx *tx, struct m0_be_btree_anchor *anchor)
Definition: btree.c:2180
m0_be_tx_credit_mul
M0_INTERNAL void m0_be_tx_credit_mul(struct m0_be_tx_credit *c, m0_bcount_t k)
Definition: tx_credit.c:73
bt_child_arr
struct m0_be_bnode * bt_child_arr[KV_NR+1]
Definition: btree_internal.h:596
btree_save_optype
btree_save_optype
Definition: btree.c:46
m0_be_seg_allocator
M0_INTERNAL struct m0_be_allocator * m0_be_seg_allocator(struct m0_be_seg *seg)
Definition: stubs.c:113
node_pop
static struct m0_be_bnode * node_pop(struct m0_be_btree_cursor *it, int *idx)
Definition: btree.c:1077
m0_be_tx_credit_add
M0_INTERNAL void m0_be_tx_credit_add(struct m0_be_tx_credit *c0, const struct m0_be_tx_credit *c1)
Definition: tx_credit.c:44
be_btree_delete_key
static int be_btree_delete_key(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_bnode *bnode, void *key)
Definition: btree.c:911
m0_be_bnode
Definition: btree_internal.h:49
key0
static int key0
Definition: locality.c:282
be_btree_key_val
Definition: btree_internal.h:43
m0_be_btree_backlink::bli_gen
uint64_t bli_gen
Definition: btree.h:55
m0_be_btree_cursor_prev_sync
M0_INTERNAL int m0_be_btree_cursor_prev_sync(struct m0_be_btree_cursor *cur)
Definition: btree.c:2472
btree_invariant
static bool btree_invariant(const struct m0_be_btree *btree)
Definition: btree.c:337
M0_BBO_CURSOR_NEXT
Definition: btree.h:149
M0_BBO_CREATE
Definition: btree.h:140
kv_delete_credit
static void kv_delete_credit(const struct m0_be_btree *tree, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1652
m0_be_btree_fini
M0_INTERNAL void m0_be_btree_fini(struct m0_be_btree *tree)
Definition: btree.c:1503
M0_POST
#define M0_POST(cond)
m0_be_btree_minkey
M0_INTERNAL void m0_be_btree_minkey(struct m0_be_btree *tree, struct m0_be_op *op, struct m0_buf *out)
Definition: btree.c:2070
M0_BBO_LOOKUP
Definition: btree.h:145
m0_be_tx_credit
Definition: tx_credit.h:79
btree_rwlock
static struct m0_rwlock * btree_rwlock(struct m0_be_btree *tree)
Definition: btree.c:2516
m0_be_bnode::bt_level
unsigned int bt_level
Definition: btree_internal.h:54
m0_cookie_init
M0_INTERNAL void m0_cookie_init(struct m0_cookie *cookie, const uint64_t *obj)
Definition: cookie.c:90
delete_credit
static void delete_credit(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1704
M0_BBO_CURSOR_GET
Definition: btree.h:148
m0_be_op_done
M0_INTERNAL void m0_be_op_done(struct m0_be_op *op)
Definition: stubs.c:104
m0_format_header::hd_magic
uint64_t hd_magic
Definition: format.h:43
m0_be_btree_update_credit2
M0_INTERNAL void m0_be_btree_update_credit2(const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1772
M0_BAO_ALLOC_ALIGNED
Definition: alloc.h:200
m0_rwlock_write_unlock
M0_INTERNAL void m0_rwlock_write_unlock(struct m0_rwlock *lock)
Definition: rwlock.c:47
KV_NR
Definition: btree_internal.h:40
m0_be_btree_cursor_first_sync
M0_INTERNAL int m0_be_btree_cursor_first_sync(struct m0_be_btree_cursor *cur)
Definition: btree.c:2348
be_btree_get_max_key
static void * be_btree_get_max_key(struct m0_be_btree *tree)
Definition: btree.c:1319
mem_free
static void mem_free(const struct m0_be_btree *btree, struct m0_be_tx *tx, void *ptr)
Definition: btree.c:102
BTREE_SAVE_UPDATE
Definition: btree.c:48
btree_node_subtree_invariant
static bool btree_node_subtree_invariant(const struct m0_be_btree *btree, const struct m0_be_bnode *node)
Definition: btree.c:308
btree_mem_free_credit
static void btree_mem_free_credit(const struct m0_be_btree *btree, m0_bcount_t size, struct m0_be_tx_credit *accum)
Definition: btree.c:139
m0_be_seg
Definition: seg.h:66
M0_BBO_DELETE
Definition: btree.h:143
m0_be_btree_kv_ops
Definition: btree.h:96
be_btree_get_max_key_pos
static void be_btree_get_max_key_pos(struct m0_be_bnode *node, struct btree_node_pos *pos)
Definition: btree.c:619
m0_format_footer_verify
M0_INTERNAL int m0_format_footer_verify(const void *buffer, bool iem)
Definition: format.c:149
m0_be_seg_contains
M0_INTERNAL bool m0_be_seg_contains(const struct m0_be_seg *seg, const void *addr)
Definition: stubs.c:144
m0_be_bnode::bt_next
struct m0_be_bnode * bt_next
Definition: btree_internal.h:52
error_injection.dest
dest
Definition: error_injection.py:49
btree_op_fill
static void btree_op_fill(struct m0_be_op *op, struct m0_be_btree *btree, struct m0_be_tx *tx, enum m0_be_btree_op optype, struct m0_be_btree_anchor *anchor)
Definition: btree.c:78
node_push
static void node_push(struct m0_be_btree_cursor *it, struct m0_be_bnode *node, int idx)
Definition: btree.c:1066
m0_be_btree_cursor_kv_get
M0_INTERNAL void m0_be_btree_cursor_kv_get(struct m0_be_btree_cursor *cur, struct m0_buf *key, struct m0_buf *val)
Definition: btree.c:2485
be_btree_compare
static int be_btree_compare(const struct m0_be_btree *btree, const void *key0, const void *key1)
Definition: btree.c:162
btree_node_alloc_credit
static void btree_node_alloc_credit(const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
Definition: btree.c:1590
m0_forall
#define m0_forall(var, nr,...)
Definition: misc.h:112
m0_be_btree_update
M0_INTERNAL void m0_be_btree_update(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val)
Definition: btree.c:1941
btree_val
void * btree_val
Definition: btree_internal.h:589
kv_insert_credit
static void kv_insert_credit(const struct m0_be_btree *tree, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
Definition: btree.c:1639
be_btree_move_parent_key_to_right_child
static void be_btree_move_parent_key_to_right_child(struct m0_be_bnode *parent, struct m0_be_bnode *lch, struct m0_be_bnode *rch, unsigned int idx)
Definition: btree.c:737
m0_be_btree_cursor::bc_tree
struct m0_be_btree * bc_tree
Definition: btree.h:586
m0_be_btree_lookup_slant
M0_INTERNAL void m0_be_btree_lookup_slant(struct m0_be_btree *tree, struct m0_be_op *op, struct m0_buf *key, struct m0_buf *value)
Definition: btree.c:2041
m0_be_btree_backlink
Definition: btree.h:52
M0_BBO_DESTROY
Definition: btree.h:141
be_btree_merge_siblings
static struct m0_be_bnode * be_btree_merge_siblings(struct m0_be_tx *tx, struct m0_be_btree *tree, struct m0_be_bnode *parent, unsigned int idx)
Definition: btree.c:680
be_btree_insert_newkey
static void be_btree_insert_newkey(struct m0_be_btree *btree, struct m0_be_tx *tx, struct be_btree_key_val *kv)
Definition: btree.c:574
m0_be_op_active
M0_INTERNAL void m0_be_op_active(struct m0_be_op *op)
Definition: stubs.c:100
btree_node_pos
Definition: btree.c:52
btree_node_keyval_update
static void btree_node_keyval_update(struct m0_be_bnode *node, const struct m0_be_btree *btree, struct m0_be_tx *tx, unsigned int index)
Definition: btree.c:361
m0_be_btree_anchor
Definition: btree.h:463
M0_FI_ENABLED
#define M0_FI_ENABLED(tag)
Definition: finject.h:231
m0_fid
Definition: fid.h:38
BTREE_HEIGHT_MAX
Definition: btree.h:574
m0_format_footer_update
M0_INTERNAL void m0_format_footer_update(const void *buffer)
Definition: format.c:95
be_btree_get_btree_node
static struct btree_node_pos be_btree_get_btree_node(struct m0_be_btree_cursor *it, const void *key, bool slant)
Definition: btree.c:1102
m0_be_btree_anchor::ba_value
struct m0_buf ba_value
Definition: btree.h:469
m0_be_btree_cursor_stack_entry::bs_idx
int bs_idx
Definition: btree.h:567
m0_be_btree_cursor_get
M0_INTERNAL void m0_be_btree_cursor_get(struct m0_be_btree_cursor *cur, const struct m0_buf *key, bool slant)
Definition: btree.c:2295
m0_be_btree::bb_lock
struct m0_be_rwlock bb_lock
Definition: btree.h:74
m0_fid_type
Definition: fid.h:100
btree_internal.h
m0_be_btree_cursor_prev
M0_INTERNAL void m0_be_btree_cursor_prev(struct m0_be_btree_cursor *cur)
Definition: btree.c:2411
M0_BE_OP_SYNC_WITH
#define M0_BE_OP_SYNC_WITH(op, action)
Definition: op.h:207
mem_alloc
static void * mem_alloc(const struct m0_be_btree *btree, struct m0_be_tx *tx, m0_bcount_t size, uint64_t zonemask)
Definition: btree.c:116
m0_be_btree_anchor::ba_write
bool ba_write
Definition: btree.h:472
m0_be_btree::bb_header
struct m0_format_header bb_header
Definition: btree.h:64
M0_DEBUG
Definition: trace.h:487
m0_cookie_new
M0_INTERNAL void m0_cookie_new(uint64_t *gen)
Definition: cookie.c:83
size
m0_bcount_t size
Definition: di.c:39
_0C
#define _0C(exp)
Definition: assert.h:311
start
static int start(struct m0_fom *fom)
Definition: trigger_fom.c:321
be_btree_key_val::btree_val
void * btree_val
Definition: btree_internal.h:45
mem_update
static void mem_update(const struct m0_be_btree *btree, struct m0_be_tx *tx, void *ptr, m0_bcount_t size)
Definition: btree.c:110
m0_rwlock_read_lock
M0_INTERNAL void m0_rwlock_read_lock(struct m0_rwlock *lock)
Definition: rwlock.c:52
m0_be_free_aligned
M0_INTERNAL void m0_be_free_aligned(struct m0_be_allocator *a, struct m0_be_tx *tx, struct m0_be_op *op, void *ptr)
Definition: alloc.c:1101
M0_BBO_INSERT
Definition: btree.h:142
P_RIGHT
Definition: btree.c:193
m0_rwlock_fini
M0_INTERNAL void m0_rwlock_fini(struct m0_rwlock *lock)
Definition: rwlock.c:37
m0_be_btree_init
M0_INTERNAL void m0_be_btree_init(struct m0_be_btree *tree, struct m0_be_seg *seg, const struct m0_be_btree_kv_ops *ops)
Definition: btree.c:1487
m0_be_btree_cursor_init
M0_INTERNAL void m0_be_btree_cursor_init(struct m0_be_btree_cursor *cur, struct m0_be_btree *btree)
Definition: btree.c:2281
M0_BBO_UPDATE
Definition: btree.h:144
m0_be_bnode::bt_num_active_key
unsigned int bt_num_active_key
Definition: btree_internal.h:53
btree_count_items
static int btree_count_items(struct m0_be_btree *tree, m0_bcount_t *ksize, m0_bcount_t *vsize)
Definition: btree.c:1794
be_btree_key_val::btree_key
void * btree_key
Definition: btree_internal.h:44
be_btree_get_min_key_pos
static void be_btree_get_min_key_pos(struct m0_be_bnode *node, struct btree_node_pos *pos)
Definition: btree.c:638
P_LEFT
Definition: btree.c:192
seg
static struct m0_be_seg * seg
Definition: btree.c:40
btree_mem_alloc_credit
static void btree_mem_alloc_credit(const struct m0_be_btree *btree, m0_bcount_t size, struct m0_be_tx_credit *accum)
Definition: btree.c:131
m0_be_btree_cursor_get_sync
M0_INTERNAL int m0_be_btree_cursor_get_sync(struct m0_be_btree_cursor *cur, const struct m0_buf *key, bool slant)
Definition: btree.c:2331
m0_be_tx_capture
M0_INTERNAL void m0_be_tx_capture(struct m0_be_tx *tx, const struct m0_be_reg *reg)
Definition: stubs.c:190
m0_rwlock_read_unlock
M0_INTERNAL void m0_rwlock_read_unlock(struct m0_rwlock *lock)
Definition: rwlock.c:57
out
#define out(...)
Definition: gen.c:41
M0_BBT_NR
Definition: btree.h:131
M0_BBT_INVALID
Definition: btree.h:118
be_btree_insert
static void be_btree_insert(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val, struct m0_be_btree_anchor *anchor, uint64_t zonemask)
Definition: btree.c:1892
m0_be_allocator_credit
M0_INTERNAL void m0_be_allocator_credit(struct m0_be_allocator *a, enum m0_be_allocator_op optype, m0_bcount_t size, unsigned shift, struct m0_be_tx_credit *accum)
Definition: alloc.c:900
m0_be_btree_cursor
Definition: btree.h:583
ops
struct m0_fom_ops ops
Definition: io_foms.c:623
be_btree_set_node_params
static void be_btree_set_node_params(struct m0_be_bnode *p_node, unsigned int num_active_key, unsigned int level, bool isleaf)
Definition: btree.c:396
m0_be_op
Definition: op.h:74
M0_PRE_EX
#define M0_PRE_EX(cond)
btree_node_split_child_credit
static void btree_node_split_child_credit(const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
Definition: btree.c:1667
BTREE_ALLOC_SHIFT
Definition: btree.c:43
m0_be_btree_cursor_last_sync
M0_INTERNAL int m0_be_btree_cursor_last_sync(struct m0_be_btree_cursor *cur)
Definition: btree.c:2353
btree_node_update_credit
static void btree_node_update_credit(struct m0_be_tx_credit *accum, m0_bcount_t nr)
Definition: btree.c:1596
M0_BUF_INIT
#define M0_BUF_INIT(size, data)
Definition: buf.h:64
M0_BE_CREDIT_INC
#define M0_BE_CREDIT_INC(n, cr_user, credit)
Definition: tx.h:464
m0_be_btree_truncate
M0_INTERNAL void m0_be_btree_truncate(struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, m0_bcount_t limit)
Definition: btree.c:1564
src
struct m0_pdclust_src_addr src
Definition: fd.c:108
btree_node_pos::bnp_index
unsigned int bnp_index
Definition: btree.c:54
rc
int32_t rc
Definition: trigger_fop.h:47
btree_key
void * btree_key
Definition: btree_internal.h:588
be_btree_node_alloc
static struct m0_be_bnode * be_btree_node_alloc(const struct m0_be_btree *btree, struct m0_be_tx *tx)
Definition: btree.c:414
m0_be_op_is_done
M0_INTERNAL bool m0_be_op_is_done(struct m0_be_op *op)
Definition: stubs.c:108
ARRAY_SIZE
#define ARRAY_SIZE(a)
Definition: misc.h:45
M0_POST_EX
#define M0_POST_EX(cond)
offsetof
#define offsetof(typ, memb)
Definition: misc.h:29
m0_align
static uint64_t m0_align(uint64_t val, uint64_t alignment)
Definition: arith.h:170
be_btree_ksize
static m0_bcount_t be_btree_ksize(const struct m0_be_btree *btree, const void *key)
Definition: btree.c:147
M0_BE_OP_SYNC_RET_WITH
#define M0_BE_OP_SYNC_RET_WITH(op, action, member)
Definition: op.h:253
bnode
static int bnode(struct scanner *s, struct rectype *r, char *buf)
Definition: beck.c:1316
m0_be_btree::bb_ops
const struct m0_be_btree_kv_ops * bb_ops
Definition: btree.h:78
last
static struct m0_addb2_frame_header last
Definition: storage.c:93
M0_BE_CU_BTREE_INSERT
Definition: tx_credit.h:71
be_btree_move_parent_key_to_left_child
static void be_btree_move_parent_key_to_left_child(struct m0_be_bnode *parent, struct m0_be_bnode *lch, struct m0_be_bnode *rch, unsigned int idx)
Definition: btree.c:760
tail
static int tail(struct m0_sm *mach)
Definition: sm.c:474
b_nob
m0_bcount_t b_nob
Definition: buf.h:230
M0_BOP_TREE
Definition: op.h:68
m0_be_bnode::bt_isleaf
bool bt_isleaf
Definition: btree_internal.h:55
m0_be_tx
Definition: tx.h:280
bt_num_active_key
unsigned int bt_num_active_key
Definition: btree_internal.h:591
key
Definition: idx_mock.c:47
m0_cookie_dereference
M0_INTERNAL int m0_cookie_dereference(const struct m0_cookie *cookie, uint64_t **addr)
Definition: cookie.c:109
btree_node_free_credit
static void btree_node_free_credit(const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
Definition: btree.c:1608