ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/vendor/pxys2-2.0.0/ipcache/ipcache.c
Revision: 3252
Committed: Wed Apr 2 20:41:43 2014 UTC (9 years, 11 months ago) by michael
Content type: text/x-csrc
File size: 17609 byte(s)
Log Message:
- Imported pxys2-2.0.0

File Contents

# Content
1 /* Copyright (C) 2003 Stephane Thiell
2 *
3 * This file is part of pxyservd (from pxys)
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 *
19 */
20 #define RCSID "$Id"
21
22 #ifdef HAVE_CONFIG_H
23 #include "config.h"
24 #endif
25
26 #include "ipcache.h"
27
28 #include <peak/peak.h>
29
30 #include <assert.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <time.h>
35 #include <unistd.h>
36 #ifdef IPCACHE_TEST
37 #include <arpa/inet.h>
38 #endif
39
40 struct __ipcache_in4_entry
41 {
42 struct __ipcache_in4_entry *next;
43 struct in_addr key;
44 int lru_ring_refcnt;
45 time_t ts;
46 char data[0]; /* append optional data here */
47 };
48
49 typedef struct __ipcache_in4_entry hentry4;
50
51 struct __ipcache_in6_entry
52 {
53 struct __ipcache_in6_entry *next;
54 struct in6_addr key;
55 int lru_ring_refcnt;
56 time_t ts;
57 char data[0]; /* append optional data here */
58 };
59
60 typedef struct __ipcache_in6_entry hentry6;
61
62 typedef struct __ipcache_lru_ring *ipcache_lru_ring_t;
63
64 struct __ipcache
65 {
66 int buckets;
67 int count;
68 int maxcount;
69 size_t datasize;
70 int flags;
71 peak_mem_pool mem_pool;
72 union
73 {
74 struct __ipcache_in4_entry **v4;
75 struct __ipcache_in6_entry **v6;
76 } table;
77 ipcache_lru_ring_t lru_ring;
78 };
79
80 typedef void (*ipcache_lru_ring_release_func)(ipcache_t cp, void *obj);
81
82 struct __ipcache_lru_ring
83 {
84 int size;
85 int count;
86 int pos_start;
87 int pos_end;
88 ipcache_t cache;
89 void **address;
90 ipcache_lru_ring_release_func rel_fun;
91 };
92
93 static uint32_t hashfun_in4(const struct in_addr *addrptr);
94 static uint32_t hashfun_in6(const struct in6_addr *addrptr);
95
96 static int ipcache_hash_remove_in4(ipcache_t cp, struct in_addr *addr);
97 static int ipcache_hash_remove_in6(ipcache_t cp, struct in6_addr *addr);
98 static void ipcache_release_in4(ipcache_t cp, hentry4 *e);
99 static int ipcache_dispose_in4(ipcache_t cp, hentry4 *e);
100 static void ipcache_release_in6(ipcache_t cp, hentry6 *e);
101 static int ipcache_dispose_in6(ipcache_t cp, hentry6 *e);
102
103 static ipcache_lru_ring_t ipcache_lru_ring_create(ipcache_t cp, size_t size,
104 ipcache_lru_ring_release_func rel_fun);
105 static void ipcache_lru_ring_dispose(ipcache_lru_ring_t ring);
106 static void ipcache_lru_ring_add(ipcache_lru_ring_t ring, void *obj);
107 static int ipcache_lru_ring_clear(ipcache_lru_ring_t ring);
108
109 #ifdef IPCACHE_TEST
110 static int coll;
111 static int llen;
112 #endif
113
114 static uint32_t
115 hashfun_in4(const struct in_addr *addrptr)
116 {
117 return (uint32_t)addrptr->s_addr;
118 }
119
120 static uint32_t
121 hashfun_in6(const struct in6_addr *addrptr)
122 {
123 const u_char *key = (u_char *)addrptr;
124 uint32_t h = 0;
125
126 #define HASH4 \
127 h = h * 33 + *key++; \
128 h = h * 33 + *key++; \
129 h = h * 33 + *key++; \
130 h = h * 33 + *key++
131
132 HASH4;
133 HASH4;
134 HASH4;
135 HASH4;
136
137 return (h);
138 }
139
140 ipcache_t
141 ipcache_create_in4(int size, size_t datasize)
142 {
143 int pos;
144 ipcache_t cp = (ipcache_t)peak_allocate(sizeof(struct __ipcache));
145 cp->buckets = size;
146 cp->count = 0;
147 cp->maxcount = size;
148 cp->datasize = datasize;
149 cp->flags = 0;
150 cp->mem_pool = peak_mem_pool_create(sizeof(hentry4) + cp->datasize, 0);
151 cp->table.v4 = (hentry4 **)peak_allocate(sizeof(hentry4 *) * cp->buckets);
152
153 for (pos = cp->buckets; pos--; )
154 cp->table.v4[pos] = NULL;
155
156 cp->lru_ring = ipcache_lru_ring_create(cp, size,
157 (ipcache_lru_ring_release_func)ipcache_release_in4);
158
159 return cp;
160 }
161
162 ipcache_t
163 ipcache_create_in6(int size, size_t datasize)
164 {
165 int pos;
166 ipcache_t cp = (ipcache_t)peak_allocate(sizeof(struct __ipcache));
167 cp->buckets = size;
168 cp->count = 0;
169 cp->maxcount = size;
170 cp->datasize = datasize;
171 cp->flags = 1;
172 cp->mem_pool = peak_mem_pool_create(sizeof(hentry6) + cp->datasize, 0);
173 cp->table.v6 = (hentry6 **)peak_allocate(sizeof(hentry6 *) * cp->buckets);
174
175 for (pos = cp->buckets; pos--; )
176 cp->table.v6[pos] = NULL;
177
178 cp->lru_ring = ipcache_lru_ring_create(cp, size,
179 (ipcache_lru_ring_release_func)ipcache_release_in6);
180
181 return cp;
182 }
183
184 void
185 ipcache_dispose(ipcache_t cp)
186 {
187 ipcache_lru_ring_dispose(cp->lru_ring);
188 peak_release(cp->mem_pool);
189 peak_deallocate((void *)cp->table.v4);
190 peak_deallocate(cp);
191 }
192
193 int
194 ipcache_clear(ipcache_t cp)
195 {
196 int result = ipcache_lru_ring_clear(cp->lru_ring);
197 assert (cp->count == 0);
198 return result;
199 }
200
201 void
202 ipcache_add_in4(ipcache_t cp, const struct in_addr *addr, time_t t,
203 const void *data)
204 {
205 hentry4 *e;
206 uint32_t slot = hashfun_in4(addr) % cp->buckets;
207
208 for (e = cp->table.v4[slot]; e; e = e->next)
209 {
210 if (e->key.s_addr == addr->s_addr)
211 {
212 e->lru_ring_refcnt++;
213 e->ts = t;
214 ipcache_lru_ring_add(cp->lru_ring, e);
215 return;
216 }
217 }
218
219 e = (hentry4 *)peak_mem_pool_new(cp->mem_pool);
220 e->key = *addr;
221 e->lru_ring_refcnt = 0;
222 e->ts = t;
223 if (cp->datasize > 0)
224 memcpy(e->data, data, cp->datasize);
225
226 e->next = cp->table.v4[slot];
227
228 #ifdef IPCACHE_TEST
229 if (e->next != NULL)
230 {
231 int cnt;
232 hentry4 *ti = e;
233 coll++;
234 for (cnt = 0; ti->next != NULL; ti = ti->next)
235 cnt++;
236 if (cnt > llen)
237 llen = cnt;
238 }
239 #endif
240 cp->table.v4[slot] = e;
241 cp->count++;
242
243 e->lru_ring_refcnt++;
244 ipcache_lru_ring_add(cp->lru_ring, e);
245 }
246
247 void
248 ipcache_add_in6(ipcache_t cp, const struct in6_addr *addr, time_t t,
249 const void *data)
250 {
251 hentry6 *e;
252 uint32_t slot = hashfun_in6(addr) % cp->buckets;
253
254 for (e = cp->table.v6[slot]; e; e = e->next)
255 {
256 if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0)
257 {
258 e->lru_ring_refcnt++;
259 e->ts = t;
260 ipcache_lru_ring_add(cp->lru_ring, e);
261 return;
262 }
263 }
264
265 e = (hentry6 *)peak_mem_pool_new(cp->mem_pool);
266 e->key = *addr;
267 e->lru_ring_refcnt = 0;
268 e->ts = t;
269
270 if (cp->datasize > 0)
271 memcpy(e->data, data, cp->datasize);
272 e->next = cp->table.v6[slot];
273 cp->table.v6[slot] = e;
274 cp->count++;
275
276 e->lru_ring_refcnt++;
277 ipcache_lru_ring_add(cp->lru_ring, e);
278 }
279
280 int
281 ipcache_invalidate_in4(ipcache_t cp, const struct in_addr *addr)
282 {
283 hentry4 *e;
284 uint32_t slot = hashfun_in4(addr) % cp->buckets;
285
286 for (e = cp->table.v4[slot]; e; e = e->next)
287 {
288 if (e->key.s_addr == addr->s_addr && e->ts != 0)
289 {
290 printf("ipcache_invalidate_in4: found!\n");
291 e->ts = 0;
292 return 0;
293 }
294 }
295 printf("ipcache_invalidate_in4: not found!\n");
296 return -1;
297 }
298
299 int
300 ipcache_invalidate_in6(ipcache_t cp, const struct in6_addr *addr)
301 {
302 hentry6 *e;
303 uint32_t slot = hashfun_in6(addr) % cp->buckets;
304
305 for (e = cp->table.v6[slot]; e; e = e->next)
306 {
307 if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0
308 && e->ts != 0)
309 {
310 e->ts = 0;
311 return 0;
312 }
313 }
314 return -1;
315 }
316
317 static int
318 ipcache_hash_remove_in4(ipcache_t cp, struct in_addr *addr)
319 {
320 hentry4 **e, *kill;
321 uint32_t slot = hashfun_in4(addr) % cp->buckets;
322
323 for (e = &cp->table.v4[slot]; *e; e = &((*e)->next))
324 {
325 if ((*e)->key.s_addr == addr->s_addr)
326 {
327 cp->count--;
328 kill = *e;
329 *e = (*e)->next;
330 peak_mem_pool_delete(cp->mem_pool, kill);
331 return 0;
332 }
333 }
334 return -1;
335 }
336
337 static int
338 ipcache_hash_remove_in6(ipcache_t cp, struct in6_addr *addr)
339 {
340 hentry6 **e, *kill;
341 uint32_t slot = hashfun_in6(addr) % cp->buckets;
342
343 for (e = &cp->table.v6[slot]; *e; e = &((*e)->next))
344 {
345 if (memcmp(&(*e)->key, addr, sizeof(struct in6_addr)) == 0)
346 {
347 cp->count--;
348 kill = *e;
349 *e = (*e)->next;
350 peak_mem_pool_delete(cp->mem_pool, kill);
351 return 0;
352 }
353 }
354 return -1;
355 }
356
357
358 static void
359 ipcache_release_in4(ipcache_t cp, hentry4 *e)
360 {
361 int err;
362
363 assert(e->lru_ring_refcnt > 0);
364
365 if (!--e->lru_ring_refcnt)
366 {
367 err = ipcache_dispose_in4(cp, e);
368 assert (err == 0);
369 }
370 }
371
372 static int
373 ipcache_dispose_in4(ipcache_t cp, hentry4 *e)
374 {
375 return ipcache_hash_remove_in4(cp, &e->key);
376 }
377
378 static void
379 ipcache_release_in6(ipcache_t cp, hentry6 *e)
380 {
381 int err;
382
383 assert(e->lru_ring_refcnt > 0);
384
385 if (!--e->lru_ring_refcnt)
386 {
387 err = ipcache_dispose_in6(cp, e);
388 assert (err == 0);
389 }
390 }
391
392 static int
393 ipcache_dispose_in6(ipcache_t cp, hentry6 *e)
394 {
395 return ipcache_hash_remove_in6(cp, &e->key);
396 }
397
398 time_t
399 ipcache_find_in4(ipcache_t cp, const struct in_addr *addr, void **od)
400 {
401 hentry4 *e;
402 uint32_t slot = hashfun_in4(addr) % cp->buckets;
403
404 for (e = cp->table.v4[slot]; e; e = e->next)
405 if (e->key.s_addr == addr->s_addr)
406 {
407 if (od && cp->datasize)
408 *od = e->data;
409 return e->ts;
410 }
411
412 return 0;
413 }
414
415 time_t
416 ipcache_find_in6(ipcache_t cp, const struct in6_addr *addr, void **od)
417 {
418 hentry6 *e;
419 uint32_t slot = hashfun_in6(addr) % cp->buckets;
420
421 for (e = cp->table.v6[slot]; e; e = e->next)
422 if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0)
423 {
424 if (od && cp->datasize)
425 *od = e->data;
426 return e->ts;
427 }
428
429 return 0;
430 }
431
432 size_t
433 ipcache_get_count(ipcache_t cp)
434 {
435 return cp->lru_ring->count;
436 }
437
438 /**************** Associated internal LRU Ring *****************/
439
440 static ipcache_lru_ring_t
441 ipcache_lru_ring_create(ipcache_t cp, size_t size,
442 ipcache_lru_ring_release_func rel_fun)
443 {
444 ipcache_lru_ring_t ring =
445 (ipcache_lru_ring_t)peak_allocate(sizeof(struct __ipcache_lru_ring));
446 ring->size = size;
447 ring->count = 0;
448 ring->address = (void **)peak_allocate(sizeof(void *) * ring->size);
449 ring->pos_start = 0;
450 ring->pos_end = -1;
451 ring->cache = cp;
452 ring->rel_fun = rel_fun;
453 return ring;
454 }
455
456 static void
457 ipcache_lru_ring_dispose(ipcache_lru_ring_t ring)
458 {
459 peak_deallocate(ring->address);
460 peak_deallocate(ring);
461 }
462
463 static void
464 ipcache_lru_ring_add(ipcache_lru_ring_t ring, void *obj)
465 {
466 if (++ring->pos_end >= ring->size)
467 ring->pos_end = 0;
468
469 if (ring->count >= ring->size)
470 {
471 assert (ring->pos_end == ring->pos_start);
472 assert (ring->count == ring->size);
473
474 (*ring->rel_fun)(ring->cache, ring->address[ring->pos_end]);
475
476 if (++ring->pos_start >= ring->size)
477 ring->pos_start = 0;
478 }
479 else
480 ring->count++;
481
482 ring->address[ring->pos_end] = obj;
483 }
484
485 static int
486 ipcache_lru_ring_clear(ipcache_lru_ring_t ring)
487 {
488 int result = ring->count;
489
490 while (ring->count > 0)
491 {
492 (*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
493 if (++ring->pos_start >= ring->size)
494 ring->pos_start = 0;
495 ring->count--;
496 }
497 assert(ring->pos_start == ring->pos_end);
498
499 return result;
500 }
501
502 /************************ Special cleanup ************************/
503
504 size_t
505 ipcache_cleanup(ipcache_t cp, time_t expire_ts)
506 {
507 ipcache_lru_ring_t ring = cp->lru_ring;
508 size_t count = 0;
509
510 if (cp->flags & 1) /* ipv6 */
511 {
512 hentry6 *e6;
513
514 for (e6 = (hentry6 *)ring->address[ring->pos_start];
515 ring->count > 0 && e6->ts <= expire_ts;
516 e6 = (hentry6 *)ring->address[ring->pos_start])
517 {
518 (*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
519 if (++ring->pos_start >= ring->size)
520 ring->pos_start = 0;
521 ring->count--;
522 count++;
523 }
524 }
525 else
526 {
527 hentry4 *e4;
528
529 for (e4 = (hentry4 *)ring->address[ring->pos_start];
530 ring->count > 0 && e4->ts <= expire_ts;
531 e4 = (hentry4 *)ring->address[ring->pos_start])
532 {
533 (*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
534 if (++ring->pos_start >= ring->size)
535 ring->pos_start = 0;
536 ring->count--;
537 count++;
538 }
539 }
540 return count;
541 }
542
543
544 /************************ Cache storage ************************/
545
546 typedef struct __ipcache_file_header
547 {
548 uint32_t sig; // file signature
549 int32_t last_update; // file last update time
550 uint32_t sizeof_entry; // size of an entry in bytes
551 uint32_t count; // number of entries
552 } ipcache_file_header;
553
554 typedef struct __ipcache_file_entry4
555 {
556 struct in_addr addr;
557 time_t ts;
558 char data[0];
559 } ipcache_file_entry4;
560
561 typedef struct __ipcache_file_entry6
562 {
563 struct in6_addr addr;
564 time_t ts;
565 char data[0];
566 } ipcache_file_entry6;
567
568
569 #define SWAP_NMEMB 16
570
571 int
572 ipcache_swapin(ipcache_t cp, const char *file, uint32_t sig)
573 {
574 int res = -1;
575 FILE *fp;
576 ipcache_file_header head;
577 ipcache_file_entry4 *e4p, *e4p2;
578 ipcache_file_entry6 *e6p, *e6p2;
579 size_t size, i, n;
580 uint32_t cnt = 0;
581
582 if ((fp = fopen(file, "r")) == NULL)
583 return res;
584
585 if (fread(&head, sizeof(head), 1, fp) < 1 || (head.sig != sig))
586 goto swapin_failure;
587
588 if (cp->flags & 1)
589 {
590 size = sizeof(ipcache_file_entry6) + cp->datasize;
591 if (head.sizeof_entry != size)
592 goto swapin_failure;
593
594 e6p = (ipcache_file_entry6 *)peak_allocate(size * SWAP_NMEMB);
595
596 while ((n = fread(e6p, size, SWAP_NMEMB, fp)) > 0)
597 for (i = 0, e6p2 = e6p; i < n; i++, cnt++, ((char*)e6p2) += size)
598 ipcache_add_in6(cp, &e6p2->addr, e6p2->ts, e6p2->data);
599
600 peak_deallocate(e6p);
601 }
602 else
603 {
604 size = sizeof(ipcache_file_entry4) + cp->datasize;
605 if (head.sizeof_entry != size)
606 goto swapin_failure;
607
608 e4p = (ipcache_file_entry4 *)peak_allocate(size * SWAP_NMEMB);
609
610 while ((n = fread(e4p, size, SWAP_NMEMB, fp)) > 0)
611 for (i = 0, e4p2 = e4p; i < n; i++, cnt++, ((char *)e4p2) += size)
612 ipcache_add_in4(cp, &e4p2->addr, e4p2->ts, e4p2->data);
613
614 peak_deallocate(e4p);
615 }
616
617 if (head.count == cnt)
618 res = 0; /* success */
619
620 swapin_failure:
621 fclose(fp);
622 return res;
623 }
624
625 int
626 ipcache_swapout(ipcache_t cp, const char *file, uint32_t sig)
627 {
628 int res = -1;
629 FILE *fp;
630 ipcache_file_header head;
631 ipcache_lru_ring_t ring = cp->lru_ring;
632 size_t size;
633 int i, pos;
634
635 if ((fp = fopen(file, "w")) == NULL)
636 return res;
637
638 size = (cp->flags & 1) ? sizeof(ipcache_file_entry6)
639 : sizeof(ipcache_file_entry4);
640 size += cp->datasize;
641
642 head.sig = sig;
643 head.last_update = peak_time();
644 head.sizeof_entry = size;
645 head.count = ring->count;
646
647 if (fwrite(&head, sizeof(head), 1, fp) < 1)
648 goto swapout_failure;
649
650 if (cp->flags & 1) /* ipv6 */
651 {
652 ipcache_file_entry6 *fe6p =
653 (ipcache_file_entry6 *)peak_allocate(size);
654 hentry6 *he6p;
655
656 for (i = ring->count, pos = ring->pos_start; i > 0; i--)
657 {
658 he6p = (hentry6 *)ring->address[pos];
659 fe6p->addr = he6p->key;
660 fe6p->ts = he6p->ts;
661 if (cp->datasize > 0)
662 memcpy(fe6p->data, he6p->data, cp->datasize);
663 if (fwrite(fe6p, size, 1, fp) < 1)
664 goto swapout_failure;
665
666 if (++pos >= ring->size)
667 pos = 0;
668 }
669 peak_deallocate(fe6p);
670 }
671 else
672 {
673 ipcache_file_entry4 *fe4p =
674 (ipcache_file_entry4 *)peak_allocate(size);
675 hentry4 *he4p;
676
677 for (i = ring->count, pos = ring->pos_start; i > 0; i--)
678 {
679 he4p = (hentry4 *)ring->address[pos];
680 fe4p->addr = he4p->key;
681 fe4p->ts = he4p->ts;
682 if (cp->datasize > 0)
683 memcpy(fe4p->data, he4p->data, cp->datasize);
684 if (fwrite(fe4p, size, 1, fp) < 1)
685 goto swapout_failure;
686
687 if (++pos >= ring->size)
688 pos = 0;
689 }
690 peak_deallocate(fe4p);
691 }
692 res = 0;
693 swapout_failure:
694 fclose(fp);
695 return res;
696 }
697
698
699
700 /* Test */
701
702 #ifdef IPCACHE_TEST
703 int
704 main(int argc, char *argv[])
705 {
706 ipcache_t cache = ipcache_create_in4(CACHESIZE, 0);
707 struct in_addr addr;
708 int i, j, res;
709 int found = 0, loaded = 0;
710 FILE *fp;
711 char buf[32];
712 struct in_addr *randips = malloc(sizeof(struct in_addr) * LOOPS);
713
714 fp = fopen("urandip.txt", "r");
715 assert(fp);
716
717 i = 0;
718 while(fgets(buf, sizeof(buf), fp))
719 {
720 buf[strlen(buf)-1] = '\0';
721 randips[i++].s_addr = inet_addr(buf);
722 loaded++;
723 }
724
725 for (j = 0; i < LOOPS; i++, j++)
726 {
727 randips[i] = randips[j];
728 randips[i].s_addr += 2;
729 }
730 fclose(fp);
731
732 for (i = 0; i < LOOPS; i++)
733 {
734 addr = randips[i];
735 if (ipcache_find_in4(cache, &addr, NULL) != 0)
736 found++;
737
738 ipcache_add_in4(cache, &addr, peak_time(), NULL);
739 }
740
741 #if CACHESIZE >= LOOPS
742 for (i = 0; i < LOOPS; i++)
743 {
744 addr = randips[i];
745 assert (ipcache_find_in4(cache, &addr, NULL) != 0);
746 }
747 #endif
748 printf("coll=%d loaded=%d %f%% found=%d llen=%d\n", coll, loaded,
749 100.0 - (100.0 * (double)coll/(double)(LOOPS-found)), found, llen);
750
751 printf("swapout...\n");
752 res = ipcache_swapout(cache, "test.cache", 42);
753 assert(res == 0);
754 ipcache_dispose(cache);
755 cache = ipcache_create_in4(CACHESIZE, 0);
756 printf("swapin...\n");
757 res = ipcache_swapin(cache, "test.cache", 42);
758 assert(res == 0);
759 #if CACHESIZE >= LOOPS
760 printf("recovery test...");
761 for (i = 0; i < LOOPS; i++)
762 {
763 addr = randips[i];
764 assert (ipcache_find_in4(cache, &addr, NULL) != 0);
765 }
766 #endif
767 printf("ok\n");
768 return 0;
769 }
770 #endif /* IPCACHE_TEST */