Branch data Line data Source code
1 : : // $Id: PacketSort.h 3228 2006-06-08 02:12:03Z vern $
2 : :
3 : : #ifndef packetsort_h
4 : : #define packetsort_h
5 : :
6 : : // Timestamps can be imprecise and even inconsistent among packets
7 : : // from different sources. This class tries to guess a "correct"
8 : : // order by looking at TCP sequence numbers.
9 : : //
10 : : // In particular, it tries to eliminate "false" content gaps.
11 : :
12 : : #include "Dict.h"
13 : : #include "Conn.h"
14 : :
15 : : enum {
16 : : CONN_PQ,
17 : : GLOBAL_PQ,
18 : : NUM_OF_PQ_LEVEL,
19 : : };
20 : :
21 : : class PktSrc;
22 : :
23 : : class PacketSortElement {
24 : : public:
25 : : PacketSortElement(PktSrc* src, double timestamp,
26 : : const struct pcap_pkthdr* hdr,
27 : : const u_char* pkt, int hdr_size);
28 : : ~PacketSortElement();
29 : :
30 : 0 : PktSrc* Src() const { return src; }
31 : 0 : double TimeStamp() const { return timestamp; }
32 : 0 : const struct pcap_pkthdr* Hdr() const { return &hdr; }
33 : 0 : const u_char* Pkt() const { return pkt; }
34 : 0 : int HdrSize() const { return hdr_size; }
35 : 0 : const IP_Hdr* IPHdr() const { return ip_hdr; }
36 : :
37 : : protected:
38 : : PktSrc* src;
39 : : double timestamp;
40 : : struct pcap_pkthdr hdr;
41 : : u_char* pkt;
42 : : int hdr_size;
43 : :
44 : : IP_Hdr* ip_hdr;
45 : : int is_tcp;
46 : : ConnID id;
47 : : uint32 seq[2]; // indexed by endpoint
48 : : int tcp_flags;
49 : : int endp; // 0 or 1
50 : : int payload_length;
51 : :
52 : : HashKey* key;
53 : :
54 : : int pq_index[NUM_OF_PQ_LEVEL];
55 : :
56 : : friend class PacketSortPQ;
57 : : friend class PacketSortConnPQ;
58 : : friend class PacketSortGlobalPQ;
59 : : };
60 : :
61 : : class PacketSortPQ {
62 : : public:
63 : 0 : PacketSortPQ()
64 : 0 : { pq_level = -1; }
65 [ # # ][ # # ]: 0 : virtual ~PacketSortPQ() {}
[ # # ]
66 : :
67 [ # # ]: 0 : PacketSortElement* Min() const { return (pq.size() > 0) ? pq[0] : 0; }
68 : :
69 : : protected:
70 : : virtual int Cmp(PacketSortElement* a, PacketSortElement* b) = 0;
71 : : int Timestamp_Cmp(PacketSortElement* a, PacketSortElement* b);
72 : :
73 : : int UpdatePQ(PacketSortElement* prev_e, PacketSortElement* new_e);
74 : : int AddToPQ(PacketSortElement* e);
75 : : int RemoveFromPQ(PacketSortElement* e);
76 : :
77 : : void Assign(int k, PacketSortElement* e);
78 : : int FixUp(PacketSortElement* e, int k);
79 : : void FixDown(PacketSortElement* e, int k);
80 : :
81 : : vector<PacketSortElement*> pq;
82 : : int pq_level;
83 : : };
84 : :
85 : : // Sort by sequence numbers within a connection
86 : : class PacketSortConnPQ : public PacketSortPQ {
87 : : public:
88 : 0 : PacketSortConnPQ()
89 : 0 : {
90 : 0 : pq_level = CONN_PQ;
91 : 0 : delivered_seq[0] = delivered_seq[1] = 0;
92 : 0 : }
93 : : ~PacketSortConnPQ();
94 : :
95 : : int Add(PacketSortElement* e);
96 : :
97 : : int Remove(PacketSortElement* e);
98 : :
99 : : bool IsContentGapSafe(PacketSortElement* e);
100 : :
101 : : protected:
102 : : int Cmp(PacketSortElement* a, PacketSortElement* b);
103 : : void UpdateDeliveredSeq(int endp, int seq, int len, int ack);
104 : :
105 : : int delivered_seq[2];
106 : : };
107 : :
108 [ # # ][ # # ]: 0 : declare(PDict, PacketSortConnPQ);
109 : :
110 : : // Sort by timestamps.
111 : : class PacketSortGlobalPQ : public PacketSortPQ {
112 : : public:
113 : : PacketSortGlobalPQ();
114 : : ~PacketSortGlobalPQ();
115 : :
116 : : int Add(PacketSortElement* e);
117 : :
118 : 0 : int Empty() const { return conn_pq_table.Length() == 0; }
119 : :
120 : : // Returns the next packet to dispatch if it arrives earlier than the
121 : : // given timestamp, otherwise returns 0.
122 : : // The packet, if to be returned, is also removed from the
123 : : // priority queue.
124 : : PacketSortElement* RemoveMin(double timestamp);
125 : :
126 : : protected:
127 : 0 : int Cmp(PacketSortElement* a, PacketSortElement* b)
128 : 0 : { return Timestamp_Cmp(a, b); }
129 : : PacketSortConnPQ* FindConnPQ(PacketSortElement* e);
130 : :
131 : : PDict(PacketSortConnPQ) conn_pq_table;
132 : : };
133 : :
134 : : #endif
|