From 992a8e60e3fea77c55589fc1c5af2304e78a5baa Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 23 Nov 2017 22:57:20 -0500 Subject: xarray: Add documentation This is documentation on how to use the XArray, not details about its internal implementation. Signed-off-by: Matthew Wilcox Acked-by: Josef Bacik --- Documentation/core-api/index.rst | 1 + Documentation/core-api/xarray.rst | 404 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 405 insertions(+) create mode 100644 Documentation/core-api/xarray.rst (limited to 'Documentation/core-api') diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst index 26b735cefb93..df3105aa75f4 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -21,6 +21,7 @@ Core utilities local_ops workqueue genericirq + xarray flexible-arrays librs genalloc diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst new file mode 100644 index 000000000000..4b101b4f3aa1 --- /dev/null +++ b/Documentation/core-api/xarray.rst @@ -0,0 +1,404 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +====== +XArray +====== + +:Author: Matthew Wilcox + +Overview +======== + +The XArray is an abstract data type which behaves like a very large array +of pointers. It meets many of the same needs as a hash or a conventional +resizable array. Unlike a hash, it allows you to sensibly go to the +next or previous entry in a cache-efficient manner. In contrast to a +resizable array, there is no need to copy data or change MMU mappings in +order to grow the array. It is more memory-efficient, parallelisable +and cache friendly than a doubly-linked list. It takes advantage of +RCU to perform lookups without locking. + +The XArray implementation is efficient when the indices used are densely +clustered; hashing the object and using the hash as the index will not +perform well. The XArray is optimised for small indices, but still has +good performance with large indices. If your index can be larger than +``ULONG_MAX`` then the XArray is not the data type for you. The most +important user of the XArray is the page cache. + +Each non-``NULL`` entry in the array has three bits associated with +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, +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`. +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`. + +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 +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 +conflict with value entries or internal entries. + +An unusual feature of the XArray is the ability to create entries which +occupy a range of indices. Once stored to, looking up any index in +the range will return the same entry as looking up any other index in +the range. Setting a mark on one index will set it on all of them. +Storing to any index will store to all of them. Multi-index entries can +be explicitly split into smaller entries, or storing ``NULL`` into any +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 +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 +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 +``NULL`` entry. There is no difference between an entry that has never +been stored to 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 +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. + +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 +returns ``-EEXIST`` 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`. + +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 +entry in the XArray. + +Finally, you can remove all entries from an XArray by calling +:c:func:`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. + +Memory allocation +----------------- + +The :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_reserve` +and :c:func:`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`. +If you don't need to know exactly which error occurred, using +:c:func:`xa_is_err` is slightly more efficient. + +Locking +------- + +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` + +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` + +Takes xa_lock internally: + * :c:func:`xa_store` + * :c:func:`xa_insert` + * :c:func:`xa_erase` + * :c:func:`xa_erase_bh` + * :c:func:`xa_erase_irq` + * :c:func:`xa_cmpxchg` + * :c:func:`xa_destroy` + * :c:func:`xa_set_mark` + * :c:func:`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_set_mark` + * :c:func:`__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 +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 +the scope of this document. + +The XArray does not disable interrupts or softirqs while modifying +the array. It is safe to read the XArray from interrupt or softirq +context as the RCU lock provides enough protection. + +If, for example, you want to store entries in the XArray in process +context and then erase them in softirq context, you can do that this way:: + + void foo_init(struct foo *foo) + { + xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH); + } + + int foo_store(struct foo *foo, unsigned long index, void *entry) + { + int err; + + xa_lock_bh(&foo->array); + err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL)); + if (!err) + foo->count++; + xa_unlock_bh(&foo->array); + return err; + } + + /* foo_erase() is only called from softirq context */ + void foo_erase(struct foo *foo, unsigned long index) + { + xa_lock(&foo->array); + __xa_erase(&foo->array, index); + foo->count--; + xa_unlock(&foo->array); + } + +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 +``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``. + +The above example also shows a common pattern of wanting to extend the +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` +in the interrupt handler. Some of the more common patterns have helper +functions such as :c:func:`xa_erase_bh` and :c:func:`xa_erase_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 +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 +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. + +Advanced API +============ + +The advanced API offers more flexibility and better performance at the +cost of an interface which can be harder to use and has fewer safeguards. +No locking is done for you by the advanced API, and you are required +to use the xa_lock while modifying the array. You can choose whether +to use the xa_lock or the RCU lock while doing read-only operations on +the array. You can mix advanced and normal operations on the same array; +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` +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 +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. + +If the xa_state is holding an ``ENOMEM`` error, calling :c:func:`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` +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 +that memory wasn't used, and there is no error (or some error that isn't +``ENOMEM``), then it will free the memory previously allocated. + +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``. + +.. flat-table:: + :widths: 1 1 6 + + * - Name + - Test + - Usage + + * - Node + - :c:func:`xa_is_node` + - An XArray node. May be visible when using a multi-index xa_state. + + * - Sibling + - :c:func:`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` + - 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. + +Other internal entries may be added in the future. As far as possible, they +will be handled by :c:func:`xas_retry`. + +Additional functionality +------------------------ + +The :c:func:`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 +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 +the marks reset, you should do that explicitly. + +The :c:func:`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. + +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 +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 +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`; +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 +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 +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`. + +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. +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 +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` +immediately before. + +You can call :c:func:`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. + +Multi-Index Entries +------------------- + +The XArray has the ability to tie multiple indices together so that +operations on one index affect all indices. For example, storing into +any index will change the value of the entry retrieved from any index. +Setting or clearing a mark on any index will set or clear the mark +on every index that is tied together. The current implementation +only allows tying ranges which are aligned powers of two together; +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 +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` +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 +iterate over every entry which overlaps the specified range. + +If :c:func:`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 +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 +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. + +Storing ``NULL`` into any index of a multi-index entry will set the entry +at every index to ``NULL`` and dissolve the tie. Splitting a multi-index +entry into entries occupying smaller ranges is not yet supported. + +Functions and structures +======================== + +.. kernel-doc:: include/linux/xarray.h +.. kernel-doc:: lib/xarray.c -- cgit v1.2.3 From 9f14d4f1f1045f161fd4db8a8e194b7825c2874a Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 1 Oct 2018 14:54:59 -0400 Subject: xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox --- Documentation/core-api/xarray.rst | 6 +++++ include/linux/xarray.h | 34 ++++++++++++++++++++++++++-- lib/test_xarray.c | 40 +++++++++++++++++++++++++++++++++ lib/xarray.c | 47 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 125 insertions(+), 2 deletions(-) (limited to 'Documentation/core-api') diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index 4b101b4f3aa1..2b397da84bcd 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -293,6 +293,12 @@ to :c:func:`xas_retry`, and retry the operation if it returns ``true``. of this RCU period. You should restart the lookup from the head of the array. + * - Zero + - :c:func:`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. + Other internal entries may be added in the future. As far as possible, they will be handled by :c:func:`xas_retry`. diff --git a/include/linux/xarray.h b/include/linux/xarray.h index deae17aa0ed7..bed63d3cfea8 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -32,7 +32,8 @@ * The following internal entries have a special meaning: * * 0-62: Sibling entries - * 256: Retry entry + * 256: Zero entry + * 257: Retry entry * * Errors are also represented as internal entries, but use the negative * space (-4094 to -2). They're never stored in the slots array; only @@ -277,6 +278,7 @@ void *xa_load(struct xarray *, unsigned long index); void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); void *xa_cmpxchg(struct xarray *, unsigned long index, void *old, void *entry, gfp_t); +int xa_reserve(struct xarray *, unsigned long index, gfp_t); bool xa_get_mark(struct xarray *, unsigned long index, xa_mark_t); void xa_set_mark(struct xarray *, unsigned long index, xa_mark_t); void xa_clear_mark(struct xarray *, unsigned long index, xa_mark_t); @@ -371,6 +373,20 @@ static inline int xa_insert(struct xarray *xa, unsigned long index, return -EEXIST; } +/** + * xa_release() - Release a reserved entry. + * @xa: XArray. + * @index: Index of entry. + * + * After calling xa_reserve(), you can call this function to release the + * reservation. If the entry at @index has been stored to, this function + * will do nothing. + */ +static inline void xa_release(struct xarray *xa, unsigned long index) +{ + xa_cmpxchg(xa, index, NULL, NULL, 0); +} + /** * xa_for_each() - Iterate over a portion of an XArray. * @xa: XArray. @@ -658,7 +674,19 @@ static inline bool xa_is_sibling(const void *entry) (entry < xa_mk_sibling(XA_CHUNK_SIZE - 1)); } -#define XA_RETRY_ENTRY xa_mk_internal(256) +#define XA_ZERO_ENTRY xa_mk_internal(256) +#define XA_RETRY_ENTRY xa_mk_internal(257) + +/** + * xa_is_zero() - Is the entry a zero entry? + * @entry: Entry retrieved from the XArray + * + * Return: %true if the entry is a zero entry. + */ +static inline bool xa_is_zero(const void *entry) +{ + return unlikely(entry == XA_ZERO_ENTRY); +} /** * xa_is_retry() - Is the entry a retry entry? @@ -880,6 +908,8 @@ static inline void xas_reset(struct xa_state *xas) */ static inline bool xas_retry(struct xa_state *xas, const void *entry) { + if (xa_is_zero(entry)) + return true; if (!xa_is_retry(entry)) return false; xas_reset(xas); diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 703370015d10..6aafd411a5c3 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -259,6 +259,45 @@ static noinline void check_cmpxchg(struct xarray *xa) XA_BUG_ON(xa, !xa_empty(xa)); } +static noinline void check_reserve(struct xarray *xa) +{ + void *entry; + unsigned long index = 0; + + /* An array with a reserved entry is not empty */ + XA_BUG_ON(xa, !xa_empty(xa)); + xa_reserve(xa, 12345678, GFP_KERNEL); + XA_BUG_ON(xa, xa_empty(xa)); + XA_BUG_ON(xa, xa_load(xa, 12345678)); + xa_release(xa, 12345678); + XA_BUG_ON(xa, !xa_empty(xa)); + + /* Releasing a used entry does nothing */ + xa_reserve(xa, 12345678, GFP_KERNEL); + XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL); + xa_release(xa, 12345678); + xa_erase_index(xa, 12345678); + XA_BUG_ON(xa, !xa_empty(xa)); + + /* cmpxchg sees a reserved entry as NULL */ + xa_reserve(xa, 12345678, GFP_KERNEL); + XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678), + GFP_NOWAIT) != NULL); + xa_release(xa, 12345678); + xa_erase_index(xa, 12345678); + XA_BUG_ON(xa, !xa_empty(xa)); + + /* Can iterate through a reserved entry */ + xa_store_index(xa, 5, GFP_KERNEL); + xa_reserve(xa, 6, GFP_KERNEL); + xa_store_index(xa, 7, GFP_KERNEL); + + xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { + XA_BUG_ON(xa, index != 5 && index != 7); + } + xa_destroy(xa); +} + static noinline void check_xas_erase(struct xarray *xa) { XA_STATE(xas, xa, 0); @@ -808,6 +847,7 @@ static int xarray_checks(void) check_xa_shrink(&array); check_xas_erase(&array); check_cmpxchg(&array); + check_reserve(&array); check_multi_store(&array); check_find(&array); check_destroy(&array); diff --git a/lib/xarray.c b/lib/xarray.c index ff37516fe832..546461914282 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1266,6 +1266,8 @@ void *xa_load(struct xarray *xa, unsigned long index) rcu_read_lock(); do { entry = xas_load(&xas); + if (xa_is_zero(entry)) + entry = NULL; } while (xas_retry(&xas, entry)); rcu_read_unlock(); @@ -1275,6 +1277,8 @@ EXPORT_SYMBOL(xa_load); static void *xas_result(struct xa_state *xas, void *curr) { + if (xa_is_zero(curr)) + return NULL; XA_NODE_BUG_ON(xas->xa_node, xa_is_internal(curr)); if (xas_error(xas)) curr = xas->xa_node; @@ -1394,6 +1398,8 @@ void *xa_cmpxchg(struct xarray *xa, unsigned long index, do { xas_lock(&xas); curr = xas_load(&xas); + if (curr == XA_ZERO_ENTRY) + curr = NULL; if (curr == old) xas_store(&xas, entry); xas_unlock(&xas); @@ -1430,6 +1436,8 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, do { curr = xas_load(&xas); + if (curr == XA_ZERO_ENTRY) + curr = NULL; if (curr == old) xas_store(&xas, entry); } while (__xas_nomem(&xas, gfp)); @@ -1438,6 +1446,43 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, } EXPORT_SYMBOL(__xa_cmpxchg); +/** + * xa_reserve() - Reserve this index in the XArray. + * @xa: XArray. + * @index: Index into array. + * @gfp: Memory allocation flags. + * + * Ensures there is somewhere to store an entry at @index in the array. + * If there is already something stored at @index, this function does + * nothing. If there was nothing there, the entry is marked as reserved. + * Loads from @index will continue to see a %NULL pointer until a + * subsequent store to @index. + * + * If you do not use the entry that you have reserved, call xa_release() + * or xa_erase() to free any unnecessary memory. + * + * Context: Process context. Takes and releases the xa_lock, IRQ or BH safe + * if specified in XArray flags. May sleep if the @gfp flags permit. + * Return: 0 if the reservation succeeded or -ENOMEM if it failed. + */ +int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) +{ + XA_STATE(xas, xa, index); + unsigned int lock_type = xa_lock_type(xa); + void *curr; + + do { + xas_lock_type(&xas, lock_type); + curr = xas_load(&xas); + if (!curr) + xas_store(&xas, XA_ZERO_ENTRY); + xas_unlock_type(&xas, lock_type); + } while (xas_nomem(&xas, gfp)); + + return xas_error(&xas); +} +EXPORT_SYMBOL(xa_reserve); + /** * __xa_set_mark() - Set this mark on this entry while locked. * @xa: XArray. @@ -1797,6 +1842,8 @@ void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift) pr_cont("retry (%ld)\n", xa_to_internal(entry)); else if (xa_is_sibling(entry)) pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry)); + else if (xa_is_zero(entry)) + pr_cont("zero (%ld)\n", xa_to_internal(entry)); else pr_cont("UNKNOWN ENTRY (%px)\n", entry); } -- cgit v1.2.3 From 371c752dc66948714ee3b66c3306f3ff1ff71d2e Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Wed, 4 Jul 2018 10:50:12 -0400 Subject: xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox --- Documentation/core-api/xarray.rst | 23 +++++++-- include/linux/xarray.h | 101 ++++++++++++++++++++++++++++++++++++++ lib/test_xarray.c | 61 +++++++++++++++++++++++ lib/xarray.c | 88 +++++++++++++++++++++++++++++++-- 4 files changed, 266 insertions(+), 7 deletions(-) (limited to 'Documentation/core-api') diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index 2b397da84bcd..463e4c798ec1 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -103,12 +103,25 @@ Finally, you can remove all entries from an XArray by calling 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. +ID assignment +------------- + +You can call :c:func:`xa_alloc` to store the entry at any 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 +interrupts while allocating the ID. Unlike :c:func:`xa_store`, allocating +a ``NULL`` pointer does not delete an entry. Instead it reserves an +entry like :c:func:`xa_reserve` and you can release it using either +:c:func:`xa_erase` or :c:func:`xa_release`. To use ID assignment, the +XArray must be defined with :c:func:`DEFINE_XARRAY_ALLOC`, or initialised +by passing ``XA_FLAGS_ALLOC`` to :c:func:`xa_init_flags`, + Memory allocation ----------------- -The :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_reserve` -and :c:func:`xa_insert` functions take a gfp_t parameter in case -the XArray needs to allocate memory to store this entry. +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 +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. @@ -143,6 +156,9 @@ Takes xa_lock internally: * :c:func:`xa_erase_bh` * :c:func:`xa_erase_irq` * :c:func:`xa_cmpxchg` + * :c:func:`xa_alloc` + * :c:func:`xa_alloc_bh` + * :c:func:`xa_alloc_irq` * :c:func:`xa_destroy` * :c:func:`xa_set_mark` * :c:func:`xa_clear_mark` @@ -152,6 +168,7 @@ Assumes xa_lock held on entry: * :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` diff --git a/include/linux/xarray.h b/include/linux/xarray.h index bed63d3cfea8..e0b57af52e9b 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -205,6 +205,7 @@ typedef unsigned __bitwise xa_mark_t; #define XA_MARK_2 ((__force xa_mark_t)2U) #define XA_PRESENT ((__force xa_mark_t)8U) #define XA_MARK_MAX XA_MARK_2 +#define XA_FREE_MARK XA_MARK_0 enum xa_lock_type { XA_LOCK_IRQ = 1, @@ -217,9 +218,12 @@ enum xa_lock_type { */ #define XA_FLAGS_LOCK_IRQ ((__force gfp_t)XA_LOCK_IRQ) #define XA_FLAGS_LOCK_BH ((__force gfp_t)XA_LOCK_BH) +#define XA_FLAGS_TRACK_FREE ((__force gfp_t)4U) #define XA_FLAGS_MARK(mark) ((__force gfp_t)((1U << __GFP_BITS_SHIFT) << \ (__force unsigned)(mark))) +#define XA_FLAGS_ALLOC (XA_FLAGS_TRACK_FREE | XA_FLAGS_MARK(XA_FREE_MARK)) + /** * struct xarray - The anchor of the XArray. * @xa_lock: Lock that protects the contents of the XArray. @@ -273,6 +277,15 @@ struct xarray { */ #define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0) +/** + * DEFINE_XARRAY_ALLOC() - Define an XArray which can allocate IDs. + * @name: A string that names your XArray. + * + * This is intended for file scope definitions of allocating XArrays. + * See also DEFINE_XARRAY(). + */ +#define DEFINE_XARRAY_ALLOC(name) DEFINE_XARRAY_FLAGS(name, XA_FLAGS_ALLOC) + void xa_init_flags(struct xarray *, gfp_t flags); void *xa_load(struct xarray *, unsigned long index); void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); @@ -439,6 +452,7 @@ void *__xa_erase(struct xarray *, unsigned long index); void *__xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); void *__xa_cmpxchg(struct xarray *, unsigned long index, void *old, void *entry, gfp_t); +int __xa_alloc(struct xarray *, u32 *id, u32 max, void *entry, gfp_t); void __xa_set_mark(struct xarray *, unsigned long index, xa_mark_t); void __xa_clear_mark(struct xarray *, unsigned long index, xa_mark_t); @@ -518,6 +532,93 @@ static inline void *xa_erase_irq(struct xarray *xa, unsigned long index) return entry; } +/** + * xa_alloc() - Find somewhere to store this entry in the XArray. + * @xa: XArray. + * @id: Pointer to ID. + * @max: Maximum ID to allocate (inclusive). + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @id and @max. + * Updates the @id pointer with the index, then stores the entry at that + * index. A concurrent lookup will not see an uninitialised @id. + * + * Context: Process context. Takes and releases the xa_lock. May sleep if + * the @gfp flags permit. + * Return: 0 on success, -ENOMEM if memory allocation fails or -ENOSPC if + * there is no more space in the XArray. + */ +static inline int xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, + gfp_t gfp) +{ + int err; + + xa_lock(xa); + err = __xa_alloc(xa, id, max, entry, gfp); + xa_unlock(xa); + + return err; +} + +/** + * xa_alloc_bh() - Find somewhere to store this entry in the XArray. + * @xa: XArray. + * @id: Pointer to ID. + * @max: Maximum ID to allocate (inclusive). + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @id and @max. + * Updates the @id pointer with the index, then stores the entry at that + * index. A concurrent lookup will not see an uninitialised @id. + * + * Context: Process context. Takes and releases the xa_lock while + * disabling softirqs. May sleep if the @gfp flags permit. + * Return: 0 on success, -ENOMEM if memory allocation fails or -ENOSPC if + * there is no more space in the XArray. + */ +static inline int xa_alloc_bh(struct xarray *xa, u32 *id, u32 max, void *entry, + gfp_t gfp) +{ + int err; + + xa_lock_bh(xa); + err = __xa_alloc(xa, id, max, entry, gfp); + xa_unlock_bh(xa); + + return err; +} + +/** + * xa_alloc_irq() - Find somewhere to store this entry in the XArray. + * @xa: XArray. + * @id: Pointer to ID. + * @max: Maximum ID to allocate (inclusive). + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @id and @max. + * Updates the @id pointer with the index, then stores the entry at that + * index. A concurrent lookup will not see an uninitialised @id. + * + * Context: Process context. Takes and releases the xa_lock while + * disabling interrupts. May sleep if the @gfp flags permit. + * Return: 0 on success, -ENOMEM if memory allocation fails or -ENOSPC if + * there is no more space in the XArray. + */ +static inline int xa_alloc_irq(struct xarray *xa, u32 *id, u32 max, void *entry, + gfp_t gfp) +{ + int err; + + xa_lock_irq(xa); + err = __xa_alloc(xa, id, max, entry, gfp); + xa_unlock_irq(xa); + + return err; +} + /* Everything below here is the Advanced API. Proceed with caution. */ /* diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 6aafd411a5c3..a752e6a37e6f 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -33,6 +33,15 @@ static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp) return xa_store(xa, index, xa_mk_value(index & LONG_MAX), gfp); } +static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp) +{ + u32 id = 0; + + XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_value(index & LONG_MAX), + gfp) != 0); + XA_BUG_ON(xa, id != index); +} + static void xa_erase_index(struct xarray *xa, unsigned long index) { XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_value(index & LONG_MAX)); @@ -404,6 +413,57 @@ static noinline void check_multi_store(struct xarray *xa) #endif } +static DEFINE_XARRAY_ALLOC(xa0); + +static noinline void check_xa_alloc(void) +{ + int i; + u32 id; + + /* An empty array should assign 0 to the first alloc */ + xa_alloc_index(&xa0, 0, GFP_KERNEL); + + /* Erasing it should make the array empty again */ + xa_erase_index(&xa0, 0); + XA_BUG_ON(&xa0, !xa_empty(&xa0)); + + /* And it should assign 0 again */ + xa_alloc_index(&xa0, 0, GFP_KERNEL); + + /* The next assigned ID should be 1 */ + xa_alloc_index(&xa0, 1, GFP_KERNEL); + xa_erase_index(&xa0, 1); + + /* Storing a value should mark it used */ + xa_store_index(&xa0, 1, GFP_KERNEL); + xa_alloc_index(&xa0, 2, GFP_KERNEL); + + /* If we then erase 0, it should be free */ + xa_erase_index(&xa0, 0); + xa_alloc_index(&xa0, 0, GFP_KERNEL); + + xa_erase_index(&xa0, 1); + xa_erase_index(&xa0, 2); + + for (i = 1; i < 5000; i++) { + xa_alloc_index(&xa0, i, GFP_KERNEL); + } + + xa_destroy(&xa0); + + id = 0xfffffffeU; + XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), + GFP_KERNEL) != 0); + XA_BUG_ON(&xa0, id != 0xfffffffeU); + XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), + GFP_KERNEL) != 0); + XA_BUG_ON(&xa0, id != 0xffffffffU); + XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), + GFP_KERNEL) != -ENOSPC); + XA_BUG_ON(&xa0, id != 0xffffffffU); + xa_destroy(&xa0); +} + static noinline void __check_store_iter(struct xarray *xa, unsigned long start, unsigned int order, unsigned int present) { @@ -849,6 +909,7 @@ static int xarray_checks(void) check_cmpxchg(&array); check_reserve(&array); check_multi_store(&array); + check_xa_alloc(); check_find(&array); check_destroy(&array); check_move(&array); diff --git a/lib/xarray.c b/lib/xarray.c index 546461914282..9a0d49d4b5f0 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -52,6 +52,11 @@ static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type) xas_unlock(xas); } +static inline bool xa_track_free(const struct xarray *xa) +{ + return xa->xa_flags & XA_FLAGS_TRACK_FREE; +} + static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark) { if (!(xa->xa_flags & XA_FLAGS_MARK(mark))) @@ -94,6 +99,11 @@ static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark) return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE); } +static inline void node_mark_all(struct xa_node *node, xa_mark_t mark) +{ + bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE); +} + #define mark_inc(mark) do { \ mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \ } while (0) @@ -416,6 +426,8 @@ static void xas_shrink(struct xa_state *xas) xas->xa_node = XAS_BOUNDS; RCU_INIT_POINTER(xa->xa_head, entry); + if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK)) + xa_mark_clear(xa, XA_FREE_MARK); node->count = 0; node->nr_values = 0; @@ -549,8 +561,15 @@ static int xas_expand(struct xa_state *xas, void *head) /* Propagate the aggregated mark info to the new child */ for (;;) { - if (xa_marked(xa, mark)) + if (xa_track_free(xa) && mark == XA_FREE_MARK) { + node_mark_all(node, XA_FREE_MARK); + if (!xa_marked(xa, XA_FREE_MARK)) { + node_clear_mark(node, 0, XA_FREE_MARK); + xa_mark_set(xa, XA_FREE_MARK); + } + } else if (xa_marked(xa, mark)) { node_set_mark(node, 0, mark); + } if (mark == XA_MARK_MAX) break; mark_inc(mark); @@ -624,6 +643,8 @@ static void *xas_create(struct xa_state *xas) node = xas_alloc(xas, shift); if (!node) break; + if (xa_track_free(xa)) + node_mark_all(node, XA_FREE_MARK); rcu_assign_pointer(*slot, xa_mk_node(node)); } else if (xa_is_node(entry)) { node = xa_to_node(entry); @@ -882,7 +903,10 @@ void xas_init_marks(const struct xa_state *xas) xa_mark_t mark = 0; for (;;) { - xas_clear_mark(xas, mark); + if (xa_track_free(xas->xa) && mark == XA_FREE_MARK) + xas_set_mark(xas, mark); + else + xas_clear_mark(xas, mark); if (mark == XA_MARK_MAX) break; mark_inc(mark); @@ -1333,6 +1357,8 @@ void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) do { xas_lock(&xas); curr = xas_store(&xas, entry); + if (xa_track_free(xa) && entry) + xas_clear_mark(&xas, XA_FREE_MARK); xas_unlock(&xas); } while (xas_nomem(&xas, gfp)); @@ -1365,6 +1391,8 @@ void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) do { curr = xas_store(&xas, entry); + if (xa_track_free(xa) && entry) + xas_clear_mark(&xas, XA_FREE_MARK); } while (__xas_nomem(&xas, gfp)); return xas_result(&xas, curr); @@ -1400,8 +1428,11 @@ void *xa_cmpxchg(struct xarray *xa, unsigned long index, curr = xas_load(&xas); if (curr == XA_ZERO_ENTRY) curr = NULL; - if (curr == old) + if (curr == old) { xas_store(&xas, entry); + if (xa_track_free(xa) && entry) + xas_clear_mark(&xas, XA_FREE_MARK); + } xas_unlock(&xas); } while (xas_nomem(&xas, gfp)); @@ -1438,8 +1469,11 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, curr = xas_load(&xas); if (curr == XA_ZERO_ENTRY) curr = NULL; - if (curr == old) + if (curr == old) { xas_store(&xas, entry); + if (xa_track_free(xa) && entry) + xas_clear_mark(&xas, XA_FREE_MARK); + } } while (__xas_nomem(&xas, gfp)); return xas_result(&xas, curr); @@ -1483,6 +1517,52 @@ int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) } EXPORT_SYMBOL(xa_reserve); +/** + * __xa_alloc() - Find somewhere to store this entry in the XArray. + * @xa: XArray. + * @id: Pointer to ID. + * @max: Maximum ID to allocate (inclusive). + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @id and @max. + * Updates the @id pointer with the index, then stores the entry at that + * index. A concurrent lookup will not see an uninitialised @id. + * + * Context: Any context. Expects xa_lock to be held on entry. May + * release and reacquire xa_lock if @gfp flags permit. + * Return: 0 on success, -ENOMEM if memory allocation fails or -ENOSPC if + * there is no more space in the XArray. + */ +int __xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, gfp_t gfp) +{ + XA_STATE(xas, xa, 0); + int err; + + if (WARN_ON_ONCE(xa_is_internal(entry))) + return -EINVAL; + if (WARN_ON_ONCE(!xa_track_free(xa))) + return -EINVAL; + + if (!entry) + entry = XA_ZERO_ENTRY; + + do { + xas.xa_index = *id; + xas_find_marked(&xas, max, XA_FREE_MARK); + if (xas.xa_node == XAS_RESTART) + xas_set_err(&xas, -ENOSPC); + xas_store(&xas, entry); + xas_clear_mark(&xas, XA_FREE_MARK); + } while (__xas_nomem(&xas, gfp)); + + err = xas_error(&xas); + if (!err) + *id = xas.xa_index; + return err; +} +EXPORT_SYMBOL(__xa_alloc); + /** * __xa_set_mark() - Set this mark on this entry while locked. * @xa: XArray. -- cgit v1.2.3 From 0e9446c35a80931044b6d8d2d74a9cabd248539f Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Wed, 15 Aug 2018 14:13:29 -0400 Subject: xarray: Add range store functionality This version of xa_store_range() really only supports load and store. Our only user only needs basic load and store functionality, so there's no need to do the extra work to support marking and overlapping stores correctly yet. Signed-off-by: Matthew Wilcox --- Documentation/core-api/xarray.rst | 8 ++++ include/linux/xarray.h | 2 + lib/test_xarray.c | 34 ++++++++++++++ lib/xarray.c | 97 ++++++++++++++++++++++++++++++++++++++- 4 files changed, 139 insertions(+), 2 deletions(-) (limited to 'Documentation/core-api') diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index 463e4c798ec1..a4e705108f42 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -98,6 +98,13 @@ 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 entry in the XArray. +Calling :c:func:`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. + Finally, you can remove all entries from an XArray by calling :c:func:`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 @@ -156,6 +163,7 @@ Takes xa_lock internally: * :c:func:`xa_erase_bh` * :c:func:`xa_erase_irq` * :c:func:`xa_cmpxchg` + * :c:func:`xa_store_range` * :c:func:`xa_alloc` * :c:func:`xa_alloc_bh` * :c:func:`xa_alloc_irq` diff --git a/include/linux/xarray.h b/include/linux/xarray.h index e0b57af52e9b..d9514928ddac 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -292,6 +292,8 @@ void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); void *xa_cmpxchg(struct xarray *, unsigned long index, void *old, void *entry, gfp_t); int xa_reserve(struct xarray *, unsigned long index, gfp_t); +void *xa_store_range(struct xarray *, unsigned long first, unsigned long last, + void *entry, gfp_t); bool xa_get_mark(struct xarray *, unsigned long index, xa_mark_t); void xa_set_mark(struct xarray *, unsigned long index, xa_mark_t); void xa_clear_mark(struct xarray *, unsigned long index, xa_mark_t); diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 0f06a93b4d0e..aa47754150ce 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1039,6 +1039,39 @@ static noinline void check_create_range(struct xarray *xa) check_create_range_3(); } +static noinline void __check_store_range(struct xarray *xa, unsigned long first, + unsigned long last) +{ +#ifdef CONFIG_XARRAY_MULTI + xa_store_range(xa, first, last, xa_mk_value(first), GFP_KERNEL); + + XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_value(first)); + XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_value(first)); + XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL); + XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL); + + xa_store_range(xa, first, last, NULL, GFP_KERNEL); +#endif + + XA_BUG_ON(xa, !xa_empty(xa)); +} + +static noinline void check_store_range(struct xarray *xa) +{ + unsigned long i, j; + + for (i = 0; i < 128; i++) { + for (j = i; j < 128; j++) { + __check_store_range(xa, i, j); + __check_store_range(xa, 128 + i, 128 + j); + __check_store_range(xa, 4095 + i, 4095 + j); + __check_store_range(xa, 4096 + i, 4096 + j); + __check_store_range(xa, 123456 + i, 123456 + j); + __check_store_range(xa, UINT_MAX + i, UINT_MAX + j); + } + } +} + static LIST_HEAD(shadow_nodes); static void test_update_node(struct xa_node *node) @@ -1184,6 +1217,7 @@ static int xarray_checks(void) check_destroy(&array); check_move(&array); check_create_range(&array); + check_store_range(&array); check_store_iter(&array); check_workingset(&array, 0); diff --git a/lib/xarray.c b/lib/xarray.c index 9a0d49d4b5f0..8b176f009c08 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -376,6 +376,14 @@ static void *xas_alloc(struct xa_state *xas, unsigned int shift) return node; } +#ifdef CONFIG_XARRAY_MULTI +/* Returns the number of indices covered by a given xa_state */ +static unsigned long xas_size(const struct xa_state *xas) +{ + return (xas->xa_sibs + 1UL) << xas->xa_shift; +} +#endif + /* * Use this to calculate the maximum index that will need to be created * in order to add the entry described by @xas. Because we cannot store a @@ -388,8 +396,7 @@ static unsigned long xas_max(struct xa_state *xas) #ifdef CONFIG_XARRAY_MULTI if (xas->xa_shift || xas->xa_sibs) { - unsigned long mask; - mask = (((xas->xa_sibs + 1UL) << xas->xa_shift) - 1); + unsigned long mask = xas_size(xas) - 1; max |= mask; if (mask == max) max++; @@ -1517,6 +1524,92 @@ int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) } EXPORT_SYMBOL(xa_reserve); +#ifdef CONFIG_XARRAY_MULTI +static void xas_set_range(struct xa_state *xas, unsigned long first, + unsigned long last) +{ + unsigned int shift = 0; + unsigned long sibs = last - first; + unsigned int offset = XA_CHUNK_MASK; + + xas_set(xas, first); + + while ((first & XA_CHUNK_MASK) == 0) { + if (sibs < XA_CHUNK_MASK) + break; + if ((sibs == XA_CHUNK_MASK) && (offset < XA_CHUNK_MASK)) + break; + shift += XA_CHUNK_SHIFT; + if (offset == XA_CHUNK_MASK) + offset = sibs & XA_CHUNK_MASK; + sibs >>= XA_CHUNK_SHIFT; + first >>= XA_CHUNK_SHIFT; + } + + offset = first & XA_CHUNK_MASK; + if (offset + sibs > XA_CHUNK_MASK) + sibs = XA_CHUNK_MASK - offset; + if ((((first + sibs + 1) << shift) - 1) > last) + sibs -= 1; + + xas->xa_shift = shift; + xas->xa_sibs = sibs; +} + +/** + * xa_store_range() - Store this entry at a range of indices in the XArray. + * @xa: XArray. + * @first: First index to affect. + * @last: Last index to affect. + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * After this function returns, loads from any index between @first and @last, + * inclusive will return @entry. + * Storing into an existing multislot entry updates the entry of every index. + * The marks associated with @index are unaffected unless @entry is %NULL. + * + * Context: Process context. Takes and releases the xa_lock. May sleep + * if the @gfp flags permit. + * Return: %NULL on success, xa_err(-EINVAL) if @entry cannot be stored in + * an XArray, or xa_err(-ENOMEM) if memory allocation failed. + */ +void *xa_store_range(struct xarray *xa, unsigned long first, + unsigned long last, void *entry, gfp_t gfp) +{ + XA_STATE(xas, xa, 0); + + if (WARN_ON_ONCE(xa_is_internal(entry))) + return XA_ERROR(-EINVAL); + if (last < first) + return XA_ERROR(-EINVAL); + + do { + xas_lock(&xas); + if (entry) { + unsigned int order = (last == ~0UL) ? 64 : + ilog2(last + 1); + xas_set_order(&xas, last, order); + xas_create(&xas); + if (xas_error(&xas)) + goto unlock; + } + do { + xas_set_range(&xas, first, last); + xas_store(&xas, entry); + if (xas_error(&xas)) + goto unlock; + first += xas_size(&xas); + } while (first <= last); +unlock: + xas_unlock(&xas); + } while (xas_nomem(&xas, gfp)); + + return xas_result(&xas, NULL); +} +EXPORT_SYMBOL(xa_store_range); +#endif /* CONFIG_XARRAY_MULTI */ + /** * __xa_alloc() - Find somewhere to store this entry in the XArray. * @xa: XArray. -- cgit v1.2.3 From 530d4c0cfd5b71caf2d17f73a80696c4a4509813 Mon Sep 17 00:00:00 2001 From: Mike Rapoport Date: Tue, 30 Oct 2018 15:09:54 -0700 Subject: docs/boot-time-mm: remove bootmem documentation Link: http://lkml.kernel.org/r/1536927045-23536-31-git-send-email-rppt@linux.vnet.ibm.com Signed-off-by: Mike Rapoport Cc: Catalin Marinas Cc: Chris Zankel Cc: "David S. Miller" Cc: Geert Uytterhoeven Cc: Greentime Hu Cc: Greg Kroah-Hartman Cc: Guan Xuetao Cc: Ingo Molnar Cc: "James E.J. Bottomley" Cc: Jonas Bonn Cc: Jonathan Corbet Cc: Ley Foon Tan Cc: Mark Salter Cc: Martin Schwidefsky Cc: Matt Turner Cc: Michael Ellerman Cc: Michal Hocko Cc: Michal Simek Cc: Palmer Dabbelt Cc: Paul Burton Cc: Richard Kuo Cc: Richard Weinberger Cc: Rich Felker Cc: Russell King Cc: Serge Semin Cc: Thomas Gleixner Cc: Tony Luck Cc: Vineet Gupta Cc: Yoshinori Sato Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- Documentation/core-api/boot-time-mm.rst | 69 +++++---------------------------- 1 file changed, 9 insertions(+), 60 deletions(-) (limited to 'Documentation/core-api') diff --git a/Documentation/core-api/boot-time-mm.rst b/Documentation/core-api/boot-time-mm.rst index 6e12e89a03e0..e5ec9f1a563d 100644 --- a/Documentation/core-api/boot-time-mm.rst +++ b/Documentation/core-api/boot-time-mm.rst @@ -5,54 +5,23 @@ Boot time memory management Early system initialization cannot use "normal" memory management simply because it is not set up yet. But there is still need to allocate memory for various data structures, for instance for the -physical page allocator. To address this, a specialized allocator -called the :ref:`Boot Memory Allocator `, or bootmem, was -introduced. Several years later PowerPC developers added a "Logical -Memory Blocks" allocator, which was later adopted by other -architectures and renamed to :ref:`memblock `. There is also -a compatibility layer called `nobootmem` that translates bootmem -allocation interfaces to memblock calls. +physical page allocator. -The selection of the early allocator is done using -``CONFIG_NO_BOOTMEM`` and ``CONFIG_HAVE_MEMBLOCK`` kernel -configuration options. These options are enabled or disabled -statically by the architectures' Kconfig files. - -* Architectures that rely only on bootmem select - ``CONFIG_NO_BOOTMEM=n && CONFIG_HAVE_MEMBLOCK=n``. -* The users of memblock with the nobootmem compatibility layer set - ``CONFIG_NO_BOOTMEM=y && CONFIG_HAVE_MEMBLOCK=y``. -* And for those that use both memblock and bootmem the configuration - includes ``CONFIG_NO_BOOTMEM=n && CONFIG_HAVE_MEMBLOCK=y``. - -Whichever allocator is used, it is the responsibility of the -architecture specific initialization to set it up in -:c:func:`setup_arch` and tear it down in :c:func:`mem_init` functions. +A specialized allocator called ``memblock`` performs the +boot time memory management. The architecture specific initialization +must set it up in :c:func:`setup_arch` and tear it down in +:c:func:`mem_init` functions. Once the early memory management is available it offers a variety of functions and macros for memory allocations. The allocation request may be directed to the first (and probably the only) node or to a particular node in a NUMA system. There are API variants that panic -when an allocation fails and those that don't. And more recent and -advanced memblock even allows controlling its own behaviour. - -.. _bootmem: - -Bootmem -======= +when an allocation fails and those that don't. -(mostly stolen from Mel Gorman's "Understanding the Linux Virtual -Memory Manager" `book`_) +Memblock also offers a variety of APIs that control its own behaviour. -.. _book: https://www.kernel.org/doc/gorman/ - -.. kernel-doc:: mm/bootmem.c - :doc: bootmem overview - -.. _memblock: - -Memblock -======== +Memblock Overview +================= .. kernel-doc:: mm/memblock.c :doc: memblock overview @@ -61,26 +30,6 @@ Memblock Functions and structures ======================== -Common API ----------- - -The functions that are described in this section are available -regardless of what early memory manager is enabled. - -.. kernel-doc:: mm/nobootmem.c - -Bootmem specific API --------------------- - -These interfaces available only with bootmem, i.e when ``CONFIG_NO_BOOTMEM=n`` - -.. kernel-doc:: include/linux/bootmem.h -.. kernel-doc:: mm/bootmem.c - :functions: - -Memblock specific API ---------------------- - Here is the description of memblock data structures, functions and macros. Some of them are actually internal, but since they are documented it would be silly to omit them. Besides, reading the -- cgit v1.2.3