flex_array related problems on selinux policy loading

flex_array related problems on selinux policy loading

[Steffen Klassert]

Some recent changes to use flex_array_alloc on selinux policy loading made
me unable load my selinux policy. I'm not using 'common' and 'bool' in the
policy, this leads to some zero size allocations in policydb_index().
Unfortunately the behaviour on zero size allocations of flex_array_alloc()
is not the same as of kmalloc(). While zero size allocations are legal on
kmalloc(), flex_array_prealloc() fails with -ENOSPC if total_nr_elements
is zero (this happens if I try to load my policy) or it hits a division by
zero if element_size is zero.

The patch below changes the flex_array_alloc behaviour on zero size allocations
to be the same as with kmalloc. I'm able to load my policy with the patch
and everything seems to work fine. However, flex_array_get() returns now NULL
if the pointer to the struct flex_array is a ZERO_SIZE_PTR.  There is a lot
of BUG_ON() in the policy handling code if flex_array_get() returns NULL, so
somebody with a deeper knowledge on selinux policy handling should look into
this to see if furter changes are necessary.

Steffen

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

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, we return ZERO_SIZE_PTR in this case. All flex_array handlers
test for ZERO_SIZE_PTR and return an appropriate value to the caller.

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

diff --git a/lib/flex_array.c b/lib/flex_array.c
index c0ea40b..420d11d 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -88,8 +88,13 @@ 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;
+
+	if (unlikely(!element_size || !total))
+		return ZERO_SIZE_PTR;
+
+	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)
@@ -123,6 +128,9 @@ void flex_array_free_parts(struct flex_array *fa)
 {
 	int part_nr;
 
+	if (unlikely(ZERO_OR_NULL_PTR(fa)))
+		return;
+
 	if (elements_fit_in_base(fa))
 		return;
 	for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
@@ -187,6 +195,9 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
 	struct flex_array_part *part;
 	void *dst;
 
+	if (unlikely(ZERO_OR_NULL_PTR(fa)))
+		return 0;
+
 	if (element_nr >= fa->total_nr_elements)
 		return -ENOSPC;
 	if (elements_fit_in_base(fa))
@@ -215,6 +226,9 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
 	struct flex_array_part *part;
 	void *dst;
 
+	if (unlikely(ZERO_OR_NULL_PTR(fa)))
+		return 0;
+
 	if (element_nr >= fa->total_nr_elements)
 		return -ENOSPC;
 	if (elements_fit_in_base(fa))
@@ -252,6 +266,9 @@ int flex_array_prealloc(struct flex_array *fa, unsigned int start,
 	int part_nr;
 	struct flex_array_part *part;
 
+	if (unlikely(ZERO_OR_NULL_PTR(fa)))
+		return 0;
+
 	if (start >= fa->total_nr_elements || end >= fa->total_nr_elements)
 		return -ENOSPC;
 	if (elements_fit_in_base(fa))
@@ -284,6 +301,9 @@ 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 (unlikely(ZERO_OR_NULL_PTR(fa)))
+		return NULL;
+
 	if (element_nr >= fa->total_nr_elements)
 		return NULL;
 	if (elements_fit_in_base(fa))
@@ -343,6 +363,9 @@ int flex_array_shrink(struct flex_array *fa)
 	int part_nr;
 	int ret = 0;
 
+	if (unlikely(ZERO_OR_NULL_PTR(fa)))
+		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: flex_array related problems on selinux policy loading

[Dave Hansen]

On Thu, 2011-01-20 at 13:26 +0100, Steffen Klassert wrote:
> 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, we return ZERO_SIZE_PTR in this case. All flex_array handlers
> test for ZERO_SIZE_PTR and return an appropriate value to the caller.

Some of this seems pretty sane, at least to make it more of a drop-in
for kmalloc().

...
> @@ -187,6 +195,9 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
>  	struct flex_array_part *part;
>  	void *dst;
> 
> +	if (unlikely(ZERO_OR_NULL_PTR(fa)))
> +		return 0;

I think it's OK to add these for the array alloc and free cases.  But,
it's really dangerous to do it for put.  It has the potential to
silently throw away data and then be really confusing to debug when you
can't get it back later.

This can only make sense if you have a zero-byte element.  However, this
would also just return if you happened to try and insert data in to a
zero-length array.  That's a bug we need to catch.  Note that
kmem_cache_create() doesn't let you create caches for zero-byte objects.

> @@ -215,6 +226,9 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
>  	struct flex_array_part *part;
>  	void *dst;
> 
> +	if (unlikely(ZERO_OR_NULL_PTR(fa)))
> +		return 0;

I tend to think about the flex_array itself as being more like a
kmem_cache than anything else.  So, all of the operations on the array
itself, like shrinking and growing are probably OK.

Can you also pull the unlikely()s?  

-- Dave

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

On Thu, Jan 20, 2011 at 07:28:50AM -0800, Dave Hansen wrote:
> On Thu, 2011-01-20 at 13:26 +0100, Steffen Klassert wrote:
> ...
> > @@ -187,6 +195,9 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
> >  	struct flex_array_part *part;
> >  	void *dst;
> > 
> > +	if (unlikely(ZERO_OR_NULL_PTR(fa)))
> > +		return 0;
> 
> I think it's OK to add these for the array alloc and free cases.  But,
> it's really dangerous to do it for put.  It has the potential to
> silently throw away data and then be really confusing to debug when you
> can't get it back later.

If the pointer to struct flex_array is a ZERO_SIZE_PTR we have to exit
before we try to dereference the first time as we have not allocated
anything. We can think about returning an error value in flex_array_put
if the flex_array is a ZERO_SIZE_PTR. The the user would be notified
that we could not store his data, but that's all we can do here I think.

Anyway, I just noticed in some functions the line

int part_nr = fa_element_to_part_nr(fa, element_nr);

which already dereferences the flex_array before I test for ZERO_SIZE_PTR.
So I have to fix this and to resubmit the patch.

> 
> This can only make sense if you have a zero-byte element.  However, this
> would also just return if you happened to try and insert data in to a
> zero-length array.  That's a bug we need to catch.  Note that
> kmem_cache_create() doesn't let you create caches for zero-byte objects.
> 
> > @@ -215,6 +226,9 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
> >  	struct flex_array_part *part;
> >  	void *dst;
> > 
> > +	if (unlikely(ZERO_OR_NULL_PTR(fa)))
> > +		return 0;
> 
> I tend to think about the flex_array itself as being more like a
> kmem_cache than anything else.  So, all of the operations on the array
> itself, like shrinking and growing are probably OK.

Hm, if either element_size or total_nr_elements is zero on allocation time,
the maximum size the array can ever have is zero. So I don't see how to
grow (shrink) anything in this case. Do I miss something here?

> 
> Can you also pull the unlikely()s?  
> 

Usually, when you call flex_array_alloc you want to allocate some memory.
So I considered a zero size allocation as a rare corner case, like kmalloc
does. Therefore the unlikely branch predictors made sense for me. Anyway,
I don't have a strong opinion about the unlikelys, so if you think it is
better to remove them I'll do so.

Steffen

Re: flex_array related problems on selinux policy loading

[Dave Hansen]

On Fri, 2011-01-21 at 08:20 +0100, Steffen Klassert wrote:
> On Thu, Jan 20, 2011 at 07:28:50AM -0800, Dave Hansen wrote:
> > On Thu, 2011-01-20 at 13:26 +0100, Steffen Klassert wrote:
> > ...
> > > @@ -187,6 +195,9 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
> > >  	struct flex_array_part *part;
> > >  	void *dst;
> > > 
> > > +	if (unlikely(ZERO_OR_NULL_PTR(fa)))
> > > +		return 0;
> > 
> > I think it's OK to add these for the array alloc and free cases.  But,
> > it's really dangerous to do it for put.  It has the potential to
> > silently throw away data and then be really confusing to debug when you
> > can't get it back later.
> 
> If the pointer to struct flex_array is a ZERO_SIZE_PTR we have to exit
> before we try to dereference the first time as we have not allocated
> anything. We can think about returning an error value in flex_array_put
> if the flex_array is a ZERO_SIZE_PTR. The the user would be notified
> that we could not store his data, but that's all we can do here I think.

Yeah, a zero-sized array with a put() done on it should return -ENOSPC,
not 0.  But, an array storing 0-byte objects can and should return 0.

Basically, the patch confuses those two cases.

> > I tend to think about the flex_array itself as being more like a
> > kmem_cache than anything else.  So, all of the operations on the array
> > itself, like shrinking and growing are probably OK.
> 
> Hm, if either element_size or total_nr_elements is zero on allocation time,
> the maximum size the array can ever have is zero. So I don't see how to
> grow (shrink) anything in this case. Do I miss something here?

I mean it shouldn't return an error, nor is it invalid.  You can't _do_
anything, but it's at least valid.

My suggestion would be to simply make sure that the code handles 0-sized
objects and 0-length arrays OK, and do it in two separate patches.  The
ZERO_SIZE_PTR can't be used for both because you need to know which
situation you were in and you need different behavior (like in
flex_array_put()).

Frankly, I like the idea of just allocating a 'struct flex_array' in any
case, and just teaching the code to handle element_size=0 and
nr_elements=0.  That way, if you have bugs in the code that does things
like flex_array_alloc(elem_size=0, len=5, ...) and then
flex_array_get(fa, index=99), you have the potential to detect and
report the bugs.  The only way to do that is to remember what you set
the length as.  

If you're worried about allocating a whole page, you could easily just
kmalloc() a the two integers for the metadata portion of the 'struct
flex_array'.

-- Dave

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

Cc'ed Andrew on request.

On Fri, Jan 21, 2011 at 07:57:35AM -0800, Dave Hansen wrote:
> 
> My suggestion would be to simply make sure that the code handles 0-sized
> objects and 0-length arrays OK, and do it in two separate patches.  The
> ZERO_SIZE_PTR can't be used for both because you need to know which
> situation you were in and you need different behavior (like in
> flex_array_put()).
> 
> Frankly, I like the idea of just allocating a 'struct flex_array' in any
> case, and just teaching the code to handle element_size=0 and
> nr_elements=0.  That way, if you have bugs in the code that does things
> like flex_array_alloc(elem_size=0, len=5, ...) and then
> flex_array_get(fa, index=99), you have the potential to detect and
> report the bugs.  The only way to do that is to remember what you set
> the length as. 

Ok, if we can catch these bugs in an easy way, without a lot of extra
handling for this a rare case, we should do this.
 
> 
> If you're worried about allocating a whole page, you could easily just
> kmalloc() a the two integers for the metadata portion of the 'struct
> flex_array'.
> 

Yes, I thought a moment on allocating the basic struct flex_array
in any case. But I immediately stopped thinking about this when I saw that
I would allocate a whole page that I don't need afterwards. For the moment
I don't see any sane way to allocate just the metadata as long as the
struct flex_array has a fixed size.

Btw. why the struct flex_array needs to have page size? If we would make
flex_array of dynamic size, say metadata plus the maximum size of the array
in the case that the metadata and the array fit into a single page, and
metadata plus space for all the base pointers we need to dereference the
parts, if the metadata and array is beyond page size. With this, the struct
flex_array would have a reasonable size in any case, even if the array to
store is small or of zero size.

Steffen

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

On Fri, Jan 21, 2011 at 07:57:35AM -0800, Dave Hansen wrote:
> 
> My suggestion would be to simply make sure that the code handles 0-sized
> objects and 0-length arrays OK, and do it in two separate patches.  The
> ZERO_SIZE_PTR can't be used for both because you need to know which
> situation you were in and you need different behavior (like in
> flex_array_put()).
> 
> Frankly, I like the idea of just allocating a 'struct flex_array' in any
> case, and just teaching the code to handle element_size=0 and
> nr_elements=0.  That way, if you have bugs in the code that does things
> like flex_array_alloc(elem_size=0, len=5, ...) and then
> flex_array_get(fa, index=99), you have the potential to detect and
> report the bugs.  The only way to do that is to remember what you set
> the length as.  
> 

Another thing came to my mind. An atempt to do a zero size allocation
always succeed on kmalloc. If we want to allocate our metadata even in
this case, we should be aware that this allocation _can_ fail. So
flex_array_alloc would not show the same behaviour as kmalloc on zero
size allocations. As most potential flex_array users convert their code
from kmalloc, the behaviour of flex_array_alloc should be the same as of
kmalloc. Showing a different behaviour here will produce pitfalls for
potential new users. Also, to tell a user that we can not allocate memory
for him, if the wants to allocate 0 byte (nothing) is quite odd. This
user could easily continue processing, even if we can not allocate our
metadata in this moment.

>From this point of view, I'd tend to not allocating anything. Instead we
could return two newly defined pointers, e.g. FLEX_ARRAY_ZERO_SIZE and
FLEX_ARRAY_ZERO_ELEMENTS to catch if either element_size or
total_nr_elements is zero.

The downside of this is of course, that we can't catch the bugs you
mentioned above.

Steffen

Re: flex_array related problems on selinux policy loading

[Dave Hansen]

On Wed, 2011-01-26 at 11:23 +0100, Steffen Klassert wrote: 
> Yes, I thought a moment on allocating the basic struct flex_array
> in any case. But I immediately stopped thinking about this when I saw that
> I would allocate a whole page that I don't need afterwards. For the moment
> I don't see any sane way to allocate just the metadata as long as the
> struct flex_array has a fixed size.
> 
> Btw. why the struct flex_array needs to have page size?

It was designed as an alternative to _large_ allocations and we didn't
expect people to want to use it for small things.  But, it doesn't
_need_ to stay that way, we just did it like that for simplicity.

> If we would make
> flex_array of dynamic size, say metadata plus the maximum size of the array
> in the case that the metadata and the array fit into a single page, and
> metadata plus space for all the base pointers we need to dereference the
> parts, if the metadata and array is beyond page size. With this, the struct
> flex_array would have a reasonable size in any case, even if the array to
> store is small or of zero size.

Sounds like a good idea to me.  Done right, it should only really affect
the allocation path since we use kmalloc() already, and we can still
plain kfree() it.

-- Dave

Re: flex_array related problems on selinux policy loading

[Dave Hansen]

On Wed, 2011-01-26 at 14:04 +0100, Steffen Klassert wrote:
> Another thing came to my mind. An atempt to do a zero size allocation
> always succeed on kmalloc. If we want to allocate our metadata even in
> this case, we should be aware that this allocation _can_ fail. So
> flex_array_alloc would not show the same behaviour as kmalloc on zero
> size allocations.

I think that's just fine.

You have to check for and handle those allocation failures anyway.  Can
you think of places in the kernel where we have known-zero-sized
allocations that don't check kmalloc() returns?

> As most potential flex_array users convert their code
> from kmalloc, the behaviour of flex_array_alloc should be the same as of
> kmalloc. Showing a different behaviour here will produce pitfalls for
> potential new users. Also, to tell a user that we can not allocate memory
> for him, if the wants to allocate 0 byte (nothing) is quite odd. This
> user could easily continue processing, even if we can not allocate our
> metadata in this moment.

This doesn't have to be a one to one, direct, replacement for kmalloc().
As long as it's close enough not to confuse people or normally cause
problems, I think it's fine.
-- Dave

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

On Wed, Jan 26, 2011 at 08:10:16AM -0800, Dave Hansen wrote:
> > 
> > Btw. why the struct flex_array needs to have page size?
> 
> It was designed as an alternative to _large_ allocations and we didn't
> expect people to want to use it for small things.  But, it doesn't
> _need_ to stay that way, we just did it like that for simplicity.
> 

Ok, I thought that. In case of selinux, the informations on how big
the array will be comes from the userspace. In the most cases, people
use big selinux policies like the selinux reference policy, these
arrays are quite big. But if somebody uses just a dummy policy, the
arrays are small or empty in some cases.

> > If we would make
> > flex_array of dynamic size, say metadata plus the maximum size of the array
> > in the case that the metadata and the array fit into a single page, and
> > metadata plus space for all the base pointers we need to dereference the
> > parts, if the metadata and array is beyond page size. With this, the struct
> > flex_array would have a reasonable size in any case, even if the array to
> > store is small or of zero size.
> 
> Sounds like a good idea to me.  Done right, it should only really affect
> the allocation path since we use kmalloc() already, and we can still
> plain kfree() it.
> 

So lets do it like that. I'll propose another patch, may take some days.

Steffen

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

On Wed, Jan 26, 2011 at 08:15:26AM -0800, Dave Hansen wrote:
> On Wed, 2011-01-26 at 14:04 +0100, Steffen Klassert wrote:
> > Another thing came to my mind. An atempt to do a zero size allocation
> > always succeed on kmalloc. If we want to allocate our metadata even in
> > this case, we should be aware that this allocation _can_ fail. So
> > flex_array_alloc would not show the same behaviour as kmalloc on zero
> > size allocations.
> 
> I think that's just fine.
> 
> You have to check for and handle those allocation failures anyway.  

If we just return a pointer to the user that notifies that this was a
zerro size allocation, we would not need to allocate anything (like
kmalloc does), so we can't get allocation failures.

> Can
> you think of places in the kernel where we have known-zero-sized
> allocations that don't check kmalloc() returns?

Usually, if somebody allocates memory he just checks if he got a
NULL pointer. I've never seen somebody checking for ZERO_SIZE_PTR.

> 
> > As most potential flex_array users convert their code
> > from kmalloc, the behaviour of flex_array_alloc should be the same as of
> > kmalloc. Showing a different behaviour here will produce pitfalls for
> > potential new users. Also, to tell a user that we can not allocate memory
> > for him, if the wants to allocate 0 byte (nothing) is quite odd. This
> > user could easily continue processing, even if we can not allocate our
> > metadata in this moment.
> 
> This doesn't have to be a one to one, direct, replacement for kmalloc().
> As long as it's close enough not to confuse people or normally cause
> problems, I think it's fine.

Indeed, it does not have to be one to one. But if we do it different,
we should document the difference somewere at least. I'll do that
once I have an updated patch and I know how the difference will be.

Steffen

Re: flex_array related problems on selinux policy loading

[Dave Hansen]

On Thu, 2011-01-27 at 13:46 +0100, Steffen Klassert wrote:
> On Wed, Jan 26, 2011 at 08:15:26AM -0800, Dave Hansen wrote:
> > On Wed, 2011-01-26 at 14:04 +0100, Steffen Klassert wrote:
> > > Another thing came to my mind. An atempt to do a zero size allocation
> > > always succeed on kmalloc. If we want to allocate our metadata even in
> > > this case, we should be aware that this allocation _can_ fail. So
> > > flex_array_alloc would not show the same behaviour as kmalloc on zero
> > > size allocations.
> > 
> > I think that's just fine.
> > 
> > You have to check for and handle those allocation failures anyway.  
> 
> If we just return a pointer to the user that notifies that this was a
> zerro size allocation, we would not need to allocate anything (like
> kmalloc does), so we can't get allocation failures.

Could you point me to some of this code?  I'm having a hard time seeing
how this is going to get used, and I don't see any use of
ZERO_SIZE_PTR/ZERO_OR_NULL_PTR() outside of the sl*b code.

-- Dave

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

On Thu, Jan 27, 2011 at 08:57:29AM -0800, Dave Hansen wrote:
> > > 
> > > You have to check for and handle those allocation failures anyway.  
> > 
> > If we just return a pointer to the user that notifies that this was a
> > zerro size allocation, we would not need to allocate anything (like
> > kmalloc does), so we can't get allocation failures.
> 
> Could you point me to some of this code?  I'm having a hard time seeing
> how this is going to get used, and I don't see any use of
> ZERO_SIZE_PTR/ZERO_OR_NULL_PTR() outside of the sl*b code.
> 

Perhaps I did not express it the right way, but
I did not say that this is used somewhere outside the sl*b code.
All I meant is that we return a pointer, like ZERO_SIZE_PTR
that notifies us that we have not allocated anything if a user
wants to access or to free data. This pointers are just for
internal usage of course.

Steffen

Re: flex_array related problems on selinux policy loading

[Steffen Klassert]

On Wed, Jan 26, 2011 at 08:10:16AM -0800, Dave Hansen wrote:
> 
> > If we would make
> > flex_array of dynamic size, say metadata plus the maximum size of the array
> > in the case that the metadata and the array fit into a single page, and
> > metadata plus space for all the base pointers we need to dereference the
> > parts, if the metadata and array is beyond page size. With this, the struct
> > flex_array would have a reasonable size in any case, even if the array to
> > store is small or of zero size.
> 
> Sounds like a good idea to me.  Done right, it should only really affect
> the allocation path since we use kmalloc() already, and we can still
> plain kfree() it.
> 


I started to look into making flex_array of dynamic size.
There are al lot of structural changes necessary, so I think this
is too much just to fix a zero size allocation bug. So
lets fix it like you proposed it by allocating the flex_array
in any case and accept that it will be of PAGE_SIZE by now.
Making flex_array of dynamic size can wait for 2.6.39 I think.

Steffen