Futex non-page-pinning fix
Subsystems (6)
PATCH 2/2 Futex non-page-pinning fix
Hi Andrew, Ingo,
Ingo was (rightfully) concerned about the amount of memory
which could be pinned using FUTEX_FD. This solution doesn't keep pages pinned any more: it hashes on mapping + offset, or for anonomous pages, uses a callback to move them out and back into the hash table as they are swapped out and in.
Searching the (256-bucket) hash table to find potential pages
is fairly slow, but we're swapping anyway, so it's lost in the noise. The hash table is usually fairly empty.
My only concern is for a race between swapping a page in and
it being accessed, but I think I have the callbacks in the right place in the swap code: more VM-aware eyes welcome.
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Futexes without pinning pages
Author: Rusty Russell
Status: Tested on 2.6.0-test4-bk2
Depends: Misc/futex-minor-tweaks.patch.gz
Depends: Misc/qemu-page-offset.patch.gz
D: Avoid pinning pages with futexes in them, to resolve FUTEX_FD DoS.
D: For file-backed mappings, change hash to use page->mapping and
D: page->index, which should uniquely identify each one. For
D: anonymous mappings, insert callbacks in swap code to unhash them
D: when they are swapped out and rehash them when they are swapped
D: back in.
include/linux/futex.h +3 -0
@@ -17,4 +17,7 @@ asmlinkage long sys_futex(u32 __user *ualong do_futex (unsigned long uaddr,int op,int val,unsigned long timeout,unsigned long uaddr2,int val2); +/* For mm/page_io.c to tell us about swapping of (anonymous) pages. */ +extern void futex_swap_out (struct page *page); +extern void futex_swap_in (struct page *page);#endif
kernel/futex.c +63 -14
142 lines not on this page · raw message
mm/page_io.c +3 -0
@@ -19,6 +19,7 @@#include <linux/buffer_head.h> /* for block_sync_page() */ #include <linux/mpage.h> #include <linux/writeback.h> +#include <linux/futex.h> #include <asm/pgtable.h> static struct bio *
@@ -77,6 +78,7 @@ static int end_swap_bio_read(struct bioClearPageUptodate (page); }else {SetPageUptodate (page); +futex_swap_in (page); }unlock_page (page);bio_put (bio);
@@ -105,6 +107,7 @@ int swap_writepage(struct page *page, st }inc_page_state (pswpout);SetPageWriteback (page); +futex_swap_out (page);unlock_page (page);submit_bio (WRITE , bio); out:
Quoted 8 lines · Rusty Russell
Hi Andrew, Ingo,
Ingo was (rightfully) concerned about the amount of memory
which could be pinned usingFUTEX_FD. This solution doesn't keep pages pinned any more: it hashes on mapping + offset, or for anonomous pages, uses a callback to move them out and back into the hash table as they are swapped out and in.
I have a bad feeling about this. We shall see...
Quoted 7 lines
Searching the (256-bucket) hash table to find potential pages
is fairly slow, but we're swapping anyway, so it's lost in the noise. The hash table is usually fairly empty.My only concern is for a race between swapping a page in and
it being accessed, but I think I have the callbacks in the right place in the swap code: more VM-aware eyes welcome.
Looks to be OK: as long as the page is locked you can't go far wrong.
But end_swap_bio_read() is called from interrupt context. Hence the spinlock you have in there needs to become IRQ safe.
Two issues:
a) what to do about futexes in file-backed pages? At present the attacker can pin arbitrary amount of memory by backing it with a file.
Your solution won't scale to solving this, because we need to perform a futex lookup on every add_to_page_cache(). (Well, it will scale fairly well because add_to_page_cache() is ratelimited by the IO speed. But it will still suck quite a bit for some people).
b) Assuming a) is solved: futexes which are backed by tmpfs. tmpfs (which is a study in conceptual baroquenness) will rewrite page->mapping as pages are moved between tmpfs inodes and swapper_space. I _think_ lock_page() is sufficient to serialise against this. If not, both ->page_locks are needed.
This of course will break your hashing scheme. Hooks in move_to_swap_cache() and move_from_swap_cache() are needed.
So what to do? One option is to just not pin the pages at all: let them be reclaimed and/or swapped out. Let the kernel fault them in. We have all the stuff to do this over in fs/aio.c, with use_mm().
It does mean that the futex code would have to change its representation of a futex's location from page/offset to mm/vaddr, and the futex code would need to hook into the exit path, similar to exit_aio().
Or create RLIM_NRFUTEX.
Ingo Molnar
maintainerQuoted 9 lines · Andrew Morton
Two issues:
a) what to do about futexes in file-backed pages? At present the attacker can pin arbitrary amount of memory by backing it with a file.
Your solution won't scale to solving this, because we need to perform a futex lookup on every
add_to_page_cache(). (Well, it will scale fairly well becauseadd_to_page_cache()is ratelimited by the IO speed. But it will still suck quite a bit for some people).
add_to_page_cache() can be fairly high-frequency when the pagecache is created anew (write) and torn down immediately afterwards (temporary files). So i dont think it's 100% ratelimited by IO speed.
the cleanest thing would be to do the hashtable registration with every futex existing in the system. But we might get away with doing it only for FUTEX_FD 'asynchronous' futexes (which are only limited by the # of open files, per process), and do the usual page pinning (and thus fast) thing with the 'synchronous' futexes (which are limited to one per context, so they are resource-limited automatically). As long as the hashtable is empty, the lookup ought to be really fast.
Quoted 1 line
Or create
RLIM_NRFUTEX.
futexes do have some small lowmem footprint nevertheless (they have a queue entry structure, etc.), but much less than PAGE_SIZE. So basically the overhead can be added to the already existing fd footprint, without changing the balance too much.
but if all futexes pin down one page (worst-case), then to make it really safe we'll have to use a fairly low default RLIM_NRFUTEX value - which will decrease the generic utility of futexes.
Ingo
Quoted 4 lines · Ingo Molnar
but if all futexes pin down one page (worst-case), then to make it really
safe we'll have to use a fairly low defaultRLIM_NRFUTEXvalue - which will decrease the generic utility of futexes.
We could make it RLIM_NRFUTEX_PAGES: the number of pages which the user can pin via futexes, perhaps.
Ingo Molnar
maintainerQuoted 6 lines · Andrew Morton
Quoted 3 lines
but if all futexes pin down one page (worst-case), then to make it really
safe we'll have to use a fairly low defaultRLIM_NRFUTEXvalue - which will decrease the generic utility of futexes.We could make it
RLIM_NRFUTEX_PAGES: the number of pages which the user can pin via futexes, perhaps.
the problem is that this is not really a deterministic limit. The nr of thread or open files limit is deterministic: it will either fail or succeed at clone() or open() time - and can be freely used afterwards. The kernel doesnt in fact know about the first use of a futex: no-contention futexes have zero kernel footprint. This is the big plus of them. So i'd really favor some sort of hashing method and no limits, that way the Linux VM is extended and every VM address is waitable and wakable on - a pretty powerful concept.
Ingo
Quoted 7 lines · Ingo Molnar
The
kernel doesnt in fact know about the first use of a futex: no-contention futexes have zero kernel footprint. This is the big plus of them. So i'd really favor some sort of hashing method and no limits, that way the Linux VM is extended and every VM address is waitable and wakable on - a pretty powerful concept.
What about the option of not pinning the pages at all: just fault them in when required?
Ingo Molnar
maintainerQuoted 11 lines · Andrew Morton
Quoted 7 lines · Ingo Molnar
The
kernel doesnt in fact know about the first use of a futex: no-contention futexes have zero kernel footprint. This is the big plus of them. So i'd really favor some sort of hashing method and no limits, that way the Linux VM is extended and every VM address is waitable and wakable on - a pretty powerful concept.What about the option of not pinning the pages at all: just fault them in when required?
precisely what scheme do you mean by this? There are two important points:
when a thread sleeps on a futex, and when some thread does a wakeup on a futex address. We cannot hash the futex based on the virtual address (arbitrary share-ability of futex pages is another key appeal of them), and if by the time the wakeup happens the physical page goes away how do we find which threads are queued on this address?
Ingo
Quoted 10 lines · Ingo Molnar
Quoted 3 lines
What about the option of not pinning the pages at all: just fault them in when required?
precisely what scheme do you mean by this? There are two important points:
when a thread sleeps on a futex, and when some thread does a wakeup on a futex address. We cannot hash the futex based on the virtual address (arbitrary share-ability of futex pages is another key appeal of them), and if by the time the wakeup happens the physical page goes away how do we find which threads are queued on this address?
I was suggesting that we hash the futex on mm+vaddr. Yes, differing vaddrs break that.
umm, how about hashing only on offset into page? That reduces the number of threads which need to be visited in futex_wake() by a factor of up to 1024.
In futext_wake(), fault in and pin the page, then for each thread which is waiting on a futex which has the same offset into a page, do a get_user_pages+follow_page, see if he's waiting on the just-faulted-in page?
Quoted 2 lines · Andrew Morton
umm, how about hashing only on offset into page? That reduces the number of threads which need to be visited in
futex_wake()by a factor of up to 1024.
How likely do you consider it that we then get a major collision? I wouldn't be surprised if, say, glibc lays some hot futexes out in a way that's the same for all processes in the system, like start of the page.... Might as well not hash :)
Greetings,
Arjan van de Ven
Quoted 9 lines · Arjan van de Ven
Quoted 2 lines · Andrew Morton
umm, how about hashing only on offset into page? That reduces the number of threads which need to be visited in
futex_wake()by a factor of up to 1024.How likely do you consider it that we then get a major collision? I wouldn't be surprised if, say, glibc lays some hot futexes out in a way that's the same for all processes in the system, like start of the page.... Might as well not hash :)
How about combining something that's shared to all of the threads that share a futex but not system wide (the mm?) with something simple that won't change, like the page offset? Adding the mm into the mix wil make collisions harder, and limiting the buckets to the number of different futex offsets will make it simple and differentiate between different futexes in the same mm.
Signature · 2 lines
Muli Ben-Yehuda http://www.mulix.org
Quoted 11 lines · Muli Ben-Yehuda
Quoted 9 lines · Arjan van de Ven
Quoted 2 lines · Andrew Morton
umm, how about hashing only on offset into page? That reduces the number of threads which need to be visited in
futex_wake()by a factor of up to 1024.How likely do you consider it that we then get a major collision? I wouldn't be surprised if, say, glibc lays some hot futexes out in a way that's the same for all processes in the system, like start of the page.... Might as well not hash :)
Quoted 6 lines
How about combining something that's shared to all of the threads that share a futex but not system wide (the mm?) with something simple that won't change, like the page offset? Adding the mm into the mix wil make collisions harder, and limiting the buckets to the number of different futex offsets will make it simple and differentiate between different futexes in the same mm.
The problem is that you can (and
want to) share futexes between different processes via shm.... glibc actualy uses this to implement cross-process posix mutexes (mutici?)
Quoted 4 lines · Muli Ben-Yehuda
Quoted 4 lines
Quoted 3 lines
umm, how about hashing only on offset into page? That reduces the number of threads which need to be visited in
futex_wake()by a factor of up to 1024.
Quoted 8 lines
Quoted 4 lines
How likely do you consider it that we then get a major collision? I wouldn't be surprised if, say, glibc lays some hot futexes out in a way that's the same for all processes in the system, like start of the page.... Might as well not hash :)
How about combining something that's shared to all of the threads that share a futex but not system wide (the mm?) with something simple that won't change, like the page offset?
The mm's could well be independent.
Some userspace help would be needed to avoid defeating the hash. In the case where a bunch of threads with a shared mm are waiting on the same futex things should automatically be OK.
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Muli Ben-Yehuda
How about combining something that's shared to all of the threads that share a futex but not system wide (the mm?) with something simple that won't change, like the page offset?
The mm's could well be independent.
I assumed all threads sharing a futex share an mm since you suggested hashing on mm + vaddr?
Quoted 3 lines
Some userspace help would be needed to avoid defeating the hash. In the case where a bunch of threads with a shared mm are waiting on the same futex things should automatically be OK.
Userspace help would be fine, but relying only on userspace could lead to an immediate DoS by forcing the hash to always hash to the same bucket.
Signature · 2 lines
Muli Ben-Yehuda http://www.mulix.org
Quoted 6 lines · Muli Ben-Yehuda
How about combining something that's shared to all of the threads that share a futex but not system wide (the mm?) with something simple that won't change, like the page offset? Adding the mm into the mix wil make collisions harder, and limiting the buckets to the number of different futex offsets will make it simple and differentiate between different futexes in the same mm.
The mm is not the sharing boundary; it can be shared along the usual sharing boundaries; hence we have the usual two cases:
(a) shared between all those mmap()'ing some inode for file-backed memory Can be handled by embedding it into a struct address_space.
(b) shared between all fork()'s between exec()'s for anonymous memory Can be handled by embedding it in some new object representing all fork()'s between exec()'s.
(c) anonymous pages formerly owned by inodes orphaned by truncate(). This is hard.
The containing object (for (a) and (b)) can be located with a back pointer from the futex, except you have the usual intractable disaster whenever file-backed pages are anonymized via truncate().
-- wli
Quoted 3 lines · William Lee Irwin III
except you have the usual intractable disaster
whenever file-backed pages are anonymized viatruncate().
They only arose due to races between major faults and truncate. That got fixed.
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
except you have the usual intractable disaster
whenever file-backed pages are anonymized viatruncate().
Quoted 2 lines · Andrew Morton
They only arose due to races between major faults and truncate. That got fixed.
Then it sounds relatively easy to localize the search structure (if you care to do so), apart from a policy decision about what on earth to do about waiters on truncated futexes.
-- wli
Quoted 11 lines · William Lee Irwin III
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
except you have the usual intractable disaster
whenever file-backed pages are anonymized viatruncate().Quoted 2 lines · Andrew Morton
They only arose due to races between major faults and truncate. That got fixed.
Then it sounds relatively easy to localize the search structure (if you care to do so),
The "group of all processes which could potentially (or really do) share a chunk of anon memory" thing sounds tricky.
Quoted 2 lines
apart from a policy decision about what on earth to do
about waiters on truncated futexes.
erk, screwed.
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
Then it sounds relatively easy to localize the search structure (if you care to do so),
Quoted 2 lines · Andrew Morton
The "group of all processes which could potentially (or really do) share a chunk of anon memory" thing sounds tricky.
Not really; it's just a random data structure with very low odds of proliferating. Hugh did it once (for anobjrmap) and I rearranged and/or rewrote it to suit my preferences (I think I RCU'd the lock in it or some ridiculous nonsense on that order).
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
apart from a policy decision about what on earth to do
about waiters on truncated futexes.
Quoted 1 line · Andrew Morton
erk, screwed.
Well, the decision is essentially arbitrary, it just has to be made (and by definition some decision is being made regardless of what the implementation does or fails to do).
-- wli
In message <[email protected]> you write:
Quoted 2 lines
But
end_swap_bio_read()is called from interrupt context. Hence the spinlock you have in there needs to become IRQ safe.
OK, I've fixed that, with conservative assumptions (so it doesn't assume context). Or is _bh sufficient?
Quoted 4 lines
Two issues:
a) what to do about futexes in file-backed pages? At present the attacker can pin arbitrary amount of memory by backing it with a file.
At present == 2.6.0-test4? In 2.6.0-test4, the attacker can pin one page per process (OK), or on per FD using FUTEX_FD (not OK). This patch changes it so that pages are *never* pinned, whatever is backing them.
Quoted 4 lines
Your solution won't scale to solving this, because we need to perform a futex lookup on every
add_to_page_cache(). (Well, it will scale fairly well becauseadd_to_page_cache()is ratelimited by the IO speed. But it will still suck quite a bit for some people).
I assumed that for non-anonymous pages the mapping + index was always a unique identifier, even as they were swapped out. We need a persistent unique identifier for a page, OR a callback to unhash/rehash it when the identifier changes. Hence mapping + index where mapping != NULL, and the struct page and callbacks for swap pages. Using the callbacks for wherever else page->mapping changes is simple (but may be slow).
Quoted 5 lines
b) Assuming a) is solved: futexes which are backed by tmpfs. tmpfs (which is a study in conceptual baroquenness) will rewrite
page->mappingas pages are moved between tmpfs inodes andswapper_space. I _think_lock_page()is sufficient to serialise against this. If not, both ->page_locks are needed.
Looks like the call to move_to_swap_cache is already serialized by spin_lock(&info->lock) in shmem_writepage AFAICT, in fact, move_to_swap_cache seems to assume serialization, since it does (outside any of its locks):
/* shift page from clean_pages to dirty_pages list */ BUG_ON(PageDirty(page)); set_page_dirty(page);
Quoted 2 lines
This of course will break your hashing scheme. Hooks in
move_to_swap_cache()andmove_from_swap_cache()are needed.
I've added it, but how often does that get called?
A simple optimization would be to have a page bit which says "has ever had someone waiting on a futex" which would optimize this: it could be reset in the futex callbacks if it finds noone is waiting on that page.
Quoted 1 line
Or create
RLIM_NRFUTEX.
This is the option of last resort: shades of SysV semaphores. Even if it only applied to FUTEX_FD, it makes them basically unusable.
OK, here's a new one (modified previous patch prepended for completeness), Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Minor futex comment tweaks and cleanups
Author: Rusty Russell
Status: Tested on 2.6.0-test4-bk2
D: Changes:
D:
D: (1) don't return 0 from futex_wait if we are somehow
D: spuriously woken up, loop in that case.
D:
D: (2) remove bogus comment about address no longer being in this D: address space: we hold the mm lock, and __pin_page succeeded, so it D: can't be true,
D:
D: (3) remove bogus comment about "get_user might fault and schedule", D:
D: (4) clarify comment about hashing: we hash address of struct page,
D: not page itself,
D:
D: (4) remove list_empty check: we still hold the lock, so it can
D: never happen, and
D:
D: (5) single error exit path, and move __queue_me to the end (order
D: doesn't matter since we're inside the futex lock).
kernel/futex.c +32 -33
@@ -84,9 +84,7 @@ static inline void unlock_futex_mm(void)spin_unlock (¤t->mm->page_table_lock); } -/* -* The physical page is shared, so we can hash on its address: -*/ +/* The struct page is shared, so we can hash on its address. */ static inline struct list_head *hash_futex (struct page *page,int offset) { return &futex_queues[hash_long((unsigned long)page + offset,
@@ -311,67 +309,68 @@ static inline int futex_wait(unsigned lo int val, unsigned long time) { -DECLARE_WAITQUEUE (wait ,current ); -int ret =0 , curval; +wait_queue_t wait; +int ret, curval;struct page *page;struct futex_q q; +again:init_waitqueue_head (&q.waiters); +init_waitqueue_entry (wait, current);lock_futex_mm (); page =__pin_page (uaddr - offset);if (!page) { -unlock_futex_mm (); -return -EFAULT ; + ret = -EFAULT ; + goto unlock; } -__queue_me (&q, page, uaddr, offset,-1 ,NULL );/* -* Page is pinned, but may no longer be in this address space. +* Page is pinned, but may be a kernel address. * It cannot schedule, so we access it with the spinlock held. */ if (get_user (curval, (int *)uaddr) !=0 ) { -unlock_futex_mm (); ret = -EFAULT ; - goto out; + goto unlock; } +if (curval != val) { -unlock_futex_mm (); ret = -EWOULDBLOCK ; - goto out; + goto unlock; } -/* -* The get_user() above might fault and schedule so we -* cannot just set TASK_INTERRUPTIBLE state when queueing -* ourselves into the futex hash. This code thus has to -* rely on the futex_wake() code doing a wakeup after removing -* the waiter from the list. -*/ + +__queue_me (&q, page, uaddr, offset,-1 ,NULL );add_wait_queue (&q.waiters, &wait);set_current_state (TASK_INTERRUPTIBLE ); -if (!list_empty (&q.list)) { -unlock_futex_mm (); - time =schedule_timeout (time); - } +unlock_futex_mm (); + + time =schedule_timeout (time); +set_current_state (TASK_RUNNING );/* * NOTE: we don't remove ourselves from the waitqueue because * we are the only user of it. */ -if (time ==0 ) { - ret = -ETIMEDOUT ; - goto out; - } -if (signal_pending (current)) - ret = -EINTR ; -out: -/* Were we woken up anyway? */ +put_page (q.page); + +/* Were we woken up (and removed from queue)? Always return +* success when this happens. */ if (!unqueue_me (&q)) ret =0 ; -put_page (q.page); +else if (time ==0 ) + ret = -ETIMEDOUT ; +else if (signal_pending (current)) + ret = -EINTR ; +else +/* Spurious wakeup somehow. Loop. */ + goto again;return ret; + +unlock: +unlock_futex_mm (); +return ret; }static int futex_close (struct inode *inode,struct file *filp)
Name: Futexes without pinning pages
Author: Rusty Russell
Status: Tested on 2.6.0-test4-bk2
Depends: Misc/futex-minor-tweaks.patch.gz
Depends: Misc/qemu-page-offset.patch.gz
D: Avoid pinning pages with futexes in them, to resolve FUTEX_FD DoS.
D: Insert callbacks in swap code to unhash them when they are swapped
D: out and rehash them when they are swapped back in.
include/linux/futex.h +3 -0
@@ -17,4 +17,7 @@ asmlinkage long sys_futex(u32 __user *ualong do_futex (unsigned long uaddr,int op,int val,unsigned long timeout,unsigned long uaddr2,int val2); +/* For mm/page_io.c to tell us about swapping of (anonymous) pages. */ +extern void futex_swap_out (struct page *page); +extern void futex_swap_in (struct page *page);#endif
kernel/futex.c +75 -22
203 lines not on this page · raw message
mm/page_io.c +3 -0
@@ -19,6 +19,7 @@#include <linux/buffer_head.h> /* for block_sync_page() */ #include <linux/mpage.h> #include <linux/writeback.h> +#include <linux/futex.h> #include <asm/pgtable.h> static struct bio *
@@ -77,6 +78,7 @@ static int end_swap_bio_read(struct bioClearPageUptodate (page); }else {SetPageUptodate (page); +futex_swap_in (page); }unlock_page (page);bio_put (bio);
@@ -105,6 +107,7 @@ int swap_writepage(struct page *page, st }inc_page_state (pswpout);SetPageWriteback (page); +futex_swap_out (page);unlock_page (page);submit_bio (WRITE , bio); out:
mm/swap_state.c +3 -0
@@ -13,6 +13,7 @@#include <linux/init.h> #include <linux/pagemap.h> #include <linux/backing-dev.h> +#include <linux/futex.h> #include <asm/pgtable.h>
@@ -214,6 +215,7 @@ int move_to_swap_cache(struct page *pageBUG_ON (PageDirty (page));set_page_dirty (page);INC_CACHE_INFO (add_total); +futex_swap_out (page); }else if (err == -EEXIST )INC_CACHE_INFO (exist_race);return err;
@@ -248,6 +250,7 @@ int move_from_swap_cache(struct page *pa/* shift page from clean_pages to dirty_pages list */ ClearPageDirty (page);set_page_dirty (page); +futex_swap_in (page); }return err; }
Quoted 7 lines · Rusty Russell
In message <[email protected]> you write:
Quoted 2 lines
But
end_swap_bio_read()is called from interrupt context. Hence the spinlock you have in there needs to become IRQ safe.OK, I've fixed that, with conservative assumptions (so it doesn't assume context). Or is
_bhsufficient?
spin_lock_irq/irqsave is correct.
Quoted 9 lines
Quoted 4 lines
Two issues:
a) what to do about futexes in file-backed pages? At present the attacker can pin arbitrary amount of memory by backing it with a file.
At present == 2.6.0-test4? In 2.6.0-test4, the attacker can pin one page per process (OK), or on per FD using
FUTEX_FD(not OK). This patch changes it so that pages are *never* pinned, whatever is backing them.
oh, OK.
Quoted 5 lines
Quoted 4 lines
Your solution won't scale to solving this, because we need to perform a futex lookup on every
add_to_page_cache(). (Well, it will scale fairly well becauseadd_to_page_cache()is ratelimited by the IO speed. But it will still suck quite a bit for some people).
Quoted 7 lines
I assumed that for non-anonymous pages the mapping + index was always a unique identifier, even as they were swapped out. We need a persistent unique identifier for a page, OR a callback to unhash/rehash it when the identifier changes. Hence mapping + index where mapping != NULL, and the struct page and callbacks for swap pages. Using the callbacks for wherever else
page->mappingchanges is simple (but may be slow).
swap_writepage() and end_swap_bio_read() are not really companion functions. The page is in use and may be mapped into user pagetables during swap_writepage(). It won't actually be freed up for a very long time, if at all.
I guess this means that there could be a large number of futexes which are considered "swapped out" which are in fact not swapped out at all.
I'm starting to dimly understand what this code does. You get 2/10 for patch explanation ;)
I think a better place to rehash the futex would be at the point where the page is added to and removed from swapcache.
When the page is in swapcache it has stable ->mapping and ->index and can be treated in the same way as file-backed MAP_SHARED memory.
If this works then the places to be looking are:
__delete_from_swap_cache(): page moves from swapcache to anon
add_to_swap(): page moves from anon to swapcache.
move_to_swap_cache(): file-backed to swapcache
move_from_swap_cache(): swapcache to file-backed.
The locking you have there in move_to_swap_cache() and move_from_swap_cache() look wrong. Take move_to_swap_cache(): there is a window in which the page has mapping==&swapper_space, but it is hashed over in futex land by the old tmpfs mapping. A futex lookup which is concurrent with move_to_swap_cache() will fail to find the futex.
I think that to resolve this you need to take futex_lock while swizzling the mapping and index in move_to_swap_cache():
spin_lock(&swapper_space.page_lock); spin_lock(&mapping->page_lock);
+ spin_lock(&futex_lock);
err = radix_tree_insert(&swapper_space.page_tree, entry.val, page);
if (!err) {
__remove_from_page_cache(page);
___add_to_page_cache(page, &swapper_space, entry.val);
+ __futex_rehash(page);
}+ spin_unlock(&futex_lock); spin_unlock(&mapping->page_lock); spin_unlock(&swapper_space.page_lock);
Similarly, all places which change the page's hash keys (mapping and index) need to be locked against the futex lookup code.
None of the above four functions are performance-critical; they already take a ton of global locks.
Alternative: just use swapper_space.page_lock when you're doing futex lookups. That will pin down the ->mapping and ->index of anonymous, swapcache and tmpfs pages.
Please make sure it builds with CONFIG_SWAP=n
Please make sure it builds with CONFIG_FUTEX=n (sorry)
Please augment the lock ranking comment at the top of filemap.c
If a futex resides in a pagecache page which is then truncated, a futex_wake() should really send the caller a SIGBUS; it looks like the code will return -EFAULT, which is good enough. Any waiters on that futex will not be wakeable, but they will be killable.
In message <[email protected]> you write:
Quoted 13 lines
Quoted 7 lines
I assumed that for non-anonymous pages the mapping + index was always a unique identifier, even as they were swapped out. We need a persistent unique identifier for a page, OR a callback to unhash/rehash it when the identifier changes. Hence mapping + index where mapping != NULL, and the struct page and callbacks for swap pages. Using the callbacks for wherever else
page->mappingchanges is simple (but may be slow).
swap_writepage()andend_swap_bio_read()are not really companion functions. The page is in use and may be mapped into user pagetables duringswap_writepage(). It won't actually be freed up for a very long time, if at all.
Quoted 5 lines
I guess this means that there could be a large number of futexes which are considered "swapped out" which are in fact not swapped out at all.
I'm starting to dimly understand what this code does. You get 2/10 for patch explanation ;)
Heh, you get 4/10 for reading comprehension. See: "Name: Futexes without pinning pages" at the top of the patch.
lkml trains people to use Alan Cox-style maximal density descriptions, to avoid being accused of insulting colleagues' intelligence (or being accused of not being 31337 enough). You seem to be cut of a different cloth. I will try to be more verbose here, and I think we'll all be better for it.
Quoted 2 lines
I think a better place to rehash the futex would be at the point where the page is added to and removed from swapcache.
This is simplest: the current code actually moves the futex queue out of the hash. If we make the rule: "call futex_rehash" every time page->mapping (or page->index) changes, we avoid races and make the code simpler.
But this means it could be called quite often. One answer is to restrict the futex hashing so we don't have to search the entire table. Another is to have a separate futexed pages hash. The third is to implement the "futex_was_here" bit in the page->flags, which I think will work well in practice. I'll implement it as a separate patch however.
Quoted 2 lines
Similarly, all places which change the page's hash keys (mapping and index) need to be locked against the futex lookup code.
Yes. I'll look at everywhere that mapping is changed: thanks for the hints [snipped].
Quoted 3 lines
Please make sure it builds with
CONFIG_SWAP=nPlease make sure it builds with
CONFIG_FUTEX=n(sorry)
Will do.
Quoted 1 line
Please augment the lock ranking comment at the top of
filemap.c
Yes.
Quoted 4 lines
If a futex resides in a pagecache page which is then truncated, a
futex_wake()should really send the caller a SIGBUS; it looks like the code will return-EFAULT, which is good enough. Any waiters on that futex will not be wakeable, but they will be killable.
It would be nice, but it's not worth more than a couple of lines of kernel code. There's a similar case where one thread is waiting in an mmapped file and it is unmapped by the other thread. It's a programmer bug since obviously noone can now wake the futex you're waiting on...
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Quoted 10 lines · Rusty Russell
Quoted 3 lines
I think a better place to rehash the futex would be at the point where the page is added to and removed from swapcache.
This is simplest: the current code actually moves the futex queue out of the hash. If we make the rule: "call
futex_rehash" every timepage->mapping(orpage->index) changes, we avoid races and make the code simpler.But this means it could be called quite often.
Moving pages to and from swapcache really is not a fastpath at all, so I wouldn't be worrying about that.
And even if the code is sucky, it will only be sucky when there is a lot of swapcache activity AND a lot of futexes are in use.
In message <[email protected]> you write:
Quoted 8 lines
Quoted 1 line · Rusty Russell
But this means it could be called quite often.
Moving pages to and from swapcache really is not a fastpath at all, so I wouldn't be worrying about that.
And even if the code is sucky, it will only be sucky when there is a lot of swapcache activity AND a lot of futexes are in use.
Well, the patch I posted adds a futex_rehash to ___add_to_page_cache, which seems to get called more often (ie. even new pages added to the page cache), but is by far the most logical and simple solution (ie. where you actually change the mapping, the locking *has* to be sufficient).
Walking a 256 entry hash table isn't free even if it's empty. Example patch below.
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Futexes Rehash Optimization
Author: Rusty Russell
Status: Experimental
Depends: Misc/futex-swap.patch.gz
D: The current futex_rehash() call walks the entire hash table, which
D: is slow. The simplest optimization is to have a page->flags bit
D: which indicates a futex has been placed in this page: we can clear
D: it if futex_rehash() finds no futexes.
include/linux/page-flags.h +5 -0
@@ -75,6 +75,7 @@#define PG_mappedtodisk 17/* Has blocks allocated on-disk */ #define PG_reclaim 18/* To be reclaimed asap */ #define PG_compound 19/* Part of a compound page */ +#define PG_futexed 20/* Has/had a futex waiting in it */ /*
@@ -267,6 +268,10 @@ extern void get_full_page_state(struct p#define SetPageCompound (page) set_bit(PG_compound, &(page)->flags)#define ClearPageCompound (page) clear_bit(PG_compound, &(page)->flags) +#define PageFutexed (page) test_bit(PG_futexed, &(page)->flags) +#define SetPageFutexed (page) set_bit(PG_futexed, &(page)->flags) +#define ClearPageFutexed (page) clear_bit(PG_futexed, &(page)->flags) +/* * The PageSwapCache predicate doesn't use a PG_flag at this time, * but it may again do so one day.
kernel/futex.c +7 -0
@@ -130,6 +131,10 @@ void futex_rehash(struct page *page,static int rehash_count =0 ;spin_lock_irqsave (&futex_lock, flags); +if (likely (!PageFutexed (page))) + goto out; + +ClearPageFutexed (page); rehash_count++;for (i =0 ; i <1 <<FUTEX_HASHBITS ; i++) {struct list_head *l, *next;
@@ -141,6 +145,7 @@ void futex_rehash(struct page *page,if (page_matches (page, q)) {list_del (&q->list);list_add (&q->list, &gather); +SetPageFutexed (page);printk ("futex_rehash %i: offset %i %p -> %p\n" , rehash_count, q->offset, page->mapping, new_mapping);
@@ -156,6 +161,7 @@ void futex_rehash(struct page *page,list_add (&q->list,hash_futex (new_mapping, new_index, page, q->offset)); } +out:spin_unlock_irqrestore (&futex_lock, flags); }
@@ -348,6 +354,7 @@ static inline void __queue_me(struct fut q->mapping = page->mapping; q->index = page->index; q->page = page; +SetPageFutexed (page);list_add_tail (&q->list, head);/*
Quoted 2 lines · Rusty Russell
Well, the patch I posted adds a
futex_rehashto___add_to_page_cache,
That's a real hotpath. Certainly we couldn't take a global lock there.
Need to find a way to rehash when moving pages around only in swapcache. I thought the earlier patches were structured that way?
In message <[email protected]> you write:
Quoted 5 lines
Quoted 2 lines · Rusty Russell
Well, the patch I posted adds a
futex_rehashto___add_to_page_cache,That's a real hotpath. Certainly we couldn't take a global lock there.
Agreed.
Quoted 2 lines
Need to find a way to rehash when moving pages around only in swapcache. I thought the earlier patches were structured that way?
Yes, but I'm fairly sure they were racy. Which is enough for me to dislike it.
Rehashing when the ->mapping changes is simple and clear. It's fairly easy to push it up to the callers, and then I'll figure out which ones are adding new pages, and which ones are moving pages from one ->mapping to another (these ones we care about). But it has to be under the same locks (ie. rehashing and changing the mapping an atomic operation) otherwise someone has to prove that noone can do a futex lookup on the page with the new mapping before it's been updated in the hash.
The other possibility is to use some lock we already have, rather than the futex_lock, to protect that PG_futexed bit.
I'll keep working on it. I'm learning more about the VM, at least.
Thanks,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Quoted 2 lines · Rusty Russell
Walking a 256 entry hash table isn't free even if it's empty. Example patch below.
You can avoid walking the whole hash table. Instead of this:
(page, offset) -> list of futexes at (p,o)
You can use a two-level map like this:
(page) -> (offset) -> list of futexes at (p,o)
Or you can use two one-level maps, like this:
(page) -> list of futexes at (p)
(page, offset) -> list of futexes at (p,o)Either of these gives you the list of futexes give then page in O(list_size). They also mean you don't need the page->flags bit to get O(1) for a page with no futexes, but it's probably a good optimisation anyway.
-- Jamie
In message <[email protected]> you write:
Quoted 12 lines
Quoted 2 lines · Rusty Russell
Walking a 256 entry hash table isn't free even if it's empty. Example patch below.
You can avoid walking the whole hash table. Instead of this:
(page, offset) -> list of futexes at (p,o)You can use a two-level map like this:
(page) -> (offset) -> list of futexes at (p,o)
Quoted 7 lines
Or you can use two one-level maps, like this:
(page) -> list of futexes at (p) (page, offset) -> list of futexes at (p,o)Either of these gives you the list of futexes give then page in
O(list_size).
Yes, it's effectively segmenting your hash table, which reduces the effective hash table size for futexes in the same page. I'm reluctant to do that unless there's a real speed problem.
This is the latest version of my futex patch. I think we're getting closer.
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Futexes without pinning pages
Author: Rusty Russell
Status: Tested on 2.6.0-test4-bk2
Depends: Misc/futex-minor-tweaks.patch.gz
Depends: Misc/qemu-page-offset.patch.gz
D: Avoid pinning pages with futexes in them, to resolve FUTEX_FD DoS.
D: This means we need another way to uniquely identify pages, rather
D: than simply comparing the "struct page *" (and using a hash table
D: based on the "struct page *"). For file-backed pages, the
D: page->mapping and page->index provide a unique identifier, which is
D: persistent even if they get swapped out to the file and back. D:
D: For anonymous pages, page->mapping == NULL. So for this case we
D: use the "struct page *" itself to hash and compare: if the page is
D: going to be swapped out, the mapping will be changed (to
D: &swapper_space).
D:
D: We need to catch cases where the mapping changes (anon or tmpfs
D: pages moving into swapcache and back): for these we now have a
D: futex_rehash() callback to rehash all futexes in that page, which
D: must be done atomic with the change in ->mapping, so we hold the
D: futex_lock around both. (This also means any calls to hash_futex()
D: must be inside the futex lock, as in futex_vcache_callback). D:
D: Since most calls to ___add_to_page_cache() (which actually does the
D: ->mapping change) are actually new pages (for which the
D: futex_rehash is not required), we do the locking and futex_rehash
D: in the (few) callers who require it.
D:
D: The main twist is that add_to_page_cache() can only be called for
D: pages which are actually unused (ie. new pages in which there can
D: be no futexes): add_to_swap() called it on already "live" pages.
D: So a new variant "move_to_page_cache()" which calls the
D: futex_rehash() is added, and called from add_to_swap(). D:
D: One remaining FIXME: is in truncate. It would be nice to wake all
D: futexes in mmaped pages when the pages are truncated underneath the
D: mmap: the callers would then get -EFAULT. It's a politeness thing,
D: not a requirement.
include/linux/futex.h +20 -2
@@ -1,9 +1,9 @@#ifndef _LINUX_FUTEX_H#define _LINUX_FUTEX_H +#include <linux/config.h> +#include <linux/spinlock.h> /* Second argument to futex syscall */ - -#define FUTEX_WAIT (0)#define FUTEX_WAKE (1)#define FUTEX_FD (2)
@@ -17,4 +17,22 @@ asmlinkage long sys_futex(u32 __user *ualong do_futex (unsigned long uaddr,int op,int val,unsigned long timeout,unsigned long uaddr2,int val2); +/* To tell us when the page->mapping or page->index changes on page +* which might have futex: must hold futex_lock across futex_rehash +* and actual change. */ +extern spinlock_t futex_lock; +struct page ; +struct address_space ; +#ifdef CONFIG_FUTEX +extern void futex_rehash (struct page *page, +struct address_space *new_mapping, +unsigned long new_index); +#else +static inline void futex_rehash (struct page *page, +struct address_space *new_mapping, +unsigned long new_index) +{ +} +#endif /*CONFIG_FUTEX*/ +#endif
include/linux/pagemap.h +2 -0
@@ -94,6 +94,8 @@ int add_to_page_cache(struct page *page, unsigned long index, int gfp_mask);int add_to_page_cache_lru (struct page *page,struct address_space *mapping,unsigned long index,int gfp_mask); +int move_to_page_cache (struct page *page,struct address_space *mapping, +unsigned long index,int gfp_mask);extern void remove_from_page_cache (struct page *page);extern void __remove_from_page_cache (struct page *page);
kernel/futex.c +93 -24
223 lines not on this page · raw message
mm/filemap.c +41 -9
75 lines not on this page · raw message
mm/page_io.c +7 -0
@@ -19,6 +19,7 @@#include <linux/buffer_head.h> /* for block_sync_page() */ #include <linux/mpage.h> #include <linux/writeback.h> +#include <linux/futex.h> #include <asm/pgtable.h> static struct bio *
@@ -151,8 +152,11 @@ int rw_swap_page_sync(int rw, swp_entry_lock_page (page);BUG_ON (page->mapping); +spin_lock (&futex_lock); +futex_rehash (page, &swapper_space, entry.val); page->mapping = &swapper_space; page->index = entry.val; +spin_unlock (&futex_lock);if (rw ==READ ) { ret =swap_readpage (NULL , page);
@@ -161,7 +165,10 @@ int rw_swap_page_sync(int rw, swp_entry_ ret =swap_writepage (page, &swap_wbc);wait_on_page_writeback (page); } +spin_lock (&futex_lock); +futex_rehash (page,NULL ,0 ); page->mapping =NULL ; +spin_unlock (&futex_lock);if (ret ==0 && (!PageUptodate (page) ||PageError (page))) ret = -EIO ;return ret;
mm/swap_state.c +9 -2
@@ -13,6 +13,7 @@#include <linux/init.h> #include <linux/pagemap.h> #include <linux/backing-dev.h> +#include <linux/futex.h> #include <asm/pgtable.h>
@@ -140,8 +141,8 @@ int add_to_swap(struct page * page)/* * Add it to the swap cache and mark it dirty */ - err =add_to_page_cache (page, &swapper_space, - entry.val,GFP_ATOMIC ); + err =move_to_page_cache (page, &swapper_space, + entry.val,GFP_ATOMIC );if (pf_flags &PF_MEMALLOC ) current->flags |=PF_MEMALLOC ;
@@ -200,8 +201,11 @@ int move_to_swap_cache(struct page *page err =radix_tree_insert (&swapper_space.page_tree, entry.val, page);if (!err) { +spin_lock (&futex_lock); +futex_rehash (page, &swapper_space, entry.val);__remove_from_page_cache (page);___add_to_page_cache (page, &swapper_space, entry.val); +spin_unlock (&futex_lock); }spin_unlock (&mapping->page_lock);
@@ -236,8 +240,11 @@ int move_from_swap_cache(struct page *pa err =radix_tree_insert (&mapping->page_tree, index, page);if (!err) { +spin_lock (&futex_lock); +futex_rehash (page, mapping, index);__delete_from_swap_cache (page);___add_to_page_cache (page, mapping, index); +spin_unlock (&futex_lock); }spin_unlock (&mapping->page_lock);
mm/truncate.c +1 -0
@@ -53,6 +53,7 @@ truncate_complete_page(struct address_spclear_page_dirty (page);ClearPageUptodate (page);ClearPageMappedToDisk (page); +/* FIXME: Rehash futexes, or send signal? --RR */ remove_from_page_cache (page);page_cache_release (page);/* pagecache ref */ }
Quoted 3 lines · Rusty Russell
This is the latest version of my futex patch. I think we're getting closer.
Miscellaneous comments:
1. Please leave mm/page_io.c out of it. rw_swap_page_sync used to be just for swapon to read the header page of a swap area: it seems swapon no longer uses it, but kernel/power/swsusp.c has grabbed it. It would be very much better if that had a bdev_write_page to match its bdev_read_page, and we could delete rw_swap_page_sync; but that's not for your patch (and I've no inclination to get into swsusp either).
rw_swap_page_sync is just a way of hacking page->mapping and page->index temporarily, in order to make use of some lowlevel swapio routines. If futexes really need to be looked up at that stage of swsusp, you're in trouble anyway. And (though I may be quite wrong, not knowing swsusp) it looks like doing futex_rehash there could actually introduce errors - the page containing the corresponding struct futex_q would get suspended to disk with mapping wrongly set to &swapper_space, so lookups would get missed after resume.
2. Please leave mm/swap_state.c's move_to_swap_cache and move_from_swap_ cache out of it. I already explained how those are for tmpfs files, and it's only the file mapping and index you need to worry about, you won't see a such page while it's assigned to swapper_space. If you're anxious to show that you've visited everywhere that modifies page->mapping, then add a comment or BUG, but not code which could mislead people into thinking futexes really need to be rehashed there.
3. Please remove reference to move_xxx_swap_cache from locking hierarchy comment in mm/filemap.c. And reference to swap_out_add_to_swap_cache:
probably meant to say move_to_page_cache (I'm not keen on that name, too much like the unrelated _swap_cache pair, but never mind, it'll do).
4. You've added a comment line to mm/truncate.c truncate_complete_page, but that's the wrong place for it. If you are going to do something about truncation, then you need to do it whether or not the page is currently in cache: needs to be a mapping/indexrange thing not a struct page* thing. Do you need to do anything at all? I hope not, but unsure.
5. If you're not doing anything in __remove_from_page_cache (rightly trying to avoid hotpath), you do need to futex_rehash in mm/swap_state.c __delete_from_swap_cache (last time I did say without the __s, but that would miss an instance you need to catch). That will handle the swapoff case amongst others.
6. The futex_q has no reference count on struct address_space *mapping. A task might set a futex in a shared file mapping, get a futex fd, unmap the mapping, delete the file, poll the fd, and be woken for events on whatever (if anything) next got a struct address_space at that same address? Is this a possible scenario, and is it a worry?
Hugh
Quoted 6 lines · Hugh Dickins
5. If you're not doing anything in
__remove_from_page_cache(rightly trying to avoid hotpath), you do need tofutex_rehashinmm/swap_state.c__delete_from_swap_cache(last time I did say without the__s, but that would miss an instance you need to catch). That will handle the swapoff case amongst others.
Of course, the reason I originally said without the __s, was because move_from_swap_cache uses __delete_from_swap_cache, and we don't want interference there. So best convert that to use __remove_from_page_cache instead, with INC_CACHE_INFO(del_total) outside the locking, after theset_page_dirty: would improve symmetry between move_from_ and move_to_.
The instance of __delete_from_swap_cache I say you need to catch, is that in remove_exclusive_swap_page; though I think its count restrictions limit it to cornercases like your test program, rather than real communication between processes. But hold on, in such a cornercase (no other references to the swap), what if the process unmaps the vma containing the futex while it is swapped out and not even in page cache? Unclear.
Hugh
In message <[email protected]> you write:
Quoted 8 lines · Hugh Dickins
Quoted 6 lines
5. If you're not doing anything in
__remove_from_page_cache(rightly trying to avoid hotpath), you do need tofutex_rehashinmm/swap_state.c__delete_from_swap_cache(last time I did say without the__s, but that would miss an instance you need to catch). That will handle the swapoff case amongst others.
Quoted 5 lines
Of course, the reason I originally said without the
__s, was becausemove_from_swap_cacheuses__delete_from_swap_cache, and we don't want interference there. So best convert that to use__remove_from_page_cacheinstead, withINC_CACHE_INFO(del_total)outside the locking, after theset_page_dirty: would improve symmetry betweenmove_from_andmove_to_.
But you previously said:
Message-ID: <[email protected]>
Quoted 7 lines
2. Please leave mm/swap_state.c's
move_to_swap_cacheandmove_from_swap_cache out of it. I already explained how those are for tmpfs files, and it's only the file mapping and index you need to worry about, you won't see a such page while it's assigned toswapper_space. If you're anxious to show that you've visited everywhere that modifiespage->mapping, then add a comment or BUG, but not code which could mislead people into thinking futexes really need to be rehashed there.
Confused,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
In message <[email protected]> you write:
Quoted 6 lines · Rusty Russell
Quoted 3 lines
This is the latest version of my futex patch. I think we're getting closer.
Miscellaneous comments:
Hi Hugh!
Thanks for the analysis.
Quoted 6 lines
1. Please leave
mm/page_io.cout of it.rw_swap_page_syncused to be just for swapon to read the header page of a swap area: it seems swapon no longer uses it, butkernel/power/swsusp.chas grabbed it. It would be very much better if that had abdev_write_pageto match itsbdev_read_page, and we could deleterw_swap_page_sync; but that's not for your patch (and I've no inclination to get into swsusp either).
Right, I just looked for everywhere that ->mapping was set, and touched every one I wasn't *sure* was safe. I've deleted the change to rw_swap_page_sync().
Quoted 7 lines
2. Please leave mm/swap_state.c's
move_to_swap_cacheandmove_from_swap_cache out of it. I already explained how those are for tmpfs files, and it's only the file mapping and index you need to worry about, you won't see a such page while it's assigned toswapper_space. If you're anxious to show that you've visited everywhere that modifiespage->mapping, then add a comment or BUG, but not code which could mislead people into thinking futexes really need to be rehashed there.
OK. I've removed it, too. Patch is getting shorter 8)
Quoted 2 lines
3. Please remove reference to
move_xxx_swap_cachefrom locking hierarchy comment inmm/filemap.c.
Andrew told me to add a comment 8(. I've removed it again.
Quoted 3 lines
And reference to
swap_out_add_to_swap_cache:
probably meant to saymove_to_page_cache(I'm not keen on that name, too much like the unrelated_swap_cachepair, but never mind, it'll do).
Hmm, comment was moved, not modified. If it was wrong before, it's wrong now 8(
Quoted 5 lines
4. You've added a comment line to
mm/truncate.ctruncate_complete_page, but that's the wrong place for it. If you are going to do something about truncation, then you need to do it whether or not the page is currently in cache: needs to be a mapping/indexrange thing not a struct page* thing. Do you need to do anything at all? I hope not, but unsure.
No, we don't *need* to do anything. If a file is mmapped and someone truncates the file, it'd be nice to scan the futex table and wake everyone so they can -EFAULT or SEGV. Similar case is whenever any area is munmaped, it'd be nice to find any futexes waiting in those pages and wake them. But it's not worth working up a sweat over, IMHO, it's undefined behavior (don't do that, then).
A FIXME at the top of futex.c in case someone gets ambitious is a better choice: done.
Quoted 5 lines
5. If you're not doing anything in
__remove_from_page_cache(rightly trying to avoid hotpath), you do need tofutex_rehashinmm/swap_state.c__delete_from_swap_cache(last time I did say without the__s, but that would miss an instance you need to catch). That will handle the swapoff case amongst others.
Thanks. I looked at the callers, and thought it unneccessary, but only mm/vmscan.c's shrink_list seems to just free the page. Done.
Quoted 5 lines
6. The
futex_qhas no reference count on structaddress_space*mapping. A task might set a futex in a shared file mapping, get a futex fd, unmap the mapping, delete the file, poll the fd, and be woken for events on whatever (if anything) next got a structaddress_spaceat that same address? Is this a possible scenario, and is it a worry?
Yes. It's the same "it'd be nice to wake on unmap" problem: undefined behavior but not a requirement.
A futex page bit would probably be the best way to do this sanely if someone was interested.
Cheers,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Minor futex comment tweaks and cleanups
Author: Rusty Russell
Status: Booted on 2.6.0-test4-bk3
D: Changes:
D:
D: (1) don't return 0 from futex_wait if we are somehow
D: spuriously woken up, loop in that case.
D:
D: (2) remove bogus comment about address no longer being in this D: address space: we hold the mm lock, and __pin_page succeeded, so it D: can't be true,
D:
D: (3) remove bogus comment about "get_user might fault and schedule", D:
D: (4) clarify comment about hashing: we hash address of struct page,
D: not page itself,
D:
D: (4) remove list_empty check: we still hold the lock, so it can
D: never happen, and
D:
D: (5) single error exit path, and move __queue_me to the end (order
D: doesn't matter since we're inside the futex lock).
kernel/futex.c +32 -33
@@ -84,9 +84,7 @@ static inline void unlock_futex_mm(void)spin_unlock (¤t->mm->page_table_lock); } -/* -* The physical page is shared, so we can hash on its address: -*/ +/* The struct page is shared, so we can hash on its address. */ static inline struct list_head *hash_futex (struct page *page,int offset) { return &futex_queues[hash_long((unsigned long)page + offset,
@@ -311,67 +309,68 @@ static inline int futex_wait(unsigned lo int val, unsigned long time) { -DECLARE_WAITQUEUE (wait ,current ); -int ret =0 , curval; +wait_queue_t wait; +int ret, curval;struct page *page;struct futex_q q; +again:init_waitqueue_head (&q.waiters); +init_waitqueue_entry (&wait, current);lock_futex_mm (); page =__pin_page (uaddr - offset);if (!page) { -unlock_futex_mm (); -return -EFAULT ; + ret = -EFAULT ; + goto unlock; } -__queue_me (&q, page, uaddr, offset,-1 ,NULL );/* -* Page is pinned, but may no longer be in this address space. +* Page is pinned, but may be a kernel address. * It cannot schedule, so we access it with the spinlock held. */ if (get_user (curval, (int *)uaddr) !=0 ) { -unlock_futex_mm (); ret = -EFAULT ; - goto out; + goto unlock; } +if (curval != val) { -unlock_futex_mm (); ret = -EWOULDBLOCK ; - goto out; + goto unlock; } -/* -* The get_user() above might fault and schedule so we -* cannot just set TASK_INTERRUPTIBLE state when queueing -* ourselves into the futex hash. This code thus has to -* rely on the futex_wake() code doing a wakeup after removing -* the waiter from the list. -*/ + +__queue_me (&q, page, uaddr, offset,-1 ,NULL );add_wait_queue (&q.waiters, &wait);set_current_state (TASK_INTERRUPTIBLE ); -if (!list_empty (&q.list)) { -unlock_futex_mm (); - time =schedule_timeout (time); - } +unlock_futex_mm (); + + time =schedule_timeout (time); +set_current_state (TASK_RUNNING );/* * NOTE: we don't remove ourselves from the waitqueue because * we are the only user of it. */ -if (time ==0 ) { - ret = -ETIMEDOUT ; - goto out; - } -if (signal_pending (current)) - ret = -EINTR ; -out: -/* Were we woken up anyway? */ +put_page (q.page); + +/* Were we woken up (and removed from queue)? Always return +* success when this happens. */ if (!unqueue_me (&q)) ret =0 ; -put_page (q.page); +else if (time ==0 ) + ret = -ETIMEDOUT ; +else if (signal_pending (current)) + ret = -EINTR ; +else +/* Spurious wakeup somehow. Loop. */ + goto again;return ret; + +unlock: +unlock_futex_mm (); +return ret; }static int futex_close (struct inode *inode,struct file *filp)
Name: Futexes without pinning pages
Author: Rusty Russell
Status: Booted on 2.6.0-test4-bk3
Depends: Misc/futex-minor-tweaks.patch.gz
Depends: Misc/qemu-page-offset.patch.gz
D: Avoid pinning pages with futexes in them, to resolve FUTEX_FD DoS.
D: This means we need another way to uniquely identify pages, rather
D: than simply comparing the "struct page *" (and using a hash table
D: based on the "struct page *"). For file-backed pages, the
D: page->mapping and page->index provide a unique identifier, which is
D: persistent even if they get swapped out to the file and back. D:
D: For anonymous pages, page->mapping == NULL. So for this case we
D: use the "struct page *" itself to hash and compare: if the page is
D: going to be swapped out, the mapping will be changed (to
D: &swapper_space).
D:
D: We need to catch cases where the mapping changes (anon or tmpfs
D: pages moving into swapcache and back): for these we now have a
D: futex_rehash() callback to rehash all futexes in that page, which
D: must be done atomic with the change in ->mapping, so we hold the
D: futex_lock around both. (This also means any calls to hash_futex()
D: must be inside the futex lock, as in futex_vcache_callback). D:
D: Since most calls to ___add_to_page_cache() (which actually does the
D: ->mapping change) are actually new pages (for which the
D: futex_rehash is not required), we do the locking and futex_rehash
D: in the (few) callers who require it.
D:
D: The main twist is that add_to_page_cache() can only be called for
D: pages which are actually unused (ie. new pages in which there can
D: be no futexes): add_to_swap() called it on already "live" pages.
D: So a new variant "move_to_page_cache()" which calls the
D: futex_rehash() is added, and called from add_to_swap().
include/linux/futex.h +24 -2
@@ -1,9 +1,9 @@#ifndef _LINUX_FUTEX_H#define _LINUX_FUTEX_H +#include <linux/config.h> +#include <linux/spinlock.h> /* Second argument to futex syscall */ - -#define FUTEX_WAIT (0)#define FUTEX_WAKE (1)#define FUTEX_FD (2)
@@ -17,4 +17,26 @@ asmlinkage long sys_futex(u32 __user *ualong do_futex (unsigned long uaddr,int op,int val,unsigned long timeout,unsigned long uaddr2,int val2); +/* To tell us when the page->mapping or page->index changes on page +* which might have futex: must hold futex_lock across futex_rehash +* and actual change. */ +struct page ; +struct address_space ; +#ifdef CONFIG_FUTEX +extern spinlock_t futex_lock; +extern void futex_rehash (struct page *page, +struct address_space *new_mapping, +unsigned long new_index); +#define lock_futex () spin_lock(&futex_lock) +#define unlock_futex () spin_unlock(&futex_lock) +#else +static inline void futex_rehash (struct page *page, +struct address_space *new_mapping, +unsigned long new_index) +{ +} +#define lock_futex () +#define unlock_futex () +#endif /*CONFIG_FUTEX*/ +#endif
include/linux/pagemap.h +2 -0
@@ -94,6 +94,8 @@ int add_to_page_cache(struct page *page, unsigned long index, int gfp_mask);int add_to_page_cache_lru (struct page *page,struct address_space *mapping,unsigned long index,int gfp_mask); +int move_to_page_cache (struct page *page,struct address_space *mapping, +unsigned long index,int gfp_mask);extern void remove_from_page_cache (struct page *page);extern void __remove_from_page_cache (struct page *page);
kernel/futex.c +96 -24
226 lines not on this page · raw message
mm/filemap.c +38 -9
66 lines not on this page · raw message
mm/swap_state.c +6 -2
@@ -13,6 +13,7 @@#include <linux/init.h> #include <linux/pagemap.h> #include <linux/backing-dev.h> +#include <linux/futex.h> #include <asm/pgtable.h>
@@ -96,7 +97,10 @@ void __delete_from_swap_cache(struct pagBUG_ON (!PageLocked (page));BUG_ON (!PageSwapCache (page));BUG_ON (PageWriteback (page)); +lock_futex (); +futex_rehash (page,NULL ,0 );__remove_from_page_cache (page); +unlock_futex ();INC_CACHE_INFO (del_total); }
@@ -140,8 +144,8 @@ int add_to_swap(struct page * page)/* * Add it to the swap cache and mark it dirty */ - err =add_to_page_cache (page, &swapper_space, - entry.val,GFP_ATOMIC ); + err =move_to_page_cache (page, &swapper_space, + entry.val,GFP_ATOMIC );if (pf_flags &PF_MEMALLOC ) current->flags |=PF_MEMALLOC ;
What happens after this sequence:
1. process A forks, making process B
2. B does FUTEX_FD, or splits into threads and one does FUTEX_WAIT, on a private page that has not been written to since the fork
3. A does FUTEX_WAIT on the same address
3. The page is swapped out
4. B does FUTEX_WAKE at the same address
Won't the futex be hashed on the swap entry at step 4, so that both processes are woken, yet only the waiter in B should be woken?
Related: could COW sharing after fork() explain the spurious wakeups I saw mentioned earlier in the thread?
-- Jamie
Quoted 11 lines · Jamie Lokier
What happens after this sequence:
1. process A forks, making process B
2. B doesFUTEX_FD, or splits into threads and one doesFUTEX_WAIT, on a private page that has not been written to since the fork
3. A doesFUTEX_WAITon the same address
3. The page is swapped out
4. B doesFUTEX_WAKEat the same addressWon't the futex be hashed on the swap entry at step 4, so that both processes are woken, yet only the waiter in B should be woken?
I don't see that step 3 (the second!) makes any difference:
it behaves like that whether or not the page is swapped out, doesn't it?
I agree with you that behaviour seems wrong for a private anonymous page. And we'd agree it's right behaviour for a shared file page. The case of a MAP_PRIVATE or !PROT_WRITE file page may be harder to decide, but I'm inclined to follow you and say distinction should depend on MAP_SHARED (shm included as MAP_SHARED mapping of unnamed shmem object).
I know nothing of the user/glibc end of futexes, perhaps it makes your case academic. But I'd still like a consistent definition for how sys_futex should behave.
I'd been wondering along similar lines (worried by futex on uninstantiated anon page, which would end up on the empty zero page), thinking futex.c's __pin_page ought to pass write flag set to follow_page and get_user_pages.
But now (and I'd like to switch to capitals, but restrain myself) I think most of the COW/vcache/callback/swap/page/pinning stuff is just a waste of space and time, creating its own problems which it then has to solve.
When sys_futex passes a uaddr in a VM_MAYSHARE vma, it should be handled by mapping/index (or inode/offset). When sys_futex passes a uaddr in a !VM_MAYSHARE vma, it should be handled by mm/uaddr. (If outside vma?)
That's it. Doesn't a whole lot of code and complication fall away? The physical page is pretty much irrelevant.
For a while I thought this would change the behaviour if futex is mremapped. Well, yes, but nobody has remembered to do anything about vcache in mremap anyway, so it's already broken.
What am I missing?
Hugh
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 11 lines · Jamie Lokier
What happens after this sequence:
1. process A forks, making process B
2. B doesFUTEX_FD, or splits into threads and one doesFUTEX_WAIT, on a private page that has not been written to since the fork
3. A doesFUTEX_WAITon the same address
3. The page is swapped out
4. B doesFUTEX_WAKEat the same addressWon't the futex be hashed on the swap entry at step 4, so that both processes are woken, yet only the waiter in B should be woken?
I don't see that step 3 (the second!) makes any difference:
it behaves like that whether or not the page is swapped out, doesn't it?
I agree with you that behaviour seems wrong for a private anonymous page. And we'd agree it's right behaviour for a shared file page. The case of a MAP_PRIVATE or !PROT_WRITE file page may be harder to decide, but I'm inclined to follow you and say distinction should depend on MAP_SHARED (shm included as MAP_SHARED mapping of unnamed shmem object).
I know nothing of the user/glibc end of futexes, perhaps it makes your case academic. But I'd still like a consistent definition for how sys_futex should behave.
I'd been wondering along similar lines (worried by futex on uninstantiated anon page, which would end up on the empty zero page), thinking futex.c's __pin_page ought to pass write flag set to follow_page and get_user_pages.
But now (and I'd like to switch to capitals, but restrain myself) I think most of the COW/vcache/callback/swap/page/pinning stuff is just a waste of space and time, creating its own problems which it then has to solve.
When sys_futex passes a uaddr in a VM_MAYSHARE vma, it should be handled by mapping/index (or inode/offset). When sys_futex passes a uaddr in a !VM_MAYSHARE vma, it should be handled by mm/uaddr. (If outside vma?)
That's it. Doesn't a whole lot of code and complication fall away? The physical page is pretty much irrelevant.
For a while I thought this would change the behaviour if futex is mremapped. Well, yes, but nobody has remembered to do anything about vcache in mremap anyway, so it's already broken.
What am I missing?
Hugh
Quoted 7 lines · Hugh Dickins
Quoted 7 lines
1. process A forks, making process B
2. B doesFUTEX_FD, or splits into threads and one doesFUTEX_WAIT, on a private page that has not been written to since the fork
3. A doesFUTEX_WAITon the same address
3. The page is swapped out
4. B doesFUTEX_WAKEat the same address
Quoted 5 lines
Quoted 2 lines
Won't the futex be hashed on the swap entry at step 4, so that both processes are woken, yet only the waiter in B should be woken?
I don't see that step 3 (the second!) makes any difference:
it behaves like that whether or not the page is swapped out, doesn't it?
You're right.
I had assumed that the reformed futex keyed on (mapping, offset) for shared pages and (mm, page) for private anonymous pages. But I see it only keys on (page) in the latter case.
Now I see that it _ought_ to key on (mapping, index, offset) for shared mappings, (mm, uaddr) for private mappings.
Quoted 2 lines
I agree with you that behaviour seems wrong for a private anonymous page. And we'd agree it's right behaviour for a shared file page.
Yes.
Quoted 4 lines
The case of a
MAP_PRIVATEor !PROT_WRITE file page may be harder to decide, but I'm inclined to follow you and say distinction should depend onMAP_SHARED(shm included asMAP_SHAREDmapping of unnamed shmem object).
Yes, absolutely.
Quoted 3 lines
I know nothing of the user/glibc end of futexes, perhaps it makes your case academic. But I'd still like a consistent definition for how
sys_futexshould behave.
Futexes are actually a very nice primitive, and used by more than glibc already. In particular, they are used inside database files and similar things.
Quoted 3 lines
I'd been wondering along similar lines (worried by futex on uninstantiated anon page, which would end up on the empty zero page), thinking futex.c's
__pin_pageought to pass write flag set tofollow_pageandget_user_pages.
Shared read-only mappings should be futexable too. Also, there is no need to clone a page at __pin_page() time, because the vcache should take care of any subsequent COW. (Also it wouldn't work because the page can become a COW page after the futex is established, due to a subsequent fork).
Quoted 3 lines
But now (and I'd like to switch to capitals, but restrain myself) I think most of the COW/vcache/callback/swap/page/pinning stuff is just a waste of space and time, creating its own problems which it then has to solve.
Not pinning pages fixes a real resource leak problem, and is obviously the right thing to do - lots of threads queued up on futexes in a database file, for example, should still be pageable as much as possible.
Quoted 10 lines
When
sys_futexpasses a uaddr in aVM_MAYSHAREvma, it should be handled by mapping/index (or inode/offset). Whensys_futexpasses a uaddr in a !VM_MAYSHARE vma, it should be handled by mm/uaddr. (If outside vma?)That's it. Doesn't a whole lot of code and complication fall away? The physical page is pretty much irrelevant.
For a while I thought this would change the behaviour if futex is mremapped. Well, yes, but nobody has remembered to do anything about vcache in mremap anyway, so it's already broken.
I have thought it over and I agree.
Keying on (mm,uaddr) instead of (page) does solve the problem of private mappings and COW. It also removes the need for the page to be in memory (a minor bonus, not an important reason).
The vcache is horribly broken with mremap(). If vcache is fixed to rehash vcache entries on mremap, that could rehash the futexes too.
Rusty, I see that futex.c does a vcache lookup for every wait and wake at the moment.
That means every wait and wake does two hash lookups at the moment. We can reduce that to one :)
I think this solves the COW incorrect/spurious wakeups problem _and_ removes page pinning (without mm hooks) _and_ makes futex_rehash _and_ speeds up futex operations. Credit for the idea goes to Hugh:
1. Remove all references to struct page from futex.c (!)
2. Call find_extend_vma instead of get_user_pages, and decide how to look up the futex_q based on (vma & VM_SHARED).
3. For (vma & VM_SHARED), look up futex_qs keyed on (vma->vm_file, vma->vm_pgoff + (uaddr - vma->vm_start) >> PAGE_SHIFT, offset).
4. For !(vma & VM_SHARED), look up futex_qs keyed on (mm, uaddr).
Note how pages aren't pinned by this, vcache isn't needed, it is fine with swapping, and works correctly with COW pages. tmpfs & shared memory (all 3 kinds) are also correct: if they are mapped privately, (mm, uaddr) is a fine key, and if they are mapped shared, (file, offset) is a correct key at all times whether swapped or not.
mremap does not work with the above, but mremap is broken anyway, as all futexes use the vcache at present which is broken by mremap. When mremap is fixed to rehash a vcache address range, it can be fixed to rehash a futex address range too.
The more I think about it, the better it looks. So sure, I am, that I must have missed something. What do you think, Rusty?
-- Jamie
Quoted 4 lines · Jamie Lokier
3. For (vma & VM_SHARED), look up futex_qs keyed on (vma->vm_file, vma->vm_pgoff + (uaddr - vma->vm_start) >> PAGE_SHIFT, offset).
That's a bit meaningless in non-linear mappings.
Quoted 7 lines · Andrew Morton
Quoted 4 lines · Jamie Lokier
3. For (vma & VM_SHARED), look up futex_qs keyed on (vma->vm_file, vma->vm_pgoff + (uaddr - vma->vm_start) >> PAGE_SHIFT, offset).That's a bit meaningless in non-linear mappings.
You think it's worth supporting futexes on non-linear mappings? I see your point of view; they could be useful.
In that case, the (vma & VM_SHARED) case needs to look up the correct pgoff or page after all.
It might be worth a VM_NONLINEAR flag, to skip walking the page table in the non-linear case, but that's just an optimisation.
-- Jamie
In message <[email protected]> you write:
Quoted 7 lines · Hugh Dickins
When
sys_futexpasses a uaddr in aVM_MAYSHAREvma, it should be handled by mapping/index (or inode/offset). Whensys_futexpasses a uaddr in a !VM_MAYSHARE vma, it should be handled by mm/uaddr. (If outside vma?)That's it. Doesn't a whole lot of code and complication fall away? The physical page is pretty much irrelevant.
The physical page is a relic from my original implementation, which did "pin page and hash on it". Life was simple and good, and then came FUTEX_FD (which allows more than one futex per process) and before Ingo found the COW issue, and added the vcache stuff.
Now, I am lost in a maze of VM hackers' advice, all slightly different 8)
Assume that we do:
1) Look up vma.
2) If vma->vm_flags & VM_SHARED, index by page->mapping & page->index.
3) Otherwise, index by vma->vm_mm & uaddr.
Questions:
1) What is the difference between VM_SHARED and VM_MAYSHARE? They always seem to be set/reset together.
2) If VM_SHARED, and page->mapping is NULL, what to do? AFAICT, this can happen in the case of anonymous shared mappings, say mmap /dev/zero MAP_SHARED and fork()? Treating it as !VM_SHARED (and hence matching in mm & uaddr) won't work, since the mm's will be different (and with mremap, the uaddrs may be different).
3) Since we need the offset in the file anyway for the VM_SHARED, it makes more sense to use get_user_pages() to get the vma and page in one call, rather than find_extend_vma().
4) mremap on a futex: same case as munmap, it's undefined behavior. A correct program will need to re-wait on the futex anyway.
BTW, the other solution to the COW problem which Ingo thought about (I was away on my honeymoon), was to have the child always get the copied page, even if the parent caused the COW fault. If you also always un-COW the page in FUTEX_WAIT, this scheme works. IIRC he said the implementation was icky.
Thanks,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
PATCH 1/1 Alternate futex non-page-pinning and COW fix
Quoted 4 lines · Rusty Russell
The physical page is a relic from my original implementation, which did "pin page and hash on it". Life was simple and good, and then came
FUTEX_FD(which allows more than one futex per process) and before Ingo found the COW issue, and added the vcache stuff.
Hi Rusty,
You will be please to know I have written a complete patch :)
Quoted 4 lines
Assume that we do:
1) Look up vma.
2) Ifvma->vm_flags&VM_SHARED, index bypage->mapping&page->index.
3) Otherwise, index byvma->vm_mm& uaddr.
Like that, but 2) uses vma->vm_file->f_dentry->d_inode.
That way, there is no need to walk the page table at all unless it's a non-linear mapping (which my patch does handle).
Quoted 3 lines
Questions:
1) What is the difference betweenVM_SHAREDandVM_MAYSHARE? They always seem to be set/reset together.
Good question. No kernel code seems to check VM_MAYSHARE - the one to check is VM_SHARED.
Quoted 5 lines
2) If
VM_SHARED, andpage->mappingis NULL, what to do? AFAICT, this can happen in the case of anonymous shared mappings, say mmap/dev/zeroMAP_SHAREDandfork()? Treating it as !VM_SHARED (and hence matching in mm & uaddr) won't work, since the mm's will be different (and with mremap, the uaddrs may be different).
No, that doesn't happen. An anoymous shared mapping calls shmem_zero_setup(), which creates an anonymous tmpfs file to back the mapping. It then looks the same as IPC shm or any other tmpfs file.
So it works :)
Quoted 3 lines
3) Since we need the offset in the file anyway for the
VM_SHARED, it makes more sense to useget_user_pages()to get the vma and page in one call, rather thanfind_extend_vma().
You need the offset, but you don't need the page. For a linear mapping, the offset is a very simple calculation - no page table lock and no page table walk. As a silly bonus it doesn't touch the page.
For non-linear mappings, I try follow_page() and then get_user_pages(), as usual, to get page->index. Technically you don't need to swap the page in, but there's no point using complicated code for that unimportant case.
I added a flag VM_NONLINEAR to distinguish them.
Quoted 8 lines
4) mremap on a futex: same case as munmap, it's undefined behavior. A correct program will need to re-wait on the futex anyway.
BTW, the other solution to the COW problem which Ingo thought about (I was away on my honeymoon), was to have the child always get the copied page, even if the parent caused the COW fault. If you also always un-COW the page in
FUTEX_WAIT, this scheme works. IIRC he said the implementation was icky.
That's icky in a lot of ways, including unnecessary un-COWing.
I have an obvious fix for mremap(): rehash all the futexes in its range. That's not in the attached patch, but it will be in the next one.
Please take a look at the patch and see what you think. I have tried some basic tests with it (playing with your futex-2.2 lib, and Red Hat 9 uses plenty of futexes while booting & running too).
Patch is against 2.6.0-test4. Net reduction of about 100 lines from test4, too :)
Thanks,
-- Jamie
===========================================
include/linux/mm.h | 1 include/linux/vcache.h | 26 --- kernel/futex.c | 368 +++++++++++++++++++++++++------------------------ mm/Makefile | 2 mm/fremap.c | 9 + mm/memory.c | 2 mm/vcache.c | 90 ----------- 7 files changed, 200 insertions(+), 298 deletions(-)
Patch name: futex-fixes-2.6.0-test4-01jl
This patch changes the way futexes are indexed, so that they do not pin pages and also corrects some problems with private mappings and COW pages.
Currently, all futexes look up the page at the userspace address and pin it, using the pair (page,offset) as an index into a table of waiting futexes. Any page with a futex waiting on it remains pinned in RAM, which is a problem when many futexes are used, especially with FUTEX_FD.
Another problem is that the page is not always the correct one, if it can be changed later by a COW (copy on write) operation. This can happen when waiting on a futex without writing to it after fork(), exec() or mmap(), if the page is then written to before attempting to wake a futex at the same adress.
There are two symptoms of the COW problem: 1. The wrong process can receive wakeups; 2. A process can fail to receive required wakeups.
This patch fixes both by changing the indexing so that VM_SHARED mappings use the triple (inode,offset,index), and private mappings use the pair (mm,virtual_address).
The former correctly handles all shared mappings, including tmpfs and therefore all kinds of shared memory (IPC shm, /dev/shm and MAP_ANON|MAP_SHARED). This works because every mapping which is VM_SHARED has an associated non-zero vma->vm_file, and hence inode. (This is ensured in do_mmap_pgoff, where it calls shmem_zero_setup).
The latter handles all private mappings, both files and anonymous. It isn't affected by COW, because it doesn't care about the actual pages, just the virtual address.
The only obvious problem is that mremap() can move a private mapping without informing futexes waiting on that mapping. However, mremap() was already broken with futexes, because it doesn't update the vcache, which is used by futexes, so this just changes an existing bug.
(A later patch from me will fix this problem with mremap(), by moving the futexes).
This patch has a few bonuses:
1. It removes the vcache implementation, as only futexes were using it, and they don't any more.
2. Removing the vcache should make COW page faults a bit faster.
3. Futex operations no longer take the page table lock, walk the page table, fault in pages that aren't mapped in the page table, or do a vcache hash lookup - they are mostly a simple offset calculation with one hash for the futex table. So they should be noticably faster.
4. The patch reduces the kernel size by 98 lines.
-- Jamie
==========================
include/linux/mm.h +1 -0
@@ -110,6 +110,7 @@#define VM_RESERVED 0x00080000/* Don't unmap it from swap_out */ #define VM_ACCOUNT 0x00100000/* Is a VM accounted object */ #define VM_HUGETLB 0x00400000/* Huge TLB Page VM */ +#define VM_NONLINEAR 0x00800000/* Is non-linear (remap_file_pages) */ #ifndef VM_STACK_DEFAULT_FLAGS /* arch can override this */ #define VM_STACK_DEFAULT_FLAGS VM_DATA_DEFAULT_FLAGS
include/linux/vcache.h +0 -26
@@ -1,26 +0,0 @@ -/* -* virtual => physical mapping cache support. -*/ -#ifndef _LINUX_VCACHE_H -#define _LINUX_VCACHE_H - -typedef struct vcache_s { -unsigned long address; -struct mm_struct *mm; -struct list_head hash_entry; -void (*callback)(struct vcache_s *data,struct page *new_page); -}vcache_t ; - -extern spinlock_t vcache_lock; - -extern void __attach_vcache (vcache_t *vcache, -unsigned long address, -struct mm_struct *mm, -void (*callback)(struct vcache_s *data,struct page *new_page)); - -extern void __detach_vcache (vcache_t *vcache); - -extern void invalidate_vcache (unsigned long address,struct mm_struct *mm, -struct page *new_page); - -#endif
kernel/futex.c +190 -178
566 lines not on this page · raw message
mm/fremap.c +8 -1
@@ -151,9 +151,16 @@if (vma && (vma->vm_flags &VM_SHARED ) && vma->vm_ops && vma->vm_ops->populate && end > start && start >= vma->vm_start && - end <= vma->vm_end) + end <= vma->vm_end) { + +if (start != vma->vm_start || end != vma->vm_end) + vma->vm_flags |=VM_NONLINEAR ; +else + vma->vm_flags &= ~VM_NONLINEAR ; + err = vma->vm_ops->populate (vma, start, size, vma->vm_page_prot, pgoff, flags &MAP_NONBLOCK ); + }up_read (&mm->mmap_sem);
mm/Makefile +1 -1
@@ -9,6 +9,6 @@ obj-y := bootmem.o filemap.o mempool.o oom_kill.o fadvise.o \ page_alloc.o page-writeback.o pdflush.o readahead.o \ - slab.o swap.o truncate.o vcache.o vmscan.o $(mmu-y) + slab.o swap.o truncate.o vmscan.o $(mmu-y) obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o
mm/memory.c +0 -2
@@ -43,7 +43,6 @@#include <linux/swap.h> #include <linux/highmem.h> #include <linux/pagemap.h> -#include <linux/vcache.h> #include <linux/rmap-locking.h> #include <asm/pgalloc.h>
@@ -960,7 +959,6 @@static inline void break_cow (struct vm_area_struct * vma,struct page * new_page,unsigned long address,pte_t *page_table) { -invalidate_vcache (address, vma->vm_mm, new_page);flush_cache_page (vma, address);establish_pte (vma, address, page_table,pte_mkwrite (pte_mkdirty (mk_pte (new_page, vma->vm_page_prot)))); }
mm/vcache.c +0 -90
90 lines not on this page · raw message
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 2 lines · Jamie Lokier
You will be please to know I have written a complete patch :)
Me too, well, mine wasn't quite complete yet, so I'll switch to reviewing yours later instead. I've not glanced at it so far, but what you've said about it leaves no doubt that you got my point.
Quoted 2 lines
That way, there is no need to walk the page table at all unless it's a non-linear mapping (which my patch does handle).
Gosh, I thought it was just a bit of one-up-man-ship from Andrew, futex on non-linear! I doubt anyone really cares about that case.
Quoted 2 lines
Good question. No kernel code seems to check
VM_MAYSHARE- the one to check isVM_SHARED.
No, it should be VM_MAYSHARE (if the behaviour is to depend on whether user said MAP_SHARED or not: which is a good starting point, but if odd readonly compatibility issues force us away from that position, perhaps VM_MAYSHARE won't in the end be the right test).
I agree it's peculiar, I agree (search LKML archives for VM_MAYSHARE) that again and again I'm having to make the distinction (I can't pretend to explain it, just indicate it), which strongly suggests it should be done better. But that's some other patch, some other time, for now use VM_MAYSHARE.
Observe fs/procfs/task_mmu.c show_map checking VM_MAYSHARE for 's'. Observe mm/mmap.c do_mmap_pgoff vm_flags &= ~(VM_MAYWRITE | VM_SHARED). VM_MAYSHARE reflects whether user chose MAP_SHARED, VM_SHARED may not.
Quoted 1 line
I added a flag
VM_NONLINEARto distinguish them.
Yes, I had that flag removed while it served no purpose, but I'm happy to have it back once it's useful for efficiency.
Quoted 2 lines
I have an obvious fix for
mremap(): rehash all the futexes in its range. That's not in the attached patch, but it will be in the next one.
Will it be worth the code added to handle it? I wonder the same of non-linear (sys_mremap and sys_remap_file_pages, familiar troublemakers). But all credit for handling them, good to reduce "undefined behaviour"s.
Hugh
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Hugh Dickins
Will it be worth the code added to handle it? I wonder the same of non-linear (
sys_mremapandsys_remap_file_pages, familiar troublemakers). But all credit for handling them, good to reduce "undefined behaviour"s.
I dismissed remap_file_pages the same as you at first, but since Andrew mentioned it, I think it's a fair point. As long as it's there, programmers should get the natural behaviour from it.
Databases (tdb I think) use futexes in database files, and remap_file_pages is used to look at different views of database files, and for huge files, so... It seems reasonable. That's quite an easy bit of code anyway. The futexes nicely stay persistent even when their particular offset into the file isn't mapped.
mremap() is used for moving anonymous data structures around mainly. Applications don't really need to depend on the futexes moving in that, but it is what the current implementation does so they might exist by now. The code for this is less defensible as it is more complicated.
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Hugh DickinsQuoted 6 lines · Hugh Dickins
Quoted 2 lines
Good question. No kernel code seems to check
VM_MAYSHARE- the one to check isVM_SHARED.Observe
fs/procfs/task_mmu.cshow_mapcheckingVM_MAYSHAREfor 's'. Observemm/mmap.cdo_mmap_pgoffvm_flags&= ~(VM_MAYWRITE |VM_SHARED).VM_MAYSHAREreflects whether user choseMAP_SHARED,VM_SHAREDmay not.
Hugh, thank you. In the case of futex.c, either flag could be used to mean "is this a shared" mapping, and each choice has a different user-visible meaning.
Most of the VM code uses VM_SHARED to ask the question "is this a shared mapping", but it turns out that most of the VM code means something different by that than what is meant in userspace. To the VM code, a "shared mapping" means something which can dirty backing-file pages, either after mmap() or maybe mprotect() as well.
This is different to the userspace point of view. The common language is unfortunate. (IMHO the flag should be called VM_SHAREDWRITABLE).
With futex.c using VM_SHARED to determine whether to hash on (inode,offset,index), mappings of read-only file handles will hash on (mm,uaddr) which is not correct: a FUTEX_WAIT on a shared mapping using userspace's meaning of "shared mapping" should notice changes in a different mm.
Therefore, futex.c will use VM_MAYSHARE in my next patch.
Thanks,
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Jamie Lokier
Quoted 3 lines · Hugh Dickins
Quoted 2 lines
Good question. No kernel code seems to check
VM_MAYSHARE- the one to check isVM_SHARED.
Quoted 7 lines
Quoted 3 lines
Observe
fs/procfs/task_mmu.cshow_mapcheckingVM_MAYSHAREfor 's'. Observemm/mmap.cdo_mmap_pgoffvm_flags&= ~(VM_MAYWRITE |VM_SHARED).VM_MAYSHAREreflects whether user choseMAP_SHARED,VM_SHAREDmay not.Hugh, thank you. In the case of
futex.c, either flag could be used to mean "is this a shared" mapping, and each choice has a different user-visible meaning.
Actually: the VM_SHARED flag will never change, so testing VM_SHARED is actually the _right_ thing from a mm perspective.
The only person who should ever test VM_MAYSHARE is somebody who does reporting back to user space: VM_MAYSHARE basically ends up meaning "the user _asked_ for a shared mapping". While "VM_SHARED" means "this mapping can actually contain a shared dirty page".
The VM itself should only ever care about VM_SHARED. Because that's the only bit that has real semantic meaning.
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 11 lines · Linus Torvalds
Actually: the
VM_SHAREDflag will never change, so testingVM_SHAREDis actually the _right_ thing from a mm perspective.The only person who should ever test
VM_MAYSHAREis somebody who does reporting back to user space:VM_MAYSHAREbasically ends up meaning "the user _asked_ for a shared mapping". While "VM_SHARED" means "this mapping can actually contain a shared dirty page".The VM itself should only ever care about
VM_SHARED. Because that's the only bit that has real semantic meaning.
To that part of the kernel interested in dirty pages, yes. But when interested in futexes, it seems not.
If we're going to document a behaviour as depending on whether the user said MAP_SHARED or MAP_PRIVATE, then it's VM_MAYSHARE we should check to decide which behaviour to use.
We could use VM_SHARED, and document the behaviour of the futex as depending on whether it's in an area that was MAP_SHARED from a file which was opened for writing as well as reading - but do we really
want to complicate the documentation that way? Principle of least
least surprise, principle of minimal doc.
Hugh
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 6 lines · Hugh Dickins
Quoted 3 lines
The VM itself should only ever care about
VM_SHARED. Because that's the only bit that has real semantic meaning.To that part of the kernel interested in dirty pages, yes. But when interested in futexes, it seems not.
I don't like it.
If the patches can't be made to work for private mappings, then there's something fundamentally wrong with them.
A non-writable shared mapping has degenerated into a private mapping since the very first releases of Linux that supported mmap. It started out as a "hey, we don't support true writable shared mappings, but we _do_ support cache coherency on read-only mmaps through the normal private mappings, so..".
And even later on, when true shared mappings were supported, we continued the "degenerate to a private mapping" approach because the private mappings tend to be simpler and require less overhead (exactly because they don't need to worry about dirty bits).
So part of the picture is that this is just how the Linux VM fundamentally works.
The other part of the picture is that futex'es should "just work" even when it comes to regular private mappings. Regardless of any VM_SHARED or VM_MAYSHARE bits. Even if the user did a totally private mmap() in the first place, that does not mean that the futex shouldn't work properly.
So the thing boils down to:
- if the futex works on a proper private mapping, then the downgrade is still proper, and the futex should never care about anything but a real VM_SHARED.
- if the futex doesn't work with a proper private mapping, then that is a bug _regardless_ of anything else, and VM_SHARED vs VM_MAYSHARE never enters into the picture anyway.
What?
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Linus Torvalds
If the patches can't be made to work for private mappings, then there's something fundamentally wrong with them.
Of course (not). That's the point, they do work on private mappings, but the semantics are different on private mappings from on shared mappings:
on private mappings they're private to the mm, on shared mappings they're shared with other mms (via the shared file).
Quoted 5 lines
So the thing boils down to:
- if the futex works on a proper private mapping, then the downgrade is still proper, and the futex should never care about anything but a real
VM_SHARED.
In the usual mm case, yes, deciding by VM_SHARED and ignoring VM_MAYSHARE turns out to be the right thing to do.
But a futex differs from the usual mm case, that much was clear when they were invented, but we're still discovering just how they are.
As I've said before, I haven't a clue about the user/glibc end of futexes, and for all I know a futex on a shared-readonly-cannot-be- mprotected-for-writing mapping cannot be used as a futex. If that's so, then perhaps we should simply prohibit sys_futex on such an area, and settle this dispute in that way. Is that the case?
Hugh
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Hugh Dickins
Of course (not). That's the point, they do work on private mappings, but the semantics are different on private mappings from on shared mappings:
on private mappings they're private to the mm, on shared mappings they're shared with other mms (via the shared file).
That's not true. It never has been true in Linux.
Private mappings that haven't been broken by COW (and a read-only mapping never will be) will see updates as they happen on the file that backs it. That's the fundamental difference between "mmap(MAP_PRIVATE)" and "read()".
You may not like it, and others too have not liked it (Hurd and Mach do this big dance about MAP_COPY that really creates a static _copy_ of the state at the time of the mmap), but it's just a fact.
Repeat after me: private read-only mappings are 100% equivalent to shared read-only mappings. No ifs, buts, or maybes. This is a FACT. It's a fact codified in many years of Linux implementation, but it's a fact outside of that too.
(Yeah, yeah, I know some broken old Unixes do not offer mmap consistency guarantees, and nntpd is unhappy. But Linux isn't broken.)
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 9 lines · Linus Torvalds
Quoted 5 lines · Hugh Dickins
Of course (not). That's the point, they do work on private mappings, but the semantics are different on private mappings from on shared mappings:
on private mappings they're private to the mm, on shared mappings they're shared with other mms (via the shared file).That's not true. It never has been true in Linux.
Quoted 8 lines
Private mappings that haven't been broken by COW (and a read-only mapping never will be) will see updates as they happen on the file that backs it. That's the fundamental difference between "
mmap(MAP_PRIVATE)" and "read()".You may not like it, and others too have not liked it (Hurd and Mach do this big dance about
MAP_COPYthat really creates a static _copy_ of the state at the time of the mmap), but it's just a fact.
I like the way Linux does that fine, it's the right way. We have a misunderstanding. You're talking about the behaviour of mmaps, I was talking about the behaviour of futexes placed within mmaps.
I'm not sure whether you've read this thread from the beginning, Jamie started CCing you today. The background is that Rusty's been working on unpinning futex pages, Jamie discovered inconsistency with current futex COW behaviour, that pushed me into realizing that the whole physical-page-based futex implementation has been misguided (adding more problems than it solves), Jamie has now made a patch to implement sys_futex the simpler way, we're discussing the test to distinguish a "private futex" from a "shared futex".
Quoted 4 lines
Repeat after me: private read-only mappings are 100% equivalent to shared read-only mappings. No ifs, buts, or maybes. This is a FACT. It's a fact codified in many years of Linux implementation, but it's a fact outside of that too.
Maybe, but, if the file was opened for writing as well as reading, the shared read-only mapping can be mprotected to read-write at any point, which does lead to differences: which is why Linux is very careful about deciding VM_SHARED, and it's quite difficult to explain.
If we document how sys_futex (which does not dirty a page, doesn't even need a page there) behaves when placed within different kinds of mmaps, it's easier for the reader to understand if we don't get into such sophistications - hence choice of VM_MAYSHARE equivalent to MAP_SHARED, never mind the readwriteness.
We'd both do better to be reading Jamie's patch.
Hugh
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Hugh Dickins
Maybe, but, if the file was opened for writing as well as reading, the shared read-only mapping can be mprotected to read-write at any point, which does lead to differences: which is why Linux is very careful about deciding
VM_SHARED, and it's quite difficult to explain.
And that's why the kernel does this:
case MAP_SHARED: .... vm_flags |= VM_SHARED | VM_MAYSHARE; if (!(file->f_mode & FMODE_WRITE)) vm_flags &= ~(VM_MAYWRITE | VM_SHARED); ...
ie it only degenerates the shared mapping to a private mapping if it _also_ removes the MAYWRITE bit.
So if the mapping is a shared mapping and read-only - but the file was opened read-write and the mapping may later be changed to a writable one - then Linux will keep the mapping VM_SHARED.
Quoted 5 lines
If we document how
sys_futex(which does not dirty a page, doesn't even need a page there) behaves when placed within different kinds of mmaps, it's easier for the reader to understand if we don't get into such sophistications - hence choice ofVM_MAYSHAREequivalent toMAP_SHARED, never mind the readwriteness.
I'd be very very nervous about anything that documents a read-only MAP_SHARED as anythign but a MAP_PRIVATE. That just is fundamentally not right, and it _will_ bite us at some point, since all of the rest of the VM thinks that they are the same.
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Linus TorvaldsIn message <[email protected]> you write:
Quoted 4 lines
Private mappings that haven't been broken by COW (and a read-only mapping never will be) will see updates as they happen on the file that backs it. That's the fundamental difference between "
mmap(MAP_PRIVATE)" and "read()".
Right, so it would be consistent for someone doing a FUTEX_WAIT on an "intact" (not broken by COW) private mapping to see a FUTEX_WAKE done on that file.
However, Jamie's futex code will see !VM_SHARED on the mapping, and compare futexes by mm + uaddr (rather than inode + file offset), so this is NOT the case. Using VM_MAYSHARE instead would make the MAP_SHARED readonly case work as above, though.
The way futexes are used now, they're both "don't care". If you have a private mapping or read-only mapping, you'll never get woken by others with the same file mapped writable shared, but WTF were you waiting for a futex if the mapping is private anyway: the lock acquisition won't work (and sleeping forever is easier to debug than two tasks getting the lock).
Oh no, I think I'm starting to understand the VM a little.
Ick.
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Rusty Russell
However, Jamie's futex code will see !VM_SHARED on the mapping, and compare futexes by mm + uaddr (rather than inode + file offset), so this is NOT the case. Using
VM_MAYSHAREinstead would make theMAP_SHAREDreadonly case work as above, though.
But that is WORSE!
Now MAP_SHARED works, but MAP_PRIVATE does not. That's still the same bug, but now it' san inconsistent bug!
I'd rather have a consistent bug than one that makes no sense.
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 7 lines · Linus Torvalds
Quoted 5 lines · Rusty Russell
However, Jamie's futex code will see !VM_SHARED on the mapping, and compare futexes by mm + uaddr (rather than inode + file offset), so this is NOT the case. Using
VM_MAYSHAREinstead would make theMAP_SHAREDreadonly case work as above, though.
Quoted 6 lines
But that is WORSE!
Now
MAP_SHAREDworks, butMAP_PRIVATEdoes not. That's still the same bug, but now it' san inconsistent bug!I'd rather have a consistent bug than one that makes no sense.
Aren't we arguing back and forth about a totally pointless case?
I've at last read the futex manpages and looked at Rusty's futex-2.2, to repair my understanding of the userspace end.
Isn't it the case that to use sys_futex (in the way it's intended), userspace needs write access to the futex? FUTEX_WAIT and FUTEX_WAKE are used (depending on condition) after decrementing or incrementing the futex in userspace. FUTEX_FD is not such a clear case, but again it appears that you'd use it for an async wait after decrementing. FUTEX_REQUEUE seems to be a move or remap, doesn't change the picture.
So, isn't discussing sys_futex behaviour on a readonly mapping just academic? I'd like us to define that behaviour precisely by returning -EACCES if sys_futex is attempted on a !VM_WRITE mapping, but it's not worth arguing over. And it doesn't matter whether Jamie tests VM_MAYSHARE (as I argued) or VM_SHARED (as you insist): they're set or clear together on all the writable mappings.
The particular case above: if it's !PROT_WRITE MAP_PRIVATE, I'm saying that's not an area you can manipulate mutexes in anyway; if it's PROT_WRITE MAP_PRIVATE but the page readonly while shared with parent, child or sibling, the prior decrement or increment on the futex in userspace will break COW, so it's private to the mm by the time sys_futex WAIT or WAKE is called, in either the old or the new implementation.
(But you can construct fork-with-futex examples in which the old implementation would share private futex between parent and child, because no write after fork to break the COW.)
Hugh
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 7 lines · Hugh Dickins
Isn't it the case that to use
sys_futex(in the way it's intended), userspace needs write access to the futex?FUTEX_WAITandFUTEX_WAKEare used (depending on condition) after decrementing or incrementing the futex in userspace.FUTEX_FDis not such a clear case, but again it appears that you'd use it for an async wait after decrementing.FUTEX_REQUEUEseems to be a move or remap, doesn't change the picture.
Yes.
We can certainly just document it as a nonsense op. All I care about is that it is _consistently_ broken, and that people don't make read-only MAP_SHARED do something it has never ever done before - differ from a semantic standpoint.
Quoted 2 lines
The particular case above: if it's !PROT_WRITE
MAP_PRIVATE, I'm saying that's not an area you can manipulate mutexes in anyway;
However, the thing is, the case really can be a totally writable MAP_PRIVATE that just hasn't been modified (and thus not COW'ed) _yet_.
But sure, we could just require that futex pages are dirty in this case.
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Linus Torvalds
However, the thing is, the case really can be a totally writable
MAP_PRIVATEthat just hasn't been modified (and thus not COW'ed) _yet_.But sure, we could just require that futex pages are dirty in this case.
There's no problem here in Jamie's implementation, no need to demand that; but the previous implementation did make COWing problems for itself, yes.
Hugh
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Linus TorvaldsQuoted 9 lines · Linus Torvalds
Quoted 4 lines
Of course (not). That's the point, they do work on private mappings, but the semantics are different on private mappings from on shared mappings:
on private mappings they're private to the mm, on shared mappings they're shared with other mms (via the shared file).Repeat after me: private read-only mappings are 100% equivalent to shared read-only mappings. No ifs, buts, or maybes. This is a FACT. It's a fact codified in many years of Linux implementation, but it's a fact outside of that too.
Thanks Linus. I already knew this, I was in the audience of the old thread about MAP_COPY, remember? :)
Please read below and think about it, because I'm convinced from your 3 emails later in this thread that you haven't thought about how COW should interact with futexes.
If you don't have time, skip to the last paragraph.
The new futexes key off (mm,address) for a private mapping, and (file,offset) for a shared mapping. That is actually a user-visible distinction, so I have to explain and justify it.
Private writable mapping: futex must be mm-local, obviously. This is a bug in the old futex code, which could be fixed as you say by forcibly COWing the page. But that's unnecessary: (mm,address) is fine.
Shared writable mapping: futex must be shared, obviously.
Read-only mapping: as yous say, private and shared are the same for a read-only mapping, until you call mprotect() if you're permitted. Anything which breaks that is wrong.
So what shall a futex do on a read-only mapping. First, does it even make sense? A: Yes it does. If I hand you a scoreboard file and tell you to wait for changes to words in it, it's a legitimate use of futexes on a read-only mapping.
Ok, now we understand that _this_ read-only mapping should not be mm-local.
But Linux does something weird at this point, if the new futex code's hash keys on VM_SHARED.
If I hand you a scoreboard file opened O_RDWR, your futexes are keyed on file pages. But if I open it O_RDONLY, your futexes are mm-local.
* I contend that the user-visible behaviour of a mapping should
* _not_ depend on whether the file was opened with O_RDWR or O_RDONLY.
Thanks,
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Jamie Lokier
* I contend that the user-visible behaviour of a mapping should
* _not_ depend on whether the file was opened withO_RDWRorO_RDONLY.
And I violently agree. But I also add the _other_ requirement:
* I contend that user-visible behaviour of a mapping should be 100% the
* same for a unwritable MAP_SHARED and a unwritten MAP_PRIVATE
Put the two together, and see what you get. You get the requirement that if MAP_SHARED works, then MAP_PRIVATE also has to work.
That's my requirement. Consistency.
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 10 lines · Linus Torvalds
Quoted 2 lines
* I contend that the user-visible behaviour of a mapping should
* _not_ depend on whether the file was opened withO_RDWRorO_RDONLY.And I violently agree. But I also add the _other_ requirement:
* I contend that user-visible behaviour of a mapping should be 100% the
* same for a unwritableMAP_SHAREDand a unwrittenMAP_PRIVATEPut the two together, and see what you get. You get the requirement that if
MAP_SHAREDworks, thenMAP_PRIVATEalso has to work.
I'll add three more conditions to be explicit:
* A futex on a MAP_PRIVATE must be mm-local: the canonical
* example being MAP_PRIVATE of /dev/zero.
* A FUTEX_WAIT on an unwritten mapping should be woken by a
* FUTEX_WAKE to the same address after writing.
* A FUTEX_WAIT on a read-only mapping should wait for the same
* thing from other processes as if it were a writable mapping.
Quoted 1 line
That's my requirement. Consistency.
Unfortunately I think the above 5 conditions do not have a consistent solution. Please prove me wrong :)
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Jamie Lokier
* A futex on a
MAP_PRIVATEmust be mm-local: the canonical
* example beingMAP_PRIVATEof/dev/zero.
Actually, /dev/zero is a special case in itself. It is an anonymous mapping, and is equivalent to MAP_ANON for private mappings. For MAP_SHARED it is something _totally_ different.
So /dev/zero isn't even an interesting case.
Quoted 2 lines
Unfortunately I think the above 5 conditions do not have a consistent solution. Please prove me wrong :)
I don't think there is any inconsistency.
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 6 lines · Linus Torvalds
Quoted 2 lines
* A futex on a
MAP_PRIVATEmust be mm-local: the canonical
* example beingMAP_PRIVATEof/dev/zero.Actually,
/dev/zerois a special case in itself. It is an anonymous mapping, and is equivalent toMAP_ANONfor private mappings. ForMAP_SHAREDit is something _totally_ different.
Well yes, but conceptually it's behaviour is that of a private mapping of a file-like object. But fine, let's not get sidetracked by /dev/zero.
I'll restate it:
* A futex on a MAP_PRIVATE must be mm-local. The canonical example being the data section of your executable.
Quoted 4 lines
Quoted 2 lines
Unfortunately I think the above 5 conditions do not have a consistent solution. Please prove me wrong :)
I don't think there is any inconsistency.
I can't think of a behaviour which satisfies all 5 conditions, so you'll have to help me out. :/
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Linus TorvaldsQuoted 2 lines · Linus Torvalds
Actually: the
VM_SHAREDflag will never change, so testingVM_SHAREDis actually the _right_ thing from a mm perspective.
Yes it can. See sys_mprotect(). If that's not intended, it's a bug in mprotect(). What does PROT_SEM mean for Linux, btw?
See:
if (prot & ~(PROT_READ | PROT_WRITE | PROT_EXEC | PROT_SEM)) return -EINVAL;
and:
newflags = prot | (vma->vm_flags & ~(PROT_READ | PROT_WRITE | PROT_EXEC));
if ((newflags & ~(newflags >> 4)) & 0xf) {
error = -EACCES;
goto out;
}newflags is than used to index protection_map[], like this:
newprot = protection_map[newflags & 0xf];
and that is stored in the page tables.
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Jamie Lokier
Yes it can. See
sys_mprotect(). If that's not intended, it's a bug inmprotect().
Oh. I see. Yes - it's accessing "vm_flags" with "MAP_SEM". That's really wrong, since it's not even the same _domain_.
"vm_flags" should use the "VM_xxxx" bits. Trying to use "PROT_xxx" bits is totally improper, but it so happens that the low three bits (READ|WRITE|EXEC) are supposed to be the same.
Good catch.
It really should do what mmap() does, and translate from the "PROT_xxx" domain to the "VM_xxx" domain:
flag = _trans(prot, PROT_READ, VM_READ) |
_trans(prot, PROT_WRITE, VM_WRITE) | _trans(prot, PROT_EXEC, VM_EXEC);
and the only reason sys_mprotect _looks_ like it is working is that those three bits (but _not_ MAP_SEM) happen to be the same anyway.
I'm inclined to be lazy, and say "we know the low three bits of "prot" and "flags" are the same, and leave it as-is, but remove the MAP_SEM, which clearly is a bug.
But the proper thing is to move that part of calc_vm_flags() to a header file. Does anybody want to take that on?
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Linus Torvalds
Oh. I see. Yes - it's accessing "
vm_flags" with "MAP_SEM". That's really wrong, since it's not even the same _domain_.
How about something like this that at least gets it closer? It fixes the fact that incorrect usage of PROT_SEM would allow users to set the VM_SHARED bit behind the back of the OS, which sounds like a total disaster and which can potentially confuse other parts of the VM.
It's not a very _pretty_ fix, but there really is no excuse for PROT_xxx to not match VM_xxx for the three standard protection flags, so in that sense it is the technically "sane" approach. We might want to just simplify the mmap() code too..
Linus
Re: [PATCH] Alternate futex non-page-pinning and COW fix
[ Oops. Forgot the actual patch. ]
Quoted 2 lines · Linus Torvalds
How about something like this [ ... ]
THIS.
Linus
===== mm/mprotect.c 1.23 vs edited =====
mm/mprotect.c +8 -2
@@ -224,7 +224,7 @@asmlinkage long sys_mprotect (unsigned long start,size_t len,unsigned long prot) { -unsigned long nstart, end, tmp; +unsigned long flags, nstart, end, tmp;struct vm_area_struct * vma, * next, * prev;int error = -EINVAL ;
@@ -239,6 +239,12 @@if (end == start)return 0 ; +/* +* FIXME! This assumes that PROT_xxx == VM_xxxx for READ, WRITE, EXEC +* That does happen to be true, but it's ugly.. mmap() gets this right. +*/ + flags = prot & (VM_READ |VM_WRITE |VM_EXEC ); +down_write (¤t->mm->mmap_sem); vma =find_vma_prev (current->mm, start, &prev);
@@ -257,7 +263,7 @@ goto out; } - newflags = prot | (vma->vm_flags & ~(PROT_READ |PROT_WRITE |PROT_EXEC )); + newflags = flags | (vma->vm_flags & ~(VM_READ |VM_WRITE |VM_EXEC ));if ((newflags & ~(newflags >>4 )) &0xf ) { error = -EACCES ; goto out;
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Jamie LokierIn message <[email protected]> you write:
Quoted 1 line
What does
PROT_SEMmean for Linux, btw?
It's a relic: some archs might need a special flag to ensure inter-process atomic ops worked as expected. It was never fully implemented, with the assumption that such archs just won't be able to use futexes, and if someone really wants to fix it, they will.
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Rusty Russell
In message <[email protected]> you write:
Quoted 1 line
What does
PROT_SEMmean for Linux, btw?It's a relic: some archs might need a special flag to ensure inter-process atomic ops worked as expected. It was never fully
~~~~~~~~~~~
Quoted 1 line
implemented, with the assumption that such archs just won't be able to
~~~~~~~~~~~
Quoted 1 line
use futexes, and if someone really wants to fix it, they will.
Looking at the kernel I can confidently say it was never implemented at all. sys_mprotect mentioned PROT_SEM but it was a misleading logic error that did nothing useful :)
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Linus TorvaldsQuoted 4 lines · Linus Torvalds
The only person who should ever test
VM_MAYSHAREis somebody who does reporting back to user space:VM_MAYSHAREbasically ends up meaning "the user _asked_ for a shared mapping". While "VM_SHARED" means "this mapping can actually contain a shared dirty page".
Precisely. And for futex, the correct meaning is "the user asked for a shared mapping": a FUTEX_WAIT on a shared mapping of a file opened read-only _should_ be woken by a FUTEX_WAKE on the same file by another process.
Quoted 2 lines
The VM itself should only ever care about
VM_SHARED. Because that's the only bit that has real semantic meaning.
remap_file_pages() returns -EINVAL on mappings of read-only file handles because it tests VM_SHARED. There is no good reason not to remap a read-only file - it doesn't complain about remapping a PROT_READ mapping of a writable file!
Patch tested and attached.
Enjoy,
-- Jamie
Subject: [PATCH] Allow remap_file_pages() on read-only files
Patch: nonlinear-mayshare-2.6.0-test4-02.2jl
This changes remap_file_pages() to work on mappings of read-only file handles. Without this it returns -EINVAL.
mm/fremap.c +4 -3
@@ -145,10 +145,11 @@ vma =find_vma (mm, start);/* * Make sure the vma is shared, that it supports prefaulting, -* and that the remapped range is valid and fully within -* the single existing vma: +* and that the remapped range is valid and fully within the +* single existing vma. VM_MAYSHARE is checked (not VM_SHARED) +* so that read-only files can be remapped too: */ -if (vma && (vma->vm_flags &VM_SHARED ) && +if (vma && (vma->vm_flags &VM_MAYSHARE ) && vma->vm_ops && vma->vm_ops->populate && end > start && start >= vma->vm_start && end <= vma->vm_end)
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Hugh DickinsIn message <[email protected]> you write:
Quoted 7 lines · Jamie Lokier
Quoted 2 lines
I have an obvious fix for
mremap(): rehash all the futexes in its range. That's not in the attached patch, but it will be in the next one.Will it be worth the code added to handle it? I wonder the same of non-linear (
sys_mremapandsys_remap_file_pages, familiar troublemakers). But all credit for handling them, good to reduce "undefined behaviour"s.
I don't have a problem with the omission. mremap is logically equivalent to munmap + mmap, so it's a subset of the "I unmapped underneath my futex!". It's not like it's going to happen without the caller knowing: if the address doesn't change, then the futexes won't break. If they do, the caller needs to reset them anyway.
Cheers,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 5 lines · Rusty Russell
I don't have a problem with the omission. mremap is logically equivalent to munmap + mmap, so it's a subset of the "I unmapped underneath my futex!". It's not like it's going to happen without the caller knowing: if the address doesn't change, then the futexes won't break. If they do, the caller needs to reset them anyway.
I think mremap() on block of memory containing futexes is reasonable. Imagine a big data structure with a table futex locks at the start of it. I'm not sure how useful it is, but it's not worthless.
Anyway, I have a patch, tested, which moves remapped futexes _and_ returns EFAULT to waiters when pages are unmapped. It's kept separate from the main futex patch so you can accept it or not.
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In message <[email protected]> you write:
Quoted 10 lines
Quoted 5 lines · Rusty Russell
I don't have a problem with the omission. mremap is logically equivalent to munmap + mmap, so it's a subset of the "I unmapped underneath my futex!". It's not like it's going to happen without the caller knowing: if the address doesn't change, then the futexes won't break. If they do, the caller needs to reset them anyway.
I think
mremap()on block of memory containing futexes is reasonable. Imagine a big data structure with a table futex locks at the start of it. I'm not sure how useful it is, but it's not worthless.
Think about the code that does this:
struct futex_file
{
struct futex lock;
int content_len;
char contents[0];
};
fd = sys_futex(&futfile->lock);
...
futfile = mremap(futfile, oldsize, newsize, MREMAP_MAYMOVE);Now, if mremap doesn't move the memory, futexes aren't broken, even without your patch, right? If it does move, you've got a futex sitting in invalid memory, no surprise if it doesn't work.
OTOH, I'm interested in returning EFAULT on waiters when pages are unmapped, because I realized that stale waiters could "match" live futex wakeups (an mm_struct gets recycled), and steal the wakeup. Bad juju. We could do some uid check or something for anon pages, but cleaner to flush them at unmap.
Cheers!
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Rusty Russell
Now, if mremap doesn't move the memory, futexes aren't broken, even without your patch, right? If it does move, you've got a futex sitting in invalid memory, no surprise if it doesn't work.
If the mremap doesn't move the memory it's fine. No surprise :)
If it's moved, then the program isn't broken - it knows it just did an mremap, and it sends the wakeup to the new address.
This makes sense if async futexes are used on an in-memory private database. But such programs can just use MAP_ANON|MAP_SHARED if they want mremap to work.
Quoted 5 lines
OTOH, I'm interested in returning EFAULT on waiters when pages are unmapped, because I realized that stale waiters could "match" live futex wakeups (an
mm_structgets recycled), and steal the wakeup. Bad juju. We could do some uid check or something for anon pages, but cleaner to flush them at unmap.
Ah, you're right. Not fixing that is a serious bug.
It can happen when an async futex fd is passed to another process.
Not only can the mm_struct be recycled, it might be recycled into an inode so it could match a file futex too.
This can be fixed more simply than the full do_unmap patch I posted earlier, by invalidating all the futexes in an mm when it is destroyed.
Another fix would be to prevent futex fds of private mappings being passed to another process, somehow.
It must be fixed somehow.
Linus, which patch do you prefer? Invalidate all futexes in an mm when it's destroyed, or invalidate ranges in do_munmap?
-- Jamie
ps. There's another bug: shared waiters match inodes, which they don't hold a reference to. Inodes can be recycled too. Fix is easy: just need to take an inode reference.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In message <[email protected]> you write:
Quoted 5 lines
Quoted 3 lines · Rusty Russell
Now, if mremap doesn't move the memory, futexes aren't broken, even without your patch, right? If it does move, you've got a futex sitting in invalid memory, no surprise if it doesn't work.
Quoted 8 lines
If the mremap doesn't move the memory it's fine. No surprise :)
If it's moved, then the program isn't broken - it knows it just did an mremap, and it sends the wakeup to the new address.
This makes sense if async futexes are used on an in-memory private database. But such programs can just use MAP_ANON|MAP_SHARED if they want mremap to work.
wakeup is not a problem: from the kernel's POV, between wakeups the futex doesn't exist.
The only real case (ignoring the "one thread FUTEX_WAIT while the other mremaps underneath" which is gonna break anyway), is FUTEX_FD, I don't see a problem with having to manually move your futex fds in this case when the memory underneath them has been remapped. In fact, it'd be surprising if you didn't have to.
Quoted 9 lines
Quoted 2 lines
OTOH, I'm interested in returning EFAULT on waiters when pages are unmapped, because I realized that stale waiters could "match" live
Ah, you're right. Not fixing that is a serious bug.
It can happen when an async futex fd is passed to another process.ps. There's another bug: shared waiters match inodes, which they don't hold a reference to. Inodes can be recycled too. Fix is easy: just need to take an inode reference.
Yes. Invalidate is nice because it catches a programmer mistake. But why not solve the problem by just holding an mm reference, too?
Cheers,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 11 lines · Rusty Russell
In message <[email protected]> you write:
Quoted 10 lines
Quoted 3 lines · Rusty Russell
Now, if mremap doesn't move the memory, futexes aren't broken, even without your patch, right? If it does move, you've got a futex sitting in invalid memory, no surprise if it doesn't work.
If the mremap doesn't move the memory it's fine. No surprise :)
If it's moved, then the program isn't broken - it knows it just did an mremap, and it sends the wakeup to the new address.
Quoted 6 lines
Quoted 3 lines
This makes sense if async futexes are used on an in-memory private database. But such programs can just use MAP_ANON|MAP_SHARED if they want mremap to work.
The only real case (ignoring the "one thread
FUTEX_WAITwhile the other mremaps underneath" which is gonna break anyway), isFUTEX_FD,
By "async futex" I mean FUTEX_FD; sorry if that wasn't clear. By "sync futex" I mean FUTEX_WAIT.
Quoted 3 lines
I don't see a problem with having to manually move your futex fds in this case when the memory underneath them has been remapped. In fact, it'd be surprising if you didn't have to.
I don't see a problem, as long as it is documented. Anybody grokking the old futex code would expect futexes to move with mappings.
It's a mild surprise whatever behaviour, because:
- if it's a MAP_SHARED, then the program doesn't have to move futexes, and this is a good thing (think locks in a remap_file_pages database mapping).
- the old (page pinning) version moves FUTEX_FD futexes "automatically", in the sense that they're attached to the page which moves.
Quoted 2 lines
Yes. Invalidate is nice because it catches a programmer mistake. But why not solve the problem by just holding an mm reference, too?
That would work. An mm isn't that huge once everything's been unmapped by exit. Alternatively, mm-private futexes can be woken when the mm is destroyed.
I just implemented the latter, but come to think of it a reference to a dead mm is light enough not to bother with a list of "futexes attached to mm to destroy on exit".
So I'll throw that away and provide a patch which just takes a reference. (Also, takes inode references).
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In message <[email protected]> you write:
Quoted 2 lines
I don't see a problem, as long as it is documented. Anybody grokking the old futex code would expect futexes to move with mappings.
BTW, I don't know of anyone *doing* this, but IMHO it's not worth a single line of kernel code, since if you don't adjust your futex addresses when you mremap, the try_down_futex will segv after the poll or whatever. As a programmer, I would *expect* to have to reset the futexes (along with every other pointer into the map) when mremap
happens: after all, I told the kernel to watch the old address. If it still works, great, but I'd not expect it.
Quoted 7 lines
Quoted 2 lines
Yes. Invalidate is nice because it catches a programmer mistake. But why not solve the problem by just holding an mm reference, too?
That would work. An mm isn't that huge once everything's been unmapped by exit. Alternatively, mm-private futexes can be woken when the mm is destroyed.
Quoted 6 lines
I just implemented the latter, but come to think of it a reference to a dead mm is light enough not to bother with a list of "futexes attached to mm to destroy on exit".
So I'll throw that away and provide a patch which just takes a reference. (Also, takes inode references).
Agreed. You can get a page per 2 fds trivially anyway with pipes, so staying within that bound is fairly safe.
Cheers!
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 11 lines · Rusty Russell
In message <[email protected]> you write:
Quoted 2 lines
I don't see a problem, as long as it is documented. Anybody grokking the old futex code would expect futexes to move with mappings.
BTW, I don't know of anyone *doing* this, but IMHO it's not worth a single line of kernel code, since if you don't adjust your futex addresses when you mremap, the
try_down_futexwill segv after the poll or whatever. As a programmer, I would *expect* to have to reset the futexes (along with every other pointer into the map) when mremap
happens: after all, I told the kernel to watch the old address. If it still works, great, but I'd not expect it.
Sure. As long as it's documented, because my expectation is the opposite of yours :)
(Some uses of futex don't read the memory after they are woken, until they have re-tested some other condition and can recalculate the address, so segv and pointers-into-the-map don't occur in these uses).
-- Jamie
PATCH 1/1 Little fixes to previous futex patch
In reply to Jamie LokierPatch name: futex-nonlinear-2.6.0-test4-02jl
Depends on: futex-fixes-2.6.0-test4-01jl
This fixes a couple of bugs in the previous patch:
1. A typo in futex.c. It affects the FUTEX_REQUEUE operation, which is a fairly recent addition.
2. VM_NONLINEAR would not be set under some conditions when it should be. The bug only affected futexes on non-linear shared mappings.
Enjoy,
-- Jamie
kernel/futex.c +1 -1
@@ -224,7 +224,7 @@down_read (¤t->mm->mmap_sem); - ret =__get_page_keys (uaddr2 - offset1, keys1); + ret =__get_page_keys (uaddr1 - offset1, keys1);if (unlikely (ret !=0 )) goto out; ret =__get_page_keys (uaddr2 - offset2, keys2);
mm/fremap.c +3 -3
@@ -153,9 +153,9 @@ end > start && start >= vma->vm_start && end <= vma->vm_end) { -if (start != vma->vm_start || end != vma->vm_end) - vma->vm_flags |=VM_NONLINEAR ; -else + vma->vm_flags |=VM_NONLINEAR ; +if (start == vma->vm_start && end == vma->vm_end && + pgoff == vma->vm_pgoff) vma->vm_flags &= ~VM_NONLINEAR ; err = vma->vm_ops->populate(vma, start, size, vma->vm_page_prot,
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 2 lines · Jamie Lokier
Patch name: futex-nonlinear-2.6.0-test4-02jl
Depends on: futex-fixes-2.6.0-test4-01jl
I've now read your patches, they look good to me:
I particularly like the way you divided up the locking.
In sys_remap_file_pages, you set the VM_NONLINEAR flag, then clear it if this particular population matches the vma. No, you cannot clear that flag once set, without checking every page and pte_file already set within the vma. Check if population matches vma first, and if it doesn't match just set the VM_NONLINEAR flag in that case. (Andrew already mentioned locking: I'd have said page_table_lock, but his mmap_sem is also appropriate: it's an odd case.)
I think rip out the FIXADDR_USER_START bit, it's rather over-the-top,
ugly: and that area is readonly, so not a useful place for a futex.
The units of keys[1]: bytes if private but pages if shared. That's okay for now I think, but if a hashing expert comes along later s/he'll probably want to change it. The current hash does add key1 to offset, which is okay: if it xor'ed you'd lose the the offset bits in the private case.
Those keys[1] pages: in units of PAGE_SIZE in the linear case, of PAGE_CACHE_SIZE in the nonlinear case. Oh well, this is far from the only place with such an inconsistency, let's worry about that when never comes.
The err at the end of __get_page_keys would be 1 from successful get_user_pages, treated as error by the callers: need to make it 0.
futex_wait: I didn't get around to it in my version, so haven't thought through the issues, but I'm a bit worried that you get curval for -EWOULDBLOCK check without holding the futex_lock. That looks suspicious to me, but I'm going to be lazy and not try to think about it, because Rusty is sure to understand the races there. If that code is insufficient as you have it, may need __pin_page reinstated for just that case (hmm, was that get_user right before? I'd expect it to kmap_atomic pinned page.)
Hugh
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 7 lines · Hugh Dickins
In
sys_remap_file_pages, you set theVM_NONLINEARflag, then clear it if this particular population matches the vma. No, you cannot clear that flag once set, without checking every page andpte_filealready set within the vma. Check if population matches vma first, and if it doesn't match just set theVM_NONLINEARflag in that case. (Andrew already mentioned locking: I'd have saidpage_table_lock, but hismmap_semis also appropriate: it's an odd case.)
I don't see why you can't clear the flag: the call to ->populate will change every page and pte_file to correspond with the linear page offsets, which is all that !VM_NONLINEAR indicates.
However, it _is_ wrong to clear VM_NONLINEAR before the call to ->populate() has finished, with Andrew's patch which uses downgrade_write(). Instead, the clear must come after ->populate() has finished.
Quoted 2 lines
I think rip out the
FIXADDR_USER_STARTbit, it's rather over-the-top,
ugly: and that area is readonly, so not a useful place for a futex.
Agreed. I put it because the old futex has it as a side effect of get_user_pages(). It can go.
Quoted 5 lines
The units of keys[1]: bytes if private but pages if shared. That's okay for now I think, but if a hashing expert comes along later s/he'll probably want to change it. The current hash does add key1 to offset, which is okay: if it xor'ed you'd lose the the offset bits in the private case.
Feel free to think up a better hash that isn't slow. Two iterations of hash_long() would be a good hash, but slower.
Quoted 4 lines
Those keys[1] pages: in units of
PAGE_SIZEin the linear case, ofPAGE_CACHE_SIZEin the nonlinear case. Oh well, this is far from the only place with such an inconsistency, let's worry about that when never comes.
Ew.
Quoted 2 lines
The err at the end of
__get_page_keyswould be 1 from successfulget_user_pages, treated as error by the callers: need to make it 0.
Well spotted.
Quoted 8 lines
futex_wait: I didn't get around to it in my version, so haven't thought through the issues, but I'm a bit worried that you get curval for-EWOULDBLOCKcheck without holding thefutex_lock. That looks suspicious to me, but I'm going to be lazy and not try to think about it, because Rusty is sure to understand the races there. If that code is insufficient as you have it, may need__pin_pagereinstated for just that case (hmm, was thatget_userright before? I'd expect it tokmap_atomicpinned page.)
The important things are that the futex is queued prior to checking curval, the requested page won't change (it's protected by mmap_sem), and any parallel waker changes the word prior to waking us.
You made me notice a rather subtle memory ordering condition, though.
We must issue the read after queuing the futex. There needs to be a smp_rmb() after queuing and before the read, because the spin_unlock() barrier only constrains earlier reads, not later ones.
Thanks for all your great insights,
-- Jamie
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 4 lines · Jamie Lokier
I don't see why you can't clear the flag: the call to ->populate will change every page and
pte_fileto correspond with the linear page offsets, which is all that !VM_NONLINEAR indicates.
You're assuming that one call to sys_remap_file_pages precisely populates a whole vma: no, it's quite likely it'll just do a single page of the vma.
Quoted 3 lines
The important things are that the futex is queued prior to checking curval, the requested page won't change (it's protected by
mmap_sem), and any parallel waker changes the word prior to waking us.
Ah, that may well be so, it's beyond me,
just so long as Rusty is happy with it.
(I don't think you mean "the requested page won't change" - the down_read on mmap_sem does not prevent it from being swapped out before the get_user, but nor does it prevent a replacement page being faulted back in by get_user, and we no longer have any dependence on those being the same physical page.)
Hugh
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 6 lines · Hugh Dickins
Quoted 3 lines
I don't see why you can't clear the flag: the call to ->populate will change every page and
pte_fileto correspond with the linear page offsets, which is all that !VM_NONLINEAR indicates.You're assuming that one call to
sys_remap_file_pagesprecisely populates a whole vma: no, it's quite likely it'll just do a single page of the vma.
What are you talking about? The condition for clearing VM_NONLINEAR is an explicit check to see if the range to be populated covers the whole vma.
Quoted 6 lines
Quoted 3 lines
The important things are that the futex is queued prior to checking curval, the requested page won't change (it's protected by
mmap_sem), and any parallel waker changes the word prior to waking us.Ah, that may well be so, it's beyond me,
just so long as Rusty is happy with it.
If that condition isn't enough, then async futexes are in trouble, because the curval check equivalent is done in userspace for async futexes...
Quoted 5 lines
(I don't think you mean "the requested page won't change" - the
down_readonmmap_semdoes not prevent it from being swapped out before theget_user, but nor does it prevent a replacement page being faulted back in byget_user, and we no longer have any dependence on those being the same physical page.)
I mean it prevents the futex key corresponding to the userspace word from changing before we read the word. For all reasonable uses this doesn't matter anyway.
-- Jamie
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 8 lines · Jamie Lokier
Quoted 3 lines · Hugh Dickins
You're assuming that one call to
sys_remap_file_pagesprecisely populates a whole vma: no, it's quite likely it'll just do a single page of the vma.What are you talking about? The condition for clearing
VM_NONLINEARis an explicit check to see if the range to be populated covers the whole vma.
I apologize, I'm just not reading, am I? Thanks for re-explaining.
You're right, the condition on clearing is fine. It's the (lack of condition on) setting that's over-enthusiastic, should be saying:
if (start - vma->vm_start != (pgoff - vma->vm_pgoff) << PAGE_SHIFT) vma->vm_flags |= VM_NONLINEAR;
(Unless I'm making a fool of myself again.)
Hugh
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 5 lines · Hugh Dickins
You're right, the condition on clearing is fine. It's the (lack of condition on) setting that's over-enthusiastic, should be saying:
if (start - vma->vm_start != (pgoff - vma->vm_pgoff) << PAGE_SHIFT) vma->vm_flags |= VM_NONLINEAR;
I hadn't thought of that.
I wonder if it's useful, though. The only time it's likely to not set the flag with it not already set, in real use, is when other VM code calls remap_file_pages() with the whole vma. But then the flag is cleared by the next line.
So it's correct and nice, but I'm not sure it adds anything practical.
-- Jamie
Ingo Molnar
maintainerRe: [PATCH 2] Little fixes to previous futex patch
In reply to Hugh Dickinsbtw., regarding this fix:
[email protected], 2003-09-06 12:28:20-07:00, [email protected]
[PATCH] Fix futex hashing bugs
why dont we do this:
} else {
/* Make sure to stop if key1 == key2 */
if (head1 == head2)
break;
list_add_tail(i, head2);
this->key = key2;
if (ret - nr_wake >= nr_requeue)
break;
}instead of the current:
} else {
list_add_tail(i, head2);
this->key = key2;
if (ret - nr_wake >= nr_requeue)
break;
/* Make sure to stop if key1 == key2 */
if (head1 == head2 && head1 != next)
head1 = i;
}what's the point in requeueing once, and then exiting the loop by changing the loop exit condition variable? You are trying to avoid the lockup but the first one ought to be the most straightforward way to do it.
Ingo
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 30 lines · Ingo Molnar
btw., regarding this fix:
[email protected], 2003-09-06 12:28:20-07:00, [email protected]
[PATCH] Fix futex hashing bugswhy dont we do this:
} else { /* Make sure to stop if key1 == key2 */ if (head1 == head2) break; list_add_tail(i, head2); this->key = key2; if (ret - nr_wake >= nr_requeue) break; }instead of the current:
} else { list_add_tail(i, head2); this->key = key2; if (ret - nr_wake >= nr_requeue) break; /* Make sure to stop if key1 == key2 */ if (head1 == head2 && head1 != next) head1 = i; }
Quoted 3 lines
what's the point in requeueing once, and then exiting the loop by changing the loop exit condition variable? You are trying to avoid the lockup but the first one ought to be the most straightforward way to do it.
I think you're reading it as a "list_for_each(i, head1)" loop, whereas it is and must be a "list_for_each_safe(i, next, head1)" loop.
So it won't (in general) terminate after this one requeueing (as list_for_each would, finding i->next == head1): termination depends on next (already set) and head1, so I repoint head1 to the first requeued.
So it should terminate after one pass down the list, when it reaches the first requeued, and can then return the appropriate "ret" count to user.
You may perhaps know that the ret count is not important, but I don't know that, so wanted to get it right. (At the time, I also wanted to have the list sorted exactly as intended, but now I can't see that the relative positions of different keys could matter at all.)
It may be bad practice to use a familiar macro like list_for_each_safe, yet play with its controlling variables within the loop. I just felt safer that way than expanding it, or adding extraneous variables.
Hugh
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 4 lines · Hugh Dickins
You may perhaps know that the ret count is not important, but I don't know that, so wanted to get it right. (At the time, I also wanted to have the list sorted exactly as intended, but now I can't see that the relative positions of different keys could matter at all.)
The position of different keys doesn't matter, but the relative position of identical keys does.
-- jamie
Re: [PATCH 2] Little fixes to previous futex patch
In reply to Hugh DickinsIn message <[email protected]> you write:
Quoted 9 lines · Ingo Molnar
Quoted 8 lines
btw., regarding this fix:
[email protected], 2003-09-06 12:28:20-07:00, [email protected]
[PATCH] Fix futex hashing bugswhy dont we do this:
Quoted 9 lines
Quoted 9 lines
} else { /* Make sure to stop if key1 == key2 */ if (head1 == head2) break; list_add_tail(i, head2); this->key = key2; if (ret - nr_wake >= nr_requeue) break; }
Why not make the code a *whole* lot more readable (and only marginally slower, if at all) by doing it in two passes: pull them off onto a (on-stack) list in one pass, then requeue them all in another.
This on top of Hugh's patch on top of Jamie's. Untested, but you get the idea...
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: FUTEX_REQUEUE simplyfication
Author: Rusty Russell
Status: Booted on 2.6.0-test4-bk9
Depends: Misc/futex-hugh.patch.gz
D: Simplify the logic of FUTEX_REQUEUE.
kernel/futex.c +15 -11
@@ -253,8 +253,10 @@ out:static int futex_requeue (unsigned long uaddr1,unsigned long uaddr2,int nr_wake,int nr_requeue) { -struct list_head *i, *next, *head1, *head2; +struct list_head *head1, *head2; +struct futex_q *this, *next;union futex_key key1, key2; +LIST_HEAD (moved);int ret;down_read (¤t->mm->mmap_sem);
@@ -270,27 +272,29 @@ static int futex_requeue(unsigned long u head2 =hash_futex (&key2);spin_lock (&futex_lock); -list_for_each_safe (i, next, head1) { - struct futex_q *this = list_entry(i, struct futex_q, list); - -if (match_futex (&this->key, &key1)) { -list_del_init (i); +list_for_each_entry_safe (this, next, head1, list) { +if (match_futex (&this->key, &key1)) {if (++ret <= nr_wake) { +list_del_init (&this->list);wake_up_all (&this->waiters);if (this->filp)send_sigio (&this->filp->f_owner, this->fd,POLL_IN ); }else { -list_add_tail (i, head2); - this->key = key2; +/* Dequeue. */ +list_del (&this->list); +list_add (&this->list, &moved);if (ret - nr_wake >= nr_requeue)break ; -/* Make sure to stop if key1 == key2 */ -if (head1 == head2 && head1 != next) - head1 = i; } } } + +/* Requeue */ +list_for_each_entry_safe (this, next, &moved, list) { +list_del (&this->list); +list_add_tail (&this->list, head2); + }spin_unlock (&futex_lock); out:
Re: [PATCH 2] Little fixes to previous futex patch
In reply to Ingo MolnarQuoted 29 lines · Ingo Molnar
btw., regarding this fix:
[email protected], 2003-09-06 12:28:20-07:00, [email protected]
[PATCH] Fix futex hashing bugswhy dont we do this:
} else { /* Make sure to stop if key1 == key2 */ if (head1 == head2) break; list_add_tail(i, head2); this->key = key2; if (ret - nr_wake >= nr_requeue) break; }instead of the current:
} else { list_add_tail(i, head2); this->key = key2; if (ret - nr_wake >= nr_requeue) break; /* Make sure to stop if key1 == key2 */ if (head1 == head2 && head1 != next) head1 = i; }
Quoted 2 lines
what's the point in requeueing once, and then exiting the loop by changing the loop exit condition variable?
Hugh's patch is clever and subtle. It doesn't exit the loop; the loop continues from "next".
What it does is change the end condition so that the loop stops just before the first requeued futex. Let's call that one REQUEUED1.
If are other futexes to requeue, they after inserted after REQUEUED1 (because head2 wasn't changed), yet the end condition _isn't_ changed when this happens, because now head1 != head2.
This causes the correct number of futexes to be requeued at the end of the wait list.
Quoted 2 lines
You are trying to avoid the lockup but the first one ought to be the most straightforward way to do it.
Hugh's patch returns the correct retval _and_ requeues the correct number of waiters to the end of the queue. And it does it without fancy code.
Remember that the waiter order is visible to userspace - it's used by "fair" operations, so it's appropriate that requeuing a futex to itself moves nr_requeues waiters to the end of the queue, just like it does when it requeues to a different futex.
If the code to handle that were complicated, I'd vote for dropping it. But Hugh's patch does exactly the right thing in a simple way. Lovely!
-- Jamie
Ingo Molnar
maintainerRe: [PATCH 2] Little fixes to previous futex patch
Quoted 2 lines · Jamie Lokier
Hugh's patch is clever and subtle. It doesn't exit the loop; the loop continues from "next".
ugh. It would be much cleaner to simply do a list_add() instead of a list_add_tail(). (the ordering of the queue doesnt matter anyway)
Ingo
Re: [PATCH 2] Little fixes to previous futex patch
Quoted 5 lines · Ingo Molnar
Quoted 2 lines
Hugh's patch is clever and subtle. It doesn't exit the loop; the loop continues from "next".
ugh. It would be much cleaner to simply do a
list_add()instead of alist_add_tail(). (the ordering of the queue doesnt matter anyway)
Why do you say the order doesn't matter? If you change the order in FUTEX_WAIT & FUTEX_WAKE, then "fair" operations aren't fair any more.
Is there a reason why FUTEX_REQUEUE is exempt from this?
-- Jamie
Ingo Molnar
maintainerRe: [PATCH 2] Little fixes to previous futex patch
Quoted 2 lines · Jamie Lokier
Why do you say the order doesn't matter? If you change the order in
FUTEX_WAIT&FUTEX_WAKE, then "fair" operations aren't fair any more.
hm, indeed, the ordering of wake-one/wake-few wakeups would be impacted.
Quoted 1 line
Is there a reason why
FUTEX_REQUEUEis exempt from this?
no, you are right - FIFO queueing must be preserved there too.
Ingo
Re: [PATCH 2] Little fixes to previous futex patch
In reply to Jamie LokierIn message <[email protected]> you write:
Quoted 2 lines
Feel free to think up a better hash that isn't slow. Two iterations of
hash_long()would be a good hash, but slower.
I've used jhash below.
Quoted 4 lines
Quoted 2 lines
The err at the end of
__get_page_keyswould be 1 from successfulget_user_pages, treated as error by the callers: need to make it 0.Well spotted.
Fixed below.
Quoted 3 lines
Quoted 3 lines
futex_wait: I didn't get around to it in my version, so haven't thought through the issues, but I'm a bit worried that you get curval for-EWOULDBLOCKcheck without holding thefutex_lock.
This works: the only danger is that the WAKE side will wake us even though we were going to fail with -EWOULDBLOCK, which is why we notice this in out_unqueue and return 0 in this case (if it's doing wake-one, it *really* must successfully wake one...).
Quoted 10 lines
Quoted 5 lines
That looks suspicious to me, but I'm going to be lazy and not try to think about it, because Rusty is sure to understand the races there. If that code is insufficient as you have it, may need
__pin_pagereinstated for just that case (hmm, was thatget_userright before? I'd expect it tokmap_atomicpinned page.)The important things are that the futex is queued prior to checking curval, the requested page won't change (it's protected by
mmap_sem), and any parallel waker changes the word prior to waking us.
Quoted 5 lines
You made me notice a rather subtle memory ordering condition, though.
We must issue the read after queuing the futex. There needs to be a
smp_rmb()after queuing and before the read, because thespin_unlock()barrier only constrains earlier reads, not later ones.
Ah, the joys of thinking too hard: I've been here before 8).
In my analyss, the earliest the read can move is to the beginning of the futex_lock, ie equivalent to:
spin_lock(&futex_lock); get_user(curval, (int *)uaddr); list_add_tail(&q->list, head); spin_unlock(&futex_lock);
Since the wake side has to take the futex lock too, this ordering is still safe.
Quoted 1 line
Thanks for all your great insights,
Definitely seconded, Hugh. Thanks!
Here's my accumulated patch set (Jamie's fixed patch included first for completeness):
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Futexes without pinning pages
Author: Jamie Lokier
Status: Booted on 2.6.0-test4-bk6
D: [ Later fixes from Jamie and Andrew Morton added --RR ]
D: include/linux/mm.h | 1
D: include/linux/vcache.h | 26 ---
D: kernel/futex.c | 368 +++++++++++++++++++++++++------------------------
D: mm/Makefile | 2
D: mm/fremap.c | 9 +
D: mm/memory.c | 2
D: mm/vcache.c | 90 -----------
D: 7 files changed, 200 insertions(+), 298 deletions(-)
D:
D: Patch name: futex-fixes-2.6.0-test4-01jl
D:
D: This patch changes the way futexes are indexed, so that they do not
D: pin pages and also corrects some problems with private mappings and COW
D: pages.
D:
D: Currently, all futexes look up the page at the userspace address and
D: pin it, using the pair (page,offset) as an index into a table of
D: waiting futexes. Any page with a futex waiting on it remains pinned
D: in RAM, which is a problem when many futexes are used, especially with
D: FUTEX_FD.
D:
D: Another problem is that the page is not always the correct one, if it
D: can be changed later by a COW (copy on write) operation. This can
D: happen when waiting on a futex without writing to it after fork(),
D: exec() or mmap(), if the page is then written to before attempting to
D: wake a futex at the same adress.
D:
D: There are two symptoms of the COW problem: 1. The wrong process can
D: receive wakeups; 2. A process can fail to receive required wakeups. D:
D: This patch fixes both by changing the indexing so that VM_SHARED
D: mappings use the triple (inode,offset,index), and private mappings use
D: the pair (mm,virtual_address).
D:
D: The former correctly handles all shared mappings, including tmpfs and
D: therefore all kinds of shared memory (IPC shm, /dev/shm and
D: MAP_ANON|MAP_SHARED). This works because every mapping which is
D: VM_SHARED has an associated non-zero vma->vm_file, and hence inode.
D: (This is ensured in do_mmap_pgoff, where it calls shmem_zero_setup). D:
D: The latter handles all private mappings, both files and anonymous. It
D: isn't affected by COW, because it doesn't care about the actual pages,
D: just the virtual address.
D:
D: The only obvious problem is that mremap() can move a private mapping
D: without informing futexes waiting on that mapping. However, mremap()
D: was already broken with futexes, because it doesn't update the vcache,
D: which is used by futexes, so this just changes an existing bug. D:
D: (A later patch from me will fix this problem with mremap(), by moving
D: the futexes).
D:
D: This patch has a few bonuses:
D:
D: 1. It removes the vcache implementation, as only futexes were
D: using it, and they don't any more.
D:
D: 2. Removing the vcache should make COW page faults a bit faster.
D:
D: 3. Futex operations no longer take the page table lock, walk
D: the page table, fault in pages that aren't mapped in the
D: page table, or do a vcache hash lookup - they are mostly a
D: simple offset calculation with one hash for the futex
D: table. So they should be noticably faster.
D:
D: 4. The patch reduces the kernel size by 98 lines.
D:
D: -- Jamie
include/linux/mm.h +1 -0
@@ -110,6 +110,7 @@ struct vm_area_struct {#define VM_RESERVED 0x00080000/* Don't unmap it from swap_out */ #define VM_ACCOUNT 0x00100000/* Is a VM accounted object */ #define VM_HUGETLB 0x00400000/* Huge TLB Page VM */ +#define VM_NONLINEAR 0x00800000/* Is non-linear (remap_file_pages) */ #ifndef VM_STACK_DEFAULT_FLAGS /* arch can override this */ #define VM_STACK_DEFAULT_FLAGS VM_DATA_DEFAULT_FLAGS
include/linux/vcache.h +0 -26
@@ -1,26 +0,0 @@ -/* -* virtual => physical mapping cache support. -*/ -#ifndef _LINUX_VCACHE_H -#define _LINUX_VCACHE_H - -typedef struct vcache_s { -unsigned long address; -struct mm_struct *mm; -struct list_head hash_entry; -void (*callback)(struct vcache_s *data,struct page *new_page); -}vcache_t ; - -extern spinlock_t vcache_lock; - -extern void __attach_vcache (vcache_t *vcache, -unsigned long address, -struct mm_struct *mm, -void (*callback)(struct vcache_s *data,struct page *new_page)); - -extern void __detach_vcache (vcache_t *vcache); - -extern void invalidate_vcache (unsigned long address,struct mm_struct *mm, -struct page *new_page); - -#endif
kernel/futex.c +190 -179
566 lines not on this page · raw message
mm/Makefile +1 -1
@@ -9,6 +9,6 @@ mmu-$(CONFIG_MMU) := fremap.o highmem.o obj-y := bootmem.o filemap.o mempool.o oom_kill.o fadvise.o \ page_alloc.o page-writeback.o pdflush.o readahead.o \ - slab.o swap.o truncate.o vcache.o vmscan.o $(mmu-y) + slab.o swap.o truncate.o vmscan.o $(mmu-y) obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o
mm/fremap.c +15 -6
@@ -144,7 +144,10 @@ long sys_remap_file_pages(unsigned longreturn err;#endif -down_read (&mm->mmap_sem); +/* +* vm_flags is protected by down_write(mmap_sem) +*/ +down_write (&mm->mmap_sem); vma =find_vma (mm, start);/*
@@ -155,12 +158,18 @@ long sys_remap_file_pages(unsigned longif (vma && (vma->vm_flags &VM_SHARED ) && vma->vm_ops && vma->vm_ops->populate && end > start && start >= vma->vm_start && - end <= vma->vm_end) + end <= vma->vm_end) { + + vma->vm_flags |=VM_NONLINEAR ; +if (start == vma->vm_start && end == vma->vm_end && + pgoff == vma->vm_pgoff) + vma->vm_flags &= ~VM_NONLINEAR ; +downgrade_write (&mm->mmap_sem); err = vma->vm_ops->populate (vma, start, size, vma->vm_page_prot, pgoff, flags &MAP_NONBLOCK ); - -up_read (&mm->mmap_sem); - +up_read (&mm->mmap_sem); + }else { +up_write (&mm->mmap_sem); + }return err; } -
mm/memory.c +0 -2
@@ -43,7 +43,6 @@#include <linux/swap.h> #include <linux/highmem.h> #include <linux/pagemap.h> -#include <linux/vcache.h> #include <linux/rmap-locking.h> #include <linux/module.h>
@@ -962,7 +961,6 @@ static inline void establish_pte(structstatic inline void break_cow (struct vm_area_struct * vma,struct page * new_page,unsigned long address,pte_t *page_table) { -invalidate_vcache (address, vma->vm_mm, new_page);flush_cache_page (vma, address);establish_pte (vma, address, page_table,pte_mkwrite (pte_mkdirty (mk_pte (new_page, vma->vm_page_prot)))); }
mm/vcache.c +0 -90
90 lines not on this page · raw message
Name: Minor Tweaks To Jamie Lokier's Futex Patch
Author: Rusty Russell
Status: Booted on 2.6.0-test4-bk6
Depends: Misc/futex-jamie.patch.gz
D: Minor changes to Jamie's excellent futex patch.
D: 1) Declare and use a union for the hash key, and rename __get_page_keys
D: to get_page_key.
D: 2) Remove obsolete comment above hash array decl.
D: 3) Simply -EFAULT on futexes in VSYSCALL area.
D: 4) Clarify comment about TASK_INTERRUPTIBLE.
D: 5) Andrew Morton says spurious wakeup is a bug. Catch it.
D: 6) Semantics of futex on read-only pages unclear: require write perm.
D: 7) Use Jenkins hash.
D: 8) Make get_page_keys return 0 on successful get_user_pages().
kernel/futex.c +80 -74
344 lines not on this page · raw message
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Jamie LokierQuoted 2 lines · Jamie Lokier
You will be please to know I have written a complete patch :)
Looks pretty sane to me. A couple of (untested) fixups:
Take mmap_sem for writing around the modification of vma->vm_flags.
But hold it for reading across the populate function: it does I/O and is slow.
25-akpm/mm/fremap.c | 14 ++++++++------ 1 files changed, 8 insertions(+), 6 deletions(-)
mm/fremap.c renamed from mm/fremap.c~futex-non-page-pinning-akpm-1 +8 -6
@@ -144,7 +144,10 @@ long sys_remap_file_pages(unsigned longreturn err;#endif -down_read (&mm->mmap_sem); +/* +* vm_flags is protected by down_write(mmap_sem) +*/ +down_write (&mm->mmap_sem); vma =find_vma (mm, start);/*
@@ -161,13 +164,12 @@ long sys_remap_file_pages(unsigned longif (start == vma->vm_start && end == vma->vm_end && pgoff == vma->vm_pgoff) vma->vm_flags &= ~VM_NONLINEAR ; - +downgrade_write (&mm->mmap_sem); err = vma->vm_ops->populate (vma, start, size, vma->vm_page_prot, pgoff, flags &MAP_NONBLOCK ); +up_read (&mm->mmap_sem); + }else { +up_write (&mm->mmap_sem); } - -up_read (&mm->mmap_sem); -return err; } -
_
schedule_timeout() returns in state TASK_RUNNING.
25-akpm/kernel/futex.c | 1 - 1 files changed, 1 deletion(-)
kernel/futex.c renamed from kernel/futex.c~futex-non-page-pinning-akpm-2 +0 -1
@@ -358,7 +358,6 @@ static inline int futex_wait(unsigned lospin_unlock (&futex_lock); time =schedule_timeout (time); -set_current_state (TASK_RUNNING );/* * NOTE: we don't remove ourselves from the waitqueue because
_
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Andrew Morton
Take
mmap_semfor writing around the modification ofvma->vm_flags. But hold it for reading across the populate function: it does I/O and is slow.
Agreed. Well spotted.
-- Jamie
Re: [PATCH] Alternate futex non-page-pinning and COW fix
In reply to Jamie LokierIn message <[email protected]> you write:
Quoted 3 lines
Hi Rusty,
You will be please to know I have written a complete patch :)
Hi Jamie,
Very pleased! Remember, Open Source is all about having other
people do your work for you 8)
Quoted 9 lines
Quoted 4 lines
Assume that we do:
1) Look up vma.
2) Ifvma->vm_flags&VM_SHARED, index bypage->mapping&page->index.
3) Otherwise, index byvma->vm_mm& uaddr.Like that, but 2) uses
vma->vm_file->f_dentry->d_inode.That way, there is no need to walk the page table at all unless it's a non-linear mapping (which my patch does handle).
OK.
Quoted 11 lines
Quoted 5 lines
2) If
VM_SHARED, andpage->mappingis NULL, what to do? AFAICT, this can happen in the case of anonymous shared mappings, say mmap/dev/zeroMAP_SHAREDandfork()? Treating it as !VM_SHARED (and hence matching in mm & uaddr) won't work, since the mm's will be different (and with mremap, the uaddrs may be different).No, that doesn't happen. An anoymous shared mapping calls
shmem_zero_setup(), which creates an anonymous tmpfs file to back the mapping. It then looks the same as IPC shm or any other tmpfs file.So it works :)
Ah, I didn't look down that far in do_mmap_pgoff. Right: that makes things much simpler.
Quoted 8 lines
Quoted 3 lines
3) Since we need the offset in the file anyway for the
VM_SHARED, it makes more sense to useget_user_pages()to get the vma and page in one call, rather thanfind_extend_vma().You need the offset, but you don't need the page. For a linear mapping, the offset is a very simple calculation - no page table lock and no page table walk. As a silly bonus it doesn't touch the page.
Quoted 6 lines
For non-linear mappings, I try
follow_page()and thenget_user_pages(), as usual, to getpage->index. Technically you don't need to swap the page in, but there's no point using complicated code for that unimportant case.I added a flag
VM_NONLINEARto distinguish them.
OK, I would have done it the naive way, but Ingo would probably have just written what you did (he did the follow_page optimization) 8)
The rest is just nitpicking...
kernel/futex.c line 52
Quoted 3 lines
kernel/futex.c +2
-0+/* Page keys and offset within the page. */ +unsigned long keys[2 ];int offset;
I prefer a union here. It's a little more verbose, but I think it's clearer:
struct anon_key
{
struct mm_struct *mm;
unsigned long uaddr;
};struct filebacked_key
{
struct inode *inode;
unsigned long page_index;
};union hash_key
{
struct anon_key anon;
struct filebacked_key filebacked;
unsigned long keys[2];
};kernel/futex.c line 113
Quoted 7 lines
kernel/futex.c +7
-0+#ifdef FIXADDR_USER_START +if (addr >=FIXADDR_USER_START && addr <FIXADDR_USER_END ) { + keys[0 ] =1 ;/* Different from any pointer value. */ + keys[1 ] = addr -FIXADDR_USER_START ; +return 0 ; + } +#endif
I think this is a bit extreme: this would allow futexes in the VSYSCALL region, right? I admire your thoroughness, but perhaps this should wait until someone comes up with a reason to do it?
The rest looks ok, I'll do a differential once the rest settles down... Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Re: [PATCH] Alternate futex non-page-pinning and COW fix
Quoted 3 lines · Rusty Russell
I think this is a bit extreme: this would allow futexes in the VSYSCALL region, right? I admire your thoroughness, but perhaps this should wait until someone comes up with a reason to do it?
I only put that in because map_user_pages does it. It isn't important.
If you look carefully, you see that these patches work exactly like the old implementation in all cases where the old one worked.
-- Jamie
In message <[email protected]> you write:
Quoted 11 lines
What happens after this sequence:
1. process A forks, making process B
2. B doesFUTEX_FD, or splits into threads and one doesFUTEX_WAIT, on a private page that has not been written to since the fork
3. A doesFUTEX_WAITon the same address
3. The page is swapped out
4. B doesFUTEX_WAKEat the same addressWon't the futex be hashed on the swap entry at step 4, so that both processes are woken, yet only the waiter in B should be woken?
Part of step (4) is to swap the page back in (see __pin_page).
Quoted 2 lines
Related: could COW sharing after
fork()explain the spurious wakeups I saw mentioned earlier in the thread?
In case others are sharing this misconception: there *are* no spurious wakeups. But if they were to happen, the current code doesn't handle them correctly, unlike every other primitive I know of in the kernel, which is why I fixed it while tidying the code.
I don't know of a rule which says "thou shalt not wake a random thread in the kernel": for all I know wierd things like CPU hotplug or software suspend may do this in the future.
Hope that clarifies,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Quoted 4 lines · Rusty Russell
I don't know of a rule which says "thou shalt not wake a random thread in the kernel": for all I know wierd things like CPU hotplug or software suspend may do this in the future.
pdflush is sensitive to that. It emits angry squeaks if unexpectedly woken.
And up until a couple of months ago there were sporadic squeaking reports, but they seem to have gone away.
Yes, we should treat a random wakeup like that as a bug.
Quoted 10 lines · Andrew Morton
Quoted 4 lines · Rusty Russell
I don't know of a rule which says "thou shalt not wake a random thread in the kernel": for all I know wierd things like CPU hotplug or software suspend may do this in the future.
pdflush is sensitive to that. It emits angry squeaks if unexpectedly woken.
And up until a couple of months ago there were sporadic squeaking reports, but they seem to have gone away.
I still run into the pdflush problem once a month or so, but only with boxes that are up for a week or more. It usually takes the box down if for no other reason than it's too busy prink()ing to do anything else. I haven't been able to sysrq it and the particular box that it happens on doesn't like NMIs so kgdb and the NMI oopser are out.
Are there any good reasons not to do something like the attached patch? It would at least keep pdflush from evicting everthing interesting that may have preceded it in dmesg.
Signature · 2 lines
Dave Hansen [email protected]
pdflush.c renamed from pdflush.c.orig +5 -1
@@ -112,7 +112,11 @@spin_lock_irq (&pdflush_lock);if (!list_empty (&my_work->list)) { -printk ("pdflush: bogus wakeup!\n" ); +static int wakeup_count =100 ; +if (wakeup_count >0 ) { + wakeup_count--; +printk ("pdflush: bogus wakeup!\n" ); + } my_work->fn =NULL ;continue ; }
Quoted 8 lines · Dave Hansen
Quoted 6 lines · Andrew Morton
Quoted 4 lines · Rusty Russell
I don't know of a rule which says "thou shalt not wake a random thread in the kernel": for all I know wierd things like CPU hotplug or software suspend may do this in the future.
Quoted 8 lines
Quoted 4 lines
pdflush is sensitive to that. It emits angry squeaks if unexpectedly woken.
And up until a couple of months ago there were sporadic squeaking reports, but they seem to have gone away.
I still run into the pdflush problem once a month or so, but only with boxes that are up for a week or more. It usually takes the box down if for no other reason than it's too busy prink()ing to do anything else.
That serves you right for not telling me!
Quoted 6 lines
I haven't been able to sysrq it and the particular box that it happens on doesn't like NMIs so kgdb and the NMI oopser are out.
Are there any good reasons not to do something like the attached patch? It would at least keep pdflush from evicting everthing interesting that may have preceded it in dmesg.
I'd prefer a more intricate patch which does something like the below.
Seriously, please: this shouldn't be happening. We need to work out the cause.
mm/pdflush.c | 18 +++++++++++++++++- 1 files changed, 17 insertions(+), 1 deletion(-)
mm/pdflush.c renamed from mm/pdflush.c~pdflush-diag +17 -1
@@ -84,6 +84,8 @@ struct pdflush_work {unsigned long when_i_went_to_sleep; }; +static int wakeup_count =100 ; +static int __pdflush (struct pdflush_work *my_work) {daemonize ("pdflush" );
@@ -112,7 +114,10 @@ static int __pdflush(struct pdflush_workspin_lock_irq (&pdflush_lock);if (!list_empty (&my_work->list)) { -printk ("pdflush: bogus wakeup!\n" ); +if (wakeup_count >0 ) { + wakeup_count--; +printk ("pdflush: bogus wakeup!\n" ); + } my_work->fn =NULL ;continue ; }
@@ -182,6 +187,7 @@ int pdflush_operation(void (*fn)(unsigne {unsigned long flags;int ret =0 ; +static int poke_count =0 ;if (fn ==NULL )BUG ();/* Hard to diagnose if it's deferred */
@@ -190,9 +196,19 @@ int pdflush_operation(void (*fn)(unsigneif (list_empty (&pdflush_list)) {spin_unlock_irqrestore (&pdflush_lock, flags); ret =-1 ; +if (wakeup_count <100 && poke_count <10 ) { +printk ("%s: no threads\n" , __FUNCTION__); +dump_stack (); + poke_count++; + } }else {struct pdflush_work *pdf; +if (wakeup_count <100 && poke_count <10 ) { +printk ("%s: found a thread\n" , __FUNCTION__); +dump_stack (); + poke_count++; + } pdf = list_entry(pdflush_list.next, struct pdflush_work, list);list_del_init (&pdf->list);if (list_empty (&pdflush_list))
_
Not pinning the pages, and going by mapping,index (including swapper_space,swap_index case) seems fine; with a special case of struct page * for the anonymous not yet assigned to swap.
(Very tempting to assign to swap early to avoid that special case; but swapoff,swapless,swapon make that unreasonable.)
But I do not understand how futex_wake can still be doing a this->page == page test: its __pin_page will ensure that some page is faulted in, but that's not necessarily the same page as in this->page.
I believe you need mapping,index in struct futex_q (with swapper_space just one possibility for mapping), and the struct page * considered an exceptional (though common) case.
I strongly agree with Andrew that add_to_swap and delete_from_swap_cache (probably the one without the __s) are the places for switching the anonymous, not page_io.c:page->mapping will be set and unset in those, and it's page->mapping that you're keying off in hash_futex.
But I disagree over move_to/from_swap_cache: nothing should be done there at all. Once you have mapping,index in struct futex_q, it's irrelevant what tmpfs might be doing to the page->mapping,page->index of the unmapped page.
I dare not think what locking may be necessary, to manage the switch from hashing by struct page * to hashing by swapper_space,index.
Hugh
Quoted 7 lines · Hugh Dickins
But I disagree over move_to/from_swap_cache: nothing should be done there at all. Once you have mapping,index in struct
futex_q, it's irrelevant what tmpfs might be doing to the page->mapping,page->index of the unmapped page.
I dare not think what locking may be necessary, to manage the switch from hashing by struct page * to hashing by swapper_space,index.
PG_locked and mapping->page_lock held for writing are needed to switch in general AIUI; adding the vcache/futex locks into the mix sounds like some deep hierarchy, especially since the page is meant to go away in the middle of this process. move_to_swap_cache() has mapping->page_lock held for writing, as is needed; PG_locked is required to add_to_swap() and some other callers are from call chains not checking BUG_ON(!PageLocked(page)) so it sounds as if things are partly there, assuming vcache_lock/futex_lock stay at the bottom.
I think it's worth coming up with an answer to in order to remove the DoS scenario and/or resource scalability limitations.
-- wli
Quoted 5 lines · Hugh Dickins
But I disagree over move_to/from_swap_cache: nothing should
be done there at all. Once you have mapping,index in structfutex_q, it's irrelevant what tmpfs might be doing to the page->mapping,page->index of the unmapped page.
But move_to_swap_cache() alters a page's ->mapping and ->index when that page is potentially mapped into user pagetables.
Quoted 9 lines · Andrew Morton
Quoted 5 lines · Hugh Dickins
But I disagree over move_to/from_swap_cache: nothing should
be done there at all. Once you have mapping,index in structfutex_q, it's irrelevant what tmpfs might be doing to the page->mapping,page->index of the unmapped page.But
move_to_swap_cache()alters a page's ->mapping and ->index when that page is potentially mapped into user pagetables.
It'd better not: BUG_ON(page_mapped(page)) at start of shmem_writepage, sole caller of move_to_swap_cache. Things fall apart if tmpfs pages get reassigned to swap while they're mapped.
Hugh
In message <[email protected]> you write:
Quoted 4 lines
But I do not understand how
futex_wakecan still be doing athis->page== page test: its__pin_pagewill ensure that some page is faulted in, but that's not necessarily the same page as inthis->page.
Yeah, my complete screwup. See below, with new routine page_matches().
Quoted 5 lines
I strongly agree with Andrew that
add_to_swapanddelete_from_swap_cache(probably the one without the__s) are the places for switching the anonymous, notpage_io.c:page->mappingwill be set and unset in those, and it'spage->mappingthat you're keying off inhash_futex.
Agreed, it's simplest, at least, to call futex_rehash every time ->mapping changes. But that's alot, so we'll need that futex page->flags optimization.
I've included 3 patches and my test code. This includes debugging output, so it's not a final patch.
The test code sets up 3 futexes (one in a file-backed mmap, one in a malloc, and one in a shared memory segment), then runs through <N> MB forcing things to swap. When you see the kernel message saying a futex has been swapped out, press Enter and it will wake the futexes. A successful run looks like (it can take a few attempts before the futex gets swapped out, depending on the phase of the moon):
test:~# swapon /swap Adding 14992k swap on /swap. Priority:-1 extents:82 test:~# ./test-swap2 36 MMAP=8, SHM=16, ANON=24, beginning chill... . futex_rehash 13370: offset 24 00000000 -> 902bd100
Exiting...
Waking up 0x30012008
Waking up 0x804c018
Waking up 0x30013010
test:~#
Thanks for feedback,
Rusty
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Name: Minor futex comment tweaks and cleanups
Author: Rusty Russell
Status: Booted on 2.6.0-test4-bk2
D: Changes:
D:
D: (1) don't return 0 from futex_wait if we are somehow
D: spuriously woken up, loop in that case.
D:
D: (2) remove bogus comment about address no longer being in this D: address space: we hold the mm lock, and __pin_page succeeded, so it D: can't be true,
D:
D: (3) remove bogus comment about "get_user might fault and schedule", D:
D: (4) clarify comment about hashing: we hash address of struct page,
D: not page itself,
D:
D: (4) remove list_empty check: we still hold the lock, so it can
D: never happen, and
D:
D: (5) single error exit path, and move __queue_me to the end (order
D: doesn't matter since we're inside the futex lock).
kernel/futex.c +32 -33
@@ -84,9 +84,7 @@ static inline void unlock_futex_mm(void)spin_unlock (¤t->mm->page_table_lock); } -/* -* The physical page is shared, so we can hash on its address: -*/ +/* The struct page is shared, so we can hash on its address. */ static inline struct list_head *hash_futex (struct page *page,int offset) { return &futex_queues[hash_long((unsigned long)page + offset,
@@ -311,67 +309,68 @@ static inline int futex_wait(unsigned lo int val, unsigned long time) { -DECLARE_WAITQUEUE (wait ,current ); -int ret =0 , curval; +wait_queue_t wait; +int ret, curval;struct page *page;struct futex_q q; +again:init_waitqueue_head (&q.waiters); +init_waitqueue_entry (&wait, current);lock_futex_mm (); page =__pin_page (uaddr - offset);if (!page) { -unlock_futex_mm (); -return -EFAULT ; + ret = -EFAULT ; + goto unlock; } -__queue_me (&q, page, uaddr, offset,-1 ,NULL );/* -* Page is pinned, but may no longer be in this address space. +* Page is pinned, but may be a kernel address. * It cannot schedule, so we access it with the spinlock held. */ if (get_user (curval, (int *)uaddr) !=0 ) { -unlock_futex_mm (); ret = -EFAULT ; - goto out; + goto unlock; } +if (curval != val) { -unlock_futex_mm (); ret = -EWOULDBLOCK ; - goto out; + goto unlock; } -/* -* The get_user() above might fault and schedule so we -* cannot just set TASK_INTERRUPTIBLE state when queueing -* ourselves into the futex hash. This code thus has to -* rely on the futex_wake() code doing a wakeup after removing -* the waiter from the list. -*/ + +__queue_me (&q, page, uaddr, offset,-1 ,NULL );add_wait_queue (&q.waiters, &wait);set_current_state (TASK_INTERRUPTIBLE ); -if (!list_empty (&q.list)) { -unlock_futex_mm (); - time =schedule_timeout (time); - } +unlock_futex_mm (); + + time =schedule_timeout (time); +set_current_state (TASK_RUNNING );/* * NOTE: we don't remove ourselves from the waitqueue because * we are the only user of it. */ -if (time ==0 ) { - ret = -ETIMEDOUT ; - goto out; - } -if (signal_pending (current)) - ret = -EINTR ; -out: -/* Were we woken up anyway? */ +put_page (q.page); + +/* Were we woken up (and removed from queue)? Always return +* success when this happens. */ if (!unqueue_me (&q)) ret =0 ; -put_page (q.page); +else if (time ==0 ) + ret = -ETIMEDOUT ; +else if (signal_pending (current)) + ret = -EINTR ; +else +/* Spurious wakeup somehow. Loop. */ + goto again;return ret; + +unlock: +unlock_futex_mm (); +return ret; }static int futex_close (struct inode *inode,struct file *filp)
Name: Allow Futex Rehashing In Interrupt
Author: Rusty Russell
Status: Tested on 2.6.0-test4-bk2
Depends: Misc/futex-minor-tweaks.patch.gz
Depends: Misc/qemu-page-offset.patch.gz
D: This patch simply uses spin_lock_irq() instead of spin_lock for the
D: futex lock, in preparation for the futex_rehash patch which needs to
D: operate on the futex hash table in IRQ context.
kernel/futex.c +8 -8
@@ -74,12 +74,12 @@ static inline void lock_futex_mm(void) {spin_lock (¤t->mm->page_table_lock);spin_lock (&vcache_lock); -spin_lock (&futex_lock); +spin_lock_irq (&futex_lock); }static inline void unlock_futex_mm (void ) { -spin_unlock (&futex_lock); +spin_unlock_irq (&futex_lock);spin_unlock (&vcache_lock);spin_unlock (¤t->mm->page_table_lock); }
@@ -196,7 +196,7 @@ static void futex_vcache_callback(vcache struct futex_q *q = container_of(vcache, struct futex_q, vcache);struct list_head *head =hash_futex (new_page, q->offset); -spin_lock (&futex_lock); +spin_lock_irq (&futex_lock);if (!list_empty (&q->list)) {put_page (q->page);
@@ -206,7 +206,7 @@ static void futex_vcache_callback(vcachelist_add_tail (&q->list, head); } -spin_unlock (&futex_lock); +spin_unlock_irq (&futex_lock); }/*
@@ -293,13 +293,13 @@ static inline int unqueue_me(struct futeint ret =0 ;spin_lock (&vcache_lock); -spin_lock (&futex_lock); +spin_lock_irq (&futex_lock);if (!list_empty (&q->list)) {list_del (&q->list);__detach_vcache (&q->vcache); ret =1 ; } -spin_unlock (&futex_lock); +spin_unlock_irq (&futex_lock);spin_unlock (&vcache_lock);return ret; }
@@ -391,10 +391,10 @@ static unsigned int futex_poll(struct fiint ret =0 ;poll_wait (filp, &q->waiters, wait); -spin_lock (&futex_lock); +spin_lock_irq (&futex_lock);if (list_empty (&q->list)) ret =POLLIN |POLLRDNORM ; -spin_unlock (&futex_lock); +spin_unlock_irq (&futex_lock);return ret; }
Name: Futexes without pinning pages
Author: Rusty Russell
Status: Tested on 2.6.0-test4-bk2
Depends: Misc/futex-irqsave.patch.gz
Depends: Misc/qemu-page-offset.patch.gz
D: TODO: Fix compilation with CONFIG_FUTEX=n.
D:
D: Avoid pinning pages with futexes in them, to resolve FUTEX_FD DoS.
D: This means we need another way to uniquely identify pages, rather
D: than simply comparing the "struct page *" (and using a hash table
D: based on the "struct page *". For file-backed pages, the
D: page->mapping and page->index provide a unique identifier, which is
D: persistent even if they get swapped out to the file and back.
D: There are cases where the mapping changes: for these we need a
D: callback to rehash all futexes in that page.
D:
D: For anonymous pages, page->mapping == NULL. So for this case we
D: use the "struct page *" itself to hash and compare, because the
D: mapping will be set (to &swapper_space) if the page is moved to the
D: swap cache, and will be rehashed, and we can find it again. D:
D: The current futex_rehash() call walks the entire hash table, which
D: is slow. The simplest optimization is to have a page->flags bit
D: which indicates a futex has been placed in this page: we can clear
D: it if futex_rehash() finds no futexes. This will come in a
D: followup patch.
include/linux/futex.h +6 -0
@@ -17,4 +17,10 @@ asmlinkage long sys_futex(u32 __user *ualong do_futex (unsigned long uaddr,int op,int val,unsigned long timeout,unsigned long uaddr2,int val2); +/* To tell us when the page->mapping or page->index changes. */ +struct page ; +struct address_space ; +extern void futex_rehash (struct page *page, +struct address_space *new_mapping, +unsigned long new_index);#endif
include/linux/pagemap.h +2 -0
@@ -11,6 +11,7 @@#include <linux/pagemap.h> #include <asm/uaccess.h> #include <linux/gfp.h> +#include <linux/futex.h> /* * Bits in mapping->flags. The lower __GFP_BITS_SHIFT bits are the page
@@ -143,6 +144,7 @@ static inline void ___add_to_page_cache( struct address_space *mapping, unsigned long index) {list_add (&page->list, &mapping->clean_pages); +futex_rehash (page, mapping, index); page->mapping = mapping; page->index = index;
kernel/futex.c +93 -22
221 lines not on this page · raw message
mm/filemap.c +2 -0
@@ -27,6 +27,7 @@#include <linux/pagevec.h> #include <linux/blkdev.h> #include <linux/security.h> +#include <linux/futex.h> /* * This is needed for the following functions: * - try_to_release_page
@@ -92,6 +93,7 @@ void __remove_from_page_cache(struct pagradix_tree_delete (&mapping->page_tree, page->index);list_del (&page->list); +futex_rehash (page,NULL ,0 ); page->mapping =NULL ; mapping->nrpages--;
mm/page_io.c +5 -0
@@ -19,6 +19,7 @@#include <linux/buffer_head.h> /* for block_sync_page() */ #include <linux/mpage.h> #include <linux/writeback.h> +#include <linux/futex.h> #include <asm/pgtable.h> static struct bio *
@@ -151,6 +152,7 @@ int rw_swap_page_sync(int rw, swp_entry_lock_page (page);BUG_ON (page->mapping); +futex_rehash (page, &swapper_space, entry.val); page->mapping = &swapper_space; page->index = entry.val;
@@ -161,7 +163,10 @@ int rw_swap_page_sync(int rw, swp_entry_ ret =swap_writepage (page, &swap_wbc);wait_on_page_writeback (page); } +lock_page (page); +futex_rehash (page,NULL ,0 ); page->mapping =NULL ; +unlock_page (page);if (ret ==0 && (!PageUptodate (page) ||PageError (page))) ret = -EIO ;return ret;
mm/swap_state.c +3 -0
@@ -13,6 +13,7 @@#include <linux/init.h> #include <linux/pagemap.h> #include <linux/backing-dev.h> +#include <linux/futex.h> #include <asm/pgtable.h>
@@ -200,6 +201,7 @@ int move_to_swap_cache(struct page *page err =radix_tree_insert (&swapper_space.page_tree, entry.val, page);if (!err) { +futex_rehash (page, &swapper_space, entry.val);__remove_from_page_cache (page);___add_to_page_cache (page, &swapper_space, entry.val); }
@@ -236,6 +238,7 @@ int move_from_swap_cache(struct page *pa err =radix_tree_insert (&mapping->page_tree, index, page);if (!err) { +futex_rehash (page, mapping, index);__delete_from_swap_cache (page);___add_to_page_cache (page, mapping, index); }
================
/* Test program for unpinned futexes. */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sched.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <signal.h>
#include <errno.h>
#include <string.h>
#include <sys/shm.h>
#include <sys/poll.h>
#include <sys/mman.h>
#include "usersem.h"
#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof((arr)[0])) #define streq(a,b) (strcmp((a),(b)) == 0)
#define UNTOUCHED_VALUE 7
#define TOUCHED_VALUE 100
/* Recognizable offsets within page so printks can easily identify the futex */ #define MMAP_OFFSET 8
#define SHMEM_OFFSET 16
#define ANON_OFFSET 24
static void chill(int size)
{
char *mem;
unsigned int i, numpages;
unsigned int pagesize = getpagesize();
numpages = size * 1024*1024 / pagesize;
mem = malloc(numpages * pagesize);
if (!mem) {
fprintf(stderr, "Out of memory\n");
exit(1);
}
for (;;) {
for (i = 0; i < numpages; i++)
*(mem + i*pagesize) = '\0';
printf(".\n");
}
}static void *adjust_to_offset(void *addr, unsigned int off)
{
unsigned int pagesize = getpagesize();
while ((unsigned long)addr % pagesize != off)
addr++;
return addr;
}/* Give an FD waiting on futex at this addr. */
static int fd_for_addr(void *addr)
{
return sys_futex(addr, FUTEX_FD, 0, NULL);
}static void *get_anon_page(void)
{
return malloc(getpagesize());
}static void *get_shared_memory(void)
{
unsigned int pagesize = getpagesize();
void *memory;
static int shm;
shm = shmget(IPC_PRIVATE, pagesize, IPC_CREAT);
if (shm < 0) {
perror("shmget");
return NULL;
}
memory = shmat(shm, NULL, 0);
if (memory == (void *)-1) {
perror("shmat");
shmctl(shm, IPC_RMID, NULL);
return NULL;
}
/* Delete when we exit. */
shmctl(shm, IPC_RMID, NULL);
return memory;
}static void *get_mmap(void)
{
unsigned int pagesize = getpagesize();
void *memory;
int fd;
fd = open("/tmp/test-swap2", O_CREAT|O_EXCL|O_RDWR, 0600);
if (fd < 0) {
perror("Opening /tmp/test-swap2");
return NULL;
}
unlink("/tmp/test-swap2");
if (write(fd, malloc(pagesize), pagesize) != pagesize) {
perror("Writing /tmp/test-swap2");
return NULL;
}
memory = mmap(NULL, pagesize, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
if (memory == MAP_FAILED) {
perror("mmap /tmp/test-swap2");
return NULL;
}
return memory;
}/* Touching the page swaps it back in, which is slightly different
* from waking on a page which is swapped out. */
static void wake_futex(int *futex, int touch, const char action[])
{
if (touch)
*futex = TOUCHED_VALUE;
printf("Waking up %p\n", futex);
if (sys_futex(futex, FUTEX_WAKE, 1, NULL) != 1) {
perror(action);
exit(1);
}
}int main(int argc, char *argv[])
{
int *map, *anon, *shm, touch = 0;
pid_t child;
char c;
struct pollfd pollarr[3];
if (argc > 1 && streq(argv[1], "-t")) {
touch = 1;
argc--;
argv++;
}
if (argc != 2) {
fprintf(stderr, "Usage: test-swap2 [-t] <mb-to-thrash>\n"
" Where -t means touch before waking futexes\n");
exit(1);
}
map = get_mmap();
anon = get_anon_page();
shm = get_shared_memory();
if (!map || !anon || !shm)
exit(1);
/* Different offsets so we can recognize them in printks. */
map = adjust_to_offset(map, MMAP_OFFSET);
anon = adjust_to_offset(anon, ANON_OFFSET);
shm = adjust_to_offset(shm, SHMEM_OFFSET);
*map = *anon = *shm = UNTOUCHED_VALUE;
pollarr[0].fd = fd_for_addr(map);
pollarr[1].fd = fd_for_addr(anon);
pollarr[2].fd = fd_for_addr(shm);
pollarr[0].events = pollarr[1].events = pollarr[2].events = POLLIN;
/* None should be ready yet */
if (poll(pollarr, ARRAY_SIZE(pollarr), 0)) {
perror("poll");
exit(1);
}
printf("MMAP=%u, SHM=%u, ANON=%u, beginning chill...\n",
MMAP_OFFSET, SHMEM_OFFSET, ANON_OFFSET);
child = fork();
if (child < 0) {
perror("fork");
exit(1);
}
if (child == 0)
chill(atoi(argv[1]));
/* Wait until they hit <CR>. */
if (read(0, &c, 1) != 1) {
perror("read");
exit(1);
}
kill(child, SIGTERM);
printf("Exiting...\n");
wake_futex(map, touch, "wake up mmap");
wake_futex(anon, touch, "wake up anon");
wake_futex(shm, touch, "wake up shm");
if (poll(pollarr, ARRAY_SIZE(pollarr), -1) != 3) {
perror("poll after wakeup");
exit(1);
}
if (touch)
c = TOUCHED_VALUE;
else
c = UNTOUCHED_VALUE;
if (*map != c) {
fprintf(stderr, "mmap didn't get value %u: it's %u\n",
c, *mmap);
exit(1);
}
if (*anon != c) {
fprintf(stderr, "anon didn't get value %u: it's %u\n",
c, *anon);
exit(1);
}
if (*shm != c) {
fprintf(stderr, "shm didn't get value %u: it's %u\n",
c, *shm);
exit(1);
}
return 0;
}================