From patchwork Mon Mar 10 07:49:32 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009362 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 59591C282DE for ; Mon, 10 Mar 2025 07:49:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7946F280003; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 740FD280001; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5BBBA280003; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) 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 3A7CA280001 for ; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 9C955C0B89 for ; Mon, 10 Mar 2025 07:49:52 +0000 (UTC) X-FDA: 83204867424.20.4D03418 Received: from mail-ed1-f43.google.com (mail-ed1-f43.google.com [209.85.208.43]) by imf23.hostedemail.com (Postfix) with ESMTP id B9890140009 for ; Mon, 10 Mar 2025 07:49:50 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=OWCIwX8o; spf=pass (imf23.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.43 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=1741592990; 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=9W+xu8VqzPmTbsa68u6Ns3GVZLAVmpbi8PutkbHzKe4=; b=HmNwhpPrm62vdCreey1qbjv/I0nsO5W6BWbAmhGHcocieASOVmHewqgsEKMknQI+jw/u1d oaMKLSXsW3JWrt1V1QPhYMI1X/EV4vewXoXSCp33FVanj1tSeA3G93eBBvMU2mciADRmXp K3zsBllOtme86L8SiTfpIxcW8/OGI3Q= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=OWCIwX8o; spf=pass (imf23.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.43 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=1741592990; a=rsa-sha256; cv=none; b=fX66Tkp8z/qreSRV4smG8PYvXHU0BjHZKzqOCtNzrXBQ9jeM52f8lIMDrFTgeWC4NQdhEo bPiW4dH4IzPQvWzdAXBKZCbDusmANltH1H8pZO/P/L384YcXBnQLWcKCqqHeLh6KR/OXKM PVSSefuUt8ukD/u4vCqW7pPremsdEVo= Received: by mail-ed1-f43.google.com with SMTP id 4fb4d7f45d1cf-5e686d39ba2so1759659a12.2 for ; Mon, 10 Mar 2025 00:49:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592989; x=1742197789; 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=9W+xu8VqzPmTbsa68u6Ns3GVZLAVmpbi8PutkbHzKe4=; b=OWCIwX8onDtsC4v9EbkBDNxes8QxWyYPmpAwmAgH8dbq6Q41Veicbz8WnGcn1MNWxp yNAYhtOyk+ftaqLIKqrxZz8MwAU8UFSV+EBYnNDv0X5xaqP5WeV/Xofrv0mlJf7lFXIR 8P+sC5s77OPK0BWBL6IisHW9VhJHKxWpAhYAWRdyhYSEFkhaw40ZdshsnDqLBNEwB79H BO2y3TwiT7yQSttSrnd/V2PhskHFEjs/h4D1Cw3s+rayunO3RQPNj+i7DuPejpD6twQE VzCu5sscmmiVIfqdrKFJSlspuBa8l4I7haEKwmuxlupRv9KqLhXyNTwRHpdAaMDRJjCt WFQA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592989; x=1742197789; 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=9W+xu8VqzPmTbsa68u6Ns3GVZLAVmpbi8PutkbHzKe4=; b=wfJ11UYNsVv244X1XCvFBuLVFKI+DB7dY9FoIBB9m2035zu3sTWROtS6Y+3mVtzZU9 KYVlAlFUn9DcPpPDhkdwaF+tczmY2Pj4t4XGJfYTHpJ3SoCd11Jg2PrBmuU/g0KsXUw0 qJrL7gSs6dMK8rvuya7A/7LfTCFBxWYVOd24W10SuzOFRXRXgIfA0c3WBC3RGHiemcna aLWnxXjUgdiR7Rj63e4PCQKtzs6+ZvvlwW00iNowrLxPfJ5eq8u1sQ4QNDIzI2IRfLtx IESpcIPMFdKMpHw4ijK9Q3nX6gw4qLiMXbyJeLIjssGqlIWHe7ToAwNOrsK6hpWiAxsz SPRA== X-Forwarded-Encrypted: i=1; AJvYcCXx4suKDvW+9RM/Sn1Jwm7oLH4IkHdRY/xw2UhIXj+7LoCVVVeNnFHajZL7s1+sHYgXBABpyQeZrw==@kvack.org X-Gm-Message-State: AOJu0Yz6oENMzN8poVXLMOV1CUAo6m+TZosORtIogS2BqBunhjuoVYWq /5O5R8T2kMlI9ny1CGAXQJFqj6CPLlGu+eTb0X4XAZnFj65AgPJZh+2v+SFd X-Gm-Gg: ASbGncslQDgpcJIsfq3ce8Sm55WI5B6Sk0J3xsuACzmcRx4goOC6qEST/u5ZF5Q4mlh 0wPOA8Qc0RY3UtRmanXKEG2WKT6sMDRJOQHpN5TO9XSHUYpVwvg95sPxtehUdc2pLsu7wbm0+bJ k+gRKy4T7gMJwRvKA52PVkUHGNLiwCYvhYTH0EcGX0Yy1fdniPpLmM6HKk9fFC0OTRsiKg1ds4H XrCXTtbsZgHb2QtaxD0Pi6nBF8d/tjYqvTHz+7OP8D4LJA1dB2QqCb1sR4pakbB9+s6FpRhzo5W BZFmGEItGRisARJrQUBMMsNgZDxZihQfibS7XVtK1Vj6 X-Google-Smtp-Source: AGHT+IFN++XdhwKw/A7WxYw8gLORuO3rtdMW1XCsOiinOtBqOBKhOrF5XR0PZOLgysSgSAXw4f9Zbw== X-Received: by 2002:a17:906:240c:b0:ac2:6a7c:142e with SMTP id a640c23a62f3a-ac26a7c2295mr789924866b.44.1741592988573; Mon, 10 Mar 2025 00:49:48 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac2a3c775absm108608366b.184.2025.03.10.00.49.48 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:48 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 1/7] lib/rbtree: enable userland test suite for rbtree related data structure Date: Mon, 10 Mar 2025 07:49:32 +0000 Message-Id: <20250310074938.26756-2-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Queue-Id: B9890140009 X-Rspamd-Server: rspam03 X-Stat-Signature: 3dsirwhwwkgoib4tx935e4p9w3fat5ix X-HE-Tag: 1741592990-90416 X-HE-Meta: U2FsdGVkX18k99hCwMQy8mZu5nnLZfUpurOYvfolB5S1WYdx+dzhqmfwJo+12V2Dy4PBFwVMnPvZs94Xr1HLxFqCeqz4kVa/BAX5FGk1DkDMCTdikCOQtmmbwrAR9YO0+Xl4x509ACsyix5Epy1nENDIkoCmLXuhxEg2AWYVpzasLMNgt/eoC1ljY3mBWjamKX1IsqIgoa0e7pYAGPfycZECnjf7aY2LD9v+Bw6uh24PoDDVZ8IF0KGHqrK0Zm2R97+8M3nHJzMBfUJBXjJFPN3on91S9fKj74yyWR/RuZycalIXsPaiIM8AaBi0UjiRQ2Y6kvuj3Wn1d3LiM62DLurrGCTlr3v7zF019UO0x0hfLgVnIZwk68cS5HA9bYUmFGcgUgInvGkq/rEPIT78sDX6e4li3kGHvFJdsX6GN8bTxeQIuFBS3o1bM/Onp6L+NQgMbPiJWBP725wPEhb/h1UCG5U0ng2+FwhdWW3eucnc1jGl12LTZR759f9GaTSDj4xrNsDB3pP+57IT/v/Av/igtnpUidS3RoTzYeE/OmOY9esug3MDBNj4xmUTwP2dk4GstlAh8wjuMWeRtqptZEYQjYPggebowlR/V+n9zpOqufpaB5BOAO/xnWqV7lxK9RnOzVx+2rcsslwxOYLPugW/biFSZfzDsmpGNTbKYnm+9DZEFTzgyVoTbyRjp+BcW3IwmkU9m770dVUJNyH+C0PLE0CR2ZchjvK1EC6ooqUk9Q39zpqxlHzzTcK3fkIL0L9KwlaQtlXyZdOjw80VfzmN3IsrmYZALHrdrM6zc2algj/S3Y+M7DiuAPQCexQ+Gqpu6VogHa/DkIWHugCvwv6nEvdNd2wcyOtYg7DE60dqkJ+xn6bpr7UR/TRuXiZMXaQ3XGsVN3HW9bJATtxKenFemYomQSQLc/ZlAI2z3K1NPVhSEwdiIHOroZCXTuo8t+N7DGyBcOQe3iFVuYf nrVlA8cp hMDnI7PRh1rORckGLFmRiDht4LwDNWlHg+2ZucoPVnDXrWtupg8Es0l5yas3Ne2k3iObHEZvi4gMjJNOl1F6wWHyuh+Df4aTTlyTLDmnr7WVJzA300WX1kSfH0vJtPo/i7Ngll84wGB8FfGeoRFMCAbHa2VSoMo5o6xtA1eDmNcjhq5gw2yZJWKCZQmJHQYFxqNxqwFq84lcnNLxqqDWYxOx/ybQ2dFJtWyc447eRjcR2B/EaUTBkHGXTp3vtswTFeIfhIq1W6BBzeXOCdxyD66wCOWSAqyvlLIYlGl0PKn3itvt8CHyBBvRDgUQo7+lUddb+OXbJ7UZWr/agQqGhEd2IFrdnzTcHezk8z2TtrfyYFBk17QGR/A+fQ7pmCsFJIwTPXTpT8FWxlbRgzQ0/+oZ0BWYZvv44c1vSWVzp7L0fWk+ox2onO5W1xMlo04ntRBA9vvZYp54ObAMcpooJWq+s6ZC3DrqpQX4wjzoayFCT4dADwN9Qc9T8AjYMqcM3UIB3zY/eJbLiQKCxbRGrySfSRKAmwq9JEHOY0CvLw0iRAYkguH4pTfhLUXFMfxtOuZaymkEZp7xQXq5rfkvKwqvDWWeaPg0noIEC 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 --- v2: move container_of into container_of.h --- tools/include/asm/timex.h | 13 +++++ tools/include/linux/container_of.h | 18 +++++++ tools/include/linux/kernel.h | 14 +---- 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 +++ 19 files changed, 288 insertions(+), 13 deletions(-) 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..c879e14c3dd6 --- /dev/null +++ b/tools/include/linux/container_of.h @@ -0,0 +1,18 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_CONTAINER_OF_H +#define _TOOLS_LINUX_CONTAINER_OF_H + +#ifndef container_of +/** + * container_of - cast a member of a structure out to the containing structure + * @ptr: the pointer to the member. + * @type: the type of the container struct this is embedded in. + * @member: the name of the member within the struct. + * + */ +#define container_of(ptr, type, member) ({ \ + const typeof(((type *)0)->member) * __mptr = (ptr); \ + (type *)((char *)__mptr - offsetof(type, member)); }) +#endif + +#endif /* _TOOLS_LINUX_CONTAINER_OF_H */ diff --git a/tools/include/linux/kernel.h b/tools/include/linux/kernel.h index 07cfad817d53..c8c18d3908a9 100644 --- a/tools/include/linux/kernel.h +++ b/tools/include/linux/kernel.h @@ -11,6 +11,7 @@ #include #include #include +#include #ifndef UINT_MAX #define UINT_MAX (~0U) @@ -25,19 +26,6 @@ #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #endif -#ifndef container_of -/** - * container_of - cast a member of a structure out to the containing structure - * @ptr: the pointer to the member. - * @type: the type of the container struct this is embedded in. - * @member: the name of the member within the struct. - * - */ -#define container_of(ptr, type, member) ({ \ - const typeof(((type *)0)->member) * __mptr = (ptr); \ - (type *)((char *)__mptr - offsetof(type, member)); }) -#endif - #ifndef max #define max(x, y) ({ \ typeof(x) _max1 = (x); \ 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 Mon Mar 10 07:49:33 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009363 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 0A570C28B2E for ; Mon, 10 Mar 2025 07:49:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D82D1280001; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D0BE0280004; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BABC5280001; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) 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 9AA93280004 for ; Mon, 10 Mar 2025 03:49:51 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id EADF31A0BC7 for ; Mon, 10 Mar 2025 07:49:52 +0000 (UTC) X-FDA: 83204867424.06.7A37A58 Received: from mail-ej1-f42.google.com (mail-ej1-f42.google.com [209.85.218.42]) by imf06.hostedemail.com (Postfix) with ESMTP id 064C9180007 for ; Mon, 10 Mar 2025 07:49:50 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=PUZlwJ+E; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.42 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=1741592991; 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=gk/TY0u38iFZ68Q9lPKXBywG+sJUsPSYcwzIuaMOmRCF4pgmuVRaOcWgPjPrIl2iNXmbHU 8JTa+l2dKbPH8DhTenBHU9+rVuEBHmCeWs3F2T+mH8CVENys/sUmfXvdXpuLixIvhvnFVz RGgypaKwQ8zHdOH88LRqsFGxCbqjiQ4= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592991; a=rsa-sha256; cv=none; b=WYTZ/hMqG2tMpHN90HJimDEJ20wRQAnMtAtOIyhOzaDtykOkebH1HDHytsKN0aHBjcTNMI SvEgpKJ6cjKXsZtfS8xhSXkPS9suXURjK++jZBRAda3RXRwImfWdUOQvuw7/co2chIvbyg FUNDKgQTYKD5u6j3GDAXWvPFw3a2anQ= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=PUZlwJ+E; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.42 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com Received: by mail-ej1-f42.google.com with SMTP id a640c23a62f3a-ac25520a289so455182666b.3 for ; Mon, 10 Mar 2025 00:49:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592989; x=1742197789; 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=PUZlwJ+Ek3nHX4GJTzpODIoKqgMNFmA7jZxv4ysgew/8J5CWU3aDSokpSNZ1vY2Lmt LuQIG/32i+VhjANa2kp9trMgvDDelGwuwtYaOKwyAuDF7KpYb3oCVfjkEAxOwHkgCYme zvy4k3NxfZ74LoMs/AnxFVcURdDecq8vCM/SH4JfmABlCj8IW0KMb4RG7gX4NfcErVsS DLMQp/9irpKFO8oNRaRHh2Ri6TD3snwWC2wngEBgDH7legoDKfdIZmwXafwfgnt1Mx9i FTO7bDf7pAtTiW8nj3a1OGm+ghMfUZc3L/TfgdFsoGsO6+nbXANQbQ1hwV7wspg29hDI IZ8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592989; x=1742197789; 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=l+TjPW1TY/NJ5oGCYZGj5eNtQDcYOeFenc58z8apB5My5ns7TGS8EfKCLtjE7QwbhY xs/hGJs9thyHeO7ONLxZv54xwWk3/0RdSe0fm5l7BVD00MsouDnFAdPXGHAQGAEGE5U/ Tt2qz8VcuwvKCoH78/i4st+W4zC1F5Ka8O9+7Ed5c/PD553wP6ldYpxGt84C8NGR1BBL N9b9OYKRvBMxcDd/TN8ZrS3+NaDQeYaeVqMnWmPXzl9R8+wSJaj2poiyGaCFPNYtMoip eGTcHTjGicp5is6ztQrVfRDyllVBCInB5byt+7rTQ9DElR5lEjLQaWX/VpR3yGj/GyE9 rVYQ== X-Forwarded-Encrypted: i=1; AJvYcCXtEhqPCx62xD5381MQAqpt4va/0Xr/vUFRdJtUWlCZvv/ENFE0spzBezL2n09sl5rgOkSIeHmi6w==@kvack.org X-Gm-Message-State: AOJu0Yz1HhxSdzpXv2vbE90wig12TJQCCnvdjTFTCRiWIBW8S9FM6XgS LI/t76wo3xwrPsDLGGCwrozFQr8TmfTtjCFPnFFMN2jkuZ49Fx0f X-Gm-Gg: ASbGncv7V5WiC5scNoP7uOlbq8HaqYfFblYHPl8Yw4thHCFMkIePseO1rx398WNW2Nk A2KWYJTIl8sIRRUWwuf/JLehKXi1+VPz8NjtVcscka+YUy/jwu17Yn1ifJTzsu3ef82X8bBbaOz XiYwJ/gSiuuQmhjMOR9D+ftH71QpMeiy8DTSMCyqn6BimQ5Bhgwbx6PMtSt7zPE2kXPZXfdZKJl Z0vGaCZzEScypAZ6iinwlD/7cmVoLWrVycIO69vqHt502yz3y7A26DRXtZMuYmtUCQdq98OJGSn fH658TylRJsopaJdHNluEiASfxVdzHRpJnqfGBVC993v X-Google-Smtp-Source: AGHT+IHJam5Pq/yFn/yWdif1/Nrk7QNJF900leJluyerxJchZF7XgJgUQ/5odygu/aMRsMKreURwWg== X-Received: by 2002:a17:907:2d2b:b0:ac2:b086:88ec with SMTP id a640c23a62f3a-ac2b0868a7bmr30936666b.5.1741592989408; Mon, 10 Mar 2025 00:49:49 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac239517802sm714186266b.86.2025.03.10.00.49.48 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:49 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 2/7] lib/rbtree: split tests Date: Mon, 10 Mar 2025 07:49:33 +0000 Message-Id: <20250310074938.26756-3-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Stat-Signature: 7wqqzctufn5q74x8sh8peqnntws8uw5i X-Rspamd-Server: rspam05 X-Rspam-User: X-Rspamd-Queue-Id: 064C9180007 X-HE-Tag: 1741592990-839291 X-HE-Meta: U2FsdGVkX1+5CcgI1q0i+cXHWVr2+w1d3xzGCw3iGnlyAcl3f5j2yzMPQw95lvVLZg0mhfRDu8+9BVq/aZyNWqaar2s3eLSN9224Qlg7b7JH0SG2PiLyw4Elg+xOnN7uzasAPzqpfo73/77v4P71DVRPPqRm78E4unaoojTJ1+MJURTHcWIFkDtrFkko1WDn8NGceYjWoPWBp6TgepAS/d55cvZCYge7q+6OTtm+7urMT4IMQzbYLGmHlY8ziViE0eGpnmD3/kIVCh8MHPYSgq/hxp0f7gnzSSjyg0hnR9F++mygdED7X40KtTTb+shEIwIzCi+rpGH/WQhgek3WYpHtFxIPb5Ap+C+S7bvoskuY8c897CIUuymIvA67n/XVivU1TWs+ldrwT8q8wcZt0sN4tzHrHX7Bfg+ZVQ5pnC22jmKPQsKgEhHmiqwKMPN6QFqeRLwLYLB4fNrH6j6n+yl4qbfcezibx410NwaJhn82ZFVza2EVRkuQshGFv7J2BUX0+n6RbgNMc0NYtkkukBq7iNCBRuKMs13BDWSME6u9dLDMC5tnWW1Bjj84yBPkMy0b+Cf6skbz2zDMDcDdpkZ0g5q7oqtBsMrZYYJT5AANFyJGriyujAprij1v5+6t2Jf0LmAbZG9QpLjfuEiLi2IH68Gwfxk+mD1Naf3OZYLo4JdnJX/hWtvYz84oGurPka+epp/Ya2VgTll6X0DIWFrtimBsZT6zEIJkL1w0poacqTuN94wp/mVzC0f8jH9m1cKiVfngX5z1d8A7ZX+ToqlCKzeSkf/Qv5f9BT4y2j5opq8xhM6k8PjNKsgHGih+4WPZUyz4t3y2w0IHGx3KEX/6q4lkFXruKz6Lv/Z2qVKiODBudxZIMBL0yDplZfMGjZo+7UXjnMytNbv8JEogasVVpiIrOXs+9/5zBh6aioZXpNZSpk9crGHr1YhIqYszDO3viR/VxFhJHRd6Gh6 +oMxzgGj hpiu1pUZIOuFp0P2h9fDRT5jLLII8i97R3feWMgKEPacbhGWHz/a4jyeZFCAfuOie5WW+dWb9dh3iWFkVVCQ3mmFKW3v7XUEdPwADFKRgm5ApQUSRloYiG76NfqSQp2oSOxMLVHn6SoRpqaUPjeXy1K2PuWV4cYUVoTca7m8ioDCMH4368KPbd06TCINXN1vZBw0Ry/TXMI9zjCQG6w99Fmn6TeOjIGT6oY2uS4ue6tx8T4MJ6BzWJloZ2p6pFsvmGYxbbq4PwNu5mM1r9+dEBWEqnz9lQ2tOOO6WmDJhLnxQWEFZkvzNjQrmMKOx0Vy+LwOttOlIYbLEVvVK7cbmIiIotrSZM4rF+kOq2z11vhW4mCZurLocBCzvHHg/Vud5ltEmrFPdRI85YPHhPo9pCYLyd3umwQ4PQ/bDLViPiKVxulLZ7eIfaotsfeufOQiPv9f8GJt61gG+Yaab6KD3x/2Vev040XM0VC47rdGd1xgvDHq1MxTbjoWZszbCni1+LZvfrfKiybsPWFlzZHUNfFfPNXZ6XkuOs579pr+8+eQKO8DrzOMdwGNzjc9VHzfhUwPmDQzWsjCu+b5P2Q4BuDd3x2ltZTKs1eoU 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 Mon Mar 10 07:49:34 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009364 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 9FDEBC282DE for ; Mon, 10 Mar 2025 07:49:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A4793280005; Mon, 10 Mar 2025 03:49:52 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 9D0DE280004; Mon, 10 Mar 2025 03:49:52 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 87206280005; Mon, 10 Mar 2025 03:49:52 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 6C0B9280004 for ; Mon, 10 Mar 2025 03:49:52 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id EBB32B7758 for ; Mon, 10 Mar 2025 07:49:53 +0000 (UTC) X-FDA: 83204867466.20.503380D Received: from mail-ed1-f51.google.com (mail-ed1-f51.google.com [209.85.208.51]) by imf03.hostedemail.com (Postfix) with ESMTP id 0FF0120004 for ; Mon, 10 Mar 2025 07:49:51 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=ajufT8mM; spf=pass (imf03.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.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=1741592992; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=ZOM7SWXrVUOZbxXSv5zw92HxqGduUeTf1wpYowNIKoY=; b=RcBvjTMM6wkgBAZFh1nVWzhM48XBrrZN6PguOng9x559jBpptqyf56ip087x0AQABhsV7w XC5bYI9yroNyZELpY7tJcTWuNhvstn19J7BcUBlb20HqCuncnwpvhYFm3w54IjHwR7lWo9 t+wGGwx9zGf49XYLYn0q4gzpxiSFNUI= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=ajufT8mM; spf=pass (imf03.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.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=1741592992; a=rsa-sha256; cv=none; b=dLCjpLDSw4rP4U6IwjgahLBlaj5uxuHrQNGKhgtymo7rTgRd5yc1DDYhey22BcOcbn04dZ I2oXn3j6jA5nVJLuwNXHfZw1z+ujiU+aYKi3X2NPxUKIym2yPRMPYLiA2RreuOy1ghRsRJ yoaENjo2mu0d794CClpFv4uTBp2vuZw= Received: by mail-ed1-f51.google.com with SMTP id 4fb4d7f45d1cf-5e61da95244so2510192a12.2 for ; Mon, 10 Mar 2025 00:49:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592991; x=1742197791; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=ZOM7SWXrVUOZbxXSv5zw92HxqGduUeTf1wpYowNIKoY=; b=ajufT8mMhYK0Dl11mfm5S2EJ86C98/OVaLif/OCaLULyjLet8l/lHl8ZCDh8l5367n 0Lb1g8WnZ8mrixY5cFJPpMgqzpK3yjhtlwPBwvR2EyadKcgmD3Hk8A113hPR2IHJSRMt gRO4oRQnoTrQKLpyLicJRzhLsPyZG8/RQmACNao2ckQqr1dJ+Z9znmrxGRyJKUWyDJBr X9rRSyFes+FTAKqMOPl5rU+qmAIywq/KKTQZCGLdXPvaSHOsLnfSQVMaPCHGHAGtuZws WQ9kap5m9ca6ciaqg0Qu8ete6rIP0lTDfqgM6KCZSvjNSRtzdFmY0KdfLEsRuUNPIUp8 86Nw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592991; x=1742197791; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=ZOM7SWXrVUOZbxXSv5zw92HxqGduUeTf1wpYowNIKoY=; b=v59z3yODkuCqHQoYXImsglWGLh+/S5euWOA0bXhHSLiqjDu0Vy/9WjbCN2W7i2pnwj lzIn9Xtj8FHZSdduPyZoj8O4i/uCgVWQKhdQkYFdjKqine73JxHH8lYYqkb/Ni2pgjCs xi19547WRoOzPlYkDc6bBL5Y6Idq3uibNkzofXcoC4Y5xE5ekhK+OHbu47XLPTB7FMLy tDlmIdZZ1PUzXIAnhA1RoHK1ZFDvPJNPWVdNNJWJmn9PUoSUJKrPAGwDza/ZPMAtjKg6 a+C3iNaH2cILZ8px+KF1pgC+7s/Jh4XUNeuMkZ8OSv6ypHDh/5tL/4UqlFois1h5hcYW qpnw== X-Forwarded-Encrypted: i=1; AJvYcCU90hen67sZRUvdgy9jeZAcSazMCrNWCCXqKmIzFnbZDp0+s82YDj2GAGl3BNOetTQmjwHXzc8dYw==@kvack.org X-Gm-Message-State: AOJu0Yxry86qGoLIlVblvlp1sQNRG4jfKr7d7xcvTxvtdOwgA9UmOUfc 6lfTB+7UNMEmBD9lbbrm3RXm/glmZWaxjBJFCArdy5kHQMOMk9h8pM1COrFd X-Gm-Gg: ASbGncs1GhX3XYNqBUDnqaP2qypjZ1eE2Wwga/831ASZAABZ4EdCCyESm6DilAJh/fF ccIJ4O1ZTf/TMhl3VB+CuzwkOi1ggwC2vxzIYydWu3BplTAZQmAMmjqKEUiPIOcno/otEhwMVMJ Q8t8mFMypM/ubru6wVUTXegXy6XD7e3oDFTh2HDHEpzKmRwAgHc+KPnlACs7omljGZ/Q7ZOwFUg +bUzOqClV1KnlOqFZGySM+3um8lrrGV1vhY3F+YPwXxOj6Plh6MFww4mq+uGarcvqmnOzfTgqDv p5TDHMbeQd6+KzL1I8JtBvTYy4G2qMpx2nliss/Ohy3H X-Google-Smtp-Source: AGHT+IHvrT/pOwBpR5/oi7nDO0oDX7b+Ia3GuvmuV4YRjiam3fhzL0vA1O4fpkeO9eoIQZ2rGzuFbQ== X-Received: by 2002:a05:6402:270f:b0:5e4:b66f:880b with SMTP id 4fb4d7f45d1cf-5e5e22988f8mr14574895a12.6.1741592990458; Mon, 10 Mar 2025 00:49:50 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5e5c74a82ecsm6466431a12.37.2025.03.10.00.49.49 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:49 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 3/7] lib/rbtree: add random seed Date: Mon, 10 Mar 2025 07:49:34 +0000 Message-Id: <20250310074938.26756-4-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Queue-Id: 0FF0120004 X-Rspamd-Server: rspam03 X-Stat-Signature: a5jfa4zys1h9ejoegwdponpmxinbwuea X-HE-Tag: 1741592991-311724 X-HE-Meta: U2FsdGVkX1/EarUZzKxK65sFKu12Q3pRxXEGePpmZgYTCMvI5FidO7hfask+/t1E4kkdS5Tbv43LCGYMZ7ZypNoMScPOl03M2c48O3/SZBdil0qAK8qQpQZi37B3lZbpRAPtj6PrIGk/wBgNThLh5KRohN32W5lSIoUXUDgY84AZNwlXLv/kcJHXhh6UYKSWCRKwsZ8KeHL0vLzAEvrEFT4oA4RDVSe63bfyLWEoXbmQCYQ/JSXdViLm6QvA4GNIWOwXsoU+XFyMvDI607Pvcu9XJr+D9q35sHlX8bu3kqb67w23FFIuUiXKMx6Ld8tRLAYNWtSjYNGLB35l6zcMkqoCHtSWRY99d5nfTJ23UBLVtKtTZkKkzX6CpvjM1Snhi1MD2dFmwVp41fRbzvXSmMkeD1Cvnlw7N+UGuugfjeGHe2CNFzIl21304Rcxan2zy585twn11/XyGUIVWN7enXSyGh3EkA9Ashu1LHjSF7vQFo4FFha1E2JRSDjkS3c0rCGNm30Se9yR953nXX/Ov4pYu+L4ovWI7+CAKHgVoWTxMJx1a9XJgZ89dAAlNGdhjzvN/v0xZhB8MSfJ8Q7FGaIgDOyLrecrsAAy4Og5vI1MIgIgWLlOpH0VZrR3hc9J6HdXHIuoxQHxuAxX22HFzCvDqQCfAG5LRFgAWuOq9+xF6ayFSdHbypo44CXmLamziK5Fh1uiTCZDZFXBm2QRzyVP1+23Jb+xZr+l5eCTTqRfVUBwULTpxQJCywFTJdyntrAnuiryepL0kRah2Kenpe52Glkqa14Ktz6KJQFWoxq+ndSG3IjFp2umNVFotOAdUmYkIlNL3lEtkgUiT/tmzCwZEY7y36AX3SIVol+9dqU7ZibtJOWfqhx56ycQbml0839iOqmmTLYUescG807sxMIUhtsGfI2hggtF7cK6QA2M81lCgWHAtEJKBsybHFvYfYqvL/9lc4yZ7LbNu1j v/nGgznP 2ajGDVKdxmHiUufl0LqQpVCrsfmR/hec1dD3DE3fDs6Zv4J6nffIzVN5v78mlI387SLLInwiKy18f/WE6duqxouu7fYVZhnLOo84uamEGwaUo8PsE7Wn24kyIMv1ubMhg8seaPfXowhEwA7kkrgCIji6O49cErXHKw5g1bLYa0t6fun2ioXaIjHMMXSPKu6A0wabfv1AyD/woxQvp4aulZfZtrdmXFp1TflsdtJSIXoVwPlWBAGnN2yVBL5n6jb1iqf7KT3SohFLtSEPJ/dh7WqffvV1aX9QlcOuvidnAZy15Qsgg7/CgrLR4aSEX56xox5ZeQ9UL4ICki5EYWdGoV3cYVD015lfMN+jUwrprxp7y9AyqTKU1i4IwPbXHqAn2aypDYMNPyR+KdIscoYZp6HoL95F1o5yrBBQDddxn/Rb5fqO9aqJjpLEdBMIeKBPN3SkbiVXiJZ0Aty2b6S4UxGLzFXrgi5Cw749xJb9qUlnCvgXhJHuz6fOTO230F/U0CboZTHP1xWh3i7N0k9ftyTLXE7x+4vleP4adyqWEGWWcJir0TsxWV5XkEhCxlia95q/xUb4qEVR1aM2SyDrGubh7fsPpYd0khsyZ X-Bogosity: Ham, tests=bogofilter, spamicity=0.000031, 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 --- v2: * define seed with ullong --- include/linux/types.h | 1 + lib/interval_tree_test.c | 3 ++- lib/rbtree_test.c | 3 ++- tools/include/linux/types.h | 2 ++ tools/testing/rbtree/interval_tree_test.c | 5 ++++- tools/testing/rbtree/rbtree_test.c | 5 ++++- 6 files changed, 15 insertions(+), 4 deletions(-) diff --git a/include/linux/types.h b/include/linux/types.h index a3d2182c2686..49b79c8bb1a9 100644 --- a/include/linux/types.h +++ b/include/linux/types.h @@ -92,6 +92,7 @@ typedef unsigned char unchar; typedef unsigned short ushort; typedef unsigned int uint; typedef unsigned long ulong; +typedef unsigned long long ullong; #ifndef __BIT_TYPES_DEFINED__ #define __BIT_TYPES_DEFINED__ diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 12880d772945..51863077d4ec 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(ullong, 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..690cede46ac2 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(ullong, 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/include/linux/types.h b/tools/include/linux/types.h index 8519386acd23..4928e33d44ac 100644 --- a/tools/include/linux/types.h +++ b/tools/include/linux/types.h @@ -42,6 +42,8 @@ typedef __s16 s16; typedef __u8 u8; typedef __s8 s8; +typedef unsigned long long ullong; + #ifdef __CHECKER__ #define __bitwise __attribute__((bitwise)) #else 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 Mon Mar 10 07:49:35 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009365 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 47F73C28B2E for ; Mon, 10 Mar 2025 07:50:02 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 429B7280006; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3B2DD280004; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 204C3280006; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 0659E280004 for ; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 95771B7767 for ; Mon, 10 Mar 2025 07:49:54 +0000 (UTC) X-FDA: 83204867508.16.A184302 Received: from mail-ej1-f52.google.com (mail-ej1-f52.google.com [209.85.218.52]) by imf12.hostedemail.com (Postfix) with ESMTP id C1B2E40006 for ; Mon, 10 Mar 2025 07:49:52 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=TKb1fn8O; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592992; a=rsa-sha256; cv=none; b=m2O0ULje0teSfrA4z1K/5TtSKTCv2opnExZGNX4+WCrKXIHuFi+B34H/6VbFoewkQw5h+u 4KJAS1Bt7ZHVudzig1m57WvbZOVmkNGrn8n8CzjIk5cJCyKKeM0K5ETsLKq2DV0TZBKgea HQxnQdsD1iTnWYg647nbOAJ6WwM/S3Y= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=TKb1fn8O; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1741592992; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=joz/03VnGW14f0pZtcpHMTRILy/FcawI+lP6p4ltkek=; b=he58xI5Zoxh0XpJ9K9BH2vUCz0+NOtygHFL7JHBJZqRgRQEsZ5TNY4DuzK3yB02MBZbx6u HBgAemjosZ0yoRRyT85kQDOtKGpkoaD5+wJ79IyCTOE0CCunCxvupdK0d80pYXY14ghWLa 89bsxyGSq8TbQuM7fN+UdX4pwfHnGLk= Received: by mail-ej1-f52.google.com with SMTP id a640c23a62f3a-ab771575040so909805566b.1 for ; Mon, 10 Mar 2025 00:49:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592991; x=1742197791; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=joz/03VnGW14f0pZtcpHMTRILy/FcawI+lP6p4ltkek=; b=TKb1fn8OG7Ophef9oRtLp9y+HMCsDkpOZ6aUeqomti9xucq6VsOjQL7hm1Gy13sXX9 iqjZVHxVEO7CkA1MtY9P1fAowNTEpQvaAv/YMC4VMr13lPwgz8gbCrOjmWruSsOHn8wW vEcTQhHyCa4CmP6jC67D73U77Bh0i8Ci3xGij3txQgwOWa80E/dz8RVN1qR9JiRGW4GC Hwqe0jwu5RK7F3JvNUQoAKBeTdIZim1fuEO4f4KVY8kUw2KPABW2pNOtDmod//kmaASo vJNXe6ICE44WB7X6wt63gfV+43j6JiZrtOgdwOwwTM3l+vGxITyRFy7jrSX+g6xcnEg4 G2Xg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592991; x=1742197791; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=joz/03VnGW14f0pZtcpHMTRILy/FcawI+lP6p4ltkek=; b=a3D8c2yS+yuwKYMzSPUVbPD5uxlS1B7yy0qG/L8GpYV4pEZed5M3S/FXT20WG7CmwG 9WaESdQZjP8Re1zg5PgZGpBePzkNBqwSjLwibb+BJfW+ShwXnpy3477zKO+X9mmfl4QB wlSggwdnQ+bNIXkojh9hzWzdxbOod/TTAzLpdNQ8J5XJORXQUvbWoLLOH7cgAlaT1G9Q nKo+l1q7sWRi18DVpxFtfFfgUPd+lWAz/0lpw6qMbLvEqqHZp1XNp3BsUyLZouUIxGF5 zXfJDRKAtkM4T9Rz0+wKnv8LUmOJrvGediujvPMsB34kTh9803GBNh0kPT0OkL55bpAz jshA== X-Forwarded-Encrypted: i=1; AJvYcCVwd8iMK54R/nETnZ7S/DygiN2oiRGNikKu97TunwH9laD9POjXT9sHw/AwOiGHLb6S7F9wDz/q1w==@kvack.org X-Gm-Message-State: AOJu0Yx5/GnBZ1p8uF+bPrwFAPrkuwVD80DBrEh5VTwIkd0qaVBfAMtr lCnetqJR7hHWPvE1tcFxuj6TIRuUIM1eyNBrFUSA2VWZPfMUuBT1 X-Gm-Gg: ASbGncvYgy8JlbQwBEdAqrsccQ3l5fdhGca8MWNEwFcj+AjCJHvfmUlymkEYX/QIuCc 4TY4JOTpjG+Ex28XjvVKFiEA2UhDbXB1nAdtF1DNwqY5jV0F3wLGjJ8l1Vd3mCX2OqP9WgYbwlp xT8+REYvOYppyGPhNrJ0ccfMvgMMkv4RSjIzgVTQLTVIwZeUs+ezgb7Hpi84b069Db5iV5/3ngY vI9qpCo6jvIo27j5zxyRUMR80OdktJP9jTVHKucEiHB6ZGyXTVvJ4BR0+ivkMttOLULQdZ/XioW 37Sf6V/doswhv2ypGK3DD2hzpzJaSAxTEZPh6RIrRhwfwXWU6ZF0EZE= X-Google-Smtp-Source: AGHT+IFsHgng+oPXGP/cHdlWarbQNchvHfc9aERG+HQj3txMw2RZfi2meBLJa9JQDhhcuIiBxITKAw== X-Received: by 2002:a17:907:1908:b0:ac1:edc5:d73b with SMTP id a640c23a62f3a-ac26ca59335mr758842066b.8.1741592991238; Mon, 10 Mar 2025 00:49:51 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac2901427f2sm231575166b.151.2025.03.10.00.49.50 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:50 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers Date: Mon, 10 Mar 2025 07:49:35 +0000 Message-Id: <20250310074938.26756-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: C1B2E40006 X-Stat-Signature: 77kw41iagbscoo55fafwe6tsknq1tsiw X-Rspamd-Server: rspam02 X-Rspam-User: X-HE-Tag: 1741592992-632397 X-HE-Meta: U2FsdGVkX19qpE0EILDhKRuxUoUxASyYaJL40Ayk23jKMFjiwl31kAsZz7UDVvCVYNIpi/O50q3i66gYb+XtRSnOXZ/Rb99bP5LGjg2bVVBgtTN/p7+PT36jg+7+5XWb5XpR2r+RWHqX15nkQsNyO1uMqlZA2VDPi5jjDZQ+27EQ8NTGjzqsc94GaAxq23GbwRy2arCXztIpf5v6eE1AsxLI1CRZjL4cW5TvrXar/CT3eOl5JzGU7ydgB3KWOy/fS2DWxDcOg+CmjkBmeKi2rE5+QelPAer5DP1etxFhYqXHrTPFr/dFHRe5MYps34EageYFZ+E/K1T/stN4jXWUqwaeTn6PE3c1l1XcaB+4e5p9XjtnhjhWgwQZk7eZAEVPVt0RmGw3szm0+h/AbiJW7tHLIEzzZ9tJtVrFk17nnqW+/lJ1DNPhCDuTgl7R0jc8rwL+/J8OdZao17aa2BjoEDfkmUIeWp8ixaAP1zaNyCJivDJv+su8nP/fgoBuo68I8OHNmSk1V80AQ6v2P+nTEAOHhIkkzYYetVplPUrnmzl+rt88h/54zTwaE+BeQY4wxvIsF3tp1V7P6Pdxqo6Gk1VVyfwWv3gyfbj+36QS7vi27StBIkzFKqNpr44QSBi6szEBf52iRCOHkRakpaHldjIOEPBChSJHAN+4ygIKYckk5e9GKoi6zXLqL1tRl03KaC2Ci+IWsbIZl420nqtiSC3D0DWHMY6uhmftFPYqE17tFC2d1+xzsSGXM6HzfzdX31h702aviTO3IE30MirCOpOzEvSmc9NX697171bxaSq3X0GLyImdpJbhPzQTY/4qMEdL06jFCP0qsucxa3L1481v/kppciaxPEGC/d5PxLG4VllcX/+wnjtA5Ulod7Fg1eTlnUst8EkenDZ8+gZmHBtm3LPJI9rYyIoGTUDb7rB0Gts/htHlBdUwOK56jVlqAj12r8p9mW2NOP/3xZg yKwTmhth 3zMDlUIdmRLusCoxs9xeBouKPliukzM8arQQcrwflqr82NYmQZGWNSgeq6uOnsozlmDQVzYjYQEDvwdjOkWzqQWMs0bZ0aNet20bFliX5voAzDDS40p/ThWsK25DOThXON2c1kc0Po0csX05pTUT7vw3fy0K+cAnYy97FBvJZ5iNTTKQcGY07vaoHz6fBf2TC6l8aygZjSiwGht2ijSwQmrJFzXf6tIjVTb9wxJbwyDHzknpFAw5rPR8lxnuOIMeyZfKLEBzzMiNZgvzms0xyoqXR6E+tAfG+mc9718XweYqWU78Xc4va7BFyGqV0sF2asrRt5aGwvVDKFYND3/5+4VdBcv/4Fy8QG8bZIXuWhujHsrDDlN9Ws5tUrzMm8wFInfX6dYM7NcS8Mq0L7EjFzESaOOoA0og/PDPNpibZkby/vUJeosWFIcT/8vpQXB2CqoQUwBVhWywvxXs53ZVdSNJATMUiJycREzgiQo0JeALuABBp7igcy1M2G4fQ9JCTWxTl41HhbuPTv6DuORrMOs3girzmQ2pk1qLhdIbdfB7e/jB0yuQQT+QZ3Y2FZ51cr2/4mkFFGJITeJv9489N7eCgX/5MOcNtTliddsSADO2pP3jBevgHtJ1nvRxBaZi9No72q7skaIeGh7YM61mxp7r/6w== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Verify interval_tree_iter_xxx() helpers could find intersection ranges as expected. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 69 ++++++++++++++++++++++++++++++++++++ tools/include/linux/bitmap.h | 21 +++++++++++ tools/lib/bitmap.c | 20 +++++++++++ 3 files changed, 110 insertions(+) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 51863077d4ec..7821379e2c21 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -5,6 +5,7 @@ #include #include #include +#include #define __param(type, name, init, msg) \ static type name = init; \ @@ -125,6 +126,73 @@ static int search_check(void) return 0; } +static int intersection_range_check(void) +{ + int i, j, k; + unsigned long start, last; + struct interval_tree_node *node; + unsigned long *intxn1; + unsigned long *intxn2; + + printk(KERN_ALERT "interval tree iteration\n"); + + intxn1 = bitmap_alloc(nnodes, GFP_KERNEL); + if (!intxn1) { + WARN_ON_ONCE("Failed to allocate intxn1\n"); + return -ENOMEM; + } + + intxn2 = bitmap_alloc(nnodes, GFP_KERNEL); + if (!intxn2) { + WARN_ON_ONCE("Failed to allocate intxn2\n"); + bitmap_free(intxn1); + return -ENOMEM; + } + + for (i = 0; i < search_loops; i++) { + /* Initialize interval tree for each round */ + init(); + for (j = 0; j < nnodes; j++) + interval_tree_insert(nodes + j, &root); + + /* Let's try nsearches different ranges */ + for (k = 0; k < nsearches; k++) { + /* Try whole range once */ + if (!k) { + start = 0UL; + last = ULONG_MAX; + } else { + last = (prandom_u32_state(&rnd) >> 4) % max_endpoint; + start = (prandom_u32_state(&rnd) >> 4) % last; + } + + /* Walk nodes to mark intersection nodes */ + bitmap_zero(intxn1, nnodes); + for (j = 0; j < nnodes; j++) { + node = nodes + j; + + if (start <= node->last && last >= node->start) + bitmap_set(intxn1, j, 1); + } + + /* Iterate tree to clear intersection nodes */ + bitmap_zero(intxn2, nnodes); + for (node = interval_tree_iter_first(&root, start, last); node; + node = interval_tree_iter_next(node, start, last)) + bitmap_set(intxn2, node - nodes, 1); + + WARN_ON_ONCE(!bitmap_equal(intxn1, intxn2, nnodes)); + } + + for (j = 0; j < nnodes; j++) + interval_tree_remove(nodes + j, &root); + } + + bitmap_free(intxn1); + bitmap_free(intxn2); + return 0; +} + static int interval_tree_test_init(void) { nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), @@ -142,6 +210,7 @@ static int interval_tree_test_init(void) basic_check(); search_check(); + intersection_range_check(); kfree(queries); kfree(nodes); diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h index 2a7f260ef9dc..8166719178f7 100644 --- a/tools/include/linux/bitmap.h +++ b/tools/include/linux/bitmap.h @@ -19,6 +19,7 @@ bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits); bool __bitmap_equal(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits); +void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); bool __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits); @@ -79,6 +80,11 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, __bitmap_or(dst, src1, src2, nbits); } +static inline unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags) +{ + return malloc(bitmap_size(nbits)); +} + /** * bitmap_zalloc - Allocate bitmap * @nbits: Number of bits @@ -150,6 +156,21 @@ static inline bool bitmap_intersects(const unsigned long *src1, return __bitmap_intersects(src1, src2, nbits); } +static inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) +{ + if (__builtin_constant_p(nbits) && nbits == 1) + __set_bit(start, map); + else if (small_const_nbits(start + nbits)) + *map |= GENMASK(start + nbits - 1, start); + else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && + IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && + __builtin_constant_p(nbits & BITMAP_MEM_MASK) && + IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) + memset((char *)map + start / 8, 0xff, nbits / 8); + else + __bitmap_set(map, start, nbits); +} + static inline void bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits) { diff --git a/tools/lib/bitmap.c b/tools/lib/bitmap.c index 2178862bb114..51255c69754d 100644 --- a/tools/lib/bitmap.c +++ b/tools/lib/bitmap.c @@ -101,6 +101,26 @@ bool __bitmap_intersects(const unsigned long *bitmap1, return false; } +void __bitmap_set(unsigned long *map, unsigned int start, int len) +{ + unsigned long *p = map + BIT_WORD(start); + const unsigned int size = start + len; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + while (len - bits_to_set >= 0) { + *p |= mask_to_set; + len -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + if (len) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + *p |= mask_to_set; + } +} + void __bitmap_clear(unsigned long *map, unsigned int start, int len) { unsigned long *p = map + BIT_WORD(start); From patchwork Mon Mar 10 07:49:36 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009366 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id F10BBC28B2E for ; Mon, 10 Mar 2025 07:50:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 24D9D280007; Mon, 10 Mar 2025 03:49:54 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1D689280004; Mon, 10 Mar 2025 03:49:54 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 07570280007; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id DB05C280004 for ; Mon, 10 Mar 2025 03:49:53 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 5285FC0A79 for ; Mon, 10 Mar 2025 07:49:55 +0000 (UTC) X-FDA: 83204867550.17.41CA3EA Received: from mail-ed1-f44.google.com (mail-ed1-f44.google.com [209.85.208.44]) by imf13.hostedemail.com (Postfix) with ESMTP id 899A02000B for ; Mon, 10 Mar 2025 07:49:53 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=DBKKzZLn; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.44 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1741592993; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=fSNM+BjsL8ldsVQ0jKlhYRMMA8VboPlTUZMvNfcAmYk=; b=besqQQ5atrLVFfmh2AJE4Cf8iGYXsutDvUUBuE0S8oQt0P/2RZdCgpfEMb+ZnivvWi1XZe BFKt8QE3+VM0xnyrEyelC7m1rDCqklzIcM14AmGffU6agiiLImxqVPChfZcVeppuh52EA1 AOXktBqYgtUy8gb1cq8e+DQnuPJT+pU= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=DBKKzZLn; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.44 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592993; a=rsa-sha256; cv=none; b=n0Uialr9Zdi/gaIAwRn3YIp8Q2My//QtXkUUJvtlazHdrqkB5ipLhrIQIVzQDUk40WWHI9 aP4Si5IfDVAvLXtAfFw4RWzOpeVW2ntr5N9fY6UekKWyV6USXn+ysF8GiZ4nIZp2K/gh2L phBt+bSjrH3npnOGBgUIlS2ij2Oeejg= Received: by mail-ed1-f44.google.com with SMTP id 4fb4d7f45d1cf-5e5e1a38c1aso3430707a12.2 for ; Mon, 10 Mar 2025 00:49:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592992; x=1742197792; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=fSNM+BjsL8ldsVQ0jKlhYRMMA8VboPlTUZMvNfcAmYk=; b=DBKKzZLnvHN27Aoiu7+Qr6aRds6p4M/gedvf9N+4C9+NJeFHnZjh56LRuKXSCa4qP6 i1yIUBTe/au6BtST0ePnTcBU0hW02WDVDmKK79oUbeywOO0znPacndf9lAOzcqO0Mutj um3X2WfPViJ/v2REZ9VNYpfe87z0aX+w4U2hg1atvYqog8xn3fz2rOit6XMPylKeMsq6 JTf6YTR0GeGuHXos0rbHIuw538I/ngS+2IgNN/9CC9XOItzJQRkR2qlEQqAA1Vl8M/cm LR0sam/rsYrqX503Zh1J8FBdmc9RXml5DTjZVKb7g10Q0k5OAhNogWbZ3PLl2Xt20lXx VOpw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592992; x=1742197792; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=fSNM+BjsL8ldsVQ0jKlhYRMMA8VboPlTUZMvNfcAmYk=; b=evk0AP+AM5kenhQYV7VLyPNZMxfoU0hYwzDd/0fKzsP/R9LLd9fV/KbbUcoPBcE8E3 +ajbG99O12BDPYYyOw8aASdTT8htWsX1I0c6vsmZj4tf125hngE4xmqmTTFtXlbNQcH6 5zAvbsW7CUVdsgkWoTn9hD7sZ45ivAaGms1bldl4OF2W0ifr3rs1NrAjqzcworeSt2u2 mfJnbJGAXXq39XsEIozLJJpHHM1qe59PO0Pq5iPfqjBvENA0DmJDcGmhuGQydtO/uKpA hf7b2Kb49cKlv7WRMCHS4u3DZA+UM8HnVvij8OOXWI8b+7z4oE/uiitMmSh3X3BjNcLr fpHQ== X-Forwarded-Encrypted: i=1; AJvYcCWVqj3gYAPJ/+ArsmHYeH5KYtpkbPtXunEQIHP8oQnU9cOQoEcCPxQgARinGU6i+6OD2BSEC332XA==@kvack.org X-Gm-Message-State: AOJu0YyijIeSbMZ/9CsGEFuRLe0yJvRw8UkrgXetnsWhG0Uq3VC8xl/A agDNKdDbtAj5AJUi0CVVTyLNM3wkSaQ9gIi4t5+yE0kJFkJt/MPF X-Gm-Gg: ASbGnctEO9wI9oe5XFXuyEQF/ik2nacKQbnKR/pTp4gmAMescqsfyqI4KQe5C9w5sCp Dc04BztznzR7A6955pJhYqfonaofxoAhv1+k6DJ7QevzMX/3hzVSvkFVTFs9H+NKJYPBcHqla9u ceMCxDbtOMj9abCsqPVn+1Fxeye+ZKq+J2eyKIoyrVJ40uveukFA7Va6pRJo6s2fLjWrLo+RCXc WOadNTyz07IuCE7z8R1CaUGJNZXqwDHuhygydI5BZSzzAKi+qb42vIG5U+/EBzH9/allVESX+6K 8tAq/xP0ogKFXgfFlHYAjo9Rkc7k9+EuJI/36YbciZDB X-Google-Smtp-Source: AGHT+IEEhzEdUmOe/3IgZzeMQd7AIhsSTXxQCgkkFvUFa7EClkIVywBOwgsqXBU2JdOXxxU61WuIWg== X-Received: by 2002:a05:6402:35c7:b0:5e5:c010:e67e with SMTP id 4fb4d7f45d1cf-5e5e24bd6bemr27353094a12.31.1741592991989; Mon, 10 Mar 2025 00:49:51 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5e5c733f39fsm6698255a12.11.2025.03.10.00.49.51 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:51 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 5/7] lib/interval_tree: add test case for span iteration Date: Mon, 10 Mar 2025 07:49:36 +0000 Message-Id: <20250310074938.26756-6-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 899A02000B X-Stat-Signature: hxrptd6eqaz5zjggs5ns6w4njngi4jqe X-Rspam-User: X-HE-Tag: 1741592993-965492 X-HE-Meta: U2FsdGVkX19MlDcfPlY6WqerGC1OKvAeIGeT2m60HHWmz22t0VLSoRQUUuAMJoKUfFwwvyfST+rxe1ImhmD9rRBNDEsZUBOv2CviEy1ew6fjZ8GAFSvXD1LrUt+KRn/g164sKbER5IgTlfL8rupdZGh9N7uu/sKGEVUAaLecq1T2bjX9RaSBcDhUgXirDOfKJlvMg7I0n56yrh3IrlLSJi4x5kksffQ6VzhR0pQ7CMDgHDSMRL+KkxpR/GcGsZ0ZPkM+3trWtngKaN+R8nO/CzIBnxKeti8icWfUi48dm65U6DijDxvuisP0wyKkf3JyxnS7jy5ibJeUJsPbFDfKyQmh1RHUiy2IAMIJYFW+YTtFWx4c48NSKMm/hW3DO2VOq6IekJaUF+Ht8QSpRaBF5FOF9qyoww7aeko1g6pkVApw/eZJ0SJYSy7LzrOsMyGPyUJFo2SO07avjjL2eLb63Cm7q6pQwWE/iyGg7YJ+OPb5W3jPRnHEQiNf1f1efP5s23m101qetuswUmAfSfsvg50j113GDPIjBhwoG5NxNd4WIY/aOnX+onXz9U0Gp0WNZLSstAZeS3pHtyR97qClF1U5fQDhcAK2bnIpUhHz2y5lAgCV8J2PwjJofdXjki2g8TmHgpPBrHvzBc79Kvufhu1U09U3oKsuDdvQor+zvnC+ALD7UTUotSOQBV/0JiL+VOitR8c+Vzgz+4lj+IGakgLCTRC/3j+l/zgjG7o2M6f1mA7SvMq+JYq3Zj4EpF76Tk87PEg2WKw/ZTi9OPgoPTo0NmCYUD2EuMSSdpcn5vjnqMwRVhQxl56e0N3SwOm4hIEy7B14aaZzjj0fkh7bXDkifgwfxe4CN7F8E8LuUVRjitB16eXn7Q+3mxWR7GXds6hxSn/esfS0p7teGzD42eLv5+Flog+PCy5LBPE99EqIGuF3xnLShtwfLFilWA9vYNue14t5SfvPO/oGEJg goXwg9ua p6wHaA3qwngzGpzr4nsSONBw8CwA4jstXOUUi7KNtxSaE/DfF4OqyWJh4j63/IIZ59J5Ulu9aE/ah7wkeDaj9Ly8p7H2LOr4n+N+9JBzea7FAHGzywAty7qDMixrV+ZyK4GlD5O71ewfgY/B40ThwEiMGL2F3X0HQGkZ19l12sYJ+v4qR91UL/WHwzVnVHzdCci2Pnw0Gyg3MYcnYiaa9g1X0S1KdNBHDiDnFjXRNd6D6vNO1DfTMBhYZSy8S6S3qvXOHdvI7isqn9XGjnC6pXt0Z+lH9igrmvphVa2lbTlpe1inrXcJRNs6QR1jzUr8WJhNabdpGvZyrnCZNmBf7zOvprAOlvXAh0gAePSMmvpiYamGxhrQrlJw1iqU4MMLOmqlEIC324sWSYxKiHxi/mFCEWgtS3t0zrwGL/u/Yc2hHEiglXs7uhCawaB1bc4knhBM6MF1SuMy3IrvWd1R9Gsnoh4+aP6vWJh67bMIgw2F+YH+5BKoEDVXWOPPC8vqAPKIl0q21XQrb+J1azbG/80RWN7UhmPsBviLsrg9YTyRQrHYlCyBPKm5QJX+qcjFyW9lGxzDGVk5A/Adt6JYSzWT8KCyczOypAzp6xQ0tQKaJAikU1A5V5AlfVxZYKSor5yXh7uwyadbwFrFlGgUHV7nO1Q== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Verify interval_tree_span_iter_xxx() helpers works as expected. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 117 ++++++++++++++++++++++ tools/testing/rbtree/Makefile | 6 +- tools/testing/rbtree/interval_tree_test.c | 2 + 3 files changed, 123 insertions(+), 2 deletions(-) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 7821379e2c21..5fd62656f42e 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -6,6 +6,7 @@ #include #include #include +#include #define __param(type, name, init, msg) \ static type name = init; \ @@ -193,6 +194,121 @@ static int intersection_range_check(void) return 0; } +#ifdef CONFIG_INTERVAL_TREE_SPAN_ITER +/* + * Helper function to get span of current position from maple tree point of + * view. + */ +static void mas_cur_span(struct ma_state *mas, struct interval_tree_span_iter *state) +{ + unsigned long cur_start; + unsigned long cur_last; + int is_hole; + + if (mas->status == ma_overflow) + return; + + /* walk to current position */ + state->is_hole = mas_walk(mas) ? 0 : 1; + + cur_start = mas->index < state->first_index ? + state->first_index : mas->index; + + /* whether we have followers */ + do { + + cur_last = mas->last > state->last_index ? + state->last_index : mas->last; + + is_hole = mas_next_range(mas, state->last_index) ? 0 : 1; + + } while (mas->status != ma_overflow && is_hole == state->is_hole); + + if (state->is_hole) { + state->start_hole = cur_start; + state->last_hole = cur_last; + } else { + state->start_used = cur_start; + state->last_used = cur_last; + } + + /* advance position for next round */ + if (mas->status != ma_overflow) + mas_set(mas, cur_last + 1); +} + +static int span_iteration_check(void) +{ + int i, j, k; + unsigned long start, last; + struct interval_tree_span_iter span, mas_span; + + DEFINE_MTREE(tree); + + MA_STATE(mas, &tree, 0, 0); + + printk(KERN_ALERT "interval tree span iteration\n"); + + for (i = 0; i < search_loops; i++) { + /* Initialize interval tree for each round */ + init(); + for (j = 0; j < nnodes; j++) + interval_tree_insert(nodes + j, &root); + + /* Put all the range into maple tree */ + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + mt_set_in_rcu(&tree); + + for (j = 0; j < nnodes; j++) + WARN_ON_ONCE(mtree_store_range(&tree, nodes[j].start, + nodes[j].last, nodes + j, GFP_KERNEL)); + + /* Let's try nsearches different ranges */ + for (k = 0; k < nsearches; k++) { + /* Try whole range once */ + if (!k) { + start = 0UL; + last = ULONG_MAX; + } else { + last = (prandom_u32_state(&rnd) >> 4) % max_endpoint; + start = (prandom_u32_state(&rnd) >> 4) % last; + } + + mas_span.first_index = start; + mas_span.last_index = last; + mas_span.is_hole = -1; + mas_set(&mas, start); + + interval_tree_for_each_span(&span, &root, start, last) { + mas_cur_span(&mas, &mas_span); + + WARN_ON_ONCE(span.is_hole != mas_span.is_hole); + + if (span.is_hole) { + WARN_ON_ONCE(span.start_hole != mas_span.start_hole); + WARN_ON_ONCE(span.last_hole != mas_span.last_hole); + } else { + WARN_ON_ONCE(span.start_used != mas_span.start_used); + WARN_ON_ONCE(span.last_used != mas_span.last_used); + } + } + + } + + WARN_ON_ONCE(mas.status != ma_overflow); + + /* Cleanup maple tree for each round */ + mtree_destroy(&tree); + /* Cleanup interval tree for each round */ + for (j = 0; j < nnodes; j++) + interval_tree_remove(nodes + j, &root); + } + return 0; +} +#else +static inline int span_iteration_check(void) {return 0; } +#endif + static int interval_tree_test_init(void) { nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), @@ -211,6 +327,7 @@ static int interval_tree_test_init(void) basic_check(); search_check(); intersection_range_check(); + span_iteration_check(); kfree(queries); kfree(nodes); diff --git a/tools/testing/rbtree/Makefile b/tools/testing/rbtree/Makefile index bac6931b499d..d7bbae2af4c7 100644 --- a/tools/testing/rbtree/Makefile +++ b/tools/testing/rbtree/Makefile @@ -3,7 +3,7 @@ .PHONY: clean TARGETS = rbtree_test interval_tree_test -OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o +OFILES = $(SHARED_OFILES) rbtree-shim.o interval_tree-shim.o maple-shim.o DEPS = ../../../include/linux/rbtree.h \ ../../../include/linux/rbtree_types.h \ ../../../include/linux/rbtree_augmented.h \ @@ -25,7 +25,9 @@ $(TARGETS): $(OFILES) rbtree-shim.o: $(DEPS) rbtree_test.o: ../../../lib/rbtree_test.c interval_tree-shim.o: $(DEPS) +interval_tree-shim.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER interval_tree_test.o: ../../../lib/interval_tree_test.c +interval_tree_test.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER clean: - $(RM) $(TARGETS) *.o generated/* + $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/* diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c index 63775b831c1c..49bc5b534330 100644 --- a/tools/testing/rbtree/interval_tree_test.c +++ b/tools/testing/rbtree/interval_tree_test.c @@ -6,6 +6,7 @@ #include #include #include "shared.h" +#include "maple-shared.h" #include "../../../lib/interval_tree_test.c" @@ -51,6 +52,7 @@ int main(int argc, char **argv) usage(); } + maple_tree_init(); interval_tree_tests(); return 0; } From patchwork Mon Mar 10 07:49:37 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009367 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 7F08FC282DE for ; Mon, 10 Mar 2025 07:50:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3A7A2280008; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 35515280004; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1AA2D280008; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) 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 EC6FB280004 for ; Mon, 10 Mar 2025 03:49:54 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 4D0E9C0B7B for ; Mon, 10 Mar 2025 07:49:56 +0000 (UTC) X-FDA: 83204867592.18.B7F00DB Received: from mail-ed1-f42.google.com (mail-ed1-f42.google.com [209.85.208.42]) by imf19.hostedemail.com (Postfix) with ESMTP id 780961A0002 for ; Mon, 10 Mar 2025 07:49:54 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=OnjkuDGf; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.42 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592994; a=rsa-sha256; cv=none; b=YQ52gMw3U7WuGOaGpn2/mi0/XtKX8/du3PMSaAbvgg21szYsRErGqbJpjW21t4ysRjzKyw 1STKdqAvm1DzFbiKb4SQqUgnRk7LMo8jHqWHby/Yu2zfWNJxjn2EEr5MoZrw389sW3kCD0 krYPVIZxLNpYYlm9K/i87XA5z8sFKGU= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=OnjkuDGf; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.42 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=1741592994; 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=xBI+Pzrdz5sMrEYCMyflvj2xFMP/t9XTFf2D2j2R2EagdxaOPlavA5opDrxEl8s9dkhh2E 30KGD5NN5EnVuXNS4Lhz4fBrxDMW+W/w93IlLNEDLS9SMqDi3ghUnq0lbQQDoRRj04XhEj dDSanXk1VtxsQ0iG6FeUdpnakakqjNs= Received: by mail-ed1-f42.google.com with SMTP id 4fb4d7f45d1cf-5e6167d0536so3418711a12.1 for ; Mon, 10 Mar 2025 00:49:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592993; x=1742197793; 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=OnjkuDGf75VlJONMXOlbB/y1CSaSuEdigf3gMY47+8zbnSdEjCu8GlUUJ5oPJZ6NOJ YQnyEgZXjDlKT1xvW7KQ2C+SIDEC5zhsxBFQmg3AtQ6TDmcuo9JkiM5IJNyStIGgAaCD s49iB4fAygWydUsVbXFRm+B18aiej3OU6nlztnlaqdLnJOEXmLejs0scNaF/wOoh21L6 nS7WTf3BTcY9Sp0Gv12QyqEu3a4NdxnruuPeS72EzxbS54Pg+gd9hbwWSuGXa4oBIsWP cOXefsxapadpoxVckXAc7c+hHMur3VPvOaowz2PbFnc8GBO9/VvfLrXm5NBJ8KqG1+kc BMHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592993; x=1742197793; 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=EjkVLt5Xb+5LbkJLTr7G4zyzsHkkqBEoFrG4KG6a5i4O+xjOuimLlH3eEj60H3MCad vepsGAZkfqoWFIZBDfVJ2TPQTFkAlMoBHU/xxt9JxTfIR4gAQ6ncmr2KXrjR1CeRrAMY ujMPSeoyReiQeOo5sH6kCA9Z3ctasFzmrHnPQQvZ/eVbCwVpXeIhDQ1qOJF88gZASm8r OmgAC0nhVcKMZkJJ/qJJkvL5lDOLE1g0v9Q8+mFfO7zvOiXM9WfnMQ/+QfqJ9n5M4lUF pBG8UnIdnkWOyaklOf6TsNsmxNY2q1S+ubqga5NaWiL0DtNhwJc6L8ln6y1I1EHIi2A+ NlkA== X-Forwarded-Encrypted: i=1; AJvYcCV5/nAtqQf3b+O9q757KmZJKliTh1zAaRqt3MuIuGJ+Tm35Eh2EDp9Gjvl2oo899fgPmOyKCCjRvQ==@kvack.org X-Gm-Message-State: AOJu0Yx/RiwyheB4G55oqiziwlen4x7Dl6LSDSJckmvce1mmXeIpRAPR ThHl5HfvdWRl6BlniBctF+RccFGoBMruFUSc2WQ6nam60eWzcNi4 X-Gm-Gg: ASbGnctgZ0TZWmAj1OGgXtLEUvRF7rD6XZ1CODfNXQO03lQqSyYqK399yEIAf/Wixws cNE4bqKVHeX23psxAPKWsZk1Uro+0OvOMYCqcl88mACBCOKZMJDCToBOtnS3zMg6lwUKbTLWr18 a88Qt1uxdh9dAhSeMXVm9AnVb3bQ8crd4aFHnRiyheeyDFTd2B1YlMoiJz9W8Zpv7U0z8CCz5g5 iockHHFFP3+RwTCP5ij06wvlFEFfx/fHiaEESV6v4C/ZWyuW2N41VSFW4fDC/t1xW4TTJBrPC7c x8fMYsXwmWu3I0mv9elG/5MrttDaOLLb00FRayaa0Huh X-Google-Smtp-Source: AGHT+IGxctomeTXnccXmCKDLBbisBnglon009/Xz6BlFrso0ld3s1z2+xfX8OQnemTt+wvwGgoMnpg== X-Received: by 2002:a05:6402:34ce:b0:5e5:c5f5:f4b with SMTP id 4fb4d7f45d1cf-5e5e246896dmr13924307a12.22.1741592992712; Mon, 10 Mar 2025 00:49:52 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5e5c733f8b5sm6459268a12.12.2025.03.10.00.49.52 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:52 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 6/7] lib/interval_tree: skip the check before go to the right subtree Date: Mon, 10 Mar 2025 07:49:37 +0000 Message-Id: <20250310074938.26756-7-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: 780961A0002 X-Rspamd-Server: rspam11 X-Stat-Signature: fep79cgfry9j6neyswdsi4dzan43g9gt X-Rspam-User: X-HE-Tag: 1741592994-999086 X-HE-Meta: U2FsdGVkX1+GSZwz1yc8W8BZyzSeOLJwugWT6OKXpteDhu8E0aUbexv56UVcA3JsdrifCA2W5r+cC7cgS4g2loIgbN4jinD2p7rPNxeupZLRKz2wTAL09QGoS2pyEF/zYjEEMsTXXnXv00Ie22sABIyp3/zbtlgXsbt6zbwcG5lwiFI9JDcyIBTr2zlGSDcn5PRvRqQxNHViBxhkU+yVfCOZTdu1mOduELhQt+pRVE5w4j7zk/siNyydcfXGZgaEZZD++oimSa1ONXjK6Ae+wiM4dHwATm3FHI124NKS9mZZvd9MRNvQR0q2AS8ytwKbM3ja/84KJZFcsMwyhdVp13CtGzWV6w/WATOHN/gyyj4G0rRso+IxJ4oCdANmkD62e5i36DQZdf7N/PJmo3OG9HnTCdbn8Ga8geos3p5ZTV9S5SMcn8/Wb2MmNzZSZ/mSpNolgc8OXhj7UrcylpPRVNOFDTztWiGFeu5Xmgeb1PV+7uFowgccVojrmmI3nqRkk459bXSn633Gq358SeR4o61B2sTzWaNHnxo4O9B2oTPGw2SEZbvFZXAngO0qIiHxu2nTtnUQM1bZkAZrUihWK9zg3iGuWymEPneCYe1WusXkRJllaYV5s2gua25EnUhIDr92F0FTmDYMG29a0YCAHm+cGgm2jxljMRbg/Npq/yjFUrQ0kSDehjbqIY78lN/U8jbjDQDCMa2FM2X05UEQhpovE4vzJEsS8tzBAjRe9REILpGyTsrcy+7+ZQGBq1ENymPqtdykeNWiiu2I+qPJ6hNPm3xU3QHvdWyP75UByY583gQ6DVb2pyl16NCMovtvTcXRKnBSgs4++NSc1SroCR1W9X8U4lb2L+QSZGpcGDH9lx4DwoO4BpR55FCBh1xven7XXXuRLgMniORda/7pp0zoJcKaChn08kVAUKZFzW4rJNzcuKwvRiDvkutICXi51E22rXVjvGCB9Imi3eo c0lyIHX6 fyNCAZ8oUoekpeI6A7WuWfyxJ2+3vAzvqImV7jbMPdxeolAnBiv/zTTiuExJap5Igufjwnot47Q+KjhcdxEHJnwsCPqmaPUr37e1+5Xn+EXzh4IGF/TLSwIA49VtqzwW+M6EstP5QC5JSgIlgtxVhhRbJ5aGC3ZVFV4OksHwcI7dmjRScgqJq7m+Js4fcaOE2PaH9RX/DOTQW0Ujab82231CLAb/UUXq6Taf5Qopf/fD/kNwtIwLLVv8uN3V5oHopQr668KL1PjJnYMQuogiYZWbz2w9aKWvWORldfrYzp4IGbBpvmKbUU2PxzQ9Vp9g6MaVuyaFapWYAatd8cl0o1vfb2nQlhOsYUrCTwGA0PO7grZCScIrvUdbWir2IJr4p9/RA1D1Ge1ou/zD+P6MGp4DIsAU31KmLjQrFhEsfS9JyVGNTZf+ankt0GyfGcK/XTrUZXb3F/gQ8J7ntMq7QvaiY4Z/zBoYDZPkKIGlnEuG+RfNo4vvwIGur7b6jHKyTVyltLBmPFilfAYhpgcAiCR6l7AGRncIf4Uy4nG+oTvUmQ0NlVlzPMOAePB2ZddYCHXbu7FZjrTr0n1L7gCYkS/hvGABzcxUQiSXhF+DXkoSKvkHHmWzWl3cd/T+QXlp+vLA5qYW4yg4+zZ9eHyqJZFR0C75/fl1rRY9u2rAaNDpfA1Q= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000002, 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 Mon Mar 10 07:49:38 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009368 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 1DEF6C282DE for ; Mon, 10 Mar 2025 07:50:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AA4C0280004; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A2FA0280009; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 80D74280004; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 4BF02280009 for ; Mon, 10 Mar 2025 03:49:55 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id CF90BA8F1D for ; Mon, 10 Mar 2025 07:49:56 +0000 (UTC) X-FDA: 83204867592.26.FFC77CE Received: from mail-ej1-f50.google.com (mail-ej1-f50.google.com [209.85.218.50]) by imf18.hostedemail.com (Postfix) with ESMTP id 01D661C0011 for ; Mon, 10 Mar 2025 07:49:54 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=iv2FIw8j; spf=pass (imf18.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.50 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=1741592995; 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=s8D9wIHCQO6GSqINDUAZTXSIDPk3aVq+Xtx/mUavzJg=; b=o3B7a5Um+yIERrpUPAn1SVgcm+tpH2Ot8lHMQiOKqiCvRJ044f4LPBT4QpULx0o39EVpfs XRLPXNPE2EYbmpVX/jxX7Mn0YCowVZi2wCilgA5necms4UAGtUPT9JZ1QeQxzI95zeJfDa NFR22BOyNXgDs43ojh2B0w8DpOFmUR8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592995; a=rsa-sha256; cv=none; b=qYYgbtNjCK2IOXk4vzTUA0CBsYeOnACVSKlgY3MCg2rhUsX+7OdvKtSZNd6ZtaDo2+NGFm rS+njZGQFkNy20m0PdvvXHfbY2y4Uk5XcUMWLOnDOqT+T2knutbeyXhYdot8RANWPO0kDu n8fOz1k3KJ/vKZC5oVGGze8XIbrIgrE= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=iv2FIw8j; spf=pass (imf18.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.50 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ej1-f50.google.com with SMTP id a640c23a62f3a-abbb12bea54so720461466b.0 for ; Mon, 10 Mar 2025 00:49:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592993; x=1742197793; 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=s8D9wIHCQO6GSqINDUAZTXSIDPk3aVq+Xtx/mUavzJg=; b=iv2FIw8jbkAi+53J4RM5t2qMHZsZWYTsqxT1XFzsPMzkurzKalfdhoqAWlsogkhoxi KwbL4OY4NenLUXYT/iJSMGn9/9BRYGkygXHNnyYzX/MwaJrf7KBMTHO+qXrg6I1bHXoy pOBBmP3fMRf6k3RnYy2FZerdr4InLilrmoNLeoerhjgL0zKvAjM9XeTxyzdu6IiNeqFp tQqN5kLCwR6rsEDVflQZaSBZmGyMAb6jlM8vbCXbEoFau7VTBzSaWHl7hOAPwais6sSB xMPcrNtjfb2k368NQk/he5sD207xrgcqx1QtDdXG52HplVlAdMdBzm8vQvBg1Pp5CXWg oVCg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592993; x=1742197793; 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=s8D9wIHCQO6GSqINDUAZTXSIDPk3aVq+Xtx/mUavzJg=; b=gs1Ca9tKCDlfFWUAka7JPYhx7nrG986FF77nCG2oi6brlg1U7k0FVCVIu8kRemmNr/ 2rqeXPbHSBu74TWMPuBiFjmqtGFlsY2HRHl4fkAMI+tuLMUcGzFysPU5wWDOXVc556nV TS5ilwjCO1ffohCu3TFtGUXZapal9rEkV/JrEWKryWwlK2FCqvlANNTiICBhYaaHwPUy ZXz8jN8Tg0HhZS4CG2MQrAEcmyoGoas8TXGSiXn5QFTkw+T7BVCxbB3vN8QVv78kgIu/ 0bVLFNrDuY5mE6T+B6WehKFJuM5I8uwXuk4BHP5oLKMXf+SRtJ0EVHYg4rTI4IVzLIZP Iq9w== X-Forwarded-Encrypted: i=1; AJvYcCUK+WEzOl9eDjHWhJg1Zhmu1MCcXVn8CAcQTFjchrwKjA7qL+vTnaTtZMV3jXLo08dlPY7z5wT4kA==@kvack.org X-Gm-Message-State: AOJu0YwulkDhjnnKwE1eAjeLUd42VsHvJylpXFTroN8ymnQeyEGE+KeP onnpKeF95VAScWPScDIcHjlvdc9k3BdQQH6QEHUzeBn5/12G5rUG X-Gm-Gg: ASbGnctWkZofdaYcMi72icVrfhrLQwzl4K9Ii4pocBV9vgmPEw66gp2WLqvZt1bpY7x DWLIALbRda+n8JboUIDGu+mpye3dvviEYQGnNvKF5VpxBcVGmXJ5Ns5JJHgxa1lagAp1QaSbijo d65BqcMrso7/4Tfodv13vuER8HH9K1f35sCzukntob0rR1lQcqJOHLmmzXRHrYa8P6jvnMIumvF 841YVKVfYGFgW2Xu/wPgWv61oVPlKc/DCHXOO6fLmYQVnDXhUyxa9Kjyvyh1OyXTAbhIwIX5h3l DPJ2ePFw2pI+0d2g5Ucs+2JYTlYd3k6rSdwlbBbXDGwT X-Google-Smtp-Source: AGHT+IFrPHGfFhLzZZ2ZsP+CQCgsVS7dZOADqpC8IaFPNkNUrl4sZ/mvJahbHteKvA/REkfmKEmExQ== X-Received: by 2002:a17:907:7156:b0:ac2:26a6:fed5 with SMTP id a640c23a62f3a-ac252703847mr1186103866b.29.1741592993480; Mon, 10 Mar 2025 00:49:53 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac2901427f2sm231579666b.151.2025.03.10.00.49.52 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:53 -0700 (PDT) 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 v2 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap() Date: Mon, 10 Mar 2025 07:49:38 +0000 Message-Id: <20250310074938.26756-8-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250310074938.26756-1-richard.weiyang@gmail.com> References: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Queue-Id: 01D661C0011 X-Stat-Signature: xcy8rmnqpomkksmewtyprhwnhkx974s6 X-Rspamd-Server: rspam10 X-HE-Tag: 1741592994-789529 X-HE-Meta: U2FsdGVkX1/MoKUMq71CtGlvkK43DxO+qUZ7UTq2jCQkPIqFOYUMP4iWni4TmMkNxlPEgZMn+EOa2dy0PtGTXpJ44ywZ7uyYfrYeUVYtqStpeVlIE33fKDPLyK0cO59MYa2FSYdkZtFuCbWReaLWxQIDiRKfodnQUdE9rfw65lu9pwjBx7L8at9EvUtTX1RHpx8BbXCCna8aptnrEwikcErDtmYIDUe8eSZuBTBWcXG6Eqy6d0y1kRnRLqWMUP4L5wNTx3QRh/nkExEno+2r0nJWCsKJByTua90hMwt+XDGpx4m3z+5yk6CvpsAkCVkM4rdcVFwEaFcePaNoQ80mFCpgi/lJycEiImd2Hd8rnzMhbf2VNzBOy36M/TJrsqh9TEc0l1KtChBteyHa1Hic35W6uuusu8D1aZkxrmu2UWqMH0ulAM4K3ilcV1MJ2XhzJ/RgYor/lyhaOJunreY+ibyLqqQaE3vZbu5jKeKVM+Rvq9vTa4gUvgsUsgw8xxzfJVYDoXwSexMAR/HHlTl345v7kaAWJobxe/YGrtGW8NtVRXFwC9hKj4ifIVLLshPX040puuVtfloOmSdn/62jzU12qnCtkZkXFDKE6VmhMyTMRe5Opir0OnsQabqbQfO06Z7RBNO2PGU+P6KQmmDo/kNe0VLOE7YS8GKNk6Olkw5zEonnV+D4UdQ+qBP8GETAPAstErU6yKNsYk/58w6stzzUnWkU81scwb05J5/uh+9AE/tgMuxV0qwMHZoSuvnsQiEA45m0bHKHMoTq5tQU5yqHACXvMWUBN/YRKoGOeSXJLhryKwmB1Tre6KfPx0QI212KjNdX9khDfxqbKfuHMUXEUZimomnEubb+x03dpI9jL5lhBfGbVUBRFU47MGv0bOnkyNJeqttTmx3AYadckjloDIPr+svO+rv+Cdwm7aXGwEelUwT659evlKhjDXk0XL5TAzU6quWvgxjO6Ei osEe0JDX zbQdMx60amKK2zHZZuIW0Arp9yO1oKKim2vVvRRvQVmVLnrfTED+mBO4vfzvmTWFgSHGKEHobTWTJx20SRuzFYIdkBuJmHBInfCPLuKLK10d+sBy68t6UggIsAQvOI0guhKOrDz2RgMtBNXtPTfBhFxhPPtJpsM77QMkWZahMDq1C9jjaWnYurzfOyU6XxIpG/XcptTYQHhoWuTQlEREGAte9SKLBq0zL0El8atsRnjZTTDI8GAb4lDsTey2QWOgBC11hGQjPMplsZjAdTkRJheZ4ZfQY8PjXTq3UuOdLfeQEKgEKCv9vlaWeEq8zxfFVWbtq5+YsGUE3S+5QvE+iKLcvmj8Y0Kl52YaswbHMX2fcGZaz3gPppPfMHhXytI9jVUYdxW/JH1l4Gg/5DaATVN9BBl2jDXSodZCmWnZK+3XCoEOvsRbPDPRddldlKmxnSYm+W6SNERpTIQIUeVpdxY9eCdHAiFoRHRGzyCcXSvBr8xDFlNFP+x9pmWh9KJq1gnYLYkvloavtLCHliOK2cE7V5p57II5Rp+uYqgLpXoqxbprD5cfB1nC2fl5dGvoToKWVehYqzxd2TlestB/VlP2g1XCD7SCdpP0c6+EpJAEZjIT9VAI02U/2U11hMri46UHS7+8Phh5bEP5eS8HhnvTEcfrp7E4joGl64jCokQOj5LkitaWjRlrNvOvuEbiQuGlD3nUJ/CKyZopjPqA+U8yKt0eW7MG/sOod 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 Reviewed-by: Jason Gunthorpe --- v2: add the missing "of" in comment --- 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..324766e9bf63 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. + * of 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)