Allocation

Functions
static __inline void *	_tm_type_alloc_node_from_free_list (tm_type *t)
	Allocates a node from at tm_type's free list.
static __inline int	_tm_type_memory_pressureQ (tm_type *t)
static __inline int	_tm_type_memory_pressureQ_2 (tm_type *t)
void *	_tm_alloc_type_inner (tm_type *t)
	Allocates a node of a given type.
void *	_tm_alloc_inner (size_t size)
	Allocates a node of a particular size.
void *	_tm_alloc_desc_inner (tm_adesc *desc)
	Allocates a node of a particular type.
void *	_tm_realloc_inner (void *oldptr, size_t size)
	Reallocates a node to a particular size.
void *	tm_alloc (size_t size)
	API: Allocate a node.
void *	tm_alloc_desc (tm_adesc *desc)
	API: Allocate a node based on a allocation descriptor.
void *	tm_realloc (void *ptr, size_t size)
	API: Reallocate a node of a givin size.
void	tm_free (void *ptr)
	API: Explicitly free a node.

---

Function Documentation

void* _tm_alloc_desc_inner

(

tm_adesc *

desc

)

Allocates a node of a particular type.

Definition at line 2109 of file tm.c.

References _tm_alloc_type_inner(), tm_data::alloc_request_size, tm_data::alloc_request_type, tm_adesc::hidden, tm_type::size, and tm.

Referenced by tm_alloc_desc().

