[PATCH v2 0/2] alloc_huge_page/hugetlb_reserve_pages race

[PATCH v2 0/2] alloc_huge_page/hugetlb_reserve_pages race

[Mike Kravetz]

This updated patch set includes new documentation for the region/
reserve map routines.  Since I am not the original author of this
code, comments would be appreciated.

While working on hugetlbfs fallocate support, I noticed the following
race in the existing code.  It is unlikely that this race is hit very
often in the current code.  However, if more functionality to add and
remove pages to hugetlbfs mappings (such as fallocate) is added the
likelihood of hitting this race will increase.

alloc_huge_page and hugetlb_reserve_pages use information from the
reserve map to determine if there are enough available huge pages to
complete the operation, as well as adjust global reserve and subpool
usage counts.  The order of operations is as follows:
- call region_chg() to determine the expected change based on reserve map
- determine if enough resources are available for this operation
- adjust global counts based on the expected change
- call region_add() to update the reserve map
The issue is that reserve map could change between the call to region_chg
and region_add.  In this case, the counters which were adjusted based on
the output of region_chg will not be correct.

In order to hit this race today, there must be an existing shared hugetlb
mmap created with the MAP_NORESERVE flag.  A page fault to allocate a huge
page via this mapping must occur at the same another task is mapping the
same region without the MAP_NORESERVE flag.

The patch set does not prevent the race from happening.  Rather, it adds
simple functionality to detect when the race has occurred.  If a race is
detected, then the incorrect counts are adjusted.

v2:
  Added documentation for the region/reserve map routines
  Created common routine for vma_commit_reservation and
    vma_commit_reservation to help prevent them from drifting
    apart in the future.

Mike Kravetz (2):
  mm/hugetlb: compute/return the number of regions added by region_add()
  mm/hugetlb: handle races in alloc_huge_page and hugetlb_reserve_pages

 mm/hugetlb.c | 154 +++++++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 124 insertions(+), 30 deletions(-)

-- 
2.1.0

[PATCH v2 1/2] mm/hugetlb: compute/return the number of regions added by region_add()

[Mike Kravetz]

Modify region_add() to keep track of regions(pages) added to the
reserve map and return this value.  The return value can be
compared to the return value of region_chg() to determine if the
map was modified between calls.

Add documentation to the reserve/region map routines.

Make vma_commit_reservation() also pass along the return value of
region_add().  In the normal case, we want vma_commit_reservation
to return the same value as the preceding call to vma_needs_reservation.
Create a common __vma_reservation_common routine to help keep the
special case return values in sync

Signed-off-by: Mike Kravetz <mike.kravetz@oracle.com>
---
 mm/hugetlb.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 94 insertions(+), 26 deletions(-)

diff --git a/mm/hugetlb.c b/mm/hugetlb.c
index 54f129d..3855889 100644
--- a/mm/hugetlb.c
+++ b/mm/hugetlb.c
@@ -212,8 +212,16 @@ static inline struct hugepage_subpool *subpool_vma(struct vm_area_struct *vma)
  * Region tracking -- allows tracking of reservations and instantiated pages
  *                    across the pages in a mapping.
  *
- * The region data structures are embedded into a resv_map and
- * protected by a resv_map's lock
+ * The region data structures are embedded into a resv_map and protected
+ * by a resv_map's lock.  The set of regions within the resv_map represent
+ * reservations for huge pages, or huge pages that have already been
+ * instantiated within the map.  The from and to elements are huge page
+ * indicies into the associated mapping.  from indicates the starting index
+ * of the region.  to represents the first index past the end of  the region.
+ * For example, a file region structure with from == 0 and to == 4 represents
+ * four huge pages in a mapping.  It is important to note that the to element
+ * represents the first element past the end of the region. This is used in
+ * arithmetic as 4(to) - 0(from) = 4 huge pages in the region.
  */
 struct file_region {
 	struct list_head link;
@@ -221,10 +229,23 @@ struct file_region {
 	long to;
 };
 
+/*
+ * Add the huge page range represented by indicies f (from)
+ * and t (to) to the reserve map.  Existing regions will be
+ * expanded to accommodate the specified range.  We know only
+ * existing regions need to be expanded, because region_add
+ * is only called after region_chg(with the same range).  If
+ * a new file_region structure must be allocated, it is done
+ * in region_chg.
+ *
+ * Return the number of new huge pages added to the map.  This
+ * number is greater than or equal to zero.
+ */
 static long region_add(struct resv_map *resv, long f, long t)
 {
 	struct list_head *head = &resv->regions;
 	struct file_region *rg, *nrg, *trg;
+	long add = 0;
 
 	spin_lock(&resv->lock);
 	/* Locate the region we are either in or before. */
@@ -250,16 +271,44 @@ static long region_add(struct resv_map *resv, long f, long t)
 		if (rg->to > t)
 			t = rg->to;
 		if (rg != nrg) {
+			/* Decrement return value by the deleted range.
+			 * Another range will span this area so that by
+			 * end of routine add will be >= zero
+			 */
+			add -= (rg->to - rg->from);
 			list_del(&rg->link);
 			kfree(rg);
 		}
 	}
+
+	add += (nrg->from - f);		/* Added to beginning of region */
 	nrg->from = f;
+	add += t - nrg->to;		/* Added to end of region */
 	nrg->to = t;
+
 	spin_unlock(&resv->lock);
-	return 0;
+	return add;
 }
 
