Adding element to interval map consumes entire memory

Adding element to interval map consumes entire memory

[Richard Mörbitz]

Hello,

first of all: the build in use is the current master
(c89a0801d07740eff531412fe35ea2c9faad82b0).

We have a test setup running which consists of one table ("nat2") and an
interval mapping ("subnettoip") of the type ipv4_addr -> ipv4_addr. The
mapping is quite large (~16000 elements). One requirement of the system
is that elements can be added and deleted during runtime.

With that map constructed, adding a new element is not possible. NFT
will terminate during reallocation, because no memory is left.

GDB trace:
http://pastebin.com/s7eyNEsH

Valgrind leak check:
http://pastebin.com/fkG5UQig

Note that the test machine only has 2 GB of RAM, 1.6 of which are
consumed by nft. So one question is: is it even possible to have enough
memory in the final system, such that the required operation can be
performed?

The second question would be: why is it necessary to allocate that much
memory? As I have found out by reading the code, all map elemtents are
cached before performing the operation; they are even sorted. Is that
really necessary for operations like adding map entries?

Kind regards
Richard

Re: Adding element to interval map consumes entire memory

[Pablo Neira Ayuso]

On Sun, Dec 11, 2016 at 03:20:16PM +0100, Richard Mörbitz wrote:
> Hello,
> 
> first of all: the build in use is the current master
> (c89a0801d07740eff531412fe35ea2c9faad82b0).
> 
> We have a test setup running which consists of one table ("nat2") and an
> interval mapping ("subnettoip") of the type ipv4_addr -> ipv4_addr. The
> mapping is quite large (~16000 elements). One requirement of the system
> is that elements can be added and deleted during runtime.
> 
> With that map constructed, adding a new element is not possible. NFT
> will terminate during reallocation, because no memory is left.
> 
> GDB trace:
> http://pastebin.com/s7eyNEsH
> 
> Valgrind leak check:
> http://pastebin.com/fkG5UQig
> 
> Note that the test machine only has 2 GB of RAM, 1.6 of which are
> consumed by nft. So one question is: is it even possible to have enough
> memory in the final system, such that the required operation can be
> performed?
> 
> The second question would be: why is it necessary to allocate that much
> memory? As I have found out by reading the code, all map elemtents are
> cached before performing the operation; they are even sorted. Is that
> really necessary for operations like adding map entries?

interval code is buggy, I remember to have seen a large memory
allocation being triggered in libgmp calls.

If you can hand over an example that I can use to reproduce I'd
appreciate, I understand this may require some confidentiality, so
feel free to send me a file with randomized addresses or such.

Thanks.

Re: Adding element to interval map consumes entire memory

[Pablo Neira Ayuso]

Hi Richard,

On Mon, Dec 12, 2016 at 04:43:33PM +0100, Richard Mörbitz wrote:
> 
> > interval code is buggy, I remember to have seen a large memory
> > allocation being triggered in libgmp calls.
> 
> These allocations are triggered from the expr_to_intervals function in
> segtree.c - three times, 500 MB each. I have attached the full valgrind
> leak summary to the mail.

I think I found the problem, we have an underflow triggering the
allocation of a huge bitmask, see patch:

http://patchwork.ozlabs.org/patch/705279/

Quickly tested with your example ruleset.

BTW, if you have some spare cycles, I would really appreciate if you
can send a shell test, similar to:

nftables/tests/shell/testcases/sets/0012add_delete_many_elements_0
nftables/tests/shell/testcases/sets/0013add_delete_many_elements_0

It would be great to cover intervals and maps too.

> I also want to point out that calculating overlapping intervals has
> bugs; trying to add a non-overlapping interval can result in the error
> "interval overlaps with an existing one" (function set_overlap,
> segtree.c). However, this should probably become a different thread.

Are you running nft from git.netfilter.org? I just would like to make
sure you're not seeing anything that is already fixed.

I have also posted this patch:

http://patchwork.ozlabs.org/patch/705278/

So nft doesn't complain on exact overlaps to keep it consistent with
non-interval sets. Probably you refering to this?

> > If you can hand over an example that I can use to reproduce I'd
> > appreciate, I understand this may require some confidentiality, so
> > feel free to send me a file with randomized addresses or such.
> 
> I have attached a dummy ruleset that represents the one we use in size
> and shape. You can read it (nft -f test.ruleset) without problems. If
> you attempt to add another map element (say, nft add element nat2
> subnettoip {0.0.0.0/24: 0.0.0.0}) you get the error I have described.
> Of course it depends on the memory of the machine you are using, but you
> should see memory consumption going up drastically.

Thanks for providing the example to reproduce it.

