Memblock – (1)

<kernel v5.10>

Memblock

memblock 메모리 할당자는 커널 부트업 타임에 가장 먼저 활성화되는 메모리 할당자로, 다른 커널 메모리 할당자가 준비되기 전에 메모리 범위를 등록하여 사용한다. 주로 부팅 타임에 사용되지만 메모리 핫플러그 기능이 활성화되어 있으면 런타임에도 사용한다. 2010년 커널 v2.6.35에서 memblock이 처음 소개되어 사용하기 전에는 bootmem이라는 메모리 할당자를 사용했었다. bootmem이 부트업에 필요한 메모리의 일부(lowmem)만을 관리하는 것에 비해 memblock은 전체 메모리를 관리한다. 커널에서 페이지 할당자로 사용하는 버디 시스템이 준비되기 전까지 메모리 할당을 먼저(early) 할 수 있는 메모리 관리자는 memblock이 유일하다. 따라서 early 메모리 할당자라는 용어를 사용한다. 또한 memblock은 LMB(Logical Memory Block)라고 알려져 있다. 또한 핫플러그메모리를 지원하면서 런타임에 추가된 메모리를 memblock을 사용하여 추가한 이후 버디 할당자로 전환하는데에도 사용된다.

 

Memblock의 구조

memblock은 다음과 같이 두 가지 타입으로 나누어 관리하고 있다

• memory 타입
  •  memory 타입은 사용할 물리 메모리 영역을 등록하여 사용한다. 커널 파라미터에 의해 실제 물리 메모리의 일부 영역만을 사용하게끔 제한되어 등록 가능하다. 처음에는 regions[ ] 배열에 최대 128개의 영역을 사용할 수 있고, 추후 2배 단위로 계속 확장될 수 있다.
• reserved 타입
  • reserved 타입은 사용 중이거나 사용할 물리 메모리 영역을 등록하여 사용한다. 처음에는 regions[ ] 배열에 최대 128개의 영역을 사용할 수 있고, 추후 2배 단위로 계속 확장될 수 있다.

 

초기에 memblock 영역은 아래의 타입과 영역 배열로 등록되어 있다.

 

physmem 타입

physmem 타입은 2014년에 추가된 타입이며, 물리적으로 감지된 메모리 영역을 등록하여 사용되고 이 값은 등록된 후 수정되지 않는다는 특성이 있다. memory 타입과 달리 커널 파라미터에 의해 제한된 메모리가 아닌 실제 물리 메모리 크기를 등록하여 사용할 계획으로 코드가 추가되었고, 현재 s390 아키텍처에서 사용하고 있다. regions[ ] 배열로 처음에 최대 4개의 엔트리를 사용한다.

 

CONFIG_HAVE_MEMBLOCK_PHYS_MAP

• 2014년 1월 kernel 3.16-rc1에서 추가된 옵션
• 사용가능한 물리메모리의 영역을 4개(INIT_PHYSMEM_REGIONS)까지 추가할 수 있으며 입력된 영역은 수정되지 않는다.
• 다른 memblock 구조체와 다르게 메모리의 전체 range를 담고 있다.

CONFIG_ARCH_KEEP_MEMBLOCK

• memblock에 등록된 데이터를 early 부트 프로세스 이후 메모리에서 제거하지 않고 보존할 수 있게 vmlinux.lds.h 에서 제어할 수 있는 옵션이다.

 

include/linux/memblock.h

#ifndef CONFIG_ARCH_KEEP_MEMBLOCK
#define __init_memblock __meminit
#define __initdata_memblock __meminitdata
void memblock_discard(void);
#else
#define __init_memblock
#define __initdata_memblock
static inline void memblock_discard(void) {}
#endif

 

include/linux/init.h

#define __meminit        __section(.meminit.text) __cold notrace \
                                                  __latent_entropy
#define __meminitdata    __section(.meminit.data)

 

CONFIG_MEMORY_HOTPLUG

• CONFIG_ARCH_KEEP_MEMBLOCK 옵션과 같이 사용한다.
  • CONFIG_MEMORY_HOTPLUG 옵션을 사용하지 않는 경우 부트 프로세스가 끝나고 나면 memblock 영역을 삭제할 수 있다. 이러한 경우 부팅 이후에 memblcok을 사용하면 안된다.
  • CONFIG_MEMORY_HOTPLUG를 사용하는 경우 부트 프로세스가 끝나더라도 계속 사용할 수 있도록 보존 한다.

 

include/asm-generic/vmlinux.lds.h

#if defined(CONFIG_MEMORY_HOTPLUG)
#define MEM_KEEP(sec)    *(.mem##sec)
#define MEM_DISCARD(sec)
#else
#define MEM_KEEP(sec)
#define MEM_DISCARD(sec) *(.mem##sec)
#endif

 

초기화

전역 구조체명 memblock은 컴파일 타임에 아래와 같이 초기화된다.

• cnt 변수는 각 영역의 갯수로 초기 1로 설정된다.
  • 영역 데이터가 하나도 없어도 기본 1로 설정되어 있으며, 영역 데이터를 처음 하나 추가하는 경우 cnt는 변동되지 않는다. 그 후 부터는 추가할 때마다 1씩 증가한다.
