reassemble.c

   1 /* reassemble.c
   2  * Routines for {fragment,segment} reassembly
   3  *
   4  * $Id: reassemble.c,v 1.28 2002/12/19 11:22:38 sahlberg 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         const fragment_key* key1 = (const fragment_key*) k1;
  61         const fragment_key* key2 = (const 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         const fragment_key* key = (const 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         const frame_data* key1 = (const frame_data*) k1;
 119         const frame_data* key2 = (const frame_data*) k2;
 120
 121         return (key1->num == key2->num);
 122 }
 123
 124 static guint
 125 reassembled_hash(gconstpointer k)
 126 {
 127         const frame_data* key = (const 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                 last_fd=NULL;
 727                 for (fd_i=fd_head->next;fd_i->offset!=fd->offset;fd_i=fd_i->next) {
 728                   if (!last_fd || last_fd->offset!=fd_i->offset){
 729                     dfpos += fd_i->len;
 730                   }
 731                   last_fd=fd_i;
 732                 }
 733                 if(fd_i->datalen!=fd->datalen){
 734                         fd->flags      |= FD_OVERLAPCONFLICT;
 735                         fd_head->flags |= FD_OVERLAPCONFLICT;
 736                         LINK_FRAG(fd_head,fd);
 737                         return TRUE;
 738                 }
 739                 g_assert(fd_head->len >= dfpos + fd->len);
 740                 if ( memcmp(fd_head->data+dfpos,
 741                         tvb_get_ptr(tvb,offset,fd->len),fd->len) ){
 742                         fd->flags      |= FD_OVERLAPCONFLICT;
 743                         fd_head->flags |= FD_OVERLAPCONFLICT;
 744                         LINK_FRAG(fd_head,fd);
 745                         return TRUE;
 746                 }
 747                 /* it was just an overlap, link it and return */
 748                 LINK_FRAG(fd_head,fd);
 749                 return TRUE;
 750         }
 751
 752         /* If we have reached this point, the packet is not defragmented yet.
 753          * Save all payload in a buffer until we can defragment.
 754          * XXX - what if we didn't capture the entire fragment due
 755          * to a too-short snapshot length?
 756          */
 757         fd->data = g_malloc(fd->len);
 758         tvb_memcpy(tvb, fd->data, offset, fd->len);
 759         LINK_FRAG(fd_head,fd);
 760
 761
 762         if( !(fd_head->datalen) ){
 763                 /* if we dont know the datalen, there are still missing
 764                  * packets. Cheaper than the check below.
 765                  */
 766                 return FALSE;
 767         }
 768
 769
 770         /* check if we have received the entire fragment
 771          * this is easy since the list is sorted and the head is faked.
 772          */
 773         max = 0;
 774         for(fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 775           if ( fd_i->offset==max ){
 776             max++;
 777           }
 778         }
 779         /* max will now be datalen+1 if all fragments have been seen */
 780
 781         if (max <= fd_head->datalen) {
 782                 /* we have not received all packets yet */
 783                 return FALSE;
 784         }
 785
 786
 787         if (max > (fd_head->datalen+1)) {
 788                 /* oops, too long fragment detected */
 789                 fd->flags      |= FD_TOOLONGFRAGMENT;
 790                 fd_head->flags |= FD_TOOLONGFRAGMENT;
 791         }
 792
 793
 794         /* we have received an entire packet, defragment it and
 795          * free all fragments
 796          */
 797         size=0;
 798         last_fd=NULL;
 799         for(fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 800           if(!last_fd || last_fd->offset!=fd_i->offset){
 801             size+=fd_i->len;
 802           }
 803           last_fd=fd_i;
 804         }
 805         fd_head->data = g_malloc(size);
 806         fd_head->len = size;            /* record size for caller       */
 807
 808         /* add all data fragments */
 809         last_fd=NULL;
 810         for (dfpos=0,fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 811           if (fd_i->len) {
 812             if(!last_fd || last_fd->offset!=fd_i->offset){
 813               memcpy(fd_head->data+dfpos,fd_i->data,fd_i->len);
 814               dfpos += fd_i->len;
 815             } else {
 816               /* duplicate/retransmission/overlap */
 817               fd_i->flags    |= FD_OVERLAP;
 818               fd_head->flags |= FD_OVERLAP;
 819               if( (last_fd->len!=fd_i->datalen)
 820                   || memcmp(last_fd->data, fd_i->data, last_fd->len) ){
 821                         fd->flags      |= FD_OVERLAPCONFLICT;
 822                         fd_head->flags |= FD_OVERLAPCONFLICT;
 823               }
 824             }
 825             last_fd=fd_i;
 826           }
 827         }
 828
 829         /* we have defragmented the pdu, now free all fragments*/
 830         for (fd_i=fd_head->next;fd_i;fd_i=fd_i->next) {
 831           if(fd_i->data){
 832             g_free(fd_i->data);
 833             fd_i->data=NULL;
 834           }
 835         }
 836
 837         /* mark this packet as defragmented.
 838            allows us to skip any trailing fragments */
 839         fd_head->flags |= FD_DEFRAGMENTED;
 840
 841         return TRUE;
 842 }
 843
 844 /*
 845  * This function adds a new fragment to the fragment hash table.
 846  * If this is the first fragment seen for this datagram, a new entry
 847  * is created in the hash table, otherwise this fragment is just added
 848  * to the linked list of fragments for this packet.
 849  *
 850  * Returns a pointer to the head of the fragment data list if we have all the
 851  * fragments, NULL otherwise.
 852  *
 853  * This function assumes frag_number being a block sequence number.
 854  * The bsn for the first block is 0.
 855  */
 856 fragment_data *
 857 fragment_add_seq(tvbuff_t *tvb, int offset, packet_info *pinfo, guint32 id,
 858              GHashTable *fragment_table, guint32 frag_number,
 859              guint32 frag_data_len, gboolean more_frags)
 860 {
 861         fragment_key key, *new_key;
 862         fragment_data *fd_head;
 863
 864         /* create key to search hash with */
 865         key.src = pinfo->src;
 866         key.dst = pinfo->dst;
 867         key.id  = id;
 868
 869         fd_head = g_hash_table_lookup(fragment_table, &key);
 870
 871         /* have we already seen this frame ?*/
 872         if (pinfo->fd->flags.visited) {
 873                 if (fd_head != NULL && fd_head->flags & FD_DEFRAGMENTED) {
 874                         return fd_head;
 875                 } else {
 876                         return NULL;
 877                 }
 878         }
 879
 880         if (fd_head==NULL){
 881                 /* not found, this must be the first snooped fragment for this
 882                  * packet. Create list-head.
 883                  */
 884                 fd_head=g_mem_chunk_alloc(fragment_data_chunk);
 885                 /* head/first structure in list only holds no other data than
 886                  * 'datalen' then we don't have to change the head of the list
 887                  * even if we want to keep it sorted
 888                  */
 889                 fd_head->next=NULL;
 890                 fd_head->datalen=0;
 891                 fd_head->offset=0;
 892                 fd_head->len=0;
 893                 fd_head->flags=FD_BLOCKSEQUENCE;
 894                 fd_head->data=NULL;
 895
 896                 /*
 897                  * We're going to use the key to insert the fragment,
 898                  * so allocate a structure for it, and copy the
 899                  * addresses, allocating new buffers for the address
 900                  * data.
 901                  */
 902                 new_key = g_mem_chunk_alloc(fragment_key_chunk);
 903                 COPY_ADDRESS(&new_key->src, &key.src);
 904                 COPY_ADDRESS(&new_key->dst, &key.dst);
 905                 new_key->id = key.id;
 906                 g_hash_table_insert(fragment_table, new_key, fd_head);
 907         }
 908
 909         if (fragment_add_seq_work(fd_head, tvb, offset, pinfo,
 910                                   frag_number, frag_data_len, more_frags)) {
 911                 /*
 912                  * Reassembly is complete.
 913                  */
 914                 return fd_head;
 915         } else {
 916                 /*
 917                  * Reassembly isn't complete.
 918                  */
 919                 return NULL;
 920         }
 921 }
 922
 923 /*
 924  * This function gets rid of an entry from a fragment table, given
 925  * a pointer to the key for that entry; it also frees up the key
 926  * and the addresses in it.
 927  */
 928 static void
 929 fragment_unhash(GHashTable *fragment_table, fragment_key *key)
 930 {
 931         /*
 932          * Free up the copies of the addresses from the old key.
 933          */
 934         g_free((gpointer)key->src.data);
 935         g_free((gpointer)key->dst.data);
 936
 937         /*
 938          * Remove the entry from the fragment table.
 939          */
 940         g_hash_table_remove(fragment_table, key);
 941
 942         /*
 943          * Free the key itself.
 944          */
 945         g_mem_chunk_free(fragment_key_chunk, key);
 946 }
 947
 948 /*
 949  * This function adds fragment_data structure to a reassembled-packet
 950  * hash table, using the frame data structure as the key.
 951  */
 952 static void
 953 fragment_reassembled(fragment_data *fd_head, packet_info *pinfo,
 954              GHashTable *reassembled_table)
 955 {
 956         g_hash_table_insert(reassembled_table, pinfo->fd, fd_head);
 957 }
 958
 959 /*
 960  * This does the work for "fragment_add_seq_check()" and
 961  * "fragment_add_seq_next()".
 962  *
 963  * This function assumes frag_number being a block sequence number.
 964  * The bsn for the first block is 0.
 965  *
 966  * If "no_frag_number" is TRUE, it uses the next expected fragment number
 967  * as the fragment number if there is a reassembly in progress, otherwise
 968  * it uses 0.
 969  *
 970  * If "no_frag_number" is FALSE, it uses the "frag_number" argument as
 971  * the fragment number.
 972  *
 973  * If this is the first fragment seen for this datagram, a new
 974  * "fragment_data" structure is allocated to refer to the reassembled,
 975  * packet, and:
 976  *
 977  *      if "more_frags" is false, the structure is not added to
 978  *      the hash table, and not given any fragments to refer to,
 979  *      but is just returned;
 980  *
 981  *      if "more_frags" is true, this fragment is added to the linked
 982  *      list of fragments for this packet, and the "fragment_data"
 983  *      structure is put into the hash table.
 984  *
 985  * Otherwise, this fragment is just added to the linked list of fragments
 986  * for this packet.
 987  *
 988  * Returns a pointer to the head of the fragment data list, and removes
 989  * that from the fragment hash table if necessary and adds it to the
 990  * table of reassembled fragments, if we have all the fragments or if
 991  * this is the only fragment and "more_frags" is false, returns NULL
 992  * otherwise.
 993  */
 994 fragment_data *
 995 fragment_add_seq_check_work(tvbuff_t *tvb, int offset, packet_info *pinfo,
 996              guint32 id, GHashTable *fragment_table,
 997              GHashTable *reassembled_table, guint32 frag_number,
 998              guint32 frag_data_len, gboolean more_frags,
 999              gboolean no_frag_number)
