Software Design Notes Storage Management SECTION 9 Storage Management 9.1 INTRODUCTION This section discusses Explorer storate management in Areas and Regions. Garbage Collection (GC) and its special spaces are covered in the section on Garbage Collection. Storage allocation for Lisp objects is implemented on top of a large uniform address space provided by the Virtual Memory System. The collection fo all Lisp objects is known as the Lisp Object Space. Storage Allocation and Garbage Collection manage the mapping of Lisp Object Space to the virtual address space. Both storage allocation and garbage collection are logically above the virtual memory system. The virtual memory system does not understand and therefore cannot assist in a meaningful way in the allocation of address space to Lisp objects. 9.1.1 Areas and Regions. The storage allocation system manages the address space by breaking it down into smaller segments called regions. A region -------- is the smallest quantum of address space managed by the address space management system. Regions in turn belong to areas. ------ Areas are created by explicit commands (see MAKE-AREA). Area creation merely defines the abstract area entity, whose regions ------- are intended to contain objects related in some sense (such as all local objects used by a process). One initial region is created when the area is first made. 9.1.2 Address Space Allocation and Use. Virtual address space is allocated to regions when they are created. The allocation a --------- region is defined by the region's origin (starting virtual ------ address) and its length. Actual occupation (use) of virtual ---------- address space by objects takes place in regions as storage requests are made by the various storage allocation primitives. The general term consing is used to refer to any such allocation ------- of storage, whether to actual cons cells or to other objects. 9-1 Software Design Notes Storage Management Storage is assigned to objects in a linear fashion starting at the origin address of a region. The subset of region locations occupied by objects is defined by the region's free pointer, ------------ which is the next offset at which an object can be given storage. All locations before this pointer have been used. 9.2 AREAS The logical address space is divided into areas. An area defines a set of attributes on the virtual address space that it contains. While an area doesn't really have any virtual address space assigned directly to it, it does contain one or more regions which do. An area is identified by its area number, an integer between 0 and 255. The area number is used as an index into the various area descriptor tables described in Table 9-1 to --------------- obtain the appropriate characteristic of the area. Table 9-1 Area Attributes AREA-NAME A symbol representing the name of the area. AREA-REGION-LIST The region number of the first region in this area. AREA-REGION-BITS A template for the REGION-BITS word for a region allocated in this area. AREA-REGION-SIZE The default size of this area's oldest regions. AREA-MAXIMUM-SIZE The maximum size this area is allowed to occupy or *MOST-POSITIVE-FIXNUM* if unlimited. A further series of attributes are defined by the AREA-REGION- BITS word. When a new region is created it inherits the attributes of the area to which it belongs by using the AREA- REGION-BITS word as a template. These attributes will be described in detail in the paragraph on regions. Logically, the area descriptor table is a table of 5-word entries --------------------- as shown above. In reality, the table exists as five separate tables indexed by the area number, each table corresponding to one of the five words. This makes it easy for the microcode to index into the table and makes the code fairly insensitive to changes in the entry size. Areas can be created by user commands. The area in which general consing occurs can also be controlled from Lisp (see the Storage Management chapter of the Explorer Lisp Reference manual). A ----------------------- 9-2 Software Design Notes Storage Management program may use this feature to allocate related items in a contiguous portion of the virtual address space. This has the effect of increasing "locality of reference" on these data items, which can improve virtual memory paging performance. 9.3 REGIONS A region is a block of contiguous virtual address space which is some multiple of the Address Space Quantum Size of 32 pages. -------------------------- When all the address space assigned to a region has been used by objects, new regions are automatically created as they are needed. The amount of address space allocated to an area's regions is generally unlimited, unless a particular area maximum ------------ size quantity was specified when the area was created. ---- Each region is identified by a number from 0 to 2047. Like an area number, this number is used as an index into any of the region descriptor tables in order to look up information about ------------------------ the region. The region characteristics found in these tables are summarized on Table 9-2 Table 9-2 Region Characteristics REGION-ORIGIN Starting virtual address of the region. REGION-LENGTH The total amount of virtual address space assigned to this region in words. REGION-FREE-POINTER Offset into this region of the next free word that can be allocated. REGION-GC-POINTER Offset into this region of the next object which needs to be scavenged. REGION-BITS Defines various attributes of this region. REGION-LIST-THREAD Region number of the next region in this area's list of regions. The address space allocated to this region are defined by its origin and its length characteristics. A region's allocation is only available for use by objects specifically created in this region's area; that is the address space cannot be used by just any storage request in general. The portion of a region's allocation actually used by objects occurs before the free pointer; the virtual address of the next free can be calculated by adding the region free pointer to the origin address. 9-3 Software Design Notes Storage Management All the regions in an area are linked together in a list. The list is anchored in the AREA-REGION-LIST entry for the area number. The next region in the list is found in the REGION-LIST- THREAD entry indexed by the first region; the third region is in the REGION-LIST-THREAD of the second entry; and so forth until a region number which is a negative number is encountered. The free regions are also linked into a list. This is needed since when the garbage collector "flips" it frees a set of regions. Storage allocation needs to be able to find a free region easily. 9.3.1 Region Bits. The REGION-BITS word defines a number of important attributes of the region. The fields within the region bits word are shown in Figure 9-1 and are discussed here. 31 29 25 24 20 18 16 14 12 9 8 7 5 4 3 2 0 +--+-------+----------+---+-+------+-+-------+-+-+--+-+-+------+ |CC|DTP-FIX| Status |Rep|O| GEN |U| Type |S|V|VO|C|R| Swap | +--+-------+----------+---+-+------+-+-------+-+-+--+-+-+------+ CC: CDR Code Res: Reserved, unused Status: Access and status bits to be used in the hardware virtual memory map Rep: Representation type 0 = list 1 = structure 2,3 unused O: Oldspace meta bit. 0 = old space or free 1 = new space, static space or fixed GEN: Region generation U: Region usage (for future expansion) Type: Space type (see space type code table) S: Scavenger Enable. Value: 1 = Scavenger can touch this area. V: Region zero volatility lock VO: Region volatility C: Cache Inhibit (Explorer II only) R: Reserved, unused Swap: Number of pages the Virtual Memory System should try to swap at a time (Explorer II only) Figure 9-1 Region Bits Area Entry Description 9-4 Software Design Notes Storage Management A regions can store one of two types of data: list objects or structure objects. A structure object is any object other than a list. This is termed a region's representation type. ------------------- The Oldspace meta bit is a bit that is set to zero in the first- level hardware maps for this region when the region is flipped to Oldspace. The map bit can then be used to efficiently implement the Garbage Collector's Oldspace Read Barrier. A region's generation, volatility, and zero volatility lock properties are temporal attributes used to support the Temporal -------- Garbage Collection algorithm. These are described in the section on Garbage Collection. The scavenge enable bit is set when this region is part of the Scavenge Space defined by the garbage collector for a collection. The cache-inhibit bit and the swapin quantum field are used in the Explorer II only. The cache-inhibit means that the virtual memory cache should be disabled for all pages in this region. The swapin quantum is the log (base 2) of the number of pages to try to swap in simultaneously on virtual memory reads in this region. A value of 3, for example, means try to swap in up to 8 (2**3) pages. The space type attribute defines the storage allocation scheme that is used. The encoding of this field is shown in Table 9-3. Table 9-3 Space Type Codes Code Region Type ---- ------------------------ 0 Free 1 Oldspace 2 Newspace 3-8 Unused 9 Static 10 Fixed (static, not growable, no consing) 11 Extra PDL 12 Copyspace 13 Reserved for future use 14-15 Unused 9-5 Software Design Notes Storage Management 9.4 STANDARD AREAS When a machine comes up after a cold boot there are 25 FIXED areas reserved for use by the system itself. The first 11 areas are permanently wired down (not allowed to be swapped out by the virtual memory system) because they are either referenced heavily by the microcode or are referenced at or below the level of the virtual memory system. The system parameters file (LROY-QCOM) specifies these areas and their sizes. As described above, an area is identified by a unique area number. The assignment of these area numbers for the standard areas is made by the LROY- QCOM file. The fixed areas each contain a single region. They are special areas in that their regions may be smaller than the minimum region quantum size of 32 pages. This requires that they be specially handled by the storage allocation mapping system (see the discussion of the Address Space Map Area below). The standard areas are as follows: * Resident Symbol Area (wired) - Contains T and NIL symbols. This area's single region currently always starts at virtual address 0. * System Communication Area (wired) - This area contains various values used by I/O routines and systems utilities. See discussion of SCA below. * Scratch Pad Init Area (wired, read only) - Micro code variables are loaded into this area at startup. * Micro Code Link Area (wired, read only) - Contains the microcode entry points for the miscellaneous operations. * Region Origin Area (wired) - Contains the starting address for each region, indexed by region number. * Region Length Area (wired) - Contains the length of each region, indexed by region number. * Region Bits Area (wired) - Contains the region bits information for each region, indexed by region number. * Region Free Pointer Area (wired) - Contains the region free pointer for each region, indexed by region number. * Device Descriptor Area (wired) - Contains device descriptors for the I/O system. 9-6 Software Design Notes Storage Management * Disk Page Map Area (wired) - Contains the Disk Page Map Table for the Virtual Memory System. * Address Space Map Area (wired) - Contains the Address Space Map. The Address Space Map is a table indexed by the virtual address quantum and indicates the region number of the virtual address. If the region number in the address space map is zero, then either the virtual address has not been allocated to a region or the virtual address belongs to a fixed area. When a zero is found in the Address Space Map the fixed areas are searched to determine which area contains the virtual address. The region number is then determined from the area number, since for fixed areas the region number and area number are the same. * Region GC Pointer Area (fixed) - Contains the GC pointer information for each region, indexed by region number. * Region List Thread Area (fixed) - Contains the list thread for each region, indexed by region number. * Area Name Area (fixed) - Contains the name of each area, indexed by area number. * Area Region List Area (fixed) - Contains the first region number in each area, indexed by area number. * Area Region Bits Area (fixed) - Contains the Region Bits word for each area, indexed by area number. * Area Region Size Area (fixed) - Contains the default region size for each area, indexed by area number. * Area Maximum Size (fixed) - Contains the maximum size for each area, indexed by area number. * Support Entry Vector (fixed, read only) - Contains Lisp functions which are callable by microcode. * Extra PDL Area (fixed) - The Extra PDL Area, or number consing area, is used to reduce the garbage generated when evaluating arithmetic expressions. All bignums and floating point numbers are first consed in the Extra PDL Area. Pointers into the Extra PDL Area are only allowed "in the machine" (see the chapter on garbage collection for a description of the parts of the processor that are "in the machine"). Before a pointer is written into main memory, a check is made to see if the pointer points into the Extra PDL Area. If the pointer being written points into the Extra PDL Area, then the object is copied out of the Extra PDL Area into the default consing area and the pointer is modified to reflect the 9-7 Software Design Notes Storage Management number's new address When the Extra PDL Area is full, all of the pointers in the machine are checked to see if they point into the Extra PDL Area. If a pointer into the Extra PDL Area is found, then the object is copied out of the Extra PDL Area into the default consing area and the pointer is replaced by a pointer to the copy. When there are no more pointers in the machine that point into the Extra PDL Area, then the Extra PDL Area contains only garbage. The address space is then reclaimed by setting the free pointer for each region in the Extra PDL Area to zero (currently there is exactly one region in the Extra PDL Area). * Microcode Entry Area (fixed) - Contains indices into the Microcode Link Area for each microcoded function (see discussion of DTP-U-ENTRY in chapter on data types). * Microcode Entry Debug Info Area (fixed) - Micro entry address or locative indirect micro-code-symbol-area. * Scavenger State Area (fixed) - This single region area contains the stack used by garbage collection depth- first scavenging. * Linear PDL Area (fixed) - The Linear PDL Area contains the Linear PDL (Push Down List, or stack) for the initial process. The Linear PDL (usually just called PDL) is the runtime stack for the process. The currently executing process will have the top part of its PDL cached in the processor's PDL Buffer. Any memory reference to this area results in a page fault so that the virtual memory system can check if the target of the memory reference is really in the PDL Buffer. * Linear Bind PDL Area (fixed) - contains the Special PDL for the initial process. * Working Storage Area - The default cons area; most objects created by users are created in this area. * Permanent Storage Area - Permanent data structures are placed here. * Property List Area - Contains the property lists for symbols. * Print Name String Area - Contains the print names for symbols. * Control Tables Area 9-8 Software Design Notes Storage Management * Non-Resident Symbol Area - Contains most of the symbols in the kernel. * Macro Compiled Program Area (read only) - Contains all compiled functions. In addition, any constant objects, such as lists, are also loaded into this area. This causes naive users to get mysterious error messages about trying to write in a read- only area when they try to do destructive operations (such as RPLACA) on constant objects in compiled functions. * PDL Area - contains the linear PDL, except for the one used by the initial process which is in wired memory. * SG And Bind PDL Area - The SG and Bind PDL Area contains the stack groups and the Special, or Binding, PDL for each process. The Special PDL contains the variable binding information for a process. * Indirection Cell Area - This area is always pointed to by DTP-GC-YOUNG-POINTER's. It is used to keep track of pointers from older to younger generations. * FASL Table Area - The FASL Table is placed here at load time. * FASL Temp Area - Temporary structures created by the Loader are placed here. * Debug Info Area - Contains debug info structures and fields. 9.5 SYSTEM COMMUNICATION AREA The Systems Communication Area contains miscellaneous words that are needed for basic operation and do not rely on the rest of the machine operating. This information is shared by the microcode and Lisp. The file SYS:UCODE;LROY-QCOM contains the definitions of items in this area. The Systems Communication Area is wired and at the fixed address of 1000 (octal). A map of systems communications areas is shown in Figure 9-2. 9-9 Software Design Notes Storage Management Octal Addresses --------- 1000-1046 : Miscellaneous words 1047-1577 : Not used 1600- : swap-in-rqb-origin Figure 9-2 Map of Systems Communications Area The miscellaneous words (1000 - 1-46) are: 1. Area Origin Pointer - Virtual address of the Area Origin Area, which lists the starting virtual address of all fixed areas. 2. Valid Size - Number of words used in a saved band. 3. Object Array Pointer - Unused Unused 4. Ether Free List - Ethernet interrupt-handler variable. 5. Ether Transmit List - Ethernet interrupt-handler variable. 6. Ether Receive List - Ethernet interrupt-handler variable. 7. Band Format - Encodes format number in a saved band: 2000 -> new compressed format, otherwise old expanded format. 8. GC Generation Number - Reserved for value of %GC- GENERATION-NUMBER 9. Device Interrupt Table - Points to the Device Interrupt Table. 10. Temporary - Microcode bashes this at extra-pdl-purge. 11. Free Area Number List - Threaded through area-region- list, end=0. 12. Free Region Number List - Threaded through region-list- thread, end=0. 13. Memory Size - Number of words of main memory. 14. Wired Size - Words of low memory wired down; not all of these words are wired, this is really the virtual 9-10 Software Design Notes Storage Management address of the start of normal pageable memory. 15. Chaos Free List - Chaosnet interrupt-handler variable. 16. Chaos Transmit List - Chaosnet interrupt-handler variable. 17. Chaos Receive List - Chaosnet interrupt-handler variable. 18. Debugger Requests 19. Debugger Keep Alive 20. Debugger Data 1 21. Debugger Data 2 22. Major Version - Major version number of SYSTEM. 23. Desired Microcode Version - Microcode version this world expects. Note: this word may be stored with its data type field starting at bit 24 even though pointer fields are now 25 bits. 24. Highest Virtual Address - (Note: Should have this much room in the paging partition) 25. Pointer Width - 25 26. Descriptor Space Free Pointer - Current allocation pointer in the Device-Descriptor-Area. 27. Page Device Table - Unused 28. System Nupi Descriptor - Pointer to descriptor for system nupi 29. Processor Slot - Ucode stores A-SLOT-IM-IN here. 30. Overtemp Event - SIB will post overtemp events here. 31. Fiber Optic Warning Event - Microcode posts fiber optic warning event her. 32. Nupi Overtemp Event - NUPI Special event: microcode will post overhead special event here with formatter number embedded in bits <3:5> and non-zero value in bits <2:0>. 33. Physical Memory Map - Pointer to a memory table of memory board addresses in A-Memory. 9-11 Software Design Notes Storage Management 34. Keybd Error Event - Keybd error condition; log of possible flaky keyboards. 35. Disk Retry Event - Disk retry condition; log of successful retries after disk errors. 36. Unused SIB Event - Place this address in all the unused SIB event locations 37. Parity Error Event - NuBus parity error; high 8 bits (0-7) with bit 8 on. 38. Parity Error Event 2 - NuBus parity error; part 2 - low 24 bits. 39. Syslog Wrap Event - System log wrap around event. 9-12