Tour De Linux Memory Management - D3s.mff.cuni.cz

page VMA mappings How to get from struct page to all mappings? (mm/rmap.c) rmap walk – rmap walk control defines callback to call for each mappingpage::mapping, page::index Anonymous pages – page::mapping has the lowest bit set anon vma page mapping & PAGE MAPPING FLAGS Address space of all anonymous pages – hierarchical tree of interval treesINTERVAL TREE DEFINE(struct anon vma chain, rb, unsigned long, rb subtree last,avc start pgoff, avc last pgoff,static inline, anon vma interval tree) More on https://lwn.net/Articles/383162/ pgoff page index anon vma interval tree foreach – iterates over all VMAs which contain pgoffFile backed pages Mapping points to struct address space – one per each inode/block device mapping i mmap contains interval tree of all VMAs vma interval tree foreach iterates over all VMAs which contain pgoff17

Address space – gluing it togethermm structVMAVMAVMAanon vmavm filestruct filestruct anon vmaf inodestruct inodei mappingrb rootstruct anon vma chaini mmapstruct address spacemapping & PAGE MAPPING FLAGSmappingstruct pageindexindexstruct page18

Page cache management address space::page tree - radix tree of pages belonging to theinode – move to xarray in the recent pastfilemap fault find get page Returns an existing page from the radix tree or allocates a new onepage cache alloc() and inserted to the radix treeadd to page cache locked() and LRU listPage is locked and !PageUptodate() if newly allocateddo async mmap readahead() – triggers asynchronous read from thebacking storage (including readahead).do sync mmap readahead() – synchronous readread pages – mapping a ops readpages() – to do the actual read fromthe (fs usually use mpage readpages())Once we have the content – SetPageUptodate() PageUnlock()19

Page allocator alloc pages nodemask(gfp t gfp mask, unsigned int order, struct zonelist *zonelist,nodemask t *nodemask) to get a struct pageget free pages() to get a directly usable pointer – use with care!gfp mask – bitmask for the allocation mode Request specific zones – GFP DMA, GFP DMA32, GFP HIGHMEM, GFP MOVABLE GFP NOWAIT, GFP ATOMIC – non sleeping allocations, no direct reclaim GFP KERNEL – standard kernel allocations GFP USER, GFP USER MOVABLE – allocations for userspace GFP NOFAIL – non-failing allocations GFP NOFS, GFP NOIO – do not recurse to fs perform any IO from the reclaimOrder – size of the allocation 2 order contiguous pages PAGE ALLOC COSTLY ORDER (3) – small allocations are special – trigger OOM killer rather than failZonelists – list of zones to allocate from Start with zones of a local or requested node - node zonelist() build zonelists() - numa zonelist order kernel boot parameter – node order, zone orderNodemask to filter only allowed nodes defined by memory policy Note that there is also cpuset API to overrule memory policiesFunny things will happen if those two disagree20

Page allocator Slow path quite complex Core of the page allocator – get page from freelist() Wake up kswapd/kcompactdTriggers direct memory reclaim/compaction when neededTriggers the OOM killer when no progress was made during the reclaimChecks watermarks to not allow memory depletionPer-cpu allocation for order-0 – no locking, batch refill, freeing - rmqueue pcplist()rmqueue() for other ordersBased on buddy allocator Physically contiguous pages are grouped in 2N chunks2 2N-1 blocks are merged to 2N when page is freed - free one page()A larger block is split up when appropriate is not available - rmqueue smallest()vs rmqueue fallback() cat /proc/buddyinfoNode 0, zoneDMA10101110113Node 0, zoneDMA327435357542538Node 0, zoneNormal438445339715888773671777436731221

Memory reclaim Background reclaim The main logic implemented in balance pgdat()Direct reclaim All eligible zones hit the min watermark Tries to free SWAP CLUSTER MAX pages The main logic implemented in try to free pages()Node reclaim – former zone reclaim Kernel thread per NUMA nodeStarts when free memory hit low watermark on all zones eligible for the allocation –pgdat balanced()Reclaims until high watermark is hitEnforce direct reclaim on the requested node firstUsed to be enabled on NUMA machines with large numa distances in the pastHas to be enabled explicitly - /proc/sys/vm/zone reclaim modeOOM killer Last despair attempt to free memory by killing the task with the largest memory consumptionoom reaper – kernel thread to unmap memory of the oom victimVery tricky to get right22

