CSc 520Principles of Programming Languages42: Garbage Collection — Uncooperative LanguagesChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Uncooperative LanguagesThere is some information which is necessary in order to perform automatic memory management:1. We need to find the roots of the object graph, i.e. the pointers from the stack, registers, or globalvariables which point to objects on the heap.2. We need to know the size, the beginning, and end of each object.3. For each object we need to find which of its fields are pointers.• Unfortunately, some languages have been designed so that it is impossible to determine this information.• C and C++ are the two most popular such languages.2 Uncooperative 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++ but they can be encapsulated into unsafe modules,which don’t mess up the safety of the main (safe) part of the program.3 Uncooperative Languages. . .• Most GC algorithms assume that there is always a pointer to the beginning of every object. Dependingon the 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]); }1There may be no pointer to s[0].4 Uncooperative 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 Uncooperative 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;Conservative Garbage Collection6 Conservative GC• Works OK for uncooperative languages (C, C++) where we can’t distinguish between pointers andintegers. Sometimes fails to reclaim all garbage.Main Ideas:• Allocate memory in chunks. Each chunk holds a collection 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 of chunk number (C) + 20 bits of offset withinthe chunk (O).7 Conservative GC. . .• To check whether a value V = (C, O) is a pointer to some 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 chunk C.28 Conservative GC. . .ChunkList:1 2 3 4 5 6 7size= 8markbitsObjectsChunk 1:. . . . . . . . . . 8 byteseachV:Chunk number Offset within chunk(12 bits) (20 bits)00000000011100000000000000011110ObjectsChunk 7:sizemarkbits= 324K bytes32 bytes each9 Readings and References• Read Scott, pp.
View Full Document