Archive for the ‘内存管理’ category

malloc()之后,内核发生了什么?

2 9 月, 2012

考虑这样一种常见的情况:用户进程调用malloc()动态分配了一块内存空间,再对这块内存进行访问。这些用户空间发生的事会引发内核空间的那些反映?本文将简单为您解答。

1.brk系统调用服务例程

malloc()是一个API,这个函数在库中封装了系统调用brk。因此如果调用malloc,那么首先会引发brk系统调用执行的过程。brk()在内核中对应的系统调用服务例程为SYSCALL_DEFINE1(brk, unsigned long, brk),参数brk用来指定heap段新的结束地址,也就是重新指定mm_struct结构中的brk字段。

brk系统调用服务例程首先会确定heap段的起始地址min_brk,然后再检查资源的限制问题。接着,将新老heap地址分别按照页大小对齐,对齐后的地址分别存储与newbrk和okdbrk中。

brk()系统调用本身既可以缩小堆大小,又可以扩大堆大小。缩小堆这个功能是通过调用do_munmap()完成的。如果要扩大堆的大小,那么必须先通过find_vma_intersection()检查扩大以后的堆是否与已经存在的某个虚拟内存重合,如何重合则直接退出。否则,调用do_brk()进行接下来扩大堆的各种工作。

SYSCALL_DEFINE1(brk, unsigned long, brk)
{
        unsigned long rlim, retval;
        unsigned long newbrk, oldbrk;
        struct mm_struct *mm = current->mm;
        unsigned long min_brk;

        down_write(&mm->mmap_sem);

#ifdef CONFIG_COMPAT_BRK
        min_brk = mm->end_code;
#else
        min_brk = mm->start_brk;
#endif
        if (brk < min_brk)
                goto out;

        rlim = rlimit(RLIMIT_DATA);
        if (rlim < RLIM_INFINITY && (brk - mm->start_brk) +
                        (mm->end_data - mm->start_data) > rlim)

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

        if (brk brk) {
                if (!do_munmap(mm, newbrk, oldbrk-newbrk))
                        goto set_brk;
                goto out;
        }

        if (find_vma_intersection(mm, oldbrk, newbrk+PAGE_SIZE))
                goto out;

        if (do_brk(oldbrk, newbrk-oldbrk) != oldbrk)
                goto out;
set_brk:
        mm->brk = brk;
out:
        retval = mm->brk;
        up_write(&mm->mmap_sem);
        return retval;
}

brk系统调用服务例程最后将返回堆的新结束地址。

2.扩大堆

用户进程调用malloc()会使得内核调用brk系统调用服务例程,因为malloc总是动态的分配内存空间,因此该服务例程此时会进入第二条执行路径中,即扩大堆。do_brk()主要完成以下工作:

1.通过get_unmapped_area()在当前进程的地址空间中查找一个符合len大小的线性区间,并且该线性区间的必须在addr地址之后。如果找到了这个空闲的线性区间,则返回该区间的起始地址,否则返回错误代码-ENOMEM;

2.通过find_vma_prepare()在当前进程所有线性区组成的红黑树中依次遍历每个vma,以确定上一步找到的新区间之前的线性区对象的位置。如果addr位于某个现存的vma中,则调用do_munmap()删除这个线性区。如果删除成功则继续查找,否则返回错误代码。

3.目前已经找到了一个合适大小的空闲线性区,接下来通过vma_merge()去试着将当前的线性区与临近的线性区进行合并。如果合并成功,那么该函数将返回prev这个线性区的vm_area_struct结构指针,同时结束do_brk()。否则,继续分配新的线性区。

4.接下来通过kmem_cache_zalloc()在特定的slab高速缓存vm_area_cachep中为这个线性区分配vm_area_struct结构的描述符。

5.初始化vma结构中的各个字段。

6.更新mm_struct结构中的vm_total字段,它用来同级当前进程所拥有的vma数量。

7.如果当前vma设置了VM_LOCKED字段,那么通过mlock_vma_pages_range()立即为这个线性区分配物理页框。否则,do_brk()结束。

可以看到,do_brk()主要是为当前进程分配一个新的线性区,在没有设置VM_LOCKED标志的情况下,它不会立刻为该线性区分配物理页框,而是通过vma一直将分配物理内存的工作进行延迟,直至发生缺页异常。

