GNUnet  0.11.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 260 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().

261 {
262  struct MessageContext *mc = cls;
263  struct GNUNET_DEFRAGMENT_Context *dc = mc->dc;
264  struct FragmentAcknowledgement fa;
265 
266  mc->ack_task = NULL;
267  fa.header.size = htons (sizeof(struct FragmentAcknowledgement));
268  fa.header.type = htons (GNUNET_MESSAGE_TYPE_FRAGMENT_ACK);
269  fa.fragment_id = htonl (mc->fragment_id);
270  fa.bits = GNUNET_htonll (mc->bits);
272  _ ("# acknowledgements sent for fragment"),
273  1,
274  GNUNET_NO);
275  mc->last_duplicate = GNUNET_NO; /* clear flag */
276  dc->ackp (dc->cls,
277  mc->fragment_id,
278  &fa.header);
279 }
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:64
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 287 of file defragmentation.c.

Referenced by estimate_latency().

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

347 {
348  struct FragTimes *first;
349  size_t total = mc->frag_times_write_offset - mc->frag_times_start_offset;
350  double x[total];
351  double y[total];
352  size_t i;
353  double c1;
354  double cov11;
355  double sumsq;
356  struct GNUNET_TIME_Relative ret;
357 
358  first = &mc->frag_times[mc->frag_times_start_offset];
359  GNUNET_assert (total > 1);
360  for (i = 0; i < total; i++)
361  {
362  x[i] = (double) i;
363  y[i] = (double) (first[i].time.abs_value_us - first[0].time.abs_value_us);
364  }
365  gsl_fit_mul (x, 1, y, 1, total, &c1, &cov11, &sumsq);
366  c1 += sqrt (sumsq); /* add 1 std dev */
367  ret.rel_value_us = (uint64_t) c1;
368  if (0 == ret.rel_value_us)
369  ret = GNUNET_TIME_UNIT_MICROSECONDS; /* always at least 1 */
370  return ret;
371 }
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...
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
Timestamps for fragments.
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 380 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().

381 {
382  struct MessageContext *old;
383  struct MessageContext *pos;
384 
385  old = NULL;
386  pos = dc->head;
387  while (NULL != pos)
388  {
389  if ((old == NULL) ||
391  old = pos;
392  pos = pos->next;
393  }
394  GNUNET_assert (NULL != old);
395  GNUNET_CONTAINER_DLL_remove (dc->head, dc->tail, old);
396  dc->list_size--;
397  if (NULL != old->ack_task)
398  {
400  old->ack_task = NULL;
401  }
402  GNUNET_free (old);
403 }
#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:966
Here is the call graph for this function:
Here is the caller graph for this function: