[PATCH] flex_array: Change behaviour on zero size allocations

[PATCH] flex_array: Change behaviour on zero size allocations

[Steffen Klassert]

flex_array_alloc allocates the basic struct flex_array regardless whether
total_nr_elements or element_size is zero. Then flex_array_prealloc
fails with -ENOSPC if total_nr_elements is zero or it hits a division by
zero if element_size is zero.

This patch changes the behaviour on zero size allocations to the same
as kmalloc, so zero size allocations are leagal now. This fixes a
regression on selinux policy loading.

Signed-off-by: Steffen Klassert <steffen.klassert@secunet.com>
---
 lib/flex_array.c |   25 +++++++++++++++++++++----
 1 files changed, 21 insertions(+), 4 deletions(-)

diff --git a/lib/flex_array.c b/lib/flex_array.c
index c0ea40b..8eb437b 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -88,8 +88,11 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
 					gfp_t flags)
 {
 	struct flex_array *ret;
-	int max_size = FLEX_ARRAY_NR_BASE_PTRS *
-				FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
+	int max_size = 0;
+
+	if (element_size)
+		max_size = FLEX_ARRAY_NR_BASE_PTRS *
+			   FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
 
 	/* max_size will end up 0 if element_size > PAGE_SIZE */
 	if (total > max_size)
@@ -183,15 +186,18 @@ __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
 int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
 			gfp_t flags)
 {
-	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	int part_nr;
 	struct flex_array_part *part;
 	void *dst;
 
+	if (!fa->element_size)
+		return 0;
 	if (element_nr >= fa->total_nr_elements)
 		return -ENOSPC;
 	if (elements_fit_in_base(fa))
 		part = (struct flex_array_part *)&fa->parts[0];
 	else {
+		part_nr = fa_element_to_part_nr(fa, element_nr);
 		part = __fa_get_part(fa, part_nr, flags);
 		if (!part)
 			return -ENOMEM;
@@ -211,15 +217,18 @@ EXPORT_SYMBOL(flex_array_put);
  */
 int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
 {
-	int part_nr = fa_element_to_part_nr(fa, element_nr);
+	int part_nr;
 	struct flex_array_part *part;
 	void *dst;
 
+	if (!fa->element_size)
+		return 0;
 	if (element_nr >= fa->total_nr_elements)
 		return -ENOSPC;
 	if (elements_fit_in_base(fa))
 		part = (struct flex_array_part *)&fa->parts[0];
 	else {
+		part_nr = fa_element_to_part_nr(fa, element_nr);
 		part = fa->parts[part_nr];
 		if (!part)
 			return -EINVAL;
@@ -252,8 +261,12 @@ int flex_array_prealloc(struct flex_array *fa, unsigned int start,
 	int part_nr;
 	struct flex_array_part *part;
 
+	if (!fa->total_nr_elements)
+		return 0;
 	if (start >= fa->total_nr_elements || end >= fa->total_nr_elements)
 		return -ENOSPC;
+	if (!fa->element_size)
+		return 0;
 	if (elements_fit_in_base(fa))
 		return 0;
 	start_part = fa_element_to_part_nr(fa, start);
@@ -284,6 +297,8 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
 	int part_nr = fa_element_to_part_nr(fa, element_nr);
 	struct flex_array_part *part;
 
+	if (!fa->total_nr_elements || !fa->element_size)
+		return NULL;
 	if (element_nr >= fa->total_nr_elements)
 		return NULL;
 	if (elements_fit_in_base(fa))
@@ -343,6 +358,8 @@ int flex_array_shrink(struct flex_array *fa)
 	int part_nr;
 	int ret = 0;
 
+	if (!fa->total_nr_elements || !fa->element_size)
+		return 0;
 	if (elements_fit_in_base(fa))
 		return ret;
 	for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) {
-- 
1.7.0.4

Re: [PATCH] flex_array: Change behaviour on zero size allocations

[Dave Hansen]

On Mon, 2011-01-31 at 09:52 +0100, Steffen Klassert wrote:
>  int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
>                         gfp_t flags)
>  {
> -       int part_nr = fa_element_to_part_nr(fa, element_nr);
> +       int part_nr;
>         struct flex_array_part *part;
>         void *dst;
> 
> +       if (!fa->element_size)
> +               return 0;
>         if (element_nr >= fa->total_nr_elements)
>                 return -ENOSPC; 

I think this still has some of the issues of the earlier patch.  The
zero-size check needs to be moved after the ->total_nr_elements check.
Otherwise, this won't produce any errors:

	fa = flex_array_alloc(0, 100, GFP_KERNEL);
	flex_array_put(fa, 1001, ptr, GFP_KERNEL);

> @@ -284,6 +297,8 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
>         int part_nr = fa_element_to_part_nr(fa, element_nr);
>         struct flex_array_part *part;
> 
> +       if (!fa->total_nr_elements || !fa->element_size)
> +               return NULL;
>         if (element_nr >= fa->total_nr_elements)
>                 return NULL;
>         if (elements_fit_in_base(fa))

Do you really need to check fa->total_nr_elements both for zero and
against element_nr?  Seems a but superfluous to me.

-- Dave

Re: [PATCH] flex_array: Change behaviour on zero size allocations

[Steffen Klassert]

On Mon, Jan 31, 2011 at 08:31:37AM -0800, Dave Hansen wrote:
> 
> I think this still has some of the issues of the earlier patch.  The
> zero-size check needs to be moved after the ->total_nr_elements check.
> Otherwise, this won't produce any errors:
> 
> 	fa = flex_array_alloc(0, 100, GFP_KERNEL);
> 	flex_array_put(fa, 1001, ptr, GFP_KERNEL);
> 
> > @@ -284,6 +297,8 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
> >         int part_nr = fa_element_to_part_nr(fa, element_nr);
> >         struct flex_array_part *part;
> > 
> > +       if (!fa->total_nr_elements || !fa->element_size)
> > +               return NULL;
> >         if (element_nr >= fa->total_nr_elements)
> >                 return NULL;
> >         if (elements_fit_in_base(fa))
> 
> Do you really need to check fa->total_nr_elements both for zero and
> against element_nr?  Seems a but superfluous to me.
> 

Both objections are correct, I'll send an updated patch.

Steffen

Re: [PATCH] flex_array: Change behaviour on zero size allocations

[Steffen Klassert]

On Tue, Feb 01, 2011 at 11:24:18AM +0100, Steffen Klassert wrote:
> 
> Both objections are correct, I'll send an updated patch.
> 

I think we need to fix selinux too to get rid of the policy loading
problem. In security/selinux/ss/policydb.c are several pieces of code
like this one:

p->type_val_to_struct_array = flex_array_alloc(sizeof(struct type_datum *),   
                                               p->p_types.nprim,              
                                               GFP_KERNEL | __GFP_ZERO);
if (!p->type_val_to_struct_array)      
	goto out;

rc = flex_array_prealloc(p->type_val_to_struct_array, 0,
                         p->p_types.nprim - 1, GFP_KERNEL | __GFP_ZERO);
if (rc)
	goto out;

If p->p_types.nprim is zero, we allocare with total_nr_elements equal
to zerro and then we try to prealloc with p->p_types.nprim - 1.
flex_array_prealloc interprets this as an unsigned int and fails,
because this is bigger than total_nr_elements, which is correct I think.

Thoughts?

Steffen

Re: [PATCH] flex_array: Change behaviour on zero size allocations

[Dave Hansen]

On Tue, 2011-02-01 at 12:03 +0100, Steffen Klassert wrote:
> rc = flex_array_prealloc(p->type_val_to_struct_array, 0,
>                          p->p_types.nprim - 1, GFP_KERNEL | __GFP_ZERO);
> if (rc)
>         goto out;
> 
> If p->p_types.nprim is zero, we allocare with total_nr_elements equal
> to zerro and then we try to prealloc with p->p_types.nprim - 1.
> flex_array_prealloc interprets this as an unsigned int and fails,
> because this is bigger than total_nr_elements, which is correct I
> think.
> 
> Thoughts?

The most we ever hold in a flex_array is ~2 million entries.  So we have
plenty of room to use a normal int if you want.

On the other hand, there's only one user of flex_array_prealloc(), and
making the "end" argument inclusive doesn't seem to be what that user
wants.  We might want to either make flex_array_prealloc() take start
and length, or instead make "end" be exclusive of the "end" index.

I thought that flex_array_prealloc would say, effectively: "all put()'s
would work up until 'end'".  But, looking at it now, that's probably not
how people will use it.  

-- Dave

Re: [PATCH] flex_array: Change behaviour on zero size allocations

[Eric Paris]

On Tue, 2011-02-01 at 06:55 -0800, Dave Hansen wrote:
> On Tue, 2011-02-01 at 12:03 +0100, Steffen Klassert wrote:
> > rc = flex_array_prealloc(p->type_val_to_struct_array, 0,
> >                          p->p_types.nprim - 1, GFP_KERNEL | __GFP_ZERO);
> > if (rc)
> >         goto out;
> > 
> > If p->p_types.nprim is zero, we allocare with total_nr_elements equal
> > to zerro and then we try to prealloc with p->p_types.nprim - 1.
> > flex_array_prealloc interprets this as an unsigned int and fails,
> > because this is bigger than total_nr_elements, which is correct I
> > think.
> > 
> > Thoughts?
> 
> The most we ever hold in a flex_array is ~2 million entries.  So we have
> plenty of room to use a normal int if you want.
> 
> On the other hand, there's only one user of flex_array_prealloc(), and
> making the "end" argument inclusive doesn't seem to be what that user
> wants.  We might want to either make flex_array_prealloc() take start
> and length, or instead make "end" be exclusive of the "end" index.
>
> I thought that flex_array_prealloc would say, effectively: "all put()'s
> would work up until 'end'".  But, looking at it now, that's probably not
> how people will use it.  

I'm fine with any solution.  It's obviously broken for SELinux to be
passing -1 even if the library supported it.  I guess I don't really
have strong feelings on how to fix it.

1) make end exclusive
2) change 'end' to 'len'
3) just make selinux not prealloc() when the #elements == 0

All seem perfectly reasonable to me, but I'd probably do them in that
order.

-Eric

Re: [PATCH] flex_array: Change behaviour on zero size allocations

[Steffen Klassert]

On Tue, Feb 01, 2011 at 10:20:22AM -0500, Eric Paris wrote:
> 
> I'm fine with any solution.  It's obviously broken for SELinux to be
> passing -1 even if the library supported it.  I guess I don't really
> have strong feelings on how to fix it.
> 
> 1) make end exclusive
> 2) change 'end' to 'len'
> 3) just make selinux not prealloc() when the #elements == 0
> 
> All seem perfectly reasonable to me, but I'd probably do them in that
> order.
> 

I think I would prefer option 2. Passing a size or a length to
a memory allocator is quite common and we would not need to care
for bugs where 'end' is smaller than 'start'.

So I'd do it like that, if noone has strong feelings for another option.

Steffen