Linux kernel v5.1 study log tree

IAMROOT16 Linux kernel v5.1 study log tree

We planed studying on week [001 ~ 067] Arm64 Linux kernel boot flow. so, we reviewed source code line by line, from arch/arm64/kernel/head.S to init/main.c::start_kernel() → mm/page_alloc.c::page_alloc_init().
After week [067 ~ ], we decided to learn each subsystem unit of the Linux kernel, starting target was the buddy system.

week [001 ~ 006] : 리눅스 커널 내부구조 + Arm 리눅스 커널 2판
1. 000 (2019-05-18) : OT
2. 001 (2019-05-25) : 리눅스 커널 내부구조 - 1장 리눅스 소개, 2장 리눅스 커널 구조 목차 제0장 운영체제 이야기 1. 운영체제 이야기 2. 운영체제 동작 비유 제1장 리눅스 소개 1. 리눅스의 탄생 2. 유닉스와 리눅스 3. 리눅스의 배포판 4. 리눅스의 장점 5. 쉘(Shell) 사용해보기 제2장 리눅스 커널 구조 1. 리눅스 커널 구조 2. 리눅스 커널 컴파일 실습 문제 제3장 태스트 관리 1. 프로세스와 쓰레드 그리고 태스크 2. 사용자 입장에서 프로세스 구조 3. 프로세스와 쓰레드의 생성과 수행 4. 리눅스의 태스크 모델 5. 태스크 문맥 6. 상태 전이(State Transtion)의 실행 수준 변화 7. 런큐와 스케줄링 8. 문맥 교환 9. 태스크와 시그널 실습 문제 제4장 메모리 관리 1. 메모리 관리 기법과 가상 메모리 2. 물리 메모리 관리 자료 구조 2-1 node 2-2 zone 2-3 page frame 3. Buddy와 Slab 3-1 버디 할당자(Buddy Allocator) 3-2 Lazy Buddy 3-3 슬랩 할당자(Slab Allocator) 4. 가상 메모리 관리 기법 5. 가상 메모리와 물리 메모리의 연결 및 변환 6. 커널 주소 공간 7. Slub, Slob 실습 문제 제5장 파일시스템과 가상 파일시스템 1. 파일 시스템 일반 2. 디스크 구조와 블록 관리 기법 3. FAT 파일시스템 4. inode 구조 5. Ext2 파일시스템 6. Ext3 파일시스템과 Ext4 파일시스템 7. 가상 파일시스템(Virtual File System) 8. 태스크 구조와 VFS 객체 9. 파일시스템 제어 흐름 분석 실습 문제 제6장 인터럽트와 트랩 그리고 시스템 호출 1. 인터럽트 처리 과정 2. 시스템 호출 처리 과정 3. 새로운 시스템 호출 구현 4. 시스템 호출 구현 확장 4-1 커널 정보 출력 4-2 인자 전달 4-3 구조체를 사용한 인자 전달 실습 문제 제7장 리눅스 모듈 프로그래밍 1. 마이크로 커널 2. 모듈 프로그래밍 무작정 따라하기 3. 시스템 호출 hooking 4. 시스템 호출 hooking 모듈 확장 실습 문제 제8장 디바이스 드라이버 1. 디바이스 드라이버 일반 2. 문자 디바이스 드라이버 구조 3. 블록 디바이스 드라이버 구조 실습 문제 제9장 네트워킹 1. 계층 구조 2. 주요 커널 내부 구조 3. 리눅스에서 통신 프로토콜의 제어 흐름 실습 문제 제10장 운영체제 관련 실습 1. 쉘(Shell) 2. 스케줄러와 시뮬레이팅 환경 3. 버디 할당자와 시뮬레이팅 환경 4. FAT 파일시스템과 디스크 에뮬레이팅 환경 4-1 파일 시스템 마운트 4-2 파일의 생성 및 쓰기 4-3 파일의 탐색 및 읽기 4-4 파일의 삭제 부록A 리눅스와 가상화 그리고 XEN 1. 가상화 기법의 이해 2. 가상화 기술 3. Xen 3-1 전가상화 기술을 이용한 리눅스 설치 3-2 전가상화 기술을 이용한 윈도즈 설치 부록B MTD와 YAFFS 1. 플래시 메모리의 이해 2. MTD 3. YAFFS 부록C Map of the Linux
3. 002 (2019-06-01) : 리눅스 커널 내부구조 - 3장 태스크 관리, 4장 메모리 관리
4. 003 (2019-06-08) : 리눅스 커널 내부구조 - 5장 파일시스템과 가상 파일시스템 (1) 파일시스템 질문: 136p FAT 파일 중간데이터를 읽을때, 처음 블록부터 읽을 필요가없다고 나와있는데, 어떻게? - FAT파일 시스템도 "인덱스 블록 기법" 처럼 블록 위치를 테이블로 관리함. - FAT는 클러스터 단위로 파일의 데이터를 관리하여, "클러스터 테이블" 이 "인덱스 블록" 과 같은 역할을 함. - 즉, 파일 데이터는 순서대로 클러스터 테이블로 관리하고, 디렉토리 엔트리에서 파일의 크기를 알수있으므로 중간 데이터의 위치를 얻을 수 있음. (2) FAT vs ext 동작방식, 슈퍼블록 구성 방식 차이 - FAT의 슈퍼블록은 하나로 관리함. FAT 할당 기법으로 하나의 블록을 전체 블록으로 하여 관리함. - ext는 복수 블록 그룹 마다 관리함. (3) 5장 파일시스템 : 140p i-links-count 가 사용되는 예시? - "hard link"하고 있는 다른 파일이 삭제 되어도, 원본 파일은 삭제되지 않음. - 다른 파일이 "hard link"할 때마다 "i_links_count"가 증가함. - 이 값이 '0'이 되면 삭제됨. - https://www.nongnu.org/ext2-doc/ext2.html#i-links-count (4) 파일시스템 질문 (2조 seo) : Ext2 파일시스템에서 디렉토리에 속해 있는 파일 정보 얻는 방법? 145p 그림5.13 설명에서, "disk block 20" 에 파일 정보가 있다는 것을 어떻게 알수 있을까? "disk block 20"의 자료구조는 어떻게 구성 되어있을까? (144p 마지막 단락 3,4번째 설명 참조) - i_mode 를 읽어서, 파일 속성이 디렉토리 이므로, 이 데이터의 시작 블록 20 은 디렉토리 엔트리 자료구조가 있음을 알 수 있음.
5. 004 (2019-06-15) : 리눅스 커널 내부구조 - 5장 파일시스템과 가상 파일시스템, 6장 인터럽트와 트랩 그리고 시스템 호출 (1) 5장 파일시스템 질문(1조 이파란) : 156p sys_open() vs sys_read() 의 기능적 차이점 - Functions like open() , printf() , scanf() , read() are library function implemented on top of their sys_* counterparts. - so they can be used for any Application development. - On the other hand sys_open, sys_close, sys_read etc are implemented as-part-of-system commonly known as "kernel". - https://stackoverflow.com/questions/1628540/are-programs-like-sys-open-sys-read-et-al-examples-of-system-level-progra (2) 5장 파일시스템 질문(4조, 노영진) : p151.line4, p152.line6를 보면 "파일 이름을 보고 파일을 관리하는 파일시스템이 무엇인지 판단한다"고 나와있는데, 파일 이름을 가지고 파일시스템을 어떻게 알아내는지? - where-are-filenames-stored-on-a-filesystem? See Directory Structure. - Unix directories are lists of association structures, each of which contains one filename and one inode number. - So the name of the file is stored within the directories' information structure. - https://unix.stackexchange.com/questions/117325/where-are-filenames-stored-on-a-filesystem (3) 6장 인터럽트와 트랩 그리고 시스템 호출 (1조 이파란) : 171p 트랩을 세가지로 구분하는 이유 - fault trap abort의 구분은 핸들러가 수행된 이후 Return Address(eip)하고 연관됨.
6. 005 (2019-06-22) : Arm 리눅스 커널 2판 - 1장 ARMv8 아키텍처 1
  숙지하고 있습니까? 당신? Arm 64 커널을 공부한다? 1.1 ARMv8 소개 4 1.1.1 익셉션 모델 5 1.1.2 익셉션 레벨 변경 6 1.1.3 실행 상태 7 1.1.4 실행 상태 변경 7 1.2 ARMv8 레지스터 8 1.2.1 프로세서 상태 레지스터(PSTATE) 9 1.2.2 AArch64 특수 목적 레지스터 10 1.2.3 시스템 레지스터 12 1.2.4 ABI의 레지스터 사용 규칙 12 1.3 AArch64 익셉션 핸들링 13 1.3.1 익셉션 타입 14 1.3.2 동기 및 비동기 익셉션 15 1.3.3 익셉션 핸들링 16 1.3.4 익셉션에 의해 변경되는 실행 상태와 익셉션 레벨 17 1.3.5 AArch64 익셉션 벡터 테이블 19 1.3.6 인터럽트 핸들링 20 1.3.7 GIC 표준 인터럽트 컨트롤러 21 1.4 캐시 21 1.4.1 캐시 구조 22 1.4.2 캐시 컨트롤러 24 1.4.3 캐시 정책 24 1.4.4 캐시 일관성의 두 가지 관점 25 1.4.5 캐시 관리 27 1.4.6 캐시 탐색 27 1.5 MMU 28 1.5.1 가상 주소를 물리 주소로 변환 29 1.5.2 AArch64의 테이블 디스크립터 종류 30 1.5.3 커널과 애플리케이션의 가상 주소 공간 분리 32 1.5.4 변환 테이블의 cacheable과 shareable 속성 33 1.5.5 디스크립터 메모리 속성 34 1.5.6 시큐리티와 MMU 36 1.5.7 컨텍스트 스위칭 36 1.6 메모리 오더링 37 1.6.1 메모리 타입 39 1.6.2 배리어 41 1.6.3 메모리 속성 42 1.7 멀티코어 프로세서 44 1.7.1 멀티프로세싱 시스템 44 1.7.2 캐시 일관성 47 1.7.3 클러스터 내의 멀티코어 캐시 일관성 48 1.7.4 버스 프로토콜과 캐시 일관성 인터커넥트 51 1.8 전력 관리 52 1.8.1 유휴 상태 관리 52 1.8.2 소비전류 관련 인스트럭션 54 1.8.3 PSCI 54
  
  (1) Arm 리눅스 커널 1장 (1조 이파란) : 5p 하이퍼바이저와 보안모니터의 주체 (하드웨어적? 소프트웨어적으로? 펌웨어?) - hypervisor mode desciptions : 2140 PAGE - https://static.docs.arm.com/ddi0487/db/DDI0487D_b_armv8_arm.pdf (2) Arm 리눅스 커널 1장 (1조 최지영) : 18p 익셉션 모드가 어떤 상황일 때 하이퍼 바이저로 전환되는지? - 호스트가 자신을 지탱하는 하이퍼 바이저에게 서비스를 요청하면 바뀜. (3) ARM 리눅스 커널 1장 (4조 박진우) : AArch64 는 V7A와 같이 CP15를 통한 Coprocessor을 지원하지 않음. - 대표적인 ARMv8A의 SoC칩들은 GPU 나 전원/외부단순 인터페이스용으로 Cortex-M Core 을 가지고 있는 경우가 있음. (4) ARM 리눅스 커널 1장(3조 김태형) : 익셉션 벡터 테이블 옵셋이 기존 ARM 아키텍쳐에서는 4Byte이었는데 128Byte로 바꾼 이유? - aarch64 의 Exception Table 사용 예시 (리눅스 메일링 리스트 인용) - https://lore.kernel.org/patchwork/patch/312340/ - Aarch64에서는 exception table에 명령어를 넣고 (aarch32의 어셈블리라면 2배로 더 많이 들어감) - http://recipes.egloos.com/5035801 - 차후 Exception table을 다루는 단원/코드 분석에서 보자! (5) ARM 리눅스 커널 1장 (3조 김태형) : 31페이지의 주소변환 테이블의 구성 이미지가 있는데 블록 디스크립터가 어떻게 맵핑이 되는지? - 매핑한 페이지 디스크립터
