1. First Fit分配器

    First Fit分配器是最基本的内存分配器，它使用bitmap而不是空闲块列表来表示内存。在bitmap中，如果page对应位为1，则表示此page已经被分配，为0则表示此page没有被分配。为了分配小于一个page的内存块，First Fit分配器记录了最后被分配的PFN (Page Frame Number)和分配的结束地址在页内的偏移量。随后小的内存分配被Merge到一起并存储到同一页中。

   First Fit分配器不会造成严重的内存碎片，但其效率较低，由于内存经常通过线性地址进行search，而First Fit中的小块内存经常在物理内存的开始处，为了分配大块内存而不得不扫描前面大量的内存。

2. Boot Memory分配器

    物理内存分配器如何分配内存来初始化其自己呢？

    答案是：通过Boot Memory分配器来实现，而Boot Memory分配器则通过最基本的First Fit分配器来实现。

2.1 Boot Map定义 

    Boot Map通过数据结构bootmem_data来定义，详见<linux/bootmem.h>，其定义如下所示： 

typedef struct bootmem_data {
  unsigned long node_boot_start; // 描述的物理内存的起始地址
  unsigned long node_low_pfn;    // 结束物理地址，即ZONE_NORMAL的结束
  void *node_bootmem_map;        // 描述“使用或空闲的位图”的地址
  unsigned long last_offset;     // 最后被分配的页内偏移量，即在llast_pos描述的物理页中，
                                 // 从last_offset开始，没有被分配 
  unsigned long last_pos;        // 最后被分配的页的PFN
} bootmem_data_t;

    所有bootmem_data被放于全局变量bdata_list中。

2.2 Boot Memory分配器初始化

      每一个CPU架构被要求提供setup_arch函数，它负责获取初始化boot memory分配器的必要参数。不同的CPU架构通过不同的函数来实现，如ARM通过bootmem_init来实现。它负责获取以下参数：

     • min_low_pfn： 系统中可获得的最小的PFN，装载kernel image结束之后的第一页，在mm/bootmem.c中定义

     • max_low_pfn：低端内存(ZONE_NORMAL)中可获得的最大PFN

     • highstart_pfn：高端内存(ZONE_HIGHMEM)的起始PFN

         • highend_pfn：高端内存(ZONE_HIGHMEM)的结束PFN

     • max_pfn：系统中可获得的最大的PFN， 在mm/bootmem.c中定义

     PFN是在物理内存map的偏移量，以page为单位。Kernel可直接访问ZONE_NORMAL，其偏移量为：PAGE_OFFSET。

     通过以上5个参数明确了可用物理内存之后，调用init_bootmem->init_bootmem_core来初始化contig_page_data。它主要完成以下两件事：

     1) 将把与此node对应pgdat_data_t插入到pgdat_list中

     2) 初始化bootmem_data_t的中参数，并分配表示页分配状态的bitmap，其大小为: (end_pfn-start_pfn+7)/8

          bitmap的物理地址为：bootmem_data_t->node_boot_start

          bitmap的虚拟地直为：bootmem_data_t->node_bootmem_map

2.3 分配内存

     • reserve_bootmem：用于预留物理页面。但用于通用的内存分配是低率的，它主要用于各种驱动(如：Video Codec)预留内存。

     常用的内存分配函数如下(in UMA架构，我们常的ARM架构为UMA架构)：

     • alloc_bootmem

     • alloc_bootmem_low

     • alloc_bootmem_pages

     • alloc_bootmem_low_pages

     其调用关系如下图所示：

 2.3.1  __alloc_bootmem

     __alloc_bootmem() 需要以下参数：

     • pgdat

       用于分配内存块的节点，在UMA架构中，它被忽略，因为它总是为：contig_page_data

     • size

       指定请求分配的内存大小，以字节为单位

     • align

       请求以多少字节对齐，地于小块内存分配，一般以SMP_CACHE_BYTES对齐，如在X86上，与L1硬件cache对齐

     • goal

       偏好的分配内存的起始地址,

2.3.2 __alloc_bootmem_core

     它从goal指定的地址开始，线性地扫描内存，以寻找可以满足内存分配要求的内存块。它的另外一项功能是决定是否需要把新分配的内存块与以前已经分配的内存块merge到一起。

   

      分配内存常用函数定义如下： 

#ifdef CONFIG_NO_BOOTMEM
/* We are using top down, so it is safe to use 0 here */
#define BOOTMEM_LOW_LIMIT 0
#else
#define BOOTMEM_LOW_LIMIT __pa(MAX_DMA_ADDRESS)
#endif

#define alloc_bootmem(x) \
	__alloc_bootmem(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_align(x, align) \
	__alloc_bootmem(x, align, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_nopanic(x) \
	__alloc_bootmem_nopanic(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_pages(x) \
	__alloc_bootmem(x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_pages_nopanic(x) \
	__alloc_bootmem_nopanic(x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_node(pgdat, x) \
	__alloc_bootmem_node(pgdat, x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_node_nopanic(pgdat, x) \
	__alloc_bootmem_node_nopanic(pgdat, x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_pages_node(pgdat, x) \
	__alloc_bootmem_node(pgdat, x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_pages_node_nopanic(pgdat, x) \
	__alloc_bootmem_node_nopanic(pgdat, x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)

#define alloc_bootmem_low(x) \
	__alloc_bootmem_low(x, SMP_CACHE_BYTES, 0)
#define alloc_bootmem_low_pages(x) \
	__alloc_bootmem_low(x, PAGE_SIZE, 0)
#define alloc_bootmem_low_pages_node(pgdat, x) \
	__alloc_bootmem_low_node(pgdat, x, PAGE_SIZE, 0)

2.4 释放内存

     调用free_bootmem来释放内存。

void __init free_bootmem(unsigned long addr, unsigned long size)
{
	unsigned long start, end;

	kmemleak_free_part(__va(addr), size);

	start = PFN_UP(addr);
	end = PFN_DOWN(addr + size);

	mark_bootmem(start, end, 0, 0);
}