Skip to contentSkip to conversation

add b+tree library

PATCH In review Johannes Berg 9 participants 24 messages Jan 10, 2009 – Feb 7, 2009 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 add b+tree library

This adds a b+tree library. The API and memory layout is documented in the header file lib/btree.h. There are tree versions for 32, 64 and 128 bit keys as well as unsigned long (32/64 depending on platform).

---
We've tested this code in userspace, and would appreciate still getting it into 2.6.29 because we're working on two separate users for 2.6.30 and it's easier to manage that way. We do not expect API changes before using it, as the code using these trees is almost finished but not well enough tested for .29.

 MAINTAINERS                |    8 
 include/linux/btree-128.h  |  109 ++++++
 include/linux/btree-type.h |  147 ++++++++
 include/linux/btree.h      |  243 +++++++++++++
 lib/Kconfig                |    3 
 lib/Makefile               |    1 
 lib/btree.c                |  797 +++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 1308 insertions(+)
include/linux/btree.h new file +243 -0
@@ -0,0 +1,243 @@
+#ifndef BTREE_H
+#define BTREE_H
+
+#include <linux/kernel.h>
+#include <linux/mempool.h>
+
+/**
+ * DOC: B+Tree basics
+ *
+ * A B+Tree is a data structure for looking up arbitrary (currently allowing
+ * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure
+ * is described at http://en.wikipedia.org/wiki/B-tree, we currently do not
+ * use binary search to find the key on lookups.
+ *
+ * Each B+Tree consists of a head, that contains bookkeeping information and
+ * a variable number (starting with zero) nodes. Each node contains the keys
+ * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the
+ * tree entries.
+ *
+ * Each node in this implementation has the following layout:
+ * [key1, key2, ..., keyN] [val1, val2, ..., valN]
+ *
+ * Each key here is an array of unsigned longs, geo->no_longs in total. The
+ * number of keys and values (N) is geo->no_pairs.
+ */
+
+/**
+ * struct btree_head - btree head
+ *
+ * @node: the first node in the tree
+ * @mempool: mempool used for node allocations
+ * @height: current of the tree
+ */
+struct btree_head {
+	unsigned long *node;
+	mempool_t *mempool;
+	int height;
+};
+
+/* btree geometry */
+struct btree_geo;
+
+/**
+ * btree_alloc - allocate function for the mempool
+ * @gfp_mask: gfp mask for the allocation
+ * @pool_data: unused
+ */
+void *btree_alloc(gfp_t gfp_mask, void *pool_data);
+
+/**
+ * btree_free - free function for the mempool
+ * @element: the element to free
+ * @pool_data: unused
+ */
+void btree_free(void *element, void *pool_data);
+
+/**
+ * btree_init_mempool - initialise a btree with given mempool
+ *
+ * @head: the btree head to initialise
+ * @mempool: the mempool to use
+ *
+ * When this function is used, there is no need to destroy
+ * the mempool.
+ */
+void btree_init_mempool(struct btree_head *head, mempool_t *mempool);
+
+/**
+ * btree_init - initialise a btree
+ *
+ * @head: the btree head to initialise
+ *
+ * This function allocates the memory pool that the
+ * btree needs. Returns zero or a negative error code
+ * (-%ENOMEM) when memory allocation fails.
+ *
+ */
+int __must_check btree_init(struct btree_head *head);
+
+/**
+ * btree_destroy - destroy mempool
+ *
+ * @head: the btree head to destroy
+ *
+ * This function destroys the internal memory pool, use only
+ * when using btree_init(), not with btree_init_mempool().
+ */
+void btree_destroy(struct btree_head *head);
+
+/**
+ * btree_lookup - look up a key in the btree
+ *
+ * @head: the btree to look in
+ * @geo: the btree geometry
+ * @key: the key to look up
+ *
+ * This function returns the value for the given key, or %NULL.
+ */
+void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
+		   unsigned long *key);
+
+/**
+ * btree_insert - insert an entry into the btree
+ *
+ * @head: the btree to add to
+ * @geo: the btree geometry
+ * @key: the key to add (must not already be present)
+ * @val: the value to add (must not be %NULL)
+ * @gfp: allocation flags for node allocations
+ *
+ * This function returns 0 if the item could be added, or an
+ * error code if it failed (may fail due to memory pressure).
+ */
+int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo,
+			      unsigned long *key, void *val, gfp_t gfp);
+/**
+ * btree_update - update an entry in the btree
+ *
+ * @head: the btree to update
+ * @geo: the btree geometry
+ * @key: the key to update
+ * @val: the value to change it to (must not be %NULL)
+ *
+ * This function returns 0 if the update was successful, or
+ * -%ENOENT if the key could not be found.
+ */
+int btree_update(struct btree_head *head, struct btree_geo *geo,
+		 unsigned long *key, void *val);
+/**
+ * btree_remove - remove an entry from the btree
+ *
+ * @head: the btree to update
+ * @geo: the btree geometry
+ * @key: the key to remove
+ *
+ * This function returns the removed entry, or %NULL if the key
+ * could not be found.
+ */
+void *btree_remove(struct btree_head *head, struct btree_geo *geo,
+		   unsigned long *key);
+
+/**
+ * btree_merge - merge two btrees
+ *
+ * @target: the tree that gets all the entries
+ * @victim: the tree that gets merged into @target
+ * @geo: the btree geometry
+ * @gfp: allocation flags
+ *
+ * The two trees @target and @victim may not contain the same keys,
+ * that is a bug and triggers a BUG(). This function returns zero
+ * if the trees were merged successfully, and may return a failure
+ * when memory allocation fails, in which case both trees might have
+ * been partially merged, i.e. some entries have been moved from
+ * @victim to @target.
+ */
+int btree_merge(struct btree_head *target, struct btree_head *victim,
+		struct btree_geo *geo, gfp_t gfp);
+
+/**
+ * btree_last - get last entry in btree
+ *
+ * @head: btree head
+ * @geo: btree geometry
+ * @key: last key
+ *
+ * Returns the last entry in the btree, and sets @key to the key
+ * of that entry; returns NULL if the tree is empty, in that case
+ * key is not changed.
+ */
+void *btree_last(struct btree_head *head, struct btree_geo *geo,
+		 unsigned long *key);
+
+/**
+ * btree_get_prev - get previous entry
+ *
+ * @head: btree head
+ * @geo: btree geometry
+ * @key: pointer to key
+ *
+ * The function returns the next item right before the value pointed to by
+ * @key, and updates @key with its key, or returns %NULL when there is no
+ * entry with a key smaller than the given key.
+ */
+void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
+		     unsigned long *key);
+
+
+/* internal use, use btree_visitor{l,32,64,128} */
+size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
+		     unsigned long opaque,
+		     void (*func)(void *elem, unsigned long opaque,
+				  unsigned long *key, size_t index,
+				  void *func2),
+		     void *func2);
+
+/* internal use, use btree_grim_visitor{l,32,64,128} */
+size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
+			  unsigned long opaque,
+			  void (*func)(void *elem, unsigned long opaque,
+				       unsigned long *key,
+				       size_t index, void *func2),
+			  void *func2);
+
+
+#include <linux/btree-128.h>
+
+extern struct btree_geo btree_geo32;
+#define BTREE_TYPE_SUFFIX l
+#define BTREE_TYPE_BITS BITS_PER_LONG
+#define BTREE_TYPE_GEO &btree_geo32
+#define BTREE_KEYTYPE unsigned long
+#include <linux/btree-type.h>
+
+#define btree_for_each_safel(head, key, val)	\
+	for (val = btree_lastl(head, &key);	\
+	     val;				\
+	     val = btree_get_prevl(head, &key))
+
+#define BTREE_TYPE_SUFFIX 32
+#define BTREE_TYPE_BITS 32
+#define BTREE_TYPE_GEO &btree_geo32
+#define BTREE_KEYTYPE u32
+#include <linux/btree-type.h>
+
+#define btree_for_each_safe32(head, key, val)	\
+	for (val = btree_last32(head, &key);	\
+	     val;				\
+	     val = btree_get_prev32(head, &key))
+
+extern struct btree_geo btree_geo64;
+#define BTREE_TYPE_SUFFIX 64
+#define BTREE_TYPE_BITS 64
+#define BTREE_TYPE_GEO &btree_geo64
+#define BTREE_KEYTYPE u64
+#include <linux/btree-type.h>
+
+#define btree_for_each_safe64(head, key, val)	\
+	for (val = btree_last64(head, &key);	\
+	     val;				\
+	     val = btree_get_prev64(head, &key))
+
+#endif
lib/Kconfig +3 -0
@@ -136,6 +136,9 @@ config TEXTSEARCH_FSM
 config PLIST
 	boolean
 