Memory reclaim Reclaimable pages are sitting on LRU lists – struct lruvecenum lru list {LRU INACTIVE ANON LRU BASE,LRU ACTIVE ANON LRU BASE LRU ACTIVE,LRU INACTIVE FILE LRU BASE LRU FILE,LRU ACTIVE FILE LRU BASE LRU FILE LRU ACTIVE,LRU UNEVICTABLE,NR LRU LISTS}; Used to have LRU lists per zones, now we have one per node Pages are added to the list when allocatedAnonymous pages start on the active listFile pages start on the inactive list Pages freed recently are put to the active list - workingset refault()Promotion from inactive to active list based on pte references –page check references() Actually per memory cgroup – more on that laterUsed once heuristic for file pagesExecutable pages protectionActive list is shrunk when it grows too large – inactive list is low()23

Memory reclaim Each reclaim pass has a priority – starting from DEF PRIORITY (12) get scan count() - keeps balance between file and anonymous lru lists Highly biased to reclaim file pages/proc/sys/vm/swappinessConsiders recently scanned and rotated pages for each LRUisolate lru pages() - removes pages from the LRU list in a batch for further inspection Size of the window to scan LRU lists – lruvec lru size() priorityReduces the lock contentionSkip over ineligible pages – e.g. highmem pages for GFP KERNEL requestshrink page list() - core of the reclaim Referenced pages are promoted to the active listAnonymous pages are added to the swap cache and scheduled for swapout - add to swap()Dirty file pages are written out – pageout() - only in kswapd contextMapped pages are unmapped – try to unmap one() Anonymous ptes will point to swap entries, MADV FREE pages are dropped Dirty pte states is moved to struct page – set page dirty()remove mapping() Dirty pages are not removed – protection for racesRemove from the page cache (including swap cache) – records the eviction time for file cacheworkingset eviction()24

Memory reclaim Many types of SLAB allocations are reclaimable Dentry, inode cache etc Register their shrinkers Not restricted to slab objects onlystruct shrinker {unsigned long (*count objects)(struct shrinker *,struct shrink control *sc);unsigned long (*scan objects)(struct shrinker *,struct shrink control *sc);int seeks;/* seeks to recreate an obj */long batch;/* reclaim batch size, 0 default */unsigned long flags;/* These are for internal use */struct list head list;/* objs pending delete, per node */atomic long t *nr deferred;}; shrink slab() Invokes shrinkers – count objects() to see how many are freeable, scan objects willreclaim and ageCan be really inefficient because it is object rather than page based – internalfragmentation25

Huge pages in Linux Kernel mapping of physical memoryUses 1GB or 2MB huge pages when possible Direct mapping, ioremap() for device memory rangesExplicit hugepage usage – HugeTLBfs Pre-allocated in pools, accessible by several interfaces Private or shared, no splitting, no swapping Multiple sizes supported; page table sharing supportTransparent hugepage usage – THP Allocated implicitly, possible to prefer or disallow by hints Anonymous, private (except fork COW), can be split back to base pagesand then swapped out Shmem/tmpfs support – controlled via mount parameter

HugeTLBfs Usage SysV shared memory segment Sice 3.8: same alternative flags as shmget()mount -t hugetlbfs none /dev/hugepages -o pagesize 2M fd open(“/dev/hugepages/1”, O CREAT O RDWR, 0755);addr mmap(NULL, SIZE, PROT *, MAP SHARED, fd, 0);Use libhugetlbfs library – man libhugetlbfs(7) addr mmap(NULL, SIZE, PROT *,MAP PRIVATE MAP ANONYMOUS MAP HUGETLB, -1, 0);Mount a special virtual filesystem Since 3.8: alternative flags SHM HUGE 2MB, SHM HUGE 1GB, and SHM HUGE SHIFTAnonymous mmap() shmid shmget(key, SIZE, SHM HUGETLB );addr shmat(shmid, NULL, 0);get huge pages(), get hugepage region().LD PRELOAD for legacy applicationsText, data, malloc(), shared memory backed by hugepagesUseful tools: hugeadm, hugectl

HugeTLBfs Internals Hugetlb pages reserved on mmap() Reservation system tracksCheaper mmap(), potentially better NUMA placementPrivate mappings can fork() COW fault at any time Potential copies not reserved – fork() won’t failCOW will try to allocate without reserve, but that can fail Child COW alloc fails SIGBUS Parent COW alloc fails child’s mapping removed, fault SIGBUS Reservations don’t guarantee NUMA placementShared page tables Scenario: many processes mapping the same region of 2MB hugepagesEach 1GB large region (fully populated or not) would have 4KB pmd-level page table foreach processThis page table will be shared when mappings are properly aligned, reducing thememory usageExample: Memory usage of (system running Oracle) by page tables 150GB without vs1GB with HugeTLB

