Old design

Warning

Much of the documentation in this section is very old: some of it dates back to the origin of the MPS in 1995. It has not been brought up to date or checked for correctness, so it is mainly of historical interest. As pieces of documentation are brought up to date, they will be moved to the main Design section.

• 1. Allocation frame protocol
  • 1.1. Introduction
  • 1.2. Definitions
  • 1.3. Purpose
  • 1.4. Requirements
    • 1.4.1. Known requirements
    • 1.4.2. Proto-requirements
  • 1.5. Overview
  • 1.6. Operations
  • 1.7. Interface
    • 1.7.1. External types
    • 1.7.2. External functions
    • 1.7.3. Internal types
  • 1.8. Lightweight frames
    • 1.8.1. Overview
    • 1.8.2. Synchronization
    • 1.8.3. Implementation
• 2. Arena
  • 2.1. Introduction
  • 2.2. Overview
  • 2.3. Definitions
  • 2.4. Requirements
    • 2.4.1. Block management
    • 2.4.2. Address translation
    • 2.4.3. Arena partition
    • 2.4.4. Constraints
  • 2.5. Architecture
    • 2.5.1. Statics
    • 2.5.2. Arena classes
    • 2.5.3. Chunks
    • 2.5.4. Tracts
    • 2.5.5. Control pool
    • 2.5.6. Polling
    • 2.5.7. Commit limit
    • 2.5.8. Spare committed (aka “hysteresis”)
    • 2.5.9. Pause time control
    • 2.5.10. Locks
    • 2.5.11. Location dependencies
    • 2.5.12. Finalization
  • 2.6. Implementation
    • 2.6.1. Tract cache
    • 2.6.2. Control pool
    • 2.6.3. Traces
    • 2.6.4. Polling
    • 2.6.5. Location dependencies
    • 2.6.6. Roots
• 3. Virtual Memory Arena
  • 3.1. Introduction
  • 3.2. Overview
  • 3.3. Notes
  • 3.4. Requirements
    • 3.4.1. Placement
    • 3.4.2. Arena partition
  • 3.5. Architecture
  • 3.6. Solution ideas
  • 3.7. Data structures
  • 3.8. Notes
• 4. Bit tables
  • 4.1. Introduction
  • 4.2. Definitions
  • 4.3. Requirements
  • 4.4. Non requirements
  • 4.5. Background
  • 4.6. Clients
  • 4.7. Overview
  • 4.8. Interface
  • 4.9. Detailed design
    • 4.9.1. Data structures
    • 4.9.2. Functions
  • 4.10. Testing
  • 4.11. References
• 5. Allocation buffers and allocation points
  • 5.1. Introduction
  • 5.2. Glossary
  • 5.3. Source
  • 5.4. Requirements
  • 5.5. Classes
  • 5.6. Logging
  • 5.7. Measurement
  • 5.8. Notes from the whiteboard
  • 5.9. Synchronization
  • 5.10. Interface
  • 5.11. Diagrams
• 6. Checking
  • 6.1. Introduction
  • 6.2. Implementation
  • 6.3. Common assertions
• 7. Collection framework
  • 7.1. Introduction
  • 7.2. Overview
  • 7.3. Collection abstractions
    • 7.3.1. Colours, scanning and fixing
    • 7.3.2. Reference sets
  • 7.4. The tracer
    • 7.4.1. The condemn phase
    • 7.4.2. The grey mutator phase
    • 7.4.3. The flip phase
    • 7.4.4. The black mutator phase
    • 7.4.5. The reclaim phase
  • 7.5. Barriers
    • 7.5.1. Hardware barriers
    • 7.5.2. Software barriers
• 8. Diagnostic feedback
  • 8.1. Introduction
  • 8.2. Overview
  • 8.3. Requirements
  • 8.4. Usage
  • 8.5. How to write a diagnostic
    • 8.5.1. Compile away in non-diag varieties; no side effects
    • 8.5.2. Writing good paragraph text
  • 8.6. How the MPS diagnostic system works
    • 8.6.1. Parts of the MPS diagnostic system
    • 8.6.2. Statistics
    • 8.6.3. Related systems
  • 8.7. References
• 9. The generic fix function
  • 9.1. Introduction
  • 9.2. Was-marked protocol
  • 9.3. Implementation
