The points computed by mdriver are not absolute but depend on the machine where the test is run as they depend on an evaluation of the installed libc performance. You might therefore notice different results for your lab. All the labs are tested on the same machine and evaluated using the same libc performance values.
Archive for the 'malloc' Category
Some sample solutions and examples for the malloc lab are availble.
| mm-naive.c | The simplest solution: malloc simply sbrk’s and writes a size header. free does nothing. realloc is implemented directly with malloc and free. This solution has great throughput but terrible space utilization, and thus fails on many traces because it exhausts memory. |
| mm-implicit.c | Solution based on coalescing implicit free lists with boundary tag. This is the simplest reasonable package. |
| mm-explicit.c | Solution based on explicit free list with boundary tag coalescing and first fit placement. |
| mm-tree.c | Highly optimized solution based on red-black trees. |
| mm-test.c | A buggy malloc that produces overlapping blocks. Used for testing the driver. |
As you may have seen most of the malloc labs have been corrected. I sent emails with the points to all people of each team (some handins have not yet been graded – they will follow in a day or so). If there are any questions, step by at my office or drop me an email.
The C99 standard defines that a malloc(0) is legal:
If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.
If a non-zero value is returned it should be not used but it is legal to pass it to a subsequent call of free (note that free(NULL)is also legal).
It follows that
void * p = malloc(0); free(p);
is legal and should be accepted by your allocator.
mdriver prints the ERROR: mem_sbrk failed. Ran out of memory... error message when the simulated memory heap (20MB) is full. Some of the test traces allocate a total of 37MB (without considering frees). This could therefore happen if:
- your
freeroutine fails to free the released blocks - your
mallocroutine fails to use freed blocks - your allocation algorithm generates too much internal fragmentation
Compilers usually align fields to allow faster access. It is usually possible to tell the compiler to avoid this behavior and generate structs as they are specified. gcc uses the attribute tag. For example the following code
struct test_t {
char b;
long l;
};
struct test_t test = { 'a', 42 };
is compiled (on an Intel architecture) as
.globl _test
.data
.align 2
_test:
.byte 97
.space 3
.long 42
.subsections_via_symbols
where three bytes are used to pad the char to 32 bits. While
struct test_t {
char b;
long l;
} __attribute__ ((packed));
struct test_t test = { 'a', 42 } ;
is compiled as
.globl _test
.data
_test:
.byte 97
.long 42
.subsections_via_symbols
The macros to align the addresses returned by malloc in the given example (in malloc-handout) are wrong since they only deliver 8-byte aligned results.
The results must of course be and-ed with ~(ALIGNMENT-1) and not ~0x7 (which is only OK if ALIGNMENT is 8).
Please patch your mm.c file:
#define ALIGNMENT 8 #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1)) #define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
A new tarball (malloclab-handout.tar) is available