7. 006 (2019-06-29) : Arm 리눅스 커널 2판 - 1.5 MMU (1) AArch64 디스크립터 타입 중 테이블 엔트리 포맷? - http://jake.dothome.co.kr/pt64/ (2) ARM 리눅스 커널 1장 (2조 최자은) : 35p [OS의 변환 테이블 디스크립터 사용] AF를 설정함으로써 1) 늦은 할당이 가능하고 2) 스왑아웃할 때는 사용 중인 페이지를 스왑아웃할 가능성이 낮아진다? - https://static.docs.arm.com/100940/0100/armv8_a_address%20translation_100940_0100_en.pdf page 24페이지에 관련내용이 있는것 같음. (3) 1조 1.6 메모리 오더링? - http://jake.dothome.co.kr/barriers/ (4) 4조 질문 : 파워다운모드와 휴먼 모드의 차이점? - https://developer.arm.com/documentation/100737/0100/Power-management/Wakeup-from-sleep-mode/Wakeup-Interrupt-Controller--WIC-
week [007 ~ 018] : arch/arm64/kernel/head.S
1. 007 (2019-07-06) : arch/arm64/kernel/head.S * 항상 업데이트 되는 Arm v8 매뉴얼 링크 - https://kib.kiev.ua/x86docs/ARM/ * GNU 어셈블러 매뉴얼 - https://sourceware.org/binutils/docs/as/ - https://en.wikipedia.org/wiki/GNU_Assembler - http://tigcc.ticalc.org/doc/gnuasm.html * 부트업 헤드 설정 - https://elixir.bootlin.com/linux/latest/source/Documentation/arm64/booting.txt * Branch 명령어 종류와 차이점 - http://trace32.com/wiki/index.php/B,_BL,_BX_and_BLX - https://modexp.wordpress.com/2018/10/30/arm64-assembly/ * __inval_dcache_area (preserve_boot_args의 tail call) 관련 위치 ENTRY(__inval_dcache_area) - arch/arm64/mm/cache.S extern void __inval_dcache_area(void *addr, size_t len); - arch/arm64/include/asm/cacheflush.h : 78
2. 008 (2019-07-13) : arch/arm64/kernel/head.S ENTRY(el2_setup) * Arm 베리어 관련 정리 내용 공유 http://forum.falinux.com/zbxe/index.php?document_srl=534002&mid=Kernel_API * SPsel - https://developer.arm.com/docs/100878/latest/processor-state * subsection - https://sourceware.org/binutils/docs/as/Sub_002dSections.html#Sub_002dSections * SCTLR - https://developer.arm.com/docs/100878/latest/the-system-control-register * ARM에서 immediate를 encoding 하는 방식에 관한 설명. armv8에서도 동일하게 적용되는지 확인 필요. - https://alisdair.mcdiarmid.org/arm-immediate-value-encoding/ __PHYS_OFFSET == 0x82000 * adr 내용입니다 - http://forum.falinux.com/zbxe/index.php?document_srl=627913&mid=lecture_tip * arch/arm64/mm/cache.S::__inval_dcache_area () 132 * __inval_dcache_area(kaddr, size) 133 * 134 * Ensure that any D-cache lines for the interval [kaddr, kaddr+size) 135 * are invalidated. Any partial lines at the ends of the interval are 136 * also cleaned to PoC to prevent data loss. 프로시저 전체 주석과 라인별 주석에 설명이 나와 있네요. kaddr부터 size크기만큼 dcache를 invalidate(clean은 더티 캐시를 다음 레벨의 캐시/메모리에 써주는 것, invalidate는 캐시라인을 무효화시키는 것)하는 함수입니다. 시작 주소, 끝 주소 써주면 알아서 동작하면 좋으련만 아키텍처를 그렇게 설계할 수는 없죠. 몇 가지 캐시 오퍼레이션이 있는데, armv8에서 최대한 친절하게 종류별로 옵션을 달아줬으니 필요한 오퍼레이션 선택해서 짜면 저렇게 나오겠죠. 캐시라인 단위로 반복문 돌면서 invalidate 시키는데(dc ivac), 지우고 싶은 메모리가 캐시라인에 맞게 딱 떨어지지 않고 걸쳐 있을 때를 고려해 준 거죠. 시작 주소랑 끝주소가 캐시라인에 걸쳐 있는지 딱 들어맞는지(cache line aligned?) 비교해서(tst 명령과 b.eq 조합) clean & invalidate(dc civac) 시켜준 것입니다. cache hierarchy나 용어는 아키텍처 문서 참고하시면 될 것이고요, instruction은 TRM(technical reference manual) 참고하시면 될 것 같습니다. 참고: http://events17.linuxfoundation.org/sites/events/files/slides/slides_17.pdf - http://www.iamroot.org/xe/index.php?document_srl=206739&mid=Programming#2 * CTR (Cache Type Register) - https://developer.arm.com/docs/ddi0433/a/system-control/register-descriptions/cache-type-register
3. 009 (2019-07-20) : arch/arm64/kernel/head.S * MT_NORMAL - http://jake.dothome.co.kr/map64/ * .inst expressions - Inserts the expressions into the output as if they were instructions, rather than data. - https://sourceware.org/binutils/docs/as/AArch64-Directives.html#AArch64-Directives * sys_reg() 관련 - http://jake.dothome.co.kr/cpucaps64/ * MMFR2 레지스터 - http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0363e/Bgbfhfjc.html
4. 010 (2019-07-27) : arch/arm64/kernel/head.S * arch/arm64/kernel/head.S .macro map_memory() * .macro populate_entries에 나오는 ".Lpe\@" 의 \@에 관련 https://sourceware.org/binutils/docs/as/Macro.html#Macro \@ as maintains a counter of how many macros it has executed in this pseudo-variable; you can copy that number to your output with ‘\@’, but only within a macro definition.
5. 011 (2019-08-03) : arch/arm64/kernel/head.S compute_indices - populate_entries * Check ID_AA64DFR0_EL1 PMUVer - PMU : Performance Monitoring Unit, or the PMU, is found in all high end processors these days. The PMU is basically hardware built inside a processor to measure it's performance parameters. We can measure parameters like instruction cycles, cache hits, cache misses, branch misses and many others depending on the support i.e. hardware provide by the processor. * MT_XXXX 관련 - http://jake.dothome.co.kr/map64/ * IPA 관련 - https://developer.arm.com/architectures/learn-the-architecture/armv8-a-virtualization/stage-2-translation * Arm64 Assembly cheet sheet 간소화 - https://courses.cs.washington.edu/courses/cse469/18wi/Materials/arm64.pdf
6. 012 (2019-08-10) : arch/arm64/kernel/head.S * Cache -> Kernel code(Driver Code 를 제외한 Kernel Core code) 를 복잡하게 만드는 주요한 원인 중 하나 * Kernel code = Kernel core code + Subsystem code (Architecture 마다 Kernel 이 동작하도록 각 system 별로 구현한 것) + Driver code * Kernel core code = Memory management + Task management + Lock, ... * C++, Java, C# 이 Kernel에서 쓰이지 않는 이유? - OOP 는 일단 객체 생성을 위해서 Memory 할당이 필요함. - Kernel 단에서 객체 생성을 위한 Memory 할당 자체가 어려움. - Kernel 이 Memory management 역할을 하기 때문임. * Cache Tree : Low <-> High level 단에서의 속도 차이를 해소하기 위한 장치 - L1, L2 Cache 는 DRAM 의 느린 동작을 보완하여 System Performance 증가하기 위해 사용함. - L1 Cache 가 필요 없으려면? -> CPU Clock 속도와 Memory R/W 속도가 일치해서 Zero Latency 가 유지된다면 가능함. - {(CPU1, L1), (CPU2, L1)}-(L2)-<Memory> - L1 Cache -> SRAM 으로 제작됨. 2 Clock 정도의 속도로 L1 Cache 에 접근 가능. - 과거 10MHz CPU 에 SRAM, DRAM 을 달았을 때는, 속도 차이가 크게 안났음. But, 현재와 같은 GHz CPU 는 속도 차이가 100배 이상 남. * Lock 이란? 여러 개의 Task 가 진행되고 있을 때, Masking 을 통해 순서를 지정해주는 것. (대기하는 Task 는 Spin 상태에 있다고 표현) Lock 의 Masking 과정은 굉장히 느림. (특히, LDR, STR 명령어의 경우 시간이 굉장히 오래 걸림.) - {(CPU1, L1), (CPU2, L1), (CPU3, L1)}-(L2)-<Memory> 각 CPU - L1 - L2 - Memory 가 수행할 때 공유하는 태스크나 값에 대한 정보를 서로 공유해야함. 해당 공유 작업 자체도 Clock 이 굉장히 많이 소요되게 됨. (CPU Core 가 병렬적으로 늘어났기 때문임.) - Clock 속도는 5GHz 의 벽을 넘지 못하고(실리콘적인 병목 현상), Core 를 병렬적으로 늘리기 시작함. - CPU 스케쥴링: CPU 가 한 Task(Process) 의 명령어를 수행하다가, 다른 Task 의 명령어 수행으로 전환되는 것. 시분할 단위로 스케쥴링이 이루어지기 때문에, 마치 한 시간대에 여러 Task 가 수행되는 것처럼 보임. - Thread : 각 Process 간의 Scheduling 단위 (과거에는 Scheduling 단위는 Process 였으나, Process 하부의 Thread 단위로 변경되었으며, 현재는 Schedule Entity 단위로 수행) Kernel Space // User Space - User Space 에서 3개의 Process 가 Process1(Thread1, Thread1-1, Thread1-2), Process2(Thread1), Process3(Thread1) - 총 5개의 Thread (각 Thread 는 Task Struct 로 관리 함) - 각 20% 씩 Thread 가 수행됨 (총 100%) - 여기서 그러면, Kernel 은 언제돌까? 어느 CPU 에서 돌까? 5개의 Task 가 Scheduling 되는 도중, Interrupt 가 발생했을 때 (EL0 -> EL1 변경), Kernel 실행된 후 다시 복귀함. - Kernel Space 에는 Kernel 용 Thread 가 존재함. (Interrupt 해결을 위해 존재하며, User Thread 처럼 항상 열심히 돌고있지는 않음.) - 대부분의 CPU 수행 시간은 User Thread 가 차지함. - 네트워크나 SSD 와 같은 고성능 장치들에 의한 Interrupt 가 어마무시하게 들어오면, EL0 -> EL1 -> EL0 하는 Interrupt 처리가 많아져서 User Thread 의 다른 태스크를 처리하지 못할 정도로 CPU 할당이 길어져 throughput이 낮아짐. 즉, Interrup overhead 가 발생함. - task가 잠시 중단하고 interrupt vector로 이동하여 irq 등을 처리하는 것을 전반부 처리라고 함. - 전반부 처리에서ㄴ,ㄴ 인터럽트가 빠르게 완료되는 동작이나, 당장 처리해야 하는 것만 처리함. - 고속의 대량 네트워크 패킷도, Receive 하는 동작만 처리한 뒤, 해당 패킷에 대한 처리 등을 후반부 처리에게 전달함. ex) Kernel 단에 SKB (Socket Buffer) 가 존재하고, User 단에서는 TCP/IP 가 있으며, Web 과 연결되어 있음. 이 때, 네트워크 Interrupt 가 다량 발생시, Overhead 발생으로 인해 Kernel 단에서 Overhead 해결이 안됨. -> 해결 : Kernel 단의 역할을 User Space 쪽으로 이동 시켜준다! (User Space 에서 고속으로 네트워크 Interrupt 처리) Kernel 도움 없이 User 단에서 TCP/IP, Interrupt 처리 (10G 속도의 Interrupt 해결 위함.) File Server 등에서 많이 사용. ex) Youtube, Netflix (고속 네트워크 + 고용량/고속 Disk) 10G Network - XDP -> 필요한 부분만 Kernel 단의 SKB 로 넘기고, 나머지는 User Space 에서 처리함! (User Application 을 활용할 수 있음!) - 잠깐, XDP 를 통해 Kernel 단에서 처리할 것과 User 단에서 처리할 것을 나누는 Filter 역할을 해줄 수 있을 뿐임. Kernel 단에서 처리 속도가 빨라지는 방법은 아님. Kernel 단에서 처리 : XDP, User 단에서 처리 : DPDK (스위치 등의 개발 업체에서 사용?) 과거 : Kernel Space Driver 속도 > User Space Driver 속도 (고속의 네트워크 개발 이전) 현재 : Kernel Space Driver 속도 < User Space Driver 속도 (고속의 네트워크 등장 이후) -> Scheduling 을 안하는게 더 처리 속도가 빨라짐? -> Kernel 단의 처리 속도를 빠르게 할려고 하는 노력이 이루어짐. * cache <-> DRAM - DRAM 의 속도가 L1, L2 캐시 만큼 빨라지기 전까지는, L1, L2 캐시는 어쩔 수 없이 쓸 수밖에 없음. - 명령 파이프(각 Stage 별로 저장하는 공간이 자리하기 때문.) - 예측 분기(Branch Predict)를 위한 캐시(i.e. BL 의 경우 Return 위치를 미리 예측/저장) - Interrupt Vector : DRAM 에 vector Table 있음. - TLB Cache (Page Table Cache) : Main TLB, Micro TLB | L1 TLB, L2 TLB 등으로 나눠짐. - Load, Store Buffer (4단계의 Store 작업을 위해 Writing Buffer 를 둠.) SRAM 으로 구성함. * ARM CPU 파이프라인 <초기> : 4단계 (Fetch, Decode, Execute, Store) - <현재> Stage 수가 훨씬 많아짐. (신축성 있게) 그리고 Instruction 마다 Stage 수가 달라짐. * ARM <초기> : 1 Clock 당 Instruction 1개 처리 - <현재>의 고성능 Architecture : 1 Clock 당 Instruction 2개 이상 처리 - (SIMD 와 결합시 5개 이상 가능) - Multi Issue : 정수 연산 처리 기준으로 몇 개의 연산을 동시에 처리 가능한가? * Architecture 별로 Cache 가 다양하게 많이 도입되었기 때문에, 관련 Code 들이 굉장히 많이 늘어남. ex) 명령 캐시, 데이터 캐시, TLB 캐시와 관련된 ISA 가 많이 추가 되었음. 해당 캐시들을 조작(Cache Operation)하는 것과 관련된 ISA 가 추가 되었음. Cache Operation : i.e. Cache 를 비워라! i.e. Invalidate (Cache 비움), Clean(DRAM 에 저장된 Cache Dirty data 저장?) Flush : Invalidate or Clean (ARM 에서는 쓰이지 않음) 1) Invalidate 2) Clean 3) Invalidate & Clean -> Background 에서 동작함. -> A code --> B code 로 runtime 시, Clean 명령 시 Cache 가 비워질 때까지 기다리는 경우가 있음. 이 경우, Barrier (Cache 가 비워질 때까지 Instruction 대기함.)를 사용 -> Barrier 는 대기시간이 김 (Cost 가 큼; 시간 낭비가 큼.) * O.O.O (Out Of Order) - weak - 최근 Architecture 가 채택. - Program 명령어 들의 순서가 바뀌어 수행될 수 있다는 가능성 있음. - 의존성이 있는 구문의 명령어들은 순서를 안 바꾸기로 함. 그런데, 관련이 없어보이는데 실제로는 의존성이 있는 구문인 경우가 있음! - 이럴 때, Barrier 를 '잘' 사용해야함. (User mode 에서도 Barrier 를 사용할 준비를 함.) 고속의 처리가 필요한 부분 : Cost 가 낮은 Barrier 를 사용 명령어 순서 보존이 훨씬 중요한 부분 : Cost 가 높은 Barrier 사용 - 최근의 SMP CPU -> DSB sy , DSB ish (inner share) : CPU core 들 끼리의 Barrier 동기화 시킴. (CPU core 가 여러 개니깐, 다른 core 들까지 Barrier 상태를 동기화 시키는 것.) DSB nsh | (outer share) : CPU core 들 이외의 GPU core 들까지 Barrier 를 동기화 시키는 경우 Barrier cost 를 명시해야만 Barrier 적용이 명확하게 잘됨? - 명령어 순서도 바뀔 수 있고, Memory 에 저장 순서도 바뀔 수 있음 명령어 순서 보존 : ISB Memory 순서 보존 : DMB 이외 DSB (Cost 가 가장 높음) * I.O.O (In of Order) - strong - 단방향 Barrier <-> 양방향 Barrier - ldar, stlr (ARMv8)은 이전의 Barrier 에 비해서 속도가 어마무시하게 빠름. * Barrier Option - Shareable? inner share : CPU core outer share : CPU core <-> GPU core option 에 따라서 Read 만 Barrier 칠수도, Write 만 Barrier 칠수도 있음. Architecture 단위의 Barrier 내용임. 이와는 별개로 Compiler 단위에서 Barrier 개념도 있음. - ISB : 명령 파이프를 비우고, PoU 코드를 넣고, 다시 한번 ISB를 침으로써 Self Modification / Page Table Modification 에 대응, 이후 DSB 를 사용 - DMB : Half Barrier, SMP Barrier, ... , etc - SMP CPU 체계에서 CPU core 들 간에 간섭이 일어나는 code 들은 Architecture 단에서 DMB 를 사용하더라도 순서가 바뀔 수 있음. ex) A Core [flag = 1] --- B Core [if(flag) loop, printf(Data) -> 1] A core [Data = 10] --- B core [printf(Data) -> 0 ???? 10 아니고??] Uni-Process system 에서는 상관이 없는데, SMP (Multi-Process system) 에서는 뮤텍스 락/언락을 걸지 않는 이상 이러한 문제가 발생할 수 있음. 락/언락 작업을 할 때마다 데드락 걸릴 위험성이 크며, 속도도 저하됨 뮤텍스 대신 DMB 를 쓸 수 있음. (User level : 뮤텍스, Kernel level : DMB) Barrier, PoC, PoU 등의 개념이 ARM Cache system 을 이해하기 위해 필수적임. * Cache coherency - CPU 와 Device 는 DRAM 을 통해 Data 를 주고받음. - CPU 의 Cache 에 Dirty flag 가 설정되어 있고, DRAM 과 내용이 다르다면, Device 의 Data 전송이 실패함 - 최근의 Architecture : ACP 를 통해 Cache Coherency 처리함 (HW 단에서 Cache Coherency) - ACP 를 사용하지 못하는 Device 들 : Flush 를 통해 Data 깨짐을 방지함. - MT_DEVICE_nGnRnE : non Gathering (모아서 처리하지 마시오), non Reordering, non Early Byte _non ~ : 속도가 느려지는 작업들. _DEVICE -> NORMAL 과 다르게 Prefetch 기능이 없음. - Cache, Mapping : Architecture 을 정확히 알아야 제대로 이해 가능. - Poc, PoU 와 같은 작업 들은, HW 가 해결해줄 수 없는 부분으로, SW 적으로 해결해야함. PoC : Point of Coherency (== Location of Coherency ; LoC) 다음 캐시와 일관성을 가져야 하는 단계의 캐시 Device -- DMA -- DRAM -- Cache(x) -- Cache (y) -- CPU => Cache(x) 와 Cache(y) 에 Clean & Invalidate 과정이 필요. 언제 Clean 을 하고, 언제 Invalidate 를 사용함? Write 동작을 하는 DMA 를 할 때는 Invalidate 를 함. (Invalidate 속도 >> Clean 속도) PoU : Point of Unification (통합 캐시 레벨) ARM 의 경우 L2 캐시 부터 I-Cache, D-Cachea 가 나뉘지 않음 이런 L2 캐시를 PoU 라고 함. Kernel code 중에서 성능 향상을 위해 미리 Branch 를 어느쪽으로 할지 결정할 수 있는 기능이 있음. if 문 사용 시 (어셈블리에서 b.ne) 괜히 CPU Clock 을 사용하지 않게, 어차피 Branch 할 부분으로 Jump 하게 코드를 실시간으로 변경함. (User Level 단에서는 Java code가 유사한 기능이 있음. 실행 중에 code가 실시간으로 변경됨.) LDR 명령어 -> I-Cache 에는 이전 명령어 저장되어 있고, D-Cache(L1) 와 DRAM 에는 해당 내용이 저장됨. 1. Self modification code 가 있을 때는 flush 를 통해 명령어를 비워주는 행위가 꼭 필요. (PoU 방식의 Barrier) 2. Page Table(Mapping entry) 이 바뀔 때도, Flush 를 통해서 기존 Mapping 들을 비워줘야함. 바뀐 내용이 D-Cache 나 DRAM 에만 반영되고 I-Cache 에는 반영이 안 되어있음
7. 013 (2019-08-24) : arch/arm64/kernel/head.S * tst x23, ~(MIN_KIMG_ALIGN - 1) 에 대한 커밋 내용 - http://lists.infradead.org/pipermail/linux-arm-kernel/2016-March/413173.html
8. 014 (2019-08-31) : arch/arm64/kernel/head.S * Low level Exception - https://s-matyukevich.github.io/raspberry-pi-os/docs/lesson03/linux/low_level-exception_handling.html * SSBD 이슈 - https://lwn.net/Articles/755211/ * GICC_PMR - http://jake.dothome.co.kr/ic/ * arch/arm64/include/asm/ptrace.h 159 /* 160 * This struct defines the way the registers are stored on the stack during an 161 * exception. Note that sizeof(struct pt_regs) has to be a multiple of 16 (for 162 * stack alignment). struct user_pt_regs must form a prefix of struct pt_regs. 163 */ 164 struct pt_reg
9. 015 (2019-09-21) : arch/arm64/kernel/head.S * static unsigned int array[10] = { [0] = 5, [1] = 5, [2] = 5, [3] = 5, [4] = 5, [5] = 5, [6] = 5, [7] = 5, [8] = 5, [9] = 5}; * static unsigned int array[10] = { [ 0 ... 9 ] = 5 }; * _Bool lowercase_eh(char c) { switch(c) case 'a' ... 'z': return 1; return 0; } - https://stackoverflow.com/questions/56598905/three-dots-operator-for-initializing-an-array * asm volatile - https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html asm asm-qualifiers ( AssemblerTemplate : OutputOperands [ : InputOperands [ : Clobbers ] ]) asm asm-qualifiers ( AssemblerTemplate : OutputOperands : InputOperands : Clobbers : GotoLabels) * debug_object_early_init() 함수는 .config 파일 내에 CONFIG_DEBUG_OBJECTS 가 정의되어 있지 않으면 빈함수이고 정의되어 있으면 lib/debugobjects.c 파일에 기술되어 있는 함수가 사용된다. 이 함수는 obj_hash 구조체 배열과 obj_static_pool 구조체 배열을 초기화 한다. - http://m.blog.daum.net/english_100/86?np_nil_b=1 - http://jake.dothome.co.kr/debug_objects_early_init/ * ((void)(((typeof(p) space )p) == p)) 관련 참고하세요. - https://stackoverflow.com/questions/34288844/what-does-casting-to-void-really-do * IDR (Integer ID 관리) - http://jake.dothome.co.kr/idr/ * local_irq_disable() - http://jake.dothome.co.kr/local_irq_disable/
10. 016 (2019-09-28) : arch/arm64/kernel/head.S * DEFINE_PER_CPU_SECTION 관련 - https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-1.html * __verify_pcpu_ptr 관련 - http://egloos.zum.com/studyfoss/v/5375570 * tpidr_el1 관련 - https://developer.arm.com/docs/ddi0595/latest/aarch64-system-registers/tpidr_el1 * inline assembly - http://jake.dothome.co.kr/inline-assembly/ * RELOC_HIDE 매크로 Linux: 2.6.35RELOC_HIDE() 매크로는 컴파일러의 최적화/오동작(?)을 방지하려는 목적으로 만들어짐. gcc의 경우 다음과 같이 정의되어 있다. include/linux/compiler-gcc.h:#define RELOC_HIDE(ptr, off) - http://egloos.zum.com/studyfoss/v/5374731 * preempt_count() 는 현재 스레드 정보(thread_info 구조체)에서 preempt_count를 리턴함. preempt_count 값은 preempt_enable() 호출 시 감소되며 preempt_disable() 호출 시 증가됨. preempt_count 값이 0인 경우 preemption이 가능한 상태가 됨. - http://jake.dothome.co.kr/tag/function/ * preemption disabled 관련 현대의 OS는 대부분 preemptive multitasking을 지원함. preemption이란, 어느 thread가 수행 중인데, 느닷없이 그 thread가 동작을 멈추고 다른 thread가 수행되는 것을 가리킴. preempt_disable은 이러한 preemption을 막기 위해서 사용함. - http://egloos.zum.com/nimhaplz/v/5683475 * READ_ONCE WRITE_ONCE 관련 - https://stackoverflow.com/questions/34988277/write-once-in-linux-kernel-lists read_once, write_once, barrier, volatile 관련 (Memory Functions) - https://medium.com/@chenfelix/memory-barrier-684dcd3f7441 * typecheck, expression statement 관련 - https://stackoverflow.com/questions/10393844/how-does-the-typecheck-macro-from-the-linux-kernel-work * icc_pmr_el1 관련 - https://developer.arm.com/docs/ddi0595/b/aarch64-system-registers/icc_pmr_el1 * round_up 관련 - https://medium.com/@arunistime/how-div-round-up-works-179f1a2113b5
11. 017 (2019-09-30) : arch/arm64/kernel/head.S * statement expression 관련 - http://lvzuufx.blogspot.com/2015/07/c-gcc.html
12. 018 (2019-10-05) : arch/arm64/kernel/head.S * priority masking 관련 - https://developer.arm.com/docs/ddi0601/latest/aarch64-system-registers/icc_pmr_el1 * GIC - Generic Interrupt Controller - http://jake.dothome.co.kr/ic/ * typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t; bitmask로 활용 관련 - http://jake.dothome.co.kr/cpu-api/
week [019 ~ 027] : init/main.c::start_kernel() → arch/arm64/mm/mmu.c::early_fixmap_init()
1. 019 (2019-10-12) : arch/arm64/mm/mmu.c::early_fixmap_init() * atomic64_or - include/asm-generic/atomic-long.h -> include/asm-generic/atomic64.h 1. arch/arm64/include/asm/atomic_lse.h 2. arch/arm64/include/asm/atomic_ll_sc.h 3. arch/arm64/include/asm/atomic.h) * boot_cpu_init() https://m.blog.naver.com/deviliangel/50187759904 * spinlock_check(_lock) - https://0xax.gitbooks.io/linux-insides/SyncPrim/linux-sync-1.html - https://junsoolee.gitbook.io/linux-insides-ko/summary/syncprim/linux-sync-1 * 구조체 변수를 선언하는 동시에 초기화하기 struct Person p1 = { .name = "홍길동", .age = 30, .address = "서울시 용산구 한남동" }; - https://dojang.io/mod/page/view.php?id=408 * 5.4 The Special Dot Symbol The special symbol ‘.’ refers to the current address that as is assembling into. Thus, the expression ‘melvin: .long .’ defines melvin to contain its own address. Assigning a value to . is treated the same as a .org directive. Thus, the expression ‘.=.+4’ is the same as saying ‘.space 4’. - https://sourceware.org/binutils/docs/as/Dot.html#Dot * void __init early_fixmap_init(void) - https://sonseungha.tistory.com/457 * early_fixmap_init() - https://isun2501.tistory.com/20 * bm_pte // which is boot time page tables - https://junsoolee.gitbook.io/linux-insides-ko/summary/initialization/linux-initialization-5#early-ioremap-initialization * arch_atomic64_or(), arch_atomic_or() - arch/arm64/include/asm/atomic_lse.h
2. 020 (2019-10-26) : arch/arm64/mm/ioremap.c::early_ioremap_init() early_ioremap_init() (arch/arm64/mm/ioremap.c) - early_ioremap_setup() (mm/early_ioremap.c) -- __fix_to_virt() (include/asm-generic/fixmap.h) #define __fix_to_virt(x) (FIXADDR_TOP - ((x) << PAGE_SHIFT)) * 이른(early) 시간에 io 매핑이 필요한 경우 256K씩 최대 7개의 fixmap 매핑 공간을 사용하여 매핑을 할 수 있게 한다. - http://jake.dothome.co.kr/early-ioremap/ - http://jake.dothome.co.kr/fixmap/ * fdt, dtb 관련 - http://jake.dothome.co.kr/dtb1/
3. 021 (2019-11-02) : 통합 연습 스터디
4. 022 (2019-11-09) : 통합 연습 스터디 2
5. 023 (2019-11-16) : 통합 전 각 조별 스터디 * pgprot_t 관련 - https://www.kernel.org/doc/gorman/html/understand/understand006.html * create_pgd_mapping 관련입니다 http://jake.dothome.co.kr/map64/
6. 024 ~ 027 : Slack 을 참고하여 확인 필요 024 (2019-11-23) 024 (2019-11-23) 025 (2019-11-30) 026 (2019-12-07) 027 (2019-12-14)
week [028 ~ 054] : init/main.c::start_kernel() → arch/arm64/kernel/setup.c::setup_arch()
1. 028 (2019-12-21) ~ : arch/arm64/mm/mmu.c::fixmap_remap_fdt
  1. 028 (2019-12-21) : fixmap_remap_fdt setup_arch - setup_machine_fdt -- fixmap_remap_fdt 까지 진행
  2. 029 ~ 035 : Slack 을 참고하여 확인 필요 029 (2020-01-04) 030 (2020-01-11) 031 (2020-01-18) 032 (2020-02-01) 033 (2020-02-08) 034 (2020-02-15) 035 (2020-02-22)
