Re: subobj-rmap

Re: subobj-rmap

[Chuck Ebbert]

Davide Libenzi wrote:

1) |----------------------|
2)     |-----------|
3) |--------------------------|
4)         |-----------|

R) |---|---|-------|---|--|---|

    1   1   1       1   1  3
    3   2   2       3   3
        3   3       4
            4


 How's this for an alogorithm for finding which
chunk of 'R' you have hit with a given memory reference:

 o  Use a bitmap to represent the whole address range.
 o  Set the bits that correspond the the first page
    of each subregion.

 To search:

 o  Look up the bit for the page you are interested in.
 o  Scan backwards for a 1.
 o  Convert bit position to address, this is the
    base of the subregion.

 Since this is i386-only you can play neat assembler
tricks with this code to make it fast.

 (OS/2 did/does it that way.)

--
 Chuck
 I am not a number!

Re: objrmap and vmtruncate

[Andrew Morton]

Andrea Arcangeli <andrea@suse.de> wrote:
>
> the worst part IMHO is that it screwup the vma making the vma->vm_file
> totally wrong for the pages in the vma.

Not sure what you mean here.  All pages in the vma are backed by the file at
vm_file.  It is vm_pgoff which is meaningless.

As for your other concerns: yes, I hear you.  I suspect something will have
to give.  Ingo has a better feel for the problems which this code is solving
and hopefully he can comment.

Perhaps it is useful to itemise the prblems which we're trying to solve here:

- ZONE_NORMAL consumption by pte_chains

  Solved by objrmap and presumably page clustering.

- ZONE_NORMAL consumption by VMAs

  Solved by remap_file_pages.  Neither objrmap nor page clustering will
  help here.

- pte_chain setup and teardown CPU cost.

  objrmap does not seem to help.  Page clustering might, but is unlikely to
  be enabled on the machines which actually care about the overhead.

- get_unmapped_area() search complexity.

  Solved by remap_file_pages and by as-yet unimplemented algorithmic rework.

- pagefault frequency and TLB invalidation cost.

  Solved by MAP_POPULATE, could also be solved by MAP_PREFAULT (but it's
  not really a demonstrated problem).

Anything else?


So looking at the above, remap_file_pages() actually has pretty good
coverage.

Re: objrmap and vmtruncate

[Martin J. Bligh]

> Perhaps it is useful to itemise the prblems which we're trying to solve here:
> 
> - ZONE_NORMAL consumption by pte_chains
> 
>   Solved by objrmap and presumably page clustering.
> 
> - ZONE_NORMAL consumption by VMAs
> 
>   Solved by remap_file_pages.  Neither objrmap nor page clustering will
>   help here.

I'm not convinced that we can't do something with nonlinear mappings for
this ... we just need to keep a list of linear areas within the nonlinear
vmas, and use that to do the objrmap stuff with. Dave and I talked about
this yesterday ... we both had different terminology, but I think the
same underlying fundamental concept ... I was calling them "sub-vmas"
for each linear region within the nonlinear space. 

The fundamental problem I came to (and I think Dave had the same problem) 
is that I couldn't see what problem remap_file_pages was trying to solve,
so it was tricky to see if we'd cause the same thing or not. sub-vmas
could certainly be a lot smaller, but we weren't thinking of 128K of the
damned things, so ... the other thing is of course the setup and teardown
time ... but the could be a btree or something for the structure.

Of course, if we did this, it would get rid of the whole conversion
to and from object based stuff ;-) I think Dave had some other bright
idea on this too, but I don't recall what it was ;-(

> - pte_chain setup and teardown CPU cost.
> 
>   objrmap does not seem to help.  Page clustering might, but is unlikely to
>   be enabled on the machines which actually care about the overhead.

eh? Not sure what you mean by that. It helped massively ...
diffprofile from kernbench showed:

     -4666   -74.9% page_add_rmap
    -10666   -92.0% page_remove_rmap

I'd say that about an 85% reduction in cost is pretty damned fine ;-)
And that was about a 20% overall reduction in the system time for the
test too ... that was all for partial objrmap (file backed, not anon).

M.

Re: objrmap and vmtruncate

[Andrea Arcangeli]

