CS 61C L06 C Memory Management (1) Garcia, Fall 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture 6 – C Memory Management 2004-09-13Cal ranked in the top 10!⇒ After a convincing win overAir Force, we’re now ranked #10 in allpolls (USA/ESPN/AP). We face SouthernMiss (1-0) on Thursday. Barry Bondsalso homered to reach 699 HRs!CS 61C L06 C Memory Management (2) Garcia, Fall 2004 © UCBClarifications to Friday’s lecturestruct point { int x; int y;}should have been written struct point { int x; int y;};CS 61C L06 C Memory Management (3) Garcia, Fall 2004 © UCBWhere allocated?• Structure declaration does notallocate memory• Variable declaration does allocatememory• If declare outside a procedure,allocated in static storage• If declare inside procedure,allocated on the stackand freed whenprocedure returns.- NB: main() is aprocedureint myGlobal;main() { int myTemp;}CS 61C L06 C Memory Management (4) Garcia, Fall 2004 © UCBThe Stack• Stack frame includes:• Return address• Parameters• Space for other local variables• Stack frames contiguousblocks of memory; stack pointertells where top stack frame is• When procedure ends, stackframe is tossed off the stack;frees memory for future stackframesframeframeframeframeSPCS 61C L06 C Memory Management (5) Garcia, Fall 2004 © UCBStack• Last In, First Out (LIFO) memoryusagemain (){ a(0); }void a (int m){ b(1); }void b (int n){ c(2); }void c (int o){ d(3); }void d (int p){ }stackStack PointerStack PointerStack PointerStack PointerStack PointerCS 61C L06 C Memory Management (6) Garcia, Fall 2004 © UCB• Pointers in C allow access to deallocatedmemory, leading to hard-to-find bugs !int * ptr () {int y;y = 3;return &y;};main () {int *stackAddr,content;stackAddr = ptr();content = *stackAddr;printf("%d", content); /* 3 */content = *stackAddr;printf("%d", content); /*13451514 */};Who cares about stack management?mainptr()(y==3)SPmainSPmainprintf()(y==?)SPCS 61C L06 C Memory Management (7) Garcia, Fall 2004 © UCBC Memory Management• C has 3 pools of memory• Static storage: global variable storage,basically permanent, entire program run• The Stack: local variable storage,parameters, return address(location of "activation records" in Java or"stack frame" in C)• The Heap (dynamic storage): data livesuntil deallocated by programmer• C requires knowing where objects are inmemory, otherwise don't work as expect• Java hides location of objectsCS 61C L06 C Memory Management (8) Garcia, Fall 2004 © UCBThe Heap (Dynamic memory)• Large pool of memory,not allocated in contiguous order• back-to-back requests for heap memorycould result blocks very far apart• where Java new command allocates memory• In C, specify number of bytes of memoryexplicitly to allocate item int *ptr;ptr = (int *) malloc(sizeof(int));/* malloc returns type (void *),so need to cast to right type */•malloc(): Allocates raw, uninitializedmemory from heapCS 61C L06 C Memory Management (9) Garcia, Fall 2004 © UCBReview: Normal C Memory Management• A program’s addressspace contains 4 regions:• stack: local variables,grows downward• heap: space requested forpointers via malloc() ;resizes dynamically,grows upward• static data: variablesdeclared outside main,does not grow or shrink• code: loaded whenprogram starts, does notchangecodestatic dataheapstackFor now, OS somehowprevents accesses between stack and heap (gray hash lines). Wait for virtual memory~ FFFF FFFFhex~ 0hexCS 61C L06 C Memory Management (10) Garcia, Fall 2004 © UCBIntel 80x86 C Memory Management• A C program’s 80x86address space :• heap: space requested forpointers via malloc();resizes dynamically,grows upward• static data: variablesdeclared outside main,does not grow or shrink• code: loaded whenprogram starts, does notchange• stack: local variables,grows downwardcodestatic dataheapstack~ 08000000hexCS 61C L06 C Memory Management (11) Garcia, Fall 2004 © UCBMemory Management• How do we manage memory?• Code, Static storage are easy:they never grow or shrink• Stack space is also easy:stack frames are created anddestroyed in last-in, first-out (LIFO)order• Managing the heap is tricky:memory can be allocated / deallocatedat any timeCS 61C L06 C Memory Management (12) Garcia, Fall 2004 © UCBHeap Management Requirements• Want malloc() and free() to runquickly.• Want minimal memory overhead• Want to avoid fragmentation –when most of our free memory is inmany small chunks• In this case, we might have many freebytes but not be able to satisfy a largerequest since the free bytes are notcontiguous in memory.CS 61C L06 C Memory Management (13) Garcia, Fall 2004 © UCBHeap Management• An example• Request R1 for 100bytes• Request R2 for 1 byte• Memory from R1 isfreed• Request R3 for 50bytesR2 (1 byte)R1 (100 bytes)CS 61C L06 C Memory Management (14) Garcia, Fall 2004 © UCBHeap Management• An example• Request R1 for 100bytes• Request R2 for 1 byte• Memory from R1 isfreed• Request R3 for 50bytesR2 (1 byte)R3?R3?CS 61C L06 C Memory Management (15) Garcia, Fall 2004 © UCBK&R Malloc/Free Implementation• From Section 8.7 of K&R• Code in the book uses some C languagefeatures we haven’t discussed and iswritten in a very terse style, don’t worry ifyou can’t decipher the code• Each block of memory is preceded bya header that has two fields:size of the block anda pointer to the next block• All free blocks are kept in a linked list,the pointer field is unused in anallocated blockCS 61C L06 C Memory Management (16) Garcia, Fall 2004 © UCBK&R Implementation• malloc() searches the free list for ablock that is big enough. If none isfound, more memory is requested fromthe operating system.• free() checks if the blocks adjacent tothe freed block are also free• If so, adjacent free blocks are merged(coalesced) into a single, larger free block• Otherwise, the freed block is just added tothe free listCS 61C L06 C Memory Management (17) Garcia, Fall 2004 © UCBChoosing a block in malloc()• If there are multiple free blocks ofmemory that are big enough for somerequest, how do we choose which oneto use?• best-fit: choose the smallest block that isbig enough for the request• first-fit: choose the first block we see thatis big enough• next-fit: like first-fit but remember wherewe
View Full Document
Unlocking...