+config BTREE
+	tristate
+
 config HAS_IOMEM
 	boolean
 	depends on !NO_IOMEM
lib/Makefile +1 -0
@@ -40,6 +40,7 @@ lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += f
 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
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
lib/btree.c new file +797 -0

797 lines not on this page · raw message

include/linux/btree-128.h new file +109 -0

109 lines not on this page · raw message

include/linux/btree-type.h new file +147 -0

147 lines not on this page · raw message

MAINTAINERS +8 -0
@@ -866,6 +866,14 @@ L:	[email protected]
 W:	http://www.linux-ax25.org/
 S:	Maintained
 
+B+TREE
+P:	Johannes Berg
+M:	[email protected]
+P:	Joern Engel
+M:	[email protected]
+L:	[email protected]
+S:	Maintained
+
 B43 WIRELESS DRIVER
 P:	Michael Buesch
 M:	[email protected]
#1 lore raw

Hi

Quoted 3 lines

This adds a b+tree library. The API and memory layout is documented in the header file lib/btree.h. There are tree versions for 32, 64 and 128 bit keys as well as unsigned long (32/64 depending on platform).

Can this library remove the btree code in some btree based filesystem?

#2 lore raw
Quoted 5 lines · KOSAKI Motohiro
Quoted 3 lines

