lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20240807011618.GA6043@frogsfrogsfrogs>
Date: Tue, 6 Aug 2024 18:16:18 -0700
From: "Darrick J. Wong" <djwong@...nel.org>
To: JaeJoon Jung <rgbi3307@...il.com>
Cc: Linus Torvalds <torvalds@...ux-foundation.org>,
	Sasha Levin <levinsasha928@...il.com>,
	"Liam R . Howlett" <Liam.Howlett@...cle.com>,
	Matthew Wilcox <willy@...radead.org>,
	Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
	linux-kernel@...r.kernel.org, linux-mm@...ck.org,
	maple-tree@...ts.infradead.org, linux-fsdevel@...r.kernel.org
Subject: Re: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash Tree

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@...il.com>
> ---
>  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@...il.com>
> @@ -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
> 
> 

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