[커널 17차] 57주차

2021.10.04 02:07

ㅇㅇㅇ 조회 수:66

구조체 align 크기 결정

 

struct A {
    char a;
    int b;
};

align(A) = align(b) = 4;

제일 큰 놈으로 align 된다

flexible struct인 경우 align 기준에 실제 없는 trailing array member size도 추가된다

struct A {
    int a;
    long b[];
};

이 경우 long도 struct A의 sizeof를 정하는 데 추가된다

The following statements are almost equivalent:

a = x ?: y;
a = x ? x : y;


percpu 이론
- http://jake.dothome.co.kr/per-cpu/
- http://jake.dothome.co.kr/setup_per_cpu_areas/


pcpu_setup_first_chunk()
- alloc info와 base addr를 인자로 받아서 reserved 및 dynamic 영역을 관리하는 1st chunk를 setup한다
- static 영역의 경우 kernel image의 percpu static 영역을 copy함으로써 setup이 이미 완료됨

- 인자에 대한 sanity check 수행
- 각 group의 base_offset을 나타내는 group_offsets, 각 group의 크기를 나타내는 group_sizes, 각 cpu가 몇 번째 unit에 해당하는지 나타내는 unit_map, 각 cpu의 base_offset을 나타내는 unit_off 배열에 대해 memblock으로 메모리를 할당한다
- alloc_info를 이용해서 각 group에 대해 group_offsets, group_sizes를 업데이트하고 각 cpu별로 unit_map, unit_off를 채운다
- cpu 중 가장 작은 offset을 가지는 cpu를 pcpu_low_unit_cpu로 기록하고, 가장 큰 offset을 가지는 cpu를 pcpu_high_unit_cpu로 기록한다
- percpu 관련 전역 변수들을 업데이트한다


1) pcpu_nr_units에 총 unit 수를 기록한다
2) pcpu_nr_groups에 총 group 개수를 기록한다
3) pcpu_group_offsets, pcpu_group_sizes, pcpu_unit_map, pcpu_unit_offsets가 각각 group_offsets, group_sizes, unit_map, unit_off 배열을 가리키게 한다
4) pcpu_unit_pages에 unit 당 page 수를 기록한다
5) pcpu_unit_size에 unit 크기를 기록한다
6) pcpu_atom_size에 atom_size를 기록한다
7) pcpu_chunk_struct_size에 구조체 pcpu_chunk와 trailing array populated를 위한 메모리 사이즈를 계산하여 기록한다. populated는 populated page를 나타내는 bitmap으로 1 bit 당 1개 page를 표시한다.


- pcpu_stats_save_ai() 함수는 디버깅 용 함수
- dynamic 영역을 관리하기 위한 chunk slot을 초기화한다. chunk slot은 list_head로 각 slot에 해당하는 chunk들을 linked list로 연결하여 관리한다. chunk가 어느 slot에 연결되는지는 free size에 연관되는 것으로 보임
- chunk slot의 개수와 최대 크기는 unit size에 의해 결정되며 16 바이트 미만은 slot 1번, 32 바이트 미만은 slot 2번, 64 바이트 미만은 slot 3번, …, 이런 식으로 두 배 크기 씩 slot index가 결정된다. unit size에 의해 N번 slot이 결정되면 실제로는 1번부터 N번 slot까지 사용되는 것으로 보이며 0번과 N+1번은 빈 slot이나 메모리 할당은 받는다.
- 결론적으로 unit size에 따라 필요한 slot 수를 산출하여 전역 변수 pcpu_nr_slots에 저장한다
- chunk type에는 root type과 cgroup에서 관리하는 memcg type이 있으며 config에 따라 mercy type은 없을 수도 있다. 두 type 모두 있는 경우에는 chunk slot을 두 배로 memblock 할당하여 전역변수 pcpu_chunk_lists가 가리키도록 한다. 이후 pcpu_chunk_lists의 각 list_head를 초기화 한다
- static_size를 4 바이트 단위로 align 하고 dynamic size를 static size가 align up 된 수치만큼 감소시킨다
- reserved 영역이 있는 경우에는 reserved 영역에 대한 1st chunk를 allocation하고 그 후 dynamic 영역에 대한  1st chunk를 allocation한다. chunk allocation을 위해서는 함수 pcpu_alloc_first_chunk()를 호출한다.
- 만들어진 reserved_chunk를 전역변수 pcpu_reserved_chunk에 할당하고, 만들어진 dynamic chunk는 전역 변수 pcpu_first_chunk에 할당한다


