skiplists for range indexes
Subsystems (4)
cover skiplists for range indexes
Hi everyone,
I've been working on skiplists for indexing off/on for a little while now. For btrfs, I really need a fast way to manage extents that doesn't bog down in lock contention for reads or writes. Dave Chinner has mentioned this as well, so I've cc'd him.
Liu Bo started this skiplist code, but at the time it didn't make a huge difference. I've reworked things a bit and used the IOMMU to test things. I ran some benchmarks on a single socket server with two SSD cards to get a baseline of how much it is helping.
I tried to keep the basic structure of the IOMMU code, and there are probably many better ways to fix the IOMMU contention. Really I'm just trying to compare with rbtrees, not fix the IOMMU.
Basic numbers (all aio/dio):
Streaming writes
IOMMU off 2,575MB/s skiplist 1,715MB/s rbtree 1,659MB/s
Not a huge improvement, but the CPU time was lower.
16 threads, iodepth 10, 20MB random reads
IOMMU off 2,861MB/s (mostly idle)
skiplist 2,484MB/s (100% system time)
rbtree 99MB/s (100% system time)
16 threads, iodepth 10, 20MB random writes
IOMMU off 2,548MB/s
skiplist 1,649MB/s
rbtree 33MB/s
I ran this a bunch of times to make sure I got the rbtree numbers right, lowering the thread count did improve the rbtree performance, but the best I could do was around 300MB/s. For skiplists, all of the CPU time is being spent in skiplist_insert_hole, which has a lot of room for improvement.
Quoted 1 line
From here the code needs a lot of testing, and I need to fill out the API
to make it a little easier to use. But, I wanted to send this around for comments and to see how other might want to use things. More details on all internals are below.
It starts with a basic skiplist implementation where:
* skiplist nodes are dynamically sized. There is a slab cache for each node height, so every node is actively using all of the pointers allocated for it.
* Each node has a back pointer as well as a forward pointer
* Each skiplist node stores an array of pointers to items. This is a huge speed improvement because the array of keys is much more cache friendly.
Since the array of item pointers is something of an extension to the basic skiplist, I've separated them out into two structs. First sl_node (just the indexing pointers) and then sl_leaf, which has an sl_node and the array of item pointers.
There's no cache benefit to the leaves if I'm just storing an array of pointers though, so it also has an array of keys:
unsigned long keys[SKIP_KEYS_PER_NODE]; struct sl_slot *ptrs[SKIP_KEYS_PER_NODE];
The keys array is used for the first search pass, and based on that result I narrow things down and only have to follow one or two pointers from the corresponding ptrs array.
The sl_slot is very simple:
struct sl_slot {
unsigned long key;
unsigned long size;
}The idea is to embed the sl_slot in your struct, giving us something like this:
sl_leaf
________________
| node ptr N |
| .... |
| node ptr 0 |
|_______________|
| | keys | |
|___|________|__|
| . | ptrs |. |
|___|________|__|
/ \
/ \
------------- ------------
| sl_slot 0 | | sl_slot N |
| | | |
| data | | data |
------------- -------------
your
structThis basic setup gives us similar performance to rbtrees, but uses less memory. The performance varies (a lot really) with the size of the keys array.
Locking is a mixture of RCU and per-node locking. For searches, it can be pure RCU, or it can use the per-node lock to synchronize the final search though the last leaf. But, everything from the skiplist head to that final node is RCU either way.
Insert locking is slightly different. Before the insert is started, a new node is preallocated. The height of this node is used to pick the level where we start locking nodes during the insert. Much of the time we're able to get through huge portions of the list without any locks.
For deletes, it does an RCU search for the leaf, and hold the per-node lock while we remove a specific slot. If the leaf is empty it is marked as dead and then unlinked from the skiplist level by level.
All the locking and tries does slow things down a bit, but the benefits for concurrent access make a big difference.
RFC PATCH 1/2 core skiplist code
include/linux/skiplist.h new file +179 -0
@@ -0,0 +1,179 @@ +/* +* (C) 2011 Liu Bo <[email protected]> +* (C) 2013 Fusion-io +* +* This program is free software; you can redistribute it and/or modify it under +* the terms of the GNU General Public License as published by the Free Software +* Foundation; version 2 of the License. +* +* This program is distributed in the hope that it will be useful, but WITHOUT +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +* details. +* +* You should have received a copy of the GNU General Public License along with +* this program; if not, write to the Free Software Foundation, Inc., 59 Temple +* Place, Suite 330, Boston, MA 02111-1307 USA +*/ +#ifndef _SKIPLIST_H +#define _SKIPLIST_H + +#include <linux/spinlock.h> +#include <linux/stacktrace.h> + +/* +* This includes a basic skiplist implementation and builds a more +* cache friendly variant on top meant to index ranges of keys. +* +* our random generation function has P at 0.5, so a rough metric +* of good performance happens for lists up to 2^MAXLEVEL in size. +* Since we have an array of keys, you can do 2^MAXLEVEL * SKIP_KEYS_PER_NODE +*/ +#define SKIP_MAXLEVEL 32/* skiplist_get_new_level requires <= 32 */ + +struct sl_node_ptr { +struct sl_node *prev; +struct sl_node *next; +}; + +/* +* sl_node must be last in the leaf data struct. Allocate enough +* ram for a given size using either the sl_ptrs_size or sl_node_size +* helpers. +*/ +struct sl_node { +int level; +int dead; +spinlock_t lock; +struct sl_node_ptr ptrs[]; +}; + +/* +* The head list structure. The head node has no data, +* but it does have the full array of pointers for all the levels. +*/ +struct sl_list { +/* in the head pointer, we use head->prev to point to +* the highest item in the list. But, the last item does +* not point back to the head. The head->prev items +* are protected the by node lock on the last item +*/ +struct sl_node *head; +spinlock_t lock; +unsigned int level; +}; + +/* +* If you are indexing extents, embed sl_slots into your structure and use +* sl_slot_entry to pull out your real struct. The key and size must not +* change if you're using rcu. +*/ +struct sl_slot { +/* +* when rcu is on, we use this key to verify the pointer we pull +* out of the array. It must not change once the object is +* inserted +*/ +unsigned long key; + +/* +* the range searching functions follow pointers into this slot +* struct and use this size field to find out how big the +* range is. +*/ +unsigned long size; + +/* +* there is no reference count here, that's the job of whatever +* struct you embed this into. Good luck. +*/ +}; + +/* +* Larger values here make us faster when single threaded. Lower values +* increase cache misses but give more chances for concurrency. +*/ +#define SKIP_KEYS_PER_NODE 32 + +/* +* For indexing extents, this is a leaf in our skip list tree. +* Each leaf has a number of pointers and the max field +* is used to figure out the key space covered. +*/ +struct sl_leaf { +/* number of valid keys/ptrs in this leaf */ +int nr; + +/* +* max value of the range covered by this leaf. This +* includes the size field of the very last extent, +* so max = keys[last_index] + ptrs[last_index]->size +*/ +unsigned long max; + +/* +* sorted, all the keys +*/ +unsigned long keys[SKIP_KEYS_PER_NODE ]; + +/* +* data pointers corresponding to the keys +*/ +struct sl_slot *ptrs[SKIP_KEYS_PER_NODE ]; + +/* for freeing our objects after the grace period */ +struct rcu_head rcu_head; + +/* this needs to be at the end. The size changes based on the level */ +struct sl_node node; +}; + +/* +* for a given level, how much memory we need for an array of +* all the pointers +*/ +static inline int sl_ptrs_size (int level) +{ +return sizeof (struct sl_node_ptr ) * (level +1 ); +} + +/* +* for a given level, how much memory we need for the +* array of pointers and the sl_node struct +*/ +static inline int sl_node_size (int level) +{ +return sizeof (struct sl_node ) +sl_ptrs_size (level); +} + +static inline int sl_leaf_size (int level) +{ +return sizeof (struct sl_leaf ) +sl_ptrs_size (level); +} + +#define sl_entry (ptr) container_of((ptr), struct sl_leaf, node) +#define sl_slot_entry (ptr, type, member) container_of(ptr, type, member) + +static inline int sl_empty (const struct sl_node *head) +{ +return head->ptrs[0 ].next ==NULL ; +} + +int skiplist_preload (struct sl_list *list,gfp_t gfp_mask); +int skiplist_get_new_level (struct sl_list *list,int max_level); +int skiplist_insert (struct sl_list *list,struct sl_slot *slot, +int preload_token); +int sl_init_list (struct sl_list *list,gfp_t mask); +struct sl_slot *skiplist_lookup (struct sl_list *list,unsigned long key,unsigned long size); +struct sl_slot *skiplist_lookup_rcu (struct sl_list *list,unsigned long key,unsigned long size); +struct sl_slot *skiplist_delete (struct sl_list *list,unsigned long key,unsigned long size); +int skiplist_insert_hole (struct sl_list *list,unsigned long hint, +unsigned long limit, +unsigned long size,unsigned long align, +struct sl_slot *slot, +gfp_t gfp_mask); +void sl_lock_node (struct sl_node *n); +void sl_unlock_node (struct sl_node *n); +void sl_free_leaf (struct sl_leaf *leaf); +unsigned long sl_highest_key (struct sl_list *list); +#endif /* _SKIPLIST_H */
init/main.c +6 -0
@@ -90,6 +90,7 @@ extern void fork_init(unsigned long);extern void mca_init (void );extern void sbus_init (void );extern void radix_tree_init (void ); +extern void skiplist_init (void );#ifndef CONFIG_DEBUG_RODATA static inline void mark_rodata_ro (void ) { }#endif
@@ -548,6 +549,7 @@ asmlinkage void __init start_kernel(void)perf_event_init ();rcu_init ();radix_tree_init (); +/* init some links before init_ISA_irqs() */ early_irq_init ();init_IRQ ();
@@ -566,6 +568,10 @@ asmlinkage void __init start_kernel(void)kmem_cache_init_late (); +#ifdef CONFIG_SKIPLIST +skiplist_init (); +#endif +/* * HACK ALERT! This is early. We're enabling the console before * we've done PCI setups etc, and console_init() must be aware of
lib/Kconfig +14 -0
@@ -393,6 +393,20 @@ config SIGNATURE Digital signature verification. Currently only RSA is supported. Implementation is done using GnuPG MPI library +config SKIPLIST + bool "Concurrent Skiplists" + default n + help + Concurrent skiplist indexing trees. Just say N + +config SKIPLIST_TEST + tristate "Skiplist testing module" + default n + select SKIPLIST + help + Testing module for the skiplist implementation + +# # # libfdt files, only selected if needed. #
lib/Makefile +3 -0
@@ -108,6 +108,9 @@ obj-$(CONFIG_NLATTR) += nlattr.o obj-$(CONFIG_LRU_CACHE) += lru_cache.o +obj-$(CONFIG_SKIPLIST) += skiplist.o +obj-$(CONFIG_SKIPLIST_TEST) += skiplist_test.o + obj-$(CONFIG_DMA_API_DEBUG) += dma-debug.o obj-$(CONFIG_GENERIC_CSUM) += checksum.o
lib/skiplist.c new file +1877 -0
1,877 lines not on this page · raw message
lib/skiplist_test.c new file +688 -0
688 lines not on this page · raw message
Signature · 1 line
1.8.2
RFC PATCH 2/2 skiplists for the IOMMU
In reply to Chris MasonThis is only for experimental use, and it is only lightly tested.
drivers/iommu/intel-iommu.c +0 -4
@@ -1403,7 +1403,6 @@ static void iommu_detach_domain(struct dmar_domain *domain, }static struct iova_domain reserved_iova_list; -static struct lock_class_key reserved_rbtree_key;static int dmar_init_reserved_ranges (void ) {
@@ -1413,9 +1412,6 @@ static int dmar_init_reserved_ranges(void)init_iova_domain (&reserved_iova_list,DMA_32BIT_PFN ); -lockdep_set_class (&reserved_iova_list.iova_rbtree_lock, - &reserved_rbtree_key); -/* IOAPIC ranges shouldn't be accessed by DMA */ iova =reserve_iova (&reserved_iova_list,IOVA_PFN (IOAPIC_RANGE_START ),IOVA_PFN (IOAPIC_RANGE_END ));
drivers/iommu/iova.c +211 -259
560 lines not on this page · raw message
include/linux/iova.h +5 -5
@@ -13,7 +13,7 @@#include <linux/types.h> #include <linux/kernel.h> -#include <linux/rbtree.h> +#include <linux/skiplist.h> #include <linux/dma-mapping.h> /* IO virtual address start page frame number */
@@ -21,16 +21,16 @@/* iova structure */ struct iova { -struct rb_node node; +struct sl_slot slot;unsigned long pfn_hi;/* IOMMU dish out addr hi */ unsigned long pfn_lo;/* IOMMU dish out addr lo */ };/* holds all the iova translations for a domain */ struct iova_domain { -spinlock_t iova_rbtree_lock;/* Lock to protect update of rbtree */ -struct rb_root rbroot;/* iova domain rbtree root */ -struct rb_node *cached32_node;/* Save last alloced node */ +spinlock_t skiplist_lock; +spinlock_t del_skiplist_lock; +struct sl_list skiplist;/* iova domain skiplist */ unsigned long dma_32bit_pfn; };
Signature · 1 line
1.8.2
Jan Kara
reviewerHi,
Quoted 4 lines · Chris Mason
I've been working on skiplists for indexing off/on for a little while now. For btrfs, I really need a fast way to manage extents that doesn't bog down in lock contention for reads or writes. Dave Chinner has mentioned this as well, so I've cc'd him.
But I guess you still need writer-writer exclusion, don't you? Or are you
able to do some partial locking of the structure to allow parallel modifications?
Quoted 8 lines
Liu Bo started this skiplist code, but at the time it didn't make a huge difference. I've reworked things a bit and used the IOMMU to test things. I ran some benchmarks on a single socket server with two SSD cards to get a baseline of how much it is helping.
I tried to keep the basic structure of the IOMMU code, and there are probably many better ways to fix the IOMMU contention. Really I'm just trying to compare with rbtrees, not fix the IOMMU.
There also exist some research papers on RCU friendly RB-trees (or other
trees). Maybe they would be interesting to try? The basic trick is to use a copy-on-write when you need to do a rotation. This is slightly impractical because it requires memory allocation (or alternatively doubles memory footprint of an rb node) but you need to do a similar stuff in skip lists anyway. Just an idea...
Honza
Quoted 112 lines
Basic numbers (all aio/dio):
Streaming writes
IOMMU off 2,575MB/s skiplist 1,715MB/s rbtree 1,659MB/sNot a huge improvement, but the CPU time was lower.
16 threads, iodepth 10, 20MB random reads
IOMMU off 2,861MB/s (mostly idle)
skiplist 2,484MB/s (100% system time)
rbtree 99MB/s (100% system time)16 threads, iodepth 10, 20MB random writes
IOMMU off 2,548MB/s
skiplist 1,649MB/s
rbtree 33MB/sI ran this a bunch of times to make sure I got the rbtree numbers right, lowering the thread count did improve the rbtree performance, but the best I could do was around 300MB/s. For skiplists, all of the CPU time is being spent in
skiplist_insert_hole, which has a lot of room for improvement.From here the code needs a lot of testing, and I need to fill out the API to make it a little easier to use. But, I wanted to send this around for comments and to see how other might want to use things. More details on all internals are below.
It starts with a basic skiplist implementation where:
* skiplist nodes are dynamically sized. There is a slab cache for each node height, so every node is actively using all of the pointers allocated for it.
* Each node has a back pointer as well as a forward pointer
* Each skiplist node stores an array of pointers to items. This is a huge speed improvement because the array of keys is much more cache friendly.
Since the array of item pointers is something of an extension to the basic skiplist, I've separated them out into two structs. First
sl_node(just the indexing pointers) and thensl_leaf, which has ansl_nodeand the array of item pointers.There's no cache benefit to the leaves if I'm just storing an array of pointers though, so it also has an array of keys:
unsigned long keys[SKIP_KEYS_PER_NODE]; struct sl_slot *ptrs[SKIP_KEYS_PER_NODE];The keys array is used for the first search pass, and based on that result I narrow things down and only have to follow one or two pointers from the corresponding ptrs array.
The
sl_slotis very simple:struct sl_slot { unsigned long key; unsigned long size; }The idea is to embed the
sl_slotin your struct, giving us something like this:sl_leaf ________________ | node ptr N | | .... | | node ptr 0 | |_______________| | | keys | | |___|________|__| | . | ptrs |. | |___|________|__| / \ / \ ------------- ------------ | sl_slot 0 | | sl_slot N | | | | | | data | | data | ------------- ------------- your structThis basic setup gives us similar performance to rbtrees, but uses less memory. The performance varies (a lot really) with the size of the keys array.
Locking is a mixture of RCU and per-node locking. For searches, it can be pure RCU, or it can use the per-node lock to synchronize the final search though the last leaf. But, everything from the skiplist head to that final node is RCU either way.
Insert locking is slightly different. Before the insert is started, a new node is preallocated. The height of this node is used to pick the level where we start locking nodes during the insert. Much of the time we're able to get through huge portions of the list without any locks.
For deletes, it does an RCU search for the leaf, and hold the per-node lock while we remove a specific slot. If the leaf is empty it is marked as dead and then unlinked from the skiplist level by level.
All the locking and tries does slow things down a bit, but the benefits for concurrent access make a big difference.
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Quoting Jan Kara (2013-05-03 05:19:24)
Quoted 10 lines
Hi,
Quoted 4 lines · Chris Mason
I've been working on skiplists for indexing off/on for a little while now. For btrfs, I really need a fast way to manage extents that doesn't bog down in lock contention for reads or writes. Dave Chinner has mentioned this as well, so I've cc'd him.
But I guess you still need writer-writer exclusion, don't you? Or are you
able to do some partial locking of the structure to allow parallel modifications?
Hi Jan,
Yes, insert/delete still lock, but they only take locks for the levels required for the operation. So if we're inserting at level 0, we'll walk all the way down to level 0 before taking any locks.
If an insert happens at level 5, it'll start locking at level 5 and build a list of nodes we'll have to update in order to do the insert. Everything in the list is locked until the insert is done.
There's room for optimization there, since chances are good the insertion point will have some free room and I won't need all those locks. The real goal is a little less fine grained, just because all the locking does slow things down when there's no contention.
For the iommu code, the biggest difference between skiplists and rbtrees is the rbtrees are trying to remember a spot they are likely to find free ranges to hand out. The skiplists pick a random starting point and hope the locking spread saves us.
Quoted 9 lines
Quoted 9 lines
Liu Bo started this skiplist code, but at the time it didn't make a huge difference. I've reworked things a bit and used the IOMMU to test things. I ran some benchmarks on a single socket server with two SSD cards to get a baseline of how much it is helping.
I tried to keep the basic structure of the IOMMU code, and there are probably many better ways to fix the IOMMU contention. Really I'm just trying to compare with rbtrees, not fix the IOMMU.
Quoted 6 lines
There also exist some research papers on RCU friendly RB-trees (or other
trees). Maybe they would be interesting to try? The basic trick is to use a copy-on-write when you need to do a rotation. This is slightly impractical because it requires memory allocation (or alternatively doubles memory footprint of an rb node) but you need to do a similar stuff in skip lists anyway. Just an idea...
Definitely interested if you know of alternatives. Most of the ones I saw were RCU for reads but not very fine grained for writes. For btrfs at least, the indexes will be getting a lot of updates and I need higher concurrency on writes.
-chris
Quoted 48 lines · Chris Mason
Quoting Jan Kara (2013-05-03 05:19:24)
Quoted 10 lines
Hi,
Quoted 4 lines · Chris Mason
I've been working on skiplists for indexing off/on for a little while now. For btrfs, I really need a fast way to manage extents that doesn't bog down in lock contention for reads or writes. Dave Chinner has mentioned this as well, so I've cc'd him.
But I guess you still need writer-writer exclusion, don't you? Or are you
able to do some partial locking of the structure to allow parallel modifications?Hi Jan,
Yes, insert/delete still lock, but they only take locks for the levels required for the operation. So if we're inserting at level 0, we'll walk all the way down to level 0 before taking any locks.
If an insert happens at level 5, it'll start locking at level 5 and build a list of nodes we'll have to update in order to do the insert. Everything in the list is locked until the insert is done.
There's room for optimization there, since chances are good the insertion point will have some free room and I won't need all those locks. The real goal is a little less fine grained, just because all the locking does slow things down when there's no contention.
For the iommu code, the biggest difference between skiplists and rbtrees is the rbtrees are trying to remember a spot they are likely to find free ranges to hand out. The skiplists pick a random starting point and hope the locking spread saves us.
Quoted 9 lines
Quoted 9 lines
Liu Bo started this skiplist code, but at the time it didn't make a huge difference. I've reworked things a bit and used the IOMMU to test things. I ran some benchmarks on a single socket server with two SSD cards to get a baseline of how much it is helping.
I tried to keep the basic structure of the IOMMU code, and there are probably many better ways to fix the IOMMU contention. Really I'm just trying to compare with rbtrees, not fix the IOMMU.
Quoted 6 lines
There also exist some research papers on RCU friendly RB-trees (or other
trees). Maybe they would be interesting to try? The basic trick is to use a copy-on-write when you need to do a rotation. This is slightly impractical because it requires memory allocation (or alternatively doubles memory footprint of an rb node) but you need to do a similar stuff in skip lists anyway. Just an idea...
Quoted 4 lines
Definitely interested if you know of alternatives. Most of the ones I saw were RCU for reads but not very fine grained for writes. For btrfs at least, the indexes will be getting a lot of updates and I need higher concurrency on writes.
I've got two cases I care about. The first is the buffer cache indexes which have a 1000:1 read:modify ratio and I'd really like the lookups to be lockless. The other case is the extent tree, where we do lots of inserts when the extent tree is first read, and after than it's typically 2 lookups for every insert/remove. Having one tree that works for both would be handy...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoting Dave Chinner (2013-05-03 23:25:36)
Quoted 7 lines
I've got two cases I care about. The first is the buffer cache indexes which have a 1000:1 read:modify ratio and I'd really like the lookups to be lockless. The other case is the extent tree, where we do lots of inserts when the extent tree is first read, and after than it's typically 2 lookups for every insert/remove. Having one tree that works for both would be handy...
Ok, we're in a similar boat then. I'll finish off some of the API and test the pure RCU side harder.
For the extent tree, are you doing a lot of merging once things are in the tree? I'm not planning on doing pure-rcu for items that get merged quiet yet.
Also, I'm using unsigned longs right now. My guess is we'll both want u64s, which means I have to do an i_size_read/write trick in a few spots.
-chris
Quoted 9 lines · Chris Mason
Quoting Dave Chinner (2013-05-03 23:25:36)
Quoted 7 lines
I've got two cases I care about. The first is the buffer cache indexes which have a 1000:1 read:modify ratio and I'd really like the lookups to be lockless. The other case is the extent tree, where we do lots of inserts when the extent tree is first read, and after than it's typically 2 lookups for every insert/remove. Having one tree that works for both would be handy...
Quoted 6 lines
Ok, we're in a similar boat then. I'll finish off some of the API and test the pure RCU side harder.
For the extent tree, are you doing a lot of merging once things are in the tree? I'm not planning on doing pure-rcu for items that get merged quiet yet.
Yes, we merge extents where ever possible. Almost all contiguous allocations and unwritten extent conversions merge extents in some manner...
Quoted 3 lines
Also, I'm using unsigned longs right now. My guess is we'll both want u64s, which means I have to do an i_size_read/write trick in a few spots.
Yup, definitely needs to be u64 for XFS...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoting Dave Chinner (2013-05-05 03:33:57)
Quoted 13 lines · Chris Mason
Quoted 12 lines
Quoting Dave Chinner (2013-05-03 23:25:36)
Quoted 7 lines
I've got two cases I care about. The first is the buffer cache indexes which have a 1000:1 read:modify ratio and I'd really like the lookups to be lockless. The other case is the extent tree, where we do lots of inserts when the extent tree is first read, and after than it's typically 2 lookups for every insert/remove. Having one tree that works for both would be handy...
Ok, we're in a similar boat then. I'll finish off some of the API and test the pure RCU side harder.
Quoted 7 lines
Quoted 3 lines
For the extent tree, are you doing a lot of merging once things are in the tree? I'm not planning on doing pure-rcu for items that get merged quiet yet.
Yes, we merge extents where ever possible. Almost all contiguous allocations and unwritten extent conversions merge extents in some manner...
Ok, I'll make sure those helpers are generic. The helpers need to search down to the leaf with the items we care about, take the lock and then start merging things together. For btrfs, the decision to merge is pretty complex, so it'll end up driven by the FS code.
The skiplist doesn't do the copy part of rcu. It carefully orders the updates instead, but the merging should still be possible because I'm making sure the keys in the leaf and the slot structure match before trusting what I read.
Quoted 6 lines
Quoted 4 lines
Also, I'm using unsigned longs right now. My guess is we'll both want u64s, which means I have to do an i_size_read/write trick in a few spots.
Yup, definitely needs to be u64 for XFS...
Fair enough. The i_size_read equiv will slow down searches some on 32 bit. I think the hit is worth it though, much better than two trees.
Is your buffer cache radix now or rbtree? It's worth mentioning that radix is still 2x-3x faster than rbtree if you aren't doing range searches.
I'm not sure if that carries from the microbenchmark into something we can notice, but I definitely wouldn't use skiplists for something like the page cache unless we have a good case for a major range based overhaul.
Quoted 37 lines · Chris Mason
Quoting Dave Chinner (2013-05-05 03:33:57)
Quoted 13 lines · Chris Mason
Quoted 12 lines
Quoting Dave Chinner (2013-05-03 23:25:36)
Quoted 7 lines
I've got two cases I care about. The first is the buffer cache indexes which have a 1000:1 read:modify ratio and I'd really like the lookups to be lockless. The other case is the extent tree, where we do lots of inserts when the extent tree is first read, and after than it's typically 2 lookups for every insert/remove. Having one tree that works for both would be handy...
Ok, we're in a similar boat then. I'll finish off some of the API and test the pure RCU side harder.
Quoted 7 lines
Quoted 3 lines
For the extent tree, are you doing a lot of merging once things are in the tree? I'm not planning on doing pure-rcu for items that get merged quiet yet.
Yes, we merge extents where ever possible. Almost all contiguous allocations and unwritten extent conversions merge extents in some manner...
Ok, I'll make sure those helpers are generic. The helpers need to search down to the leaf with the items we care about, take the lock and then start merging things together. For btrfs, the decision to merge is pretty complex, so it'll end up driven by the FS code.
The skiplist doesn't do the copy part of rcu. It carefully orders the updates instead, but the merging should still be possible because I'm making sure the keys in the leaf and the slot structure match before trusting what I read.
Quoted 5 lines
Quoted 4 lines
Also, I'm using unsigned longs right now. My guess is we'll both want u64s, which means I have to do an i_size_read/write trick in a few spots.
Quoted 8 lines
Quoted 1 line
Yup, definitely needs to be u64 for XFS...
Fair enough. The
i_size_readequiv will slow down searches some on 32 bit. I think the hit is worth it though, much better than two trees.Is your buffer cache radix now or rbtree? It's worth mentioning that radix is still 2x-3x faster than rbtree if you aren't doing range searches.
It's an rbtree per allocation group. The code is doing an exact extent match and there is potential for multiple buffers at the same offset (key) into the tree so we can't use a radix tree at all. See _xfs_buf_find() for the rbtree search code...
Also, the metadata buffers are sparsely indexed, so a radix tree gobbles memory pretty badly, too...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoting Dave Chinner (2013-05-05 18:44:16)
Quoted 6 lines · Chris Mason
It's an rbtree per allocation group. The code is doing an exact extent match and there is potential for multiple buffers at the same offset (key) into the tree so we can't use a radix tree at all. See
_xfs_buf_find()for the rbtree search code...
The exact match part won't work with my current code. But a small change will let you pick your own insertion point and allow the duplicates. I'll have to break up deletion a little as well, but it is already setup for this.
After the merge window, I've got linuxcon japan. Once both are done I'll pick this up again and see what I can do.
-chris
Quoted 8 lines · Chris Mason
Quoting Dave Chinner (2013-05-05 18:44:16)
Quoted 6 lines · Chris Mason
It's an rbtree per allocation group. The code is doing an exact extent match and there is potential for multiple buffers at the same offset (key) into the tree so we can't use a radix tree at all. See
_xfs_buf_find()for the rbtree search code...
Quoted 7 lines
The exact match part won't work with my current code. But a small change will let you pick your own insertion point and allow the duplicates. I'll have to break up deletion a little as well, but it is already setup for this.
After the merge window, I've got linuxcon japan. Once both are done I'll pick this up again and see what I can do.
No worries - I'm not in any hurry to replace this code right now. Reducing the number of unnecessary/repeated buffer lookups is probably a bigger win for XFS right now...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]