[PATCH v2] MM: check limit while deallocating bootmem node

[PATCH v2] MM: check limit while deallocating bootmem node

[Gavin Shan]

For the particular bootmem node, the minimal and maximal PFN (
Page Frame Number) have been traced in the instance of "struct
bootmem_data_t". On current implementation, the maximal PFN isn't
checked while deallocating a bunch (BITS_PER_LONG) of page frames.
So the current implementation won't work if the maximal PFN isn't
aligned with BITS_PER_LONG.

The patch will check the maximal PFN of the given bootmem node.
Also, we needn't check all the bits map when the starting PFN isn't
BITS_PER_LONG aligned. Actually, we should start from the offset
of the bits map, which indicated by the starting PFN. By the way,
V2 patch removed the duplicate check according to comments from
Johannes Weiner.

Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
---
 mm/bootmem.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/mm/bootmem.c b/mm/bootmem.c
index 5a04536..b4f3ba5 100644
--- a/mm/bootmem.c
+++ b/mm/bootmem.c
@@ -201,9 +201,11 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
 			count += BITS_PER_LONG;
 			start += BITS_PER_LONG;
 		} else {
-			unsigned long off = 0;
+			unsigned long cursor = start;
+			unsigned long off = cursor & (BITS_PER_LONG - 1);
 
-			while (vec && off < BITS_PER_LONG) {
+			vec >>= off;
+			while (vec) {
 				if (vec & 1) {
 					page = pfn_to_page(start + off);
 					__free_pages_bootmem(page, 0);
@@ -211,6 +213,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
 				}
 				vec >>= 1;
 				off++;
+				cursor++;
 			}
 			start = ALIGN(start + 1, BITS_PER_LONG);
 		}
-- 
1.7.5.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2] MM: check limit while deallocating bootmem node

[Johannes Weiner]

On Thu, May 03, 2012 at 09:31:14AM +0800, Gavin Shan wrote:
> For the particular bootmem node, the minimal and maximal PFN (
> Page Frame Number) have been traced in the instance of "struct
> bootmem_data_t". On current implementation, the maximal PFN isn't
> checked while deallocating a bunch (BITS_PER_LONG) of page frames.
> So the current implementation won't work if the maximal PFN isn't
> aligned with BITS_PER_LONG.

That's not true, given how the bitmap works, see my previous mail.

> The patch will check the maximal PFN of the given bootmem node.
> Also, we needn't check all the bits map when the starting PFN isn't
> BITS_PER_LONG aligned.

