Re: objrmap and vmtruncate

[Martin J. Bligh]

> Well, AFAICT the question wrt. sys_remap_file_pages() is not speed, but
> space. Speeding up mmap() is of course worthy of merging given the
> usual mergeability criteria.
> 
> On this point I must make a concession: k-d trees as formulated by
> Bentley et al have space consumption issues that may well render them
> inappropriate for kernel usage. I still believe it's worth an empirical
> investigation once descriptions of on-line algorithms for their
> maintenance are recovered, as well as other 2D+ spatial algorithms, esp.
> those with better space behavior.
> 
> Specifically, k-d trees require internal nodes to partition spaces that
> are not related to leaf nodes (i.e. data points), and not all
> rebalancing policies are guaranteed to recover space.

We can still do the simple sorted list of lists thing (I have preliminary
non-functional code). But I don't see that it's really worth the overhead
in the common case to fix a corner case that has already been fixed in a
different way.

/*
 * s = address_space, r = address_range, v = vma
 *
 * s - r - r - r - r - r
 *     |   |   |   |   |
 *     v   v   v   v   v
 *     |   |           |
 *     v   v           v
 *         |
 *         v
 */

struct address_range {
       unsigned long           start;
       unsigned long           end;
       struct list_head        ranges;
       struct list_head        vmas;
};

where the list of address_ranges is sorted by start address. This is
intended to make use of the real-world case that many things (like shared
libs) map the same exact address ranges over and over again (ie something
like 3 ranges, but hundreds or thousands of mappings).

M.