From patchwork Mon Mar 10 07:49:35 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009365 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 47F73C28B2E for ; Mon, 10 Mar 2025 07:50:02 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 429B7280006; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3B2DD280004; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 204C3280006; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 0659E280004 for ; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 95771B7767 for ; Mon, 10 Mar 2025 07:49:54 +0000 (UTC) X-FDA: 83204867508.16.A184302 Received: from mail-ej1-f52.google.com (mail-ej1-f52.google.com [209.85.218.52]) by imf12.hostedemail.com (Postfix) with ESMTP id C1B2E40006 for ; Mon, 10 Mar 2025 07:49:52 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=TKb1fn8O; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592992; a=rsa-sha256; cv=none; b=m2O0ULje0teSfrA4z1K/5TtSKTCv2opnExZGNX4+WCrKXIHuFi+B34H/6VbFoewkQw5h+u 4KJAS1Bt7ZHVudzig1m57WvbZOVmkNGrn8n8CzjIk5cJCyKKeM0K5ETsLKq2DV0TZBKgea HQxnQdsD1iTnWYg647nbOAJ6WwM/S3Y= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=TKb1fn8O; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1741592992; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=joz/03VnGW14f0pZtcpHMTRILy/FcawI+lP6p4ltkek=; b=he58xI5Zoxh0XpJ9K9BH2vUCz0+NOtygHFL7JHBJZqRgRQEsZ5TNY4DuzK3yB02MBZbx6u HBgAemjosZ0yoRRyT85kQDOtKGpkoaD5+wJ79IyCTOE0CCunCxvupdK0d80pYXY14ghWLa 89bsxyGSq8TbQuM7fN+UdX4pwfHnGLk= Received: by mail-ej1-f52.google.com with SMTP id a640c23a62f3a-ab771575040so909805566b.1 for ; Mon, 10 Mar 2025 00:49:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592991; x=1742197791; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=joz/03VnGW14f0pZtcpHMTRILy/FcawI+lP6p4ltkek=; b=TKb1fn8OG7Ophef9oRtLp9y+HMCsDkpOZ6aUeqomti9xucq6VsOjQL7hm1Gy13sXX9 iqjZVHxVEO7CkA1MtY9P1fAowNTEpQvaAv/YMC4VMr13lPwgz8gbCrOjmWruSsOHn8wW vEcTQhHyCa4CmP6jC67D73U77Bh0i8Ci3xGij3txQgwOWa80E/dz8RVN1qR9JiRGW4GC Hwqe0jwu5RK7F3JvNUQoAKBeTdIZim1fuEO4f4KVY8kUw2KPABW2pNOtDmod//kmaASo vJNXe6ICE44WB7X6wt63gfV+43j6JiZrtOgdwOwwTM3l+vGxITyRFy7jrSX+g6xcnEg4 G2Xg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592991; x=1742197791; h=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=joz/03VnGW14f0pZtcpHMTRILy/FcawI+lP6p4ltkek=; b=a3D8c2yS+yuwKYMzSPUVbPD5uxlS1B7yy0qG/L8GpYV4pEZed5M3S/FXT20WG7CmwG 9WaESdQZjP8Re1zg5PgZGpBePzkNBqwSjLwibb+BJfW+ShwXnpy3477zKO+X9mmfl4QB wlSggwdnQ+bNIXkojh9hzWzdxbOod/TTAzLpdNQ8J5XJORXQUvbWoLLOH7cgAlaT1G9Q nKo+l1q7sWRi18DVpxFtfFfgUPd+lWAz/0lpw6qMbLvEqqHZp1XNp3BsUyLZouUIxGF5 zXfJDRKAtkM4T9Rz0+wKnv8LUmOJrvGediujvPMsB34kTh9803GBNh0kPT0OkL55bpAz jshA== X-Forwarded-Encrypted: i=1; AJvYcCVwd8iMK54R/nETnZ7S/DygiN2oiRGNikKu97TunwH9laD9POjXT9sHw/AwOiGHLb6S7F9wDz/q1w==@kvack.org X-Gm-Message-State: AOJu0Yx5/GnBZ1p8uF+bPrwFAPrkuwVD80DBrEh5VTwIkd0qaVBfAMtr lCnetqJR7hHWPvE1tcFxuj6TIRuUIM1eyNBrFUSA2VWZPfMUuBT1 X-Gm-Gg: ASbGncvYgy8JlbQwBEdAqrsccQ3l5fdhGca8MWNEwFcj+AjCJHvfmUlymkEYX/QIuCc 4TY4JOTpjG+Ex28XjvVKFiEA2UhDbXB1nAdtF1DNwqY5jV0F3wLGjJ8l1Vd3mCX2OqP9WgYbwlp xT8+REYvOYppyGPhNrJ0ccfMvgMMkv4RSjIzgVTQLTVIwZeUs+ezgb7Hpi84b069Db5iV5/3ngY vI9qpCo6jvIo27j5zxyRUMR80OdktJP9jTVHKucEiHB6ZGyXTVvJ4BR0+ivkMttOLULQdZ/XioW 37Sf6V/doswhv2ypGK3DD2hzpzJaSAxTEZPh6RIrRhwfwXWU6ZF0EZE= X-Google-Smtp-Source: AGHT+IFsHgng+oPXGP/cHdlWarbQNchvHfc9aERG+HQj3txMw2RZfi2meBLJa9JQDhhcuIiBxITKAw== X-Received: by 2002:a17:907:1908:b0:ac1:edc5:d73b with SMTP id a640c23a62f3a-ac26ca59335mr758842066b.8.1741592991238; Mon, 10 Mar 2025 00:49:51 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac2901427f2sm231575166b.151.2025.03.10.00.49.50 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:50 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers Date: Mon, 10 Mar 2025 07:49:35 +0000 Message-Id: <20250310074938.26756-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: C1B2E40006 X-Stat-Signature: 77kw41iagbscoo55fafwe6tsknq1tsiw X-Rspamd-Server: rspam02 X-Rspam-User: X-HE-Tag: 1741592992-632397 X-HE-Meta: U2FsdGVkX19qpE0EILDhKRuxUoUxASyYaJL40Ayk23jKMFjiwl31kAsZz7UDVvCVYNIpi/O50q3i66gYb+XtRSnOXZ/Rb99bP5LGjg2bVVBgtTN/p7+PT36jg+7+5XWb5XpR2r+RWHqX15nkQsNyO1uMqlZA2VDPi5jjDZQ+27EQ8NTGjzqsc94GaAxq23GbwRy2arCXztIpf5v6eE1AsxLI1CRZjL4cW5TvrXar/CT3eOl5JzGU7ydgB3KWOy/fS2DWxDcOg+CmjkBmeKi2rE5+QelPAer5DP1etxFhYqXHrTPFr/dFHRe5MYps34EageYFZ+E/K1T/stN4jXWUqwaeTn6PE3c1l1XcaB+4e5p9XjtnhjhWgwQZk7eZAEVPVt0RmGw3szm0+h/AbiJW7tHLIEzzZ9tJtVrFk17nnqW+/lJ1DNPhCDuTgl7R0jc8rwL+/J8OdZao17aa2BjoEDfkmUIeWp8ixaAP1zaNyCJivDJv+su8nP/fgoBuo68I8OHNmSk1V80AQ6v2P+nTEAOHhIkkzYYetVplPUrnmzl+rt88h/54zTwaE+BeQY4wxvIsF3tp1V7P6Pdxqo6Gk1VVyfwWv3gyfbj+36QS7vi27StBIkzFKqNpr44QSBi6szEBf52iRCOHkRakpaHldjIOEPBChSJHAN+4ygIKYckk5e9GKoi6zXLqL1tRl03KaC2Ci+IWsbIZl420nqtiSC3D0DWHMY6uhmftFPYqE17tFC2d1+xzsSGXM6HzfzdX31h702aviTO3IE30MirCOpOzEvSmc9NX697171bxaSq3X0GLyImdpJbhPzQTY/4qMEdL06jFCP0qsucxa3L1481v/kppciaxPEGC/d5PxLG4VllcX/+wnjtA5Ulod7Fg1eTlnUst8EkenDZ8+gZmHBtm3LPJI9rYyIoGTUDb7rB0Gts/htHlBdUwOK56jVlqAj12r8p9mW2NOP/3xZg yKwTmhth 3zMDlUIdmRLusCoxs9xeBouKPliukzM8arQQcrwflqr82NYmQZGWNSgeq6uOnsozlmDQVzYjYQEDvwdjOkWzqQWMs0bZ0aNet20bFliX5voAzDDS40p/ThWsK25DOThXON2c1kc0Po0csX05pTUT7vw3fy0K+cAnYy97FBvJZ5iNTTKQcGY07vaoHz6fBf2TC6l8aygZjSiwGht2ijSwQmrJFzXf6tIjVTb9wxJbwyDHzknpFAw5rPR8lxnuOIMeyZfKLEBzzMiNZgvzms0xyoqXR6E+tAfG+mc9718XweYqWU78Xc4va7BFyGqV0sF2asrRt5aGwvVDKFYND3/5+4VdBcv/4Fy8QG8bZIXuWhujHsrDDlN9Ws5tUrzMm8wFInfX6dYM7NcS8Mq0L7EjFzESaOOoA0og/PDPNpibZkby/vUJeosWFIcT/8vpQXB2CqoQUwBVhWywvxXs53ZVdSNJATMUiJycREzgiQo0JeALuABBp7igcy1M2G4fQ9JCTWxTl41HhbuPTv6DuORrMOs3girzmQ2pk1qLhdIbdfB7e/jB0yuQQT+QZ3Y2FZ51cr2/4mkFFGJITeJv9489N7eCgX/5MOcNtTliddsSADO2pP3jBevgHtJ1nvRxBaZi9No72q7skaIeGh7YM61mxp7r/6w== 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: List-Subscribe: List-Unsubscribe: Verify interval_tree_iter_xxx() helpers could find intersection ranges as expected. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 69 ++++++++++++++++++++++++++++++++++++ tools/include/linux/bitmap.h | 21 +++++++++++ tools/lib/bitmap.c | 20 +++++++++++ 3 files changed, 110 insertions(+) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 51863077d4ec..7821379e2c21 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -5,6 +5,7 @@ #include #include #include +#include #define __param(type, name, init, msg) \ static type name = init; \ @@ -125,6 +126,73 @@ static int search_check(void) return 0; } +static int intersection_range_check(void) +{ + int i, j, k; + unsigned long start, last; + struct interval_tree_node *node; + unsigned long *intxn1; + unsigned long *intxn2; + + printk(KERN_ALERT "interval tree iteration\n"); + + intxn1 = bitmap_alloc(nnodes, GFP_KERNEL); + if (!intxn1) { + WARN_ON_ONCE("Failed to allocate intxn1\n"); + return -ENOMEM; + } + + intxn2 = bitmap_alloc(nnodes, GFP_KERNEL); + if (!intxn2) { + WARN_ON_ONCE("Failed to allocate intxn2\n"); + bitmap_free(intxn1); + return -ENOMEM; + } + + for (i = 0; i < search_loops; i++) { + /* Initialize interval tree for each round */ + init(); + for (j = 0; j < nnodes; j++) + interval_tree_insert(nodes + j, &root); + + /* Let's try nsearches different ranges */ + for (k = 0; k < nsearches; k++) { + /* Try whole range once */ + if (!k) { + start = 0UL; + last = ULONG_MAX; + } else { + last = (prandom_u32_state(&rnd) >> 4) % max_endpoint; + start = (prandom_u32_state(&rnd) >> 4) % last; + } + + /* Walk nodes to mark intersection nodes */ + bitmap_zero(intxn1, nnodes); + for (j = 0; j < nnodes; j++) { + node = nodes + j; + + if (start <= node->last && last >= node->start) + bitmap_set(intxn1, j, 1); + } + + /* Iterate tree to clear intersection nodes */ + bitmap_zero(intxn2, nnodes); + for (node = interval_tree_iter_first(&root, start, last); node; + node = interval_tree_iter_next(node, start, last)) + bitmap_set(intxn2, node - nodes, 1); + + WARN_ON_ONCE(!bitmap_equal(intxn1, intxn2, nnodes)); + } + + for (j = 0; j < nnodes; j++) + interval_tree_remove(nodes + j, &root); + } + + bitmap_free(intxn1); + bitmap_free(intxn2); + return 0; +} + static int interval_tree_test_init(void) { nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), @@ -142,6 +210,7 @@ static int interval_tree_test_init(void) basic_check(); search_check(); + intersection_range_check(); kfree(queries); kfree(nodes); diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h index 2a7f260ef9dc..8166719178f7 100644 --- a/tools/include/linux/bitmap.h +++ b/tools/include/linux/bitmap.h @@ -19,6 +19,7 @@ bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits); bool __bitmap_equal(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits); +void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); bool __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits); @@ -79,6 +80,11 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, __bitmap_or(dst, src1, src2, nbits); } +static inline unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags) +{ + return malloc(bitmap_size(nbits)); +} + /** * bitmap_zalloc - Allocate bitmap * @nbits: Number of bits @@ -150,6 +156,21 @@ static inline bool bitmap_intersects(const unsigned long *src1, return __bitmap_intersects(src1, src2, nbits); } +static inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) +{ + if (__builtin_constant_p(nbits) && nbits == 1) + __set_bit(start, map); + else if (small_const_nbits(start + nbits)) + *map |= GENMASK(start + nbits - 1, start); + else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && + IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && + __builtin_constant_p(nbits & BITMAP_MEM_MASK) && + IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) + memset((char *)map + start / 8, 0xff, nbits / 8); + else + __bitmap_set(map, start, nbits); +} + static inline void bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits) { diff --git a/tools/lib/bitmap.c b/tools/lib/bitmap.c index 2178862bb114..51255c69754d 100644 --- a/tools/lib/bitmap.c +++ b/tools/lib/bitmap.c @@ -101,6 +101,26 @@ bool __bitmap_intersects(const unsigned long *bitmap1, return false; } +void __bitmap_set(unsigned long *map, unsigned int start, int len) +{ + unsigned long *p = map + BIT_WORD(start); + const unsigned int size = start + len; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + while (len - bits_to_set >= 0) { + *p |= mask_to_set; + len -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + if (len) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + *p |= mask_to_set; + } +} + void __bitmap_clear(unsigned long *map, unsigned int start, int len) { unsigned long *p = map + BIT_WORD(start);