From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.4 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE, SPF_PASS,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id DB298C38A2A for ; Fri, 8 May 2020 16:29:46 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 938C820CC7 for ; Fri, 8 May 2020 16:29:45 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=yandex-team.ru header.i=@yandex-team.ru header.b="G22ceIVJ" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 938C820CC7 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=yandex-team.ru Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 580C4900002; Fri, 8 May 2020 12:29:45 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 530308E0003; Fri, 8 May 2020 12:29:45 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 46CF3900002; Fri, 8 May 2020 12:29:45 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0209.hostedemail.com [216.40.44.209]) by kanga.kvack.org (Postfix) with ESMTP id 314068E0003 for ; Fri, 8 May 2020 12:29:45 -0400 (EDT) Received: from smtpin03.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id D512C181AEF10 for ; Fri, 8 May 2020 16:29:44 +0000 (UTC) X-FDA: 76794087888.03.pest80_37da25909a126 X-HE-Tag: pest80_37da25909a126 X-Filterd-Recvd-Size: 4605 Received: from forwardcorp1p.mail.yandex.net (forwardcorp1p.mail.yandex.net [77.88.29.217]) by imf47.hostedemail.com (Postfix) with ESMTP for ; Fri, 8 May 2020 16:29:43 +0000 (UTC) Received: from mxbackcorp1j.mail.yandex.net (mxbackcorp1j.mail.yandex.net [IPv6:2a02:6b8:0:1619::162]) by forwardcorp1p.mail.yandex.net (Yandex) with ESMTP id A02312E1489; Fri, 8 May 2020 19:29:41 +0300 (MSK) Received: from myt5-70c90f7d6d7d.qloud-c.yandex.net (myt5-70c90f7d6d7d.qloud-c.yandex.net [2a02:6b8:c12:3e2c:0:640:70c9:f7d]) by mxbackcorp1j.mail.yandex.net (mxbackcorp/Yandex) with ESMTP id 79lEU9qBfi-TeWmumsJ; Fri, 08 May 2020 19:29:41 +0300 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex-team.ru; s=default; t=1588955381; bh=jmR/DsNk+b5hvFTl8iWVW5V6hZXuHrGwKPYXyFBJJ6c=; h=In-Reply-To:Message-ID:From:Date:References:To:Subject:Cc; b=G22ceIVJgcTLXW32v7RDdWj71AvNDdzYWSFqTWcdPKxlh1t8KvA2HhLLWAxZKWWlR /nQgf10nznYePpe1EiEIsyWb+zqOd7hnbo6WECRHMRzZtZVmYJlLbe1AA+XFjcypRs Nab5knMpKr66+N1FZPVzCuKUjIm/jymF5v5XumXk= Authentication-Results: mxbackcorp1j.mail.yandex.net; dkim=pass header.i=@yandex-team.ru Received: from dynamic-vpn.dhcp.yndx.net (dynamic-vpn.dhcp.yndx.net [2a02:6b8:b080:7008::1:4]) by myt5-70c90f7d6d7d.qloud-c.yandex.net (smtpcorp/Yandex) with ESMTPSA id Fvbdd2NnKu-TeW8lndv; Fri, 08 May 2020 19:29:40 +0300 (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) (Client certificate not present) Subject: Re: [PATCH RFC 8/8] dcache: prevent flooding with negative dentries To: Matthew Wilcox Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, Alexander Viro , Waiman Long References: <158893941613.200862.4094521350329937435.stgit@buzz> <158894061332.200862.9812452563558764287.stgit@buzz> <20200508145659.GQ16070@bombadil.infradead.org> From: Konstantin Khlebnikov Message-ID: Date: Fri, 8 May 2020 19:29:40 +0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0 MIME-Version: 1.0 In-Reply-To: <20200508145659.GQ16070@bombadil.infradead.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-CA Content-Transfer-Encoding: 7bit X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 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.