2 This file is part of GNUnet
3 (C) 2009, 2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
21 * @file src/fragmentation/defragmentation.c
22 * @brief library to help defragment messages
23 * @author Christian Grothoff
26 #include "gnunet_fragmentation_lib.h"
27 #include "fragmentation.h"
30 * Timestamps for fragments.
35 * The time the fragment was received.
37 struct GNUNET_TIME_Absolute time;
40 * Number of the bit for the fragment (in [0,..,63]).
47 * Information we keep for one message that is being assembled. Note
48 * that we keep the context around even after the assembly is done to
49 * handle 'stray' messages that are received 'late'. A message
50 * context is ONLY discarded when the queue gets too big.
57 struct MessageContext *next;
62 struct MessageContext *prev;
65 * Associated defragmentation context.
67 struct GNUNET_DEFRAGMENT_Context *dc;
70 * Pointer to the assembled message, allocated at the
73 const struct GNUNET_MessageHeader *msg;
76 * Last time we received any update for this message
77 * (least-recently updated message will be discarded
78 * if we hit the queue size).
80 struct GNUNET_TIME_Absolute last_update;
83 * Task scheduled for transmitting the next ACK to the
86 GNUNET_SCHEDULER_TaskIdentifier ack_task;
89 * When did we receive which fragment? Used to calculate
90 * the time we should send the ACK.
92 struct FragTimes frag_times[64];
95 * Which fragments have we gotten yet? bits that are 1
96 * indicate missing fragments.
101 * Unique ID for this message.
103 uint32_t fragment_id;
106 * Which 'bit' did the last fragment we received correspond to?
108 unsigned int last_bit;
111 * For the current ACK round, which is the first relevant
112 * offset in 'frag_times'?
114 unsigned int frag_times_start_offset;
117 * Which offset whould we write the next frag value into
118 * in the 'frag_times' array? All smaller entries are valid.
120 unsigned int frag_times_write_offset;
123 * Total size of the message that we are assembling.
131 * Defragmentation context (one per connection).
133 struct GNUNET_DEFRAGMENT_Context
139 struct GNUNET_STATISTICS_Handle *stats;
142 * Head of list of messages we're defragmenting.
144 struct MessageContext *head;
147 * Tail of list of messages we're defragmenting.
149 struct MessageContext *tail;
152 * Closure for 'proc' and 'ackp'.
157 * Function to call with defragmented messages.
159 GNUNET_FRAGMENT_MessageProcessor proc;
162 * Function to call with acknowledgements.
164 GNUNET_DEFRAGMENT_AckProcessor ackp;
167 * Running average of the latency (delay between messages) for this
170 struct GNUNET_TIME_Relative latency;
173 * num_msgs how many fragmented messages
174 * to we defragment at most at the same time?
176 unsigned int num_msgs;
179 * Current number of messages in the 'struct MessageContext'
180 * DLL (smaller or equal to 'num_msgs').
182 unsigned int list_size;
185 * Maximum message size for each fragment.
192 * Create a defragmentation context.
194 * @param stats statistics context
195 * @param mtu the maximum message size for each fragment
196 * @param num_msgs how many fragmented messages
197 * to we defragment at most at the same time?
198 * @param cls closure for proc and ackp
199 * @param proc function to call with defragmented messages
200 * @param ackp function to call with acknowledgements (to send
201 * back to the other side)
202 * @return the defragmentation context
204 struct GNUNET_DEFRAGMENT_Context *
205 GNUNET_DEFRAGMENT_context_create (struct GNUNET_STATISTICS_Handle *stats,
207 unsigned int num_msgs,
209 GNUNET_FRAGMENT_MessageProcessor proc,
210 GNUNET_DEFRAGMENT_AckProcessor ackp)
212 struct GNUNET_DEFRAGMENT_Context *dc;
214 dc = GNUNET_malloc (sizeof (struct GNUNET_DEFRAGMENT_Context));
219 dc->num_msgs = num_msgs;
221 dc->latency = GNUNET_TIME_UNIT_SECONDS; /* start with likely overestimate */
227 * Destroy the given defragmentation context.
229 * @param dc defragmentation context
232 GNUNET_DEFRAGMENT_context_destroy (struct GNUNET_DEFRAGMENT_Context *dc)
234 struct MessageContext *mc;
236 while (NULL != (mc = dc->head))
238 GNUNET_CONTAINER_DLL_remove (dc->head, dc->tail, mc);
240 if (GNUNET_SCHEDULER_NO_TASK != mc->ack_task)
242 GNUNET_SCHEDULER_cancel (mc->ack_task);
243 mc->ack_task = GNUNET_SCHEDULER_NO_TASK;
247 GNUNET_assert (0 == dc->list_size);
253 * Send acknowledgement to the other peer now.
255 * @param cls the message context
256 * @param tc the scheduler context
259 send_ack (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
261 struct MessageContext *mc = cls;
262 struct GNUNET_DEFRAGMENT_Context *dc = mc->dc;
263 struct FragmentAcknowledgement fa;
265 mc->ack_task = GNUNET_SCHEDULER_NO_TASK;
266 fa.header.size = htons (sizeof (struct FragmentAcknowledgement));
267 fa.header.type = htons (GNUNET_MESSAGE_TYPE_FRAGMENT_ACK);
268 fa.fragment_id = htonl (mc->fragment_id);
269 fa.bits = GNUNET_htonll (mc->bits);
270 GNUNET_STATISTICS_update (mc->dc->stats,
271 _("# acknowledgements sent for fragment"),
273 dc->ackp (dc->cls, mc->fragment_id, &fa.header);
278 * This function is from the GNU Scientific Library, linear/fit.c,
279 * (C) 2000 Brian Gough
282 gsl_fit_mul (const double *x, const size_t xstride,
283 const double *y, const size_t ystride,
284 const size_t n, double *c1, double *cov_11, double *sumsq)
286 double m_x = 0, m_y = 0, m_dx2 = 0, m_dxdy = 0;
290 for (i = 0; i < n; i++)
292 m_x += (x[i * xstride] - m_x) / (i + 1.0);
293 m_y += (y[i * ystride] - m_y) / (i + 1.0);
296 for (i = 0; i < n; i++)
298 const double dx = x[i * xstride] - m_x;
299 const double dy = y[i * ystride] - m_y;
301 m_dx2 += (dx * dx - m_dx2) / (i + 1.0);
302 m_dxdy += (dx * dy - m_dxdy) / (i + 1.0);
305 /* In terms of y = b x */
308 double s2 = 0, d2 = 0;
309 double b = (m_x * m_y + m_dxdy) / (m_x * m_x + m_dx2);
313 /* Compute chi^2 = \sum (y_i - b * x_i)^2 */
315 for (i = 0; i < n; i++)
317 const double dx = x[i * xstride] - m_x;
318 const double dy = y[i * ystride] - m_y;
319 const double d = (m_y - b * m_x) + dy - b * dx;
324 s2 = d2 / (n - 1.0); /* chisq per degree of freedom */
326 *cov_11 = s2 * 1.0 / (n * (m_x * m_x + m_dx2));
334 * Estimate the latency between messages based on the most recent
335 * message time stamps.
337 * @param mc context with time stamps
338 * @return average delay between time stamps (based on least-squares fit)
340 static struct GNUNET_TIME_Relative
341 estimate_latency (struct MessageContext *mc)
343 struct FragTimes *first;
344 size_t total = mc->frag_times_write_offset - mc->frag_times_start_offset;
351 struct GNUNET_TIME_Relative ret;
353 first = &mc->frag_times[mc->frag_times_start_offset];
354 GNUNET_assert (total > 1);
355 for (i = 0; i < total; i++)
358 y[i] = (double) (first[i].time.abs_value - first[0].time.abs_value);
360 gsl_fit_mul (x, 1, y, 1, total, &c1, &cov11, &sumsq);
361 c1 += sqrt (sumsq); /* add 1 std dev */
362 ret.rel_value = (uint64_t) c1;
363 if (ret.rel_value == 0)
364 ret = GNUNET_TIME_UNIT_MILLISECONDS; /* always at least 1 */
370 * Discard the message context that was inactive for the longest time.
372 * @param dc defragmentation context
375 discard_oldest_mc (struct GNUNET_DEFRAGMENT_Context *dc)
377 struct MessageContext *old;
378 struct MessageContext *pos;
385 (old->last_update.abs_value > pos->last_update.abs_value))
389 GNUNET_assert (NULL != old);
390 GNUNET_CONTAINER_DLL_remove (dc->head, dc->tail, old);
392 if (GNUNET_SCHEDULER_NO_TASK != old->ack_task)
394 GNUNET_SCHEDULER_cancel (old->ack_task);
395 old->ack_task = GNUNET_SCHEDULER_NO_TASK;
402 * We have received a fragment. Process it.
404 * @param dc the context
405 * @param msg the message that was received
406 * @return GNUNET_OK on success, GNUNET_NO if this was a duplicate, GNUNET_SYSERR on error
409 GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc,
410 const struct GNUNET_MessageHeader *msg)
412 struct MessageContext *mc;
413 const struct FragmentHeader *fh;
419 struct GNUNET_TIME_Absolute now;
420 struct GNUNET_TIME_Relative delay;
426 if (ntohs (msg->size) < sizeof (struct FragmentHeader))
429 return GNUNET_SYSERR;
431 if (ntohs (msg->size) > dc->mtu)
434 return GNUNET_SYSERR;
436 fh = (const struct FragmentHeader *) msg;
437 msize = ntohs (fh->total_size);
438 if (msize < sizeof (struct GNUNET_MessageHeader))
441 return GNUNET_SYSERR;
443 fid = ntohl (fh->fragment_id);
444 foff = ntohs (fh->offset);
448 return GNUNET_SYSERR;
450 if (0 != (foff % (dc->mtu - sizeof (struct FragmentHeader))))
453 return GNUNET_SYSERR;
455 GNUNET_STATISTICS_update (dc->stats, _("# fragments received"), 1, GNUNET_NO);
457 while ((NULL != mc) && (fid != mc->fragment_id))
459 bit = foff / (dc->mtu - sizeof (struct FragmentHeader));
460 if (bit * (dc->mtu - sizeof (struct FragmentHeader)) + ntohs (msg->size)
461 - sizeof (struct FragmentHeader) > msize)
463 /* payload extends past total message size */
465 return GNUNET_SYSERR;
467 if ((NULL != mc) && (msize != mc->total_size))
469 /* inconsistent message size */
471 return GNUNET_SYSERR;
473 now = GNUNET_TIME_absolute_get ();
476 mc = GNUNET_malloc (sizeof (struct MessageContext) + msize);
477 mc->msg = (const struct GNUNET_MessageHeader *) &mc[1];
479 mc->total_size = msize;
480 mc->fragment_id = fid;
481 mc->last_update = now;
482 n = (msize + dc->mtu - sizeof (struct FragmentHeader) - 1) / (dc->mtu -
486 mc->bits = UINT64_MAX; /* set all 64 bit */
488 mc->bits = (1LL << n) - 1; /* set lowest 'bits' bit */
489 if (dc->list_size >= dc->num_msgs)
490 discard_oldest_mc (dc);
491 GNUNET_CONTAINER_DLL_insert (dc->head, dc->tail, mc);
495 /* copy data to 'mc' */
496 if (0 != (mc->bits & (1LL << bit)))
498 mc->bits -= 1LL << bit;
499 mbuf = (char *) &mc[1];
500 memcpy (&mbuf[bit * (dc->mtu - sizeof (struct FragmentHeader))],
501 &fh[1], ntohs (msg->size) - sizeof (struct FragmentHeader));
502 mc->last_update = now;
503 if (bit < mc->last_bit)
504 mc->frag_times_start_offset = mc->frag_times_write_offset;
506 mc->frag_times[mc->frag_times_write_offset].time = now;
507 mc->frag_times[mc->frag_times_write_offset].bit = bit;
508 mc->frag_times_write_offset++;
509 duplicate = GNUNET_NO;
513 duplicate = GNUNET_YES;
514 GNUNET_STATISTICS_update (dc->stats,
515 _("# duplicate fragments received"),
519 /* count number of missing fragments */
521 for (b = 0; b < 64; b++)
522 if (0 != (mc->bits & (1LL << b)))
524 if (mc->frag_times_write_offset - mc->frag_times_start_offset > 1)
525 dc->latency = estimate_latency (mc);
526 delay = GNUNET_TIME_relative_multiply (dc->latency, bc + 1);
527 if ((0 == mc->bits) || (GNUNET_YES == duplicate)) /* message complete or duplicate, ACK now! */
528 delay = GNUNET_TIME_UNIT_ZERO;
529 if (GNUNET_SCHEDULER_NO_TASK != mc->ack_task)
530 GNUNET_SCHEDULER_cancel (mc->ack_task);
531 mc->ack_task = GNUNET_SCHEDULER_add_delayed (delay, &send_ack, mc);
532 if ((duplicate == GNUNET_NO) && (0 == mc->bits))
534 GNUNET_STATISTICS_update (dc->stats,
535 _("# messages defragmented"), 1, GNUNET_NO);
536 /* message complete, notify! */
537 dc->proc (dc->cls, mc->msg);
539 if (duplicate == GNUNET_YES)
544 /* end of defragmentation.c */