From e6de3988aa52debb25a427d085061f3bf1181d54 Mon Sep 17 00:00:00 2001 From: David Rientjes Date: Mon, 21 Sep 2009 17:04:30 -0700 Subject: flex_array: add flex_array_clear function Add a new function to the flex_array API: int flex_array_clear(struct flex_array *fa, unsigned int element_nr) This function will zero the element at element_nr in the flex_array. Although this is equivalent to using flex_array_put() and passing a pointer to zero'd memory, flex_array_clear() does not require such a pointer to memory that would most likely need to be allocated on the caller's stack which could be significantly large depending on element_size. Signed-off-by: David Rientjes Cc: Dave Hansen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/flex_array.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'lib/flex_array.c') diff --git a/lib/flex_array.c b/lib/flex_array.c index 7baed2fc3bc8..b68f99be4080 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -206,6 +206,32 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, return 0; } +/** + * flex_array_clear - clear element in array at @element_nr + * @element_nr: index of the position to clear. + * + * Locking must be provided by the caller. + */ +int flex_array_clear(struct flex_array *fa, unsigned int element_nr) +{ + int part_nr = fa_element_to_part_nr(fa, element_nr); + struct flex_array_part *part; + void *dst; + + 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 = fa->parts[part_nr]; + if (!part) + return -EINVAL; + } + dst = &part->elements[index_inside_part(fa, element_nr)]; + memset(dst, 0, fa->element_size); + return 0; +} + /** * flex_array_prealloc - guarantee that array space exists * @start: index of first array element for which space is allocated -- cgit v1.2.3 From 19da3dd157f8db6fe727ff268dab4791d55a6371 Mon Sep 17 00:00:00 2001 From: David Rientjes Date: Mon, 21 Sep 2009 17:04:31 -0700 Subject: flex_array: poison free elements Newly initialized flex_array's and/or flex_array_part's are now poisoned with a new poison value, FLEX_ARRAY_FREE. It's value is similar to POISON_FREE used in the various slab allocators, but is different to distinguish between flex array's poisoned kmem and slab allocator poisoned kmem. This will allow us to identify flex_array_part's that only contain free elements (and free them with an addition to the flex_array API). This could also be extended in the future to identify `get' uses on elements that have not been `put'. If __GFP_ZERO is passed for a part's gfp mask, the poisoning is avoided. These elements are considered to be in-use since they have been initialized. Signed-off-by: David Rientjes Cc: Dave Hansen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/poison.h | 3 +++ lib/flex_array.c | 15 +++++++-------- 2 files changed, 10 insertions(+), 8 deletions(-) (limited to 'lib/flex_array.c') diff --git a/include/linux/poison.h b/include/linux/poison.h index 6729f7dcd60e..7fc194aef8c2 100644 --- a/include/linux/poison.h +++ b/include/linux/poison.h @@ -65,6 +65,9 @@ #define MUTEX_DEBUG_INIT 0x11 #define MUTEX_DEBUG_FREE 0x22 +/********** lib/flex_array.c **********/ +#define FLEX_ARRAY_FREE 0x6c /* for use-after-free poisoning */ + /********** security/ **********/ #define KEY_DESTROY 0xbd diff --git a/lib/flex_array.c b/lib/flex_array.c index b68f99be4080..e22d0e9776aa 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -113,6 +113,8 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total, return NULL; ret->element_size = element_size; ret->total_nr_elements = total; + if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO)) + memset(ret->parts[0], FLEX_ARRAY_FREE, bytes_left_in_base()); return ret; } @@ -159,15 +161,12 @@ __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags) { struct flex_array_part *part = fa->parts[part_nr]; if (!part) { - /* - * This leaves the part pages uninitialized - * and with potentially random data, just - * as if the user had kmalloc()'d the whole. - * __GFP_ZERO can be used to zero it. - */ - part = kmalloc(FLEX_ARRAY_PART_SIZE, flags); + part = kmalloc(sizeof(struct flex_array_part), flags); if (!part) return NULL; + if (!(flags & __GFP_ZERO)) + memset(part, FLEX_ARRAY_FREE, + sizeof(struct flex_array_part)); fa->parts[part_nr] = part; } return part; @@ -228,7 +227,7 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr) return -EINVAL; } dst = &part->elements[index_inside_part(fa, element_nr)]; - memset(dst, 0, fa->element_size); + memset(dst, FLEX_ARRAY_FREE, fa->element_size); return 0; } -- cgit v1.2.3 From 4af5a2f770cc8575840ccb1514ec76ecb592985c Mon Sep 17 00:00:00 2001 From: David Rientjes Date: Mon, 21 Sep 2009 17:04:31 -0700 Subject: flex_array: add flex_array_shrink function Add a new function to the flex_array API: int flex_array_shrink(struct flex_array *fa) This function will free all unused second-level pages. Since elements are now poisoned if they are not allocated with __GFP_ZERO, it's possible to identify parts that consist solely of unused elements. flex_array_shrink() returns the number of pages freed. Signed-off-by: David Rientjes Cc: Dave Hansen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/flex_array.h | 1 + lib/flex_array.c | 40 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 41 insertions(+) (limited to 'lib/flex_array.c') diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h index 3887b21f883f..f12401e485fe 100644 --- a/include/linux/flex_array.h +++ b/include/linux/flex_array.h @@ -46,5 +46,6 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, gfp_t flags); int flex_array_clear(struct flex_array *fa, unsigned int element_nr); void *flex_array_get(struct flex_array *fa, unsigned int element_nr); +int flex_array_shrink(struct flex_array *fa); #endif /* _FLEX_ARRAY_H */ diff --git a/lib/flex_array.c b/lib/flex_array.c index e22d0e9776aa..1b03bb553410 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -291,3 +291,43 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr) } return &part->elements[index_inside_part(fa, element_nr)]; } + +static int part_is_free(struct flex_array_part *part) +{ + int i; + + for (i = 0; i < sizeof(struct flex_array_part); i++) + if (part->elements[i] != FLEX_ARRAY_FREE) + return 0; + return 1; +} + +/** + * flex_array_shrink - free unused second-level pages + * + * Frees all second-level pages that consist solely of unused + * elements. Returns the number of pages freed. + * + * Locking must be provided by the caller. + */ +int flex_array_shrink(struct flex_array *fa) +{ + struct flex_array_part *part; + int max_part = nr_base_part_ptrs(); + int part_nr; + int ret = 0; + + if (elements_fit_in_base(fa)) + return ret; + for (part_nr = 0; part_nr < max_part; part_nr++) { + part = fa->parts[part_nr]; + if (!part) + continue; + if (part_is_free(part)) { + fa->parts[part_nr] = NULL; + kfree(part); + ret++; + } + } + return ret; +} -- cgit v1.2.3 From 45b588d6e5cc172704bac0c998ce54873b149b22 Mon Sep 17 00:00:00 2001 From: David Rientjes Date: Mon, 21 Sep 2009 17:04:33 -0700 Subject: flex_array: introduce DEFINE_FLEX_ARRAY FLEX_ARRAY_INIT(element_size, total_nr_elements) cannot determine if either parameter is valid, so flex arrays which are statically allocated with this interface can easily become corrupted or reference beyond its allocated memory. This removes FLEX_ARRAY_INIT() as a struct flex_array initializer since no initializer may perform the required checking. Instead, the array is now defined with a new interface: DEFINE_FLEX_ARRAY(name, element_size, total_nr_elements) This may be prefixed with `static' for file scope. This interface includes compile-time checking of the parameters to ensure they are valid. Since the validity of both element_size and total_nr_elements depend on FLEX_ARRAY_BASE_SIZE and FLEX_ARRAY_PART_SIZE, the kernel build will fail if either of these predefined values changes such that the array parameters are no longer valid. Since BUILD_BUG_ON() requires compile time constants, several of the static inline functions that were once local to lib/flex_array.c had to be moved to include/linux/flex_array.h. Signed-off-by: David Rientjes Acked-by: Dave Hansen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/flex_array.h | 30 ++++++++++++++++++++++++++---- lib/flex_array.c | 36 ++++++++++-------------------------- 2 files changed, 36 insertions(+), 30 deletions(-) (limited to 'lib/flex_array.c') diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h index f12401e485fe..1d747f72298b 100644 --- a/include/linux/flex_array.h +++ b/include/linux/flex_array.h @@ -31,10 +31,32 @@ struct flex_array { }; }; -#define FLEX_ARRAY_INIT(size, total) { { {\ - .element_size = (size), \ - .total_nr_elements = (total), \ -} } } +/* Number of bytes left in base struct flex_array, excluding metadata */ +#define FLEX_ARRAY_BASE_BYTES_LEFT \ + (FLEX_ARRAY_BASE_SIZE - offsetof(struct flex_array, parts)) + +/* Number of pointers in base to struct flex_array_part pages */ +#define FLEX_ARRAY_NR_BASE_PTRS \ + (FLEX_ARRAY_BASE_BYTES_LEFT / sizeof(struct flex_array_part *)) + +/* Number of elements of size that fit in struct flex_array_part */ +#define FLEX_ARRAY_ELEMENTS_PER_PART(size) \ + (FLEX_ARRAY_PART_SIZE / size) + +/* + * Defines a statically allocated flex array and ensures its parameters are + * valid. + */ +#define DEFINE_FLEX_ARRAY(__arrayname, __element_size, __total) \ + struct flex_array __arrayname = { { { \ + .element_size = (__element_size), \ + .total_nr_elements = (__total), \ + } } }; \ + static inline void __arrayname##_invalid_parameter(void) \ + { \ + BUILD_BUG_ON((__total) > FLEX_ARRAY_NR_BASE_PTRS * \ + FLEX_ARRAY_ELEMENTS_PER_PART(__element_size)); \ + } struct flex_array *flex_array_alloc(int element_size, unsigned int total, gfp_t flags); diff --git a/lib/flex_array.c b/lib/flex_array.c index 1b03bb553410..b62ce6cffd0a 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -28,23 +28,6 @@ struct flex_array_part { char elements[FLEX_ARRAY_PART_SIZE]; }; -static inline int __elements_per_part(int element_size) -{ - return FLEX_ARRAY_PART_SIZE / element_size; -} - -static inline int bytes_left_in_base(void) -{ - int element_offset = offsetof(struct flex_array, parts); - int bytes_left = FLEX_ARRAY_BASE_SIZE - element_offset; - return bytes_left; -} - -static inline int nr_base_part_ptrs(void) -{ - return bytes_left_in_base() / sizeof(struct flex_array_part *); -} - /* * If a user requests an allocation which is small * enough, we may simply use the space in the @@ -54,7 +37,7 @@ static inline int nr_base_part_ptrs(void) static inline int elements_fit_in_base(struct flex_array *fa) { int data_size = fa->element_size * fa->total_nr_elements; - if (data_size <= bytes_left_in_base()) + if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT) return 1; return 0; } @@ -103,7 +86,8 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total, gfp_t flags) { struct flex_array *ret; - int max_size = nr_base_part_ptrs() * __elements_per_part(element_size); + int 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) @@ -114,14 +98,15 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total, ret->element_size = element_size; ret->total_nr_elements = total; if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO)) - memset(ret->parts[0], FLEX_ARRAY_FREE, bytes_left_in_base()); + memset(ret->parts[0], FLEX_ARRAY_FREE, + FLEX_ARRAY_BASE_BYTES_LEFT); return ret; } static int fa_element_to_part_nr(struct flex_array *fa, unsigned int element_nr) { - return element_nr / __elements_per_part(fa->element_size); + return element_nr / FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); } /** @@ -133,11 +118,10 @@ static int fa_element_to_part_nr(struct flex_array *fa, void flex_array_free_parts(struct flex_array *fa) { int part_nr; - int max_part = nr_base_part_ptrs(); if (elements_fit_in_base(fa)) return; - for (part_nr = 0; part_nr < max_part; part_nr++) + for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) kfree(fa->parts[part_nr]); } @@ -152,7 +136,8 @@ static unsigned int index_inside_part(struct flex_array *fa, { unsigned int part_offset; - part_offset = element_nr % __elements_per_part(fa->element_size); + part_offset = element_nr % + FLEX_ARRAY_ELEMENTS_PER_PART(fa->element_size); return part_offset * fa->element_size; } @@ -313,13 +298,12 @@ static int part_is_free(struct flex_array_part *part) int flex_array_shrink(struct flex_array *fa) { struct flex_array_part *part; - int max_part = nr_base_part_ptrs(); int part_nr; int ret = 0; if (elements_fit_in_base(fa)) return ret; - for (part_nr = 0; part_nr < max_part; part_nr++) { + for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) { part = fa->parts[part_nr]; if (!part) continue; -- cgit v1.2.3 From fc0d8d944df0c58cd810f33db82f87dcf5dcc190 Mon Sep 17 00:00:00 2001 From: David Rientjes Date: Mon, 21 Sep 2009 17:04:33 -0700 Subject: flex_array: add missing kerneldoc annotations Add kerneldoc annotations for function formals of type struct flex_array and gfp_t which are currently lacking. Signed-off-by: David Rientjes Cc: Dave Hansen Cc: Randy Dunlap Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/flex_array.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) (limited to 'lib/flex_array.c') diff --git a/lib/flex_array.c b/lib/flex_array.c index b62ce6cffd0a..66eef2e4483e 100644 --- a/lib/flex_array.c +++ b/lib/flex_array.c @@ -46,6 +46,7 @@ static inline int elements_fit_in_base(struct flex_array *fa) * flex_array_alloc - allocate a new flexible array * @element_size: the size of individual elements in the array * @total: total number of elements that this should hold + * @flags: page allocation flags to use for base array * * Note: all locking must be provided by the caller. * @@ -111,6 +112,7 @@ static int fa_element_to_part_nr(struct flex_array *fa, /** * flex_array_free_parts - just free the second-level pages + * @fa: the flex array from which to free parts * * This is to be used in cases where the base 'struct flex_array' * has been statically allocated and should not be free. @@ -159,9 +161,12 @@ __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags) /** * flex_array_put - copy data into the array at @element_nr - * @src: address of data to copy into the array + * @fa: the flex array to copy data into * @element_nr: index of the position in which to insert * the new element. + * @src: address of data to copy into the array + * @flags: page allocation flags to use for array expansion + * * * Note that this *copies* the contents of @src into * the array. If you are trying to store an array of @@ -192,6 +197,7 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src, /** * flex_array_clear - clear element in array at @element_nr + * @fa: the flex array of the element. * @element_nr: index of the position to clear. * * Locking must be provided by the caller. @@ -218,8 +224,10 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr) /** * flex_array_prealloc - guarantee that array space exists + * @fa: the flex array for which to preallocate parts * @start: index of first array element for which space is allocated * @end: index of last (inclusive) element for which space is allocated + * @flags: page allocation flags * * This will guarantee that no future calls to flex_array_put() * will allocate memory. It can be used if you are expecting to @@ -252,6 +260,7 @@ int flex_array_prealloc(struct flex_array *fa, unsigned int start, /** * flex_array_get - pull data back out of the array + * @fa: the flex array from which to extract data * @element_nr: index of the element to fetch from the array * * Returns a pointer to the data at index @element_nr. Note @@ -289,6 +298,7 @@ static int part_is_free(struct flex_array_part *part) /** * flex_array_shrink - free unused second-level pages + * @fa: the flex array to shrink * * Frees all second-level pages that consist solely of unused * elements. Returns the number of pages freed. -- cgit v1.2.3