From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id DA615C3ABA9 for ; Tue, 29 Apr 2025 09:07:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1857D6B0008; Tue, 29 Apr 2025 05:07:29 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 134486B000C; Tue, 29 Apr 2025 05:07:29 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E2EB66B000A; Tue, 29 Apr 2025 05:07:28 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id BBD856B0007 for ; Tue, 29 Apr 2025 05:07:28 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 80A751A16F7 for ; Tue, 29 Apr 2025 09:07:30 +0000 (UTC) X-FDA: 83386503060.05.CAD58CD Received: from mail-ej1-f48.google.com (mail-ej1-f48.google.com [209.85.218.48]) by imf13.hostedemail.com (Postfix) with ESMTP id 8038220002 for ; Tue, 29 Apr 2025 09:07:28 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=dEP+rV14; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1745917648; a=rsa-sha256; cv=none; b=jXd+UaPOIINo6OKNThEr26VuRxC3+Ozy9pUHBLVts2PenC5XOKwNGCFS9Dnf59YTw/mNuM EUwcbhb2d+L8mTcI0j9jLox1oQGWo1mmJYunW35UIOCN8B/MB7TP61eralH+lOWwveAAxP Vk+EHQwA/XcU5Itq6wJUemd1ChROhac= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=dEP+rV14; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.48 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1745917648; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=yOTSWhenvL+XK/IByjWMLhN2UaaIz8/Pf2nFffo6KSg=; b=ZGq34YfB4XxulRgueJC3zB15q+nXWqb/Yqm0b1B7R9JgxRrqzUy7ojaj+SQxKXOaC3UuHJ OHTOSXDnVzeGtDyFnonmzFDnMH/U1T9Y5fyiZRDBjvL2b9+vien1hyjuDm4K1QZNKaDO/B BzTqENgFzgvJSdbgQOLu2jtFDcI7mus= Received: by mail-ej1-f48.google.com with SMTP id a640c23a62f3a-ac7bd86f637so1290046266b.1 for ; Tue, 29 Apr 2025 02:07:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1745917647; x=1746522447; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=yOTSWhenvL+XK/IByjWMLhN2UaaIz8/Pf2nFffo6KSg=; b=dEP+rV14TVKG46BQw+j10FjbH8AXbbc9XG+opZPG8v25pZauM9OC7jLSyxtH7nOqtS rA94m3VRV1qL1DzsEMTIcUViE3je9wqehEMHnF4jXqtQL0W1sqd5VhC/fnrDumbfvnnn g3ZzFwFaBF0ZmyY8qU+xD9VIKie20hcZOR2lAHB2N0hGVFo5NkkAgbCL5jkOtaMhICrX D4EtjQNYFIvayKy/d4biNY5EjCnQJTenaKUV3PsnuevC0qz1/C7ZDCBb7anXJ0sa5GX7 x4x9mQm1ujF1T6Y/bBPeDEA7KTAGRaebOBiSlX4a24Ct8Ywt52WKaW2UG74E7RKSIfqd 89Lw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1745917647; x=1746522447; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=yOTSWhenvL+XK/IByjWMLhN2UaaIz8/Pf2nFffo6KSg=; b=BVbPJZDXxmli0P1a22SyVIaeJC1h2CaJkpvOlIxg1jO+0lDRD6TnKDVDuTphIk348P MCj5cbvVYNOC/dJFAB4HoSDlcxpmOPHu1S1HlTfKsIWQYjVA6ljcQUJeQp8iTthsK2Zq 7WCpdgMHYnsMhaldL8JJ8H/iAvKxqaU/hhx99N8GRH0NsvP7a81V089UYJ17PpmdudOC tucKzuX8Kx0jC6FWEsWmHQ4spRQLK5/PJ0OOkeAz5K0n8YBx6SwOPR6ImcTfPAw2mPiT /412FY3MuT+A5UXTjgMSZV16dDGqvY9CSVPTe/JcesqLeSfLvhx5Cym+mmJ8s7SGWqjI q1sw== X-Forwarded-Encrypted: i=1; AJvYcCU3ksClxL1v8m19ytwkxvmUOPel/g9bNs2HpZo1F7HjqqguUakaq6gut6hK+/1gxjoQaFGHWwNDiA==@kvack.org X-Gm-Message-State: AOJu0YzPZRxHQ3Qy/m/xNt++d9lPlsrWI3hkYYuQ+RluwH4X9lDkPCSq H7YICuTSOXE+L02TOFKPHr665R1JJwsRvUvD//+RL5rPgZjblVuD+e2Yyw== X-Gm-Gg: ASbGncsvRQxkL7+P/o7qa/MQVaxtjdtSh67GivUPvrg0RB0EH3if4K1LR7Knoc7b5Qb tZVwJ0+CA6AAPTsq+tq6zg6h07RpIk+2dWzYvkYYRnudJR/8qUsSA/TKq/diu6xkb2d8FRM7cjB UsRxrZLeqmZYJljTmDnt9pvmVWmA2z28t01Zj73PHFiLhvAZDnFMKCHemDJT5dsSzN6fyn6bqai PH3jsiT5Kydp5Pc2T8Skem2XgAccx4Fcmhs63hqCbyE8Fs3XM7YIL1caFh8wij5ihbwsUY1kTt9 06/VqnK/R4zstzw3Z+22vFJt8DMZXbJ24PJGbri8 X-Google-Smtp-Source: AGHT+IF12mUUo8reCVZpSL1G3qcw0OcS7Kvvf6fMPQ7t2+pOvgQENZosCS21whC3BfSc19HCa4xa5A== X-Received: by 2002:a17:907:9693:b0:abf:742e:1fde with SMTP id a640c23a62f3a-acec6a76540mr216040466b.14.1745917646672; Tue, 29 Apr 2025 02:07:26 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ace6edb0becsm741674066b.167.2025.04.29.02.07.25 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 29 Apr 2025 02:07:25 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: david@redhat.com, lorenzo.stoakes@oracle.com, riel@surriel.com, vbabka@suse.cz, harry.yoo@oracle.com, jannh@google.com, baohua@kernel.org, linux-mm@kvack.org, Wei Yang Subject: [RFC Patch 2/5] anon_vma: add skeleton code for userland testing of anon_vma logic Date: Tue, 29 Apr 2025 09:06:36 +0000 Message-Id: <20250429090639.784-3-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20250429090639.784-1-richard.weiyang@gmail.com> References: <20250429090639.784-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: 8038220002 X-Rspam-User: X-Rspamd-Server: rspam07 X-Stat-Signature: p4e4izc6xqaweyca3hjq6j8d8xa1qqeg X-HE-Tag: 1745917648-556615 X-HE-Meta: U2FsdGVkX19pRVBk9NZlwYNNkYOkmeIarVt2prq2JSwAe+IqkLWhLIlqX1vo6cX4gagEY8LJi9Yi7RAusu2f9Pu/jSwBzEj4QF0Bqi50XLPaJR0fv+Uaie8lrUp/922jH9RBCNq2u7n4Gk72IYb9GsvPFuSIcdgz1C+HBELFE5v/u9hsXxK/XplyC3sGdJW2Yo26Yxl1pqtDFoWuZgCbXjvj4oBZm6x5Ph/X/V6U6Ij/2uoOmdG/6rxN0EMZzShhvSQF2Pg1eWLtZD3ECyAfFFC1DuMdmoBrFsbFIFC1ZrHXTdIlMY6nXZJuo1W+EGwRIYfjmY8Pp6bMI9gTd3/W1dyBiwrOc906h0v3zHw2KBKl0BqoVEiQtJNQfIBgONzCmBchWRMoo0m/U6PyQCSyDQSG4ASRs2qT9OIZYRQJMYP9xDeNopIrYU/HlZrajRRvqVyKTpuIA6W+Rb+A7YnonOD4AsPSFwX1RjH1ASowI3B/6PUZszHuN6MCPZaMnTcQIk1qAIq/wn/8RY8jz109WVrrmpW5aoICpM5xqLGDYaalBJZ8s+UTVtxIyos/pHaR3hRxdeCSqCgZQX/NzD2ueyLrXEDoRi8iguhgq6D4OOxXaq8Fbrs7k5JUXesGlj41++X4Za0DneTzwJdaQvrmySb/6Kp8Ek7cH6x51YtH1lUhqpaXi4/Hq0hgOkRtLiOCVjFjy5BhLtzL0BDw1USbJJf9Bgmf2vNIRYoKAmJOlGqiAO2MRJKvcz5pmiyNbzzIqtNhj6wad14p0uxbWu3mQvXXLe1daAviv4CIIR27QnEBxIcj7kCU85AQy1AZWQ9NdXYLB62Y8+jK3370RRJL3ITvppYjIlkiYdxp8NTWosvGinDmT/oVtHUAiiKuxKG6p0nBGr2RDy5FiKOkYo6uPBvAjnv/1pVEhYaiSPcMPkw6tigTxXU+mqmpIsd6r+vZ/2EELpwPVplOfjN9FQy kcxyFMsD nLKy4ZEbk4lKXhkJ4JhQMMPkVq1fZKHzd1PVopDqyyzy15OU6rO6Z16KcCG4GLGpbYGgcw1PV0VD41VvaNO7kUwTCR1RxnHY9AAwU+wgHEA/g7qCGmbBlFK72epQquBNwySYvtjEQmK6fD95TN4nXT4U2OKiuRVRbnBMRP/4IvFC9c2mf0ge27PL968Bsvjh1ZL8sxReJ2PzcVTG36EjjbITE2slMReVv0JDhJnEO6SiCfH6d7uKJm62X29m4AWfrRXzDnXCGtJ4z4Wz0JRT8Hq+34/Vsxmk8KYwbc3rKj7cNOTuIJPfqTOvD06MzLBEV1O1sWT4aP4noY8r8wfsLJ/Ss5tTnuWC7QIXWTaChp731PmC8EnSchsNMoGlHsSSEZWM7qKw33TNXENLJqAFVV0JkNqFkHLbO8cGBk4YWsIoSJ+rR8062YeomhOJC26VJrR6B6uY7oOcvHcg4VL+pCBP2/tzGdxIpP7GJkkLngWFKFN0Ln7iZ7SamdOUJuScdBINbmpyXRS6FxAbdLK5uLDXRouhZDymUMmCS2INClJjgNnlllBkDGyEqU9fz4bTpwHrU9Zfp1b8omYIRd4CHRJccYdnZ/+HYWlQJBk1msAvZnPKnRmOtGRVOwLRyEG6QwNBbIR0GnVyJwfR86QQJtdKIZYVzKBSFAjnpU2Hml6eA+CRQHzFzb+79eQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 Cc: Lorenzo Stoakes Cc: Jann Horn Cc: David Hildenbrand Cc: Barry Song Cc: Rik van Riel Cc: Vlastimil Babka Cc: Harry Yoo --- 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 +#include +#include +#include + +#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 +#include +#include +#include +#include + +#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 + +#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 +#include +#include +#include +#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 + +#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 +#include +#include +#include +#include +#include + +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 + +#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