B+Tree library
RFC 1/1 B+Tree library
The idea of using btrees in the kernel is not exactly new. They have a number of advantages over rbtrees and hashtables, but also a number of drawbacks. More importantly, logfs already makes use of them and - since I don't want any incompatible code to get merged and suffer the trouble it creates - I would like to discuss my implementation and where it makes sense and where it doesn't.
General advantages of btrees are memory density and efficient use of cachelines. Hashtables are either too small and degrade into linked list performance, or they are too large and waste memory. With changing workloads, both may be true on the same system. Rbtrees have a bad fanout of less than 2 (they are not actually balanced binary trees), hence reading a fairly large number of cachelines to each lookup.
Main disadvantage of btrees is that they are complicated, come in a gazillion subtly different variant that differ mainly in the balance between read efficiency and write efficiency. Comparing btrees against anything is a bit like comparing apples and random fruits.
This implementation is extremely simple. It splits nodes when they overflow. It does not move elements to neighboring nodes. It does not try fancy 2:3 splits. It does not even merge nodes when they shrink, making degenerate cases possible. And it requires callers to do tree-global locking. In effect, it will be hard to find anything less sophisticated.
The one aspect where my implementation is actually nice is in allowing variable key length. Btree keys are interpreted as an array of unsigned long. So by passing the correct geometry to the core functions, it is possible to handle 32bit, 64bit or 128bit btrees, which logfs uses. If so desired, any other weird data format can be used as well (Zach, are you reading this?).
So would something like this be merged once some users are identified? Would it be useful for anything but logfs? Or am I plain nuts?
include/linux/btree.h | 272 ++++++++++++++++++++++ lib/Kconfig | 3 lib/Makefile | 1 lib/btree.c | 603 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 879 insertions(+)
Jörn
Signature · 3 lines
It is the mark of an educated mind to be able to entertain a thought without accepting it. -- Aristotle
include/linux/btree.h new file +272 -0
@@ -0,0 +1,272 @@ +#ifndef BTREE_H +#define BTREE_H + +#include <linux/kernel.h> +#include <linux/mempool.h> + +/* +* B+Tree node format: +* [key0, key1, ..., keyN] [val0, val1, ..., valN] +* Each key is an array of unsigned longs, head->no_longs in total. +* Total number of keys and vals (N) is head->no_pairs. +*/ + +struct btree_head { +unsigned long *node; +mempool_t *mempool; +int height; +gfp_t gfp_mask; +}; + +struct btree_geo { +int keylen; +int no_pairs; +}; +extern struct btree_geo btree_geo32; +extern struct btree_geo btree_geo64; +extern struct btree_geo btree_geo128; + +struct btree_headl {struct btree_head h; }; +struct btree_head32 {struct btree_head h; }; +struct btree_head64 {struct btree_head h; }; +struct btree_head128 {struct btree_head h; }; + +/* +* These couple of functions are all there is to it. The rest of this header +* consists only of wrappers that try to add some typesafety, make the code +* a little self-documenting and generally be nice to people. +*/ +void *btree_alloc (gfp_t gfp_mask,void *pool_data); +void btree_free (void *element,void *pool_data); +void btree_init (struct btree_head *head,mempool_t *mempool,gfp_t gfp); +void *btree_lookup (struct btree_head *head,struct btree_geo *geo, +unsigned long *key); +int btree_insert (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, +struct btree_geo *geo,unsigned long *duplicate); +unsigned long *btree_last (struct btree_head *head,struct btree_geo *geo); +size_t btree_visitor (struct btree_head *head,struct btree_geo *geo, +long opaque, +void (*func)(void *elem,long opaque,unsigned long *key, +size_t index,void *func2),void *func2); +size_t btree_grim_visitor (struct btree_head *head,struct btree_geo *geo, +long opaque, +void (*func)(void *elem,long opaque,unsigned long *key, +size_t index,void *func2),void *func2); + +/* key is unsigned long */ +static inline void btree_initl (struct btree_headl *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookupl (struct btree_headl *head,unsigned long key) +{ +return btree_lookup (&head->h, &btree_geo32, &key); +} + +static inline int btree_insertl (struct btree_headl *head,unsigned long key, +void *val) +{ +return btree_insert (&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); +} + +static inline int btree_mergel (struct btree_headl *target, +struct btree_headl *victim) +{ +unsigned long scratch; + +return btree_merge (&target->h, &victim->h, &btree_geo32, &scratch); +} + +void visitorl (void *elem,long opaque,unsigned long *key,size_t index, +void *__func); + +typedef void (*visitorl_t )(void *elem,long opaque,unsigned long key, +size_t index); + +static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +} + +static inline size_t btree_grim_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +} + +/* key is u32 */ +static inline void btree_init32 (struct btree_head32 *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookup32 (struct btree_head32 *head,u32 key) +{ +return btree_lookup (&head->h, &btree_geo32, (unsigned long *)&key); +} + +static inline int btree_insert32 (struct btree_head32 *head,u32 key, +void *val) +{ +return btree_insert (&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); +} + +static inline int btree_merge32 (struct btree_head32 *target, +struct btree_head32 *victim) +{ +unsigned long scratch; + +return btree_merge (&target->h, &victim->h, &btree_geo32, &scratch); +} + +void visitor32 (void *elem,long opaque,unsigned long *__key,size_t index, +void *__func); + +typedef void (*visitor32_t )(void *elem,long opaque,u32 key,size_t index); + +static inline size_t btree_visitor32 (struct btree_head32 *head,long opaque, +visitor32_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitor32, func2); +} + +static inline size_t btree_grim_visitor32 (struct btree_head32 *head,long opaque, +visitor32_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo32, opaque, visitor32, func2); +} + +/* key is u64 */ +static inline void btree_init64 (struct btree_head64 *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookup64 (struct btree_head64 *head,u64 key) +{ +return btree_lookup (&head->h, &btree_geo64, (unsigned long *)&key); +} + +static inline int btree_insert64 (struct btree_head64 *head,u64 key, +void *val) +{ +return btree_insert (&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); +} + +static inline int btree_merge64 (struct btree_head64 *target, +struct btree_head64 *victim) +{ +u64 scratch; + +return btree_merge (&target->h, &victim->h, &btree_geo64, + (unsigned long *)&scratch); +} + +void visitor64 (void *elem,long opaque,unsigned long *__key,size_t index, +void *__func); + +typedef void (*visitor64_t )(void *elem,long opaque,u64 key,size_t index); + +static inline size_t btree_visitor64 (struct btree_head64 *head,long opaque, +visitor64_t func2) +{ +return btree_visitor (&head->h, &btree_geo64, opaque, visitor64, func2); +} + +static inline size_t btree_grim_visitor64 (struct btree_head64 *head,long opaque, +visitor64_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo64, opaque, visitor64, func2); +} + +/* key is 128bit (two u64) */ +static inline void btree_init128 (struct btree_head128 *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookup128 (struct btree_head128 *head,u64 k1,u64 k2) +{ +u64 key[2 ] = {k1, k2}; +return btree_lookup (&head->h, &btree_geo128, (unsigned long *)&key); +} + +static inline int btree_insert128 (struct btree_head128 *head,u64 k1,u64 k2, +void *val) +{ +u64 key[2 ] = {k1, k2}; +return btree_insert (&head->h, &btree_geo128, (unsigned long *)&key, val); +} + +static inline void *btree_remove128 (struct btree_head128 *head,u64 k1,u64 k2) +{ +u64 key[2 ] = {k1, k2}; +return btree_remove (&head->h, &btree_geo128, (unsigned long *)&key); +} + +static inline void btree_last128 (struct btree_head128 *head,u64 *k1,u64 *k2) +{ +u64 *key = (u64 *)btree_last (&head->h, &btree_geo128); + +if (key) { + *k1 = key[0 ]; + *k2 = key[1 ]; + }else { + *k1 =0 ; + *k2 =0 ; + } +} + +static inline int btree_merge128 (struct btree_head128 *target, +struct btree_head128 *victim) +{ +u64 scratch[2 ]; + +return btree_merge (&target->h, &victim->h, &btree_geo128, + (unsigned long *)scratch); +} + +void visitor128 (void *elem,long opaque,unsigned long *__key,size_t index, +void *__func); + +typedef void (*visitor128_t )(void *elem,long opaque,u64 key1,u64 key2, +size_t index); + +static inline size_t btree_visitor128 (struct btree_head128 *head,long opaque, +visitor128_t func2) +{ +return btree_visitor (&head->h, &btree_geo128, opaque, visitor128, func2); +} + +static inline size_t btree_grim_visitor128 (struct btree_head128 *head,long opaque, +visitor128_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo128, opaque, visitor128, func2); +} + +#endif
include/linux/kernel.h +0 -0
lib/Kconfig +3 -0
@@ -129,6 +129,9 @@ config TEXTSEARCH_FSM config PLIST boolean +config BTREE + boolean + config HAS_IOMEM boolean depends on !NO_IOMEM
lib/Makefile +1 -0
@@ -34,6 +34,7 @@ lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_PLIST) += plist.o +obj-$(CONFIG_BTREE) += btree.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o
lib/btree.c new file +603 -0
603 lines not on this page · raw message
Quoted 33 lines · Jörn Engel
The idea of using btrees in the kernel is not exactly new. They have a number of advantages over rbtrees and hashtables, but also a number of drawbacks. More importantly, logfs already makes use of them and - since I don't want any incompatible code to get merged and suffer the trouble it creates - I would like to discuss my implementation and where it makes sense and where it doesn't.
General advantages of btrees are memory density and efficient use of cachelines. Hashtables are either too small and degrade into linked list performance, or they are too large and waste memory. With changing workloads, both may be true on the same system. Rbtrees have a bad fanout of less than 2 (they are not actually balanced binary trees), hence reading a fairly large number of cachelines to each lookup.
Main disadvantage of btrees is that they are complicated, come in a gazillion subtly different variant that differ mainly in the balance between read efficiency and write efficiency. Comparing btrees against anything is a bit like comparing apples and random fruits.
This implementation is extremely simple. It splits nodes when they overflow. It does not move elements to neighboring nodes. It does not try fancy 2:3 splits. It does not even merge nodes when they shrink, making degenerate cases possible. And it requires callers to do tree-global locking. In effect, it will be hard to find anything less sophisticated.
The one aspect where my implementation is actually nice is in allowing variable key length. Btree keys are interpreted as an array of unsigned long. So by passing the correct geometry to the core functions, it is possible to handle 32bit, 64bit or 128bit btrees, which logfs uses. If so desired, any other weird data format can be used as well (Zach, are you reading this?).
Quoted 2 lines
So would something like this be merged once some users are identified? Would it be useful for anything but logfs? Or am I plain nuts?
I think a btree library would be useful - there are places where people are using rb-trees instead of btree simply because it's easier to use the rbtree than it is to implement a btree library. I can think of several places I could use such a library for in-memory extent representation....
That being said, I haven't had a chance to look at that code yet....
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Hi!
Quoted 4 lines
Main disadvantage of btrees is that they are complicated, come in a gazillion subtly different variant that differ mainly in the balance between read efficiency and write efficiency. Comparing btrees against anything is a bit like comparing apples and random fruits.
:-)))))
+ * Disks have fulfilled the prerequite for a long time. More recently DRAM
prerequisite?
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
We already have that in the headers somewhere.
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Quoted 4 lines · Pavel Machek
+ * Disks have fulfilled the prerequite for a long time. More recently DRAM
prerequisite?
In the paragraph above:
+ * B+Trees can be used similar to Linux radix trees (which don't have anything
+ * in common with textbook radix trees, beware). Prerequisite for them working
+ * well is that access to a random tree node is much faster than a large number
+ * of operations within each node.
Quoted 3 lines
+#define
MAX(a, b)((a) > (b) ? (a) : (b))We already have that in the headers somewhere.
Except that min/max in include/linux/kernel.h have some type-safety added. In this particular case that is actually a disadvantage:
CC lib/btree.o
lib/btree.c:56: error: braced-group within expression allowed only inside a function lib/btree.c:62: error: braced-group within expression allowed only inside a function lib/btree.c:67: error: braced-group within expression allowed only inside a function
So I need something more stupid. :)
Jörn
Signature · 3 lines
It does not require a majority to prevail, but rather an irate, tireless minority keen to set brush fires in people's minds. -- Samuel Adams
Quoted 7 lines · Jörn Engel
Quoted 4 lines · Pavel Machek
+ * Disks have fulfilled the prerequite for a long time. More recently DRAM
prerequisite?
In the paragraph above:
I don't thing "prerequite" is valid english word... is it?
Quoted 4 lines
Quoted 3 lines
+#define
MAX(a, b)((a) > (b) ? (a) : (b))We already have that in the headers somewhere.
Quoted 8 lines
Except that min/max in
include/linux/kernel.hhave some type-safety added. In this particular case that is actually a disadvantage:
CClib/btree.o
lib/btree.c:56: error: braced-group within expression allowed only inside a functionlib/btree.c:62: error: braced-group within expression allowed only inside a functionlib/btree.c:67: error: braced-group within expression allowed only inside a functionSo I need something more stupid. :)
Aha, ok.
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Quoted 9 lines · Pavel Machek
Quoted 6 lines · Jörn Engel
Quoted 3 lines · Pavel Machek
+ * Disks have fulfilled the prerequite for a long time. More recently DRAM prerequisite?
In the paragraph above:
I don't thing "prerequite" is valid english word... is it?
Indeed. I could have read it another dozen times and not noticed myself. Thanks.
Jörn
Signature · 3 lines
The wise man seeks everything in himself; the ignorant man tries to get everything from somebody else. -- unknown
Am Donnerstag, 30. Oktober 2008 schrieb Jörn Engel:
Quoted 2 lines
Except that min/max in
include/linux/kernel.hhave some type-safety added. In this particular case that is actually a disadvantage:
So what about min_t and max_t from include/linux/kernel.h? Can that be used?
Christian
Quoted 5 lines · Christian Borntraeger
Am Donnerstag, 30. Oktober 2008 schrieb Jörn Engel:
Quoted 2 lines
Except that min/max in
include/linux/kernel.hhave some type-safety added. In this particular case that is actually a disadvantage:So what about
min_tandmax_tfrominclude/linux/kernel.h? Can that be used?
Sorry, no. The problems comes from using MAX in structure initializers.
struct btree_geo btree_geo32 = {
.keylen = 1,
.no_pairs = NODESIZE / sizeof(long) / 2,
};Jörn
Signature · 4 lines
Correctness comes second. Features come third. Performance comes last. Maintainability is easily forgotten.
Quoted 5 lines · Jörn Engel
Quoted 4 lines · Christian Borntraeger
Am Donnerstag, 30. Oktober 2008 schrieb Jörn Engel:
Quoted 2 lines
Except that min/max in
include/linux/kernel.hhave some type-safety added. In this particular case that is actually a disadvantage:
Quoted 8 lines
Quoted 1 line
So what about
min_tandmax_tfrominclude/linux/kernel.h? Can that be used?Sorry, no. The problems comes from using MAX in structure initializers.
struct btree_geo btree_geo32 = { .keylen = 1, .no_pairs = NODESIZE / sizeof(long) / 2, };
Where's the MIN/MAX? ;-)
Gr{oetje,eeting}s,
Geert
--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]
In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds
Quoted 2 lines · Geert Uytterhoeven
Where's the MIN/MAX? ;-)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define NODESIZE MAX(L1_CACHE_BYTES, 128)
struct btree_geo btree_geo32 = {
.keylen = 1,
.no_pairs = NODESIZE / sizeof(long) / 2,
};
/me senses a bikeshed discussion.
Jörn
Signature · 4 lines
You cannot suppose that Moliere ever troubled himself to be original in the matter of ideas. You cannot suppose that the stories he tells in his plays have never been told before. They were culled, as you very well know. -- Andre-Louis Moreau in Scarabouche
[looks like this hitting LWN means everyone suddenly found it...]
Quoted 6 lines
The one aspect where my implementation is actually nice is in allowing variable key length. Btree keys are interpreted as an array of unsigned long. So by passing the correct geometry to the core functions, it is possible to handle 32bit, 64bit or 128bit btrees, which logfs uses. If so desired, any other weird data format can be used as well (Zach, are you reading this?).
Would there be an easy way to use 48-bit keys? Or variable length keys?
Quoted 2 lines
So would something like this be merged once some users are identified? Would it be useful for anything but logfs? Or am I plain nuts?
I could imagine using it instead of the hash-table for stations and APs in the wireless code, stations are identified by the MAC address (48 bit) and APs (BSSs) are identified by their BSSID+SSID (or mesh ID), so variable length. Currently we use a hash table with 256 slots which is quite large for the typical case of mostly less than a hundred entries.
Quoted 6 lines
This implementation is extremely simple. It splits nodes when they overflow. It does not move elements to neighboring nodes. It does not try fancy 2:3 splits. It does not even merge nodes when they shrink, making degenerate cases possible. And it requires callers to do tree-global locking. In effect, it will be hard to find anything less sophisticated.
I think the wireless case would probably want to have real shrinking because it's well possible that you're moving, with your laptop, from an area with a large number of APs to say your home out in the countryside that only has your single AP.
johannes
Quoted 2 lines · Johannes Berg
[looks like this hitting LWN means everyone suddenly found it...]
It did?
Quoted 8 lines
Quoted 6 lines
The one aspect where my implementation is actually nice is in allowing variable key length. Btree keys are interpreted as an array of unsigned long. So by passing the correct geometry to the core functions, it is possible to handle 32bit, 64bit or 128bit btrees, which logfs uses. If so desired, any other weird data format can be used as well (Zach, are you reading this?).
Would there be an easy way to use 48-bit keys? Or variable length keys?
Variable as in one implementation for several trees with different sizes, yes. Variable as in one tree with differently sized keys, no.
With the existing code, 48bit keys would need to be expressed as an array of longs, thereby growing to 64bit. Alternatively one could replace the longset/longcmp/longcpy with memset/memcmp/memcpy.
Quoted 8 lines
Quoted 2 lines
So would something like this be merged once some users are identified? Would it be useful for anything but logfs? Or am I plain nuts?
I could imagine using it instead of the hash-table for stations and APs in the wireless code, stations are identified by the MAC address (48 bit) and APs (BSSs) are identified by their BSSID+SSID (or mesh ID), so variable length. Currently we use a hash table with 256 slots which is quite large for the typical case of mostly less than a hundred entries.
MAC address wouldn't be a problem. For BSSID+SSID one could just keep the hashing and use the btree as an 'implementation detail' of the 'hashtable'. Beware that I don't allow two identical keys. The implications of that make my toenails curl up.
Quoted 11 lines
Quoted 6 lines
This implementation is extremely simple. It splits nodes when they overflow. It does not move elements to neighboring nodes. It does not try fancy 2:3 splits. It does not even merge nodes when they shrink, making degenerate cases possible. And it requires callers to do tree-global locking. In effect, it will be hard to find anything less sophisticated.
I think the wireless case would probably want to have real shrinking because it's well possible that you're moving, with your laptop, from an area with a large number of APs to say your home out in the countryside that only has your single AP.
Indeed.
Jörn
Signature · 2 lines
Joern's library part 7: http://www.usenix.org/publications/library/proceedings/neworl/full_papers/mckusick.a
Quoted 5 lines · Jörn Engel
Quoted 2 lines · Johannes Berg
[looks like this hitting LWN means everyone suddenly found it...]
It did?
Yes, on the weekly kernel page, under "Patches and updates / Core kernel code"
Quoted 11 lines
Quoted 8 lines
Quoted 6 lines
The one aspect where my implementation is actually nice is in allowing variable key length. Btree keys are interpreted as an array of unsigned long. So by passing the correct geometry to the core functions, it is possible to handle 32bit, 64bit or 128bit btrees, which logfs uses. If so desired, any other weird data format can be used as well (Zach, are you reading this?).
Would there be an easy way to use 48-bit keys? Or variable length keys?
Variable as in one implementation for several trees with different sizes, yes. Variable as in one tree with differently sized keys, no.
Ok, I guess that would blow up the key size to 6+1+32 bytes, or 10 (5) longs. Bit large.
Quoted 9 lines
Quoted 8 lines
Quoted 2 lines
So would something like this be merged once some users are identified? Would it be useful for anything but logfs? Or am I plain nuts?
I could imagine using it instead of the hash-table for stations and APs in the wireless code, stations are identified by the MAC address (48 bit) and APs (BSSs) are identified by their BSSID+SSID (or mesh ID), so variable length. Currently we use a hash table with 256 slots which is quite large for the typical case of mostly less than a hundred entries.
Quoted 4 lines
MAC address wouldn't be a problem. For BSSID+SSID one could just keep the hashing and use the btree as an 'implementation detail' of the 'hashtable'. Beware that I don't allow two identical keys. The implications of that make my toenails curl up.
Heh. We don't actually hash on the SSID right now, only on the BSSID, and then use the SSID to distinguish (it isn't common to have two SSIDs on the same BSSID)
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines
This implementation is extremely simple. It splits nodes when they overflow. It does not move elements to neighboring nodes. It does not try fancy 2:3 splits. It does not even merge nodes when they shrink, making degenerate cases possible. And it requires callers to do tree-global locking. In effect, it will be hard to find anything less sophisticated.
Quoted 6 lines
Quoted 4 lines
I think the wireless case would probably want to have real shrinking because it's well possible that you're moving, with your laptop, from an area with a large number of APs to say your home out in the countryside that only has your single AP.
Indeed.
I guess not then for now, unless one of us wants to implement resizing... I'll look for replacements another time, nobody has complained yet about the huge hash table :)
johannes
Quoted 8 lines · Johannes Berg
Quoted 5 lines
Quoted 2 lines
Would there be an easy way to use 48-bit keys? Or variable length keys?
Variable as in one implementation for several trees with different sizes, yes. Variable as in one tree with differently sized keys, no.
Ok, I guess that would blow up the key size to 6+1+32 bytes, or 10 (5) longs. Bit large.
Yes. Insanely large keys are a good indication to better avoid btrees.
Quoted 10 lines
Quoted 6 lines
Quoted 4 lines
I think the wireless case would probably want to have real shrinking because it's well possible that you're moving, with your laptop, from an area with a large number of APs to say your home out in the countryside that only has your single AP.
Indeed.
I guess not then for now, unless one of us wants to implement resizing... I'll look for replacements another time, nobody has complained yet about the huge hash table :)
I actually have something that compiles now. It still needs a bit of water and soap before I'd consider it presentable, but turned out to be less complicated than expected.
Jörn
Signature · 4 lines
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity. -- W. A. Wulf
Quoted 11 lines · Jörn Engel
Quoted 8 lines · Johannes Berg
Quoted 5 lines
Quoted 2 lines
Would there be an easy way to use 48-bit keys? Or variable length keys?
Variable as in one implementation for several trees with different sizes, yes. Variable as in one tree with differently sized keys, no.
Ok, I guess that would blow up the key size to 6+1+32 bytes, or 10 (5) longs. Bit large.
Yes. Insanely large keys are a good indication to better avoid btrees.
OTOH, there is no need to put the SSID in if I put a small list into each node, effectively using the tree instead of the hash table and then disambiguating the unlikely case of multiple SSID in a list.
Quoted 3 lines
I actually have something that compiles now. It still needs a bit of water and soap before I'd consider it presentable, but turned out to be less complicated than expected.
:)
johannes
Quoted 4 lines · Johannes Berg
OTOH, there is no need to put the SSID in if I put a small list into each node, effectively using the tree instead of the hash table and then disambiguating the unlikely case of multiple SSID in a list.
Exactly. In sunny wheather btrees can be a good implementation for hash tables. They can grow and shrink as needed, without taking the latency hit for rehashing every single item. Until lock contention or pingpong shows otherwise. :(
Most likely the answer to bad whether is RCU. Patches are welcome.
Jörn
Signature · 3 lines
They laughed at Galileo. They laughed at Copernicus. They laughed at Columbus. But remember, they also laughed at Bozo the Clown. -- unknown
RFC 1/1 B+Tree library V2
In reply to Jörn EngelQuoted 9 lines · Jörn Engel
Quoted 4 lines · Johannes Berg
I guess not then for now, unless one of us wants to implement resizing... I'll look for replacements another time, nobody has complained yet about the huge hash table :)
I actually have something that compiles now. It still needs a bit of water and soap before I'd consider it presentable, but turned out to be less complicated than expected.
Not only compiles, also survives muserspace test harness and no longer looks like a bulldog with lipstick.
You might note that "less complicated than expected" means I'm still bending the rules a bit. I only merge underpopulated nodes with neighbours. If the neighbour is too full for a merge I don't steal entries. That bit is for someone else to implement. :)
Jörn
Signature · 3 lines
on a false concept. This concept is that people actually want to look at source code. -- Rob Enderle
include/linux/btree.h new file +272 -0
@@ -0,0 +1,272 @@ +#ifndef BTREE_H +#define BTREE_H + +#include <linux/kernel.h> +#include <linux/mempool.h> + +/* +* B+Tree node format: +* [key0, key1, ..., keyN] [val0, val1, ..., valN] +* Each key is an array of unsigned longs, head->no_longs in total. +* Total number of keys and vals (N) is head->no_pairs. +*/ + +struct btree_head { +unsigned long *node; +mempool_t *mempool; +int height; +gfp_t gfp_mask; +}; + +struct btree_geo { +int keylen; +int no_pairs; +}; +extern struct btree_geo btree_geo32; +extern struct btree_geo btree_geo64; +extern struct btree_geo btree_geo128; + +struct btree_headl {struct btree_head h; }; +struct btree_head32 {struct btree_head h; }; +struct btree_head64 {struct btree_head h; }; +struct btree_head128 {struct btree_head h; }; + +/* +* These couple of functions are all there is to it. The rest of this header +* consists only of wrappers that try to add some typesafety, make the code +* a little self-documenting and generally be nice to people. +*/ +void *btree_alloc (gfp_t gfp_mask,void *pool_data); +void btree_free (void *element,void *pool_data); +void btree_init (struct btree_head *head,mempool_t *mempool,gfp_t gfp); +void *btree_lookup (struct btree_head *head,struct btree_geo *geo, +unsigned long *key); +int btree_insert (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, +struct btree_geo *geo,unsigned long *duplicate); +unsigned long *btree_last (struct btree_head *head,struct btree_geo *geo); +size_t btree_visitor (struct btree_head *head,struct btree_geo *geo, +long opaque, +void (*func)(void *elem,long opaque,unsigned long *key, +size_t index,void *func2),void *func2); +size_t btree_grim_visitor (struct btree_head *head,struct btree_geo *geo, +long opaque, +void (*func)(void *elem,long opaque,unsigned long *key, +size_t index,void *func2),void *func2); + +/* key is unsigned long */ +static inline void btree_initl (struct btree_headl *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookupl (struct btree_headl *head,unsigned long key) +{ +return btree_lookup (&head->h, &btree_geo32, &key); +} + +static inline int btree_insertl (struct btree_headl *head,unsigned long key, +void *val) +{ +return btree_insert (&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); +} + +static inline int btree_mergel (struct btree_headl *target, +struct btree_headl *victim) +{ +unsigned long scratch; + +return btree_merge (&target->h, &victim->h, &btree_geo32, &scratch); +} + +void visitorl (void *elem,long opaque,unsigned long *key,size_t index, +void *__func); + +typedef void (*visitorl_t )(void *elem,long opaque,unsigned long key, +size_t index); + +static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +} + +static inline size_t btree_grim_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +} + +/* key is u32 */ +static inline void btree_init32 (struct btree_head32 *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookup32 (struct btree_head32 *head,u32 key) +{ +return btree_lookup (&head->h, &btree_geo32, (unsigned long *)&key); +} + +static inline int btree_insert32 (struct btree_head32 *head,u32 key, +void *val) +{ +return btree_insert (&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); +} + +static inline int btree_merge32 (struct btree_head32 *target, +struct btree_head32 *victim) +{ +unsigned long scratch; + +return btree_merge (&target->h, &victim->h, &btree_geo32, &scratch); +} + +void visitor32 (void *elem,long opaque,unsigned long *__key,size_t index, +void *__func); + +typedef void (*visitor32_t )(void *elem,long opaque,u32 key,size_t index); + +static inline size_t btree_visitor32 (struct btree_head32 *head,long opaque, +visitor32_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitor32, func2); +} + +static inline size_t btree_grim_visitor32 (struct btree_head32 *head,long opaque, +visitor32_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo32, opaque, visitor32, func2); +} + +/* key is u64 */ +static inline void btree_init64 (struct btree_head64 *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookup64 (struct btree_head64 *head,u64 key) +{ +return btree_lookup (&head->h, &btree_geo64, (unsigned long *)&key); +} + +static inline int btree_insert64 (struct btree_head64 *head,u64 key, +void *val) +{ +return btree_insert (&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); +} + +static inline int btree_merge64 (struct btree_head64 *target, +struct btree_head64 *victim) +{ +u64 scratch; + +return btree_merge (&target->h, &victim->h, &btree_geo64, + (unsigned long *)&scratch); +} + +void visitor64 (void *elem,long opaque,unsigned long *__key,size_t index, +void *__func); + +typedef void (*visitor64_t )(void *elem,long opaque,u64 key,size_t index); + +static inline size_t btree_visitor64 (struct btree_head64 *head,long opaque, +visitor64_t func2) +{ +return btree_visitor (&head->h, &btree_geo64, opaque, visitor64, func2); +} + +static inline size_t btree_grim_visitor64 (struct btree_head64 *head,long opaque, +visitor64_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo64, opaque, visitor64, func2); +} + +/* key is 128bit (two u64) */ +static inline void btree_init128 (struct btree_head128 *head,mempool_t *mempool, +gfp_t gfp) +{ +btree_init (&head->h, mempool, gfp); +} + +static inline void *btree_lookup128 (struct btree_head128 *head,u64 k1,u64 k2) +{ +u64 key[2 ] = {k1, k2}; +return btree_lookup (&head->h, &btree_geo128, (unsigned long *)&key); +} + +static inline int btree_insert128 (struct btree_head128 *head,u64 k1,u64 k2, +void *val) +{ +u64 key[2 ] = {k1, k2}; +return btree_insert (&head->h, &btree_geo128, (unsigned long *)&key, val); +} + +static inline void *btree_remove128 (struct btree_head128 *head,u64 k1,u64 k2) +{ +u64 key[2 ] = {k1, k2}; +return btree_remove (&head->h, &btree_geo128, (unsigned long *)&key); +} + +static inline void btree_last128 (struct btree_head128 *head,u64 *k1,u64 *k2) +{ +u64 *key = (u64 *)btree_last (&head->h, &btree_geo128); + +if (key) { + *k1 = key[0 ]; + *k2 = key[1 ]; + }else { + *k1 =0 ; + *k2 =0 ; + } +} + +static inline int btree_merge128 (struct btree_head128 *target, +struct btree_head128 *victim) +{ +u64 scratch[2 ]; + +return btree_merge (&target->h, &victim->h, &btree_geo128, + (unsigned long *)scratch); +} + +void visitor128 (void *elem,long opaque,unsigned long *__key,size_t index, +void *__func); + +typedef void (*visitor128_t )(void *elem,long opaque,u64 key1,u64 key2, +size_t index); + +static inline size_t btree_visitor128 (struct btree_head128 *head,long opaque, +visitor128_t func2) +{ +return btree_visitor (&head->h, &btree_geo128, opaque, visitor128, func2); +} + +static inline size_t btree_grim_visitor128 (struct btree_head128 *head,long opaque, +visitor128_t func2) +{ +return btree_grim_visitor (&head->h, &btree_geo128, opaque, visitor128, func2); +} + +#endif
lib/Kconfig +3 -0
@@ -129,6 +129,9 @@ config TEXTSEARCH_FSM config PLIST boolean +config BTREE + boolean + config HAS_IOMEM boolean depends on !NO_IOMEM
lib/Makefile +1 -0
@@ -34,6 +34,7 @@ lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_PLIST) += plist.o +obj-$(CONFIG_BTREE) += btree.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o
lib/btree.c new file +668 -0
668 lines not on this page · raw message
Re: [RFC] B+Tree library V2
sorry for the late reply.
Quoted 2 lines · Jörn Engel
Not only compiles, also survives muserspace test harness and no longer looks like a bulldog with lipstick.
cool :)
Quoted 4 lines
You might note that "less complicated than expected" means I'm still bending the rules a bit. I only merge underpopulated nodes with neighbours. If the neighbour is too full for a merge I don't steal entries. That bit is for someone else to implement. :)
That sounds fair, after all at least it limits the tree size, but I'm too lazy to calculate the worst case right now.
I'd use this as-is for the WIP cfg80211 code that keeps track of BSSes, as a hash-table/list on steroids.
johannes
Re: [RFC] B+Tree library V2
Quoted 3 lines · Johannes Berg
That sounds fair, after all at least it limits the tree size, but I'm too lazy to calculate the worst case right now.
Worst case you have a single entry next to a full node, then split the full node, etc. So slightly more than 1/4 populated.
Quoted 2 lines
I'd use this as-is for the WIP cfg80211 code that keeps track of BSSes, as a hash-table/list on steroids.
Excellent. With this trojan horse in place I don't have to worry much about a competing library with a different interface. Famous last words. :)
Jörn
Signature · 3 lines
The wise man seeks everything in himself; the ignorant man tries to get everything from somebody else. -- unknown
Re: [RFC] B+Tree library V2
Quoted 7 lines · Jörn Engel
Quoted 3 lines · Johannes Berg
That sounds fair, after all at least it limits the tree size, but I'm too lazy to calculate the worst case right now.
Worst case you have a single entry next to a full node, then split the full node, etc. So slightly more than 1/4 populated.
That would be roughly 1/3, no? But it doesn't really matter much.
Quoted 6 lines
Quoted 2 lines
I'd use this as-is for the WIP cfg80211 code that keeps track of BSSes, as a hash-table/list on steroids.
Excellent. With this trojan horse in place I don't have to worry much about a competing library with a different interface. Famous last words. :)
:)
How we going to synchronise this? I'm not in a hurry with this scanning code and I need to work on it still anyway.
johannes
Re: [RFC] B+Tree library V2
Quoted 10 lines · Johannes Berg
Quoted 7 lines · Jörn Engel
Quoted 3 lines · Johannes Berg
That sounds fair, after all at least it limits the tree size, but I'm too lazy to calculate the worst case right now.
Worst case you have a single entry next to a full node, then split the full node, etc. So slightly more than 1/4 populated.
That would be roughly 1/3, no? But it doesn't really matter much.
When entries/node approaches infinity it is 1/4. With 4 entries/node, which is the smallest useful number, it is 3/8.
Quoted 2 lines
How we going to synchronise this? I'm not in a hurry with this scanning code and I need to work on it still anyway.
I could create a git tree and ask for inclusion in -next. Or you could combine it with your code. I slightly favor the latter, as a library without any users is somewhat... useless.
Jörn
Signature · 2 lines
When in doubt, use brute force. -- Ken Thompson
Re: [RFC] B+Tree library V2
Quoted 7 lines · Jörn Engel
Quoted 6 lines · Johannes Berg
Quoted 5 lines · Jörn Engel
Quoted 3 lines · Johannes Berg
That sounds fair, after all at least it limits the tree size, but I'm too lazy to calculate the worst case right now.
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
Worst case you have a single entry next to a full node, then split the full node, etc. So slightly more than 1/4 populated.
That would be roughly 1/3, no? But it doesn't really matter much.
When entries/node approaches infinity it is 1/4. With 4 entries/node, which is the smallest useful number, it is 3/8.
Ah, right.
Quoted 6 lines
Quoted 2 lines
How we going to synchronise this? I'm not in a hurry with this scanning code and I need to work on it still anyway.
I could create a git tree and ask for inclusion in -next. Or you could combine it with your code. I slightly favor the latter, as a library without any users is somewhat... useless.
I can do that, though I can't promise right now when I'll actually be able to solve the remaining problems with that code. And I also thought you already had another user in mind :)
johannes
Re: [RFC] B+Tree library V2
Quoted 9 lines · Johannes Berg
Quoted 4 lines · Jörn Engel
I could create a git tree and ask for inclusion in -next. Or you could combine it with your code. I slightly favor the latter, as a library without any users is somewhat... useless.
I can do that, though I can't promise right now when I'll actually be able to solve the remaining problems with that code. And I also thought you already had another user in mind :)
Of course I do. And if my code gets merged first I'll take the btree along, promised.
Jörn
Signature · 3 lines
He who knows others is wise. He who knows himself is enlightened. -- Lao Tsu
Re: [RFC] B+Tree library V2
In reply to Jörn EngelOn 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(-)
lib/Kconfig +1 -1
@@ -137,7 +137,7 @@ config PLIST boolean config BTREE - boolean + tristate config HAS_IOMEM boolean
lib/btree.c +59 -0
170 lines not on this page · raw message
include/linux/btree.h +30 -1
@@ -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 breturn 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(structreturn 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(structreturn 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)
Re: [RFC] B+Tree library V2
Quoted 7 lines · Johannes Berg
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?
At first glance it does. The update looks like someone might need it, but doesn't have a user yet. The btree_merge is similar, as I used to need it, but no longer do. Maybe #if 0 those two.
Quoted 6 lines
One thing that seems a little odd is requiring a
btree_init(), but not having abtree_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?
Well, I used to have heaps of btrees around and wanted to share the mempool between all of them. Not sure if I still do, I believe not. Will check.
If mempools aren't shared, I agree that encapsulating those bits is much nicer.
Quoted 4 lines
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.
If you want to open-code it, you can use btree_lookup_less(). I added that function sometime last month. Basically something like this:
key = btree_last(head, geo);
while (key) {
/* do something with key */
key = btree_lookup_less(head, geo, key);
}Maybe it should be renamed to btree_get_prev_key(). I never noticed how confusing it was because my head was busy with other problems. The code is currently burried within my logfs tree:
http://logfs.org/git?p=logfs;a=summary
Will merge it with your patch and respin later tonight or tomorrow...
Jörn
Signature · 3 lines
I can say that I spend most of my time fixing bugs even if I have lots of new features to implement in mind, but I give bugs more priority. -- Andrea Arcangeli, 2000
Re: [RFC] B+Tree library V2
Quoted 7 lines · Jörn Engel
Quoted 3 lines
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?
At first glance it does. The update looks like someone might need it, but doesn't have a user yet. The
btree_mergeis similar, as I used to need it, but no longer do. Maybe #if 0 those two.
Sure, works for me. I just had written it and didn't want to keep it from the world after changing my mind about needing it.
Quoted 6 lines
Well, I used to have heaps of btrees around and wanted to share the mempool between all of them. Not sure if I still do, I believe not. Will check.
If mempools aren't shared, I agree that encapsulating those bits is much nicer.
Just made the API a bit quirky, maybe just support both ways of using things? Would only need a flag somewhere in the btree structure, I'd think; ultimately it doesn't matter much to me though.
Quoted 13 lines
Quoted 4 lines
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.
If you want to open-code it, you can use
btree_lookup_less(). I added that function sometime last month. Basically something like this:key = btree_last(head, geo); while (key) { /* do something with key */ key = btree_lookup_less(head, geo, key); }
Quoted 4 lines
Maybe it should be renamed to
btree_get_prev_key(). I never noticed how confusing it was because my head was busy with other problems. The code is currently burried within my logfs tree:
http://logfs.org/git?p=logfs;a=summary
I don't think I've understood this yet. That code above there is a backwards walk over the key space, and it's safe to call btree_remove(key) at /* do something with key */?
Quoted 1 line
Will merge it with your patch and respin later tonight or tomorrow...
Cool, thanks. Mainly making it a module for testing anyway.
johannes
Re: [RFC] B+Tree library V2
Quoted 11 lines · Johannes Berg
Quoted 7 lines
Well, I used to have heaps of btrees around and wanted to share the mempool between all of them. Not sure if I still do, I believe not. Will check.
If mempools aren't shared, I agree that encapsulating those bits is much nicer.
Just made the API a bit quirky, maybe just support both ways of using things? Would only need a flag somewhere in the btree structure, I'd think; ultimately it doesn't matter much to me though.
I don't think we need a flag. Just a regular pair of init/cleanup functions and some __init_i_want_to_share_mempools_and_crawl_on_my_knees without a cleanup for those who need it.
Quoted 8 lines
Quoted 8 lines
If you want to open-code it, you can use
btree_lookup_less(). I added that function sometime last month. Basically something like this:key = btree_last(head, geo); while (key) { /* do something with key */ key = btree_lookup_less(head, geo, key); }
Quoted 8 lines
Quoted 4 lines
Maybe it should be renamed to
btree_get_prev_key(). I never noticed how confusing it was because my head was busy with other problems. The code is currently burried within my logfs tree:
http://logfs.org/git?p=logfs;a=summaryI don't think I've understood this yet. That code above there is a backwards walk over the key space, and it's safe to call
btree_remove(key)at /* do something with key */?
Yes, it's a backwards walk. The btree is sorted backwards as a micro-optimization. Loops will terminate a bit earlier without a complicated test this way.
And you can do absolutely anything at /* do something with key */. The btree_get_prev_key() will simply tell you what the next-lowest key in the btree is at that time. You no longer need locking around the whole visitor, but can release the lock after each step, if you want.
Downside is that each step will walk the btree from the root again. Twice, because you also need to lookup/remove each element. Tanstaafl.
Jörn
Signature · 3 lines
Courage is not the absence of fear, but rather the judgement that something else is more important than fear. -- Ambrose Redmoon
Re: [RFC] B+Tree library V2
In reply to Jörn EngelQuoted 5 lines
Maybe it should be renamed to
btree_get_prev_key(). I never noticed how confusing it was because my head was busy with other problems. The code is currently burried within my logfs tree:
http://logfs.org/git?p=logfs;a=summary
I see this:
- * Second trick is to special-case the key "0" or NUL. As seen above, this
- * value indicates an unused slot, so such a value should not be stored in the
- * tree itself. Instead it is stored in the null_ptr field in the btree_head.
Does that mean that wasn't true, and I can store a 0 key?
johannes
Re: [RFC] B+Tree library V2
Quoted 9 lines · Johannes Berg
I see this:
- * Second trick is to special-case the key "0" or NUL. As seen above, this
- * value indicates an unused slot, so such a value should not be stored in the
- * tree itself. Instead it is stored in thenull_ptrfield in thebtree_head.Does that mean that wasn't true, and I can store a 0 key?
Ahh, don't look at that! The embarrassment is unbearable! Go away!
Yes, I used to have a special exception for a 0 key. But I also have a special exception for a NULL value and can test against that instead of testing against a 0 key. It is even faster, because the value is not variable-sized. In hindsight it is hard to explain why I ever did that.
Jörn
Signature · 3 lines
Unless something dramatically changes, by 2015 we'll be largely wondering what all the fuss surrounding Linux was really about. -- Rob Enderle
Re: [RFC] B+Tree library V2
In reply to Jörn EngelQuoted 7 lines · Jörn Engel
If you want to open-code it, you can use
btree_lookup_less(). I added that function sometime last month. Basically something like this:key = btree_last(head, geo); while (key) { /* do something with key */ key = btree_lookup_less(head, geo, key); }
Ok, so looking deeper into this, how about adding
#define btree_for_each_key(head, geo, key, tmp) \ for (key = btree_last(head, geo), tmp = btree_lookup_less(head, geo, key); key; key = tmp, tmp = btree_lookup_less(head, geo, key))
(and possibly some type-checking variants that hardcode the geo)
Does that seem correct? And would it be possible to provide btree_last() that takes an void ** and fills it with the last entry, and the same for lookup_less(), so we can write btree_for_each_entry() too?
johannes
Re: [RFC] B+Tree library V2
Quoted 10 lines · Johannes Berg
Quoted 7 lines · Jörn Engel
If you want to open-code it, you can use
btree_lookup_less(). I added that function sometime last month. Basically something like this:key = btree_last(head, geo); while (key) { /* do something with key */ key = btree_lookup_less(head, geo, key); }
Quoted 5 lines
Ok, so looking deeper into this, how about adding
#define btree_for_each_key(head, geo, key, tmp) \ for (key = btree_last(head, geo), tmp = btree_get_prev_key(head, geo, key); key; key = tmp, tmp = btree_get_prev_key(head, geo, key))
[ Changed the function name above. It really isn't a lookup, it returns a key, not a value. My fault. ]
Looks correct otherwise. Probably needs a comment that without "tmp" we would skip a 0 key. Or am I the only one who wants to simplify the code before spotting this little subtlety?
Quoted 5 lines
(and possibly some type-checking variants that hardcode the geo)
Does that seem correct? And would it be possible to provide
btree_last()that takes an void ** and fills it with the last entry, and the same forlookup_less(), so we can writebtree_for_each_entry()too?
Not sure what you mean. Something with the same effect as this?
#define btree_for_each_val(head, geo, key, val) \ for (key = btree_last(head, geo), \ val = btree_lookup(head, geo, key); \ val; \ key = btree_get_prev_key(head, geo, key), \ val = btree_lookup(head, geo, key))
Jörn
Signature · 2 lines
Time? What's that? Time is only worth what you do with it. -- Theo de Raadt
Re: [RFC] B+Tree library V2
Quoted 6 lines · Jörn Engel
Quoted 3 lines
#define btree_for_each_key(head, geo, key, tmp) \ for (key = btree_last(head, geo), tmp = btree_get_prev_key(head, geo, key); key; key = tmp, tmp = btree_get_prev_key(head, geo, key))[ Changed the function name above. It really isn't a lookup, it returns a key, not a value. My fault. ]
Right.
Quoted 3 lines
Looks correct otherwise. Probably needs a comment that without "tmp" we would skip a 0 key. Or am I the only one who wants to simplify the code before spotting this little subtlety?
I, uh, I didn't even realise that. I think the code for btree_last/btree_get_prev_key isn't correct as is since the 0 key is valid, but you can't tell whether it returned 0 because it didn't find anything, or because there was no more entry. Or am I missing something?
Quoted 6 lines
Quoted 5 lines
(and possibly some type-checking variants that hardcode the geo)
Does that seem correct? And would it be possible to provide
btree_last()that takes an void ** and fills it with the last entry, and the same forlookup_less(), so we can writebtree_for_each_entry()too?
Quoted 8 lines
Not sure what you mean. Something with the same effect as this?
#define btree_for_each_val(head, geo, key, val) \ for (key = btree_last(head, geo), \ val = btree_lookup(head, geo, key); \ val; \ key = btree_get_prev_key(head, geo, key), \ val = btree_lookup(head, geo, key))
Well, that does lots of lookups that don't seem necessary, since a function like btree_last should be able to return the value right away. Also, if it was
#define btree_for_each_val(head, geo, key, val) for (val = btree_last(head, geo, &key); val; val = btree_get_prev(head, geo, &key))
it would be more correct, I think?
johannes
Re: [RFC] B+Tree library V2
Quoted 9 lines · Johannes Berg
Quoted 4 lines
Looks correct otherwise. Probably needs a comment that without "tmp" we would skip a 0 key. Or am I the only one who wants to simplify the code before spotting this little subtlety?
I, uh, I didn't even realise that. I think the code for btree_last/btree_get_prev_key isn't correct as is since the 0 key is valid, but you can't tell whether it returned 0 because it didn't find anything, or because there was no more entry. Or am I missing something?
Correct or not is a matter of opinion, so let's not go there. It certainly is unexpected and also inefficient. The alternative would be to return two values, they key and a flag to indicate the end.
Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
(and possibly some type-checking variants that hardcode the geo)
Does that seem correct? And would it be possible to provide
btree_last()that takes an void ** and fills it with the last entry, and the same forlookup_less(), so we can writebtree_for_each_entry()too?Not sure what you mean. Something with the same effect as this?
^^^^^^^^^^^ ;)
Quoted 12 lines
Quoted 7 lines
#define btree_for_each_val(head, geo, key, val) \ for (key = btree_last(head, geo), \ val = btree_lookup(head, geo, key); \ val; \ key = btree_get_prev_key(head, geo, key), \ val = btree_lookup(head, geo, key))Well, that does lots of lookups that don't seem necessary, since a function like
btree_lastshould be able to return the value right away. Also, if it was
Quoted 6 lines
#define btree_for_each_val(head, geo, key, val) for (val = btree_last(head, geo, &key); val; val = btree_get_prev(head, geo, &key))it would be more correct, I think?
More efficient, certainly. Half the tree walks are gone. Let's do it.
Note, btw, that this changes effort from O(2n) to O(n), while the old visitor is O(1) *). That was the reason why I wrote it in the first place. If the code wasn't as horrible and hard to use, it would be a clear winner. Guess we'll have to keep both variants.
*) Or rather O(2n*log(n)), O(n*log(n)) and O(log(n)) respectively.
Jörn
Signature · 2 lines
Joern's library part 6: http://www.gzip.org/zlib/feldspar.html
include/linux/btree.h line 101
Quoted 6 lines
include/linux/btree.h new file +5
-0+static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +}
Incidentally, do you think it would be possible to implement a kind of
btree_for_each_entry(e, ...) {
do something with e
}
macro or function/macro combination? You seem to be doing a recursive walk across the tree, would it be useful to have a linked list at the lowest level of nodes to be able to iterate more easily?
johannes
Quoted 9 lines · Johannes Berg
include/linux/btree.h line 101
Quoted 6 lines
include/linux/btree.h new file +5
-0+static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +}Incidentally, do you think it would be possible to implement a kind of
Quoted 7 lines
btree_for_each_entry(e, ...){
do something with e
}macro or function/macro combination? You seem to be doing a recursive walk across the tree, would it be useful to have a linked list at the lowest level of nodes to be able to iterate more easily?
Maybe. On the whole, I've tried hard not to optimize much. The idea was that a simple design can still receive some fundamental changes. But once a number of neat tricks like a linked list at the lowest level are used, the code becomes more resistent to changes.
That being said, the maze of function pointer around btree_visitor() does not make me very proud. Might be worth it.
Jörn
Signature · 2 lines
Prosperity makes friends, adversity tries them. -- Publilius Syrus
Quoted 9 lines · Johannes Berg
include/linux/btree.h line 101
Quoted 6 lines
include/linux/btree.h new file +5
-0+static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +}Incidentally, do you think it would be possible to implement a kind of
Quoted 3 lines
btree_for_each_entry(e, ...){
do something with e
}
#define btree_for_each_entryl(__elem, __head, __opaque, ...) \
({ \
void f2(void *__elem, long opaque, unsigned long key, size_t index) \
{ \
(__VA_ARGS__); \
} \
btree_visitorl(__head, __opaque, f2); \
});usage:
btree_for_each_entryl(e, head, opaque, {
do something with e
})
looks strange but works.
Bert
Quoted 7 lines
macro or function/macro combination? You seem to be doing a recursive walk across the tree, would it be useful to have a linked list at the lowest level of nodes to be able to iterate more easily?
johannes
Quoted 12 lines · Johannes Berg
include/linux/btree.h line 101
Quoted 5 lines
include/linux/btree.h new file +5
-0+static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +}Incidentally, do you think it would be possible to implement a kind of
btree_for_each_entry(e, ...){
do something with e
}
Quoted 5 lines
macro or function/macro combination? You seem to be doing a recursive walk across the tree, would it be useful to have a linked list at the lowest level of nodes to be able to iterate more easily?
johannes
What would you expect to be the behavior if you remove 'e' ? That might cause the tree to get re-ordered. Do you restart the list traversal?
I had a similar issue once with a hash table algorithm where you could either access elements with a hash key, or efficiently traverse the hash table using a linked list of elements. The solution wasn't too difficult in that case because removing an element didn't cause the table to get re-ordered.
rtg
Signature · 1 line
Tim Gardner [email protected]
Quoted 13 lines · Tim Gardner
Quoted 12 lines · Johannes Berg
include/linux/btree.h line 101
Quoted 5 lines
include/linux/btree.h new file +5
-0+static inline size_t btree_visitorl (struct btree_headl *head,long opaque, +visitorl_t func2) +{ +return btree_visitor (&head->h, &btree_geo32, opaque, visitorl, func2); +}Incidentally, do you think it would be possible to implement a kind of
btree_for_each_entry(e, ...){
do something with e
}
Quoted 6 lines
Quoted 3 lines
macro or function/macro combination? You seem to be doing a recursive walk across the tree, would it be useful to have a linked list at the lowest level of nodes to be able to iterate more easily?
What would you expect to be the behavior if you remove 'e' ? That might cause the tree to get re-ordered. Do you restart the list traversal?
BUG(), if you're lucky. Silent data corruption, if you're not so lucky.
The btree_grim_visitor() exists to remove all element after being handed to the visitor. btree_visitor() removes none. Either function requires the caller to do proper locking. Calling two functions from two threads in parallel or calling a function from the visitor callback will give you undefined results - with the exception of parallel lookups, which are obviously fine.
Jörn
Signature · 3 lines
Beware of bugs in the above code; I have only proved it correct, but not tried it. -- Donald Knuth
Quoted 6 lines · Joern Engel
General advantages of btrees are memory density and efficient use of cachelines. Hashtables are either too small and degrade into linked list performance, or they are too large and waste memory. With changing workloads, both may be true on the same system. Rbtrees have a bad fanout of less than 2 (they are not actually balanced binary trees), hence reading a fairly large number of cachelines to each lookup.
Which reminds me:
find_vma() uses rbtrees. Now I assume find_vma() is called far more than mmap() and friends. Since avltree are balanced (unlike rbtrees) lookups will be faster at the expense of extra rotations during updates.
Would patches for avltrees be accepted?
Thanks
Sean
Quoted 8 lines · Sean Young
Quoted 6 lines · Joern Engel
General advantages of btrees are memory density and efficient use of cachelines. Hashtables are either too small and degrade into linked list performance, or they are too large and waste memory. With changing workloads, both may be true on the same system. Rbtrees have a bad fanout of less than 2 (they are not actually balanced binary trees), hence reading a fairly large number of cachelines to each lookup.
Quoted 5 lines
Which reminds me:
find_vma()uses rbtrees. Now I assumefind_vma()is called far more thanmmap()and friends. Since avltree are balanced (unlike rbtrees) lookups will be faster at the expense of extra rotations during updates.
Maybe I should have been clearer. Rbtrees _are_ balanced trees. They are not balanced _binary_ trees, but balanced 234-trees in a binary representation.
Quoted 1 line
Would patches for avltrees be accepted?
The question is whether they are an improvement. As always.
Jörn
Signature · 3 lines
Das Aufregende am Schreiben ist es, eine Ordnung zu schaffen, wo vorher keine existiert hat. -- Doris Lessing
Quoted 11 lines · Joern Engel
Quoted 10 lines · Sean Young
Quoted 6 lines · Joern Engel
General advantages of btrees are memory density and efficient use of cachelines. Hashtables are either too small and degrade into linked list performance, or they are too large and waste memory. With changing workloads, both may be true on the same system. Rbtrees have a bad fanout of less than 2 (they are not actually balanced binary trees), hence reading a fairly large number of cachelines to each lookup.
Which reminds me:
Quoted 7 lines
Quoted 3 lines
find_vma()uses rbtrees. Now I assumefind_vma()is called far more thanmmap()and friends. Since avltree are balanced (unlike rbtrees) lookups will be faster at the expense of extra rotations during updates.Maybe I should have been clearer. Rbtrees _are_ balanced trees. They are not balanced _binary_ trees, but balanced 234-trees in a binary representation.
I should have been more clearer. avltrees are more rigidly balanced than rbtrees, making them faster for lookups but slower for modification:
http://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures
The difference between the shortest path to a leaf node and the longest path to a leaf node is +1 for avl and *2 for red-black.
Sean