3.缺页异常的处理过程

经过上面的过程,malloc()返回了线性地址,如果此时用户进程访问这个线性地址,那么就会发生缺页异常(Page Fault)。整个缺页异常的处理过程非常复杂,我们这里只关注与malloc()有关的那一条执行路径。

当CPU产生一个异常时,将会跳转到异常处理的整个处理流程中。对于缺页异常,CPU将跳转到page_fault异常处理程序中:

//linux-2.6.34/arch/x86/kernel/entry_32.S
ENTRY(page_fault)
        RING0_EC_FRAME
        pushl $do_page_fault
        CFI_ADJUST_CFA_OFFSET 4
        ALIGN
error_code:
        …………
        jmp ret_from_exception
        CFI_ENDPROC
END(page_fault)

该异常处理程序会调用do_page_fault()函数,该函数通过读取CR2寄存器获得引起缺页的线性地址,通过各种条件判断以便确定一个合适的方案来处理这个异常。

3.1.do_page_fault()

该函数通过各种条件来检测当前发生异常的情况,但至少do_page_fault()会区分出引发缺页的两种情况:由编程错误引发异常,以及由进程地址空间中还未分配物理内存的线性地址引发。对于后一种情况,通常还分为用户空间所引发的缺页异常和内核空间引发的缺页异常。

内核引发的异常是由vmalloc()产生的,它只用于内核空间内存的分配。显然,我们这里需要关注的是用户空间所引发的异常情况。这部分工作从do_page_fault()中的good_area标号处开始执行,主要通过handle_mm_fault()完成。

//linux-2.6.34/arch/x86/mm/fault.c
dotraplinkage void __kprobes
do_page_fault(struct pt_regs *regs, unsigned long error_code)
{
…… ……
good_area:
        write = error_code & PF_WRITE;

        if (unlikely(access_error(error_code, write, vma))) {
                bad_area_access_error(regs, error_code, address);
                return;
        }
        fault = handle_mm_fault(mm, vma, address, write ? FAULT_FLAG_WRITE : 0);
…… ……
}

3.2.handle_mm_fault()

该函数的主要功能是为引发缺页的进程分配一个物理页框,它先确定与引发缺页的线性地址对应的各级页目录项是否存在,如何不存在则分进行分配。具体如何分配这个页框是通过调用handle_pte_fault()完成的。

int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct *vma,
                unsigned long address, unsigned int flags)
{
        pgd_t *pgd;
        pud_t *pud;
        pmd_t *pmd;
        pte_t *pte;
        …… ……
        pgd = pgd_offset(mm, address);
        pud = pud_alloc(mm, pgd, address);
        if (!pud)
                return VM_FAULT_OOM;
        pmd = pmd_alloc(mm, pud, address);
        if (!pmd)
                return VM_FAULT_OOM;
        pte = pte_alloc_map(mm, pmd, address);
        if (!pte)
                return VM_FAULT_OOM;
          return handle_pte_fault(mm, vma, address, pte, pmd, flags);
}

3.3.handle_pte_fault()

该函数根据页表项pte所描述的物理页框是否在物理内存中,分为两大类:

请求调页:被访问的页框不再主存中,那么此时必须分配一个页框。

写时复制:被访问的页存在,但是该页是只读的,内核需要对该页进行写操作,此时内核将这个已存在的只读页中的数据复制到一个新的页框中。

用户进程访问由malloc()分配的内存空间属于第一种情况。对于请求调页,handle_pte_fault()仍然将其细分为三种情况:

static inline int handle_pte_fault(struct mm_struct *mm,
                struct vm_area_struct *vma, unsigned long address,
                pte_t *pte, pmd_t *pmd, unsigned int flags)
{
        …… ……
        if (!pte_present(entry)) {
                if (pte_none(entry)) {
                        if (vma->vm_ops) {
                                if (likely(vma->vm_ops->fault))
                                        return do_linear_fault(mm, vma, address,
                                                pte, pmd, flags, entry);
                        }
                        return do_anonymous_page(mm, vma, address,
                                                 pte, pmd, flags);
                }
                if (pte_file(entry))
                        return do_nonlinear_fault(mm, vma, address,
                                        pte, pmd, flags, entry);
                return do_swap_page(mm, vma, address,
                                        pte, pmd, flags, entry);
        }
…… ……
}

