gee/hazardpointer.vala

   1 /* hazardpointer.vala
   2  *
   3  * Copyright (C) 2011  Maciej Piechotka
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  18  *
  19  * Author:
  20  *      Maciej Piechotka <uzytkownik2@gmail.com>
  21  */
  22
  23 /**
  24  * Hazard pointer is a method of protecting a pointer shared by many threads.
  25  * If you want to use atomic pointer that may be freed you should use following code:
  26  *
  27  * {{{
  28  *    string *shared_pointer = ...;
  29  *    HazardPointer<string> hptr = HazardPointer.get_hazard_pointer (&shared_pointer);
  30  *    // my_string contains value from shared_pinter. It is valid as long as hptr is alive.
  31  *    unowned string my_string = ptr.get ();
  32  *    // instead of delete
  33  *    ptr.release ((ptr) => {string *sptr = ptr;string ref = (owned)sptr;});
  34  *    });
  35  * }}}
  36  *
  37  * In some cases you may use helper methods which might involve copying of object (and are unsafe for unowned objects):
  38  * {{{
  39  *    Gtk.Window *window = ...;
  40  *    Gtk.Window? local_window = HazardPointer.get_pointer (&window);
  41  *    HazardPointer.set_pointer (&window, ...)
  42  *    local_window = HazardPointer.exchange_pointer (&window, null);
  43  *    HazardPointer.compare_and_exchange (&window, null, local_window);
  44  * }}}
  45  *
  46  * The class also provides helper methods if least significant bits are used for storing flags.
  47  *
  48  * HazardPointers are not thread-safe (unless documentation states otherwise).
  49  */
  50 [Compact]
  51 public class Gee.HazardPointer<G> { // FIXME: Make it a struct
  52         /**
  53          * Creates a hazard pointer for a pointer.
  54          *
  55          * @param ptr Protected pointer
  56          */
  57         public HazardPointer (G *ptr) {
  58                 this._node = acquire ();
  59                 this._node.set ((void *)ptr);
  60         }
  61
  62         /**
  63          * Create a hazard pointer from Node.
  64          */
  65         internal HazardPointer.from_node (Node node) {
  66                 this._node = node;
  67         }
  68
  69         /**
  70          * Gets hazard pointer from atomic pointer safely.
  71          *
  72          * @param aptr Atomic pointer.
  73          * @param mask Mask of bits.
  74          * @param mask_out Result of mask.
  75          * @return Hazard pointer containing the element.
  76          */
  77         public static HazardPointer<G>? get_hazard_pointer<G> (G **aptr, size_t mask = 0, out size_t mask_out = null) {
  78                 unowned Node node = acquire ();
  79                 void *rptr = null;
  80                 void *ptr = null;
  81                 mask_out = 0;
  82                 do {
  83                         rptr = AtomicPointer.get ((void **)aptr);
  84                         ptr = (void *)((size_t) rptr & ~mask);
  85                         mask_out = (size_t) rptr & mask;
  86                         node.set (ptr);
  87                 } while (rptr != AtomicPointer.get ((void **)aptr));
  88                 if (ptr != null) {
  89                         return new HazardPointer<G>.from_node (node);
  90                 } else {
  91                         node.release ();
  92                         return null;
  93                 }
  94         }
  95
  96         /**
  97          * Copy an object from atomic pointer.
  98          *
  99          * @param aptr Atomic pointer.
 100          * @param mask Mask of flags.
 101          * @param mask_out Result of mask.
 102          * @return A copy of object from atomic pointer.
 103          */
 104         public static G? get_pointer<G> (G **aptr, size_t mask = 0, out size_t mask_out = null) {
 105                 unowned Node node = acquire ();
 106                 void *rptr = null;
 107                 void *ptr = null;
 108                 mask_out = 0;
 109                 do {
 110                         rptr = AtomicPointer.get ((void **)aptr);
 111                         ptr = (void *)((size_t) rptr & ~mask);
 112                         mask_out = (size_t) rptr & mask;
 113                         node.set (ptr);
 114                 } while (rptr != AtomicPointer.get ((void **)aptr));
 115                 G? res = (G *)ptr;
 116                 node.release ();
 117                 return res;
 118         }
 119
 120         /**
 121          * Exchange objects safly.
 122          *
 123          * @param aptr Atomic pointer.
 124          * @param new_ptr New value
 125          * @param mask Mask of flags.
 126          * @param new_mask New mask.
 127          * @param old_mask Previous mask mask.
 128          * @return Hazard pointer containing old value.
 129          */
 130         public static HazardPointer<G>? exchange_hazard_pointer<G> (G **aptr, owned G? new_ptr, size_t mask = 0, size_t new_mask = 0, out size_t old_mask = null) {
 131                 unowned Node? new_node = null;
 132                 if (new_ptr != null) {
 133                         new_node = acquire ();
 134                         new_node.set (new_ptr);
 135                 }
 136                 old_mask = 0;
 137                 void *new_rptr = (void *)((size_t)((owned) new_ptr) | (mask & new_mask));
 138                 unowned Node node = acquire ();
 139                 void *rptr = null;
 140                 void *ptr = null;
 141                 do {
 142                         rptr = AtomicPointer.get ((void **)aptr);
 143                         ptr = (void *)((size_t) rptr & ~mask);
 144                         old_mask = (size_t) rptr & mask;
 145                         node.set (ptr);
 146                 } while (!AtomicPointer.compare_and_exchange((void **)aptr, rptr, new_rptr));
 147                 if (new_node != null)
 148                         new_node.release ();
 149                 if (ptr != null) {
 150                         return new HazardPointer<G>.from_node (node);
 151                 } else {
 152                         node.release ();
 153                         return null;
 154                 }
 155         }
 156
 157         /**
 158          * Sets object safely
 159          *
 160          * @param aptr Atomic pointer.
 161          * @param new_ptr New value
 162          * @param mask Mask of flags.
 163          * @param new_mask New mask.
 164          */
 165         public static void set_pointer<G> (G **aptr, owned G? new_ptr, size_t mask = 0, size_t new_mask = 0) {
 166                 HazardPointer<G>? ptr = exchange_hazard_pointer<G> (aptr, new_ptr, mask, new_mask, null);
 167                 if (ptr != null) {
 168                         DestroyNotify<G> notify = get_destroy_notify<G> ();
 169                         ptr.release ((owned)notify);
 170                 }
 171         }
 172
 173         /**
 174          * Exchange objects safly.
 175          *
 176          * @param aptr Atomic pointer.
 177          * @param new_ptr New value
 178          * @param mask Mask of flags.
 179          * @param new_mask New mask.
 180          * @param old_mask Previous mask mask.
 181          * @return Value that was previously stored.
 182          */
 183         public static G? exchange_pointer<G> (G **aptr, owned G? new_ptr, size_t mask = 0, size_t new_mask = 0, out size_t old_mask = null) {
 184                 HazardPointer<G>? ptr = exchange_hazard_pointer<G> (aptr, new_ptr, mask, new_mask, out old_mask);
 185                 G? rptr = ptr != null ? ptr.get () : null;
 186                 return rptr;
 187         }
 188
 189         /**
 190          * Compares and exchanges objects.
 191          *
 192          * @param aptr Atomic pointer.
 193          * @param old_ptr Old pointer.
 194          * @param _new_ptr New value.
 195          * @param old_mask Old mask.
 196          * @param new_mask New mask.
 197          * @return Value that was previously stored.
 198          */
 199         public static bool compare_and_exchange_pointer<G> (G **aptr, G? old_ptr, owned G? _new_ptr, size_t mask = 0, size_t old_mask = 0, size_t new_mask = 0) {
 200                 G *new_ptr = (owned)_new_ptr;
 201                 void *new_rptr = (void *)((size_t)(new_ptr) | (mask & new_mask));
 202                 void *old_rptr = (void *)((size_t)(old_ptr) | (mask & old_mask));
 203                 bool success = AtomicPointer.compare_and_exchange((void **)aptr, old_rptr, new_rptr);
 204                 if (success) {
 205                         DestroyNotify<G> notify = get_destroy_notify<G> ();
 206                         if (old_ptr != null) {
 207                                 Context.get_current_context ()->release_ptr (old_ptr, (owned)notify);
 208                         }
 209                 } else if (new_ptr != null) {
 210                         _new_ptr = (owned)new_ptr;
 211                 }
 212                 return success;
 213         }
 214
 215         ~HazardPointer () {
 216                 _node.release ();
 217         }
 218
 219         /**
 220          * Gets the pointer hold by hazard pointer.
 221          *
 222          * @param other_thread Have to be set to ``true`` if accessed from thread that did not create this thread.
 223          * @return The value hold by pointer.
 224          */
 225         public inline new unowned G get (bool other_thread = false) {
 226                 return _node[other_thread];
 227         }
 228
 229         /**
 230          * Free the pointer.
 231          *
 232          * @param notify method freeing object
 233          */
 234         public void release (owned DestroyNotify notify) {
 235                 unowned G item = _node[false];
 236                 _node.set (null);
 237                 if (item != null) {
 238                         Context.get_current_context ()->release_ptr (item, (owned)notify);
 239                 }
 240         }
 241
 242         /**
 243          * Sets default policy (i.e. default policy for user-created contexts).
 244          * The policy must be concrete and should not be blocking.
 245          *
 246          * @param policy New default policy.
 247          */
 248         public static void set_default_policy (Policy policy) requires (policy.is_concrete ()) {
 249                 if (policy.is_blocking ())
 250                         warning ("Setting blocking defautl Gee.HazardPointer.Policy (there may be a deadlock).\n");
 251                 AtomicInt.set(ref _default_policy, (int)policy);
 252         }
 253
 254         /**
 255          * Sets thread exit policy (i.e. default policy for the top-most Context).
 256          * The policy must be concrete and should not be unsafe.
 257          *
 258          * @param policy New thread policy.
 259          */
 260         public static void set_thread_exit_policy (Policy policy) requires (policy.is_concrete ()) {
 261                 if (!policy.is_safe ())
 262                         warning ("Setting unsafe globale thread-exit Gee.HazardPointer.Policy (there may be a memory leak).\n");
 263                 AtomicInt.set(ref _thread_exit_policy, (int)policy);
 264         }
 265
 266         /**
 267          * Sets release (i.e. how exactly the released objects arefreed).
 268          *
 269          * The method can be only set before any objects is released and is not thread-safe.
 270          *
 271          * @param policy New release policy.
 272          */
 273         public static bool set_release_policy (ReleasePolicy policy) {
 274                 int old_policy = AtomicInt.get (ref release_policy);
 275                 if ((old_policy & (sizeof(int) * 8 - 1)) != 0) {
 276                         critical ("Attempt to change the policy of running helper. Failing.");
 277                         return false;
 278                 }
 279                 if (!AtomicInt.compare_and_exchange (ref release_policy, old_policy, (int)policy)) {
 280                         critical ("Concurrent access to release policy detected. Failing.");
 281                         return false;
 282                 }
 283                 return true;
 284         }
 285
 286         /**
 287          * Policy determines what happens on exit from Context.
 288          */
 289         public enum Policy {
 290                 /**
 291                  * Performs default action on exit from thread.
 292                  */
 293                 DEFAULT,
 294                 /**
 295                  * Performs the same action as on exit from current thread.
 296                  */
 297                 THREAD_EXIT,
 298                 /**
 299                  * Goes through the free list and attempts to free un-freed elements.
 300                  */
 301                 TRY_FREE,
 302                 /**
 303                  * Goes through the free list and attempts to free un-freed elements
 304                  * untill all elements are freed.
 305                  */
 306                 FREE,
 307                 /**
 308                  * Release the un-freed elements to either helper thread or to main loop.
 309                  * Please note if the operation would block it is not performed.
 310                  */
 311                 TRY_RELEASE,
 312                 /**
 313                  * Release the un-freed elements to either helper thread or to main loop.
 314                  * Please note it may block while adding to queue.
 315                  */
 316                 RELEASE;
 317
 318                 /**
 319                  * Checks if the policy is concrete or if it depends on global variables.
 320                  *
 321                  * @return ``true`` if this policy does not depend on global variables
 322                  */
 323                 public bool is_concrete () {
 324                         switch (this) {
 325                         case DEFAULT:
 326                         case THREAD_EXIT:
 327                                 return false;
 328                         case TRY_FREE:
 329                         case FREE:
 330                         case TRY_RELEASE:
 331                         case RELEASE:
 332                                 return true;
 333                         default:
 334                                 assert_not_reached ();
 335                         }
 336                 }
 337
 338                 /**
 339                  * Checks if policy blocks or is lock-free.
 340                  * Please note that it works on a concrete policy only.
 341                  *
 342                  * @return ``true`` if the policy may block the thread.
 343                  */
 344                 public bool is_blocking () requires (this.is_concrete ()) {
 345                         switch (this) {
 346                         case TRY_FREE:
 347                         case TRY_RELEASE:
 348                                 return false;
 349                         case FREE:
 350                         case RELEASE:
 351                                 return true;
 352                         default:
 353                                 assert_not_reached ();
 354                         }
 355                 }
 356
 357                 /**
 358                  * Checks if policy guarantees freeing all elements.
 359                  * Please note that it works on a concrete policy only.
 360                  *
 361                  * @return ``true`` if the policy guarantees freeing all elements.
 362                  */
 363                 public bool is_safe () requires (this.is_concrete ()) {
 364                         switch (this) {
 365                         case TRY_FREE:
 366                         case TRY_RELEASE:
 367                                 return false;
 368                         case FREE:
 369                         case RELEASE:
 370                                 return true;
 371                         default:
 372                                 assert_not_reached ();
 373                         }
 374                 }
 375
 376                 /**
 377                  * Finds concrete policy which corresponds to given policy.
 378                  *
 379                  * @return Policy that corresponds to given policy at given time in given thread.
 380                  */
 381                 public Policy to_concrete () ensures (result.is_concrete ()) {
 382                         switch (this) {
 383                         case TRY_FREE:
 384                         case FREE:
 385                         case TRY_RELEASE:
 386                         case RELEASE:
 387                                 return this;
 388                         case DEFAULT:
 389                                 return (Policy) AtomicInt.get (ref _default_policy);
 390                         case THREAD_EXIT:
 391                                 return (Policy) AtomicInt.get (ref _thread_exit_policy);
 392                         default:
 393                                 assert_not_reached ();
 394
 395                         }
 396                 }
 397
 398                 /**
 399                  * Runs the policy.
 400                  * @param to_free List containing elements to free.
 401                  * @return Non-empty list of not freed elements or ``null`` if all elements have been disposed.
 402                  */
 403                 internal ArrayList<FreeNode *>? perform (owned ArrayList<FreeNode *> to_free) {
 404                         switch (this.to_concrete ()) {
 405                         case TRY_FREE:
 406                                 return try_free (to_free) ? (owned) to_free : null;
 407                         case FREE:
 408                                 while (try_free (to_free)) {
 409                                         Thread.yield ();
 410                                 }
 411                                 return null;
 412                         case TRY_RELEASE:
 413                                 ReleasePolicy.ensure_start ();
 414                                 if (_queue_mutex.trylock ()) {
 415                                         _queue.offer ((owned) to_free);
 416                                         _queue_mutex.unlock ();
 417                                         return null;
 418                                 } else {
 419                                         return (owned) to_free;
 420                                 }
 421                         case RELEASE:
 422                                 ReleasePolicy.ensure_start ();
 423                                 _queue_mutex.lock ();
 424                                 _queue.offer ((owned) to_free);
 425                                 _queue_mutex.unlock ();
 426                                 return null;
 427                         default:
 428                                 assert_not_reached ();
 429                         }
 430                 }
 431         }
 432
 433         public delegate void DestroyNotify (void *ptr);
 434
 435         /**
 436          * Release policy determines what happens with object freed by Policy.TRY_RELEASE
 437          * and Policy.RELEASE.
 438          */
 439         public enum ReleasePolicy {
 440                 /**
 441                  * Libgee spawns helper thread to free those elements.
 442                  * This is default.
 443                  */
 444                 HELPER_THREAD,
 445                 /**
 446                  * Libgee uses GLib main loop.
 447                  * This is recommended for application using GLib main loop.
 448                  */
 449                 MAIN_LOOP;
 450
 451                 private static void start (ReleasePolicy self) { // FIXME: Make it non-static [bug 659778]
 452                         switch (self) {
 453                         case HELPER_THREAD:
 454                                 Thread.create<bool> (() => {
 455                                         Thread.self<bool> ().set_priority (ThreadPriority.LOW);
 456                                         while (true) {
 457                                                 Thread.yield ();
 458                                                 attempt_free ();
 459                                         }
 460                                 }, false);
 461                                 break;
 462                         case MAIN_LOOP:
 463                                 Idle.add (() => {
 464                                         attempt_free ();
 465                                         return true;
 466                                 }, Priority.LOW);
 467                                 break;
 468                         default:
 469                                 assert_not_reached ();
 470                         }
 471                 }
 472
 473                 /**
 474                  * Ensures that helper methods are started.
 475                  */
 476                 internal static inline void ensure_start () {
 477                         int policy = AtomicInt.get (ref release_policy);
 478                         if ((policy & (1 << (sizeof(int) * 8 - 1))) != 0)
 479                                 return;
 480                         if (_queue_mutex.trylock ()) {
 481                                 policy = AtomicInt.get (ref release_policy);
 482                                 if ((policy & (1 << (sizeof(int) * 8 - 1))) == 0) {
 483                                         _queue = new LinkedList<ArrayList<FreeNode *>> ();
 484                                         // Hack to not lie about successfull setting policy
 485                                         policy = AtomicInt.exchange_and_add (ref release_policy, (int)(1 << (sizeof(int) * 8 - 1)));
 486                                         start ((ReleasePolicy) policy);
 487                                 }
 488                                 _queue_mutex.unlock ();
 489                         }
 490                 }
 491
 492                 private static inline void attempt_free () {
 493                         if (_queue_mutex.trylock ()) {
 494                                 Collection<ArrayList<FreeNode *>> temp = new ArrayList<ArrayList<FreeNode *>> ();
 495                                 _queue.drain (temp);
 496                                 _queue_mutex.unlock ();
 497                                 temp.foreach ((x) => {_global_to_free.add_all (x); return true;});
 498                         }
 499                         try_free (_global_to_free);
 500                 }
 501         }
 502
 503         /**
 504          * Create a new context. User does not need to create explicitly however it might be benefitial
 505          * if he is about to issue bunch of commands he might consider it benefitial to fine-tune the creation of contexts.
 506          *
 507          * {{{
 508          *   Context ctx = new Context ();
 509          *   lock_free_collection.operation1 ();
 510          *   // Normally on exit the thread exit operation would be executed but here the default operation of
 511          *   // child context is executed.
 512          *   lock_free_collection.operation2 ();
 513          * }}}
 514          *
 515          * Please note that the Context in implicitly part of stack and:
 516          *
 517          * 1. It cannot be moved between threads.
 518          * 2. If in given thread the child (created later) context is alive parent must be alive as well.
 519          */
 520         [Compact]
 521         public class Context { // FIXME: Should be struct
 522                 public Context (Policy? policy = null) {
 523                         this._to_free = new ArrayList<FreeNode *> ();
 524                         this._parent = _current_context.get ();
 525                         _current_context.set (this, null);
 526                         if (policy == null) {
 527                                 if (_parent == null) {
 528                                         _policy = (Policy)AtomicInt.get (ref _thread_exit_policy);
 529                                 } else {
 530                                         _policy = (Policy)AtomicInt.get (ref _default_policy);
 531                                 }
 532                         } else {
 533                                 this._policy = policy.to_concrete ();
 534                         }
 535 #if DEBUG
 536                         stderr.printf ("Entering context %p (policy %s, parent %p)\n", this, _policy != null ? _policy.to_string () : null, _parent);
 537 #endif
 538                 }
 539
 540                 ~Context () {
 541 #if DEBUG
 542                         stderr.printf ("Exiting context %p (policy %s, parent %p)\n", this, _policy != null ? _policy.to_string () : null, _parent);
 543 #endif
 544                         int size = _to_free.size;
 545                         bool clean_parent = false;
 546                         if (size > 0) {
 547                                 ArrayList<FreeNode *>? remaining;
 548                                 if (_parent == null || size >= THRESHOLD)
 549                                         remaining = _policy.perform ((owned) _to_free);
 550                                 else
 551                                         remaining = (owned) _to_free;
 552                                 if (remaining != null) {
 553                                         assert (_parent != null);
 554                                         _parent->_to_free.add_all (remaining);
 555                                         clean_parent = true;
 556                                 }
 557                         }
 558 #if DEBUG
 559                         stderr.printf ("Setting current context to %p\n", _parent);
 560 #endif
 561                         _current_context.set (_parent, null);
 562                         if (clean_parent)
 563                                 HazardPointer.try_free (_parent->_to_free);
 564                 }
 565
 566                 /**
 567                  * Tries to free all freed pointer in current context.
 568                  */
 569                 public void try_free () {
 570                         HazardPointer.try_free (_to_free);
 571                 }
 572
 573                 /**
 574                  * Ensure that whole context is freed. Plase note that it might block.
 575                  */
 576                 public void free_all () {
 577                         while (HazardPointer.try_free (_to_free))
 578                                 Thread.yield ();
 579                 }
 580
 581                 /**
 582                  * Tries to push the current context to releaser.
 583                  */
 584                 public void try_release () {
 585                         if (_queue_mutex.trylock ()) {
 586                                 _queue.offer ((owned) _to_free);
 587                                 _to_free = new ArrayList<FreeNode *> ();
 588                                 _queue_mutex.unlock ();
 589                         }
 590                 }
 591
 592                 /**
 593                  * Pushes the current context to releaser. Plase note that it might block.
 594                  */
 595                 public void release () {
 596                         _queue_mutex.lock ();
 597                         _queue.offer ((owned) _to_free);
 598                         _to_free = new ArrayList<FreeNode *> ();
 599                         _queue_mutex.unlock ();
 600                 }
 601
 602                 /**
 603                  * Add pointer to freed array.
 604                  */
 605                 internal inline void release_ptr (void *ptr, owned DestroyNotify notify) {
 606                         FreeNode *node = new FreeNode ();
 607                         node->pointer = ptr;
 608                         node->destroy_notify = (owned)notify;
 609                         _to_free.add (node);
 610                         if (_to_free.size >= THRESHOLD)
 611                                 HazardPointer.try_free (_to_free);
 612                 }
 613
 614                 /**
 615                  * Gets current context.
 616                  */
 617                 internal inline static Context *get_current_context () {
 618                         return _current_context.get ();
 619                 }
 620
 621                 internal Context *_parent;
 622                 internal ArrayList<FreeNode *> _to_free;
 623                 internal Policy? _policy;
 624                 internal static StaticPrivate _current_context;
 625                 internal static StaticPrivate _root_context;
 626                 private static uint THRESHOLD = 10;
 627         }
 628
 629         /**
 630          * Gets a new hazard pointer node.
 631          *
 632          * @return new hazard pointer node.
 633          */
 634         internal static inline unowned Node acquire () {
 635                 for (unowned Node? curr = get_head (); curr != null; curr = curr.get_next ())
 636                         if (curr.activate ())
 637                                 return curr;
 638                 Node *node = new Node ();
 639                 Node *old_head = null;
 640                 do {
 641                         node->set_next (old_head = (Node *)AtomicPointer.get (&_head));
 642                 } while (!AtomicPointer.compare_and_exchange (&_head, old_head, node));
 643                 return  node;
 644         }
 645
 646         /**
 647          * Tries to free from list.
 648          *
 649          * @return ``true`` if list is empty.
 650          */
 651         internal static bool try_free (ArrayList<FreeNode *> to_free) {
 652                 Collection<void *> used = new HashSet<void *>();
 653                 for (unowned Node? current = get_head (); current != null; current = current.get_next ()) {
 654                         used.add (current.get ());
 655                 }
 656                 for (int i = 0; i < to_free.size;) {
 657                         FreeNode *current = to_free[i];
 658                         if (used.contains (current->pointer)) {
 659 #if DEBUG
 660                                 stderr.printf ("Skipping freeing %p\n", current->pointer);
 661 #endif
 662                                 i++;
 663                         } else {
 664 #if DEBUG
 665                                 stderr.printf ("Freeing %p\n", current->pointer);
 666 #endif
 667                                 FreeNode *cur = to_free.remove_at (to_free.size - 1);
 668                                 if (i != to_free.size) {
 669                                         FreeNode *temp = to_free[i];
 670                                         to_free[i] = cur;
 671                                         cur = temp;
 672                                 }
 673                                 cur->destroy_notify (cur->pointer);
 674                                 delete cur;
 675                         }
 676                 }
 677                 return to_free.size > 0;
 678         }
 679
 680         /**
 681          * Gets head of hazard pointers.
 682          * @return Hazard pointer head.
 683          */
 684         internal static unowned Node? get_head () {
 685                 return (Node *)AtomicPointer.get(&_head);
 686         }
 687
 688         internal unowned Node _node;
 689
 690         internal static Node *_head = null;
 691
 692         internal static int _default_policy = (int)Policy.TRY_FREE;
 693         internal static int _thread_exit_policy = (int)Policy.RELEASE;
 694
 695         internal static int release_policy = 0;
 696
 697         internal static Queue<ArrayList<FreeNode *>> _queue;
 698         internal static StaticMutex _queue_mutex;
 699
 700         internal static ArrayList<FreeNode *> _global_to_free;
 701
 702         internal static DestroyNotify get_destroy_notify<G> () {
 703                 return (ptr) => {
 704                         G *gptr = ptr;
 705                         G obj = (owned)gptr;
 706                         obj = null;
 707                 };
 708         }
 709
 710         [Compact]
 711         internal class FreeNode {
 712                 public void *pointer;
 713                 public DestroyNotify destroy_notify;
 714         }
 715
 716         /**
 717          * List of used pointers.
 718          */
 719         [Compact]
 720         internal class Node {
 721                 public Node () {
 722                         AtomicPointer.set (&_hazard, null);
 723                         AtomicInt.set (ref _active, 1);
 724                 }
 725
 726                 inline ~Node () {
 727                         delete _next;
 728                 }
 729
 730                 public void release () {
 731                         AtomicPointer.set (&_hazard, null);
 732                         AtomicInt.set (ref _active, 0);
 733                 }
 734
 735                 public inline bool is_active () {
 736                         return AtomicInt.get (ref _active) != 0;
 737                 }
 738
 739                 public inline bool activate () {
 740                         return AtomicInt.compare_and_exchange (ref _active, 0, 1);
 741                 }
 742
 743                 public inline void set (void *ptr) {
 744                         AtomicPointer.set (&_hazard, ptr);
 745                 }
 746
 747                 public inline void *get (bool safe = true) {
 748                         if (safe) {
 749                                 return (void *)AtomicPointer.get (&_hazard);
 750                         } else {
 751                                 return (void *)_hazard;
 752                         }
 753                 }
 754
 755                 public inline unowned Node? get_next () {
 756                         return (Node *)AtomicPointer.get (&_next);
 757                 }
 758
 759                 public inline void set_next (Node *next) {
 760                         AtomicPointer.set (&_next, next);
 761                 }
 762
 763                 public Node *_next;
 764                 public int _active;
 765                 public void *_hazard;
 766         }
 767 }
 768