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