Skip to contentSkip to conversation

lib/htree: Implementation of new Hash Tree

PATCH New JaeJoon Jung 1 participant 1 message Aug 2, 2024

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/2 lib/htree: Implementation of new Hash Tree

new Hash Tree Features
-------------------------------------------------------------------------------
* Very small hash tree structure. [16 Bytes]
* Dynamic memory allocation and free.
* Both 32-bit and 64-bit indexes are possible
* Generate hash keys uniformly based on the index.
* Hash trees are balanced by hash keys, and have no rotation costs.
* Standard deviation of hash key is 4 or less.
* Algorithm O(n) is depth(d) x nodes(c)
* Finding walks is (d x c), min:4, avg:12, max:20
* First hash table has smallest, largest index, algorithm O(1).
* The codes implementing of the algorithm is simple.
* Adjust hash tree depth according to system memory and index nr.
* Hash list nodes use include/linux/list.h, hlist as their base.
-------------------------------------------------------------------------------

Hash Tree Summary (include/linux/htree.h)
-------------------------------------------------------------------------------
size of one hash tree struct: [16]Bytes
size of one data struct: (40)Bytes
size of middle: 32Bytes

if system has 16GB memory, number of index(nr) is 256M(middle) if system has 4GB memory, number of index(nr) is 64M(middle)
...

 index max: 1 << 50: 2^50:   1P (  1P x 32:  32P) --> depth:6 (64bits index)
 index max: 1 << 40: 2^40:   1T (  1T x 32:  32T) --> depth:6 (64bits index)
 ...
 index max: 1 << 32: 2^32:   4G (  4G x 32: 128G) --> depth:5
 index max: 1 << 28: 2^29: 512M (512M x 32:  16G) --> depth:4 (32bits index)
 index max: 1 << 28: 2^28: 256M (256M x 32:   8G) --> depth:4
 index max: 1 << 26: 2^26:  64M ( 64M x 32:   2G) --> depth:3 (32bits index)
 index max: 1 << 25: 2^25:  32M ( 32M x 32:   1G) --> depth:2

if number of index(nr) is between 32M and 64M, hash tree depth is [2,3)

hash array size(anum): 1 << (sbit - depth)
dnum: [d0:anum x d1:anum x d2:anum x d3:anum x d4:anum x d5:anum ...)

if starting hash bit(sbit) is 9:
dnum: [d0:512 x d1:256 x d2:128 x d3:64 x d4:32 x d5:16 ...)

dcnt(max index): (d:dnum * HTREE_NODE_CNT): (dnum * 4)

     : d0:2K, d1:512K, d2:64M, d3:4G, d4:128G, d5:2T, ...

asum(mid index): (d:dnum * HTREE_NODE_MIN): (dnum * 2)

     : d0:1K, d1:256K, d2:32M, d3:2G, d4: 64G, d5:1T, ...

htree depth avg(d): (3)
hlist node cnt(c) : [4)
algorithm O(n) : (d) x c == 3 x 4 == 12 (finding walks)
memory efficiency : (dcnt / asum) == 85%(/100 == 0.85) (usage eff)

 htree depth(d):   0 ---->   1 ---->   2 ---->  3 ---->  4 ---->  5
 hash bits(b)  :   9 ---->   8 ---->   7 ---->  6 ---->  5 ---->  4

table size(t) : 512 ----> 256 ----> 128 ----> 64 ----> 32 ----> 16

d0:b9:t512

    +-----[4)--> d1:b8:t256
                    +-------> d2:b7:t128
                                 +-------> d3:b6:t64
                                              +------> d4:b5:t32
                                                          +------> d5:b4:t16

if sort flag is HTREE_FLAG_ASCD, first htree depth(d0) has smallest index. if sort flag is HTREE_FLAG_DECD, first htree depth(d0) has largest index. hts->most has the hash key position, algorithm O(1).

If there is the same index:
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.

-------------------------------------------------------------------------------
Hash Tree API flow (lib/htree.c, lib/htree-test.c)
-------------------------------------------------------------------------------

*hts = ht_hts_alloc() /* alloc hts */
ht_hts_clear_init(hts, ...) /* max nr, type(32/64bits), sort(ASC, DES) */
*htree = ht_table_alloc(hts) /* alloc first(depth:0) htree */

