bootmem allocator

시스템 시작 단계 에서 buddy 시스템 과 slab 분배 기 가 구축 되 기 전에 시스템 의 모든 노드 는 자신의 bootmem allocator 를 가지 고 메모리 분 배 를 실현 합 니 다. 시작 단계 가 끝나 면 bootmem allocator 는 소각 되 고 해당 하 는 남 은 메모 리 는 buddy 시스템 에 제출 하여 관리 하기 때문에 bootmem allocator 가 존재 하 는 시간 은 짧 습 니 다. 그 취 지 는 간단 합 니 다.효율 이 아니 라!bootmem allocator 의 기본 사상 은 한 노드 에 비트 맵 구역 을 만 드 는 것 입 니 다. 각 노드 의 저급 메모리 에 대한 페이지 상 자 는 하나의 bit 를 통 해 페이지 의 상 태 를 표시 하고 페이지 의 배분 과 회 수 를 실현 합 니 다.
        우선 bootmem 의 핵심 데이터 구 조 를 알 아 보 겠 습 니 다.
 

typedef struct bootmem_data {
	unsigned long node_min_pfn; 	
	unsigned long node_low_pfn;
	void *node_bootmem_map;    
	unsigned long last_end_off; 	
	unsigned long hint_idx;     	
	struct list_head list;     
} bootmem_data_t;

node_min_pfn: 노드 의 최소 페이지 상자 번호

node_low_pfn: 노드 의 저급 메모리 최대 페이지 상자 번호

node_bootmem_map: 노드 의 비트 맵 시작 주소

last_end_off: 마지막 으로 분 배 된 메모리 의 마지막 바이트 가 소속 페이지 끝의 오프셋 에 비해 이 변 수 는 메모리 가 분 배 될 때 사용 되 며 조각 이 생기 지 않도록 합 니 다.

hint_idx: 메모리 할당 에 사용 할 때 할당 의 시작 주 소 를 확인 합 니 다.

list: 이 노드 의 bootmem 체인 을 모든 노드 의 bootmem 링크 에 연결 하 는 데 사용 합 니 다.

     다음은 구체 적 인 코드 를 결합 하여 다음 과 같은 몇 가지 주요 측면 에서 bootmem allocator 의 작업 과정 을 소개 합 니 다.
      1. bootmem allocator 초기 화
      2. bootmem allocator 메모리 저장 및 메모리 방출
      3. bootmem allocator 할당 메모리
      4. bootmem allocator 의 소각
1. bootmem allocator 초기 화
        archsetup (), initmeminit()-->setup_bootmem_allocator()-->setup_node_bootmem()-->init_bootmem_노드 에 있 는 bootmem allocator 를 만 들 기 위해 node () 를 만 듭 니 다. 또 하나의 초기 화 함 수 는 init 입 니 다.bootmem (), 그 와 initbootmem_node () 와 마찬가지 로 모두 initbootmem_core () 의 패 키 징 은 전 자 는 단일 노드 시스템 만 대상 으로 하고 후 자 는 하나의 노드 를 지정 하여 뒤의 다른 작업 에서 비슷 한 패 키 징 방법 을 사용 한 것 과 구별 된다.

unsigned long __init init_bootmem_node(pg_data_t *pgdat, unsigned long freepfn,
				unsigned long startpfn, unsigned long endpfn)
{
	return init_bootmem_core(pgdat->bdata, freepfn, startpfn, endpfn);
}

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)->bdata, start, 0, pages);
}

 
다음은 bootmem 초기 화의 핵심 함수 init 를 살 펴 보 겠 습 니 다.bootmem_core()

static unsigned long __init init_bootmem_core(bootmem_data_t *bdata,
	unsigned long mapstart, unsigned long start, unsigned long end)
{
	unsigned long mapsize;

	mminit_validate_memmodel_limits(&start, &end);
	bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));/*             */
	bdata->node_min_pfn = start;/*       */
	bdata->node_low_pfn = end;  /*       */
	link_bootmem(bdata);/*  bdata     bdata_list */

	/*
	 * Initially all pages are reserved - setup_arch() has to
	 * register free RAM areas explicitly.
	 */
	mapsize = bootmap_bytes(end - start);
	memset(bdata->node_bootmem_map, 0xff, mapsize);/*      1，     */

	bdebug("nid=%td start=%lx map=%lx end=%lx mapsize=%lx
",
		bdata - bootmem_node_data, start, mapstart, end, mapsize);

	return mapsize;/*      */
}

 
우 리 는 init 에서 볼 수 있다.bootmem_core () 에서 주요 작업 은 bdata 의 변 수 를 초기 화하 고 비트 맵 을 모두 1 로 설정 하 는 것 입 니 다. 이 매개 변 수 는 앞에서 열거 한 함수 에서 이 루어 진 것 이 확실 합 니 다.
 
 
2. bootmem allocator 메모리 저장 및 메모리 방출
           메모리 보존 과 메모리 방출 은 두 가지 상대 적 인 개념 입 니 다. bootmem allocator 가 할당 한 메모 리 는 보존 상태 로 표 시 됩 니 다. 즉, 해당 하 는 비트 맵 구역 은 모두 1 입 니 다. 이 안에 bootmem allocator 가 존재 하면 버 디 시스템 에 의 해 관리 되 지 않 습 니 다. 내부 저장 소 를 방출 하 는 것 은 이해 하기 쉽 습 니 다. 즉, 해당 페이지 를 빈 상태 로 두 는 것 입 니 다.이 페이지 들 은 bootmem allocator 에 의 해 분 배 될 수 있 으 며, 남 은 페이지 는 bootmem allocator 에서 소각 되면 buddy 시스템 에 의 해 연 결 됩 니 다.
       메모리 저장 처 리 를 살 펴 보고 reserve 호출bootmem_node () 함 수 는 지정 한 노드 의 지정 범위 페이지 를 보존 상태 로 설정 할 수 있 습 니 다.

int __init reserve_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
				 unsigned long size, int flags)
{
	unsigned long start, end;

	start = PFN_DOWN(physaddr);     /*      */
 	end = PFN_UP(physaddr + size);  /*      */

	return mark_bootmem_node(pgdat->bdata, start, end, 1, flags);
}

 
다음은 핵심 함수 markbootmem_node()

static int __init mark_bootmem_node(bootmem_data_t *bdata,
				unsigned long start, unsigned long end,
				int reserve, int flags)
{
	unsigned long sidx, eidx;

	bdebug("nid=%td start=%lx end=%lx reserve=%d flags=%x
",
		bdata - bootmem_node_data, start, end, reserve, flags);

	/*    */
	BUG_ON(start < bdata->node_min_pfn);
	BUG_ON(end > bdata->node_low_pfn);

	/*   start index,end index, start end              */
	sidx = start - bdata->node_min_pfn;
	eidx = end - bdata->node_min_pfn;

	if (reserve) /*        */
		return __reserve(bdata, sidx, eidx, flags);
	else	    /*      */
		__free(bdata, sidx, eidx);
	return 0;
}

 
다시 보기reserve()

static int __init __reserve(bootmem_data_t *bdata, unsigned long sidx,
			unsigned long eidx, int flags)
{
	unsigned long idx;
	int exclusive = flags & BOOTMEM_EXCLUSIVE;

	bdebug("nid=%td start=%lx end=%lx flags=%x
",
		bdata - bootmem_node_data,
		sidx + bdata->node_min_pfn,
		eidx + bdata->node_min_pfn,
		flags);

	for (idx = sidx; idx < eidx; idx++)/*  sidx-->eidx          */
		if (test_and_set_bit(idx, bdata->node_bootmem_map)) {/*        1*/
			if (exclusive) {
				__free(bdata, sidx, idx);
				return -EBUSY;
			}
			bdebug("silent double reserve of PFN %lx
",
				idx + bdata->node_min_pfn);
		}
	return 0;
}

 
페이지 를 유지 하 는 관건 적 인 작업 은 test 를 호출 하 는 것 임 을 알 수 있 습 니 다.and_set_bit () 비트 맵 의 관련 구역 을 1.
 
          메모 리 를 방출 하 는 것 과 메모 리 를 보존 하 는 과정 은 기본적으로 같 지만 mark 에 게 만 전 달 됩 니 다.bootmem_node () 의 reserve 인 자 는 0 으로 해당 페이지 를 표시 하기 때문에 markbootmem_node () 에서 호출free()

