From patchwork Thu Dec 15 20:58:48 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jarkko Sakkinen X-Patchwork-Id: 9476965 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id B1FB660571 for ; Thu, 15 Dec 2016 20:59:24 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 94FFC28816 for ; Thu, 15 Dec 2016 20:59:24 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 75A6428843; Thu, 15 Dec 2016 20:59:24 +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=-1.9 required=2.0 tests=BAYES_00, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 Received: from ml01.01.org (ml01.01.org [198.145.21.10]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id C315F28816 for ; Thu, 15 Dec 2016 20:59:23 +0000 (UTC) Received: from [127.0.0.1] (localhost [IPv6:::1]) by ml01.01.org (Postfix) with ESMTP id B2A6781FD1 for ; Thu, 15 Dec 2016 12:59:23 -0800 (PST) X-Original-To: intel-sgx-kernel-dev@lists.01.org Delivered-To: intel-sgx-kernel-dev@lists.01.org Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id B04A081FD1 for ; Thu, 15 Dec 2016 12:59:22 -0800 (PST) Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by orsmga105.jf.intel.com with ESMTP; 15 Dec 2016 12:59:22 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos; i="5.33,354,1477983600"; d="scan'208"; a="1099716409" Received: from unknown (HELO localhost) ([10.249.37.126]) by fmsmga002.fm.intel.com with ESMTP; 15 Dec 2016 12:59:20 -0800 From: Jarkko Sakkinen To: intel-sgx-kernel-dev@lists.01.org Date: Thu, 15 Dec 2016 22:58:48 +0200 Message-Id: <20161215205848.26207-1-jarkko.sakkinen@linux.intel.com> X-Mailer: git-send-email 2.9.3 Subject: [intel-sgx-kernel-dev] [PATCH v9 RESEND] intel_sgx: migrate to radix tree for addressing enclave pages X-BeenThere: intel-sgx-kernel-dev@lists.01.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Project: Intel® Software Guard Extensions for Linux*: https://01.org/intel-software-guard-extensions" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: intel-sgx-kernel-dev-bounces@lists.01.org Sender: "intel-sgx-kernel-dev" X-Virus-Scanned: ClamAV using ClamSMTP Radix tree is the fastest data structure for addressing so it does make sense to replace RB tree with a Radix tree. Signed-off-by: Jarkko Sakkinen --- Ugh, copule of fixes to sgx_vma_do_fault were not squashed :( Sorry. Here's a fixed version. drivers/platform/x86/intel_sgx.h | 6 ++--- drivers/platform/x86/intel_sgx_ioctl.c | 40 +++++++------------------------ drivers/platform/x86/intel_sgx_util.c | 44 +++++++--------------------------- drivers/platform/x86/intel_sgx_vma.c | 20 +++++++++------- 4 files changed, 31 insertions(+), 79 deletions(-) diff --git a/drivers/platform/x86/intel_sgx.h b/drivers/platform/x86/intel_sgx.h index c8b65fe..ed9e8e6 100644 --- a/drivers/platform/x86/intel_sgx.h +++ b/drivers/platform/x86/intel_sgx.h @@ -68,6 +68,7 @@ #include #include #include +#include #define SGX_EINIT_SPIN_COUNT 20 #define SGX_EINIT_SLEEP_COUNT 50 @@ -115,7 +116,6 @@ struct sgx_encl_page { struct sgx_va_page *va_page; unsigned int va_offset; struct sgx_pcmd pcmd; - struct rb_node node; }; struct sgx_tgid_ctx { @@ -146,7 +146,7 @@ struct sgx_encl { unsigned long base; unsigned long size; struct list_head va_pages; - struct rb_root encl_rb; + struct radix_tree_root page_tree; struct list_head add_page_reqs; struct work_struct add_page_work; struct sgx_encl_page secs_page; @@ -211,8 +211,6 @@ void sgx_unpin_mm(struct sgx_encl *encl); void sgx_invalidate(struct sgx_encl *encl); int sgx_find_encl(struct mm_struct *mm, unsigned long addr, struct vm_area_struct **vma); -struct sgx_encl_page *sgx_encl_find_page(struct sgx_encl *encl, - unsigned long addr); void sgx_encl_release(struct kref *ref); void sgx_tgid_ctx_release(struct kref *ref); diff --git a/drivers/platform/x86/intel_sgx_ioctl.c b/drivers/platform/x86/intel_sgx_ioctl.c index 8543373..3a4a8fa 100644 --- a/drivers/platform/x86/intel_sgx_ioctl.c +++ b/drivers/platform/x86/intel_sgx_ioctl.c @@ -138,33 +138,6 @@ void sgx_tgid_ctx_release(struct kref *ref) kfree(pe); } -static int encl_rb_insert(struct rb_root *root, - struct sgx_encl_page *data) -{ - struct rb_node **new = &root->rb_node; - struct rb_node *parent = NULL; - - /* Figure out where to put new node */ - while (*new) { - struct sgx_encl_page *this = - container_of(*new, struct sgx_encl_page, node); - - parent = *new; - if (data->addr < this->addr) - new = &((*new)->rb_left); - else if (data->addr > this->addr) - new = &((*new)->rb_right); - else - return -EFAULT; - } - - /* Add new node and rebalance tree. */ - rb_link_node(&data->node, parent, new); - rb_insert_color(&data->node, root); - - return 0; -} - static int sgx_find_and_get_encl(unsigned long addr, struct sgx_encl **encl) { struct mm_struct *mm = current->mm; @@ -538,6 +511,7 @@ static long sgx_ioc_enclave_create(struct file *filep, unsigned int cmd, kref_init(&encl->refcount); INIT_LIST_HEAD(&encl->add_page_reqs); INIT_LIST_HEAD(&encl->va_pages); + INIT_RADIX_TREE(&encl->page_tree, GFP_KERNEL); INIT_LIST_HEAD(&encl->load_list); INIT_LIST_HEAD(&encl->encl_list); mutex_init(&encl->lock); @@ -713,7 +687,7 @@ static int __encl_add_page(struct sgx_encl *encl, goto out; } - if (sgx_encl_find_page(encl, addp->addr)) { + if (radix_tree_lookup(&encl->page_tree, addp->addr >> PAGE_SHIFT)) { ret = -EEXIST; goto out; } @@ -730,6 +704,13 @@ static int __encl_add_page(struct sgx_encl *encl, goto out; } + ret = radix_tree_insert(&encl->page_tree, encl_page->addr >> PAGE_SHIFT, + encl_page); + if (ret) { + sgx_put_backing(backing, false /* write */); + goto out; + } + user_vaddr = kmap(backing); tmp_vaddr = kmap(tmp_page); memcpy(user_vaddr, tmp_vaddr, PAGE_SIZE); @@ -757,9 +738,6 @@ static int __encl_add_page(struct sgx_encl *encl, kfree(req); sgx_free_va_slot(encl_page->va_page, encl_page->va_offset); - } else { - ret = encl_rb_insert(&encl->encl_rb, encl_page); - WARN_ON(ret); } mutex_unlock(&encl->lock); diff --git a/drivers/platform/x86/intel_sgx_util.c b/drivers/platform/x86/intel_sgx_util.c index f6f7dde0..2c390c5 100644 --- a/drivers/platform/x86/intel_sgx_util.c +++ b/drivers/platform/x86/intel_sgx_util.c @@ -120,13 +120,9 @@ struct vm_area_struct *sgx_find_vma(struct sgx_encl *encl, unsigned long addr) void sgx_zap_tcs_ptes(struct sgx_encl *encl, struct vm_area_struct *vma) { struct sgx_encl_page *entry; - struct rb_node *rb; - rb = rb_first(&encl->encl_rb); - while (rb) { - entry = container_of(rb, struct sgx_encl_page, node); - rb = rb_next(rb); - if (entry->epc_page && (entry->flags & SGX_ENCL_PAGE_TCS) && + list_for_each_entry(entry, &encl->load_list, load_list) { + if ((entry->flags & SGX_ENCL_PAGE_TCS) && entry->addr >= vma->vm_start && entry->addr < vma->vm_end) zap_vma_ptes(vma, entry->addr, PAGE_SIZE); @@ -203,55 +199,31 @@ int sgx_find_encl(struct mm_struct *mm, unsigned long addr, return 0; } -struct sgx_encl_page *sgx_encl_find_page(struct sgx_encl *encl, - unsigned long addr) -{ - struct rb_node *node = encl->encl_rb.rb_node; - - while (node) { - struct sgx_encl_page *data = - container_of(node, struct sgx_encl_page, node); - - if (data->addr > addr) - node = node->rb_left; - else if (data->addr < addr) - node = node->rb_right; - else - return data; - } - - return NULL; -} - void sgx_encl_release(struct kref *ref) { - struct rb_node *rb1, *rb2; struct sgx_encl_page *entry; struct sgx_va_page *va_page; - struct sgx_encl *encl = - container_of(ref, struct sgx_encl, refcount); + struct sgx_encl *encl = container_of(ref, struct sgx_encl, refcount); + struct radix_tree_iter iter; + void **slot; mutex_lock(&sgx_tgid_ctx_mutex); if (!list_empty(&encl->encl_list)) list_del(&encl->encl_list); - mutex_unlock(&sgx_tgid_ctx_mutex); if (encl->mmu_notifier.ops) mmu_notifier_unregister_no_release(&encl->mmu_notifier, encl->mm); - rb1 = rb_first(&encl->encl_rb); - while (rb1) { - entry = container_of(rb1, struct sgx_encl_page, node); - rb2 = rb_next(rb1); - rb_erase(rb1, &encl->encl_rb); + radix_tree_for_each_slot(slot, &encl->page_tree, &iter, 0) { + entry = *slot; if (entry->epc_page) { list_del(&entry->load_list); sgx_free_page(entry->epc_page, encl, 0); } + radix_tree_delete(&encl->page_tree, entry->addr >> PAGE_SHIFT); kfree(entry); - rb1 = rb2; } while (!list_empty(&encl->va_pages)) { diff --git a/drivers/platform/x86/intel_sgx_vma.c b/drivers/platform/x86/intel_sgx_vma.c index d588932..1ff55c1 100644 --- a/drivers/platform/x86/intel_sgx_vma.c +++ b/drivers/platform/x86/intel_sgx_vma.c @@ -169,16 +169,20 @@ static struct sgx_encl_page *sgx_vma_do_fault(struct vm_area_struct *vma, if (!encl) return ERR_PTR(-EFAULT); - entry = sgx_encl_find_page(encl, addr); - if (!entry) - return ERR_PTR(-EFAULT); + mutex_lock(&encl->lock); - epc_page = sgx_alloc_page(encl->tgid_ctx, SGX_ALLOC_ATOMIC); - if (IS_ERR(epc_page)) - /* reinterpret the type as we return an error */ - return (struct sgx_encl_page *)epc_page; + entry = radix_tree_lookup(&encl->page_tree, addr >> PAGE_SHIFT); + if (!entry) { + entry = ERR_PTR(-EFAULT); + goto out; + } - mutex_lock(&encl->lock); + epc_page = sgx_alloc_page(encl->tgid_ctx, SGX_ALLOC_ATOMIC); + if (IS_ERR(epc_page)) { + entry = (struct sgx_encl_page *)epc_page; + epc_page = NULL; + goto out; + } if (encl->flags & SGX_ENCL_DEAD) { entry = ERR_PTR(-EFAULT);