Memblock – (2)

Early Memory Allocation

 

memblock_alloc()

  • memory memblock에 등록된 영역중에서 reserved memblock 영역을 제외한 공간중에서 size 만큼 영역을 할당한다.
  • memblock allocation은 buddy등의 memory allocator가 활성화되기 전까지 사용할 수 있는 수단으로 커널에서 early memory allocator로 자리잡았다.
  • 요청 영역의 사이즈는 지정된 align 바이트만큼 정렬(align) 된다.
    • align 조정된 사이즈만큼 크기가 작아질 수 있다.
  • free 메모리 할당받는 방향에 따라 align 방향이 결정된다.
    • bottom up인 경우 메모리 할당을 아래에서 부터 위로 할당하여야 하므로 영역의 align은 round down 되어야 한다.
    • top down인 경우 메모리 할당을 위에서 부터 아래로 할당하여야 하므로 영역의 align은 round up 되어야 한다.
      • ARM은 cpu hotplug 기능이 적용되지 않았고, 따라서 모든 노드가 non-movable 속성이다. 이에 항상 top down 방식을 사용한다.

memblock-9b

mm/memblock.c

phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
{
        return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
}

 

memblock_alloc_base()

phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr) 
{
        phys_addr_t alloc;

        alloc = __memblock_alloc_base(size, align, max_addr);

        if (alloc == 0)
                panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
                      (unsigned long long) size, (unsigned long long) max_addr);

        return alloc;
}

 

__memblock_alloc_base()

  • NUMA_NO_NODE: 노드 영역에 관계 없이 할당한다.
phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr) 
{
        return memblock_alloc_base_nid(size, align, max_addr, NUMA_NO_NODE);
}

 

memblock_alloc_base_nid()

static phys_addr_t __init memblock_alloc_base_nid(phys_addr_t size,
                                        phys_addr_t align, phys_addr_t max_addr,
                                        int nid)
{
        return memblock_alloc_range_nid(size, align, 0, max_addr, nid);
}

 

memblock_alloc_range_nid()

  • memblock_find_in_range_node()
    • 주어진 범위내에서 free 영역을 찾는다.
  • memblock_reserve()
    • 해당 영역을 reserve한다.
  • kmemleak_alloc()
    • register a newly allocated object

mm/memblock.c

static phys_addr_t __init memblock_alloc_range_nid(phys_addr_t size,
                                        phys_addr_t align, phys_addr_t start,
                                        phys_addr_t end, int nid)
{
        phys_addr_t found;

        if (!align)
                align = SMP_CACHE_BYTES;

        found = memblock_find_in_range_node(size, align, start, end, nid);
        if (found && !memblock_reserve(found, size)) {
                /*
                 * The min_count is set to 0 so that memblock allocations are
                 * never reported as leaks.
                 */
                kmemleak_alloc(__va(found), size, 0, 0);
                return found;
        }
        return 0;
}

 

memblock_reserve()

  • reserved 영역에 주어진 범위를 추가한다.
int __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
{
        return memblock_reserve_region(base, size, MAX_NUMNODES, 0);
}

 

memblock_reserve_region()

static int __init_memblock memblock_reserve_region(phys_addr_t base,
                                                   phys_addr_t size,
                                                   int nid,
                                                   unsigned long flags)
{
        struct memblock_type *_rgn = &memblock.reserved;

        memblock_dbg("memblock_reserve: [%#016llx-%#016llx] flags %#02lx %pF\n",                     (unsigned long long)base,
                     (unsigned long long)base + size - 1,
                     flags, (void *)_RET_IP_);

        return memblock_add_range(_rgn, base, size, nid, flags);
}

 

