kernel hacker修炼之道之内存管理-bootmem allocator

bootmem allocator 核心数据结构

typedef struct bootmem_data { unsigned long node_boot_start; unsigned long node_low_pfn; void *node_bootmem_map; unsigned long last_offset; unsigned long last_pos; unsigned long last_success; /* Previous allocation point. To speed * up searching */ } bootmem_data_t;系统内存的中每一个结点都有一个bootmem_data_t结构，它含有bootmem allocator给结点分配内存时所需的信息。

• node_boot_start是这个结点内存的起始地址
• node_low_pfn是低端内存最后一个page的页帧号
• node_bootmem_map指向内存中bitmap所在的位置
• last_offset是分配的最后一个页内的偏移，如果该页完全使用，则offset为0
• last_pos是分配最后一个页帧号
• last_success是最后一次成功分配的位置

bootmem allocator 的初始化

unsigned long __init init_bootmem (unsigned long start, unsigned long pages) { max_low_pfn = pages; min_low_pfn = start; return(init_bootmem_core(NODE_DATA(0), start, 0, pages)); }

• max_low_pfn是低端内存结束page的帧号，在物理内存探测的文章中会介绍
• min_low_pfn是内核镜像后的第一个page的帧号，在setup_memory()中有这么一句：start_pfn = PFN_UP(init_pg_tables_end);也就是获得符号_end的下一个page的页帧号，传过来就是这里的start了

可以看出这里调用了核心函数init_bootmem_core()：

static unsigned long __init init_bootmem_core (pg_data_t *pgdat, unsigned long mapstart, unsigned long start, unsigned long end) { bootmem_data_t *bdata = pgdat->bdata; unsigned long mapsize = ((end - start)+7)/8; pgdat->pgdat_next = pgdat_list; pgdat_list = pgdat; mapsize = (mapsize + (sizeof(long) - 1UL)) & ~(sizeof(long) - 1UL); bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT); bdata->node_boot_start = (start << PAGE_SHIFT); bdata->node_low_pfn = end; /* * Initially all pages are reserved - setup_arch() has to * register free RAM areas explicitly. */ memset(bdata->node_bootmem_map, 0xff, mapsize); return mapsize; }

• 将结点添加到pgdat_list链表
  
• 计算位图大小，使用公式：，加7是为了使相除后向上取整，除以8获得所需的字节数
• 使mapsize对齐到sizeof(long)的倍数即4个字节的倍数，比如我们有80个页，mapsize为10，(10 + (4 -1 )) & ~(4 - 1)==》0000 1101 & 1111 1100，0000 1100，去掉低2位，为12，即4的倍数
• 这里设置bitmap的位置为内核镜像后的第一个page
• 设置内存块的起始物理地址
• 初始化所有的区域被占用
• 返回bitmap的大小

void * __init __alloc_bootmem (unsigned long size, unsigned long align, unsigned long goal) { pg_data_t *pgdat = pgdat_list; void *ptr; for_each_pgdat(pgdat) if ((ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal))) return(ptr); /* * Whoops, we cannot satisfy the allocation request. */ printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size); panic("Out of memory"); return NULL; }

• 每个结点是链在一个链表头为pgdat_list的链表上的，对于UMA的系统，只有一个结点，结点的描述符存放在contig_page_data变量中，因此这个pgdat_list指向一个只有一个元素的链表
• align的参数是指定对齐
• goal指定了希望分配内存的起始地址，会从这个位置开始查找
  

