1 /* SPDX-License-Identifier: GPL-2.0+ */
5  * Maple Tree - An RCU-safe adaptive tree for storing ranges
6  * Copyright (c) 2018-2022 Oracle
17  * Allocated nodes are mutable until they have been inserted into the tree,
19  * from the tree and an RCU grace period has passed.
21  * Removed nodes have their ->parent set to point to themselves.  RCU readers
22  * check ->parent before relying on the value that they loaded from the
25  * Nodes in the tree point to their parent unless bit 0 is set.
29 #define MAPLE_NODE_SLOTS	31	/* 256 bytes including ->parent */
32 #define MAPLE_ALLOC_SLOTS	(MAPLE_NODE_SLOTS - 1)
35 #define MAPLE_NODE_SLOTS	63	/* 256 bytes including ->parent */
38 #define MAPLE_ALLOC_SLOTS	(MAPLE_NODE_SLOTS - 2)
44  * The node->parent of the root node has bit 0 set and the rest of the pointer
45  * is a pointer to the tree itself.  No more bits are available in this pointer
46  * (on m68k, the data structure may only be 2-byte aligned).
48  * Internal non-root nodes can only have maple_range_* nodes as parents.  The
49  * parent pointer is 256B aligned like all other tree nodes.  When storing a 32
52  * bit in the node type.  This is possible by using bit 1 to indicate if bit 2
56  * range type is done by examining the immutable tree flag for the
65  *  Slot size and location in the parent pointer:
68  *   0x?00 : 16 bit values, type in 0-1, slot in 2-6
69  *   0x010 : 32 bit values, type in 0-2, slot in 3-6
70  *   0x110 : 64 bit values, type in 0-2, slot in 3-6
74  * This metadata is used to optimize the gap updating code and in reverse
85  * entry at 0 in the root pointer cannot be done for data which have the bottom
89  * two bits set to '10', and while choosing to store these values in the array
93  * Non-leaf nodes store the type of the node pointed to (enum maple_type in bits
94  * 3-6), bit 2 is reserved.  That leaves bits 0-1 unused for now.
96  * In regular B-Tree terms, pivots are called keys.  The term pivot is used to
97  * indicate that the tree is specifying ranges,  Pivots may appear in the
99  * specific position of a B-tree.  Pivot values are inclusive of the slot with
105 	unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
109 			void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
116  * At tree creation time, the user can specify that they're willing to trade off
117  * storing fewer entries in a tree in return for storing more information in
120  * The maple tree supports recording the largest range of NULL entries available
121  * in this node, also called gaps.  This optimises the tree for allocating a
126 	unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
165  * DOC: Maple tree flags
167  * * MT_FLAGS_ALLOC_RANGE	- Track gaps in this tree
168  * * MT_FLAGS_USE_RCU		- Operate in RCU mode
169  * * MT_FLAGS_HEIGHT_OFFSET	- The position of the tree height in the flags
170  * * MT_FLAGS_HEIGHT_MASK	- The mask for the maple tree height value
171  * * MT_FLAGS_LOCK_MASK		- How the mt_lock is used
172  * * MT_FLAGS_LOCK_IRQ		- Acquired irq-safe
173  * * MT_FLAGS_LOCK_BH		- Acquired bh-safe
174  * * MT_FLAGS_LOCK_EXTERN	- mt_lock is not used
199 	(!(mt)->ma_external_lock || lock_is_held((mt)->ma_external_lock))
202 	(!(mt)->ma_external_lock ||					\
203 	 lock_is_held_type((mt)->ma_external_lock, 0))
206 	(mt)->ma_external_lock = &(lock)->dep_map
218  * If the tree contains a single entry at index 0, it is usually stored in
219  * tree->ma_root.  To optimise for the page cache, an entry which ends in '00',
220  * '01' or '11' is stored in the root, but an entry which ends in '10' will be
221  * stored in a node.  Bits 3-6 are used to store enum maple_type.
223  * The flags are used both to store some immutable information about this tree
224  * (set at tree creation time) and dynamic information set under the spinlock.
226  * Another use of flags are to indicate global states of the tree.  This is the
227  * case with the MT_FLAGS_USE_RCU flag, which indicates the tree is currently in
228  * RCU mode.  This mode was added to allow the tree to reuse nodes instead of
229  * re-allocating and RCU freeing nodes when there is a single user.
241  * MTREE_INIT() - Initialize a maple tree
242  * @name: The maple tree name
243  * @__flags: The maple tree flags
253  * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
254  * @name: The tree name
255  * @__flags: The maple tree flags
271 #define mtree_lock(mt)		spin_lock((&(mt)->ma_lock))
273 		spin_lock_nested((&(mt)->ma_lock), subclass)
274 #define mtree_unlock(mt)	spin_unlock((&(mt)->ma_lock))
277  * The Maple Tree squeezes various bits in at various points which aren't
279  * N-byte aligned and thus the bottom log_2(N) bits are available for use.  We
283  * Nodes are 256 bytes in size and are also aligned to 256 bytes, giving us 8
285  * 1. Single pointer (Range is 0-0)
286  * 2. Non-leaf Allocation Range nodes
287  * 3. Non-leaf Range nodes
315  * potentially alter the height of the tree.  Either half of the tree may need
317  * which nodes have been 'cut' from the tree so that the change can be done
355  * mtree_empty() - Determine if a tree has any present entries.
356  * @mt: Maple Tree.
359  * Return: %true if the tree contains only NULL pointers.
363 	return mt->ma_root == NULL;  in mtree_empty()
371  * continue operating on the tree.
372  * ma_start means we have not searched the tree.
373  * ma_root means we have searched the tree and the entry we found lives in
374  * the root of the tree (ie it has index 0, length 1 and is the only entry in
375  * the tree).
376  * ma_none means we have searched the tree and there is no node in the
377  * tree for this entry.  For example, we searched for index 1 in an empty
378  * tree.  Or we have a tree which points to a full leaf node and we
379  * searched for an entry which is larger than can be contained in that
399  * The maple state is defined in the struct ma_state and is used to keep track
403  * If state->node has bit 0 set then it references a tree location which is not
405  * errno.  Bit 2 (the 'unallocated slots' bit) is clear.  Bits 3-6 indicate the
408  * state->alloc either has a request number of nodes or an allocated node.  If
409  * stat->alloc has a requested number of nodes, the first bit will be set (0x1)
410  * and the remaining bits are the value.  If state->alloc is a node, then the
411  * node will be of type maple_alloc.  maple_alloc has MAPLE_NODE_SLOTS - 1 for
413  * node_count in this node.  node_count is the number of allocated nodes in this
414  * node.  The scaling beyond MAPLE_NODE_SLOTS - 1 is handled by storing further
415  * nodes into state->alloc->slot[0]'s node.  Nodes are taken from state->alloc
416  * by removing a node from the state->alloc node until state->alloc->node_count
417  * is 1, when state->alloc is returned and the state->alloc->slot[0] is promoted
418  * to state->alloc.  Nodes are pushed onto state->alloc by putting the current
419  * state->alloc into the pushed node's slot[0].
421  * The state also contains the implied min/max of the state->node, the depth of
423  * node or are 0-oo for the root node.  The depth is incremented or decremented
425  * interest in the node - either for reading or writing.
428  * the start and end of the range for the entry.  Ranges are inclusive in the
429  * Maple Tree.
433  * should start at the root of the tree and walk down.  If the status is
439 	struct maple_tree *tree;	/* The tree we're operating in */  member
440 	unsigned long index;		/* The index we're operating on - range start */
441 	unsigned long last;		/* The last index we're operating on - range end */
443 	unsigned long min;		/* The minimum index of this node - implied pivot min */
444 	unsigned long max;		/* The maximum index of this node - implied pivot max */
447 	unsigned char depth;		/* depth of tree descent during write */
456 	struct maple_node *node;	/* Decoded mas->node */
459 	enum maple_type type;		/* mas->node type */
461 	unsigned long *pivots;		/* mas->node->pivots pointer */
463 	void __rcu **slots;		/* mas->node->slots pointer */
468 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
470 		spin_lock_nested(&((mas)->tree->ma_lock), subclass)
471 #define mas_unlock(mas)         spin_unlock(&((mas)->tree->ma_lock))
477  * top of the tree as the tree may have been modified.
484 		.tree = mt,						\
503 #define MA_TOPIARY(name, tree)						\  argument
507 		.mtree = tree,						\
544 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,  in mas_init()  argument
548 	mas->tree = tree;  in mas_init()
549 	mas->index = mas->last = addr;  in mas_init()
550 	mas->max = ULONG_MAX;  in mas_init()
551 	mas->status = ma_start;  in mas_init()
552 	mas->node = NULL;  in mas_init()
557 	return mas->status == ma_active;  in mas_is_active()
562 	return mas->status == ma_error;  in mas_is_err()
566  * mas_reset() - Reset a Maple Tree operation state.
567  * @mas: Maple Tree operation state.
577 	mas->status = ma_start;  in mas_reset()
578 	mas->node = NULL;  in mas_reset()
582  * mas_for_each() - Iterate over a range of the maple tree.
583  * @__mas: Maple Tree operation state (maple_state)
584  * @__entry: Entry retrieved from the tree
585  * @__max: maximum index to retrieve from the tree
587  * When returned, mas->index and mas->last will hold the entire range for the
596  * mas_for_each_rev() - Iterate over a range of the maple tree in reverse order.
597  * @__mas: Maple Tree operation state (maple_state)
598  * @__entry: Entry retrieved from the tree
599  * @__min: minimum index to retrieve from the tree
601  * When returned, mas->index and mas->last will hold the entire range for the
644 		mt_dump((__mas)->tree, mt_dump_hex);			\
660 		mas_dump((__wrmas)->mas);				\
661 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
695 		mt_dump((__mas)->tree, mt_dump_hex);			\
713 		mas_dump((__wrmas)->mas);				\
714 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
734  * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
736  * @mas: Maple Tree operation state.
737  * @start: New start of range in the Maple Tree.
738  * @last: New end of range in the Maple Tree.
740  * set the internal maple state values to a sub-range.
741  * Please use mas_set_range() if you do not know where you are in the tree.
748 		   (mas->index > start || mas->last < start));  in __mas_set_range()
749 	mas->index = start;  in __mas_set_range()
750 	mas->last = last;  in __mas_set_range()
754  * mas_set_range() - Set up Maple Tree operation state for a different index.
755  * @mas: Maple Tree operation state.
756  * @start: New start of range in the Maple Tree.
757  * @last: New end of range in the Maple Tree.
771  * mas_set() - Set up Maple Tree operation state for a different index.
772  * @mas: Maple Tree operation state.
773  * @index: New index into the Maple Tree.
787 	return (mt->ma_flags & MT_FLAGS_LOCK_MASK) == MT_FLAGS_LOCK_EXTERN;  in mt_external_lock()
791  * mt_init_flags() - Initialise an empty maple tree with flags.
792  * @mt: Maple Tree
793  * @flags: maple tree flags.
795  * If you need to initialise a Maple Tree with special flags (eg, an
796  * allocation tree), use this function.
802 	mt->ma_flags = flags;  in mt_init_flags()
804 		spin_lock_init(&mt->ma_lock);  in mt_init_flags()
805 	rcu_assign_pointer(mt->ma_root, NULL);  in mt_init_flags()
809  * mt_init() - Initialise an empty maple tree.
810  * @mt: Maple Tree
812  * An empty Maple Tree.
826 	return mt->ma_flags & MT_FLAGS_USE_RCU;  in mt_in_rcu()
830  * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
831  * @mt: The Maple Tree
840 		mt->ma_flags &= ~MT_FLAGS_USE_RCU;  in mt_clear_in_rcu()
843 		mt->ma_flags &= ~MT_FLAGS_USE_RCU;  in mt_clear_in_rcu()
849  * mt_set_in_rcu() - Switch the tree to RCU safe mode.
850  * @mt: The Maple Tree
859 		mt->ma_flags |= MT_FLAGS_USE_RCU;  in mt_set_in_rcu()
862 		mt->ma_flags |= MT_FLAGS_USE_RCU;  in mt_set_in_rcu()
869 	return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET;  in mt_height()
879  * mt_for_each - Iterate over each entry starting at index until max.
880  * @__tree: The Maple Tree