From patchwork Tue Mar 4 01:19:47 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13999760 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 652F6C282D1 for ; Tue, 4 Mar 2025 01:20:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 48E6E280002; Mon, 3 Mar 2025 20:20:40 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 43E35280001; Mon, 3 Mar 2025 20:20:40 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E0A0280002; Mon, 3 Mar 2025 20:20:40 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 0F058280001 for ; Mon, 3 Mar 2025 20:20:40 -0500 (EST) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 7FBE4A4A4C for ; Tue, 4 Mar 2025 01:20:39 +0000 (UTC) X-FDA: 83182113798.10.75A6F79 Received: from mail-ed1-f48.google.com (mail-ed1-f48.google.com [209.85.208.48]) by imf13.hostedemail.com (Postfix) with ESMTP id 32A0620003 for ; Tue, 4 Mar 2025 01:20:36 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GsXPfPlm; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741051237; a=rsa-sha256; cv=none; b=Xykq4IoT0oOiNd9JPuUot88lZJLUKuFvBYWQ0W5q8Y0xMPx3s8Wok7LJqerR0ycFtqBPkf Pq/YQOqBEYMKPw0OjThdsAbPjJeN4yJaKDzGr2ldmOdKAnKmkKLrnOnb0Jo4Ng1FQc7Abu Nd2IIG9ITG4xYlfbA5h/ctG8mtSip58= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GsXPfPlm; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1741051237; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=bm4OptN4vaLvm8m6h9gJ+k3MbpCZ+m7z5hS8YgozQEw=; b=vhpegJGy6UU1jp8qk3QgIOHEIimVK7mLG3czeR9JJI2xG6WzSxXOkAZ61oBdjvNqSEskxH zTsrqK72xZJHnYRo8sQusVLUtBSEJcJ9guRHdZRW2eX8wufT34eVqBRRZY44gGBup2sY0n oROTSyR742mg2/5Nq+erCHc7pyaJXfA= Received: by mail-ed1-f48.google.com with SMTP id 4fb4d7f45d1cf-5e53b3fa7daso3046007a12.2 for ; Mon, 03 Mar 2025 17:20:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741051236; x=1741656036; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=bm4OptN4vaLvm8m6h9gJ+k3MbpCZ+m7z5hS8YgozQEw=; b=GsXPfPlmyCIQbMnjGHJ9DQ1YJPxUX4LYRmIUQhgVFFDLH30lfqQZhpBmpD372lyDp9 GsvaOpHskZ7rgcjsA7QZzDPKpR4F9MzAx0l+6mynknDIwuKWsWuN98PNiDccAeaptqmW 5THa6YJ+MlWTQ1t9YCU7DMbDTxFsX1K6zoBIu0dSIco5usnlKed8ldxMBjS7lJfbiQUS AeZRyezllG3HQ92NlTPLTOsrGWhv+8X68AJbxPU+ipDq/yX3M59QqRRobdZxJjB7SecG Y1kli/I3I6VBT7s7hjeKj86uMHNvHFK6itkqzv5aMz94bAfv+SyRLAcqREaK9BtfNyTc M1yA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741051236; x=1741656036; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=bm4OptN4vaLvm8m6h9gJ+k3MbpCZ+m7z5hS8YgozQEw=; b=e9uOq9sG2rtokVAR1044iNHSVRV5Vsx6UcquhveqmYjopnvxroFkv5MdzkDcgio5Vr H03ckEUljZDBGRlTwxRY6M/9DGUcBAWfnnBJNQAesYWBOyE1klE5NPIp7MncbTR5iurZ +NH8vILzfcckZV9RtrZLrckusmsnj/sUiraPqMga7uS7i4Pb2JNoCCi5IJFqnPjJe9zb boEDV/n3CTUB93VicyQSKd59ODNzaoF1vuGWS7kVb0q6kObO7A7Uvbh0QpSFRG5lCsfs 01AFLJXMiaAlSMDY6zIzQVVAs/CxiKYgsogXR2jvo6AMkFAYIHQOLbMf0+5EjTlAj9MP JaaQ== X-Forwarded-Encrypted: i=1; AJvYcCX75c4i8PgcO67gyz3yANU5PbYB+n+1ZnZ6hkH9AjCQVRYPqekTu8dSNEvq8wFlAyIkSvjmkDfD7w==@kvack.org X-Gm-Message-State: AOJu0Yx+puFP60QcIFpdWVdjZLcHwwQHRvBsf0AVZY4TjrX9hOJuzRV3 1j1TGWN6uefyzudOTMekGAb2xGeqwRzpT/uaTkUJbkCvf3sH0XmG X-Gm-Gg: ASbGncv7GSEkEIjdXQwz+158m9Luiq7S+vZ+Ravv9uvCXgqDM5/wMEkhlFZdBrwVe1z kPxLkpj5fgl2Lw54N2HbCiU1oEJ7LmFfnbOd52D8Q5AmScPOC98TpYv5Jj7PAP/83CCiARe+TYm lhRAF0IMnPeOXhF3Znlbd8SOG65xq7VMuEoOpKCaL0A61zlEwvfwNmIp2AbVHagFuNzEHE7HztJ QG0L9W4bnrv9P4OJG6xDSvzroHNMQ/Qd6v6FCfnlzBWJgxi3W59Ky5KB9GMx815LHv+Mp8K7uMG XE5Dke92dvh7YQ8mN+YAFcjeXk19rp6NNXZ9vZi+gjYR X-Google-Smtp-Source: AGHT+IEwZ9eOzbVIFKHq0uoYI5tILJ061IQXBKRedVHXC01BrDQcvUWiTgfDruhaaI8EMPkd+QHCWA== X-Received: by 2002:a17:907:7f12:b0:ab3:4c32:aa6c with SMTP id a640c23a62f3a-abf25fc618bmr1823299366b.20.1741051235579; Mon, 03 Mar 2025 17:20:35 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abf0c7c0faasm891284666b.179.2025.03.03.17.20.33 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 03 Mar 2025 17:20:34 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [PATCH 2/7] lib/rbtree: split tests Date: Tue, 4 Mar 2025 01:19:47 +0000 Message-Id: <20250304011952.29182-3-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250304011952.29182-1-richard.weiyang@gmail.com> References: <20250304011952.29182-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: 32A0620003 X-Stat-Signature: hnxqhktq4ymhp4paroywr34apsoon53h X-Rspam-User: X-Rspamd-Server: rspam05 X-HE-Tag: 1741051236-432738 X-HE-Meta: U2FsdGVkX18OHQB+zXbIz/RH3WVneSxZmDeNZVuC68wELvrp8Jk6pZJbcR0JKNQSdo32s6nIQct6yc24G7OHthTuy97QOToY5bwn3caQyb4oS0C2PQz7xJzZq17uZDaB4vg2Yo4gdjrV7sffY40g02DPlo0R0jHk0L2MqAZuRVtu/fn9D1/kXzp1PhiRGbdhuMkIr1dtoyiDPVx8aOO1vymQBavOYLELr8kMAA8dRlekYGTAkI6KJd455AHMo7AkhUV9ET0y6370R+08kR08qa4CTEcrnsnpiGQK8umDY5YGz/C0duv5Gv1jRk+xFZDWa4AkJPcNxfiG3YAYfyhxyIxztDN6EWMp5d0NQmvP0PfBwYVxSonNjz4Bt1cypDdflRBTR0xuL4XlDMv7DQ2h+wYmH8oF0uNpF8+Vsr0x6EzCtXvJh8vBssuaANs0maSYZxlHFiBf2zBMo1t7s5WMaRk98cQFuV+zwxaK2b8MA8tokuLe/bdJBKQUOQU+6F3oVPpW11jDniwI9PnAWtdMOBJjjpfDweqfPiHnGKTzvrd7Cxe5QxjqjgOGsqQBZdCGZ/GJViErxRzH/oL0dEDm47ycADcjTkVGVdg40ABNfyOp/x5/oUZE26hTVC4VwO1F3927rkWUGlDQvm+xlMH4+GtYEpSorfxVZgQ/x1k0YtzR5hRLsg+DajS0JYaqhTnlq/btdfBpSD64AKHVhswp3h7Dkux1BcbjYC8KupWnS+aw+C1gH+VhH4zekD1fpIT8TRTCS0D4OtjL5EWq3YCEpq8xb2I5gHca+afmWTluu7UZ/J5LMVz0kxJQZ1cCip1jNICCyoKBkInOK7ehv7qKGn838ZXy2hrhd2d/JS4/z6ic+EA0XKrFqllxPsfOyN31/fjS7v5FNwi1I0dom2FHAtHIlW+0gH0zrUWQVsGj5YUfYXC65loT91g3v5uSeGG+2JYSxe7CRlabCDBdiGG Vw54BHgb Km/O5elpR8Xv7MJO5oXITBBTkvTNi+Uk7dUBCjgftOMH+T2OwBeGiWkuInjUXakM4SETKAOD8HEKo3wImnd2H998ZObR5liXiduBbDxw6wN74hwSNRoqDbNuBdwAIVswCIQkcCoq0WPGwsG0n03ZwIb39odSjnME/Nb2dHH7dYAYQXBbiEdX3II1M8HAGtTWJr8OPtvqBKCCJhRHtLil/FTtYV+mZzRi7ULFKMdxIeNu3AZZhN0KRWe4QhOI964IofECre7JRFETboeoh5sV2jDH2zNj+vXK6F5hEuFgHs32LTy7MOE74Zh5wmrDwsB0wNqiueKb2FgpdGmo917Chv8E+x/OXZGwem/XMVh+LhJiy6+6tYhrlbM4r5Tgs8aDWA6oRD3Y8xYUVPiwYv0h7Z2fcheIF3UweCAsdq66M5iuvYZqyrUh6vxPBZxrZZ1M++W4dr5Y2S04CrvJpIptY25nTiMLZfgQ5xC8JPEPz7VLLwNzb3aCGhOm2JCLHX1C4uJ0kNPobOOvCZHBGo+mTacnwx3CRqXGB9KKbKRrFowJ17LrdEu3X28h/rnfHtzhMZLE47EeDb0snX0smG+cpF+Ww8Qc95vOfdEdW X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Current tests are gathered in one big function. Split tests into its own function for better understanding and also it is a preparation for introducing new test cases. Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Michel Lespinasse --- lib/interval_tree_test.c | 50 +++++++++++++++++++++++++++++----------- lib/rbtree_test.c | 29 ++++++++++++++++++----- 2 files changed, 59 insertions(+), 20 deletions(-) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 837064b83a6c..12880d772945 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -59,26 +59,13 @@ static void init(void) queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint; } -static int interval_tree_test_init(void) +static int basic_check(void) { int i, j; - unsigned long results; cycles_t time1, time2, time; - nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), - GFP_KERNEL); - if (!nodes) - return -ENOMEM; - - queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL); - if (!queries) { - kfree(nodes); - return -ENOMEM; - } - printk(KERN_ALERT "interval tree insert/remove"); - prandom_seed_state(&rnd, 3141592653589793238ULL); init(); time1 = get_cycles(); @@ -96,8 +83,19 @@ static int interval_tree_test_init(void) time = div_u64(time, perf_loops); printk(" -> %llu cycles\n", (unsigned long long)time); + return 0; +} + +static int search_check(void) +{ + int i, j; + unsigned long results; + cycles_t time1, time2, time; + printk(KERN_ALERT "interval tree search"); + init(); + for (j = 0; j < nnodes; j++) interval_tree_insert(nodes + j, &root); @@ -120,6 +118,30 @@ static int interval_tree_test_init(void) printk(" -> %llu cycles (%lu results)\n", (unsigned long long)time, results); + for (j = 0; j < nnodes; j++) + interval_tree_remove(nodes + j, &root); + + return 0; +} + +static int interval_tree_test_init(void) +{ + nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node), + GFP_KERNEL); + if (!nodes) + return -ENOMEM; + + queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL); + if (!queries) { + kfree(nodes); + return -ENOMEM; + } + + prandom_seed_state(&rnd, 3141592653589793238ULL); + + basic_check(); + search_check(); + kfree(queries); kfree(nodes); diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 8655a76d29a1..b0e0b26506cb 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -239,19 +239,14 @@ static void check_augmented(int nr_nodes) } } -static int __init rbtree_test_init(void) +static int basic_check(void) { int i, j; cycles_t time1, time2, time; struct rb_node *node; - nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL); - if (!nodes) - return -ENOMEM; - printk(KERN_ALERT "rbtree testing"); - prandom_seed_state(&rnd, 3141592653589793238ULL); init(); time1 = get_cycles(); @@ -343,6 +338,14 @@ static int __init rbtree_test_init(void) check(0); } + return 0; +} + +static int augmented_check(void) +{ + int i, j; + cycles_t time1, time2, time; + printk(KERN_ALERT "augmented rbtree testing"); init(); @@ -390,6 +393,20 @@ static int __init rbtree_test_init(void) check_augmented(0); } + return 0; +} + +static int __init rbtree_test_init(void) +{ + nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL); + if (!nodes) + return -ENOMEM; + + prandom_seed_state(&rnd, 3141592653589793238ULL); + + basic_check(); + augmented_check(); + kfree(nodes); return -EAGAIN; /* Fail will directly unload the module */