From nobody Thu Sep 08 02:42:44 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 4MNNhN4Vw5z4bqvV; Thu, 8 Sep 2022 02:42:44 +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 4MNNhN3NV3z41xl; Thu, 8 Sep 2022 02:42:44 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1662604964; 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=/NCWO8H712XNk8MeX348h9M9qG8HeIB22f262v245Sk=; b=hCI4zqsLjkEvaXXwdwZwcQErNXQ9wn69CdkOTSKOQRJGBgO1ebpndc2/wRbGe5mzYagbgz c1EWik2PYVimHQvSbg4irltqLtmlaKEBbnK70bE/xfb5xVx9V621DLBeNd2D9+A3Utw2hb hkYIwtJLi/6GBSMGcCpsrU2qzshRWS+YDhC/1Jv3lrsnGM1+VSJfIKUAjT8DjF2nzuL5B6 MOFyQrhfN/hzJcIpwmioIsX982XURpRVT8PCDUp37lgoh3wSQlph1AJP/OGy/uaNyLGqNK WviYXtSugaSUZi/GZsbXAINuBnrjpddFXd6u45JXqiEwLaIJOdY4O8jDhqtFvA== 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 4MNNhN2Q2lzkXV; Thu, 8 Sep 2022 02:42:44 +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 2882gib3064373; Thu, 8 Sep 2022 02:42:44 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 2882gi0x064372; Thu, 8 Sep 2022 02:42:44 GMT (envelope-from git) Date: Thu, 8 Sep 2022 02:42:44 GMT Message-Id: <202209080242.2882gi0x064372@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 2c545cf3b063 - main - 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/main X-Git-Reftype: branch X-Git-Commit: 2c545cf3b06310e248dd4427f31e73f0bc1ad504 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1662604964; 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=/NCWO8H712XNk8MeX348h9M9qG8HeIB22f262v245Sk=; b=ax9z1bKct0fWrFIEDCQmPFHvfM1JV19PqCf1VAdR9Q1hNEK6k3PogvdP/uAmPMB4Dp38/l MjiOLyl69NoAHreziT3WJiY+JnvOqWBM37qN49iRq6dX2UcmzqsD8RlWID9DLaU7EzxNsn p3VV7PBjXFX4AsVVzJ0VqABqEOM7wpqOIooRIY2epfjks8CnuTlkulXlRAgOO8sM7tg4QB k/vn5Z+7Xv0SFmM1KHEgwLO84G8sDZOwNDC4u4w3y6Qjh8+nHKlyDZMNviHASTaZmxeUiN KzEPpw3XITBTI/DyMFxIn3OXu++kdTsR7ZgG6rLXfh0oEP4zCa4otIzyC1B+lg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1662604964; a=rsa-sha256; cv=none; b=Z7vSVSmg4oLa9nS8KlaR/ivK9TcHJuHMAXRwaS6pAQ0K3Lh5BrCAkBc5DQ67MplQgtdR0l NHryNEbnYDIeJYf6xyemHeaXa0NP3E6HqS4GxoRjDF9dJ6YgQu2NvDALDNLVAid/gyZL0B sOwzCPY03UaC3I9BeWsktkLGkeTzrwBoDvPZYs9cAkddzDhnudYatx9/i+6M6OAQYgSgnX 8bneQwvwl9g7/m+bnZvMl1HGvXYmhwRxPT82UvItqsw+FrXj95wn2jsNfzo8Cffy5h6Df7 ayU8KLB+YEZb7y/1d62+NsBKIu584jZOvHb9sOJAlv6GXc+kTTnGngbNuniCGg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N 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); } }