Use a direct xa_load lookup instead of hyperoptimising the lookup.
No locking changes.
Signed-off-by: Matthew Wilcox <willy@xxxxxxxxxxxxx>
---
drivers/infiniband/core/rdma_core.h | 8 +-
drivers/infiniband/core/uverbs_ioctl.c | 67 +++------
drivers/infiniband/core/uverbs_uapi.c | 191 ++++++++++++-------------
3 files changed, 109 insertions(+), 157 deletions(-)
diff --git a/drivers/infiniband/core/rdma_core.h b/drivers/infiniband/core/rdma_core.h
index 69f8db66925e..df3c6b5cbbdc 100644
--- a/drivers/infiniband/core/rdma_core.h
+++ b/drivers/infiniband/core/rdma_core.h
@@ -117,7 +117,7 @@ void release_ufile_idr_uobject(struct ib_uverbs_file *ufile);
*/
/*
- * Depending on ID the slot pointer in the radix tree points at one of these
+ * Depending on ID the pointer in the xarray points at one of these
* structs.
*/
@@ -148,8 +148,8 @@ struct uverbs_api_attr {
};
struct uverbs_api {
- /* radix tree contains struct uverbs_api_* pointers */
- struct radix_tree_root radix;
+ /* xarray contains struct uverbs_api_* pointers */
+ struct xarray xa;
enum rdma_driver_id driver_id;
unsigned int num_write;
@@ -172,7 +172,7 @@ uapi_get_object(struct uverbs_api *uapi, u16 object_id)
if (object_id == UVERBS_IDR_ANY_OBJECT)
return ERR_PTR(-ENOMSG);
- res = radix_tree_lookup(&uapi->radix, uapi_key_obj(object_id));
+ res = xa_load(&uapi->xa, uapi_key_obj(object_id));
if (!res)
return ERR_PTR(-ENOENT);
diff --git a/drivers/infiniband/core/uverbs_ioctl.c b/drivers/infiniband/core/uverbs_ioctl.c
index 0ca04d224015..3c6994634e2b 100644
--- a/drivers/infiniband/core/uverbs_ioctl.c
+++ b/drivers/infiniband/core/uverbs_ioctl.c
@@ -47,10 +47,8 @@ struct bundle_priv {
size_t internal_avail;
size_t internal_used;
- struct radix_tree_root *radix;
+ struct xarray *xa;
const struct uverbs_api_ioctl_method *method_elm;
- void __rcu **radix_slots;
- unsigned long radix_slots_len;
u32 method_key;
struct ib_uverbs_attr __user *user_attrs;
@@ -354,32 +352,10 @@ static int uverbs_process_attr(struct bundle_priv *pbundle,
return 0;
}
-/*
- * We search the radix tree with the method prefix and now we want to fast
- * search the suffix bits to get a particular attribute pointer. It is not
- * totally clear to me if this breaks the radix tree encasulation or not, but
- * it uses the iter data to determine if the method iter points at the same
- * chunk that will store the attribute, if so it just derefs it directly. By
- * construction in most kernel configs the method and attrs will all fit in a
- * single radix chunk, so in most cases this will have no search. Other cases
- * this falls back to a full search.
- */
-static void __rcu **uapi_get_attr_for_method(struct bundle_priv *pbundle,
- u32 attr_key)
+static const struct uverbs_api_attr *uapi_get_attr_for_method(
+ struct bundle_priv *pbundle, u32 attr_key)
{
- void __rcu **slot;
-
- if (likely(attr_key < pbundle->radix_slots_len)) {
- void *entry;
-
- slot = pbundle->radix_slots + attr_key;
- entry = rcu_dereference_raw(*slot);
- if (likely(!radix_tree_is_internal_node(entry) && entry))
- return slot;
- }
-
- return radix_tree_lookup_slot(pbundle->radix,
- pbundle->method_key | attr_key);
+ return xa_load(pbundle->xa, pbundle->method_key | attr_key);
}
static int uverbs_set_attr(struct bundle_priv *pbundle,
@@ -388,11 +364,10 @@ static int uverbs_set_attr(struct bundle_priv *pbundle,
u32 attr_key = uapi_key_attr(uattr->attr_id);
u32 attr_bkey = uapi_bkey_attr(attr_key);
const struct uverbs_api_attr *attr;
- void __rcu **slot;
int ret;
- slot = uapi_get_attr_for_method(pbundle, attr_key);
- if (!slot) {
+ attr = uapi_get_attr_for_method(pbundle, attr_key);
+ if (!attr) {
/*
* Kernel does not support the attribute but user-space says it
* is mandatory
@@ -401,7 +376,6 @@ static int uverbs_set_attr(struct bundle_priv *pbundle,
return -EPROTONOSUPPORT;
return 0;
}
- attr = rcu_dereference_protected(*slot, true);
/* Reject duplicate attributes from user-space */
if (test_bit(attr_bkey, pbundle->bundle.attr_present))
@@ -520,17 +494,13 @@ static int bundle_destroy(struct bundle_priv *pbundle, bool commit)
i + 1)) < key_bitmap_len) {
struct uverbs_attr *attr = &pbundle->bundle.attrs[i];
const struct uverbs_api_attr *attr_uapi;
- void __rcu **slot;
int current_ret;
- slot = uapi_get_attr_for_method(
- pbundle,
- pbundle->method_key | uapi_bkey_to_key_attr(i));
- if (WARN_ON(!slot))
+ attr_uapi = uapi_get_attr_for_method(pbundle,
+ pbundle->method_key | uapi_bkey_to_key_attr(i));
+ if (WARN_ON(!attr_uapi))
continue;
- attr_uapi = rcu_dereference_protected(*slot, true);
-
if (attr_uapi->spec.type == UVERBS_ATTR_TYPE_IDRS_ARRAY) {
current_ret = uverbs_free_idrs_array(
attr_uapi, &attr->objs_arr_attr, commit);
@@ -555,23 +525,20 @@ static int ib_uverbs_cmd_verbs(struct ib_uverbs_file *ufile,
{
const struct uverbs_api_ioctl_method *method_elm;
struct uverbs_api *uapi = ufile->device->uapi;
- struct radix_tree_iter attrs_iter;
struct bundle_priv *pbundle;
struct bundle_priv onstack;
- void __rcu **slot;
+ u32 method_id;
int destroy_ret;
int ret;
if (unlikely(hdr->driver_id != uapi->driver_id))
return -EINVAL;
- slot = radix_tree_iter_lookup(
- &uapi->radix, &attrs_iter,
- uapi_key_obj(hdr->object_id) |
- uapi_key_ioctl_method(hdr->method_id));
- if (unlikely(!slot))
+ method_id = uapi_key_obj(hdr->object_id) |
+ uapi_key_ioctl_method(hdr->method_id);
+ method_elm = xa_load(&uapi->xa, method_id);
+ if (unlikely(!method_elm))
return -EPROTONOSUPPORT;
- method_elm = rcu_dereference_protected(*slot, true);
if (!method_elm->use_stack) {
pbundle = kmalloc(method_elm->bundle_size, GFP_KERNEL);
@@ -590,11 +557,9 @@ static int ib_uverbs_cmd_verbs(struct ib_uverbs_file *ufile,
/* Space for the pbundle->bundle.attrs flex array */
pbundle->method_elm = method_elm;
- pbundle->method_key = attrs_iter.index;
+ pbundle->method_key = method_id;
pbundle->bundle.ufile = ufile;
- pbundle->radix = &uapi->radix;
- pbundle->radix_slots = slot;
- pbundle->radix_slots_len = radix_tree_chunk_size(&attrs_iter);
+ pbundle->xa = &uapi->xa;
pbundle->user_attrs = user_attrs;
pbundle->internal_used = ALIGN(pbundle->method_elm->key_bitmap_len *
diff --git a/drivers/infiniband/core/uverbs_uapi.c b/drivers/infiniband/core/uverbs_uapi.c
index 9ae08e4b78a3..cd567c062d43 100644
--- a/drivers/infiniband/core/uverbs_uapi.c
+++ b/drivers/infiniband/core/uverbs_uapi.c
@@ -15,41 +15,46 @@ static int ib_uverbs_notsupp(struct uverbs_attr_bundle *attrs)
static void *uapi_add_elm(struct uverbs_api *uapi, u32 key, size_t alloc_size)
{
- void *elm;
- int rc;
+ void *elm, *curr;
if (key == UVERBS_API_KEY_ERR)
return ERR_PTR(-EOVERFLOW);
elm = kzalloc(alloc_size, GFP_KERNEL);
- rc = radix_tree_insert(&uapi->radix, key, elm);
- if (rc) {
- kfree(elm);
- return ERR_PTR(rc);
- }
-
- return elm;
+ if (!elm)
+ return ERR_PTR(-ENOMEM);
+ curr = xa_cmpxchg(&uapi->xa, key, NULL, elm, GFP_KERNEL);
+ if (!curr)
+ return elm;
+ kfree(elm);
+ if (curr == XA_ERROR(-ENOMEM))
+ return ERR_PTR(-ENOMEM);
+ return ERR_PTR(-EEXIST);
}
static void *uapi_add_get_elm(struct uverbs_api *uapi, u32 key,
size_t alloc_size, bool *exists)
{
- void *elm;
+ void *elm, *curr;
- elm = uapi_add_elm(uapi, key, alloc_size);
- if (!IS_ERR(elm)) {
+ if (key == UVERBS_API_KEY_ERR)
+ return ERR_PTR(-EOVERFLOW);
+
+ elm = kzalloc(alloc_size, GFP_KERNEL);
+ if (!elm)
+ return ERR_PTR(-ENOMEM);
+ curr = xa_cmpxchg(&uapi->xa, key, NULL, elm, GFP_KERNEL);
+ if (!curr) {
*exists = false;
return elm;
}
- if (elm != ERR_PTR(-EEXIST))
- return elm;
+ kfree(elm);
+ if (curr == XA_ERROR(-ENOMEM))
+ return ERR_PTR(-ENOMEM);
- elm = radix_tree_lookup(&uapi->radix, key);
- if (WARN_ON(!elm))
- return ERR_PTR(-EINVAL);
*exists = true;
- return elm;
+ return curr;
}
static int uapi_create_write(struct uverbs_api *uapi,
@@ -349,22 +354,19 @@ uapi_finalize_ioctl_method(struct uverbs_api *uapi,
struct uverbs_api_ioctl_method *method_elm,
u32 method_key)
{
- struct radix_tree_iter iter;
+ XA_STATE(xas, &uapi->xa, uapi_key_attrs_start(method_key));
+ struct uverbs_api_attr *elm;
unsigned int num_attrs = 0;
unsigned int max_bkey = 0;
bool single_uobj = false;
- void __rcu **slot;
method_elm->destroy_bkey = UVERBS_API_ATTR_BKEY_LEN;
- radix_tree_for_each_slot (slot, &uapi->radix, &iter,
- uapi_key_attrs_start(method_key)) {
- struct uverbs_api_attr *elm =
- rcu_dereference_protected(*slot, true);
- u32 attr_key = iter.index & UVERBS_API_ATTR_KEY_MASK;
+ xas_for_each(&xas, elm, ULONG_MAX) {
+ u32 attr_key = xas.xa_index & UVERBS_API_ATTR_KEY_MASK;
u32 attr_bkey = uapi_bkey_attr(attr_key);
u8 type = elm->spec.type;
- if (uapi_key_attr_to_ioctl_method(iter.index) !=
+ if (uapi_key_attr_to_ioctl_method(xas.xa_index) !=
uapi_key_attr_to_ioctl_method(method_key))
break;
@@ -413,29 +415,26 @@ static int uapi_finalize(struct uverbs_api *uapi)
const struct uverbs_api_write_method **data;
unsigned long max_write_ex = 0;
unsigned long max_write = 0;
- struct radix_tree_iter iter;
- void __rcu **slot;
+ XA_STATE(xas, &uapi->xa, 0);
+ struct uverbs_api_ioctl_method *method_elm;
int rc;
int i;
- radix_tree_for_each_slot (slot, &uapi->radix, &iter, 0) {
- struct uverbs_api_ioctl_method *method_elm =
- rcu_dereference_protected(*slot, true);
-
- if (uapi_key_is_ioctl_method(iter.index)) {
+ xas_for_each(&xas, method_elm, ULONG_MAX) {
+ if (uapi_key_is_ioctl_method(xas.xa_index)) {
rc = uapi_finalize_ioctl_method(uapi, method_elm,
- iter.index);
+ xas.xa_index);
if (rc)
return rc;
}
- if (uapi_key_is_write_method(iter.index))
- max_write = max(max_write,
- iter.index & UVERBS_API_ATTR_KEY_MASK);
- if (uapi_key_is_write_ex_method(iter.index))
+ if (uapi_key_is_write_method(xas.xa_index))
+ max_write = max(max_write, xas.xa_index &
+ UVERBS_API_ATTR_KEY_MASK);
+ if (uapi_key_is_write_ex_method(xas.xa_index))
max_write_ex =
- max(max_write_ex,
- iter.index & UVERBS_API_ATTR_KEY_MASK);
+ max(max_write_ex, xas.xa_index &
+ UVERBS_API_ATTR_KEY_MASK);
}
uapi->notsupp_method.handler = ib_uverbs_notsupp;
@@ -448,15 +447,16 @@ static int uapi_finalize(struct uverbs_api *uapi)
uapi->write_methods = data;
uapi->write_ex_methods = data + uapi->num_write;
- radix_tree_for_each_slot (slot, &uapi->radix, &iter, 0) {
- if (uapi_key_is_write_method(iter.index))
- uapi->write_methods[iter.index &
+ xas_set(&xas, 0);
+ xas_for_each(&xas, method_elm, ULONG_MAX) {
+ if (uapi_key_is_write_method(xas.xa_index))
+ uapi->write_methods[xas.xa_index &
UVERBS_API_ATTR_KEY_MASK] =
- rcu_dereference_protected(*slot, true);
- if (uapi_key_is_write_ex_method(iter.index))
- uapi->write_ex_methods[iter.index &
+ (const void *)method_elm;
+ if (uapi_key_is_write_ex_method(xas.xa_index))
+ uapi->write_ex_methods[xas.xa_index &
UVERBS_API_ATTR_KEY_MASK] =
- rcu_dereference_protected(*slot, true);
+ (const void *)method_elm;
}
return 0;
@@ -464,14 +464,12 @@ static int uapi_finalize(struct uverbs_api *uapi)
static void uapi_remove_range(struct uverbs_api *uapi, u32 start, u32 last)
{
- struct radix_tree_iter iter;
- void __rcu **slot;
-
- radix_tree_for_each_slot (slot, &uapi->radix, &iter, start) {
- if (iter.index > last)
- return;
- kfree(rcu_dereference_protected(*slot, true));
- radix_tree_iter_delete(&uapi->radix, &iter, slot);
+ XA_STATE(xas, &uapi->xa, start);
+ void *entry;
+
+ xas_for_each(&xas, entry, last) {
+ kfree(entry);
+ xas_store(&xas, NULL);
}
}
@@ -518,56 +516,50 @@ static void uapi_key_okay(u32 key)
static void uapi_finalize_disable(struct uverbs_api *uapi)
{
- struct radix_tree_iter iter;
+ XA_STATE(xas, &uapi->xa, 0);
u32 starting_key = 0;
bool scan_again = false;
- void __rcu **slot;
+ void *entry;
again:
- radix_tree_for_each_slot (slot, &uapi->radix, &iter, starting_key) {
- uapi_key_okay(iter.index);
+ xas_for_each(&xas, entry, ULONG_MAX) {
+ uapi_key_okay(xas.xa_index);
- if (uapi_key_is_object(iter.index)) {
- struct uverbs_api_object *obj_elm =
- rcu_dereference_protected(*slot, true);
+ if (uapi_key_is_object(xas.xa_index)) {
+ struct uverbs_api_object *obj_elm = entry;
if (obj_elm->disabled) {
/* Have to check all the attrs again */
scan_again = true;
- starting_key = iter.index;
- uapi_remove_object(uapi, iter.index);
- goto again;
+ starting_key = xas.xa_index;
+ uapi_remove_object(uapi, xas.xa_index);
}
continue;
}
- if (uapi_key_is_ioctl_method(iter.index)) {
- struct uverbs_api_ioctl_method *method_elm =
- rcu_dereference_protected(*slot, true);
+ if (uapi_key_is_ioctl_method(xas.xa_index)) {
+ struct uverbs_api_ioctl_method *method_elm = entry;
if (method_elm->disabled) {
- starting_key = iter.index;
- uapi_remove_method(uapi, iter.index);
- goto again;
+ starting_key = xas.xa_index;
+ uapi_remove_method(uapi, xas.xa_index);
}
continue;
}
- if (uapi_key_is_write_method(iter.index) ||
- uapi_key_is_write_ex_method(iter.index)) {
- struct uverbs_api_write_method *method_elm =
- rcu_dereference_protected(*slot, true);
+ if (uapi_key_is_write_method(xas.xa_index) ||
+ uapi_key_is_write_ex_method(xas.xa_index)) {
+ struct uverbs_api_write_method *method_elm = entry;
if (method_elm->disabled) {
kfree(method_elm);
- radix_tree_iter_delete(&uapi->radix, &iter, slot);
+ xas_store(&xas, NULL);
}
continue;
}
- if (uapi_key_is_attr(iter.index)) {
- struct uverbs_api_attr *attr_elm =
- rcu_dereference_protected(*slot, true);
+ if (uapi_key_is_attr(xas.xa_index)) {
+ struct uverbs_api_attr *attr_elm = entry;
const struct uverbs_api_object *tmp_obj;
u32 obj_key;
@@ -590,19 +582,19 @@ static void uapi_finalize_disable(struct uverbs_api *uapi)
continue;
}
- starting_key = iter.index;
- uapi_remove_method(
- uapi,
- iter.index & (UVERBS_API_OBJ_KEY_MASK |
+ starting_key = xas.xa_index;
+ uapi_remove_method(uapi,
+ xas.xa_index & (UVERBS_API_OBJ_KEY_MASK |
UVERBS_API_METHOD_KEY_MASK));
- goto again;
+ continue;
}
- WARN_ON(false);
+ WARN_ON(true);
}
if (!scan_again)
return;
+ xas_set(&xas, starting_key);
scan_again = false;
starting_key = 0;
goto again;
@@ -639,7 +631,7 @@ struct uverbs_api *uverbs_alloc_api(struct ib_device *ibdev)
if (!uapi)
return ERR_PTR(-ENOMEM);
- INIT_RADIX_TREE(&uapi->radix, GFP_KERNEL);
+ xa_init(&uapi->xa);
uapi->driver_id = ibdev->driver_id;
rc = uapi_merge_def(uapi, ibdev, uverbs_core_api, false);
@@ -673,16 +665,13 @@ struct uverbs_api *uverbs_alloc_api(struct ib_device *ibdev)
void uverbs_disassociate_api_pre(struct ib_uverbs_device *uverbs_dev)
{
struct uverbs_api *uapi = uverbs_dev->uapi;
- struct radix_tree_iter iter;
- void __rcu **slot;
+ XA_STATE(xas, &uapi->xa, 0);
+ struct uverbs_api_ioctl_method *method_elm;
rcu_assign_pointer(uverbs_dev->ib_dev, NULL);
- radix_tree_for_each_slot (slot, &uapi->radix, &iter, 0) {
- if (uapi_key_is_ioctl_method(iter.index)) {
- struct uverbs_api_ioctl_method *method_elm =
- rcu_dereference_protected(*slot, true);
-
+ xas_for_each(&xas, method_elm, ULONG_MAX) {
+ if (uapi_key_is_ioctl_method(xas.xa_index)) {
if (method_elm->driver_method)
rcu_assign_pointer(method_elm->handler, NULL);
}
@@ -698,13 +687,12 @@ void uverbs_disassociate_api_pre(struct ib_uverbs_device *uverbs_dev)
*/
void uverbs_disassociate_api(struct uverbs_api *uapi)
{
- struct radix_tree_iter iter;
- void __rcu **slot;
+ XA_STATE(xas, &uapi->xa, 0);
+ void *entry;
- radix_tree_for_each_slot (slot, &uapi->radix, &iter, 0) {
- if (uapi_key_is_object(iter.index)) {
- struct uverbs_api_object *object_elm =
- rcu_dereference_protected(*slot, true);
+ xas_for_each(&xas, entry, ULONG_MAX) {
+ if (uapi_key_is_object(xas.xa_index)) {
+ struct uverbs_api_object *object_elm = entry;
/*
* Some type_attrs are in the driver module. We don't
@@ -712,9 +700,8 @@ void uverbs_disassociate_api(struct uverbs_api *uapi)
* no use of this after disassociate.
*/
object_elm->type_attrs = NULL;
- } else if (uapi_key_is_attr(iter.index)) {
- struct uverbs_api_attr *elm =
- rcu_dereference_protected(*slot, true);
+ } else if (uapi_key_is_attr(xas.xa_index)) {
+ struct uverbs_api_attr *elm = entry;
if (elm->spec.type == UVERBS_ATTR_TYPE_ENUM_IN)
elm->spec.u2.enum_def.ids = NULL;
--
2.20.1
