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

[Werner Almesberger <werner@almesberger.net>]

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@almesberger.net /
/_http://www.almesberger.net/____________________________________________/