Merge tag 'mm-stable-2024-03-13-20-04' of git://git.kernel.org/pub/scm/linux/kernel...

[sfrench/cifs-2.6.git] / lib / maple_tree.c

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 82fb5195c2354fde935b04c1eb1ae3dde39d92bb..55e1b35bf877ea529d4f278692c57f46a259d568 100644 (file)
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4288,6 +4288,56 @@ exists:
 
 }
 
+/**
+ * mas_alloc_cyclic() - Internal call to find somewhere to store an entry
+ * @mas: The maple state.
+ * @startp: Pointer to ID.
+ * @range_lo: Lower bound of range to search.
+ * @range_hi: Upper bound of range to search.
+ * @entry: The entry to store.
+ * @next: Pointer to next ID to allocate.
+ * @gfp: The GFP_FLAGS to use for allocations.
+ *
+ * Return: 0 if the allocation succeeded without wrapping, 1 if the
+ * allocation succeeded after wrapping, or -EBUSY if there are no
+ * free entries.
+ */
+int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,
+               void *entry, unsigned long range_lo, unsigned long range_hi,
+               unsigned long *next, gfp_t gfp)
+{
+       unsigned long min = range_lo;
+       int ret = 0;
+
+       range_lo = max(min, *next);
+       ret = mas_empty_area(mas, range_lo, range_hi, 1);
+       if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) {
+               mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED;
+               ret = 1;
+       }
+       if (ret < 0 && range_lo > min) {
+               ret = mas_empty_area(mas, min, range_hi, 1);
+               if (ret == 0)
+                       ret = 1;
+       }
+       if (ret < 0)
+               return ret;
+
+       do {
+               mas_insert(mas, entry);
+       } while (mas_nomem(mas, gfp));
+       if (mas_is_err(mas))
+               return xa_err(mas->node);
+
+       *startp = mas->index;
+       *next = *startp + 1;
+       if (*next == 0)
+               mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED;
+
+       return ret;
+}
+EXPORT_SYMBOL(mas_alloc_cyclic);
+
 static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index)
 {
 retry:
@@ -6441,6 +6491,49 @@ unlock:
 }
 EXPORT_SYMBOL(mtree_alloc_range);
 
+/**
+ * mtree_alloc_cyclic() - Find somewhere to store this entry in the tree.
+ * @mt: The maple tree.
+ * @startp: Pointer to ID.
+ * @range_lo: Lower bound of range to search.
+ * @range_hi: Upper bound of range to search.
+ * @entry: The entry to store.
+ * @next: Pointer to next ID to allocate.
+ * @gfp: The GFP_FLAGS to use for allocations.
+ *
+ * Finds an empty entry in @mt after @next, stores the new index into
+ * the @id pointer, stores the entry at that index, then updates @next.
+ *
+ * @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag.
+ *
+ * Context: Any context.  Takes and releases the mt.lock.  May sleep if
+ * the @gfp flags permit.
+ *
+ * Return: 0 if the allocation succeeded without wrapping, 1 if the
+ * allocation succeeded after wrapping, -ENOMEM if memory could not be
+ * allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no
+ * free entries.
+ */
+int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp,
+               void *entry, unsigned long range_lo, unsigned long range_hi,
+               unsigned long *next, gfp_t gfp)
+{
+       int ret;
+
+       MA_STATE(mas, mt, 0, 0);
+
+       if (!mt_is_alloc(mt))
+               return -EINVAL;
+       if (WARN_ON_ONCE(mt_is_reserved(entry)))
+               return -EINVAL;
+       mtree_lock(mt);
+       ret = mas_alloc_cyclic(&mas, startp, entry, range_lo, range_hi,
+                              next, gfp);
+       mtree_unlock(mt);
+       return ret;
+}
+EXPORT_SYMBOL(mtree_alloc_cyclic);
+
 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
                void *entry, unsigned long size, unsigned long min,
                unsigned long max, gfp_t gfp)