• bottom_up 변수는 arm 및 arm64에서 디폴트로 false로 되어 있어 allocation 요청 시 상단에서 하단으로 검색하여 free 공간을 찾는 방향성을 갖는다.
• current_limit은 초기에 MEMBLOCK_ALLOC_ANYWHERE (~(phys_addr_t) 0)로 설정하고 설정될 수 있는 값은 다음과 같다.
  • MEMBLOCK_ALLOC_ANYWHERE (~(phys_addr_t) 0):
    • 물리 주소의 최대치
  • MEMBLOCK_ALLOC_ACCESSBLE (0):
    • 물리 메모리 주소의 최대치
  • 입력한 주소 값으로 최대 한계 제한

 

memblock_region 배열

mm/memblock.c

static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS] __initdata_memblocc
k;
static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_RESERVED_REGIONS] __initdd
ata_memblock;
#ifdef CONFIG_HAVE_MEMBLOCK_PHYS_MAP
static struct memblock_region memblock_physmem_init_regions[INIT_PHYSMEM_REGIONS]
k;
#endif

컴파일 타임에 memblock 영역에 사용할 엔트리 배열의 개수를 지정한다. 배열의 크기는 위에서 아래 순서대로 각각 128, 128, 4개이다. 물리 메모리 등록은 몇 번 등록하지 않으므로 최대 4개로 제한된 상태이다.

 

memblock 배열

mm/memblock.c

struct memblock memblock __initdata_memblock = {
        .memory.regions         = memblock_memory_init_regions,
        .memory.cnt             = 1,    /* empty dummy entry */
        .memory.max             = INIT_MEMBLOCK_REGIONS,
        .memory.name            = "memory",

        .reserved.regions       = memblock_reserved_init_regions,
        .reserved.cnt           = 1,    /* empty dummy entry */
        .reserved.max           = INIT_MEMBLOCK_REGIONS,
        .reserved.name          = "reserved",

        .bottom_up              = false,
        .current_limit          = MEMBLOCK_ALLOC_ANYWHERE,
};

컴파일 타임에 3 가지 타입의 memblock 영역을 관리하는 memblock을 준비한다. 처음에 부트업에서는 각 memblock 영역들은 static 한 배열을 가리키고 있다가, 확장이 필요할 때 dynamic하게 추가될 수 있다.

• 코드 라인 2~5에서 memory memblock을 128개 엔트리 배열로 초기화한다.
• 코드 라인 7~10에서 reserved memblock을 128개 엔트리 배열로 초기화한다. 이 배열의 크기는 추후 reserved 영역이 등록되어 가득 차면 2배 단위로 확장하여 사용할 수 있다.
• 코드 라인 12에서 비어 있는 영역의 검색을 위에서 아래 주소 방향으로 수행하도록 초깃값으로 설정한다.
• 코드 라인 13에서 최대 메모리 할당 제한 값을 시스템이 사용하는 주소의 가장 큰 주소를 갖게 하여 제한이 없는 상태로 초기화한다

 

다음 그림은 memblock, memblock_type 및 memblock_regions 구조체들 사이의 연관성을 보여준다.

 

주요 구조체

struct memblock

include/linux/memblock.h

struct memblock {
        bool bottom_up;  	/* is bottom up direction? */
        phys_addr_t current_limit;
        struct memblock_type memory;
        struct memblock_type reserved;
};

• bottom_up
  • 메모리 할당을 아래에서 위로 검색하여 빈 공간을 할당할 수 있도록 하는 옵션으로, 현재 x86_64 NUMA 시스템에 먼저 적용되어 있다. NUMA 시스템에서 메모리 핫플러그 기능을 사용하는 경우 효과가 있다. 커널이 할당한 메모리가 최대한 커널이 있는 low 메모리 주소 근처에 할당하게 유도하여 특정 노드의 메모리를 시스템에서 오프(off)할 때 그 노드에서 이미 할당되어 사용하는 페이지들이 적은 경우 마이그레이션(migration)되는 비율을 최대한 억제할 수 있기 때문에 설계된 기능이다(1 = 아래에서 위로 할당).
• current_limit
  • 커널 부트업 프로세스 루틴에서 커널 메모리의 할당을 제한하고자 하는 경우에 사용한다. 64비트 시스템에서 모든 물리 메모리에 대해 가상 메모리에 1:1 direct 매핑되어 있으므로 별도로 lowmem 영역으로 관리하지 않기 때문에 current_limit에는 커널 초기 빌드 시 주어진 사용되는 MEMBLOCK_ALLOC_ANYWHERE(0xffffffff_ffffffff) 값으로 지정된다.
• memory
  • 물리 메모리 영역 등록
• reserved
  • reserved 영역 등록

 

struct memblock_type

include/linux/memblock.h

struct memblock_type {
        unsigned long cnt;
        unsigned long max;
        phys_addr_t total_size;
        struct memblock_region *regions;
        char *name;
};

• cnt
  • 사용 영역 엔트리 수다. 엔트리 영역이 한 건도 등록되지 않아도 1부터 시작하도록 설계되었다. 첫 엔트리 영역이 추가되는 경우 이 값은 바뀌지 않고, 두 번째 엔트리가 추가될 때마다 증가된다.
