Received: by 2002:a05:7412:2a8c:b0:e2:908c:2ebd with SMTP id u12csp1262823rdh; Mon, 25 Sep 2023 07:45:39 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFuksSQLTgsQ6ekNf4g4fq07KEOB2eVqM/Z2cW50vDlSEkG1dUVsAyU/5L54sFCtxrv5Zmj X-Received: by 2002:a17:90a:bc9:b0:268:38a7:842e with SMTP id x9-20020a17090a0bc900b0026838a7842emr6147115pjd.2.1695653139437; Mon, 25 Sep 2023 07:45:39 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695653139; cv=none; d=google.com; s=arc-20160816; b=iAtV8tV2MgVfBAX9Rq1m8d6v4RDkAlOn1plsJvs3S2JsXYr7SpPIurBTyxYKBtDBAf kouhqB4/+U0JMlFidWFNsFhkxZbJF40IGy3JK5WjxOV5Ol8wRAVA8k3SNNA+PfJNuKm+ wveYiM5XlsEN+xLpAvGznUW9ikbO28CocJTbYoX+gsufUGxyF8p7vuZejyi+cN4sS0Aj aMoZOmOxlRtLb/dcDJNZvvE6K/V/QiTLTRZ5eVsJMnxg+URi5HM9PlbPMus+Vwo7awps APnBDGG9HdO9CTIa2oBBwZ+u1bYPheUnIqhbw9g0mAVOzuNMPWvuytitlPFPnZ6JsTBK R/zg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:in-reply-to:from :references:to:subject:user-agent:mime-version:date:message-id :dkim-signature; bh=Lyla+nz0kn6ZrMb94jQzHHryI7zWM3so0OyzevozWXo=; fh=Z1qEpGvvHf5f164lHCf0q0MEGNCsPjdqSyTV5+pbiM0=; b=ilqjIGcDPUPi8pWSL6hgjp9DLLKgRBSPkJ31jYr7ms41Ab2K6NHYlYnqs0YIjVmI6E LUiuC9Exv9rntCUXzegONBmIzLVE+dIiU5Rr8njd58x3UyDsZKM9w5agZnWvxop5/Y/z qQVtWUh0wuznm02UYHeisJnJ9XWd7s3lpJ6s7yyiXY/r7I9lqFHv2vrlbf9/SJ5KQCIB 83V4DQmGeMKT6Pax/z1EBD3Zj1kk88sxWFaaQuWsd8AXko3yd0EFW7SBVbeKI51vehA8 bZCeCELezCx69Q4fozJ7AeOiSpgCv0ynGGHL0K/SVRFVMqGSAfSp1lp1y+XsPJCN+/Ai msLA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=UvK6XxWQ; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:5 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Return-Path: Received: from groat.vger.email (groat.vger.email. [2620:137:e000::3:5]) by mx.google.com with ESMTPS id g8-20020a17090ace8800b0026b698fdda6si11922155pju.98.2023.09.25.07.45.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Sep 2023 07:45:39 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:5 as permitted sender) client-ip=2620:137:e000::3:5; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=UvK6XxWQ; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:5 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by groat.vger.email (Postfix) with ESMTP id 6BD1C8068966; Mon, 25 Sep 2023 01:31:30 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at groat.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232844AbjIYIax (ORCPT + 99 others); Mon, 25 Sep 2023 04:30:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54950 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232827AbjIYIau (ORCPT ); Mon, 25 Sep 2023 04:30:50 -0400 Received: from mail-oi1-x230.google.com (mail-oi1-x230.google.com [IPv6:2607:f8b0:4864:20::230]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9DC44D3 for ; Mon, 25 Sep 2023 01:30:20 -0700 (PDT) Received: by mail-oi1-x230.google.com with SMTP id 5614622812f47-3adc3d94f66so4065443b6e.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=vger.kernel.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=UvK6XxWQV6ZOPnqb8IM8cDtLDAFm5jaamNLvSLdmWXPssQBrzjXvXkQhbAc/AXKD6u iKzwS+mz3gcL/RCwE5hds1VgAg6ulji9DYZC5fAsDc2M9I3HKyyH4y2Xo6+ICnmT+3rg 6ecU3SmYcwGrJyt3R3RZte+9S5EBmhCvSdzsRCscHfzTf/gL0HRy6aRskF/9bYgkI095 aazRzVnhnjXrzMlSW8JTFSuT9fcMFKeKlm/6xbQa3jQjqCk8hj+ryFUPzv1V1a+E4TLf ArSekkkVaHxiPxagz9yUNRzz14HO+6JJM5c3H5sC5O3zhpDbaidACY1KWkzdR+S0+LEg 3CbA== 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=pb4C92zrwXNWGzRnsn9I7HPTNyAcbFvnoQHNR598mrCxFwN+50DZzDsaSwUZ4gjnli 6XuvM0QpHmklbR9xAkdMwq+nDxM4g66umGPBsDtDaHeL8G5pB2ZPrGrKrF4bdlJcviol 3cV7HwQQ0Vfa6sVIZq+j708Fw0C6Yz4OWPdhDZIPRP3yhyBSz8I2RGeZ2Zov1vrd4avv bELN58EpIi8h6LPoWz0ySzX4k40P1aSS8c1/sqApC28J5eHRrdbaE/Rv+Fakic+EDiHN 3s8ljmpDUvToFV0ebFIy/3vOtt5DHUIKG4Hz6ejLG744XZ8rSIHgnWxb9a3QCrgzlRgs r/gA== X-Gm-Message-State: AOJu0YwV6lHLMSM0C0Ql9YFIEjfO1ztHHG/qwc5hZSO0xqKM9KYUW+lh YL2l+qpAtOBMfakyiMQUIXlzag== 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-Spam-Status: No, score=-2.3 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, NICE_REPLY_A,SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on groat.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (groat.vger.email [0.0.0.0]); Mon, 25 Sep 2023 01:31:30 -0700 (PDT) 在 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 >>>>