to be completed in the C language. I attached the code base which should be modified as detailed in the instructions. please show all your work and provide detailed explanations. finna learn
#include #include #include // heap declaration #define _1MB 1048576 unsigned char myheap[_1MB]; #define PAGESIZE 1024 // chunkhead data structure typedef struct chunkhead { unsigned int size; unsigned int info; unsigned char *next, *prev; } chunkhead; // function declarations unsigned char *mymalloc(unsigned int size); void myfree(unsigned char *address); void analyse(); // main void main() { // testing code unsigned char *a, *b, *c; a = mymalloc(1000); b = mymalloc(1000); c = mymalloc(1000); myfree(a); myfree(b); myfree(c); // analysis analyse(); // exiting exit(EXIT_SUCCESS); } // function definitions unsigned char *mymalloc(unsigned int size) { // head of the chunkhead list chunkhead *list = (chunkhead *) myheap; // run only the first time mymalloc is called // to initialize myheap static bool initialized = false; if(!initialized) { *list = (chunkhead) { .size = sizeof(myheap) - sizeof(chunkhead), .info = 0, .next = 0, .prev = 0, }; initialized = true; } // checking list head for size if(list->info == 0) { // memory is free if(size == list->size) { // perfect fit list->info = 1; // marking memory as occupied // returning chunk address return (unsigned char *) list + sizeof(chunkhead); } else if(size + sizeof(chunkhead) size) { // chunkhead of next chunk can fit in // shrinking chunk unsigned int oldSize = list->size; list->size = size; // splitting memory chunkhead *oldNext = (chunkhead *) list->next; chunkhead *newNext = (chunkhead *) list + sizeof(chunkhead) + size; *newNext = (chunkhead) { .size = oldSize - sizeof(chunkhead) - size, .info = 0, .next = (unsigned char *) oldNext, .prev = (unsigned char *) list, }; list->next = (unsigned char *) newNext; if(oldNext != NULL) { oldNext->prev = (unsigned char *) newNext; } // marking memory as occupied list->info = 1; // returning chunk address return (unsigned char *) list + sizeof(chunkhead); } } // set to false since the chunk // has not yet been allocated bool allocated = false; // cannot allocate in head, // find available chunk chunkhead *chunk = (chunkhead *) list->next; // traversing the list while(!allocated && chunk != NULL) { if(chunk->info == 0) { // memory is free if(size == chunk->size) { // perfect fit chunk->info = 1;// marking memory as occupied allocated = true; break; } else if(size + sizeof(chunkhead) size) { // chunkhead of next chunk can fit in // shrinking chunk unsigned int oldSize = chunk->size; chunk->size = size; // splitting memory chunkhead *oldNext = (chunkhead *) chunk->next; chunkhead *newNext = (chunkhead *) chunk + sizeof(chunkhead) + size; *newNext = (chunkhead) { .size = oldSize - sizeof(chunkhead) - size, .info = 0, .next = (unsigned char *) oldNext, .prev = (unsigned char *) chunk, }; chunk->next = (unsigned char *) newNext; if(oldNext != NULL) { oldNext->prev = (unsigned char *) newNext; } // marking memory as occupied chunk->info = 1; allocated = true; break; } } // moving to next chunk chunk = (chunkhead *) chunk->next; } if(!allocated) { // could not be allocated return NULL; } else { // returning chunk address return (unsigned char *) chunk + sizeof(chunkhead); } } void myfree(unsigned char *address) { // NULL address is not freed if(address == NULL) { return; } // getting chunk chunkhead *chunk = (chunkhead *) (address - sizeof(chunkhead)); // freeing chunk chunk->info = 0; if(chunk == (chunkhead *) myheap) { // head chunk return; } // getting previous and next chunks chunkhead *next = (chunkhead *) chunk->next; chunkhead *prev = (chunkhead *) chunk->prev; if(prev != NULL && prev->info == 0 && next != NULL && next->info == 0) { // previous and next chunks are free // so, remove this chunk and link both ends prev->next = (unsigned char *) next; next->prev = (unsigned char *) prev; } } void analyse() { // head of the chunkhead list const chunkhead *list = (chunkhead *) myheap; // traversing the list int chunkNumber = 1; while(list != NULL) { // printing chunk info printf("Chunk #%d ", chunkNumber); printf("Size = %d bytes ", list->size); printf("%s ", list->info ? "Occupied" : "Free"); printf("Next = 0x%08x ", (unsigned int) list->next); printf("Prev = 0x%08x ", (unsigned int) list->prev); // moving to next chunk ++chunkNumber; list = (chunkhead *) list->next; } }
Exercise: Based on lab 3, remove the static heap array and use brk() and sbrk() commands to make the heap. Also, imlement "best fit". Howto: . . Be aware, that the heap size starts at 0, which means, you don't even have a chunk header. Make sure to catch that condition! Maybe with a global variable "heapsize"? From here on, when mymalloc is called, move the program break as far as you need to allocate your first chunk. This time make sure, that the chunkhead is part of the PAGESIZE! Also, assume the PAGESIZE is 4096 bytes. From now on, move through the chunklist similar to lab3, but if no chunk is free, move the program break further and assign a new chunk! If some earlier chunk is free and you allocate less size than that, split as usual. Move the program break back again when the last chunk in the list is removed! You analyse function should print the address of the program break! Best fit: Search the chunks for the smallest possible chunk which satisfies the request. . . . Submit: The whole project folder zipped as filename: program2.zip How we test: byte*a[100); analyze();//50% points for(int i=0;inext; ch = (chunkhead*)ch->next); return ch; } void analyze() { printf(" - if(!startofheap) { printf("no heap"); return; "); chunkhead* ch = (chunkhead*)startofheap; for (int no=0; ch; ch = (chunkhead*)ch->next, no++) { printf("%d | current addr: %x 1", no, ch); printf("size: %d ", ch->size); printf("info: %d ", ch->info); printf("next: %x", ch->next); printf("prev: %x", ch->prev); printf(" "); } printf("program break on address: %x ", sbrk(@)); } Result for comparison no heap, program break on address: 5ff89000 o current addr: 5fff9000 size: 368640 | info: 01 next: 60053000 | prev: 0 1 I current addr: 60053000 size: 4096 | info: 1 | next: 60054000 | prev: 5fff9000 2 current addr: 60054000 Isize: 4096 | info: 1 | next: 60055000 prev: 60053000 3 | current addr: 60055000 size: 4096 | info: 1 | next: 60056000 | prev: 60054000 4 | current addr: 60056000 size: 4096 | info: 1 | next: 60057000 l prev: 60055000 5 | current addr: 60057000 size: 4096 | info: 1 | next: 60058000 | prev: 60056000 6 | current addr: 60058000 size: 4096 | info: 1 | next: 60059000 | prev: 60057000 7 | current addr: 60059000 size: 4096 | info: 1 | next: 6005a000 | prev: 60058000 8 I current addr: 6005a000 size: 4096 | info: 1 | next: 60056000 prev: 60059000 9 | current addr: 6005b000 size: 4096 | info: il next: 60050000 | prev: 6005a000 10 | current addr: 60050000 size: 4096 | info: 1 | next: 0 prev: 60056000 program break on address: 60050000 0 1 current addr: 5fff9000 size: 368640 | info: 0 | next: 60053000 | prev: 0 1 1 current addr: 60053000 size: 4096 | info: 1 | next: 60054000 prev: 5ff9000 2 I current addr: 60054000 size: 4096 | info: 1 l next: 60055000 | prev: 60053000 3 | current addr: 60055000 size: 4096 | info: 1 | next: 60056000 | prev: 60054000 4 | current addr: 60056000 size: 4096 | info: 1 | next: 60057000 | prev: 60055000 5 | current addr: 60057000 size: 4096 | info: 1 | next: 60058000 | prev: 60056000 6 1 current addr: 60058000 size: 4096 | info: 1 | next: 60059000 | prev: 60057000 7 I current addr: 60059000 | size: 4096 | info: 1 | next: 6005a000 | prev: 60058000 8 I current addr: 6005a000 size: 4096 | info: 1 l next: 6005b000 | prev: 60059000 9 | current addr: 6005b000 size: 4096 | info: 1 | next: 60050000 | prev: 60052 000 10 | current addr: 60050000 size: 4096 | info: 1 | next: 0 prev: 6005b000 program break on address: 60050000 no heap, program break on address: 5ff19000 Bonus: We will measure the performance of your code on one and the same computer. The 5 fastest get 2% bonus on the whole course grade. Be creative! My results: 521 micro seconds (VirtualBox, Xubuntu, i7-4770, 3.4 GHz) Test case for speed test (same as above, no print statement except time duration): byte*a[100]; clock_t ca, cb; for(int i=0; i #include
#include // heap declaration #define 1MB 1048576 unsigned char myheap[_1MB]; #define PAGESIZE 1024 // chunkhead data structure typedef struct chunkhead { unsigned int size; unsigned int info; unsigned char *next, *prev; } chunkhead; // function declarations unsigned char *mymalloc(unsigned int size); void myfree(unsigned char *address); void analyse(); // main void main() { // testing code unsigned char *a, *b, *c; a = mymalloc(1000); b = mymalloc(1000); C = mymalloc(1000); myfree(a); myfree(b); myfree(c); // analysis analyse(); Il exiting exit(EXIT SUCCESS); } Il function definitions unsigned char *mymalloc(unsigned int size) { // head of the chunkhead list chunkhead #list = (chunkhead *) myheap; // run only the first time mymalloc is called // to initialize myheap static bool initialized = false; if(!initialized) { *list = (chunkhead) { size = sizeof(myheap) - sizeof(chunkhead), info = 0, .next = 0, .prev = 0, }; initialized = true; } == // checking list head for size if(list->info 0){ // memory is free if(size == list->size) { // perfect fit list->info = 1; // marking memory as occupied // returning chunk address return (unsigned char *) list + sizeof(chunkhead); } else if(size + sizeof(chunkhead) size) { Il chunkhead of next chunk can fit in Il shrinking chunk unsigned int oldSize list->size = size; list->size; 1/ splitting memory chunkhead *oldNext = (chunkhead *) list->next; chunkhead *newNext = (chunkhead *) list + sizeof(chunkhead) + size *newNext = (chunkhead) { size = oldSize - sizeof(chunkhead) - size, info = 0, .next = (unsigned char *) oldNext, .prev = (unsigned char *) list, }; list->next = (unsigned char *) newNext; if(oldNext != NULL) { oldNext->prev = (unsigned char *) newNext; } // marking memory as occupied list->info = 1; // returning chunk address return (unsigned char *) list + sizeof(chunkhead); } } // set to false since the chunk // has not yet been allocated bool allocated = false; Il cannot allocate in head, // find available chunk chunkhead *chunk = (chunkhead *) list->next; // traversing the list while(!allocated && chunk != NULL) { if(chunk->info == 0) { // memory is free if(size == chunk->size) { // perfect fit chunk->info = 1;// marking memory as occupied allocated = true; break; } else if(size + sizeof(chunkhead) size) { Il chunkhead of next chunk can fit in if(chunk->info == 0) { // memory is free if(size chunk->size) { // perfect fit chunk->info = 1;// marking memory as occupied allocated = true; break; } else if(size + sizeof(chunkhead) size) { Il chunkhead of next chunk can fit in // shrinking chunk unsigned int oldSize = chunk->size; chunk->size = size; // splitting memory chunkhead *oldNext = (chunkhead *) chunk->next; chunkhead *newNext = (chunkhead *) chunk + sizeof(chunkhead) + size; *newNext = (chunkhead) { size = oldSize - sizeof(chunkhead) - size, info = 0, .next = (unsigned char *) oldNext, .prev = (unsigned char *) chunk, }; chunk->next = (unsigned char *) new Next; if(oldNext != NULL) { oldNext->prev = (unsigned char *) newNext; } // marking memory as occupied chunk->info = 1; allocated = true; break; } } Il moving to next chunk chunk = (chunkhead *) chunk->next; } if(!allocated) { Il could not be allocated return NULL; } else { // returning chunk address chunk = (chunkhead *) chunk->next; } if(!allocated) { // could not be allocated return NULL; } else { // returning chunk address return (unsigned char *) chunk + sizeof(chunkhead); } } void myfree(unsigned char *address) { // NULL address is not freed if(address NULL) { return; } == // getting chunk chunkhead *chunk = (chunkhead *) (address - sizeof(chunkhead)); // freeing chunk chunk->info = 0; == if(chunk (chunkhead *) myheap) { // head chunk return; } // getting previous and next chunks chunkhead *next = (chunkhead *) chunk->next; chunkhead *prev = (chunkhead *) chunk->prev; if(prev != NULL && prev->info == 0 && next != NULL && next->info == 0) { // previous and next chunks are free // so, remove this chunk and link both ends prev->next = (unsigned char *) next; next->prev = (unsigned char *) prev; } } prev->next = (unsigned char *) next; next->prev = (unsigned char *) prev; } void analyse() { // head of the chunkhead list const chunkhead *list = (chunkhead *) myheap; // traversing the list int chunkNumber = 1; while(list != NULL) { // printing chunk info printf("Chunk #%d ", chunkNumber); printf("Size = %d bytes ", list->size); printf("%s ", list->info ? "Occupied" : "Free"); printf("Next = 0x%08x ", (unsigned int) list->next); printf("Prev = Ox%08x ", (unsigned int) list->prev); // moving to next chunk ++chunkNumber; list = (chunkhead *) list->next; } } Here is the snapshot of a demo run; gcc dma, s . /a.out Chunk #1 size = 1000 bytes Free Next = 0X00442fco Prev = Ox00000000 Chunk #2 Size = 1000 bytes Exercise: Based on lab 3, remove the static heap array and use brk() and sbrk() commands to make the heap. Also, imlement "best fit". Howto: . . Be aware, that the heap size starts at 0, which means, you don't even have a chunk header. Make sure to catch that condition! Maybe with a global variable "heapsize"? From here on, when mymalloc is called, move the program break as far as you need to allocate your first chunk. This time make sure, that the chunkhead is part of the PAGESIZE! Also, assume the PAGESIZE is 4096 bytes. From now on, move through the chunklist similar to lab3, but if no chunk is free, move the program break further and assign a new chunk! If some earlier chunk is free and you allocate less size than that, split as usual. Move the program break back again when the last chunk in the list is removed! You analyse function should print the address of the program break! Best fit: Search the chunks for the smallest possible chunk which satisfies the request. . . . Submit: The whole project folder zipped as filename: program2.zip How we test: byte*a[100); analyze();//50% points for(int i=0;inext; ch = (chunkhead*)ch->next); return ch; } void analyze() { printf(" - if(!startofheap) { printf("no heap"); return; "); chunkhead* ch = (chunkhead*)startofheap; for (int no=0; ch; ch = (chunkhead*)ch->next, no++) { printf("%d | current addr: %x 1", no, ch); printf("size: %d ", ch->size); printf("info: %d ", ch->info); printf("next: %x", ch->next); printf("prev: %x", ch->prev); printf(" "); } printf("program break on address: %x ", sbrk(@)); } Result for comparison no heap, program break on address: 5ff89000 o current addr: 5fff9000 size: 368640 | info: 01 next: 60053000 | prev: 0 1 I current addr: 60053000 size: 4096 | info: 1 | next: 60054000 | prev: 5fff9000 2 current addr: 60054000 Isize: 4096 | info: 1 | next: 60055000 prev: 60053000 3 | current addr: 60055000 size: 4096 | info: 1 | next: 60056000 | prev: 60054000 4 | current addr: 60056000 size: 4096 | info: 1 | next: 60057000 l prev: 60055000 5 | current addr: 60057000 size: 4096 | info: 1 | next: 60058000 | prev: 60056000 6 | current addr: 60058000 size: 4096 | info: 1 | next: 60059000 | prev: 60057000 7 | current addr: 60059000 size: 4096 | info: 1 | next: 6005a000 | prev: 60058000 8 I current addr: 6005a000 size: 4096 | info: 1 | next: 60056000 prev: 60059000 9 | current addr: 6005b000 size: 4096 | info: il next: 60050000 | prev: 6005a000 10 | current addr: 60050000 size: 4096 | info: 1 | next: 0 prev: 60056000 program break on address: 60050000 0 1 current addr: 5fff9000 size: 368640 | info: 0 | next: 60053000 | prev: 0 1 1 current addr: 60053000 size: 4096 | info: 1 | next: 60054000 prev: 5ff9000 2 I current addr: 60054000 size: 4096 | info: 1 l next: 60055000 | prev: 60053000 3 | current addr: 60055000 size: 4096 | info: 1 | next: 60056000 | prev: 60054000 4 | current addr: 60056000 size: 4096 | info: 1 | next: 60057000 | prev: 60055000 5 | current addr: 60057000 size: 4096 | info: 1 | next: 60058000 | prev: 60056000 6 1 current addr: 60058000 size: 4096 | info: 1 | next: 60059000 | prev: 60057000 7 I current addr: 60059000 | size: 4096 | info: 1 | next: 6005a000 | prev: 60058000 8 I current addr: 6005a000 size: 4096 | info: 1 l next: 6005b000 | prev: 60059000 9 | current addr: 6005b000 size: 4096 | info: 1 | next: 60050000 | prev: 60052 000 10 | current addr: 60050000 size: 4096 | info: 1 | next: 0 prev: 6005b000 program break on address: 60050000 no heap, program break on address: 5ff19000 Bonus: We will measure the performance of your code on one and the same computer. The 5 fastest get 2% bonus on the whole course grade. Be creative! My results: 521 micro seconds (VirtualBox, Xubuntu, i7-4770, 3.4 GHz) Test case for speed test (same as above, no print statement except time duration): byte*a[100]; clock_t ca, cb; for(int i=0; i #include #include // heap declaration #define 1MB 1048576 unsigned char myheap[_1MB]; #define PAGESIZE 1024 // chunkhead data structure typedef struct chunkhead { unsigned int size; unsigned int info; unsigned char *next, *prev; } chunkhead; // function declarations unsigned char *mymalloc(unsigned int size); void myfree(unsigned char *address); void analyse(); // main void main() { // testing code unsigned char *a, *b, *c; a = mymalloc(1000); b = mymalloc(1000); C = mymalloc(1000); myfree(a); myfree(b); myfree(c); // analysis analyse(); Il exiting exit(EXIT SUCCESS); } Il function definitions unsigned char *mymalloc(unsigned int size) { // head of the chunkhead list chunkhead #list = (chunkhead *) myheap; // run only the first time mymalloc is called // to initialize myheap static bool initialized = false; if(!initialized) { *list = (chunkhead) { size = sizeof(myheap) - sizeof(chunkhead), info = 0, .next = 0, .prev = 0, }; initialized = true; } == // checking list head for size if(list->info 0){ // memory is free if(size == list->size) { // perfect fit list->info = 1; // marking memory as occupied // returning chunk address return (unsigned char *) list + sizeof(chunkhead); } else if(size + sizeof(chunkhead) size) { Il chunkhead of next chunk can fit in Il shrinking chunk unsigned int oldSize list->size = size; list->size; 1/ splitting memory chunkhead *oldNext = (chunkhead *) list->next; chunkhead *newNext = (chunkhead *) list + sizeof(chunkhead) + size *newNext = (chunkhead) { size = oldSize - sizeof(chunkhead) - size, info = 0, .next = (unsigned char *) oldNext, .prev = (unsigned char *) list, }; list->next = (unsigned char *) newNext; if(oldNext != NULL) { oldNext->prev = (unsigned char *) newNext; } // marking memory as occupied list->info = 1; // returning chunk address return (unsigned char *) list + sizeof(chunkhead); } } // set to false since the chunk // has not yet been allocated bool allocated = false; Il cannot allocate in head, // find available chunk chunkhead *chunk = (chunkhead *) list->next; // traversing the list while(!allocated && chunk != NULL) { if(chunk->info == 0) { // memory is free if(size == chunk->size) { // perfect fit chunk->info = 1;// marking memory as occupied allocated = true; break; } else if(size + sizeof(chunkhead) size) { Il chunkhead of next chunk can fit in if(chunk->info == 0) { // memory is free if(size chunk->size) { // perfect fit chunk->info = 1;// marking memory as occupied allocated = true; break; } else if(size + sizeof(chunkhead) size) { Il chunkhead of next chunk can fit in // shrinking chunk unsigned int oldSize = chunk->size; chunk->size = size; // splitting memory chunkhead *oldNext = (chunkhead *) chunk->next; chunkhead *newNext = (chunkhead *) chunk + sizeof(chunkhead) + size; *newNext = (chunkhead) { size = oldSize - sizeof(chunkhead) - size, info = 0, .next = (unsigned char *) oldNext, .prev = (unsigned char *) chunk, }; chunk->next = (unsigned char *) new Next; if(oldNext != NULL) { oldNext->prev = (unsigned char *) newNext; } // marking memory as occupied chunk->info = 1; allocated = true; break; } } Il moving to next chunk chunk = (chunkhead *) chunk->next; } if(!allocated) { Il could not be allocated return NULL; } else { // returning chunk address chunk = (chunkhead *) chunk->next; } if(!allocated) { // could not be allocated return NULL; } else { // returning chunk address return (unsigned char *) chunk + sizeof(chunkhead); } } void myfree(unsigned char *address) { // NULL address is not freed if(address NULL) { return; } == // getting chunk chunkhead *chunk = (chunkhead *) (address - sizeof(chunkhead)); // freeing chunk chunk->info = 0; == if(chunk (chunkhead *) myheap) { // head chunk return; } // getting previous and next chunks chunkhead *next = (chunkhead *) chunk->next; chunkhead *prev = (chunkhead *) chunk->prev; if(prev != NULL && prev->info == 0 && next != NULL && next->info == 0) { // previous and next chunks are free // so, remove this chunk and link both ends prev->next = (unsigned char *) next; next->prev = (unsigned char *) prev; } } prev->next = (unsigned char *) next; next->prev = (unsigned char *) prev; } void analyse() { // head of the chunkhead list const chunkhead *list = (chunkhead *) myheap; // traversing the list int chunkNumber = 1; while(list != NULL) { // printing chunk info printf("Chunk #%d ", chunkNumber); printf("Size = %d bytes ", list->size); printf("%s ", list->info ? "Occupied" : "Free"); printf("Next = 0x%08x ", (unsigned int) list->next); printf("Prev = Ox%08x ", (unsigned int) list->prev); // moving to next chunk ++chunkNumber; list = (chunkhead *) list->next; } } Here is the snapshot of a demo run; gcc dma, s . /a.out Chunk #1 size = 1000 bytes Free Next = 0X00442fco Prev = Ox00000000 Chunk #2 Size = 1000 bytes
