/* Copyright (C) 2023-2026 Free Software Foundation, Inc.    This file is part of the GNU Offloading and Multi Processing Library   (libgomp).    Libgomp 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.    Libgomp 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.    Under Section 7 of GPL version 3, you are granted additional   permissions described in the GCC Runtime Library Exception, version   3.1, as published by the Free Software Foundation.    You should have received a copy of the GNU General Public License and   a copy of the GCC Runtime Library Exception along with this program;   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see   <http://www.gnu.org/licenses/>.  */ /* This is a basic "malloc" implementation intended for use with small,   low-latency memories.    Compared to the "simple" allocator, this one is designed to keep the   metadata and heap together (no slow memory needed), and prioritize   space-efficiency over algorithm speed (the memory already being   low-latency).    To use this template, define BASIC_ALLOC_PREFIX, and then #include the   source file.  The other configuration macros are optional.    The root heap descriptor is stored in the first bytes of the heap, and each   free chunk contains a similar descriptor for the next free chunk in the   chain.    The descriptor is two values: offset and size, which describe the   location of a chunk of memory available for allocation. The offset is   relative to the base of the heap.  The special offset value 0xffffffff   indicates that the heap (free chain) is locked.  The offset and size are   32-bit values so the base alignment can be 8-bytes.    Memory is allocated to the first free chunk that fits.  The free chain   is always stored in order of the offset to assist coalescing adjacent   chunks.  */ #include "libgomp.h" #ifndef BASIC_ALLOC_PREFIX#error "BASIC_ALLOC_PREFIX not defined."#endif #ifndef BASIC_ALLOC_YIELD#define BASIC_ALLOC_YIELD#endif #define ALIGN(VAR) (((VAR) + 7) & ~7)    /* 8-byte granularity.  */ #define fn1(prefix, name) prefix ## _ ## name#define fn(prefix, name) fn1 (prefix, name)#define basic_alloc_init fn(BASIC_ALLOC_PREFIX,init)#define basic_alloc_alloc fn(BASIC_ALLOC_PREFIX,alloc)#define basic_alloc_calloc fn(BASIC_ALLOC_PREFIX,calloc)#define basic_alloc_free fn(BASIC_ALLOC_PREFIX,free)#define basic_alloc_realloc fn(BASIC_ALLOC_PREFIX,realloc) typedef struct {  uint32_t offset;  uint32_t size;} heapdesc; voidbasic_alloc_init (char *heap, size_t limit){  if (heap == NULL)    return;   /* Initialize the head of the free chain.  */  heapdesc *root = (heapdesc *) heap;  root->offset = ALIGN(1);  root->size = limit - root->offset;   /* And terminate the chain.  */  heapdesc *next = (heapdesc *) (heap + root->offset);  next->offset = 0;  next->size = 0;} static void *basic_alloc_alloc (char *heap, size_t size){  if (heap == NULL)    return NULL;   /* Memory is allocated in N-byte granularity.  */  size = ALIGN (size);   /* Acquire a lock on the low-latency heap.  */  heapdesc root, *root_ptr = (heapdesc *) heap;  do    {      root.offset = __atomic_exchange_n (&root_ptr->offset, 0xffffffff, 					 MEMMODEL_ACQUIRE);      if (root.offset != 0xffffffff)	{	  root.size = root_ptr->size;	  break;	}      /* Spin.  */      BASIC_ALLOC_YIELD;    }  while (1);   /* Walk the free chain.  */  heapdesc chunk = root;  heapdesc *prev_chunkptr = NULL;  heapdesc *chunkptr = (heapdesc *) (heap + chunk.offset);  heapdesc onward_chain = *chunkptr;  while (chunk.size != 0 && (uint32_t) size > chunk.size)    {      chunk = onward_chain;      prev_chunkptr = chunkptr;      chunkptr = (heapdesc *) (heap + chunk.offset);      onward_chain = *chunkptr;    }   void *result = NULL;  if (chunk.size != 0)    {      /* Allocation successful.  */      result = chunkptr;       /* Update the free chain.  */      heapdesc stillfree = chunk;      stillfree.offset += size;      stillfree.size -= size;      heapdesc *stillfreeptr = (heapdesc *) (heap + stillfree.offset);       if (stillfree.size == 0)	/* The whole chunk was used.  */	stillfree = onward_chain;      else	/* The chunk was split, so restore the onward chain.  */	*stillfreeptr = onward_chain;       /* The previous free slot or root now points to stillfree.  */      if (prev_chunkptr)	*prev_chunkptr = stillfree;      else	root = stillfree;    }   /* Update the free chain root and release the lock.  */  root_ptr->size = root.size;  __atomic_store_n (&root_ptr->offset, root.offset, MEMMODEL_RELEASE);   return result;} static void *basic_alloc_calloc (char *heap, size_t size){  /* Memory is allocated in N-byte granularity.  */  size = ALIGN (size);   uint64_t *result = basic_alloc_alloc (heap, size);  if (result)    /* Inline memset in which we know size is a multiple of 8.  */    for (unsigned i = 0; i < (unsigned) size / 8; i++)    result[i] = 0;   return result;} static voidbasic_alloc_free (char *heap, void *addr, size_t size){  /* Memory is allocated in N-byte granularity.  */  size = ALIGN (size);   /* Acquire a lock on the low-latency heap.  */  heapdesc root, *root_ptr = (heapdesc *) heap;  do    {      root.offset = __atomic_exchange_n (&root_ptr->offset, 0xffffffff, 					 MEMMODEL_ACQUIRE);      if (root.offset != 0xffffffff)	{	  root.size = root_ptr->size;	  break;	}      /* Spin.  */      BASIC_ALLOC_YIELD;    }  while (1);   /* Walk the free chain to find where to insert a new entry.  */  heapdesc chunk = root, prev_chunk = {0};  heapdesc *prev_chunkptr = NULL, *prevprev_chunkptr = NULL;  heapdesc *chunkptr = (heapdesc *) (heap + chunk.offset);  heapdesc onward_chain = *chunkptr;  while (chunk.size != 0 && addr > (void *) chunkptr)    {      prev_chunk = chunk;      chunk = onward_chain;      prevprev_chunkptr = prev_chunkptr;      prev_chunkptr = chunkptr;      chunkptr = (heapdesc *) (heap + chunk.offset);      onward_chain = *chunkptr;    }   /* Create the new chunk descriptor.  */  heapdesc newfreechunk;  newfreechunk.offset = (uint32_t) ((uintptr_t) addr - (uintptr_t) heap);  newfreechunk.size = (uint32_t) size;   /* Coalesce adjacent free chunks.  */  if (newfreechunk.offset + size == chunk.offset)    {      /* Free chunk follows.  */      newfreechunk.size += chunk.size;      chunk = onward_chain;    }  if (prev_chunkptr)    {      if (prev_chunk.offset + prev_chunk.size	  == newfreechunk.offset)	{	  /* Free chunk precedes.  */	  newfreechunk.offset = prev_chunk.offset;	  newfreechunk.size += prev_chunk.size;	  addr = heap + prev_chunk.offset;	  prev_chunkptr = prevprev_chunkptr;	}    }   /* Update the free chain in the new and previous chunks.  */  *(heapdesc *) addr = chunk;  if (prev_chunkptr)    *prev_chunkptr = newfreechunk;  else    root = newfreechunk;   /* Update the free chain root and release the lock.  */  root_ptr->size = root.size;  __atomic_store_n (&root_ptr->offset, root.offset, MEMMODEL_RELEASE); } static void *basic_alloc_realloc (char *heap, void *addr, size_t oldsize,				      size_t size){  /* Memory is allocated in N-byte granularity.  */  oldsize = ALIGN (oldsize);  size = ALIGN (size);   if (oldsize == size)    return addr;   /* Acquire a lock on the low-latency heap.  */  heapdesc root, *root_ptr = (heapdesc *) heap;  do    {      root.offset = __atomic_exchange_n (&root_ptr->offset, 0xffffffff, 					 MEMMODEL_ACQUIRE);      if (root.offset != 0xffffffff)	{	  root.size = root_ptr->size;	  break;	}      /* Spin.  */      BASIC_ALLOC_YIELD;    }  while (1);   /* Walk the free chain.  */  heapdesc chunk = root;  heapdesc *prev_chunkptr = NULL;  heapdesc *chunkptr = (heapdesc *) (heap + chunk.offset);  heapdesc onward_chain = *chunkptr;  while (chunk.size != 0 && (void *) chunkptr < addr)    {      chunk = onward_chain;      prev_chunkptr = chunkptr;      chunkptr = (heapdesc *) (heap + chunk.offset);      onward_chain = *chunkptr;    }   void *result = NULL;  if (size < oldsize)    {      /* The new allocation is smaller than the old; we can always	 shrink an allocation in place.  */      result = addr;       heapdesc *nowfreeptr = (heapdesc *) (addr + size);       /* Update the free chain.  */      heapdesc nowfree;      nowfree.offset = (char *) nowfreeptr - heap;      nowfree.size = oldsize - size;       if (nowfree.offset + size == chunk.offset)	{	  /* Coalesce following free chunk.  */	  nowfree.size += chunk.size;	  *nowfreeptr = onward_chain;	}      else	*nowfreeptr = chunk;       /* The previous free slot or root now points to nowfree.  */      if (prev_chunkptr)	*prev_chunkptr = nowfree;      else	root = nowfree;    }  else if (chunk.size != 0	   && (char *) addr + oldsize == (char *) chunkptr	   && chunk.size >= size-oldsize)    {      /* The new allocation is larger than the old, and we found a	 large enough free block right after the existing block,	 so we extend into that space.  */      result = addr;       uint32_t delta = size-oldsize;       /* Update the free chain.  */      heapdesc stillfree = chunk;      stillfree.offset += delta;      stillfree.size -= delta;      heapdesc *stillfreeptr = (heapdesc *) (heap + stillfree.offset);       if (stillfree.size == 0)	/* The whole chunk was used.  */	stillfree = onward_chain;      else	/* The chunk was split, so restore the onward chain.  */	*stillfreeptr = onward_chain;       /* The previous free slot or root now points to stillfree.  */      if (prev_chunkptr)	*prev_chunkptr = stillfree;      else	root = stillfree;    }  /* Else realloc in-place has failed and result remains NULL.  */   /* Update the free chain root and release the lock.  */  root_ptr->size = root.size;  __atomic_store_n (&root_ptr->offset, root.offset, MEMMODEL_RELEASE);   if (result == NULL)    {      /* The allocation could not be extended in place, so we simply	 allocate fresh memory and move the data.  If we can't allocate	 from low-latency memory then we leave the original alloaction	 intact and return NULL.	 We could do a fall-back to main memory, but we don't know what	 the fall-back trait said to do.  */      result = basic_alloc_alloc (heap, size);      if (result != NULL)	{	  /* Inline memcpy in which we know oldsize is a multiple of 8.  */	  uint64_t *from = addr, *to = result;	  for (unsigned i = 0; i < (unsigned) oldsize / 8; i++)	    to[i] = from[i]; 	  basic_alloc_free (heap, addr, oldsize);	}    }   return result;} #undef ALIGN#undef fn1#undef fn#undef basic_alloc_init#undef basic_alloc_alloc#undef basic_alloc_free#undef basic_alloc_realloc