• max
  • 최대 사용 가능한 영역 엔트리 수
• total_size
  • 해당 memblock 타입의 등록된 모든 영역의 크기를 더한 값(bytes)
• *regions
  • 영역을 가리키는 포인터
• *name
  • 영역명

 

struct memblock_region

include/linux/memblock.h

struct memblock_region {
        phys_addr_t base;
        phys_addr_t size;
        enum memblock_flags flags;
#ifdef CONFIG_NEED_MULTIPLE_NODES
        int nid;
#endif
};

• base
  • 시작 물리 주소
• size
  • 영역 크기
• flags
  • flags에는 다음과 같이 4개의 매크로 상수를 사용하고 3개의 비트 요청을 조합하여 사용할 수 있다.
    • MEMBLOCK_NONE(0x0): 특이 요청 없는 영역
    • MEMBLOCK_HOTPLUG(0x1): 메모리 핫플러그 영역
    • MEMBLOCK_MIRROR(0x2): 미러된 영역
    • MEMBLOCK_NOMAP(0x4): 커널이 직접 매핑하지 않는 영역
• nid
  • 노드 id

 

---

 

Memblock의 기본 관리 API

메모리를 추가할 때 멀티 노드(NUMA 등) 시스템이 아닌 경우 memblock_add( ) 함수를 사용하면 내부에서 노드 id는 0으로 처리된다. 그리고 멀티 노드 시스템을 사용하는 경우 memblock_add_node( ) 함수를 사용하여 노드 id까지 지정을 한다. 머신을 설계할 때 등록되는 메모리 영역이 서로 겹치지 않도록 되어 있지만, 여러 가지 예외 처리를 위해 다양한 상황에서 요청한 영역이 겹치지 않도록 조정을 한다.

 

메모리 영역 추가

memblock_add()

mm/memblock.c

/**
 * memblock_add - add new memblock region
 * @base: base address of the new region
 * @size: size of the new region
 *
 * Add new memblock region [@base, @base + @size) to the "memory"
 * type. See memblock_add_range() description for mode details
 *
 * Return:
 * 0 on success, -errno on failure.
 */

int __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
{
        phys_addr_t end = base + size - 1;

        memblock_dbg("memblock_add: [%pa-%pa] %pF\n",
                     &base, &end, (void *)_RET_IP_);

        return memblock_add_range(&memblock.memory, base, size, MAX_NUMNODES, 0);
}

메모리 영역을 memory memblock에 추가한다.

• 물리 메모리 시작 주소 @base 부터 @size 만큼을 memory memblock에 추가한다.

 

reserve 영역 추가

memblock_reserve()

mm/memblock.c

int __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
{
        phys_addr_t end = base + size - 1;

        memblock_dbg("%s: [%pa-%pa] %pS\n", __func__,
                     &base, &end, (void *)_RET_IP_);

        return memblock_add_range(&memblock.reserved, base, size, MAX_NUMNODES, 0);
}

reserved 영역을 reserved memblock에 추가한다.

• 물리 메모리 시작 주소 @base 부터 @size 만큼을 reserved memblock에 추가한다.

 

영역 추가

memblock_add_range()

mm/memblock.c

/**
 * memblock_add_range - add new memblock region
 * @type: memblock type to add new region into
 * @base: base address of the new region
 * @size: size of the new region
 * @nid: nid of the new region
 * @flags: flags of the new region
 *
 * Add new memblock region [@base,@base+@size) into @type.  The new region
 * is allowed to overlap with existing ones - overlaps don't affect already
 * existing regions.  @type is guaranteed to be minimal (all neighbouring
 * compatible regions are merged) after the addition.
 *
 * RETURNS:
 * 0 on success, -errno on failure.
 */

int __init_memblock memblock_add_range(struct memblock_type *type,
                                phys_addr_t base, phys_addr_t size,
                                int nid, enum memblock_flags flags)
{
        bool insert = false;
        phys_addr_t obase = base;
        phys_addr_t end = base + memblock_cap_size(base, &size);
        int idx, nr_new;
        struct memblock_region *rgn;

        if (!size)
                return 0;

        /* special case for empty array */
        if (type->regions[0].size == 0) {
                WARN_ON(type->cnt != 1 || type->total_size);
                type->regions[0].base = base;
                type->regions[0].size = size;
                type->regions[0].flags = flags;
                memblock_set_region_node(&type->regions[0], nid);
                type->total_size = size;
                return 0;
        }
repeat:
        /*
         * The following is executed twice.  Once with %false @insert and
         * then with %true.  The first counts the number of regions needed
         * to accommodate the new area.  The second actually inserts them.
         */
        base = obase;
        nr_new = 0;

        for_each_memblock_type(idx, type, rgn) {
                phys_addr_t rbase = rgn->base;
                phys_addr_t rend = rbase + rgn->size;

                if (rbase >= end)
                        break;
                if (rend <= base)
                        continue;
                /*
                 * @rgn overlaps.  If it separates the lower part of new
                 * area, insert that portion.
                 */
                if (rbase > base) {
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
                        WARN_ON(nid != memblock_get_region_node(rgn));
#endif
                        WARN_ON(flags != rgn->flags);
                        nr_new++;
                        if (insert)
                                memblock_insert_region(type, idx++, base,
                                                       rbase - base, nid,
                                                       flags);
                }
                /* area below @rend is dealt with, forget about it */
                base = min(rend, end);
        }

        /* insert the remaining portion */
        if (base < end) {
                nr_new++;
                if (insert)
                        memblock_insert_region(type, idx, base, end - base,
                                               nid, flags);
        }

        if (!nr_new)
                return 0;

        /*
         * If this was the first round, resize array and repeat for actual
         * insertions; otherwise, merge and return.
         */
        if (!insert) {
                while (type->cnt + nr_new > type->max)
                        if (memblock_double_array(type, obase, size) < 0)
                                return -ENOMEM;
                insert = true;
                goto repeat;
        } else {
                memblock_merge_regions(type);
                return 0;
        }
}

