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 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id E0DE4C282C6 for ; Tue, 4 Mar 2025 01:20:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C309B280004; Mon, 3 Mar 2025 20:20:41 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B9454280001; Mon, 3 Mar 2025 20:20:41 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A0EBF280004; Mon, 3 Mar 2025 20:20:41 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 7DB01280001 for ; Mon, 3 Mar 2025 20:20:41 -0500 (EST) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 24CED52EA0 for ; Tue, 4 Mar 2025 01:20:41 +0000 (UTC) X-FDA: 83182113882.14.B11C554 Received: from mail-ej1-f44.google.com (mail-ej1-f44.google.com [209.85.218.44]) by imf18.hostedemail.com (Postfix) with ESMTP id 3E6131C000A for ; Tue, 4 Mar 2025 01:20:39 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=W2rTohIm; spf=pass (imf18.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.44 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1741051239; 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=kI0zXTtiY0d3vsDTb7OzwfiDVtUoCDm94bbENlqCAVo=; b=C2g8T9Y4UubI1E4VJUHDMkCvhi7K8z2RutKk2J2/CL668vzLN6mLom/A5ybjsLKO6n/5L5 sIZKKFYV1923DWHt8Z60xJKyK5glngBci8bPYKfbCDaK2zDS9ojmm5Goejdi8wo6KdBZrh 8TkFNRS/7X/oiz42bT4/C5lFNRwC27M= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=W2rTohIm; spf=pass (imf18.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.44 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741051239; a=rsa-sha256; cv=none; b=BypYk4ZglQWTCLl7Qyt1rN82fhgAUZqaZiLIu8HZHwpnNbxKZx14crCD5VanMjMQf+Ob8/ n85+k2xGTKaptex1SeF9oGKQ5O82PReiL3TedGYgkI/ErLfp+MVM8ngPbUQ+Gw9KSeV7Dy FjA8Spg4NSLoQH4lqiQhkX2aKx6ooiE= Received: by mail-ej1-f44.google.com with SMTP id a640c23a62f3a-aaec61d0f65so1035515266b.1 for ; Mon, 03 Mar 2025 17:20:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051238; x=1741656038; 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=kI0zXTtiY0d3vsDTb7OzwfiDVtUoCDm94bbENlqCAVo=; b=W2rTohImCvqLDymh/9ycz2morOEOlaqQju+mOFRAJh/kIjgfkmK4Z88CzDAB5Ewi6H U9DPIPTYJ29UwPbn2WE3Y/3fn+NgIt5FASrPAM+BmMCvde8TbFn4BN1Fwyb8nPgOvKZ/ GvPgoikatHrb9tugkRKZ/bi7v7GkiH1ibCS+q8IHU/xSMVt2Iq9b0zgJ6bBChVlG8rSs JonshvU6S8/9GH7QRGyVEMX6F51/dICtU0r5rja9MQupUmOD93RHEeNEZNPQ8ChAIl59 Lr52VvOUA6Jg3avumudhDmQRjpD96pQLY8CW74f4s9IoU07ixdEU0It89LA6tbtP4rMb +gxA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051238; x=1741656038; 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=kI0zXTtiY0d3vsDTb7OzwfiDVtUoCDm94bbENlqCAVo=; b=QmPmNddBXx32Py84VYgQXyHZSHgcu8r+FGf3s1WqzCj2wdVaCyojpUq0dwbj2rmL2e QCXJlxGLbmMcAYql0+n6YgocXiAJ9vT8o/01TKT+QZSfYRXMw2vexBc/hjjd1nPNudVi QQFeIVfYGGCVW17T+33BPFtmE4BQIHK3bTdCYgcbeYtJs2U6hXft1aobe1hsFrQaUH4p 1bG7+YLOspQH6Ia8lzD17HgPk7tSQWNgj1sfgtGUpQ1a7Tr7qwDdVH5wqlmLBO02xbZz O/A4N6M8wK7KgO1tVmWI+/XNETxfukSyFAsCvO4gVdjlQLpLhMkwjMG0bwJ8QRClQi1S 9MsQ== X-Forwarded-Encrypted: i=1; AJvYcCW6/iiLeqolJUTSKcye3Fxc5MWteYz70eY/yI5Q+Ue4ZrDz/c+YDO4L9+RoQU6Jp59+bP5A9nWjTg==@kvack.org X-Gm-Message-State: AOJu0YyzH3p59eBg9c428ygnqsGZCGU2MNKjDkn00WFbhh+B+Nab3Ujf 0hJGJdjhp++ElVTKOMTg1PHzyYX+ULU3ZtrY9SndKtv3a+RhAj2A X-Gm-Gg: ASbGncu3U8DNIHBxtzN/Aq17AKMpyT9f+PXDPIePQ22lYG8mvdIO1Fw8FbqAomqkB63 5DNhJW2hSIv2lZdHfMPMZGDmkWT37BmpSPGVv949u0BTgvovCljagtNBe9PqNjMbYRC6fHDmD0V RokOZEvSXkLywyKhjjMWnEu2Dy/ZJu/reAfeEvJgwPTK1rTpCGmds3urxAh4oY8uA6s+A8Tg5dU 3ACtqfsfzbUioDIIuNUvDGrqOakSwLhpJ0wf1oezb5gFY1D9GH9yXW5bRRRpPXFu6lzKnU9sVlo v7EWgWkAAJOKcML5V46jHrIZizs7ICSjPvMSLNt46oIA X-Google-Smtp-Source: AGHT+IFEQeUYLyRIsjAeunAdMQ5YhiOIMBGu7uG/yqOXKgPF2gezLht/EMqsxTBBRcb6dvDEkvY3fQ== X-Received: by 2002:a17:906:c149:b0:abf:67de:2f25 with SMTP id a640c23a62f3a-abf67de36cdmr925051466b.33.1741051237808; Mon, 03 Mar 2025 17:20:37 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac1da87a727sm186131466b.139.2025.03.03.17.20.37 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:37 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [PATCH 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers Date: Tue, 4 Mar 2025 01:19:49 +0000 Message-Id: <20250304011952.29182-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250304011952.29182-1-richard.weiyang@gmail.com> References: <20250304011952.29182-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 3E6131C000A X-Stat-Signature: tgnxjpjyuyycxc1amquer9b7tfb5fj11 X-HE-Tag: 1741051239-266273 X-HE-Meta: U2FsdGVkX18rKuEvzGHg3BAfOSKfWX/aqSGV8k4JRXs/Vc8BvdkRN7ge1wLXCyPdt4qUixzfSw7BPqwG51CmF8zxvjJ6v0o7CsqWydU3KSSEFsVUOSm09uYMRPfHwPIjT1mB1etwOkCSIRWE+ZdJN1C17nusBnSHMLWgC13sU/WtlVqkRaOiST9S/BLYLflJobFtq9mugHBa3T0pcoDc6ggI5lxseyDeWWrAoOv//DPmZ3NJMG5YHTeJI3DFbWIXj6Dpmhw2nCsRIP5mdisVagxTO3eUxrAruweFMvPqOqu85ojq7dZ4Eu7MSAcnE3WyyVmYbGYCDbLjIQ9fC+tJF+sQKz1m3FpuR6+HfnLZC6N220z6Ygu078Trcyy62njitcck/FWsI/HYoDcDq6LjExu5CrlnwdSGSVLkJsVrsLCM1YDKBMb7eOr+lPdksX1YAReFsEuBQRHurxGwu7pluzDcB3ol4Wp22GZyDnOfPN3bgJSj1UsJtzpnnbqHlBe9yl4vNYwqmR8UOmoBYf2bBFg4TMFGc2xgyJQ1MhxVv8wYcwqR/UaH+aYsQBVD7/b+ztFzMdk2uuuY9abkfUyVaOmw7iJ76B9u6I1Z5xmPBTl7JSILrXLpYQBkfFaXwgcoXmv57xK1sUZc3uI7k5d2NtGkRWGRg7keA266ouEk/i1to4DmeN0r2nhZN0ZKDsGNmrlsbWy1WwL4bExvxGzqsXZX8E6YfrPoBNl9Nc//uul0/rfC0fM3rvED6LOlwhU0qidfOBm3FnARErw5tDIz2hcGjbNOgGLxxfrgVrQzvYNWcMofKOQJnC4e1SjiAeHLTn6O82dyARZ9KnNlDX10l489n+vHuCYj82u7WooPCGXQoPoiigFsbO1/kLE49QSdGBvcSiQVfwrxt8nYlFQvYn5E4bKjMNWZLGnu2WRVCuDXh5WWvQ50bjVWVY93Reu4CYjVm5FD1rtNsicI9Xk xsgVQ7qe EGvjy0XbUBxLJxHhO7DbTVFFb1VsmQqQ0L8tnvnO4cR9o6bDEZmTSaNGbrxoy4B5wFsBBv4kkGaVfJUUbcs/ATEcC4BzSIhqmhSopKIKdoFwwpH9b91WgVhgqegpVYTH7x1DIIpgJdfXn3ofjFgh0k7d0P1CArXkIHyqEG0guNg9rLkb0faN0CoMy3NJukKFNHEvMhAzIxGOitNXEeowNoSmu2lBp0z6b4ORt17KeQNL/YuuudDFpg8+GbyUyMk91yKub/zjfHKDQsCMwsSNRU5F7HHQjxJVaTJtoEEI+3WVuqmIN8FGN+I2+IX6vZEROui305dJQVv/taGAgTUhzdSrkk2waFTlt3EvooJR242pkIG3stj50oHCcwMt6KW475qxJSSsGVdRtXhCDb15/WOAHmMh0FR4oork+9yiwHdNlTl5db2FzJG2kH+2xkSB1qdvc8Hdb9/+IAzPpSsCnfc4tJSZwqKTaCbn3JlsRHULjSTaANR3liKS10A3Kzk+2rEYCbLKEFEqVg/KD+uCsTLKN8WQqEdbOhZ/nkXPwMvQT3tfHVqM70GwYFV8jHIK5n5tBKh/Q8cjLeyjbOW+lx0Fd8ePyGBQeXbmzKzV3h4SLjITUgCkScNXzPA1PEkFJ8OCQc8NLOyfwfqG8ymGlqcsQHw== 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 51cbc50d4cc5..383b547e8929 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); -- 2.34.1