/*

 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers

 * Copyright (c) 1991-1996 by Xerox Corporation.  All rights reserved.

 * Copyright (c) 1996-1999 by Silicon Graphics.  All rights reserved.

 * Copyright (C) 2007 Free Software Foundation, Inc

 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED

 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.

 *

 * Permission is hereby granted to use or copy this program

 * for any purpose,  provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 */

#include "private/gc_pmark.h"

#ifndef GC_NO_FINALIZATION

/* Type of mark procedure used for marking from finalizable object.     */

/* This procedure normally does not mark the object, only its           */

/* descendants.                                                         */

typedef void (* finalization_mark_proc)(ptr_t /* finalizable_obj_ptr */);

#define HASH3(addr,size,log_size) \

        ((((word)(addr) >> 3) ^ ((word)(addr) >> (3 + (log_size)))) \

         & ((size) - 1))

#define HASH2(addr,log_size) HASH3(addr, (word)1 << (log_size), log_size)

struct hash_chain_entry {

    word hidden_key;

    struct hash_chain_entry * next;

};

struct disappearing_link {

    struct hash_chain_entry prolog;

#   define dl_hidden_link prolog.hidden_key

                                /* Field to be cleared.         */

#   define dl_next(x) (struct disappearing_link *)((x) -> prolog.next)

#   define dl_set_next(x, y) \

                (void)((x)->prolog.next = (struct hash_chain_entry *)(y))

    word dl_hidden_obj;         /* Pointer to object base       */

};

struct dl_hashtbl_s {

    struct disappearing_link **head;

    signed_word log_size;

    word entries;

};

STATIC struct dl_hashtbl_s GC_dl_hashtbl = {

    /* head */ NULL, /* log_size */ -1, /* entries */ 0 };

#ifndef GC_LONG_REFS_NOT_NEEDED

  STATIC struct dl_hashtbl_s GC_ll_hashtbl = { NULL, -1, 0 };

#endif

struct finalizable_object {

    struct hash_chain_entry prolog;

#   define fo_hidden_base prolog.hidden_key

                                /* Pointer to object base.      */

                                /* No longer hidden once object */

                                /* is on finalize_now queue.    */

#   define fo_next(x) (struct finalizable_object *)((x) -> prolog.next)

#   define fo_set_next(x,y) ((x)->prolog.next = (struct hash_chain_entry *)(y))

    GC_finalization_proc fo_fn; /* Finalizer.                   */

    ptr_t fo_client_data;

    word fo_object_size;        /* In bytes.                    */

    finalization_mark_proc fo_mark_proc;        /* Mark-through procedure */

};

static signed_word log_fo_table_size = -1;

STATIC struct {

  struct finalizable_object **fo_head;

  /* List of objects that should be finalized now: */

  struct finalizable_object *finalize_now;

} GC_fnlz_roots = { NULL, NULL };

GC_API void GC_CALL GC_push_finalizer_structures(void)

{

  GC_ASSERT((word)&GC_dl_hashtbl.head % sizeof(word) == 0);

  GC_ASSERT((word)&GC_fnlz_roots % sizeof(word) == 0);

# ifndef GC_LONG_REFS_NOT_NEEDED

    GC_ASSERT((word)&GC_ll_hashtbl.head % sizeof(word) == 0);

    GC_PUSH_ALL_SYM(GC_ll_hashtbl.head);

# endif

  GC_PUSH_ALL_SYM(GC_dl_hashtbl.head);

  GC_PUSH_ALL_SYM(GC_fnlz_roots);

}

/* Double the size of a hash table. *size_ptr is the log of its current */

/* size.  May be a no-op.                                               */

/* *table is a pointer to an array of hash headers.  If we succeed, we  */

/* update both *table and *log_size_ptr.  Lock is held.                 */

STATIC void GC_grow_table(struct hash_chain_entry ***table,

                          signed_word *log_size_ptr)

{

    register word i;

    register struct hash_chain_entry *p;

    signed_word log_old_size = *log_size_ptr;

    signed_word log_new_size = log_old_size + 1;

    word old_size = log_old_size == -1 ? 0 : (word)1 << log_old_size;

    word new_size = (word)1 << log_new_size;

    /* FIXME: Power of 2 size often gets rounded up to one more page. */

    struct hash_chain_entry **new_table;

    GC_ASSERT(I_HOLD_LOCK());

    new_table = (struct hash_chain_entry **)

                    GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE(

                        (size_t)new_size * sizeof(struct hash_chain_entry *),

                        NORMAL);

    if (new_table == 0) {

        if (*table == 0) {

            ABORT("Insufficient space for initial table allocation");

        } else {

            return;

        }

    }

    for (i = 0; i < old_size; i++) {

      p = (*table)[i];

      while (p != 0) {

        ptr_t real_key = GC_REVEAL_POINTER(p -> hidden_key);

        struct hash_chain_entry *next = p -> next;

        size_t new_hash = HASH3(real_key, new_size, log_new_size);

        p -> next = new_table[new_hash];

        new_table[new_hash] = p;

        p = next;

      }

    }

    *log_size_ptr = log_new_size;

    *table = new_table;

}

GC_API int GC_CALL GC_register_disappearing_link(void * * link)

{

    ptr_t base;

    base = (ptr_t)GC_base(link);

    if (base == 0)

        ABORT("Bad arg to GC_register_disappearing_link");

    return(GC_general_register_disappearing_link(link, base));

}

STATIC int GC_register_disappearing_link_inner(

                        struct dl_hashtbl_s *dl_hashtbl, void **link,

                        const void *obj, const char *tbl_log_name)

{

    struct disappearing_link *curr_dl;

    size_t index;

    struct disappearing_link * new_dl;

    DCL_LOCK_STATE;

    if (EXPECT(GC_find_leak, FALSE)) return GC_UNIMPLEMENTED;

    LOCK();

    GC_ASSERT(obj != NULL && GC_base_C(obj) == obj);

    if (dl_hashtbl -> log_size == -1

        || dl_hashtbl -> entries > ((word)1 << dl_hashtbl -> log_size)) {

        GC_grow_table((struct hash_chain_entry ***)&dl_hashtbl -> head,

                      &dl_hashtbl -> log_size);

#       ifdef LINT2

          if (dl_hashtbl->log_size < 0) ABORT("log_size is negative");

#       endif

        GC_COND_LOG_PRINTF("Grew %s table to %u entries\n", tbl_log_name,

                           1 << (unsigned)dl_hashtbl -> log_size);

    }

    index = HASH2(link, dl_hashtbl -> log_size);

    for (curr_dl = dl_hashtbl -> head[index]; curr_dl != 0;

         curr_dl = dl_next(curr_dl)) {

        if (curr_dl -> dl_hidden_link == GC_HIDE_POINTER(link)) {

            curr_dl -> dl_hidden_obj = GC_HIDE_POINTER(obj);

            UNLOCK();

            return GC_DUPLICATE;

        }

    }

    new_dl = (struct disappearing_link *)

        GC_INTERNAL_MALLOC(sizeof(struct disappearing_link),NORMAL);

    if (0 == new_dl) {

      GC_oom_func oom_fn = GC_oom_fn;

      UNLOCK();

      new_dl = (struct disappearing_link *)

                (*oom_fn)(sizeof(struct disappearing_link));

      if (0 == new_dl) {

        return GC_NO_MEMORY;

      }

      /* It's not likely we'll make it here, but ... */

      LOCK();

      /* Recalculate index since the table may grow.    */

      index = HASH2(link, dl_hashtbl -> log_size);

      /* Check again that our disappearing link not in the table. */

      for (curr_dl = dl_hashtbl -> head[index]; curr_dl != 0;

           curr_dl = dl_next(curr_dl)) {

        if (curr_dl -> dl_hidden_link == GC_HIDE_POINTER(link)) {

          curr_dl -> dl_hidden_obj = GC_HIDE_POINTER(obj);

          UNLOCK();

#         ifndef DBG_HDRS_ALL

            /* Free unused new_dl returned by GC_oom_fn() */

            GC_free((void *)new_dl);

#         endif

          return GC_DUPLICATE;

        }

      }

    }

    new_dl -> dl_hidden_obj = GC_HIDE_POINTER(obj);

    new_dl -> dl_hidden_link = GC_HIDE_POINTER(link);

    dl_set_next(new_dl, dl_hashtbl -> head[index]);

    dl_hashtbl -> head[index] = new_dl;

    dl_hashtbl -> entries++;

    UNLOCK();

    return GC_SUCCESS;

}

