linux内核虚拟内存管理算法.docx

操作系统第十次实验张焓1. 实验名称：虚拟内存管理算法2. 实验目的：1.分析算法设计原理；2.写出算法伪代码；3.从算法的执行效率等方面分析算法的性能。3. 实验方法通过阅读linux内核代码中管理虚拟内存的代码段学习虚拟内存管理算法的原理。4. 实验步骤(1) mm_struct结构体，定义了每个进程的虚拟存储用户区，首地址在任务结构体中，定义在/include/linux/schedul.h中struct mm_struct struct vm_area_struct *mmap;/* list of VMAs */struct rb_root mm_rb;u32 vmacache_seqnum; /* per-thread vmacache */#ifdef CONFIG_MMUunsigned long (*get_unmapped_area) (struct file *filp,unsigned long addr, unsigned long len,unsigned long pgoff, unsigned long flags);#endifunsigned long mmap_base;/* base of mmap area */unsigned long mmap_legacy_base; /* base of mmap area in bottom-up allocations */unsigned long task_size;/* size of task vm space */unsigned long highest_vm_end;/* highest vma end address */pgd_t * pgd;atomic_t mm_users;/* How many users with user space? */atomic_t mm_count;/* How many references to struct mm_struct (users count as 1) */atomic_long_t nr_ptes;/* PTE page table pages */#if CONFIG_PGTABLE_LEVELS 2atomic_long_t nr_pmds;/* PMD page table pages */#endifint map_count;/* number of VMAs */spinlock_t page_table_lock;/* Protects page tables and some counters */struct rw_semaphore mmap_sem;struct list_head mmlist;/* List of maybe swapped mms.These are globally strung * together off init_mm.mmlist, and are protected * by mmlist_lock */unsigned long hiwater_rss;/* High-watermark of RSS usage */unsigned long hiwater_vm;/* High-water virtual memory usage */unsigned long total_vm;/* Total pages mapped */unsigned long locked_vm;/* Pages that have PG_mlocked set */unsigned long pinned_vm;/* Refcount permanently increased */unsigned long data_vm;/* VM_WRITE & VM_SHARED & VM_STACK */unsigned long exec_vm;/* VM_EXEC & VM_WRITE & VM_STACK */unsigned long stack_vm;/* VM_STACK */unsigned long def_flags;unsigned long start_code, end_code, start_data, end_data;unsigned long start_brk, brk, start_stack;unsigned long arg_start, arg_end, env_start, env_end;unsigned long saved_auxvAT_VECTOR_SIZE; /* for /proc/PID/auxv */* * Special counters, in some configurations protected by the * page_table_lock, in other configurations by being atomic. */struct mm_rss_stat rss_stat;struct linux_binfmt *binfmt;cpumask_var_t cpu_vm_mask_var;/* Architecture-specific MM context */mm_context_t context;unsigned long flags; /* Must use atomic bitops to access the bits */struct core_state *core_state; /* coredumping support */#ifdef CONFIG_AIOspinlock_tioctx_lock;struct kioctx_table _rcu*ioctx_table;#endif#ifdef CONFIG_MEMCG/* * owner points to a task that is regarded as the canonical * user/owner of this mm. All of the following must be true in * order for it to be changed: * * current = mm-owner * current-mm != mm * new_owner-mm = mm * new_owner-alloc_lock is held */struct task_struct _rcu *owner;#endif/* store ref to file /proc/exe symlink points to */struct file _rcu *exe_file;#ifdef CONFIG_MMU_NOTIFIERstruct mmu_notifier_mm *mmu_notifier_mm;#endif#if defined(CONFIG_TRANSPARENT_HUGEPAGE) & !USE_SPLIT_PMD_PTLOCKSpgtable_t pmd_huge_pte; /* protected by page_table_lock */#endif#ifdef CONFIG_CPUMASK_OFFSTACKstruct cpumask cpumask_allocation;#endif#ifdef CONFIG_NUMA_BALANCING/* * numa_next_scan is the next time that the PTEs will be marked * pte_numa. NUMA hinting faults will gather statistics and migrate * pages to new nodes if necessary. */unsigned long numa_next_scan;/* Restart point for scanning and setting pte_numa */unsigned long numa_scan_offset;/* numa_scan_seq prevents two threads setting pte_numa */int numa_scan_seq;#endif#if defined(CONFIG_NUMA_BALANCING) | defined(CONFIG_COMPACTION)/* * An operation with batched TLB flushing is going on. Anything that * can move process memory needs to flush the TLB when moving a * PROT_NONE or PROT_NUMA mapped page. */bool tlb_flush_pending;#endifstruct uprobes_state uprobes_state;#ifdef CONFIG_X86_INTEL_MPX/* address of the bounds directory */void _user *bd_addr;#endif#ifdef CONFIG_HUGETLB_PAGEatomic_long_t hugetlb_usage;#endif#ifdef CONFIG_MMUstruct work_struct async_put_work;#endif;(2) 进程虚存区域，一个虚存区域是许村空间中一个连续区域，每个虚拟区域用一个vm_area_struct结构体描述，定义在/include/linux/mm_type.h中；struct vm_area_struct /* The first cache line has the info for VMA tree walking. */unsigned long vm_start;/* Our start address within vm_mm. */unsigned long vm_end;/* The first byte after our end address within vm_mm. */* linked list of VM areas per task, sorted by address */struct vm_area_struct *vm_next, *vm_prev;struct rb_node vm_rb;/* * Largest free memory gap in bytes to the left of this VMA. * Either between this VMA and vma-vm_prev, or between one of the * VMAs below us in the VMA rbtree and its -vm_prev. This helps * get_unmapped_area find a free area of the right size. */unsigned long rb_subtree_gap;/* Second cache line starts here. */struct mm_struct *vm_mm;/* The address space we belong to. */pgprot_t vm_page_prot;/* Access permissions of this VMA. */unsigned long vm_flags;/* Flags, see mm.h. */* * For areas with an address space and backing store, * linkage into the address_space-i_mmap interval tree. */struct struct rb_node rb;unsigned long rb_subtree_last; shared;/* * A files MAP_PRIVATE vma can be in both i_mmap tree and anon_vma * list, after a COW of one of the file pages.A MAP_SHARED vma * can only be in the i_mmap tree. An anonymous MAP_PRIVATE, stack * or brk vma (with NULL file) can only be in an anon_vma list. */struct list_head anon_vma_chain; /* Serialized by mmap_sem & * page_table_lock */struct anon_vma *anon_vma;/* Serialized by page_table_lock */* Function pointers to deal with this struct. */const struct vm_operations_struct *vm_ops;/* Information about our backing store: */unsigned long vm_pgoff;/* Offset (within vm_file) in PAGE_SIZE units */struct file * vm_file;/* File we map to (can be NULL). */void * vm_private_data;/* was vm_pte (shared mem) */#ifndef CONFIG_MMUstruct vm_region *vm_region;/* NOMMU mapping region */#endif#ifdef CONFIG_NUMAstruct mempolicy *vm_policy;/* NUMA policy for the VMA */#endifstruct vm_userfaultfd_ctx vm_userfaultfd_ctx;(3) linux使用do_mmap()函数完成可执行映像向虚存区域的映射，建立有关的虚存区域，定义在/mm/mmap.c中；unsigned long do_mmap(struct file *file, unsigned long addr,unsigned long len, unsigned long prot,unsigned long flags, vm_flags_t vm_flags,unsigned long pgoff, unsigned long *populate)struct mm_struct *mm = current-mm;int pkey = 0;*populate = 0;if (!len)return -EINVAL;/* * Does the application expect PROT_READ to imply PROT_EXEC? * * (the exception is when the underlying filesystem is noexec * mounted, in which case we dont add PROT_EXEC.) */if (prot & PROT_READ) & (current-personality & READ_IMPLIES_EXEC)if (!(file & path_noexec(&file-f_path)prot |= PROT_EXEC;if (!(flags & MAP_FIXED)addr = round_hint_to_min(addr);/* Careful about overflows. */len = PAGE_ALIGN(len);if (!len)return -ENOMEM;/* offset overflow? */if (pgoff + (len PAGE_SHIFT) map_count sysctl_max_map_count)return -ENOMEM;/* Obtain the address to map to. we verify (or select) it and ensure * that it represents a valid section of the address space. */addr = get_unmapped_area(file, addr, len, pgoff, flags);if (offset_in_page(addr)return addr;if (prot = PROT_EXEC) pkey = execute_only_pkey(mm);if (pkey def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;if (flags & MAP_LOCKED)if (!can_do_mlock()return -EPERM;if (mlock_future_check(mm, vm_flags, len)return -EAGAIN;if (file) struct inode *inode = file_inode(file);switch (flags & MAP_TYPE) case MAP_SHARED:if (prot&PROT_WRITE) & !(file-f_mode&FMODE_WRITE)return -EACCES;/* * Make sure we dont allow writing to an append-only * file. */if (IS_APPEND(inode) & (file-f_mode & FMODE_WRITE)return -EACCES;/* * Make sure there are no mandatory locks on the file. */if (locks_verify_locked(file)return -EAGAIN;vm_flags |= VM_SHARED | VM_MAYSHARE;if (!(file-f_mode & FMODE_WRITE)vm_flags &= (VM_MAYWRITE | VM_SHARED);/* fall through */case MAP_PRIVATE:if (!(file-f_mode & FMODE_READ)return -EACCES;if (path_noexec(&file-f_path) if (vm_flags & VM_EXEC)return -EPERM;vm_flags &= VM_MAYEXEC;if (!file-f_op-mmap)return -ENODEV;if (vm_flags & (VM_GROWSDOWN|VM_GROWSUP)return -EINVAL;break;default:return -EINVAL; else switch (flags & MAP_TYPE) case MAP_SHARED:if (vm_flags & (VM_GROWSDOWN|VM_GROWSUP)return -EINVAL;/* * Ignore pgoff. */pgoff = 0;vm_flags |= VM_SHARED | VM_MAYSHARE;break;case MAP_PRIVATE:/* * Set pgoff according to addr for anon_vma. */pgoff = addr PAGE_SHIFT;break;default:return -EINVAL;/* * Set VM_NORESERVE if we should not account for the * memory use of this mapping. */if (flags & MAP_NORESERVE) /* We honor MAP_NORESERVE if allowed to overcommit */if (sysctl_overcommit_memory != OVERCOMMIT_NEVER)vm_flags |= VM_NORESERVE;/* hugetlb applies strict overcommit unless MAP_NORESERVE */if (file & is_file_hugepages(file)vm_flags |= VM_NORESERVE;addr = mmap_region(file, addr, len, vm_flags, pgoff);if (!IS_ERR_VALUE(addr) & (vm_flags & VM_LOCKED) | (flags & (MAP_POPULATE | MAP_NONBLOCK) = MAP_POPULATE)*populate = len;return addr;算法伪代码：do_mmap()判断是否隐藏了可执行属性；该虚拟区间的地址是否必须有参数addr指定，若不是，重新获取addr地址；检测要映射的文件部分的长度是否是页对齐；offset是否越界；映射数量限制；获得一个一个未映射区间的起始地址，并检查是否是页大小对齐的，即低12位必须*为0；获取文件相关节点inode；如果file结构指针为0，则目的仅在于创建虚拟区间，或者说，并没有真正的映射*发生；如果file结构指针不为0，则目的在于建立从文件到虚拟区间的映射，那就要*根据标志指定的映射种类，把为文件设置的访问权考虑进去;判断输入的欲映射的起始地址是否小于最小映射地址，如果小于，将addr修改为最小地址，不过前提是MAP_FIXED旗标没有设置；查找没有映射过的空洞内存区，返回值addr就是这段空洞的起始地址；对vm_flags进行设置，由参数flags确定vma线性区的flags，是共享还是私有;创建vma，mmap_region();(4) mmap_region()代码如下：unsigned long mmap_region(struct file *file, unsigned long addr,unsigned long len, vm_flags_t vm_flags, unsigned long pgoff)struct mm_struct *mm = current-mm;struct vm_area_struct *vma, *prev;int error;struct rb_node *rb_link, *rb_parent;unsigned long charged = 0;/* Check against address space limit. */if (!may_expand_vm(mm, vm_flags, len PAGE_SHIFT) unsigned long nr_pages;/* * MAP_FIXED may remove pages of mappings that intersects with * requested mapping. Account for the pages it would unmap. */nr_pages = count_vma_pages_range(mm, addr, addr + len);if (!may_expand_vm(mm, vm_flags,(len PAGE_SHIFT) - nr_pages)return -ENOMEM;/* Clear old maps */while (find_vma_links(mm, addr, addr + len, &prev, &rb_link, &rb_parent) if (do_munmap(mm, addr, len)return -ENOMEM;/* * Private writable mapping: check memory availability */if (accountable_mapping(file, vm_flags) charged = len PAGE_SHIFT;if (security_vm_enough_memory_mm(mm, charged)return -ENOMEM;vm_flags |= VM_ACCOUNT;/* * Can we just expand an old mapping? */vma = vma_merge(mm, prev, addr, addr + len, vm_flags,NULL, file, pgoff, NULL, NULL_VM_UFFD_CTX);if (vma)goto out;/* * Determine the object being mapped and call the appropriate * specific mapper. the address has already been validated, but * not unmapped, but the maps are removed from the list. */vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);if (!vma) error = -ENOMEM;goto unacct_error;vma-vm_mm = mm;vma-vm_start = addr;vma-vm_end = addr + len;vma-vm_flags = vm_flags;vma-vm_page_prot = vm_get_page_prot(vm_flags);vma-vm_pgoff = pgoff;INIT_LIST_HEAD(&vma-anon_vma_chain);if (file) if (vm_flags & VM_DENYWRITE) error = deny_write_access(file);if (error)goto free_vma;if (vm_flags & VM_SHARED) error = mapping_map_writable(file-f_mapping);if (error)goto allow_write_and_free_vma;/* -mmap() can change vma-vm_file, but must guarantee that * vma_link() below can deny write-access if VM_DENYWRITE is set * and map writably if VM_SHARED is set. This usually means the * new file must not have been exposed to user-space, yet. */vma-vm_file = get_file(file);error = file-f_op-mmap(file, vma);if (error)goto unmap_and_free_vma;/* Can addr have changed? * * Answer: Yes, several device drivers can do it in their * f_op-mmap method. -DaveM * Bug: If addr is changed, prev, rb_link, rb_parent should * be updated for vma_link() */WARN_ON_ONCE(addr != vma-vm_start);addr = vma-vm_start;vm_flags = vma-vm_flags; else if (vm_flags & VM_SHARED) error = shmem_zero_setup(vma);if (error)goto free_vma;vma_link(mm, vma, prev, rb_link, rb_parent);/* Once vma denies write, undo our temporary denial count */if (file) if (vm_flags & VM_SHARED)mapping_unmap_writable(file-f_mapping);if (vm_flags & VM_DENYWRITE)allow_write_access(file);file = vma-vm_file;out:perf_event_mmap(vma);vm_stat_account(mm, vm_flags, len PAGE_SHIFT);if (vm_flags & VM_LOCKED) if (!(vm_flags & VM_SPECIAL) | is_vm_hugetlb_page(vma) |vma = get_gate_vma(current-mm)mm-locked_vm += (len PAGE_SHIFT);elsevma-vm_flags &= VM_LOCKED_CLEAR_MASK;if (file)uprobe_mmap(vma);/* * New (or expanded) vma always get soft dirty status. * Otherwise user-space soft-dirty page tracker wont * be able to distinguish situation when vma area unmapped, * then new mapped in-place (which must be aimed as * a completely new data area). */vma-vm_flags |= VM_SOFTDIRTY;vma_set_page_prot(vma);return addr;unmap_and_free_vma:vma-vm_file = NULL;fput(file);/* Undo any partial mapping done by a device driver. */unmap_region(mm, vma, prev, vma-vm_start, vma-vm_end);charged = 0;if (vm_flags & VM_SHARED)mapping_unmap_writable(file-f_mapping);allow_write_and_free_vma:if (vm_flags & VM_DENYWRITE)allow_write_access(file);free_vma:kmem_cache_free(vm_area_cachep, vma);unacct_error:if (charged)vm_unacct_memory(charged);return error;算法伪代码：mmap_region()寻找前后一个区域的vm_area_struct实例以及红黑树中节点对应的数据；if(在指定的映射位置已经存在映射)do_munmap();检查内存空间是否满足需求，是否需要扩充；如果是匿名映射（file为空），并且这个虚拟区是非共享的，则可以把这个虚拟区和*与它紧挨的前一个虚拟区进行合并；虚拟区的合并是由vma_merge()函数实现的。如*果合并成功，则转out处，请看后面out处的代码;创建新的vm_area_strcut实例；file-f_op-mmap();/创建映射if(VM_LOCKED)扫描映射中各页发出的中断以便读取数据；retuen 映射的起始地址；(5) linux使用do_munmap()函数取消断开可执行映像向虚存区域的映射，删除有关的虚存区域，定义在/mm/mmap.c中；int do_munmap(struct mm_struct *mm, unsigned long start, size_t len)unsigned long end;struct vm_area_struct *vma, *prev, *last;if (offset_in_page(start) | start TASK_SIZE | len TASK_SIZE-start)return -EINVAL;len = PAGE_ALIGN(len);if (len = 0)return -EINVAL;/* Find the first overlapping VMA */vma = find_vma(mm, start);if (!vma)return 0;prev = vma-vm_prev;/* we have start vm_end */* if it doesnt overlap, we have nothing. */end = start + len;if (vma-vm_start = end)return 0;/* * If we need to split any vma, do it now to save pain later. * * Note: mremaps move_vma VM_ACCOUNT handling assumes a partially * unmapped vm_area_struct will remain in use: so lower split_vma * places tmp vma above, and higher split_vma places tmp vma below. */if (start vma-vm_start) int error;/* * Make sure that map_count on return from munmap() will * not exceed its limit; but let map_count go just above * its limit temporarily, to help free resources as expected. */if (end vm_end & mm-map_count = sysctl_max_map_count)return -ENOMEM;error = _split_vma(mm, vma, start, 0);if (error)return error;prev = vma;/* Does it split the last one? */last = find_vma(mm, end);if (last & end last-vm_start) int error = _split_vma(mm, last, end, 1);if (error)return error;vma = prev ? prev-vm_next : mm-mma