OpenVPN
list.h
Go to the documentation of this file.
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-2017 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 along
20  * with this program; if not, write to the Free Software Foundation, Inc.,
21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22  */
23 
24 #ifndef LIST_H
25 #define LIST_H
26 
27 /*
28  * This code is a fairly straightforward hash
29  * table implementation using Bob Jenkins'
30  * hash function.
31  *
32  * Hash tables are used in OpenVPN to keep track of
33  * client instances over various key spaces.
34  */
35 
36 #if P2MP_SERVER
37 
38 /* define this to enable special list test mode */
39 /*#define LIST_TEST*/
40 
41 #include "basic.h"
42 #include "buffer.h"
43 
44 #define hashsize(n) ((uint32_t)1<<(n))
45 #define hashmask(n) (hashsize(n)-1)
46 
48 {
49  void *value;
50  const void *key;
51  unsigned int hash_value;
52  struct hash_element *next;
53 };
54 
56 {
57  struct hash_element *list;
58 };
59 
60 struct hash
61 {
62  int n_buckets;
64  int mask;
66  uint32_t (*hash_function)(const void *key, uint32_t iv);
67  bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
69 };
70 
71 struct hash *hash_init(const int n_buckets,
72  const uint32_t iv,
73  uint32_t (*hash_function)(const void *key, uint32_t iv),
74  bool (*compare_function)(const void *key1, const void *key2));
75 
76 void hash_free(struct hash *hash);
77 
78 bool hash_add(struct hash *hash, const void *key, void *value, bool replace);
79 
80 struct hash_element *hash_lookup_fast(struct hash *hash,
81  struct hash_bucket *bucket,
82  const void *key,
83  uint32_t hv);
84 
85 bool hash_remove_fast(struct hash *hash,
86  struct hash_bucket *bucket,
87  const void *key,
88  uint32_t hv);
89 
90 void hash_remove_by_value(struct hash *hash, void *value);
91 
93 {
94  struct hash *hash;
97  struct hash_element *elem;
98  struct hash_element *last;
102 };
103 
104 void hash_iterator_init_range(struct hash *hash,
105  struct hash_iterator *hi,
106  int start_bucket,
107  int end_bucket);
108 
109 void hash_iterator_init(struct hash *hash, struct hash_iterator *iter);
110 
111 struct hash_element *hash_iterator_next(struct hash_iterator *hi);
112 
114 
115 void hash_iterator_free(struct hash_iterator *hi);
116 
117 uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval);
118 
119 uint32_t void_ptr_hash_function(const void *key, uint32_t iv);
120 
121 bool void_ptr_compare_function(const void *key1, const void *key2);
122 
123 #ifdef LIST_TEST
124 void list_test(void);
125 
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 *
148 {
149  return &hash->buckets[hv & hash->mask];
150 }
151 
152 static inline void *
153 hash_lookup(struct hash *hash, const void *key)
154 {
155  void *ret = NULL;
156  struct hash_element *he;
157  uint32_t hv = hash_value(hash, key);
158  struct hash_bucket *bucket = &hash->buckets[hv & hash->mask];
159 
160  he = hash_lookup_fast(hash, bucket, key, hv);
161  if (he)
162  {
163  ret = he->value;
164  }
165 
166  return ret;
167 }
168 
169 /* NOTE: assumes that key is not a duplicate */
170 static inline void
172  struct hash_bucket *bucket,
173  const void *key,
174  uint32_t hv,
175  void *value)
176 {
177  struct hash_element *he;
178 
179  ALLOC_OBJ(he, struct hash_element);
180  he->value = value;
181  he->key = key;
182  he->hash_value = hv;
183  he->next = bucket->list;
184  bucket->list = he;
185  ++hash->n_elements;
186 }
187 
188 static inline bool
189 hash_remove(struct hash *hash, const void *key)
190 {
191  uint32_t hv;
192  struct hash_bucket *bucket;
193  bool ret;
194 
195  hv = hash_value(hash, key);
196  bucket = &hash->buckets[hv & hash->mask];
197  ret = hash_remove_fast(hash, bucket, key, hv);
198  return ret;
199 }
200 
201 #endif /* P2MP_SERVER */
202 #endif /* LIST */
#define ALLOC_OBJ(dptr, type)
Definition: buffer.h:1012
uint32_t void_ptr_hash_function(const void *key, uint32_t iv)
Definition: list.c:226
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition: list.h:171
struct hash_element * next
Definition: list.h:52
int n_elements
Definition: list.h:63
const void * key
Definition: list.h:50
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition: list.c:304
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:117
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition: list.c:336
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: list.c:602
bool void_ptr_compare_function(const void *key1, const void *key2)
Definition: list.c:232
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition: list.h:66
struct hash_bucket * bucket
Definition: list.h:96
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket)
Definition: list.c:238
struct hash_element * list
Definition: list.h:57
struct hash_bucket * buckets
Definition: list.h:68
int bucket_index_start
Definition: list.h:100
unsigned __int32 uint32_t
Definition: config-msvc.h:121
static void * hash_lookup(struct hash *hash, const void *key)
Definition: list.h:153
uint32_t iv
Definition: list.h:65
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition: list.c:150
int mask
Definition: list.h:64
static int hash_n_buckets(const struct hash *hash)
Definition: list.h:141
int bucket_index
Definition: list.h:95
Container for bidirectional cipher and HMAC key material.
Definition: crypto.h:183
static struct hash_bucket * hash_bucket(struct hash *hash, uint32_t hv)
Definition: list.h:147
void hash_remove_by_value(struct hash *hash, void *value)
Definition: list.c:178
unsigned __int8 uint8_t
Definition: config-msvc.h:123
int n_buckets
Definition: list.h:62
struct hash_element * last
Definition: list.h:98
int bucket_index_end
Definition: list.h:101
bool(* compare_function)(const void *key1, const void *key2)
Definition: list.h:67
static int hash_n_elements(const struct hash *hash)
Definition: list.h:135
static bool hash_remove(struct hash *hash, const void *key)
Definition: list.h:189
bool bucket_marked
Definition: list.h:99
#define bool
Definition: simple.c:61
void * value
Definition: list.h:49
void hash_free(struct hash *hash)
Definition: list.c:66
void hash_iterator_init(struct hash *hash, struct hash_iterator *iter)
Definition: list.c:261
struct hash * hash_init(const int n_buckets, const uint32_t iv, uint32_t(*hash_function)(const void *key, uint32_t iv), bool(*compare_function)(const void *key1, const void *key2))
Definition: list.c:41
Definition: list.h:60
struct hash_element * elem
Definition: list.h:97
void hash_iterator_free(struct hash_iterator *hi)
Definition: list.c:298
Container for unidirectional cipher and HMAC key material.
Definition: crypto.h:153
struct hash * hash
Definition: list.h:94
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:86
unsigned int hash_value
Definition: list.h:51