diff options
Diffstat (limited to 'Documentation/core-api')
| -rw-r--r-- | Documentation/core-api/circular-buffers.rst | 2 | ||||
| -rw-r--r-- | Documentation/core-api/conf.py | 10 | ||||
| -rw-r--r-- | Documentation/core-api/gcc-plugins.rst | 93 | ||||
| -rw-r--r-- | Documentation/core-api/index.rst | 6 | ||||
| -rw-r--r-- | Documentation/core-api/kernel-api.rst | 19 | ||||
| -rw-r--r-- | Documentation/core-api/packing.rst | 166 | ||||
| -rw-r--r-- | Documentation/core-api/printk-formats.rst | 18 | ||||
| -rw-r--r-- | Documentation/core-api/protection-keys.rst | 99 | ||||
| -rw-r--r-- | Documentation/core-api/timekeeping.rst | 14 | ||||
| -rw-r--r-- | Documentation/core-api/xarray.rst | 270 |
10 files changed, 533 insertions, 164 deletions
diff --git a/Documentation/core-api/circular-buffers.rst b/Documentation/core-api/circular-buffers.rst index 53e51caa3347..50966f66e398 100644 --- a/Documentation/core-api/circular-buffers.rst +++ b/Documentation/core-api/circular-buffers.rst @@ -3,7 +3,7 @@ Circular Buffers ================ :Author: David Howells <dhowells@redhat.com> -:Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> +:Author: Paul E. McKenney <paulmck@linux.ibm.com> Linux provides a number of features that can be used to implement circular diff --git a/Documentation/core-api/conf.py b/Documentation/core-api/conf.py deleted file mode 100644 index db1f7659f3da..000000000000 --- a/Documentation/core-api/conf.py +++ /dev/null @@ -1,10 +0,0 @@ -# -*- coding: utf-8; mode: python -*- - -project = "Core-API Documentation" - -tags.add("subproject") - -latex_documents = [ - ('index', 'core-api.tex', project, - 'The kernel development community', 'manual'), -] diff --git a/Documentation/core-api/gcc-plugins.rst b/Documentation/core-api/gcc-plugins.rst new file mode 100644 index 000000000000..8502f24396fb --- /dev/null +++ b/Documentation/core-api/gcc-plugins.rst @@ -0,0 +1,93 @@ +========================= +GCC plugin infrastructure +========================= + + +Introduction +============ + +GCC plugins are loadable modules that provide extra features to the +compiler [1]_. They are useful for runtime instrumentation and static analysis. +We can analyse, change and add further code during compilation via +callbacks [2]_, GIMPLE [3]_, IPA [4]_ and RTL passes [5]_. + +The GCC plugin infrastructure of the kernel supports all gcc versions from +4.5 to 6.0, building out-of-tree modules, cross-compilation and building in a +separate directory. +Plugin source files have to be compilable by both a C and a C++ compiler as well +because gcc versions 4.5 and 4.6 are compiled by a C compiler, +gcc-4.7 can be compiled by a C or a C++ compiler, +and versions 4.8+ can only be compiled by a C++ compiler. + +Currently the GCC plugin infrastructure supports only the x86, arm, arm64 and +powerpc architectures. + +This infrastructure was ported from grsecurity [6]_ and PaX [7]_. + +-- + +.. [1] https://gcc.gnu.org/onlinedocs/gccint/Plugins.html +.. [2] https://gcc.gnu.org/onlinedocs/gccint/Plugin-API.html#Plugin-API +.. [3] https://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html +.. [4] https://gcc.gnu.org/onlinedocs/gccint/IPA.html +.. [5] https://gcc.gnu.org/onlinedocs/gccint/RTL.html +.. [6] https://grsecurity.net/ +.. [7] https://pax.grsecurity.net/ + + +Files +===== + +**$(src)/scripts/gcc-plugins** + + This is the directory of the GCC plugins. + +**$(src)/scripts/gcc-plugins/gcc-common.h** + + This is a compatibility header for GCC plugins. + It should be always included instead of individual gcc headers. + +**$(src)/scripts/gcc-plugin.sh** + + This script checks the availability of the included headers in + gcc-common.h and chooses the proper host compiler to build the plugins + (gcc-4.7 can be built by either gcc or g++). + +**$(src)/scripts/gcc-plugins/gcc-generate-gimple-pass.h, +$(src)/scripts/gcc-plugins/gcc-generate-ipa-pass.h, +$(src)/scripts/gcc-plugins/gcc-generate-simple_ipa-pass.h, +$(src)/scripts/gcc-plugins/gcc-generate-rtl-pass.h** + + These headers automatically generate the registration structures for + GIMPLE, SIMPLE_IPA, IPA and RTL passes. They support all gcc versions + from 4.5 to 6.0. + They should be preferred to creating the structures by hand. + + +Usage +===== + +You must install the gcc plugin headers for your gcc version, +e.g., on Ubuntu for gcc-4.9:: + + apt-get install gcc-4.9-plugin-dev + +Enable a GCC plugin based feature in the kernel config:: + + CONFIG_GCC_PLUGIN_CYC_COMPLEXITY = y + +To compile only the plugin(s):: + + make gcc-plugins + +or just run the kernel make and compile the whole kernel with +the cyclomatic complexity GCC plugin. + + +4. How to add a new GCC plugin +============================== + +The GCC plugins are in $(src)/scripts/gcc-plugins/. You can use a file or a directory +here. It must be added to $(src)/scripts/gcc-plugins/Makefile, +$(src)/scripts/Makefile.gcc-plugins and $(src)/arch/Kconfig. +See the cyc_complexity_plugin.c (CONFIG_GCC_PLUGIN_CYC_COMPLEXITY) GCC plugin. diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst index ee1bb8983a88..fa16a0538dcb 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -25,6 +25,7 @@ Core utilities librs genalloc errseq + packing printk-formats circular-buffers generic-radix-tree @@ -34,6 +35,9 @@ Core utilities timekeeping boot-time-mm memory-hotplug + protection-keys + ../RCU/index + gcc-plugins Interfaces for kernel debugging @@ -45,7 +49,7 @@ Interfaces for kernel debugging debug-objects tracepoint -.. only:: subproject +.. only:: subproject and html Indices ======= diff --git a/Documentation/core-api/kernel-api.rst b/Documentation/core-api/kernel-api.rst index a29c99d13331..f77de49b1d51 100644 --- a/Documentation/core-api/kernel-api.rst +++ b/Documentation/core-api/kernel-api.rst @@ -33,12 +33,18 @@ String Conversions .. kernel-doc:: lib/kstrtox.c :export: +.. kernel-doc:: lib/string_helpers.c + :export: + String Manipulation ------------------- .. kernel-doc:: lib/string.c :export: +.. kernel-doc:: include/linux/string.h + :internal: + .. kernel-doc:: mm/util.c :functions: kstrdup kstrdup_const kstrndup kmemdup kmemdup_nul memdup_user vmemdup_user strndup_user memdup_user_nul @@ -51,7 +57,7 @@ The Linux kernel provides more basic utility functions. Bit Operations -------------- -.. kernel-doc:: arch/x86/include/asm/bitops.h +.. kernel-doc:: include/asm-generic/bitops-instrumented.h :internal: Bitmap Operations @@ -138,6 +144,15 @@ Base 2 log and power Functions .. kernel-doc:: include/linux/log2.h :internal: +Integer power Functions +----------------------- + +.. kernel-doc:: lib/math/int_pow.c + :export: + +.. kernel-doc:: lib/math/int_sqrt.c + :export: + Division Functions ------------------ @@ -358,8 +373,6 @@ Read-Copy Update (RCU) .. kernel-doc:: kernel/rcu/tree.c -.. kernel-doc:: kernel/rcu/tree_plugin.h - .. kernel-doc:: kernel/rcu/tree_exp.h .. kernel-doc:: kernel/rcu/update.c diff --git a/Documentation/core-api/packing.rst b/Documentation/core-api/packing.rst new file mode 100644 index 000000000000..d8c341fe383e --- /dev/null +++ b/Documentation/core-api/packing.rst @@ -0,0 +1,166 @@ +================================================ +Generic bitfield packing and unpacking functions +================================================ + +Problem statement +----------------- + +When working with hardware, one has to choose between several approaches of +interfacing with it. +One can memory-map a pointer to a carefully crafted struct over the hardware +device's memory region, and access its fields as struct members (potentially +declared as bitfields). But writing code this way would make it less portable, +due to potential endianness mismatches between the CPU and the hardware device. +Additionally, one has to pay close attention when translating register +definitions from the hardware documentation into bit field indices for the +structs. Also, some hardware (typically networking equipment) tends to group +its register fields in ways that violate any reasonable word boundaries +(sometimes even 64 bit ones). This creates the inconvenience of having to +define "high" and "low" portions of register fields within the struct. +A more robust alternative to struct field definitions would be to extract the +required fields by shifting the appropriate number of bits. But this would +still not protect from endianness mismatches, except if all memory accesses +were performed byte-by-byte. Also the code can easily get cluttered, and the +high-level idea might get lost among the many bit shifts required. +Many drivers take the bit-shifting approach and then attempt to reduce the +clutter with tailored macros, but more often than not these macros take +shortcuts that still prevent the code from being truly portable. + +The solution +------------ + +This API deals with 2 basic operations: + + - Packing a CPU-usable number into a memory buffer (with hardware + constraints/quirks) + - Unpacking a memory buffer (which has hardware constraints/quirks) + into a CPU-usable number. + +The API offers an abstraction over said hardware constraints and quirks, +over CPU endianness and therefore between possible mismatches between +the two. + +The basic unit of these API functions is the u64. From the CPU's +perspective, bit 63 always means bit offset 7 of byte 7, albeit only +logically. The question is: where do we lay this bit out in memory? + +The following examples cover the memory layout of a packed u64 field. +The byte offsets in the packed buffer are always implicitly 0, 1, ... 7. +What the examples show is where the logical bytes and bits sit. + +1. Normally (no quirks), we would do it like this: + +:: + + 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 + 7 6 5 4 + 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + 3 2 1 0 + +That is, the MSByte (7) of the CPU-usable u64 sits at memory offset 0, and the +LSByte (0) of the u64 sits at memory offset 7. +This corresponds to what most folks would regard to as "big endian", where +bit i corresponds to the number 2^i. This is also referred to in the code +comments as "logical" notation. + + +2. If QUIRK_MSB_ON_THE_RIGHT is set, we do it like this: + +:: + + 56 57 58 59 60 61 62 63 48 49 50 51 52 53 54 55 40 41 42 43 44 45 46 47 32 33 34 35 36 37 38 39 + 7 6 5 4 + 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 + 3 2 1 0 + +That is, QUIRK_MSB_ON_THE_RIGHT does not affect byte positioning, but +inverts bit offsets inside a byte. + + +3. If QUIRK_LITTLE_ENDIAN is set, we do it like this: + +:: + + 39 38 37 36 35 34 33 32 47 46 45 44 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56 + 4 5 6 7 + 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 + 0 1 2 3 + +Therefore, QUIRK_LITTLE_ENDIAN means that inside the memory region, every +byte from each 4-byte word is placed at its mirrored position compared to +the boundary of that word. + +4. If QUIRK_MSB_ON_THE_RIGHT and QUIRK_LITTLE_ENDIAN are both set, we do it + like this: + +:: + + 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 + 4 5 6 7 + 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 + 0 1 2 3 + + +5. If just QUIRK_LSW32_IS_FIRST is set, we do it like this: + +:: + + 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 + 3 2 1 0 + 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 + 7 6 5 4 + +In this case the 8 byte memory region is interpreted as follows: first +4 bytes correspond to the least significant 4-byte word, next 4 bytes to +the more significant 4-byte word. + + +6. If QUIRK_LSW32_IS_FIRST and QUIRK_MSB_ON_THE_RIGHT are set, we do it like + this: + +:: + + 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 + 3 2 1 0 + 56 57 58 59 60 61 62 63 48 49 50 51 52 53 54 55 40 41 42 43 44 45 46 47 32 33 34 35 36 37 38 39 + 7 6 5 4 + + +7. If QUIRK_LSW32_IS_FIRST and QUIRK_LITTLE_ENDIAN are set, it looks like + this: + +:: + + 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 + 0 1 2 3 + 39 38 37 36 35 34 33 32 47 46 45 44 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56 + 4 5 6 7 + + +8. If QUIRK_LSW32_IS_FIRST, QUIRK_LITTLE_ENDIAN and QUIRK_MSB_ON_THE_RIGHT + are set, it looks like this: + +:: + + 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 + 0 1 2 3 + 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 + 4 5 6 7 + + +We always think of our offsets as if there were no quirk, and we translate +them afterwards, before accessing the memory region. + +Intended use +------------ + +Drivers that opt to use this API first need to identify which of the above 3 +quirk combinations (for a total of 8) match what the hardware documentation +describes. Then they should wrap the packing() function, creating a new +xxx_packing() that calls it using the proper QUIRK_* one-hot bits set. + +The packing() function returns an int-encoded error code, which protects the +programmer against incorrect API use. The errors are not expected to occur +durring runtime, therefore it is reasonable for xxx_packing() to return void +and simply swallow those errors. Optionally it can dump stack or print the +error description. diff --git a/Documentation/core-api/printk-formats.rst b/Documentation/core-api/printk-formats.rst index 75d2bbe9813f..ecbebf4ca8e7 100644 --- a/Documentation/core-api/printk-formats.rst +++ b/Documentation/core-api/printk-formats.rst @@ -13,10 +13,10 @@ Integer types If variable is of Type, use printk format specifier: ------------------------------------------------------------ - char %hhd or %hhx - unsigned char %hhu or %hhx - short int %hd or %hx - unsigned short int %hu or %hx + char %d or %x + unsigned char %u or %x + short int %d or %x + unsigned short int %u or %x int %d or %x unsigned int %u or %x long %ld or %lx @@ -25,10 +25,10 @@ Integer types unsigned long long %llu or %llx size_t %zu or %zx ssize_t %zd or %zx - s8 %hhd or %hhx - u8 %hhu or %hhx - s16 %hd or %hx - u16 %hu or %hx + s8 %d or %x + u8 %u or %x + s16 %d or %x + u16 %u or %x s32 %d or %x u32 %u or %x s64 %lld or %llx @@ -119,7 +119,7 @@ Kernel Pointers For printing kernel pointers which should be hidden from unprivileged users. The behaviour of %pK depends on the kptr_restrict sysctl - see -Documentation/sysctl/kernel.txt for more details. +Documentation/admin-guide/sysctl/kernel.rst for more details. Unmodified Addresses -------------------- diff --git a/Documentation/core-api/protection-keys.rst b/Documentation/core-api/protection-keys.rst new file mode 100644 index 000000000000..49d9833af871 --- /dev/null +++ b/Documentation/core-api/protection-keys.rst @@ -0,0 +1,99 @@ +.. SPDX-License-Identifier: GPL-2.0 + +====================== +Memory Protection Keys +====================== + +Memory Protection Keys for Userspace (PKU aka PKEYs) is a feature +which is found on Intel's Skylake "Scalable Processor" Server CPUs. +It will be avalable in future non-server parts. + +For anyone wishing to test or use this feature, it is available in +Amazon's EC2 C5 instances and is known to work there using an Ubuntu +17.04 image. + +Memory Protection Keys provides a mechanism for enforcing page-based +protections, but without requiring modification of the page tables +when an application changes protection domains. It works by +dedicating 4 previously ignored bits in each page table entry to a +"protection key", giving 16 possible keys. + +There is also a new user-accessible register (PKRU) with two separate +bits (Access Disable and Write Disable) for each key. Being a CPU +register, PKRU is inherently thread-local, potentially giving each +thread a different set of protections from every other thread. + +There are two new instructions (RDPKRU/WRPKRU) for reading and writing +to the new register. The feature is only available in 64-bit mode, +even though there is theoretically space in the PAE PTEs. These +permissions are enforced on data access only and have no effect on +instruction fetches. + +Syscalls +======== + +There are 3 system calls which directly interact with pkeys:: + + int pkey_alloc(unsigned long flags, unsigned long init_access_rights) + int pkey_free(int pkey); + int pkey_mprotect(unsigned long start, size_t len, + unsigned long prot, int pkey); + +Before a pkey can be used, it must first be allocated with +pkey_alloc(). An application calls the WRPKRU instruction +directly in order to change access permissions to memory covered +with a key. In this example WRPKRU is wrapped by a C function +called pkey_set(). +:: + + int real_prot = PROT_READ|PROT_WRITE; + pkey = pkey_alloc(0, PKEY_DISABLE_WRITE); + ptr = mmap(NULL, PAGE_SIZE, PROT_NONE, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0); + ret = pkey_mprotect(ptr, PAGE_SIZE, real_prot, pkey); + ... application runs here + +Now, if the application needs to update the data at 'ptr', it can +gain access, do the update, then remove its write access:: + + pkey_set(pkey, 0); // clear PKEY_DISABLE_WRITE + *ptr = foo; // assign something + pkey_set(pkey, PKEY_DISABLE_WRITE); // set PKEY_DISABLE_WRITE again + +Now when it frees the memory, it will also free the pkey since it +is no longer in use:: + + munmap(ptr, PAGE_SIZE); + pkey_free(pkey); + +.. note:: pkey_set() is a wrapper for the RDPKRU and WRPKRU instructions. + An example implementation can be found in + tools/testing/selftests/x86/protection_keys.c. + +Behavior +======== + +The kernel attempts to make protection keys consistent with the +behavior of a plain mprotect(). For instance if you do this:: + + mprotect(ptr, size, PROT_NONE); + something(ptr); + +you can expect the same effects with protection keys when doing this:: + + pkey = pkey_alloc(0, PKEY_DISABLE_WRITE | PKEY_DISABLE_READ); + pkey_mprotect(ptr, size, PROT_READ|PROT_WRITE, pkey); + something(ptr); + +That should be true whether something() is a direct access to 'ptr' +like:: + + *ptr = foo; + +or when the kernel does the access on the application's behalf like +with a read():: + + read(fd, ptr, 1); + +The kernel will send a SIGSEGV in both cases, but si_code will be set +to SEGV_PKERR when violating protection keys versus SEGV_ACCERR when +the plain mprotect() permissions are violated. diff --git a/Documentation/core-api/timekeeping.rst b/Documentation/core-api/timekeeping.rst index 93cbeb9daec0..c0ffa30c7c37 100644 --- a/Documentation/core-api/timekeeping.rst +++ b/Documentation/core-api/timekeeping.rst @@ -65,7 +65,7 @@ different format depending on what is required by the user: .. c:function:: u64 ktime_get_ns( void ) u64 ktime_get_boottime_ns( void ) u64 ktime_get_real_ns( void ) - u64 ktime_get_tai_ns( void ) + u64 ktime_get_clocktai_ns( void ) u64 ktime_get_raw_ns( void ) Same as the plain ktime_get functions, but returning a u64 number @@ -99,19 +99,23 @@ Coarse and fast_ns access Some additional variants exist for more specialized cases: -.. c:function:: ktime_t ktime_get_coarse_boottime( void ) +.. c:function:: ktime_t ktime_get_coarse( void ) + ktime_t ktime_get_coarse_boottime( void ) ktime_t ktime_get_coarse_real( void ) ktime_t ktime_get_coarse_clocktai( void ) - ktime_t ktime_get_coarse_raw( void ) + +.. c:function:: u64 ktime_get_coarse_ns( void ) + u64 ktime_get_coarse_boottime_ns( void ) + u64 ktime_get_coarse_real_ns( void ) + u64 ktime_get_coarse_clocktai_ns( void ) .. c:function:: void ktime_get_coarse_ts64( struct timespec64 * ) void ktime_get_coarse_boottime_ts64( struct timespec64 * ) void ktime_get_coarse_real_ts64( struct timespec64 * ) void ktime_get_coarse_clocktai_ts64( struct timespec64 * ) - void ktime_get_coarse_raw_ts64( struct timespec64 * ) These are quicker than the non-coarse versions, but less accurate, - corresponding to CLOCK_MONONOTNIC_COARSE and CLOCK_REALTIME_COARSE + corresponding to CLOCK_MONOTONIC_COARSE and CLOCK_REALTIME_COARSE in user space, along with the equivalent boottime/tai/raw timebase not available in user space. diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index ef6f9f98f595..fcedc5349ace 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -30,27 +30,27 @@ it called marks. Each mark may be set or cleared independently of the others. You can iterate over entries which are marked. Normal pointers may be stored in the XArray directly. They must be 4-byte -aligned, which is true for any pointer returned from :c:func:`kmalloc` and -:c:func:`alloc_page`. It isn't true for arbitrary user-space pointers, +aligned, which is true for any pointer returned from kmalloc() and +alloc_page(). It isn't true for arbitrary user-space pointers, nor for function pointers. You can store pointers to statically allocated objects, as long as those objects have an alignment of at least 4. You can also store integers between 0 and ``LONG_MAX`` in the XArray. -You must first convert it into an entry using :c:func:`xa_mk_value`. +You must first convert it into an entry using xa_mk_value(). When you retrieve an entry from the XArray, you can check whether it is -a value entry by calling :c:func:`xa_is_value`, and convert it back to -an integer by calling :c:func:`xa_to_value`. +a value entry by calling xa_is_value(), and convert it back to +an integer by calling xa_to_value(). Some users want to store tagged pointers instead of using the marks -described above. They can call :c:func:`xa_tag_pointer` to create an -entry with a tag, :c:func:`xa_untag_pointer` to turn a tagged entry -back into an untagged pointer and :c:func:`xa_pointer_tag` to retrieve +described above. They can call xa_tag_pointer() to create an +entry with a tag, xa_untag_pointer() to turn a tagged entry +back into an untagged pointer and xa_pointer_tag() to retrieve the tag of an entry. Tagged pointers use the same bits that are used to distinguish value entries from normal pointers, so each user must decide whether they want to store value entries or tagged pointers in any particular XArray. -The XArray does not support storing :c:func:`IS_ERR` pointers as some +The XArray does not support storing IS_ERR() pointers as some conflict with value entries or internal entries. An unusual feature of the XArray is the ability to create entries which @@ -64,89 +64,89 @@ entry will cause the XArray to forget about the range. Normal API ========== -Start by initialising an XArray, either with :c:func:`DEFINE_XARRAY` -for statically allocated XArrays or :c:func:`xa_init` for dynamically +Start by initialising an XArray, either with DEFINE_XARRAY() +for statically allocated XArrays or xa_init() for dynamically allocated ones. A freshly-initialised XArray contains a ``NULL`` pointer at every index. -You can then set entries using :c:func:`xa_store` and get entries -using :c:func:`xa_load`. xa_store will overwrite any entry with the +You can then set entries using xa_store() and get entries +using xa_load(). xa_store will overwrite any entry with the new entry and return the previous entry stored at that index. You can -use :c:func:`xa_erase` instead of calling :c:func:`xa_store` with a +use xa_erase() instead of calling xa_store() with a ``NULL`` entry. There is no difference between an entry that has never been stored to, one that has been erased and one that has most recently had ``NULL`` stored to it. You can conditionally replace an entry at an index by using -:c:func:`xa_cmpxchg`. Like :c:func:`cmpxchg`, it will only succeed if +xa_cmpxchg(). Like cmpxchg(), it will only succeed if the entry at that index has the 'old' value. It also returns the entry which was at that index; if it returns the same entry which was passed as -'old', then :c:func:`xa_cmpxchg` succeeded. +'old', then xa_cmpxchg() succeeded. If you want to only store a new entry to an index if the current entry -at that index is ``NULL``, you can use :c:func:`xa_insert` which +at that index is ``NULL``, you can use xa_insert() which returns ``-EBUSY`` if the entry is not empty. You can enquire whether a mark is set on an entry by using -:c:func:`xa_get_mark`. If the entry is not ``NULL``, you can set a mark -on it by using :c:func:`xa_set_mark` and remove the mark from an entry by -calling :c:func:`xa_clear_mark`. You can ask whether any entry in the -XArray has a particular mark set by calling :c:func:`xa_marked`. +xa_get_mark(). If the entry is not ``NULL``, you can set a mark +on it by using xa_set_mark() and remove the mark from an entry by +calling xa_clear_mark(). You can ask whether any entry in the +XArray has a particular mark set by calling xa_marked(). You can copy entries out of the XArray into a plain array by calling -:c:func:`xa_extract`. Or you can iterate over the present entries in -the XArray by calling :c:func:`xa_for_each`. You may prefer to use -:c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present +xa_extract(). Or you can iterate over the present entries in +the XArray by calling xa_for_each(). You may prefer to use +xa_find() or xa_find_after() to move to the next present entry in the XArray. -Calling :c:func:`xa_store_range` stores the same entry in a range +Calling xa_store_range() stores the same entry in a range of indices. If you do this, some of the other operations will behave in a slightly odd way. For example, marking the entry at one index may result in the entry being marked at some, but not all of the other indices. Storing into one index may result in the entry retrieved by some, but not all of the other indices changing. -Sometimes you need to ensure that a subsequent call to :c:func:`xa_store` -will not need to allocate memory. The :c:func:`xa_reserve` function +Sometimes you need to ensure that a subsequent call to xa_store() +will not need to allocate memory. The xa_reserve() function will store a reserved entry at the indicated index. Users of the normal API will see this entry as containing ``NULL``. If you do -not need to use the reserved entry, you can call :c:func:`xa_release` +not need to use the reserved entry, you can call xa_release() to remove the unused entry. If another user has stored to the entry -in the meantime, :c:func:`xa_release` will do nothing; if instead you -want the entry to become ``NULL``, you should use :c:func:`xa_erase`. -Using :c:func:`xa_insert` on a reserved entry will fail. +in the meantime, xa_release() will do nothing; if instead you +want the entry to become ``NULL``, you should use xa_erase(). +Using xa_insert() on a reserved entry will fail. -If all entries in the array are ``NULL``, the :c:func:`xa_empty` function +If all entries in the array are ``NULL``, the xa_empty() function will return ``true``. Finally, you can remove all entries from an XArray by calling -:c:func:`xa_destroy`. If the XArray entries are pointers, you may wish +xa_destroy(). If the XArray entries are pointers, you may wish to free the entries first. You can do this by iterating over all present -entries in the XArray using the :c:func:`xa_for_each` iterator. +entries in the XArray using the xa_for_each() iterator. Allocating XArrays ------------------ -If you use :c:func:`DEFINE_XARRAY_ALLOC` to define the XArray, or -initialise it by passing ``XA_FLAGS_ALLOC`` to :c:func:`xa_init_flags`, +If you use DEFINE_XARRAY_ALLOC() to define the XArray, or +initialise it by passing ``XA_FLAGS_ALLOC`` to xa_init_flags(), the XArray changes to track whether entries are in use or not. -You can call :c:func:`xa_alloc` to store the entry at an unused index +You can call xa_alloc() to store the entry at an unused index in the XArray. If you need to modify the array from interrupt context, -you can use :c:func:`xa_alloc_bh` or :c:func:`xa_alloc_irq` to disable +you can use xa_alloc_bh() or xa_alloc_irq() to disable interrupts while allocating the ID. -Using :c:func:`xa_store`, :c:func:`xa_cmpxchg` or :c:func:`xa_insert` will +Using xa_store(), xa_cmpxchg() or xa_insert() will also mark the entry as being allocated. Unlike a normal XArray, storing -``NULL`` will mark the entry as being in use, like :c:func:`xa_reserve`. -To free an entry, use :c:func:`xa_erase` (or :c:func:`xa_release` if +``NULL`` will mark the entry as being in use, like xa_reserve(). +To free an entry, use xa_erase() (or xa_release() if you only want to free the entry if it's ``NULL``). By default, the lowest free entry is allocated starting from 0. If you want to allocate entries starting at 1, it is more efficient to use -:c:func:`DEFINE_XARRAY_ALLOC1` or ``XA_FLAGS_ALLOC1``. If you want to +DEFINE_XARRAY_ALLOC1() or ``XA_FLAGS_ALLOC1``. If you want to allocate IDs up to a maximum, then wrap back around to the lowest free -ID, you can use :c:func:`xa_alloc_cyclic`. +ID, you can use xa_alloc_cyclic(). You cannot use ``XA_MARK_0`` with an allocating XArray as this mark is used to track whether an entry is free or not. The other marks are @@ -155,17 +155,17 @@ available for your use. Memory allocation ----------------- -The :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_alloc`, -:c:func:`xa_reserve` and :c:func:`xa_insert` functions take a gfp_t +The xa_store(), xa_cmpxchg(), xa_alloc(), +xa_reserve() and xa_insert() functions take a gfp_t parameter in case the XArray needs to allocate memory to store this entry. If the entry is being deleted, no memory allocation needs to be performed, and the GFP flags specified will be ignored. It is possible for no memory to be allocatable, particularly if you pass a restrictive set of GFP flags. In that case, the functions return a -special value which can be turned into an errno using :c:func:`xa_err`. +special value which can be turned into an errno using xa_err(). If you don't need to know exactly which error occurred, using -:c:func:`xa_is_err` is slightly more efficient. +xa_is_err() is slightly more efficient. Locking ------- @@ -174,54 +174,54 @@ When using the Normal API, you do not have to worry about locking. The XArray uses RCU and an internal spinlock to synchronise access: No lock needed: - * :c:func:`xa_empty` - * :c:func:`xa_marked` + * xa_empty() + * xa_marked() Takes RCU read lock: - * :c:func:`xa_load` - * :c:func:`xa_for_each` - * :c:func:`xa_find` - * :c:func:`xa_find_after` - * :c:func:`xa_extract` - * :c:func:`xa_get_mark` + * xa_load() + * xa_for_each() + * xa_find() + * xa_find_after() + * xa_extract() + * xa_get_mark() Takes xa_lock internally: - * :c:func:`xa_store` - * :c:func:`xa_store_bh` - * :c:func:`xa_store_irq` - * :c:func:`xa_insert` - * :c:func:`xa_insert_bh` - * :c:func:`xa_insert_irq` - * :c:func:`xa_erase` - * :c:func:`xa_erase_bh` - * :c:func:`xa_erase_irq` - * :c:func:`xa_cmpxchg` - * :c:func:`xa_cmpxchg_bh` - * :c:func:`xa_cmpxchg_irq` - * :c:func:`xa_store_range` - * :c:func:`xa_alloc` - * :c:func:`xa_alloc_bh` - * :c:func:`xa_alloc_irq` - * :c:func:`xa_reserve` - * :c:func:`xa_reserve_bh` - * :c:func:`xa_reserve_irq` - * :c:func:`xa_destroy` - * :c:func:`xa_set_mark` - * :c:func:`xa_clear_mark` + * xa_store() + * xa_store_bh() + * xa_store_irq() + * xa_insert() + * xa_insert_bh() + * xa_insert_irq() + * xa_erase() + * xa_erase_bh() + * xa_erase_irq() + * xa_cmpxchg() + * xa_cmpxchg_bh() + * xa_cmpxchg_irq() + * xa_store_range() + * xa_alloc() + * xa_alloc_bh() + * xa_alloc_irq() + * xa_reserve() + * xa_reserve_bh() + * xa_reserve_irq() + * xa_destroy() + * xa_set_mark() + * xa_clear_mark() Assumes xa_lock held on entry: - * :c:func:`__xa_store` - * :c:func:`__xa_insert` - * :c:func:`__xa_erase` - * :c:func:`__xa_cmpxchg` - * :c:func:`__xa_alloc` - * :c:func:`__xa_set_mark` - * :c:func:`__xa_clear_mark` + * __xa_store() + * __xa_insert() + * __xa_erase() + * __xa_cmpxchg() + * __xa_alloc() + * __xa_set_mark() + * __xa_clear_mark() If you want to take advantage of the lock to protect the data structures -that you are storing in the XArray, you can call :c:func:`xa_lock` -before calling :c:func:`xa_load`, then take a reference count on the -object you have found before calling :c:func:`xa_unlock`. This will +that you are storing in the XArray, you can call xa_lock() +before calling xa_load(), then take a reference count on the +object you have found before calling xa_unlock(). This will prevent stores from removing the object from the array between looking up the object and incrementing the refcount. You can also use RCU to avoid dereferencing freed memory, but an explanation of that is beyond @@ -261,7 +261,7 @@ context and then erase them in softirq context, you can do that this way:: } If you are going to modify the XArray from interrupt or softirq context, -you need to initialise the array using :c:func:`xa_init_flags`, passing +you need to initialise the array using xa_init_flags(), passing ``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``. The above example also shows a common pattern of wanting to extend the @@ -269,20 +269,20 @@ coverage of the xa_lock on the store side to protect some statistics associated with the array. Sharing the XArray with interrupt context is also possible, either -using :c:func:`xa_lock_irqsave` in both the interrupt handler and process -context, or :c:func:`xa_lock_irq` in process context and :c:func:`xa_lock` +using xa_lock_irqsave() in both the interrupt handler and process +context, or xa_lock_irq() in process context and xa_lock() in the interrupt handler. Some of the more common patterns have helper -functions such as :c:func:`xa_store_bh`, :c:func:`xa_store_irq`, -:c:func:`xa_erase_bh`, :c:func:`xa_erase_irq`, :c:func:`xa_cmpxchg_bh` -and :c:func:`xa_cmpxchg_irq`. +functions such as xa_store_bh(), xa_store_irq(), +xa_erase_bh(), xa_erase_irq(), xa_cmpxchg_bh() +and xa_cmpxchg_irq(). Sometimes you need to protect access to the XArray with a mutex because that lock sits above another mutex in the locking hierarchy. That does -not entitle you to use functions like :c:func:`__xa_erase` without taking +not entitle you to use functions like __xa_erase() without taking the xa_lock; the xa_lock is used for lockdep validation and will be used for other purposes in the future. -The :c:func:`__xa_set_mark` and :c:func:`__xa_clear_mark` functions are also +The __xa_set_mark() and __xa_clear_mark() functions are also available for situations where you look up an entry and want to atomically set or clear a mark. It may be more efficient to use the advanced API in this case, as it will save you from walking the tree twice. @@ -300,27 +300,27 @@ indeed the normal API is implemented in terms of the advanced API. The advanced API is only available to modules with a GPL-compatible license. The advanced API is based around the xa_state. This is an opaque data -structure which you declare on the stack using the :c:func:`XA_STATE` +structure which you declare on the stack using the XA_STATE() macro. This macro initialises the xa_state ready to start walking around the XArray. It is used as a cursor to maintain the position in the XArray and let you compose various operations together without having to restart from the top every time. The xa_state is also used to store errors. You can call -:c:func:`xas_error` to retrieve the error. All operations check whether +xas_error() to retrieve the error. All operations check whether the xa_state is in an error state before proceeding, so there's no need for you to check for an error after each call; you can make multiple calls in succession and only check at a convenient point. The only errors currently generated by the XArray code itself are ``ENOMEM`` and ``EINVAL``, but it supports arbitrary errors in case you want to call -:c:func:`xas_set_err` yourself. +xas_set_err() yourself. -If the xa_state is holding an ``ENOMEM`` error, calling :c:func:`xas_nomem` +If the xa_state is holding an ``ENOMEM`` error, calling xas_nomem() will attempt to allocate more memory using the specified gfp flags and cache it in the xa_state for the next attempt. The idea is that you take the xa_lock, attempt the operation and drop the lock. The operation attempts to allocate memory while holding the lock, but it is more -likely to fail. Once you have dropped the lock, :c:func:`xas_nomem` +likely to fail. Once you have dropped the lock, xas_nomem() can try harder to allocate more memory. It will return ``true`` if it is worth retrying the operation (i.e. that there was a memory error *and* more memory was allocated). If it has previously allocated memory, and @@ -333,7 +333,7 @@ Internal Entries The XArray reserves some entries for its own purposes. These are never exposed through the normal API, but when using the advanced API, it's possible to see them. Usually the best way to handle them is to pass them -to :c:func:`xas_retry`, and retry the operation if it returns ``true``. +to xas_retry(), and retry the operation if it returns ``true``. .. flat-table:: :widths: 1 1 6 @@ -343,89 +343,89 @@ to :c:func:`xas_retry`, and retry the operation if it returns ``true``. - Usage * - Node - - :c:func:`xa_is_node` + - xa_is_node() - An XArray node. May be visible when using a multi-index xa_state. * - Sibling - - :c:func:`xa_is_sibling` + - xa_is_sibling() - A non-canonical entry for a multi-index entry. The value indicates which slot in this node has the canonical entry. * - Retry - - :c:func:`xa_is_retry` + - xa_is_retry() - This entry is currently being modified by a thread which has the xa_lock. The node containing this entry may be freed at the end of this RCU period. You should restart the lookup from the head of the array. * - Zero - - :c:func:`xa_is_zero` + - xa_is_zero() - Zero entries appear as ``NULL`` through the Normal API, but occupy an entry in the XArray which can be used to reserve the index for future use. This is used by allocating XArrays for allocated entries which are ``NULL``. Other internal entries may be added in the future. As far as possible, they -will be handled by :c:func:`xas_retry`. +will be handled by xas_retry(). Additional functionality ------------------------ -The :c:func:`xas_create_range` function allocates all the necessary memory +The xas_create_range() function allocates all the necessary memory to store every entry in a range. It will set ENOMEM in the xa_state if it cannot allocate memory. -You can use :c:func:`xas_init_marks` to reset the marks on an entry +You can use xas_init_marks() to reset the marks on an entry to their default state. This is usually all marks clear, unless the XArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set and all other marks are clear. Replacing one entry with another using -:c:func:`xas_store` will not reset the marks on that entry; if you want +xas_store() will not reset the marks on that entry; if you want the marks reset, you should do that explicitly. -The :c:func:`xas_load` will walk the xa_state as close to the entry +The xas_load() will walk the xa_state as close to the entry as it can. If you know the xa_state has already been walked to the entry and need to check that the entry hasn't changed, you can use -:c:func:`xas_reload` to save a function call. +xas_reload() to save a function call. If you need to move to a different index in the XArray, call -:c:func:`xas_set`. This resets the cursor to the top of the tree, which +xas_set(). This resets the cursor to the top of the tree, which will generally make the next operation walk the cursor to the desired spot in the tree. If you want to move to the next or previous index, -call :c:func:`xas_next` or :c:func:`xas_prev`. Setting the index does +call xas_next() or xas_prev(). Setting the index does not walk the cursor around the array so does not require a lock to be held, while moving to the next or previous index does. -You can search for the next present entry using :c:func:`xas_find`. This -is the equivalent of both :c:func:`xa_find` and :c:func:`xa_find_after`; +You can search for the next present entry using xas_find(). This +is the equivalent of both xa_find() and xa_find_after(); if the cursor has been walked to an entry, then it will find the next entry after the one currently referenced. If not, it will return the -entry at the index of the xa_state. Using :c:func:`xas_next_entry` to -move to the next present entry instead of :c:func:`xas_find` will save +entry at the index of the xa_state. Using xas_next_entry() to +move to the next present entry instead of xas_find() will save a function call in the majority of cases at the expense of emitting more inline code. -The :c:func:`xas_find_marked` function is similar. If the xa_state has +The xas_find_marked() function is similar. If the xa_state has not been walked, it will return the entry at the index of the xa_state, if it is marked. Otherwise, it will return the first marked entry after -the entry referenced by the xa_state. The :c:func:`xas_next_marked` -function is the equivalent of :c:func:`xas_next_entry`. +the entry referenced by the xa_state. The xas_next_marked() +function is the equivalent of xas_next_entry(). -When iterating over a range of the XArray using :c:func:`xas_for_each` -or :c:func:`xas_for_each_marked`, it may be necessary to temporarily stop -the iteration. The :c:func:`xas_pause` function exists for this purpose. +When iterating over a range of the XArray using xas_for_each() +or xas_for_each_marked(), it may be necessary to temporarily stop +the iteration. The xas_pause() function exists for this purpose. After you have done the necessary work and wish to resume, the xa_state is in an appropriate state to continue the iteration after the entry you last processed. If you have interrupts disabled while iterating, then it is good manners to pause the iteration and reenable interrupts every ``XA_CHECK_SCHED`` entries. -The :c:func:`xas_get_mark`, :c:func:`xas_set_mark` and -:c:func:`xas_clear_mark` functions require the xa_state cursor to have +The xas_get_mark(), xas_set_mark() and +xas_clear_mark() functions require the xa_state cursor to have been moved to the appropriate location in the xarray; they will do -nothing if you have called :c:func:`xas_pause` or :c:func:`xas_set` +nothing if you have called xas_pause() or xas_set() immediately before. -You can call :c:func:`xas_set_update` to have a callback function +You can call xas_set_update() to have a callback function called each time the XArray updates a node. This is used by the page cache workingset code to maintain its list of nodes which contain only shadow entries. @@ -443,25 +443,25 @@ eg indices 64-127 may be tied together, but 2-6 may not be. This may save substantial quantities of memory; for example tying 512 entries together will save over 4kB. -You can create a multi-index entry by using :c:func:`XA_STATE_ORDER` -or :c:func:`xas_set_order` followed by a call to :c:func:`xas_store`. -Calling :c:func:`xas_load` with a multi-index xa_state will walk the +You can create a multi-index entry by using XA_STATE_ORDER() +or xas_set_order() followed by a call to xas_store(). +Calling xas_load() with a multi-index xa_state will walk the xa_state to the right location in the tree, but the return value is not meaningful, potentially being an internal entry or ``NULL`` even when there -is an entry stored within the range. Calling :c:func:`xas_find_conflict` +is an entry stored within the range. Calling xas_find_conflict() will return the first entry within the range or ``NULL`` if there are no -entries in the range. The :c:func:`xas_for_each_conflict` iterator will +entries in the range. The xas_for_each_conflict() iterator will iterate over every entry which overlaps the specified range. -If :c:func:`xas_load` encounters a multi-index entry, the xa_index +If xas_load() encounters a multi-index entry, the xa_index in the xa_state will not be changed. When iterating over an XArray -or calling :c:func:`xas_find`, if the initial index is in the middle +or calling xas_find(), if the initial index is in the middle of a multi-index entry, it will not be altered. Subsequent calls or iterations will move the index to the first index in the range. Each entry will only be returned once, no matter how many indices it occupies. -Using :c:func:`xas_next` or :c:func:`xas_prev` with a multi-index xa_state +Using xas_next() or xas_prev() with a multi-index xa_state is not supported. Using either of these functions on a multi-index entry will reveal sibling entries; these should be skipped over by the caller. |