[数据结构与算法]内存映射原理

内存映射原理

a. 内存映射原理

? 内存映射即在进程的虚拟地址空间中创建一个映射，分为两种：

• 文件映射：文件支持的内存映射，把文件的一个区间映射到进程的虚拟地址空间，数据源是存储设备上的文件。
• 匿名映射：没有文件支持的内存映射，把物理内存映射到进程的虚拟地址空间，没有数据源。

创建内存映射时，在进程的用户虚拟地址空间中分配一个虚拟内存区域。内核采用延迟分配物理内存的策略，在进程第一次访问虚拟页的时候，产生缺页异常。如果是文件映射，那么分配物理页，把文件指定区间的数据读到物理页中，然后在页表中把虚拟页映射到物理页。
如果是匿名映射，就分配物理页，然后在页表中把虚拟页映射到物理页。

内核必须提供数据结构，以建立虚拟地址空间的区域和相关数据所在位置之间的关联。例如，在映射文本文件时，映射的虚似内存区必须关联到文件系统在硬盘上存储文件内容的区域。

当然，给出的图示是简化的，因为文件数据在硬盘上的存储通常并不是连续的，而是分布到若干小的区域。内核利用address_space数据结构，提供一组方法从后备存储器读取数据。例如，从文件系统读取。因此address_space形成了一个辅助层，将映射的数据表示为连续的线性区域，提供给内存管理子系统。按需分配和填充页称之为按需调页法（ demand paging）。它基于处理器和内核之间的交互，使用的各种数据结构如图。

• 进程试图访问用户地址空间中的一个内存地址，但使用页表无法确定物理地址（物理内存中没有关联页）。

• 处理器接下来触发一个缺页异常，发送到内核。

• 内核会检查负责缺页区域的进程地址空间数据结构，找到适当的后备存储器，或者确认该访问实际上是不正确的。

• 分配物理内存页，并从后备存储器读取所需数据填充。

• 借助于页表将物理内存页并入到用户进程的地址空间，应用程序恢复执行。

这些操作对用户进程是透明的。换句话说，进程不会注意到页是实际在物理内存中，还是需要通过按需调页加载。

b.数据结构

虚拟内存区域分配给进程的一个虚拟地址范围，内核使用结构体vm_area_struct描述虚拟内存区域，主要核心成员如下：

我们知道struct mm_struct很重要，该结构提供了进程在内存中布局的所有必要信息。另外，它还包括下列成员，用于管理用户进程在虚拟地址空间中的所有内存区域。

/*mm_types.h*/
struct mm_struct {
	struct vm_area_struct *mmap;		/* list of VMAs */
	struct rb_root mm_rb;
	u32 vmacache_seqnum;                   /* per-thread vmacache */
	.....
}

用户虚拟地址空间中的每个区域由开始和结束地址描述。现存的区域按起始地址以递增次序被归入链表中。扫描链表找到与特定地址关联的区域，在有大量区域时是非常低效的操作（数据密集型的应用程序就是这样）。因此vm_area_struct的各个实例还通过红黑树管理，可以显著加快扫描速度。增加新区域时，内核首先搜索红黑树，找到刚好在新区域之前的区域。因此，内核可以向树和线性链表添加新的区域，而无需扫描链表。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zknBf3AO-1638714343843)(C:\Users\wangzhen\AppData\Roaming\Typora\typora-user-images\image-20211205101738426.png)]

b.1 虚拟内存区域的数据结构

每个区域表示为vm_area_struct的一个实例，其定义（简化形式）如下：

