Is there a malloc implementation which does bookkeeping outside its own heap?

I need to manage a memory heap, with the constraint that this memory should only be written to, never read, i.e. the malloc implementation should keep the bookkeeping information separately from the heap it manages, on the normal heap, and should in fact never touch the specific heap it manages. I was hoping to use a tested, optimized, off the shelf solution for that, if one is available. Examples of use include OpenGL VBOs and memory on external units of embedded systems.

I glanced at dlmalloc, and from the documentation, it seems to tag the memory blocks it allocates from both sides with bookkeeping information. Googling didn't do any good either - perhaps i don't have the right keywords to find what i'm looking for.

Clarifications: as a separate heap, i mean what i define to be a heap. I want to tightly use memory with small allocations within one or a small number of pre-allocated blocks. I don't even care if the bookkeeping information (outside the thus managed heap) is larger than the data inside :) Furthermore, the application it开发者_StackOverflow社区self will use stock malloc and heap for its operation, and only use those blocks for special purpose, which boils down to memory regions for speaking to external hardware, where writes from application are the purpose, reads are impossible or expensive. This is not a general malloc question, i was merely hoping to leverage something where a lot of research and testing has gone into.

and should in fact never touch the specific heap it manages.

What if it does not manage the heap? See this malloc function utilizing a particular implementation that neither manages the [heap] area (cf. /proc/$$/maps), nor stores its metadata in adressable memory, and yet, gives your program unique adressable memory.

void *mymalloc(size_t len)
{
        void *x = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        return (x == (void *)-1) ? NULL : x;
}

And now for the killer revelation: glibc uses exactly that for sufficiently large allocations.

It's not a ready to use library, but the resource management code in the Linux kernel does exactly this to manage resources such as PCI address space.

Here's a very simple malloc implementation that never writes bookkeeping information to the heap it manages:

void *malloc(size_t n) { return sbrk(n); }
void free(void *p) { }
void *realloc(void *p, size_t n }
{
    void *q = malloc(n);
    if (q) memcpy(q, p, n);
    return q;
}

If you'd like some more realistic ideas, one simple solution is to choose a smallest unit of memory for allocation (8 or 16 bytes might be reasonable) and divide the managed heap into units of this size, then store which ones are free in a bitmap (e.g. one bit per 16 bytes, for 1/128, <1% overhead). Searching for free space is then O(n), but you can think of ways to improve it with multi-scale maps perhaps.

Another idea is to use the same principles as dlmalloc, but instead of storing data in the free chunks, perform a hash on a chunk's address to get its bookkeeping information from a hash bin. One big problem with any method like this that doesn't store information in the actual heap, though, is that freeing memory can paradoxically increase the amount of memory in use (due to the need to allocate new bookkeeping structures).

An implementation would probably be fairly simple to implement. One disadvantage of not storing the metatdata with the allocated block is that the performance of free() is likley to be slower and non-deterministic. But since malloc() already has that problem, perhaps that is not really an issue.

A simple deterministic solution is to implement a fixed-block memory allocator, where fixed size blocks are allocated from the conventional heap and a pointer to each block is placed on a queue or linked list. To allocate a block you simply take a pointer from the free-block queue/list, and to free it you place the pointer back on the free-block list.

Does the manager need to have the same semantics as malloc/free? Things would be greatly simplified if you could have your allocate function return a pointer to a structure which would in turn point to the actual memory; the deallocate function would accept a pointer to the structure, rather than a pointer to the memory.

Beyond that, the allocation method will be greatly influenced by your usage patterns. What can be said about the sizes of allocations, and the pattern of allocating and freeing memory blocks?

Just use the Buddy System.