From mboxrd@z Thu Jan 1 00:00:00 1970 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 213B8C001DE for ; Mon, 31 Jul 2023 12:32:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6EB46280038; Mon, 31 Jul 2023 08:32:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 69BD5280023; Mon, 31 Jul 2023 08:32:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 58A78280038; Mon, 31 Jul 2023 08:32:51 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 49955280023 for ; Mon, 31 Jul 2023 08:32:51 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 18EB4B1F1E for ; Mon, 31 Jul 2023 12:32:51 +0000 (UTC) X-FDA: 81071846142.15.3BC6D9F Received: from mail-il1-f181.google.com (mail-il1-f181.google.com [209.85.166.181]) by imf12.hostedemail.com (Postfix) with ESMTP id 38D534001D for ; Mon, 31 Jul 2023 12:32:48 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=jzUbqYIt; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.166.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690806769; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=M82ZdWiowDuFGINOioxht4VyUsVaoAlVTe7iYwfL+EY=; b=AgJNMuagEz498PxOWU+S2CuJp/Xf7qlhKvzyNXw5NvhfRVA5i/QFhlzIehNi/0jZqTnRLg BzrvvYJsojM4qnpMie873UdUAorwqKAjDudpGylXiSXrC1gcSGPV68EGJbXOMv/TfUBPaC BU70zuvKk9gSzviPRehkqrAz0xRZ0b0= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=jzUbqYIt; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.166.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690806769; a=rsa-sha256; cv=none; b=U4K+yECkoxczTt5OzN7G8SOqj9wNrgwFgtshn0+qAYYvp3FktK6zsrMDTSVJkIEe0ZerYX YZZtP94XUiwYdw6JT3o2u9kZOmDwj5D0BjFYdUWMkUHO+7Cx9iKW51PY4qy0IU344aM7+N w/Wawgkoeqh0JIweDgjcgOS29ky5zo0= Received: by mail-il1-f181.google.com with SMTP id e9e14a558f8ab-3490cf176feso10713095ab.0 for ; Mon, 31 Jul 2023 05:32:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690806768; x=1691411568; h=content-transfer-encoding:in-reply-to:cc:from:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=M82ZdWiowDuFGINOioxht4VyUsVaoAlVTe7iYwfL+EY=; b=jzUbqYItuP9YFcB/tb2GFTKwveIsFjgvgxT2X14M7kdofmVGaSkN/Kgech4ITWRdYm hvCkCAVFZwvUUSNlbIjm2QyFxXJES2guD/oDfWsZGqOxcxuYs5/wC0Vx6ZgRdFQ+pIT4 YAimzTigd7Ic9pmG28jLiKXfDVVdduoEZ8PkrTL77rcIjOP+80lW+jNBmF9FtBymy8Pf VdpQUO3iOvXgUzM4CcKgh43qQ2S613H5cT2gwYAoHza3Tt9f21SzoZr6glkM9m/LDqZl d51Y7Skn8D34TSlc4TbvfSPhEoYXyKly6H7CfFBd9v/OqwsJUwsJFX2xjNF+ANuLLjG/ YUSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690806768; x=1691411568; h=content-transfer-encoding:in-reply-to:cc:from:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=M82ZdWiowDuFGINOioxht4VyUsVaoAlVTe7iYwfL+EY=; b=V1sN0a6FIvrSZgnNGiDaOX2kpdntyVmiYgfznSwK0qRmO7Bb1cOuzpj5YE446Aq038 hGq8+CFnAKYvSg8LeFx2dgPsQO4zWaP0EWYXK9sXo6Tn9iIy+Fj+lPLlOJw/9cimmWDd oJUFrFxS/0Cza8CE2iBPjsrK53H9oX4lKLS5v/JfA+3W4v6os3n3zbG/FPy7IAH1GAHE YlUVHAVik/2SMPZIXMPrwYgx3OfTDOCNJkXHhFXlvYne/oL5aM1R+BaTWJCwVq6GUK5e KUy0H7cuM+/tKKsiwQDIwgpPED61Embwtsw8vy2XQporIDyQHJoSqxCpkDMLp6OShd5M R9OA== X-Gm-Message-State: ABy/qLbn5SSy1RvwP7wIF4/1NAKD+LQ1wCKV7YxJKrokbtEu4gSVOyFM jWgyqCZDcslXeXR4Z+lcJCbWIA== X-Google-Smtp-Source: APBJJlGwNo86te08ep7jpQMQqoMESzoPDWpWBxvTZh6sPoZa7hVi8pEFmx+2RZS4UZzgQFprT3Mfhg== X-Received: by 2002:a05:6e02:12ad:b0:348:cfad:1608 with SMTP id f13-20020a056e0212ad00b00348cfad1608mr7556440ilr.5.1690806767771; Mon, 31 Jul 2023 05:32:47 -0700 (PDT) Received: from [10.90.34.137] ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id gj2-20020a17090b108200b00267fff8e024sm7773341pjb.30.2023.07.31.05.32.42 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 31 Jul 2023 05:32:47 -0700 (PDT) Message-ID: <248b946a-f42f-6b59-147c-c7dbbe03ef0d@bytedance.com> Date: Mon, 31 Jul 2023 20:32:40 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.13.1 Subject: Re: [PATCH 05/11] maple_tree: Add test for mt_dup() To: "Liam R. Howlett" References: <20230726080916.17454-1-zhangpeng.00@bytedance.com> <20230726080916.17454-6-zhangpeng.00@bytedance.com> <20230726160607.eoobd4dyvryfb25a@revolver> From: Peng Zhang Cc: Peng Zhang , linux-doc@vger.kernel.org, linux-mm@kvack.org, avagin@gmail.com, npiggin@gmail.com, mathieu.desnoyers@efficios.com, peterz@infradead.org, michael.christie@oracle.com, surenb@google.com, brauner@kernel.org, willy@infradead.org, corbet@lwn.net, linux-fsdevel@vger.kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org In-Reply-To: <20230726160607.eoobd4dyvryfb25a@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 38D534001D X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: fzadgcan8mnyfdrwo1zi6ayis3jo8a8a X-HE-Tag: 1690806768-299860 X-HE-Meta: U2FsdGVkX1/qtcJoe6PZzV9Pp6tbQxYvXuVrtdqX1JS/lyXwR4gKQH/3DyB3fMYckNVXuP1gcl+m4YKECJvGYA88wMykHcJPKZyaqII5Q0hHULL6AIR24Wq3aiGVH4riRboqqLKJUUT/AS+Dj5LPzJLRUHclf8v0t3hvhw4ycTLUhhuB7ptlGGCwBLm3RQWiAMu83P063kVc1E04lX9g3DOAFdnSlx9hUIVhzTPpWH47y8xynzMFmQngtis12pJO7MwQq5gb26zIjgjmOFZWG3SnRmj4sGlTrEbkpPMW5HURI8kiYkxLuejS8TkEHq6kqJM498h2ecogqslwS1fBqTELe1YE44892TT2u7fz9PoF0/nd3gl0VpFqHCT6orxuRM8YXVgUpYlS9+6yCO+FggI2Yjd46PcByVJJQHuA9WwVAek/HWqfqOaFeR4OBu52eJYsKU5W+eGRk0usn2pIWvpgxgMy0YTEM9wG49uOOlZh2iSbFZYUToEx9Y9XT/oL4D16SZMDxpjSHpLwAZY+NwlIx4UpKB5fS77yrY3STEVGumt0J/Pfd5TsQXE95/urxUnEz+Ob7gPkyX83XmeTehUE6cWd+xylm0cbXOoMpQMAybQsOh82Q52nIzjUCNkI+ZG46TxcLvbaso0wvNnjgVgLx/Tflb6eG2HtCy+o6pDv4eT6gsPeXXQ5PPh6WdYhjnvt2NtPCtQHTBe9O0kzJrOTkVbhPZkeqLRbDydXM6FQeRIF0v/1uIkpz8Ib6w3k0lI1u1x/uuk3aTlyfv7v4nApLppjtOH8Bn1G98NlOv6MR1jfZZboKXBvwuWrd4AdKBPhkNU7QRT5MlZ10oRIT62L9u2QxiB1WTYyqSTrWWvRVXNJ2FFMdeCqMZ0tfPlYmUgsQAwZseSoL4KdIejbt02y3Nqz/LKAjHnvosrq65Xh7buZQL0uyyi9hrbSuB/tIfgKAVJNPZimuC/RzLa DWFNMB1l AB9B7xwaEKYjdTeYE/9rMzpZ9Doj/y6mg6sDDxdSjchhUc8ovGUpJg8IuygIww6XRk12yxT1WCWEqRaADzGXGM40ALH+ujK9Fz5sknrDIOLJYG1j/Oq2f6h6lH77USJMk2U2YI+PVN1k63R/wIq2P65+4oFVKe38JCDSrbmPqgq1LRjaGu92+JlVcZNfq3/H4Mf+Hy5TKu4gKKxRZ0DNRcfSMVCGWE4Oo63OjgOwyFa7JBoZMw+FItzBtww+TC1S3V77NpkyXGdEQ+pE32dwFqy/mCC9jQ4H0AYT4GcF9ixb0Y+hYVotMxgslluhuR0WMCiXnyKliqhjvM4KoFkwhwFsYu2H30GXzrehF1J4moI1vIj/udVHT6TAlwm/BrDuyROnZypC7r4hM0wROh/ALmcMREYKcQgREOb5uy6u0GlKsYDFKTugyCvAoT4e0vALsL8B9Y6d7aGBmW6g6QDHM0x1CD90GeCPunCJC+XYWo75Q2lVjc6iaXs00UezhxbdMC7O2 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: 在 2023/7/27 00:06, Liam R. Howlett 写道: > * Peng Zhang [230726 04:10]: >> Add test for mt_dup(). >> >> Signed-off-by: Peng Zhang >> --- >> tools/testing/radix-tree/maple.c | 202 +++++++++++++++++++++++++++++++ >> 1 file changed, 202 insertions(+) >> >> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c >> index e5da1cad70ba..3052e899e5df 100644 >> --- a/tools/testing/radix-tree/maple.c >> +++ b/tools/testing/radix-tree/maple.c >> @@ -35857,6 +35857,204 @@ static noinline void __init check_locky(struct maple_tree *mt) >> mt_clear_in_rcu(mt); >> } >> >> +/* >> + * Compare two nodes and return 0 if they are the same, non-zero otherwise. >> + */ >> +static int __init compare_node(struct maple_enode *enode_a, >> + struct maple_enode *enode_b) >> +{ >> + struct maple_node *node_a, *node_b; >> + struct maple_node a, b; >> + void **slots_a, **slots_b; /* Do not use the rcu tag. */ >> + enum maple_type type; >> + int i; >> + >> + if (((unsigned long)enode_a & MAPLE_NODE_MASK) != >> + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { >> + pr_err("The lower 8 bits of enode are different.\n"); >> + return -1; >> + } >> + >> + type = mte_node_type(enode_a); >> + node_a = mte_to_node(enode_a); >> + node_b = mte_to_node(enode_b); >> + a = *node_a; >> + b = *node_b; >> + >> + /* Do not compare addresses. */ >> + if (ma_is_root(node_a) || ma_is_root(node_b)) { >> + a.parent = (struct maple_pnode *)((unsigned long)a.parent & >> + MA_ROOT_PARENT); >> + b.parent = (struct maple_pnode *)((unsigned long)b.parent & >> + MA_ROOT_PARENT); >> + } else { >> + a.parent = (struct maple_pnode *)((unsigned long)a.parent & >> + MAPLE_NODE_MASK); >> + b.parent = (struct maple_pnode *)((unsigned long)b.parent & >> + MAPLE_NODE_MASK); >> + } >> + >> + if (a.parent != b.parent) { >> + pr_err("The lower 8 bits of parents are different. %p %p\n", >> + a.parent, b.parent); >> + return -1; >> + } >> + >> + /* >> + * If it is a leaf node, the slots do not contain the node address, and >> + * no special processing of slots is required. >> + */ >> + if (ma_is_leaf(type)) >> + goto cmp; >> + >> + slots_a = ma_slots(&a, type); >> + slots_b = ma_slots(&b, type); >> + >> + for (i = 0; i < mt_slots[type]; i++) { >> + if (!slots_a[i] && !slots_b[i]) >> + break; >> + >> + if (!slots_a[i] || !slots_b[i]) { >> + pr_err("The number of slots is different.\n"); >> + return -1; >> + } >> + >> + /* Do not compare addresses in slots. */ >> + ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK; >> + ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK; >> + } >> + >> +cmp: >> + /* >> + * Compare all contents of two nodes, including parent (except address), >> + * slots (except address), pivots, gaps and metadata. >> + */ >> + return memcmp(&a, &b, sizeof(struct maple_node)); >> +} >> + >> +/* >> + * Compare two trees and return 0 if they are the same, non-zero otherwise. >> + */ >> +static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b) >> +{ >> + MA_STATE(mas_a, mt_a, 0, 0); >> + MA_STATE(mas_b, mt_b, 0, 0); >> + >> + if (mt_a->ma_flags != mt_b->ma_flags) { >> + pr_err("The flags of the two trees are different.\n"); >> + return -1; >> + } >> + >> + mas_dfs_preorder(&mas_a); >> + mas_dfs_preorder(&mas_b); >> + >> + if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) { >> + if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) { >> + pr_err("One is MAS_ROOT and the other is not.\n"); >> + return -1; >> + } >> + return 0; >> + } >> + >> + while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) { >> + >> + if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) { >> + pr_err("One is MAS_NONE and the other is not.\n"); >> + return -1; >> + } >> + >> + if (mas_a.min != mas_b.min || >> + mas_a.max != mas_b.max) { >> + pr_err("mas->min, mas->max do not match.\n"); >> + return -1; >> + } >> + >> + if (compare_node(mas_a.node, mas_b.node)) { >> + pr_err("The contents of nodes %p and %p are different.\n", >> + mas_a.node, mas_b.node); >> + mt_dump(mt_a, mt_dump_dec); >> + mt_dump(mt_b, mt_dump_dec); >> + return -1; >> + } >> + >> + mas_dfs_preorder(&mas_a); >> + mas_dfs_preorder(&mas_b); >> + } >> + >> + return 0; >> +} >> + >> +static noinline void __init check_mt_dup(struct maple_tree *mt) >> +{ >> + DEFINE_MTREE(new); >> + int i, j, ret, count = 0; >> + >> + /* stored in the root pointer*/ >> + mt_init_flags(&tree, 0); >> + mtree_store_range(&tree, 0, 0, xa_mk_value(0), GFP_KERNEL); >> + mt_dup(&tree, &new, GFP_KERNEL); >> + mt_validate(&new); >> + if (compare_tree(&tree, &new)) >> + MT_BUG_ON(&new, 1); >> + >> + mtree_destroy(&tree); >> + mtree_destroy(&new); >> + >> + for (i = 0; i < 1000; i += 3) { >> + if (i & 1) >> + mt_init_flags(&tree, 0); >> + else >> + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); >> + >> + for (j = 0; j < i; j++) { >> + mtree_store_range(&tree, j * 10, j * 10 + 5, >> + xa_mk_value(j), GFP_KERNEL); >> + } > > Storing in this way is probably not checking a full tree. I think it's > important to check the full tree/full nodes since you have changes to > detect the metadata. I probably won't change the way I check metadata. But is there a way to construct a full tree? All I can think of is to write new code to construct a full tree. > >> + >> + ret = mt_dup(&tree, &new, GFP_KERNEL); >> + MT_BUG_ON(&new, ret != 0); >> + mt_validate(&new); >> + if (compare_tree(&tree, &new)) >> + MT_BUG_ON(&new, 1); >> + >> + mtree_destroy(&tree); >> + mtree_destroy(&new); >> + } >> + >> + /* Test memory allocation failed. */ >> + for (i = 0; i < 1000; i += 3) { >> + if (i & 1) >> + mt_init_flags(&tree, 0); >> + else >> + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); >> + >> + for (j = 0; j < i; j++) { >> + mtree_store_range(&tree, j * 10, j * 10 + 5, >> + xa_mk_value(j), GFP_KERNEL); >> + } >> + >> + mt_set_non_kernel(50); > > It may be worth while allowing more/less than 50 allocations. Actually I have used other values before. I haven't thought of a good value yet, probably a random number in a suitable range would be nice too. > >> + ret = mt_dup(&tree, &new, GFP_NOWAIT); >> + mt_set_non_kernel(0); >> + if (ret != 0) { >> + MT_BUG_ON(&new, ret != -ENOMEM); >> + count++; >> + mtree_destroy(&tree); >> + continue; >> + } >> + >> + mt_validate(&new); >> + if (compare_tree(&tree, &new)) >> + MT_BUG_ON(&new, 1); >> + >> + mtree_destroy(&tree); >> + mtree_destroy(&new); >> + } >> + >> + /* pr_info("mt_dup() fail %d times\n", count); */ >> + BUG_ON(!count); >> +} >> + >> extern void test_kmem_cache_bulk(void); >> >> void farmer_tests(void) >> @@ -35904,6 +36102,10 @@ void farmer_tests(void) >> check_null_expand(&tree); >> mtree_destroy(&tree); >> >> + mt_init_flags(&tree, 0); >> + check_mt_dup(&tree); >> + mtree_destroy(&tree); >> + >> /* RCU testing */ >> mt_init_flags(&tree, 0); >> check_erase_testset(&tree); >> -- >> 2.20.1 >> >>