Statistics
| Branch: | Revision:

streamers / streaming.c @ 70921454

History | View | Annotate | Download (16.3 KB)

1
/*
2
 *  Copyright (c) 2010 Luca Abeni
3
 *  Copyright (c) 2010 Csaba Kiraly
4
 *
5
 *  This is free software; see gpl-3.0.txt
6
 */
7
#include <sys/time.h>
8
#include <stdlib.h>
9
#include <stdio.h>
10
#include <stdint.h>
11
#include <stdbool.h>
12
#include <math.h>
13
#include <assert.h>
14
#include <string.h>
15
#include <inttypes.h>
16

    
17
#include <net_helper.h>
18
#include <chunk.h> 
19
#include <chunkbuffer.h> 
20
#include <trade_msg_la.h>
21
#include <trade_msg_ha.h>
22
#include <peerset.h>
23
#include <peer.h>
24
#include <chunkidset.h>
25
#include <limits.h>
26
#include <trade_sig_ha.h>
27

    
28
#include "streaming.h"
29
#include "output.h"
30
#include "input.h"
31
#include "dbg.h"
32
#include "chunk_signaling.h"
33
#include "chunklock.h"
34
#include "topology.h"
35
#include "measures.h"
36
#include "scheduling.h"
37

    
38
#include "scheduler_la.h"
39

    
40
static bool heuristics_distance_maxdeliver = false;
41
static int bcast_after_receive_every = 0;
42
static bool neigh_on_chunk_recv = false;
43

    
44
struct chunk_attributes {
45
  uint64_t deadline;
46
  uint16_t deadline_increment;
47
  uint16_t hopcount;
48
} __attribute__((packed));
49

    
50
extern bool chunk_log;
51

    
52
struct chunk_buffer *cb;
53
static struct input_desc *input;
54
static int cb_size;
55
static int transid=0;
56

    
57
static int offer_per_tick = 1;        //N_p parameter of POLITO
58

    
59
int _needs(struct chunkID_set *cset, int cb_size, int cid);
60

    
61
uint64_t gettimeofday_in_us(void)
62
{
63
  struct timeval what_time; //to store the epoch time
64

    
65
  gettimeofday(&what_time, NULL);
66
  return what_time.tv_sec * 1000000ULL + what_time.tv_usec;
67
}
68

    
69
void cb_print()
70
{
71
#ifdef DEBUG
72
  struct chunk *chunks;
73
  int num_chunks, i, id;
74
  chunks = cb_get_chunks(cb, &num_chunks);
75

    
76
  dprintf("\tchbuf :");
77
  i = 0;
78
  if(num_chunks) {
79
    id = chunks[0].id;
80
    dprintf(" %d-> ",id);
81
    while (i < num_chunks) {
82
      if (id == chunks[i].id) {
83
        dprintf("%d",id % 10);
84
        i++;
85
      } else if (chunk_islocked(id)) {
86
        dprintf("*");
87
      } else {
88
        dprintf(".");
89
      }
90
      id++;
91
    }
92
  }
93
  dprintf("\n");
94
#endif
95
}
96

    
97
void stream_init(int size, struct nodeID *myID)
98
{
99
  static char conf[32];
100

    
101
  cb_size = size;
102

    
103
  sprintf(conf, "size=%d", cb_size);
104
  cb = cb_init(conf);
105
  chunkDeliveryInit(myID);
106
  chunkSignalingInit(myID);
107
  init_measures();
108
}
109

    
110
int source_init(const char *fname, struct nodeID *myID, bool loop, int *fds, int fds_size)
111
{
112
  int flags = 0;
113

    
114
  if (memcmp(fname, "udp:", 4) == 0) {
115
    fname += 4;
116
    flags = INPUT_UDP;
117
  }
118
  if (loop) {
119
    flags |= INPUT_LOOP;
120
  }
121

    
122
  source = true;
123

    
124
  input = input_open(fname, flags, fds, fds_size);
125
  if (input == NULL) {
126
    return -1;
127
  }
128

    
129
  stream_init(1, myID);
130
  return 0;
131
}
132

    
133
void chunk_attributes_fill(struct chunk* c)
134
{
135
  struct chunk_attributes * ca;
136

    
137
  assert(!c->attributes && c->attributes_size == 0);
138

    
139
  c->attributes_size = sizeof(struct chunk_attributes);
140
  c->attributes = ca = malloc(c->attributes_size);
141

    
142
  ca->deadline = c->timestamp;
143
  ca->deadline_increment = 2;
144
  ca->hopcount = 0;
145
}
146

    
147
int chunk_get_hopcount(struct chunk* c) {
148
  struct chunk_attributes * ca;
149

    
150
  if (!c->attributes || c->attributes_size != sizeof(struct chunk_attributes)) {
151
    fprintf(stderr,"Warning, chunk %d with strange attributes block. Size:%d expected:%lu\n", c->id, c->attributes ? c->attributes_size : 0, sizeof(struct chunk_attributes));
152
    return -1;
153
  }
154

    
155
  ca = (struct chunk_attributes *) c->attributes;
156
  return ca->hopcount;
157
}
158

    
159
void chunk_attributes_update_received(struct chunk* c)
160
{
161
  struct chunk_attributes * ca;
162

    
163
  if (!c->attributes || c->attributes_size != sizeof(struct chunk_attributes)) {
164
    fprintf(stderr,"Warning, received chunk %d with strange attributes block. Size:%d expected:%lu\n", c->id, c->attributes ? c->attributes_size : 0, sizeof(struct chunk_attributes));
165
    return;
166
  }
167

    
168
  ca = (struct chunk_attributes *) c->attributes;
169
  ca->hopcount++;
170
  dprintf("Received chunk %d with hopcount %hu\n", c->id, ca->hopcount);
171
}
172

    
173
void chunk_attributes_update_sending(const struct chunk* c)
174
{
175
  struct chunk_attributes * ca;
176

    
177
  if (!c->attributes || c->attributes_size != sizeof(struct chunk_attributes)) {
178
    fprintf(stderr,"Warning, chunk %d with strange attributes block\n", c->id);
179
    return;
180
  }
181

    
182
  ca = (struct chunk_attributes *) c->attributes;
183
  ca->deadline += ca->deadline_increment;
184
  dprintf("Sending chunk %d with deadline %lu\n", c->id, ca->deadline);
185
}
186

    
187
struct chunkID_set *cb_to_bmap(struct chunk_buffer *chbuf)
188
{
189
  struct chunk *chunks;
190
  int num_chunks, i;
191
  struct chunkID_set *my_bmap = chunkID_set_init("type=bitmap");
192
  chunks = cb_get_chunks(chbuf, &num_chunks);
193

    
194
  for(i=num_chunks-1; i>=0; i--) {
195
    chunkID_set_add_chunk(my_bmap, chunks[i].id);
196
  }
197
  return my_bmap;
198
}
199

    
200
// a simple implementation that request everything that we miss ... up to max deliver
201
struct chunkID_set *get_chunks_to_accept(struct nodeID *fromid, const struct chunkID_set *cset_off, int max_deliver, uint16_t trans_id){
202
  struct chunkID_set *cset_acc, *my_bmap;
203
  int i, d, cset_off_size;
204
  //double lossrate;
205
  struct peer *from = nodeid_to_peer(fromid, 0);
206

    
207
  cset_acc = chunkID_set_init("size=0");
208

    
209
  //reduce load a little bit if there are losses on the path from this guy
210
  //lossrate = get_lossrate_receive(from->id);
211
  //lossrate = finite(lossrate) ? lossrate : 0;        //start agressively, assuming 0 loss
212
  //if (rand()/((double)RAND_MAX + 1) >= 10 * lossrate ) {
213
    my_bmap = cb_to_bmap(cb);
214
    cset_off_size = chunkID_set_size(cset_off);
215
    for (i = 0, d = 0; i < cset_off_size && d < max_deliver; i++) {
216
      int chunkid = chunkID_set_get_chunk(cset_off, i);
217
      //dprintf("\tdo I need c%d ? :",chunkid);
218
      if (!chunk_islocked(chunkid) && _needs(my_bmap, cb_size, chunkid)) {
219
        chunkID_set_add_chunk(cset_acc, chunkid);
220
        chunk_lock(chunkid,from);
221
        dtprintf("accepting %d from %s", chunkid, node_addr(fromid));
222
#ifdef MONL
223
        dprintf(", loss:%f rtt:%f", get_lossrate(fromid), get_rtt(fromid));
224
#endif
225
        dprintf("\n");
226
        d++;
227
      }
228
    }
229
    chunkID_set_free(my_bmap);
230
  //} else {
231
  //    dtprintf("accepting -- from %s loss:%f rtt:%f\n", node_addr(fromid), lossrate, get_rtt(fromid));
232
  //}
233

    
234
  return cset_acc;
235
}
236

    
237
void send_bmap(struct nodeID *toid)
238
{
239
  struct chunkID_set *my_bmap = cb_to_bmap(cb);
240
   sendBufferMap(toid,NULL, my_bmap, input ? 0 : cb_size, 0);
241
  chunkID_set_free(my_bmap);
242
}
243

    
244
void bcast_bmap()
245
{
246
  int i, n;
247
  struct peer *neighbours;
248
  struct peerset *pset;
249
  struct chunkID_set *my_bmap;
250

    
251
  pset = get_peers();
252
  n = peerset_size(pset);
253
  neighbours = peerset_get_peers(pset);
254

    
255
  my_bmap = cb_to_bmap(cb);        //cache our bmap for faster processing
256
  for (i = 0; i<n; i++) {
257
    sendBufferMap(neighbours[i].id,NULL, my_bmap, input ? 0 : cb_size, 0);
258
  }
259
  chunkID_set_free(my_bmap);
260
}
261

    
262
double get_average_lossrate_pset(struct peerset *pset)
263
{
264
  int i, n;
265
  struct peer *neighbours;
266

    
267
  n = peerset_size(pset);
268
  neighbours = peerset_get_peers(pset);
269
  {
270
    struct nodeID *nodeids[n];
271
    for (i = 0; i<n; i++) nodeids[i] = neighbours[i].id;
272
#ifdef MONL
273
    return get_average_lossrate(nodeids, n);
274
#else
275
    return 0;
276
#endif
277
  }
278
}
279

    
280
void ack_chunk(struct chunk *c, struct nodeID *from)
281
{
282
  //reduce load a little bit if there are losses on the path from this guy
283
  double average_lossrate = get_average_lossrate_pset(get_peers());
284
  average_lossrate = finite(average_lossrate) ? average_lossrate : 0;        //start agressively, assuming 0 loss
285
  if (rand()/((double)RAND_MAX + 1) < 1 * average_lossrate ) {
286
    return;
287
  }
288
  send_bmap(from);        //send explicit ack
289
}
290

    
291
void received_chunk(struct nodeID *from, const uint8_t *buff, int len)
292
{
293
  int res;
294
  static struct chunk c;
295
  struct peer *p;
296
  static int bcast_cnt;
297
  uint16_t transid;
298

    
299
  res = parseChunkMsg(buff + 1, len - 1, &c, &transid);
300
  if (res > 0) {
301
    chunk_attributes_update_received(&c);
302
    chunk_unlock(c.id);
303
    dprintf("Received chunk %d from peer: %s\n", c.id, node_addr(from));
304
    if(chunk_log){fprintf(stderr, "TEO: Received chunk %d from peer: %s at: %"PRIu64" hopcount: %i\n", c.id, node_addr(from), gettimeofday_in_us(), chunk_get_hopcount(&c));}
305
    output_deliver(&c);
306
    res = cb_add_chunk(cb, &c);
307
    reg_chunk_receive(c.id, c.timestamp, chunk_get_hopcount(&c), res==E_CB_OLD, res==E_CB_DUPLICATE);
308
    cb_print();
309
    if (res < 0) {
310
      dprintf("\tchunk too old, buffer full with newer chunks\n");
311
      if(chunk_log){fprintf(stderr, "TEO: Received chunk: %d too old (buffer full with newer chunks) from peer: %s at: %"PRIu64"\n", c.id, node_addr(from), gettimeofday_in_us());}
312
      free(c.data);
313
      free(c.attributes);
314
    }
315
    p = nodeid_to_peer(from, neigh_on_chunk_recv);
316
    if (p) {        //now we have it almost sure
317
      chunkID_set_add_chunk(p->bmap,c.id);        //don't send it back
318
    }
319
    ack_chunk(&c,from);        //send explicit ack
320
    if (bcast_after_receive_every && bcast_cnt % bcast_after_receive_every == 0) {
321
       bcast_bmap();
322
    }
323
  } else {
324
    fprintf(stderr,"\tError: can't decode chunk!\n");
325
  }
326
}
327

    
328
struct chunk *generated_chunk(suseconds_t *delta)
329
{
330
  struct chunk *c;
331

    
332
  c = malloc(sizeof(struct chunk));
333
  if (!c) {
334
    fprintf(stderr, "Memory allocation error!\n");
335
    return NULL;
336
  }
337

    
338
  *delta = input_get(input, c);
339
  if (*delta < 0) {
340
    fprintf(stderr, "Error in input!\n");
341
    exit(-1);
342
  }
343
  if (c->data == NULL) {
344
    free(c);
345
    return NULL;
346
  }
347
  dprintf("Generated chunk %d of %d bytes\n",c->id, c->size);
348
  chunk_attributes_fill(c);
349
  return c;
350
}
351

    
352
int add_chunk(struct chunk *c)
353
{
354
  int res;
355

    
356
  res = cb_add_chunk(cb, c);
357
  if (res < 0) {
358
    free(c->data);
359
    free(c->attributes);
360
    free(c);
361
    return 0;
362
  }
363
  free(c);
364
  return 1;
365
}
366

    
367
/**
368
 *example function to filter chunks based on whether a given peer needs them.
369
 *
370
 * Looks at buffermap information received about the given peer.
371
 */
