Statistics
| Branch: | Revision:

grapes / src / TopologyManager / blist_cache.c @ c3d9eba1

History | View | Annotate | Download (15.7 KB)

1
/*
2
 *  Copyright (c) 2010 Luca Abeni
3
 *
4
 *  This is free software; see lgpl-2.1.txt
5
 */
6

    
7
#include <arpa/inet.h>
8
#include <stdint.h>
9
#include <stdlib.h>
10
#include <string.h>
11

    
12
#include <stdio.h>
13

    
14
#include "net_helper.h"
15
#include "blist_cache.h"
16
#include "int_coding.h"
17

    
18
#define NOREPLY_FLAG_UNSET 254
19
#define NOREPLY_FLAG_SET 1
20

    
21
struct cache_entry {
22
  struct nodeID *id;
23
  uint32_t timestamp;
24
  uint8_t flags;
25
};
26

    
27
struct peer_cache {
28
  struct cache_entry *entries;
29
  struct nodeID **blist;
30
  int cache_size;
31
  int blist_size;
32
  int current_size;
33
  int metadata_size;
34
  uint8_t *metadata;
35
  int max_timestamp;
36
};
37

    
38
struct nodeID *blist_nodeid(const struct peer_cache *c, int i)
39
{
40
  if (i < c->current_size) {
41
    return c->entries[i].id;
42
  }
43

    
44
  return NULL;
45
}
46

    
47
const void *blist_get_metadata(const struct peer_cache *c, int *size)
48
{
49
  *size = c->metadata_size;
50
  return c->metadata;
51
}
52

    
53
int blist_cache_metadata_update(struct peer_cache *c, struct nodeID *p, const void *meta, int meta_size)
54
{
55
  int i;
56

    
57
  if (!meta_size || meta_size != c->metadata_size) {
58
    return -3;
59
  }
60
  for (i = 0; i < c->current_size; i++) {
61
    if (nodeid_equal(c->entries[i].id, p)) {
62
      memcpy(c->metadata + i * meta_size, meta, meta_size);
63
      return 1;
64
    }
65
  }
66

    
67
  return 0;
68
}
69

    
70
static int find_in_bl(struct peer_cache *c, struct nodeID *neighbour) {
71
        int i;
72
        for (i=0; i < c->blist_size; i++) {
73
                if (nodeid_equal(c->blist[i], neighbour)) {
74
                        return i;
75
                }
76
        }
77
        return c->blist_size;
78
}
79

    
80
int blist_cache_del(struct peer_cache *c, struct nodeID *neighbour)
81
{
82
  int i;
83
  int found = 0;
84

    
85
  for (i = 0; i < c->current_size; i++) {
86
    if (nodeid_equal(c->entries[i].id, neighbour)) {
87
      nodeid_free(c->entries[i].id);
88
      c->current_size--;
89
      found = 1;
90
      if (c->metadata_size && (i < c->current_size)) {
91
        memmove(c->metadata + c->metadata_size * i,
92
                c->metadata + c->metadata_size * (i + 1),
93
                c->metadata_size * (c->current_size - i));
94
      }
95
    }
96
    if (found && (i < c->current_size)) {
97
      c->entries[i] = c->entries[i + 1];
98
    }
99
  }
100

    
101
  return c->current_size;
102
}
103

    
104
int blist_cache_add_ranked(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size, ranking_function f, const void *tmeta)
105
{
106
  int i, pos = 0;
107

    
108
  if (meta_size && meta_size != c->metadata_size) {
109
    return -3;
110
  }
111
  for (i = 0; i < c->current_size; i++) {
112
    if (nodeid_equal(c->entries[i].id, neighbour)) {
113
                if (f != NULL) {
114
                        if (memcmp(c->metadata+meta_size*i, meta, meta_size) != 0) {
115
                                blist_cache_del(c,neighbour);
116
                                if (i == c->current_size) break;
117
                        } else {
118
                                c->entries[i].flags &= NOREPLY_FLAG_UNSET;
119
                                return -1;
120
                        }
121
                } else {
122
                        blist_cache_metadata_update(c,neighbour,meta,meta_size);
123
                        c->entries[i].flags &= NOREPLY_FLAG_UNSET;
124
                        return -1;
125
                }
126
    }
127
    if ((f != NULL) && f(tmeta, meta, c->metadata+(c->metadata_size * i)) == 2) {
128
      pos++;
129
    }
130
  }
131
  if (c->current_size == c->cache_size) {
132
    return -2;
133
  }
134
  if (c->metadata_size) {
135
    memmove(c->metadata + (pos + 1) * c->metadata_size, c->metadata + pos * c->metadata_size, (c->current_size - pos) * c->metadata_size);
136
    if (meta_size) {
137
      memcpy(c->metadata + pos * c->metadata_size, meta, meta_size);
138
    } else {
139
      memset(c->metadata + pos * c->metadata_size, 0, c->metadata_size);
140
    }
141
  }
142
  for (i = c->current_size; i > pos; i--) {
143
    c->entries[i] = c->entries[i - 1];
144
  }
145
  c->entries[pos].id = nodeid_dup(neighbour);
146
  c->entries[pos].timestamp = 1;
147
  c->entries[pos].flags = 00;
148
  c->current_size++;
149

    
150
  pos = find_in_bl(c, neighbour);
151
  if (pos < c->blist_size) {
152
        nodeid_free(c->blist[pos]);
153
        c->blist_size--;
154
        for (i = pos; i < c->blist_size; i++) {
155
                c->blist[i] = c->blist[i + 1];
156
        }
157
  }
158

    
159
  return c->current_size;
160
}
161

    
162
int blist_cache_add(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size)
163
{
164
  return blist_cache_add_ranked(c, neighbour, meta, meta_size, NULL, NULL);
165
}
166

    
167
void blist_cache_update_tout(struct peer_cache *c)
168
{
169
  int i;
170
  
171
  for (i = 0; i < c->current_size; i++) {
172
    if (c->max_timestamp && (c->entries[i].timestamp == c->max_timestamp)) {
173
      int j = i;
174

    
175
      while(j < c->current_size && c->entries[j].id) {
176
        nodeid_free(c->entries[j].id);
177
        c->entries[j++].id = NULL;
178
      }
179
      c->current_size = i;        /* The cache is ordered by timestamp...
180
                                   all the other entries wiil be older than
181
                                   this one, so remove all of them
182
                                */
183
    } else {
184
      c->entries[i].timestamp++;
185
    }
186
  }
187
}
188

    
189
void blist_cache_update(struct peer_cache *c)
190
{
191
  int i;
192
  
193
  for (i = 0; i < c->current_size; i++) {
194
      c->entries[i].timestamp++;
195
  }
196
}
197

    
198
struct peer_cache *blist_cache_init(int n, int metadata_size, int max_timestamp)
199
{
200
  struct peer_cache *res;
201

    
202
  res = malloc(sizeof(struct peer_cache));
203
  if (res == NULL) {
204
    return NULL;
205
  }
206
  res->max_timestamp = max_timestamp;
207
  res->cache_size = n;
208
  res->current_size = 0;
209
  res->entries = malloc(sizeof(struct cache_entry) * n);
210
  if (res->entries == NULL) {
211
    free(res);
212

    
213
    return NULL;
214
  }
215
  
216
  memset(res->entries, 0, sizeof(struct cache_entry) * n);
217
  if (metadata_size) {
218
    res->metadata = malloc(metadata_size * n);
219
  } else {
220
    res->metadata = NULL;
221
  }
222

    
223
  if (res->metadata) {
224
    res->metadata_size = metadata_size;
225
    memset(res->metadata, 0, metadata_size * n);
226
  } else {
227
    res->metadata_size = 0;
228
  }
229

    
230
  res->blist = calloc(n, sizeof(struct nodeID *));
231
  res->blist_size = 0;
232

    
233
  return res;
234
}
235

    
236
void blist_cache_free(struct peer_cache *c)
237
{
238
  int i;
239

    
240
  for (i = 0; i < c->current_size; i++) {
241
    if(c->entries[i].id) {
242
      nodeid_free(c->entries[i].id);
243
    }
244
  }
245
  free(c->entries);
246
  free(c->metadata);
247

    
248
  for (i = 0; i < c->blist_size; i++) {
249
        nodeid_free(c->blist[i]);
250
  }
251
  free(c->blist);
252

    
253
  free(c);
254
}
255

    
256
static int in_cache(const struct peer_cache *c, const struct cache_entry *elem)
257
{
258
  int i;
259

    
260
  for (i = 0; i < c->current_size; i++) {
261
    if (nodeid_equal(c->entries[i].id, elem->id)) {
262
      return i;
263
    }
264
  }
265

    
266
  return -1;
267
}
268

    
269
static int blacklist_this (struct peer_cache *c, int indx) {
270

    
271
        int i;
272
        if (c->blist_size == c->cache_size) {
273
                nodeid_free(c->blist[0]);
274
                for (i = 1; i < c->blist_size; i++) {
275
                        c->blist[i - 1] = c->blist[i];
276
                }
277
                c->blist_size--;
278
        }
279
        c->blist[c->blist_size] = nodeid_dup(c->entries[indx].id);
280
        blist_cache_del(c, c->blist[c->blist_size]);
281
        c->blist_size++;
282
        return c->blist_size;
283
}
284

    
285
struct nodeID *blist_rand_peer(struct peer_cache *c, void **meta, int max)
286
{
287
  int j;
288
  static void *new_meta = NULL;
289
  new_meta = realloc(new_meta, c->metadata_size);
290
  if (c->current_size == 0) {
291
    return NULL;
292
  }
293
  if (!max || max >= c->current_size)
294
        max = c->current_size;
295
  else
296
        ++max;
297
  j = ((double)rand() / (double)RAND_MAX) * max;
298

    
299
  if (c->entries[j].flags & NOREPLY_FLAG_SET) {
300
        if (meta) {
301
                *meta = new_meta;
302
                memcpy(*meta, c->metadata + (j * c->metadata_size), c->metadata_size);
303
        }
304
        blacklist_this(c, j);
305
        return c->blist[c->blist_size - 1];
306
  }
307
  c->entries[j].flags |= NOREPLY_FLAG_SET;
308

    
309
  if (meta) {
310
    *meta = c->metadata + (j * c->metadata_size);
311
  }
312

    
313
  return c->entries[j].id;
314
}
315

    
316
struct peer_cache *blist_entries_undump(const uint8_t *buff, int size)
317
{
318
  struct peer_cache *res;
319
  int i = 0;
320
  const uint8_t *p = buff;
321
  uint8_t *meta;
322
  int cache_size, metadata_size;
323

    
324
  cache_size = int_rcpy(buff);
325
  metadata_size = int_rcpy(buff + 4);
326
  p = buff + 8;
327
  res = blist_cache_init(cache_size, metadata_size, 0);
328
  meta = res->metadata;
329
  while (p - buff < size) {
330
    int len;
331

    
332
    res->entries[i].timestamp = int_rcpy(p);
333
    p += sizeof(uint32_t);
334
    res->entries[i].flags = p[0];
335
    res->entries[i++].id = nodeid_undump(++p, &len);
336
    p += len;
337
    if (metadata_size) {
338
      memcpy(meta, p, metadata_size);
339
      p += metadata_size;
340
      meta += metadata_size;
341
    }
342
  }
343
  res->current_size = i;
344
if (p - buff != size) { fprintf(stderr, "Waz!! %d != %d\n", (int)(p - buff), size); exit(-1);}
345

    
346
  return res;
347
}
348

    
349
int blist_cache_header_dump(uint8_t *b, const struct peer_cache *c)
350
{
351
  int_cpy(b, c->cache_size);
352
  int_cpy(b + 4, c->metadata_size);
353

    
354
  return 8;
355
}
356

    
357
int blist_entry_dump(uint8_t *b, struct peer_cache *c, int i, size_t max_write_size)
358
{
359
  int res;
360
  int size = 0;
361
 
362
  if (i && (i >= c->cache_size - 1)) {
363
    return 0;
364
  }
365
  int_cpy(b, c->entries[i].timestamp);
366
  size = +4;
367
  b[size++] = c->entries[i].flags;
368
  res = nodeid_dump(b + size, c->entries[i].id, max_write_size - size);
369
  if (res < 0 ) {
370
    fprintf (stderr,"cavolo1\n");
371
    return -1;
372
  }
373
  size += res;
374
  if (c->metadata_size) {
375
    if (c->metadata_size > max_write_size - size) {
376
      fprintf (stderr,"cavolo2\n");
377
      return -1;
378
    }
379
    memcpy(b + size, c->metadata + c->metadata_size * i, c->metadata_size);
380
    size += c->metadata_size;
381
  }
382

    
383
  return size;
384
}
385

    
386
struct peer_cache *blist_cache_rank (const struct peer_cache *c, ranking_function rank, const struct nodeID *target, const void *target_meta)
387
{
388
        struct peer_cache *res;
389
        int i,j,pos;
390

    
391
        res = blist_cache_init(c->cache_size, c->metadata_size, c->max_timestamp);
392
        if (res == NULL) {
393
                return res;
394
        }
395

    
396
        for (i = 0; i < c->current_size; i++) {
397
                if (!target || !nodeid_equal(c->entries[i].id,target)) {
398
                        pos = 0;
399
                        for (j=0; j<res->current_size;j++) {
400
                                if (((rank != NULL) && rank(target_meta, c->metadata+(c->metadata_size * i), res->metadata+(res->metadata_size * j)) == 2) ||
401
                                        ((rank == NULL) && res->entries[j].timestamp < c->entries[i].timestamp)) {
402
                                        pos++;
403
                                }
404
                        }
405
                        if (c->metadata_size) {
406
                                memmove(res->metadata + (pos + 1) * res->metadata_size, res->metadata + pos * res->metadata_size, (res->current_size - pos) * res->metadata_size);
407
                                memcpy(res->metadata + pos * res->metadata_size, c->metadata+(c->metadata_size * i), res->metadata_size);
408
                        }
409
                        for (j = res->current_size; j > pos; j--) {
410
                                res->entries[j] = res->entries[j - 1];
411
                        }
412
                        res->entries[pos].id = nodeid_dup(c->entries[i].id);
413
                        res->entries[pos].timestamp = c->entries[i].timestamp;
414
                        res->entries[pos].flags = c->entries[i].flags;
415
                        res->current_size++;
416
                }
417
        }
418

    
419
        for (i = 0; i < c->blist_size; i++) {
420
                res->blist[i] = nodeid_dup(c->blist[i]);
421
        }
422
        res->blist_size = c->blist_size;
423

    
424
        return res;
425
}
426

    
427
// It MUST always be called with c1 = current local_cache to ensure black_list continuity
428
struct peer_cache *blist_cache_union(struct peer_cache *c1, struct peer_cache *c2, int *size) {
429
        int n,pos;
430
        struct peer_cache *new_cache;
431
        uint8_t *meta;
432

    
433
        if (c1->metadata_size != c2->metadata_size) {
434
                return NULL;
435
        }
436

    
437
        new_cache = blist_cache_init(c1->current_size + c2->current_size, c1->metadata_size, c1->max_timestamp);
438
        if (new_cache == NULL) {
439
                return NULL;
440
        }
441

    
442
        meta = new_cache->metadata;
443

    
444
        for (n = 0; n < c1->current_size; n++) {
445
                if (new_cache->metadata_size) {
446
                        memcpy(meta, c1->metadata + n * c1->metadata_size, c1->metadata_size);
447
                        meta += new_cache->metadata_size;
448
                }
449
                new_cache->entries[new_cache->current_size++] = c1->entries[n];
450
                c1->entries[n].id = NULL;
451
        }
452

    
453

    
454
        for (n = 0; n < c1->blist_size; n++) {
455
                if (!nodeid_equal(c1->blist[n], c2->entries[0].id)) { // sender should never be blacklisted
456
                        new_cache->blist[new_cache->blist_size++] = c1->blist[n];
457
                        c1->blist[n] = NULL;
458
                }
459
        }
460

    
461
        for (n = 0; n < c2->current_size; n++) {
462
                pos = in_cache(new_cache, &c2->entries[n]);
463
                if (pos >= 0) {
464
                        if (!n) new_cache->entries[pos].flags &= NOREPLY_FLAG_UNSET; // reset flags of sender
465
                        if (new_cache->entries[pos].timestamp > c2->entries[n].timestamp) {
466
                                blist_cache_metadata_update(new_cache, c2->entries[n].id, c2->metadata + n * c2->metadata_size, c2->metadata_size);
467
                                new_cache->entries[pos].timestamp = c2->entries[n].timestamp;
468
                                new_cache->entries[pos].flags = c2->entries[n].flags;
469
                        }
470
                }
471
                if (pos < 0 && find_in_bl(new_cache, c2->entries[n].id) == new_cache->blist_size) {
472
                        if (new_cache->metadata_size) {
473
                                memcpy(meta, c2->metadata + n * c2->metadata_size, c2->metadata_size);
474
                                meta += new_cache->metadata_size;
475
                        }
476
                        new_cache->entries[new_cache->current_size++] = c2->entries[n];
477
                        c2->entries[n].id = NULL;
478
                }
479
        }
480
        *size = new_cache->current_size;
481

    
482
        return new_cache;
483
}
484

    
485
int blist_cache_resize (struct peer_cache *c, int size) {
486

    
487
        int i,dif = size - c->cache_size;
488
        if (!dif) {
489
                return c->current_size;
490
        }
491

    
492
        c->entries = realloc(c->entries, sizeof(struct cache_entry) * size);
493
        if (dif > 0) {
494
                memset(c->entries + c->cache_size, 0, sizeof(struct cache_entry) * dif);
495
        }
496
        else if (c->current_size > size) {
497
                c->current_size = size;
498
        }
499

    
500
        if (c->metadata_size) {
501
                c->metadata = realloc(c->metadata, c->metadata_size * size);
502
                if (dif > 0) {
503
                        memset(c->metadata + c->metadata_size * c->cache_size, 0, c->metadata_size * dif);
504
                }
505
        }
506

    
507
        if (dif < 0 && c->blist_size > size) {
508
                for (i = 0; i < -dif; i++) {
509
                        nodeid_free(c->blist[i]);
510
                }
511
                memmove(c->blist, c->blist - dif, sizeof(struct nodeID *) * size);
512
                c->blist = realloc(c->blist, sizeof(struct nodeID *) * size);
513
                c->blist_size = size;
514
        } else {
515
                c->blist = realloc(c->blist, sizeof(struct nodeID *) * size);
516
                if (dif > 0) {
517
                        memset(c->blist + c->cache_size, 0, sizeof(struct nodeID *) * dif);
518
                }
519
        }
520

    
521
        c->cache_size = size;
522

    
523
        return c->current_size;
524

    
525
}
526

    
527
// It MUST always be called with c1 = current local_cache to ensure black_list continuity
528
struct peer_cache *blist_merge_caches(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source)
529
{
530
  int n1, n2;
531
  struct peer_cache *new_cache;
532
  uint8_t *meta;
533

    
534
  new_cache = blist_cache_init(newsize, c1->metadata_size, c1->max_timestamp);
535
  if (new_cache == NULL) {
536
    return NULL;
537
  }
538

    
539
  n1 = newsize > c1->blist_size? 0 : c1->blist_size - newsize; // pick the most recent!
540
  while (n1 < c1->blist_size) {
541
        if (!nodeid_equal(c1->blist[n1], c2->entries[0].id)) { // sender should never be blacklisted
542
                new_cache->blist[new_cache->blist_size] = c1->blist[n1];
543
                c1->blist[n1] = NULL;
544
                new_cache->blist_size++;
545
        }
546
        n1++;
547
  }
548

    
549
  meta = new_cache->metadata;
550
  *source = 0;
551
  for (n1 = 0, n2 = 0; new_cache->current_size < new_cache->cache_size;) {
552
    if ((n1 == c1->current_size) && (n2 == c2->current_size)) {
553
                break;
554
    }
555
    if (n1 == c1->current_size) {
556
      if (in_cache(new_cache, &c2->entries[n2]) < 0 &&
557
                find_in_bl(new_cache, c2->entries[n2].id) == new_cache->blist_size) {
558
        if (new_cache->metadata_size) {
559
          memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
560
          meta += new_cache->metadata_size;
561
        }
562
        new_cache->entries[new_cache->current_size++] = c2->entries[n2];
563
        c2->entries[n2].id = NULL;
564
        *source |= 0x02;
565
      }
566
      n2++;
567
    } else if (n2 == c2->current_size) {
568
      if (in_cache(new_cache, &c1->entries[n1]) < 0) {
569
        if (new_cache->metadata_size) {
570
          memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
571
          meta += new_cache->metadata_size;
572
        }
573
        new_cache->entries[new_cache->current_size++] = c1->entries[n1];
574
        c1->entries[n1].id = NULL;
575
        *source |= 0x01;
576
      }
577
      n1++;
578
    } else {
579
      if (c2->entries[n2].timestamp > c1->entries[n1].timestamp) {
580
        if (in_cache(new_cache, &c1->entries[n1]) < 0) {
581
          if (new_cache->metadata_size) {
582
            memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size);
583
            meta += new_cache->metadata_size;
584
          }
585
          new_cache->entries[new_cache->current_size++] = c1->entries[n1];
586
          c1->entries[n1].id = NULL;
587
          *source |= 0x01;
588
        }
589
        n1++;
590
      } else {
591
        if (in_cache(new_cache, &c2->entries[n2]) < 0 &&
592
                find_in_bl(new_cache, c2->entries[n2].id) == new_cache->blist_size) {
593
          if (new_cache->metadata_size) {
594
            memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size);
595
            meta += new_cache->metadata_size;
596
          }
597
          new_cache->entries[new_cache->current_size++] = c2->entries[n2];
598
          c2->entries[n2].id = NULL;
599
          *source |= 0x02;
600
        }
601
        n2++;
602
      }
603
    }
604
  }
605

    
606
  return new_cache;
607
}