This adds a b+tree library. The API and memory layout is documented in the header file lib/btree.h. There are tree versions for 32, 64 and 128 bit keys as well as unsigned long (32/64 depending on platform).

Can this library remove the btree code in some btree based filesystem?

Joern is going to use it for logfs, that's the point. Not sure about other filesystems.

johannes

#3 lore raw
Quoted 10 lines · Johannes Berg
Quoted 5 lines · KOSAKI Motohiro
Quoted 3 lines

This adds a b+tree library. The API and memory layout is documented in the header file lib/btree.h. There are tree versions for 32, 64 and 128 bit keys as well as unsigned long (32/64 depending on platform).

Can this library remove the btree code in some btree based filesystem?

Joern is going to use it for logfs, that's the point. Not sure about other filesystems.

Err...

While true, this is decidedly _not_ a disk-based btree. Logfs uses it for in-memory data structures. So the short answer is no.

There are several differences between this implementation and one used for disk data.

- The value is a pointer, 32/64bit depending on architecture. Won't be suited for a 64bit filesystem on a 32bit host, f.e.

- Lookups are a simple loop and don't use binary search. With a 4KiB btree node and 64B cacheline, binary search will only load 7 out of 64 cachelines - making a big difference. This implementation uses 128B (or cacheline size, whichever is bigger) nodes, so binary search buy almost nothing, but cause branch mispredictions, bigger code, etc.

There may be more. So if you plan to replace disk-based btree code with this, it will certainly be some amount of work. Not sure if it is a good idea or if one should rather have a seperate library.

Jörn

Signature · 3 lines
The cost of changing business rules is much more expensive for software
than for a secretaty.
-- unknown
#4 lore raw
In reply to Johannes Berg
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

This adds a b+tree library. The API and memory layout is documented in the header file lib/btree.h. There are tree versions for 32, 64 and 128 bit keys as well as unsigned long (32/64 depending on platform).

Can this library remove the btree code in some btree based filesystem?

Joern is going to use it for logfs, that's the point. Not sure about other filesystems.

Why can't you investigate other filesystem?
if this library is used by only one fs, why does this library routine need to linux/lib/ directory?

#5 lore raw
Quoted 7 lines · KOSAKI Motohiro
Quoted 3 lines

Joern is going to use it for logfs, that's the point. Not sure about other filesystems.

Why can't you investigate other filesystem?
if this library is used by only one fs, why does this library routine need to linux/lib/ directory?

Because it is not used for on-disk data structures. It is an alternative to radix trees, rbtrees, hash tables or linked lists.

Jörn

Signature · 3 lines
When in doubt, punt.  When somebody actually complains, go back and fix it...
The 90% solution is a good thing.
-- Rob Landley
#6 lore raw
Quoted 11 lines · Jörn Engel
Quoted 7 lines · KOSAKI Motohiro
Quoted 3 lines

Joern is going to use it for logfs, that's the point. Not sure about other filesystems.

Why can't you investigate other filesystem?
if this library is used by only one fs, why does this library routine need to linux/lib/ directory?

Because it is not used for on-disk data structures. It is an alternative to radix trees, rbtrees, hash tables or linked lists.

Sorry, I misunderstood the question here.

Also, to elaborate on that answer, I'm going to use this as a sort of hash table for wireless, where it ensures better scalability than a pure hashtable from quiet environments (say wireless off on an airplane) to your wireless test lab (100+ access points)

johannes

#7 lore raw
Quoted 4 lines · Johannes Berg

Also, to elaborate on that answer, I'm going to use this as a sort of hash table for wireless, where it ensures better scalability than a pure hashtable from quiet environments (say wireless off on an airplane) to your wireless test lab (100+ access points)

Is there any particular reason you can't use the standard rbtrees for that?

-Andi

Signature · 1 line
[email protected]
#8 lore raw
Quoted 9 lines · Andi Kleen
Quoted 4 lines · Johannes Berg

Also, to elaborate on that answer, I'm going to use this as a sort of hash table for wireless, where it ensures better scalability than a pure hashtable from quiet environments (say wireless off on an airplane) to your wireless test lab (100+ access points)

