polar-runtime-memory-pool.c

/* Internal API: internal memory pool for polar-objc.
   Copyright (C) 2022-2025 Michael Malicoat <[email protected]>
 
   This file is part of polar-objc.
 
   polar-objc is free software; you can redistribute it and/or modify it under the terms of the GNU General Public
   License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
 
   polar-objc is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
   warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
   details.
 
   You should have received a copy of the GNU General Public License along with this program; see the file LICENSE.  If
   not, see <http://www.gnu.org/licenses/>.
*/
// polar_runtime_memory_pool *******************************************************************************************
// Private =============================================================================================================
 
// This variable is initialized in polar_runtime_memory_pool_get_type()
static polar_runtime_memory_pool_class class_polar_runtime_memory_pool;
 
// This variable is initialized in _polar_runtime_memory_pool_class_init()
static polar_runtime_object_class *superclass_polar_runtime_memory_pool = NULL;
 
// ---------------------------------------------------------------------------------------------------------------------
 
// This works out to 32K on 64-bit systems and 16K on 32-bit systems
#define POLAR_SIZE_RUNTIME_MEMORY_POOL_PAGE ( OBJC_SIZEOF_POINTER << 12 )
#define POLAR_COUNT_RUNTIME_MEMORY_TUNE_MISSES_START 1
#define POLAR_COUNT_BUCKETS_TABLE_STRINGS_INTERNED 4
 
// Assumes the pool lock is held by the caller!
static inline void *
polar_runtime_memory_pool_block_idle_pop( polar_runtime_memory_pool *self, intptr_t idx_idle_list )
{
  void *result;
 
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
  assert( idx_idle_list > 0 );
  assert( idx_idle_list <= POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE );
 
  result = self->array_idle_blocks[idx_idle_list].block_last;
  if( result != NULL )
  {
    self->array_idle_blocks[idx_idle_list].block_last = *( (void **)result );
    *( (void **)result ) = NULL;
 
  #ifdef POLAR_DEBUG_RUNTIME_MEMORY
    self->array_idle_blocks[idx_idle_list].count_blocks_idle--;
  #endif // POLAR_DEBUG_RUNTIME_MEMORY
  }
 
  return result;
}
 
// Assumes the pool lock is held by the caller!
static inline void
polar_runtime_memory_pool_block_idle_push( polar_runtime_memory_pool *self, intptr_t idx_idle_list,
                                           void *block_new )
{
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
  assert( idx_idle_list > 0 );
  assert( idx_idle_list <= POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE );
  assert( block_new != NULL );
  assert( *((void **)block_new) == NULL ); // The memory should be zeroed before it is discarded
 
  *( (void **)block_new ) = self->array_idle_blocks[idx_idle_list].block_last;
  self->array_idle_blocks[idx_idle_list].block_last = block_new;
 
#ifdef POLAR_DEBUG_RUNTIME_MEMORY
  self->array_idle_blocks[idx_idle_list].count_blocks_idle++;
#endif // POLAR_DEBUG_RUNTIME_MEMORY
}
 
// Assumes the pool lock is held by the caller!
POLAR_FUNCTION_INTERNAL uintptr_t
polar_runtime_memory_pool_block_idle_push_list( polar_runtime_memory_pool *self, intptr_t idx_idle_list,
                                                void **block_first )
{
  uintptr_t result;
  void *block_current, *block_next;
 
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
  assert( idx_idle_list > 0 );
  assert( idx_idle_list <= POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE );
  assert( block_first != NULL );
 
  result = 0;
 
  // Find the end of the linked list
  block_next = block_first;
 
  do
  {
    block_current = block_next;
    result++;
 
    block_next = *( (void **)block_current );
  } while( block_next != NULL );
 
  // Push the entire chain of nodes at once
  *( (void **)block_current ) = self->array_idle_blocks[idx_idle_list].block_last;
  self->array_idle_blocks[idx_idle_list].block_last = block_first;
 
#ifdef POLAR_DEBUG_RUNTIME_MEMORY
  self->array_idle_blocks[idx_idle_list].count_blocks_idle += result;
#endif // POLAR_DEBUG_RUNTIME_MEMORY
 
  return result;
}
 
