Statistics
| Branch: | Revision:

grapes / src / TopologyManager / blist_cache.c @ 5033613a

History | View | Annotate | Download (15.6 KB)

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

    
7
#include <stdint.h>
8
#include <stdlib.h>
9
#include <string.h>
10

    
11
#include <stdio.h>
12

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

    
17
#define NOREPLY_FLAG_UNSET 254
18
#define NOREPLY_FLAG_SET 1
19

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

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

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

    
43
  return NULL;
44
}
45

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

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

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

    
66
  return 0;
67
}
68

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

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

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

    
100
  return c->current_size;
101
}
102

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

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

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

    
158
  return c->current_size;
159
}
160

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

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

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

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

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

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

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

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

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

    
232
  return res;
233
}
234

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

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

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

    
252
  free(c);
253
}
254

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

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

    
265
  return -1;
266
}
267

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

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

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

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

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

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

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

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

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

    
345
  return res;
346
}
347

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

    
353
  return 8;
354
}
355

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

    
382
  return size;
383
}
384

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

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

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

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

    
423
        return res;
424
}
425

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

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

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

    
441
        meta = new_cache->metadata;
442

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

    
452

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

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

    
481
        return new_cache;
482
}
483

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

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

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

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

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

    
520
        c->cache_size = size;
521

    
522
        return c->current_size;
523

    
524
}
525

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

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

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

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

    
605
  return new_cache;
606
}