Messages in this thread | | | Date | Mon, 15 Nov 2004 16:14:13 -0500 (EST) | From | Rajesh Venkatasubramanian <> | Subject | Re: [RFC] Generalize prio_tree (1/3) |
| |
On Mon, 15 Nov 2004, Werner Almesberger wrote:
> 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.)
I thought about this, but this will lead to a very intrusive patch. We have to change the meaning of vm_start and vm_end or increase the size of vm_area_struct.
> 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.
Why can't we have only 2 types of prio_tree. One VMA_PRIO_TREE and another GENERIC_PRIO_TREE.
struct generic_prio_tree_node { unsigned long r_index, h_index; struct prio_tree_node prio_tree_node; }
That way all new users of prio_tree code will use the generic_prio_tree_node if possible. Moreover, we can avoid an intrusive patch.
I am only worried about the micro-performance loss due to get_index in the hot-paths such as vma_prio_tree_insert.
Rajesh - 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/
| |