这里调用了核心函数__alloc_bootmem_core，下面看其实现：
static void * __init __alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size, unsigned long align, unsigned long goal) { unsigned long offset, remaining_size, areasize, preferred; unsigned long i, start = 0, incr, eidx; void *ret; if(!size) { printk("__alloc_bootmem_core(): zero-sized request\n"); BUG(); } BUG_ON(align & (align-1)); eidx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT); offset = 0; if (align && (bdata->node_boot_start & (align - 1UL)) != 0) offset = (align - (bdata->node_boot_start & (align - 1UL))); offset >>= PAGE_SHIFT; /* * We try to allocate bootmem pages above 'goal' * first, then we try to allocate lower pages. */ if (goal && (goal >= bdata->node_boot_start) && ((goal >> PAGE_SHIFT) < bdata->node_low_pfn)) { preferred = goal - bdata->node_boot_start; if (bdata->last_success >= preferred) preferred = bdata->last_success; } else preferred = 0; preferred = ((preferred + align - 1) & ~(align - 1)) >> PAGE_SHIFT; preferred += offset; areasize = (size+PAGE_SIZE-1)/PAGE_SIZE; incr = align >> PAGE_SHIFT ? : 1; restart_scan: for (i = preferred; i < eidx; i += incr) { unsigned long j; i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i); i = ALIGN(i, incr); if (test_bit(i, bdata->node_bootmem_map)) continue; for (j = i + 1; j < i + areasize; ++j) { if (j >= eidx) goto fail_block; if (test_bit (j, bdata->node_bootmem_map)) goto fail_block; } start = i; goto found; fail_block: i = ALIGN(j, incr); } if (preferred > offset) { preferred = offset; goto restart_scan; } return NULL;

• 在preffered～edix之间进行查找，使用 first fit。它会查找后面第一个为0的位
• 然后以这个为0位开始查找areasize大小的返回个page
• 如果失败重新找bitmap为0的bit
• 如果找到记下起始位置start

found: bdata->last_success = start << PAGE_SHIFT; BUG_ON(start >= eidx); /* * Is the next page of the previous allocation-end the start * of this allocation's buffer? If yes then we can 'merge' * the previous partial page with this allocation. */ if (align < PAGE_SIZE && bdata->last_offset && bdata->last_pos+1 == start) { offset = (bdata->last_offset+align-1) & ~(align-1); BUG_ON(offset > PAGE_SIZE); remaining_size = PAGE_SIZE-offset; if (size < remaining_size) { areasize = 0; /* last_pos unchanged */ bdata->last_offset = offset+size; ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset + bdata->node_boot_start); } else { remaining_size = size - remaining_size; areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE; ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset + bdata->node_boot_start); bdata->last_pos = start+areasize-1; bdata->last_offset = remaining_size; } bdata->last_offset &= ~PAGE_MASK; } else { bdata->last_pos = start + areasize - 1; bdata->last_offset = size & ~PAGE_MASK; ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start); } /* * Reserve the area now: */ for (i = start; i < start+areasize; i++) if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map))) BUG(); memset(ret, 0, size); return ret; }

• 找到后设置一下last_success
• 如果找到我们开始常识时候可以merge
• 能构merge需要几个条件：1）align < PAGE_SIZE 2）上一次分配最后一个page没有完全使用 3）找到的页正好是上次分配最后一个page的下一个page
• 如果可以merge，将offset按照align对齐
• 计算这个要被merge的page还剩下多少空间，即remaining_size
• 这时又分两种情况：1）请求的大小小于一个page且比前一个page剩下的大小小 2）反之
• 如果恰好请求的大小小于一个page且比前一个page剩下的大小小，则分配这个page的剩下部分给请求
• 如果请求大于等于剩下的大小则减一下，请求的一部分分在前一个page中，另一部分计算还需要多少个page
• 然后更新相应的last_pos，last_offset字段
• 如果不满足merge的条件，就从start开始分配，更新last_pos，last_offset字段
• 调用test_and_set_bit，对于没有设置bitmap的设置相应的位，像那种分配小块内存不足一个page的并且与前一个page merge的，当然test后就不用再设置了

void __init reserve_bootmem (unsigned long addr, unsigned long size) { reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size); }reserve_bootmem只是进行了一次封装，看reserve_bootmem_core的实现过程：

