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); 

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

 개발자로 살다보면, 어느 시점에는 내가 실력이 있는 건가 하는 고민을 한다. 사실 Open source project 에 참가하다보면 이렇게 잘하는 사람들이 넘치는데서 Software 개발을 하는 것이 맞는 일인지도 잘 모르겠다. 그래서 이런 저런 고민을 하고 찾다보니, 어디에서 연결된 페이지인지는 기억나진 않지만, 재미있는 Github project 를 발견했다.

 https://github.com/jwasham/coding-interview-university 여기에 가면, 작성하신 분이 Google 에 입사하기 위해 공부했던 내용의 리스트들을 만날 수 있다. 이런 공부를 통해 Google / Facebook / Amazon 이런 곳에 입사하면야 좋겠지만, 이런 공부들을 조금씩 하다보면 좋은 개발자라는 소릴 어디선가는 듣지 않을까하는 생각이다. 그리고 각종 언어로 번역중에 있다.(물론 한국어도 진행하시는 분이 있긴 하다.)

 개인적인 생각은 원래 그 사이트를 번역만 할 것이 아니라 한글 책 소개 / 한글 자막 영상/ 한국어 설명 영상이 있는 것이 링크 및 업데이트를 위해서 개인적으로 fork 해서 한글화 번역을 마무리 했다.(잘 되었다고 할 순 없지만, 답답하지 않을 정도 일 것이다.) https://github.com/daeseokyoun/google-interview-university [한글 번역]

원본을 보시면 더욱더 좋고, 더 잘 하신분의 번역을(완료가 되면-아직 작업중인 것으로 보인다) 보셔도 된다. 

원본: https://github.com/jwasham/coding-interview-university

번역[개인 저장소] : https://github.com/daeseokyoun/google-interview-university

What Can I Do For Mozilla

"What Can I Do For Mozilla" 라는 이름의 사이트가 있다.

https://www.whatcanidoformozilla.org/#!/progornoprog/teach

입장을 하면, 각종 질문이 주어지는데 그 카테고리에 맞는 Mozilla open source project 를 소개 해준다.

자신에 입맞에 맞는 open source project 를 찾아보고 싶다면 한번 이용해 보면 좋겠다.

Terminal File manger : Ranger

원문: https://www.digitalocean.com/community/tutorials/installing-and-using-ranger-a-terminal-file-manager-on-a-ubuntu-vps

소개

ubuntu terminal 에서 directory / file 을 키보드와 마우스(!!!) 이동/선택이 가능하다

설치법 (Ubuntu)

sudo apt-get update
sudo apt-get install ranger caca-utils highlight atool w3m poppler-utils mediainfo

실행은 terminal 에서 "ranger" 만 입력하면 되고, 종료는 'q' 입력하면 된다.

실행 시 모습은, 실행한 directory 기준으로 UI(?)가 보여진다.

마우스 클릭과 'VIM' 에서 사용하는 키이동으로 이동 가능하며, 엔터 입력시 text file 이 열리거나 X application 실행도 가능하다. (ex) PDF file 을 열면 acrobat reader 가 열린다.)

key binding

• j = 아래로 이동
• k = 위로 이동
• h = 상위 디렉토리로 이동
• gg = 현재 list 의 최상위로 이동
• G = 현재 list 의 최하위로 이동
• <ctrl>-f = 페이지 다운
• <ctrl>-b = 페이지 업
• J = 1/2 페이지 다운
• K = 1/2 페이지 업
• H = 히스토리의 "이전"으로 이동
• L = 히스토리의 "다음"으로 이동

• gh = cd ~
• ge = cd /etc
• gu = cd /usr
• gd = cd /dev
• go = cd /opt
• gv = cd /var
• gm = cd /media
• gM = cd /mnt
• gs = cd /srv
• gr = cd /
• gR = cd /usr/share/ranger/ranger (ubuntu 14.04 기준)

잘쓰면 좋은 툴이 될듯.

vim 에서 text 문서를 보거나, code 를 작성하고 관련 comment 를 영어로 남기는 경우에 spelling 확인하는 방법이 있다.

vim 7 버전에서 추가된 기능이며, 이후버전에서 간단히 사용 가능하다.

:set spell spelllang=en_us

spell 이 틀린 경우, 붉은색 박스로 표시된다.

아주 간단히 사용할 수 있는 vim tip.

원본 링크는: https://www.linux.com/learn/using-spell-checking-vim

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을 더욱더 견고하게 할 것이다.