2. 036 (2020-02-29) ~ : arch/arm64/mm/init.c::arm64_memblock_init()
  1. 036 (2020-02-29) : drivers/of/fdt.c::early_init_fdt_scan_reserved_mem() setup_arch - arm64_memblock_init -- early_init_fdt_scan_reserved_mem 까지 진행
  2. 037 (2020-03-07) : include/linux/cma.h::cma_declare_contiguous() setup_arch - arm64_memblock_init -- dma_contiguous_reserve (kernel/dma/contiguous.c) --- dma_contiguous_reserve_area (kernel/dma/contiguous.c) ---- cma_declare_contiguous (include/linux/cma.h) ----- cma_declare_contiguous_nid (mm/cma.c) ------ cma_init_reserved_mem 이전 까지 진행
3. 038 (2020-03-14) : arch/arm64/mm/mmu.c::paging_init()
  1. 038 (2020-03-14) setup_arch - paging_init -- map_kernel 까지 진행
  2. 039 (2020-03-21)
  3. 040 (2020-03-28)
4. 041 (2020-04-04) ~ : drivers/of/fdt.c::unflatten_device_tree()
  1. 041 (2020-04-04) : drivers/of/fdt.c::populate_properties() setup_arch - unflatten_device_tree -- __unflatten_device_tree --- unflatten_dt_nodes ---- populate_node (drivers/of/fdt.c) ----- populate_properties (drivers/of/fdt.c) ------ " if (!has_name) { " 이전 까지 진행
  2. 042 (2020-04-11) : drivers/of/fdt.c::unittest_unflatten_overlay_base() setup_arch - unflatten_device_tree -- unittest_unflatten_overlay_base 이전 까지 진행
5. 043 (2020-04-18) ~ : arch/arm64/mm/numa.c::arm64_numa_init()
  1. 043 (2020-04-18) : drivers/of/*::of_*() setup_arch - arm64_numa_init -- of_numa_init (drivers/of/of_numa.c) --- of_numa_parse_memory_nodes (drivers/of/of_numa.c) ---- of_address_to_resource (drivers/of/address.c) ----- of_get_address (drivers/of/address.) ------ of_get_property (drivers/of/base.c) 이전 까지 진행
  2. 044 (2020-04-25) : 슬랙에서 확인 필요
6. 045 (2020-05-09) ~ : arch/arm64/mm/init.c::bootmem_init()
  1. 045 (2020-05-09) : mm/sparse.c::memblocks_present() setup_arch - bootmem_init -- memblocks_present (mm/sparse.c) --- memory_present (mm/sparse.c) ---- section_mark_present (mm/sparse.c) 이전 까지 진행
  2. 046 (2020-05-16) : mm/sparse.c::spare_init() setup_arch - bootmem_init -- spare_init (mm/sparse.c) --- sparse_init_nid (mm/sparse.c) ---- sparse_mem_map_populate(vmemmap) (mm/sparse.c) ## v5.10.x 이후 사라짐 ----- pfn_to_page. 까지 진행
  3. 047 (2020-05-23) : mm/sparse.c::sparse_init_nid() setup_arch - bootmem_init -- spare_init (mm/sparse.c) --- sparse_init_nid (mm/sparse.c) ---- check_usemap_section_nr (mm/sparse.c) 이전 까지 진행
  4. 048 (2020-05-30) : arch/arm64/mm/init.c::zone_sizes_init() setup_arch - bootmem_init -- zone_sizes_init (arch/arm64/mm/init.c) --- free_area_init_nodes (mm/page_alloc.c) ## v5.10.x 이후 사라짐 ---- find_zone_movable_pfns_for_nodes (mm/page_alloc.c) ----- "if (required_kernelcore_percent)" 이전 까지 진행
  5. 049 (2020-06-06) : mm/page_alloc.c::zone_spanned_pages_in_node() setup_arch - bootmem_init -- zone_sizes_init (arch/arm64/mm/init.c) --- free_area_init_nodes (mm/page_alloc.c) ## v5.10.x 이후 사라짐 ---- free_area_init_node (mm/page_alloc.c) ----- calculate_node_totalpages (mm/page_alloc.c) ------ zone_spanned_pages_in_node (mm/page_alloc.c) 이전 까지 진행
  6. 050 (2020-06-13) : ㅡm/page_alloc.c::memmap_init_zone() setup_arch - bootmem_init -- zone_sizes_init --- free_area_init_nodes (mm/page_alloc.c) ## v5.10.x 이후 사라짐 ---- free_area_init_node (mm/page_alloc.c) ----- free_area_init_core (mm/page_alloc.c) ------ memmap_init (mm/page_alloc.c) ------- memmap_init_zone (mm/page_alloc.c) -------- __init_single_page 이전 까지 완료
  7. 051 (2020-06-20) bootmem_init 완료
  8. 052 (2020-06-27) bootmem_init 복습 1
  9. 053 (2020-07-04) bootmem_init 복습 2
week [055 ~ 059] : init/main.c::start_kernel() → mm/percpu.c::setup_per_cpu_areas()
1. 055 (2020-07-18) : setup_per_cpu_areas - pcpu_embed_first_chunk (mm/percpu.c) -- pcpu_build_alloc_info (mm/percpu.c) --- "max_upa = upa;" 까지 진행
2. 056 (2020-07-25) : setup_per_cpu_areas - pcpu_embed_first_chunk (mm/percpu.c) -- pcpu_setup_first_chunk (mm/percpu.c) --- PCPU_SETUP_BUG_ON 까지 진행
3. 057 (2020-08-01) : arch/arm64/mm/numa.c::setup_per_cpu_areas() setup_per_cpu_areas - pcpu_embed_first_chunk (mm/percpu.c) -- pcpu_setup_first_chunk (mm/percpu.c) --- pcpu_alloc_first_chunk (mm/percpu.c) ---- pcpu_block_update_hint_alloc (mm/percpu.c) 이전 까지 진행
4. 058 (2020-08-08) : arch/arm64/mm/numa.c::setup_per_cpu_areas() 복습
5. 059 (2020-08-29) : per-cpu, static-key per-cpu 개념 복습 static-key 개념
week [063 ~ 064] : init/main.c::start_kernel() → arch/arm64/kernel/smp.c::smp_prepare_boot_cpu()
1. 063 (2020-09-26) : arch/arm64/kernel/alternative.c::apply_boot_alternatives() start_kernel - smp_prepare_boot_cpu (arch/arm64/kernel/smp.c) -- apply_boot_alternatives (arch/arm64/kernel/alternative.c) --- __apply_alternatives (arch/arm64/kernel/alternative.c) ---- patch_alternative (arch/arm64/kernel/alternative.c) ----- get_alt_insn (arch/arm64/kernel/alternative.c)
2. 064 (2020-10-10) : arch/arm64/kernel/smp.c::init_gic_priority_masking() - smp_prepare_boot_cpu (arch/arm64/kernel/smp.c) -- init_gic_priority_masking (arch/arm64/kernel/smp.c)
week [065] : init/main.c::start_kernel() → mm/page_alloc.c::build_all_zonelists()
1. 065 (2020-10-17) : build_all_zonelists (init/main.c) - build_all_zonelists_init (mm/page_alloc.c) -- for_each_possible_cpu (mm/page_alloc.c)
week [066] : init/main.c::start_kernel() → mm/page_alloc.c::page_alloc_init()
1. 066 (2020-10-24) : mm/page_alloc.c::page_alloc_init() - page_alloc_init -- page_alloc_cpu_dead --- lru_add_drain_cpu ---0 __pagevec_lru_add_fn 가상머신에서는 런타임 동적으로 CPU 를 바꿀 수 있음. → 해제한 CPU 와 연관된 메모리 서브시스템에 대한 동작이 필요함.
  순차 지향 소스 코드 분석보다는, 서브시스템 단위 Buddy System 먼저 보기로 결정함.
week [067 ~ 092] : Buddy System 및 서적을 통한 기반 지식 학습
1. 067 (2020-10-31) : Mastering linux kernel development
  Chap 4. Memory Management and Allocators 중 - Page mobility and placement 까지 읽음 (p122 시작부)
2. 068 (2020-11-07) include/linux/page-flags.h::__SetPageBuddy & Mastering linux kernel development 1. 책 : Mastering linux kernel development 4장 Memory Management and Allocators (pp.124-139) 2. 코드 분석 alloc_pages (include/linux/gfp.h) - alloc_pages_current (mm/mempolicy.c) -- __alloc_pages_nodemask (mm/page_alloc.c) 분석하다가 중단 --- get_page_from_freelist ---- rmqueue ----- __rmqueue_smallest 분석 완료 ------ rmv_page_order ------- __ClearPageBuddy (include/linux/page-flags.h:716) ------ expand ------- set_page_guard ------- set_page_order -------- __SetPageBuddy (include/linux/page-flags.h:716)
3. 069 (2020-11-14) mm/page_alloc.c::__zone_watermark_ok() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- get_page_from_freelist ----- zone_watermark_fast ------ __zone_watermark_ok 진행 中
4. 070 (2020-11-21) mm/page_alloc.c::move_freepages_block() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- get_page_from_freelist ----- rmqueue ------ __rmqueue ------- _rmqueue_fallback -------- steal_suitable_fallback --------- move_freepages_block
5. 071 (2020-11-28) mm/vmstat.c::__mod_zone_page_state() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- get_page_from_freelist ----- rmqueue ------ __mod_zone_freepage_state ------- __mod_zone_page_state
6. 072 (2020-12-5) mm/page_alloc.c::get_page_from_freelist() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- get_page_from_freelist -> 완료
7. 073 (2020-12-12) mm/compaction.c::__compaction_suitable() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) ---------- compaction_suitable (mm/compaction.c) ----------- __compaction_suitable (mm/compaction.c) -> 완료
8. 074 (2020-12-19) mm/compaction.c::compact_zone() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) -> migrate_prep_local() 까지 보고, 뒤의 while 부터 볼차례임.
9. 075 (2021-1-9) mm/page_alloc.c::__alloc_pages_slowpath
  __alloc_pages_slowpath 복습
10. 076 (2021-1-16) mm/compaction.c::isolate_migratepages() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- isolate_migratepages (mm/compaction.c) -> 1798 isolation_suitable() 부터 볼차례
11. 077 (2021-1-23) mm/compaction.c::isolate_migratepages() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- isolate_migratepages (mm/compaction.c) ---------- isolate_migratepages_block (mm/compaction.c) -> 1006 isolate_fail: 부터 볼차례 (+ vmstat.c 536 mod_node_state() 정리)
12. 078 (2021-1-30) : 리눅스 커널의 이해(3판)
  9장. 프로세스 주소공간 : p399 '주소 공간 밖의 잘못된 주소 처리하기' 까지 진행
13. 079 (2021-2-6) : 리눅스 커널의 이해(3판)
  9장. 프로세스 주소공간 p408 '불연속적인 메모리 영역 접근 처리'까지 진행
14. 080 (2021-2-20) 리눅스 커널의 이해(3판)
  12장 - 가상 파일 시스템 역할, 파일 객체, 아이노드 객체, 디엔트리 객체, 디엔트리 객체 캐시
  
  15장 - 페이지 캐시에서 페이지 캐시처리 함수 부분
15. 081 (2021-2-27) 리눅스 커널의 이해(3판)
  17장 - 페이지 프레임 회수 p692 'LRU 리스트 시이의 페이지 이동'까지 진행
16. 082 (2021-3-6) 리눅스 커널의 이해(3판)
  17장 - 페이지 프레임 회수 p705 '아이노드 캐시에서 페이지 프레임 회수하기'까지 진행
17. 083 (2021-3-13) 리눅스 커널의 이해(3판)
  17장 - 페이지 프레임 회수 p720 'sys_swapoff() 서비스 루틴'까지 진행
18. 084 (2021-3-20) 리눅스 커널의 이해(3판)
  17장 - 페이지 프레임 회수 p730 '스왑 캐시에서 페이지 프레임 제거하기'까지 진행
19. 085 (2021-3-27) 리눅스 커널의 이해(3판)
  17장 - 페이지 프레임 회수 마치고 요약정리 진행
20. 086 (2021-4-3) Understanding the Linux Virtual Memory Manager - Mel Gorman
  10장 Page Frame Reclamation 진행
21. 087 (2021-4-10) mm/compaction.c::compact_zone - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) -> 2181 migrate_pages() 전까지 진행
22. 088 (2021-4-17) mm/compaction.c::isolate_freepages() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- migrate_pages (mm/compaction.c) -> unmap_and_move_huge_page()보다 unmap_and_move()를 먼저 분석 ---------- unmap_and_move (mm/migrate.c) -> get_new_page() : compaction에서는 compaction_alloc()함수 호출 ------------ compaction_alloc (mm/compaction.c) ------------- isolate_freepages (mm/compaction.c) -> 1465행 for문부터 볼차례
23. 089 (2021-4-24) mm/migrate.c::migrate_page() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- migrate_pages (mm/compaction.c) -> unmap_and_move_huge_page()보다 unmap_and_move()를 먼저 분석 ---------- unmap_and_move (mm/migrate.c) ----------- __unmap_and_move (mm/migrate.c) ------------ move_to_new_page (mm/migrate.c) ------------- migrate_page (mm/migrate.c) -------------- migrate_page_move_mapping (mm/migrate.c) -> 454행 dirty = PageDirty(page); 부터 볼차례
24. 090 (2021-5-1) mm/migrate.c::unmap_and_move - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- migrate_pages (mm/compaction.c) -> unmap_and_move_huge_page()보다 unmap_and_move()를 먼저 분석 ---------- unmap_and_move (mm/migrate.c) ----------- __unmap_and_move (mm/migrate.c) -> 1089행 move_to_new_page()함수 다음줄 부터 볼차례
25. 091 (2021-5-8) mm/page_vma_mapped.c::page_vma_mapped_walk() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- migrate_pages (mm/compaction.c) -> unmap_and_move_huge_page()보다 unmap_and_move()를 먼저 분석 ---------- unmap_and_move (mm/migrate.c) ----------- __unmap_and_move (mm/migrate.c) ------------ try_to_unmap(mm/rmap.c) -> rmap_walk_lock보다 rmap_walk부터 분석 ------------- rmap_walk(mm/rmap.c) -> rmap_walk_ksm와 rmap_walk_file보다 rmap_walk_anon부터 분석 -------------- rmap_walk_anon(mm/rmap.c) - rmap_one -> try_to_unmap_one --------------- try_to_unmap_one(mm/rmap.c) ---------------- page_vma_mapped_walk (mm/page_vma_mapped.c) -> 183행 pmde = READ_ONCE(*pvmw->pmd); 부터 볼차례
26. 092 (2021-5-15) mm/rmap.c::try_to_unmap_one() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) --------- migrate_pages (mm/compaction.c) -> unmap_and_move_huge_page()보다 unmap_and_move()를 먼저 분석 ---------- unmap_and_move (mm/migrate.c) ----------- __unmap_and_move (mm/migrate.c) ------------ try_to_unmap(mm/rmap.c) -> rmap_walk_lock보다 rmap_walk부터 분석 ------------- rmap_walk(mm/rmap.c) -> rmap_walk_ksm와 rmap_walk_file보다 rmap_walk_anon부터 분석 -------------- rmap_walk_anon(mm/rmap.c) - rmap_one -> try_to_unmap_one --------------- try_to_unmap_one(mm/rmap.c) ---------------- put_page (include/linux/mm.h) __put_page부터 볼차례, 버디시스템 해지 : free_pages (mm/page_alloc.c) 분석 예정
week [093 ~ 095] : memory compaction
1. 093 (2021-5-22) mm/compaction.c::compact_zone() - alloc_pages (include/linux/gfp.h) -- alloc_pages_current (mm/mempolicy.c) --- __alloc_pages_nodemask (mm/page_alloc.c) ---- __alloc_pages_slowpath (mm/page_alloc.c) ----- __alloc_pages_direct_compact (mm/page_alloc.c) ------ try_to_compact_pages (mm/compaction.c) ------- compact_zone_order (mm/compaction.c) -------- compact_zone (mm/compaction.c) -> check_drain: 부터 시작, compaction 및 rmap 다시 볼 예정
2. 094 (2021-5-29) : compaction 관련 중요한 commit을 시간순으로 리뷰 - 5e1f0f098b4649fad53011246bcaeff011ffdf5d mm, compaction: capture a page under direct compaction - 1fb3f8ca0e9222535a39b884cb67a34628411b9f mm: compaction: capture a suitable high-order page immediately when it is made available - 85aa125f001f87f96a72e9e6ee515490843b1202 mm: compaction: introduce isolate_freepages_range() - 2fe86e0004076128f05d5a774b5c9c03d9dc3de2 mm: compaction: introduce isolate_migratepages_range() - 3e7d344970673c5334cf7b5bb27c8c0942b06126 mm: vmscan: reclaim order-0 and use compaction instead of lumpy reclaim capture → compaction 할 때 page 를 isolation 하여 경합 조건으로 노출하지 않음.
3. 095 (2021-6-5) : compaction 복습 compaction 관련 중요한 commit을 시간순으로 리뷰 끝.
week [096 ~ 099] : rmap
1. 096 (2021-06-12) : rmap - workload - do_fork()에서 자식 VMA 에 대한 AVC 생성 과정 코드 리뷰 - rmap 리뷰 (fork, anon_vma)
2. 097 (2021-06-19) : rmap - AV, AVC, VMA - rmap.h의 commit을 시간 순으로 리뷰 - AVC 도입 배경, LWN AV 단위 Lock contention 리뷰
3. 098 (2021-06-26) : mm/rmap.c::page_add_new_anon_rmap - linear_page_index() 함수의 pgoff 를 중심으로 AV, VMA 분석 - 커널 관점의 mmap() 시스템 콜 분석 : MAP_SHARED vs MAP_PRIVATE
  pgoff 0 : SIGBUS 에러 관련 MAP_SHARED; pgoff = 0;
  
  mmap: fix petty bug in anonymous shared mmap offset handling
4. 097 (2021-07-03) : PVMW(Page Vma Mapped Walk) mm/rmap.c::try_to_unmap_one() - AVC 에 대한 same_anon_vma 가 바뀐 rb tree 기반 interval_tree 우선 소스 분석 관점 말고, 개념으로 이해 후 나중에 분석하기로 결정함. try_to_unmap() (mm/rmap.c) : struct rmap_walk_control rwc 설정 - anon_vma_interval_tree_foreach (include/linux/mm.h) : 루프안에서 rmap 으로 찾은 페이지에 대한 vma 를 뽑고 해당 VM 주소를 반환함 -- rwc->rmap_one() == try_to_unmap_one() : 1. struct page_vma_mapped_walk pvmw 설정함 2. struct mm_struct *mm 에서 해당하는 페이지 테이블 엔트리를 타고 들어감 --- map_pte() (mm/page_vma_mapped.c) : pvmw->address를 사용하여 pte 엔트리를 알아옴. /** * try_to_unmap_one - worker function for try_to_unmap * @page: page to unmap * @ptep: page table entry to unmap from page * * Internal helper function for try_to_unmap, called for each page * table entry mapping a page. Because locking order here is opposite * to the locking order used by the page fault path, we use trylocks. * Locking: * page lock shrink_list(), trylock * rmap lock shrink_list() * mm->page_table_lock try_to_unmap_one(), trylock */ v2.6.6 - try_to_unmap_one shrink_list() 를 분석하면 이해도를 높힐 수 있을까?
  v2.6.6 - try_to_unmap_one
