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=-4.1 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS 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 45FC0C43466 for ; Thu, 6 Aug 2020 11:01:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 280142310A for ; Thu, 6 Aug 2020 11:01:26 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=themaw.net header.i=@themaw.net header.b="1krTwyay"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="q4byEJlG" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727933AbgHFFnY (ORCPT ); Thu, 6 Aug 2020 01:43:24 -0400 Received: from wnew3-smtp.messagingengine.com ([64.147.123.17]:44399 "EHLO wnew3-smtp.messagingengine.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726093AbgHFFnX (ORCPT ); Thu, 6 Aug 2020 01:43:23 -0400 Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailnew.west.internal (Postfix) with ESMTP id B1A6FC10; Thu, 6 Aug 2020 01:43:21 -0400 (EDT) Received: from mailfrontend1 ([10.202.2.162]) by compute2.internal (MEProxy); Thu, 06 Aug 2020 01:43:22 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=themaw.net; h= message-id:subject:from:to:cc:date:in-reply-to:references :content-type:mime-version:content-transfer-encoding; s=fm3; bh= Awpd/iaKMwO3xriBXgL7yRd6ZsbwGEwHcJ9iVbEAWAs=; b=1krTwyayDva0Q1mK m6P8LfWxFtP0gbC5ZJ4RXLrW4Xe3B+4DvLjbWeiGFj6KbGknmmigNG2sczhB0pcG 13nhBFr7d4/GOjO6ol86Fq6R0tks5VS0Y8ZasfxsrRZlVdjrKyq8YzfFcG6cksw2 fmiIS+SwhFecOGr6hs2vrTnBCgZZQAyTlJlvrrSvijUecgyWUFcre4aMZaTcWp8V o2ffi+CgrWkpBgpdrNBWsVFhZsR0EaRMyXM9kMFOYp48W1uOibG7iUx/HBqCzMqT 3qy2MXnvbgV1QDuMCz5n5aCDC7hrTdsaymx+RfzFPZP9v/yME/r2wN+n572rU40y 6Rdb5A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm3; bh=Awpd/iaKMwO3xriBXgL7yRd6ZsbwGEwHcJ9iVbEAW As=; b=q4byEJlGrJpU4Clt62ffMOHvyBeHqc8C49IeF6pTmi7wr38QHrxKsMNpl y5dLQJjehgjmpRhgdyrHqIJM96MnLMEqv2uIEfVh+6c/g4ip2shY47lR8d6Cmmlf OwIWw4AENYOwphwTZwXTQgCLOcFzMdAQseX4NITk+jA3z/mDNi6EVqnH4hA94Cex M4teDxu4YBDH0MvD4NF99T/BrjbDMC3Qv4FyRD4oxYERb2ttk1kc7Cj6nXM71eh/ J4RQK7qglO5YRf3zWv639KugPAyujWjKJ56z+0VJ2tvQNHtTQAqFRmKOTC7Z2CxZ GBj2WEEHNmbzR/5lxWi9FFCZQsfqw== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduiedrjeelgddutdduucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepkffuhffvffgjfhgtfggggfesthejredttderjeenucfhrhhomhepkfgrnhcu mfgvnhhtuceorhgrvhgvnhesthhhvghmrgifrdhnvghtqeenucggtffrrghtthgvrhhnpe effeettedvgeduvdevfeevfeettdffudduheeuiefhueevgfevheffledugefgjeenucfk phepuddukedrvddtkedrhedvrddutdelnecuvehluhhsthgvrhfuihiivgeptdenucfrrg hrrghmpehmrghilhhfrhhomheprhgrvhgvnhesthhhvghmrgifrdhnvght X-ME-Proxy: Received: from mickey.themaw.net (unknown [118.208.52.109]) by mail.messagingengine.com (Postfix) with ESMTPA id E5174328005E; Thu, 6 Aug 2020 01:43:14 -0400 (EDT) Message-ID: <61ad7b12b1d242247b066e6ffbf5f9382bc57b2a.camel@themaw.net> Subject: Re: [PATCH 06/18] fsinfo: Add a uniquifier ID to struct mount [ver #21] From: Ian Kent To: Matthew Wilcox , David Howells Cc: Miklos Szeredi , Al Viro , Linus Torvalds , Miklos Szeredi , Christian Brauner , Jann Horn , "Darrick J. Wong" , Karel Zak , Jeff Layton , Linux API , linux-fsdevel@vger.kernel.org, LSM , linux-kernel@vger.kernel.org Date: Thu, 06 Aug 2020 13:43:11 +0800 In-Reply-To: <20200805193303.GM23808@casper.infradead.org> References: <159646178122.1784947.11705396571718464082.stgit@warthog.procyon.org.uk> <159646183662.1784947.5709738540440380373.stgit@warthog.procyon.org.uk> <20200804104108.GC32719@miu.piliscsaba.redhat.com> <2306029.1596636828@warthog.procyon.org.uk> <2315925.1596641410@warthog.procyon.org.uk> <20200805193303.GM23808@casper.infradead.org> Content-Type: text/plain; charset="UTF-8" User-Agent: Evolution 3.34.4 (3.34.4-1.fc31) MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed, 2020-08-05 at 20:33 +0100, Matthew Wilcox wrote: > On Wed, Aug 05, 2020 at 04:30:10PM +0100, David Howells wrote: > > Miklos Szeredi wrote: > > > > > idr_alloc_cyclic() seems to be a good template for doing the > > > lower > > > 32bit allocation, and we can add code to increment the high 32bit > > > on > > > wraparound. > > > > > > Lots of code uses idr_alloc_cyclic() so I guess it shouldn't be > > > too > > > bad in terms of memory use or performance. > > > > It's optimised for shortness of path and trades memory for > > performance. It's > > currently implemented using an xarray, so memory usage is dependent > > on the > > sparseness of the tree. Each node in the tree is 576 bytes and in > > the worst > > case, each one node will contain one mount - and then you have to > > backfill the > > ancestry, though for lower memory costs. > > > > Systemd makes life more interesting since it sets up a whole load > > of > > propagations. Each mount you make may cause several others to be > > created, but > > that would likely make the tree more efficient. > > I would recommend using xa_alloc and ignoring the ID assigned from > xa_alloc. Looking up by unique ID is then a matter of iterating > every > mount (xa_for_each()) looking for a matching unique ID in the mount > struct. That's O(n) search, but it's faster than a linked list, and > we > don't have that many mounts in a system. How many is not many, 5000, 10000, I agree that 30000 plus is fairly rare, even for the autofs direct mount case I hope the implementation here will help to fix. Ian