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

From: Werner Almesberger
Date: Mon Nov 15 2004 - 16:13:34 EST

Rajesh Venkatasubramanian wrote:
> Again I don't like the following approach fully. I couldn't come
> out with a clean generalization something like rb_tree code.

Hmm, GET_INDEX/get_index grows and grows, and also generates a
hotspot for patch collisions ...

And what if we took the hit and moved the key into struct
prio_tree_node ? struct vm_area_struct.shared.vm_set already is
one word longer than vm_area_struct.shared.prio_tree_node, so
half of the key is free (in terms of storage - the key updates
when vm_pgoff, vm_end, or vm_start changes aren't free). The
other half could also be made free (in terms of storage and
processing) with a little tweaking, e.g. by adding

union {
unsigned long vm_pgoff;
struct vm_set {
unsigned long vm_pgoff;
} vm_set;
struct prio_tree_node prio_tree_node;

#define vm_pgoff shared.vm_pgoff

(Untested. This kind of #define is of course risky, so it may be
better to just rewrite all the accesses.)

Then, we could have

struct prio_tree_node {
unsigned long r_index, h_index;

For the elevators, the keys (the "footprint" of a set of overlapping
requests) are already stored as separate variables, so that could be
migrated very easily, at no additional cost.

- Werner

/ Werner Almesberger, Buenos Aires, Argentina werner@xxxxxxxxxxxxxxx /
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at