linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
To: Matthew Wilcox <willy@infradead.org>
Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org,
	linux-mm@kvack.org, Alexander Viro <viro@zeniv.linux.org.uk>,
	Waiman Long <longman@redhat.com>
Subject: Re: [PATCH RFC 8/8] dcache: prevent flooding with negative dentries
Date: Fri, 8 May 2020 19:29:40 +0300	[thread overview]
Message-ID: <be7ae157-9c87-7ee7-e669-f1eb448b0cbf@yandex-team.ru> (raw)
In-Reply-To: <20200508145659.GQ16070@bombadil.infradead.org>

On 08/05/2020 17.56, Matthew Wilcox wrote:
> On Fri, May 08, 2020 at 03:23:33PM +0300, Konstantin Khlebnikov wrote:
>> This patch implements heuristic which detects such scenarios and prevents
>> unbounded growth of completely unneeded negative dentries. It keeps up to
>> three latest negative dentry in each bucket unless they were referenced.
>>
>> At first dput of negative dentry when it swept to the tail of siblings
>> we'll also clear it's reference flag and look at next dentries in chain.
>> Then kill third in series of negative, unused and unreferenced denries.
>>
>> This way each hash bucket will preserve three negative dentry to let them
>> get reference and survive. Adding positive or used dentry into hash chain
>> also protects few recent negative dentries. In result total size of dcache
>> asymptotically limited by count of buckets and positive or used dentries.
>>
>> This heuristic isn't bulletproof and solves only most practical case.
>> It's easy to deceive: just touch same random name twice.
> 
> I'm not sure if that's "easy to deceive" ... My concern with limiting
> negative dentries is something like a kernel compilation where there
> are many (11 for mm/mmap.c, 9 in general) and there will be a lot of
> places where <linux/fs.h> does not exist
> 
> -isystem /usr/lib/gcc/x86_64-linux-gnu/9/include
> -I../arch/x86/include
> -I./arch/x86/include/generated
> -I../include
> -I./include
> -I../arch/x86/include/uapi
> -I./arch/x86/include/generated/uapi
> -I../include/uapi
> -I./include/generated/uapi
> -I ../mm
> -I ./mm
> 
> So it'd be good to know that kernel compilation times are unaffected by
> this patch.
> 

It's very unlikely that this patches changes anything for compilation.
Or any other scenario with sane amount and rate of appearing new names.

This trims only dentries which never been accessed twice.
Keeping 3 dentries per bucket gives high chances that all of them get
reference bit and stay in cache until shrinker bury them.

To get false positive in this heuristic - multiple newly created
negative dentries must hit one bucket in short period of time.
I.e. at least three hash collisions is required.

  reply	other threads:[~2020-05-08 16:29 UTC|newest]

Thread overview: 24+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-05-08 12:23 [PATCH RFC 0/8] dcache: increase poison resistance Konstantin Khlebnikov
2020-05-08 12:23 ` [PATCH RFC 1/8] dcache: show count of hash buckets in sysctl fs.dentry-state Konstantin Khlebnikov
2020-05-08 14:49   ` Waiman Long
2020-05-08 16:16     ` Konstantin Khlebnikov
2020-05-08 19:05       ` Waiman Long
2020-05-08 19:38         ` Konstantin Khlebnikov
2020-05-08 20:00           ` Waiman Long
2020-05-08 20:03             ` Matthew Wilcox
2020-05-08 12:23 ` [PATCH RFC 2/8] selftests: add stress testing tool for dcache Konstantin Khlebnikov
2020-05-13  1:52   ` Dave Chinner
2020-05-08 12:23 ` [PATCH RFC 3/8] dcache: sweep cached negative dentries to the end of list of siblings Konstantin Khlebnikov
2020-05-08 19:38   ` Waiman Long
2020-05-08 12:23 ` [PATCH RFC 4/8] fsnotify: stop walking child dentries if remaining tail is negative Konstantin Khlebnikov
2020-05-08 12:23 ` [PATCH RFC 5/8] dcache: add action D_WALK_SKIP_SIBLINGS to d_walk() Konstantin Khlebnikov
2020-05-08 12:23 ` [PATCH RFC 6/8] dcache: stop walking siblings if remaining dentries all negative Konstantin Khlebnikov
2020-05-08 12:23 ` [PATCH RFC 7/8] dcache: push releasing dentry lock into sweep_negative Konstantin Khlebnikov
2020-05-08 12:23 ` [PATCH RFC 8/8] dcache: prevent flooding with negative dentries Konstantin Khlebnikov
2020-05-08 14:56   ` Matthew Wilcox
2020-05-08 16:29     ` Konstantin Khlebnikov [this message]
2020-05-08 21:07   ` Waiman Long
2020-12-09 23:01 ` [PATCH RFC 0/8] dcache: increase poison resistance Junxiao Bi
     [not found]   ` <CALYGNiN2F8gcKX+2nKOi1tapquJWfyzUkajWxTqgd9xvd7u1AA@mail.gmail.com>
2020-12-13 18:49     ` Junxiao Bi
     [not found]       ` <CALYGNiM8Fp=ZV8S6c2L50ne1cGhE30PrT-C=4nfershvfAgP+Q@mail.gmail.com>
2020-12-14 23:10         ` Junxiao Bi
2020-12-16 18:46           ` Junxiao Bi

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=be7ae157-9c87-7ee7-e669-f1eb448b0cbf@yandex-team.ru \
    --to=khlebnikov@yandex-team.ru \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=longman@redhat.com \
    --cc=viro@zeniv.linux.org.uk \
    --cc=willy@infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).