Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 80

The freeroutine can combine them by increasing the predecessor’s size field and storing the appropriate pointer at the end of bj . Combining these blocks lets freeavoid updating the free list.To make this scheme work, allocate and free must maintain the end-ofblock pointers. Each time that free processes a block, it must update thatpointer with the address of the head of the block. The allocate routinemust invalidate either the next pointer or the end-of-block pointer to preventfree from coalescing a freed block with an allocated block in which thosefields have not been overwritten.The free routine can also try to combine bj with its successor in memory,bk .

It can use bj ’s size field to locate the start of bk . It can use bk ’s size fieldand end-of-block pointer to determine if bk is free. If bk is free, then free6.6 Advanced Topics 315ARENA-BASED ALLOCATIONInside the compiler itself, the compiler writer may find it profitable to usea specialized allocator. Compilers have phase-oriented activity. This lendsitself well to an arena-based allocation scheme.With an arena-based allocator, the program creates an arena at the beginning of an activity.

It uses the arena to hold allocated objects that arerelated in their use. Calls to allocate objects in the arena are satisfied ina stacklike fashion; an allocation involves incrementing a pointer to thearena’s high-water mark and returning a pointer to the newly allocatedblock. No call is used to deallocate individual objects; they are freed whenthe arena that contains them is deallocated.The arena-based allocator is a compromise between traditional allocatorsand garbage-collecting allocators. With an arena-based allocator, the callsto allocate can be made lightweight (as in the modern allocator). Nofreeing calls are needed; the program frees the entire arena in a single callwhen it finishes the activity for which the arena was created.can combine the two blocks, removing bk from the free list, adding bj to thefree list, and updating bj ’s size field and end-of-block pointer appropriately.To make the free-list update efficient, the free list should be a doubly linkedlist.

Of course, the pointers are stored in unallocated blocks, so the spaceoverhead is irrelevant. Extra time required to update the doubly linked freelist is minimal.As described, the coalescing scheme depends on the fact that the relationshipbetween the final pointer and the size field in a free block are absent in anallocated block. While it is extremely unlikely that the allocator will identifyan allocated block as free, this can happen. To ensure against this unlikelyevent, the implementor can make the end-of-block pointer a field that existsin both allocated and free blocks. On allocation, the pointer is set to containan address outside the heap, such as zero. On freeing, the pointer is set tothe block’s own address.

The cost of this added assurance is an extra field ineach allocated block and an extra store for each allocation.Many variations on first-fit allocation have been tried. They trade off thecost of allocate, the cost of free, the amount of fragmentation producedby a long series of allocations, and the amount of space wasted by returningblocks larger than requested.Multipool AllocatorsModern allocators are derived from first-fit allocation but simplified by acouple of observations about the behavior of programs. As memory sizes316 CHAPTER 6 The Procedure Abstractiongrew in the early 1980s, it became reasonable to waste some space if doingso led to faster allocation.

At the same time, studies of program behaviorsuggested that real programs allocate memory frequently in a few commonsizes and infrequently in large or unusual sizes.Modern allocators use separate memory pools for several common sizes.Typically, selected sizes are powers of two, starting with a small block size(such as 16 bytes) and running up to the size of a virtual-memory page (typically 4096 or 8192 bytes). Each pool has only one size of block, so allocatecan return the first block on the appropriate free list, and free can simplyadd the block to the head of the appropriate free list. For requests largerthan a page, a separate first-fit allocator is used.

Allocators based on theseideas are fast. They work particularly well for heap allocation of activationrecords.These changes simplify both allocate and free. The allocate routinemust check for an empty free list and adds a new page to the free list if itis empty. The free routine inserts the freed block at the head of the freelist for its size.

A careful implementation could determine the size of a freedblock by checking its address against the memory segments allocated foreach pool. Alternative schemes include using a size field as before, and, ifthe allocator places all the storage on a page into a single pool, storing thesize of the blocks in a page in the first word of the page.Debugging HelpPrograms written with explicit allocation and deallocation are notoriouslydifficult to debug.

It appears that programmers have difficulty decidingwhen to free heap-allocated objects. If the allocator can quickly distinguish between an allocated object and a free object, then the heapmanagement software can provide the programmer with some help indebugging.For example, to coalesce adjacent free blocks, the allocator needs a pointerfrom the end of a block back to its head. If an allocated block has that pointerset to an invalid value, then the deallocation routine can check that fieldand report a runtime error when the program attempts to deallocate a freeblock or an illegal address—a pointer to anything other than the start of anallocated block.For a modest additional overhead, heap-management software can provideadditional help.

By linking together allocated blocks, the allocator can createan environment for memory-allocation debugging tools. A snapshot tool canwalk the list of allocated blocks. Tagging blocks by the call site that createdthem lets the tool expose memory leaks. Timestamping them allows the tool6.6 Advanced Topics 317to provide the programmer with detailed information about memory use.Tools of this sort can provide invaluable help in locating blocks that arenever deallocated.6.6.2 Implicit DeallocationMany programming languages support implicit deallocation of heap objects.The implementation deallocates memory objects automatically when theyare no longer in use.

This requires some care in the implementation ofboth the allocator and the compiled code. To perform implicit deallocation,or garbage collection, the compiler and runtime system must include amechanism for determining when an object is no longer of interest, or dead,and a mechanism for reclaiming and recycling the dead space.The work associated with garbage collection can be performed incrementally, for individual statements, or it can be performed as a batch-orientedtask that runs on demand, when the free-space pool is exhausted.

Reference counting is a classic way to perform incremental garbage collection.Mark-sweep collection is a classic approach to performing batch-orientedcollection.Reference CountingThis technique adds a counter to each heap-allocated object. The countertracks the number of outstanding pointers that refer to the object. When theallocator creates the object, it sets the reference count to one. Each assignment to a pointer variable adjusts two reference counts.

It decrements thereference count of the pointer’s preassignment value and increments thereference count of the pointer’s postassignment value. When an object’s reference count drops to zero, no pointer exists that can reach the object, sothe system may safely free the object.

Freeing an object can, in turn, discardpointers to other objects. This must decrement the reference counts of thoseobjects. Thus, discarding the last pointer to an abstract syntax tree shouldfree the entire tree. When the root node’s reference count drops to zero, it isfreed and its descendant’s reference counts are decremented. This, in turn,should free the descendants, decrementing the counts of their children. Thisprocess continues until the entire ast has been freed.The presence of pointers in allocated objects creates problems for referencecounting schemes, as follows:1. The running code needs a mechanism to distinguish pointers from otherdata.

It may either store extra information in the header field for eachobject or limit the range of pointers to less than a full word and use theGarbage collectionthe implicit deallocation of objects that reside onthe runtime heap318 CHAPTER 6 The Procedure Abstractionremaining bits to “tag” the pointer. Batch collectors face the sameproblem and use the same solutions.2. The amount of work done for a single decrement can grow quite large.If external constraints require bounded deallocation times, the runtimesystem can adopt a more complex protocol that limits the number ofobjects deallocated for each pointer assignment.

By keeping a queue ofobjects that must be freed and limiting the number handled on eachreference-count adjustment, the system can distribute the cost offreeing objects over a larger set of operations. This amortizes the cost offreeing over the set of all assignments to heap-allocated objects andbounds the work done per assignment.3. The program might form cyclic graphs with pointers. The referencecounts for a cyclic data structure cannot be decremented to zero.