From nobody Wed Feb 11 23:56:34 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C66A3C77B7E for ; Tue, 2 May 2023 04:26:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233297AbjEBE0q (ORCPT ); Tue, 2 May 2023 00:26:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41710 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232598AbjEBE0o (ORCPT ); Tue, 2 May 2023 00:26:44 -0400 Received: from mout-p-202.mailbox.org (mout-p-202.mailbox.org [80.241.56.172]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 44F1F3AA4 for ; Mon, 1 May 2023 21:26:42 -0700 (PDT) Received: from smtp1.mailbox.org (smtp1.mailbox.org [10.196.197.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-p-202.mailbox.org (Postfix) with ESMTPS id 4Q9RqM00V6z9sdn for ; Tue, 2 May 2023 06:26:39 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mailbox.org; s=mail20150812; t=1683001599; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=8JIidON7ObJRXtw6ghF6hznpzFYqEMz6CIXHrODRrKU=; b=mIYx5D61w/xSoYvxqUcy2Q7+ecKGjsvfrAY2q74R8qa0YbHCp8HQ16Rq62+YlIagLwEbz0 TuWCyYnt2Pjr2Gfr9ozCMriHoAJeUSkv73kNGl/TemvodGAP3W/6U4dslChVQ7V+dOH3QW /jpAUO8rWjYxGYC7LrLBr23uoMYB+RJ2skj8/uH627V+gwu3308GuZjZvs2IseNFZjkyu8 P68ftSSvTjHX/zjp7ECjM5u1UDckeo7HCV2I1hRE6tOSx5M15jnDIJmgfP+dS3tEDTCLkF 9YeVyd3ztzCwRaD3W7GED4pxRZjQytu5KKxfVNz7tAdf1fQtkdryKomJvOq0eA== Message-ID: Subject: Library: [RFC PATCH 2/3] btree_blue - A simple btree with fast linear traverse From: liuwf To: linux-kernel@vger.kernel.org Date: Tue, 02 May 2023 00:26:27 -0400 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-MBO-RS-META: rwm4jpzcucjxem4n51xff7ttwdx4gzyg X-MBO-RS-ID: 335a4a434b017783020 Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Library: [RFC PATCH 2/3] btree_blue - A simple btree with fast linear trave= rse From: Liu Weifeng 4019c26b5c0d5f6b Signed-off-by: Liu Weifeng 4019c26b5c0d5f6b --- include/linux/btree_blue.h | 4 +- lib/btree_blue.c | 170 +++++++++++++++++++++++++------------ 2 files changed, 118 insertions(+), 56 deletions(-) diff --git a/include/linux/btree_blue.h b/include/linux/btree_blue.h index 2f1a7781c77b..62217b96cb4e 100644 --- a/include/linux/btree_blue.h +++ b/include/linux/btree_blue.h @@ -17,16 +17,16 @@ struct btree_blue_node_cb; =20 struct btree_blue_head { unsigned long *node; - mempool_t *mempool; =20 u16 node_size; + u16 leaf_size; u16 stub_base; u8 keylen; u8 slot_width; u8 height; u8 reserved[1]; =20 - u16 vols[MAX_TREE_HEIGHT + 1]; + u16 slot_vols[MAX_TREE_HEIGHT + 1]; }; =20 void *btree_blue_alloc(gfp_t gfp_mask, void *pool_data); diff --git a/lib/btree_blue.c b/lib/btree_blue.c index ddde34f23139..62f7baa43044 100644 --- a/lib/btree_blue.c +++ b/lib/btree_blue.c @@ -32,8 +32,10 @@ struct btree_blue_stub { unsigned long *next; }; =20 -static struct kmem_cache *btree_blue_cachep; +static struct kmem_cache *btree_blue_cache_node; +static struct kmem_cache *btree_blue_cache_leaf; =20 +/* void *btree_blue_alloc(gfp_t gfp_mask, void *pool_data) { return kmem_cache_alloc(btree_blue_cachep, gfp_mask); @@ -45,18 +47,36 @@ void btree_blue_free(void *element, void *pool_data) kmem_cache_free(btree_blue_cachep, element); } EXPORT_SYMBOL_GPL(btree_blue_free); +*/ =20 static unsigned long *btree_blue_node_alloc(struct btree_blue_head *head, - gfp_t gfp) + int level, gfp_t gfp) { unsigned long *node; + int size; + + if (likely(level =3D=3D 1)) { + size =3D head->leaf_size; + node =3D kmem_cache_alloc(btree_blue_cache_leaf, gfp); + } else { + size =3D head->node_size; + node =3D kmem_cache_alloc(btree_blue_cache_node, gfp); + } =20 - node =3D mempool_alloc(head->mempool, gfp); if (likely(node)) - memset(node, 0, head->node_size); + memset(node, 0, size); + return node; } =20 +static void btree_blue_node_free(unsigned long *node, int level) +{ + if (likely(level =3D=3D 1)) + kmem_cache_free(btree_blue_cache_leaf, node); + else + kmem_cache_free(btree_blue_cache_node, node); +} + static int longcmp(const unsigned long *l1, const unsigned long *l2, size_= t n) { size_t i; @@ -422,9 +442,12 @@ void *btree_blue_prev_or_next(struct btree_blue_head *= head, return NULL; =20 slots_nr =3D node->slots_info.slots_nr; + i =3D geteqv(head, node, key); + /* for (i =3D 0; i < slots_nr; i++) if (keycmp(head, node, i, key) =3D=3D 0) break; + */ if (i =3D=3D slots_nr) return NULL; =20 @@ -516,10 +539,12 @@ size_t btree_blue_traverse_from_key(struct btree_blue= _head *head, return total; =20 slots_nr =3D node->slots_info.slots_nr; + i =3D geteqv(head, node, key); + /* for (i =3D 0; i < slots_nr; i++) if (keycmp(head, node, i, (unsigned long *)key) =3D=3D 0) break; - + */ if (i =3D=3D slots_nr) return total; =20 @@ -619,7 +644,8 @@ static int btree_blue_grow(struct btree_blue_head *head= , gfp_t gfp) { struct btree_blue_node_cb *node, *node_h; =20 - node =3D (struct btree_blue_node_cb *)btree_blue_node_alloc(head, gfp); + node =3D (struct btree_blue_node_cb *)btree_blue_node_alloc( + head, head->height + 1, gfp); if (!node) return -ENOMEM; =20 @@ -648,9 +674,10 @@ static void btree_blue_shrink(struct btree_blue_head *= head) BUG_ON(node->slots_info.slots_nr > 1); =20 head->node =3D bval(head, node, 0); + btree_blue_node_free((unsigned long *)node, head->height); head->height--; =20 - mempool_free(node, head->mempool); + //mempool_free(node, head->mempool); } =20 static int btree_blue_insert_level(struct btree_blue_head *head, @@ -684,13 +711,13 @@ static int btree_blue_insert_level(struct btree_blue_= head *head, =20 slots_nr =3D cb->slots_info.slots_nr; =20 - if (slots_nr =3D=3D head->vols[level]) { + if (slots_nr =3D=3D head->slot_vols[level]) { /* need to split node */ struct btree_blue_node_cb *cb_prev; struct btree_blue_stub *stub, *stub_new, *stub_prev; =20 cb_new =3D (struct btree_blue_node_cb *)btree_blue_node_alloc( - head, gfp); + head, level, gfp); if (!cb_new) return -ENOMEM; =20 @@ -698,7 +725,8 @@ static int btree_blue_insert_level(struct btree_blue_he= ad *head, bkey(head, cb, slots_nr / 2 - 1), cb_new, level + 1, cb_p, gfp); if (err) { - mempool_free(cb_new, head->mempool); + //mempool_free(cb_new, head->mempool); + btree_blue_node_free((unsigned long *)cb_new, level); return err; } =20 @@ -728,7 +756,7 @@ static int btree_blue_insert_level(struct btree_blue_he= ad *head, } } =20 - BUG_ON(slots_nr >=3D head->vols[level]); + BUG_ON(slots_nr >=3D head->slot_vols[level]); =20 /* shift and insert */ //pos =3D shift_slots_on_insert(head, cb, pos, level); @@ -784,7 +812,8 @@ static void merge(struct btree_blue_head *head, int lev= el, setval(head, cb_parent, lpos + 1, cb_left); /* Remove left (formerly right) child from parent */ btree_blue_remove_level(head, bkey(head, cb_parent, lpos), level + 1); - mempool_free(cb_right, head->mempool); + //mempool_free(cb_right, head->mempool); + btree_blue_node_free((unsigned long *)cb_right, level); } =20 static void rebalance(struct btree_blue_head *head, unsigned long *key, @@ -826,7 +855,8 @@ static void rebalance(struct btree_blue_head *head, uns= igned long *key, } } =20 - mempool_free(cb_child, head->mempool); + //mempool_free(cb_child, head->mempool); + btree_blue_node_free((unsigned long *)cb_child, level); return; } =20 @@ -839,7 +869,7 @@ static void rebalance(struct btree_blue_head *head, uns= igned long *key, cb_left =3D bval(head, cb_parent, i - 1); slots_nr_left =3D cb_left->slots_info.slots_nr; =20 - if (slots_nr_left + slots_nr <=3D head->vols[level]) { + if (slots_nr_left + slots_nr <=3D head->slot_vols[level]) { merge(head, level, cb_left, cb_child, cb_parent, i - 1); return; } @@ -849,7 +879,7 @@ static void rebalance(struct btree_blue_head *head, uns= igned long *key, cb_right =3D bval(head, cb_parent, i + 1); slots_nr_right =3D cb_right->slots_info.slots_nr; =20 - if (slots_nr + slots_nr_right <=3D head->vols[level]) { + if (slots_nr + slots_nr_right <=3D head->slot_vols[level]) { merge(head, level, cb_child, cb_right, cb_parent, i); return; } @@ -891,7 +921,7 @@ static void *btree_blue_remove_level(struct btree_blue_= head *head, _shift_slots(head, cb, pos, pos + 1, slots_nr - pos - 1); cb->slots_info.slots_nr--; =20 - if (cb->slots_info.slots_nr < head->vols[level] / 2 - 2) { + if (cb->slots_info.slots_nr < head->slot_vols[level] / 2 - 2) { if (level < head->height) rebalance(head, key, level, cb, cb_p); else if (cb->slots_info.slots_nr =3D=3D 1) @@ -910,35 +940,12 @@ void *btree_blue_remove(struct btree_blue_head *head,= unsigned long *key) } EXPORT_SYMBOL_GPL(btree_blue_remove); =20 -static inline void __btree_blue_init(struct btree_blue_head *head, - int node_size, int keylen, int flags) -{ - int vol; - - head->node =3D NULL; - head->height =3D 0; - head->node_size =3D node_size; - head->keylen =3D (keylen * BITS_PER_BYTE) / BITS_PER_LONG; - head->slot_width =3D - (VALUE_LEN * BITS_PER_BYTE) / BITS_PER_LONG + head->keylen; - - vol =3D (node_size - sizeof(struct btree_blue_node_cb)) / - (head->slot_width * sizeof(long)); - for (int i =3D 2; i < MAX_TREE_HEIGHT + 1; i++) - head->vols[i] =3D vol; - vol =3D (node_size - sizeof(struct btree_blue_node_cb) - - sizeof(struct btree_blue_stub)) / - (head->slot_width * sizeof(long)); - head->vols[0] =3D head->vols[1] =3D vol; - - head->stub_base =3D sizeof(struct btree_blue_node_cb) + - head->vols[1] * (head->slot_width * sizeof(long)); -} - int __must_check btree_blue_init(struct btree_blue_head *head, int node_size_in_byte, int key_len_in_byte, int flags) { + int x; + if (node_size_in_byte % L1_CACHE_BYTES) return -EINVAL; =20 @@ -950,27 +957,78 @@ int __must_check btree_blue_init(struct btree_blue_he= ad *head, (key_len_in_byte !=3D 2 * sizeof(unsigned long))) return -EINVAL; =20 - btree_blue_cachep =3D kmem_cache_create("btree_blue_node_buf", - node_size_in_byte, 0, - SLAB_HWCACHE_ALIGN, NULL); - if (!btree_blue_cachep) - return -ENOMEM; + //__btree_blue_init(head, node_size_in_byte, key_len_in_byte, flags); =20 - __btree_blue_init(head, node_size_in_byte, key_len_in_byte, flags); + //head->mempool =3D + // mempool_create(0, btree_blue_alloc, btree_blue_free, NULL); + //if (!head->mempool) + // return -ENOMEM; + //return 0; =20 - head->mempool =3D - mempool_create(0, btree_blue_alloc, btree_blue_free, NULL); - if (!head->mempool) + head->node =3D NULL; + head->height =3D 0; + + head->keylen =3D (key_len_in_byte * BITS_PER_BYTE) / BITS_PER_LONG; + head->slot_width =3D + (VALUE_LEN * BITS_PER_BYTE) / BITS_PER_LONG + head->keylen; + + //head->node_size =3D node_size; + + if (node_size_in_byte > 512) + x =3D 512; + else + x =3D node_size_in_byte; + head->node_size =3D x; + head->leaf_size =3D node_size_in_byte; + + btree_blue_cache_node =3D kmem_cache_create("btree_blue_cache_node", + head->node_size, 0, + SLAB_HWCACHE_ALIGN, NULL); + if (!btree_blue_cache_node) return -ENOMEM; + + btree_blue_cache_leaf =3D kmem_cache_create("btree_blue_cache_leaf", + head->leaf_size, 0, + SLAB_HWCACHE_ALIGN, NULL); + if (!btree_blue_cache_leaf) + return -ENOMEM; + + for (int i =3D 2; i < MAX_TREE_HEIGHT + 1; i++) { + x =3D (head->node_size - sizeof(struct btree_blue_node_cb)) / + (head->slot_width * sizeof(long)); + head->slot_vols[i] =3D x; + } + + x =3D (head->leaf_size - sizeof(struct btree_blue_node_cb) - + sizeof(struct btree_blue_stub)) / + (head->slot_width * sizeof(long)); + head->slot_vols[0] =3D head->slot_vols[1] =3D x; + + head->stub_base =3D + sizeof(struct btree_blue_node_cb) + + head->slot_vols[1] * (head->slot_width * sizeof(long)); + return 0; } EXPORT_SYMBOL_GPL(btree_blue_init); =20 void btree_blue_destroy(struct btree_blue_head *head) { - mempool_free(head->node, head->mempool); - mempool_destroy(head->mempool); - head->mempool =3D NULL; + //mempool_free(head->node, head->mempool); + //mempool_destroy(head->mempool); + //head->mempool =3D NULL; + + if (btree_blue_cache_node) { + kmem_cache_destroy(btree_blue_cache_node); + btree_blue_cache_node =3D NULL; + } + + if (btree_blue_cache_leaf) { + kmem_cache_destroy(btree_blue_cache_leaf); + btree_blue_cache_leaf =3D NULL; + } + + head->node =3D NULL; } EXPORT_SYMBOL_GPL(btree_blue_destroy); =20 @@ -981,7 +1039,11 @@ static int __init btree_blue_module_init(void) =20 static void __exit btree_blue_module_exit(void) { - kmem_cache_destroy(btree_blue_cachep); + if (btree_blue_cache_node) + kmem_cache_destroy(btree_blue_cache_node); + + if (btree_blue_cache_leaf) + kmem_cache_destroy(btree_blue_cache_leaf); } =20 module_init(btree_blue_module_init); --=20 2.30.2