kernel/cbuf.c

   1 #include <kernel/kernel.h>
   2 #include <kernel/heap.h>
   3 #include <kernel/sem.h>
   4 #include <kernel/lock.h>
   5 #include <kernel/smp.h>
   6 #include <kernel/int.h>
   7 #include <kernel/debug.h>
   8 #include <kernel/cbuf.h>
   9 #include <kernel/vm.h>
  10 #include <kernel/net/misc.h> // for cksum16
  11 #include <kernel/arch/cpu.h>
  12 #include <newos/errors.h>
  13
  14 #include <string.h>
  15
  16 #if DEBUG > 1
  17 #define VALIDATE_CBUFS 1
  18 #else
  19 #define VALIDATE_CBUFS 0
  20 #endif
  21
  22 #define ALLOCATE_CHUNK (PAGE_SIZE * 16)
  23 #define CBUF_REGION_SIZE (1*1024*1024)
  24 #define CBUF_BITMAP_SIZE (CBUF_REGION_SIZE / CBUF_LEN)
  25
  26 static cbuf *cbuf_free_list;
  27 static mutex cbuf_free_list_lock;
  28 static cbuf *cbuf_free_noblock_list;
  29 static spinlock_t noblock_spin;
  30
  31 static spinlock_t cbuf_lowlevel_spinlock;
  32 static region_id cbuf_region_id;
  33 static cbuf *cbuf_region;
  34 static region_id cbuf_bitmap_region_id;
  35 static uint8 *cbuf_bitmap;
  36
  37 /* initialize most of the cbuf structure */
  38 /* does not initialize the next pointer, because it may already be in a chain */
  39 static void initialize_cbuf(cbuf *buf)
  40 {
  41         buf->len = sizeof(buf->dat);
  42         buf->total_len = 0;
  43         buf->data = buf->dat;
  44         buf->flags = 0;
  45         buf->packet_next = 0;
  46 }
  47
  48 static int validate_cbuf(cbuf *head)
  49 {
  50 #if VALIDATE_CBUFS
  51         size_t counted_size;
  52         cbuf *tail;
  53         cbuf *buf;
  54
  55         if(head == NULL)
  56                 return ERR_GENERAL;
  57
  58         /* make sure the first cbuf is the head */
  59         if((head->flags & CBUF_FLAG_CHAIN_HEAD) == 0)
  60                 panic("validate_cbuf: cbuf %p is not head\n", head);
  61
  62         /* walk through the chain and verify a few things */
  63         buf = head;
  64         counted_size = 0;
  65         while(buf) {
  66                 if(buf != head && (buf->flags & CBUF_FLAG_CHAIN_HEAD))
  67                         panic("validate_cbuf: cbuf %p has buffer %p with HEAD flag set\n", head, buf);
  68
  69                 if(buf->next != NULL && (buf->flags & CBUF_FLAG_CHAIN_TAIL))
  70                         panic("validate_cbuf: cbuf %p has buffer %p with TAIL flag set\n", head, buf);
  71
  72                 /* make sure len makes sense */
  73                 if(buf->len > sizeof(buf->dat))
  74                         panic("validate_cbuf: cbuf %p has buffer %p with bad length\n", head, buf);
  75
  76                 /* add up the size of this part of the chain */
  77                 counted_size += buf->len;
  78
  79                 /* make sure the data pointer is inside the buffer */
  80                 if(((addr_t)buf->data < (addr_t)buf->dat)
  81                   || ((addr_t)buf->data - (addr_t)buf->dat > sizeof(buf->dat))
  82                   || ((addr_t)buf->data + buf->len > (addr_t)buf->data + sizeof(buf->dat)))
  83                         panic("validate_cbuf: cbuf %p has buffer %p with bad pointer\n", head, buf);
  84
  85                 tail = buf;
  86                 buf = buf->next;
  87         }
  88
  89         /* look at the tail */
  90         if((tail->flags & CBUF_FLAG_CHAIN_TAIL) == 0)
  91                 panic("validate_cbuf: cbuf %p 's tail at %p does not have TAIL flag set\n", head, tail);
  92
  93         /* make sure the added up size == the total size */
  94         if(counted_size != head->total_len)
  95                 panic("validate_cbuf: cbuf %p has bad total_len %ld, counted %ld\n", head, head->total_len, counted_size);
  96 #endif
  97         return 0;
  98 }
  99
 100 static void *_cbuf_alloc(size_t *size)
 101 {
 102         void *buf;
 103         int i;
 104         int start;
 105         size_t len_found = 0;
 106
 107 //      dprintf("cbuf_alloc: asked to allocate size %d\n", *size);
 108
 109         int_disable_interrupts();
 110         acquire_spinlock(&cbuf_lowlevel_spinlock);
 111
 112         // scan through the allocation bitmap, looking for the first free block
 113         // XXX not optimal
 114         start = -1;
 115         for(i = 0; i < CBUF_BITMAP_SIZE; i++) {
 116                 // skip bytes of the bitmap at a time
 117                 if((i % 8) == 0 && cbuf_bitmap[i/8] == 0xff) {
 118                         i += 8;
 119                         continue;
 120                 }
 121
 122                 if(!CHECK_BIT(cbuf_bitmap[i/8], i%8)) {
 123                         cbuf_bitmap[i/8] = SET_BIT(cbuf_bitmap[i/8], i%8);
 124                         if(start < 0)
 125                                 start = i;
 126                         len_found += CBUF_LEN;
 127                         if(len_found >= *size) {
 128                                 // we're done
 129                                 break;
 130                         }
 131                 } else if(start >= 0) {
 132                         // we've found a start of a run before, so we're done now
 133                         break;
 134                 }
 135         }
 136
 137         if(start < 0) {
 138                 // couldn't find any memory
 139                 buf = NULL;
 140                 *size = 0;
 141         } else {
 142                 buf = &cbuf_region[start];
 143                 *size = len_found;
 144         }
 145
 146         release_spinlock(&cbuf_lowlevel_spinlock);
 147         int_restore_interrupts();
 148
 149         return buf;
 150 }
 151
 152 static cbuf *allocate_cbuf_mem(size_t size)
 153 {
 154         void *_buf;
 155         cbuf *buf = NULL;
 156         cbuf *last_buf = NULL;
 157         cbuf *head_buf = NULL;
 158         int i;
 159         int count;
 160         size_t found_size;
 161
 162         size = PAGE_ALIGN(size);
 163
 164         while(size > 0) {
 165                 found_size = size;
 166                 _buf = _cbuf_alloc(&found_size);
 167                 if(!_buf) {
 168                         // couldn't allocate, lets bail with what we have
 169                         break;
 170                 }
 171                 size -= found_size;
 172                 count = found_size / CBUF_LEN;
 173 //              dprintf("allocate_cbuf_mem: returned %d of memory, %d left\n", found_size, size);
 174
 175                 buf = (cbuf *)_buf;
 176                 if(!head_buf)
 177                         head_buf = buf;
 178                 for(i=0; i<count; i++) {
 179                         initialize_cbuf(buf);
 180                         if(last_buf)
 181                                 last_buf->next = buf;
 182                         if(buf == head_buf) {
 183                                 buf->flags |= CBUF_FLAG_CHAIN_HEAD;
 184                                 buf->total_len = (size / CBUF_LEN) * sizeof(buf->dat);
 185                         }
 186                         last_buf = buf;
 187                         buf++;
 188                 }
 189         }
 190         if(last_buf) {
 191                 last_buf->next = NULL;
 192                 last_buf->flags |= CBUF_FLAG_CHAIN_TAIL;
 193         }
 194
 195         return head_buf;
 196 }
 197
 198 static void _clear_chain(cbuf *head, cbuf **tail)
 199 {
 200         cbuf *buf;
 201
 202         buf = head;
 203         *tail = NULL;
 204         while(buf) {
 205                 initialize_cbuf(buf); // doesn't touch the next ptr
 206                 *tail = buf;
 207                 buf = buf->next;
 208         }
 209
 210         return;
 211 }
 212
 213 void cbuf_free_chain_noblock(cbuf *buf)
 214 {
 215         cbuf *head, *last;
 216
 217         if(buf == NULL)
 218                 return;
 219
 220         head = buf;
 221         _clear_chain(head, &last);
 222
 223         int_disable_interrupts();
 224         acquire_spinlock(&noblock_spin);
 225
 226         last->next = cbuf_free_noblock_list;
 227         cbuf_free_noblock_list = head;
 228
 229         release_spinlock(&noblock_spin);
 230         int_restore_interrupts();
 231 }
 232
 233 void cbuf_free_chain(cbuf *buf)
 234 {
 235         cbuf *head, *last;
 236
 237         if(buf == NULL)
 238                 return;
 239
 240         head = buf;
 241         _clear_chain(head, &last);
 242
 243         mutex_lock(&cbuf_free_list_lock);
 244
 245         last->next = cbuf_free_list;
 246         cbuf_free_list = head;
 247
 248         mutex_unlock(&cbuf_free_list_lock);
 249 }
 250
 251 cbuf *cbuf_get_chain(size_t len)
 252 {
 253         cbuf *chain = NULL;
 254         cbuf *tail = NULL;
 255         cbuf *temp;
 256         size_t chain_len = 0;
 257
 258         if(len == 0)
 259                 panic("cbuf_get_chain: passed size 0\n");
 260
 261         mutex_lock(&cbuf_free_list_lock);
 262
 263         while(chain_len < len) {
 264                 if(cbuf_free_list == NULL) {
 265                         // we need to allocate some more cbufs
 266                         mutex_unlock(&cbuf_free_list_lock);
 267                         temp = allocate_cbuf_mem(ALLOCATE_CHUNK);
 268                         if(!temp) {
 269                                 // no more ram
 270                                 if(chain)
 271                                         cbuf_free_chain(chain);
 272                                 dprintf("cbuf_get_chain: asked to allocate %ld bytes but out of memory\n", len);
 273                                 return NULL;
 274                         }
 275                         cbuf_free_chain(temp);
 276                         mutex_lock(&cbuf_free_list_lock);
 277                         continue;
 278                 }
 279
 280                 temp = cbuf_free_list;
 281                 cbuf_free_list = cbuf_free_list->next;
 282                 temp->flags = 0;
 283                 temp->next = chain;
 284                 if(chain == NULL)
 285                         tail = temp;
 286                 chain = temp;
 287
 288                 chain_len += chain->len;
 289         }
 290         mutex_unlock(&cbuf_free_list_lock);
 291
 292         // now we have a chain, fixup the first and last entry
 293         chain->total_len = len;
 294         chain->flags |= CBUF_FLAG_CHAIN_HEAD;
 295         tail->len -= chain_len - len;
 296         tail->flags |= CBUF_FLAG_CHAIN_TAIL;
 297
 298         validate_cbuf(chain);
 299
 300         return chain;
 301 }
 302
 303 cbuf *cbuf_get_chain_noblock(size_t len)
 304 {
 305         cbuf *chain = NULL;
 306         cbuf *tail = NULL;
 307         cbuf *temp;
 308         size_t chain_len = 0;
 309
 310         int_disable_interrupts();
 311         acquire_spinlock(&noblock_spin);
 312
 313         while(chain_len < len) {
 314                 if(cbuf_free_noblock_list == NULL) {
 315                         dprintf("cbuf_get_chain_noblock: not enough cbufs\n");
 316                         release_spinlock(&noblock_spin);
 317                         int_restore_interrupts();
 318
 319                         if(chain != NULL)
 320                                 cbuf_free_chain_noblock(chain);
 321
 322                         return NULL;
 323                 }
 324
 325                 temp = cbuf_free_noblock_list;
 326                 cbuf_free_noblock_list = cbuf_free_noblock_list->next;
 327                 temp->next = chain;
 328                 if(chain == NULL)
 329                         tail = temp;
 330                 chain = temp;
 331
 332                 chain_len += chain->len;
 333         }
 334         release_spinlock(&noblock_spin);
 335         int_restore_interrupts();
 336
 337         // now we have a chain, fixup the first and last entry
 338         chain->total_len = len;
 339         chain->flags |= CBUF_FLAG_CHAIN_HEAD;
 340         tail->len -= chain_len - len;
 341         tail->flags |= CBUF_FLAG_CHAIN_TAIL;
 342
 343         return chain;
 344 }
 345
 346 int cbuf_memcpy_to_chain(cbuf *chain, size_t offset, const void *_src, size_t len)
 347 {
 348         cbuf *buf;
 349         char *src = (char *)_src;
 350         int buf_offset;
 351
 352         validate_cbuf(chain);
 353
 354         if(offset + len > chain->total_len) {
 355                 panic("cbuf_memcpy_to_chain: offset + len > size of cbuf chain\n");
 356                 return ERR_INVALID_ARGS;
 357         }
 358
 359         // find the starting cbuf in the chain to copy to
 360         buf = chain;
 361         buf_offset = 0;
 362         while(offset > 0) {
 363                 if(buf == NULL) {
 364                         panic("cbuf_memcpy_to_chain: end of chain reached too early!\n");
 365                         return ERR_GENERAL;
 366                 }
 367                 if(offset < buf->len) {
 368                         // this is the one
 369                         buf_offset = offset;
 370                         break;
 371                 }
 372                 offset -= buf->len;
 373                 buf = buf->next;
 374         }
 375
 376         while(len > 0) {
 377                 int to_copy;
 378
 379                 if(buf == NULL) {
 380                         panic("cbuf_memcpy_to_chain: end of chain reached too early!\n");
 381                         return ERR_GENERAL;
 382                 }
 383                 to_copy = min(len, buf->len - buf_offset);
 384                 memcpy((char *)buf->data + buf_offset, src, to_copy);
 385
 386                 buf_offset = 0;
 387                 len -= to_copy;
 388                 src += to_copy;
 389                 buf = buf->next;
 390         }
 391
 392         return NO_ERROR;
 393 }
 394
 395 int cbuf_user_memcpy_to_chain(cbuf *chain, size_t offset, const void *_src, size_t len)
 396 {
 397         cbuf *buf;
 398         char *src = (char *)_src;
 399         int buf_offset;
 400         int err;
 401
 402         validate_cbuf(chain);
 403
 404         if(len + offset > chain->total_len) {
 405                 dprintf("cbuf_memcpy_to_chain: len + offset > size of cbuf chain\n");
 406                 return ERR_INVALID_ARGS;
 407         }
 408
 409         // find the starting cbuf in the chain to copy to
 410         buf = chain;
 411         buf_offset = 0;
 412         while(offset > 0) {
 413                 if(buf == NULL) {
 414                         dprintf("cbuf_memcpy_to_chain: end of chain reached too early!\n");
 415                         return ERR_GENERAL;
 416                 }
 417                 if(offset < buf->len) {
 418                         // this is the one
 419                         buf_offset = offset;
 420                         break;
 421                 }
 422                 offset -= buf->len;
 423                 buf = buf->next;
 424         }
 425
 426         err = NO_ERROR;
 427         while(len > 0) {
 428                 int to_copy;
 429
 430                 if(buf == NULL) {
 431                         dprintf("cbuf_memcpy_to_chain: end of chain reached too early!\n");
 432                         return ERR_GENERAL;
 433                 }
 434                 to_copy = min(len, buf->len - buf_offset);
 435                 if ((err = user_memcpy((char *)buf->data + buf_offset, src, to_copy) < 0))
 436                         break; // memory exception
 437
 438                 buf_offset = 0;
 439                 len -= to_copy;
 440                 src += to_copy;
 441                 buf = buf->next;
 442         }
 443
 444         return err;
 445 }
 446
 447
 448 int cbuf_memcpy_from_chain(void *_dest, cbuf *chain, size_t offset, size_t len)
 449 {
 450         cbuf *buf;
 451         char *dest = (char *)_dest;
 452         int buf_offset;
 453
 454         validate_cbuf(chain);
 455
 456         if(len + offset > chain->total_len) {
 457                 dprintf("cbuf_memcpy_from_chain: len + offset > size of cbuf chain\n");
 458                 return ERR_INVALID_ARGS;
 459         }
 460
 461         // find the starting cbuf in the chain to copy from
 462         buf = chain;
 463         buf_offset = 0;
 464         while(offset > 0) {
 465                 if(buf == NULL) {
 466                         dprintf("cbuf_memcpy_from_chain: end of chain reached too early!\n");
 467                         return ERR_GENERAL;
 468                 }
 469                 if(offset < buf->len) {
 470                         // this is the one
 471                         buf_offset = offset;
 472                         break;
 473                 }
 474                 offset -= buf->len;
 475                 buf = buf->next;
 476         }
 477
 478         while(len > 0) {
 479                 int to_copy;
 480
 481                 if(buf == NULL) {
 482                         dprintf("cbuf_memcpy_from_chain: end of chain reached too early!\n");
 483                         return ERR_GENERAL;
 484                 }
 485
 486                 to_copy = min(len, buf->len - buf_offset);
 487                 memcpy(dest, (char *)buf->data + buf_offset, to_copy);
 488
 489                 buf_offset = 0;
 490                 len -= to_copy;
 491                 dest += to_copy;
 492                 buf = buf->next;
 493         }
 494
 495         return NO_ERROR;
 496 }
 497
 498 int cbuf_user_memcpy_from_chain(void *_dest, cbuf *chain, size_t offset, size_t len)
 499 {
 500         cbuf *buf;
 501         char *dest = (char *)_dest;
 502         int buf_offset;
 503         int err;
 504
 505         validate_cbuf(chain);
 506
 507         if(len + offset > chain->total_len) {
 508                 dprintf("cbuf_memcpy_from_chain: len + offset > size of cbuf chain\n");
 509                 return ERR_INVALID_ARGS;
 510         }
 511
 512         // find the starting cbuf in the chain to copy from
 513         buf = chain;
 514         buf_offset = 0;
 515         while(offset > 0) {
 516                 if(buf == NULL) {
 517                         dprintf("cbuf_memcpy_from_chain: end of chain reached too early!\n");
 518                         return ERR_GENERAL;
 519                 }
 520                 if(offset < buf->len) {
 521                         // this is the one
 522                         buf_offset = offset;
 523                         break;
 524                 }
 525                 offset -= buf->len;
 526                 buf = buf->next;
 527         }
 528
 529         err = NO_ERROR;
 530         while(len > 0) {
 531                 int to_copy;
 532
 533                 if(buf == NULL) {
 534                         dprintf("cbuf_memcpy_from_chain: end of chain reached too early!\n");
 535                         return ERR_GENERAL;
 536                 }
 537
 538                 to_copy = min(len, buf->len - buf_offset);
 539                 if ((err = user_memcpy(dest, (char *)buf->data + buf_offset, to_copy) < 0))
 540                         break;
 541
 542                 buf_offset = 0;
 543                 len -= to_copy;
 544                 dest += to_copy;
 545                 buf = buf->next;
 546         }
 547
 548         return err;
 549 }
 550
 551 cbuf *cbuf_duplicate_chain(cbuf *chain, size_t offset, size_t len, size_t leading_space)
 552 {
 553         cbuf *buf;
 554         cbuf *newbuf;
 555         cbuf *destbuf;
 556         int dest_buf_offset;
 557         int buf_offset;
 558
 559         if(!chain)
 560                 return NULL;
 561
 562         validate_cbuf(chain);
 563
 564         if(offset >= chain->total_len)
 565                 return NULL;
 566         len = min(len, chain->total_len - offset);
 567
 568         newbuf = cbuf_get_chain(len + leading_space);
 569         if(!newbuf)
 570                 return NULL;
 571
 572         if(leading_space > 0) {
 573                 cbuf_truncate_head(newbuf, leading_space, false);
 574         }
 575
 576         // find the starting cbuf in the chain to copy from
 577         buf = chain;
 578         buf_offset = 0;
 579         while(offset > 0) {
 580                 if(buf == NULL) {
 581                         cbuf_free_chain(newbuf);
 582                         dprintf("cbuf_duplicate_chain: end of chain reached too early!\n");
 583                         return NULL;
 584                 }
 585                 if(offset < buf->len) {
 586                         // this is the one
 587                         buf_offset = offset;
 588                         break;
 589                 }
 590                 offset -= buf->len;
 591                 buf = buf->next;
 592         }
 593
 594         destbuf = newbuf;
 595         dest_buf_offset = 0;
 596         while(len > 0) {
 597                 size_t to_copy;
 598
 599                 if(buf == NULL) {
 600                         cbuf_free_chain(newbuf);
 601                         dprintf("cbuf_duplicate_chain: end of source chain reached too early!\n");
 602                         return NULL;
 603                 }
 604                 if(destbuf == NULL) {
 605                         cbuf_free_chain(newbuf);
 606                         dprintf("cbuf_duplicate_chain: end of destination chain reached too early!\n");
 607                         return NULL;
 608                 }
 609
 610                 to_copy = min(destbuf->len - dest_buf_offset, buf->len - buf_offset);
 611                 to_copy = min(to_copy, len);
 612                 memcpy((char *)destbuf->data + dest_buf_offset, (char *)buf->data + buf_offset, to_copy);
 613
 614                 len -= to_copy;
 615                 if(to_copy + buf_offset == buf->len) {
 616                         buf = buf->next;
 617                         buf_offset = 0;
 618                 } else {
 619                         buf_offset += to_copy;
 620                 }
 621                 if(to_copy + dest_buf_offset == destbuf->len) {
 622                         destbuf = destbuf->next;
 623                         dest_buf_offset = 0;
 624                 } else {
 625                         dest_buf_offset += to_copy;
 626                 }
 627         }
 628
 629         validate_cbuf(newbuf);
 630
 631         return newbuf;
 632 }
 633
 634
 635 cbuf *cbuf_merge_chains(cbuf *chain1, cbuf *chain2)
 636 {
 637         cbuf *buf;
 638
 639         if(!chain1 && !chain2)
 640                 return NULL;
 641         if(!chain1)
 642                 return chain2;
 643         if(!chain2)
 644                 return chain1;
 645         if(chain1 == chain2)
 646                 return chain1;
 647
 648         validate_cbuf(chain1);
 649         validate_cbuf(chain2);
 650
 651         // walk to the end of the first chain and tag the second one on
 652         buf = chain1;
 653         while(buf->next)
 654                 buf = buf->next;
 655
 656         buf->next = chain2;
 657
 658         // modify the flags on the chain headers
 659         buf->flags &= ~CBUF_FLAG_CHAIN_TAIL;
 660         chain1->total_len += chain2->total_len;
 661         chain2->flags &= ~CBUF_FLAG_CHAIN_HEAD;
 662
 663         return chain1;
 664 }
 665
 666 size_t cbuf_get_len(cbuf *buf)
 667 {
 668         if(!buf)
 669                 return 0;
 670
 671         validate_cbuf(buf);
 672
 673         if(buf->flags & CBUF_FLAG_CHAIN_HEAD) {
 674                 return buf->total_len;
 675         } else {
 676                 int len = 0;
 677                 while(buf) {
 678                         len += buf->len;
 679                         buf = buf->next;
 680                 }
 681                 return len;
 682         }
 683 }
 684
 685 void *cbuf_get_ptr(cbuf *buf, size_t offset)
 686 {
 687         validate_cbuf(buf);
 688
 689         while(buf) {
 690                 if(buf->len > offset)
 691                         return (void *)((int)buf->data + offset);
 692                 if(buf->len > offset)
 693                         return NULL;
 694                 offset -= buf->len;
 695                 buf = buf->next;
 696         }
 697         return NULL;
 698 }
 699
 700 int cbuf_is_contig_region(cbuf *buf, size_t start, size_t end)
 701 {
 702         validate_cbuf(buf);
 703
 704         while(buf) {
 705                 if(buf->len > start) {
 706                         if(buf->len - start >= end)
 707                                 return 1;
 708                         else
 709                                 return 0;
 710                 }
 711                 start -= buf->len;
 712                 end -= buf->len;
 713                 buf = buf->next;
 714         }
 715         return 0;
 716 }
 717
 718 static uint16 _cbuf_ones_cksum16(cbuf *buf, size_t offset, size_t len, uint16 sum)
 719 {
 720         int swapped = 0;
 721
 722         if(!buf)
 723                 return sum;
 724
 725         validate_cbuf(buf);
 726
 727         // find the start ptr
 728         while(buf) {
 729                 if(buf->len > offset)
 730                         break;
 731                 if(buf->len > offset)
 732                         return 0;
 733                 offset -= buf->len;
 734                 buf = buf->next;
 735         }
 736
 737         // start checksumming
 738         while(buf && len > 0) {
 739                 void *ptr = (void *)((addr_t)buf->data + offset);
 740                 size_t plen = min(len, buf->len - offset);
 741
 742                 sum = ones_sum16(sum, ptr, plen);
 743
 744                 len -= plen;
 745                 buf = buf->next;
 746
 747                 // if the pointer was odd, or the length was odd, but not both,
 748                 // the checksum was swapped
 749                 if((buf && len > 0) && (((offset % 2) && ((plen % 2) == 0)) || (((offset % 2) == 0) && (plen % 2)))) {
 750                         swapped ^= 1;
 751                         sum = ((sum & 0xff) << 8) | ((sum >> 8) & 0xff);
 752                 }
 753                 offset = 0;
 754         }
 755
 756         if (swapped)
 757                 sum = ((sum & 0xff) << 8) | ((sum >> 8) & 0xff);
 758
 759         return sum;
 760 }
 761
 762 uint16 cbuf_ones_cksum16(cbuf *chain, size_t offset, size_t len)
 763 {
 764         return ~_cbuf_ones_cksum16(chain, offset, len, 0);
 765 }
 766
 767 uint16 cbuf_ones_cksum16_2(cbuf *chain, size_t offset, size_t len, void *buf, size_t buf_len)
 768 {
 769         uint16 sum = ones_sum16(0, buf, buf_len);
 770         return ~_cbuf_ones_cksum16(chain, offset, len, sum);
 771 }
 772
 773 cbuf *cbuf_truncate_head(cbuf *buf, size_t trunc_bytes, bool free_unused)
 774 {
 775         cbuf *head = buf;
 776         cbuf *free_chain = NULL;
 777
 778         if(!buf)
 779                 return head;
 780
 781         validate_cbuf(buf);
 782
 783         while(buf && trunc_bytes > 0) {
 784                 int to_trunc;
 785
 786                 to_trunc = min(trunc_bytes, buf->len);
 787
 788                 buf->len -= to_trunc;
 789                 buf->data = (void *)((int)buf->data + to_trunc);
 790
 791                 trunc_bytes -= to_trunc;
 792                 head->total_len -= to_trunc;
 793
 794                 buf = buf->next;
 795                 if(free_unused && buf && head->len == 0) {
 796                         // the head cbuf is now zero length
 797                         buf->total_len = head->total_len;
 798                         buf->flags |= CBUF_FLAG_CHAIN_HEAD;
 799                         buf->packet_next = head->packet_next;
 800
 801                         head->next = free_chain;
 802                         free_chain = head;
 803
 804                         head = buf;
 805                 }
 806         }
 807
 808         if(free_chain)
 809                 cbuf_free_chain(free_chain);
 810
 811         validate_cbuf(head);
 812
 813         return head;
 814 }
 815
 816 int cbuf_truncate_tail(cbuf *buf, size_t trunc_bytes, bool free_unused)
 817 {
 818         size_t offset;
 819         size_t buf_offset;
 820         cbuf *head = buf;
 821         cbuf *free_chain = NULL;
 822
 823         validate_cbuf(buf);
 824
 825         if(trunc_bytes > buf->total_len)
 826                 trunc_bytes = buf->total_len;
 827
 828         offset = buf->total_len - trunc_bytes;
 829         buf_offset = 0;
 830         while(buf && offset > 0) {
 831                 if(offset < buf->len) {
 832                         // this is the one
 833                         buf_offset = offset;
 834                         break;
 835                 }
 836                 offset -= buf->len;
 837                 buf = buf->next;
 838         }
 839         if(!buf)
 840                 return ERR_GENERAL;
 841
 842         head->total_len -= buf->len - buf_offset;
 843         buf->len -= buf->len - buf_offset;
 844
 845         // clear out the rest of the buffers in this chain
 846         buf = buf->next;
 847         while(buf) {
 848                 cbuf *temp = buf;
 849
 850                 // account for the loss of this buffer
 851                 head->total_len -= buf->len;
 852                 buf = buf->next;
 853
 854                 if(free_unused) {
 855                         // stick it on the free list that we'll dispose of in a bit
 856                         temp->next = free_chain;
 857                         free_chain = temp;
 858                 }
 859         }
 860
 861         if(free_chain)
 862                 cbuf_free_chain(free_chain);
 863
 864         validate_cbuf(head);
 865
 866         return NO_ERROR;
 867 }
 868
 869 int cbuf_extend_head(cbuf **_buf, size_t extend_bytes)
 870 {
 871         cbuf *buf;
 872
 873         if(!_buf || !(*_buf))
 874                 return ERR_INVALID_ARGS;
 875
 876         buf = *_buf;
 877
 878         validate_cbuf(buf);
 879
 880         // first, see how much space we can allocate off the front of the chain
 881         if(buf->len < sizeof(buf->dat) && (addr_t)buf->data != (addr_t)buf->dat) {
 882                 // there is some space at the front of this buffer, lets see how much
 883                 size_t available;
 884                 size_t to_extend;
 885
 886                 // check to make sure the data pointer is inside the dat buffer in this cbuf
 887                 ASSERT((addr_t)buf->data > (addr_t)buf->dat);
 888                 ASSERT((addr_t)buf->data - (addr_t)buf->dat < sizeof(buf->dat));
 889
 890                 available = (addr_t)buf->data - (addr_t)buf->dat;
 891                 to_extend = min(available, extend_bytes);
 892
 893                 buf->len += to_extend;
 894                 buf->data = (void *)((addr_t)buf->data - to_extend);
 895                 extend_bytes -= to_extend;
 896         }
 897
 898         if(extend_bytes > 0) {
 899                 cbuf *new_buf;
 900
 901                 new_buf = cbuf_get_chain(extend_bytes);
 902                 if(!new_buf)
 903                         return ERR_NO_MEMORY;
 904
 905                 if(new_buf->next == NULL) {
 906                         // simple case, the head extension is a single buffer.
 907                         // move the data in the head to the end of the cbuf (so subsequent extends)
 908                         // have a better shot at being able to reuse the cbuf.
 909                         size_t move_size;
 910
 911                         ASSERT(new_buf->len <= sizeof(new_buf->dat));
 912
 913                         move_size = sizeof(new_buf->dat) - new_buf->len;
 914
 915                         buf->data = (void *)((addr_t)buf->data + move_size);
 916                 }
 917
 918                 buf = cbuf_merge_chains(new_buf, buf);
 919         }
 920
 921         validate_cbuf(buf);
 922
 923         return NO_ERROR;
 924 }
 925
 926 int cbuf_extend_tail(cbuf *head, size_t extend_bytes)
 927 {
 928         cbuf *temp;
 929         size_t available;
 930
 931         if(!head)
 932                 return ERR_INVALID_ARGS;
 933
 934         validate_cbuf(head);
 935
 936         // walk to the end of this buffer
 937         for(temp = head; temp->next != NULL; temp = temp->next)
 938                 ;
 939         if(!temp)
 940                 return ERR_INVALID_ARGS;
 941
 942         // calculate the available space in this cbuf
 943         ASSERT((addr_t)temp->data >= (addr_t)temp->dat);
 944         ASSERT((addr_t)temp->data - (addr_t)temp->dat <= sizeof(temp->dat));
 945         ASSERT((addr_t)temp->data + temp->len <= (addr_t)temp->dat + sizeof(temp->dat));
 946
 947         available = sizeof(temp->dat) - (temp->len + ((addr_t)temp->data - (addr_t)temp->dat));
 948         if(available > 0) {
 949                 // we can extend by adding
 950                 size_t extend_by = min(available, extend_bytes);
 951
 952                 temp->len += extend_by;
 953                 head->total_len += extend_by;
 954                 extend_bytes -= extend_by;
 955         }
 956
 957         if(extend_bytes > 0) {
 958                 // we still need to extend
 959                 cbuf *new_buf;
 960
 961                 new_buf = cbuf_get_chain(extend_bytes);
 962                 if(!new_buf) {
 963                         // XXX undo any previons extension we may have done
 964                         return ERR_NO_MEMORY;
 965                 }
 966
 967                 cbuf_merge_chains(head, new_buf);
 968         }
 969
 970         return NO_ERROR;
 971 }
 972
 973
 974 static void dbg_dump_cbuf_freelists(int argc, char **argv)
 975 {
 976         cbuf *buf;
 977
 978         dprintf("cbuf_free_list:\n");
 979         for(buf = cbuf_free_list; buf; buf = buf->next)
 980                 dprintf("%p ", buf);
 981         dprintf("\n");
 982
 983         dprintf("cbuf_free_noblock_list:\n");
 984         for(buf = cbuf_free_noblock_list; buf; buf = buf->next)
 985                 dprintf("%p ", buf);
 986         dprintf("\n");
 987 }
 988
 989 void cbuf_test()
 990 {
 991         cbuf *buf, *buf2;
 992         char temp[1024];
 993         unsigned int i;
 994
 995         dprintf("starting cbuffer test\n");
 996
 997         buf = cbuf_get_chain(32);
 998         if(!buf)
 999                 panic("cbuf_test: failed allocation of 32\n");
1000
1001         buf2 = cbuf_get_chain(3*1024*1024);
1002         if(!buf2)
1003                 panic("cbuf_test: failed allocation of 3mb\n");
1004
1005         buf = cbuf_merge_chains(buf2, buf);
1006
1007         cbuf_free_chain(buf);
1008
1009         dprintf("allocating too much...\n");
1010
1011         buf = cbuf_get_chain(128*1024*1024);
1012         if(buf)
1013                 panic("cbuf_test: should have failed to allocate 128mb\n");
1014
1015         dprintf("touching memory allocated by cbuf\n");
1016
1017         buf = cbuf_get_chain(7*1024*1024);
1018         if(!buf)
1019                 panic("cbuf_test: failed allocation of 7mb\n");
1020
1021         for(i=0; i < sizeof(temp); i++)
1022                 temp[i] = i;
1023         for(i=0; i<7*1024*1024 / sizeof(temp); i++) {
1024                 if(i % 128 == 0) dprintf("%Lud\n", (long long)(i*sizeof(temp)));
1025                 cbuf_memcpy_to_chain(buf, i*sizeof(temp), temp, sizeof(temp));
1026         }
1027         cbuf_free_chain(buf);
1028
1029         dprintf("finished cbuffer test\n");
1030 }
1031
1032 int cbuf_init()
1033 {
1034         cbuf *buf;
1035         int i;
1036         int err;
1037
1038         cbuf_free_list = NULL;
1039         cbuf_free_noblock_list = NULL;
1040         noblock_spin = 0;
1041         cbuf_lowlevel_spinlock = 0;
1042
1043         // add the debug command
1044         dbg_add_command(&dbg_dump_cbuf_freelists, "cbuf_freelist", "Dumps the cbuf free lists");
1045
1046         err = mutex_init(&cbuf_free_list_lock, "cbuf_free_list_lock");
1047         if(err < 0) {
1048                 panic("cbuf_init: error creating cbuf_free_list_lock\n");
1049                 return ERR_NO_MEMORY;
1050         }
1051
1052         cbuf_region_id = vm_create_anonymous_region(vm_get_kernel_aspace_id(), "cbuf region",
1053                 (void **)&cbuf_region, REGION_ADDR_ANY_ADDRESS, CBUF_REGION_SIZE, REGION_WIRING_LAZY, LOCK_RW|LOCK_KERNEL);
1054         if(cbuf_region_id < 0) {
1055                 panic("cbuf_init: error creating cbuf region\n");
1056                 return ERR_NO_MEMORY;
1057         }
1058
1059         cbuf_bitmap_region_id = vm_create_anonymous_region(vm_get_kernel_aspace_id(), "cbuf bitmap region",
1060                 (void **)&cbuf_bitmap, REGION_ADDR_ANY_ADDRESS,
1061                 CBUF_BITMAP_SIZE / 8, REGION_WIRING_WIRED, LOCK_RW|LOCK_KERNEL);
1062         if(cbuf_region_id < 0) {
1063                 panic("cbuf_init: error creating cbuf bitmap region\n");
1064                 return ERR_NO_MEMORY;
1065         }
1066
1067         // initialize the bitmap
1068         for(i=0; i<CBUF_BITMAP_SIZE/8; i++)
1069                 cbuf_bitmap[i] = 0;
1070
1071 #if 0
1072         buf = allocate_cbuf_mem(ALLOCATE_CHUNK);
1073         if(buf == NULL)
1074                 return ERR_NO_MEMORY;
1075         cbuf_free_chain_noblock(buf);
1076 #endif
1077         buf = allocate_cbuf_mem(ALLOCATE_CHUNK);
1078         if(buf == NULL)
1079                 return ERR_NO_MEMORY;
1080
1081         cbuf_free_chain(buf);
1082
1083         return NO_ERROR;
1084 }