[PATCH 06/32] infiniband/core: Convert uverbs to XArray

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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




[Index of Archives]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Photo]     [Yosemite News]     [Yosemite Photos]     [Linux Kernel]     [Linux SCSI]     [XFree86]

  Powered by Linux