Messages in this thread Patch in this message | | | From | "Aneesh Kumar K.V" <> | Subject | Re: [PATCH 1/2] [RFC] Range tree implementation | Date | Tue, 20 Mar 2012 22:14:51 +0530 |
| |
John Stultz <john.stultz@linaro.org> writes:
....
> +/** > + * range_tree_in_range - Returns the first node that overlaps with the > + * given range > + * @root: range_tree root > + * @start: range start > + * @end: range end > + * > + */ > +struct range_tree_node *range_tree_in_range(struct range_tree_root *root, > + u64 start, u64 end) > +{ > + struct rb_node **p = &root->head.rb_node; > + struct range_tree_node *candidate; > + > + while (*p) { > + candidate = rb_entry(*p, struct range_tree_node, rb); > + if (end < candidate->start) > + p = &(*p)->rb_left; > + else if (start > candidate->end) > + p = &(*p)->rb_right; > + else > + return candidate; > + } > + > + return 0;
return NULL ?
> +} > + > + > +/** > + * range_tree_in_range - Returns the first node that overlaps or is adjacent > + * with the given range > + * @root: range_tree root > + * @start: range start > + * @end: range end > + * > + */
The comment needs update
> +struct range_tree_node *range_tree_in_range_adjacent( > + struct range_tree_root *root, > + u64 start, u64 end) > +{ > + struct rb_node **p = &root->head.rb_node; > + struct range_tree_node *candidate; > + > + while (*p) { > + candidate = rb_entry(*p, struct range_tree_node, rb); > + if (end+1 < candidate->start) > + p = &(*p)->rb_left; > + else if (start > candidate->end + 1) > + p = &(*p)->rb_right; > + else > + return candidate; > + } > + return 0; > +} > +
Below is my hack to get hugetlbfs code converted. The patch compiles. Will test and send a signed-off-by version later.
not-signed-off-by: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
fs/hugetlbfs/inode.c | 3 +- include/linux/hugetlb.h | 2 + mm/hugetlb.c | 291 ++++++++++++++++++++++------------------------- 3 files changed, 139 insertions(+), 157 deletions(-)
diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c index ca4fa70..8309f5e 100644 --- a/fs/hugetlbfs/inode.c +++ b/fs/hugetlbfs/inode.c @@ -455,6 +455,7 @@ static struct inode *hugetlbfs_get_root(struct super_block *sb, inode->i_atime = inode->i_mtime = inode->i_ctime = CURRENT_TIME; info = HUGETLBFS_I(inode); mpol_shared_policy_init(&info->policy, NULL); + range_tree_init(&info->rg_root); inode->i_op = &hugetlbfs_dir_inode_operations; inode->i_fop = &simple_dir_operations; /* directory inodes start off with i_nlink == 2 (for "." entry) */ @@ -478,7 +479,6 @@ static struct inode *hugetlbfs_get_inode(struct super_block *sb, inode->i_mapping->a_ops = &hugetlbfs_aops; inode->i_mapping->backing_dev_info =&hugetlbfs_backing_dev_info; inode->i_atime = inode->i_mtime = inode->i_ctime = CURRENT_TIME; - INIT_LIST_HEAD(&inode->i_mapping->private_list); info = HUGETLBFS_I(inode); /* * The policy is initialized here even if we are creating a @@ -488,6 +488,7 @@ static struct inode *hugetlbfs_get_inode(struct super_block *sb, * the rb tree will still be empty. */ mpol_shared_policy_init(&info->policy, NULL); + range_tree_init(&info->rg_root); switch (mode & S_IFMT) { default: init_special_inode(inode, mode, dev); diff --git a/include/linux/hugetlb.h b/include/linux/hugetlb.h index 32e948c..b785541a 100644 --- a/include/linux/hugetlb.h +++ b/include/linux/hugetlb.h @@ -5,6 +5,7 @@ #include <linux/fs.h> #include <linux/hugetlb_inline.h> #include <linux/cgroup.h> +#include <linux/rangetree.h> struct ctl_table; struct user_struct; @@ -150,6 +151,7 @@ struct hugetlbfs_sb_info { struct hugetlbfs_inode_info { struct shared_policy policy; + struct range_tree_root rg_root; struct inode vfs_inode; }; diff --git a/mm/hugetlb.c b/mm/hugetlb.c index 4e1462d..a83727d 100644 --- a/mm/hugetlb.c +++ b/mm/hugetlb.c @@ -69,148 +69,94 @@ static DEFINE_SPINLOCK(hugetlb_lock); * down_read(&mm->mmap_sem); * mutex_lock(&hugetlb_instantiation_mutex); */ -struct file_region { - struct list_head link; - long from; - long to; -}; - -static long region_add(struct list_head *head, long f, long t) +static long region_chg(struct range_tree_root *rg_root, long start, long end, + struct range_tree_node **rg_nodep) { - struct file_region *rg, *nrg, *trg; + long chg = 0; + struct range_tree_node *rg_node; - /* Locate the region we are either in or before. */ - list_for_each_entry(rg, head, link) - if (f <= rg->to) - break; + rg_node = range_tree_in_range_adjacent(rg_root, start, end); + /* + * If we need to allocate a new range_tree_node, we return a charge + * with NULL *rg_node; + */ + if (rg_node == NULL) + return end - start; - /* Round our left edge to the current segment if it encloses us. */ - if (f > rg->from) - f = rg->from; + if (start < rg_node->start) + chg += rg_node->start - start; + if (rg_node->end < end) + chg += end - rg_node->end; - /* Check for and consume any regions we now overlap with. */ - nrg = rg; - list_for_each_entry_safe(rg, trg, rg->link.prev, link) { - if (&rg->link == head) - break; - if (rg->from > t) - break; - - /* If this area reaches higher then extend our area to - * include it completely. If this is not the first area - * which we intend to reuse, free it. */ - if (rg->to > t) - t = rg->to; - if (rg != nrg) { - list_del(&rg->link); - kfree(rg); - } - } - nrg->from = f; - nrg->to = t; - return 0; + *rg_nodep = rg_node; + return chg; } -static long region_chg(struct list_head *head, long f, long t) +static void region_add(struct range_tree_root *rg_root, long start, long end, + struct range_tree_node *rg_node) { - struct file_region *rg, *nrg; - long chg = 0; - - /* Locate the region we are before or in. */ - list_for_each_entry(rg, head, link) - if (f <= rg->to) - break; + if (rg_node == NULL) + return; - /* If we are below the current region then a new region is required. - * Subtle, allocate a new region at the position but make it zero - * size such that we can guarantee to record the reservation. */ - if (&rg->link == head || t < rg->from) { - nrg = kmalloc(sizeof(*nrg), GFP_KERNEL); - if (!nrg) - return -ENOMEM; - nrg->from = f; - nrg->to = f; - INIT_LIST_HEAD(&nrg->link); - list_add(&nrg->link, rg->link.prev); + if (start < rg_node->start) + rg_node->start = start; - return t - f; - } + if (end > rg_node->end) + rg_node->end = end; - /* Round our left edge to the current segment if it encloses us. */ - if (f > rg->from) - f = rg->from; - chg = t - f; - - /* Check for and consume any regions we now overlap with. */ - list_for_each_entry(rg, rg->link.prev, link) { - if (&rg->link == head) - break; - if (rg->from > t) - return chg; - - /* We overlap with this area, if it extends further than - * us then we must extend ourselves. Account for its - * existing reservation. */ - if (rg->to > t) { - chg += rg->to - t; - t = rg->to; - } - chg -= rg->to - rg->from; - } - return chg; + range_tree_add(rg_root, rg_node); } -static long region_truncate(struct list_head *head, long end) +static long region_truncate(struct range_tree_root *rg_root, long off) { - struct file_region *rg, *trg; long chg = 0; - - /* Locate the region we are either in or before. */ - list_for_each_entry(rg, head, link) - if (end <= rg->to) - break; - if (&rg->link == head) - return 0; - - /* If we are in the middle of a region then adjust it. */ - if (end > rg->from) { - chg = rg->to - end; - rg->to = end; - rg = list_entry(rg->link.next, typeof(*rg), link); - } - - /* Drop any remaining regions. */ - list_for_each_entry_safe(rg, trg, rg->link.prev, link) { - if (&rg->link == head) - break; - chg += rg->to - rg->from; - list_del(&rg->link); - kfree(rg); + struct rb_node *rb_node; + +restart: + rb_node = rb_first(&rg_root->head); + while (rb_node) { + struct range_tree_node *rg_node; + rg_node = rb_entry(rb_node, struct range_tree_node, rb); + if (rg_node->end <= off) { + rb_node = rb_next(rb_node); + continue; + } + if (rg_node->start < off) { + chg += rg_node->end - off; + rg_node->end = off; + rb_node = rb_next(rb_node); + continue; + } + chg += rg_node->end - rg_node->start; + rb_erase(rb_node, &rg_root->head); + goto restart; } return chg; } -static long region_count(struct list_head *head, long f, long t) +static long region_count(struct range_tree_root *rg_root, long start, long end) { - struct file_region *rg; long chg = 0; + struct rb_node *rb_node; - /* Locate each segment we overlap with, and count that overlap. */ - list_for_each_entry(rg, head, link) { - int seg_from; - int seg_to; + rb_node = rb_first(&rg_root->head); + while (rb_node) { + int seg_from, seg_to; + struct range_tree_node *rg_node; - if (rg->to <= f) + rg_node = rb_entry(rb_node, struct range_tree_node, rb); + if (rg_node->end <= start) { + rb_node = rb_next(rb_node); continue; - if (rg->from >= t) + } + if (rg_node->start >= end) break; - - seg_from = max(rg->from, f); - seg_to = min(rg->to, t); + seg_from = max(rg_node->start, (u64)start); + seg_to = min(rg_node->end, (u64)end); chg += seg_to - seg_from; + rb_node = rb_next(rb_node); } - return chg; } @@ -302,7 +248,7 @@ static void set_vma_private_data(struct vm_area_struct *vma, struct resv_map { struct kref refs; - struct list_head regions; + struct range_tree_root rg_root; }; static struct resv_map *resv_map_alloc(void) @@ -312,7 +258,7 @@ static struct resv_map *resv_map_alloc(void) return NULL; kref_init(&resv_map->refs); - INIT_LIST_HEAD(&resv_map->regions); + range_tree_init(&resv_map->rg_root); return resv_map; } @@ -322,7 +268,7 @@ static void resv_map_release(struct kref *ref) struct resv_map *resv_map = container_of(ref, struct resv_map, refs); /* Clear out any active regions before we release the map. */ - region_truncate(&resv_map->regions, 0); + region_truncate(&resv_map->rg_root, 0); kfree(resv_map); } @@ -980,16 +926,19 @@ static void return_unused_surplus_pages(struct hstate *h, * No action is required on failure. */ static long vma_needs_reservation(struct hstate *h, - struct vm_area_struct *vma, unsigned long addr) + struct vm_area_struct *vma, + unsigned long addr, + struct range_tree_node **rg_node) { struct address_space *mapping = vma->vm_file->f_mapping; struct inode *inode = mapping->host; + struct hugetlbfs_inode_info *hinfo = HUGETLBFS_I(inode); + *rg_node = NULL; if (vma->vm_flags & VM_MAYSHARE) { pgoff_t idx = vma_hugecache_offset(h, vma, addr); - return region_chg(&inode->i_mapping->private_list, - idx, idx + 1); + return region_chg(&hinfo->rg_root, idx, idx + 1, rg_node); } else if (!is_vma_resv_set(vma, HPAGE_RESV_OWNER)) { return 1; @@ -998,28 +947,34 @@ static long vma_needs_reservation(struct hstate *h, pgoff_t idx = vma_hugecache_offset(h, vma, addr); struct resv_map *reservations = vma_resv_map(vma); - err = region_chg(&reservations->regions, idx, idx + 1); + err = region_chg(&reservations->rg_root, idx, idx + 1, rg_node); if (err < 0) return err; return 0; } } static void vma_commit_reservation(struct hstate *h, - struct vm_area_struct *vma, unsigned long addr) + struct vm_area_struct *vma, + unsigned long addr, + struct range_tree_node *rg_node) { struct address_space *mapping = vma->vm_file->f_mapping; struct inode *inode = mapping->host; + struct hugetlbfs_inode_info *hinfo = HUGETLBFS_I(inode); + + if (rg_node == NULL) + return; if (vma->vm_flags & VM_MAYSHARE) { pgoff_t idx = vma_hugecache_offset(h, vma, addr); - region_add(&inode->i_mapping->private_list, idx, idx + 1); + region_add(&hinfo->rg_root, idx, idx + 1, rg_node); } else if (is_vma_resv_set(vma, HPAGE_RESV_OWNER)) { pgoff_t idx = vma_hugecache_offset(h, vma, addr); struct resv_map *reservations = vma_resv_map(vma); /* Mark this page used in the map. */ - region_add(&reservations->regions, idx, idx + 1); + region_add(&reservations->rg_root, idx, idx + 1, rg_node); } } @@ -1027,6 +982,7 @@ static struct page *alloc_huge_page(struct vm_area_struct *vma, unsigned long addr, int avoid_reserve) { int ret, idx; + struct range_tree_node *rg_node; struct hstate *h = hstate_vma(vma); struct page *page; struct mem_cgroup *memcg; @@ -1042,18 +998,24 @@ static struct page *alloc_huge_page(struct vm_area_struct *vma, * MAP_NORESERVE mappings may also need pages and quota allocated * if no reserve mapping overlaps. */ - chg = vma_needs_reservation(h, vma, addr); - if (chg < 0) - return ERR_PTR(-ENOMEM); - if (chg) - if (hugetlb_get_quota(inode->i_mapping, chg)) - return ERR_PTR(-ENOSPC); + chg = vma_needs_reservation(h, vma, addr, &rg_node); + if (chg > 0 && rg_node == NULL) { + rg_node = kzalloc(sizeof(*rg_node), GFP_KERNEL); + if (rg_node == NULL) + return ERR_PTR(-ENOMEM); + } + if (chg) { + if (hugetlb_get_quota(inode->i_mapping, chg)) { + ret = -ENOSPC; + goto err_out; + } + } ret = mem_cgroup_hugetlb_charge_page(idx, pages_per_huge_page(h), &memcg); if (ret) { - hugetlb_put_quota(inode->i_mapping, chg); - return ERR_PTR(-ENOSPC); + ret = -ENOSPC; + goto err_out_quota; } spin_lock(&hugetlb_lock); page = dequeue_huge_page_vma(h, vma, addr, avoid_reserve); @@ -1062,21 +1024,26 @@ static struct page *alloc_huge_page(struct vm_area_struct *vma, if (!page) { page = alloc_buddy_huge_page(h, NUMA_NO_NODE); if (!page) { - mem_cgroup_hugetlb_uncharge_memcg(idx, - pages_per_huge_page(h), - memcg); - hugetlb_put_quota(inode->i_mapping, chg); - return ERR_PTR(-ENOSPC); + ret = -ENOSPC; + goto err_out_uncharge; } } set_page_private(page, (unsigned long) mapping); - vma_commit_reservation(h, vma, addr); + vma_commit_reservation(h, vma, addr, rg_node); /* update page cgroup details */ mem_cgroup_hugetlb_commit_charge(idx, pages_per_huge_page(h), memcg, page); return page; + +err_out_uncharge: + mem_cgroup_hugetlb_uncharge_memcg(idx, pages_per_huge_page(h), memcg); +err_out_quota: + hugetlb_put_quota(inode->i_mapping, chg); +err_out: + kfree(rg_node); + return ERR_PTR(ret); } int __weak alloc_bootmem_huge_page(struct hstate *h) @@ -2170,7 +2137,7 @@ static void hugetlb_vm_op_close(struct vm_area_struct *vma) end = vma_hugecache_offset(h, vma, vma->vm_end); reserve = (end - start) - - region_count(&reservations->regions, start, end); + region_count(&reservations->rg_root, start, end); kref_put(&reservations->refs, resv_map_release); @@ -2697,11 +2664,13 @@ retry: * any allocations necessary to record that reservation occur outside * the spinlock. */ - if ((flags & FAULT_FLAG_WRITE) && !(vma->vm_flags & VM_SHARED)) - if (vma_needs_reservation(h, vma, address) < 0) { + if ((flags & FAULT_FLAG_WRITE) && !(vma->vm_flags & VM_SHARED)) { + struct range_tree_node *rg_node; + if (vma_needs_reservation(h, vma, address, &rg_node) < 0) { ret = VM_FAULT_OOM; goto backout_unlocked; } + } spin_lock(&mm->page_table_lock); size = i_size_read(mapping->host) >> huge_page_shift(h); @@ -2789,7 +2758,8 @@ int hugetlb_fault(struct mm_struct *mm, struct vm_area_struct *vma, * consumed. */ if ((flags & FAULT_FLAG_WRITE) && !pte_write(entry)) { - if (vma_needs_reservation(h, vma, address) < 0) { + struct range_tree_node *rg_node; + if (vma_needs_reservation(h, vma, address, &rg_node) < 0) { ret = VM_FAULT_OOM; goto out_mutex; } @@ -2975,7 +2945,9 @@ int hugetlb_reserve_pages(struct inode *inode, vm_flags_t vm_flags) { long ret, chg; + struct range_tree_node *rg_node; struct hstate *h = hstate_inode(inode); + struct hugetlbfs_inode_info *hinfo = HUGETLBFS_I(inode); /* * Only apply hugepage reservation if asked. At fault time, an @@ -2992,25 +2964,27 @@ int hugetlb_reserve_pages(struct inode *inode, * called to make the mapping read-write. Assume !vma is a shm mapping */ if (!vma || vma->vm_flags & VM_MAYSHARE) - chg = region_chg(&inode->i_mapping->private_list, from, to); + chg = region_chg(&hinfo->rg_root, from, to, &rg_node); else { struct resv_map *resv_map = resv_map_alloc(); if (!resv_map) return -ENOMEM; - chg = to - from; - + chg = region_chg(&resv_map->rg_root, from, to, &rg_node); set_vma_resv_map(vma, resv_map); set_vma_resv_flags(vma, HPAGE_RESV_OWNER); } - - if (chg < 0) - return chg; - + if (chg > 0 && rg_node == NULL ) { + /* We need allocate a new node */ + rg_node = kzalloc(sizeof(*rg_node), GFP_KERNEL); + if (rg_node == NULL) + return -ENOMEM; + } /* There must be enough filesystem quota for the mapping */ - if (hugetlb_get_quota(inode->i_mapping, chg)) - return -ENOSPC; - + if (hugetlb_get_quota(inode->i_mapping, chg)) { + ret = -ENOSPC; + goto err_out; + } /* * Check enough hugepages are available for the reservation. * Hand back the quota if there are not @@ -3018,7 +2992,7 @@ int hugetlb_reserve_pages(struct inode *inode, ret = hugetlb_acct_memory(h, chg); if (ret < 0) { hugetlb_put_quota(inode->i_mapping, chg); - return ret; + goto err_out; } /* @@ -3033,14 +3007,19 @@ int hugetlb_reserve_pages(struct inode *inode, * else has to be done for private mappings here */ if (!vma || vma->vm_flags & VM_MAYSHARE) - region_add(&inode->i_mapping->private_list, from, to); + region_add(&hinfo->rg_root, from, to, rg_node); return 0; +err_out: + kfree(rg_node); + return ret; } void hugetlb_unreserve_pages(struct inode *inode, long offset, long freed) { struct hstate *h = hstate_inode(inode); - long chg = region_truncate(&inode->i_mapping->private_list, offset); + struct hugetlbfs_inode_info *hinfo = HUGETLBFS_I(inode); + + long chg = region_truncate(&hinfo->rg_root, offset); spin_lock(&inode->i_lock); inode->i_blocks -= (blocks_per_huge_page(h) * freed);
| |