nat: Introduce a prefix lookup tree (trie) for number rewriting

* It is a trie. The max depth of the trie is the length of the
longest prefix. The lookup is O(lookuped_prefix), but as the prefix
length is limited, the lookup time is constant.

* Each node can hold the entire prefix, has place for the rewrite
  rule with up to three digits.

* A trie with 20k entries will take about 3MB ram.

* Filling the trie 100 times takes ~800ms on my i7 laptop

* 10.000.000 lookups take 315ms.. (for the same prefix).

* 93/99 lines are tested, 6/6 functions are tested, 49 of 54 branches
  are tested. Only memory allocation failures are not covered

* A late addition is to handle the '+' sign and to increase the number
  of chars in the rewrite prefix. The timing/line coverage has not
  been updated after this change.

6 files changed, 159 insertions, 1 deletions

diff --git a/openbsc/tests/Makefile.am b/openbsc/tests/Makefile.am
index c9afeedd4..0597c14d0 100644
--- a/openbsc/tests/Makefile.am
+++ b/openbsc/tests/Makefile.am
@@ -1,7 +1,7 @@
 SUBDIRS = gsm0408 db channel mgcp gprs si abis
 
 if BUILD_NAT
-SUBDIRS += bsc-nat
+SUBDIRS += bsc-nat bsc-nat-trie
 endif
 
 if BUILD_SMPP
diff --git a/openbsc/tests/bsc-nat-trie/Makefile.am b/openbsc/tests/bsc-nat-trie/Makefile.am
new file mode 100644
index 000000000..355ed6441
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/Makefile.am
@@ -0,0 +1,18 @@
+AM_CPPFLAGS = $(all_includes) -I$(top_srcdir)/include
+AM_CFLAGS=-Wall -ggdb3 $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGSM_CFLAGS) $(LIBOSMOSCCP_CFLAGS) $(LIBOSMOABIS_CFLAGS) $(COVERAGE_CFLAGS)
+AM_LDFLAGS = $(COVERAGE_LDFLAGS)
+
+EXTRA_DIST = bsc_nat_trie_test.ok prefixes.csv
+
+noinst_PROGRAMS = bsc_nat_trie_test
+
+bsc_nat_trie_test_SOURCES = bsc_nat_trie_test.c \
+			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
+bsc_nat_trie_test_LDADD = $(top_builddir)/src/libbsc/libbsc.a \
+			$(top_srcdir)/src/libctrl/libctrl.a \
+			$(top_srcdir)/src/libmgcp/libmgcp.a \
+			$(top_srcdir)/src/libtrau/libtrau.a \
+			$(top_srcdir)/src/libcommon/libcommon.a \
+			$(LIBOSMOCORE_LIBS) $(LIBOSMOGSM_LIBS) -lrt \
+			$(LIBOSMOSCCP_LIBS) $(LIBOSMOVTY_LIBS) \
+			$(LIBOSMOABIS_LIBS)
diff --git a/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c
new file mode 100644
index 000000000..4b4df2faf
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c
@@ -0,0 +1,87 @@
+/*
+ * (C) 2013 by On-Waves
+ * (C) 2013 by Holger Hans Peter Freyther <zecke@selfish.org>
+ * All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <openbsc/nat_rewrite_trie.h>
+#include <openbsc/debug.h>
+
+#include <osmocom/core/application.h>
+#include <osmocom/core/backtrace.h>
+#include <osmocom/core/talloc.h>
+#include <osmocom/core/utils.h>
+
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+	struct nat_rewrite *trie;
+
+	osmo_init_logging(&log_info);
+
+	printf("Testing the trie\n");
+
+	trie = nat_rewrite_parse(NULL, "prefixes.csv");
+	OSMO_ASSERT(trie);
+
+	/* verify that it has been parsed */
+	OSMO_ASSERT(trie->prefixes == 17);
+	printf("Dumping the internal trie\n");
+	nat_rewrite_dump(trie);
+
+	/* now do the matching... */
+	OSMO_ASSERT(!nat_rewrite_lookup(trie, ""));
+	OSMO_ASSERT(!nat_rewrite_lookup(trie, "2"));
+
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1")->rewrite, "1") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12")->rewrite, "2") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123")->rewrite, "3") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234")->rewrite, "4") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345")->rewrite, "5") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123456")->rewrite, "6") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234567")->rewrite, "7") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678")->rewrite, "8") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123456789")->rewrite, "9") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234567890")->rewrite, "10") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "13")->rewrite, "11") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "14")->rewrite, "12") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "15")->rewrite, "13") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "16")->rewrite, "14") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "823455")->rewrite, "15") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "82")->rewrite, "16") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "+49123445")->rewrite, "17") == 0);
+
+	/* match a prefix */
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "121")->rewrite, "2") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1292323")->rewrite, "2") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678901")->rewrite, "10") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "160")->rewrite, "14") == 0);
+
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678901123452123123")->rewrite, "10") == 0);
+
+	/* invalid input */
+	OSMO_ASSERT(!nat_rewrite_lookup(trie, "12abc"));
+
+	talloc_free(trie);
+
+	trie = nat_rewrite_parse(NULL, "does_not_exist.csv");
+	OSMO_ASSERT(!trie);
+
+	printf("Done with the tests.\n");
+	return 0;
+}
diff --git a/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok
new file mode 100644
index 000000000..4d4cc9949
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok
@@ -0,0 +1,20 @@
+Testing the trie
+Dumping the internal trie
+1,1
+12,2
+123,3
+1234,4
+12345,5
+123456,6
+1234567,7
+12345678,8
+123456789,9
+1234567890,10
+13,11
+14,12
+15,13
+16,14
+82,16
+823455,15
++49123,17
+Done with the tests.
diff --git a/openbsc/tests/bsc-nat-trie/prefixes.csv b/openbsc/tests/bsc-nat-trie/prefixes.csv
new file mode 100644
index 000000000..35485b1a3
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/prefixes.csv
@@ -0,0 +1,25 @@
+1,1
+12,2
+123,3
+1234,4
+12345,5
+123456,6
+1234567,7
+12345678,8
+123456789,9
+1234567890,10
+13,11
+14,12
+15,13
+16,14
+823455,15
+82,16
++49123,17
+1ABC,18
+12345678901234567890,19
+,20
+14A,21
+124,324324324234
+1234567890,10
+no line
+99,
diff --git a/openbsc/tests/testsuite.at b/openbsc/tests/testsuite.at
index ea3fa1ce5..148b3d369 100644
--- a/openbsc/tests/testsuite.at
+++ b/openbsc/tests/testsuite.at
@@ -48,6 +48,14 @@ cat $abs_srcdir/smpp/smpp_test.err > experr
 AT_CHECK([$abs_top_builddir/tests/smpp/smpp_test], [], [expout], [experr])
 AT_CLEANUP
 
+AT_SETUP([bsc-nat-trie])
+AT_KEYWORDS([bsc-nat-trie])
+AT_CHECK([test "$enable_nat_test" != no || exit 77])
+cp $abs_srcdir/bsc-nat-trie/prefixes.csv .
+cat $abs_srcdir/bsc-nat-trie/bsc_nat_trie_test.ok > expout
+AT_CHECK([$abs_top_builddir/tests/bsc-nat-trie/bsc_nat_trie_test], [], [expout], [ignore])
+AT_CLEANUP
+
 AT_SETUP([si])
 AT_KEYWORDS([si])
 cat $abs_srcdir/si/si_test.ok > expout