1.如果页表项确实为空(pte_none(entry)),那么必须分配页框。如果当前进程实现了vma操作函数集合中的fault钩子函数,那么这种情况属于基于文件的内存映射,它调用do_linear_fault()进行分配物理页框。否则,内核将调用针对匿名映射分配物理页框的函数do_anonymous_page()。

2.如果检测出该页表项为非线性映射(pte_file(entry)),则调用do_nonlinear_fault()分配物理页。

3.如果页框事先被分配,但是此刻已经由主存换出到了外存,则调用do_swap_page()完成页框分配。

由malloc分配的内存将会调用do_anonymous_page()分配物理页框。

3.4.do_anonymous_page()

此时,缺页异常处理程序终于要为当前进程分配物理页框了。它通过alloc_zeroed_user_highpage_movable()来完成这个过程。我们层层拨开这个函数的外衣,发现它最终调用了alloc_pages()。

static int do_anonymous_page(struct mm_struct *mm, struct vm_area_struct *vma,
                unsigned long address, pte_t *page_table, pmd_t *pmd,
                unsigned int flags)
{
…… ……
        if (unlikely(anon_vma_prepare(vma)))
                goto oom;
        page = alloc_zeroed_user_highpage_movable(vma, address);
        if (!page)
                goto oom;
…… ……
}

经过这样一个复杂的过程,用户进程所访问的线性地址终于对应到了一块物理内存。

参考:

1.《深入理解LINUX内核》

2.《深入LINUX内核架构》

Linux内存管理实践-使用fault()实现内存映射

15 5 月, 2012

内核态与用户态进行数据交互通常是这样一种模型:内核利用自身的特权通过特定的服务程序采集、接收和处理数据;接着,用户态程序和内核服务程序进行数据交互,或接收内核态的数据,或向内核态写入数据。通过传统的那些对文件操作的系统调用就可以完成这样的工作,但是我们有时候需要通过访问用户空间的内存来直接读取内核数据,因为这样可以免去数据在内核态与用户态之间拷贝所花费的时间。

本文基于以上背景,以Linux字符设备驱动为基础,通过内存映射将内核中的一部分虚拟内存直接映射到用户空间,使得用户在访问内存时等同于直接访问内核空间,从而直接获取内核空间的数据。

1.实现原理

不管进程是在用户空间访问数据还是在内核空间访问数据,它所面临的都是虚拟地址。由于Linux对分段机制进行了特殊处理,因此这里的虚拟地址就等同于线性地址。按照一开始我们提出的要求,进程通过访问用户虚拟地址A来达到直接访问内核虚拟地址B中所存储数据的目的,这里的地址A和B必然不相同。那么,如何通过不同的虚拟地址来访问相同的数据?我们可以将虚拟地址A和B都映射到同一块物理内存,就可以实现内核空间和用户空间之间的数据共享。

示意图如下:

虚拟内存和物理内存之间如何联系?当然是通过页表了。我们在内核空间提前分配好缓冲区,并且向该缓冲区写入数据,此时内核会自动将该缓冲区对应的内核虚拟地址与实际的某一快物理内存进行关联,并将它们的映射关系保存在内核页表中。当在内核空间分配内存时时,上述工作自动被完成,比如通过kmalloc()分配内存时。

一旦在内核空间中分配了内存,随之就确定了物理内存。现在我们需要做的是将用户虚拟地址与物理内存进行关联,也就是说我们要将这个映射关系写入进程的用户页表。整个关联的过程是内核缺页异常处理程序完成的,这个处理过程比较复杂。我们要在内核中实现的并不是缺页异常处理程序,因为内核已经实现的很完美,而只需完成其中的一小部门。具体如何实现下问会详细说明。

2.用户态程序的实现

在本文所描述的内存管理试验,用户态程序首先通过open()打开字符设备文件mapdrv,该系统调用执行成功时返回文件描述符;通过mmap()将该设备文件映射到当前进程的用户空间中,该系统调用执行成功时返回指向映射区域的指针;最后通过该指针打印数据。用户态程序的实现如下所示:

#define LEN (10 * 4096)

int main(void)
{
	int fd, ret = 0;
	char *vadr;
	int i;

	if ((fd = open("/dev/mapdrv_k", O_RDWR)) < 0) {
		perror("open");
		ret = -1;
		goto fail;
	}
	vadr = mmap(0, LEN, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0);

	if (vadr == MAP_FAILED) {
		perror("mmap");
		ret = -1;
		goto fail_close;
	}

	printf("%s\n", vadr);

	if (-1 == munmap(vadr, LEN))
		ret = -1;
fail_close:
	close(fd);
fail:
	exit(ret);
}

用户态程序的实现并不复杂,因为它的主要作用是对内核模块程序的测试。由于用户态程序是对特定的字符设备文件mapdrv进行操作,所以程序中所使用的系统调用将会调用file_operations结构中对应的钩子函数。比如mmap系统调用在执行时会调用mapdrv设备驱动中的mmap钩子函数,虽然两者同名,但是mmap钩子函数所实现的功能只是mmap系统调用执行过程中的一部门,该钩子函数是file_operations结构中的成员。两者的函数原型如下:

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int (*mmap) (struct file *, struct vm_area_struct *);

如何实例化open和mmap等钩子函数便是整个内核模块程序实现的关键。

3.字符设备驱动程序的实现

整个内核模块程序是以字符设备驱动为基础进行实现的。该程序模块加载函数与一般字符设备驱动程序完成的工作一致:

1.申请设备号;

2.为描述字符设备的数据结构分配空间,并进行初始化;

3.将该字符设备注册到内核中;

在本文所描述的实验中,模块加载函数除了完成上述功能,还要完成以下功能:

	kmalloc_area = kmalloc(MAPLEN, GFP_KERNEL);
	if (!kmalloc_area)
		goto fail4;

	for (page = virt_to_page(kmalloc_area);
			page < virt_to_page(kmalloc_area + MAPLEN); page++) {
		SetPageReserved(page);
	}

首先,通过kmalloc()分配一块内存用于在内核空间保存数据;通过SetPageReserved()将缓存数据的页面常驻内存,防止被换出到磁盘;将一段字符串拷贝到这片内存中。完成初始化函数后,字符设备驱动中最重要的就是实现file_operations结构中的钩子函数。在本文所述的实验中,我们只需实现三个钩子函数。

static struct file_operations mapdrv_fops = {
	.owner = THIS_MODULE,
	.mmap = mapdrv_mmap,
	.open = mapdrv_open,
	.release = mapdrv_release,
};

int mapdrv_open(struct inode *inode, struct file *file)
{
	struct mapdrv *md;

	printk("device is opened..\n");
	md = container_of(inode->i_cdev, struct mapdrv, mapdev);
	atomic_inc(&md->usage);
	return 0;
}

int mapdrv_release(struct inode *inode, struct file *file)
{
        struct mapdrv* md;

        printk("device is closed..\n");
        md = container_of(inode->i_cdev, struct mapdrv, mapdev);
        atomic_dec(&md->usage);
        return 0;
}

可以看到,open和release钩子函数的实现十分简单,只是打印相应语句以及更新设备的引用计数。事实上,我们不实现这两个钩子函数对整个驱动程序也没有任何影响。因为他们分别在open和close系统调用执行的过程中被调用,而这两个系统调用已经完成了打开文件和关闭文件的所有工作。因此,open和release钩子函数只是打印一些日志信息,方便用户查看。因此,同名的钩子函数和系统调用并不是等价的关系。

4.通过fault()实现内存映射

mmap系统调用是将本地文件映射到进程的用户空间,如果执行成功,进程的地址空间中会新增一块虚拟内存区域(但并不是每次调用mmap()都会增加一个vma,因为可能会出现内存区域之间的合并)

mmap钩子函数的回调只是整个系统调用执行过程中的一部分,这个钩子函数完成的主要功能是将新增的vma中的操作集进行实例化。具体实现代码如下:

int mapdrv_mmap(struct file *file, struct vm_area_struct *vma)
{
	unsigned long offset = vma->vm_pgoff << PAGE_SHIFT;

	unsigned long size = vma->vm_end - vma->vm_start;
	if (offset & ~PAGE_MASK) {
		printk("offset not aligned: %ld\n", offset);
		return -ENXIO;
	}
	if (size > MAPLEN) {
		printk("size too big\n");
		return -ENXIO;
	}

	if ((vma->vm_flags & VM_WRITE) && !(vma->vm_flags & VM_SHARED)) {
		printk("writeable mappings must be shared, rejecting\n");
		return -EINVAL;
	}

	vma->vm_flags |= VM_LOCKED;
	if (offset == 0) {
		vma->vm_ops = &map_vm_ops;
		map_vopen(vma);
	} else {
		printk("offset out of range\n");
		return -ENXIO;
	}
	return 0;
}

首先,offset中保存映射的首页在文件中的偏移量,该偏移量必须是页大小的整数倍,否则将不能进行映射。这一点在实现上将offset与PAGE_MASK宏进行位运算即可判断。接着,判断映射区域的长度是否超出了本实验中预设的长度大小。

如果上述两个条件都合法,那么接下来将进行最为重要的操作,将vma中的操作集进行实例化。vma的操作集就是专门对所属vma进行操作的钩子函数集合,内核中通过vm_operations_struct结构对其描述:

struct vm_operations_struct {
        void (*open)(struct vm_area_struct * area);
        void (*close)(struct vm_area_struct * area);
        int (*fault)(struct vm_area_struct *vma, struct vm_fault *vmf);
        ……
}

参考上述代码,具体的实例化操作就是定义该类型的变量map_vm_ops,实现所需钩子函数,并将该变量与vm中的操作集字段进行挂接。

我们这里用到的主要有以下三个钩子函数:

open:当指定的vma加入到一个地址空间时,该函数被调用。

close:当指定的vma从地址空间删除时,该函数被调用。

fault:当要访问的页不再物理内存时,该函数被缺页处理程序调用。

这三个钩子函数的实现代码如下:

static struct vm_operations_struct map_vm_ops = {
	.open = map_vopen,
	.close = map_vclose,
	.fault = map_fault,
};

void map_vopen(struct vm_area_struct *vma)
{
	printk("mapping vma is opened..\n");
}

void map_vclose(struct vm_area_struct *vma)
{
	printk("mapping vma is closed..\n");
}

可以看到,vma的open和close两个钩子函数没有做什么具体工作,因为打开和关闭一个vma的工作全部由内核负责,但是在mmap钩子函数中我们必须显示的调用map_open()。

这里我们重点说明falut钩子函数的实现。当用户要访问vma中的页,而该页又不在内存时,将发生缺页异常,fault钩子函数会在整个缺页处理程序中被调用。整个过程大致如下:

1.找到缺页地址所在的vma。

2.如果有必要分配各级页表项。

3.如果页表项对应的物理页面不存在,则回调当前vma中的fault钩子函数,它返回物理页面描述符。

4.将物理页面地址填充到相应页表项中。

5.完毕。

可以看到,fault钩子函数所实现的主要功能就是返回所需的物理内存描述符。

根据本文第一部分所描述实现原理,我们通过kmalloc()分配一块虚拟内存,可以通过virt_to_page()获得该虚拟内存对应的物理页框描述符,最后将该物理页框描述符返回到缺页异常处理程序中。至于用户页表的更新,那是缺页异常处理程序负责的事情,我们不必理会。

int map_fault(struct vm_area_struct *vma, struct vm_fault *vmf)
{
	struct page *page = virt_to_page(kmalloc_area);

	get_page(page);
	vmf->page = page;
	printk("the requiring page is returned..\n");

	return 0;
}

通过上述实现过程,我们就将用户虚拟地址A和内核虚拟地址B映射到了同一的物理内存上,从而实现进程访问用户地址时直接获得内核数据的功能。

本实验涉及的知识点比较多,比如字符设备驱动程序的基本模型,Linux内存管理等相关知识。感兴趣的童鞋可以参考:

1.内核之旅网站,http://www.kerneltravel.net/journal/v/mem.htm

2.Linux设备驱动程序,第十五章

 

Linux物理内存管理概述

10 4 月, 2012

