[RFC Patch 2/5] anon_vma: add skeleton code for userland testing of anon_vma logic

[Wei Yang <richard.weiyang@gmail.com>]

Establish a new userland anon_vma unit testing implementation under
tools/testing.

Current is a skeleton with simple cases and provides possibility for new
tests.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
Cc: Jann Horn <jannh@google.com>
Cc: David Hildenbrand <david@redhat.com>
Cc: Barry Song <baohua@kernel.org>
Cc: Rik van Riel <riel@surriel.com>
Cc: Vlastimil Babka <vbabka@suse.cz>
Cc: Harry Yoo <harry.yoo@oracle.com>
---
 tools/include/linux/rwsem.h                |  10 +
 tools/include/linux/slab.h                 |   4 +
 tools/testing/anon_vma/.gitignore          |   3 +
 tools/testing/anon_vma/Makefile            |  25 ++
 tools/testing/anon_vma/anon_vma.c          | 438 +++++++++++++++++++++
 tools/testing/anon_vma/anon_vma_internal.h |  55 +++
 tools/testing/anon_vma/interval_tree.c     |  53 +++
 tools/testing/anon_vma/linux/atomic.h      |  18 +
 tools/testing/anon_vma/linux/fs.h          |   6 +
 tools/testing/anon_vma/linux/mm.h          |  44 +++
 tools/testing/anon_vma/linux/mm_types.h    |  57 +++
 tools/testing/anon_vma/linux/mmzone.h      |   6 +
 tools/testing/anon_vma/linux/rmap.h        |   8 +
 tools/testing/shared/linux/anon_vma.h      |   7 +
 14 files changed, 734 insertions(+)
 create mode 100644 tools/testing/anon_vma/.gitignore
 create mode 100644 tools/testing/anon_vma/Makefile
 create mode 100644 tools/testing/anon_vma/anon_vma.c
 create mode 100644 tools/testing/anon_vma/anon_vma_internal.h
 create mode 100644 tools/testing/anon_vma/interval_tree.c
 create mode 100644 tools/testing/anon_vma/linux/atomic.h
 create mode 100644 tools/testing/anon_vma/linux/fs.h
 create mode 100644 tools/testing/anon_vma/linux/mm.h
 create mode 100644 tools/testing/anon_vma/linux/mm_types.h
 create mode 100644 tools/testing/anon_vma/linux/mmzone.h
 create mode 100644 tools/testing/anon_vma/linux/rmap.h
 create mode 100644 tools/testing/shared/linux/anon_vma.h

diff --git a/tools/include/linux/rwsem.h b/tools/include/linux/rwsem.h
index f8bffd4a987c..a74e424e4cfe 100644
--- a/tools/include/linux/rwsem.h
+++ b/tools/include/linux/rwsem.h
@@ -38,6 +38,16 @@ static inline int up_write(struct rw_semaphore *sem)
 	return pthread_rwlock_unlock(&sem->lock);
 }
 
+static inline int down_read_trylock(struct rw_semaphore *sem)
+{
+	return pthread_rwlock_tryrdlock(&sem->lock);
+}
+
+static inline int down_write_trylock(struct rw_semaphore *sem)
+{
+	return pthread_rwlock_trywrlock(&sem->lock);
+}
+
 #define down_read_nested(sem, subclass)		down_read(sem)
 #define down_write_nested(sem, subclass)	down_write(sem)
 
diff --git a/tools/include/linux/slab.h b/tools/include/linux/slab.h
index c87051e2b26f..6ebdda7aadbf 100644
--- a/tools/include/linux/slab.h
+++ b/tools/include/linux/slab.h
@@ -41,6 +41,10 @@ struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
 			unsigned int align, unsigned int flags,
 			void (*ctor)(void *));
 
+#define KMEM_CACHE(__struct, __flags)					\
+	kmem_cache_create(#__struct, sizeof(struct __struct),		\
+		__alignof__(struct __struct), __flags, NULL)
+
 void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list);
 int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
 			  void **list);
