GNUnet  0.19.2
fragmentation.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2009-2013 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
25 #include "platform.h"
26 #include "gnunet_protocols.h"
27 #include "fragmentation.h"
28 
29 
33 #define MIN_ACK_DELAY GNUNET_TIME_relative_multiply ( \
34  GNUNET_TIME_UNIT_MILLISECONDS, 1)
35 
36 
41 {
46 
51 
56 
61 
66 
71 
75  const struct GNUNET_MessageHeader *msg;
76 
81 
85  void *proc_cls;
86 
90  uint64_t acks;
91 
96  uint64_t acks_mask;
97 
102 
106  uint32_t fragment_id;
107 
111  unsigned int next_transmission;
112 
116  unsigned int num_rounds;
117 
121  unsigned int num_transmissions;
122 
126  int8_t proc_busy;
127 
131  int8_t wack;
132 
136  uint16_t mtu;
137 };
138 
139 
146 const char *
148 {
149  static char buf[128];
150  const struct FragmentAcknowledgement *fa;
151 
152  if (sizeof(struct FragmentAcknowledgement) !=
153  htons (ack->size))
154  return "<malformed ack>";
155  fa = (const struct FragmentAcknowledgement *) ack;
157  sizeof(buf),
158  "%u-%llX",
159  ntohl (fa->fragment_id),
160  (unsigned long long) GNUNET_ntohll (fa->bits));
161  return buf;
162 }
163 
164 
170 static void
171 transmit_next (void *cls)
172 {
173  struct GNUNET_FRAGMENT_Context *fc = cls;
174  char msg[fc->mtu];
175  const char *mbuf;
176  struct FragmentHeader *fh;
178  unsigned int bit;
179  size_t size;
180  size_t fsize;
181  int wrap;
182 
183  fc->task = NULL;
185  if (0 == fc->acks)
186  return; /* all done */
187  /* calculate delay */
188  wrap = 0;
189  while (0 == (fc->acks & (1LLU << fc->next_transmission)))
190  {
191  fc->next_transmission = (fc->next_transmission + 1) % 64;
192  wrap |= (0 == fc->next_transmission);
193  }
194  bit = fc->next_transmission;
195  size = ntohs (fc->msg->size);
196  if (bit == size / (fc->mtu - sizeof(struct FragmentHeader)))
197  fsize =
198  (size % (fc->mtu - sizeof(struct FragmentHeader)))
199  + sizeof(struct FragmentHeader);
200  else
201  fsize = fc->mtu;
202  if (NULL != fc->tracker)
204  fsize);
205  else
207  if (delay.rel_value_us > 0)
208  {
210  "Fragmentation logic delays transmission of next fragment by %s\n",
212  GNUNET_YES));
214  &transmit_next,
215  fc);
216  return;
217  }
218  fc->next_transmission = (fc->next_transmission + 1) % 64;
219  wrap |= (0 == fc->next_transmission);
220  while (0 == (fc->acks & (1LLU << fc->next_transmission)))
221  {
222  fc->next_transmission = (fc->next_transmission + 1) % 64;
223  wrap |= (0 == fc->next_transmission);
224  }
225 
226  /* assemble fragmentation message */
227  mbuf = (const char *) &fc[1];
228  fh = (struct FragmentHeader *) msg;
229  fh->header.size = htons (fsize);
230  fh->header.type = htons (GNUNET_MESSAGE_TYPE_FRAGMENT);
231  fh->fragment_id = htonl (fc->fragment_id);
232  fh->total_size = fc->msg->size; /* already in big-endian */
233  fh->offset = htons ((fc->mtu - sizeof(struct FragmentHeader)) * bit);
234  GNUNET_memcpy (&fh[1], &mbuf[bit * (fc->mtu - sizeof(struct FragmentHeader))],
235  fsize - sizeof(struct FragmentHeader));
236  if (NULL != fc->tracker)
239  _ ("# fragments transmitted"),
240  1,
241  GNUNET_NO);
242  if (0 != fc->last_round.abs_value_us)
244  _ ("# fragments retransmitted"),
245  1,
246  GNUNET_NO);
247 
248  /* select next message to calculate delay */
249  bit = fc->next_transmission;
250  size = ntohs (fc->msg->size);
251  if (bit == size / (fc->mtu - sizeof(struct FragmentHeader)))
252  fsize = size % (fc->mtu - sizeof(struct FragmentHeader));
253  else
254  fsize = fc->mtu;
255  if (NULL != fc->tracker)
257  fsize);
258  else
260  if (fc->num_rounds < 64)
263  (fc->msg_delay,
264  (1ULL << fc->num_rounds)));
265  else
267  if (wrap)
268  {
269  /* full round transmitted wait 2x delay for ACK before going again */
270  fc->num_rounds++;
272  /* never use zero, need some time for ACK always */
274  fc->wack = GNUNET_YES;
277  _ ("# fragments wrap arounds"),
278  1,
279  GNUNET_NO);
280  }
281  fc->proc_busy = GNUNET_YES;
283  fc->num_transmissions++;
284  fc->proc (fc->proc_cls,
285  &fh->header);
286 }
287 
288 
311  uint16_t mtu,
315  const struct GNUNET_MessageHeader *msg,
317  void *proc_cls)
318 {
319  struct GNUNET_FRAGMENT_Context *fc;
320  size_t size;
321  uint64_t bits;
322 
324  _ ("# messages fragmented"),
325  1,
326  GNUNET_NO);
327  GNUNET_assert (mtu >= 1024 + sizeof(struct FragmentHeader));
328  size = ntohs (msg->size);
330  _ ("# total size of fragmented messages"),
331  size, GNUNET_NO);
332  GNUNET_assert (size >= sizeof(struct GNUNET_MessageHeader));
333  fc = GNUNET_malloc (sizeof(struct GNUNET_FRAGMENT_Context) + size);
334  fc->stats = stats;
335  fc->mtu = mtu;
336  fc->tracker = tracker;
337  fc->ack_delay = ack_delay;
338  fc->msg_delay = msg_delay;
339  fc->msg = (const struct GNUNET_MessageHeader *) &fc[1];
340  fc->proc = proc;
341  fc->proc_cls = proc_cls;
342  fc->fragment_id =
344  UINT32_MAX);
345  GNUNET_memcpy (&fc[1], msg, size);
346  bits =
347  (size + mtu - sizeof(struct FragmentHeader) - 1) / (mtu
348  - sizeof(struct
349  FragmentHeader));
350  GNUNET_assert (bits <= 64);
351  if (bits == 64)
352  fc->acks_mask = UINT64_MAX; /* set all 64 bit */
353  else
354  fc->acks_mask = (1LLU << bits) - 1; /* set lowest 'bits' bit */
355  fc->acks = fc->acks_mask;
357  return fc;
358 }
359 
360 
368 void
370 {
372  fc->proc_busy = GNUNET_NO;
373  GNUNET_assert (fc->task == NULL);
374  fc->task =
376  &transmit_next,
377  fc);
378 }
379 
380 
392 int
394  const struct GNUNET_MessageHeader *msg)
395 {
396  const struct FragmentAcknowledgement *fa;
397  uint64_t abits;
398  struct GNUNET_TIME_Relative ndelay;
399  unsigned int ack_cnt;
400  unsigned int snd_cnt;
401  unsigned int i;
402 
403  if (sizeof(struct FragmentAcknowledgement) != ntohs (msg->size))
404  {
405  GNUNET_break_op (0);
406  return GNUNET_SYSERR;
407  }
408  fa = (const struct FragmentAcknowledgement *) msg;
409  if (ntohl (fa->fragment_id) != fc->fragment_id)
410  return GNUNET_SYSERR; /* not our ACK */
411  abits = GNUNET_ntohll (fa->bits);
412  if ((GNUNET_YES == fc->wack) &&
413  (0 != fc->num_transmissions))
414  {
415  /* normal ACK, can update running average of delay... */
416  fc->wack = GNUNET_NO;
418  fc->ack_delay.rel_value_us =
419  (ndelay.rel_value_us / fc->num_transmissions + 3
420  * fc->ack_delay.rel_value_us) / 4;
421  /* calculate ratio msg sent vs. msg acked */
422  ack_cnt = 0;
423  snd_cnt = 0;
424  for (i = 0; i < 64; i++)
425  {
426  if (1 == (fc->acks_mask & (1ULL << i)))
427  {
428  snd_cnt++;
429  if (0 == (abits & (1ULL << i)))
430  ack_cnt++;
431  }
432  }
433  if (0 == ack_cnt)
434  {
435  /* complete loss */
437  snd_cnt);
438  }
439  else if (snd_cnt > ack_cnt)
440  {
441  /* some loss, slow down proportionally */
442  fc->msg_delay.rel_value_us = ((fc->msg_delay.rel_value_us * ack_cnt)
443  / snd_cnt);
444  }
445  else if (snd_cnt == ack_cnt)
446  {
447  fc->msg_delay.rel_value_us =
448  (ndelay.rel_value_us / fc->num_transmissions + 3
449  * fc->msg_delay.rel_value_us) / 5;
450  }
451  fc->num_transmissions = 0;
456  }
458  _ ("# fragment acknowledgements received"),
459  1,
460  GNUNET_NO);
461  if (abits != (fc->acks & abits))
462  {
463  /* ID collision or message reordering, count! This should be rare! */
465  _ ("# bits removed from fragmentation ACKs"), 1,
466  GNUNET_NO);
467  }
468  fc->acks = abits & fc->acks_mask;
469  if (0 != fc->acks)
470  {
471  /* more to transmit, do so right now (if tracker permits...) */
472  if (fc->task != NULL)
473  {
474  /* schedule next transmission now, no point in waiting... */
477  }
478  else
479  {
480  /* only case where there is no task should be if we're waiting
481  * for the right to transmit again (proc_busy set to YES) */
483  }
484  return GNUNET_NO;
485  }
486 
487  /* all done */
489  _ ("# fragmentation transmissions completed"),
490  1,
491  GNUNET_NO);
492  if (NULL != fc->task)
493  {
495  fc->task = NULL;
496  }
497  return GNUNET_OK;
498 }
499 
500 
511 void
513  struct GNUNET_TIME_Relative *msg_delay,
514  struct GNUNET_TIME_Relative *ack_delay)
515 {
516  if (fc->task != NULL)
518  if (NULL != ack_delay)
519  *ack_delay = fc->ack_delay;
520  if (NULL != msg_delay)
522  fc->num_rounds);
523  GNUNET_free (fc);
524 }
525 
526 
527 /* end of fragmentation.c */
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
static void transmit_next(void *cls)
Transmit the next fragment to the other peer.
#define MIN_ACK_DELAY
Absolute minimum delay we impose between sending and expecting ACK to arrive.
Definition: fragmentation.c:33
library to help fragment messages
static struct GNUNET_TIME_Relative delay
When should dkg communication start?
struct GNUNET_STATISTICS_Handle * stats
Handle to the statistics service.
static char buf[2048]
static struct GNUNET_DISK_FileHandle * fh
File handle to STDIN, for reading restart/quit commands.
Constants for network protocols.
int GNUNET_BANDWIDTH_tracker_consume(struct GNUNET_BANDWIDTH_Tracker *av, ssize_t size)
Notify the tracker that a certain number of bytes of bandwidth have been consumed.
Definition: bandwidth.c:368
struct GNUNET_TIME_Relative GNUNET_BANDWIDTH_tracker_get_delay(struct GNUNET_BANDWIDTH_Tracker *av, size_t size)
Compute how long we should wait until consuming size bytes of bandwidth in order to stay within the g...
Definition: bandwidth.c:424
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_WEAK
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
const char * GNUNET_FRAGMENT_print_ack(const struct GNUNET_MessageHeader *ack)
Convert an ACK message to a printable format suitable for logging.
void GNUNET_FRAGMENT_context_transmission_done(struct GNUNET_FRAGMENT_Context *fc)
Continuation to call from the 'proc' function after the fragment has been transmitted (and hence the ...
int GNUNET_FRAGMENT_process_ack(struct GNUNET_FRAGMENT_Context *fc, const struct GNUNET_MessageHeader *msg)
Process an acknowledgement message we got from the other side (to control re-transmits).
void(* GNUNET_FRAGMENT_MessageProcessor)(void *cls, const struct GNUNET_MessageHeader *msg)
Function that is called with messages created by the fragmentation module.
void GNUNET_FRAGMENT_context_destroy(struct GNUNET_FRAGMENT_Context *fc, struct GNUNET_TIME_Relative *msg_delay, struct GNUNET_TIME_Relative *ack_delay)
Destroy the given fragmentation context (stop calling 'proc', free resources).
struct GNUNET_FRAGMENT_Context * GNUNET_FRAGMENT_context_create(struct GNUNET_STATISTICS_Handle *stats, uint16_t mtu, struct GNUNET_BANDWIDTH_Tracker *tracker, struct GNUNET_TIME_Relative msg_delay, struct GNUNET_TIME_Relative ack_delay, const struct GNUNET_MessageHeader *msg, GNUNET_FRAGMENT_MessageProcessor proc, void *proc_cls)
Create a fragmentation context for the given message.
#define GNUNET_log(kind,...)
uint64_t GNUNET_ntohll(uint64_t n)
Convert unsigned 64-bit integer to host byte order.
Definition: common_endian.c:54
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_DEBUG
int GNUNET_snprintf(char *buf, size_t size, const char *format,...) __attribute__((format(printf
Like snprintf, just aborts if the buffer is of insufficient size.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
#define GNUNET_MESSAGE_TYPE_FRAGMENT
FRAGMENT of a larger message.
struct GNUNET_SCHEDULER_Task * GNUNET_SCHEDULER_add_now(GNUNET_SCHEDULER_TaskCallback task, void *task_cls)
Schedule a new task to be run as soon as possible.
Definition: scheduler.c:1268
struct GNUNET_SCHEDULER_Task * GNUNET_SCHEDULER_add_at(struct GNUNET_TIME_Absolute at, GNUNET_SCHEDULER_TaskCallback task, void *task_cls)
Schedule a new task to be run at the specified time.
Definition: scheduler.c:1218
void * GNUNET_SCHEDULER_cancel(struct GNUNET_SCHEDULER_Task *task)
Cancel the task with the specified identifier.
Definition: scheduler.c:944
struct GNUNET_SCHEDULER_Task * GNUNET_SCHEDULER_add_delayed(struct GNUNET_TIME_Relative delay, GNUNET_SCHEDULER_TaskCallback task, void *task_cls)
Schedule a new task to be run with a specified delay.
Definition: scheduler.c:1241
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
struct GNUNET_TIME_Relative GNUNET_TIME_relative_min(struct GNUNET_TIME_Relative t1, struct GNUNET_TIME_Relative t2)
Return the minimum of two relative time values.
Definition: time.c:343
#define GNUNET_TIME_UNIT_FOREVER_REL
Constant used to specify "forever".
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_duration(struct GNUNET_TIME_Absolute whence)
Get the duration of an operation as the difference of the current time and the given start time "henc...
Definition: time.c:436
struct GNUNET_TIME_Relative GNUNET_TIME_relative_saturating_multiply(struct GNUNET_TIME_Relative rel, unsigned long long factor)
Saturating multiply relative time by a given factor.
Definition: time.c:531
struct GNUNET_TIME_Relative GNUNET_TIME_relative_max(struct GNUNET_TIME_Relative t1, struct GNUNET_TIME_Relative t2)
Return the maximum of two relative time values.
Definition: time.c:351
#define GNUNET_TIME_UNIT_SECONDS
One second.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:111
struct GNUNET_TIME_Absolute GNUNET_TIME_relative_to_absolute(struct GNUNET_TIME_Relative rel)
Convert relative time to an absolute time in the future.
Definition: time.c:316
#define GNUNET_TIME_UNIT_ZERO
Relative time zero.
const char * GNUNET_STRINGS_relative_time_to_string(struct GNUNET_TIME_Relative delta, int do_round)
Give relative time in human-readable fancy format.
Definition: strings.c:569
static unsigned int size
Size of the "table".
Definition: peer.c:68
#define _(String)
GNU gettext support macro.
Definition: platform.h:177
Message fragment acknowledgement.
Definition: fragmentation.h:67
uint32_t fragment_id
Unique fragment ID.
Definition: fragmentation.h:76
uint64_t bits
Bits that are being acknowledged, in big-endian.
Definition: fragmentation.h:83
Header for a message fragment.
Definition: fragmentation.h:39
Struct to track available bandwidth.
Fragmentation context.
Definition: fragmentation.c:41
struct GNUNET_TIME_Absolute last_round
Time we transmitted the last message of the last round.
Definition: fragmentation.c:70
uint32_t fragment_id
Our fragmentation ID.
int8_t wack
GNUNET_YES if we are waiting for an ACK.
struct GNUNET_TIME_Relative ack_delay
Current expected delay for ACKs.
Definition: fragmentation.c:55
unsigned int next_transmission
Round-robin selector for the next transmission.
GNUNET_FRAGMENT_MessageProcessor proc
Function to call for transmissions.
Definition: fragmentation.c:80
struct GNUNET_TIME_Relative msg_delay
Current expected delay between messages.
Definition: fragmentation.c:60
struct GNUNET_SCHEDULER_Task * task
Task performing work for the fragmenter.
const struct GNUNET_MessageHeader * msg
Message to fragment (allocated at the end of this struct).
Definition: fragmentation.c:75
unsigned int num_rounds
How many rounds of transmission have we completed so far?
int8_t proc_busy
GNUNET_YES if we called proc and are now waiting for GNUNET_FRAGMENT_context_transmission_done()
void * proc_cls
Closure for proc.
Definition: fragmentation.c:85
uint64_t acks_mask
Bitfield with all possible bits for acks (used to mask the ack we get back).
Definition: fragmentation.c:96
unsigned int num_transmissions
How many transmission have we completed in this round?
uint16_t mtu
Target fragment size.
struct GNUNET_TIME_Absolute delay_until
Next allowed transmission time.
Definition: fragmentation.c:65
uint64_t acks
Bitfield, set to 1 for each unacknowledged fragment.
Definition: fragmentation.c:90
struct GNUNET_STATISTICS_Handle * stats
Statistics to use.
Definition: fragmentation.c:45
struct GNUNET_BANDWIDTH_Tracker * tracker
Tracker for flow control.
Definition: fragmentation.c:50
Header for all communications.
uint16_t size
The length of the struct (in bytes, including the length field itself), in big-endian format.
Entry in list of pending tasks.
Definition: scheduler.c:136
Handle for the service.
Time for absolute times used by GNUnet, in microseconds.
uint64_t abs_value_us
The actual value.
Time for relative time used by GNUnet, in microseconds.
uint64_t rel_value_us
The actual value.