Hello,
This is a request for comments on a generic AVL-Tree implementation. The
implementation is made generic using the same mechanism in linux/list.h.
It also uses some "creative" macros to generalize the comparison functions.
The patch included was tested against 2.3.30. (It really only touches
mm/mmap.c - thus it will probably also work against later versions.)
Also, I'd appreciate it if someone could point me to benchmarking tools
that can test the MM code's use of AVL trees.
Some additional notes:
This implementation of an AVL-Tree encodes the height of each node into the
lower two bits of one of the pointers. The memory overhead is exactly 8
bytes per node (on a 32-bit system).
The included patch only converts the MM usage of AVL-Trees. The kernel
also uses AVL-Trees in net/bridge/br_tree.c. However, since I do not use
the bridge code, I have not attempted to convert it.
Comments?
-Kevin
-- ------------------------------------------------------------------------ | Kevin O'Connor "BTW, IMHO we need a FAQ for | | koconnor@cse.buffalo.edu 'IMHO', 'FAQ', 'BTW', etc. !" | --------------------------------------------------------------------------a8Wt8u1KmwUX3Y2C Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="genavltree.patch"
--- linux/kernel/Makefile.orig Tue Dec 14 00:19:38 1999 +++ linux/kernel/Makefile Tue Dec 14 00:09:48 1999 @@ -13,7 +13,7 @@ O_TARGET := kernel.o O_OBJS = sched.o dma.o fork.o exec_domain.o panic.o printk.o sys.o \ module.o exit.o itimer.o info.o time.o softirq.o resource.o \ - sysctl.o acct.o capability.o ptrace.o + sysctl.o acct.o capability.o ptrace.o avltree.o OX_OBJS += signal.o --- linux/kernel/avltree.c.orig Tue Dec 14 00:22:45 1999 +++ linux/kernel/avltree.c Thu Dec 16 01:12:24 1999 @@ -0,0 +1,384 @@ +/* Generic AVL-Tree implementation */ + +/* + * Copyright (C) 1999 Kevin O'Connor + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + + +/* AVL Trees. An AVL-Tree (designed by Adelson-Velskii and Landis) is a + * binary tree that maintains balance. For every node in an AVL-Tree the + * height of it's right sub-tree is guaranteed to be no more than one + * larger than the height of it's left sub-tree, and vice-versa. That is: + * abs(rightHeight - leftHeight) <= 1. + * + * This AVL-Tree implementation can work for many different types of + * structures. To use this implementation, create a structure that + * contains a member 'struct avl_node'. The generic implementation works + * by linking the left/right pointers of each item to the address of the + * next structure's 'struct avl_node' sub-element, NOT the address of the + * structure itself. See the avltree.h file for more implementation + * details. + * + * In this implementation, information about the height of each node is + * stored in the node itself. However, instead of storing the absolute + * height in each node, the delta between the left/right sub-tree heights + * is stored. This reduces the size of the data and allows the information + * to be encoded in the lower 2 bits of one of the pointers. + */ + + +#include <linux/avltree.h> + +static inline int +otherChild(int child) +{ + return child == TREE_LEFT ? TREE_RIGHT : TREE_LEFT; +} + +/* + * Bit pointer wrappers + */ + +/* Some functions are defined in the header file. */ +#define getChild avlGetChild +#define childPtrLoc avlChildPtrLoc + +static inline void +setChild(struct avl_node *node, int child, struct avl_node *val) +{ + if (child == TREE_LEFT) { + P2B_SETPTR(node->left, val); + } else { + node->right = val; + } +} + +static inline int +getDelta(struct avl_node *node) +{ + return P2B_GETBITS(node->left); +} + +static inline void +setDelta(struct avl_node *node, int val) +{ + P2B_SETBITS(node->left, val); +} + +/* Dereference a pointer to a pointer to a child. */ +static inline struct avl_node * +getAnonChild(ptr2bit_t *p) +{ + return (struct avl_node *) P2B_GETPTR(*p); +} + +/* Set a pointer to a pointer to a child to a different child address. */ +static inline void +setAnonChild(ptr2bit_t *p, struct avl_node *val) +{ + P2B_SETPTR(*p, val); +} + +/* + * Rotations + */ + +/* Rotate with child: Below is an example of the rotation (it is a "rotate + * with left child" - rotate with right child is a mirror image.) Capital + * letters represent nodes in the tree; lower case letters represent + * subtrees. */ +/* */ +/* N C */ +/* / \ / \ */ +/* C c --> a N */ +/* / \ / \ */ +/* a b b c */ +/* */ +static inline void +rotateWithChild(ptr2bit_t *ptrnode, int child) +{ + int other = otherChild(child); + struct avl_node *node = getAnonChild(ptrnode); + struct avl_node *childnode = getChild(node, child); + int childdiff = getDelta(childnode); + + setAnonChild(ptrnode, childnode); + setChild(node, child, getChild(childnode, other)); + if (childdiff != TREE_BALANCED) { + setDelta(node, TREE_BALANCED); + setDelta(childnode, TREE_BALANCED); + } else { + /* Can only occur on delete */ +// setDelta(node, child); + setDelta(childnode, other); + } + setChild(childnode, other, node); +} + +/* Rotate with grandchild: Also referred to as a double rotate. */ +/* */ +/* N G */ +/* / \ / \ */ +/* C d --> C N */ +/* / \ / \ / \ */ +/* a G a b c d */ +/* / \ */ +/* b c */ +/* */ +static inline void +rotateWithGrandChild(ptr2bit_t *ptrnode, int child) +{ + int other = otherChild(child); + struct avl_node *node = getAnonChild(ptrnode); + struct avl_node *childnode = getChild(node, child); + struct avl_node *grandchildnode = getChild(childnode, other); + int grandchilddiff = getDelta(grandchildnode); + + setAnonChild(ptrnode, grandchildnode); + setChild(node, child, getChild(grandchildnode, other)); + + if (grandchilddiff == child) { + setDelta(node, other); + setDelta(childnode, TREE_BALANCED); + } else if (grandchilddiff == other) { + setDelta(node, TREE_BALANCED); + setDelta(childnode, child); + } else { + setDelta(node, TREE_BALANCED); + setDelta(childnode, TREE_BALANCED); + } + + setChild(childnode, other, getChild(grandchildnode, child)); + + setChild(grandchildnode, child, childnode); + setDelta(grandchildnode, TREE_BALANCED); + setChild(grandchildnode, other, node); +} + +/* + * Main code + */ + +void +__avl_insert(struct avl_node *node, ptr2bit_t *stack[], int stackmax) +{ + int oldheightdiff = TREE_BALANCED; + + /* Perform insert */ + memset(node, 0, sizeof(struct avl_node)); + setAnonChild(stack[stackmax], node); + + /* Rebalance tree */ + while (stackmax) { + int heightdiff, insertside; + struct avl_node *parent = getAnonChild(stack[--stackmax]); + + /* Is the node its parent's left or right child? */ + if (getChild(parent, TREE_LEFT) == node) + insertside = TREE_LEFT; + else + insertside = TREE_RIGHT; + + node = parent; + heightdiff = getDelta(node); + + if (heightdiff == TREE_BALANCED) { + /* The insert slightly unbalances this tree. + Continue checking higher levels. */ + setDelta(node, insertside); + oldheightdiff = insertside; + } else if (heightdiff != insertside) { + /* The insert balances this tree. We're done. */ + setDelta(node, TREE_BALANCED); + return; + } else { + /* The insert unbalances this tree. Perform a + rotate to rebalance it. */ + if (oldheightdiff == heightdiff) { + rotateWithChild(stack[stackmax], insertside); + } else { + rotateWithGrandChild(stack[stackmax] + , insertside); + } + + return; + } + } +} + +void +__avl_remove(ptr2bit_t *stack[], int stackmax) +{ + struct avl_node *node = getAnonChild(stack[stackmax]); + struct avl_node *nextgreatest = getChild(node, TREE_LEFT); + struct avl_node *removenode; + ptr2bit_t *removenodeptr; + int relinkdirection; + + /* Can only remove leaf nodes - if target isn't a leaf, swap its + * position with the next greatest node, and then remove it. */ + if (nextgreatest) { + int newmax = stackmax+1; + struct avl_node *next, tmp; + + /* Find next greatest */ + while ((next = getChild(nextgreatest, TREE_RIGHT))) { + newmax++; + stack[newmax] = childPtrLoc(nextgreatest, TREE_RIGHT); + nextgreatest = next; + } + + /* Exchange found node with original. */ + memcpy(&tmp, node, sizeof(struct avl_node)); + memcpy(node, nextgreatest, sizeof(struct avl_node)); + memcpy(nextgreatest, &tmp, sizeof(struct avl_node)); + + setAnonChild(stack[stackmax], nextgreatest); + stack[stackmax+1] = childPtrLoc(nextgreatest, TREE_LEFT); + setAnonChild(stack[newmax], node); + + stackmax = newmax; + relinkdirection = TREE_LEFT; + } else { + relinkdirection = TREE_RIGHT; + } + + /* Store the remove node for later deletion */ + removenode = node; + removenodeptr = stack[stackmax]; + + /* Rebalance tree */ + while (stackmax) { + int heightdiff, removeside; + struct avl_node *parent = getAnonChild(stack[--stackmax]); + + /* Is the node its parent's left or right child? */ + if (getChild(parent, TREE_LEFT) == node) + removeside = TREE_LEFT; + else + removeside = TREE_RIGHT; + + node = parent; + heightdiff = getDelta(node); + + if (heightdiff == TREE_BALANCED) { + /* The remove slightly unbalances this tree. + That's Ok - we're done. */ + setDelta(node, otherChild(removeside)); + break; + } else if (heightdiff == removeside) { + /* The remove balances this tree. Continue up + higher levels so that they update as well. */ + setDelta(node, TREE_BALANCED); + } else { + /* The remove unbalances this tree. Perform a + rotate to rebalance it. */ + int childdiff = getDelta(getChild(node, heightdiff)); + + if (childdiff == otherChild(heightdiff)) { + rotateWithGrandChild(stack[stackmax] + , heightdiff); + } else { + rotateWithChild(stack[stackmax], heightdiff); + if (childdiff == TREE_BALANCED) { + /* Now slightly imbalanced - we're + done. */ + break; + } + } + + node = getAnonChild(stack[stackmax]); + } + } + + /* Perform the actual remove */ + setAnonChild(removenodeptr, getChild(removenode, relinkdirection)); +} + +#ifdef DEBUG_AVL +/* + * Debugging code. + */ + +#ifndef __KERNEL__ + +/* It is often useful to debug from userspace... */ +#include <stdio.h> +#define printk(args...) +//#define printk printf +#define printe printf + +#else + +#include <linux/kernel.h> +#define printe printk + +#endif /* KERNEL */ + +/* The following code can be used for testing the internal integrity of an + * AVL-Tree. It is recursive - only use it for testing. The depth + * parameter is used in the recursion; outside callers should specify 0. + * The func() callback is invoked with each node in the tree. This + * function can implement ordering checks and/or debugging print + * statements. */ +int +printk_avl(struct avl_node *tree, void (*func)(struct avl_node *), int depth) +{ + int leftheight=0, rightheight=0, err=0; + + printk("tree: %p\n", tree); + + if (tree) { + struct avl_node *next; + int diff; + + printk("("); + next = getChild(tree, TREE_LEFT); + if (next) { + leftheight = printk_avl(next, func, depth+1); + printk(" < "); + } + + diff = getDelta(tree); + printk("*%d/%d*: ", depth, diff); + func(tree); + + next = getChild(tree, TREE_RIGHT); + if (next) { + printk(" > "); + rightheight = printk_avl(next, func, depth+1); + } + + if (abs(leftheight - rightheight) > 1) { + printe(" ERROR imbalanced %d|%d.", leftheight + , rightheight); + err = 1; + } else if ((leftheight > rightheight && diff != TREE_LEFT) + || (leftheight < rightheight && diff != TREE_RIGHT) + || (leftheight == rightheight + && diff != TREE_BALANCED)) { + printe(" ERROR incorrect height."); + err = 1; + } + + printk(")"); + } + + return (leftheight > rightheight ? leftheight : rightheight) + 1; +} + +#endif /* DEBUG_AVL */ --- linux/mm/mmap_avl.c.orig Fri Jan 15 17:41:04 1999 +++ linux/mm/mmap_avl.c Tue Dec 14 00:17:17 1999 @@ -1,374 +0,0 @@ -/* - * Searching a VMA in the linear list task->mm->mmap is horribly slow. - * Use an AVL (Adelson-Velskii and Landis) tree to speed up this search - * from O(n) to O(log n), where n is the number of VMAs of the task - * n is typically around 6, but may reach 3000 in some cases: object-oriented - * databases, persistent store, generational garbage collection (Java, Lisp), - * ElectricFence. - * Written by Bruno Haible <haible@ma2s2.mathematik.uni-karlsruhe.de>. - */ - -/* We keep the list and tree sorted by address. */ -#define vm_avl_key vm_end -#define vm_avl_key_t unsigned long /* typeof(vma->avl_key) */ - -/* - * task->mm->mmap_avl is the AVL tree corresponding to task->mm->mmap - * or, more exactly, its root. - * A vm_area_struct has the following fields: - * vm_avl_left left son of a tree node - * vm_avl_right right son of a tree node - * vm_avl_height 1+max(heightof(left),heightof(right)) - * The empty tree is represented as NULL. - */ - -/* Since the trees are balanced, their height will never be large. */ -#define avl_maxheight 41 /* why this? a small exercise */ -#define heightof(tree) ((tree) == vm_avl_empty ? 0 : (tree)->vm_avl_height) -/* - * Consistency and balancing rules: - * 1. tree->vm_avl_height == 1+max(heightof(tree->vm_avl_left),heightof(tree->vm_avl_right)) - * 2. abs( heightof(tree->vm_avl_left) - heightof(tree->vm_avl_right) ) <= 1 - * 3. foreach node in tree->vm_avl_left: node->vm_avl_key <= tree->vm_avl_key, - * foreach node in tree->vm_avl_right: node->vm_avl_key >= tree->vm_avl_key. - */ - -#ifdef DEBUG_AVL - -/* Look up the nodes at the left and at the right of a given node. */ -static void avl_neighbours (struct vm_area_struct * node, struct vm_area_struct * tree, struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right) -{ - vm_avl_key_t key = node->vm_avl_key; - - *to_the_left = *to_the_right = NULL; - for (;;) { - if (tree == vm_avl_empty) { - printk("avl_neighbours: node not found in the tree\n"); - return; - } - if (key == tree->vm_avl_key) - break; - if (key < tree->vm_avl_key) { - *to_the_right = tree; - tree = tree->vm_avl_left; - } else { - *to_the_left = tree; - tree = tree->vm_avl_right; - } - } - if (tree != node) { - printk("avl_neighbours: node not exactly found in the tree\n"); - return; - } - if (tree->vm_avl_left != vm_avl_empty) { - struct vm_area_struct * node; - for (node = tree->vm_avl_left; node->vm_avl_right != vm_avl_empty; node = node->vm_avl_right) - continue; - *to_the_left = node; - } - if (tree->vm_avl_right != vm_avl_empty) { - struct vm_area_struct * node; - for (node = tree->vm_avl_right; node->vm_avl_left != vm_avl_empty; node = node->vm_avl_left) - continue; - *to_the_right = node; - } - if ((*to_the_left && ((*to_the_left)->vm_next != node)) || (node->vm_next != *to_the_right)) - printk("avl_neighbours: tree inconsistent with list\n"); -} - -#endif - -/* - * Rebalance a tree. - * After inserting or deleting a node of a tree we have a sequence of subtrees - * nodes[0]..nodes[k-1] such that - * nodes[0] is the root and nodes[i+1] = nodes[i]->{vm_avl_left|vm_avl_right}. - */ -static void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr, int count) -{ - for ( ; count > 0 ; count--) { - struct vm_area_struct ** nodeplace = *--nodeplaces_ptr; - struct vm_area_struct * node = *nodeplace; - struct vm_area_struct * nodeleft = node->vm_avl_left; - struct vm_area_struct * noderight = node->vm_avl_right; - int heightleft = heightof(nodeleft); - int heightright = heightof(noderight); - if (heightright + 1 < heightleft) { - /* */ - /* * */ - /* / \ */ - /* n+2 n */ - /* */ - struct vm_area_struct * nodeleftleft = nodeleft->vm_avl_left; - struct vm_area_struct * nodeleftright = nodeleft->vm_avl_right; - int heightleftright = heightof(nodeleftright); - if (heightof(nodeleftleft) >= heightleftright) { - /* */ - /* * n+2|n+3 */ - /* / \ / \ */ - /* n+2 n --> / n+1|n+2 */ - /* / \ | / \ */ - /* n+1 n|n+1 n+1 n|n+1 n */ - /* */ - node->vm_avl_left = nodeleftright; nodeleft->vm_avl_right = node; - nodeleft->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightleftright); - *nodeplace = nodeleft; - } else { - /* */ - /* * n+2 */ - /* / \ / \ */ - /* n+2 n --> n+1 n+1 */ - /* / \ / \ / \ */ - /* n n+1 n L R n */ - /* / \ */ - /* L R */ - /* */ - nodeleft->vm_avl_right = nodeleftright->vm_avl_left; - node->vm_avl_left = nodeleftright->vm_avl_right; - nodeleftright->vm_avl_left = nodeleft; - nodeleftright->vm_avl_right = node; - nodeleft->vm_avl_height = node->vm_avl_height = heightleftright; - nodeleftright->vm_avl_height = heightleft; - *nodeplace = nodeleftright; - } - } - else if (heightleft + 1 < heightright) { - /* similar to the above, just interchange 'left' <--> 'right' */ - struct vm_area_struct * noderightright = noderight->vm_avl_right; - struct vm_area_struct * noderightleft = noderight->vm_avl_left; - int heightrightleft = heightof(noderightleft); - if (heightof(noderightright) >= heightrightleft) { - node->vm_avl_right = noderightleft; noderight->vm_avl_left = node; - noderight->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightrightleft); - *nodeplace = noderight; - } else { - noderight->vm_avl_left = noderightleft->vm_avl_right; - node->vm_avl_right = noderightleft->vm_avl_left; - noderightleft->vm_avl_right = noderight; - noderightleft->vm_avl_left = node; - noderight->vm_avl_height = node->vm_avl_height = heightrightleft; - noderightleft->vm_avl_height = heightright; - *nodeplace = noderightleft; - } - } - else { - int height = (heightleft<heightright ? heightright : heightleft) + 1; - if (height == node->vm_avl_height) - break; - node->vm_avl_height = height; - } - } -} - -/* Insert a node into a tree. */ -static inline void avl_insert (struct vm_area_struct * new_node, struct vm_area_struct ** ptree) -{ - vm_avl_key_t key = new_node->vm_avl_key; - struct vm_area_struct ** nodeplace = ptree; - struct vm_area_struct ** stack[avl_maxheight]; - int stack_count = 0; - struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */ - for (;;) { - struct vm_area_struct * node = *nodeplace; - if (node == vm_avl_empty) - break; - *stack_ptr++ = nodeplace; stack_count++; - if (key < node->vm_avl_key) - nodeplace = &node->vm_avl_left; - else - nodeplace = &node->vm_avl_right; - } - new_node->vm_avl_left = vm_avl_empty; - new_node->vm_avl_right = vm_avl_empty; - new_node->vm_avl_height = 1; - *nodeplace = new_node; - avl_rebalance(stack_ptr,stack_count); -} - -/* Insert a node into a tree, and - * return the node to the left of it and the node to the right of it. - */ -static inline void avl_insert_neighbours (struct vm_area_struct * new_node, struct vm_area_struct ** ptree, - struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right) -{ - vm_avl_key_t key = new_node->vm_avl_key; - struct vm_area_struct ** nodeplace = ptree; - struct vm_area_struct ** stack[avl_maxheight]; - int stack_count = 0; - struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */ - *to_the_left = *to_the_right = NULL; - for (;;) { - struct vm_area_struct * node = *nodeplace; - if (node == vm_avl_empty) - break; - *stack_ptr++ = nodeplace; stack_count++; - if (key < node->vm_avl_key) { - *to_the_right = node; - nodeplace = &node->vm_avl_left; - } else { - *to_the_left = node; - nodeplace = &node->vm_avl_right; - } - } - new_node->vm_avl_left = vm_avl_empty; - new_node->vm_avl_right = vm_avl_empty; - new_node->vm_avl_height = 1; - *nodeplace = new_node; - avl_rebalance(stack_ptr,stack_count); -} - -/* Removes a node out of a tree. */ -static void avl_remove (struct vm_area_struct * node_to_delete, struct vm_area_struct ** ptree) -{ - vm_avl_key_t key = node_to_delete->vm_avl_key; - struct vm_area_struct ** nodeplace = ptree; - struct vm_area_struct ** stack[avl_maxheight]; - int stack_count = 0; - struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */ - struct vm_area_struct ** nodeplace_to_delete; - for (;;) { - struct vm_area_struct * node = *nodeplace; -#ifdef DEBUG_AVL - if (node == vm_avl_empty) { - /* what? node_to_delete not found in tree? */ - printk("avl_remove: node to delete not found in tree\n"); - return; - } -#endif - *stack_ptr++ = nodeplace; stack_count++; - if (key == node->vm_avl_key) - break; - if (key < node->vm_avl_key) - nodeplace = &node->vm_avl_left; - else - nodeplace = &node->vm_avl_right; - } - nodeplace_to_delete = nodeplace; - /* Have to remove node_to_delete = *nodeplace_to_delete. */ - if (node_to_delete->vm_avl_left == vm_avl_empty) { - *nodeplace_to_delete = node_to_delete->vm_avl_right; - stack_ptr--; stack_count--; - } else { - struct vm_area_struct *** stack_ptr_to_delete = stack_ptr; - struct vm_area_struct ** nodeplace = &node_to_delete->vm_avl_left; - struct vm_area_struct * node; - for (;;) { - node = *nodeplace; - if (node->vm_avl_right == vm_avl_empty) - break; - *stack_ptr++ = nodeplace; stack_count++; - nodeplace = &node->vm_avl_right; - } - *nodeplace = node->vm_avl_left; - /* node replaces node_to_delete */ - node->vm_avl_left = node_to_delete->vm_avl_left; - node->vm_avl_right = node_to_delete->vm_avl_right; - node->vm_avl_height = node_to_delete->vm_avl_height; - *nodeplace_to_delete = node; /* replace node_to_delete */ - *stack_ptr_to_delete = &node->vm_avl_left; /* replace &node_to_delete->vm_avl_left */ - } - avl_rebalance(stack_ptr,stack_count); -} - -#ifdef DEBUG_AVL - -/* print a list */ -static void printk_list (struct vm_area_struct * vma) -{ - printk("["); - while (vma) { - printk("%08lX-%08lX", vma->vm_start, vma->vm_end); - vma = vma->vm_next; - if (!vma) - break; - printk(" "); - } - printk("]"); -} - -/* print a tree */ -static void printk_avl (struct vm_area_struct * tree) -{ - if (tree != vm_avl_empty) { - printk("("); - if (tree->vm_avl_left != vm_avl_empty) { - printk_avl(tree->vm_avl_left); - printk("<"); - } - printk("%08lX-%08lX", tree->vm_start, tree->vm_end); - if (tree->vm_avl_right != vm_avl_empty) { - printk(">"); - printk_avl(tree->vm_avl_right); - } - printk(")"); - } -} - -static char *avl_check_point = "somewhere"; - -/* check a tree's consistency and balancing */ -static void avl_checkheights (struct vm_area_struct * tree) -{ - int h, hl, hr; - - if (tree == vm_avl_empty) - return; - avl_checkheights(tree->vm_avl_left); - avl_checkheights(tree->vm_avl_right); - h = tree->vm_avl_height; - hl = heightof(tree->vm_avl_left); - hr = heightof(tree->vm_avl_right); - if ((h == hl+1) && (hr <= hl) && (hl <= hr+1)) - return; - if ((h == hr+1) && (hl <= hr) && (hr <= hl+1)) - return; - printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point); -} - -/* check that all values stored in a tree are < key */ -static void avl_checkleft (struct vm_area_struct * tree, vm_avl_key_t key) -{ - if (tree == vm_avl_empty) - return; - avl_checkleft(tree->vm_avl_left,key); - avl_checkleft(tree->vm_avl_right,key); - if (tree->vm_avl_key < key) - return; - printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->vm_avl_key,key); -} - -/* check that all values stored in a tree are > key */ -static void avl_checkright (struct vm_area_struct * tree, vm_avl_key_t key) -{ - if (tree == vm_avl_empty) - return; - avl_checkright(tree->vm_avl_left,key); - avl_checkright(tree->vm_avl_right,key); - if (tree->vm_avl_key > key) - return; - printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->vm_avl_key,key); -} - -/* check that all values are properly increasing */ -static void avl_checkorder (struct vm_area_struct * tree) -{ - if (tree == vm_avl_empty) - return; - avl_checkorder(tree->vm_avl_left); - avl_checkorder(tree->vm_avl_right); - avl_checkleft(tree->vm_avl_left,tree->vm_avl_key); - avl_checkright(tree->vm_avl_right,tree->vm_avl_key); -} - -/* all checks */ -static void avl_check (struct task_struct * task, char *caller) -{ - avl_check_point = caller; -/* printk("task \"%s\", %s\n",task->comm,caller); */ -/* printk("task \"%s\" list: ",task->comm); printk_list(task->mm->mmap); printk("\n"); */ -/* printk("task \"%s\" tree: ",task->comm); printk_avl(task->mm->mmap_avl); printk("\n"); */ - avl_checkheights(task->mm->mmap_avl); - avl_checkorder(task->mm->mmap_avl); -} - -#endif --- linux/mm/mmap.c.orig Tue Dec 7 21:14:17 1999 +++ linux/mm/mmap.c Thu Dec 16 00:11:00 1999 @@ -366,9 +366,137 @@ } } -#define vm_avl_empty (struct vm_area_struct *) NULL +/* Convert a pointer from &(vma->tree_node) to &vma. */ +#define vmavl_entry(node) avl_entry((node), struct vm_area_struct, tree_node) -#include "mmap_avl.c" +#ifdef DEBUG_AVL +void +vmavl_printk(struct avl_node *node) +{ + struct vm_area_struct *vma = vmavl_entry(node); + + if (node) + printk("start:%lx end:%lx\n", vma->vm_start, vma->vm_end); + else + printk(" NULL \n"); +} +#endif + +static inline struct vm_area_struct * +vmavl_find(struct avl_node *tree, unsigned long addr) +{ + struct vm_area_struct *found = NULL; + +#ifdef DEBUG_AVL + printk("find:%lx\n", addr); +#endif + while (tree) { + struct vm_area_struct *cur = vmavl_entry(tree); + + if (addr < cur->vm_end) { + found = vmavl_entry(tree); + if (addr >= cur->vm_start) + break; + tree = avlGetChild(tree, TREE_LEFT); + } else { + tree = avlGetChild(tree, TREE_RIGHT); + } + } + + return found; +} + +static inline struct vm_area_struct * +vmavl_findwithprev(struct avl_node *tree, unsigned long addr + , struct vm_area_struct **pprev) +{ + struct avl_node *found = NULL; + struct avl_node *prev = NULL, *last_turn_right = NULL; + +#ifdef DEBUG_AVL + printk("find_with_prev:%lx\n", addr); +#endif + while (tree) { + struct vm_area_struct *cur = vmavl_entry(tree); + + if (cur->vm_end > addr) { + found = tree; + prev = last_turn_right; + if (cur->vm_start <= addr) + break; + tree = avlGetChild(tree, TREE_LEFT); + } else { + last_turn_right = tree; + tree = avlGetChild(tree, TREE_RIGHT); + } + } + + if (found) { + struct avl_node *next = avlGetChild(found, TREE_LEFT); + + if (next != NULL) { + prev = next; + while ( (next = avlGetChild(prev, TREE_RIGHT)) != NULL) + prev = next; + } + + *pprev = prev ? vmavl_entry(prev) : NULL; + return vmavl_entry(found); + } + + *pprev = NULL; + return NULL; +} + +static inline int +vmavl_cmpfunc(struct avl_node *node, unsigned long addr) +{ + unsigned long nodeaddr = (vmavl_entry(node))->vm_end; + + return (addr<nodeaddr ? -1 : addr>nodeaddr ? 1 : 0); +} + +static void +vmavl_remove(struct avl_node **root, struct vm_area_struct *node) +{ +#ifdef DEBUG_AVL + printk("remove\n"); + vmavl_printk(&node->tree_node); +#endif + AVL_REMOVE(root, (vmavl_cmpfunc(AVLNode, node->vm_end)) ); +} + +static inline void +vmavl_insert(struct avl_node **root, struct vm_area_struct *node) +{ +#ifdef DEBUG_AVL + printk("insert\n"); + vmavl_printk(&node->tree_node); +#endif + AVL_INSERT(root, &node->tree_node + , (vmavl_cmpfunc(AVLNode, node->vm_end)) ); +} + +static inline void +vmavl_insert_neighbours(struct avl_node **root, struct vm_area_struct *node + , struct vm_area_struct **to_the_left + , struct vm_area_struct **to_the_right) +{ + struct avl_node *left, *right; + ptr2bit_t *stack[AVL_MAXHEIGHT]; + int count; + +#ifdef DEBUG_AVL + printk("insert_neighbours\n"); + vmavl_printk(&node->tree_node); +#endif + AVL_FINDWITHSTACK(root, stack, count, left, right + , (vmavl_cmpfunc(AVLNode, node->vm_end)) ); + __avl_insert(&node->tree_node, stack, count); + + *to_the_left = left ? vmavl_entry(left) : NULL; + *to_the_right = right ? vmavl_entry(right) : NULL; +} /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */ struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr) @@ -387,19 +515,7 @@ vma = vma->vm_next; } else { /* Then go through the AVL tree quickly. */ - struct vm_area_struct * tree = mm->mmap_avl; - vma = NULL; - for (;;) { - if (tree == vm_avl_empty) - break; - if (tree->vm_end > addr) { - vma = tree; - if (tree->vm_start <= addr) - break; - tree = tree->vm_avl_left; - } else - tree = tree->vm_avl_right; - } + vma = vmavl_find(mm->mmap_avl, addr); } if (vma) mm->mmap_cache = vma; @@ -425,35 +541,12 @@ return vma; } else { /* Go through the AVL tree quickly. */ - struct vm_area_struct * vma = NULL; - struct vm_area_struct * last_turn_right = NULL; - struct vm_area_struct * prev = NULL; - struct vm_area_struct * tree = mm->mmap_avl; - for (;;) { - if (tree == vm_avl_empty) - break; - if (tree->vm_end > addr) { - vma = tree; - prev = last_turn_right; - if (tree->vm_start <= addr) - break; - tree = tree->vm_avl_left; - } else { - last_turn_right = tree; - tree = tree->vm_avl_right; - } - } - if (vma) { - if (vma->vm_avl_left != vm_avl_empty) { - prev = vma->vm_avl_left; - while (prev->vm_avl_right != vm_avl_empty) - prev = prev->vm_avl_right; - } - if ((prev ? prev->vm_next : mm->mmap) != vma) - printk("find_vma_prev: tree inconsistent with list\n"); - *pprev = prev; - return vma; - } + struct vm_area_struct *vma; + vma = vmavl_findwithprev(mm->mmap_avl, addr, pprev); + + if ((*pprev ? (*pprev)->vm_next : mm->mmap) != vma) + printk("find_vma_prev: tree inconsistent with list\n"); + return vma; } } *pprev = NULL; @@ -665,7 +758,7 @@ mpnt->vm_next = free; free = mpnt; if (mm->mmap_avl) - avl_remove(mpnt, &mm->mmap_avl); + vmavl_remove(&mm->mmap_avl, mpnt); } mm->mmap_cache = NULL; /* Kill the cache. */ vmlist_modify_unlock(mm); @@ -812,7 +905,7 @@ mm->mmap_avl = NULL; for (vma = mm->mmap; vma; vma = vma->vm_next) - avl_insert(vma, &mm->mmap_avl); + vmavl_insert(&mm->mmap_avl, vma); } /* Release all mmaps. */ @@ -823,7 +916,8 @@ release_segments(mm); mpnt = mm->mmap; vmlist_modify_lock(mm); - mm->mmap = mm->mmap_avl = mm->mmap_cache = NULL; + mm->mmap = mm->mmap_cache = NULL; + mm->mmap_avl = NULL; vmlist_modify_unlock(mm); mm->rss = 0; mm->total_vm = 0; @@ -870,7 +964,7 @@ pprev = &(*pprev)->vm_next; } else { struct vm_area_struct *prev, *next; - avl_insert_neighbours(vmp, &mm->mmap_avl, &prev, &next); + vmavl_insert_neighbours(&mm->mmap_avl, vmp, &prev, &next); pprev = (prev ? &prev->vm_next : &mm->mmap); if (*pprev != next) printk("insert_vm_struct: tree inconsistent with list\n"); @@ -952,7 +1046,7 @@ * The old unused mpnt is freed. */ if (mm->mmap_avl) - avl_remove(mpnt, &mm->mmap_avl); + vmavl_remove(&mm->mmap_avl, mpnt); prev->vm_end = mpnt->vm_end; prev->vm_next = mpnt->vm_next; if (mpnt->vm_ops && mpnt->vm_ops->close) { --- linux/include/linux/sched.h.orig Tue Dec 7 21:40:40 1999 +++ linux/include/linux/sched.h Thu Dec 16 00:57:02 1999 @@ -206,7 +206,7 @@ struct mm_struct { struct vm_area_struct * mmap; /* list of VMAs */ - struct vm_area_struct * mmap_avl; /* tree of VMAs */ + struct avl_node *mmap_avl; /* tree of VMAs */ struct vm_area_struct * mmap_cache; /* last find_vma result */ pgd_t * pgd; atomic_t mm_users; /* How many users with user space? */ --- linux/include/linux/mm.h.orig Tue Dec 7 21:40:40 1999 +++ linux/include/linux/mm.h Thu Dec 16 01:00:02 1999 @@ -10,6 +10,7 @@ #include <linux/string.h> #include <linux/list.h> #include <linux/mmzone.h> +#include <linux/avltree.h> extern unsigned long max_mapnr; extern unsigned long num_physpages; @@ -47,9 +48,7 @@ unsigned short vm_flags; /* AVL tree of VM areas per task, sorted by address */ - short vm_avl_height; - struct vm_area_struct * vm_avl_left; - struct vm_area_struct * vm_avl_right; + struct avl_node tree_node; /* For areas with inode, the list inode->i_mmap, for shm areas, * the list of attaches, otherwise unused. --- linux/include/linux/avltree.h.orig Tue Dec 14 00:24:13 1999 +++ linux/include/linux/avltree.h Thu Dec 16 00:56:42 1999 @@ -0,0 +1,215 @@ +#ifndef _LINUX_AVLTREE_H +#define _LINUX_AVLTREE_H + +#include <linux/bitpointers.h> + +#define AVL_MAXHEIGHT 41 + +/* AVL_MAXHEIGHT is only used by the macros AVL_INSERT and AVL_REMOVE. + * They use this value to determine the stack size that should be + * allocated. No where in the actual code is this value checked - there is + * no overflow detection. However, an AVL-Tree of height 41 is gaurenteed + * to hold at least (approx) 700733725 items. + * + * Minimum capacity (approx) = (1.618 ^ (Height + 3)) / sqrt(5) + */ + +#define avl_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) + + +/* + * Types + */ + +struct avl_node { + ptr2bit_t left; + void *right; +}; + +enum { + TREE_BALANCED = 0, /* Used only internally */ + TREE_LEFT = 1, + TREE_RIGHT = 2, +}; + +/* + * Function definitions + */ + +void __avl_insert(struct avl_node *node, ptr2bit_t *stack[], int stackmax); +void __avl_remove(ptr2bit_t *stack[], int stackmax); + +/* + * Bit pointer wrappers + */ + +static inline struct avl_node * +avlGetChild(struct avl_node *node, int child) +{ + if (child == TREE_LEFT) { + return (struct avl_node *) P2B_GETPTR(node->left); + } else { + return (struct avl_node *) node->right; + } +} + +static inline ptr2bit_t * +avlChildPtrLoc(struct avl_node *node, int child) +{ + if (child == TREE_LEFT) { + return (ptr2bit_t *) P2B_GETPTRLOC(node->left); + } else { + return (ptr2bit_t *) &node->right; + } +} + + +/* + * Function Suite + */ + +/* The following macros are templates for the main functions performed on a + * binary tree. Each of the functions take a parameter "__Compare". This + * parameter should be filled with code that interrogates the provided + * variable "AVLNode" and returns a value greater than, less than, or equal + * to zero depending on whether the left tree should be searched, the right + * tree searched, or if the current node should be returned. + * + * Note: The __Compare parameter should be substituted with _code_ that can + * be inlined into the search. See the example implementation at the end + * of this file for more information. + */ + +#define AVL_FIND(__Tree,__LastLeft,__LastRight,__Compare) ({ \ + struct avl_node *AVLNode=(__Tree); \ + \ + __LastLeft = __LastRight = NULL; \ + while (AVLNode) { \ + int __compval = (__Compare); \ + \ + if (__compval < 0) { \ + __LastRight = AVLNode; \ + AVLNode = avlGetChild(AVLNode, TREE_LEFT); \ + } else if (__compval > 0) { \ + __LastLeft = AVLNode; \ + AVLNode = avlGetChild(AVLNode, TREE_RIGHT); \ + } else { \ + break; \ + } \ + } \ + AVLNode;}) + +#define AVL_FINDWITHSTACK(__TreeP,__Stack,__Count,__L,__R,__Compare) ({ \ + struct avl_node **__tree = (__TreeP); \ + struct avl_node *AVLNode = *__tree; \ + ptr2bit_t **__stack = (__Stack); \ + int __found=0; \ + \ + __L = __R = NULL; \ + __Count = 0; \ + *__stack++ = (ptr2bit_t *) __tree; \ + while (AVLNode) { \ + int __compval = (__Compare); \ + \ + if (__compval < 0) { \ + __R = AVLNode; \ + (__Count)++; \ + *__stack++ = avlChildPtrLoc(AVLNode \ + , TREE_LEFT); \ + AVLNode = avlGetChild(AVLNode, TREE_LEFT); \ + } else if (__compval > 0) { \ + __L = AVLNode; \ + (__Count)++; \ + *__stack++ = avlChildPtrLoc(AVLNode \ + , TREE_RIGHT); \ + AVLNode = avlGetChild(AVLNode, TREE_RIGHT); \ + } else { \ + __found = 1; \ + break; \ + } \ + } \ + __found;}) + +#define AVL_REMOVE(__TreeP,__Compare) ({ \ + struct avl_node *__dummy; \ + ptr2bit_t *__stk[AVL_MAXHEIGHT]; \ + int __cnt, __ret; \ + \ + if (! AVL_FINDWITHSTACK((__TreeP),__stk,__cnt \ + ,__dummy,__dummy,(__Compare))) { \ + __ret = 0; \ + } else { \ + __avl_remove(__stk, __cnt); \ + __ret = 1; \ + } \ + __ret;}) + +#define AVL_INSERT(__TreeP,__Node,__Compare) ({ \ + struct avl_node *__dummy; \ + ptr2bit_t *__stk[AVL_MAXHEIGHT]; \ + int __cnt, __ret; \ + \ + if (AVL_FINDWITHSTACK((__TreeP),__stk,__cnt \ + ,__dummy,__dummy,(__Compare))) { \ + __ret = 0; \ + } else { \ + __avl_insert((__Node), __stk, __cnt); \ + __ret = 1; \ + } \ + __ret;}) + + +/* SAMPLE IMPLEMENTATION: + * + * #include <avltree.h> + * + * struct sample_data { + * int num; + * struct avl_node treenode; + * }; + * + * * Note the use of inline here. Inline isn't required, but since the + * * comparison function is small reducing call instructions should improve + * * performance. + * inline int + * sample_compare(struct avl_node *x, int num) + * { + * int nodenum = avl_entry(x, struct sample_data, treenode)->num; + * + * return (num < nodenum ? -1 : num > nodenum ? 1 : 0); + * } + * + * int + * sample_insert(struct avl_node **tree, struct sample_data *node) + * { + * * Note: The call to sample_compare is compiled into the inner loop + * * of the macro. It is not evaluated locally! + * return AVL_INSERT(tree,&node->treenode + * , (sample_compare(AVLNode,node->num)) ); + * } + * + * int + * sample_remove(struct avl_node **tree, int num) + * { + * * Note: The call to sample_compare is compiled into the inner loop + * * of the macro. It is not evaluated locally! + * return AVL_REMOVE(tree, (sample_compare(AVLNode,num)) ); + * } + * + * struct sample_data * + * sample_find(struct avl_node *tree, int num) + * { + * struct avl_node *dummy; + * + * * Note: The call to sample_compare is compiled into the inner loop + * * of the macro. It is not evaluated locally! + * tree = AVL_FIND(tree, dummy, dummy, (sample_compare(AVLNode,num)) ); + * if (tree) { + * return avl_entry(tree, struct sample_data, treenode); + * } + * return NULL; + * } + */ + +#endif /* _LINUX_AVLTREE_H */ --- linux/include/linux/bitpointers.h.orig Tue Dec 14 00:24:17 1999 +++ linux/include/linux/bitpointers.h Mon Dec 13 23:39:13 1999 @@ -0,0 +1,49 @@ +#ifndef _LINUX_BITPOINTERS_H +#define _LINUX_BITPOINTERS_H + + +#if 1 + +/* + * Pointers that also store 2 programmable bits. + * + * The caller is responsible for ensuring that the address pointed to by + * the pointer is 4 byte aligned. The caller must also ensure that the + * value assigned to the bits is not greater than 3. + */ + +typedef struct { + void *p; +} ptr2bit_t; + +#define P2B_GETPTR(p2b) ((unsigned long)(p2b).p & ~3) +#define P2B_GETBITS(p2b) ((unsigned long)(p2b).p & 3) +#define P2B_SETPTR(p2b,val) do {(p2b).p = (void *)(((unsigned long)(p2b).p & 3) | (unsigned long) (val));} while (0) +#define P2B_SETBITS(p2b,val) do {(p2b).p = (void *)(((unsigned long)(p2b).p & ~3) | (val));} while (0) + +/* Pointers to ptr2bit_t */ +#define P2B_GETPTRLOC(p2b) (&((p2b).p)) +#define P2B_GETPTRPTR(p2b) P2B_GETPTR(*(p2b)) + +#else + +/* Compatibility defines */ + +typedef struct { + void *p; + unsigned char bits; +} ptr2bit_t; + +#define P2B_GETPTR(p2b) ((p2b).p) +#define P2B_GETBITS(p2b) ((p2b).bits) +#define P2B_SETPTR(p2b,val) do {(p2b).p = (val);} while (0) +#define P2B_SETBITS(p2b,val) do {(p2b).bits = (val);} while (0) + +/* Pointers to ptr2bit_t */ +#define P2B_GETPTRLOC(p2b) (&((p2b).p)) +#define P2B_GETPTRPTR(p2b) (*(p2b)) + +#endif + + +#endif /* _LINUX_BITPOINTERS_H */
--a8Wt8u1KmwUX3Y2C--
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/