reassemble.c

   1 /* reassemble.c
   2  * Routines for {fragment,segment} reassembly
   3  *
   4  * $Id: reassemble.c,v 1.21 2002/06/07 10:17:21 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 <epan/packet.h>
  32
  33 #include "reassemble.h"
  34
  35
  36 typedef struct _fragment_key {
  37         address src;
  38         address dst;
  39         guint32 id;
  40 } fragment_key;
  41
  42 static GMemChunk *fragment_key_chunk = NULL;
  43 static GMemChunk *fragment_data_chunk = NULL;
  44 static int fragment_init_count = 200;
  45
  46 #define LINK_FRAG(fd_head,fd)                                   \
  47         {       fragment_data *fd_i;                            \
  48                 /* add fragment to list, keep list sorted */            \
  49                 for(fd_i=(fd_head);fd_i->next;fd_i=fd_i->next){ \
  50                         if( ((fd)->offset) < (fd_i->next->offset) )     \
  51                                 break;                                  \
  52                 }                                                       \
  53                 (fd)->next=fd_i->next;                          \
  54                 fd_i->next=(fd);                                        \
  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         /*key.id is the first item to compare since item is most
  64           likely to differ between sessions, thus shortcircuiting
  65           the comparasion of addresses.
  66         */
  67         return ( ( (key1->id    == key2->id) &&
  68                    (ADDRESSES_EQUAL(&key1->src, &key2->src)) &&
  69                    (ADDRESSES_EQUAL(&key1->dst, &key2->dst))
  70                  ) ?
  71                  TRUE : FALSE);
  72 }
  73
  74 static guint
  75 fragment_hash(gconstpointer k)
  76 {
  77         fragment_key* key = (fragment_key*) k;
  78         guint hash_val;
  79 /*
  80         int i;
  81 */
  82
  83         hash_val = 0;
  84
  85 /*      More than likely: in most captures src and dst addresses are the
  86         same, and would hash the same.
  87         We only use id as the hash as an optimization.
  88
  89         for (i = 0; i < key->src.len; i++)
  90                 hash_val += key->src.data[i];
  91         for (i = 0; i < key->dst.len; i++)
  92                 hash_val += key->dst.data[i];
  93 */
  94
  95         hash_val += key->id;
  96
  97         return hash_val;
  98 }
  99
 100 /*
 101  * XXX - we use the frame_data structure for a frame as the key
 102  * structure, with the frame number as the item compared.
 103  *
 104  * This won't work if there's more than one form of reassembly using
 105  * the reassembled-packet hash tables going on in the frame, and two
 106  * or more are using the same protocol and thus the same hash table.
 107  *
 108  * We could use the addresses, or the reassembly ID, to distinguish
 109  * between the reassemblies, if necessary.
 110  *
 111  * Hopefully, we won't see anything perverse such as that (say, some
 112  * form of IP-in-IP tunneling, with fragments of an IP datagram
 113  * tunneled inside IP datagrams that are themselves fragmented).
 114  */
 115 static gint
 116 reassembled_equal(gconstpointer k1, gconstpointer k2)
 117 {
 118         frame_data* key1 = (frame_data*) k1;
 119         frame_data* key2 = (frame_data*) k2;
 120
 121         return (key1->num == key2->num);
 122 }
 123
 124 static guint
 125 reassembled_hash(gconstpointer k)
 126 {
 127         frame_data* key = (frame_data*) k;
 128
 129         return key->num;
 130 }
 131
 132 /*
 133  * For a fragment hash table entry, free the address data to which the key
 134  * refers and the fragment data to which the value refers.
 135  * (The actual key and value structures get freed by "reassemble_init()".)
 136  */
 137 static gboolean
 138 free_all_fragments(gpointer key_arg, gpointer value, gpointer user_data _U_)
 139 {
 140         fragment_key *key = key_arg;
 141         fragment_data *fd_head;
 142
 143         /*
 144          * Grr.  I guess the theory here is that freeing
 145          * something sure as heck modifies it, so you
 146          * want to ban attempts to free it, but, alas,
 147          * if we make the "data" field of an "address"
 148          * structure not a "const", the compiler whines if
 149          * we try to make it point into the data for a packet,
 150          * as that's a "const" array (and should be, as dissectors
 151          * shouldn't trash it).
 152          *
 153          * So we cast the complaint into oblivion, and rely on
 154          * the fact that these addresses are known to have had
 155          * their data mallocated, i.e. they don't point into,
 156          * say, the middle of the data for a packet.
 157          */
 158         g_free((gpointer)key->src.data);
 159         g_free((gpointer)key->dst.data);
 160
 161         for (fd_head = value; fd_head != NULL; fd_head = fd_head->next) {
 162                 if(fd_head->data && !(fd_head->flags&FD_NOT_MALLOCED))
 163                         g_free(fd_head->data);
 164         }
 165
 166         return TRUE;
 167 }
 168
 169 /*
 170  * For a reassembled-packet hash table entry, free the fragment data
 171  * to which the value refers.
 172  * (The actual value structures get freed by "reassemble_init()".)
 173  */
 174 static gboolean
 175 free_all_reassembled_fragments(gpointer key_arg _U_, gpointer value,
 176                                gpointer user_data _U_)
 177 {
 178         fragment_data *fd_head;
 179
 180         for (fd_head = value; fd_head != NULL; fd_head = fd_head->next) {
 181                 if(fd_head->data && !(fd_head->flags&FD_NOT_MALLOCED))
 182                         g_free(fd_head->data);
 183         }
 184
 185         return TRUE;
 186 }
 187
 188 /*
 189  * Initialize a fragment table.
 190  */
 191 void
 192 fragment_table_init(GHashTable **fragment_table)
 193 {
 194         if (*fragment_table != NULL) {
 195                 /*
 196                  * The fragment hash table exists.
 197                  *
 198                  * Remove all entries and free fragment data for
 199                  * each entry.  (The key and value data is freed
 200                  * by "reassemble_init()".)
 201                  */
 202                 g_hash_table_foreach_remove(*fragment_table,
 203                                 free_all_fragments, NULL);
 204         } else {
 205                 /* The fragment table does not exist. Create it */
 206                 *fragment_table = g_hash_table_new(fragment_hash,
 207                                 fragment_equal);
 208         }
 209 }
 210
 211 /*
 212  * Initialize a reassembled-packet table.
 213  */
 214 void
 215 reassembled_table_init(GHashTable **reassembled_table)
 216 {
 217         if (*reassembled_table != NULL) {
 218                 /*
 219                  * The reassembled-packet hash table exists.
 220                  *
 221                  * Remove all entries and free fragment data for
 222                  * each entry.  (The key and value data is freed
 223                  * by "reassemble_init()".)
 224                  */
 225                 g_hash_table_foreach_remove(*reassembled_table,
 226                                 free_all_reassembled_fragments, NULL);
 227         } else {
 228                 /* The fragment table does not exist. Create it */
 229                 *reassembled_table = g_hash_table_new(reassembled_hash,
 230                                 reassembled_equal);
 231         }
 232 }
 233
 234 /*
 235  * Free up all space allocated for fragment keys and data.
 236  */
 237 void
 238 reassemble_init(void)
 239 {
 240         if (fragment_key_chunk != NULL)
 241                 g_mem_chunk_destroy(fragment_key_chunk);
 242         if (fragment_data_chunk != NULL)
 243                 g_mem_chunk_destroy(fragment_data_chunk);
 244         fragment_key_chunk = g_mem_chunk_new("fragment_key_chunk",
 245             sizeof(fragment_key),
 246             fragment_init_count * sizeof(fragment_key),
 247             G_ALLOC_AND_FREE);
 248         fragment_data_chunk = g_mem_chunk_new("fragment_data_chunk",
 249             sizeof(fragment_data),
 250             fragment_init_count * sizeof(fragment_data),
 251             G_ALLOC_ONLY);
 252
 253 }
 254
 255 /* This function cleans up the stored state and removes the reassembly data and
 256  * (with one exception) all allocated memory for matching reassembly.
 257  *
 258  * The exception is :
 259  * If the PDU was already completely reassembled, then the buffer containing the
 260  * reassembled data WILL NOT be free()d, and the pointer to that buffer will be
 261  * returned.
 262  * Othervise the function will return NULL.
 263  *
 264  * So, if you call fragment_delete and it returns non-NULL, YOU are responsible to
 265  * g_free() that buffer.
 266  */
 267 unsigned char *
 268 fragment_delete(packet_info *pinfo, guint32 id, GHashTable *fragment_table)
 269 {
 270         fragment_data *fd_head, *fd;
 271         fragment_key key;
 272         unsigned char *data=NULL;
 273
 274         /* create key to search hash with */
 275         key.src = pinfo->src;
 276         key.dst = pinfo->dst;
 277         key.id  = id;
 278
 279         fd_head = g_hash_table_lookup(fragment_table, &key);
 280
 281         if(fd_head==NULL){
 282                 /* We do not recognize this as a PDU we have seen before. return*/
 283                 return NULL;
 284         }
 285
 286         data=fd_head->data;
 287         /* loop over all partial fragments and free any buffers */
 288         for(fd=fd_head->next;fd;){
 289                 fragment_data *tmp_fd;
 290                 tmp_fd=fd->next;
 291
 292                 if( !(fd->flags&FD_NOT_MALLOCED) )
 293                         g_free(fd->data);
 294                 g_mem_chunk_free(fragment_data_chunk, fd);
 295                 fd=tmp_fd;
 296         }
 297         g_mem_chunk_free(fragment_data_chunk, fd_head);
 298         g_hash_table_remove(fragment_table, &key);
 299
 300         return data;
 301 }
 302
 303 /* This function is used to check if there is partial or completed reassembly state
 304  * matching this packet. I.e. Are there reassembly going on or not for this packet?
 305  */
 306 fragment_data *
 307 fragment_get(packet_info *pinfo, guint32 id, GHashTable *fragment_table)
 308 {
 309         fragment_data *fd_head;
 310         fragment_key key;
 311
 312         /* create key to search hash with */
 313         key.src = pinfo->src;
 314         key.dst = pinfo->dst;
 315         key.id  = id;
 316
 317         fd_head = g_hash_table_lookup(fragment_table, &key);
 318
 319         return fd_head;
 320 }
 321
 322 /* This function can be used to explicitely set the total length (if known)
 323  * for reassembly of a PDU.
 324  * This is useful for reassembly of PDUs where one may have the total length specified
 325  * in the first fragment instead of as for, say, IPv4 where a flag indicates which
 326  * is the last fragment.
 327  *
 328  * Such protocols might fragment_add with a more_frags==TRUE for every fragment
 329  * and just tell the reassembly engine the expected total length of the reassembled data
 330  * using fragment_set_tot_len immediately after doing fragment_add for the first packet.
 331  *
 332  * note that for FD_BLOCKSEQUENCE tot_len is the index for the tail fragment.
 333  * i.e. since the block numbers start at 0, if we specify tot_len==2, that
 334  * actually means we want to defragment 3 blocks, block 0, 1 and 2.
 335  */
 336 void
 337 fragment_set_tot_len(packet_info *pinfo, guint32 id, GHashTable *fragment_table,
 338                      guint32 tot_len)
 339 {
 340         fragment_data *fd_head;
 341         fragment_key key;
 342
 343         /* create key to search hash with */
 344         key.src = pinfo->src;
 345         key.dst = pinfo->dst;
 346         key.id  = id;
 347
 348         fd_head = g_hash_table_lookup(fragment_table, &key);
 349
 350         if(fd_head){
 351                 fd_head->datalen = tot_len;
 352         }
 353
 354         return;
 355 }
 356
 357 guint32
 358 fragment_get_tot_len(packet_info *pinfo, guint32 id, GHashTable *fragment_table)
 359 {
 360         fragment_data *fd_head;
 361         fragment_key key;
 362
 363         /* create key to search hash with */
 364         key.src = pinfo->src;
 365         key.dst = pinfo->dst;
 366         key.id  = id;
 367
 368         fd_head = g_hash_table_lookup(fragment_table, &key);
 369
 370         if(fd_head){
 371                 return fd_head->datalen;
 372         }
 373
 374         return 0;
 375 }
 376
 377
 378 /* This function will set the partial reassembly flag for a fh.
 379    When this function is called, the fh MUST already exist, i.e.
 380    the fh MUST be created by the initial call to fragment_add() before
 381    this function is called.
 382    Also note that this function MUST be called to indicate a fh will be
 383    extended (increase the already stored data)
 384 */
 385
 386 void
 387 fragment_set_partial_reassembly(packet_info *pinfo, guint32 id, GHashTable *fragment_table)
 388 {
 389         fragment_data *fd_head;
 390         fragment_key key;
 391
 392         /* create key to search hash with */
 393         key.src = pinfo->src;
 394         key.dst = pinfo->dst;
 395         key.id  = id;
 396
 397         fd_head = g_hash_table_lookup(fragment_table, &key);
 398
 399         if(fd_head){
 400                 fd_head->flags |= FD_PARTIAL_REASSEMBLY;
 401         }
 402 }
 403
 404 /*
 405  * This function adds a new fragment to the fragment hash table.
 406  * If this is the first fragment seen for this datagram, a new entry
 407  * is created in the hash table, otherwise this fragment is just added
 408  * to the linked list of fragments for this packet.
 409  * The list of fragments for a specific datagram is kept sorted for
 410  * easier handling.
 411  *
 412  * Returns a pointer to the head of the fragment data list if we have all the
 413  * fragments, NULL otherwise.
 414  *
 415  * This function assumes frag_offset being a byte offset into the defragment
 416  * packet.
 417  *
 418  * 01-2002
 419  * Once the fh is defragmented (= FD_DEFRAGMENTED set), it can be
 420  * extended using the FD_PARTIAL_REASSEMBLY flag. This flag should be set
 421  * using fragment_set_partial_reassembly() before calling fragment_add
 422  * with the new fragment. FD_TOOLONGFRAGMENT and FD_MULTIPLETAILS flags
 423  * are lowered when a new extension process is started.
 424  */
 425 fragment_data *
 426 fragment_add(tvbuff_t *tvb, int offset, packet_info *pinfo, guint32 id,
 427              GHashTable *fragment_table, guint32 frag_offset,
 428              guint32 frag_data_len, gboolean more_frags)
 429 {
 430         fragment_key key, *new_key;
 431         fragment_data *fd_head;
 432         fragment_data *fd;
 433         fragment_data *fd_i;
 434         guint32 max, dfpos;
 435         unsigned char *old_data;
 436
 437         /* create key to search hash with */
 438         key.src = pinfo->src;
 439         key.dst = pinfo->dst;
 440         key.id  = id;
 441
 442         fd_head = g_hash_table_lookup(fragment_table, &key);
 443
 444         /* have we already seen this frame ?*/
 445         if (pinfo->fd->flags.visited) {
 446                 if (fd_head != NULL && fd_head->flags & FD_DEFRAGMENTED) {
 447                         return fd_head;
 448                 } else {
 449                         return NULL;
 450                 }
 451         }
 452
 453         if (fd_head==NULL){
 454                 /* not found, this must be the first snooped fragment for this
 455                  * packet. Create list-head.
 456                  */
 457                 fd_head=g_mem_chunk_alloc(fragment_data_chunk);
 458                 /* head/first structure in list only holds no other data than
 459                  * 'datalen' then we don't have to change the head of the list
 460                  * even if we want to keep it sorted
 461                  */
 462                 fd_head->next=NULL;
 463                 fd_head->datalen=0;
 464                 fd_head->offset=0;
 465                 fd_head->len=0;
 466                 fd_head->flags=0;
 467                 fd_head->data=NULL;
 468
 469                 /*
 470                  * We're going to use the key to insert the fragment,
 471                  * so allocate a structure for it, and copy the
 472                  * addresses, allocating new buffers for the address
 473                  * data.
 474                  */
 475                 new_key = g_mem_chunk_alloc(fragment_key_chunk);
 476                 COPY_ADDRESS(&new_key->src, &key.src);
 477                 COPY_ADDRESS(&new_key->dst, &key.dst);
 478                 new_key->id = key.id;
 479                 g_hash_table_insert(fragment_table, new_key, fd_head);
 480         }
 481
 482         /* create new fd describing this fragment */
 483         fd = g_mem_chunk_alloc(fragment_data_chunk);
 484         fd->next = NULL;
 485         fd->flags = 0;
 486         fd->frame = pinfo->fd->num;
 487         fd->offset = frag_offset;
 488         fd->len  = frag_data_len;
 489         fd->data = NULL;
 490
 491         /*
 492          * If it was already defragmented and this new fragment goes beyond
 493          * data limits, set flag in already empty fds & point old fds to malloc'ed data.
 494          */
 495         if(fd_head->flags & FD_DEFRAGMENTED && (frag_offset+frag_data_len) >= fd_head->datalen &&
 496                 fd_head->flags & FD_PARTIAL_REASSEMBLY){
 497                 for(fd_i=fd_head->next; fd_i; fd_i=fd_i->next){
 498                         if( !fd_i->data ) {
 499                                 fd_i->data = fd_head->data + fd_i->offset;
 500                                 fd_i->flags |= FD_NOT_MALLOCED;
 501                         }
 502                         fd_i->flags &= (~FD_TOOLONGFRAGMENT) & (~FD_MULTIPLETAILS);
 503                 }
 504                 fd_head->flags ^= FD_DEFRAGMENTED|FD_PARTIAL_REASSEMBLY;
 505                 fd_head->flags &= (~FD_TOOLONGFRAGMENT) & (~FD_MULTIPLETAILS);
 506                 fd_head->datalen=0;
 507         }
 508
 509         if (!more_frags) {
 510                 /*
 511                  * This is the tail fragment in the sequence.
 512                  */
 513                 if (fd_head->datalen) {
 514                         /* ok we have already seen other tails for this packet
 515                          * it might be a duplicate.
 516                          */
 517                         if (fd_head->datalen != (fd->offset + fd->len) ){
 518                                 /* Oops, this tail indicates a different packet
 519                                  * len than the previous ones. Somethings wrong
 520                                  */
 521                                 fd->flags      |= FD_MULTIPLETAILS;
 522                                 fd_head->flags |= FD_MULTIPLETAILS;
 523                         }
 524                 } else {
 525                         /* this was the first tail fragment, now we know the
 526                          * length of the packet
 527                          */
 528                         fd_head->datalen = fd->offset + fd->len;
 529                 }
 530         }
 531
 532
 533
 534
 535         /* If the packet is already defragmented, this MUST be an overlap.
 536          * The entire defragmented packet is in fd_head->data
 537          * Even if we have previously defragmented this packet, we still check
 538          * check it. Someone might play overlap and TTL games.
 539          */
 540         if (fd_head->flags & FD_DEFRAGMENTED) {
 541                 fd->flags      |= FD_OVERLAP;
 542                 fd_head->flags |= FD_OVERLAP;
 543                 /* make sure its not too long */
 544                 if (fd->offset + fd->len > fd_head->datalen) {
 545                         fd->flags      |= FD_TOOLONGFRAGMENT;
 546                         fd_head->flags |= FD_TOOLONGFRAGMENT;
 547                         LINK_FRAG(fd_head,fd);
 548                         return (fd_head);
 549                 }
 550                 /* make sure it doesnt conflict with previous data */
 551                 if ( memcmp(fd_head->data+fd->offset,
 552                         tvb_get_ptr(tvb,offset,fd->len),fd->len) ){
 553                         fd->flags      |= FD_OVERLAPCONFLICT;
 554                         fd_head->flags |= FD_OVERLAPCONFLICT;
 555                         LINK_FRAG(fd_head,fd);
 556                         return (fd_head);
 557                 }
 558                 /* it was just an overlap, link it and return */
 559                 LINK_FRAG(fd_head,fd);
 560                 return (fd_head);
 561         }
 562
 563
 564
 565         /* If we have reached this point, the packet is not defragmented yet.
 566          * Save all payload in a buffer until we can defragment.
 567          * XXX - what if we didn't capture the entire fragment due
 568          * to a too-short snapshot length?
 569          */
 570         fd->data = g_malloc(fd->len);
 571         tvb_memcpy(tvb, fd->data, offset, fd->len);
 572         LINK_FRAG(fd_head,fd);
 573
 574
 575         if( !(fd_head->datalen) ){
 576                 /* if we dont know the datalen, there are still missing
 577                  * packets. Cheaper than the check below.
 578                  */
 579                 return NULL;
 580         }
 581
 582
 583         /* check if we have received the entire fragment
 584          * this is easy since the list is sorted and the head is faked.
 585          */
 586         max = 0;
 587         for (fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 588                 if ( ((fd_i->offset)<=max) &&
 589                     ((fd_i->offset+fd_i->len)>max) ){
 590                         max = fd_i->offset+fd_i->len;
 591                 }
 592         }
 593
 594         if (max < (fd_head->datalen)) {
 595                 /* we have not received all packets yet */
 596                 return NULL;
 597         }
 598
 599
 600         if (max > (fd_head->datalen)) {
 601                 /*XXX not sure if current fd was the TOOLONG*/
 602                 /*XXX is it fair to flag current fd*/
 603                 /* oops, too long fragment detected */
 604                 fd->flags      |= FD_TOOLONGFRAGMENT;
 605                 fd_head->flags |= FD_TOOLONGFRAGMENT;
 606         }
 607
 608
 609         /* we have received an entire packet, defragment it and
 610          * free all fragments
 611          */
 612         /* store old data just in case */
 613         old_data=fd_head->data;
 614         fd_head->data = g_malloc(max);
 615
 616         /* add all data fragments */
 617         for (dfpos=0,fd_i=fd_head;fd_i;fd_i=fd_i->next) {
 618                 if (fd_i->len) {
 619                         if (fd_i->offset < dfpos) {
 620                                 fd_i->flags    |= FD_OVERLAP;
 621                                 fd_head->flags |= FD_OVERLAP;
 622                                 if ( memcmp(fd_head->data+fd_i->offset,
 623                                         fd_i->data,
 624                                         MIN(fd_i->len,(dfpos-fd_i->offset))
 625                                         ) ){
 626                                         fd_i->flags    |= FD_OVERLAPCONFLICT;
 627                                         fd_head->flags |= FD_OVERLAPCONFLICT;
 628                                 }
 629                         }
 630                         /* dfpos is always >= than fd_i->offset */
 631                         /* No gaps can exist here, max_loop(above) does this */
 632                         if( fd_i->offset+fd_i->len > dfpos )
 633                                 memcpy(fd_head->data+dfpos, fd_i->data+(dfpos-fd_i->offset),
 634                                         fd_i->len-(dfpos-fd_i->offset));
 635                         if( fd_i->flags & FD_NOT_MALLOCED )
 636                                 fd_i->flags ^= FD_NOT_MALLOCED;
 637                         else
 638                                 g_free(fd_i->data);
 639                         fd_i->data=NULL;
 640
 641                         dfpos=MAX(dfpos,(fd_i->offset+fd_i->len));
 642                 }
 643         }
 644
 645         if( old_data )
 646                 g_free(old_data);
 647         /* mark this packet as defragmented.
 648            allows us to skip any trailing fragments */
 649         fd_head->flags |= FD_DEFRAGMENTED;
 650
 651         return fd_head;
 652 }
 653
 654 /*
 655  * This function adds a new fragment to the entry for a reassembly
 656  * operation.
 657  *
 658  * The list of fragments for a specific datagram is kept sorted for
 659  * easier handling.
 660  *
 661  * Returns TRUE if we have all the fragments, FALSE otherwise.
 662  *
 663  * This function assumes frag_number being a block sequence number.
 664  * The bsn for the first block is 0.
 665  */
 666 static gboolean
 667 fragment_add_seq_work(fragment_data *fd_head, tvbuff_t *tvb, int offset,
 668              packet_info *pinfo, guint32 frag_number,
 669              guint32 frag_data_len, gboolean more_frags)
 670 {
 671         fragment_data *fd;
 672         fragment_data *fd_i;
 673         fragment_data *last_fd;
 674         guint32 max, dfpos, size;
 675
 676         /* create new fd describing this fragment */
 677         fd = g_mem_chunk_alloc(fragment_data_chunk);
 678         fd->next = NULL;
 679         fd->flags = 0;
 680         fd->frame = pinfo->fd->num;
 681         fd->offset = frag_number;
 682         fd->len  = frag_data_len;
 683         fd->data = NULL;
 684
 685         if (!more_frags) {
 686                 /*
 687                  * This is the tail fragment in the sequence.
 688                  */
 689                 if (fd_head->datalen) {
 690                         /* ok we have already seen other tails for this packet
 691                          * it might be a duplicate.
 692                          */
 693                         if (fd_head->datalen != fd->offset ){
 694                                 /* Oops, this tail indicates a different packet
 695                                  * len than the previous ones. Somethings wrong
 696                                  */
 697                                 fd->flags      |= FD_MULTIPLETAILS;
 698                                 fd_head->flags |= FD_MULTIPLETAILS;
 699                         }
 700                 } else {
 701                         /* this was the first tail fragment, now we know the
 702                          * length of the packet
 703                          */
 704                         fd_head->datalen = fd->offset;
 705                 }
 706         }
 707
 708         /* If the packet is already defragmented, this MUST be an overlap.
 709          * The entire defragmented packet is in fd_head->data
 710          * Even if we have previously defragmented this packet, we still check
 711          * check it. Someone might play overlap and TTL games.
 712          */
 713         if (fd_head->flags & FD_DEFRAGMENTED) {
 714                 fd->flags      |= FD_OVERLAP;
 715                 fd_head->flags |= FD_OVERLAP;
 716
 717                 /* make sure its not too long */
 718                 if (fd->offset > fd_head->datalen) {
 719                         fd->flags      |= FD_TOOLONGFRAGMENT;
 720                         fd_head->flags |= FD_TOOLONGFRAGMENT;
 721                         LINK_FRAG(fd_head,fd);
 722                         return TRUE;
 723                 }
 724                 /* make sure it doesnt conflict with previous data */
 725                 dfpos=0;
 726                 for (fd_i=fd_head->next;fd_i->offset!=fd->offset;fd_i=fd_i->next) {
 727                   dfpos += fd_i->len;
 728                 }
 729                 if(fd_i->datalen!=fd->datalen){
 730                         fd->flags      |= FD_OVERLAPCONFLICT;
 731                         fd_head->flags |= FD_OVERLAPCONFLICT;
 732                         LINK_FRAG(fd_head,fd);
 733                         return TRUE;
 734                 }
 735                 if ( memcmp(fd_head->data+dfpos,
 736                         tvb_get_ptr(tvb,offset,fd->len),fd->len) ){
 737                         fd->flags      |= FD_OVERLAPCONFLICT;
 738                         fd_head->flags |= FD_OVERLAPCONFLICT;
 739                         LINK_FRAG(fd_head,fd);
 740                         return TRUE;
 741                 }
 742                 /* it was just an overlap, link it and return */
 743                 LINK_FRAG(fd_head,fd);
 744                 return TRUE;
 745         }
 746
 747         /* If we have reached this point, the packet is not defragmented yet.
 748          * Save all payload in a buffer until we can defragment.
 749          * XXX - what if we didn't capture the entire fragment due
 750          * to a too-short snapshot length?
 751          */
 752         fd->data = g_malloc(fd->len);
 753         tvb_memcpy(tvb, fd->data, offset, fd->len);
 754         LINK_FRAG(fd_head,fd);
 755
 756
 757         if( !(fd_head->datalen) ){
 758                 /* if we dont know the datalen, there are still missing
 759                  * packets. Cheaper than the check below.
 760                  */
 761                 return FALSE;
 762         }
 763
 764
 765         /* check if we have received the entire fragment
 766          * this is easy since the list is sorted and the head is faked.
 767          */
 768         max = 0;
 769         for(fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 770           if ( fd_i->offset==max ){
 771             max++;
 772           }
 773         }
 774         /* max will now be datalen+1 if all fragments have been seen */
 775
 776         if (max <= fd_head->datalen) {
 777                 /* we have not received all packets yet */
 778                 return FALSE;
 779         }
 780
 781
 782         if (max > (fd_head->datalen+1)) {
 783                 /* oops, too long fragment detected */
 784                 fd->flags      |= FD_TOOLONGFRAGMENT;
 785                 fd_head->flags |= FD_TOOLONGFRAGMENT;
 786         }
 787
 788
 789         /* we have received an entire packet, defragment it and
 790          * free all fragments
 791          */
 792         size=0;
 793         last_fd=NULL;
 794         for(fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 795           if(!last_fd || last_fd->offset!=fd_i->offset){
 796             size+=fd_i->len;
 797           }
 798           last_fd=fd_i;
 799         }
 800         fd_head->data = g_malloc(size);
 801         fd_head->len = size;            /* record size for caller       */
 802
 803         /* add all data fragments */
 804         last_fd=NULL;
 805         for (dfpos=0,fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 806           if (fd_i->len) {
 807             if(!last_fd || last_fd->offset!=fd_i->offset){
 808               memcpy(fd_head->data+dfpos,fd_i->data,fd_i->len);
 809               dfpos += fd_i->len;
 810             } else {
 811               /* duplicate/retransmission/overlap */
 812               if( (last_fd->len!=fd_i->datalen)
 813                   || memcmp(last_fd->data, fd_i->data, last_fd->len) ){
 814                         fd->flags      |= FD_OVERLAPCONFLICT;
 815                         fd_head->flags |= FD_OVERLAPCONFLICT;
 816               }
 817             }
 818             last_fd=fd_i;
 819           }
 820         }
 821
 822         /* we have defragmented the pdu, now free all fragments*/
 823         for (fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 824           if(fd_i->data){
 825             g_free(fd_i->data);
 826             fd_i->data=NULL;
 827           }
 828         }
 829
 830         /* mark this packet as defragmented.
 831            allows us to skip any trailing fragments */
 832         fd_head->flags |= FD_DEFRAGMENTED;
 833
 834         return TRUE;
 835 }
 836
 837 /*
 838  * This function adds a new fragment to the fragment hash table.
 839  * If this is the first fragment seen for this datagram, a new entry
 840  * is created in the hash table, otherwise this fragment is just added
 841  * to the linked list of fragments for this packet.
 842  *
 843  * Returns a pointer to the head of the fragment data list if we have all the
 844  * fragments, NULL otherwise.
 845  *
 846  * This function assumes frag_number being a block sequence number.
 847  * The bsn for the first block is 0.
 848  */
 849 fragment_data *
 850 fragment_add_seq(tvbuff_t *tvb, int offset, packet_info *pinfo, guint32 id,
 851              GHashTable *fragment_table, guint32 frag_number,
 852              guint32 frag_data_len, gboolean more_frags)
 853 {
 854         fragment_key key, *new_key;
 855         fragment_data *fd_head;
 856
 857         /* create key to search hash with */
 858         key.src = pinfo->src;
 859         key.dst = pinfo->dst;
 860         key.id  = id;
 861
 862         fd_head = g_hash_table_lookup(fragment_table, &key);
 863
 864         /* have we already seen this frame ?*/
 865         if (pinfo->fd->flags.visited) {
 866                 if (fd_head != NULL && fd_head->flags & FD_DEFRAGMENTED) {
 867                         return fd_head;
 868                 } else {
 869                         return NULL;
 870                 }
 871         }
 872
 873         if (fd_head==NULL){
 874                 /* not found, this must be the first snooped fragment for this
 875                  * packet. Create list-head.
 876                  */
 877                 fd_head=g_mem_chunk_alloc(fragment_data_chunk);
 878                 /* head/first structure in list only holds no other data than
 879                  * 'datalen' then we don't have to change the head of the list
 880                  * even if we want to keep it sorted
 881                  */
 882                 fd_head->next=NULL;
 883                 fd_head->datalen=0;
 884                 fd_head->offset=0;
 885                 fd_head->len=0;
 886                 fd_head->flags=FD_BLOCKSEQUENCE;
 887                 fd_head->data=NULL;
 888
 889                 /*
 890                  * We're going to use the key to insert the fragment,
 891                  * so allocate a structure for it, and copy the
 892                  * addresses, allocating new buffers for the address
 893                  * data.
 894                  */
 895                 new_key = g_mem_chunk_alloc(fragment_key_chunk);
 896                 COPY_ADDRESS(&new_key->src, &key.src);
 897                 COPY_ADDRESS(&new_key->dst, &key.dst);
 898                 new_key->id = key.id;
 899                 g_hash_table_insert(fragment_table, new_key, fd_head);
 900         }
 901
 902         if (fragment_add_seq_work(fd_head, tvb, offset, pinfo,
 903                                   frag_number, frag_data_len, more_frags)) {
 904                 /*
 905                  * Reassembly is complete.
 906                  */
 907                 return fd_head;
 908         } else {
 909                 /*
 910                  * Reassembly isn't complete.
 911                  */
 912                 return NULL;
 913         }
 914 }
 915
 916 /*
 917  * This function gets rid of an entry from a fragment table, given
 918  * a pointer to the key for that entry; it also frees up the key
 919  * and the addresses in it.
 920  */
 921 static void
 922 fragment_unhash(GHashTable *fragment_table, fragment_key *key)
 923 {
 924         /*
 925          * Free up the copies of the addresses from the old key.
 926          */
 927         g_free((gpointer)key->src.data);
 928         g_free((gpointer)key->dst.data);
 929
 930         /*
 931          * Remove the entry from the fragment table.
 932          */
 933         g_hash_table_remove(fragment_table, key);
 934
 935         /*
 936          * Free the key itself.
 937          */
 938         g_mem_chunk_free(fragment_key_chunk, key);
 939 }
 940
 941 /*
 942  * This function adds fragment_data structure to a reassembled-packet
 943  * hash table, using the frame data structure as the key.
 944  */
 945 static void
 946 fragment_reassembled(fragment_data *fd_head, packet_info *pinfo,
 947              GHashTable *reassembled_table)
 948 {
 949         g_hash_table_insert(reassembled_table, pinfo->fd, fd_head);
 950 }
 951
 952 /*
 953  * This function adds a new fragment to the fragment hash table.
 954  * If this is the first fragment seen for this datagram, a new
 955  * "fragment_data" structure is allocated to refer to the reassembled,
 956  * packet, and:
 957  *
 958  *      if "more_frags" is false, the structure is not added to
 959  *      the hash table, and not given any fragments to refer to,
 960  *      but is just returned;
 961  *
 962  *      if "more_frags" is true, this fragment is added to the linked
 963  *      list of fragments for this packet, and the "fragment_data"
 964  *      structure is put into the hash table.
 965  *
 966  * Otherwise, this fragment is just added to the linked list of fragments
 967  * for this packet.
 968  *
 969  * Returns a pointer to the head of the fragment data list, and removes
 970  * that from the fragment hash table if necessary and adds it to the
 971  * table of reassembled fragments, if we have all the fragments or if
 972  * this is the only fragment and "more_frags" is false, returns NULL
 973  * otherwise.
 974  *
 975  * This function assumes frag_number being a block sequence number.
 976  * The bsn for the first block is 0.
 977  */
 978 fragment_data *
 979 fragment_add_seq_check(tvbuff_t *tvb, int offset, packet_info *pinfo,
 980              guint32 id, GHashTable *fragment_table,
 981              GHashTable *reassembled_table, guint32 frag_number,
 982              guint32 frag_data_len, gboolean more_frags)
 983 {
 984         fragment_key key, *new_key, *old_key;
 985         gpointer orig_key, value;
 986         fragment_data *fd_head;
 987         gboolean short_frame;
 988
 989         /*
 990          * Have we already seen this frame?
 991          * If so, look for it in the table of reassembled packets.
 992          */
 993         if (pinfo->fd->flags.visited)
 994                 return g_hash_table_lookup(reassembled_table, pinfo->fd);
 995
 996         short_frame = (tvb_reported_length(tvb) > tvb_length(tvb));
 997
 998         /* create key to search hash with */
 999         key.src = pinfo->src;
1000         key.dst = pinfo->dst;
1001         key.id  = id;
1002
1003         if (!g_hash_table_lookup_extended(fragment_table, &key,
1004                                           &orig_key, &value)) {
1005                 /* not found, this must be the first snooped fragment for this
1006                  * packet. Create list-head.
1007                  */
1008                 fd_head=g_mem_chunk_alloc(fragment_data_chunk);
1009
1010                 /* head/first structure in list only holds no other data than
1011                  * 'datalen' then we don't have to change the head of the list
1012                  * even if we want to keep it sorted
1013                  */
1014                 fd_head->next=NULL;
1015                 fd_head->datalen=0;
1016                 fd_head->offset=0;
1017                 fd_head->len=0;
1018                 fd_head->flags=FD_BLOCKSEQUENCE;
1019                 fd_head->data=NULL;
1020
1021                 if (!more_frags) {
1022                         /*
1023                          * This is the last snooped fragment for this
1024                          * packet as well; that means it's the only
1025                          * fragment.  Just add it to the table of
1026                          * reassembled packets, and return it.
1027                          */
1028                         fragment_reassembled(fd_head, pinfo,
1029                                reassembled_table);
1030                         return fd_head;
1031                 }
1032
1033                 /*
1034                  * We're going to use the key to insert the fragment,
1035                  * so allocate a structure for it, and copy the
1036                  * addresses, allocating new buffers for the address
1037                  * data.
1038                  */
1039                 new_key = g_mem_chunk_alloc(fragment_key_chunk);
1040                 COPY_ADDRESS(&new_key->src, &key.src);
1041                 COPY_ADDRESS(&new_key->dst, &key.dst);
1042                 new_key->id = key.id;
1043                 g_hash_table_insert(fragment_table, new_key, fd_head);
1044
1045                 orig_key = new_key;     /* for unhashing it later */
1046         } else {
1047                 /*
1048                  * We found it.
1049                  */
1050                 fd_head = value;
1051         }
1052
1053         /*
1054          * If this is a short frame, then we can't, and don't, do
1055          * reassembly on it.
1056          *
1057          * If it's the first frame (fragment number is 0), handle it
1058          * as an unfragmented packet.  Otherwise, just handle it
1059          * as a fragment.
1060          *
1061          * If "more_frags" isn't set, we get rid of the entry in the
1062          * hash table for this reassembly, as we don't need it any more.
1063          */
1064         if (short_frame) {
1065                 if (!more_frags) {
1066                         /*
1067                          * Remove this from the table of in-progress
1068                          * reassemblies, and free up any memory used for
1069                          * it in that table.
1070                          */
1071                         old_key = orig_key;
1072                         fragment_unhash(fragment_table, old_key);
1073                 }
1074                 return frag_number == 0 ? fd_head : NULL;
1075         }
1076
1077         if (fragment_add_seq_work(fd_head, tvb, offset, pinfo,
1078                                   frag_number, frag_data_len, more_frags)) {
1079                 /*
1080                  * Reassembly is complete.
1081                  * Remove this from the table of in-progress
1082                  * reassemblies, add it to the table of
1083                  * reassembled packets, and return it.
1084                  */
1085
1086                 /*
1087                  * Remove this from the table of in-progress reassemblies,
1088                  * and free up any memory used for it in that table.
1089                  */
1090                 old_key = orig_key;
1091                 fragment_unhash(fragment_table, old_key);
1092
1093                 /*
1094                  * Add this item to the table of reassembled packets.
1095                  */
1096                 fragment_reassembled(fd_head, pinfo, reassembled_table);
1097                 return fd_head;
1098         } else {
1099                 /*
1100                  * Reassembly isn't complete.
1101                  */
1102                 return NULL;
1103         }
1104 }
1105
1106
1107 /*
1108  * Show a single fragment in a fragment subtree.
1109  */
1110 static void
1111 show_fragment(fragment_data *fd, int offset, fragment_items *fit,
1112     proto_tree *ft, tvbuff_t *tvb)
1113 {
1114         if (fd->flags & (FD_OVERLAP|FD_OVERLAPCONFLICT
1115                 |FD_MULTIPLETAILS|FD_TOOLONGFRAGMENT) ) {
1116                 /* this fragment has some flags set, create a subtree
1117                  * for it and display the flags.
1118                  */
1119                 proto_tree *fet=NULL;
1120                 proto_item *fei=NULL;
1121                 int hf;
1122
1123                 if (fd->flags & (FD_OVERLAPCONFLICT
1124                         |FD_MULTIPLETAILS|FD_TOOLONGFRAGMENT) ) {
1125                         hf = *(fit->hf_fragment_error);
1126                 } else {
1127                         hf = *(fit->hf_fragment);
1128                 }
1129                 fei = proto_tree_add_none_format(ft, hf,
1130                         tvb, offset, fd->len,
1131                         "Frame:%u payload:%u-%u",
1132                         fd->frame,
1133                         offset,
1134                         offset+fd->len-1);
1135                 fet = proto_item_add_subtree(fei, *(fit->ett_fragment));
1136                 if (fd->flags&FD_OVERLAP) {
1137                         proto_tree_add_boolean(fet,
1138                                 *(fit->hf_fragment_overlap),
1139                                 tvb, 0, 0,
1140                                 TRUE);
1141                 }
1142                 if (fd->flags&FD_OVERLAPCONFLICT) {
1143                         proto_tree_add_boolean(fet,
1144                                 *(fit->hf_fragment_overlap_conflict),
1145                                 tvb, 0, 0,
1146                                 TRUE);
1147                 }
1148                 if (fd->flags&FD_MULTIPLETAILS) {
1149                         proto_tree_add_boolean(fet,
1150                                 *(fit->hf_fragment_multiple_tails),
1151                                 tvb, 0, 0,
1152                                 TRUE);
1153                 }
1154                 if (fd->flags&FD_TOOLONGFRAGMENT) {
1155                         proto_tree_add_boolean(fet,
1156                                 *(fit->hf_fragment_too_long_fragment),
1157                                 tvb, 0, 0,
1158                                 TRUE);
1159                 }
1160         } else {
1161                 /* nothing of interest for this fragment */
1162                 proto_tree_add_none_format(ft, *(fit->hf_fragment),
1163                         tvb, offset, fd->len,
1164                         "Frame:%u payload:%u-%u",
1165                         fd->frame,
1166                         offset,
1167                         offset+fd->len-1
1168                 );
1169         }
1170 }
1171
1172 static gboolean
1173 show_fragment_errs_in_col(fragment_data *fd_head, fragment_items *fit,
1174     packet_info *pinfo)
1175 {
1176         if (fd_head->flags & (FD_OVERLAPCONFLICT
1177                 |FD_MULTIPLETAILS|FD_TOOLONGFRAGMENT) ) {
1178                 if (check_col(pinfo->cinfo, COL_INFO)) {
1179                         col_add_fstr(pinfo->cinfo, COL_INFO,
1180                                 "[Illegal %s]", fit->tag);
1181                         return TRUE;
1182                 }
1183         }
1184
1185         return FALSE;
1186 }
1187
1188 /* This function will build the fragment subtree; it's for fragments
1189    reassembled with "fragment_add()".
1190
1191    It will return TRUE if there were fragmentation errors
1192    or FALSE if fragmentation was ok.
1193 */
1194 gboolean
1195 show_fragment_tree(fragment_data *fd_head, fragment_items *fit,
1196     proto_tree *tree, packet_info *pinfo, tvbuff_t *tvb)
1197 {
1198         fragment_data *fd;
1199         proto_tree *ft=NULL;
1200         proto_item *fi=NULL;
1201
1202         /* It's not fragmented. */
1203         pinfo->fragmented = FALSE;
1204
1205         fi = proto_tree_add_item(tree, *(fit->hf_fragments),
1206                 tvb, 0, -1, FALSE);
1207         ft = proto_item_add_subtree(fi, *(fit->ett_fragments));
1208         for (fd=fd_head->next; fd; fd=fd->next)
1209                 show_fragment(fd, fd->offset, fit, ft, tvb);
1210
1211         return show_fragment_errs_in_col(fd_head, fit, pinfo);
1212 }
1213
1214 /* This function will build the fragment subtree; it's for fragments
1215    reassembled with "fragment_add_seq()" or "fragment_add_seq_check()".
1216
1217    It will return TRUE if there were fragmentation errors
1218    or FALSE if fragmentation was ok.
1219 */
1220 gboolean
1221 show_fragment_seq_tree(fragment_data *fd_head, fragment_items *fit,
1222     proto_tree *tree, packet_info *pinfo, tvbuff_t *tvb)
1223 {
1224         guint32 offset;
1225         fragment_data *fd;
1226         proto_tree *ft=NULL;
1227         proto_item *fi=NULL;
1228
1229         /* It's not fragmented. */
1230         pinfo->fragmented = FALSE;
1231
1232         fi = proto_tree_add_item(tree, *(fit->hf_fragments),
1233                 tvb, 0, -1, FALSE);
1234         ft = proto_item_add_subtree(fi, *(fit->ett_fragments));
1235         offset = 0;
1236         for (fd=fd_head->next; fd; fd=fd->next){
1237                 show_fragment(fd, offset, fit, ft, tvb);
1238                 offset += fd->len;
1239         }
1240
1241         return show_fragment_errs_in_col(fd_head, fit, pinfo);
1242 }