이 함수에서는 요청받은 인자를 사용하여 새로운 memblock 영역을 추가하는데, 기존 memblock 영역들과 중복되는 곳은 중복되지 않게 사이사이에 끼워 넣고 마지막으로 인접 memblock과 경계가 붙어 있고 플래그 타입이 같은 memblock들을 merge한다. return 값은 항상 0이다.

• 코드 라인 15~23에서 memblock 영역이 비어 있다면 중복 체크 없이 첫 memblock 영역에 대한 설정을 하고 함수를 종료한다.
• 코드 라인 24에서 repeat 레이블을 통해 한 번 반복되는데, 첫 번째 수행을 first round라고 하고 다음번 수행을 second round라고 할 때 first round에서는 루프를 돌때 끼워 넣어야 할 memblock 수를 체크할 목적으로 카운터(nr_new)만 증가시킨다. second round에서는 루프를 돌며 실제로 memblock을 곳곳에 인접 memblock과 중복되지 않게 끼워 넣는다.
• 코드 라인 33~35에서 요청한 memblock 타입들에 대해 루프를 돈다.
• 코드 라인 37~38에서 new memblock 영역이 비교하는 memblock 영역의 하단에 위치하여 겹치지 않으므로 더이상 반복 루프를 진행할 필요가 없어서 루프를 빠져나간다.
  • 아래 그림의 (A)에 해당한다. 참고로 regions[] 배열은 base 주소 순으로 정렬되어 있다. regions[0]에 가장 하위의 base 주소가 위치한다.
• 코드 라인 39~40에서 new memblock 영역이 비교하는 memblock 영역의 상부에 위치하여 겹치지 않으므로 스킵하여 다음 memblock과 비교하도록 한다.
  • 아래 그림의 (B)에 해당한다.
• 코드 라인 45~55 new memblock 영역이 비교하는 memblock 영역과 겹치므로 요청한 new memblock을 이 위치에 끼워 넣는데, 그 영역은 비교하는 memblock 영역과 겹치지 않는 영역의 크기만큼으로 조절한다.
  • 아래 그림의 (C)에 해당한다.
• 코드 라인 57에서 base를 끼워 넣어야 할 때를 대비하여 끼워 넣을 memblock 영역의 시작 주소를 미리 설정해놓는다.
• 코드 라인 61~66에서 루프 종료 후 new memblock 영역의 끝부분이 상부로 돌출되어 남아 있다면 그 돌출된 부분만을 memblock으로 추가한다.
  • 아래 그림의 (D)에 해당한다.
• 코드 라인 75~80에서 first round의 경우 기존 memblock들과 끼워 넣을 memblock들의 합이 최대 관리 개수를 넘어가는 경우에 한해 memblock 영역의 엔트리 수를 두 배 더 크게 넓히기 위해 memblock_double_array( ) 함수를 호출한다. 이 때 충분한 엔트리 개 수가 준비될 때까지 반복한다.
• 코드 라인 81~84에서 second round에서 끼워 넣은 memblock들에 대해 주변 memblock들과 인접하고 flag 타입이 동일한 memblock들을 memblock_merge_regions( ) 함수를 사용하여 merge한다.

 

다음 그림은 요청한 메모리 영역을 추가하는 흐름을 보여준다

 

아래 그림에서 회색으로 6개의 기존 영역이 등록되어 있고, 하늘색으로 새로운 memblock을 6가지 케이스에 대해 추가할 때 region[0]부터 화살표 방향으로 비교하는 모습을 보여준다.

• 추가할 영역이 기존 memblock 영역과 겹치는 경우 일단 겹쳐지지 않는 영역으로 쪼개어 추가한 후 나중에 인접 블럭들끼리 최종 merge한다.
• insertion 수
  • memblock이 추가될 때 실제 insertion이 일어나는 개수
• merge 후 cnt 수
  • 추후 merge된 후 최종적으로 남게되는 memblock 수

 

memblock_insert_region()

mm/memblock.c

/**
 * memblock_insert_region - insert new memblock region
 * @type:       memblock type to insert into
 * @idx:        index for the insertion point
 * @base:       base address of the new region
 * @size:       size of the new region
 * @nid:        node id of the new region
 * @flags:      flags of the new region
 *
 * Insert new memblock region [@base,@base+@size) into @type at @idx.
 * @type must already have extra room to accomodate the new region.
 */

