From nobody Sat Oct 01 17:54:01 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 4MfvqF4vR6z4ddg4; Sat, 1 Oct 2022 17:54:01 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4MfvqF4NWqz4F6h; Sat, 1 Oct 2022 17:54:01 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664646841; h=from:from: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; bh=/Ob5ZrbIjWwRGzQej8n5fAAZIrvLD5oLopsIFm1WgHg=; b=OA0FPsQTe+Vk79+/zPP9jqNOGB5BVdjkElR2RrqI+TV7ZrCNIaxCM8NuL/lA8Kw9ZIk+Ja aeYaUkbyNF5U3WSFyVs7XR9OQfYc3660omqNAeMKoXDFlpLjBS+gg4Wu3NjfoQ6m7PwJXd mR/PuJUkjseykvWgoesIbwqMVkPXvd8GQoBakBIRTd4mDnPOC1Ja0ZPWaMrc4WHjNH+HQ2 B86lO2KTt5VPh11rWoabW+OAMEkNZuhwVGpIDpWLWghhHX9Pq5ks7JXXEzQSyu69N10eLj S92jEKb3w5KFTmP0EK6Vy80eJt5tGAXvwticzXbUdzkf7nc3UEQImtiF4x0D4Q== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4MfvqF3QzXzbpF; Sat, 1 Oct 2022 17:54:01 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 291Hs1x8072394; Sat, 1 Oct 2022 17:54:01 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 291Hs1ZE072393; Sat, 1 Oct 2022 17:54:01 GMT (envelope-from git) Date: Sat, 1 Oct 2022 17:54:01 GMT Message-Id: <202210011754.291Hs1ZE072393@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Doug Moore Subject: git: 6164e0292234 - stable/13 - rb_tree: test rank balance 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 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 6164e0292234c1b6901e7b892d617971d3e7abca Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664646841; h=from:from: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; bh=/Ob5ZrbIjWwRGzQej8n5fAAZIrvLD5oLopsIFm1WgHg=; b=ESGbqXj4wvD3tAaj2+ej8tFQ/ahVpeNf6jc5jdzJRz5RZjewcUA8/jIofAlYmcglqviVBY rpeak832Rt62sLgeb/Ef4Qv+2kATWsF2Ujdev4uENjqhZctDhuOwAHGa32+ZEnlT35hQvK jjtQ1vUJKzfcOeHNmATYut8B/cb/fmGQwl2NqjBG+L6ev/NGXO2U+nvR/jwOO3dUIY+6X2 TDM8lUsP/IRM6MV64zMEbkK5VTdz47xC7xsHCdv0b4oLp1I2iJBcq0miVBsrF3LtpNst6S gjVN8uTk6BLbyDfAv6kzJ26vARsG2bp3/VBkti4oy0FAEEsPmbFS7KBRjDs+4A== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1664646841; a=rsa-sha256; cv=none; b=mcNi3oUuObpuCtZiXMlADI8TVx90UZ6sX2tIdUypoNYf1MW30Ox6GEFrmLtc6I40/9mQeY fi7mQOoeMfD8GwbDomUa6MHU279mB9XCffDXKGVgHYFX6/l+PQn3C0gwgqRCVa+VzWqy4R n/bkmx+JrxPEYkFy12D3Pk1WnlRONhdYEhmrn2JcLIPCl+9Jmjm1y9aaiDIGFNHHSFX/Ki 8OQVvbDWIzzhpZvhaB2tXLlE4cYGgb+G6Lu6IAs+zpzQKDd0dXgK7/2yCno6oNCIIM/FeF CTIXOrpyXGFT9JXcUthE8T8ofpcaOd8RrAtNyS1ux/1RhxEj8qEFjgGe4Iyatw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=6164e0292234c1b6901e7b892d617971d3e7abca commit 6164e0292234c1b6901e7b892d617971d3e7abca Author: Doug Moore AuthorDate: 2022-09-08 02:40:05 +0000 Commit: Doug Moore CommitDate: 2022-10-01 17:50:33 +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 (cherry picked from commit 2c545cf3b06310e248dd4427f31e73f0bc1ad504) --- 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 3f1735d2a837..414a89e202a0 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); } }