1000 {
1001         fragment_key key, *new_key, *old_key;
1002         gpointer orig_key, value;
1003         fragment_data *fd_head, *fd;
1004
1005         /*
1006          * Have we already seen this frame?
1007          * If so, look for it in the table of reassembled packets.
1008          */
1009         if (pinfo->fd->flags.visited)
1010                 return g_hash_table_lookup(reassembled_table, pinfo->fd);
1011
1012         /* create key to search hash with */
1013         key.src = pinfo->src;
1014         key.dst = pinfo->dst;
1015         key.id  = id;
1016
1017         if (!g_hash_table_lookup_extended(fragment_table, &key,
1018                                           &orig_key, &value)) {
1019                 /* not found, this must be the first snooped fragment for this
1020                  * packet. Create list-head.
1021                  */
1022                 fd_head=g_mem_chunk_alloc(fragment_data_chunk);
1023
1024                 /* head/first structure in list only holds no other data than
1025                  * 'datalen' then we don't have to change the head of the list
1026                  * even if we want to keep it sorted
1027                  */
1028                 fd_head->next=NULL;
1029                 fd_head->datalen=0;
1030                 fd_head->offset=0;
1031                 fd_head->len=0;
1032                 fd_head->flags=FD_BLOCKSEQUENCE;
1033                 fd_head->data=NULL;
1034
1035                 if (!more_frags) {
1036                         /*
1037                          * This is the last snooped fragment for this
1038                          * packet as well; that means it's the only
1039                          * fragment.  Just add it to the table of
1040                          * reassembled packets, and return it.
1041                          */
1042                         fragment_reassembled(fd_head, pinfo,
1043                                reassembled_table);
1044                         return fd_head;
1045                 }
1046
1047                 /*
1048                  * We're going to use the key to insert the fragment,
1049                  * so allocate a structure for it, and copy the
1050                  * addresses, allocating new buffers for the address
1051                  * data.
1052                  */
1053                 new_key = g_mem_chunk_alloc(fragment_key_chunk);
1054                 COPY_ADDRESS(&new_key->src, &key.src);
1055                 COPY_ADDRESS(&new_key->dst, &key.dst);
1056                 new_key->id = key.id;
1057                 g_hash_table_insert(fragment_table, new_key, fd_head);
1058
1059                 orig_key = new_key;     /* for unhashing it later */
1060
1061                 /*
1062                  * If we weren't given an initial fragment number,
1063                  * make it 0.
1064                  */
1065                 if (no_frag_number)
1066                         frag_number = 0;
1067         } else {
1068                 /*
1069                  * We found it.
1070                  */
1071                 fd_head = value;
1072
1073                 /*
1074                  * If we weren't given an initial fragment number,
1075                  * use the next expected fragment number as the fragment
1076                  * number for this fragment.
1077                  */
1078                 if (no_frag_number) {
1079                         for (fd = fd_head; fd != NULL; fd = fd->next) {
1080                                 if (fd->next == NULL)
1081                                         frag_number = fd->offset + 1;
1082                         }
1083                 }
1084         }
1085
1086         /*
1087          * If this is a short frame, then we can't, and don't, do
1088          * reassembly on it.
1089          *
1090          * If it's the first frame, handle it as an unfragmented packet.
1091          * Otherwise, just handle it as a fragment.
1092          *
1093          * If "more_frags" isn't set, we get rid of the entry in the
1094          * hash table for this reassembly, as we don't need it any more.
1095          */
1096         if (tvb_reported_length(tvb) > tvb_length(tvb)) {
1097                 if (!more_frags) {
1098                         /*
1099                          * Remove this from the table of in-progress
1100                          * reassemblies, and free up any memory used for
1101                          * it in that table.
1102                          */
1103                         old_key = orig_key;
1104                         fragment_unhash(fragment_table, old_key);
1105                 }
1106                 return frag_number == 0 ? fd_head : NULL;
1107         }
1108
1109         if (fragment_add_seq_work(fd_head, tvb, offset, pinfo,
1110                                   frag_number, frag_data_len, more_frags)) {
1111                 /*
1112                  * Reassembly is complete.
1113                  * Remove this from the table of in-progress
1114                  * reassemblies, add it to the table of
1115                  * reassembled packets, and return it.
1116                  */
1117
1118                 /*
1119                  * Remove this from the table of in-progress reassemblies,
1120                  * and free up any memory used for it in that table.
1121                  */
1122                 old_key = orig_key;
1123                 fragment_unhash(fragment_table, old_key);
1124
1125                 /*
1126                  * Add this item to the table of reassembled packets.
1127                  */
1128                 fragment_reassembled(fd_head, pinfo, reassembled_table);
1129                 return fd_head;
1130         } else {
1131                 /*
1132                  * Reassembly isn't complete.
1133                  */
1134                 return NULL;
1135         }
1136 }
1137
1138 fragment_data *
1139 fragment_add_seq_check(tvbuff_t *tvb, int offset, packet_info *pinfo,
1140              guint32 id, GHashTable *fragment_table,
1141              GHashTable *reassembled_table, guint32 frag_number,
1142              guint32 frag_data_len, gboolean more_frags)
1143 {
1144         return fragment_add_seq_check_work(tvb, offset, pinfo, id,
1145             fragment_table, reassembled_table, frag_number, frag_data_len,
1146             more_frags, FALSE);
1147 }
1148
1149 fragment_data *
1150 fragment_add_seq_next(tvbuff_t *tvb, int offset, packet_info *pinfo,
1151              guint32 id, GHashTable *fragment_table,
1152              GHashTable *reassembled_table, guint32 frag_data_len,
1153              gboolean more_frags)
1154 {
1155         return fragment_add_seq_check_work(tvb, offset, pinfo, id,
1156             fragment_table, reassembled_table, 0, frag_data_len,
1157             more_frags, TRUE);
1158 }
1159
1160 /*
1161  * Show a single fragment in a fragment subtree.
1162  */
1163 static void
1164 show_fragment(fragment_data *fd, int offset, const fragment_items *fit,
1165     proto_tree *ft, tvbuff_t *tvb)
1166 {
1167         if (fd->flags & (FD_OVERLAP|FD_OVERLAPCONFLICT
1168                 |FD_MULTIPLETAILS|FD_TOOLONGFRAGMENT) ) {
1169                 /* this fragment has some flags set, create a subtree
1170                  * for it and display the flags.
1171                  */
1172                 proto_tree *fet=NULL;
1173                 proto_item *fei=NULL;
1174                 int hf;
1175
1176                 if (fd->flags & (FD_OVERLAPCONFLICT
1177                         |FD_MULTIPLETAILS|FD_TOOLONGFRAGMENT) ) {
1178                         hf = *(fit->hf_fragment_error);
1179                 } else {
1180                         hf = *(fit->hf_fragment);
1181                 }
1182                 fei = proto_tree_add_uint_format(ft, hf,
1183                         tvb, offset, fd->len,
1184                         fd->frame,
1185                         "Frame:%u payload:%u-%u",
1186                         fd->frame,
1187                         offset,
1188                         offset+fd->len-1);
1189                 fet = proto_item_add_subtree(fei, *(fit->ett_fragment));
1190                 if (fd->flags&FD_OVERLAP) {
1191                         proto_tree_add_boolean(fet,
1192                                 *(fit->hf_fragment_overlap),
1193                                 tvb, 0, 0,
1194                                 TRUE);
1195                 }
1196                 if (fd->flags&FD_OVERLAPCONFLICT) {
1197                         proto_tree_add_boolean(fet,
1198                                 *(fit->hf_fragment_overlap_conflict),
1199                                 tvb, 0, 0,
1200                                 TRUE);
1201                 }
1202                 if (fd->flags&FD_MULTIPLETAILS) {
1203                         proto_tree_add_boolean(fet,
1204                                 *(fit->hf_fragment_multiple_tails),
1205                                 tvb, 0, 0,
1206                                 TRUE);
1207                 }
1208                 if (fd->flags&FD_TOOLONGFRAGMENT) {
1209                         proto_tree_add_boolean(fet,
1210                                 *(fit->hf_fragment_too_long_fragment),
1211                                 tvb, 0, 0,
1212                                 TRUE);
1213                 }
1214         } else {
1215                 /* nothing of interest for this fragment */
1216                 proto_tree_add_uint_format(ft, *(fit->hf_fragment),
1217                         tvb, offset, fd->len,
1218                         fd->frame,
1219                         "Frame:%u payload:%u-%u",
1220                         fd->frame,
1221                         offset,
1222                         offset+fd->len-1
1223                 );
1224         }
1225 }
1226
1227 static gboolean
1228 show_fragment_errs_in_col(fragment_data *fd_head, const fragment_items *fit,
1229     packet_info *pinfo)
1230 {
1231         if (fd_head->flags & (FD_OVERLAPCONFLICT
1232                 |FD_MULTIPLETAILS|FD_TOOLONGFRAGMENT) ) {
1233                 if (check_col(pinfo->cinfo, COL_INFO)) {
1234                         col_add_fstr(pinfo->cinfo, COL_INFO,
1235                                 "[Illegal %s]", fit->tag);
1236                         return TRUE;
1237                 }
1238         }
1239
1240         return FALSE;
1241 }
1242
1243 /* This function will build the fragment subtree; it's for fragments
1244    reassembled with "fragment_add()".
1245
1246    It will return TRUE if there were fragmentation errors
1247    or FALSE if fragmentation was ok.
1248 */
1249 gboolean
1250 show_fragment_tree(fragment_data *fd_head, const fragment_items *fit,
1251     proto_tree *tree, packet_info *pinfo, tvbuff_t *tvb)
1252 {
1253         fragment_data *fd;
1254         proto_tree *ft;
1255         proto_item *fi;
1256
1257         /* It's not fragmented. */
1258         pinfo->fragmented = FALSE;
1259
1260         fi = proto_tree_add_item(tree, *(fit->hf_fragments),
1261             tvb, 0, -1, FALSE);
1262         ft = proto_item_add_subtree(fi, *(fit->ett_fragments));
1263         for (fd = fd_head->next; fd != NULL; fd = fd->next)
1264                 show_fragment(fd, fd->offset, fit, ft, tvb);
1265
1266         return show_fragment_errs_in_col(fd_head, fit, pinfo);
1267 }
1268
1269 /* This function will build the fragment subtree; it's for fragments
1270    reassembled with "fragment_add_seq()" or "fragment_add_seq_check()".
1271
1272    It will return TRUE if there were fragmentation errors
1273    or FALSE if fragmentation was ok.
1274 */
1275 gboolean
1276 show_fragment_seq_tree(fragment_data *fd_head, const fragment_items *fit,
1277     proto_tree *tree, packet_info *pinfo, tvbuff_t *tvb)
1278 {
1279         guint32 offset, next_offset;
1280         fragment_data *fd, *last_fd;
1281         proto_tree *ft;
1282         proto_item *fi;
1283
1284         /* It's not fragmented. */
1285         pinfo->fragmented = FALSE;
1286
1287         fi = proto_tree_add_item(tree, *(fit->hf_fragments),
1288             tvb, 0, -1, FALSE);
1289         ft = proto_item_add_subtree(fi, *(fit->ett_fragments));
1290         offset = 0;
1291         next_offset = 0;
1292         last_fd = NULL;
1293         for (fd = fd_head->next; fd != NULL; fd = fd->next){
1294                 if (last_fd == NULL || last_fd->offset != fd->offset) {
1295                         offset = next_offset;
1296                         next_offset += fd->len;
1297                 }
1298                 last_fd = fd;
1299                 show_fragment(fd, offset, fit, ft, tvb);
1300         }
1301
1302         return show_fragment_errs_in_col(fd_head, fit, pinfo);
1303 }