From 923a4599192bf8b6cceb2453ec51e7ba503169b9 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 19 Jan 2021 10:38:07 -0500 Subject: [PATCH] maple_tree: More comments Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 131 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 119 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9185f6c42b4bb..cc86a13848be4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5255,9 +5255,13 @@ EXPORT_SYMBOL_GPL(mas_next); /* * mas_erase() - Find the range in which index resides and erase the entire * range. + * @mas: The maple state + * + * Must hold the write lock. + * Searches for @mas->index, sets @mas->index and @mas->last to the range and + * erases that range. * - * Any previous pivots with no value will be set to the same pivot value. - * Return: the entry that was erased + * Return: the entry that was erased, @mas->index and @mas->last are updated. */ static inline void *mas_erase(struct ma_state *mas) { @@ -5276,6 +5280,16 @@ retry: return entry; } +/* + * mas_dead_leaves() - Mark all leaves of a node as dead. + * @mas: The maple state + * @*slots: Pointer to the slot array + * + * Internal function. + * Must hold the write lock. + * + * Return: The number of leaves marked as dead. + */ static inline unsigned char mas_dead_leaves(struct ma_state *mas, void **slots) { struct maple_node *node; @@ -5293,6 +5307,17 @@ static inline unsigned char mas_dead_leaves(struct ma_state *mas, void **slots) return offset; } +/* + * mas_destroy_descend() - Descend until one level before the leaves. + * @mas: The maple state + * + * Internal Function. + * Must hold the write lock. + * Used to walk down the left side of the tree during a destroy operation. + * + * Return: Pointer to the slot array of the left most node one level above the + * leave nodes. + */ static inline void **mas_destroy_descend(struct ma_state *mas) { void **slots = ma_slots(mte_to_node(mas->node), @@ -5308,10 +5333,11 @@ static inline void **mas_destroy_descend(struct ma_state *mas) /* * mt_destroy_walk() - Free this the node and all nodes in this sub-tree. - * - * Walk all nodes from the start node and bulk free/ free the all nodes. - * * @head: The rcu_head of the starting node. + * + * Must hold the write lock. + * Walk all nodes from the start node and frees all nodes with use of the bulk + * free where possible. */ static void mt_destroy_walk(struct rcu_head *head) { @@ -5354,10 +5380,11 @@ free_leaf: } /* - * mte_destroy_walk() - Free the sub-tree from @mn and below. - * + * mte_destroy_walk() - Free a tree or sub-tree. * @enode - the encoded maple node (maple_enode) to start * @mn - the tree to free - needed for node types. + * + * Must hold the write lock. */ static inline void mte_destroy_walk(struct maple_enode *enode, struct maple_tree *mt) @@ -5382,6 +5409,11 @@ void __init maple_tree_init(void) SLAB_PANIC, NULL); } +/* + * mtree_init() - Initialize a maple tree. + * @mt: The maple tree + * @ma_flags: The flags to use for the tree. + */ void mtree_init(struct maple_tree *mt, unsigned int ma_flags) { spin_lock_init(&mt->ma_lock); @@ -5390,6 +5422,13 @@ void mtree_init(struct maple_tree *mt, unsigned int ma_flags) } EXPORT_SYMBOL(mtree_init); +/* + * mtree_load() - Load a value stored in a maple tree + * @mt: The maple tree + * @index: The index to load + * + * Return: the entry of %NULL + */ void *mtree_load(struct maple_tree *mt, unsigned long index) { void *entry; @@ -5406,6 +5445,17 @@ void *mtree_load(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_load); +/* + * mtree_store_range() - Store an entry at a given range. + * @mt: The maple tree + * @index: The start of the range + * @last: The end of the range + * @entry: The entry to store + * @gfp: The GFP_FLAGS to use for allocations + * + * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not + * be allocated. + */ int mtree_store_range(struct maple_tree *mt, unsigned long index, unsigned long last, void *entry, gfp_t gfp) { @@ -5432,6 +5482,16 @@ retry: } EXPORT_SYMBOL(mtree_store_range); +/* + * mtree_store() - Store an entry at a given index. + * @mt: The maple tree + * @index: The index to store the value + * @entry: The entry to store + * @gfp: The GFP_FLAGS to use for allocations + * + * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not + * be allocated. + */ int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp) { @@ -5439,6 +5499,17 @@ int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, } EXPORT_SYMBOL(mtree_store); +/* + * mtree_insert_range() - Insert an entry at a give range if there is no value. + * @mt: The maple tree + * @first: The start of the range + * @last: The end of the range + * @entry: The entry to store + * @gfp: The FGP_FLAGS to use for allocations. + * + * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not + * be allocated. + */ int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp) { @@ -5463,7 +5534,17 @@ retry: return 0; } EXPORT_SYMBOL(mtree_insert_range); -int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, + +/* + * mtree_insert() - Insert an entry at a give index if there is no value. + * @mt: The maple tree + * @index : The index to store the value + * @entry: The entry to store + * @gfp: The FGP_FLAGS to use for allocations. + * + * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not + * be allocated. + */int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp) { return mtree_insert_range(mt, index, index, entry, gfp); @@ -5537,6 +5618,13 @@ retry: return ret; } +/* + * mtree_erase() - Find an index and erase the entire range. + * @mt: The maple tree + * @index: The index to erase + * + * Return: The entry stored at the @index or %NULL + */ void *mtree_erase(struct maple_tree *mt, unsigned long index) { void *entry = NULL; @@ -5552,6 +5640,12 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mtree_destroy() - Destroy a maple tree + * @mt: The maple tree + * + * Frees all resources used by the tree. + */ void mtree_destroy(struct maple_tree *mt) { mtree_lock(mt); @@ -5592,6 +5686,15 @@ void *mas_store(struct ma_state *mas, void *entry) return existing; } +/* + * mas_store_gfp() - Store a value into the tree. + * @mas: The maple state + * @entry: The entry to store + * @gfp: The GFP_FLAGS to use for allocations if necessary. + * + * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not + * be allocated. + */ int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp) { @@ -5617,7 +5720,6 @@ retry: /* * mas_entry_count() - Set the expected number of entries that will be inserted. - * * @mas: The maple state * @nr_entries: The number of expected entries. * @@ -5625,6 +5727,8 @@ retry: * of entries. The allocations will occur using the bulk allocator interface * for speed. Please call mas_destroy() on the @mas after inserting the entries * to ensure any unused nodes are freed. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. */ int mas_entry_count(struct ma_state *mas, unsigned long nr_entries) { @@ -5664,7 +5768,6 @@ int mas_entry_count(struct ma_state *mas, unsigned long nr_entries) * @mas: The maple state * * Frees any allocated nodes associated with this maple state. - * */ void mas_destroy(struct ma_state *mas) { @@ -5701,8 +5804,12 @@ void mas_destroy(struct ma_state *mas) } /* - * Check if there was an error allocating and do the allocation if necessary - * If there are allocations, then free them. + * mas_nomem() - * Check if there was an error allocating and do the allocation + * if necessary If there are allocations, then free them. + * @mas: The maple state + * @gfp: The GFP_FALGS to use for allocations + * + * Internal function */ bool mas_nomem(struct ma_state *mas, gfp_t gfp) __must_hold(mas->tree->lock) -- 2.50.1