/*
 * This struct defines a memory VMM memory area. There is one of these
 * per VM-area/task.  A VM area is any part of the process virtual memory
 * space that has a special rule for the page-fault handlers (ie a shared
 * library, the executable area etc).
 */
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; //采用 红黑树（每个进程结构体mm_struct中都创建一颗红黑树，将VMA作为一个节点加入到红黑树中，提升搜索速度）

	/*
	 * 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. */
    /*
    #define VM_READ           0x00000001
    #define VM_WRITE		 0x00000002
    #define VM_EXEC           0x00000004
    #define VM_SHARED         0x00000008
    */
	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 file's 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.
	 */
    //把虚拟内存区域关联的所有的anon_vma实例串联起来，一个虚拟内存区域会关联到父进程的anon_vma实例和自己的anon_vma实例
	struct list_head anon_vma_chain; /* Serialized by mmap_sem &
					  * page_table_lock */
    //指向一个anon_vma实例，结构anon_vma用来组织匿名页被映射到的所有的虚拟地址空间
	struct anon_vma *anon_vma;	/* Serialized by page_table_lock */

	/* Function pointers to deal with this struct. */
    /*
    <mm.h>
    struct vm_operations_struct {
	void (*open)(struct vm_area_struct * area);
	void (*close)(struct vm_area_struct * area);
	int (*mremap)(struct vm_area_struct * area);
	int (*fault)(struct vm_area_struct *vma, struct vm_fault *vmf);
	int (*pmd_fault)(struct vm_area_struct *, unsigned long address, pmd_t *, unsigned int flags);
	void (*map_pages)(struct vm_area_struct *vma, struct vm_fault *vmf);
	int (*page_mkwrite)(struct vm_area_struct *vma, struct vm_fault *vmf);
	int (*pfn_mkwrite)(struct vm_area_struct *vma, struct vm_fault *vmf);
	int (*access)(struct vm_area_struct *vma, unsigned long addr, void *buf, int len, int write);
	const char *(*name)(struct vm_area_struct *vma);
	struct page *(*find_special_page)(struct vm_area_struct *vma, unsigned long addr);
    */
	const struct vm_operations_struct *vm_ops;

	/* Information about our backing store: */
    //文件偏移，单位是页
	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
					   units, *not* PAGE_CACHE_SIZE */
	struct file * vm_file;		/* File we map to (can be NULL). */
	void * vm_private_data;		/* was vm_pte (shared mem) 指向内存区的私有数据*/

#ifndef CONFIG_MMU
	struct vm_region *vm_region;	/* NOMMU mapping region */
#endif
#ifdef CONFIG_NUMA
	struct mempolicy *vm_policy;	/* NUMA policy for the VMA */
#endif
	struct vm_userfaultfd_ctx vm_userfaultfd_ctx;
};

c. 系统调用和mmap内存映射

c.1 系统调用

应用程序通常使用C标准库提供的函数malloc()申请内存，glibc库的内存分配器ptmalloc使用brk或mmap向内核以页为单位申请虚拟内存，然后把页划分成小内存块分配给应用程序。默认的阈值时128kb，如果应用程序申请的内存长度小于阈值，ptmalloc分配器使用brk向内核申请虚拟内存，否则ptmalloc分配器使用mmap向内核申请虚拟内存。应用程序可以直接使用mmap向内核申请虚拟内存。

我们已经熟悉了内存映射相关的数据结构和地址空间操作，在本节中，我们将进一步讨论在建立映射时内核和应用程序之间的交互。就我们所知， C标准库提供了mmap 函数建立映射。在内核一端，提供了两个系统调用mmap和mmap2。两个函数的参数相同。

void* mmap(void* start,size_t length,int prot,int flags,int fd,off_t offset);

这两个调用都会在用户虚拟地址空间中的pos位置，建立一个长度为len的映射，其访问权限通过prot定义。 flags是一个标志集，用于设置一些参数。相关的文件通过其文件描述符fd标识。

mmap和mmap2之间的差别在于偏移量的语义（ off）。在这两个调用中，它都表示映射在文件中开始的位置。对于mmap，位置的单位是字节，而mmap2使用的单位则是页（ PAGE_SIZE）。因此即使文件比可用地址空间大，也可以映射文件的一部分。通常C标准库只提供一个函数，由应用程序用来创建内存映射。接下来该函数调用在内部转换为适合于体系结构的系统调用。可使用munmap系统调用删除映射。因为不需要文件偏移量，因此不需要munmap2系统调用，只需提供映射的虚拟地址。

参数start：指向欲映射的内存起始地址，通常设为 NULL，代表让系统自动选定地址，映射成功后返回该地址。

参数length：代表将文件中多大的部分映射到内存。

参数prot：映射区域的保护方式。可以为以下几种方式的组合：
PROT_EXEC 映射区域可被执行
PROT_READ 映射区域可被读取
PROT_WRITE 映射区域可被写入
PROT_NONE 映射区域不能存取

参数flags：影响映射区域的各种特性。在调用mmap()时必须要指定MAP_SHARED 或MAP_PRIVATE。

MAP_FIXED 如果参数start所指的地址无法成功建立映射时，则放弃映射，不对地址做修正。通常不鼓励用此旗标。
MAP_SHARED对映射区域的写入数据会复制回文件内，而且允许其他映射该文件的进程共享。
MAP_PRIVATE 对映射区域的写入操作会产生一个映射文件的复制，即私人的“写入时复制”（copy on write）对此区域作的任何修改都不会写回原来的文件内容。
MAP_ANONYMOUS建立匿名映射。此时会忽略参数fd，不涉及文件，而且映射区域无法和其他进程共享。
MAP_DENYWRITE只允许对映射区域的写入操作，其他对文件直接写入的操作将会被拒绝。
MAP_LOCKED 将映射区域锁定住，这表示该区域不会被置换（swap）。

参数fd：要映射到内存中的文件描述符。如果使用匿名内存映射时，即flags中设置了MAP_ANONYMOUS，fd设为-1。有些系统不支持匿名内存映射，则可以使用fopen打开/dev/zero文件，然后对该文件进行映射，可以同样达到匿名内存映射的效果。

参数offset：文件映射的偏移量，通常设置为0，代表从文件最前方开始对应，offset必须是分页大小的整数倍。

返回值：若映射成功则返回映射区的内存起始地址，否则返回MAP_FAILED(－1)，错误原因存于errno 中。

错误代码：

EBADF 参数fd 不是有效的文件描述词
EACCES 存取权限有误。如果是MAP_PRIVATE 情况下文件必须可读，使用MAP_SHARED则要有PROT_WRITE以及该文件要能写入。
EINVAL 参数start、length 或offset有一个不合法。
EAGAIN 文件被锁住，或是有太多内存被锁住。
ENOMEM 内存不足。

我们回顾一下mmap内存映射原理的三个阶段：

1. 进程启动映射过程，并且在虚拟地址空间为映射创建虚拟映射区域；
2. 调用内核空间的系统调用函数mmap(不同于用户空间函数)，实现文件物理地址和进程虚拟的一一映射关系；
3. 进程发起对这片映射空间的访问，引发缺页异常，实现文件内容到物理内存(主存)的拷贝。

munmap()----删除内存映射
#include <sys/mman.h>
int munmap(void *addr, size_t len);

mprotect()----设置虚拟内存区域的访问权限
#include <sys/mman.h>
int mprotect(void *addr, size_t len, int prot);

//进程1
#include <sys/mman.h>
#include <sys/types.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>

typedef struct 
{
    /* data */
    char name[4];
    int age;
}people;


void main(int argc,char**argv)
{
    int fd,i;
    people *p_map;
    char temp;
    fd=open(argv[1],O_CREAT|O_RDWR|O_TRUNC,00777);

    lseek(fd,sizeof(people)*5-1,SEEK_SET);
    write(fd,"",1);

    p_map=(people*)mmap(NULL,sizeof(people)*10,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);
    if(p_map==(void*)-1)
    {
        fprintf(stderr,"mmap : %s \n",strerror(errno));
        return ;
    }
    close(fd);

    temp='A';
    for(i=0;i<10;i++)
    {
        (*(p_map+i)).name[1]='\0';
        memcpy((*(p_map+i)).name,&temp,1);
        (*(p_map+i)).age=30+i;
        temp=temp+1;
    }

    printf("Initialize.\n");

    sleep(15);

    munmap(p_map,sizeof(people)*10);

    printf("UMA OK.\n");

}

//进程2
#include <sys/mman.h>
#include <sys/types.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>

typedef struct 
{
    /* data */
    char name[4];
    int age;
}people;

void main(int argc,char**argv)
{
    int fd,i;
    people *p_map;

    fd=open(argv[1],O_CREAT|O_RDWR,00777);
    p_map=(people*)mmap(NULL,sizeof(people)*10,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);
    if(p_map==(void*)-1)
    {
        fprintf(stderr,"mmap : %s \n",strerror(errno));
        return ;
    }

    for(i=0;i<10;i++)
    {
        printf("name:%s age:%d\n",(*(p_map+i)).name,(*(p_map+i)).age);
    }

    munmap(p_map,sizeof(people)*10);   

}

//mprotect

#include <unistd.h>
#include <signal.h>
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/mman.h>

#define handle_error(msg) do{ perror(msg); exit(EXIT_FAILURE);}while(0)

static char *buffer;

static void handler(int sig,siginfo_t *si,void *unused)
{
    printf("Get SIGSEGV at address : %p\n",si->si_addr);
    exit(EXIT_FAILURE);
}

int main(int argc,char *argv[])
{
    int pagesize;
    struct sigaction sa;

    sa.sa_flags=SA_SIGINFO;
    sigemptyset(&sa.sa_mask);
    sa.sa_sigaction=handler;

    if(sigaction(SIGSEGV,&sa,NULL)==-1)
        handle_error("siaction");

    pagesize=sysconf(_SC_PAGE_SIZE);
    if(pagesize==-1)
        handle_error("sysconf");

    buffer=memalign(pagesize,4*pagesize);
    if(buffer==NULL)
        handle_error("memalign");

    printf("start of region : %p\n",buffer);

    if(mprotect(buffer+pagesize*2,pagesize,PROT_READ)==-1)
        handle_error("mprotect");

        for(char *p=buffer;;)
        *(p++)='A';

        printf("for completed.\n");
        exit(EXIT_SUCCESS);

    return 0;
}