commit dfd7a7f5b63eb968caebf6823395689e6b77b654 Author: Nick Mathewson nickm@torproject.org Date: Thu Oct 25 12:04:19 2018 -0400

Add a type to map names to short identifiers

We'll be using this for four kinds of identifier in dispatch.c --- src/lib/container/include.am | 3 + src/lib/container/namemap.c | 184 +++++++++++++++++++++++++++++++++++++++++ src/lib/container/namemap.h | 35 ++++++++ src/lib/container/namemap_st.h | 34 ++++++++ src/test/include.am | 1 + src/test/test.c | 1 + src/test/test.h | 1 + src/test/test_namemap.c | 154 ++++++++++++++++++++++++++++++++++ 8 files changed, 413 insertions(+)

diff --git a/src/lib/container/include.am b/src/lib/container/include.am index 032e4033d..50d35e749 100644 --- a/src/lib/container/include.am +++ b/src/lib/container/include.am @@ -8,6 +8,7 @@ endif src_lib_libtor_container_a_SOURCES = \ src/lib/container/bloomfilt.c \ src/lib/container/map.c \ + src/lib/container/namemap.c \ src/lib/container/order.c \ src/lib/container/smartlist.c

@@ -21,5 +22,7 @@ noinst_HEADERS += \ src/lib/container/bloomfilt.h \ src/lib/container/handles.h \ src/lib/container/map.h \ + src/lib/container/namemap.h \ + src/lib/container/namemap_st.h \ src/lib/container/order.h \ src/lib/container/smartlist.h diff --git a/src/lib/container/namemap.c b/src/lib/container/namemap.c new file mode 100644 index 000000000..a90057b32 --- /dev/null +++ b/src/lib/container/namemap.c @@ -0,0 +1,184 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" +#include "lib/container/smartlist.h" +#include "lib/container/namemap.h" +#include "lib/container/namemap_st.h" +#include "lib/log/util_bug.h" +#include "lib/malloc/malloc.h" +#include "lib/string/printf.h" + +#include "ext/siphash.h" + +#include <string.h> + +/** Helper for namemap hashtable implementation: compare two entries. */ +static inline int +mapped_name_eq(const mapped_name_t *a, const mapped_name_t *b) +{ + return !strcmp(a->name, b->name); +} + +/** Helper for namemap hashtable implementation: hash an entry. */ +static inline unsigned +mapped_name_hash(const mapped_name_t *a) +{ + return (unsigned) siphash24g(a->name, strlen(a->name)); +} + +HT_PROTOTYPE(namemap_ht, mapped_name_t, node, mapped_name_hash, + mapped_name_eq) +HT_GENERATE2(namemap_ht, mapped_name_t, node, mapped_name_hash, + mapped_name_eq, 0.6, tor_reallocarray_, tor_free_) + +/** Set up an uninitialized <b>map</b>. */ +void +namemap_init(namemap_t *map) +{ + memset(map, 0, sizeof(*map)); + HT_INIT(namemap_ht, &map->ht); + map->names = smartlist_new(); +} + +/** Return the name that <b>map</b> associates with a given <b>id</b>, or + * NULL if there is no such name. */ +const char * +namemap_get_name(const namemap_t *map, unsigned id) +{ + if (map->names && id < (unsigned)smartlist_len(map->names)) { + mapped_name_t *name = smartlist_get(map->names, (int)id); + return name->name; + } else { + return NULL; + } +} + +/** + * Return the name that <b>map</b> associates with a given <b>id</b>, or a + * pointer to a statically allocated string describing the value of <b>id</b> + * if no such name exists. + **/ +const char * +namemap_fmt_name(const namemap_t *map, unsigned id) +{ + static char buf[32]; + + const char *name = namemap_get_name(map, id); + if (name) + return name; + + tor_snprintf(buf, sizeof(buf), "{%u}", id); + + return buf; +} + +/** + * Helper: As namemap_get_id(), but requires that <b>name</b> is + * <b>namelen</b> charaters long, and that <b>namelen</b> is no more than + * MAX_NAMEMAP_NAME_LEN. + */ +static unsigned +namemap_get_id_unchecked(const namemap_t *map, + const char *name, + size_t namelen) +{ + union { + mapped_name_t n; + char storage[MAX_NAMEMAP_NAME_LEN + sizeof(mapped_name_t) + 1]; + } u; + memcpy(u.n.name, name, namelen); + u.n.name[namelen] = 0; + const mapped_name_t *found = HT_FIND(namemap_ht, &map->ht, &u.n); + if (found) { + tor_assert(map->names); + tor_assert(smartlist_get(map->names, found->intval) == found); + return found->intval; + } + + return NAMEMAP_ERR; +} + +/** + * Return the identifier currently associated by <b>map</b> with the name + * <b>name</b>, or NAMEMAP_ERR if no such identifier exists. + **/ +unsigned +namemap_get_id(const namemap_t *map, + const char *name) +{ + size_t namelen = strlen(name); + if (namelen > MAX_NAMEMAP_NAME_LEN) { + return NAMEMAP_ERR; + } + + return namemap_get_id_unchecked(map, name, namelen); +} + +/** + * Return the identifier associated by <b>map</b> with the name + * <b>name</b>, allocating a new identifier in <b>map</b> if none exists. + * + * Return NAMEMAP_ERR if <b>name</b> is too long, or if there are no more + * identifiers we can allocate. + **/ +unsigned +namemap_get_or_create_id(namemap_t *map, + const char *name) +{ + size_t namelen = strlen(name); + if (namelen > MAX_NAMEMAP_NAME_LEN) { + return NAMEMAP_ERR; + } + + if (PREDICT_UNLIKELY(map->names == NULL)) + map->names = smartlist_new(); + + unsigned found = namemap_get_id_unchecked(map, name, namelen); + if (found != NAMEMAP_ERR) + return found; + + unsigned new_id = (unsigned)smartlist_len(map->names); + if (new_id == NAMEMAP_ERR) + return NAMEMAP_ERR; /* Can't allocate any more. */ + + mapped_name_t *insert = tor_malloc_zero( + offsetof(mapped_name_t, name) + namelen + 1); + memcpy(insert->name, name, namelen+1); + insert->intval = new_id; + + HT_INSERT(namemap_ht, &map->ht, insert); + smartlist_add(map->names, insert); + + return new_id; +} + +/** Return the number of entries in 'names' */ +size_t +namemap_get_size(const namemap_t *map) +{ + if (PREDICT_UNLIKELY(map->names == NULL)) + return 0; + + return smartlist_len(map->names); +} + +/** + * Release all storage held in <b>map</b>. + */ +void +namemap_clear(namemap_t *map) +{ + if (!map) + return; + + HT_CLEAR(namemap_ht, &map->ht); + if (map->names) { + SMARTLIST_FOREACH(map->names, mapped_name_t *, n, + tor_free(n)); + smartlist_free(map->names); + } + memset(map, 0, sizeof(*map)); +} diff --git a/src/lib/container/namemap.h b/src/lib/container/namemap.h new file mode 100644 index 000000000..97792e13b --- /dev/null +++ b/src/lib/container/namemap.h @@ -0,0 +1,35 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_NAMEMAP_H +#define TOR_NAMEMAP_H + +/** + * \file namemap.h + * + * \brief Header for namemap.c + **/ + +#include "lib/cc/compat_compiler.h" +#include "ext/ht.h" + +#include <stddef.h> + +typedef struct namemap_t namemap_t; + +/** Returned in place of an identifier when an error occurs. */ +#define NAMEMAP_ERR UINT_MAX + +void namemap_init(namemap_t *map); +const char *namemap_get_name(const namemap_t *map, unsigned id); +const char *namemap_fmt_name(const namemap_t *map, unsigned id); +unsigned namemap_get_id(const namemap_t *map, + const char *name); +unsigned namemap_get_or_create_id(namemap_t *map, + const char *name); +size_t namemap_get_size(const namemap_t *map); +void namemap_clear(namemap_t *map); + +#endif diff --git a/src/lib/container/namemap_st.h b/src/lib/container/namemap_st.h new file mode 100644 index 000000000..5717352fa --- /dev/null +++ b/src/lib/container/namemap_st.h @@ -0,0 +1,34 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef NAMEMAP_ST_H +#define NAMEMAP_ST_H + +#include "lib/cc/compat_compiler.h" +#include "ext/ht.h" + +struct smartlist_t; + +/** Longest allowed name that's allowed in a namemap_t. */ +#define MAX_NAMEMAP_NAME_LEN 128 + +/** An entry inside a namemap_t. Maps a string to a numeric identifier. */ +typedef struct mapped_name_t { + HT_ENTRY(mapped_name_t) node; + unsigned intval; + char name[FLEXIBLE_ARRAY_MEMBER]; +} mapped_name_t; + +/** A structure that allocates small numeric identifiers for names and maps + * back and forth between them. */ +struct namemap_t { + HT_HEAD(namemap_ht, mapped_name_t) ht; + struct smartlist_t *names; +}; + +/** Macro to initialize a namemap. */ +#define NAMEMAP_INIT() { HT_INITIALIZER(), NULL } + +#endif diff --git a/src/test/include.am b/src/test/include.am index b276500fd..c3827d3eb 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -148,6 +148,7 @@ src_test_test_SOURCES += \ src/test/test_logging.c \ src/test/test_mainloop.c \ src/test/test_microdesc.c \ + src/test/test_namemap.c \ src/test/test_netinfo.c \ src/test/test_nodelist.c \ src/test/test_oom.c \ diff --git a/src/test/test.c b/src/test/test.c index 902565dfb..1230b632a 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -857,6 +857,7 @@ struct testgroup_t testgroups[] = { { "consdiff/", consdiff_tests }, { "consdiffmgr/", consdiffmgr_tests }, { "container/", container_tests }, + { "container/namemap/", namemap_tests }, { "control/", controller_tests }, { "control/btrack/", btrack_tests }, { "control/event/", controller_event_tests }, diff --git a/src/test/test.h b/src/test/test.h index 39953e9f7..7a3a4d8fd 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -234,6 +234,7 @@ extern struct testcase_t link_handshake_tests[]; extern struct testcase_t logging_tests[]; extern struct testcase_t mainloop_tests[]; extern struct testcase_t microdesc_tests[]; +extern struct testcase_t namemap_tests[]; extern struct testcase_t netinfo_tests[]; extern struct testcase_t nodelist_tests[]; extern struct testcase_t oom_tests[]; diff --git a/src/test/test_namemap.c b/src/test/test_namemap.c new file mode 100644 index 000000000..5134e1451 --- /dev/null +++ b/src/test/test_namemap.c @@ -0,0 +1,154 @@ +/* Copyright (c) 2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "test/test.h" + +#include "lib/cc/torint.h" +#include "lib/container/namemap.h" +#include "lib/container/namemap_st.h" +#include "lib/malloc/malloc.h" + +#include <stdio.h> +#include <string.h> + +static void +test_namemap_empty(void *arg) +{ + (void)arg; + + namemap_t m; + namemap_init(&m); + namemap_t m2 = NAMEMAP_INIT(); + + tt_uint_op(0, OP_EQ, namemap_get_size(&m)); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, "hello")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, "hello")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, "hello128")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, "")); + tt_uint_op(0, OP_EQ, namemap_get_size(&m)); + + tt_uint_op(0, OP_EQ, namemap_get_size(&m2)); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m2, "hello")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m2, "hello")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m2, "hello128")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m2, "")); + tt_uint_op(0, OP_EQ, namemap_get_size(&m)); + + done: + namemap_clear(&m); + namemap_clear(&m2); +} + +static void +test_namemap_toolong(void *arg) +{ + (void)arg; + namemap_t m; + char *ok = NULL; + char *toolong = NULL; + namemap_init(&m); + + ok = tor_malloc_zero(MAX_NAMEMAP_NAME_LEN+1); + memset(ok, 'x', MAX_NAMEMAP_NAME_LEN); + + toolong = tor_malloc_zero(MAX_NAMEMAP_NAME_LEN+2); + memset(toolong, 'x', MAX_NAMEMAP_NAME_LEN+1); + + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, ok)); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, toolong)); + unsigned u1 = namemap_get_or_create_id(&m, toolong); + unsigned u2 = namemap_get_or_create_id(&m, ok); + tt_uint_op(u1, OP_EQ, NAMEMAP_ERR); + tt_uint_op(u2, OP_NE, NAMEMAP_ERR); + tt_uint_op(u2, OP_EQ, namemap_get_id(&m, ok)); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m, toolong)); + + tt_str_op(ok, OP_EQ, namemap_get_name(&m, u2)); + tt_ptr_op(NULL, OP_EQ, namemap_get_name(&m, u1)); + + done: + tor_free(ok); + tor_free(toolong); + namemap_clear(&m); +} + +static void +test_namemap_blackbox(void *arg) +{ + (void)arg; + + namemap_t m1, m2; + namemap_init(&m1); + namemap_init(&m2); + + unsigned u1 = namemap_get_or_create_id(&m1, "hello"); + unsigned u2 = namemap_get_or_create_id(&m1, "world"); + tt_uint_op(u1, OP_NE, NAMEMAP_ERR); + tt_uint_op(u2, OP_NE, NAMEMAP_ERR); + tt_uint_op(u1, OP_NE, u2); + + tt_uint_op(u1, OP_EQ, namemap_get_id(&m1, "hello")); + tt_uint_op(u1, OP_EQ, namemap_get_or_create_id(&m1, "hello")); + tt_uint_op(u2, OP_EQ, namemap_get_id(&m1, "world")); + tt_uint_op(u2, OP_EQ, namemap_get_or_create_id(&m1, "world")); + + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m1, "HELLO")); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m2, "hello")); + + unsigned u3 = namemap_get_or_create_id(&m2, "hola"); + tt_uint_op(u3, OP_NE, NAMEMAP_ERR); + tt_uint_op(NAMEMAP_ERR, OP_EQ, namemap_get_id(&m1, "hola")); + tt_uint_op(u3, OP_EQ, namemap_get_or_create_id(&m2, "hola")); + tt_uint_op(u3, OP_EQ, namemap_get_id(&m2, "hola")); + + unsigned int u4 = namemap_get_or_create_id(&m1, "hola"); + tt_uint_op(u4, OP_NE, NAMEMAP_ERR); + tt_uint_op(u4, OP_EQ, namemap_get_id(&m1, "hola")); + tt_uint_op(u3, OP_EQ, namemap_get_id(&m2, "hola")); + + tt_str_op("hello", OP_EQ, namemap_get_name(&m1, u1)); + tt_str_op("world", OP_EQ, namemap_get_name(&m1, u2)); + tt_str_op("hola", OP_EQ, namemap_get_name(&m2, u3)); + tt_str_op("hola", OP_EQ, namemap_get_name(&m1, u4)); + + tt_ptr_op(NULL, OP_EQ, namemap_get_name(&m2, u3 + 10)); + + done: + namemap_clear(&m1); + namemap_clear(&m2); +} + +static void +test_namemap_internals(void *arg) +{ + (void)arg; + // This test actually assumes know something about the identity layout. + namemap_t m; + namemap_init(&m); + + tt_uint_op(0, OP_EQ, namemap_get_or_create_id(&m, "that")); + tt_uint_op(0, OP_EQ, namemap_get_or_create_id(&m, "that")); + tt_uint_op(1, OP_EQ, namemap_get_or_create_id(&m, "is")); + tt_uint_op(1, OP_EQ, namemap_get_or_create_id(&m, "is")); + + tt_uint_op(0, OP_EQ, namemap_get_id(&m, "that")); + tt_uint_op(0, OP_EQ, namemap_get_id(&m, "that")); + tt_uint_op(1, OP_EQ, namemap_get_id(&m, "is")); + tt_uint_op(2, OP_EQ, namemap_get_or_create_id(&m, "not")); + tt_uint_op(1, OP_EQ, namemap_get_or_create_id(&m, "is")); + tt_uint_op(2, OP_EQ, namemap_get_or_create_id(&m, "not")); + + done: + namemap_clear(&m); +} + +#define T(name) \ + { #name, test_namemap_ ## name , 0, NULL, NULL } + +struct testcase_t namemap_tests[] = { + T(empty), + T(toolong), + T(blackbox), + T(internals), + END_OF_TESTCASES +};