memblock_find_in_range()

  • 커널 버전 3.13-rc1부터 bottom up 메모리 할당 기능이 추가되었다.
  • 기존 버전의 커널은 항상 메모리 할당을 top down으로 free 영역을 검색하여 할당하였었다.
  • 리눅스에 메모리 hotplug 기능이 추가되면서 메모리 노드에 movable 속성 필드가 새롭게 생겨났다.
  • movable 가능한 노드들은 hotplug 기능으로 인해 탈착 기능을 수행하는 동안 해당 노드 전체의 사용중인 페이지들이 다른 노드로 이주(migration)를 하게 하는 코드가 추가되었다.
  • 커널과 커널이 사용하는 메모리는 hotplug 기능을 지원하지 않는 노드에 설치가 되며 이 노드는 항상 non-movable 속성을 갖는다.
  • 현재 x86 64비트 대용량 서버들이 hotplug 기능을 지원하는데 이러한 노드들은 최소 16G 용량씩을 가지고 보통 커널이미지가 있는 non-moveable 속성의 노드의 위쪽으로 떨어져 있다. 이러한 조건에서 커널이 메모리를 할당하게 되면 메모리의 최 상단 movable 노드부터 할당을 하게된다. 이러한 경우 moveable 노드를 탈착하게 되면 그 동안 할당하여 사용한 많은 메모리들이 movable 노드에서 대량으로 다른 노드로 이주(migration)이 되어야 하는 경우가 발생한다.
  • hotplug 기능으로 인하여 데이터 페이지의 이주가 발생하는 빈도를 낮추기 위해 메모리 할당을 bottom up으로(낮은 주소부터 높은 주소 방향으로) 할당할 수 있는 기능이 필요하게 되었고 커널이 있는 곳에서 즉, 커널의 끝(_end)부터 상단으로 메모리 할당이 가능할 수 있도록 코드가 추가되었다. 이렇게 하여 할당된 메모리는 커널이 있는 non-movable 노드에 같이 있게될 확률이 매우 높다.
  • ARM 아키텍처는 현재(커널 v4.4)까지 CPU hotplug 기능과는 달리 메모리 hotplug 기능이 적용되지 않았다. 따라서 메모리 할당은 top down 방식 을 사용한다.
    • CONFIG_MEMORY_HOTPLUG, CONFIG_HOTPLUG_CPU
  • 참고: mm/memblock.c: introduce bottom-up allocation mode

memblock4

 

__memblock_find_range_top_down()
/**
 * __memblock_find_range_top_down - find free area utility, in top-down
 * @start: start of candidate range
 * @end: end of candidate range, can be %MEMBLOCK_ALLOC_{ANYWHERE|ACCESSIBLE}
 * @size: size of free area to find
 * @align: alignment of free area to find
 * @nid: nid of the free area to find, %NUMA_NO_NODE for any node
 *
 * Utility called from memblock_find_in_range_node(), find free area top-down.
 *
 * RETURNS:
 * Found address on success, 0 on failure.
 */
static phys_addr_t __init_memblock
__memblock_find_range_top_down(phys_addr_t start, phys_addr_t end,
                               phys_addr_t size, phys_addr_t align, int nid)
{
        phys_addr_t this_start, this_end, cand;
        u64 i;

        for_each_free_mem_range_reverse(i, nid, &this_start, &this_end, NULL) {

                this_start = clamp(this_start, start, end);
                this_end = clamp(this_end, start, end);

                if (this_end < size)
                        continue;

                cand = round_down(this_end - size, align);
                if (cand >= this_start)
                        return cand;
        }

        return 0;
}
  • for_each_free_mem_range_reverse()를 사용하여 free 공간을 루프를 돌며 하나씩 알아온다.
  • if (this_end < size) continue;
    • 알아온 free 영역의 끝 주소가 사이즈보다 작으면 next
      this_end – size를 하여 마이너스 값이 나오면서 오류(원하지 않는 round_down 값)가 나올 수 있으므로 이를 방지
  • cand = round_down(this_end – size, align)
    • 요청 사이즈의 비교는 align된 크기로 한다.
  • if (cand >= this_start) return cand;
    • 알아온 free 영역의 범위에 size가 포함될 수 있으면 성공적으로 cand 주소를 리턴한다.

아래의 그림에서 for_each_free_mem_range_reverse()를 통해 7개의 free 공간이 얻어지며, start 에서 end까지의 범위에 포함되는 케이스가 4개로 압축이 되고 1번 부터 4번 까지 우선 순위로 요청 사이즈가 포함될 수 있는 경우 이 공간의 주소를 리턴한다.

__memblock_find_range_top_down-1b

 

for_each_memblock()

  • 지정한 타입의 memblock 영역 전체를 처음부터 끝까지 loop를 돌며 region 변수에 각각의 memblock 구조체 포인터 값을 담는다.

include/linux/memblock.h

#define for_each_memblock(memblock_type, region)                \
        for (region = memblock.memblock_type.regions;           \
             region < (memblock.memblock_type.regions + 	\
	     memblock.memblock_type.cnt); 			\
             region++)

 

동작 과정)
struct memblock_region *r;
for_each_memblock(reserved, r)
{
	print_info(“base=0x%x, size=0x%x\n”, r.base, r.size);
}

 

  • reserved 영역이 아래와 같이 4개가 있을 때 r 값은 가장 하단의 memblock region부터 최상단 memblock region까지 반복하여 memblock_region 구조체 포인터를 지정한다.

memblock10

for_each_mem_pfn_range()

include/linux/memblock.h

/**
 * for_each_mem_pfn_range - early memory pfn range iterator
 * @i: an integer used as loop variable
 * @nid: node selector, %MAX_NUMNODES for all nodes
 * @p_start: ptr to ulong for start pfn of the range, can be %NULL
 * @p_end: ptr to ulong for end pfn of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 *
 * Walks over configured memory ranges.
 */
#define for_each_mem_pfn_range(i, nid, p_start, p_end, p_nid)           \
        for (i = -1, __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid); \
             i >= 0; __next_mem_pfn_range(&i, nid, p_start, p_end, p_nid))
  • 노드 번호에 해당하는 memory memblock가 파편화된 페이지를 제외한 즉 온전한 페이지가 1개 이상인 경우의 시작 pfn과 끝 pfn 값을 루프를 돌며 하나씩 알아온다.

아래의 그림은 nid=1 값으로 for_each_mem_pfn_range() 매크로 루프를 동작시킬 때 조건에 매치되는 경우를 붉은 박스로 표현하였고 각각의 값은 다음과 같다.

  • 다음과 같이 2번의 매치 건이 발생한다.
    • i 값이 1로 p_start=3, p_end=3, p_nid=1을 얻어온다.
    • i값이 2로 p_start=5, p_end=7, p_nid=1을 얻어온다.
  • 실제 memory memblock 들은 아래 그림과 다르게 매우 큰 페이지들로 이루어졌고 거의 대부분 align 된 상태이므로 아래 그림과는 많이 다르지만 계산 방법에 대해 이해를 돕는 것으로 활용해야 한다.

for_each_mem_pfn_range-1a

 

__next_mem_pfn_range()

mm/memblock.c

/*
 * Common iterator interface used to define for_each_mem_range().
 */                         
