From patchwork Mon Mar 10 07:49:36 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009366 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 F10BBC28B2E for ; Mon, 10 Mar 2025 07:50:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 24D9D280007; Mon, 10 Mar 2025 03:49:54 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1D689280004; Mon, 10 Mar 2025 03:49:54 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 07570280007; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id DB05C280004 for ; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 5285FC0A79 for ; Mon, 10 Mar 2025 07:49:55 +0000 (UTC) X-FDA: 83204867550.17.41CA3EA Received: from mail-ed1-f44.google.com (mail-ed1-f44.google.com [209.85.208.44]) by imf13.hostedemail.com (Postfix) with ESMTP id 899A02000B for ; Mon, 10 Mar 2025 07:49:53 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=DBKKzZLn; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.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=1741592993; 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=fSNM+BjsL8ldsVQ0jKlhYRMMA8VboPlTUZMvNfcAmYk=; b=besqQQ5atrLVFfmh2AJE4Cf8iGYXsutDvUUBuE0S8oQt0P/2RZdCgpfEMb+ZnivvWi1XZe BFKt8QE3+VM0xnyrEyelC7m1rDCqklzIcM14AmGffU6agiiLImxqVPChfZcVeppuh52EA1 AOXktBqYgtUy8gb1cq8e+DQnuPJT+pU= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=DBKKzZLn; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.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=1741592993; a=rsa-sha256; cv=none; b=n0Uialr9Zdi/gaIAwRn3YIp8Q2My//QtXkUUJvtlazHdrqkB5ipLhrIQIVzQDUk40WWHI9 aP4Si5IfDVAvLXtAfFw4RWzOpeVW2ntr5N9fY6UekKWyV6USXn+ysF8GiZ4nIZp2K/gh2L phBt+bSjrH3npnOGBgUIlS2ij2Oeejg= Received: by mail-ed1-f44.google.com with SMTP id 4fb4d7f45d1cf-5e5e1a38c1aso3430707a12.2 for ; Mon, 10 Mar 2025 00:49:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592992; x=1742197792; 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=fSNM+BjsL8ldsVQ0jKlhYRMMA8VboPlTUZMvNfcAmYk=; b=DBKKzZLnvHN27Aoiu7+Qr6aRds6p4M/gedvf9N+4C9+NJeFHnZjh56LRuKXSCa4qP6 i1yIUBTe/au6BtST0ePnTcBU0hW02WDVDmKK79oUbeywOO0znPacndf9lAOzcqO0Mutj um3X2WfPViJ/v2REZ9VNYpfe87z0aX+w4U2hg1atvYqog8xn3fz2rOit6XMPylKeMsq6 JTf6YTR0GeGuHXos0rbHIuw538I/ngS+2IgNN/9CC9XOItzJQRkR2qlEQqAA1Vl8M/cm LR0sam/rsYrqX503Zh1J8FBdmc9RXml5DTjZVKb7g10Q0k5OAhNogWbZ3PLl2Xt20lXx VOpw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592992; x=1742197792; 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=fSNM+BjsL8ldsVQ0jKlhYRMMA8VboPlTUZMvNfcAmYk=; b=evk0AP+AM5kenhQYV7VLyPNZMxfoU0hYwzDd/0fKzsP/R9LLd9fV/KbbUcoPBcE8E3 +ajbG99O12BDPYYyOw8aASdTT8htWsX1I0c6vsmZj4tf125hngE4xmqmTTFtXlbNQcH6 5zAvbsW7CUVdsgkWoTn9hD7sZ45ivAaGms1bldl4OF2W0ifr3rs1NrAjqzcworeSt2u2 mfJnbJGAXXq39XsEIozLJJpHHM1qe59PO0Pq5iPfqjBvENA0DmJDcGmhuGQydtO/uKpA hf7b2Kb49cKlv7WRMCHS4u3DZA+UM8HnVvij8OOXWI8b+7z4oE/uiitMmSh3X3BjNcLr fpHQ== X-Forwarded-Encrypted: i=1; AJvYcCWVqj3gYAPJ/+ArsmHYeH5KYtpkbPtXunEQIHP8oQnU9cOQoEcCPxQgARinGU6i+6OD2BSEC332XA==@kvack.org X-Gm-Message-State: AOJu0YyijIeSbMZ/9CsGEFuRLe0yJvRw8UkrgXetnsWhG0Uq3VC8xl/A agDNKdDbtAj5AJUi0CVVTyLNM3wkSaQ9gIi4t5+yE0kJFkJt/MPF X-Gm-Gg: ASbGnctEO9wI9oe5XFXuyEQF/ik2nacKQbnKR/pTp4gmAMescqsfyqI4KQe5C9w5sCp Dc04BztznzR7A6955pJhYqfonaofxoAhv1+k6DJ7QevzMX/3hzVSvkFVTFs9H+NKJYPBcHqla9u ceMCxDbtOMj9abCsqPVn+1Fxeye+ZKq+J2eyKIoyrVJ40uveukFA7Va6pRJo6s2fLjWrLo+RCXc WOadNTyz07IuCE7z8R1CaUGJNZXqwDHuhygydI5BZSzzAKi+qb42vIG5U+/EBzH9/allVESX+6K 8tAq/xP0ogKFXgfFlHYAjo9Rkc7k9+EuJI/36YbciZDB X-Google-Smtp-Source: AGHT+IEEhzEdUmOe/3IgZzeMQd7AIhsSTXxQCgkkFvUFa7EClkIVywBOwgsqXBU2JdOXxxU61WuIWg== X-Received: by 2002:a05:6402:35c7:b0:5e5:c010:e67e with SMTP id 4fb4d7f45d1cf-5e5e24bd6bemr27353094a12.31.1741592991989; Mon, 10 Mar 2025 00:49:51 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5e5c733f39fsm6698255a12.11.2025.03.10.00.49.51 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:51 -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 5/7] lib/interval_tree: add test case for span iteration Date: Mon, 10 Mar 2025 07:49:36 +0000 Message-Id: <20250310074938.26756-6-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-Server: rspam07 X-Rspamd-Queue-Id: 899A02000B X-Stat-Signature: hxrptd6eqaz5zjggs5ns6w4njngi4jqe X-Rspam-User: X-HE-Tag: 1741592993-965492 X-HE-Meta: U2FsdGVkX19MlDcfPlY6WqerGC1OKvAeIGeT2m60HHWmz22t0VLSoRQUUuAMJoKUfFwwvyfST+rxe1ImhmD9rRBNDEsZUBOv2CviEy1ew6fjZ8GAFSvXD1LrUt+KRn/g164sKbER5IgTlfL8rupdZGh9N7uu/sKGEVUAaLecq1T2bjX9RaSBcDhUgXirDOfKJlvMg7I0n56yrh3IrlLSJi4x5kksffQ6VzhR0pQ7CMDgHDSMRL+KkxpR/GcGsZ0ZPkM+3trWtngKaN+R8nO/CzIBnxKeti8icWfUi48dm65U6DijDxvuisP0wyKkf3JyxnS7jy5ibJeUJsPbFDfKyQmh1RHUiy2IAMIJYFW+YTtFWx4c48NSKMm/hW3DO2VOq6IekJaUF+Ht8QSpRaBF5FOF9qyoww7aeko1g6pkVApw/eZJ0SJYSy7LzrOsMyGPyUJFo2SO07avjjL2eLb63Cm7q6pQwWE/iyGg7YJ+OPb5W3jPRnHEQiNf1f1efP5s23m101qetuswUmAfSfsvg50j113GDPIjBhwoG5NxNd4WIY/aOnX+onXz9U0Gp0WNZLSstAZeS3pHtyR97qClF1U5fQDhcAK2bnIpUhHz2y5lAgCV8J2PwjJofdXjki2g8TmHgpPBrHvzBc79Kvufhu1U09U3oKsuDdvQor+zvnC+ALD7UTUotSOQBV/0JiL+VOitR8c+Vzgz+4lj+IGakgLCTRC/3j+l/zgjG7o2M6f1mA7SvMq+JYq3Zj4EpF76Tk87PEg2WKw/ZTi9OPgoPTo0NmCYUD2EuMSSdpcn5vjnqMwRVhQxl56e0N3SwOm4hIEy7B14aaZzjj0fkh7bXDkifgwfxe4CN7F8E8LuUVRjitB16eXn7Q+3mxWR7GXds6hxSn/esfS0p7teGzD42eLv5+Flog+PCy5LBPE99EqIGuF3xnLShtwfLFilWA9vYNue14t5SfvPO/oGEJg goXwg9ua p6wHaA3qwngzGpzr4nsSONBw8CwA4jstXOUUi7KNtxSaE/DfF4OqyWJh4j63/IIZ59J5Ulu9aE/ah7wkeDaj9Ly8p7H2LOr4n+N+9JBzea7FAHGzywAty7qDMixrV+ZyK4GlD5O71ewfgY/B40ThwEiMGL2F3X0HQGkZ19l12sYJ+v4qR91UL/WHwzVnVHzdCci2Pnw0Gyg3MYcnYiaa9g1X0S1KdNBHDiDnFjXRNd6D6vNO1DfTMBhYZSy8S6S3qvXOHdvI7isqn9XGjnC6pXt0Z+lH9igrmvphVa2lbTlpe1inrXcJRNs6QR1jzUr8WJhNabdpGvZyrnCZNmBf7zOvprAOlvXAh0gAePSMmvpiYamGxhrQrlJw1iqU4MMLOmqlEIC324sWSYxKiHxi/mFCEWgtS3t0zrwGL/u/Yc2hHEiglXs7uhCawaB1bc4knhBM6MF1SuMy3IrvWd1R9Gsnoh4+aP6vWJh67bMIgw2F+YH+5BKoEDVXWOPPC8vqAPKIl0q21XQrb+J1azbG/80RWN7UhmPsBviLsrg9YTyRQrHYlCyBPKm5QJX+qcjFyW9lGxzDGVk5A/Adt6JYSzWT8KCyczOypAzp6xQ0tQKaJAikU1A5V5AlfVxZYKSor5yXh7uwyadbwFrFlGgUHV7nO1Q== 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_span_iter_xxx() helpers works as expected. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 117 ++++++++++++++++++++++ tools/testing/rbtree/Makefile | 6 +- tools/testing/rbtree/interval_tree_test.c | 2 + 3 files changed, 123 insertions(+), 2 deletions(-) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 7821379e2c21..5fd62656f42e 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -6,6 +6,7 @@ #include #include #include +#include #define __param(type, name, init, msg) \ static type name = init; \ @@ -193,6 +194,121 @@ static int intersection_range_check(void) return 0; } +#ifdef CONFIG_INTERVAL_TREE_SPAN_ITER +/* + * Helper function to get span of current position from maple tree point of + * view. + */ +static void mas_cur_span(struct ma_state *mas, struct interval_tree_span_iter *state) +{ + unsigned long cur_start; + unsigned long cur_last; + int is_hole; + + if (mas->status == ma_overflow) + return; + + /* walk to current position */ + state->is_hole = mas_walk(mas) ? 0 : 1; + + cur_start = mas->index < state->first_index ? + state->first_index : mas->index; + + /* whether we have followers */ + do { + + cur_last = mas->last > state->last_index ? + state->last_index : mas->last; + + is_hole = mas_next_range(mas, state->last_index) ? 0 : 1; + + } while (mas->status != ma_overflow && is_hole == state->is_hole); + + if (state->is_hole) { + state->start_hole = cur_start; + state->last_hole = cur_last; + } else { + state->start_used = cur_start; + state->last_used = cur_last; + } + + /* advance position for next round */ + if (mas->status != ma_overflow) + mas_set(mas, cur_last + 1); +} + +static int span_iteration_check(void) +{ + int i, j, k; + unsigned long start, last; + struct interval_tree_span_iter span, mas_span; + + DEFINE_MTREE(tree); + + MA_STATE(mas, &tree, 0, 0); + + printk(KERN_ALERT "interval tree span iteration\n"); + + 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); + + /* Put all the range into maple tree */ + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + mt_set_in_rcu(&tree); + + for (j = 0; j < nnodes; j++) + WARN_ON_ONCE(mtree_store_range(&tree, nodes[j].start, + nodes[j].last, nodes + j, GFP_KERNEL)); + + /* 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; + } + + mas_span.first_index = start; + mas_span.last_index = last; + mas_span.is_hole = -1; + mas_set(&mas, start); + + interval_tree_for_each_span(&span, &root, start, last) { + mas_cur_span(&mas, &mas_span); + + WARN_ON_ONCE(span.is_hole != mas_span.is_hole); + + if (span.is_hole) { + WARN_ON_ONCE(span.start_hole != mas_span.start_hole); + WARN_ON_ONCE(span.last_hole != mas_span.last_hole); + } else { + WARN_ON_ONCE(span.start_used != mas_span.start_used); + WARN_ON_ONCE(span.last_used != mas_span.last_used); + } + } + + } + + WARN_ON_ONCE(mas.status != ma_overflow); + + /* Cleanup maple tree for each round */ + mtree_destroy(&tree); + /* Cleanup interval tree for each round */ + for (j = 0; j < nnodes; j++) + interval_tree_remove(nodes + j, &root); + } + return 0; +} +#else +static inline int span_iteration_check(void) {return 0; } +#endif + static int interval_tree_test_init(void) { nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), @@ -211,6 +327,7 @@ static int interval_tree_test_init(void) basic_check(); search_check(); intersection_range_check(); + span_iteration_check(); kfree(queries); kfree(nodes); diff --git a/tools/testing/rbtree/Makefile b/tools/testing/rbtree/Makefile index bac6931b499d..d7bbae2af4c7 100644 --- a/tools/testing/rbtree/Makefile +++ b/tools/testing/rbtree/Makefile @@ -3,7 +3,7 @@ .PHONY: clean TARGETS = rbtree_test interval_tree_test -OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o +OFILES = $(SHARED_OFILES) rbtree-shim.o interval_tree-shim.o maple-shim.o DEPS = ../../../include/linux/rbtree.h \ ../../../include/linux/rbtree_types.h \ ../../../include/linux/rbtree_augmented.h \ @@ -25,7 +25,9 @@ $(TARGETS): $(OFILES) rbtree-shim.o: $(DEPS) rbtree_test.o: ../../../lib/rbtree_test.c interval_tree-shim.o: $(DEPS) +interval_tree-shim.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER interval_tree_test.o: ../../../lib/interval_tree_test.c +interval_tree_test.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER clean: - $(RM) $(TARGETS) *.o generated/* + $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/* diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c index 63775b831c1c..49bc5b534330 100644 --- a/tools/testing/rbtree/interval_tree_test.c +++ b/tools/testing/rbtree/interval_tree_test.c @@ -6,6 +6,7 @@ #include #include #include "shared.h" +#include "maple-shared.h" #include "../../../lib/interval_tree_test.c" @@ -51,6 +52,7 @@ int main(int argc, char **argv) usage(); } + maple_tree_init(); interval_tree_tests(); return 0; }