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