GC_API int GC_CALL GC_general_register_disappearing_link(void * * link,

                                                         const void * obj)

{

    if (((word)link & (ALIGNMENT-1)) != 0 || !NONNULL_ARG_NOT_NULL(link))

        ABORT("Bad arg to GC_general_register_disappearing_link");

    return GC_register_disappearing_link_inner(&GC_dl_hashtbl, link, obj,

                                               "dl");

}

#ifdef DBG_HDRS_ALL

# define FREE_DL_ENTRY(curr_dl) dl_set_next(curr_dl, NULL)

#else

# define FREE_DL_ENTRY(curr_dl) GC_free(curr_dl)

#endif

/* Unregisters given link and returns the link entry to free.   */

/* Assume the lock is held.                                     */

GC_INLINE struct disappearing_link *GC_unregister_disappearing_link_inner(

                                struct dl_hashtbl_s *dl_hashtbl, void **link)

{

    struct disappearing_link *curr_dl;

    struct disappearing_link *prev_dl = NULL;

    size_t index;

    if (dl_hashtbl->log_size == -1)

        return NULL; /* prevent integer shift by a negative amount */

    index = HASH2(link, dl_hashtbl->log_size);

    for (curr_dl = dl_hashtbl -> head[index]; curr_dl;

         curr_dl = dl_next(curr_dl)) {

        if (curr_dl -> dl_hidden_link == GC_HIDE_POINTER(link)) {

            /* Remove found entry from the table. */

            if (NULL == prev_dl) {

                dl_hashtbl -> head[index] = dl_next(curr_dl);

            } else {

                dl_set_next(prev_dl, dl_next(curr_dl));

            }

            dl_hashtbl -> entries--;

            break;

        }

        prev_dl = curr_dl;

    }

    return curr_dl;

}

GC_API int GC_CALL GC_unregister_disappearing_link(void * * link)

{

    struct disappearing_link *curr_dl;

    DCL_LOCK_STATE;

    if (((word)link & (ALIGNMENT-1)) != 0) return(0); /* Nothing to do. */

    LOCK();

    curr_dl = GC_unregister_disappearing_link_inner(&GC_dl_hashtbl, link);

    UNLOCK();

    if (NULL == curr_dl) return 0;

    FREE_DL_ENTRY(curr_dl);

    return 1;

}

/* Toggle-ref support.  */

