From patchwork Thu Feb 21 00:20:41 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10822949 X-Patchwork-Delegate: jgg@ziepe.ca Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4750213A4 for ; Thu, 21 Feb 2019 00:21:27 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2EEBC2FC7C for ; Thu, 21 Feb 2019 00:21:27 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2032F2FC84; Thu, 21 Feb 2019 00:21:27 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.7 required=2.0 tests=BAYES_00,DKIM_INVALID, DKIM_SIGNED,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0E56D2FC7C for ; Thu, 21 Feb 2019 00:21:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726655AbfBUAVZ (ORCPT ); Wed, 20 Feb 2019 19:21:25 -0500 Received: from bombadil.infradead.org ([198.137.202.133]:52410 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726352AbfBUAVK (ORCPT ); Wed, 20 Feb 2019 19:21:10 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=References:In-Reply-To:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=Q/VQiNkTY/gtzJy/aQdp6uEh343UVCO28/j17Z8HsiI=; b=i7k7TYaMKi1qj7FGkHfDtzMF4 rGGvlbYTo2rV0aQuaSFsrTgzv9R5uunBos4q/nCGXLuDLFU4f3wjSKJUjYOUY1ASuj8Evl3/Lbm8q O1eSQ2VVp8F0YQc8zykbQeikQ1vi4HKbw9eYqM/+2YWF+1oz770Dldw/usHC/3LBBwQo/QnEfM+Bw bsmKp6bzBhHgOqJEMMO6CS6EjDJdYcOXsUuhjk7yvzCF/pscX5pZJmJmBtyZ9sjP0NISt2JmeEDn8 Fae2Vyjx+148zngEhZlPCX1oVbu7VnplfQpiZylAkyWzFju+V96c4fEHkkzo4t3mlJif+TfWN+CSm jvJA291PA==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1gwc6w-0005ub-Ar; Thu, 21 Feb 2019 00:21:10 +0000 From: Matthew Wilcox To: Jason Gunthorpe Cc: Matthew Wilcox , linux-rdma@vger.kernel.org Subject: [PATCH 06/32] infiniband/core: Convert uverbs to XArray Date: Wed, 20 Feb 2019 16:20:41 -0800 Message-Id: <20190221002107.22625-7-willy@infradead.org> X-Mailer: git-send-email 2.14.5 In-Reply-To: <20190221002107.22625-1-willy@infradead.org> References: <20190221002107.22625-1-willy@infradead.org> Sender: linux-rdma-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Use a direct xa_load lookup instead of hyperoptimising the lookup. No locking changes. Signed-off-by: Matthew Wilcox --- 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;