From 85d3b34ed2c3b627fca50c82abe426b7239b62a3 Mon Sep 17 00:00:00 2001 From: Holger Hans Peter Freyther Date: Fri, 14 Jun 2013 19:10:28 +0200 Subject: 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. --- openbsc/tests/Makefile.am | 2 +- openbsc/tests/bsc-nat-trie/Makefile.am | 18 +++++ openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c | 87 +++++++++++++++++++++++++ openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok | 20 ++++++ openbsc/tests/bsc-nat-trie/prefixes.csv | 25 +++++++ openbsc/tests/testsuite.at | 8 +++ 6 files changed, 159 insertions(+), 1 deletion(-) create mode 100644 openbsc/tests/bsc-nat-trie/Makefile.am create mode 100644 openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c create mode 100644 openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok create mode 100644 openbsc/tests/bsc-nat-trie/prefixes.csv (limited to 'openbsc/tests') 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 + * 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 . + * + */ + +#include +#include + +#include +#include +#include +#include + +#include + +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 -- cgit v1.2.3