From nobody Wed Dec 17 20:41:14 2025 Received: from mail-yb1-f173.google.com (mail-yb1-f173.google.com [209.85.219.173]) (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 6EDAF42056 for ; Thu, 2 May 2024 23:32:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692734; cv=none; b=tGUtUbJfuWWCl5qPdl/p86UE1a2E4bBoDdHROg1rRC2/DRgSpxRpmzpTM1/c//k4PdEolpDg+whDotCzpSl0ZBvB2vACBlMh/Bszw4QGbbout/KoVZLIZ2tv6c9OE6yJ2f7aRYgwxCzPLODs57hAjSOIK4k6ow1H9kMLOB6MOwU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692734; c=relaxed/simple; bh=7dqAqPc5jtoofxyWnRuoCg8LIeM0occN/PCKEq8ky0E=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fi/4eFZibS3Ae6oCG/luBG1NwDXz6t6l5+iGb2tbYmzUk5kZYPC/J5/nrtBCLW3lFny14MmS7tOi2mysDAsRcRQHcnvfDailYfFYFKAPHEwSs0bw7OjT6Tq9KaBffqBmuSTldrwDl3OoMLO8UaUVsn/8+WA74DGRUCMhnARSSeQ= 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=AWmmhfZi; arc=none smtp.client-ip=209.85.219.173 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="AWmmhfZi" Received: by mail-yb1-f173.google.com with SMTP id 3f1490d57ef6-de8b66d1726so1129196276.0 for ; Thu, 02 May 2024 16:32:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714692732; x=1715297532; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=lIltuOo/UMxTPopgbTGchZq1egfHJ5nqwS9l0DIwlU4=; b=AWmmhfZipE69o6fEZYl7T1l+wuiam8uVOXxEDf7FMEYHjeCGEiuPGBcP92A/ffcyI3 JUYNqHO8I8ntmC09b1Yct5iUBRqrj7Z8IaJusDkhKEjYXEr5GuV/L7gT2x+4L+E0lSdP Z/yeXbTEy7Awt2NdwrMWhVs3SZilqnR+wLDIyZNtqd2IHKUBqLjBqZP3xWWH9k9otaVF K5IQiW3ijdP/xNL9szxoaC0/SZvh/v1euRlwvTjkgt/BCD2QZ4lGzexxNvBj03vWPsPO l9vM0fQqGCXVMKt4Li1MoPSOVnNEvGK3ZZSv9GeKDTAo+RNX62L3KejVm6dqPoEUNAf1 Ezpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714692732; x=1715297532; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=lIltuOo/UMxTPopgbTGchZq1egfHJ5nqwS9l0DIwlU4=; b=tZidG8l0LNCv+ZpvlSSILAb+1H1xX3xS1yfSr9fJqmUuGEmxBUk88lPdX8KqyhaQTB gotPWIVpwH16YHlO4MYszDH6wJeWLy8Jg8b5KQdEnoqP3qwUE6Ujhe45nfD1HGR4Ysnj HbgCDX0zM4HH5sQfVjLubZapbOUNMJVMvlv6sMAa5ZZRuIT5W5KzuZxFdF8CceCJ350h +uEw94Wr4AEX7/l/9ao/d3HljW363NkVfiP5zHeNIc4lg7eMK4Q3KiLDBsJKT/pwNb1O 04syfcjExmFOxBK0WbAPRkakpoHAaMo94+sXNj3TFEIPvgf2xXAzNGb+ZRhXz2KqUXqy f/VQ== X-Gm-Message-State: AOJu0YxkM3QTugNQTZly3aaliPyul69g++AzVhA4o9LcT4X5K+M50WOe c9PVgXpCUCCZeQlQnf6C+mJ/ZyUw6+wtGIdM356I3DSxmbqxasBN78tuqg== X-Google-Smtp-Source: AGHT+IFghE9Y+h3O2dRvkZCSIo2buTLHl1NFEpbmNbLUtoKsAvBmEIo+HLTbuVvaFzhXaAxLmWybXg== X-Received: by 2002:a05:6902:2203:b0:dda:c380:689e with SMTP id dm3-20020a056902220300b00ddac380689emr2908827ybb.4.1714692729362; Thu, 02 May 2024 16:32:09 -0700 (PDT) Received: from localhost ([69.73.66.55]) by smtp.gmail.com with ESMTPSA id x193-20020a254aca000000b00de5a5fcee44sm425994yba.13.2024.05.02.16.32.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 02 May 2024 16:32:08 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Rasmus Villemoes , Andrew Morton , Kuan-Wei Chiu Subject: [PATCH 1/4] lib: make test_bitops compilable into the kernel image Date: Thu, 2 May 2024 16:32:01 -0700 Message-Id: <20240502233204.2255158-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20240502233204.2255158-1-yury.norov@gmail.com> References: <20240502233204.2255158-1-yury.norov@gmail.com> 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" The test is limited to be compiled as a module. There's no technical reason for it. Now that the test bears performance benchmark, it would be reasonable to allow running it at kernel load time, before userspace starts, to reduce possible jitter. Signed-off-by: Yury Norov Reviewed-by: Kuan-Wei Chiu --- lib/Kconfig.debug | 1 - 1 file changed, 1 deletion(-) diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index c63a5fbf1f1c..fc8fe1ea5b49 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2436,7 +2436,6 @@ config TEST_LKM =20 config TEST_BITOPS tristate "Test module for compilation of bitops operations" - depends on m help This builds the "test_bitops" module that is much like the TEST_LKM module except that it does a basic exercise of the --=20 2.40.1 From nobody Wed Dec 17 20:41:14 2025 Received: from mail-yw1-f180.google.com (mail-yw1-f180.google.com [209.85.128.180]) (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 63FF5433CF for ; Thu, 2 May 2024 23:32:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692735; cv=none; b=M+3nYad19exjfwYHhHJMzLBu1iZaOW47zLGAsMHKTnK0c0NNW3Ir9xlwqyGXEJYKbRQ2OkBp0AD4DNJmRSh6bmYQu8NZ9/hg83N+mjb3iH0Ip5h5iXdCPQp9UbpKbFyQj74cZM6Him9Y6IHspkh8OEhTKgWm1u4+Bh5+Q6ado2E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692735; c=relaxed/simple; bh=YpKQ29iVm/00wlNh7i525FynJteEBIE69FNB58UBFw8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=pryRt6yQfmsgrFFfXkf9w2mD0pCMv93Yuc4ECsxBGBfvUlCCxlpqJn3Bbm0AgxD6CG+lPOXQVZPCbn/jkGLHaMUJtbI7DNP3tba+fjXazWQN9Ocp0GjGdMjTsvoLheZDfi4ZZE5aaPHOOrmdq9r39qKqvqCMUhYkJ171coSI2Ws= 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=AiZIuSs1; arc=none smtp.client-ip=209.85.128.180 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="AiZIuSs1" Received: by mail-yw1-f180.google.com with SMTP id 00721157ae682-6150670d372so72612327b3.1 for ; Thu, 02 May 2024 16:32:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714692733; x=1715297533; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Rz+WU4hPA1taz/uX+9jMD3l6e25brCZmsg2ndtmnoJ8=; b=AiZIuSs1aldkY53bh7NAE0FKEBb2vPe8vc7FLYShAa+uVs20nXIpxgqVBhllqc7lHp peU/H73mtq+Q3kTUHY4pw5lbphmvMAeTk7izzsR+WNMx9KaaQ+arjB62AB5yeQq16MkC +k4azmGqSdETba3pD6/sAnSqqdS+VTEN/vMz/v4sbtC/FQnCYe+B0EeNegyrFCyAlyld UF+TSTKUpoLYGAJ1zMbB5EUpXcRQnlhwB65/e59YIoYOF55WWkBxCrDXCwEXePS0bcdB xI5Hh0HDhBg7WlzYd6XtF6kqRYi8umeTBDCTTDvoxK0Rz9wIHiTII3++CczjkYbQENd8 SjMA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714692733; x=1715297533; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Rz+WU4hPA1taz/uX+9jMD3l6e25brCZmsg2ndtmnoJ8=; b=AzJG3k2nXMax9ydTkBgkCXAcQoki/ii4AAqYM0voalzcNDdzaf8LGE9GALCDnO2+nY clbhjb/CUfUz2et6qKRFCKJg492p2xaUYJOcXlxjgGYEc1CmM2fEdpLzlQXBnmmd9PxC dHGIzH2dKTyUuyNdjneafd9pMEDORByY+1Wwur+T/FSPftZiF6Y0bI1LY2ctr43x939z mZIHZYvpWDj5nRn90XtW3YIsF+jgMU7Gz072tme6+MRnycjEwT2U9Pdk2kvaovOGIvBq yYensZ1H5y0I8wZ2bMyxbto7cbDZwsUNQrL2e//wxZx/H49YJGIUSAeIrXthzTryvhOn EPnw== X-Gm-Message-State: AOJu0Yw2HD1sVOxvRTqBphBDo1jno65KRuEoZsWUzka7oHAUwR95/dcd K6WsKJ0BtLDstJ5HiVI4WfjyVSjO2H5P3AO9fVstNkvtL2t+mCw69Ob0VA== X-Google-Smtp-Source: AGHT+IG3RRdpWMQIhYOUX+rJ1wV69r7PLNWhZhd134y5VWy4XsO8zgu0Csr0D+x/IcixBUrGsYvmlQ== X-Received: by 2002:a0d:d40e:0:b0:615:1dc3:9596 with SMTP id w14-20020a0dd40e000000b006151dc39596mr1108749ywd.28.1714692733374; Thu, 02 May 2024 16:32:13 -0700 (PDT) Received: from localhost ([69.73.66.55]) by smtp.gmail.com with ESMTPSA id s3-20020a817703000000b0061beb26a082sm425303ywc.112.2024.05.02.16.32.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 02 May 2024 16:32:13 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Rasmus Villemoes , Andrew Morton , Kuan-Wei Chiu Subject: [PATCH 2/4] bitmap: relax find_nth_bit() limitation on return value Date: Thu, 2 May 2024 16:32:02 -0700 Message-Id: <20240502233204.2255158-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20240502233204.2255158-1-yury.norov@gmail.com> References: <20240502233204.2255158-1-yury.norov@gmail.com> 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" The function claims to return the bitmap size if Nth bit doesn't exist. This rule is violated in inline case because the fns() that is used there doesn't know anything about size of the bitmap. So, relax this requirement to '>=3D size', and make the outline implementation a bit cheaper. All in-tree kernel users of find_nth_bit() are safe against that. Reported-by: Rasmus Villemoes Closes: https://lore.kernel.org/all/Zi50cAgR8nZvgLa3@yury-ThinkPad/T/#m6da8= 06a0525e74dcc91f35e5f20766ed4e853e8a Signed-off-by: Yury Norov --- include/linux/find.h | 2 +- lib/find_bit.c | 2 +- lib/test_bitmap.c | 4 ++-- 3 files changed, 4 insertions(+), 4 deletions(-) diff --git a/include/linux/find.h b/include/linux/find.h index c69598e383c1..02751e43d448 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -220,7 +220,7 @@ unsigned long find_first_bit(const unsigned long *addr,= unsigned long size) * idx =3D find_first_bit(addr, size); * * Returns the bit number of the N'th set bit. - * If no such, returns @size. + * If no such, returns >=3D @size. */ static inline unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, = unsigned long n) diff --git a/lib/find_bit.c b/lib/find_bit.c index 32f99e9a670e..0bddfc3ff248 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -87,7 +87,7 @@ out: \ if (sz % BITS_PER_LONG) \ tmp =3D (FETCH) & BITMAP_LAST_WORD_MASK(sz); \ found: \ - sz =3D min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \ + sz =3D idx * BITS_PER_LONG + fns(tmp, nr); \ out: \ sz; \ }) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 6b2b33579f56..088838f829c9 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -244,7 +244,7 @@ static void __init test_find_nth_bit(void) expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5)); expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6)); expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7)); - expect_eq_uint(64 * 3, find_nth_bit(bmap, 64 * 3, 8)); + expect_eq_uint(0, !!(find_nth_bit(bmap, 64 * 3, 8) < 64 * 3)); =20 expect_eq_uint(10, find_nth_bit(bmap, 64 * 3 - 1, 0)); expect_eq_uint(20, find_nth_bit(bmap, 64 * 3 - 1, 1)); @@ -254,7 +254,7 @@ static void __init test_find_nth_bit(void) expect_eq_uint(60, find_nth_bit(bmap, 64 * 3 - 1, 5)); expect_eq_uint(80, find_nth_bit(bmap, 64 * 3 - 1, 6)); expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7)); - expect_eq_uint(64 * 3 - 1, find_nth_bit(bmap, 64 * 3 - 1, 8)); + expect_eq_uint(0, !!(find_nth_bit(bmap, 64 * 3 - 1, 8) < 64 * 3 - 1)); =20 for_each_set_bit(bit, exp1, EXP1_IN_BITS) { b =3D find_nth_bit(exp1, EXP1_IN_BITS, cnt++); --=20 2.40.1 From nobody Wed Dec 17 20:41:14 2025 Received: from mail-yw1-f177.google.com (mail-yw1-f177.google.com [209.85.128.177]) (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 EC62046B80 for ; Thu, 2 May 2024 23:32:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692737; cv=none; b=O7crce+CHYmPJoOT2Z+z4h/lVYR+LeDqzBk6WzDEPr3A+W+DVJdoaULGKEwFTEcFoUC1WWGh+yNd/K0/oilZM6PR4qHMfuosV9MiVEHmE3WgAWq6lVm2EdScXh4fN0BsI7fUsD+cgyYyst8jP7v3HMF/apXUH4St0XV3GUmAY/I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692737; c=relaxed/simple; bh=JjG9zTh3YcEGevq2mGu1lapQZDi6ixXR4kkaGkiUikM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=TlPE4er0/5wEXKcn1+SlldVeWWW4alcfFhx5IcKv18tFFMLUcN9aYshR6hGQUSN8L8goTanGXw6ZP3SyY7v5FQ/05M6Qc6IOEHzonLRTvi5TdfnM6fKMAET4dYY7BrZ60bUC+2/jKvBR6t1S2ABJM2itdOSpxY+jV1Esy3kvQh0= 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=FovkIkSu; arc=none smtp.client-ip=209.85.128.177 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="FovkIkSu" Received: by mail-yw1-f177.google.com with SMTP id 00721157ae682-61bee45d035so38695817b3.1 for ; Thu, 02 May 2024 16:32:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714692735; x=1715297535; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=xwV1HZVleW01thm7cKmWmN1euQJwSchKow0lguZfgFs=; b=FovkIkSuwpRyRsoZTvFnqnVfc2SiM8x8HEbO/pnTc5uEHyyiAdeMFzSFrLt/e3XgtI 38L4AAT09UtcF9PvA24dzbopMKwSr4UDi7vACrxmU/IJJpdDp0BDmkOWpzEBJspY9I69 5ZvoqCkIN/yfPK953BJwShB1LdLZJvTf8rFBPv1YFVQerkPuY4naIyO5Wh8nI8SnF7dy UuzufOS0/uUPefcA8J584XzfuQxkUBZy7kVWxCHYdxRPNz56ZyAFV+TOvyFsTkjm/z7H ehtFSWM0no8MkMQkC8Q7oEHvTlj2gZpI0a2hg3QGfmNhBasUt0pmCCoCjcf701P/UfyL OotQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714692735; x=1715297535; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=xwV1HZVleW01thm7cKmWmN1euQJwSchKow0lguZfgFs=; b=iTxf9fHuRK2iBKcnCZdsco1t6+2iC/9gxkynqGDk+i9Rb/NR6zSOKh7s+u1ocDrAjz tCYcJaBJjx/228MaI70SkDSkVZ9TzQ8bsTGz9xrAg3kpJi1+epMlXsaMGoSiEVrgteAz h+SzfQPEnKspawXD2G35TPHWcSAJRYOEZe0GOdpmXom810eUILTgI40gderHyXULwQvY VNqfYWNINzntRMw7xxum+3NYv6FZWyrxafReKHE/CxzbctdghCMdHcCjKu2HW2PzMXmk PTnm+Faud2/9Kg21vUkO1k3vJLNxhk7+UhusB8JYcHpfNTIZZb5tZ91o5LL4WKSVFd3f u/7g== X-Gm-Message-State: AOJu0Yw3Izi/iKpnjdoAxxyc0oYFd3LWHiW1O1rPtyH8mpGTIVUvIGXd yhGqYTSZ4wYmaVOZzCD082H3ug5eYnRcQ1Ai3S5fF8zuguWLSZJV/OeK0g== X-Google-Smtp-Source: AGHT+IEfIyTCFtIJsgR5/4dFaKx64FgUX3BiK43cMG6jgpNDd+rdbywqtcN3n4X3qgws0YGbJKmeDg== X-Received: by 2002:a81:4882:0:b0:61b:1f0d:838b with SMTP id v124-20020a814882000000b0061b1f0d838bmr1103567ywa.14.1714692734769; Thu, 02 May 2024 16:32:14 -0700 (PDT) Received: from localhost ([69.73.66.55]) by smtp.gmail.com with ESMTPSA id s20-20020a819f14000000b006152af6131dsm420052ywn.119.2024.05.02.16.32.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 02 May 2024 16:32:14 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Rasmus Villemoes , Andrew Morton , Kuan-Wei Chiu Subject: [PATCH 3/4] bitops: squeeze even more out of fns() Date: Thu, 2 May 2024 16:32:03 -0700 Message-Id: <20240502233204.2255158-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20240502233204.2255158-1-yury.norov@gmail.com> References: <20240502233204.2255158-1-yury.norov@gmail.com> 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" The function clears N-1 first set bits to find the N'th one with: while (word && n--) word &=3D word - 1; In the worst case, it would take 63 iterations. Instead of linear walk through the set bits, we can do a binary search by using hweight(). This would work even better on platforms supporting hardware-assisted hweight() - pretty much every modern arch. On my Ryzen 9 5900X, the test_fns() benchmark runs binary fns() twice faster, comparing to linear one. The fns8() returns 64 to make sure that in case of no bit found, the return value will be greater than the bit capacity of arguments of all fnsXX() functions up to fns64(). Signed-off-by: Yury Norov Reviewed-by: Kuan-Wei Chiu --- include/linux/bitops.h | 42 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 37 insertions(+), 5 deletions(-) diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 57ecef354f47..1c4773db56e0 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -247,17 +247,49 @@ static inline unsigned long __ffs64(u64 word) return __ffs((unsigned long)word); } =20 +static inline unsigned long fns8(u8 word, unsigned int n) +{ + while (word && n--) + word &=3D word - 1; + + return word ? __ffs(word) : 64; +} + +static inline unsigned long fns16(u16 word, unsigned int n) +{ + unsigned int w =3D hweight8((u8)word); + + return n < w ? fns8((u8)word, n) : 8 + fns8((u8)(word >> 8), n - w); +} + +static inline unsigned long fns32(u32 word, unsigned int n) +{ + unsigned int w =3D hweight16((u16)word); + + return n < w ? fns16((u16)word, n) : 16 + fns16((u16)(word >> 16), n - w); +} + +static inline unsigned long fns64(u64 word, unsigned int n) +{ + unsigned int w =3D hweight32((u32)word); + + return n < w ? fns32((u32)word, n) : 32 + fns32((u32)(word >> 32), n - w); +} + /** * fns - find N'th set bit in a word * @word: The word to search - * @n: Bit to find + * @n: Bit to find, counting from 0 + * + * Returns N'th set bit. If no such bit found, returns >=3D BITS_PER_LONG */ static inline unsigned long fns(unsigned long word, unsigned int n) { - while (word && n--) - word &=3D word - 1; - - return word ? __ffs(word) : BITS_PER_LONG; +#if BITS_PER_LONG =3D=3D 64 + return fns64(word, n); +#else + return fns32(word, n); +#endif } =20 /** --=20 2.40.1 From nobody Wed Dec 17 20:41:14 2025 Received: from mail-yw1-f182.google.com (mail-yw1-f182.google.com [209.85.128.182]) (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 53F8E4AEE0 for ; Thu, 2 May 2024 23:32:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692738; cv=none; b=UqirBTztmJy3INMhtJz6W2PJWLZjgQopEJi32sI9i8ZzC1ApSShEbryk2W8nJ0EyuAT7czPq5N/s6Gjln64tLNn3ekZRJDVeytsLRqn53j1X0312tgNE/8+Vp7zaVDJu1uvItnLElv/MmWpsJhBGGViUXxaQKVt2dYPtz1++dy0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714692738; c=relaxed/simple; bh=vGxye/FU6337p1UzT7aFBq/KUA2R8rfM3m6vHhGjdT4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=OXdk2kqpw5uimH9OKoXoDSdpVEaN2pCDzqfIrCm81e1Rq3dmJ9S89q0NPwQSJIdvIizshGlmaIYFTFJVjDrTfGBFEk4KiM01iGoi/lD6ehPBZe1iG7OGgokTb0FKZKCQjrXwOD1uD8jFk5Inmfo5uPe6nPbAIbB5clR1ieNg7x4= 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=f0e+nUee; arc=none smtp.client-ip=209.85.128.182 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="f0e+nUee" Received: by mail-yw1-f182.google.com with SMTP id 00721157ae682-61e01d5ea74so22828167b3.2 for ; Thu, 02 May 2024 16:32:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714692736; x=1715297536; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7EMydeMYAoD8bLiiOASQ2pN3/O7edcAgllopuW/8Dwk=; b=f0e+nUeeDVoWGpV9kXreQFIS46ksrNKtVYOXF/0INPwG8VAIRa8ceItCY0Ld7ZS21H pgmNB/8c0mebyO61m8L9DJhUXUf9pv/LEDOm15nxwIlUOQAvkUf707H860P0DLU71To+ g1h1hvTDSGxqrBs0zbryXFzKllG1hMzRq4wp89fnK2d+gwjjpnxny8jcQyaxbqXv+KLn PbBqsZOZ/ogkEci1Poj+SxKW+ThPxgm7PKKRyNmQ8FhgsKm6rrEmU89emlKtwX6+ay3F yfkaI+nGSM6khBrqm/Jjs+al4KhniQaLqdCtlNderuBV8mL8GG2WWbrhbnNagL1AM1qR QAjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714692736; x=1715297536; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7EMydeMYAoD8bLiiOASQ2pN3/O7edcAgllopuW/8Dwk=; b=L5RXTiokM9pR6hMbFld4Jt3yWOchFL8DIF5rTxPtqcnj0UgEjxNhKwqNxzE6O33Vdp Df+Yoc/25RuV2GugmjNG/a1reKjviLdSp0oXQf4TTSXs144Rv8BRjWUQJ6D6qAjOhe27 GyAS1WW10gEANLGELNN7a9Jb/hVvyZei8Nnda/qzyXnG9ASoIQ5ZyMYfoOERYQrgomgF tiihBdpNQaAT+al1xLDSfxaYA1a0VVqpBcRI4uW8lAUEU+ZYe+F28sj2NI/WpUVe05SY lFhAq3AkPcgd56Lv/ccaxf9dQ3Q07XCudbqjsPqaiaymPul0ME24oWq6+pMabQSiCn93 +m2Q== X-Gm-Message-State: AOJu0YwrLHf6g+Lu15oKaZRgFtqd+XV3o3ojAzgpChjziTIL7fLxRIoK YXhz7YwXMsx4gqbV7gCNiQFBbF4UTSZUBKHr+XzGWraSZBBwmHnlr9Aj5Q== X-Google-Smtp-Source: AGHT+IErSjtSElCwfJ4YRpT9SrZC2anGphCNOMBDxAltaBhPPmPCh7iSjcPAOwt3nq5wjcgBaCVFlQ== X-Received: by 2002:a0d:e2d2:0:b0:61a:ced3:2574 with SMTP id l201-20020a0de2d2000000b0061aced32574mr1071205ywe.13.1714692736209; Thu, 02 May 2024 16:32:16 -0700 (PDT) Received: from localhost ([69.73.66.55]) by smtp.gmail.com with ESMTPSA id ck25-20020a05690c0b9900b0061ad5c52d23sm412698ywb.69.2024.05.02.16.32.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 02 May 2024 16:32:15 -0700 (PDT) From: Yury Norov To: linux-kernel@vger.kernel.org Cc: Yury Norov , Rasmus Villemoes , Andrew Morton , Kuan-Wei Chiu Subject: [PATCH 4/4] MAINTAINERS: add BITOPS API record Date: Thu, 2 May 2024 16:32:04 -0700 Message-Id: <20240502233204.2255158-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20240502233204.2255158-1-yury.norov@gmail.com> References: <20240502233204.2255158-1-yury.norov@gmail.com> 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" Bitops API is the very basic, and it's widely used by the kernel. But corresponding files are not maintained. Bitmaps actively use bit operations, and big share of bitops material already moves through the bitmap branch. I would like to take a closer look to bitops. This patch creates a BITOPS API record in the MAINTAINERS, and adds Rasmus as a reviewer, and myself as a maintainer of those files. Signed-off-by: Yury Norov --- MAINTAINERS | 14 ++++++++++++++ 1 file changed, 14 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index c23fda1aa1f0..0cfd2c5d9086 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -3638,6 +3638,20 @@ F: tools/include/vdso/bits.h F: tools/lib/bitmap.c F: tools/lib/find_bit.c =20 +BITOPS API +M: Yury Norov +R: Rasmus Villemoes +S: Maintained +F: arch/*/include/asm/bitops.h +F: arch/*/include/asm/bitops_32.h +F: arch/*/include/asm/bitops_64.h +F: arch/*/lib/bitops.c +F: include/asm-generic/bitops +F: include/asm-generic/bitops.h +F: include/linux/bitops.h +F: lib/test_bitops.c +F: tools/*/bitops* + BLINKM RGB LED DRIVER M: Jan-Simon Moeller S: Maintained --=20 2.40.1