GNUnet  0.10.x
Data Structures | Functions
defragmentation.c File Reference

library to help defragment messages More...

#include "platform.h"
#include "gnunet_fragmentation_lib.h"
#include "fragmentation.h"
Include dependency graph for defragmentation.c:

Go to the source code of this file.

Data Structures

struct  FragTimes
 Timestamps for fragments. More...
 
struct  MessageContext
 Information we keep for one message that is being assembled. More...
 
struct  GNUNET_DEFRAGMENT_Context
 Defragmentation context (one per connection). More...
 

Functions

struct GNUNET_DEFRAGMENT_ContextGNUNET_DEFRAGMENT_context_create (struct GNUNET_STATISTICS_Handle *stats, uint16_t mtu, unsigned int num_msgs, void *cls, GNUNET_FRAGMENT_MessageProcessor proc, GNUNET_DEFRAGMENT_AckProcessor ackp)
 Create a defragmentation context. More...
 
void GNUNET_DEFRAGMENT_context_destroy (struct GNUNET_DEFRAGMENT_Context *dc)
 Destroy the given defragmentation context. More...
 
static void send_ack (void *cls)
 Send acknowledgement to the other peer now. More...
 
static void gsl_fit_mul (const double *x, const size_t xstride, const double *y, const size_t ystride, const size_t n, double *c1, double *cov_11, double *sumsq)
 This function is from the GNU Scientific Library, linear/fit.c, Copyright (C) 2000 Brian Gough. More...
 
static struct GNUNET_TIME_Relative estimate_latency (struct MessageContext *mc)
 Estimate the latency between messages based on the most recent message time stamps. More...
 
static void discard_oldest_mc (struct GNUNET_DEFRAGMENT_Context *dc)
 Discard the message context that was inactive for the longest time. More...
 
int GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc, const struct GNUNET_MessageHeader *msg)
 We have received a fragment. More...
 

Detailed Description

library to help defragment messages

Author
Christian Grothoff

Definition in file defragmentation.c.

Function Documentation

◆ send_ack()

static void send_ack ( void *  cls)
static

Send acknowledgement to the other peer now.

Parameters
clsthe message context

Definition at line 257 of file defragmentation.c.

References _, MessageContext::ack_task, GNUNET_DEFRAGMENT_Context::ackp, FragmentAcknowledgement::bits, MessageContext::bits, GNUNET_DEFRAGMENT_Context::cls, dc, MessageContext::dc, FragmentAcknowledgement::fragment_id, MessageContext::fragment_id, GNUNET_htonll(), GNUNET_MESSAGE_TYPE_FRAGMENT_ACK, GNUNET_NO, GNUNET_STATISTICS_update(), FragmentAcknowledgement::header, MessageContext::last_duplicate, mc, GNUNET_MessageHeader::size, GNUNET_DEFRAGMENT_Context::stats, and GNUNET_MessageHeader::type.

Referenced by GNUNET_DEFRAGMENT_process_fragment().

