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. State
    • 1.8.3. Synchronization
    • 1.8.4. 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. Iteration protocol
    • 2.4.4. Arena partition
    • 2.4.5. Constraints
  • 2.5. Architecture
    • 2.5.1. Statics
    • 2.5.2. Arena classes
    • 2.5.3. Tracts
    • 2.5.4. Control pool
    • 2.5.5. Polling
    • 2.5.6. Commit limit
    • 2.5.7. Spare committed (aka “hysteresis”)
    • 2.5.8. Locks
    • 2.5.9. Location dependencies
    • 2.5.10. 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
• 7. Pool class interface
  • 7.1. Introduction
  • 7.2. Methods
  • 7.3. Events
  • 7.4. 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. 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. C interface design
  • 12.1. Introduction
  • 12.2. Analysis
    • 12.2.1. Goals
    • 12.2.2. Requirements
  • 12.3. Architecture
  • 12.4. General conventions
  • 12.5. Checking
  • 12.6. Binary compatibility issues
  • 12.7. Constraints
  • 12.8. Notes
• 13. I/O subsystem
  • 13.1. Introduction
  • 13.2. Background
  • 13.3. Purpose
  • 13.4. Requirements
    • 13.4.1. General
    • 13.4.2. Functional
  • 13.5. Architecture
    • 13.5.1. Example configurations
  • 13.6. Interface
    • 13.6.1. I/O module state
    • 13.6.2. Message types
    • 13.6.3. Limits
    • 13.6.4. Interface set-up and tear-down
    • 13.6.5. Message send and receive
  • 13.7. I/O module implementations
    • 13.7.1. Routeing
  • 13.8. Notes
  • 13.9. Attachments
• 14. Library interface
  • 14.1. Introduction
  • 14.2. Goals
  • 14.3. Description
    • 14.3.1. Overview
    • 14.3.2. Outside the interface
  • 14.4. Implementation
• 15. The lock module
  • 15.1. Purpose
  • 15.2. Background
  • 15.3. Overview
  • 15.4. Detailed design
• 16. MPS Configuration
  • 16.1. Introduction
  • 16.2. Overview
    • 16.2.1. Why is it important to manage address space?
    • 16.2.2. Discovering the layout
  • 16.3. Definitions
  • 16.4. Requirements
  • 16.5. Analysis
  • 16.6. Interface
    • 16.6.1. Loci
    • 16.6.2. Peaks
  • 16.7. Architecture
    • 16.7.1. Data objects
    • 16.7.2. Overview of strategy
    • 16.7.3. Allocation
    • 16.7.4. Deallocation
    • 16.7.5. Region placement recomputation
  • 16.8. Implementation
  • 16.9. Notes
• 17. Client message protocol
  • 17.1. Introduction
  • 17.2. Requirements
  • 17.3. External interface
    • 17.3.1. Functions
    • 17.3.2. Types of messages
    • 17.3.3. Compatibility issues
  • 17.4. Internal interface
    • 17.4.1. Types
    • 17.4.2. Functions
  • 17.5. Message life cycle
  • 17.6. Examples
    • 17.6.1. Finalization
• 18. GC messages
  • 18.1. Introduction
  • 18.2. Overview
  • 18.3. Introduction
  • 18.4. Purpose
  • 18.5. Names and parts
  • 18.6. Lifecycle
    • 18.6.1. Requirements
    • 18.6.2. Storage
    • 18.6.3. Creating and Posting
    • 18.6.4. Getting and discarding
    • 18.6.5. Final clearup
  • 18.7. Testing
    • 18.7.1. Coverage
• 19. Debugging features for client objects
  • 19.1. Introduction
  • 19.2. Overview
  • 19.3. Requirements
  • 19.4. Solution ideas
  • 19.5. Architecture
  • 19.6. Client interface
  • 19.7. Examples
  • 19.8. Implementation
• 20. Pool and pool class mechanisms
  • 20.1. Definitions
  • 20.2. Defaults
  • 20.3. Requirements
  • 20.4. Other
• 21. AMC pool class
  • 21.1. Introduction
  • 21.2. Guide
    • 21.2.1. Segment states
    • 21.2.2. Pads
    • 21.2.3. Placement pads are okay
    • 21.2.4. Retained pads could be a problem
    • 21.2.5. Small, medium, and large segments
    • 21.2.6. The LSP payoff calculation
    • 21.2.7. Retained pages
    • 21.2.8. Feedback about retained pages
  • 21.3. Initial design
    • 21.3.1. Introduction
    • 21.3.2. Overview
    • 21.3.3. Definitions
    • 21.3.4. Segments
    • 21.3.5. Fixing and nailing
    • 21.3.6. Emergency tracing
    • 21.3.7. Buffers
    • 21.3.8. Types
    • 21.3.9. Generations
    • 21.3.10. Ramps
    • 21.3.11. Headers
    • 21.3.12. Old and aging notes below here
• 22. AMS pool class
  • 22.1. Introduction
  • 22.2. Overview
  • 22.3. Requirements
  • 22.4. Architecture
    • 22.4.1. Subclassing
    • 22.4.2. Allocation
    • 22.4.3. Colours
    • 22.4.4. Scanning
  • 22.5. Implementation
    • 22.5.1. Colour
    • 22.5.2. Iteration
    • 22.5.3. Scanning Algorithm
    • 22.5.4. Allocation
    • 22.5.5. Initialization
    • 22.5.6. Condemnation
    • 22.5.7. Reclaim
    • 22.5.8. Segment merging and splitting
  • 22.6. Testing
  • 22.7. Notes
• 23. AWL pool class
  • 23.1. Introduction
  • 23.2. Requirements
  • 23.3. Definitions
  • 23.4. Overview
  • 23.5. Interface
  • 23.6. Data structures
  • 23.7. Functions
    • 23.7.1. External
    • 23.7.2. Internal
  • 23.8. Test
• 24. LO pool class
  • 24.1. Introduction
  • 24.2. Definitions
  • 24.3. Requirements
  • 24.4. Overview
  • 24.5. Interface
  • 24.6. Data structures
  • 24.7. Functions
    • 24.7.1. External
    • 24.7.2. Internal
  • 24.8. Attachment
• 25. MFS pool class
  • 25.1. Overview
• 26. MRG pool class
  • 26.1. Introduction
  • 26.2. Goals
  • 26.3. Requirements
  • 26.4. Terminology
  • 26.5. Overview
  • 26.6. Protocols
    • 26.6.1. Object Registration
    • 26.6.2. Finalizer execution
    • 26.6.3. Setup / destroy
  • 26.7. Data structures
  • 26.8. Functions
  • 26.9. Transgressions
  • 26.10. Future
  • 26.11. Tests
    • 26.11.1. Functionality
    • 26.11.2. Attributes
    • 26.11.3. Implementation
  • 26.12. Notes
• 27. MV pool class
  • 27.1. Implementation
  • 27.2. References
• 28. Manual Variable Temporal (MVT) pool design
  • 28.1. Introduction
  • 28.2. Definitions
  • 28.3. Abbreviations
  • 28.4. Overview
  • 28.5. Requirements
    • 28.5.1. Critical requirements
    • 28.5.2. Essential requirements
    • 28.5.3. Nice requirements
  • 28.6. Architecture
  • 28.7. Analysis
  • 28.8. Ideas
    • 28.8.1. Strategy
    • 28.8.2. Policy
    • 28.8.3. Mechanism
  • 28.9. Implementation
    • 28.9.1. Coalescing Block Structure
    • 28.9.2. Fail-over to address-ordered free list
    • 28.9.3. Available Block Queue
    • 28.9.4. Pool implementation
    • 28.9.5. AP Dispatch
  • 28.10. Testing
  • 28.11. Text
• 29. MVFF pool class
  • 29.1. Introduction
  • 29.2. Overview
  • 29.3. Methods
  • 29.4. External Functions
  • 29.5. Implementation
  • 29.6. Details
• 30. The protection module
  • 30.1. Introduction
  • 30.2. Interface
• 31. ANSI implementation of protection module
  • 31.1. Introduction
  • 31.2. Requirements
  • 31.3. Overview
  • 31.4. Functions
• 32. Linux implementation of protection module
  • 32.1. Introduction
  • 32.2. Requirements
  • 32.3. Data structures
  • 32.4. Functions
  • 32.5. Threads
• 33. SunOS 4 protection module
  • 33.1. Introduction
  • 33.2. Requirements
  • 33.3. Overview
  • 33.4. Misc
  • 33.5. Data structures
  • 33.6. Functions
• 34. Protocol inheritance
  • 34.1. Introduction
  • 34.2. Purpose
  • 34.3. Requirements
  • 34.4. Overview
  • 34.5. Interface
    • 34.5.1. Class definition
    • 34.5.2. Single inheritance
    • 34.5.3. Specialization
    • 34.5.4. Extension
    • 34.5.5. Introspection
    • 34.5.6. Multiple inheritance
    • 34.5.7. Protocol guidelines
    • 34.5.8. Example
  • 34.6. Implementation
• 35. POSIX thread extensions
  • 35.1. Introduction
  • 35.2. Definitions
  • 35.3. Requirements
  • 35.4. Analysis
  • 35.5. Interface
  • 35.6. Implementation
  • 35.7. Attachments
  • 35.8. References
• 36. The low-memory reservoir
  • 36.1. Introduction
  • 36.2. Architecture
  • 36.3. Implementation
• 37. Root manager
  • 37.1. Basics
  • 37.2. Details
    • 37.2.1. Creation
    • 37.2.2. Destruction
    • 37.2.3. Invariants
    • 37.2.4. Scanning
• 38. The generic scanner
  • 38.1. Summaries
    • 38.1.1. Scanned summary
    • 38.1.2. Partial scans
• 39. Segment data structure
  • 39.1. Introduction
  • 39.2. Overview
  • 39.3. Data Structure
  • 39.4. Interface
    • 39.4.1. Splitting and merging
  • 39.5. Extensibility
    • 39.5.1. Splitting and merging
• 40. Shield
  • 40.1. Introduction
  • 40.2. Overview
  • 40.3. Control of mutator access
  • 40.4. Control of collector access
  • 40.5. Initial ideas
  • 40.6. References
• 41. Splay trees
  • 41.1. Introduction
  • 41.2. Overview
  • 41.3. Definitions
  • 41.4. Requirements
  • 41.5. External types
  • 41.6. External functions
  • 41.7. Client-determined properties
  • 41.8. Usage
  • 41.9. Implementation
    • 41.9.1. Top-down splaying
    • 41.9.2. Top-level operations
  • 41.10. Testing
  • 41.11. Error Handling
  • 41.12. Future
• 42. Stack scanner for Digital Unix on Alpha
  • 42.1. Introduction
  • 42.2. Definitions
  • 42.3. Overview
  • 42.4. Detail Design
    • 42.4.1. Functions
  • 42.5. References
• 43. MPS Strategy
  • 43.1. Introduction
  • 43.2. Overview
  • 43.3. Requirements
  • 43.4. Generations
    • 43.4.1. Data Structures
    • 43.4.2. Zones
    • 43.4.3. Accounting
    • 43.4.4. Ramps
    • 43.4.5. Non-AMC Pools
    • 43.4.6. Starting a Trace
    • 43.4.7. Trace Progress
• 44. Telemetry
  • 44.1. Introduction
  • 44.2. Overview
  • 44.3. Requirements
  • 44.4. Architecture
  • 44.5. Analysis
  • 44.6. Ideas
  • 44.7. Implementation
    • 44.7.1. Annotation
    • 44.7.2. Registration
    • 44.7.3. Control
    • 44.7.4. Debugging
    • 44.7.5. Dumper tool
    • 44.7.6. Allocation replayer tool
• 45. Tests
  • 45.1. Introduction
  • 45.2. Smoke tests
    • 45.2.1. Smoke test list
• 46. Thread Manager
  • 46.1. Purpose
  • 46.2. Context
  • 46.3. Overview
  • 46.4. Detailed Design
    • 46.4.1. Stack scan
    • 46.4.2. Thread interface
    • 46.4.3. Single-threaded generic implementation
    • 46.4.4. POSIX threads implementation
    • 46.4.5. Win32 implementation
  • 46.5. Issues
• 47. Thread safety in the MPS
  • 47.1. Introduction
  • 47.2. Overview
  • 47.3. Requirements
  • 47.4. Architecture
  • 47.5. Analysis
    • 47.5.1. Performance cost of locking
    • 47.5.2. Recursive vs binary locks
  • 47.6. Ideas
  • 47.7. Implementation
    • 47.7.1. Locking Functions
    • 47.7.2. Shared and non-shared data
    • 47.7.3. Validation
    • 47.7.4. Safe functions
• 48. Tracer
  • 48.1. Introduction
  • 48.2. Architecture
  • 48.3. Analysis
  • 48.4. Ideas
  • 48.5. Implementation
    • 48.5.1. Speed
  • 48.6. Life cycle of a trace object
    • 48.6.1. Making progress: scanning grey segments
  • 48.7. References
• 49. General MPS types
  • 49.1. Introduction
  • 49.2. Rationale
  • 49.3. Concrete types
  • 49.4. Abstract types
• 50. Library version mechanism
  • 50.1. Introduction
  • 50.2. Readership
  • 50.3. Source
  • 50.4. Overview
  • 50.5. Architecture
  • 50.6. Implementation
• 51. Software versions
  • 51.1. Introduction
  • 51.2. Overview
• 52. Virtual mapping
  • 52.1. Introduction
  • 52.2. Definitions
  • 52.3. Interface
  • 52.4. Notes
• 53. ANSI fake VM
• 54. VM for Digital Unix
  • 54.1. Introduction
  • 54.2. Functions
• 55. VM for Solaris
  • 55.1. Introduction
  • 55.2. Definitions
  • 55.3. Overview
  • 55.4. Implementation
• 56. The WriteF function
  • 56.1. Introduction
  • 56.2. Design