flex_array related problems on selinux policy loading

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.

On Thu, 2011-01-20 at 13:26 +0100, Steffen Klassert wrote:
...

Quoted 4 lines

lib/flex_array.c +0 -0

@@ -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;
 

Review int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, · line 199

Quoted 2 lines

(quoted diff) +2 -0

+	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.

Quoted 4 lines

lib/flex_array.c +0 -0

@@ -215,6 +226,9 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
 	struct flex_array_part *part;
 	void *dst;
 

Review int flex_array_clear(struct flex_array *fa, unsigned int element_nr) · line 230

Quoted 2 lines

(quoted diff) +2 -0

+	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?

Quoted 6 lines · Dave Hansen

On Thu, 2011-01-20 at 13:26 +0100, Steffen Klassert wrote:
...

Quoted 4 lines

lib/flex_array.c +0 -0

@@ -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;
 

Quoted 7 lines

Review int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, · line 199

Quoted 2 lines

(quoted diff) +2 -0

+	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.

Quoted 3 lines

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?

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'.

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.

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 8 lines

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.

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.

From this point of view, I'd tend to not allocating anything. Instead we

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.

Quoted 5 lines · Steffen Klassert

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?

Quoted 8 lines

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.

Quoted 7 lines · Dave Hansen

Quoted 5 lines · Steffen Klassert

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.

Quoted 3 lines

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.

Quoted 6 lines

Quoted 2 lines

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.