258 {
259  struct MessageContext *mc = cls;
260  struct GNUNET_DEFRAGMENT_Context *dc = mc->dc;
261  struct FragmentAcknowledgement fa;
262 
263  mc->ack_task = NULL;
264  fa.header.size = htons(sizeof(struct FragmentAcknowledgement));
265  fa.header.type = htons(GNUNET_MESSAGE_TYPE_FRAGMENT_ACK);
266  fa.fragment_id = htonl(mc->fragment_id);
267  fa.bits = GNUNET_htonll(mc->bits);
269  _("# acknowledgements sent for fragment"),
270  1,
271  GNUNET_NO);
272  mc->last_duplicate = GNUNET_NO; /* clear flag */
273  dc->ackp(dc->cls,
274  mc->fragment_id,
275  &fa.header);
276 }
struct GNUNET_SCHEDULER_Task * ack_task
Task scheduled for transmitting the next ACK to the other peer.
uint64_t bits
Which fragments have we gotten yet? bits that are 1 indicate missing fragments.
#define GNUNET_NO
Definition: gnunet_common.h:78
void * cls
Closure for proc and ackp.
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
#define GNUNET_MESSAGE_TYPE_FRAGMENT_ACK
Acknowledgement of a FRAGMENT of a larger message.
GNUNET_DEFRAGMENT_AckProcessor ackp
Function to call with acknowledgements.
#define _(String)
GNU gettext support macro.
Definition: platform.h:181
Information we keep for one message that is being assembled.
uint32_t fragment_id
Unique ID for this message.
static struct GNUNET_TESTBED_Controller * mc
Handle to the master controller.
int16_t last_duplicate
Was the last fragment we got a duplicate?
struct GNUNET_DEFRAGMENT_Context * dc
Associated defragmentation context.
Defragmentation context (one per connection).
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:35
struct GNUNET_STATISTICS_Handle * stats
For statistics.
Message fragment acknowledgement.
Definition: fragmentation.h:63
static struct GNUNET_FS_DownloadContext * dc
Here is the call graph for this function:
Here is the caller graph for this function:

◆ gsl_fit_mul()

static void gsl_fit_mul ( const double *  x,
const size_t  xstride,
const double *  y,
const size_t  ystride,
const size_t  n,
double *  c1,
double *  cov_11,
double *  sumsq 
)
static

This function is from the GNU Scientific Library, linear/fit.c, Copyright (C) 2000 Brian Gough.

Definition at line 284 of file defragmentation.c.

Referenced by estimate_latency().

287 {
288  double m_x = 0, m_y = 0, m_dx2 = 0, m_dxdy = 0;
289 
290  size_t i;
291 
292  for (i = 0; i < n; i++)
293  {
294  m_x += (x[i * xstride] - m_x) / (i + 1.0);
295  m_y += (y[i * ystride] - m_y) / (i + 1.0);
296  }
297 
298  for (i = 0; i < n; i++)
299  {
300  const double dx = x[i * xstride] - m_x;
301  const double dy = y[i * ystride] - m_y;
302 
303  m_dx2 += (dx * dx - m_dx2) / (i + 1.0);
304  m_dxdy += (dx * dy - m_dxdy) / (i + 1.0);
305  }
306 
307  /* In terms of y = b x */
308 
309  {
310  double s2 = 0, d2 = 0;
311  double b = (m_x * m_y + m_dxdy) / (m_x * m_x + m_dx2);
312 
313  *c1 = b;
314 
315  /* Compute chi^2 = \sum (y_i - b * x_i)^2 */
316 
317  for (i = 0; i < n; i++)
318  {
319  const double dx = x[i * xstride] - m_x;
320  const double dy = y[i * ystride] - m_y;
321  const double d = (m_y - b * m_x) + dy - b * dx;
322 
323  d2 += d * d;
324  }
325 
326  s2 = d2 / (n - 1.0); /* chisq per degree of freedom */
327 
328  *cov_11 = s2 * 1.0 / (n * (m_x * m_x + m_dx2));
329 
330  *sumsq = d2;
331  }
332 }
Here is the caller graph for this function:

◆ estimate_latency()

static struct GNUNET_TIME_Relative estimate_latency ( struct MessageContext mc)
static

Estimate the latency between messages based on the most recent message time stamps.

Parameters
mccontext with time stamps
Returns
average delay between time stamps (based on least-squares fit)

Definition at line 343 of file defragmentation.c.

References GNUNET_TIME_Absolute::abs_value_us, GNUNET_assert, GNUNET_TIME_UNIT_MICROSECONDS, gsl_fit_mul(), mc, GNUNET_TIME_Relative::rel_value_us, ret, and FragTimes::time.

Referenced by GNUNET_DEFRAGMENT_process_fragment().

