1 /* 2 * Copyright 2007, Hugo Santos. All Rights Reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Hugo Santos, hugosantos@gmail.com 7 */ 8 9 10 #include "slab_private.h" 11 12 #include <algorithm> 13 #include <new> 14 #include <stdlib.h> 15 #include <string.h> 16 17 #include <KernelExport.h> 18 19 #include <Depot.h> 20 #include <kernel.h> 21 #include <Slab.h> 22 #include <smp.h> 23 #include <util/AutoLock.h> 24 #include <util/DoublyLinkedList.h> 25 #include <util/OpenHashTable.h> 26 #include <vm.h> 27 #include <vm_low_memory.h> 28 29 30 // TODO kMagazineCapacity should be dynamically tuned per cache. 31 32 33 //#define TRACE_SLAB 34 35 #ifdef TRACE_SLAB 36 #define TRACE_CACHE(cache, format, args...) \ 37 dprintf("Cache[%p, %s] " format "\n", cache, cache->name , ##args) 38 #else 39 #define TRACE_CACHE(cache, format, bananas...) do { } while (0) 40 #endif 41 42 43 static const int kMagazineCapacity = 32; 44 static const size_t kCacheColorPeriod = 8; 45 46 struct object_link { 47 struct object_link *next; 48 }; 49 50 struct slab : DoublyLinkedListLinkImpl<slab> { 51 void *pages; 52 size_t count, size; 53 size_t offset; 54 object_link *free; 55 }; 56 57 typedef DoublyLinkedList<slab> SlabList; 58 59 struct object_cache : DoublyLinkedListLinkImpl<object_cache> { 60 char name[32]; 61 benaphore lock; 62 size_t object_size; 63 size_t cache_color_cycle; 64 SlabList empty, partial, full; 65 size_t used_count, empty_count, pressure; 66 67 size_t slab_size; 68 size_t usage, maximum; 69 uint32 flags; 70 71 void *cookie; 72 object_cache_constructor constructor; 73 object_cache_destructor destructor; 74 object_cache_reclaimer reclaimer; 75 76 status_t (*allocate_pages)(object_cache *cache, void **pages, 77 uint32 flags); 78 void (*free_pages)(object_cache *cache, void *pages); 79 80 object_depot depot; 81 82 virtual slab *CreateSlab(uint32 flags) = 0; 83 virtual void ReturnSlab(slab *slab) = 0; 84 virtual slab *ObjectSlab(void *object) const = 0; 85 86 slab *InitSlab(slab *slab, void *pages, size_t byteCount); 87 void UninitSlab(slab *slab); 88 89 virtual status_t PrepareObject(slab *source, void *object) { return B_OK; } 90 virtual void UnprepareObject(slab *source, void *object) {} 91 92 virtual ~object_cache() {} 93 }; 94 95 typedef DoublyLinkedList<object_cache> ObjectCacheList; 96 97 struct SmallObjectCache : object_cache { 98 slab *CreateSlab(uint32 flags); 99 void ReturnSlab(slab *slab); 100 slab *ObjectSlab(void *object) const; 101 }; 102 103 104 struct HashedObjectCache : object_cache { 105 struct Link : HashTableLink<Link> { 106 const void *buffer; 107 slab *parent; 108 }; 109 110 struct Definition { 111 typedef HashedObjectCache ParentType; 112 typedef const void * KeyType; 113 typedef Link ValueType; 114 115 Definition(HashedObjectCache *_parent) : parent(_parent) {} 116 Definition(const Definition& definition) : parent(definition.parent) {} 117 118 size_t HashKey(const void *key) const 119 { 120 return (((const uint8 *)key) - ((const uint8 *)0)) 121 >> parent->lower_boundary; 122 } 123 124 size_t Hash(Link *value) const { return HashKey(value->buffer); } 125 bool Compare(const void *key, Link *value) const 126 { return value->buffer == key; } 127 HashTableLink<Link> *GetLink(Link *value) const { return value; } 128 129 HashedObjectCache *parent; 130 }; 131 132 typedef OpenHashTable<Definition> HashTable; 133 134 HashedObjectCache() 135 : hash_table(this) {} 136 137 slab *CreateSlab(uint32 flags); 138 void ReturnSlab(slab *slab); 139 slab *ObjectSlab(void *object) const; 140 status_t PrepareObject(slab *source, void *object); 141 void UnprepareObject(slab *source, void *object); 142 143 HashTable hash_table; 144 size_t lower_boundary; 145 }; 146 147 148 struct depot_magazine { 149 struct depot_magazine *next; 150 uint16 current_round, round_count; 151 void *rounds[0]; 152 }; 153 154 155 struct depot_cpu_store { 156 benaphore lock; 157 struct depot_magazine *loaded, *previous; 158 }; 159 160 161 static ObjectCacheList sObjectCaches; 162 static benaphore sObjectCacheListLock; 163 164 static uint8 *sInitialBegin, *sInitialLimit, *sInitialPointer; 165 static kernel_args *sKernelArgs; 166 167 168 static status_t object_cache_reserve_internal(object_cache *cache, 169 size_t object_count, uint32 flags); 170 static status_t object_depot_init_locks(object_depot *depot); 171 static depot_magazine *alloc_magazine(); 172 static void free_magazine(depot_magazine *magazine); 173 174 template<typename Type> static Type * 175 _pop(Type* &head) 176 { 177 Type *oldHead = head; 178 head = head->next; 179 return oldHead; 180 } 181 182 183 template<typename Type> static inline void 184 _push(Type* &head, Type *object) 185 { 186 object->next = head; 187 head = object; 188 } 189 190 191 static inline void * 192 link_to_object(object_link *link, size_t objectSize) 193 { 194 return ((uint8 *)link) - (objectSize - sizeof(object_link)); 195 } 196 197 198 static inline object_link * 199 object_to_link(void *object, size_t objectSize) 200 { 201 return (object_link *)(((uint8 *)object) 202 + (objectSize - sizeof(object_link))); 203 } 204 205 206 static inline depot_cpu_store * 207 object_depot_cpu(object_depot *depot) 208 { 209 return &depot->stores[smp_get_current_cpu()]; 210 } 211 212 213 static inline int 214 __fls0(size_t value) 215 { 216 if (value == 0) 217 return -1; 218 219 int bit; 220 for (bit = 0; value != 1; bit++) 221 value >>= 1; 222 return bit; 223 } 224 225 226 static void * 227 internal_alloc(size_t size, uint32 flags) 228 { 229 if (flags & CACHE_DURING_BOOT) { 230 if ((sInitialPointer + size) > sInitialLimit) 231 panic("internal_alloc: ran out of initial space"); 232 233 uint8 *buffer = sInitialPointer; 234 sInitialPointer += size; 235 return buffer; 236 } 237 238 return block_alloc(size); 239 } 240 241 242 static void 243 internal_free(void *_buffer) 244 { 245 uint8 *buffer = (uint8 *)_buffer; 246 247 if (buffer >= sInitialBegin && buffer < sInitialLimit) 248 return; 249 250 block_free(buffer); 251 } 252 253 254 static status_t 255 benaphore_boot_init(benaphore *lock, const char *name, uint32 flags) 256 { 257 if (flags & CACHE_DURING_BOOT) { 258 lock->sem = -1; 259 lock->count = 1; 260 return B_OK; 261 } 262 263 return benaphore_init(lock, name); 264 } 265 266 267 static status_t 268 area_allocate_pages(object_cache *cache, void **pages, uint32 flags) 269 { 270 TRACE_CACHE(cache, "allocate pages (%lu, 0x0%lx)", cache->slab_size, flags); 271 272 uint32 lock = B_FULL_LOCK; 273 if (cache->flags & CACHE_UNLOCKED_PAGES) 274 lock = B_NO_LOCK; 275 276 // if we are allocating, it is because we need the pages immediatly 277 // so we lock them. when moving the slab to the empty list we should 278 // unlock them, and lock them again when getting one from the empty list. 279 area_id areaId = create_area(cache->name, pages, B_ANY_KERNEL_ADDRESS, 280 cache->slab_size, lock, B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA); 281 if (areaId < 0) 282 return areaId; 283 284 cache->usage += cache->slab_size; 285 286 TRACE_CACHE(cache, " ... = { %ld, %p }", areaId, *pages); 287 288 return B_OK; 289 } 290 291 292 static void 293 area_free_pages(object_cache *cache, void *pages) 294 { 295 area_id id = area_for(pages); 296 297 TRACE_CACHE(cache, "delete pages %p (%ld)", pages, id); 298 299 if (id < B_OK) 300 panic("object cache: freeing unknown area"); 301 302 delete_area(id); 303 304 cache->usage -= cache->slab_size; 305 } 306 307 308 static status_t 309 early_allocate_pages(object_cache *cache, void **pages, uint32 flags) 310 { 311 TRACE_CACHE(cache, "early allocate pages (%lu, 0x0%lx)", cache->slab_size, 312 flags); 313 314 addr_t base = vm_allocate_early(sKernelArgs, cache->slab_size, 315 cache->slab_size, B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA); 316 317 *pages = (void *)base; 318 319 cache->usage += cache->slab_size; 320 321 TRACE_CACHE(cache, " ... = { %p }", *pages); 322 323 return B_OK; 324 } 325 326 327 static void 328 early_free_pages(object_cache *cache, void *pages) 329 { 330 panic("memory pressure on bootup?"); 331 } 332 333 334 static void 335 object_cache_low_memory(void *_self, int32 level) 336 { 337 if (level == B_NO_LOW_MEMORY) 338 return; 339 340 object_cache *cache = (object_cache *)_self; 341 342 // we are calling the reclaimer without the object cache lock 343 // to give the owner a chance to return objects to the slabs. 344 // As we only register the low memory handler after we complete 345 // the init of the object cache, unless there are some funky 346 // memory re-order business going on, we should be ok. 347 348 if (cache->reclaimer) 349 cache->reclaimer(cache->cookie, level); 350 351 BenaphoreLocker _(cache->lock); 352 size_t minimumAllowed; 353 354 switch (level) { 355 case B_LOW_MEMORY_NOTE: 356 minimumAllowed = cache->pressure / 2 + 1; 357 break; 358 359 case B_LOW_MEMORY_WARNING: 360 cache->pressure /= 2; 361 minimumAllowed = 0; 362 break; 363 364 default: 365 cache->pressure = 0; 366 minimumAllowed = 0; 367 break; 368 } 369 370 if (cache->empty_count <= minimumAllowed) 371 return; 372 373 TRACE_CACHE(cache, "cache: memory pressure, will release down to %lu.", 374 minimumAllowed); 375 376 while (cache->empty_count > minimumAllowed) { 377 cache->ReturnSlab(cache->empty.RemoveHead()); 378 cache->empty_count--; 379 } 380 } 381 382 383 static void 384 object_cache_return_object_wrapper(object_depot *depot, void *object) 385 { 386 object_cache *cache = (object_cache *)(((uint8 *)depot) 387 - offsetof(object_cache, depot)); 388 389 object_cache_free(cache, object); 390 } 391 392 393 static status_t 394 object_cache_init(object_cache *cache, const char *name, size_t objectSize, 395 size_t alignment, size_t maximum, uint32 flags, void *cookie, 396 object_cache_constructor constructor, object_cache_destructor destructor, 397 object_cache_reclaimer reclaimer) 398 { 399 strlcpy(cache->name, name, sizeof(cache->name)); 400 401 status_t status = benaphore_boot_init(&cache->lock, name, flags); 402 if (status < B_OK) 403 return status; 404 405 if (objectSize < sizeof(object_link)) 406 objectSize = sizeof(object_link); 407 408 if (alignment > 0 && (objectSize & (alignment - 1))) 409 cache->object_size = objectSize + alignment 410 - (objectSize & (alignment - 1)); 411 else 412 cache->object_size = objectSize; 413 414 TRACE_CACHE(cache, "init %lu, %lu -> %lu", objectSize, alignment, 415 cache->object_size); 416 417 cache->cache_color_cycle = 0; 418 cache->used_count = 0; 419 cache->empty_count = 0; 420 cache->pressure = 0; 421 422 cache->usage = 0; 423 cache->maximum = maximum; 424 425 cache->flags = flags; 426 427 // no gain in using the depot in single cpu setups 428 if (smp_get_num_cpus() == 1) 429 cache->flags |= CACHE_NO_DEPOT; 430 431 if (!(cache->flags & CACHE_NO_DEPOT)) { 432 status_t status = object_depot_init(&cache->depot, flags, 433 object_cache_return_object_wrapper); 434 if (status < B_OK) { 435 benaphore_destroy(&cache->lock); 436 return status; 437 } 438 } 439 440 cache->cookie = cookie; 441 cache->constructor = constructor; 442 cache->destructor = destructor; 443 cache->reclaimer = reclaimer; 444 445 if (cache->flags & CACHE_DURING_BOOT) { 446 cache->allocate_pages = early_allocate_pages; 447 cache->free_pages = early_free_pages; 448 } else { 449 cache->allocate_pages = area_allocate_pages; 450 cache->free_pages = area_free_pages; 451 } 452 453 register_low_memory_handler(object_cache_low_memory, cache, 5); 454 455 BenaphoreLocker _(sObjectCacheListLock); 456 sObjectCaches.Add(cache); 457 458 return B_OK; 459 } 460 461 462 static status_t 463 object_cache_init_locks(object_cache *cache) 464 { 465 status_t status = benaphore_init(&cache->lock, cache->name); 466 if (status < B_OK) 467 return status; 468 469 if (cache->flags & CACHE_NO_DEPOT) 470 return B_OK; 471 472 return object_depot_init_locks(&cache->depot); 473 } 474 475 476 static void 477 object_cache_commit_slab(object_cache *cache, slab *slab) 478 { 479 void *pages = (void *)ROUNDOWN((addr_t)slab->pages, B_PAGE_SIZE); 480 if (create_area(cache->name, &pages, B_EXACT_ADDRESS, cache->slab_size, 481 B_ALREADY_WIRED, B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA) < B_OK) 482 panic("failed to create_area()"); 483 } 484 485 486 static void 487 object_cache_commit_pre_pages(object_cache *cache) 488 { 489 SlabList::Iterator it = cache->full.GetIterator(); 490 while (it.HasNext()) 491 object_cache_commit_slab(cache, it.Next()); 492 493 it = cache->partial.GetIterator(); 494 while (it.HasNext()) 495 object_cache_commit_slab(cache, it.Next()); 496 497 it = cache->empty.GetIterator(); 498 while (it.HasNext()) 499 object_cache_commit_slab(cache, it.Next()); 500 501 cache->allocate_pages = area_allocate_pages; 502 cache->free_pages = area_free_pages; 503 } 504 505 506 static void 507 delete_cache(object_cache *cache) 508 { 509 cache->~object_cache(); 510 internal_free(cache); 511 } 512 513 514 static SmallObjectCache * 515 create_small_object_cache(const char *name, size_t object_size, 516 size_t alignment, size_t maximum, uint32 flags, void *cookie, 517 object_cache_constructor constructor, object_cache_destructor destructor, 518 object_cache_reclaimer reclaimer) 519 { 520 void *buffer = internal_alloc(sizeof(SmallObjectCache), flags); 521 if (buffer == NULL) 522 return NULL; 523 524 SmallObjectCache *cache = new (buffer) SmallObjectCache(); 525 526 if (object_cache_init(cache, name, object_size, alignment, maximum, flags, 527 cookie, constructor, destructor, reclaimer) < B_OK) { 528 delete_cache(cache); 529 return NULL; 530 } 531 532 cache->slab_size = B_PAGE_SIZE; 533 534 return cache; 535 } 536 537 538 static HashedObjectCache * 539 create_hashed_object_cache(const char *name, size_t object_size, 540 size_t alignment, size_t maximum, uint32 flags, void *cookie, 541 object_cache_constructor constructor, object_cache_destructor destructor, 542 object_cache_reclaimer reclaimer) 543 { 544 void *buffer = internal_alloc(sizeof(HashedObjectCache), flags); 545 if (buffer == NULL) 546 return NULL; 547 548 HashedObjectCache *cache = new (buffer) HashedObjectCache(); 549 550 if (object_cache_init(cache, name, object_size, alignment, maximum, flags, 551 cookie, constructor, destructor, reclaimer) < B_OK) { 552 delete_cache(cache); 553 return NULL; 554 } 555 556 cache->slab_size = max_c(16 * B_PAGE_SIZE, 8 * object_size); 557 cache->lower_boundary = __fls0(cache->object_size); 558 559 return cache; 560 } 561 562 563 object_cache * 564 create_object_cache(const char *name, size_t object_size, size_t alignment, 565 void *cookie, object_cache_constructor constructor, 566 object_cache_destructor destructor) 567 { 568 return create_object_cache_etc(name, object_size, alignment, 0, 0, cookie, 569 constructor, destructor, NULL); 570 } 571 572 573 object_cache * 574 create_object_cache_etc(const char *name, size_t object_size, size_t alignment, 575 size_t maximum, uint32 flags, void *cookie, 576 object_cache_constructor constructor, object_cache_destructor destructor, 577 object_cache_reclaimer reclaimer) 578 { 579 if (object_size == 0) 580 return NULL; 581 else if (object_size <= 256) 582 return create_small_object_cache(name, object_size, alignment, 583 maximum, flags, cookie, constructor, destructor, reclaimer); 584 585 return create_hashed_object_cache(name, object_size, alignment, 586 maximum, flags, cookie, constructor, destructor, reclaimer); 587 } 588 589 590 void 591 delete_object_cache(object_cache *cache) 592 { 593 { 594 BenaphoreLocker _(sObjectCacheListLock); 595 sObjectCaches.Remove(cache); 596 } 597 598 benaphore_lock(&cache->lock); 599 600 if (!(cache->flags & CACHE_NO_DEPOT)) 601 object_depot_destroy(&cache->depot); 602 603 unregister_low_memory_handler(object_cache_low_memory, cache); 604 605 if (!cache->full.IsEmpty()) 606 panic("cache destroy: still has full slabs"); 607 608 if (!cache->partial.IsEmpty()) 609 panic("cache destroy: still has partial slabs"); 610 611 while (!cache->empty.IsEmpty()) 612 cache->ReturnSlab(cache->empty.RemoveHead()); 613 614 benaphore_destroy(&cache->lock); 615 delete_cache(cache); 616 } 617 618 619 void * 620 object_cache_alloc(object_cache *cache, uint32 flags) 621 { 622 // flags are read only. 623 if (!(cache->flags & CACHE_NO_DEPOT)) { 624 void *object = object_depot_obtain(&cache->depot); 625 if (object) 626 return object; 627 } 628 629 BenaphoreLocker _(cache->lock); 630 slab *source; 631 632 if (cache->partial.IsEmpty()) { 633 if (cache->empty.IsEmpty()) { 634 if (object_cache_reserve_internal(cache, 1, flags) < B_OK) 635 return NULL; 636 637 cache->pressure++; 638 } 639 640 source = cache->empty.RemoveHead(); 641 cache->empty_count--; 642 cache->partial.Add(source); 643 } else { 644 source = cache->partial.Head(); 645 } 646 647 object_link *link = _pop(source->free); 648 source->count--; 649 cache->used_count++; 650 651 TRACE_CACHE(cache, "allocate %p (%p) from %p, %lu remaining.", 652 link_to_object(link, cache->object_size), link, source, source->count); 653 654 if (source->count == 0) { 655 cache->partial.Remove(source); 656 cache->full.Add(source); 657 } 658 659 return link_to_object(link, cache->object_size); 660 } 661 662 663 static void 664 object_cache_return_to_slab(object_cache *cache, slab *source, void *object) 665 { 666 if (source == NULL) 667 panic("object_cache: free'd object has no slab"); 668 669 object_link *link = object_to_link(object, cache->object_size); 670 671 TRACE_CACHE(cache, "returning %p (%p) to %p, %lu used (%lu empty slabs).", 672 object, link, source, source->size - source->count, 673 cache->empty_count); 674 675 _push(source->free, link); 676 source->count++; 677 cache->used_count--; 678 679 if (source->count == source->size) { 680 cache->partial.Remove(source); 681 682 if (cache->empty_count < cache->pressure) { 683 cache->empty_count++; 684 cache->empty.Add(source); 685 } else { 686 cache->ReturnSlab(source); 687 } 688 } else if (source->count == 1) { 689 cache->full.Remove(source); 690 cache->partial.Add(source); 691 } 692 } 693 694 695 void 696 object_cache_free(object_cache *cache, void *object) 697 { 698 // flags are read only. 699 if (!(cache->flags & CACHE_NO_DEPOT)) { 700 if (object_depot_store(&cache->depot, object)) 701 return; 702 } 703 704 BenaphoreLocker _(cache->lock); 705 object_cache_return_to_slab(cache, cache->ObjectSlab(object), object); 706 } 707 708 709 static status_t 710 object_cache_reserve_internal(object_cache *cache, size_t object_count, 711 uint32 flags) 712 { 713 size_t numBytes = object_count * cache->object_size; 714 size_t slabCount = ((numBytes - 1) / cache->slab_size) + 1; 715 716 while (slabCount > 0) { 717 slab *newSlab = cache->CreateSlab(flags); 718 if (newSlab == NULL) 719 return B_NO_MEMORY; 720 721 cache->empty.Add(newSlab); 722 cache->empty_count++; 723 slabCount--; 724 } 725 726 return B_OK; 727 } 728 729 730 status_t 731 object_cache_reserve(object_cache *cache, size_t object_count, uint32 flags) 732 { 733 if (object_count == 0) 734 return B_OK; 735 736 BenaphoreLocker _(cache->lock); 737 return object_cache_reserve_internal(cache, object_count, flags); 738 } 739 740 741 slab * 742 object_cache::InitSlab(slab *slab, void *pages, size_t byteCount) 743 { 744 TRACE_CACHE(this, "construct (%p, %p .. %p, %lu)", slab, pages, 745 ((uint8 *)pages) + byteCount, byteCount); 746 747 slab->pages = pages; 748 slab->count = slab->size = byteCount / object_size; 749 slab->free = NULL; 750 751 size_t spareBytes = byteCount - (slab->size * object_size); 752 slab->offset = cache_color_cycle; 753 754 if (slab->offset > spareBytes) 755 cache_color_cycle = slab->offset = 0; 756 else 757 cache_color_cycle += kCacheColorPeriod; 758 759 TRACE_CACHE(this, " %lu objects, %lu spare bytes, offset %lu", 760 slab->size, spareBytes, slab->offset); 761 762 uint8 *data = ((uint8 *)pages) + slab->offset; 763 764 for (size_t i = 0; i < slab->size; i++) { 765 bool failedOnFirst = false; 766 767 status_t status = PrepareObject(slab, data); 768 if (status < B_OK) 769 failedOnFirst = true; 770 else if (constructor) 771 status = constructor(cookie, data); 772 773 if (status < B_OK) { 774 if (!failedOnFirst) 775 UnprepareObject(slab, data); 776 777 data = ((uint8 *)pages) + slab->offset; 778 for (size_t j = 0; j < i; j++) { 779 if (destructor) 780 destructor(cookie, data); 781 UnprepareObject(slab, data); 782 data += object_size; 783 } 784 785 return NULL; 786 } 787 788 _push(slab->free, object_to_link(data, object_size)); 789 data += object_size; 790 } 791 792 return slab; 793 } 794 795 796 void 797 object_cache::UninitSlab(slab *slab) 798 { 799 TRACE_CACHE(this, "destruct %p", slab); 800 801 if (slab->count != slab->size) 802 panic("cache: destroying a slab which isn't empty."); 803 804 uint8 *data = ((uint8 *)slab->pages) + slab->offset; 805 806 for (size_t i = 0; i < slab->size; i++) { 807 if (destructor) 808 destructor(cookie, data); 809 UnprepareObject(slab, data); 810 data += object_size; 811 } 812 } 813 814 815 static inline slab * 816 slab_in_pages(const void *pages, size_t slab_size) 817 { 818 return (slab *)(((uint8 *)pages) + slab_size - sizeof(slab)); 819 } 820 821 822 static inline const void * 823 lower_boundary(void *object, size_t byteCount) 824 { 825 const uint8 *null = (uint8 *)NULL; 826 return null + ((((uint8 *)object) - null) & ~(byteCount - 1)); 827 } 828 829 830 static inline bool 831 check_cache_quota(object_cache *cache) 832 { 833 if (cache->maximum == 0) 834 return true; 835 836 return (cache->usage + cache->slab_size) <= cache->maximum; 837 } 838 839 840 slab * 841 SmallObjectCache::CreateSlab(uint32 flags) 842 { 843 if (!check_cache_quota(this)) 844 return NULL; 845 846 void *pages; 847 848 if (allocate_pages(this, &pages, flags) < B_OK) 849 return NULL; 850 851 return InitSlab(slab_in_pages(pages, slab_size), pages, 852 slab_size - sizeof(slab)); 853 } 854 855 856 void 857 SmallObjectCache::ReturnSlab(slab *slab) 858 { 859 UninitSlab(slab); 860 free_pages(this, slab->pages); 861 } 862 863 864 slab * 865 SmallObjectCache::ObjectSlab(void *object) const 866 { 867 return slab_in_pages(lower_boundary(object, slab_size), slab_size); 868 } 869 870 871 static slab * 872 allocate_slab(uint32 flags) 873 { 874 return (slab *)internal_alloc(sizeof(slab), flags); 875 } 876 877 878 static void 879 free_slab(slab *slab) 880 { 881 internal_free(slab); 882 } 883 884 885 static HashedObjectCache::Link * 886 allocate_link(uint32 flags) 887 { 888 return (HashedObjectCache::Link *) 889 internal_alloc(sizeof(HashedObjectCache::Link), flags); 890 } 891 892 893 static void 894 free_link(HashedObjectCache::Link *link) 895 { 896 internal_free(link); 897 } 898 899 900 slab * 901 HashedObjectCache::CreateSlab(uint32 flags) 902 { 903 if (!check_cache_quota(this)) 904 return NULL; 905 906 slab *slab = allocate_slab(flags); 907 if (slab == NULL) 908 return NULL; 909 910 void *pages; 911 912 if (allocate_pages(this, &pages, flags) == B_OK) { 913 if (InitSlab(slab, pages, slab_size)) 914 return slab; 915 916 free_pages(this, pages); 917 } 918 919 free_slab(slab); 920 return NULL; 921 } 922 923 924 void 925 HashedObjectCache::ReturnSlab(slab *slab) 926 { 927 UninitSlab(slab); 928 free_pages(this, slab->pages); 929 } 930 931 932 slab * 933 HashedObjectCache::ObjectSlab(void *object) const 934 { 935 Link *link = hash_table.Lookup(object); 936 if (link == NULL) 937 panic("object cache: requested object missing from hash table"); 938 return link->parent; 939 } 940 941 942 status_t 943 HashedObjectCache::PrepareObject(slab *source, void *object) 944 { 945 Link *link = allocate_link(CACHE_DONT_SLEEP); 946 if (link == NULL) 947 return B_NO_MEMORY; 948 949 link->buffer = object; 950 link->parent = source; 951 952 hash_table.Insert(link); 953 return B_OK; 954 } 955 956 957 void 958 HashedObjectCache::UnprepareObject(slab *source, void *object) 959 { 960 Link *link = hash_table.Lookup(object); 961 if (link == NULL) 962 panic("object cache: requested object missing from hash table"); 963 if (link->parent != source) 964 panic("object cache: slab mismatch"); 965 966 hash_table.Remove(link); 967 free_link(link); 968 } 969 970 971 static inline bool 972 is_magazine_empty(depot_magazine *magazine) 973 { 974 return magazine->current_round == 0; 975 } 976 977 978 static inline bool 979 is_magazine_full(depot_magazine *magazine) 980 { 981 return magazine->current_round == magazine->round_count; 982 } 983 984 985 static inline void * 986 pop_magazine(depot_magazine *magazine) 987 { 988 return magazine->rounds[--magazine->current_round]; 989 } 990 991 992 static inline bool 993 push_magazine(depot_magazine *magazine, void *object) 994 { 995 if (is_magazine_full(magazine)) 996 return false; 997 magazine->rounds[magazine->current_round++] = object; 998 return true; 999 } 1000 1001 1002 static bool 1003 exchange_with_full(object_depot *depot, depot_magazine* &magazine) 1004 { 1005 BenaphoreLocker _(depot->lock); 1006 1007 if (depot->full == NULL) 1008 return false; 1009 1010 depot->full_count--; 1011 depot->empty_count++; 1012 1013 _push(depot->empty, magazine); 1014 magazine = _pop(depot->full); 1015 return true; 1016 } 1017 1018 1019 static bool 1020 exchange_with_empty(object_depot *depot, depot_magazine* &magazine) 1021 { 1022 BenaphoreLocker _(depot->lock); 1023 1024 if (depot->empty == NULL) { 1025 depot->empty = alloc_magazine(); 1026 if (depot->empty == NULL) 1027 return false; 1028 } else { 1029 depot->empty_count--; 1030 } 1031 1032 if (magazine) { 1033 _push(depot->full, magazine); 1034 depot->full_count++; 1035 } 1036 1037 magazine = _pop(depot->empty); 1038 return true; 1039 } 1040 1041 1042 static depot_magazine * 1043 alloc_magazine() 1044 { 1045 depot_magazine *magazine = (depot_magazine *)internal_alloc( 1046 sizeof(depot_magazine) + kMagazineCapacity * sizeof(void *), 0); 1047 if (magazine) { 1048 magazine->next = NULL; 1049 magazine->current_round = 0; 1050 magazine->round_count = kMagazineCapacity; 1051 } 1052 1053 return magazine; 1054 } 1055 1056 1057 static void 1058 free_magazine(depot_magazine *magazine) 1059 { 1060 internal_free(magazine); 1061 } 1062 1063 1064 static void 1065 empty_magazine(object_depot *depot, depot_magazine *magazine) 1066 { 1067 for (uint16 i = 0; i < magazine->current_round; i++) 1068 depot->return_object(depot, magazine->rounds[i]); 1069 free_magazine(magazine); 1070 } 1071 1072 1073 status_t 1074 object_depot_init(object_depot *depot, uint32 flags, 1075 void (*return_object)(object_depot *depot, void *object)) 1076 { 1077 depot->full = NULL; 1078 depot->empty = NULL; 1079 depot->full_count = depot->empty_count = 0; 1080 1081 status_t status = benaphore_boot_init(&depot->lock, "depot", flags); 1082 if (status < B_OK) 1083 return status; 1084 1085 depot->stores = (depot_cpu_store *)internal_alloc(sizeof(depot_cpu_store) 1086 * smp_get_num_cpus(), flags); 1087 if (depot->stores == NULL) { 1088 benaphore_destroy(&depot->lock); 1089 return B_NO_MEMORY; 1090 } 1091 1092 for (int i = 0; i < smp_get_num_cpus(); i++) { 1093 benaphore_boot_init(&depot->stores[i].lock, "cpu store", flags); 1094 depot->stores[i].loaded = depot->stores[i].previous = NULL; 1095 } 1096 1097 depot->return_object = return_object; 1098 1099 return B_OK; 1100 } 1101 1102 1103 status_t 1104 object_depot_init_locks(object_depot *depot) 1105 { 1106 status_t status = benaphore_init(&depot->lock, "depot"); 1107 if (status < B_OK) 1108 return status; 1109 1110 for (int i = 0; i < smp_get_num_cpus(); i++) { 1111 status = benaphore_init(&depot->stores[i].lock, "cpu store"); 1112 if (status < B_OK) 1113 return status; 1114 } 1115 1116 return B_OK; 1117 } 1118 1119 1120 void 1121 object_depot_destroy(object_depot *depot) 1122 { 1123 object_depot_make_empty(depot); 1124 1125 for (int i = 0; i < smp_get_num_cpus(); i++) { 1126 benaphore_destroy(&depot->stores[i].lock); 1127 } 1128 1129 internal_free(depot->stores); 1130 1131 benaphore_destroy(&depot->lock); 1132 } 1133 1134 1135 static void * 1136 object_depot_obtain_from_store(object_depot *depot, depot_cpu_store *store) 1137 { 1138 BenaphoreLocker _(store->lock); 1139 1140 // To better understand both the Alloc() and Free() logic refer to 1141 // Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings] 1142 1143 // In a nutshell, we try to get an object from the loaded magazine 1144 // if it's not empty, or from the previous magazine if it's full 1145 // and finally from the Slab if the magazine depot has no full magazines. 1146 1147 if (store->loaded == NULL) 1148 return NULL; 1149 1150 while (true) { 1151 if (!is_magazine_empty(store->loaded)) 1152 return pop_magazine(store->loaded); 1153 1154 if (store->previous && (is_magazine_full(store->previous) 1155 || exchange_with_full(depot, store->previous))) 1156 std::swap(store->previous, store->loaded); 1157 else 1158 return NULL; 1159 } 1160 } 1161 1162 1163 static int 1164 object_depot_return_to_store(object_depot *depot, depot_cpu_store *store, 1165 void *object) 1166 { 1167 BenaphoreLocker _(store->lock); 1168 1169 // We try to add the object to the loaded magazine if we have one 1170 // and it's not full, or to the previous one if it is empty. If 1171 // the magazine depot doesn't provide us with a new empty magazine 1172 // we return the object directly to the slab. 1173 1174 while (true) { 1175 if (store->loaded && push_magazine(store->loaded, object)) 1176 return 1; 1177 1178 if ((store->previous && is_magazine_empty(store->previous)) 1179 || exchange_with_empty(depot, store->previous)) 1180 std::swap(store->loaded, store->previous); 1181 else 1182 return 0; 1183 } 1184 } 1185 1186 1187 void * 1188 object_depot_obtain(object_depot *depot) 1189 { 1190 return object_depot_obtain_from_store(depot, object_depot_cpu(depot)); 1191 } 1192 1193 1194 int 1195 object_depot_store(object_depot *depot, void *object) 1196 { 1197 return object_depot_return_to_store(depot, object_depot_cpu(depot), 1198 object); 1199 } 1200 1201 1202 void 1203 object_depot_make_empty(object_depot *depot) 1204 { 1205 for (int i = 0; i < smp_get_num_cpus(); i++) { 1206 depot_cpu_store *store = &depot->stores[i]; 1207 1208 BenaphoreLocker _(store->lock); 1209 1210 if (depot->stores[i].loaded) 1211 empty_magazine(depot, depot->stores[i].loaded); 1212 if (depot->stores[i].previous) 1213 empty_magazine(depot, depot->stores[i].previous); 1214 depot->stores[i].loaded = depot->stores[i].previous = NULL; 1215 } 1216 1217 BenaphoreLocker _(depot->lock); 1218 1219 while (depot->full) 1220 empty_magazine(depot, _pop(depot->full)); 1221 1222 while (depot->empty) 1223 empty_magazine(depot, _pop(depot->empty)); 1224 } 1225 1226 1227 static int 1228 dump_slabs(int argc, char *argv[]) 1229 { 1230 kprintf("%10s %22s %8s %8s %6s %8s %8s %8s\n", "address", "name", 1231 "objsize", "usage", "empty", "usedobj", "total", "flags"); 1232 1233 ObjectCacheList::Iterator it = sObjectCaches.GetIterator(); 1234 1235 while (it.HasNext()) { 1236 object_cache *cache = it.Next(); 1237 1238 kprintf("%p %22s %8lu %8lu %6lu %8lu %8lu %8lx\n", cache, cache->name, 1239 cache->object_size, cache->usage, cache->empty_count, 1240 cache->used_count, cache->usage / cache->object_size, 1241 cache->flags); 1242 } 1243 1244 return 0; 1245 } 1246 1247 1248 static int 1249 dump_cache_info(int argc, char *argv[]) 1250 { 1251 if (argc < 2) { 1252 kprintf("usage: cache_info [address]\n"); 1253 return 0; 1254 } 1255 1256 object_cache *cache = (object_cache *)strtoul(argv[1], NULL, 16); 1257 1258 kprintf("name: %s\n", cache->name); 1259 kprintf("lock: { count: %ld, sem: %ld }\n", cache->lock.count, 1260 cache->lock.sem); 1261 kprintf("object_size: %lu\n", cache->object_size); 1262 kprintf("cache_color_cycle: %lu\n", cache->cache_color_cycle); 1263 kprintf("used_count: %lu\n", cache->used_count); 1264 kprintf("empty_count: %lu\n", cache->empty_count); 1265 kprintf("pressure: %lu\n", cache->pressure); 1266 kprintf("slab_size: %lu\n", cache->slab_size); 1267 kprintf("usage: %lu\n", cache->usage); 1268 kprintf("maximum: %lu\n", cache->maximum); 1269 kprintf("flags: 0x%lx\n", cache->flags); 1270 kprintf("cookie: %p\n", cache->cookie); 1271 1272 return 0; 1273 } 1274 1275 1276 void 1277 slab_init(kernel_args *args, addr_t initialBase, size_t initialSize) 1278 { 1279 dprintf("slab: init base %p + 0x%lx\n", (void *)initialBase, initialSize); 1280 1281 sInitialBegin = (uint8 *)initialBase; 1282 sInitialLimit = sInitialBegin + initialSize; 1283 sInitialPointer = sInitialBegin; 1284 1285 sKernelArgs = args; 1286 1287 new (&sObjectCaches) ObjectCacheList(); 1288 1289 block_allocator_init_boot(); 1290 1291 add_debugger_command("slabs", dump_slabs, "list all object caches"); 1292 add_debugger_command("cache_info", dump_cache_info, 1293 "dump information about a specific cache"); 1294 } 1295 1296 1297 void 1298 slab_init_post_sem() 1299 { 1300 status_t status = benaphore_init(&sObjectCacheListLock, "object cache list"); 1301 if (status < B_OK) 1302 panic("slab_init: failed to create object cache list lock"); 1303 1304 ObjectCacheList::Iterator it = sObjectCaches.GetIterator(); 1305 1306 while (it.HasNext()) { 1307 object_cache *cache = it.Next(); 1308 if (object_cache_init_locks(cache) < B_OK) 1309 panic("slab_init: failed to create sems"); 1310 if (cache->allocate_pages == early_allocate_pages) 1311 object_cache_commit_pre_pages(cache); 1312 } 1313 1314 block_allocator_init_rest(); 1315 } 1316 1317