• 10. I/O subsystem
  • 10.1. Introduction
  • 10.2. Background
  • 10.3. Purpose
  • 10.4. Requirements
    • 10.4.1. General
    • 10.4.2. Functional
  • 10.5. Architecture
    • 10.5.1. Example configurations
  • 10.6. Interface
    • 10.6.1. I/O module state
    • 10.6.2. Message types
    • 10.6.3. Limits
    • 10.6.4. Interface set-up and tear-down
    • 10.6.5. Message send and receive
  • 10.7. I/O module implementations
    • 10.7.1. Routeing
  • 10.8. Notes
  • 10.9. Attachments
• 11. Library interface
  • 11.1. Introduction
  • 11.2. Goals
  • 11.3. Description
    • 11.3.1. Overview
  • 11.4. Implementation
• 12. Locus manager
  • 12.1. Introduction
  • 12.2. Overview
    • 12.2.1. Why is it important to manage address space?
    • 12.2.2. Discovering the layout
  • 12.3. Definitions
  • 12.4. Requirements
  • 12.5. Analysis
  • 12.6. Interface
    • 12.6.1. Loci
    • 12.6.2. Peaks
  • 12.7. Architecture
    • 12.7.1. Data objects
    • 12.7.2. Overview of strategy
    • 12.7.3. Allocation
    • 12.7.4. Deallocation
    • 12.7.5. Region placement recomputation
  • 12.8. Implementation
  • 12.9. Notes
• 13. GC messages
  • 13.1. Introduction
  • 13.2. Overview
  • 13.3. Introduction
  • 13.4. Purpose
  • 13.5. Names and parts
  • 13.6. Lifecycle
    • 13.6.1. Requirements
    • 13.6.2. Storage
    • 13.6.3. Creating and Posting
    • 13.6.4. Getting and discarding
    • 13.6.5. Final clearup
  • 13.7. Testing
    • 13.7.1. Coverage
• 14. Debugging features for client objects
  • 14.1. Introduction
  • 14.2. Overview
  • 14.3. Requirements
  • 14.4. Solution ideas
  • 14.5. Architecture
  • 14.6. Client interface
  • 14.7. Examples
  • 14.8. Implementation
• 15. AMC pool class
  • 15.1. Introduction
  • 15.2. Guide
    • 15.2.1. Segment states
    • 15.2.2. Pads
    • 15.2.3. Placement pads are okay
    • 15.2.4. Retained pads could be a problem
    • 15.2.5. Small, medium, and large segments
    • 15.2.6. The LSP payoff calculation
    • 15.2.7. Retained pages
    • 15.2.8. Feedback about retained pages
  • 15.3. Initial design
    • 15.3.1. Introduction
    • 15.3.2. Overview
    • 15.3.3. Definitions
    • 15.3.4. Segments
    • 15.3.5. Fixing and nailing
    • 15.3.6. Emergency tracing
    • 15.3.7. Buffers
    • 15.3.8. Types
    • 15.3.9. Generations
    • 15.3.10. Ramps
    • 15.3.11. Headers
    • 15.3.12. Old and aging notes below here
• 16. AMS pool class
  • 16.1. Introduction
  • 16.2. Overview
  • 16.3. Requirements
  • 16.4. Architecture
    • 16.4.1. Subclassing
    • 16.4.2. Allocation
    • 16.4.3. Colours
    • 16.4.4. Scanning
  • 16.5. Implementation
    • 16.5.1. Colour
    • 16.5.2. Iteration
    • 16.5.3. Scanning Algorithm
    • 16.5.4. Allocation
    • 16.5.5. Initialization
    • 16.5.6. Condemnation
    • 16.5.7. Reclaim
    • 16.5.8. Segment merging and splitting
  • 16.6. Testing
  • 16.7. Notes
• 17. AWL pool class
  • 17.1. Introduction
  • 17.2. Requirements
  • 17.3. Definitions
  • 17.4. Overview
  • 17.5. Interface
  • 17.6. Data structures
  • 17.7. Functions
    • 17.7.1. External
    • 17.7.2. Internal
  • 17.8. Test
• 18. LO pool class
  • 18.1. Introduction
  • 18.2. Definitions
  • 18.3. Requirements
  • 18.4. Overview
  • 18.5. Interface
  • 18.6. Data structures
  • 18.7. Functions
    • 18.7.1. External
    • 18.7.2. Internal
  • 18.8. Attachment
• 19. MFS pool class
  • 19.1. Overview
  • 19.2. Implementation
• 20. MRG pool class
  • 20.1. Introduction
  • 20.2. Goals
  • 20.3. Requirements
  • 20.4. Terminology
  • 20.5. Overview
  • 20.6. Protocols
    • 20.6.1. Object Registration
    • 20.6.2. Finalizer execution
    • 20.6.3. Setup / destroy
  • 20.7. Data structures
  • 20.8. Functions
  • 20.9. Transgressions
  • 20.10. Future
  • 20.11. Tests
    • 20.11.1. Functionality
    • 20.11.2. Attributes
    • 20.11.3. Implementation
  • 20.12. Notes
• 21. Manual Variable Temporal (MVT) pool design
  • 21.1. Introduction
  • 21.2. Definitions
  • 21.3. Abbreviations
  • 21.4. Overview
  • 21.5. Requirements
    • 21.5.1. Critical requirements
    • 21.5.2. Essential requirements
    • 21.5.3. Nice requirements
  • 21.6. Architecture
  • 21.7. Analysis
  • 21.8. Ideas
    • 21.8.1. Strategy
    • 21.8.2. Policy
    • 21.8.3. Mechanism
  • 21.9. Implementation
    • 21.9.1. Splay Tree
    • 21.9.2. Coalescing Block Structure
    • 21.9.3. Fail-over to address-ordered free list
    • 21.9.4. Available Block Queue
    • 21.9.5. Pool implementation
    • 21.9.6. AP Dispatch
  • 21.10. Testing
  • 21.11. Text
• 22. MVFF pool class
  • 22.1. Introduction
  • 22.2. Overview
  • 22.3. Methods
  • 22.4. Implementation
  • 22.5. Details
• 23. Protocol inheritance
  • 23.1. Introduction
  • 23.2. Purpose
  • 23.3. Requirements
  • 23.4. Overview
  • 23.5. Interface
    • 23.5.1. Class declaration
    • 23.5.2. Class definition
    • 23.5.3. Class access
    • 23.5.4. Single inheritance
    • 23.5.5. Specialization
    • 23.5.6. Extension
    • 23.5.7. Methods
    • 23.5.8. Conversion
    • 23.5.9. Introspection
    • 23.5.10. Protocol guidelines
    • 23.5.11. Example
  • 23.6. Implementation
  • 23.7. Common instance methods
  • 23.8. References
• 24. POSIX thread extensions
  • 24.1. Introduction
  • 24.2. Definitions
  • 24.3. Requirements
  • 24.4. Analysis
  • 24.5. Interface
  • 24.6. Implementation
  • 24.7. Attachments
  • 24.8. References
• 25. Root manager
  • 25.1. Basics
  • 25.2. Details
    • 25.2.1. Creation
    • 25.2.2. Destruction
    • 25.2.3. Invariants
    • 25.2.4. Scanning
• 26. The generic scanner
  • 26.1. Summaries
    • 26.1.1. Scanned summary
    • 26.1.2. Partial scans
• 27. Segment data structure
  • 27.1. Introduction
  • 27.2. Overview
  • 27.3. Data Structure
  • 27.4. Interface
    • 27.4.1. Splitting and merging
  • 27.5. Extensibility
    • 27.5.1. Allocation
    • 27.5.2. Garbage collection
    • 27.5.3. Splitting and merging
• 28. MPS Strategy
  • 28.1. Introduction
  • 28.2. Overview
  • 28.3. Requirements
  • 28.4. Generations
    • 28.4.1. General data structures
    • 28.4.2. AMC data structures
    • 28.4.3. Collections
    • 28.4.4. Zones
    • 28.4.5. Parameters
    • 28.4.6. Accounting
    • 28.4.7. Ramps
  • 28.5. Policy
    • 28.5.1. Assignment of zones
    • 28.5.2. Deciding whether to collect the world
    • 28.5.3. Starting a trace
    • 28.5.4. Trace progress
  • 28.6. References
• 29. Telemetry
  • 29.1. Introduction
  • 29.2. Overview
  • 29.3. Requirements
  • 29.4. Architecture
  • 29.5. Analysis
  • 29.6. Ideas
  • 29.7. Implementation
    • 29.7.1. Annotation
    • 29.7.2. Registration
    • 29.7.3. Control
    • 29.7.4. Debugging
    • 29.7.5. Dumper tool
    • 29.7.6. Allocation replayer tool
• 30. Tests
  • 30.1. Introduction
  • 30.2. Smoke tests
    • 30.2.1. Smoke test list
  • 30.3. Performance test
  • 30.4. Adding a new smoke test
• 31. Tracer
  • 31.1. Introduction
  • 31.2. Architecture
  • 31.3. Analysis
  • 31.4. Ideas
  • 31.5. Implementation
    • 31.5.1. Speed
  • 31.6. Life cycle of a trace object
    • 31.6.1. Making progress: scanning grey segments
  • 31.7. References