lttv/lttv/sync/data_structures.c

   1 /* This file is part of the Linux Trace Toolkit viewer
   2  * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
   3  *
   4  * This program is free software: you can redistribute it and/or modify it
   5  * under the terms of the GNU Lesser General Public License as published by
   6  * the Free Software Foundation, either version 2.1 of the License, or (at
   7  * your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  12  * License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public License
  15  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #ifdef HAVE_CONFIG_H
  19 #include <config.h>
  20 #endif
  21
  22 #include <arpa/inet.h>
  23 #include <glib.h>
  24 #include <stdint.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 #include <unistd.h>
  30
  31 #include "lookup3.h"
  32
  33 #include "data_structures.h"
  34
  35
  36 // TCP sequence numbers use clock arithmetic, these comparison functions take
  37 // that into account
  38 #define SEQ_LT(a,b)     ((int32_t)((a)-(b)) < 0)
  39 #define SEQ_LEQ(a,b)    ((int32_t)((a)-(b)) <= 0)
  40 #define SEQ_GT(a,b)     ((int32_t)((a)-(b)) > 0)
  41 #define SEQ_GEQ(a,b)    ((int32_t)((a)-(b)) >= 0)
  42
  43
  44 /*
  45  * Compare two ConnectionKey structures
  46  *
  47  * Returns:
  48  *   true if each field of the structure is equal
  49  *   false otherwise
  50  */
  51 bool connectionKeyEqual(const ConnectionKey* const a, const
  52         ConnectionKey* const b)
  53 {
  54         if (a->saddr == b->saddr && a->daddr == b->daddr && a->source == b->source
  55                 && a->dest == b->dest)
  56         {
  57                 return true;
  58         }
  59         else
  60         {
  61                 return false;
  62         }
  63 }
  64
  65
  66 /*
  67  * Check if a packet is an acknowledge of another packet.
  68  *
  69  * Args:
  70  *   ackSegment    packet that is the confirmation
  71  *   ackedSegment  packet that contains the original data, both packets have to
  72  *                 come from the same direction of the same connection. Both
  73  *                 messages have to contain TCP events.
  74  */
  75 bool isAcking(const Message* const ackSegment, const Message* const
  76         ackedSegment)
  77 {
  78         g_assert(ackSegment->inE->type == TCP);
  79         g_assert(ackSegment->outE->type == TCP);
  80
  81         if (SEQ_GT(ackSegment->inE->event.tcpEvent->segmentKey->ack_seq,
  82                         ackedSegment->inE->event.tcpEvent->segmentKey->seq))
  83     {
  84         return true;
  85     }
  86     else
  87     {
  88         return false;
  89     }
  90 }
  91
  92
  93 /*
  94  * Convert an IP address from 32 bit form to dotted quad
  95  *
  96  * Args:
  97  *   str:          A preallocated string of length >= 16
  98  *   addr:         Address
  99  */
 100 void convertIP(char* const str, const uint32_t addr)
 101 {
 102         strcpy(str, inet_ntoa((struct in_addr) {.s_addr= addr}));
 103 }
 104
 105
 106 /*
 107  * Print the content of a TCP Message structure
 108  */
 109 void printTCPSegment(const Message* const segment)
 110 {
 111         char saddr[16], daddr[16];
 112         SegmentKey* segmentKey;
 113
 114         g_assert(segment->inE->type == TCP);
 115         g_assert(segment->inE->event.tcpEvent->segmentKey ==
 116                 segment->outE->event.tcpEvent->segmentKey);
 117
 118         segmentKey= segment->inE->event.tcpEvent->segmentKey;
 119
 120         convertIP(saddr, segmentKey->connectionKey.saddr);
 121         convertIP(daddr, segmentKey->connectionKey.daddr);
 122         g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u "
 123                 "ack: %u rst: %u syn: %u fin: %u", saddr,
 124                 segmentKey->connectionKey.source, daddr, segmentKey->connectionKey.dest,
 125                 segmentKey->tot_len, segmentKey->ihl, segmentKey->seq,
 126                 segmentKey->ack_seq, segmentKey->doff, segmentKey->ack, segmentKey->rst,
 127                 segmentKey->syn, segmentKey->fin);
 128 }
 129
 130
 131 /*
 132  * A GHashFunc for g_hash_table_new()
 133  *
 134  * This function is for indexing TCPEvents in unMatched lists. All fields of
 135  * the corresponding SegmentKey must match for two keys to be equal.
 136  *
 137  * Args:
 138  *   key           SegmentKey*
 139  *
 140  * Returns:
 141  *   A hash of all fields in the SegmentKey
 142  */
 143 guint ghfSegmentKeyHash(gconstpointer key)
 144 {
 145         const SegmentKey* p;
 146         uint32_t a, b, c;
 147
 148         p= (SegmentKey*) key;
 149
 150         a= p->connectionKey.source + (p->connectionKey.dest << 16);
 151         b= p->connectionKey.saddr;
 152         c= p->connectionKey.daddr;
 153         mix(a, b, c);
 154
 155         a+= p->ihl + (p->tot_len << 8) + (p->doff << 24);
 156         b+= p->seq;
 157         c+= p->ack_seq;
 158         mix(a, b, c);
 159
 160         a+= p->ack + (p->rst << 8) + (p->syn << 16) + (p->fin << 24);
 161         final(a, b, c);
 162
 163         g_debug("segment key hash %p: %u", p, c);
 164
 165         return c;
 166 }
 167
 168
 169 /*
 170  * A GEqualFunc for g_hash_table_new()
 171  *
 172  * This function is for indexing TCPEvents in unMatched lists. All fields of
 173  * the corresponding SegmentKey must match for two keys to be equal.
 174  *
 175  * Args:
 176  *   a, b          SegmentKey*
 177  *
 178  * Returns:
 179  *   TRUE if both values are equal
 180  */
 181 gboolean gefSegmentKeyEqual(gconstpointer a, gconstpointer b)
 182 {
 183         const SegmentKey* sA, * sB;
 184
 185         sA= (SegmentKey*) a;
 186         sB= (SegmentKey*) b;
 187
 188         if (connectionKeyEqual(&sA->connectionKey, &sB->connectionKey) &&
 189                 sA->ihl == sB->ihl &&
 190                 sA->tot_len == sB->tot_len &&
 191                 sA->seq == sB->seq &&
 192                 sA->ack_seq == sB->ack_seq &&
 193                 sA->doff == sB->doff &&
 194                 sA->ack == sB->ack &&
 195                 sA->rst == sB->rst &&
 196                 sA->syn == sB->syn &&
 197                 sA->fin == sB->fin)
 198         {
 199                 g_debug("segment key equal %p %p: TRUE", sA, sB);
 200                 return TRUE;
 201         }
 202         else
 203         {
 204                 g_debug("segment key equal %p %p: FALSE", sA, sB);
 205                 return FALSE;
 206         }
 207 }
 208
 209
 210 /*
 211  * A GDestroyNotify function for g_hash_table_new_full()
 212  *
 213  * Args:
 214  *   data:         Event*
 215  */
 216 void gdnDestroyEvent(gpointer data)
 217 {
 218         Event* event= data;
 219
 220         event->destroy(event);
 221 }
 222
 223
 224 /*
 225  * A GDestroyNotify function for g_hash_table_new_full()
 226  *
 227  * Args:
 228  *   data:         GQueue* list[Packet]
 229  */
 230 void gdnTCPSegmentListDestroy(gpointer data)
 231 {
 232         GQueue* list;
 233
 234         list= (GQueue*) data;
 235
 236         g_queue_foreach(list, &gfTCPSegmentDestroy, NULL);
 237         g_queue_free(list);
 238 }
 239
 240
 241 /*
 242  * A GFunc for g_queue_foreach()
 243  *
 244  * Args:
 245  *   data          Message*, TCP message to destroy
 246  *   user_data     NULL
 247  */
 248 void gfTCPSegmentDestroy(gpointer data, gpointer user_data)
 249 {
 250         destroyTCPSegment((Message*) data);
 251 }
 252
 253
 254 /*
 255  * Free the memory used by a TCP Message and the memory of all its associated
 256  * resources
 257  *
 258  * Args:
 259  *   segment       TCP Message to destroy
 260  */
 261 void destroyTCPSegment(Message* const segment)
 262 {
 263         TCPEvent* inE, *outE;
 264
 265         segment->print(segment);
 266
 267         g_assert(segment->inE != NULL && segment->outE != NULL);
 268         g_assert(segment->inE->type == TCP && segment->outE->type == TCP);
 269         inE= segment->inE->event.tcpEvent;
 270         outE= segment->outE->event.tcpEvent;
 271         g_assert(inE->segmentKey == outE->segmentKey);
 272
 273         outE->segmentKey= NULL;
 274
 275         destroyTCPEvent(segment->inE);
 276         destroyTCPEvent(segment->outE);
 277
 278         free(segment);
 279 }
 280
 281
 282 /*
 283  * Free the memory used by a TCP Exchange and the memory of SOME of its
 284  * associated resources. The message is not destroyed. Use destroyTCPSegment()
 285  * to free it.
 286  *
 287  * Args:
 288  *   exchange      TCP Exchange to destroy. The .message must be NULL
 289  */
 290 void destroyTCPExchange(Exchange* const exchange)
 291 {
 292         g_assert(exchange->message == NULL);
 293
 294         if (exchange->acks != NULL)
 295         {
 296                 g_queue_foreach(exchange->acks, &gfTCPSegmentDestroy, NULL);
 297                 g_queue_free(exchange->acks);
 298         }
 299
 300         free(exchange);
 301 }
 302
 303
 304 /*
 305  * Free the memory used by a TCP Event and its associated resources
 306  */
 307 void destroyTCPEvent(Event* const event)
 308 {
 309         g_assert(event->type == TCP);
 310
 311         if (event->event.tcpEvent->segmentKey != NULL)
 312         {
 313                 free(event->event.tcpEvent->segmentKey);
 314         }
 315         free(event->event.tcpEvent);
 316         event->event.tcpEvent= NULL;
 317         destroyEvent(event);
 318 }
 319
 320
 321 /*
 322  * Free the memory used by a base Event
 323  */
 324 void destroyEvent(Event* const event)
 325 {
 326         g_assert(event->event.tcpEvent == NULL);
 327
 328         free(event);
 329 }
 330
 331
 332 /*
 333  * Free the memory used by a UDP Event and its associated resources
 334  */
 335 void destroyUDPEvent(Event* const event)
 336 {
 337         g_assert(event->type == UDP);
 338
 339         if (event->event.udpEvent->datagramKey != NULL)
 340         {
 341                 free(event->event.udpEvent->datagramKey);
 342         }
 343         free(event->event.udpEvent);
 344         event->event.udpEvent= NULL;
 345         destroyEvent(event);
 346 }
 347
 348
 349 /*
 350  * A GCompareFunc for g_queue_find_custom()
 351  *
 352  * Args:
 353  *   a          Message* acked packet
 354  *   b          Message* ack packet
 355  *
 356  * Returns:
 357  *   0 if b acks a
 358  */
 359 gint gcfTCPSegmentAckCompare(gconstpointer a, gconstpointer b)
 360 {
 361         if (isAcking((const Message*) b, (const Message*) a))
 362         {
 363                 return 0;
 364         }
 365         else
 366         {
 367                 return 1;
 368         }
 369 }
 370
 371
 372 /*
 373  * A GHashFunc for g_hash_table_new()
 374  *
 375  * Hash TCP connection keys. Here are a few possible implementations:
 376  *
 377  * 2.4 kernels used tcp_hashfn()
 378  *
 379  * I've seen something about an XOR hash:
 380  * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
 381  * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
 382  * h ^= h >> 16;
 383  * h ^= h >> 8;
 384  * return h;
 385  *
 386  * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of
 387  * Jenkins hashing, jhash.h
 388  *
 389  * This function uses jenkins hashing. The hash is not the same for packets in
 390  * opposite directions of the same connection. (Hence the name
 391  * connection*key*hash)
 392  *
 393  * Args:
 394  *    key        ConnectionKey*
 395  */
 396 guint ghfConnectionKeyHash(gconstpointer key)
 397 {
 398         ConnectionKey* connectionKey;
 399         uint32_t a, b, c;
 400
 401         connectionKey= (ConnectionKey*) key;
 402
 403         a= connectionKey->source + (connectionKey->dest << 16);
 404         b= connectionKey->saddr;
 405         c= connectionKey->daddr;
 406         final(a, b, c);
 407
 408         return c;
 409 }
 410
 411
 412 /*
 413  * A GEqualFunc for g_hash_table_new()
 414  *
 415  * Args:
 416  *   a, b          ConnectionKey*
 417  *
 418  * Returns:
 419  *   TRUE if both values are equal
 420  */
 421 gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b)
 422 {
 423         // Two packets in the same direction
 424         if (connectionKeyEqual((const ConnectionKey*) a, (const ConnectionKey*) b))
 425         {
 426                 return TRUE;
 427         }
 428         else
 429         {
 430                 return FALSE;
 431         }
 432 }
 433
 434
 435 /*
 436  * A GDestroyNotify function for g_hash_table_new_full()
 437  *
 438  * Args:
 439  *   data:         ConnectionKey*
 440  */
 441 void gdnConnectionKeyDestroy(gpointer data)
 442 {
 443         free((ConnectionKey*) data);
 444 }
 445
 446
 447 /*
 448  * A GHashFunc for g_hash_table_new()
 449  *
 450  * Args:
 451  *    key        DatagramKey*
 452  */
 453 guint ghfDatagramKeyHash(gconstpointer key)
 454 {
 455         DatagramKey* datagramKey;
 456         union {
 457                 uint8_t byteKey[8];
 458                 uint32_t hashableKey[2];
 459         } dataKey;
 460         uint32_t a, b, c;
 461
 462         datagramKey= (DatagramKey*) key;
 463         memcpy(dataKey.byteKey, datagramKey->dataKey, sizeof(dataKey.byteKey));
 464
 465         a= datagramKey->saddr;
 466         b= datagramKey->daddr;
 467         c= datagramKey->source + (datagramKey->dest << 16);
 468         mix(a, b, c);
 469
 470         a+= datagramKey->ulen; // 16 bits left here
 471         b+= dataKey.hashableKey[0];
 472         c+= dataKey.hashableKey[1];
 473         final(a, b, c);
 474
 475         return c;
 476 }
 477
 478
 479 /*
 480  * A GEqualFunc for g_hash_table_new()
 481  *
 482  * Args:
 483  *   a, b          DatagramKey*
 484  *
 485  * Returns:
 486  *   TRUE if both values are equal
 487  */
 488 gboolean gefDatagramKeyEqual(gconstpointer a, gconstpointer b)
 489 {
 490         const DatagramKey* dA, * dB;
 491
 492         dA= (DatagramKey*) a;
 493         dB= (DatagramKey*) b;
 494
 495         if (dA->saddr == dB->saddr && dA->daddr == dB->daddr &&
 496                 dA->source == dB->source && dA->dest == dB->dest &&
 497                 dA->ulen == dB->ulen &&
 498                 memcmp(dA->dataKey, dB->dataKey, sizeof(dA->dataKey)) == 0)
 499         {
 500                 return TRUE;
 501         }
 502         else
 503         {
 504                 return FALSE;
 505         }
 506 }
 507
 508
 509 /*
 510  * A GDestroyNotify function for g_hash_table_new_full()
 511  *
 512  * Args:
 513  *   data:         DatagramKey*
 514  */
 515 void gdnDestroyDatagramKey(gpointer data)
 516 {
 517         free((DatagramKey*) data);
 518 }
 519
 520
 521 /*
 522  * A GDestroyNotify function for g_hash_table_new_full()
 523  *
 524  * Args:
 525  *   data:         Broadcast*
 526  */
 527 void gdnDestroyBroadcast(gpointer data)
 528 {
 529         destroyBroadcast((Broadcast*) data);
 530 }
 531
 532
 533 /*
 534  * Free a Broadcast struct and its associated ressources
 535  *
 536  * Args:
 537  *   broadcast:    Broadcast*
 538  */
 539 void destroyBroadcast(Broadcast* const broadcast)
 540 {
 541         g_queue_foreach(broadcast->events, &gfDestroyEvent, NULL);
 542         g_queue_free(broadcast->events);
 543         free(broadcast);
 544 }
 545
 546
 547 /*
 548  * A GFunc for g_queue_foreach()
 549  *
 550  * Args:
 551  *   data          Event*
 552  *   user_data     NULL
 553  */
 554 void gfDestroyEvent(gpointer data, gpointer user_data)
 555 {
 556         Event* event= data;
 557
 558         event->destroy(event);
 559 }
 560
 561
 562 /* Subtract two WallTime structs
 563  *
 564  * Args:
 565  *   tA, tB:       WallTime
 566  *
 567  * Returns:
 568  *   The result of tA - tB, as a double. This may incur a loss of
 569  *   precision.
 570  */
 571 double wallTimeSub(const WallTime const* tA, const WallTime const* tB)
 572 {
 573         return (double) tA->seconds - tB->seconds + ((double) tA->nanosec - tB->nanosec) / 1e9;
 574 }
 575
 576
 577 /*
 578  * Allocate and copy a base event
 579  *
 580  * Args:
 581  *   newEvent:     new event, pointer will be updated
 582  *   event:        event to copy
 583  */
 584 void copyEvent(const Event* const event, Event** const newEvent)
 585 {
 586         g_assert(event->event.tcpEvent == NULL);
 587
 588         *newEvent= malloc(sizeof(Event));
 589         memcpy(*newEvent, event, sizeof(Event));
 590 }
 591
 592
 593 /*
 594  * Allocate and copy a TCP event
 595  *
 596  * Args:
 597  *   newEvent:     new event, pointer will be updated
 598  *   event:        event to copy
 599  */
 600 void copyTCPEvent(const Event* const event, Event** const newEvent)
 601 {
 602         g_assert(event->type == TCP);
 603
 604         *newEvent= malloc(sizeof(Event));
 605         memcpy(*newEvent, event, sizeof(Event));
 606
 607         (*newEvent)->event.tcpEvent= malloc(sizeof(TCPEvent));
 608         memcpy((*newEvent)->event.tcpEvent, event->event.tcpEvent,
 609                 sizeof(TCPEvent));
 610
 611         (*newEvent)->event.tcpEvent->segmentKey= malloc(sizeof(SegmentKey));
 612         memcpy((*newEvent)->event.tcpEvent->segmentKey,
 613                 event->event.tcpEvent->segmentKey, sizeof(SegmentKey));
 614 }
 615
 616
 617 /*
 618  * Allocate and copy a UDP event
 619  *
 620  * Args:
 621  *   newEvent:     new event, pointer will be updated
 622  *   event:        event to copy
 623  */
 624 void copyUDPEvent(const Event* const event, Event** const newEvent)
 625 {
 626         g_assert(event->type == UDP);
 627
 628         *newEvent= malloc(sizeof(Event));
 629         memcpy(*newEvent, event, sizeof(Event));
 630
 631         (*newEvent)->event.udpEvent= malloc(sizeof(UDPEvent));
 632         memcpy((*newEvent)->event.udpEvent, event->event.udpEvent,
 633                 sizeof(UDPEvent));
 634
 635         (*newEvent)->event.udpEvent->datagramKey= malloc(sizeof(DatagramKey));
 636         memcpy((*newEvent)->event.udpEvent->datagramKey,
 637                 event->event.udpEvent->datagramKey, sizeof(DatagramKey));
 638 }
 639
 640
 641 /*
 642  * A GFunc for g_queue_foreach()
 643  *
 644  * Args:
 645  *   data          Event*, event to add
 646  *   user_data     GArray*, array to add to
 647  */
 648 void gfAddEventToArray(gpointer data, gpointer user_data)
 649 {
 650         g_array_append_val((GArray*) user_data, data);
 651 }