lkml.org 
[lkml]   [1998]   [Jan]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: 2.1.76, nfs client, and memory fragmentation


    On Fri, 2 Jan 1998 kwrohrer@enteract.com wrote:

    > And lo, Linus Torvalds saith unto me:
    > >
    > > Umm? And what do you do after a fork, when the same physical page is
    > > present in multiple page tables?
    >
    > Until I figure out what to do with such a page, I can't move it. However,
    > I can do what the existing VM routines already do: slate it for asynchronous
    > swapping (which will decrement the usage count), and go on to the next
    > likely-looking candidate. Of course, to do that, my reverse page table
    > swells bigger than the forward page table, so at this point I'll just
    > give up and try to grow a different free area...

    The reverse page table can actually be made to be the same size as the
    forward page table fairly easily. We can essentially make the pte entries
    contain a next pointer (you don't want to do it exactly that way, because
    you want the pte to match the hardware layout if possible, but
    conceptually you can think of it as just making the pte larger).

    And I generally don't worry all that much about the size of the page
    tables. However, doubling them still makes me nervous.

    Note that the normal VM routines can handle COW-shared pages fairly
    efficiently the way they work now: forgetting them one at a time until
    only the page cache one is left sounds like the chicken way out of a hard
    problem, but it actually acts as a simple aging agent at the same time as
    it allows us to not keep exact track of where all physical pages are
    mapped, so for the normal page-out routines this is a perfectly acceptable
    situation.

    It's only when you want a _specific_ physical page that the lack of
    reverse mapping is painful. That does happen with shared non-COW pages
    occasionally (paging them out would be complex), but UNIX semantics tends
    to make it fairly easy - the only shared non-COW pages that exist have a
    well-specified backing store that all processes can agree about, so there
    is no ambiguity about where on the disk a page should be. It does result
    in potentially unnecessary page-outs (when multiple processes have the
    same page dirty), but it's a pretty rare condition.

    (But thist is what makes anonymous shared mapping so hard, and why Linux
    doesn't support them other than trough the SysV shared memory shm
    interface - which _does_ keep a reverse mapping internally).

    So yes, reverse page tables would be useful, but it's fairly painful and
    the gain is usually not all that large except for this one case. And this
    one case could probably be solved other ways (I _still_ think that the
    slab allocator is wrong in being so aggressive about getting large areas,
    so it's not just a page-allocator problem, it's also a _usage_ problem).

    > > But in order to keep track of shared pages (whether they are truly shared
    > > or just COW-shared) you need to essentially have a shadow page table which
    > > contains the linked list of virtual mappings..
    >
    > You seem to do fine without one. :-P I don't see the existing code making
    > any effort to, e.g., kill all processes which were using a shared page when
    > it encountered an error during swapping. :-) (I take it there's a reason
    > to assume whatever failure ruined the original copy of the page? I'd
    > expect transient failures to be more common...)

    Right. That's my point. We _can_ generally do fine without any reverse
    mapping at all, because most of the time it makes no difference. But if we
    were to need a reverse mapping, then we need one that can handle page
    sharing.

    One approach is to have just a "hint-map", which might indeed be good
    enough. The hint-map would contain entries only for private un-shared
    pages - which is often a large fraction of the pages. HOWEVER, I suspect
    that the UNIX fork()/exec() semantics would make even this be impractical:
    on average a lot of pages are not shared, but most pages are shared at
    least for a short while every once in a while. And even if they become
    unshared quickly after being shared, they will have lost the information
    about what single mapping they had.

    (So you could instead try to keep a hint map that has a pointer for each
    physical page, but the pointer might point to just one of multiple users,
    and the code that wants to free the page would have to check whether it
    actually got the exclusive access. It might well be "good enough" for what
    we're interested in - we couldn't free an arbitrary page, but we would
    have a reasonable chance of freeing some pages we're interested in).

    > Unfortunately, it seems like I need a heck of a lot more junk than
    > just the page table entry to evict a page under Linux. Ignoring the
    > shared page issue for now, is frobbing the pte (to change the physical
    > address), plus (presumably) flushing the TLB by the time I'm done, safe?
    > Or do I need to go galumphing through the plethora of structs the
    > swap_out_I_really_mean_it_this_time() functions pass around?

    It's not all that bad, but you do need the vma associated with the pte -
    otherwise you wouldn't know where to swap it out to (it might have backing
    store, and the vma might actually tell you that you mustn't swap it out at
    all because the area is locked etc). But with the vma and the virtual
    address you should have all the info you need.

    So it should be entirely possible to add a (vma, offset) tuple into the
    "struct page". In fact, if you limit the scheme to only non-shared
    anonymous pages you wouldn't even need to grow the "struct page" at all:
    you could overlay the information with the current (inode, offset)
    information (or hash) that is needed for the page cache (but as this would
    be an anonymous page you know that it cannot be in the page cache).

    I'd certainly like a scheme that would need memory only proportional to
    the physical memory space - even if the scheme would be less than perfect
    in some regards. But some things that want the reverse mapping do want it
    expressly for the case of shared pages, so the question then becomes
    whether you want to make a more limited scheme that works well enough for
    the page allocator but not some other cases, or whether you really want to
    go the whole way..

    Linus


    \
     
     \ /
      Last update: 2005-03-22 13:41    [W:0.027 / U:61.504 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site