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 >= 17
 103  *   addr:         Address
 104  */
 105 void convertIP(char* const str, const uint32_t addr)
 106 {
 107         struct in_addr iaddr;
 108
 109         iaddr.s_addr= htonl(addr);
 110         strcpy(str, inet_ntoa(iaddr));
 111 }
 112
 113
 114 /*
 115  * Print the content of a TCP Message structure
 116  */
 117 void printTCPSegment(const Message* const segment)
 118 {
 119         char saddr[17], daddr[17];
 120         SegmentKey* segmentKey;
 121
 122         g_assert(segment->inE->type == TCP);
 123         g_assert(segment->inE->event.tcpEvent->segmentKey ==
 124                 segment->outE->event.tcpEvent->segmentKey);
 125
 126         segmentKey= segment->inE->event.tcpEvent->segmentKey;
 127
 128         convertIP(saddr, segmentKey->connectionKey.saddr);
 129         convertIP(daddr, segmentKey->connectionKey.daddr);
 130         g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u "
 131                 "ack: %u rst: %u syn: %u fin: %u", saddr,
 132                 segmentKey->connectionKey.source, daddr, segmentKey->connectionKey.dest,
 133                 segmentKey->tot_len, segmentKey->ihl, segmentKey->seq,
 134                 segmentKey->ack_seq, segmentKey->doff, segmentKey->ack, segmentKey->rst,
 135                 segmentKey->syn, segmentKey->fin);
 136 }
 137
 138
 139 /*
 140  * A GHashFunc for g_hash_table_new()
 141  *
 142  * This function is for indexing TCPEvents in unMatched lists. All fields of
 143  * the corresponding SegmentKey must match for two keys to be equal.
 144  *
 145  * Args:
 146  *   key           SegmentKey*
 147  *
 148  * Returns:
 149  *   A hash of all fields in the SegmentKey
 150  */
 151 guint ghfSegmentKeyHash(gconstpointer key)
 152 {
 153         const SegmentKey* p;
 154         uint32_t a, b, c;
 155
 156         p= (SegmentKey*) key;
 157
 158         a= p->connectionKey.source + (p->connectionKey.dest << 16);
 159         b= p->connectionKey.saddr;
 160         c= p->connectionKey.daddr;
 161         mix(a, b, c);
 162
 163         a+= p->ihl + (p->tot_len << 8) + (p->doff << 24);
 164         b+= p->seq;
 165         c+= p->ack_seq;
 166         mix(a, b, c);
 167
 168         a+= p->ack + (p->rst << 8) + (p->syn << 16) + (p->fin << 24);
 169         final(a, b, c);
 170
 171         g_debug("segment key hash %p: %u", p, c);
 172
 173         return c;
 174 }
 175
 176
 177 /*
 178  * A GEqualFunc for g_hash_table_new()
 179  *
 180  * This function is for indexing TCPEvents in unMatched lists. All fields of
 181  * the corresponding SegmentKey must match for two keys to be equal.
 182  *
 183  * Args:
 184  *   a, b          SegmentKey*
 185  *
 186  * Returns:
 187  *   TRUE if both values are equal
 188  */
 189 gboolean gefSegmentKeyEqual(gconstpointer a, gconstpointer b)
 190 {
 191         const SegmentKey* sA, * sB;
 192
 193         sA= (SegmentKey*) a;
 194         sB= (SegmentKey*) b;
 195
 196         if (connectionKeyEqual(&sA->connectionKey, &sB->connectionKey) &&
 197                 sA->ihl == sB->ihl &&
 198                 sA->tot_len == sB->tot_len &&
 199                 sA->seq == sB->seq &&
 200                 sA->ack_seq == sB->ack_seq &&
 201                 sA->doff == sB->doff &&
 202                 sA->ack == sB->ack &&
 203                 sA->rst == sB->rst &&
 204                 sA->syn == sB->syn &&
 205                 sA->fin == sB->fin)
 206         {
 207                 g_debug("segment key equal %p %p: TRUE", sA, sB);
 208                 return TRUE;
 209         }
 210         else
 211         {
 212                 g_debug("segment key equal %p %p: FALSE", sA, sB);
 213                 return FALSE;
 214         }
 215 }
 216
 217
 218 /*
 219  * A GDestroyNotify function for g_hash_table_new_full()
 220  *
 221  * Args:
 222  *   data:         Event*
 223  */
 224 void gdnDestroyEvent(gpointer data)
 225 {
 226         Event* event= data;
 227
 228         event->destroy(event);
 229 }
 230
 231
 232 /*
 233  * A GDestroyNotify function for g_hash_table_new_full()
 234  *
 235  * Args:
 236  *   data:         GQueue* list[Packet]
 237  */
 238 void gdnTCPSegmentListDestroy(gpointer data)
 239 {
 240         GQueue* list;
 241
 242         list= (GQueue*) data;
 243
 244         g_debug("XXXX gdnTCPSegmentListDestroy\n");
 245
 246         g_queue_foreach(list, &gfTCPSegmentDestroy, NULL);
 247         g_queue_free(list);
 248 }
 249
 250
 251 /*
 252  * A GFunc for g_queue_foreach()
 253  *
 254  * Args:
 255  *   data          Message*, TCP message to destroy
 256  *   user_data     NULL
 257  */
 258 void gfTCPSegmentDestroy(gpointer data, gpointer user_data)
 259 {
 260         g_debug("XXXX gfTCPSegmentDestroy\n");
 261         destroyTCPSegment((Message*) data);
 262 }
 263
 264
 265 /*
 266  * Free the memory used by a TCP Message and the memory of all its associated
 267  * resources
 268  *
 269  * Args:
 270  *   segment       TCP Message to destroy
 271  */
 272 void destroyTCPSegment(Message* const segment)
 273 {
 274         TCPEvent* inE, *outE;
 275
 276         g_debug("XXXX destroyTCPSegment");
 277         segment->print(segment);
 278
 279         g_assert(segment->inE != NULL && segment->outE != NULL);
 280         g_assert(segment->inE->type == TCP && segment->outE->type == TCP);
 281         inE= segment->inE->event.tcpEvent;
 282         outE= segment->outE->event.tcpEvent;
 283         g_assert(inE->segmentKey == outE->segmentKey);
 284
 285         outE->segmentKey= NULL;
 286
 287         destroyTCPEvent(segment->inE);
 288         destroyTCPEvent(segment->outE);
 289
 290         free(segment);
 291 }
 292
 293
 294 /*
 295  * Free the memory used by a TCP Exchange and the memory of SOME of its
 296  * associated resources. The message is not destroyed. Use destroyTCPSegment()
 297  * to free it.
 298  *
 299  * Args:
 300  *   exchange      TCP Exchange to destroy. The .message must be NULL
 301  */
 302 void destroyTCPExchange(Exchange* const exchange)
 303 {
 304         g_assert(exchange->message == NULL);
 305
 306         if (exchange->acks != NULL)
 307         {
 308                 g_queue_foreach(exchange->acks, &gfTCPSegmentDestroy, NULL);
 309                 g_queue_free(exchange->acks);
 310         }
 311
 312         free(exchange);
 313 }
 314
 315
 316 /*
 317  * Free the memory used by a TCP Event and its associated resources
 318  */
 319 void destroyTCPEvent(Event* const event)
 320 {
 321         g_assert(event->type == TCP);
 322
 323         if (event->event.tcpEvent->segmentKey != NULL)
 324         {
 325                 free(event->event.tcpEvent->segmentKey);
 326         }
 327         free(event->event.tcpEvent);
 328         event->event.tcpEvent= NULL;
 329         destroyEvent(event);
 330 }
 331
 332 /*
 333  * Free the memory used by a base Event
 334  */
 335 void destroyEvent(Event* const event)
 336 {
 337         g_assert(event->event.tcpEvent == NULL);
 338
 339         free(event);
 340 }
 341
 342
 343 /*
 344  * Free the memory used by a UDP Event and its associated resources
 345  */
 346 void destroyUDPEvent(Event* const event)
 347 {
 348         g_assert(event->type == UDP);
 349
 350         if (event->event.udpEvent->datagramKey != NULL)
 351         {
 352                 free(event->event.udpEvent->datagramKey);
 353         }
 354         free(event->event.udpEvent);
 355         event->event.udpEvent= NULL;
 356         destroyEvent(event);
 357 }
 358
 359
 360 /*
 361  * A GCompareFunc for g_queue_find_custom()
 362  *
 363  * Args:
 364  *   a          Message* acked packet
 365  *   b          Message* ack packet
 366  *
 367  * Returns:
 368  *   0 if b acks a
 369  */
 370 gint gcfTCPSegmentAckCompare(gconstpointer a, gconstpointer b)
 371 {
 372         if (isAcking((const Message*) b, (const Message*) a))
 373         {
 374                 return 0;
 375         }
 376         else
 377         {
 378                 return 1;
 379         }
 380 }
 381
 382
 383 /*
 384  * A GHashFunc for g_hash_table_new()
 385  *
 386  * Hash TCP connection keys. Here are a few possible implementations:
 387  *
 388  * 2.4 kernels used tcp_hashfn()
 389  *
 390  * I've seen something about an XOR hash:
 391  * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
 392  * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
 393  * h ^= h >> 16;
 394  * h ^= h >> 8;
 395  * return h;
 396  *
 397  * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of
 398  * Jenkins hashing, jhash.h
 399  *
 400  * This function uses jenkins hashing. The hash is not the same for packets in
 401  * opposite directions of the same connection. (Hence the name
 402  * connection*key*hash)
 403  *
 404  * Args:
 405  *    key        ConnectionKey*
 406  */
 407 guint ghfConnectionKeyHash(gconstpointer key)
 408 {
 409         ConnectionKey* connectionKey;
 410         uint32_t a, b, c;
 411
 412         connectionKey= (ConnectionKey*) key;
 413
 414         a= connectionKey->source + (connectionKey->dest << 16);
 415         b= connectionKey->saddr;
 416         c= connectionKey->daddr;
 417         final(a, b, c);
 418
 419         return c;
 420 }
 421
 422
 423 /*
 424  * A GEqualFunc for g_hash_table_new()
 425  *
 426  * Args:
 427  *   a, b          ConnectionKey*
 428  *
 429  * Returns:
 430  *   TRUE if both values are equal
 431  */
 432 gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b)
 433 {
 434         // Two packets in the same direction
 435         if (connectionKeyEqual((const ConnectionKey*) a, (const ConnectionKey*) b))
 436         {
 437                 return TRUE;
 438         }
 439         else
 440         {
 441                 return FALSE;
 442         }
 443 }
 444
 445
 446 /*
 447  * A GDestroyNotify function for g_hash_table_new_full()
 448  *
 449  * Args:
 450  *   data:         ConnectionKey*
 451  */
 452 void gdnConnectionKeyDestroy(gpointer data)
 453 {
 454         free((ConnectionKey*) data);
 455 }