Fixing private mappings
Please excuse me for thinking out loud but private mappings seems to be a hard problem that has not been correctly implemented in the linux kernel.
Definition of Private Mappings:
A private mapping is a copy-on-write mapping of a file.
That is if the file is written to after the mapping is established, the contents of the mapping will always remain what the contents of the file was at the time of the private mapping.
Further if another private mapping is established after one private mapping has been established it should have the file contents of the file at the time the mapping is established. Not at the time any previous private mapping was established.
A few ideas occur to me for specific problems, but the whole problem is a challenge.
What I do know is that we need some kind of write barrier that we check to see if we have made a copy of a page for any private mappings that may exist before we write to it.
How should we find those private mappings?
Wait. That would be follow inode->i_mmap whenver we read in a page. And then have code in generic_file_write, and update_vm_cache, to make sure the copies are made at the appropriate times.
How should we maximize sharing of private mappings?
The simplest solution would be to continue with the current solution, and just restrict mappings 512 byte boundaries.
A slightly more generic solution would be to introduce a new ``inode'' that new it was a copy of the old inode but at a different offset. If these new ``inodes'' would then have a linked list of their own, that could be followed for update purposes.
--
Extra inodes for files could also be extended to allow an offset at say 4TB or so into a file so that we can handle any sized file. Though obviously you can't cache it all at once, but you could cache any piece ;)
There is a possibility there for per-inode metadata too but I'm not certain about that one.
I think since my initial goal was large file support with the common case on intel being restricted to 32bit integers, I'll play with the extra inodes approach.
It will probably be smart to restrict ourselves to still only allowing mappings on fs block boundaries. There are some efficiency gained there (on reading pages that are totally not in memory in) but otherwise we should be fine.
Eric
Quoted 9 lines · Eric W. Biederman
A slightly more generic solution would be to introduce a new ``inode'' that new it was a copy of the old inode but at a different offset. If these new ``inodes'' would then have a linked list of their own, that could be followed for update purposes.
Extra inodes for files could also be extended to allow an offset at say 4TB or so into a file so that we can handle any sized file. Though obviously you can't cache it all at once, but you could cache any piece ;)
This is a nice idea indeed. Maybe we could even use the 'extra inodes' idea to implement arbitrarily large files on _any_ architecture...
When the on-disk maximum size is reached, just grab a slave inode and start on part two.
The same for in-memory inodes, but there the maximum size may be different.
Rik.
+-------------------------------------------+--------------------------+ | Linux: - LinuxHQ MM-patches page | Scouting webmaster | | - kswapd ask-him & complain-to guy | Vries cubscout leader | | http://www.phys.uu.nl/~riel/ | <[email protected]> | +-------------------------------------------+--------------------------+
Quoted 10 lines · Eric W. Biederman
Please excuse me for thinking out loud but private mappings seems to be a hard problem that has not been correctly implemented in the linux kernel.
Definition of Private Mappings:
A private mapping is a copy-on-write mapping of a file.That is if the file is written to after the mapping is established, the contents of the mapping will always remain what the contents of the file was at the time of the private mapping.
No, this is not the case. Examine the behaviour of other unicies out there that implement mmap. The following is quoted from the man page for mmap on Solaris:
MAP_SHARED and MAP_PRIVATE describe the disposition of write references to the memory object. If MAP_SHARED is speci-
fied, write references will change the memory object. If
MAP_PRIVATE is specified, the initial write reference will create a private copy of the memory object page and redirect the mapping to the copy. Either MAP_SHARED or MAP_PRIVATE
must be specified, but not both. The mapping type is
retained across a fork(2).
Note: 'the initial write reference will create a private copy' -- not the act of reading or mapping.
Quoted 4 lines
Further if another private mapping is established after one private mapping has been established it should have the file contents of the file at the time the mapping is established. Not at the time any previous private mapping was established.
Linux does behave this way currently.
...
Quoted 4 lines
A slightly more generic solution would be to introduce a new ``inode'' that new it was a copy of the old inode but at a different offset. If these new ``inodes'' would then have a linked list of their own, that could be followed for update purposes.
...
This would be the appropriate thing to do if you'd like see such exotic behaviour ;-)
-ben
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"BL" == Benjamin C R LaHaise <[email protected]> writes:
Quoted 10 lines · Eric W. Biederman
Quoted 10 lines
Please excuse me for thinking out loud but private mappings seems to be a hard problem that has not been correctly implemented in the linux kernel.
Definition of Private Mappings:
A private mapping is a copy-on-write mapping of a file.That is if the file is written to after the mapping is established, the contents of the mapping will always remain what the contents of the file was at the time of the private mapping.
BL> No, this is not the case. Examine the behaviour of other unicies out BL> there that implement mmap. The following is quoted from the man page for BL> mmap on Solaris:
BL> MAP_SHARED and MAP_PRIVATE describe the disposition of write BL> references to the memory object. If MAP_SHARED is speci- BL> fied, write references will change the memory object. If BL> MAP_PRIVATE is specified, the initial write reference will BL> create a private copy of the memory object page and redirect BL> the mapping to the copy. Either MAP_SHARED or MAP_PRIVATE BL> must be specified, but not both. The mapping type is BL> retained across a fork(2).
BL> Note: 'the initial write reference will create a private copy' -- not BL> the act of reading or mapping.
Right. That is probably the only reasonable way to implement it.
I stated it as I did so what happens if another process writes to the file is clear. Another process writing to the file will be the `initial write reference'.
So logically MAP_PRIVATE gives you a snapshot of the contents of a
file. Not that it actually takes that snapshot...
Possibly I'm failing to see the difference in the definitions?
Was it the always remains the same bit? I was thinking of what the contents of the mapping would be if you don't write to it.
Quoted 4 lines
Quoted 4 lines
Further if another private mapping is established after one private mapping has been established it should have the file contents of the file at the time the mapping is established. Not at the time any previous private mapping was established.
BL> Linux does behave this way currently.
Only most of the time.
With private mappings at 1k alignment. I have written a program on 2.0.32 and verified this. I don't believe the code has significantly changed since then.
The problem is update_vm_cache only looks currently for the primary inode page. The one at (offset%PAGE_SIZE)==0. So the other page at offset%PAGE_SIZE==1k is not updated.
BL> This would be the appropriate thing to do if you'd like see such exotic BL> behaviour ;-)
I guess everyone seems to like this :)
Eric
Hi,
Quoted 6 lines · On 23 Apr 1998 17:03:02 -0500, [email protected] (Eric W. Biederman) said:
Quoted 6 lines
Quoted 6 lines
Definition of Private Mappings:
A private mapping is a copy-on-write mapping of a file.That is if the file is written to after the mapping is established, the contents of the mapping will always remain what the contents of the file was at the time of the private mapping.
BL> Note: 'the initial write reference will create a private copy' -- not BL> the act of reading or mapping.
Quoted 1 line
Right. That is probably the only reasonable way to implement it.
Indeed.
Quoted 3 lines
I stated it as I did so what happens if another process writes to the file is clear. Another process writing to the file will be the `initial write reference'.
No --- in the context of a MAP_PRIVATE mapping, only in-memory writes to the privately mapped virtual address space count as write references.
Quoted 2 lines
So logically
MAP_PRIVATEgives you a snapshot of the contents of a
file. Not that it actually takes that snapshot...
No, it shouldn't --- it maps the file into the process address space, and all updates to the file are reflected in the process's virtual memory copy. Only if the process tries to write to the file is the COW activated.
Quoted 1 line
Possibly I'm failing to see the difference in the definitions?
Yep. MAP_PRIVATE mappings preserve the correspondance over writes to the file by any mechanism other than modifying the mapping itself.
Note that the semantics are relaxed a bit if we have non-page-aligned private maps, in that the correspondance between the mapped image and the file contents is no longer always preserved if the file is updated.
Quoted 3 lines
The problem is
update_vm_cacheonly looks currently for the primary inode page. The one at (offset%PAGE_SIZE)==0. So the other page at offset%PAGE_SIZE==1k is not updated.
Yep, but we are not required to support non-page-aligned maps at all, so hacking it for special read-only cases is no big deal. Doing a search for all overlapping mapped pages would be far too slow.
--Stephen
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"ST" == Stephen C Tweedie <[email protected]> writes:
ST> Hi,
ST> On 23 Apr 1998 17:03:02 -0500, [email protected] (Eric ST> W. Biederman) said:
ST> No --- in the context of a MAP_PRIVATE mapping, only in-memory writes to ST> the privately mapped virtual address space count as write references.
Got it.
I still like the semantics I defined, but if they aren't defined as map_private I won't worry about it for the present.
Sometime it might be worth it/fun implementing a MAP_SNAPSHOT, but I won't worry about that for the present.
ST> Yep, but we are not required to support non-page-aligned maps at all, so ST> hacking it for special read-only cases is no big deal. Doing a search ST> for all overlapping mapped pages would be far too slow.
I think in the general case I could implement it without overhead and in the common a.out case within a factor of 2, and in the worst case within a factor of 4 (assuming a restriction of 1k alignment). And this is primarly memcpy cost there should be no need for extra disk i/o.
The scheme I'm playing with using will share the same case as extra huge file I/O (> 16TB), and in the common case should perform identically to what we have now.
Thanks for setting me straight. It hadn't been my intention to play with mmap until I found this really weird use of that mmap makes of the page_cache, so I really wasn't prepared for that one.
Eric