| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1231376241.3545.96.camel@johannes>
Date: Thu, 08 Jan 2009 01:57:21 +0100
From: Johannes Berg <johannes@...solutions.net>
To: Jörn Engel <joern@...fs.org>
Cc: linux-kernel@...r.kernel.org
Subject: Re: [RFC] B+Tree library V2
On Sat, 2008-11-01 at 16:59 +0100, Jörn Engel wrote:
[btree library]
Alright, back to this. I'm going to need something like the patch below
(except the update facility, which I thought I needed but then changed
my mind) which is on top of your patch. Does that look sane?
One thing that seems a little odd is requiring a btree_init(), but not
having a btree_destroy(), but rather requiring managing the mempool in
the caller (which invariably leads to two mempool pointers being
required unless callers want to look into the btree struct details)...
Do you think this is required? Could we have a btree_init/btree_destroy
instead that take care of the mempool stuff?
Another thing that I need is a visitor that deletes _some_ entries. How
can I do that? Additionally, it would be nice to be able to abort a tree
walk, when you have determined that you can't continue for whatever
reason.
johannes
---
include/linux/btree.h | 31 +++++++++++++++++++++++++-
lib/Kconfig | 2 -
lib/btree.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 90 insertions(+), 2 deletions(-)
--- wireless-testing.orig/lib/Kconfig 2009-01-07 22:58:29.000000000 +0100
+++ wireless-testing/lib/Kconfig 2009-01-07 22:58:32.000000000 +0100
@@ -137,7 +137,7 @@ config PLIST
boolean
config BTREE
- boolean
+ tristate
config HAS_IOMEM
boolean
--- wireless-testing.orig/lib/btree.c 2009-01-07 22:58:35.000000000 +0100
+++ wireless-testing/lib/btree.c 2009-01-08 00:50:37.000000000 +0100
@@ -47,6 +47,7 @@
#include <linux/cache.h>
#include <linux/kernel.h>
#include <linux/slab.h>
+#include <linux/module.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define NODESIZE MAX(L1_CACHE_BYTES, 128)
@@ -55,17 +56,20 @@ struct btree_geo btree_geo32 = {
.keylen = 1,
.no_pairs = NODESIZE / sizeof(long) / 2,
};
+EXPORT_SYMBOL_GPL(btree_geo32);
#define LONG_PER_U64 (64 / BITS_PER_LONG)
struct btree_geo btree_geo64 = {
.keylen = LONG_PER_U64,
.no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
};
+EXPORT_SYMBOL_GPL(btree_geo64);
struct btree_geo btree_geo128 = {
.keylen = 2 * LONG_PER_U64,
.no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
};
+EXPORT_SYMBOL_GPL(btree_geo128);
static struct kmem_cache *btree_cachep;
@@ -73,11 +77,13 @@ void *btree_alloc(gfp_t gfp_mask, void *
{
return kmem_cache_alloc(btree_cachep, gfp_mask);
}
+EXPORT_SYMBOL_GPL(btree_alloc);
void btree_free(void *element, void *pool_data)
{
kmem_cache_free(btree_cachep, element);
}
+EXPORT_SYMBOL_GPL(btree_free);
static unsigned long *btree_node_alloc(struct btree_head *head)
{
@@ -217,6 +223,7 @@ void btree_init(struct btree_head *head,
head->mempool = mempool;
head->gfp_mask = gfp;
}
+EXPORT_SYMBOL_GPL(btree_init);
unsigned long *btree_last(struct btree_head *head, struct btree_geo *geo)
{
@@ -231,6 +238,7 @@ unsigned long *btree_last(struct btree_h
return bkey(geo, node, 0);
}
+EXPORT_SYMBOL_GPL(btree_last);
static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
unsigned long *key)
@@ -266,6 +274,39 @@ void *btree_lookup(struct btree_head *he
return (void *)bval(geo, node, i);
return NULL;
}
+EXPORT_SYMBOL_GPL(btree_lookup);
+
+int btree_update(struct btree_head *head, struct btree_geo *geo,
+ unsigned long *key, void *val)
+{
+ int i, height = head->height;
+ unsigned long *node = head->node;
+
+ if (height == 0)
+ return -ENOENT;
+
+ for ( ; height > 1; height--) {
+ for (i = 0; i < geo->no_pairs; i++)
+ if (keycmp(geo, node, i, key) <= 0)
+ break;
+ if (i == geo->no_pairs)
+ return -ENOENT;
+ node = (unsigned long *)bval(geo, node, i);
+ if (!node)
+ return -ENOENT;
+ }
+
+ if (!node)
+ return -ENOENT;
+
+ for (i = 0; i < geo->no_pairs; i++)
+ if (keycmp(geo, node, i, key) == 0) {
+ setval(geo, node, (unsigned long)val, i);
+ return 0;
+ }
+ return -ENOENT;
+}
+EXPORT_SYMBOL_GPL(btree_update);
static int getpos(struct btree_geo *geo, unsigned long *node,
unsigned long *key)
@@ -417,6 +458,7 @@ int btree_insert(struct btree_head *head
{
return btree_insert_level(head, geo, key, (unsigned long)val, 1);
}
+EXPORT_SYMBOL_GPL(btree_insert);
static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
unsigned long *key, int level);
@@ -527,6 +569,7 @@ void *btree_remove(struct btree_head *he
return btree_remove_level(head, geo, key, 1);
}
+EXPORT_SYMBOL_GPL(btree_remove);
int btree_merge(struct btree_head *target, struct btree_head *victim,
struct btree_geo *geo, unsigned long *duplicate)
@@ -560,6 +603,7 @@ int btree_merge(struct btree_head *targe
}
return 0;
}
+EXPORT_SYMBOL_GPL(btree_merge);
static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
unsigned long *node, long opaque,
@@ -598,6 +642,7 @@ void visitorl(void *elem, long opaque, u
func(elem, opaque, *key, index);
}
+EXPORT_SYMBOL_GPL(visitorl);
void visitor32(void *elem, long opaque, unsigned long *__key, size_t index,
void *__func)
@@ -607,6 +652,7 @@ void visitor32(void *elem, long opaque,
func(elem, opaque, *key, index);
}
+EXPORT_SYMBOL_GPL(visitor32);
void visitor64(void *elem, long opaque, unsigned long *__key, size_t index,
void *__func)
@@ -616,6 +662,7 @@ void visitor64(void *elem, long opaque,
func(elem, opaque, *key, index);
}
+EXPORT_SYMBOL_GPL(visitor64);
void visitor128(void *elem, long opaque, unsigned long *__key, size_t index,
void *__func)
@@ -625,6 +672,7 @@ void visitor128(void *elem, long opaque,
func(elem, opaque, key[0], key[1], index);
}
+EXPORT_SYMBOL_GPL(visitor128);
size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
long opaque,
@@ -640,6 +688,7 @@ size_t btree_visitor(struct btree_head *
func2, 0, head->height, 0);
return count;
}
+EXPORT_SYMBOL_GPL(btree_visitor);
size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
long opaque,
@@ -656,6 +705,7 @@ size_t btree_grim_visitor(struct btree_h
__btree_init(head);
return count;
}
+EXPORT_SYMBOL_GPL(btree_grim_visitor);
static int __init btree_module_init(void)
{
@@ -664,5 +714,14 @@ static int __init btree_module_init(void
return 0;
}
+static void __exit btree_module_exit(void)
+{
+ kmem_cache_destroy(btree_cachep);
+}
+
/* If core code starts using btree, initialization should happen even earlier */
module_init(btree_module_init);
+module_exit(btree_module_exit);
+
+MODULE_AUTHOR("Joern Engel <joern@...fs.org>");
+MODULE_LICENSE("GPL");
--- wireless-testing.orig/include/linux/btree.h 2009-01-07 23:16:54.000000000 +0100
+++ wireless-testing/include/linux/btree.h 2009-01-08 00:48:29.000000000 +0100
@@ -43,6 +43,8 @@ void *btree_lookup(struct btree_head *he
unsigned long *key);
int btree_insert(struct btree_head *head, struct btree_geo *geo,
unsigned long *key, void *val);
+int btree_update(struct btree_head *head, struct btree_geo *geo,
+ unsigned long *key, void *val);
void *btree_remove(struct btree_head *head, struct btree_geo *geo,
unsigned long *key);
int btree_merge(struct btree_head *target, struct btree_head *victim,
@@ -75,6 +77,12 @@ static inline int btree_insertl(struct b
return btree_insert(&head->h, &btree_geo32, &key, val);
}
+static inline int btree_updatel(struct btree_headl *head, unsigned long key,
+ void *val)
+{
+ return btree_update(&head->h, &btree_geo32, &key, val);
+}
+
static inline void *btree_removel(struct btree_headl *head, unsigned long key)
{
return btree_remove(&head->h, &btree_geo32, &key);
@@ -124,6 +132,12 @@ static inline int btree_insert32(struct
return btree_insert(&head->h, &btree_geo32, (unsigned long *)&key, val);
}
+static inline int btree_update32(struct btree_head32 *head, u32 key,
+ void *val)
+{
+ return btree_update(&head->h, &btree_geo32, (unsigned long *)&key, val);
+}
+
static inline void *btree_remove32(struct btree_head32 *head, u32 key)
{
return btree_remove(&head->h, &btree_geo32, (unsigned long *)&key);
@@ -172,6 +186,12 @@ static inline int btree_insert64(struct
return btree_insert(&head->h, &btree_geo64, (unsigned long *)&key, val);
}
+static inline int btree_update64(struct btree_head64 *head, u64 key,
+ void *val)
+{
+ return btree_update(&head->h, &btree_geo64, (unsigned long *)&key, val);
+}
+
static inline void *btree_remove64(struct btree_head64 *head, u64 key)
{
return btree_remove(&head->h, &btree_geo64, (unsigned long *)&key);
@@ -220,7 +240,16 @@ static inline int btree_insert128(struct
void *val)
{
u64 key[2] = {k1, k2};
- return btree_insert(&head->h, &btree_geo128, (unsigned long *)&key, val);
+ return btree_insert(&head->h, &btree_geo128,
+ (unsigned long *)&key, val);
+}
+
+static inline int btree_update128(struct btree_head128 *head, u64 k1, u64 k2,
+ void *val)
+{
+ u64 key[2] = {k1, k2};
+ return btree_update(&head->h, &btree_geo128,
+ (unsigned long *)&key, val);
}
static inline void *btree_remove128(struct btree_head128 *head, u64 k1, u64 k2)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists