src/system/kernel/slab/ObjectDepot.cpp

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