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

간단히, 메모리 할당이 8 개 페이지 크기보다 같거나 작다면, vmalloc() 은 쓰지 않을 것이다. 그냥 될때까지(oom killer 도 돌고 요청완료할 때까지) 진행을 하고, 그 크기보다 클때는 vmalloc() 으로 메모리 할당을 대체 하겠다는 것이다.


이와 관련된 헬퍼 함수는 다음과 같다.

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



'Open Source Project' 카테고리의 다른 글

Mozilla open source project 찾기  (0) 2016.12.01

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

'Linux Kernel Study > Linux Weekly News - 번역' 카테고리의 다른 글

Extended system call error reporting  (0) 2015.11.27
[LWN] A taste of Rust  (0) 2013.04.27
[LWN 번역] Memory Compaction  (0) 2012.11.01

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


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


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


목차

chapter 1 들어가며


chapter 2 개발 환경 설정 
    2.1 기반 OS 선택 
    2.2 리눅스 배포판 선택    
    2.3 VirtualBox 설치    
    2.4 배포판 설치    
    2.5 리눅스 커널 개발 환경 만들기    
    2.6 이메일 계정 만들기    


chapter 3 리눅스 커널 빌드하기    
    3.1 리눅스 커널 타깃 설정    
    3.2 리눅스 커널 옵션 설정    
    3.3 빌드하기    
    3.4 다른 아키텍처로 빌드하기    


chapter 4 리눅스 커널 패치의 라이프 사이클    
    4.1 패치의 라이프 사이클    
    4.2 개발자별 커밋 통계 확인    


chapter 5 리눅스 커널의 코딩 스타일 고치기    
    5.1 개발용 리눅스 커널 브랜치 준비    
    5.2 리눅스 커널의 코딩 스타일    
    5.3 코딩 스타일 고치기    
    5.4 Gmail로 답장쓰기    


chapter 6 좋은 패치 만들기    
    6.1 작업 단위의 로컬 브랜치 만들기    
    6.2 CC 추가와 불필요한 헤더 지우기    
    6.3 알맞은 브랜치에서 개발하기    
    6.4 패치 작게 만들기    
    6.5 하나의 패치를 두 개로 분리하기    
    6.6 둘 이상의 패치를 하나로 합치기    
    6.7 패치에 코멘트 남기기    
    6.8 패치 Versioning 
    6.9 패치 Rebase    
    6.10 커버 패치 만들기    
    6.11 패치 시리즈 중 일부 패치만 수정하기    
    6.12 다른 개발자의 패치 다운로드와 적용    


chapter 7 리눅스 커널 메일링 리스트 구독하기    
    7.1 메일링 리스트 선택하기    
    7.2 메일링 리스트 구독하기    
    7.3 라벨 만들기    
    7.4 필터 설정하기    


chapter 8 정적 코드 분석 도구 사용하기    
    8.1 Sparse    
    8.2 Smatch    
    8.3 Coccinelle    


chapter 9 정적 코드 분석 도구로 패치 만들기    
    9.1 Sparse로 로그 분석하기    
    9.2 Smatch로 로그 분석하기    
    9.3 Coccinelle로 로그 분석하기    


chapter 10 QEMU로 리눅스 커널 디버깅하기    
    10.1 QEMU 설치    
    10.2 QEMU로 리눅스 커널 부팅하기    
    10.3 GDB를 연결해 리눅스 커널 디버깅하기    
    10.4 루트 파일 시스템 만들기    
    10.5 루트 파일 시스템에 실행 바이너리 추가하기    
    10.6 Linux Test Project    


chapter 11 참고용 사이트   
    11.1 LWN.net   
    11.2 kernelnewbies.org   
    11.3 Git 연습과 이해    
    11.4 기타


chapter 12 맺음말


현재는 한빛 미디어 E-Book 카테고리에 등록이 되어 있으며, 구매 시 PDF 로 받아 볼 수 있다.

링크는 : http://www.hanbit.co.kr/ebook/look.html?isbn=9788968487453


많은 사람들이 리눅스 커널 오픈소스에 커밋하고 흥미를 느꼈으면 한다.





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


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



[Google Codejam] Qualification Round 2014-Magic Trick


