Re: [RFC][PATCH 1/3] radix priority search tree - objrmap complexity fix

[Rajesh Venkatasubramanian <vrajesh@umich.edu>]

This patch fixes a couple of mask overflow bugs in the prio_tree
search code. These bugs trigger in some very rare corner cases.
The patch also removes a couple of BUG_ONs from the fast paths.

Now the code is well-tested. I have tested all __vma_prio_tree_*
functions in the user-space with as many as 10 million vmas and
all prio_tree functions work fine.

This patch is against 2.6.5-aa2. It will apply on top of Hugh's
patches also.

If you like to test the prio_tree code further in the user-space,
the programs in the following link may help you.

http://www-personal.engin.umich.edu/~vrajesh/linux/prio_tree/user_space/



 mm/prio_tree.c |   46 ++++++++++++++++++++++++++++++----------------
 1 files changed, 30 insertions(+), 16 deletions(-)

diff -puN mm/prio_tree.c~080_prio_tree mm/prio_tree.c
--- mmlinux-2.6/mm/prio_tree.c~080_prio_tree	2004-04-04 22:25:29.000000000 -0400
+++ mmlinux-2.6-jaya/mm/prio_tree.c	2004-04-04 22:25:30.000000000 -0400
@@ -124,10 +124,8 @@ static inline struct prio_tree_node *pri
 		node->parent = old->parent;
 		if (old->parent->left == old)
 			old->parent->left = node;
-		else {
-			BUG_ON(old->parent->right != old);
+		else
 			old->parent->right = node;
-		}
 	}

 	if (!prio_tree_left_empty(old)) {
@@ -271,10 +269,8 @@ void prio_tree_remove(struct prio_tree_r

 	if (cur->parent->right == cur)
 		cur->parent->right = cur->parent;
-	else {
-		BUG_ON(cur->parent->left != cur);
+	else
 		cur->parent->left = cur->parent;
-	}

 	while (cur != node)
 		cur = prio_tree_replace(root, cur->parent, cur);
@@ -308,8 +304,16 @@ static inline struct prio_tree_node *__p
 				iter->size_level++;
 		}
 		else {
-			iter->size_level = 1;
-			iter->mask = 1UL << (root->index_bits - 1);
+			if (iter->size_level) {
+				BUG_ON(!prio_tree_left_empty(iter->cur));
+				BUG_ON(!prio_tree_right_empty(iter->cur));
+				iter->size_level++;
+				iter->mask = ULONG_MAX;
+			}
+			else {
+				iter->size_level = 1;
+				iter->mask = 1UL << (root->index_bits - 1);
+			}
 		}
 		return iter->cur;
 	}
@@ -347,8 +351,16 @@ static inline struct prio_tree_node *__p
 				iter->size_level++;
 		}
 		else {
-			iter->size_level = 1;
-			iter->mask = 1UL << (root->index_bits - 1);
+			if (iter->size_level) {
+				BUG_ON(!prio_tree_left_empty(iter->cur));
+				BUG_ON(!prio_tree_right_empty(iter->cur));
+				iter->size_level++;
+				iter->mask = ULONG_MAX;
+			}
+			else {
+				iter->size_level = 1;
+				iter->mask = 1UL << (root->index_bits - 1);
+			}
 		}
 		return iter->cur;
 	}
@@ -360,13 +372,15 @@ static inline struct prio_tree_node *__p
 	struct prio_tree_iter *iter)
 {
 	iter->cur = iter->cur->parent;
-	iter->mask <<= 1;
-	if (iter->size_level) {
-		if (iter->size_level == 1)
-			iter->mask = 1UL;
+	if (iter->mask == ULONG_MAX)
+		iter->mask = 1UL;
+	else if (iter->size_level == 1)
+		iter->mask = 1UL;
+	else
+		iter->mask <<= 1;
+	if (iter->size_level)
 		iter->size_level--;
-	}
-	else if (iter->value & iter->mask)
+	if (!iter->size_level && (iter->value & iter->mask))
 		iter->value ^= iter->mask;
 	return iter->cur;
 }

_

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>