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. Pool class interface
  • 7.1. Introduction
  • 7.2. Fields
  • 7.3. Methods
  • 7.4. Events
  • 7.5. Text
• 8. Collection framework
  • 8.1. Introduction
  • 8.2. Overview
  • 8.3. Collection abstractions
    • 8.3.1. Colours, scanning and fixing
    • 8.3.2. Reference sets
  • 8.4. The tracer
    • 8.4.1. The condemn phase
    • 8.4.2. The grey mutator phase
    • 8.4.3. The flip phase
    • 8.4.4. The black mutator phase
    • 8.4.5. The reclaim phase
  • 8.5. Barriers
    • 8.5.1. Hardware barriers
    • 8.5.2. Software barriers
• 9. Diagnostic feedback
  • 9.1. Introduction
  • 9.2. Overview
  • 9.3. Requirements
  • 9.4. Usage
  • 9.5. How to write a diagnostic
    • 9.5.1. Compile away in non-diag varieties; no side effects
    • 9.5.2. Writing good paragraph text
  • 9.6. How the MPS diagnostic system works
    • 9.6.1. Parts of the MPS diagnostic system
    • 9.6.2. Statistics
    • 9.6.3. Related systems
  • 9.7. References
• 10. Finalization
  • 10.1. Overview
  • 10.2. Requirements
  • 10.3. Architecture
    • 10.3.1. External interface
  • 10.4. Implementation
• 11. The generic fix function
  • 11.1. Introduction
  • 11.2. Architecture
  • 11.3. Implementation
• 12. I/O subsystem
  • 12.1. Introduction
  • 12.2. Background
  • 12.3. Purpose
  • 12.4. Requirements
    • 12.4.1. General
    • 12.4.2. Functional
  • 12.5. Architecture
    • 12.5.1. Example configurations
  • 12.6. Interface
    • 12.6.1. I/O module state
    • 12.6.2. Message types
    • 12.6.3. Limits
    • 12.6.4. Interface set-up and tear-down
    • 12.6.5. Message send and receive
  • 12.7. I/O module implementations
    • 12.7.1. Routeing
  • 12.8. Notes
  • 12.9. Attachments
• 13. Library interface
  • 13.1. Introduction
  • 13.2. Goals
  • 13.3. Description
    • 13.3.1. Overview
  • 13.4. Implementation
• 14. Locus manager
  • 14.1. Introduction
  • 14.2. Overview
    • 14.2.1. Why is it important to manage address space?
    • 14.2.2. Discovering the layout
  • 14.3. Definitions
  • 14.4. Requirements
  • 14.5. Analysis
  • 14.6. Interface
    • 14.6.1. Loci
    • 14.6.2. Peaks
  • 14.7. Architecture
    • 14.7.1. Data objects
    • 14.7.2. Overview of strategy
    • 14.7.3. Allocation
    • 14.7.4. Deallocation
    • 14.7.5. Region placement recomputation
  • 14.8. Implementation
  • 14.9. Notes
• 15. Client message protocol
  • 15.1. Introduction
  • 15.2. Requirements
  • 15.3. External interface
    • 15.3.1. Functions
    • 15.3.2. Types of messages
    • 15.3.3. Compatibility issues
  • 15.4. Internal interface
    • 15.4.1. Types
    • 15.4.2. Functions
  • 15.5. Message life cycle
  • 15.6. Examples
    • 15.6.1. Finalization
• 16. GC messages
  • 16.1. Introduction
  • 16.2. Overview
  • 16.3. Introduction
  • 16.4. Purpose
  • 16.5. Names and parts
  • 16.6. Lifecycle
    • 16.6.1. Requirements
    • 16.6.2. Storage
    • 16.6.3. Creating and Posting
    • 16.6.4. Getting and discarding
    • 16.6.5. Final clearup
  • 16.7. Testing
    • 16.7.1. Coverage
• 17. Debugging features for client objects
  • 17.1. Introduction
  • 17.2. Overview
  • 17.3. Requirements
  • 17.4. Solution ideas
  • 17.5. Architecture
  • 17.6. Client interface
  • 17.7. Examples
  • 17.8. Implementation
• 18. Pool and pool class mechanisms
  • 18.1. Definitions
  • 18.2. Defaults
  • 18.3. Requirements
  • 18.4. Other
• 19. AMC pool class
  • 19.1. Introduction
  • 19.2. Guide
    • 19.2.1. Segment states
    • 19.2.2. Pads
    • 19.2.3. Placement pads are okay
    • 19.2.4. Retained pads could be a problem
    • 19.2.5. Small, medium, and large segments
    • 19.2.6. The LSP payoff calculation
    • 19.2.7. Retained pages
    • 19.2.8. Feedback about retained pages
  • 19.3. Initial design
    • 19.3.1. Introduction
    • 19.3.2. Overview
    • 19.3.3. Definitions
    • 19.3.4. Segments
    • 19.3.5. Fixing and nailing
    • 19.3.6. Emergency tracing
    • 19.3.7. Buffers
    • 19.3.8. Types
    • 19.3.9. Generations
    • 19.3.10. Ramps
    • 19.3.11. Headers
    • 19.3.12. Old and aging notes below here
• 20. AMS pool class
  • 20.1. Introduction
  • 20.2. Overview
  • 20.3. Requirements
  • 20.4. Architecture
    • 20.4.1. Subclassing
    • 20.4.2. Allocation
    • 20.4.3. Colours
    • 20.4.4. Scanning
  • 20.5. Implementation
    • 20.5.1. Colour
    • 20.5.2. Iteration
    • 20.5.3. Scanning Algorithm
    • 20.5.4. Allocation
    • 20.5.5. Initialization
    • 20.5.6. Condemnation
    • 20.5.7. Reclaim
    • 20.5.8. Segment merging and splitting
  • 20.6. Testing
  • 20.7. Notes
• 21. AWL pool class
  • 21.1. Introduction
  • 21.2. Requirements
  • 21.3. Definitions
  • 21.4. Overview
  • 21.5. Interface
  • 21.6. Data structures
  • 21.7. Functions
    • 21.7.1. External
    • 21.7.2. Internal
  • 21.8. Test
• 22. LO pool class
  • 22.1. Introduction
  • 22.2. Definitions
  • 22.3. Requirements
  • 22.4. Overview
  • 22.5. Interface
  • 22.6. Data structures
  • 22.7. Functions
    • 22.7.1. External
    • 22.7.2. Internal
  • 22.8. Attachment
• 23. MFS pool class
  • 23.1. Overview
• 24. MRG pool class
  • 24.1. Introduction
  • 24.2. Goals
  • 24.3. Requirements
  • 24.4. Terminology
  • 24.5. Overview
  • 24.6. Protocols
    • 24.6.1. Object Registration
    • 24.6.2. Finalizer execution
    • 24.6.3. Setup / destroy
  • 24.7. Data structures
  • 24.8. Functions
  • 24.9. Transgressions
  • 24.10. Future
  • 24.11. Tests
    • 24.11.1. Functionality
    • 24.11.2. Attributes
    • 24.11.3. Implementation
  • 24.12. Notes
• 25. MV pool class
  • 25.1. Implementation
  • 25.2. References
• 26. Manual Variable Temporal (MVT) pool design
  • 26.1. Introduction
  • 26.2. Definitions
  • 26.3. Abbreviations
  • 26.4. Overview
  • 26.5. Requirements
    • 26.5.1. Critical requirements
    • 26.5.2. Essential requirements
    • 26.5.3. Nice requirements
  • 26.6. Architecture
  • 26.7. Analysis
  • 26.8. Ideas
    • 26.8.1. Strategy
    • 26.8.2. Policy
    • 26.8.3. Mechanism
  • 26.9. Implementation
    • 26.9.1. Splay Tree
    • 26.9.2. Coalescing Block Structure
    • 26.9.3. Fail-over to address-ordered free list
    • 26.9.4. Available Block Queue
    • 26.9.5. Pool implementation
    • 26.9.6. AP Dispatch
  • 26.10. Testing
  • 26.11. Text
• 27. MVFF pool class
  • 27.1. Introduction
  • 27.2. Overview
  • 27.3. Methods
  • 27.4. Implementation
  • 27.5. Details
• 28. Linux implementation of protection module
  • 28.1. Introduction
  • 28.2. Requirements
  • 28.3. Data structures
  • 28.4. Functions
  • 28.5. Threads
• 29. SunOS 4 protection module
  • 29.1. Introduction
  • 29.2. Requirements
  • 29.3. Overview
  • 29.4. Misc
  • 29.5. Data structures
  • 29.6. Functions
• 30. Protocol inheritance
  • 30.1. Introduction
  • 30.2. Purpose
  • 30.3. Requirements
  • 30.4. Overview
  • 30.5. Interface
    • 30.5.1. Class declaration
    • 30.5.2. Class definition
    • 30.5.3. Class access
    • 30.5.4. Single inheritance
    • 30.5.5. Specialization
    • 30.5.6. Extension
    • 30.5.7. Methods
    • 30.5.8. Conversion
    • 30.5.9. Introspection
    • 30.5.10. Protocol guidelines
    • 30.5.11. Example
  • 30.6. Implementation
  • 30.7. References
• 31. POSIX thread extensions
  • 31.1. Introduction
  • 31.2. Definitions
  • 31.3. Requirements
  • 31.4. Analysis
  • 31.5. Interface
  • 31.6. Implementation
  • 31.7. Attachments
  • 31.8. References
• 32. Root manager
  • 32.1. Basics
  • 32.2. Details
    • 32.2.1. Creation
    • 32.2.2. Destruction
    • 32.2.3. Invariants
    • 32.2.4. Scanning
• 33. The generic scanner
  • 33.1. Summaries
    • 33.1.1. Scanned summary
    • 33.1.2. Partial scans
• 34. Segment data structure
  • 34.1. Introduction
  • 34.2. Overview
  • 34.3. Data Structure
  • 34.4. Interface
    • 34.4.1. Splitting and merging
  • 34.5. Extensibility
    • 34.5.1. Splitting and merging
• 35. Stack scanner for Digital Unix on Alpha
  • 35.1. Introduction
  • 35.2. Definitions
  • 35.3. Overview
  • 35.4. Detail Design
    • 35.4.1. Functions
  • 35.5. References
• 36. MPS Strategy
  • 36.1. Introduction
  • 36.2. Overview
  • 36.3. Requirements
  • 36.4. Generations
    • 36.4.1. General data structures
    • 36.4.2. AMC data structures
    • 36.4.3. Collections
    • 36.4.4. Zones
    • 36.4.5. Parameters
    • 36.4.6. Accounting
    • 36.4.7. Ramps
  • 36.5. Policy
    • 36.5.1. Assignment of zones
    • 36.5.2. Deciding whether to collect the world
    • 36.5.3. Starting a trace
    • 36.5.4. Trace progress
  • 36.6. References
• 37. Telemetry
  • 37.1. Introduction
  • 37.2. Overview
  • 37.3. Requirements
  • 37.4. Architecture
  • 37.5. Analysis
  • 37.6. Ideas
  • 37.7. Implementation
    • 37.7.1. Annotation
    • 37.7.2. Registration
    • 37.7.3. Control
    • 37.7.4. Debugging
    • 37.7.5. Dumper tool
    • 37.7.6. Allocation replayer tool
• 38. Tests
  • 38.1. Introduction
  • 38.2. Smoke tests
    • 38.2.1. Smoke test list
  • 38.3. Performance test
• 39. Thread safety in the MPS
  • 39.1. Introduction
  • 39.2. Overview
  • 39.3. Requirements
  • 39.4. Architecture
  • 39.5. Analysis
    • 39.5.1. Performance cost of locking
    • 39.5.2. Recursive vs binary locks
  • 39.6. Ideas
  • 39.7. Implementation
    • 39.7.1. Locking Functions
    • 39.7.2. Shared and non-shared data
    • 39.7.3. Validation
    • 39.7.4. Safe functions
• 40. Tracer
  • 40.1. Introduction
  • 40.2. Architecture
  • 40.3. Analysis
  • 40.4. Ideas
  • 40.5. Implementation
    • 40.5.1. Speed
  • 40.6. Life cycle of a trace object
    • 40.6.1. Making progress: scanning grey segments
  • 40.7. References
• 41. Library version mechanism
  • 41.1. Introduction
  • 41.2. Readership
  • 41.3. Source
  • 41.4. Overview
  • 41.5. Architecture
  • 41.6. Implementation
• 42. Software versions
  • 42.1. Introduction
  • 42.2. Overview
• 43. VM for Digital Unix
  • 43.1. Introduction
  • 43.2. Functions
• 44. VM for Solaris
  • 44.1. Introduction
  • 44.2. Definitions
  • 44.3. Overview
  • 44.4. Implementation