Is there any particular reason you can't use the standard rbtrees for that?

It just seemed like a lot of overhead, no particular reason I guess.

johannes

#9 lore raw
In reply to Andi Kleen
Quoted 9 lines · Andi Kleen
Quoted 4 lines · Johannes Berg

Also, to elaborate on that answer, I'm going to use this as a sort of hash table for wireless, where it ensures better scalability than a pure hashtable from quiet environments (say wireless off on an airplane) to your wireless test lab (100+ access points)

Is there any particular reason you can't use the standard rbtrees for that?

Can't think of any. You can use linked lists as well. Whether you want to is a different matter.

Key difference is the number of cachelines you need to find a particular entry. rbtrees have a fanout of sqrt(3), so for a million elements (to pick a random example) you need about 25 cachelines with rbtrees and about 5-16 with btrees. Closer to 5 if keys and pointers are small and cachelines are large, closer to 16 if keys and pointers are large and cachelines are small.

Jörn

Signature · 2 lines
The key to performance is elegance, not battalions of special cases.
-- Jon Bentley and Doug McIlroy
#10 lore raw
Quoted 7 lines · Jörn Engel

Key difference is the number of cachelines you need to find a particular entry. rbtrees have a fanout of sqrt(3), so for a million elements (to pick a random example) you need about 25 cachelines with rbtrees and about 5-16 with btrees. Closer to 5 if keys and pointers are small and cachelines are large, closer to 16 if keys and pointers are large and cachelines are small.

Three questions.... is the number of cachelines in use going to make a measurable difference for your use case in the filesystem? If the operation is going to involve disk access, trying to optimize for to improve cacheline utilization may not be the higher priority thing to worry about.

If you have a million elements, and assuming each element is but 4 bytes (which seems unlikely; very likely you'd be indexing at least 8-12 bytes of data, right?) we're talking about 4 megabytes of non-swappable kernel memory. Is that likely to be happen in your use case?

Finally, are b+tree so much better than rbtrees that it would be worthwhile to just *replace* rbtrees with b+trees? Or is the problem the overhead issue if the number of entries in an rbtree is relatively small?

Regards,

- Ted

#11 lore raw
Quoted 9 lines · Theodore Tso
Quoted 7 lines · Jörn Engel

Key difference is the number of cachelines you need to find a particular entry. rbtrees have a fanout of sqrt(3), so for a million elements (to pick a random example) you need about 25 cachelines with rbtrees and about 5-16 with btrees. Closer to 5 if keys and pointers are small and cachelines are large, closer to 16 if keys and pointers are large and cachelines are small.

Quoted 5 lines

Three questions.... is the number of cachelines in use going to make a measurable difference for your use case in the filesystem? If the operation is going to involve disk access, trying to optimize for to improve cacheline utilization may not be the higher priority thing to worry about.

I don't really expect a big difference, even if the filesystem is intended for flash, not disks. Other overhead will dominate the picture. The situation may be different for Johannes, though.

Quoted 5 lines

If you have a million elements, and assuming each element is but 4 bytes (which seems unlikely; very likely you'd be indexing at least 8-12 bytes of data, right?) we're talking about 4 megabytes of non-swappable kernel memory. Is that likely to be happen in your use case?

A million was picked because a) it is easy to calculate with and b) it is sufficiently (insanely) large to illustrate the effect. It is not likely at all in my case. With 1000 elements, which is much more realistic, you can just halve the numbers above.

Quoted 4 lines

Finally, are b+tree so much better than rbtrees that it would be worthwhile to just *replace* rbtrees with b+trees? Or is the problem the overhead issue if the number of entries in an rbtree is relatively small?

Maybe and no. The overhead for near-empty or completely empty trees is fairly low. At one point in time I had one btree for every indirect block and every inode in the filesystem. As a result, struct btree_head contains just two pointers and an int.

One key difference is that rbtrees maintain the tree within objects and btrees maintain the tree externally. So btrees have to allocate memory on insertion, where rbtrees have the necessary memory as part of the object. With mempools the memory allocation should be reasonably safe, so maybe this is a bit of a red herring now.

Another difference is the locking. The current implementation completely ignores locking and depends on the callers to serialize access to the btree.

Keeping all that in mind, I believe many rbtree users could be converted.

Jörn

Signature · 4 lines
The competent programmer is fully aware of the strictly limited size of
his own skull; therefore he approaches the programming task in full
humility, and among other things he avoids clever tricks like the plague.
-- Edsger W. Dijkstra
maintainer
#12 lore raw
Quoted 4 lines · On Sat, 10 Jan 2009 23:01:35 +0100 J__rn Engel <[email protected]> wrote:

One key difference is that rbtrees maintain the tree within objects and btrees maintain the tree externally. So btrees have to allocate memory on insertion, where rbtrees have the necessary memory as part of the object.

This is a major disadvantage of the btrees.

See all the hoops we ended up jumping through with things like radix_tree_preload() and idr_pre_get().

The IDR code there wasn't very well designed and still has holes. The radix-tree code afaik is solid, but look at all the stuff it does!

Quoted 2 lines

With mempools the memory allocation should be reasonably safe,
so maybe this is a bit of a red herring now.

No, mempools won't help, particularly if items are being added from atomic contexts.

This is a major major shortcoming which greatly limits the usefulness of btrees and which greatly reduces the chances of anyone migrating any rbtree users over to btrees.

#13 lore raw
Quoted 7 lines · Andrew Morton
Quoted 4 lines · On Sat, 10 Jan 2009 23:01:35 +0100 J__rn Engel <[email protected]> wrote:

One key difference is that rbtrees maintain the tree within objects and btrees maintain the tree externally. So btrees have to allocate memory on insertion, where rbtrees have the necessary memory as part of the object.

Quoted 7 lines

This is a major disadvantage of the btrees.

See all the hoops we ended up jumping through with things like radix_tree_preload() and idr_pre_get().

The IDR code there wasn't very well designed and still has holes. The radix-tree code afaik is solid, but look at all the stuff it does!

Yeah, its a bit of a mess, but solvable, as radix trees show.

B-tree's however have one thing over RB-trees, B-trees can be made RCU-safe whereas RB-trees cannot be -- the only problem is that Joern's doesn't do that.

I've been poking at my B-tree implementation but got distracted by the mutex spin stuff, its still buggy (still the insert sibling overflow -- the rest should be ok-ish, although I need a hard look at the memory barriers).

---
Subject: lib: RCU friendly B+tree
From: Peter Zijlstra <[email protected]>
Date: Mon Jan 05 14:23:17 CET 2009

A RCU friendly B+tree

---
 include/linux/btree.h |  150 ++++++
 init/main.c           |    2 
 lib/Makefile          |    3 
 lib/btree.c           | 1228 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1382 insertions(+), 1 deletion(-)
