Generalized prio_tree, revisited

Hi Rajesh,

did you have a chance to look at the prio_tree generalization ?

I've attached the patch I posted a month ago (plus the trivial "const" change). It's for 2.6.9, but also applies to 2.6.10-rc2, which I've been using for a good while now.

The patch splits the radix priority search trees into two types:
the "raw" one with implicit keys, as it's currently used, and a new, generalized one with explicit keys, which should be used by new code.

There are currently no in-tree users of the generalized prio_tree, but an example of one can be found in the elevator code of ABISS (abiss.sourceforge.net), where it's used to detect overlapping requests, which in turn is needed to improve barrier handling in the elevator. Jens has also indicated interest in putting overlap handling into the general block IO layer.

At a later point, also VMA could be converted to use explicit keys. That would slightly enlarge struct vm_area_struct, but simplify the code and save a few cycles for key access.

To make the changes clearly visible, this patch doesn't split mm/prio_tree.c into the VMA-specific and the generic part and move the latter to lib/. This can be done at a later time. I've noticed that 2.6.10-rc3-mm1 dummies out prio_tree on systems without MMU. So if combined with this change, the split will need to be done.

Are there any standard benchmarks I could run to show how/if this affects VMA performance ? I'd be surprised if there was much of a change, but you never know.

Thanks,
- Werner

---------------------------------- cut here -----------------------------------

@@ -1,15 +1,38 @@
 #ifndef _LINUX_PRIO_TREE_H
 #define _LINUX_PRIO_TREE_H
 
+/*
+ * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
+ * fields with identical types should end up at the same location. We'll use
+ * this until we can scrap struct raw_prio_tree_node.
+ *
+ * Note: all this could be dome more elegantly by using unnamed union/struct
+ * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
+ * language extension.
+ */
+
+struct raw_prio_tree_node {
+	struct prio_tree_node	*left;
+	struct prio_tree_node	*right;
+	struct prio_tree_node	*parent;
+};
+
 struct prio_tree_node {
 	struct prio_tree_node	*left;
 	struct prio_tree_node	*right;
 	struct prio_tree_node	*parent;
+	unsigned long		start;
+	unsigned long		end;
 };
 
 struct prio_tree_root {
 	struct prio_tree_node	*prio_tree_node;
-	unsigned int 		index_bits;
+	unsigned short 		index_bits;
+	unsigned short		raw;
+		/*
+		 * 0: nodes are of type struct prio_tree_node
+		 * 1: nodes are of type raw_prio_tree_node
+		 */
 };
 
 struct prio_tree_iter {

@@ -31,10 +54,11 @@
 	iter->h_index = h_index;
 }
 
-#define INIT_PRIO_TREE_ROOT(ptr)	\
+#define INIT_PRIO_TREE_ROOT(ptr, _raw)	\
 do {					\
 	(ptr)->prio_tree_node = NULL;	\
 	(ptr)->index_bits = 1;		\
+	(ptr)->raw = (_raw);		\
 } while (0)
 
 #define INIT_PRIO_TREE_NODE(ptr)				\

@@ -73,4 +97,21 @@
 	return node->right == node;
 }
 
+
+struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root, 
+                struct prio_tree_node *old, struct prio_tree_node *node);
+struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root, 
+                struct prio_tree_node *node);
+void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node);
+struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter);
+struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter);
+
+#define raw_prio_tree_replace(root, old, node) \
+	prio_tree_replace(root, (struct prio_tree_node *) (old), \
+	    (struct prio_tree_node *) (node))
+#define raw_prio_tree_insert(root, node) \
+	prio_tree_insert(root, (struct prio_tree_node *) (node))
+#define raw_prio_tree_remove(root, node) \
+	prio_tree_remove(root, (struct prio_tree_node *) (node))
+
 #endif /* _LINUX_PRIO_TREE_H */

@@ -83,7 +83,7 @@
 			struct vm_area_struct *head;
 		} vm_set;
 
