On Tue, Jan 15, 2019 at 10:01:23PM +0200, Leon Romanovsky wrote:
> It will be something like that:
>
> diff --git a/drivers/infiniband/core/restrack.c b/drivers/infiniband/core/restrack.c
> index 58a60730e835..262e6499d40d 100644
> +++ b/drivers/infiniband/core/restrack.c
> @@ -10,6 +10,8 @@
> #include <linux/sched/task.h>
> #include <linux/pid_namespace.h>
> #include <linux/rwsem.h>
> +#include <linux/spinlock.h>
> +#include <linux/overflow.h>
>
> #include "cma_priv.h"
>
> @@ -35,6 +37,14 @@ struct rdma_restrack_root {
> * @max: Maximal supported number of indexes
> */
> u32 max;
> + /**
> + * @next: Next ID to support cyclic allocation
> + */
> + u32 next_id;
> + /**
> + * @next_lock: Lock to protect next-ID generation
> + */
> + spinlock_t next_lock;
> };
>
> /**
> @@ -58,6 +68,7 @@ int rdma_restrack_init(struct ib_device *dev)
> init_rwsem(&rt[i].rwsem);
> xa_init_flags(&rt[i].xa, XA_FLAGS_ALLOC);
> rt[i].max = U32_MAX;
> + spin_lock_init(&rt[i].next_lock);
> }
>
> return 0;
> @@ -282,14 +293,28 @@ int rdma_restrack_add(struct rdma_restrack_entry *res)
> res->valid = true;
>
> if (rt[res->type].max) {
> + u32 a = 1, b;
> +
> /* Not HW-capable device */
> - res->id = rt[res->type].reserved;
> + spin_lock(&rt[res->type].next_lock);
> + res->id = rt[res->type].next_id;
> ret = xa_alloc(xa, &res->id, rt[res->type].max, res,
> GFP_KERNEL);
Can't use a spinlock if this is GFP_KERNEL, use a mutex?
> + if (ret) {
> + spin_unlock(&rt[res->type].next_lock);
> + goto out;
> + }
> +
> + if (check_add_overflow(res->id, a, &b))
if (res->id == rt[res->type].max)
> + rt[res->type].next_id = rt[res->type].reserved;
> + else
> + rt[res->type].next_id = res->id + 1;
> + spin_unlock(&rt[res->type].next_lock);
> } else {
> ret = xa_insert(xa, res->id, res, GFP_KERNEL);
This seems simple enough to be worthwhile.
Matt, down the road can we get an xa_alloc_cyclic helper that handles
this and the required locking? I have another need in the works as
well..
Here is a musing on one possible arrangement:
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index f492e21c4aa2c8..5fbe5591a8f941 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -393,7 +393,8 @@ 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);
+int __xa_alloc(struct xarray *xa, u32 *cyclic_next, u32 *id, u32 max,
+ void *entry, gfp_t gfp);
int __xa_reserve(struct xarray *, unsigned long index, 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);
@@ -658,7 +659,42 @@ static inline int xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry,
int err;
xa_lock(xa);
- err = __xa_alloc(xa, id, max, entry, gfp);
+ err = __xa_alloc(xa, NULL, id, max, entry, gfp);
+ xa_unlock(xa);
+
+ return err;
+}
+
+/**
+ * xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
+ * @xa: XArray.
+ * @cyclic_next: Storage to compute a cyclic ID
+ * @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.
+ *
+ * If @cyclic_next is set then the returned value will try to start after this
+ * value, but the range will still be bounded by @id and @max as
+ * normal. xarray takes care to manage cyclic_next concurrently, callers
+ * should not alter it.
+ *
+ * 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_cyclic(struct xarray *xa, u32 *cyclic_next, u32 *id,
+ u32 max, void *entry, gfp_t gfp)
+{
+ int err;
+
+ xa_lock(xa);
+ err = __xa_alloc(xa, cyclic_next, id, max, entry, gfp);
xa_unlock(xa);
return err;
@@ -687,7 +723,7 @@ static inline int xa_alloc_bh(struct xarray *xa, u32 *id, u32 max, void *entry,
int err;
xa_lock_bh(xa);
- err = __xa_alloc(xa, id, max, entry, gfp);
+ err = __xa_alloc(xa, NULL, id, max, entry, gfp);
xa_unlock_bh(xa);
return err;
@@ -716,7 +752,7 @@ static inline int xa_alloc_irq(struct xarray *xa, u32 *id, u32 max, void *entry,
int err;
xa_lock_irq(xa);
- err = __xa_alloc(xa, id, max, entry, gfp);
+ err = __xa_alloc(xa, NULL, id, max, entry, gfp);
xa_unlock_irq(xa);
return err;
diff --git a/lib/xarray.c b/lib/xarray.c
index 5f3f9311de893a..569de54a1e151e 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1590,6 +1590,7 @@ EXPORT_SYMBOL(xa_store_range);
/**
* __xa_alloc() - Find somewhere to store this entry in the XArray.
* @xa: XArray.
+ * @cyclic_next: Storage to compute a cyclic ID
* @id: Pointer to ID.
* @max: Maximum ID to allocate (inclusive).
* @entry: New entry.
@@ -1599,12 +1600,16 @@ EXPORT_SYMBOL(xa_store_range);
* Updates the @id pointer with the index, then stores the entry at that
* index. A concurrent lookup will not see an uninitialised @id.
*
+ * If @cyclic_next is set then the returned value will try to start after this
+ * value, but the range will still be bounded by @id and @max as normal.
+ *
* 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)
+int __xa_alloc(struct xarray *xa, u32 *cyclic_next, u32 *id, u32 max,
+ void *entry, gfp_t gfp)
{
XA_STATE(xas, xa, 0);
int err;
@@ -1618,17 +1623,30 @@ int __xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, gfp_t gfp)
entry = XA_ZERO_ENTRY;
do {
- xas.xa_index = *id;
+ if (cyclic_next)
+ xas.xa_index = max(min(*id, *cyclic_next), max);
+ else
+ xas.xa_index = *id;
xas_find_marked(&xas, max, XA_FREE_MARK);
- if (xas.xa_node == XAS_RESTART)
+ if (xas.xa_node == XAS_RESTART) {
+ if (cyclic_next && *id != *cyclic_next) {
+ *cyclic_next = *id;
+ continue;
+ }
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)
+ if (!err) {
+ if (xas.xa_index == max)
+ *cyclic_next = *id;
+ else
+ *cyclic_next = xas.xa_index + 1;
*id = xas.xa_index;
+ }
return err;
}
EXPORT_SYMBOL(__xa_alloc);
