node_set_mark(node, offset, mark);			if (child)				node_mark_slots(child, sibs, mark);		}		if (mark == XA_MARK_MAX)			break;		mark_inc(mark);	}} static void __xas_init_node_for_split(struct xa_state *xas,		struct xa_node *node, void *entry){	unsigned int i;	void *sibling = NULL;	unsigned int mask = xas->xa_sibs; 	if (!node)		return;	node->array = xas->xa;	for (i = 0; i < XA_CHUNK_SIZE; i++) {		if ((i & mask) == 0) {			RCU_INIT_POINTER(node->slots[i], entry);			sibling = xa_mk_sibling(i);		} else {			RCU_INIT_POINTER(node->slots[i], sibling);		}	}} /** * xas_split_alloc() - Allocate memory for splitting an entry. * @xas: XArray operation state. * @entry: New entry which will be stored in the array. * @order: Current entry order. * @gfp: Memory allocation flags. * * This function should be called before calling xas_split(). * If necessary, it will allocate new nodes (and fill them with @entry) * to prepare for the upcoming split of an entry of @order size into * entries of the order stored in the @xas. * * Context: May sleep if @gfp flags permit. */void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order,		gfp_t gfp){	unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1; 	/* XXX: no support for splitting really large entries yet */	if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT <= order))		goto nomem;	if (xas->xa_shift + XA_CHUNK_SHIFT > order)		return; 	do {		struct xa_node *node; 		node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);		if (!node)			goto nomem; 		__xas_init_node_for_split(xas, node, entry);		RCU_INIT_POINTER(node->parent, xas->xa_alloc);		xas->xa_alloc = node;	} while (sibs-- > 0); 	return;nomem:	xas_destroy(xas);	xas_set_err(xas, -ENOMEM);}EXPORT_SYMBOL_GPL(xas_split_alloc); /** * xas_split() - Split a multi-index entry into smaller entries. * @xas: XArray operation state. * @entry: New entry to store in the array. * @order: Current entry order. * * The size of the new entries is set in @xas.  The value in @entry is * copied to all the replacement entries. * * Context: Any context.  The caller should hold the xa_lock. */void xas_split(struct xa_state *xas, void *entry, unsigned int order){	unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;	unsigned int offset, marks;	struct xa_node *node;	void *curr = xas_load(xas);	int values = 0; 	node = xas->xa_node;	if (xas_top(node))		return; 	marks = node_get_marks(node, xas->xa_offset); 	offset = xas->xa_offset + sibs;	do {		if (xas->xa_shift < node->shift) {			struct xa_node *child = xas->xa_alloc; 			xas->xa_alloc = rcu_dereference_raw(child->parent);			child->shift = node->shift - XA_CHUNK_SHIFT;			child->offset = offset;			child->count = XA_CHUNK_SIZE;			child->nr_values = xa_is_value(entry) ?					XA_CHUNK_SIZE : 0;			RCU_INIT_POINTER(child->parent, node);			node_set_marks(node, offset, child, xas->xa_sibs,					marks);			rcu_assign_pointer(node->slots[offset],					xa_mk_node(child));			if (xa_is_value(curr))				values--;			xas_update(xas, child);		} else {			unsigned int canon = offset - xas->xa_sibs; 			node_set_marks(node, canon, NULL, 0, marks);			rcu_assign_pointer(node->slots[canon], entry);			while (offset > canon)				rcu_assign_pointer(node->slots[offset--],						xa_mk_sibling(canon));			values += (xa_is_value(entry) - xa_is_value(curr)) *					(xas->xa_sibs + 1);		}	} while (offset-- > xas->xa_offset); 	node->nr_values += values;	xas_update(xas, node);}EXPORT_SYMBOL_GPL(xas_split); /** * xas_try_split_min_order() - Minimal split order xas_try_split() can accept * @order: Current entry order. * * xas_try_split() can split a multi-index entry to smaller than @order - 1 if * no new xa_node is needed. This function provides the minimal order * xas_try_split() supports. * * Return: the minimal order xas_try_split() supports * * Context: Any context. * */unsigned int xas_try_split_min_order(unsigned int order){	if (order % XA_CHUNK_SHIFT == 0)		return order == 0 ? 0 : order - 1; 	return order - (order % XA_CHUNK_SHIFT);}EXPORT_SYMBOL_GPL(xas_try_split_min_order); /** * xas_try_split() - Try to split a multi-index entry. * @xas: XArray operation state. * @entry: New entry to store in the array. * @order: Current entry order. * * The size of the new entries is set in @xas.  The value in @entry is * copied to all the replacement entries. If and only if one new xa_node is * needed, the function will use GFP_NOWAIT to get one if xas->xa_alloc is * NULL. If more new xa_node are needed, the function gives EINVAL error. * * NOTE: use xas_try_split_min_order() to get next split order instead of * @order - 1 if you want to minmize xas_try_split() calls. * * Context: Any context.  The caller should hold the xa_lock. */void xas_try_split(struct xa_state *xas, void *entry, unsigned int order){	unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;	unsigned int offset, marks;	struct xa_node *node;	void *curr = xas_load(xas);	int values = 0;	gfp_t gfp = GFP_NOWAIT; 	node = xas->xa_node;	if (xas_top(node))		return; 	if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)		gfp |= __GFP_ACCOUNT; 	marks = node_get_marks(node, xas->xa_offset); 	offset = xas->xa_offset + sibs; 	if (xas->xa_shift < node->shift) {		struct xa_node *child = xas->xa_alloc;		unsigned int expected_sibs =			(1 << ((order - 1) % XA_CHUNK_SHIFT)) - 1; 		/*		 * No support for splitting sibling entries		 * (horizontally) or cascade split (vertically), which		 * requires two or more new xa_nodes.		 * Since if one xa_node allocation fails,		 * it is hard to free the prior allocations.		 */		if (sibs || xas->xa_sibs != expected_sibs) {			xas_destroy(xas);			xas_set_err(xas, -EINVAL);			return;		} 		if (!child) {			child = kmem_cache_alloc_lru(radix_tree_node_cachep,						     xas->xa_lru, gfp);			if (!child) {				xas_destroy(xas);				xas_set_err(xas, -ENOMEM);				return;			}			RCU_INIT_POINTER(child->parent, xas->xa_alloc);		}		__xas_init_node_for_split(xas, child, entry); 		xas->xa_alloc = rcu_dereference_raw(child->parent);		child->shift = node->shift - XA_CHUNK_SHIFT;		child->offset = offset;		child->count = XA_CHUNK_SIZE;		child->nr_values = xa_is_value(entry) ?				XA_CHUNK_SIZE : 0;		RCU_INIT_POINTER(child->parent, node);		node_set_marks(node, offset, child, xas->xa_sibs,				marks);		rcu_assign_pointer(node->slots[offset],				xa_mk_node(child));		if (xa_is_value(curr))			values--;		xas_update(xas, child); 	} else {		do {			unsigned int canon = offset - xas->xa_sibs; 			node_set_marks(node, canon, NULL, 0, marks);			rcu_assign_pointer(node->slots[canon], entry);			while (offset > canon)				rcu_assign_pointer(node->slots[offset--],						xa_mk_sibling(canon));			values += (xa_is_value(entry) - xa_is_value(curr)) *					(xas->xa_sibs + 1);		} while (offset-- > xas->xa_offset);	} 	node->nr_values += values;	xas_update(xas, node);}EXPORT_SYMBOL_GPL(xas_try_split);#endif /** * xas_pause() - Pause a walk to drop a lock. * @xas: XArray operation state. * * Some users need to pause a walk and drop the lock they're holding in * order to yield to a higher priority thread or carry out an operation * on an entry.  Those users should call this function before they drop * the lock.  It resets the @xas to be suitable for the next iteration * of the loop after the user has reacquired the lock.  If most entries * found during a walk require you to call xas_pause(), the xa_for_each() * iterator may be more appropriate. * * Note that xas_pause() only works for forward iteration.  If a user needs * to pause a reverse iteration, we will need a xas_pause_rev(). */void xas_pause(struct xa_state *xas){	struct xa_node *node = xas->xa_node; 	if (xas_invalid(xas))		return; 	xas->xa_node = XAS_RESTART;	if (node) {		unsigned long offset = xas->xa_offset;		while (++offset < XA_CHUNK_SIZE) {			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))				break;		}		xas->xa_index &= ~0UL << node->shift;		xas->xa_index += (offset - xas->xa_offset) << node->shift;		if (xas->xa_index == 0)			xas->xa_node = XAS_BOUNDS;	} else {		xas->xa_index++;	}}EXPORT_SYMBOL_GPL(xas_pause); /* * __xas_prev() - Find the previous entry in the XArray. * @xas: XArray operation state. * * Helper function for xas_prev() which handles all the complex cases * out of line. */void *__xas_prev(struct xa_state *xas){	void *entry; 	if (!xas_frozen(xas->xa_node))		xas->xa_index--;	if (!xas->xa_node)		return set_bounds(xas);	if (xas_not_node(xas->xa_node))		return xas_load(xas); 	if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))		xas->xa_offset--; 	while (xas->xa_offset == 255) {		xas->xa_offset = xas->xa_node->offset - 1;		xas->xa_node = xa_parent(xas->xa, xas->xa_node);		if (!xas->xa_node)			return set_bounds(xas);	} 	for (;;) {		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);		if (!xa_is_node(entry))			return entry; 		xas->xa_node = xa_to_node(entry);		xas_set_offset(xas);	}}EXPORT_SYMBOL_GPL(__xas_prev); /* * __xas_next() - Find the next entry in the XArray. * @xas: XArray operation state. * * Helper function for xas_next() which handles all the complex cases * out of line. */void *__xas_next(struct xa_state *xas){	void *entry; 	if (!xas_frozen(xas->xa_node))		xas->xa_index++;	if (!xas->xa_node)		return set_bounds(xas);	if (xas_not_node(xas->xa_node))		return xas_load(xas); 	if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))		xas->xa_offset++; 	while (xas->xa_offset == XA_CHUNK_SIZE) {		xas->xa_offset = xas->xa_node->offset + 1;		xas->xa_node = xa_parent(xas->xa, xas->xa_node);		if (!xas->xa_node)			return set_bounds(xas);	} 	for (;;) {		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);		if (!xa_is_node(entry))			return entry; 		xas->xa_node = xa_to_node(entry);		xas_set_offset(xas);	}}EXPORT_SYMBOL_GPL(__xas_next); /** * xas_find() - Find the next present entry in the XArray. * @xas: XArray operation state. * @max: Highest index to return. * * If the @xas has not yet been walked to an entry, return the entry * which has an index >= xas.xa_index.  If it has been walked, the entry * currently being pointed at has been processed, and so we move to the * next entry. * * If no entry is found and the array is smaller than @max, the iterator * is set to the smallest index not yet in the array.  This allows @xas * to be immediately passed to xas_store(). * * Return: The entry, if found, otherwise %NULL. */void *xas_find(struct xa_state *xas, unsigned long max){	void *entry; 	if (xas_error(xas) || xas->xa_node == XAS_BOUNDS)		return NULL;	if (xas->xa_index > max)		return set_bounds(xas); 	if (!xas->xa_node) {		xas->xa_index = 1;		return set_bounds(xas);	} else if (xas->xa_node == XAS_RESTART) {		entry = xas_load(xas);		if (entry || xas_not_node(xas->xa_node))			return entry;	} else if (!xas->xa_node->shift &&		    xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) {		xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1;	} 	xas_next_offset(xas); 	while (xas->xa_node && (xas->xa_index <= max)) {		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {			xas->xa_offset = xas->xa_node->offset + 1;			xas->xa_node = xa_parent(xas->xa, xas->xa_node);			continue;		} 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);		if (xa_is_node(entry)) {			xas->xa_node = xa_to_node(entry);			xas->xa_offset = 0;			continue;		}		if (entry && !xa_is_sibling(entry))			return entry; 		xas_next_offset(xas);	} 	if (!xas->xa_node)		xas->xa_node = XAS_BOUNDS;	return NULL;}EXPORT_SYMBOL_GPL(xas_find); /** * xas_find_marked() - Find the next marked entry in the XArray. * @xas: XArray operation state. * @max: Highest index to return. * @mark: Mark number to search for. * * If the @xas has not yet been walked to an entry, return the marked entry * which has an index >= xas.xa_index.  If it has been walked, the entry * currently being pointed at has been processed, and so we return the * first marked entry with an index > xas.xa_index. * * If no marked entry is found and the array is smaller than @max, @xas is * set to the bounds state and xas->xa_index is set to the smallest index * not yet in the array.  This allows @xas to be immediately passed to * xas_store(). * * If no entry is found before @max is reached, @xas is set to the restart * state. * * Return: The entry, if found, otherwise %NULL. */void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark){	bool advance = true;	unsigned int offset;	void *entry; 	if (xas_error(xas))		return NULL;	if (xas->xa_index > max)		goto max; 	if (!xas->xa_node) {		xas->xa_index = 1;		goto out;	} else if (xas_top(xas->xa_node)) {		advance = false;		entry = xa_head(xas->xa);		xas->xa_node = NULL;		if (xas->xa_index > max_index(entry))			goto out;		if (!xa_is_node(entry)) {			if (xa_marked(xas->xa, mark))				return entry;			xas->xa_index = 1;			goto out;		}		xas->xa_node = xa_to_node(entry);		xas->xa_offset = xas->xa_index >> xas->xa_node->shift;	} 	while (xas->xa_index <= max) {		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {			xas->xa_offset = xas->xa_node->offset + 1;			xas->xa_node = xa_parent(xas->xa, xas->xa_node);			if (!xas->xa_node)				break;			advance = false;			continue;		}

Lines 1001–1500 of 2481. Previous lines Load more