void __init_memblock __next_mem_pfn_range(int *idx, int nid,
                                unsigned long *out_start_pfn,
                                unsigned long *out_end_pfn, int *out_nid)
{
        struct memblock_type *type = &memblock.memory;
        struct memblock_region *r;

        while (++*idx < type->cnt) {
                r = &type->regions[*idx];

                if (PFN_UP(r->base) >= PFN_DOWN(r->base + r->size))
                        continue;
                if (nid == MAX_NUMNODES || nid == r->nid)
                        break;
        }
        if (*idx >= type->cnt) {
                *idx = -1;
                return;
        }

        if (out_start_pfn)
                *out_start_pfn = PFN_UP(r->base);
        if (out_end_pfn)
                *out_end_pfn = PFN_DOWN(r->base + r->size);
        if (out_nid)
                *out_nid = r->nid;
}
  • while (++*idx < type->cnt) {
    • 증가시킨 인덱스가 memory memblock 수 보다 작은동안 루프를 돈다.
  • if (PFN_UP(r->base) >= PFN_DOWN(r->base + r->size))
    • memblock 영역안에 온전한 1개 이상의 4K 페이지가 포함되지 않은 경우 다음 memblock을 위해 continue를 수행하고 포함된 경우
  • if (nid == MAX_NUMNODES || nid == r->nid)
    • 요청 노드 번호와 매치가 되거나 MAX_NUMNODES인 경우 루프를 탈출한다.
  • if (*idx >= type->cnt) {
    • 루프가 끝날 때까지 매치되지 않았으면 idx에 -1을 담고 리턴한다.
  • if (out_start_pfn) *out_start_pfn = PFN_UP(r->base);
    • out_start_pfn이 null이 아니면 out_start_pfn에 4K 페이지가 파편화되지 않고 온전히 포함된 시작 페이지 번호를 담는다.
  • if (out_end_pfn) *out_end_pfn = PFN_DOWN(r->base + r->size);
    • out_end_pfn이 null이 아니면 out_end_pfn에 4K 페이지가 파편화되지 않고 온전히 포함된 끝 페이지 번호를 담는다.
  • if (out_nid) *out_nid = r->nid;
    • out_nid가 null이 아니면 out_nid에 memblock의 nid 값을 담는다.

아래 그림은 7개의 case 별로 __next_mem_pfn_range() 함수가 실행될 때 출력되는 인수에 대해 표현하였다.

  • 아래 그림 역시도 실제 memory memblock 들의 사이즈보다 훨씬 축소를 해놨기 때문에 계산 방법에 대해 이해를 돕는 것으로 활용해야 한다

__next_mem_pfn_range-1a

 

for_each_free_mem_range()

  • 루프를 돌며 지정된 노드 id의 memory 영역에서 reserved 영역을 제외한 영역이 free 메모리이며 이 영역을 순서대로 p_start, p_end, p_nid 인수에 지정한다.

include/linux/memblock.h

/**
 * for_each_free_mem_range - iterate through free memblock areas
 * @i: u64 used as loop variable
 * @nid: node selector, %NUMA_NO_NODE for all nodes
 * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 *
 * Walks over free (memory && !reserved) areas of memblock.  Available as
 * soon as memblock is initialized.
 */
#define for_each_free_mem_range(i, nid, p_start, p_end, p_nid)          \
        for_each_mem_range(i, &memblock.memory, &memblock.reserved,     \
                           nid, p_start, p_end, p_nid)

 

for_each_mem_range()

  • 루프를 돌며 지정된 노드 id의 A 타입 영역에서 B 타입 영역을 제외한 영역이 주어질 때 이 영역을 순서대로 p_start, p_end, p_nid 인수에 지정한다.
  • B 타입 영역이 null일 수도 있다.

include/linux/memblock.h

/**
 * for_each_mem_range - iterate through memblock areas from type_a and not
 * included in type_b. Or just type_a if type_b is NULL.
 * @i: u64 used as loop variable
 * @type_a: ptr to memblock_type to iterate
 * @type_b: ptr to memblock_type which excludes from the iteration
 * @nid: node selector, %NUMA_NO_NODE for all nodes
 * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 */
#define for_each_mem_range(i, type_a, type_b, nid,                      \
                           p_start, p_end, p_nid)                       \
        for (i = 0, __next_mem_range(&i, nid, type_a, type_b,           \
                                     p_start, p_end, p_nid);            \
             i != (u64)ULLONG_MAX;                                      \
             __next_mem_range(&i, nid, type_a, type_b,                  \
                              p_start, p_end, p_nid))

 

  • 아래와 같이 memory 영역내에서 reserved 영역을 제외한 영역이 free 영역이고 2개의 영역이 루프로 제공된다.

memblock11

 

__next_mem_range()

mm/memblock.c

/**
 * __next__mem_range - next function for for_each_free_mem_range() etc.
 * @idx: pointer to u64 loop variable
 * @nid: node selector, %NUMA_NO_NODE for all nodes
 * @type_a: pointer to memblock_type from where the range is taken
 * @type_b: pointer to memblock_type which excludes memory from being taken
 * @out_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @out_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @out_nid: ptr to int for nid of the range, can be %NULL
 *
 * Find the first area from *@idx which matches @nid, fill the out
 * parameters, and update *@idx for the next iteration.  The lower 32bit of
 * *@idx contains index into type_a and the upper 32bit indexes the
 * areas before each region in type_b.  For example, if type_b regions
 * look like the following,
 *
 *      0:[0-16), 1:[32-48), 2:[128-130)
 *
 * The upper 32bit indexes the following regions.
 *
 *      0:[0-0), 1:[16-32), 2:[48-128), 3:[130-MAX)
 *
 * As both region arrays are sorted, the function advances the two indices
 * in lockstep and returns each intersection.
 */
void __init_memblock __next_mem_range(u64 *idx, int nid,
                                      struct memblock_type *type_a,
                                      struct memblock_type *type_b,
                                      phys_addr_t *out_start,
                                      phys_addr_t *out_end, int *out_nid)

 

  • 노드 id 인수 값으로 deprecated된 MAX_NUMNODES를 사용하면 경고문을 출력한다.
  • type_a는 memory 타입, type_b는 reserved 타입으로 한다.
  • memory memblock에 대한 1차 루프는 idx_a가 등록된 갯수보다 작을 때까지 하나씩 증가한다.
  • m_start와 m_end는 현재 1차 루프 인덱스의 memblock 영역의 시작 주소와 끝 주소이다.
  • 주어진 nid가 NUMA_NO_NODE가 아니면서 해당 인덱스 memblock의 노드도 아니면 skip 한다.
  • 현재 1차 루프 인덱스의 memblock이 hotplug 영역으로(flag: bit0=MEMBLOCK_HOTPLUG)되어 있는 경우이면서 노드가 이동가능한 상태라면 이 영역을 배정하지 않도록 skip 한다.
{
        int idx_a = *idx & 0xffffffff;
        int idx_b = *idx >> 32;

        if (WARN_ONCE(nid == MAX_NUMNODES,
        "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
                nid = NUMA_NO_NODE;

        for (; idx_a < type_a->cnt; idx_a++) {
                struct memblock_region *m = &type_a->regions[idx_a];

                phys_addr_t m_start = m->base;
                phys_addr_t m_end = m->base + m->size;
                int         m_nid = memblock_get_region_node(m);

                /* only memory regions are associated with nodes, check it */
                if (nid != NUMA_NO_NODE && nid != m_nid)
                        continue;

                /* skip hotpluggable memory regions if needed */
                if (movable_node_is_enabled() && memblock_is_hotpluggable(m))
                        continue;
  • type_b에 대한 영역이 지정되지 않으면(null) 현재 1차 루프 인덱스의 memblock에 대한 영역으로 out_start와 out_end를 결정하고 idx_a 만을 1 증가 시키고 함수를 성공리에 빠져나간다.
  • type_b에 대한 2차 루프는 idx_b가 등록된 갯수+1보다 작을때 까지 하나씩 증가한다.
  • r 영역은 현재 2차 루프 인덱스가 가리킨 곳의 영역을 가리킨다.
  • r_start는 idx_b가 0보다 크면 현재 이전 memblock의 끝 주소를 가리키고 idx_b가 0이면 0번 주소를 지정한다.
  • r_end는 idx_b가 등록된 갯수보다 작은 경우 r 영역의 시작주소를 지정하고 아니면 시스템 최대 주소를 지정한다.
                if (!type_b) {
                        if (out_start)
                                *out_start = m_start;
                        if (out_end)
                                *out_end = m_end;
                        if (out_nid)
                                *out_nid = m_nid;
                        idx_a++;
                        *idx = (u32)idx_a | (u64)idx_b << 32;
                        return;
                }

                /* scan areas before each reservation */
                for (; idx_b < type_b->cnt + 1; idx_b++) {
                        struct memblock_region *r;
                        phys_addr_t r_start;
                        phys_addr_t r_end;

                        r = &type_b->regions[idx_b];
                        r_start = idx_b ? r[-1].base + r[-1].size : 0;
                        r_end = idx_b < type_b->cnt ?
                                r->base : ULLONG_MAX;

 

  • 조건 A) r_start >= m_end
    • reserve memblock 영역이 memory memblock 영역을 벗어난 경우 2차 루프를 빠져나가서 다음 memory memblock을 준비하도록 한다.
  • 조건 B) m_start < r_end
    • 두 영역이 교차하는 경우이다.
    • out_start에 하단 reserve 영역값의 끝 주소나 memory 영역값의 시작 주소중 가장 큰 주소를 담는다.
    • out_end에 상단 reserve 영역값의 시작 주소나 memory 영역값의 끝 주소중에 가장 작은 주소를 담는다.
  • 조건 B-1) m_end < r_end
    • reserve 영역의 끝 주소가 memory 영역의 끝주소와 비교하여 큰 경우 idx_a를 증가시키고 다음 memory block을 준비하기 위해 빠져나가고, 크지 않은 경우 idx_b를 증가시키고 계속하여 다음 reserve 영역을 준비하기 위해 빠져나간다.
  • 1차 루프를 끝까지 완료하면 더 이상 처리할 수 없으므로 idx에 ULLONG_MAX(시스템 최대 주소) 값을 부여하고 빠져나간다.
                        /*
                         * if idx_b advanced past idx_a,
                         * break out to advance idx_a
                         */
                        if (r_start >= m_end)
                                break;
                        /* if the two regions intersect, we're done */
                        if (m_start < r_end) {
                                if (out_start)
                                        *out_start =
                                                max(m_start, r_start);
                                if (out_end)
                                        *out_end = min(m_end, r_end);
                                if (out_nid)
                                        *out_nid = m_nid;
                                /*
                                 * The region which ends first is
                                 * advanced for the next iteration.
                                 */
                                if (m_end <= r_end)
                                        idx_a++;
                                else
                                        idx_b++;
                                *idx = (u32)idx_a | (u64)idx_b << 32;
                                return;
                        }
                }
        }
        /* signal end of iteration */
        *idx = ULLONG_MAX;
}

 

