From patchwork Mon Mar 10 07:49:31 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 14009361 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 7FA54C28B2E for ; Mon, 10 Mar 2025 07:49:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8AA1A280002; Mon, 10 Mar 2025 03:49:50 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 85A8E280001; Mon, 10 Mar 2025 03:49:50 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 722C8280002; Mon, 10 Mar 2025 03:49:50 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 53084280001 for ; Mon, 10 Mar 2025 03:49:50 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 8C2B0160B7D for ; Mon, 10 Mar 2025 07:49:51 +0000 (UTC) X-FDA: 83204867382.10.4F91C04 Received: from mail-ej1-f53.google.com (mail-ej1-f53.google.com [209.85.218.53]) by imf30.hostedemail.com (Postfix) with ESMTP id B8C3F80004 for ; Mon, 10 Mar 2025 07:49:49 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=RY3XYVRp; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf30.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.53 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=1741592989; 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:references:dkim-signature; bh=iWS3TPtV4Y8lCeNboiMnbnAQUEXZWB6vFuQseQZNsTw=; b=TevM+uGB19eJSb87jfF2CSiWgecmMyBS2qE31/Nn4yXqXdkgJZN/r869nXMaEywa31pPWW j2NIIHnH71vCp/Gr8RVqN6YabrvrgdEACHf5Cr1+Omb2f5aZ1ISlcXbcIyrdA9lyJS+xyT 47juwoMHozCKMeR9XFaqlku6A2knogY= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1741592989; a=rsa-sha256; cv=none; b=KYOxZBexKrHytJ3tGMZ5M/x/bSErluYI8zMbstac9QZW64AdnSukASlcQNoC+rdwTAiuQV 3nOTd9ZTQkSE5qrIo2jjfU3k7515me2e5PzdZOV7AGt5HDBqNiKOQir6dEJ7P2b4I0cTW7 MzrwI9mseXqSYPzdS6vHWf4cNYMz4AE= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=RY3XYVRp; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf30.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.53 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com Received: by mail-ej1-f53.google.com with SMTP id a640c23a62f3a-ac2ae81dd81so31723666b.0 for ; Mon, 10 Mar 2025 00:49:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741592988; x=1742197788; darn=kvack.org; h=message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=iWS3TPtV4Y8lCeNboiMnbnAQUEXZWB6vFuQseQZNsTw=; b=RY3XYVRpaISHIDGlTP33O7qQJ1utMS8J+21d2c89GvyV7gSDzob7wUo7JHScfh/vGT LsTv0NpMLO+ViIcalPCn5ZuIBoxvZebDswg8jrVzE7Tm4lNgaoOrHbkxhSEfhJ5Mqz8i PaMe/wPaSIWFvmkGtB3jrV3uwaomD0SjXCa4EMtEH+UdTl0EIEo7wIpxQVLNYCOCBKP4 JUqeekm9YiR31dCpNcR32vCxpJu5MFP5JXWNPChZ2PwLqR8W/Q/MadfM95+U+u2dEUsT K1b2PHhCCocsWFxJVBvvG6XXu/N5wSuGV0xs4O1tbSC+BUDDLku+nInfWRjy3cn0olpS 7cAw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741592988; x=1742197788; h=message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=iWS3TPtV4Y8lCeNboiMnbnAQUEXZWB6vFuQseQZNsTw=; b=go+KfhXIHbyj8ICjYcuYp5g59iY8qRzUtmQQ9qSVqCVwgDSjgcpeQ/uc/WaMhhZyvF cTX5aeesU72lRToumECbeVW2ol9ja8Bsa4EvsY8O01GJqlBmnLnubntqy6AjuVvYHY0c FLvgwPj4h2HB4VHPR1V7ce1yy1ctZ3UxaKkduCTzF6BAJqqeNjdX06qiT1uTVQPtLOc8 6PFSj7FW0a/Nw660DT12U/KfzGs4DKf2bLt8AVlfvmtFYRRxhsz7viYmmYidQ+WWWZmF kvRp3R4VfHvrd3Qvi/yU2fHrbN0n9tIRS8HdTg1uK+XtaXmQT0ek91yFaKuHC3IQ68sY +fZg== X-Forwarded-Encrypted: i=1; AJvYcCXYUhzasLsowYiCjYa/Z38k2KwKAVnOnX/SSbKgAipGOHVZjS+OcPOFKrN6273XeKn3knb7ourn2g==@kvack.org X-Gm-Message-State: AOJu0Yz65Xf79fZ/qF+AB6A1FMhmS7UCybflSRp2/GylCNpj5Z5164SL 6fmcvCWs6vBV1RxawBzukIUYk1Zd1gROIWqf13030QgmI/EdmQ4+ X-Gm-Gg: ASbGnctqnoA/raImLFHNuJc4P4m2wQJn9rw+zCsH+EXGtE7baKLc6xnEQex7tWgTG9+ WiH6aU2jxlFAFk7ZSorqs1QBl7yQAVXTMHPQ0Umu3E3Rb3MNgwJcDwV8FEdepjBIlsw6tgn616e Gv6OK1v7ULoxWUGGiaZbKRIfdAN4Kr/HKY0mMqLgICBj83EDFIh9aw4qhAcR54BEla/s1++G54v ITGffuyIIoDpt0pKRXmocXNsvleP+ksxHSmI22Gmu3eB7KluRKEm9D/aCP6Zc4S/WgQFTn32vP6 dlDtP3bBw8zXuXENNBENZg8iT4lFLcjk56fMuXH6Z1i7gS2t2gULcdw= X-Google-Smtp-Source: AGHT+IFAzQimvEYLzQuuERXCl4U1GZR68yvUb4gIVSK9JA8BEQ6E3xAlP+CLB2rBZZBYIE4eehq5jg== X-Received: by 2002:a17:907:9718:b0:ac2:a151:c300 with SMTP id a640c23a62f3a-ac2a151cdb4mr332378066b.20.1741592987778; Mon, 10 Mar 2025 00:49:47 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ac23988b64asm717058566b.155.2025.03.10.00.49.47 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Mar 2025 00:49:47 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org Cc: willy@infradead.org, michel@lespinasse.org, linux-mm@kvack.org, Wei Yang Subject: [Patch v2 0/7] lib/interval_tree: add some test cases and cleanup Date: Mon, 10 Mar 2025 07:49:31 +0000 Message-Id: <20250310074938.26756-1-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 X-Stat-Signature: i7ixszfwck9r9414fam5hxihgf5tio5t X-Rspam-User: X-Rspamd-Queue-Id: B8C3F80004 X-Rspamd-Server: rspam04 X-HE-Tag: 1741592989-580419 X-HE-Meta: U2FsdGVkX1+pMMg0DERXWdWPdDQFpGopUsourzRDJWNLUAhODh0DVqGUrguY6BQifz3UBNdkSxdwbQqyN9i3XmHdytrXyR8eYd0NzYiCRx4wRugHmZW51bj1FdVAnVyToCDJ4syDfvMNPool40Hmk7yIqj2IZL3mF1owEYspFbHIiloZj5DjIgIfIyUNAWmbPWzhpmtsa3lfAbugH8IK7LC5pYj0PkXj1MYRXKOoBvob6wBRj6nWK/oy0p47/dYH1Y71DjNbUEwS1J64jui+5umc+Fm4vSh1clYWjBmujrfqqU5L9IQOmzKBLWjUaEHPmgObuxHIRf2XtfQNRx8a4Zo9znYQOl32+KT0WHmOHe2ILH74f7gtJC2lgN7KUM6rLnlgjNcTGg08iT7WL6bn5z1wDVVvxQmQWoE1hQ9igXkIhyPPhjbSAOHDW71/HFnK8nCpCy5o1ekqTlEASdxsZl13JvD8QZ9OqGZkLiUNv3fBXPj0JRDsCh0MgYkc0Gk6tGD4tjVXoIn0jL2FRkTbrXgQjXQhkadfaGxiElGZTx0m+2L+8Wak5zWRyNVHnGXnlAEchjth5JhCCaz+s+vt3aZ3mT+9boFnf72r4j2yp9smR4PBlf7coAuEy+7ZheEAEx3e435Fhh25vujWKDvJB3GliHwCUDNFBia7R1yrS7sKB/qgx32JKknfHyUFkxChnxhGd0fQraTqwqqX3is6k4QV1irnecoLJrc4UrH4vJHtzrLBlbc7YMxyk5+mSX95YCSQ8yjXrG3q+1rHXjoGoqdkAM+Ng5h3Y26rEUwp/z8spqi8l4gqlcZw0cLEK1JzsEeKjeu7xIr3/83oHcOhiMZmsQ6DuyEgwdpeOIvfLRSx5fSyzyDmZP4DuE2fcxn4lpIRK1RQKagbOCuQ2e0XvKWuQPf5Btk37npU2sGB4iEVlvPDU2JrurTGVS4ZbPi86/i0X8NnNtgJ85rxO0g cQvFRxSI fZaIEozaXPcTH2XK3rvlPCP6LGDr+gAxtyB7sdBhtPXzNPqxK0vheDydfp3mc5z0FToGKh+xvSQNC9+ol8mbNbVbJt+ugy3tjanjm4xC7B69coZqK9rtjLla1JTvAIZqVT+SRBzfY/uLECkXxZKrRGDFKKo04ga1R4wK472phw0AOYr7jXoqTelKJuh/UwuiCsUKQrpEacb8CJD0NKC8jXBe9Fe75MGTYhqITcrCLPL7uTQ+uBYuapnLLkqROZ3fWlGvIY4cQbNgW7idKCUmbjN7Rb11XxDOAfjj3MtWcVktUdFG9eFMxrzqY7QZKNskRzOGxd/pGc0KqP7Plu0fCVkdTD/NXqGJsYlgJ8+107LhI7zX08YfHVBrkO/GCwUHzQgDUKQLBl9kXI1FyOWmkf9OEaVw9Vq8qebI/8BhPhUGmdUIherXY3eBugUdftHCc98tEVyYYWejbbfWrjKB4389+C2v8ZdRpFKoBm5D9lZU1hv4dh0URBl0ehpfu/NX8g+DE87foskr75GYnrnhk8rO0bk2MVvFfY4obdorscE9R0iy2mxJcoqVG6A== 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: Originally, I sent an interval tree cleanup[1], but lack of reasonable test. As Matthew suggested, this patch set includes proper test to exercise the change in interval tree. Since rbtree/augmented tree/interval tree share similar data structure, besides new cases for interval tree, this patch set also does cleanup for others. Patch 1: There are test cases as kernel module, this patch enable them in userland. This would help for testing and debugging. Patch 2: Split cases for better reading. And prepare for new cases adding. Patch 3: Add random seed to cover different situations Patch 4: Add case for interval_tree_iter_xxx() helper Patch 5: Add case for span iteration Patch 6: is the original cleanup Patch 7: fix the comment of interval_tree_span_iter_next_gap() v2: * move definition of container_of() into container_of.h * fix compile warning by defining seed with ullong [1]: https://lkml.kernel.org/r/20250224022239.21976-1-richard.weiyang@gmail.com Wei Yang (7): lib/rbtree: enable userland test suite for rbtree related data structure lib/rbtree: split tests lib/rbtree: add random seed lib/interval_tree: add test case for interval_tree_iter_xxx() helpers lib/interval_tree: add test case for span iteration lib/interval_tree: skip the check before go to the right subtree lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap() include/linux/interval_tree_generic.h | 8 +- include/linux/types.h | 1 + lib/interval_tree.c | 12 +- lib/interval_tree_test.c | 237 ++++++++++++++++-- lib/rbtree_test.c | 30 ++- tools/include/asm/timex.h | 13 + tools/include/linux/bitmap.h | 21 ++ tools/include/linux/container_of.h | 18 ++ tools/include/linux/kernel.h | 14 +- tools/include/linux/math64.h | 5 + tools/include/linux/moduleparam.h | 7 + tools/include/linux/prandom.h | 51 ++++ tools/include/linux/slab.h | 1 + tools/include/linux/types.h | 2 + tools/lib/bitmap.c | 20 ++ tools/lib/slab.c | 16 ++ tools/testing/rbtree/Makefile | 33 +++ tools/testing/rbtree/interval_tree_test.c | 58 +++++ tools/testing/rbtree/rbtree_test.c | 48 ++++ tools/testing/rbtree/test.h | 4 + tools/testing/shared/interval_tree-shim.c | 5 + tools/testing/shared/linux/interval_tree.h | 7 + .../shared/linux/interval_tree_generic.h | 2 + tools/testing/shared/linux/rbtree.h | 8 + tools/testing/shared/linux/rbtree_augmented.h | 7 + tools/testing/shared/linux/rbtree_types.h | 8 + tools/testing/shared/rbtree-shim.c | 6 + 27 files changed, 600 insertions(+), 42 deletions(-) create mode 100644 tools/include/asm/timex.h create mode 100644 tools/include/linux/container_of.h create mode 100644 tools/include/linux/moduleparam.h create mode 100644 tools/include/linux/prandom.h create mode 100644 tools/testing/rbtree/Makefile create mode 100644 tools/testing/rbtree/interval_tree_test.c create mode 100644 tools/testing/rbtree/rbtree_test.c create mode 100644 tools/testing/rbtree/test.h create mode 100644 tools/testing/shared/interval_tree-shim.c create mode 100644 tools/testing/shared/linux/interval_tree.h create mode 100644 tools/testing/shared/linux/interval_tree_generic.h create mode 100644 tools/testing/shared/linux/rbtree.h create mode 100644 tools/testing/shared/linux/rbtree_augmented.h create mode 100644 tools/testing/shared/linux/rbtree_types.h create mode 100644 tools/testing/shared/rbtree-shim.c