lkml.org 
[lkml]   [2018]   [Jun]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH v14 17/74] xarray: Add xas_for_each_conflict
    Date
    This iterator iterates over each entry that is stored in the index or
    indices specified by the xa_state. This is intended for use for a
    conditional store of a multiindex entry, or to allow entries which are
    about to be removed from the xarray to be disposed of properly.

    Signed-off-by: Matthew Wilcox <willy@infradead.org>
    ---
    include/linux/xarray.h | 17 ++++++++++++
    lib/test_xarray.c | 63 ++++++++++++++++++++++++++++++++++++++++++
    lib/xarray.c | 61 ++++++++++++++++++++++++++++++++++++++++
    3 files changed, 141 insertions(+)

    diff --git a/include/linux/xarray.h b/include/linux/xarray.h
    index 921d41034d7d..0a9f66266c9a 100644
    --- a/include/linux/xarray.h
    +++ b/include/linux/xarray.h
    @@ -769,6 +769,7 @@ static inline bool xas_retry(struct xa_state *xas, const void *entry)
    void *xas_load(struct xa_state *);
    void *xas_store(struct xa_state *, void *entry);
    void *xas_find(struct xa_state *, unsigned long max);
    +void *xas_next_conflict(struct xa_state *);

    bool xas_get_tag(const struct xa_state *, xa_tag_t);
    void xas_set_tag(const struct xa_state *, xa_tag_t);
    @@ -983,6 +984,22 @@ enum {
    for (entry = xas_find_tagged(xas, max, tag); entry; \
    entry = xas_next_tagged(xas, max, tag))

    +/**
    + * xas_for_each_conflict() - Iterate over a range of an XArray.
    + * @xas: XArray operation state.
    + * @entry: Entry retrieved from the array.
    + *
    + * The loop body will be executed for each entry in the XArray that lies
    + * within the range specified by @xas. If the loop completes successfully,
    + * any entries that lie in this range will be replaced by @entry. The caller
    + * may break out of the loop; if they do so, the contents of the XArray will
    + * be unchanged. The operation may fail due to an out of memory condition.
    + * The caller may also call xa_set_err() to exit the loop while setting an
    + * error to record the reason.
    + */
    +#define xas_for_each_conflict(xas, entry) \
    + while ((entry = xas_next_conflict(xas)))
    +
    void *__xas_next(struct xa_state *);
    void *__xas_prev(struct xa_state *);

    diff --git a/lib/test_xarray.c b/lib/test_xarray.c
    index e74ade12c663..818cfd8746ba 100644
    --- a/lib/test_xarray.c
    +++ b/lib/test_xarray.c
    @@ -315,6 +315,68 @@ static void check_multi_store(struct xarray *xa)
    }
    }

    +static void __check_store_iter(struct xarray *xa, unsigned long start,
    + unsigned int order, unsigned int present)
    +{
    + XA_STATE_ORDER(xas, xa, start, order);
    + void *entry;
    + unsigned int count = 0;
    +
    +retry:
    + xas_for_each_conflict(&xas, entry) {
    + XA_BUG_ON(xa, !xa_is_value(entry));
    + XA_BUG_ON(xa, entry < xa_mk_value(start));
    + XA_BUG_ON(xa, entry > xa_mk_value(start + (1UL << order) - 1));
    + count++;
    + }
    + xas_store(&xas, xa_mk_value(start));
    + if (xas_nomem(&xas, GFP_KERNEL)) {
    + count = 0;
    + goto retry;
    + }
    + XA_BUG_ON(xa, xas_error(&xas));
    + XA_BUG_ON(xa, count != present);
    + XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_value(start));
    + XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
    + xa_mk_value(start));
    + xa_erase_value(xa, start);
    +}
    +
    +static void check_store_iter(struct xarray *xa)
    +{
    + unsigned int i, j;
    +
    + for (i = 0; i < 20; i++) {
    + unsigned int min = 1 << i;
    + unsigned int max = (2 << i) - 1;
    + __check_store_iter(xa, 0, i, 0);
    + XA_BUG_ON(xa, !xa_empty(xa));
    + __check_store_iter(xa, min, i, 0);
    + XA_BUG_ON(xa, !xa_empty(xa));
    +
    + xa_store_value(xa, min, GFP_KERNEL);
    + __check_store_iter(xa, min, i, 1);
    + XA_BUG_ON(xa, !xa_empty(xa));
    + xa_store_value(xa, max, GFP_KERNEL);
    + __check_store_iter(xa, min, i, 1);
    + XA_BUG_ON(xa, !xa_empty(xa));
    +
    + for (j = 0; j < min; j++)
    + xa_store_value(xa, j, GFP_KERNEL);
    + __check_store_iter(xa, 0, i, min);
    + XA_BUG_ON(xa, !xa_empty(xa));
    + for (j = 0; j < min; j++)
    + xa_store_value(xa, min + j, GFP_KERNEL);
    + __check_store_iter(xa, min, i, min);
    + XA_BUG_ON(xa, !xa_empty(xa));
    + }
    + xa_store_value(xa, 63, GFP_KERNEL);
    + xa_store_value(xa, 65, GFP_KERNEL);
    + __check_store_iter(xa, 64, 2, 1);
    + xa_erase_value(xa, 63);
    + XA_BUG_ON(xa, !xa_empty(xa));
    +}
    +
    static void check_multi_find(struct xarray *xa)
    {
    unsigned long index;
    @@ -506,6 +568,7 @@ static int xarray_checks(void)
    check_multi_store(&array);
    check_find(&array);
    check_move(&array);
    + check_store_iter(&array);

    printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
    return (tests_run != tests_passed) ? 0 : -EINVAL;
    diff --git a/lib/xarray.c b/lib/xarray.c
    index ab1b6786711e..31c5332c8146 100644
    --- a/lib/xarray.c
    +++ b/lib/xarray.c
    @@ -1086,6 +1086,67 @@ void *xas_find_tagged(struct xa_state *xas, unsigned long max, xa_tag_t tag)
    }
    EXPORT_SYMBOL_GPL(xas_find_tagged);

    +/**
    + * xas_next_conflict() - Step for xas_for_each_conflict().
    + * @xas: XArray operation state.
    + *
    + * This function does the work for xas_for_each_conflict().
    + *
    + * Context: Any context. Expects xa_lock to be held.
    + * Return: The next entry in the range covered by @xas or %NULL.
    + */
    +void *xas_next_conflict(struct xa_state *xas)
    +{
    + void *curr;
    +
    + if (xas_error(xas))
    + return NULL;
    +
    + if (!xas->xa_node)
    + return NULL;
    +
    + if (xas_top(xas->xa_node)) {
    + curr = xas_start(xas);
    + if (!curr)
    + return NULL;
    + while (xa_is_node(curr)) {
    + struct xa_node *node = xa_to_node(curr);
    + curr = xas_descend(xas, node);
    + }
    + if (curr)
    + return curr;
    + }
    +
    + if (xas->xa_node->shift > xas->xa_shift)
    + return NULL;
    +
    + for (;;) {
    + if (xas->xa_node->shift == xas->xa_shift) {
    + if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs)
    + break;
    + } else if (xas->xa_offset == XA_CHUNK_MASK) {
    + xas->xa_offset = xas->xa_node->offset;
    + xas->xa_node = xas->xa_node->parent;
    + if (!xas->xa_node)
    + break;
    + continue;
    + }
    + curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);
    + if (xa_is_sibling(curr))
    + continue;
    + while (xa_is_node(curr)) {
    + xas->xa_node = xa_to_node(curr);
    + xas->xa_offset = 0;
    + curr = xa_entry_locked(xas->xa, xas->xa_node, 0);
    + }
    + if (curr)
    + return curr;
    + }
    + xas->xa_offset -= xas->xa_sibs;
    + return NULL;
    +}
    +EXPORT_SYMBOL_GPL(xas_next_conflict);
    +
    /**
    * xa_init_flags() - Initialise an empty XArray with flags.
    * @xa: XArray.
    --
    2.17.1
    \
     
     \ /
      Last update: 2018-06-17 04:18    [W:3.635 / U:0.008 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site