kk Blog —— 通用基础

struct vm_area_struct {
	struct mm_struct * vm_mm;   /* 所属的内存描述符 */
	unsigned long vm_start;    /* vma的起始地址 */
	unsigned long vm_end;       /* vma的结束地址 */

	/* 该vma的在一个进程的vma链表中的前驱vma和后驱vma指针，链表中的vma都是按地址来排序的*/
	struct vm_area_struct *vm_next, *vm_prev;

	pgprot_t vm_page_prot;      /* vma的访问权限 */
	unsigned long vm_flags;    /* 标识集 */

	struct rb_node vm_rb;      /* 红黑树中对应的节点 */

	/*
	 * For areas with an address space and backing store,
	 * linkage into the address_space->i_mmap prio tree, or
	 * linkage to the list of like vmas hanging off its node, or
	 * linkage of vma in the address_space->i_mmap_nonlinear list.
	 */
	/* shared联合体用于和address space关联 */
	union {
		struct {
			struct list_head list;/* 用于链入非线性映射的链表 */
			void *parent;   /* aligns with prio_tree_node parent */
			struct vm_area_struct *head;
		} vm_set;

		struct raw_prio_tree_node prio_tree_node;/*线性映射则链入i_mmap优先树*/
	} 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.
	 */
	/*anno_vma_node和annon_vma用于管理源自匿名映射的共享页*/
	struct list_head anon_vma_node; /* Serialized by anon_vma->lock */
	struct anon_vma *anon_vma;  /* Serialized by page_table_lock */

	/* Function pointers to deal with this struct. */
	/*该vma上的各种标准操作函数指针集*/
	const struct vm_operations_struct *vm_ops;

	/* Information about our backing store: */
	unsigned long vm_pgoff;     /* 映射文件的偏移量，以PAGE_SIZE为单位 */
	struct file * vm_file;          /* 映射的文件，没有则为NULL */
	void * vm_private_data;     /* was vm_pte (shared mem) */
	unsigned long vm_truncate_count;/* truncate_count or restart_addr */

#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 address_space {
	struct inode        *host;      /* owner: inode, block_device */
	...
	struct prio_tree_root   i_mmap;     /* tree of private and shared mappings */
	struct list_head    i_mmap_nonlinear;          /*list VM_NONLINEAR mappings */
	...
} __attr

struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
	struct vm_area_struct *vma = NULL;

	if (mm) {
		/* Check the cache first. */
		/* (Cache hit rate is typically around 35%.) */
		vma = mm->mmap_cache; //首先尝试mmap_cache中缓存的vma
		/*如果不满足下列条件中的任意一个则从红黑树中查找合适的vma
		  1.缓存vma不存在
		  2.缓存vma的结束地址小于给定的地址
		  3.缓存vma的起始地址大于给定的地址*/
		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
			struct rb_node * rb_node;

			rb_node = mm->mm_rb.rb_node;//获取红黑树根节点
			vma = NULL;

			while (rb_node) {
				struct vm_area_struct * vma_tmp;

				vma_tmp = rb_entry(rb_node,   //获取节点对应的vma
						struct vm_area_struct, vm_rb);

				/*首先确定vma的结束地址是否大于给定地址，如果是的话，再确定
				  vma的起始地址是否小于给定地址，也就是优先保证给定的地址是
				  处于vma的范围之内的，如果无法保证这点，则只能找到一个距离
				  给定地址最近的vma并且该vma的结束地址要大于给定地址*/
				if (vma_tmp->vm_end > addr) {
					vma = vma_tmp;
					if (vma_tmp->vm_start <= addr)
						break;
					rb_node = rb_node->rb_left;
				} else
					rb_node = rb_node->rb_right;
			}
			if (vma)
				mm->mmap_cache = vma;//将结果保存在缓存中
		}
	}
	return vma;
}

struct vm_area_struct *vma_merge(struct mm_struct *mm,
			struct vm_area_struct *prev, unsigned long addr,
			unsigned long end, unsigned long vm_flags,
			struct anon_vma *anon_vma, struct file *file,
			pgoff_t pgoff, struct mempolicy *policy)
{
	pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
	struct vm_area_struct *area, *next;

	/*
	 * We later require that vma->vm_flags == vm_flags,
	 * so this tests vma->vm_flags & VM_SPECIAL, too.
	 */
	if (vm_flags & VM_SPECIAL)
		return NULL;

	if (prev)//指定了先驱vma，则获取先驱vma的后驱vma
		next = prev->vm_next;
	else     //否则指定mm的vma链表中的第一个元素为后驱vma
		next = mm->mmap;
	area = next;

	/*后驱节点存在，并且后驱vma的结束地址和给定区域的结束地址相同，
	  也就是说两者有重叠，那么调整后驱vma*/
	if (next && next->vm_end == end)     /* cases 6, 7, 8 */
		next = next->vm_next;

	/*
	 * 先判断给定的区域能否和前驱vma进行合并，需要判断如下的几个方面:
	   1.前驱vma必须存在
	   2.前驱vma的结束地址正好等于给定区域的起始地址
	   3.两者的struct mempolicy中的相关属性要相同，这项检查只对NUMA架构有意义
	   4.其他相关项必须匹配，包括两者的vm_flags，是否映射同一个文件等等
	 */
	if (prev && prev->vm_end == addr &&
			mpol_equal(vma_policy(prev), policy) &&
			can_vma_merge_after(prev, vm_flags,
						anon_vma, file, pgoff)) {
		/*
		 *确定可以和前驱vma合并后再判断是否能和后驱vma合并，判断方式和前面一样，
		  不过这里多了一项检查，在给定区域能和前驱、后驱vma合并的情况下还要检查
		  前驱、后驱vma的匿名映射可以合并
		 */
		if (next && end == next->vm_start &&
				mpol_equal(policy, vma_policy(next)) &&
				can_vma_merge_before(next, vm_flags,
					anon_vma, file, pgoff+pglen) &&
				is_mergeable_anon_vma(prev->anon_vma,
							  next->anon_vma)) {
							/* cases 1, 6 */
			vma_adjust(prev, prev->vm_start,
				next->vm_end, prev->vm_pgoff, NULL);
		} else                  /* cases 2, 5, 7 */
			vma_adjust(prev, prev->vm_start,
				end, prev->vm_pgoff, NULL);
		return prev;
	}

	/*
	 * Can this new request be merged in front of next?
	 */
	 /*如果前面的步骤失败，那么则从后驱vma开始进行和上面类似的步骤*/
	if (next && end == next->vm_start &&
			mpol_equal(policy, vma_policy(next)) &&
			can_vma_merge_before(next, vm_flags,
					anon_vma, file, pgoff+pglen)) {
		if (prev && addr < prev->vm_end)  /* case 4 */
			vma_adjust(prev, prev->vm_start,
				addr, prev->vm_pgoff, NULL);
		else                    /* cases 3, 8 */
			vma_adjust(area, addr, next->vm_end,
				next->vm_pgoff - pglen, NULL);
		return area;
	}

	return NULL;
}

void vma_adjust(struct vm_area_struct *vma, unsigned long start,
	unsigned long end, pgoff_t pgoff, struct vm_area_struct *insert)
{
	struct mm_struct *mm = vma->vm_mm;
	struct vm_area_struct *next = vma->vm_next;
	struct vm_area_struct *importer = NULL;
	struct address_space *mapping = NULL;
	struct prio_tree_root *root = NULL;
	struct file *file = vma->vm_file;
	struct anon_vma *anon_vma = NULL;
	long adjust_next = 0;
	int remove_next = 0;

	if (next && !insert) {
		/*指定的范围已经跨越了整个后驱vma，并且有可能超过后驱vma*/
		if (end >= next->vm_end) {
			/*
			 * vma expands, overlapping all the next, and
			 * perhaps the one after too (mprotect case 6).
			 */
again:          remove_next = 1 + (end > next->vm_end);//确定是否超过了后驱vma
			end = next->vm_end;
			anon_vma = next->anon_vma;
			importer = vma;
		} else if (end > next->vm_start) {/*指定的区域和后驱vma部分重合*/

			/*
			 * vma expands, overlapping part of the next:
			 * mprotect case 5 shifting the boundary up.
			 */
			adjust_next = (end - next->vm_start) >> PAGE_SHIFT;
			anon_vma = next->anon_vma;
			importer = vma;
		} else if (end < vma->vm_end) {/*指定的区域没到达后驱vma的结束处*/
			/*
			 * vma shrinks, and !insert tells it's not
			 * split_vma inserting another: so it must be
			 * mprotect case 4 shifting the boundary down.
			 */
			adjust_next = - ((vma->vm_end - end) >> PAGE_SHIFT);
			anon_vma = next->anon_vma;
			importer = next;
		}
	}

	if (file) {//如果有映射文件
		mapping = file->f_mapping;//获取文件对应的address_space
		if (!(vma->vm_flags & VM_NONLINEAR))
			root = &mapping->i_mmap;
		spin_lock(&mapping->i_mmap_lock);
		if (importer &&
			vma->vm_truncate_count != next->vm_truncate_count) {
			/*
			 * unmap_mapping_range might be in progress:
			 * ensure that the expanding vma is rescanned.
			 */
			importer->vm_truncate_count = 0;
		}
		/*如果指定了待插入的vma，则根据vma是否以非线性的方式映射文件来选择是将
		vma插入file对应的address_space的优先树(对应线性映射)还是双向链表(非线性映射)*/
		if (insert) {
			insert->vm_truncate_count = vma->vm_truncate_count;
			/*
			 * Put into prio_tree now, so instantiated pages
			 * are visible to arm/parisc __flush_dcache_page
			 * throughout; but we cannot insert into address
			 * space until vma start or end is updated.
			 */
			__vma_link_file(insert);
		}
	}

	/*
	 * When changing only vma->vm_end, we don't really need
	 * anon_vma lock.
	 */
	if (vma->anon_vma && (insert || importer || start != vma->vm_start))
		anon_vma = vma->anon_vma;
	if (anon_vma) {
		spin_lock(&anon_vma->lock);
		/*
		 * Easily overlooked: when mprotect shifts the boundary,
		 * make sure the expanding vma has anon_vma set if the
		 * shrinking vma had, to cover any anon pages imported.
		 */
		if (importer && !importer->anon_vma) {
			importer->anon_vma = anon_vma;
			__anon_vma_link(importer);//将importer插入importer的anon_vma匿名映射链表中
		}
	}

	if (root) {
		flush_dcache_mmap_lock(mapping);
		vma_prio_tree_remove(vma, root);
		if (adjust_next)
			vma_prio_tree_remove(next, root);
	}

	/*调整vma的相关量*/
	vma->vm_start = start;
	vma->vm_end = end;
	vma->vm_pgoff = pgoff;
	if (adjust_next) {//调整后驱vma的相关量
		next->vm_start += adjust_next << PAGE_SHIFT;
		next->vm_pgoff += adjust_next;
	}

	if (root) {
		if (adjust_next)//如果后驱vma被调整了，则重新插入到优先树中
			vma_prio_tree_insert(next, root);
		vma_prio_tree_insert(vma, root);//将vma插入到优先树中
		flush_dcache_mmap_unlock(mapping);
	}

	if (remove_next) {//给定区域与后驱vma有重合
		/*
		 * vma_merge has merged next into vma, and needs
		 * us to remove next before dropping the locks.
		 */
		__vma_unlink(mm, next, vma);//将后驱vma从红黑树中删除
		if (file)//将后驱vma从文件对应的address space中删除
			__remove_shared_vm_struct(next, file, mapping);
		if (next->anon_vma)//将后驱vma从匿名映射链表中删除
			__anon_vma_merge(vma, next);
	} else if (insert) {
		/*
		 * split_vma has split insert from vma, and needs
		 * us to insert it before dropping the locks
		 * (it may either follow vma or precede it).
		 */
		__insert_vm_struct(mm, insert);//将待插入的vma插入mm的红黑树，双向链表以及
						//匿名映射链表
	}

	if (anon_vma)
		spin_unlock(&anon_vma->lock);
	if (mapping)
		spin_unlock(&mapping->i_mmap_lock);

	if (remove_next) {
		if (file) {
			fput(file);
			if (next->vm_flags & VM_EXECUTABLE)
				removed_exe_file_vma(mm);
		}
		mm->map_count--;
		mpol_put(vma_policy(next));
		kmem_cache_free(vm_area_cachep, next);
		/*
		 * In mprotect's case 6 (see comments on vma_merge),
		 * we must remove another next too. It would clutter
		 * up the code too much to do both in one go.
		 */
		if (remove_next == 2) {//还有待删除的区域
			next = vma->vm_next;
			goto again;
		}
	}

	validate_mm(mm);
}

int insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma)
{
	struct vm_area_struct * __vma, * prev;
	struct rb_node ** rb_link, * rb_parent;

	/*
	 * The vm_pgoff of a purely anonymous vma should be irrelevant
	 * until its first write fault, when page's anon_vma and index
	 * are set.  But now set the vm_pgoff it will almost certainly
	 * end up with (unless mremap moves it elsewhere before that
	 * first wfault), so /proc/pid/maps tells a consistent story.
	 *
	 * By setting it to reflect the virtual start address of the
	 * vma, merges and splits can happen in a seamless way, just
	 * using the existing file pgoff checks and manipulations.
	 * Similarly in do_mmap_pgoff and in do_brk.
	 */
	if (!vma->vm_file) {
		BUG_ON(vma->anon_vma);
		vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT;
	}
	/*__vma用来保存和vma->start对应的vma(与find_vma()一样)，同时获取以下信息:
	  1.prev用来保存对应的前驱vma
	  2.rb_link保存该vma区域插入对应的红黑树节点
	  3.rb_parent保存该vma区域对应的父节点*/
	__vma = find_vma_prepare(mm,vma->vm_start,&prev,&rb_link,&rb_parent);
	if (__vma && __vma->vm_start < vma->vm_end)
		return -ENOMEM;
	if ((vma->vm_flags & VM_ACCOUNT) &&
		 security_vm_enough_memory_mm(mm, vma_pages(vma)))
		return -ENOMEM;
	vma_link(mm, vma, prev, rb_link, rb_parent);//将vma关联到所有的数据结构中
	return 0;
}

static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
			struct vm_area_struct *prev, struct rb_node **rb_link,
			struct rb_node *rb_parent)
{
	struct address_space *mapping = NULL;

	if (vma->vm_file)//如果存在文件映射则获取文件对应的地址空间
		mapping = vma->vm_file->f_mapping;

	if (mapping) {
		spin_lock(&mapping->i_mmap_lock);
		vma->vm_truncate_count = mapping->truncate_count;
	}
	anon_vma_lock(vma);

	/*将vma插入到相应的数据结构中--双向链表，红黑树和匿名映射链表*/
	__vma_link(mm, vma, prev, rb_link, rb_parent);
	__vma_link_file(vma);//将vma插入到文件地址空间的相应数据结构中

	anon_vma_unlock(vma);
	if (mapping)
		spin_unlock(&mapping->i_mmap_lock);

	mm->map_count++;
	validate_mm(mm);
}

unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
		unsigned long len, unsigned long pgoff, unsigned long flags)
{
	struct mm_struct *mm = current->mm;
	struct vm_area_struct *vma;
	unsigned long start_addr;

	if (len > TASK_SIZE)
		return -ENOMEM;

	if (flags & MAP_FIXED)
		return addr;

	if (addr) {
		addr = PAGE_ALIGN(addr);//将地址按页对齐
		vma = find_vma(mm, addr);//获取一个vma，该vma可能包含了addr也可能在addr后面并且离addr最近
		/*这里确定是否有一块适合的空闲区域，先要保证addr+len不会
		  超过进程地址空间的最大允许范围，然后如果前面vma获取成功的话则要保证
		  vma位于addr的后面并且addr+len不会延伸到该vma的区域*/
		if (TASK_SIZE - len >= addr &&
			(!vma || addr + len <= vma->vm_start))
			return addr;
	}
	/*前面获取不成功的话则要调整起始地址了，根据情况选择缓存的空闲区域地址
	  或者TASK_UNMAPPED_BASE=TASK_SIZE/3*/
	if (len > mm->cached_hole_size) {
			start_addr = addr = mm->free_area_cache;
	} else {
			start_addr = addr = TASK_UNMAPPED_BASE;
			mm->cached_hole_size = 0;
	}

full_search:
	/*从addr开始遍历用户地址空间*/
	for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
		/* At this point:  (!vma || addr < vma->vm_end). */
		if (TASK_SIZE - len < addr) {//这里判断是否已经遍历到了用户地址空间的末端
			/*
			 * Start a new search - just in case we missed
			 * some holes.
			 */
			 //如果上次不是从TAKS_UNMAPPED_BASE开始遍历的，则尝试从TASK_UNMAPPED_BASE开始遍历
			if (start_addr != TASK_UNMAPPED_BASE) {
				addr = TASK_UNMAPPED_BASE;
					start_addr = addr;
				mm->cached_hole_size = 0;
				goto full_search;
			}
			return -ENOMEM;
		}
		if (!vma || addr + len <= vma->vm_start) {//判断是否有空闲区域
			/*
			 *找到空闲区域的话则记住我们搜索的结束处，以便下次搜索
			 */
			mm->free_area_cache = addr + len;
			return addr;
		}
		/*该空闲区域不符合大小要求，但是如果这个空闲区域大于之前保存的最大值的话
		  则将这个空闲区域保存，这样便于前面确定从哪里开始搜索*/
		if (addr + mm->cached_hole_size < vma->vm_start)
				mm->cached_hole_size = vma->vm_start - addr;
		addr = vma->vm_end;
	}
}