Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18;
From:   Stephen Brennan <stephen.s.brennan@oracle.com>
To:     Al Viro <viro@zeniv.linux.org.uk>
Cc:     linux-kernel@vger.kernel.org, Luis Chamberlain <mcgrof@kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Jan Kara <jack@suse.cz>, linux-fsdevel@vger.kernel.org,
        Arnd Bergmann <arnd@arndb.de>,
        Amir Goldstein <amir73il@gmail.com>
Subject: Re: [PATCH v2 1/4] dcache: sweep cached negative dentries to the
 end of list of siblings
In-Reply-To: <Ygx0ZJbn3cdUwnQ1@zeniv-ca.linux.org.uk>
References: <20220209231406.187668-1-stephen.s.brennan@oracle.com>
 <20220209231406.187668-2-stephen.s.brennan@oracle.com>
 <YgSjo5wascR9mfnA@zeniv-ca.linux.org.uk>
 <875ypf8s5m.fsf@stepbren-lnx.us.oracle.com>
 <YgxvK03Q3wBVfLYS@zeniv-ca.linux.org.uk>
 <Ygx0ZJbn3cdUwnQ1@zeniv-ca.linux.org.uk>
Date:   Tue, 15 Feb 2022 23:43:33 -0800
Message-ID: <8735kj8dei.fsf@stepbren-lnx.us.oracle.com>
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?HxQvg8tJ/DuHFYiNG5vMpWoJl9aQjXvZTnKX6Tzs6p6L/GuAzu+9oHljJPs8?=
 =?us-ascii?Q?VLKwGMk/YLC1V+jO6BQZW11V550ryyOmU5PfprMFVK5ryI0c8ZcnQHE9eiAw?=
 =?us-ascii?Q?ZWPBslxU5HudiEoE3WPmb4q48+es9jlpxytadVOpxARywPUGLFjDzOFpiVs9?=
 =?us-ascii?Q?P4aJS41r5fGPTQVXHkLPDitStSqxsU+omd/D1X4BrPXy75dcH1iC0M4s5W8k?=
 =?us-ascii?Q?diY9ALTp8uX/Xo2gYQ2gGoDEN/6LmdhT/DilK+n+ccWCI+3bwvjPWUMUuPMt?=
 =?us-ascii?Q?ltXamPE8WHXvOdEUhGWWomOwhGmaLchXvpP8qbYZDYVPtqdYCeObGvPwfKCF?=
 =?us-ascii?Q?I0KXKN1qQtL1VeEGedQ7gGcb3MfPgBvF4g4eojkqkkNdh6fts6HUET6hosIB?=
 =?us-ascii?Q?TyJnpsV72fzmAmbStPU4Sdqii44ARDElHrar/Akf4th/B3FZkgVgNB5lYSnL?=
 =?us-ascii?Q?BB5xW9213v1iPc0F8YvOPOxBxUSoQCTRwyrCxECnXuvnfUPW/NXEl/+2onYf?=
 =?us-ascii?Q?MBCaoFOG8j58cmPAix/qFk9ySsGzupa0Wuno71e+XFdYcIyQI0yrUFLT4wEr?=
 =?us-ascii?Q?bA6auhhXSKDItc/xfxx2VojzoT3WQ0PJkKRfqtqonKAAGrlhvzbEe2G6Hr3P?=
 =?us-ascii?Q?t12QiW0cODvNXMPGFzFtDTN2ZOIjD2EIzmI1h9qq5QtR9nrf89ahqkRMSUQR?=
 =?us-ascii?Q?ifOMJfU3M6Tl30xRI/o9DBrW/MFlwdrwC0+zqJpSn3VaueK1ZnAu37VWsCt8?=
 =?us-ascii?Q?rKTs37npJqAZbGNQ23SPzv2Q3ANXFi6fsZOhkmoOASouQ1fwNzy6F49EWDlo?=
 =?us-ascii?Q?rQnxQS3aG/UkzoYPHGjlvBp1gUDwiAGuH6u6X9vCPUhgsx3Yzi/F1A+BrI8y?=
 =?us-ascii?Q?N011nLq+SPX0TAJ42jIeH8+/gmcenPoGVyBHZqg82Z+vLPbt9YW+NvJgdY6L?=
 =?us-ascii?Q?57wrthBBTm3zHbUBlSdwAD7p2OQdTafQQPo1vNUYzWZY9iw0BNPj52M0eLjF?=
 =?us-ascii?Q?cluOg7QK31+qYL4TxkVSQxPossiTu/BWPxDBX0mc6YRPQU9IKNz0I5mJFCra?=
 =?us-ascii?Q?TH4ImTtxcYXOd33NLvb0hl4Sz8thLHDAOMv9/XcK4/TyRUl+qZZTu3AIMT8q?=
 =?us-ascii?Q?qhOS9YTMinqu/OmWGGER9DO1e0KKmP4d9ruAIprciCdMyenGzzHua3Ljjg86?=
 =?us-ascii?Q?y6BXZifCTM2lleBlSkzC2xeCGiZ/GNS30m/dip6WcIPSXol0OwMAch1x4ytP?=
 =?us-ascii?Q?We7NLJtow/N5GJUcpMV8+ggsz1rAWYkv84Y0xBmzCuX01M50WnYcyHKyBzgY?=
 =?us-ascii?Q?/weTntrpXFvjjfaHOB7Umt3p94WrWm3+GWYLqZeUHmgo0h6Cq53L5IhHnG2n?=
 =?us-ascii?Q?xU5cC2wVjc+SReNauVu3ydwVZubNebYOyegScbVNCI3Xm6N9egN8XyzCuNIm?=
 =?us-ascii?Q?Rm3hlEkLmqUf408KvixxsBvfVX+NiYzyag9NKqXscHlXebbFdwvKK9/HPcD9?=
 =?us-ascii?Q?c6gEYZhW6dP2Gve5gplEdZRGwtK3OFSqnQh1YBiHDHuZj6fZearQ1zhCVCCr?=
 =?us-ascii?Q?pjvuysDRsadXB9ifuIkiKEhgh5Zw4MR6jhnvklQX2RX1PZ0DPq+Hb+NAXsb7?=
 =?us-ascii?Q?NnEmQ9Hd8eE+/4fHLYZOzI2uizglhmyBYMRLfgHPNGJ2tq+6TYxD1dgk4dHg?=
 =?us-ascii?Q?Yj16BQ=3D=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 58ae9160-1bb2-42dc-dae8-08d9f1200a84
