RCU Judy array with distributed locking for FS extents
Hi Chris,
I stumbled the LWN article "A kernel skiplist implementation (Part 1)", and really thought I should tell you about the side-project I am currently working on: RCU Judy array, with locking distributed within the data structure. I developed my own design of this structure specifically to be usable with RCU. (ref. my LPC2012 presentation:
https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)
I think it would fit your extents use-case perfectly, with excellent cache usage, constant lookup time, near-linear scalability for lookups, and pretty good update scability.
The code is available in a development branch of the Userspace RCU library:
git://git.lttng.org/userspace-rcu.git branch: urcu/rcuja
https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcuja
It runs entirely in user-space, although it can be ported easily to the Linux kernel. I'd be curious to see how it behaves with your workload.
Relevant files:
- rcuja/design.txt: design document of the data structure,
- urcu/rcuja.h (public API)
- rcuja/*.[ch]: implementation
- tests/test_urcu_ja.c: stress-tests, example usage.
After reading the article on skiplists, I added a new API specifically to handle non-overlapping ranges:
struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja,
uint64_t key);
AFAIU, "extents", as far as keys are concerned, are nothing more than segments, with start and end values.
Extents can be indexed by the Judy array in the following way: we use the start of segment as node key, and keep the end of segment value within the leaf node. We add those nodes into the judy array, indexed by start-of-segment value. Then, when we want to figure out if a value matches a segment, we do the following:
1) lookup the possible segment match with cds_ja_lookup_lower_equal(), passing the key to lookup as parameter,
2) check that our key fits within the range of the segment using the end-of-segment value within the leaf node.
Of course, this approach is limited to non-overlapping segments, so I hope this is what you need.
Feedback is welcome!
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoting Mathieu Desnoyers (2013-06-03 01:27:58)
Quoted 43 lines
Hi Chris,
I stumbled the LWN article "A kernel skiplist implementation (Part 1)", and really thought I should tell you about the side-project I am currently working on: RCU Judy array, with locking distributed within the data structure. I developed my own design of this structure specifically to be usable with RCU. (ref. my LPC2012 presentation:
https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)I think it would fit your extents use-case perfectly, with excellent cache usage, constant lookup time, near-linear scalability for lookups, and pretty good update scability.
The code is available in a development branch of the Userspace RCU library:
git://git.lttng.org/userspace-rcu.gitbranch: urcu/rcuja
https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcujaIt runs entirely in user-space, although it can be ported easily to the Linux kernel. I'd be curious to see how it behaves with your workload.
Relevant files:
-rcuja/design.txt: design document of the data structure,
-urcu/rcuja.h(public API)
- rcuja/*.[ch]: implementation
-tests/test_urcu_ja.c: stress-tests, example usage.After reading the article on skiplists, I added a new API specifically to handle non-overlapping ranges:
struct
cds_hlist_headcds_ja_lookup_lower_equal(structcds_ja*ja,uint64_t key);AFAIU, "extents", as far as keys are concerned, are nothing more than segments, with start and end values.
Extents can be indexed by the Judy array in the following way: we use the start of segment as node key, and keep the end of segment value within the leaf node. We add those nodes into the judy array, indexed by start-of-segment value. Then, when we want to figure out if a value matches a segment, we do the following:
Quoted 8 lines
1) lookup the possible segment match with
cds_ja_lookup_lower_equal(), passing the key to lookup as parameter,2) check that our key fits within the range of the segment using the end-of-segment value within the leaf node.
Of course, this approach is limited to non-overlapping segments, so I hope this is what you need.
Hi Mathieu,
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Regardless, it is worth trying out. I'll pull my current code back into userland and try out the userspace-rcu port (I had planned this anyway). That way we can have a proper head-to-head benchmark ;)
-chris
Quoted 50 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-03 01:27:58)
Quoted 49 lines
Hi Chris,
I stumbled the LWN article "A kernel skiplist implementation (Part 1)", and really thought I should tell you about the side-project I am currently working on: RCU Judy array, with locking distributed within the data structure. I developed my own design of this structure specifically to be usable with RCU. (ref. my LPC2012 presentation:
https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)I think it would fit your extents use-case perfectly, with excellent cache usage, constant lookup time, near-linear scalability for lookups, and pretty good update scability.
The code is available in a development branch of the Userspace RCU library:
git://git.lttng.org/userspace-rcu.gitbranch: urcu/rcuja
https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcujaIt runs entirely in user-space, although it can be ported easily to the Linux kernel. I'd be curious to see how it behaves with your workload.
Relevant files:
-rcuja/design.txt: design document of the data structure,
-urcu/rcuja.h(public API)
- rcuja/*.[ch]: implementation
-tests/test_urcu_ja.c: stress-tests, example usage.After reading the article on skiplists, I added a new API specifically to handle non-overlapping ranges:
struct
cds_hlist_headcds_ja_lookup_lower_equal(structcds_ja*ja,uint64_t key);AFAIU, "extents", as far as keys are concerned, are nothing more than segments, with start and end values.
Extents can be indexed by the Judy array in the following way: we use the start of segment as node key, and keep the end of segment value within the leaf node. We add those nodes into the judy array, indexed by start-of-segment value. Then, when we want to figure out if a value matches a segment, we do the following:
1) lookup the possible segment match with
cds_ja_lookup_lower_equal(), passing the key to lookup as parameter,2) check that our key fits within the range of the segment using the end-of-segment value within the leaf node.
Quoted 8 lines
Quoted 2 lines
Of course, this approach is limited to non-overlapping segments, so I hope this is what you need.
Hi Mathieu,
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Are those segments that completely overlap, or partially overlap ?
Quoted 4 lines
Regardless, it is worth trying out. I'll pull my current code back into userland and try out the userspace-rcu port (I had planned this anyway). That way we can have a proper head-to-head benchmark ;)
Cool! Don't hesitate to ping me if I can be of any help.
Thanks,
Mathieu
Quoted 3 lines
-chris
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoting Mathieu Desnoyers (2013-06-03 08:46:01)
Quoted 7 lines
Quoted 5 lines
Hi Mathieu,
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Are those segments that completely overlap, or partially overlap ?
I believe completely overlap. On the skiplist side I'll make it possible for either one.
Quoted 7 lines
Quoted 5 lines
Regardless, it is worth trying out. I'll pull my current code back into userland and try out the userspace-rcu port (I had planned this anyway). That way we can have a proper head-to-head benchmark ;)
Cool! Don't hesitate to ping me if I can be of any help.
Once I get into the userland rcu code I'll probably have more questions.
-chris
Quoted 11 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-03 08:46:01)
Quoted 7 lines
Quoted 5 lines
Hi Mathieu,
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Are those segments that completely overlap, or partially overlap ?
I believe completely overlap. On the skiplist side I'll make it possible for either one.
A complete segment overlap is conceptually the same as having duplicate segments, which makes it easy to handle in my Judy implementation: the nodes returned by a key lookup are a linked RCU hlist. So when a segment match is found for a key, iterating on the linked list of duplicate segments should achieve the intended goal.
Partial overlap can be trickier. There might be extra overhead and complexity required to support those, so I'll wait until this becomes really needed before trying to figure out how to support them in Judy.
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 54 lines · Mathieu Desnoyers
Quoted 53 lines · * Chris Mason ([email protected]) wrote:
Quoting Mathieu Desnoyers (2013-06-03 01:27:58)
Quoted 51 lines
Hi Chris,
I stumbled the LWN article "A kernel skiplist implementation (Part 1)", and really thought I should tell you about the side-project I am currently working on: RCU Judy array, with locking distributed within the data structure. I developed my own design of this structure specifically to be usable with RCU. (ref. my LPC2012 presentation:
https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)I think it would fit your extents use-case perfectly, with excellent cache usage, constant lookup time, near-linear scalability for lookups, and pretty good update scability.
The code is available in a development branch of the Userspace RCU library:
git://git.lttng.org/userspace-rcu.gitbranch: urcu/rcuja
https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcujaIt runs entirely in user-space, although it can be ported easily to the Linux kernel. I'd be curious to see how it behaves with your workload.
Relevant files:
-rcuja/design.txt: design document of the data structure,
-urcu/rcuja.h(public API)
- rcuja/*.[ch]: implementation
-tests/test_urcu_ja.c: stress-tests, example usage.After reading the article on skiplists, I added a new API specifically to handle non-overlapping ranges:
struct
cds_hlist_headcds_ja_lookup_lower_equal(structcds_ja*ja,uint64_t key);AFAIU, "extents", as far as keys are concerned, are nothing more than segments, with start and end values.
Extents can be indexed by the Judy array in the following way: we use the start of segment as node key, and keep the end of segment value within the leaf node. We add those nodes into the judy array, indexed by start-of-segment value. Then, when we want to figure out if a value matches a segment, we do the following:
1) lookup the possible segment match with
cds_ja_lookup_lower_equal(), passing the key to lookup as parameter,2) check that our key fits within the range of the segment using the end-of-segment value within the leaf node.
Of course, this approach is limited to non-overlapping segments, so I hope this is what you need.
Quoted 7 lines
Quoted 5 lines
Hi Mathieu,
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Are those segments that completely overlap, or partially overlap ?
Partial overlap. Can be wholly within an existing exist, or overlap start, end or both.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoting Dave Chinner (2013-06-04 07:54:56)
Quoted 57 lines · Mathieu Desnoyers
Quoted 56 lines · * Chris Mason ([email protected]) wrote:
Quoted 55 lines
Quoting Mathieu Desnoyers (2013-06-03 01:27:58)
Quoted 43 lines
Hi Chris,
I stumbled the LWN article "A kernel skiplist implementation (Part 1)", and really thought I should tell you about the side-project I am currently working on: RCU Judy array, with locking distributed within the data structure. I developed my own design of this structure specifically to be usable with RCU. (ref. my LPC2012 presentation:
https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)I think it would fit your extents use-case perfectly, with excellent cache usage, constant lookup time, near-linear scalability for lookups, and pretty good update scability.
The code is available in a development branch of the Userspace RCU library:
git://git.lttng.org/userspace-rcu.gitbranch: urcu/rcuja
https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcujaIt runs entirely in user-space, although it can be ported easily to the Linux kernel. I'd be curious to see how it behaves with your workload.
Relevant files:
-rcuja/design.txt: design document of the data structure,
-urcu/rcuja.h(public API)
- rcuja/*.[ch]: implementation
-tests/test_urcu_ja.c: stress-tests, example usage.After reading the article on skiplists, I added a new API specifically to handle non-overlapping ranges:
struct
cds_hlist_headcds_ja_lookup_lower_equal(structcds_ja*ja,uint64_t key);AFAIU, "extents", as far as keys are concerned, are nothing more than segments, with start and end values.
Extents can be indexed by the Judy array in the following way: we use the start of segment as node key, and keep the end of segment value within the leaf node. We add those nodes into the judy array, indexed by start-of-segment value. Then, when we want to figure out if a value matches a segment, we do the following:
Quoted 8 lines
1) lookup the possible segment match with
cds_ja_lookup_lower_equal(), passing the key to lookup as parameter,2) check that our key fits within the range of the segment using the end-of-segment value within the leaf node.
Of course, this approach is limited to non-overlapping segments, so I hope this is what you need.
Hi Mathieu,
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Are those segments that completely overlap, or partially overlap ?
Partial overlap. Can be wholly within an existing exist, or overlap start, end or both.
Ouch, ok. In private email yesterday I talked with Mathieu about how his current setup can't prevent the concurrent insertion of overlapping extents. He does have a plan to address this where the insertion is synchronized by keeping placeholders in the tree for the free space. I think it'll work, but I'm worried about doubling the cost of the insert.
Mathieu, I'm going to spend some time on the kernel side of the skiplist code filling out the API and reworking the insert code to get rid of my cursors. I won't have a chance to move it into userland until at least next week.
In terms of comparing the two, I'd rather compare in the kernel so we don't have any surprises. Are you willing to port the judy code in?
-chris
* Chris Mason ([email protected]) wrote:
[...]
Quoted 2 lines
In terms of comparing the two, I'd rather compare in the kernel so we don't have any surprises. Are you willing to port the judy code in?
I'm in a similar situation as yours on the Judy side: I still need to clean up the API and extend its documentation (this is why the Judy code is still in a development branch), and I'd prefer to have the API stabilized on the userspace RCU side before porting it to the kernel. Moreover, I see that it might be a good thing to create an API on top of Judy to handle overlapping and non-overlapping sparse index ranges. Ideally, I'd like to implement this and test it in user-space before porting to the kernel.
I'd be very much interested in helping out in porting your skip list code to Userspace RCU, I think this should be very much straightforward. By the way, would you be willing to license it under LGPLv2.1 so it could be integrated within the Userspace RCU code base ?
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 64 lines · Chris Mason
Quoting Dave Chinner (2013-06-04 07:54:56)
Quoted 63 lines · Mathieu Desnoyers
Quoted 61 lines · * Chris Mason ([email protected]) wrote:
Quoted 50 lines
Quoting Mathieu Desnoyers (2013-06-03 01:27:58)
Quoted 49 lines
Hi Chris,
I stumbled the LWN article "A kernel skiplist implementation (Part 1)", and really thought I should tell you about the side-project I am currently working on: RCU Judy array, with locking distributed within the data structure. I developed my own design of this structure specifically to be usable with RCU. (ref. my LPC2012 presentation:
https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)I think it would fit your extents use-case perfectly, with excellent cache usage, constant lookup time, near-linear scalability for lookups, and pretty good update scability.
The code is available in a development branch of the Userspace RCU library:
git://git.lttng.org/userspace-rcu.gitbranch: urcu/rcuja
https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcujaIt runs entirely in user-space, although it can be ported easily to the Linux kernel. I'd be curious to see how it behaves with your workload.
Relevant files:
-rcuja/design.txt: design document of the data structure,
-urcu/rcuja.h(public API)
- rcuja/*.[ch]: implementation
-tests/test_urcu_ja.c: stress-tests, example usage.After reading the article on skiplists, I added a new API specifically to handle non-overlapping ranges:
struct
cds_hlist_headcds_ja_lookup_lower_equal(structcds_ja*ja,uint64_t key);AFAIU, "extents", as far as keys are concerned, are nothing more than segments, with start and end values.
Extents can be indexed by the Judy array in the following way: we use the start of segment as node key, and keep the end of segment value within the leaf node. We add those nodes into the judy array, indexed by start-of-segment value. Then, when we want to figure out if a value matches a segment, we do the following:
1) lookup the possible segment match with
cds_ja_lookup_lower_equal(), passing the key to lookup as parameter,2) check that our key fits within the range of the segment using the end-of-segment value within the leaf node.
Quoted 8 lines
Quoted 2 lines
Of course, this approach is limited to non-overlapping segments, so I hope this is what you need.
Hi Mathieu,
One problem here is that XFS wants to allow duplicate keys in the tree. This is possible with some modifications to the skiplist code, but I'm not sure if it fits into your description above.
Are those segments that completely overlap, or partially overlap ?
Quoted 8 lines
Quoted 2 lines
Partial overlap. Can be wholly within an existing exist, or overlap start, end or both.
Ouch, ok. In private email yesterday I talked with Mathieu about how his current setup can't prevent the concurrent insertion of overlapping extents. He does have a plan to address this where the insertion is synchronized by keeping placeholders in the tree for the free space. I think it'll work, but I'm worried about doubling the cost of the insert.
Insert cost probably isn't an issue for XFS. Most workloads have a buffer lookup ratio that is dominated by reads and cache hits.
FWIW, I've been thinking of ways of avoiding needing overlaps in the tree to make it simpler to drop in replacements. The overlaps stem from buffers that map freed extents that haven't yet been written to the journal. They are free space, but we have to keep tracking it until the transactiont hat freed the extent hits the disk. In the mean time, it's free space, so it can be reallocated and a new buffer can be built that overlaps part or all of that extent that has been freed. If it's a perfect match we just reuse the existing buffer, but if it isn't we need to have both the new buffer and the old buffer in cache for some period of time...
There's a couple of things I think I can do to rework this so that we don't need to track buffers over free space in the main cache, and that would remove all the overlap issues from the cache. That would certainly make things easier for dropping in some other type of index that doesn't support overlaps easily...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
* Chris Mason ([email protected]) wrote:
[...]
Quoted 5 lines
Ouch, ok. In private email yesterday I talked with Mathieu about how his current setup can't prevent the concurrent insertion of overlapping extents. He does have a plan to address this where the insertion is synchronized by keeping placeholders in the tree for the free space. I think it'll work, but I'm worried about doubling the cost of the insert.
Hi Chris,
The weekend and early week has been productive on my side. My updated work is available on this new branch:
git://git.lttng.org/userspace-rcu.git
branch: urcu/rcuja-range
Since last week, I managed to:
- expand the RCU Judy Array API documentation:
https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/rcuja.h;h=82e272bd4ede1aec436845aef287754dd1dab8b6;hb=03a50ae89ec4d7f39e91d0d49c4639c4cf6e894c
- create an API for Judy Array Ranges, as discussed via email privately:
Please keep in mind that this code has only been moderately stress-tested (with up to 24 cores, on small keyspaces of 3, 5, 10, 100 keys, so races occur much more frequently). It should not be considered production-ready yet.
The test code (and thus examples usage) is available here:
https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=tests/test_urcu_ja_range.c;h=12abcc51465b64a7124fb3e48a2150e225e145af;hb=03a50ae89ec4d7f39e91d0d49c4639c4cf6e894c
https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=tests/test_urcu_ja_range.h;h=e9bbdbc3ed7eb8f57e30c26b8789ba609a6bfdd9;hb=03a50ae89ec4d7f39e91d0d49c4639c4cf6e894c
So far, my benchmarks shows near-linear read-side scalability (as expected from RCU). However, early results does not show the scalability I would have expected for concurrent updates. It's not as bad as, e.g., a global lock making performances crawl due to ping-pong between processors, but so far, roughly speaking, if I multiply the number of cores doing updates by e.g. 12, the per-core throughput of update stress-test gets divided by approximately 12. Therefore, the number of updates system-wide seems to stay constant as we increase the number of cores. I will try to get more info as I dig into more benchmarking, which may point at some memory-throughput bottlenecks.
I stopped working on the range implementation thinking that I should wait to get some feedback before I start implementing more complex features like RCU-friendly range resize.
Feedback is welcome!
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoting Mathieu Desnoyers (2013-06-11 21:12:31)
Quoted 13 lines · * Chris Mason ([email protected]) wrote:
[...]
Quoted 5 lines
Ouch, ok. In private email yesterday I talked with Mathieu about how his current setup can't prevent the concurrent insertion of overlapping extents. He does have a plan to address this where the insertion is synchronized by keeping placeholders in the tree for the free space. I think it'll work, but I'm worried about doubling the cost of the insert.
Hi Chris,
The weekend and early week has been productive on my side. My updated work is available on this new branch:
Quoted 7 lines
git://git.lttng.org/userspace-rcu.git
branch: urcu/rcuja-rangeSince last week, I managed to:
- expand the RCU Judy Array API documentation:
https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/rcuja.h;h=82e272bd4ede1aec436845aef287754dd1dab8b6;hb=03a50ae89ec4d7f39e91d0d49c4639c4cf6e894c
Nice
Quoted 6 lines
- create an API for Judy Array Ranges, as discussed via email privately:
Quoted 7 lines
Please keep in mind that this code has only been moderately stress-tested (with up to 24 cores, on small keyspaces of 3, 5, 10, 100 keys, so races occur much more frequently). It should not be considered production-ready yet.
Ok, I'll definitely take a look.
Quoted 5 lines
The test code (and thus examples usage) is available here:
https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=tests/test_urcu_ja_range.c;h=12abcc51465b64a7124fb3e48a2150e225e145af;hb=03a50ae89ec4d7f39e91d0d49c4639c4cf6e894c
https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=tests/test_urcu_ja_range.h;h=e9bbdbc3ed7eb8f57e30c26b8789ba609a6bfdd9;hb=03a50ae89ec4d7f39e91d0d49c4639c4cf6e894c
Quoted 10 lines
So far, my benchmarks shows near-linear read-side scalability (as expected from RCU). However, early results does not show the scalability I would have expected for concurrent updates. It's not as bad as, e.g., a global lock making performances crawl due to ping-pong between processors, but so far, roughly speaking, if I multiply the number of cores doing updates by e.g. 12, the per-core throughput of update stress-test gets divided by approximately 12. Therefore, the number of updates system-wide seems to stay constant as we increase the number of cores. I will try to get more info as I dig into more benchmarking, which may point at some memory-throughput bottlenecks.
We're benchmarking different workloads, and I'm not sure how much of the scalability difference is from being in the kernel. One test I have here is a batch of deletion and reinsertion of keys at random.
I'm running on a key space of 10 million keys. If I run the same number of random operations on 100,000 keys I get similar (but slightly faster) numbers:
100,000 random insertion and deletions batches:
skiplist: 3.01s per thread rbtree: 2.1s per thread
With 16 threads:
skiplist: 5.8s per thread rbtree: ~70s per thread (ranges from 15s to 76s)
The random part is crucial for scaling with the skiplists. The locks are per node, and as long as all the threads are working in different places things scale fairly well.
Quoted 4 lines
I stopped working on the range implementation thinking that I should wait to get some feedback before I start implementing more complex features like RCU-friendly range resize.
I really wanted to send out my code this morning, but I also wanted to match rbtrees single threaded first. It's much closer now, so I'm commenting and cleaning up what I have for posting tomorrow.
I'll talk with Liu Bo about putting the skiplists under LGPL, but I'd love some help getting numbers against librcu.
-chris
Quoted 2 lines · Chris Mason
Quoting Mathieu Desnoyers (2013-06-11 21:12:31)
Quoted 1 line · * Chris Mason ([email protected]) wrote:
...
Quoted 11 lines
Quoted 4 lines
I stopped working on the range implementation thinking that I should wait to get some feedback before I start implementing more complex features like RCU-friendly range resize.
I really wanted to send out my code this morning, but I also wanted to match rbtrees single threaded first. It's much closer now, so I'm commenting and cleaning up what I have for posting tomorrow.
I'll talk with Liu Bo about putting the skiplists under LGPL, but I'd love some help getting numbers against librcu.
I'm ok with LGPL :)
thanks,
liubo
Quoted 7 lines
-chris
--
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