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 -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com -- 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
