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-next>] [day] [month] [year] [list]
Message-Id: <20240805100109.14367-1-rgbi3307@gmail.com>
Date: Mon,  5 Aug 2024 19:01:09 +0900
From: JaeJoon Jung <rgbi3307@...il.com>
To: 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>
Cc: JaeJoon Jung <rgbi3307@...il.com>,
	linux-kernel@...r.kernel.org,
	linux-mm@...ck.org,
	maple-tree@...ts.infradead.org,
	linux-fsdevel@...r.kernel.org
Subject: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash Tree

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

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