net: add support for flex_array_resize in flex_array
Subsystems (4)
Xin Long
maintainerv2 cover net: add support for flex_array_resize in flex_array
Without the support for the total_nr_elements's growing or shrinking dynamically, flex_array is not that 'flexible'. Like when users want to change the size, they have to redo flex_array_alloc and copy all the elements from the old to the new one. The worse thing is every element's memory gets changed.
To implement flex_array_resize based on current code, the difficult thing is to process the size border of FLEX_ARRAY_BASE_BYTES_LEFT, where the base data memory may change to an array for the 2nd level data memory for growing, likewise for shrinking.
To make this part easier, we separate the base data memory and define FLEX_ARRAY_BASE_SIZE as a same value of FLEX_ARRAY_PART_SIZE, as Neil suggested. When new size is crossing the border, the base memory is allocated as the array for the 2nd level data memory and its part[0] is pointed to the old base memory, and do the opposite for shrinking.
But it doesn't do any memory allocation or shrinking for elements in flex_array_resize, as which should be done by flex_array_prealloc or flex_array_shrink called by users. No memory leaks can be caused by that.
SCTP has benefited a lot from flex_array_resize() for managing its stream memory so far.
v1->v2:
Cc LKML and more developers.
Xin Long (3):
flex_array: make FLEX_ARRAY_BASE_SIZE the same value of
FLEX_ARRAY_PART_SIZE
flex_array: support flex_array_resize
sctp: fa_resize sctp stream instead of redo fa_alloc
include/linux/flex_array.h | 40 ++++++++++----------- lib/flex_array.c | 73 ++++++++++++++++++++++++++++++++++++-- net/sctp/stream.c | 87 +++++++++++++++++++++------------------------- 3 files changed, 130 insertions(+), 70 deletions(-)
Signature · 1 line
2.1.0
Xin Long
maintainerPATCH v2 1/3 flex_array: make FLEX_ARRAY_BASE_SIZE the same value of FLEX_ARRAY_PART_SIZE
This patch is to separate the base data memory from struct flex_array and save it into a page. With this change, total_nr_elements of a flex_array can grow or shrink without having the old element's memory changed when the new size of the flex_arry crosses FLEX_ARRAY_BASE_SIZE, which will be added in the next patch.
--- include/linux/flex_array.h | 29 +++++++++-------------------- lib/flex_array.c | 15 ++++++++++++--- 2 files changed, 21 insertions(+), 23 deletions(-)
include/linux/flex_array.h +9 -20
@@ -7,9 +7,10 @@#include <asm/page.h> #define FLEX_ARRAY_PART_SIZE PAGE_SIZE -#define FLEX_ARRAY_BASE_SIZE PAGE_SIZE +#define FLEX_ARRAY_BASE_SIZE FLEX_ARRAY_PART_SIZEstruct flex_array_part ; +struct flex_array_part_p ;/* * This is meant to replace cases where an array-like
@@ -19,29 +20,17 @@ struct flex_array_part;*/ struct flex_array { -union { -struct { -int element_size; -int total_nr_elements; -int elems_per_part; -struct reciprocal_value reciprocal_elems; -struct flex_array_part *parts[]; - }; -/* -* This little trick makes sure that -* sizeof(flex_array) = PAGE_SIZE -*/ -char padding[FLEX_ARRAY_BASE_SIZE ]; - }; +int element_size; +int total_nr_elements; +int elems_per_part; +struct reciprocal_value reciprocal_elems; +struct flex_array_part_p *part_p; +#define parts part_p->p_part }; -/* 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 *)) + (FLEX_ARRAY_BASE_SIZE / sizeof(struct flex_array_part *))/* Number of elements of size that fit in struct flex_array_part */ #define FLEX_ARRAY_ELEMENTS_PER_PART (size) \
lib/flex_array.c +12 -3
@@ -30,6 +30,10 @@ struct flex_array_part {char elements[FLEX_ARRAY_PART_SIZE ]; }; +struct flex_array_part_p { +struct flex_array_part *p_part[FLEX_ARRAY_NR_BASE_PTRS ]; +}; +/* * If a user requests an allocation which is small * enough, we may simply use the space in the
@@ -39,7 +43,7 @@ struct flex_array_part {static inline int elements_fit_in_base (struct flex_array *fa) {int data_size = fa->element_size * fa->total_nr_elements; -if (data_size <=FLEX_ARRAY_BASE_BYTES_LEFT ) +if (data_size <=FLEX_ARRAY_BASE_SIZE )return 1 ;return 0 ; }
@@ -105,13 +109,17 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total, ret =kzalloc (sizeof (struct flex_array ), flags);if (!ret)return NULL ; + ret->part_p =kzalloc (sizeof (struct flex_array_part_p ), flags); +if (!ret->part_p) { +kfree (ret); +return NULL ; + } ret->element_size = element_size; ret->total_nr_elements = total; ret->elems_per_part = elems_per_part; ret->reciprocal_elems = reciprocal_elems;if (elements_fit_in_base (ret) && !(flags & __GFP_ZERO)) -memset (&ret->parts[0 ],FLEX_ARRAY_FREE , -FLEX_ARRAY_BASE_BYTES_LEFT ); +memset (&ret->parts[0 ],FLEX_ARRAY_FREE ,FLEX_ARRAY_BASE_SIZE );return ret; }EXPORT_SYMBOL (flex_array_alloc);
@@ -148,6 +156,7 @@ EXPORT_SYMBOL(flex_array_free_parts);void flex_array_free (struct flex_array *fa) {flex_array_free_parts (fa); +kfree (fa->part_p);kfree (fa); }EXPORT_SYMBOL (flex_array_free);
Signature · 1 line
2.1.0
Xin Long
maintainerPATCH v2 2/3 flex_array: support flex_array_resize
This function can dynamically change total_nr_elements of a flex_array, and keep the old elements of the same memory. Returns 0 if it succeeds.
Note that it won't do any memory allocation or shrinking for elements, which should be only done by flex_array_prealloc and flex_array_shrink.
--- include/linux/flex_array.h | 11 +++++++++ lib/flex_array.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 69 insertions(+)
include/linux/flex_array.h +11 -0
@@ -130,6 +130,17 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr);*/ int flex_array_shrink (struct flex_array *fa); +/** +* flex_array_resize() - Resize without the old elements memory changed +* @fa: array to resize +* @total: total number of elements that this would change to +* @flags: page allocation flags to use for base array +* +* Return: Returns 0 if it succeeds. +* +*/ +int flex_array_resize (struct flex_array *fa,unsigned int total,gfp_t flags); +#define flex_array_put_ptr (fa, nr, src, gfp) \ flex_array_put(fa, nr, (void *)&(src), gfp)
lib/flex_array.c +58 -0
61 lines not on this page · raw message
Signature · 1 line
2.1.0
Xin Long
maintainerPATCH v2 3/3 sctp: fa_resize sctp stream instead of redo fa_alloc
Now when doing 4-shakehand or adding new streams, sctp has to allocate new memory for asoc->stream and copy the old stream's information from the old asoc->stream to the new one. It also cause the stream pointers to change, by which a panic was even caused due to stream->out_curr's change.
To fix this, flex_array_resize() is used in sctp_stream_alloc_out/in() when asoc->stream has been allocated. Besides, with this asoc->stream will only be allocated once, and grow or shrink dynamically later.
Note that flex_array_prealloc() is needed before growing as fa_alloc does, while flex_array_clear() and flex_array_shrink() are called to free the unused memory before shrinking.
--- net/sctp/stream.c | 87 +++++++++++++++++++++++++------------------------------ 1 file changed, 40 insertions(+), 47 deletions(-)
net/sctp/stream.c +40 -47
@@ -37,6 +37,17 @@#include <net/sctp/sm.h> #include <net/sctp/stream_sched.h> +static void fa_zero (struct flex_array *fa,size_t index,size_t count) +{ +void *elem; + +while (count--) { + elem =flex_array_get (fa, index); +memset (elem,0 , fa->element_size); + index++; + } +} +static struct flex_array *fa_alloc (size_t elem_size,size_t elem_count,gfp_t gfp) {
@@ -48,8 +59,9 @@ static struct flex_array *fa_alloc(size_t elem_size, size_t elem_count, err =flex_array_prealloc (result,0 , elem_count, gfp);if (err) {flex_array_free (result); - result =NULL ; +return NULL ; } +fa_zero (result,0 , elem_count); }return result;
@@ -61,27 +73,28 @@ static void fa_free(struct flex_array *fa)flex_array_free (fa); } -static void fa_copy (struct flex_array *fa,struct flex_array *from, -size_t index,size_t count) +static int fa_resize (struct flex_array *fa,size_t count,gfp_t gfp) { -void *elem; +int nr = fa->total_nr_elements, n; -while (count--) { - elem =flex_array_get (from, index); -flex_array_put (fa, index, elem,0 ); - index++; +if (count > nr) { +if (flex_array_resize (fa, count, gfp)) +return -ENOMEM ; +if (flex_array_prealloc (fa, nr, count - nr, gfp)) +return -ENOMEM ; +fa_zero (fa, nr, count - nr); + +return 0 ; } -} -static void fa_zero (struct flex_array *fa,size_t index,size_t count) -{ -void *elem; +/* Shrink the unused memory, +* FLEX_ARRAY_FREE check is safe for sctp stream. +*/ +for (n = count; n < nr; n++) +flex_array_clear (fa, n); +flex_array_shrink (fa); -while (count--) { - elem =flex_array_get (fa, index); -memset (elem,0 , fa->element_size); - index++; - } +return flex_array_resize (fa, count, gfp); }/* Migrates chunks from stream queues to new stream queues if needed,
@@ -138,47 +151,27 @@ static void sctp_stream_outq_migrate(struct sctp_stream *stream,static int sctp_stream_alloc_out (struct sctp_stream *stream,__u16 outcnt,gfp_t gfp) { -struct flex_array *out; -size_t elem_size =sizeof (struct sctp_stream_out ); - - out =fa_alloc (elem_size, outcnt, gfp); -if (!out) -return -ENOMEM ; +if (!stream->out) { + stream->out =fa_alloc (sizeof (struct sctp_stream_out ), + outcnt, gfp); -if (stream->out) { -fa_copy (out, stream->out,0 ,min (outcnt, stream->outcnt)); -fa_free (stream->out); +return stream->out ?0 : -ENOMEM ; } -if (outcnt > stream->outcnt) -fa_zero (out, stream->outcnt, (outcnt - stream->outcnt)); - - stream->out = out; - -return 0 ; +return fa_resize (stream->out, outcnt, gfp); }static int sctp_stream_alloc_in (struct sctp_stream *stream,__u16 incnt,gfp_t gfp) { -struct flex_array *in; -size_t elem_size =sizeof (struct sctp_stream_in ); +if (!stream->in) { + stream->in =fa_alloc (sizeof (struct sctp_stream_in ), + incnt, gfp); - in =fa_alloc (elem_size, incnt, gfp); -if (!in) -return -ENOMEM ; - -if (stream->in) { -fa_copy (in, stream->in,0 ,min (incnt, stream->incnt)); -fa_free (stream->in); +return stream->in ?0 : -ENOMEM ; } -if (incnt > stream->incnt) -fa_zero (in, stream->incnt, (incnt - stream->incnt)); - - stream->in = in; - -return 0 ; +return fa_resize (stream->in, incnt, gfp); } int sctp_stream_init(struct sctp_stream *stream, __u16 outcnt, __u16 incnt,
Signature · 1 line
2.1.0
Kent Overstreet had a patch set to completely remove flex arrays:
[email protected]
I wonder where that set went.
David Miller
maintainerFrom: Xin Long <[email protected]>
Date: Fri, 7 Dec 2018 14:30:32 +0800
Quoted 22 lines
Without the support for the total_nr_elements's growing or shrinking dynamically,
flex_arrayis not that 'flexible'. Like when users want to change the size, they have to redoflex_array_allocand copy all the elements from the old to the new one. The worse thing is every element's memory gets changed.To implement
flex_array_resizebased on current code, the difficult thing is to process the size border ofFLEX_ARRAY_BASE_BYTES_LEFT, where the base data memory may change to an array for the 2nd level data memory for growing, likewise for shrinking.To make this part easier, we separate the base data memory and define
FLEX_ARRAY_BASE_SIZEas a same value ofFLEX_ARRAY_PART_SIZE, as Neil suggested. When new size is crossing the border, the base memory is allocated as the array for the 2nd level data memory and its part[0] is pointed to the old base memory, and do the opposite for shrinking.But it doesn't do any memory allocation or shrinking for elements in
flex_array_resize, as which should be done byflex_array_preallocorflex_array_shrinkcalled by users. No memory leaks can be caused by that.
Quoted 5 lines
SCTP has benefited a lot from
flex_array_resize()for managing its stream memory so far.
v1->v2:
Cc LKML and more developers.
So I don't know what to do about this series.
One of the responses stated that it has been proposed to remove flex_array and I don't know what to make of that, nor can I tell if that makes this series inappropriate or not.
Quoted 28 lines · David Miller
From: Xin Long <[email protected]>
Date: Fri, 7 Dec 2018 14:30:32 +0800Quoted 25 lines
Without the support for the total_nr_elements's growing or shrinking dynamically,
flex_arrayis not that 'flexible'. Like when users want to change the size, they have to redoflex_array_allocand copy all the elements from the old to the new one. The worse thing is every element's memory gets changed.To implement
flex_array_resizebased on current code, the difficult thing is to process the size border ofFLEX_ARRAY_BASE_BYTES_LEFT, where the base data memory may change to an array for the 2nd level data memory for growing, likewise for shrinking.To make this part easier, we separate the base data memory and define
FLEX_ARRAY_BASE_SIZEas a same value ofFLEX_ARRAY_PART_SIZE, as Neil suggested. When new size is crossing the border, the base memory is allocated as the array for the 2nd level data memory and its part[0] is pointed to the old base memory, and do the opposite for shrinking.But it doesn't do any memory allocation or shrinking for elements in
flex_array_resize, as which should be done byflex_array_preallocorflex_array_shrinkcalled by users. No memory leaks can be caused by that.SCTP has benefited a lot from
flex_array_resize()for managing its stream memory so far.
Quoted 9 lines
Quoted 2 lines
v1->v2:
Cc LKML and more developers.So I don't know what to do about this series.
One of the responses stated that it has been proposed to remove
flex_arrayand I don't know what to make of that, nor can I tell if that makes this series inappropriate or not.
I suggest xin respond to messageid [email protected]> and send a NAK, indicating that his patch seems like it will break the build, as, looking through it, it never removes flex_array calls from the sctp code. If kent reposts with a conversion of the sctp code to radix trees, we're done. If not, you can move forward with this commit.
Neil
David Miller
maintainerFrom: Neil Horman <[email protected]>
Date: Wed, 12 Dec 2018 07:00:15 -0500
Quoted 6 lines
I suggest xin respond to messageid [email protected]> and send a NAK, indicating that his patch seems like it will break the build, as, looking through it, it never removes
flex_arraycalls from the sctp code. If kent reposts with a conversion of the sctp code to radix trees, we're done. If not, you can move forward with this commit.
Ok, Xin please do that so we can more forward.
Thanks Neil.