Re: [PATCH 0/3] Volatile Ranges (v7) & Lots of words

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 10/07/2012 11:25 PM, Minchan Kim wrote:
Hi John,

On Fri, Sep 28, 2012 at 11:16:30PM -0400, John Stultz wrote:
After Kernel Summit and Plumbers, I wanted to consider all the various
side-discussions and try to summarize my current thoughts here along
with sending out my current implementation for review.

Also: I'm going on four weeks of paternity leave in the very near
(but non-deterministic) future. So while I hope I still have time
for some discussion, I may have to deal with fussier complaints
then yours. :)  In any case, you'll have more time to chew on
the idea and come up with amazing suggestions. :)


General Interface semantics:
----------------------------------------------

The high level interface I've been pushing has so far stayed fairly
consistent:

Application marks a range of data as volatile. Volatile data may
be purged at any time. Accessing volatile data is undefined, so
applications should not do so. If the application wants to access
data in a volatile range, it should mark it as non-volatile. If any
of the pages in the range being marked non-volatile had been purged,
the kernel will return an error, notifying the application that the
data was lost.

But one interesting new tweak on this design, suggested by the Taras
Glek and others at Mozilla, is as follows:

Instead of leaving volatile data access as being undefined , when
accessing volatile data, either the data expected will be returned
if it has not been purged, or the application will get a SIGBUS when
it accesses volatile data that has been purged.

Everything else remains the same (error on marking non-volatile
if data was purged, etc). This model allows applications to avoid
having to unmark volatile data when it wants to access it, then
immediately re-mark it as volatile when its done. It is in effect
Just out of curiosity.
Why should application remark it as volatile again?
It have been already volatile range and application doesn't receive
any signal while it uses that range. So I think it doesn't need to
remark.

Not totally sure I understand your question clearly.

So assuming one has a large cache of independently accessed objects, this mark-nonvolatile/access/mark-volatile pattern is useful if you don't want to have to deal with handling the SIGBUS.

For instance, if when accessing the data (say uncompressed image data), you are passing it to a library (to do something like an image filter, in place), where you don't want the library's access of the data to cause an unexpected SIGBUS that would be difficult to recover from.


"lazy" with its marking, allowing the kernel to hit it with a signal
when it gets unlucky and touches purged data. From the signal handler,
the application can note the address it faulted on, unmark the range,
and regenerate the needed data before returning to execution.
I like this model if plumbers really want it.

I think it makes sense. Also it avoids a hole in the earlier semantics: If accessing volatile data is undefined, and you might get the data, or you might get zeros, there's the problem of writes that occur on purged ranges (Credits to Mike Hommey for pointing this out in his critique of Android's ashmem). If an application writes data to a purged range, the range continues to be considered volatile, and since neighboring data may still be purged, the entire set is considered purged. Because of this, we don't end up purging the data again (at least with the shrinker method).

By adding the SIGBUS on access of purged pages, it cleans up the semantics nicely.




However, If applications don't want to deal with handling the
sigbus, they can use the more straightforward (but more costly)
unmark/access/mark pattern in the same way as my earlier proposals.

This allows folks to balance the cost vs complexity in their
application appropriately.

