// SPDX-License-Identifier: GPL-2.0+/* * XArray implementation * Copyright (c) 2017-2018 Microsoft Corporation * Copyright (c) 2018-2020 Oracle * Author: Matthew Wilcox <willy@infradead.org> */ #include <linux/bitmap.h>#include <linux/export.h>#include <linux/list.h>#include <linux/slab.h>#include <linux/xarray.h> #include "radix-tree.h" /* * Coding conventions in this file: * * @xa is used to refer to the entire xarray. * @xas is the 'xarray operation state'.  It may be either a pointer to * an xa_state, or an xa_state stored on the stack.  This is an unfortunate * ambiguity. * @index is the index of the entry being operated on * @mark is an xa_mark_t; a small number indicating one of the mark bits. * @node refers to an xa_node; usually the primary one being operated on by * this function. * @offset is the index into the slots array inside an xa_node. * @parent refers to the @xa_node closer to the head than @node. * @entry refers to something stored in a slot in the xarray */ static inline unsigned int xa_lock_type(const struct xarray *xa){	return (__force unsigned int)xa->xa_flags & 3;} static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type){	if (lock_type == XA_LOCK_IRQ)		xas_lock_irq(xas);	else if (lock_type == XA_LOCK_BH)		xas_lock_bh(xas);	else		xas_lock(xas);} static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type){	if (lock_type == XA_LOCK_IRQ)		xas_unlock_irq(xas);	else if (lock_type == XA_LOCK_BH)		xas_unlock_bh(xas);	else		xas_unlock(xas);} static inline bool xa_track_free(const struct xarray *xa){	return xa->xa_flags & XA_FLAGS_TRACK_FREE;} static inline bool xa_zero_busy(const struct xarray *xa){	return xa->xa_flags & XA_FLAGS_ZERO_BUSY;} static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark){	if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))		xa->xa_flags |= XA_FLAGS_MARK(mark);} static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark){	if (xa->xa_flags & XA_FLAGS_MARK(mark))		xa->xa_flags &= ~(XA_FLAGS_MARK(mark));} static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark){	return node->marks[(__force unsigned)mark];} static inline bool node_get_mark(struct xa_node *node,		unsigned int offset, xa_mark_t mark){	return test_bit(offset, node_marks(node, mark));} /* returns true if the bit was set */static inline bool node_set_mark(struct xa_node *node, unsigned int offset,				xa_mark_t mark){	return __test_and_set_bit(offset, node_marks(node, mark));} /* returns true if the bit was set */static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,				xa_mark_t mark){	return __test_and_clear_bit(offset, node_marks(node, mark));} static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark){	return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);} static inline void node_mark_all(struct xa_node *node, xa_mark_t mark){	bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);} #define mark_inc(mark) do { \	mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \} while (0) /* * xas_squash_marks() - Merge all marks to the first entry * @xas: Array operation state. * * Set a mark on the first entry if any entry has it set.  Clear marks on * all sibling entries. */static void xas_squash_marks(const struct xa_state *xas){	xa_mark_t mark = 0;	unsigned int limit = xas->xa_offset + xas->xa_sibs + 1; 	for (;;) {		unsigned long *marks = node_marks(xas->xa_node, mark); 		if (find_next_bit(marks, limit, xas->xa_offset + 1) != limit) {			__set_bit(xas->xa_offset, marks);			bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);		}		if (mark == XA_MARK_MAX)			break;		mark_inc(mark);	}} /* extracts the offset within this node from the index */static unsigned int get_offset(unsigned long index, struct xa_node *node){	return (index >> node->shift) & XA_CHUNK_MASK;} static void xas_set_offset(struct xa_state *xas){	xas->xa_offset = get_offset(xas->xa_index, xas->xa_node);} /* move the index either forwards (find) or backwards (sibling slot) */static void xas_move_index(struct xa_state *xas, unsigned long offset){	unsigned int shift = xas->xa_node->shift;	xas->xa_index &= ~XA_CHUNK_MASK << shift;	xas->xa_index += offset << shift;} static void xas_next_offset(struct xa_state *xas){	xas->xa_offset++;	xas_move_index(xas, xas->xa_offset);} static void *set_bounds(struct xa_state *xas){	xas->xa_node = XAS_BOUNDS;	return NULL;} /* * Starts a walk.  If the @xas is already valid, we assume that it's on * the right path and just return where we've got to.  If we're in an * error state, return NULL.  If the index is outside the current scope * of the xarray, return NULL without changing @xas->xa_node.  Otherwise * set @xas->xa_node to NULL and return the current head of the array. */static void *xas_start(struct xa_state *xas){	void *entry; 	if (xas_valid(xas))		return xas_reload(xas);	if (xas_error(xas))		return NULL; 	entry = xa_head(xas->xa);	if (!xa_is_node(entry)) {		if (xas->xa_index)			return set_bounds(xas);	} else {		if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)			return set_bounds(xas);	} 	xas->xa_node = NULL;	return entry;} static __always_inline void *xas_descend(struct xa_state *xas,					struct xa_node *node){	unsigned int offset = get_offset(xas->xa_index, node);	void *entry = xa_entry(xas->xa, node, offset); 	xas->xa_node = node;	while (xa_is_sibling(entry)) {		offset = xa_to_sibling(entry);		entry = xa_entry(xas->xa, node, offset);		if (node->shift && xa_is_node(entry))			entry = XA_RETRY_ENTRY;	} 	xas->xa_offset = offset;	return entry;} /** * xas_load() - Load an entry from the XArray (advanced). * @xas: XArray operation state. * * Usually walks the @xas to the appropriate state to load the entry * stored at xa_index.  However, it will do nothing and return %NULL if * @xas is in an error state.  xas_load() will never expand the tree. * * If the xa_state is set up to operate on a multi-index entry, xas_load() * may return %NULL or an internal entry, even if there are entries * present within the range specified by @xas. * * Context: Any context.  The caller should hold the xa_lock or the RCU lock. * Return: Usually an entry in the XArray, but see description for exceptions. */void *xas_load(struct xa_state *xas){	void *entry = xas_start(xas); 	while (xa_is_node(entry)) {		struct xa_node *node = xa_to_node(entry); 		if (xas->xa_shift > node->shift)			break;		entry = xas_descend(xas, node);		if (node->shift == 0)			break;	}	return entry;}EXPORT_SYMBOL_GPL(xas_load); #define XA_RCU_FREE	((struct xarray *)1) static void xa_node_free(struct xa_node *node){	XA_NODE_BUG_ON(node, !list_empty(&node->private_list));	node->array = XA_RCU_FREE;	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);} /* * xas_destroy() - Free any resources allocated during the XArray operation. * @xas: XArray operation state. * * Most users will not need to call this function; it is called for you * by xas_nomem(). */void xas_destroy(struct xa_state *xas){	struct xa_node *next, *node = xas->xa_alloc; 	while (node) {		XA_NODE_BUG_ON(node, !list_empty(&node->private_list));		next = rcu_dereference_raw(node->parent);		radix_tree_node_rcu_free(&node->rcu_head);		xas->xa_alloc = node = next;	}}EXPORT_SYMBOL_GPL(xas_destroy); /** * xas_nomem() - Allocate memory if needed. * @xas: XArray operation state. * @gfp: Memory allocation flags. * * If we need to add new nodes to the XArray, we try to allocate memory * with GFP_NOWAIT while holding the lock, which will usually succeed. * If it fails, @xas is flagged as needing memory to continue.  The caller * should drop the lock and call xas_nomem().  If xas_nomem() succeeds, * the caller should retry the operation. * * Forward progress is guaranteed as one node is allocated here and * stored in the xa_state where it will be found by xas_alloc().  More * nodes will likely be found in the slab allocator, but we do not tie * them up here. * * Return: true if memory was needed, and was successfully allocated. */bool xas_nomem(struct xa_state *xas, gfp_t gfp){	if (xas->xa_node != XA_ERROR(-ENOMEM)) {		xas_destroy(xas);		return false;	}	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)		gfp |= __GFP_ACCOUNT;	xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);	if (!xas->xa_alloc)		return false;	xas->xa_alloc->parent = NULL;	XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));	xas->xa_node = XAS_RESTART;	return true;}EXPORT_SYMBOL_GPL(xas_nomem); /* * __xas_nomem() - Drop locks and allocate memory if needed. * @xas: XArray operation state. * @gfp: Memory allocation flags. * * Internal variant of xas_nomem(). * * Return: true if memory was needed, and was successfully allocated. */static bool __xas_nomem(struct xa_state *xas, gfp_t gfp)	__must_hold(xas->xa->xa_lock){	unsigned int lock_type = xa_lock_type(xas->xa); 	if (xas->xa_node != XA_ERROR(-ENOMEM)) {		xas_destroy(xas);		return false;	}	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)		gfp |= __GFP_ACCOUNT;	if (gfpflags_allow_blocking(gfp)) {		xas_unlock_type(xas, lock_type);		xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);		xas_lock_type(xas, lock_type);	} else {		xas->xa_alloc = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);	}	if (!xas->xa_alloc)		return false;	xas->xa_alloc->parent = NULL;	XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));	xas->xa_node = XAS_RESTART;	return true;} static void xas_update(struct xa_state *xas, struct xa_node *node){	if (xas->xa_update)		xas->xa_update(node);	else		XA_NODE_BUG_ON(node, !list_empty(&node->private_list));} static void *xas_alloc(struct xa_state *xas, unsigned int shift){	struct xa_node *parent = xas->xa_node;	struct xa_node *node = xas->xa_alloc; 	if (xas_invalid(xas))		return NULL; 	if (node) {		xas->xa_alloc = NULL;	} else {		gfp_t gfp = GFP_NOWAIT; 		if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)			gfp |= __GFP_ACCOUNT; 		node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);		if (!node) {			xas_set_err(xas, -ENOMEM);			return NULL;		}	} 	if (parent) {		node->offset = xas->xa_offset;		parent->count++;		XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);		xas_update(xas, parent);	}	XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);	XA_NODE_BUG_ON(node, !list_empty(&node->private_list));	node->shift = shift;	node->count = 0;	node->nr_values = 0;	RCU_INIT_POINTER(node->parent, xas->xa_node);	node->array = xas->xa; 	return node;} #ifdef CONFIG_XARRAY_MULTI/* Returns the number of indices covered by a given xa_state */static unsigned long xas_size(const struct xa_state *xas){	return (xas->xa_sibs + 1UL) << xas->xa_shift;}#endif /* * Use this to calculate the maximum index that will need to be created * in order to add the entry described by @xas.  Because we cannot store a * multi-index entry at index 0, the calculation is a little more complex * than you might expect. */static unsigned long xas_max(struct xa_state *xas){	unsigned long max = xas->xa_index; #ifdef CONFIG_XARRAY_MULTI	if (xas->xa_shift || xas->xa_sibs) {		unsigned long mask = xas_size(xas) - 1;		max |= mask;		if (mask == max)			max++;	}#endif 	return max;} /* The maximum index that can be contained in the array without expanding it */static unsigned long max_index(void *entry){	if (!xa_is_node(entry))		return 0;	return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1;} static inline void *xa_zero_to_null(void *entry){	return xa_is_zero(entry) ? NULL : entry;} static void xas_shrink(struct xa_state *xas){	struct xarray *xa = xas->xa;	struct xa_node *node = xas->xa_node; 	for (;;) {		void *entry; 		XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);		if (node->count != 1)			break;		entry = xa_entry_locked(xa, node, 0);		if (!entry)			break;		if (!xa_is_node(entry) && node->shift)			break;		if (xa_zero_busy(xa))			entry = xa_zero_to_null(entry);		xas->xa_node = XAS_BOUNDS; 		RCU_INIT_POINTER(xa->xa_head, entry);		if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))			xa_mark_clear(xa, XA_FREE_MARK); 		node->count = 0;		node->nr_values = 0;		if (!xa_is_node(entry))			RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);		xas_update(xas, node);		xa_node_free(node);		if (!xa_is_node(entry))			break;		node = xa_to_node(entry);		node->parent = NULL;	}} /* * xas_delete_node() - Attempt to delete an xa_node * @xas: Array operation state. * * Attempts to delete the @xas->xa_node.  This will fail if xa->node has * a non-zero reference count. */static void xas_delete_node(struct xa_state *xas){	struct xa_node *node = xas->xa_node; 	for (;;) {		struct xa_node *parent; 		XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);		if (node->count)			break; 		parent = xa_parent_locked(xas->xa, node);

Lines 1–500 of 2481. Load more