lttv/lttv/sync/data_structures.c

   1 /* This file is part of the Linux Trace Toolkit viewer
   2  * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License Version 2 as
   6  * published by the Free Software Foundation;
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  16  * MA 02111-1307, USA.
  17  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include <config.h>
  21 #endif
  22
  23 #include <arpa/inet.h>
  24 #include <glib.h>
  25 #include <stdint.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include <unistd.h>
  31
  32 #include "lookup3.h"
  33
  34 #include "data_structures.h"
  35
  36
  37 // TCP sequence numbers use clock arithmetic, these comparison functions take
  38 // that into account
  39 #define SEQ_LT(a,b)     ((int32_t)((a)-(b)) < 0)
  40 #define SEQ_LEQ(a,b)    ((int32_t)((a)-(b)) <= 0)
  41 #define SEQ_GT(a,b)     ((int32_t)((a)-(b)) > 0)
  42 #define SEQ_GEQ(a,b)    ((int32_t)((a)-(b)) >= 0)
  43
  44
  45 /*
  46  * Compare two ConnectionKey structures
  47  *
  48  * Returns:
  49  *   true if each field of the structure is equal
  50  *   false otherwise
  51  */
  52 bool connectionKeyEqual(const ConnectionKey* const a, const
  53         ConnectionKey* const b)
  54 {
  55         if (a->saddr == b->saddr && a->daddr == b->daddr && a->source == b->source
  56                 && a->dest == b->dest)
  57         {
  58                 return true;
  59         }
  60         else
  61         {
  62                 return false;
  63         }
  64 }
  65
  66
  67 /*
  68  * Check if a packet is an acknowledge of another packet.
  69  *
  70  * Args:
  71  *   ackSegment    packet that is the confirmation
  72  *   ackedSegment  packet that contains the original data, both packets have to
  73  *                 come from the same direction of the same connection. Both
  74  *                 messages have to contain TCP events.
  75  */
  76 bool isAcking(const Message* const ackSegment, const Message* const
  77         ackedSegment)
  78 {
  79         g_assert(ackSegment->inE->type == TCP);
  80         g_assert(ackSegment->outE->type == TCP);
  81
  82         if (SEQ_GT(ackSegment->inE->event.tcpEvent->segmentKey->ack_seq,
  83                         ackedSegment->inE->event.tcpEvent->segmentKey->seq))
  84     {
  85         return true;
  86     }
  87     else
  88     {
  89         return false;
  90     }
  91 }
  92
  93
  94 /*
  95  * Convert an IP address from 32 bit form to dotted quad
  96  *
  97  * Args:
  98  *   str:          A preallocated string of length >= 16
  99  *   addr:         Address
 100  */
 101 void convertIP(char* const str, const uint32_t addr)
 102 {
 103         strcpy(str, inet_ntoa((struct in_addr) {.s_addr= addr}));
 104 }
 105
 106
 107 /*
 108  * Print the content of a TCP Message structure
 109  */
 110 void printTCPSegment(const Message* const segment)
 111 {
 112         char saddr[16], daddr[16];
 113         SegmentKey* segmentKey;
 114
 115         g_assert(segment->inE->type == TCP);
 116         g_assert(segment->inE->event.tcpEvent->segmentKey ==
 117                 segment->outE->event.tcpEvent->segmentKey);
 118
 119         segmentKey= segment->inE->event.tcpEvent->segmentKey;
 120
 121         convertIP(saddr, segmentKey->connectionKey.saddr);
 122         convertIP(daddr, segmentKey->connectionKey.daddr);
 123         g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u "
 124                 "ack: %u rst: %u syn: %u fin: %u", saddr,
 125                 segmentKey->connectionKey.source, daddr, segmentKey->connectionKey.dest,
 126                 segmentKey->tot_len, segmentKey->ihl, segmentKey->seq,
 127                 segmentKey->ack_seq, segmentKey->doff, segmentKey->ack, segmentKey->rst,
 128                 segmentKey->syn, segmentKey->fin);
 129 }
 130
 131
 132 /*
 133  * A GHashFunc for g_hash_table_new()
 134  *
 135  * This function is for indexing TCPEvents in unMatched lists. All fields of
 136  * the corresponding SegmentKey must match for two keys to be equal.
 137  *
 138  * Args:
 139  *   key           SegmentKey*
 140  *
 141  * Returns:
 142  *   A hash of all fields in the SegmentKey
 143  */
 144 guint ghfSegmentKeyHash(gconstpointer key)
 145 {
 146         const SegmentKey* p;
 147         uint32_t a, b, c;
 148
 149         p= (SegmentKey*) key;
 150
 151         a= p->connectionKey.source + (p->connectionKey.dest << 16);
 152         b= p->connectionKey.saddr;
 153         c= p->connectionKey.daddr;
 154         mix(a, b, c);
 155
 156         a+= p->ihl + (p->tot_len << 8) + (p->doff << 24);
 157         b+= p->seq;
 158         c+= p->ack_seq;
 159         mix(a, b, c);
 160
 161         a+= p->ack + (p->rst << 8) + (p->syn << 16) + (p->fin << 24);
 162         final(a, b, c);
 163
 164         g_debug("segment key hash %p: %u", p, c);
 165
 166         return c;
 167 }
 168
 169
 170 /*
 171  * A GEqualFunc for g_hash_table_new()
 172  *
 173  * This function is for indexing TCPEvents in unMatched lists. All fields of
 174  * the corresponding SegmentKey must match for two keys to be equal.
 175  *
 176  * Args:
 177  *   a, b          SegmentKey*
 178  *
 179  * Returns:
 180  *   TRUE if both values are equal
 181  */
 182 gboolean gefSegmentKeyEqual(gconstpointer a, gconstpointer b)
 183 {
 184         const SegmentKey* sA, * sB;
 185
 186         sA= (SegmentKey*) a;
 187         sB= (SegmentKey*) b;
 188
 189         if (connectionKeyEqual(&sA->connectionKey, &sB->connectionKey) &&
 190                 sA->ihl == sB->ihl &&
 191                 sA->tot_len == sB->tot_len &&
 192                 sA->seq == sB->seq &&
 193                 sA->ack_seq == sB->ack_seq &&
 194                 sA->doff == sB->doff &&
 195                 sA->ack == sB->ack &&
 196                 sA->rst == sB->rst &&
 197                 sA->syn == sB->syn &&
 198                 sA->fin == sB->fin)
 199         {
 200                 g_debug("segment key equal %p %p: TRUE", sA, sB);
 201                 return TRUE;
 202         }
 203         else
 204         {
 205                 g_debug("segment key equal %p %p: FALSE", sA, sB);
 206                 return FALSE;
 207         }
 208 }
 209
 210
 211 /*
 212  * A GDestroyNotify function for g_hash_table_new_full()
 213  *
 214  * Args:
 215  *   data:         Event*
 216  */
 217 void gdnDestroyEvent(gpointer data)
 218 {
 219         Event* event= data;
 220
 221         event->destroy(event);
 222 }
 223
 224
 225 /*
 226  * A GDestroyNotify function for g_hash_table_new_full()
 227  *
 228  * Args:
 229  *   data:         GQueue* list[Packet]
 230  */
 231 void gdnTCPSegmentListDestroy(gpointer data)
 232 {
 233         GQueue* list;
 234
 235         list= (GQueue*) data;
 236
 237         g_debug("XXXX gdnTCPSegmentListDestroy\n");
 238
 239         g_queue_foreach(list, &gfTCPSegmentDestroy, NULL);
 240         g_queue_free(list);
 241 }
 242
 243
 244 /*
 245  * A GFunc for g_queue_foreach()
 246  *
 247  * Args:
 248  *   data          Message*, TCP message to destroy
 249  *   user_data     NULL
 250  */
 251 void gfTCPSegmentDestroy(gpointer data, gpointer user_data)
 252 {
 253         g_debug("XXXX gfTCPSegmentDestroy\n");
 254         destroyTCPSegment((Message*) data);
 255 }
 256
 257
 258 /*
 259  * Free the memory used by a TCP Message and the memory of all its associated
 260  * resources
 261  *
 262  * Args:
 263  *   segment       TCP Message to destroy
 264  */
 265 void destroyTCPSegment(Message* const segment)
 266 {
 267         TCPEvent* inE, *outE;
 268
 269         g_debug("XXXX destroyTCPSegment");
 270         segment->print(segment);
 271
 272         g_assert(segment->inE != NULL && segment->outE != NULL);
 273         g_assert(segment->inE->type == TCP && segment->outE->type == TCP);
 274         inE= segment->inE->event.tcpEvent;
 275         outE= segment->outE->event.tcpEvent;
 276         g_assert(inE->segmentKey == outE->segmentKey);
 277
 278         outE->segmentKey= NULL;
 279
 280         destroyTCPEvent(segment->inE);
 281         destroyTCPEvent(segment->outE);
 282
 283         free(segment);
 284 }
 285
 286
 287 /*
 288  * Free the memory used by a TCP Exchange and the memory of SOME of its
 289  * associated resources. The message is not destroyed. Use destroyTCPSegment()
 290  * to free it.
 291  *
 292  * Args:
 293  *   exchange      TCP Exchange to destroy. The .message must be NULL
 294  */
 295 void destroyTCPExchange(Exchange* const exchange)
 296 {
 297         g_assert(exchange->message == NULL);
 298
 299         if (exchange->acks != NULL)
 300         {
 301                 g_queue_foreach(exchange->acks, &gfTCPSegmentDestroy, NULL);
 302                 g_queue_free(exchange->acks);
 303         }
 304
 305         free(exchange);
 306 }
 307
 308
 309 /*
 310  * Free the memory used by a TCP Event and its associated resources
 311  */
 312 void destroyTCPEvent(Event* const event)
 313 {
 314         g_assert(event->type == TCP);
 315
 316         if (event->event.tcpEvent->segmentKey != NULL)
 317         {
 318                 free(event->event.tcpEvent->segmentKey);
 319         }
 320         free(event->event.tcpEvent);
 321         event->event.tcpEvent= NULL;
 322         destroyEvent(event);
 323 }
 324
 325
 326 /*
 327  * Free the memory used by a base Event
 328  */
 329 void destroyEvent(Event* const event)
 330 {
 331         g_assert(event->event.tcpEvent == NULL);
 332
 333         free(event);
 334 }
 335
 336
 337 /*
 338  * Free the memory used by a UDP Event and its associated resources
 339  */
 340 void destroyUDPEvent(Event* const event)
 341 {
 342         g_assert(event->type == UDP);
 343
 344         if (event->event.udpEvent->datagramKey != NULL)
 345         {
 346                 free(event->event.udpEvent->datagramKey);
 347         }
 348         free(event->event.udpEvent);
 349         event->event.udpEvent= NULL;
 350         destroyEvent(event);
 351 }
 352
 353
 354 /*
 355  * A GCompareFunc for g_queue_find_custom()
 356  *
 357  * Args:
 358  *   a          Message* acked packet
 359  *   b          Message* ack packet
 360  *
 361  * Returns:
 362  *   0 if b acks a
 363  */
 364 gint gcfTCPSegmentAckCompare(gconstpointer a, gconstpointer b)
 365 {
 366         if (isAcking((const Message*) b, (const Message*) a))
 367         {
 368                 return 0;
 369         }
 370         else
 371         {
 372                 return 1;
 373         }
 374 }
 375
 376
 377 /*
 378  * A GHashFunc for g_hash_table_new()
 379  *
 380  * Hash TCP connection keys. Here are a few possible implementations:
 381  *
 382  * 2.4 kernels used tcp_hashfn()
 383  *
 384  * I've seen something about an XOR hash:
 385  * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
 386  * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
 387  * h ^= h >> 16;
 388  * h ^= h >> 8;
 389  * return h;
 390  *
 391  * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of
 392  * Jenkins hashing, jhash.h
 393  *
 394  * This function uses jenkins hashing. The hash is not the same for packets in
 395  * opposite directions of the same connection. (Hence the name
 396  * connection*key*hash)
 397  *
 398  * Args:
 399  *    key        ConnectionKey*
 400  */
 401 guint ghfConnectionKeyHash(gconstpointer key)
 402 {
 403         ConnectionKey* connectionKey;
 404         uint32_t a, b, c;
 405
 406         connectionKey= (ConnectionKey*) key;
 407
 408         a= connectionKey->source + (connectionKey->dest << 16);
 409         b= connectionKey->saddr;
 410         c= connectionKey->daddr;
 411         final(a, b, c);
 412
 413         return c;
 414 }
 415
 416
 417 /*
 418  * A GEqualFunc for g_hash_table_new()
 419  *
 420  * Args:
 421  *   a, b          ConnectionKey*
 422  *
 423  * Returns:
 424  *   TRUE if both values are equal
 425  */
 426 gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b)
 427 {
 428         // Two packets in the same direction
 429         if (connectionKeyEqual((const ConnectionKey*) a, (const ConnectionKey*) b))
 430         {
 431                 return TRUE;
 432         }
 433         else
 434         {
 435                 return FALSE;
 436         }
 437 }
 438
 439
 440 /*
 441  * A GDestroyNotify function for g_hash_table_new_full()
 442  *
 443  * Args:
 444  *   data:         ConnectionKey*
 445  */
 446 void gdnConnectionKeyDestroy(gpointer data)
 447 {
 448         free((ConnectionKey*) data);
 449 }
 450
 451
 452 /*
 453  * A GHashFunc for g_hash_table_new()
 454  *
 455  * Args:
 456  *    key        DatagramKey*
 457  */
 458 guint ghfDatagramKeyHash(gconstpointer key)
 459 {
 460         DatagramKey* datagramKey;
 461         uint32_t a, b, c;
 462
 463         datagramKey= (DatagramKey*) key;
 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+= *((uint32_t*) datagramKey->dataKey);
 472         c+= *((uint32_t*) ((void*) datagramKey->dataKey + 4));
 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 }