release/src/router/openvpn/list.h

   1 /*
   2  *  OpenVPN -- An application to securely tunnel IP networks
   3  *             over a single TCP/UDP port, with support for SSL/TLS-based
   4  *             session authentication and key exchange,
   5  *             packet encryption, packet authentication, and
   6  *             packet compression.
   7  *
   8  *  Copyright (C) 2002-2009 OpenVPN Technologies, Inc. <sales@openvpn.net>
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License version 2
  12  *  as published by the Free Software Foundation.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program (see the file COPYING included with this
  21  *  distribution); if not, write to the Free Software Foundation, Inc.,
  22  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23  */
  24
  25 #ifndef LIST_H
  26 #define LIST_H
  27
  28 /*
  29  * This code is a fairly straightforward hash
  30  * table implementation using Bob Jenkins'
  31  * hash function.
  32  *
  33  * Hash tables are used in OpenVPN to keep track of
  34  * client instances over various key spaces.
  35  */
  36
  37 #if P2MP_SERVER
  38
  39 /* define this to enable special list test mode */
  40 /*#define LIST_TEST*/
  41
  42 #include "basic.h"
  43 #include "thread.h"
  44 #include "buffer.h"
  45
  46 #define hashsize(n) ((uint32_t)1<<(n))
  47 #define hashmask(n) (hashsize(n)-1)
  48
  49 struct hash_element
  50 {
  51   void *value;
  52   const void *key;
  53   unsigned int hash_value;
  54   struct hash_element *next;
  55 };
  56
  57 struct hash_bucket
  58 {
  59   MUTEX_DEFINE (mutex);
  60   struct hash_element *list;
  61 };
  62
  63 struct hash
  64 {
  65   int n_buckets;
  66   int n_elements;
  67   int mask;
  68   uint32_t iv;
  69   uint32_t (*hash_function)(const void *key, uint32_t iv);
  70   bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
  71   struct hash_bucket *buckets;
  72 };
  73
  74 struct hash *hash_init (const int n_buckets,
  75                         const uint32_t iv,
  76                         uint32_t (*hash_function)(const void *key, uint32_t iv),
  77                         bool (*compare_function)(const void *key1, const void *key2));
  78
  79 void hash_free (struct hash *hash);
  80
  81 bool hash_add (struct hash *hash, const void *key, void *value, bool replace);
  82
  83 struct hash_element *hash_lookup_fast (struct hash *hash,
  84                                        struct hash_bucket *bucket,
  85                                        const void *key,
  86                                        uint32_t hv);
  87
  88 bool hash_remove_fast (struct hash *hash,
  89                        struct hash_bucket *bucket,
  90                        const void *key,
  91                        uint32_t hv);
  92
  93 void hash_remove_by_value (struct hash *hash, void *value, bool autolock);
  94
  95 struct hash_iterator
  96 {
  97   struct hash *hash;
  98   int bucket_index;
  99   struct hash_bucket *bucket;
 100   struct hash_element *elem;
 101   struct hash_element *last;
 102   bool bucket_marked;
 103   bool autolock;
 104   int bucket_index_start;
 105   int bucket_index_end;
 106 };
 107
 108 void hash_iterator_init_range (struct hash *hash,
 109                                struct hash_iterator *hi,
 110                                bool autolock,
 111                                int start_bucket,
 112                                int end_bucket);
 113
 114 void hash_iterator_init (struct hash *hash, struct hash_iterator *iter, bool autolock);
 115 struct hash_element *hash_iterator_next (struct hash_iterator *hi);
 116 void hash_iterator_delete_element (struct hash_iterator *hi);
 117 void hash_iterator_free (struct hash_iterator *hi);
 118
 119 uint32_t hash_func (const uint8_t *k, uint32_t length, uint32_t initval);
 120
 121 uint32_t void_ptr_hash_function (const void *key, uint32_t iv);
 122 bool void_ptr_compare_function (const void *key1, const void *key2);
 123
 124 #ifdef LIST_TEST
 125 void list_test (void);
 126 #endif
 127
 128 static inline uint32_t
 129 hash_value (const struct hash *hash, const void *key)
 130 {
 131   return (*hash->hash_function)(key, hash->iv);
 132 }
 133
 134 static inline int
 135 hash_n_elements (const struct hash *hash)
 136 {
 137   return hash->n_elements;
 138 }
 139
 140 static inline int
 141 hash_n_buckets (const struct hash *hash)
 142 {
 143   return hash->n_buckets;
 144 }
 145
 146 static inline struct hash_bucket *
 147 hash_bucket (struct hash *hash, uint32_t hv)
 148 {
 149   return &hash->buckets[hv & hash->mask];
 150 }
 151
 152 static inline void
 153 hash_bucket_lock (struct hash_bucket *bucket)
 154 {
 155   mutex_lock (&bucket->mutex);
 156 }
 157
 158 static inline void
 159 hash_bucket_unlock (struct hash_bucket *bucket)
 160 {
 161   mutex_unlock (&bucket->mutex);
 162 }
 163
 164 static inline void *
 165 hash_lookup_lock (struct hash *hash, const void *key, uint32_t hv)
 166 {
 167   void *ret = NULL;
 168   struct hash_element *he;
 169   struct hash_bucket *bucket = &hash->buckets[hv & hash->mask];
 170
 171   mutex_lock (&bucket->mutex);
 172   he = hash_lookup_fast (hash, bucket, key, hv);
 173   if (he)
 174     ret = he->value;
 175   mutex_unlock (&bucket->mutex);
 176
 177   return ret;
 178 }
 179
 180 static inline void *
 181 hash_lookup (struct hash *hash, const void *key)
 182 {
 183   return hash_lookup_lock (hash, key, hash_value (hash, key));
 184 }
 185
 186 /* NOTE: assumes that key is not a duplicate */
 187 static inline void
 188 hash_add_fast (struct hash *hash,
 189                struct hash_bucket *bucket,
 190                const void *key,
 191                uint32_t hv,
 192                void *value)
 193 {
 194   struct hash_element *he;
 195
 196   ALLOC_OBJ (he, struct hash_element);
 197   he->value = value;
 198   he->key = key;
 199   he->hash_value = hv;
 200   he->next = bucket->list;
 201   bucket->list = he;
 202   ++hash->n_elements;
 203 }
 204
 205 static inline bool
 206 hash_remove (struct hash *hash, const void *key)
 207 {
 208   uint32_t hv;
 209   struct hash_bucket *bucket;
 210   bool ret;
 211
 212   hv = hash_value (hash, key);
 213   bucket = &hash->buckets[hv & hash->mask];
 214   mutex_lock (&bucket->mutex);
 215   ret = hash_remove_fast (hash, bucket, key, hv);
 216   mutex_unlock (&bucket->mutex);
 217   return ret;
 218 }
 219
 220 #endif /* P2MP_SERVER */
 221 #endif /* LIST */