Design

• 1. Fixed-length queues
  • 1.1. Introduction
  • 1.2. Requirements
  • 1.3. Interface
• 2. Generic modules
  • 2.1. Introduction
  • 2.2. Requirements
  • 2.3. Design
  • 2.4. Modules
  • 2.5. Limitations of generic implementations
• 3. Bootstrapping
  • 3.1. Introduction
  • 3.2. Bootstrapping problems
    • 3.2.1. Virtual memory descriptor
    • 3.2.2. Arena descriptor
    • 3.2.3. Arena’s free land
• 4. Coalescing block structures
  • 4.1. Introduction
  • 4.2. Requirements
  • 4.3. Interface
    • 4.3.1. External types
    • 4.3.2. External classes
    • 4.3.3. Keyword arguments
    • 4.3.4. Limitations
  • 4.4. Implementation
    • 4.4.1. Splay tree
    • 4.4.2. Low memory behaviour
    • 4.4.3. The CBS block
  • 4.5. Testing
  • 4.6. Notes for future development
  • 4.7. Risks
• 5. Fast high-resolution clock
  • 5.1. Introduction
  • 5.2. Requirements
  • 5.3. Interface
  • 5.4. Implementation
• 6. MPS Configuration
  • 6.1. Introduction
  • 6.2. Requirements
    • 6.2.1. Retired requirements
  • 6.3. Definitions
  • 6.4. Overview
  • 6.5. The build system
    • 6.5.1. Abstract build function
    • 6.5.2. File Structure
    • 6.5.3. Modules and naming
    • 6.5.4. Build system rationale
  • 6.6. Implementation
    • 6.6.1. Target platform detection
    • 6.6.2. Target varieties
  • 6.7. Source code configuration
    • 6.7.1. Configuration Parameters
    • 6.7.2. Abstract and Concrete Module Interfaces
  • 6.8. Configuration options
  • 6.9. To document
  • 6.10. References
• 7. The critical path through the MPS
  • 7.1. Introduction
  • 7.2. What makes the critical path critical
  • 7.3. How the MPS avoids scanning and fixing
  • 7.4. Where to find the critical path
  • 7.5. The format scanner
  • 7.6. The second stage fix in the MPM
  • 7.7. The third stage fix in the segment class
  • 7.8. Other considerations
  • 7.9. References
• 8. Execution environment
  • 8.1. Introduction
  • 8.2. Discussion
  • 8.3. Interpretation
  • 8.4. Requirements
  • 8.5. Architecture
• 9. Fail-over allocator
  • 9.1. Introduction
  • 9.2. Interface
    • 9.2.1. Types
    • 9.2.2. Classes
    • 9.2.3. Keyword arguments
  • 9.3. Implementation
• 10. Finalization
  • 10.1. Overview
  • 10.2. Requirements
  • 10.3. Implementation
  • 10.4. External interface
  • 10.5. Internal interface
• 11. Free list allocator
  • 11.1. Introduction
  • 11.2. Overview
  • 11.3. Requirements
  • 11.4. Interface
    • 11.4.1. Types
    • 11.4.2. Classes
    • 11.4.3. Keyword arguments
  • 11.5. Implementation
  • 11.6. Testing
  • 11.7. Opportunities for improvement
• 12. Transliterating the alphabet into hexadecimal
  • 12.1. Introduction
  • 12.2. Transliteration
  • 12.3. Justification
  • 12.4. Notes
  • 12.5. References
• 13. C Style – formatting
  • 13.1. Introduction
  • 13.2. General formatting conventions
    • 13.2.1. Line width
    • 13.2.2. White space
    • 13.2.3. Sections and paragraphs
    • 13.2.4. Statements
    • 13.2.5. Indentation
    • 13.2.6. Positioning of braces
    • 13.2.7. Switch statements
    • 13.2.8. Comments
    • 13.2.9. Macros
  • 13.3. History
  • 13.4. Copyright and License
• 14. C Style – naming
  • 14.1. Introduction
  • 14.2. Capitalization
  • 14.3. Prefixes
  • 14.4. Suffixes
• 15. Review checklist
  • 15.1. Introduction
  • 15.2. Checklist
• 16. C interface design
  • 16.1. Introduction
  • 16.2. Analysis
    • 16.2.1. Goals
    • 16.2.2. Requirements
  • 16.3. Architecture
  • 16.4. Naming conventions
  • 16.5. Type conventions
  • 16.6. Checking
  • 16.7. Binary compatibility issues
  • 16.8. Constraints
  • 16.9. Implementation
  • 16.10. Notes
• 17. Keyword arguments in the MPS
  • 17.1. Introduction
  • 17.2. Overview
  • 17.3. Internals
  • 17.4. The varargs legacy
  • 17.5. References
• 18. Lands
  • 18.1. Introduction
  • 18.2. Definitions
  • 18.3. Requirements
  • 18.4. Interface
    • 18.4.1. Types
    • 18.4.2. Generic functions
  • 18.5. Implementations
  • 18.6. Testing
• 19. Lock module
  • 19.1. Introduction
  • 19.2. Background
  • 19.3. Requirements
  • 19.4. Interface
  • 19.5. Implementation
  • 19.6. Example
  • 19.7. References
• 20. Client message protocol
  • 20.1. Introduction
  • 20.2. Requirements
  • 20.3. Design
  • 20.4. External interface
    • 20.4.1. Functions
    • 20.4.2. Types of messages
  • 20.5. Internal interface
    • 20.5.1. Types
    • 20.5.2. Functions
  • 20.6. Message life cycle
  • 20.7. References
