blacklst.c

/*
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
 *
 * 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_priv.h"

/*
 * We maintain several hash tables of hblks that have had false hits.
 * Each contains one bit per hash bucket;  If any page in the bucket
 * has had a false hit, we assume that all of them have.
 * See the definition of page_hash_table in gc_priv.h.
 * False hits from the stack(s) are much more dangerous than false hits
 * from elsewhere, since the former can pin a large object that spans the
 * block, even though it does not start on the dangerous block.
 */

/* Externally callable routines are:    */
/* - GC_add_to_black_list_normal,       */
/* - GC_add_to_black_list_stack,        */
/* - GC_promote_black_lists.            */

/* Pointers to individual tables.  We replace one table by another by   */
/* switching these pointers.                                            */

/* Nonstack false references seen at last full collection.      */
STATIC word *GC_old_normal_bl = NULL;

/* Nonstack false references seen since last full collection.   */
STATIC word *GC_incomplete_normal_bl = NULL;

STATIC word *GC_old_stack_bl = NULL;
STATIC word *GC_incomplete_stack_bl = NULL;

/* Number of bytes on stack blacklist.  */
STATIC word GC_total_stack_black_listed = 0;

GC_INNER word GC_black_list_spacing = MINHINCR * HBLKSIZE; /* initial guess */

STATIC void GC_clear_bl(word *);

GC_INNER void
GC_default_print_heap_obj_proc(ptr_t p)
{
  ptr_t base = (ptr_t)GC_base(p);
  int kind = HDR(base)->hb_obj_kind;

  GC_err_printf("object at %p of appr. %lu bytes (%s)\n", (void *)base,
                (unsigned long)GC_size(base),
                kind == PTRFREE          ? "atomic"
                : IS_UNCOLLECTABLE(kind) ? "uncollectable"
                                         : "composite");
}

GC_INNER void (*GC_print_heap_obj)(ptr_t p) = GC_default_print_heap_obj_proc;

#ifdef PRINT_BLACK_LIST
STATIC void
GC_print_blacklisted_ptr(ptr_t p, ptr_t source, const char *kind_str)
{
  ptr_t base = (ptr_t)GC_base(source);

  if (0 == base) {
    GC_err_printf("Black listing (%s) %p referenced from %p in %s\n", kind_str,
                  (void *)p, (void *)source,
                  NULL != source ? "root set" : "register");
  } else {
    /* FIXME: We can't call the debug version of GC_print_heap_obj  */
    /* (with PRINT_CALL_CHAIN) here because the allocator lock is   */
    /* held and the world is stopped.                               */
    GC_err_printf("Black listing (%s) %p referenced from %p in"
                  " object at %p of appr. %lu bytes\n",
                  kind_str, (void *)p, (void *)source, (void *)base,
                  (unsigned long)GC_size(base));
  }
}
#endif /* PRINT_BLACK_LIST */

GC_INNER void
GC_bl_init_no_interiors(void)
{
  GC_ASSERT(I_HOLD_LOCK());
  if (NULL == GC_incomplete_normal_bl) {
    GC_old_normal_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
    GC_incomplete_normal_bl
        = (word *)GC_scratch_alloc(sizeof(page_hash_table));
    if (NULL == GC_old_normal_bl || NULL == GC_incomplete_normal_bl) {
      GC_err_printf("Insufficient memory for black list\n");
      EXIT();
    }
    GC_clear_bl(GC_old_normal_bl);
    GC_clear_bl(GC_incomplete_normal_bl);
  }
}

GC_INNER void
GC_bl_init(void)
{
  GC_ASSERT(I_HOLD_LOCK());
  if (!GC_all_interior_pointers) {
    GC_bl_init_no_interiors();
  }
  GC_ASSERT(NULL == GC_old_stack_bl && NULL == GC_incomplete_stack_bl);
  GC_old_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
  GC_incomplete_stack_bl = (word *)GC_scratch_alloc(sizeof(page_hash_table));
  if (NULL == GC_old_stack_bl || NULL == GC_incomplete_stack_bl) {
    GC_err_printf("Insufficient memory for black list\n");
    EXIT();
  }
  GC_clear_bl(GC_old_stack_bl);
  GC_clear_bl(GC_incomplete_stack_bl);
}

STATIC void
GC_clear_bl(word *bl)
{
  BZERO(bl, sizeof(page_hash_table));
}

STATIC void
GC_copy_bl(const word *old, word *dest)
{
  BCOPY(old, dest, sizeof(page_hash_table));
}

static word total_stack_black_listed(void);

/* Signal the completion of a collection.  Turn the incomplete black    */
/* lists into new black lists, etc.                                     */
GC_INNER void
GC_promote_black_lists(void)
{
  word *very_old_normal_bl = GC_old_normal_bl;
  word *very_old_stack_bl = GC_old_stack_bl;

  GC_ASSERT(I_HOLD_LOCK());
  GC_old_normal_bl = GC_incomplete_normal_bl;
  GC_old_stack_bl = GC_incomplete_stack_bl;
  if (!GC_all_interior_pointers) {
    GC_clear_bl(very_old_normal_bl);
  }
  GC_clear_bl(very_old_stack_bl);
  GC_incomplete_normal_bl = very_old_normal_bl;
  GC_incomplete_stack_bl = very_old_stack_bl;
  GC_total_stack_black_listed = total_stack_black_listed();
  GC_VERBOSE_LOG_PRINTF(
      "%lu bytes in heap blacklisted for interior pointers\n",
      (unsigned long)GC_total_stack_black_listed);
  if (GC_total_stack_black_listed != 0) {
    GC_black_list_spacing
        = HBLKSIZE * (GC_heapsize / GC_total_stack_black_listed);
  }
  if (GC_black_list_spacing < 3 * HBLKSIZE) {
    GC_black_list_spacing = 3 * HBLKSIZE;
  }
  if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
    /* Make it easier to allocate really huge blocks, which         */
    /* otherwise may have problems with nonuniform blacklist        */
    /* distributions.  This way we should always succeed            */
    /* immediately after growing the heap.                          */
    GC_black_list_spacing = MAXHINCR * HBLKSIZE;
  }
}

