1 : /*
2 : * peerlist.c - Teredo relay internal peers list manipulation
3 : * $Id: peerlist.c 1852 2006-12-15 16:42:20Z remi $
4 : */
5 :
6 : /***********************************************************************
7 : * Copyright © 2004-2006 Rémi Denis-Courmont. *
8 : * This program is free software; you can redistribute and/or modify *
9 : * it under the terms of the GNU General Public License as published *
10 : * by the Free Software Foundation; version 2 of the license. *
11 : * *
12 : * This program is distributed in the hope that it will be useful, *
13 : * but WITHOUT ANY WARRANTY; without even the implied warranty of *
14 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *
15 : * See the GNU General Public License for more details. *
16 : * *
17 : * You should have received a copy of the GNU General Public License *
18 : * along with this program; if not, you can get it from: *
19 : * http://www.gnu.org/copyleft/gpl.html *
20 : ***********************************************************************/
21 :
22 : #ifdef HAVE_CONFIG_H
23 : # include <config.h>
24 : #endif
25 :
26 : #include <stdbool.h>
27 : #include <string.h>
28 : #include <time.h>
29 : #include <stdlib.h> /* malloc() / free() */
30 : #include <assert.h>
31 :
32 : #include <inttypes.h>
33 :
34 : #include <sys/types.h>
35 : #include <netinet/in.h>
36 : #include <pthread.h>
37 : #include <errno.h>
38 :
39 : #ifndef NDEBUG
40 : # define JUDYERROR_NOTEST 1
41 : #endif
42 : #ifdef HAVE_JUDY_H
43 : # include <Judy.h>
44 : #endif
45 :
46 : #include "teredo.h"
47 : #include "teredo-udp.h" // FIXME: ugly
48 : #include "debug.h"
49 : #include "clock.h"
50 : #include "peerlist.h"
51 :
52 : /*
53 : * Packets queueing
54 : */
55 : struct teredo_queue
56 : {
57 : teredo_queue *next;
58 : size_t length;
59 : uint32_t ipv4;
60 : uint16_t port;
61 : bool incoming;
62 : uint8_t data[];
63 : };
64 :
65 : static const unsigned teredo_MaxQueueBytes = 1280;
66 :
67 :
68 : static inline void teredo_peer_init (teredo_peer *peer)
69 302301 : {
70 302301 : peer->queue = NULL;
71 302301 : peer->queue_left = teredo_MaxQueueBytes;
72 302301 : }
73 :
74 :
75 : static inline void teredo_peer_destroy (teredo_peer *peer)
76 302301 : {
77 302301 : teredo_queue *p = peer->queue;
78 :
79 604602 : while (p != NULL)
80 : {
81 : teredo_queue *buf;
82 :
83 0 : buf = p->next;
84 0 : free (p);
85 0 : p = buf;
86 : }
87 302301 : }
88 :
89 :
90 : static void teredo_peer_queue (teredo_peer *restrict peer,
91 : const void *restrict data, size_t len,
92 : uint32_t ip, uint16_t port, bool incoming)
93 0 : {
94 : teredo_queue *p;
95 :
96 0 : if (len > peer->queue_left)
97 0 : return;
98 0 : peer->queue_left -= len;
99 :
100 0 : p = (teredo_queue *)malloc (sizeof (*p) + len);
101 0 : p->length = len;
102 0 : memcpy (p->data, data, len);
103 0 : p->ipv4 = ip;
104 0 : p->port = port;
105 0 : p->incoming = incoming;
106 :
107 0 : p->next = peer->queue;
108 0 : peer->queue = p;
109 : }
110 :
111 :
112 : void teredo_enqueue_in (teredo_peer *restrict peer, const void *restrict data,
113 : size_t len, uint32_t ip, uint16_t port)
114 0 : {
115 0 : teredo_peer_queue (peer, data, len, ip, port, true);
116 0 : }
117 :
118 :
119 : void teredo_enqueue_out (teredo_peer *restrict peer,
120 : const void *restrict data, size_t len)
121 0 : {
122 0 : teredo_peer_queue (peer, data, len, 0, 0, false);
123 0 : }
124 :
125 :
126 : teredo_queue *teredo_peer_queue_yield (teredo_peer *peer)
127 0 : {
128 0 : teredo_queue *q = peer->queue;
129 0 : peer->queue = NULL;
130 0 : peer->queue_left = teredo_MaxQueueBytes;
131 0 : return q;
132 : }
133 :
134 :
135 : void teredo_queue_emit (teredo_queue *q, int fd, uint32_t ipv4, uint16_t port,
136 : teredo_dequeue_cb cb, void *opaque)
137 0 : {
138 0 : while (q != NULL)
139 : {
140 : teredo_queue *buf;
141 :
142 0 : buf = q->next;
143 0 : if (q->incoming)
144 : {
145 0 : if ((ipv4 == q->ipv4) && (port == q->port))
146 0 : cb (opaque, q->data, q->length);
147 : }
148 : else
149 0 : teredo_send (fd, q->data, q->length, ipv4, port);
150 0 : free (q);
151 0 : q = buf;
152 : }
153 0 : }
154 :
155 :
156 : /*** Peer list handling ***/
157 : typedef struct teredo_listitem
158 : {
159 : struct teredo_listitem **pprev, *next;
160 : teredo_peer peer;
161 : union teredo_addr key;
162 : } teredo_listitem;
163 :
164 : struct teredo_peerlist
165 : {
166 : teredo_listitem *recent, *old;
167 : unsigned left;
168 : unsigned expiration;
169 : pthread_t gc;
170 : pthread_mutex_t lock;
171 : #ifdef HAVE_LIBJUDY
172 : Pvoid_t PJHSArray;
173 : #endif
174 : };
175 :
176 :
177 : static inline teredo_listitem *listitem_create (void)
178 302301 : {
179 302301 : teredo_listitem *entry = malloc (sizeof (*entry));
180 302301 : if (entry != NULL)
181 302301 : teredo_peer_init (&entry->peer);
182 302301 : return entry;
183 : }
184 :
185 :
186 : static inline void listitem_destroy (teredo_listitem *entry)
187 302301 : {
188 302301 : teredo_peer_destroy (&entry->peer);
189 302301 : free (entry);
190 302301 : }
191 :
192 :
193 : static void listitem_recdestroy (teredo_listitem *entry)
194 83 : {
195 302467 : while (entry != NULL)
196 : {
197 302301 : teredo_listitem *buf = entry->next;
198 302301 : listitem_destroy (entry);
199 302301 : entry = buf;
200 : }
201 83 : }
202 :
203 :
204 : /**
205 : * Peer list garbage collector entry point.
206 : *
207 : * @return never ever.
208 : */
209 : static LIBTEREDO_NORETURN void *garbage_collector (void *data)
210 13 : {
211 13 : struct teredo_peerlist *l = (struct teredo_peerlist *)data;
212 :
213 : for (;;)
214 : {
215 52 : struct timespec delay = { .tv_sec = l->expiration };
216 52 : while (clock_nanosleep (CLOCK_REALTIME, 0, &delay, &delay));
217 :
218 : int state;
219 39 : pthread_setcancelstate (PTHREAD_CANCEL_DISABLE, &state);
220 : /* cancel-unsafe section starts */
221 39 : pthread_mutex_lock (&l->lock);
222 :
223 : // remove expired peers from hash table
224 1953 : for (teredo_listitem *p = l->old; p != NULL; p = p->next)
225 : {
226 : #ifdef HAVE_LIBJUDY
227 : int Rc_int;
228 1914 : JHSD (Rc_int, l->PJHSArray, (uint8_t *)&p->key, 16);
229 1914 : assert (Rc_int);
230 : #endif
231 1914 : l->left++;
232 : }
233 :
234 : // unlinks old peers
235 39 : teredo_listitem *old = l->old;
236 :
237 : // moves recent peers to old peers area
238 39 : l->old = l->recent;
239 39 : l->recent = NULL;
240 39 : if (l->old != NULL)
241 16 : l->old->pprev = &l->old;
242 :
243 39 : pthread_mutex_unlock (&l->lock);
244 :
245 : // Perform possibly expensive memory release without the lock
246 39 : listitem_recdestroy (old);
247 :
248 : /* cancel-unsafe section ends */
249 39 : pthread_setcancelstate (state, NULL);
250 39 : }
251 : }
252 :
253 :
254 : /**
255 : * Creates an empty peer list.
256 : *
257 : * @param max maximum number of peers in the list
258 : * @param expiration minimum delay (seconds) before a peer can be removed
259 : * by the garbage collector. Must not be 0.
260 : *
261 : * @return NULL on error (see errno for actual problem).
262 : */
263 : teredo_peerlist *teredo_list_create (unsigned max, unsigned expiration)
264 13 : {
265 : /*printf ("Peer size: %u/%u bytes\n",sizeof (teredo_peer),
266 : sizeof (teredo_listitem));*/
267 13 : assert (expiration > 0);
268 :
269 13 : teredo_peerlist *l = (teredo_peerlist *)malloc (sizeof (*l));
270 13 : if (l == NULL)
271 0 : return NULL;
272 :
273 13 : memset (l, 0, sizeof (l));
274 13 : pthread_mutex_init (&l->lock, NULL);
275 13 : l->recent = l->old = NULL;
276 13 : l->left = max;
277 13 : l->expiration = expiration;
278 : #ifdef HAVE_LIBJUDY
279 13 : l->PJHSArray = (Pvoid_t)NULL;
280 : #endif
281 :
282 13 : if (pthread_create (&l->gc, NULL, garbage_collector, l))
283 : {
284 0 : pthread_mutex_destroy (&l->lock);
285 0 : free (l);
286 0 : return NULL;
287 : }
288 :
289 13 : return l;
290 : }
291 :
292 : /**
293 : * Empties an existing unlocked list. Always succeeds.
294 : *
295 : * @param max new value for maximum number of items allowed.
296 : */
297 : void teredo_list_reset (teredo_peerlist *l, unsigned max)
298 22 : {
299 22 : pthread_mutex_lock (&l->lock);
300 :
301 : #ifdef HAVE_LIBJUDY
302 : // detach old array
303 22 : Pvoid_t array = l->PJHSArray;
304 22 : l->PJHSArray = (Pvoid_t)NULL;
305 : #endif
306 :
307 22 : teredo_listitem *recent = l->recent, *old = l->old;
308 : // unlinks peers and resets lists
309 22 : l->recent = l->old = NULL;
310 22 : l->left = max;
311 :
312 22 : pthread_mutex_unlock (&l->lock);
313 :
314 : /* the mutex is not needed for actual memory release */
315 22 : listitem_recdestroy (old);
316 22 : listitem_recdestroy (recent);
317 :
318 : #ifdef HAVE_LIBJUDY
319 : // destroy the old array that was detached before unlocking
320 : Word_t Rc_word;
321 22 : JHSFA (Rc_word, array);
322 : #endif
323 22 : }
324 :
325 : /**
326 : * Destroys an existing unlocked list.
327 : */
328 : void teredo_list_destroy (teredo_peerlist *l)
329 13 : {
330 13 : teredo_list_reset (l, 0);
331 :
332 13 : pthread_cancel (l->gc);
333 13 : pthread_join (l->gc, NULL);
334 13 : pthread_mutex_destroy (&l->lock);
335 :
336 13 : free (l);
337 13 : }
338 :
339 : /**
340 : * Locks the list and looks up a peer in an unlocked list.
341 : * On success, the list must be unlocked with teredo_list_release(), otherwise
342 : * the next call to teredo_list_lookup will deadlock. Unlocking the list after
343 : * a failure is not defined.
344 : *
345 : * @param create if not NULL, the peer will be added to the list if it is not
346 : * present already, and *create will be true on return. If create is not NULL
347 : * but the peer was already present, *create will be false on return.
348 : * *create is undefined on return in case of error.
349 : *
350 : * @return The peer if found or created. NULL on error (when create is not
351 : * NULL), or if the peer was not found (when create is NULL).
352 : */
353 : teredo_peer *teredo_list_lookup (teredo_peerlist *restrict list,
354 : const struct in6_addr *restrict addr,
355 : bool *restrict create)
356 611148 : {
357 : teredo_listitem *p;
358 :
359 611148 : pthread_mutex_lock (&list->lock);
360 :
361 : #ifdef HAVE_LIBJUDY
362 611148 : teredo_listitem **pp = NULL;
363 :
364 : /* Judy dynamic array-based fast lookup */
365 : {
366 : void *PValue;
367 :
368 611148 : if (create != NULL)
369 : {
370 302316 : JHSI (PValue, list->PJHSArray, (uint8_t *)addr, 16);
371 302316 : if (PValue == PJERR)
372 : {
373 0 : pthread_mutex_unlock (&list->lock);
374 0 : return NULL;
375 : }
376 302316 : pp = (teredo_listitem **)PValue;
377 302316 : p = *pp;
378 : }
379 : else
380 : {
381 308832 : JHSG (PValue, list->PJHSArray, (uint8_t *)addr, 16);
382 308832 : pp = (teredo_listitem **)PValue;
383 308832 : p = (pp != NULL) ? *pp : NULL;
384 : }
385 :
386 : }
387 : #else
388 : /* Slow O(n) simplistic peer lookup */
389 : p = NULL;
390 :
391 : for (p = list->recent; p != NULL; p = p->next)
392 : if (memcmp (&p->key, addr, sizeof (*addr)) == 0)
393 : break;
394 :
395 : if (p == NULL)
396 : for (p = list->old; p != NULL; p = p->next)
397 : if (memcmp (&p->key, addr, sizeof (*addr)) == 0)
398 : break;
399 : #endif
400 :
401 611148 : if (p != NULL)
402 : {
403 : /* peer was already in list */
404 303060 : assert (*(p->pprev) == p);
405 303060 : assert ((p->next == NULL) || (p->next->pprev == &p->next));
406 :
407 303060 : if (create != NULL)
408 0 : *create = false;
409 :
410 : /* move peer to the top of the head of the "recent" list */
411 303060 : if (list->recent != p)
412 : {
413 : // unlinks
414 303060 : if (p->next != NULL)
415 1974 : p->next->pprev = p->pprev;
416 303060 : *(p->pprev) = p->next;
417 :
418 : // inserts at head
419 303060 : p->next = list->recent;
420 303060 : if (p->next != NULL)
421 303054 : p->next->pprev = &p->next;
422 :
423 303060 : list->recent = p;
424 303060 : p->pprev = &list->recent;
425 :
426 303060 : assert (*(p->pprev) == p);
427 303060 : assert ((p->next == NULL) || (p->next->pprev == &p->next));
428 : }
429 :
430 303060 : return &p->peer;
431 : }
432 :
433 308088 : assert (p == NULL);
434 :
435 : /* otherwise, peer was not in list */
436 308088 : if (create == NULL)
437 : {
438 5772 : pthread_mutex_unlock (&list->lock);
439 5772 : return NULL;
440 : }
441 :
442 302316 : *create = true;
443 :
444 : /* Allocates a new peer entry */
445 302316 : if (list->left > 0)
446 302301 : p = listitem_create ();
447 :
448 302316 : if (p == NULL)
449 : {
450 : #ifdef HAVE_LIBJUDY
451 : int Rc_int;
452 15 : JHSD (Rc_int, list->PJHSArray, (uint8_t *)addr, sizeof (*addr));
453 : #endif
454 15 : pthread_mutex_unlock (&list->lock);
455 15 : return NULL;
456 : }
457 :
458 : /* Puts new entry at the head of the list */
459 302301 : p->next = list->recent;
460 302301 : if (p->next != NULL)
461 302282 : p->next->pprev = &p->next;
462 :
463 302301 : p->pprev = &list->recent;
464 302301 : list->recent = p;
465 302301 : p->pprev = &list->recent;
466 :
467 302301 : list->left--;
468 :
469 302301 : assert (*(p->pprev) == p);
470 302301 : assert ((p->next == NULL) || (p->next->pprev == &p->next));
471 :
472 : #ifdef HAVE_LIBJUDY
473 302301 : *pp = p;
474 : #endif
475 302301 : memcpy (&p->key.ip6, addr, sizeof (struct in6_addr));
476 302301 : return &p->peer;
477 : }
478 :
479 :
480 : /**
481 : * Unlocks a list that was locked by teredo_list_lookup().
482 : */
483 : void teredo_list_release (teredo_peerlist *l)
484 605361 : {
485 605361 : pthread_mutex_unlock (&l->lock);
486 605361 : }
|
