From patchwork Tue Mar 4 01:19:46 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999759 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id B3E05C282D2 for ; Tue, 4 Mar 2025 01:20:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9721D6B0083; Mon, 3 Mar 2025 20:20:37 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 883916B0085; Mon, 3 Mar 2025 20:20:37 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7241D6B0088; Mon, 3 Mar 2025 20:20:37 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 503596B0083 for ; Mon, 3 Mar 2025 20:20:37 -0500 (EST) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id EEA6C1211D8 for ; Tue, 4 Mar 2025 01:20:36 +0000 (UTC) X-FDA: 83182113672.03.2C7D116 Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf12.hostedemail.com (Postfix) with ESMTP id EFD4040008 for ; Tue, 4 Mar 2025 01:20:34 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=IK3KhK9+; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1741051235; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=6IRYqsy5kv8Qft9uaJF7Bfdin73pEBYViojMc1Cujz4=; b=jm28GOgj1n6obog8WZF5hrNT2eCgQjZnhFjAkvRPynkpDuRtIJKLU2qyMm7QDOAj9P7TOO GWj57SD4ZDy+d68PKViaLK+jaXvZRAKeiwyD7VFsyo50/fNa2VdFkGXd8WqsiswXbuGWI3 gi8o4YGH5pHitWISVFXor68ik4097Ro= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741051235; a=rsa-sha256; cv=none; b=AdNL+smauikq70fSBzDthzF8MHbTeWyLZ/5ZNh8ddvQVSyNBfN0X41xRchoTtUbXKebAnl RBCHDB+ClxDHxY7o1eAU7W5vaIyp4Wl7cRj13OJ5bzaz8cdSee4jbJlBCS5WkgigIZpjz8 daTp7k0Bh0sa+3NhKaJrZIl1cA9toLU= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=IK3KhK9+; spf=pass (imf12.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-5dee07e51aaso9492881a12.3 for ; Mon, 03 Mar 2025 17:20:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051233; x=1741656033; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=6IRYqsy5kv8Qft9uaJF7Bfdin73pEBYViojMc1Cujz4=; b=IK3KhK9+w/t07QG8mH3uYwPJH6vov0L2S0GgFrV1UwEJAC4F7GWk8ruWQRini4z+BF ZzFveL/IWi2tVpgN3joLapmrP5FM2PhBuNrd0QBYQEya5d9VLL9Gf82ytHUmfmq61tu1 Kx2IJ8KTkmIv7+b+apqNWjZxryePgWVlWn8JBYoVUzNcJEVHifxsRDe9bymSBe1qLXoQ 2orBhCsuwA2HGvPpfdWVaAH64Lpzk23k+xMIvTLb9RglJZwh639D8lfFFlPZ+M2i0RPE fl4YoeNxfvviZrB6EsOsPQadqWFW5M6jHcCIF1EZ5265/IJIvH3V570WgePv4I+zZ58q fnnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051233; x=1741656033; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=6IRYqsy5kv8Qft9uaJF7Bfdin73pEBYViojMc1Cujz4=; b=FjQgKlQR2hNlxeHam0NalspaBsQE+AtXPOZ+YTDtI6G96h7JDr5PgROrQEkBRL2uIy U+HYeUEofJInWFqMCto41h6WtQmGKZppV3w2NGeiaTuILT1Xp+9/bTvcpEG1IVphykWm sXXKBwIxXZ10uyuyzoAdGrmk9vkhoySE9lOQM1/GHcPXk+1ACWXa4m4vMIcSzVWQmQpp Fspb/GCsZm9Cp8kQ1+JeCte+TtJHJ3nrdj+PbEWkGiMRNb85NetiZJlNuaPw78twRMYp lhGXKkcK/IgLx/ATx38bhIcmyki3zBIgXh5SiLAwztrvE+fj0DteX/sFSAapQ2E+7bCW jXqA== X-Forwarded-Encrypted: i=1; AJvYcCVmrMz5xhvqyZlHBTmKCbdNBGT2k8bH6K4G7GmUdlEdHpwQ+qVGellCUMY08+UgVCne/7gseC5yjA==@kvack.org X-Gm-Message-State: AOJu0Yz6LvJQXEk3YO0DOkRjLbJBxuHo7cPhed/hQxzfqOOPutC3ct8s aneSxDHk0ym7agEFx3klc+WbZoaojtZ5anmL/+Il/ROW7Pxqa01y X-Gm-Gg: ASbGncsQPazDSRCBsmziuaiIXZsXxowO5Qxb5/YrTUgvKKJeCjCqY+jQRQjBcYmj21E iO7CdICO0RbEKBE2pvEUGBOdgZZM1JY29Ms1rWfZCGGTkQK5xYrUit/WZoNHDAzO+skvRwLpk1P UKQ2EbdhQ9T0itdeA07saichPmQB8lr5iJvBPDiWmZZtqE7l93jzPYRV+GNXVyGsRYYyLRibbSq lq3OVpX7mAmdAKNvWV4q2KHAz6EittNWhzDIZxyco/9uXAf0O+va8b/V38c1Tc5MpRRkdZoa+0G CqsUKIVpp1yzlravd5yuAJTnLGB4DqriLOYPO/QkopV1 X-Google-Smtp-Source: AGHT+IGafBiaW/uln7TkX4zY3MWfEYcRqgYKLFmeIj0TKcASe5B2sZisGvttx4VAmaNyMmn45QeO0g== X-Received: by 2002:a17:907:2d8e:b0:abf:6dc7:b53c with SMTP id a640c23a62f3a-abf6dc7b96amr788207366b.37.1741051233415; Mon, 03 Mar 2025 17:20:33 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf508f2288sm529199966b.2.2025.03.03.17.20.32 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:33 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure Date: Tue, 4 Mar 2025 01:19:46 +0000 Message-Id: <20250304011952.29182-2-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250304011952.29182-1-richard.weiyang@gmail.com> References: <20250304011952.29182-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam02 X-Stat-Signature: nwfumfp68m3zwip3s11zidj7jg4k17bn X-Rspamd-Queue-Id: EFD4040008 X-Rspam-User: X-HE-Tag: 1741051234-883724 X-HE-Meta: U2FsdGVkX1+vVTWubGdk4aErq/htlqoHjuyg9iJ1EuvMaKPKghxy9uOx+ODhSb7uMW9nl9g8EiP1gEfeeoFysGp7cfvwyg3FO1+B72rn6HKcS8HoSHB2WtUl6AIRqrZvzvTsQSX1Bu9Uh/93BBM6X4J+CHV1+l1xiA/Kal0KgSX3+GprXCC+sgrpKq5kk03wQbAkT/E/3nfBhsuMzyKjZ2rfAPXo96MmJHhokTQKGUhQy1J5YvEy9orBA9Gkw2h9mhwUwugzR5v1LoXm/S1gzRoafDcL6F1kZHjVtsCCcCYlsmq2vuC40yjZIVQhmTkNOy4MGrN0lOLGv3rNsCGMjFlEnd8RqcMiWlcDFFB8VNPjagiiZ29Rg2AbRWVE+ujt33uHZc2sHoJUWGUwfGR9YEKFI4R0HAigyzCJ7wNh3U3EKP3AjomqIA+Mu1oEWs6XC18nI5oJ9Upn73ISc2sj3FF4VnCx2bNewiowIbwvKAd5ghG4mP2O0m4T02H2r1jhlztNlUGez9sNjLcPxr3CQDr46lxxlwhqRX8PjtHub9dRQhSTD/htrHOmBFOLpsmhrbIuFqDRo5wklmvqpx7pPztH/hXOHOM1XzzHR26SVYrPNH3vhQTnCvY6HiRLnhDg4kLnyGqWmCCfuDedN9flYl/443qwbRg3uL20doooeQG91zlNxJ8eSuJ2vynvmvH64u3n4vOY59ysVzGoYBNSoMC+V6jPpdQRo15RmVOBcPUZM3ZCsdIaChd+zQo+fV08WoT/K8BPnCGy4Cunk5XYITgF0WPvcZwTYSOfDgZws+/qow9k+VIJ/eLFd7sRPLxZtDEEd4vg5TzZZ/2Gw+a1qFcmElBFiWqngoNnidO+Oame8jwkIxMhOVd42MXg3vCvSYC957GTOhpudyBRIs9tMYqU7irFdQa6HN21F+O3FpakZ2Y7Mic18rq16Hwdp/gDe9ILOi4atc/IyZi0Riu 5BI8syLP UNd9YGGe7fCw2SnKhEcOnvAT5VTm1ThCEFBgizywB+PUMN+Uq51zEj1h1GC/lohh00PklSk2+HW2e3odaHefgK3+Dguo/dH6rRNMH7LE3XDK0mPsx4qgpGqBdW0DdQc2RBYFU6Hx9K1cbpncL1sMk3+NnZ3aWA09L0qRNNvye9Mx3/9FHgZTRXaY+WcFAQ8sVEIhXTId8MJUT+ujET9JEErvZ0B3mQXMvqoXseY2PyBP7nY32UyceBkoWlh5rEq35nbSDxXtBKU/I/4KDP9rXi6zXa/pQzFEr8o8bMeMxIyC5LiRvrokIL0m3zObVe0uON7XQFZKy/LCp+CStwyaQtc3Zeye4pD0cR5kAddF7qEEdFIf6iVN44EfCiMydzMcAepaUGTuYW9E3QMlbF8YpezdzHQl6U6KDiEYUt3VVOJNPs8MTlT+wv2koKtpi13Hckjr/15zAhip1kswBNfGBx5YFoeTmRZphAU+KV3KGBnOJxqkz9HlI1SW3wJJyssU9fzobUEmlZTnQAKU9Ags2+7DQv8LGjEJYPWjDTC6EPrHYEfFw5GhOX0cEe22CTDrBzt1n+zciC5uglhREfs1sE27DbfQg8ze/S4nM X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Currently we have some tests for rbtree related data structure, e.g. rbtree, augmented rbtree, interval tree, in lib/ as kernel module. To facilitate the test and debug for those fundamental data structure, this patch enable those tests in userland. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- tools/include/asm/timex.h | 13 +++++ tools/include/linux/container_of.h | 5 ++ tools/include/linux/math64.h | 5 ++ tools/include/linux/moduleparam.h | 7 +++ tools/include/linux/prandom.h | 51 ++++++++++++++++++ tools/include/linux/slab.h | 1 + tools/lib/slab.c | 16 ++++++ tools/testing/rbtree/Makefile | 31 +++++++++++ tools/testing/rbtree/interval_tree_test.c | 53 +++++++++++++++++++ tools/testing/rbtree/rbtree_test.c | 45 ++++++++++++++++ tools/testing/rbtree/test.h | 4 ++ tools/testing/shared/interval_tree-shim.c | 5 ++ tools/testing/shared/linux/interval_tree.h | 7 +++ .../shared/linux/interval_tree_generic.h | 2 + tools/testing/shared/linux/rbtree.h | 8 +++ tools/testing/shared/linux/rbtree_augmented.h | 7 +++ tools/testing/shared/linux/rbtree_types.h | 8 +++ tools/testing/shared/rbtree-shim.c | 6 +++ 18 files changed, 274 insertions(+) create mode 100644 tools/include/asm/timex.h create mode 100644 tools/include/linux/container_of.h create mode 100644 tools/include/linux/moduleparam.h create mode 100644 tools/include/linux/prandom.h create mode 100644 tools/testing/rbtree/Makefile create mode 100644 tools/testing/rbtree/interval_tree_test.c create mode 100644 tools/testing/rbtree/rbtree_test.c create mode 100644 tools/testing/rbtree/test.h create mode 100644 tools/testing/shared/interval_tree-shim.c create mode 100644 tools/testing/shared/linux/interval_tree.h create mode 100644 tools/testing/shared/linux/interval_tree_generic.h create mode 100644 tools/testing/shared/linux/rbtree.h create mode 100644 tools/testing/shared/linux/rbtree_augmented.h create mode 100644 tools/testing/shared/linux/rbtree_types.h create mode 100644 tools/testing/shared/rbtree-shim.c diff --git a/tools/include/asm/timex.h b/tools/include/asm/timex.h new file mode 100644 index 000000000000..5adfe3c6d326 --- /dev/null +++ b/tools/include/asm/timex.h @@ -0,0 +1,13 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __TOOLS_LINUX_ASM_TIMEX_H +#define __TOOLS_LINUX_ASM_TIMEX_H + +#include + +#define cycles_t clock_t + +static inline cycles_t get_cycles(void) +{ + return clock(); +} +#endif // __TOOLS_LINUX_ASM_TIMEX_H diff --git a/tools/include/linux/container_of.h b/tools/include/linux/container_of.h new file mode 100644 index 000000000000..9adce874bea9 --- /dev/null +++ b/tools/include/linux/container_of.h @@ -0,0 +1,5 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_CONTAINER_OF_H +#define _TOOLS_LINUX_CONTAINER_OF_H + +#endif /* _TOOLS_LINUX_CONTAINER_OF_H */ diff --git a/tools/include/linux/math64.h b/tools/include/linux/math64.h index 4ad45d5943dc..8a67d478bf19 100644 --- a/tools/include/linux/math64.h +++ b/tools/include/linux/math64.h @@ -72,4 +72,9 @@ static inline u64 mul_u64_u64_div64(u64 a, u64 b, u64 c) } #endif +static inline u64 div_u64(u64 dividend, u32 divisor) +{ + return dividend / divisor; +} + #endif /* _LINUX_MATH64_H */ diff --git a/tools/include/linux/moduleparam.h b/tools/include/linux/moduleparam.h new file mode 100644 index 000000000000..4c4d05bef0cb --- /dev/null +++ b/tools/include/linux/moduleparam.h @@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_MODULE_PARAMS_H +#define _TOOLS_LINUX_MODULE_PARAMS_H + +#define MODULE_PARM_DESC(parm, desc) + +#endif // _TOOLS_LINUX_MODULE_PARAMS_H diff --git a/tools/include/linux/prandom.h b/tools/include/linux/prandom.h new file mode 100644 index 000000000000..b745041ccd6a --- /dev/null +++ b/tools/include/linux/prandom.h @@ -0,0 +1,51 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __TOOLS_LINUX_PRANDOM_H +#define __TOOLS_LINUX_PRANDOM_H + +#include + +struct rnd_state { + __u32 s1, s2, s3, s4; +}; + +/* + * Handle minimum values for seeds + */ +static inline u32 __seed(u32 x, u32 m) +{ + return (x < m) ? x + m : x; +} + +/** + * prandom_seed_state - set seed for prandom_u32_state(). + * @state: pointer to state structure to receive the seed. + * @seed: arbitrary 64-bit value to use as a seed. + */ +static inline void prandom_seed_state(struct rnd_state *state, u64 seed) +{ + u32 i = ((seed >> 32) ^ (seed << 10) ^ seed) & 0xffffffffUL; + + state->s1 = __seed(i, 2U); + state->s2 = __seed(i, 8U); + state->s3 = __seed(i, 16U); + state->s4 = __seed(i, 128U); +} + +/** + * prandom_u32_state - seeded pseudo-random number generator. + * @state: pointer to state structure holding seeded state. + * + * This is used for pseudo-randomness with no outside seeding. + * For more random results, use get_random_u32(). + */ +static inline u32 prandom_u32_state(struct rnd_state *state) +{ +#define TAUSWORTHE(s, a, b, c, d) (((s & c) << d) ^ (((s << a) ^ s) >> b)) + state->s1 = TAUSWORTHE(state->s1, 6U, 13U, 4294967294U, 18U); + state->s2 = TAUSWORTHE(state->s2, 2U, 27U, 4294967288U, 2U); + state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U, 7U); + state->s4 = TAUSWORTHE(state->s4, 3U, 12U, 4294967168U, 13U); + + return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4); +} +#endif // __TOOLS_LINUX_PRANDOM_H diff --git a/tools/include/linux/slab.h b/tools/include/linux/slab.h index 51b25e9c4ec7..c87051e2b26f 100644 --- a/tools/include/linux/slab.h +++ b/tools/include/linux/slab.h @@ -12,6 +12,7 @@ void *kmalloc(size_t size, gfp_t gfp); void kfree(void *p); +void *kmalloc_array(size_t n, size_t size, gfp_t gfp); bool slab_is_available(void); diff --git a/tools/lib/slab.c b/tools/lib/slab.c index 959997fb0652..981a21404f32 100644 --- a/tools/lib/slab.c +++ b/tools/lib/slab.c @@ -36,3 +36,19 @@ void kfree(void *p) printf("Freeing %p to malloc\n", p); free(p); } + +void *kmalloc_array(size_t n, size_t size, gfp_t gfp) +{ + void *ret; + + if (!(gfp & __GFP_DIRECT_RECLAIM)) + return NULL; + + ret = calloc(n, size); + uatomic_inc(&kmalloc_nr_allocated); + if (kmalloc_verbose) + printf("Allocating %p from calloc\n", ret); + if (gfp & __GFP_ZERO) + memset(ret, 0, n * size); + return ret; +} diff --git a/tools/testing/rbtree/Makefile b/tools/testing/rbtree/Makefile new file mode 100644 index 000000000000..bac6931b499d --- /dev/null +++ b/tools/testing/rbtree/Makefile @@ -0,0 +1,31 @@ +# SPDX-License-Identifier: GPL-2.0 + +.PHONY: clean + +TARGETS = rbtree_test interval_tree_test +OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o +DEPS = ../../../include/linux/rbtree.h \ + ../../../include/linux/rbtree_types.h \ + ../../../include/linux/rbtree_augmented.h \ + ../../../include/linux/interval_tree.h \ + ../../../include/linux/interval_tree_generic.h \ + ../../../lib/rbtree.c \ + ../../../lib/interval_tree.c + +targets: $(TARGETS) + +include ../shared/shared.mk + +ifeq ($(DEBUG), 1) + CFLAGS += -g +endif + +$(TARGETS): $(OFILES) + +rbtree-shim.o: $(DEPS) +rbtree_test.o: ../../../lib/rbtree_test.c +interval_tree-shim.o: $(DEPS) +interval_tree_test.o: ../../../lib/interval_tree_test.c + +clean: + $(RM) $(TARGETS) *.o generated/* diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c new file mode 100644 index 000000000000..f1c41f5e28ba --- /dev/null +++ b/tools/testing/rbtree/interval_tree_test.c @@ -0,0 +1,53 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * interval_tree.c: Userspace Interval Tree test-suite + * Copyright (c) 2025 Wei Yang + */ +#include +#include +#include "shared.h" + +#include "../../../lib/interval_tree_test.c" + +int usage(void) +{ + fprintf(stderr, "Userland interval tree test cases\n"); + fprintf(stderr, " -n: Number of nodes in the interval tree\n"); + fprintf(stderr, " -p: Number of iterations modifying the tree\n"); + fprintf(stderr, " -q: Number of searches to the interval tree\n"); + fprintf(stderr, " -s: Number of iterations searching the tree\n"); + fprintf(stderr, " -a: Searches will iterate all nodes in the tree\n"); + fprintf(stderr, " -m: Largest value for the interval's endpoint\n"); + exit(-1); +} + +void interval_tree_tests(void) +{ + interval_tree_test_init(); + interval_tree_test_exit(); +} + +int main(int argc, char **argv) +{ + int opt; + + while ((opt = getopt(argc, argv, "n:p:q:s:am:")) != -1) { + if (opt == 'n') + nnodes = strtoul(optarg, NULL, 0); + else if (opt == 'p') + perf_loops = strtoul(optarg, NULL, 0); + else if (opt == 'q') + nsearches = strtoul(optarg, NULL, 0); + else if (opt == 's') + search_loops = strtoul(optarg, NULL, 0); + else if (opt == 'a') + search_all = true; + else if (opt == 'm') + max_endpoint = strtoul(optarg, NULL, 0); + else + usage(); + } + + interval_tree_tests(); + return 0; +} diff --git a/tools/testing/rbtree/rbtree_test.c b/tools/testing/rbtree/rbtree_test.c new file mode 100644 index 000000000000..c723e751b9a9 --- /dev/null +++ b/tools/testing/rbtree/rbtree_test.c @@ -0,0 +1,45 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * rbtree_test.c: Userspace Red Black Tree test-suite + * Copyright (c) 2025 Wei Yang + */ +#include +#include +#include +#include "shared.h" + +#include "../../../lib/rbtree_test.c" + +int usage(void) +{ + fprintf(stderr, "Userland rbtree test cases\n"); + fprintf(stderr, " -n: Number of nodes in the rb-tree\n"); + fprintf(stderr, " -p: Number of iterations modifying the rb-tree\n"); + fprintf(stderr, " -c: Number of iterations modifying and verifying the rb-tree\n"); + exit(-1); +} + +void rbtree_tests(void) +{ + rbtree_test_init(); + rbtree_test_exit(); +} + +int main(int argc, char **argv) +{ + int opt; + + while ((opt = getopt(argc, argv, "n:p:c:")) != -1) { + if (opt == 'n') + nnodes = strtoul(optarg, NULL, 0); + else if (opt == 'p') + perf_loops = strtoul(optarg, NULL, 0); + else if (opt == 'c') + check_loops = strtoul(optarg, NULL, 0); + else + usage(); + } + + rbtree_tests(); + return 0; +} diff --git a/tools/testing/rbtree/test.h b/tools/testing/rbtree/test.h new file mode 100644 index 000000000000..f1f1b545b55a --- /dev/null +++ b/tools/testing/rbtree/test.h @@ -0,0 +1,4 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +void rbtree_tests(void); +void interval_tree_tests(void); diff --git a/tools/testing/shared/interval_tree-shim.c b/tools/testing/shared/interval_tree-shim.c new file mode 100644 index 000000000000..122e74756571 --- /dev/null +++ b/tools/testing/shared/interval_tree-shim.c @@ -0,0 +1,5 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* Very simple shim around the interval tree. */ + +#include "../../../lib/interval_tree.c" diff --git a/tools/testing/shared/linux/interval_tree.h b/tools/testing/shared/linux/interval_tree.h new file mode 100644 index 000000000000..129faf9f1d0a --- /dev/null +++ b/tools/testing/shared/linux/interval_tree.h @@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_INTERVAL_TREE_H +#define _TEST_INTERVAL_TREE_H + +#include "../../../../include/linux/interval_tree.h" + +#endif /* _TEST_INTERVAL_TREE_H */ diff --git a/tools/testing/shared/linux/interval_tree_generic.h b/tools/testing/shared/linux/interval_tree_generic.h new file mode 100644 index 000000000000..34cd654bee61 --- /dev/null +++ b/tools/testing/shared/linux/interval_tree_generic.h @@ -0,0 +1,2 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#include "../../../../include/linux/interval_tree_generic.h" diff --git a/tools/testing/shared/linux/rbtree.h b/tools/testing/shared/linux/rbtree.h new file mode 100644 index 000000000000..d644bb7360bf --- /dev/null +++ b/tools/testing/shared/linux/rbtree.h @@ -0,0 +1,8 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_H +#define _TEST_RBTREE_H + +#include +#include "../../../../include/linux/rbtree.h" + +#endif /* _TEST_RBTREE_H */ diff --git a/tools/testing/shared/linux/rbtree_augmented.h b/tools/testing/shared/linux/rbtree_augmented.h new file mode 100644 index 000000000000..ad138fcf6652 --- /dev/null +++ b/tools/testing/shared/linux/rbtree_augmented.h @@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_AUGMENTED_H +#define _TEST_RBTREE_AUGMENTED_H + +#include "../../../../include/linux/rbtree_augmented.h" + +#endif /* _TEST_RBTREE_AUGMENTED_H */ diff --git a/tools/testing/shared/linux/rbtree_types.h b/tools/testing/shared/linux/rbtree_types.h new file mode 100644 index 000000000000..194194a5bf92 --- /dev/null +++ b/tools/testing/shared/linux/rbtree_types.h @@ -0,0 +1,8 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_TYPES_H +#define _TEST_RBTREE_TYPES_H + +#include "../../../../include/linux/rbtree_types.h" + +#endif /* _TEST_RBTREE_TYPES_H */ + diff --git a/tools/testing/shared/rbtree-shim.c b/tools/testing/shared/rbtree-shim.c new file mode 100644 index 000000000000..7692a993e5f1 --- /dev/null +++ b/tools/testing/shared/rbtree-shim.c @@ -0,0 +1,6 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* Very simple shim around the rbtree. */ + +#include "../../../lib/rbtree.c" +