static void __init __free(bootmem_data_t *bdata,
			unsigned long sidx, unsigned long eidx)
{
	unsigned long idx;

	bdebug("nid=%td start=%lx end=%lx
", bdata - bootmem_node_data,
		sidx + bdata->node_min_pfn,
		eidx + bdata->node_min_pfn);

	if (bdata->hint_idx > sidx)
		bdata->hint_idx = sidx;/*  hint_idx        */

	for (idx = sidx; idx < eidx; idx++)/*         */
		if (!test_and_clear_bit(idx, bdata->node_bootmem_map))/*  */
			BUG();
}

__free () 비교reserve () 대 bdata - > hintidx 의 조작, 이곳 은 hintidx 는 가장 낮은 빈 페이지 를 가리 키 고 있 습 니 다. 분 배 를 진행 할 때 boot allocator 는 가장 낮은 빈 페이지 부터 분 배 를 보장 하기 때 문 입 니 다.
 
 
3. bootmem allocator 할당 메모리
         bootmem allocator 의 메모리 배분 은 앞의 작업 에 비해 복잡 합 니 다. 이 안에서 주로 고려 하 는 문 제 는 메모리 조각 입 니 다.우리 의 페이지 크기 를 4KB 로 설정 합 니 다. 만약 에 우리 가 지난번 에 메모 리 를 분배 한 범위 가 네 번 째 페이지 부터 여덟 번 째 페이지 의 2KB 에 이 르 렀 는데 이번에 배정 을 요구 하 는 시작 주 소 는 아홉 번 째 페이지 에 있 습 니 다. 만약 에 아홉 번 째 페이지 부터 분배 하면 적어도 2KB 의 메모리 조각 이 생 겨 서 대량의 낭 비 를 초래 할 수 있 습 니 다.이것 도 우리 가 전에 소개 한 bootmem 핵심 데이터 구조 에 last 를 도입 한 이유 입 니 다.end_off 이 변 수 는 마지막 으로 분 배 된 말단 주소 의 페이지 끝 에서 의 오프셋 을 기록 합 니 다. 이 예 에서 이 값 은 2KB 입 니 다. 그러면 이번에 우리 가 9 번 째 페이지 부터 분 배 를 시작 하면 이 2KB 를 이번 분배 에 통합 하 는 것 을 고려 해 야 합 니 다.
       메모리 분배 의 핵심 함 수 는 allocbootmem_core (), 구체 적 인 코드 는 다음 과 같 습 니 다.

static void * __init alloc_bootmem_core(struct bootmem_data *bdata,
					unsigned long size, unsigned long align,
					unsigned long goal, unsigned long limit)
{
	unsigned long fallback = 0;
	unsigned long min, max, start, sidx, midx, step;

	bdebug("nid=%td size=%lx [%lu pages] align=%lx goal=%lx limit=%lx
",
		bdata - bootmem_node_data, size, PAGE_ALIGN(size) >> PAGE_SHIFT,
		align, goal, limit);

	BUG_ON(!size);                        /*  size*/
	BUG_ON(align & (align - 1));          /*        2    */
	BUG_ON(limit && goal + size > limit); /*  limit  0   goal+size    limit*/

	if (!bdata->node_bootmem_map)
		return NULL;

	/*                 */
	min = bdata->node_min_pfn;
	max = bdata->node_low_pfn;

	/* goal limit         */
	goal >>= PAGE_SHIFT;
	limit >>= PAGE_SHIFT;

	if (limit && max > limit)
		max = limit;
	if (max <= min)
		return NULL;

	/*    ，      */
	step = max(align >> PAGE_SHIFT, 1UL);

	/*      */
	if (goal && min < goal && goal < max)
		start = ALIGN(goal, step);
	else
		start = ALIGN(min, step);

	/*               */
	sidx = start - bdata->node_min_pfn;
	midx = max - bdata->node_min_pfn;

	if (bdata->hint_idx > sidx) { /*sidx  hint_idx       hint_idx      */
		/*
		 * Handle the valid case of sidx being zero and still
		 * catch the fallback below.
		 */
		fallback = sidx + 1;
		sidx = align_idx(bdata, bdata->hint_idx, step);
	}

	while (1) {
		int merge;
		void *region;
		unsigned long eidx, i, start_off, end_off;
find_block:
		sidx = find_next_zero_bit(bdata->node_bootmem_map, midx, sidx); /*     0       */
		sidx = align_idx(bdata, sidx, step);                            /* step    */
		eidx = sidx + PFN_UP(size);

		if (sidx >= midx || eidx > midx)
			break;

		for (i = sidx; i < eidx; i++)
			if (test_bit(i, bdata->node_bootmem_map)) { /*      ，                */
				sidx = align_idx(bdata, i, step);  /*  sidx*/
				if (sidx == i)
					sidx += step;
				goto find_block;                   /*      bitmap*/
			}
			
        /*   1.     PAGE       
		       2.PAGE_SIZE-1>0
		       3.     PAGE         PAGE       */
		if (bdata->last_end_off & (PAGE_SIZE - 1) &&
				PFN_DOWN(bdata->last_end_off) + 1 == sidx)
			start_off = align_off(bdata, bdata->last_end_off, align);/*start_off    PAGE     ,       ,                         */
		else
			start_off = PFN_PHYS(sidx);/*       ，       PAGE  */

		merge = PFN_DOWN(start_off) < sidx; /*  merge   0 1*/
		end_off = start_off + size;

		/*    last_end_off hint_idx*/
		bdata->last_end_off = end_off;
		bdata->hint_idx = PFN_UP(end_off);

		/*
		 * Reserve the area now:
		 */
		if (__reserve(bdata, PFN_DOWN(start_off) + merge, /*       */
				PFN_UP(end_off), BOOTMEM_EXCLUSIVE))
			BUG();

		region = phys_to_virt(PFN_PHYS(bdata->node_min_pfn) + /*           */
				start_off);
		memset(region, 0, size);/*         */
		/*
		 * The min_count is set to 0 so that bootmem allocated blocks
		 * are never reported as leaks.
		 */
		kmemleak_alloc(region, size, 0, 0);
		return region;
	}

	if (fallback) {
		sidx = align_idx(bdata, fallback - 1, step);
		fallback = 0;
		goto find_block;
	}

	return NULL;
}
 
 

4.bootmem allocator   
           bootmem allocator   ，         buddy system  ，     free_all_bootmem_core()

static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
{
	int aligned;
	struct page *page;
	unsigned long start, end, pages, count = 0;

	if (!bdata->node_bootmem_map)/*bitmap   ，         */
		return 0;

	/*                */
	start = bdata->node_min_pfn;
	end = bdata->node_low_pfn;

	/*
	 * If the start is aligned to the machines wordsize, we might
	 * be able to free pages in bulks of that order.
	 */
	aligned = !(start & (BITS_PER_LONG - 1));/*  start   2    */

	bdebug("nid=%td start=%lx end=%lx aligned=%d
",
		bdata - bootmem_node_data, start, end, aligned);

	/*************************************
	*            :               *
	*************************************/
	while (start < end) {
		unsigned long *map, idx, vec;

		map = bdata->node_bootmem_map;
		idx = start - bdata->node_min_pfn;
		vec = ~map[idx / BITS_PER_LONG];/* idx   long           */

		/*  :1.     2    
		       2. long       0，     
		       3.start+BITS_PER_LONG     */
		if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {
			int order = ilog2(BITS_PER_LONG);/*  Long    2     */

			__free_pages_bootmem(pfn_to_page(start), order);/*         */
			count += BITS_PER_LONG;
		} else {/*        */
			unsigned long off = 0;

			while (vec && off < BITS_PER_LONG) {/*                 */
				if (vec & 1) { /*vec     1，    start+off   page   */
					page = pfn_to_page(start + off);
					__free_pages_bootmem(page, 0);
					count++;
				}
				vec >>= 1;
				off++;
			}
		}
		start += BITS_PER_LONG;
	}

	/*****************************
	*     :    bitmap   *
	******************************/
	page = virt_to_page(bdata->node_bootmem_map);/*  bitmap        */
	pages = bdata->node_low_pfn - bdata->node_min_pfn;
	pages = bootmem_bootmap_pages(pages);/*  bitmap   ，     */
	count += pages;
	while (pages--)/*    */
		__free_pages_bootmem(page++, 0);

	bdebug("nid=%td released=%lx
", bdata - bootmem_node_data, count);

	return count;/*        */
}