KVMALLOC()

memory = kmalloc(allocation_size, GFP_KERNEL);
    if (!memory)
        memory = vmalloc(allocation_size);

kvmalloc() 은 내부적으로 kmalloc() 호출을 시도한다. 이는 slab allocator 를 이용한 메모리 압박이 없다면 빠른 메모리 할당을 지원한다. 또한 slab 은 PAGE_SIZE(32비트에서는 4KB) 보다 작은 메모리 할당을 위해 사용하고, 그보다 큰경우에는 물리적으로 연속적인 메모리를 할당하려고 한다. 하지만, 시스템을 운영하다 보면, 할당할 수 있는 메모리 공간은 있지만, 단편화로 인해 물리적으로 연속적인 공간은 할당 받지 못하는 경우가 있다. 물론, 연속적인 공간 확보를 위한 compaction 등의 feature 로 노력은 하지만 연속적인 공간 요청이 크다면 힘들 수도 있다.

 이런 경우 가상주소 공간에서 연속적인 메모리 할당을 vmalloc() 으로 가능하게 한다. vmalloc() 은 가상 주소 공간에서 연속적이지만, 실제 물리적으로는 흩어진 메모리를 관리한다. 이런 할당은 페이지 테이블의 수정이 생기고, TLB cache 의 invalidation 을 갖게 된다.(페이지 폴트) 또한 PAGE_SIZE 보다 작은 메모리 할당은 align 되어 PAGE_SIZE  만큼 할당할 것이다.

 이제 kvmalloc() 내부를 보자.

/**
 * kvmalloc_node - attempt to allocate physically contiguous memory, but upon
 * failure, fall back to non-contiguous (vmalloc) allocation.
 * @size: size of the request.
 * @flags: gfp mask for the allocation - must be compatible (superset) with GFP_KERNEL.
 * @node: numa node to allocate from
 *
 * Uses kmalloc to get the memory but if the allocation fails then falls back
 * to the vmalloc allocator. Use kvfree for freeing the memory.
 *
 * Reclaim modifiers - __GFP_NORETRY and __GFP_NOFAIL are not supported. __GFP_REPEAT
 * is supported only for large (>32kB) allocations, and it should be used only if
 * kmalloc is preferable to the vmalloc fallback, due to visible performance drawbacks.
 *
 * Any use of gfp flags outside of GFP_KERNEL should be consulted with mm people.
 */
void *kvmalloc_node(size_t size, gfp_t flags, int node)
{
    gfp_t kmalloc_flags = flags;
    void *ret;

    /*
     * vmalloc uses GFP_KERNEL for some internal allocations (e.g page tables)
     * so the given set of flags has to be compatible.
     */
    WARN_ON_ONCE((flags & GFP_KERNEL) != GFP_KERNEL);

    /*
     * Make sure that larger requests are not too disruptive - no OOM
     * killer and no allocation failure warnings as we have a fallback
     */
    if (size > PAGE_SIZE) {
        kmalloc_flags |= __GFP_NOWARN;

        /*
         * We have to override __GFP_REPEAT by __GFP_NORETRY for !costly
         * requests because there is no other way to tell the allocator
         * that we want to fail rather than retry endlessly.
         */
        if (!(kmalloc_flags & __GFP_REPEAT) ||
                (size <= PAGE_SIZE << PAGE_ALLOC_COSTLY_ORDER))
            kmalloc_flags |= __GFP_NORETRY;
    }

    ret = kmalloc_node(size, kmalloc_flags, node);

    /*
     * It doesn't really make sense to fallback to vmalloc for sub page
     * requests
     */
    if (ret || size <= PAGE_SIZE)
        return ret;

    return __vmalloc_node_flags(size, node, flags);
}
EXPORT_SYMBOL(kvmalloc_node);

 void *kvmalloc(size_t size, gfp_t flags);
 void *kvzalloc(size_t size, gfp_t flags);
 void *kvmalloc_node(size_t size, gfp_t flags, int node);
 void *kvzalloc_node(size_t size, gfp_t flags, int node); 

 커널 코드를 보다가 이 헬퍼 함수로 교체 가능한 코드가 있다면 수정 하면 좋겠다.

Virtually mapped kernel stacks

Original link: http://lwn.net/Articles/692208/

Linux Kernel "Stack"은 시스템 설계에서 거의 틀림없이 약점일 것이다: Stack 의 크기는 충분하지만 작은 크기를 갖기 때문에 Kernel 개발자들은 Stack overflow 를 피하기위해 끊임없이 그들이 stack 에 무엇을 넣든 주의해야 한다. 이런 상황을 만들려는 공격자가(attacker) 없어도 overflow 의 이슈는 생기기 마련이다. 그리고, Jann Horn 의 최근 데모를 보면, 왜 attacker 가 이런 시도를 하는지에 대한 이유들이 있다. When an overflow does occur, the kernel is poorly placed to even detect the problem, much less act on it. Linux Kernel Stack은 현재까지 개발되면서 아주 적은 변화만 있었지만, 최근의 변화는 잠재적으로 kernel stack 을 더욱더 견고하게 만들어 줄 가능성이 있다.

How current kernels stack up

각 프로세스는 kernel 에서 수행될 때 자기 자신 만의 stack 을 갖고 사용한다; 현재 kernel stack 의 크기는 8KB 나 16KB (64bit system)이다. Stack 은 "Direct-Mapped Kernel Memory" 에 있고 당연히 물리적으로 연속적인 공간을 이용한다. 이 요구사항은 시스템을 오래 운영하면서 memory fragmentation 때문에 연속적인 2 개 혹은 4 개의 page을 찾는 것은 어렵기 때문에 문제가 될 수 있다. Direct-Mapped memory 영역의 사용은 stack overflow 를 막기 위해 접근허용이 안되는 memory page(guard page) 의 사용으로 실제 사용되는 메모리 page 를 낭비하는 것이다.

결과적으로, 만약 Kernel 이 overflow 되려고 하는 시점에는 어떠한 조짐을 받을 수 없다. 대신에, 하나의 stack 이 메모리으 위치가 어디가 되었던 간에 할당된 영역 아래로 계속 overwrite를 하게 된다.(stack 의 특성상 큰 주소 번지에서 작은 주소 번지로 자란다.) 그러나 만약 stack overflow 가 production system에서 검출이 된다면, 이미 알수 없는 많은 데미지를 입은 상태일 것이다.(But if a stack overflow is detected at all on a production system, it is often well after the actual event and after an unknown amount of damage has been done.)

재미난 것이 하나 더 있다면, Kernel stack 맨 바닥에는 thread_info 라는 중요한 구조체가 있다. 그래서 만약 kernel stack 이 overflow 가되면, thread_info( kernel의 모든 것이라고 할 수 있는 현재 실행되는 프로세스에 관한 것을 알수 있는 정보에 접근) 가 제일 먼저 overwrite 될 것이다. stack 의 대부분이 어떤 것이 들어가 있는지 알수 없지만, thread_info는 너무나 유명한 것이니 attacker 들이 관심있어 하는 정보일 것이다.

kernel 개발자들은, 당연한 얘기 겠지만, stack overflow 를 피하기 위해 애쓰고 있다. stack 에 할당은 일발적인 rule 에 따라 실험되고, 재귀(recursion)은 허용하지 않는다. 하지만 놀라운것은 별로 관심도 없던 변수 선언에 의해 기대하지 않았던 호출 chain 이 형성되는 경우가 발생한다. (But surprises can come in a number of forms, from a careless variable declaration to unexpectedly deep call chains.) storage system (filesystem) 과 networking code 는 독단적인 depth를 가지고 stack을 쌓을 수 있어서 이런 문제를 쉽게 가질 수 있다.(The storage subsystem, where filesystems, storage technologies, and networking code can be stacked up to arbitrary depths, is particularly prone to such problems.) 3.15 release 를 위해 x86-64 kernel 의  stack 을 16KB 로 확장 하게 이끈것도 이 때문이다. 그러나 얼마나 stack 이 더 커질수 있는지에 대한 제한은 있다. 시스템에서 모든 process를 위한 하나의 stack 이 있는 이후로, 이런 증가는 여러번 일어 날 수 있을 것입니다.

stack overflow 문제를 회피하는 문제는 여전히 kernel 개발자 들에게 도전으로 남아 있다. 하지만, 그것은 overflow가 발생했을 때, Kernel이 더 나은 응답성을 가질 수 있도록 하는 가능성이 될 수 있다. 이런 가능성을 높이기 위한 가장 중요하게 진행할 수 있는 것은 Andy Lutomirski 의 Virtual mapped stacks patch set 으로 kernel의 stack 메모리 할당 방식의 변경이 될 수 있다. 

Virtually mapped stacks

대부분의 memory 는 directly mapped memory 영역으로 kernel에 의해 직접적으로 접근이 가능하다. 그 영역은 간단하고 모든 실질적인(?) 목적을 위해 선형적으로 물리 memory 를 mapping 한 주소공간이다. 이것은 마치 물리 memory 를 갖고 kernel 이 수행하는 것처럼 보일 수 있다. 64 bit 시스템에서는 모든 메모리가 이런 방법으로 접근 가능하다. 하지만 32bit 시스템은 모든 물리 memory 를 direct 접근을 할 수가 없다.(알겠지만, 32 bit 리눅스 커널의 가상 주소 공간은 4G 이며, 대게는 kernel 의 공간으로 1G를 사용한다. 이중 16MB 는 DMA, 896MB 은 direct mapped, 128MB 는 highmem 으로 사용된다. 그래서 최대 direct access 가 가능한 영역은 896MB 이다. 하지만 64 bit system에서는 현재 H/W 에 붙일수 있는 최대 크기의 memory 를 highmem 영역없이 접근가능하다.)

Linux 는 directly mapped 공간 뿐만 아니라 실제 physical memory 에 접근하기 위해 가상 주소를 사용하는 virtual memory system 이 있다. 그런 접근이 발생하면, Kernel은 가상으로 mapped 된 memory 를 위한 주소공간을 만든다. 이 공간은 vmalloc() 이 호출되었을 때 생기며, 이를 "vmalloc range"라 부른다. 실제 가상 주소 공간은 연속적이지만 물리적으로는 연속적이지 않다. 전통적으로 이 영역의 사용은 아주 큰 공간이 필요할 때 사용되며 가상적으로 연속적이지만 물리적으로 흩어져 있는 것을 허용할 때 이용된다.

Kernel stack 은 물리적으로 연속적일 이유가 하나도 없다. 각각의 page들이 vmalloc 영역에 mapping 되어 사용될 수 있다는 것이다. vmalloc 영역을 이용하는 것은 kernel 내에서 물리적으로 연속적인 큰 공간을 할당받아 사용하는 것 중에 하나를 제거할 수 있다는 것이고, memory fragmentation 이 많이 생겼을 때, 시스템을 안정적으로 만들 수 있다는 것이 장점이다. 이것은 또한 할당된 stack 을 보호하기 위해 낭비되는 메모리 없이 접근 불가능한 영역을 만들 수 있고, 만약 할당된 stack 영역을 넘어서는 접근이 있을 경우 Kernel이 즉각적으로 반응하여 처리 할 수 있다는 것이다. Andy 의 patch는 단지 kernel stack을 vmalloc 영역으로 부터 할당 받는 것이다. 또한 그는 이 patch 를 만들면서, 멋진 overflow handler 를 추가했다. 이는 oops 메세지 없이 overflow 를 만든 process를 죽이도록 하는 것이다.

이 patch set 자체는 아주 간단하다. 물론 architecture 의존적인 부분이 있긴 하지만, 이는 kernel의 안정성을 향상 시키며 reviewer 들도 긍정적으로 검토 중이다. 

Inconvenient details

vmalloc 영역에서 할당받은 stack 은 약간은 성능의 문제가 있다. Andy의 말에 따르면, clone()으로 생성되는 새로운 process 만드들때, 1.5µs 정도 더 걸린다. process-creation overhead 와 같은 작업들은 이 변경으로 인해 고통(?)받는 민감한 작업이다, 그래서 Linus 는 "이 변경이 적용이 되기전에 이 문제는 고쳐질 필요가 있다." 라고 했다. Andy는 이와 같은 문제는 vmalloc() 을 성능개선하여 고쳐질 수 있다고 생각한다.(vmalloc() 여지껏 성능에 관련해서 최적화하는 작업이 거의 이루어지지 않았다). 대신, Linus는 이것을 작게 유지하고 미리할당된 stack의 per-CPU cache 를 유지할 것을 제안했다. 그는 변경이 적용되기 전에 성능에 대한 regression 은 명확히 짚고 넘어가야 한다고 말했다.

다른 잠재적인 비용은 "translation miss" 증가에 대한 측정이 이루지지 않았다는 것이다.(page fault?) Direct mapped 영역을 사용하는 것은 huge-page mapping을 사용하는 것인데, 이는 전체 커널이(code, data 그리고 stack 을 포함하여) single TLB(Translation lookaside buffer) entry 로 맞춰 질 수 있다는 것이다. 하지만, vmalloc 의 경우 single-page mapping 을 이용하여 메모리내에 다른 window(?)를 생성한다. 그래서 kernel stack(direct mapped)의 접근은 일반적인 것이기 때문에, stack 이 만약 vmalloc 영역을 통해 접근한다면, TLB miss 의 증가의 가능성을 가질 수 있다.

또 다른 중요한 작은 세부사항은 guard page 를 포함한(물론 이 page 들은 할당 이후에 생성) vmalloc area 로 부터 받는 것이다. 일반적인 heap memory 는 쉽게 overrun이 발생할 수 있다. 하지만 stack은 작은 주소 방향으로 자란다는 것이고, overrun은 앞서 할당된 영역에 덮어쓰기를 한다는 것이다. 실제로는, vmalloc 영역의 앞부분에 guard page 가 위치 할 수만 있다면, 현재의 변경되는 코드는 overrun에 대한 guard page 로 부터 앞뒤로 잘 사용될 수 있도록 보장될 수 있을 것이다. 하지만 이와 같은 guard page 는 이 patch set 의 주요한 목표 중 하나이다. 

