|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| | | #redirect [[Template:Computer hardware]] |
| =On memory fragmentation=
| |
| | |
| ==Fragmentation in general==
| |
| <!--
| |
| | |
| Since you don't want to manage all memory by yourself, you usually want something to provide an allocator for you, so you can ask "I would like X amount of contiguous memory now, please" and it'll figure out where it needs to come from.
| |
| | |
| Since an allocator will serve many such requests over time, and programs ask for fairly arbitrary-sized chunks,
| |
| over time these allocations end up somewhat arbitrarily positioned, with arbitrarily sized holes in-between.
| |
| | |
| These holes will serve smaller but not larger requests, and mean programs get chunks that are fairly randomly positioned in physical memory.
| |
| | |
| | |
| | |
| Fragmentation in general can be bad for a few reasons:
| |
| * allocation becoming slightly slower because its bookkeeping gets more complex over time
| |
| | |
| * slightly lower access speed due to going to more places - e.g. when you think things are in sequence but actually comes from different places in RAM
| |
| : since most memory is random-access (but there are details like hardware caches), the overhead is small and the difference is small | |
| | |
| * holes that develop over time means the speed at which memory fragments increases over time
| |
| | |
| | |
| | |
| | |
| This is basically irrelevant for physical memory, mostly because the translation between physical and virtual memory done for us.
| |
| | |
| Physical memory can fragment all it wants, the VMM can make it look entirely linear in terms of addressing we see, so there is almost no side effect on the RAM side.
| |
| | |
| It's still kept simple because the mechanism that ''does'' those RAM accesses involves a lookup table,
| |
| and it's better if most of that lookup table can stay in hardware (if interested, look for how the TLB works).
| |
| | |
| But all this matters more to people writing operating systems.
| |
| | |
| | |
| | |
| So instead, memory fragmentation typically refers to virtual address fragmentation.
| |
| | |
| Which refers to an app using ''its'' address space badly.
| |
| | |
| For example, its heap may, over time with many alloc()s and free()s, grow holes that fewer allocations can be served by, meaning some percentage of its commited memory won't often be used.
| |
| | |
| | |
| Note that due to swapping, even this has limited ef
| |
| Even this isn't all too bad, due to
| |
| | |
| -->
| |
| | |
| ==Slab allocation==
| |
| {{stub}}
| |
| | |
| | |
| The slab allocator does caches of fixed-size objects.
| |
| | |
| Slab allocation is often used in kernel modules/drivers that are perfectly fine to allocate only uniform-sized and potentially short-lived structures - think task structures, filesystem internals, network buffers.
| |
| | |
| Fixed size, and often separated for each specific type, makes it easier to write an allocator that guarantees allocation within very small timeframe (by avoiding "hey let me look at RAM and all the allocations currently in there" - you can keep track of slots being taken or not with a simple bitmask, and it ''cannot'' fragment).
| |
| | |
| There may also be arbitrary allocation not for specific data structures but for fixed sizes like 4K, 8K, 32K, 64K, 128K, etc, used for things that have known bounds but not precise sizes, for similar lower-time-overhead allocation at the cost of some wasted RAM.
| |
| | |
| | |
| Upsides:
| |
| : Each such cache is easy to handle
| |
| : avoids fragmentation because all holes are of the same size,
| |
| :: that the otherwise-typical [https://en.wikipedia.org/wiki/Buddy_memory_allocation buddy system] still has
| |
| : making slab allocation/free simpler, and thereby a little faster
| |
| : easier to fit them to hardware caches better
| |
| | |
| Limits:
| |
| : It still deals with the page allocator under the cover, so deallocation patterns can still mean that pages for the same cache become sparsely filled - which wastes space.
| |
| | |
| | |
| SLAB, SLOB, SLUB:
| |
| * SLOB: K&R allocator (1991-1999), aims to allocate as compactly as possible. But fragments faster than various others.
| |
| * SLAB: Solaris type allocator (1999-2008), as cache-friendly as possible.
| |
| * SLUB: Unqueued allocator (2008-today): Execution-time friendly, not always as cache friendly, does defragmentation (mostly just of pages with few objects)
| |
| | |
| | |
| For some indication of what's happening, look at {{inlinecode|slabtop}} and {{inlinecode|slabinfo}}
| |
| | |
| See also:
| |
| * http://www.secretmango.com/jimb/Whitepapers/slabs/slab.html
| |
| * https://linux-mm.org/PageAllocation
| |
| | |
| | |
| | |
| There are some similar higher-level allocators "I will handle things of the same type" allocation,
| |
| from some custom allocators in C,
| |
| to object allocators in certain languages,
| |
| arguably even just the implementation of certain data structures.
| |