+/*
+ * Examine the existing reserve map and determine how many
+ * huge pages in the specified range (f, t) are NOT currently
+ * represented.  This routine is called before a subsequent
+ * call to region_add that will actually modify the reserve
+ * map to add the specified range (f, t).  region_chg does
+ * not change the number of huge pages represented by the
+ * map.  However, if the existing regions in the map can not
+ * be expanded to represent the new range, a new file_region
+ * structure is added to the map as a placeholder.  This is
+ * so that the subsequent region_add call will have all
+ * regions it needs and will not fail.
+ *
+ * Returns the number of huge pages that need to be added
+ * to the existing reservation map for the range (f, t).
+ * This number is greater or equal to zero.  -ENOMEM is
+ * returned if a new  file_region structure can not be
+ * allocated.
+ */
 static long region_chg(struct resv_map *resv, long f, long t)
 {
 	struct list_head *head = &resv->regions;
@@ -326,6 +375,11 @@ out_nrg:
 	return chg;
 }
 
+/*
+ * Truncate the reserve map at index 'end'.  Modify/truncate any
+ * region which contains end.  Delete any regions past end.
+ * Return the number of huge pages removed from the map.
+ */
 static long region_truncate(struct resv_map *resv, long end)
 {
 	struct list_head *head = &resv->regions;
@@ -361,6 +415,10 @@ out:
 	return chg;
 }
 
+/*
+ * Count and return the number of huge pages in the reserve map
+ * that intersect with the range (f, t).
+ */
 static long region_count(struct resv_map *resv, long f, long t)
 {
 	struct list_head *head = &resv->regions;
@@ -1424,46 +1482,56 @@ static void return_unused_surplus_pages(struct hstate *h,
 }
 
 /*
- * Determine if the huge page at addr within the vma has an associated
- * reservation.  Where it does not we will need to logically increase
- * reservation and actually increase subpool usage before an allocation
- * can occur.  Where any new reservation would be required the
- * reservation change is prepared, but not committed.  Once the page
- * has been allocated from the subpool and instantiated the change should
- * be committed via vma_commit_reservation.  No action is required on
- * failure.
+ * vma_needs_reservation and vma_commit_reservation are used by the huge
+ * page allocation routines to manage reservations.
+ *
+ * vma_needs_reservation is called to determine if the huge page at addr
+ * within the vma has an associated reservation.  If a reservation is
+ * needed, the value 1 is returned.  The caller is then responsible for
+ * managing the global reservation and subpool usage counts.  After
+ * the huge page has been allocated, vma_commit_reservation is called
+ * to add the page to the reservation map.
+ *
+ * In the normal case, vma_commit_reservation should return the same value
+ * as the preceding vma_needs_reservation call.  The only time this is
+ * not the case is if a reserve map was changed between calls.  It is the
+ * responsibility of the caller to notice the difference and take appropriate
+ * action.
  */
-static long vma_needs_reservation(struct hstate *h,
-			struct vm_area_struct *vma, unsigned long addr)
+static long __vma_reservation_common(struct hstate *h,
+				struct vm_area_struct *vma, unsigned long addr,
+				bool needs)
 {
 	struct resv_map *resv;
 	pgoff_t idx;
-	long chg;
+	long ret;
 
 	resv = vma_resv_map(vma);
 	if (!resv)
 		return 1;
 
 	idx = vma_hugecache_offset(h, vma, addr);
-	chg = region_chg(resv, idx, idx + 1);
+	if (needs)
+		ret = region_chg(resv, idx, idx + 1);
+	else
+		ret = region_add(resv, idx, idx + 1);
 
 	if (vma->vm_flags & VM_MAYSHARE)
-		return chg;
+		return ret;
 	else
-		return chg < 0 ? chg : 0;
+		return ret < 0 ? ret : 0;
 }
-static void vma_commit_reservation(struct hstate *h,
+
+static long vma_needs_reservation(struct hstate *h,
 			struct vm_area_struct *vma, unsigned long addr)
 {
-	struct resv_map *resv;
-	pgoff_t idx;
-
-	resv = vma_resv_map(vma);
-	if (!resv)
-		return;
+	return __vma_reservation_common(h, vma, addr, (bool)1);
+}
 
-	idx = vma_hugecache_offset(h, vma, addr);
-	region_add(resv, idx, idx + 1);
+static long vma_commit_reservation(struct hstate *h,
+			struct vm_area_struct *vma, unsigned long addr)
+{
+	return __vma_reservation_common(h, vma, addr, (bool)0);
 }
 
 static struct page *alloc_huge_page(struct vm_area_struct *vma,
-- 
2.1.0

[PATCH v2 2/2] mm/hugetlb: handle races in alloc_huge_page and hugetlb_reserve_pages

[Mike Kravetz]

alloc_huge_page and hugetlb_reserve_pages use region_chg to
calculate the number of pages which will be added to the reserve
map.  Subpool and global reserve counts are adjusted based on
the output of region_chg.  Before the pages are actually added
to the reserve map, these routines could race and add fewer
pages than expected.  If this happens, the subpool and global
reserve counts are not correct.

Compare the number of pages actually added (region_add) to those
expected to added (region_chg).  If fewer pages are actually added,
this indicates a race and adjust counters accordingly.

Signed-off-by: Mike Kravetz <mike.kravetz@oracle.com>
---
 mm/hugetlb.c | 34 ++++++++++++++++++++++++++++++----
 1 file changed, 30 insertions(+), 4 deletions(-)

diff --git a/mm/hugetlb.c b/mm/hugetlb.c
index 3855889..9234163 100644
--- a/mm/hugetlb.c
+++ b/mm/hugetlb.c
@@ -1540,7 +1540,7 @@ static struct page *alloc_huge_page(struct vm_area_struct *vma,
 	struct hugepage_subpool *spool = subpool_vma(vma);
 	struct hstate *h = hstate_vma(vma);
 	struct page *page;
-	long chg;
+	long chg, commit;
 	int ret, idx;
 	struct hugetlb_cgroup *h_cg;
 
@@ -1581,7 +1581,20 @@ static struct page *alloc_huge_page(struct vm_area_struct *vma,
 
 	set_page_private(page, (unsigned long)spool);
 
-	vma_commit_reservation(h, vma, addr);
+	commit = vma_commit_reservation(h, vma, addr);
+	if (unlikely(chg > commit)) {
+		/*
+		 * The page was added to the reservation map between
+		 * vma_needs_reservation and vma_commit_reservation.
+		 * This indicates a race with hugetlb_reserve_pages.
+		 * Adjust for the subpool count incremented above AND
+		 * in hugetlb_reserve_pages for the same page.  Also,
+		 * the reservation count added in hugetlb_reserve_pages
+		 * no longer applies.
+		 */
+		hugepage_subpool_put_pages(spool, 1);
+		hugetlb_acct_memory(h, -1);
+	}
 	return page;
 
 out_uncharge_cgroup:
@@ -3695,8 +3708,21 @@ int hugetlb_reserve_pages(struct inode *inode,
 	 * consumed reservations are stored in the map. Hence, nothing
 	 * else has to be done for private mappings here
 	 */
-	if (!vma || vma->vm_flags & VM_MAYSHARE)
-		region_add(resv_map, from, to);
+	if (!vma || vma->vm_flags & VM_MAYSHARE) {
+		long add = region_add(resv_map, from, to);
+
+		if (unlikely(chg > add)) {
+			/*
+			 * pages in this range were added to the reserve
+			 * map between region_chg and region_add.  This
+			 * indicates a race with alloc_huge_page.  Adjust
+			 * the subpool and reserve counts modified above
+			 * based on the difference.
+			 */
+			hugepage_subpool_put_pages(spool, chg - add);
+			hugetlb_acct_memory(h, -(chg - ret));
+		}
+	}
 	return 0;
 out_err:
 	if (vma && is_vma_resv_set(vma, HPAGE_RESV_OWNER))
-- 
2.1.0

Re: [PATCH v2 1/2] mm/hugetlb: compute/return the number of regions added by region_add()

[Naoya Horiguchi]

On Fri, May 22, 2015 at 08:55:03PM -0700, Mike Kravetz wrote:
> Modify region_add() to keep track of regions(pages) added to the
> reserve map and return this value.  The return value can be
> compared to the return value of region_chg() to determine if the
> map was modified between calls.
> 
> Add documentation to the reserve/region map routines.
> 
> Make vma_commit_reservation() also pass along the return value of
> region_add().  In the normal case, we want vma_commit_reservation
> to return the same value as the preceding call to vma_needs_reservation.
> Create a common __vma_reservation_common routine to help keep the
> special case return values in sync
> 
> Signed-off-by: Mike Kravetz <mike.kravetz@oracle.com>
> ---
>  mm/hugetlb.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++-------------
>  1 file changed, 94 insertions(+), 26 deletions(-)
> 
> diff --git a/mm/hugetlb.c b/mm/hugetlb.c
> index 54f129d..3855889 100644
> --- a/mm/hugetlb.c
> +++ b/mm/hugetlb.c
> @@ -212,8 +212,16 @@ static inline struct hugepage_subpool *subpool_vma(struct vm_area_struct *vma)
>   * Region tracking -- allows tracking of reservations and instantiated pages
>   *                    across the pages in a mapping.
>   *
> - * The region data structures are embedded into a resv_map and
> - * protected by a resv_map's lock
> + * The region data structures are embedded into a resv_map and protected
> + * by a resv_map's lock.  The set of regions within the resv_map represent
> + * reservations for huge pages, or huge pages that have already been
> + * instantiated within the map.

>  The from and to elements are huge page
> + * indicies into the associated mapping.  from indicates the starting index
> + * of the region.  to represents the first index past the end of  the region.
> + * For example, a file region structure with from == 0 and to == 4 represents
> + * four huge pages in a mapping.  It is important to note that the to element
> + * represents the first element past the end of the region. This is used in
> + * arithmetic as 4(to) - 0(from) = 4 huge pages in the region.

How about just saying "[from, to)", which implies "from" is inclusive and "to"
is exclusive. I hope this mathematical notation is widely accepted among kernel
developers.

>   */
>  struct file_region {
>  	struct list_head link;
> @@ -221,10 +229,23 @@ struct file_region {
>  	long to;
>  };
>  
> +/*
> + * Add the huge page range represented by indicies f (from)
> + * and t (to) to the reserve map.  Existing regions will be
> + * expanded to accommodate the specified range.  We know only
> + * existing regions need to be expanded, because region_add
> + * is only called after region_chg(with the same range).  If
> + * a new file_region structure must be allocated, it is done
> + * in region_chg.
> + *
> + * Return the number of new huge pages added to the map.  This
> + * number is greater than or equal to zero.
> + */
>  static long region_add(struct resv_map *resv, long f, long t)
>  {
>  	struct list_head *head = &resv->regions;
>  	struct file_region *rg, *nrg, *trg;
> +	long add = 0;
>  
>  	spin_lock(&resv->lock);
>  	/* Locate the region we are either in or before. */
> @@ -250,16 +271,44 @@ static long region_add(struct resv_map *resv, long f, long t)
>  		if (rg->to > t)
>  			t = rg->to;
>  		if (rg != nrg) {
> +			/* Decrement return value by the deleted range.
> +			 * Another range will span this area so that by
> +			 * end of routine add will be >= zero
> +			 */
> +			add -= (rg->to - rg->from);

I can't say how, but if file_region data were broken for some reason (mainly
due to bug,) this could return negative value, so how about asserting add >=0
with VM_BUG_ON() at the end of this function?

>  			list_del(&rg->link);
>  			kfree(rg);
>  		}
>  	}
> +
> +	add += (nrg->from - f);		/* Added to beginning of region */
>  	nrg->from = f;
> +	add += t - nrg->to;		/* Added to end of region */
>  	nrg->to = t;
> +
>  	spin_unlock(&resv->lock);
> -	return 0;
> +	return add;
>  }
>  
> +/*
> + * Examine the existing reserve map and determine how many
> + * huge pages in the specified range (f, t) are NOT currently

"[f, t)" would be better.

> + * represented.  This routine is called before a subsequent
> + * call to region_add that will actually modify the reserve
> + * map to add the specified range (f, t).  region_chg does
> + * not change the number of huge pages represented by the
> + * map.  However, if the existing regions in the map can not
> + * be expanded to represent the new range, a new file_region
> + * structure is added to the map as a placeholder.  This is
> + * so that the subsequent region_add call will have all
> + * regions it needs and will not fail.
> + *
> + * Returns the number of huge pages that need to be added
> + * to the existing reservation map for the range (f, t).
> + * This number is greater or equal to zero.  -ENOMEM is
> + * returned if a new  file_region structure can not be
> + * allocated.
> + */
>  static long region_chg(struct resv_map *resv, long f, long t)
>  {
>  	struct list_head *head = &resv->regions;
> @@ -326,6 +375,11 @@ out_nrg:
>  	return chg;
>  }
>  
> +/*
> + * Truncate the reserve map at index 'end'.  Modify/truncate any
> + * region which contains end.  Delete any regions past end.
> + * Return the number of huge pages removed from the map.
> + */
>  static long region_truncate(struct resv_map *resv, long end)
>  {
>  	struct list_head *head = &resv->regions;
> @@ -361,6 +415,10 @@ out:
>  	return chg;
>  }
>  
> +/*
> + * Count and return the number of huge pages in the reserve map
> + * that intersect with the range (f, t).
> + */
>  static long region_count(struct resv_map *resv, long f, long t)
>  {
>  	struct list_head *head = &resv->regions;
> @@ -1424,46 +1482,56 @@ static void return_unused_surplus_pages(struct hstate *h,
>  }
>  
>  /*
> - * Determine if the huge page at addr within the vma has an associated
> - * reservation.  Where it does not we will need to logically increase
> - * reservation and actually increase subpool usage before an allocation
> - * can occur.  Where any new reservation would be required the
> - * reservation change is prepared, but not committed.  Once the page
> - * has been allocated from the subpool and instantiated the change should
> - * be committed via vma_commit_reservation.  No action is required on
> - * failure.
> + * vma_needs_reservation and vma_commit_reservation are used by the huge
> + * page allocation routines to manage reservations.
> + *
> + * vma_needs_reservation is called to determine if the huge page at addr
> + * within the vma has an associated reservation.  If a reservation is
> + * needed, the value 1 is returned.  The caller is then responsible for
> + * managing the global reservation and subpool usage counts.  After
> + * the huge page has been allocated, vma_commit_reservation is called
> + * to add the page to the reservation map.
> + *
> + * In the normal case, vma_commit_reservation should return the same value
> + * as the preceding vma_needs_reservation call.  The only time this is
> + * not the case is if a reserve map was changed between calls.  It is the
> + * responsibility of the caller to notice the difference and take appropriate
> + * action.
>   */
> -static long vma_needs_reservation(struct hstate *h,
> -			struct vm_area_struct *vma, unsigned long addr)
> +static long __vma_reservation_common(struct hstate *h,
> +				struct vm_area_struct *vma, unsigned long addr,
> +				bool needs)
>  {
>  	struct resv_map *resv;
>  	pgoff_t idx;
> -	long chg;
> +	long ret;
>  
>  	resv = vma_resv_map(vma);
>  	if (!resv)
>  		return 1;
>  
>  	idx = vma_hugecache_offset(h, vma, addr);
> -	chg = region_chg(resv, idx, idx + 1);
> +	if (needs)
> +		ret = region_chg(resv, idx, idx + 1);
> +	else
> +		ret = region_add(resv, idx, idx + 1);

This code sharing is OK, but the name "needs" looks a bit unclear to me.
I feel that it's more readable if we name "commit" (or "commits") to the bool
parameter and call region_add() if "commit" is true.

>  
>  	if (vma->vm_flags & VM_MAYSHARE)
> -		return chg;
> +		return ret;
>  	else
> -		return chg < 0 ? chg : 0;
> +		return ret < 0 ? ret : 0;
>  }
> -static void vma_commit_reservation(struct hstate *h,
> +
> +static long vma_needs_reservation(struct hstate *h,
>  			struct vm_area_struct *vma, unsigned long addr)
>  {
> -	struct resv_map *resv;
> -	pgoff_t idx;
> -
> -	resv = vma_resv_map(vma);
> -	if (!resv)
> -		return;
> +	return __vma_reservation_common(h, vma, addr, (bool)1);

You can simply use literal "true"?

Thanks,
Naoya Horiguchi

> +}
>  
> -	idx = vma_hugecache_offset(h, vma, addr);
> -	region_add(resv, idx, idx + 1);
> +static long vma_commit_reservation(struct hstate *h,
> +			struct vm_area_struct *vma, unsigned long addr)
> +{
> +	return __vma_reservation_common(h, vma, addr, (bool)0);
>  }
>  
>  static struct page *alloc_huge_page(struct vm_area_struct *vma,
> -- 
> 2.1.0
> 

Re: [PATCH v2 0/2] alloc_huge_page/hugetlb_reserve_pages race

[Davidlohr Bueso]

On Fri, 2015-05-22 at 20:55 -0700, Mike Kravetz wrote:
> This updated patch set includes new documentation for the region/
> reserve map routines.  Since I am not the original author of this
> code, comments would be appreciated.
> 
> While working on hugetlbfs fallocate support, I noticed the following
> race in the existing code.  It is unlikely that this race is hit very
> often in the current code.

Have you actually run into this issue? Can you produce a testcase?

>   However, if more functionality to add and
> remove pages to hugetlbfs mappings (such as fallocate) is added the
> likelihood of hitting this race will increase.
> 
> alloc_huge_page and hugetlb_reserve_pages use information from the
> reserve map to determine if there are enough available huge pages to
> complete the operation, as well as adjust global reserve and subpool
> usage counts.  The order of operations is as follows:
> - call region_chg() to determine the expected change based on reserve map
> - determine if enough resources are available for this operation
> - adjust global counts based on the expected change
> - call region_add() to update the reserve map
> The issue is that reserve map could change between the call to region_chg
> and region_add.  In this case, the counters which were adjusted based on
> the output of region_chg will not be correct.
> 
> In order to hit this race today, there must be an existing shared hugetlb
> mmap created with the MAP_NORESERVE flag.  A page fault to allocate a huge
> page via this mapping must occur at the same another task is mapping the
> same region without the MAP_NORESERVE flag.

In the past file regions were serialized by either mmap_sem (exclusive)
or the hugetlb instantiation mutex (when mmap_sem was shared). With
finer grained locking, however, we now rely on the resv_map->lock. So I
guess you are referring to something like this, no?

CPU0 (via vma_[needs/commit]_reservation)  CPU1
hugetlb_fault				
  mutex_lock(hash_A)			  
  hugetlb_no_page			
    alloc_huge_page			shm_get  
       region_chg			  hugetlb_file_setup
       <accounting updates>		    hugetlb_reserve_pages
					      region_chg
       region_add			      <accounting updates>
					      region_add

Couldn't this race also occur upon concurrent faults on two different
hashes backed by the same vma?

Anyway, it's memorial day, so I'll take a closer look during the week,
but you seem to be correct. An alternative could be to continue holding
the spinlock until the after region_add, but I like your "fixup"
approach.

> The patch set does not prevent the race from happening.  Rather, it adds
> simple functionality to detect when the race has occurred.  If a race is
> detected, then the incorrect counts are adjusted.
> 
> v2:
>   Added documentation for the region/reserve map routines

Thanks for doing this, as akpm mentioned, it is much needed. However,
this should be a new, separate patch.

>   Created common routine for vma_commit_reservation and
>     vma_commit_reservation to help prevent them from drifting
>     apart in the future.
> 
> Mike Kravetz (2):
>   mm/hugetlb: compute/return the number of regions added by region_add()
>   mm/hugetlb: handle races in alloc_huge_page and hugetlb_reserve_pages

Ah, so these two patches are duplicates from your fallocate series,
right? You should drop those from that patchset then, as bugfixes should
be separate.

Could you rename patch 2 to something more meaningful? ie:

mm/hugetlb: account for races between region_chg and region_add

Also, gosh those function names are nasty and unclear -- I would change
them to region_prepare and region_commit, or something like that where
the purpose is more obvious.

Thanks,
Davidlohr

Re: [PATCH v2 1/2] mm/hugetlb: compute/return the number of regions added by region_add()

[Davidlohr Bueso]

On Fri, 2015-05-22 at 20:55 -0700, Mike Kravetz wrote:
> + * The region data structures are embedded into a resv_map and protected
> + * by a resv_map's lock.  The set of regions within the resv_map represent
> + * reservations for huge pages, or huge pages that have already been
> + * instantiated within the map.  The from and to elements are huge page
> + * indicies into the associated mapping.  from indicates the starting index
> + * of the region.  to represents the first index past the end of  the region.

newline

> + * For example, a file region structure with from == 0 and to == 4 represents
> + * four huge pages in a mapping.  It is important to note that the to element
> + * represents the first element past the end of the region. This is used in
> + * arithmetic as 4(to) - 0(from) = 4 huge pages in the region.
>   */
>  struct file_region {
>  	struct list_head link;
> @@ -221,10 +229,23 @@ struct file_region {
>  	long to;
>  };
>  
> +/*
> + * Add the huge page range represented by indicies f (from)
> + * and t (to) to the reserve map.  Existing regions will be

How about simply renaming those parameters to from and to across the
entire hugetlb code.

Thanks,
Davidlohr

Re: [PATCH v2 1/2] mm/hugetlb: compute/return the number of regions added by region_add()

[Mike Kravetz]

On 05/24/2015 11:19 PM, Naoya Horiguchi wrote:
> On Fri, May 22, 2015 at 08:55:03PM -0700, Mike Kravetz wrote:
>> Modify region_add() to keep track of regions(pages) added to the
>> reserve map and return this value.  The return value can be
>> compared to the return value of region_chg() to determine if the
>> map was modified between calls.
>>
>> Add documentation to the reserve/region map routines.
>>
>> Make vma_commit_reservation() also pass along the return value of
>> region_add().  In the normal case, we want vma_commit_reservation
>> to return the same value as the preceding call to vma_needs_reservation.
>> Create a common __vma_reservation_common routine to help keep the
>> special case return values in sync
>>
>> Signed-off-by: Mike Kravetz <mike.kravetz@oracle.com>
>> ---
>>   mm/hugetlb.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++-------------
>>   1 file changed, 94 insertions(+), 26 deletions(-)
>>
>> diff --git a/mm/hugetlb.c b/mm/hugetlb.c
>> index 54f129d..3855889 100644
>> --- a/mm/hugetlb.c
>> +++ b/mm/hugetlb.c
>> @@ -212,8 +212,16 @@ static inline struct hugepage_subpool *subpool_vma(struct vm_area_struct *vma)
>>    * Region tracking -- allows tracking of reservations and instantiated pages
>>    *                    across the pages in a mapping.
>>    *
>> - * The region data structures are embedded into a resv_map and
>> - * protected by a resv_map's lock
>> + * The region data structures are embedded into a resv_map and protected
>> + * by a resv_map's lock.  The set of regions within the resv_map represent
>> + * reservations for huge pages, or huge pages that have already been
>> + * instantiated within the map.
> 
>>   The from and to elements are huge page
>> + * indicies into the associated mapping.  from indicates the starting index
>> + * of the region.  to represents the first index past the end of  the region.
>> + * For example, a file region structure with from == 0 and to == 4 represents
>> + * four huge pages in a mapping.  It is important to note that the to element
>> + * represents the first element past the end of the region. This is used in
>> + * arithmetic as 4(to) - 0(from) = 4 huge pages in the region.
> 
> How about just saying "[from, to)", which implies "from" is inclusive and "to"
> is exclusive. I hope this mathematical notation is widely accepted among kernel
> developers.

OK, I'll add the mathematical notation.  But, I think the more explicit
description and example might help those who would not recognize the
notation.

>>    */
>>   struct file_region {
>>   	struct list_head link;
>> @@ -221,10 +229,23 @@ struct file_region {
>>   	long to;
>>   };
>>   
>> +/*
>> + * Add the huge page range represented by indicies f (from)
>> + * and t (to) to the reserve map.  Existing regions will be
>> + * expanded to accommodate the specified range.  We know only
>> + * existing regions need to be expanded, because region_add
>> + * is only called after region_chg(with the same range).  If
>> + * a new file_region structure must be allocated, it is done
>> + * in region_chg.
>> + *
>> + * Return the number of new huge pages added to the map.  This
>> + * number is greater than or equal to zero.
>> + */
>>   static long region_add(struct resv_map *resv, long f, long t)
>>   {
>>   	struct list_head *head = &resv->regions;
>>   	struct file_region *rg, *nrg, *trg;
>> +	long add = 0;
>>   
>>   	spin_lock(&resv->lock);
>>   	/* Locate the region we are either in or before. */
>> @@ -250,16 +271,44 @@ static long region_add(struct resv_map *resv, long f, long t)
>>   		if (rg->to > t)
>>   			t = rg->to;
>>   		if (rg != nrg) {
>> +			/* Decrement return value by the deleted range.
>> +			 * Another range will span this area so that by
>> +			 * end of routine add will be >= zero
>> +			 */
>> +			add -= (rg->to - rg->from);
> 
> I can't say how, but if file_region data were broken for some reason (mainly
> due to bug,) this could return negative value, so how about asserting add >=0
> with VM_BUG_ON() at the end of this function?
> 

Sure, that should not be a problem.

>>   			list_del(&rg->link);
>>   			kfree(rg);
>>   		}
>>   	}
>> +
>> +	add += (nrg->from - f);		/* Added to beginning of region */
>>   	nrg->from = f;
>> +	add += t - nrg->to;		/* Added to end of region */
>>   	nrg->to = t;
>> +
>>   	spin_unlock(&resv->lock);
>> -	return 0;
>> +	return add;
>>   }
>>   
>> +/*
>> + * Examine the existing reserve map and determine how many
>> + * huge pages in the specified range (f, t) are NOT currently
> 
> "[f, t)" would be better.
> 

Yes, my plan is to use the mathematical notation throughout with a
more detailed explanation the first time it is used.

>> + * represented.  This routine is called before a subsequent
>> + * call to region_add that will actually modify the reserve
>> + * map to add the specified range (f, t).  region_chg does
>> + * not change the number of huge pages represented by the
>> + * map.  However, if the existing regions in the map can not
>> + * be expanded to represent the new range, a new file_region
>> + * structure is added to the map as a placeholder.  This is
>> + * so that the subsequent region_add call will have all
>> + * regions it needs and will not fail.
>> + *
>> + * Returns the number of huge pages that need to be added
>> + * to the existing reservation map for the range (f, t).
>> + * This number is greater or equal to zero.  -ENOMEM is
>> + * returned if a new  file_region structure can not be
>> + * allocated.
>> + */
>>   static long region_chg(struct resv_map *resv, long f, long t)
>>   {
>>   	struct list_head *head = &resv->regions;
>> @@ -326,6 +375,11 @@ out_nrg:
>>   	return chg;
>>   }
>>   
>> +/*
>> + * Truncate the reserve map at index 'end'.  Modify/truncate any
>> + * region which contains end.  Delete any regions past end.
>> + * Return the number of huge pages removed from the map.
>> + */
>>   static long region_truncate(struct resv_map *resv, long end)
>>   {
>>   	struct list_head *head = &resv->regions;
>> @@ -361,6 +415,10 @@ out:
>>   	return chg;
>>   }
>>   
>> +/*
>> + * Count and return the number of huge pages in the reserve map
>> + * that intersect with the range (f, t).
>> + */
>>   static long region_count(struct resv_map *resv, long f, long t)
>>   {
>>   	struct list_head *head = &resv->regions;
>> @@ -1424,46 +1482,56 @@ static void return_unused_surplus_pages(struct hstate *h,
>>   }
>>   
>>   /*
>> - * Determine if the huge page at addr within the vma has an associated
>> - * reservation.  Where it does not we will need to logically increase
>> - * reservation and actually increase subpool usage before an allocation
>> - * can occur.  Where any new reservation would be required the
>> - * reservation change is prepared, but not committed.  Once the page
>> - * has been allocated from the subpool and instantiated the change should
>> - * be committed via vma_commit_reservation.  No action is required on
>> - * failure.
>> + * vma_needs_reservation and vma_commit_reservation are used by the huge
>> + * page allocation routines to manage reservations.
>> + *
>> + * vma_needs_reservation is called to determine if the huge page at addr
>> + * within the vma has an associated reservation.  If a reservation is
>> + * needed, the value 1 is returned.  The caller is then responsible for
>> + * managing the global reservation and subpool usage counts.  After
>> + * the huge page has been allocated, vma_commit_reservation is called
>> + * to add the page to the reservation map.
>> + *
>> + * In the normal case, vma_commit_reservation should return the same value
>> + * as the preceding vma_needs_reservation call.  The only time this is
>> + * not the case is if a reserve map was changed between calls.  It is the
>> + * responsibility of the caller to notice the difference and take appropriate
>> + * action.
>>    */
>> -static long vma_needs_reservation(struct hstate *h,
>> -			struct vm_area_struct *vma, unsigned long addr)
>> +static long __vma_reservation_common(struct hstate *h,
>> +				struct vm_area_struct *vma, unsigned long addr,
>> +				bool needs)
>>   {
>>   	struct resv_map *resv;
>>   	pgoff_t idx;
>> -	long chg;
>> +	long ret;
>>   
>>   	resv = vma_resv_map(vma);
>>   	if (!resv)
>>   		return 1;
>>   
>>   	idx = vma_hugecache_offset(h, vma, addr);
>> -	chg = region_chg(resv, idx, idx + 1);
>> +	if (needs)
>> +		ret = region_chg(resv, idx, idx + 1);
>> +	else
>> +		ret = region_add(resv, idx, idx + 1);
> 
> This code sharing is OK, but the name "needs" looks a bit unclear to me.
> I feel that it's more readable if we name "commit" (or "commits") to the bool
> parameter and call region_add() if "commit" is true.
> 

Agree.  And Davidlor suggested renaming "needs" in the routine name
to prepare.  If renamed prepare, I think it would more clear.

>>   
>>   	if (vma->vm_flags & VM_MAYSHARE)
>> -		return chg;
>> +		return ret;
>>   	else
>> -		return chg < 0 ? chg : 0;
>> +		return ret < 0 ? ret : 0;
>>   }
>> -static void vma_commit_reservation(struct hstate *h,
>> +
>> +static long vma_needs_reservation(struct hstate *h,
>>   			struct vm_area_struct *vma, unsigned long addr)
>>   {
>> -	struct resv_map *resv;
>> -	pgoff_t idx;
>> -
>> -	resv = vma_resv_map(vma);
>> -	if (!resv)
>> -		return;
>> +	return __vma_reservation_common(h, vma, addr, (bool)1);
> 
> You can simply use literal "true"?

Yes.

Thank you for the review and comments.
-- 
Mike Kravetz

> 
> Thanks,
> Naoya Horiguchi
> 
>> +}
>>   
>> -	idx = vma_hugecache_offset(h, vma, addr);
>> -	region_add(resv, idx, idx + 1);
>> +static long vma_commit_reservation(struct hstate *h,
>> +			struct vm_area_struct *vma, unsigned long addr)
>> +{
>> +	return __vma_reservation_common(h, vma, addr, (bool)0);
>>   }
>>   
>>   static struct page *alloc_huge_page(struct vm_area_struct *vma,
>> -- 
>> 2.1.0

Re: [PATCH v2 0/2] alloc_huge_page/hugetlb_reserve_pages race

[Mike Kravetz]

On 05/25/2015 12:58 PM, Davidlohr Bueso wrote:
> On Fri, 2015-05-22 at 20:55 -0700, Mike Kravetz wrote:
>> This updated patch set includes new documentation for the region/
>> reserve map routines.  Since I am not the original author of this
>> code, comments would be appreciated.
>>
>> While working on hugetlbfs fallocate support, I noticed the following
>> race in the existing code.  It is unlikely that this race is hit very
>> often in the current code.
>
> Have you actually run into this issue? Can you produce a testcase?

I have not hit this with the current code.  However, the race is as
you describe below.  So, from code examination it is pretty easy to
see.

I have hit this with fallocate testing.  Note that this is a race with
the fault code which instantiates a page and mmap.  In the existing
code, you can only fault in/instantiate a page at a specific virtual
address once.  Therefore, there are a finite number of races possible
for each VMA.  With fallocate, you can hole punch to release the page
and then fault another back in.  My stress testing has this hole punch
then fault sequence happening in several processes while others are
doing mmap/munmap.

I suspect it would also be easy to recreate on a big system with
something like a TB of huge pages.  One process could just fault
in the TB of huge pages while the other mmap/unmap.

>>    However, if more functionality to add and
>> remove pages to hugetlbfs mappings (such as fallocate) is added the
>> likelihood of hitting this race will increase.
>>
>> alloc_huge_page and hugetlb_reserve_pages use information from the
>> reserve map to determine if there are enough available huge pages to
>> complete the operation, as well as adjust global reserve and subpool
>> usage counts.  The order of operations is as follows:
>> - call region_chg() to determine the expected change based on reserve map
>> - determine if enough resources are available for this operation
>> - adjust global counts based on the expected change
>> - call region_add() to update the reserve map
>> The issue is that reserve map could change between the call to region_chg
>> and region_add.  In this case, the counters which were adjusted based on
>> the output of region_chg will not be correct.
>>
>> In order to hit this race today, there must be an existing shared hugetlb
>> mmap created with the MAP_NORESERVE flag.  A page fault to allocate a huge
>> page via this mapping must occur at the same another task is mapping the
>> same region without the MAP_NORESERVE flag.
>
> In the past file regions were serialized by either mmap_sem (exclusive)
> or the hugetlb instantiation mutex (when mmap_sem was shared). With
> finer grained locking, however, we now rely on the resv_map->lock. So I
> guess you are referring to something like this, no?
>
> CPU0 (via vma_[needs/commit]_reservation)  CPU1
> hugetlb_fault				
>    mutex_lock(hash_A)			
>    hugetlb_no_page			
>      alloc_huge_page			shm_get
>         region_chg			  hugetlb_file_setup
>         <accounting updates>		    hugetlb_reserve_pages
> 					      region_chg
>         region_add			      <accounting updates>
> 					      region_add

Yes, that is exactly what I am referring to.  The issue is that the
accounting updates are based on the return value of region_chg.

> Couldn't this race also occur upon concurrent faults on two different
> hashes backed by the same vma?

I do not think we will race in this case.  Two different hashes,
implies two different virtual addresses (mapping index, huge pages).
In this case, the ranges passed to region_chg/region_add will not
intersect.  The race only happens when there is an intersection
of the ranges.

> Anyway, it's memorial day, so I'll take a closer look during the week,
> but you seem to be correct. An alternative could be to continue holding
> the spinlock until the after region_add, but I like your "fixup"
> approach.
>
>> The patch set does not prevent the race from happening.  Rather, it adds
>> simple functionality to detect when the race has occurred.  If a race is
>> detected, then the incorrect counts are adjusted.
>>
>> v2:
>>    Added documentation for the region/reserve map routines
>
> Thanks for doing this, as akpm mentioned, it is much needed. However,
> this should be a new, separate patch.

OK, I can break that out.

>>    Created common routine for vma_commit_reservation and
>>      vma_commit_reservation to help prevent them from drifting
>>      apart in the future.
>>
>> Mike Kravetz (2):
>>    mm/hugetlb: compute/return the number of regions added by region_add()
>>    mm/hugetlb: handle races in alloc_huge_page and hugetlb_reserve_pages
>
> Ah, so these two patches are duplicates from your fallocate series,
> right? You should drop those from that patchset then, as bugfixes should
> be separate.

Yes, I will drop them from future versions of fallocate patch set.

> Could you rename patch 2 to something more meaningful? ie:
>
> mm/hugetlb: account for races between region_chg and region_add

Sure.  I'm not sure if I like that name as region_chg and region_add
are not really racing IMO.  Rather, it is the callers of those
routines which expect the reserve map not to change between region_chg
and region_add.

> Also, gosh those function names are nasty and unclear -- I would change
> them to region_prepare and region_commit, or something like that where
> the purpose is more obvious.

Let me think about this.  After staring at the code for several days
the names sort of make sense to me.  However, you are correct in that
they may not make much sense when first looking at the code.

Thanks for the review and all the comments.
-- 
Mike Kravetz

>
> Thanks,
> Davidlohr
>

Re: [PATCH v2 1/2] mm/hugetlb: compute/return the number of regions added by region_add()

[Mike Kravetz]

On 05/25/2015 01:29 PM, Davidlohr Bueso wrote:
> On Fri, 2015-05-22 at 20:55 -0700, Mike Kravetz wrote:
>> +/*
>> + * Add the huge page range represented by indicies f (from)
>> + * and t (to) to the reserve map.  Existing regions will be
>
> How about simply renaming those parameters to from and to across the
> entire hugetlb code.
>
> Thanks,
> Davidlohr

After adding the notation suggested by Naoya Horiguchi and cleaning
up that specific comment, I think using f and t is OK.  See the
documentation only patch:

[PATCH] mm/hugetlb: document the reserve map/region tracking routines

-- 
Mike Kravetz