From patchwork Fri Aug 2 05:16:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: JaeJoon Jung X-Patchwork-Id: 13751097 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id C3C3CC52D71 for ; Fri, 2 Aug 2024 05:16:55 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E48716B007B; Fri, 2 Aug 2024 01:16:54 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E1E406B0083; Fri, 2 Aug 2024 01:16:54 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C49F86B0085; Fri, 2 Aug 2024 01:16:54 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 9AADD6B007B for ; Fri, 2 Aug 2024 01:16:54 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id F3D0D1C4809 for ; Fri, 2 Aug 2024 05:16:53 +0000 (UTC) X-FDA: 82406145906.08.C98A41F Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) by imf29.hostedemail.com (Postfix) with ESMTP id 09865120006 for ; Fri, 2 Aug 2024 05:16:51 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=LcB+i3sx; spf=pass (imf29.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1722575755; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:in-reply-to: references:dkim-signature; bh=m6AV2RSG77qPhghw7GhPlerdPy9PAUnZvPAu1UbDThA=; b=A2DnIYitD7sw7zoc/c+Wxi3orNaUu9DdiYbGo36Y2uctc8GMVtBsZjC6MDg8oWVEjIR3iY K0855ndqFu2Ib89K1vA5L+aaMWIinztIY6q7NtGNkhSeV2A2eYBYzSvC439Yhpqtwov588 Cp17IrdM/yVj/1qoQV7a6kAQ4MeF4CA= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1722575755; a=rsa-sha256; cv=none; b=ZkwWNDpp8BzgqHEpQeeezue7c0V8j8cPN8sd+s10njnucY4SXailfFt3IJwsBvtXySOubf JFwvd9dRntmuMaL4ZMLNUWHeYb0xp2yeyfmLQUgWERFVIK6A8eWM/mxuAOYYiabOvyHXpk OxnEAAI2VI3RaGmzA32jsc2nvy70srA= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=LcB+i3sx; spf=pass (imf29.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-7a211a272c2so2021343a12.1 for ; Thu, 01 Aug 2024 22:16:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722575811; x=1723180611; darn=kvack.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=m6AV2RSG77qPhghw7GhPlerdPy9PAUnZvPAu1UbDThA=; b=LcB+i3sxXG2bx65HD7wb+1nTHQvc10Hd2GiP/pTBN5K+IeM18mzgXVuMjZtTgqO14O ynbsPjwDWPHwHFEqgMEu66E+5fEzIoUhqJmHCtN5j5dtjfGVgSn7klD8sSlCTfOph1Zn RMlkSCNu3I1UfeUT+7BEDQINZQbgzDzJ4mIxIGeZyJXYmXmMD6aUTAKRqN1qKKuEtsg2 IAvWQ/BhY9SggpuCcxc0jgyYXSWwIDe76jlc5SQSP4hjpX8GWBXvaAUeG/EgtjRCNbob r2b12saEtRIbMLHazI2o//ZFHStIRsL5zM5KQM/Ks4cjXoDnFF6bPoL61bK7qoz8bLN1 sn9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722575811; x=1723180611; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=m6AV2RSG77qPhghw7GhPlerdPy9PAUnZvPAu1UbDThA=; b=FxEbIKUhAkSme5OAyDVv+ts1Ynh6ZxZbDyJKNPTJcB2eEKsy/SiU9CAxarofmGLZ3k YF06INb3xWN2PdeEeWdY3uMLkCJnSdeTyg2f+40IASaCJGPGrnww0IXlcuEocIeASHPB VSJLEIFAi4wkyK1j2kIuuIUHyL/ptbi33Xvu1s76YMB4eajVdXRnNTehi5EhAgvc20aq MetxADHPzwxuyDQO8tUv8JQLhNJl3u8+K+0k7ryQkOqXjZpsAo69jreAlAtBfIETiBqb +DegSbZEzLUAKH6/UwY71kn1pMGYGl6nBffIl/xr7wwX3RYX8Q+X08GAazFVGsGfAmQL Ipow== X-Forwarded-Encrypted: i=1; AJvYcCWc038hskALdULazTgDeIiGxSbs3GEwGJhWW14u8wRyUwkrzcnOVq3ViDzIk74/srUcm7Nqvc1jMGxz+hJxdGfcEvE= X-Gm-Message-State: AOJu0YzHemAmwkdK3RSeJ5GpjAfk1esxTJyTHh9ANoS/C8S8E4aNQjAN QfrnLz7Lad7/cgU8QoFoG9voISpx4+9or1PSy+b09CoiZf0tPNj0 X-Google-Smtp-Source: AGHT+IFf0pYFyJPrXkEQkmuLsNx8WTW74uS7uaUzYAi1jhrJogyP6plXw0Ga6eEujFObwAMOVz6LtA== X-Received: by 2002:a05:6a21:6da4:b0:1c0:f0af:60d with SMTP id adf61e73a8af0-1c69a59186cmr3717629637.6.1722575810159; Thu, 01 Aug 2024 22:16:50 -0700 (PDT) Received: from localhost.localdomain ([180.69.210.41]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-7106e7f2981sm667143b3a.0.2024.08.01.22.16.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 01 Aug 2024 22:16:49 -0700 (PDT) From: JaeJoon Jung To: Linus Torvalds , Sasha Levin , Michel Lespinasse , "Liam R . Howlett " , Matthew Wilcox Cc: JaeJoon Jung , linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org Subject: [PATCH v1 1/2] lib/htree: Implementation of new Hash Tree Date: Fri, 2 Aug 2024 14:16:35 +0900 Message-Id: <20240802051635.8179-1-rgbi3307@gmail.com> X-Mailer: git-send-email 2.17.1 MIME-Version: 1.0 X-Rspamd-Queue-Id: 09865120006 X-Stat-Signature: ma66dgbstyhea8k73mb5f6sgps9hj8a8 X-Rspamd-Server: rspam09 X-Rspam-User: X-HE-Tag: 1722575811-979997 X-HE-Meta: U2FsdGVkX1+HRw5EEW3VW7vq/pHBH6bmleuuOsr/luLo3MIcE0tlYH9/hAtWtZRWG2mAL1RziXD02I2TwBD5io1TsM5j6V4cHJZQ8M8iOfeErfqlirwoMVs46NpRYqpDiOA8Wlct6U2JTUMl7qhUdXU4yttT+XCMB2DxAq31SojVEX9eZpTKxLjmDBaQpG/e5sKX5rdk/WQvb6l1D/3x/RlhpYxYqpaJYS2DnDPMQBWExPiWr9tgAgB5Nt3zmp3LG8Iwyl8B2EOFnm+2cRyfw/XRSInfiWTHEpMwd0z7CZ0TNMxaTxdiTlmHkyBBP2iF24I85BtZVdoH1JWtM/bfCiT/++8yn4BIkiX7T9FB/hHILnJVnuZ1dOvz3hTL87HMKofXXIDzCQ7Oh/l0Ct9D1AkAuFXxOvfK7RZ+92wbCRrEQWDgUdJTvC5D9JkQCmvwdNaZZ7UtmfGOvInyxE2GoqBwvjGacbe1A95CD5axrgod/vWuFoHOqNLRZkrM9kT4WThu3dwq2pvslIrpvvbyIs560JM4V6BLdoAy/a8Tvxbw6QQr2Xr35OFtMTSog5Z+zf7ZRQ57Z81lu1QUlff5lLZRG+Fm5zoE+UXgC+hlTkF1J3TsbpTe2fbCegg9dMLuSjym2hmJ7wqV977mAn1bsNfncrS520A/E9wu80dFiqZLJJnSodXlJ7uBYm/SYSfDr29SpRsshMi+xi0e6Q8jc275V+c5N1qLbZQes8ZiL870cfq2Zi+tACtTOAem9Z2f2WbscFOItTi55JE284jnwZQf6VTSdwvrr1i/2Cg9d4J0q6mNEahWAEeHNXsN4q4vBEVQo8VJ9tkFJGyJM2xdy0oNZEzc/wVGQjMR6XT7fBwCxMC9013RjN31oGKQL9N1706bM7nfLd2hZzTLJHxSZgUFyJDQD7GP396qF0AyvmdHJZSFunCkUGBlrRjtI0fAoiYrZAWLnWfxN4r9aFl G1u5Co3G vAmVhReT6Vhj5hJlbVTqltWUlVNN67IAEe0AUPz4BLCJJxeHbj70pGwvdlSXopj+3rneoWoIgLHV6BIm4qe4IOLOHjqSukfrevikkFSp8mHFszBqdu+pUxVzD4vEEE66ZUSRt46arPpMyHxY3V817pqHM3HlePfWRK3Rge7NRXwBKvTaL6gwSTzui1a6+iS+1PNnFKCwnzcOHZPgED6CAg3qKEH8+WCbEHwNCcSiKUVFX+2OWhPhgbGgu3FLhKOKrpZ9wNIcqt8kAiOCmfmlXjYQPlPcmGVhW15ueFoaA3/OTJGF2c8B7s93z9GuB/0Qky6eOm8nIzoq55rKwwgKnzp1x605tezqsTbdSd7Mva38NKJm4k96ulJGIdkZamK2YL6CDyqQ+Op6PKIFlEp4FYui7ZvmIH1Cz36mb X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 */ ------------------------------------------------------------------------------- Signed-off-by: JaeJoon Jung --- 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 diff --git a/include/linux/htree.h b/include/linux/htree.h new file mode 100644 index 000000000000..c7b10c5b9bf2 --- /dev/null +++ b/include/linux/htree.h @@ -0,0 +1,247 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Hash-Trees header + * lib/htree.h + * + * Copyright(C) 2024, JaeJoon Jung + */ + +#ifndef _LINUX_HTREE_H +#define _LINUX_HTREE_H + +#include +#include +#include +#include +#include +#include + +/* + 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 */ diff --git a/lib/htree-test.c b/lib/htree-test.c new file mode 100644 index 000000000000..05b60da271de --- /dev/null +++ b/lib/htree-test.c @@ -0,0 +1,1102 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * htree/htree-api.c + * Hash-Trees test codes to verify + * + * Copyright(C) 2024, JaeJoon Jung + */ + +#include +#include +#include +#include + +#include + +/* + Hash Tree API flow + ------------------ + + *hts = ht_hts_alloc() //alloc hts + ht_hts_clear_init(hts, ...) + + *htree = ht_table_alloc(hts) //alloc first(depth:0) htree + + run_loop() { + + *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_statis(hts, htree, ...) + } + + htree_erase_all(hts, htree) //remove all udata + + ht_destroy(hts, htree) //remove all htree + + kfree(hts) //remove hts +*/ + + +/* +#define HTREE_DEBUG_INFO +#define HTREE_DEBUG_DETAIL +*/ + +#define pr_ht_err pr_err +#define pr_ht_warn pr_warn +#define pr_ht_stat printk + +#ifdef HTREE_DEBUG_INFO +#define pr_ht_info printk + +#else +#define pr_ht_info(fmt, ...) + +#endif + +#ifdef HTREE_DEBUG_DETAIL +#define pr_ht_find printk +#define pr_ht_erase printk +#define pr_ht_update printk +#define pr_ht_debug printk + +#else +#define pr_ht_find(fmt, ...) +#define pr_ht_erase(fmt, ...) +#define pr_ht_update(fmt, ...) +#define pr_ht_debug(fmt, ...) + +#endif + +#define HTREE_TEST_SCHED_CNT 200 + +struct data_struct { + /* user defined data members ... */ + char a; + int b; + long c; + + /* must be here to interface hash index */ + struct htree_data hdata; +}; + +/** + * _htree_data_alloc - memory allocation of user data_struct + * @index: 64bits index to make hash key + * + * the hash key is created using the index and connected to the hash tree. + * udata is linked to the index(hash key) location. + * + * connection flow: + * udata <----> hdata <----> htree + * index(64bits): udata.hdata.index --> hash key --> hash table index(htree) + * data : udata.hdata.hnode --> htree.head --> hash list data nodes + */ +static struct data_struct *_htree_data_alloc(u64 index) +{ + struct data_struct *udata = (struct data_struct *) + kmalloc(sizeof(struct data_struct), GFP_KERNEL); + + /* todo: set user defined data */ + udata->a = 97; + udata->b = 98; + udata->c = 99; + + /* interface with hash index (64bits) */ + udata->hdata.index = index; + + INIT_HLIST_NODE(&udata->hdata.hnode); + + return udata; +} + +/** + * _htree_test_hash_var - calculate the standard deviation of the hash key + * @bits: hash table size is (1 << bits) + * @vbits: for loop count + * + * ht_get_hkey distributes the hash keys using a golden ratio table. + */ +static void _htree_hash_dev(const u32 bits, const u32 vbits) +{ + u64 i, v, k; + s64 ka; + u64 ks, kas = 0; + const u16 kcnt = 1 << bits; + u32 *kc = (u32 *)kmalloc_array(kcnt, sizeof(u32), GFP_KERNEL); + + const u32 vcnt = 1 << vbits; + + for (v = 0; v < vcnt; v++) { + for (k = 0; k < kcnt; k++) + kc[k] = 0; + + for (i = 0; i < HTREE_GOLDEN_NR; i++) { + k = ht_get_hkey(v, i, bits, HTREE_FLAG_IDX32); + kc[k]++; + k = ht_get_hkey(v, i, bits, HTREE_FLAG_IDX64); + kc[k]++; + } + + ks = 0; + for (k = 0; k < kcnt; k++) + ks += kc[k]; + ka = ks >> bits; /* avg: ks / kcnt */ + ks = 0; + for (k = 0; k < kcnt; k++) + ks += ((kc[k] - ka) * (kc[k] - ka)); + ka = ks >> bits; /* Variance: avg: ks / kcnt */ + kas += ka; /* sum of Variance */ + } + /* Standard Deviation: sqrt(avg:kas) */ + pr_ht_info("vbits:%u, cnt:%u, Standard Deviation:sqrt(%llu)\n\n", + vbits, vcnt, (kas >> vbits) >> 2); + kfree(kc); +} + +/** + * __htree_hash_key - outputs hash key distribution data + * @index: index to make hash key + * @bits: hash table size is (1 << bits) + */ +static void __htree_hash_key(u64 index, const u32 bits) +{ + u32 k, key0, key1, key2; + const u32 kcnt = 1 << bits; + u32 *kcnt0 = (u32*)kmalloc_array(kcnt, sizeof(u32), GFP_KERNEL); + u32 *kcnt1 = (u32*)kmalloc_array(kcnt, sizeof(u32), GFP_KERNEL); + u32 *kcnt2 = (u32*)kmalloc_array(kcnt, sizeof(u32), GFP_KERNEL); + + for (k = 0; k < kcnt; k++) { + kcnt0[k] = 0; + kcnt1[k] = 0; + kcnt2[k] = 0; + } + + key1 = index; + for (k = 0; k < HTREE_GOLDEN_NR; k++) { + key0 = hash_min(index, bits); + key1 = hash_min((u64)key1, bits); + kcnt0[key0]++; + kcnt1[key1]++; + + key2 = ht_get_hkey(index, k, bits, HTREE_FLAG_IDX32); + kcnt2[key2]++; + key2 = ht_get_hkey(index, k, bits, HTREE_FLAG_IDX64); + kcnt2[key2]++; + } + + key0 = 0; + key1 = 0; + key2 = 0; + for (k = 0; k < kcnt; k++) { + pr_ht_info("%3u: kcnt0:%6u, kcnt1:%6u, kcnt2:%6u\n", + k, kcnt0[k], kcnt1[k], kcnt2[k]); + key0 += kcnt0[k]; + key1 += kcnt1[k]; + key2 += kcnt2[k]; + } + pr_ht_info("----------------------------------------------\n"); + pr_ht_info("sum: skey0:%6u, skey1:%6u, skey2:%6u\n", key0, key1, key2); + + kfree(kcnt0); + kfree(kcnt1); + kfree(kcnt2); +} + +/** + * _htree_hash_key - test of sample hash key + * @bits: hash table size is (1 << bits) + * @vbits: loop count in use sample index + * + * outputs hash key distribution data calculated from hash_min() + * and ht_get_hkey using some indices. + */ +static void _htree_hash_key(const u32 bits, const u32 vbits) +{ + u64 v; + for (v = 0; v < vbits / 2; v++) { + pr_ht_info("value:%llu, bits:%u\n", v, bits); + pr_ht_info("----------------------------------------------\n"); + __htree_hash_key(v, bits); + pr_ht_info("\n"); + } +} + +/** + * _htree_test_hash - hash key test + * + * output of hash key distribution + */ +static void _htree_test_hash(void) +{ + const u32 bits = 2; + const u32 vbits = 12; + + _htree_hash_dev(bits, vbits); + _htree_hash_key(bits, vbits); +} + + +#ifdef HTREE_DEBUG_DETAIL + +/** + * htree_hdata_debug - shows hlist nodes in the hash tree at same index order. + * @htree: hash_tree to show + * @index: index to find + * @htf: ht_flags to confirm + */ +static void htree_debug_hdata(struct htree_state *hts, struct hash_tree *hcurr, + u64 index, enum ht_flags htf) +{ + u8 ncnt, bits; + u16 key; + s16 dept; + u32 offset; + struct htree_data *pos; + struct hlist_node *tmp; + const char *htfs[] = { + "htf_none", + "htf_ok", + "htf_ins", + "htf_find_lt", + "htf_find", + "htf_find_gt", + "htf_move", + "htf_update", + "htf_erase", + "htf_freed", + }; + + if (!hcurr) + return; + + dept = hts->dept; + pr_ht_debug("\n((%s)) DEBUG sbit:%u, dept:%d/%d, index:<%llu>\n", + htfs[htf], hts->sbit, hts->dept, hts->dmax, index); + pr_ht_debug("-----------------------------------------------\n"); + bits = ht_bits_from_depth(hts->sbit, dept); + key = ht_get_hkey(index, dept, bits, hts->idxt); +__next: + ncnt = ht_ncnt_get(hcurr->next); + + pr_ht_debug("d:%d b:%u [%u] %p(%u): ", dept, bits, key, hcurr, ncnt); + offset = 0; + hlist_for_each_entry_safe(pos, tmp, &hcurr->head, hnode) { + if (pos->index == index) { + pr_ht_debug("%u:%llu(@) FOUND.", offset, pos->index); + } else { + pr_ht_debug("%u:%llu> ", offset, pos->index); + } + offset++; + } + pr_ht_debug("\n"); + + hcurr = ht_ncnt_pointer(hcurr->next); + if (hcurr) { + dept++; + bits = ht_bits_from_depth(hts->sbit, dept); + key = ht_get_hkey(index, dept, bits, hts->idxt); + hcurr = &hcurr[key]; + goto __next; + } +} + +/** + * __htree_debug_walks_all - private call recursively to show all indexes + * @hts: htree_state pointer + * @htree: hash_tree root pointer + * @index: index to find + */ +static void __htree_debug_walks_all(struct htree_state *hts, + struct hash_tree *htree, u64 index) +{ + u8 bits, ncnt; + u16 k, anum, pnum; + struct hash_tree *_next; + struct htree_data *hdata; + struct hlist_node *tmp; + + bits = ht_bits_from_depth(hts->sbit, hts->dept); + anum = HTREE_ARRAY_SIZE(bits); + + for (k = 0; k < anum; k++) { + ncnt = ht_ncnt_get(htree[k].next); + if (ncnt > 0) { + bits = ht_bits_from_depth(hts->sbit, hts->dept); + pr_ht_debug("d:%u b:%u [%u] %p (%u): ", + hts->dept, bits, k, &htree[k], ncnt); + + hlist_for_each_entry_safe(hdata, tmp, + &htree[k].head, hnode) { + if (hdata->index == index) { + pr_ht_debug("< ((%llu)) ", hdata->index); + } else { + pr_ht_debug("< %llu ", hdata->index); + } + } + } + _next = ht_ncnt_pointer(htree[k].next); + if (_next) { + pr_ht_debug(">>\n"); + hts->dept++; + pnum = anum; + /* recursive call */ + __htree_debug_walks_all(hts, _next, index); + anum = pnum; + hts->dept--; + } else { + pr_ht_debug("\n%u]] ", k); + continue; + } + pr_ht_debug(".\n\n"); + } +} + +/** + * htree_walks_all_debug - display to debug all indexes + * @hts: htree_state pointer + * @htree: 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) +{ + 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); + + pr_ht_debug("(@@@@] done: sbit:%u, dmax:%u, acnt:%d, dcnt:%llu\n\n", + hts->sbit, hts->dmax, hts->acnt, hts->dcnt); +} +#endif /* HTREE_DEBUG_DETAIL */ + +/** + * __htree_erase_all - 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, + struct hash_tree *htree, u64 *erased) +{ + u8 bits, ncnt; + u16 k, anum, pnum; + struct hash_tree *_next; + struct htree_data *pos; + struct hlist_node *tmp; + struct data_struct *udata; + + bits = ht_bits_from_depth(hts->sbit, hts->dept); + anum = HTREE_ARRAY_SIZE(bits); + + for (k = 0; k < anum; k++) { + ncnt = ht_ncnt_get(htree[k].next); + if (ncnt > 0) { + bits = ht_bits_from_depth(hts->sbit, hts->dept); + hlist_for_each_entry_safe(pos, tmp, + &htree[k].head, hnode) { + hlist_del(&pos->hnode); + udata = hlist_entry_safe(pos, + struct data_struct, hdata); + if (udata) { + kfree(udata); + (*erased)++; + } + } + } + _next = ht_ncnt_pointer(htree[k].next); + if (_next) { + hts->dept++; + pnum = anum; + /* recursive call */ + __htree_erase_all(hts, _next, erased); + anum = pnum; + hts->dept--; + } else { + continue; + } + } +} + +/** + * htree_erase_all - erase udata all + * @hts: htree_state pointer + * @htree: hash_tree root pointer + * + * return: erased all udata count + */ +static u64 htree_erase_all(struct htree_state *hts, struct hash_tree *htree) +{ + u64 erased = 0; + + pr_ht_info("[~~~~) erase all: sbit:%u, dmax:%u, acnt:%d, dcnt:%llu\n", + hts->sbit, hts->dmax, hts->acnt, hts->dcnt); + + hts->dept = 0; + __htree_erase_all(hts, htree, &erased); + + pr_ht_info("(~~~~] done: sbit:%u, acnt:%d, dcnt:%llu, erased:%llu\n\n", + hts->sbit, hts->acnt, hts->dcnt, erased); + + return erased; +} + +/** + * _htree_insert_range - insert udata to hash tree using ht_insert() + * @hts: htree_state pointer + * @htree: hash_tree root pointer + * @start: start index to insert + * @end: end index to insert + * @gap: gap between indices + * @req: request flags + * + * 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. + */ +static u64 _htree_insert_range(struct htree_state *hts, struct hash_tree *htree, + u64 start, u64 end, u64 gap, enum ht_flags req) +{ + u64 index; + u64 loop = 0, ins = 0, era = 0; + struct data_struct *udata; + struct htree_data *rdata; + + pr_ht_info("[++++) inserting: [s:%llu ... e:%llu] (g:%llu)\n", + start, end, gap); + for (index = start; index <= end; index += gap) { + udata = _htree_data_alloc(index); + rdata = ht_insert(hts, htree, &udata->hdata, req); + if (req == htf_erase && rdata) { + udata = hlist_entry_safe(rdata, struct data_struct, hdata); + if (udata && rdata->index == index) { + kfree(udata); + era++; + } + } + ins++; + loop++; + if (!(loop % HTREE_TEST_SCHED_CNT)) + schedule(); + } + pr_ht_info("(++++] done: loop:%llu, inserted:%llu, same erased:%llu\n\n", + loop, ins, era); + + return ins - era; +} + +/** + * _htree_find_range - find udata in the hash tree using ht_find() + * @hts: htree_state pointer + * @htree: 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, + u64 start, u64 end, u64 gap) +{ + u64 index; + u64 loop = 0, found = 0; + struct data_struct *udata; + struct htree_data *rdata; + + 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); + if (rdata) { + udata = hlist_entry_safe(rdata, struct data_struct, hdata); + if (udata && rdata->index == index) { + pr_ht_find("*todo: find:<%llu> %c %c %c\n", + index, udata->a, (char)udata->b, (char)udata->c); + found++; + } + } + loop++; + if (!(loop % HTREE_TEST_SCHED_CNT)) + schedule(); + } + pr_ht_info("(****] done: loop:%llu, found:%llu, diff:%llu\n\n", + loop, found, loop - found); + return found; +} + +/** + * _htree_erase_range - erase udata from hash tree using ht_erase() + * @hts: htree_state pointer + * @htree: 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, + u64 start, u64 end, u64 gap) +{ + u64 index; + u64 loop = 0, erased = 0; + 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); + if (rdata) { + udata = hlist_entry_safe(rdata, struct data_struct, hdata); + if (udata && rdata->index == index) { + pr_ht_erase("*todo: erase:<%llu> %c %c %c\n", + index, udata->a, (char)udata->b, (char)udata->c); + kfree(udata); + erased++; + } +#ifdef HTREE_DEBUG_DETAIL + } else { + hts->hkey = ht_get_hkey(index, 0, hts->sbit, hts->idxt); + htree_debug_hdata(hts, &htree[hts->hkey], index, htf_erase); +#endif + } + loop++; + if (!(loop % HTREE_TEST_SCHED_CNT)) + schedule(); + } + pr_ht_info("(----] done: loop:%llu, erased:%llu, diff:%llu\n\n", + loop, erased, loop - erased); + return erased; +} + +/** + * _htree_update_range - update udata in the hash tree using ft_find() + * @hts: htree_state pointer + * @htree: 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, + u64 start, u64 end, u64 gap) +{ + u64 index; + u64 loop = 0, updated = 0; + 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) { + rdata = ht_find(hts, htree, index); + if (rdata) { + udata = hlist_entry_safe(rdata, struct data_struct, hdata); + if (udata && rdata->index == index) { + pr_ht_update("*todo: update:<%llu> %c %c %c ", + index, udata->a, (char)udata->b, (char)udata->c); + /* todo: update user defined data */ + udata->a -= 32; + udata->b -= 32; + udata->c -= 32; + + pr_ht_update(">> %c %c %c\n", + udata->a, (char)udata->b, (char)udata->c); + updated++; + } +#ifdef HTREE_DEBUG_DETAIL + } else { + hts->hkey = ht_get_hkey(index, 0, hts->sbit, hts->idxt); + htree_debug_hdata(hts, &htree[hts->hkey], index, htf_update); +#endif + } + loop++; + if (!(loop % HTREE_TEST_SCHED_CNT)) + schedule(); + } + pr_ht_info("(####] done: loop:%llu, updated:%llu, diff:%llu\n\n", + loop, updated, loop - updated); + + return updated; +} + +/** + * _htree_statis - calculate hash tree statistics and get into hts. + * @hts: htree_state pointer to store statistics + * @htree: hash_tree root pointer + */ +static void _htree_statis(struct htree_state *hts, struct hash_tree *htree) +{ + s32 acnt = 0; + u64 dcnt = 0; + + ht_statis(hts, htree, &acnt, &dcnt); + + if (hts->dcnt == dcnt && hts->acnt == acnt) { + pr_ht_info("[ OK ] statist: acnt:%d, dcnt:%llu ", acnt, dcnt); + } else { + pr_ht_info("[FAIL] statist: acnt:%d(%d), dcnt:%llu(%llu)\n", + acnt, hts->acnt, dcnt, hts->dcnt); + } + pr_ht_info(">> asum:%llu, eff:%llu(/100)\n\n", + hts->asum, HTREE_EFFICIENCY(hts->dcnt, hts->asum)); +} + +/** + * _htree_statis_info - shows information calculated by htree_statis(). + */ +static void _htree_statis_info(struct htree_state *hts, struct hash_tree *htree) +{ + u32 sizh = sizeof(struct hash_tree); + u32 sizd = sizeof(struct data_struct); + + /* total data slot of full hash table area */ + u64 hsum = (sizh * hts->acnt) >> 10; + u64 dsum = (sizd * hts->dcnt) >> 10; + u64 smem = hsum + dsum; + + if (hts->asum == 0) + _htree_statis(hts, htree); + + pr_ht_stat("------------------------------------------\n"); + pr_ht_stat(" hash start bits(sbit) : %10d\n", hts->sbit); + pr_ht_stat(" hash tree max depth : %10u\n", hts->dmax); + pr_ht_stat(" finding walks(wcnt) : %10u\n", hts->wcnt); + pr_ht_stat(" user data alloc(dcnt) : %16llu\n", hts->dcnt); + pr_ht_stat(" hash tree alloc(acnt) : %10d\n", hts->acnt); + pr_ht_stat(" hash tree sum(asum) : %16llu\n", hts->asum); + pr_ht_stat(" htree nodes sum(stot) : %16llu\n", + HTREE_EFF_ASUM(hts->asum)); + pr_ht_info(" hlist node cnt(ncnt) : %10d\n", HTREE_NODE_CNT); + pr_ht_info(" sizeof hash_tree(B) : %10u\n", sizh); + pr_ht_info(" sizeof data_struct(B) : %10u\n", sizd); + pr_ht_info(" hash using mem(KB) : %16llu\n", hsum); + pr_ht_info(" data using mem(KB) : %16llu\n", dsum); + pr_ht_stat(" total using mem(KB) : %16llu\n", smem); + pr_ht_stat("------------------------------------------\n"); + pr_ht_stat(" efficiency(dcnt/stot) : %8llu(/100)\n", + HTREE_EFFICIENCY(hts->dcnt, hts->asum)); + pr_ht_stat("------------------------------------------\n\n"); +} + +/** + * _htree_get_most_index - get most smallest and largest index + * + * 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) +{ + struct htree_data *hdata; + hdata = ht_most_index(hts, htree); + if (hdata) { + if (hts->sort == HTREE_FLAG_ASCD) { + pr_ht_stat("[MOST] smallest index:%llu\n\n", hdata->index); + } else { + pr_ht_stat("[MOST] largest index:%llu\n\n", hdata->index); + } + } +} + +/** + * _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. + */ +static void _htree_remove_all(struct htree_state *hts, struct hash_tree *htree) +{ + /* remove all udata */ + hts->dcnt -= htree_erase_all(hts, htree); + 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) { + pr_ht_stat("[ OK ] destroy remained acnt:%d, dcnt:%llu\n\n", + hts->acnt, hts->dcnt); + } else { + pr_ht_warn("[WARN] destroy remained acnt:%d, dcnt:%llu\n\n", + hts->acnt, hts->dcnt); + } +} + +/** + * _htree_test_index_loop - main test loop + * @hts: htree_state pointer + * @start: starting index to test + * @end: ending index to test + * + * return: dcnt: index(data) working count + * + * testing flow: + * insert --> erase,find --> insert,update --> statistic --> free,destroy + */ +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; + + if (start > end) + return 0; + slice = (end - start) / 10 + 2; + + /* first root hash tree alloc */ + htree = ht_table_alloc(hts); + + inserted = _htree_insert_range(hts, htree, 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); + + erased = _htree_erase_range(hts, htree, start, end, slice); + found = _htree_find_range(hts, htree, 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); + + inserted = _htree_insert_range(hts, htree, start, end, slice, htf_ins); + updated = _htree_update_range(hts, htree, 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); + +#ifdef HTREE_DEBUG_DETAIL + htree_debug_walks_all(hts, htree, 0); +#endif + _htree_statis_info(hts, htree); + dcnt = hts->dcnt; + + _htree_remove_all(hts, htree); + + return dcnt; +} + +/** + * _htree_test_idx_range - index test of 32bits/64bits, ascending/descending + * @idx_type: hts->idxt: index type [0:64bits, 1:32bits] + * @sort_type: hts->sort: sorting type [0:ascending, 1:descending] + * + * Importance: must be use the ht_hts_clear_init() to adjust htree depth. + * + * 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 ...) + * + * number of index(nr) is between 32M and 64M, and hash tree depth is [2,3) + * + * htree depth avg(d): (3) + * hlist node cnt(c) : [4) + * efficiency O(n) : (d) x c == 3 x 4 == 12 (finding walks) + * using memory eff : (dcnt / asum) == 85%(/100 == 0.85) + * + * you can test by changing start, end with 32bits or 64bits data type. + * Be careful: if system has 4GB memory: + * if (index nr > 128M) then depth > 3, out of memory(OOM) + */ +static void _htree_test_idx_range(u8 idx_type, u8 sort_type) +{ + u64 start, end, maxnr; + u64 idx, dcnt, eff = 0; + u32 wcnt = 0; + const u8 loopnr = 14; + const u32 v1k = 1 << 10; + const u64 v1t = (u64)1 << 40; + const char *idxts[] = { "64bits", "32bits" }; + const char *sorts[] = { "ASCD", "DECD" }; + + struct htree_state *hts = ht_hts_alloc(); + + for (idx = 1; idx <= loopnr; idx++) { + pr_ht_stat("[START) RANGE(insert, erase, find, update) \ +index type:<%s>, sorting type:<%s>\n", idxts[idx_type], sorts[sort_type]); + + start = (idx_type == HTREE_FLAG_IDX32) ? idx * v1k : idx * v1t; + end = start + (1 << idx) * v1k; + maxnr = end - start + 1; + + /* setting hash tree depth, index type and sorting type */ + ht_hts_clear_init(hts, maxnr, idx_type, sort_type); + + pr_ht_stat( + "[loop) %llu: sbit:%u, start:%llu, end:%llu, maxnr:%llu\n\n", + idx, hts->sbit, start, end, maxnr); + + dcnt = _htree_test_index_loop(hts, start, end); + eff += HTREE_EFFICIENCY(dcnt, hts->asum); + wcnt += hts->wcnt; + } + /* + * loopnr:14(16M) 32bits: ascending efficiency avg: 85/100, wcnt: 9 + * loopnr:14(16M) 32bits: descending efficiency avg: 85/100, wcnt: 8 + * + * loopnr:14(16M) 64bits: ascending efficiency avg: 97/100, wcnt:10 + * loopnr:14(16M) 64bits: descending efficiency avg: 97/100, wcnt: 7 + */ + pr_ht_stat("=======================================================\n"); + pr_ht_stat("( END] RANGE index type:<%s>, sorting type:<%s>\n", + idxts[idx_type], sorts[sort_type]); + pr_ht_stat("( EFF] loop:%u, efficiency avg:%llu(/100), wcnt:(%u)\n\n", + loopnr, eff / loopnr, wcnt / loopnr); + kfree(hts); +} + +/** + * _htree_test_idx_random - random index test + * @idx_type: hts->idxt: index type [0:64bits, 1:32bits] + * @sort_type: hts->sort: sorting type [0:ascending, 1:descending] + * @maxnr: max number of index + * + * testing flow: + * random index --> ht_insert() --> ht_erase() --> statis info --> free all + */ +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; + const char *idxts[] = { "64bits", "32bits" }; + const char *sorts[] = { "ASCD", "DECD" }; + const u64 check_idx = 25203307; + + struct htree_state *hts = ht_hts_alloc(); + + /* setting hash tree depth, index type and sorting type */ + ht_hts_clear_init(hts, maxnr, idx_type, sort_type); + + /* first root hash tree alloc */ + htree = ht_table_alloc(hts); + + 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); + inserted++; + loop++; + + pr_ht_stat("[loop) %llu: random insert\n\n", maxnr); + for (i = 0; i < maxnr; i++) { + index = (idx_type == HTREE_FLAG_IDX32) ? + get_random_u32() : get_random_u64(); + + udata = _htree_data_alloc(index); + rdata = ht_insert(hts, htree, &udata->hdata, htf_ins); + if (!rdata) + inserted++; + loop++; + if (!(loop % HTREE_TEST_SCHED_CNT)) + schedule(); + } + + _htree_statis(hts, htree); + + rdata = ht_find(hts, htree, check_idx); + if (!rdata) { + pr_ht_err("[FAIL] NOT found check index:%llu\n\n", check_idx); + } + + maxnr *= 2; + pr_ht_stat("[loop) %llu: random erase\n\n", maxnr); + for (i = 0; i < maxnr; i++) { + index = (idx_type == HTREE_FLAG_IDX32) ? + get_random_u32() : get_random_u64(); + + rdata = ht_erase(hts, htree, index); + if (rdata) { + udata = hlist_entry_safe(rdata, struct data_struct, hdata); + if (udata && rdata->index == index) { + pr_ht_erase("*todo: erase:<%llu> %c %c %c\n", + index, udata->a, (char)udata->b, (char)udata->c); + kfree(udata); + erased++; + } + } + loop++; + if (!(loop % HTREE_TEST_SCHED_CNT)) + schedule(); + } + + _htree_statis(hts, htree); + + rdata = ht_find(hts, htree, check_idx); + if (!rdata) { + pr_ht_info("[INFO] check index:%llu (erased)\n\n", check_idx); + } + + pr_ht_stat("( END] RANDOM loop:%llu, inserted:%llu, erased:%llu\n\n", + loop, inserted, erased); + +#ifdef HTREE_DEBUG_DETAIL + htree_debug_walks_all(hts, htree, 0); +#endif + + _htree_get_most_index(hts, htree); + _htree_statis_info(hts, htree); + + _htree_remove_all(hts, htree); + + kfree(hts); +} + +/** + * _htree_test_index_same - same index test + * @idx_type: hts->idxt: index type [0:64bits, 1:32bits] + * @sort_type: hts->sort: sorting type [0:ascending, 1:descending] + * @maxnr: max number of index + * + * 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. + * + * testing flow: + * new index --> ht_insert() --> same index --> ht_insert() --> statis info + */ +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" }; + const u32 gap = 2; + + struct htree_state *hts = ht_hts_alloc(); + + /* setting hash tree depth, index type and sorting type */ + ht_hts_clear_init(hts, maxnr, idx_type, sort_type); + + /* first root hash tree alloc */ + htree = ht_table_alloc(hts); + + 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); + 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); + + pr_ht_stat("[loop) %llu: SAME index inserting(htf_erase)\n\n", maxnr); + inserted = _htree_insert_range(hts, htree, 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); + 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); + 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); + +#ifdef HTREE_DEBUG_DETAIL + htree_debug_walks_all(hts, htree, 0); +#endif + _htree_get_most_index(hts, htree); + _htree_statis_info(hts, htree); + + _htree_remove_all(hts, htree); + + kfree(hts); +} + +#ifdef HTREE_DEBUG_DETAIL +/** + * _htree_test_index_debug - simple index test on debug mode + * + * show detailed hash tree information + */ +static void htree_debug_index(void) +{ + struct htree_state *hts = ht_hts_alloc(); + + ht_hts_clear_init(hts, 32, HTREE_FLAG_IDX64, HTREE_FLAG_DECD); + _htree_test_index_loop(hts, 0, 32); + + ht_hts_clear_init(hts, 32, HTREE_FLAG_IDX32, HTREE_FLAG_ASCD); + _htree_test_index_loop(hts, 0, 32); + + _htree_test_idx_random(HTREE_FLAG_IDX64, HTREE_FLAG_ASCD, 32); + _htree_test_idx_random(HTREE_FLAG_IDX32, HTREE_FLAG_DECD, 32); + + _htree_test_index_same(HTREE_FLAG_IDX64, HTREE_FLAG_ASCD, 32); + _htree_test_index_same(HTREE_FLAG_IDX32, HTREE_FLAG_DECD, 32); + + kfree(hts); +} +#endif + +static int __init htree_test_init(void) +{ + const u64 v1m = 1 << 20; + + _htree_test_hash(); + +#ifdef HTREE_DEBUG_DETAIL + htree_debug_index(); + return 0; +#endif + + /* range(insert, erase, find, update) index testing */ + _htree_test_idx_range(HTREE_FLAG_IDX64, HTREE_FLAG_ASCD); + _htree_test_idx_range(HTREE_FLAG_IDX64, HTREE_FLAG_DECD); + + _htree_test_idx_range(HTREE_FLAG_IDX32, HTREE_FLAG_ASCD); + _htree_test_idx_range(HTREE_FLAG_IDX32, HTREE_FLAG_DECD); + + /* random index testing */ + _htree_test_idx_random(HTREE_FLAG_IDX64, HTREE_FLAG_DECD, v1m); + _htree_test_idx_random(HTREE_FLAG_IDX32, HTREE_FLAG_ASCD, v1m); + + /* same index testing */ + _htree_test_index_same(HTREE_FLAG_IDX64, HTREE_FLAG_ASCD, v1m); + _htree_test_index_same(HTREE_FLAG_IDX32, HTREE_FLAG_DECD, v1m); + + return 0; +} + +static void __exit htree_test_exit(void) +{ + pr_info("htree test exit.\n"); +} + +module_init(htree_test_init) +module_exit(htree_test_exit) + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("JaeJoon Jung "); +MODULE_DESCRIPTION("Hash Tree Test"); diff --git a/lib/htree.c b/lib/htree.c new file mode 100644 index 000000000000..be7b34b5d4e1 --- /dev/null +++ b/lib/htree.c @@ -0,0 +1,634 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Hash-Trees implementation + * lib/htree.c + * + * Copyright(C) 2024, JaeJoon Jung + */ + +#include + +/** + * ht_table_alloc - memory allocation of hash table + * @hts: hts->acnt increase + * return: htree: allocated memory pointer + * + * hash bits is calculated using the ht_bits_from_depth() + * that is important to decision the depth of hash tree. + * hts->sbit is determined in the _ht_hts_get_sbit() function + * in proportion to the total number of indexes. + * hash array(table) size is (1 << bits). + */ +struct hash_tree *ht_table_alloc(struct htree_state *hts) +{ + u8 bits; + u16 k, anum; + struct hash_tree *htree; + + bits = ht_bits_from_depth(hts->sbit, hts->dept); + anum = HTREE_ARRAY_SIZE(bits); + htree = (struct hash_tree *) + kmalloc_array(anum, sizeof(struct hash_tree), GFP_KERNEL); + + for (k = 0; k < anum; k++) { + INIT_HLIST_HEAD(&htree[k].head); + htree[k].next = NULL; + } + hts->acnt++; + + return htree; +} +EXPORT_SYMBOL(ht_table_alloc); + +/** + * ht_hts_alloc - memory allocation of htree_state struct + * return: hts: allocated memory pointer + * + * htree_state is the numeric data structure for operations. + * It is used to calculate the starting bit and depth of the hash tree, + * number of searches, number of memory allocations, and usage efficiency. + */ +struct htree_state *ht_hts_alloc(void) +{ + struct htree_state *hts = (struct htree_state *) + kmalloc(sizeof(struct htree_state), GFP_KERNEL); + return hts; +} +EXPORT_SYMBOL(ht_hts_alloc); + +/** + * _ht_hts_get_sbit - starting bit to determine hash table size + * @maxnr: maximum number of indexes to use in the system + * return: starting bit(stored in hts->sbit) + + * Determine the size of the hash table by choosing the starting number of + * bits for the hash tree. Increase memory usage efficiency by optimizing + * hash table size in proportion to index quantity(maxnr). + * hts->sbit enables maintain memory usage efficiency more than 80%. + */ +static u8 _ht_hts_get_sbit(u64 maxnr) +{ + u8 sbit = 0; + do { + maxnr >>= HTREE_BITS_SHIFT; + sbit++; + } while(maxnr > 0); + + return (sbit < HTREE_BITS_END) ? HTREE_BITS_END : sbit; +} + +/** + * ht_hts_clear_init - clear & init of htree statistic structure + * @hts: htree_state struct pointer + * @maxnr: maximum number of indexes to use in the system + * @idxt: type of index [0:64bits, 1:32bits] + * @sort: index sorting type [0:ascending, 1:descending] + * + * hts->sbit is determined in the _ht_hts_get_sbit() function + * in proportion to the total number of indexes(maxnr). + */ +void ht_hts_clear_init(struct htree_state *hts, u64 maxnr, u8 idxt, u8 sort) +{ + memset(hts, 0, sizeof(struct htree_state)); + + hts->sbit = _ht_hts_get_sbit(maxnr); + hts->idxt = idxt; + hts->sort = sort; +} +EXPORT_SYMBOL(ht_hts_clear_init); + +/** + * __ht_find - private function to call recursively to find index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @index: user index to find + * @rdata: node data at the searched location to return + * @rtree: hash tree at the searched location to return + */ +static enum ht_flags __ht_find(struct htree_state *hts, struct hash_tree *htree, + u64 index, struct htree_data **rdata, struct hash_tree **rtree) +{ + struct htree_data *pos; + u8 bits, ncnt; + +_retry: + *rtree = htree; + ncnt = ht_ncnt_get(htree[hts->hkey].next); + if (ncnt == 0) + goto _next_step; + + hlist_for_each_entry(pos, &htree[hts->hkey].head, hnode) { + *rdata = pos; + hts->wcnt++; + if (pos->index > index) { + if (hts->sort == HTREE_FLAG_ASCD) + return htf_find_gt; + + } else if (pos->index < index) { + if (hts->sort == HTREE_FLAG_DECD) + return htf_find_lt; + + } else { + return htf_find; + } + } + +_next_step: + htree = ht_ncnt_pointer(htree[hts->hkey].next); + if (htree) { + hts->dept++; + bits = ht_bits_from_depth(hts->sbit, hts->dept); + hts->hkey = ht_get_hkey(index, hts->dept, bits, hts->idxt); + goto _retry; + } + return htf_none; +} + +/** + * ht_find - private function to find index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @index: user index to find + * @rdata: node data at the searched location to return(**) + * @rtree: hash tree at the searched location to return(**) + */ +static enum ht_flags _ht_find(struct htree_state *hts, struct hash_tree *htree, + u64 index, struct htree_data **rdata, struct hash_tree **rtree) +{ + enum ht_flags ret; + + hts->wcnt = 0; + hts->dept = 0; + hts->hkey = ht_get_hkey(index, 0, hts->sbit, hts->idxt); + + ret = __ht_find(hts, htree, index, rdata, rtree); + + return ret; +} + +/** + * ht_find - public function to find index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @index: user index to find + * + * return: rdata: found node data to return + */ +struct htree_data *ht_find(struct htree_state *hts, + struct hash_tree *htree, u64 index) +{ + struct htree_data *rdata = NULL; + struct hash_tree *rtree; + + if (_ht_find(hts, htree, index, &rdata, &rtree) == htf_find) + return rdata; + return NULL; +} +EXPORT_SYMBOL(ht_find); + +/** + * _ht_move_to_next - private function to call recursively to move index + * @hts: htree_state pointer + * @sdata: hash list node + * @prev: previous hash_tree pointer + * @ntree: next hash_tree + * + * The number of lists linking to the same hash key is HTREE_MAX_NCNT. + * If this is exceeded, it moves to the next hash table in sequence. + */ +static void _ht_move_to_next(struct htree_state *hts, struct htree_data *sdata, + struct hash_tree *prev, struct hash_tree *ntree) +{ + u8 bits, ncnt, dept = hts->dept; + u16 hkey; + struct htree_data *edata; + struct htree_data *pos, *rdata = NULL; + enum ht_flags htf; + +_retry: + edata = sdata; + pos = sdata; + /* find the end node on the current(prev) */ + hlist_for_each_entry_from(pos, hnode) + edata = pos; + + hlist_del(&edata->hnode); + INIT_HLIST_NODE(&edata->hnode); + WRITE_ONCE(prev->next, ht_ncnt_dec(prev->next, 1)); + + dept++; + bits = ht_bits_from_depth(hts->sbit, dept); + hkey = ht_get_hkey(edata->index, dept, bits, hts->idxt); + + if (!ntree) { + ncnt = ht_ncnt_get(prev->next); + ntree = ht_table_alloc(hts); + WRITE_ONCE(prev->next, ht_ncnt_set(ntree, ncnt)); + htree_add_head(ntree, &edata->hnode, hkey); + goto _next; + } + + ncnt = ht_ncnt_get(ntree[hkey].next); + if (ncnt == 0) { + htree_add_head(ntree, &edata->hnode, hkey); + goto _next; + } + + htf = htf_none; + hlist_for_each_entry(pos, &ntree[hkey].head, hnode) { + rdata = pos; + if (hts->sort == HTREE_FLAG_ASCD && + pos->index >= edata->index) { + htf = htf_find_gt; + hlist_add_before(&edata->hnode, &rdata->hnode); + break; + } + if (hts->sort == HTREE_FLAG_DECD && + pos->index <= edata->index) { + htf = htf_find_lt; + hlist_add_before(&edata->hnode, &rdata->hnode); + break; + } + } + if (htf < htf_find_lt) + hlist_add_behind(&edata->hnode, &rdata->hnode); + +_next: + WRITE_ONCE(ntree[hkey].next, ht_ncnt_inc(ntree[hkey].next, 1)); + + ncnt = ht_ncnt_get(ntree[hkey].next); + if (ncnt > HTREE_MAX_NCNT(dept)) { + sdata = edata; + prev = &ntree[hkey]; + ntree = ht_ncnt_pointer(ntree[hkey].next); + goto _retry; + } +} + +/** + * ht_insert - insert the user index into the hash tree. + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @index: user index to insert + * @rdata: destination data pointer of hlist node + * @hdata: source data pointer of hlist node + * @htf: working flags + * + * The flow linked to a specific depth of the hash tree by a hash key: + * user index --> hash key --> hash tree --> depth --> hash lists + */ +static void _ht_insert(struct htree_state *hts, struct hash_tree *htree, + struct htree_data *rdata, struct htree_data *hdata, + enum ht_flags htf, enum ht_flags req) +{ + struct htree_data *edata = hdata; + u64 index = hdata->index; + u8 bits, ncnt; + + bits = ht_bits_from_depth(hts->sbit, hts->dept); + hts->hkey = ht_get_hkey(index, hts->dept, bits, hts->idxt); + ncnt = ht_ncnt_get(htree[hts->hkey].next); + + if (ncnt == 0) { + htree_add_head(htree, &hdata->hnode, hts->hkey); + goto _finish; + } + + /* + * if (hts->sort == HTREE_FLAG_ASCD) then htf is htf_find_gt + * if (hts->sort == HTREE_FLAG_DECD) then htf is htf_find_lt + */ + if (htf == htf_find_gt || htf == htf_find_lt) { + hlist_add_before(&hdata->hnode, &rdata->hnode); + edata = rdata; + if (hts->dept == 0 && hts->wcnt == 1) + hts->most = hts->hkey; + } else { + hlist_add_behind(&hdata->hnode, &rdata->hnode); + edata = hdata; + } + +_finish: + if (req == htf_ins) { + WRITE_ONCE(htree[hts->hkey].next, + ht_ncnt_inc(htree[hts->hkey].next, 1)); + hts->dcnt++; + ncnt++; + } + + if (ncnt > HTREE_MAX_NCNT(hts->dept)) { + _ht_move_to_next(hts, edata, &htree[hts->hkey], + ht_ncnt_pointer(htree[hts->hkey].next)); + } +} + +/** + * ht_insert - public function to insert udata + * @hts: htree_state pointer + * @htree: hash_tree root pointer + * @udata: data_struct to insert + * @req: flag to proceed further after index insertion + * + * return: rdata: searched node data to return + * + * 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. + * + * insert flow: + * _ht_find() --> finding rdata, rtree --> _ht_insert() + */ +struct htree_data *ht_insert(struct htree_state *hts, struct hash_tree *htree, + struct htree_data *hdata, enum ht_flags req) +{ + struct htree_data *rdata = NULL; + struct hash_tree *rtree = NULL; + enum ht_flags htf; + + htf = _ht_find(hts, htree, hdata->index, &rdata, &rtree); + + _ht_insert(hts, rtree, rdata, hdata, htf, req); + + if (htf == htf_find && req == htf_erase) { + hlist_del(&rdata->hnode); + return rdata; + } + return NULL; +} +EXPORT_SYMBOL(ht_insert); + +/** + * ___ht_erase - delete an empty hash tree + * @hts: htree_state pointer + * @htree: hash_tree to check if empty + * @bits: bits of this hash tree + */ +static enum ht_flags ___ht_erase(struct htree_state *hts, + struct hash_tree *htree, u8 bits) +{ + u16 k; + u16 anum = HTREE_ARRAY_SIZE(bits); + + for (k = 0; k < anum; k++) + if (htree[k].next) + break; + + if (k == anum) { + kfree(htree); + hts->acnt--; + hts->dept--; + return htf_freed; + } + return htf_erase; +} + +/** + * __ht_erase - private function to call recursively to erase index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @rdata: searched node data to erase + * @index: user index to erase + */ +static int __ht_erase(struct htree_state *hts, struct hash_tree *htree, + struct htree_data **rdata, u64 index) +{ + struct hash_tree *_next; + struct htree_data *pos; + struct hlist_node *tmp; + enum ht_flags ret = htf_none; + u8 bits, ncnt; + u16 key = hts->hkey; + + ncnt = ht_ncnt_get(htree[key].next); + bits = ht_bits_from_depth(hts->sbit, hts->dept); + + if (ncnt == 0) + goto _next_step; + + hlist_for_each_entry_safe(pos, tmp, &htree[key].head, hnode) { + if (pos->index == index) { + hlist_del(&pos->hnode); + ncnt--; + hts->dcnt--; + WRITE_ONCE(htree[key].next, + ht_ncnt_set(htree[key].next, ncnt)); + *rdata = pos; + ret = htf_erase; + break; + } else { + if (hts->sort == HTREE_FLAG_ASCD && pos->index > index) + break; + if (hts->sort == HTREE_FLAG_DECD && pos->index < index) + break; + } + } + + if (ncnt == 0) + ret = ___ht_erase(hts, htree, bits); + + if (ret > htf_none) /* erased or freed */ + return ret; +_next_step: + _next = ht_ncnt_pointer(htree[key].next); + if (_next) { + hts->dept++; + bits = ht_bits_from_depth(hts->sbit, hts->dept); + hts->hkey = ht_get_hkey(index, hts->dept, bits, hts->idxt); + + /* must be recursive call */ + ret = __ht_erase(hts, _next, rdata, index); + + if (ret == htf_freed) { + WRITE_ONCE(htree[key].next, ht_ncnt_set(NULL, ncnt)); + ret = htf_erase; + } + } + return (ret > htf_none) ? htf_erase : htf_none; +} + +/** + * _ht_erase - private function to erase index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @rdata: searching node data to erase + * @index: user index to erase + */ +static enum ht_flags _ht_erase(struct htree_state *hts, + struct hash_tree *htree, struct htree_data **rdata, u64 index) +{ + hts->dept = 0; + hts->hkey = ht_get_hkey(index, 0, hts->sbit, hts->idxt); + + if (__ht_erase(hts, htree, rdata, index) >= htf_erase) + return htf_erase; + + return htf_none; +} + +/** + * ht_erase - public function to erase index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @index: user index to erase + * + * return: rdata: searched node data to erase + */ +struct htree_data *ht_erase(struct htree_state *hts, + struct hash_tree *htree, u64 index) +{ + struct htree_data *rdata = NULL; + + if (_ht_erase(hts, htree, &rdata, index) == htf_erase) + return rdata; + + return NULL; +} +EXPORT_SYMBOL(ht_erase); + +/** + * __ht_free_all - private function to call recursively to free hash tree + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @acnt: freed allocated hash tree count + * @dcnt: freed node data count + */ +static void __ht_free_all(struct htree_state *hts, + struct hash_tree *htree, s32 *acnt, u64 *dcnt) +{ + u8 bits, ncnt; + u16 k, anum, pnum; + struct htree_data *pos; + struct hlist_node *tmp; + struct hash_tree *_next; + + bits = ht_bits_from_depth(hts->sbit, hts->dept); + anum = HTREE_ARRAY_SIZE(bits); + + for (k = 0; k < anum; k++) { + ncnt = ht_ncnt_get(htree[k].next); + if (ncnt > 0) { + bits = ht_bits_from_depth(hts->sbit, hts->dept); + hlist_for_each_entry_safe(pos, tmp, + &htree[k].head, hnode) { + hlist_del(&pos->hnode); + (*dcnt)++; + } + } + _next = ht_ncnt_pointer(htree[k].next); + if (_next) { + hts->dept++; + pnum = anum; + /* recursive call */ + __ht_free_all(hts, _next, acnt, dcnt); + anum = pnum; + hts->dept--; + } else { + continue; + } + } + if (htree) { + (*acnt)++; + kfree(htree); /* free hash table[asize] */ + } +} + +/** + * ht_destroy - public function to free hash tree + * @hts: htree_state pointer + * @htree: hash_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) +{ + s32 acnt = 0; + u64 dcnt = 0; + + if (hts->acnt == 0 && hts->dcnt == 0) + return htf_ok; + + hts->dept = 0; + __ht_free_all(hts, htree, &acnt, &dcnt); + + hts->acnt -= acnt; + hts->dcnt -= dcnt; + + return (hts->dept == 0 && hts->dcnt == 0 && hts->acnt == 0) ? + htf_ok : htf_none; +} +EXPORT_SYMBOL(ht_destroy); + +/** + * __ht_statis - private function to call recursively to calculate nodes + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @acnt: allocated hash tree count + * @dcnt: node data count + */ +static void __ht_statis(struct htree_state *hts, + struct hash_tree *htree, s32 *acnt, u64 *dcnt) +{ + u8 bits, ncnt; + u16 k, anum, pnum; + struct hash_tree *_next; + + bits = ht_bits_from_depth(hts->sbit, hts->dept); + anum = HTREE_ARRAY_SIZE(bits); + + hts->asum += anum; + (*acnt)++; + + for (k = 0; k < anum; k++) { + ncnt = ht_ncnt_get(htree[k].next); + if (ncnt > 0) { + (*dcnt) += ncnt; + } + _next = ht_ncnt_pointer(htree[k].next); + if (_next) { + hts->dept++; + if (hts->dept > hts->dmax) + hts->dmax = hts->dept; + pnum = anum; + /* recursive call */ + __ht_statis(hts, _next, acnt, dcnt); + anum = pnum; + hts->dept--; + } else { + continue; + } + } +} + +/** + * ht_statis - public function to calculate nodes information + * @hts: htree_state pointer + * @htree: hash_tree pointer + * @acnt: allocated hash tree count to return + * @dcnt: node data count to return + */ +void ht_statis(struct htree_state *hts, + struct hash_tree *htree, s32 *acnt, u64 *dcnt) +{ + hts->asum = 0; + hts->dept = 0; + hts->dmax = 0; + + __ht_statis(hts, htree, acnt, dcnt); +} +EXPORT_SYMBOL(ht_statis); + +/** + * ht_most_index - get most smallest and largest index + * @hts: htree_state pointer + * @htree: hash_tree pointer + * + * if sorting flag is HTREE_FLAG_ASCD, first hash table has the smallest index. + * if sorting flag is HTREE_FLAG_DECD, first hash table has the largest index. + * hts->most has the hash key position, algorithm O(1). + */ +struct htree_data *ht_most_index(struct htree_state *hts, struct hash_tree *htree) +{ + return hlist_entry_safe(htree[hts->most].head.first, + struct htree_data, hnode); +} +EXPORT_SYMBOL(ht_most_index);