[PATCH v2 0/2] segtree: move huge arrays to heap

[PATCH v2 0/2] segtree: move huge arrays to heap

[Oleksandr Natalenko]

While dealing with huge sets, nft may exhaust stack
and trigger segfault. To avoid this, lets move those
huge arrays away from stack to heap.

First patch introduces array allocation helper.

Second patch modifies interval_map_decompose()
function, allocating memory for arrays on head.

Meny thanks to Florian Westphal who helped
to sort this out.

Changelog:

v2: nmemb actually can be 0, so remove that
    assertion

v1: initial submission

Oleksandr Natalenko (2):
  utils: provide array allocation wrapper
  segtree: allocate memory for arrays on heap

 include/utils.h |  1 +
 src/segtree.c   |  8 +++++++-
 src/utils.c     | 10 ++++++++++
 3 files changed, 18 insertions(+), 1 deletion(-)

-- 
2.11.0

[PATCH v2 1/2] utils: provide array allocation wrapper

[Oleksandr Natalenko]

This will be used for allocating memory for arrays
in heap instead of keeping them on stack.

Signed-off-by: Oleksandr Natalenko <oleksandr@natalenko.name>
---
 include/utils.h |  1 +
 src/utils.c     | 10 ++++++++++
 2 files changed, 11 insertions(+)

diff --git a/include/utils.h b/include/utils.h
index bb58ba4..3199388 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -138,6 +138,7 @@ extern void __memory_allocation_error(const char *filename, uint32_t line) __nor
 
 extern void xfree(const void *ptr);
 extern void *xmalloc(size_t size);
+extern void *xmalloc_array(size_t nmemb, size_t size);
 extern void *xrealloc(void *ptr, size_t size);
 extern void *xzalloc(size_t size);
 extern char *xstrdup(const char *s);
diff --git a/src/utils.c b/src/utils.c
index 65dabf4..16bc9e2 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -39,6 +39,16 @@ void *xmalloc(size_t size)
 	return ptr;
 }
 
+void *xmalloc_array(size_t nmemb, size_t size)
+{
+	assert(size != 0);
+
+	if (nmemb > SIZE_MAX / size)
+		memory_allocation_error();
+
+	return xmalloc(nmemb * size);
+}
+
 void *xrealloc(void *ptr, size_t size)
 {
 	ptr = realloc(ptr, size);
-- 
2.11.0

[PATCH v2 2/2] segtree: allocate memory for arrays on heap

[Oleksandr Natalenko]

Huge sets may cause stack to be exhausted.
So, put allocate memory for arrays in
interval_map_decompose() function on heap.

Signed-off-by: Oleksandr Natalenko <oleksandr@natalenko.name>
---
 src/segtree.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/src/segtree.c b/src/segtree.c
index 5b6cdd1..d3873d9 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -608,12 +608,15 @@ static int expr_value_cmp(const void *p1, const void *p2)
 
 void interval_map_decompose(struct expr *set)
 {
-	struct expr *elements[set->size], *ranges[set->size * 2];
+	struct expr **elements, **ranges;
 	struct expr *i, *next, *low = NULL, *end;
 	unsigned int n, m, size;
 	mpz_t range, p;
 	bool interval;
 
+	elements = xmalloc_array(set->size, sizeof(struct expr *));
+	ranges = xmalloc_array(set->size * 2, sizeof(struct expr *));
+
 	mpz_init(range);
 	mpz_init(p);
 
@@ -728,4 +731,7 @@ void interval_map_decompose(struct expr *set)
 
 		compound_expr_add(set, i);
 	}
+
+	xfree(ranges);
+	xfree(elements);
 }
-- 
2.11.0

Re: [PATCH v2 0/2] segtree: move huge arrays to heap

[Florian Westphal]

Oleksandr Natalenko <oleksandr@natalenko.name> wrote:
> While dealing with huge sets, nft may exhaust stack
> and trigger segfault. To avoid this, lets move those
> huge arrays away from stack to heap.
> 
> First patch introduces array allocation helper.
> 
> Second patch modifies interval_map_decompose()
> function, allocating memory for arrays on head.
> 
> Meny thanks to Florian Westphal who helped
> to sort this out.

Applied, thanks a lot!  I used v1 of first patch (retaining assert()
of nmemb) and added an early return on v2 so decompose step doesn't do
anything on empty arrays, let me know if you spot a problem with it.