#ifndef GC_TOGGLE_REFS_NOT_NEEDED

  typedef union {

    /* Lowest bit is used to distinguish between choices.       */

    void *strong_ref;

    GC_hidden_pointer weak_ref;

  } GCToggleRef;

  STATIC GC_toggleref_func GC_toggleref_callback = 0;

  STATIC GCToggleRef *GC_toggleref_arr = NULL;

  STATIC int GC_toggleref_array_size = 0;

  STATIC int GC_toggleref_array_capacity = 0;

  GC_INNER void GC_process_togglerefs(void)

  {

    int i;

    int new_size = 0;

    GC_ASSERT(I_HOLD_LOCK());

    for (i = 0; i < GC_toggleref_array_size; ++i) {

      GCToggleRef r = GC_toggleref_arr[i];

      void *obj = r.strong_ref;

      if (((word)obj & 1) != 0) {

        obj = GC_REVEAL_POINTER(r.weak_ref);

      }

      if (NULL == obj) {

        continue;

      }

      switch (GC_toggleref_callback(obj)) {

      case GC_TOGGLE_REF_DROP:

        break;

      case GC_TOGGLE_REF_STRONG:

        GC_toggleref_arr[new_size++].strong_ref = obj;

        break;

      case GC_TOGGLE_REF_WEAK:

        GC_toggleref_arr[new_size++].weak_ref = GC_HIDE_POINTER(obj);

        break;

      default:

        ABORT("Bad toggle-ref status returned by callback");

      }

    }

    if (new_size < GC_toggleref_array_size) {

      BZERO(&GC_toggleref_arr[new_size],

            (GC_toggleref_array_size - new_size) * sizeof(GCToggleRef));

      GC_toggleref_array_size = new_size;

    }

  }

  STATIC void GC_normal_finalize_mark_proc(ptr_t);

  static void push_and_mark_object(void *p)

  {

    GC_normal_finalize_mark_proc(p);

    while (!GC_mark_stack_empty()) {

      MARK_FROM_MARK_STACK();

    }

    GC_set_mark_bit(p);

    if (GC_mark_state != MS_NONE) {

      while (!GC_mark_some(0)) {

        /* Empty. */

      }

    }

  }

  STATIC void GC_mark_togglerefs(void)

  {

    int i;

    if (NULL == GC_toggleref_arr)

      return;

    /* TODO: Hide GC_toggleref_arr to avoid its marking from roots. */

    GC_set_mark_bit(GC_toggleref_arr);

    for (i = 0; i < GC_toggleref_array_size; ++i) {

      void *obj = GC_toggleref_arr[i].strong_ref;

      if (obj != NULL && ((word)obj & 1) == 0) {

        push_and_mark_object(obj);

      }

    }

  }

  STATIC void GC_clear_togglerefs(void)

  {

    int i;

    for (i = 0; i < GC_toggleref_array_size; ++i) {

      if ((GC_toggleref_arr[i].weak_ref & 1) != 0) {

        if (!GC_is_marked(GC_REVEAL_POINTER(GC_toggleref_arr[i].weak_ref))) {

          GC_toggleref_arr[i].weak_ref = 0;

        } else {

          /* No need to copy, BDWGC is a non-moving collector.    */

        }

      }

    }

  }

  GC_API void GC_CALL GC_set_toggleref_func(GC_toggleref_func fn)

  {

    DCL_LOCK_STATE;

    LOCK();

    GC_toggleref_callback = fn;

    UNLOCK();

  }

  GC_API GC_toggleref_func GC_CALL GC_get_toggleref_func(void)

  {

    GC_toggleref_func fn;

    DCL_LOCK_STATE;

    LOCK();

    fn = GC_toggleref_callback;

    UNLOCK();

    return fn;

  }

  static GC_bool ensure_toggleref_capacity(int capacity_inc)

  {

    GC_ASSERT(capacity_inc >= 0);

    if (NULL == GC_toggleref_arr) {

      GC_toggleref_array_capacity = 32; /* initial capacity */

      GC_toggleref_arr = GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE(

                        GC_toggleref_array_capacity * sizeof(GCToggleRef),

                        NORMAL);

      if (NULL == GC_toggleref_arr)

        return FALSE;

    }

    if ((unsigned)GC_toggleref_array_size + (unsigned)capacity_inc

        >= (unsigned)GC_toggleref_array_capacity) {

      GCToggleRef *new_array;

      while ((unsigned)GC_toggleref_array_capacity

              < (unsigned)GC_toggleref_array_size + (unsigned)capacity_inc) {

        GC_toggleref_array_capacity *= 2;

        if (GC_toggleref_array_capacity < 0) /* overflow */

          return FALSE;

      }

      new_array = GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE(

                        GC_toggleref_array_capacity * sizeof(GCToggleRef),

                        NORMAL);

      if (NULL == new_array)

        return FALSE;

      BCOPY(GC_toggleref_arr, new_array,

            GC_toggleref_array_size * sizeof(GCToggleRef));

      GC_INTERNAL_FREE(GC_toggleref_arr);

      GC_toggleref_arr = new_array;

    }

    return TRUE;

  }

  GC_API int GC_CALL GC_toggleref_add(void *obj, int is_strong_ref)

  {

    int res = GC_SUCCESS;

    DCL_LOCK_STATE;

    GC_ASSERT(NONNULL_ARG_NOT_NULL(obj));

    LOCK();

    if (GC_toggleref_callback != 0) {

      if (!ensure_toggleref_capacity(1)) {

        res = GC_NO_MEMORY;

      } else {

        GC_toggleref_arr[GC_toggleref_array_size++].strong_ref =

                        is_strong_ref ? obj : (void *)GC_HIDE_POINTER(obj);

      }

    }

    UNLOCK();

    return res;

  }

#endif /* !GC_TOGGLE_REFS_NOT_NEEDED */

/* Finalizer callback support. */

STATIC GC_await_finalize_proc GC_object_finalized_proc = 0;

GC_API void GC_CALL GC_set_await_finalize_proc(GC_await_finalize_proc fn)

{

  DCL_LOCK_STATE;

  LOCK();

  GC_object_finalized_proc = fn;

  UNLOCK();

}

GC_API GC_await_finalize_proc GC_CALL GC_get_await_finalize_proc(void)

