// 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_TREEstatic 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 inlineenum 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 inlinevoid 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;

Lines 1–500 of 7655. Load more