On Mon, 2011-05-30 at 14:57 -0400, Mathieu Desnoyers wrote: > * Sasha Levin (levinsasha928@xxxxxxxxx) wrote: > > On Mon, 2011-05-30 at 13:38 -0400, Mathieu Desnoyers wrote: > > > * Sasha Levin (levinsasha928@xxxxxxxxx) wrote: > > > > On Sun, 2011-05-29 at 22:54 -0400, Mathieu Desnoyers wrote: > > > > > Please note that what I currently have is a normal rbtree, not an > > > > > interval rbtree. Can you elaborate on your use-case so I can try to > > > > > figure out how we could augment it to support the interval rbtree you > > > > > need ? > > > > > > > > We don't need anything specific for interval rbtree. The rbtree used in > > > > the kernel provides augmentation functions for insert and erase (see > > > > rb_augment_insert() and rb_augment_erase_begin() + > > > > rb_augment_erase_end()). > > > > What they basically do is call a user-provided callback for each node > > > > from the newly inserted (or deepest after deletion) node up to the root > > > > of the tree. You can see our code at 'tools/kvm/util/rbtree-interval.c', > > > > basically all we need are the 2 augmentation functions I've mentioned > > > > above. > > > > > > Just a little question about Documentation/rbtree.txt: > > > > > > I see that find_lowest_match(lo, hi, node) seems to use ">" and "<" to > > > compare the lo value with the max_hi and node->lo. I think it would be > > > more natural to do range comparison functions with inclusive ranges (>= > > > and <=). Or maybe I am missing something about the way find_lowest_match > > > works ? > > > > It's just an implementation of an interval search() function. Since > > kernel rbtree users implement their own search() and insert() functions > > (look in our util/rbtree-interval.c) it shouldn't be a consideration in > > designing the tree - we (the users of urcu/rbtree) want to control the > > search code anyway. > > The reason why I provide this facility as part of the RCU rbtree is > because, unlike the kernel rbtree where every user is free to use > "inheritance" to put their object in the same cache-line as the rbtree > node, the RCU implementation needs to do copies of its inner nodes, so > the rbtree user cannot expect the node pointer to stay valid. Therefore, > I use a more usual scheme where the pointer to the user-provided data > structure is kept as a "void *key" in the node. So basically, the rbtree > user don't have to provide the search, next and prev functions: this is > all done within the rbtree code, especially because these have to be > RCU-aware, and because the code that augments the rbtree with ranges > needs to be RCU-aware too. > > Finally, my tests showed up that the "<= and >=" need to have the equal > for the ranges to be inclusive. I tested this by using the same > test-case as the search, duplicating the key value as both lower and > upper bound of the range searched for. (see updated rbtree2 branch for > tested range search). > > My stress-test now tests the range lookups, and it passes fine so far: > > e.g. test_urcu_rbtree 6 2 200 -g 40 (on a 8-core machine) Mathieu, I've started working on converting our MMIO code to use RCU rbtree. It looks like each node contains one key, and the search functions search for a node with a key in a specific range. Instead, the key in interval tree nodes is a range, and when searching we try to find which node's range contains our search param. For example, our MMIO mapper maps an address space into devices, so we can have one node which holds the range (0x100-0x200) which maps to a VGA card, a (0x400-0x500) which maps to a sound card, and so on. Then, when a guest is running and tries to write to 0x150, we want to know which device it maps to. -- Sasha. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