static void __init_memblock memblock_insert_region(struct memblock_type *type,
                                                   int idx, phys_addr_t base,
                                                   phys_addr_t size,
                                                   int nid, 
                                                   enum memblock_flags flags)
{
        struct memblock_region *rgn = &type->regions[idx];

        BUG_ON(type->cnt >= type->max);
        memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
        rgn->base = base;
        rgn->size = size;
        rgn->flags = flags;
        memblock_set_region_node(rgn, nid);
        type->cnt++;
        type->total_size += size;
}

new 영역을 지정된 타입의 지정된 index memblock 위치에 끼워(insert) 넣는다. memblock_type 구조체의 필드 cnt와 total_size에는 카운터를 증가시키고 증가된 size도 더한다.

• 코드 라인 10에서 지정된 index의 memblock부터 마지막 memblock까지 한 칸씩 뒤로 복사한다.
• 코드 라인 11~14에서 멀티 노드를 지원하기 위해 노드 id를 지정한다.
• 코드 라인 15~16에서 memblock 타입 정보에는 카운터를 증가 시키고 증가된 size도 더한다.

 

memblock 배열 확장

memblock_double_array()

memblock이 위치한 배열이 작아서 확장이 필요할 때 호출되면 두 배로 키울 수 있다. 다음 코드를 통해 memblock_double_array( ) 함수를 분석해보자.

mm/memblock.c -1/2-

/**
 * memblock_double_array - double the size of the memblock regions array
 * @type: memblock type of the regions array being doubled
 * @new_area_start: starting address of memory range to avoid overlap with
 * @new_area_size: size of memory range to avoid overlap with
 *
 * Double the size of the @type regions array. If memblock is being used to
 * allocate memory for a new reserved regions array and there is a previously
 * allocated memory range [@new_area_start, @new_area_start + @new_area_size]
 * waiting to be reserved, ensure the memory used by the new array does
 * not overlap.
 *
 * Return:
 * 0 on success, -1 on failure.
 */

static int __init_memblock memblock_double_array(struct memblock_type *type,
                                                phys_addr_t new_area_start,
                                                phys_addr_t new_area_size)
{
        struct memblock_region *new_array, *old_array;
        phys_addr_t old_alloc_size, new_alloc_size;
        phys_addr_t old_size, new_size, addr, new_end;
        int use_slab = slab_is_available();
        int *in_slab;

        /* We don't allow resizing until we know about the reserved regions
         * of memory that aren't suitable for allocation
         */
        if (!memblock_can_resize)
                return -1;

        /* Calculate new doubled size */
        old_size = type->max * sizeof(struct memblock_region);
        new_size = old_size << 1;
        /*
         * We need to allocated new one align to PAGE_SIZE,
         *   so we can free them completely later.
         */
        old_alloc_size = PAGE_ALIGN(old_size);
        new_alloc_size = PAGE_ALIGN(new_size);

        /* Retrieve the slab flag */
        if (type == &memblock.memory)
                in_slab = &memblock_memory_in_slab;
        else
                in_slab = &memblock_reserved_in_slab;

        /* Try to find some space for it. */
        if (use_slab) {
                new_array = kmalloc(new_size, GFP_KERNEL);
                addr = new_array ? __pa(new_array) : 0;
        } else {
                /* only exclude range when trying to double reserved.regions */
                if (type != &memblock.reserved)
                        new_area_start = new_area_size = 0;

                addr = memblock_find_in_range(new_area_start + new_area_size,
                                                memblock.current_limit,
                                                new_alloc_size, PAGE_SIZE);
                if (!addr && new_area_size)
                        addr = memblock_find_in_range(0,
                                min(new_area_start, memblock.current_limit),
                                new_alloc_size, PAGE_SIZE);

                new_array = addr ? __va(addr) : NULL;
        }

• 코드 라인 14~15에서 memblock_allow_resize( )가 호출되어 memblock_can_resize 전역 변수가 1로 설정된 후에만 이 함수가 동작하도록 제한한다.
  • 커널 이미지와 메모리 영역이 매핑 완료되고, arm64_memblock_init() 루틴이 수행되어 memblock이 사용될 준비가 되면 다음 함수 호출 경로에서 사용된다.
    • setup_arch() -> paging_init()의 마지막에서 -> memblock_allow_resize()이 호출된다.
• 코드 라인 18~25에서 새로 관리할 영역을 기존 관리 영역보다 두 배 큰 크기로 할당받을 준비를 한다.
• 코드 라인 28~31에서 기존 memblock 관리 맵이 static이나 memblock에서 할당받은 것이 아니라 이미 슬랩(slab)으로 전환하여 운영되고 있는 중인지 여부를 확인한다.
• 코드 라인 34~36에서 정규 메모리 할당자인 슬랩을 사용할 수 있는 단계에서 kmalloc( )으로 메모리를 할당받는다.
• 코드 라인 37~40에서 슬랩을 사용하지 못하는 경우 memblock_add( ) 함수에서 사용 요청한 영역을 피해 memblock_find_in_range( )로 새로 만들 관리 영역을 사용할 수 있는 공간을 찾아온다. 요청 타입이 reserved 타입이 아닌 경우, 즉 memory 타입인 경우에는 할당 영역 검색을 0부터 시작하게 한다.
  • 메모리 타입을 등록하는 중에 관리 영역이 확장되는 경우, 새로 할당받아야 하는 영역은 그 전에 등록한 모든 메모리 영역 내에서 빈자리를 검색하면 된다. 어차피 새로 추가될 메모리 공간은 기존 메모리 공간과 간섭이 없는 영역일 것이다. 우선, 새로 관리 영역을 할당받을 공간은 추가 요청 영역을 피해야 하므로 요청 영역의 상부를 먼저 검색한다.
• 코드 라인 42~48에서 만일 첫 번째 검색에서 할당받지 못했거나 요청 타입이 reserved인 경우에 추가 요청 영역을 피해 하부를 검색한다.

 

mm/memblock.c -2/2-

        if (!addr) {
                pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
                       type->name, type->max, type->max * 2);
                return -1;
        }

        new_end = addr + new_size - 1;
        memblock_dbg("memblock: %s is doubled to %ld at [%pa-%pa]",
                        type->name, type->max * 2, &addr, &new_end);

        /*
         * Found space, we now need to move the array over before we add the
         * reserved region since it may be our reserved array itself that is
         * full.
         */
        memcpy(new_array, type->regions, old_size);
        memset(new_array + type->max, 0, old_size);
        old_array = type->regions;
        type->regions = new_array;
        type->max <<= 1;

        /* Free old array. We needn't free it if the array is the static one */
        if (*in_slab)
                kfree(old_array);
        else if (old_array != memblock_memory_init_regions &&
                 old_array != memblock_reserved_init_regions)
                memblock_free(__pa(old_array), old_alloc_size);

        /*
         * Reserve the new array if that comes from the memblock.  Otherwise, we
         * needn't do it
         */
        if (!use_slab)
                BUG_ON(memblock_reserve(addr, new_alloc_size));

        /* Update slab flag */
        *in_slab = use_slab;

        return 0;
}

