Changes in Makefile

3fec86f8 - xarray: add xas_try_split() to split a multi-index entry

Fri, 07 Mar 2025 17:39:54 +0000

xarray: add xas_try_split() to split a multi-index entryPatch series "Buddy allocator like (or non-uniform) folio split", v10.This patchset adds a new buddy allocator like (or non-uniform) large foliosplit from a order-n folio to order-m with m < n. It reduces1. the total number of after-split folios from 2^(n-m) to n-m+1;2. the amount of memory needed for multi-index xarray split from 2^(n/6-m/6) to n/6-m/6, assuming XA_CHUNK_SHIFT=6;3. keep more large folios after a split from all order-m folios to order-(n-1) to order-m folios.For example, to split an order-9 to order-0, folio split generates 10 (or11 for anonymous memory) folios instead of 512, allocates 1 xa_nodeinstead of 8, and leaves 1 order-8, 1 order-7, ..., 1 order-1 and 2order-0 folios (or 4 order-0 for anonymous memory) instead of 512 order-0folios.Instead of duplicating existing split_huge_page*() code, __folio_split()is introduced as the shared backend code for bothsplit_huge_page_to_list_to_order() and folio_split(). __folio_split() cansupport both uniform split and buddy allocator like (or non-uniform)split. All existing split_huge_page*() users can be gradually convertedto use folio_split() if possible. In this patchset, I convertedtruncate_inode_partial_folio() to use folio_split().xfstests quick group passed for both tmpfs and xfs. I alsosemi-replicated Hugh's test[12] and ran it without any issue for almost 24hours.This patch (of 8):A preparation patch for non-uniform folio split, which always split afolio into half iteratively, and minimal xarray entry split.Currently, xas_split_alloc() and xas_split() always split all slots from amulti-index entry. They cost the same number of xa_node as theto-be-split slots. For example, to split an order-9 entry, which takes2^(9-6)=8 slots, assuming XA_CHUNK_SHIFT is 6 (!CONFIG_BASE_SMALL), 8xa_node are needed. Instead xas_try_split() is intended to be usediteratively to split the order-9 entry into 2 order-8 entries, then splitone order-8 entry, based on the given index, to 2 order-7 entries, ...,and split one order-1 entry to 2 order-0 entries. When splitting theorder-6 entry and a new xa_node is needed, xas_try_split() will try toallocate one if possible. As a result, xas_try_split() would only need 1xa_node instead of 8.When a new xa_node is needed during the split, xas_try_split() can try toallocate one but no more. -ENOMEM will be return if a node cannot beallocated. -EINVAL will be return if a sibling node is split or cascadesplit happens, where two or more new nodes are needed, and these are notsupported by xas_try_split().xas_split_alloc() and xas_split() split an order-9 to order-0: --------------------------------- | | | | | | | | | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | | | | | | | | --------------------------------- | | | | ------- --- --- ------- | | ... | | V V V V----------- ----------- ----------- -----------| xa_node | | xa_node | ... | xa_node | | xa_node |----------- ----------- ----------- -----------xas_try_split() splits an order-9 to order-0: --------------------------------- | | | | | | | | | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | | | | | | | | --------------------------------- | | V-----------| xa_node |-----------Link: https://lkml.kernel.org/r/20250307174001.242794-1-ziy@nvidia.comLink: https://lkml.kernel.org/r/20250307174001.242794-2-ziy@nvidia.comSigned-off-by: Zi Yan Cc: Baolin Wang Cc: David Hildenbrand Cc: Hugh Dickins Cc: John Hubbard Cc: Kefeng Wang Cc: Kirill A. Shuemov Cc: Miaohe Lin Cc: Matthew Wilcox Cc: Ryan Roberts Cc: Yang Shi Cc: Yu Zhao Cc: Zi Yan Cc: Kairui Song Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/Makefile

74579d8d - tools: separate out shared radix-tree components

Mon, 29 Jul 2024 11:50:40 +0000