在内核态申请内存比在用户态申请内存要更为直接,它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存,那么就必须立刻满足该申请内存的请求,并且这个请求一定是正确合理的。相反,对于用户态申请内存的请求,内核总是尽量延后分配物理内存,用户进程总是先获得一个虚拟内存区的使用权,最终通过缺页异常获得一块真正的物理内存。

1.物理内存的内核映射

IA32架构中内核虚拟地址空间只有1GB大小(从3GB到4GB),因此可以直接将1GB大小的物理内存(即常规内存)映射到内核地址空间,但超出1GB大小的物理内存(即高端内存)就不能映射到内核空间。为此,内核采取了下面的方法使得内核可以使用所有的物理内存。

1.高端内存不能全部映射到内核空间,也就是说这些物理内存没有对应的线性地址。不过,内核为每个物理页框都分配了对应的页框描述符,所有的页框描述符都保存在mem_map数组中,因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存,因为这些函数返回页框描述符的线性地址。

2.内核地址空间的后128MB专门用于映射高端内存,否则,没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的,否则也只能映射128MB的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射,使用完毕之后再用来进行其他高端内存的映射。

由于要进行高端内存的内核映射,因此直接能够映射的物理内存大小只有896MB,该值保存在high_memory中。内核地址空间的线性地址区间如下图所示:

从图中可以看出,内核采用了三种机制将高端内存映射到内核空间:永久内核映射,固定映射和vmalloc机制。

2.物理内存管理机制

基于物理内存在内核空间中的映射原理,物理内存的管理方式也有所不同。内核中物理内存的管理机制主要有伙伴算法,slab高速缓存和vmalloc机制。其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存,而vmalloc机制则在高端内存映射区分配物理内存。

伙伴算法

伙伴算法负责大块连续物理内存的分配和释放,以页框为基本单位。该机制可以避免外部碎片。

per-CPU页框高速缓存

内核经常请求和释放单个页框,该缓存包含预先分配的页框,用于满足本地CPU发出的单一页框请求。

slab缓存

slab缓存负责小块物理内存的分配,并且它也作为高速缓存,主要针对内核中经常分配并释放的对象。

vmalloc机制

vmalloc机制使得内核通过连续的线性地址来访问非连续的物理页框,这样可以最大限度的使用高端物理内存。

3.物理内存的分配

内核发出内存申请的请求时,根据内核函数调用接口将启用不同的内存分配器。

3.1 分区页框分配器

分区页框分配器 (zoned page frame allocator) ,处理对连续页框的内存分配请求。分区页框管理器分为两大部分:前端的管理区分配器和伙伴系统,如下图:

管理区分配器负责搜索一个能满足请求页框块大小的管理区。在每个管理区中,具体的页框分配工作由伙伴系统负责。为了达到更好的系统性能,单个页框的申请工作直接通过per-CPU页框高速缓存完成。

该分配器通过几个函数和宏来请求页框,它们之间的封装关系如下图所示。

这些函数和宏将核心的分配函数__alloc_pages_nodemask()封装,形成满足不同分配需求的分配函数。其中,alloc_pages()系列函数返回物理内存首页框描述符,__get_free_pages()系列函数返回内存的线性地址。

3.2 slab分配器

slab 分配器最初是为了解决物理内存的内部碎片而提出的,它将内核中常用的数据结构看做对象。slab分配器为每一种对象建立高速缓存。内核对该对象的分配和释放均是在这块高速缓存中操作。一种对象的slab分配器结构图如下:

可以看到每种对象的高速缓存是由若干个slab组成,每个slab是由若干个页框组成的。虽然slab分配器可以分配比单个页框更小的内存块,但它所需的所有内存都是通过伙伴算法分配的。

slab高速缓存分专用缓存和通用缓存。专用缓存是对特定的对象,比如为内存描述符创建高速缓存。通用缓存则是针对一般情况,适合分配任意大小的物理内存,其接口即为kmalloc()。

3.3 非连续内存区内存的分配

内核通过vmalloc()来申请非连续的物理内存,若申请成功,该函数返回连续内存区的起始地址,否则,返回NULL。vmalloc()和kmalloc()申请的内存有所不同,kmalloc()所申请内存的线性地址与物理地址都是连续的,而vmalloc()所申请的内存线性地址连续而物理地址则是离散的,两个地址之间通过内核页表进行映射。

vmalloc()的工作方式理解起来很简单:

1.寻找一个新的连续线性地址空间;

2.依次分配一组非连续的页框;

3.为线性地址空间和非连续页框建立映射关系,即修改内核页表;

vmalloc()的内存分配原理与用户态的内存分配相似,都是通过连续的虚拟内存来访问离散的物理内存,并且虚拟地址和物理地址之间是通过页表进行连接的,通过这种方式可以有效的使用物理内存。但是应该注意的是,vmalloc()申请物理内存时是立即分配的,因为内核认为这种内存分配请求是正当而且紧急的;相反,用户态有内存请求时,内核总是尽可能的延后,毕竟用户态跟内核态不在一个特权级。

后记:本文将Linux内核中物理内存管理这部分内容进行框架性总结,对内存管理感兴趣的同学可以从伙伴算法,slab和vmalloc()三个角度去了解和学习物理内存管理。

伙伴算法的实现-释放页框

12 3 月, 2012

与页框分配函数的整个实现过程相比,页框释放函数的实现要简单的多。常用的页框分配函数接口有 __free_pages()和__free_page(),很明显后者是前者的特殊情况。

#define __free_page(page) __free_pages((page), 0)

void __free_pages(struct page *page, unsigned int order)
{
        if (put_page_testzero(page)) {
                if (order == 0)
                        free_hot_cold_page(page, 0);
                else
                        __free_pages_ok(page, order);
        }
}

释放页框函数在一开始也兵分两路:如果分配阶为0,那么直接通过per-CPU机制来释放单一页框;否则通过__free_pages_ok()释放所申请的页框块。

1.__free_pages_ok()

该函数内部经过一些检查,这些检查是确保稍候对页框的释放是安全的,最终会调用free_one_page(),而它内部又封装了__free_one_page()。内核中函数之间的这种多次封装是很常见的,上层函数通过这种封装可以屏蔽某些参数,而底层的被封装的函数也可以被多种情况所引用。

static void __free_pages_ok(struct page *page, unsigned int order)
{
        …………
        free_one_page(page_zone(page), page, order, get_pageblock_migratetype(page));
        …………
}

static void free_one_page(struct zone *zone, struct page *page, int order,int migratetype)
{
        spin_lock(&zone->lock);
        zone->all_unreclaimable = 0;
        zone->pages_scanned = 0;

        __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
        __free_one_page(page, zone, order, migratetype);
        spin_unlock(&zone->lock);
}

在调用核心函数__free_one_page()之前,还需更新当前内存管理区的空闲页面数,其实就是将(1<vm_stat[NR_FREE_PAGES]上,其中vm_stat是一个对内存区进行信息统计的数组。

2.__free_one_page()

该函数按照伙伴算法的回收原理实现,从所请求的分配阶order开始,为当前页框块尽可能的寻找伙伴,进而合并成更大的页框块。在进入循环之前,先得到释放页框块的索引page_idx。

static inline void __free_one_page(struct page *page,
                struct zone *zone, unsigned int order,
                int migratetype)
{
        unsigned long page_idx;

        if (unlikely(PageCompound(page)))
                if (unlikely(destroy_compound_page(page, order)))
                        return;

        VM_BUG_ON(migratetype == -1);

        page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

        VM_BUG_ON(page_idx & ((1 << order) - 1));
        VM_BUG_ON(bad_range(zone, page));

        while (order < MAX_ORDER-1) {
                unsigned long combined_idx;
                struct page *buddy;

                buddy = __page_find_buddy(page, page_idx, order);
                if (!page_is_buddy(page, buddy, order))
                        break;

                list_del(&buddy->lru);
                zone->free_area[order].nr_free--;
                rmv_page_order(buddy);
                combined_idx = __find_combined_index(page_idx, order);
                page = page + (combined_idx - page_idx);
                page_idx = combined_idx;
                order++;
        }
        set_page_order(page, order);
        list_add(&page->lru,
                &zone->free_area[order].free_list[migratetype]);
        zone->free_area[order].nr_free++;
}

在每次的遍历过程中,通过__page_find_buddy()为当前页框块找一个伙伴buddy,这个伙伴可能在当前页框块之前,也可能在其之后。通过page_is_buddy()判断刚才找到的buddy是否能和欲释放的页框块进行合并。如果可以合并,则将这个buddy从它所处的页框块链表中删除,并更新nr_free的值,然后再通过rmv_page_order()更新buddy页框块首页框的相关标志。

接下来,通过__find_combined_index()寻找合并后页框块的索引combined_idx。由于page永远都指向要释放页框块的首页框描述符,因此根据combined_idx更新page和page_idx。同时,由于成功进行了伙伴合并,因此最后再将分配阶order加一。一旦没有可合并的伙伴(通过page_is_buddy()而break),整个合并过程也将结束,即退出循环。

接下来就要将页框块进行释放,其实就是将合并后的页框块(也许并没有合并,还是合并之前的那个页框块)插入到具体的分配阶链表中,并设置首页框的相关标志,将nr_free加一。要释放的页框块由page指定,order则指明了应该将这个页框块插入到哪一个页框块链表中,而migratetype则更具体的指明了要将该页框块插入哪一个迁移列表中。这些操作和之前伙伴算法中页框分配的过程是相反的。

3.__page_find_buddy()

前文已经说过,这个函数用于寻找当前要释放页框块的伙伴。具体的办法是先通过异或求出伙伴的索引,再根据此索引求出伙伴页框块的首页框描述符。

static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
        unsigned long buddy_idx = page_idx ^ (1 << order);

        return page + (buddy_idx - page_idx);
}

