From nobody Sun Feb 8 20:32:45 2026 Received: from mail-dl1-f44.google.com (mail-dl1-f44.google.com [74.125.82.44]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id F340E3BF2FB for ; Thu, 22 Jan 2026 16:36:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.44 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769099768; cv=none; b=BiEoAzjtYyDmhrh9ZfI8Crbl912Mo/D0FZx9i9qpjh0efFS8tJbuBGw4fADiC/nyVGW+i9TMEi852PSxyOViHn4oUNvBMQAMtuISoa508rLc+dfvi4xYfDDkzK9KCy2nI3wfKkpwSKgGOh8YQ/sFiu+iNUO4RPv20rF+NFWKV74= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769099768; c=relaxed/simple; bh=slb/GGM+dDvhj/vRE0/DHMfg6wYcuMLRVsOLLU+nlSc=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=qnqnd2QLRi0AmCNE0CnrgpJcE/mvqaJS1RjlXH2JQU+0FI3fEmnXEooEHPNfLZQa6HZYB+gcO6BUbQ0m7IFw+HwvpBjaK/RMhCl41+2QhdwD0qqfeL3OO40Uva5BUh3ONgZ3WDlcLzH4JVMSm7278w7uH+1Gs4WKfC5s6otZ9WI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=E/Wwrzyw; arc=none smtp.client-ip=74.125.82.44 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="E/Wwrzyw" Received: by mail-dl1-f44.google.com with SMTP id a92af1059eb24-121a0bcd364so2113177c88.0 for ; Thu, 22 Jan 2026 08:36:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1769099760; x=1769704560; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=78HgOhT4Kw2q12pLeDbNDTx/e26eJDuxp0giAwSWLiw=; b=E/Wwrzyw4ja0O0zAFgX9K74S0kBrTf2YDlPK3LOLp1vOD0PCJmHmlIYYBHaWrCKwmR XLYrBAu2n92XCwp6WkM8qO9EjPvukHKKWUx5YStA2txzblw0Rx2/o4htYlabVt9SrMoe X2+oA6VXikfoQ+i2muP7I17EeNT4nNpWKM7wDRhFZ5YuTV12azA20A4v4l96A3sa1BDr 8a9O661PUaVR8ZdXqzQvAPZ6hhnmdg+mCUh+85/nCfE7yKKe6z0wsNbLdF73D0BoWUhy UT6pbvkSSORDiusDTEXzRO/uHBYM705VdtufKmp0xu4/11VGFHyehA7makX0TkHbeZ7Y gk7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1769099760; x=1769704560; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=78HgOhT4Kw2q12pLeDbNDTx/e26eJDuxp0giAwSWLiw=; b=Xkfq4dobBYjx7UfAC9nDKA9PfaRPTDR+deN3RV4HlpxBW780Khjci3RZTrNQHPFd7R ZwCXELZsxR/Z/VYfeHB0KD4Bl/JLsQuMAIOsJ3qOLT/vv/F9cSPwpuFD9C1Wiyy1OsfU oeqmvhlnzyJfxj6SLkKGnL/09py329jwAOGJoNoz9Xjkg98hmP+Cn8n6Qv7s5Gh7RT9m EQsxIegqsUjyieH2Nj51sSydLjXVBcuQCro2BLxpEojrpxm0xaj52pRUqVcSCbyXdwC9 3kPS+ppyCAX3+1oiebncx15iI8+q/VDZMTXsu3F/qh70bCC9mf4PlWIFLLPwXnwcS9Ll RZ2w== X-Forwarded-Encrypted: i=1; AJvYcCVhUez8+07OevZ7WKkPFzyQLbiR+UHeV/w/wQ5CAgQ7Z1sjJ50iMe6MIecqDI8LH5k6Bk8aKoK/70glar0=@vger.kernel.org X-Gm-Message-State: AOJu0YyGEN1UDOaxIj/hvg4U3Hgj8XoZBaVDcVta4eQVqItIgEn5bhPm 2LYc7dejDKvhaLnVf0MUdPRU6QAkCNvIKxCU4K92VuEPhtfJSjLLT94S X-Gm-Gg: AZuq6aI0Q0fr87C3hFXFyrz1jYfwj3FUMO4JRunGuGUJSyabwNkiAktEwx+Pt+Hus/y 8AbzeaWt1ZPzw4z6oWlYev6LHBP30P/UXle4xZ68sJJf2gC46ypvXJEwjoBa7/V6Emx6nl/V38Y j+xfphnUNFV6PIKRLu5w+cbapc+4gPaLRF2wg4Iw8/6tq66XMFXKiKEohwsAEymCZpSXMK0hVNI VuCuerMHHZx3RiaKdB3XpswWa3DdbE/VFyuZSY2gz0XvxIyBeioDM9xxrxF7/j3xZU6y4eynrb+ OPvslUsfQinjPHckaERQiDjmT4gp0sp0l68jU4x6w/M/WKmn1JfTWRNE36WFo/qkx2xHxP/ePLM wOZgtAJ8xrhVEbnmSAbqVR7Dd2zPqGKbTxxGw0QzqjCSnkWYXX/u5a0hA8hVad7KPIUCMxFI4Hd EwE5c= X-Received: by 2002:a05:7300:80c8:b0:2b7:2daf:34cd with SMTP id 5a478bee46e88-2b72daf34edmr860373eec.12.1769099759921; Thu, 22 Jan 2026 08:35:59 -0800 (PST) Received: from debian ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-2b71d3d2da2sm5525543eec.6.2026.01.22.08.35.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Jan 2026 08:35:58 -0800 (PST) From: Qiliang Yuan To: viro@zeniv.linux.org.uk, brauner@kernel.org Cc: jack@suse.cz, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, yuanql9@chinatelecom.cn, Qiliang Yuan Subject: [PATCH] fs/file: optimize close_range() complexity from O(N) to O(Sparse) Date: Thu, 22 Jan 2026 11:35:53 -0500 Message-ID: <20260122163553.147673-1-realwujing@gmail.com> X-Mailer: git-send-email 2.51.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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; =20 spin_lock(&files->file_lock); - n =3D last_fd(files_fdtable(files)); + fdt =3D files_fdtable(files); + n =3D last_fd(fdt); max_fd =3D min(max_fd, n); =20 - for (; fd <=3D max_fd; fd++) { + for (fd =3D find_next_bit(fdt->open_fds, max_fd + 1, fd); + fd <=3D max_fd; + fd =3D find_next_bit(fdt->open_fds, max_fd + 1, fd + 1)) { file =3D file_close_fd_locked(files, fd); if (file) { spin_unlock(&files->file_lock); --=20 2.51.0