On Mon, Aug 05, 2024 at 07:01:09PM +0900, JaeJoon Jung wrote: > Implementation of new Hash Tree [PATCH v2] > ------------------------------------------ > Add spinlock.h and rcupdate.h in the include/linux/htree.h > Add htree_root structue to interface locking. > htree_root.ht_lock is spinlock_t to run spin_lock. > htree_root.ht_first is __rcu type to access rcu API. > Access the kernel standard API using macros. > > full source: > ------------ > https://github.com/kernel-bz/htree.git > > Manual(PDF): > ------------ > https://github.com/kernel-bz/htree/blob/main/docs/htree-20240802.pdf How does this compare to rhashtable or willy's rosebush? --D > Signed-off-by: JaeJoon Jung <rgbi3307@xxxxxxxxx> > --- > include/linux/htree.h | 117 ++++++++++++++++++++++++++- > lib/htree-test.c | 182 ++++++++++++++++++++++-------------------- > lib/htree.c | 29 ++++++- > 3 files changed, 238 insertions(+), 90 deletions(-) > > diff --git a/include/linux/htree.h b/include/linux/htree.h > index c7b10c5b9bf2..c5bc2858e7fd 100644 > --- a/include/linux/htree.h > +++ b/include/linux/htree.h > @@ -15,6 +15,8 @@ > #include <linux/hash.h> > #include <linux/hashtable.h> > #include <linux/slab.h> > +#include <linux/spinlock.h> > +#include <linux/rcupdate.h> > > /* > size of one hash tree struct: [16]Bytes > @@ -112,6 +114,17 @@ enum ht_flags { /* htf: htree working flags (keep order) */ > htf_freed, > }; > > +struct htree_root { /* root: hash tree root */ > + spinlock_t ht_lock; /* lock while update */ > + struct hash_tree __rcu *ht_first; /* start of the hash tree */ > +}; > + > +#define DEFINE_HTREE_ROOT(name) \ > + struct htree_root name = { \ > + .ht_lock = __SPIN_LOCK_UNLOCKED(name.ht_lock), \ > + .ht_first = NULL, \ > + } > + > #define HTREE_BITS_START 8 /* start of hash bits(default) */ > #define HTREE_BITS_END 3 /* end of hash bits */ > #define HTREE_BITS_SHIFT 3 /* shift of hash bits */ > @@ -235,7 +248,7 @@ struct htree_data *ht_insert(struct htree_state *hts, struct hash_tree *htree, > struct htree_data *ht_erase(struct htree_state *hts, > struct hash_tree *htree, u64 index); > > -enum ht_flags ht_destroy(struct htree_state *hts, struct hash_tree *htree); > +enum ht_flags ht_destroy_lock(struct htree_state *hts, struct htree_root *root); > > void ht_statis(struct htree_state *hts, struct hash_tree *htree, > s32 *acnt, u64 *dcnt); > @@ -243,5 +256,107 @@ void ht_statis(struct htree_state *hts, struct hash_tree *htree, > struct htree_data *ht_most_index(struct htree_state *hts, > struct hash_tree *htree); > > +/* spin_lock API */ > +#define ht_trylock(xa) spin_trylock(&(xa)->ht_lock) > +#define ht_lock(xa) spin_lock(&(xa)->ht_lock) > +#define ht_unlock(xa) spin_unlock(&(xa)->ht_lock) > +#define ht_lock_bh(xa) spin_lock_bh(&(xa)->ht_lock) > +#define ht_unlock_bh(xa) spin_unlock_bh(&(xa)->ht_lock) > +#define ht_lock_irq(xa) spin_lock_irq(&(xa)->ht_lock) > +#define ht_unlock_irq(xa) spin_unlock_irq(&(xa)->ht_lock) > +#define ht_lock_irqsave(xa, flags) \ > + spin_lock_irqsave(&(xa)->ht_lock, flags) > +#define ht_unlock_irqrestore(xa, flags) \ > + spin_unlock_irqrestore(&(xa)->ht_lock, flags) > +#define ht_lock_nested(xa, subclass) \ > + spin_lock_nested(&(xa)->ht_lock, subclass) > +#define ht_lock_bh_nested(xa, subclass) \ > + spin_lock_bh_nested(&(xa)->ht_lock, subclass) > +#define ht_lock_irq_nested(xa, subclass) \ > + spin_lock_irq_nested(&(xa)->ht_lock, subclass) > +#define ht_lock_irqsave_nested(xa, flags, subclass) \ > + spin_lock_irqsave_nested(&(xa)->ht_lock, flags, subclass) > + > + > +static inline void htree_root_alloc(struct htree_state *hts, > + struct htree_root *root) > +{ > + rcu_assign_pointer(root->ht_first, ht_table_alloc(hts)); > +} > + > +static inline struct hash_tree *htree_first_rcu(const struct htree_root *root) > +{ > + return rcu_dereference_check(root->ht_first, > + lockdep_is_held(&root->ht_lock)); > +} > + > +static inline struct hash_tree *htree_first_rcu_locked(const struct htree_root *root) > +{ > + return rcu_dereference_protected(root->ht_first, > + lockdep_is_held(&root->ht_lock)); > +} > + > + > +static inline __must_check struct htree_data *ht_insert_lock( > + struct htree_state *hts, struct htree_root *root, > + struct htree_data *hdata, enum ht_flags req) > +{ > + ht_lock(root); > + hdata = ht_insert(hts, htree_first_rcu_locked(root), hdata, req); > + ht_unlock(root); > + return hdata; > +} > + > +static inline __must_check struct htree_data *ht_insert_lock_irq( > + struct htree_state *hts, struct htree_root *root, > + struct htree_data *hdata, enum ht_flags req) > +{ > + ht_lock_irq(root); > + hdata = ht_insert(hts, htree_first_rcu_locked(root), hdata, req); > + ht_unlock_irq(root); > + return hdata; > +} > + > +static inline __must_check struct htree_data *ht_insert_lock_irqsave( > + struct htree_state *hts, struct htree_root *root, > + struct htree_data *hdata, enum ht_flags req) > +{ > + unsigned long flags; > + ht_lock_irqsave(root, flags); > + hdata = ht_insert(hts, htree_first_rcu_locked(root), hdata, req); > + ht_unlock_irqrestore(root, flags); > + return hdata; > +} > + > +static inline __must_check struct htree_data *ht_erase_lock( > + struct htree_state *hts, struct htree_root *root, u64 index) > +{ > + struct htree_data *hdata; > + ht_lock(root); > + hdata = ht_erase(hts, htree_first_rcu_locked(root), index); > + ht_unlock(root); > + return hdata; > +} > + > +static inline __must_check struct htree_data *ht_erase_lock_irq( > + struct htree_state *hts, struct htree_root *root, u64 index) > +{ > + struct htree_data *hdata; > + ht_lock_irq(root); > + hdata = ht_erase(hts, htree_first_rcu_locked(root), index); > + ht_unlock_irq(root); > + return hdata; > +} > + > +static inline __must_check struct htree_data *ht_erase_lock_irqsave( > + struct htree_state *hts, struct htree_root *root, u64 index) > +{ > + unsigned long flags; > + struct htree_data *hdata; > + ht_lock_irqsave(root, flags); > + hdata = ht_erase(hts, htree_first_rcu_locked(root), index); > + ht_unlock_irqrestore(root, flags); > + return hdata; > +} > > #endif /* _LINUX_HTREE_H */ > diff --git a/lib/htree-test.c b/lib/htree-test.c > index 05b60da271de..5bf862706ce2 100644 > --- a/lib/htree-test.c > +++ b/lib/htree-test.c > @@ -1,6 +1,6 @@ > // SPDX-License-Identifier: GPL-2.0-only > /* > - * htree/htree-api.c > + * htree/htree-test.c > * Hash-Trees test codes to verify > * > * Copyright(C) 2024, JaeJoon Jung <rgbi3307@xxxxxxxxx> > @@ -17,28 +17,30 @@ > Hash Tree API flow > ------------------ > > - *hts = ht_hts_alloc() //alloc hts > - ht_hts_clear_init(hts, ...) > + DEFINE_HTREE_ROOT(ht_root); //define htree_root > > - *htree = ht_table_alloc(hts) //alloc first(depth:0) htree > + *hts = ht_hts_alloc(); //alloc hts > + ht_hts_clear_init(hts, ...); > + > + htree_root_alloc(hts, &ht_root); //alloc first hash tree > > run_loop() { > > - *udata = _data_alloc(index) //alloc udata > + *udata = _data_alloc(index); //alloc udata > > - ht_insert(hts, htree, udata->hdata, ..) > - ht_erase(hts, htree, index) > - hdata = ht_find(hts, htree, index) > - hdata = ht_most_index(hts, htree) > + ht_insert_lock(hts, &ht_root, udata->hdata, ..); > + ht_erase_lock(hts, &ht_root, index); > + hdata = ht_find(hts, ht_root.ht_first, index); > + hdata = ht_most_index(hts, ht_root.ht_first); > > - ht_statis(hts, htree, ...) > + ht_statis(hts, ht_root.ht_first, ...); > } > > - htree_erase_all(hts, htree) //remove all udata > + htree_erase_all_lock(hts, &ht_root) //remove all udata > > - ht_destroy(hts, htree) //remove all htree > + ht_destroy_lock(hts, &ht_root) //remove all htree > > - kfree(hts) //remove hts > + kfree(hts) //remove hts > */ > > > @@ -75,6 +77,8 @@ > > #define HTREE_TEST_SCHED_CNT 200 > > +DEFINE_HTREE_ROOT(ht_root); > + > struct data_struct { > /* user defined data members ... */ > char a; > @@ -361,19 +365,19 @@ static void __htree_debug_walks_all(struct htree_state *hts, > /** > * htree_walks_all_debug - display to debug all indexes > * @hts: htree_state pointer > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > * @index: index to find > * > * this function cycles through all hash tables and outputs all indexes. > */ > static void htree_debug_walks_all(struct htree_state *hts, > - struct hash_tree *htree, u64 index) > + struct htree_root *root, u64 index) > { > pr_ht_debug("[@@@@) walking: sbit:%u, dmax:%u, acnt:%d, dcnt:%llu\n\n", > hts->sbit, hts->dmax, hts->acnt, hts->dcnt); > > hts->dept = 0; > - __htree_debug_walks_all(hts, htree, index); > + __htree_debug_walks_all(hts, htree_first_rcu(root), index); > > pr_ht_debug("(@@@@] done: sbit:%u, dmax:%u, acnt:%d, dcnt:%llu\n\n", > hts->sbit, hts->dmax, hts->acnt, hts->dcnt); > @@ -381,14 +385,14 @@ static void htree_debug_walks_all(struct htree_state *hts, > #endif /* HTREE_DEBUG_DETAIL */ > > /** > - * __htree_erase_all - erase udata all > + * __htree_erase_all_lock - erase udata all > * @hts: htree_state pointer > * @htree: hash_tree root pointer > * @erased: erased udata count > * > * this function cycles through all hash tables and erase udata all > */ > -static void __htree_erase_all(struct htree_state *hts, > +static void __htree_erase_all_lock(struct htree_state *hts, > struct hash_tree *htree, u64 *erased) > { > u8 bits, ncnt; > @@ -421,7 +425,7 @@ static void __htree_erase_all(struct htree_state *hts, > hts->dept++; > pnum = anum; > /* recursive call */ > - __htree_erase_all(hts, _next, erased); > + __htree_erase_all_lock(hts, _next, erased); > anum = pnum; > hts->dept--; > } else { > @@ -431,13 +435,13 @@ static void __htree_erase_all(struct htree_state *hts, > } > > /** > - * htree_erase_all - erase udata all > + * htree_erase_all_lock - erase udata all > * @hts: htree_state pointer > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > * > * return: erased all udata count > */ > -static u64 htree_erase_all(struct htree_state *hts, struct hash_tree *htree) > +static u64 htree_erase_all_lock(struct htree_state *hts, struct htree_root *root) > { > u64 erased = 0; > > @@ -445,7 +449,10 @@ static u64 htree_erase_all(struct htree_state *hts, struct hash_tree *htree) > hts->sbit, hts->dmax, hts->acnt, hts->dcnt); > > hts->dept = 0; > - __htree_erase_all(hts, htree, &erased); > + > + ht_lock(root); > + __htree_erase_all_lock(hts, htree_first_rcu_locked(root), &erased); > + ht_unlock(root); > > pr_ht_info("(~~~~] done: sbit:%u, acnt:%d, dcnt:%llu, erased:%llu\n\n", > hts->sbit, hts->acnt, hts->dcnt, erased); > @@ -456,7 +463,7 @@ static u64 htree_erase_all(struct htree_state *hts, struct hash_tree *htree) > /** > * _htree_insert_range - insert udata to hash tree using ht_insert() > * @hts: htree_state pointer > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > * @start: start index to insert > * @end: end index to insert > * @gap: gap between indices > @@ -466,7 +473,7 @@ static u64 htree_erase_all(struct htree_state *hts, struct hash_tree *htree) > * if req is htf_ins, the new udata is inserted next to each other. > * if req is htf_erase, the new udata is inserted, and old udata is erased. > */ > -static u64 _htree_insert_range(struct htree_state *hts, struct hash_tree *htree, > +static u64 _htree_insert_range(struct htree_state *hts, struct htree_root *root, > u64 start, u64 end, u64 gap, enum ht_flags req) > { > u64 index; > @@ -478,7 +485,7 @@ static u64 _htree_insert_range(struct htree_state *hts, struct hash_tree *htree, > start, end, gap); > for (index = start; index <= end; index += gap) { > udata = _htree_data_alloc(index); > - rdata = ht_insert(hts, htree, &udata->hdata, req); > + rdata = ht_insert_lock(hts, root, &udata->hdata, req); > if (req == htf_erase && rdata) { > udata = hlist_entry_safe(rdata, struct data_struct, hdata); > if (udata && rdata->index == index) { > @@ -500,12 +507,12 @@ static u64 _htree_insert_range(struct htree_state *hts, struct hash_tree *htree, > /** > * _htree_find_range - find udata in the hash tree using ht_find() > * @hts: htree_state pointer > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > * @start: start index to find > * @end: end index to find > * @gap: gap between indices > */ > -static u64 _htree_find_range(struct htree_state *hts, struct hash_tree *htree, > +static u64 _htree_find_range(struct htree_state *hts, struct htree_root *root, > u64 start, u64 end, u64 gap) > { > u64 index; > @@ -516,7 +523,7 @@ static u64 _htree_find_range(struct htree_state *hts, struct hash_tree *htree, > pr_ht_info("[****) finding: [s:%llu ... e:%llu] (g:%llu)\n", > start, end, gap); > for (index = start; index <= end; index += gap) { > - rdata = ht_find(hts, htree, index); > + rdata = ht_find(hts, htree_first_rcu(root), index); > if (rdata) { > udata = hlist_entry_safe(rdata, struct data_struct, hdata); > if (udata && rdata->index == index) { > @@ -525,6 +532,7 @@ static u64 _htree_find_range(struct htree_state *hts, struct hash_tree *htree, > found++; > } > } > + > loop++; > if (!(loop % HTREE_TEST_SCHED_CNT)) > schedule(); > @@ -537,23 +545,25 @@ static u64 _htree_find_range(struct htree_state *hts, struct hash_tree *htree, > /** > * _htree_erase_range - erase udata from hash tree using ht_erase() > * @hts: htree_state pointer > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > * @start: start index to erase > * @end: end index to erase > * @gap: gap between indices > */ > -static u64 _htree_erase_range(struct htree_state *hts, struct hash_tree *htree, > +static u64 _htree_erase_range(struct htree_state *hts, struct htree_root *root, > u64 start, u64 end, u64 gap) > { > u64 index; > u64 loop = 0, erased = 0; > + struct hash_tree *htree; > struct data_struct *udata; > struct htree_data *rdata; > > pr_ht_info("[----) erasing: [s:%llu ... e:%llu] (g:%llu)\n", > start, end, gap); > for (index = start; index <= end; index += gap) { > - rdata = ht_erase(hts, htree, index); > + htree = htree_first_rcu(root); > + rdata = ht_erase_lock(hts, root, index); > if (rdata) { > udata = hlist_entry_safe(rdata, struct data_struct, hdata); > if (udata && rdata->index == index) { > @@ -580,22 +590,24 @@ static u64 _htree_erase_range(struct htree_state *hts, struct hash_tree *htree, > /** > * _htree_update_range - update udata in the hash tree using ft_find() > * @hts: htree_state pointer > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > * @start: start index to update > * @end: end index to update > * @gap: gap between indices > */ > -static u64 _htree_update_range(struct htree_state *hts, struct hash_tree *htree, > +static u64 _htree_update_range(struct htree_state *hts, struct htree_root *root, > u64 start, u64 end, u64 gap) > { > u64 index; > u64 loop = 0, updated = 0; > + struct hash_tree *htree; > struct data_struct *udata; > struct htree_data *rdata; > > pr_ht_info("[####) updating: [s:%llu ... e:%llu] (g:%llu)\n", > start, end, gap); > for (index = start; index <= end; index += gap) { > + htree = htree_first_rcu(root); > rdata = ht_find(hts, htree, index); > if (rdata) { > udata = hlist_entry_safe(rdata, struct data_struct, hdata); > @@ -630,14 +642,14 @@ static u64 _htree_update_range(struct htree_state *hts, struct hash_tree *htree, > /** > * _htree_statis - calculate hash tree statistics and get into hts. > * @hts: htree_state pointer to store statistics > - * @htree: hash_tree root pointer > + * @root: hash_tree root pointer > */ > -static void _htree_statis(struct htree_state *hts, struct hash_tree *htree) > +static void _htree_statis(struct htree_state *hts, struct htree_root *root) > { > s32 acnt = 0; > u64 dcnt = 0; > > - ht_statis(hts, htree, &acnt, &dcnt); > + ht_statis(hts, htree_first_rcu(root), &acnt, &dcnt); > > if (hts->dcnt == dcnt && hts->acnt == acnt) { > pr_ht_info("[ OK ] statist: acnt:%d, dcnt:%llu ", acnt, dcnt); > @@ -651,8 +663,10 @@ static void _htree_statis(struct htree_state *hts, struct hash_tree *htree) > > /** > * _htree_statis_info - shows information calculated by htree_statis(). > + * @hts: htree_state pointer to read statistics > + * @root: hash_tree root pointer > */ > -static void _htree_statis_info(struct htree_state *hts, struct hash_tree *htree) > +static void _htree_statis_info(struct htree_state *hts, struct htree_root *root) > { > u32 sizh = sizeof(struct hash_tree); > u32 sizd = sizeof(struct data_struct); > @@ -663,7 +677,7 @@ static void _htree_statis_info(struct htree_state *hts, struct hash_tree *htree) > u64 smem = hsum + dsum; > > if (hts->asum == 0) > - _htree_statis(hts, htree); > + _htree_statis(hts, root); > > pr_ht_stat("------------------------------------------\n"); > pr_ht_stat(" hash start bits(sbit) : %10d\n", hts->sbit); > @@ -692,10 +706,11 @@ static void _htree_statis_info(struct htree_state *hts, struct hash_tree *htree) > * if sort flag is HTREE_FLAG_ASCD, root hash table has the smallest index. > * if sort flag is HTREE_FLAG_DECD, root hash table has the largest index. > */ > -static void _htree_get_most_index(struct htree_state *hts, struct hash_tree *htree) > +static void _htree_get_most_index(struct htree_state *hts, struct htree_root *root) > { > struct htree_data *hdata; > - hdata = ht_most_index(hts, htree); > + > + hdata = ht_most_index(hts, htree_first_rcu(root)); > if (hdata) { > if (hts->sort == HTREE_FLAG_ASCD) { > pr_ht_stat("[MOST] smallest index:%llu\n\n", hdata->index); > @@ -708,20 +723,20 @@ static void _htree_get_most_index(struct htree_state *hts, struct hash_tree *htr > /** > * _htree_remove_all - remove all udata and hash trees > * > - * before run ht_destroy(), the udata must be erased all. > - * ht_destroy() removes all hash trees, but it does not remove the udata. > + * before run ht_destroy_lock(), the udata must be erased all. > + * ht_destroy_lock() removes all hash trees, but it does not remove the udata. > */ > -static void _htree_remove_all(struct htree_state *hts, struct hash_tree *htree) > +static void _htree_remove_all(struct htree_state *hts, struct htree_root *root) > { > /* remove all udata */ > - hts->dcnt -= htree_erase_all(hts, htree); > + hts->dcnt -= htree_erase_all_lock(hts, root); > if (hts->dcnt != 0) { > pr_ht_warn("[WARN] erase remained acnt:%d, dcnt:%llu\n\n", > hts->acnt, hts->dcnt); > } > > /* remove all hash trees */ > - if (ht_destroy(hts, htree) == htf_ok) { > + if (ht_destroy_lock(hts, root) == htf_ok) { > pr_ht_stat("[ OK ] destroy remained acnt:%d, dcnt:%llu\n\n", > hts->acnt, hts->dcnt); > } else { > @@ -743,7 +758,6 @@ static void _htree_remove_all(struct htree_state *hts, struct hash_tree *htree) > */ > static u64 _htree_test_index_loop(struct htree_state *hts, u64 start, u64 end) > { > - struct hash_tree *htree; > u64 inserted, found, erased, updated; > u64 dcnt, slice; > > @@ -752,42 +766,42 @@ static u64 _htree_test_index_loop(struct htree_state *hts, u64 start, u64 end) > slice = (end - start) / 10 + 2; > > /* first root hash tree alloc */ > - htree = ht_table_alloc(hts); > + htree_root_alloc(hts, &ht_root); > > - inserted = _htree_insert_range(hts, htree, start, end, 1, htf_ins); > + inserted = _htree_insert_range(hts, &ht_root, start, end, 1, htf_ins); > if (inserted != hts->dcnt) { > pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", > inserted, hts->dcnt, inserted - hts->dcnt); > } > > - _htree_statis(hts, htree); > + _htree_statis(hts, &ht_root); > > - erased = _htree_erase_range(hts, htree, start, end, slice); > - found = _htree_find_range(hts, htree, start, end, slice); > + erased = _htree_erase_range(hts, &ht_root, start, end, slice); > + found = _htree_find_range(hts, &ht_root, start, end, slice); > if (found) { > pr_ht_err("[FAIL] erased:%llu, found:%llu, diff:%lld\n\n", > erased, found, erased - found); > } > > - _htree_statis(hts, htree); > + _htree_statis(hts, &ht_root); > > - inserted = _htree_insert_range(hts, htree, start, end, slice, htf_ins); > - updated = _htree_update_range(hts, htree, start, end, slice); > + inserted = _htree_insert_range(hts, &ht_root, start, end, slice, htf_ins); > + updated = _htree_update_range(hts, &ht_root, start, end, slice); > if (inserted != updated) { > pr_ht_err("[FAIL] inserted:%llu, updated:%llu, diff:%lld\n\n", > inserted, updated, inserted - updated); > } > > - _htree_statis(hts, htree); > - _htree_get_most_index(hts, htree); > + _htree_statis(hts, &ht_root); > + _htree_get_most_index(hts, &ht_root); > > #ifdef HTREE_DEBUG_DETAIL > - htree_debug_walks_all(hts, htree, 0); > + htree_debug_walks_all(hts, &ht_root, 0); > #endif > - _htree_statis_info(hts, htree); > + _htree_statis_info(hts, &ht_root); > dcnt = hts->dcnt; > > - _htree_remove_all(hts, htree); > + _htree_remove_all(hts, &ht_root); > > return dcnt; > } > @@ -872,7 +886,6 @@ index type:<%s>, sorting type:<%s>\n", idxts[idx_type], sorts[sort_type]); > static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > { > u64 i, index; > - struct hash_tree *htree; > struct data_struct *udata; > struct htree_data *rdata; > u64 loop = 0, inserted = 0, erased = 0; > @@ -886,13 +899,13 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > ht_hts_clear_init(hts, maxnr, idx_type, sort_type); > > /* first root hash tree alloc */ > - htree = ht_table_alloc(hts); > + htree_root_alloc(hts, &ht_root); > > pr_ht_stat("[START) RANDOM: sbit:%u, index type:<%s>, sorting type:<%s>\n\n", > hts->sbit, idxts[idx_type], sorts[sort_type]); > > udata = _htree_data_alloc(check_idx); > - rdata = ht_insert(hts, htree, &udata->hdata, htf_ins); > + rdata = ht_insert_lock(hts, &ht_root, &udata->hdata, htf_ins); > inserted++; > loop++; > > @@ -902,7 +915,7 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > get_random_u32() : get_random_u64(); > > udata = _htree_data_alloc(index); > - rdata = ht_insert(hts, htree, &udata->hdata, htf_ins); > + rdata = ht_insert_lock(hts, &ht_root, &udata->hdata, htf_ins); > if (!rdata) > inserted++; > loop++; > @@ -910,9 +923,9 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > schedule(); > } > > - _htree_statis(hts, htree); > + _htree_statis(hts, &ht_root); > > - rdata = ht_find(hts, htree, check_idx); > + rdata = ht_find(hts, htree_first_rcu(&ht_root), check_idx); > if (!rdata) { > pr_ht_err("[FAIL] NOT found check index:%llu\n\n", check_idx); > } > @@ -923,7 +936,7 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > index = (idx_type == HTREE_FLAG_IDX32) ? > get_random_u32() : get_random_u64(); > > - rdata = ht_erase(hts, htree, index); > + rdata = ht_erase_lock(hts, &ht_root, index); > if (rdata) { > udata = hlist_entry_safe(rdata, struct data_struct, hdata); > if (udata && rdata->index == index) { > @@ -938,9 +951,9 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > schedule(); > } > > - _htree_statis(hts, htree); > + _htree_statis(hts, &ht_root); > > - rdata = ht_find(hts, htree, check_idx); > + rdata = ht_find(hts, htree_first_rcu(&ht_root), check_idx); > if (!rdata) { > pr_ht_info("[INFO] check index:%llu (erased)\n\n", check_idx); > } > @@ -949,13 +962,13 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > loop, inserted, erased); > > #ifdef HTREE_DEBUG_DETAIL > - htree_debug_walks_all(hts, htree, 0); > + htree_debug_walks_all(hts, &ht_root, 0); > #endif > > - _htree_get_most_index(hts, htree); > - _htree_statis_info(hts, htree); > + _htree_get_most_index(hts, &ht_root); > + _htree_statis_info(hts, &ht_root); > > - _htree_remove_all(hts, htree); > + _htree_remove_all(hts, &ht_root); > > kfree(hts); > } > @@ -975,7 +988,6 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) > */ > static void _htree_test_index_same(u8 idx_type, u8 sort_type, u64 maxnr) > { > - struct hash_tree *htree; > u64 inserted, found; > const char *idxts[] = { "64bits", "32bits" }; > const char *sorts[] = { "ASCD", "DECD" }; > @@ -987,49 +999,49 @@ static void _htree_test_index_same(u8 idx_type, u8 sort_type, u64 maxnr) > ht_hts_clear_init(hts, maxnr, idx_type, sort_type); > > /* first root hash tree alloc */ > - htree = ht_table_alloc(hts); > + htree_root_alloc(hts, &ht_root); > > pr_ht_stat("[START) SAME: sbit:%u, index type:<%s>, sorting type:<%s>\n\n", > hts->sbit, idxts[idx_type], sorts[sort_type]); > > pr_ht_stat("[loop) %llu: new index inserting(htf_ins)\n\n", maxnr); > - inserted = _htree_insert_range(hts, htree, 0, maxnr, gap - 1, htf_ins); > + inserted = _htree_insert_range(hts, &ht_root, 0, maxnr, gap - 1, htf_ins); > if (inserted != hts->dcnt) { > pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", > inserted, hts->dcnt, inserted - hts->dcnt); > } > > - _htree_statis(hts, htree); > + _htree_statis(hts, &ht_root); > > pr_ht_stat("[loop) %llu: SAME index inserting(htf_erase)\n\n", maxnr); > - inserted = _htree_insert_range(hts, htree, 1, maxnr, gap, htf_erase); > + inserted = _htree_insert_range(hts, &ht_root, 1, maxnr, gap, htf_erase); > if (inserted != 0) { > pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", > inserted, hts->dcnt, inserted - hts->dcnt); > } > > pr_ht_stat("[loop) %llu: SAME index inserting(htf_ins)\n\n", maxnr); > - inserted = _htree_insert_range(hts, htree, 1, maxnr, gap, htf_ins); > + inserted = _htree_insert_range(hts, &ht_root, 1, maxnr, gap, htf_ins); > if (inserted != (maxnr / gap)) { > pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", > inserted, hts->dcnt, inserted - hts->dcnt); > } > > - found = _htree_find_range(hts, htree, 0, maxnr, gap - 1); > + found = _htree_find_range(hts, &ht_root, 0, maxnr, gap - 1); > if (found != (hts->dcnt - inserted)) { > pr_ht_err("[FAIL] dcnt:%llu, inserted:%llu, found:%llu\n\n", > hts->dcnt, inserted, found); > } > > - _htree_statis(hts, htree); > + _htree_statis(hts, &ht_root); > > #ifdef HTREE_DEBUG_DETAIL > - htree_debug_walks_all(hts, htree, 0); > + htree_debug_walks_all(hts, &ht_root, 0); > #endif > - _htree_get_most_index(hts, htree); > - _htree_statis_info(hts, htree); > + _htree_get_most_index(hts, &ht_root); > + _htree_statis_info(hts, &ht_root); > > - _htree_remove_all(hts, htree); > + _htree_remove_all(hts, &ht_root); > > kfree(hts); > } > diff --git a/lib/htree.c b/lib/htree.c > index be7b34b5d4e1..1fcdb8d69730 100644 > --- a/lib/htree.c > +++ b/lib/htree.c > @@ -180,6 +180,9 @@ struct htree_data *ht_find(struct htree_state *hts, > struct htree_data *rdata = NULL; > struct hash_tree *rtree; > > + if (!htree) > + return NULL; > + > if (_ht_find(hts, htree, index, &rdata, &rtree) == htf_find) > return rdata; > return NULL; > @@ -345,6 +348,9 @@ struct htree_data *ht_insert(struct htree_state *hts, struct hash_tree *htree, > struct hash_tree *rtree = NULL; > enum ht_flags htf; > > + if (!htree) > + return NULL; > + > htf = _ht_find(hts, htree, hdata->index, &rdata, &rtree); > > _ht_insert(hts, rtree, rdata, hdata, htf, req); > @@ -478,6 +484,9 @@ struct htree_data *ht_erase(struct htree_state *hts, > { > struct htree_data *rdata = NULL; > > + if (!htree) > + return NULL; > + > if (_ht_erase(hts, htree, &rdata, index) == htf_erase) > return rdata; > > @@ -533,22 +542,31 @@ static void __ht_free_all(struct htree_state *hts, > } > > /** > - * ht_destroy - public function to free hash tree > + * ht_destroy_lock - public function to free hash tree > * @hts: htree_state pointer > - * @htree: hash_tree pointer(root) > + * @root: htree_tree pointer(root) > * > * this function removes all hash tree, but it does not remove udata. > */ > -enum ht_flags ht_destroy(struct htree_state *hts, struct hash_tree *htree) > +enum ht_flags ht_destroy_lock(struct htree_state *hts, struct htree_root *root) > { > s32 acnt = 0; > u64 dcnt = 0; > + struct hash_tree *htree; > > if (hts->acnt == 0 && hts->dcnt == 0) > return htf_ok; > > + htree = htree_first_rcu(root); > + if (!htree) > + return htf_none; > + > hts->dept = 0; > + > + ht_lock(root); > __ht_free_all(hts, htree, &acnt, &dcnt); > + RCU_INIT_POINTER(root->ht_first, NULL); > + ht_unlock(root); > > hts->acnt -= acnt; > hts->dcnt -= dcnt; > @@ -556,7 +574,7 @@ enum ht_flags ht_destroy(struct htree_state *hts, struct hash_tree *htree) > return (hts->dept == 0 && hts->dcnt == 0 && hts->acnt == 0) ? > htf_ok : htf_none; > } > -EXPORT_SYMBOL(ht_destroy); > +EXPORT_SYMBOL(ht_destroy_lock); > > /** > * __ht_statis - private function to call recursively to calculate nodes > @@ -613,6 +631,9 @@ void ht_statis(struct htree_state *hts, > hts->dept = 0; > hts->dmax = 0; > > + if (!htree) > + return; > + > __ht_statis(hts, htree, acnt, dcnt); > } > EXPORT_SYMBOL(ht_statis); > -- > 2.17.1 > >