• 코드 라인 16~20에서 새로 할당받은 관리 영역 시작 주소에 기존 memblock 영역들을 모두 복사하고 복사되지 않은 빈 곳은 0으로 초기화한다. 또한 max를 기존 값의 두 배로 변경한다.
• 코드 라인 23~27에서 확장하기 전의 기존 관리 영역을 해제한다. 초기 관리 영역은 컴파일 타임에 선언된 배열 변수 영역에 있으므로 삭제할 수 없어서 그냥 버린다. 삭제할 관리 영역이 초기 영역이 아니면 다음과 같이 할당자 종류에 따라 처리한다.
  • 기존에 슬랩을 사용 중이었으면 kfree( )로 기존 영역을 해제한다.
  • 슬랩을 사용하지 않았다면 memblock_free( )로 기존 영역을 해제한다.

 

memblock_allow_resize()

mm/memblock.c

void __init memblock_allow_resize(void)
{
        memblock_can_resize = 1;
}

memblock 영역이 필요 시 확장이 가능하도록 1을 대입한다.

 

memblock 병합

memblock_merge_regions()

mm/memblock.c

/**
 * memblock_merge_regions - merge neighboring compatible regions
 * @type: memblock type to scan
 *
 * Scan @type and merge neighboring compatible regions.
 */

static void __init_memblock memblock_merge_regions(struct memblock_type *type)
{
        int i = 0;

        /* cnt never goes below 1 */
        while (i < type->cnt - 1) {
                struct memblock_region *this = &type->regions[i];
                struct memblock_region *next = &type->regions[i + 1];

                if (this->base + this->size != next->base ||
                    memblock_get_region_node(this) !=
                    memblock_get_region_node(next) ||
                    this->flags != next->flags) {
                        BUG_ON(this->base + this->size > next->base);
                        i++;
                        continue;
                }

                this->size += next->size;
                /* move forward from next + 1, index of which is i + 2 */
                memmove(next, next + 1, (type->cnt - (i + 2)) * sizeof(*next));
                type->cnt--;
        }
}

인접 메모리 블록이 같은 플래그 타입을 사용하는 경우 병합한다

• 코드 라인 6~8에서 요청 memblock 타입의 개수만큼 거꾸로 감소시키며 루프를 돈다.
• 코드 라인 10~17에서 경계가 붙어 있지 않거나 두 memblock 간의 flag 상태가 다른 경우 memblock을 합치지 않고 스킵한다.
• 코드 라인 19~22에서 경계가 붙어 있다면 memblock을 합친다. 참고로 병합이 된 경우 다시 한 번 다음 블럭과 비교하기 위해 regions[] 배열을 지정하는 인덱스 i 값은 증가시키지 않는다.

 

memblock_cap_size()

mm/memblock.c

/* adjust *@size so that (@base + *@size) doesn't overflow, return new size */
static inline phys_addr_t memblock_cap_size(phys_addr_t base, phys_addr_t *size)
{
        return *size = min(*size, PHYS_ADDR_MAX - base);
}

영역이 unsigned long 값을 넘어가는 경우(overflow) 넘친 부분을 잘라낸다.

• • 64bit: min(0xffff_ffff_ffff_ffff – base, size)
  • 32bit: min(0xffff_ffff – base, size)