pcpu_alloc_first_chunk()
- 시작 주소와 사이즈를 인수로 받아서 1st chunk를 allocation한다

- 시작 주소와 끝 주소를 모두 page align 시키고 원래 시작 주소와 끝 주소 사이를 offset 영역으로 둔다
- 시작 주소가 aligned_addr, 원래 시작 주소가 start_offset, 전체 사이즈가 region_size, 원래 끝 주소에서 끝 주소까지의 크기가 end_offset이다.
- pcpu_chunk 구조체를 위한 메모리를 memblock으로 할당한다. pcpu_chunk 구조체 끝에 trailing array populated[]가 존재하므로 해당 배열을 위한 메모리도 더해서 할당한다. 해당 배열은 페이지 당 1bit로 표현하는 bitmap이다.
- slot list head에 연결할 chunk list head를 초기화한다
- chunk->base_addr를 aligned 시작 주소로 초기화한다
- chunk->start_offset은 start_offset으로 초기화
- chunk->end_offset도 end_offset 크기로 초기화한다
- chunk->nr_pages는 region_size를 페이지 사이즈로 나눈 값으로 초기화한다
- chunk 페이지 전체 사이즈를 4 바이트로 나누어 region_bits를 계산한다
- chunk->alloc_map을 위한 메모리를 할당한다. alloc_map은 chunk 전체 영역을 4B 단위로 free/non-free를 비트맵으로 나타낸 것으로 0이 free, 1이 non-free를 나타낸다. 4B 단위로 관리하므로 위에서 게산한 region_bits로 비트맵 사이즈를 계산한다
- chunk->bound_map을 위한 메모리를 할당한다. bound_map은 offset/free/non-free 영역의 경계점을 나타내는 bitmap으로 4 바이트 단위로 비트를 표시하며, offset/free/non-free 영역의 시작 비트만 1로 나머지는 0으로 표시한다. 그리고 가장 마지막에 1비트를 추가하여 마지막 지점도 1로 표시한다. 4 바이트 단위로 관리하고 마지막 1개 비트가 있으므로 위에서 계산한 region_bits + 1로 비트맵 사이즈를 계산한다
- chunk->md_block을 위한 메모리를 할당한다. md_block은 meta data block으로 chunk를 구성하는 각 page의 메타 데이터 정보 (contig_hint, contig_hint_start, first_free, left_free, right_free, scan_hint, scan_hint_start  등)를 저장함. 따라서 페이지 개수 만큼의 md_block 크기를 메모리 할당함
- contig_hint : 해당 페이지 내에서 가장 긴 연속된 free 영역 길이
- contig_hnt_start : 해당 페이지 내에서 가장 긴 연속된 free 영역 시작 지점
- first_free : 해당 페이지 내에 처음으로 나타나는 free 영역 시작 지점
- left_free : 해당 페이지의 가장 왼쪽 지점이 free이면 1 아니면 0
- right free : 해당 페이지의 가장 오른쪽 지점이 free이면 1 아니면 0
- scan_hint : 해당 페이지 내에서 두 번째로 길고 contig_hint 영역보다 왼쪽에 있는 연속된 free 영역 길이
- scan_hint_start : 해당 페이지 내에서 두 번째로 길고 contig_hint 영역보다 왼쪽에 있는 연속된 free 영역 시작 지점
- chunk->obj_cgroups = NULL 로 하여 1st chunk는 memcg-ware가 아님을 표시한다
- 함수 pcpu_init_md_blocks()로 chunk의 md_block들을 초기화한다
- chunk->immutable = true
- 함수 bitmap_fill로 chunk->popluated[] 비트맵을 all 1으로 초기화한다
- chunk->nr_populated = chunk->nr_pages
- chunk->nr_empty_pop_pages = chunk->nr_pages
- chunk->free_bytes = map_size (offset을 제외한 실제 chunk 사이즈)
- chunk에 start_offset이 존재할 경우에는 다음을 수행한다

- chunk->start_offset을 4 바이트로 나누어서 비트맵상 offset 크기 offset_bits를 구한다
- 함수 bitmap_set()을 이용하여 chunk->alloc_map의 0번째 부터 offset_bits 만큼 비트맵을 1로 세팅한다. 따라서 start offset 영역은 allocation 되어 있는 것으로 취급되어 사용 불가능하다
- set_bit() 함수로 chunk->bound_map 비트맵의 첫 번째 비트를 1로 세팅하여 start offset 시작 경계선을 표시한다
- set_bit() 함수로 chunk->bound_map 비트맵의 offset_bits 번째 비트를 1로 세팅하여 start offset 다음 영역의 시작 경계선을 표시한다
- chunk의 first_free를 offset_bits로 표시한다
- 함수 pcpu_block_update_hint_alloc()로 0번째 부터 offset_bits까지 지점이 offset 영역으로 allocation되었으므로 hint 데이터 (contig, scan) 들을 업데이트한다.

- chunk에 end_offset이 존재할 경우에는 다음을 수행한다

- chunk->end_offset을 4 바이트로 나누어서 비트맵상 offset 크기 offset_bits를 구한다
- 함수 bitmap_set()을 이용하여 chunk->alloc_map의 마지막 offset_bits 만큼 비트맵을 1로 세팅한다. 따라서 end offset 영역은 allocation 되어 있는 것으로 취급되어 사용 불가능하다
- set_bit() 함수로 chunk->bound_map 비트맵의 end offset 시작 비트를 1로 세팅하여 end offset 시작 경계선을 표시한다
- set_bit() 함수로 chunk->bound_map 비트맵의 region_bits 번째 비트를 1로 세팅하여 chunk 영역의 끝 경계선을 표시한다
- 함수 pcpu_block_update_hint_alloc()로 마지막 offset_bits 영역이 allocation되었으므로 hint 데이터 (contig, scan) 들을 업데이트한다.

- 만들어진 1st chunk를 리턴한다


pcpu_init_md_blocks()
- meta datablock들은 chunk 자체에 대한 md_block과 chunk에 속한 페이지들의 md_block을 초기화한다.
- 함수 pcpu_init_md_block()를 이용해서 md_block 1개를 초기화한다
- 우선 chunk 자체 md_block인 chunk->chunk_md를 초기화하고 각 페이지들의 md_block을 루프를 돌면서 초기화한다


pcpu_init_md_block()
- 특정 md_block 1개를 아래와 같이 초기화한다
- scan_hint, first_free = 0
- contig_hint, left_free, right_free, nr_bits = nr_bits


pcpu_block_update_hint_alloc()
- 인자로 chunk, chunk의 bitmap 시작 offset, bitmap상 비트수(bits)를 받아서 시작 offset에서 비트수만큼 영역에 대한 hint를 업데이트한다

- 시작 offset과 bits를 이용해서 시작 block과 끝 block index 및 offset을 계산하고, 시작 block과 끝 block을 구한다
- 시작 block = s_block, 시작 block index = s_index, 시작 block 내의 offset = s_off, 끝 block = e_block, 끝 block index = e_index, 끝 block offset = e_off

 

- 시작 block(=s_block)을 업데이트한다
1) s_block->contig_hint가 비트맵 전체이면 nr_empty_pages++ 수행. nr_empty_pages는 새로 allocation된 page 중에서 원래는 empty 였던 page가 몇 개인지를 나타낸다
2) s_off == s_block->first_free이면 원래 1st free였던 곳이 allocation되었으므로 first_free를 find_next_zero_bit() 함수로 다음 first free를 찾아 업데이트한다
3) s_block의 scan_hint 영역이 allocation 영역과 겹치는 지 확인하고 겹치면 scan_hint를 무효화한다.
4) s_block의 contig_hint 영역이 allocation 영역과 겹치는 지 확인하고 겹치면 함수 pcpu_block_refresh_hint()로 s_block의 hint를 refresh한다. 또한 s_off이 0이면 시작 지점이 allocation되므로 left_free도 0으로 세팅한다.
5) s_block의 contig_hint 영역이 allocation과 겹치지 않으면 left_free와 right_free만 체크한다. left_free는 기존의 left_free와 s_off 중 작은 값으로 세팅한다. s_block과 e_block이 다르면 right_free는 0으로 설정한다. 만약 같으면 기존의 right_free와 e_off부터 block 끝 영역 크기 중 작은 값으로 세팅한다.

 

- 마지막 block (=e_block)을 업데이트한다
1) s_index == e_index이면 이미 s_block = e_block을 업데이트했으므로 그냥 넘어간다
2) e_block->contig_hint가 비트맵 전체이면 nr_empty_pages++ 수행한다
3) find_next_zero_bit() 함수로 e_off 다음 영역에서 처음으로 나오는 zero bit을 찾아서 first_free를 업데이트한다
4) e_off가 마지막 비트이면 e_block 전체가 allocation되었으므로 e_block++ 하여 중간 block들과 함께 e_block을 처리한다
5) e_off가 마지막 비트가 아니면 다음을 수행한다
    - e_off가 scan_hint_start를 넘어가면 scan_hint가 더이상 유효하지 않으므로 scan_hint = 0으로 한다
    - e_block은 항상 왼쪽이 allocation되어 있으므로 left_free는 항상 0으로 한다
    - e_off가 contig_hint_start를 넘어가면 contig_hint가 깨졌으므로 함수 pcpu_block_refresh_hint()로 hint 데이터들을 업데이트한다
    - e_off가 contig_hint_start를 안 넘어가면 기존의 right_free와 e_block 마지막과 e_off 사이의 크기 중 작은 값으로 업데이트 한다

6) s_block과 e_block 사이의 block들을 모두 세서 nr_empty_pages에 추가한다
7) 중간 block들에 대해서 scan_hint, contig_hint, left_free, right_free를 모두 0으로 세팅한다

 

- nr_empty_pages가 1 이상이면 pcpu_update_empty_pages() 함수로 chunk 자료구조의 nr_empty_pop_pages를 nr_empty_pages 만큼 감소시킨다.
- allocation 영역이 chunk 전체를 관리하는 chunk_md의 scan_hint 영역과 겹치면 chunk_md의 scan_hint를 0으로 무효화한다
- allocation 영역이 chunk_md의 contig_hint 영역과 겹치면 함수 pcpu_chunk_refresh_hint()로 chunk 전체를 scan해서 hint를 업데이트한다
- 이후 리턴


pcpu_update_empty_pages()
- 인자로 chunk와 nr 값을 받아서 chunk->nr_empty_pop_pages를 nr 만큼 증가시킨다. 음수를 받으면 감소된다.
- chunk가 reserved_chunk가 아니면 전역 변수 pcpu_nr_empty_pop_pages도 똑같이 업데이트한다. reserved 영역은 module이 관리하는 듯


pcpu_block_refresh_hint()
- chunk와 block index를 인자로 받아 해당 block의 metadata hint를 업데이트한다

- 여기로 들어왔다는 것은 일단 contig_hint가 broken되었다는 것을 의미한다
- index로부터 해당 block과 block에 대한 alloc_map을 설정한다
- 해당 block에 scan_hint가 broken되지 않은 경우 broken된 contig_hint 대신 scan_hint를 새 contig_hint로 변경한다. 그리고 scan_hint를 무효화하고 scan할 첫 위치를 새 contig_hint 영역 다음으로 잡는다
- 만약 block의 scan_hint가 broken된 경우 contig_hint = 0으로 무효화하고 scan 시작 지점을 block의 first_free 지점으로 잡는다
- block의 right_free 지점은 0으로 무효화한다
- bitmap_for_each_clear_region() 매크로로 alloc_map에서 free 영역을 iterate하면서 각 free 영역에 대해 함수 pcpu_block_update()로 block의 meta data (=hint)를 업데이트한다