include/linux/btree.h new file +150 -0
Index: linux-2.6/include/linux/btree.h
===================================================================
@@ -0,0 +1,150 @@
+#ifndef _LINUX_BTREE_H
+#define _LINUX_BTREE_H
+
+#define BTREE_DEBUG	1
+
+#include <linux/log2.h>
+#include <linux/rcupdate.h>
+#include <linux/bitops.h>
+#include <linux/cache.h>
+
+struct btree_item {
+	unsigned long key;
+	void *data;
+};
+
+#define BTREE_ITEM_CACHELINE (L1_CACHE_BYTES / sizeof(struct btree_item))
+#define BTREE_ITEM_MAX (BTREE_ITEM_CACHELINE < 4 ? 4 : BTREE_ITEM_CACHELINE)
+#define BTREE_ITEM_HALF (BTREE_ITEM_MAX/2)
+
+struct btree_node {
+	struct btree_item item[BTREE_ITEM_MAX];
+};
+
+/*
+ * Max depth of the tree.
+ * Assumes BTREE_ITEM_MAX is power of two.
+ */
+#define BTREE_MAX_DEPTH \
+	(1 + DIV_ROUND_UP(BITS_PER_LONG, ilog2(BTREE_ITEM_MAX)))
+
+/*
+ * Max number of nodes to be RCUed per modification.
+ */
+#define BTREE_NODE_REPLACE (1 + 2 * BTREE_MAX_DEPTH)
+
+struct btree_vec {
+	struct rcu_head rcu_head;
+	int pos;
+	void *slot[BTREE_NODE_REPLACE];
+};
+
+struct btree_root {
+	struct btree_node *root;
+	int height;
+	struct btree_vec *allocvec;
+	struct btree_vec *freevec;
+	gfp_t gfp_mask;
+	void (*flush)(struct btree_vec *);
+};
+
+#ifdef BTREE_DEBUG
+void btree_print(struct btree_root *);
+#else
+#define btree_print(root) do { } while (0)
+#endif
+
+static inline void *btree_item_deref(struct btree_item *itemp)
+{
+	void *ptr = rcu_dereference(itemp->data);
+	__clear_bit(0, (void *)&ptr);
+	return ptr;
+}
+
+static inline unsigned long btree_item_key(struct btree_item *itemp)
+{
+	unsigned long key = itemp->key;
+	/*
+	 * match the smp_wmb() in btree_item_key_set()
+	 */
+	smp_rmb();
+	return key;
+}
+
+extern struct btree_item *btree_search_next(struct btree_root *root,
+		unsigned long index, struct btree_item **nextp);
+
+static inline void *btree_lookup(struct btree_root *root, unsigned long index)
+{
+	struct btree_item *item;
+
+	item = btree_search_next(root, index, NULL);
+	if (!item || btree_item_key(item) != index)
+		return NULL;
+
+	return btree_item_deref(item);
+}
+
+static inline void *btree_lookup_next(struct btree_root *root,
+		unsigned long index, void **nextp)
+{
+	struct btree_item *next = NULL, *item;
+
+	item = btree_search_next(root, index, &next);
+	if (next)
+		*nextp = btree_item_deref(next);
+	if (!item || btree_item_key(item) != index)
+		return NULL;
+
+	return btree_item_deref(item);
+}
+
+static inline void *btree_stab(struct btree_root *root, unsigned long index)
+{
+	struct btree_item *item;
+
+	item = btree_search_next(root, index, NULL);
+	if (!item)
+		return NULL;
+
+	return btree_item_deref(item);
+}
+
+static inline void *btree_stab_next(struct btree_root *root,
+		unsigned long index, void **nextp)
+{
+	struct btree_item *next = NULL, *item;
+
+	item = btree_search_next(root, index, &next);
+	if (next)
+		*nextp = btree_item_deref(next);
+	if (!item)
+		return NULL;
+
+	return btree_item_deref(item);
+}
+
+extern int btree_preload(struct btree_root *, gfp_t);
+extern int btree_insert(struct btree_root *, unsigned long, void *);
+extern int btree_update(struct btree_root *, unsigned long, unsigned long);
+extern void *btree_remove(struct btree_root *, unsigned long);
+
+extern void btree_root_init(struct btree_root *, gfp_t);
+extern void btree_root_destroy(struct btree_root *);
+
+extern void btree_vec_flush(struct btree_vec *);
+
+#define BTREE_INIT_FLUSH(gfp, f) (struct btree_root){ 	\
+	.root = NULL, 					\
+	.height = 0,					\
+	.allocvec = NULL,				\
+	.freevec = NULL,				\
+	.gfp_mask = (gfp),				\
+	.flush = (f),					\
+}
+
+#define BTREE_INIT(gfp) BTREE_INIT_FLUSH(gfp, btree_vec_flush)
+
+extern void __init btree_init(void);
+
+#endif /* _LINUX_BTREE_H */
lib/Makefile +2 -1
Index: linux-2.6/lib/Makefile
===================================================================
@@ -11,7 +11,8 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 rbtree.o radix-tree.o dump_stack.o \
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
-	 proportions.o prio_heap.o ratelimit.o show_mem.o is_single_threaded.o
+	 proportions.o prio_heap.o ratelimit.o show_mem.o \
+	 is_single_threaded.o btree.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
lib/btree.c new file +1228 -0

1,228 lines not on this page · raw message

init/main.c +2 -0
Index: linux-2.6/init/main.c
===================================================================
@@ -66,6 +66,7 @@
 #include <linux/kmemcheck.h>
 #include <linux/ftrace.h>
 #include <trace/boot.h>
+#include <linux/btree.h>
 
 #include <asm/io.h>
 #include <asm/bugs.h>
@@ -654,6 +655,7 @@ asmlinkage void __init start_kernel(void
 	kmemtrace_init();
 	debug_objects_mem_init();
 	idr_init_cache();
+	btree_init();
 	setup_per_cpu_pageset();
 	numa_policy_init();
 	if (late_time_init)
#14 lore raw
Quoted 4 lines · Peter Zijlstra

B-tree's however have one thing over RB-trees, B-trees can be made RCU-safe whereas RB-trees cannot be -- the only problem is that Joern's doesn't do that.

And yours doesn't support multiple key sizes afaics. I don't mind using your version as a basis, so long as my^Wboth requirements get fulfilled. ;)

Do you see a problem combining rcu with keys being an array of unsigned long?

Jörn

Signature · 2 lines
Schrödinger's cat is <BLINK>not</BLINK> dead.
-- Illiad
#15 lore raw
Quoted 6 lines · Jörn Engel
Quoted 4 lines · Peter Zijlstra

B-tree's however have one thing over RB-trees, B-trees can be made RCU-safe whereas RB-trees cannot be -- the only problem is that Joern's doesn't do that.

Quoted 6 lines

And yours doesn't support multiple key sizes afaics. I don't mind using your version as a basis, so long as my^Wboth requirements get fulfilled. ;)

Do you see a problem combining rcu with keys being an array of unsigned long?

There is a theory vs. practice issue here. In theory, you could make any dynamically allocated search structure RCU-searchable by copy-updating the entire structure on each update. In many cases, you only have to replace a fairly small part. In practice, the question is whether your read-to-update ratio is large enough to make it a win.

The main potential issue with keys being an array of unsigned long is that it is no longer possible to atomically rewrite a given key in place. The usual ways to work around this are:

