From patchwork Thu Dec 8 12:38:28 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jarkko Sakkinen X-Patchwork-Id: 9466339 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 0E1A06071E for ; Thu, 8 Dec 2016 12:39:00 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 02031284EC for ; Thu, 8 Dec 2016 12:39:00 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id EB11428526; Thu, 8 Dec 2016 12:38:59 +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 671C7284EC for ; Thu, 8 Dec 2016 12:38:59 +0000 (UTC) Received: from [127.0.0.1] (localhost [IPv6:::1]) by ml01.01.org (Postfix) with ESMTP id 78B5F81F5B for ; Thu, 8 Dec 2016 04:38:59 -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 27FD581F5B for ; Thu, 8 Dec 2016 04:38:58 -0800 (PST) Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga105.jf.intel.com with ESMTP; 08 Dec 2016 04:38:57 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.33,319,1477983600"; d="scan'208";a="200415138" Received: from jsakkine-mobl1.tm.intel.com (HELO localhost) ([10.237.50.66]) by fmsmga004.fm.intel.com with ESMTP; 08 Dec 2016 04:38:56 -0800 From: Jarkko Sakkinen To: intel-sgx-kernel-dev@lists.01.org Date: Thu, 8 Dec 2016 14:38:28 +0200 Message-Id: <20161208123828.21834-11-jarkko.sakkinen@linux.intel.com> X-Mailer: git-send-email 2.9.3 In-Reply-To: <20161208123828.21834-1-jarkko.sakkinen@linux.intel.com> References: <20161208123828.21834-1-jarkko.sakkinen@linux.intel.com> Subject: [intel-sgx-kernel-dev] [PATCH v8 10/10] 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 --- drivers/platform/x86/intel_sgx.h | 12 +++---- drivers/platform/x86/intel_sgx_ioctl.c | 42 +++++++----------------- drivers/platform/x86/intel_sgx_util.c | 60 ++++++++-------------------------- drivers/platform/x86/intel_sgx_vma.c | 2 +- 4 files changed, 32 insertions(+), 84 deletions(-) diff --git a/drivers/platform/x86/intel_sgx.h b/drivers/platform/x86/intel_sgx.h index c8b65fe..c7047c5 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 @@ -111,11 +112,11 @@ struct sgx_encl_page { unsigned long addr; unsigned int flags; struct sgx_epc_page *epc_page; - struct list_head load_list; struct sgx_va_page *va_page; unsigned int va_offset; struct sgx_pcmd pcmd; - struct rb_node node; + struct list_head page_list; + struct list_head load_list; }; struct sgx_tgid_ctx { @@ -141,12 +142,13 @@ struct sgx_encl { struct task_struct *owner; struct mm_struct *mm; struct file *backing; + struct list_head page_list; + struct radix_tree_root page_tree; struct list_head load_list; struct kref refcount; unsigned long base; unsigned long size; struct list_head va_pages; - struct rb_root encl_rb; struct list_head add_page_reqs; struct work_struct add_page_work; struct sgx_encl_page secs_page; @@ -204,15 +206,11 @@ void sgx_insert_pte(struct sgx_encl *encl, struct vm_area_struct *vma); int sgx_eremove(struct sgx_epc_page *epc_page); 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); bool sgx_pin_mm(struct sgx_encl *encl); 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..ab31ba6 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,8 @@ 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_LIST_HEAD(&encl->page_list); + 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 +688,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 +705,14 @@ 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); @@ -758,8 +741,7 @@ out: 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); + list_add_tail(&encl_page->page_list, &encl->page_list); } mutex_unlock(&encl->lock); diff --git a/drivers/platform/x86/intel_sgx_util.c b/drivers/platform/x86/intel_sgx_util.c index f6f7dde0..758e1ec 100644 --- a/drivers/platform/x86/intel_sgx_util.c +++ b/drivers/platform/x86/intel_sgx_util.c @@ -117,22 +117,6 @@ struct vm_area_struct *sgx_find_vma(struct sgx_encl *encl, unsigned long addr) return NULL; } -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) && - entry->addr >= vma->vm_start && - entry->addr < vma->vm_end) - zap_vma_ptes(vma, entry->addr, PAGE_SIZE); - } -} - bool sgx_pin_mm(struct sgx_encl *encl) { mutex_lock(&encl->lock); @@ -163,15 +147,21 @@ void sgx_unpin_mm(struct sgx_encl *encl) void sgx_invalidate(struct sgx_encl *encl) { struct vm_area_struct *vma; + struct sgx_encl_page *entry; unsigned long addr; for (addr = encl->base; addr < (encl->base + encl->size); addr = vma->vm_end) { vma = sgx_find_vma(encl, addr); - if (vma) - sgx_zap_tcs_ptes(encl, vma); - else + if (!vma) break; + + 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); + } } encl->flags |= SGX_ENCL_DEAD; @@ -203,30 +193,10 @@ 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_encl_page *entry_tmp; struct sgx_va_page *va_page; struct sgx_encl *encl = container_of(ref, struct sgx_encl, refcount); @@ -241,17 +211,15 @@ void sgx_encl_release(struct kref *ref) 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); + list_for_each_entry_safe(entry, entry_tmp, &encl->page_list, + page_list) { 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 5520080..a9ea67f 100644 --- a/drivers/platform/x86/intel_sgx_vma.c +++ b/drivers/platform/x86/intel_sgx_vma.c @@ -171,7 +171,7 @@ 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); + entry = radix_tree_lookup(&encl->page_tree, addr >> PAGE_SHIFT); if (!entry) return ERR_PTR(-EFAULT);