[patch 1/3] flex_array: fix get function for elements in base starting at non-zero

[patch 1/3] flex_array: fix get function for elements in base starting at non-zero

[David Rientjes]

If all array elements fit into the base structure and data is copied
using flex_array_put() starting at a non-zero index, flex_array_get()
will fail to return the data.

This fixes the bug by only checking for NULL parts when all elements do
not fit in the base structure when flex_array_get() is used.  Otherwise,
fa_element_to_part_nr() will always be 0 since there are no parts
structures needed and such element may never have been put.  Thus, it
will remain NULL due to the kzalloc() of the base.

Additionally, flex_array_put() now only checks for a NULL part when all
elements do not fit in the base structure.  This is otherwise unnecessary
since the base structure is guaranteed to exist (or we would have already
hit a NULL pointer).

Cc: Dave Hansen <dave@linux.vnet.ibm.com>
Signed-off-by: David Rientjes <rientjes@google.com>
---
 lib/flex_array.c |   14 ++++++++------
 1 files changed, 8 insertions(+), 6 deletions(-)

diff --git a/lib/flex_array.c b/lib/flex_array.c
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -198,10 +198,11 @@ int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags
 		return -ENOSPC;
 	if (elements_fit_in_base(fa))
 		part = (struct flex_array_part *)&fa->parts[0];
-	else
+	else {
 		part = __fa_get_part(fa, part_nr, flags);
-	if (!part)
-		return -ENOMEM;
+		if (!part)
+			return -ENOMEM;
+	}
 	dst = &part->elements[index_inside_part(fa, element_nr)];
 	memcpy(dst, src, fa->element_size);
 	return 0;
@@ -257,11 +258,12 @@ void *flex_array_get(struct flex_array *fa, int element_nr)
 
 	if (element_nr >= fa->total_nr_elements)
 		return NULL;
-	if (!fa->parts[part_nr])
-		return NULL;
 	if (elements_fit_in_base(fa))
 		part = (struct flex_array_part *)&fa->parts[0];
-	else
+	else {
 		part = fa->parts[part_nr];
+		if (!part)
+			return NULL;
+	}
 	return &part->elements[index_inside_part(fa, element_nr)];
 }

[patch 2/3] flex_array: fix flex_array_free_parts comment

[David Rientjes]

flex_array_free_parts() does not take `src' or `element_nr' formals, so
remove their respective comments.

Cc: Dave Hansen <dave@linux.vnet.ibm.com>
Signed-off-by: David Rientjes <rientjes@google.com>
---
 lib/flex_array.c |    3 ---
 1 files changed, 0 insertions(+), 3 deletions(-)

