usr.sbin/tcpdump/tcpslice/search.c

   1 /*
   2  * Copyright (c) 1990, 1991, 1992, 1993
   3  * The Regents of the University of California. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that: (1) source code distributions
   7  * retain the above copyright notice and this paragraph in its entirety, (2)
   8  * distributions including binary code include the above copyright notice and
   9  * this paragraph in its entirety in the documentation or other materials
  10  * provided with the distribution, and (3) all advertising materials mentioning
  11  * features or use of this software display the following acknowledgement:
  12  * ``This product includes software developed by the University of California,
  13  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  14  * the University nor the names of its contributors may be used to endorse
  15  * or promote products derived from this software without specific prior
  16  * written permission.
  17  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20  *
  21  * $FreeBSD: src/usr.sbin/tcpdump/tcpslice/search.c,v 1.4 1999/08/28 05:11:32 peter Exp $
  22  * $DragonFly: src/usr.sbin/tcpdump/tcpslice/search.c,v 1.2 2003/06/17 04:30:03 dillon Exp $
  23  */
  24
  25 /*
  26  * search.c - supports fast searching through tcpdump files for timestamps
  27  */
  28
  29 #include "tcpslice.h"
  30
  31
  32 /* Maximum number of seconds that we can conceive of a dump file spanning. */
  33 #define MAX_REASONABLE_FILE_SPAN (3600*24*366)  /* one year */
  34
  35 /* Maximum packet length we ever expect to see. */
  36 #define MAX_REASONABLE_PACKET_LENGTH 65535
  37
  38 /* Size of a packet header in bytes; easier than typing the sizeof() all
  39  * the time ...
  40  */
  41 #define PACKET_HDR_LEN (sizeof( struct pcap_pkthdr ))
  42
  43 extern int snaplen;
  44
  45 /* The maximum size of a packet, including its header. */
  46 #define MAX_PACKET_SIZE (PACKET_HDR_LEN + snaplen)
  47
  48 /* Number of contiguous bytes from a dumpfile in which there's guaranteed
  49  * to be enough information to find a "definite" header if one exists
  50  * therein.  This takes 3 full packets - the first to be just misaligned
  51  * (one byte short of a full packet), missing its timestamp; the second
  52  * to have the legitimate timestamp; and the third to provide confirmation
  53  * that the second is legit, making it a "definite" header.  We could
  54  * scrimp a bit here since not the entire third packet is required, but
  55  * it doesn't seem worth it
  56  */
  57 #define MAX_BYTES_FOR_DEFINITE_HEADER (3 * MAX_PACKET_SIZE)
  58
  59 /* Maximum number of seconds that might reasonably separate two headers. */
  60 #define MAX_REASONABLE_HDR_SEPARATION (3600 * 24 * 7)   /* one week */
  61
  62 /* When searching a file for a packet, if we think we're within this many
  63  * bytes of the packet we just search linearly.  Since linear searches are
  64  * probably much faster than random ones (random ones require searching for
  65  * the beginning of the packet, which may be unaligned in memory), we make
  66  * this value pretty hefty.
  67  */
  68 #define STRAIGHT_SCAN_THRESHOLD (100 * MAX_PACKET_SIZE)
  69
  70
  71 /* Given a header and an acceptable first and last time stamp, returns non-zero
  72  * if the header looks reasonable and zero otherwise.
  73  */
  74 static int
  75 reasonable_header( struct pcap_pkthdr *hdr, long first_time, long last_time )
  76         {
  77         if ( last_time == 0 )
  78                 last_time = first_time + MAX_REASONABLE_FILE_SPAN;
  79
  80         return hdr->ts.tv_sec >= first_time &&
  81                hdr->ts.tv_sec <= last_time &&
  82                hdr->len > 0 &&
  83                hdr->len <= MAX_REASONABLE_PACKET_LENGTH &&
  84                hdr->caplen > 0 &&
  85                hdr->caplen <= MAX_REASONABLE_PACKET_LENGTH;
  86         }
  87
  88
  89 #define SWAPLONG(y) \
  90 ((((y)&0xff)<<24) | (((y)&0xff00)<<8) | (((y)&0xff0000)>>8) | (((y)>>24)&0xff))
  91 #define SWAPSHORT(y) \
  92         ( (((y)&0xff)<<8) | (((y)&0xff00)>>8) )
  93
  94 /* Given a buffer, extracts a (properly aligned) packet header from it. */
  95
  96 static void
  97 extract_header( pcap_t *p, u_char *buf, struct pcap_pkthdr *hdr )
  98         {
  99         bcopy((char *) buf, (char *) hdr, sizeof(struct pcap_pkthdr));
 100
 101         if ( pcap_is_swapped( p ) )
 102                 {
 103                 hdr->ts.tv_sec = SWAPLONG(hdr->ts.tv_sec);
 104                 hdr->ts.tv_usec = SWAPLONG(hdr->ts.tv_usec);
 105                 hdr->len = SWAPLONG(hdr->len);
 106                 hdr->caplen = SWAPLONG(hdr->caplen);
 107                 }
 108
 109         /*
 110          * From bpf/libpcap/savefile.c:
 111          *
 112          * We interchanged the caplen and len fields at version 2.3,
 113          * in order to match the bpf header layout.  But unfortunately
 114          * some files were written with version 2.3 in their headers
 115          * but without the interchanged fields.
 116          */
 117         if ( pcap_minor_version( p ) < 3 ||
 118              (pcap_minor_version( p ) == 3 && hdr->caplen > hdr->len) )
 119                 {
 120                 int t = hdr->caplen;
 121                 hdr->caplen = hdr->len;
 122                 hdr->len = t;
 123                 }
 124         }
 125
 126
 127 /* Search a buffer to locate the first header within it.  Return values
 128  * are HEADER_NONE, HEADER_CLASH, HEADER_PERHAPS, and HEADER_DEFINITELY.
 129  * The first indicates that no evidence of a header was found; the second
 130  * that two or more possible headers were found, neither more convincing
 131  * than the other(s); the third that exactly one "possible" header was
 132  * found; and the fourth that exactly one "definite" header was found.
 133  *
 134  * Headers are detected by looking for positions in the buffer which have
 135  * reasonable timestamps and lengths.  If there is enough room in the buffer
 136  * for another header to follow a candidate header, a check is made for
 137  * that following header.  If it is present then the header is *definite*
 138  * (unless another "perhaps" or "definite" header is found); if not, then
 139  * the header is discarded.  If there is not enough room in the buffer for
 140  * another header then the candidate is *perhaps* (unless another header
 141  * is subsequently found).  A "tie" between a "definite" header and a
 142  * "perhaps" header is resolved in favor of the definite header.  Any
 143  * other tie leads to HEADER_CLASH.
 144  *
 145  * The buffer position of the header is returned in hdrpos_addr and
 146  * for convenience the corresponding header in return_hdr.
 147  *
 148  * first_time is the earliest possible acceptable timestamp in the
 149  * header.  last_time, if non-zero, is the last such timestamp.  If
 150  * zero, then up to MAX_REASONABLE_FILE_SPAN seconds after first_time
 151  * is acceptable.
 152  */
 153
 154 #define HEADER_NONE 0
 155 #define HEADER_CLASH 1
 156 #define HEADER_PERHAPS 2
 157 #define HEADER_DEFINITELY 3
 158
 159 static int
 160 find_header( pcap_t *p, u_char *buf, int buf_len,
 161                 long first_time, long last_time,
 162                 u_char **hdrpos_addr, struct pcap_pkthdr *return_hdr )
 163         {
 164         u_char *bufptr, *bufend, *last_pos_to_try;
 165         struct pcap_pkthdr hdr, hdr2;
 166         int status = HEADER_NONE;
 167         int saw_PERHAPS_clash = 0;
 168
 169         /* Initially, try each buffer position to see whether it looks like
 170          * a valid packet header.  We may later restrict the positions we look
 171          * at to avoid seeing a sequence of legitimate headers as conflicting
 172          * with one another.
 173          */
 174         bufend = buf + buf_len;
 175         last_pos_to_try = bufend - PACKET_HDR_LEN;
 176
 177         for ( bufptr = buf; bufptr < last_pos_to_try; ++bufptr )
 178             {
 179             extract_header( p, bufptr, &hdr );
 180
 181             if ( reasonable_header( &hdr, first_time, last_time ) )
 182                 {
 183                 u_char *next_header = bufptr + PACKET_HDR_LEN + hdr.caplen;
 184
 185                 if ( next_header + PACKET_HDR_LEN < bufend )
 186                     { /* check for another good header */
 187                     extract_header( p, next_header, &hdr2 );
 188
 189                     if ( reasonable_header( &hdr2, hdr.ts.tv_sec,
 190                             hdr.ts.tv_sec + MAX_REASONABLE_HDR_SEPARATION ) )
 191                         { /* a confirmed header */
 192                         switch ( status )
 193                             {
 194                             case HEADER_NONE:
 195                             case HEADER_PERHAPS:
 196                                 status = HEADER_DEFINITELY;
 197                                 *hdrpos_addr = bufptr;
 198                                 *return_hdr = hdr;
 199
 200                                 /* Make sure we don't demote this "definite"
 201                                  * to a "clash" if we stumble across its
 202                                  * successor.
 203                                  */
 204                                 last_pos_to_try = next_header - PACKET_HDR_LEN;
 205                                 break;
 206
 207                             case HEADER_DEFINITELY:
 208                                 return HEADER_CLASH;
 209
 210                             default:
 211                                 error( "bad status in find_header()" );
 212                             }
 213                         }
 214
 215                     /* ... else the header is bogus - we've verified that it's
 216                      * not followed by a reasonable header.
 217                      */
 218                     }
 219
 220                 else
 221                     { /* can't check for another good header */
 222                     switch ( status )
 223                         {
 224                         case HEADER_NONE:
 225                             status = HEADER_PERHAPS;
 226                             *hdrpos_addr = bufptr;
 227                             *return_hdr = hdr;
 228                             break;
 229
 230                         case HEADER_PERHAPS:
 231                             /* We don't immediately turn this into a
 232                              * clash because perhaps we'll later see a
 233                              * "definite" which will save us ...
 234                              */
 235                             saw_PERHAPS_clash = 1;
 236                             break;
 237
 238                         case HEADER_DEFINITELY:
 239                             /* Keep the definite in preference to this one. */
 240                             break;
 241
 242                         default:
 243                             error( "bad status in find_header()" );
 244                         }
 245                     }
 246                 }
 247             }
 248
 249         if ( status == HEADER_PERHAPS && saw_PERHAPS_clash )
 250                 status = HEADER_CLASH;
 251
 252         return status;
 253         }
 254
 255
 256 /* Positions the sf_readfile stream such that the next sf_read() will
 257  * read the final full packet in the file.  Returns non-zero if
 258  * successful, zero if unsuccessful.  If successful, returns the
 259  * timestamp of the last packet in last_timestamp.
 260  *
 261  * Note that this routine is a special case of sf_find_packet().  In
 262  * order to use sf_find_packet(), one first must use this routine in
 263  * order to give sf_find_packet() an upper bound on the timestamps
 264  * present in the dump file.
 265  */
 266 int
 267 sf_find_end( pcap_t *p, struct timeval *first_timestamp,
 268                 struct timeval *last_timestamp )
 269         {
 270         long first_time = first_timestamp->tv_sec;
 271         u_int num_bytes;
 272         u_char *buf, *bufpos, *bufend;
 273         u_char *hdrpos;
 274         struct pcap_pkthdr hdr, successor_hdr;
 275         int status;
 276
 277         /* Allow enough room for at least two full (untruncated) packets,
 278          * perhaps followed by a truncated packet, so we have a shot at
 279          * finding a "definite" header and following its chain to the
 280          * end of the file.
 281          */
 282         num_bytes = MAX_BYTES_FOR_DEFINITE_HEADER;
 283         if ( fseek( pcap_file( p ), (long) -num_bytes, 2 ) < 0 )
 284                 return 0;
 285
 286         buf = (u_char *)malloc((u_int) num_bytes);
 287         if ( ! buf )
 288                 return 0;
 289
 290         status = 0;
 291         bufpos = buf;
 292         bufend = buf + num_bytes;
 293
 294         if ( fread( (char *) bufpos, num_bytes, 1, pcap_file( p ) ) != 1 )
 295                 goto done;
 296
 297         if ( find_header( p, bufpos, num_bytes,
 298                           first_time, 0L, &hdrpos, &hdr ) != HEADER_DEFINITELY )
 299                 goto done;
 300
 301         /* Okay, we have a definite header in our hands.  Follow its
 302          * chain till we find the last valid packet in the file ...
 303          */
 304         for ( ; ; )
 305                 {
 306                 /* move to the next header position */
 307                 bufpos = hdrpos + PACKET_HDR_LEN + hdr.caplen;
 308
 309                 /* bufpos now points to a candidate packet, which if valid
 310                  * should replace the current packet pointed to by hdrpos as
 311                  * the last valid packet ...
 312                  */
 313                 if ( bufpos >= bufend - PACKET_HDR_LEN )
 314                         /* not enough room for another header */
 315                         break;
 316
 317                 extract_header( p, bufpos, &successor_hdr );
 318
 319                 first_time = hdr.ts.tv_sec;
 320                 if ( ! reasonable_header( &successor_hdr, first_time, 0L ) )
 321                         /* this bodes ill - it means bufpos is perhaps a
 322                          * bogus packet header after all ...
 323                          */
 324                         break;
 325
 326                 /* Note that the following test is for whether the next
 327                  * packet starts at a position > bufend, *not* for a
 328                  * position >= bufend.  If this is the last packet in the
 329                  * file and there isn't a subsequent partial packet, then
 330                  * we expect the first buffer position beyond this packet
 331                  * to be just beyond the end of the buffer, i.e., at bufend
 332                  * itself.
 333                  */
 334                 if ( bufpos + PACKET_HDR_LEN + successor_hdr.caplen > bufend )
 335                         /* the packet is truncated */
 336                         break;
 337
 338                 /* Accept this packet as fully legit. */
 339                 hdrpos = bufpos;
 340                 hdr = successor_hdr;
 341                 }
 342
 343         /* Success!  Last valid packet is at hdrpos. */
 344         *last_timestamp = hdr.ts;
 345         status = 1;
 346
 347         /* Seek so that the next read will start at last valid packet. */
 348         if ( fseek( pcap_file( p ), (long) -(bufend - hdrpos), 2 ) < 0 )
 349                 error( "final fseek() failed in sf_find_end()" );
 350
 351     done:
 352         free( (char *) buf );
 353
 354         return status;
 355         }
 356
 357
 358 /* Takes two timeval's and returns the difference, tv2 - tv1, as a double. */
 359
 360 static double
 361 timeval_diff( struct timeval *tv1, struct timeval *tv2 )
 362         {
 363         double result = (tv2->tv_sec - tv1->tv_sec);
 364         result += (tv2->tv_usec - tv1->tv_usec) / 1000000.0;
 365
 366         return result;
 367         }
 368
 369
 370 /* Returns true if timestamp t1 is chronologically less than timestamp t2. */
 371
 372 int
 373 sf_timestamp_less_than( struct timeval *t1, struct timeval *t2 )
 374         {
 375         return t1->tv_sec < t2->tv_sec ||
 376                (t1->tv_sec == t2->tv_sec &&
 377                 t1->tv_usec < t2->tv_usec);
 378         }
 379
 380
 381 /* Given two timestamps on either side of desired_time and their positions,
 382  * returns the interpolated position of the desired_time packet.  Returns a
 383  * negative value if the desired_time is outside the given range.
 384  */
 385
 386 static long
 387 interpolated_position( struct timeval *min_time, long min_pos,
 388                         struct timeval *max_time, long max_pos,
 389                         struct timeval *desired_time )
 390         {
 391         double full_span = timeval_diff( max_time, min_time );
 392         double desired_span = timeval_diff( desired_time, min_time );
 393         long full_span_pos = max_pos - min_pos;
 394         double fractional_offset = desired_span / full_span;
 395
 396         if ( fractional_offset < 0.0 || fractional_offset > 1.0 )
 397                 return -1;
 398
 399         return min_pos + (long) (fractional_offset * (double) full_span_pos);
 400         }
 401
 402
 403 /* Reads packets linearly until one with a time >= the given desired time
 404  * is found; positions the dump file so that the next read will start
 405  * at the given packet.  Returns non-zero on success, 0 if an EOF was
 406  * first encountered.
 407  */
 408
 409 static int
 410 read_up_to( pcap_t *p, struct timeval *desired_time )
 411         {
 412         struct pcap_pkthdr hdr;
 413         const u_char *buf;
 414         long pos;
 415         int status;
 416
 417         for ( ; ; )
 418                 {
 419                 struct timeval *timestamp;
 420
 421                 pos = ftell( pcap_file( p ) );
 422                 buf = pcap_next( p, &hdr );
 423
 424                 if ( buf == 0 )
 425                         {
 426                         if ( feof( pcap_file( p ) ) )
 427                                 {
 428                                 status = 0;
 429                                 clearerr( pcap_file( p ) );
 430                                 break;
 431                                 }
 432
 433                         error( "bad status in read_up_to()" );
 434                         }
 435
 436                 timestamp = &hdr.ts;
 437
 438                 if ( ! sf_timestamp_less_than( timestamp, desired_time ) )
 439                         {
 440                         status = 1;
 441                         break;
 442                         }
 443                 }
 444
 445         if ( fseek( pcap_file( p ), pos, 0 ) < 0 )
 446                 error( "fseek() failed in read_up_to()" );
 447
 448         return (status);
 449         }
 450
 451
 452 /* Positions the sf_readfile stream so that the next sf_read() will
 453  * return the first packet with a time greater than or equal to
 454  * desired_time.  desired_time must be greater than min_time and less
 455  * than max_time, which should correspond to actual packets in the
 456  * file.  min_pos is the file position (byte offset) corresponding to
 457  * the min_time packet and max_pos is the same for the max_time packet.
 458  *
 459  * Returns non-zero on success, 0 if the given position is beyond max_pos.
 460  *
 461  * NOTE: when calling this routine, the sf_readfile stream *must* be
 462  * already aligned so that the next call to sf_next_packet() will yield
 463  * a valid packet.
 464  */
 465
 466 int
 467 sf_find_packet( pcap_t *p,
 468                 struct timeval *min_time, long min_pos,
 469                 struct timeval *max_time, long max_pos,
 470                 struct timeval *desired_time )
 471         {
 472         int status = 1;
 473         struct timeval min_time_copy, max_time_copy;
 474         u_int num_bytes = MAX_BYTES_FOR_DEFINITE_HEADER;
 475         int num_bytes_read;
 476         long desired_pos, present_pos;
 477         u_char *buf, *hdrpos;
 478         struct pcap_pkthdr hdr;
 479
 480         buf = (u_char *) malloc( num_bytes );
 481         if ( ! buf )
 482                 error( "malloc() failured in sf_find_packet()" );
 483
 484         min_time_copy = *min_time;
 485         min_time = &min_time_copy;
 486
 487         max_time_copy = *max_time;
 488         max_time = &max_time_copy;
 489
 490         for ( ; ; )     /* loop until positioned correctly */
 491                 {
 492                 desired_pos =
 493                         interpolated_position( min_time, min_pos,
 494                                                max_time, max_pos,
 495                                                desired_time );
 496
 497                 if ( desired_pos < 0 )
 498                         {
 499                         status = 0;
 500                         break;
 501                         }
 502
 503                 present_pos = ftell( pcap_file( p ) );
 504
 505                 if ( present_pos <= desired_pos &&
 506                      desired_pos - present_pos < STRAIGHT_SCAN_THRESHOLD )
 507                         { /* we're close enough to just blindly read ahead */
 508                         status = read_up_to( p, desired_time );
 509                         break;
 510                         }
 511
 512                 /* Undershoot the target a little bit - it's much easier to
 513                  * then scan straight forward than to try to read backwards ...
 514                  */
 515                 desired_pos -= STRAIGHT_SCAN_THRESHOLD / 2;
 516                 if ( desired_pos < min_pos )
 517                         desired_pos = min_pos;
 518
 519                 if ( fseek( pcap_file( p ), desired_pos, 0 ) < 0 )
 520                         error( "fseek() failed in sf_find_packet()" );
 521
 522                 num_bytes_read =
 523                         fread( (char *) buf, 1, num_bytes, pcap_file( p ) );
 524
 525                 if ( num_bytes_read == 0 )
 526                         /* This shouldn't ever happen because we try to
 527                          * undershoot, unless the dump file has only a
 528                          * couple packets in it ...
 529                          */
 530                         error( "fread() failed in sf_find_packet()" );
 531
 532                 if ( find_header( p, buf, num_bytes, min_time->tv_sec,
 533                                   max_time->tv_sec, &hdrpos, &hdr ) !=
 534                      HEADER_DEFINITELY )
 535                         error( "can't find header at position %ld in dump file",
 536                                 desired_pos );
 537
 538                 /* Correct desired_pos to reflect beginning of packet. */
 539                 desired_pos += (hdrpos - buf);
 540
 541                 /* Seek to the beginning of the header. */
 542                 if ( fseek( pcap_file( p ), desired_pos, 0 ) < 0 )
 543                         error( "fseek() failed in sf_find_packet()" );
 544
 545                 if ( sf_timestamp_less_than( &hdr.ts, desired_time ) )
 546                         { /* too early in the file */
 547                         *min_time = hdr.ts;
 548                         min_pos = desired_pos;
 549                         }
 550
 551                 else if ( sf_timestamp_less_than( desired_time, &hdr.ts ) )
 552                         { /* too late in the file */
 553                         *max_time = hdr.ts;
 554                         max_pos = desired_pos;
 555                         }
 556
 557                 else
 558                         /* got it! */
 559                         break;
 560                 }
 561
 562         free( (char *) buf );
 563
 564         return status;
 565         }