reassemble.c

   1 /* reassemble.c
   2  * Routines for {fragment,segment} reassembly
   3  *
   4  * $Id: reassemble.c,v 1.2 2001/06/28 19:15:11 guy Exp $
   5  *
   6  * Ethereal - Network traffic analyzer
   7  * By Gerald Combs <gerald@ethereal.com>
   8  * Copyright 1998 Gerald Combs
   9  *
  10  * This program is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU General Public License
  12  * as published by the Free Software Foundation; either version 2
  13  * of the License, or (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  23  */
  24
  25 #ifdef HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include <string.h>
  30
  31 #include "packet.h"
  32
  33 #include "reassemble.h"
  34
  35 typedef struct _fragment_key {
  36         address src;
  37         address dst;
  38         guint32 id;
  39 } fragment_key;
  40
  41 static GMemChunk *fragment_key_chunk = NULL;
  42 static GMemChunk *fragment_data_chunk = NULL;
  43 static int fragment_init_count = 200;
  44
  45 #define LINK_FRAG(fd_head,fd)                                   \
  46         {       fragment_data *fd_i;                            \
  47                 /* add fragment to list, keep list sorted */            \
  48                 for(fd_i=fd_head;fd_i->next;fd_i=fd_i->next){   \
  49                         if( (fd->offset) < (fd_i->next->offset) )       \
  50                                 break;                                  \
  51                 }                                                       \
  52                 fd->next=fd_i->next;                            \
  53                 fd_i->next=fd;                                  \
  54         }
  55
  56
  57 static gint
  58 fragment_equal(gconstpointer k1, gconstpointer k2)
  59 {
  60         fragment_key* key1 = (fragment_key*) k1;
  61         fragment_key* key2 = (fragment_key*) k2;
  62
  63         return ( ( (ADDRESSES_EQUAL(&key1->src, &key2->src)) &&
  64                    (ADDRESSES_EQUAL(&key1->dst, &key2->dst)) &&
  65                    (key1->id    == key2->id)
  66                  ) ?
  67                  TRUE : FALSE);
  68 }
  69
  70 static guint
  71 fragment_hash(gconstpointer k)
  72 {
  73         fragment_key* key = (fragment_key*) k;
  74         guint hash_val;
  75         int i;
  76
  77         hash_val = 0;
  78         for (i = 0; i < key->src.len; i++)
  79                 hash_val += key->src.data[i];
  80         for (i = 0; i < key->dst.len; i++)
  81                 hash_val += key->dst.data[i];
  82         hash_val += key->id;
  83
  84         return hash_val;
  85 }
  86
  87 /*
  88  * For a hash table entry, free the address data to which the key refers
  89  * and the fragment data to which the value refers.
  90  * (The actual key and value structures get freed by "reassemble_init()".)
  91  */
  92 static gboolean
  93 free_all_fragments(gpointer key_arg, gpointer value, gpointer user_data)
  94 {
  95         fragment_key *key = key_arg;
  96         fragment_data *fd_head;
  97
  98         /*
  99          * Grr.  I guess the theory here is that freeing
 100          * something sure as heck modifies it, so you
 101          * want to ban attempts to free it, but, alas,
 102          * if we make the "data" field of an "address"
 103          * structure not a "const", the compiler whines if
 104          * we try to make it point into the data for a packet,
 105          * as that's a "const" array (and should be, as dissectors
 106          * shouldn't trash it).
 107          *
 108          * So we cast the complaint into oblivion, and rely on
 109          * the fact that these addresses are known to have had
 110          * their data mallocated, i.e. they don't point into,
 111          * say, the middle of the data for a packet.
 112          */
 113         g_free((gpointer)key->src.data);
 114         g_free((gpointer)key->dst.data);
 115
 116         for (fd_head = value; fd_head != NULL; fd_head = fd_head->next) {
 117                 if (fd_head->data)
 118                         g_free(fd_head->data);
 119         }
 120
 121         return TRUE;
 122 }
 123
 124 /*
 125  * Initialize a fragment table.
 126  */
 127 void
 128 fragment_table_init(GHashTable **fragment_table)
 129 {
 130         if (*fragment_table != NULL) {
 131                 /*
 132                  * The fragment hash table exists.
 133                  *
 134                  * Remove all entries and free fragment data for
 135                  * each entry.  (The key and value data is freed
 136                  * by "reassemble_init()".)
 137                  */
 138                 g_hash_table_foreach_remove(*fragment_table,
 139                                 free_all_fragments, NULL);
 140         } else {
 141                 /* The fragment table does not exist. Create it */
 142                 *fragment_table = g_hash_table_new(fragment_hash,
 143                                 fragment_equal);
 144         }
 145 }
 146
 147 /*
 148  * Free up all space allocated for fragment keys and data.
 149  */
 150 void
 151 reassemble_init(void)
 152 {
 153         if (fragment_key_chunk != NULL)
 154                 g_mem_chunk_destroy(fragment_key_chunk);
 155         if (fragment_data_chunk != NULL)
 156                 g_mem_chunk_destroy(fragment_data_chunk);
 157         fragment_key_chunk = g_mem_chunk_new("fragment_key_chunk",
 158             sizeof(fragment_key),
 159             fragment_init_count * sizeof(fragment_key),
 160             G_ALLOC_ONLY);
 161         fragment_data_chunk = g_mem_chunk_new("fragment_data_chunk",
 162             sizeof(fragment_data),
 163             fragment_init_count * sizeof(fragment_data),
 164             G_ALLOC_ONLY);
 165 }
 166
 167 /*
 168  * This function adds a new fragment to the fragment hash table.
 169  * If this is the first fragment seen for this datagram, a new entry
 170  * is created in the hash table, otherwise this fragment is just added
 171  * to the linked list of fragments for this packet.
 172  * The list of fragments for a specific datagram is kept sorted for
 173  * easier handling.
 174  *
 175  * Returns a pointer to the head of the fragment data list if we have all the
 176  * fragments, NULL otherwise.
 177  */
 178 fragment_data *
 179 fragment_add(tvbuff_t *tvb, int offset, packet_info *pinfo, guint32 id,
 180              GHashTable *fragment_table, guint32 frag_offset,
 181              guint32 frag_data_len, gboolean more_frags)
 182 {
 183         fragment_key key, *new_key;
 184         fragment_data *fd_head;
 185         fragment_data *fd;
 186         fragment_data *fd_i;
 187         guint32 max, dfpos;
 188
 189         /* create key to search hash with */
 190         key.src = pinfo->src;
 191         key.dst = pinfo->dst;
 192         key.id  = id;
 193
 194         fd_head = g_hash_table_lookup(fragment_table, &key);
 195
 196         /* have we already seen this frame ?*/
 197         if (pinfo->fd->flags.visited) {
 198                 if (fd_head != NULL && fd_head->flags & FD_DEFRAGMENTED) {
 199                         return fd_head;
 200                 } else {
 201                         return NULL;
 202                 }
 203         }
 204
 205         if (fd_head==NULL){
 206                 /* not found, this must be the first snooped fragment for this
 207                  * packet. Create list-head.
 208                  */
 209                 fd_head=g_mem_chunk_alloc(fragment_data_chunk);
 210                 /* head/first structure in list only holds no other data than
 211                  * 'datalen' then we don't have to change the head of the list
 212                  * even if we want to keep it sorted
 213                  */
 214                 fd_head->next=NULL;
 215                 fd_head->datalen=0;
 216                 fd_head->offset=0;
 217                 fd_head->len=0;
 218                 fd_head->flags=0;
 219                 fd_head->data=NULL;
 220
 221                 /*
 222                  * We're going to use the key to insert the fragment,
 223                  * so allocate a structure for it, and copy the
 224                  * addresses, allocating new buffers for the address
 225                  * data.
 226                  */
 227                 new_key = g_mem_chunk_alloc(fragment_key_chunk);
 228                 COPY_ADDRESS(&new_key->src, &key.src);
 229                 COPY_ADDRESS(&new_key->dst, &key.dst);
 230                 new_key->id = key.id;
 231                 g_hash_table_insert(fragment_table, new_key, fd_head);
 232         }
 233
 234         /* create new fd describing this fragment */
 235         fd = g_mem_chunk_alloc(fragment_data_chunk);
 236         fd->next = NULL;
 237         fd->flags = 0;
 238         fd->frame = pinfo->fd->num;
 239         fd->offset = frag_offset;
 240         fd->len  = frag_data_len;
 241         fd->data = NULL;
 242
 243         if (!more_frags) {
 244                 /*
 245                  * This is the tail fragment in the sequence.
 246                  */
 247                 if (fd_head->datalen) {
 248                         /* ok we have already seen other tails for this packet
 249                          * it might be a duplicate.
 250                          */
 251                         if (fd_head->datalen != (fd->offset + fd->len) ){
 252                                 /* Oops, this tail indicates a different packet
 253                                  * len than the previous ones. Somethings wrong
 254                                  */
 255                                 fd->flags      |= FD_MULTIPLETAILS;
 256                                 fd_head->flags |= FD_MULTIPLETAILS;
 257                         }
 258                 } else {
 259                         /* this was the first tail fragment, now we know the
 260                          * length of the packet
 261                          */
 262                         fd_head->datalen = fd->offset + fd->len;
 263                 }
 264         }
 265
 266
 267
 268
 269         /* If the packet is already defragmented, this MUST be an overlap.
 270          * The entire defragmented packet is in fd_head->data
 271          * Even if we have previously defragmented this packet, we still check
 272          * check it. Someone might play overlap and TTL games.
 273          */
 274         if (fd_head->flags & FD_DEFRAGMENTED) {
 275                 fd->flags      |= FD_OVERLAP;
 276                 fd_head->flags |= FD_OVERLAP;
 277                 /* make sure its not too long */
 278                 if (fd->offset + fd->len > fd_head->datalen) {
 279                         fd->flags      |= FD_TOOLONGFRAGMENT;
 280                         fd_head->flags |= FD_TOOLONGFRAGMENT;
 281                         LINK_FRAG(fd_head,fd);
 282                         return (fd_head);
 283                 }
 284                 /* make sure it doesnt conflict with previous data */
 285                 if ( memcmp(fd_head->data+fd->offset,
 286                         tvb_get_ptr(tvb,offset,fd->len),fd->len) ){
 287                         fd->flags      |= FD_OVERLAPCONFLICT;
 288                         fd_head->flags |= FD_OVERLAPCONFLICT;
 289                         LINK_FRAG(fd_head,fd);
 290                         return (fd_head);
 291                 }
 292                 /* it was just an overlap, link it and return */
 293                 LINK_FRAG(fd_head,fd);
 294                 return (fd_head);
 295         }
 296
 297
 298
 299         /* If we have reached this point, the packet is not defragmented yet.
 300          * Save all payload in a buffer until we can defragment.
 301          * XXX - what if we didn't capture the entire fragment due
 302          * to a too-short snapshot length?
 303          */
 304         fd->data = g_malloc(fd->len);
 305         tvb_memcpy(tvb, fd->data, offset, fd->len);
 306         LINK_FRAG(fd_head,fd);
 307
 308
 309         if( !(fd_head->datalen) ){
 310                 /* if we dont know the datalen, there are still missing
 311                  * packets. Cheaper than the check below.
 312                  */
 313                 return NULL;
 314         }
 315
 316
 317         /* check if we have received the entire fragment
 318          * this is easy since the list is sorted and the head is faked.
 319          */
 320         max = 0;
 321         for (fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 322                 if ( ((fd_i->offset)<=max) &&
 323                     ((fd_i->offset+fd_i->len)>max) ){
 324                         max = fd_i->offset+fd_i->len;
 325                 }
 326         }
 327
 328         if (max < (fd_head->datalen)) {
 329                 /* we have not received all packets yet */
 330                 return NULL;
 331         }
 332
 333
 334         if (max > (fd_head->datalen)) {
 335                 /* oops, too long fragment detected */
 336                 fd->flags      |= FD_TOOLONGFRAGMENT;
 337                 fd_head->flags |= FD_TOOLONGFRAGMENT;
 338         }
 339
 340
 341         /* we have received an entire packet, defragment it and
 342          * free all fragments
 343          */
 344         fd_head->data = g_malloc(max);
 345
 346         /* add all data fragments */
 347         for (dfpos=0,fd_i=fd_head;fd_i;fd_i=fd_i->next) {
 348                 if (fd_i->len) {
 349                         if (fd_i->offset < dfpos) {
 350                                 fd_i->flags    |= FD_OVERLAP;
 351                                 fd_head->flags |= FD_OVERLAP;
 352                                 if ( memcmp(fd_head->data+fd_i->offset,
 353                                         fd_i->data,
 354                                         MIN(fd_i->len,(dfpos-fd_i->offset))
 355                                         ) ){
 356                                         fd_i->flags    |= FD_OVERLAPCONFLICT;
 357                                         fd_head->flags |= FD_OVERLAPCONFLICT;
 358                                 }
 359                         }
 360                         memcpy(fd_head->data+fd_i->offset,fd_i->data,fd_i->len);
 361                         g_free(fd_i->data);
 362                         fd_i->data=NULL;
 363
 364                         dfpos=MAX(dfpos,(fd_i->offset+fd_i->len));
 365                 }
 366         }
 367
 368         /* mark this packet as defragmented.
 369            allows us to skip any trailing fragments */
 370         fd_head->flags |= FD_DEFRAGMENTED;
 371
 372         return fd_head;
 373 }