diff mbox series

[v2,1/2] lib/htree: Add locking interface to new Hash Tree

Message ID 20240805100109.14367-1-rgbi3307@gmail.com (mailing list archive)
State New
Headers show
Series [v2,1/2] lib/htree: Add locking interface to new Hash Tree | expand

Commit Message

JaeJoon Jung Aug. 5, 2024, 10:01 a.m. UTC 
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@gmail.com>
---
 include/linux/htree.h | 117 ++++++++++++++++++++++++++-
 lib/htree-test.c      | 182 ++++++++++++++++++++++--------------------
 lib/htree.c           |  29 ++++++-
 3 files changed, 238 insertions(+), 90 deletions(-)

Comments

Greg Kroah-Hartman Aug. 5, 2024, 6:33 p.m. UTC | #1 
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
> 
> Signed-off-by: JaeJoon Jung <rgbi3307@gmail.com>
> ---
>  include/linux/htree.h | 117 ++++++++++++++++++++++++++-
>  lib/htree-test.c      | 182 ++++++++++++++++++++++--------------------
>  lib/htree.c           |  29 ++++++-
>  3 files changed, 238 insertions(+), 90 deletions(-)

Hi,

This is the friendly patch-bot of Greg Kroah-Hartman.  You have sent him
a patch that has triggered this response.  He used to manually respond
to these common problems, but in order to save his sanity (he kept
writing the same thing over and over, yet to different people), I was
created.  Hopefully you will not take offence and will fix the problem
in your patch and resubmit it so that it can be accepted into the Linux
kernel tree.

You are receiving this message because of the following common error(s)
as indicated below:

- You did not specify a description of why the patch is needed, or
  possibly, any description at all, in the email body.  Please read the
  section entitled "The canonical patch format" in the kernel file,
  Documentation/process/submitting-patches.rst for what is needed in
  order to properly describe the change.

- You did not write a descriptive Subject: for the patch, allowing Greg,
  and everyone else, to know what this patch is all about.  Please read
  the section entitled "The canonical patch format" in the kernel file,
  Documentation/process/submitting-patches.rst for what a proper
  Subject: line should look like.

If you wish to discuss this problem further, or you have questions about
how to resolve this issue, please feel free to respond to this email and
Greg will reply once he has dug out from the pending patches received
from other developers.

thanks,

greg k-h's patch email bot
Greg Kroah-Hartman Aug. 6, 2024, 7:07 a.m. UTC | #2 
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.

Why?  What is going to use this?  What needs it?

> full source:
> ------------
> https://github.com/kernel-bz/htree.git
> 
> Manual(PDF):
> ------------
> https://github.com/kernel-bz/htree/blob/main/docs/htree-20240802.pdf

These obviously do not belong in a changelog text :(
JaeJoon Jung Aug. 6, 2024, 7:32 a.m. UTC | #3 
Dear, Greg Kroah-Hartman
Thank you for your reply email.

My first email(PATCH v1) is at the below link:
https://mail.google.com/mail/u/0/?tab=rm&ogbl#label/htree/FMfcgzQVxtmfRqXCVrDZjsJBdddbPLCV
[PATCH v1 1/2] lib/htree: Implementation of new Hash Tree

I missed you in the first email above.
Since I've been working on something called a new Hash Table, it may
not be needed in the kernel right now.
Since it is not currently implemented in the kernel, I have been
thinking a lot about how to release it.
I sent it as a patch file, but since there was too much content,
So, I attached the github address and PDF separately.
I'm very sorry if this doesn't meet the current patch standards.
However, I would like you to check the contents of my first email and
reply to me regarding the technical details.
I want to prove that my Hash Tree is superior.
I know you're busy, but please review it again.
Thanks.
From JaeJoon Jung.

On Tue, 6 Aug 2024 at 16:07, Greg Kroah-Hartman
<gregkh@linuxfoundation.org> wrote:
>
> 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.
>
> Why?  What is going to use this?  What needs it?
>
> > full source:
> > ------------
> > https://github.com/kernel-bz/htree.git
> >
> > Manual(PDF):
> > ------------
> > https://github.com/kernel-bz/htree/blob/main/docs/htree-20240802.pdf
>
> These obviously do not belong in a changelog text :(
Greg Kroah-Hartman Aug. 6, 2024, 7:38 a.m. UTC | #4 
On Tue, Aug 06, 2024 at 04:32:22PM +0900, JaeJoon Jung wrote:
> Since I've been working on something called a new Hash Table, it may
> not be needed in the kernel right now.

We don't review, or accept, changes that are not actually needed in the
kernel tree as that would be a huge waste of reviewer time and energy
for no actual benefit.

sorry,

greg k-h
diff mbox series

Patch

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@gmail.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);