K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 80
Текст из файла (страница 80)
While the details of the linkage convention vary from systemto system, the basic concepts are similar across most combinations oftarget machine, operating system, and compiler.Review Questions1. What role does the linkage convention play in the construction of largeprograms? Of interlanguage programs? What facts would the compilerneed to know in order to generate code for an interlanguage call?2. If the compiler knows, at a procedure call, that the callee does not,itself, contain any procedure calls, what steps might it omit from thecalling sequence? Are there any fields in the AR that the callee wouldnever need?6.6 ADVANCED TOPICSThe compiler must arrange for the allocation of space to hold the various runtime structures discussed in Section 6.3.
For some languages, thosestructures have lifetimes that do not fit well into the first-in first-out discipline of a stack. In such cases, the language implementation allocates spacein the runtime heap—a region of memory set aside for such objects andmanaged by routines in a runtime support library. The compiler must alsoarrange storage for other objects that have lifetimes unrelated to the flow of6.6 Advanced Topics 313control, such as many lists in a Scheme program or many objects in a Javaprogram.We assume a simple interface to the heap, namely, a routine allocate(size) and a routine free(address).
The allocate routine takes aninteger argument size and returns the address of a block of space in theheap that contains at least size bytes. The free routine takes the addressof a block of previously allocated space in the heap and returns it to thepool of free space. The critical issues that arise in designing algorithms forexplicitly managing the heap are the speeds of both allocate and free andthe extent to which the pool of free space becomes fragmented into smallblocks.This section sketches the algorithms involved in allocation and reclamation of space in a runtime heap.
Section 6.6.1 focuses on techniques forexplicit management of the heap. Along the way, it describes how toimplement free for each of the schemes. Section 6.6.2 examines implicitdeallocation—techniques that avoid the need for free.6.6.1 Explicit Heap ManagementMost language implementations include a runtime system that provides support functions for the code generated by the compiler. The runtime systemtypically includes provision for management of a runtime heap. The actualroutines that implement the heap may be language specific, as in a Schemeinterpreter or a Java virtual machine, or they may be part of the underlyingoperating system, as in the Posix implementations of malloc and free.While many techniques have been proposed to implement allocate andfree, most of those implementations share common strategies and insights.This section explores a simple strategy, first-fit allocation, that exposes mostof the issues, and then shows how a strategy such as first fit is used toimplement a modern allocator.First-Fit AllocationThe goal of a first-fit allocator is to allocate and free space in the heapquickly.
First fit emphasizes speed over memory utilization. Every blockin the heap has a hidden field that holds its size. In general, the size field islocated in the word preceding the address returned by allocate, as shownin Figure 6.11a. Blocks available for allocation reside on a list called the freelist.
In addition to the mandatory size field, blocks on the free list have additional fields, as shown in Figure 6.11b. Each free block has a pointer to thenext block on the free list (set to null in the last block) and a pointer to theblock itself in the last word of the block. To initialize the heap, the allocatorcreates a free list that contains a single large unallocated block.314 CHAPTER 6 The Procedure Abstractionsizesizenext(a) Allocated Block(b) Free Blockn FIGURE 6.11 Blocks in a First-Fit Allocator.A call allocate(k) causes the following sequence of events: The allocate routine walks the free list until it discovers a block with size greaterthan or equal to k plus one word for the size field.
Assume it finds an appropriate block, bi . It removes bi from the free list. If bi is larger than necessary,allocate creates a new free block from the excess space at the end of biand places that block on the free list. The allocate routine returns a pointerto the second word of bi .If allocate fails to find a large enough block, it tries to extend the heap.If it succeeds in extending the heap, it returns a block of appropriate sizefrom this newly allocated portion of the heap. If extending the heap fails,allocate reports failure (typically by returning a null pointer).To deallocate a block, the program calls free with the address of the block,b j .
The simplest implementation of free adds b j to the head of the free listand returns. This produces a fast free routine. Unfortunately, it leads to anallocator that, over time, fragments memory into small blocks.To overcome this flaw, the allocator can use the pointer at the end of a freedblock to coalesce adjacent free blocks. The free routine loads the word preceding b j ’s size field, which is the end-of-block pointer for the block thatimmediately precedes b j in memory. If that word contains a valid pointer,and it points to a matching block header (one whose address plus size fieldpoints to the start of b j ), then both b j and its predecessor are free.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