문제 link : https://code.google.com/codejam/contest/dashboard?c=2974486


Google Codejam 이 시작되었다. 참가는 하지 않았지만, 하나씩 풀어 보려고 노력중이다.

이 문제는 처음 시작하는 사람들에게 자신감을 줄 수 있는 문제가 아닌가 한다. :-)


문제의 내용을 요약하면,

마술사가 1~16까지의 수가 적힌 카드를 갖고 4X4 로 무작위(사실 마술사가 트릭을 쓴다는 내용이다. 실제 무작위가 아님)로 배열한뒤 지원자가 선택한 카드가 무엇인지 맞추는 문제이다.


Rule 과 함께 예제를 들면,

1. 마술사가 1~16 까지 숫자를 4X4로 놓는다.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16


2. 지원자가 원하는 숫자가 어느 열에 있는지 물어본다.

예를 들어 지원자는 7을 생각했고 마술사에게 "2"열이라고 답해준다.


3. 마술사가 카드를 썪어 다시 한번 놓게된다.

1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16


4. 그럼 지원자는 "3" 열이라고 마술사에게 얘길 하고, 마술사는 지원자가 생각한 숫자 7을 말해주면 된다.


이는 마술사가 1번째와 2번째 카드 배열시 "Trick"을 써 지원자의 생각한 숫자를 맞추는 것이다.

(이런걸 속을 수 있나.. 지원자도 말하면서 눈치를 챌듯..)


이렇게 정상적인 case 만 있는 것은 아니다. 지원자가 실제 위의 예제에서 마술사가 2번째로 카드를 배열했을 때

3열이라고 답해야 하지만, 2열이라고 답하게 되었다면 "Volunteer cheated!" 출력하고,

마술사가 2번째 배열에서 5,6,7,8 을 다른 열로 분리를 해야 하는데, 하나이상 같은 열에 놓게 되어 맞출수 없는 경우에는

"Bad magician!" 이라고 출력하면 이 문제는 완전히 풀수 있게 된다.


문제 link 를 가면, Sample case 가 잘 나와있다. 


일단 Google Codejam 은 input data file을 제공한다. 이 파일을 받아서 code의 input으로 사용하면된다.

input 파일의 한라인씩 읽는다고 했을때,

첫번째 배열에서 지원자가 말한 열(5, 6, 7, 8) 을 저장해놓고 다음 배열에서 말한 (9, 10, 7, 12)를 단순 비교한다


만약

1. 같은 숫자가 하나 라면, 그 값을 return 한다.

2. 같은 숫자가 2 이상 4 이하라면 "Bad magician!" 을 return 한다.

3. 같은 숫자가 하나도 없으면 "Volunteer cheated!" 를 return 한다.


끝.


파일을 첨부하는데 문제가 있어, code를 붙여 넣는다.

def checkCards(first, second):
    sameCount = 0
    sameNum = ""

    for num in range(0, len(first)):
        for snum in range(0, len(second)):
            if first[num] == second[snum]:
                sameCount = sameCount + 1
                sameNum = first[num]

    if sameCount == 1:
        return sameNum
    elif sameCount > 1 and sameCount <= 4:
        return "Bad magician!"
    elif sameCount == 0:
        return "Volunteer cheated!"

    # never reach hear with data from codejam
    return "error"

if __name__ == "__main__":
    testcases = input()
    LineOfCardsFirst = []
    LineOfCardsSeconds = []
    for caseNr in xrange(1, testcases + 1):
        for num in range(0,2):
            selectRow = raw_input()
            #print "selected Row : ", selectRow
            for row in xrange(0, 4):
                if row == int(selectRow) - 1:
                    if (num == 0):
                        LineOfCardsFirst = map(int, raw_input().split())
                        #print "LineOfCards : ", LineOfCardsFirst
                    else:
                        LineOfCardsSeconds = map(int, raw_input().split())
                        #print "LineOfCards : ", LineOfCardsSeconds
                else:
                    raw_input()
 

      print("Case #%i: %s" % (caseNr, checkCards(LineOfCardsFirst, LineOfCardsSeconds)))


Git: 특정 commit 으로 이동 후, amend 하기


