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_queue_foreach(list, &gfTCPSegmentDestroy, NULL);
 238         g_queue_free(list);
 239 }
 240
 241
 242 /*
 243  * A GFunc for g_queue_foreach()
 244  *
 245  * Args:
 246  *   data          Message*, TCP message to destroy
 247  *   user_data     NULL
 248  */
 249 void gfTCPSegmentDestroy(gpointer data, gpointer user_data)
 250 {
 251         destroyTCPSegment((Message*) data);
 252 }
 253
 254
 255 /*
 256  * Free the memory used by a TCP Message and the memory of all its associated
 257  * resources
 258  *
 259  * Args:
 260  *   segment       TCP Message to destroy
 261  */
 262 void destroyTCPSegment(Message* const segment)
 263 {
 264         TCPEvent* inE, *outE;
 265
 266         segment->print(segment);
 267
 268         g_assert(segment->inE != NULL && segment->outE != NULL);
 269         g_assert(segment->inE->type == TCP && segment->outE->type == TCP);
 270         inE= segment->inE->event.tcpEvent;
 271         outE= segment->outE->event.tcpEvent;
 272         g_assert(inE->segmentKey == outE->segmentKey);
 273
 274         outE->segmentKey= NULL;
 275
 276         destroyTCPEvent(segment->inE);
 277         destroyTCPEvent(segment->outE);
 278
 279         free(segment);
 280 }
 281
 282
 283 /*
 284  * Free the memory used by a TCP Exchange and the memory of SOME of its
 285  * associated resources. The message is not destroyed. Use destroyTCPSegment()
 286  * to free it.
 287  *
 288  * Args:
 289  *   exchange      TCP Exchange to destroy. The .message must be NULL
 290  */
 291 void destroyTCPExchange(Exchange* const exchange)
 292 {
 293         g_assert(exchange->message == NULL);
 294
 295         if (exchange->acks != NULL)
 296         {
 297                 g_queue_foreach(exchange->acks, &gfTCPSegmentDestroy, NULL);
 298                 g_queue_free(exchange->acks);
 299         }
 300
 301         free(exchange);
 302 }
 303
 304
 305 /*
 306  * Free the memory used by a TCP Event and its associated resources
 307  */
 308 void destroyTCPEvent(Event* const event)
 309 {
 310         g_assert(event->type == TCP);
 311
 312         if (event->event.tcpEvent->segmentKey != NULL)
 313         {
 314                 free(event->event.tcpEvent->segmentKey);
 315         }
 316         free(event->event.tcpEvent);
 317         event->event.tcpEvent= NULL;
 318         destroyEvent(event);
 319 }
 320
 321
 322 /*
 323  * Free the memory used by a base Event
 324  */
 325 void destroyEvent(Event* const event)
 326 {
 327         g_assert(event->event.tcpEvent == NULL);
 328
 329         free(event);
 330 }
 331
 332
 333 /*
 334  * Free the memory used by a UDP Event and its associated resources
 335  */
 336 void destroyUDPEvent(Event* const event)
 337 {
 338         g_assert(event->type == UDP);
 339
 340         if (event->event.udpEvent->datagramKey != NULL)
 341         {
 342                 free(event->event.udpEvent->datagramKey);
 343         }
 344         free(event->event.udpEvent);
 345         event->event.udpEvent= NULL;
 346         destroyEvent(event);
 347 }
 348
 349
 350 /*
 351  * A GCompareFunc for g_queue_find_custom()
 352  *
 353  * Args:
 354  *   a          Message* acked packet
 355  *   b          Message* ack packet
 356  *
 357  * Returns:
 358  *   0 if b acks a
 359  */
 360 gint gcfTCPSegmentAckCompare(gconstpointer a, gconstpointer b)
 361 {
 362         if (isAcking((const Message*) b, (const Message*) a))
 363         {
 364                 return 0;
 365         }
 366         else
 367         {
 368                 return 1;
 369         }
 370 }
 371
 372
 373 /*
 374  * A GHashFunc for g_hash_table_new()
 375  *
 376  * Hash TCP connection keys. Here are a few possible implementations:
 377  *
 378  * 2.4 kernels used tcp_hashfn()
 379  *
 380  * I've seen something about an XOR hash:
 381  * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
 382  * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
 383  * h ^= h >> 16;
 384  * h ^= h >> 8;
 385  * return h;
 386  *
 387  * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of
 388  * Jenkins hashing, jhash.h
 389  *
 390  * This function uses jenkins hashing. The hash is not the same for packets in
 391  * opposite directions of the same connection. (Hence the name
 392  * connection*key*hash)
 393  *
 394  * Args:
 395  *    key        ConnectionKey*
 396  */
 397 guint ghfConnectionKeyHash(gconstpointer key)
 398 {
 399         ConnectionKey* connectionKey;
 400         uint32_t a, b, c;
 401
 402         connectionKey= (ConnectionKey*) key;
 403
 404         a= connectionKey->source + (connectionKey->dest << 16);
 405         b= connectionKey->saddr;
 406         c= connectionKey->daddr;
 407         final(a, b, c);
 408
 409         return c;
 410 }
 411
 412
 413 /*
 414  * A GEqualFunc for g_hash_table_new()
 415  *
 416  * Args:
 417  *   a, b          ConnectionKey*
 418  *
 419  * Returns:
 420  *   TRUE if both values are equal
 421  */
 422 gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b)
 423 {
 424         // Two packets in the same direction
 425         if (connectionKeyEqual((const ConnectionKey*) a, (const ConnectionKey*) b))
 426         {
 427                 return TRUE;
 428         }
 429         else
 430         {
 431                 return FALSE;
 432         }
 433 }
 434
 435
 436 /*
 437  * A GDestroyNotify function for g_hash_table_new_full()
 438  *
 439  * Args:
 440  *   data:         ConnectionKey*
 441  */
 442 void gdnConnectionKeyDestroy(gpointer data)
 443 {
 444         free((ConnectionKey*) data);
 445 }
 446
 447
 448 /*
 449  * A GHashFunc for g_hash_table_new()
 450  *
 451  * Args:
 452  *    key        DatagramKey*
 453  */
 454 guint ghfDatagramKeyHash(gconstpointer key)
 455 {
 456         DatagramKey* datagramKey;
 457         uint32_t a, b, c;
 458
 459         datagramKey= (DatagramKey*) key;
 460
 461         a= datagramKey->saddr;
 462         b= datagramKey->daddr;
 463         c= datagramKey->source + (datagramKey->dest << 16);
 464         mix(a, b, c);
 465
 466         a+= datagramKey->ulen; // 16 bits left here
 467         b+= *((uint32_t*) datagramKey->dataKey);
 468         c+= *((uint32_t*) ((void*) datagramKey->dataKey + 4));
 469         final(a, b, c);
 470
 471         return c;
 472 }
 473
 474
 475 /*
 476  * A GEqualFunc for g_hash_table_new()
 477  *
 478  * Args:
 479  *   a, b          DatagramKey*
 480  *
 481  * Returns:
 482  *   TRUE if both values are equal
 483  */
 484 gboolean gefDatagramKeyEqual(gconstpointer a, gconstpointer b)
 485 {
 486         const DatagramKey* dA, * dB;
 487
 488         dA= (DatagramKey*) a;
 489         dB= (DatagramKey*) b;
 490
 491         if (dA->saddr == dB->saddr && dA->daddr == dB->daddr &&
 492                 dA->source == dB->source && dA->dest == dB->dest &&
 493                 dA->ulen == dB->ulen &&
 494                 memcmp(dA->dataKey, dB->dataKey, sizeof(dA->dataKey)) == 0)
 495         {
 496                 return TRUE;
 497         }
 498         else
 499         {
 500                 return FALSE;
 501         }
 502 }
 503
 504
 505 /*
 506  * A GDestroyNotify function for g_hash_table_new_full()
 507  *
 508  * Args:
 509  *   data:         DatagramKey*
 510  */
 511 void gdnDestroyDatagramKey(gpointer data)
 512 {
 513         free((DatagramKey*) data);
 514 }
 515
 516
 517 /*
 518  * A GDestroyNotify function for g_hash_table_new_full()
 519  *
 520  * Args:
 521  *   data:         Broadcast*
 522  */
 523 void gdnDestroyBroadcast(gpointer data)
 524 {
 525         destroyBroadcast((Broadcast*) data);
 526 }
 527
 528
 529 /*
 530  * Free a Broadcast struct and its associated ressources
 531  *
 532  * Args:
 533  *   broadcast:    Broadcast*
 534  */
 535 void destroyBroadcast(Broadcast* const broadcast)
 536 {
 537         g_queue_foreach(broadcast->events, &gfDestroyEvent, NULL);
 538         g_queue_free(broadcast->events);
 539         free(broadcast);
 540 }
 541
 542
 543 /*
 544  * A GFunc for g_queue_foreach()
 545  *
 546  * Args:
 547  *   data          Event*
 548  *   user_data     NULL
 549  */
 550 void gfDestroyEvent(gpointer data, gpointer user_data)
 551 {
 552         Event* event= data;
 553
 554         event->destroy(event);
 555 }
 556
 557
 558 /* Subtract two WallTime structs
 559  *
 560  * Args:
 561  *   tA, tB:       WallTime
 562  *
 563  * Returns:
 564  *   The result of tA - tB, as a double. This may incur a loss of
 565  *   precision.
 566  */
 567 double wallTimeSub(const WallTime const* tA, const WallTime const* tB)
 568 {
 569         return (double) tA->seconds - tB->seconds + ((double) tA->nanosec - tB->nanosec) / 1e9;
 570 }
 571
 572
 573 /*
 574  * Allocate and copy a base event
 575  *
 576  * Args:
 577  *   newEvent:     new event, pointer will be updated
 578  *   event:        event to copy
 579  */
 580 void copyEvent(const Event* const event, Event** const newEvent)
 581 {
 582         g_assert(event->event.tcpEvent == NULL);
 583
 584         *newEvent= malloc(sizeof(Event));
 585         memcpy(*newEvent, event, sizeof(Event));
 586 }
 587
 588
 589 /*
 590  * Allocate and copy a TCP event
 591  *
 592  * Args:
 593  *   newEvent:     new event, pointer will be updated
 594  *   event:        event to copy
 595  */
 596 void copyTCPEvent(const Event* const event, Event** const newEvent)
 597 {
 598         g_assert(event->type == TCP);
 599
 600         *newEvent= malloc(sizeof(Event));
 601         memcpy(*newEvent, event, sizeof(Event));
 602
 603         (*newEvent)->event.tcpEvent= malloc(sizeof(TCPEvent));
 604         memcpy((*newEvent)->event.tcpEvent, event->event.tcpEvent,
 605                 sizeof(TCPEvent));
 606
 607         (*newEvent)->event.tcpEvent->segmentKey= malloc(sizeof(SegmentKey));
 608         memcpy((*newEvent)->event.tcpEvent->segmentKey,
 609                 event->event.tcpEvent->segmentKey, sizeof(SegmentKey));
 610 }
 611
 612
 613 /*
 614  * Allocate and copy a UDP event
 615  *
 616  * Args:
 617  *   newEvent:     new event, pointer will be updated
 618  *   event:        event to copy
 619  */
 620 void copyUDPEvent(const Event* const event, Event** const newEvent)
 621 {
 622         g_assert(event->type == UDP);
 623
 624         *newEvent= malloc(sizeof(Event));
 625         memcpy(*newEvent, event, sizeof(Event));
 626
 627         (*newEvent)->event.udpEvent= malloc(sizeof(UDPEvent));
 628         memcpy((*newEvent)->event.udpEvent, event->event.udpEvent,
 629                 sizeof(UDPEvent));
 630
 631         (*newEvent)->event.udpEvent->datagramKey= malloc(sizeof(DatagramKey));
 632         memcpy((*newEvent)->event.udpEvent->datagramKey,
 633                 event->event.udpEvent->datagramKey, sizeof(DatagramKey));
 634 }
 635
 636
 637 /*
 638  * A GFunc for g_queue_foreach()
 639  *
 640  * Args:
 641  *   data          Event*, event to add
 642  *   user_data     GArray*, array to add to
 643  */
 644 void gfAddEventToArray(gpointer data, gpointer user_data)
 645 {
 646         g_array_append_val((GArray*) user_data, data);
 647 }