tools: separate out shared radix-tree componentsThe core components contained within the radix-tree tests which provideshims for kernel headers and access to the maple tree are useful fortesting other things, so separate them out and make the radix tree testsdependent on the shared components.This lays the groundwork for us to add VMA tests of the newly introducedvma.c file.Link: https://lkml.kernel.org/r/1ee720c265808168e0d75608e687607d77c36719.1722251717.git.lorenzo.stoakes@oracle.comSigned-off-by: Lorenzo Stoakes Acked-by: Vlastimil Babka Reviewed-by: Liam R. Howlett Cc: Alexander Viro Cc: Brendan Higgins Cc: Christian Brauner Cc: David Gow Cc: Eric W. Biederman Cc: Jan Kara Cc: Kees Cook Cc: Matthew Wilcox (Oracle) Cc: Rae Moar Cc: SeongJae Park Cc: Shuah Khan Cc: Suren Baghdasaryan Cc: Pengfei Xu Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/Makefile

692a68ee - radix tree test suite: put definition of bitmap_clear() into lib/bitmap.c

Wed, 10 Jul 2024 17:27:01 +0000

radix tree test suite: put definition of bitmap_clear() into lib/bitmap.cIn tools/ directory, function bitmap_clear() is currently only used inobject file tools/testing/radix-tree/xarray.o.But instead of keeping a bitmap.c with only bitmap_clear() definition inradix-tree's own directory, it would be more proper to put it in commondirectory lib/.Sync the kernel definition and link some related libs, no functionalchange is expected.Signed-off-by: Wei Yang CC: Matthew Wilcox CC: Yury Norov Signed-off-by: Yury Norov List of files: /linux-6.15/tools/testing/radix-tree/Makefile

bde1597d - radix-tree: move declarations to header

Tue, 16 May 2023 19:41:54 +0000

radix-tree: move declarations to headerThe xarray.c file contains the only call to radix_tree_node_rcu_free(),and it comes with its own extern declaration for it. This means thefunction definition causes a missing-prototype warning:lib/radix-tree.c:288:6: error: no previous prototype for 'radix_tree_node_rcu_free' [-Werror=missing-prototypes]Instead, move the declaration for this function to a new header that canbe included by both, and do the same for the radix_tree_node_cachepvariable that has the same underlying problem but does not cause a warningwith gcc.[zhangpeng.00@bytedance.com: fix building radix tree test suite] Link: https://lkml.kernel.org/r/20230521095450.21332-1-zhangpeng.00@bytedance.comLink: https://lkml.kernel.org/r/20230516194212.548910-1-arnd@kernel.orgSigned-off-by: Arnd Bergmann Signed-off-by: Peng Zhang Cc: Matthew Wilcox (Oracle) Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/Makefile

120b1162 - maple_tree: reorganize testing to restore module testing

Fri, 28 Oct 2022 18:04:30 +0000

maple_tree: reorganize testing to restore module testingAlong the development cycle, the testing code support for module/in-kernelcompiles was removed. Restore this functionality by moving any internalAPI tests to the userspace side, as well as threading tests. Fix thelockdep issues and add a way to reduce memory usage so the tests cancomplete with KASAN + memleak detection. Make the tests work on 32 bithosts where possible and detect 32 bit hosts in the radix test suite.[akpm@linux-foundation.org: fix module export][akpm@linux-foundation.org: fix it some more][liam.howlett@oracle.com: fix compile warnings on 32bit build in check_find()] Link: https://lkml.kernel.org/r/20221107203816.1260327-1-Liam.Howlett@oracle.comLink: https://lkml.kernel.org/r/20221028180415.3074673-1-Liam.Howlett@oracle.comSigned-off-by: Liam R. Howlett Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/Makefile

e15e06a8 - lib/test_maple_tree: add testing for maple tree

Tue, 06 Sep 2022 19:48:45 +0000