• 21. Nailboards for ambiguously referenced segments
  • 21.1. Introduction
  • 21.2. Requirements
  • 21.3. Implementation
  • 21.4. Future
  • 21.5. References
• 22. Pool classes
  • 22.1. Introduction
  • 22.2. Classes and structures
  • 22.3. Fields
  • 22.4. Methods
• 23. Mutator context
  • 23.1. Introduction
  • 23.2. Requirements
  • 23.3. Interface
  • 23.4. Implementations
    • 23.4.1. Generic implementation
    • 23.4.2. Posix implementation
    • 23.4.3. Windows implementation
    • 23.4.4. macOS implementation
• 24. Memory protection
  • 24.1. Introduction
  • 24.2. Requirements
  • 24.3. Design
  • 24.4. Interface
  • 24.5. Implementations
• 25. POSIX implementation of protection module
  • 25.1. Introduction
  • 25.2. Requirements
  • 25.3. Data structures
  • 25.4. Functions
  • 25.5. Threads
• 26. Ranges of addresses
  • 26.1. Introduction
  • 26.2. Requirements
  • 26.3. Interface
• 27. Ring data structure
  • 27.1. Introduction
  • 27.2. Description
  • 27.3. Interface
    • 27.3.1. Init / Finish
    • 27.3.2. Checking
    • 27.3.3. Iteration
    • 27.3.4. Element access
    • 27.3.5. Append / Remove
  • 27.4. Naming
  • 27.5. Deques
  • 27.6. Defects
• 28. Shield
  • 28.1. Introduction
  • 28.2. Overview
  • 28.3. Interface
    • 28.3.1. Mutator access
    • 28.3.2. Entering the shield
    • 28.3.3. Collector access to segments
    • 28.3.4. Collector access to the unprotectable
  • 28.4. Mechanism
  • 28.5. Implementation
    • 28.5.1. Definitions
    • 28.5.2. Properties
    • 28.5.3. Invariants
    • 28.5.4. Proof Hints
  • 28.6. Initial ideas
  • 28.7. Improvement Ideas
    • 28.7.1. Mass exposure
    • 28.7.2. Segment independence
    • 28.7.3. Concurrent collection
    • 28.7.4. Early Resume
    • 28.7.5. Expose modes
  • 28.8. References
• 29. Signatures in the MPS
  • 29.1. Introduction
  • 29.2. Overview
  • 29.3. Definitions
  • 29.4. Init and Finish
  • 29.5. Checking
  • 29.6. Rules
  • 29.7. Tools
  • 29.8. References
• 30. Stack probe
  • 30.1. Introduction
  • 30.2. Requirements
  • 30.3. Design
  • 30.4. Interface
  • 30.5. Issues
  • 30.6. Implementations
• 31. Splay trees
  • 31.1. Introduction
  • 31.2. Overview
  • 31.3. Definitions
  • 31.4. Requirements
  • 31.5. Generic binary tree interface
    • 31.5.1. Types
    • 31.5.2. Functions
  • 31.6. Splay tree interface
    • 31.6.1. Types
    • 31.6.2. Functions
  • 31.7. Client-determined properties
  • 31.8. Usage
  • 31.9. Implementation
    • 31.9.1. Top-down splaying
    • 31.9.2. Top-level operations
  • 31.10. Testing
  • 31.11. Error Handling
  • 31.12. Future
  • 31.13. References
• 32. Stack and register scanning
  • 32.1. Introduction
  • 32.2. Requirements
  • 32.3. Design
  • 32.4. Analysis
  • 32.5. Interface
  • 32.6. Implementations
  • 32.7. References
• 33. Multi-threaded testing
  • 33.1. Introduction
  • 33.2. Requirements
  • 33.3. Implementation
  • 33.4. Interface
  • 33.5. References
• 34. Thread manager
  • 34.1. Introduction
  • 34.2. Requirements
  • 34.3. Design
  • 34.4. Interface
  • 34.5. Implementations
    • 34.5.1. Generic implementation
    • 34.5.2. POSIX threads implementation
    • 34.5.3. Windows implementation
    • 34.5.4. macOS implementation
• 35. Thread safety in the MPS
  • 35.1. Introduction
  • 35.2. Requirements
  • 35.3. Analysis
    • 35.3.1. Performance cost of locking
    • 35.3.2. Recursive vs binary locks
    • 35.3.3. Fork safety
  • 35.4. Design
  • 35.5. Fork safety
• 36. General MPS types
  • 36.1. Introduction
  • 36.2. Rationale
  • 36.3. Concrete types
  • 36.4. Abstract types
• 37. Library version mechanism
  • 37.1. Introduction
  • 37.2. Readership
  • 37.3. Source
  • 37.4. Overview
  • 37.5. Architecture
  • 37.6. Implementation
• 38. Virtual mapping
  • 38.1. Introduction
  • 38.2. Requirements
  • 38.3. Design
  • 38.4. Interface
  • 38.5. Implementations
    • 38.5.1. Generic implementation
    • 38.5.2. Unix implementation
    • 38.5.3. Windows implementation
  • 38.6. Testing
• 39. Write barrier
  • 39.1. Introduction
  • 39.2. Overview
  • 39.3. Write Barrier Processes
  • 39.4. Write barrier deferral
  • 39.5. Improvements
  • 39.6. References
• 40. The WriteF function
  • 40.1. Introduction
  • 40.2. Design