memblock12

  • 아래 1개의 meory memblock과 2개의 reserve memblock가 등록되어 있는 상태에서 __next__mem_range(0x1UUL) 매크로를 사용한 경우의 예이다.
  • 루프 1의 idx_a 인덱스는 0으로 memory.regions[0]의 정보 사용
  • 루프 2의 idx_b 인덱스는 1로 reserve.regions[1]과 이전 reserve memblock의 영역 정보를 사용하는 중이다.
  • 확정된 free 영역으로 r_start는 reserve.regions[0]의 끝 주소로 지정되고 r_end는 reserve.regions[1]의 시작 주소로 지정된다.

memblock13

 

  • 아래 2개의 meory memblock과 4개의 reserve memblock이 등록되어 있는 상태에서 __next__mem_range(0x1UUL) 매크로를 사용하여 free 영역이 검색되는 범위를 표현한다.

memblock14a

 

for_each_free_mem_range_reverse()

  • 루프를 역순으로 돌며 지정된 노드 id의 memory 영역에서 reserved 영역을 제외한 영역이 free 메모리이며 이 영역을 순서대로 p_start, p_end, p_nid 인수에 지정한다.

mm/memblock.c

/**
 * for_each_free_mem_range_reverse - rev-iterate through free memblock areas
 * @i: u64 used as loop variable
 * @nid: node selector, %NUMA_NO_NODE for all nodes
 * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 *
 * Walks over free (memory && !reserved) areas of memblock in reverse
 * order.  Available as soon as memblock is initialized.
 */
