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" +