On Fri, Apr 04, 2003 at 06:13:52PM -0800, Martin J. Bligh wrote:
> > Perhaps it is useful to itemise the prblems which we're trying to solve here:
> > 
> > - ZONE_NORMAL consumption by pte_chains
> > 
> >   Solved by objrmap and presumably page clustering.
> > 
> > - ZONE_NORMAL consumption by VMAs
> > 
> >   Solved by remap_file_pages.  Neither objrmap nor page clustering will
> >   help here.
> 
> I'm not convinced that we can't do something with nonlinear mappings for
> this ... we just need to keep a list of linear areas within the nonlinear
> vmas, and use that to do the objrmap stuff with. Dave and I talked about
> this yesterday ... we both had different terminology, but I think the
> same underlying fundamental concept ... I was calling them "sub-vmas"
> for each linear region within the nonlinear space. 

that's wasted memory IMHO, if you need nonlinear, you don't want to
waste further metadata, you only want to pin pages in the pagetables,
the 'window' over the pagecache (incidentally shm)

the vm shouldn't know about it.

> The fundamental problem I came to (and I think Dave had the same problem) 
> is that I couldn't see what problem remap_file_pages was trying to solve,

Oh that's clear, it's only the avoidance of the mmap calls that walks
the rbtree with many vmas allocated. Which is another reason for not
having any kind of metadata associated with the pages attached to the
nonlinear vma. Taking a linearity inside the non-linearity sounds
not worthwhile.

remap_file_pages isn't a regular API, it's a 32bit hack to mangle
pagetables and attach pages into it hard due the lack of address space
that avoids you to map the whole file at once.

Should pin stuff into ram and be enabled by a sysctl, and to be not used
on 64bit archs that can map all at once in a cleaner way that also
allows efficient swapping etc...

> so it was tricky to see if we'd cause the same thing or not. sub-vmas
> could certainly be a lot smaller, but we weren't thinking of 128K of the
> damned things, so ... the other thing is of course the setup and teardown
> time ... but the could be a btree or something for the structure.
> 
> Of course, if we did this, it would get rid of the whole conversion
> to and from object based stuff ;-) I think Dave had some other bright
> idea on this too, but I don't recall what it was ;-(
> 
> > - pte_chain setup and teardown CPU cost.
> > 
> >   objrmap does not seem to help.  Page clustering might, but is unlikely to
> >   be enabled on the machines which actually care about the overhead.
> 
> eh? Not sure what you mean by that. It helped massively ...
> diffprofile from kernbench showed:

Indeed. objrmap is the only way to avoid the big rmap waste. Infact I'm
not even convinced about the hybrid approch, rmap should be avoided even
for the anon pages. And the swap cpu doesn't matter, as far as we can
reach pagteables in linear time that's fine, doesn't matter how many
fixed cycles it takes. Only the complexity factor matters, and objrmap
takes care of it just fine.

> 
>      -4666   -74.9% page_add_rmap
>     -10666   -92.0% page_remove_rmap
> 
> I'd say that about an 85% reduction in cost is pretty damned fine ;-)
> And that was about a 20% overall reduction in the system time for the
> test too ... that was all for partial objrmap (file backed, not anon).
> 
> M.


Andrea

Re: objrmap and vmtruncate

[Andrew Morton]

Andrea Arcangeli <andrea@suse.de> wrote:
>
> Indeed. objrmap is the only way to avoid the big rmap waste. Infact I'm
> not even convinced about the hybrid approch, rmap should be avoided even
> for the anon pages. And the swap cpu doesn't matter, as far as we can
> reach pagteables in linear time that's fine, doesn't matter how many
> fixed cycles it takes. Only the complexity factor matters, and objrmap
> takes care of it just fine.

Well not really.

Consider the case where 100 processes each own 100 vma's against the same
file.

To unmap a page with objrmap we need to search those 10,000 vma's (10000
cachelines).  With full rmap we need to search only 100 pte_chain slots (3 to
33 cachelines).  That's an enormous difference.  It happens for *each* page.

And, worse, we have the same cost when searching for referenced bits in the
pagetables.  Nobody has written an "exploit" for this yet, but it's there.

Possibly we should defer the assembly of the pte chain until a page hits the
tail of the LRU.  That's an awkward time to be allocating memory though.  We
could perhaps fall back to the vma walk if pte_chain allocation starts to
endanger the page reserves.

