| Age | Commit message (Collapse) | Author |
|---|
|
Export prio_tree functions such that they can be used by other subsystems than
only VMAs. Also adds a mode to prio_tree to use it with keys explicitly
included in the prio_tree meta-data.
The plan is to also consider converting VMAs to use explicit keys, so that the
old "raw" mode can be removed.
Signed-off-by: Werner Almesberger <werner@almesberger.net>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
Allow prio_tree_next to be used as the only function for tree traversal,
similar to how vma_prio_tree_next works.
This patch isn't needed for the generalization, but since it affects the API,
it's better to include it first.
Signed-off-by: Werner Almesberger <werner@almesberger.net>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
Currently we have:
while ((vma = vma_prio_tree_next(vma, root, &iter,
begin, end)) != NULL)
do_something_with(vma);
Then iter,root,begin,end are all transfered unchanged to various functions.
This patch hides them in struct iter instead.
It slightly lessens source, code size, and stack usage. Patch compiles and
tested lightly.
Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
Signed-off-by: Rajesh Venkatasubramanian <vrajesh@umich.edu>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
From: Hugh Dickins <hugh@veritas.com>
Rajesh Venkatasubramanian's implementation of a radix priority search tree of
vmas, to handle object-based reverse mapping corner cases well.
Amongst the objections to object-based rmap were test cases by akpm and by
mingo, in which large numbers of vmas mapping disjoint or overlapping parts of
a file showed strikingly poor performance of the i_mmap lists. Perhaps those
tests are irrelevant in the real world? We cannot be too sure: the prio_tree
is well-suited to solving precisely that problem, so unless it turns out to
bring too much overhead, let's include it.
Why is this prio_tree.c placed in mm rather than lib? See GET_INDEX: this
implementation is geared throughout to use with vmas, though the first half of
the file appears more general than the second half.
Each node of the prio_tree is itself (contained within) a vma: might save
memory by allocating distinct nodes from which to hang vmas, but wouldn't save
much, and would complicate the usage with preallocations. Off each node of
the prio_tree itself hangs a list of like vmas, if any.
The connection from node to list is a little awkward, but probably the best
compromise: it would be more straightforward to list likes directly from the
tree node, but that would use more memory per vma, for the list_head and to
identify that head. Instead, node's shared.vm_set.head points to next vma
(whose shared.vm_set.head points back to node vma), and that next contains the
list_head from which the rest hang - reusing fields already used in the
prio_tree node itself.
Currently lacks prefetch: Rajesh hopes to add some soon.
|
|
From: Hugh Dickins <hugh@veritas.com>
Pave the way for prio_tree by switching over to its interfaces, but actually
still implement them with the same old lists as before.
Most of the vma_prio_tree interfaces are straightforward. The interesting one
is vma_prio_tree_next, used to search the tree for all vmas which overlap the
given range: unlike the list_for_each_entry it replaces, it does not find
every vma, just those that match.
But this does leave handling of nonlinear vmas in a very unsatisfactory state:
for now we have to search again over the maximum range to find all the
nonlinear vmas which might contain a page, which of course takes away the
point of the tree. Fixed in later patch of this batch.
There is no need to initialize vma linkage all over, just do it before
inserting the vma in list or tree. /proc/pid/statm had an odd test for its
shared count: simplified to an equivalent test on vm_file.
|
