1a915879a049d4a05f8139db821ef9e7e0723c71
[dragonfly.git] / 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         }