372
int needs(struct peer *n, int cid){
373
  struct peer * p = n;
374

    
375
  //dprintf("\t%s needs c%d ? :",node_addr(p->id),c->id);
376
  if (! p->bmap) {
377
    //dprintf("no bmap\n");
378
    return 1;        // if we have no bmap information, we assume it needs the chunk (aggressive behaviour!)
379
  }
380
  return _needs(p->bmap, p->cb_size, cid);
381
}
382

    
383
int _needs(struct chunkID_set *cset, int cb_size, int cid){
384
  if (cb_size == 0) { //if it declared it does not needs chunks
385
    return 0;
386
  }
387

    
388
  if (chunkID_set_check(cset,cid) < 0) { //it might need the chunk
389
    int missing, min;
390
    //@TODO: add some bmap_timestamp based logic
391

    
392
    if (chunkID_set_size(cset) == 0) {
393
      //dprintf("bmap empty\n");
394
      return 1;        // if the bmap seems empty, it needs the chunk
395
    }
396
    missing = cb_size - chunkID_set_size(cset);
397
    missing = missing < 0 ? 0 : missing;
398
    min = chunkID_set_get_earliest(cset);
399
      //dprintf("%s ... cid(%d) >= min(%d) - missing(%d) ?\n",(cid >= min - missing)?"YES":"NO",cid, min, missing);
400
    return (cid >= min - missing);
401
  }
402

    
403
  //dprintf("has it\n");
404
  return 0;
405
}
406

    
407
double peerWeightReceivedfrom(struct peer **n){
408
  struct peer * p = *n;
409
  return timerisset(&p->bmap_timestamp) ? 1 : 0.1;
410
}
411

    
412
double peerWeightUniform(struct peer **n){
413
  return 1;
414
}
415

    
416
double peerWeightRtt(struct peer **n){
417
#ifdef MONL
418
  double rtt = get_rtt(*n->id);
419
  //dprintf("RTT to %s: %f\n", node_addr(p->id), rtt);
420
  return finite(rtt) ? 1 / (rtt + 0.005) : 1 / 1;
421
#else
422
  return 1;
423
#endif
424
}
425

    
426
//ordering function for ELp peer selection, chunk ID based
427
//can't be used as weight
428
double peerScoreELpID(struct nodeID **n){
429
  struct chunkID_set *bmap;
430
  int latest;
431
  struct peer * p = nodeid_to_peer(*n, 0);
432
  if (!p) return 0;
433

    
434
  bmap = p->bmap;
435
  if (!bmap) return 0;
436
  latest = chunkID_set_get_latest(bmap);
437
  if (latest == INT_MIN) return 0;
438

    
439
  return -latest;
440
}
441

    
442
double chunkScoreChunkID(int *cid){
443
  return (double) *cid;
444
}
445

    
446
double getChunkTimestamp(int *cid){
447
  const struct chunk *c = cb_get_chunk(cb, *cid);
448
  if (!c) return 0;
449

    
450
  return (double) c->timestamp;
451
}
452

    
453
void send_accepted_chunks(struct nodeID *toid, struct chunkID_set *cset_acc, int max_deliver, uint16_t trans_id){
454
  int i, d, cset_acc_size, res;
455
  struct peer *to = nodeid_to_peer(toid, 0);
456

    
457
  cset_acc_size = chunkID_set_size(cset_acc);
458
  reg_offer_accept(cset_acc_size > 0 ? 1 : 0);        //this only works if accepts are sent back even if 0 is accepted
459
  for (i = 0, d=0; i < cset_acc_size && d < max_deliver; i++) {
460
    const struct chunk *c;
461
    int chunkid = chunkID_set_get_chunk(cset_acc, i);
462
    c = cb_get_chunk(cb, chunkid);
463
    if (c && (!to || needs(to, chunkid)) ) {// we should have the chunk, and he should not have it. Although the "accept" should have been an answer to our "offer", we do some verification
464
      chunk_attributes_update_sending(c);
465
      res = sendChunk(toid, c, trans_id);
466
      if (res >= 0) {
467
        if(to) chunkID_set_add_chunk(to->bmap, c->id); //don't send twice ... assuming that it will actually arrive
468
        d++;
469
        reg_chunk_send(c->id);
470
        if(chunk_log){fprintf(stderr, "TEO: Sending chunk %d to peer: %s at: %"PRIu64" Result: %d\n", c->id, node_addr(toid), gettimeofday_in_us(), res);}
471
      } else {
472
        fprintf(stderr,"ERROR sending chunk %d\n",c->id);
473
      }
474
    }
475
  }
476
}
477

    
478
int offer_peer_count()
479
{
480
  return offer_per_tick;
481
}
482

    
483
int offer_max_deliver(struct nodeID *n)
484
{
485

    
486
  if (!heuristics_distance_maxdeliver) return 1;
487

    
488
#ifdef MONL
489
  switch (get_hopcount(n)) {
490
    case 0: return 5;
491
    case 1: return 2;
492
    default: return 1;
493
  }
494
#else
495
  return 1;
496
#endif
497
}
498

    
499
void send_offer()
500
{
501
  struct chunk *buff;
502
  int size, res, i, n;
503
  struct peer *neighbours;
504
  struct peerset *pset;
505

    
506
  pset = get_peers();
507
  n = peerset_size(pset);
508
  neighbours = peerset_get_peers(pset);
509
  dprintf("Send Offer: %d neighbours\n", n);
510
  if (n == 0) return;
511
  buff = cb_get_chunks(cb, &size);
512
  if (size == 0) return;
513

    
514
  {
515
    size_t selectedpeers_len = offer_peer_count();
516
    int chunkids[size];
517
    struct peer *nodeids[n];
518
    struct peer *selectedpeers[selectedpeers_len];
519

    
520
    //reduce load a little bit if there are losses on the path from this guy
521
    double average_lossrate = get_average_lossrate_pset(pset);
522
    average_lossrate = finite(average_lossrate) ? average_lossrate : 0;        //start agressively, assuming 0 loss
523
    if (rand()/((double)RAND_MAX + 1) < 10 * average_lossrate ) {
524
      return;
525
    }
526

    
527
    for (i = 0;i < size; i++) chunkids[size - 1 - i] = (buff+i)->id;
528
    for (i = 0; i<n; i++) nodeids[i] = (neighbours+i);
529
    selectPeersForChunks(SCHED_WEIGHTING, nodeids, n, chunkids, size, selectedpeers, &selectedpeers_len, SCHED_NEEDS, SCHED_PEER);
530

    
531
    for (i=0; i<selectedpeers_len ; i++){
532
      int max_deliver = offer_max_deliver(selectedpeers[i]->id);
533
      struct chunkID_set *my_bmap = cb_to_bmap(cb);
534
      dprintf("\t sending offer(%d) to %s, cb_size: %d\n", transid, node_addr(selectedpeers[i]->id), selectedpeers[i]->cb_size);
535
      res = offerChunks(selectedpeers[i]->id, my_bmap, max_deliver, transid++);
536
      chunkID_set_free(my_bmap);
537
    }
538
  }
539
}
540

    
541

    
542
void send_chunk()
543
{
544
  struct chunk *buff;
545
  int size, res, i, n;
546
  struct peer *neighbours;
547
  struct peerset *pset;
548

    
549
  pset = get_peers();
550
  n = peerset_size(pset);
551
  neighbours = peerset_get_peers(pset);
552
  dprintf("Send Chunk: %d neighbours\n", n);
553
  if (n == 0) return;
554
  buff = cb_get_chunks(cb, &size);
555
  dprintf("\t %d chunks in buffer...\n", size);
556
  if (size == 0) return;
557

    
558
  /************ STUPID DUMB SCHEDULING ****************/
559
  //target = n * (rand() / (RAND_MAX + 1.0)); /*0..n-1*/
560
  //c = size * (rand() / (RAND_MAX + 1.0)); /*0..size-1*/
561
  /************ /STUPID DUMB SCHEDULING ****************/
562

    
563
  /************ USE SCHEDULER ****************/
564
  {
565
    size_t selectedpairs_len = 1;
566
    int chunkids[size];
567
    struct peer *nodeids[n];
568
    struct PeerChunk selectedpairs[1];
569
  
570
    for (i = 0;i < size; i++) chunkids[i] = (buff+i)->id;
571
    for (i = 0; i<n; i++) nodeids[i] = (neighbours+i);
572
    SCHED_TYPE(SCHED_WEIGHTING, nodeids, n, chunkids, size, selectedpairs, &selectedpairs_len, SCHED_NEEDS, SCHED_PEER, SCHED_CHUNK);
573
  /************ /USE SCHEDULER ****************/
574

    
575
    for (i=0; i<selectedpairs_len ; i++){
576
      struct peer *p = selectedpairs[i].peer;
577
      struct chunk *c = cb_get_chunk(cb, selectedpairs[i].chunk);
578
      dprintf("\t sending chunk[%d] to ", c->id);
579
      dprintf("%s\n", node_addr(p->id));
580

    
581
      send_bmap(p->id);
582

    
583
      chunk_attributes_update_sending(c);
584
      res = sendChunk(p->id, c, 0);        //we do not use transactions in pure push
585
      if(chunk_log){fprintf(stderr, "TEO: Sending chunk %d to peer: %s at: %"PRIu64" Result: %d Size: %d bytes\n", c->id, node_addr(p->id), gettimeofday_in_us(), res, c->size);}
586
      dprintf("\tResult: %d\n", res);
587
      if (res>=0) {
588
        chunkID_set_add_chunk(p->bmap,c->id); //don't send twice ... assuming that it will actually arrive
589
        reg_chunk_send(c->id);
590
      } else {
591
        fprintf(stderr,"ERROR sending chunk %d\n",c->id);
592
      }
593
    }
594
  }
595
}