1. Replace each key entry with a pointer to the array of unsigned
longs, so that you can atomically rewrite the pointer. The downside of this approach is the extra cache line accessed per key scanned. The upside of this approach is that you might be able to share code with Peter's tree by using a comparison function (if NULL, just compare the entries directly) or some other similar trick.

2. Place the array of unsigned longs directly in the structure, but
copy-update the entire node rather than rewriting keys in place. This has better cache locality, but makes it more difficult to share code with the small-key variant.

There are probably other tricks as well.

Thanx, Paul

#16 lore raw
In reply to Peter Zijlstra

Let me get back to this...

Quoted 4 lines
Quoted 2 lines

The IDR code there wasn't very well designed and still has holes. The radix-tree code afaik is solid, but look at all the stuff it does!

Yeah, its a bit of a mess, but solvable, as radix trees show.

To be fair, it hasn't been attempted yet though.

Quoted 8 lines

B-tree's however have one thing over RB-trees, B-trees can be made RCU-safe whereas RB-trees cannot be -- the only problem is that Joern's doesn't do that.

I've been poking at my B-tree implementation but got distracted by the mutex spin stuff, its still buggy (still the insert sibling overflow -- the rest should be ok-ish, although I need a hard look at the memory barriers).

Joern may need arbitrary key lengths, don't. But I've just looked around a little:

* radix trees are completely unsuitable for use as a sort of hash table because of their behaviour when keys are not at last mostly contiguous
* rbtrees require lots of boilerplate code, and have much worse cache behaviour

In my use case, tracking the wifi APs around you, you have to scale from a single one to >1k (yes, it's happening!), and lookups better be fast because you might be doing them a lot (dozens of times per second).

johannes

#17 lore raw
Quoted 3 lines

In my use case, tracking the wifi APs around you, you have to scale from a single one to >1k (yes, it's happening!), and lookups better be fast because you might be doing them a lot (dozens of times per second).

dozens of times per second is actually not a lot on any reasonable system. anything that's not totally screwed up (like the rbtrees) should be fine.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#18 lore raw
In reply to Johannes Berg
Quoted 9 lines · Johannes Berg

Joern may need arbitrary key lengths, don't. But I've just looked around a little:

* radix trees are completely unsuitable for use as a sort of hash table because of their behaviour when keys are not at last mostly contiguous
* rbtrees require lots of boilerplate code, and have much worse cache behaviour

I did some testing as well. And I didn't like the results very much. In my test harness, rbtrees performed roughly twice as good as btrees.

Something clearly is wrong with my theory. To spell it out, the theory assumes that 1) CPUs get continuously faster at computations while memory latency stays roughly constant and as a result 2) current CPUs are sufficiently fast that memory latency is more important than a large amount of computation. And maybe 3) L1 cache latency can be ignored, while DRAM latency most definitely can not.

At least one of the above must be wrong. Another interesting data point is that after hacking up binary search within nodes, btrees performed roughly 10% better than before. Binary search means we mispredict every other branch, yet this still improved performance. So on my test CPU (Pentium M), branch mispredictions must be relatively cheap compared to either calculations or L1 cache latency.

I also tried to rig the tests to favor btrees over rbtrees. Since the rb_node is embedded in an object, I grew those objects beyond cacheline size, so no two rb_nodes would ever share a cacheline while all the pointers in btrees still do. And still btrees lost. Well - if the dataset is large enough that all the object padding is comsuming half a gigabyte of memory, swapping will make the rbtree load go slow, but given enough free memory and no swapping (i.e. second run) it beats btrees.

So there are two results I can see from all this. Rbtrees are still a good choice an semi-current machines and the kernel doesn't need much rework yet. Whether my assumption 2) above will match reality better in the future and the scales will tip to the other side I don't know. The other is that my assumptions are wrong somewhere and I don't yet understand where. If anyone has an idea, I'd be glad to hear about it.

Jörn

Signature · 3 lines
Science is like sex: sometimes something useful comes out,
but that is not the reason we are doing it.
-- Richard Feynman
#19 lore raw
In reply to Jörn Engel
Quoted 4 lines · Jörn Engel

I don't really expect a big difference, even if the filesystem is intended for flash, not disks. Other overhead will dominate the picture. The situation may be different for Johannes, though.

If there isn't a big difference, is it really worth it to have both rbtrees and b-trees in the kernel? Especially given the disadvantages akpm noted....

- Ted

#20 lore raw
In reply to Theodore Tso
Quoted 2 lines

Finally, are b+tree so much better than rbtrees that it would be worthwhile to just *replace* rbtrees with b+trees? Or is the problem

