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=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham 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 1B2F1C433EF for ; Wed, 8 Sep 2021 03:00:56 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id C39D66115A for ; Wed, 8 Sep 2021 03:00:55 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org C39D66115A Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=linux-foundation.org Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=kvack.org Received: by kanga.kvack.org (Postfix) id 6F822940062; Tue, 7 Sep 2021 23:00:55 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6A763940042; Tue, 7 Sep 2021 23:00:55 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5BC3E940062; Tue, 7 Sep 2021 23:00:55 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0046.hostedemail.com [216.40.44.46]) by kanga.kvack.org (Postfix) with ESMTP id 4CA17940042 for ; Tue, 7 Sep 2021 23:00:55 -0400 (EDT) Received: from smtpin21.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 193152C5B9 for ; Wed, 8 Sep 2021 03:00:55 +0000 (UTC) X-FDA: 78562904070.21.0406A2B Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by imf16.hostedemail.com (Postfix) with ESMTP id D1794F000091 for ; Wed, 8 Sep 2021 03:00:54 +0000 (UTC) Received: by mail.kernel.org (Postfix) with ESMTPSA id D9D1B6115B; Wed, 8 Sep 2021 03:00:53 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1631070054; bh=c+u+HUlxPzxAbHVXw1b4TlISD7daj5+/hKtpepjKSNU=; h=Date:From:To:Subject:In-Reply-To:From; b=ahzLOZIPU60TwkHYAko1SoPOLhSSAm0Hr/ye/y7qSBO6R6ukJ8wax8VwStC7fcpEa nnze2kstvVk6ipHi3tO4th4QHksUGhjkeBXj7r2l3XXnK4Ie985sUuNVvwLOUBdevO 1naEYVbNn8u/PrXG54ZmBKTjBDxJuI0v4Jpd5noo= Date: Tue, 07 Sep 2021 20:00:53 -0700 From: Andrew Morton To: akpm@linux-foundation.org, aquini@redhat.com, dbueso@suse.de, linux-mm@kvack.org, llong@redhat.com, manfred@colorfullife.com, mm-commits@vger.kernel.org, torvalds@linux-foundation.org Subject: [patch 145/147] ipc: replace costly bailout check in sysvipc_find_ipc() Message-ID: <20210908030053.bzt189DZK%akpm@linux-foundation.org> In-Reply-To: <20210907195226.14b1d22a07c085b22968b933@linux-foundation.org> User-Agent: s-nail v14.8.16 Authentication-Results: imf16.hostedemail.com; dkim=pass header.d=linux-foundation.org header.s=korg header.b=ahzLOZIP; spf=pass (imf16.hostedemail.com: domain of akpm@linux-foundation.org designates 198.145.29.99 as permitted sender) smtp.mailfrom=akpm@linux-foundation.org; dmarc=none X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: D1794F000091 X-Stat-Signature: tnmn1frchd9nk6ft47cn874rpedmi8k9 X-HE-Tag: 1631070054-941203 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: From: Rafael Aquini Subject: ipc: replace costly bailout check in sysvipc_find_ipc() sysvipc_find_ipc() was left with a costly way to check if the offset position fed to it is bigger than the total number of IPC IDs in use. So much so that the time it takes to iterate over /proc/sysvipc/* files grows exponentially for a custom benchmark that creates "N" SYSV shm segments and then times the read of /proc/sysvipc/shm (milliseconds): 12 msecs to read 1024 segs from /proc/sysvipc/shm 18 msecs to read 2048 segs from /proc/sysvipc/shm 65 msecs to read 4096 segs from /proc/sysvipc/shm 325 msecs to read 8192 segs from /proc/sysvipc/shm 1303 msecs to read 16384 segs from /proc/sysvipc/shm 5182 msecs to read 32768 segs from /proc/sysvipc/shm The root problem lies with the loop that computes the total amount of ids in use to check if the "pos" feeded to sysvipc_find_ipc() grew bigger than "ids->in_use". That is a quite inneficient way to get to the maximum index in the id lookup table, specially when that value is already provided by struct ipc_ids.max_idx. This patch follows up on the optimization introduced via commit 15df03c879836 ("sysvipc: make get_maxid O(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based on ipc_get_maxidx() returned value, which allows for a smooth linear increase in time complexity for the same custom benchmark: 2 msecs to read 1024 segs from /proc/sysvipc/shm 2 msecs to read 2048 segs from /proc/sysvipc/shm 4 msecs to read 4096 segs from /proc/sysvipc/shm 9 msecs to read 8192 segs from /proc/sysvipc/shm 19 msecs to read 16384 segs from /proc/sysvipc/shm 39 msecs to read 32768 segs from /proc/sysvipc/shm Link: https://lkml.kernel.org/r/20210809203554.1562989-1-aquini@redhat.com Signed-off-by: Rafael Aquini Acked-by: Davidlohr Bueso Acked-by: Manfred Spraul Cc: Waiman Long Signed-off-by: Andrew Morton --- ipc/util.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-) --- a/ipc/util.c~ipc-replace-costly-bailout-check-in-sysvipc_find_ipc +++ a/ipc/util.c @@ -788,21 +788,13 @@ struct pid_namespace *ipc_seq_pid_ns(str static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t pos, loff_t *new_pos) { - struct kern_ipc_perm *ipc; - int total, id; + struct kern_ipc_perm *ipc = NULL; + int max_idx = ipc_get_maxidx(ids); - total = 0; - for (id = 0; id < pos && total < ids->in_use; id++) { - ipc = idr_find(&ids->ipcs_idr, id); - if (ipc != NULL) - total++; - } - - ipc = NULL; - if (total >= ids->in_use) + if (max_idx == -1 || pos > max_idx) goto out; - for (; pos < ipc_mni; pos++) { + for (; pos <= max_idx; pos++) { ipc = idr_find(&ids->ipcs_idr, pos); if (ipc != NULL) { rcu_read_lock(); _