{

  GC_await_finalize_proc fn;

  DCL_LOCK_STATE;

  LOCK();

  fn = GC_object_finalized_proc;

  UNLOCK();

  return fn;

}

#ifndef GC_LONG_REFS_NOT_NEEDED

  GC_API int GC_CALL GC_register_long_link(void * * link, const void * obj)

  {

    if (((word)link & (ALIGNMENT-1)) != 0 || !NONNULL_ARG_NOT_NULL(link))

        ABORT("Bad arg to GC_register_long_link");

    return GC_register_disappearing_link_inner(&GC_ll_hashtbl, link, obj,

                                               "long dl");

  }

  GC_API int GC_CALL GC_unregister_long_link(void * * link)

  {

    struct disappearing_link *curr_dl;

    DCL_LOCK_STATE;

    if (((word)link & (ALIGNMENT-1)) != 0) return(0); /* Nothing to do. */

    LOCK();

    curr_dl = GC_unregister_disappearing_link_inner(&GC_ll_hashtbl, link);

    UNLOCK();

    if (NULL == curr_dl) return 0;

    FREE_DL_ENTRY(curr_dl);

    return 1;

  }

#endif /* !GC_LONG_REFS_NOT_NEEDED */

#ifndef GC_MOVE_DISAPPEARING_LINK_NOT_NEEDED

  /* Moves a link.  Assume the lock is held.    */

  STATIC int GC_move_disappearing_link_inner(

                                struct dl_hashtbl_s *dl_hashtbl,

                                void **link, void **new_link)

  {

    struct disappearing_link *curr_dl, *prev_dl, *new_dl;

    size_t curr_index, new_index;

    word curr_hidden_link;

    word new_hidden_link;

    if (dl_hashtbl->log_size == -1)

        return GC_NOT_FOUND; /* prevent integer shift by a negative amount */

    /* Find current link.       */

    curr_index = HASH2(link, dl_hashtbl -> log_size);

    curr_hidden_link = GC_HIDE_POINTER(link);

    prev_dl = NULL;

    for (curr_dl = dl_hashtbl -> head[curr_index]; curr_dl;

         curr_dl = dl_next(curr_dl)) {

      if (curr_dl -> dl_hidden_link == curr_hidden_link)

        break;

      prev_dl = curr_dl;

    }

    if (NULL == curr_dl) {

      return GC_NOT_FOUND;

    }

    if (link == new_link) {

      return GC_SUCCESS; /* Nothing to do.      */

    }

    /* link found; now check new_link not present.      */

    new_index = HASH2(new_link, dl_hashtbl -> log_size);

    new_hidden_link = GC_HIDE_POINTER(new_link);

    for (new_dl = dl_hashtbl -> head[new_index]; new_dl;

         new_dl = dl_next(new_dl)) {

      if (new_dl -> dl_hidden_link == new_hidden_link) {

        /* Target already registered; bail.     */

        return GC_DUPLICATE;

      }

    }

    /* Remove from old, add to new, update link.        */

    if (NULL == prev_dl) {

      dl_hashtbl -> head[curr_index] = dl_next(curr_dl);

    } else {

      dl_set_next(prev_dl, dl_next(curr_dl));

    }

    curr_dl -> dl_hidden_link = new_hidden_link;

    dl_set_next(curr_dl, dl_hashtbl -> head[new_index]);

    dl_hashtbl -> head[new_index] = curr_dl;

    return GC_SUCCESS;

  }

  GC_API int GC_CALL GC_move_disappearing_link(void **link, void **new_link)

  {

    int result;

    DCL_LOCK_STATE;

    if (((word)new_link & (ALIGNMENT-1)) != 0

        || !NONNULL_ARG_NOT_NULL(new_link))

      ABORT("Bad new_link arg to GC_move_disappearing_link");

    if (((word)link & (ALIGNMENT-1)) != 0)

      return GC_NOT_FOUND; /* Nothing to do. */

    LOCK();

    result = GC_move_disappearing_link_inner(&GC_dl_hashtbl, link, new_link);

    UNLOCK();

    return result;

  }