#define for_each_free_mem_range_reverse(i, nid, p_start, p_end, p_nid)  \
        for_each_mem_range_rev(i, &memblock.memory, &memblock.reserved, \
                               nid, p_start, p_end, p_nid)

 

for_each_mem_range_rev()

  • 루프를 역순으로 돌며 지정된 노드 id의 A 타입 영역에서 B 타입 영역을 제외한 영역이 주어질 때 이 영역을 순서대로 p_start, p_end, p_nid 인수에 지정한다. B 타입 영역이 null일 수도 있다.
  • 인덱스는 64비트 값이며 절반씩 나누어 상위 32비트는 memory memblock 영역에 대한 인덱스를 가리키고, 하위 32비트는 reserved memblock 영역에 대한 인덱스를 가리킨다.
    • 처음 시작 시 역순으로 루프를 시작하므로 ~0UUL 값이 대입되어 시작한다.
  • ARM은 free 메모리를 할당하기 위해 검색시 이 top down 방식의 매크로를 사용한다.

mm/memblock.c

/**
 * for_each_mem_range_rev - reverse iterate through memblock areas from
 * type_a and not included in type_b. Or just type_a if type_b is NULL.
 * @i: u64 used as loop variable
 * @type_a: ptr to memblock_type to iterate
 * @type_b: ptr to memblock_type which excludes from the iteration
 * @nid: node selector, %NUMA_NO_NODE for all nodes
 * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 */
#define for_each_mem_range_rev(i, type_a, type_b, nid,                  \
                               p_start, p_end, p_nid)                   \
        for (i = (u64)ULLONG_MAX,                                       \
                     __next_mem_range_rev(&i, nid, type_a, type_b,      \
                                         p_start, p_end, p_nid);        \
             i != (u64)ULLONG_MAX;                                      \
             __next_mem_range_rev(&i, nid, type_a, type_b,              \
                                  p_start, p_end, p_nid))

 

  • 아래와 같이 memory 영역내에서 reserved 영역을 제외한 영역이 free 영역이고 2개의 영역이 역순 루프로 제공된다.

memblock15

  • 아래와 같이 memory region이 여러 개일 때 i 값의 추적을 표현하였다.
    •  i 값의 최초 시작은 0xffff_ffff_ffff_ffff로 시작하고 free 영역을 리턴할 때 마다 아래와 같이 변화가 됨을 알 수 있다.
    • for each 루프를 종료하는 순간 i 값은 다시 0xffff_ffff_ffff_ffff로 바뀐다.

for_each_free_mem_range_reverse-1d

 

__next_mem_range_rev()

mm/memblock.c

  • idx 값이 ~0UUL로 진입한 경우 idx_a에는 type_a 형태의 memblock 갯수에서 -1을 대입하고, idx_b에는 type_b 형태의 memblock 갯수 값을 대입한다.
  • 더 이상 매치되는 값이 없어서 루프를 다 돌고  함수를 종료하는 경우에는 idx 값이 다시 ~0UUL로 지정된다. (no more data)
/**
 * __next_mem_range_rev - generic next function for for_each_*_range_rev()
 *
 * Finds the next range from type_a which is not marked as unsuitable
 * in type_b.
 *
 * @idx: pointer to u64 loop variable
 * @nid: nid: node selector, %NUMA_NO_NODE for all nodes
 * @type_a: pointer to memblock_type from where the range is taken
 * @type_b: pointer to memblock_type which excludes memory from being taken
 * @out_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @out_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @out_nid: ptr to int for nid of the range, can be %NULL
 *
 * Reverse of __next_mem_range().
 */
