mono/utils/lock-free-alloc.c

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