Lines Matching refs:node
24 * @node refers to an xa_node; usually the primary one being operated on by
27 * @parent refers to the @xa_node closer to the head than @node.
78 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
80 return node->marks[(__force unsigned)mark];
83 static inline bool node_get_mark(struct xa_node *node,
86 return test_bit(offset, node_marks(node, mark));
90 static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
93 return __test_and_set_bit(offset, node_marks(node, mark));
97 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
100 return __test_and_clear_bit(offset, node_marks(node, mark));
103 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
105 return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
108 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
110 bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
141 /* extracts the offset within this node from the index */
142 static unsigned int get_offset(unsigned long index, struct xa_node *node)
144 return (index >> node->shift) & XA_CHUNK_MASK;
201 static void *xas_descend(struct xa_state *xas, struct xa_node *node)
203 unsigned int offset = get_offset(xas->xa_index, node);
204 void *entry = xa_entry(xas->xa, node, offset);
206 xas->xa_node = node;
209 entry = xa_entry(xas->xa, node, offset);
236 struct xa_node *node = xa_to_node(entry);
238 if (xas->xa_shift > node->shift)
240 entry = xas_descend(xas, node);
241 if (node->shift == 0)
248 /* Move the radix tree node cache here */
254 static void xa_node_free(struct xa_node *node)
256 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
257 node->array = XA_RCU_FREE;
258 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
269 struct xa_node *next, *node = xas->xa_alloc;
271 while (node) {
272 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
273 next = rcu_dereference_raw(node->parent);
274 radix_tree_node_rcu_free(&node->rcu_head);
275 xas->xa_alloc = node = next;
290 * Forward progress is guaranteed as one node is allocated here and
350 static void xas_update(struct xa_state *xas, struct xa_node *node)
353 xas->xa_update(node);
355 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
361 struct xa_node *node = xas->xa_alloc;
366 if (node) {
374 node = kmem_cache_alloc(radix_tree_node_cachep, gfp);
375 if (!node) {
382 node->offset = xas->xa_offset;
384 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
387 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
388 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
389 node->shift = shift;
390 node->count = 0;
391 node->nr_values = 0;
392 RCU_INIT_POINTER(node->parent, xas->xa_node);
393 node->array = xas->xa;
395 return node;
439 struct xa_node *node = xas->xa_node;
444 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
445 if (node->count != 1)
447 entry = xa_entry_locked(xa, node, 0);
450 if (!xa_is_node(entry) && node->shift)
457 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
460 node->count = 0;
461 node->nr_values = 0;
463 RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
464 xas_update(xas, node);
465 xa_node_free(node);
468 node = xa_to_node(entry);
469 node->parent = NULL;
477 * Attempts to delete the @xas->xa_node. This will fail if xa->node has
482 struct xa_node *node = xas->xa_node;
487 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
488 if (node->count)
491 parent = xa_parent_locked(xas->xa, node);
493 xas->xa_offset = node->offset;
494 xa_node_free(node);
505 node = parent;
506 xas_update(xas, node);
509 if (!node->parent)
514 * xas_free_nodes() - Free this node and all nodes that it references
518 * This node has been removed from the tree. We must now free it and all
525 struct xa_node *node = top;
528 void *entry = xa_entry_locked(xas->xa, node, offset);
530 if (node->shift && xa_is_node(entry)) {
531 node = xa_to_node(entry);
536 RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
541 parent = xa_parent_locked(xas->xa, node);
542 offset = node->offset + 1;
543 node->count = 0;
544 node->nr_values = 0;
545 xas_update(xas, node);
546 xa_node_free(node);
547 if (node == top)
549 node = parent;
561 struct xa_node *node = NULL;
572 node = xa_to_node(head);
573 shift = node->shift + XA_CHUNK_SHIFT;
580 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
581 node = xas_alloc(xas, shift);
582 if (!node)
585 node->count = 1;
587 node->nr_values = 1;
588 RCU_INIT_POINTER(node->slots[0], head);
593 node_mark_all(node, XA_FREE_MARK);
595 node_clear_mark(node, 0, XA_FREE_MARK);
599 node_set_mark(node, 0, mark);
607 * Now that the new node is fully initialised, we can add
612 rcu_assign_pointer(xa_to_node(head)->parent, node);
614 head = xa_mk_node(node);
616 xas_update(xas, node);
621 xas->xa_node = node;
643 struct xa_node *node = xas->xa_node;
647 if (xas_top(node)) {
661 } else if (node) {
664 shift = node->shift;
665 entry = xa_entry_locked(xa, node, offset);
666 slot = &node->slots[offset];
676 node = xas_alloc(xas, shift);
677 if (!node)
680 node_mark_all(node, XA_FREE_MARK);
681 rcu_assign_pointer(*slot, xa_mk_node(node));
683 node = xa_to_node(entry);
687 entry = xas_descend(xas, node);
688 slot = &node->slots[xas->xa_offset];
724 struct xa_node *node = xas->xa_node;
725 if (node->shift >= shift)
727 xas->xa_node = xa_parent_locked(xas->xa, node);
728 xas->xa_offset = node->offset - 1;
729 if (node->offset != 0)
746 static void update_node(struct xa_state *xas, struct xa_node *node,
749 if (!node || (!count && !values))
752 node->count += count;
753 node->nr_values += values;
754 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
755 XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
756 xas_update(xas, node);
776 struct xa_node *node;
793 node = xas->xa_node;
794 if (node && (xas->xa_shift < node->shift))
802 if (node) {
803 slot = &node->slots[offset];
819 if (xa_is_node(next) && (!node || node->shift))
821 if (!node)
834 next = xa_entry_locked(xas->xa, node, ++offset);
843 update_node(xas, node, count, values);
877 struct xa_node *node = xas->xa_node;
883 while (node) {
884 if (node_set_mark(node, offset, mark))
886 offset = node->offset;
887 node = xa_parent_locked(xas->xa, node);
906 struct xa_node *node = xas->xa_node;
912 while (node) {
913 if (!node_clear_mark(node, offset, mark))
915 if (node_any_mark(node, mark))
918 offset = node->offset;
919 node = xa_parent_locked(xas->xa, node);
955 static unsigned int node_get_marks(struct xa_node *node, unsigned int offset)
961 if (node_get_mark(node, offset, mark))
971 static void node_set_marks(struct xa_node *node, unsigned int offset,
978 node_set_mark(node, offset, mark);
1017 struct xa_node *node;
1019 node = kmem_cache_alloc(radix_tree_node_cachep, gfp);
1020 if (!node)
1022 node->array = xas->xa;
1025 RCU_INIT_POINTER(node->slots[i], entry);
1028 RCU_INIT_POINTER(node->slots[i], sibling);
1031 RCU_INIT_POINTER(node->parent, xas->xa_alloc);
1032 xas->xa_alloc = node;
1056 struct xa_node *node;
1060 node = xas->xa_node;
1061 if (xas_top(node))
1064 marks = node_get_marks(node, xas->xa_offset);
1068 if (xas->xa_shift < node->shift) {
1072 child->shift = node->shift - XA_CHUNK_SHIFT;
1077 RCU_INIT_POINTER(child->parent, node);
1078 node_set_marks(node, offset, child, marks);
1079 rcu_assign_pointer(node->slots[offset],
1087 node_set_marks(node, canon, NULL, marks);
1088 rcu_assign_pointer(node->slots[canon], entry);
1090 rcu_assign_pointer(node->slots[offset--],
1097 node->nr_values += values;
1098 xas_update(xas, node);
1120 struct xa_node *node = xas->xa_node;
1126 if (node) {
1129 if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
1132 xas->xa_index += (offset - xas->xa_offset) << node->shift;
1407 struct xa_node *node = xa_to_node(curr);
1408 curr = xas_descend(xas, node);
2032 struct xa_node *node = xas->xa_node;
2035 if (!IS_ENABLED(CONFIG_XARRAY_MULTI) || !node)
2037 mask = (XA_CHUNK_SIZE << node->shift) - 1;
2039 ((unsigned long)xas->xa_offset << node->shift);
2172 * @node: Node to be removed from the tree.
2177 void xa_delete_node(struct xa_node *node, xa_update_node_t update)
2180 .xa = node->array,
2181 .xa_index = (unsigned long)node->offset <<
2182 (node->shift + XA_CHUNK_SHIFT),
2183 .xa_shift = node->shift + XA_CHUNK_SHIFT,
2184 .xa_offset = node->offset,
2185 .xa_node = xa_parent_locked(node->array, node),
2224 void xa_dump_node(const struct xa_node *node)
2228 if (!node)
2230 if ((unsigned long)node & 3) {
2231 pr_cont("node %px\n", node);
2235 pr_cont("node %px %s %d parent %px shift %d count %d values %d "
2237 node, node->parent ? "offset" : "max", node->offset,
2238 node->parent, node->shift, node->count, node->nr_values,
2239 node->array, node->private_list.prev, node->private_list.next);
2242 pr_cont(" %lx", node->marks[i][j]);
2268 struct xa_node *node = xa_to_node(entry);
2269 xa_dump_node(node);
2271 xa_dump_entry(node->slots[i],
2272 index + (i << node->shift), node->shift);