Git 으로 local branch 를 생성 한 후, 특정 source 를 수정함에 있어 여러개의 commit 이 만들어 질 수 있다.

이 때, 기존에 했던 commit 에 추가적인 수정을 하려면 git add/commit --amend 를 하면 되는데 최상위에 있는

commit 은 바로 수정 후, git add/git commit --amend 하면 적용이 되지만 현재 수정하려는 내용이 이전에 있던 commit 에 반영되었으면 하는 경우가 발생한다.


예를 들어, 아래와 같이 commit 들이 있다고 가정하자.

commit ec88cc08f5a29f98a3c5f14ca642f235fb1c0fb8

Author: Daeseok Youn <daeseok.youn@gmail.com>

Date:   Fri Feb 28 15:34:22 2014 +0900


    staging: cxt1e1: fix checkpatch errors with open brace '{'


    clean up checkpatch.pl error:

     ERROR: that open brace { should be on the previous line


    Signed-off-by: Daeseok Youn <daeseok.youn@gmail.com>


commit 6007a41fffd430b79775871a2c9eb6c35eb3e6a6

Author: Daeseok Youn <daeseok.youn@gmail.com>

Date:   Fri Feb 28 15:27:51 2014 +0900


    staging: cxt1e1: fix checkpatch error 'assignment in if condition'


    checkpatch.pl error:

     ERROR: do not use assignment in if condition


    Signed-off-by: Daeseok Youn <daeseok.youn@gmail.com>


commit aa877600a98048d056b65d0c9e7426616e9ccc2f

Author: Daeseok Youn <daeseok.youn@gmail.com>

Date:   Fri Feb 28 15:22:13 2014 +0900


    Staging: cxt1e1: Fix line length over 80 characters in hwprobe.c


    clean up checkpatch.pl warnings:

     WARNING: Line length over 80 characters


    Signed-off-by: Daeseok Youn <daeseok.youn@gmail.com>


commit 2f61d921981a45c687e5dc26d6f7e6a3925ca0e5

Author: Daeseok Youn <daeseok.youn@gmail.com>

Date:   Fri Feb 28 15:14:39 2014 +0900


    staging: cxt1e1: Fix no spaces at the start of a line in hwprobe.c


    clean up checkpatch.pl warnings:

    WARNING: please no spaces at the start of a line in


    Signed-off-by: Daeseok Youn <daeseok.youn@gmail.com>


이 때, 추가적인 수정사항이 발생 되었는데, 이 내용이 맨 아래에 있는 "staging: cxt1e1: Fix no spaces at the start of a line in hwprobe.c" 에 적용되었으면 하는 바램이 생겼다.


그렇다면, 일단 그 commit 을 수정할 수 있는 mode(?) 로 가야한다.

$ git rebase --interactive 2f61d921981a45c687e5dc26d6f7e6a3925ca0e5^

라고 한다. 맨 마지막에 "^" 를 넣어줘야 그 commit 을 포함하여 rebase  를 진행한다.


위에서 처럼 입력하면, 나의 경우는 vim 이 열리면서 아래와 같은 내용이 입력된다.

pick 2f61d92 staging: cxt1e1: Fix no spaces at the start of a line in hwprobe.c

pick aa87760 Staging: cxt1e1: Fix line length over 80 characters in hwprobe.c

pick 6007a41 staging: cxt1e1: fix checkpatch error 'assignment in if condition'

pick ec88cc0 staging: cxt1e1: fix checkpatch errors with open brace '{'


# Rebase b9ea35b..ec88cc0 onto b9ea35b

#

# Commands:

#  p, pick = use commit

#  r, reword = use commit, but edit the commit message

#  e, edit = use commit, but stop for amending

#  s, squash = use commit, but meld into previous commit

#  f, fixup = like "squash", but discard this commit's log message

#  x, exec = run command (the rest of the line) using shell

#

# If you remove a line here THAT COMMIT WILL BE LOST.

# However, if you remove everything, the rebase will be aborted.

#


여기서 내가 수정하고 싶은 것은 맨 위에 있는 commit 이다. "pick" 을 "edit" 로 변경하고 저장 하고 나와 git log를 하면

최상위에 그 commit 이 올라와 있다. 


이제 원하던 수정을 하자.


수정이 완료되면,

$ git add <file>

$ git commit --amend


이렇게 하면 일단 현재 원하던 commit 에 추가 반영이 된다.


이제 원래 갖고 있던 commit 들을 복구 해야 한다.

$ git rebase --continue


이렇게 하면 수정한 commit 이 후에 생성된 commit 들을 merge 하기 시작한다. 하나씩 merge 를 하다가 conflict 날 수 있다.

그러면 rebase 가 중지 되고, conflict 를 해결 한 후에 다시 git rebase --continue 를 입력하라고 한다.


이렇게 해서 마지막으로

Successfully rebased and updated ref/heads/<local branch name>

이라고 나오면 성공한 것이다.



'Development Tip' 카테고리의 다른 글

VIM 에서 spelling 확인하기  (0) 2016.07.08
Git add -p 로 수정사항 분리하기  (0) 2014.04.16
const char* vs. char const*  (0) 2014.02.19
Fish shell environment  (0) 2013.12.03
Kernel mailing list 활용 방법  (0) 2013.11.08

const char* vs. char const*


code 를 보다 보니 C/C++ 에서 사용하는 const 에 대한 내용은 알고 있지만, 막상 보면 어디가 상수로 결정되어 수정될 수 없는지 계속 찾아 보게된다. 


그래서 검색을 해보았더니, 예제로 잘 정리된 내용이 있어 갖고 왔다.

original url : http://stackoverflow.com/questions/162480/const-int-vs-int-const-as-function-parameter-in-c-and-c


아래서 처럼 const int 와 int const 는 같은 의미로 사용되어 진다.

const int a = 1; // read as "a is an integer which is constant"
int const a = 1; // read as "a is a constant integer"

그래서 아래와 같이 2를 넣을 수 없다.

a = 2; // Can't do because a is constant

하지만 pointer 변수일 때는 다르게 해석이 되는데, 하나는 주소값을 변경하지 못하는 것과 다른 하나는 주소가 가리키고 있는 값의 변경을 할 수 없는 것이다. 아래의 주석을 잘 읽어보면 이해가 될 것이다.

const char *s;      // read as "s is a pointer to a char that is constant"
char c;
char *const t = &c; // read as "t is a constant pointer to a char"

*s = 'A'; // Can't do because the char is constant
s++;      // Can do because the pointer isn't constant
*t = 'A'; // Can do because the char isn't constant
t++;      // Can't do because the pointer is constant


Install Fish Shell on Ubuntu


Fish shell 이라는 것이 생겼다. 이 shell 의 가장 큰 특징은 자동 완성기능인데, 특정 command 의 man page를 parsing 해서 option 까지 자동완성해준다. 기본적으로 현재 typing 하고 있는 command 의 hint 기능도 있다. 


또 하나 큰 특징은 shell 에서 script 작성 및 실행이 가능하다는 것이다.(command line 에서 편집기 editor 처럼 동작이 가능하다는 것이다!) 


이러한 모든 기능의 설명은 http://fishshell.com/docs/current/index.html 에서 확인할 수 있다.


여기서는 ubuntu 에 fish shell 의 설치 방법과 간단한 기능들을 살펴 본다.

(Bash shell 에서 지원하는 것은 일단 다 지원하는 듯 하다)


1. Installation.

sudo apt-add-repository ppa:fish-shell/release-2

$ sudo apt-get update

$ sudo apt-get install fish


2. 실행

$ fish


3. 기본 shell 로 등록

$ chsh -s /usr/bin/fish


2 번 실행으로 사용하다가 괜찮다 싶으면 기본 shell 로 등록해서 사용하면 될 것이다.


4. Commands hint



위에 그림 처럼 최근 history base 로 vi 를 입력했을 때 회색으로 되어 있는 부분이 자동 완성 될 문장이다. 간단히 화살표 오른쪽을 누르면 그  command 를 바로 이용할 수 있다.(화살표 위/아래를 하면 vi 와 관련된 history command 들간 이동이 가능하다.)


5. Edit script



쉘에서 바로 script 를 작성할 수 있다. 위의 그림처럼 간단히 작성 가능하고 위/아래로 움직여서 수정도 가능하다. 정말 editor 처럼 동작한다.

실제 예로는 현재 시점에서 prompt 모양을 변경할 경우 이렇게도 사용할 수 있을 것이다.

(나머지는 http://fishshell.com/docs/current/index.html 으로 이동해서 확인 바란다.)


'Development Tip' 카테고리의 다른 글

Git: 특정 commit 으로 이동 후, amend 하기  (0) 2014.02.28
const char* vs. char const*  (0) 2014.02.19
Kernel mailing list 활용 방법  (0) 2013.11.08
PuTTY 설정 값 공유하는 방법  (0) 2013.10.07
Git with eclipse  (0) 2013.04.04

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 를 받자.

$ mkdir ~/work/Kernel

$ cd ~/work/Kernel

$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git


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


  - kernel build

$ make ARCH=i386 menuconfig

   다른 것들은 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


$ make ARCH=i386 -j4


2. qemu 준비
 - Ubuntu 의 경우

sudo apt-get install qemu qemu-system


3. kernel 부팅.(x86_64 system)

$ qemu-system-x86_64 -no-kvm -kernel arch/x86/boot/bzImage -hda /dev/zero -append "root=/dev/zero console=ttyS0" -serial stdio

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


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

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


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

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


4. gdb 연결

$ qemu-system-x86_64 -s -S -no-kvm -kernel arch/x86/boot/bzImage -hda /dev/zero -append "root=/dev/zero console=ttyS0" -serial stdio


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

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


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

$ cd ~/work/Kernel/linux/

$ gdb ./vmlinux

GNU gdb (Ubuntu/Linaro 7.4-2012.04-0ubuntu2.1) 7.4-2012.04

Copyright (C) 2012 Free Software Foundation, Inc.

License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>

This is free software: you are free to change and redistribute it.

There is NO WARRANTY, to the extent permitted by law.  Type "show copying"

and "show warranty" for details.

This GDB was configured as "x86_64-linux-gnu".

For bug reporting instructions, please see:

<http://bugs.launchpad.net/gdb-linaro/>...

Reading symbols from /home/daeseok/work/Kernel/linux/vmlinux...done.

(gdb) target remote localhost:1234

Remote debugging using localhost:1234

0x0000fff0 in ?? ()


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

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

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

(gdb) b start_kernel

Breakpoint 1 at 0xc18cb6f2: file init/main.c, line 484.

(gdb) c

Continuing.


Breakpoint 1, start_kernel () at init/main.c:484

484 {

(gdb)


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

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


(gdb) list

479 pgtable_init();

480 vmalloc_init();

481 }

482

483 asmlinkage void __init start_kernel(void)

484 {

485 char * command_line;

486 extern const struct kernel_param __start___param[], __stop___param[];

487

488 /*


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

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 이걸 받았다.

$ mkdir ~/work/rootfs_qemu

$ tar zxf core-image-minimal-dev-qemux86.tar.bz2 -C ~/work/rootfs_qemu


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

bin  boot  dev  etc  home  lib  media  mnt  proc  sbin  sys  tmp  usr  var


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

$ BLOCKS=$(((1024*$(du -m -s rootfs | awk '{print $1}')*12)/10))

$ genext2fs -z -d rootfs_qemu -b $BLOCKS -i 1024 rootfs.ext3

$ resize2fs rootfs.ext3 1G

$ tune2fs -j -c 0 -i 0 rootfs.ext3

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


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

qemu-system-x86_64 -no-kvm -kernel arch/x86/boot/bzImage -hda ~/work/rootfs.ext3 -append "root=/dev/sda console=ttyS0" -serial stdio 


부팅을 다하면,

.....

Starting system message bus: dbus.

Starting syslogd/klogd: done

Stopping Bootlog daemon: bootlogd.


Yocto (Built by Poky 7.0.1) 1.2.1 qemux86 ttyS0


qemux86 login: 


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


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


6. cgdb

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

$ sudo apt-get install cgdb


사용은, 

$ cgdb ./vmlinux

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



위의 예제는

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

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

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


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



+ Recent posts