Re: [RFC] Generalize prio_tree (1/3)

From: Rajesh Venkatasubramanian
Date: Mon Nov 15 2004 - 13:15:40 EST




On Sun, 14 Nov 2004, Werner Almesberger wrote:

> perhaps you remember me posting a long time ago about generalizing
> prio_tree. Now I finally got to make that patch. In fact, there are
> three parts:
>
> - the prio_tree "core" in lib/
> - switching mm/prio_tree.c to use the "core"
> - some debugging extensions
>
[snip]
>
> The patch below puts an includeable version of prio_tree to lib/.
> This should be included similar to how inflate.c is used.

I don't like including prio_tree. I will only choose to go the
include way if and only if every other choice leads to significant
performance overhead.

Currently I prefer the following way, but I didn't implement it
because I don't have a strong reason to generalize prio_tree and
the generalization may lead to some preformance loss (which may be
insignificant loss in real world apps). We have to test to know
the performance loss.

Again I don't like the following approach fully. I couldn't come
out with a clean generalization something like rb_tree code. I don't
think such a clean generalization exists for prio_tree. Therefore,
if we have a strong reason to generalize the prio_tree, then we have to
choose one of the options we have. Untested prototype patch below.

prio_tree generalization...

---

linux-2.6.9-testuser/fs/inode.c | 2
linux-2.6.9-testuser/include/linux/prio_tree.h | 10 +++-
linux-2.6.9-testuser/mm/prio_tree.c | 56 ++++++++++++++-----------
3 files changed, 41 insertions(+), 27 deletions(-)