-		struct prio_tree_node prio_tree_node;
+		struct raw_prio_tree_node prio_tree_node;
 	} shared;
 
 	/*

@@ -201,7 +201,7 @@
 	atomic_set(&inode->i_data.truncate_count, 0);
 	INIT_LIST_HEAD(&inode->i_data.private_list);
 	spin_lock_init(&inode->i_data.private_lock);
-	INIT_PRIO_TREE_ROOT(&inode->i_data.i_mmap);
+	INIT_PRIO_TREE_ROOT(&inode->i_data.i_mmap, 1);
 	INIT_LIST_HEAD(&inode->i_data.i_mmap_nonlinear);
 	spin_lock_init(&inode->i_lock);
 	i_size_ordered_init(inode);

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/

Yeah, it's not pretty. I also hope this division to be very transitional, that's why I didn't bother to do anything nicer.

Struct names ? I'd rather not duplicate everything. Or did you mean initialization function names, e.g. INIT_RAW_PRIO_TREE_ROOT ? Or, for just the flag, maybe something like
#define PRIO_TREE_RAW 1
#define PRIO_TREE_NORMAL 0
?

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/

Initialisation function names.

Cheers,
Con

Okay, I'll fix this.

Thanks,
- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/

I admit I haven't gone through the patch carefully yet. Overall it looks good except for a problem which bothers me. The "raw" prio_tree can only handle unique intervals, i.e., we cannot insert two intervals with the same indices. Check vm_set.head and vma_prio_tree_* functions to see how multiple vmas with identical indices are handled.

Maybe in your case you don't have to worry about storing multiple identical intervals. However, if we are generalizing prio_tree then we have to consider that, I guess. This is similar to map and multi_map in C++. I _guess_ in prio_tree case we will be using the multi_ variant more often. So, I was thinking something like this:

struct raw_prio_tree_node {}
/* same as in your patch */
struct unique_prio_tree_node {}
/* same as prio_tree_node in your patch */ struct prio_tree_node {}
/* somthing similar to shared in vm_area_struct */

I wish we could have a patch using the generlized prio_tree when we propose to merge the generalized prio_tree code.

I don't think the performance drop will be measurable.

Thanks,
Rajesh

Yes, I admit that I found it convenient (laziness is a survival trait :-) to preserve this property of the underlying code.

In fact, I'm not so sure if we should really offer alternatives at that level, since it seems that adding a conflict resolution layer on top of prio_tree (or including it in the user) is about as much work as including one inside, and the former could be tailored to the specific needs of the user, e.g.

- new entry is rejected
- new entry replaces old entry
- entries are somehow merged (reference count, add partial content, etc.)
- entries neutralize each other
- both entries are kept, in a list (like VMA and the ABISS elevator do)
- both entries are kept, ordered by some other key
- action depends on context

and so on. So it seems to me that we're just at the level of abstraction that gives us the most narrow interface and that doesn't hide any information we need to implement the other cases. And it's just the "engine" that would be used in all cases anyway.

Besides, handling of non-unique entries shouldn't such a big deal that the user whould be seriously inconvenienced by having to do it. E.g. in the case of red-black trees, we also expect the user to do a lot for us.

I just build a list that's usually read in FIFO order. In my case, any kind of overlap needs special handling, so non-unique entries aren't much extra work.

If I was really ambitious, I could try to combine non-unique requests if they all are writes (but then, having a lot of these is probably an indication of problems elsewhere).

Thanks,
- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/

Yeah, makes sense. I think we can consider multi_prio_tree_node later if many future users of prio_tree code need vma->shared.vm_set like handling.

I am okay with the patch. I haven't tested it myself and I won't have time to do so for next few days. Below are some small nitpicks.

Should we go with prio_tree_iter_init and remove prio_tree_first (similar to vma_prio_tree_next) ? I am not very particular about it, though.

Should be "inline" ?

Thanks,
Rajesh

Yes, good idea. I've changed it in my tree.

Indeed. Thanks !

You mean to roll prio_tree_first and prio_tree_iter_init into a single call, so that prio_tree_first would look similar to the one in 2.6.7 ?

That's of course what we hope to happen, but I'd leave the inlining decision to the compiler. After all, it's supposed to be really good at such things nowadays ;-)

Thanks,
- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/

Something like this...

---

linux-2.6.9-testuser/include/linux/prio_tree.h |    1 +
linux-2.6.9-testuser/mm/prio_tree.c            |    3 +++
2 files changed, 4 insertions(+)

diff -puN include/linux/prio_tree.h~roll_prio_tree_first include/linux/prio_tree.h
@@ -29,6 +29,7 @@ static inline void prio_tree_iter_init(s
       iter->root = root;
       iter->r_index = r_index;
       iter->h_index = h_index;
+       iter->cur = NULL;

}

#define INIT_PRIO_TREE_ROOT(ptr) \

diff -puN mm/prio_tree.c~roll_prio_tree_first mm/prio_tree.c
@@ -457,6 +457,9 @@ static struct prio_tree_node *prio_tree_

{
       unsigned long r_index, h_index;

+ if (iter->cur == NULL)
+ return prio_tree_first(iter);
+
repeat:
while (prio_tree_left(iter, &r_index, &h_index))
if (overlap(iter, r_index, h_index))
_

Actually, no - vma_prio_tree_remove uses it too. Reverted.

So that's a change that ought to go in before the actual split, along with changing vma_prio_tree_next to use only prio_tree_next. Okay, it's in my patch set, which I'll post after a bit of testing. (Three overlapping patches, *shiver*.)

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/