run_loop() {
*udata = _data_alloc(index) /* alloc udata */
ht_insert(hts, htree, udata->hdata, ..) /* working data with index */
ht_erase(hts, htree, index)
hdata = ht_find(hts, htree, index)
hdata = ht_most_index(hts, htree) /* smallest, largest index */
ht_statis(hts, htree, ...) /* statistic */
}

htree_erase_all(hts, htree)     /* remove all udata */
ht_destroy(hts, htree)          /* remove all htree */
kfree(hts)                      /* remove hts */

-------------------------------------------------------------------------------

---
 include/linux/htree.h |  247 +++++++++
 lib/htree-test.c      | 1102 +++++++++++++++++++++++++++++++++++++++++
 lib/htree.c           |  634 ++++++++++++++++++++++++
 3 files changed, 1983 insertions(+)
 create mode 100644 include/linux/htree.h
 create mode 100644 lib/htree-test.c
 create mode 100644 lib/htree.c
include/linux/htree.h new file +247 -0
new file mode 100644
index 000000000000..c7b10c5b9bf2
@@ -0,0 +1,247 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ *  Hash-Trees header
+ *  lib/htree.h
+ *
+ *  Copyright(C) 2024, JaeJoon Jung <[email protected]> 
+ */
+
+#ifndef _LINUX_HTREE_H
+#define _LINUX_HTREE_H
+
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/list.h>
+#include <linux/hash.h>
+#include <linux/hashtable.h>
+#include <linux/slab.h>
+
+/*
+ size of one hash tree struct: [16]Bytes
+ size of one data struct: (40)Bytes
+ size of middle: 32Bytes
+
+ if system has 16GB memory, number of index(nr) is 256M(middle)
+ if system has  4GB memory, number of index(nr) is  64M(middle)
+ ...
+ index max: 1 << 50: 2^50:   1P (  1P x 32:  32P) --> depth:6 (64bits index)
+ index max: 1 << 40: 2^40:   1T (  1T x 32:  32T) --> depth:6 (64bits index)
+ ...
+ index max: 1 << 32: 2^32:   4G (  4G x 32: 128G) --> depth:5
+ index max: 1 << 28: 2^29: 512M (512M x 32:  16G) --> depth:4 (32bits index)
+ index max: 1 << 28: 2^28: 256M (256M x 32:   8G) --> depth:4
+ index max: 1 << 26: 2^26:  64M ( 64M x 32:   2G) --> depth:3 (32bits index)
+ index max: 1 << 25: 2^25:  32M ( 32M x 32:   1G) --> depth:2
+
+ if number of index(nr) is between 32M and 64M, hash tree depth is [2,3)
+
+ hash array size(anum): 1 << (sbit - depth)
+ dnum: [d0:anum x d1:anum x d2:anum x d3:anum x d4:anum x d5:anum ...)
+
+ if starting hash bit(sbit) is 9:
+ dnum: [d0:512  x d1:256  x d2:128  x d3:64   x d4:32   x d5:16   ...)
+
+ dcnt(max index): (d:dnum * HTREE_NODE_CNT): (dnum * 4)
+     : d0:2K, d1:512K, d2:64M, d3:4G, d4:128G, d5:2T, ...
+
+ asum(mid index): (d:dnum * HTREE_NODE_MIN): (dnum * 2)
+     : d0:1K, d1:256K, d2:32M, d3:2G, d4: 64G, d5:1T, ...
+
+ htree depth avg(d): (3)
+ hlist node cnt(c) : [4)
+ algorithm O(n)    : (d) x c == 3 x 4 == 12 (finding walks)
+ memory efficiency : (dcnt / asum) == 85%(/100 == 0.85) (usage eff)
+
+ htree depth(d):   0 ---->   1 ---->   2 ---->  3 ---->  4 ---->  5
+ hash bits(b)  :   9 ---->   8 ---->   7 ---->  6 ---->  5 ---->  4
+ table size(t) : 512 ----> 256 ----> 128 ----> 64 ----> 32 ----> 16
+
+ d0:b9:t512
+    +-----[4)--> d1:b8:t256
+		    +-------> d2:b7:t128
+				 +-------> d3:b6:t64
+					      +------> d4:b5:t32
+							  +------> d5:b4:t16
+
+ if sort flag is HTREE_FLAG_ASCD, first htree depth(d0) has smallest index.
+ if sort flag is HTREE_FLAG_DECD, first htree depth(d0) has largest index.
+ hts->most has the hash key position, algorithm O(1).
+
+ If there is the same index:
+ 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.
+*/
+
+struct hash_tree {		/* *htree: hash tree struct */
+	struct hlist_head head;	/* head of hash list(include/linux/types.h) */
+	struct hash_tree *next;	/* next depth hash tree of this node */
+} __aligned(16);		/* size:16, must be aligned(2^4) */
+
+
+struct htree_data {		/* *hdata: to interface with data */
+	u64 index;		/* hash index to interface with hash key */
+	struct hlist_node hnode;/* hash list node(data) to connect udata */
+};
+
+
+struct htree_state {		/* *hts: hash tree state to operation */
+	s8  sbit;		/* start bits of hash table */
+	s8  dept;		/* depth[0...127] of hash tree */
+	s8  dmax;		/* max depth[0...127] of hash tree */
+	u16 hkey;		/* hash key */
+	u16 wcnt;		/* count of finding walk steps */
+	u16 most;		/* moset smallest or largest position */
+	s32 acnt;		/* global: count of hash table alloc */
+	u64 dcnt;		/* global: count of data alloc */
+	u64 asum;		/* global: sum of hash table slot(anum) */
+	u8  idxt: 1;		/* bit flag: index type [0:64bits, 1:32bits] */
+	u8  sort: 1;		/* bit flag: sort type [0:ascend. 1:descend] */
+} __packed;
+
+
+enum ht_flags {			/* htf: htree working flags (keep order) */
+	htf_none,
+	htf_ok,
+	htf_ins,		/* insert */
+	htf_find_lt,		/* find less than */
+	htf_find,		/* find */
+	htf_find_gt,		/* find grater than */
+	htf_move,
+	htf_update,
+	htf_erase,
+	htf_freed,
+};
+
+#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 */
+
+#define HTREE_NODE_MIN		2	/* node min in one slot of htree */
+#define HTREE_NODE_CNT		4	/* node count in one slot of htree */
+#define HTREE_NODE_MAX		6	/* node max(2^4 - 2) in one slot */
+
+#define HTREE_GOLDEN_NR		25
+
+/*
+ * htgr32: hash tree golden ratio for 32bits: Standard Deviation: sqrt(4)
+ */
+static const u32 htgr32[] = { GOLDEN_RATIO_32,
+	0x8864761C, 0x64761C6B, 0x864761C6, 0x761C6B07,
+	0x4761C6B0, 0x1C6B0718, 0x61C6B071, 0x6B0718E0,
+	0xC6B0718E, 0x0718E074, 0xB0718E07, 0x18E074B3,
+	0x718E074B, 0xE074B396, 0x8E074B39, 0x74B396CC,
+	0x074B396C, 0xB396CC6B, 0x4B396CC6, 0x96CC6B07,
+	0x396CC6B0, 0xCC6B0718, 0x6CC6B071, 0x1C88647E
+};
+
+/*
+ * htgr64: hash tree golden ratio for 64bits: Standard Deviation: sqrt(4)
+ */
+static const u64 htgr64[] = { GOLDEN_RATIO_64,
+	0xB481B860C486B468ull, 0x4080B581D962C816ull, 0x86C281B581B061D4ull,
+	0xCB64C8B64D80B283ull, 0xC680C584DB60C8A1ull, 0x0C8262682B5862B6ull,
+	0x4B2B61B82616801Cull, 0x5680D518CB61C0B1ull, 0x1584CB61C816468Cull,
+	0x0B280CB60B816D68ull, 0x64680B1938B62B18ull, 0x84B261B0864180B5ull,
+	0x8064680B0938B61Cull, 0x583CB61C4C64280Bull, 0x680B282DB6D1C864ull,
+	0x51864180B481AB4Dull, 0x2BB080CB64C8D6A1ull, 0xA24680B180CB61D9ull,
+	0xC82D4680B082CA61ull, 0x80B583A461C28646ull, 0x2C460C8064D80B58ull,
+	0xA5C461C8064680C2ull, 0x1864A80B583C26BCull, 0xCB583CB6E2806064ull
+};
+
+#define HTREE_HASH_KEY(idx, d, bits)	( sizeof(idx) <= 4 ?	\
+	(((u32)idx + d) * htgr32[d]) >> (32 - bits) : 		\
+	(((u64)idx + d) * htgr64[d]) >> (64 - bits) )
+
+#define HTREE_MAX_NCNT(dept)	\
+	((dept < HTREE_NODE_MIN) ? HTREE_NODE_CNT : HTREE_NODE_MAX)
+
+#define HTREE_ARRAY_SIZE(bits)		(1 << bits)
+#define HTREE_EFF_ASUM(asum)		(asum * HTREE_NODE_MIN)
+#define HTREE_EFFICIENCY(dcnt, asum)	((dcnt * 100) / HTREE_EFF_ASUM(asum))
+
+#define HTREE_IDX_BASIC_NR		(1 << 25)	/* default: 32M */
+
+/* flag bit in the htree_state struct */
+#define HTREE_FLAG_IDX64	0
+#define HTREE_FLAG_IDX32	1
+#define HTREE_FLAG_ASCD		0
+#define HTREE_FLAG_DECD		1
+
+/* node count [0...255] to set/get at htree->next */
+#define HTREE_NCNT_MASK		0xF
+
+static inline struct hash_tree *ht_ncnt_inc(struct hash_tree *ht, u8 ncnt)
+{
+	return (struct hash_tree *)((u64)ht + ncnt);
+}
+
+static inline struct hash_tree *ht_ncnt_dec(struct hash_tree *ht, u8 ncnt)
+{
+	return (struct hash_tree *)((u64)ht - ncnt);
+}
+
+static inline struct hash_tree *ht_ncnt_set(struct hash_tree *ht, u8 ncnt)
+{
+	return (struct hash_tree *)(((u64)ht & ~HTREE_NCNT_MASK) | ncnt);
+}
+
+static inline u8 ht_ncnt_get(struct hash_tree *ht)
+{
+	return (u8)((u64)ht & HTREE_NCNT_MASK);
+}
+
+static inline struct hash_tree *ht_ncnt_pointer(struct hash_tree *ht)
+{
+	return (struct hash_tree *)((u64)ht & ~HTREE_NCNT_MASK);
+}
+
+static inline u8 ht_bits_from_depth(s8 sbit, s8 depth)
+{
+	s8 diff;
+	diff = sbit - depth;
+	return (diff < HTREE_BITS_END) ? HTREE_BITS_END : diff;
+}
+
+static inline u16 ht_get_hkey(u64 index, s8 dept, u8 bits, u8 idxt)
+{
+	return (idxt == HTREE_FLAG_IDX32) ?
+		HTREE_HASH_KEY((u32)index, dept % HTREE_GOLDEN_NR, bits):
+		HTREE_HASH_KEY((u64)index, dept % HTREE_GOLDEN_NR, bits);
+}
+
+/**
+  * htree_add - add an object to a hashtree
+  * @hashtree: hashtree to add to
+  * @node: the &struct hlist_node of the object to be added
+  * @key: the hash key of the object to be added
+  */
+#define htree_add_head(hashtree, node, key)	\
+	hlist_add_head((struct hlist_node*)node, &hashtree[key].head)
+
+
+/* public functions in the lib/htree.c */
+struct hash_tree *ht_table_alloc(struct htree_state *hts);
+
+struct htree_state *ht_hts_alloc(void);
+
+void ht_hts_clear_init(struct htree_state *hts, u64 maxnr, u8 idxt, u8 sort);
+
+struct htree_data *ht_find(struct htree_state *hts, 
+			   struct hash_tree *htree, u64 index);
+
+struct htree_data *ht_insert(struct htree_state *hts, struct hash_tree *htree,
+			     struct htree_data *hdata, enum ht_flags htf_req);
+
+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);
+
+void ht_statis(struct htree_state *hts, struct hash_tree *htree,
+	       s32 *acnt, u64 *dcnt);
+
+struct htree_data *ht_most_index(struct htree_state *hts, 
+				 struct hash_tree *htree);
+
+
+#endif	/* _LINUX_HTREE_H */
lib/htree-test.c new file +1102 -0

1,102 lines not on this page · raw message

lib/htree.c new file +634 -0

634 lines not on this page · raw message

Signature · 1 line
2.17.1