summaryrefslogtreecommitdiffstats
path: root/Documentation
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2018-02-08 14:39:29 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2018-02-08 14:39:29 -0800
commit9d21874da8ec0e0043c85cde8dda173e74ffc24d (patch)
tree8c02dce2b04ff5d70cafbd82a8bff383f2a49604 /Documentation
parent4ed8244ef8847c8ad7414e1a12ba45fef7998721 (diff)
parentac665d9423474e64e64b34b0e2cea43601b50d7d (diff)
downloadlinux-9d21874da8ec0e0043c85cde8dda173e74ffc24d.tar.bz2
Merge branch 'idr-2018-02-06' of git://git.infradead.org/users/willy/linux-dax
Pull idr updates from Matthew Wilcox: - test-suite improvements - replace the extended API by improving the normal API - performance improvement for IDRs which are 1-based rather than 0-based - add documentation * 'idr-2018-02-06' of git://git.infradead.org/users/willy/linux-dax: idr: Add documentation idr: Make 1-based IDRs more efficient idr: Warn if old iterators see large IDs idr: Rename idr_for_each_entry_ext idr: Remove idr_alloc_ext cls_u32: Convert to idr_alloc_u32 cls_u32: Reinstate cyclic allocation cls_flower: Convert to idr_alloc_u32 cls_bpf: Convert to use idr_alloc_u32 cls_basic: Convert to use idr_alloc_u32 cls_api: Convert to idr_alloc_u32 net sched actions: Convert to use idr_alloc_u32 idr: Add idr_alloc_u32 helper idr: Delete idr_find_ext function idr: Delete idr_replace_ext function idr: Delete idr_remove_ext function IDR test suite: Check handling negative end correctly idr test suite: Fix ida_test_random() radix tree test suite: Remove ARRAY_SIZE
Diffstat (limited to 'Documentation')
-rw-r--r--Documentation/core-api/idr.rst79
-rw-r--r--Documentation/core-api/index.rst1
-rw-r--r--Documentation/core-api/kernel-api.rst12
3 files changed, 80 insertions, 12 deletions
diff --git a/Documentation/core-api/idr.rst b/Documentation/core-api/idr.rst
new file mode 100644
index 000000000000..9078a5c3ac95
--- /dev/null
+++ b/Documentation/core-api/idr.rst
@@ -0,0 +1,79 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+=============
+ID Allocation
+=============
+
+:Author: Matthew Wilcox
+
+Overview
+========
+
+A common problem to solve is allocating identifiers (IDs); generally
+small numbers which identify a thing. Examples include file descriptors,
+process IDs, packet identifiers in networking protocols, SCSI tags
+and device instance numbers. The IDR and the IDA provide a reasonable
+solution to the problem to avoid everybody inventing their own. The IDR
+provides the ability to map an ID to a pointer, while the IDA provides
+only ID allocation, and as a result is much more memory-efficient.
+
+IDR usage
+=========
+
+Start by initialising an IDR, either with :c:func:`DEFINE_IDR`
+for statically allocated IDRs or :c:func:`idr_init` for dynamically
+allocated IDRs.
+
+You can call :c:func:`idr_alloc` to allocate an unused ID. Look up
+the pointer you associated with the ID by calling :c:func:`idr_find`
+and free the ID by calling :c:func:`idr_remove`.
+
+If you need to change the pointer associated with an ID, you can call
+:c:func:`idr_replace`. One common reason to do this is to reserve an
+ID by passing a ``NULL`` pointer to the allocation function; initialise the
+object with the reserved ID and finally insert the initialised object
+into the IDR.
+
+Some users need to allocate IDs larger than ``INT_MAX``. So far all of
+these users have been content with a ``UINT_MAX`` limit, and they use
+:c:func:`idr_alloc_u32`. If you need IDs that will not fit in a u32,
+we will work with you to address your needs.
+
+If you need to allocate IDs sequentially, you can use
+:c:func:`idr_alloc_cyclic`. The IDR becomes less efficient when dealing
+with larger IDs, so using this function comes at a slight cost.
+
+To perform an action on all pointers used by the IDR, you can
+either use the callback-based :c:func:`idr_for_each` or the
+iterator-style :c:func:`idr_for_each_entry`. You may need to use
+:c:func:`idr_for_each_entry_continue` to continue an iteration. You can
+also use :c:func:`idr_get_next` if the iterator doesn't fit your needs.
+
+When you have finished using an IDR, you can call :c:func:`idr_destroy`
+to release the memory used by the IDR. This will not free the objects
+pointed to from the IDR; if you want to do that, use one of the iterators
+to do it.
+
+You can use :c:func:`idr_is_empty` to find out whether there are any
+IDs currently allocated.
+
+If you need to take a lock while allocating a new ID from the IDR,
+you may need to pass a restrictive set of GFP flags, which can lead
+to the IDR being unable to allocate memory. To work around this,
+you can call :c:func:`idr_preload` before taking the lock, and then
+:c:func:`idr_preload_end` after the allocation.
+
+.. kernel-doc:: include/linux/idr.h
+ :doc: idr sync
+
+IDA usage
+=========
+
+.. kernel-doc:: lib/idr.c
+ :doc: IDA description
+
+Functions and structures
+========================
+
+.. kernel-doc:: include/linux/idr.h
+.. kernel-doc:: lib/idr.c
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 1b1fd01990b5..c670a8031786 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -16,6 +16,7 @@ Core utilities
atomic_ops
refcount-vs-atomic
cpu_hotplug
+ idr
local_ops
workqueue
genericirq
diff --git a/Documentation/core-api/kernel-api.rst b/Documentation/core-api/kernel-api.rst
index e7fadf02c511..ff335f8aeb39 100644
--- a/Documentation/core-api/kernel-api.rst
+++ b/Documentation/core-api/kernel-api.rst
@@ -103,18 +103,6 @@ CRC Functions
.. kernel-doc:: lib/crc-itu-t.c
:export:
-idr/ida Functions
------------------
-
-.. kernel-doc:: include/linux/idr.h
- :doc: idr sync
-
-.. kernel-doc:: lib/idr.c
- :doc: IDA description
-
-.. kernel-doc:: lib/idr.c
- :export:
-
Math Functions in Linux
=======================