vmalloc 범위안에서 memory mapped 는 명확한 제약사항이 있다. 그것을 Direct Memory Access(DMA) I/O를 위해 쉽게 사용되어 질 수 없다. 이런 I/O는 메모리가 물리적으로 연속적이길 기대하고 있으며, 그리고 virtual-to-physical mapping address 함수는 이런 기대를 맞춰줄 수 없다. Kernel에서 stack로 부터 DMA를 수행하는 시도를 위한 코드는 없기 때문에 이것은 문제가 되지 않는다. stack 으로 부터 DMA 운영은 다른 이유들로 문제가 있다. 하지만 그런 코드들이 커널내에 어째든 운영이 된다는 것이다.(? - 이런 시도는 없다고 하지 않았나?) virtually mapped stack patch가 널리 이용이 된다면 정리되어야 하는 코드가 될 것이다.

마지막으로, 이 패치를 적용한 커널은 kernel stack 의 overflow 를 검출할 수 있도록 할 수 있다. 하지만 그것은 각 kernel stack의 맨 아래에 살고(?) 있는 thread_info에 작은 문제가 여전히 있다. 전체 stack을 overrun 하지 않는 선에서 이 구조체를 덮어쓰는 overrun은 발견되지 않을 것이다. 이것에 대한 알맞은 해결잭은 thread_info 구조체를 kernel stack으로 부터 멀리 떨어뜨려 이동해야 하는 것이다. 현재 이 패치를 그렇게 하지 않았는데, Andy 는 현재 이 패치가 적용되고 나면 생각해 본다고 말했다.

이 패치는 적용은 현재 문제들을 적절히 처리 할 수 있을 것 같아보인다. kernel은 stack overrrun에 대한 처리 및 발견이 가능하고 Linux system을 더욱더 견고하게 할 것이다.

Extended system call error reporting

the original link : https://lwn.net/Articles/657341

Kernel 과 User 영역 사이에 Interface 의 복잡도는 굉장이 높다. H/W 설정, 프로세스 상태 등의 자세한 정보를 어느 방향으로든 전달해주는 많은 task 들이 있다. 그런 task 들이 많기는 하지만, 뭔가 잘못 진행되는 경우 단지 integer 의 error code 만을 보여주기 때문에 종종 개발자들이 그것이 무엇이 잘못된 것인지 알아내기가 어렵다. 과거에도 그런 error-reporting 을 위해 다양한 제안히 있었다; 마지막 제안은(Alexander Shishkin) 이전 제안에 비해 많이 나아지질 않았으나 이 문제에 대해 나아가야 할 만한 포인트를 보여줬다.

