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