CS 330 Lecture 14 – Jeff’s Malloc
Agenda
- what ?s
- finish jmalloc
- what happens when
TODO
- Optional: check out the section of the C FAQ on memory allocation: http://c-faq.com/malloc/index.html.
- Really optional: check out the GNU implementation of malloc.
What Happens When…
- You malloc but you don’t free?
- You write beyond your allocation?
- You free a pointer twice?
- You free memory that’s not your own?
- You free NULL?
- You never malloc?
Code
sizeof.c
#include <stdio.h>
#include <stdlib.h>
#define PRINTSIZE(type) printf("sizeof(" # type "): %ld\n", sizeof(type))
int main(int argc, char **argv) {
PRINTSIZE(char);
PRINTSIZE(unsigned char);
PRINTSIZE(short);
PRINTSIZE(unsigned short);
PRINTSIZE(int);
PRINTSIZE(unsigned int);
PRINTSIZE(long);
PRINTSIZE(unsigned long);
PRINTSIZE(long long);
PRINTSIZE(unsigned long long);
PRINTSIZE(float);
PRINTSIZE(double);
PRINTSIZE(long double);
PRINTSIZE(char *);
PRINTSIZE(short *);
PRINTSIZE(int *);
PRINTSIZE(long *);
PRINTSIZE(float *);
PRINTSIZE(double *);
PRINTSIZE(void *);
return 0;
}
jmalloc.h
#ifndef JMALLOC_H
#define JMALLOC_H
void *jmalloc(int nbytes_requested);
void jfree(void *p);
#endif
jmalloc.c
#include <stdio.h>
#include <string.h>
#include "jmalloc.h"
#define HEAP_SIZE 8192
char heap[HEAP_SIZE];
struct block_t {
int size;
struct block_t *next;
struct block_t *prev;
};
struct block_t *head = NULL;
void show_blocks() {
for (struct block_t *block = head; block != NULL; block = block->next) {
printf("%p has %d bytes | ", block, block->size);
}
printf("\n");
}
void *jmalloc(int nbytes_requested) {
// One-time startup costs of initializing free list.
if (!head) {
head = (struct block_t *) heap;
head->size = HEAP_SIZE;
head->next = NULL;
head->prev = NULL;
}
show_blocks();
// Assert that we have enough room to put a freed block_t structure.
// Each requested block will be preceded by its size.
int nbytes_needed = nbytes_requested + sizeof(int);
if (nbytes_needed < sizeof(struct block_t)) {
nbytes_needed = sizeof(struct block_t);
}
// Make sure blocks are always a multiple of 16.
if (nbytes_needed % 16) {
nbytes_needed += 16 - nbytes_needed % 16;
}
// Find a block that has enough capacity to satisfy the request.
struct block_t *big_enough_block = head;
while (big_enough_block != NULL && /* stop when we hit the end of the list */
big_enough_block->size != nbytes_needed && /* stop when we hit a block that's exactly the right size */
big_enough_block->size < nbytes_needed + sizeof(struct block_t) /* stop when we hit a block that has enough space for the request and a new block node in the free list */) {
big_enough_block = big_enough_block->next;
}
// Hey, fellas. This doesn't look good. No block satisfies.
if (!big_enough_block) {
return NULL;
} else {
// Either the block was exactly the right size. In this case, there's no new link. We just give back the whole block.
if (big_enough_block->size == nbytes_needed) {
if (big_enough_block->prev) {
big_enough_block->prev->next = big_enough_block->next;
} else {
head = big_enough_block->next;
}
if (big_enough_block->next) {
big_enough_block->next->prev = big_enough_block->prev;
}
}
// Or it had some extra space. In this case the new link is going to appear after the reservation.
else {
struct block_t *leftovers_block = (struct block_t *) ((char *) big_enough_block + nbytes_needed);
leftovers_block->size = big_enough_block->size - nbytes_needed;
leftovers_block->prev = big_enough_block->prev;
leftovers_block->next = big_enough_block->next;
if (leftovers_block->prev) {
leftovers_block->prev->next = leftovers_block;
}
if (leftovers_block->next) {
leftovers_block->next->prev = leftovers_block;
}
if (big_enough_block == head) {
head = leftovers_block;
}
}
// big_enough_block gets sent back, but not before we write its size so that freeing becomes easier.
int *block_as_int_pointer = (int *) big_enough_block;
*block_as_int_pointer = nbytes_needed;
return &block_as_int_pointer[1];
}
}
void jfree(void *p) {
// We's gonna prepend the freed block onto the free list. Yes we is!
// The block starts an int back.
struct block_t *freed_block = (struct block_t *) ((int *) p - 1);
/* freed_block->size = */ // We don't need to write size! It's already there. Hee hee hee!
freed_block->prev = NULL;
freed_block->next = head;
// Make successor know about the new block on the block.
if (freed_block->next) {
freed_block->next->prev = freed_block;
}
head = freed_block;
show_blocks();
}
malloc_test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "jmalloc.h"
int main(int argc, char **argv) {
char *s1 = (char *) jmalloc(sizeof(char) * 25);
char *s2 = (char *) jmalloc(sizeof(char) * 72);
char *s3 = (char *) jmalloc(sizeof(char) * 37);
strcpy(s1, "foo bag");
strcpy(s2, "carnival");
strcpy(s3, "parabola");
printf("s1: %s\n", s1);
printf("s2: %s\n", s2);
printf("s3: %s\n", s3);
jfree(s1);
jfree(s2);
jfree(s3);
/* show_blocks(); */
s1 = (char *) jmalloc(sizeof(char) * 25);
return 0;
}
Haiku
We run from hard work
“Next time…”, it growls, teeth flashing
“I’ll be difficult”
“Next time…”, it growls, teeth flashing
“I’ll be difficult”