[系统运维]linux内存管理-系统调用brk()

尽管可见度不高，brk也许是最常使用的系统调用了，用户进程通过它向内核申请空间。人们常常并不意识到在调用brk，原因在于很少有人会直接使用系统调用brk向系统申请空间，而总是通过像malloc一类的C语言库函数（或语言成分，如C++中的new）间接地调用brk。如果把malloc想象成零售，brk则是批发。库函数malloc为用户进程（malloc本身就是该进程的一部分）维持一个小仓库，当进程需要使用更多的内存空间时就向小仓库要，小仓库中存量不足时就通过brk向内核批发。

前面讲过，每个进程拥有3GB字节的用户虚存空间。但是，这并不意味着用户进程在这3GB字节的范围里可以任意使用，因为虚存空间最终得映射到某个物理存储空间（内存或磁盘空间），才真正可以使用，而这种映射的建立和管理则由内核处理。所谓向内核申请一块空间，是指请求内核分配一块虚存空间和相应的若干物理页面，并建立起映射关系。由于每个进程的虚存空间都很大（3GB），而实际需要使用的又很小，内核不可能在创建进程时就为整个虚存空间都分配好相应的物理空间并建立映射，而只能是需要用多少才分配多少。

那么，内核怎样管理每个进程的3G字节虚存空间呢？粗略地说，用户程序经过编译、链接形成的映像文件中有一个代码段和一个数据段（包括data段和bss段），其中代码段在下，数据段在上。数据段中包括了所有静态分配的数据空间，包括全局变量和说明为static的局部变量。这些空间是进程所必须的基本要求，所以内核在建立一个进程的运行映象时就分配好些空间，包括虚存地址区间和物理页面，并建立好二者间的映射。除此之外，堆栈空间安置在虚存空间的顶部，运行时由顶向下延伸；代码段和数据段则在底部（注意，不要与X86系统结构中由段寄存器建立的代码段及数据段相混淆）；在运行时并不向上伸展。而从数据段的顶部end_data到堆栈段地址的下沿这个中间区域则是一个巨大的空洞，这就是可以在运行时动态分配的空间。最初，这个动态分配空间是从进程的end_data开始的，这个地址为内核和进程所共知。以后，每次动态分配一块内存，这个编辑就往上推进一段距离，同时内核和进程都要几下当前的边界在哪里。在进程这一边由malloc或类似的库函数管理，而在内核则将当前的边界记录在进程的mm_struct结构中。具体地说，mm_struct结构中有一个成分brk，表示动态分配区当前的底部。当一个进程需要分配内存时，将要求的大小与其当前的动态分配区底部边界相加，所得的就是所要求的的新边界，也就是brk调用时的参数brk。当内核能满足要求时，系统调用brk返回0，此后新旧两个边界之间的虚存地址就都可以使用了。当内核发现无法满足要求（例如物理空间已经分配完），或者发现新的边界已经过于逼近设于顶部额堆栈时，就拒绝分配而返回-1。

系统调用brk在内核中的实现为sys_brk，其代码在mm/mmap.c中，这个函数既可以用来分配空间，即把动态分配区底部的边界往上推；也可以用来释放，即归还空间。因此，它的代码也大致上可以分成两部分。我们先读第一部分：

sys_brk

/*
 *  sys_brk() for the most part doesn't need the global kernel
 *  lock, except when an application is doing something nasty
 *  like trying to un-brk an area that has already been mapped
 *  to a regular file.  in this case, the unmapping will need
 *  to invoke file system routines that need the global lock.
 */