THP First page fault in each huge-page aligned part of vma (last-level pagetable does not yet exist) Read fault map a shared “THP zero page” firstDuring mmap() with MAP POPULATEKhugepaged merge small pages into THP in the backgroundIf allocating huge page fails, fallback to mapping a page table with asingle PTE entry for a base pageCOW – alloc copy whole huge page, fallback to alloc copy many basepages mapped by PTEsTHP may be mapped by ptes partially – mprotect, unmapFault in resp. merging policy fine tuning madvise(MADV HUGEPAGE, MADV NOHUGEPAGE)prctl(PR SET THP DISABLE)Global setting - /sys/kernel/mm/transparent hugepage/ allways, madvise, never for global settingallways, madvise, never, defer, defer madvise for khugepagedShmem controlled by mount option allways, advise, never, within size

THP - khugepaged Kernel thread to scan address space/sys/kernel/mm/transparent hugepage/khugepaged/*Merges sparsely populated PMD Pros max ptes none – how much more to allocatemax ptes swap – how much to swap inpages to scan, scan sleep millisecs – how much/often to scanFault in is latency sensitive while deferred context might try harderVMAs might grow over time (e.g. stack, shmem file)Reduces memory fragmentationCons Background interference – e.g. mmap sem lock contentionJumps in too late for short lived mappings

THP related statistics/proc/meminfoAnonHugePages:1929216 kBShmemHugePages, ShmemPmdMapped/proc/vmstatthp split page 5542thp fault alloc 174171thp split page failed 4thp fault fallback 61457thp deferred split page 199thp collapse alloc 35893thp collapse alloc failed 703 thp split pmd 26504thp split pud 0thp file alloc 0thp zero page alloc 1thp file mapped 0thp zero page alloc failed 0/sys/kernel/mm/transparent hugepage/khugepagedfull scans: 751pages collapsed: 26272

Memory cgroup controller Hierarchical accounting of user memory (page faults) and opt-in kernelallocations GFP ACCOUNT (e.g. kernel stacks)Represented by struct mem cgroup Page counters for chargesOwn LRUs – mem cgroup::nodeinfo – per NUMA nodeMemory is charged when the page is added to the LRU list or in the pageallocator for kernel allocations - try charge() Charge is propagated up the hierarchyPerforms direct reclaim on the memcg which hits hard limit mem cgroup shrink node() shrink node memcg() - iterates over all lruvecs under given mem cgroup in a round robinmannerCode shared with the standard reclaim – some exceptions, we wait for Dirty pages, swappiness isnot ignored even under hard memory pressure etc.Schedules “background” reclaim when high limit is reached – reclaim high() whenreturning to the user spaceLow/Min limit protects memory cgroup from reclaim32

Memory cgroup controller Charge fails and marks OOM context when the reclaim fails Memcg OOM killer can be handled from userspace Only kills tasks from the memcg hierarchyecho 1 memory.oom control – disables oom killer, the kernel will notifylistener on this file and waits for situation to change mem cgroup oom synchronize()Admin may increase the limit or kill a task manuallyOnly page faults are triggering memcg OOM killerpagefault out of memory() Used to trigger it from the charge path but this could deadlock easily – chargecontext can hold locks which might be needed for OOM to make a forwardprogress33

Questions?34

Unpublished Work of SUSE LLC. All Rights Reserved.This work is an unpublished work and contains confidential, proprietary and trade secret information of SUSE LLC.Access to this work is restricted to SUSE employees who have a need to know to perform tasks within the scope of theirassignments. No part of this work may be practiced, performed, copied, distributed, revised, modified, translated,abridged, condensed, expanded, collected, or adapted without the prior written consent of SUSE.Any use or exploitation of this work without authorization could subject the perpetrator to criminal and civil liability.General DisclaimerThis document is not to be construed as a promise by any participating company to develop, deliver, or market aproduct. It is not a commitment to deliver any material, code, or functionality, and should not be relied upon in makingpurchasing decisions. SUSE makes no representations or warranties with respect to the contents of this document, andspecifically disclaims any express or implied warranties of merchantability or fitness for any particular purpose. Thedevelopment, release, and timing of features or functionality described for SUSE products remains at the sole discretionof SUSE. Further, SUSE reserves the right to revise this document and to make changes to its content, at any time,without obligation to notify any person or entity of such revisions or changes. All SUSE marks referenced in thispresentation are trademarks or registered trademarks of Novell, Inc. in the United States and other countries. All thirdparty trademarks are the property of their respective owners.36

4 Purpose and the scope of MM APIs for kernel Bootmem/memblock allocator - early initialization Page allocator - page order (2N physically contiguous pages) SLAB allocator - sub page granularity, internal fragmentation management SLOB - very rudimentary for small devices SLAB - based on Solaris design - optimized for CPU cache efficiency, NUMA aware