Branch data Line data Source code
1 : : // $Id: Reassem.cc 6703 2009-05-13 22:27:44Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #include "Reassem.h"
8 : : #include "Serializer.h"
9 : :
10 : : const bool DEBUG_reassem = false;
11 : :
12 : : #ifdef DEBUG
13 : : int reassem_seen_bytes = 0;
14 : : int reassem_copied_bytes = 0;
15 : : #endif
16 : :
17 : : DataBlock::DataBlock(const u_char* data, int size, int arg_seq,
18 : 8168 : DataBlock* arg_prev, DataBlock* arg_next)
19 : : {
20 : 8168 : seq = arg_seq;
21 : 8168 : upper = seq + size;
22 : :
23 : 8168 : block = new u_char[size];
24 [ - + # # ]: 8168 : if ( ! block )
25 : 0 : internal_error("out of memory");
26 : :
27 : 8168 : memcpy((void*) block, (const void*) data, size);
28 : :
29 : : #ifdef DEBUG
30 : 8168 : reassem_copied_bytes += size;
31 : : #endif
32 : :
33 : 8168 : prev = arg_prev;
34 : 8168 : next = arg_next;
35 : :
36 [ + + # # ]: 8168 : if ( prev )
37 : 3484 : prev->next = this;
38 [ + + ][ # # ]: 8168 : if ( next )
39 : 207 : next->prev = this;
40 : :
41 : 8168 : Reassembler::total_size += pad_size(size) + padded_sizeof(DataBlock);
42 : 8168 : }
43 : :
44 : : unsigned int Reassembler::total_size = 0;
45 : :
46 : : Reassembler::Reassembler(int init_seq, const uint32* ip_addr,
47 : 1876 : ReassemblerType arg_type)
48 : : {
49 : 1876 : blocks = last_block = 0;
50 : 1876 : trim_seq = last_reassem_seq = init_seq;
51 : :
52 : : const NumericData* host_profile;
53 : 1876 : get_map_result(ip_addr[0], host_profile); // breaks for IPv6
54 : :
55 : : policy = (arg_type == REASSEM_TCP) ?
56 [ # # ][ + - ]: 1876 : host_profile->tcp_reassem : host_profile->ip_reassem;
57 : 1876 : }
58 : :
59 : :
60 : 1876 : Reassembler::~Reassembler()
61 : : {
62 : 1876 : ClearBlocks();
63 [ # # ][ # # ]: 1876 : }
[ - + ]
64 : :
65 : 8552 : void Reassembler::NewBlock(double t, int seq, int len, const u_char* data)
66 : : {
67 [ - + ]: 8552 : if ( len == 0 )
68 : 0 : return;
69 : :
70 : : #ifdef DEBUG
71 : 8552 : reassem_seen_bytes += len;
72 : : #endif
73 : :
74 : 8552 : int upper_seq = seq + len;
75 : :
76 [ + + ]: 8552 : if ( seq_delta(upper_seq, trim_seq) <= 0 )
77 : : // Old data, don't do any work for it.
78 : 157 : return;
79 : :
80 [ + + ]: 8395 : if ( seq_delta(seq, trim_seq) < 0 )
81 : : { // Partially old data, just keep the good stuff.
82 : 2 : int amount_old = seq_delta(trim_seq, seq);
83 : :
84 : 2 : data += amount_old;
85 : 2 : seq += amount_old;
86 : 2 : len -= amount_old;
87 : : }
88 : :
89 : : DataBlock* start_block;
90 : :
91 [ + + ]: 8395 : if ( ! blocks )
92 : : blocks = last_block = start_block =
93 : 4535 : new DataBlock(data, len, seq, 0, 0);
94 : : else
95 : 3860 : start_block = AddAndCheck(blocks, seq, upper_seq, data);
96 : :
97 : 8552 : BlockInserted(start_block);
98 : : }
99 : :
100 : 5826 : int Reassembler::TrimToSeq(int seq)
101 : : {
102 : 5826 : int num_missing = 0;
103 : :
104 : : // Do this accounting before looking for Undelivered data,
105 : : // since that will alter last_reassem_seq.
106 : :
107 [ + + ]: 5826 : if ( blocks )
108 : : {
109 [ + + ]: 5156 : if ( seq_delta(blocks->seq, last_reassem_seq) > 0 )
110 : : // An initial hole.
111 : 5156 : num_missing += seq_delta(blocks->seq, last_reassem_seq);
112 : : }
113 : :
114 [ + - ]: 670 : else if ( seq_delta(seq, last_reassem_seq) > 0 )
115 : : { // Trimming data we never delivered.
116 [ + - ]: 670 : if ( ! blocks )
117 : : // We won't have any accounting based on blocks
118 : : // for this hole.
119 : 670 : num_missing += seq_delta(seq, last_reassem_seq);
120 : : }
121 : :
122 [ + + ]: 5826 : if ( seq_delta(seq, last_reassem_seq) > 0 )
123 : : {
124 : : // We're trimming data we never delivered.
125 : 867 : Undelivered(seq);
126 : : }
127 : :
128 [ + + ][ + + ]: 13568 : while ( blocks && seq_delta(blocks->upper, seq) <= 0 )
[ + + ]
129 : : {
130 : 7742 : DataBlock* b = blocks->next;
131 : :
132 [ + + ][ + + ]: 7742 : if ( b && seq_delta(b->seq, seq) <= 0 )
[ + + ]
133 : : {
134 [ + + ]: 3269 : if ( blocks->upper != b->seq )
135 : 3269 : num_missing += seq_delta(b->seq, blocks->upper);
136 : : }
137 : : else
138 : : {
139 : : // No more blocks - did this one make it to seq?
140 : : // Second half of test is for acks of FINs, which
141 : : // don't get entered into the sequence space.
142 [ + + ][ + + ]: 4473 : if ( blocks->upper != seq && blocks->upper != seq - 1 )
143 : 66 : num_missing += seq_delta(seq, blocks->upper);
144 : : }
145 : :
146 [ + - ]: 7742 : delete blocks;
147 : :
148 : 7742 : blocks = b;
149 : : }
150 : :
151 [ + + ]: 5826 : if ( blocks )
152 : : {
153 : 798 : blocks->prev = 0;
154 : :
155 : : // If we skipped over some undeliverable data, then
156 : : // it's possible that this block is now deliverable.
157 : : // Give it a try.
158 [ + + ]: 798 : if ( blocks->seq == last_reassem_seq )
159 : 798 : BlockInserted(blocks);
160 : : }
161 : : else
162 : 5028 : last_block = 0;
163 : :
164 [ + - ]: 5826 : if ( seq_delta(seq, trim_seq) > 0 )
165 : : // seq is further ahead in the sequence space.
166 : 5826 : trim_seq = seq;
167 : :
168 : 5826 : return num_missing;
169 : : }
170 : :
171 : 1888 : void Reassembler::ClearBlocks()
172 : : {
173 [ + + ]: 2314 : while ( blocks )
174 : : {
175 : 426 : DataBlock* b = blocks->next;
176 [ + - ]: 426 : delete blocks;
177 : 426 : blocks = b;
178 : : }
179 : :
180 : 1888 : last_block = 0;
181 : 1888 : }
182 : :
183 : 0 : int Reassembler::TotalSize() const
184 : : {
185 : 0 : int size = 0;
186 : :
187 [ # # ]: 0 : for ( DataBlock* b = blocks; b; b = b->next )
188 : 0 : size += b->Size();
189 : :
190 : 0 : return size;
191 : : }
192 : :
193 : 0 : void Reassembler::Describe(ODesc* d) const
194 : : {
195 : 0 : d->Add("reassembler");
196 : 0 : }
197 : :
198 : 0 : void Reassembler::Undelivered(int /* up_to_seq */)
199 : : {
200 : 0 : }
201 : :
202 : : DataBlock* Reassembler::AddAndCheck(DataBlock* b, int seq, int upper,
203 : 3865 : const u_char* data)
204 : : {
205 : : if ( DEBUG_reassem )
206 : : {
207 : : DEBUG_MSG("%.6f Reassembler::AddAndCheck seq=%d, upper=%d\n",
208 : : network_time, seq, upper);
209 : : }
210 : :
211 : : // Special check for the common case of appending to the end.
212 [ + - ][ + + ]: 3865 : if ( last_block && seq == last_block->upper )
213 : : {
214 : : last_block = new DataBlock(data, upper - seq, seq,
215 : 3347 : last_block, 0);
216 : 3347 : return last_block;
217 : : }
218 : :
219 : : // Find the first block that doesn't come completely before the
220 : : // new data.
221 [ + + ][ + + ]: 1266 : while ( b->next && seq_delta(b->upper, seq) <= 0 )
[ + + ]
222 : 748 : b = b->next;
223 : :
224 [ + + ]: 518 : if ( seq_delta(b->upper, seq) <= 0 )
225 : : {
226 : : // b is the last block, and it comes completely before
227 : : // the new block.
228 : 79 : last_block = new DataBlock(data, upper - seq, seq, b, 0);
229 : 79 : return last_block;
230 : : }
231 : :
232 : 439 : DataBlock* new_b = 0;
233 : :
234 [ + + ]: 439 : if ( seq_delta(upper, b->seq) <= 0 )
235 : : {
236 : : // The new block comes completely before b.
237 : : new_b = new DataBlock(data, seq_delta(upper, seq), seq,
238 : 204 : b->prev, b);
239 [ + + ]: 204 : if ( b == blocks )
240 : 146 : blocks = new_b;
241 : 204 : return new_b;
242 : : }
243 : :
244 : : // The blocks overlap.
245 : :
246 : : #ifdef ACTIVE_MAPPING
247 : : if ( policy != RP_UNKNOWN )
248 : : {
249 : : if ( seq_delta(seq, b->seq) < 0 )
250 : : { // The new block has a prefix that comes before b.
251 : : int prefix_len = seq_delta(b->seq, seq);
252 : : new_b = new DataBlock(data, prefix_len, seq, b->prev, b);
253 : : if ( b == blocks )
254 : : blocks = new_b;
255 : :
256 : : data += prefix_len;
257 : : seq += prefix_len;
258 : : }
259 : :
260 : : if ( policy == RP_LAST ||
261 : : // After handling the prefix block, BSD takes the rest
262 : : (policy == RP_BSD && new_b) ||
263 : : // Similar, but overwrite for same seq number
264 : : (policy == RP_LINUX && (new_b || seq == b->seq)) )
265 : : {
266 : : DataBlock* bprev = b->prev;
267 : : bool b_was_first = b == blocks;
268 : : while ( b && b->upper <= upper )
269 : : {
270 : : DataBlock* next = b->next;
271 : : delete b;
272 : : b = next;
273 : : }
274 : :
275 : : new_b = new DataBlock(data, upper - seq, seq, bprev, b);
276 : : if ( b_was_first )
277 : : blocks = new_b;
278 : :
279 : : // Trim the next block as needed.
280 : : if ( b && seq_delta(new_b->upper, b->seq) > 0 )
281 : : {
282 : : DataBlock* next_b =
283 : : new DataBlock(&b->block[upper - b->seq],
284 : : b->upper - upper, upper,
285 : : new_b, b->next);
286 : : if ( b == last_block )
287 : : last_block = next_b;
288 : :
289 : : delete b;
290 : : }
291 : : }
292 : :
293 : : else
294 : : { // handle the piece that sticks out past b
295 : : new_b = b;
296 : : int len = upper - b->upper;
297 : : if ( len > 0 )
298 : : new_b = AddAndCheck(b, b->upper, upper, &data[b->upper - seq]);
299 : : }
300 : : }
301 : : else
302 : : {
303 : : #endif
304 : : // Default behavior - complain about overlaps.
305 [ + + ]: 235 : if ( seq_delta(seq, b->seq) < 0 )
306 : : {
307 : : // The new block has a prefix that comes before b.
308 : 3 : int prefix_len = seq_delta(b->seq, seq);
309 : 3 : new_b = new DataBlock(data, prefix_len, seq, b->prev, b);
310 [ + - ]: 3 : if ( b == blocks )
311 : 3 : blocks = new_b;
312 : :
313 : 3 : data += prefix_len;
314 : 3 : seq += prefix_len;
315 : : }
316 : : else
317 : 232 : new_b = b;
318 : :
319 : 235 : int overlap_start = seq;
320 : 235 : int overlap_offset = seq_delta(overlap_start, b->seq);
321 : 235 : int new_b_len = seq_delta(upper, seq);
322 : 235 : int b_len = seq_delta(b->upper, overlap_start);
323 : 235 : int overlap_len = min(new_b_len, b_len);
324 : :
325 : 235 : Overlap(&b->block[overlap_offset], data, overlap_len);
326 : :
327 [ + + ]: 235 : if ( overlap_len < new_b_len )
328 : : {
329 : : // Recurse to resolve remainder of the new data.
330 : 5 : data += overlap_len;
331 : 5 : seq += overlap_len;
332 : :
333 [ + - ]: 5 : if ( new_b == b )
334 : 5 : new_b = AddAndCheck(b, seq, upper, data);
335 : : else
336 : 0 : (void) AddAndCheck(b, seq, upper, data);
337 : : }
338 : :
339 : : #ifdef ACTIVE_MAPPING
340 : : } // else branch, for RP_UNKNOWN behavior
341 : : #endif
342 : :
343 [ - + ]: 235 : if ( new_b->prev == last_block )
344 : 0 : last_block = new_b;
345 : :
346 : 3865 : return new_b;
347 : : }
348 : :
349 : 0 : bool Reassembler::Serialize(SerialInfo* info) const
350 : : {
351 : 0 : return SerialObj::Serialize(info);
352 : : }
353 : :
354 : 0 : Reassembler* Reassembler::Unserialize(UnserialInfo* info)
355 : : {
356 : 0 : return (Reassembler*) SerialObj::Unserialize(info, SER_REASSEMBLER);
357 : : }
358 : :
359 : 0 : bool Reassembler::DoSerialize(SerialInfo* info) const
360 : : {
361 [ # # ][ # # ]: 0 : DO_SERIALIZE(SER_REASSEMBLER, BroObj);
362 : :
363 : : // I'm not sure if it makes sense to actually save the buffered data.
364 : : // For now, we just remember the seq numbers so that we don't get
365 : : // complaints about missing content.
366 [ # # ][ # # ]: 0 : return SERIALIZE(trim_seq) && SERIALIZE(int(policy));
367 : : }
368 : :
369 : 0 : bool Reassembler::DoUnserialize(UnserialInfo* info)
370 : : {
371 [ # # ]: 0 : DO_UNSERIALIZE(BroObj);
372 : :
373 : 0 : blocks = last_block = 0;
374 : :
375 : : int p;
376 [ # # ][ # # ]: 0 : if ( ! UNSERIALIZE(&trim_seq) || ! UNSERIALIZE(&p) )
[ # # ]
377 : 0 : return false;
378 : :
379 : 0 : policy = ReassemblyPolicy(p);
380 : 0 : last_reassem_seq = trim_seq;
381 : :
382 : 0 : return true;
383 [ + - ][ + - ]: 6 : }
|