malloc code in C

Question

I have a code block that seems to be the code behind malloc. But as I go through the code, I get the feeling that parts of the code are missing. Does anyone know if there is a part of the function that's missing? Does malloc always combine adjacent chunks together?

int heap[10000];
void* malloc(int size) {
int sz = (size + 3) / 4;
int chunk = 0;
if(heap[chunk] > sz) {
    int my_size = heap[chunk];
    if (my_size < 0) {
      my_size = -my_size
    }
    chunk = chunk + my_size + 2;
    if (chunk == heap_size) { 
      return 0;
    }
}

Answer 1

The code behind malloc is certainly much more complex than that. There are several strategies. One popular code is the dlmalloc library. A simpler one is described in K&R.

Answer 2

Well, one error in that code is that it doesn't return a pointer to the data.

I suspect the best approach to that code is [delete].

Answer 3

The code is obviously incomplete (not all paths return a value). But in any case this is not a "real" malloc. This is probably an attempt to implement a highly simplified "model" of 'malloc'. The approach chosen by the author of the code can't really lead to a useful practical implementation.

(And BTW, standard 'malloc's parameter has type 'size_t', not 'int').

Answer 4

When possible, I expect that malloc will try to put different requests close to each other, as it will have a block of code that is available for malloc, until it has to get a new block.

But, that also depends on the requirements imposed by the OS and hardware architecture. If you are only allowed to request a certain minimum size of code then it may be that each allocation won't be near each other.

As others mentioned, there are problems with the code snippet.

You can find various open-source projects that have their own malloc function, and it may be best to look at one of those, in order to get an idea what is missing.

Answer 5

The code seems to be run on a metal machine, normally no virtual address mapping on such a system which only use physical address space directly.

See my understanding, on a 32 bits system, sizeof(ptr) = 4 bytes:

extern block_t *block_head; // the real heap, and its address 
                            // is >= 0x80000000, see below "my_size < 0"
extern void *get_block(int index); // get a block from the heap 
                                   // (lead by block_head)
int heap[10000]; // just the indicators, not the real heap

void* malloc(int size) 
{
    int sz = (size + 3) / 4; // make the size aligns with 4 bytes,
                             // you know, allocated size would be aligned.
    int chunk = 0; // the first check point
    if(heap[chunk] > sz) { // the value is either a valid free-block size 
                           // which meets my requirement, or an 
                           // address of an allocated block
        int my_size = heap[chunk]; // verify size or address
        if (my_size < 0) { // it is an address, say a 32-bit value which 
                           // is >0x8000...., not a size. 
              my_size = -my_size // the algo, convert it
        }
        chunk = chunk + my_size + 2; // the algo too, get available 
                                     // block index
        if (chunk == heap_size) { // no free chunks left
           return NULL; // Out of Memory
        }
        void *block = get_block(chunk);
        heap[chunk] = (int)block;
        return block;
    }
    // my blocks is too small initially, none of the blocks 
    // will meet the requirement
    return NULL;
}

EDIT: Could somebody help to explain the algo, that is, converting address -> my_size -> chunk? you know, when call reclaim, say free(void *addr), it'll use this address -> my_size -> chunk algo too, to update the heap[chunk] accordingly after return the block to the heap.

Answer 6

malloc is for dynamically allocated memory. And this involves sbrk, mmap, or maybe some other system functions for Windows and/or other architectures. I am not sure what your int heap[10000] is for, as the code is too incomplete.

Effo's version make a little bit more sense, but then it introduce another black box function get_block, so it doesn't help much.

Answer 7

To small to be a whole malloc implementation

Take a llok in the sources of the C library of Visual Studio 6.0, there you will find the implementation of malloc if I remeber it correctly