lttv/lttv/sync/data_structures_tcp.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 "lookup3.h"
  31
  32 #include "data_structures_tcp.h"
  33
  34
  35 #ifndef g_info
  36 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
  37 #endif
  38
  39 // TCP sequence numbers use clock arithmetic, these comparison functions take
  40 // that into account
  41 #define SEQ_LT(a,b)     ((int32_t)((a)-(b)) < 0)
  42 #define SEQ_LEQ(a,b)    ((int32_t)((a)-(b)) <= 0)
  43 #define SEQ_GT(a,b)     ((int32_t)((a)-(b)) > 0)
  44 #define SEQ_GEQ(a,b)    ((int32_t)((a)-(b)) >= 0)
  45
  46
  47 /*
  48  * Compare two ConnectionKey structures
  49  *
  50  * Returns:
  51  *   true if each field of the structure is equal
  52  *   false otherwise
  53  */
  54 bool connectionKeyEqual(const ConnectionKey* const a, const
  55         ConnectionKey* const b)
  56 {
  57         if (a->saddr == b->saddr && a->daddr == b->daddr && a->source == b->source
  58                 && a->dest == b->dest)
  59         {
  60                 return true;
  61         }
  62         else
  63         {
  64                 return false;
  65         }
  66 }
  67
  68
  69 /*
  70  * Check if a packet is an acknowledge of another packet.
  71  *
  72  * Args:
  73  *   ackPacket     packet that is the confirmation
  74  *   ackedPacket   packet that contains the original data, both packets have to
  75  *                 come from the same direction of the same connection
  76  */
  77 bool isAcking(const Packet* const ackPacket, const Packet* const
  78         ackedPacket)
  79 {
  80         if (SEQ_GT(ackPacket->inE->packetKey->ack_seq,
  81                         ackedPacket->inE->packetKey->seq))
  82     {
  83         return true;
  84     }
  85     else
  86     {
  87         return false;
  88     }
  89 }
  90
  91
  92 /*
  93  * Convert an IP address from 32 bit form to dotted quad
  94  *
  95  * Args:
  96  *   str:          A preallocated string of length >= 17
  97  *   addr:         Address
  98  */
  99 void convertIP(char* const str, const uint32_t addr)
 100 {
 101         struct in_addr iaddr;
 102
 103         iaddr.s_addr= htonl(addr);
 104         strcpy(str, inet_ntoa(iaddr));
 105 }
 106
 107
 108 /*
 109  * Print the content of a Packet structure
 110  */
 111 void printPacket(const Packet* const packet)
 112 {
 113         char saddr[17], daddr[17];
 114         PacketKey* packetKey;
 115
 116         packetKey= packet->inE->packetKey;
 117
 118         convertIP(saddr, packetKey->connectionKey.saddr);
 119         convertIP(daddr, packetKey->connectionKey.daddr);
 120         g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u "
 121                 "ack: %u rst: %u syn: %u fin: %u", saddr,
 122                 packetKey->connectionKey.source, daddr, packetKey->connectionKey.dest,
 123                 packetKey->tot_len, packetKey->ihl, packetKey->seq,
 124                 packetKey->ack_seq, packetKey->doff, packetKey->ack, packetKey->rst,
 125                 packetKey->syn, packetKey->fin);
 126 }
 127
 128
 129 /*
 130  * A GHashFunc for g_hash_table_new()
 131  *
 132  * This function is for indexing netEvents in unMatched lists. All fields of
 133  * the corresponding packet must match for two keys to be equal.
 134  *
 135  * Args:
 136  *    key        PacketKey*
 137  */
 138 guint ghfPacketKeyHash(gconstpointer key)
 139 {
 140         const PacketKey* p;
 141         uint32_t a, b, c;
 142
 143         p= (PacketKey*) key;
 144
 145         a= p->connectionKey.source + (p->connectionKey.dest << 16);
 146         b= p->connectionKey.saddr;
 147         c= p->connectionKey.daddr;
 148         mix(a, b, c);
 149
 150         a+= p->ihl + (p->tot_len << 8) + (p->doff << 24);
 151         b+= p->seq;
 152         c+= p->ack_seq;
 153         mix(a, b, c);
 154
 155         a+= p->ack + (p->rst << 8) + (p->syn << 16) + (p->fin << 24);
 156         final(a, b, c);
 157
 158         return c;
 159 }
 160
 161
 162 /*
 163  * A GEqualFunc for g_hash_table_new()
 164  *
 165  * This function is for indexing netEvents in unMatched lists. All fields of
 166  * the corresponding packet must match for two keys to be equal.
 167  *
 168  * Args:
 169  *   a, b          PacketKey*
 170  *
 171  * Returns:
 172  *   TRUE if both values are equal
 173  */
 174 gboolean gefPacketKeyEqual(gconstpointer a, gconstpointer b)
 175 {
 176         const PacketKey* pA, * pB;
 177
 178         pA= ((PacketKey*) a);
 179         pB= ((PacketKey*) b);
 180
 181         if (connectionKeyEqual(&pA->connectionKey, &pB->connectionKey) &&
 182                 pA->ihl == pB->ihl &&
 183                 pA->tot_len == pB->tot_len &&
 184                 pA->seq == pB->seq &&
 185                 pA->ack_seq == pB->ack_seq &&
 186                 pA->doff == pB->doff &&
 187                 pA->ack == pB->ack &&
 188                 pA->rst == pB->rst &&
 189                 pA->syn == pB->syn &&
 190                 pA->fin == pB->fin)
 191         {
 192                 return TRUE;
 193         }
 194         else
 195         {
 196                 return FALSE;
 197         }
 198 }
 199
 200
 201 /*
 202  * A GDestroyNotify function for g_hash_table_new_full()
 203  *
 204  * Args:
 205  *   data:         NetEvent*
 206  */
 207 void gdnDestroyNetEvent(gpointer data)
 208 {
 209         destroyNetEvent((NetEvent*) data);
 210 }
 211
 212
 213 /*
 214  * A GDestroyNotify function for g_hash_table_new_full()
 215  *
 216  * Args:
 217  *   data:         GQueue* list[Packet]
 218  */
 219 void gdnPacketListDestroy(gpointer data)
 220 {
 221         GQueue* list;
 222
 223         list= (GQueue*) data;
 224
 225         g_debug("XXXX gdnPacketListDestroy\n");
 226
 227         g_queue_foreach(list, &gfPacketDestroy, NULL);
 228         g_queue_free(list);
 229 }
 230
 231
 232 /*
 233  * A GFunc for g_queue_foreach()
 234  *
 235  * Args:
 236  *   data          Packet*, packet to destroy
 237  *   user_data     NULL
 238  */
 239 void gfPacketDestroy(gpointer data, gpointer user_data)
 240 {
 241         g_debug("XXXX gfPacketDestroy\n");
 242         destroyPacket((Packet*) data);
 243 }
 244
 245
 246 /*
 247  * Free the memory used by a Packet and the memory of all its associated
 248  * resources
 249  */
 250 void destroyPacket(Packet* const packet)
 251 {
 252         g_debug("XXXX destroyPacket ");
 253         printPacket(packet);
 254         g_debug("\n");
 255
 256         g_assert(packet->inE != NULL && packet->outE != NULL &&
 257                 packet->inE->packetKey == packet->outE->packetKey);
 258
 259         packet->outE->packetKey= NULL;
 260
 261         destroyNetEvent(packet->inE);
 262         destroyNetEvent(packet->outE);
 263
 264         if (packet->acks != NULL)
 265         {
 266                 g_queue_foreach(packet->acks, &gfPacketDestroy, NULL);
 267                 g_queue_free(packet->acks);
 268         }
 269
 270         free(packet);
 271 }
 272
 273
 274 /*
 275  * Free the memory used by a NetEvent
 276  */
 277 void destroyNetEvent(NetEvent* const event)
 278 {
 279         g_debug("XXXX destroyNetEvent\n");
 280
 281         if (event->packetKey != NULL)
 282         {
 283                 free(event->packetKey);
 284         }
 285         free(event);
 286 }
 287
 288
 289 /*
 290  * A GCompareFunc for g_queue_find_custom()
 291  *
 292  * Args:
 293  *   a          Packet* acked packet
 294  *   b          Packet* ack packet
 295  *
 296  * Returns:
 297  *   0 if b acks a
 298  */
 299 gint gcfPacketAckCompare(gconstpointer a, gconstpointer b)
 300 {
 301         if (isAcking((const Packet*) b, (const Packet*) a))
 302         {
 303                 return 0;
 304         }
 305         else
 306         {
 307                 return 1;
 308         }
 309 }
 310
 311
 312 /*
 313  * A GHashFunc for g_hash_table_new()
 314  *
 315  * Hash TCP connection keys. Here are a few possible implementations:
 316  *
 317  * 2.4 kernels used tcp_hashfn()
 318  *
 319  * I've seen something about an XOR hash:
 320  * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
 321  * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
 322  * h ^= h >> 16;
 323  * h ^= h >> 8;
 324  * return h;
 325  *
 326  * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of
 327  * Jenkins hashing, jhash.h
 328  *
 329  * This function uses jenkins hashing. The hash is not the same for packets in
 330  * opposite directions of the same connection. (Hence the name
 331  * connection*key*hash)
 332  *
 333  * Args:
 334  *    key        ConnectionKey*
 335  */
 336 guint ghfConnectionKeyHash(gconstpointer key)
 337 {
 338         ConnectionKey* connectionKey;
 339         uint32_t a, b, c;
 340
 341         connectionKey= (ConnectionKey*) key;
 342
 343         a= connectionKey->source + (connectionKey->dest << 16);
 344         b= connectionKey->saddr;
 345         c= connectionKey->daddr;
 346         final(a, b, c);
 347
 348         return c;
 349 }
 350
 351
 352 /*
 353  * A GEqualFunc for g_hash_table_new()
 354  *
 355  * Args:
 356  *   a, b          ConnectionKey*
 357  *
 358  * Returns:
 359  *   TRUE if both values are equal
 360  */
 361 gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b)
 362 {
 363         // Two packets in the same direction
 364         if (connectionKeyEqual((const ConnectionKey*) a, (const ConnectionKey*) b))
 365         {
 366                 return TRUE;
 367         }
 368         else
 369         {
 370                 return FALSE;
 371         }
 372 }
 373
 374
 375 /*
 376  * A GDestroyNotify function for g_hash_table_new_full()
 377  *
 378  * Args:
 379  *   data:         ConnectionKey*
 380  */
 381 void gdnConnectionKeyDestroy(gpointer data)
 382 {
 383         free((ConnectionKey*) data);
 384 }
 385