From patchwork Fri Aug 2 05:17:00 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: JaeJoon Jung X-Patchwork-Id: 13751098 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 450BBC52D71 for ; Fri, 2 Aug 2024 05:17:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6F5826B0085; Fri, 2 Aug 2024 01:17:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6A54F6B0088; Fri, 2 Aug 2024 01:17:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 56CDB6B0089; Fri, 2 Aug 2024 01:17:18 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 368C96B0085 for ; Fri, 2 Aug 2024 01:17:18 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id B0C94160575 for ; Fri, 2 Aug 2024 05:17:17 +0000 (UTC) X-FDA: 82406146914.03.397139A Received: from mail-pl1-f172.google.com (mail-pl1-f172.google.com [209.85.214.172]) by imf26.hostedemail.com (Postfix) with ESMTP id 11288140004 for ; Fri, 2 Aug 2024 05:17:15 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BMG9c+5s; spf=pass (imf26.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.214.172 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=1722575759; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:references:dkim-signature; bh=mzQPgYXXMRWw+msy5ZgzdvZDXWhdSZVTosMfme1JQME=; b=xjOnSxUzjAaUkn98y3Wwvg+oHaW1aVvDiq8cnDOUC7EHH4nN7Gu+4OUeuZbFUbUbUNnK7H x1VvXH+hq2YaVe7PFI9Rv812MiyWszcOSW5sJn9UeuRb8Nv6COLJ8Nfqz1wFbl/TXsVv9i XE6JBvAMO4Q6yH3eU8ZJvU0Hm75vFJY= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BMG9c+5s; spf=pass (imf26.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.214.172 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1722575759; a=rsa-sha256; cv=none; b=O8Df8YTOaP50Raa6NdIQ89mm0oC/sm2DLfqfQD/LSdeACI5vK673F843Semx88EQbjFhd+ MrjbmReoFgFMwwTJ1ouy93+ECSDRl+DJBvFsOJd0c1VGGmV02RGDEoz/u6LxJ9MugGSLKN fQlhocl0msmrvUh9lfGgjeMHPeZc7PM= Received: by mail-pl1-f172.google.com with SMTP id d9443c01a7336-1fd69e44596so21273215ad.1 for ; Thu, 01 Aug 2024 22:17:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722575835; x=1723180635; darn=kvack.org; h=message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=mzQPgYXXMRWw+msy5ZgzdvZDXWhdSZVTosMfme1JQME=; b=BMG9c+5sfbxVoa4CQ7PGQn561QhvtETvlIvLo97BXnINQMxTJGE8icMKUB46t1AMfY xCsfQnbiuKPOtL4hgm4jKMftP0HOj/NA7J1HFMFvwkKVm9wIhfOBcK3yvZ8TlFb5n6QX CGLGw+8xd86DnbE8YAwFH6a098cxvjYOoMnN+J1JvchetwMPbt+tFPhAz5SMA7ixlhw1 FJc/Cwwb32etxbCK7JaLe+ngLuDj1UU7ede94gwTFVGXD0wEV8r9XWYCx49W0goXeNlS aeQQihZ6tXx+3pBJmQF3+DhyVg7izbRc4d5BvuqAnoWNwrIc40gwpYvkOIOm61ptLwYc gZrQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722575835; x=1723180635; h=message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mzQPgYXXMRWw+msy5ZgzdvZDXWhdSZVTosMfme1JQME=; b=YvxGfW8pQ2X8WulrFYdISzJGtIQhrB5kuwYLKxRUvmGe2eaPM47GvZYzcUcoFnxIZF DH+I9XaUYEJByIHrvkbPOZn+9MvsLAuzmtAPYp7+/iMQacls2fH+uKNSBLcJGdD/TiV9 PpJxumgdHl8ou5nGlsFXKcoWXmPvZRYarM5axUA4P15wSVzzpmJVlomN3fxq3KufLKvW b5iIHONfnbrQurNl6zpziRPyzjbbGHhMoj9k2S2JJCn09Pv1zKUJh1O6ilHokogNWGPS uzGKdYQQyjg688v59NlVJg3+TYpMQspFMVXbphXRQauBM/DvFUFRL10GDNHslWUZNvLh JV5g== X-Forwarded-Encrypted: i=1; AJvYcCVUwEt+NlWq2W1jlDV9UEhJSwK/JivtmpbrT6HGRHgM7pUh7nCtYC9s/Wv+q6GYrR07oJ5+PyyVSd6Fy9fhWYjjJyU= X-Gm-Message-State: AOJu0YxowksswbF/jpms7YSyPKaeFETJRS5oljy6A8ltIRSllGRiI2ia iirKbjmPQQzQxU2eA6Ra6xwpD84Gnp6JSRpQdl2YoADouPGpcwSx X-Google-Smtp-Source: AGHT+IGmSneQzIx8fc2d042dCc2cdpSWM3j7hQV2KJJwF4AwLAZ6KFQaFmXW2t5txQbHjXXIcT1QHg== X-Received: by 2002:a17:903:247:b0:1fd:74ac:e6b8 with SMTP id d9443c01a7336-1ff57b60fffmr40602005ad.7.1722575834590; Thu, 01 Aug 2024 22:17:14 -0700 (PDT) Received: from localhost.localdomain ([180.69.210.41]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1ff5929404dsm7919805ad.245.2024.08.01.22.17.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 01 Aug 2024 22:17:13 -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 2/2] lib/htree: Modified lib/Makefile and lib/Kconfig to build htree Date: Fri, 2 Aug 2024 14:17:00 +0900 Message-Id: <20240802051700.8234-1-rgbi3307@gmail.com> X-Mailer: git-send-email 2.17.1 X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 11288140004 X-Stat-Signature: 43xkgi4ano69s3nsgfeomcuxjb1q8sem X-Rspam-User: X-HE-Tag: 1722575835-865673 X-HE-Meta: U2FsdGVkX18+nm3Q5wNlfv0ftsW1ey0i74wHIN2fok/C63bI8kgpoQF+PU8u049x968/XHURmrx+DApAXEl2MEErSm67FMyXpJ2yElXc6aP/Vl8hllSZcH4vCQ8Rj3bfAyyRzmlc/PF5GPsa9KWLXK2j3hKeWdTAK9AjiBBVysbR/RM17iE9rLeyQdEKplY67InCYVeic6fqdVEk50w91OsAjJNaaBbnJ311UfhfiWQgkoS8Qk9QgbiiSzd7iZd3kKh4dRh6wZFDCjZTwOw5it8mqtD+IYZPq4I4kJwSSluxfU5BPDtKQ5X3TGzGctFlOXr2CoZx6ZOoYcyVXvGHUdMup2qU/70/dLzd1qRBTjEuoQ3wdzctoeL0EcO7Ig0Eka2n7l7pCbQs31mlLQIyxjcDpUZzZdO6CrCPZmaFMICG+OnBI1+GmKFhBF2+0rA6PUJIn/2af8DCn8aVTaIHLkAlMNIvXqHuG+5nlGpVuWvzhQ+ETo1ktw3yUzmxTWzZlz4wzE0DK8/BGt7XVsnTKfScNGbLkV9jIKlNhMZd0MkPOXyNobGlE7kN3s5MerByHpE1J3EYx4VIJvBw+WclkUfcDAqpbR1PUkinV0LQpujk8ktpm+/HEbSMZ1fjY+Sa5GH+2B1sO+V5Dgr7episvX5oiiGjLIjbLSwyHjdKN+sNedxjXTDH1h65ZgqDmKpfZDBjE+EJv1K5F8Y71PT/JJCDUzetbwkns2SchkceEWShbDWuPqRCJ11wr4liWXF0768axF+BRgtb93QGM7fykEtkaqvlpBRY/4K97+Css95i8GdGUehTOzPVZX7WoYgHwpWqtIo95UsbD85iFmB9qzvohR6gBWEjVWpC7b67Bq/R857E0xLq5Sd6jTi0sGzOI0fearNeTnzQyz3/DZ3zc8j77s10RyHK3nJvVPRrmHK4UiOfkEziDOWOqTIL+F+qdT9RgSR29iyiD5a42W4 spElMrwb 3YQdOR0pmDFEnBH8DKhbRrLXpwJ7e4qp+HKNSTuWgQ6IEkwKtVLSLxNPZTHnhWFJW+jpUii2FqEQdxhVldYhvTtL1m/fHxsk1gB9s8iVgteUJll2RBovpKWMUhRJhv9UktCxMAmLzn4vSjT9iLldBktXfz7M8aGm5d9yoVDwrFq0l4RtAdA+64KjvBynvuLWoYEZAShfrPJhp5hGDrO9M1Kw7YZJ0jvYmWta5mc9Wz6OdjAhk/kd27Hr6ikN8ei2A5RpgovuJbCY5y0vCWIuoBZ0VGBIyyfKDa2/8sIZAWAxnlbjpgaLiu0o5zHcbYBa4lWHD4Y+RaxoiUyM= 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: add lhtree.o, htree-test.o in the lib/Makfile and Kconfig.debug add Documentation/Documentation/core-api/htree.rst Full files can be download at the link below: source files: https://github.com/kernel-bz/htree.git documents(PDF): https://github.com/kernel-bz/htree/tree/main/docs/htree=20240802.pdf I have described this in more detail with pictures in the PDF file. Signed-off-by: JaeJoon Jung --- Documentation/core-api/htree.rst | 111 +++++++++++++++++++++++++++++++ lib/Kconfig.debug | 6 ++ lib/Makefile | 4 +- 3 files changed, 120 insertions(+), 1 deletion(-) create mode 100644 Documentation/core-api/htree.rst diff --git a/Documentation/core-api/htree.rst b/Documentation/core-api/htree.rst new file mode 100644 index 000000000000..78073b413779 --- /dev/null +++ b/Documentation/core-api/htree.rst @@ -0,0 +1,111 @@ +====================================== +Hash Trees (lib/htree) in Linux Kernel +====================================== + +:Date: August 2, 2024 +:Author: JaeJoon Jung + + +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 */ + +----------------------------------------------------------------------------- +Please refer to the attached PDF for more detailed information. +----------------------------------------------------------------------------- +documents(PDF): + https://github.com/kernel-bz/htree/tree/main/docs/htree=20240802.pdf + +Thanks. diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index a30c03a66172..0a0844710e05 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2349,6 +2349,12 @@ config RBTREE_TEST A benchmark measuring the performance of the rbtree library. Also includes rbtree invariant checks. +config HTREE_TEST + tristate "Hash Tree test" + depends on DEBUG_KERNEL + help + A performance testing of the hash tree library. + config REED_SOLOMON_TEST tristate "Reed-Solomon library test" depends on DEBUG_KERNEL || m diff --git a/lib/Makefile b/lib/Makefile index 322bb127b4dc..a2ac59e9d731 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ nmi_backtrace.o win_minmax.o memcat_p.o \ - buildid.o objpool.o + buildid.o objpool.o htree.o lib-$(CONFIG_PRINTK) += dump_stack.o lib-$(CONFIG_SMP) += cpumask.o @@ -295,6 +295,8 @@ $(obj)/default.bconf: $(CONFIG_BOOT_CONFIG_EMBED_FILE) FORCE obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o +obj-$(CONFIG_HTREE_TEST) += htree-test.o + obj-$(CONFIG_PERCPU_TEST) += percpu_test.o obj-$(CONFIG_ASN1) += asn1_decoder.o