static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size) { unsigned long i; /* * round up, partially reserved pages are considered * fully reserved. */ unsigned long sidx = (addr - bdata->node_boot_start)/PAGE_SIZE; unsigned long eidx = (addr + size - bdata->node_boot_start + PAGE_SIZE-1)/PAGE_SIZE; unsigned long end = (addr + size + PAGE_SIZE-1)/PAGE_SIZE; BUG_ON(!size); BUG_ON(sidx >= eidx); BUG_ON((addr >> PAGE_SHIFT) >= bdata->node_low_pfn); BUG_ON(end > bdata->node_low_pfn); for (i = sidx; i < eidx; i++) if (test_and_set_bit(i, bdata->node_bootmem_map)) { #ifdef CONFIG_DEBUG_BOOTMEM printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE); #endif } }

• sidx 是起始页的索引
• edix是终止页的索引
• 调用test_and_set_bit函数将bitmap中相应位置位

这里的释放是用bootmem allocator释放内存，而不是bootmem allocator本身，其调用了free_bootmem_core函数：

void __init free_bootmem (unsigned long addr, unsigned long size) { free_bootmem_core(NODE_DATA(0)->bdata, addr, size); } 分析free_bootmem_core函数实现：

static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size) { unsigned long i; unsigned long start; /* * round down end of usable mem, partially free pages are * considered reserved. */ unsigned long sidx; unsigned long eidx = (addr + size - bdata->node_boot_start)/PAGE_SIZE; unsigned long end = (addr + size)/PAGE_SIZE; BUG_ON(!size); BUG_ON(end > bdata->node_low_pfn); if (addr < bdata->last_success) bdata->last_success = addr; /* * Round up the beginning of the address. */ start = (addr + PAGE_SIZE-1) / PAGE_SIZE; sidx = start - (bdata->node_boot_start/PAGE_SIZE); for (i = sidx; i < eidx; i++) { if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map))) BUG(); } }

• sidx 是起始页的索引
• edix是终止页的索引
• 调用test_and_clear_bit函数将bitmap中相应位清除，可以看出在bootmem allocator时代，内存的释放还是很容易的，清除相应bitmap就行。这时你发现相应page并没有清零，但是在__alloc_bootmem_core函数中，每次分配页后都调用memset进行清零操作

unsigned long __init free_all_bootmem (void) { return(free_all_bootmem_core(NODE_DATA(0))); }释放的时候调用free_all_bootmem，它只是一个前段，里边封装了核心函数free_all_bootmem_core。

static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat) { struct page *page; bootmem_data_t *bdata = pgdat->bdata; unsigned long i, count, total = 0; unsigned long idx; unsigned long *map; int gofast = 0; BUG_ON(!bdata->node_bootmem_map); count = 0; /* first extant page of the node */ page = virt_to_page(phys_to_virt(bdata->node_boot_start)); idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT); map = bdata->node_bootmem_map; /* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */ if (bdata->node_boot_start == 0 || ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG)) gofast = 1; for (i = 0; i < idx; ) { unsigned long v = ~map[i / BITS_PER_LONG]; if (gofast && v == ~0UL) { int j, order; count += BITS_PER_LONG; __ClearPageReserved(page); order = ffs(BITS_PER_LONG) - 1; set_page_refs(page, order); for (j = 1; j < BITS_PER_LONG; j++) { if (j + 16 < BITS_PER_LONG) prefetchw(page + j + 16); __ClearPageReserved(page + j); } __free_pages(page, order); i += BITS_PER_LONG; page += BITS_PER_LONG; } else if (v) { unsigned long m; for (m = 1; m && i < idx; m<<=1, page++, i++) { if (v & m) { count++; __ClearPageReserved(page); set_page_refs(page, 0); __free_page(page); } } } else { i+=BITS_PER_LONG; page += BITS_PER_LONG; } } total += count; /* * Now free the allocator bitmap itself, it's not * needed anymore: */ page = virt_to_page(bdata->node_bootmem_map); count = 0; for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++) { count++; __ClearPageReserved(page); set_page_count(page, 1); __free_page(page); } total += count; bdata->node_bootmem_map = NULL; return total; }将bitmap占用的空间释放给buddy system，此时bootmem allocator生命终结。

void *bootmem_addr = NULL; EXPORT_SYMBOL(bootmem_addr); #define BOOTMEM_SIZE 524288000在start_kernel函数中，记得要在mem_init函数之前添加：
bootmem_addr = alloc_bootmem(BOOTMEM_SIZE); if(!bootmem_addr) printk("can not alloc BOOTMEM\n"); else printk("alloc BOOTMEM success!\n");重新编译内核，重启，修改后：