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 template<typename Backend> 316 struct HashCacheStrategy : BaseCacheStrategy<Backend> { 317 typedef typename BaseCacheStrategy<Backend>::Slab Slab; 318 typedef HashCacheStrategy<Backend> Strategy; 319 typedef BaseCache::ObjectLink ObjectLink; 320 typedef BaseCache::ObjectInfo ObjectInfo; 321 322 struct Link : ObjectLink { 323 Slab *slab; 324 void *buffer; 325 }; 326 327 struct HashTableDefinition { 328 typedef Strategy * ParentType; 329 typedef void * KeyType; 330 typedef Link ValueType; 331 332 static size_t HashKey(Strategy *parent, void *key) 333 { 334 return (((uint8_t *)key) - ((uint8_t *)0)) >> parent->fLowerBoundary; 335 } 336 337 static size_t Hash(Strategy *parent, Link *value) 338 { 339 return HashKey(parent, value->buffer); 340 } 341 342 static bool Compare(Strategy *parent, void *key, Link *value) 343 { 344 return value->buffer == key; 345 } 346 }; 347 348 // for g++ 2.95 349 friend class HashTableDefinition; 350 351 typedef OpenHashTable<HashTableDefinition> HashTable; 352 353 HashCacheStrategy(BaseCache *parent) 354 : BaseCacheStrategy<Backend>(parent), fHashTable(this), 355 fSlabCache("slab cache", 0), fLinkCache("link cache", 0), 356 fLowerBoundary(Fls(parent->ObjectSize()) - 1) {} 357 358 static size_t RequiredSpace(size_t objectSize) 359 { 360 return objectSize; 361 } 362 363 void *Object(ObjectLink *link) const 364 { 365 return ((Link *)link)->buffer; 366 } 367 368 ObjectInfo ObjectInformation(void *object) const 369 { 370 Link *link = _Linkage(object); 371 return ObjectInfo(link->slab, link); 372 } 373 374 BaseCache::Slab *NewSlab(uint32_t flags) 375 { 376 size_t byteCount = _SlabSize(); 377 378 Slab *slab = fSlabCache.Alloc(flags); 379 if (slab == NULL) 380 return NULL; 381 382 void *pages; 383 if (Backend::AllocatePages(fParent, &slab->id, &pages, byteCount, 384 flags) < B_OK) { 385 fSlabCache.Free(slab); 386 return NULL; 387 } 388 389 uint8_t *data = (uint8_t *)pages; 390 for (uint8_t *it = data; 391 it < (data + byteCount); it += fParent->ObjectSize()) { 392 Link *link = fLinkCache.Alloc(flags); 393 link->slab = slab; 394 link->buffer = it; 395 fHashTable.Insert(link); 396 } 397 398 return BaseCacheStrategy<Backend>::_ConstructSlab(slab, pages, 0, 399 _Linkage, this); 400 } 401 402 void ReturnSlab(BaseCache::Slab *slab) 403 { 404 uint8_t *data = (uint8_t *)slab->pages; 405 size_t byteCount = _SlabSize(); 406 407 for (uint8_t *it = data; 408 it < (data + byteCount); it += fParent->ObjectSize()) { 409 Link *link = fHashTable.Lookup(it); 410 fHashTable.Remove(link); 411 fLinkCache.Free(link); 412 } 413 414 BaseCacheStrategy<Backend>::_DestructSlab(slab); 415 fSlabCache.Free((Slab *)slab); 416 } 417 418 private: 419 size_t _SlabSize() const 420 { 421 return BaseCacheStrategy<Backend>::SlabSize(0); 422 } 423 424 Link *_Linkage(void *object) const 425 { 426 return fHashTable.Lookup(object); 427 } 428 429 static ObjectLink *_Linkage(void *_this, void *object) 430 { 431 return ((Strategy *)_this)->_Linkage(object); 432 } 433 434 HashTable fHashTable; 435 TypedCache<Slab, Backend> fSlabCache; 436 TypedCache<Link, Backend> fLinkCache; 437 const size_t fLowerBoundary; 438 }; 439 440 441 class BaseDepot { 442 public: 443 struct Magazine { 444 Magazine *next; 445 uint16_t current_round, round_count; 446 void *rounds[0]; 447 }; 448 449 struct CPUStore { 450 benaphore lock; 451 Magazine *loaded, *previous; 452 }; 453 454 protected: 455 BaseDepot(); 456 virtual ~BaseDepot(); 457 458 status_t InitCheck() const; 459 460 CPUStore *CPU() const { return &fStores[smp_get_current_cpu()]; } 461 462 void *ObtainFromStore(CPUStore *store); 463 bool ReturnToStore(CPUStore *store, void *object); 464 void MakeEmpty(); 465 466 virtual void ReturnObject(void *object) = 0; 467 468 bool _ExchangeWithFull(Magazine* &magazine); 469 bool _ExchangeWithEmpty(Magazine* &magazine); 470 void _EmptyMagazine(Magazine *magazine); 471 472 Magazine *_AllocMagazine(); 473 void _FreeMagazine(Magazine *magazine); 474 475 benaphore fLock; 476 Magazine *fFull, *fEmpty; 477 size_t fFullCount, fEmptyCount; 478 CPUStore *fStores; 479 }; 480 481 482 template<typename CacheType> 483 class LocalCache : public CacheType, protected BaseDepot { 484 public: 485 typedef typename CacheType::Constructor Constructor; 486 typedef typename CacheType::Destructor Destructor; 487 488 LocalCache(const char *name, size_t objectSize, size_t alignment, 489 Constructor _constructor, Destructor _destructor, void *_cookie) 490 : CacheType(name, objectSize, alignment, _constructor, _destructor, 491 _cookie) {} 492 493 ~LocalCache() { Destroy(); } 494 495 void *Alloc(uint32_t flags) 496 { 497 void *object = BaseDepot::ObtainFromStore(CPU()); 498 if (object == NULL) 499 object = CacheType::AllocateObject(flags); 500 return object; 501 } 502 503 void Free(void *object) 504 { 505 if (!BaseDepot::ReturnToStore(CPU(), object)) 506 CacheType::ReturnObject(object); 507 } 508 509 void Destroy() { BaseDepot::MakeEmpty(); } 510 511 private: 512 void ReturnObject(void *object) 513 { 514 CacheType::ReturnObject(object); 515 } 516 }; 517 518 #endif 519