diff --git a/tools/testing/anon_vma/.gitignore b/tools/testing/anon_vma/.gitignore
new file mode 100644
index 000000000000..aa2885a029f9
--- /dev/null
+++ b/tools/testing/anon_vma/.gitignore
@@ -0,0 +1,3 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+generated/
+anon_vma
diff --git a/tools/testing/anon_vma/Makefile b/tools/testing/anon_vma/Makefile
new file mode 100644
index 000000000000..120e2217e957
--- /dev/null
+++ b/tools/testing/anon_vma/Makefile
@@ -0,0 +1,25 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+
+.PHONY: default clean
+
+default: anon_vma
+
+include ../shared/shared.mk
+
+CFLAGS += -D CONFIG_PHYS_ADDR_T_64BIT
+ifeq ($(DEBUG), 1)
+	CFLAGS += -D ANON_VMA_INTERVAL_TREE_DEBUG -g
+endif
+
+OFILES = $(LIBS) linux.o anon_vma.o rbtree-shim.o \
+	 interval_tree-shim.o interval_tree.o
+TARGETS = anon_vma
+
+interval_tree.o: ../../../mm/interval_tree.c
+anon_vma.o: anon_vma.c anon_vma_internal.h ../../../mm/anon_vma.c \
+	 ../../../include/linux/anon_vma.h
+
+anon_vma: $(OFILES)
+
+clean:
+	$(RM) $(TARGETS) *.o generated/*
diff --git a/tools/testing/anon_vma/anon_vma.c b/tools/testing/anon_vma/anon_vma.c
new file mode 100644
index 000000000000..f3ca193857ec
--- /dev/null
+++ b/tools/testing/anon_vma/anon_vma.c
@@ -0,0 +1,438 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <linux/bitmap.h>
+
+#include "anon_vma_internal.h"
+#include "../../../mm/anon_vma.c"
+
+#define ASSERT_TRUE(_expr)						\
+	do {								\
+		if (!(_expr)) {						\
+			fprintf(stderr,					\
+				"Assert FAILED at %s:%d:%s(): %s is FALSE.\n", \
+				__FILE__, __LINE__, __func__, #_expr); \
+			return false;					\
+		}							\
+	} while (0)
+#define ASSERT_FALSE(_expr) ASSERT_TRUE(!(_expr))
+#define ASSERT_EQ(_val1, _val2) ASSERT_TRUE((_val1) == (_val2))
+#define ASSERT_NE(_val1, _val2) ASSERT_TRUE((_val1) != (_val2))
+
+static struct mm_struct dummy_mm = {
+	.page_table_lock = __SPIN_LOCK_UNLOCKED(dummy_mm.page_table_lock),
+};
+
+#define NUM_VMAS 50
+static int vmas_idx;
+static struct vm_area_struct *vmas[NUM_VMAS];
+static struct kmem_cache *vm_area_cachep;
+
+static void vma_ctor(void *data)
+{
+	struct vm_area_struct *vma;
+
+	vma = data;
+	INIT_LIST_HEAD(&vma->anon_vma_chain);
+	vma->vm_mm = &dummy_mm;
+	vma->anon_vma = NULL;
+}
+
+void vma_cache_init(void)
+{
+	/* vma's kmem_cache for test */
+	vm_area_cachep = kmem_cache_create("vm_area_struct",
+			sizeof(struct vm_area_struct), 0,
+			SLAB_PANIC|SLAB_ACCOUNT, vma_ctor);
+}
+
+struct vm_area_struct *alloc_vma(unsigned long start, unsigned long end, pgoff_t pgoff)
+{
+	if (vmas_idx >= NUM_VMAS)
+		return NULL;
+
+	vmas[vmas_idx] = kmem_cache_alloc(vm_area_cachep, GFP_KERNEL);
+	vmas[vmas_idx]->index = vmas_idx;
+	vma_set_range(vmas[vmas_idx], start, end, pgoff);
+
+	return vmas[vmas_idx++];
+}
+
+void vm_area_free(struct vm_area_struct *vma)
+{
+	kmem_cache_free(vm_area_cachep, vma);
+}
+
+void cleanup(void)
+{
+	int i;
+
+	for (i = 0; i < NUM_VMAS; i++) {
+		if (!vmas[i])
+			continue;
+
+		unlink_anon_vmas(vmas[i]);
+		vm_area_free(vmas[i]);
+		vmas[i] = NULL;
+	}
+
+	vmas_idx = 0;
+}
+
+static bool test_simple_fault(void)
+{
+	struct vm_area_struct *root_vma;
+	struct anon_vma_chain *avc;
+
+	root_vma = alloc_vma(0x3000, 0x5000, 3);
+	/* First fault on anonymous vma would create its anon_vma. */
+	__anon_vma_prepare(root_vma);
+	ASSERT_NE(NULL, root_vma->anon_vma);
+	dump_anon_vma_interval_tree(root_vma->anon_vma);
+
+	/*
+	 *  anon_vma           root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 */
+
+	anon_vma_interval_tree_foreach(avc, &root_vma->anon_vma->rb_root, 3, 4) {
+		/* Expect to find itself from anon_vma interval tree */
+		ASSERT_EQ(avc->vma, root_vma);
+	}
+
+	cleanup();
+
+	ASSERT_EQ(0, nr_allocated);
+	return true;
+}
+
+static bool test_simple_fork(void)
+{
+	struct vm_area_struct *root_vma, *child_vma;
+	struct anon_vma_chain *avc;
+	DECLARE_BITMAP(expected, 10);
+	DECLARE_BITMAP(found, 10);
+
+	bitmap_zero(expected, 10);
+	bitmap_zero(found, 10);
+
+	/*
+	 *  anon_vma           root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 */
+
+	root_vma = alloc_vma(0x3000, 0x5000, 3);
+	/* First fault on parent anonymous vma. */
+	__anon_vma_prepare(root_vma);
+	ASSERT_NE(NULL, root_vma->anon_vma);
+	bitmap_set(expected, root_vma->index, 1);
+
+	/*
+	 *  anon_vma           root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 *                \
+	 *                 \   child_vma
+	 *                  \  +-----------+
+	 *                   > |           |
+	 *                     +-----------+
+	 */
+
+	child_vma = alloc_vma(0x3000, 0x5000, 3);
+	/* Fork child will link it to parent and may create its own anon_vma. */
+	anon_vma_fork(child_vma, root_vma);
+	ASSERT_NE(NULL, child_vma->anon_vma);
+	bitmap_set(expected, child_vma->index, 1);
+	/* Parent/Root is root_vma->anon_vma */
+	ASSERT_EQ(child_vma->anon_vma->parent, root_vma->anon_vma);
+	ASSERT_EQ(child_vma->anon_vma->root, root_vma->anon_vma);
+	dump_anon_vma_interval_tree(root_vma->anon_vma);
+
+	anon_vma_interval_tree_foreach(avc, &root_vma->anon_vma->rb_root, 3, 4) {
+		bitmap_set(found, avc->vma->index, 1);
+	}
+
+	/* Expect to find all vma including the forked one. */
+	ASSERT_TRUE(bitmap_equal(expected, found, 10));
+
+	cleanup();
+
+	ASSERT_EQ(0, nr_allocated);
+	return true;
+}
+
+static bool test_fork_two(void)
+{
+	struct vm_area_struct *root_vma, *vma1, *vma2;
+	struct anon_vma_chain *avc;
+	DECLARE_BITMAP(expected, 10);
+	DECLARE_BITMAP(found, 10);
+
+	bitmap_zero(expected, 10);
+	bitmap_zero(found, 10);
+
+	/*
+	 *  anon_vma           root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 */
+
+	root_vma = alloc_vma(0x3000, 0x5000, 3);
+	/* First fault on parent anonymous vma. */
+	__anon_vma_prepare(root_vma);
+	ASSERT_NE(NULL, root_vma->anon_vma);
+	bitmap_set(expected, root_vma->index, 1);
+
+	/* First fork */
+	/*
+	 *  anon_vma           root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 *                \
+	 *                 \   vma1
+	 *                  \  +-----------+
+	 *                   > |           |
+	 *                     +-----------+
+	 */
+	vma1 = alloc_vma(0x3000, 0x5000, 3);
+	anon_vma_fork(vma1, root_vma);
+	ASSERT_NE(NULL, vma1->anon_vma);
+	bitmap_set(expected, vma1->index, 1);
+	/* Parent/Root is root_vma->anon_vma */
+	ASSERT_EQ(vma1->anon_vma->parent, root_vma->anon_vma);
+	ASSERT_EQ(vma1->anon_vma->root, root_vma->anon_vma);
+
+	/* Second fork */
+	/*
+	 *  anon_vma           root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 *               \
+	 *                \------------------+
+	 *                 \   vma1           \   vma2
+	 *                  \  +-----------+   \  +-----------+
+	 *                   > |           |    > |           |
+	 *                     +-----------+      +-----------+
+	 */
+	vma2 = alloc_vma(0x3000, 0x5000, 3);
+	anon_vma_fork(vma2, root_vma);
+	ASSERT_NE(NULL, vma2->anon_vma);
+	bitmap_set(expected, vma2->index, 1);
+	/* Parent/Root is root_vma->anon_vma */
+	ASSERT_EQ(vma2->anon_vma->parent, root_vma->anon_vma);
+	ASSERT_EQ(vma2->anon_vma->root, root_vma->anon_vma);
+	dump_anon_vma_interval_tree(root_vma->anon_vma);
+
+	anon_vma_interval_tree_foreach(avc, &root_vma->anon_vma->rb_root, 3, 4) {
+		bitmap_set(found, avc->vma->index, 1);
+	}
+
+	/* Expect to find all vma including the forked one. */
+	ASSERT_TRUE(bitmap_equal(expected, found, 10));
+
+	/*
+	 *  vma1->anon_vma     vma1
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 */
+	anon_vma_interval_tree_foreach(avc, &vma1->anon_vma->rb_root, 3, 4) {
+		/* Expect to find only itself from its anon_vma interval tree */
+		ASSERT_EQ(avc->vma, vma1);
+	}
+
+	/*
+	 *  vma2->anon_vma     vma2
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 */
+	anon_vma_interval_tree_foreach(avc, &vma2->anon_vma->rb_root, 3, 4) {
+		/* Expect to find only itself from its anon_vma interval tree */
+		ASSERT_EQ(avc->vma, vma2);
+	}
+
+	cleanup();
+
+	ASSERT_EQ(0, nr_allocated);
+	return true;
+}
+
+static bool test_fork_grand_child(void)
+{
+	struct vm_area_struct *root_vma, *grand_vma, *vma1, *vma2;
+	struct anon_vma_chain *avc;
+	struct anon_vma *root_anon_vma;
+	DECLARE_BITMAP(expected, 10);
+	DECLARE_BITMAP(found, 10);
+
+	bitmap_zero(expected, 10);
+	bitmap_zero(found, 10);
+
+	/*
+	 *  root_anon_vma      root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 */
+
+	root_vma = alloc_vma(0x3000, 0x5000, 3);
+	/* First fault on parent anonymous vma. */
+	__anon_vma_prepare(root_vma);
+	root_anon_vma = root_vma->anon_vma;
+	ASSERT_NE(NULL, root_anon_vma);
+	bitmap_set(expected, root_vma->index, 1);
+
+	/* First fork */
+	/*
+	 *  root_anon_vma      root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 *                \
+	 *                 \   vma1
+	 *                  \  +-----------+
+	 *                   > |           |
+	 *                     +-----------+
+	 */
+	vma1 = alloc_vma(0x3000, 0x5000, 3);
+	anon_vma_fork(vma1, root_vma);
+	ASSERT_NE(NULL, vma1->anon_vma);
+	bitmap_set(expected, vma1->index, 1);
+	/* Parent/Root is root_vma->anon_vma */
+	ASSERT_EQ(vma1->anon_vma->parent, root_vma->anon_vma);
+	ASSERT_EQ(vma1->anon_vma->root, root_vma->anon_vma);
+
+	/* Second fork */
+	/*
+	 *  root_anon_vma      root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 *               \
+	 *                \------------------+
+	 *                 \   vma1           \   vma2
+	 *                  \  +-----------+   \  +-----------+
+	 *                   > |           |    > |           |
+	 *                     +-----------+      +-----------+
+	 */
+	vma2 = alloc_vma(0x3000, 0x5000, 3);
+	anon_vma_fork(vma2, root_vma);
+	ASSERT_NE(NULL, vma2->anon_vma);
+	bitmap_set(expected, vma2->index, 1);
+	/* Parent/Root is root_vma->anon_vma */
+	ASSERT_EQ(vma2->anon_vma->parent, root_vma->anon_vma);
+	ASSERT_EQ(vma2->anon_vma->root, root_vma->anon_vma);
+	dump_anon_vma_interval_tree(root_vma->anon_vma);
+
+	/* Fork grand child from second child */
+	/*
+	 *  root_anon_vma      root_vma
+	 *  +-----------+      +-----------+
+	 *  |           | ---> |           |
+	 *  +-----------+      +-----------+
+	 *               \
+	 *                \------------------+
+	 *                |\   vma1           \   vma2
+	 *                | \  +-----------+   \  +-----------+
+	 *                |  > |           |    > |           |
+	 *                |    +-----------+      +-----------+
+	 *                \
+	 *                 \   grand_vma
+	 *                  \  +-----------+
+	 *                   > |           |
+	 *                     +-----------+
+	 */
+	grand_vma = alloc_vma(0x3000, 0x5000, 3);
+	anon_vma_fork(grand_vma, vma2);
+	ASSERT_NE(NULL, grand_vma->anon_vma);
+	bitmap_set(expected, grand_vma->index, 1);
+	/* Root is root_vma->anon_vma */
+	ASSERT_EQ(grand_vma->anon_vma->root, root_vma->anon_vma);
+	/* Parent is vma2->anon_vma */
+	ASSERT_EQ(grand_vma->anon_vma->parent, vma2->anon_vma);
+
+	/* Expect to find only vmas from second fork */
+	anon_vma_interval_tree_foreach(avc, &vma2->anon_vma->rb_root, 3, 4) {
+		ASSERT_TRUE(avc->vma == vma2 || avc->vma == grand_vma);
+	}
+
+	anon_vma_interval_tree_foreach(avc, &root_vma->anon_vma->rb_root, 3, 4) {
+		bitmap_set(found, avc->vma->index, 1);
+	}
+	/* Expect to find all vma including child and grand child. */
+	ASSERT_TRUE(bitmap_equal(expected, found, 10));
+
+	/* Root process exit or unmap root_vma. */
+	/*
+	 *  root_anon_vma
+	 *  +-----------+
+	 *  |           |
+	 *  +-----------+
+	 *               \
+	 *                \------------------+
+	 *                |\   vma1           \   vma2
+	 *                | \  +-----------+   \  +-----------+
+	 *                |  > |           |    > |           |
+	 *                |    +-----------+      +-----------+
+	 *                \
+	 *                 \   grand_vma
+	 *                  \  +-----------+
+	 *                   > |           |
+	 *                     +-----------+
+	 */
+	bitmap_clear(expected, root_vma->index, 1);
+	unlink_anon_vmas(root_vma);
+	ASSERT_EQ(0, root_anon_vma->num_active_vmas);
+
+	bitmap_zero(found, 10);
+	anon_vma_interval_tree_foreach(avc, &root_anon_vma->rb_root, 3, 4) {
+		bitmap_set(found, avc->vma->index, 1);
+	}
+	/* Expect to find all vmas even root_vma released. */
+	ASSERT_TRUE(bitmap_equal(expected, found, 10));
+
+	cleanup();
+
+	ASSERT_EQ(0, nr_allocated);
+	return true;
+}
+
+int main(void)
+{
+	int num_tests = 0, num_fail = 0;
+
+	vma_cache_init();
+	anon_vma_init();
+
+#define TEST(name)							\
+	do {								\
+		num_tests++;						\
+		if (!test_##name()) {					\
+			num_fail++;					\
+			fprintf(stderr, "Test " #name " FAILED\n");	\
+		}							\
+	} while (0)
+
+	TEST(simple_fault);
+	TEST(simple_fork);
+	TEST(fork_two);
+	TEST(fork_grand_child);
+
+#undef TEST
+
+	printf("%d tests run, %d passed, %d failed.\n",
+	       num_tests, num_tests - num_fail, num_fail);
+
+	return num_fail == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
+}
diff --git a/tools/testing/anon_vma/anon_vma_internal.h b/tools/testing/anon_vma/anon_vma_internal.h
new file mode 100644
index 000000000000..296c1df71f7c
--- /dev/null
+++ b/tools/testing/anon_vma/anon_vma_internal.h
@@ -0,0 +1,55 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __MM_ANON_VMA_INTERNAL_H
+#define __MM_ANON_VMA_INTERNAL_H
+
+#define CONFIG_MMU
+
+#include <linux/init.h>
+#include <linux/kernel.h>
+#include <linux/mm_types.h>
+#include <linux/mm.h>
+#include <linux/bug.h>
+
+#define SLAB_TYPESAFE_BY_RCU	0
+#define SLAB_ACCOUNT		0
+
+static inline void might_sleep(void)
+{
+}
+
+static inline void mmap_assert_locked(struct mm_struct *)
+{
+}
+
+/*
+ * rwsem_is_locked() is only used in anon_vma_free() to synchronize against
+ * folio_lock_anon_vma_read(), which is not used in current tests.
+ *
+ * So just return 0 for simplification.
+ */
+static inline int rwsem_is_locked(struct rw_semaphore *sem)
+{
+	return 0;
+}
+
+static inline struct anon_vma *find_mergeable_anon_vma(struct vm_area_struct *vma)
+{
+	return NULL;
+}
+
+#ifndef pgoff_t
+#define pgoff_t unsigned long
+#endif
+static inline void vma_set_range(struct vm_area_struct *vma,
+					  unsigned long start, unsigned long end,
+					  pgoff_t pgoff)
+{
+	vma->vm_start = start;
+	vma->vm_end = end;
+	vma->vm_pgoff = pgoff;
+}
+
+void dump_anon_vma_interval_tree(struct anon_vma *anon_vma);
+extern int nr_allocated;
+#endif // __MM_ANON_VMA_INTERNAL_H
diff --git a/tools/testing/anon_vma/interval_tree.c b/tools/testing/anon_vma/interval_tree.c
new file mode 100644
index 000000000000..154c9ccbf3e1
--- /dev/null
+++ b/tools/testing/anon_vma/interval_tree.c
@@ -0,0 +1,53 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include "../../../mm/interval_tree.c"
+
+#ifdef ANON_VMA_INTERVAL_TREE_DEBUG
+enum child_dir {
+	left_child,
+	right_child,
+	root_node
+};
+
+typedef void (*dump_node)(struct rb_node *node, int level);
+
+void dump_avc(struct rb_node *node, int level)
+{
+	struct anon_vma_chain *avc;
+
+	avc = rb_entry(node, struct anon_vma_chain, rb);
+
+	printf(" -%02d [%lu, %lu] %lu\n", avc->vma->index,
+		avc_start_pgoff(avc), avc_last_pgoff(avc),
+		avc->rb_subtree_last);
+}
+
+void dump_rb_tree(struct rb_node *node, int level,
+		  enum child_dir state, dump_node print)
+{
+	char prefix[40] = "                                        ";
+
+	if (!node)
+		return;
+
+	dump_rb_tree(node->rb_right, level+1, right_child, print);
+
+	if (state == left_child)
+		printf("%.*s|\n", min_t(int, level * 2 + 2, ARRAY_SIZE(prefix)), prefix);
+
+	printf("%02d%.*s", level, min_t(int, level * 2, ARRAY_SIZE(prefix)), prefix);
+	(*print)(node, level);
+
+	if (state == right_child)
+		printf("%.*s|\n", min_t(int, level * 2 + 2, ARRAY_SIZE(prefix)), prefix);
+
+	dump_rb_tree(node->rb_left, level+1, left_child, print);
+}
+
+void dump_anon_vma_interval_tree(struct anon_vma *anon_vma)
+{
+	dump_rb_tree(anon_vma->rb_root.rb_root.rb_node, 0, root_node, dump_avc);
+}
+#else
+void dump_anon_vma_interval_tree(struct anon_vma *anon_vma) { return; }
+#endif
diff --git a/tools/testing/anon_vma/linux/atomic.h b/tools/testing/anon_vma/linux/atomic.h
new file mode 100644
index 000000000000..b9f7c2e91f15
--- /dev/null
+++ b/tools/testing/anon_vma/linux/atomic.h
@@ -0,0 +1,18 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __TOOLS_LINUX_ATOMIC_H
+#define __TOOLS_LINUX_ATOMIC_H
+
+#include <urcu/uatomic.h>
+
+#define atomic_t int32_t
+#define atomic_inc(x) uatomic_inc(x)
+#define atomic_read(x) uatomic_read(x)
+#define atomic_set(x, y) uatomic_set(x, y)
+
+static inline bool atomic_dec_and_test(atomic_t *v)
+{
+	return uatomic_sub_return(v, 1) == 0;
+}
+
+#endif	/* __TOOLS_LINUX_ATOMIC_H */
diff --git a/tools/testing/anon_vma/linux/fs.h b/tools/testing/anon_vma/linux/fs.h
new file mode 100644
index 000000000000..9e9addd3310c
--- /dev/null
+++ b/tools/testing/anon_vma/linux/fs.h
@@ -0,0 +1,6 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __TOOLS_LINUX_FS_H
+#define __TOOLS_LINUX_FS_H
+
+#endif /* __TOOLS_LINUX_FS_H */
diff --git a/tools/testing/anon_vma/linux/mm.h b/tools/testing/anon_vma/linux/mm.h
new file mode 100644
index 000000000000..3bfe232f298a
--- /dev/null
+++ b/tools/testing/anon_vma/linux/mm.h
@@ -0,0 +1,44 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __TOOLS_LINUX_MM_H
+#define __TOOLS_LINUX_MM_H
+
+#include <linux/kernel.h>
+#include <linux/mm_types.h>
+#include <linux/interval_tree_generic.h>
+#include <linux/types.h>
+#include "../../include/linux/mm.h"
+
+#define VM_WARN_ON(_expr) (WARN_ON(_expr))
+#define VM_BUG_ON(_expr) (BUG_ON(_expr))
+#define VM_BUG_ON_VMA(_expr, _vma) (BUG_ON(_expr))
+
+static inline unsigned long vma_pages(struct vm_area_struct *vma)
+{
+	return (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
+}
+
+#include <linux/anon_vma.h>
+
+#define vma_interval_tree_foreach(vma, root, start, last)		\
+	for (vma = vma_interval_tree_iter_first(root, start, last);	\
+	     vma; vma = vma_interval_tree_iter_next(vma, start, last))
+
+void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
+				   struct rb_root_cached *root);
+void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
+				   struct rb_root_cached *root);
+struct anon_vma_chain *
+anon_vma_interval_tree_iter_first(struct rb_root_cached *root,
+				  unsigned long start, unsigned long last);
+struct anon_vma_chain *anon_vma_interval_tree_iter_next(
+	struct anon_vma_chain *node, unsigned long start, unsigned long last);
+#ifdef CONFIG_DEBUG_VM_RB
+void anon_vma_interval_tree_verify(struct anon_vma_chain *node);
+#endif
+
+#define anon_vma_interval_tree_foreach(avc, root, start, last)		 \
+	for (avc = anon_vma_interval_tree_iter_first(root, start, last); \
+	     avc; avc = anon_vma_interval_tree_iter_next(avc, start, last))
+
+#endif /* __TOOLS_LINUX_MM_H */
diff --git a/tools/testing/anon_vma/linux/mm_types.h b/tools/testing/anon_vma/linux/mm_types.h
new file mode 100644
index 000000000000..9cfbedecdc35
--- /dev/null
+++ b/tools/testing/anon_vma/linux/mm_types.h
@@ -0,0 +1,57 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __TOOLS_LINUX_MM_TYPES_H
+#define __TOOLS_LINUX_MM_TYPES_H
+
+#include <linux/list.h>
+#include <linux/rbtree.h>
+#include <linux/slab.h>
+#include <linux/rwsem.h>
+#include <linux/spinlock.h>
+#include <linux/atomic.h>
+
+struct mm_struct {
+		spinlock_t page_table_lock;
+};
+
+struct vm_area_struct {
+	/* For test purpose */
+	int	index;
+	/* VMA covers [vm_start; vm_end) addresses within mm */
+	unsigned long vm_start;
+	unsigned long vm_end;
+
+	/* The address space we belong to. */
+	struct mm_struct *vm_mm;
+
+	/*
+	 * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
+	 * list, after a COW of one of the file pages.	A MAP_SHARED vma
+	 * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
+	 * or brk vma (with NULL file) can only be in an anon_vma list.
+	 */
+	struct list_head anon_vma_chain; /* Serialized by mmap_lock &
+					  * page_table_lock */
+	struct anon_vma *anon_vma;	/* Serialized by page_table_lock */
+	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
+					   units */
+	/*
+	 * For areas with an address space and backing store,
+	 * linkage into the address_space->i_mmap interval tree.
+	 *
+	 */
+	struct {
+		struct rb_node rb;
+		unsigned long rb_subtree_last;
+	} shared;
+#ifdef CONFIG_ANON_VMA_NAME
+	/*
+	 * For private and shared anonymous mappings, a pointer to a null
+	 * terminated string containing the name given to the vma, or NULL if
+	 * unnamed. Serialized by mmap_lock. Use anon_vma_name to access.
+	 */
+	struct anon_vma_name *anon_name;
+#endif
+};
+
+#endif	/* __TOOLS_LINUX_MM_TYPES_H */
diff --git a/tools/testing/anon_vma/linux/mmzone.h b/tools/testing/anon_vma/linux/mmzone.h
new file mode 100644
index 000000000000..e6be2d214777
--- /dev/null
+++ b/tools/testing/anon_vma/linux/mmzone.h
@@ -0,0 +1,6 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __TOOLS_LINUX_MMZONE_H
+#define __TOOLS_LINUX_MMZONE_H
+
+#endif /* __TOOLS_LINUX_MMZONE_H */
diff --git a/tools/testing/anon_vma/linux/rmap.h b/tools/testing/anon_vma/linux/rmap.h
new file mode 100644
index 000000000000..d29511ae0294
--- /dev/null
+++ b/tools/testing/anon_vma/linux/rmap.h
@@ -0,0 +1,8 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#ifndef __TOOLS_LINUX_RMAP_H
+#define __TOOLS_LINUX_RMAP_H
+
+#include <linux/anon_vma.h>
+
+#endif /* __TOOLS_LINUX_RMAP_H */
diff --git a/tools/testing/shared/linux/anon_vma.h b/tools/testing/shared/linux/anon_vma.h
new file mode 100644
index 000000000000..a5bac325402a
--- /dev/null
+++ b/tools/testing/shared/linux/anon_vma.h
@@ -0,0 +1,7 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#ifndef _TEST_ANON_VMA_H
+#define _TEST_ANON_VMA_H
+
+#include "../../../../include/linux/anon_vma.h"
+
+#endif /* _TEST_ANON_VMA_H */
-- 
2.34.1