grapes / som / TopologyManager / topocache.c @ ac9b476d
History | View | Annotate | Download (8.77 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 "topocache.h" |
| 16 |
|
| 17 |
#define MAX_TIMESTAMP 5 |
| 18 |
struct cache_entry {
|
| 19 |
struct nodeID *id;
|
| 20 |
uint32_t timestamp; |
| 21 |
}; |
| 22 |
|
| 23 |
struct peer_cache {
|
| 24 |
struct cache_entry *entries;
|
| 25 |
int cache_size;
|
| 26 |
int current_size;
|
| 27 |
int metadata_size;
|
| 28 |
uint8_t *metadata; |
| 29 |
}; |
| 30 |
|
| 31 |
static inline void int_cpy(uint8_t *p, int v) |
| 32 |
{
|
| 33 |
int tmp;
|
| 34 |
|
| 35 |
tmp = htonl(v); |
| 36 |
memcpy(p, &tmp, 4);
|
| 37 |
} |
| 38 |
|
| 39 |
static inline int int_rcpy(const uint8_t *p) |
| 40 |
{
|
| 41 |
int tmp;
|
| 42 |
|
| 43 |
memcpy(&tmp, p, 4);
|
| 44 |
tmp = ntohl(tmp); |
| 45 |
|
| 46 |
return tmp;
|
| 47 |
} |
| 48 |
|
| 49 |
struct nodeID *nodeid(const struct peer_cache *c, int i) |
| 50 |
{
|
| 51 |
if (i < c->current_size) {
|
| 52 |
return c->entries[i].id;
|
| 53 |
} |
| 54 |
|
| 55 |
return NULL; |
| 56 |
} |
| 57 |
|
| 58 |
const void *get_metadata(const struct peer_cache *c, int *size) |
| 59 |
{
|
| 60 |
*size = c->metadata_size; |
| 61 |
return c->metadata;
|
| 62 |
} |
| 63 |
|
| 64 |
int cache_metadata_update(struct peer_cache *c, struct nodeID *p, const void *meta, int meta_size) |
| 65 |
{
|
| 66 |
int i;
|
| 67 |
|
| 68 |
if (!meta_size || meta_size != c->metadata_size) {
|
| 69 |
return -3; |
| 70 |
} |
| 71 |
for (i = 0; i < c->current_size; i++) { |
| 72 |
if (nodeid_equal(c->entries[i].id, p)) {
|
| 73 |
memcpy(c->metadata + i * meta_size, meta, meta_size); |
| 74 |
return 1; |
| 75 |
} |
| 76 |
} |
| 77 |
|
| 78 |
return 0; |
| 79 |
} |
| 80 |
|
| 81 |
int cache_add_ranked(struct peer_cache *c, const struct nodeID *neighbour, const void *meta, int meta_size, ranking_function f, const void *tmeta) |
| 82 |
{
|
| 83 |
int i, pos = 0; |
| 84 |
|
| 85 |
if (meta_size && meta_size != c->metadata_size) {
|
| 86 |
return -3; |
| 87 |
} |
| 88 |
for (i = 0; i < c->current_size; i++) { |
| 89 |
if (nodeid_equal(c->entries[i].id, neighbour)) {
|
| 90 |
return -1; |
| 91 |
} |
| 92 |
if ((f != NULL) && f(tmeta, meta, c->metadata+(c->metadata_size * i)) == 2) { |
| 93 |
pos++; |
| 94 |
} |
| 95 |
} |
| 96 |
if (c->current_size == c->cache_size) {
|
| 97 |
return -2; |
| 98 |
} |
| 99 |
if (meta_size) {
|
| 100 |
memmove(c->metadata + (pos + 1) * meta_size, c->metadata + pos * meta_size, (c->current_size - pos) * meta_size);
|
| 101 |
memcpy(c->metadata + pos * meta_size, meta, meta_size); |
| 102 |
} |
| 103 |
for (i = pos; i < c->current_size; i++) {
|
| 104 |
c->entries[i + 1] = c->entries[i];
|
| 105 |
} |
| 106 |
c->entries[pos].id = nodeid_dup(neighbour); |
| 107 |
c->entries[pos].timestamp = 1;
|
| 108 |
c->current_size++; |
| 109 |
|
| 110 |
return c->current_size;
|
| 111 |
} |
| 112 |
|
| 113 |
int cache_add(struct peer_cache *c, struct nodeID *neighbour, const void *meta, int meta_size) |
| 114 |
{
|
| 115 |
return cache_add_ranked(c, neighbour, meta, meta_size, NULL, NULL); |
| 116 |
} |
| 117 |
|
| 118 |
int cache_del(struct peer_cache *c, struct nodeID *neighbour) |
| 119 |
{
|
| 120 |
int i;
|
| 121 |
int found = 0; |
| 122 |
|
| 123 |
for (i = 0; i < c->current_size; i++) { |
| 124 |
if (nodeid_equal(c->entries[i].id, neighbour)) {
|
| 125 |
nodeid_free(c->entries[i].id); |
| 126 |
c->current_size--; |
| 127 |
found = 1;
|
| 128 |
if (c->metadata_size && (i < c->current_size)) {
|
| 129 |
memmove(c->metadata + c->metadata_size * i, |
| 130 |
c->metadata + c->metadata_size * (found + 1),
|
| 131 |
c->metadata_size * (c->current_size - i)); |
| 132 |
} |
| 133 |
} |
| 134 |
if (found && (i < c->current_size)) {
|
| 135 |
c->entries[i] = c->entries[i + 1];
|
| 136 |
} |
| 137 |
} |
| 138 |
|
| 139 |
return c->current_size;
|
| 140 |
} |
| 141 |
|
| 142 |
void cache_update_tout(struct peer_cache *c) |
| 143 |
{
|
| 144 |
int i;
|
| 145 |
|
| 146 |
for (i = 0; i < c->current_size; i++) { |
| 147 |
if (c->entries[i].timestamp == MAX_TIMESTAMP) {
|
| 148 |
c->current_size = i; /* The cache is ordered by timestamp...
|
| 149 |
all the other entries wiil be older than
|
| 150 |
this one, so remove all of them
|
| 151 |
*/
|
| 152 |
} else {
|
| 153 |
c->entries[i].timestamp++; |
| 154 |
} |
| 155 |
} |
| 156 |
} |
| 157 |
|
| 158 |
void cache_update(struct peer_cache *c) |
| 159 |
{
|
| 160 |
int i;
|
| 161 |
|
| 162 |
for (i = 0; i < c->current_size; i++) { |
| 163 |
c->entries[i].timestamp++; |
| 164 |
} |
| 165 |
} |
| 166 |
|
| 167 |
struct peer_cache *cache_init(int n, int metadata_size) |
| 168 |
{
|
| 169 |
struct peer_cache *res;
|
| 170 |
|
| 171 |
res = malloc(sizeof(struct peer_cache)); |
| 172 |
if (res == NULL) { |
| 173 |
return NULL; |
| 174 |
} |
| 175 |
res->cache_size = n; |
| 176 |
res->current_size = 0;
|
| 177 |
res->entries = malloc(sizeof(struct cache_entry) * n); |
| 178 |
if (res->entries == NULL) { |
| 179 |
free(res); |
| 180 |
|
| 181 |
return NULL; |
| 182 |
} |
| 183 |
|
| 184 |
memset(res->entries, 0, sizeof(struct cache_entry) * n); |
| 185 |
if (metadata_size) {
|
| 186 |
res->metadata = malloc(metadata_size * n); |
| 187 |
} else {
|
| 188 |
res->metadata = NULL;
|
| 189 |
} |
| 190 |
|
| 191 |
if (res->metadata) {
|
| 192 |
res->metadata_size = metadata_size; |
| 193 |
memset(res->metadata, 0, metadata_size * n);
|
| 194 |
} else {
|
| 195 |
res->metadata_size = 0;
|
| 196 |
} |
| 197 |
|
| 198 |
return res;
|
| 199 |
} |
| 200 |
|
| 201 |
void cache_free(struct peer_cache *c) |
| 202 |
{
|
| 203 |
int i;
|
| 204 |
|
| 205 |
for (i = 0; i < c->current_size; i++) { |
| 206 |
nodeid_free(c->entries[i].id); |
| 207 |
} |
| 208 |
free(c->entries); |
| 209 |
free(c->metadata); |
| 210 |
free(c); |
| 211 |
} |
| 212 |
|
| 213 |
static int in_cache(const struct peer_cache *c, const struct cache_entry *elem) |
| 214 |
{
|
| 215 |
int i;
|
| 216 |
|
| 217 |
for (i = 0; i < c->current_size; i++) { |
| 218 |
if (nodeid_equal(c->entries[i].id, elem->id)) {
|
| 219 |
return 1; |
| 220 |
} |
| 221 |
} |
| 222 |
|
| 223 |
return 0; |
| 224 |
} |
| 225 |
|
| 226 |
struct nodeID *rand_peer(struct peer_cache *c, uint8_t **meta) |
| 227 |
{
|
| 228 |
int j;
|
| 229 |
|
| 230 |
if (c->current_size == 0) { |
| 231 |
return NULL; |
| 232 |
} |
| 233 |
j = ((double)rand() / (double)RAND_MAX) * c->current_size; |
| 234 |
|
| 235 |
if (**meta) {
|
| 236 |
*meta = c->metadata + (j * c->metadata_size); |
| 237 |
} |
| 238 |
|
| 239 |
return c->entries[j].id;
|
| 240 |
} |
| 241 |
|
| 242 |
struct peer_cache *entries_undump(const uint8_t *buff, int size) |
| 243 |
{
|
| 244 |
struct peer_cache *res;
|
| 245 |
int i = 0; |
| 246 |
const uint8_t *p = buff;
|
| 247 |
uint8_t *meta; |
| 248 |
int cache_size, metadata_size;
|
| 249 |
|
| 250 |
cache_size = int_rcpy(buff); |
| 251 |
metadata_size = int_rcpy(buff + 4);
|
| 252 |
p = buff + 8;
|
| 253 |
res = cache_init(cache_size, metadata_size); |
| 254 |
meta = res->metadata; |
| 255 |
while (p - buff < size) {
|
| 256 |
int len;
|
| 257 |
|
| 258 |
res->entries[i].timestamp = int_rcpy(p); |
| 259 |
p += sizeof(uint32_t);
|
| 260 |
res->entries[i++].id = nodeid_undump(p, &len); |
| 261 |
p += len; |
| 262 |
if (metadata_size) {
|
| 263 |
memcpy(meta, p, metadata_size); |
| 264 |
p += metadata_size; |
| 265 |
meta += metadata_size; |
| 266 |
} |
| 267 |
} |
| 268 |
res->current_size = i; |
| 269 |
if (p - buff != size) { fprintf(stderr, "Waz!! %d != %d\n", p - buff, size); exit(-1);} |
| 270 |
|
| 271 |
return res;
|
| 272 |
} |
| 273 |
|
| 274 |
int cache_header_dump(uint8_t *b, const struct peer_cache *c) |
| 275 |
{
|
| 276 |
int_cpy(b, c->cache_size); |
| 277 |
int_cpy(b + 4, c->metadata_size);
|
| 278 |
|
| 279 |
return 8; |
| 280 |
} |
| 281 |
|
| 282 |
int entry_dump(uint8_t *b, struct peer_cache *c, int i) |
| 283 |
{
|
| 284 |
int res;
|
| 285 |
|
| 286 |
int_cpy(b, c->entries[i].timestamp); |
| 287 |
res = 4;
|
| 288 |
res += nodeid_dump(b + res, c->entries[i].id); |
| 289 |
if (c->metadata_size) {
|
| 290 |
memcpy(b + res, c->metadata + c->metadata_size * i, c->metadata_size); |
| 291 |
res += c->metadata_size; |
| 292 |
} |
| 293 |
|
| 294 |
return res;
|
| 295 |
} |
| 296 |
|
| 297 |
struct peer_cache *merge_caches_ranked(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source, ranking_function rank, void *mymetadata) |
| 298 |
{
|
| 299 |
int n1, n2;
|
| 300 |
struct peer_cache *new_cache;
|
| 301 |
uint8_t *meta; |
| 302 |
|
| 303 |
new_cache = cache_init(newsize, c1->metadata_size); |
| 304 |
if (new_cache == NULL) { |
| 305 |
return NULL; |
| 306 |
} |
| 307 |
|
| 308 |
meta = new_cache->metadata; |
| 309 |
*source = 0;
|
| 310 |
for (n1 = 0, n2 = 0; new_cache->current_size < new_cache->cache_size;) { |
| 311 |
if ((n1 == c1->current_size) && (n2 == c2->current_size)) {
|
| 312 |
return new_cache;
|
| 313 |
} |
| 314 |
if (n1 == c1->current_size) {
|
| 315 |
if (!in_cache(new_cache, &c2->entries[n2])) {
|
| 316 |
if (new_cache->metadata_size) {
|
| 317 |
memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size); |
| 318 |
meta += new_cache->metadata_size; |
| 319 |
} |
| 320 |
new_cache->entries[new_cache->current_size++] = c2->entries[n2]; |
| 321 |
c2->entries[n2].id = NULL;
|
| 322 |
*source |= 0x02;
|
| 323 |
} |
| 324 |
n2++; |
| 325 |
} else if (n2 == c2->current_size) { |
| 326 |
if (!in_cache(new_cache, &c1->entries[n1])) {
|
| 327 |
if (new_cache->metadata_size) {
|
| 328 |
memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size); |
| 329 |
meta += new_cache->metadata_size; |
| 330 |
} |
| 331 |
new_cache->entries[new_cache->current_size++] = c1->entries[n1]; |
| 332 |
c1->entries[n1].id = NULL;
|
| 333 |
*source |= 0x01;
|
| 334 |
} |
| 335 |
n1++; |
| 336 |
} else {
|
| 337 |
int nowFirst;
|
| 338 |
|
| 339 |
nowFirst = 0;
|
| 340 |
if (rank) {
|
| 341 |
nowFirst = rank(mymetadata, c1->metadata + n1 * c1->metadata_size, |
| 342 |
c2->metadata + n2 * c2->metadata_size); |
| 343 |
} |
| 344 |
if (nowFirst == 0) { |
| 345 |
nowFirst = c2->entries[n2].timestamp > c1->entries[n1].timestamp ? 1 : 2; |
| 346 |
} |
| 347 |
if (nowFirst == 1) { |
| 348 |
if (!in_cache(new_cache, &c1->entries[n1])) {
|
| 349 |
if (new_cache->metadata_size) {
|
| 350 |
memcpy(meta, c1->metadata + n1 * c1->metadata_size, c1->metadata_size); |
| 351 |
meta += new_cache->metadata_size; |
| 352 |
} |
| 353 |
new_cache->entries[new_cache->current_size++] = c1->entries[n1]; |
| 354 |
c1->entries[n1].id = NULL;
|
| 355 |
*source |= 0x01;
|
| 356 |
} |
| 357 |
n1++; |
| 358 |
} else {
|
| 359 |
if (!in_cache(new_cache, &c2->entries[n2])) {
|
| 360 |
if (new_cache->metadata_size) {
|
| 361 |
memcpy(meta, c2->metadata + n2 * c2->metadata_size, c2->metadata_size); |
| 362 |
meta += new_cache->metadata_size; |
| 363 |
} |
| 364 |
new_cache->entries[new_cache->current_size++] = c2->entries[n2]; |
| 365 |
c2->entries[n2].id = NULL;
|
| 366 |
*source |= 0x02;
|
| 367 |
} |
| 368 |
n2++; |
| 369 |
} |
| 370 |
} |
| 371 |
} |
| 372 |
|
| 373 |
return new_cache;
|
| 374 |
} |
| 375 |
|
| 376 |
struct peer_cache *merge_caches(struct peer_cache *c1, struct peer_cache *c2, int newsize, int *source) |
| 377 |
{
|
| 378 |
return merge_caches_ranked(c1, c2, newsize, source, NULL, NULL); |
| 379 |
} |