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⪯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¯os?&– “Faster”&than&func+on&calls&• Why?&– For&mal loc&• 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&sec+on&5.12)&int *p int *p[13] int *(p[13]) int **p int (*p)[13] &int *f() int (*f)() int (*(*f())[13])() int (*(*x[3])())[5] p&is&a&pointer&to&int&p&is&an&array[13]&of&pointer&to&int&p&is&an&array[13]&of&pointer&to&int&p&is&a&pointer&to&a&pointer&to&an&int&p&is&a&pointer&to&an&array[13]&of&int&f&is&a&func+on&returning&a&pointer&to&int&f&is&a&pointer&to&a&func+on&returning&int&f&is&a&func+on&returning&ptr&to&an&array[13]&of&pointers&to&func+ons&returning&int&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&– float&to&int,&int&to&float&– <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 0x12341235More&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&memor y&al loca+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&– Resul t&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+onImplementa+on&Hurdles&• How&do&we&know&where&the&chu nks&are?&• How&do&we&know&how&big&the&chunks&are?&• How&do&we&know&which&chunks&are&free?&• Remember:&can’t&buffer&calls&to&malloc&and&free…&must&deal&with&themℜ+me.&• Remember:&calls&to&free&only&takes&a&pointer,¬&a&pointer&and&a&size.&• Solu+on:&Need*a*data*str uc ture*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&th e&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&find&the&next*free*chunk&that&is&“a&good&fit&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&•
View Full Document