Line data    Source code

       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       24343 : mapped_name_eq(const mapped_name_t *a, const mapped_name_t *b)
      26             : {
      27       24343 :   return !strcmp(a->name, b->name);
      28             : }
      29             : 
      30             : /** Helper for namemap hashtable implementation: hash an entry. */
      31             : static inline unsigned
      32       39428 : mapped_name_hash(const mapped_name_t *a)
      33             : {
      34       39428 :   return (unsigned) siphash24g(a->name, strlen(a->name));
      35             : }
      36             : 
      37       72486 : HT_PROTOTYPE(namemap_ht, mapped_name_t, node, mapped_name_hash,
      38             :              mapped_name_eq);
      39       25666 : 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           5 : namemap_init(namemap_t *map)
      45             : {
      46           5 :   memset(map, 0, sizeof(*map));
      47           5 :   HT_INIT(namemap_ht, &map->ht);
      48           5 :   map->names = smartlist_new();
      49           5 : }
      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        1782 : namemap_get_name(const namemap_t *map, unsigned id)
      55             : {
      56        1782 :   if (map->names && id < (unsigned)smartlist_len(map->names)) {
      57        1757 :     mapped_name_t *name = smartlist_get(map->names, (int)id);
      58        1757 :     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        1775 : namemap_fmt_name(const namemap_t *map, unsigned id)
      71             : {
      72        1775 :   static char buf[32];
      73             : 
      74        1775 :   const char *name = namemap_get_name(map, id);
      75        1775 :   if (name)
      76             :     return name;
      77             : 
      78          23 :   tor_snprintf(buf, sizeof(buf), "{%u}", id);
      79             : 
      80          23 :   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       30737 : namemap_get_id_unchecked(const namemap_t *map,
      90             :                          const char *name,
      91             :                          size_t namelen)
      92             : {
      93       30737 :   union {
      94             :     mapped_name_t n;
      95             :     char storage[MAX_NAMEMAP_NAME_LEN + sizeof(mapped_name_t) + 1];
      96             :   } u;
      97       30737 :   memcpy(u.n.name, name, namelen);
      98       30737 :   u.n.name[namelen] = 0;
      99       30737 :   const mapped_name_t *found = HT_FIND(namemap_ht, &map->ht, &u.n);
     100       30737 :   if (found) {
     101       22034 :     tor_assert(map->names);
     102       22034 :     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          23 : namemap_get_id(const namemap_t *map,
     115             :                const char *name)
     116             : {
     117          23 :   size_t namelen = strlen(name);
     118          23 :   if (namelen > MAX_NAMEMAP_NAME_LEN) {
     119             :     return NAMEMAP_ERR;
     120             :   }
     121             : 
     122          21 :   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       30717 : namemap_get_or_create_id(namemap_t *map,
     134             :                          const char *name)
     135             : {
     136       30717 :   size_t namelen = strlen(name);
     137       30717 :   if (namelen > MAX_NAMEMAP_NAME_LEN) {
     138             :     return NAMEMAP_ERR;
     139             :   }
     140             : 
     141       30716 :   if (PREDICT_UNLIKELY(map->names == NULL))
     142        1049 :     map->names = smartlist_new();
     143             : 
     144       30716 :   unsigned found = namemap_get_id_unchecked(map, name, namelen);
     145       30716 :   if (found != NAMEMAP_ERR)
     146             :     return found;
     147             : 
     148        8691 :   unsigned new_id = (unsigned)smartlist_len(map->names);
     149        8691 :   if (new_id == NAMEMAP_ERR)
     150             :     return NAMEMAP_ERR; /* Can't allocate any more. */
     151             : 
     152        8691 :   mapped_name_t *insert = tor_malloc_zero(
     153             :                        offsetof(mapped_name_t, name) + namelen + 1);
     154        8691 :   memcpy(insert->name, name, namelen+1);
     155        8691 :   insert->intval = new_id;
     156             : 
     157        8691 :   HT_INSERT(namemap_ht, &map->ht, insert);
     158        8691 :   smartlist_add(map->names, insert);
     159             : 
     160        8691 :   return new_id;
     161             : }
     162             : 
     163             : /** Return the number of entries in 'names' */
     164             : size_t
     165         528 : namemap_get_size(const namemap_t *map)
     166             : {
     167         528 :   if (PREDICT_UNLIKELY(map->names == NULL))
     168             :     return 0;
     169             : 
     170         527 :   return smartlist_len(map->names);
     171             : }
     172             : 
     173             : /**
     174             :  * Release all storage held in <b>map</b>.
     175             :  */
     176             : void
     177           7 : namemap_clear(namemap_t *map)
     178             : {
     179           7 :   if (!map)
     180             :     return;
     181             : 
     182           7 :   HT_CLEAR(namemap_ht, &map->ht);
     183           7 :   if (map->names) {
     184          16 :     SMARTLIST_FOREACH(map->names, mapped_name_t *, n,
     185             :                       tor_free(n));
     186           6 :     smartlist_free(map->names);
     187             :   }
     188           7 :   memset(map, 0, sizeof(*map));
     189             : }