1 /* 2 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Copyright 2008-2010, Axel Dörfler. All Rights Reserved. 4 * Copyright 2007, Hugo Santos. All Rights Reserved. 5 * 6 * Distributed under the terms of the MIT License. 7 */ 8 9 10 #include <slab/ObjectDepot.h> 11 12 #include <algorithm> 13 14 #include <int.h> 15 #include <slab/Slab.h> 16 #include <smp.h> 17 #include <util/AutoLock.h> 18 19 #include "slab_private.h" 20 21 22 struct DepotMagazine { 23 DepotMagazine* next; 24 uint16 current_round; 25 uint16 round_count; 26 void* rounds[0]; 27 28 public: 29 inline bool IsEmpty() const; 30 inline bool IsFull() const; 31 32 inline void* Pop(); 33 inline bool Push(void* object); 34 }; 35 36 37 struct depot_cpu_store { 38 DepotMagazine* loaded; 39 DepotMagazine* previous; 40 }; 41 42 43 bool 44 DepotMagazine::IsEmpty() const 45 { 46 return current_round == 0; 47 } 48 49 50 bool 51 DepotMagazine::IsFull() const 52 { 53 return current_round == round_count; 54 } 55 56 57 void* 58 DepotMagazine::Pop() 59 { 60 return rounds[--current_round]; 61 } 62 63 64 bool 65 DepotMagazine::Push(void* object) 66 { 67 if (IsFull()) 68 return false; 69 70 rounds[current_round++] = object; 71 return true; 72 } 73 74 75 // #pragma mark - 76 77 78 static DepotMagazine* 79 alloc_magazine(object_depot* depot, uint32 flags) 80 { 81 DepotMagazine* magazine = (DepotMagazine*)slab_internal_alloc( 82 sizeof(DepotMagazine) + depot->magazine_capacity * sizeof(void*), 83 flags); 84 if (magazine) { 85 magazine->next = NULL; 86 magazine->current_round = 0; 87 magazine->round_count = depot->magazine_capacity; 88 } 89 90 return magazine; 91 } 92 93 94 static void 95 free_magazine(DepotMagazine* magazine, uint32 flags) 96 { 97 slab_internal_free(magazine, flags); 98 } 99 100 101 static void 102 empty_magazine(object_depot* depot, DepotMagazine* magazine, uint32 flags) 103 { 104 for (uint16 i = 0; i < magazine->current_round; i++) 105 depot->return_object(depot, depot->cookie, magazine->rounds[i], flags); 106 free_magazine(magazine, flags); 107 } 108 109 110 static bool 111 exchange_with_full(object_depot* depot, DepotMagazine*& magazine) 112 { 113 ASSERT(magazine->IsEmpty()); 114 115 SpinLocker _(depot->inner_lock); 116 117 if (depot->full == NULL) 118 return false; 119 120 depot->full_count--; 121 depot->empty_count++; 122 123 _push(depot->empty, magazine); 124 magazine = _pop(depot->full); 125 return true; 126 } 127 128 129 static bool 130 exchange_with_empty(object_depot* depot, DepotMagazine*& magazine, 131 DepotMagazine*& freeMagazine) 132 { 133 ASSERT(magazine == NULL || magazine->IsFull()); 134 135 SpinLocker _(depot->inner_lock); 136 137 if (depot->empty == NULL) 138 return false; 139 140 depot->empty_count--; 141 142 if (magazine != NULL) { 143 if (depot->full_count < depot->max_count) { 144 _push(depot->full, magazine); 145 depot->full_count++; 146 freeMagazine = NULL; 147 } else 148 freeMagazine = magazine; 149 } 150 151 magazine = _pop(depot->empty); 152 return true; 153 } 154 155 156 static void 157 push_empty_magazine(object_depot* depot, DepotMagazine* magazine) 158 { 159 SpinLocker _(depot->inner_lock); 160 161 _push(depot->empty, magazine); 162 depot->empty_count++; 163 } 164 165 166 static inline depot_cpu_store* 167 object_depot_cpu(object_depot* depot) 168 { 169 return &depot->stores[smp_get_current_cpu()]; 170 } 171 172 173 // #pragma mark - public API 174 175 176 status_t 177 object_depot_init(object_depot* depot, size_t capacity, size_t maxCount, 178 uint32 flags, void* cookie, void (*return_object)(object_depot* depot, 179 void* cookie, void* object, uint32 flags)) 180 { 181 depot->full = NULL; 182 depot->empty = NULL; 183 depot->full_count = depot->empty_count = 0; 184 depot->max_count = maxCount; 185 depot->magazine_capacity = capacity; 186 187 rw_lock_init(&depot->outer_lock, "object depot"); 188 B_INITIALIZE_SPINLOCK(&depot->inner_lock); 189 190 int cpuCount = smp_get_num_cpus(); 191 depot->stores = (depot_cpu_store*)slab_internal_alloc( 192 sizeof(depot_cpu_store) * cpuCount, flags); 193 if (depot->stores == NULL) { 194 rw_lock_destroy(&depot->outer_lock); 195 return B_NO_MEMORY; 196 } 197 198 for (int i = 0; i < cpuCount; i++) { 199 depot->stores[i].loaded = NULL; 200 depot->stores[i].previous = NULL; 201 } 202 203 depot->cookie = cookie; 204 depot->return_object = return_object; 205 206 return B_OK; 207 } 208 209 210 void 211 object_depot_destroy(object_depot* depot, uint32 flags) 212 { 213 object_depot_make_empty(depot, flags); 214 215 slab_internal_free(depot->stores, flags); 216 217 rw_lock_destroy(&depot->outer_lock); 218 } 219 220 221 void* 222 object_depot_obtain(object_depot* depot) 223 { 224 ReadLocker readLocker(depot->outer_lock); 225 InterruptsLocker interruptsLocker; 226 227 depot_cpu_store* store = object_depot_cpu(depot); 228 229 // To better understand both the Alloc() and Free() logic refer to 230 // Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings] 231 232 // In a nutshell, we try to get an object from the loaded magazine 233 // if it's not empty, or from the previous magazine if it's full 234 // and finally from the Slab if the magazine depot has no full magazines. 235 236 if (store->loaded == NULL) 237 return NULL; 238 239 while (true) { 240 if (!store->loaded->IsEmpty()) 241 return store->loaded->Pop(); 242 243 if (store->previous 244 && (store->previous->IsFull() 245 || exchange_with_full(depot, store->previous))) { 246 std::swap(store->previous, store->loaded); 247 } else 248 return NULL; 249 } 250 } 251 252 253 void 254 object_depot_store(object_depot* depot, void* object, uint32 flags) 255 { 256 ReadLocker readLocker(depot->outer_lock); 257 InterruptsLocker interruptsLocker; 258 259 depot_cpu_store* store = object_depot_cpu(depot); 260 261 // We try to add the object to the loaded magazine if we have one 262 // and it's not full, or to the previous one if it is empty. If 263 // the magazine depot doesn't provide us with a new empty magazine 264 // we return the object directly to the slab. 265 266 while (true) { 267 if (store->loaded != NULL && store->loaded->Push(object)) 268 return; 269 270 DepotMagazine* freeMagazine = NULL; 271 if ((store->previous != NULL && store->previous->IsEmpty()) 272 || exchange_with_empty(depot, store->previous, freeMagazine)) { 273 std::swap(store->loaded, store->previous); 274 275 if (freeMagazine != NULL) { 276 // Free the magazine that didn't have space in the list 277 interruptsLocker.Unlock(); 278 readLocker.Unlock(); 279 280 empty_magazine(depot, freeMagazine, flags); 281 282 readLocker.Lock(); 283 interruptsLocker.Lock(); 284 285 store = object_depot_cpu(depot); 286 } 287 } else { 288 // allocate a new empty magazine 289 interruptsLocker.Unlock(); 290 readLocker.Unlock(); 291 292 DepotMagazine* magazine = alloc_magazine(depot, flags); 293 if (magazine == NULL) { 294 depot->return_object(depot, depot->cookie, object, flags); 295 return; 296 } 297 298 readLocker.Lock(); 299 interruptsLocker.Lock(); 300 301 push_empty_magazine(depot, magazine); 302 store = object_depot_cpu(depot); 303 } 304 } 305 } 306 307 308 void 309 object_depot_make_empty(object_depot* depot, uint32 flags) 310 { 311 WriteLocker writeLocker(depot->outer_lock); 312 313 // collect the store magazines 314 315 DepotMagazine* storeMagazines = NULL; 316 317 int cpuCount = smp_get_num_cpus(); 318 for (int i = 0; i < cpuCount; i++) { 319 depot_cpu_store& store = depot->stores[i]; 320 321 if (store.loaded) { 322 _push(storeMagazines, store.loaded); 323 store.loaded = NULL; 324 } 325 326 if (store.previous) { 327 _push(storeMagazines, store.previous); 328 store.previous = NULL; 329 } 330 } 331 332 // detach the depot's full and empty magazines 333 334 DepotMagazine* fullMagazines = depot->full; 335 depot->full = NULL; 336 337 DepotMagazine* emptyMagazines = depot->empty; 338 depot->empty = NULL; 339 340 writeLocker.Unlock(); 341 342 // free all magazines 343 344 while (storeMagazines != NULL) 345 empty_magazine(depot, _pop(storeMagazines), flags); 346 347 while (fullMagazines != NULL) 348 empty_magazine(depot, _pop(fullMagazines), flags); 349 350 while (emptyMagazines) 351 free_magazine(_pop(emptyMagazines), flags); 352 } 353 354 355 // #pragma mark - private kernel API 356 357 358 void 359 dump_object_depot(object_depot* depot) 360 { 361 kprintf(" full: %p, count %lu\n", depot->full, depot->full_count); 362 kprintf(" empty: %p, count %lu\n", depot->empty, depot->empty_count); 363 kprintf(" max full: %lu\n", depot->max_count); 364 kprintf(" capacity: %lu\n", depot->magazine_capacity); 365 kprintf(" stores:\n"); 366 367 int cpuCount = smp_get_num_cpus(); 368 369 for (int i = 0; i < cpuCount; i++) { 370 kprintf(" [%d] loaded: %p\n", i, depot->stores[i].loaded); 371 kprintf(" previous: %p\n", depot->stores[i].previous); 372 } 373 } 374 375 376 int 377 dump_object_depot(int argCount, char** args) 378 { 379 if (argCount != 2) 380 kprintf("usage: %s [address]\n", args[0]); 381 else 382 dump_object_depot((object_depot*)parse_expression(args[1])); 383 384 return 0; 385 } 386 387 388 int 389 dump_depot_magazine(int argCount, char** args) 390 { 391 if (argCount != 2) { 392 kprintf("usage: %s [address]\n", args[0]); 393 return 0; 394 } 395 396 DepotMagazine* magazine = (DepotMagazine*)parse_expression(args[1]); 397 398 kprintf("next: %p\n", magazine->next); 399 kprintf("current_round: %u\n", magazine->current_round); 400 kprintf("round_count: %u\n", magazine->round_count); 401 402 for (uint16 i = 0; i < magazine->current_round; i++) 403 kprintf(" [%i] %p\n", i, magazine->rounds[i]); 404 405 return 0; 406 } 407