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 263 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().

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

Referenced by estimate_latency().

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

350 {
351  struct FragTimes *first;
352  size_t total = mc->frag_times_write_offset - mc->frag_times_start_offset;
353  double x[total];
354  double y[total];
355  size_t i;
356  double c1;
357  double cov11;
358  double sumsq;
359  struct GNUNET_TIME_Relative ret;
360 
361  first = &mc->frag_times[mc->frag_times_start_offset];
362  GNUNET_assert (total > 1);
363  for (i = 0; i < total; i++)
364  {
365  x[i] = (double) i;
366  y[i] = (double) (first[i].time.abs_value_us - first[0].time.abs_value_us);
367  }
368  gsl_fit_mul (x, 1, y, 1, total, &c1, &cov11, &sumsq);
369  c1 += sqrt (sumsq); /* add 1 std dev */
370  ret.rel_value_us = (uint64_t) c1;
371  if (0 == ret.rel_value_us)
372  ret = GNUNET_TIME_UNIT_MICROSECONDS; /* always at least 1 */
373  return ret;
374 }
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 383 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().

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