Actually, it's musn't.  I just realized that this code is totally
buggy :(

vec is an aligned chunk of memory that start is pointing into.  If
start is not aligned, we check the bitmap at the wrong offset
throughout the loop.

Your skipping the unaligned bits is not an optimization, it's a
bugfix.

> Actually, we should start from the offset
> of the bits map, which indicated by the starting PFN. By the way,
> V2 patch removed the duplicate check according to comments from
> Johannes Weiner.
> 
> Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
> ---
>  mm/bootmem.c |    7 +++++--
>  1 files changed, 5 insertions(+), 2 deletions(-)
> 
> diff --git a/mm/bootmem.c b/mm/bootmem.c
> index 5a04536..b4f3ba5 100644
> --- a/mm/bootmem.c
> +++ b/mm/bootmem.c
> @@ -201,9 +201,11 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
>  			count += BITS_PER_LONG;
>  			start += BITS_PER_LONG;
>  		} else {
> -			unsigned long off = 0;
> +			unsigned long cursor = start;
> +			unsigned long off = cursor & (BITS_PER_LONG - 1);
>  
> -			while (vec && off < BITS_PER_LONG) {
> +			vec >>= off;
> +			while (vec) {
>  				if (vec & 1) {
>  					page = pfn_to_page(start + off);

I don't understand this.

start + (start & (BITS_PER_LONG - 1)) ?

>  					__free_pages_bootmem(page, 0);
> @@ -211,6 +213,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
>  				}
>  				vec >>= 1;
>  				off++;
> +				cursor++;

cursor is not really used anywhere.

>  			start = ALIGN(start + 1, BITS_PER_LONG);
>  		}
> -- 

I think all we need to add is

	vec >>= start & (BITS_PER_LONG - 1);

before the loop, and call the patch a bugfix rather than an
optimization.

And removing the off < BITS_PER_LONG check should probably be a
separate change with its own explanation then, to not have unrelated
cleanup and error potential in a bugfix patch.

How about this:

---
From: Gavin Shan <shangw@linux.vnet.ibm.com>
Subject: [patch 1/2] mm: bootmem: fix checking the bitmap when finally
 freeing bootmem

When bootmem releases an unaligned chunk of memory at the beginning of
a node to the page allocator, it iterates from that unaligned PFN but
checks an aligned word of the page bitmap.  The checked bits do not
correspond to the PFNs and, as a result, reserved pages can be freed.

Properly shift the bitmap word so that the lowest bit corresponds to
the starting PFN before entering the freeing loop.

Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
---
 mm/bootmem.c |    1 +
 1 file changed, 1 insertion(+)

diff --git a/mm/bootmem.c b/mm/bootmem.c
index 0131170..67872fc 100644
--- a/mm/bootmem.c
+++ b/mm/bootmem.c
@@ -203,6 +203,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
 		} else {
 			unsigned long off = 0;
 
+			vec >>= start & (BITS_PER_LONG - 1);
 			while (vec && off < BITS_PER_LONG) {
 				if (vec & 1) {
 					page = pfn_to_page(start + off);
-- 
1.7.10

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2] MM: check limit while deallocating bootmem node

[Gavin Shan]

>> For the particular bootmem node, the minimal and maximal PFN (
>> Page Frame Number) have been traced in the instance of "struct
>> bootmem_data_t". On current implementation, the maximal PFN isn't
>> checked while deallocating a bunch (BITS_PER_LONG) of page frames.
>> So the current implementation won't work if the maximal PFN isn't
>> aligned with BITS_PER_LONG.
>
>That's not true, given how the bitmap works, see my previous mail.
>
>> The patch will check the maximal PFN of the given bootmem node.
>> Also, we needn't check all the bits map when the starting PFN isn't
>> BITS_PER_LONG aligned.
>
>Actually, it's musn't.  I just realized that this code is totally
>buggy :(
>
>vec is an aligned chunk of memory that start is pointing into.  If
>start is not aligned, we check the bitmap at the wrong offset
>throughout the loop.
>
>Your skipping the unaligned bits is not an optimization, it's a
>bugfix.
>
>> Actually, we should start from the offset
>> of the bits map, which indicated by the starting PFN. By the way,
>> V2 patch removed the duplicate check according to comments from
>> Johannes Weiner.
>> 
>> Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
>> ---
>>  mm/bootmem.c |    7 +++++--
>>  1 files changed, 5 insertions(+), 2 deletions(-)
>> 
>> diff --git a/mm/bootmem.c b/mm/bootmem.c
>> index 5a04536..b4f3ba5 100644
>> --- a/mm/bootmem.c
>> +++ b/mm/bootmem.c
>> @@ -201,9 +201,11 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
>>  			count += BITS_PER_LONG;
>>  			start += BITS_PER_LONG;
>>  		} else {
>> -			unsigned long off = 0;
>> +			unsigned long cursor = start;
>> +			unsigned long off = cursor & (BITS_PER_LONG - 1);
>>  
>> -			while (vec && off < BITS_PER_LONG) {
>> +			vec >>= off;
>> +			while (vec) {
>>  				if (vec & 1) {
>>  					page = pfn_to_page(start + off);
>
>I don't understand this.
>
>start + (start & (BITS_PER_LONG - 1)) ?
>

Yeah, It has calculated the PFN wrongly here. Actually, "cursor"
should be used here.

>>  					__free_pages_bootmem(page, 0);
>> @@ -211,6 +213,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
>>  				}
>>  				vec >>= 1;
>>  				off++;
>> +				cursor++;
>
>cursor is not really used anywhere.
>
>>  			start = ALIGN(start + 1, BITS_PER_LONG);
>>  		}
>> -- 
>
>I think all we need to add is
>
>	vec >>= start & (BITS_PER_LONG - 1);
>
>before the loop, and call the patch a bugfix rather than an
>optimization.
>
>And removing the off < BITS_PER_LONG check should probably be a
>separate change with its own explanation then, to not have unrelated
>cleanup and error potential in a bugfix patch.
>
>How about this:
>
>---
>From: Gavin Shan <shangw@linux.vnet.ibm.com>
>Subject: [patch 1/2] mm: bootmem: fix checking the bitmap when finally
> freeing bootmem
>
>When bootmem releases an unaligned chunk of memory at the beginning of
>a node to the page allocator, it iterates from that unaligned PFN but
>checks an aligned word of the page bitmap.  The checked bits do not
>correspond to the PFNs and, as a result, reserved pages can be freed.
>
>Properly shift the bitmap word so that the lowest bit corresponds to
>the starting PFN before entering the freeing loop.
>

Thanks for changing it correctly, Johannes ;-)

>Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
>Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
>---
> mm/bootmem.c |    1 +
> 1 file changed, 1 insertion(+)
>
>diff --git a/mm/bootmem.c b/mm/bootmem.c
>index 0131170..67872fc 100644
>--- a/mm/bootmem.c
>+++ b/mm/bootmem.c
>@@ -203,6 +203,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
> 		} else {
> 			unsigned long off = 0;
>
>+			vec >>= start & (BITS_PER_LONG - 1);
> 			while (vec && off < BITS_PER_LONG) {

I think it can be changed to "while (vec) {" since it's duplicate
check. "vec" has no chance to have more bits than BITS_PER_LONG here.

Others look good. Need I change it accordingly and send it out
again?

> 				if (vec & 1) {
> 					page = pfn_to_page(start + off);

Thanks,
Gavin

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2] MM: check limit while deallocating bootmem node

[Johannes Weiner]

On Thu, May 03, 2012 at 04:35:06PM +0800, Gavin Shan wrote:
> >From: Gavin Shan <shangw@linux.vnet.ibm.com>
> >Subject: [patch 1/2] mm: bootmem: fix checking the bitmap when finally
> > freeing bootmem
> >
> >When bootmem releases an unaligned chunk of memory at the beginning of
> >a node to the page allocator, it iterates from that unaligned PFN but
> >checks an aligned word of the page bitmap.  The checked bits do not
> >correspond to the PFNs and, as a result, reserved pages can be freed.
> >
> >Properly shift the bitmap word so that the lowest bit corresponds to
> >the starting PFN before entering the freeing loop.
> >
> 
> Thanks for changing it correctly, Johannes ;-)
> 
> >Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
> >Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
> >---
> > mm/bootmem.c |    1 +
> > 1 file changed, 1 insertion(+)
> >
> >diff --git a/mm/bootmem.c b/mm/bootmem.c
> >index 0131170..67872fc 100644
> >--- a/mm/bootmem.c
> >+++ b/mm/bootmem.c
> >@@ -203,6 +203,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
> > 		} else {
> > 			unsigned long off = 0;
> >
> >+			vec >>= start & (BITS_PER_LONG - 1);
> > 			while (vec && off < BITS_PER_LONG) {
> 
> I think it can be changed to "while (vec) {" since it's duplicate
> check. "vec" has no chance to have more bits than BITS_PER_LONG here.

Yes, I think it should be removed too, but as a separate patch.  It's
an unrelated cleanup, better to keep it out of the bugfix change.

> Others look good. Need I change it accordingly and send it out
> again?

It doesn't really matter who sends the patches, your original
authorship is preserved (see the From: in the patch header).  If you
don't have any objections, I'll send both patches to Andrew later.

Here is 2/2, btw:

---
From: Johannes Weiner <hannes@cmpxchg.org>
Subject: [patch 2/2] mm: bootmem: remove redundant offset check when finally
 freeing bootmem

When bootmem releases an unaligned BITS_PER_LONG pages chunk of memory
to the page allocator, it checks the bitmap if there are still
unreserved pages in the chunk (set bits), but also if the offset in
the chunk indicates BITS_PER_LONG loop iterations already.

But since the consulted bitmap is only a one-word-excerpt of the full
per-node bitmap, there can not be more than BITS_PER_LONG bits set in
it.  The additional offset check is unnecessary.

Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
---
 mm/bootmem.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/bootmem.c b/mm/bootmem.c
index 67872fc..053ac3f 100644
--- a/mm/bootmem.c
+++ b/mm/bootmem.c
@@ -204,7 +204,7 @@ static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
 			unsigned long off = 0;
 
 			vec >>= start & (BITS_PER_LONG - 1);
-			while (vec && off < BITS_PER_LONG) {
+			while (vec) {
 				if (vec & 1) {
 					page = pfn_to_page(start + off);
 					__free_pages_bootmem(page, 0);
-- 
1.7.10

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>