From patchwork Tue Mar 4 01:19:50 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999763 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 AD205C282D1 for ; Tue, 4 Mar 2025 01:20:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 097EA280005; Mon, 3 Mar 2025 20:20:43 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 02353280001; Mon, 3 Mar 2025 20:20:42 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DB580280005; Mon, 3 Mar 2025 20:20:42 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id BD0CC280001 for ; Mon, 3 Mar 2025 20:20:42 -0500 (EST) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 87683A5CF7 for ; Tue, 4 Mar 2025 01:20:42 +0000 (UTC) X-FDA: 83182113924.24.ABF808B Received: from mail-ej1-f42.google.com (mail-ej1-f42.google.com [209.85.218.42]) by imf27.hostedemail.com (Postfix) with ESMTP id B8E3240002 for ; Tue, 4 Mar 2025 01:20:40 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=WSakm2Kj; spf=pass (imf27.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.42 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=1741051240; 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=N70gg8cD7fTDy6kiKxq+x5TjzZfv2LA60+seTj4/nVQ=; b=YMqXU9GbUu6tsNHG0pK86qr4K2+L7TRvntOLQP+/XBhT257LnctksIMVNqHVg1264gYNo6 vmufXjMhTC4U7pNf+aZei/eKr99CmQ1o/iwYMiLNFEZpLX7PT23AD+yHOxEC8rQPbJ4tmr 1blUyD9EE6U/vK+OFeiFRUKMNRC//3U= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741051240; a=rsa-sha256; cv=none; b=xYt6NbSwyh2RXZgbNI+gwpOY6O8j8effGg1DiICntPEdT0l0cERIK8UMT3QjZA8sQ16q/0 1hSOeTXGUypRJhVZQSMUo5F5yJggyX2k+Uz5LrlBGYhRJYWQPXowKT6cJQqBIQF6aQKrbI kPj4nUArawhLWGdEUjGlkTIljYF00/w= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=WSakm2Kj; spf=pass (imf27.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.42 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ej1-f42.google.com with SMTP id a640c23a62f3a-abf5e1a6cd3so415640066b.2 for ; Mon, 03 Mar 2025 17:20:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051239; x=1741656039; 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=N70gg8cD7fTDy6kiKxq+x5TjzZfv2LA60+seTj4/nVQ=; b=WSakm2KjQQw5dqVbfm8mK8tMUdZ5a+WtWQE96/P32t3ZC5NPwNffQ3LRwYgBnYVrU/ L3C0MYGxkiQTw/zGOD5VlMK/LYHgZYvPk9KijWXvOmDeoEwaQc48dsti2ryI2ZbaalA+ MkVGvxlkrhA16dWj+u7+6PgdI8kLPZpwxdfes4fPbQmBZTh03XJboeP/YkoOH/DrO1n4 jZiWG8kr48pgN8ugPeV+0DX678jS+QV45v6U/TXM9VHf/rfWAE6mgXp9/Sw89jIOhh1O slQrb+AkhblBBTBHQ89DhWi76WTfP3lzdnwLAVjibMEZQaRshEGrhAF31i1v+iSHFGe5 D90w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051239; x=1741656039; 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=N70gg8cD7fTDy6kiKxq+x5TjzZfv2LA60+seTj4/nVQ=; b=uJPQ4agDb0NfktLeSbggzAAJjkjBH9s3/Xjc6EiaQTsFPmctv1C+7okcko44lS/SeX zbWYziaOG6iXnrXNq9lLxSGUhYwe0+uGpyVRTGdoXwH1t+gcTzZ6HYgrUjjzJwbYs4ua jDsAu08UqeW8T+ByiEb89fo8XBR300q3kp7j9+CHFoRxiPLCVsPKJ+XovpM6ImpYFpBd AAVD7I4j4v94aQvizx6Ty42w8Xhoz1pkCfIrH0W2NGe77YNk+52N8TSKvVtFiIbmMEQN Ka5NL7cJ124l68zi8g0VlMtBaZ4wcaGZBi0Aa9EKrdn8okeebSuAzTpFgY87EIPJHVR2 YNcA== X-Forwarded-Encrypted: i=1; AJvYcCU9wEBRze3sNX/0J/z0A/AQf0kzDx53fvtWisvUAgbNXEfvS1SG5fN9ii6coacQiMgtRjWOh6Se3g==@kvack.org X-Gm-Message-State: AOJu0Yz59EAgSXj0rTi1PY+5S6oohYW5qq+0e8xzOUKiHQla4An5VoD1 2tisfIIlHQtlj0VMuYgzBukjvfpnmB8iJfVvMIDBoh6MkgU80aGo X-Gm-Gg: ASbGnctxvXex3DbAWcZbsvOvvKTs9FYp528d8UEio1quLjEiJA7vQpLcPLbbgjFZoaS jY/atgmD+77pPwtTDt2m12uDb8kV5a3eSbvQl5dfpwTVt+78I5Rb2jfxHRItVLviMzeK1Dh6P6o PXcgKS0mrkLcVM/i6eaGnyfGseaJXgzKLEZVU0pTxCqIjR0Dqu/D9FaNmHWC/GMKVirZq1fJXs3 solZtp0llfArCfaac2W3A6i0Ch1BrmbTr6jdGOhbQxOp61AIJUP0q2qfeyrOH5p2ahq/bZKBi72 H15I5IUEKeYX2eIrn1TphkLzopWrqTRwmksZAltGI+ip X-Google-Smtp-Source: AGHT+IFBEAltAa8+oSNwY+4ppbSKF9k/IiHTk1vNQzXRfC4hSmf+4at6Xu4Sw5MdnpuKJZm0zAkVXA== X-Received: by 2002:a17:907:98b:b0:abe:fd0c:68a8 with SMTP id a640c23a62f3a-abf2682e175mr1899406466b.52.1741051239235; Mon, 03 Mar 2025 17:20:39 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf0c0dc5f6sm885005966b.53.2025.03.03.17.20.38 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:38 -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 5/7] lib/interval_tree: add test case for span iteration Date: Tue, 4 Mar 2025 01:19:50 +0000 Message-Id: <20250304011952.29182-6-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-Rspamd-Server: rspam02 X-Stat-Signature: uytytjk6t5gb4sfesgtqxtfuurkr5ce1 X-Rspamd-Queue-Id: B8E3240002 X-Rspam-User: X-HE-Tag: 1741051240-822582 X-HE-Meta: U2FsdGVkX19biKDPvOySnIPyoGNtsGcOvQrwarXHpSEsufpjqx3Yukf9m07MLEcmmr04N8JXtg4SbP7AP6Gl8lmJEhlofy2s5e6dSprI+CIJsWomtmF/39CDMpCzgoiRE9qizvJI+jot4sHXQ6on/7aK+ghM44afhBkWg0uHeV34eWN9nopS97q0AopssFmBChIwR77VT0yzCxFU4u/ZGkGZK78mwYcn40wxRM6hMYsaBqtPOtwKMnc7xgr08JFTcLA1d78wDeOsqQ+qlYkNV3idbbGxN1A5oNDbc6te0O+3pHXFMh0cPQvkyYA3D20xATMiqWdhQZV2aq9Wi/Ade1Qz5/LAW8sV6R4E9gkJYMKvs/HR/b/6qM25yeNbU+42ZYzJPdOUN0hRm8e+GkRfTUHt/EeojksDmwy8/lah/LvRlVd8RFhTwhoNgq13OrFawa7JFRzpgxImkKdX1bzopQdj5h40vNHbDKePs4dwfAT31ps/12I7joWd853oWE2I5vvIOSxihkTt1Y6n71sqyfKUL7aPlNgm7a6XXsap+Smm1Me7GRpNWqWfiKKmmm6+QO686256nWwQZNj2pQjDdtJy4PqVks5ABDikami4ghkKuz8DJJDvW/tBXVU/WmX5vrX7zR4RDD80HO01ntg1yCMHD7l7Pr84CTEBzUcdAG1LuHu5WtRvNzefymkc5JCvrXu1Gb3++84LT2Cyvj70/9VaUiFLHnttiTqwXVxrrSvelVbsTEDdgtzBHd41j0CRDildzCdTeMF8br/k63rZm8d2hNWruRbxeX18Y0diXda0I89adSt7x8KIO+R0FBtpAp6+taF7BWNYHObHtBjNXX2+vzfr0+fWR+Z0Jf3zSKMRxyCYEAaVAMRDFeq3E2UDDV9CLNNiwpRXwsF5UTRMxu77xlxVpwW+cnabJ3Go9zb7hV9dS2/qhwbEWOnYWdkFqrLMOZW2VZ6H2VmYkyJ mgq4NKeJ GHyLdZ9Ljx3A8bWhDFWvXG2OeWkYzQAIP67e7MvIjRTYcUEZRLQ0mdV31dYzWXS6VLbYwdEWNJMmeJeV7da8ZxVQB2X09GyvZC27HxoLJnLxfM/CPdIjbH0KJQSi/T6ivjeYSsPiBVwQs4vfWFAOvXGLyO6+tbVWwJhoDqwDYAIc2G/ewp6ioxCmT/do3OXDnMJFEZy8mnZxnfbJ5PidELepZkTABOjvZPLLofAQALvRMHVV4THH8g9jvNxkt4O+PP392dYIqynIt2Qx/Kr4S9shrVyliIwvKLYqY7CnnJmjnz5tJ9eAMuJ+TmKweDLh8wS5v0rnvmvksureenPjfNlkx24EgknGb8X3bJ3QR9mURw8RC5n0blzL8bIhHVTly4eAIrKJinditpNuQ4LA82awOl06gkgXRgNPa/Ls0AsT3S4ByQzIGfpxHYJ2LRCUzq/spjQ1kVOICqUBo9tSVUym5DghcC8QsizH2WXpL+1zk+swgDWVjLVWHyDzSHS8Lm1xXERFdwmRreE6pJd/LAprOV3dsorOJxPvf1AGzQSTDOMyIkbnKERUd2ujoVGvylS82Q9Tdwy7tZH4GBYgMqZERp+EfOvNDbqepNgWr72zFBJFqd0Ouo1GpfcKbS0gGXmK6waXBeyxjd8XgxDdi4IWoag== 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 383b547e8929..37198afa87ed 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; }