src/lib/container/namemap.c

   1 /* Copyright (c) 2003-2004, Roger Dingledine
   2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   3  * Copyright (c) 2007-2021, The Tor Project, Inc. */
   4 /* See LICENSE for licensing information */
   5
   6 /**
   7  * @file namemap.c
   8  * @brief Mappings between identifiers and 16-bit ints.
   9  **/
  10
  11 #include "orconfig.h"
  12 #include "lib/container/smartlist.h"
  13 #include "lib/container/namemap.h"
  14 #include "lib/container/namemap_st.h"
  15 #include "lib/log/util_bug.h"
  16 #include "lib/malloc/malloc.h"
  17 #include "lib/string/printf.h"
  18
  19 #include "ext/siphash.h"
  20
  21 #include <string.h>
  22
  23 /** Helper for namemap hashtable implementation: compare two entries. */
  24 static inline int
  25 mapped_name_eq(const mapped_name_t *a, const mapped_name_t *b)
  26 {
  27   return !strcmp(a->name, b->name);
  28 }
  29
  30 /** Helper for namemap hashtable implementation: hash an entry. */
  31 static inline unsigned
  32 mapped_name_hash(const mapped_name_t *a)
  33 {
  34   return (unsigned) siphash24g(a->name, strlen(a->name));
  35 }
  36
  37 HT_PROTOTYPE(namemap_ht, mapped_name_t, node, mapped_name_hash,
  38              mapped_name_eq);
  39 HT_GENERATE2(namemap_ht, mapped_name_t, node, mapped_name_hash,
  40              mapped_name_eq, 0.6, tor_reallocarray_, tor_free_);
  41
  42 /** Set up an uninitialized <b>map</b>. */
  43 void
  44 namemap_init(namemap_t *map)
  45 {
  46   memset(map, 0, sizeof(*map));
  47   HT_INIT(namemap_ht, &map->ht);
  48   map->names = smartlist_new();
  49 }
  50
  51 /** Return the name that <b>map</b> associates with a given <b>id</b>, or
  52  * NULL if there is no such name. */
  53 const char *
  54 namemap_get_name(const namemap_t *map, unsigned id)
  55 {
  56   if (map->names && id < (unsigned)smartlist_len(map->names)) {
  57     mapped_name_t *name = smartlist_get(map->names, (int)id);
  58     return name->name;
  59   } else {
  60     return NULL;
  61   }
  62 }
  63
  64 /**
  65  * Return the name that <b>map</b> associates with a given <b>id</b>, or a
  66  * pointer to a statically allocated string describing the value of <b>id</b>
  67  * if no such name exists.
  68  **/
  69 const char *
  70 namemap_fmt_name(const namemap_t *map, unsigned id)
  71 {
  72   static char buf[32];
  73
  74   const char *name = namemap_get_name(map, id);
  75   if (name)
  76     return name;
  77
  78   tor_snprintf(buf, sizeof(buf), "{%u}", id);
  79
  80   return buf;
  81 }
  82
  83 /**
  84  * Helper: As namemap_get_id(), but requires that <b>name</b> is
  85  * <b>namelen</b> characters long, and that <b>namelen</b> is no more than
  86  * MAX_NAMEMAP_NAME_LEN.
  87  */
  88 static unsigned
  89 namemap_get_id_unchecked(const namemap_t *map,
  90                          const char *name,
  91                          size_t namelen)
  92 {
  93   union {
  94     mapped_name_t n;
  95     char storage[MAX_NAMEMAP_NAME_LEN + sizeof(mapped_name_t) + 1];
  96   } u;
  97   memcpy(u.n.name, name, namelen);
  98   u.n.name[namelen] = 0;
  99   const mapped_name_t *found = HT_FIND(namemap_ht, &map->ht, &u.n);
 100   if (found) {
 101     tor_assert(map->names);
 102     tor_assert(smartlist_get(map->names, found->intval) == found);
 103     return found->intval;
 104   }
 105
 106   return NAMEMAP_ERR;
 107 }
 108
 109 /**
 110  * Return the identifier currently associated by <b>map</b> with the name
 111  * <b>name</b>, or NAMEMAP_ERR if no such identifier exists.
 112  **/
 113 unsigned
 114 namemap_get_id(const namemap_t *map,
 115                const char *name)
 116 {
 117   size_t namelen = strlen(name);
 118   if (namelen > MAX_NAMEMAP_NAME_LEN) {
 119     return NAMEMAP_ERR;
 120   }
 121
 122   return namemap_get_id_unchecked(map, name, namelen);
 123 }
 124
 125 /**
 126  * Return the identifier associated by <b>map</b> with the name
 127  * <b>name</b>, allocating a new identifier in <b>map</b> if none exists.
 128  *
 129  * Return NAMEMAP_ERR if <b>name</b> is too long, or if there are no more
 130  * identifiers we can allocate.
 131  **/
 132 unsigned
 133 namemap_get_or_create_id(namemap_t *map,
 134                          const char *name)
 135 {
 136   size_t namelen = strlen(name);
 137   if (namelen > MAX_NAMEMAP_NAME_LEN) {
 138     return NAMEMAP_ERR;
 139   }
 140
 141   if (PREDICT_UNLIKELY(map->names == NULL))
 142     map->names = smartlist_new();
 143
 144   unsigned found = namemap_get_id_unchecked(map, name, namelen);
 145   if (found != NAMEMAP_ERR)
 146     return found;
 147
 148   unsigned new_id = (unsigned)smartlist_len(map->names);
 149   if (new_id == NAMEMAP_ERR)
 150     return NAMEMAP_ERR; /* Can't allocate any more. */
 151
 152   mapped_name_t *insert = tor_malloc_zero(
 153                        offsetof(mapped_name_t, name) + namelen + 1);
 154   memcpy(insert->name, name, namelen+1);
 155   insert->intval = new_id;
 156
 157   HT_INSERT(namemap_ht, &map->ht, insert);
 158   smartlist_add(map->names, insert);
 159
 160   return new_id;
 161 }
 162
 163 /** Return the number of entries in 'names' */
 164 size_t
 165 namemap_get_size(const namemap_t *map)
 166 {
 167   if (PREDICT_UNLIKELY(map->names == NULL))
 168     return 0;
 169
 170   return smartlist_len(map->names);
 171 }
 172
 173 /**
 174  * Release all storage held in <b>map</b>.
 175  */
 176 void
 177 namemap_clear(namemap_t *map)
 178 {
 179   if (!map)
 180     return;
 181
 182   HT_CLEAR(namemap_ht, &map->ht);
 183   if (map->names) {
 184     SMARTLIST_FOREACH(map->names, mapped_name_t *, n,
 185                       tor_free(n));
 186     smartlist_free(map->names);
 187   }
 188   memset(map, 0, sizeof(*map));
 189 }