Malloc Recita on By sseshadr Agenda Macros in C Pointer declara ons Cas ng and Pointer Arithme c Malloc Macros Macros Run me compile me or pre compile me Constant define NUM ENTRIES 100 OK Macro define twice x 2 x Not OK twice x 1 becomes 2 x 1 define twice x 2 x OK Use lots of parenthesis it s a na ve search and replace Macros Why macros Faster than func on calls Why For malloc Quick access to header informa on payload size valid What s the keyword inline do At compile me replaces func on calls with code Pointer declara ons C operators K R p 53 Operators Associa vity left to right type sizeof right to left left to right left to right left to right left to right left to right left to right left to right left to right left to right left to right right to left right to left left to right Note Unary and have higher precedence than binary forms Review of C Pointer Declara ons K R s ec on 5 12 int p p is a pointer to int int p 13 p is an array 13 of pointer to int int p 13 p is an array 13 of pointer to int int p p is a pointer to a pointer to an int int p 13 p is a pointer to an array 13 of int int f f is a func on returning a pointer to int int f f is a pointer to a func on returning int int f 13 f is a func on returning ptr to an array 13 of pointers to func ons returning int int x 3 5 x is an array 3 of pointers to func ons returning pointers to array 5 of ints Pointer cas ng arithme c and dereferencing Pointer cas ng Separate from non pointer cas ng oat to int int to oat struct a to struct b No gcc error Cast from type a to type b type a to integer unsigned int integer unsigned int to type a Pointer cas ng What actually happens in a pointer cast Nothing It s just an assignment Remember all pointers are the same size The magic happens in dereferencing and arithme c Pointer arithme c The expression ptr a doesn t always evaluate into the arithme c sum of the two Consider type a pointer void pointer2 void pointer a Think about it as leal pointer a sizeof type a pointer2 Pointer arithme c int ptr int 0x12341234 int ptr2 ptr 1 char ptr char 0x12341234 char ptr2 ptr 1 int ptr int 0x12341234 int ptr2 int char ptr 1 void ptr char 0x12341234 void ptr2 ptr 1 void ptr int 0x12341234 void ptr2 ptr 1 Pointer arithme c int ptr int 0x12341234 int ptr2 ptr 1 ptr2 is 0x12341238 char ptr char 0x12341234 char ptr2 ptr 1 ptr2 is 0x12341235 int ptr int 0x12341234 int ptr2 int char ptr 1 ptr2 is 0x12341235 void ptr char 0x12341234 void ptr2 ptr 1 ptr2 is 0x12341235 void ptr int 0x12341234 void ptr2 ptr 1 ptr2 is still 0x12341235 More pointer arithme c int ptr int 0x12341234 int ptr2 int ptr 1 char ptr char 0x12341234 short ptr2 short ptr 1 int ptr int 0x12341234 void ptr2 ptr 1 int ptr int 0x12341234 void ptr2 void ptr 1 This is on a 64 bit machine More pointer arithme c int ptr int 0x12341234 int ptr2 int ptr 1 ptr2 0x1234123c char ptr char 0x12341234 short ptr2 short ptr 1 ptr2 0x1234123c int ptr int 0x12341234 void ptr2 ptr 1 ptr2 ptr2 is actually 8 bytes higher than the address of the variable ptr int ptr int 0x12341234 void ptr2 void ptr 1 ptr2 ptr2 is just one higher than the value at 0x12341234 so probably segfault Pointer dereferencing Basics It must be a POINTER type or cast to one at the me of dereference Cannot dereference void The result must get assigned into the right datatype or cast into it Pointer dereferencing What gets returned int ptr1 malloc 100 ptr1 0xdeadbeef int val1 ptr1 int val2 int char ptr1 What are val1 and val2 Pointer dereferencing What gets returned int ptr1 malloc sizeof int ptr1 0xdeadbeef int val1 ptr1 int val2 int char ptr1 val1 0xdeadbeef val2 0xffffffef What happened Malloc Malloc basics What is dynamic memory alloca on Terms you will need to know malloc calloc realloc free sbrk payload fragmenta on internal vs external coalescing Bi direc onal Immediate vs Deferred Fragmenta on Internal fragmenta on Result of payload being smaller than block size void m1 malloc 3 void m1 malloc 3 m1 m2 both have to be aligned to 8 bytes External fragmenta on Implementa on Hurdles How do we know where the chunks are How do we know how big the chunks are How do we know which chunks are free Remember can t bu er calls to malloc and free must deal with them real me Remember calls to free only takes a pointer not a pointer and a size Solu on Need a data structure to store informa on on the chunks Where do I keep this data structure The data structure Requirements The data structure needs to tell us where the chunks are how big they are and whether they re free We need to be able to CHANGE the data structure during calls to malloc and free We need to be able to nd the next free chunk that is a good t for a given payload We need to be able to quickly mark a chunk as free allocated We need to be able to detect when we re out of chunks What do we do when we re out of chunks The data structure It would be convenient if it worked like malloc struct malloc data structure ptr malloc 100 malloc data structure free ptr malloc data structure Instead all we have is the memory we re giving out All of it doesn t have to be payload We can use some of that for our data structure The data structure The data structure IS your memory A start h1 pl1 h2 pl2 h3 pl3 What goes in the header That s your job Lets say somebody calls free p2 how can I coalesce Maybe you need a footer Maybe not The data structure Common types Implicit List Root chunk1 chunk2 chunk3 Explicit List Root free chunk 1 free chunk 2 free chunk 3 Segregated List Small malloc root free small chunk 1 free small chunk 2 Medium malloc root free medium chunk 1 Large malloc root free large chunk1 Design considera ons I found a chunk that ts the necessary payload should I look for a beper t or not Spliqng a free block void ptr malloc 200 free ptr ptr malloc 50 use same space then mark remaining bytes as free void ptr malloc 200 free ptr ptr malloc 192 use same space then mark remaining bytes as free Design Considera ons Free blocks address ordered or LIFO What s the di erence Pros and …
View Full Document
Unlocking...