prio_tree shared.vm_set simplifications.

Hello.

I think, prio_tree vm_set managment can be simplified. Patch at the end.

New layout:

struct prio_tree_node {                   struct "vm_area_struct.shared.vmset" {
        struct prio_tree_node  *parent;           void    *parent;
        struct prio_tree_node  *left;             void    *unused;
        struct prio_tree_node  *right;            struct list_head list;
};                                        };                    // list.next == prio_tree_node.right

vmas with identical [radix_index, heap_index] values iterated via list.prev, last element has list.prev == NULL.
First vma (used as a tree node, parent != NULL) do not use list.next, others use it to point back in list.

So, after vma_prio_tree_insert():

       right_node
         /\	
          |
       (next) prev		// parent != 0
               |
               \/
              NULL

after vma_prio_tree_add():

       right_node
         /\
          |
       (next) prev		// parent != 0
         /\    |
          |    \/
        next  prev		// parent == 0
         /\    |
          |    \/
        next  prev		// parent == 0
               |
               \/
              NULL

So, we can use list.next as list pointer if:
parent == 0 OR we reached this node via prev.

With this patch applied, code looks like:

void vma_prio_tree_add(struct vm_area_struct *vma, struct vm_area_struct *old)

{
	struct list_head
		*new  = &vma->shared.vm_set.list;
		*head = &old->shared.vm_set.list;

	new->prev = head->prev;
	if (new->prev)                    <------ TRUE for nonlinear vma!
		new->prev->next = new;    <------ reached via prev, safe

	head->prev = new;
	new->next = head;
}
void vma_prio_tree_remove(struct vm_area_struct *vma, struct prio_tree_root *root)
{
	struct list_head *prev = vma->shared.vm_set.list.prev;

	if (vma->shared.vm_set.parent) {
		if (prev)
			prio_tree_replace(root, &vma->shared.prio_tree_node,
						list_entry(prev, ....));
		else
			prio_tree_remove(root,  &vma->shared.prio_tree_node);
	} else {
		struct list_head *next = vma->shared.vm_set.list.next;

		next->prev = prev;          <------ parent == NULL, safe
		if (prev)
			prev->next = next;  <------ reached via prev, safe
	}
}
struct vm_area_struct *vma_prio_tree_next(vma)
{
	if (!vma)
		return prio_tree_first();

	if (!vma->shared.vm_set.list.prev)
		return prio_tree_next();

	return list_entry(vma->shared.vm_set.list.prev, ....);
}

Please note, that vma_prio_tree_add() works for nonlinear vmas too. Also, vma_prio_tree_remove() now works with them, beacause shuch a vmas have vm_set.parent == 0 && vm_set.list.prev != 0.

I am very interested in your opinion.

Patch against 2.6.8-rc2, compiled, booted, seems to work.

Oleg.

diff -urp 2.6.8-rc2/include/linux/mm.h prio_tree/include/linux/mm.h
@@ -72,9 +72,9 @@ struct vm_area_struct {
 	 */
 	union {
 		struct {
-			struct list_head list;
-			void *parent;	/* aligns with prio_tree_node parent */
-			struct vm_area_struct *head;
+			void	*parent;
+			void	*unused;
+			struct	list_head list;
 		} vm_set;
 
 		struct prio_tree_node prio_tree_node;

@@ -600,10 +600,10 @@ extern void si_meminfo_node(struct sysin
 
 static inline void vma_prio_tree_init(struct vm_area_struct *vma)
 {
+	vma->shared.vm_set.parent = NULL;
+	vma->shared.vm_set.unused = NULL;
 	vma->shared.vm_set.list.next = NULL;
 	vma->shared.vm_set.list.prev = NULL;
-	vma->shared.vm_set.parent = NULL;
-	vma->shared.vm_set.head = NULL;
 }
 
 /* prio_tree.c */

diff -urp 2.6.8-rc2/include/linux/prio_tree.h prio_tree/include/linux/prio_tree.h
@@ -2,9 +2,9 @@
 #define _LINUX_PRIO_TREE_H
 
 struct prio_tree_node {
+	struct prio_tree_node	*parent;
 	struct prio_tree_node	*left;
 	struct prio_tree_node	*right;
-	struct prio_tree_node	*parent;
 };
 
 struct prio_tree_root {