X-MS-Exchange-CrossTenant-AuthSource: CH2PR10MB4166.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Feb 2022 07:43:37.1124
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: HyobFdeyPWKUDqaVmyeY+VMWNwKCDBxt5oACPHA0vCeKHFER7wctGkoglUB34ldwZjY7aDu/aGpTHpv+fpKtgdqaIt3tOKbmTbs+W6u9QU8=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB3421
X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10259 signatures=675924
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 spamscore=0
 phishscore=0 bulkscore=0 suspectscore=0 malwarescore=0 mlxscore=0
 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2201110000 definitions=main-2202160042
X-Proofpoint-ORIG-GUID: uRrK29QfnPgYc-vbUWbMypHPMgTLcQQG
X-Proofpoint-GUID: uRrK29QfnPgYc-vbUWbMypHPMgTLcQQG
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,
	MAILING_LIST_MULTI,RDNS_NONE,SPF_HELO_NONE,T_SCC_BODY_TEXT_LINE
	autolearn=no autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Al Viro <viro@zeniv.linux.org.uk> writes:
> On Wed, Feb 16, 2022 at 03:27:39AM +0000, Al Viro wrote:
>> On Tue, Feb 15, 2022 at 06:24:53PM -0800, Stephen Brennan wrote:
>>
>> > It seems to me that, if we had taken a reference on child by
>> > incrementing the reference count prior to unlocking it, then
>> > dentry_unlist could never have been called, since we would never have
>> > made it into __dentry_kill. child would still be on the list, and any
>> > cursor (or sweep_negative) list updates would now be reflected in
>> > child->d_child.next. But dput is definitely not safe while holding a
>> > lock on a parent dentry (even more so now thanks to my patch), so that
>> > is out of the question.
>> >
>> > Would dput_to_list be an appropriate solution to that issue? We can
>> > maintain a dispose list in d_walk and then for any dput which really
>> > drops the refcount to 0, we can handle them after d_walk is done. It
>> > shouldn't be that many dentries anyway.
>>
>> 	Interesting idea, but... what happens to behaviour of e.g.
>> shrink_dcache_parent()?  You'd obviously need to modify the test in
>> select_collect(), but then the selected dentries become likely candidates
>> for d_walk() itself wanting to move them over to its internal shrink list.
>> OTOH, __dput_to_list() will just decrement the count and skip the sucker
>> if it's already on a shrink list...
>>
>> 	It might work, but it really needs a careful analysis wrt.
>> parallel d_walk().  What happens when you have two threads hitting
>> shrink_dcache_parent() on two different places, one being an ancestor
>> of another?  That can happen in parallel, and currently it does work
>> correctly, but that's fairly delicate and there are places where a minor
>> change could turn O(n) into O(n^2), etc.
>>
>> 	Let me think about that - I'm not saying it's hopeless, and it
>> would be nice to avoid that subtlety in dentry_unlist(), but there
>> might be dragons.
>
> PS: another obvious change is that d_walk() would become blocking.
> So e.g.
>
> int path_has_submounts(const struct path *parent)
> {
>         struct check_mount data = { .mnt = parent->mnt, .mounted = 0 };
>
> 	read_seqlock_excl(&mount_lock);
> 	d_walk(parent->dentry, &data, path_check_mount);
> 	read_sequnlock_excl(&mount_lock);
>
> 	return data.mounted;
> }
>
> would need a rework - d_walk() is under a spinlock here.  Another
> potential headache in that respect is d_genocide() - currently non-blocking,
> with this change extremely likely to do evictions.  That, however, is
> not a problem for current in-tree callers - they are all shortly followed
> by shrink_dcache_parent() or equivalents.
>
> path_has_submounts(), though...  I'd really hate to reintroduce the
> "call this on entry/call this on exit" callbacks.  Perhaps it would
> be better to pass the dispose list to d_walk() and have the callers
> deal with evictions?  For that matter, shrink_dcache_parent() and
> friends would be just fine passing the same list they are collecting
> into.
>
> <looks at path_has_submounts() callers>
> *growl*
> autofs_d_automount() has it called under sbi->fs_lock.  So we'd need
> to take the disposal all the way out there, and export shrink_dentry_list()
> while we are at it.  Not pretty ;-/
>
> And no, we can't make the disposal async, so offloading it to a worker or
> thread is not feasible...