diff -puN include/linux/prio_tree.h~prio_tree_gen include/linux/prio_tree.h
--- linux-2.6.9/include/linux/prio_tree.h~prio_tree_gen 2004-11-15 12:30:34.513076512 -0500
+++ linux-2.6.9-testuser/include/linux/prio_tree.h 2004-11-15 13:04:55.772717416 -0500
@@ -9,7 +9,8 @@ struct prio_tree_node {

struct prio_tree_root {
struct prio_tree_node *prio_tree_node;
- unsigned int index_bits;
+ unsigned short index_bits;
+ unsigned short type;
};

struct prio_tree_iter {
@@ -31,10 +32,15 @@ static inline void prio_tree_iter_init(s
iter->h_index = h_index;
}

-#define INIT_PRIO_TREE_ROOT(ptr) \
+/* prio_tree types */
+#define VMA_PRIO_TREE 0
+#define ABISS_PRIO_TREE 1
+
+#define INIT_PRIO_TREE_ROOT(ptr, t) \
do { \
(ptr)->prio_tree_node = NULL; \
(ptr)->index_bits = 1; \
+ (ptr)->type = t; \
} while (0)

#define INIT_PRIO_TREE_NODE(ptr) \
diff -puN mm/prio_tree.c~prio_tree_gen mm/prio_tree.c
--- linux-2.6.9/mm/prio_tree.c~prio_tree_gen 2004-11-15 12:32:39.010150080 -0500
+++ linux-2.6.9-testuser/mm/prio_tree.c 2004-11-15 12:54:00.085397040 -0500
@@ -44,23 +44,10 @@
* The following macros are used for implementing prio_tree for i_mmap
*/

-#define RADIX_INDEX(vma) ((vma)->vm_pgoff)
-#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
+#define VMA_RADIX_INDEX(vma) ((vma)->vm_pgoff)
+#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
/* avoid overflow */
-#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
-
-#define GET_INDEX_VMA(vma, radix, heap) \
-do { \
- radix = RADIX_INDEX(vma); \
- heap = HEAP_INDEX(vma); \
-} while (0)
-
-#define GET_INDEX(node, radix, heap) \
-do { \
- struct vm_area_struct *__tmp = \
- prio_tree_entry(node, struct vm_area_struct, shared.prio_tree_node);\
- GET_INDEX_VMA(__tmp, radix, heap); \
-} while (0)
+#define VMA_HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))

static unsigned long index_bits_to_maxindex[BITS_PER_LONG];

@@ -83,6 +70,27 @@ static inline unsigned long prio_tree_ma

static void prio_tree_remove(struct prio_tree_root *, struct prio_tree_node *);

+static void get_index(struct prio_tree_root *root, struct prio_tree_node *node,
+ unsigned long *radix, unsigned long *heap)
+{
+ switch (root->type) {
+ case VMA_PRIO_TREE:
+ struct vm_area_struct *vma;
+ vma = prio_tree_entry(node, struct vm_area_struct,
+ shared.prio_tree_node);
+ *radix = VMA_RADIX_INDEX(vma);
+ *heap = VMA_HEAP_INDEX(vma);
+ break;
+ case ABISS_PRIO_TREE:
+ ...
+ break;
+ default:
+ BUG();
+ break;
+ }
+}
+
+
/*
* Extend a priority search tree so that it can store a node with heap_index
* max_heap_index. In the worst case, this algorithm takes O((log n)^2).
@@ -190,7 +198,7 @@ static struct prio_tree_node *prio_tree_
unsigned long r_index, h_index, index, mask;
int size_flag = 0;

- GET_INDEX(node, radix_index, heap_index);
+ get_index(root, node, &radix_index, &heap_index);

if (prio_tree_empty(root) ||
heap_index > prio_tree_maxindex(root->index_bits))
@@ -200,7 +208,7 @@ static struct prio_tree_node *prio_tree_
mask = 1UL << (root->index_bits - 1);

while (mask) {
- GET_INDEX(cur, r_index, h_index);
+ get_index(root, cur, &r_index, &h_index);

if (r_index == radix_index && h_index == heap_index)
return cur;
@@ -269,14 +277,14 @@ static void prio_tree_remove(struct prio

while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) {
if (!prio_tree_left_empty(cur))
- GET_INDEX(cur->left, r_index, h_index_left);
+ get_index(root, cur->left, &r_index, &h_index_left);
else {
cur = cur->right;
continue;
}

if (!prio_tree_right_empty(cur))
- GET_INDEX(cur->right, r_index, h_index_right);
+ get_index(root, cur->right, &r_index, &h_index_right);
else {
cur = cur->left;
continue;
@@ -291,7 +299,7 @@ static void prio_tree_remove(struct prio

if (prio_tree_root(cur)) {
BUG_ON(root->prio_tree_node != cur);
- INIT_PRIO_TREE_ROOT(root);
+ INIT_PRIO_TREE_ROOT(root, root->type);
return;
}

@@ -318,7 +326,7 @@ static struct prio_tree_node *prio_tree_
if (prio_tree_left_empty(iter->cur))
return NULL;

- GET_INDEX(iter->cur->left, *r_index, *h_index);
+ get_index(iter->root, iter->cur->left, r_index, h_index);

if (iter->r_index <= *h_index) {
iter->cur = iter->cur->left;
@@ -359,7 +367,7 @@ static struct prio_tree_node *prio_tree_
if (iter->h_index < value)
return NULL;

- GET_INDEX(iter->cur->right, *r_index, *h_index);
+ get_index(iter->root, iter->cur->right, r_index, h_index);

if (iter->r_index <= *h_index) {
iter->cur = iter->cur->right;
@@ -425,7 +433,7 @@ static struct prio_tree_node *prio_tree_
if (prio_tree_empty(root))
return NULL;

- GET_INDEX(root->prio_tree_node, r_index, h_index);
+ get_index(root, root->prio_tree_node, &r_index, &h_index);

if (iter->r_index > h_index)
return NULL;
diff -puN fs/inode.c~prio_tree_gen fs/inode.c
--- linux-2.6.9/fs/inode.c~prio_tree_gen 2004-11-15 12:50:22.393491240 -0500
+++ linux-2.6.9-testuser/fs/inode.c 2004-11-15 12:51:18.155014200 -0500
@@ -201,7 +201,7 @@ void inode_init_once(struct inode *inode
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, VMA_PRIO_TREE);
INIT_LIST_HEAD(&inode->i_data.i_mmap_nonlinear);
spin_lock_init(&inode->i_lock);
i_size_ordered_init(inode);
_
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/