From: Pablo Neira Ayuso <pablo@netfilter.org>
To: "Richard Mörbitz" <richard.moerbitz@tu-dresden.de>
Cc: netfilter-devel@vger.kernel.org
Subject: Re: Adding element to interval map consumes entire memory
Date: Thu, 15 Dec 2016 23:47:30 +0100 [thread overview]
Message-ID: <20161215224730.GA3663@salvia> (raw)
In-Reply-To: <20161215220238.GA25865@salvia>
[-- 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
prev parent reply other threads:[~2016-12-15 22:47 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-11 14:20 Adding element to interval map consumes entire memory Richard Mörbitz
2016-12-11 19:28 ` Pablo Neira Ayuso
[not found] ` <3acabb81-c5b5-2004-18ce-8b5242f07921@tu-dresden.de>
2016-12-13 0:48 ` Pablo Neira Ayuso
2016-12-14 23:52 ` Richard Mörbitz
2016-12-15 22:02 ` Pablo Neira Ayuso
2016-12-15 22:47 ` Pablo Neira Ayuso [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20161215224730.GA3663@salvia \
--to=pablo@netfilter.org \
--cc=netfilter-devel@vger.kernel.org \
--cc=richard.moerbitz@tu-dresden.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.