week [100 ~ ] : page reclaim
1. 100 (2021-07-10) : should_continue_reclaim()
  1. 100 (2021-07-10) : should_continue_reclaim
    (1) alloc_pages_slowpath 다이어그램
    
    - [문C] __alloc_pages_slowpath()
    __alloc_pages_nodemask (mm/page_alloc.c) : heart' of the zoned buddy allocator. - __alloc_pages_slowpath(alloc_mask, order, &ac) (mm/page_alloc.c) -- get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags, const struct alloc_context *ac) (/mm/page_alloc.c) : for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, ac->nodemask) { ret = node_reclaim(zone->zone_pgdat, gfp_mask, order); --- node_reclaim(zone->zone_pgdat, gfp_mask, order) (/mm/vmscan.c) ---- __node_reclaim(pgdat, gfp_mask, order) (/mm/vmscan.c) : struct scan_control sc 설정함. do { shrink_node(pgdat, &sc); } while (sc.nr_reclaimed < nr_pages && --sc.priority >= 0); ----- shrink_node(pgdat, &sc) (/mm/vmscan.c) : do{ } while (should_continue_reclaim(pgdat, sc->nr_reclaimed - nr_reclaimed, sc->nr_scanned - nr_scanned, sc)); ------ should_continue_reclaim (/mm/vmscan.c) /* * Reclaim/compaction is used for high-order allocation requests. It reclaims * order-0 pages before compacting the zone. should_continue_reclaim() returns * true if more pages should be reclaimed such that when the page allocator * calls try_to_compact_zone() that it will have enough free pages to succeed. * It will give up earlier than that if there is difficulty reclaiming pages. */ static inline bool should_continue_reclaim(struct pglist_data *pgdat, unsigned long nr_reclaimed, unsigned long nr_scanned, struct scan_control *sc)
    (2) 리눅스 커널의 이해 3판 : PFRA - try_to_free_pages 메모리 부족 시 회수
    
    - [PATCH] vmscan: rename functions
    v2.6.16.62 -> v2.7.17 [PATCH] vmscan: rename functions We have: try_to_free_pages ->shrink_caches(struct zone **zones, ..) ->shrink_zone(struct zone *, ...) ->shrink_cache(struct zone *, ...) ->shrink_list(struct list_head *, ...) ->refill_inactive_list((struct zone *, ...) which is fairly irrational. Rename things so that we have try_to_free_pages ->shrink_zones(struct zone **zones, ..) ->shrink_zone(struct zone *, ...) ->shrink_inactive_list(struct zone *, ...) ->shrink_page_list(struct list_head *, ...) ->shrink_active_list(struct zone *, ...) static void refill_inactive_zone(struct zone *zone, struct scan_control *sc) -> static void shrink_active_list(unsigned long nr_pages, struct zone *zone, struct scan_control *sc)
    (3) (v2.6.11) VS (v5.1) 기준 이름 변경 관련
    
    - [문c] zonned-allocator-shrink-1
    try_to_free_pages(struct zonelist *zonelist, int order, (/mm/vmscan.c) gfp_t gfp_mask, nodemask_t *nodemask) : struct scan_control sc 설정함. - do_try_to_free_pages(zonelist, &sc) : (/mm/vmscan.c) -- shrink_zones(zonelist, sc) : (/mm/vmscan.c) : for_each_zone_zonelist_nodemask(zone, z, zonelist, sc->reclaim_idx, sc->nodemask) { shrink_node(zone->zone_pgdat, sc); --- shrink_node(zone->zone_pgdat, sc) (/mm/vmscan.c) : do{} while (should_continue_reclaim(pgdat, sc->nr_reclaimed - nr_reclaimed, sc->nr_scanned - nr_scanned, sc)); ---- shrink_node_memcg(pgdat, memcg, sc, &lru_pages); : for_each_evictable_lru(lru) { nr_reclaimed += shrink_list(lru, nr_to_scan, lruvec, sc); ----- shrink_list(lru, nr_to_scan, lruvec, sc) (/mm/vmscan.c) : return shrink_inactive_list(nr_to_scan, lruvec, sc, lru); ------ shrink_active_list(nr_to_scan, lruvec, sc, lru) (/mm/vmscan.c) : a helper for shrink_node(). It returns the number of reclaimed pages ------- shrink_page_list(&page_list, pgdat, sc, 0, &stat, false) (/mm/vmscan.c) : returns the number of reclaimed pages ----- shrink_inactive_list(nr_to_scan, lruvec, sc, lru); : a helper for shrink_node(). It returns the number of reclaimed pages
2. 101 (2021-07-17) : v2.6.11 mm/vmscan.c::refill_inactive_zone()
  1. 101 (2021-07-17) : refill_inactive_zone - 100주차 내용 (스터디 휴가임) # 진도 shrink_zone(struct zone *zone, struct scan_control *sc) (mm/vmscan.c) - refill_inactive_zone (mm/vmscan.c) (struct zone *zone, struct scan_control *sc) while (pgscanned < nr_pages && !list_empty(&zone->active_list)) 까지 봤음. @ nr_active || nr_inactive 가 존재할 때, SWAP_CLUSTER_MAX 단위로 배치 처리 @ mm/swap.c::lru_add_drain, include/linux/pagevec.h::struct pagevec 공부 - __pagevec_lru_add(struct pagevec *pvec) -- add_page_to_inactive_list(struct zone *zone, struct page *page) - percpu 변수로 lru 캐시된 페이지를 zone inactive / acive_list 넣음 - https://elixir.bootlin.com/linux/v2.6.11/source/include/linux/mm_inline.h#L10 @ 리스트 멤버를 가진 해당 구조체를 가져옴. #define lru_to_page(_head) (list_entry((_head)->prev, struct page, lru)) /** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) @ prefetch_prev_lru_page 에서 page 구조체에 멤버인 LIST_HEAD 구조에 따른 if ((_page)->lru.prev != _base) 예외 처리 @ refill_inactive_zone 네이밍은 이후 변경함. static void refill_inactive_zone -> static void shrink_active_list
3. 102 (2021-07-24) : v2.6.11 mm/vmscan.c::shrink_list()
  1. 102 (2021-07-24) : shrink_zone->shrink_list(); # 진도 shrink_zone(struct zone *zone, struct scan_control *sc) (mm/vmscan.c) - refill_inactive_zone (mm/vmscan.c) (struct zone *zone, struct scan_control *sc) - shrink_cache(struct zone *zone, struct scan_control *sc) -- get_page_testone(page) --- __put_page(page); -- shrink_list(struct list_head *page_list, struct scan_control *sc) --- try_to_unmap(page) --- __delete_from_swap_cache(struct page *page) ---- radix_tree_delete(&swapper_space.page_tree, page->private); --- swap_free(swp_entry_t entry) ---- swap_info_get(entry); @ already free? 버디 시스템에 넣어줄까? /* * Grab a ref, return true if the page previously had a logical refcount of * zero. ie: returns true if we just grabbed an already-deemed-to-be-free page */ #define get_page_testone(p) atomic_inc_and_test(&(p)->_count) @ Understanding Linux Kernel - Figure 17-6. Swap area data structures - Figure 17-7. Swapped-out page identifier - swap_info_struct 구조체 - swp_entry_t 구조체 - struct swap_info_struct swap_info[MAX_SWAPFILES]; // MAX_SWAPFILES = 32 - shrink_list() -> swap_free(entry) -> swap_info_get(entry) @ swp_entry_t 에 인코딩한 페이지의 정보 - (1) 널 엔트리 : 해당 페이지는 [1] 프로세스의 주소 공간에 속하지 않거나 [2] 프레임이 아직 프로세스에 할당되지 않았음 - (2) 스왕 아웃 : 최하위 비트가 0 이고 [31:1] 비트 중에 1 인 비트가 있음 - (3) 메모리에 있음 최하위 비트가 0 @ 스왑 캐시 - 아래의 동시성 문제를 해결함 - 여러 프로세스가 같은 페이지를 보고 동시에 스왑 인 & 아웃 관련 동작을 할 때 - shrink_list() 에서 특정 페이지를 스왑 아웃을 하고 싶으면, try_to_unmap() 에서 해당 페이지를 사용하는 모든 프로세스의 User Mode Page Tables 에서 페이지를 언 매핑한 경우에만 가능하다. - 스왑 캐시는 shrink_list()를 통해서 스왑 아웃 할 페이지들을 저장한다. @ anon 매핑에서 swap 페이지의 fault 처리 handle_pte_fault(struct vm_fault *vmf) -> do_swap_page(vmf) @ Understanding Linux Kernel - Figure 17-8. The role of the swap cache 연관 함수 (프로세스 anon page) (a) 2개의 프로세스에서 사용하는 anon 페이지 (b) 해당 페이지 프레임은 3 개의 소유자 (2 프로세스, 1 스왑 캐시) swap_info_struct 안의 페이지 슬롯 1 군데에서만 참조 (1 스왑 캐시) shrink_list() - add_to_swap(struct page * page) entry = get_swap_page(); -- __add_to_swap_cache(page, entry, GFP_ATOMIC|__GFP_NOWARN); (c) 해당 페이지 프레임은 1 개의 소유자 (1 스왑 캐시) swap_info_struct 안의 페이지 슬롯을 3 군데에서 참조 (2 프로세스, 1 스왑 캐시) anon 페이지를 언 매핑함 shrink_list() - try_to_unmap() - __delete_from_swap_cache() (d) 페이지 폴트 핸들러가 스왑 캐시에서 페이지 프레임을 발견한다. do_swap_page() - lookup_swap_cache() [ (e) -> (d) 일 경우 ] do_swap_page() - read_swap_cache_async() -- add_to_swap_cache() --- __add_to_swap_cache() ---- radix_tree_insert() (e) 디스크에 쓰는 동안 스왑 인 연산이 발생하지 않으면, 스왑 아웃이 끝난 후, shrink_list() 함수는 페이지 프레임을 스왑 캐시에서 제거한다 shrink_list() - __delete_from_swap_cache(page); -- radix_tree_delete(&swapper_space.page_tree, page->private); delete_from_swap_cache(struct page *page) - radix_tree_delete() swap_map 에 저장된 해당하는 카운터 감소, 페이지 참조 카운터를 감소 해당 페이지 프레임을 해지하여 버디 시스템에 넣는다. p.s. free_page_and_swap_cache(struct page *page) - remove_exclusive_swap_page(struct page *page) -- __delete_from_swap_cache(page); 페이지를 스왑 캐시에서 제거함. 유저 모드 프로세스가 하나도 해당 페이지 슬롯을 참조하지 않을 때, 페이지를 스왑 캐시에서 제거하고, 페이지 사용 카운터를 감소 free_swap_and_cache() - delete_from_swap_cache(page); + 스왑 엔트리가 50% 이상 사용중일 때도 스왑 캐시에서 제거함
4. 103 (2021-07-31) : v5.1 mm/vmscan.c::shrink_page_list()
  1. 103 (2021-07-31) : v5.1 mm/vmscan.c::shrink_page_list() # ULK 버전 shirink_list() 마무리 @ do_swap_page() - read_swap() -> get_swap_bio() -> struct bio -> submmit_bio(READ or WRITE, bio) @ mm 락 처리 루틴 - &mapping->tree_lock 에 대한 락과 page 에 대한 락 비교 (1) rmap.c 처음 릴리즈 v2.5.27 https://elixir.bootlin.com/linux/v2.5.27/source/mm/rmap.c#L14 /* * Locking: * - the page->pte.chain is protected by the PG_chainlock bit, * which nests within the pagemap_lru_lock, then the * mm->page_table_lock, and then the page lock. * - because swapout locking is opposite to the locking order * in the page fault path, the swapout path uses trylocks * on the mm->page_table_lock */ (2) ULK 버전 v2.6.11 https://elixir.bootlin.com/linux/v2.6.11/source/mm/rmap.c#L14 /* * Lock ordering in mm: * * inode->i_sem (while writing or truncating, not reading or faulting) * inode->i_alloc_sem * * When a page fault occurs in writing from user to file, down_read * of mmap_sem nests within i_sem; in sys_msync, i_sem nests within * down_read of mmap_sem; i_sem and down_write of mmap_sem are never * taken together; in truncation, i_sem is taken outermost. * * mm->mmap_sem * page->flags PG_locked (lock_page) * mapping->i_mmap_lock * anon_vma->lock * mm->page_table_lock * zone->lru_lock (in mark_page_accessed) * swap_list_lock (in swap_free etc's swap_info_get) * mmlist_lock (in mmput, drain_mmlist and others) * swap_device_lock (in swap_duplicate, swap_info_get) * mapping->private_lock (in __set_page_dirty_buffers) * inode_lock (in set_page_dirty's __mark_inode_dirty) * sb_lock (within inode_lock in fs/fs-writeback.c) * mapping->tree_lock (widely used, in set_page_dirty, * in arch-dependent flush_dcache_mmap_lock, * within inode_lock in __sync_single_inode) */ (3) v5.1 기준 https://elixir.bootlin.com/linux/v5.1/source/mm/rmap.c#L20 /* * Lock ordering in mm: * * inode->i_mutex (while writing or truncating, not reading or faulting) * mm->mmap_sem * page->flags PG_locked (lock_page) * hugetlbfs_i_mmap_rwsem_key (in huge_pmd_share) * mapping->i_mmap_rwsem * anon_vma->rwsem * mm->page_table_lock or pte_lock * pgdat->lru_lock (in mark_page_accessed, isolate_lru_page) * swap_lock (in swap_duplicate, swap_info_get) * mmlist_lock (in mmput, drain_mmlist and others) * mapping->private_lock (in __set_page_dirty_buffers) * mem_cgroup_{begin,end}_page_stat (memcg->move_lock) * i_pages lock (widely used) * inode->i_lock (in set_page_dirty's __mark_inode_dirty) * bdi.wb->list_lock (in set_page_dirty's __mark_inode_dirty) * sb_lock (within inode_lock in fs/fs-writeback.c) * i_pages lock (widely used, in set_page_dirty, * in arch-dependent flush_dcache_mmap_lock, * within bdi.wb->list_lock in __sync_single_inode) * * anon_vma->rwsem,mapping->i_mutex (memory_failure, collect_procs_anon) * ->tasklist_lock * pte map lock */ @try_to_release() 부분 버퍼 페이지 처리 - 디스크 정보에 대한 캐시 정리 필요 - private -> 버퍼를 가지고 있음. # v5.1 mm/vmscan.c::shrink_page_list() - UKL 기준 shirink_list() 가 하던 동작을 v5.1 에서 하고 있음. @ swap_info_struct 멤버인 swap_cluster_info : SSD 를 위해 추가한 멤버 https://github.com/iamroot16/linux/commit/2a8f9449343260373398d59228a62a4332ea513a @ reclaim 몸통 부분을 보면서 정리 while (!list_empty(page_list)) -> page = lru_to_page(page_list); // 리스트 멤버의 콘테이너 페이지 디스크립터 -> if (!trylock_page(page)) -> page = compound_head(page); @ compound_page 복습 [PATCH] mm: make compound_head() robust - 주소 비트가 4, 8 바이트 단위로 align 되는 특성을 이용한 사파의 기술 - https://github.com/iamroot16/linux/commit/1d798ca3f16437c71ff63e36597ff07f9c12e4d6 - 참고 : http://jake.dothome.co.kr/compound/ @ sc->nr_scanned++; // related with vmppressure @ shrink_node @ BDI : Backing Device INFO (such as HDD, Flash memory...) - inode_write_congested(mapping->host) : write가 혼잡한 상태 - (writeback && PageReclaim(page)) : writeback을 통해 회수를 진행함 @ a page at the tail of the LRU is under writeback - 고려할 3 가지의 경우 정리 https://elixir.bootlin.com/linux/v5.1/source/mm/vmscan.c#L1172
5. 104 (2021-08-07) : v5.1 mm/vmscan.c::shrink_page_list()
  1. 104 (2021-08-07) : v5.1 mm/vmscan.c::shrink_page_list() v5.1 mm/vmscan.c::shrink_page_list() 마무리 split_huge_page_to_list() : thp인 경우 split이 불가능하면 activate_locked 레이블로 이동시키고, 페이지를 split한 order 0 페이지들을 page_list에 추가하고 activate_locked 레이블로 이동한다. compound_page가 매핑되지 않은 경우에만, 각각의 페이지로 split 함. https://elixir.bootlin.com/linux/v2.5.51/source/include/linux/page-flags.h#L244 #define PageReclaim(page) test_bit(PG_reclaim, &(page)->flags) #define SetPageReclaim(page) set_bit(PG_reclaim, &(page)->flags) PG_reclaim, /* To be reclaimed asap */ asap : As soon as possible clean anon: - PageAnon(page) && !PageSwapBacked(page) enum pgdat_flags.PGDAT_DIRTY - reclaim scanning has recently found many dirty file pages at the tail of the LRU.
6. 105 (2021-08-14) : swap, direct migration & LRU
  1. 105 (2021-08-14) : swap, direct migration & LRU 1. LRU & pagevec v2.6.11 복습 (1) 어떻게 pagevec 을 채울까? -> lru_cache_add() - 각 percpu 변수로 lru_add_pvecs lru_add_active_pvecs 가 있음 pagevec 이 가득차면 pagevec 을 zone->lru list 로 넘겨주면서 flush 함. (2) 어떻게 pagevec 을 비울까? release_pages() __pagevec_lru_drain() - mm/swap.c::release_pages() - pagevec 을 release 함! - LRU pagevec 에서 놔주지 않아서 - reference_cnt 를 감소함. reference_cnt 0 이면 제거함 해당 페이지는 아무도 사용하지 않을 때 __pagevec_free() - (1) lru flag 를 지움 - (2) pagevec_add 는 남는 여유공간을 리턴함. 해당 페이지를 사용하지 않는데, LRU 에 넣으면 이상함! 왜냐하면, LRU 는 사용하고 있는 메모리를 관리하는 자료구조임! static inline unsigned pagevec_space(struct pagevec *pvec) { return PAGEVEC_SIZE - pvec->nr; } /* * Add a page to a pagevec. Returns the number of slots still available. */ static inline unsigned pagevec_add(struct pagevec *pvec, struct page *page) { pvec->pages[pvec->nr++] = page; return pagevec_space(pvec); } if (!pagevec_add(&pages_to_free, page)) { ... } pagevec 사이즈가 꽉 찼을 때 동작임. 2. reference_cnt page_cache_get() 에서 reference_cnt 증가함 PFRA 에서 reclaim 에서 1 증가하므로, put_page_testzero() 를 통과하지 못하여, 아래 pagevec_free 를 하지 못함! 3. [PATCH] Swap Migration V5: LRU operations - Christoph Lameter v2.6.15 (1) This is the start of the `swap migration' patch series. - https://github.com/iamroot16/linux/commit/21eac81f252fe31c3cf64b805a1e8652192f3a3b 가상메모리는 그대로, 메모리 접근을 빨리할 수 있도록, 누마 노드에 맞춰서 물리 페이지를 옮겨줌! This breaks out isolate_lru_page() and putpack_lru_page() numa mem policy? (2) migrate_pages() 함수를 추가함 - https://github.com/iamroot16/linux/commit/49d2e9cc4544369635cd6f4ef6d5bb0f757079a7 This adds the basic page migration function with a minimal implementation that only allows the eviction of pages to swap space. shrink_page_list() 와 거의 동일함! int migrate_pages(struct list_head *l, struct list_head *t) -> if (PageAnon(page) && !PageSwapCache(page)) -> add_to_swap(page) -> static int swap_page(struct page *page) struct address_space *mapping = page_mapping(page); -> try_to_unmap(page) -> if(PageDirty(page)) -> pageout(page, mapping) // swap out! -> if (PagePrivate(page)) -> try_to_release_page(page, GFP_KERNEL) -> remove_mapping(mapping, page) -> if (PageSwapCache(page)) -> swap_free(swap); -> __remove_from_page_cache(page); 4. Direct Migration - Christoph Lameter v2.6.16-rc2 - numa migration, memory hotplug 을 지원하는게 동기임 - swap migration 이랑 비슷한 컨셉임 (1) Add direct migration support with fall back to swap. - https://github.com/iamroot16/linux/commit/a48d07afdf18212de22b959715b16793c5a6e57a @ int migrate_page(struct page *newpage, struct page *page) - swap cache 에서 페이지를 가져온 다음 newpage 에 매핑함! @ void migrate_page_copy(struct page *newpage, struct page *page) - flag 설정까지 복붙함 * Pages are locked upon entry and exit. migrate_page_remove_references() - try_to_unmap() vs 다른 프로세서를 통해서 do_swap_page() - do_swap_page() 에서도 lock_page() 를 함! /* Page migration has occured */ - address_space 맵이 락으로 보호되는 구간임 : write_lock_irq(&mapping->tree_lock); ~ write_unlock_irq(&mapping->tree_lock); @ migrate_pages() - page 에 락은 입장 rc = migrate_page(newpage, page); 퇴장동안 걸리고 이후 - 서로 다른 프로세스가 병행적으로 각 각을 진행할 때 시나리오를 고려해보면, ├─ migrate_pages() -> unlock_page: unlock_page(page); ... ├─ do_swap_page() -> lock_page(page) -> if(!PageSwapCache(page)) /* Page migration has occured */ ... 5. Split LRU page replacement design - Rik van Riel, Lee Schermerhorn, Kosaki Motohiro - lru 는 V2.6.28 이전에는 active 하나 inactive 하나씩, 파일과 anon 페이지를 같이 관리함. ex: 128GB 메모리, 스캔 속도 ⬇ - lru 는 V2.6.28 이gn에는 파일 & anon 페이지에 대해 active & inactive 각 각 따로 관리함. 스캔 속도 ⬆ - https://linux-mm.org/PageReplacementDesign - https://linux-mm.org/ProblemWorkloads - https://linux-mm.org/PageReplacementRequirements - https://lwn.net/Articles/147879/ - CLOCK-Pro : 비활성 목록의 페이지가 활성 목록의 페이지보다 덜 자주 참조되도록 합니다. 따라서 [액세스 다이어그램]특정 페이지가 애플리케이션에서 거의 사용되지 않는 경우에도, 가장 최근에 액세스한 페이지에 우선 순위를 지정하는 LRU 방식 과 다릅니다. LRU 참고: (1) ULK : LRU pagevec 그림 네모 4개 (2) https://pr0gr4m.tistory.com/entry/Linux-Kernel-5-LRU-Memory-Reclaim 6. [PATCH] swap: use an array for the LRU pagevecs - 복붙 코드를 LRU 배열로 리팩토링함 - https://github.com/iamroot16/linux/commit/f04e9ebbe4909f9a41efd55149bc353299f4e83b 7. [PATCH] define page_file_cache() function - PG_swapbacked 도입함 - 익명페이지를 설정하는 부분에는 PageSwapBacked(page) 관련 확인이 있음! - https://github.com/iamroot16/linux/commit/b2e185384f534781fd22f5ce170b2ad26f97df70 8. [PATCH] vmscan: split LRU lists into anon & file sets - mmzone.h 쪽에 /* Second 128 byte cacheline */ 캐시 라인 관련 패치가 있음. - https://github.com/iamroot16/linux/commit/4f98a2fee8acdb4ac84545df98cccecfd130f8db 9. [PATCH] vmscan: second chance replacement for anonymous pages - active:inactive ratio = sqrt(memory in GB * 10). - linux-mm PageReplacementDesign 에 anon page 항목의 구현사항이 들어가 있음! - 추가로 active : inactive 메인메모리를 root sqaure raio 산식을 사용함! - https://github.com/iamroot16/linux/commit/556adecba110bf5f1db6c6b56416cfab5bcab698 # [PATCH] per-zone and reclaim enhancements for memory controller: add scan_global_lru macro - scan_global_lru(sc) : scan_control 로 global lru 을 스캔할 지 mem_cgroup lru 할 지 정함. - https://git.kernel.org/pub/scm/linux/kernel/git/history/history.git/commit/mm/vmscan.c?h=v2.6.25-rc1&id=91a45470f7ddc322073752e711a2e8dcbc339e6f 10. [PATCH] Unevictable LRU Infrastructure - kernel 이 wrong pages를 evicts 하면, 성능이 굉장히 안좋아지므로 이를 방지함. - https://github.com/iamroot16/linux/commit/894bc310419ac95f4fa4142dc364401a7e607f65 11. [PATCH] unevictable lru: add event counting with statistics - https://github.com/iamroot16/linux/commit/bbfd28eee9fbd73e780b19beb3dc562befbb94fa
7. 106 (2021-08-21) :
  1. 106 (2021-08-21) : 10 ~ 11. evitable 패치 다시한번 보기 #ifdef CONFIG_UNEVICTABLE_LRU void putback_lru_page(struct page *page) @ unevictable -> reclaim 스캔 대상이 아님! evictable page 가 unevictable LRU list 에 있으면, free 가 안됨!! - 왜 free가 안될까? -> reclaim 대상이 아님! -> 스캔 대상이 아니라 회수가 안됨. if (lru == LRU_UNEVICTABLE && page_evictable(page, NULL)) { if (!isolate_lru_page(page)) { put_page(page); -> isolate_lru_page(page) 성공하면 LRU 에 속해있다는 플래그를 지움! -> redo: ClearPageUnevictable(page); -> if (page_evictable(page, NULL)) -> lru_cache_add_lru(page, lru); - This way, we avoid "stranding" evictable pages on the unevictable list. 락을 걸지 않고 왜 이렇게 했을까? LRU 락? returns 0 on success, -ve errno on failure. isolate_lru_page(page) -> ClearPageLRU(page); put_page(page) -> 리퍼런스 카운트를 내림 * add_page_to_unevictable_list - add a page to the unevictable list * @page: the page to be added to the unevictable list void add_page_to_unevictable_list(struct page *page); @ insert to unevictable - evictable -> unevictable #ifdef CONFIG_UNEVICTABLE_LRU void putback_lru_page(struct page *page) if (page_evictable(page, NULL)) -> add_page_to_unevictable_list(page); @ delte from unevictable - unevictable -> evictable - moving the page from non-evictable to evictable state @ 페이지를 undevictable 로 바꿈! void lru_cache_add_lru(struct page *page, enum lru_list lru) if(PageUnevictable(page)) -> ClearPageUnevictable(page); 12. [PATCH] mlock: mlocked pages are unevictable - Nick Piggin - https://github.com/iamroot16/linux/commit/b291f000393f5a0b679012b39d79fbc85c018233 - mlock 한 페이지는 unevictable 함! - 4가지 전략으로 할 수 있음! fault path 가 뭘까? (1) PG_mlocked 로 fault path에 대한 vmscan 성능을 효과적으로 함! - unevictable pages 들에 대해서 page_referenced()/try_to_unmap() 실행하는 것을 방지함! (2) mm/internal.h에 새로운 기능을 만들어 놓았음! - mm/internal.c::mlock_vma_pages_range() - Mark page as mlocked if not already. mlock_vma_page() - lock_page may only be called if we have the page's inode pinned. linux/pagemap.h::lock_page(struct page *page) -> mm/filemap.c::__lock_page() -> __wait_on_bit_lock() - mm/internal.c::munlock_vma_pages_all(struct vm_area_struct *v - __munlock_vma_pages_range(vma, vma->vm_start, vma->vm_end); - 워커 세팅 struct munlock_page_walk mpw = { .vma = vma, }; struct mm_walk munlock_page_walk = { .pmd_entry = __munlock_pmd_handler, // pmd 세터 .pte_entry = __munlock_pte_handler, // pte 에 대해 munlock 해줌! .private = &mpw, .mm = mm, }; - walk_page_range(start, end, &munlock_page_walk); -> munlock_vma_page(page); (3) c:page_evictable 에 mlocked 포함 unevictable 인 것을 확인함! - new page 가 왜 나오지? 랑 fault path ?? - in the fault path, handle_mm_fault(). 페이지 폴트로 실행하는 함수 루틴을 말함! (4) mm/rmap.c::try_to_munlock() -> ClearPageMlocked() - mm/rmap.c::try_to_unlock() munlock 으로 이름을 변경했는데, 커밋 코멘트에 반영안되 있어서 햇갈렸음. - https://lore.kernel.org/patchwork/patch/99978/ - 이것은 lru 리스트 링크 중 하나를 mlock_count로 사용하는 것을 효과적으로 대체합니다. ?? # 참고 - mlock(), mlock2(), mlockall()은 호출 프로세스 가상 주소 공간의 일부 내지 전체를 램에 고정하여 그 메모리가 스왑 영역으로 빠지지 않도록 한다. - https://man7.org/linux/man-pages/man2/mlock.2.html - https://wariua.github.io/man-pages-ko/mlockall%282%29/ @ CONFIG_UNEVICTABLE_LRU 1 -> MLOCK_PAGES 1 int try_to_munlock(struct page *page) -> try_to_unmap_anon(page, 1, 0); -> if (MLOCK_PAGES && unlikely(unlock)) -> ret = SWAP_SUCCESS; /* * Subfunctions of try_to_unmap: try_to_unmap_one called * repeatedly from either try_to_unmap_anon or try_to_unmap_file. */ static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma, int migration) * Mlocked pages: check VM_LOCKED under mmap_sem held for read, if we can * acquire it without blocking. If vma locked, mlock the pages in the cluster, * rather than unmapping them. If we encounter the "check_page" that vmscan is * trying to unmap, return SWAP_MLOCK, else default SWAP_AGAIN. 13. [PATCH] vmscan: simplify shrink_inactive_list() - KOSAKI Motohiro - https://github.com/torvalds/linux/commit/e247dbce5cc747a714e8dcbd6b3f442cc2a284cf
8. 107 (2021-08-28) :
  1. 107 (2021-08-28) :
9. 108 (2021-09-04) :
  1. 108 (2021-09-04) :
10. 109 (2021-09-11) :
  1. 109 (2021-09-11) :