Quoting Mathieu Desnoyers (2013-06-03 01:27:58) > 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. 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 -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
