Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752748AbcJEJZ7 (ORCPT ); Wed, 5 Oct 2016 05:25:59 -0400 Received: from gum.cmpxchg.org ([85.214.110.215]:57618 "EHLO gum.cmpxchg.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750807AbcJEJZ4 (ORCPT ); Wed, 5 Oct 2016 05:25:56 -0400 Date: Wed, 5 Oct 2016 11:25:34 +0200 From: Johannes Weiner To: Linus Torvalds Cc: Andrew Morton , Antonio SJ Musumeci , Miklos Szeredi , Dave Jones , Oleg Nesterov , Dave Chinner , Michal Hocko , Jan Kara , Linux Kernel Mailing List , stable Subject: Re: BUG_ON() in workingset_node_shadows_dec() triggers Message-ID: <20161005092534.GA20174@cmpxchg.org> References: <20161004093216.GA21170@cmpxchg.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.7.0 (2016-08-17) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 11708 Lines: 313 On Tue, Oct 04, 2016 at 06:21:37PM -0700, Linus Torvalds wrote: > On Tue, Oct 4, 2016 at 2:32 AM, Johannes Weiner wrote: > > > > In the workingset code, if we detect radix tree nodes in a state in > > which they shouldn't be on the shadow node LRU, we could simply warn, > > abort the reclaim process and leave them off the LRU. Something like > > the below patch. > > I don't hate that patch, but I wonder why the counts get corrupted and > the workingset_node_shadows_dec() thing triggered in the first place. Okay, I kept digging, and I think I found the culprit: yes, the actual bug is ancient (3.15), but also requires a fairly specific combination of access pattern and memory pressure to trigger, which is why testing didn't reveal it right away. The symptom before the sanity check was an occasionally leaked radix tree node, which is mostly harmless and hard to notice [ really drives home the BUG_ON point, doesn't it... ] The problem is in the way we account shadow entries inside the upper bits of node->count behind the back of the radix tree code. We don't use the insert and delete functions directly from the page cache and then do our own node->count updates. And other than that the radix tree code mostly accounts only its own childpointers in node->count and doesn't make assumptions about how user entries are accounted. The notable exception is during tree extension: when there is a single entry at index 0, it's stored as a direct pointer from root->rnode. A fault at a higher index will copy that direct entry to a proper node and do node->count = 1. That's wrong if the direct entry is a shadow. So the scenario required to trigger this issue is this: you need a file with only the first page faulted in and then evicted before touching another page in the file. When that first page faults back, that's when the counter underflows. Here is a reproducer that triggers the warning instantly for me: --- /* * When index 0 is present, then evicted, rnode is a direct pointer to * a shadow entry. Extending the tree from there does the wrong thing * by setting node->count = 1; that's the page counter bits, it should * be setting the upper shadow bits. When index 0 faults back and we * try to remove the shadow entry, the shadow counter is 0. */ #include #include #include #include #include /* Set to slightly bigger than memory */ #define PRESSURE_SIZE (12UL << 30) int main(void) { unsigned long off; char buf[4096]; int fd1, fd2; fd1 = open("test-twopages", O_CREAT|O_RDWR); unlink("test-twopages"); ftruncate(fd1, 4096); /* fault page at index 0 */ pread(fd1, buf, 4096, 0); /* create pressure to plant shadow at fd1's index 0 (knock on wood) */ fd2 = open("test-pressure", O_CREAT|O_RDWR); unlink("test-pressure"); ftruncate(fd2, PRESSURE_SIZE); for (off = 0; off < PRESSURE_SIZE; off += 4096) read(fd2, buf, 4096); close(fd2); /* fault page at index 1, extending tree sets wrong node->count */ ftruncate(fd1, 8192); pread(fd1, buf, 4096, 4096); /* refault index 0, deletes shadow with no shadows in node->count */ pread(fd1, buf, 4096, 0); close(fd1); return 0; } --- That radix tree node management needs some cleaning up. It probably makes sense to split node->count into actually separate members for clarity, and then add a root tag to distinguish shadows from regular entries in root->rnode. I have to think about this more, the current situation is too fragile and ugly. But in the meantime, there is an obvious fix: don't ever store shadow entries in root->rnode, seeing as we need nodes for proper accounting. It means we temporarily lose the ability to detect refaults from single-page files, but it's probably better to keep the stable fix small and restore that functionality in a new release. Patch below. NOTE: I'm traveling without access to my test rig right now and so I have only lightly tested this on my laptop. I'm also jetlagged like crazy, so please triple check my thinking. The patch does fix the reproducer case and has otherwise been stable here. --- >From 5e948543a814183f04c30b072707300a94deb6c7 Mon Sep 17 00:00:00 2001 From: Johannes Weiner Date: Tue, 4 Oct 2016 22:02:08 +0200 Subject: [PATCH] mm: filemap: don't plant shadow entries without radix tree node When the underflow checks were added to workingset_node_shadow_dec(), they triggered immediately: kernel BUG at ./include/linux/swap.h:276! invalid opcode: 0000 [#1] SMP Modules linked in: isofs usb_storage fuse xt_CHECKSUM ipt_MASQUERADE nf_nat_masquerade_ipv4 tun nf_conntrack_netbios_ns nf_conntrack_broadcast ip6t_REJECT nf_reject_ipv6 soundcore wmi acpi_als pinctrl_sunrisepoint kfifo_buf tpm_tis industrialio acpi_pad pinctrl_intel tpm_tis_core tpm nfsd auth_rpcgss nfs_acl lockd grace sunrpc dm_crypt CPU: 0 PID: 20929 Comm: blkid Not tainted 4.8.0-rc8-00087-gbe67d60ba944 #1 Hardware name: System manufacturer System Product Name/Z170-K, BIOS 1803 05/06/2016 task: ffff8faa93ecd940 task.stack: ffff8faa7f478000 RIP: page_cache_tree_insert+0xf1/0x100 RSP: 0018:ffff8faa7f47bab0 EFLAGS: 00010046 RAX: 0000000000000001 RBX: ffff8faadfaf8c18 RCX: ffff8fa8737b5488 RDX: 0000000000000000 RSI: 0000000000000000 RDI: ffff8fa8737b4b48 RBP: ffff8faa7f47bae8 R08: 0000000000000012 R09: ffff8fa8737b54b0 R10: 0000000000000040 R11: ffff8fa8737b54b0 R12: ffffea000b1ad580 R13: 0000000000000000 R14: ffff8faa7f47bb48 R15: ffffea000b1ad580 FS: 00007ffba3a61780(0000) GS:ffff8faaf6c00000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 00007ffba31a5430 CR3: 00000002c6d40000 CR4: 00000000003406f0 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 Call Trace: __add_to_page_cache_locked+0x12e/0x270 add_to_page_cache_lru+0x4e/0xe0 mpage_readpages+0x112/0x1d0 blkdev_readpages+0x1d/0x20 __do_page_cache_readahead+0x1ad/0x290 force_page_cache_readahead+0xaa/0x100 page_cache_sync_readahead+0x3f/0x50 generic_file_read_iter+0x5af/0x740 blkdev_read_iter+0x35/0x40 __vfs_read+0xe1/0x130 vfs_read+0x96/0x130 SyS_read+0x55/0xc0 entry_SYSCALL_64_fastpath+0x13/0x8f Code: 03 00 48 8b 5d d8 65 48 33 1c 25 28 00 00 00 44 89 e8 75 19 48 83 c4 18 5b 41 5c 41 5d 41 5e 5d c3 0f 0b 41 bd ef ff ff ff eb d7 <0f> 0b e8 88 68 ef ff 0f 1f 84 00 RIP page_cache_tree_insert+0xf1/0x100 This is a long-standing bug in the way shadow entries are accounted in the radix tree nodes. The shrinker needs to know when radix tree nodes contain only shadow entries, no pages, so node->count is split in half to count shadows in the upper bits and pages in the lower bits. Unfortunately, the radix tree implementation doesn't know of this and assumes all entries are in node->count. When there is a shadow entry directly in root->rnode and the tree is later extended, the radix tree implementation will copy that entry into the new node and and bump its node->count, i.e. increases the page count bits. Once the shadow gets removed and we subtract from the upper counter, node->count underflows and triggers the warning. Afterwards, without node->count reaching 0 again, the radix tree node is leaked. Limit shadow entries to when we have actual radix tree nodes and can count them properly. That means we lose the ability to detect refaults from files that had only the first page faulted in at eviction time. Fixes: 449dd6984d0e ("mm: keep page cache radix tree nodes in check") Signed-off-by: Johannes Weiner --- include/linux/radix-tree.h | 6 +++--- lib/radix-tree.c | 14 +++----------- mm/filemap.c | 46 ++++++++++++++++++++++++++++++---------------- 3 files changed, 36 insertions(+), 30 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 4c45105dece3..52b97db93830 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -280,9 +280,9 @@ bool __radix_tree_delete_node(struct radix_tree_root *root, struct radix_tree_node *node); void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *); void *radix_tree_delete(struct radix_tree_root *, unsigned long); -struct radix_tree_node *radix_tree_replace_clear_tags( - struct radix_tree_root *root, - unsigned long index, void *entry); +void radix_tree_clear_tags(struct radix_tree_root *root, + struct radix_tree_node *node, + void **slot); unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items); diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 91f0727e3cad..8e6d552c40dd 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1583,15 +1583,10 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) } EXPORT_SYMBOL(radix_tree_delete); -struct radix_tree_node *radix_tree_replace_clear_tags( - struct radix_tree_root *root, - unsigned long index, void *entry) +void radix_tree_clear_tags(struct radix_tree_root *root, + struct radix_tree_node *node, + void **slot) { - struct radix_tree_node *node; - void **slot; - - __radix_tree_lookup(root, index, &node, &slot); - if (node) { unsigned int tag, offset = get_slot_offset(node, slot); for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) @@ -1600,9 +1595,6 @@ struct radix_tree_node *radix_tree_replace_clear_tags( /* Clear root node tags */ root->gfp_mask &= __GFP_BITS_MASK; } - - radix_tree_replace_slot(slot, entry); - return node; } /** diff --git a/mm/filemap.c b/mm/filemap.c index c17395825650..5bcadb6471bf 100644 --- a/mm/filemap.c +++ b/mm/filemap.c @@ -169,33 +169,35 @@ static int page_cache_tree_insert(struct address_space *mapping, static void page_cache_tree_delete(struct address_space *mapping, struct page *page, void *shadow) { - struct radix_tree_node *node; int i, nr = PageHuge(page) ? 1 : hpage_nr_pages(page); VM_BUG_ON_PAGE(!PageLocked(page), page); VM_BUG_ON_PAGE(PageTail(page), page); VM_BUG_ON_PAGE(nr != 1 && shadow, page); - if (shadow) { - mapping->nrexceptional += nr; - /* - * Make sure the nrexceptional update is committed before - * the nrpages update so that final truncate racing - * with reclaim does not see both counters 0 at the - * same time and miss a shadow entry. - */ - smp_wmb(); - } - mapping->nrpages -= nr; - for (i = 0; i < nr; i++) { - node = radix_tree_replace_clear_tags(&mapping->page_tree, - page->index + i, shadow); + struct radix_tree_node *node; + void **slot; + + __radix_tree_lookup(&mapping->page_tree, page->index + i, + &node, &slot); + + radix_tree_clear_tags(&mapping->page_tree, node, slot); + if (!node) { VM_BUG_ON_PAGE(nr != 1, page); - return; + /* + * We need a node to properly account shadow + * entries. Don't plant any without. XXX + */ + shadow = NULL; } + radix_tree_replace_slot(slot, shadow); + + if (!node) + break; + workingset_node_pages_dec(node); if (shadow) workingset_node_shadows_inc(node); @@ -219,6 +221,18 @@ static void page_cache_tree_delete(struct address_space *mapping, &node->private_list); } } + + if (shadow) { + mapping->nrexceptional += nr; + /* + * Make sure the nrexceptional update is committed before + * the nrpages update so that final truncate racing + * with reclaim does not see both counters 0 at the + * same time and miss a shadow entry. + */ + smp_wmb(); + } + mapping->nrpages -= nr; } /* -- 2.10.0