| 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
| ||
|
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