From patchwork Thu Jul 1 01:57:18 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Morton X-Patchwork-Id: 12353441 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,URIBL_RED 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 9AE16C11F66 for ; Thu, 1 Jul 2021 01:57:21 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 529256141A for ; Thu, 1 Jul 2021 01:57:21 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 529256141A 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=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id D16158D028B; Wed, 30 Jun 2021 21:57:20 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CC5C18D0279; Wed, 30 Jun 2021 21:57:20 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B73618D028B; Wed, 30 Jun 2021 21:57:20 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0101.hostedemail.com [216.40.44.101]) by kanga.kvack.org (Postfix) with ESMTP id 919C88D0279 for ; Wed, 30 Jun 2021 21:57:20 -0400 (EDT) Received: from smtpin01.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id 6341A82F4878 for ; Thu, 1 Jul 2021 01:57:20 +0000 (UTC) X-FDA: 78312356640.01.9DCBECB Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by imf27.hostedemail.com (Postfix) with ESMTP id 0D199700009E for ; Thu, 1 Jul 2021 01:57:19 +0000 (UTC) Received: by mail.kernel.org (Postfix) with ESMTPSA id 2743C61483; Thu, 1 Jul 2021 01:57:19 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1625104639; bh=38fiufiaI4VV8d67qzuB5qatPPBfMY/7Tvd0MK24Tac=; h=Date:From:To:Subject:In-Reply-To:From; b=ADVUHgp2A7P+2CDoykIjkDvvuNw7cGR5QDFtCyugTcuzDZArBRZBcUTdt4hFMS6Xh lCwQob9rjWevjGjHjs+l+gPAzWrtQDJBBAwtcsVD6LmjPYyWeZ5wyLILJczSpgmUM3 O1GmCFy+rW81zTgJX4OyUrhd0OgbAgb3S20Gm4CQ= Date: Wed, 30 Jun 2021 18:57:18 -0700 From: Andrew Morton To: 1vier1@web.de, akpm@linux-foundation.org, dbueso@suse.de, linux-mm@kvack.org, manfred@colorfullife.com, mm-commits@vger.kernel.org, torvalds@linux-foundation.org Subject: [patch 192/192] ipc/util.c: use binary search for max_idx Message-ID: <20210701015718.0DUvPUD_l%akpm@linux-foundation.org> In-Reply-To: <20210630184624.9ca1937310b0dd5ce66b30e7@linux-foundation.org> User-Agent: s-nail v14.8.16 Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=linux-foundation.org header.s=korg header.b=ADVUHgp2; spf=pass (imf27.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: rspam03 X-Rspamd-Queue-Id: 0D199700009E X-Stat-Signature: tzeefihmaremmejttujxyomzo7i8xjit X-HE-Tag: 1625104639-501718 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: Manfred Spraul Subject: ipc/util.c: use binary search for max_idx If semctl(), msgctl() and shmctl() are called with IPC_INFO, SEM_INFO, MSG_INFO or SHM_INFO, then the return value is the index of the highest used index in the kernel's internal array recording information about all SysV objects of the requested type for the current namespace. (This information can be used with repeated ..._STAT or ..._STAT_ANY operations to obtain information about all SysV objects on the system.) There is a cache for this value. But when the cache needs up be updated, then the highest used index is determined by looping over all possible values. With the introduction of IPCMNI_EXTEND_SHIFT, this could be a loop over 16 million entries. And due to /proc/sys/kernel/*next_id, the index values do not need to be consecutive. With , msgget(), msgctl(,IPC_RMID) in a loop, I have observed a performance increase of around factor 13000. As there is no get_last() function for idr structures: Implement a "get_last()" using a binary search. As far as I see, ipc is the only user that needs get_last(), thus implement it in ipc/util.c and not in a central location. [akpm@linux-foundation.org: tweak comment, fix typo] Link: https://lkml.kernel.org/r/20210425075208.11777-2-manfred@colorfullife.com Signed-off-by: Manfred Spraul Acked-by: Davidlohr Bueso Cc: <1vier1@web.de> Signed-off-by: Andrew Morton --- ipc/util.c | 44 +++++++++++++++++++++++++++++++++++++++----- ipc/util.h | 3 +++ 2 files changed, 42 insertions(+), 5 deletions(-) --- a/ipc/util.c~ipc-utilc-use-binary-search-for-max_idx +++ a/ipc/util.c @@ -64,6 +64,7 @@ #include #include #include +#include #include @@ -451,6 +452,41 @@ static void ipc_kht_remove(struct ipc_id } /** + * ipc_search_maxidx - search for the highest assigned index + * @ids: ipc identifier set + * @limit: known upper limit for highest assigned index + * + * The function determines the highest assigned index in @ids. It is intended + * to be called when ids->max_idx needs to be updated. + * Updating ids->max_idx is necessary when the current highest index ipc + * object is deleted. + * If no ipc object is allocated, then -1 is returned. + * + * ipc_ids.rwsem needs to be held by the caller. + */ +static int ipc_search_maxidx(struct ipc_ids *ids, int limit) +{ + int tmpidx; + int i; + int retval; + + i = ilog2(limit+1); + + retval = 0; + for (; i >= 0; i--) { + tmpidx = retval | (1<ipcs_idr, &tmpidx)) + retval |= (1<deleted = true; if (unlikely(idx == ids->max_idx)) { - do { - idx--; - if (idx == -1) - break; - } while (!idr_find(&ids->ipcs_idr, idx)); + idx = ids->max_idx-1; + if (idx >= 0) + idx = ipc_search_maxidx(ids, idx); ids->max_idx = idx; } } --- a/ipc/util.h~ipc-utilc-use-binary-search-for-max_idx +++ a/ipc/util.h @@ -145,6 +145,9 @@ int ipcperms(struct ipc_namespace *ns, s * ipc_get_maxidx - get the highest assigned index * @ids: ipc identifier set * + * The function returns the highest assigned index for @ids. The function + * doesn't scan the idr tree, it uses a cached value. + * * Called with ipc_ids.rwsem held for reading. */ static inline int ipc_get_maxidx(struct ipc_ids *ids)