mono/utils/lock-free-alloc.c

   1 /*
   2  * lock-free-alloc.c: Lock free allocator.
   3  *
   4  * (C) Copyright 2011 Novell, Inc
   5  *
   6  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   7  */
   8
   9 /*
  10  * This is a simplified version of the lock-free allocator described in
  11  *
  12  * Scalable Lock-Free Dynamic Memory Allocation
  13  * Maged M. Michael, PLDI 2004
  14  *
  15  * I could not get Michael's allocator working bug free under heavy
  16  * stress tests.  The paper doesn't provide correctness proof and after
  17  * failing to formalize the ownership of descriptors I devised this
  18  * simpler allocator.
  19  *
  20  * Allocation within superblocks proceeds exactly like in Michael's
  21  * allocator.  The simplification is that a thread has to "acquire" a
  22  * descriptor before it can allocate from its superblock.  While it owns
  23  * the descriptor no other thread can acquire and hence allocate from
  24  * it.  A consequence of this is that the ABA problem cannot occur, so
  25  * we don't need the tag field and don't have to use 64 bit CAS.
  26  *
  27  * Descriptors are stored in two locations: The partial queue and the
  28  * active field.  They can only be in at most one of those at one time.
  29  * If a thread wants to allocate, it needs to get a descriptor.  It
  30  * tries the active descriptor first, CASing it to NULL.  If that
  31  * doesn't work, it gets a descriptor out of the partial queue.  Once it
  32  * has the descriptor it owns it because it is not referenced anymore.
  33  * It allocates a slot and then gives the descriptor back (unless it is
  34  * FULL).
  35  *
  36  * Note that it is still possible that a slot is freed while an
  37  * allocation is in progress from the same superblock.  Ownership in
  38  * this case is not complicated, though.  If the block was FULL and the
  39  * free set it to PARTIAL, the free now owns the block (because FULL
  40  * blocks are not referenced from partial and active) and has to give it
  41  * back.  If the block was PARTIAL then the free doesn't own the block
  42  * (because it's either still referenced, or an alloc owns it).  A
  43  * special case of this is that it has changed from PARTIAL to EMPTY and
  44  * now needs to be retired.  Technically, the free wouldn't have to do
  45  * anything in this case because the first thing an alloc does when it
  46  * gets ownership of a descriptor is to check whether it is EMPTY and
  47  * retire it if that is the case.  As an optimization, our free does try
  48  * to acquire the descriptor (by CASing the active field, which, if it
  49  * is lucky, points to that descriptor) and if it can do so, retire it.
  50  * If it can't, it tries to retire other descriptors from the partial
  51  * queue, so that we can be sure that even if no more allocations
  52  * happen, descriptors are still retired.  This is analogous to what
  53  * Michael's allocator does.
  54  *
  55  * Another difference to Michael's allocator is not related to
  56  * concurrency, however: We don't point from slots to descriptors.
  57  * Instead we allocate superblocks aligned and point from the start of
  58  * the superblock to the descriptor, so we only need one word of
  59  * metadata per superblock.
  60  *
  61  * FIXME: Having more than one allocator per size class is probably
  62  * buggy because it was never tested.
  63  */
  64
  65 #include <glib.h>
  66 #include <stdlib.h>
  67
  68 #include <mono/utils/atomic.h>
  69 #ifdef SGEN_WITHOUT_MONO
  70 #include <mono/sgen/sgen-gc.h>
  71 #include <mono/sgen/sgen-client.h>
  72 #else
  73 #include <mono/utils/mono-mmap.h>
  74 #endif
  75 #include <mono/utils/mono-membar.h>
  76 #include <mono/utils/hazard-pointer.h>
  77 #include <mono/utils/lock-free-queue.h>
  78
  79 #include <mono/utils/lock-free-alloc.h>
  80
  81 //#define DESC_AVAIL_DUMMY
  82
  83 enum {
  84         STATE_FULL,
  85         STATE_PARTIAL,
  86         STATE_EMPTY
  87 };
  88
  89 typedef union {
  90         gint32 value;
  91         struct {
  92                 guint32 avail : 15;
  93                 guint32 count : 15;
  94                 guint32 state : 2;
  95         } data;
  96 } Anchor;
  97
  98 typedef struct _MonoLockFreeAllocDescriptor Descriptor;
  99 struct _MonoLockFreeAllocDescriptor {
 100         MonoLockFreeQueueNode node;
 101         MonoLockFreeAllocator *heap;
 102         volatile Anchor anchor;
 103         unsigned int slot_size;
 104         unsigned int block_size;
 105         unsigned int max_count;
 106         gpointer sb;
 107 #ifndef DESC_AVAIL_DUMMY
 108         Descriptor * volatile next;
 109 #endif
 110         gboolean in_use;        /* used for debugging only */
 111 };
 112
 113 #define NUM_DESC_BATCH  64
 114
 115 static MONO_ALWAYS_INLINE gpointer
 116 sb_header_for_addr (gpointer addr, size_t block_size)
 117 {
 118         return (gpointer)(((size_t)addr) & (~(block_size - 1)));
 119 }
 120
 121 /* Taken from SGen */
 122
 123 static unsigned long
 124 prot_flags_for_activate (int activate)
 125 {
 126         unsigned long prot_flags = activate? MONO_MMAP_READ|MONO_MMAP_WRITE: MONO_MMAP_NONE;
 127         return prot_flags | MONO_MMAP_PRIVATE | MONO_MMAP_ANON;
 128 }
 129
 130 static gpointer
 131 alloc_sb (Descriptor *desc)
 132 {
 133         static int pagesize = -1;
 134
 135         gpointer sb_header;
 136
 137         if (pagesize == -1)
 138                 pagesize = mono_pagesize ();
 139
 140         sb_header = desc->block_size == pagesize ?
 141                 mono_valloc (NULL, desc->block_size, prot_flags_for_activate (TRUE)) :
 142                 mono_valloc_aligned (desc->block_size, desc->block_size, prot_flags_for_activate (TRUE));
 143
 144         g_assert (sb_header == sb_header_for_addr (sb_header, desc->block_size));
 145
 146         *(Descriptor**)sb_header = desc;
 147         //g_print ("sb %p for %p\n", sb_header, desc);
 148
 149         return (char*)sb_header + LOCK_FREE_ALLOC_SB_HEADER_SIZE;
 150 }
 151
 152 static void
 153 free_sb (gpointer sb, size_t block_size)
 154 {
 155         gpointer sb_header = sb_header_for_addr (sb, block_size);
 156         g_assert ((char*)sb_header + LOCK_FREE_ALLOC_SB_HEADER_SIZE == sb);
 157         mono_vfree (sb_header, block_size);
 158         //g_print ("free sb %p\n", sb_header);
 159 }
 160
 161 #ifndef DESC_AVAIL_DUMMY
 162 static Descriptor * volatile desc_avail;
 163
 164 static Descriptor*
 165 desc_alloc (void)
 166 {
 167         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 168         Descriptor *desc;
 169
 170         for (;;) {
 171                 gboolean success;
 172
 173                 desc = (Descriptor *) get_hazardous_pointer ((gpointer * volatile)&desc_avail, hp, 1);
 174                 if (desc) {
 175                         Descriptor *next = desc->next;
 176                         success = (InterlockedCompareExchangePointer ((gpointer * volatile)&desc_avail, next, desc) == desc);
 177                 } else {
 178                         size_t desc_size = sizeof (Descriptor);
 179                         Descriptor *d;
 180                         int i;
 181
 182                         desc = (Descriptor *) mono_valloc (NULL, desc_size * NUM_DESC_BATCH, prot_flags_for_activate (TRUE));
 183
 184                         /* Organize into linked list. */
 185                         d = desc;
 186                         for (i = 0; i < NUM_DESC_BATCH; ++i) {
 187                                 Descriptor *next = (i == (NUM_DESC_BATCH - 1)) ? NULL : (Descriptor*)((char*)desc + ((i + 1) * desc_size));
 188                                 d->next = next;
 189                                 mono_lock_free_queue_node_init (&d->node, TRUE);
 190                                 d = next;
 191                         }
 192
 193                         mono_memory_write_barrier ();
 194
 195                         success = (InterlockedCompareExchangePointer ((gpointer * volatile)&desc_avail, desc->next, NULL) == NULL);
 196
 197                         if (!success)
 198                                 mono_vfree (desc, desc_size * NUM_DESC_BATCH);
 199                 }
 200
 201                 mono_hazard_pointer_clear (hp, 1);
 202
 203                 if (success)
 204                         break;
 205         }
 206
 207         g_assert (!desc->in_use);
 208         desc->in_use = TRUE;
 209
 210         return desc;
 211 }
 212
 213 static void
 214 desc_enqueue_avail (gpointer _desc)
 215 {
 216         Descriptor *desc = (Descriptor *) _desc;
 217         Descriptor *old_head;
 218
 219         g_assert (desc->anchor.data.state == STATE_EMPTY);
 220         g_assert (!desc->in_use);
 221
 222         do {
 223                 old_head = desc_avail;
 224                 desc->next = old_head;
 225                 mono_memory_write_barrier ();
 226         } while (InterlockedCompareExchangePointer ((gpointer * volatile)&desc_avail, desc, old_head) != old_head);
 227 }
 228
 229 static void
 230 desc_retire (Descriptor *desc)
 231 {
 232         g_assert (desc->anchor.data.state == STATE_EMPTY);
 233         g_assert (desc->in_use);
 234         desc->in_use = FALSE;
 235         free_sb (desc->sb, desc->block_size);
 236         mono_thread_hazardous_try_free (desc, desc_enqueue_avail);
 237 }
 238 #else
 239 MonoLockFreeQueue available_descs;
 240
 241 static Descriptor*
 242 desc_alloc (void)
 243 {
 244         Descriptor *desc = (Descriptor*)mono_lock_free_queue_dequeue (&available_descs);
 245
 246         if (desc)
 247                 return desc;
 248
 249         return calloc (1, sizeof (Descriptor));
 250 }
 251
 252 static void
 253 desc_retire (Descriptor *desc)
 254 {
 255         free_sb (desc->sb, desc->block_size);
 256         mono_lock_free_queue_enqueue (&available_descs, &desc->node);
 257 }
 258 #endif
 259
 260 static Descriptor*
 261 list_get_partial (MonoLockFreeAllocSizeClass *sc)
 262 {
 263         for (;;) {
 264                 Descriptor *desc = (Descriptor*) mono_lock_free_queue_dequeue (&sc->partial);
 265                 if (!desc)
 266                         return NULL;
 267                 if (desc->anchor.data.state != STATE_EMPTY)
 268                         return desc;
 269                 desc_retire (desc);
 270         }
 271 }
 272
 273 static void
 274 desc_put_partial (gpointer _desc)
 275 {
 276         Descriptor *desc = (Descriptor *) _desc;
 277
 278         g_assert (desc->anchor.data.state != STATE_FULL);
 279
 280         mono_lock_free_queue_node_free (&desc->node);
 281         mono_lock_free_queue_enqueue (&desc->heap->sc->partial, &desc->node);
 282 }
 283
 284 static void
 285 list_put_partial (Descriptor *desc)
 286 {
 287         g_assert (desc->anchor.data.state != STATE_FULL);
 288         mono_thread_hazardous_try_free (desc, desc_put_partial);
 289 }
 290
 291 static void
 292 list_remove_empty_desc (MonoLockFreeAllocSizeClass *sc)
 293 {
 294         int num_non_empty = 0;
 295         for (;;) {
 296                 Descriptor *desc = (Descriptor*) mono_lock_free_queue_dequeue (&sc->partial);
 297                 if (!desc)
 298                         return;
 299                 /*
 300                  * We don't need to read atomically because we're the
 301                  * only thread that references this descriptor.
 302                  */
 303                 if (desc->anchor.data.state == STATE_EMPTY) {
 304                         desc_retire (desc);
 305                 } else {
 306                         g_assert (desc->heap->sc == sc);
 307                         mono_thread_hazardous_try_free (desc, desc_put_partial);
 308                         if (++num_non_empty >= 2)
 309                                 return;
 310                 }
 311         }
 312 }
 313
 314 static Descriptor*
 315 heap_get_partial (MonoLockFreeAllocator *heap)
 316 {
 317         return list_get_partial (heap->sc);
 318 }
 319
 320 static void
 321 heap_put_partial (Descriptor *desc)
 322 {
 323         list_put_partial (desc);
 324 }
 325
 326 static gboolean
 327 set_anchor (Descriptor *desc, Anchor old_anchor, Anchor new_anchor)
 328 {
 329         if (old_anchor.data.state == STATE_EMPTY)
 330                 g_assert (new_anchor.data.state == STATE_EMPTY);
 331
 332         return InterlockedCompareExchange (&desc->anchor.value, new_anchor.value, old_anchor.value) == old_anchor.value;
 333 }
 334
 335 static gpointer
 336 alloc_from_active_or_partial (MonoLockFreeAllocator *heap)
 337 {
 338         Descriptor *desc;
 339         Anchor old_anchor, new_anchor;
 340         gpointer addr;
 341
 342  retry:
 343         desc = heap->active;
 344         if (desc) {
 345                 if (InterlockedCompareExchangePointer ((gpointer * volatile)&heap->active, NULL, desc) != desc)
 346                         goto retry;
 347         } else {
 348                 desc = heap_get_partial (heap);
 349                 if (!desc)
 350                         return NULL;
 351         }
 352
 353         /* Now we own the desc. */
 354
 355         do {
 356                 unsigned int next;
 357                 new_anchor = old_anchor = *(volatile Anchor*)&desc->anchor.value;
 358                 if (old_anchor.data.state == STATE_EMPTY) {
 359                         /* We must free it because we own it. */
 360                         desc_retire (desc);
 361                         goto retry;
 362                 }
 363                 g_assert (old_anchor.data.state == STATE_PARTIAL);
 364                 g_assert (old_anchor.data.count > 0);
 365
 366                 addr = (char*)desc->sb + old_anchor.data.avail * desc->slot_size;
 367
 368                 mono_memory_read_barrier ();
 369
 370                 next = *(unsigned int*)addr;
 371                 g_assert (next < LOCK_FREE_ALLOC_SB_USABLE_SIZE (desc->block_size) / desc->slot_size);
 372
 373                 new_anchor.data.avail = next;
 374                 --new_anchor.data.count;
 375
 376                 if (new_anchor.data.count == 0)
 377                         new_anchor.data.state = STATE_FULL;
 378         } while (!set_anchor (desc, old_anchor, new_anchor));
 379
 380         /* If the desc is partial we have to give it back. */
 381         if (new_anchor.data.state == STATE_PARTIAL) {
 382                 if (InterlockedCompareExchangePointer ((gpointer * volatile)&heap->active, desc, NULL) != NULL)
 383                         heap_put_partial (desc);
 384         }
 385
 386         return addr;
 387 }
 388
 389 static gpointer
 390 alloc_from_new_sb (MonoLockFreeAllocator *heap)
 391 {
 392         unsigned int slot_size, block_size, count, i;
 393         Descriptor *desc = desc_alloc ();
 394
 395         slot_size = desc->slot_size = heap->sc->slot_size;
 396         block_size = desc->block_size = heap->sc->block_size;
 397         count = LOCK_FREE_ALLOC_SB_USABLE_SIZE (block_size) / slot_size;
 398
 399         desc->heap = heap;
 400         /*
 401          * Setting avail to 1 because 0 is the block we're allocating
 402          * right away.
 403          */
 404         desc->anchor.data.avail = 1;
 405         desc->slot_size = heap->sc->slot_size;
 406         desc->max_count = count;
 407
 408         desc->anchor.data.count = desc->max_count - 1;
 409         desc->anchor.data.state = STATE_PARTIAL;
 410
 411         desc->sb = alloc_sb (desc);
 412
 413         /* Organize blocks into linked list. */
 414         for (i = 1; i < count - 1; ++i)
 415                 *(unsigned int*)((char*)desc->sb + i * slot_size) = i + 1;
 416
 417         mono_memory_write_barrier ();
 418
 419         /* Make it active or free it again. */
 420         if (InterlockedCompareExchangePointer ((gpointer * volatile)&heap->active, desc, NULL) == NULL) {
 421                 return desc->sb;
 422         } else {
 423                 desc->anchor.data.state = STATE_EMPTY;
 424                 desc_retire (desc);
 425                 return NULL;
 426         }
 427 }
 428
 429 gpointer
 430 mono_lock_free_alloc (MonoLockFreeAllocator *heap)
 431 {
 432         gpointer addr;
 433
 434         for (;;) {
 435
 436                 addr = alloc_from_active_or_partial (heap);
 437                 if (addr)
 438                         break;
 439
 440                 addr = alloc_from_new_sb (heap);
 441                 if (addr)
 442                         break;
 443         }
 444
 445         return addr;
 446 }
 447
 448 void
 449 mono_lock_free_free (gpointer ptr, size_t block_size)
 450 {
 451         Anchor old_anchor, new_anchor;
 452         Descriptor *desc;
 453         gpointer sb;
 454         MonoLockFreeAllocator *heap = NULL;
 455
 456         desc = *(Descriptor**) sb_header_for_addr (ptr, block_size);
 457         g_assert (block_size == desc->block_size);
 458
 459         sb = desc->sb;
 460
 461         do {
 462                 new_anchor = old_anchor = *(volatile Anchor*)&desc->anchor.value;
 463                 *(unsigned int*)ptr = old_anchor.data.avail;
 464                 new_anchor.data.avail = ((char*)ptr - (char*)sb) / desc->slot_size;
 465                 g_assert (new_anchor.data.avail < LOCK_FREE_ALLOC_SB_USABLE_SIZE (block_size) / desc->slot_size);
 466
 467                 if (old_anchor.data.state == STATE_FULL)
 468                         new_anchor.data.state = STATE_PARTIAL;
 469
 470                 if (++new_anchor.data.count == desc->max_count) {
 471                         heap = desc->heap;
 472                         new_anchor.data.state = STATE_EMPTY;
 473                 }
 474         } while (!set_anchor (desc, old_anchor, new_anchor));
 475
 476         if (new_anchor.data.state == STATE_EMPTY) {
 477                 g_assert (old_anchor.data.state != STATE_EMPTY);
 478
 479                 if (InterlockedCompareExchangePointer ((gpointer * volatile)&heap->active, NULL, desc) == desc) {
 480                         /* We own it, so we free it. */
 481                         desc_retire (desc);
 482                 } else {
 483                         /*
 484                          * Somebody else must free it, so we do some
 485                          * freeing for others.
 486                          */
 487                         list_remove_empty_desc (heap->sc);
 488                 }
 489         } else if (old_anchor.data.state == STATE_FULL) {
 490                 /*
 491                  * Nobody owned it, now we do, so we need to give it
 492                  * back.
 493                  */
 494
 495                 g_assert (new_anchor.data.state == STATE_PARTIAL);
 496
 497                 if (InterlockedCompareExchangePointer ((gpointer * volatile)&desc->heap->active, desc, NULL) != NULL)
 498                         heap_put_partial (desc);
 499         }
 500 }
 501
 502 #define g_assert_OR_PRINT(c, format, ...)       do {                            \
 503                 if (!(c)) {                                             \
 504                         if (print)                                      \
 505                                 g_print ((format), ## __VA_ARGS__);     \
 506                         else                                            \
 507                                 g_assert (FALSE);                               \
 508                 }                                                       \
 509         } while (0)
 510
 511 static void
 512 descriptor_check_consistency (Descriptor *desc, gboolean print)
 513 {
 514         int count = desc->anchor.data.count;
 515         int max_count = LOCK_FREE_ALLOC_SB_USABLE_SIZE (desc->block_size) / desc->slot_size;
 516 #if _MSC_VER
 517         gboolean* linked = alloca(max_count*sizeof(gboolean));
 518 #else
 519         gboolean linked [max_count];
 520 #endif
 521         int i, last;
 522         unsigned int index;
 523
 524 #ifndef DESC_AVAIL_DUMMY
 525         Descriptor *avail;
 526
 527         for (avail = desc_avail; avail; avail = avail->next)
 528                 g_assert_OR_PRINT (desc != avail, "descriptor is in the available list\n");
 529 #endif
 530
 531         g_assert_OR_PRINT (desc->slot_size == desc->heap->sc->slot_size, "slot size doesn't match size class\n");
 532
 533         if (print)
 534                 g_print ("descriptor %p is ", desc);
 535
 536         switch (desc->anchor.data.state) {
 537         case STATE_FULL:
 538                 if (print)
 539                         g_print ("full\n");
 540                 g_assert_OR_PRINT (count == 0, "count is not zero: %d\n", count);
 541                 break;
 542         case STATE_PARTIAL:
 543                 if (print)
 544                         g_print ("partial\n");
 545                 g_assert_OR_PRINT (count < max_count, "count too high: is %d but must be below %d\n", count, max_count);
 546                 break;
 547         case STATE_EMPTY:
 548                 if (print)
 549                         g_print ("empty\n");
 550                 g_assert_OR_PRINT (count == max_count, "count is wrong: is %d but should be %d\n", count, max_count);
 551                 break;
 552         default:
 553                 g_assert_OR_PRINT (FALSE, "invalid state\n");
 554         }
 555
 556         for (i = 0; i < max_count; ++i)
 557                 linked [i] = FALSE;
 558
 559         index = desc->anchor.data.avail;
 560         last = -1;
 561         for (i = 0; i < count; ++i) {
 562                 gpointer addr = (char*)desc->sb + index * desc->slot_size;
 563                 g_assert_OR_PRINT (index >= 0 && index < max_count,
 564                                 "index %d for %dth available slot, linked from %d, not in range [0 .. %d)\n",
 565                                 index, i, last, max_count);
 566                 g_assert_OR_PRINT (!linked [index], "%dth available slot %d linked twice\n", i, index);
 567                 if (linked [index])
 568                         break;
 569                 linked [index] = TRUE;
 570                 last = index;
 571                 index = *(unsigned int*)addr;
 572         }
 573 }
 574
 575 gboolean
 576 mono_lock_free_allocator_check_consistency (MonoLockFreeAllocator *heap)
 577 {
 578         Descriptor *active = heap->active;
 579         Descriptor *desc;
 580         if (active) {
 581                 g_assert (active->anchor.data.state == STATE_PARTIAL);
 582                 descriptor_check_consistency (active, FALSE);
 583         }
 584         while ((desc = (Descriptor*)mono_lock_free_queue_dequeue (&heap->sc->partial))) {
 585                 g_assert (desc->anchor.data.state == STATE_PARTIAL || desc->anchor.data.state == STATE_EMPTY);
 586                 descriptor_check_consistency (desc, FALSE);
 587         }
 588         return TRUE;
 589 }
 590
 591 void
 592 mono_lock_free_allocator_init_size_class (MonoLockFreeAllocSizeClass *sc, unsigned int slot_size, unsigned int block_size)
 593 {
 594         g_assert (block_size > 0);
 595         g_assert ((block_size & (block_size - 1)) == 0); /* check if power of 2 */
 596         g_assert (slot_size * 2 <= LOCK_FREE_ALLOC_SB_USABLE_SIZE (block_size));
 597
 598         mono_lock_free_queue_init (&sc->partial);
 599         sc->slot_size = slot_size;
 600         sc->block_size = block_size;
 601 }
 602
 603 void
 604 mono_lock_free_allocator_init_allocator (MonoLockFreeAllocator *heap, MonoLockFreeAllocSizeClass *sc)
 605 {
 606         heap->sc = sc;
 607         heap->active = NULL;
 608 }