malloc alternative for memory allocation as a stack

Question

I am looking for a malloc alternative for c that will only ever be used as a stack. Something more like alloca but not limited in space by the stack size. It is for coding a math algorithm.

• I will work with large amounts of memory (possibly hundreds of megabytes in use in the middle of the algorithm)
• memory is accessed in a stack-like order. What I mean is that the next memory to be freed is always the memory that was most recently allocated.
• would like to be able to run an a variety of systems (Windows and Unix-like)
• as an extra, something that can be used with threading, where the stack-like allocate and free order applies just to individual threads. (ie ideally each thread has its own "pool" for memory allocation)

My question is, is there anything like this, or is this something that would be easy to implement?

Answer 1

This sounds like a perfect use for Obstack.

I've never used it myself since the API is really confusing, and I can't dig up an example right now. But it supports all the operations you want, and additionally supports streaming creation of the "current" object.

Edit: whipped up a quick example. The Obstack API shows signs of age, but the principle is sound at least.

You will probably want to look into tuning the align/block settings and likely use obstack_next_free and obstack_object_size if you do any fancy growing.

#include <obstack.h>
#include <stdio.h>
#include <stdlib.h>

void *xmalloc(size_t size)
{
    void *rv = malloc(size);
    if (rv == NULL)
        abort();
    return rv;
}

#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free

const char *cat(struct obstack *obstack_ptr, const char *dir, const char *file)
{
    obstack_grow(obstack_ptr, dir, strlen(dir));
    obstack_1grow(obstack_ptr, '/');
    obstack_grow0(obstack_ptr, file, strlen(file));
    return obstack_finish(obstack_ptr);
}

int main()
{
    struct obstack main_stack;
    obstack_init(&main_stack);
    const char *cat1 = cat(&main_stack, "dir1", "file1");
    const char *cat2 = cat(&main_stack, "dir1", "file2");
    const char *cat3 = cat(&main_stack, "dir2", "file3");
    puts(cat1);
    puts(cat2);
    puts(cat3);
    obstack_free(&main_stack, cat2);
    // cat2 and cat3 both freed, cat1 still valid
}

Answer 2

As you already found out, as long as it works with malloc you should use it and only come back when you need to squeeze out the last bit of performance.

An idea fit that case: You could use a list of blocks, that you allocate when needed. Using a list makes it possible to eventually swap out data in case you hit the virtual memory limit.

struct block {
  size_t size;
  void * memory;
  struct block * next;
};
struct stacklike {
  struct block * top;
  void * last_alloc;
};
void * allocate (struct stacklike * a, size_t s) {
  // add null check for top
  if (a->top->size - (a->next_alloc - a->top->memory) < s + sizeof(size_t)) {
    // not enough memory left in top block, allocate new one
    struct block * nb = malloc(sizeof(*nb));
    nb->next = a->top;
    a->top = nb;
    nb->memory = malloc(/* some size large enough to hold multiple data entities */);
    // also set nb size to that size
    a->next_alloc = nb->memory;
  }
  void * place = a->next_alloc;
  a->next_alloc += s;
  *((size_t *) a->next_alloc) = s; // store size to be able to free
  a->next_alloc += sizeof (size_t);
  return place;
}

I hope this shows the general idea, for an actual implementation there's much more to consider.

To swap out stuff you change that to a doubly linked list an keep track of the total allocated bytes. If you hit a limit, write the end to some file.

Answer 3

I have seen a strategy used in an old FORTRAN program that might be what you are looking for. The strategy involves use of a global array that is passed down to each function from main.

char global_buffer[SOME_LARGE_SIZE];

void foo1(char* buffer, ...);
void foo2(char* buffer, ...);
void foo3(char* buffer, ...);

int main()
{
   foo1(global_buffer, ....);
}

void foo1(char* buffer, ...)
{
   // This function needs to use SIZE1 characters of buffer.
   // It can let the functions that it calls use buffer+SIZE1

   foo2(buffer+SIZE1, ...);

   // When foo2 returns, everything from buffer+SIZE1 is assumed
   // to be free for re-use.
}

void foo2(char* buffer, ...)
{
   // This function needs to use SIZE2 characters of buffer.
   // It can let the functions that it calls use buffer+SIZE2

   foo3(buffer+SIZE2, ...);
}

void foo3(char* buffer, ...)
{
   // This function needs to use SIZE3 characters of buffer.
   // It can let the functions that it calls use buffer+SIZE3

   bar1(buffer+SIZE3, ...);
}