[PATCH net 0/3] net: add support for flex_array_resize in flex_array

[PATCH net 0/3] net: add support for flex_array_resize in flex_array

[Xin Long]

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.

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(-)

-- 
2.1.0

[PATCH net 1/3] flex_array: make FLEX_ARRAY_BASE_SIZE the same value of FLEX_ARRAY_PART_SIZE

[Xin Long]

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.

Suggested-by: Neil Horman <nhorman@tuxdriver.com>
Signed-off-by: Xin Long <lucien.xin@gmail.com>
---
 include/linux/flex_array.h | 29 +++++++++--------------------
 lib/flex_array.c           | 15 ++++++++++++---
 2 files changed, 21 insertions(+), 23 deletions(-)

diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
index b94fa61..29ad65f 100644
--- a/include/linux/flex_array.h
+++ b/include/linux/flex_array.h
@@ -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_SIZE
 
 struct 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)				\
diff --git a/lib/flex_array.c b/lib/flex_array.c
index 2eed22f..8c0b9b6 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -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);
-- 
2.1.0

[PATCH net 2/3] flex_array: support flex_array_resize

[Xin Long]

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.

Suggested-by: Neil Horman <nhorman@tuxdriver.com>
Signed-off-by: Xin Long <lucien.xin@gmail.com>
---
 include/linux/flex_array.h | 11 +++++++++
 lib/flex_array.c           | 58 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 69 insertions(+)

diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
index 29ad65f..19ff58d 100644
--- a/include/linux/flex_array.h
+++ b/include/linux/flex_array.h
@@ -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)
 
diff --git a/lib/flex_array.c b/lib/flex_array.c
index 8c0b9b6..2f913e7 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -405,3 +405,61 @@ int flex_array_shrink(struct flex_array *fa)
 	return ret;
 }
 EXPORT_SYMBOL(flex_array_shrink);
+
+/**
+ * flex_array_resize - resize without the old elements memory changed
+ * @fa:		the flex array to resize
+ * @total:	total number of elements that this would change to
+ * @flags:	page allocation flags to use for base array
+ *
+ * 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.
+ *
+ * Locking must be provided by the caller.
+ */
+int flex_array_resize(struct flex_array *fa, unsigned int total, gfp_t flags)
+{
+	int nr;
+
+	if (total > FLEX_ARRAY_NR_BASE_PTRS * fa->elems_per_part)
+		return -EINVAL;
+
+	if (elements_fit_in_base(fa)) {
+		struct flex_array_part_p *part_p;
+
+		nr = fa->total_nr_elements;
+		fa->total_nr_elements = total;
+		if (elements_fit_in_base(fa))
+			return 0;
+
+		part_p = kzalloc(sizeof(*part_p), flags);
+		if (!part_p) {
+			fa->total_nr_elements = nr;
+			return -ENOMEM;
+		}
+
+		part_p->p_part[0] = (struct flex_array_part *)&fa->parts[0];
+		fa->part_p = part_p;
+	} else {
+		struct flex_array_part *part;
+
+		fa->total_nr_elements = total;
+		if (!elements_fit_in_base(fa))
+			return 0;
+
+		for (nr = 1; nr < FLEX_ARRAY_NR_BASE_PTRS; nr++) {
+			part = fa->parts[nr];
+			if (part) {
+				fa->parts[nr] = NULL;
+				kfree(part);
+			}
+		}
+
+		fa->part_p = (struct flex_array_part_p *)fa->parts[0];
+	}
+
+	return 0;
+}
+EXPORT_SYMBOL(flex_array_resize);
-- 
2.1.0

[PATCH net 3/3] sctp: fa_resize sctp stream instead of redo fa_alloc

[Xin Long]

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.

Fixes: 5bbbbe32a431 ("sctp: introduce stream scheduler foundations")
Reported-by: Ying Xu <yinxu@redhat.com>
Reported-by: syzbot+e33a3a138267ca119c7d@syzkaller.appspotmail.com
Suggested-by: Neil Horman <nhorman@tuxdriver.com>
Signed-off-by: Xin Long <lucien.xin@gmail.com>
---
 net/sctp/stream.c | 87 +++++++++++++++++++++++++------------------------------
 1 file changed, 40 insertions(+), 47 deletions(-)

diff --git a/net/sctp/stream.c b/net/sctp/stream.c
index 3892e76..aff30b2 100644
--- a/net/sctp/stream.c
+++ b/net/sctp/stream.c
@@ -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,
-- 
2.1.0

Re: [PATCH net 0/3] net: add support for flex_array_resize in flex_array

[Neil Horman]

On Wed, Dec 05, 2018 at 02:49:39PM +0800, Xin Long wrote:
> 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.
> 
> 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(-)
> 
> -- 
> 2.1.0
> 
> 
Series
Acked-by: Neil Horman <nhorman@tuxdriver.com>

Re: [PATCH net 1/3] flex_array: make FLEX_ARRAY_BASE_SIZE the same value of FLEX_ARRAY_PART_SIZE

[David Miller]

From: Xin Long <lucien.xin@gmail.com>
Date: Wed,  5 Dec 2018 14:49:40 +0800

> 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.
> 
> Suggested-by: Neil Horman <nhorman@tuxdriver.com>
> Signed-off-by: Xin Long <lucien.xin@gmail.com>

This needs to be reviewed by the flex array hackers and lkml.

It can't just get reviewed on netdev alone.

Re: [PATCH net 1/3] flex_array: make FLEX_ARRAY_BASE_SIZE the same value of FLEX_ARRAY_PART_SIZE

[Xin Long]

On Thu, Dec 6, 2018 at 1:38 PM David Miller <davem@davemloft.net> wrote:
>
> From: Xin Long <lucien.xin@gmail.com>
> Date: Wed,  5 Dec 2018 14:49:40 +0800
>
> > 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.
> >
> > Suggested-by: Neil Horman <nhorman@tuxdriver.com>
> > Signed-off-by: Xin Long <lucien.xin@gmail.com>
>
> This needs to be reviewed by the flex array hackers and lkml.
>
> It can't just get reviewed on netdev alone.
Will repost with CCing lkml and
the author:
  "Dave Hansen <dave.hansen@linux.intel.com>"
and two contributors:
  "David Rientjes <rientjes@google.com>", "Eric Paris <eparis@redhat.com>"

Thanks.