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: 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

[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.

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

[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]

>> 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: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]

>> 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

[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

[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

[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

[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

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.