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 B7E90CE7A81 for ; Mon, 25 Sep 2023 08:30:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5CB368D0015; Mon, 25 Sep 2023 04:30:25 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 57BFE8D0001; Mon, 25 Sep 2023 04:30:25 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 41C988D0015; Mon, 25 Sep 2023 04:30:25 -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 30DBF8D0001 for ; Mon, 25 Sep 2023 04:30:25 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id F0832160B35 for ; Mon, 25 Sep 2023 08:30:24 +0000 (UTC) X-FDA: 81274447968.25.69E1EC4 Received: from mail-oi1-f174.google.com (mail-oi1-f174.google.com [209.85.167.174]) by imf29.hostedemail.com (Postfix) with ESMTP id 86936120030 for ; Mon, 25 Sep 2023 08:30:22 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=icHTBE4Q; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.174 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=1695630623; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to: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=Lyla+nz0kn6ZrMb94jQzHHryI7zWM3so0OyzevozWXo=; b=s54d9jsfgqdO9IOx2CqcqHz+FT1SHf+OgO6t2ifKtQNhmt91+LIcJBzN2wkHV7+HC4SrAD 4pYyDLz7TMM2Gju/s6ab6gVGQmOSx8gXbNUznb/XTReGnDT8Fj16Con08U0EhE2bIFmtZt 46nSuwaQwOZZFxFUuyxxwN9blvC6vkM= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=icHTBE4Q; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695630623; a=rsa-sha256; cv=none; b=xiVtsEZwnH262GNhEqjFLrxGIX8A3b5L7nbLqgmt0iRMCoFtkMj7XwsGHyc+Sfle2ejrY+ M9ewhjW1irqY1ic0w6X8c0gW3sF5EvIU7db7u8E+B8/hutGeWCucx0cN61tbJzlKeoaCer KfXlasEYQCGvIxSCXNHJGPM2rEArNik= Received: by mail-oi1-f174.google.com with SMTP id 5614622812f47-3adc3d94f66so4065444b6e.1 for ; Mon, 25 Sep 2023 01:30:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695630620; x=1696235420; darn=kvack.org; h=content-transfer-encoding:in-reply-to:from:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=Lyla+nz0kn6ZrMb94jQzHHryI7zWM3so0OyzevozWXo=; b=icHTBE4QHfdiHjFNE3bJYJ/W1yPuPQSOF0clWb3eQ4BMbX/Vf3B8CuexEtJNuCU3e3 ZAJkuBEj+svqDmTGR/j3UvXGWCESZbR9NnKwR6Y2VDjj744Etov0isB9KAa0w+wqstHP ihZ4GAHFVT2E21NNnC/A4M3B0Ti3+RRdr9/1MCB0JQFBDl6Rygq5NRFA+gS4MyT6nxCX NXY5LpKUxMlodnaCmYj3odsZwyhtMVNhr6pOtwdf5AYBTV/H0+KVi/sqs3NBk2SFi6qX 3p9PpqApzV36AWJ8O7j+UayaLCnTIG9sfK7pMGp9wafDKFJHOf9MDCo7qlVQU47uvTro 7yyA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695630620; x=1696235420; h=content-transfer-encoding:in-reply-to: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=Lyla+nz0kn6ZrMb94jQzHHryI7zWM3so0OyzevozWXo=; b=TNsmhcWYXWPTNrCaNIdzaItpKE3JMbackZuQWUQG9FZoZ07tphbRFL5DX6c+D0CtPK 8+LWlEpPaLLZCYsedD8Ou7GhPqBqQwsvbrGQn7U+TjUzUkmvmlK+TUgaorqRSsxowsE2 fKreJ3pozIcLKCRoO8Tu9ClM8jXRxC8jZk83H9jCYDrILTgpZ3WaIuoJvpOmMqk0sAk9 rF9mVR6Pr77tioH4rqm8EWcfBZ9a5IZ7Jh8VlCS3tz8im0T58cS92XSi4a13R6vJZ/AH bOgMCHU+SxyspCv/6qnwb0kvRosmUX/+HMvhKzcSANVZs3n96KITxz6rxZgepZGHYSRQ PzJg== X-Gm-Message-State: AOJu0YxE88oZaTtKAkxzhiwu34HZq/mny6JH+DjYF29DQwtmDObJWlD1 2GIPc8DpwLLs5jCX0WzviFaWWA== X-Google-Smtp-Source: AGHT+IGQLQl8G9S6dKeQbFqnKdlWtZk7mlByiAuo6msAGpQAr9WiX03OMpCXFhCvQ9HtxxftG8+isg== X-Received: by 2002:a54:449a:0:b0:3ad:ffa4:e003 with SMTP id v26-20020a54449a000000b003adffa4e003mr6913467oiv.33.1695630619721; Mon, 25 Sep 2023 01:30:19 -0700 (PDT) Received: from [10.84.144.104] ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id s22-20020a62e716000000b0069023d80e63sm7428786pfh.25.2023.09.25.01.30.13 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 25 Sep 2023 01:30:18 -0700 (PDT) Message-ID: Date: Mon, 25 Sep 2023 16:30:11 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.15.1 Subject: Re: [PATCH v2 3/6] maple_tree: Add test for mtree_dup() To: "Liam R. Howlett" , Peng Zhang , corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> <20230830125654.21257-4-zhangpeng.00@bytedance.com> <20230907201353.jv6bojekvamvdzaj@revolver> <65fbae1b-6253-8a37-2adb-e9c5612ff8e3@bytedance.com> <20230925074439.4tq6kyeivdfesgkr@revolver> From: Peng Zhang In-Reply-To: <20230925074439.4tq6kyeivdfesgkr@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 86936120030 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: 8uh71ufpfz7gagebug8frui9u5b6cjwo X-HE-Tag: 1695630622-87908 X-HE-Meta: U2FsdGVkX18owSpOUhl15FuL7jgXb5qHH2EFn/oVFK1+8uX3KJwa8D9IuzAsL71AeV3UgqvlUUKoHHJEPOdIoTy/4EhgQTz7sgn51wonD4aHWCcjYB2etrM2aTmBTFuSEf4vw0xqmr6Li+iXIhqVizgUWZDaMkxy1dkSvf1EhREuGFhmhSLzn7k6F6I3H0tZi++JkiukILVV7FIGansNko3qvu7eolKmnufzl5h/w8HtI1gPOScqVSskFOGcnOmNnV3j3kpdTV0t+Shjt+cCxYpdGVeGI4kYsD+tP5V/WVv84uxwox75Ek+QM54sQ+fngSJDkwdiuGHlKK1EIf/wu2cTgqaYqAy++OSmZ+4Huk1Be7auk20m7yq1EDG9u/1ZsFg2E6NxspT1r5UqVsHk38Qk1smOd0Chjd4pKmluODBYKjTqztXL1vk9Xyb/t/0bvSf7OyX+U1GW/ZqljxgHNaIf34q0tiFT0xtXw2BBNJyhPuIOrNUu35gXDORGdBOx2ufIv+nndEsX/LqqY1sgX4qlgQeq/6+KtavJBgSPApSHKsoXf1CQdvCLMjlbDDJQAlVBe4PdO2pP/dmLDFeL5AIRrtAiRSzW/DJN2vLjNVVcrXZOJZQE6naeQm4YQ/18G1POZR7mqRi1gfmuOgLTtLZHzledGlCAs137AiRjLC8zHYdI9HFpcO0ri9yCrmVrEjJHQ9VzZcTdByWuoaLN3Llzqb9MjOGxvbUyj+IQwHf1eQYaDYxFcQn8a3Ue3gxM0fMRIez3MCPgKn7ymhkZT5gMYS8SDEuwVsnYr+QJzWOvtEB6qdR9ygjmgabh1AvCjmWHVxx2d8ZtvMAxpPh8DzVFWE5P7G77exxanAMwfIFyIVTfEir5j++gdYo7GNqsqpIVlENrGdebWZAU70nqVys76AEyLq2GQtbQJ4P9p67BbJ7Nzs8M0HUcNI4eufxf0E1QgSnmQX5HgtTzYU2 KIqlepoZ ZaTlnGjj+Amx4HRwonh4rXhXsXkkZKP+cNxeV/sVT1tWUhv6t8XL2E9xfIwTEopjtCs9+WL+DnFs8Cz0EvW4H/gXSaJsyt1q/6YlmpRKSektrxJgHrLPrsETnxjIeXzOLTyqWlskFvlB2fEnb+1/feyiBBzDb20kJw6YCIaIvjNA5Lf6QXquygF1UrurKOy505ouIwaf5rU/DBguAp/TdYD3xQ8tgi0nfclo5usK9Kyh/6eFrRrRuEKusNShClR8BQwLe6YYa+uaB9Y0k/wyxm4sgtXVTvesg5PfmdX/5QnrFkfMAeMx4DtXux7G3juRru+jF539OavCr5YMIfwvgPNDlaK68aQtb1uw3UHP/6OM981hOtEljEvFtqiODYp8gdlVgwdj3VTuPxh+V2bexPKzlamlY4dTM0gCOaihkN/XFZqoP/KsnZm39f+TVjalitaCrsfWt44L1mu9ogG97uaaLJcl/M/c3tw/si6r7uvqC+UFW79kWwz7Ejmz0Q8a7oDri 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/9/25 15:44, Liam R. Howlett 写道: > * Peng Zhang [230925 00:06]: >> >> >> 在 2023/9/8 04:13, Liam R. Howlett 写道: >>> * Peng Zhang [230830 08:57]: >>>> Add test for mtree_dup(). >>> >>> Please add a better description of what tests are included. >>> >>>> >>>> Signed-off-by: Peng Zhang >>>> --- >>>> tools/testing/radix-tree/maple.c | 344 +++++++++++++++++++++++++++++++ >>>> 1 file changed, 344 insertions(+) >>>> >>>> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c >>>> index e5da1cad70ba..38455916331e 100644 >>>> --- a/tools/testing/radix-tree/maple.c >>>> +++ b/tools/testing/radix-tree/maple.c >>> >>> Why not lib/test_maple_tree.c? >>> >>> If they are included there then they will be built into the test module. >>> I try to include any tests that I can in the test module, within reason. >>> >>> >>>> @@ -35857,6 +35857,346 @@ 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. >>> >>> The slots can be different, right? That seems worth mentioning here. >>> It's also worth mentioning this is destructive. >> I compared the type information in the slots, but the addresses cannot >> be compared because they are different. > > Yes, but that is not what the comment says, it states that it will > return 0 if they are the same. It doesn't check the memory addresses or > the parent. I don't expect it to, but your comment is misleading. OK, I have made the modifications in v3. Thanks. > >>> >>>> + */ >>>> +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 __init void mas_subtree_max_range(struct ma_state *mas) >>>> +{ >>>> + unsigned long limit = mas->max; >>>> + MA_STATE(newmas, mas->tree, 0, 0); >>>> + void *entry; >>>> + >>>> + mas_for_each(mas, entry, limit) { >>>> + if (mas->last - mas->index >= >>>> + newmas.last - newmas.index) { >>>> + newmas = *mas; >>>> + } >>>> + } >>>> + >>>> + *mas = newmas; >>>> +} >>>> + >>>> +/* >>>> + * build_full_tree() - Build a full tree. >>>> + * @mt: The tree to build. >>>> + * @flags: Use @flags to build the tree. >>>> + * @height: The height of the tree to build. >>>> + * >>>> + * Build a tree with full leaf nodes and internal nodes. Note that the height >>>> + * should not exceed 3, otherwise it will take a long time to build. >>>> + * Return: zero if the build is successful, non-zero if it fails. >>>> + */ >>>> +static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, >>>> + int height) >>>> +{ >>>> + MA_STATE(mas, mt, 0, 0); >>>> + unsigned long step; >>>> + int ret = 0, cnt = 1; >>>> + enum maple_type type; >>>> + >>>> + mt_init_flags(mt, flags); >>>> + mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); >>>> + >>>> + mtree_lock(mt); >>>> + >>>> + while (1) { >>>> + mas_set(&mas, 0); >>>> + if (mt_height(mt) < height) { >>>> + mas.max = ULONG_MAX; >>>> + goto store; >>>> + } >>>> + >>>> + while (1) { >>>> + mas_dfs_preorder(&mas); >>>> + if (mas_is_none(&mas)) >>>> + goto unlock; >>>> + >>>> + type = mte_node_type(mas.node); >>>> + if (mas_data_end(&mas) + 1 < mt_slots[type]) { >>>> + mas_set(&mas, mas.min); >>>> + goto store; >>>> + } >>>> + } >>>> +store: >>>> + mas_subtree_max_range(&mas); >>>> + step = mas.last - mas.index; >>>> + if (step < 1) { >>>> + ret = -1; >>>> + goto unlock; >>>> + } >>>> + >>>> + step /= 2; >>>> + mas.last = mas.index + step; >>>> + mas_store_gfp(&mas, xa_mk_value(5), >>>> + GFP_KERNEL); >>>> + ++cnt; >>>> + } >>>> +unlock: >>>> + mtree_unlock(mt); >>>> + >>>> + MT_BUG_ON(mt, mt_height(mt) != height); >>>> + /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ >>>> + return ret; >>>> +} >>>> + >>>> +static noinline void __init check_mtree_dup(struct maple_tree *mt) >>>> +{ >>>> + DEFINE_MTREE(new); >>>> + int i, j, ret, count = 0; >>>> + unsigned int rand_seed = 17, rand; >>>> + >>>> + /* store a value at [0, 0] */ >>>> + mt_init_flags(&tree, 0); >>>> + mtree_store_range(&tree, 0, 0, xa_mk_value(0), GFP_KERNEL); >>>> + ret = mtree_dup(&tree, &new, GFP_KERNEL); >>>> + MT_BUG_ON(&new, ret); >>>> + mt_validate(&new); >>>> + if (compare_tree(&tree, &new)) >>>> + MT_BUG_ON(&new, 1); >>>> + >>>> + mtree_destroy(&tree); >>>> + mtree_destroy(&new); >>>> + >>>> + /* The two trees have different attributes. */ >>>> + mt_init_flags(&tree, 0); >>>> + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); >>>> + ret = mtree_dup(&tree, &new, GFP_KERNEL); >>>> + MT_BUG_ON(&new, ret != -EINVAL); >>>> + mtree_destroy(&tree); >>>> + mtree_destroy(&new); >>>> + >>>> + /* The new tree is not empty */ >>>> + mt_init_flags(&tree, 0); >>>> + mt_init_flags(&new, 0); >>>> + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); >>>> + ret = mtree_dup(&tree, &new, GFP_KERNEL); >>>> + MT_BUG_ON(&new, ret != -EINVAL); >>>> + mtree_destroy(&tree); >>>> + mtree_destroy(&new); >>>> + >>>> + /* Test for duplicating full trees. */ >>>> + for (i = 1; i <= 3; i++) { >>>> + ret = build_full_tree(&tree, 0, i); >>>> + MT_BUG_ON(&tree, ret); >>>> + mt_init_flags(&new, 0); >>>> + >>>> + ret = mtree_dup(&tree, &new, GFP_KERNEL); >>>> + MT_BUG_ON(&new, ret); >>>> + mt_validate(&new); >>>> + if (compare_tree(&tree, &new)) >>>> + MT_BUG_ON(&new, 1); >>>> + >>>> + mtree_destroy(&tree); >>>> + mtree_destroy(&new); >>>> + } >>>> + >>>> + for (i = 1; i <= 3; i++) { >>>> + ret = build_full_tree(&tree, MT_FLAGS_ALLOC_RANGE, i); >>>> + MT_BUG_ON(&tree, ret); >>>> + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); >>>> + >>>> + ret = mtree_dup(&tree, &new, GFP_KERNEL); >>>> + MT_BUG_ON(&new, ret); >>>> + mt_validate(&new); >>>> + if (compare_tree(&tree, &new)) >>>> + MT_BUG_ON(&new, 1); >>>> + >>>> + mtree_destroy(&tree); >>>> + mtree_destroy(&new); >>>> + } >>>> + >>>> + /* Test for normal duplicating. */ >>>> + for (i = 0; i < 1000; i += 3) { >>>> + if (i & 1) { >>>> + mt_init_flags(&tree, 0); >>>> + mt_init_flags(&new, 0); >>>> + } else { >>>> + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); >>>> + mt_init_flags(&new, 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); >>>> + } >>>> + >>>> + ret = mtree_dup(&tree, &new, GFP_KERNEL); >>>> + MT_BUG_ON(&new, ret); >>>> + mt_validate(&new); >>>> + if (compare_tree(&tree, &new)) >>>> + MT_BUG_ON(&new, 1); >>>> + >>>> + mtree_destroy(&tree); >>>> + mtree_destroy(&new); >>>> + } >>>> + >>>> + /* Test memory allocation failed. */ >>> >>> It might be worth while having specific allocations fail. At a leaf >>> node, intermediate nodes, first node come to mind. >> Memory allocation is only possible in non-leaf nodes. It is impossible >> to fail in leaf nodes. > > I understand that's your intent and probably what happens today - but > it'd be good to have testing for that, if not for this code then for > future potential changes. But currently, it's not possible to have tests that fail at leaf nodes because they don't fail at leaf nodes. What is done at leaf nodes is simply copying the node and replacing the parent pointer. > >>> >>>> + for (i = 0; i < 1000; i += 3) { >>>> + if (i & 1) { >>>> + mt_init_flags(&tree, 0); >>>> + mt_init_flags(&new, 0); >>>> + } else { >>>> + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); >>>> + mt_init_flags(&new, 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); >>>> + } >>>> + /* >>>> + * The rand() library function is not used, so we can generate >>>> + * the same random numbers on any platform. >>>> + */ >>>> + rand_seed = rand_seed * 1103515245 + 12345; >>>> + rand = rand_seed / 65536 % 128; >>>> + mt_set_non_kernel(rand); >>>> + >>>> + ret = mtree_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("mtree_dup() fail %d times\n", count); */ >>>> + BUG_ON(!count); >>>> +} >>>> + >>>> extern void test_kmem_cache_bulk(void); >>>> void farmer_tests(void) >>>> @@ -35904,6 +36244,10 @@ void farmer_tests(void) >>>> check_null_expand(&tree); >>>> mtree_destroy(&tree); >>>> + mt_init_flags(&tree, 0); >>>> + check_mtree_dup(&tree); >>>> + mtree_destroy(&tree); >>>> + >>>> /* RCU testing */ >>>> mt_init_flags(&tree, 0); >>>> check_erase_testset(&tree); >>>> -- >>>> 2.20.1 >>>>