Re: objrmap and vmtruncate

[Andrew Morton]

Andrew Morton <akpm@digeo.com> wrote:
>
> Nobody has written an "exploit" for this yet, but it's there.

Here we go.  The test app is called `rmap-test'.  It is in ext3 CVS.  See

	http://www.zip.com.au/~akpm/linux/ext3/

It sets up N MAP_SHARED VMA's and N tasks touching them in various access
patterns.

vmm:/usr/src/ext3/tools> ./rmap-test 
Usage: ./rmap-test [-hlrvV] [-iN] [-nN] [-sN] [-tN] filename
     -h:          Pattern: half of memory is busy
     -l:          Pattern: linear
     -r:          Pattern: random
     -iN:         Number of iterations
     -nN:         Number of VMAs
     -sN:         VMA size (pages)
     -tN:         Run N tasks
     -VN:         Number of VMAs to process
     -v:          Verbose

The kernels which were compared were 2.5.66-mm4, 2.5.66-mm4+all objrmap
patches and 2.4.21-pre5aa2.  The machine has 256MB of memory, 2.7G P4,
uniprocessor, IDE disk.




The first test has 100 tasks, each of which has 100 vma's.  The 100 processes
modify their 100 vma's in a linear walk.  Total working set is 240MB
(slightly more than is available).

	./rmap-test -l -i 10 -n 100 -s 600 -t 100 foo

2.5.66-mm4:
	15.76s user 86.91s system 33% cpu 5:05.07 total
2.5.66-mm4+objrmap:
	23.07s user 1143.26s system 87% cpu 22:09.81 total
2.4.21-pre5aa2:
	14.91s user 75.30s system 24% cpu 6:15.84 total





In the second test we again have 100 tasks, each with 100 vma's but the
access pattern is random:

	./rmap-test -vv -V 2 -r -i 1 -n 100 -s 600 -t 100 foo

2.5.66-mm4:
	0.12s user 6.05s system 2% cpu 3:59.68 total
2.5.66-mm4+objrmap:
	0.12s user 2.10s system 0% cpu 4:01.15 total
2.4.21-pre5aa2:
	0.07s user 2.03s system 0% cpu 4:12.69 total


The -aa VM failed in this test.

	__alloc_pages: 0-order allocation failed (gfp=0x1d2/0)
	VM: killing process rmap-test

I'd have to call this a bug - the machine was full of reclaimable memory.

I also saw the 2.4 kernel do 705,000 context switches in a single second,
which was odd.  It only happened once.





In the third test a single task owns 10000 VMA's and walks across them in a
linear pattern:

	./rmap-test -v -l -i 10 -n 10000 -s 7 -t 1 foo

2.5.66-mm4:
	0.25s user 3.75s system 1% cpu 4:38.44 total
2.5.66-mm4+objrmap:
	0.28s user 146.45s system 16% cpu 15:14.59 total
2.4.21-pre5aa2:
	0.32s user 4.83s system 0% cpu 18:25.90 total




These are not ridiculous workloads, especially the third one.  And 10k VMA's
is by no means inconceivable.

The objrmap code will be show-stoppingly expensive at 100k vmas per file.

And as expected, the full rmap implementation gives the most stable,
predictable and highest performance result under heavy load.  That's why
we're using it.

When it comes to the VM, there is a lot of value in sturdiness under unusual
and heavy loads.

Tomorrow I'll change the test app to do nonlinear mappings too.

Re: objrmap and vmtruncate

[Martin J. Bligh]

> The first test has 100 tasks, each of which has 100 vma's.  The 100 processes
> modify their 100 vma's in a linear walk.  Total working set is 240MB
> (slightly more than is available).
> 
> 	./rmap-test -l -i 10 -n 100 -s 600 -t 100 foo
> 
> 2.5.66-mm4:
> 	15.76s user 86.91s system 33% cpu 5:05.07 total
> 2.5.66-mm4+objrmap:
> 	23.07s user 1143.26s system 87% cpu 22:09.81 total
> 2.4.21-pre5aa2:
> 	14.91s user 75.30s system 24% cpu 6:15.84 total

Isn't the intent to use sys_remap_file_pages for these sort of workloads
anyway? In which case partial objrmap = rmap for these tests, so we're
still OK?

M.

Re: objrmap and vmtruncate

[Alan Cox]

On Sul, 2003-04-06 at 03:23, Martin J. Bligh wrote:
> > 	14.91s user 75.30s system 24% cpu 6:15.84 total
> 
> Isn't the intent to use sys_remap_file_pages for these sort of workloads
> anyway? In which case partial objrmap = rmap for these tests, so we're
> still OK?

What matters is the worst case not the best case. Users will do non
optimal things on a regular basis. 

Re: objrmap and vmtruncate

[Martin J. Bligh]

>> > 	14.91s user 75.30s system 24% cpu 6:15.84 total
>> 
>> Isn't the intent to use sys_remap_file_pages for these sort of workloads
>> anyway? In which case partial objrmap = rmap for these tests, so we're
>> still OK?
> 
> What matters is the worst case not the best case. Users will do non
> optimal things on a regular basis. 

Humpf. Well I have a fairly simple plan to fix it now. I'll either publish
some code or the plan later today, once I've thought about it a bit more.

M.

subobj-rmap

[Martin J. Bligh]

> Humpf. Well I have a fairly simple plan to fix it now. I'll either publish
> some code or the plan later today, once I've thought about it a bit more.

I'm not sure we need a full 2-d tree to solve this, because the 2 dimensions
aren't independant. What we have is a list of virtual ranges of the 
address_space, which might (but probably don't) overlap. If they never 
overlapped, this would be easy, we'd just keep a sorted structure (list or
tree) of regions, and find the region we lay in. In fact, Dave already did
that (sort by start addr) ... but we have to walk the rest of the chains 
as well to find other regions.

Supposing we keep a list of areas (hung from the address_space) that 
describes independant linear ranges of memory that have the same set
of vma's mapping them (call those subobjects). Each subobject has a
chain of vma's from it that are mapping that subobject.


address_space ---> subobject ---> subobject ---> subobject ---> subobject
                       |              |              |              |
                       v              v              v              v
                      vma            vma            vma            vma
                       |                             |              |
                       v                             v              v
                      vma                           vma            vma
                       |                             |        
                       v                             v        
                      vma                           vma       

Now we can just find the first element in that sorted list that maps
the address we're looking for, and it has a chain of vma's that we
need to worry about. This should solve the 100x100 case. To solve the 
1x10000 case efficiently, we should be able to just turn the subobject 
sorted list into an rbtree.

When we map a new VMA, we need to look for overlaps with existing 
subobjects. I suspect (with no real proof, save intuition) that most
of the time we'll either map a new space (create a new subobject),
or an existing space completely (just tack yourself onto the vma chain
from the subobject). If we do get a partial overlap, we'll split the
subobject in twain, and add ourselves to the overlapping part. Note that
This now starts to look very like the process's tree of vma's, so there's 
lots of potential for code-reuse. If the overlaps don't happen a lot,
(and I suspect they won't) it should be dirt cheap to do.

This is a bit more expensive on the maintainance side than objrmap, but
cheaper than pte_chains, since it's per-vma, not per-page. It should be
much cheaper than objrmap in the corner cases we've been discussing though.

Thoughts / flames?

Part 2
------

Moreover, this can be used for sys_remap_file_pages (and indeed
my though process is partly based on some discussions with Dave last week
about how to solve that). However, if people think this is too heavy,
we can still use pte-chains for this, so don't discard the above if you
have the following bit. We just keep a subobject for each linear region 
within the non-linear VMA - it might need a little more info in the 
subobject to work. Yes, it's more expense at remap time, but we don't
have to do the per-page stuff (and it's lighter than vmas). I suspect 
that's a good tradeoff (unless some crazy person is worried about mapping 
lots of windows and never using them). However, it would need to be 
benchmarked, and it's independant of the above.

Re: subobj-rmap

[Rik van Riel]

On Sun, 6 Apr 2003, Martin J. Bligh wrote:

> Supposing we keep a list of areas (hung from the address_space) that 
> describes independant linear ranges of memory that have the same set
> of vma's mapping them (call those subobjects). Each subobject has a
> chain of vma's from it that are mapping that subobject.
> 
> address_space ---> subobject ---> subobject ---> subobject ---> subobject
>                        |              |              |              |
>                        v              v              v              v
>                       vma            vma            vma            vma
>                        |                             |              |
>                        v                             v              v
>                       vma                           vma            vma
>                        |                             |        
>                        v                             v        
>                       vma                           vma       

OK, lets say we have a file of 1000 pages, or
offsets 0 to 999, with the following mappings:

VMA A:   0-999
VMA B:   0-200
VMA C: 150-400
VMA D: 300-500
VMA E: 300-500
VMA F:   0-999

How would you describe these with independant
regions ?

For VMAs D & E and A & F it's a no-brainer,
but for Oracle shared memory you shouldn't
assume that you have any similar mappings.

I don't see how the data structure you describe
would allow us to efficiently select the subset
of VMAs for which:

1) the start address is smaller than the address we want
and
2) the end address is larger than the address we want

Then again, that might just be my lack of imagination.

cheers,

Rik

Re: subobj-rmap

[Davide Libenzi]

On Sun, 6 Apr 2003, Rik van Riel wrote:

> On Sun, 6 Apr 2003, Martin J. Bligh wrote:
>
> > Supposing we keep a list of areas (hung from the address_space) that
> > describes independant linear ranges of memory that have the same set
> > of vma's mapping them (call those subobjects). Each subobject has a
> > chain of vma's from it that are mapping that subobject.
> >
> > address_space ---> subobject ---> subobject ---> subobject ---> subobject
> >                        |              |              |              |
> >                        v              v              v              v
> >                       vma            vma            vma            vma
> >                        |                             |              |
> >                        v                             v              v
> >                       vma                           vma            vma
> >                        |                             |
> >                        v                             v
> >                       vma                           vma
>
> OK, lets say we have a file of 1000 pages, or
> offsets 0 to 999, with the following mappings:
>
> VMA A:   0-999
> VMA B:   0-200
> VMA C: 150-400
> VMA D: 300-500
> VMA E: 300-500
> VMA F:   0-999
>
> How would you describe these with independant
> regions ?

You should decompose each VMA in a set on independent regions. Immagine to
pile up each VMA with boundaries that cuts each other VMA address space :

1) |----------------------|
2)     |-----------|
3) |--------------------------|
4)         |-----------|

R) |---|---|-------|---|--|---|

    1   1   1       1   1  3
    3   2   2       3   3
        3   3       4
            4



- Davide

Re: subobj-rmap

[Jamie Lokier]

Rik van Riel wrote:
> I don't see how the data structure you describe
> would allow us to efficiently select the subset
> of VMAs for which:
> 
> 1) the start address is smaller than the address we want
> and
> 2) the end address is larger than the address we want

Think about the data structures some text editors use to describe
special regions of the text.  A common operation is to search for all
the special regions covering a particular cursor position.

Several data structures are available.  I'm not aware of any that have
perfect behaviour in all corner cases.

It might be worth noting that these data structures are good at
determining the set of regions covering position X+1 having recently
calculated the set for position X.  Perhaps that has relevance for
speeding up page scanning?

-- Jamie

Re: subobj-rmap

[William Lee Irwin III]

Rik van Riel wrote:
>> I don't see how the data structure you describe
>> would allow us to efficiently select the subset
>> of VMAs for which:
>> 1) the start address is smaller than the address we want
>> and
>> 2) the end address is larger than the address we want

On Sun, Apr 06, 2003 at 10:55:30PM +0100, Jamie Lokier wrote:
> Think about the data structures some text editors use to describe
> special regions of the text.  A common operation is to search for all
> the special regions covering a particular cursor position.
> Several data structures are available.  I'm not aware of any that have
> perfect behaviour in all corner cases.
> It might be worth noting that these data structures are good at
> determining the set of regions covering position X+1 having recently
> calculated the set for position X.  Perhaps that has relevance for
> speeding up page scanning?

Multidimensional search trees are routine and decades old last I
checked; why do none of them suffice and why would they be good at
sequential queries?


-- wli

Re: subobj-rmap

[Martin J. Bligh]

>> Supposing we keep a list of areas (hung from the address_space) that 
>> describes independant linear ranges of memory that have the same set
>> of vma's mapping them (call those subobjects). Each subobject has a
>> chain of vma's from it that are mapping that subobject.
>> 
>> address_space ---> subobject ---> subobject ---> subobject ---> subobject
>>                        |              |              |              | 
>>                        v              v              v              v
>>                       vma            vma            vma            vma
>>                        |                             |              | 
>>                        v                             v              v
>>                       vma                           vma            vma
>>                        |                             |        
>>                        v                             v        
>>                       vma                           vma       
> 
> OK, lets say we have a file of 1000 pages, or
> offsets 0 to 999, with the following mappings:
> 
> VMA A:   0-999
> VMA B:   0-200
> VMA C: 150-400
> VMA D: 300-500
> VMA E: 300-500
> VMA F:   0-999
> 
> How would you describe these with independant regions ?

Good question to illustrate with.
Extra spacing added just for ease of reading:

0-150 -> 150-200 -> 200-300 -> 300-400 -> 400-500 -> 500-999
 A          A          A          A          A          A
 B          B
            C          C          C 
                                  D          D          
                                  E          E          
 F          F          F          F          F          F

> For VMAs D & E and A & F it's a no-brainer,
> but for Oracle shared memory you shouldn't
> assume that you have any similar mappings

We can always leave the sys_remap_file_pages stuff using pte_chains,
and should certainly do that at first. But doing it for normal stuff
should be less controversial, I think.

M.

Re: subobj-rmap

[Martin J. Bligh]

>> OK, lets say we have a file of 1000 pages, or
>> offsets 0 to 999, with the following mappings:
>> 
>> VMA A:   0-999
>> VMA B:   0-200
>> VMA C: 150-400
>> VMA D: 300-500
>> VMA E: 300-500
>> VMA F:   0-999
>> 
>> How would you describe these with independant regions ?
> 
> Good question to illustrate with.
> Extra spacing added just for ease of reading:
> 
> 0-150 -> 150-200 -> 200-300 -> 300-400 -> 400-500 -> 500-999
>  A          A          A          A          A          A
>  B          B
>             C          C          C 
>                                   D          D          
>                                   E          E          
>  F          F          F          F          F          F

Bah, offsets are slightly wrong, but the point is obviously the same

0-150 -> 151-200 -> 201-300 -> 301-400 -> 401-500 -> 501-999
 A          A          A          A          A          A
 B          B
            C          C          C 
                                  D          D          
                                  E          E          
 F          F          F          F          F          F

Re: subobj-rmap

[Andrea Arcangeli]

On Sun, Apr 06, 2003 at 03:03:03PM -0700, Martin J. Bligh wrote:
> We can always leave the sys_remap_file_pages stuff using pte_chains,

not sure why you want still to have the vm to know about the
mmap(VM_NONLINEAR) hack at all.

that's a vm bypass. I can bet the people who wants to use it for running
faster on the the 32bit archs will definitely prefer zero overhead and
full hardware speed with only the pagetable and tlb flushing trash, and
zero additional kernel internal overhead. that's just a vm bypass that
could otherwise sit in kernel module, not a real kernel API.

Andrea

Re: subobj-rmap

[Martin J. Bligh]

>> We can always leave the sys_remap_file_pages stuff using pte_chains,
> 
> not sure why you want still to have the vm to know about the
> mmap(VM_NONLINEAR) hack at all.
> 
> that's a vm bypass. I can bet the people who wants to use it for running
> faster on the the 32bit archs will definitely prefer zero overhead and
> full hardware speed with only the pagetable and tlb flushing trash, and
> zero additional kernel internal overhead. that's just a vm bypass that
> could otherwise sit in kernel module, not a real kernel API.

Well, you don't get zero overhead whatever you do. You either pay the
cost at remap time of manipulating sub-objects, or the cost at page-touch
time of the pte_chains stuff. I suspect sub-objects are cheaper if we
read /write the 32K chunks, not if people mostly just touch one page
per remap though.

What do you think about using this for the linear stuff though?

M.

Re: subobj-rmap

[Andrea Arcangeli]

On Sun, Apr 06, 2003 at 03:25:08PM -0700, Martin J. Bligh wrote:
> >> We can always leave the sys_remap_file_pages stuff using pte_chains,
> > 
> > not sure why you want still to have the vm to know about the
> > mmap(VM_NONLINEAR) hack at all.
> > 
> > that's a vm bypass. I can bet the people who wants to use it for running
> > faster on the the 32bit archs will definitely prefer zero overhead and
> > full hardware speed with only the pagetable and tlb flushing trash, and
> > zero additional kernel internal overhead. that's just a vm bypass that
> > could otherwise sit in kernel module, not a real kernel API.
> 
> Well, you don't get zero overhead whatever you do. You either pay the
> cost at remap time of manipulating sub-objects, or the cost at page-touch
> time of the pte_chains stuff. I suspect sub-objects are cheaper if we
> read /write the 32K chunks, not if people mostly just touch one page
> per remap though.
> 
> What do you think about using this for the linear stuff though?

I think at this only for the linear stuff. it would solve Andrew's
exploit against objrmap, for each page we would walk only the vmas
matching the pagetables mapping to the page. However those sub-objects
have a cost, the cost will be 8bytes per fragment. the slowest part
should be the split of the subobject when a new mapping happens and the
possible flood of list_add/list_del. I'm unsure it worth.

However it would be nice to se how the current 2.4 pte walking clock
algorithm does compared to objrmap and rmap when ext2 is used because
ext3 generated an I/O bound behaviour at least for my tree, that made
any vm-side comparison invalid.

Andrea

Re: subobj-rmap

[Jamie Lokier]

Martin J. Bligh wrote:
> 0-150 -> 150-200 -> 200-300 -> 300-400 -> 400-500 -> 500-999
>  A          A          A          A          A          A
>  B          B
>             C          C          C 
>                                   D          D          
>                                   E          E          
>  F          F          F          F          F          F

I thought of that but decided it is too simple :)

A downside with it is that from time to time you need to split or
merge subobjects, and that means splitting or merging the list nodes
linking "rows" in the table above - potentially quite a lot of memory
allocation and traversal for a single mmap().

> > For VMAs D & E and A & F it's a no-brainer,
> > but for Oracle shared memory you shouldn't
> > assume that you have any similar mappings
> 
> We can always leave the sys_remap_file_pages stuff using pte_chains,
> and should certainly do that at first. But doing it for normal stuff
> should be less controversial, I think.

If you implement the 2d data structure that you illustrated, you have
a list node for each point in the table.

By the time your subobject regions are 1 page wide, you have a data
structure that is order-equivalent to pte rmap chains, although the
exact number of words is likely to be higher.

To me this suggests that the 2d data structure could be designed
carefully, so that in the extreme case it gracefully _becomes_ rmap
chains.  For memory efficiency you'd need to pack together multiple
list nodes into a single cache line - the same tricks used to minimise
rmap memory consumption.

I'm not convinced this is the best data structure, but it does seem to
suggest the possibility of a hybrid which gives the best of both
objrmap and rmap data structures.

-- Jamie

Re: subobj-rmap

[Martin J. Bligh]

>> 0-150 -> 150-200 -> 200-300 -> 300-400 -> 400-500 -> 500-999
>>  A          A          A          A          A          A
>>  B          B
>>             C          C          C 
>>                                   D          D          
>>                                   E          E          
>>  F          F          F          F          F          F
> 
> I thought of that but decided it is too simple :)
> 
> A downside with it is that from time to time you need to split or
> merge subobjects, and that means splitting or merging the list nodes
> linking "rows" in the table above - potentially quite a lot of memory
> allocation and traversal for a single mmap().

The amount of work to be done is still fairly small ... and we already
do (as far as I can see) *exactly* this already for the existing
rb tree. Yes, mmap has a little bit more overhead, but you lose all
the per-page stuff, which seems much more efficient to me.
 
>> We can always leave the sys_remap_file_pages stuff using pte_chains,
>> and should certainly do that at first. But doing it for normal stuff
>> should be less controversial, I think.
> 
> If you implement the 2d data structure that you illustrated, you have
> a list node for each point in the table.
> 
> By the time your subobject regions are 1 page wide, you have a data
> structure that is order-equivalent to pte rmap chains, although the
> exact number of words is likely to be higher.

Well, yes. Except I hope nobody would want to do that on a per-page
basis. If you want that level of granularity, we should just do this 
for linear objects, and fall back to pte_chains for nonlinear.

Life would be a whole lot simpler if people were willing to specify
non-linear VMAs at create time - I don't see that as a big burden,
personally. That'd get rid of all the conversion stuff.

M.