[PATCH] mm: __nr_to_section - make it safe against overflow

[PATCH] mm: __nr_to_section - make it safe against overflow

[Cyrill Gorcunov]

__nr_to_section should check for array bound overflow.
We should better get NULL dereference then silently
pass some memory snippet out of bounds to a caller.

Also add a comment about mem_section structure.

Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
---

Please review. Some __nr_to_section callers don't check
for NULL returned so this patch could be a bit dangerous
but should reveal the problems eventually.

 include/linux/mmzone.h |   13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

Index: linux-2.6.git/include/linux/mmzone.h
===================================================================
--- linux-2.6.git.orig/include/linux/mmzone.h
+++ linux-2.6.git/include/linux/mmzone.h
@@ -935,6 +935,12 @@ static inline unsigned long early_pfn_to
 
 struct page;
 struct page_cgroup;
+
+/*
+ * NOTE: sizeof(struct mem_section) _must_ be power of 2
+ * otherwise SECTION_ROOT_MASK will be broken so be
+ * really cautious while modifying this structure
+ */
 struct mem_section {
 	/*
 	 * This is, logically, a pointer to an array of struct
@@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
 
 static inline struct mem_section *__nr_to_section(unsigned long nr)
 {
-	if (!mem_section[SECTION_NR_TO_ROOT(nr)])
+	unsigned long idx = SECTION_NR_TO_ROOT(nr);
+	WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
+
+	if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
 		return NULL;
-	return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
+	return &mem_section[idx][nr & SECTION_ROOT_MASK];
 }
 extern int __section_nr(struct mem_section* ms);
 extern unsigned long usemap_size(void);

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Pekka Enberg]

Hi Cyrill,

On Mon, Jan 5, 2009 at 11:40 AM, Cyrill Gorcunov <gorcunov@gmail.com> wrote:
> @@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
>
>  static inline struct mem_section *__nr_to_section(unsigned long nr)
>  {
> -       if (!mem_section[SECTION_NR_TO_ROOT(nr)])
> +       unsigned long idx = SECTION_NR_TO_ROOT(nr);
> +       WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
> +
> +       if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
>                return NULL;

Looks good to me but I have minor nitpick. You might want to write the
above like this:

    if (WARN_ON_ONCE(idx >= NR_SECTION_ROOTS))
            return NULL;

to separate the error condition from the normal case where we don't
have a mem section.

> -       return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
> +       return &mem_section[idx][nr & SECTION_ROOT_MASK];
>  }

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Cyrill Gorcunov]

[Pekka Enberg - Mon, Jan 05, 2009 at 12:00:58PM +0200]
| Hi Cyrill,
| 
| On Mon, Jan 5, 2009 at 11:40 AM, Cyrill Gorcunov <gorcunov@gmail.com> wrote:
| > @@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
| >
| >  static inline struct mem_section *__nr_to_section(unsigned long nr)
| >  {
| > -       if (!mem_section[SECTION_NR_TO_ROOT(nr)])
| > +       unsigned long idx = SECTION_NR_TO_ROOT(nr);
| > +       WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
| > +
| > +       if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
| >                return NULL;
| 
| Looks good to me but I have minor nitpick. You might want to write the
| above like this:
| 
|     if (WARN_ON_ONCE(idx >= NR_SECTION_ROOTS))
|             return NULL;
| 
| to separate the error condition from the normal case where we don't
| have a mem section.
| 
| > -       return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
| > +       return &mem_section[idx][nr & SECTION_ROOT_MASK];
| >  }
| 

Hi Pekka,

thanks, indeed! I forget that WARN_.. do return a value :)
Will fix shortly.

		- Cyrill -

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Cyrill Gorcunov]

[Cyrill Gorcunov - Mon, Jan 05, 2009 at 12:40:34PM +0300]
| __nr_to_section should check for array bound overflow.
| We should better get NULL dereference then silently
| pass some memory snippet out of bounds to a caller.
| 
| Also add a comment about mem_section structure.
| 
| Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
| ---
| 
| Please review. Some __nr_to_section callers don't check
| for NULL returned so this patch could be a bit dangerous
| but should reveal the problems eventually.
|
...

Populating WARN_ON_ONCE by inline is not good. Fixed.

		- Cyrill -
---

[PATCH] mm: __nr_to_section - make it safe against overflow

__nr_to_section should check for array bound overflow.
We should better get NULL dereference then silently
pass some memory snippet out of bounds to a caller.

Also add a comment about mem_section structure.

Signed-off-by: Cyrill Gorcunov <gorcunov@openvz.org>
---
 include/linux/mmzone.h |   14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

Index: linux-2.6.git/include/linux/mmzone.h
===================================================================
--- linux-2.6.git.orig/include/linux/mmzone.h
+++ linux-2.6.git/include/linux/mmzone.h
@@ -935,6 +935,12 @@ static inline unsigned long early_pfn_to
 
 struct page;
 struct page_cgroup;
+
+/*
+ * NOTE: sizeof(struct mem_section) _must_ be power of 2
+ * otherwise SECTION_ROOT_MASK will be broken so be
+ * really cautious while modifying this structure
+ */
 struct mem_section {
 	/*
 	 * This is, logically, a pointer to an array of struct
@@ -980,9 +986,13 @@ extern struct mem_section mem_section[NR
 
 static inline struct mem_section *__nr_to_section(unsigned long nr)
 {
-	if (!mem_section[SECTION_NR_TO_ROOT(nr)])
+	unsigned long idx = SECTION_NR_TO_ROOT(nr);
+
+	WARN_ON(idx >= NR_SECTION_ROOTS);
+	if (idx >= NR_SECTION_ROOTS || !mem_section[idx])
 		return NULL;
-	return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
+
+	return &mem_section[idx][nr & SECTION_ROOT_MASK];
 }
 extern int __section_nr(struct mem_section* ms);
 extern unsigned long usemap_size(void);

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Christoph Lameter]

On Mon, 5 Jan 2009, Cyrill Gorcunov wrote:

>  	/*
>  	 * This is, logically, a pointer to an array of struct
> @@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
>
>  static inline struct mem_section *__nr_to_section(unsigned long nr)
>  {
> -	if (!mem_section[SECTION_NR_TO_ROOT(nr)])
> +	unsigned long idx = SECTION_NR_TO_ROOT(nr);
> +	WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
> +
> +	if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
>  		return NULL;
> -	return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
> +	return &mem_section[idx][nr & SECTION_ROOT_MASK];
>  }
>  extern int __section_nr(struct mem_section* ms);
>  extern unsigned long usemap_size(void);

Not that you are adding code to numerous hot code path. Plus this is a
frequently used inline. Code size is going to increase if you do this.

I would think that the code does not have the tests because of performance
and code size concerns. Can we just say that a sane nr must be passed to
__nr_section?

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Cyrill Gorcunov]

[Christoph Lameter - Mon, Jan 05, 2009 at 09:10:57AM -0600]
| On Mon, 5 Jan 2009, Cyrill Gorcunov wrote:
| 
| >  	/*
| >  	 * This is, logically, a pointer to an array of struct
| > @@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
| >
| >  static inline struct mem_section *__nr_to_section(unsigned long nr)
| >  {
| > -	if (!mem_section[SECTION_NR_TO_ROOT(nr)])
| > +	unsigned long idx = SECTION_NR_TO_ROOT(nr);
| > +	WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
| > +
| > +	if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
| >  		return NULL;
| > -	return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
| > +	return &mem_section[idx][nr & SECTION_ROOT_MASK];
| >  }
| >  extern int __section_nr(struct mem_section* ms);
| >  extern unsigned long usemap_size(void);
| 
| Not that you are adding code to numerous hot code path. Plus this is a
| frequently used inline. Code size is going to increase if you do this.

yes, I know, that is why I've changed WARN_ON_ONCE to plain WARN_ON.

| 
| I would think that the code does not have the tests because of performance
| and code size concerns. Can we just say that a sane nr must be passed to
| __nr_section?
| 

If you mean did I test this patch for speed regresson then to be fair --
no, I didn't. BUT we have a number of macros wich are self protective
like present_section which is used havily too. On the other hand --
bad argument passed to __nr_to_section will be (and it is now) really
harmfull -- since it would allow to reference a memory outside the
valid bounds. The second -- SECTION_ROOT_MASK wich is fragile, any
attempt to modify mem_section structure will silently lead to insane
referencing, that is why it deserve a comment on top of structure.

Don't know Christoph, if it really that important to not spend a few
cycles here in a sake of safety -- we could easily drop this patch.

		- Cyrill -

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Nick Piggin]

On Mon, Jan 05, 2009 at 06:28:48PM +0300, Cyrill Gorcunov wrote:
> [Christoph Lameter - Mon, Jan 05, 2009 at 09:10:57AM -0600]
> | On Mon, 5 Jan 2009, Cyrill Gorcunov wrote:
> | 
> | >  	/*
> | >  	 * This is, logically, a pointer to an array of struct
> | > @@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
> | >
> | >  static inline struct mem_section *__nr_to_section(unsigned long nr)
> | >  {
> | > -	if (!mem_section[SECTION_NR_TO_ROOT(nr)])
> | > +	unsigned long idx = SECTION_NR_TO_ROOT(nr);
> | > +	WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
> | > +
> | > +	if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
> | >  		return NULL;
> | > -	return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
> | > +	return &mem_section[idx][nr & SECTION_ROOT_MASK];
> | >  }
> | >  extern int __section_nr(struct mem_section* ms);
> | >  extern unsigned long usemap_size(void);
> | 
> | Not that you are adding code to numerous hot code path. Plus this is a
> | frequently used inline. Code size is going to increase if you do this.
> 
> yes, I know, that is why I've changed WARN_ON_ONCE to plain WARN_ON.

Still costs. Putting it under a config option would be nice.


> | I would think that the code does not have the tests because of performance
> | and code size concerns. Can we just say that a sane nr must be passed to
> | __nr_section?
> | 
> 
> If you mean did I test this patch for speed regresson then to be fair --
> no, I didn't. BUT we have a number of macros wich are self protective
> like present_section which is used havily too. On the other hand --
> bad argument passed to __nr_to_section will be (and it is now) really
> harmfull -- since it would allow to reference a memory outside the
> valid bounds. The second -- SECTION_ROOT_MASK wich is fragile, any
> attempt to modify mem_section structure will silently lead to insane
> referencing, that is why it deserve a comment on top of structure.
> 
> Don't know Christoph, if it really that important to not spend a few
> cycles here in a sake of safety -- we could easily drop this patch.

The problem with testing every little slowdown for a speed regression
is that they are just going to be in the noise. But we *know* it will
go slower. The problem is that they add up. We just have to be sensible
about it.

Has there ever been a problem here before? Has it been a problem during
development? (in which case putting it in a .config option might make
sense).

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Cyrill Gorcunov]

[Nick Piggin - Mon, Jan 05, 2009 at 04:34:06PM +0100]
| On Mon, Jan 05, 2009 at 06:28:48PM +0300, Cyrill Gorcunov wrote:
| > [Christoph Lameter - Mon, Jan 05, 2009 at 09:10:57AM -0600]
| > | On Mon, 5 Jan 2009, Cyrill Gorcunov wrote:
| > | 
| > | >  	/*
| > | >  	 * This is, logically, a pointer to an array of struct
| > | > @@ -980,9 +986,12 @@ extern struct mem_section mem_section[NR
| > | >
| > | >  static inline struct mem_section *__nr_to_section(unsigned long nr)
| > | >  {
| > | > -	if (!mem_section[SECTION_NR_TO_ROOT(nr)])
| > | > +	unsigned long idx = SECTION_NR_TO_ROOT(nr);
| > | > +	WARN_ON_ONCE(idx >= NR_SECTION_ROOTS);
| > | > +
| > | > +	if (idx >=NR_SECTION_ROOTS || !mem_section[idx])
| > | >  		return NULL;
| > | > -	return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
| > | > +	return &mem_section[idx][nr & SECTION_ROOT_MASK];
| > | >  }
| > | >  extern int __section_nr(struct mem_section* ms);
| > | >  extern unsigned long usemap_size(void);
| > | 
| > | Not that you are adding code to numerous hot code path. Plus this is a
| > | frequently used inline. Code size is going to increase if you do this.
| > 
| > yes, I know, that is why I've changed WARN_ON_ONCE to plain WARN_ON.
| 
| Still costs. Putting it under a config option would be nice.
| 
| 
| > | I would think that the code does not have the tests because of performance
| > | and code size concerns. Can we just say that a sane nr must be passed to
| > | __nr_section?
| > | 
| > 
| > If you mean did I test this patch for speed regresson then to be fair --
| > no, I didn't. BUT we have a number of macros wich are self protective
| > like present_section which is used havily too. On the other hand --
| > bad argument passed to __nr_to_section will be (and it is now) really
| > harmfull -- since it would allow to reference a memory outside the
| > valid bounds. The second -- SECTION_ROOT_MASK wich is fragile, any
| > attempt to modify mem_section structure will silently lead to insane
| > referencing, that is why it deserve a comment on top of structure.
| > 
| > Don't know Christoph, if it really that important to not spend a few
| > cycles here in a sake of safety -- we could easily drop this patch.
| 
| The problem with testing every little slowdown for a speed regression
| is that they are just going to be in the noise. But we *know* it will
| go slower. The problem is that they add up. We just have to be sensible
| about it.
| 
| Has there ever been a problem here before? Has it been a problem during
| development? (in which case putting it in a .config option might make
| sense).
| 

After checking all 'for' and 'against' -- I think I just overzealous
about it. Please drop it. (the case I was concerning to actually protected
by present_section macro anyway). Sorry for noise.

		- Cyrill -

Re: [PATCH] mm: __nr_to_section - make it safe against overflow

[Christoph Lameter]

On Mon, 5 Jan 2009, Cyrill Gorcunov wrote:

> yes, I know, that is why I've changed WARN_ON_ONCE to plain WARN_ON.

This is still going to create a gazillion of checks in the code because it
will be expanded numerous times.

> | I would think that the code does not have the tests because of performance
> | and code size concerns. Can we just say that a sane nr must be passed to
> | __nr_section?
> |
>
> If you mean did I test this patch for speed regresson then to be fair --
> no, I didn't. BUT we have a number of macros wich are self protective
> like present_section which is used havily too. On the other hand --
> bad argument passed to __nr_to_section will be (and it is now) really
> harmfull -- since it would allow to reference a memory outside the
> valid bounds. The second -- SECTION_ROOT_MASK wich is fragile, any
> attempt to modify mem_section structure will silently lead to insane
> referencing, that is why it deserve a comment on top of structure.
>
> Don't know Christoph, if it really that important to not spend a few
> cycles here in a sake of safety -- we could easily drop this patch.

The problem is that these few cycles aggregate. Both because these inline
primitives are frequently used and because developers add more of these
checks over time.