// Called by _polar_thread_data_finalize()
POLAR_FUNCTION_INTERNAL void
polar_runtime_memory_pool_return_thread_memory( polar_runtime_memory_pool *self, void **array_idle_blocks )
{
  intptr_t i;
  uintptr_t count_blocks_returned;
 
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
  assert( array_idle_blocks != NULL );
 
  for( i = 1; i <= POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE; i++ )
  {
    if( array_idle_blocks[i] != NULL )
    {
      mtx_lock( &self->pool_lock );
        count_blocks_returned = polar_runtime_memory_pool_block_idle_push_list( self, i, array_idle_blocks[i] );
 
        // Reset the count of misses for this block size
        objc_atomic_subtract_uintptr( &self->array_idle_blocks[i].count_misses, count_blocks_returned );
      mtx_unlock( &self->pool_lock );
    }
  }
}
 
// This is called in the context of polar_memory_disposal_thread()
POLAR_FUNCTION_INTERNAL void
polar_runtime_memory_pool_tune( polar_runtime_memory_pool *self )
{
  polar_memory_pool_class *superclass;
  intptr_t i;
  uintptr_t count_misses_max, count_misses_current;
  size_t size_block, size_chain;
  char *block_first, *block_last, *block_current;
 
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
 
  superclass = POLAR_MEMORY_POOL_CLASS(superclass_polar_runtime_memory_pool);
  count_misses_max = POLAR_COUNT_RUNTIME_MEMORY_TUNE_MISSES_START;
 
  /* Here we preallocate additional structures based on how often an idle structure of a given size was sought by the
     runtime when none were available.  The idea is to speed up allocation from the pool by having preallocated
     structures ready to go.
  */
  for( i = POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE; i > 0; i-- )
  {
    count_misses_current = objc_atomic_exchange_uintptr( &self->array_idle_blocks[i].count_misses, 0 );
 
    if( count_misses_current >= count_misses_max )
    {
      // We preallocate half as many blocks as were most recently requested and not available
      count_misses_current = MAX(count_misses_current >> 1, 1);
 
      if( count_misses_current > 1 )
      {
        /* We preallocate an entire chain of blocks at once and then fix up the resulting linked list so it can all be
           pushed at once onto the appropriate idle list
        */
 
        size_block = ( i << X2_SIZE_SHIFT_POINTER );
        size_chain = ( size_block * count_misses_current );
 
        mtx_lock( &self->pool_lock );
          block_first = (char *)
            superclass->allocate_elements( (polar_memory_pool *)self, (i << 1) * count_misses_current );
        mtx_unlock( &self->pool_lock );
 
        block_last = ( (block_first + size_chain) - size_block );
        block_current = block_first;
 
        while( block_current != block_last )
        {
          // Point this block at the one that immediately follows it
          *( (void **)block_current ) = ( block_current + size_block );
          block_current += size_block;
        }
 
        // Push the entire chain of newly-allocated blocks onto the appropriate idle list
        mtx_lock( &self->pool_lock );
          *( (void **)block_last ) = self->array_idle_blocks[i].block_last;
          self->array_idle_blocks[i].block_last = block_first;
 
      #ifdef POLAR_DEBUG_RUNTIME_MEMORY
          self->array_idle_blocks[i].count_blocks_idle += count_misses_current;
          self->array_idle_blocks[i].count_blocks_allocated += count_misses_current;
      #endif // POLAR_DEBUG_RUNTIME_MEMORY
 
        mtx_unlock( &self->pool_lock );
      }
 
      else
      {
        mtx_lock( &self->pool_lock );
          block_current = (char *)superclass->allocate_elements( (polar_memory_pool *)self, i << 1 );
          polar_runtime_memory_pool_block_idle_push(self, i, block_current);
        mtx_unlock( &self->pool_lock );
      }
    }
 
    /* The idea here is to start with a low threshold when preallocating larger block sizes, and then raise the
       threshold as we get into smaller block sizes.  We do this because we fragment larger blocks to make smaller
       blocks, as needed; but we do not recombine smaller blocks to make larger blocks.  There must therefore be a
       strong demand for smaller blocks, indicated by a number of misses, before we preallocate any.
    */
    if( (i & (i - 1)) == 0 )
      count_misses_max <<= 1;
  }
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
POLAR_FUNCTION_INTERNAL polar_runtime_memory_pool *
_polar_runtime_memory_pool_init( polar_runtime_memory_pool *self )
{
  size_t size_array_idle_blocks;
 
  // Chain up first
  self = (polar_runtime_memory_pool *)
    POLAR_RUNTIME_OBJECT_CLASS(superclass_polar_runtime_memory_pool)->init( (polar_runtime_object *)self );
 
  if( self != NULL )
  {
    if( mtx_init(&self->pool_lock, mtx_recursive) == 0 )
      ;
 
    else
    {
      polar_runtime_object_free( (polar_runtime_object *)self );
      return NULL;
    }
 
    self->data_inherited.size_pool_elements = OBJC_SIZEOF_POINTER;
    
    /* Allocate the array of idle blocks from the memory pool itself.  Note that we will never use array index 0, so
       we save some space by ignoring it in our allocation request, and then adjusting our pointer afterward.
    */
 
    size_array_idle_blocks = ( sizeof(struct polar_list_memory_block_idle) * POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE );
 
    self->array_idle_blocks = (struct polar_list_memory_block_idle *)
      polar_memory_pool_page_sbrk( (polar_memory_pool_page *)self, size_array_idle_blocks );
 
    self->array_idle_blocks = &self->array_idle_blocks[-1];
  }
 
  return self;
}
 
POLAR_FUNCTION_INTERNAL polar_runtime_object *
_polar_runtime_memory_pool_finalize( polar_runtime_memory_pool *self )
{
  if( self->array_idle_blocks != NULL )
  {
    mtx_destroy( &self->pool_lock );
    objc_memzero( &self->pool_lock, sizeof(self->pool_lock) );
 
    self->array_idle_blocks = NULL;
  }
 
  // Chain up
  return POLAR_RUNTIME_OBJECT_CLASS(superclass_polar_runtime_memory_pool)->finalize( (polar_runtime_object *)self );
}
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_HOTSPOT void *
_polar_runtime_memory_pool_allocate_elements( polar_runtime_memory_pool *self, size_t count_elements )
{
  void *result;
  polar_memory_pool_class *superclass;
  intptr_t idx_idle_list, i;
  char *block_remainder;
 
  assert( count_elements > 0 );
 
  superclass = POLAR_MEMORY_POOL_CLASS(superclass_polar_runtime_memory_pool);
 
  if( count_elements <= POLAR_LENGTH_RUNTIME_STRUCT_MAX )
    ;
 
  else
  {
    mtx_lock( &self->pool_lock );
      result = superclass->allocate_elements( (polar_memory_pool *)self, count_elements );
    mtx_unlock( &self->pool_lock );
 
    return result;
  }
 
  // First, attempt to recycle an idle block
  idx_idle_list = ( count_elements >> 1 );
 
  mtx_lock( &self->pool_lock );
 
  result = polar_runtime_memory_pool_block_idle_pop(self, idx_idle_list);
  if( result != NULL )
  {
    mtx_unlock( &self->pool_lock );
 
    // The memory is already zeroed
    return result;
  }
 
  // There were no idle blocks of the desired size available
  self->array_idle_blocks[idx_idle_list].count_misses++;
 
  // Attempt to fragment and recycle a larger idle block
  if( idx_idle_list < POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE )
  {
    for( i = idx_idle_list + 1; i <= POLAR_LENGTH_ARRAY_MEMBLOCK_IDLE; i++ )
    {
      result = polar_runtime_memory_pool_block_idle_pop(self, i);
 
      if( result != NULL )
      {
        // Fragment the larger block and push the upper part back onto the appropriate idle list
        block_remainder = ( (char *)result + (count_elements << OBJC_SIZE_SHIFT_POINTER) );
        polar_runtime_memory_pool_block_idle_push(self, i - idx_idle_list, block_remainder);
 
        mtx_unlock( &self->pool_lock );
 
        // The memory has already been zeroed
        return result;
      }
    }
  }
 
  // There were no idle blocks available; allocate a new one
  result = superclass->allocate_elements( (polar_memory_pool *)self, count_elements );
 
#ifdef POLAR_DEBUG_RUNTIME_MEMORY
  self->array_blocks_idle[idx_idle_list].count_blocks_allocated++;
#endif // POLAR_DEBUG_RUNTIME_MEMORY
 
  mtx_unlock( &self->pool_lock );
 
  // The memory is already zeroed
  return result;
}
 
/* Note that the pool lock is held for the entire time this method executes, owing to the point at which this method is
   called:
     _polar_runtime_memory_pool_allocate_elements() <lock acquired> =>
       _polar_memory_pool_allocate_elements() =>
         polar_memory_pool_grow() =>
           _polar_runtime_memory_pool_memory_salvage() <virtual method call>
*/
POLAR_FUNCTION_INTERNAL void
_polar_runtime_memory_pool_memory_salvage( polar_runtime_memory_pool *self, char *byte_next,
                                           size_t count_bytes_remaining )
{
  size_t size_block_current;
  intptr_t idx_idle_list;
 
  while( count_bytes_remaining >= X2_SIZEOF_POINTER )
  {
    size_block_current = MIN(count_bytes_remaining, POLAR_SIZE_RUNTIME_STRUCT_MAX);
 
    idx_idle_list = ( size_block_current >> X2_SIZE_SHIFT_POINTER );
    size_block_current = ( idx_idle_list << X2_SIZE_SHIFT_POINTER );
 
    polar_runtime_memory_pool_block_idle_push(self, idx_idle_list, byte_next);
    byte_next += size_block_current;
    count_bytes_remaining -= size_block_current;
 
  #ifdef POLAR_DEBUG_RUNTIME_MEMORY
    self->count_bytes_salvage += size_block_current;
  #endif // POLAR_DEBUG_RUNTIME_MEMORY
  }
}
 
POLAR_FUNCTION_INTERNAL void
_polar_runtime_memory_pool_class_init( polar_runtime_memory_pool_class *self )
{
  // Acquire our superclass
  superclass_polar_runtime_memory_pool = POLAR_RUNTIME_OBJECT_CLASS(self)->class_superclass;
 
  // Establish our virtual methods
  ( (polar_runtime_object_class *)self )->init = (polar_func_runtime_object_lifecycle)_polar_runtime_memory_pool_init;
 
  ( (polar_runtime_object_class *)self )->finalize =
      (polar_func_runtime_object_lifecycle)_polar_runtime_memory_pool_finalize;
 
  ( (polar_memory_pool_class *)self )->allocate_elements = (void *)_polar_runtime_memory_pool_allocate_elements;
  ( (polar_memory_pool_class *)self )->memory_salvage = (void *)_polar_runtime_memory_pool_memory_salvage;
}
 
static struct polar_internal_type_info pti_polar_runtime_memory_pool =
{
  .name_type          = "polar_runtime_memory_pool",
  .size_type_instance = sizeof(polar_runtime_memory_pool),
  .size_type_class    = sizeof(polar_runtime_memory_pool_class),
  .type_class_init    = (polar_func_runtime_object_class_lifecycle)_polar_runtime_memory_pool_class_init
};
 
// Public ==============================================================================================================
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_CONSTANT polar_internal_type
polar_runtime_memory_pool_get_type( void )
{
  static polar_internal_type pt_polar_runtime_memory_pool = POLAR_INTERNAL_TYPE_INVALID;
 
  if( pt_polar_runtime_memory_pool != POLAR_INTERNAL_TYPE_INVALID )
    return pt_polar_runtime_memory_pool;
 
  pt_polar_runtime_memory_pool = polar_internal_type_init( POLAR_TYPE_MEMORY_POOL, &class_polar_runtime_memory_pool,
                                                           &pti_polar_runtime_memory_pool );
 
  return pt_polar_runtime_memory_pool;
}
 
POLAR_FUNCTION_INTERNAL void
polar_runtime_memory_pool_free_elements( polar_runtime_memory_pool *self, size_t count_elements,
                                         void *array_elements )
{
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
  assert( count_elements <= POLAR_LENGTH_RUNTIME_STRUCT_MAX );
  assert( count_elements & 1 == 0 );
 
  if( (count_elements > 0) && (array_elements != NULL) )
  {
    // Zero the memory before it is pushed onto the appropriate idle list
    objc_memzero(array_elements, count_elements << OBJC_SIZE_SHIFT_POINTER);
 
    mtx_lock( &self->pool_lock );
      polar_runtime_memory_pool_block_idle_push(self, (count_elements >> 1), array_elements);
    mtx_unlock( &self->pool_lock );
  }
}
 
POLAR_FUNCTION_INTERNAL void *
polar_runtime_memory_pool_intern_struct( polar_runtime_memory_pool *self, void *p_struct_source,
                                         size_t size_struct_source )
{
  void *result;
  size_t length_struct_source;
 
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
  assert( size_struct_source > 0 );
 
  length_struct_source = POLAR_LENGTH_STRUCT_IN_POINTERS(size_struct_source);
  result = polar_memory_pool_allocate_elements( (polar_memory_pool *)self, length_struct_source );
 
  if( p_struct_source != NULL )
    return objc_memcpy(result, p_struct_source, size_struct_source);
 
  return result;
}
 
POLAR_FUNCTION_INTERNAL const char *
polar_runtime_memory_pool_intern_string( polar_runtime_memory_pool *self, const char *p_string_source,
                                         intptr_t len_string_source )
{
  char *result;
  polar_hash_table_node_string_key *node_string_interned;
  size_t len_string, len_string_in_pointers;
 
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
 
  if( (p_string_source != NULL) && (*p_string_source != 0) && (len_string_source != 0) )
    ;
 
  else
    return NULL;
 
  if( len_string_source > 0 )
    len_string = objc_strnlen(p_string_source, (size_t)len_string_source);
 
  else
    len_string = objc_strlen(p_string_source);
 
  mtx_lock( &self->pool_lock );
 
  if( self->table_strings_interned != NULL )
  {
    node_string_interned = (polar_hash_table_node_string_key *)
      polar_hash_table_get_node(self->table_strings_interned, (void *)p_string_source);
 
    if( node_string_interned != NULL )
    {
      result = (char *)polar_hash_table_node_string_key_get_key(node_string_interned);
      mtx_unlock( &self->pool_lock );
 
      return (const char *)result;
    }
  }
 
  else
  {
    self->table_strings_interned = polar_hash_table_new( POLAR_COUNT_BUCKETS_TABLE_STRINGS_INTERNED,
                                                         POLAR_TYPE_HASH_TABLE_NODE_STRING_KEY );
  }
 
  len_string_in_pointers = POLAR_LENGTH_STRUCT_IN_POINTERS(len_string + 1);
 
  /* This causes a recursive lock on `self`, but potentially allows us to recycle an idle structure for strings that
     will fit inside of one of them.
  */
  result = (char *)polar_memory_pool_allocate_elements( (polar_memory_pool *)self, len_string_in_pointers );
 
  objc_memcpy(result, (void *)p_string_source, len_string);
  polar_hash_table_add_node(self->table_strings_interned, result);
 
  mtx_unlock( &self->pool_lock );
  return (const char *)result;
}
 
POLAR_FUNCTION_INTERNAL void
polar_runtime_memory_pool_recycle_struct( polar_runtime_memory_pool *self, void *p_struct_source,
                                          size_t size_struct_source )
{
  assert( POLAR_IS_RUNTIME_MEMORY_POOL(self) );
 
  if( (size_struct_source >= X2_SIZEOF_POINTER) && (p_struct_source != NULL) )
  {
    // Zero the memory first
    objc_memzero(p_struct_source, size_struct_source);
 
    mtx_lock( &self->pool_lock );
      polar_memory_pool_memory_salvage( (polar_memory_pool *)self, (char *)p_struct_source, size_struct_source );
    mtx_unlock( &self->pool_lock );
  }
}