Merge branch 'vendor/TCPDUMP' and update build for the update.
[dragonfly.git] / usr.sbin / tcpdump / tcpslice / search.c
CommitLineData
984263bc
MD
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.
1de703da
MD
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 $
984263bc 23 */
984263bc
MD
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
43extern 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 */
74static int
75reasonable_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
96static void
97extract_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
159static int
160find_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 */
266int
267sf_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
360static double
361timeval_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
372int
373sf_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
386static long
387interpolated_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
409static int
410read_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
466int
467sf_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 }