1 /* 2 * Copyright 2006-2007, Haiku, Inc. All Rights Reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Axel Dörfler, axeld@pinc-software.de 7 */ 8 9 10 #include "BufferQueue.h" 11 12 #include <KernelExport.h> 13 14 15 //#define TRACE_BUFFER_QUEUE 16 #ifdef TRACE_BUFFER_QUEUE 17 # define TRACE(x) dprintf x 18 #else 19 # define TRACE(x) 20 #endif 21 22 23 BufferQueue::BufferQueue(size_t maxBytes) 24 : 25 fMaxBytes(maxBytes), 26 fNumBytes(0), 27 fContiguousBytes(0), 28 fFirstSequence(0), 29 fLastSequence(0), 30 fPushPointer(0) 31 { 32 } 33 34 35 BufferQueue::~BufferQueue() 36 { 37 // free up any buffers left in the queue 38 39 net_buffer *buffer; 40 while ((buffer = fList.RemoveHead()) != NULL) { 41 gBufferModule->free(buffer); 42 } 43 } 44 45 46 void 47 BufferQueue::SetMaxBytes(size_t maxBytes) 48 { 49 fMaxBytes = maxBytes; 50 } 51 52 53 void 54 BufferQueue::SetInitialSequence(tcp_sequence sequence) 55 { 56 TRACE(("BufferQueue@%p::SetInitialSequence(%lu)\n", this, (uint32)sequence)); 57 58 fFirstSequence = fLastSequence = sequence; 59 } 60 61 62 63 void 64 BufferQueue::Add(net_buffer *buffer) 65 { 66 Add(buffer, fLastSequence); 67 } 68 69 70 void 71 BufferQueue::Add(net_buffer *buffer, tcp_sequence sequence) 72 { 73 TRACE(("BufferQueue@%p::Add(buffer %p, size %lu, sequence %lu)\n", 74 this, buffer, buffer->size, (uint32)sequence)); 75 TRACE((" in: first: %lu, last: %lu, num: %lu, cont: %lu\n", 76 (uint32)fFirstSequence, (uint32)fLastSequence, fNumBytes, fContiguousBytes)); 77 78 buffer->sequence = sequence; 79 80 if (fList.IsEmpty() || sequence >= fLastSequence) { 81 // we usually just add the buffer to the end of the queue 82 fList.Add(buffer); 83 84 if (sequence == fLastSequence 85 && fLastSequence - fFirstSequence == fNumBytes) { 86 // there is no hole in the buffer, we can make the whole buffer 87 // available 88 fContiguousBytes += buffer->size; 89 } 90 91 fLastSequence = sequence + buffer->size; 92 fNumBytes += buffer->size; 93 94 TRACE((" out0: first: %lu, last: %lu, num: %lu, cont: %lu\n", 95 (uint32)fFirstSequence, (uint32)fLastSequence, fNumBytes, fContiguousBytes)); 96 return; 97 } 98 99 if (fLastSequence < sequence + buffer->size) 100 fLastSequence = sequence + buffer->size; 101 102 if (fFirstSequence > sequence) { 103 // this buffer contains data that is already long gone - trim it 104 gBufferModule->remove_header(buffer, fFirstSequence - sequence); 105 sequence = fFirstSequence; 106 } 107 108 // find the place where to insert the buffer into the queue 109 110 SegmentList::ReverseIterator iterator = fList.GetReverseIterator(); 111 net_buffer *previous = NULL; 112 net_buffer *next = NULL; 113 while ((previous = iterator.Next()) != NULL) { 114 if (sequence >= previous->sequence) { 115 // The new fragment can be inserted after this one 116 break; 117 } 118 119 next = previous; 120 } 121 122 // check if we have duplicate data, and remove it if that is the case 123 if (previous != NULL) { 124 if (sequence == previous->sequence) { 125 // we already have at least part of this data - ignore new data 126 // whenever it makes sense (because some TCP implementations send 127 // bogus data when probing the window) 128 if (previous->size >= buffer->size) { 129 gBufferModule->free(buffer); 130 buffer = NULL; 131 } else { 132 fList.Remove(previous); 133 gBufferModule->free(previous); 134 } 135 } else if (tcp_sequence(previous->sequence + previous->size) > sequence) { 136 gBufferModule->remove_header(buffer, 137 previous->sequence + previous->size - sequence); 138 } 139 } 140 141 if (buffer != NULL && next != NULL 142 && tcp_sequence(sequence + buffer->size) > next->sequence) { 143 // we already have at least part of this data 144 if (tcp_sequence(next->sequence + next->size) < sequence + buffer->size) { 145 net_buffer *remove = next; 146 next = (net_buffer *)next->link.next; 147 148 fList.Remove(remove); 149 gBufferModule->free(remove); 150 } else { 151 gBufferModule->remove_trailer(buffer, 152 sequence + buffer->size - next->sequence); 153 } 154 } 155 156 if (buffer == NULL) { 157 TRACE((" out1: first: %lu, last: %lu, num: %lu, cont: %lu\n", 158 (uint32)fFirstSequence, (uint32)fLastSequence, fNumBytes, fContiguousBytes)); 159 return; 160 } 161 162 fList.Insert(next, buffer); 163 fNumBytes += buffer->size; 164 165 // we might need to update the number of bytes available 166 167 if (fLastSequence - fFirstSequence == fNumBytes) 168 fContiguousBytes = fNumBytes; 169 else if (fFirstSequence + fContiguousBytes == sequence) { 170 // the complicated case: the new segment may have connected almost all 171 // buffers in the queue (but not all, or the above would be true) 172 173 do { 174 fContiguousBytes += buffer->size; 175 176 buffer = (struct net_buffer *)buffer->link.next; 177 } while (buffer != NULL 178 && fFirstSequence + fContiguousBytes == buffer->sequence); 179 } 180 181 TRACE((" out2: first: %lu, last: %lu, num: %lu, cont: %lu\n", 182 (uint32)fFirstSequence, (uint32)fLastSequence, fNumBytes, fContiguousBytes)); 183 } 184 185 186 /*! 187 Removes all data in the queue up to the \a sequence number as specified. 188 189 NOTE: 190 If there are missing segments in the buffers to be removed, 191 fContiguousBytes is not maintained correctly! 192 */ 193 status_t 194 BufferQueue::RemoveUntil(tcp_sequence sequence) 195 { 196 TRACE(("BufferQueue@%p::RemoveUntil(sequence %lu)\n", this, (uint32)sequence)); 197 198 if (sequence < fFirstSequence) 199 return B_OK; 200 201 SegmentList::Iterator iterator = fList.GetIterator(); 202 net_buffer *buffer = NULL; 203 while ((buffer = iterator.Next()) != NULL && buffer->sequence < sequence) { 204 if (sequence >= buffer->sequence + buffer->size) { 205 // remove this buffer completely 206 iterator.Remove(); 207 fNumBytes -= buffer->size; 208 209 fContiguousBytes -= buffer->size; 210 gBufferModule->free(buffer); 211 } else { 212 // remove the header as far as needed 213 size_t size = sequence - buffer->sequence; 214 gBufferModule->remove_header(buffer, size); 215 216 buffer->sequence += size; 217 fNumBytes -= size; 218 fContiguousBytes -= size; 219 break; 220 } 221 } 222 223 if (fList.IsEmpty()) 224 fFirstSequence = fLastSequence; 225 else 226 fFirstSequence = fList.Head()->sequence; 227 228 return B_OK; 229 } 230 231 232 /*! 233 Clones the requested data in the buffer queue into the provided \a buffer. 234 */ 235 status_t 236 BufferQueue::Get(net_buffer *buffer, tcp_sequence sequence, size_t bytes) 237 { 238 TRACE(("BufferQueue@%p::Get(sequence %lu, bytes %lu)\n", this, (uint32)sequence, bytes)); 239 240 if (bytes == 0) 241 return B_OK; 242 243 if (sequence >= fLastSequence || sequence < fFirstSequence) { 244 // we don't have the requested data 245 return B_BAD_VALUE; 246 } 247 if (tcp_sequence(sequence + bytes) > fLastSequence) 248 bytes = fLastSequence - sequence; 249 250 size_t bytesLeft = bytes; 251 252 // find first buffer matching the sequence 253 254 SegmentList::Iterator iterator = fList.GetIterator(); 255 net_buffer *source = NULL; 256 while ((source = iterator.Next()) != NULL) { 257 if (sequence < source->sequence + source->size) 258 break; 259 } 260 261 if (source == NULL) 262 panic("we should have had that data..."); 263 if (source->sequence > sequence) 264 panic("source %p, sequence = %lu (%lu)\n", source, source->sequence, (uint32)sequence); 265 266 // clone the data 267 268 uint32 offset = sequence - source->sequence; 269 270 while (source != NULL && bytesLeft > 0) { 271 size_t size = min_c(source->size - offset, bytesLeft); 272 status_t status = gBufferModule->append_cloned(buffer, source, offset, size); 273 if (status < B_OK) 274 return status; 275 276 bytesLeft -= size; 277 offset = 0; 278 source = iterator.Next(); 279 } 280 281 return B_OK; 282 } 283 284 285 /*! 286 Creates a new buffer containing \a bytes bytes from the start of the 287 buffer queue. If \a remove is \c true, the data is removed from the 288 queue, if not, the data is cloned from the queue. 289 */ 290 status_t 291 BufferQueue::Get(size_t bytes, bool remove, net_buffer **_buffer) 292 { 293 if (bytes > Available()) 294 bytes = Available(); 295 296 if (bytes == 0) { 297 // we don't need to create a buffer when there is no data 298 *_buffer = NULL; 299 return B_OK; 300 } 301 302 net_buffer *buffer = fList.First(); 303 size_t bytesLeft = bytes; 304 ASSERT(buffer != NULL); 305 306 if (!remove || buffer->size > bytes) { 307 // we need a new buffer 308 buffer = gBufferModule->create(256); 309 if (buffer == NULL) 310 return B_NO_MEMORY; 311 } else { 312 // we can reuse this buffer 313 bytesLeft -= buffer->size; 314 fFirstSequence += buffer->size; 315 316 fList.Remove(buffer); 317 } 318 319 // clone/copy the remaining data 320 321 SegmentList::Iterator iterator = fList.GetIterator(); 322 net_buffer *source = NULL; 323 status_t status = B_OK; 324 while (bytesLeft > 0 && (source = iterator.Next()) != NULL) { 325 size_t size = min_c(source->size, bytesLeft); 326 status_t status = gBufferModule->append_cloned(buffer, source, 0, size); 327 if (status < B_OK) 328 break; 329 330 bytesLeft -= size; 331 332 if (!remove) 333 continue; 334 335 // remove either the whole buffer or only the part we cloned 336 337 fFirstSequence += size; 338 339 if (size == source->size) { 340 iterator.Remove(); 341 gBufferModule->free(source); 342 } else { 343 gBufferModule->remove_header(source, size); 344 source->sequence += size; 345 } 346 } 347 348 if (status == B_OK) { 349 *_buffer = buffer; 350 if (remove) { 351 fNumBytes -= bytes; 352 fContiguousBytes -= bytes; 353 } 354 } else 355 gBufferModule->free(buffer); 356 357 return status; 358 } 359 360 361 size_t 362 BufferQueue::Available(tcp_sequence sequence) const 363 { 364 if (sequence > (uint32)fFirstSequence + fContiguousBytes) 365 return 0; 366 367 return fContiguousBytes + fFirstSequence - sequence; 368 } 369 370 void 371 BufferQueue::SetPushPointer() 372 { 373 if (fList.IsEmpty()) 374 fPushPointer = 0; 375 else 376 fPushPointer = fList.Tail()->sequence + fList.Tail()->size; 377 } 378