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 */