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 <stdio.h> 12#include <malloc.h> 13 14 15// TODO this value should be dynamically tuned per cache. 16static const int kMagazineCapacity = 32; 17 18static const size_t kCacheColorPeriod = 8; 19 20 21template<typename Type> static Type * 22SListPop(Type* &head) 23{ 24 Type *oldHead = head; 25 head = head->next; 26 return oldHead; 27} 28 29 30template<typename Type> static inline void 31SListPush(Type* &head, Type *object) 32{ 33 object->next = head; 34 head = object; 35} 36 37 38status_t 39MallocBackend::AllocatePages(BaseCache *cache, AllocationID *id, void **pages, 40 size_t byteCount, uint32_t flags) 41{ 42 size_t alignment = 16; 43 44 if (flags & CACHE_ALIGN_TO_PAGE_TOTAL) 45 alignment = byteCount; 46 47 *pages = memalign(alignment, byteCount); 48 if (*pages == NULL) 49 return B_NO_MEMORY; 50 51 *id = *pages; 52 return B_OK; 53} 54 55void 56MallocBackend::FreePages(BaseCache *cache, void *pages) 57{ 58 free(pages); 59} 60 61 62status_t 63AreaBackend::AllocatePages(BaseCache *cache, area_id *id, void **pages, 64 size_t byteCount, uint32_t flags) 65{ 66 if (flags & CACHE_ALIGN_TO_PAGE_TOTAL) 67 ; // panic() 68 69 area_id areaId = create_area(cache->Name(), pages, B_ANY_ADDRESS, //B_ANY_KERNEL_ADDRESS, 70 byteCount, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA); 71 if (areaId < 0) 72 return areaId; 73 74 printf("AreaBackend::AllocatePages() = { %ld, %p }\n", areaId, *pages); 75 76 *id = areaId; 77 return B_OK; 78} 79 80void 81AreaBackend::FreePages(BaseCache *cache, area_id area) 82{ 83 printf("AreaBackend::DeletePages(%ld)\n", area); 84 delete_area(area); 85} 86 87 88BaseCache::BaseCache(const char *_name, size_t objectSize, size_t alignment, 89 Constructor _constructor, Destructor _destructor, void *_cookie) 90 : fConstructor(_constructor), fDestructor(_destructor), fCookie(_cookie) 91{ 92 strncpy(fName, _name, sizeof(fName)); 93 fName[sizeof(fName) - 1] = 0; 94 95 if (alignment > 0 && (objectSize & (alignment - 1))) 96 fObjectSize = objectSize + alignment - (objectSize & (alignment - 1)); 97 else 98 fObjectSize = objectSize; 99 100 fCacheColorCycle = 0; 101} 102 103 104BaseCache::ObjectLink *BaseCache::AllocateObject() 105{ 106 Slab *slab = fPartialSlabs.Head(); 107 108 printf("BaseCache::AllocateObject() from %p, %lu remaining\n", 109 slab, slab->count); 110 111 ObjectLink *link = SListPop(slab->free); 112 slab->count--; 113 if (slab->count == 0) { 114 // move the partial slab to the full list 115 fPartialSlabs.Remove(slab); 116 fFullSlabs.Add(slab); 117 } 118 119 return link; 120} 121 122 123bool 124BaseCache::ReturnObject(const ObjectInfo &object) 125{ 126 Slab *slab = object.first; 127 ObjectLink *link = object.second; 128 129 // We return true if the slab is completely unused. 130 131 SListPush(slab->free, link); 132 slab->count++; 133 if (slab->count == slab->size) { 134 fPartialSlabs.Remove(slab); 135 return true; 136 } else if (slab->count == 1) { 137 fFullSlabs.Remove(slab); 138 fPartialSlabs.Add(slab); 139 } 140 141 return false; 142} 143 144 145BaseCache::Slab * 146BaseCache::ConstructSlab(Slab *slab, void *pages, size_t byteCount, 147 ObjectLink *(*getLink)(void *parent, void *object), void *parent) 148{ 149 printf("BaseCache::ConstructSlab(%p, %p, %lu, %p, %p)\n", slab, pages, 150 byteCount, getLink, parent); 151 152 slab->pages = pages; 153 slab->count = slab->size = byteCount / fObjectSize; 154 slab->free = NULL; 155 156 size_t spareBytes = byteCount - (slab->size * fObjectSize); 157 size_t cycle = fCacheColorCycle; 158 159 if (cycle > spareBytes) 160 cycle = 0; 161 else 162 fCacheColorCycle += kCacheColorPeriod; 163 164 printf(" %lu objects, %lu spare bytes, cycle %lu\n", 165 slab->size, spareBytes, cycle); 166 167 uint8_t *data = ((uint8_t *)pages) + cycle; 168 169 for (size_t i = 0; i < slab->size; i++) { 170 if (fConstructor) 171 fConstructor(fCookie, data); 172 SListPush(slab->free, getLink(parent, data)); 173 data += fObjectSize; 174 } 175 176 return slab; 177} 178 179 180void 181BaseCache::DestructSlab(Slab *slab) 182{ 183 if (fDestructor == NULL) 184 return; 185 186 uint8_t *data = (uint8_t *)slab->pages; 187 188 for (size_t i = 0; i < slab->size; i++) { 189 fDestructor(fCookie, data); 190 data += fObjectSize; 191 } 192} 193 194 195static inline bool 196_IsMagazineEmpty(BaseDepot::Magazine *magazine) 197{ 198 return magazine->current_round == 0; 199} 200 201 202static inline bool 203_IsMagazineFull(BaseDepot::Magazine *magazine) 204{ 205 return magazine->current_round == magazine->round_count; 206} 207 208 209static inline void * 210_PopMagazine(BaseDepot::Magazine *magazine) 211{ 212 return magazine->rounds[--magazine->current_round]; 213} 214 215 216static inline bool 217_PushMagazine(BaseDepot::Magazine *magazine, void *object) 218{ 219 if (_IsMagazineFull(magazine)) 220 return false; 221 magazine->rounds[magazine->current_round++] = object; 222 return true; 223} 224 225 226BaseDepot::BaseDepot() 227 : fFull(NULL), fEmpty(NULL), fFullCount(0), fEmptyCount(0) 228{ 229 // benaphore_init(...) 230 fStores = new (std::nothrow) CPUStore[smp_get_num_cpus()]; 231 232 if (fStores) { 233 for (int i = 0; i < smp_get_num_cpus(); i++) { 234 // benaphore_init(...) 235 fStores[i].loaded = fStores[i].previous = NULL; 236 } 237 } 238} 239 240 241BaseDepot::~BaseDepot() 242{ 243 // MakeEmpty may not be used here as ReturnObject is 244 // no longer available by then. 245 246 delete [] fStores; 247 248 // benaphore_destroy() 249} 250 251 252status_t 253BaseDepot::InitCheck() const 254{ 255 return fStores ? B_OK : B_NO_MEMORY; 256} 257 258 259void * 260BaseDepot::ObtainFromStore(CPUStore *store) 261{ 262 BenaphoreLocker _(store->lock); 263 264 // To better understand both the Alloc() and Free() logic refer to 265 // Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings] 266 267 // In a nutshell, we try to get an object from the loaded magazine 268 // if it's not empty, or from the previous magazine if it's full 269 // and finally from the Slab if the magazine depot has no full magazines. 270 271 if (store->loaded == NULL) 272 return NULL; 273 274 while (true) { 275 if (!_IsMagazineEmpty(store->loaded)) 276 return _PopMagazine(store->loaded); 277 278 if (store->previous && (_IsMagazineFull(store->previous) 279 || _ExchangeWithFull(store->previous))) 280 std::swap(store->previous, store->loaded); 281 else 282 return NULL; 283 } 284} 285 286 287bool 288BaseDepot::ReturnToStore(CPUStore *store, void *object) 289{ 290 BenaphoreLocker _(store->lock); 291 292 // We try to add the object to the loaded magazine if we have one 293 // and it's not full, or to the previous one if it is empty. If 294 // the magazine depot doesn't provide us with a new empty magazine 295 // we return the object directly to the slab. 296 297 while (true) { 298 if (store->loaded && _PushMagazine(store->loaded, object)) 299 return true; 300 301 if ((store->previous && _IsMagazineEmpty(store->previous)) 302 || _ExchangeWithEmpty(store->previous)) 303 std::swap(store->loaded, store->previous); 304 else 305 return false; 306 } 307} 308 309 310void 311BaseDepot::MakeEmpty() 312{ 313 for (int i = 0; i < smp_get_num_cpus(); i++) { 314 if (fStores[i].loaded) 315 _EmptyMagazine(fStores[i].loaded); 316 if (fStores[i].previous) 317 _EmptyMagazine(fStores[i].previous); 318 fStores[i].loaded = fStores[i].previous = NULL; 319 } 320 321 while (fFull) 322 _EmptyMagazine(SListPop(fFull)); 323 324 while (fEmpty) 325 _EmptyMagazine(SListPop(fEmpty)); 326} 327 328 329bool 330BaseDepot::_ExchangeWithFull(Magazine* &magazine) 331{ 332 BenaphoreLocker _(fLock); 333 334 if (fFull == NULL) 335 return false; 336 337 fFullCount--; 338 fEmptyCount++; 339 340 SListPush(fEmpty, magazine); 341 magazine = SListPop(fFull); 342 return true; 343} 344 345 346bool 347BaseDepot::_ExchangeWithEmpty(Magazine* &magazine) 348{ 349 BenaphoreLocker _(fLock); 350 351 if (fEmpty == NULL) { 352 fEmpty = _AllocMagazine(); 353 if (fEmpty == NULL) 354 return false; 355 } else { 356 fEmptyCount--; 357 } 358 359 if (magazine) { 360 SListPush(fFull, magazine); 361 fFullCount++; 362 } 363 364 magazine = SListPop(fEmpty); 365 return true; 366} 367 368 369void 370BaseDepot::_EmptyMagazine(Magazine *magazine) 371{ 372 for (uint16_t i = 0; i < magazine->current_round; i++) 373 ReturnObject(magazine->rounds[i]); 374 _FreeMagazine(magazine); 375} 376 377 378BaseDepot::Magazine * 379BaseDepot::_AllocMagazine() 380{ 381 Magazine *magazine = (Magazine *)malloc(sizeof(Magazine) 382 + kMagazineCapacity * sizeof(void *)); 383 if (magazine) { 384 magazine->next = NULL; 385 magazine->current_round = 0; 386 magazine->round_count = kMagazineCapacity; 387 } 388 389 return magazine; 390} 391 392 393void 394BaseDepot::_FreeMagazine(Magazine *magazine) 395{ 396 free(magazine); 397} 398 399 400 401typedef MergedLinkCacheStrategy<MallocBackend> MallocMergedCacheStrategy; 402typedef Cache<MallocMergedCacheStrategy> MallocMergedCache; 403typedef LocalCache<MallocMergedCache> MallocLocalCache; 404 405typedef HashCacheStrategy<MallocBackend> MallocHashCacheStrategy; 406typedef Cache<MallocHashCacheStrategy> MallocHashCache; 407 408object_cache_t 409object_cache_create(const char *name, size_t object_size, size_t alignment, 410 void (*_constructor)(void *, void *), void (*_destructor)(void *, void *), 411 void *cookie) 412{ 413 return new (std::nothrow) MallocLocalCache(name, object_size, alignment, 414 _constructor, _destructor, cookie); 415} 416 417 418void * 419object_cache_alloc(object_cache_t cache) 420{ 421 return ((MallocLocalCache *)cache)->Alloc(0); 422} 423 424 425void * 426object_cache_alloc_etc(object_cache_t cache, uint32_t flags) 427{ 428 return ((MallocLocalCache *)cache)->Alloc(flags); 429} 430 431 432void 433object_cache_free(object_cache_t cache, void *object) 434{ 435 ((MallocLocalCache *)cache)->Free(object); 436} 437 438 439void 440object_cache_destroy(object_cache_t cache) 441{ 442 delete (MallocLocalCache *)cache; 443} 444 445 446void test1() 447{ 448 MallocLocalCache cache("foobar", sizeof(int), 0, NULL, NULL, NULL); 449 450 static const int N = 4096; 451 void *buf[N]; 452 453 for (int i = 0; i < N; i++) 454 buf[i] = cache.Alloc(0); 455 456 for (int i = 0; i < N; i++) 457 cache.Free(buf[i]); 458 459 cache.Destroy(); 460} 461 462void test2() 463{ 464 TypedCache<int, MallocBackend> cache("int cache", 0); 465 466 static const int N = 4096; 467 int *buf[N]; 468 469 for (int i = 0; i < N; i++) 470 buf[i] = cache.Alloc(0); 471 472 for (int i = 0; i < N; i++) 473 cache.Free(buf[i]); 474} 475 476void test3() 477{ 478 Cache<HashCacheStrategy<AreaBackend> > cache("512byte hash cache", 512, 0, NULL, 479 NULL, NULL); 480 481 static const int N = 128; 482 void *buf[N]; 483 484 for (int i = 0; i < N; i++) 485 buf[i] = cache.AllocateObject(0); 486 487 for (int i = 0; i < N; i++) 488 cache.ReturnObject(buf[i]); 489} 490 491void test4() 492{ 493 LocalCache<MallocHashCache> cache("foobar", 512, 0, NULL, NULL, NULL); 494 495 static const int N = 128; 496 void *buf[N]; 497 498 for (int i = 0; i < N; i++) 499 buf[i] = cache.Alloc(0); 500 501 for (int i = 0; i < N; i++) 502 cache.Free(buf[i]); 503 504 cache.Destroy(); 505} 506 507void test5() 508{ 509 object_cache_t cache = object_cache_create("foobar", 16, 0, 510 NULL, NULL, NULL); 511 512 static const int N = 1024; 513 void *buf[N]; 514 515 for (int i = 0; i < N; i++) 516 buf[i] = object_cache_alloc(cache); 517 518 for (int i = 0; i < N; i++) 519 object_cache_free(cache, buf[i]); 520 521 object_cache_destroy(cache); 522} 523 524 525int main() 526{ 527 //test1(); 528 //test2(); 529 test3(); 530 //test4(); 531 //test5(); 532 return 0; 533} 534