344 {
345  struct FragTimes *first;
346  size_t total = mc->frag_times_write_offset - mc->frag_times_start_offset;
347  double x[total];
348  double y[total];
349  size_t i;
350  double c1;
351  double cov11;
352  double sumsq;
353  struct GNUNET_TIME_Relative ret;
354 
355  first = &mc->frag_times[mc->frag_times_start_offset];
356  GNUNET_assert(total > 1);
357  for (i = 0; i < total; i++)
358  {
359  x[i] = (double)i;
360  y[i] = (double)(first[i].time.abs_value_us - first[0].time.abs_value_us);
361  }
362  gsl_fit_mul(x, 1, y, 1, total, &c1, &cov11, &sumsq);
363  c1 += sqrt(sumsq); /* add 1 std dev */
364  ret.rel_value_us = (uint64_t)c1;
365  if (0 == ret.rel_value_us)
366  ret = GNUNET_TIME_UNIT_MICROSECONDS; /* always at least 1 */
367  return ret;
368 }
unsigned int frag_times_start_offset
For the current ACK round, which is the first relevant offset in frag_times?
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void gsl_fit_mul(const double *x, const size_t xstride, const double *y, const size_t ystride, const size_t n, double *c1, double *cov_11, double *sumsq)
This function is from the GNU Scientific Library, linear/fit.c, Copyright (C) 2000 Brian Gough...
Timestamps for fragments.
static int ret
Final status code.
Definition: gnunet-arm.c:89
struct FragTimes frag_times[64]
When did we receive which fragment? Used to calculate the time we should send the ACK...
unsigned int frag_times_write_offset
Which offset whould we write the next frag value into in the frag_times array? All smaller entries ar...
#define GNUNET_TIME_UNIT_MICROSECONDS
One microsecond, our basic time unit.
Time for relative time used by GNUnet, in microseconds.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ discard_oldest_mc()

static void discard_oldest_mc ( struct GNUNET_DEFRAGMENT_Context dc)
static

Discard the message context that was inactive for the longest time.

Parameters
dcdefragmentation context

Definition at line 377 of file defragmentation.c.

References GNUNET_TIME_Absolute::abs_value_us, MessageContext::ack_task, GNUNET_assert, GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_SCHEDULER_cancel(), GNUNET_DEFRAGMENT_Context::head, MessageContext::last_update, GNUNET_DEFRAGMENT_Context::list_size, MessageContext::next, and GNUNET_DEFRAGMENT_Context::tail.

Referenced by GNUNET_DEFRAGMENT_process_fragment().

378 {
379  struct MessageContext *old;
380  struct MessageContext *pos;
381 
382  old = NULL;
383  pos = dc->head;
384  while (NULL != pos)
385  {
386  if ((old == NULL) ||
388  old = pos;
389  pos = pos->next;
390  }
391  GNUNET_assert(NULL != old);
392  GNUNET_CONTAINER_DLL_remove(dc->head, dc->tail, old);
393  dc->list_size--;
394  if (NULL != old->ack_task)
395  {
397  old->ack_task = NULL;
398  }
399  GNUNET_free(old);
400 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct MessageContext * tail
Tail of list of messages we&#39;re defragmenting.
struct GNUNET_SCHEDULER_Task * ack_task
Task scheduled for transmitting the next ACK to the other peer.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_TIME_Absolute last_update
Last time we received any update for this message (least-recently updated message will be discarded i...
uint64_t abs_value_us
The actual value.
unsigned int list_size
Current number of messages in the &#39;struct MessageContext&#39; DLL (smaller or equal to &#39;num_msgs&#39;)...
struct MessageContext * head
Head of list of messages we&#39;re defragmenting.
Information we keep for one message that is being assembled.
struct MessageContext * next
This is a DLL.
#define GNUNET_free(ptr)
Wrapper around free.
void * GNUNET_SCHEDULER_cancel(struct GNUNET_SCHEDULER_Task *task)
Cancel the task with the specified identifier.
Definition: scheduler.c:956
Here is the call graph for this function:
Here is the caller graph for this function: