Design a Fixed-Size Memory Allocator with Correct Alignment

Design a fixed-size memory allocator backed by slabs and a linked free list. Explain allocation, deallocation, alignment, lifetime, corruption defenses, and how you would store objects whose payload size is 9 bytes efficiently. ### Constraints & Assumptions - Every slot in one size class has the same stride. - Allocation and deallocation should be constant time in the common case. - The allocator manages raw storage; object construction and destruction are separate operations. - The design must not return pointers that violate the requested alignment. ### Clarifying Questions to Ask - What maximum alignment and number of simultaneous allocations are required? - May empty slabs be returned to the operating system? - Is the allocator used by one thread or many? ### What a Strong Answer Covers - Slab layout, slot stride, free-list linkage, and growth. - Rounding size to alignment and distinguishing payload size from stride. - Placement construction, explicit destruction, and the roles of `new` and `delete`. - Validation of deallocation, double-free mitigation, metadata, and thread-safety choices. - The 9-byte trade-off among padding, smaller alignment, packed bytes, and multiple size classes. ### Follow-up Questions - Where can free-list metadata live when a slot is allocated? - How would you make the allocator thread-safe without one global lock? - What are the consequences of returning an empty slab too aggressively?