{
  tm_type *type = (tm_type*) desc->hidden;
  tm.alloc_request_size = type->size;
  tm.alloc_request_type = type;
  return _tm_alloc_type_inner(type);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* _tm_alloc_inner

(

size_t

size

)

Allocates a node of a particular size.

Definition at line 2097 of file tm.c.

References _tm_alloc_type_inner(), tm_data::alloc_request_size, tm_data::alloc_request_type, tm, and tm_size_to_type().

Referenced by _tm_realloc_inner(), and tm_alloc().

{
  tm_type *type = tm_size_to_type(size);
  tm.alloc_request_size = size;
  tm.alloc_request_type = type;
  return _tm_alloc_type_inner(type);  
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* _tm_alloc_type_inner

(

tm_type *

t

)

Allocates a node of a given type.

Algorithm:

Depending on tm.phase, the allocator will do some other work before returning an data ptr from a tm_node:

• Unmark some allocated nodes (BLACK->ECRU).
• Scan roots (stacks or globals) for pointers to nodes.
• Scan marked nodes for pointers to other nodes (GREY->BLACK).
• Sweep some unused nodes to their free lists (ECRU->WHITE).

A node is taken from the tm_type's free list, or a new block is allocated and parcelled into the tm_type's free list.

Increment the allocation id.

Reset during tm_alloc() stats: tm_data.alloc_n.

Keep track of how many allocs since last sweep.

Assume next allocation phase will be same as current phase.

If current allocation phase is:

• tm_ALLOC: Allocate tm_ECRU nodes from tm_WHITE free lists.

If there are no free nodes for the type, Or if there are none to parcel.

• tm_UNMARK: Unmark some tm_BLACK nodes.

If all nodes are unmarked, next phase is tm_ROOT.

• tm_ROOT: scan some roots.

If tm_root_scan_full,

Scan all roots for pointers, next phase is tm_SCAN.

Otherwise, scan some roots for pointers.

If there were no roots scanned, next phase is tm_SCAN.

If scanning is complete,

If still left to scan and under pressure, scan all grey nodes.

• tm_SWEEP: reclaim any tm_ECRU nodes.

Do not remark nodes after root mutations because all newly allocated objects are marked "in use" during SWEEP. (See tm_phase_alloc).

Try to immediately sweep tm_ECRU nodes for the type request, otherwise try to immediately sweep nodes for any type.

If no tm_ECRU (unused) nodes are left to sweep,

Switch to allocating tm_ECRU nodes from free lists or from OS.

Switch to new phase.

Increment the number tm_node allocs per phase.

If a node is not available on the tm_type free list,

Attempt to parcel or allocate some nodes:

• from currently parceled block,
• a free block or,
• from new block from OS.

Return a new data ptr or 0.

Definition at line 1862 of file tm.c.

References _tm_node_parcel_or_alloc(), _tm_node_scan_all(), _tm_node_scan_some(), _tm_node_sweep_some(), _tm_node_sweep_some_for_type(), _tm_node_unmark_some(), _tm_phase_init(), _tm_root_scan_all(), _tm_root_scan_some(), _tm_type_alloc_node_from_free_list(), _tm_type_memory_pressureQ(), _tm_type_memory_pressureQ_2(), tm_data::alloc_by_phase, tm_data::alloc_id, tm_data::alloc_n, tm_data::alloc_pass, tm_data::alloc_since_sweep, tm_data::free_blocks_n, tm_type::n, tm_data::n, tm_data::next_phase, tm_type::size, tm, tm_abort(), tm_ALLOC, tm_assert, tm_B, tm_BLACK, tm_ECRU, tm_GREY, tm_msg(), tm_node_HDR_SIZE, tm_node_scan_some_size, tm_node_sweep_some_size, tm_node_unmark_some_size, tm_ptr_to_node(), tm_ROOT, tm_root_scan_full, tm_SCAN, tm_stop(), tm_SWEEP, tm_time_stat_begin(), tm_time_stat_end(), tm_TOTAL, tm_UNMARK, tm_WHITE, and tm_data::ts_phase.

Referenced by _tm_alloc_desc_inner(), and _tm_alloc_inner().

{
  void *ptr;
  int again;
#if tm_TIME_STAT
  tm_time_stat *ts;
#endif

  /*! Increment the allocation id. */
  ++ tm.alloc_id;
#if 0
  /* DEBUG DELETE ME! */
  if ( tm.alloc_id == 5040 )
    tm_stop();
#endif

  /*! Reset during tm_alloc() stats: tm_data.alloc_n. */
  tm.alloc_pass = 0;
  memset(tm.alloc_n, 0, sizeof(tm.alloc_n));

  /*! Keep track of how many allocs since last sweep. */
  ++ tm.alloc_since_sweep;

  // tm_validate_lists();

  /* Try to allocate again? */
  ++ tm.alloc_pass;

  /* BEGIN CRITICAL SECTION */

#if tm_TIME_STAT
  tm_time_stat_begin(ts = &tm.ts_phase[tm.phase]);
#endif

 again:
  again = 0;

  /*! Assume next allocation phase will be same as current phase. */
  tm.next_phase = (enum tm_phase) -1;
  
  /*! If current allocation phase is: */
  switch ( tm.phase ) {
  case tm_ALLOC:
    /*! - tm_ALLOC: Allocate tm_ECRU nodes from tm_WHITE free lists. */

    _tm_node_unmark_some(tm_node_unmark_some_size);

    /**
     * If there are no free nodes for the type,
     * Or if there are none to parcel.
     */
    if ( _tm_type_memory_pressureQ_2(t) ) {
      tm.next_phase = tm_UNMARK;
    }
    break;

  case tm_UNMARK:
    /*! - tm_UNMARK: Unmark some tm_BLACK nodes. */

    /*! If all nodes are unmarked, next phase is tm_ROOT. */
    if ( ! _tm_node_unmark_some(tm_node_unmark_some_size) ) {
      tm.next_phase = tm_ROOT;
    }

#if 0
    /**
     * Begin tm_ROOT phase immediately if memory pressure is still too high.
     */
    if ( _tm_type_memory_pressureQ(t) ) {
      tm.next_phase = tm_ROOT;
    }
#endif
    break;
    
  case tm_ROOT:
    /*! - tm_ROOT: scan some roots. */

    _tm_node_scan_some(tm_node_scan_some_size);

    /*! If tm_root_scan_full, */
    if ( tm_root_scan_full ) {
      /*! Scan all roots for pointers, next phase is tm_SCAN. */
      _tm_root_scan_all();
      tm.next_phase = tm_SCAN;
    } else {
      /*! Otherwise, scan some roots for pointers. */
      if ( ! _tm_root_scan_some() ) {
        /*! If there were no roots scanned, next phase is tm_SCAN. */
        tm.next_phase = tm_SCAN;
      }
    }
    break;
    
  case tm_SCAN:
    /* - tm_SCAN: Scan some tm_GREY nodes for internal pointers. */

    /*! If scanning is complete, */
    if ( ! _tm_node_scan_some(tm_node_scan_some_size) ) {
      /* Scan all roots once more. */
      _tm_root_scan_all();
    }

    /**
     * If still left to scan and under pressure,
     * scan all grey nodes. 
     */
    if ( tm.n[tm_GREY] && _tm_type_memory_pressureQ_2(t) ) {
      _tm_node_scan_all();
    }

    if ( ! tm.n[tm_GREY] ) {
      tm.next_phase = tm_SWEEP;
      again = 1;
    }
    break;
      
  case tm_SWEEP:
    /**
     * - tm_SWEEP: reclaim any tm_ECRU nodes.
     *
     * Do not remark nodes after root mutations
     * because all newly allocated objects are marked "in use" during SWEEP.
     * (See tm_phase_alloc).
     */

    /**
     * Try to immediately sweep tm_ECRU nodes for the type request,
     * otherwise try to immediately sweep nodes for any type.
     */
    if ( t->n[tm_TOTAL] && ! _tm_node_sweep_some_for_type(t, tm_node_sweep_some_size) ) {
      _tm_node_sweep_some(tm_node_sweep_some_size);
    }
    
    /*! If no tm_ECRU (unused) nodes are left to sweep, */
    if ( ! tm.n[tm_ECRU] ) { 
      /*! Switch to allocating tm_ECRU nodes from free lists or from OS. */
      tm.next_phase = tm_ALLOC;
    }
    break;

  default:
    tm_abort();
    break;
  }
  
  /* END CRITICAL SECTION */

  /*! Switch to new phase. */
  if ( tm.next_phase != (enum tm_phase) -1 )
    _tm_phase_init(tm.next_phase);

  if ( again )
    goto again;

  /*! Increment the number tm_node allocs per phase. */
  ++ tm.alloc_by_phase[tm.phase];

  /*! If a node is not available on the tm_type free list, */
  if ( ! (ptr = _tm_type_alloc_node_from_free_list(t)) ) {
    /**
     * Attempt to parcel or allocate some nodes:
     * - from currently parceled block, 
     * - a free block or,
     * - from new block from OS. */
    _tm_node_parcel_or_alloc(t);
    ptr = _tm_type_alloc_node_from_free_list(t);
  }

  // tm_validate_lists();

#if tm_ptr_to_node_TEST
  /* Validate tm_ptr_to_node() */
  if ( ptr ) {
    char *p = ptr;
    tm_node *n = (void*) (p - tm_node_HDR_SIZE);
    tm_assert(tm_ptr_to_node(n) == 0);
    tm_assert(tm_ptr_to_node(p) == n);
    tm_assert(tm_ptr_to_node(p + 1) == n);
    tm_assert(tm_ptr_to_node(p + t->size / 2) == n);
    tm_assert(tm_ptr_to_node(p + t->size - 1) == n);
#if tm_ptr_AT_END_IS_VALID
    tm_assert(tm_ptr_to_node(p + t->size) == n);
#else
    tm_assert(tm_ptr_to_node(p + t->size) == 0);
#endif
  }
#endif

#if tm_TIME_STAT
  tm_time_stat_end(ts);
#endif

  {
    static FILE *tm_alloc_log;
    static unsigned long log_id = 0;
    static unsigned long log_ratio = 1;

    if ( ! tm_alloc_log ) {
      tm_alloc_log = fopen("/tmp/tm_alloc.log", "w+");
      fprintf(tm_alloc_log, "#ID PTR WHITE ECRU GREY BLACK PHASE BLOCKS FREE_BLOCKS\n");
    }
    if ( tm_alloc_log ) {
      if ( log_id ++ % log_ratio == 0 ) {
        fprintf(tm_alloc_log, "%lu %lu %lu %lu %lu %lu %lu %lu %lu, %lu\n",  
                (unsigned long) tm.alloc_id,
                (unsigned long) ptr,
                (unsigned long) tm.n[tm_WHITE],
                (unsigned long) tm.n[tm_ECRU],
                (unsigned long) tm.n[tm_GREY],
                (unsigned long) tm.n[tm_BLACK],
                (unsigned long) tm.n[tm_TOTAL],
                (unsigned long) tm.phase,
                (unsigned long) tm.n[tm_B],
                (unsigned long) tm.free_blocks_n,
                0
                );
      }
      if ( log_ratio < 1000 && log_id / log_ratio > 100 ) {
        log_ratio *= 10;
      }
    }
  }

#if 0
  tm_msg("a %p[%lu]\n", ptr, (unsigned long) t->size);
#endif

  /*! Return a new data ptr or 0. */
  return (void*) ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* _tm_realloc_inner	(	void *	oldptr,
		size_t	size
	)

Reallocates a node to a particular size.

Definition at line 2121 of file tm.c.

References _tm_alloc_inner(), tm_type::size, tm_node_to_type(), tm_pure_ptr_to_node(), and tm_size_to_type().

Referenced by tm_realloc().

{
  char *ptr = 0;
  tm_type *t, *oldt;

  oldt = tm_node_to_type(tm_pure_ptr_to_node(oldptr));
  t = tm_size_to_type(size);

  if ( oldt == t ) {
    ptr = oldptr;
  } else {
    ptr = _tm_alloc_inner(size);
    memcpy(ptr, oldptr, size < oldt->size ? size : oldt->size);
  }
  
  return (void*) ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static __inline void* _tm_type_alloc_node_from_free_list

(

tm_type *

t

)

[static]

Allocates a node from at tm_type's free list.

If a tm_node is not available on the tm_type's free (tm_WHITE) list, return 0;

Otherwise,

Assert its located in a valid tm_block.

Assert that is really tm_WHITE.

Get the ptr the tm_node's data space.

Clear the data space.

Put the tm_node on the appropriate allocated list, depending on the tm.phase.

Mark the tm_node's page as used.

Keep track of allocation amounts.

Return the pointer to the data space.

Definition at line 1766 of file tm.c.

References _tm_page_mark_used(), tm_data::bytes_allocated_since_gc, tm_type::color_list, tm_data::n, tm_data::nodes_allocated_since_gc, tm_type::size, tm, tm_assert_test, tm_b, tm_list_first(), tm_msg(), tm_node_color, tm_node_set_color(), tm_node_to_block(), tm_node_to_ptr(), tm_phase_alloc, and tm_WHITE.

Referenced by _tm_alloc_type_inner().

{
  tm_node *n;
  char *ptr;

  /*! If a tm_node is not available on the tm_type's free (tm_WHITE) list, return 0; */
  if ( ! (n = tm_list_first(&t->color_list[tm_WHITE])) ) {
    return 0;
  }

  /*! Otherwise, */

  /*! Assert its located in a valid tm_block. */
  tm_assert_test(tm_node_to_block(n)->type == t);
  
  /*! Assert that is really tm_WHITE. */
  tm_assert_test(tm_node_color(n) == tm_WHITE);
  
  /*! Get the ptr the tm_node's data space. */
  ptr = tm_node_to_ptr(n);
  
  /*! Clear the data space. */
  memset(ptr, 0, t->size);
  
  /*! Put the tm_node on the appropriate allocated list, depending on the tm.phase. */
  tm_node_set_color(n, tm_node_to_block(n), tm_phase_alloc[tm.phase]);
  
  /*! Mark the tm_node's page as used. */
  _tm_page_mark_used(ptr);
  
  /*! Keep track of allocation amounts. */
  ++ tm.nodes_allocated_since_gc;
  tm.bytes_allocated_since_gc += t->size;
  tm.n[tm_b] += t->size;
  
#if 0
  tm_msg("N a n%p[%lu] t%p\n", 
         (void*) n, 
         (unsigned long) t->size,
         (void*) t);
#endif

  /*! Return the pointer to the data space. */
  return ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static __inline int _tm_type_memory_pressureQ

(

tm_type *

t

)

[static]

Definition at line 1820 of file tm.c.

References tm_data::free_blocks_n, tm_type::n, tm_type::parcel_from_block, tm, and tm_WHITE.

Referenced by _tm_alloc_type_inner(), and _tm_type_memory_pressureQ_2().

{
  return 
    (! t->n[tm_WHITE] && ! t->parcel_from_block && ! tm.free_blocks_n)
    // || ((t->n[tm_TOTAL] - t->n[tm_FREE]) > t->n[tm_TOTAL] * tm_GC_THRESHOLD)
    // || ((tm.n[tm_TOTAL] - t->n[tm_FREE]) > tm.n[tm_TOTAL] * tm_GC_THRESHOLD)
    ;
}

Here is the caller graph for this function:

static __inline int _tm_type_memory_pressureQ_2

(

tm_type *

t

)

[static]

Definition at line 1836 of file tm.c.

References _tm_type_memory_pressureQ(), tm_data::alloc_since_sweep, and tm.

Referenced by _tm_alloc_type_inner().

{
  return 
    _tm_type_memory_pressureQ(t) &&
    tm.alloc_since_sweep > 100
    ;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* tm_alloc

(

size_t

size

)

API: Allocate a node.

• Begin timing stats,
• Clear some stack words,
• Remember current stack pointer,
• Save the registers and stack pointers,
• Call "inner" routines,
• End timing stats.

Definition at line 29 of file user.c.

References _tm_alloc_inner(), _tm_clear_some_stack_words, _tm_gc_full_inner(), _tm_set_stack_ptr(), tm_data::inited, tm, tm_init(), tm_time_stat_begin(), tm_time_stat_end(), tm_data::trigger_full_gc, and tm_data::ts_alloc.

Referenced by calloc(), malloc(), and tm_realloc().

{
  void *ptr = 0;

  if ( size == 0 )
    return 0;

  if ( ! tm.inited ) {
    tm_init(0, (char***) ptr, 0);
  }

#if tm_TIME_STAT
  tm_time_stat_begin(&tm.ts_alloc);
#endif

  _tm_clear_some_stack_words();
  _tm_set_stack_ptr(&ptr);

  if ( tm.trigger_full_gc ) {
    tm.trigger_full_gc = 0;
    _tm_gc_full_inner();
  }

  ptr = _tm_alloc_inner(size);

#if tm_TIME_STAT
  tm_time_stat_end(&tm.ts_alloc);
#endif

  return ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* tm_alloc_desc

(

tm_adesc *

desc

)

API: Allocate a node based on a allocation descriptor.

• Begin timing stats,
• Clear some stack words,
• Remember current stack pointer,
• Save the registers and stack pointers,
• Call "inner" routines,
• End timing stats.

Definition at line 72 of file user.c.

References _tm_alloc_desc_inner(), _tm_clear_some_stack_words, _tm_set_stack_ptr(), tm_adesc::size, tm, tm_time_stat_begin(), tm_time_stat_end(), and tm_data::ts_alloc.

{
  void *ptr = 0;

  if ( desc == 0 || desc->size == 0 )
    return 0;

#if tm_TIME_STAT
  tm_time_stat_begin(&tm.ts_alloc);
#endif

  _tm_clear_some_stack_words();
  _tm_set_stack_ptr(&ptr);
  ptr = _tm_alloc_desc_inner(desc);

#if tm_TIME_STAT
  tm_time_stat_end(&tm.ts_alloc);
#endif

  return ptr;
}

Here is the call graph for this function:

void tm_free

(

void *

ptr

)

API: Explicitly free a node.

• Begin timing stats,
• Clear some stack words,
• Remember current stack pointer,
• Save the registers and stack pointers,
• Call "inner" routines,
• End timing stats.

Definition at line 151 of file user.c.

References _tm_clear_some_stack_words, _tm_free_inner(), _tm_set_stack_ptr(), tm_data::inited, tm, tm_init(), tm_time_stat_begin(), tm_time_stat_end(), and tm_data::ts_free.

Referenced by free(), and tm_realloc().

{
  if ( ! tm.inited ) {
    tm_init(0, (char***) ptr, 0);
  }

#if tm_TIME_STAT
  tm_time_stat_begin(&tm.ts_free);
#endif

  _tm_clear_some_stack_words();
  _tm_set_stack_ptr(&ptr);
  _tm_free_inner(ptr);

#if tm_TIME_STAT
  tm_time_stat_end(&tm.ts_free);
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* tm_realloc	(	void *	oldptr,
		size_t	size
	)

API: Reallocate a node of a givin size.

May return the same pointer, a different pointer or 0.

• Begin timing stats,
• Clear some stack words,
• Remember current stack pointer,
• Save the registers and stack pointers,
• Call "inner" routines,
• End timing stats.

Definition at line 110 of file user.c.

References _tm_clear_some_stack_words, _tm_realloc_inner(), _tm_set_stack_ptr(), tm, tm_alloc(), tm_free(), tm_time_stat_begin(), tm_time_stat_end(), and tm_data::ts_alloc.

Referenced by realloc().

{
  void *ptr = 0;

  if ( oldptr == 0 )
    return tm_alloc(size);

  if ( size == 0 ) {
    tm_free(oldptr);
    return 0;
  }

#if tm_TIME_STAT
  tm_time_stat_begin(&tm.ts_alloc);
#endif

  _tm_clear_some_stack_words();
  _tm_set_stack_ptr(&ptr);
  ptr = _tm_realloc_inner(oldptr, size);

#if tm_TIME_STAT
  tm_time_stat_end(&tm.ts_alloc);
#endif

  return ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function: