두찡의 일상

기존 알고리즘 사이트와 다르게, 제출 방식이 굉장히 까다로운 대회였다. 그래서 Practice Round 를 제공해 준듯 하고, 답은 기본적으로 두가지 스텝을 거쳐 제출 할 수 있었다. - Validation  주어진 input file 에 대해 올바른 output file 을 만들어 제출한다. 여기서 통과하면 실제로 제출 할 수 있다.- Submit  Validation 보다 큰 테스트케이스와 시간제한을 주고, 코드와 답을 제출해야 한다.  만약 시간제한이 지나면 다시 제출 할 수 없다. 그래서 이 대회의 주의점을 정리하면 다음과 같다.1. 미리 input, output file 처리를 만들어둔다2. 너무 오래걸리는 코드를 만들면 Submit phase 에서 주어진 시간 안에 제출 하지 못할 수 있다3..

4.8 kmalloc 과 vmalloc (p487)4.8.1 kmalloc과 vmalloc 의 특징구분kmallocvmalloc공통점커널에서 페이지 단위가 아닌 메모리를 할당 할당연속된 물리 메모리를 할당가상 메모리로 연속적인 것처럼 보이게 함4.8.2 GFP(Get Free Page) 플래그할당을 시도할 존을 지정페이지 MOBILITY와 장소 hint 관련 플래그워터마크 관련 플래그페이지 회수 관련 플래그액션 관련 플래그복합 GFP 플래그4.8.3 kmalloc 할당슬럽을 사용할때큰 크기나 DMA 요청에 대해서는 버디 시스템으로부터 페이지를 할당 (alloc_pages)그렇지 않은 경우, kmalloc kmem 캐시를 통해 메모리 할당 (slab_alloc)4-151 p491 include/linux/..

4.7.6 슬랩 객체 할당 (p449)4-137 p464 new_slab_objectsnode 의 partial list 를 cpu 캐시로 옮겨온다, 없는 경우 버디 시스템에서 할당 받는다.slub 에서 node 는 partial list 만 갖고 있고, cpu cache 에서는 freelist, page, partial 로 관리된다.freelist = get_partial() // cpu 캐시로 노드의 partial list 에서 가져오기if (freelist) return freelist;page = new_slab(s, flags, node); // 없는 경우 버디시스템에서 할당freelist = page->freelist // 첫 객체return freelist4-138 p467 get_parti..

4.7.5 p442 슬랩 페이지 할당slab 용으로 페이지를 할당받고, 슬랩 페이지로 사용할 수 있도록 초기화4-125 p443 mm/slub.c new_slab()새 페이지 할당 요청// allocate_slab 을 부를때 최초 생성할 수 있도록 플래그를 추가해서 요청allocate_slab(s, flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);4-126 p444 mm/slub.c allocate_slab() 페이지 획득시 권장 order 로 시도후 실패시 최소 order 로 시도// kmem_cache 구조체의 order_objects 인 oo 에는, 권장 order 와 객체수가 담겨있다.s->oo;첫번째 요청시에는 warning 과 retry 플래..

4-114create_kmalloc_cacheskmalloc 캐시를 CACHE_BYTES 부터 배수로 미리 생성3 부터 2의 배수로 사용하고 0,1 은 96, 192 사이즈KMALLOC_MIN_SIZE : 캐시 라인 크기4-115create_kmalloc_cachekmem_cache_zalloc: zalloc 은 0으로 모두 set 한다는 의미 -> 452 페이지에서 다시 나옴kmem_cache 구조체를 할당하기 위한 kmem_cache 객체를 사용. 이것 또한 keme_cache 를 받는 slab 에서 받아오는 것4.7.4 kmem 캐시 생성 (p426)4-116kmem_cache_createkmem 캐시를 생성4-117_kmem_cache_alias이전에 만들어둔 kmem 캐시와 병합이 가능하다면 해..

4-101, 102kswapd 는 페이지를 회수하는데, watermark_high 보다 올라가면 잠들고, low 보다 낮아지면 깨어나서 회수를 시작한다.min_free_kbytes 보다 높아질때까지 kswapd 는 메모리를 확보하고, min 보다 낮아지는 경우는 kswapd 에 의존하기만 하지 않고, 직접 페이지 수행을 시도해본다page_alloc.c __zone_watermark_okalloc_harder = highautomic 용도로 사용되는 reserve 페이지 블록에서도 할당free_pages 로 들어온 인자는 밖에서 zone_page_stage(z_ NR_FREE_PAGES)) 로 넘어온 값min = ? 여기에서 min 의 의미가 뭘까? -> 할당 성공률을 높인다고는 하는데,,min = mar..

4-96 __alloc_pages_slowpath__GFP_ATOMIC, __GFP_DIRECT_RECLAIM ATOMIC 은 저수준으로 sleep 없이 돌고 DIRECT_RECLAIM 은 sleep 하면서 회수를 해야 하는 상반되는 옵션따라서 ATOMIC 을 제거하고 돌게됨if (gfp_mask & __GFP_KSWAPD_RECLAIM) wake_all_kswapds(order, ac);이 플래그가 켜져있으면 모든 kswapd를 활성화 시켜서, zonelist 중 허용존의 kswapd 를 모두 깨운다.alloc flag 를 조절해줌. slow path 에 맞게 ->gft_to_alloc_flags --> 4-100cpuset 이 꺼저있는데, nodemask 도 없다 (전체 노드에 대한..

4.6 페이지 할당자 (356P) 노드별 활성화 된 존에서 페이지 할당이 실패한 경우에 대비해 fallback 에 대한 후보 존 리스트를 만든다. 4.6.2 NUMA 메모리 정책 (358P) Interleave: 해당 태스크에 구성된 노드 세트에서 순서대로 할당을 수행함 .. bind preferred default 4-81__build_all_zonelists -> 최초 실행시 모든 노드에 생성, 각 cpu 별 per-cpu 프레임 캐시 환경 구성 4-82 build_zonelists 모든 zone 을 돌면서 zone list 를 초기화 다른 노드를 순회하기 위해 비트마스킹으로, while 순회  * void nodes_clear(mask) clear all bits * node_order 에 node..

__free_one_page - 여기서 해제시 머지하는 부분은 이해가 됐음, - *다만 max_order, MAX_ORDER, pageblock_order 의 이해가 명확하지 않음* - buddy 할당자에서 struct page 의 Privatge 은 order 값으로 사용. (2^order 사이즈) - 상위 슬롯에서 버디를 발견하면 cold (뒤로 넣는다) static inline int page_is_buddy(struct page *page, struct page *buddy,unsigned int order) -> 이게 buddy 만 실제 buddy 로 Free 인지 검사하기 때문 ┌────────────────────┐└──▲──────────▲──────┘┌──┼──────┐┌──┼──────..

Page: 가상 메모리에서 사용되는 단위. Page Frame: 물리 메모리에서 사용되는 단위. PageDescriptor : PageFrame 의 상태 정보. memmap 으로 사용 페이지 지울때 static inline void rmv_page_order(struct page *page){__ClearPageBuddy(page);set_page_private(page, 0);}static inline void __ClearPageBuddy(struct page *page){VM_BUG_ON_PAGE(!PageBuddy(page), page);atomic_set(&page->_mapcount, -1);}page 의 private 변수는 여러 용도로 쓰이지만 버디에서는 이렇게 사용 - 버디 시스템에서 p..