diff --git a/lib/flex_array.c b/lib/flex_array.c
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -122,9 +122,6 @@ static int fa_element_to_part_nr(struct flex_array *fa, int element_nr)
 
 /**
  * flex_array_free_parts - just free the second-level pages
- * @src:	address of data to copy into the array
- * @element_nr:	index of the position in which to insert
- * 		the new element.
  *
  * This is to be used in cases where the base 'struct flex_array'
  * has been statically allocated and should not be free.

Re: [patch 2/3] flex_array: fix flex_array_free_parts comment

[Dave Hansen]

On Mon, 2009-08-17 at 16:46 -0700, David Rientjes wrote:
> flex_array_free_parts() does not take `src' or `element_nr' formals, so
> remove their respective comments.
> 
> Cc: Dave Hansen <dave@linux.vnet.ibm.com>
> Signed-off-by: David Rientjes <rientjes@google.com>
> ---
>  lib/flex_array.c |    3 ---
>  1 files changed, 0 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/flex_array.c b/lib/flex_array.c
> --- a/lib/flex_array.c
> +++ b/lib/flex_array.c
> @@ -122,9 +122,6 @@ static int fa_element_to_part_nr(struct flex_array *fa, int element_nr)
> 
>  /**
>   * flex_array_free_parts - just free the second-level pages
> - * @src:	address of data to copy into the array
> - * @element_nr:	index of the position in which to insert
> - * 		the new element.
>   *
>   * This is to be used in cases where the base 'struct flex_array'
>   * has been statically allocated and should not be free.

Looks great to me.

Signed-off-by: Dave Hansen <dave@linux.vnet.ibm.com>

-- Dave

[patch 3/3] flex_array: declare parts member to have incomplete type

[David Rientjes]

The `parts' member of struct flex_array should evaluate to an incomplete
type so that sizeof() cannot be used and C99 does not require the
zero-length specification.

Cc: Dave Hansen <dave@linux.vnet.ibm.com>
Signed-off-by: David Rientjes <rientjes@google.com>
---
 include/linux/flex_array.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
--- a/include/linux/flex_array.h
+++ b/include/linux/flex_array.h
@@ -21,7 +21,7 @@ struct flex_array {
 		struct {
 			int element_size;
 			int total_nr_elements;
-			struct flex_array_part *parts[0];
+			struct flex_array_part *parts[];
 		};
 		/*
 		 * This little trick makes sure that

Re: [patch 3/3] flex_array: declare parts member to have incomplete type

[Dave Hansen]

On Mon, 2009-08-17 at 16:46 -0700, David Rientjes wrote:
> The `parts' member of struct flex_array should evaluate to an incomplete
> type so that sizeof() cannot be used and C99 does not require the
> zero-length specification.
> 
> Cc: Dave Hansen <dave@linux.vnet.ibm.com>
> Signed-off-by: David Rientjes <rientjes@google.com>
> ---
>  include/linux/flex_array.h |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
> --- a/include/linux/flex_array.h
> +++ b/include/linux/flex_array.h
> @@ -21,7 +21,7 @@ struct flex_array {
>  		struct {
>  			int element_size;
>  			int total_nr_elements;
> -			struct flex_array_part *parts[0];
> +			struct flex_array_part *parts[];
>  		};
>  		/*
>  		 * This little trick makes sure that

That's a good little trick.  I don't see any downside to it. 

Signed-off-by: Dave Hansen <dave@linux.vnet.ibm.com>

-- Dave

Re: [patch 1/3] flex_array: fix get function for elements in base starting at non-zero

[Dave Hansen]

On Mon, 2009-08-17 at 16:46 -0700, David Rientjes wrote:
> This fixes the bug by only checking for NULL parts when all elements do
> not fit in the base structure when flex_array_get() is used.  Otherwise,
> fa_element_to_part_nr() will always be 0 since there are no parts
> structures needed and such element may never have been put.  Thus, it
> will remain NULL due to the kzalloc() of the base.

Whew.  That one took me way longer to grok than it should have.  Thanks
for finding this.  Just to be clear, there is only a bug in
flex_array_get(), right?  The flex_array_put() change is completely
separate and is intended to optimize the case where we know the pointer
can't be NULL.

This definitely fixes a bug, but do you mind if we do it a bit
differently?  The compiler should be able to take care of figuring out
when that pointer actually needs to be checked, and I think it looks a
bit nicer as it stands.   

--

When trying to use the 'packed' flex_array format, we take the space
normally used the ->parts[] pointers and instead use it to store user
data.  When doing that, we may have any kind of data in the ->parts[]
pointers that the user puts there.  The user may be storing '\0's there
or whatever else they want.  If they do that (or the data are
uninitialized), we might falsely trigger this NULL check.

This makes sure not to check the contents of the ->parts[] array until
after we've determined that we are not going to use the 'packed' mode.  

---

 linux-2.6.git-dave/lib/flex_array.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff -puN lib/flex_array.c~fa-fixes-0 lib/flex_array.c
--- linux-2.6.git/lib/flex_array.c~fa-fixes-0	2009-08-17 17:02:51.000000000 -0700
+++ linux-2.6.git-dave/lib/flex_array.c	2009-08-17 17:02:51.000000000 -0700
@@ -257,11 +257,11 @@ void *flex_array_get(struct flex_array *
 
 	if (element_nr >= fa->total_nr_elements)
 		return NULL;
-	if (!fa->parts[part_nr])
-		return NULL;
 	if (elements_fit_in_base(fa))
 		part = (struct flex_array_part *)&fa->parts[0];
 	else
 		part = fa->parts[part_nr];
+	if (!part)
+		return NULL;
 	return &part->elements[index_inside_part(fa, element_nr)];
 }
_


-- Dave

Re: [patch 1/3] flex_array: fix get function for elements in base starting at non-zero

[David Rientjes]

On Mon, 17 Aug 2009, Dave Hansen wrote:

> On Mon, 2009-08-17 at 16:46 -0700, David Rientjes wrote:
> > This fixes the bug by only checking for NULL parts when all elements do
> > not fit in the base structure when flex_array_get() is used.  Otherwise,
> > fa_element_to_part_nr() will always be 0 since there are no parts
> > structures needed and such element may never have been put.  Thus, it
> > will remain NULL due to the kzalloc() of the base.
> 
> Whew.  That one took me way longer to grok than it should have.  Thanks
> for finding this.  Just to be clear, there is only a bug in
> flex_array_get(), right?  The flex_array_put() change is completely
> separate and is intended to optimize the case where we know the pointer
> can't be NULL.
> 
> This definitely fixes a bug, but do you mind if we do it a bit
> differently?  The compiler should be able to take care of figuring out
> when that pointer actually needs to be checked, and I think it looks a
> bit nicer as it stands.   
> 

Your patch doesn't optimize the check away when all the elements are 
stored in the base structure, gcc doesn't infer that part must be valid 
based upon previous dereferences.  In fact, the resulting assembly would 
probably show the calculation of the element offset from `part' to happen 
in all cases iff part is non-NULL.

The flex_array_put() optimization is done for the same reason.

Re: [patch 1/3] flex_array: fix get function for elements in base starting at non-zero

[Dave Hansen]

On Mon, 2009-08-17 at 17:49 -0700, David Rientjes wrote:
> On Mon, 17 Aug 2009, Dave Hansen wrote:
> 
> > On Mon, 2009-08-17 at 16:46 -0700, David Rientjes wrote:
> > > This fixes the bug by only checking for NULL parts when all elements do
> > > not fit in the base structure when flex_array_get() is used.  Otherwise,
> > > fa_element_to_part_nr() will always be 0 since there are no parts
> > > structures needed and such element may never have been put.  Thus, it
> > > will remain NULL due to the kzalloc() of the base.
> > 
> > Whew.  That one took me way longer to grok than it should have.  Thanks
> > for finding this.  Just to be clear, there is only a bug in
> > flex_array_get(), right?  The flex_array_put() change is completely
> > separate and is intended to optimize the case where we know the pointer
> > can't be NULL.
> > 
> > This definitely fixes a bug, but do you mind if we do it a bit
> > differently?  The compiler should be able to take care of figuring out
> > when that pointer actually needs to be checked, and I think it looks a
> > bit nicer as it stands.   
> > 
> 
> Your patch doesn't optimize the check away when all the elements are 
> stored in the base structure, gcc doesn't infer that part must be valid 
> based upon previous dereferences.  In fact, the resulting assembly would 
> probably show the calculation of the element offset from `part' to happen 
> in all cases iff part is non-NULL.
> 
> The flex_array_put() optimization is done for the same reason.

Oh, I wasn't talking about dereferences.  I figured it would happen from
the *assignment*.  But, I guess with address space wrapping or other
oddities, gcc can't make that optimization, so my assumption was bogus.
We're arguing way too much about two instructions.  Either way is fine
with me.

-- Dave

Re: [patch 1/3] flex_array: fix get function for elements in base starting at non-zero

[Dave Hansen]

On Mon, 2009-08-17 at 16:46 -0700, David Rientjes wrote:
> If all array elements fit into the base structure and data is copied
> using flex_array_put() starting at a non-zero index, flex_array_get()
> will fail to return the data.
> 
> This fixes the bug by only checking for NULL parts when all elements do
> not fit in the base structure when flex_array_get() is used.  Otherwise,
> fa_element_to_part_nr() will always be 0 since there are no parts
> structures needed and such element may never have been put.  Thus, it
> will remain NULL due to the kzalloc() of the base.
> 
> Additionally, flex_array_put() now only checks for a NULL part when all
> elements do not fit in the base structure.  This is otherwise unnecessary
> since the base structure is guaranteed to exist (or we would have already
> hit a NULL pointer).
> 
> Cc: Dave Hansen <dave@linux.vnet.ibm.com>
> Signed-off-by: David Rientjes <rientjes@google.com>
> ---
>  lib/flex_array.c |   14 ++++++++------
>  1 files changed, 8 insertions(+), 6 deletions(-)
> 
> diff --git a/lib/flex_array.c b/lib/flex_array.c
> --- a/lib/flex_array.c
> +++ b/lib/flex_array.c
> @@ -198,10 +198,11 @@ int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags
>  		return -ENOSPC;
>  	if (elements_fit_in_base(fa))
>  		part = (struct flex_array_part *)&fa->parts[0];
> -	else
> +	else {
>  		part = __fa_get_part(fa, part_nr, flags);
> -	if (!part)
> -		return -ENOMEM;
> +		if (!part)
> +			return -ENOMEM;
> +	}
>  	dst = &part->elements[index_inside_part(fa, element_nr)];
>  	memcpy(dst, src, fa->element_size);
>  	return 0;
> @@ -257,11 +258,12 @@ void *flex_array_get(struct flex_array *fa, int element_nr)
> 
>  	if (element_nr >= fa->total_nr_elements)
>  		return NULL;
> -	if (!fa->parts[part_nr])
> -		return NULL;
>  	if (elements_fit_in_base(fa))
>  		part = (struct flex_array_part *)&fa->parts[0];
> -	else
> +	else {
>  		part = fa->parts[part_nr];
> +		if (!part)
> +			return NULL;
> +	}
>  	return &part->elements[index_inside_part(fa, element_nr)];
>  }

This is fine with me, and fixes the bug you describe.

-- 

Signed-off-by: Dave Hansen <dave@linux.vnet.ibm.com>

-- Dave