From patchwork Tue Mar 4 01:19:46 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999759 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 B3E05C282D2 for ; Tue, 4 Mar 2025 01:20:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9721D6B0083; Mon, 3 Mar 2025 20:20:37 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 883916B0085; Mon, 3 Mar 2025 20:20:37 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7241D6B0088; Mon, 3 Mar 2025 20:20:37 -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 503596B0083 for ; Mon, 3 Mar 2025 20:20:37 -0500 (EST) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id EEA6C1211D8 for ; Tue, 4 Mar 2025 01:20:36 +0000 (UTC) X-FDA: 83182113672.03.2C7D116 Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf12.hostedemail.com (Postfix) with ESMTP id EFD4040008 for ; Tue, 4 Mar 2025 01:20:34 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=IK3KhK9+; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 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=1741051235; 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=6IRYqsy5kv8Qft9uaJF7Bfdin73pEBYViojMc1Cujz4=; b=jm28GOgj1n6obog8WZF5hrNT2eCgQjZnhFjAkvRPynkpDuRtIJKLU2qyMm7QDOAj9P7TOO GWj57SD4ZDy+d68PKViaLK+jaXvZRAKeiwyD7VFsyo50/fNa2VdFkGXd8WqsiswXbuGWI3 gi8o4YGH5pHitWISVFXor68ik4097Ro= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741051235; a=rsa-sha256; cv=none; b=AdNL+smauikq70fSBzDthzF8MHbTeWyLZ/5ZNh8ddvQVSyNBfN0X41xRchoTtUbXKebAnl RBCHDB+ClxDHxY7o1eAU7W5vaIyp4Wl7cRj13OJ5bzaz8cdSee4jbJlBCS5WkgigIZpjz8 daTp7k0Bh0sa+3NhKaJrZIl1cA9toLU= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=IK3KhK9+; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-5dee07e51aaso9492881a12.3 for ; Mon, 03 Mar 2025 17:20:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051233; x=1741656033; 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=6IRYqsy5kv8Qft9uaJF7Bfdin73pEBYViojMc1Cujz4=; b=IK3KhK9+w/t07QG8mH3uYwPJH6vov0L2S0GgFrV1UwEJAC4F7GWk8ruWQRini4z+BF ZzFveL/IWi2tVpgN3joLapmrP5FM2PhBuNrd0QBYQEya5d9VLL9Gf82ytHUmfmq61tu1 Kx2IJ8KTkmIv7+b+apqNWjZxryePgWVlWn8JBYoVUzNcJEVHifxsRDe9bymSBe1qLXoQ 2orBhCsuwA2HGvPpfdWVaAH64Lpzk23k+xMIvTLb9RglJZwh639D8lfFFlPZ+M2i0RPE fl4YoeNxfvviZrB6EsOsPQadqWFW5M6jHcCIF1EZ5265/IJIvH3V570WgePv4I+zZ58q fnnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051233; x=1741656033; 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=6IRYqsy5kv8Qft9uaJF7Bfdin73pEBYViojMc1Cujz4=; b=FjQgKlQR2hNlxeHam0NalspaBsQE+AtXPOZ+YTDtI6G96h7JDr5PgROrQEkBRL2uIy U+HYeUEofJInWFqMCto41h6WtQmGKZppV3w2NGeiaTuILT1Xp+9/bTvcpEG1IVphykWm sXXKBwIxXZ10uyuyzoAdGrmk9vkhoySE9lOQM1/GHcPXk+1ACWXa4m4vMIcSzVWQmQpp Fspb/GCsZm9Cp8kQ1+JeCte+TtJHJ3nrdj+PbEWkGiMRNb85NetiZJlNuaPw78twRMYp lhGXKkcK/IgLx/ATx38bhIcmyki3zBIgXh5SiLAwztrvE+fj0DteX/sFSAapQ2E+7bCW jXqA== X-Forwarded-Encrypted: i=1; AJvYcCVmrMz5xhvqyZlHBTmKCbdNBGT2k8bH6K4G7GmUdlEdHpwQ+qVGellCUMY08+UgVCne/7gseC5yjA==@kvack.org X-Gm-Message-State: AOJu0Yz6LvJQXEk3YO0DOkRjLbJBxuHo7cPhed/hQxzfqOOPutC3ct8s aneSxDHk0ym7agEFx3klc+WbZoaojtZ5anmL/+Il/ROW7Pxqa01y X-Gm-Gg: ASbGncsQPazDSRCBsmziuaiIXZsXxowO5Qxb5/YrTUgvKKJeCjCqY+jQRQjBcYmj21E iO7CdICO0RbEKBE2pvEUGBOdgZZM1JY29Ms1rWfZCGGTkQK5xYrUit/WZoNHDAzO+skvRwLpk1P UKQ2EbdhQ9T0itdeA07saichPmQB8lr5iJvBPDiWmZZtqE7l93jzPYRV+GNXVyGsRYYyLRibbSq lq3OVpX7mAmdAKNvWV4q2KHAz6EittNWhzDIZxyco/9uXAf0O+va8b/V38c1Tc5MpRRkdZoa+0G CqsUKIVpp1yzlravd5yuAJTnLGB4DqriLOYPO/QkopV1 X-Google-Smtp-Source: AGHT+IGafBiaW/uln7TkX4zY3MWfEYcRqgYKLFmeIj0TKcASe5B2sZisGvttx4VAmaNyMmn45QeO0g== X-Received: by 2002:a17:907:2d8e:b0:abf:6dc7:b53c with SMTP id a640c23a62f3a-abf6dc7b96amr788207366b.37.1741051233415; Mon, 03 Mar 2025 17:20:33 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf508f2288sm529199966b.2.2025.03.03.17.20.32 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:33 -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 1/7] lib/rbtree: enable userland test suite for rbtree related data structure Date: Tue, 4 Mar 2025 01:19:46 +0000 Message-Id: <20250304011952.29182-2-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: nwfumfp68m3zwip3s11zidj7jg4k17bn X-Rspamd-Queue-Id: EFD4040008 X-Rspam-User: X-HE-Tag: 1741051234-883724 X-HE-Meta: U2FsdGVkX1+vVTWubGdk4aErq/htlqoHjuyg9iJ1EuvMaKPKghxy9uOx+ODhSb7uMW9nl9g8EiP1gEfeeoFysGp7cfvwyg3FO1+B72rn6HKcS8HoSHB2WtUl6AIRqrZvzvTsQSX1Bu9Uh/93BBM6X4J+CHV1+l1xiA/Kal0KgSX3+GprXCC+sgrpKq5kk03wQbAkT/E/3nfBhsuMzyKjZ2rfAPXo96MmJHhokTQKGUhQy1J5YvEy9orBA9Gkw2h9mhwUwugzR5v1LoXm/S1gzRoafDcL6F1kZHjVtsCCcCYlsmq2vuC40yjZIVQhmTkNOy4MGrN0lOLGv3rNsCGMjFlEnd8RqcMiWlcDFFB8VNPjagiiZ29Rg2AbRWVE+ujt33uHZc2sHoJUWGUwfGR9YEKFI4R0HAigyzCJ7wNh3U3EKP3AjomqIA+Mu1oEWs6XC18nI5oJ9Upn73ISc2sj3FF4VnCx2bNewiowIbwvKAd5ghG4mP2O0m4T02H2r1jhlztNlUGez9sNjLcPxr3CQDr46lxxlwhqRX8PjtHub9dRQhSTD/htrHOmBFOLpsmhrbIuFqDRo5wklmvqpx7pPztH/hXOHOM1XzzHR26SVYrPNH3vhQTnCvY6HiRLnhDg4kLnyGqWmCCfuDedN9flYl/443qwbRg3uL20doooeQG91zlNxJ8eSuJ2vynvmvH64u3n4vOY59ysVzGoYBNSoMC+V6jPpdQRo15RmVOBcPUZM3ZCsdIaChd+zQo+fV08WoT/K8BPnCGy4Cunk5XYITgF0WPvcZwTYSOfDgZws+/qow9k+VIJ/eLFd7sRPLxZtDEEd4vg5TzZZ/2Gw+a1qFcmElBFiWqngoNnidO+Oame8jwkIxMhOVd42MXg3vCvSYC957GTOhpudyBRIs9tMYqU7irFdQa6HN21F+O3FpakZ2Y7Mic18rq16Hwdp/gDe9ILOi4atc/IyZi0Riu 5BI8syLP UNd9YGGe7fCw2SnKhEcOnvAT5VTm1ThCEFBgizywB+PUMN+Uq51zEj1h1GC/lohh00PklSk2+HW2e3odaHefgK3+Dguo/dH6rRNMH7LE3XDK0mPsx4qgpGqBdW0DdQc2RBYFU6Hx9K1cbpncL1sMk3+NnZ3aWA09L0qRNNvye9Mx3/9FHgZTRXaY+WcFAQ8sVEIhXTId8MJUT+ujET9JEErvZ0B3mQXMvqoXseY2PyBP7nY32UyceBkoWlh5rEq35nbSDxXtBKU/I/4KDP9rXi6zXa/pQzFEr8o8bMeMxIyC5LiRvrokIL0m3zObVe0uON7XQFZKy/LCp+CStwyaQtc3Zeye4pD0cR5kAddF7qEEdFIf6iVN44EfCiMydzMcAepaUGTuYW9E3QMlbF8YpezdzHQl6U6KDiEYUt3VVOJNPs8MTlT+wv2koKtpi13Hckjr/15zAhip1kswBNfGBx5YFoeTmRZphAU+KV3KGBnOJxqkz9HlI1SW3wJJyssU9fzobUEmlZTnQAKU9Ags2+7DQv8LGjEJYPWjDTC6EPrHYEfFw5GhOX0cEe22CTDrBzt1n+zciC5uglhREfs1sE27DbfQg8ze/S4nM 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: Currently we have some tests for rbtree related data structure, e.g. rbtree, augmented rbtree, interval tree, in lib/ as kernel module. To facilitate the test and debug for those fundamental data structure, this patch enable those tests in userland. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- tools/include/asm/timex.h | 13 +++++ tools/include/linux/container_of.h | 5 ++ tools/include/linux/math64.h | 5 ++ tools/include/linux/moduleparam.h | 7 +++ tools/include/linux/prandom.h | 51 ++++++++++++++++++ tools/include/linux/slab.h | 1 + tools/lib/slab.c | 16 ++++++ tools/testing/rbtree/Makefile | 31 +++++++++++ tools/testing/rbtree/interval_tree_test.c | 53 +++++++++++++++++++ tools/testing/rbtree/rbtree_test.c | 45 ++++++++++++++++ tools/testing/rbtree/test.h | 4 ++ tools/testing/shared/interval_tree-shim.c | 5 ++ tools/testing/shared/linux/interval_tree.h | 7 +++ .../shared/linux/interval_tree_generic.h | 2 + tools/testing/shared/linux/rbtree.h | 8 +++ tools/testing/shared/linux/rbtree_augmented.h | 7 +++ tools/testing/shared/linux/rbtree_types.h | 8 +++ tools/testing/shared/rbtree-shim.c | 6 +++ 18 files changed, 274 insertions(+) create mode 100644 tools/include/asm/timex.h create mode 100644 tools/include/linux/container_of.h create mode 100644 tools/include/linux/moduleparam.h create mode 100644 tools/include/linux/prandom.h create mode 100644 tools/testing/rbtree/Makefile create mode 100644 tools/testing/rbtree/interval_tree_test.c create mode 100644 tools/testing/rbtree/rbtree_test.c create mode 100644 tools/testing/rbtree/test.h create mode 100644 tools/testing/shared/interval_tree-shim.c create mode 100644 tools/testing/shared/linux/interval_tree.h create mode 100644 tools/testing/shared/linux/interval_tree_generic.h create mode 100644 tools/testing/shared/linux/rbtree.h create mode 100644 tools/testing/shared/linux/rbtree_augmented.h create mode 100644 tools/testing/shared/linux/rbtree_types.h create mode 100644 tools/testing/shared/rbtree-shim.c diff --git a/tools/include/asm/timex.h b/tools/include/asm/timex.h new file mode 100644 index 000000000000..5adfe3c6d326 --- /dev/null +++ b/tools/include/asm/timex.h @@ -0,0 +1,13 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __TOOLS_LINUX_ASM_TIMEX_H +#define __TOOLS_LINUX_ASM_TIMEX_H + +#include + +#define cycles_t clock_t + +static inline cycles_t get_cycles(void) +{ + return clock(); +} +#endif // __TOOLS_LINUX_ASM_TIMEX_H diff --git a/tools/include/linux/container_of.h b/tools/include/linux/container_of.h new file mode 100644 index 000000000000..9adce874bea9 --- /dev/null +++ b/tools/include/linux/container_of.h @@ -0,0 +1,5 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_CONTAINER_OF_H +#define _TOOLS_LINUX_CONTAINER_OF_H + +#endif /* _TOOLS_LINUX_CONTAINER_OF_H */ diff --git a/tools/include/linux/math64.h b/tools/include/linux/math64.h index 4ad45d5943dc..8a67d478bf19 100644 --- a/tools/include/linux/math64.h +++ b/tools/include/linux/math64.h @@ -72,4 +72,9 @@ static inline u64 mul_u64_u64_div64(u64 a, u64 b, u64 c) } #endif +static inline u64 div_u64(u64 dividend, u32 divisor) +{ + return dividend / divisor; +} + #endif /* _LINUX_MATH64_H */ diff --git a/tools/include/linux/moduleparam.h b/tools/include/linux/moduleparam.h new file mode 100644 index 000000000000..4c4d05bef0cb --- /dev/null +++ b/tools/include/linux/moduleparam.h @@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_MODULE_PARAMS_H +#define _TOOLS_LINUX_MODULE_PARAMS_H + +#define MODULE_PARM_DESC(parm, desc) + +#endif // _TOOLS_LINUX_MODULE_PARAMS_H diff --git a/tools/include/linux/prandom.h b/tools/include/linux/prandom.h new file mode 100644 index 000000000000..b745041ccd6a --- /dev/null +++ b/tools/include/linux/prandom.h @@ -0,0 +1,51 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __TOOLS_LINUX_PRANDOM_H +#define __TOOLS_LINUX_PRANDOM_H + +#include + +struct rnd_state { + __u32 s1, s2, s3, s4; +}; + +/* + * Handle minimum values for seeds + */ +static inline u32 __seed(u32 x, u32 m) +{ + return (x < m) ? x + m : x; +} + +/** + * prandom_seed_state - set seed for prandom_u32_state(). + * @state: pointer to state structure to receive the seed. + * @seed: arbitrary 64-bit value to use as a seed. + */ +static inline void prandom_seed_state(struct rnd_state *state, u64 seed) +{ + u32 i = ((seed >> 32) ^ (seed << 10) ^ seed) & 0xffffffffUL; + + state->s1 = __seed(i, 2U); + state->s2 = __seed(i, 8U); + state->s3 = __seed(i, 16U); + state->s4 = __seed(i, 128U); +} + +/** + * prandom_u32_state - seeded pseudo-random number generator. + * @state: pointer to state structure holding seeded state. + * + * This is used for pseudo-randomness with no outside seeding. + * For more random results, use get_random_u32(). + */ +static inline u32 prandom_u32_state(struct rnd_state *state) +{ +#define TAUSWORTHE(s, a, b, c, d) (((s & c) << d) ^ (((s << a) ^ s) >> b)) + state->s1 = TAUSWORTHE(state->s1, 6U, 13U, 4294967294U, 18U); + state->s2 = TAUSWORTHE(state->s2, 2U, 27U, 4294967288U, 2U); + state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U, 7U); + state->s4 = TAUSWORTHE(state->s4, 3U, 12U, 4294967168U, 13U); + + return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4); +} +#endif // __TOOLS_LINUX_PRANDOM_H diff --git a/tools/include/linux/slab.h b/tools/include/linux/slab.h index 51b25e9c4ec7..c87051e2b26f 100644 --- a/tools/include/linux/slab.h +++ b/tools/include/linux/slab.h @@ -12,6 +12,7 @@ void *kmalloc(size_t size, gfp_t gfp); void kfree(void *p); +void *kmalloc_array(size_t n, size_t size, gfp_t gfp); bool slab_is_available(void); diff --git a/tools/lib/slab.c b/tools/lib/slab.c index 959997fb0652..981a21404f32 100644 --- a/tools/lib/slab.c +++ b/tools/lib/slab.c @@ -36,3 +36,19 @@ void kfree(void *p) printf("Freeing %p to malloc\n", p); free(p); } + +void *kmalloc_array(size_t n, size_t size, gfp_t gfp) +{ + void *ret; + + if (!(gfp & __GFP_DIRECT_RECLAIM)) + return NULL; + + ret = calloc(n, size); + uatomic_inc(&kmalloc_nr_allocated); + if (kmalloc_verbose) + printf("Allocating %p from calloc\n", ret); + if (gfp & __GFP_ZERO) + memset(ret, 0, n * size); + return ret; +} diff --git a/tools/testing/rbtree/Makefile b/tools/testing/rbtree/Makefile new file mode 100644 index 000000000000..bac6931b499d --- /dev/null +++ b/tools/testing/rbtree/Makefile @@ -0,0 +1,31 @@ +# SPDX-License-Identifier: GPL-2.0 + +.PHONY: clean + +TARGETS = rbtree_test interval_tree_test +OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o +DEPS = ../../../include/linux/rbtree.h \ + ../../../include/linux/rbtree_types.h \ + ../../../include/linux/rbtree_augmented.h \ + ../../../include/linux/interval_tree.h \ + ../../../include/linux/interval_tree_generic.h \ + ../../../lib/rbtree.c \ + ../../../lib/interval_tree.c + +targets: $(TARGETS) + +include ../shared/shared.mk + +ifeq ($(DEBUG), 1) + CFLAGS += -g +endif + +$(TARGETS): $(OFILES) + +rbtree-shim.o: $(DEPS) +rbtree_test.o: ../../../lib/rbtree_test.c +interval_tree-shim.o: $(DEPS) +interval_tree_test.o: ../../../lib/interval_tree_test.c + +clean: + $(RM) $(TARGETS) *.o generated/* diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c new file mode 100644 index 000000000000..f1c41f5e28ba --- /dev/null +++ b/tools/testing/rbtree/interval_tree_test.c @@ -0,0 +1,53 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * interval_tree.c: Userspace Interval Tree test-suite + * Copyright (c) 2025 Wei Yang + */ +#include +#include +#include "shared.h" + +#include "../../../lib/interval_tree_test.c" + +int usage(void) +{ + fprintf(stderr, "Userland interval tree test cases\n"); + fprintf(stderr, " -n: Number of nodes in the interval tree\n"); + fprintf(stderr, " -p: Number of iterations modifying the tree\n"); + fprintf(stderr, " -q: Number of searches to the interval tree\n"); + fprintf(stderr, " -s: Number of iterations searching the tree\n"); + fprintf(stderr, " -a: Searches will iterate all nodes in the tree\n"); + fprintf(stderr, " -m: Largest value for the interval's endpoint\n"); + exit(-1); +} + +void interval_tree_tests(void) +{ + interval_tree_test_init(); + interval_tree_test_exit(); +} + +int main(int argc, char **argv) +{ + int opt; + + while ((opt = getopt(argc, argv, "n:p:q:s:am:")) != -1) { + if (opt == 'n') + nnodes = strtoul(optarg, NULL, 0); + else if (opt == 'p') + perf_loops = strtoul(optarg, NULL, 0); + else if (opt == 'q') + nsearches = strtoul(optarg, NULL, 0); + else if (opt == 's') + search_loops = strtoul(optarg, NULL, 0); + else if (opt == 'a') + search_all = true; + else if (opt == 'm') + max_endpoint = strtoul(optarg, NULL, 0); + else + usage(); + } + + interval_tree_tests(); + return 0; +} diff --git a/tools/testing/rbtree/rbtree_test.c b/tools/testing/rbtree/rbtree_test.c new file mode 100644 index 000000000000..c723e751b9a9 --- /dev/null +++ b/tools/testing/rbtree/rbtree_test.c @@ -0,0 +1,45 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * rbtree_test.c: Userspace Red Black Tree test-suite + * Copyright (c) 2025 Wei Yang + */ +#include +#include +#include +#include "shared.h" + +#include "../../../lib/rbtree_test.c" + +int usage(void) +{ + fprintf(stderr, "Userland rbtree test cases\n"); + fprintf(stderr, " -n: Number of nodes in the rb-tree\n"); + fprintf(stderr, " -p: Number of iterations modifying the rb-tree\n"); + fprintf(stderr, " -c: Number of iterations modifying and verifying the rb-tree\n"); + exit(-1); +} + +void rbtree_tests(void) +{ + rbtree_test_init(); + rbtree_test_exit(); +} + +int main(int argc, char **argv) +{ + int opt; + + while ((opt = getopt(argc, argv, "n:p:c:")) != -1) { + if (opt == 'n') + nnodes = strtoul(optarg, NULL, 0); + else if (opt == 'p') + perf_loops = strtoul(optarg, NULL, 0); + else if (opt == 'c') + check_loops = strtoul(optarg, NULL, 0); + else + usage(); + } + + rbtree_tests(); + return 0; +} diff --git a/tools/testing/rbtree/test.h b/tools/testing/rbtree/test.h new file mode 100644 index 000000000000..f1f1b545b55a --- /dev/null +++ b/tools/testing/rbtree/test.h @@ -0,0 +1,4 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +void rbtree_tests(void); +void interval_tree_tests(void); diff --git a/tools/testing/shared/interval_tree-shim.c b/tools/testing/shared/interval_tree-shim.c new file mode 100644 index 000000000000..122e74756571 --- /dev/null +++ b/tools/testing/shared/interval_tree-shim.c @@ -0,0 +1,5 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* Very simple shim around the interval tree. */ + +#include "../../../lib/interval_tree.c" diff --git a/tools/testing/shared/linux/interval_tree.h b/tools/testing/shared/linux/interval_tree.h new file mode 100644 index 000000000000..129faf9f1d0a --- /dev/null +++ b/tools/testing/shared/linux/interval_tree.h @@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_INTERVAL_TREE_H +#define _TEST_INTERVAL_TREE_H + +#include "../../../../include/linux/interval_tree.h" + +#endif /* _TEST_INTERVAL_TREE_H */ diff --git a/tools/testing/shared/linux/interval_tree_generic.h b/tools/testing/shared/linux/interval_tree_generic.h new file mode 100644 index 000000000000..34cd654bee61 --- /dev/null +++ b/tools/testing/shared/linux/interval_tree_generic.h @@ -0,0 +1,2 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#include "../../../../include/linux/interval_tree_generic.h" diff --git a/tools/testing/shared/linux/rbtree.h b/tools/testing/shared/linux/rbtree.h new file mode 100644 index 000000000000..d644bb7360bf --- /dev/null +++ b/tools/testing/shared/linux/rbtree.h @@ -0,0 +1,8 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_H +#define _TEST_RBTREE_H + +#include +#include "../../../../include/linux/rbtree.h" + +#endif /* _TEST_RBTREE_H */ diff --git a/tools/testing/shared/linux/rbtree_augmented.h b/tools/testing/shared/linux/rbtree_augmented.h new file mode 100644 index 000000000000..ad138fcf6652 --- /dev/null +++ b/tools/testing/shared/linux/rbtree_augmented.h @@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_AUGMENTED_H +#define _TEST_RBTREE_AUGMENTED_H + +#include "../../../../include/linux/rbtree_augmented.h" + +#endif /* _TEST_RBTREE_AUGMENTED_H */ diff --git a/tools/testing/shared/linux/rbtree_types.h b/tools/testing/shared/linux/rbtree_types.h new file mode 100644 index 000000000000..194194a5bf92 --- /dev/null +++ b/tools/testing/shared/linux/rbtree_types.h @@ -0,0 +1,8 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_TYPES_H +#define _TEST_RBTREE_TYPES_H + +#include "../../../../include/linux/rbtree_types.h" + +#endif /* _TEST_RBTREE_TYPES_H */ + diff --git a/tools/testing/shared/rbtree-shim.c b/tools/testing/shared/rbtree-shim.c new file mode 100644 index 000000000000..7692a993e5f1 --- /dev/null +++ b/tools/testing/shared/rbtree-shim.c @@ -0,0 +1,6 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* Very simple shim around the rbtree. */ + +#include "../../../lib/rbtree.c" + From patchwork Tue Mar 4 01:19:47 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999760 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 652F6C282D1 for ; Tue, 4 Mar 2025 01:20:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 48E6E280002; Mon, 3 Mar 2025 20:20:40 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 43E35280001; Mon, 3 Mar 2025 20:20:40 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E0A0280002; Mon, 3 Mar 2025 20:20:40 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 0F058280001 for ; Mon, 3 Mar 2025 20:20:40 -0500 (EST) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 7FBE4A4A4C for ; Tue, 4 Mar 2025 01:20:39 +0000 (UTC) X-FDA: 83182113798.10.75A6F79 Received: from mail-ed1-f48.google.com (mail-ed1-f48.google.com [209.85.208.48]) by imf13.hostedemail.com (Postfix) with ESMTP id 32A0620003 for ; Tue, 4 Mar 2025 01:20:36 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GsXPfPlm; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741051237; a=rsa-sha256; cv=none; b=Xykq4IoT0oOiNd9JPuUot88lZJLUKuFvBYWQ0W5q8Y0xMPx3s8Wok7LJqerR0ycFtqBPkf Pq/YQOqBEYMKPw0OjThdsAbPjJeN4yJaKDzGr2ldmOdKAnKmkKLrnOnb0Jo4Ng1FQc7Abu Nd2IIG9ITG4xYlfbA5h/ctG8mtSip58= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GsXPfPlm; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.48 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=1741051237; 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=bm4OptN4vaLvm8m6h9gJ+k3MbpCZ+m7z5hS8YgozQEw=; b=vhpegJGy6UU1jp8qk3QgIOHEIimVK7mLG3czeR9JJI2xG6WzSxXOkAZ61oBdjvNqSEskxH zTsrqK72xZJHnYRo8sQusVLUtBSEJcJ9guRHdZRW2eX8wufT34eVqBRRZY44gGBup2sY0n oROTSyR742mg2/5Nq+erCHc7pyaJXfA= Received: by mail-ed1-f48.google.com with SMTP id 4fb4d7f45d1cf-5e53b3fa7daso3046007a12.2 for ; Mon, 03 Mar 2025 17:20:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051236; x=1741656036; 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=bm4OptN4vaLvm8m6h9gJ+k3MbpCZ+m7z5hS8YgozQEw=; b=GsXPfPlmyCIQbMnjGHJ9DQ1YJPxUX4LYRmIUQhgVFFDLH30lfqQZhpBmpD372lyDp9 GsvaOpHskZ7rgcjsA7QZzDPKpR4F9MzAx0l+6mynknDIwuKWsWuN98PNiDccAeaptqmW 5THa6YJ+MlWTQ1t9YCU7DMbDTxFsX1K6zoBIu0dSIco5usnlKed8ldxMBjS7lJfbiQUS AeZRyezllG3HQ92NlTPLTOsrGWhv+8X68AJbxPU+ipDq/yX3M59QqRRobdZxJjB7SecG Y1kli/I3I6VBT7s7hjeKj86uMHNvHFK6itkqzv5aMz94bAfv+SyRLAcqREaK9BtfNyTc M1yA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051236; x=1741656036; 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=bm4OptN4vaLvm8m6h9gJ+k3MbpCZ+m7z5hS8YgozQEw=; b=e9uOq9sG2rtokVAR1044iNHSVRV5Vsx6UcquhveqmYjopnvxroFkv5MdzkDcgio5Vr H03ckEUljZDBGRlTwxRY6M/9DGUcBAWfnnBJNQAesYWBOyE1klE5NPIp7MncbTR5iurZ +NH8vILzfcckZV9RtrZLrckusmsnj/sUiraPqMga7uS7i4Pb2JNoCCi5IJFqnPjJe9zb boEDV/n3CTUB93VicyQSKd59ODNzaoF1vuGWS7kVb0q6kObO7A7Uvbh0QpSFRG5lCsfs 01AFLJXMiaAlSMDY6zIzQVVAs/CxiKYgsogXR2jvo6AMkFAYIHQOLbMf0+5EjTlAj9MP JaaQ== X-Forwarded-Encrypted: i=1; AJvYcCX75c4i8PgcO67gyz3yANU5PbYB+n+1ZnZ6hkH9AjCQVRYPqekTu8dSNEvq8wFlAyIkSvjmkDfD7w==@kvack.org X-Gm-Message-State: AOJu0Yx+puFP60QcIFpdWVdjZLcHwwQHRvBsf0AVZY4TjrX9hOJuzRV3 1j1TGWN6uefyzudOTMekGAb2xGeqwRzpT/uaTkUJbkCvf3sH0XmG X-Gm-Gg: ASbGncv7GSEkEIjdXQwz+158m9Luiq7S+vZ+Ravv9uvCXgqDM5/wMEkhlFZdBrwVe1z kPxLkpj5fgl2Lw54N2HbCiU1oEJ7LmFfnbOd52D8Q5AmScPOC98TpYv5Jj7PAP/83CCiARe+TYm lhRAF0IMnPeOXhF3Znlbd8SOG65xq7VMuEoOpKCaL0A61zlEwvfwNmIp2AbVHagFuNzEHE7HztJ QG0L9W4bnrv9P4OJG6xDSvzroHNMQ/Qd6v6FCfnlzBWJgxi3W59Ky5KB9GMx815LHv+Mp8K7uMG XE5Dke92dvh7YQ8mN+YAFcjeXk19rp6NNXZ9vZi+gjYR X-Google-Smtp-Source: AGHT+IEwZ9eOzbVIFKHq0uoYI5tILJ061IQXBKRedVHXC01BrDQcvUWiTgfDruhaaI8EMPkd+QHCWA== X-Received: by 2002:a17:907:7f12:b0:ab3:4c32:aa6c with SMTP id a640c23a62f3a-abf25fc618bmr1823299366b.20.1741051235579; Mon, 03 Mar 2025 17:20:35 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf0c7c0faasm891284666b.179.2025.03.03.17.20.33 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:34 -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 2/7] lib/rbtree: split tests Date: Tue, 4 Mar 2025 01:19:47 +0000 Message-Id: <20250304011952.29182-3-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-Queue-Id: 32A0620003 X-Stat-Signature: hnxqhktq4ymhp4paroywr34apsoon53h X-Rspam-User: X-Rspamd-Server: rspam05 X-HE-Tag: 1741051236-432738 X-HE-Meta: U2FsdGVkX18OHQB+zXbIz/RH3WVneSxZmDeNZVuC68wELvrp8Jk6pZJbcR0JKNQSdo32s6nIQct6yc24G7OHthTuy97QOToY5bwn3caQyb4oS0C2PQz7xJzZq17uZDaB4vg2Yo4gdjrV7sffY40g02DPlo0R0jHk0L2MqAZuRVtu/fn9D1/kXzp1PhiRGbdhuMkIr1dtoyiDPVx8aOO1vymQBavOYLELr8kMAA8dRlekYGTAkI6KJd455AHMo7AkhUV9ET0y6370R+08kR08qa4CTEcrnsnpiGQK8umDY5YGz/C0duv5Gv1jRk+xFZDWa4AkJPcNxfiG3YAYfyhxyIxztDN6EWMp5d0NQmvP0PfBwYVxSonNjz4Bt1cypDdflRBTR0xuL4XlDMv7DQ2h+wYmH8oF0uNpF8+Vsr0x6EzCtXvJh8vBssuaANs0maSYZxlHFiBf2zBMo1t7s5WMaRk98cQFuV+zwxaK2b8MA8tokuLe/bdJBKQUOQU+6F3oVPpW11jDniwI9PnAWtdMOBJjjpfDweqfPiHnGKTzvrd7Cxe5QxjqjgOGsqQBZdCGZ/GJViErxRzH/oL0dEDm47ycADcjTkVGVdg40ABNfyOp/x5/oUZE26hTVC4VwO1F3927rkWUGlDQvm+xlMH4+GtYEpSorfxVZgQ/x1k0YtzR5hRLsg+DajS0JYaqhTnlq/btdfBpSD64AKHVhswp3h7Dkux1BcbjYC8KupWnS+aw+C1gH+VhH4zekD1fpIT8TRTCS0D4OtjL5EWq3YCEpq8xb2I5gHca+afmWTluu7UZ/J5LMVz0kxJQZ1cCip1jNICCyoKBkInOK7ehv7qKGn838ZXy2hrhd2d/JS4/z6ic+EA0XKrFqllxPsfOyN31/fjS7v5FNwi1I0dom2FHAtHIlW+0gH0zrUWQVsGj5YUfYXC65loT91g3v5uSeGG+2JYSxe7CRlabCDBdiGG Vw54BHgb Km/O5elpR8Xv7MJO5oXITBBTkvTNi+Uk7dUBCjgftOMH+T2OwBeGiWkuInjUXakM4SETKAOD8HEKo3wImnd2H998ZObR5liXiduBbDxw6wN74hwSNRoqDbNuBdwAIVswCIQkcCoq0WPGwsG0n03ZwIb39odSjnME/Nb2dHH7dYAYQXBbiEdX3II1M8HAGtTWJr8OPtvqBKCCJhRHtLil/FTtYV+mZzRi7ULFKMdxIeNu3AZZhN0KRWe4QhOI964IofECre7JRFETboeoh5sV2jDH2zNj+vXK6F5hEuFgHs32LTy7MOE74Zh5wmrDwsB0wNqiueKb2FgpdGmo917Chv8E+x/OXZGwem/XMVh+LhJiy6+6tYhrlbM4r5Tgs8aDWA6oRD3Y8xYUVPiwYv0h7Z2fcheIF3UweCAsdq66M5iuvYZqyrUh6vxPBZxrZZ1M++W4dr5Y2S04CrvJpIptY25nTiMLZfgQ5xC8JPEPz7VLLwNzb3aCGhOm2JCLHX1C4uJ0kNPobOOvCZHBGo+mTacnwx3CRqXGB9KKbKRrFowJ17LrdEu3X28h/rnfHtzhMZLE47EeDb0snX0smG+cpF+Ww8Qc95vOfdEdW 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: Current tests are gathered in one big function. Split tests into its own function for better understanding and also it is a preparation for introducing new test cases. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 50 +++++++++++++++++++++++++++++----------- lib/rbtree_test.c | 29 ++++++++++++++++++----- 2 files changed, 59 insertions(+), 20 deletions(-) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 837064b83a6c..12880d772945 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -59,26 +59,13 @@ static void init(void) queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint; } -static int interval_tree_test_init(void) +static int basic_check(void) { int i, j; - unsigned long results; cycles_t time1, time2, time; - nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), - GFP_KERNEL); - if (!nodes) - return -ENOMEM; - - queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL); - if (!queries) { - kfree(nodes); - return -ENOMEM; - } - printk(KERN_ALERT "interval tree insert/remove"); - prandom_seed_state(&rnd, 3141592653589793238ULL); init(); time1 = get_cycles(); @@ -96,8 +83,19 @@ static int interval_tree_test_init(void) time = div_u64(time, perf_loops); printk(" -> %llu cycles\n", (unsigned long long)time); + return 0; +} + +static int search_check(void) +{ + int i, j; + unsigned long results; + cycles_t time1, time2, time; + printk(KERN_ALERT "interval tree search"); + init(); + for (j = 0; j < nnodes; j++) interval_tree_insert(nodes + j, &root); @@ -120,6 +118,30 @@ static int interval_tree_test_init(void) printk(" -> %llu cycles (%lu results)\n", (unsigned long long)time, results); + for (j = 0; j < nnodes; j++) + interval_tree_remove(nodes + j, &root); + + return 0; +} + +static int interval_tree_test_init(void) +{ + nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), + GFP_KERNEL); + if (!nodes) + return -ENOMEM; + + queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL); + if (!queries) { + kfree(nodes); + return -ENOMEM; + } + + prandom_seed_state(&rnd, 3141592653589793238ULL); + + basic_check(); + search_check(); + kfree(queries); kfree(nodes); diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 8655a76d29a1..b0e0b26506cb 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -239,19 +239,14 @@ static void check_augmented(int nr_nodes) } } -static int __init rbtree_test_init(void) +static int basic_check(void) { int i, j; cycles_t time1, time2, time; struct rb_node *node; - nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL); - if (!nodes) - return -ENOMEM; - printk(KERN_ALERT "rbtree testing"); - prandom_seed_state(&rnd, 3141592653589793238ULL); init(); time1 = get_cycles(); @@ -343,6 +338,14 @@ static int __init rbtree_test_init(void) check(0); } + return 0; +} + +static int augmented_check(void) +{ + int i, j; + cycles_t time1, time2, time; + printk(KERN_ALERT "augmented rbtree testing"); init(); @@ -390,6 +393,20 @@ static int __init rbtree_test_init(void) check_augmented(0); } + return 0; +} + +static int __init rbtree_test_init(void) +{ + nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL); + if (!nodes) + return -ENOMEM; + + prandom_seed_state(&rnd, 3141592653589793238ULL); + + basic_check(); + augmented_check(); + kfree(nodes); return -EAGAIN; /* Fail will directly unload the module */ From patchwork Tue Mar 4 01:19:48 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999761 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 105F0C282D1 for ; Tue, 4 Mar 2025 01:20:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id EA3DE280003; Mon, 3 Mar 2025 20:20:40 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id E553B280001; Mon, 3 Mar 2025 20:20:40 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CA54B280003; Mon, 3 Mar 2025 20:20:40 -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 A0AB7280001 for ; Mon, 3 Mar 2025 20:20:40 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 62504C1213 for ; Tue, 4 Mar 2025 01:20:40 +0000 (UTC) X-FDA: 83182113840.19.523FC24 Received: from mail-ej1-f51.google.com (mail-ej1-f51.google.com [209.85.218.51]) by imf01.hostedemail.com (Postfix) with ESMTP id 923964000F for ; Tue, 4 Mar 2025 01:20:38 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Bexk6xPQ; spf=pass (imf01.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.51 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=1741051238; 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=XdglvyptV1k6t/WS6GK2XareaYX2F5gnorivUDFtRoQ=; b=OSN9omvlzF8RRZLvNVVq9tPjG2yfqHbuJQjon02kZwJxClT21G6EQ9JzGnehMzApw9vPUj Zqzdj4STAVzmTZh05jmBSUrz//VKHJ0/+e+QLOMUko+54CNNXko7ZaylWZgnxb+lnP+5l/ 2I668Ruw2f9T2m7ExUmPGz7mCFnZtRs= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Bexk6xPQ; spf=pass (imf01.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.51 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=1741051238; a=rsa-sha256; cv=none; b=R7XO5H1GCTyfeeHpfMmPVrhZcmsjzJJ5NVDGNTxZcMFEWN0ry9fNwMqJaXmF32L8/hhPOt bFatUnolcOAqxv9Y2pSLQOskjDACXogZRD8pwuQU75IDSk9sOo12dQUGsLa+gxqoYMwjQf 5ZK3OojlWYwnuXtq5OjCOKGCMb9cDLs= Received: by mail-ej1-f51.google.com with SMTP id a640c23a62f3a-abf615d5f31so434166466b.2 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=1741051237; x=1741656037; 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=XdglvyptV1k6t/WS6GK2XareaYX2F5gnorivUDFtRoQ=; b=Bexk6xPQqkKmDeZydPeNmxJEvG0TQF4++rUE4dxyGzeQD3irQdMfF2aBVRR/uuqabs JTrMoLFJ8Hd08Bio5lq7lKISwJWrsRbGX+RuCb/LzCdFdqB007Puc+CPK0+aLAfCLQIj jJE3rnpHXzOB+nBQvkpgATKnQPgzSxw/Ogx9dHVDsqAUljlrDVup6lGevd4+3E1/ryz8 iCoIS2YubrNiMPiVlJumLIIFvVNGGeMpUx+q6deTfFmPkjcEk6c0hU5ByCaVFeUzrunr nQEN2RP7rKBHiXMARg6LVvrYtmZ18s9/A7vQ1Cehs8BqwYxxbV1c+Ly9oR4/CLIKN6Ws xBkw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051237; x=1741656037; 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=XdglvyptV1k6t/WS6GK2XareaYX2F5gnorivUDFtRoQ=; b=VroqIGlDXXb6+cjKykEFzSAvIY71PUUYh6NG9OkZZR4VCc454fhMdR742P4I2ylOp/ MnAifpGV8bRM1xW80WDscnxM0KysF/dWY/TwOtKAS8hDNprOxBkQKPmZ2G+nc1g1A5Rn FoQkfyIEL7BeY0/ZidQotR+zf578X8C4uovfmLI87tTcV2nS1AtWBCR/kjAvDqVH/twA QHV4LuMa0slv8g4yAar2aOeNX0sMFGStEy7AUPowPwxXx5Csrt/Z+JoF+btYr1nZgHoF YUJ5fd4WvZmuN5iwJcywnV5KaZMHZO77Pkzxo5ZAvNndlSLu9Ok9oERrBqnmRpLTumWx iykw== X-Forwarded-Encrypted: i=1; AJvYcCVfNm9ggnRRv8zcovlIxzA3HZ+RDJUfTpDpipH+PJzwbTL1ubuPwHKT2+9C8k22j2bmkOEFNdyfUg==@kvack.org X-Gm-Message-State: AOJu0YxLxJiU0fBN68aQBzRwx2P6bAOPvdFaSRWW2N0zMLbuirqdZxLe vrS4Q5Ue7GoCD+WOINsduMmDVMUPZA5xIoLG/VfdaEh8jpXKbFFO X-Gm-Gg: ASbGncuQevOJNYGZqCTnHHSNv0lJuKFuVgqeNNRETAgCEDLkc4PtcRL5puyBiVUSabb E72wa1ulvUklxjLspWRD6ESi+VXg9Ad3qmXtcfVgrihFkhZwfnz7alkR9X20lmXlp8WhclNIbkK GNXum/ecGdn8MIuqZ+HSNAQesYtIHvyeREdsdwHOlj9dBLPbN3GkdoE3/h/0VolU3fTfF4hmIpM MW5Ye8CPDVzVYgJ+QGmzEG1lJoVBehae/OFQKjCMu2zvya3Glb2TY4Vq2ozDh3JugiY4zE714QI CnKgdfQ5y4gixrNzH9Wl0m83N+q3CkALlxFiKAecRO30 X-Google-Smtp-Source: AGHT+IH2NpW5meHnGbwNvP5eh/J+X0KZM9C5y1Ye3CLruGmMCshcWiuOEDnH32BuOra5cvrWYI++rg== X-Received: by 2002:a17:907:3f1a:b0:ac1:dc0f:e03e with SMTP id a640c23a62f3a-ac1dc0fe441mr433024366b.13.1741051236938; Mon, 03 Mar 2025 17:20:36 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf76063ab8sm292159766b.73.2025.03.03.17.20.35 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:35 -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 3/7] lib/rbtree: add random seed Date: Tue, 4 Mar 2025 01:19:48 +0000 Message-Id: <20250304011952.29182-4-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: 923964000F X-Stat-Signature: xbefkqqdzqiekcry1ocdejypd6a8mbd7 X-HE-Tag: 1741051238-498137 X-HE-Meta: U2FsdGVkX1/ZvISzJK1l/N0EWvSE8vFJvG/ZdUf+a8PYke/pAh6iS+PPoyk6c167QKrVCdWe22JRcc3OtbOklANeTpi+u4aHhngIDSLs/71Cu2OtG8+MbXUmom8UGwPLl/2fNbRvjIC/qahYlNYw9QkR+0/YhKroDKvWgoUs9HxUEDw13YL+oCJW7UiY692DzanZBA82eDpwSfX77EZ8CDhjdGBm5xhWODIXbbqB59L38TB+UY0G3Ijl8x0Og4wrtn0ixdxDNC5zqE49toek4Z1tbv0gdRhTt5Hgh+YV6n2v0zeOCRCF3/t0SpcdqSkWQT+h7MIyFR7iPEX54+JS6TsUDOGUcNpwxrgH2NHryxqGKSAXvshQCXMAo2TpvMlAdO7cCcFikvJweE5X8/+qMvHry8VhznnLjZdN9P4hw4WzFceMGPaQtJ+IMVJbl6rWqlNKAyB8PtjJ6Kj9t9sGDDNxZC6SqI2Rq07YSCKmylUbmEidKZAX6lrQBd+5vz/7Cx6uKe3OJUgXSgQdaz2Faad7+rJAKuhzH3CylcQhCB4uN14+7BVVlSQ29MhNmbgx+C3ePpaFewDeOU6Bn96+wVukDnc+Z7h9UJORtsfmwE/rJQr4BwVwdXFH0+NqwrABwaj1vfu9dnkC/cvxGurxrygig/eChKKQ88uNHMpbGYxmdGITJTSc/x5UjarCmx8yS7lZAJchmvgCJTm69iTEcIOya70xhJqosP4Z7MQtbnSkUl2e4xDdjSPREUu/thC0+g9/OYnZl3VtRf8Kgodoa9K+vo9bwu2ZAEA0xoDi00wGDkg2jbZ1JZkLvQ5fH2ur6kYrrKAjcSI+28RLz3NJQJZ1ekfdM/gxaiHHoNhawvXCi/QgIefdnhzETBwODiBIQ3E8HanCvr31H2txWKYcvmIhm+Ja8FTQQOzdUzfVjHAbtFaCe5ZgJjtF0X9hDC0FMj5pXL8szK6LdLmNLnR GmnQ+vdE o2f9mkU9GmiIMdbJDS+xC7YVCC8JIVKOV3m4az4DuZHT+Q0cPCl+7C93qBEqlQ9JDM7hYnsV9kcEahwphle5z09HhGqXiviP0OJZG3SLVgqxpkW8oxOlojiRr427Jn+lPLXYDd+B/4JsrhD+P0NSgnmqxiWOVl/F2v9vCWrFU/5RhrvP6ucijQk8/FBFkOEIytQDSJv0FPZE2jcY2TxRKQLRmGLCNLf71rA0KYClbQ7HI3ScGrXt3ScAzsDHMgHVzUdJ6kzE0txnvzImfDnqiGK7iFcJEryFAhsdgO5z85z01wvbsozfZbNLe02GmKUC13hS9FzWJE5tkJ6x22UgWr7zTtJ4fBLjurbDRk9snAZvL251//ik+KwicNavjiteb6owtavyu2Wj0C9wdiI6hYVZxzY2z/c4pSaTW8QzuG7SGzM5rOVe2VtOLvAU/HN3PEJTFQRTJQFn5P14IcGFjDhD5B2BEnjycYabHFlJZcXiK+j1qOqggosbfqm4oI6spnB1xcUJGUVpPK0HeWbZpAHhjIOdmN7AECpC0tm6t2TFRI7MxpQmOO+ZVxaSK7RYjym2/Gsr+2D2r17aKaCNaxIzWVISn5h2xK8P8 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: Current test use pseudo rand function with fixed seed, which means the test data is the same pattern each time. Add random seed parameter to randomize the test. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 3 ++- lib/rbtree_test.c | 3 ++- tools/testing/rbtree/interval_tree_test.c | 5 ++++- tools/testing/rbtree/rbtree_test.c | 5 ++++- 4 files changed, 12 insertions(+), 4 deletions(-) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 12880d772945..51cbc50d4cc5 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -19,6 +19,7 @@ __param(int, search_loops, 1000, "Number of iterations searching the tree"); __param(bool, search_all, false, "Searches will iterate all nodes in the tree"); __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint"); +__param(ulong, seed, 3141592653589793238ULL, "Random seed"); static struct rb_root_cached root = RB_ROOT_CACHED; static struct interval_tree_node *nodes = NULL; @@ -137,7 +138,7 @@ static int interval_tree_test_init(void) return -ENOMEM; } - prandom_seed_state(&rnd, 3141592653589793238ULL); + prandom_seed_state(&rnd, seed); basic_check(); search_check(); diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index b0e0b26506cb..94ace8f0fbf8 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -14,6 +14,7 @@ __param(int, nnodes, 100, "Number of nodes in the rb-tree"); __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree"); __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree"); +__param(ulong, seed, 3141592653589793238ULL, "Random seed"); struct test_node { u32 key; @@ -402,7 +403,7 @@ static int __init rbtree_test_init(void) if (!nodes) return -ENOMEM; - prandom_seed_state(&rnd, 3141592653589793238ULL); + prandom_seed_state(&rnd, seed); basic_check(); augmented_check(); diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c index f1c41f5e28ba..63775b831c1c 100644 --- a/tools/testing/rbtree/interval_tree_test.c +++ b/tools/testing/rbtree/interval_tree_test.c @@ -18,6 +18,7 @@ int usage(void) fprintf(stderr, " -s: Number of iterations searching the tree\n"); fprintf(stderr, " -a: Searches will iterate all nodes in the tree\n"); fprintf(stderr, " -m: Largest value for the interval's endpoint\n"); + fprintf(stderr, " -r: Random seed\n"); exit(-1); } @@ -31,7 +32,7 @@ int main(int argc, char **argv) { int opt; - while ((opt = getopt(argc, argv, "n:p:q:s:am:")) != -1) { + while ((opt = getopt(argc, argv, "n:p:q:s:am:r:")) != -1) { if (opt == 'n') nnodes = strtoul(optarg, NULL, 0); else if (opt == 'p') @@ -44,6 +45,8 @@ int main(int argc, char **argv) search_all = true; else if (opt == 'm') max_endpoint = strtoul(optarg, NULL, 0); + else if (opt == 'r') + seed = strtoul(optarg, NULL, 0); else usage(); } diff --git a/tools/testing/rbtree/rbtree_test.c b/tools/testing/rbtree/rbtree_test.c index c723e751b9a9..585c970f679e 100644 --- a/tools/testing/rbtree/rbtree_test.c +++ b/tools/testing/rbtree/rbtree_test.c @@ -16,6 +16,7 @@ int usage(void) fprintf(stderr, " -n: Number of nodes in the rb-tree\n"); fprintf(stderr, " -p: Number of iterations modifying the rb-tree\n"); fprintf(stderr, " -c: Number of iterations modifying and verifying the rb-tree\n"); + fprintf(stderr, " -r: Random seed\n"); exit(-1); } @@ -29,13 +30,15 @@ int main(int argc, char **argv) { int opt; - while ((opt = getopt(argc, argv, "n:p:c:")) != -1) { + while ((opt = getopt(argc, argv, "n:p:c:r:")) != -1) { if (opt == 'n') nnodes = strtoul(optarg, NULL, 0); else if (opt == 'p') perf_loops = strtoul(optarg, NULL, 0); else if (opt == 'c') check_loops = strtoul(optarg, NULL, 0); + else if (opt == 'r') + seed = strtoul(optarg, NULL, 0); else usage(); } From patchwork Tue Mar 4 01:19:49 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999762 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); 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; } From patchwork Tue Mar 4 01:19:51 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999764 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 692CEC282D2 for ; Tue, 4 Mar 2025 01:20:52 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C30A3280007; Mon, 3 Mar 2025 20:20:45 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id BE2AF280006; Mon, 3 Mar 2025 20:20:45 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A80D6280007; Mon, 3 Mar 2025 20:20:45 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 85EA3280006 for ; Mon, 3 Mar 2025 20:20:45 -0500 (EST) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 2D14416127F for ; Tue, 4 Mar 2025 01:20:45 +0000 (UTC) X-FDA: 83182114050.18.C476EA2 Received: from mail-ed1-f49.google.com (mail-ed1-f49.google.com [209.85.208.49]) by imf17.hostedemail.com (Postfix) with ESMTP id 2127440012 for ; Tue, 4 Mar 2025 01:20:42 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=cuMSNs0+; spf=pass (imf17.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.49 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=1741051243; 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=QLyYd0jtlk1HnOzrX8doBxkNkczXZFYHZmixERUQcYo=; b=DfTeaLprScGjPcFFJMD2kPeRTaVOpBQ2Z2Bh3DwOH9vNz1Q2bGAoAgV+4v4ZfZYmDlQCg1 335cZyXZlttVyXQngcGiFjKHtQVZNy9P0PUABUWl/p3Bta9aZEqS+edkeYGMEMrt5Ohgop EZfFUhi0IHEzvVBqtv0qvqMeP2mTVfk= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=cuMSNs0+; spf=pass (imf17.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.49 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=1741051243; a=rsa-sha256; cv=none; b=K9OOAloX7yOcjlLSSvg1zn4aYMo+W4v8dSWovxrpBgRpH2ehuOf/4Psvhs0YvcKTmh2/p8 FcMhHnzWck78Qrb5zXyhm01Z+80lJ4TmtZLdIiHgfhAozEeOvtt4PEeyxXLjpMwtLj62T0 R4MFo8YeIPcQF8cUF2oNbeoohy1X4B8= Received: by mail-ed1-f49.google.com with SMTP id 4fb4d7f45d1cf-5e04064af07so9427137a12.0 for ; Mon, 03 Mar 2025 17:20:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051242; x=1741656042; 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=QLyYd0jtlk1HnOzrX8doBxkNkczXZFYHZmixERUQcYo=; b=cuMSNs0+xaFuxH02Gw5uMfzUB+wJt0PrIiqmauDrCPuEXfoK/lJwW7Ojx3lP0BV0zT 5O658W8Zr2YLw6q6XnfLC1nt+UYoWdmx9ZhvHKOzDPG4mSatn4j2lH0gTkB33o9tHVw4 /0FRaAx2ZnoWHoK5RVg1QTra5VmzsnAxc68Sgk0SKU6eeJhGGkkfWVopIOlKJwunBI9I gRCKZQaxccphCVoDKDa44WPIoJALzhcUOnfuUAW/ML2aCNQmcL5sjox9qtmP6OqS5p/h zLeCYeRf5jsbIJvLfDdnSlCb7P4zpWSVkywKQFBCqUsE6O4XSrGlzlE2X0n7MU8u4ahs 7TIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051242; x=1741656042; 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=QLyYd0jtlk1HnOzrX8doBxkNkczXZFYHZmixERUQcYo=; b=lvYkSUsXT8ooeQ/ScnKu4EVni8Zp44kTfm35PxYlVof8SlClnZNW2K+VdrS1o5vRC3 1U1GhWg8pm64G2ocFK6/6KPyFURzQHSIAAqIJ1LZelcOYWdv4Q6QP3R5cB34Mp/om/D/ enD58i4/HuqBAZOj1EGb8FcUyNRwPC9JEsnmCdd3G8Wz9iBe09M7DErFSO8pTZZJk0rm P+AOQucMkp+lPBdUNWV9YGEkeuZXsM2QRg49xYSS648LjesPsrm0mImx593BbvmNvGoo XgBrkaeTKdy/M7VinwNCQEEwcrqWB21YVIrDiMekmWAafPyf40gpBVDbOOpTTwdihXIx fJ0Q== X-Forwarded-Encrypted: i=1; AJvYcCX05uB/x4AeuLnykMF1pYL3P/WfiyQzKbfkELqnZFhPqezasSryoHTAtaDHpB8DFQcRJ/yxLOKxNQ==@kvack.org X-Gm-Message-State: AOJu0YyR2PC6YWbyLcYxwy05QLgN40RwEh0puWIbhx5QRnt5Ezr/TpQ4 VYURG/BqUYgIc01weHYDMimzN873mW3RpAZFpZ2YozOU5N7zF/60 X-Gm-Gg: ASbGncsj+8eGb6AIhzFwcxETgVE8t79TI7qx+PVSwRmCMFMCcyXzFq8gw4xWbYnvPsG I6vYgH1H0UwrHffWtHh0SkQGiQ+PerXmxTnF9508oF3GG5YYgyUtpWjwBrub2LcmQSI462ztBXP CR1TWLFWU5a1g4egcSGGUu7q19UhzFgb0h2K1W0YEUNb9pX5VFeH1Mvpb1knzoV0UEOJji5fkgl vV/zvdvGBY9gMwR6m7Z/5iUTuZf/WgFUxX9hLvcal8iklGOgwS8dm1wQ4Q+LuHsdRk1o2qvY393 pcybCWlTyawXjc4CPwJfmzEARO42hq0/l3zP6tBOsGrq X-Google-Smtp-Source: AGHT+IHfu97NcNusYw3g8BLyQrOgz+GVvwBiG5QdVj9J3HFWmQdVRVX4XUa31juJj9w1rszwc92wgQ== X-Received: by 2002:a05:6402:2114:b0:5e4:9a0e:38a3 with SMTP id 4fb4d7f45d1cf-5e4d6b18ec0mr16374441a12.17.1741051241398; Mon, 03 Mar 2025 17:20:41 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5e4c3b6ce0csm7604958a12.24.2025.03.03.17.20.39 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:40 -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 6/7] lib/interval_tree: skip the check before go to the right subtree Date: Tue, 4 Mar 2025 01:19:51 +0000 Message-Id: <20250304011952.29182-7-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-Queue-Id: 2127440012 X-Rspamd-Server: rspam09 X-Stat-Signature: o8c3tjasu8m5p44rna4faj86skmza4id X-HE-Tag: 1741051242-309073 X-HE-Meta: U2FsdGVkX19vJroRbMA2AlymDplcHrYjGQZvvLMS3L9M69eSdwy3exNgKEfqBkEr3x0h36SUiNrijfuJ+NS/bieQJ+Te+F5u2+WJSky11YDHPQK9ColxmOWFXIzA5UfdtL5YLZHeNKJ3aUjTskOqhTPfpViMioBdX3j/F0geOuEcHcC6zKd22nQ8h8iP6uYodr221oPNk9MfCxV2mQPvR1jLR8iM8gYeM7E0QrLye5A0u+ut+jufwvRhmjeJf69ILpAm8SsFdyq9uxJfUQiJVjxj8jrWGwmUnJcgIQ1dMYyfdZTsD7oq2y1/OWODNwFQvZ0awiLI6qMa5gzgK8czkPex1hUp6UX48wng5Nfc3oURHfV9Pbt0BiiMJuwhQF50ez1qNTZl8Os+blRf+1xyWpVHajTqdElxQLsYaCLEjbUHjkkYz6K6orXFaZwG7Qt2SNWDW7N6ws/xbBiDjXkAO4WYgxxx1L3VSf2Q8XRT48Jk9doCrGwCUcsJeHH1vyUrXJH3fUVJ5RJtl4vV2jNtTINb+/jD+8GHKSNNIizqcAL6Zm7ayZTM50WWG/cec+G1ceOGVHA/iAQVrfFe1ZzVoyQd2EBhvUpkOP9mIPI6boJaVU1kcj9GpLs4e33dr3qhQjFrP+TZFWL/CaI/jg1/0zr31hfe5jWmyPZXExdfyRjgmoew9Ues1HZSGpU8I16imHiKRuBagZ0Jsic7F2VfsCYmVkH+4yx4qJiTTOwItiwFO6JQjY6q8gWVx0kR1n9maJwAZY34YKNWu57pEGVih+TxqZCSVINRVjvs3w0iZ1l9DSXfIjy1aa1GT5+rf7MKmJdNnQNSuPU2FjtGaBO5C1Y/6pjDwU3zvJDKIgmeZVciYC1iZBKrRMWQa6W17bpsXeQLNyHW4fB3KAfVSAx7K50kV+qoRiZcY9wDdXHGlnb+7MFwbv4maZ5RW0hEs95XZqwjL2vSo6yxeWq7fip 9YUG7ZjV 94vMQNSV+XbemWHF6ACgFy5ogYWYkV4Ao012hFDlyHuJ2L6GoFlP49hD0CwXRJI8UGSf6ngnWYC7+B4IwG5cTDXXi2Prs6ujvZ7a+fVFKnZnom53L55TWmlCzJxQuwFAJkn3XZicO2OF44zG2V960hGXeElRWlqq+MXYaT4GmTLQSixbB24A3JOEI2r88yQC13G+2aJPmvpWAw7mFfa9l2IVn8HbAN8zCcNIWYDAp2xPUVTGlDfIMeKCYh2XxlNDaCD9NUMegxGjNejh/Jh+o6CfWQujVXITF9CNn6QBflq4CpYholGExlwy4QOEwkcE601AI+EqZvdaia9gnLA6OGUrOTaP9IJAXnC2xVtxNShBFaKa3Kke9CLm8FdM3fqHJ81qIJEXbzhqWZZaF3EQFQCAHMrl5iDOM1OiXNix0V4MgYZxyiE27io1pzziQEGOemm0MtDgVQSU9YOTQ2+jpyJ4vWnYZxNsvZFDxoIJxdhnvGBO8YhUW7ku3yWeog2HnBpbCvqmTbbuHcag5ff1nwL0WyiZ953THXyFgHBNzwpMdOJNH9nnfdzG2/fKJNDDWokfczxMVyXHmXQpTD4k7okUnsvjz6ot2HaC7i6FZQrbLJupFBW/d5RkcXi+dlkVx2FhyevdV8FJ/TZtpVy7p2Y+6Ljf9m5BabVBI/HAGuLfPn1o= 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: The interval_tree_subtree_search() holds the loop invariant: start <= node->ITSUBTREE Let's say we have a following tree: node / \ left right So we know node->ITSUBTREE is contributed by one of the following: * left->ITSUBTREE * ITLAST(node) * right->ITSUBTREE When we come to the right node, we are sure the first two don't contribute to node->ITSUBTREE and it must be the right node does the job. So skip the check before go to the right subtree. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- include/linux/interval_tree_generic.h | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-) diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h index aaa8a0767aa3..1b400f26f63d 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ if (ITSTART(node) <= last) { /* Cond1 */ \ if (start <= ITLAST(node)) /* Cond2 */ \ return node; /* node is leftmost match */ \ - if (node->ITRB.rb_right) { \ - node = rb_entry(node->ITRB.rb_right, \ - ITSTRUCT, ITRB); \ - if (start <= node->ITSUBTREE) \ - continue; \ - } \ + node = rb_entry(node->ITRB.rb_right, ITSTRUCT, ITRB); \ + continue; \ } \ return NULL; /* No match */ \ } \ From patchwork Tue Mar 4 01:19:52 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999765 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 5C54BC282D1 for ; Tue, 4 Mar 2025 01:20:55 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 57AE0280008; Mon, 3 Mar 2025 20:20:47 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 502A2280006; Mon, 3 Mar 2025 20:20:47 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3318E280008; Mon, 3 Mar 2025 20:20:47 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 0DFFC280006 for ; Mon, 3 Mar 2025 20:20:47 -0500 (EST) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 8EC74C120A for ; Tue, 4 Mar 2025 01:20:46 +0000 (UTC) X-FDA: 83182114092.01.968DA57 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) by imf29.hostedemail.com (Postfix) with ESMTP id 8A4C612000A for ; Tue, 4 Mar 2025 01:20:44 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=PzFh09rE; spf=pass (imf29.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 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=1741051244; 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=ATqc+DAUm+d+/s9GFa3o3jhhrYw2scideXwKT6/5kXo=; b=0DonHkfLY8g3uuUkTCBF2iWoRrbN1BJCODLyiGIlib9hgQx0huXNyGAvWnYX+DHTjXvZf3 a2AEnVF7DUxy22ZzbVJvMWQWIbYMETaii1Z+zLHSh/it+63vd/TWCrIDsW7MhN1Eugt7zm gI4rSk/yUfyaN/MU4MXjSDdju2SEGZc= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=PzFh09rE; spf=pass (imf29.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 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=1741051244; a=rsa-sha256; cv=none; b=WpvP/BkBJFoOPu6mBDwe2zcjPOOLE3hswidI0VGhzBAGooVCEbwk8cEkIa7+XgzAhSEATZ 2UohH+DRcK7OZaGUG2qTuBF90uju3XKopTpdFUOmYAA+4UYYhfHfxFFiJb9MMt/VPVRi2q wVWdkWgCaVjy0IhKALSuhinHG4C2OmI= Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-5e50de0b5easo3781427a12.3 for ; Mon, 03 Mar 2025 17:20:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051243; x=1741656043; 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=ATqc+DAUm+d+/s9GFa3o3jhhrYw2scideXwKT6/5kXo=; b=PzFh09rE+OmUOvMnRd0cdZhpNYaGSsPiuD8f8b/y9yzQsqc3if9xYDLw3TPGHLVaZm X1/tMuzSluQLaticbD00jHVWvkuVqS6NeqHvgTK3rXkqsWxCspjtwmOElNhi2a/M0Ik0 sgj/Zblwa4DLInQtXaKyxpAZocjqdnLS7c4VZqFGwvlD4tZE4Qr30rCwTm0vdLH/UYbJ xuE9ETJUZVmrt1m/HsoMbpF50IUdBozE8ZjOkKD8QS2lsjGdxmcnrLq+7Txpx8vgBY/Y qd0xx5+cA1exZi3mfNcE5pQLz+0jZEekClWTDF83SQBzOqJRy8zHG5FdTXqA0QzDGPlz 2I6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051243; x=1741656043; 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=ATqc+DAUm+d+/s9GFa3o3jhhrYw2scideXwKT6/5kXo=; b=Y7FaBQIliIBH6IjVdGklOwduYDHvTImRgOBEFSqHtvYnCeftljLvBFsfMbAdpxq1dv WZKTSEPVKW2Y4QueQNxmw5dBg7K6w9/73dieRD8//g3DNAZmnMUC78SqGUMnn1RyJ+FT 4FgIMlmIjcZQLy9tV24ZH4Y9hEWWD+f9lUrxcLsmbZYIeIpIN/WbK5eD4XqzzwdepLUS 9GvY8+9R3LO6zDrEc+0BUpRGSeoVHi+wqVTRrvJKoZxC8yEnDrKZB/2SpIHC2ZyCUUsq x9cx8Z9qQ3Yib6OXXS8fJauza1Z7Oc64Ne7iJ9L237rOdAljCRDJ1n6yvyEcz+UYMZPc aKEg== X-Forwarded-Encrypted: i=1; AJvYcCV/k6snOcO+GT7BdaPbr8ws8m8Ue9Cp5Pu9RwvDCduo61nDiBsv3MhEaD+8YEdqPb3g5mXCXEn+3w==@kvack.org X-Gm-Message-State: AOJu0YwmnXNAr84EizcOctcTqF/6E9/pJsTTlWWZ6RXkLXlKPfXhHGvp K4GpXS4qV7RGvZ89mhVbwnho20qgodCiXmwB0z3r8U7SzhdfYXUL X-Gm-Gg: ASbGncv5xUwO8+1BkBbuy0I4NSE6fC707ppIL3Koxl1mGV1DfyzgFBtBC246dzGIMU5 4Czg1wEuTd1qvMrgTb18eJwEeyC4ekP+49s6CjHQkpXpxRt93YPlIGMssuf2EQimQ38/HZaWbUx 1ZRhpRQkWWCluEn76WDv0cZJF21oCs+/zFPmfJ97vu5SHdKDJ937afN3eXVR2K6GWANujyfgVRU tDDDTS9MUcBUC3Dgf3Nppagl0YXibp/Tsnoa1YL8r27eWGfO4z2oJWIEApjLNXHn9vQfBlJwzoM xfmhAUE5BW1tsDN+pP1z0Bhg3kQil+DnaBNiQjitF2ZT X-Google-Smtp-Source: AGHT+IFSx4tTAX2ZNo/MD0KGk+9mggif5cFyor4J7uayXZIbClcnX1Z9srog7uMKoxzNgggtrbrgYw== X-Received: by 2002:a17:906:fd86:b0:ab7:8d23:1fef with SMTP id a640c23a62f3a-abf261fae62mr1975663566b.9.1741051242840; Mon, 03 Mar 2025 17:20:42 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf5e916ad1sm444672466b.75.2025.03.03.17.20.41 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:42 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang , Jason Gunthorpe Subject: [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap() Date: Tue, 4 Mar 2025 01:19:52 +0000 Message-Id: <20250304011952.29182-8-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: 8A4C612000A X-Stat-Signature: doena3oemo3s4k3spyhe558bqqdzxgij X-HE-Tag: 1741051244-364495 X-HE-Meta: U2FsdGVkX19Y2rTaUUpwlJEh2pjtewSjA0YZXWC5RZ3YatuCsWhyG4EXa+5iMbRWvt9tCH/98YgDgLsWts80ab4SQxyC7I1FGcyPrLXn3U/Ar+jocxLidsfKlw7HB7O2PmAfgfZA/sK8jl9V2qqOTbSgeDnkWMXPDnrpsVBaWZn0w9NyeKsd9e3O92sbOJlCBgErZyT6UUxVqe5CcnaFD3HyqftQQWTKnZiuMQ5qXED+dACuUuY7oQ/TJtg0eEkzpWC3Q3fnHY9//+lz/tWDKjDYvKrKA7S5leTpDCgINHLkY+2yXNJMmSlNyQyXbvlFWd+4VtVC5n8uFmYuUtCO4iU+MvFRyafjs2sUcetfcVJ1BqSWOc5YKNPJoNQOES1HgRS5S8QbnTyXCqwb/JGT0zLJ8N3/iiTsIDueVpX27er8RJvOcvZcRrKfCXjKsg44p5iMbBMgXIFJ220XbPFuDYOPFBHFrc5RIfPDH0EXIWFyaUwJaXHKUujInkcL4O4uQTT3u8KOUdd1qpT3IsRrZ4ibaaCrJKhxcpsn54ys87yN9cFEEq/bJFzH5Qbeyb5M14hXVpHcPn8AOKFmdI5HvD6obImizeHyuWNCbfDta+BG0Xh8Ngu9rJLNJpTXJkbF0RMpmD5tOfyCScZy+z2ngWOhCA4bz4YR3FAqTz1XFHHJGJrfZ2jA3AjS7KWZ631PhJHpOefeHDTZbFK9ryk4jsP4F6H7Ei2ueZcNswaXA+zXA/KrEwuJx1oB+4+Om2ulREX6zdkN86NH7tbZyqa+LVxN98PuENXGhOFX/hF9ilx+28FfPNMPq8YshL3Sa9aGr7HF4pQqztQjqDmQJMsKtk0siGOFbP9FNW/Y1C2vqb35CQZ+orEsTZxhr7GRKbPACVmJkbS8BJkTZc8gguWuUwZK1y2L+bXvNrQUBkKdkgflnSphSpkLTK9XYKADDPKGrMyLviTlXA1TUS++xDH FVKaExds +GOwUrXXbM/CnStAAWPPmx3cF+ignYolxsnbA/3wYxr9xPmWsjLhjoeEDknE62ld0OZSlo6u2qzD7ZqboyH9IwNEB30+5x/kG24tqwj/m9t+kqwpALOVz4VlvKsroON6uGBcRkrIf8IOYQUhX0hKMofE2Rgru7vRw+2xCnLSzqcA1jgqwz22V6Rmt9QN80M0OOMa6NySrxFIKYSRdvKu0PG2UQaUBhXwnY5LsLoipdG9PZyuCM6Eg1ZDKMNYo+EVESN31PARWAcO4hW4dENB/ZILNsDHlEFYSQlReCIYWw7pjhRu7EceJ/L5C+OVuj9duhFrN0AxuPpvoVGASuXV4VpekYzElQIoYmYK+bbzY1vYrxeuGcTd6bYc4qa2ILtAK2fG6IhJ1g31BV0ODxY3HEtx3Ix4MT9BcuCNYTAcEudzgjUt/jB+z/MrmYBP/npIteznvXk8fZ/esR6loUCUoYpaTJ6WHhaouzULDoNS0g0s//9njbw9ZEbo88fbWvP6OLYptwyfv66R9wdMryr7n4aKVe/I+kIWhLKEBsAyblG+MaeAUO8F728QvUZ6IvzwLFow3hMNLAgdgqPH3Dir+c8X/M+wurPowhrzPHUm3g38bSpq17AXYddZB7GrJhTdt6PpnY2PrYQL4gTjCW/EVFsT67DspUIavAArjpVB6Kib9q3G96Pk1vNAZGMGCfyQ7Y/HIMSvpzYQ7TFQ= 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: The comment of interval_tree_span_iter_next_gap() is not exact, nodes[1] is not always !NULL. There are threes cases here. If there is an interior hole, the statement is correct. If there is a tailing hole or the contiguous used range span to the end, nodes[1] is NULL. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse CC: Jason Gunthorpe --- lib/interval_tree.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) diff --git a/lib/interval_tree.c b/lib/interval_tree.c index 3412737ff365..87bcdd387d1a 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -20,9 +20,15 @@ EXPORT_SYMBOL_GPL(interval_tree_iter_next); /* * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous * span of nodes. This makes nodes[0]->last the end of that contiguous used span - * indexes that started at the original nodes[1]->start. nodes[1] is now the - * first node starting the next used span. A hole span is between nodes[0]->last - * and nodes[1]->start. nodes[1] must be !NULL. + * indexes that started at the original nodes[1]->start. + * + * If there is an interior hole, nodes[1] is now the first node starting the + * next used span. A hole span is between nodes[0]->last and nodes[1]->start. + * + * If there is a tailing hole, nodes[1] is now NULL. A hole span is between + * nodes[0]->last and last_index. + * + * If the contiguous used range span to last_index, nodes[1] is set to NULL. */ static void interval_tree_span_iter_next_gap(struct interval_tree_span_iter *state)