From patchwork Thu Feb 22 14:22:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Herve Codina X-Patchwork-Id: 204795 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7300:aa16:b0:108:e6aa:91d0 with SMTP id by22csp285666dyb; Thu, 22 Feb 2024 06:24:06 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUY9SluJ903kBi7Jyo/oOEfISUeN59MIf7JgfW1KrMRPNgW2GsXfCQA7JuNtKUW1CNqHGq1zvGAXUvagSnX3/m/Fh8byw== X-Google-Smtp-Source: AGHT+IFbOI0cqavfvQnNZx4vhq1GVRsGIlkXU6Ca+bzKc0bdXiIuV75MPjFrXdYBHMhWjT2BQvvD X-Received: by 2002:a17:906:c319:b0:a3e:d251:f5d7 with SMTP id s25-20020a170906c31900b00a3ed251f5d7mr7734368ejz.33.1708611846525; Thu, 22 Feb 2024 06:24:06 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708611846; cv=pass; d=google.com; s=arc-20160816; b=C9k6oKrmeEclj1PMibAMK67j/jmu8Vn/c5VYOgJHmNtsgUioF4h3Nc0IOgmq6M3KwW QJschaAX1pOO5Tu1SW2J7amnfKuJZy1YY5wlRWR7rrdB5eXfP3o3Sd0DLNxmj1xTAkFW OxnnFPM/PBqfFbAO+PM0x1DycfLN1eG83F3uG0X+C5KxEFpQbDi83rsg2+rYClSV9bmi 11rvJeOvdJP7ggbJh5jF/R+tYHqvyc30qQFF/+9j/x0NayF6EXX6kKR+gsoeR/leqjRs LgwxKHQoxiHERYfnfaLVDYdgYCdUVIxy8zHU5fbE2wW+eDgkWBlIST4lMGzvHJb2087y Tgrg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:in-reply-to:message-id :date:subject:cc:to:from:dkim-signature; bh=vhUy0s5rAA2jpfib2wvQj5LlqoBlVPRKh1f7DNT90PE=; fh=S1JXykGn8s83VQzPRjkanrg93kX6oJVbyHnK1JmVqsw=; b=ARReJwXo+kkCwtGJlbHLubi9PqkbSRpBXk9WMe10wq+wYE0/27a7Bt7kzSjio5Bjks pBpvva3crMjAFHOLg6APoYBCPGpUfQwOhUEqb5UtVWDmHcw+5YhtV4UlgXY9bdZHnZCD Ww/+JVMiAtsIYnXawtyRM2RvEvwBdqxaxymHhLMRcNzp/xwhGX4St0rd27j7uMHwZN1V YMEQUJlgPPSf/Ad8RheopikIDOoGiBMTAFQqDC06xSxeG4oQinhQCCCcPb5vAQAhghH8 ABQ5JT6Pr1Tk3SMw14p/xiC1EeryWg4bofvC/e6IFpCLec4520fOyYLRwIu4D8khJ8Wf ondQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@bootlin.com header.s=gm1 header.b=V0ra76Qw; arc=pass (i=1 spf=pass spfdomain=bootlin.com dkim=pass dkdomain=bootlin.com dmarc=pass fromdomain=bootlin.com); spf=pass (google.com: domain of linux-kernel+bounces-76694-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-76694-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=bootlin.com Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [2604:1380:4601:e00::3]) by mx.google.com with ESMTPS id v21-20020a1709062f1500b00a3d72d77a6fsi5408170eji.401.2024.02.22.06.24.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Feb 2024 06:24:06 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-76694-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3; Authentication-Results: mx.google.com; dkim=pass header.i=@bootlin.com header.s=gm1 header.b=V0ra76Qw; arc=pass (i=1 spf=pass spfdomain=bootlin.com dkim=pass dkdomain=bootlin.com dmarc=pass fromdomain=bootlin.com); spf=pass (google.com: domain of linux-kernel+bounces-76694-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-76694-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=bootlin.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id 015731F22C60 for ; Thu, 22 Feb 2024 14:24:06 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 4123214E2C9; Thu, 22 Feb 2024 14:22:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=bootlin.com header.i=@bootlin.com header.b="V0ra76Qw" Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net [217.70.183.201]) (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 403671482E8; Thu, 22 Feb 2024 14:22:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=217.70.183.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708611757; cv=none; b=gPWQWhuQLrAXrzplt8xUepHtVxOAZJ35qOLOfz2wTfQeIbv2j8+DkKPEBD6jbZwZJPEvMgXDRSiHNmvALgITpoI9TnFneMroQ1cDqrHaj/TgHwKbuH7Jd9geBnJ39PTZ4kml1MN/o53U/SIjX4+F3FGW3LFXi7jhTPO0jrsGXU0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708611757; c=relaxed/simple; bh=5aDqCqJLehZjx9/6azNLCdNaSNuJcq63hnRD8jBCtco=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=HUVdXvQ8kTn9eJb56BT+jkUInh2X7M4GAfuB+hq0p6efk9PW+1xBtAvMwKD1UEmUyfSb9qi6Nd/7ASIc1Uao54tQBcIRely8JGlNCBCQoGvhlrICsCAcZHWiSdrMxl6pO4xRiFA30E4COmEQUfIoz74y+xduoXaV5kzP/LiqkOA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=bootlin.com; spf=pass smtp.mailfrom=bootlin.com; dkim=pass (2048-bit key) header.d=bootlin.com header.i=@bootlin.com header.b=V0ra76Qw; arc=none smtp.client-ip=217.70.183.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=bootlin.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=bootlin.com Received: by mail.gandi.net (Postfix) with ESMTPA id D1DB81BF20B; Thu, 22 Feb 2024 14:22:32 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bootlin.com; s=gm1; t=1708611753; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=vhUy0s5rAA2jpfib2wvQj5LlqoBlVPRKh1f7DNT90PE=; b=V0ra76QwhZp1Wq0gprppDTXEOYtxFQqiMy6HaKg+Ju/BIbZhGLi5t67DviFHjlrjmy7WJw 8kREJI7jkRE/bSqfc7osFWpecwWBKB2ZEfq548tmJnwiWvRPfjPB9tI8AAcdC37ABz/ojl xATdu5Awr5qw2rpJ4d1XHGkQq3/Ge/g6ORtZeUZQrGy7jkBMAVDHGtsFKhurRpD0Mmlh0Y 9C2WbB4lbRL8qVSOTppzNg6csMFyTFqI601pB8kjQr9KSM84S9yLW0aMAaSdC9AgkGMUjA 1RRRuEyPAs8jV3jkRzqW+qiLCGp3is1aOL3dpg8RlXDTLe30XYMKoSwXuKh80Q== From: Herve Codina To: Vadim Fedorenko , "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , Herve Codina , Yury Norov , Andy Shevchenko , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, netdev@vger.kernel.org, linuxppc-dev@lists.ozlabs.org, Andrew Lunn , Mark Brown , Christophe Leroy , Thomas Petazzoni Subject: [PATCH v4 3/5] lib/bitmap: Introduce bitmap_scatter() and bitmap_gather() helpers Date: Thu, 22 Feb 2024 15:22:16 +0100 Message-ID: <20240222142219.441767-4-herve.codina@bootlin.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240222142219.441767-1-herve.codina@bootlin.com> References: <20240222142219.441767-1-herve.codina@bootlin.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-GND-Sasl: herve.codina@bootlin.com X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791609375511215494 X-GMAIL-MSGID: 1791609375511215494 From: Andy Shevchenko These helpers scatters or gathers a bitmap with the help of the mask position bits parameter. bitmap_scatter() does the following: src: 0000000001011010 |||||| +------+||||| | +----+|||| | |+----+||| | || +-+|| | || | || mask: ...v..vv...v..vv ...0..11...0..10 dst: 0000001100000010 and bitmap_gather() performs this one: mask: ...v..vv...v..vv src: 0000001100000010 ^ ^^ ^ 0 | || | 10 | || > 010 | |+--> 1010 | +--> 11010 +----> 011010 dst: 0000000000011010 bitmap_gather() can the seen as the reverse bitmap_scatter() operation. The original work was done by Andy Shevchenko. Signed-off-by: Andy Shevchenko Link: https://lore.kernel.org/lkml/20230926052007.3917389-3-andriy.shevchenko@linux.intel.com/ Signed-off-by: Herve Codina --- Yury, Andy, I hope I correctly took into accounts the comments reveived on Andy's v1 series and found good compromise to satisfy your different point of view. include/linux/bitmap.h | 101 +++++++++++++++++++++++++++++++++++++++++ lib/test_bitmap.c | 42 +++++++++++++++++ 2 files changed, 143 insertions(+) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 99451431e4d6..a171030ff71c 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -62,6 +62,8 @@ struct device; * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest * bitmap_replace(dst, old, new, mask, nbits) *dst = (*old & ~(*mask)) | (*new & *mask) + * bitmap_scatter(dst, src, mask, nbits) *dst = map(dense, sparse)(src) + * bitmap_gather(dst, src, mask, nbits) *dst = map(sparse, dense)(src) * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit) * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap @@ -487,6 +489,105 @@ static inline void bitmap_replace(unsigned long *dst, __bitmap_replace(dst, old, new, mask, nbits); } +/** + * bitmap_scatter - Scatter a bitmap according to the given mask + * @dst: scattered bitmap + * @src: gathered bitmap + * @mask: mask representing bits to assign to in the scattered bitmap + * @nbits: number of bits in each of these bitmaps + * + * Scatters bitmap with sequential bits according to the given @mask. + * + * Example: + * If @src bitmap = 0x005a, with @mask = 0x1313, @dst will be 0x0302. + * + * Or in binary form + * @src @mask @dst + * 0000000001011010 0001001100010011 0000001100000010 + * + * (Bits 0, 1, 2, 3, 4, 5 are copied to the bits 0, 1, 4, 8, 9, 12) + * + * A more 'visual' description of the operation: + * src: 0000000001011010 + * |||||| + * +------+||||| + * | +----+|||| + * | |+----+||| + * | || +-+|| + * | || | || + * mask: ...v..vv...v..vv + * ...0..11...0..10 + * dst: 0000001100000010 + * + * A relationship exists between bitmap_scatter() and bitmap_gather(). + * bitmap_gather() can be seen as the 'reverse' bitmap_scatter() operation. + * See bitmap_scatter() for details related to this relationship. + */ +static inline void bitmap_scatter(unsigned long *dst, const unsigned long *src, + const unsigned long *mask, unsigned int nbits) +{ + unsigned int n = 0; + unsigned int bit; + + bitmap_zero(dst, nbits); + + for_each_set_bit(bit, mask, nbits) + __assign_bit(bit, dst, test_bit(n++, src)); +} + +/** + * bitmap_gather - Gather a bitmap according to given mask + * @dst: gathered bitmap + * @src: scattered bitmap + * @mask: mask representing bits to extract from in the scattered bitmap + * @nbits: number of bits in each of these bitmaps + * + * Gathers bitmap with sparse bits according to the given @mask. + * + * Example: + * If @src bitmap = 0x0302, with @mask = 0x1313, @dst will be 0x001a. + * + * Or in binary form + * @src @mask @dst + * 0000001100000010 0001001100010011 0000000000011010 + * + * (Bits 0, 1, 4, 8, 9, 12 are copied to the bits 0, 1, 2, 3, 4, 5) + * + * A more 'visual' description of the operation: + * mask: ...v..vv...v..vv + * src: 0000001100000010 + * ^ ^^ ^ 0 + * | || | 10 + * | || > 010 + * | |+--> 1010 + * | +--> 11010 + * +----> 011010 + * dst: 0000000000011010 + * + * A relationship exists between bitmap_gather() and bitmap_scatter() (See + * bitmap_scatter() for the bitmap scatter detailed operations). + * Suppose scattered computed using bitmap_scatter(scattered, src, mask, n). + * The operation bitmap_gather(result, scattered, mask, n) leads to a result + * equal or equivalent to src. + * + * The result can be 'equivalent' because bitmap_scatter() and bitmap_gather() + * are not bijective. + * The result and src values are equivalent in that sense that a call to + * bitmap_scatter(res, src, mask, n) and a call to bitmap_scatter(res, result, + * mask, n) will lead to the same res value. + */ +static inline void bitmap_gather(unsigned long *dst, const unsigned long *src, + const unsigned long *mask, unsigned int nbits) +{ + unsigned int n = 0; + unsigned int bit; + + bitmap_zero(dst, nbits); + + for_each_set_bit(bit, mask, nbits) + __assign_bit(n++, dst, test_bit(bit, src)); +} + static inline void bitmap_next_set_region(unsigned long *bitmap, unsigned int *rs, unsigned int *re, unsigned int end) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 65f22c2578b0..6b2b33579f56 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -380,6 +380,47 @@ static void __init test_replace(void) expect_eq_bitmap(bmap, exp3_1_0, nbits); } +static const unsigned long sg_mask[] __initconst = { + BITMAP_FROM_U64(0x000000000000035aULL), +}; + +static const unsigned long sg_src[] __initconst = { + BITMAP_FROM_U64(0x0000000000000667ULL), +}; + +static const unsigned long sg_gather_exp[] __initconst = { + BITMAP_FROM_U64(0x0000000000000029ULL), +}; + +static const unsigned long sg_scatter_exp[] __initconst = { + BITMAP_FROM_U64(0x000000000000021aULL), +}; + +static void __init test_bitmap_sg(void) +{ + unsigned int nbits = 64; + DECLARE_BITMAP(bmap_gather, 100); + DECLARE_BITMAP(bmap_scatter, 100); + DECLARE_BITMAP(bmap_tmp, 100); + DECLARE_BITMAP(bmap_res, 100); + + /* Simple gather call */ + bitmap_zero(bmap_gather, 100); + bitmap_gather(bmap_gather, sg_src, sg_mask, nbits); + expect_eq_bitmap(sg_gather_exp, bmap_gather, nbits); + + /* Simple scatter call */ + bitmap_zero(bmap_scatter, 100); + bitmap_scatter(bmap_scatter, sg_src, sg_mask, nbits); + expect_eq_bitmap(sg_scatter_exp, bmap_scatter, nbits); + + /* Scatter/gather relationship */ + bitmap_zero(bmap_tmp, 100); + bitmap_gather(bmap_tmp, bmap_scatter, sg_mask, nbits); + bitmap_scatter(bmap_res, bmap_tmp, sg_mask, nbits); + expect_eq_bitmap(bmap_scatter, bmap_res, nbits); +} + #define PARSE_TIME 0x1 #define NO_LEN 0x2 @@ -1252,6 +1293,7 @@ static void __init selftest(void) test_copy(); test_bitmap_region(); test_replace(); + test_bitmap_sg(); test_bitmap_arr32(); test_bitmap_arr64(); test_bitmap_parse();