GC_INNER void
GC_unpromote_black_lists(void)
{
  if (!GC_all_interior_pointers) {
    GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
  }
  GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
}

#if defined(PARALLEL_MARK) && defined(THREAD_SANITIZER)
#  define backlist_set_pht_entry_from_index(db, index) \
    set_pht_entry_from_index_concurrent(db, index)
#else
/* It is safe to set a bit in a blacklist even without        */
/* synchronization, the only drawback is that we might have   */
/* to redo blacklisting sometimes.                            */
#  define backlist_set_pht_entry_from_index(bl, index) \
    set_pht_entry_from_index(bl, index)
#endif

/* The argument p is not a valid pointer reference, but it falls inside */
/* the plausible heap bounds.  Add it to the normal incomplete black    */
/* list if appropriate.                                                 */
#ifdef PRINT_BLACK_LIST
GC_INNER void
GC_add_to_black_list_normal(ptr_t p, ptr_t source)
#else
GC_INNER void
GC_add_to_black_list_normal(ptr_t p)
#endif
{
#ifndef PARALLEL_MARK
  GC_ASSERT(I_HOLD_LOCK());
#endif
  if (GC_modws_valid_offsets[ADDR(p) & (sizeof(ptr_t) - 1)]) {
    size_t index = PHT_HASH(p);

    if (NULL == HDR(p) || get_pht_entry_from_index(GC_old_normal_bl, index)) {
#ifdef PRINT_BLACK_LIST
      if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
        GC_print_blacklisted_ptr(p, source, "normal");
      }
#endif
      backlist_set_pht_entry_from_index(GC_incomplete_normal_bl, index);
    } else {
      /* This is probably just an interior pointer to an allocated      */
      /* object, and is not worth black listing.                        */
    }
  }
}

/* And the same for false pointers from the stack. */
#ifdef PRINT_BLACK_LIST
GC_INNER void
GC_add_to_black_list_stack(ptr_t p, ptr_t source)
#else
GC_INNER void
GC_add_to_black_list_stack(ptr_t p)
#endif
{
  size_t index = PHT_HASH(p);

#ifndef PARALLEL_MARK
  GC_ASSERT(I_HOLD_LOCK());
#endif
  if (NULL == HDR(p) || get_pht_entry_from_index(GC_old_stack_bl, index)) {
#ifdef PRINT_BLACK_LIST
    if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
      GC_print_blacklisted_ptr(p, source, "stack");
    }
#endif
    backlist_set_pht_entry_from_index(GC_incomplete_stack_bl, index);
  }
}

/* Is the block starting at h of size len bytes black-listed?  If so,   */
/* return the address of the next plausible r such that (r,len) might   */
/* not be black-listed.  (Pointer r may not actually be in the heap.    */
/* We guarantee only that every smaller value of r after h is also      */
/* black-listed.)  If (h,len) is not, then return NULL.  Knows about    */
/* the structure of the black list hash tables.  Assumes the allocator  */
/* lock is held but no assertion about it by design.                    */
GC_API struct GC_hblk_s *GC_CALL
GC_is_black_listed(struct GC_hblk_s *h, size_t len)
{
  size_t index = PHT_HASH(h);
  size_t i, nblocks;

  if (!GC_all_interior_pointers
      && (get_pht_entry_from_index(GC_old_normal_bl, index)
          || get_pht_entry_from_index(GC_incomplete_normal_bl, index))) {
    return h + 1;
  }

  nblocks = divHBLKSZ(len);
  for (i = 0;;) {
    if (GC_old_stack_bl[divWORDSZ(index)] == 0
        && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
      /* An easy case. */
      i += CPP_WORDSZ - modWORDSZ(index);
    } else {
      if (get_pht_entry_from_index(GC_old_stack_bl, index)
          || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
        return &h[i + 1];
      }
      i++;
    }
    if (i >= nblocks)
      break;
    index = PHT_HASH(h + i);
  }
  return NULL;
}

/* Return the number of blacklisted blocks in a given range.  Used only */
/* for statistical purposes.  Looks only at the GC_incomplete_stack_bl. */
STATIC word
GC_number_stack_black_listed(struct hblk *start, struct hblk *endp1)
{
  struct hblk *h;
  word result = 0;

  for (h = start; ADDR_LT((ptr_t)h, (ptr_t)endp1); h++) {
    size_t index = PHT_HASH(h);

    if (get_pht_entry_from_index(GC_old_stack_bl, index))
      result++;
  }
  return result;
}

/* Return the total number of (stack) black-listed bytes. */
static word
total_stack_black_listed(void)
{
  size_t i;
  word total = 0;

  for (i = 0; i < GC_n_heap_sects; i++) {
    struct hblk *start = (struct hblk *)GC_heap_sects[i].hs_start;
    struct hblk *endp1 = start + divHBLKSZ(GC_heap_sects[i].hs_bytes);

    total += GC_number_stack_black_listed(start, endp1);
  }
  return total * HBLKSIZE;
}