bitmap_next_clear_region(unsigned long *bitmap, unsigned int *rs, unsigned int *re, unsigned int end)
- 다음 free 영역을 찾아서 시작과 끝 지점을 rs/re로 업데이트한다
- find_next_zero_bit() 함수로 bitmap에서 rs 지점 다음에 나오는 첫 번째 zero bit을 구해서 rs로 업데이트한다
- find_next_bit() 함수로 업데이트된 rs 다음 지점부터 첫 번째 set bit을 구해서 re로 업데이트한다


bitmap_for_each_clear_region(bitmap, rs, re, end) 매크로
- bitmap에서 free 영역을 iterate하여 각 free 영역의 시작점 (rs)과 끝 점 (re)을 넘겨준다


pcpu_block_update(block, start, end)
- block 내의 free 영역 [start, end)을 고려해서 block meta를 업데이트한다

- contig 값을 인자로 받은 free 영역 사이즈로 한다
- first_free를 기존 first_free와 인자로 받은 free 영역 시작점인 start 중 더 왼쪽인 값으로 업데이트한다
- start = 0 이면 free 영역이 block 시작 지점에 있으므로 block->left_free를 contig로 한다
- end = block->nr_bits 이면 free 영역이 block 마지막 지점에 있으므로 block->right_free를 contig로 한다

- 다음 세 가지 경우로 나누어 진다

 

1. 새로운 free 영역이 contig_hint 보다 큰 경우
    - 새로운 free 영역을 새 contig 영역으로 한다.
    - 기존 contig 영역이 새로운 free 영역보다 왼쪽에 있고 기존 scan 영역보다 길면 새 scan 영역을 기존 contig 영역으로 한다.
    - 기존 contig 영역이 새로운 free 영역보다 왼쪽에 있으나 기존 scan 영역과 길이가 같고 기존 scan 영역이 새로운 free 영역보다 오른쪽에 있지 않으면 기존 scan을 유지한다. 오른쪽에 있으면 scan 영역을 0으로 한다
    - 기존 contig 영역이 새로운 free 영역보다 오른쪽에 있으면 scan 영역을 0으로 한다
    - 이 함수가 처음 불리는 경우에는 pcpu_block_refresh_hint() 함수에 의해 새로운 free 영역이 항상 contig 영역보다 오른 쪽에 있으며 (왼쪽에 있는 경우는 contig_hint = 0인 경우) scan_hint도 항상 0으로 고정이다

 

2. 새 free 영역과 contig_hint 크기가 같은 경우
    - 기존 contig와 새 free 영역 중 더 나은 alignment를 지닌 것을 새 contig로 만든다.
    - 더 나은 alignment란 시작 지점이 0이거나 둘 다 시작 지점이 0이 아니면 더 오른쪽에 있는 것을 의미한다.
    - 새 free 영역이 새로운 contig로 선택되었을 경우, 기존 scan 영역이 새 free 영역보다 오른쪽에 있고 기존 scan 영역 길이가 contig 길이보다 작으면 scan_hint를 0으로 한다
    - 반대로 기존 scan 영역이 새 free 영역보다 왼쪽에 있거나 기존 scan 영역의 길이가 contig 영역과 같으면 기존 scan 영역은 유지된다
    - 새 free 영역이 새로운 contig로 선택되지 못할 경우에는 새 free 영역이 기존 scan 영역보다 오른쪽에 있거나 길이가 더 길면 새 free 영역이 새로운 scan 영역이 되고 기존 contig는 유지된다
    - 새 free 영역이 새로운 contig로 선택되지 못하고 새 free 영역이 기존 scan 보다 왼쪽에 있으면서 길이도 더 길지 못하면 기존 contig과 기존 scan이 그대로 유지된다

 

3. 새 free 영역이 contig_hint보다 작은 경우
    - 기존 contig 보다 새 free 영역이 왼쪽에 있고 기존 scan보다 더 긴 경우
    - 기존 contig 보다 새 free 영역이 왼쪽에 있고 기존 scan과 길이가 같으며 기존 scan보다 오른쪽에 있는 경우
    - 위의 두 경우에 대해 새 free 영역을 새로운 scan 영역으로 한다

XE Login