'&$%CSE 303:Concepts and Tools for Software DevelopmentDan GrossmanWinter 2006Lecture 25— Memory-Management IdiomsDan Grossman CSE303 Winter 2006, Lecture 25 1'&$%You have grading to doI am going to distribute course evaluation forms so you may rate the qualityof this course. Your parti cipation is voluntary, and you may omit specificitems if you wish. To ensure confidentiality, do not write your name on theforms. There is a possibility your handwriting on the yellow writtencomment sheet will be recognizable; however, I wi ll not see the results of thisevaluation until after the quarter is over and you have received your grades.Please be sure to use a No. 2 PENCIL ONLY on the scannable form.I have chosen (name) to distribute and collect the forms. When you arefinished, he/she will collect the forms, put them into an envelope and mailthem to the Office of Educational Assessment. If there are no questions, Iwill leave the room and not return until all the questionnaires have beenfinished and collected. Thank you for your parti cipation.I’ll come back at 12:49.Dan Grossman CSE303 Winter 2006, Lecture 25 2'&$%No tools or rules todayReview: Java and C memory-management rulesIdioms for memory-management:• Garbage collection• Unique pointers• Reference Counting• Arenas (a.k.a. regions)Note: Same “problems” with file- handles, network-connections,Java-style iterators, ...Dan Grossman CSE303 Winter 2006, Lecture 25 3'&$%Java rules• Space for loc al variables lasts until end of method-call, but noproblem because cannot get pointer into stack• All “objects” are in the heap; they conc eptually live forever.– Really get reclaimed when they are unreachable (from a stackvariables or global variable).– Static fields are global variables.Consequences:• You rarely think about memory-management.• You can run out of memory without needing to (e.g., long deadlist in a global), but you still get a safe exception.• No dangling-pointer dereferences!• Extra behind-the-scenes space and time for doing the collection.Dan Grossman CSE303 Winter 2006, Lecture 25 4'&$%C rules• Space for loc al variables lasts until end of function-call, may leadto dangling pointers into the stack.• Objects into the heap live until free(p) is called, where p pointsto the beginning of the object.• Therefore, unreachable objects can never be reclaimed.• malloc returns NULL if it cannot find space.• TFMSTCOFa:1. Calling free with a stack pointer or middle pointer.2. Calling free twice with the same pointer.3. Dereferencing a pointer to an object that has been freed.• Usually 1–2 screw up the malloc/free library and 3 screws up anapplication when the space is being used for another object.aThe Following May Set The Computer On FireDan Grossman CSE303 Winter 2006, Lecture 25 5'&$%Garbage Collec tion for CYes, there are garbage collectors for C (and C++)!http://www.hpl.hp.com/personal/Hans_Boehm/gc/• redefines free to do nothing• unlike a Java GC, conservatively thinks an int might be a pointer.Questions to ask yourself in any application:• Why do I want manual memory management?• Why do I want C?Good (and rare!) answers against GC: Tight c ontrol over performance;even short pauses unacce ptable; need to free reachable data.Good (and rare!) answers for C: Need tight control over datarepresentation and/or pointers into the stack.Other answer for C: need easy interoperability with lots of existing codeDan Grossman CSE303 Winter 2006, Lecture 25 6'&$%Why is it hard?This is not really the hard part:free(p);...p->x = 37; // dangling-pointer dereferenceThese are:p = q; // if p was last reference and q!=p, leak!lst1 = append(lst1,lst2);free_list(lst2); // user function, assume it// frees all elements of listlength(lst1); // dangling-pointer dereference// if append does not copy!There are an infinite number of safe idioms , but only a few are knownto be simple enough to get right in large systems...Dan Grossman CSE303 Winter 2006, Lecture 25 7'&$%Idiom 1: Unique PointersEnsure there is exactly one pointer to an object. Then you can callfree on the pointer whenever, and set the pointer’s location to NULLto be “extra careful”.Furthermore, you must free pointers before losing references to them.Hard parts:1. May make no sense for the data-structure/algorithm.2. May lead to extra space because sharing is not allowed.3. Easy to lose references (e.g., p=q;).4. Easy to duplicate references (e.g., p=q;) (must follow withq=NULL;).5. A pain to return unfreed function arguments.Dan Grossman CSE303 Winter 2006, Lecture 25 8'&$%Relaxing UniquenessThis does not preserve uniqueness:void g(int *p1, int*p2) { ... }void f(int *p1, int*p2) {if(...)g(p1,p1);elseg(p1,p2);...free(p1);free(p2);}Wrong if g frees (which with uniqueness it probably should).Wrong in true-branch because caller breaks makes aliases.Dan Grossman CSE303 Winter 2006, Lecture 25 9'&$%Relaxing UniquenessInstead, you allow “unconsumed” pointers:• Callee won’t free them• They will be unique again when function exitsMore often what you want, but changes the contract:• Callee must not free• Callee must not store the pointer anywhere else (in a global, in afield of an object pointed to by another pointer, etc.)Dan Grossman CSE303 Winter 2006, Lecture 25 10'&$%Idiom 2: Reference-CountingStore with an object how many pointers there are to it. When itreaches 0, call free.• Literally a field in each pointed to object.• p=q; becomes decr_count(p); p=q; incr_count(p);• In practice, you can “be careful” and omit ref-count manipulationfor temporary variables.struct Example { int count; ... };void decr_count(struct Example * p) {--p->count;if(p->count == 0)free(p);}void incr_count(struct Example * p) { ++p->count; }Dan Grossman CSE303 Winter 2006, Lecture 25 11'&$%Reference-Counting Problems1. Avoids freeing too early, but one lost reference means a leak.2. Reference-count maintenance expensive and error-prone (C++tricks can automate to some degree).3. CYCLES! (Must break them manually.)Dan Grossman CSE303 Winter 2006, Lecture 25 12'&$%Idiom 3: Arenas (a.k.a. regions)Rather than track each object’s “liveness”, track each object’s“region” and deallocate a region “all at once”.Revised memory-management interface:typedef struct RgnHandle * region_t;region_t create_rgn();void destroy_rgn(region_t);void * rgn_malloc(region_t,int);So now you “only” have to keep track of a pointer’s region and
View Full Document
Unlocking...