• 영역이 넘치는 경우 사이즈가 재계산되는데 사이즈가 1만큼 작아져 시스템의 마지막 주소 바이트를 사용할 수 없게된다.
  • 예) 32bit: base=0xffff_0000, size=0xffff -> size=0xffff (이건 정상)
  • 예) 32bit: base=0xffff_0000, size=0x10000 -> size=0xffff (1이 작아져서 0xffff_ffff 주소는 사용불가능)

 

memblock 삭제

다음 그림은 memblock_remove() 함수의 호출 관계이다.

 

memblock_remove()

mm/memblock.c

int __init_memblock memblock_remove(phys_addr_t base, phys_addr_t size)
{
        phys_addr_t end = base + size - 1;

        memblock_dbg("%s: [%pa-%pa] %pS\n", __func__,
                     &base, &end, (void *)_RET_IP_);

        return memblock_remove_range(&memblock.memory, base, size);
}

물리 메모리 주소 @base 부터 @size 만큼을 memory 타입 memblock 영역에서 제거한다.

 

memblock_free()

mm/memblock.c

/**
 * memblock_free - free boot memory block
 * @base: phys starting address of the  boot memory block
 * @size: size of the boot memory block in bytes
 *
 * Free boot memory block previously allocated by memblock_alloc_xx() API.
 * The freeing memory will not be released to the buddy allocator.
 */

int __init_memblock memblock_free(phys_addr_t base, phys_addr_t size)
{
        phys_addr_t end = base + size - 1;

        memblock_dbg("%s: [%pa-%pa] %pS\n", __func__,
                     &base, &end, (void *)_RET_IP_);

        kmemleak_free_part_phys(base, size);
        return memblock_remove_range(&memblock.reserved, base, size);
}

물리 메모리 주소 @base 부터 @size 만큼을 reserved 타입 memblock 영역에서 제거한다.

 

memblock_remove_range()

mm/memblock.c

static int __init_memblock memblock_remove_range(struct memblock_type *type,
                                          phys_addr_t base, phys_addr_t size)
{
        int start_rgn, end_rgn;
        int i, ret;

        ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
        if (ret)
                return ret;

        for (i = end_rgn - 1; i >= start_rgn; i--)
                memblock_remove_region(type, i);
        return 0;
}

요청한 @type의 memblock에서 물리 주소 @base 부터 @size까지 영역을 제거한다.

• 코드 라인 7~9에서 제거할 영역의 시작과 끝 주소를 기준으로 memblock을 분리한다.
• 코드 라인 11~12에서 제거할 영역에 해당하는 memblock 영역을 삭제한다.

 

memblock_remove_region()

mm/memblock.c

static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
{
        type->total_size -= type->regions[r].size;
        memmove(&type->regions[r], &type->regions[r + 1],
                (type->cnt - (r + 1)) * sizeof(type->regions[r]));
        type->cnt--;

        /* Special case for empty arrays */
        if (type->cnt == 0) {
                WARN_ON(type->total_size != 0);
                type->cnt = 1;
                type->regions[0].base = 0;
                type->regions[0].size = 0;
                type->regions[0].flags = 0;
                memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
        }
}

요청한 @type의 memblock에서 인덱스 r에 해당하는 memblock을 삭제한다. 상위 memblock들이 삭제한 위치로 이동해온다.

 

다음 그림은 4개의 memblock 영역이 있고 그 중 노란색의 remove 범위를 삭제하면 변경되는 memblock 영역을 보여준다.

 

memblock 분리

다음 그림은 memblock_ioslate_range() 함수가 처리되는 과정을 보여준다.

 

memblock_isolate_range()

mm/memblock.c

/**
 * memblock_isolate_range - isolate given range into disjoint memblocks
 * @type: memblock type to isolate range for
 * @base: base of range to isolate
 * @size: size of range to isolate
 * @start_rgn: out parameter for the start of isolated region
 * @end_rgn: out parameter for the end of isolated region
 *
 * Walk @type and ensure that regions don't cross the boundaries defined by
 * [@base, @base + @size).  Crossing regions are split at the boundaries,
 * which may create at most two more regions.  The index of the first
 * region inside the range is returned in *@start_rgn and end in *@end_rgn.
 *
 * Return:
 * 0 on success, -errno on failure.
 */

static int __init_memblock memblock_isolate_range(struct memblock_type *type,
                                        phys_addr_t base, phys_addr_t size,
                                        int *start_rgn, int *end_rgn)
{
        phys_addr_t end = base + memblock_cap_size(base, &size);
        int idx;
        struct memblock_region *rgn;

        *start_rgn = *end_rgn = 0;

        if (!size)
                return 0;

        /* we'll create at most two more regions */
        while (type->cnt + 2 > type->max)
                if (memblock_double_array(type, base, size) < 0)
                        return -ENOMEM;

        for_each_memblock_type(idx, type, rgn) {
                phys_addr_t rbase = rgn->base;
                phys_addr_t rend = rbase + rgn->size;

                if (rbase >= end)
                        break;
                if (rend <= base)
                        continue;

                if (rbase < base) {
                        /*
                         * @rgn intersects from below.  Split and continue
                         * to process the next region - the new top half.
                         */
                        rgn->base = base;
                        rgn->size -= base - rbase;
                        type->total_size -= base - rbase;
                        memblock_insert_region(type, idx, rbase, base - rbase,
                                               memblock_get_region_node(rgn),
                                               rgn->flags);
                } else if (rend > end) {
                        /*
                         * @rgn intersects from above.  Split and redo the
                         * current region - the new bottom half.
                         */
                        rgn->base = end;
                        rgn->size -= end - rbase;
                        type->total_size -= end - rbase;
                        memblock_insert_region(type, idx--, rbase, end - rbase,
                                               memblock_get_region_node(rgn),
                                               rgn->flags);
                } else {
                        /* @rgn is fully contained, record it */
                        if (!*end_rgn)
                                *start_rgn = idx;
                        *end_rgn = idx + 1;
                }
        }

        return 0;
}

