1a8806e5eSIngo Weinhold /* 2a8806e5eSIngo Weinhold * Copyright 2008, Axel Dörfler. All Rights Reserved. 3a8806e5eSIngo Weinhold * Copyright 2007, Hugo Santos. All Rights Reserved. 4a8806e5eSIngo Weinhold * 5a8806e5eSIngo Weinhold * Distributed under the terms of the MIT License. 6a8806e5eSIngo Weinhold */ 7a8806e5eSIngo Weinhold 8a8806e5eSIngo Weinhold 9a8806e5eSIngo Weinhold #include <slab/ObjectDepot.h> 10a8806e5eSIngo Weinhold 11a8806e5eSIngo Weinhold #include <algorithm> 12a8806e5eSIngo Weinhold 13a8806e5eSIngo Weinhold #include <util/AutoLock.h> 14a8806e5eSIngo Weinhold 15a8806e5eSIngo Weinhold #include "slab_private.h" 16a8806e5eSIngo Weinhold 17a8806e5eSIngo Weinhold 18a8806e5eSIngo Weinhold static const int kMagazineCapacity = 32; 19a8806e5eSIngo Weinhold // TODO: Should be dynamically tuned per cache. 20a8806e5eSIngo Weinhold 21a8806e5eSIngo Weinhold 22*825566f8SIngo Weinhold struct DepotMagazine { 23*825566f8SIngo Weinhold DepotMagazine* next; 24*825566f8SIngo Weinhold uint16 current_round; 25*825566f8SIngo Weinhold uint16 round_count; 26a8806e5eSIngo Weinhold void* rounds[0]; 27*825566f8SIngo Weinhold 28*825566f8SIngo Weinhold public: 29*825566f8SIngo Weinhold inline bool IsEmpty() const; 30*825566f8SIngo Weinhold inline bool IsFull() const; 31*825566f8SIngo Weinhold 32*825566f8SIngo Weinhold inline void* Pop(); 33*825566f8SIngo Weinhold inline bool Push(void* object); 34a8806e5eSIngo Weinhold }; 35a8806e5eSIngo Weinhold 36a8806e5eSIngo Weinhold 37a8806e5eSIngo Weinhold struct depot_cpu_store { 38a8806e5eSIngo Weinhold recursive_lock lock; 39*825566f8SIngo Weinhold DepotMagazine* loaded; 40*825566f8SIngo Weinhold DepotMagazine* previous; 41a8806e5eSIngo Weinhold }; 42a8806e5eSIngo Weinhold 43a8806e5eSIngo Weinhold 44*825566f8SIngo Weinhold bool 45*825566f8SIngo Weinhold DepotMagazine::IsEmpty() const 46a8806e5eSIngo Weinhold { 47*825566f8SIngo Weinhold return current_round == 0; 48a8806e5eSIngo Weinhold } 49a8806e5eSIngo Weinhold 50a8806e5eSIngo Weinhold 51*825566f8SIngo Weinhold bool 52*825566f8SIngo Weinhold DepotMagazine::IsFull() const 53a8806e5eSIngo Weinhold { 54*825566f8SIngo Weinhold return current_round == round_count; 55a8806e5eSIngo Weinhold } 56a8806e5eSIngo Weinhold 57a8806e5eSIngo Weinhold 58*825566f8SIngo Weinhold void* 59*825566f8SIngo Weinhold DepotMagazine::Pop() 60a8806e5eSIngo Weinhold { 61*825566f8SIngo Weinhold return rounds[--current_round]; 62a8806e5eSIngo Weinhold } 63a8806e5eSIngo Weinhold 64a8806e5eSIngo Weinhold 65*825566f8SIngo Weinhold bool 66*825566f8SIngo Weinhold DepotMagazine::Push(void* object) 67a8806e5eSIngo Weinhold { 68*825566f8SIngo Weinhold if (IsFull()) 69a8806e5eSIngo Weinhold return false; 70*825566f8SIngo Weinhold 71*825566f8SIngo Weinhold rounds[current_round++] = object; 72a8806e5eSIngo Weinhold return true; 73a8806e5eSIngo Weinhold } 74a8806e5eSIngo Weinhold 75a8806e5eSIngo Weinhold 76*825566f8SIngo Weinhold static DepotMagazine* 77a8806e5eSIngo Weinhold alloc_magazine() 78a8806e5eSIngo Weinhold { 79*825566f8SIngo Weinhold DepotMagazine* magazine = (DepotMagazine*)slab_internal_alloc( 80*825566f8SIngo Weinhold sizeof(DepotMagazine) + kMagazineCapacity * sizeof(void*), 0); 81a8806e5eSIngo Weinhold if (magazine) { 82a8806e5eSIngo Weinhold magazine->next = NULL; 83a8806e5eSIngo Weinhold magazine->current_round = 0; 84a8806e5eSIngo Weinhold magazine->round_count = kMagazineCapacity; 85a8806e5eSIngo Weinhold } 86a8806e5eSIngo Weinhold 87a8806e5eSIngo Weinhold return magazine; 88a8806e5eSIngo Weinhold } 89a8806e5eSIngo Weinhold 90a8806e5eSIngo Weinhold 91a8806e5eSIngo Weinhold static void 92*825566f8SIngo Weinhold free_magazine(DepotMagazine* magazine) 93a8806e5eSIngo Weinhold { 94*825566f8SIngo Weinhold slab_internal_free(magazine); 95a8806e5eSIngo Weinhold } 96a8806e5eSIngo Weinhold 97a8806e5eSIngo Weinhold 98a8806e5eSIngo Weinhold static void 99*825566f8SIngo Weinhold empty_magazine(object_depot* depot, DepotMagazine* magazine) 100a8806e5eSIngo Weinhold { 101a8806e5eSIngo Weinhold for (uint16 i = 0; i < magazine->current_round; i++) 102*825566f8SIngo Weinhold depot->return_object(depot, depot->cookie, magazine->rounds[i]); 103a8806e5eSIngo Weinhold free_magazine(magazine); 104a8806e5eSIngo Weinhold } 105a8806e5eSIngo Weinhold 106a8806e5eSIngo Weinhold 107a8806e5eSIngo Weinhold static bool 108*825566f8SIngo Weinhold exchange_with_full(object_depot* depot, DepotMagazine*& magazine) 109a8806e5eSIngo Weinhold { 110a8806e5eSIngo Weinhold RecursiveLocker _(depot->lock); 111a8806e5eSIngo Weinhold 112a8806e5eSIngo Weinhold if (depot->full == NULL) 113a8806e5eSIngo Weinhold return false; 114a8806e5eSIngo Weinhold 115a8806e5eSIngo Weinhold depot->full_count--; 116a8806e5eSIngo Weinhold depot->empty_count++; 117a8806e5eSIngo Weinhold 118a8806e5eSIngo Weinhold _push(depot->empty, magazine); 119a8806e5eSIngo Weinhold magazine = _pop(depot->full); 120a8806e5eSIngo Weinhold return true; 121a8806e5eSIngo Weinhold } 122a8806e5eSIngo Weinhold 123a8806e5eSIngo Weinhold 124a8806e5eSIngo Weinhold static bool 125*825566f8SIngo Weinhold exchange_with_empty(object_depot* depot, DepotMagazine*& magazine) 126a8806e5eSIngo Weinhold { 127a8806e5eSIngo Weinhold RecursiveLocker _(depot->lock); 128a8806e5eSIngo Weinhold 129a8806e5eSIngo Weinhold if (depot->empty == NULL) { 130a8806e5eSIngo Weinhold depot->empty = alloc_magazine(); 131a8806e5eSIngo Weinhold if (depot->empty == NULL) 132a8806e5eSIngo Weinhold return false; 133a8806e5eSIngo Weinhold } else { 134a8806e5eSIngo Weinhold depot->empty_count--; 135a8806e5eSIngo Weinhold } 136a8806e5eSIngo Weinhold 137a8806e5eSIngo Weinhold if (magazine) { 138a8806e5eSIngo Weinhold _push(depot->full, magazine); 139a8806e5eSIngo Weinhold depot->full_count++; 140a8806e5eSIngo Weinhold } 141a8806e5eSIngo Weinhold 142a8806e5eSIngo Weinhold magazine = _pop(depot->empty); 143a8806e5eSIngo Weinhold return true; 144a8806e5eSIngo Weinhold } 145a8806e5eSIngo Weinhold 146a8806e5eSIngo Weinhold 147a8806e5eSIngo Weinhold static inline depot_cpu_store* 148a8806e5eSIngo Weinhold object_depot_cpu(object_depot* depot) 149a8806e5eSIngo Weinhold { 150a8806e5eSIngo Weinhold return &depot->stores[smp_get_current_cpu()]; 151a8806e5eSIngo Weinhold } 152a8806e5eSIngo Weinhold 153a8806e5eSIngo Weinhold 154a8806e5eSIngo Weinhold // #pragma mark - 155a8806e5eSIngo Weinhold 156a8806e5eSIngo Weinhold 157a8806e5eSIngo Weinhold status_t 158*825566f8SIngo Weinhold object_depot_init(object_depot* depot, uint32 flags, void* cookie, 159*825566f8SIngo Weinhold void (*return_object)(object_depot* depot, void* cookie, void* object)) 160a8806e5eSIngo Weinhold { 161a8806e5eSIngo Weinhold depot->full = NULL; 162a8806e5eSIngo Weinhold depot->empty = NULL; 163a8806e5eSIngo Weinhold depot->full_count = depot->empty_count = 0; 164a8806e5eSIngo Weinhold 165a8806e5eSIngo Weinhold recursive_lock_init(&depot->lock, "depot"); 166a8806e5eSIngo Weinhold 167*825566f8SIngo Weinhold depot->stores = (depot_cpu_store*)slab_internal_alloc( 168*825566f8SIngo Weinhold sizeof(depot_cpu_store) * smp_get_num_cpus(), flags); 169a8806e5eSIngo Weinhold if (depot->stores == NULL) { 170a8806e5eSIngo Weinhold recursive_lock_destroy(&depot->lock); 171a8806e5eSIngo Weinhold return B_NO_MEMORY; 172a8806e5eSIngo Weinhold } 173a8806e5eSIngo Weinhold 174a8806e5eSIngo Weinhold for (int i = 0; i < smp_get_num_cpus(); i++) { 175a8806e5eSIngo Weinhold recursive_lock_init(&depot->stores[i].lock, "cpu store"); 176a8806e5eSIngo Weinhold depot->stores[i].loaded = depot->stores[i].previous = NULL; 177a8806e5eSIngo Weinhold } 178a8806e5eSIngo Weinhold 179*825566f8SIngo Weinhold depot->cookie = cookie; 180a8806e5eSIngo Weinhold depot->return_object = return_object; 181a8806e5eSIngo Weinhold 182a8806e5eSIngo Weinhold return B_OK; 183a8806e5eSIngo Weinhold } 184a8806e5eSIngo Weinhold 185a8806e5eSIngo Weinhold 186a8806e5eSIngo Weinhold void 187a8806e5eSIngo Weinhold object_depot_destroy(object_depot* depot) 188a8806e5eSIngo Weinhold { 189a8806e5eSIngo Weinhold object_depot_make_empty(depot); 190a8806e5eSIngo Weinhold 191a8806e5eSIngo Weinhold for (int i = 0; i < smp_get_num_cpus(); i++) { 192a8806e5eSIngo Weinhold recursive_lock_destroy(&depot->stores[i].lock); 193a8806e5eSIngo Weinhold } 194a8806e5eSIngo Weinhold 195*825566f8SIngo Weinhold slab_internal_free(depot->stores); 196a8806e5eSIngo Weinhold 197a8806e5eSIngo Weinhold recursive_lock_destroy(&depot->lock); 198a8806e5eSIngo Weinhold } 199a8806e5eSIngo Weinhold 200a8806e5eSIngo Weinhold 201a8806e5eSIngo Weinhold static void* 202a8806e5eSIngo Weinhold object_depot_obtain_from_store(object_depot* depot, depot_cpu_store* store) 203a8806e5eSIngo Weinhold { 204a8806e5eSIngo Weinhold RecursiveLocker _(store->lock); 205a8806e5eSIngo Weinhold 206a8806e5eSIngo Weinhold // To better understand both the Alloc() and Free() logic refer to 207a8806e5eSIngo Weinhold // Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings] 208a8806e5eSIngo Weinhold 209a8806e5eSIngo Weinhold // In a nutshell, we try to get an object from the loaded magazine 210a8806e5eSIngo Weinhold // if it's not empty, or from the previous magazine if it's full 211a8806e5eSIngo Weinhold // and finally from the Slab if the magazine depot has no full magazines. 212a8806e5eSIngo Weinhold 213a8806e5eSIngo Weinhold if (store->loaded == NULL) 214a8806e5eSIngo Weinhold return NULL; 215a8806e5eSIngo Weinhold 216a8806e5eSIngo Weinhold while (true) { 217*825566f8SIngo Weinhold if (!store->loaded->IsEmpty()) 218*825566f8SIngo Weinhold return store->loaded->Pop(); 219a8806e5eSIngo Weinhold 220*825566f8SIngo Weinhold if (store->previous 221*825566f8SIngo Weinhold && (store->previous->IsFull() 222*825566f8SIngo Weinhold || exchange_with_full(depot, store->previous))) { 223a8806e5eSIngo Weinhold std::swap(store->previous, store->loaded); 224*825566f8SIngo Weinhold } else 225a8806e5eSIngo Weinhold return NULL; 226a8806e5eSIngo Weinhold } 227a8806e5eSIngo Weinhold } 228a8806e5eSIngo Weinhold 229a8806e5eSIngo Weinhold 230a8806e5eSIngo Weinhold static int 231a8806e5eSIngo Weinhold object_depot_return_to_store(object_depot* depot, depot_cpu_store* store, 232a8806e5eSIngo Weinhold void* object) 233a8806e5eSIngo Weinhold { 234a8806e5eSIngo Weinhold RecursiveLocker _(store->lock); 235a8806e5eSIngo Weinhold 236a8806e5eSIngo Weinhold // We try to add the object to the loaded magazine if we have one 237a8806e5eSIngo Weinhold // and it's not full, or to the previous one if it is empty. If 238a8806e5eSIngo Weinhold // the magazine depot doesn't provide us with a new empty magazine 239a8806e5eSIngo Weinhold // we return the object directly to the slab. 240a8806e5eSIngo Weinhold 241a8806e5eSIngo Weinhold while (true) { 242*825566f8SIngo Weinhold if (store->loaded && store->loaded->Push(object)) 243a8806e5eSIngo Weinhold return 1; 244a8806e5eSIngo Weinhold 245*825566f8SIngo Weinhold if ((store->previous && store->previous->IsEmpty()) 246a8806e5eSIngo Weinhold || exchange_with_empty(depot, store->previous)) 247a8806e5eSIngo Weinhold std::swap(store->loaded, store->previous); 248a8806e5eSIngo Weinhold else 249a8806e5eSIngo Weinhold return 0; 250a8806e5eSIngo Weinhold } 251a8806e5eSIngo Weinhold } 252a8806e5eSIngo Weinhold 253a8806e5eSIngo Weinhold 254a8806e5eSIngo Weinhold void* 255a8806e5eSIngo Weinhold object_depot_obtain(object_depot* depot) 256a8806e5eSIngo Weinhold { 257a8806e5eSIngo Weinhold return object_depot_obtain_from_store(depot, object_depot_cpu(depot)); 258a8806e5eSIngo Weinhold } 259a8806e5eSIngo Weinhold 260a8806e5eSIngo Weinhold 261a8806e5eSIngo Weinhold int 262a8806e5eSIngo Weinhold object_depot_store(object_depot* depot, void* object) 263a8806e5eSIngo Weinhold { 264a8806e5eSIngo Weinhold return object_depot_return_to_store(depot, object_depot_cpu(depot), 265a8806e5eSIngo Weinhold object); 266a8806e5eSIngo Weinhold } 267a8806e5eSIngo Weinhold 268a8806e5eSIngo Weinhold 269a8806e5eSIngo Weinhold void 270a8806e5eSIngo Weinhold object_depot_make_empty(object_depot* depot) 271a8806e5eSIngo Weinhold { 272a8806e5eSIngo Weinhold for (int i = 0; i < smp_get_num_cpus(); i++) { 273a8806e5eSIngo Weinhold depot_cpu_store* store = &depot->stores[i]; 274a8806e5eSIngo Weinhold 275a8806e5eSIngo Weinhold RecursiveLocker _(store->lock); 276a8806e5eSIngo Weinhold 277a8806e5eSIngo Weinhold if (depot->stores[i].loaded) 278a8806e5eSIngo Weinhold empty_magazine(depot, depot->stores[i].loaded); 279a8806e5eSIngo Weinhold if (depot->stores[i].previous) 280a8806e5eSIngo Weinhold empty_magazine(depot, depot->stores[i].previous); 281a8806e5eSIngo Weinhold depot->stores[i].loaded = depot->stores[i].previous = NULL; 282a8806e5eSIngo Weinhold } 283a8806e5eSIngo Weinhold 284a8806e5eSIngo Weinhold RecursiveLocker _(depot->lock); 285a8806e5eSIngo Weinhold 286a8806e5eSIngo Weinhold while (depot->full) 287a8806e5eSIngo Weinhold empty_magazine(depot, _pop(depot->full)); 288a8806e5eSIngo Weinhold 289a8806e5eSIngo Weinhold while (depot->empty) 290a8806e5eSIngo Weinhold empty_magazine(depot, _pop(depot->empty)); 291a8806e5eSIngo Weinhold } 292