There've been a couple of proposals like this over the years, also with other data structures like judy trees (which seem to bring the cache line optimization Joern talks about to even more extreme). splay trees seem to be also a popular suggestion, although they've considered dubious by other people (including me). Another alternative would be skip lists.

Also I don't remember there was ever a big discussion about rbtrees vs other trees -- it was just that Andrea liked them and added a convenient library and some point and other people found it convenient too and started using it.

But it's unclear how much all that would really help.

I always thought it might be advanteous to look at a little more abstract interface for the existing rbtree users (shouldn't be that hard, the interface is already not too bad) and then just let some students implement a couple of backend data structures for that interface and then run some benchmarks.

I don't think it's a good idea to add a b*tree library and use it only from a few users though. After all it's a lot of code and that should have a clear benefit.

-Andi

Signature · 1 line
[email protected]
#21 lore raw
Quoted 10 lines · Andi Kleen
Quoted 3 lines

Finally, are b+tree so much better than rbtrees that it would be worthwhile to just *replace* rbtrees with b+trees? Or is the problem

There've been a couple of proposals like this over the years, also with other data structures like judy trees (which seem to bring the cache line optimization Joern talks about to even more extreme). splay trees seem to be also a popular suggestion, although they've considered dubious by other people (including me). Another alternative would be skip lists.

The number of people that truly understand what Judy trees do may be single-digit. Main disadvantage I see is that Judy trees heavily rely on repacking nodes over and over. Part of Judy is a memory manager with essentially slab caches for nodes with 2, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384 and 512 words.

Splay trees are still binary trees, so the fan-out argument is identical to that against rbtrees. If we have to pull in a cacheline, we might as well use all of it.

Skip lists are just a Bad Idea(tm). In O(x) notation they behave like binary trees, waste cachelines left and right, use more memory, depend on a sufficiently good random() function,... I guess you never closely looked at them, because anyone who does tries to forget them as fast as possible.

Quoted 13 lines

Also I don't remember there was ever a big discussion about rbtrees vs other trees -- it was just that Andrea liked them and added a convenient library and some point and other people found it convenient too and started using it.

But it's unclear how much all that would really help.

I always thought it might be advanteous to look at a little more abstract interface for the existing rbtree users (shouldn't be that hard, the interface is already not too bad) and then just let some students implement a couple of backend data structures for that interface and then run some benchmarks.

Quoted 3 lines

I don't think it's a good idea to add a b*tree library and use it only from a few users though. After all it's a lot of code and that should have a clear benefit.

Quoting Dave Chinner:

| 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....

Jörn

Signature · 2 lines
Joern's library part 15:
http://www.knosof.co.uk/cbook/accu06a.pdf
#22 lore raw

I only listed the proposals I've heard about before, not necessarily endorsing them.

Quoted 5 lines

The number of people that truly understand what Judy trees do may be single-digit. Main disadvantage I see is that Judy trees heavily rely on repacking nodes over and over. Part of Judy is a memory manager with essentially slab caches for nodes with 2, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384 and 512 words.

Well complicated code is en vogue recently :-)

Quoted 9 lines

Splay trees are still binary trees, so the fan-out argument is identical to that against rbtrees. If we have to pull in a cacheline, we might as well use all of it.

Skip lists are just a Bad Idea(tm). In O(x) notation they behave like binary trees, waste cachelines left and right, use more memory, depend on a sufficiently good random() function,... I guess you never closely looked at them, because anyone who does tries to forget them as fast as possible.

Using the radix trees more would be also an alternative.

I honestly don't know how they will all perform in the kernel that is why I thought it would be a good idea to just try them out. But I'm not volunteering to code it up, so it was more an idle thought.

Doing that would be a reasonable student project. In fact I've been asked about this sort of thing by students in the past.

Cleaning up the rbtree interface to be a little more abstract would be probably a good idea in general. I never really liked the open coded searches.

-Andi

#23 lore raw
In reply to Johannes Berg

Hi!

Quoted 12 lines
lib/btree.c new file +9 -0
@@ -0,0 +1,797 @@
+/*
+ * lib/btree.c	- Simple In-memory B+Tree
+ *
+ * As should be obvious for Linux kernel code, license is GPLv2
+ *
+ * Copyright (c) 2007-2008 Joern Engel <[email protected]>
+ * Bits and pieces stolen from Peter Zijlstra's code, which is
+ * Copyright 2007, Red Hat Inc. Peter Zijlstra <[email protected]>
+ * GPLv2

lib/btree.c line 19

Quoted 10 lines
lib/btree.c new file +10 -0
+ *
+ * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
+ *
+ * A relatively simple B+Tree implementation.  I have written it as a learning
+ * excercise to understand how B+Trees work.  Turned out to be useful as well.
+ *
+ * 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.

should be 'much slower'?

Because otherwise I don't get it.

Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html