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 functions
    • 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 pool 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. External types
    • 9.2.2. External functions
    • 9.2.3. Keyword arguments
  • 9.3. Implementation
• 10. Free list allocator
  • 10.1. Introduction
  • 10.2. Overview
  • 10.3. Requirements
  • 10.4. Interface
    • 10.4.1. Types
    • 10.4.2. External functions
    • 10.4.3. Keyword arguments
  • 10.5. Implementation
  • 10.6. Testing
  • 10.7. Opportunities for improvement
• 11. Transliterating the alphabet into hexadecimal
  • 11.1. Introduction
  • 11.2. Transliteration
  • 11.3. Justification
  • 11.4. Notes
  • 11.5. References
• 12. C Style – formatting
  • 12.1. Introduction
  • 12.2. General Formatting Conventions
    • 12.2.1. Line Width
    • 12.2.2. White Space
    • 12.2.3. Sections and Paragraphs
    • 12.2.4. Statements
    • 12.2.5. Indentation
    • 12.2.6. Positioning of Braces
    • 12.2.7. Switch Statements
    • 12.2.8. Formatting Comments
    • 12.2.9. Macros
  • 12.3. History
  • 12.4. Copyright and License
• 13. C Style – naming
  • 13.1. Introduction
  • 13.2. Capitalization
  • 13.3. Prefixes
  • 13.4. Suffixes
• 14. Review checklist
  • 14.1. Introduction
  • 14.2. Checklist
• 15. C interface design
  • 15.1. Introduction
  • 15.2. Analysis
    • 15.2.1. Goals
    • 15.2.2. Requirements
  • 15.3. Architecture
  • 15.4. Naming conventions
  • 15.5. Type conventions
  • 15.6. Checking
  • 15.7. Binary compatibility issues
  • 15.8. Constraints
  • 15.9. Implementation
  • 15.10. Notes
• 16. Keyword arguments in the MPS
  • 16.1. Introduction
  • 16.2. Overview
  • 16.3. Internals
  • 16.4. The varargs legacy
  • 16.5. References
• 17. Lands
  • 17.1. Introduction
  • 17.2. Definitions
  • 17.3. Requirements
  • 17.4. Interface
    • 17.4.1. Types
    • 17.4.2. Generic functions
  • 17.5. Implementations
  • 17.6. Testing
• 18. Lock module
  • 18.1. Introduction
  • 18.2. Background
  • 18.3. Requirements
  • 18.4. Interface
  • 18.5. Implementation
  • 18.6. Example
  • 18.7. References
• 19. Nailboards for ambiguously referenced segments
  • 19.1. Introduction
  • 19.2. Requirements
  • 19.3. Implementation
  • 19.4. Future
  • 19.5. References
• 20. Protection mutator context
  • 20.1. Introduction
  • 20.2. Requirements
  • 20.3. Interface
  • 20.4. Implementations
    • 20.4.1. Generic implementation
    • 20.4.2. Unix implementation
    • 20.4.3. Windows implementation
    • 20.4.4. OS X implementation
• 21. Memory protection
  • 21.1. Introduction
  • 21.2. Requirements
  • 21.3. Design
  • 21.4. Interface
  • 21.5. Implementations
• 22. Ranges of addresses
  • 22.1. Introduction
  • 22.2. Requirements
  • 22.3. Interface
• 23. Ring data structure
  • 23.1. Introduction
  • 23.2. Description
  • 23.3. Interface
    • 23.3.1. Init / Finish
    • 23.3.2. Checking
    • 23.3.3. Iteration
    • 23.3.4. Element access
    • 23.3.5. Append / Remove
  • 23.4. Naming
  • 23.5. Deques
  • 23.6. Defects
• 24. Shield
  • 24.1. Introduction
  • 24.2. Overview
  • 24.3. Interface
    • 24.3.1. Mutator access
    • 24.3.2. Entering the shield
    • 24.3.3. Collector access to segments
    • 24.3.4. Collector access to the unprotectable
  • 24.4. Mechanism
  • 24.5. Implementation
    • 24.5.1. Definitions
    • 24.5.2. Properties
    • 24.5.3. Invariants
    • 24.5.4. Proof Hints
  • 24.6. Initial ideas
  • 24.7. Improvement Ideas
    • 24.7.1. Mass exposure
    • 24.7.2. Segment independence
    • 24.7.3. Concurrent collection
    • 24.7.4. Early Resume
    • 24.7.5. Expose modes
  • 24.8. References
• 25. Signatures in the MPS
  • 25.1. Introduction
  • 25.2. Overview
  • 25.3. Definitions
  • 25.4. Init and Finish
  • 25.5. Checking
  • 25.6. Rules
  • 25.7. Tools
  • 25.8. References
• 26. Stack probe
  • 26.1. Introduction
  • 26.2. Requirements
  • 26.3. Design
  • 26.4. Interface
  • 26.5. Issues
  • 26.6. Implementations
• 27. Splay trees
  • 27.1. Introduction
  • 27.2. Overview
  • 27.3. Definitions
  • 27.4. Requirements
  • 27.5. Generic binary tree interface
    • 27.5.1. Types
    • 27.5.2. Functions
  • 27.6. Splay tree interface
    • 27.6.1. Types
    • 27.6.2. Functions
  • 27.7. Client-determined properties
  • 27.8. Usage
  • 27.9. Implementation
    • 27.9.1. Top-down splaying
    • 27.9.2. Top-level operations
  • 27.10. Testing
  • 27.11. Error Handling
  • 27.12. Future
  • 27.13. References
• 28. Stack and register scanning
  • 28.1. Introduction
  • 28.2. Requirements
  • 28.3. Design
  • 28.4. Interface
  • 28.5. Issue
  • 28.6. Implementations
• 29. Multi-threaded testing
  • 29.1. Introduction
  • 29.2. Requirements
  • 29.3. Implementation
  • 29.4. Interface
  • 29.5. References
• 30. Thread manager
  • 30.1. Introduction
  • 30.2. Requirements
  • 30.3. Design
  • 30.4. Interface
  • 30.5. Implementations
    • 30.5.1. Generic implementation
    • 30.5.2. POSIX threads implementation
    • 30.5.3. Windows implementation
    • 30.5.4. OS X implementation
• 31. General MPS types
  • 31.1. Introduction
  • 31.2. Rationale
  • 31.3. Concrete types
  • 31.4. Abstract types
• 32. Virtual mapping
  • 32.1. Introduction
  • 32.2. Requirements
  • 32.3. Design
  • 32.4. Interface
  • 32.5. Implementations
    • 32.5.1. Generic implementation
    • 32.5.2. Unix implementation
    • 32.5.3. Windows implementation
  • 32.6. Testing
• 33. Write barrier
  • 33.1. Introduction
  • 33.2. Overview
  • 33.3. Write Barrier Processes
  • 33.4. Write barrier deferral
  • 33.5. Improvements
  • 33.6. References
• 34. The WriteF function
  • 34.1. Introduction
  • 34.2. Design