6.S081/6.828 2019 Lecture 2: Memory allocation
Systems programming Build services for applications Not specific to an application workload Use underlying OS directly Examples: unix utilities, K/V servers, ssh, bigint library, etc.
Challenges: Low-level programming environment E.g., numbers are 64 bits (not unlimited integers) E.g., allocating/freeing memory (not typed objects) Concurrency to allow requests to be processed in parallel Crashes Performance Deliver hardware performance to applications
Dynamic memory allocation is a basic system service Example of low-level programming Pointer manipulation, type casting, etc. Use underlying OS to ask for chunks of memory Must support wide-range of workloads Performance is important When you build an application, memory allocator can be a bottleneck Likely you will look at memory allocators at some point in your career
Background: program layout text data (static storage) stack (stack storage) heap (dynamic memory allocation) Grow heap with sbrk() or mmap() [text | data | heap -> ... <- stack] 0 top of address space
Memory allocated in data segment static, always there
Memory allocated on stack allocated on function entry freed on function exit
Memory allocator for heap interface p = malloc(int sz) free(p) several implementations in this lecture all single threaded
Goals for heap allocator Fast malloc and free Small memory overhead Want to use all memory Avoid fragmentation
Simple implementation (e.g., xv6's kalloc) present heap as a list of blocks, sorted by address 200 bytes heap [ free ] 0 200 malloc(100) -> 0 malloc(50) -> 100 heap picture: [ A | B | free ] 0 100 150 200
API challenge free(100) what is size for B? need to store size for B somewhere put a header front of each block with some metadata K&R: struct header: contains size and next pointer [ H A | H free | H free ] 0 16 100+16 150+32 200 (Assume: 64-bit pointers and sizes)
Fragmentation challenge malloc(75) -> fails! no block on free list is large enough we need to coalesce
K&R malloc (see user/umalloc.c, used by xv6's shell) first-fit on malloc other policies: best-fit coalesce on free memory overhead: if every malloc is for 16 bytes, 50% efficiency: workload dependent e.g., if blocks are returned in order: free list has one element e.g., if blocks are returned out of order: perhaps search long list
Aside: C Popular for systems programming language Many kernels are written in C (e.g., Linux, BSDs, MacOS, Windows) Much system software written in C (K/V servers, ssh, etc.) Allows stepping out of type system A piece of memory can be stated to be of type T1 Same memory may also used as type T2 Type casts (Header ) Pointers = addresses Allows referencing memory, devices, etc. Examples in K&R malloc: char p (pointer to an char object) Header p; where does p+1 point to? void p (any type of pointer) Dangerous programming language Easy to have bugs No type safety Not great for concurrency Next lecture: TA lecture on C and gdb
Region allocator (see malloc.c) faster allocator, but fragmentation region for part of the heap very fast malloc very fast free low memory overhead serious fragmentation frees region until complete region is unused application must fit region use more efficient than K&R and still general-purpose?
Buddy allocator (see malloc.c) topic of one of the labs data structure: size classes: 2^0, 2^1, 2^2, ... 2^k size 0: minimum size (e.g., 16 bytes)
internal fragmentation malloc(17) allocates 32 bytes operations: malloc: allocate first free block on list perhaps after splitting a bigger block free: determine size of block if buddy is free, merge put block on free list of size class why good? malloc/free are fast cost: size of data structures several optimizations possible
Other sequential allocators: dlmalloc slab allocator
Other goals small memory overhead metadata for example buddy allocator is large good memory locality good scalability with increasing cores concurrent malloc/free
References
Knuth, Donald (1997). Fundamental Algorithms. The Art of Computer Programming. 1 (Second ed.). Reading, Massachusetts: Addison-Wesley. pp. 435鈥�455. ISBN 0-201-89683-4.
Last updated
Was this helpful?