요청 영역의 상단과 하단 라인에 겹치는 memblock에서 영역을 분리한다. 분리된 memblock 시작 인덱스가 출력 인자의 @start_rgn에 저장되고 끝 인덱스 + 1 값이 출력 인자 @end_rgn에 저장된다. 만일 분리한 memblock 항목이 없으면 두 출력 인자에 0이 저장된다.

• 코드 라인 5에서 영역의 끝 물리 주소는 아키텍처가 지원하는 물리 주소의 끝을 초과하지 않도록 제한한다.
• 코드 라인 15~17에서 해당 타입의 최대 개수를 사용하려 할 때 관리 배열을 두 배로 확장한다. 확장이 불가능하면 메모리가 부족하다는 -ENOMEM을 리턴한다.
• 코드 라인 19~21에서 첫 memblock 영역부터 마지막 영역에 대해 루프를 돌며 rbase와 rend에는 해당 루프 인덱스의 memblock 시작 주소와 끝 주소가 담긴다.
• 코드 라인 23~24에서 현재 인덱스 영역의 시작 주소가 주어진 영역의 상단보다 크거나 같은 경우 더는 상위 인덱스 memblock에서 처리할 필요가 없으므로 루프를 빠져나가게 한다.  (아래 그림의 A 조건)
• 코드 라인 25~26에서 현재 인덱스 영역의 끝 주소가 주어진 영역의 상단보다 같거나 큰 경우 아직 겹쳐지는 영역이 아니므로 다음 인덱스 memblock을 처리하기 위해 스킵한다. (아래 그림의 B 조건)
• 코드 라인 28~38에서 현재 인덱스 영역의 시작 주소가 주어진 영역의 시작 주소보다 작은 경우, 즉 주어진 영역의 시작 주소가 현재 인덱스 memblock과 겹친 경우 다음과 같이 처리한다. (아래 그림의 C 조건)
  • 현재 인덱스 memblock을 하단의 겹친 라인을 기점으로 상부로 영역을 옮긴다. 또한 인덱스 memblock의 하단 겹친 라인을 기점으로 새롭게 하부에 memblock을 insert한다.
• 코드 라인 39~49에서 현재 인덱스 영역의 끝 주소가 주어진 영역의 끝 주소보다 큰 경우, 즉 주어진 영역의 끝 주소가 현재 인덱스 memblock과 겹친 경우 다음과 같이 처리한다. (아래 그림의 D 조건)
  • 현재 인덱스 memblock을 상단의 겹친 라인을 기점으로 상부로 영역을 옮긴다. 또한 인덱스 memblock의 상단에 겹친 라인을 기점으로 새롭게 하부에 memblock을 삽입한다.
• 코드 라인 50~55에서 어떠한 조건에도 걸리지 않은 경우로, 현재 인덱스 영역이 주어진 영역에 포함된 경우다. 이때는 start_rgn에 현재 인덱스 값을 지정하고, end_rgn에는 현재 인덱스 값 + 1을 지정한다.

 

다음 그림은 회색으로 표시된 6개의 memblock 영역이 있는 상황에서 6개 각각 하늘색의 isolation 영역이 주어졌을 때 region[0]부터 화살표 방향으로 비교하는 모습을 보여준다.

• 분리할 영역이 기존 memblock 영역과 겹치는 경우 겹쳐지는 부분은 memblock을 나눈다. 그리고 memblock이 없는 부분은 추가한다.
• insertion
  • memblock이 추가될 때 실제 insertion이 일어나는 개수를 표시하였다.
• start_rgn
  • isolation 범위의 시작이 겹치는 기존 memblock 영역의 인덱스 번호
• end_rgn
  • isolation 범위의 끝이 겹치는 기존 memblock 영역의 인덱스 번호 + 1

 

다음 그림은 위 그림 6개 예제의 첫 번째 부분을 조금 더 자세하게 표현하였다.

• (C) 및 (D) case에서 insert를 하는 경우 처리 중인 idx 영역을 위로 밀어내고 추가한다.
• (D) case를 진행하는 경우 idx에 해당하는 영역을 다시 한 번 진행하는 것에 주의한다.

 

다음 그림은 위 그림 6개 예제의 세 번째 부분을 조금 더 자세하게 표현하였다.

 

참고

• Memblock – (1) | 문c – 현재 글
• Memblock – (2) | 문c
• arm_memblock_init() | 문c
• arm64_memblock_init() | 문c

 

• mm: Use memblock interface instead of bootmem | LWN.net