Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
References: <20191224121210.29713-1-r@hev.cc>
In-Reply-To: <20191224121210.29713-1-r@hev.cc>
From:   Hev <r@hev.cc>
Date:   Wed, 25 Dec 2019 01:00:15 +0800
Message-ID: <CAHirt9hnKdyCnJhdVaw1vt40tZm_3F7LTCw4Ng4Svi_=LVecCg@mail.gmail.com>
Subject: Re: [RFC PATCH 1/3] selftests: add rbtree selftests
To:     linux-kernel@vger.kernel.org
Cc:     Andrew Morton <akpm@linux-foundation.org>,
        Michel Lespinasse <walken@google.com>,
        Peter Zijlstra <peterz@infradead.org>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Hi,

On Tue, Dec 24, 2019 at 8:12 PM Heiher <r@hev.cc> wrote:
>
> This adds the selftest for rbtree. It will reproduce the crash at earsing.
>
> Signed-off-by: hev <r@hev.cc>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Michel Lespinasse <walken@google.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> ---
>  tools/testing/selftests/Makefile              |  1 +
>  tools/testing/selftests/lib/rbtree/.gitignore |  1 +
>  tools/testing/selftests/lib/rbtree/Makefile   | 29 ++++++++
>  .../selftests/lib/rbtree/rbtree_test.c        | 70 +++++++++++++++++++
>  4 files changed, 101 insertions(+)
>  create mode 100644 tools/testing/selftests/lib/rbtree/.gitignore
>  create mode 100644 tools/testing/selftests/lib/rbtree/Makefile
>  create mode 100644 tools/testing/selftests/lib/rbtree/rbtree_test.c
>
> diff --git a/tools/testing/selftests/Makefile b/tools/testing/selftests/Makefile
> index b001c602414b..0e84ca3f207f 100644
> --- a/tools/testing/selftests/Makefile
> +++ b/tools/testing/selftests/Makefile
> @@ -25,6 +25,7 @@ TARGETS += kcmp
>  TARGETS += kexec
>  TARGETS += kvm
>  TARGETS += lib
> +TARGETS += lib/rbtree
>  TARGETS += livepatch
>  TARGETS += membarrier
>  TARGETS += memfd
> diff --git a/tools/testing/selftests/lib/rbtree/.gitignore b/tools/testing/selftests/lib/rbtree/.gitignore
> new file mode 100644
> index 000000000000..4c9f82761fad
> --- /dev/null
> +++ b/tools/testing/selftests/lib/rbtree/.gitignore
> @@ -0,0 +1 @@
> +rbtree_test
> diff --git a/tools/testing/selftests/lib/rbtree/Makefile b/tools/testing/selftests/lib/rbtree/Makefile
> new file mode 100644
> index 000000000000..68fa9dad24a1
> --- /dev/null
> +++ b/tools/testing/selftests/lib/rbtree/Makefile
> @@ -0,0 +1,29 @@
> +# SPDX-License-Identifier: GPL-2.0
> +
> +CFLAGS += -I../../../../include/
> +
> +include ../../lib.mk
> +
> +# lib.mk TEST_CUSTOM_PROGS var is for custom tests that need special
> +# build rules. lib.mk will run and install them.
> +
> +TEST_CUSTOM_PROGS := $(OUTPUT)/rbtree_test
> +all: $(TEST_CUSTOM_PROGS)
> +
> +OBJS = rbtree_test.o
> +
> +LIBS = ../../../../lib/rbtree.o
> +
> +OBJS := $(patsubst %,$(OUTPUT)/%,$(OBJS))
> +LIBS := $(patsubst %,$(OUTPUT)/%,$(LIBS))
> +
> +$(TEST_CUSTOM_PROGS): $(LIBS) $(OBJS)
> +       $(CC) -o $(TEST_CUSTOM_PROGS) $(OBJS) $(LIBS) $(CFLAGS) $(LDFLAGS)
> +
> +$(OBJS): $(OUTPUT)/%.o: %.c
> +       $(CC) -c $^ -o $@ $(CFLAGS)
> +
> +$(LIBS): $(OUTPUT)/%.o: %.c
> +       $(CC) -c $^ -o $@ $(CFLAGS)
> +
> +EXTRA_CLEAN := $(TEST_CUSTOM_PROGS) $(OBJS) $(LIBS)
> diff --git a/tools/testing/selftests/lib/rbtree/rbtree_test.c b/tools/testing/selftests/lib/rbtree/rbtree_test.c
> new file mode 100644
> index 000000000000..11420541071a
> --- /dev/null
> +++ b/tools/testing/selftests/lib/rbtree/rbtree_test.c
> @@ -0,0 +1,70 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <stdlib.h>
> +#include <linux/rbtree.h>
> +#include "../../kselftest_harness.h"
> +
> +struct node {
> +       struct rb_node node;
> +       int key;
> +};
> +
> +static int _insert(struct rb_root *tree, int key)
> +{
> +       struct rb_node **new = &tree->rb_node, *parent = NULL;
> +       struct node *node;
> +
> +       while (*new) {
> +               struct node *this = container_of(*new, struct node, node);
> +
> +               if (key < this->key)
> +                       new = &((*new)->rb_left);
> +               else if (key > this->key)
> +                       new = &((*new)->rb_right);
> +               else
> +                       return 0;
> +       }
> +
> +       node = malloc(sizeof(struct node));
> +       if (!node)
> +               return 0;
> +
> +       node->key = key;
> +       rb_link_node(&node->node, parent, new);
> +       rb_insert_color(&node->node, tree);
> +
> +       return 1;
> +}
> +
> +static void _remove(struct rb_root *tree, int key)
> +{
> +       struct rb_node **node = &tree->rb_node;
> +
> +       while (*node) {
> +               struct node *this = container_of(*node, struct node, node);
> +
> +               if (key < this->key) {
> +                       node = &((*node)->rb_left);
> +               } else if (key > this->key) {
> +                       node = &((*node)->rb_right);
> +               } else {
> +                       rb_erase(&this->node, tree);
> +                       free(this);
> +                       return;
> +               }
> +       }
> +}
> +
> +TEST(rbtree)
> +{
> +       struct rb_root tree = { 0 };
> +
> +       _insert(&tree, 2);
> +       _insert(&tree, 1);
> +       _insert(&tree, 4);
> +       _insert(&tree, 3);
> +
> +       _remove(&tree, 2);
> +}
> +
> +TEST_HARNESS_MAIN
> --
> 2.24.1
>

Sorry, recall these patches.
It was my mistake. I forget to update the parent pointer at inserting. :(

-- 
Best regards!
Hev
https://hev.cc