asmlinkage unsigned long sys_brk(unsigned long brk)
{
	unsigned long rlim, retval;
	unsigned long newbrk, oldbrk;
	struct mm_struct *mm = current->mm;

	down(&mm->mmap_sem);

	if (brk < mm->end_code)
		goto out;
	newbrk = PAGE_ALIGN(brk);
	oldbrk = PAGE_ALIGN(mm->brk);
	if (oldbrk == newbrk)
		goto set_brk;

	/* Always allow shrinking brk. */
	if (brk <= mm->brk) {
		if (!do_munmap(mm, newbrk, oldbrk-newbrk))
			goto set_brk;
		goto out;
	}

参数brk表示所要求的新边界，这个边界不能低于代码段的终点，并且必须与页面大小对齐。如果新边界低于老边界，那就不是申请分配空间，而是释放空间，所以通过do_munmap解除一部分区间的映射，这是个重要的函数。其代码如下：

sys_brk=>do_munmap

/* Munmap is split into 2 main parts -- this part which finds
 * what needs doing, and the areas themselves, which do the
 * work.  This now handles partial unmappings.
 * Jeremy Fitzhardine <jeremy@sw.oz.au>
 */
int do_munmap(struct mm_struct *mm, unsigned long addr, size_t len)
{
	struct vm_area_struct *mpnt, *prev, **npp, *free, *extra;

	if ((addr & ~PAGE_MASK) || addr > TASK_SIZE || len > TASK_SIZE-addr)
		return -EINVAL;

	if ((len = PAGE_ALIGN(len)) == 0)
		return -EINVAL;

	/* Check if this memory area is ok - put it on the temporary
	 * list if so..  The checks here are pretty simple --
	 * every area affected in some way (by any overlap) is put
	 * on the list.  If nothing is put on, nothing is affected.
	 */
	mpnt = find_vma_prev(mm, addr, &prev);
	if (!mpnt)
		return 0;
	/* we have  addr < mpnt->vm_end  */

	if (mpnt->vm_start >= addr+len)
		return 0;

	/* If we'll make "hole", check the vm areas limit */
	if ((mpnt->vm_start < addr && mpnt->vm_end > addr+len)
	    && mm->map_count >= MAX_MAP_COUNT)
		return -ENOMEM;

函数find_vma_prev的作用于以前在linux内存管理-几个重要的数据结构和函数博客中读过的find_vma基本相同，它扫描当前进程用户空间的vm_area_struct结构链表或AVL树，试图找到结束地址高于address的第一个区间，如果找到，则函数返回该区间的vm_area_struct结构指针。不同的是，它同时还通过参数prev返回其前一区间结构的指针。等一下我们就将看到为什么需要这个指针。如果返回的指针为0，或者该区间的起始地址也高于addr+len，那就表示想要解除映射的那部分空间原来就没有映射，所以直接返回0,。如果这部分空间落在某个区间的中间，则在解除这部分空间的映射以后会造成一个空洞而使原来的区间一分为二。可是，一个进程可以拥有的虚存区间的数量是有限制的，所以若这个数量达到了上限MAX_MAP_COUNT，就不再允许这样的操作。

sys_brk=>do_munmap

	/*
	 * We may need one additional vma to fix up the mappings ... 
	 * and this is the last chance for an easy error exit.
	 */
	extra = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
	if (!extra)
		return -ENOMEM;

	npp = (prev ? &prev->vm_next : &mm->mmap);
	free = NULL;
	spin_lock(&mm->page_table_lock);
	for ( ; mpnt && mpnt->vm_start < addr+len; mpnt = *npp) {
		*npp = mpnt->vm_next;
		mpnt->vm_next = free;
		free = mpnt;
		if (mm->mmap_avl)
			avl_remove(mpnt, &mm->mmap_avl);
	}
	mm->mmap_cache = NULL;	/* Kill the cache. */
	spin_unlock(&mm->page_table_lock);

由于解除一部分空间的映射有可能使原来的区间一分为二，所以这里先分配好一个空白的vm_area_struct结构extra。另一方面，要解除映射的那部分空间也有可能跨越好几个区间，所以通过一个for循环把所有涉及的区间都转移到一个临时队列free中，如果建立了AVL树，则也要把这些区间的vm_area_struct结构从AVL树中删除。以前讲过，mm_struct结构中的指针mmap_cache指向上一次find_vma操作的对象，因为对虚存区间的操作往往是有连续性的（见find_vma的代码），而现在用户空间的结构有了变化，多半已经打破了这种连续性，所以把它清成0.至此，已经完成了所有的准备，下面就要具体解除映射了。

sys_brk=>do_munmap

	/* Ok - we have the memory areas we should free on the 'free' list,
	 * so release them, and unmap the page range..
	 * If the one of the segments is only being partially unmapped,
	 * it will put new vm_area_struct(s) into the address space.
	 * In that case we have to be careful with VM_DENYWRITE.
	 */
	while ((mpnt = free) != NULL) {
		unsigned long st, end, size;
		struct file *file = NULL;

		free = free->vm_next;

		st = addr < mpnt->vm_start ? mpnt->vm_start : addr;
		end = addr+len;
		end = end > mpnt->vm_end ? mpnt->vm_end : end;
		size = end - st;

		if (mpnt->vm_flags & VM_DENYWRITE &&
		    (st != mpnt->vm_start || end != mpnt->vm_end) &&
		    (file = mpnt->vm_file) != NULL) {
			atomic_dec(&file->f_dentry->d_inode->i_writecount);
		}
		remove_shared_vm_struct(mpnt);
		mm->map_count--;

		flush_cache_range(mm, st, end);
		zap_page_range(mm, st, size);
		flush_tlb_range(mm, st, end);

		/*
		 * Fix the mapping, and free the old area if it wasn't reused.
		 */
		extra = unmap_fixup(mm, mpnt, st, size, extra);
		if (file)
			atomic_inc(&file->f_dentry->d_inode->i_writecount);
	}

	/* Release the extra vma struct if it wasn't used */
	if (extra)
		kmem_cache_free(vm_area_cachep, extra);

	free_pgtables(mm, prev, addr, addr+len);

	return 0;
}

这里通过一个while循环逐个处理所涉及的区间，这些区间的vm_area_struct结构都链接在一个临时的队列free中。在下一篇博客中读者将看到，一个进程可以通过系统调用mmap将一个文件的内容映射到其用户空间的某个区间，然后就像访问内存一样来访问这个问价。但是，如果这个文件同时又被别的进程打开，并通过常规的文件操作访问，则在二者对此文件的两种不同形式的写操作之间要加以互斥。如果要解除映射的只是这样的区间的一部分（735-737行），那就相当于对此区间的写操作，所以要递减该文件的inode结构中的一个计数器i_writecount，以保证互斥，到操作完成以后再予以恢复（751-752行）。同时，还要通过remove_shared_vm_struct看看所处理的区间是否是这样的区间，如果是，就将其vm_area_struct结构从目标文件的inode结构内的i_mapping队列中脱链。

代码中的zap_page_range解除若干连续页面的映射，并且释放所映射的内存页面，或对交换设备上物理页面的引用，这才是我们在这里所主要关心的。其代码如下：

sys_brk=>do_munmap=>zap_page_range

/*
 * remove user pages in a given range.
 */
void zap_page_range(struct mm_struct *mm, unsigned long address, unsigned long size)
{
	pgd_t * dir;
	unsigned long end = address + size;
	int freed = 0;

	dir = pgd_offset(mm, address);

	/*
	 * This is a long-lived spinlock. That's fine.
	 * There's no contention, because the page table
	 * lock only protects against kswapd anyway, and
	 * even if kswapd happened to be looking at this
	 * process we _want_ it to get stuck.
	 */
	if (address >= end)
		BUG();
	spin_lock(&mm->page_table_lock);
	do {
		freed += zap_pmd_range(mm, dir, address, end - address);
		address = (address + PGDIR_SIZE) & PGDIR_MASK;
		dir++;
	} while (address && (address < end));
	spin_unlock(&mm->page_table_lock);
	/*
	 * Update rss for the mm_struct (not necessarily current->mm)
	 * Notice that rss is an unsigned long.
	 */
	if (mm->rss > freed)
		mm->rss -= freed;
	else
		mm->rss = 0;
}

这个函数解除一块虚存区间的页面映射。首先通过pgd_offset在第一层页面目录中找到起始地址所属的目录项，然后通过一个do-while循环从这个目录项开始处理涉及的所有目录项。

/* to find an entry in a page-table-directory. */
#define pgd_index(address) ((address >> PGDIR_SHIFT) & (PTRS_PER_PGD-1))

#define __pgd_offset(address) pgd_index(address)

#define pgd_offset(mm, address) ((mm)->pgd+pgd_index(address))

对于涉及的每一个目录项，通过zap_pmd_range处理第二层的中间目录项。

sys_brk=>do_munmap=>zap_page_range=>zap_pmd_range

static inline int zap_pmd_range(struct mm_struct *mm, pgd_t * dir, unsigned long address, unsigned long size)
{
	pmd_t * pmd;
	unsigned long end;
	int freed;

	if (pgd_none(*dir))
		return 0;
	if (pgd_bad(*dir)) {
		pgd_ERROR(*dir);
		pgd_clear(dir);
		return 0;
	}
	pmd = pmd_offset(dir, address);
	address &= ~PGDIR_MASK;
	end = address + size;
	if (end > PGDIR_SIZE)
		end = PGDIR_SIZE;
	freed = 0;
	do {
		freed += zap_pte_range(mm, pmd, address, end - address);
		address = (address + PMD_SIZE) & PMD_MASK; 
		pmd++;
	} while (address < end);
	return freed;
}

同样，先通过pmd_offset，在第二层目录表中找到起始目录项。对于采用二级映射的i386结构，中间目录表这一层是空的。定义如下：

extern inline pmd_t * pmd_offset(pgd_t * dir, unsigned long address)
{
	return (pmd_t *) dir;
}

可见，pmd_offset把指向第一层目录项的指针原封不动地作为指向中间目录项的指针返回来了，也就是说把第一层目录当成了中建目录。所以，对于二级映射，zap_pmd_range在某种意义上只是把zap_page_range所做的事情重复了一遍。不过，这一次重复调用的是zap_pte_range，处理的是底层的页面映射表了。

sys_brk=>do_munmap=>zap_page_range=>zap_pmd_range=>zap_pte_range

static inline int zap_pte_range(struct mm_struct *mm, pmd_t * pmd, unsigned long address, unsigned long size)
{
	pte_t * pte;
	int freed;

	if (pmd_none(*pmd))
		return 0;
	if (pmd_bad(*pmd)) {
		pmd_ERROR(*pmd);
		pmd_clear(pmd);
		return 0;
	}
	pte = pte_offset(pmd, address);
	address &= ~PMD_MASK;
	if (address + size > PMD_SIZE)
		size = PMD_SIZE - address;
	size >>= PAGE_SHIFT;
	freed = 0;
	for (;;) {
		pte_t page;
		if (!size)
			break;
		page = ptep_get_and_clear(pte);
		pte++;
		size--;
		if (pte_none(page))
			continue;
		freed += free_pte(page);
	}
	return freed;
}

还是先找到在给定页面表中的起始表项，与pte_offset有关的定义如下：

/* Find an entry in the third-level page table.. */
#define __pte_offset(addr)	(((addr) >> PAGE_SHIFT) & (PTRS_PER_PTE - 1))
#define pte_offset(dir, addr)	((pte_t *)pmd_page(*(dir)) + __pte_offset(addr))

然后就是在一个for循环中，对需要解除映射的页面调用ptep_get_and_clear将页面表项清成0：

#define ptep_get_and_clear(xp)	__pte(xchg(&(xp)->pte_low, 0))

最后通过free_pte解除对内存页面以及盘上页面的使用，这个函数的代码在mm/memory.c中：

sys_brk=>do_munmap=>zap_page_range=>zap_pmd_range=>zap_pte_range=>free_pte

/*
 * Return indicates whether a page was freed so caller can adjust rss
 */
static inline int free_pte(pte_t pte)
{
	if (pte_present(pte)) {
		struct page *page = pte_page(pte);
		if ((!VALID_PAGE(page)) || PageReserved(page))
			return 0;
		/* 
		 * free_page() used to be able to clear swap cache
		 * entries.  We may now have to do it manually.  
		 */
		if (pte_dirty(pte) && page->mapping)
			set_page_dirty(page);
		free_page_and_swap_cache(page);
		return 1;
	}
	swap_free(pte_to_swp_entry(pte));
	return 0;
}

如果页面表项表明在解除映射前页面就已不在内存，则当前进程对该内存页面的使用已经解除，所以只需调用swap_free解除对交换设备上的盘上页面的使用。当然，swap_free首先是递减盘上页面的使用计数，只有当这个计数达到0时才真正地释放了这个盘上页面。如果当前进程是这个盘上页面的最后一个用户（或惟一的用户），则该计数递减后为0。反之，则要通过free_page_and_swap_cache解除对盘上页面和内存页面二者的使用。此外，如果页面在最近一次try_to_swap_out以后已被写过，则还要通过set_page_dirty设置该页面page结构中的PG_dirty标志位，并在相应的address_space结构中将其移入dirty_pages队列。函数free_page_and_swap_cache的代码在mm/swap_state.c中：

sys_brk=>do_munmap=>zap_page_range=>zap_pmd_range=>zap_pte_range=>free_pte=>free_page_and_swap_cache

/* 
 * Perform a free_page(), also freeing any swap cache associated with
 * this page if it is the last user of the page. Can not do a lock_page,
 * as we are holding the page_table_lock spinlock.
 */
void free_page_and_swap_cache(struct page *page)
{
	/* 
	 * If we are the only user, then try to free up the swap cache. 
	 */
	if (PageSwapCache(page) && !TryLockPage(page)) {
		if (!is_page_shared(page)) {
			delete_from_swap_cache_nolock(page);
		}
		UnlockPage(page);
	}
	page_cache_release(page);
}

以前讲过，一个由用户空间映射、可换出的内存页面（确切地说是它的page数据结构），同时在三个队列中。一是通过其队列头list链入某个换入、换出队列，即相应address_space结构中的clean_pages、dirty_pages以及locked_pages三个队列之一；二是通过其队列头lru链入某个LRU队列，即active_list、inactive_dirty_list或者某个inactive_clean_list之一；最后就是通过指针next_hash链入一个杂凑队列。当一个页面在某个换入、换出队列中时，其page结构中的PG_swap_cache标志位为1，如果当前进程是这个页面的最后一个用户（或唯一用户），此时便要调用delete_from_swap_cache_nolock将页面从上述队列中脱离出来。

sys_brk=>do_munmap=>zap_page_range=>zap_pmd_range=>zap_pte_range=>free_pte=>free_page_and_swap_cache=>delete_from_swap_cache_nolock

/*
 * This will never put the page into the free list, the caller has
 * a reference on the page.
 */
void delete_from_swap_cache_nolock(struct page *page)
{
	if (!PageLocked(page))
		BUG();

	if (block_flushpage(page, 0))
		lru_cache_del(page);

	spin_lock(&pagecache_lock);
	ClearPageDirty(page);
	__delete_from_swap_cache(page);
	spin_unlock(&pagecache_lock);
	page_cache_release(page);
}

先通过block_flushpage把页面的内容冲刷到块设备上，不过实际上这种冲刷仅在页面来自一个映射到用户空间的文件时才进行，因为对于交换设备上的页面，此时的内容已经没有意义了。完成了冲刷以后，就通过lru_cache_del将页面从其所在的LRU队列中脱离出来。然后，再通过__delete_from_swap_cache，使页面脱离其他两个队列。

sys_brk=>do_munmap=>zap_page_range=>zap_pmd_range=>zap_pte_range=>free_pte=>free_page_and_swap_cache=>delete_from_swap_cache_nolock=>__delete_from_swap_cache

/*
 * This must be called only on pages that have
 * been verified to be in the swap cache.
 */
void __delete_from_swap_cache(struct page *page)
{
	swp_entry_t entry;

	entry.val = page->index;

#ifdef SWAP_CACHE_INFO
	swap_cache_del_total++;
#endif
	remove_from_swap_cache(page);
	swap_free(entry);
}

这里的remove_from_swap_cache将页面的page结构从换入、换出队列和杂凑队列中脱离出来。然后，也是通过swap_free释放盘上页面，回到delete_from_swap_cache_nolock。最后是page_cache_release，即递减page结构中的使用计数。由于当前进程是页面的最后一个用户，并且在解除映射之前页面在内存中（见上面free_pte中的264行），所以页面的使用计数应该是2，这里（119行）调用了一次page_cache_release就变成了1,。再返回到free_page_and_swap_cache中，这里（149行）又调用了一次page_cache_release，这一次就使其变成了0，于是就最终把页面释放，让它回到了空闲页面队列中。

当回到do_munmap中的时候，已经完成了对一个虚存区间的操作。此时，一方面要对虚存区间的vm_area_struct数据结构和进程的mm_struct数据结构作出调整，以反映已经发生的变化，如果整个区间都解除了映射，则要释放原有的vm_area_struct数据结构。这些操作是由unmap_fixup完成的。其代码如下：
sys_brk=>do_munmap=>unmap_fixup

/* Normal function to fix up a mapping
 * This function is the default for when an area has no specific
 * function.  This may be used as part of a more specific routine.
 * This function works out what part of an area is affected and
 * adjusts the mapping information.  Since the actual page
 * manipulation is done in do_mmap(), none need be done here,
 * though it would probably be more appropriate.
 *
 * By the time this function is called, the area struct has been
 * removed from the process mapping list, so it needs to be
 * reinserted if necessary.
 *
 * The 4 main cases are:
 *    Unmapping the whole area
 *    Unmapping from the start of the segment to a point in it
 *    Unmapping from an intermediate point to the end
 *    Unmapping between to intermediate points, making a hole.
 *
 * Case 4 involves the creation of 2 new areas, for each side of
 * the hole.  If possible, we reuse the existing area rather than
 * allocate a new one, and the return indicates whether the old
 * area was reused.
 */
static struct vm_area_struct * unmap_fixup(struct mm_struct *mm, 
	struct vm_area_struct *area, unsigned long addr, size_t len, 
	struct vm_area_struct *extra)
{
	struct vm_area_struct *mpnt;
	unsigned long end = addr + len;

	area->vm_mm->total_vm -= len >> PAGE_SHIFT;
	if (area->vm_flags & VM_LOCKED)
		area->vm_mm->locked_vm -= len >> PAGE_SHIFT;

	/* Unmapping the whole area. */
	if (addr == area->vm_start && end == area->vm_end) {
		if (area->vm_ops && area->vm_ops->close)
			area->vm_ops->close(area);
		if (area->vm_file)
			fput(area->vm_file);
		kmem_cache_free(vm_area_cachep, area);
		return extra;
	}

	/* Work out to one of the ends. */
	if (end == area->vm_end) {
		area->vm_end = addr;
		lock_vma_mappings(area);
		spin_lock(&mm->page_table_lock);
	} else if (addr == area->vm_start) {
		area->vm_pgoff += (end - area->vm_start) >> PAGE_SHIFT;
		area->vm_start = end;
		lock_vma_mappings(area);
		spin_lock(&mm->page_table_lock);
	} else {
	/* Unmapping a hole: area->vm_start < addr <= end < area->vm_end */
		/* Add end mapping -- leave beginning for below */
		mpnt = extra;
		extra = NULL;

		mpnt->vm_mm = area->vm_mm;
		mpnt->vm_start = end;
		mpnt->vm_end = area->vm_end;
		mpnt->vm_page_prot = area->vm_page_prot;
		mpnt->vm_flags = area->vm_flags;
		mpnt->vm_raend = 0;
		mpnt->vm_ops = area->vm_ops;
		mpnt->vm_pgoff = area->vm_pgoff + ((end - area->vm_start) >> PAGE_SHIFT);
		mpnt->vm_file = area->vm_file;
		mpnt->vm_private_data = area->vm_private_data;
		if (mpnt->vm_file)
			get_file(mpnt->vm_file);
		if (mpnt->vm_ops && mpnt->vm_ops->open)
			mpnt->vm_ops->open(mpnt);
		area->vm_end = addr;	/* Truncate area */

		/* Because mpnt->vm_file == area->vm_file this locks
		 * things correctly.
		 */
		lock_vma_mappings(area);
		spin_lock(&mm->page_table_lock);
		__insert_vm_struct(mm, mpnt);
	}

	__insert_vm_struct(mm, area);
	spin_unlock(&mm->page_table_lock);
	unlock_vma_mappings(area);
	return extra;
}

我们把这段代码留给读者。最后，当循环结束之时，由于已经解除了一些页面的映射，有些页面映射表可能整个都已经空白，对于这样的页面表（所占的页面）也要加以释放。这是由free_pgtables完成的。我们把它代码留给读者。

sys_brk=>do_munmap=>free_pgtables

/*
 * Try to free as many page directory entries as we can,
 * without having to work very hard at actually scanning
 * the page tables themselves.
 *
 * Right now we try to free page tables if we have a nice
 * PGDIR-aligned area that got free'd up. We could be more
 * granular if we want to, but this is fast and simple,
 * and covers the bad cases.
 *
 * "prev", if it exists, points to a vma before the one
 * we just free'd - but there's no telling how much before.
 */
static void free_pgtables(struct mm_struct * mm, struct vm_area_struct *prev,
	unsigned long start, unsigned long end)
{
	unsigned long first = start & PGDIR_MASK;
	unsigned long last = end + PGDIR_SIZE - 1;
	unsigned long start_index, end_index;

	if (!prev) {
		prev = mm->mmap;
		if (!prev)
			goto no_mmaps;
		if (prev->vm_end > start) {
			if (last > prev->vm_start)
				last = prev->vm_start;
			goto no_mmaps;
		}
	}
	for (;;) {
		struct vm_area_struct *next = prev->vm_next;

		if (next) {
			if (next->vm_start < start) {
				prev = next;
				continue;
			}
			if (last > next->vm_start)
				last = next->vm_start;
		}
		if (prev->vm_end > first)
			first = prev->vm_end + PGDIR_SIZE - 1;
		break;
	}
no_mmaps:
	/*
	 * If the PGD bits are not consecutive in the virtual address, the
	 * old method of shifting the VA >> by PGDIR_SHIFT doesn't work.
	 */
	start_index = pgd_index(first);
	end_index = pgd_index(last);
	if (end_index > start_index) {
		clear_page_tables(mm, start_index, end_index - start_index);
		flush_tlb_pgtables(mm, first & PGDIR_MASK, last & PGDIR_MASK);
	}
}

回到sys_brk的代码中，我们已经完成了通过sys_brk释放空间的情景分析。

如果新边界高于老边界，就表示要分配空间，这就是sys_brk的后一部分。我们继续往下看：

sys_brk

	/* Check against rlimit.. */
	rlim = current->rlim[RLIMIT_DATA].rlim_cur;
	if (rlim < RLIM_INFINITY && brk - mm->start_data > rlim)
		goto out;

	/* Check against existing mmap mappings. */
	if (find_vma_intersection(mm, oldbrk, newbrk+PAGE_SIZE))
		goto out;

	/* Check if we have enough memory.. */
	if (!vm_enough_memory((newbrk-oldbrk) >> PAGE_SHIFT))
		goto out;

	/* Ok, looks good - let it rip. */
	if (do_brk(oldbrk, newbrk-oldbrk) != oldbrk)
		goto out;
set_brk:
	mm->brk = brk;
out:
	retval = mm->brk;
	up(&mm->mmap_sem);
	return retval;
}

首先检查对进程的资源限制，如果所要求的新边界使数据段的大小超过了对当前进程的限制，就拒绝执行。此外，还要通过find_vma_intersection，检查所要求的那部分空间是否与已经存在的某一区间相冲突，这个inline函数的代码如下：

sys_brk=>find_vma_intersection
?

/* Look up the first VMA which intersects the interval start_addr..end_addr-1,
   NULL if none.  Assume start_addr < end_addr. */
static inline struct vm_area_struct * find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
{
	struct vm_area_struct * vma = find_vma(mm,start_addr);

	if (vma && end_addr <= vma->vm_start)
		vma = NULL;
	return vma;
}

这里的start_addr是老边界，如果find_vma返回一个非0指针，就表示在它之上已经有了一个已经映射区间，因此有冲突的可能。此时新的边界end_addr必须落在这个区间的起点之下，也就是让从start_addr到end_addr这个空间落在空洞中，否则便是有了冲突。在查明了不存在冲突以后，还要通过vm_enough_memory看看系统中是否有足够的空闲内存页面。

sys_brk=>vm_enough_memory

/* Check that a process has enough memory to allocate a
 * new virtual mapping.
 */
int vm_enough_memory(long pages)
{
	/* Stupid algorithm to decide if we have enough memory: while
	 * simple, it hopefully works in most obvious cases.. Easy to
	 * fool it, but this should catch most mistakes.
	 */
	/* 23/11/98 NJC: Somewhat less stupid version of algorithm,
	 * which tries to do "TheRightThing".  Instead of using half of
	 * (buffers+cache), use the minimum values.  Allow an extra 2%
	 * of num_physpages for safety margin.
	 */

	long free;
	
        /* Sometimes we want to use more memory than we have. */
	if (sysctl_overcommit_memory)
	    return 1;

	free = atomic_read(&buffermem_pages);
	free += atomic_read(&page_cache_size);
	free += nr_free_pages();
	free += nr_swap_pages;
	return free > pages;
}

通过了这些检查，接着就是操作的主体do_brk了。这个函数的代码在mm/mmap.c中：

sys_brk=>do_brk

/*
 *  this is really a simplified "do_mmap".  it only handles
 *  anonymous maps.  eventually we may be able to do some
 *  brk-specific accounting here.
 */
unsigned long do_brk(unsigned long addr, unsigned long len)
{
	struct mm_struct * mm = current->mm;
	struct vm_area_struct * vma;
	unsigned long flags, retval;

	len = PAGE_ALIGN(len);
	if (!len)
		return addr;

	/*
	 * mlock MCL_FUTURE?
	 */
	if (mm->def_flags & VM_LOCKED) {
		unsigned long locked = mm->locked_vm << PAGE_SHIFT;
		locked += len;
		if (locked > current->rlim[RLIMIT_MEMLOCK].rlim_cur)
			return -EAGAIN;
	}

	/*
	 * Clear old maps.  this also does some error checking for us
	 */
	retval = do_munmap(mm, addr, len);
	if (retval != 0)
		return retval;

	/* Check against address space limits *after* clearing old maps... */
	if ((mm->total_vm << PAGE_SHIFT) + len
	    > current->rlim[RLIMIT_AS].rlim_cur)
		return -ENOMEM;

	if (mm->map_count > MAX_MAP_COUNT)
		return -ENOMEM;

	if (!vm_enough_memory(len >> PAGE_SHIFT))
		return -ENOMEM;

	flags = vm_flags(PROT_READ|PROT_WRITE|PROT_EXEC,
				MAP_FIXED|MAP_PRIVATE) | mm->def_flags;

	flags |= VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
	

	/* Can we just expand an old anonymous mapping? */
	if (addr) {
		struct vm_area_struct * vma = find_vma(mm, addr-1);
		if (vma && vma->vm_end == addr && !vma->vm_file && 
		    vma->vm_flags == flags) {
			vma->vm_end = addr + len;
			goto out;
		}
	}	


	/*
	 * create a vma struct for an anonymous mapping
	 */
	vma = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
	if (!vma)
		return -ENOMEM;

	vma->vm_mm = mm;
	vma->vm_start = addr;
	vma->vm_end = addr + len;
	vma->vm_flags = flags;
	vma->vm_page_prot = protection_map[flags & 0x0f];
	vma->vm_ops = NULL;
	vma->vm_pgoff = 0;
	vma->vm_file = NULL;
	vma->vm_private_data = NULL;

	insert_vm_struct(mm, vma);

out:
	mm->total_vm += len >> PAGE_SHIFT;
	if (flags & VM_LOCKED) {
		mm->locked_vm += len >> PAGE_SHIFT;
		make_pages_present(addr, addr + len);
	}
	return addr;
}

