Messages in this thread | | | Date | Tue, 01 Jul 2014 13:52:00 +0200 | From | Vlastimil Babka <> | Subject | Re: mm: shm: hang in shmem_fallocate |
| |
On 06/27/2014 07:36 AM, Hugh Dickins wrote:> [Cc Johannes: at the end I have a particular question for you] > > On Thu, 26 Jun 2014, Vlastimil Babka wrote: >> On 06/26/2014 12:36 AM, Hugh Dickins wrote: >>> On Tue, 24 Jun 2014, Vlastimil Babka wrote: >>> >>> Sorry for the slow response: I have got confused, learnt more, and >>> changed my mind, several times in the course of replying to you. >>> I think this reply will be stable... though not final. >> >> Thanks a lot for looking into it! >> >>>> >>>> since this got a CVE, >>> >>> Oh. CVE-2014-4171. Couldn't locate that yesterday but see it now. >> >> Sorry, I should have mentioned it explicitly. >> >>> Looks overrated to me >> >> I'd bet it would pass unnoticed if you didn't use the sentence "but whether >> it's a serious matter in the scale of denials of service, I'm not so sure" in >> your first reply to Sasha's report :) I wouldn't be surprised if people grep >> for this. > > Hah, you're probably right, > I better choose my words more carefully in future. > >> >>> (and amusing to see my pompous words about a >>> "range notification mechanism" taken too seriously), but of course >>> we do need to address it. >>> >>>> I've been looking at backport to an older kernel where >>> >>> Thanks a lot for looking into it. I didn't think it was worth a >>> Cc: stable@vger.kernel.org myself, but admit to being both naive >>> and inconsistent about that. >>> >>>> fallocate(FALLOC_FL_PUNCH_HOLE) is not yet supported, and there's also no >>>> range notification mechanism yet. There's just madvise(MADV_REMOVE) and >>>> since >>> >>> Yes, that mechanism could be ported back pre-v3.5, >>> but I agree with your preference not to. >>> >>>> it doesn't guarantee anything, it seems simpler just to give up retrying >>>> to >>> >>> Right, I don't think we have formally documented the instant of "full hole" >>> that I strove for there, and it's probably not externally verifiable, nor >>> guaranteed by other filesystems. I just thought it a good QoS aim, but >>> it has given us this problem. >>> >>>> truncate really everything. Then I realized that maybe it would work for >>>> current kernel as well, without having to add any checks in the page >>>> fault >>>> path. The semantics of fallocate(FALLOC_FL_PUNCH_HOLE) might look >>>> different >>>> from madvise(MADV_REMOVE), but it seems to me that as long as it does >>>> discard >>>> the old data from the range, it's fine from any information leak point of >>>> view. >>>> If someone races page faulting, it IMHO doesn't matter if he gets a new >>>> zeroed >>>> page before the parallel truncate has ended, or right after it has ended. >>> >>> Yes. I disagree with your actual patch, for more than one reason, >>> but it's in the right area; and I found myself growing to agree with >>> you, that's it's better to have one kind of fix for all these releases, >>> than one for v3.5..v3.15 and another for v3.1..v3.4. (The CVE cites >>> v3.0 too, I'm sceptical about that, but haven't tried it as yet.) >> >> I was looking at our 3.0 based kernel, but it could be due to backported >> patches on top. > > And later you confirm that 3.0.101 vanilla is okay: thanks, that fits. > >> >>> If I'd realized that we were going to have to backport, I'd have spent >>> longer looking for a patch like yours originally. So my inclination >>> now is to go your route, make a new patch for v3.16 and backports, >>> and revert the f00cdc6df7d7 that has already gone in. >>> >>>> So I'm posting it here as a RFC. I haven't thought about the >>>> i915_gem_object_truncate caller yet. I think that this path wouldn't >>>> satisfy >>> >>> My understanding is that i915_gem_object_truncate() is not a problem, >>> that i915's dev->struct_mutex serializes all its relevant transitions, >>> plus the object woudn't even be interestingly accessible to the user. >>> >>>> the new "lstart < inode->i_size" condition, but I don't know if it's >>>> "vulnerable" >>>> to the problem. >>> >>> I don't think i915 is vulnerable, but if it is, that condition would >>> be fine for it, as would be the patch I'm now thinking of. >>> >>>> >>>> -----8<----- >>>> From: Vlastimil Babka <vbabka@suse.cz> >>>> Subject: [RFC PATCH] shmem: prevent livelock between page fault and hole >>>> punching >>>> >>>> --- >>>> mm/shmem.c | 19 +++++++++++++++++++ >>>> 1 file changed, 19 insertions(+) >>>> >>>> diff --git a/mm/shmem.c b/mm/shmem.c >>>> index f484c27..6d6005c 100644 >>>> --- a/mm/shmem.c >>>> +++ b/mm/shmem.c >>>> @@ -476,6 +476,25 @@ static void shmem_undo_range(struct inode *inode, >>>> loff_t lstart, loff_t lend, >>>> if (!pvec.nr) { >>>> if (index == start || unfalloc) >>>> break; >>>> + /* >>>> + * When this condition is true, it means we were >>>> + * called from fallocate(FALLOC_FL_PUNCH_HOLE). >>>> + * To prevent a livelock when someone else is >>>> faulting >>>> + * pages back, we are content with single pass >>>> and do >>>> + * not retry with index = start. It's important >>>> that >>>> + * previous page content has been discarded, and >>>> + * faulter(s) got new zeroed pages. >>>> + * >>>> + * The other callsites are shmem_setattr (for >>>> + * truncation) and shmem_evict_inode, which set >>>> i_size >>>> + * to truncated size or 0, respectively, and >>>> then call >>>> + * us with lstart == inode->i_size. There we do >>>> want to >>>> + * retry, and livelock cannot happen for other >>>> reasons. >>>> + * >>>> + * XXX what about i915_gem_object_truncate? >>>> + */ >>> >>> I doubt you have ever faced such a criticism before, but I'm going >>> to speak my mind and say that comment is too long! A comment of that >>> length is okay above or just inside or at a natural break in a function, >>> but here it distracts too much from what the code is actually doing. >> >> Fair enough. The reasoning should have gone into commit log, not comment. >> >>> In particular, the words "this condition" are so much closer to the >>> condition above than the condition below, that it's rather confusing. >>> >>> /* Single pass when hole-punching to not livelock on racing faults */ >>> would have been enough (yes, I've cheated, that would be 2 or 4 lines). >>> >>>> + if (lstart < inode->i_size) >>> >>> For a long time I was going to suggest that you leave i_size out of it, >>> and use "lend > 0" instead. Then suddenly I realized that this is the >>> wrong place for the test. >> >> Well my first idea was to just add a flag about how persistent it should be. >> And set it false for the punch hole case. Then I wondered if there's already >> some bit that distinguishes it. But it makes it more subtle. >> >>> And then that it's not your fault, it's mine, >>> in v3.1's d0823576bf4b "mm: pincer in truncate_inode_pages_range". >>> Wow, that really pessimized the hole-punch case! >>> >>> When is pvec.nr 0? When we've reached the end of the file. Why should >>> we go to the end of the file, when punching a hole at the start? Ughh! >> >> Ah, I see (I think). But I managed to reproduce this problem when there was >> only an extra page between lend and the end of file, so I doubt this is the >> only problem. AFAIU it's enough to try punching a large enough hole, then the >> loop can only do a single pagevec worth of pages per iteration, which gives >> enough time for somebody faulting pages back? > > That's useful info, thank you: I just wasn't trying hard enough then; > and you didn't even need 1024 cpus to show it either. Right, we have > to revert my pincer, certainly on shmem. And I think I'd better do the > same change on generic filesystems too (nobody has bothered to implement > hole-punch on ramfs, but if they did, they would hit the same problem): > though that part of it doesn't need a backport to -stable. > >> >>>> + break; >>>> index = start; >>>> continue; >>>> } >>>> -- >>>> 1.8.4.5 >>> >>> But there is another problem. We cannot break out after one pass on >>> shmem, because there's a possiblilty that a swap entry in the radix_tree >>> got swizzled into a page just as it was about to be removed - your patch >>> might then leave that data behind in the hole. >> >> Thanks, I didn't notice that. Do I understand correctly that this could mean >> info leak for the punch hole call, but wouldn't be a problem for madvise? (In >> any case, that means the solution is not general enough for all kernels, so >> I'm asking just to be sure). > > It's exactly the same issue for the madvise as for the fallocate: > data that is promised to have been punched out would still be there.
AFAIK madvise doesn't promise anything. But nevermind.
> Very hard case to trigger, though, I think: since by the time we get > to this loop, we have already made one pass down the hole, getting rid > of everything that wasn't page-locked at the time, so the chance of > catching any swap in this loop is lower. > >> >>> As it happens, Konstantin Khlebnikov suggested a patch for that a few >>> weeks ago, before noticing that it's already handled by the endless loop. >>> If we make that loop no longer endless, we need to add in Konstantin's >>> "if (shmem_free_swap) goto retry" patch. >>> >>> Right now I'm thinking that my idiocy in d0823576bf4b may actually >>> be the whole of Trinity's problem: patch below. If we waste time >>> traversing the radix_tree to end-of-file, no wonder that concurrent >>> faults have time to put something in the hole every time. >>> >>> Sasha, may I trespass on your time, and ask you to revert the previous >>> patch from your tree, and give this patch below a try? I am very >>> interested to learn if in fact it fixes it for you (as it did for me). >> >> I will try this, but as I explained above, I doubt that alone will help. > > And afterwards you confirmed, thank you. > >> >>> However, I am wasting your time, in that I think we shall decide that >>> it's too unsafe to rely solely upon the patch below (what happens if >>> 1024 cpus are all faulting on it while we try to punch a 4MB hole at >> >> My reproducer is 4MB file, where the puncher tries punching everything except >> first and last page. And there are 8 other threads (as I have 8 logical >> CPU's) that just repeatedly sweep the same range, reading only the first byte >> of each page. >> >>> end of file? if we care). I think we shall end up with the optimization >>> below (or some such: it can be written in various ways), plus reverting >>> d0823576bf4b's "index == start && " pincer, plus Konstantin's >>> shmem_free_swap handling, rolled into a single patch; and a similar >> >> So that means no retry in any case (except the swap thing)? All callers can >> handle that? I guess shmem_evict_inode would be ok, as nobody else >> can be accessing that inode. But what about shmem_setattr? (i.e. straight >> truncation) As you said earlier, faulters will get a SIGBUS (which AFAIU is >> due to i_size being updated before we enter shmem_undo_range). But could >> possibly a faulter already pass the i_size test, and proceed with the fault >> only when we are already in shmem_undo_range and have passed the page in >> question? > > We still have to retry indefinitely in the truncation case, as you > rightly guess. SIGBUS beyond i_size makes it a much easier case to > handle, and there's no danger of "indefinitely" becoming "infinitely" > as in the punch-hole case. But, depending on how the filesystem > handles its end, there is still some possibility of a race with faulting, > which some filesystems may require pagecache truncation to resolve. > > Does shmem truncation itself require that? Er, er, it would take me > too long to work out the definitive answer: perhaps it doesn't, but for > safety I certainly assume that it does require that - that is, I never > even considered removing the indefinite loop from the truncation case. > >> >>> patch (without the swap part) for several functions in truncate.c. >>> >>> Hugh >>> >>> --- 3.16-rc2/mm/shmem.c 2014-06-16 00:28:55.124076531 -0700 >>> +++ linux/mm/shmem.c 2014-06-25 10:28:47.063967052 -0700 >>> @@ -470,6 +470,7 @@ static void shmem_undo_range(struct inod >>> for ( ; ; ) { >>> cond_resched(); >>> >>> + index = min(index, end); >>> pvec.nr = find_get_entries(mapping, index, >>> min(end - index, (pgoff_t)PAGEVEC_SIZE), >>> pvec.pages, indices); > > So let's all forget that patch, although it does help to highlight my > mistake in d0823576bf4b. (Oh, hey, let's all forget my mistake too!)
What patch? What mistake? :)
> Here's the 3.16-rc2 patch that I've now settled on (which will also > require a revert of current git's f00cdc6df7d7; well, not require the > revert, but this makes that redundant, and cannot be tested with it in). > > I've not yet had time to write up the patch description, nor to test > it fully; but thought I should get the patch itself into the open for > review and testing before then.
It seems to work here (tested 3.16-rc1 which didn't have f00cdc6df7d7 yet). Checking for end != -1 is indeed much more elegant solution than i_size. Thanks. So you can add my Tested-by.
> I've checked against v3.1 to see how it works out there: certainly > wouldn't apply cleanly (and beware: prior to v3.5's shmem_undo_range, > "end" was included in the range, not excluded), but the same > principles apply. Haven't checked the intermediates yet, will > probably leave those until each stable wants them - but if you've a > particular release in mind, please ask, or ask me to check your port.
I will try, thanks.
> I've included the mm/truncate.c part of it here, but that will be a > separate (not for -stable) patch when I post the finalized version. > > Hannes, a question for you please, I just could not make up my mind. > In mm/truncate.c truncate_inode_pages_range(), what should be done > with a failed clear_exceptional_entry() in the case of hole-punch? > Is that case currently depending on the rescan loop (that I'm about > to revert) to remove a new page, so I would need to add a retry for > that rather like the shmem_free_swap() one? Or is it irrelevant, > and can stay unchanged as below? I've veered back and forth, > thinking first one and then the other. > > Thanks, > Hugh > > --- > > mm/shmem.c | 19 ++++++++++--------- > mm/truncate.c | 14 +++++--------- > 2 files changed, 15 insertions(+), 18 deletions(-) > > --- 3.16-rc2/mm/shmem.c 2014-06-16 00:28:55.124076531 -0700 > +++ linux/mm/shmem.c 2014-06-26 15:41:52.704362962 -0700 > @@ -467,23 +467,20 @@ static void shmem_undo_range(struct inod > return; > > index = start; > - for ( ; ; ) { > + while (index < end) { > cond_resched(); > > pvec.nr = find_get_entries(mapping, index, > min(end - index, (pgoff_t)PAGEVEC_SIZE), > pvec.pages, indices); > if (!pvec.nr) { > - if (index == start || unfalloc) > + /* If all gone or hole-punch or unfalloc, we're done */ > + if (index == start || end != -1) > break; > + /* But if truncating, restart to make sure all gone */ > index = start; > continue; > } > - if ((index == start || unfalloc) && indices[0] >= end) { > - pagevec_remove_exceptionals(&pvec); > - pagevec_release(&pvec); > - break; > - } > mem_cgroup_uncharge_start(); > for (i = 0; i < pagevec_count(&pvec); i++) { > struct page *page = pvec.pages[i]; > @@ -495,8 +492,12 @@ static void shmem_undo_range(struct inod > if (radix_tree_exceptional_entry(page)) { > if (unfalloc) > continue; > - nr_swaps_freed += !shmem_free_swap(mapping, > - index, page); > + if (shmem_free_swap(mapping, index, page)) { > + /* Swap was replaced by page: retry */ > + index--; > + break; > + } > + nr_swaps_freed++; > continue; > } > > --- 3.16-rc2/mm/truncate.c 2014-06-08 11:19:54.000000000 -0700 > +++ linux/mm/truncate.c 2014-06-26 16:31:35.932433863 -0700 > @@ -352,21 +352,17 @@ void truncate_inode_pages_range(struct a > return; > > index = start; > - for ( ; ; ) { > + while (index < end) { > cond_resched(); > if (!pagevec_lookup_entries(&pvec, mapping, index, > - min(end - index, (pgoff_t)PAGEVEC_SIZE), > - indices)) { > - if (index == start) > + min(end - index, (pgoff_t)PAGEVEC_SIZE), indices)) { > + /* If all gone or hole-punch, we're done */ > + if (index == start || end != -1) > break; > + /* But if truncating, restart to make sure all gone */ > index = start; > continue; > } > - if (index == start && indices[0] >= end) { > - pagevec_remove_exceptionals(&pvec); > - pagevec_release(&pvec); > - break; > - } > mem_cgroup_uncharge_start(); > for (i = 0; i < pagevec_count(&pvec); i++) { > struct page *page = pvec.pages[i]; >
| |