From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from zeniv.linux.org.uk (zeniv.linux.org.uk [62.89.141.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 09D851AE877; Thu, 22 Jan 2026 17:12:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=62.89.141.173 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769101961; cv=none; b=QmTKbA/0Y5NM79qtjjIh0nA8QpWdhF1LdJmqG7fFLhjXQ9tR8kqSxlBGOMjvI8b1NIBCmlt9XEhAmjhC5vxN7MF8KZZ+UCg3od2jAQuSCiuicTDmgSHdzqiEsVuZHsiQpnpmpIZTf3muhrHUu3dpfPoGLAS+mSkmC8if4T0Ggmw= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769101961; c=relaxed/simple; bh=XXcNZspnoL4W/Wsbggllblj227uQM2K2Orf3kgz+3qg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=ATODYze5aTXxEoso0+T4g3fPdTx9LfDB41QMz6M5jnkDxgnaoRrVTGOXVNbKb3MjkiF1mvu5Q2nHJs7uTbrNqzuCTKza4k8CprV8/u1KepZ08j9NR3+xIxk4vhaRfRacDelCY6HJYBvp2pUMvKD3cegRa5CFCUb/ztUIdt5NV4U= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=zeniv.linux.org.uk; spf=none smtp.mailfrom=ftp.linux.org.uk; dkim=pass (2048-bit key) header.d=linux.org.uk header.i=@linux.org.uk header.b=rrFHvxbP; arc=none smtp.client-ip=62.89.141.173 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=zeniv.linux.org.uk Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ftp.linux.org.uk Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=linux.org.uk header.i=@linux.org.uk header.b="rrFHvxbP" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=linux.org.uk; s=zeniv-20220401; h=Sender:In-Reply-To:Content-Type: MIME-Version:References:Message-ID:Subject:Cc:To:From:Date:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=jhcqp5p/UzonWc8IjBJaz4qAzIJwvcWefuHCxyQBqqY=; b=rrFHvxbPB8PigX7BMUdALYMxgI jNI+GK0KQFjJvQn8Ho4weVvcChZQcYzmdjJ2RQuztwhLEpnbzbTnJQ4TdO4mdx4ZqO8IhG8U9GVkt OAUfisQbrkSXz9bT+0Uz2BnQQu51lROo1X+7G4AO7239PlbIBBCi56467IRZPda/sM+wJX6MStOWQ TnYFf9ik08K0WhKczuNV7gEeSi0BqwhU8Bb1iSA7OEJOnxA/qANyUBNFxlDlOeuS6Z4D2ekla8om/ 0v29J1Lz8RBSxM8ruvDIRH9gOM7Nc5Bu6yaraAxwSBhfvaif1gL50ACj4pzsnZzJGzh6EH/Ig/nFJ uPAfe/XA==; Received: from viro by zeniv.linux.org.uk with local (Exim 4.99.1 #2 (Red Hat Linux)) id 1viyG0-0000000FDdO-3Yr6; Thu, 22 Jan 2026 17:14:08 +0000 Date: Thu, 22 Jan 2026 17:14:08 +0000 From: Al Viro To: Qiliang Yuan Cc: brauner@kernel.org, jack@suse.cz, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, yuanql9@chinatelecom.cn Subject: Re: [PATCH] fs/file: optimize close_range() complexity from O(N) to O(Sparse) Message-ID: <20260122171408.GF3183987@ZenIV> References: <20260122163553.147673-1-realwujing@gmail.com> Precedence: bulk X-Mailing-List: linux-fsdevel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260122163553.147673-1-realwujing@gmail.com> Sender: Al Viro On Thu, Jan 22, 2026 at 11:35:53AM -0500, Qiliang Yuan wrote: > In close_range(), the kernel traditionally performs a linear scan over the > [fd, max_fd] range, resulting in O(N) complexity where N is the range size. > For processes with sparse FD tables, this is inefficient as it checks many > unallocated slots. > > This patch optimizes __range_close() by using find_next_bit() on the > open_fds bitmap to skip holes. This shifts the algorithmic complexity from > O(Range Size) to O(Active FDs), providing a significant performance boost > for large-range close operations on sparse file descriptor tables. > > Signed-off-by: Qiliang Yuan > Signed-off-by: Qiliang Yuan > --- > fs/file.c | 8 ++++++-- > 1 file changed, 6 insertions(+), 2 deletions(-) > > diff --git a/fs/file.c b/fs/file.c > index 0a4f3bdb2dec..c7c3ee03f8df 100644 > --- a/fs/file.c > +++ b/fs/file.c > @@ -777,13 +777,17 @@ static inline void __range_close(struct files_struct *files, unsigned int fd, > unsigned int max_fd) > { > struct file *file; > + struct fdtable *fdt; > unsigned n; > > spin_lock(&files->file_lock); > - n = last_fd(files_fdtable(files)); > + fdt = files_fdtable(files); Careful - that thing might be expanded and reallocated once you drop ->file_lock (i.e. every time you close anything). IOW, every time you regain the lock, you need to recalculate fdt. Other than that, looks sane.