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 #ifndef _SLAB_H_ 10 #define _SLAB_H_ 11 12 #include <stdint.h> 13 #include <stdlib.h> 14 15 #include <algorithm> // for swap() 16 #include <new> 17 #include <utility> // for pair<> 18 19 #include <util/AutoLock.h> 20 #include <util/DoublyLinkedList.h> 21 #include <util/OpenHashTable.h> 22 23 #include <OS.h> 24 25 26 #define smp_get_current_cpu() 0 27 #define smp_get_num_cpus() 1 28 29 30 // C interface 31 extern "C" { 32 typedef void *object_cache_t; 33 object_cache_t 34 object_cache_create(const char *name, size_t object_size, size_t alignment, 35 void (*_constructor)(void *, void *), void (*_destructor)(void *, void *), 36 void *cookie); 37 void *object_cache_alloc(object_cache_t cache); 38 void *object_cache_alloc_etc(object_cache_t cache, uint32_t flags); 39 void object_cache_free(object_cache_t cache, void *object); 40 void object_cache_destroy(object_cache_t cache); 41 } 42 43 44 // TODO this values should be dynamically tuned per cache. 45 static const int kMinimumSlabItems = 32; 46 47 // base Slab implementation, opaque to the backend used. 48 class BaseCache { 49 public: 50 typedef void (*Constructor)(void *cookie, void *object); 51 typedef void (*Destructor)(void *cookie, void *object); 52 53 BaseCache(const char *_name, size_t objectSize, size_t alignment, 54 Constructor _constructor, Destructor _destructor, void *_cookie); 55 56 struct ObjectLink { 57 struct ObjectLink *next; 58 }; 59 60 struct Slab : DoublyLinkedListLinkImpl<Slab> { 61 void *pages; 62 size_t count, size; 63 ObjectLink *free; 64 }; 65 66 typedef std::pair<Slab *, ObjectLink *> ObjectInfo; 67 68 ObjectLink *AllocateObject(); 69 bool ReturnObject(const ObjectInfo &object); 70 71 Slab *ConstructSlab(Slab *slab, void *pages, size_t byteCount, 72 ObjectLink *(*getLink)(void *parent, void *object), void *parent); 73 void DestructSlab(Slab *slab); 74 75 const char *Name() const { return fName; } 76 size_t ObjectSize() const { return fObjectSize; } 77 78 protected: 79 typedef DoublyLinkedList<Slab> SlabList; 80 81 char fName[32]; 82 size_t fObjectSize, fCacheColorCycle; 83 SlabList fPartialSlabs, fFullSlabs; 84 85 Constructor fConstructor; 86 Destructor fDestructor; 87 void *fCookie; 88 }; 89 90 91 enum { 92 CACHE_ALIGN_TO_PAGE_TOTAL = 1 << 0, 93 }; 94 95 struct MallocBackend { 96 typedef void *AllocationID; 97 98 static int PageSize() { return 4096; } 99 static status_t AllocatePages(BaseCache *cache, AllocationID *id, 100 void **pages, size_t byteCount, uint32_t flags); 101 static void FreePages(BaseCache *cache, void *pages); 102 }; 103 104 105 struct AreaBackend { 106 typedef area_id AllocationID; 107 108 static int PageSize() { return B_PAGE_SIZE; } 109 static status_t AllocatePages(BaseCache *cache, area_id *id, void **pages, 110 size_t byteCount, uint32_t flags); 111 static void FreePages(BaseCache *cache, area_id id); 112 }; 113 114 115 // Slab implementation, glues together the frontend, backend as 116 // well as the Slab strategy used. 117 template<typename Strategy> 118 class Cache : protected BaseCache { 119 public: 120 Cache(const char *_name, size_t objectSize, size_t alignment, 121 Constructor _constructor, Destructor _destructor, void *_cookie) 122 : BaseCache(_name, Strategy::RequiredSpace(objectSize), alignment, 123 _constructor, _destructor, _cookie), fStrategy(this) {} 124 125 void *AllocateObject(uint32_t flags) 126 { 127 if (fPartialSlabs.IsEmpty()) { 128 Slab *newSlab = fStrategy.NewSlab(flags); 129 if (newSlab == NULL) 130 return NULL; 131 fPartialSlabs.Add(newSlab); 132 } 133 134 return fStrategy.Object(BaseCache::AllocateObject()); 135 } 136 137 void ReturnObject(void *object) 138 { 139 ObjectInfo location = fStrategy.ObjectInformation(object); 140 141 if (BaseCache::ReturnObject(location)) 142 fStrategy.ReturnSlab(location.first); 143 } 144 145 private: 146 Strategy fStrategy; 147 }; 148 149 150 static inline const void * 151 LowerBoundary(void *object, size_t byteCount) 152 { 153 const uint8_t *null = (uint8_t *)NULL; 154 return null + ((((uint8_t *)object) - null) & ~(byteCount - 1)); 155 } 156 157 158 template<typename Backend> 159 class BaseCacheStrategy { 160 protected: 161 typedef BaseCache::ObjectLink ObjectLink; 162 163 BaseCacheStrategy(BaseCache *parent) 164 : fParent(parent) {} 165 166 size_t SlabSize(size_t tailSpace) const 167 { 168 size_t pageCount = (kMinimumSlabItems * fParent->ObjectSize() 169 + tailSpace) / Backend::PageSize(); 170 if (pageCount < 1) 171 pageCount = 1; 172 return pageCount * Backend::PageSize(); 173 } 174 175 struct Slab : BaseCache::Slab { 176 typename Backend::AllocationID id; 177 }; 178 179 BaseCache::Slab *_ConstructSlab(Slab *slab, void *pages, size_t tailSpace, 180 ObjectLink *(*getLink)(void *parent, void *object), void *parent) 181 { 182 return fParent->ConstructSlab(slab, pages, SlabSize(tailSpace) 183 - tailSpace, getLink, parent); 184 } 185 186 void _DestructSlab(BaseCache::Slab *slab) 187 { 188 fParent->DestructSlab(slab); 189 Backend::FreePages(fParent, ((Slab *)slab)->id); 190 } 191 192 BaseCache *fParent; 193 }; 194 195 196 // This slab strategy includes the ObjectLink at the end of each object and the 197 // slab at the end of the allocated pages. It uses aligned allocations to 198 // provide object to slab mapping with zero storage, thus there is only one 199 // word of overhead per object. This is optimized for small objects. 200 template<typename Backend> 201 class MergedLinkCacheStrategy : public BaseCacheStrategy<Backend> { 202 public: 203 typedef typename BaseCacheStrategy<Backend>::Slab Slab; 204 typedef BaseCache::ObjectLink Link; 205 typedef BaseCache::ObjectInfo ObjectInfo; 206 207 MergedLinkCacheStrategy(BaseCache *parent) 208 : BaseCacheStrategy<Backend>(parent) {} 209 210 static size_t RequiredSpace(size_t objectSize) 211 { 212 return objectSize + sizeof(Link); 213 } 214 215 void *Object(Link *link) const 216 { 217 return ((uint8_t *)link) - (fParent->ObjectSize() - sizeof(Link)); 218 } 219 220 ObjectInfo ObjectInformation(void *object) const 221 { 222 Slab *slab = _SlabInPages(LowerBoundary(object, _SlabSize())); 223 return ObjectInfo(slab, _Linkage(object)); 224 } 225 226 BaseCache::Slab *NewSlab(uint32_t flags) 227 { 228 typename Backend::AllocationID id; 229 void *pages; 230 231 // in order to save a pointer per object or a hash table to 232 // map objects to slabs we required this set of pages to be 233 // aligned in a (pageCount * PAGE_SIZE) boundary. 234 if (Backend::AllocatePages(fParent, &id, &pages, _SlabSize(), 235 CACHE_ALIGN_TO_PAGE_TOTAL | flags) < B_OK) 236 return NULL; 237 238 _SlabInPages(pages)->id = id; 239 240 return BaseCacheStrategy<Backend>::_ConstructSlab(_SlabInPages(pages), 241 pages, sizeof(Slab), _Linkage, this); 242 } 243 244 void ReturnSlab(BaseCache::Slab *slab) 245 { 246 BaseCacheStrategy<Backend>::_DestructSlab(slab); 247 } 248 249 private: 250 size_t _SlabSize() const 251 { 252 return BaseCacheStrategy<Backend>::SlabSize(sizeof(Slab)); 253 } 254 255 Link *_Linkage(void *object) const 256 { 257 return (Link *)(((uint8_t *)object) 258 + (fParent->ObjectSize() - sizeof(Link))); 259 } 260 261 Slab *_SlabInPages(const void *pages) const 262 { 263 return (Slab *)(((uint8_t *)pages) + _SlabSize() - sizeof(Slab)); 264 } 265 266 static Link *_Linkage(void *_this, void *object) 267 { 268 return ((MergedLinkCacheStrategy *)_this)->_Linkage(object); 269 } 270 }; 271 272 273 template<typename Type, typename Backend> 274 class TypedCache : public Cache<MergedLinkCacheStrategy<Backend> > { 275 public: 276 typedef MergedLinkCacheStrategy<Backend> Strategy; 277 typedef Cache<Strategy> BaseType; 278 279 TypedCache(const char *name, size_t alignment) 280 : BaseType(name, sizeof(Type), alignment, _ConstructObject, 281 _DestructObject, this) {} 282 virtual ~TypedCache() {} 283 284 Type *Alloc(uint32_t flags) { return (Type *)BaseType::AllocateObject(flags); } 285 void Free(Type *object) { BaseType::ReturnObject(object); } 286 287 private: 288 static void _ConstructObject(void *cookie, void *object) 289 { 290 ((TypedCache *)cookie)->ConstructObject((Type *)object); 291 } 292 293 static void _DestructObject(void *cookie, void *object) 294 { 295 ((TypedCache *)cookie)->DestructObject((Type *)object); 296 } 297 298 virtual void ConstructObject(Type *object) {} 299 virtual void DestructObject(Type *object) {} 300 }; 301 302 303 static inline int 304 Fls(size_t value) 305 { 306 for (int i = 31; i >= 0; i--) { 307 if ((value >> i) & 1) 308 return i + 1; 309 } 310 311 return -1; 312 } 313 314 315 struct BaseHashCacheStrategy { 316 typedef BaseCache::ObjectLink ObjectLink; 317 typedef BaseCache::ObjectInfo ObjectInfo; 318 319 struct Link : ObjectLink, HashTableLink<Link> { 320 BaseCache::Slab *slab; 321 void *buffer; 322 }; 323 324 struct HashTableDefinition { 325 typedef BaseHashCacheStrategy ParentType; 326 typedef void * KeyType; 327 typedef Link ValueType; 328 329 HashTableDefinition(BaseHashCacheStrategy *_parent) : parent(_parent) {} 330 331 size_t HashKey(void *key) const 332 { 333 return (((uint8_t *)key) - ((uint8_t *)0)) >> parent->fLowerBoundary; 334 } 335 336 size_t Hash(Link *value) const { return HashKey(value->buffer); } 337 338 bool Compare(void *key, Link *value) const 339 { 340 return value->buffer == key; 341 } 342 343 HashTableLink<Link> *GetLink(Link *value) const { return value; } 344 345 BaseHashCacheStrategy *parent; 346 }; 347 348 // for g++ 2.95 349 friend class HashTableDefinition; 350 351 typedef OpenHashTable<HashTableDefinition> HashTable; 352 353 BaseHashCacheStrategy(BaseCache *parent) 354 : fHashTable(this), fLowerBoundary(Fls(parent->ObjectSize()) - 1) {} 355 356 void *Object(ObjectLink *link) const 357 { 358 return ((Link *)link)->buffer; 359 } 360 361 ObjectInfo ObjectInformation(void *object) const 362 { 363 Link *link = _Linkage(object); 364 return ObjectInfo(link->slab, link); 365 } 366 367 protected: 368 Link *_Linkage(void *object) const 369 { 370 return fHashTable.Lookup(object); 371 } 372 373 static ObjectLink *_Linkage(void *_this, void *object) 374 { 375 return ((BaseHashCacheStrategy *)_this)->_Linkage(object); 376 } 377 378 HashTable fHashTable; 379 const size_t fLowerBoundary; 380 }; 381 382 383 template<typename Backend> 384 struct HashCacheStrategy : BaseCacheStrategy<Backend>, BaseHashCacheStrategy { 385 typedef typename BaseCacheStrategy<Backend>::Slab Slab; 386 typedef HashCacheStrategy<Backend> Strategy; 387 388 HashCacheStrategy(BaseCache *parent) 389 : BaseCacheStrategy<Backend>(parent), BaseHashCacheStrategy(parent), 390 fSlabCache("slab cache", 0), fLinkCache("link cache", 0) {} 391 392 static size_t RequiredSpace(size_t objectSize) 393 { 394 return objectSize; 395 } 396 397 BaseCache::Slab *NewSlab(uint32_t flags) 398 { 399 size_t byteCount = _SlabSize(); 400 401 Slab *slab = fSlabCache.Alloc(flags); 402 if (slab == NULL) 403 return NULL; 404 405 void *pages; 406 if (Backend::AllocatePages(fParent, &slab->id, &pages, byteCount, 407 flags) < B_OK) { 408 fSlabCache.Free(slab); 409 return NULL; 410 } 411 412 if (_PrepareSlab(fParent, slab, pages, byteCount, flags) < B_OK) { 413 Backend::FreePages(fParent, slab->id); 414 fSlabCache.Free(slab); 415 return NULL; 416 } 417 418 // it's very important that we cast this to BaseHashCacheStrategy 419 // so we get the proper instance offset through void * 420 return BaseCacheStrategy<Backend>::_ConstructSlab(slab, pages, 0, 421 _Linkage, (BaseHashCacheStrategy *)this); 422 } 423 424 void ReturnSlab(BaseCache::Slab *slab) 425 { 426 _ClearSlab(fParent, slab->pages, _SlabSize()); 427 BaseCacheStrategy<Backend>::_DestructSlab(slab); 428 fSlabCache.Free((Slab *)slab); 429 } 430 431 private: 432 size_t _SlabSize() const 433 { 434 return BaseCacheStrategy<Backend>::SlabSize(0); 435 } 436 437 status_t _PrepareSlab(BaseCache *parent, Slab *slab, void *pages, 438 size_t byteCount, uint32_t flags) 439 { 440 uint8_t *data = (uint8_t *)pages; 441 for (uint8_t *it = data; 442 it < (data + byteCount); it += parent->ObjectSize()) { 443 Link *link = fLinkCache.Alloc(flags); 444 445 if (link == NULL) { 446 _ClearSlabRange(parent, data, it); 447 return B_NO_MEMORY; 448 } 449 450 link->slab = slab; 451 link->buffer = it; 452 fHashTable.Insert(link); 453 } 454 455 return B_OK; 456 } 457 458 void _ClearSlab(BaseCache *parent, void *pages, size_t byteCount) 459 { 460 _ClearSlabRange(parent, (uint8_t *)pages, 461 ((uint8_t *)pages) + byteCount); 462 } 463 464 void _ClearSlabRange(BaseCache *parent, uint8_t *data, uint8_t *end) 465 { 466 for (uint8_t *it = data; it < end; it += parent->ObjectSize()) { 467 Link *link = fHashTable.Lookup(it); 468 fHashTable.Remove(link); 469 fLinkCache.Free(link); 470 } 471 } 472 473 TypedCache<Slab, Backend> fSlabCache; 474 TypedCache<Link, Backend> fLinkCache; 475 }; 476 477 478 class BaseDepot { 479 public: 480 struct Magazine { 481 Magazine *next; 482 uint16_t current_round, round_count; 483 void *rounds[0]; 484 }; 485 486 struct CPUStore { 487 benaphore lock; 488 Magazine *loaded, *previous; 489 }; 490 491 protected: 492 BaseDepot(); 493 virtual ~BaseDepot(); 494 495 status_t InitCheck() const; 496 497 CPUStore *CPU() const { return &fStores[smp_get_current_cpu()]; } 498 499 void *ObtainFromStore(CPUStore *store); 500 bool ReturnToStore(CPUStore *store, void *object); 501 void MakeEmpty(); 502 503 virtual void ReturnObject(void *object) = 0; 504 505 bool _ExchangeWithFull(Magazine* &magazine); 506 bool _ExchangeWithEmpty(Magazine* &magazine); 507 void _EmptyMagazine(Magazine *magazine); 508 509 Magazine *_AllocMagazine(); 510 void _FreeMagazine(Magazine *magazine); 511 512 benaphore fLock; 513 Magazine *fFull, *fEmpty; 514 size_t fFullCount, fEmptyCount; 515 CPUStore *fStores; 516 }; 517 518 519 template<typename CacheType> 520 class LocalCache : public CacheType, protected BaseDepot { 521 public: 522 typedef typename CacheType::Constructor Constructor; 523 typedef typename CacheType::Destructor Destructor; 524 525 LocalCache(const char *name, size_t objectSize, size_t alignment, 526 Constructor _constructor, Destructor _destructor, void *_cookie) 527 : CacheType(name, objectSize, alignment, _constructor, _destructor, 528 _cookie) {} 529 530 ~LocalCache() { Destroy(); } 531 532 void *Alloc(uint32_t flags) 533 { 534 void *object = BaseDepot::ObtainFromStore(CPU()); 535 if (object == NULL) 536 object = CacheType::AllocateObject(flags); 537 return object; 538 } 539 540 void Free(void *object) 541 { 542 if (!BaseDepot::ReturnToStore(CPU(), object)) 543 CacheType::ReturnObject(object); 544 } 545 546 void Destroy() { BaseDepot::MakeEmpty(); } 547 548 private: 549 void ReturnObject(void *object) 550 { 551 CacheType::ReturnObject(object); 552 } 553 }; 554 555 #endif 556