| Message ID | 20161208123828.21834-11-jarkko.sakkinen@linux.intel.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, Dec 08, 2016 at 02:38:28PM +0200, Jarkko Sakkinen wrote: > 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 <jarkko.sakkinen@linux.intel.com> I could probably update this patch by not adding 'page_list' but instead traversing with radix_tree_for_each_slot and deleting entries with radix_tree_delete. I did more "conservative" implementation here because I wasn't first sure whether you can call radix_tree_delete while iterating the radix tree. In mm/backing-dev.c this is done so it probably is fine: http://lxr.free-electrons.com/source/mm/backing-dev.c#L719 This is a great thing because it will save 16 bytes for each enclave page. /Jarkko > --- > 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 <linux/sched.h> > #include <linux/workqueue.h> > #include <linux/mmu_notifier.h> > +#include <linux/radix-tree.h> > > #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); > > -- > 2.9.3 >
Jarkko Sakkinen <jarkko.sakkinen@linux.intel.com> wrote: > On Thu, Dec 08, 2016 at 02:38:28PM +0200, Jarkko Sakkinen wrote: > > 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 <jarkko.sakkinen@linux.intel.com> > > I could probably update this patch by not adding 'page_list' but instead > traversing with radix_tree_for_each_slot and deleting entries with > radix_tree_delete. I did more "conservative" implementation here because > I wasn't first sure whether you can call radix_tree_delete while > iterating the radix tree. > > In mm/backing-dev.c this is done so it probably is fine: > > http://lxr.free-electrons.com/source/mm/backing-dev.c#L719 > > This is a great thing because it will save 16 bytes for each enclave page. I tested this approach and didn't see any problems. Code snippet I used in sgx_encl_release: void **slot; struct radix_tree_iter iter; 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); }
On Wed, Dec 14, 2016 at 09:49:00PM +0000, Christopherson, Sean J wrote: > Jarkko Sakkinen <jarkko.sakkinen@linux.intel.com> wrote: > > On Thu, Dec 08, 2016 at 02:38:28PM +0200, Jarkko Sakkinen wrote: > > > 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 <jarkko.sakkinen@linux.intel.com> > > > > I could probably update this patch by not adding 'page_list' but instead > > traversing with radix_tree_for_each_slot and deleting entries with > > radix_tree_delete. I did more "conservative" implementation here because > > I wasn't first sure whether you can call radix_tree_delete while > > iterating the radix tree. > > > > In mm/backing-dev.c this is done so it probably is fine: > > > > http://lxr.free-electrons.com/source/mm/backing-dev.c#L719 > > > > This is a great thing because it will save 16 bytes for each enclave page. > > I tested this approach and didn't see any problems. Code snippet I used in sgx_encl_release: Well there are no too many ways to implement the below. /Jarkko > void **slot; > struct radix_tree_iter iter; > > 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); > }
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 <linux/sched.h> #include <linux/workqueue.h> #include <linux/mmu_notifier.h> +#include <linux/radix-tree.h> #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);
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 <jarkko.sakkinen@linux.intel.com> --- 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(-)