So that's a general overview of how the idea I'm proposing could
be used.
My idea is that we don't need to move all pages in the range
to tail of LRU or new LRU list. Just move a page in the range
into tail of LRU or new LRU list. And when reclaimer start to find
victim page, it can know this page is volatile by something
(ex, if we use new LRU list, we can know it easily, Otherwise,
we can use VMA's new flag - VM_VOLATILE and we can know it easily
by page_check_references's tweak) and isolate all pages of the range
in middle of LRU list and reclaim them all at once.
So the cost of marking is just a (search cost for finding in-memory
page of the range + moving a page between LRU or from middle to tail)
It means we can move the cost time from mark/unmark to reclaim point.

So this general idea of moving a single page to represent the entire range has been mentioned before (I think Neil also suggested something similar).

But what happens if we are creating a large volatile range, most of which hasn't been accessed in a long time. However, the chosen flag page has been accessed recently. In this case, we might end up swapping volatile pages to disk before we try to evict the volatile flag page.

I haven't looked it up, but I worry that trying to purge the rest of the range would end up causing those pages to be swapped back in.

And Neil's suggestion of removing the rest of the pages from the LRUs (if I understood his suggestion correctly) to avoid swapping out those pages, unfortunately results in the same extra O(n) cost of touching all the pages in the range every time we change the volatility state.




Specific Interface semantics:
---------------------------------------------

Here are some of the open question about how the user interface
should look:
[snip]
fd based interfaces vs madvise:
	In talking with Taras Glek, he pointed out that for his
	needs, the fd based interface is a little annoying, as it
	requires having to get access to tmpfs file and mmap it in,
	then instead of just referencing a pointer to the data he
	wants to mark volatile, he has to calculate the offset from
	start of the mmap and pass those file offsets to the interface.
	Instead he mentioned that using something like madvise would be
	much nicer, since they could just pass a pointer to the object
	in memory they want to make volatile and avoid the extra work.

	I'm not opposed to adding an madvise interface for this as
	well, but since we have a existing use case with Android's
	ashmem, I want to make sure we support this existing behavior.
	Specifically as with ashmem  applications can be sharing
	these tmpfs fds, and so file-relative volatile ranges make
	more sense if you need to coordinate what data is volatile
	between two applications.

	Also, while I agree that having an madvise interface for
	volatile ranges would be nice, it does open up some more
	complex implementation issues, since with files, there is a
	fixed relationship between pages and the files' address_space
	mapping, where you can't have pages shared between different
	mappings. This makes it easy to hang the volatile-range tree
	off of the mapping (well, indirectly via a hash table). With
	general anonymous memory, pages can be shared between multiple
	processes, and as far as I understand, don't have any grouping
	structure we could use to determine if the page is in a
	volatile range or not. We would also need to determine more
	complex questions like: What are the semantics of volatility
	with copy-on-write pages?  I'm hoping to investigate this
	idea more deeply soon so I can be sure whatever is pushed has
	a clear plan of how to address this idea. Further thoughts
	here would be appreciated.
I like madvise interface because allocator can use it for memory pool.
If allocator has free memory which just return from application
he can mark it into volatile so VM can reclaim that pages without swapout
when memory pressure happens and it can unmark it before allocating.
It would be more effective rather than calling munmap or madvise(DONTNEED)
which those operations requires all page table operation and even vma
unlinking in case of munmap.

For it, we can add new VMA flag VM_VOLATILE and we can use reverse mapping
for grouping structure. For COW semantics, I think we can discard volatile
page only if all vmas which share the page don't have VM_VOLATILE.

I'll look into this approach some more. I've got some concerns below.



It would really be great to get any thoughts on these issues, as they
are higher-priority to me then diving into the details of how we
implement this internally, which can shift over time.



Implementation Considerations:
---------------------------------------------
[snip]
* Purging order between volatile ranges:
	Again, since it makes sense to purge all the complete
	pages in a range at the same time, we need to consider the
	subtle difference between the least-recently-used pages vs
	least-recently-used ranges. A single range could contain very
	frequently accessed data, as well as rarely accessed data.
	One must also consider that the act of marking a range as
	volatile may not actually touch the underlying pages. Thus
	purging ranges based on a least-recently-used page may also
	result in purging the most-recently used page.

	Android addressed the purging order question by purging ranges
	in the order they were marked volatile. Thus the oldest
	volatile range is the first range to be purged. This works
	well in the Android  model, as applications aren't supposed
	to access volatile data, so the least-recently-marked-volatile
	order maps well to the least-recently-used-range.

	However, this assumption doesn't hold with the lazy SIGBUS
	notification method, as pages in a volatile range may continue
	to be accessed after the range is marked volatile.  So the
	question as to what is the best order of purging volatile
	ranges is definitely open.

	Abstractly the ideal solution might be to evaluate the
	most-recently used page in each range, and to purge the range
	with the oldest recently-used-page, but I suspect this is
	not something that could be calculated efficiently.

	Additionally, in my conversations with Taras, he pointed out
	that if we are using a one-application-at-a-time UI model,
	it would be ideal to discourage purging volatile data used by
	the current application, instead prioritizing volatile ranges
	from applications that aren't active. However, I'm not sure
	what mechanism could be used to prioritize range purging in
	this fashion, especially considering volatile ranges can be
	on data that is shared between applications.
My thought is that "let it be" without creating new LRU list or
deactivating volatile page to tail of LRU for early reclaiming.
It means volatile pages has same priorty with other normal pages.
Volatile doesn't mean "Early reclaim" but "we don't need to swap out
them for reclaiming" in my perception.

Right. Using your earlier terms, ez-reclaim instead early-reclaim.

Ideally I think we would want to have preference of purging volatile pages over laundering dirty pages under pressure, but maybe that's a separate vmscan issue/optimization for now?



In summary, the idea I am suggesting now if we select lazy SIGBUS is
following as,

1) use madvise and VMA rmap with newly VM_VOLATILE page
2) mark
    just mark VM_VOLATILE in the VMA
3) treat volatile pages same with normal pages in POV aging
    (Of course, non swap system, we have to tweak VM for reclaimaing
     volatile pages, for example, we can move all volatile pages into
     inactive's tail when swapoff happens and VM peek tail of inactive
     LRU list without aging when memory pressure happens)
4) unmark
    just unmark VM_VOLATILE in the VMA and return error.

So to better grasp this, you're suggesting using the vma in-effect as the volatile range object? So if we mark a large area as volatile, we'll create a new vma with the (start, end), splitting the remaining portions of the old area into two non-volatile vmas?

The caveat for #3 seems a bit large. Since on no-swap cases (which are standard for Android) that sounds like we're still having to migrate every page in the range to the end of the list (and move them to the head when they are marked non-volatile). This seems to have the same O(n) performance issue.

Also, if I understand correctly, you could have a one page in multiple vmas, and the semantics for when we consider the page as volatile are awkward. When we want to purge/writeout, do we have to scan every vma the page is in to determine if its volatile?

Another thing I worry about with this, is that the since the vmas are per-mm, I don't see how volatile range could be shared, like with a tmpfs file between two applications, a usage model that Android's ashmem supports.

I'm likely missing something, as I'm unfamiliar so far with the rmap code, so I'll look into this some more (although I may not get too much time for it in the next month). Andi Kleen tried something similar to your suggestion awhile back, but I'm just not confident that the per-mm vmas are the right place to manage this state (thus why I've used address_space mappings).

Thanks again for the feedback!
-john

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>


[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Bugtraq]     [Linux]     [Linux OMAP]     [Linux MIPS]     [ECOS]     [Asterisk Internet PBX]     [Linux API]