From nobody Fri Sep 16 22:32:37 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4MTpjh40dyz4cJJQ; Fri, 16 Sep 2022 22:32:40 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: from mail-oi1-x231.google.com (mail-oi1-x231.google.com [IPv6:2607:f8b0:4864:20::231]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1D4" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4MTpjg4YPKz3lN2; Fri, 16 Sep 2022 22:32:39 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: by mail-oi1-x231.google.com with SMTP id t62so7801954oie.10; Fri, 16 Sep 2022 15:32:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:references:in-reply-to :mime-version:from:to:cc:subject:date; bh=cgPIXGDSTszN/n+i/qs56XkwydTB2LJq0i/r+HGdFls=; b=hhuQJPprRuk76qhfwY5+M8ZaBOYjckxLCMjgL3TPQVtlqVh8F1Wk2Sekk3QD9WrLzW HU5oLzPTRXY2c15zAt78jiS213RR28dJXzzN296aZq//0GZJ0U37fMmfA3Er6tZtkklw bVSNwEcNJl/7KVQFWa520IeiKOFHXu6g+Rmk6UBtwPWwmwivYMs5cvm4eYFlgMwONws1 s1k3SPeFmhEMevAk2t0XgSwzHQW0yeJfrO9iQcEmXaobBAu10t8kk76dsViaoAdAqVR8 FlV8EHVqqSDNtHCAhGqiRx2Y6bnjzUHxN7ickRw1vmm6M0IhXFvPpsa/iq0Y91eZo2RT Eb2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:references:in-reply-to :mime-version:x-gm-message-state:from:to:cc:subject:date; bh=cgPIXGDSTszN/n+i/qs56XkwydTB2LJq0i/r+HGdFls=; b=W3Nwr5v1kFE3W20SB4x6CfRFuBoe7eP6ePwmYbtVltN5uNv/EIZ7C41/+8RJs9lPno TiL3gvXjASDvF6w4Rjml6pKrEns6NOA2lUkjZRM7lOzpdWVlr9IpFJVuQFvwArz3zSZz WTgmbq9IoJKyj/qmUW3BNrbzKViQDy/ogEd/fV0uA0lcpB9BgRkmA+MOEBhe26HH88tc DmL3Z1tC0i3Vzn5QcBZ4LPuDWJ/VYzZZmSrJ1WhJFcm8v25aYACSwXQG0SzJzLOmGIBc sZLvtb5NXVS/k6F3LerNt8Y41WGtdUpBJGT6xwC3+o51virm6NbB3+ZXTO6lv2OPlEpF r1mA== X-Gm-Message-State: ACrzQf0XYUjLIdIZeUgOE2S6eZiFdJyAUJimmthdPKRdJG4HlznyzGlK ZEu7Buf3mlbW/EiyFOVDc45MFozlcw5tYUvGBuXoF2tJ X-Google-Smtp-Source: AMsMyM5d5C3XRMw7F9At9fuF1WTe9dtNbz/UwCInCxeRv5fWnJkl08SViMcCFPCQHhkcp/xgpzAjjcbdgdOyNU5N84o= X-Received: by 2002:a05:6808:201b:b0:350:87c:a8c6 with SMTP id q27-20020a056808201b00b00350087ca8c6mr3472397oiw.228.1663367558131; Fri, 16 Sep 2022 15:32:38 -0700 (PDT) List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Received: by 2002:a8a:352:0:b0:474:267f:5338 with HTTP; Fri, 16 Sep 2022 15:32:37 -0700 (PDT) In-Reply-To: <202209080242.2882gi0x064372@gitrepo.freebsd.org> References: <202209080242.2882gi0x064372@gitrepo.freebsd.org> From: Mateusz Guzik Date: Sat, 17 Sep 2022 00:32:37 +0200 Message-ID: Subject: Re: git: 2c545cf3b063 - main - rb_tree: test rank balance To: Doug Moore Cc: src-committers@freebsd.org, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: 4MTpjg4YPKz3lN2 X-Spamd-Bar: --- Authentication-Results: mx1.freebsd.org; dkim=pass header.d=gmail.com header.s=20210112 header.b=hhuQJPpr; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (mx1.freebsd.org: domain of mjguzik@gmail.com designates 2607:f8b0:4864:20::231 as permitted sender) smtp.mailfrom=mjguzik@gmail.com X-Spamd-Result: default: False [-3.93 / 15.00]; NEURAL_HAM_SHORT(-0.99)[-0.995]; NEURAL_HAM_LONG(-0.99)[-0.985]; NEURAL_HAM_MEDIUM(-0.95)[-0.949]; DMARC_POLICY_ALLOW(-0.50)[gmail.com,none]; R_DKIM_ALLOW(-0.20)[gmail.com:s=20210112]; R_SPF_ALLOW(-0.20)[+ip6:2607:f8b0:4000::/36]; MIME_GOOD(-0.10)[text/plain]; MLMMJ_DEST(0.00)[dev-commits-src-all@freebsd.org,dev-commits-src-main@freebsd.org]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; RCVD_IN_DNSWL_NONE(0.00)[2607:f8b0:4864:20::231:from]; ASN(0.00)[asn:15169, ipnet:2607:f8b0::/32, country:US]; FREEMAIL_ENVFROM(0.00)[gmail.com]; ARC_NA(0.00)[]; RCVD_COUNT_THREE(0.00)[3]; MID_RHS_MATCH_FROMTLD(0.00)[]; RCPT_COUNT_THREE(0.00)[4]; FROM_HAS_DN(0.00)[]; DKIM_TRACE(0.00)[gmail.com:+]; FREEMAIL_FROM(0.00)[gmail.com]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; RCVD_TLS_LAST(0.00)[]; DWL_DNSWL_NONE(0.00)[gmail.com:dkim] X-ThisMailContainsUnwantedMimeParts: N Debug builds keep spamming: /tank/users/mjg/src/freebsd/sys/netpfil/pf/pf_norm.c:132:8: warning: function 'pf_frag_tree_RB_RANK' is not needed and will not be emitted [-Wunneeded-internal-declaration] static RB_GENERATE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare); ^ /tank/users/mjg/src/freebsd/sys/sys/tree.h:455:2: note: expanded from macro 'RB_GENERATE' RB_GENERATE_INTERNAL(name, type, field, cmp,) ^ /tank/users/mjg/src/freebsd/sys/sys/tree.h:459:2: note: expanded from macro 'RB_GENERATE_INTERNAL' RB_GENERATE_RANK(name, type, field, attr) \ ^ /tank/users/mjg/src/freebsd/sys/sys/tree.h:473:17: note: expanded from macro 'RB_GENERATE_RANK' attr int \ ^ :66:1: note: expanded from here pf_frag_tree_RB_RANK ^ etc. On 9/8/22, Doug Moore wrote: > The branch main has been updated by dougm: > > URL: > https://cgit.FreeBSD.org/src/commit/?id=2c545cf3b06310e248dd4427f31e73f0bc1ad504 > > commit 2c545cf3b06310e248dd4427f31e73f0bc1ad504 > Author: Doug Moore > AuthorDate: 2022-09-08 02:40:05 +0000 > Commit: Doug Moore > CommitDate: 2022-09-08 02:40:05 +0000 > > rb_tree: test rank balance > > With _RB_DIAGNOSTIC defined, provide an RB_RANK method to compute the > rank of a node in an rb-tree, if the subtree rooted at that node is > rank-balanced, and -1 otherwise. > > In rb_test, rewrite a bit to avoid malloc/free and nondeterministic > running times because of randomness. Allocate all the nodes on the > stack, and shuffle a set of keys to get randomness for the testing. > > Add a rank-balance check for the completed tree. > > Reviewed by: markj > MFC after: 3 weeks > Differential Revision: https://reviews.freebsd.org/D36484 > --- > sys/sys/tree.h | 37 ++++++++++++++++++++++++++++ > tests/sys/sys/rb_test.c | 65 > ++++++++++++++++++++++++++----------------------- > 2 files changed, 71 insertions(+), 31 deletions(-) > > diff --git a/sys/sys/tree.h b/sys/sys/tree.h > index 971562a5c121..74f1f23d3576 100644 > --- a/sys/sys/tree.h > +++ b/sys/sys/tree.h > @@ -410,12 +410,17 @@ struct { \ > RB_SET_PARENT(elm, tmp, field); \ > } while (/*CONSTCOND*/ 0) > > +#if defined(_KERNEL) && defined(DIAGNOSTIC) && !defined(_RB_DIAGNOSTIC) > +#define _RB_DIAGNOSTIC 1 > +#endif > + > /* Generates prototypes and inline functions */ > #define RB_PROTOTYPE(name, type, field, cmp) \ > RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) > #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ > RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) > #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ > + RB_PROTOTYPE_RANK(name, type, attr) \ > RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ > RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ > RB_PROTOTYPE_INSERT(name, type, attr); \ > @@ -426,6 +431,12 @@ struct { \ > RB_PROTOTYPE_PREV(name, type, attr); \ > RB_PROTOTYPE_MINMAX(name, type, attr); \ > RB_PROTOTYPE_REINSERT(name, type, attr); > +#ifdef _RB_DIAGNOSTIC > +#define RB_PROTOTYPE_RANK(name, type, attr) \ > + attr int name##_RB_RANK(struct type *); > +#else > +#define RB_PROTOTYPE_RANK(name, type, attr) > +#endif > #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ > attr void name##_RB_INSERT_COLOR(struct name *, struct type *) > #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ > @@ -456,6 +467,7 @@ struct { \ > #define RB_GENERATE_STATIC(name, type, field, cmp) \ > RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) > #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ > + RB_GENERATE_RANK(name, type, field, attr) \ > RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ > RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ > RB_GENERATE_INSERT(name, type, field, cmp, attr) \ > @@ -467,6 +479,31 @@ struct { \ > RB_GENERATE_MINMAX(name, type, field, attr) \ > RB_GENERATE_REINSERT(name, type, field, cmp, attr) > > +#ifdef _RB_DIAGNOSTIC > +#define RB_GENERATE_RANK(name, type, field, attr) \ > +attr int \ > +name##_RB_RANK(struct type *elm) \ > +{ \ > + struct type *left, *right; \ > + int left_rank, right_rank; \ > + __uintptr_t bits; \ > + \ > + if (elm == NULL) \ > + return (0); \ > + bits = RB_BITS(elm, field); \ > + left = RB_LEFT(elm, field); \ > + left_rank = ((bits & RB_RED_L) ? 2 : 1) + name##_RB_RANK(left); \ > + right = RB_RIGHT(elm, field); \ > + right_rank = ((bits & RB_RED_R) ? 2 : 1) + name##_RB_RANK(right); \ > + if (left_rank != right_rank || \ > + (left_rank == 2 && left == NULL && right == NULL)) \ > + return (-1); \ > + return (left_rank); \ > +} > +#else > +#define RB_GENERATE_RANK(name, type, field, attr) > +#endif > + > #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ > attr void \ > name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ > diff --git a/tests/sys/sys/rb_test.c b/tests/sys/sys/rb_test.c > index c558ad6098cf..149fbe052bde 100644 > --- a/tests/sys/sys/rb_test.c > +++ b/tests/sys/sys/rb_test.c > @@ -29,6 +29,7 @@ > */ > #include > > +#define _RB_DIAGNOSTIC 1 > #include > #include > > @@ -54,52 +55,54 @@ RB_PROTOTYPE(tree, node, node, compare); > RB_GENERATE(tree, node, node, compare); > > #define ITER 150 > -#define MIN 5 > -#define MAX 5000 > > ATF_TC_WITHOUT_HEAD(rb_test); > ATF_TC_BODY(rb_test, tc) > { > - struct node *tmp, *ins; > - int i, max, min; > + struct node *tmp, *ins, store[ITER]; > + int i, j, k, max, min; > > - max = min = 42; /* pacify gcc */ > + min = ITER; > + max = -1; > > RB_INIT(&root); > > + /* Initialize keys */ > + for (i = 0; i < ITER; i++) > + store[i].key = i; > + > + /* Randomly shuffle keys */ > + for (i = 0; i < ITER; i++) { > + j = i + arc4random_uniform(ITER - i); > + k = store[j].key; > + store[j].key = store[i].key; > + store[i].key = k; > + } > + > for (i = 0; i < ITER; i++) { > - tmp = malloc(sizeof(struct node)); > - ATF_REQUIRE_MSG(tmp != NULL, "malloc failed"); > - do { > - tmp->key = arc4random_uniform(MAX-MIN); > - tmp->key += MIN; > - } while (RB_FIND(tree, &root, tmp) != NULL); > - if (i == 0) > - max = min = tmp->key; > - else { > - if (tmp->key > max) > - max = tmp->key; > - if (tmp->key < min) > - min = tmp->key; > + for (j = 0; j < i; ++j) { > + tmp = &store[j]; > + ATF_REQUIRE_EQ(tmp, RB_FIND(tree, &root, tmp)); > } > + tmp = &store[i]; > + if (tmp->key > max) > + max = tmp->key; > + if (tmp->key < min) > + min = tmp->key; > ATF_REQUIRE_EQ(NULL, RB_INSERT(tree, &root, tmp)); > + ins = RB_MIN(tree, &root); > + ATF_REQUIRE_MSG(ins != NULL, "RB_MIN error"); > + ATF_CHECK_EQ(min, ins->key); > + ins = RB_MAX(tree, &root); > + ATF_REQUIRE_MSG(ins != NULL, "RB_MAX error"); > + ATF_CHECK_EQ(max, ins->key); > } > - > - ins = RB_MIN(tree, &root); > - ATF_REQUIRE_MSG(ins != NULL, "RB_MIN error"); > - ATF_CHECK_EQ(min, ins->key); > - tmp = ins; > - ins = RB_MAX(tree, &root); > - ATF_REQUIRE_MSG(ins != NULL, "RB_MAX error"); > - ATF_CHECK_EQ(max, ins->key); > - > - ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp)); > - > - for (i = 0; i < ITER - 1; i++) { > + tmp = RB_ROOT(&root); > + ATF_REQUIRE_MSG(tree_RB_RANK(tmp) >= 0, "RB rank balance error"); > + for (i = 0; i < ITER; i++) { > tmp = RB_ROOT(&root); > ATF_REQUIRE_MSG(tmp != NULL, "RB_ROOT error"); > ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp)); > - free(tmp); > } > } > > > -- Mateusz Guzik