예를 들어, Media subsystem 에 의해 제공되는 VIDIOC_S_FMT ioctl() 을 고려해보자. VIDIOC_S_FMT 는 capture 장치(카메라와 같은)로 부터 user 영역으로 Image 들의 포멧 정보를 설정하는 ioctl 이다. (http://linuxtv.org/downloads/v4l-dvb-apis/vidioc-g-fmt.html) 이런 가능한 이미지 포멧정보는 놀랍도록 다양하고 User 영역에서 연관된 파라미터와 함께 Kernel 로 포멧 디스크립션을 넘기도록 하고 있다. 이런 디스크립션 정보의 조합에 의한 문제가 발생할 수 있는데 이때, User 는 단지 VIDIOC_S_FMT 실패로 EINVAL 의 error code 만을 받게 될 것이다. 물론, kernel 은 무슨일 있었는지 알고 있지만, user 영역과 그 지식(?)을 공유하는 방법은 없었던 것이다.

이 문제는 고치는 것은 쉽지 않다; errno 매커니즘은 명백히 부족함을 느낀다. 그렇지만 Unix 전통적으로 오랫동안 사용되어 왔고 이것을 바꾸기엔 쉽지 않을 것이다. 그래서 어떤 확장된 error 정보를 잘 넘겨줄 수 있는 새로운 채널이 있어야 할 것이다. error 정보를 자세히 하여 전달하도록 kernel 에 추가하는 작업은 조심스럽게 이루어져야 한다. 이유는, kernel 의 중요한 기능을 느리게 한다던가 과도한 error 메시지 설정으로 소스의 흐름을 방해하는 것 등이다. Alexander 의 패치는 이런 두가지의 경우를 모두 만족하도록 설계되었다. 

error reporting 의 매커니즘을 잘 설명한 예제가 있다. Alexander 의 패치는 perf_event_open() 시스템 콜을 목표로 삼았다. 그것은 파라미터로 perf_event_attr 구조체를 받는데, 이 구조체는 event 캡쳐를 위해 설정해야 하는 파라미터 셋 들이 엄청나게 많이 있다. 이로 인해 이 system call의 운영은 잘못될 가능성을 갖고 있게 된다.

Describing errors

첫번째로는 error site 를 표현하는 구조체를 만들어야 한다. 그 구조체는 error 가 발견되고 user 영역으로 넘겨줄 수 있는 위치어야 한다. 그 구조체는 ext_err_site 구조체인 site 변수를 갖고 있어야 한다. 이 변수는 error 에 대한 전체적인 사항을 보고 할 수 있도록 어떤 정보든지 갖고 있을 수 있다. perf 의 경우에 이 구조체는 아래와 같이 생겼다.

    #include <linux/exterr.h>

    struct perf_ext_err_site {
	struct ext_err_site	site;
	const char		*attr_field;
    };

attr_field 멤버 변수는 error 가 생긴 struct perf_event_attr 내부의 field 의 이름을 갖고 있도록 한다.

그리고 나서, user 영역으로 넘겨질 이 구조체의 어떤 추가적인 정보를 담는 문자열을 넘겨줄 수 있는 함수를 정의할 필요가 있다. perf 버전에서는 :

    static char *perf_exterr_format(void *site)
    {
	struct perf_ext_err_site *psite = site;

	return kasprintf(GFP_KERNEL, "\t\"attr_field\": \"%s\"\n",
			 psite->attr_field);
    }

이 함수는 동적으로 할당된 문자열을 반환한다; 확장된 error reporting 구조에서 이 문자열이 더이상 필요없을때 할당 해제를 자동으로 한다.

이 두 코드 조각을 적절히 위치 시키면, 특정 error class 를 처리할 수 있는 "error domain"을 정의할 수 있게 된다. perf 의 경우를 보자

    DECLARE_EXTERR_DOMAIN(perf, perf_exterr_format);

error 정보를 실질적으로 보고하는 것은 ext_err() macro를 통해 완성된다. 실제 사용자는 wrapper 를 통해 사용할 수 있을 것이다. 어떻게 만들어 졌는지 perf code를 보자:

    #define perf_err(__code, __attr, __msg)				\
	({ /* make sure it's a real field before stringifying it */	\
	    struct perf_event_attr __x; (void)__x.__attr;		\
	    ext_err(perf, __code, __msg, 				\
	        .attr_field = __stringify(__attr));			\
	})

ext_err() 의 파라미터 들은 위에서 정의된 domain (error code, user 영역에 전달될 메시지)이다. 그리고 error-site 구조체의 나머지를 초기화된 문자열을 설정(set)한다. 이 경우, ext_err() 의 마지막 파라미터는 잘못된 속성으로 설정된 perf_ext_err_site 구조체의 이름을 attr_field 에 넣는다. 이 패치를 보면 peft_err() 매크로가 어떻게 실행되는지 볼 수 있다.

또 다른 중요한 세부 내용이 있다. 하나는 EXTERR_MODNAME 심볼인데 이것은 ext_err() 이 불리기 전에 반드시 set되어 있어야 한다.

    #define EXTERR_MODNAME	"perf"

다른 하나는 ext_err() 는 함수 파라미터로 넘어온 error 코드를 변경하여 값을 반환한다. 이 코든는 kernel 이 알고있는 모든 확장된 error 에 대한 설명이 되어 있는 ext_err_site 구조체의 index 라 보면 된다. 일반적인 방법으로는 user 영역에 반환하기 위해서 아래와 같이 사용한다.

    return ext_err_errno(code);

ext_err() 가 변환한 코드는 application 이 무슨 의미인지 알수 없기 때문에 user 영역에 직접적으로 전달되지는 않는다. 그래서 원래 error code 는 ext_err_errno() 를 호출하지 않고 반환되어서는 안된다. 이런 호출은 확장된 error 정보를 kernel 이 다 기억을 해야한다는 조건이 성립해야 한다. 간략하게 말하면, 새로운 ext_err_code 라 불리는 field 를 새로운 task_struct 내부에 있도록 해야 한다. 그래서 ext_err_errno() 의 호출은 그 field 에 위치한 특별한 error code를 바라보도록 해야 한다는 것이다. 만약 확장되기 이전 error code를 ext_err_errno() 에 넘기게 되더라도 정상동작할 것이며 그것은 안전하게 기존과 확장된 error code 모두를 지원할 것이다.

The user-space side

kernel은 user 영역에 확장된 error 메시지를 알려줄 준비가 다 되어 있지만, system call 로 부터 반환된 값을 여전히 예전 errno를 사용하는 경우가 많을 것이다. 만약 application 에서 더 많은 정보를 원한다면, 아래 처럼 사용하면 된다.

    char message[SIZE];

    len = prctl(PR_GET_ERR_DESC, message, SIZE);

반환 값을 기존 메시지와는 다를 것이다. JSON 포멧으로 에러가 발생된 곳의 file 과 line, error 코드, 모듈 이름, 실제 메시지 그리고 앞서 설명한 domain format 함수에 의해 추가된 정보를 줄 것이다. 이 변경으로 user 영역에 perf tool 에 JSON parser 를 사용하여 메시를 잘 분리하여 적절히 분석 가능할 것이다. prctl() 호출은 kernel 영역에서 error 정보를 지울 것이며, 다시 호출한다면 아무런 data를 받을 수 없을 것이다.

이 패치는 review 커멘트가 많이 보이지는 않는다. 끝으로 error 보고 문제는 많은 개발자가 인지하고 있으며, 이것을 고치기 위해 몇몇은 노력까지 한다. 그리고 커널로 부터 error-reporting 채널을 넓히는 시도를 하여 성공하는지는 알수 없지만, 전통적으로 누군가가 고민하고 변경을 시도한다면 언젠가는 누군가가 성공으로 이끌 것이다.

[책 소개] 리눅스 커널 패치와 커밋

블로그에 쓰려던 내용들을 모으다 보니, 양이 상당하니 책으로 쓰면 어떨까 하고 진행했다. 거의 10개월만에 완성하고 E-book 으로 출간이 되었다!! (종이책은 5월말에 출간 예정.)

책은 간단히 리눅스 커널의 코딩 스타일을 고치는데서 부터 정적 분석 툴을 쓰고, QEMU 를 이용한 리눅스 커널 디버깅 방법들을 정리했다. 

Qemu booted kernel debugging with GDB

책을 읽고, 그 내용의 소스를 분석하다 보면 어떤 값에 의해 진행이되고 예제를 만들어 보는 과정에서 도저히 답이 안나오는 상황들이 생긴다. 그 때 대충 시나리오를 만들고 만든 시나리오에 값을 넣어 code를 분석하는데 값이 명확하게 떨어지면 굉장히 분석이 잘된다.(지난 buddy 관련 code를 분석할 때 그러했다.http://woodz.tistory.com/57)

하지만 그렇게 분석이 순조롭게 흘러가지 못하고 방황을 하다보면 집중도 안되고 하다 말아버리는 경우가 다반사다. 그래서 얼마전에 찾다보니 gdb 를 연결하여 kernel code를 쫓아가는 방법을 알게 되었다. 

eclipse + CDT 에 gdb를 연결하여 추적하는 방법은 UI 사용성이 좋고 보기 편하지만 너무 무겁다는 것이 단점이다. 조금 빨리 보고 싶은데 답답해서 eclipse 를 빼고 최대한 편한 방법을 찾았다.

(eclipse 를 이용해 kernel debugging 및 trace 하고 싶으신 분은, http://www.sw-at.com/blog/2011/02/11/linux-kernel-development-and-debugging-using-eclipse-cdt/ 여기를 참조하여 하면 좋다. 그림으로 잘나와있기도 하고)

이 포스팅은 kernel target 을 x86 으로 build 하고 qemu 로 순조롭게(?) 부팅하여 gdb 연결하는 것까지 준비했다.

1. kernel 준비

  - kernel source 를 받자.

  요샌 30분 이내로 다운로드 가능하더라.

  - kernel build

   다른 것들은 default 로 내비두고, gdb 를 사용해야 하므로 두가지 option 이 check 되어 있는지만 확인하자.

  a. Kernel hacking ==> Compile-time checks and compiler options ==> [*] Compile the kernel with debug info

  b. Kernel hacking ==> Compile-time checks and compiler options ==> -*- Compile the kernel with frame pointers

b는 default 로 되어 있었다. 안되어 있는 분은 check 해주자.

% menuconfig 하면 ncurses-devel 이 설치 안되어 있다고  error를 낼때는,

  ==> $ sudo apt-get install ncurses-dev

2. qemu 준비
 - Ubuntu 의 경우

3. kernel 부팅.(x86_64 system)

% 32bit machine 의 경우 qemu-i386 command 로 하면 된다.

위에처럼 하면 kernel 이 부팅된다. 물론 root filesystem 이 없기 때문에 mount 를 못하고 panic 을 발생시킨다. 

(control + C 하면 qemu 가 종료한다.)

root file system 없이도 kernel 을 gdb 에 연결할 수 있다.

우선 rootfs 없이 진행을 해보자.

4. gdb 연결

위의 command 에서 -s 는 gdb 를 default 로 쓰되 tcp port 1234 으로 연결하겠다는 의미의 옵션이다.(-gdb tcp::1234)

-S 옵션은 cpu 를 start 해줄때까지 멈춰있겠다는 의미이다.

실행하면 검은 화면만 떨렁 있는 화면을 볼껏이다. 그럼 이제 gdb 를 연결해보자.

gdb command 이후에 "target remote localhost:1234" 를 치면, qemu 와 연결이 완료된다.

아직도 qemu 는 검은색화면이다. 

그다음에는 break point 하나를 잡자. 

break point 잡고 c(continue) 를 입력하면 실제 진행하다 start_kernel() 에서 멈춰있는 것을 확인 할 수 있다.

gdb command 로 요리하면서 부팅 sequence 를 살펴봐도 되고.. 뭐 암튼 그러하다.

현재 멈춰있는 곳의 소스 보기.

gdb 를 잘쓰면 아주 훌륭하다고 하는데... gdb 에 text ui 를 붙인 version 이 있는데 맨 아래에 추가적으로 소개하겠다.

5. simple rootfs 만들기.

  - get rootfs 

  http://downloads.yoctoproject.org/releases/yocto/yocto-1.2.1/machines/qemu/qemux86/ 이 링크에 접속하면

미리 만들어진 rootfs 가 있다. tar 로 묶여져있는 것과 ext3 확장자를 가진 것이 있는데, 지금 만들어진 image는 download 가 안된다. --;

일단 제일 작은 tar.gz로 된 rootfs 를 받자.

core-image-minimal-dev-qemux86.tar.bz2 이걸 받았다.

압축을 풀면, 아래와 같이 구성이 되어 있다.

이것을 qemu 가 mount 할 수 있도록 만들어 주면 된다. 이 방법도 eclipse CDT 에 참조했던 link 에 나와있다.

사실 위의 command 들 모두가 뭐하는 것인지 자세히는 모른다. :)

암튼 만들어진 rootfs.ext3 로 mount 하여 기존 빌드한 kernel image로 부팅해보자.

부팅을 다하면,

위에처럼 login 화면이 뜬다. root 라고 입력하면 shell 을 만날 수 있을 것이다.

여기서 kernel debugging을 하려면, qemu option 에 -s 만 옵션으로 넣고 gdb를  붙이면 된다. 이래저래 해보시길...

6. cgdb

검색을 해보면 아시겠지만, text based(gdb -tui) gdb 에 syntex highlight 를 넣은 것이다. 

사용은, 

하고 위에서 remote 에 연결하는 command 를 하면 된다. break point를 잡고 run 했을 때, 어떻게 보이냐면,

위의 예제는

break point 를 compact_zone 함수에 걸어놓고, 

shell 에서 $ echo 1 > /proc/sys/vm/compact_memory 하면 그 함수가 불리고 break 가 걸린다.

그럼 source level 에서 쫓아갈 수 있을 것이다.

gdb 사용이 아직 익숙치 않아 봐야 할 부분들이 많다.

How does get_current() work?

Kernel 을 보다 보면, "current"를 사용한 코드들이 보인다. 이에 관련해서 어떻게 현재 수행중인 process의 task struct 를 갖고 올 수 있는지 확인해 보자.

참고 url : http://kernelnewbies.org/FAQ/get_current

             http://kernelnewbies.org/FAQ/current

위의 두 가지를 참고하여 재구성 해봤다. 

일단 process 마다 virtual address space 를 갖고 있다. 이는 User/Kernel 의 영역이 나뉘어져 있는데(대게 3G(user)/1G(kernel) 을 많이 사용한다), 이중 kernel 영역에 get_current() 를 통해 현재 process 정보를 얻어올 수 있도록 하는 것이 get_current() 이다.

Kernel 영역의 어디에 이와 같은 정보가 저장되느냐면, Kernel 이 갖고 있는 stack 의 가장 아래쪽에 저장되어 있다.(stack 이 높은 주소에서 낮은 주소 방향으로 이동하며 사용되니까 가장 아래쪽이라 하면.. 아래 그림을 보자)

대게 32bit 에서는 8KB stack 을 사용한다고 한다. 위에서 처럼 stack 의 맨 아래의 정보를 얻기 위한 macro가 get_current() 이다.

일단 get_current() 는 thread_info struct 정보를 넘기고 thread_info struct 는(architecture 마다 다른 듯 함.)

get_current() 로 얻은 thread_info 를 통해 현재 process의 상태 및 task_struct 도 갖고 올 수 있다.

Kernel Stack 은 항상 고정된 주소이고 이 thread info가 저장되는 위치는 항상 같은 곳이다. 그래서 얻어오는 과정의 소스를 분석해보자.

간단하다. 위에서 처럼 current->XXX 로 사용하면 된다.(thread_info 구조체에 있는 녀석으로)

current_thread_info() 의 함수는 architecture 마다 따로 구현이 되어 있다. ARM 것을 보면,

단지 현재 stack pointer register를 읽어다가, sp & ~(THREAD_SIZE - 1) 했다.

현재 32bit 의 ARM 에서 stack 의 크기는 8KB 이다. 그렇다면 stack 의 12bit 만 0으로 만들어 주면 제일 낮은 주소의 stack 주소가 나오고 거기에는 현재 thread_info 의 address가 있다는 것이다.(현재 stack pointer 가 위의 그림에서 중간쯤에 위치 하더라도 하위 12bit 만 0으로 해주면 맨 아래의 thread_info 를 접근 할 수 있을 것이다.)

이렇게 해서 current macro를 이용해서 thread_info 구조체의 내용을 갖고와 process 의 status 확인 및 control 이 가능 한것이다.

define 으로  do { ... } while(0) 많이 쓰는 이유

Kernel code 를 보면 do { // some codes.. } while(0) 를 많이 쓰고 있다.

이에 대한 이유를 보면,

   1. 빈 구문은 compiler 로 부터 왜 #define FOO do {} while(0). 같이 썼는지 warning 을 받을 수 있다.

      (뭔가 구현 중에 있는 code 나 특정 define 이 정의되지 않을 때의 code가 없는 경우에 대체 후, compile 시 알림 같은 것으로 사용이 되려나.. 싶다.)

   2. 지역 변수 선언을 위해 쓰는 기본 block 으로 사용될 수 있다.

   3. 복잡한 macro를 이용해서 조건부 코드를 만들려고 할 때, 아래와 같이 만들 수 있을 것이다. 이것에 문제점을 보안하기 위해 do-while-0 블락을 사용할 것이다.

#define FOO(x) \
        printf("arg is %s\n", x); \
        do_something_useful(x);

위의 define으로 조건부 code를 만들어보자. 예를 들어,

if (blah == 2)
        FOO(blah);

위에서 처럼 만들었다면, interpreter 는 FOO 를 정의된 내용으로 대체를 할 것이다.

if (blah == 2)
        printf("arg is %s\n", blah);
        do_something_useful(blah);;

위에서 보듯이 printf 와 do_something_useful() 함수를 같이 쓰려는 목적과는 다르게, blah 가 2일 경우에만 printf 와 do_something_useful 가 같이 불릴 것이다. 이를 예방하기 위해, do { ... } while(0) 으로 define을 해두면,

if (blah == 2)
        do {
                printf("arg is %s\n", blah);
                do_something_useful(blah);
        } while (0);

위와 같이 변경 될 것이고 한번에 호출 될 수 있을 것이다.

  4. 또 다른 예제로는, define으로 지역변수 선언과 사용되는 것을 만들어 놓으면 아래와 같이 구현이 될 것인데(물론 여기에 나온 예제는 간단하고 억지스러움이 있을 수 있다.)

#define exch(x,y) { int tmp; tmp=x; x=y; y=tmp; }

위의 정의를 아래와 같이 사용한다면,

if (x > y)
        exch(x,y);          // Branch 1
else  
        do_something();     // Branch 2

이런식으로 구현을 하려고 할 것이고 이는 컴파일에 문제가 발생할 것이다. 이유는, 아래와 같이 번역(?) 되기 때문이다.

if (x > y) {                // Single-branch if-statement!!!
        int tmp;            // The one and only branch consists
        tmp = x;            // of the block.
        x = y;
        y = tmp;
}
;                           // empty statement
else                        // ERROR!!! "parse error before else"
        do_something();

세미콜론(;) 이 블락이 끝나자 마자 오게되어 발생하는 문제이다. 이것의 해결또한 do { ... } while(0) 으로 해결 할 수 있단다.

if (x > y)
        do {
                int tmp;
                tmp = x;
                x = y;
                y = tmp;
        } while(0);
else
        do_something();

위에서 보듯이 정리가 될 것이다. 이는 습관적인(?) rule 을 통해 code에 문제를 해결하기 위한 것이라 생각이 든다. 이미 kernel에는 많은 do { ... } while(0) 있다. 

추가적으로 GCC 는 do-while-0 블락을 대체 할 수 있는 것을 제공한다. 아래와 같이 사용하면 위에서 쓰는 것과 동일한 효과를 보는 것이다.(참고 자료 : http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Statement-Exprs.html#Statement-Exprs)

#define FOO(arg) ({         \
           typeof(arg) lcl; \
           lcl = bar(arg);  \
           lcl;             \
    })

알아두면 편리한 code 작성 법이다. 원본 URL 은 http://kernelnewbies.org/FAQ/DoWhile0 이다.

Likely and Unlikely

Likely() 와 Unlikely() 의 사용법과 용도를 알아보자. 원본 URL : http://kernelnewbies.org/FAQ/LikelyUnlikely

이 함수들은 뭐하는 건가?

예제를 보자.

bvl = bvec_alloc(gfp_mask, nr_iovecs, &idx);
if (unlikely(!bvl)) {
  mempool_free(bio, bio_pool);
  bio = NULL;
  goto out;
}

위와 같이, 특정 condition 을 확인하는 용도로 사용되는데 위의 code는 bvec_alloc으로 할당 받고 bvl 이 유효하지 않는 address이라면 free 하고 NULL 로 만들어주는 code이다. 

likely(), unlikely() 는 include/linux/compiler.h 에 정의된 macro 이다. 이것의 용도는 컴파일러에게 branch 예측을 도와 주는 용도로 사용이된다. 즉, 대부분 0으로 예측이 된다면 unlikely(x) 의 형태로 쓰고, 1로 예상되는 값을 likely(x) 로 쓴다. 예측을 도와 줌으로써 성능의 향상을 볼 수 있도록 하는 것이다.

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

__builtin_expect() 함수는 GCC 문서의 설명을 살펴보면,(원본은 http://kernelnewbies.org/FAQ/LikelyUnlikely 여기에서 보시길)

-- Built-in Function: long __builtin_expect (long EXP, long C)
   '__builtin_expect' 를 사용하는 것은 compiler 에게 branch prediction 정보를 제공해주기 위한 것이다. 일반적으로 개발자들은 자신의 program이 실제로 어떻게 수행되는지 알기가 힘들기 때문에 '-fprofile-arcs' option을 통해 profile 을 feedback 받는 것을 선호합니다. 그렇지만, 어떤 application들은 이것 조차도 수집하기 힘든경우가 있긴 하다.


반환 값은(return value)는 EXP 인 완전한(?) 표현이어야 한다.(아래의 예제를 통해..) EXP와 C는 서로 같아야 합니다.(EXP == C)


    if (__builtin_expect (x, 0))
       foo ();
이렇게 구현한 것의 의미는 foo() 라는 함수가 불리지 않기를 기대하는 것입니다. 즉, 'x' 는 대부분 0 의 값을 가졌으면 한다는 것이다. 또 다른 방법으로는 EXP 에 "식"으로 사용할 수 있다.


    if (__builtin_expect (ptr != NULL, 1))
       error ();
예제가 조금 이상하다. ptr != NULL 인 경우가 대부분이라고 알려주는 것인데, NULL 이 아닐때는 error() 가 실행된다. 아닌 경우라면 bypass.

#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)  __builtin_expect(!!(x), 0)

int main(char *argv[], int argc)
{
   int a;

   /* Get the value from somewhere GCC can't optimize */
   a = atoi (argv[1]);

   if (unlikely (a == 2))
      a++;
   else
      a--;

   printf ("%d\n", a);

   return 0;
}

위의 code를 편집기에 붙여 넣고 저장 한뒤,(test.c)

$ gcc -o test test.c -O2

$ objdump -S test

하면 많은 내용들이 나오는데 그 중에 <main> 이라는 부분을 찾아보면

080483b0 <main>:
 // Prologue
 80483b0:       55                      push   %ebp
 80483b1:       89 e5                   mov    %esp,%ebp
 80483b3:       50                      push   %eax
 80483b4:       50                      push   %eax
 80483b5:       83 e4 f0                and    $0xfffffff0,%esp
 //             Call atoi()
 80483b8:       8b 45 08                mov    0x8(%ebp),%eax
 80483bb:       83 ec 1c                sub    $0x1c,%esp
 80483be:       8b 48 04                mov    0x4(%eax),%ecx
 80483c1:       51                      push   %ecx
 80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
 80483c7:       83 c4 10                add    $0x10,%esp
 //             Test the value
 80483ca:       83 f8 02                cmp    $0x2,%eax
 //             --------------------------------------------------------
 //             If 'a' equal to 2 (which is unlikely), then jump,
 //             otherwise continue directly, without jump, so that it
 //             doesn't flush the pipeline.
 //             --------------------------------------------------------
 80483cd:       74 12                   je     80483e1 <main+0x31>
 80483cf:       48                      dec    %eax
 //             Call printf
 80483d0:       52                      push   %edx
 80483d1:       52                      push   %edx
 80483d2:       50                      push   %eax
 80483d3:       68 c8 84 04 08          push   $0x80484c8
 80483d8:       e8 f7 fe ff ff          call   80482d4 <printf@plt>
 //             Return 0 and go out.
 80483dd:       31 c0                   xor    %eax,%eax
 80483df:       c9                      leave
 80483e0:       c3                      ret

이것도 원본 URL 에서 붙여 넣은 것인데, 직접 해보니 조금 짤린 부분이 있는 것으로 보인다. a == 2가 같은 것이 참이라면 0x80483e1 으로 jump 를 하게 되는데 jump 되는 주소의 instruction 이 복사가 안된 듯 하다. 거기에 mov command 로 a++ 인 "3"을 직접 넣어주고 printf 를 호출해야 하니, 80483d0의 주소로 바로 jump 하는 instruction 이 있을 것이다.

주석에서 보듯이, unlikely() 의 경우 a의 값과 2가 같지 않는것이 대부분이라고 해준것이다. 만약 2와 같지 않으면 jmp instruction 을 수행하지 않고 pipeline flush 가 일어나지 않도록 하여 성능 향상을 주는 것이다.

반대로 likely() 로 변경하여 진행해보자.

컴파일을 다시 하고, objdump 로 disassem 해보면,

080483b0 <main>:
 //             Prologue
 80483b0:       55                      push   %ebp
 80483b1:       89 e5                   mov    %esp,%ebp
 80483b3:       50                      push   %eax
 80483b4:       50                      push   %eax
 80483b5:       83 e4 f0                and    $0xfffffff0,%esp
 //             Call atoi()
 80483b8:       8b 45 08                mov    0x8(%ebp),%eax
 80483bb:       83 ec 1c                sub    $0x1c,%esp
 80483be:       8b 48 04                mov    0x4(%eax),%ecx
 80483c1:       51                      push   %ecx
 80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
 80483c7:       83 c4 10                add    $0x10,%esp
 //             --------------------------------------------------
 //             If 'a' equal 2 (which is likely), we will continue
 //             without branching, so without flusing the pipeline. The
 //             jump only occurs when a != 2, which is unlikely.
 //             ---------------------------------------------------
 80483ca:       83 f8 02                cmp    $0x2,%eax
 80483cd:       75 13                   jne    80483e2 <main+0x32>
 //             Here the a++ incrementation has been optimized by gcc
 80483cf:       b0 03                   mov    $0x3,%al
 //             Call printf()
 80483d1:       52                      push   %edx
 80483d2:       52                      push   %edx
 80483d3:       50                      push   %eax
 80483d4:       68 c8 84 04 08          push   $0x80484c8
 80483d9:       e8 f6 fe ff ff          call   80482d4 <printf@plt>
 //             Return 0 and go out.
 80483de:       31 c0                   xor    %eax,%eax
 80483e0:       c9                      leave
 80483e1:       c3                      ret

여기도 마지막 두 line 이 짤려져 있다. jne 로 jump 하게 되면 거기에 2 라는 값을 eax 에 넣어주고 printf 를 호출 하도록 하는 code일 것이다. 

위에서 보듯이 likely() 로 하면 대부분 2와 같을 것이라고 컴파일러에게 알려줘서 최대한 jmp instruction 이 수행되지 않게 될 것이다.

이렇게 개발자가 예측할 수 있는 부분에 대해 거의 대부분이 x와 같을 것이다 혹은 다를 것이다라는 것을 컴파일러에게 알려주는 방식으로 적용하여 program을 만들 수 있을 것이다.

Write and Submit My First Kernel Patch

Kernel 의 Buddy 알고리즘 할당 방법을 위한 소스 분석을 하면서 발견한 문제를 큰 맘(?)먹고 진행을 해봤다. 처음이라 2~3 줄 고치는데 굉장히 여러 번 다시 보고 맞는지 확인 또 했다. 너무 간단한 내용의 수정이지만 patch 하고 검사받는 과정을 알아본다고 생각하시면 된다.

문제는 Buddy part 1 을 쓰면서 발견했다. 간단히 요약하면 while loop 내부에서 한번 설정되면 update 나 수정 사항이 없는 변수를 매 loop 매다 설정하는 것을 while 밖으로 빼낸 것이다.

이 코드는 굉장히 오랫동안 이런 상태로 유지되고 있었으며, 소스 분석 당시에 봤던 kernel 이 3.4.X 였으니 최신버전에는 반영되었겠지 하고 확인해봤는데 아직도 그대로 인 듯 하여 Patch 를 진행했다.

Patch를 하는 방법과 Coding Style 확인 하는 방법을 기존 포스트에서 쓴 적이 있으니 참고하시면 된다.

어떻게 하고 결과를 받았는지 적어 두려한다.

우선, Code를 수정한다.

수정한 위치는 mm/bootmem.c의 free_all_bootmem_core() 함수이다.

$ vi mm/bootmem.c

  수정...

$ git status

$ git add mm/bootmem.c

$ git commit

git commit 하면 "# Please..." 만 있다. 맨 윗 줄에 제목을 쓰고 한줄 띄우고 더 추가적인 comment 가 있다면 쓴다음에

마지막 줄에 Signed-off-by: Your Name <email@email.com> 형식으로 한 줄 추가해 주면 된다.

편집기를 저장 하고 나오자

$ git log .

그러면 위와 같이 나온다.

이제 patch 파일을 만들고 maintainer 를 확인 한 다음에 메일을 보내면 된다. 

물론 사전에 확인해야 할 사항들이 있는데, 너무 간단한 내용이라 빌드 확인 만 했다. 기본적으로 확인 해야 하는 사항은 

Kernel/Documentation/SubmitChecklist 를 열어보면 10가지 정도가 나와있다. 기본적인 빌드 테스트와 확인 사항이 있다.

이제 patch file 을 만들어 보자.

사실 이렇게 하나정도 수정하는 경우에는 branch 를 따로 만들지 않고 해도 무방하다.

$ git format-patch HEAD^

위와 같은 파일이 만들어진다.

내용을 열어 보면,

요런 식으로 만들어진다. 

자 이제 메일을 보내보자. 근데 누구한테 보내야 되는지 확인을 먼저 해야 한다.

$ ./scripts/get_maintainer.pl 0001-mm-unnecessary-set-a-variable-in-while-loop.patch

여러 사람과 mailing list 가 나온다. 사실 to 로 누구를 보내야 하고 cc 로 누굴 넣어야 할 지 모르는 상태이다.

그래서 사실 맨위의 한사람에게 메일을 보내버렸다. 하루정도 지나서 Andrew 라는 사람이 다음부터는 cc 에 관련자를 꼭넣어야 merge 해준다고 한다. 사람이름은 to 로 보내고 단체 이름은 cc 로 보내면 맞을 것이다.

일단 mail 보내는 방법은 git send-mail command를 이용해도 좋고, Documentation/email-clients.txt 파일을 열어보면 여러 linux email client 가 있고, patch를 보내는 방법이 나와있다.

나는 그중에 Kmail client 를 이용해서 메일을 보냈다. kernel patch 관련 메일은 patch 파일로 첨부해서 보내거나 하면 안된다. patch 를 plan text 로 보내야 하는데, indentation 이 달라지면 안되기 때문에 따로 보내는 rule 과 방법이 있는 것이다. 

그냥 git send-email command를 이용하도록 하자. 난 어쩔수 없는 상황이라 Kmail로 한것임.

git send-mail command 사용법은(물론 설치해야 한다.)

$ git help send-email 

해서 마지막 예제 부분을 보던가, google 검색을 하면 설정하는 방법들이 나온다.

$ git send-email --to akpm@linux-foundation.org --to daeseok.youn@gmail.com --cc linux-mm@kvack.org --cc linux-kernel@vger.kernel.org 0001-mm-unnecessary-set-a-variable-in-while-loop.patch 이렇게 보내면 된다.

나의 경우에는 하루만에 메일이 왔다.

실제로 보낸 commit 의 제목을 알맞게 변경도 해주었고, CC를 붙이라는 comment 로 따로 해주었다.

최종 적으로, http://marc.info/?l=linux-mm-commits&m=138195455814828&w=4 에 등록이 되었고, 3~4 일뒤에 merge 작업이 있을 것이라고 한다.

이렇게 해서 첫 patch 가 성공적으로 merge 되었다. 한번 해봤으니 다음번에는 잘 찾아서 commit 을 해볼 예정이다.

Linux kernel physical memory allocator (Buddy) - Part 3

오늘은 할당에 이어 해제과정의 소스 분석을 해본다.

현재 쓰는 시점에서 lxr.linux.no 가 접속 되지 않아 함수에 link 를 붙이지 못했다.

Free 의 호출 순서는 아래의 그림과 같다.

free_pages() 는 parameter 로 virtual address 와 order 를 받게 된다. 이 virtual address 를 page 단위로 변환하고 order 는 size 에 준하여 계산하면 된다.

위의 그림에는 나와있지 않지만 free_pages() 와 __free_pages_ok() 함수가 호출 되는 과정에 free_hot_cold_page() 함수 가 있다. 이는 order 0 일 경우에만 동작하는데, part 2 에서 할당하는 과정에 order 0 일 때, per_cpu_pages 구조체에 있는 page 를 갖고오는 code를 기억할 것이다. 이런 경우(?)는 자세히 다루진 않겠지만 대략적으로 order 0의 cold 한 page 를 per_cpu_pages 구조체에 갖고 있다가 필요한 경우 가져다 쓰는 방식으로 하는 것이 아닐까 한다. 

암튼, __free_pages_ok() ==> free_one_page() ==> __free_one_page() 순으로 호출된다.

__free_one_page() 함수의 소스를 보자.

(한꺼번에 분석하지 않고 적당한 line에서 나눈 것이다.)

이 함수는 parameter 가 4개이다. 이 때까지 migratetype은 신경 안썼으니 pass 하자. 

첫번째 parameter 는 free_pages 로 넘어온 virtual address 를 page 로 변환한 주소를 넘겨 받았을 것이다.

그리고 해제 하려는 size 를 받았을 것이고 size 를 order(세번째 parameter) 로 변환하여 받는다.

line 16 에서 page_idx (page frame number) 를 구하는 공식이다. 

간략히 살펴 보면 __page_to_pfn(page) 를 보면 (page 주소 - mem_map) 을 한뒤 ARCH_PFN_OFFSET 을 더해주고 return 해준다. 

ARCH_PFN_OFFSET 은 대게 물리메모리 시작 주소가 0이 아닌 경우에 사용된다. 

(예를 들어 물리 메모리의 시작 번지가 8192 이고 그 시스템의 PAGE size가 4096 이라면 ARCH_PFN_OFFSET 은 2 가된다.) 여기서 mem_map 은 간략히 시스템이 갖고 있는 물리 메모리를 page 단위로 mapping 해놓은 map이다. 그렇다는 것은 mem_map(struct page* 형) 을 현재 page 주소값에다 빼주면 말 그대로 page 가 mem_map 으로 부터 몇 번째 있는 page 인지 알 수 있는 것이다.

현재 page_idx = PFN & ((1 << 11) -1); // 11은 MAX_ORDER 값이다.

다시 적으면 page_idx = PFN & 0x1FFFF 가 된다. pfn max 131071 인 듯.(정확히 왜 제한을 두는 것인지 확인 하지 못했음).

line 21 현재 order 에서 MAX_ORDER - 1까지 loop 을 수행하면서, 

line 22 __find_buddy_index() 를 통해 buddy page frame number를 구해 온다. 

part 2-1 을 보면 알겠지만, buddy 와 함체를 위해 찾는 것이다. 

현재 free 하려는 index 가 2 이고 order 가 1이라면, 2 ^ (1 << 1) = 0 이 된다. 즉 order 1(page 2개가 묶음)에서 2번 page frame의 buddy는 0번 page frame이다. 

line 23 page index(page frame number) 기준으로 page 구조체 주소를 얻어 올 수 있다. 현재 해제 하려는 기준의 page 구조체는 parameter 로 받아왔으니 buddy 의 page 구조체를 구하는 것은 index 를 더하고 빼면 나올 것이다.

line 24 page_is_buddy() 함수에서 몇 가지를 check 한다.

  a. buddy page 가 유효한 page 인지 확인

  b. 현재 해제 요청한 page 와 buddy 가 같은 zone 에 있는 지 확인.

  c. buddy 의 order 가 해제 요청한 page 의 order 와 같은지 비교 및 guard 상태인지 확인.

      guard 상태의 확인은 kernel option에서 CONFIG_DEBUG_PAGEALLOC 가 enable 되어 있다면 뭔가 정보를 확인하겠지만 아니라면 무조건 false 를 return 한다.

buddy 가 맞고, 같은 order 의 free_list 에 있다면,

line 35~42 free_area[order] 의 nr_free 값을 하나 줄이고 buddy 의 page 속성 중 lru list 에서만 제거한다. 

  merge 는 위에서 보듯이 order 1의 index 2 의 요청이면 buddy가 0번 page 일 테고, merge 가 되면 0번 page 가 index 로 된다.(합쳐 졌으니)

그리고 상위 order 로 이동하여 위의 작업을 다시 하고, buddy check 에서 buddy가 아니거나 없으면 그만 둔다. 이 while loop 에서 최대한 상위 order 로의 merge 가 완료 된 후, 다음에 설명할 code 에서 실제 free_area 구조체에 정보를 update 한다.

free_area 정보 update code.

사실 위의 while 문 내부에서 현재 해제 시도에서 최상위 merge 까지 했다면 line 22 에 list_add 의 단 한 줄이면 정리가 끝난다. line 9~20 에 있는 내용이 잘 이해가 되지 않는다. :( (이부분의 내용도 __free_one_page() 함수 내부이다.) 그래도 code의 내용만을 보자면, 현재 계산된 order 가 합쳐질 수 있는 최상의 order 가 맞는지 확인하고(order 9), pfn_valid_within() 함수로 pfn 이 zone 내부에 있는 지 확인하는 것인데, zone 내부에 memory hole을 포함하고 있지 않다면 무조건 1 을 return 한다. 

line 10 ~ 15 위의 while 문과 아주 비슷한 행동을 하는데, 실제로 상위 order 의 free_area 를 확인해서 뭔가 처리하는 code가 아닌 그냥 확인용(?) 같은 느낌이 든다. 

line 15 에서 page_is_buddy 로 현재 구해진 order 에 +1 하여 상위 order 에 page buddy 를 확인해서 buddy page 가 같은 order 에 있는 상태를 확인했음에도 line 16 에서 free_area는 order + 1이 아니라 order 를 갖고 와서 적용한다. 한번 고민을 해봐야 할 듯 한 code이다.

일단 line 22 를 통해 계산된 order 의 free_area[order].free_list 에 page 를 잘 붙여 준다.

여기까지 buddy 초기화/할당/해제 를 알아봤다.

다음에는 할당하는 과정에서 memory 가 부족했을 경우에 수행되는 code를 살펴 보고자 한다.