由于buddy_idx-page_idx的值可能为正也可能为负,因此伙伴页框块可能在当前页框块之前,也可能在其之后。

4.__find_combined_index()

该函数可以获得合并后页框块的索引。如果伙伴页框在当前页框块之后,那么这个函数返回的索引还是原来的值page_idx。如果伙伴页框在当前页框之前,那么合并后页框的索引其实是伙伴页框的索引。

static inline unsigned long
__find_combined_index(unsigned long page_idx, unsigned int order)
{
        return (page_idx & ~(1 << order));
}

至此基于伙伴算法的页框分配过程完毕。

伙伴算法的数据结构

6 3 月, 2012

伙伴算法(buddy system)在物理内存管理中占据十分重要的位置,这种算法可以有效的避免内存中的外部碎片。所谓外部碎片(external fragmentation),就是指内存频繁请求和释放大小不同的连续页框后,导致在已分配页框块周围分散了许多小块空闲的页框,尽管这些空闲页框的总数可以满足接下来的请求,但却无法满足一个大块的连续页框。本文接下来详细说明伙伴算法在内核中的结构描述,其基本原理本文不再赘述。

在每个内存管理区中都有一个free_area数组,该数组的长度为MAX_ORDER,默认值为11。free_area数组描述的就是伙伴算法中每个分配阶(从0到11)所对应的页框块链表。比如free_area[2]所对应的页框块链表中,每个节点对应4个连续的页框(2的2次方)。

struct zone {
……
struct free_area        free_area[MAX_ORDER];
……
}

#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif

可以看到,free_area数组的元素类型是struct free_area,该结构的描述如下:

struct free_area {
        struct list_head        free_list[MIGRATE_TYPES];
        unsigned long           nr_free;
};

在这个结构中的确有一个表示当前分配阶所对应的页框块链表free_list,不过这里稍显复杂一下,因free_list是一个链表数组,这个数组也称为迁移数组。我们可以将这个数组看作是对页框块链表的进一步细分,每个数组元素对应一种迁移类型的页框块链表。迁移列表是在内核2.6.24中引入的,它更加的避免了由于系统长期运行而产生的外部碎片。除了链表结构以外,该结构使用nr_free表示当前链表中空闲页框块的数目,比如free_area[2]中nr_free的值为5,表示有5个大小为4的页框块,那么总的页框数目为20。

根据上面对伙伴算法数据结构的描述,可以得到下面的关系图:

上图表示的是某个内存节点中的某个内存管理区中的伙伴算法示意图。需要注意的是,页框描述符page中有一个lru字段,该字段即为链接每个页框块的链表节点。

struct page {
……
        struct list_head lru;
……
};

从图中也可以看出,链表中负责连接前后页框块的是该页框块首页框中的链表节点。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key