lib/test_maple_tree: add testing for maple treeThis is a test suite that uses the radix test infrastructure. It has beensplit into its own commit to allow for easier review of the maple treecode.The testing includes:- Allocation of nodes- gfp flag allocation checks- Expansion & contraction of tree- preallocation checks- tree navigation by next/prev- tree navigation by iterators (mas_for_each, etc)- Number of nodes for a given number of entries- Generic tree construction tests- Addition and removal of entries in forward and reverse numerical indexes- gap searching both forward and reverse- Combining gaps by overwriting entries in different ways- splitting right-most node- splitting left-most node- overwriting multiple slots- overwriting across different levels of the tree- overwriting the middle of a tree- causing a 3-way split up to the root by overwriting the last slot and first slot of different nodes and spanning different levels- RCU stress testing of the tree with threads- Duplication of the tree by entry count- Tests which were generated by fuzzers have been added.- A large number of tests which come from recording crashing in a VM and reconstructing the tree (see check_erase2_set())Link: https://lkml.kernel.org/r/20220906194824.2110408-8-Liam.Howlett@oracle.comSigned-off-by: Liam R. Howlett Tested-by: Yu Zhao Cc: Catalin Marinas Cc: David Hildenbrand Cc: David Howells Cc: Davidlohr Bueso Cc: "Matthew Wilcox (Oracle)" Cc: SeongJae Park Cc: Sven Schnelle Cc: Vlastimil Babka Cc: Will Deacon Signed-off-by: Andrew Morton List of files: /linux-6.15/tools/testing/radix-tree/Makefile

aa0eab86 - tools: Move gfp.h and slab.h from radix-tree to lib

Wed, 02 Feb 2022 11:03:00 +0000

tools: Move gfp.h and slab.h from radix-tree to libMerge radix-tree definitions from gfp.h and slab.h with thesein tools/lib, so they can be used in other test suites.Fix style issues in slab.h. Update radix-tree test files.Signed-off-by: Karolina Drobnik Signed-off-by: Mike Rapoport Link: https://lore.kernel.org/r/b76ddb8a12fdf9870b55c1401213e44f5e0d0da3.1643796665.git.karolinadrobnik@gmail.com List of files: /linux-6.15/tools/testing/radix-tree/Makefile

7e934cf5 - xarray: Fix early termination of xas_for_each_marked

Thu, 12 Mar 2020 21:29:11 +0000

