Uncooperative LanguagesUncooperative Languagesldots Uncooperative Languagesldots Uncooperative Languagesldots Uncooperative Languagesldots Conservative Garbage CollectionConservative GCConservative GCldots Conservative GCldots Readings and References520 —Spring 2008 — 11CSc 520Principles of ProgrammingLanguages11 : Garbage Collection — UncooperativeLanguagesChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 11Uncooperative LanguagesThere is some information which is necessary in order toperform automatic memory management:1. We need to find the roots of the object graph, i.e. thepointers from the stack, registers, or global variableswhich point to objects on the heap.2. We need to know the size, the beginning, and end ofeach object.3. For each object we need to find which of its fields arepointers.Unfortunately, some languages have been designed sothat it is impossible to determine this information.C and C++ are the two most popular such languages.[2]520 —Spring 2008 — 11Uncooperative Languages...C and C++ don’t separate safe and unsafe features(such as address and bit manipulation) which aresometimes needed in systems programming.Modula-3 has similar unsafe features as C and C++ butthey can be encapsulated into unsafe modules, whichdon’t mess up the safety of the main (safe) part of theprogram.[3]520 —Spring 2008 — 11Uncooperative Languages...Most GC algorithms assume that there is always apointer to the beginning of every object. Depending onthe code generator, that may or may not be true.f(g,s) char (*g)(); char*s;{ int i; int l = strlen(s);for (i = 0; i < l; i++)s[i] = (*g)(s[i]); }There may be no pointer to s[0].[4]520 —Spring 2008 — 11Uncooperative Languages...We need to know1. the roots of the object graph.2. the size, the beginning, and end of each object.3. which object fields are pointers.Finding Roots:Foo*f = new foo; // f = 0x53f36f = NULL; // f*is garbageint i = 0x53f36; // points to f...[5]520 —Spring 2008 — 11Uncooperative Languages...Finding the beginning:char*str = new char[26];strcpy(str, "This is a string");str += 10; // Only ptr to str...Finding pointers:union Unsure {char*str; int i} x;[6]520 —Spring 2008 — 11Conservative Garbage Collection[7]520 —Spring 2008 — 11Conservative GCWorks OK for uncooperative languages (C, C++) wherewe can’t distinguish between pointers and integers.Sometimes fails to reclaim all garbage.Main Ideas:Allocate memory in chunks. Each chunk holds acollection of objects of a certain size (i.e. it’s easy tofind the start of objects).Chunks are numbered. A pointer consists of 12 bits ofchunk number (C) + 20 bits of offset within the chunk(O).[8]520 —Spring 2008 — 11Conservative GC...To check whether a value V = (C, O) is a pointer tosome object we check that1. Heap-bottom ≤ V ≤ Heap-top,2. FirstChunk# ≤ C ≤ LastChunk#3. the offset O is a multiple of the object size in chunkC.[9]520 —Spring 2008 — 11Conservative GC...32 bytes eachList:1 2 3 4 5 6 7size= 8markbitsObjectsChunk 1:. . . . . . . . . . 8 byteseachV:Chunk number Offset within chunk(12 bits) (20 bits)00000000011100000000000000011110ObjectsChunk 7:sizemarkbits= 324K bytesChunk[10]520 —Spring 2008 — 11Readings and ReferencesRead Scott, pp.
View Full Document
Unlocking...