Transcript A Note on malloc() and Slab Allocation

This presentation is best viewed
in PowerPoint as a “slide show”
(Press F5 key)
A Note on malloc()
and Slab Allocation
CS-502, Operating Systems
Fall 2009 (EMC)
(Slides include materials from Modern Operating Systems, 3rd ed., by Andrew Tanenbaum and from
Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne)
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
1
Typical Implementation of malloc()
free
– Shows status
– Length
• Descriptors effectively
form a linked list
– Possibly doubly-linked
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
descriptor
allocated
descriptor
free
descriptor
allocated
descriptor
allocated
descriptor
2
Heap
• Heap comprises linked
list of allocated and
free blocks
• Each block is prefixed
by a descriptor
Implementation of malloc() (continued)
free
– Writing past block end
corrupts descriptor …
– … and messes up all
future allocation!
• Many allocated blocks
adjacent to each other
• Free blocks coalesced
descriptor
allocated
descriptor
free
descriptor
allocated
descriptor
allocated
descriptor
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
3
Heap
• Descriptors are not
protected against
program errors
…
malloc()— Allocating New Object
– length + sizeof(descriptor)
allocated
descriptor
free
descriptor
free
allocated
• Link remaining free portion
descriptor
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
…
allocated
4
Heap
• Traverse linked list until a
large enough free block is
found
• Carve off enough for request
…
free()— Deallocating an Object
• Mark block as free
• If adjacent blocks are free,
coalesce
allocated
descriptor
free
descriptor
free
allocated
free
descriptor
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
allocated
…
• Note:– if bad pointer, heap
becomes corrupted!
5
Heap
• Find descriptor from pointer
Result — External Fragmentation
• After long operation, heap fills up with a lot
of small, free spaces
• Too small for useful allocation
• Coalescence works, but not fast enough to recover
large spaces
• Typical in 24×7 operation for days or weeks
on end!
• Need something better
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
6
Slab Allocation
• Definition:– Slab. A separate memory pool
for frequently created & deleted objects of
same size.
• E.g, the task_struct in Linux kernel — i.e., the
kernel data structure representing each process and
thread — and other kernel objects
• Certain data structures in database applications
• Can be managed with bit-map allocator
• Very fast; no pointer manipulation or coalescence
needed
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
7
Slab Allocation in Linux Kernel
• Maintain a separate “cache” for each major data type
• E.g., task_struct, inode in Linux
• Slab: fixed number of contiguous physical pages assigned
to one particular “cache”
• Upon kernel memory allocation request
• Recycle an existing object if possible
• Allocate a new one within a slab if possible
• Else, create an additional slab for that cache
• When finished with an object
• Return it to “cache” for recycling
• Benefits
• Minimize fragmentation of kernel memory
• Most kernel memory requests can be satisfied quickly
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
8
Slab Allocation (illustrated)
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
9
Summary
• Dynamic memory allocation is crucial to
applications, system tools, & OS kernels
• Simple malloc() and free() are prone to a lot of
fragmentation
• Especially during long, continuous operation
• Other allocators needed for more intelligent
management of heap memory
• Slab allocators — one example of a better memory
allocation tool
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
10
Questions?
CS-502 (EMC) Fall 2009
Note on malloc() and
slab allocation
11