# ifndef GC_LONG_REFS_NOT_NEEDED

    GC_API int GC_CALL GC_move_long_link(void **link, void **new_link)

    {

      int result;

      DCL_LOCK_STATE;

      if (((word)new_link & (ALIGNMENT-1)) != 0

          || !NONNULL_ARG_NOT_NULL(new_link))

        ABORT("Bad new_link arg to GC_move_long_link");

      if (((word)link & (ALIGNMENT-1)) != 0)

        return GC_NOT_FOUND; /* Nothing to do. */

      LOCK();

      result = GC_move_disappearing_link_inner(&GC_ll_hashtbl, link, new_link);

      UNLOCK();

      return result;

    }

# endif /* !GC_LONG_REFS_NOT_NEEDED */

#endif /* !GC_MOVE_DISAPPEARING_LINK_NOT_NEEDED */

/* Possible finalization_marker procedures.  Note that mark stack       */

/* overflow is handled by the caller, and is not a disaster.            */

STATIC void GC_normal_finalize_mark_proc(ptr_t p)

{

    hdr * hhdr = HDR(p);

    PUSH_OBJ(p, hhdr, GC_mark_stack_top,

             &(GC_mark_stack[GC_mark_stack_size]));

}

/* This only pays very partial attention to the mark descriptor.        */

/* It does the right thing for normal and atomic objects, and treats    */

/* most others as normal.                                               */

STATIC void GC_ignore_self_finalize_mark_proc(ptr_t p)

{

    hdr * hhdr = HDR(p);

    word descr = hhdr -> hb_descr;

    ptr_t q;

    ptr_t scan_limit;

    ptr_t target_limit = p + hhdr -> hb_sz - 1;

    if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) {

       scan_limit = p + descr - sizeof(word);

    } else {

       scan_limit = target_limit + 1 - sizeof(word);

    }

    for (q = p; (word)q <= (word)scan_limit; q += ALIGNMENT) {

        word r = *(word *)q;

        if (r < (word)p || r > (word)target_limit) {

            GC_PUSH_ONE_HEAP(r, q, GC_mark_stack_top);

        }

    }

}

STATIC void GC_null_finalize_mark_proc(ptr_t p GC_ATTR_UNUSED) {}

/* Possible finalization_marker procedures.  Note that mark stack       */

/* overflow is handled by the caller, and is not a disaster.            */

/* GC_unreachable_finalize_mark_proc is an alias for normal marking,    */

/* but it is explicitly tested for, and triggers different              */

/* behavior.  Objects registered in this way are not finalized          */

/* if they are reachable by other finalizable objects, even if those    */

/* other objects specify no ordering.                                   */

STATIC void GC_unreachable_finalize_mark_proc(ptr_t p)

{

    GC_normal_finalize_mark_proc(p);

}

/* Register a finalization function.  See gc.h for details.     */

/* The last parameter is a procedure that determines            */

/* marking for finalization ordering.  Any objects marked       */

/* by that procedure will be guaranteed to not have been        */

/* finalized when this finalizer is invoked.                    */

STATIC void GC_register_finalizer_inner(void * obj,

                                        GC_finalization_proc fn, void *cd,

                                        GC_finalization_proc *ofn, void **ocd,

                                        finalization_mark_proc mp)