xarray: Fix early termination of xas_for_each_markedxas_for_each_marked() is using entry == NULL as a termination conditionof the iteration. When xas_for_each_marked() is used protected only byRCU, this can however race with xas_store(xas, NULL) in the followingway:TASK1 TASK2page_cache_delete() find_get_pages_range_tag() xas_for_each_marked() xas_find_marked() off = xas_find_chunk() xas_store(&xas, NULL) xas_init_marks(&xas); ... rcu_assign_pointer(*slot, NULL); entry = xa_entry(off);And thus xas_for_each_marked() terminates prematurely possibly leadingto missed entries in the iteration (translating to missing writeback ofsome pages or a similar problem).If we find a NULL entry that has been marked, skip it (unless we're tryingto allocate an entry).Reported-by: Jan Kara CC: stable@vger.kernel.orgFixes: ef8e5717db01 ("page cache: Convert delete_batch to XArray")Signed-off-by: Matthew Wilcox (Oracle) List of files: /linux-6.15/tools/testing/radix-tree/Makefile

eff3860b - radix tree: Don't return retry entries from lookup

Thu, 06 Dec 2018 13:19:13 +0000

radix tree: Don't return retry entries from lookupCommit 66ee620f06f9 ("idr: Permit any valid kernel pointer to be stored")changed the radix tree lookup so that it stops when reaching the bottomof the tree. However, the condition was added in the wrong place,making it possible to return retry entries to the caller. Reorder thetests to check for the retry entry before checking whether we're at thebottom of the tree. The retry entry should never be found in the treeroot, so it's safe to defer the check until the end of the loop.Add a regression test to the test-suite to be sure this doesn't comeback.Fixes: 66ee620f06f9 ("idr: Permit any valid kernel pointer to be stored")Reported-by: Greg Kurz Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

58d6ea30 - xarray: Add XArray unconditional store operations

Fri, 10 Nov 2017 20:15:08 +0000

xarray: Add XArray unconditional store operationsxa_store() differs from radix_tree_insert() in that it will overwrite anexisting element in the array rather than returning an error. This isthe behaviour which most users want, and those that want more complexbehaviour generally want to use the xas family of routines anyway.For memory allocation, xa_store() will first attempt to request memoryfrom the slab allocator; if memory is not immediately available, it willdrop the xa_lock and allocate memory, keeping a pointer in the xa_state.It does not use the per-CPU cache, although those will continue to existuntil all radix tree users are converted to the xarray.This patch also includes xa_erase() and __xa_erase() for a streamlinedway to store NULL. Since there is no need to allocate memory in orderto store a NULL in the XArray, we do not need to trouble the user withdeciding what memory allocation flags to use.Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

ad3d6c72 - xarray: Add XArray load operation

Tue, 07 Nov 2017 19:57:46 +0000

xarray: Add XArray load operationThe xa_load function brings with it a lot of infrastructure; xa_empty(),xa_is_err(), and large chunks of the XArray advanced API that are usedto implement xa_load.As the test-suite demonstrates, it is possible to use the XArray functionson a radix tree. The radix tree functions depend on the GFP flags beingstored in the root of the tree, so it's not possible to use the radixtree functions on an XArray.Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

f8d5d0cc - xarray: Add definition of struct xarray

Tue, 07 Nov 2017 21:30:10 +0000

xarray: Add definition of struct xarrayThis is a direct replacement for struct radix_tree_root. Some of thestruct members have changed name; convert those, and use a #define sothat radix_tree users continue to work without change.Signed-off-by: Matthew Wilcox Reviewed-by: Josef Bacik List of files: /linux-6.15/tools/testing/radix-tree/Makefile

02c02bf1 - xarray: Change definition of sibling entries

Sat, 04 Nov 2017 03:09:45 +0000

xarray: Change definition of sibling entriesInstead of storing a pointer to the slot containing the canonical entry,store the offset of the slot. Produces slightly more efficient code(~300 bytes) and simplifies the implementation.Signed-off-by: Matthew Wilcox Reviewed-by: Josef Bacik List of files: /linux-6.15/tools/testing/radix-tree/Makefile

8ab8ba38 - ida: Start new test_ida module

Mon, 18 Jun 2018 20:59:29 +0000

ida: Start new test_ida moduleStart transitioning the IDA tests into kernel space. Framework heavilycribbed from test_xarray.c.Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

d1c0d5e3 - radix tree test suite: Enable ubsan

Sat, 19 May 2018 20:30:54 +0000

radix tree test suite: Enable ubsanAdd support for the undefined behaviour sanitizer and fix the bugsthat ubsan pointed out. Nothing major, and all in the test suite,not the code.Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

8d9fa88e - radix tree test suite: fix mapshift build target

Fri, 18 May 2018 23:08:51 +0000

radix tree test suite: fix mapshift build targetCommit c6ce3e2fe3da ("radix tree test suite: Add config option for mapshift") introduced a phony makefile target called 'mapshift' that endsup generating the file generated/map-shift.h. This phony target wasthen added as a dependency of the top level 'targets' build target,which is what is run when you go to tools/testing/radix-tree and justtype 'make'.Unfortunately, this phony target doesn't actually work as a dependency,so you end up getting: $ make make: *** No rule to make target 'generated/map-shift.h', needed by 'main.o'. Stop. make: *** Waiting for unfinished jobs....Fix this by making the file generated/map-shift.h our real makefiletarget, and add this a dependency of the top level build target.Link: http://lkml.kernel.org/r/20180503192430.7582-2-ross.zwisler@linux.intel.comSigned-off-by: Ross Zwisler Cc: Christoph Hellwig Cc: CR, Sapthagirish Cc: Dan Williams Cc: Dave Chinner Cc: Jan Kara Cc: Matthew Wilcox Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds List of files: /linux-6.15/tools/testing/radix-tree/Makefile

b2441318 - License cleanup: add SPDX GPL-2.0 license identifier to files with no license

Wed, 01 Nov 2017 14:07:57 +0000

License cleanup: add SPDX GPL-2.0 license identifier to files with no licenseMany source files in the tree are missing licensing information, whichmakes it harder for compliance tools to determine the correct license.By default all files without license information are under the defaultlicense of the kernel, which is GPL version 2.Update the files which contain no license information with the 'GPL-2.0'SPDX license identifier. The SPDX identifier is a legally bindingshorthand, which can be used instead of the full boiler plate text.This patch is based on work done by Thomas Gleixner and Kate Stewart andPhilippe Ombredanne.How this work was done:Patches were generated and checked against linux-4.14-rc6 for a subset ofthe use cases: - file had no licensing information it it. - file was a */uapi/* one with no licensing information in it, - file was a */uapi/* one with existing licensing information,Further patches will be generated in subsequent months to fix up caseswhere non-standard license headers were used, and references to licensehad to be inferred by heuristics based on keywords.The analysis to determine which SPDX License Identifier to be applied toa file was done in a spreadsheet of side by side results from of theoutput of two independent scanners (ScanCode & Windriver) producing SPDXtag:value files created by Philippe Ombredanne. Philippe prepared thebase worksheet, and did an initial spot review of a few 1000 files.The 4.13 kernel was the starting point of the analysis with 60,537 filesassessed. Kate Stewart did a file by file comparison of the scannerresults in the spreadsheet to determine which SPDX license identifier(s)to be applied to the file. She confirmed any determination that was notimmediately clear with lawyers working with the Linux Foundation.Criteria used to select files for SPDX license identifier tagging was: - Files considered eligible had to be source code files. - Make and config files were included as candidates if they contained >5 lines of source - File already had some variant of a license header in it (even if <5 lines).All documentation files were explicitly excluded.The following heuristics were used to determine which SPDX licenseidentifiers to apply. - when both scanners couldn't find any license traces, file was considered to have no license information in it, and the top level COPYING file license applied. For non */uapi/* files that summary was: SPDX license identifier # files ---------------------------------------------------|------- GPL-2.0 11139 and resulted in the first patch in this series. If that file was a */uapi/* path one, it was "GPL-2.0 WITH Linux-syscall-note" otherwise it was "GPL-2.0". Results of that was: SPDX license identifier # files ---------------------------------------------------|------- GPL-2.0 WITH Linux-syscall-note 930 and resulted in the second patch in this series. - if a file had some form of licensing information in it, and was one of the */uapi/* ones, it was denoted with the Linux-syscall-note if any GPL family license was found in the file or had no licensing in it (per prior point). Results summary: SPDX license identifier # files ---------------------------------------------------|------ GPL-2.0 WITH Linux-syscall-note 270 GPL-2.0+ WITH Linux-syscall-note 169 ((GPL-2.0 WITH Linux-syscall-note) OR BSD-2-Clause) 21 ((GPL-2.0 WITH Linux-syscall-note) OR BSD-3-Clause) 17 LGPL-2.1+ WITH Linux-syscall-note 15 GPL-1.0+ WITH Linux-syscall-note 14 ((GPL-2.0+ WITH Linux-syscall-note) OR BSD-3-Clause) 5 LGPL-2.0+ WITH Linux-syscall-note 4 LGPL-2.1 WITH Linux-syscall-note 3 ((GPL-2.0 WITH Linux-syscall-note) OR MIT) 3 ((GPL-2.0 WITH Linux-syscall-note) AND MIT) 1 and that resulted in the third patch in this series. - when the two scanners agreed on the detected license(s), that became the concluded license(s). - when there was disagreement between the two scanners (one detected a license but the other didn't, or they both detected different licenses) a manual inspection of the file occurred. - In most cases a manual inspection of the information in the file resulted in a clear resolution of the license that should apply (and which scanner probably needed to revisit its heuristics). - When it was not immediately clear, the license identifier was confirmed with lawyers working with the Linux Foundation. - If there was any question as to the appropriate license identifier, the file was flagged for further research and to be revisited later in time.In total, over 70 hours of logged manual review was done on thespreadsheet to determine the SPDX license identifiers to apply to thesource files by Kate, Philippe, Thomas and, in some cases, confirmationby lawyers working with the Linux Foundation.Kate also obtained a third independent scan of the 4.13 code base fromFOSSology, and compared selected files where the other two scannersdisagreed against that SPDX file, to see if there was new insights. TheWindriver scanner is based on an older version of FOSSology in part, sothey are related.Thomas did random spot checks in about 500 files from the spreadsheetsfor the uapi headers and agreed with SPDX license identifier in thefiles he inspected. For the non-uapi files Thomas did random spot checksin about 15000 files.In initial set of patches against 4.14-rc6, 3 files were found to havecopy/paste license identifier errors, and have been fixed to reflect thecorrect identifier.Additionally Philippe spent 10 hours this week doing a detailed manualinspection and review of the 12,461 patched files from the initial patchversion early this week with: - a full scancode scan run, collecting the matched texts, detected license ids and scores - reviewing anything where there was a license detected (about 500+ files) to ensure that the applied SPDX license was correct - reviewing anything where there was no detection but the patch license was not GPL-2.0 WITH Linux-syscall-note to ensure that the applied SPDX license was correctThis produced a worksheet with 20 files needing minor correction. Thisworksheet was then exported into 3 different .csv files for thedifferent types of files to be modified.These .csv files were then reviewed by Greg. Thomas wrote a script toparse the csv files and add the proper SPDX tag to the file, in theformat that the file expected. This script was further refined by Gregbased on the output to detect more types of files automatically and todistinguish between header and source .c files (which need differentcomment types.) Finally Greg ran the script using the .csv files togenerate the patches.Reviewed-by: Kate Stewart Reviewed-by: Philippe Ombredanne Reviewed-by: Thomas Gleixner Signed-off-by: Greg Kroah-Hartman List of files: /linux-6.15/tools/testing/radix-tree/Makefile

f0f3f2d0 - radix tree test suite: Specify -m32 in LDFLAGS too

Fri, 03 Mar 2017 17:28:37 +0000

radix tree test suite: Specify -m32 in LDFLAGS tooMichael's patch to use the default make rule for linking and the patchfrom Rehas to use -m32 if building a 32-bit test-suite on a 64-bitplatform don't work well together.Reported-by: Rehas Sachdeva Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

3f1b6f9d - radix tree test suite: Depend on Makefile and quieten grep

Thu, 02 Mar 2017 17:24:28 +0000

radix tree test suite: Depend on Makefile and quieten grepChanging the CFLAGS in the Makefile didn't always lead to arecompilation because the OFILES didn't depend on the Makefile.Also, after doing make clean, grep would still complain abouta missing map-shift.h; we need -s as well as -q.Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile

284d96a4 - radix tree test suite: Fix build with --as-needed

Thu, 02 Mar 2017 09:29:00 +0000

radix tree test suite: Fix build with --as-neededCurrently the radix tree test suite doesn't build with toolchains thatuse --as-needed by default, for example Ubuntu's: cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -lpthread -lurcu main.o ... -o main /usr/bin/ld: regression1.o: undefined reference to symbol 'pthread_join@@GLIBC_2.17' /lib/powerpc64le-linux-gnu/libpthread.so.0: error adding symbols: DSO missing from command line collect2: error: ld returned 1 exit statusThis is caused by the custom makefile rules placing LDFLAGS before the.o files that need the libraries.We could fix it by using --no-as-needed, or rewriting the custom rules.But we can also just drop the custom rules and move the libraries toLDLIBS, and then the default rules work correctly - with the one caveatthat we need to add -fsanitize=address to LDFLAGS because that must bepassed to the linker as well as the compiler.Signed-off-by: Michael Ellerman Signed-off-by: Matthew Wilcox List of files: /linux-6.15/tools/testing/radix-tree/Makefile