void __init_memblock __next_mem_range_rev(u64 *idx, int nid,
                                          struct memblock_type *type_a,
                                          struct memblock_type *type_b,
                                          phys_addr_t *out_start,
                                          phys_addr_t *out_end, int *out_nid)
{
        int idx_a = *idx & 0xffffffff;
        int idx_b = *idx >> 32;

        if (WARN_ONCE(nid == MAX_NUMNODES, "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
                nid = NUMA_NO_NODE;

        if (*idx == (u64)ULLONG_MAX) {
                idx_a = type_a->cnt - 1;
                idx_b = type_b->cnt;
        }

        for (; idx_a >= 0; idx_a--) {
                struct memblock_region *m = &type_a->regions[idx_a];

                phys_addr_t m_start = m->base;
                phys_addr_t m_end = m->base + m->size;
                int m_nid = memblock_get_region_node(m);

                /* only memory regions are associated with nodes, check it */
                if (nid != NUMA_NO_NODE && nid != m_nid)
                        continue;

                /* skip hotpluggable memory regions if needed */
                if (movable_node_is_enabled() && memblock_is_hotpluggable(m))
                        continue;

 

                if (!type_b) {
                        if (out_start)
                                *out_start = m_start;
                        if (out_end)
                                *out_end = m_end;
                        if (out_nid)
                                *out_nid = m_nid;
                        idx_a++;
                        *idx = (u32)idx_a | (u64)idx_b << 32;
                        return;
                }

                /* scan areas before each reservation */
                for (; idx_b >= 0; idx_b--) {
                        struct memblock_region *r;
                        phys_addr_t r_start;
                        phys_addr_t r_end;

                        r = &type_b->regions[idx_b];
                        r_start = idx_b ? r[-1].base + r[-1].size : 0;
                        r_end = idx_b < type_b->cnt ?
                                r->base : ULLONG_MAX;
                        /*
                         * if idx_b advanced past idx_a,
                         * break out to advance idx_a
                         */

                        if (r_end <= m_start)
                                break;
                        /* if the two regions intersect, we're done */
                        if (m_end > r_start) {
                                if (out_start)
                                        *out_start = max(m_start, r_start);
                                if (out_end)
                                        *out_end = min(m_end, r_end);
                                if (out_nid)
                                        *out_nid = m_nid;
                                if (m_start >= r_start)
                                        idx_a--;
                                else
                                        idx_b--;
                                *idx = (u32)idx_a | (u64)idx_b << 32;
                                return;
                        }
                }
        }
        /* signal end of iteration */
        *idx = ULLONG_MAX;
}

 

기타 Memblock API

  • memblock_type_name()
    • memblock 타입명(문자열)을 알아온다.
  • memblock_cap_size()
    • 영역이 시스템의 최대 주소를 넘어가는 경우 overflow 된 만큼 잘라낸다.
  • memblock_addrs_overlap()
    • 영역이 서로 겹치는지 검사한다.
  • memblock_overlaps_region()
    • 등록된 memblock 영역들과 인수로 주어진 영역이 겹치는지 검사하여 겹치는 영역의 index를 리턴하고 아니면 -1 리턴
  • get_allocated_memblock_reserved_regions_info()
    • reserved 타입의 영역이 초기화 시 할당 받은 주소가 아니고 새롭게 buddy/slab memory 할당자에 의해 재 할당 받은 경우라면 해당 할당 영역의 시작주소를 리턴하고 아니면 0을 리턴한다. 이 함수는 free_low_memory_core_early() 함수를 통하여 bootmem 영역의 사용을 종료하고 buddy allocator로 전환할 때 호출된다.
  • get_allocated_memblock_memory_regions_info()
    • memory 타입의 영역이 초기화 시 할당 받은 주소가 아니고 새롭게 buddy/slab memory 할당자에 의해 재 할당 받은 경우라면 해당 할당 영역의 시작주소를 리턴하고 아니면 0을 리턴한다.이 함수는 free_low_memory_core_early() 함수를 통하여 bootmem 영역의 사용을 종료하고 buddy allocator로 전환할 때 호출된다.
  • memblock_double_array()
    • 주어진 타입의 memblock_region 배열을 2배 크기로 확장한다.
  • memblock_free()
    • reserved 영역에서 주어진 영역을 삭제한다.
  • memblock_set_node()
    • 주어진 영역에 해당하는 모든 memblock의 노드id를 설정한다. 영역이 memblock의 중간에 걸치면 분리하여 노드id를 설정한다.
  • memblock_phys_mem_size()
    • memory 영역에 등록된 memblock의 전체 사이즈
  • memblock_mem_size()
    • 주어진 limit_pfn까지 총 등록된 memory memblock 페이지 수를 알아온다.
  • memblock_start_of_DRAM()
    • memory 영역에 등록된 첫 memblock의 시작 주소(DRAM 시작 주소)
  • memblock_end_of_DRAM()
    • memory 영역에 등록된 마지막 memblock의 끝 주소(DRAM 끝 주소)
  • memblock_enforce_memory_limit()
    • 메모리 영역이 limit를 초과하는 경우 truncate ?
  • memblock_search()
    • 주어진 type의 memblock에서 주어진 주소로 2진 탐색 알고리즘을 사용하여 memblock을 찾고 해당 인덱스 값을 얻는다.
  • memblock_is_reserved()
    • reserved 영역에 주소가 포함되어 있는지 reserved 영역을 검색하여 판단한다.
  • memblock_is_memory()
    • memory 영역에 주소가 포함되어 있는지 memory 영역을 검색하여 판단한다.
  • memblock_search_pfn_nid()
    • memory 영역에서 주어진 주소로 2진 탐색 알고리즘으로 memblock을 찾은 후, 찾은 영역의 시작 페이지와 끝 페이지를 알아온다.
  • memblock_is_region_reserved()
    • 주어진 영역이 reserved memblock 영역과 겹치는지 확인한다.
  • memblock_trim_memory()
    • memory memblock들 모두 지정된 align 바이트로 정렬한다. 사이즈가 align 크기보다 작은 경우 삭제한다.
  • memblock_set_current_limit()
    • memblock의 limit를 설정한다.
  • memblock_dump()
    • 주어진 타입의 memblock들 정보를 출력한다.
  • memblock_dump_all()
    • memory와 reserved 타입의 memblock들 정보를 출력한다.
  • memblock_allow_resize()
    • 전역변수 memblock_can_resize=1로 설정(resize 허용)
  • early_memblock()
    • early_param()으로 등록한 함수이며 인수로 “debug” 문자열을 받게되면 전역 변수 memblock_debug=1로 설정하여 memblock_dbg() 함수를 동작하게 한다.
  • memblock_debug_show()
    • DEBUG_FS가 동작중이면 debug 출력할 수 있다.

 

디버그 출력

CONFIG_DEBUG_FS 커널 옵션을 사용한 경우 다음과 같이 memblock 등록 상황을 확인할 수 있다.

  • 예) rpi2의 등록된 memory와 reserved된 메모리 블럭들을 보여준다.
# cat /sys/kernel/debug/memblock/memory
   0: 0x00000000..0x3affffff

# cat /sys/kernel/debug/memblock/reserved
   0: 0x00004000..0x00007fff   <- 페이지 테이블
   1: 0x00008240..0x0098c1ab   <- 커널
   2: 0x2fffbf00..0x2fffff08
   3: 0x39e9e000..0x39f95fff
   4: 0x39f989c4..0x3a7fefff
   5: 0x3a7ff540..0x3a7ff583
   6: 0x3a7ff5c0..0x3a7ff603
   7: 0x3a7ff640..0x3a7ff6b7
   8: 0x3a7ff6c0..0x3a7ff6cf
   9: 0x3a7ff700..0x3a7ff70f
  10: 0x3a7ff740..0x3a7ff743
  11: 0x3a7ff780..0x3a7ff916
  12: 0x3a7ff940..0x3a7ffad6
  13: 0x3a7ffb00..0x3a7ffc96
  14: 0x3a7ffc9c..0x3a7ffd14
  15: 0x3a7ffd18..0x3a7ffd60
  16: 0x3a7ffd64..0x3a7ffd7e
  17: 0x3a7ffd80..0x3a7ffd9b
  18: 0x3a7ffda4..0x3a7ffdbe
  19: 0x3a7ffdc0..0x3a7ffe37
  20: 0x3a7ffe40..0x3a7ffe43
  21: 0x3a7ffe48..0x3affffff

 

참고

 

이전 글 -> Memblock – (1)

2 thoughts to “Memblock – (2)”

  1. for_each_mem_pfn_range()에서 region[0], nid=1 이 region[2], nid=1 이 되어야 합니다.

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.