Branch data Line data Source code
1 : : // $Id: PacketSort.cc 3228 2006-06-08 02:12:03Z vern $
2 : :
3 : : #include "IP.h"
4 : : #include "PacketSort.h"
5 : :
6 : : const bool DEBUG_packetsort = false;
7 : :
8 : : PacketSortElement::PacketSortElement(PktSrc* arg_src,
9 : : double arg_timestamp, const struct pcap_pkthdr* arg_hdr,
10 : 0 : const u_char* arg_pkt, int arg_hdr_size)
11 : : {
12 : 0 : src = arg_src;
13 : 0 : timestamp = arg_timestamp;
14 : 0 : hdr = *arg_hdr;
15 : 0 : hdr_size = arg_hdr_size;
16 : :
17 : 0 : pkt = new u_char[hdr.caplen];
18 : 0 : memcpy(pkt, arg_pkt, hdr.caplen);
19 : :
20 : 0 : is_tcp = 0;
21 : 0 : ip_hdr = 0;
22 : 0 : key = 0;
23 : :
24 : : // Now check if it is a "parsable" TCP packet.
25 : 0 : uint32 caplen = hdr.caplen;
26 : : uint32 tcp_offset;
27 : :
28 [ # # # # ]: 0 : if ( caplen >= sizeof(struct ip) + hdr_size )
29 : : {
30 : 0 : const struct ip* ip = (const struct ip*) (pkt + hdr_size);
31 [ # # ][ # # ]: 0 : if ( ip->ip_v == 4 )
32 : 0 : ip_hdr = new IP_Hdr(ip);
33 : : else
34 : 0 : ip_hdr = new IP_Hdr((const struct ip6_hdr*) ip);
35 : :
36 [ # # ][ # # ]: 0 : if ( ip_hdr->NextProto() == IPPROTO_TCP &&
[ # # ][ # # ]
[ # # ][ # # ]
37 : : // Note: can't sort fragmented packets
38 : : (ip_hdr->FragField() & 0x3fff) == 0 )
39 : : {
40 : 0 : tcp_offset = hdr_size + ip_hdr->HdrLen();
41 [ # # # # ]: 0 : if ( caplen >= tcp_offset + sizeof(struct tcphdr) )
42 : : {
43 : : const struct tcphdr* tp = (const struct tcphdr*)
44 : 0 : (pkt + tcp_offset);
45 : :
46 : 0 : id.src_addr = ip_hdr->SrcAddr();
47 : 0 : id.dst_addr = ip_hdr->DstAddr();
48 : 0 : id.src_port = tp->th_sport;
49 : 0 : id.dst_port = tp->th_dport;
50 : 0 : id.is_one_way = 0;
51 : :
52 : : endp = addr_port_canon_lt(id.src_addr,
53 : : id.src_port,
54 : : id.dst_addr,
55 : 0 : id.dst_port) ? 0 : 1;
56 : :
57 : 0 : seq[endp] = ntohl(tp->th_seq);
58 : :
59 [ # # # # ]: 0 : if ( tp->th_flags & TH_ACK )
60 : 0 : seq[1-endp] = ntohl(tp->th_ack);
61 : : else
62 : 0 : seq[1-endp] = 0;
63 : :
64 : 0 : tcp_flags = tp->th_flags;
65 : :
66 : : // DEBUG_MSG("%.6f: %u, %u\n", timestamp, seq[0], seq[1]);
67 : :
68 : 0 : payload_length = ip_hdr->PayloadLen() - tp->th_off * 4;
69 : :
70 : 0 : key = id.BuildConnKey();
71 : :
72 : 0 : is_tcp = 1;
73 : : }
74 : : }
75 : : }
76 : :
77 : : if ( DEBUG_packetsort && ! is_tcp )
78 : : DEBUG_MSG("%.6f non-TCP packet\n", timestamp);
79 : 0 : }
80 : :
81 : 0 : PacketSortElement::~PacketSortElement()
82 : : {
83 [ # # ][ # # ]: 0 : delete [] pkt;
84 [ # # ][ # # ]: 0 : delete ip_hdr;
85 [ # # ][ # # ]: 0 : delete key;
86 : 0 : }
87 : :
88 : 0 : int PacketSortPQ::Timestamp_Cmp(PacketSortElement* a, PacketSortElement* b)
89 : : {
90 : 0 : double d = a->timestamp - b->timestamp;
91 : :
92 [ # # ]: 0 : if ( d > 0 ) return 1;
93 [ # # ]: 0 : else if ( d < 0 ) return -1;
94 : 0 : else return 0;
95 : : }
96 : :
97 : 0 : int PacketSortPQ::UpdatePQ(PacketSortElement* prev_e, PacketSortElement* new_e)
98 : : {
99 : 0 : int index = prev_e->pq_index[pq_level];
100 : :
101 : 0 : new_e->pq_index[pq_level] = index;
102 : 0 : pq[index] = new_e;
103 : :
104 [ # # ]: 0 : if ( Cmp(prev_e, new_e) > 0 )
105 : 0 : return FixUp(new_e, index);
106 : : else
107 : : {
108 : 0 : FixDown(new_e, index);
109 : 0 : return index == 0;
110 : : }
111 : : }
112 : :
113 : 0 : int PacketSortPQ::AddToPQ(PacketSortElement* new_e)
114 : : {
115 : 0 : int index = pq.size();
116 : :
117 : 0 : new_e->pq_index[pq_level] = index;
118 : 0 : pq.push_back(new_e);
119 : :
120 : 0 : return FixUp(new_e, index);
121 : : }
122 : :
123 : 0 : int PacketSortPQ::RemoveFromPQ(PacketSortElement* prev_e)
124 : : {
125 [ # # ]: 0 : if ( pq.size() > 1 )
126 : : {
127 : 0 : PacketSortElement* new_e = pq[pq.size() - 1];
128 : 0 : pq.pop_back();
129 : 0 : return UpdatePQ(prev_e, new_e);
130 : : }
131 : : else
132 : : {
133 : 0 : pq.pop_back();
134 : 0 : return 1;
135 : : }
136 : : }
137 : :
138 : 0 : void PacketSortPQ::Assign(int k, PacketSortElement* e)
139 : : {
140 : 0 : pq[k] = e;
141 : 0 : e->pq_index[pq_level] = k;
142 : 0 : }
143 : :
144 : 0 : PacketSortConnPQ::~PacketSortConnPQ()
145 : : {
146 : : // Delete elements only in ConnPQ (not in GlobalPQ) to avoid
147 : : // double delete.
148 [ # # ][ # # ]: 0 : for ( int i = 0; i < (int) pq.size(); ++i )
[ # # ]
149 : : {
150 [ # # ][ # # ]: 0 : delete pq[i];
[ # # ]
151 : 0 : pq[i] = 0;
152 : : }
153 [ # # ][ # # ]: 0 : }
[ # # ]
154 : :
155 : 0 : int PacketSortConnPQ::Cmp(PacketSortElement* a, PacketSortElement* b)
156 : : {
157 : : // Note: here we do not distinguish between packets without
158 : : // an ACK and packets with seq/ack of 0. The later will sorted
159 : : // only by their timestamps.
160 : :
161 [ # # ][ # # ]: 0 : if ( a->seq[0] && b->seq[0] && a->seq[0] != b->seq[0] )
[ # # ]
162 [ # # ]: 0 : return (a->seq[0] > b->seq[0]) ? 1 : -1;
163 : :
164 [ # # ][ # # ]: 0 : else if ( a->seq[1] && b->seq[1] && a->seq[1] != b->seq[1] )
[ # # ]
165 [ # # ]: 0 : return (a->seq[1] > b->seq[1]) ? 1 : -1;
166 : :
167 : : else
168 : 0 : return Timestamp_Cmp(a, b);
169 : : }
170 : :
171 : 0 : int PacketSortPQ::FixUp(PacketSortElement* e, int k)
172 : : {
173 [ # # ]: 0 : if ( k == 0 )
174 : : {
175 : 0 : Assign(0, e);
176 : 0 : return 1;
177 : : }
178 : :
179 : 0 : int parent = (k-1) / 2;
180 [ # # ]: 0 : if ( Cmp(pq[parent], e) > 0 )
181 : : {
182 : 0 : Assign(k, pq[parent]);
183 : 0 : return FixUp(e, parent);
184 : : }
185 : : else
186 : : {
187 : 0 : Assign(k, e);
188 : 0 : return 0;
189 : : }
190 : : }
191 : :
192 : 0 : void PacketSortPQ::FixDown(PacketSortElement* e, int k)
193 : : {
194 : 0 : uint32 kid = k * 2 + 1;
195 : :
196 [ # # ]: 0 : if ( kid >= pq.size() )
197 : : {
198 : 0 : Assign(k, e);
199 : 0 : return;
200 : : }
201 : :
202 [ # # ][ # # ]: 0 : if ( kid + 1 < pq.size() && Cmp(pq[kid], pq[kid+1]) > 0 )
[ # # ]
203 : 0 : ++kid;
204 : :
205 [ # # ]: 0 : if ( Cmp(e, pq[kid]) > 0 )
206 : : {
207 : 0 : Assign(k, pq[kid]);
208 : 0 : FixDown(e, kid);
209 : : }
210 : : else
211 : 0 : Assign(k, e);
212 : : }
213 : :
214 : :
215 : 0 : int PacketSortConnPQ::Add(PacketSortElement* e)
216 : : {
217 : : #if 0
218 : : int endp = e->endp;
219 : : uint32 end_seq = e->seq[endp] + e->payload_length;
220 : :
221 : : int p = 1 - endp;
222 : : if ( (e->tcp_flags & TH_RST) && ! (e->tcp_flags & TH_ACK) )
223 : : {
224 : : DEBUG_MSG("%.6f %c: %u -> %u\n",
225 : : e->TimeStamp(), (p == endp) ? 'S' : 'A',
226 : : e->seq[p], next_seq[p]);
227 : : e->seq[p] = next_seq[p];
228 : : }
229 : :
230 : : if ( end_seq > next_seq[endp] )
231 : : next_seq[endp] = end_seq;
232 : : #endif
233 : :
234 : 0 : return AddToPQ(e);
235 : : }
236 : :
237 : 0 : void PacketSortConnPQ::UpdateDeliveredSeq(int endp, int seq, int len, int ack)
238 : : {
239 [ # # ][ # # ]: 0 : if ( delivered_seq[endp] == 0 || delivered_seq[endp] == seq )
240 : 0 : delivered_seq[endp] = seq + len;
241 [ # # ]: 0 : if ( ack > delivered_seq[1 - endp] )
242 : 0 : delivered_seq[endp] = ack;
243 : 0 : }
244 : :
245 : 0 : bool PacketSortConnPQ::IsContentGapSafe(PacketSortElement* e)
246 : : {
247 : 0 : int ack = e->seq[1 - e->endp];
248 : 0 : return ack <= delivered_seq[1 - e->endp];
249 : : }
250 : :
251 : 0 : int PacketSortConnPQ::Remove(PacketSortElement* e)
252 : : {
253 : 0 : int ret = RemoveFromPQ(e);
254 : : UpdateDeliveredSeq(e->endp, e->seq[e->endp], e->payload_length,
255 : 0 : e->seq[1 - e->endp]);
256 : 0 : return ret;
257 : : }
258 : :
259 : 0 : static void DeleteConnPQ(void* p)
260 : : {
261 [ # # ]: 0 : delete (PacketSortConnPQ*) p;
262 : 0 : }
263 : :
264 : 0 : PacketSortGlobalPQ::PacketSortGlobalPQ()
265 : : {
266 : 0 : pq_level = GLOBAL_PQ;
267 : 0 : conn_pq_table.SetDeleteFunc(DeleteConnPQ);
268 : 0 : }
269 : :
270 : 0 : PacketSortGlobalPQ::~PacketSortGlobalPQ()
271 : : {
272 : : // Destruction of PacketSortConnPQ will delete all conn_pq's.
273 [ # # ][ # # ]: 0 : }
[ # # ]
274 : :
275 : 0 : int PacketSortGlobalPQ::Add(PacketSortElement* e)
276 : : {
277 [ # # ]: 0 : if ( e->is_tcp )
278 : : {
279 : : // TCP packets are sorted by sequence numbers
280 : 0 : PacketSortConnPQ* conn_pq = FindConnPQ(e);
281 : 0 : PacketSortElement* prev_min = conn_pq->Min();
282 : :
283 [ # # ]: 0 : if ( conn_pq->Add(e) )
284 : : {
285 [ # # ]: 0 : ASSERT(conn_pq->Min() != prev_min);
286 : :
287 [ # # ]: 0 : if ( prev_min )
288 : 0 : return UpdatePQ(prev_min, e);
289 : : else
290 : 0 : return AddToPQ(e);
291 : : }
292 : :
293 : : else
294 : : {
295 [ # # ]: 0 : ASSERT(conn_pq->Min() == prev_min);
296 : 0 : return 0;
297 : : }
298 : : }
299 : : else
300 : 0 : return AddToPQ(e);
301 : : }
302 : :
303 : 0 : PacketSortElement* PacketSortGlobalPQ::RemoveMin(double timestamp)
304 : : {
305 : 0 : PacketSortElement* e = Min();
306 : :
307 [ # # ]: 0 : if ( ! e )
308 : 0 : return 0;
309 : :
310 [ # # ]: 0 : if ( e->is_tcp )
311 : : {
312 : 0 : PacketSortConnPQ* conn_pq = FindConnPQ(e);
313 : :
314 : : #if 0
315 : : // Note: the content gap safety check does not work
316 : : // because we remove the state for a connection once
317 : : // it has no packet in the priority queue.
318 : :
319 : : // Do not deliver e if it arrives later than timestamp,
320 : : // and is not content-gap-safe.
321 : : if ( e->timestamp > timestamp &&
322 : : ! conn_pq->IsContentGapSafe(e) )
323 : : return 0;
324 : : #else
325 [ # # ]: 0 : if ( e->timestamp > timestamp )
326 : 0 : return 0;
327 : : #endif
328 : :
329 : 0 : conn_pq->Remove(e);
330 : 0 : PacketSortElement* new_e = conn_pq->Min();
331 : :
332 [ # # ]: 0 : if ( new_e )
333 : 0 : UpdatePQ(e, new_e);
334 : : else
335 : : {
336 : 0 : RemoveFromPQ(e);
337 : 0 : conn_pq_table.Remove(e->key);
338 [ # # ]: 0 : delete conn_pq;
339 : : }
340 : : }
341 : : else
342 : 0 : RemoveFromPQ(e);
343 : :
344 : 0 : return e;
345 : : }
346 : :
347 : 0 : PacketSortConnPQ* PacketSortGlobalPQ::FindConnPQ(PacketSortElement* e)
348 : : {
349 [ # # ]: 0 : if ( ! e->is_tcp )
350 : 0 : internal_error("cannot find a connection for an invalid id");
351 : :
352 : 0 : PacketSortConnPQ* pq = (PacketSortConnPQ*) conn_pq_table.Lookup(e->key);
353 [ # # ]: 0 : if ( ! pq )
354 : : {
355 : 0 : pq = new PacketSortConnPQ();
356 : 0 : conn_pq_table.Insert(e->key, pq);
357 : : }
358 : :
359 : 0 : return pq;
360 [ + - ][ + - ]: 6 : }
|