Algorithm 문제 풀기(TopCoder, Hackerrank)

 다양한 사이트에서 알고리즘 문제를 풀고 만들어진 코드를 github project 로 올리고 있다. 아직 많이는 풀지 못했지만,

언젠가는 다양한 문제를 많이 올릴 수 있기를...

https://github.com/SolvingProblems/Code4Algorithm/tree/master/Daeseok.Youn

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 를 이용한 리눅스 커널 디버깅 방법들을 정리했다. 

[Google Codejam] Qualification Round 2014-Cookie Clicker Alpha

문제 link : https://code.google.com/codejam/contest/2974486/dashboard#s=p1

Magic Trick 에 이어 두번째 문제, Magic Trick 에 비하면 난이도가 있지만 쉬이 풀수 있는 문제이다.

이 문제의 결론은 X 값으로 주어진 cookie 의 개수를 가장 빠른 시간에 만들 수 있도록 하고 그 시간을 답으로 갖게 하는 것이다.

3 가지의 input 이 주어지는데,

C : farm 을 하나 만들 수 있는 cookie 의 개수

F : farm 하나 당 cookie 생산량

X : 최종으로 만들어야 하는 cookie 의 개수

문제의 link 를 보면 예제가 나와있다.

예제를 보면, 초기 cookie 생산량은 초당 "2" 이다.

가정 C = 500.0, F = 4.0, X = 2000.0

1. cookie 0개에서 부터 초당 2개씩 cookie 가 생산된다.

2. 250초 뒤에, 500개의 cookie 가 생산되고 farm 하나를 구입할 수 있다. 구입하게 되면 초당 4개의 cookie 를

생산하는 farm 을 만들 수 있다.

3. farm 을 하나 만들자. 그렇다면 보유하고 있던 cookie 의 개수는 0이 되고 초당 cookie 의 생산량은 6개가 된다.

4. 다음 farm 을 만들 수 있는 cookie 500개를 초당 6개씩 생산하였을 때, 83.3333333 초가 된다.

5. 83.333333 초 뒤에 farm 을 하나더 만들자. 그러면 다시 보유하고 있던 cookie 의 개수는 0이되고, 초당

10개의 cookie 생산량을 갖게된다.

6. 다음 farm 을 만들 수 있는 시간은 50초가 된다.

7. 3번째 farm 을 만들자. 다시 보유하고 있던 cookie 는 0이 되고, 생산량은 14개가 된다.

8. 생산량 14개에서 다음 farm 을 만들 필요는 없다. 왜냐 하면 이 이후의 생산량 증가는 2000개에 도달하는 시간이 점점 커진다. 이제 2000 개를 만들어 보자. 그러면 142.8571429 초가 걸린다.

총 시간은 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 초가 답이 된다.

앞서 쓴데로, C, F, X 가 input으로 주어지고 결과는 소수점 8자리에서 반올림하여 7자리를 만들면 된다.

중요한 점은,

farm 을 만들 것인지 만들지 않고 그냥 cookie 생산을 할 것인지 결정해야 하는 순간이 있다. 7번에서 8번으로 넘어갈때.

이것은 전 단계에서 X 까지 cookie 를 생산하여 걸린 시간과 현재 단계에서 farm 을 만들지 않고 cookie을 target 까지 생산한 값을 비교하여 전 단계에서 시간이 더 짧게 걸렸다면 farm을 만들지 않고 X 값까지 cookie 만든 시간을 return 하면 될 것이다.

코드를 보자.

def CalculateCookies(cookies, extra, target):
        cookieGen = 2 # default cookie
        if cookies > target:
                return target/cookieGen

        farmTime = 0.0
        prevEndTime = farmTime + target / cookieGen
        totalTimeFarm = 0.0

        while True:
                totalTimeFarm = totalTimeFarm + \
                                cookies / (cookieGen + extra * farmTime)
                farmTime = farmTime + 1.0
                currentEndTime = totalTimeFarm + \
                                 target / (cookieGen + extra * farmTime)

                if prevEndTime < currentEndTime:
                        break;
                prevEndTime = currentEndTime

        return prevEndTime

if __name__ == "__main__":
        testcases = input()
        for caseNr in xrange(1, testcases + 1):
                cookies, extra, target = map(float, raw_input().split())

                timeForCookies = CalculateCookies(cookies, extra, target)
                print "Case #%d: %.7f"% (caseNr, round(timeForCookies, 8))

코드가 간단하다. 계산만 잘하면 풀수 있는 문제일 것이다.