Reputation: 3415
malloc code in C
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;
}
}
Upvotes: 1
Views: 8805
Answers (7)
Reputation: 361
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
Upvotes: 0
Reputation: 1727
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.
Upvotes: 0
Reputation: 1202
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.
Upvotes: 0
Reputation: 320381
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').
Upvotes: 4
Reputation: 41858
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.
Upvotes: 1
Reputation: 40299
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].
Upvotes: 2