Re: Adding element to interval map consumes entire memory

[Richard Mörbitz]

[-- Attachment #1: Type: text/plain, Size: 1735 bytes --]

Hi Pablo,

> I think I found the problem, we have an underflow triggering the
> allocation of a huge bitmask, see patch:
> 
> http://patchwork.ozlabs.org/patch/705279/

thanks a lot, the patch really fixed the problem!

> BTW, if you have some spare cycles, I would really appreciate if you
> can send a shell test, similar to:
> 
> nftables/tests/shell/testcases/sets/0012add_delete_many_elements_0
> nftables/tests/shell/testcases/sets/0013add_delete_many_elements_0
> 
> It would be great to cover intervals and maps too.

I don't know how to contribute them properly, so I have attached four
tests to this mail. They are based on
sets/0013add_delete_many_elements_0, as
sets/0012add_delete_many_elements_0 fails (it seems like adding and
deleting elements simultaneously causes the whole ruleset to be empty).

maps/map_add_many_elements_0 adds scalar map elements and works always,
so the issue seems to have been in the interval code exclusively.
maps/interval_map_add_many_elements_0 does the same with interval maps -
fails under unpatched master, passes with your patch
maps/interval_map_create_once_0 is the same with only one call to nft,
works under both revisions (!)
maps/interval_map_overlap_0 is for the interval bug, see below

> So nft doesn't complain on exact overlaps to keep it consistent with
> non-interval sets. Probably you refering to this?

No, adding two disjoint intervels led to an error that they would
overlap. Your patch seems to have fixed that as well.

See the maps/interval_map_overlap_0 test. It only adds two map elements,
in two calls to nft. In the unpatched version it doesn't crash due to
memory, but complains about overlap. In the patched version it works.

Thanks again for the fast fix.

[-- Attachment #2: tests.tar --]
[-- Type: application/x-tar, Size: 20480 bytes --]

Re: Adding element to interval map consumes entire memory

[Pablo Neira Ayuso]

Hi Richard,

On Thu, Dec 15, 2016 at 12:52:01AM +0100, Richard Mörbitz wrote:
[...]
> I don't know how to contribute them properly, so I have attached four
> tests to this mail. They are based on
> sets/0013add_delete_many_elements_0, as
> sets/0012add_delete_many_elements_0 fails (it seems like adding and
> deleting elements simultaneously causes the whole ruleset to be empty).

We usually get patches, in the form of git-format-patch, but no
problem I have created a patch based on this tarball. You can now find
it at git.netfilter.org.

Thanks for making these four tests and confirming this bug is now gone!

Re: Adding element to interval map consumes entire memory

[Pablo Neira Ayuso]

[-- Attachment #1: Type: text/plain, Size: 792 bytes --]

On Thu, Dec 15, 2016 at 11:02:38PM +0100, Pablo Neira Ayuso wrote:
> Hi Richard,
> 
> On Thu, Dec 15, 2016 at 12:52:01AM +0100, Richard Mörbitz wrote:
> [...]
> > I don't know how to contribute them properly, so I have attached four
> > tests to this mail. They are based on
> > sets/0013add_delete_many_elements_0, as
> > sets/0012add_delete_many_elements_0 fails (it seems like adding and
> > deleting elements simultaneously causes the whole ruleset to be empty).
> 
> We usually get patches, in the form of git-format-patch, but no
> problem I have created a patch based on this tarball. You can now find
> it at git.netfilter.org.

This is the patch I made. I'm going to keep it back until I solve a
couple of problems that I'm hitting here, will have a look tomorrow
with fresher mind.

[-- Attachment #2: 0001-tests-shell-cover-maps.patch --]
[-- Type: text/x-diff, Size: 7237 bytes --]

>From 22e4f41dd6938a026ce87c2195a21d0067ed6454 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Richard=20M=C3=B6rbitz?= <richard.moerbitz@tu-dresden.de>
Date: Thu, 15 Dec 2016 00:52:01 +0100
Subject: [PATCH] tests: shell: cover maps
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This patch adds four new tests to cover maps and interval maps.

Signed-off-by: Richard Mörbitz <richard.moerbitz@tu-dresden.de>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 .../testcases/maps/0003map_add_many_elements_0     | 61 ++++++++++++++++++++
 .../testcases/maps/0004interval_map_create_once_0  | 60 ++++++++++++++++++++
 .../maps/0005interval_map_add_many_elements_0      | 66 ++++++++++++++++++++++
 .../testcases/maps/0006interval_map_overlap_0      | 41 ++++++++++++++
 4 files changed, 228 insertions(+)
 create mode 100755 tests/shell/testcases/maps/0003map_add_many_elements_0
 create mode 100755 tests/shell/testcases/maps/0004interval_map_create_once_0
 create mode 100755 tests/shell/testcases/maps/0005interval_map_add_many_elements_0
 create mode 100755 tests/shell/testcases/maps/0006interval_map_overlap_0

diff --git a/tests/shell/testcases/maps/0003map_add_many_elements_0 b/tests/shell/testcases/maps/0003map_add_many_elements_0
new file mode 100755
index 000000000000..278d1978eb33
--- /dev/null
+++ b/tests/shell/testcases/maps/0003map_add_many_elements_0
@@ -0,0 +1,61 @@
+#!/bin/bash
+
+# test adding many map elements
+
+HOWMANY=31
+
+tmpfile=$(mktemp)
+if [ ! -w $tmpfile ] ; then
+	echo "Failed to create tmp file" >&2
+	exit 0
+fi
+
+trap "rm -rf $tmpfile" EXIT # cleanup if aborted
+
+generate_add() {
+	echo -n "{"
+	for ((i=1; i<=HOWMANY; i++)) ; do
+		for ((j=1; j<=HOWMANY; j++)) ; do
+			[ "$i" == "$HOWMANY" ] && [ "$j" == "$HOWMANY" ] && break
+			echo -n "10.0.${i}.${j} : 10.0.${i}.${j}, "
+		done
+	done
+	echo -n "}"
+}
+
+generate_test() {
+	elements=""
+	for ((i=HOWMANY; i>=1; i--)) ; do
+		for ((j=HOWMANY; j>=1; j--)) ; do
+			elements="$elements 10.0.${i}.${j} : 10.0.${i}.${j}"
+			[ "$i" == 1 ] && [ "$j" == 1 ] && break
+			elements="${elements}, "
+		done
+	done
+	echo $elements
+}
+
+echo "add table x
+add map x y { type ipv4_addr : ipv4_addr; }
+add element x y $(generate_add)" > $tmpfile
+
+set -e
+$NFT -f $tmpfile
+
+n=$HOWMANY
+echo "add element x y { 10.0.${n}.${n} : 10.0.${n}.${n} }" > $tmpfile
+$NFT -f $tmpfile
+
+EXPECTED="table ip x {
+	map y {
+		type ipv4_addr : ipv4_addr
+		elements = { $(generate_test)}
+	}
+}"
+GET=$($NFT list ruleset)
+if [ "$EXPECTED" != "$GET" ] ; then
+	DIFF="$(which diff)"
+	[ -x $DIFF ] && $DIFF -u <(echo "$EXPECTED") <(echo "$GET")
+	exit 1
+fi
+
diff --git a/tests/shell/testcases/maps/0004interval_map_create_once_0 b/tests/shell/testcases/maps/0004interval_map_create_once_0
new file mode 100755
index 000000000000..7d4877eb6e96
--- /dev/null
+++ b/tests/shell/testcases/maps/0004interval_map_create_once_0
@@ -0,0 +1,60 @@
+#!/bin/bash
+
+# test adding many elements to an interval map
+# this always works because nft is only called once
+
+HOWMANY=63
+
+tmpfile=$(mktemp)
+if [ ! -w $tmpfile ] ; then
+	echo "Failed to create tmp file" >&2
+	exit 0
+fi
+
+trap "rm -rf $tmpfile" EXIT # cleanup if aborted
+
+generate_add() {
+	echo -n "{"
+	for ((i=1; i<=HOWMANY; i++)) ; do
+		for ((j=1; j<=HOWMANY; j++)) ; do
+			echo -n "10.${i}.${j}.0/24 : 10.0.${i}.${j}"
+			[ "$i" == "$HOWMANY" ] && [ "$j" == "$HOWMANY" ] && break
+			echo -n ", "
+		done
+	done
+	echo -n "}"
+}
+
+generate_test() {
+	elements=""
+	for ((i=1; i<=HOWMANY; i++)) ; do
+		for ((j=1; j<=HOWMANY; j++)) ; do
+			elements="$elements 10.${i}.${j}.0/24 : 10.0.${i}.${j}"
+			[ "$i" == "$HOWMANY" ] && [ "$j" == "$HOWMANY" ] && break
+			elements="${elements}, "
+		done
+	done
+	echo $elements
+}
+
+echo "add table x
+add map x y { type ipv4_addr : ipv4_addr; flags interval; }
+add element x y $(generate_add)" > $tmpfile
+
+set -e
+$NFT -f $tmpfile
+
+EXPECTED="table ip x {
+	map y {
+		type ipv4_addr : ipv4_addr
+		flags interval
+		elements = { $(generate_test)}
+	}
+}"
+GET=$($NFT list ruleset)
+if [ "$EXPECTED" != "$GET" ] ; then
+	DIFF="$(which diff)"
+	[ -x $DIFF ] && $DIFF -u <(echo "$EXPECTED") <(echo "$GET")
+	exit 1
+fi
+
diff --git a/tests/shell/testcases/maps/0005interval_map_add_many_elements_0 b/tests/shell/testcases/maps/0005interval_map_add_many_elements_0
new file mode 100755
index 000000000000..824f2c85fb70
--- /dev/null
+++ b/tests/shell/testcases/maps/0005interval_map_add_many_elements_0
@@ -0,0 +1,66 @@
+#!/bin/bash
+
+# test adding many elements to an interval map
+# even with HOWMANY=2 there are memory allocation failures in the current
+# master - the patch fixes that
+# NOTE this is only an issue with two separate nft calls
+
+HOWMANY=2
+
+tmpfile=$(mktemp)
+if [ ! -w $tmpfile ] ; then
+	echo "Failed to create tmp file" >&2
+	exit 0
+fi
+
+trap "rm -rf $tmpfile" EXIT # cleanup if aborted
+
+generate_add() {
+	echo -n "{"
+	for ((i=1; i<=HOWMANY; i++)) ; do
+		for ((j=1; j<=HOWMANY; j++)) ; do
+			[ "$i" == "$HOWMANY" ] && [ "$j" == "$HOWMANY" ] && break
+			echo -n "10.${i}.${j}.0/24 : 10.0.${i}.${j}, "
+		done
+	done
+	echo -n "}"
+}
+
+generate_test() {
+	elements=""
+	for ((i=1; i<=HOWMANY; i++)) ; do
+		for ((j=1; j<=HOWMANY; j++)) ; do
+			elements="$elements 10.${i}.${j}.0/24 : 10.0.${i}.${j}"
+			[ "$i" == "$HOWMANY" ] && [ "$j" == "$HOWMANY" ] && break
+			elements="${elements}, "
+		done
+	done
+	echo $elements
+}
+
+echo "add table x
+add map x y { type ipv4_addr : ipv4_addr; flags interval; }
+add element x y $(generate_add)" > $tmpfile
+
+set -e
+$NFT -f $tmpfile
+
+n=$HOWMANY
+echo "add element x y { 10.${n}.${n}.0/24 : 10.0.${n}.${n} }" > $tmpfile
+
+$NFT -f $tmpfile
+
+EXPECTED="table ip x {
+	map y {
+		type ipv4_addr : ipv4_addr
+		flags interval
+		elements = { $(generate_test)}
+	}
+}"
+GET=$($NFT list ruleset)
+if [ "$EXPECTED" != "$GET" ] ; then
+	DIFF="$(which diff)"
+	[ -x $DIFF ] && $DIFF -u <(echo "$EXPECTED") <(echo "$GET")
+	exit 1
+fi
+
diff --git a/tests/shell/testcases/maps/0006interval_map_overlap_0 b/tests/shell/testcases/maps/0006interval_map_overlap_0
new file mode 100755
index 000000000000..c1bf3de111ac
--- /dev/null
+++ b/tests/shell/testcases/maps/0006interval_map_overlap_0
@@ -0,0 +1,41 @@
+#!/bin/bash
+
+# test adding elements to an interval map
+# shows how disjoint intervals are seen as overlaps
+# NOTE this is only an issue with two separate nft calls
+
+tmpfile=$(mktemp)
+if [ ! -w $tmpfile ] ; then
+	echo "Failed to create tmp file" >&2
+	exit 0
+fi
+
+trap "rm -rf $tmpfile" EXIT # cleanup if aborted
+
+n=1
+echo "add table x
+add map x y { type ipv4_addr : ipv4_addr; flags interval; }
+add element x y { 10.0.${n}.0/24 : 10.0.0.${n} }" > $tmpfile
+
+set -e
+$NFT -f $tmpfile
+
+n=2
+echo "add element x y { 10.0.${n}.0/24 : 10.0.0.${n} }" > $tmpfile
+
+$NFT -f $tmpfile
+
+EXPECTED="table ip x {
+	map y {
+		type ipv4_addr : ipv4_addr
+		flags interval
+		elements = { 10.0.1.0/24 : 10.0.0.1, 10.0.2.0/24 : 10.0.0.2}
+	}
+}"
+GET=$($NFT list ruleset)
+if [ "$EXPECTED" != "$GET" ] ; then
+	DIFF="$(which diff)"
+	[ -x $DIFF ] && $DIFF -u <(echo "$EXPECTED") <(echo "$GET")
+	exit 1
+fi
+
-- 
2.1.4