Hm, making d_walk blocking seems like a real barrier to some users that
use d_walk as a lightweight check (e.g. path_has_submounts) which isn't
sensitive to retries. But other callers like shrink_dcache_parent are
okay with blocking, and already have a dispose list, but they want to
avoid retries.

What if we gave d_walk an optional "dispose" list parameter? For those
that provide it, we take references to ensure that child doesn't get
killed out from under us. For those which don't, if child does get
killed, then they are forced to retry from the beginning of
this_parent->d_subdirs. This wouldn't eliminate the careful analysis
necessary for parallel d_walk when both provide dispose lists. But it
would avoid making all d_walk callers pay the penalty of becoming
blocking.

Here's a super rough sketch of what I mean (it's late at night, no
obvious syntax errors but it won't compile unless all the callers are
updated):

diff --git a/fs/dcache.c b/fs/dcache.c
index e98079ed86be..307d32f023c8 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -1408,11 +1408,12 @@ enum d_walk_ret {
  * @enter:	callback when first entering the dentry
  *
  * The @enter() callbacks are called with d_lock held.
  */
 static void d_walk(struct dentry *parent, void *data,
-		   enum d_walk_ret (*enter)(void *, struct dentry *))
+		   enum d_walk_ret (*enter)(void *, struct dentry *),
+		   struct list_head *dispose)
 {
 	struct dentry *this_parent;
 	struct list_head *next;
 	unsigned seq = 0;
 	enum d_walk_ret ret;
@@ -1483,23 +1484,30 @@ static void d_walk(struct dentry *parent, void *data,
 ascend:
 	if (this_parent != parent) {
 		struct dentry *child = this_parent;
 		this_parent = child->d_parent;
 
-		spin_unlock(&child->d_lock);
-		spin_lock(&this_parent->d_lock);
+		if (dispose) {
+			child->d_lockref.count += 1;
+			spin_unlock(&child->d_lock);
+			spin_lock(&this_parent->d_lock);
+			dput_to_list(child, dispose);
+		} else {
+			spin_unlock(&child->d_lock);
+			spin_lock(&this_parent->d_lock);
+		}
 
 		/* might go back up the wrong parent if we have had a rename. */
 		if (need_seqretry(&rename_lock, seq))
 			goto rename_retry;
-		/* go into the first sibling still alive */
-		do {
-			next = child->d_child.next;
-			if (next == &this_parent->d_subdirs)
-				goto ascend;
-			child = list_entry(next, struct dentry, d_child);
-		} while (unlikely(child->d_flags & DCACHE_DENTRY_KILLED));
+
+		/* child was killed, its next pointers may now be stale, retry */
+		if (child->d_flags & DCACHE_DENTRY_KILLED)
+			goto killed_retry;
+
+		next = child->d_child.next;
+		child = list_entry(next, struct dentry, d_child);
 		rcu_read_unlock();
 		goto resume;
 	}
 	if (need_seqretry(&rename_lock, seq))
 		goto rename_retry;
@@ -1516,10 +1524,18 @@ static void d_walk(struct dentry *parent, void *data,
 	BUG_ON(seq & 1);
 	if (!retry)
 		return;
 	seq = 1;
 	goto again;
+
+killed_retry:
+	rcu_read_unlock();
+	BUG_ON(dispose);
+	if (!retry)
+		return;
+	goto repeat;
+
 }
 
 struct check_mount {
 	struct vfsmount *mnt;
 	unsigned int mounted;