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