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