| // SPDX-License-Identifier: GPL-2.0+ |
| /* |
| * Maple Tree implementation |
| * Copyright (c) 2018-2022 Oracle Corporation |
| * Authors: Liam R. Howlett <Liam.Howlett@oracle.com> |
| * Matthew Wilcox <willy@infradead.org> |
| * Copyright (c) 2023 ByteDance |
| * Author: Peng Zhang <zhangpeng.00@bytedance.com> |
| */ |
| |
| /* |
| * DOC: Interesting implementation details of the Maple Tree |
| * |
| * Each node type has a number of slots for entries and a number of slots for |
| * pivots. In the case of dense nodes, the pivots are implied by the position |
| * and are simply the slot index + the minimum of the node. |
| * |
| * In regular B-Tree terms, pivots are called keys. The term pivot is used to |
| * indicate that the tree is specifying ranges. Pivots may appear in the |
| * subtree with an entry attached to the value whereas keys are unique to a |
| * specific position of a B-tree. Pivot values are inclusive of the slot with |
| * the same index. |
| * |
| * |
| * The following illustrates the layout of a range64 nodes slots and pivots. |
| * |
| * |
| * Slots -> | 0 | 1 | 2 | ... | 12 | 13 | 14 | 15 | |
| * ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ |
| * │ │ │ │ │ │ │ │ └─ Implied maximum |
| * │ │ │ │ │ │ │ └─ Pivot 14 |
| * │ │ │ │ │ │ └─ Pivot 13 |
| * │ │ │ │ │ └─ Pivot 12 |
| * │ │ │ │ └─ Pivot 11 |
| * │ │ │ └─ Pivot 2 |
| * │ │ └─ Pivot 1 |
| * │ └─ Pivot 0 |
| * └─ Implied minimum |
| * |
| * Slot contents: |
| * Internal (non-leaf) nodes contain pointers to other nodes. |
| * Leaf nodes contain entries. |
| * |
| * The location of interest is often referred to as an offset. All offsets have |
| * a slot, but the last offset has an implied pivot from the node above (or |
| * UINT_MAX for the root node. |
| * |
| * Ranges complicate certain write activities. When modifying any of |
| * the B-tree variants, it is known that one entry will either be added or |
| * deleted. When modifying the Maple Tree, one store operation may overwrite |
| * the entire data set, or one half of the tree, or the middle half of the tree. |
| * |
| */ |
| |
| |
| #include <linux/maple_tree.h> |
| #include <linux/xarray.h> |
| #include <linux/types.h> |
| #include <linux/export.h> |
| #include <linux/slab.h> |
| #include <linux/limits.h> |
| #include <asm/barrier.h> |
| |
| #define CREATE_TRACE_POINTS |
| #include <trace/events/maple_tree.h> |
| |
| #define MA_ROOT_PARENT 1 |
| |
| /* |
| * Maple state flags |
| * * MA_STATE_BULK - Bulk insert mode |
| * * MA_STATE_REBALANCE - Indicate a rebalance during bulk insert |
| * * MA_STATE_PREALLOC - Preallocated nodes, WARN_ON allocation |
| */ |
| #define MA_STATE_BULK 1 |
| #define MA_STATE_REBALANCE 2 |
| #define MA_STATE_PREALLOC 4 |
| |
| #define ma_parent_ptr(x) ((struct maple_pnode *)(x)) |
| #define mas_tree_parent(x) ((unsigned long)(x->tree) | MA_ROOT_PARENT) |
| #define ma_mnode_ptr(x) ((struct maple_node *)(x)) |
| #define ma_enode_ptr(x) ((struct maple_enode *)(x)) |
| static struct kmem_cache *maple_node_cache; |
| |
| #ifdef CONFIG_DEBUG_MAPLE_TREE |
| static const unsigned long mt_max[] = { |
| [maple_dense] = MAPLE_NODE_SLOTS, |
| [maple_leaf_64] = ULONG_MAX, |
| [maple_range_64] = ULONG_MAX, |
| [maple_arange_64] = ULONG_MAX, |
| }; |
| #define mt_node_max(x) mt_max[mte_node_type(x)] |
| #endif |
| |
| static const unsigned char mt_slots[] = { |
| [maple_dense] = MAPLE_NODE_SLOTS, |
| [maple_leaf_64] = MAPLE_RANGE64_SLOTS, |
| [maple_range_64] = MAPLE_RANGE64_SLOTS, |
| [maple_arange_64] = MAPLE_ARANGE64_SLOTS, |
| }; |
| #define mt_slot_count(x) mt_slots[mte_node_type(x)] |
| |
| static const unsigned char mt_pivots[] = { |
| [maple_dense] = 0, |
| [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1, |
| [maple_range_64] = MAPLE_RANGE64_SLOTS - 1, |
| [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1, |
| }; |
| #define mt_pivot_count(x) mt_pivots[mte_node_type(x)] |
| |
| static const unsigned char mt_min_slots[] = { |
| [maple_dense] = MAPLE_NODE_SLOTS / 2, |
| [maple_leaf_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, |
| [maple_range_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, |
| [maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2) - 1, |
| }; |
| #define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)] |
| |
| #define MAPLE_BIG_NODE_SLOTS (MAPLE_RANGE64_SLOTS * 2 + 2) |
| #define MAPLE_BIG_NODE_GAPS (MAPLE_ARANGE64_SLOTS * 2 + 1) |
| |
| struct maple_big_node { |
| struct maple_pnode *parent; |
| unsigned long pivot[MAPLE_BIG_NODE_SLOTS - 1]; |
| union { |
| struct maple_enode *slot[MAPLE_BIG_NODE_SLOTS]; |
| struct { |
| unsigned long padding[MAPLE_BIG_NODE_GAPS]; |
| unsigned long gap[MAPLE_BIG_NODE_GAPS]; |
| }; |
| }; |
| unsigned char b_end; |
| enum maple_type type; |
| }; |
| |
| /* |
| * The maple_subtree_state is used to build a tree to replace a segment of an |
| * existing tree in a more atomic way. Any walkers of the older tree will hit a |
| * dead node and restart on updates. |
| */ |
| struct maple_subtree_state { |
| struct ma_state *orig_l; /* Original left side of subtree */ |
| struct ma_state *orig_r; /* Original right side of subtree */ |
| struct ma_state *l; /* New left side of subtree */ |
| struct ma_state *m; /* New middle of subtree (rare) */ |
| struct ma_state *r; /* New right side of subtree */ |
| struct ma_topiary *free; /* nodes to be freed */ |
| struct ma_topiary *destroy; /* Nodes to be destroyed (walked and freed) */ |
| struct maple_big_node *bn; |
| }; |
| |
| #ifdef CONFIG_KASAN_STACK |
| /* Prevent mas_wr_bnode() from exceeding the stack frame limit */ |
| #define noinline_for_kasan noinline_for_stack |
| #else |
| #define noinline_for_kasan inline |
| #endif |
| |
| /* Functions */ |
| static inline struct maple_node *mt_alloc_one(gfp_t gfp) |
| { |
| return kmem_cache_alloc(maple_node_cache, gfp); |
| } |
| |
| static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) |
| { |
| return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); |
| } |
| |
| static inline void mt_free_one(struct maple_node *node) |
| { |
| kmem_cache_free(maple_node_cache, node); |
| } |
| |
| static inline void mt_free_bulk(size_t size, void __rcu **nodes) |
| { |
| kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes); |
| } |
| |
| static void mt_free_rcu(struct rcu_head *head) |
| { |
| struct maple_node *node = container_of(head, struct maple_node, rcu); |
| |
| kmem_cache_free(maple_node_cache, node); |
| } |
| |
| /* |
| * ma_free_rcu() - Use rcu callback to free a maple node |
| * @node: The node to free |
| * |
| * The maple tree uses the parent pointer to indicate this node is no longer in |
| * use and will be freed. |
| */ |
| static void ma_free_rcu(struct maple_node *node) |
| { |
| WARN_ON(node->parent != ma_parent_ptr(node)); |
| call_rcu(&node->rcu, mt_free_rcu); |
| } |
| |
| static void mas_set_height(struct ma_state *mas) |
| { |
| unsigned int new_flags = mas->tree->ma_flags; |
| |
| new_flags &= ~MT_FLAGS_HEIGHT_MASK; |
| MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX); |
| new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET; |
| mas->tree->ma_flags = new_flags; |
| } |
| |
| static unsigned int mas_mt_height(struct ma_state *mas) |
| { |
| return mt_height(mas->tree); |
| } |
| |
| static inline unsigned int mt_attr(struct maple_tree *mt) |
| { |
| return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; |
| } |
| |
| static __always_inline enum maple_type mte_node_type( |
| const struct maple_enode *entry) |
| { |
| return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & |
| MAPLE_NODE_TYPE_MASK; |
| } |
| |
| static __always_inline bool ma_is_dense(const enum maple_type type) |
| { |
| return type < maple_leaf_64; |
| } |
| |
| static __always_inline bool ma_is_leaf(const enum maple_type type) |
| { |
| return type < maple_range_64; |
| } |
| |
| static __always_inline bool mte_is_leaf(const struct maple_enode *entry) |
| { |
| return ma_is_leaf(mte_node_type(entry)); |
| } |
| |
| /* |
| * We also reserve values with the bottom two bits set to '10' which are |
| * below 4096 |
| */ |
| static __always_inline bool mt_is_reserved(const void *entry) |
| { |
| return ((unsigned long)entry < MAPLE_RESERVED_RANGE) && |
| xa_is_internal(entry); |
| } |
| |
| static __always_inline void mas_set_err(struct ma_state *mas, long err) |
| { |
| mas->node = MA_ERROR(err); |
| mas->status = ma_error; |
| } |
| |
| static __always_inline bool mas_is_ptr(const struct ma_state *mas) |
| { |
| return mas->status == ma_root; |
| } |
| |
| static __always_inline bool mas_is_start(const struct ma_state *mas) |
| { |
| return mas->status == ma_start; |
| } |
| |
| static __always_inline bool mas_is_none(const struct ma_state *mas) |
| { |
| return mas->status == ma_none; |
| } |
| |
| static __always_inline bool mas_is_paused(const struct ma_state *mas) |
| { |
| return mas->status == ma_pause; |
| } |
| |
| static __always_inline bool mas_is_overflow(struct ma_state *mas) |
| { |
| return mas->status == ma_overflow; |
| } |
| |
| static inline bool mas_is_underflow(struct ma_state *mas) |
| { |
| return mas->status == ma_underflow; |
| } |
| |
| static __always_inline struct maple_node *mte_to_node( |
| const struct maple_enode *entry) |
| { |
| return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK); |
| } |
| |
| /* |
| * mte_to_mat() - Convert a maple encoded node to a maple topiary node. |
| * @entry: The maple encoded node |
| * |
| * Return: a maple topiary pointer |
| */ |
| static inline struct maple_topiary *mte_to_mat(const struct maple_enode *entry) |
| { |
| return (struct maple_topiary *) |
| ((unsigned long)entry & ~MAPLE_NODE_MASK); |
| } |
| |
| /* |
| * mas_mn() - Get the maple state node. |
| * @mas: The maple state |
| * |
| * Return: the maple node (not encoded - bare pointer). |
| */ |
| static inline struct maple_node *mas_mn(const struct ma_state *mas) |
| { |
| return mte_to_node(mas->node); |
| } |
| |
| /* |
| * mte_set_node_dead() - Set a maple encoded node as dead. |
| * @mn: The maple encoded node. |
| */ |
| static inline void mte_set_node_dead(struct maple_enode *mn) |
| { |
| mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn)); |
| smp_wmb(); /* Needed for RCU */ |
| } |
| |
| /* Bit 1 indicates the root is a node */ |
| #define MAPLE_ROOT_NODE 0x02 |
| /* maple_type stored bit 3-6 */ |
| #define MAPLE_ENODE_TYPE_SHIFT 0x03 |
| /* Bit 2 means a NULL somewhere below */ |
| #define MAPLE_ENODE_NULL 0x04 |
| |
| static inline struct maple_enode *mt_mk_node(const struct maple_node *node, |
| enum maple_type type) |
| { |
| return (void *)((unsigned long)node | |
| (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL); |
| } |
| |
| static inline void *mte_mk_root(const struct maple_enode *node) |
| { |
| return (void *)((unsigned long)node | MAPLE_ROOT_NODE); |
| } |
| |
| static inline void *mte_safe_root(const struct maple_enode *node) |
| { |
| return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE); |
| } |
| |
| static inline void *mte_set_full(const struct maple_enode *node) |
| { |
| return (void *)((unsigned long)node & ~MAPLE_ENODE_NULL); |
| } |
| |
| static inline void *mte_clear_full(const struct maple_enode *node) |
| { |
| return (void *)((unsigned long)node | MAPLE_ENODE_NULL); |
| } |
| |
| static inline bool mte_has_null(const struct maple_enode *node) |
| { |
| return (unsigned long)node & MAPLE_ENODE_NULL; |
| } |
| |
| static __always_inline bool ma_is_root(struct maple_node *node) |
| { |
| return ((unsigned long)node->parent & MA_ROOT_PARENT); |
| } |
| |
| static __always_inline bool mte_is_root(const struct maple_enode *node) |
| { |
| return ma_is_root(mte_to_node(node)); |
| } |
| |
| static inline bool mas_is_root_limits(const struct ma_state *mas) |
| { |
| return !mas->min && mas->max == ULONG_MAX; |
| } |
| |
| static __always_inline bool mt_is_alloc(struct maple_tree *mt) |
| { |
| return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE); |
| } |
| |
| /* |
| * The Parent Pointer |
| * Excluding root, the parent pointer is 256B aligned like all other tree nodes. |
| * When storing a 32 or 64 bit values, the offset can fit into 5 bits. The 16 |
| * bit values need an extra bit to store the offset. This extra bit comes from |
| * a reuse of the last bit in the node type. This is possible by using bit 1 to |
| * indicate if bit 2 is part of the type or the slot. |
| * |
| * Note types: |
| * 0x??1 = Root |
| * 0x?00 = 16 bit nodes |
| * 0x010 = 32 bit nodes |
| * 0x110 = 64 bit nodes |
| * |
| * Slot size and alignment |
| * 0b??1 : Root |
| * 0b?00 : 16 bit values, type in 0-1, slot in 2-7 |
| * 0b010 : 32 bit values, type in 0-2, slot in 3-7 |
| * 0b110 : 64 bit values, type in 0-2, slot in 3-7 |
| */ |
| |
| #define MAPLE_PARENT_ROOT 0x01 |
| |
| #define MAPLE_PARENT_SLOT_SHIFT 0x03 |
| #define MAPLE_PARENT_SLOT_MASK 0xF8 |
| |
| #define MAPLE_PARENT_16B_SLOT_SHIFT 0x02 |
| #define MAPLE_PARENT_16B_SLOT_MASK 0xFC |
| |
| #define MAPLE_PARENT_RANGE64 0x06 |
| #define MAPLE_PARENT_RANGE32 0x04 |
| #define MAPLE_PARENT_NOT_RANGE16 0x02 |
| |
| /* |
| * mte_parent_shift() - Get the parent shift for the slot storage. |
| * @parent: The parent pointer cast as an unsigned long |
| * Return: The shift into that pointer to the star to of the slot |
| */ |
| static inline unsigned long mte_parent_shift(unsigned long parent) |
| { |
| /* Note bit 1 == 0 means 16B */ |
| if (likely(parent & MAPLE_PARENT_NOT_RANGE16)) |
| return MAPLE_PARENT_SLOT_SHIFT; |
| |
| return MAPLE_PARENT_16B_SLOT_SHIFT; |
| } |
| |
| /* |
| * mte_parent_slot_mask() - Get the slot mask for the parent. |
| * @parent: The parent pointer cast as an unsigned long. |
| * Return: The slot mask for that parent. |
| */ |
| static inline unsigned long mte_parent_slot_mask(unsigned long parent) |
| { |
| /* Note bit 1 == 0 means 16B */ |
| if (likely(parent & MAPLE_PARENT_NOT_RANGE16)) |
| return MAPLE_PARENT_SLOT_MASK; |
| |
| return MAPLE_PARENT_16B_SLOT_MASK; |
| } |
| |
| /* |
| * mas_parent_type() - Return the maple_type of the parent from the stored |
| * parent type. |
| * @mas: The maple state |
| * @enode: The maple_enode to extract the parent's enum |
| * Return: The node->parent maple_type |
| */ |
| static inline |
| enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) |
| { |
| unsigned long p_type; |
| |
| p_type = (unsigned long)mte_to_node(enode)->parent; |
| if (WARN_ON(p_type & MAPLE_PARENT_ROOT)) |
| return 0; |
| |
| p_type &= MAPLE_NODE_MASK; |
| p_type &= ~mte_parent_slot_mask(p_type); |
| switch (p_type) { |
| case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */ |
| if (mt_is_alloc(mas->tree)) |
| return maple_arange_64; |
| return maple_range_64; |
| } |
| |
| return 0; |
| } |
| |
| /* |
| * mas_set_parent() - Set the parent node and encode the slot |
| * @enode: The encoded maple node. |
| * @parent: The encoded maple node that is the parent of @enode. |
| * @slot: The slot that @enode resides in @parent. |
| * |
| * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending on the |
| * parent type. |
| */ |
| static inline |
| void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, |
| const struct maple_enode *parent, unsigned char slot) |
| { |
| unsigned long val = (unsigned long)parent; |
| unsigned long shift; |
| unsigned long type; |
| enum maple_type p_type = mte_node_type(parent); |
| |
| MAS_BUG_ON(mas, p_type == maple_dense); |
| MAS_BUG_ON(mas, p_type == maple_leaf_64); |
| |
| switch (p_type) { |
| case maple_range_64: |
| case maple_arange_64: |
| shift = MAPLE_PARENT_SLOT_SHIFT; |
| type = MAPLE_PARENT_RANGE64; |
| break; |
| default: |
| case maple_dense: |
| case maple_leaf_64: |
| shift = type = 0; |
| break; |
| } |
| |
| val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */ |
| val |= (slot << shift) | type; |
| mte_to_node(enode)->parent = ma_parent_ptr(val); |
| } |
| |
| /* |
| * mte_parent_slot() - get the parent slot of @enode. |
| * @enode: The encoded maple node. |
| * |
| * Return: The slot in the parent node where @enode resides. |
| */ |
| static __always_inline |
| unsigned int mte_parent_slot(const struct maple_enode *enode) |
| { |
| unsigned long val = (unsigned long)mte_to_node(enode)->parent; |
| |
| if (unlikely(val & MA_ROOT_PARENT)) |
| return 0; |
| |
| /* |
| * Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost |
| * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT |
| */ |
| return (val & MAPLE_PARENT_16B_SLOT_MASK) >> mte_parent_shift(val); |
| } |
| |
| /* |
| * mte_parent() - Get the parent of @node. |
| * @node: The encoded maple node. |
| * |
| * Return: The parent maple node. |
| */ |
| static __always_inline |
| struct maple_node *mte_parent(const struct maple_enode *enode) |
| { |
| return (void *)((unsigned long) |
| (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK); |
| } |
| |
| /* |
| * ma_dead_node() - check if the @enode is dead. |
| * @enode: The encoded maple node |
| * |
| * Return: true if dead, false otherwise. |
| */ |
| static __always_inline bool ma_dead_node(const struct maple_node *node) |
| { |
| struct maple_node *parent; |
| |
| /* Do not reorder reads from the node prior to the parent check */ |
| smp_rmb(); |
| parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK); |
| return (parent == node); |
| } |
| |
| /* |
| * mte_dead_node() - check if the @enode is dead. |
| * @enode: The encoded maple node |
| * |
| * Return: true if dead, false otherwise. |
| */ |
| static __always_inline bool mte_dead_node(const struct maple_enode *enode) |
| { |
| struct maple_node *parent, *node; |
| |
| node = mte_to_node(enode); |
| /* Do not reorder reads from the node prior to the parent check */ |
| smp_rmb(); |
| parent = mte_parent(enode); |
| return (parent == node); |
| } |
| |
| /* |
| * mas_allocated() - Get the number of nodes allocated in a maple state. |
| * @mas: The maple state |
| * |
| * The ma_state alloc member is overloaded to hold a pointer to the first |
| * allocated node or to the number of requested nodes to allocate. If bit 0 is |
| * set, then the alloc contains the number of requested nodes. If there is an |
| * allocated node, then the total allocated nodes is in that node. |
| * |
| * Return: The total number of nodes allocated |
| */ |
| static inline unsigned long mas_allocated(const struct ma_state *mas) |
| { |
| if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) |
| return 0; |
| |
| return mas->alloc->total; |
| } |
| |
| /* |
| * mas_set_alloc_req() - Set the requested number of allocations. |
| * @mas: the maple state |
| * @count: the number of allocations. |
| * |
| * The requested number of allocations is either in the first allocated node, |
| * located in @mas->alloc->request_count, or directly in @mas->alloc if there is |
| * no allocated node. Set the request either in the node or do the necessary |
| * encoding to store in @mas->alloc directly. |
| */ |
| static inline void mas_set_alloc_req(struct ma_state *mas, unsigned long count) |
| { |
| if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) { |
| if (!count) |
| mas->alloc = NULL; |
| else |
| mas->alloc = (struct maple_alloc *)(((count) << 1U) | 1U); |
| return; |
| } |
| |
| mas->alloc->request_count = count; |
| } |
| |
| /* |
| * mas_alloc_req() - get the requested number of allocations. |
| * @mas: The maple state |
| * |
| * The alloc count is either stored directly in @mas, or in |
| * @mas->alloc->request_count if there is at least one node allocated. Decode |
| * the request count if it's stored directly in @mas->alloc. |
| * |
| * Return: The allocation request count. |
| */ |
| static inline unsigned int mas_alloc_req(const struct ma_state *mas) |
| { |
| if ((unsigned long)mas->alloc & 0x1) |
| return (unsigned long)(mas->alloc) >> 1; |
| else if (mas->alloc) |
| return mas->alloc->request_count; |
| return 0; |
| } |
| |
| /* |
| * ma_pivots() - Get a pointer to the maple node pivots. |
| * @node - the maple node |
| * @type - the node type |
| * |
| * In the event of a dead node, this array may be %NULL |
| * |
| * Return: A pointer to the maple node pivots |
| */ |
| static inline unsigned long *ma_pivots(struct maple_node *node, |
| enum maple_type type) |
| { |
| switch (type) { |
| case maple_arange_64: |
| return node->ma64.pivot; |
| case maple_range_64: |
| case maple_leaf_64: |
| return node->mr64.pivot; |
| case maple_dense: |
| return NULL; |
| } |
| return NULL; |
| } |
| |
| /* |
| * ma_gaps() - Get a pointer to the maple node gaps. |
| * @node - the maple node |
| * @type - the node type |
| * |
| * Return: A pointer to the maple node gaps |
| */ |
| static inline unsigned long *ma_gaps(struct maple_node *node, |
| enum maple_type type) |
| { |
| switch (type) { |
| case maple_arange_64: |
| return node->ma64.gap; |
| case maple_range_64: |
| case maple_leaf_64: |
| case maple_dense: |
| return NULL; |
| } |
| return NULL; |
| } |
| |
| /* |
| * mas_safe_pivot() - get the pivot at @piv or mas->max. |
| * @mas: The maple state |
| * @pivots: The pointer to the maple node pivots |
| * @piv: The pivot to fetch |
| * @type: The maple node type |
| * |
| * Return: The pivot at @piv within the limit of the @pivots array, @mas->max |
| * otherwise. |
| */ |
| static __always_inline unsigned long |
| mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots, |
| unsigned char piv, enum maple_type type) |
| { |
| if (piv >= mt_pivots[type]) |
| return mas->max; |
| |
| return pivots[piv]; |
| } |
| |
| /* |
| * mas_safe_min() - Return the minimum for a given offset. |
| * @mas: The maple state |
| * @pivots: The pointer to the maple node pivots |
| * @offset: The offset into the pivot array |
| * |
| * Return: The minimum range value that is contained in @offset. |
| */ |
| static inline unsigned long |
| mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) |
| { |
| if (likely(offset)) |
| return pivots[offset - 1] + 1; |
| |
| return mas->min; |
| } |
| |
| /* |
| * mte_set_pivot() - Set a pivot to a value in an encoded maple node. |
| * @mn: The encoded maple node |
| * @piv: The pivot offset |
| * @val: The value of the pivot |
| */ |
| static inline void mte_set_pivot(struct maple_enode *mn, unsigned char piv, |
| unsigned long val) |
| { |
| struct maple_node *node = mte_to_node(mn); |
| enum maple_type type = mte_node_type(mn); |
| |
| BUG_ON(piv >= mt_pivots[type]); |
| switch (type) { |
| case maple_range_64: |
| case maple_leaf_64: |
| node->mr64.pivot[piv] = val; |
| break; |
| case maple_arange_64: |
| node->ma64.pivot[piv] = val; |
| break; |
| case maple_dense: |
| break; |
| } |
| |
| } |
| |
| /* |
| * ma_slots() - Get a pointer to the maple node slots. |
| * @mn: The maple node |
| * @mt: The maple node type |
| * |
| * Return: A pointer to the maple node slots |
| */ |
| static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) |
| { |
| switch (mt) { |
| case maple_arange_64: |
| return mn->ma64.slot; |
| case maple_range_64: |
| case maple_leaf_64: |
| return mn->mr64.slot; |
| case maple_dense: |
| return mn->slot; |
| } |
| |
| return NULL; |
| } |
| |
| static inline bool mt_write_locked(const struct maple_tree *mt) |
| { |
| return mt_external_lock(mt) ? mt_write_lock_is_held(mt) : |
| lockdep_is_held(&mt->ma_lock); |
| } |
| |
| static __always_inline bool mt_locked(const struct maple_tree *mt) |
| { |
| return mt_external_lock(mt) ? mt_lock_is_held(mt) : |
| lockdep_is_held(&mt->ma_lock); |
| } |
| |
| static __always_inline void *mt_slot(const struct maple_tree *mt, |
| void __rcu **slots, unsigned char offset) |
| { |
| return rcu_dereference_check(slots[offset], mt_locked(mt)); |
| } |
| |
| static __always_inline void *mt_slot_locked(struct maple_tree *mt, |
| void __rcu **slots, unsigned char offset) |
| { |
| return rcu_dereference_protected(slots[offset], mt_write_locked(mt)); |
| } |
| /* |
| * mas_slot_locked() - Get the slot value when holding the maple tree lock. |
| * @mas: The maple state |
| * @slots: The pointer to the slots |
| * @offset: The offset into the slots array to fetch |
| * |
| * Return: The entry stored in @slots at the @offset. |
| */ |
| static __always_inline void *mas_slot_locked(struct ma_state *mas, |
| void __rcu **slots, unsigned char offset) |
| { |
| return mt_slot_locked(mas->tree, slots, offset); |
| } |
| |
| /* |
| * mas_slot() - Get the slot value when not holding the maple tree lock. |
| * @mas: The maple state |
| * @slots: The pointer to the slots |
| * @offset: The offset into the slots array to fetch |
| * |
| * Return: The entry stored in @slots at the @offset |
| */ |
| static __always_inline void *mas_slot(struct ma_state *mas, void __rcu **slots, |
| unsigned char offset) |
| { |
| return mt_slot(mas->tree, slots, offset); |
| } |
| |
| /* |
| * mas_root() - Get the maple tree root. |
| * @mas: The maple state. |
| * |
| * Return: The pointer to the root of the tree |
| */ |
| static __always_inline void *mas_root(struct ma_state *mas) |
| { |
| return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree)); |
| } |
| |
| static inline void *mt_root_locked(struct maple_tree *mt) |
| { |
| return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt)); |
| } |
| |
| /* |
| * mas_root_locked() - Get the maple tree root when holding the maple tree lock. |
| * @mas: The maple state. |
| * |
| * Return: The pointer to the root of the tree |
| */ |
| static inline void *mas_root_locked(struct ma_state *mas) |
| { |
| return mt_root_locked(mas->tree); |
| } |
| |
| static inline struct maple_metadata *ma_meta(struct maple_node *mn, |
| enum maple_type mt) |
| { |
| switch (mt) { |
| case maple_arange_64: |
| return &mn->ma64.meta; |
| default: |
| return &mn->mr64.meta; |
| } |
| } |
| |
| /* |
| * ma_set_meta() - Set the metadata information of a node. |
| * @mn: The maple node |
| * @mt: The maple node type |
| * @offset: The offset of the highest sub-gap in this node. |
| * @end: The end of the data in this node. |
| */ |
| static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, |
| unsigned char offset, unsigned char end) |
| { |
| struct maple_metadata *meta = ma_meta(mn, mt); |
| |
| meta->gap = offset; |
| meta->end = end; |
| } |
| |
| /* |
| * mt_clear_meta() - clear the metadata information of a node, if it exists |
| * @mt: The maple tree |
| * @mn: The maple node |
| * @type: The maple node type |
| * @offset: The offset of the highest sub-gap in this node. |
| * @end: The end of the data in this node. |
| */ |
| static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, |
| enum maple_type type) |
| { |
| struct maple_metadata *meta; |
| unsigned long *pivots; |
| void __rcu **slots; |
| void *next; |
| |
| switch (type) { |
| case maple_range_64: |
| pivots = mn->mr64.pivot; |
| if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) { |
| slots = mn->mr64.slot; |
| next = mt_slot_locked(mt, slots, |
| MAPLE_RANGE64_SLOTS - 1); |
| if (unlikely((mte_to_node(next) && |
| mte_node_type(next)))) |
| return; /* no metadata, could be node */ |
| } |
| fallthrough; |
| case maple_arange_64: |
| meta = ma_meta(mn, type); |
| break; |
| default: |
| return; |
| } |
| |
| meta->gap = 0; |
| meta->end = 0; |
| } |
| |
| /* |
| * ma_meta_end() - Get the data end of a node from the metadata |
| * @mn: The maple node |
| * @mt: The maple node type |
| */ |
| static inline unsigned char ma_meta_end(struct maple_node *mn, |
| enum maple_type mt) |
| { |
| struct maple_metadata *meta = ma_meta(mn, mt); |
| |
| return meta->end; |
| } |
| |
| /* |
| * ma_meta_gap() - Get the largest gap location of a node from the metadata |
| * @mn: The maple node |
| */ |
| static inline unsigned char ma_meta_gap(struct maple_node *mn) |
| { |
| return mn->ma64.meta.gap; |
| } |
| |
| /* |
| * ma_set_meta_gap() - Set the largest gap location in a nodes metadata |
| * @mn: The maple node |
| * @mn: The maple node type |
| * @offset: The location of the largest gap. |
| */ |
| static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, |
| unsigned char offset) |
| { |
| |
| struct maple_metadata *meta = ma_meta(mn, mt); |
| |
| meta->gap = offset; |
| } |
| |
| /* |
| * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. |
| * @mat - the ma_topiary, a linked list of dead nodes. |
| * @dead_enode - the node to be marked as dead and added to the tail of the list |
| * |
| * Add the @dead_enode to the linked list in @mat. |
| */ |
| static inline void mat_add(struct ma_topiary *mat, |
| struct maple_enode *dead_enode) |
| { |
| mte_set_node_dead(dead_enode); |
| mte_to_mat(dead_enode)->next = NULL; |
| if (!mat->tail) { |
| mat->tail = mat->head = dead_enode; |
| return; |
| } |
| |
| mte_to_mat(mat->tail)->next = dead_enode; |
| mat->tail = dead_enode; |
| } |
| |
| static void mt_free_walk(struct rcu_head *head); |
| static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, |
| bool free); |
| /* |
| * mas_mat_destroy() - Free all nodes and subtrees in a dead list. |
| * @mas - the maple state |
| * @mat - the ma_topiary linked list of dead nodes to free. |
| * |
| * Destroy walk a dead list. |
| */ |
| static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat) |
| { |
| struct maple_enode *next; |
| struct maple_node *node; |
| bool in_rcu = mt_in_rcu(mas->tree); |
| |
| while (mat->head) { |
| next = mte_to_mat(mat->head)->next; |
| node = mte_to_node(mat->head); |
| mt_destroy_walk(mat->head, mas->tree, !in_rcu); |
| if (in_rcu) |
| call_rcu(&node->rcu, mt_free_walk); |
| mat->head = next; |
| } |
| } |
| /* |
| * mas_descend() - Descend into the slot stored in the ma_state. |
| * @mas - the maple state. |
| * |
| * Note: Not RCU safe, only use in write side or debug code. |
| */ |
| static inline void mas_descend(struct ma_state *mas) |
| { |
| enum maple_type type; |
| unsigned long *pivots; |
| struct maple_node *node; |
| void __rcu **slots; |
| |
| node = mas_mn(mas); |
| type = mte_node_type(mas->node); |
| pivots = ma_pivots(node, type); |
| slots = ma_slots(node, type); |
| |
| if (mas->offset) |
| mas->min = pivots[mas->offset - 1] + 1; |
| mas->max = mas_safe_pivot(mas, pivots, mas->offset, type); |
| mas->node = mas_slot(mas, slots, mas->offset); |
| } |
| |
| /* |
| * mte_set_gap() - Set a maple node gap. |
| * @mn: The encoded maple node |
| * @gap: The offset of the gap to set |
| * @val: The gap value |
| */ |
| static inline void mte_set_gap(const struct maple_enode *mn, |
| unsigned char gap, unsigned long val) |
| { |
| switch (mte_node_type(mn)) { |
| default: |
| break; |
| case maple_arange_64: |
| mte_to_node(mn)->ma64.gap[gap] = val; |
| break; |
| } |
| } |
| |
| /* |
| * mas_ascend() - Walk up a level of the tree. |
| * @mas: The maple state |
| * |
| * Sets the @mas->max and @mas->min to the correct values when walking up. This |
| * may cause several levels of walking up to find the correct min and max. |
| * May find a dead node which will cause a premature return. |
| * Return: 1 on dead node, 0 otherwise |
| */ |
| static int mas_ascend(struct ma_state *mas) |
| { |
| struct maple_enode *p_enode; /* parent enode. */ |
| struct maple_enode *a_enode; /* ancestor enode. */ |
| struct maple_node *a_node; /* ancestor node. */ |
| struct maple_node *p_node; /* parent node. */ |
| unsigned char a_slot; |
| enum maple_type a_type; |
| unsigned long min, max; |
| unsigned long *pivots; |
| bool set_max = false, set_min = false; |
| |
| a_node = mas_mn(mas); |
| if (ma_is_root(a_node)) { |
| mas->offset = 0; |
| return 0; |
| } |
| |
| p_node = mte_parent(mas->node); |
| if (unlikely(a_node == p_node)) |
| return 1; |
| |
| a_type = mas_parent_type(mas, mas->node); |
| mas->offset = mte_parent_slot(mas->node); |
| a_enode = mt_mk_node(p_node, a_type); |
| |
| /* Check to make sure all parent information is still accurate */ |
| if (p_node != mte_parent(mas->node)) |
| return 1; |
| |
| mas->node = a_enode; |
| |
| if (mte_is_root(a_enode)) { |
| mas->max = ULONG_MAX; |
| mas->min = 0; |
| return 0; |
| } |
| |
| min = 0; |
| max = ULONG_MAX; |
| if (!mas->offset) { |
| min = mas->min; |
| set_min = true; |
| } |
| |
| if (mas->max == ULONG_MAX) |
| set_max = true; |
| |
| do { |
| p_enode = a_enode; |
| a_type = mas_parent_type(mas, p_enode); |
| a_node = mte_parent(p_enode); |
| a_slot = mte_parent_slot(p_enode); |
| a_enode = mt_mk_node(a_node, a_type); |
| pivots = ma_pivots(a_node, a_type); |
| |
| if (unlikely(ma_dead_node(a_node))) |
| return 1; |
| |
| if (!set_min && a_slot) { |
| set_min = true; |
| min = pivots[a_slot - 1] + 1; |
| } |
| |
| if (!set_max && a_slot < mt_pivots[a_type]) { |
| set_max = true; |
| max = pivots[a_slot]; |
| } |
| |
| if (unlikely(ma_dead_node(a_node))) |
| return 1; |
| |
| if (unlikely(ma_is_root(a_node))) |
| break; |
| |
| } while (!set_min || !set_max); |
| |
| mas->max = max; |
| mas->min = min; |
| return 0; |
| } |
| |
| /* |
| * mas_pop_node() - Get a previously allocated maple node from the maple state. |
| * @mas: The maple state |
| * |
| * Return: A pointer to a maple node. |
| */ |
| static inline struct maple_node *mas_pop_node(struct ma_state *mas) |
| { |
| struct maple_alloc *ret, *node = mas->alloc; |
| unsigned long total = mas_allocated(mas); |
| unsigned int req = mas_alloc_req(mas); |
| |
| /* nothing or a request pending. */ |
| if (WARN_ON(!total)) |
| return NULL; |
| |
| if (total == 1) { |
| /* single allocation in this ma_state */ |
| mas->alloc = NULL; |
| ret = node; |
| goto single_node; |
| } |
| |
| if (node->node_count == 1) { |
| /* Single allocation in this node. */ |
| mas->alloc = node->slot[0]; |
| mas->alloc->total = node->total - 1; |
| ret = node; |
| goto new_head; |
| } |
| node->total--; |
| ret = node->slot[--node->node_count]; |
| node->slot[node->node_count] = NULL; |
| |
| single_node: |
| new_head: |
| if (req) { |
| req++; |
| mas_set_alloc_req(mas, req); |
| } |
| |
| memset(ret, 0, sizeof(*ret)); |
| return (struct maple_node *)ret; |
| } |
| |
| /* |
| * mas_push_node() - Push a node back on the maple state allocation. |
| * @mas: The maple state |
| * @used: The used maple node |
| * |
| * Stores the maple node back into @mas->alloc for reuse. Updates allocated and |
| * requested node count as necessary. |
| */ |
| static inline void mas_push_node(struct ma_state *mas, struct maple_node *used) |
| { |
| struct maple_alloc *reuse = (struct maple_alloc *)used; |
| struct maple_alloc *head = mas->alloc; |
| unsigned long count; |
| unsigned int requested = mas_alloc_req(mas); |
| |
| count = mas_allocated(mas); |
| |
| reuse->request_count = 0; |
| reuse->node_count = 0; |
| if (count && (head->node_count < MAPLE_ALLOC_SLOTS)) { |
| head->slot[head->node_count++] = reuse; |
| head->total++; |
| goto done; |
| } |
| |
| reuse->total = 1; |
| if ((head) && !((unsigned long)head & 0x1)) { |
| reuse->slot[0] = head; |
| reuse->node_count = 1; |
| reuse->total += head->total; |
| } |
| |
| mas->alloc = reuse; |
| done: |
| if (requested > 1) |
| mas_set_alloc_req(mas, requested - 1); |
| } |
| |
| /* |
| * mas_alloc_nodes() - Allocate nodes into a maple state |
| * @mas: The maple state |
| * @gfp: The GFP Flags |
| */ |
| static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) |
| { |
| struct maple_alloc *node; |
| unsigned long allocated = mas_allocated(mas); |
| unsigned int requested = mas_alloc_req(mas); |
| unsigned int count; |
| void **slots = NULL; |
| unsigned int max_req = 0; |
| |
| if (!requested) |
| return; |
| |
| mas_set_alloc_req(mas, 0); |
| if (mas->mas_flags & MA_STATE_PREALLOC) { |
| if (allocated) |
| return; |
| BUG_ON(!allocated); |
| WARN_ON(!allocated); |
| } |
| |
| if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS) { |
| node = (struct maple_alloc *)mt_alloc_one(gfp); |
| if (!node) |
| goto nomem_one; |
| |
| if (allocated) { |
| node->slot[0] = mas->alloc; |
| node->node_count = 1; |
| } else { |
| node->node_count = 0; |
| } |
| |
| mas->alloc = node; |
| node->total = ++allocated; |
| requested--; |
| } |
| |
| node = mas->alloc; |
| node->request_count = 0; |
| while (requested) { |
| max_req = MAPLE_ALLOC_SLOTS - node->node_count; |
| slots = (void **)&node->slot[node->node_count]; |
| max_req = min(requested, max_req); |
| count = mt_alloc_bulk(gfp, max_req, slots); |
| if (!count) |
| goto nomem_bulk; |
| |
| if (node->node_count == 0) { |
| node->slot[0]->node_count = 0; |
| node->slot[0]->request_count = 0; |
| } |
| |
| node->node_count += count; |
| allocated += count; |
| node = node->slot[0]; |
| requested -= count; |
| } |
| mas->alloc->total = allocated; |
| return; |
| |
| nomem_bulk: |
| /* Clean up potential freed allocations on bulk failure */ |
| memset(slots, 0, max_req * sizeof(unsigned long)); |
| nomem_one: |
| mas_set_alloc_req(mas, requested); |
| if (mas->alloc && !(((unsigned long)mas->alloc & 0x1))) |
| mas->alloc->total = allocated; |
| mas_set_err(mas, -ENOMEM); |
| } |
| |
| /* |
| * mas_free() - Free an encoded maple node |
| * @mas: The maple state |
| * @used: The encoded maple node to free. |
| * |
| * Uses rcu free if necessary, pushes @used back on the maple state allocations |
| * otherwise. |
| */ |
| static inline void mas_free(struct ma_state *mas, struct maple_enode *used) |
| { |
| struct maple_node *tmp = mte_to_node(used); |
| |
| if (mt_in_rcu(mas->tree)) |
| ma_free_rcu(tmp); |
| else |
| mas_push_node(mas, tmp); |
| } |
| |
| /* |
| * mas_node_count_gfp() - Check if enough nodes are allocated and request more |
| * if there is not enough nodes. |
| * @mas: The maple state |
| * @count: The number of nodes needed |
| * @gfp: the gfp flags |
| */ |
| static void mas_node_count_gfp(struct ma_state *mas, int count, gfp_t gfp) |
| { |
| unsigned long allocated = mas_allocated(mas); |
| |
| if (allocated < count) { |
| mas_set_alloc_req(mas, count - allocated); |
| mas_alloc_nodes(mas, gfp); |
| } |
| } |
| |
| /* |
| * mas_node_count() - Check if enough nodes are allocated and request more if |
| * there is not enough nodes. |
| * @mas: The maple state |
| * @count: The number of nodes needed |
| * |
| * Note: Uses GFP_NOWAIT | __GFP_NOWARN for gfp flags. |
| */ |
| static void mas_node_count(struct ma_state *mas, int count) |
| { |
| return mas_node_count_gfp(mas, count, GFP_NOWAIT | __GFP_NOWARN); |
| } |
| |
| /* |
| * mas_start() - Sets up maple state for operations. |
| * @mas: The maple state. |
| * |
| * If mas->status == mas_start, then set the min, max and depth to |
| * defaults. |
| * |
| * Return: |
| * - If mas->node is an error or not mas_start, return NULL. |
| * - If it's an empty tree: NULL & mas->status == ma_none |
| * - If it's a single entry: The entry & mas->status == mas_root |
| * - If it's a tree: NULL & mas->status == safe root node. |
| */ |
| static inline struct maple_enode *mas_start(struct ma_state *mas) |
| { |
| if (likely(mas_is_start(mas))) { |
| struct maple_enode *root; |
| |
| mas->min = 0; |
| mas->max = ULONG_MAX; |
| |
| retry: |
| mas->depth = 0; |
| root = mas_root(mas); |
| /* Tree with nodes */ |
| if (likely(xa_is_node(root))) { |
| mas->depth = 1; |
| mas->status = ma_active; |
| mas->node = mte_safe_root(root); |
| mas->offset = 0; |
| if (mte_dead_node(mas->node)) |
| goto retry; |
| |
| return NULL; |
| } |
| |
| /* empty tree */ |
| if (unlikely(!root)) { |
| mas->node = NULL; |
| mas->status = ma_none; |
| mas->offset = MAPLE_NODE_SLOTS; |
| return NULL; |
| } |
| |
| /* Single entry tree */ |
| mas->status = ma_root; |
| mas->offset = MAPLE_NODE_SLOTS; |
| |
| /* Single entry tree. */ |
| if (mas->index > 0) |
| return NULL; |
| |
| return root; |
| } |
| |
| return NULL; |
| } |
| |
| /* |
| * ma_data_end() - Find the end of the data in a node. |
| * @node: The maple node |
| * @type: The maple node type |
| * @pivots: The array of pivots in the node |
| * @max: The maximum value in the node |
| * |
| * Uses metadata to find the end of the data when possible. |
| * Return: The zero indexed last slot with data (may be null). |
| */ |
| static __always_inline unsigned char ma_data_end(struct maple_node *node, |
| enum maple_type type, unsigned long *pivots, unsigned long max) |
| { |
| unsigned char offset; |
| |
| if (!pivots) |
| return 0; |
| |
| if (type == maple_arange_64) |
| return ma_meta_end(node, type); |
| |
| offset = mt_pivots[type] - 1; |
| if (likely(!pivots[offset])) |
| return ma_meta_end(node, type); |
| |
| if (likely(pivots[offset] == max)) |
| return offset; |
| |
| return mt_pivots[type]; |
| } |
| |
| /* |
| * mas_data_end() - Find the end of the data (slot). |
| * @mas: the maple state |
| * |
| * This method is optimized to check the metadata of a node if the node type |
| * supports data end metadata. |
| * |
| * Return: The zero indexed last slot with data (may be null). |
| */ |
| static inline unsigned char mas_data_end(struct ma_state *mas) |
| { |
| enum maple_type type; |
| struct maple_node *node; |
| unsigned char offset; |
| unsigned long *pivots; |
| |
| type = mte_node_type(mas->node); |
| node = mas_mn(mas); |
| if (type == maple_arange_64) |
| return ma_meta_end(node, type); |
| |
| pivots = ma_pivots(node, type); |
| if (unlikely(ma_dead_node(node))) |
| return 0; |
| |
| offset = mt_pivots[type] - 1; |
| if (likely(!pivots[offset])) |
| return ma_meta_end(node, type); |
| |
| if (likely(pivots[offset] == mas->max)) |
| return offset; |
| |
| return mt_pivots[type]; |
| } |
| |
| /* |
| * mas_leaf_max_gap() - Returns the largest gap in a leaf node |
| * @mas - the maple state |
| * |
| * Return: The maximum gap in the leaf. |
| */ |
| static unsigned long mas_leaf_max_gap(struct ma_state *mas) |
| { |
| enum maple_type mt; |
| unsigned long pstart, gap, max_gap; |
| struct maple_node *mn; |
| unsigned long *pivots; |
| void __rcu **slots; |
| unsigned char i; |
| unsigned char max_piv; |
| |
| mt = mte_node_type(mas->node); |
| mn = mas_mn(mas); |
| slots = ma_slots(mn, mt); |
| max_gap = 0; |
| if (unlikely(ma_is_dense(mt))) { |
| gap = 0; |
| for (i = 0; i < mt_slots[mt]; i++) { |
| if (slots[i]) { |
| if (gap > max_gap) |
| max_gap = gap; |
| gap = 0; |
| } else { |
| gap++; |
| } |
| } |
| if (gap > max_gap) |
| max_gap = gap; |
| return max_gap; |
| } |
| |
| /* |
| * Check the first implied pivot optimizes the loop below and slot 1 may |
| * be skipped if there is a gap in slot 0. |
| */ |
| pivots = ma_pivots(mn, mt); |
| if (likely(!slots[0])) { |
| max_gap = pivots[0] - mas->min + 1; |
| i = 2; |
| } else { |
| i = 1; |
| } |
| |
| /* reduce max_piv as the special case is checked before the loop */ |
| max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; |
| /* |
| * Check end implied pivot which can only be a gap on the right most |
| * node. |
| */ |
| if (unlikely(mas->max == ULONG_MAX) && !slots[max_piv + 1]) { |
| gap = ULONG_MAX - pivots[max_piv]; |
| if (gap > max_gap) |
| max_gap = gap; |
| |
| if (max_gap > pivots[max_piv] - mas->min) |
| return max_gap; |
| } |
| |
| for (; i <= max_piv; i++) { |
| /* data == no gap. */ |
| if (likely(slots[i])) |
| continue; |
| |
| pstart = pivots[i - 1]; |
| gap = pivots[i] - pstart; |
| if (gap > max_gap) |
| max_gap = gap; |
| |
| /* There cannot be two gaps in a row. */ |
| i++; |
| } |
| return max_gap; |
| } |
| |
| /* |
| * ma_max_gap() - Get the maximum gap in a maple node (non-leaf) |
| * @node: The maple node |
| * @gaps: The pointer to the gaps |
| * @mt: The maple node type |
| * @*off: Pointer to store the offset location of the gap. |
| * |
| * Uses the metadata data end to scan backwards across set gaps. |
| * |
| * Return: The maximum gap value |
| */ |
| static inline unsigned long |
| ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, |
| unsigned char *off) |
| { |
| unsigned char offset, i; |
| unsigned long max_gap = 0; |
| |
| i = offset = ma_meta_end(node, mt); |
| do { |
| if (gaps[i] > max_gap) { |
| max_gap = gaps[i]; |
| offset = i; |
| } |
| } while (i--); |
| |
| *off = offset; |
| return max_gap; |
| } |
| |
| /* |
| * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. |
| * @mas: The maple state. |
| * |
| * Return: The gap value. |
| */ |
| static inline unsigned long mas_max_gap(struct ma_state *mas) |
| { |
| unsigned long *gaps; |
| unsigned char offset; |
| enum maple_type mt; |
| struct maple_node *node; |
| |
| mt = mte_node_type(mas->node); |
| if (ma_is_leaf(mt)) |
| return mas_leaf_max_gap(mas); |
| |
| node = mas_mn(mas); |
| MAS_BUG_ON(mas, mt != maple_arange_64); |
| offset = ma_meta_gap(node); |
| gaps = ma_gaps(node, mt); |
| return gaps[offset]; |
| } |
| |
| /* |
| * mas_parent_gap() - Set the parent gap and any gaps above, as needed |
| * @mas: The maple state |
| * @offset: The gap offset in the parent to set |
| * @new: The new gap value. |
| * |
| * Set the parent gap then continue to set the gap upwards, using the metadata |
| * of the parent to see if it is necessary to check the node above. |
| */ |
| static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, |
| unsigned long new) |
| { |
| unsigned long meta_gap = 0; |
| struct maple_node *pnode; |
| struct maple_enode *penode; |
| unsigned long *pgaps; |
| unsigned char meta_offset; |
| enum maple_type pmt; |
| |
| pnode = mte_parent(mas->node); |
| pmt = mas_parent_type(mas, mas->node); |
| penode = mt_mk_node(pnode, pmt); |
| pgaps = ma_gaps(pnode, pmt); |
| |
| ascend: |
| MAS_BUG_ON(mas, pmt != maple_arange_64); |
| meta_offset = ma_meta_gap(pnode); |
| meta_gap = pgaps[meta_offset]; |
| |
| pgaps[offset] = new; |
| |
| if (meta_gap == new) |
| return; |
| |
| if (offset != meta_offset) { |
| if (meta_gap > new) |
| return; |
| |
| ma_set_meta_gap(pnode, pmt, offset); |
| } else if (new < meta_gap) { |
| new = ma_max_gap(pnode, pgaps, pmt, &meta_offset); |
| ma_set_meta_gap(pnode, pmt, meta_offset); |
| } |
| |
| if (ma_is_root(pnode)) |
| return; |
| |
| /* Go to the parent node. */ |
| pnode = mte_parent(penode); |
| pmt = mas_parent_type(mas, penode); |
| pgaps = ma_gaps(pnode, pmt); |
| offset = mte_parent_slot(penode); |
| penode = mt_mk_node(pnode, pmt); |
| goto ascend; |
| } |
| |
| /* |
| * mas_update_gap() - Update a nodes gaps and propagate up if necessary. |
| * @mas - the maple state. |
| */ |
| static inline void mas_update_gap(struct ma_state *mas) |
| { |
| unsigned char pslot; |
| unsigned long p_gap; |
| unsigned long max_gap; |
| |
| if (!mt_is_alloc(mas->tree)) |
| return; |
| |
| if (mte_is_root(mas->node)) |
| return; |
| |
| max_gap = mas_max_gap(mas); |
| |
| pslot = mte_parent_slot(mas->node); |
| p_gap = ma_gaps(mte_parent(mas->node), |
| mas_parent_type(mas, mas->node))[pslot]; |
| |
| if (p_gap != max_gap) |
| mas_parent_gap(mas, pslot, max_gap); |
| } |
| |
| /* |
| * mas_adopt_children() - Set the parent pointer of all nodes in @parent to |
| * @parent with the slot encoded. |
| * @mas - the maple state (for the tree) |
| * @parent - the maple encoded node containing the children. |
| */ |
| static inline void mas_adopt_children(struct ma_state *mas, |
| struct maple_enode *parent) |
| { |
| enum maple_type type = mte_node_type(parent); |
| struct maple_node *node = mte_to_node(parent); |
| void __rcu **slots = ma_slots(node, type); |
| unsigned long *pivots = ma_pivots(node, type); |
| struct maple_enode *child; |
| unsigned char offset; |
| |
| offset = ma_data_end(node, type, pivots, mas->max); |
| do { |
| child = mas_slot_locked(mas, slots, offset); |
| mas_set_parent(mas, child, parent, offset); |
| } while (offset--); |
| } |
| |
| /* |
| * mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the old |
| * node as dead. |
| * @mas - the maple state with the new node |
| * @old_enode - The old maple encoded node to replace. |
| */ |
| static inline void mas_put_in_tree(struct ma_state *mas, |
| struct maple_enode *old_enode) |
| __must_hold(mas->tree->ma_lock) |
| { |
| unsigned char offset; |
| void __rcu **slots; |
| |
| if (mte_is_root(mas->node)) { |
| mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas)); |
| rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); |
| mas_set_height(mas); |
| } else { |
| |
| offset = mte_parent_slot(mas->node); |
| slots = ma_slots(mte_parent(mas->node), |
| mas_parent_type(mas, mas->node)); |
| rcu_assign_pointer(slots[offset], mas->node); |
| } |
| |
| mte_set_node_dead(old_enode); |
| } |
| |
| /* |
| * mas_replace_node() - Replace a node by putting it in the tree, marking it |
| * dead, and freeing it. |
| * the parent encoding to locate the maple node in the tree. |
| * @mas - the ma_state with @mas->node pointing to the new node. |
| * @old_enode - The old maple encoded node. |
| */ |
| static inline void mas_replace_node(struct ma_state *mas, |
| struct maple_enode *old_enode) |
| __must_hold(mas->tree->ma_lock) |
| { |
| mas_put_in_tree(mas, old_enode); |
| mas_free(mas, old_enode); |
| } |
| |
| /* |
| * mas_find_child() - Find a child who has the parent @mas->node. |
| * @mas: the maple state with the parent. |
| * @child: the maple state to store the child. |
| */ |
| static inline bool mas_find_child(struct ma_state *mas, struct ma_state *child) |
| __must_hold(mas->tree->ma_lock) |
| { |
| enum maple_type mt; |
| unsigned char offset; |
| unsigned char end; |
| unsigned long *pivots; |
| struct maple_enode *entry; |
| struct maple_node *node; |
| void __rcu **slots; |
| |
| mt = mte_node_type(mas->node); |
| node = mas_mn(mas); |
| slots = ma_slots(node, mt); |
| pivots = ma_pivots(node, mt); |
| end = ma_data_end(node, mt, pivots, mas->max); |
| for (offset = mas->offset; offset <= end; offset++) { |
| entry = mas_slot_locked(mas, slots, offset); |
| if (mte_parent(entry) == node) { |
| *child = *mas; |
| mas->offset = offset + 1; |
| child->offset = offset; |
| mas_descend(child); |
| child->offset = 0; |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /* |
| * mab_shift_right() - Shift the data in mab right. Note, does not clean out the |
| * old data or set b_node->b_end. |
| * @b_node: the maple_big_node |
| * @shift: the shift count |
| */ |
| static inline void mab_shift_right(struct maple_big_node *b_node, |
| unsigned char shift) |
| { |
| unsigned long size = b_node->b_end * sizeof(unsigned long); |
| |
| memmove(b_node->pivot + shift, b_node->pivot, size); |
| memmove(b_node->slot + shift, b_node->slot, size); |
| if (b_node->type == maple_arange_64) |
| memmove(b_node->gap + shift, b_node->gap, size); |
| } |
| |
| /* |
| * mab_middle_node() - Check if a middle node is needed (unlikely) |
| * @b_node: the maple_big_node that contains the data. |
| * @size: the amount of data in the b_node |
| * @split: the potential split location |
| * @slot_count: the size that can be stored in a single node being considered. |
| * |
| * Return: true if a middle node is required. |
| */ |
| static inline bool mab_middle_node(struct maple_big_node *b_node, int split, |
| unsigned char slot_count) |
| { |
| unsigned char size = b_node->b_end; |
| |
| if (size >= 2 * slot_count) |
| return true; |
| |
| if (!b_node->slot[split] && (size >= 2 * slot_count - 1)) |
| return true; |
| |
| return false; |
| } |
| |
| /* |
| * mab_no_null_split() - ensure the split doesn't fall on a NULL |
| * @b_node: the maple_big_node with the data |
| * @split: the suggested split location |
| * @slot_count: the number of slots in the node being considered. |
| * |
| * Return: the split location. |
| */ |
| static inline int mab_no_null_split(struct maple_big_node *b_node, |
| unsigned char split, unsigned char slot_count) |
| { |
| if (!b_node->slot[split]) { |
| /* |
| * If the split is less than the max slot && the right side will |
| * still be sufficient, then increment the split on NULL. |
| */ |
| if ((split < slot_count - 1) && |
| (b_node->b_end - split) > (mt_min_slots[b_node->type])) |
| split++; |
| else |
| split--; |
| } |
| return split; |
| } |
| |
| /* |
| * mab_calc_split() - Calculate the split location and if there needs to be two |
| * splits. |
| * @bn: The maple_big_node with the data |
| * @mid_split: The second split, if required. 0 otherwise. |
| * |
| * Return: The first split location. The middle split is set in @mid_split. |
| */ |
| static inline int mab_calc_split(struct ma_state *mas, |
| struct maple_big_node *bn, unsigned char *mid_split, unsigned long min) |
| { |
| unsigned char b_end = bn->b_end; |
| int split = b_end / 2; /* Assume equal split. */ |
| unsigned char slot_min, slot_count = mt_slots[bn->type]; |
| |
| /* |
| * To support gap tracking, all NULL entries are kept together and a node cannot |
| * end on a NULL entry, with the exception of the left-most leaf. The |
| * limitation means that the split of a node must be checked for this condition |
| * and be able to put more data in one direction or the other. |
| */ |
| if (unlikely((mas->mas_flags & MA_STATE_BULK))) { |
| *mid_split = 0; |
| split = b_end - mt_min_slots[bn->type]; |
| |
| if (!ma_is_leaf(bn->type)) |
| return split; |
| |
| mas->mas_flags |= MA_STATE_REBALANCE; |
| if (!bn->slot[split]) |
| split--; |
| return split; |
| } |
| |
| /* |
| * Although extremely rare, it is possible to enter what is known as the 3-way |
| * split scenario. The 3-way split comes about by means of a store of a range |
| * that overwrites the end and beginning of two full nodes. The result is a set |
| * of entries that cannot be stored in 2 nodes. Sometimes, these two nodes can |
| * also be located in different parent nodes which are also full. This can |
| * carry upwards all the way to the root in the worst case. |
| */ |
| if (unlikely(mab_middle_node(bn, split, slot_count))) { |
| split = b_end / 3; |
| *mid_split = split * 2; |
| } else { |
| slot_min = mt_min_slots[bn->type]; |
| |
| *mid_split = 0; |
| /* |
| * Avoid having a range less than the slot count unless it |
| * causes one node to be deficient. |
| * NOTE: mt_min_slots is 1 based, b_end and split are zero. |
| */ |
| while ((split < slot_count - 1) && |
| ((bn->pivot[split] - min) < slot_count - 1) && |
| (b_end - split > slot_min)) |
| split++; |
| } |
| |
| /* Avoid ending a node on a NULL entry */ |
| split = mab_no_null_split(bn, split, slot_count); |
| |
| if (unlikely(*mid_split)) |
| *mid_split = mab_no_null_split(bn, *mid_split, slot_count); |
| |
| return split; |
| } |
| |
| /* |
| * mas_mab_cp() - Copy data from a maple state inclusively to a maple_big_node |
| * and set @b_node->b_end to the next free slot. |
| * @mas: The maple state |
| * @mas_start: The starting slot to copy |
| * @mas_end: The end slot to copy (inclusively) |
| * @b_node: The maple_big_node to place the data |
| * @mab_start: The starting location in maple_big_node to store the data. |
| */ |
| static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, |
| unsigned char mas_end, struct maple_big_node *b_node, |
| unsigned char mab_start) |
| { |
| enum maple_type mt; |
| struct maple_node *node; |
| void __rcu **slots; |
| unsigned long *pivots, *gaps; |
| int i = mas_start, j = mab_start; |
| unsigned char piv_end; |
| |
| node = mas_mn(mas); |
| mt = mte_node_type(mas->node); |
| pivots = ma_pivots(node, mt); |
| if (!i) { |
| b_node->pivot[j] = pivots[i++]; |
| if (unlikely(i > mas_end)) |
| goto complete; |
| j++; |
| } |
| |
| piv_end = min(mas_end, mt_pivots[mt]); |
| for (; i < piv_end; i++, j++) { |
| b_node->pivot[j] = pivots[i]; |
| if (unlikely(!b_node->pivot[j])) |
| break; |
| |
| if (unlikely(mas->max == b_node->pivot[j])) |
| goto complete; |
| } |
| |
| if (likely(i <= mas_end)) |
| b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); |
| |
| complete: |
| b_node->b_end = ++j; |
| j -= mab_start; |
| slots = ma_slots(node, mt); |
| memcpy(b_node->slot + mab_start, slots + mas_start, sizeof(void *) * j); |
| if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { |
| gaps = ma_gaps(node, mt); |
| memcpy(b_node->gap + mab_start, gaps + mas_start, |
| sizeof(unsigned long) * j); |
| } |
| } |
| |
| /* |
| * mas_leaf_set_meta() - Set the metadata of a leaf if possible. |
| * @node: The maple node |
| * @mt: The maple type |
| * @end: The node end |
| */ |
| static inline void mas_leaf_set_meta(struct maple_node *node, |
| enum maple_type mt, unsigned char end) |
| { |
| if (end < mt_slots[mt] - 1) |
| ma_set_meta(node, mt, 0, end); |
| } |
| |
| /* |
| * mab_mas_cp() - Copy data from maple_big_node to a maple encoded node. |
| * @b_node: the maple_big_node that has the data |
| * @mab_start: the start location in @b_node. |
| * @mab_end: The end location in @b_node (inclusively) |
| * @mas: The maple state with the maple encoded node. |
| */ |
| static inline void mab_mas_cp(struct maple_big_node *b_node, |
| unsigned char mab_start, unsigned char mab_end, |
| struct ma_state *mas, bool new_max) |
| { |
| int i, j = 0; |
| enum maple_type mt = mte_node_type(mas->node); |
| struct maple_node *node = mte_to_node(mas->node); |
| void __rcu **slots = ma_slots(node, mt); |
| unsigned long *pivots = ma_pivots(node, mt); |
| unsigned long *gaps = NULL; |
| unsigned char end; |
| |
| if (mab_end - mab_start > mt_pivots[mt]) |
| mab_end--; |
| |
| if (!pivots[mt_pivots[mt] - 1]) |
| slots[mt_pivots[mt]] = NULL; |
| |
| i = mab_start; |
| do { |
| pivots[j++] = b_node->pivot[i++]; |
| } while (i <= mab_end && likely(b_node->pivot[i])); |
| |
| memcpy(slots, b_node->slot + mab_start, |
| sizeof(void *) * (i - mab_start)); |
| |
| if (new_max) |
| mas->max = b_node->pivot[i - 1]; |
| |
| end = j - 1; |
| if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { |
| unsigned long max_gap = 0; |
| unsigned char offset = 0; |
| |
| gaps = ma_gaps(node, mt); |
| do { |
| gaps[--j] = b_node->gap[--i]; |
| if (gaps[j] > max_gap) { |
| offset = j; |
| max_gap = gaps[j]; |
| } |
| } while (j); |
| |
| ma_set_meta(node, mt, offset, end); |
| } else { |
| mas_leaf_set_meta(node, mt, end); |
| } |
| } |
| |
| /* |
| * mas_bulk_rebalance() - Rebalance the end of a tree after a bulk insert. |
| * @mas: The maple state |
| * @end: The maple node end |
| * @mt: The maple node type |
| */ |
| static inline void mas_bulk_rebalance(struct ma_state *mas, unsigned char end, |
| enum maple_type mt) |
| { |
| if (!(mas->mas_flags & MA_STATE_BULK)) |
| return; |
| |
| if (mte_is_root(mas->node)) |
| return; |
| |
| if (end > mt_min_slots[mt]) { |
| mas->mas_flags &= ~MA_STATE_REBALANCE; |
| return; |
| } |
| } |
| |
| /* |
| * mas_store_b_node() - Store an @entry into the b_node while also copying the |
| * data from a maple encoded node. |
| * @wr_mas: the maple write state |
| * @b_node: the maple_big_node to fill with data |
| * @offset_end: the offset to end copying |
| * |
| * Return: The actual end of the data stored in @b_node |
| */ |
| static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, |
| struct maple_big_node *b_node, unsigned char offset_end) |
| { |
| unsigned char slot; |
| unsigned char b_end; |
| /* Possible underflow of piv will wrap back to 0 before use. */ |
| unsigned long piv; |
| struct ma_state *mas = wr_mas->mas; |
| |
| b_node->type = wr_mas->type; |
| b_end = 0; |
| slot = mas->offset; |
| if (slot) { |
| /* Copy start data up to insert. */ |
| mas_mab_cp(mas, 0, slot - 1, b_node, 0); |
| b_end = b_node->b_end; |
| piv = b_node->pivot[b_end - 1]; |
| } else |
| piv = mas->min - 1; |
| |
| if (piv + 1 < mas->index) { |
| /* Handle range starting after old range */ |
| b_node->slot[b_end] = wr_mas->content; |
| if (!wr_mas->content) |
| b_node->gap[b_end] = mas->index - 1 - piv; |
| b_node->pivot[b_end++] = mas->index - 1; |
| } |
| |
| /* Store the new entry. */ |
| mas->offset = b_end; |
| b_node->slot[b_end] = wr_mas->entry; |
| b_node->pivot[b_end] = mas->last; |
| |
| /* Appended. */ |
| if (mas->last >= mas->max) |
| goto b_end; |
| |
| /* Handle new range ending before old range ends */ |
| piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); |
| if (piv > mas->last) { |
| if (piv == ULONG_MAX) |
| mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type); |
| |
| if (offset_end != slot) |
| wr_mas->content = mas_slot_locked(mas, wr_mas->slots, |
| offset_end); |
| |
| b_node->slot[++b_end] = wr_mas->content; |
| if (!wr_mas->content) |
| b_node->gap[b_end] = piv - mas->last + 1; |
| b_node->pivot[b_end] = piv; |
| } |
| |
| slot = offset_end + 1; |
| if (slot > mas->end) |
| goto b_end; |
| |
| /* Copy end data to the end of the node. */ |
| mas_mab_cp(mas, slot, mas->end + 1, b_node, ++b_end); |
| b_node->b_end--; |
| return; |
| |
| b_end: |
| b_node->b_end = b_end; |
| } |
| |
| /* |
| * mas_prev_sibling() - Find the previous node with the same parent. |
| * @mas: the maple state |
| * |
| * Return: True if there is a previous sibling, false otherwise. |
| */ |
| static inline bool mas_prev_sibling(struct ma_state *mas) |
| { |
| unsigned int p_slot = mte_parent_slot(mas->node); |
| |
| if (mte_is_root(mas->node)) |
| return false; |
| |
| if (!p_slot) |
| return false; |
| |
| mas_ascend(mas); |
| mas->offset = p_slot - 1; |
| mas_descend(mas); |
| return true; |
| } |
| |
| /* |
| * mas_next_sibling() - Find the next node with the same parent. |
| * @mas: the maple state |
| * |
| * Return: true if there is a next sibling, false otherwise. |
| */ |
| static inline bool mas_next_sibling(struct ma_state *mas) |
| { |
| MA_STATE(parent, mas->tree, mas->index, mas->last); |
| |
| if (mte_is_root(mas->node)) |
| return false; |
| |
| parent = *mas; |
| mas_ascend(&parent); |
| parent.offset = mte_parent_slot(mas->node) + 1; |
| if (parent.offset > mas_data_end(&parent)) |
| return false; |
| |
| *mas = parent; |
| mas_descend(mas); |
| return true; |
| } |
| |
| /* |
| * mte_node_or_none() - Set the enode and state. |
| * @enode: The encoded maple node. |
| * |
| * Set the node to the enode and the status. |
| */ |
| static inline void mas_node_or_none(struct ma_state *mas, |
| struct maple_enode *enode) |
| { |
| if (enode) { |
| mas->node = enode; |
| mas->status = ma_active; |
| } else { |
| mas->node = NULL; |
| mas->status = ma_none; |
| } |
| } |
| |
| /* |
| * mas_wr_node_walk() - Find the correct offset for the index in the @mas. |
| * @wr_mas: The maple write state |
| * |
| * Uses mas_slot_locked() and does not need to worry about dead nodes. |
| */ |
| static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) |
| { |
| struct ma_state *mas = wr_mas->mas; |
| unsigned char count, offset; |
| |
| if (unlikely(ma_is_dense(wr_mas->type))) { |
| wr_mas->r_max = wr_mas->r_min = mas->index; |
| mas->offset = mas->index = mas->min; |
| return; |
| } |
| |
| wr_mas->node = mas_mn(wr_mas->mas); |
| wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type); |
| count = mas->end = ma_data_end(wr_mas->node, wr_mas->type, |
| wr_mas->pivots, mas->max); |
| offset = mas->offset; |
| |
| while (offset < count && mas->index > wr_mas->pivots[offset]) |
| offset++; |
| |
| wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; |
| wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); |
| wr_mas->offset_end = mas->offset = offset; |
| } |
| |
| /* |
| * mast_rebalance_next() - Rebalance against the next node |
| * @mast: The maple subtree state |
| * @old_r: The encoded maple node to the right (next node). |
| */ |
| static inline void mast_rebalance_next(struct maple_subtree_state *mast) |
| { |
| unsigned char b_end = mast->bn->b_end; |
| |
| mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), |
| mast->bn, b_end); |
| mast->orig_r->last = mast->orig_r->max; |
| } |
| |
| /* |
| * mast_rebalance_prev() - Rebalance against the previous node |
| * @mast: The maple subtree state |
| * @old_l: The encoded maple node to the left (previous node) |
| */ |
| static inline void mast_rebalance_prev(struct maple_subtree_state *mast) |
| { |
| unsigned char end = mas_data_end(mast->orig_l) + 1; |
| unsigned char b_end = mast->bn->b_end; |
| |
| mab_shift_right(mast->bn, end); |
| mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); |
| mast->l->min = mast->orig_l->min; |
| mast->orig_l->index = mast->orig_l->min; |
| mast->bn->b_end = end + b_end; |
| mast->l->offset += end; |
| } |
| |
| /* |
| * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favouring |
| * the node to the right. Checking the nodes to the right then the left at each |
| * level upwards until root is reached. |
| * Data is copied into the @mast->bn. |
| * @mast: The maple_subtree_state. |
| */ |
| static inline |
| bool mast_spanning_rebalance(struct maple_subtree_state *mast) |
| { |
| struct ma_state r_tmp = *mast->orig_r; |
| struct ma_state l_tmp = *mast->orig_l; |
| unsigned char depth = 0; |
| |
| do { |
| mas_ascend(mast->orig_r); |
| mas_ascend(mast->orig_l); |
| depth++; |
| if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { |
| mast->orig_r->offset++; |
| do { |
| mas_descend(mast->orig_r); |
| mast->orig_r->offset = 0; |
| } while (--depth); |
| |
| mast_rebalance_next(mast); |
| *mast->orig_l = l_tmp; |
| return true; |
| } else if (mast->orig_l->offset != 0) { |
| mast->orig_l->offset--; |
| do { |
| mas_descend(mast->orig_l); |
| mast->orig_l->offset = |
| mas_data_end(mast->orig_l); |
| } while (--depth); |
| |
| mast_rebalance_prev(mast); |
| *mast->orig_r = r_tmp; |
| return true; |
| } |
| } while (!mte_is_root(mast->orig_r->node)); |
| |
| *mast->orig_r = r_tmp; |
| *mast->orig_l = l_tmp; |
| return false; |
| } |
| |
| /* |
| * mast_ascend() - Ascend the original left and right maple states. |
| * @mast: the maple subtree state. |
| * |
| * Ascend the original left and right sides. Set the offsets to point to the |
| * data already in the new tree (@mast->l and @mast->r). |
| */ |
| static inline void mast_ascend(struct maple_subtree_state *mast) |
| { |
| MA_WR_STATE(wr_mas, mast->orig_r, NULL); |
| mas_ascend(mast->orig_l); |
| mas_ascend(mast->orig_r); |
| |
| mast->orig_r->offset = 0; |
| mast->orig_r->index = mast->r->max; |
| /* last should be larger than or equal to index */ |
| if (mast->orig_r->last < mast->orig_r->index) |
| mast->orig_r->last = mast->orig_r->index; |
| |
| wr_mas.type = mte_node_type(mast->orig_r->node); |
| mas_wr_node_walk(&wr_mas); |
| /* Set up the left side of things */ |
| mast->orig_l->offset = 0; |
| mast->orig_l->index = mast->l->min; |
| wr_mas.mas = mast->orig_l; |
| wr_mas.type = mte_node_type(mast->orig_l->node); |
| mas_wr_node_walk(&wr_mas); |
| |
| mast->bn->type = wr_mas.type; |
| } |
| |
| /* |
| * mas_new_ma_node() - Create and return a new maple node. Helper function. |
| * @mas: the maple state with the allocations. |
| * @b_node: the maple_big_node with the type encoding. |
| * |
| * Use the node type from the maple_big_node to allocate a new node from the |
| * ma_state. This function exists mainly for code readability. |
| * |
| * Return: A new maple encoded node |
| */ |
| static inline struct maple_enode |
| *mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node) |
| { |
| return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), b_node->type); |
| } |
| |
| /* |
| * mas_mab_to_node() - Set up right and middle nodes |
| * |
| * @mas: the maple state that contains the allocations. |
| * @b_node: the node which contains the data. |
| * @left: The pointer which will have the left node |
| * @right: The pointer which may have the right node |
| * @middle: the pointer which may have the middle node (rare) |
| * @mid_split: the split location for the middle node |
| * |
| * Return: the split of left. |
| */ |
| static inline unsigned char mas_mab_to_node(struct ma_state *mas, |
| struct maple_big_node *b_node, struct maple_enode **left, |
| struct maple_enode **right, struct maple_enode **middle, |
| unsigned char *mid_split, unsigned long min) |
| { |
| unsigned char split = 0; |
| unsigned char slot_count = mt_slots[b_node->type]; |
| |
| *left = mas_new_ma_node(mas, b_node); |
| *right = NULL; |
| *middle = NULL; |
| *mid_split = 0; |
| |
| if (b_node->b_end < slot_count) { |
| split = b_node->b_end; |
| } else { |
| split = mab_calc_split(mas, b_node, mid_split, min); |
| *right = mas_new_ma_node(mas, b_node); |
| } |
| |
| if (*mid_split) |
| *middle = mas_new_ma_node(mas, b_node); |
| |
| return split; |
| |
| } |
| |
| /* |
| * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end |
| * pointer. |
| * @b_node - the big node to add the entry |
| * @mas - the maple state to get the pivot (mas->max) |
| * @entry - the entry to add, if NULL nothing happens. |
| */ |
| static inline void mab_set_b_end(struct maple_big_node *b_node, |
| struct ma_state *mas, |
| void *entry) |
| { |
| if (!entry) |
| return; |
| |
| b_node->slot[b_node->b_end] = entry; |
| if (mt_is_alloc(mas->tree)) |
| b_node->gap[b_node->b_end] = mas_max_gap(mas); |
| b_node->pivot[b_node->b_end++] = mas->max; |
| } |
| |
| /* |
| * mas_set_split_parent() - combine_then_separate helper function. Sets the parent |
| * of @mas->node to either @left or @right, depending on @slot and @split |
| * |
| * @mas - the maple state with the node that needs a parent |
| * @left - possible parent 1 |
| * @right - possible parent 2 |
| * @slot - the slot the mas->node was placed |
| * @split - the split location between @left and @right |
| */ |
| static inline void mas_set_split_parent(struct ma_state *mas, |
| struct maple_enode *left, |
| struct maple_enode *right, |
| unsigned char *slot, unsigned char split) |
| { |
| if (mas_is_none(mas)) |
| return; |
| |
| if ((*slot) <= split) |
| mas_set_parent(mas, mas->node, left, *slot); |
| else if (right) |
| mas_set_parent(mas, mas->node, right, (*slot) - split - 1); |
| |
| (*slot)++; |
| } |
| |
| /* |
| * mte_mid_split_check() - Check if the next node passes the mid-split |
| * @**l: Pointer to left encoded maple node. |
| * @**m: Pointer to middle encoded maple node. |
| * @**r: Pointer to right encoded maple node. |
| * @slot: The offset |
| * @*split: The split location. |
| * @mid_split: The middle split. |
| */ |
| static inline void mte_mid_split_check(struct maple_enode **l, |
| struct maple_enode **r, |
| struct maple_enode *right, |
| unsigned char slot, |
| unsigned char *split, |
| unsigned char mid_split) |
| { |
| if (*r == right) |
| return; |
| |
| if (slot < mid_split) |
| return; |
| |
| *l = *r; |
| *r = right; |
| *split = mid_split; |
| } |
| |
| /* |
| * mast_set_split_parents() - Helper function to set three nodes parents. Slot |
| * is taken from @mast->l. |
| * @mast - the maple subtree state |
| * @left - the left node |
| * @right - the right node |
| * @split - the split location. |
| */ |
| static inline void mast_set_split_parents(struct maple_subtree_state *mast, |
| struct maple_enode *left, |
| struct maple_enode *middle, |
| struct maple_enode *right, |
| unsigned char split, |
| unsigned char mid_split) |
| { |
| unsigned char slot; |
| struct maple_enode *l = left; |
| struct maple_enode *r = right; |
| |
| if (mas_is_none(mast->l)) |
| return; |
| |
| if (middle) |
| r = middle; |
| |
| slot = mast->l->offset; |
| |
| mte_mid_split_check(&l, &r, right, slot, &split, mid_split); |
| mas_set_split_parent(mast->l, l, r, &slot, split); |
| |
| mte_mid_split_check(&l, &r, right, slot, &split, mid_split); |
| mas_set_split_parent(mast->m, l, r, &slot, split); |
| |
| mte_mid_split_check(&l, &r, right, slot, &split, mid_split); |
| mas_set_split_parent(mast->r, l, r, &slot, split); |
| } |
| |
| /* |
| * mas_topiary_node() - Dispose of a single node |
| * @mas: The maple state for pushing nodes |
| * @enode: The encoded maple node |
| * @in_rcu: If the tree is in rcu mode |
| * |
| * The node will either be RCU freed or pushed back on the maple state. |
| */ |
| static inline void mas_topiary_node(struct ma_state *mas, |
| struct ma_state *tmp_mas, bool in_rcu) |
| { |
| struct maple_node *tmp; |
| struct maple_enode *enode; |
| |
| if (mas_is_none(tmp_mas)) |
| return; |
| |
| enode = tmp_mas->node; |
| tmp = mte_to_node(enode); |
| mte_set_node_dead(enode); |
| if (in_rcu) |
| ma_free_rcu(tmp); |
| else |
| mas_push_node(mas, tmp); |
| } |
| |
| /* |
| * mas_topiary_replace() - Replace the data with new data, then repair the |
| * parent links within the new tree. Iterate over the dead sub-tree and collect |
| * the dead subtrees and topiary the nodes that are no longer of use. |
| * |
| * The new tree will have up to three children with the correct parent. Keep |
| * track of the new entries as they need to be followed to find the next level |
| * of new entries. |
| * |
| * The old tree will have up to three children with the old parent. Keep track |
| * of the old entries as they may have more nodes below replaced. Nodes within |
| * [index, last] are dead subtrees, others need to be freed and followed. |
| * |
| * @mas: The maple state pointing at the new data |
| * @old_enode: The maple encoded node being replaced |
| * |
| */ |
| static inline void mas_topiary_replace(struct ma_state *mas, |
| struct maple_enode *old_enode) |
| { |
| struct ma_state tmp[3], tmp_next[3]; |
| MA_TOPIARY(subtrees, mas->tree); |
| bool in_rcu; |
| int i, n; |
| |
| /* Place data in tree & then mark node as old */ |
| mas_put_in_tree(mas, old_enode); |
| |
| /* Update the parent pointers in the tree */ |
| tmp[0] = *mas; |
| tmp[0].offset = 0; |
| tmp[1].status = ma_none; |
| tmp[2].status = ma_none; |
| while (!mte_is_leaf(tmp[0].node)) { |
| n = 0; |
| for (i = 0; i < 3; i++) { |
| if (mas_is_none(&tmp[i])) |
| continue; |
| |
| while (n < 3) { |
| if (!mas_find_child(&tmp[i], &tmp_next[n])) |
| break; |
| n++; |
| } |
| |
| mas_adopt_children(&tmp[i], tmp[i].node); |
| } |
| |
| if (MAS_WARN_ON(mas, n == 0)) |
| break; |
| |
| while (n < 3) |
| tmp_next[n++].status = ma_none; |
| |
| for (i = 0; i < 3; i++) |
| tmp[i] = tmp_next[i]; |
| } |
| |
| /* Collect the old nodes that need to be discarded */ |
| if (mte_is_leaf(old_enode)) |
| return mas_free(mas, old_enode); |
| |
| tmp[0] = *mas; |
| tmp[0].offset = 0; |
| tmp[0].node = old_enode; |
| tmp[1].status = ma_none; |
| tmp[2].status = ma_none; |
| in_rcu = mt_in_rcu(mas->tree); |
| do { |
| n = 0; |
| for (i = 0; i < 3; i++) { |
| if (mas_is_none(&tmp[i])) |
| continue; |
| |
| while (n < 3) { |
| if (!mas_find_child(&tmp[i], &tmp_next[n])) |
| break; |
| |
| if ((tmp_next[n].min >= tmp_next->index) && |
| (tmp_next[n].max <= tmp_next->last)) { |
| mat_add(&subtrees, tmp_next[n].node); |
| tmp_next[n].status = ma_none; |
| } else { |
| n++; |
| } |
| } |
| } |
| |
| if (MAS_WARN_ON(mas, n == 0)) |
| break; |
| |
| while (n < 3) |
| tmp_next[n++].status = ma_none; |
| |
| for (i = 0; i < 3; i++) { |
| mas_topiary_node(mas, &tmp[i], in_rcu); |
| tmp[i] = tmp_next[i]; |
| } |
| } while (!mte_is_leaf(tmp[0].node)); |
| |
| for (i = 0; i < 3; i++) |
| mas_topiary_node(mas, &tmp[i], in_rcu); |
| |
| mas_mat_destroy(mas, &subtrees); |
| } |
| |
| /* |
| * mas_wmb_replace() - Write memory barrier and replace |
| * @mas: The maple state |
| * @old: The old maple encoded node that is being replaced. |
| * |
| * Updates gap as necessary. |
| */ |
| static inline void mas_wmb_replace(struct ma_state *mas, |
| struct maple_enode *old_enode) |
| { |
| /* Insert the new data in the tree */ |
| mas_topiary_replace(mas, old_enode); |
| |
| if (mte_is_leaf(mas->node)) |
| return; |
| |
| mas_update_gap(mas); |
| } |
| |
| /* |
| * mast_cp_to_nodes() - Copy data out to nodes. |
| * @mast: The maple subtree state |
| * @left: The left encoded maple node |
| * @middle: The middle encoded maple node |
| * @right: The right encoded maple node |
| * @split: The location to split between left and (middle ? middle : right) |
| * @mid_split: The location to split between middle and right. |
| */ |
| static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, |
| struct maple_enode *left, struct maple_enode *middle, |
| struct maple_enode *right, unsigned char split, unsigned char mid_split) |
| { |
| bool new_lmax = true; |
| |
| mas_node_or_none(mast->l, left); |
| mas_node_or_none(mast->m, middle); |
| mas_node_or_none(mast->r, right); |
| |
| mast->l->min = mast->orig_l->min; |
| if (split == mast->bn->b_end) { |
| mast->l->max = mast->orig_r->max; |
| new_lmax = false; |
| } |
| |
| mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax); |
| |
| if (middle) { |
| mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true); |
| mast->m->min = mast->bn->pivot[split] + 1; |
| split = mid_split; |
| } |
| |
| mast->r->max = mast->orig_r->max; |
| if (right) { |
| mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false); |
| mast->r->min = mast->bn->pivot[split] + 1; |
| } |
| } |
| |
| /* |
| * mast_combine_cp_left - Copy in the original left side of the tree into the |
| * combined data set in the maple subtree state big node. |
| * @mast: The maple subtree state |
| */ |
| static inline void mast_combine_cp_left(struct maple_subtree_state *mast) |
| { |
| unsigned char l_slot = mast->orig_l->offset; |
| |
| if (!l_slot) |
| return; |
| |
| mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); |
| } |
| |
| /* |
| * mast_combine_cp_right: Copy in the original right side of the tree into the |
| * combined data set in the maple subtree state big node. |
| * @mast: The maple subtree state |
| */ |
| static inline void mast_combine_cp_right(struct maple_subtree_state *mast) |
| { |
| if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max) |
| return; |
| |
| mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, |
| mt_slot_count(mast->orig_r->node), mast->bn, |
| mast->bn->b_end); |
| mast->orig_r->last = mast->orig_r->max; |
| } |
| |
| /* |
| * mast_sufficient: Check if the maple subtree state has enough data in the big |
| * node to create at least one sufficient node |
| * @mast: the maple subtree state |
| */ |
| static inline bool mast_sufficient(struct maple_subtree_state *mast) |
| { |
| if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) |
| return true; |
| |
| return false; |
| } |
| |
| /* |
| * mast_overflow: Check if there is too much data in the subtree state for a |
| * single node. |
| * @mast: The maple subtree state |
| */ |
| static inline bool mast_overflow(struct maple_subtree_state *mast) |
| { |
| if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) |
| return true; |
| |
| return false; |
| } |
| |
| static inline void *mtree_range_walk(struct ma_state *mas) |
| { |
| unsigned long *pivots; |
| unsigned char offset; |
| struct maple_node *node; |
| struct maple_enode *next, *last; |
| enum maple_type type; |
| void __rcu **slots; |
| unsigned char end; |
| unsigned long max, min; |
| unsigned long prev_max, prev_min; |
| |
| next = mas->node; |
| min = mas->min; |
| max = mas->max; |
| do { |
| last = next; |
| node = mte_to_node(next); |
| type = mte_node_type(next); |
| pivots = ma_pivots(node, type); |
| end = ma_data_end(node, type, pivots, max); |
| prev_min = min; |
| prev_max = max; |
| if (pivots[0] >= mas->index) { |
| offset = 0; |
| max = pivots[0]; |
| goto next; |
| } |
| |
| offset = 1; |
| while (offset < end) { |
| if (pivots[offset] >= mas->index) { |
| max = pivots[offset]; |
| break; |
| } |
| offset++; |
| } |
| |
| min = pivots[offset - 1] + 1; |
| next: |
| slots = ma_slots(node, type); |
| next = mt_slot(mas->tree, slots, offset); |
| if (unlikely(ma_dead_node(node))) |
| goto dead_node; |
| } while (!ma_is_leaf(type)); |
| |
| mas->end = end; |
| mas->offset = offset; |
| mas->index = min; |
| mas->last = max; |
| mas->min = prev_min; |
| mas->max = prev_max; |
| mas->node = last; |
| return (void *)next; |
| |
| dead_node: |
| mas_reset(mas); |
| return NULL; |
| } |
| |
| /* |
| * mas_spanning_rebalance() - Rebalance across two nodes which may not be peers. |
| * @mas: The starting maple state |
| * @mast: The maple_subtree_state, keeps track of 4 maple states. |
| * @count: The estimated count of iterations needed. |
| * |
| * Follow the tree upwards from @l_mas and @r_mas for @count, or until the root |
| * is hit. First @b_node is split into two entries which are inserted into the |
| * next iteration of the loop. @b_node is returned populated with the final |
| * iteration. @mas is used to obtain allocations. orig_l_mas keeps track of the |
| * nodes that will remain active by using orig_l_mas->index and orig_l_mas->last |
| * to account of what has been copied into the new sub-tree. The update of |
| * orig_l_mas->last is used in mas_consume to find the slots that will need to |
| * be either freed or destroyed. orig_l_mas->depth keeps track of the height of |
| * the new sub-tree in case the sub-tree becomes the full tree. |
| * |
| * Return: the number of elements in b_node during the last loop. |
| */ |
| static int mas_spanning_rebalance(struct ma_state *mas, |
| struct maple_subtree_state *mast, unsigned char count) |
| { |
| unsigned char split, mid_split; |
| unsigned char slot = 0; |
| struct maple_enode *left = NULL, *middle = NULL, *right = NULL; |
| struct maple_enode *old_enode; |
| |
| MA_STATE(l_mas, mas->tree, mas->index, mas->index); |
| MA_STATE(r_mas, mas->tree, mas->index, mas->last); |
| MA_STATE(m_mas, mas->tree, mas->index, mas->index); |
| |
| /* |
| * The tree needs to be rebalanced and leaves need to be kept at the same level. |
| * Rebalancing is done by use of the ``struct maple_topiary``. |
| */ |
| mast->l = &l_mas; |
| mast->m = &m_mas; |
| mast->r = &r_mas; |
| l_mas.status = r_mas.status = m_mas.status = ma_none; |
| |
| /* Check if this is not root and has sufficient data. */ |
| if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) && |
| unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) |
| mast_spanning_rebalance(mast); |
| |
| l_mas.depth = 0; |
| |
| /* |
| * Each level of the tree is examined and balanced, pushing data to the left or |
| * right, or rebalancing against left or right nodes is employed to avoid |
| * rippling up the tree to limit the amount of churn. Once a new sub-section of |
| * the tree is created, there may be a mix of new and old nodes. The old nodes |
| * will have the incorrect parent pointers and currently be in two trees: the |
| * original tree and the partially new tree. To remedy the parent pointers in |
| * the old tree, the new data is swapped into the active tree and a walk down |
| * the tree is performed and the parent pointers are updated. |
| * See mas_topiary_replace() for more information. |
| */ |
| while (count--) { |
| mast->bn->b_end--; |
| mast->bn->type = mte_node_type(mast->orig_l->node); |
| split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, |
| &mid_split, mast->orig_l->min); |
| mast_set_split_parents(mast, left, middle, right, split, |
| mid_split); |
| mast_cp_to_nodes(mast, left, middle, right, split, mid_split); |
| |
| /* |
| * Copy data from next level in the tree to mast->bn from next |
| * iteration |
| */ |
| memset(mast->bn, 0, sizeof(struct maple_big_node)); |
| mast->bn->type = mte_node_type(left); |
| l_mas.depth++; |
| |
| /* Root already stored in l->node. */ |
| if (mas_is_root_limits(mast->l)) |
| goto new_root; |
| |
| mast_ascend(mast); |
| mast_combine_cp_left(mast); |
| l_mas.offset = mast->bn->b_end; |
| mab_set_b_end(mast->bn, &l_mas, left); |
| mab_set_b_end(mast->bn, &m_mas, middle); |
| mab_set_b_end(mast->bn, &r_mas, right); |
| |
| /* Copy anything necessary out of the right node. */ |
| mast_combine_cp_right(mast); |
| mast->orig_l->last = mast->orig_l->max; |
| |
| if (mast_sufficient(mast)) |
| continue; |
| |
| if (mast_overflow(mast)) |
| continue; |
| |
| /* May be a new root stored in mast->bn */ |
| if (mas_is_root_limits(mast->orig_l)) |
| break; |
| |
| mast_spanning_rebalance(mast); |
| |
| /* rebalancing from other nodes may require another loop. */ |
| if (!count) |
| count++; |
| } |
| |
| l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), |
| mte_node_type(mast->orig_l->node)); |
| l_mas.depth++; |
| mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); |
| mas_set_parent(mas, left, l_mas.node, slot); |
| if (middle) |
| mas_set_parent(mas, middle, l_mas.node, ++slot); |
| |
| if (right) |
| mas_set_parent(mas, right, l_mas.node, ++slot); |
| |
| if (mas_is_root_limits(mast->l)) { |
| new_root: |
| mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); |
| while (!mte_is_root(mast->orig_l->node)) |
| mast_ascend(mast); |
| } else { |
| mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent; |
| } |
| |
| old_enode = mast->orig_l->node; |
| mas->depth = l_mas.depth; |
| mas->node = l_mas.node; |
| mas->min = l_mas.min; |
| mas->max = l_mas.max; |
| mas->offset = l_mas.offset; |
| mas_wmb_replace(mas, old_enode); |
| mtree_range_walk(mas); |
| return mast->bn->b_end; |
| } |
| |
| /* |
| * mas_rebalance() - Rebalance a given node. |
| * @mas: The maple state |
| * @b_node: The big maple node. |
| * |
| * Rebalance two nodes into a single node or two new nodes that are sufficient. |
| * Continue upwards until tree is sufficient. |
| * |
| * Return: the number of elements in b_node during the last loop. |
| */ |
| static inline int mas_rebalance(struct ma_state *mas, |
| struct maple_big_node *b_node) |
| { |
| char empty_count = mas_mt_height(mas); |
| struct maple_subtree_state mast; |
| unsigned char shift, b_end = ++b_node->b_end; |
| |
| MA_STATE(l_mas, mas->tree, mas->index, mas->last); |
| MA_STATE(r_mas, mas->tree, mas->index, mas->last); |
| |
| trace_ma_op(__func__, mas); |
| |
| /* |
| * Rebalancing occurs if a node is insufficient. Data is rebalanced |
| * against the node to the right if it exists, otherwise the node to the |
| * left of this node is rebalanced against this node. If rebalancing |
| * causes just one node to be produced instead of two, then the parent |
| * is also examined and rebalanced if it is insufficient. Every level |
| * tries to combine the data in the same way. If one node contains the |
| * entire range of the tree, then that node is used as a new root node. |
| */ |
| mas_node_count(mas, empty_count * 2 - 1); |
| if (mas_is_err(mas)) |
| return 0; |
| |
| mast.orig_l = &l_mas; |
| mast.orig_r = &r_mas; |
| mast.bn = b_node; |
| mast.bn->type = mte_node_type(mas->node); |
| |
| l_mas = r_mas = *mas; |
| |
| if (mas_next_sibling(&r_mas)) { |
| mas_mab_cp(&r_mas, 0, mt_slot_count(r_mas.node), b_node, b_end); |
| r_mas.last = r_mas.index = r_mas.max; |
| } else { |
| mas_prev_sibling(&l_mas); |
| shift = mas_data_end(&l_mas) + 1; |
| mab_shift_right(b_node, shift); |
| mas->offset += shift; |
| mas_mab_cp(&l_mas, 0, shift - 1, b_node, 0); |
| b_node->b_end = shift + b_end; |
| l_mas.index = l_mas.last = l_mas.min; |
| } |
| |
| return mas_spanning_rebalance(mas, &mast, empty_count); |
| } |
| |
| /* |
| * mas_destroy_rebalance() - Rebalance left-most node while destroying the maple |
| * state. |
| * @mas: The maple state |
| * @end: The end of the left-most node. |
| * |
| * During a mass-insert event (such as forking), it may be necessary to |
| * rebalance the left-most node when it is not sufficient. |
| */ |
| static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end) |
| { |
| enum maple_type mt = mte_node_type(mas->node); |
| struct maple_node reuse, *newnode, *parent, *new_left, *left, *node; |
| struct maple_enode *eparent, *old_eparent; |
| unsigned char offset, tmp, split = mt_slots[mt] / 2; |
| void __rcu **l_slots, **slots; |
| unsigned long *l_pivs, *pivs, gap; |
| bool in_rcu = mt_in_rcu(mas->tree); |
| |
| MA_STATE(l_mas, mas->tree, mas->index, mas->last); |
| |
| l_mas = *mas; |
| mas_prev_sibling(&l_mas); |
| |
| /* set up node. */ |
| if (in_rcu) { |
| /* Allocate for both left and right as well as parent. */ |
| mas_node_count(mas, 3); |
| if (mas_is_err(mas)) |
| return; |
| |
| newnode = mas_pop_node(mas); |
| } else { |
| newnode = &reuse; |
| } |
| |
| node = mas_mn(mas); |
| newnode->parent = node->parent; |
| slots = ma_slots(newnode, mt); |
| pivs = ma_pivots(newnode, mt); |
| left = mas_mn(&l_mas); |
| l_slots = ma_slots(left, mt); |
| l_pivs = ma_pivots(left, mt); |
| if (!l_slots[split]) |
| split++; |
| tmp = mas_data_end(&l_mas) - split; |
| |
| memcpy(slots, l_slots + split + 1, sizeof(void *) * tmp); |
| memcpy(pivs, l_pivs + split + 1, sizeof(unsigned long) * tmp); |
| pivs[tmp] = l_mas.max; |
| memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); |
| memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); |
| |
| l_mas.max = l_pivs[split]; |
| mas->min = l_mas.max + 1; |
| old_eparent = mt_mk_node(mte_parent(l_mas.node), |
| mas_parent_type(&l_mas, l_mas.node)); |
| tmp += end; |
| if (!in_rcu) { |
| unsigned char max_p = mt_pivots[mt]; |
| unsigned char max_s = mt_slots[mt]; |
| |
| if (tmp < max_p) |
| memset(pivs + tmp, 0, |
| sizeof(unsigned long) * (max_p - tmp)); |
| |
| if (tmp < mt_slots[mt]) |
| memset(slots + tmp, 0, sizeof(void *) * (max_s - tmp)); |
| |
| memcpy(node, newnode, sizeof(struct maple_node)); |
| ma_set_meta(node, mt, 0, tmp - 1); |
| mte_set_pivot(old_eparent, mte_parent_slot(l_mas.node), |
| l_pivs[split]); |
| |
| /* Remove data from l_pivs. */ |
| tmp = split + 1; |
| memset(l_pivs + tmp, 0, sizeof(unsigned long) * (max_p - tmp)); |
| memset(l_slots + tmp, 0, sizeof(void *) * (max_s - tmp)); |
| ma_set_meta(left, mt, 0, split); |
| eparent = old_eparent; |
| |
| goto done; |
| } |
| |
| /* RCU requires replacing both l_mas, mas, and parent. */ |
| mas->node = mt_mk_node(newnode, mt); |
| ma_set_meta(newnode, mt, 0, tmp); |
| |
| new_left = mas_pop_node(mas); |
| new_left->parent = left->parent; |
| mt = mte_node_type(l_mas.node); |
| slots = ma_slots(new_left, mt); |
| pivs = ma_pivots(new_left, mt); |
| memcpy(slots, l_slots, sizeof(void *) * split); |
| memcpy(pivs, l_pivs, sizeof(unsigned long) * split); |
| ma_set_meta(new_left, mt, 0, split); |
| l_mas.node = mt_mk_node(new_left, mt); |
| |
| /* replace parent. */ |
| offset = mte_parent_slot(mas->node); |
| mt = mas_parent_type(&l_mas, l_mas.node); |
| parent = mas_pop_node(mas); |
| slots = ma_slots(parent, mt); |
| pivs = ma_pivots(parent, mt); |
| memcpy(parent, mte_to_node(old_eparent), sizeof(struct maple_node)); |
| rcu_assign_pointer(slots[offset], mas->node); |
| rcu_assign_pointer(slots[offset - 1], l_mas.node); |
| pivs[offset - 1] = l_mas.max; |
| eparent = mt_mk_node(parent, mt); |
| done: |
| gap = mas_leaf_max_gap(mas); |
| mte_set_gap(eparent, mte_parent_slot(mas->node), gap); |
| gap = mas_leaf_max_gap(&l_mas); |
| mte_set_gap(eparent, mte_parent_slot(l_mas.node), gap); |
| mas_ascend(mas); |
| |
| if (in_rcu) { |
| mas_replace_node(mas, old_eparent); |
| mas_adopt_children(mas, mas->node); |
| } |
| |
| mas_update_gap(mas); |
| } |
| |
| /* |
| * mas_split_final_node() - Split the final node in a subtree operation. |
| * @mast: the maple subtree state |
| * @mas: The maple state |
| * @height: The height of the tree in case it's a new root. |
| */ |
| static inline void mas_split_final_node(struct maple_subtree_state *mast, |
| struct ma_state *mas, int height) |
| { |
| struct maple_enode *ancestor; |
|