{

    struct finalizable_object * curr_fo;

    size_t index;

    struct finalizable_object *new_fo = 0;

    hdr *hhdr = NULL; /* initialized to prevent warning. */

    DCL_LOCK_STATE;

    if (EXPECT(GC_find_leak, FALSE)) return;

    LOCK();

    if (log_fo_table_size == -1

        || GC_fo_entries > ((word)1 << log_fo_table_size)) {

        GC_grow_table((struct hash_chain_entry ***)&GC_fnlz_roots.fo_head,

                      &log_fo_table_size);

#       ifdef LINT2

          if (log_fo_table_size < 0) ABORT("log_size is negative");

#       endif

        GC_COND_LOG_PRINTF("Grew fo table to %u entries\n",

                           1 << (unsigned)log_fo_table_size);

    }

    /* in the THREADS case we hold allocation lock.             */

    for (;;) {

      struct finalizable_object *prev_fo = NULL;

      GC_oom_func oom_fn;

      index = HASH2(obj, log_fo_table_size);

      curr_fo = GC_fnlz_roots.fo_head[index];

      while (curr_fo != 0) {

        GC_ASSERT(GC_size(curr_fo) >= sizeof(struct finalizable_object));

        if (curr_fo -> fo_hidden_base == GC_HIDE_POINTER(obj)) {

          /* Interruption by a signal in the middle of this     */

          /* should be safe.  The client may see only *ocd      */

          /* updated, but we'll declare that to be his problem. */

          if (ocd) *ocd = (void *) (curr_fo -> fo_client_data);

          if (ofn) *ofn = curr_fo -> fo_fn;

          /* Delete the structure for obj.      */

          if (prev_fo == 0) {

            GC_fnlz_roots.fo_head[index] = fo_next(curr_fo);

          } else {

            fo_set_next(prev_fo, fo_next(curr_fo));

          }

          if (fn == 0) {

            GC_fo_entries--;

            /* May not happen if we get a signal.  But a high   */

            /* estimate will only make the table larger than    */

            /* necessary.                                       */

#           if !defined(THREADS) && !defined(DBG_HDRS_ALL)

              GC_free((void *)curr_fo);

#           endif

          } else {

            curr_fo -> fo_fn = fn;

            curr_fo -> fo_client_data = (ptr_t)cd;

            curr_fo -> fo_mark_proc = mp;

            /* Reinsert it.  We deleted it first to maintain    */

            /* consistency in the event of a signal.            */

            if (prev_fo == 0) {

              GC_fnlz_roots.fo_head[index] = curr_fo;

            } else {

              fo_set_next(prev_fo, curr_fo);

            }

          }

          UNLOCK();

#         ifndef DBG_HDRS_ALL

            if (EXPECT(new_fo != 0, FALSE)) {

              /* Free unused new_fo returned by GC_oom_fn() */

              GC_free((void *)new_fo);

            }

#         endif

          return;

        }

        prev_fo = curr_fo;

        curr_fo = fo_next(curr_fo);

      }

      if (EXPECT(new_fo != 0, FALSE)) {

        /* new_fo is returned by GC_oom_fn().   */

        GC_ASSERT(fn != 0);

#       ifdef LINT2

          if (NULL == hhdr) ABORT("Bad hhdr in GC_register_finalizer_inner");

#       endif

        break;

      }

      if (fn == 0) {

        if (ocd) *ocd = 0;

        if (ofn) *ofn = 0;

        UNLOCK();

        return;

      }

      GET_HDR(obj, hhdr);

      if (EXPECT(0 == hhdr, FALSE)) {

        /* We won't collect it, hence finalizer wouldn't be run. */

        if (ocd) *ocd = 0;

        if (ofn) *ofn = 0;

        UNLOCK();

        return;

      }

      new_fo = (struct finalizable_object *)

        GC_INTERNAL_MALLOC(sizeof(struct finalizable_object),NORMAL);

      if (EXPECT(new_fo != 0, TRUE))

        break;

      oom_fn = GC_oom_fn;

      UNLOCK();

      new_fo = (struct finalizable_object *)

                (*oom_fn)(sizeof(struct finalizable_object));

      if (0 == new_fo) {

        /* No enough memory.  *ocd and *ofn remains unchanged.  */

        return;

      }

      /* It's not likely we'll make it here, but ... */

      LOCK();

      /* Recalculate index since the table may grow and         */

      /* check again that our finalizer is not in the table.    */

    }

    GC_ASSERT(GC_size(new_fo) >= sizeof(struct finalizable_object));

    if (ocd) *ocd = 0;

    if (ofn) *ofn = 0;

    new_fo -> fo_hidden_base = GC_HIDE_POINTER(obj);

    new_fo -> fo_fn = fn;

    new_fo -> fo_client_data = (ptr_t)cd;

    new_fo -> fo_object_size = hhdr -> hb_sz;

    new_fo -> fo_mark_proc = mp;

    fo_set_next(new_fo, GC_fnlz_roots.fo_head[index]);

    GC_fo_entries++;

    GC_fnlz_roots.fo_head[index] = new_fo;

    UNLOCK();

}

GC_API void GC_CALL GC_register_finalizer(void * obj,

                                  GC_finalization_proc fn, void * cd,

                                  GC_finalization_proc *ofn, void ** ocd)

{

    GC_register_finalizer_inner(obj, fn, cd, ofn,

                                ocd, GC_normal_finalize_mark_proc);

}

GC_API void GC_CALL GC_register_finalizer_ignore_self(void * obj,

                               GC_finalization_proc fn, void * cd,

                               GC_finalization_proc *ofn, void ** ocd)

