Re: [RFC] Generalize prio_tree (1/3)
From: Werner Almesberger (werner_at_almesberger.net)
Date: 11/15/04
- Previous message: Dean Nelson: "Re: [Patch] export sched_setscheduler() for kernel module use"
- In reply to: Rajesh Venkatasubramanian: "Re: [RFC] Generalize prio_tree (1/3)"
- Next in thread: Rajesh Venkatasubramanian: "Re: [RFC] Generalize prio_tree (1/3)"
- Reply: Rajesh Venkatasubramanian: "Re: [RFC] Generalize prio_tree (1/3)"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 15 Nov 2004 17:54:15 -0300 To: Rajesh Venkatasubramanian <vrajesh@umich.edu>
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/____________________________________________/ - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
- Previous message: Dean Nelson: "Re: [Patch] export sched_setscheduler() for kernel module use"
- In reply to: Rajesh Venkatasubramanian: "Re: [RFC] Generalize prio_tree (1/3)"
- Next in thread: Rajesh Venkatasubramanian: "Re: [RFC] Generalize prio_tree (1/3)"
- Reply: Rajesh Venkatasubramanian: "Re: [RFC] Generalize prio_tree (1/3)"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
