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

[PATCH 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.

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     | 11 +++++++++++
 3 files changed, 19 insertions(+), 1 deletion(-)

-- 
2.11.0

[PATCH 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     | 11 +++++++++++
 2 files changed, 12 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..9e8866d 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -39,6 +39,17 @@ void *xmalloc(size_t size)
 	return ptr;
 }
 
+void *xmalloc_array(size_t nmemb, size_t size)
+{
+	assert(nmemb != 0);
+	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 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