{

    GC_register_finalizer_inner(obj, fn, cd, ofn,

                                ocd, GC_ignore_self_finalize_mark_proc);

}

GC_API void GC_CALL GC_register_finalizer_no_order(void * obj,

                               GC_finalization_proc fn, void * cd,

                               GC_finalization_proc *ofn, void ** ocd)

{

    GC_register_finalizer_inner(obj, fn, cd, ofn,

                                ocd, GC_null_finalize_mark_proc);

}

static GC_bool need_unreachable_finalization = FALSE;

        /* Avoid the work if this isn't used.   */

GC_API void GC_CALL GC_register_finalizer_unreachable(void * obj,

                               GC_finalization_proc fn, void * cd,

                               GC_finalization_proc *ofn, void ** ocd)

{

    need_unreachable_finalization = TRUE;

    GC_ASSERT(GC_java_finalization);

    GC_register_finalizer_inner(obj, fn, cd, ofn,

                                ocd, GC_unreachable_finalize_mark_proc);

}

#ifndef NO_DEBUGGING

  STATIC void GC_dump_finalization_links(

                                const struct dl_hashtbl_s *dl_hashtbl)

  {

    size_t dl_size = dl_hashtbl->log_size == -1 ? 0 :

                                (size_t)1 << dl_hashtbl->log_size;

    size_t i;

    for (i = 0; i < dl_size; i++) {

      struct disappearing_link *curr_dl;

      for (curr_dl = dl_hashtbl -> head[i]; curr_dl != 0;

           curr_dl = dl_next(curr_dl)) {

        ptr_t real_ptr = GC_REVEAL_POINTER(curr_dl -> dl_hidden_obj);

        ptr_t real_link = GC_REVEAL_POINTER(curr_dl -> dl_hidden_link);

        GC_printf("Object: %p, link: %p\n",

                  (void *)real_ptr, (void *)real_link);

      }

    }

  }

  GC_API void GC_CALL GC_dump_finalization(void)

  {

    struct finalizable_object * curr_fo;

    size_t fo_size = log_fo_table_size == -1 ? 0 :

                                (size_t)1 << log_fo_table_size;

    size_t i;

    GC_printf("Disappearing (short) links:\n");

    GC_dump_finalization_links(&GC_dl_hashtbl);

#   ifndef GC_LONG_REFS_NOT_NEEDED

      GC_printf("Disappearing long links:\n");

      GC_dump_finalization_links(&GC_ll_hashtbl);

#   endif

    GC_printf("Finalizers:\n");

    for (i = 0; i < fo_size; i++) {

      for (curr_fo = GC_fnlz_roots.fo_head[i];

           curr_fo != NULL; curr_fo = fo_next(curr_fo)) {

        ptr_t real_ptr = GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);

        GC_printf("Finalizable object: %p\n", (void *)real_ptr);

      }

    }

  }

#endif /* !NO_DEBUGGING */

#ifndef SMALL_CONFIG

  STATIC word GC_old_dl_entries = 0; /* for stats printing */

# ifndef GC_LONG_REFS_NOT_NEEDED

    STATIC word GC_old_ll_entries = 0;

# endif

#endif /* !SMALL_CONFIG */

#ifndef THREADS

  /* Global variables to minimize the level of recursion when a client  */

  /* finalizer allocates memory.                                        */

  STATIC int GC_finalizer_nested = 0;

                        /* Only the lowest byte is used, the rest is    */

                        /* padding for proper global data alignment     */

                        /* required for some compilers (like Watcom).   */

  STATIC unsigned GC_finalizer_skipped = 0;

  /* Checks and updates the level of finalizers recursion.              */

  /* Returns NULL if GC_invoke_finalizers() should not be called by the */

  /* collector (to minimize the risk of a deep finalizers recursion),   */

  /* otherwise returns a pointer to GC_finalizer_nested.                */

  STATIC unsigned char *GC_check_finalizer_nested(void)

  {

    unsigned nesting_level = *(unsigned char *)&GC_finalizer_nested;

    if (nesting_level) {

      /* We are inside another GC_invoke_finalizers().          */

      /* Skip some implicitly-called GC_invoke_finalizers()     */

      /* depending on the nesting (recursion) level.            */

      if (++GC_finalizer_skipped < (1U << nesting_level)) return NULL;