参数addr为需要建立映射的新区建的起点，len则为区间的长度。前面我们已经看到find_vma_intersection对冲突的检查，可是不知读者是否注意到，实际上检查的只是新区间的高端，对于其低端的冲突则并未检查。例如，老的边界是否恰好是一个已映射区间的终点呢？如果不是，那就说明在低端有了冲突。不过，对于低端的冲突是允许的，解决的方法是以新的映射为准，先通过do_munmap把原有的映射解除（见803行），再来建立新的映射，读者大概要问了，为什么对新区建的高端和低端有如此不同的容忍程度和对待呢？读者最好先想一想，然后再往下看。

以前说过，用户空间的顶端是进程的用户空间堆栈。不管什么进程，在那里总是有一个已映射区间存在着的，所以find_vma_intersection中的find_vma其实不会返回0，因为至少用于堆栈的那个区间总是存在的。当然，在堆栈以下也可能还有通过mmap或ioremap建立的映射区间。所以，如果新区间的高端有冲突，那就可能是与堆栈的冲突，而低端的冲突则只能是与数据段的冲突。所以，对于低端可以让进城自己对可能的错误负责，而对于堆栈可就不能采取把原有的映射解除，另行建立新的映射这样的方法了。

建立新的映射时，先看看是否可以跟原有的区间合并，即通过扩展原有区间来覆盖新增的区间（826-831行）。如果不行就得另行建立一个区间（838-852行）。

最后，通过make_pages_present，为新增的区间建立起对内存页面的映射。其代码如下：

sys_brk=>do_brk=>make_pages_present

/*
 * Simplistic page force-in..
 */
int make_pages_present(unsigned long addr, unsigned long end)
{
	int write;
	struct mm_struct *mm = current->mm;
	struct vm_area_struct * vma;

	vma = find_vma(mm, addr);
	write = (vma->vm_flags & VM_WRITE) != 0;
	if (addr >= end)
		BUG();
	do {
		if (handle_mm_fault(mm, vma, addr, write) < 0)
			return -1;
		addr += PAGE_SIZE;
	} while (addr < end);
	return 0;
}

这里所用的方法很有趣，那就是对新区建中的每一个页面模拟一次缺页异常。读者不妨想想，当从do_brk返回，进而从sys_brk返回之时，这些页面表项的映射时怎样的？如果进程从新分配的区间中读，读出的内容该是什么？往里面写，情况又会怎样？