Redblack Tree / Augmented RB Tree / Interval Tree
- https://zeddios.tistory.com/237
- https://gwpaeng.tistory.com/309
- https://assortrock.com/88
- http://shumin.co.kr/red-black-tree-%ec%82%bd%ec%9e%85/
- http://shumin.co.kr/red-black-tree-%ec%82%ad%ec%a0%9c/
- http://shumin.co.kr/%EC%A6%9D%EA%B0%95-%ED%8A%B8%EB%A6%AC/
- http://shumin.co.kr/%EA%B0%84%EA%B2%A9-%ED%8A%B8%EB%A6%AC-interval-tree/

include/linux/interval_tree_generic.h

include/linux/pagemap.h
- linear_page_index()
- __page_set_anon_rmap()

http://jake.dothome.co.kr/rmap-1/
https://www.slideshare.net/AdrianHuang/reverse-mapping-rmap-in-linux-kernel

anon vma
- avc 들을 interval tree 형태로 가지고 있음
- Interval tree는 augmented red black tree로 interval을 node 값으로 가짐
- (a, b) 중 a를 이용해서 node를 삽입하고 tree 내의 위치가 결정됨. 즉 a 값으로 정렬되어 있음
- b 값은 augment 값을 만들 때 쓰이고 한 노드의 augment 값은 노드의 sub tree 중 가장 큰 b 값이 됨
- augment 값은 search 할 때 사용됨
- insert 시 각 노드의 augment 값은 search와 동시에 업데이트 됨
- 검색 입력으로 interval이 들어오면 overlapping이 있는 가장 작은 a 값을 가지는 노드를 출력해 줌
- 그 다음에는 overlapping이 있는 그 다음 작은 a 값의 node를 출력함
- search 순서는 a 순서대로, node 방문 순서도 a 순서대로임
- right node subtree 검색해서 overlapping이 없으면 그냥 종료해도 됨. 부모나 타 노드 검색 필요 X

RCU 복습
- https://hyeyoo.com/135
- slab cache page는 RCU로 보호 받도록 설정할 수 있으나 slab cache 내부의 object도 자동으로 RCU 보호를 받는 것은 아니다

Semaphore
- https://hyeyoo.com/86?category=900545
- https://hyeyoo.com/87?category=900545

rmap에서 anon_vma의 mapping 체크 관련 논의
- https://lkml.iu.edu/hypermail/linux/kernel/1105.3/02622.html

RW semaphore
- https://0xax.gitbooks.io/linux-insides/content/SyncPrim/linux-sync-5.html
- https://blog.dasomoli.org/246/

HANDOFF
- read path를 빠르게 하려고 최적화하다가 writer 보다 reader가 새치기 하는 경우를 방지하기 위한 것으로 보임

RW semaphore codes
- include/linux/rwsem.h
- kernel/locking/rwsem.c
- down 할 때 count 값이 올라가고 up할 때 내려간다
- wait list에 있는 task들은 count값을 올리지 않고 wait에서 빠져서 running할 때 count값을 올린다

rw_semaphore 구조체
- count : 현재 running 중인 reader의 수, writer lock 여부, waiter 존재 여부, handoff 수행 중 여부 등을 표시
- owner : writer의 경우 down할때 owner 설정하고 up할 때 clear한다. 그러나 reader의 경우 up할 때 flag bit만 clear하고 task 주소는 그대로 남겨둔다. 따라서 가장 마지막 reader가 남는다
- osq : optimistic spin queue인데 뭔지 모름
- wait_lock : semaphore 보호를 위한 스핀락
- wait_list : 대기 중인 task를 연결하기 위한 list head
- 나머지는 디버그 용으로 config에 따라 사라진다

count 값 정리
- 0 : writer lock 여부
- 1 : waiter 존재 여부
- 2: handoff 여부
- 3 ~ 7 : reserved
- 8 ~ 62 : reader count
- 63 : read fail bit (reader 너무 많음)

owner
- 하위 비트에 다음 플래그 저장
- reader owned 여부
- nonspinnable 여부

down_read()
- L1463 : might_sleep()으로 양보
- L1464 : 디버그 코드로 lock verification 수행
- L1466 : LOCK_CONTENDED() 매크로로 함수 __down_read()를 수행

__down_read()
- __down_read_common() 함수 수행
- TASK_UNINTERRUPTIBLE로 수행한다

__down_read_common()
- L1213 : 함수 rwsem_read_trylock()로 fastpath를 시도
- L1214 : fastpath 실패시 함수 rwsem_down_read_slowpath()를 시도
- L1215 : slowpath 실패시 인터럽트 에러 리턴
- L1218 : 성공하면 0 리턴

rwsem_read_trylock()
- 인자로 rw_semaphore sem, count값 cntp를 받는다
- L238 : atomic operation으로 RWSEM_READER_BIAS 만큼 sem->count 값을 올려주고 cntp에 업데이트된 count값을 받는다
- L240 : reader가 너무 많아져서 read가 실패하면 rwsem_set_nonspinnable()로 semaphore에 nonspinnable이라고 표시한다
- L243 : read가 성공한 경우 함수 rwsem_set_reader_owned()로 owner를 current task로 설정하고 true 리턴
- L248 : 아니면 false 리턴

rwsem_set_nonspinnable()
- L225 : owner를 가져온다
- L228 : owner가 reader가 아니면 break
- L230 : owner가 nonspinnable이면 break
- L232 : atomic cmpxchg로 sem->owner를 owner | RWSEM_NONSPINNABLE 로 업데이트한다. 업데이트 실패하면 L228부터 다시 반복한다

rwsem_set_reader_owned()
- sem->owner를 RWSEM_READER_OWNED를 붙여서 인자 owner로 업데이트한다
- 이 때 RWSEM_NONSPINNABLE 여부는 보존한다

rwsem_down_read_slowpath()
- 인자로 sem, count, state를 받는다
- L885 : fast path에서 늘어난 count 보정을 위해 adjustment를 -RWSEM_READER_BIAS 로 초기화
- L896 : wake_q를 로컬 변수로 정의
- L906 : sem->owner가 reader이고 rcnt > 1 이면서 writer locked가 아니면 queue로 점프하여 reader optimistic lock stealing을 못하게 한다
- L913 : writer locked, handoff가 아니면 reader optimistic lock stealing하여 wait queue에 있는 task보다 먼저 read 처리를 시도한다
- L914 : sem을 reader owned로 변경
- L921 : rcnt == 1로 현재 돌고 있는 reader가 현재 task 하나고 waiter가 존재할 경우 if 문 진입
- L922 : wait lock
- L923 : wait list가 비어있지 않으면 함수 rwsem_mark_wake()로 wait list에 있는 reader task들을 wait_q로 옮겨서 깨울 준비를 한다. 이 때 함수를 RWSEM_WAKE_READ_OWNED로 호출
- L926 : wait unlock
- L927 : 함수 wake_up_q()로 wake_q에 있는 task들을 깨운다
- L929 : sem을 리턴하고 종료. if 문 종료
- L932 : queue 시작
- L933 : waiter의 task, type, timeout을 각각 current, RWSEM_WAITING_FOR_READ, jiffies + RWSEM_WAIT_TIMEOUT 로 설정
- L937 : wait lock
- L945 : wait list가 empty이고 writer lock 및 handoff가 아닌 경우 wait lock을 풀고 rwsem_set_reader_owned()로 semaphore를 자신이 차지하고 sem 리턴
- L954 : wait list가 empty이나 writer lock 또는 handoff가 있으면 자신이 기다려야 하므로 adjustment에 waiter flag 추가
- L956 : 자신을 wait list에 추가
- L959 : sem->count에 adjustment에 더해서 fastpath에서 늘어난 count값 복구 및 waiter 플래그 반영
- L967 : 돌고 있는 reader/writer가 없는 경우 sleep하고 있는 task들을 깨워야 하므로 non spinnable flag clear 후 wake를 true로 변경
- L971 : wake == true 이거나, writer lock이 없고 waiter가 있으면 rwsem_mark_wake(), RWSEM_WAKE_ANY로 깨울 준비 수행
- L975 : wait unlock
- L976 : 함수 wake_up_q()로 wake_q에 있는 task들을 깨운다
- L979 : semaphore read lock을 잡을 때까지 for 문 루프 수행 시작
- L980 : current task 상태를 status로 업데이트
- L981 : waiter.task == NULL 이면 break. (rwsem_mark_wake()에서 깨우는 준비 중에 NULL이 된다)
- L985 : task가 signal을 받으면 task가 NULL이면 break. NULL이 아니면 wait lock을 걸고 out_nolock으로 이동
- L993 : schedule()로 sleep
- L997 : 깨어난 이후 TASK_RUNNING으로 task 상태 변경
- L999 : sem 리턴하여 read lock 잡고 종료
- L1001 : out_nolock 시작
- L1002 : task를 wait list에서 제거
- L1003 : wait list가 비어있으면 sem->count에서 waiter 및 handoff 플래그 클리어
- L1007 : wait unlock
- L1008 : task 상태를 TASK_RUNNING으로 변경
- L1010 : 에러 리턴하고 종료

rwsem_mark_wake()
- 인자로 rw_semaphore sem, 깨울 task type wake_type, 그리고 wait list에서 task를 받아올 wake_q 를 받는다
- L395 : wait list의 첫 번째 task를 가져온다
- L398 : task가 writer이고 wake_type이 RWSEM_WAKE_ANY이면 task를 wake_q에 추가하고 리턴한다
- L410 : task가 writer이고 wake_type이 RWSEM_WAKE_ANY이 아니면 그냥 리턴한다
- L416 : active reader가 너무 많으면 깨우지 말고 그냥 리턴
- L424 : wake_type != RWSEM_WAKE_READ_OWNED 이면 if 문 진입
- L428 : sem->count를 RWSEM_READER_BIAS 만큼 증가
- L429 : sem->count가 writer lock이 있었으면 sem->count를 다시 RWSEM_READER_BIAS 만큼 감소시켜 복원하고 리턴한다. 즉 reader를 깨우지 않고 그냥 나간다. 또한 write lock이 있는데 handoff가 없고 너무 오래 기다린 경우 handoff flag를 sem->count에 추가한다
- L450 : writer lock이 없는 경우에는 __rwsem_set_reader_owned()로 첫 번째 reader를 owner로 만든다
- L452 : if 문 끝
- L476 : wlist local list 선언
- L477 : wait list에 있는 task들 중 reader만 골라서 wlist에 옮긴다. 이 때 최대 256개를 옮긴다
- L492 : 옮긴 개수 - 1 만큼 adjustment 조정. 1개를 뺀 이유는 L428에서 한 번 미리 증가시켰기 때문
- L494 : wait list가 비었으면 waiter flag clear
- L503 : 옮긴 task가 존재하고 handoff가 설정되어 있었으면 clear
- L506 : sem->count adjustment 만큼 증가
- L510 : wlist에 있는 task들에 대해 get_task_struct() 수행, waiter->task를 NULL로 변경, wake_q_add_safe()로 wake_q로 이동시킨다

wake_q_add_safe()
- L929 : __wake_q_add()로 task를 wake_q에 추가
- L930 : 실패하면 put_task_struct() 수행

get_task_struct() / put_task_struct()
- task->usage refcount를 1 증가 / 감소시킴

down_read_interruptible()
- down_read()와 동일하나 __down_read_common()을 TASK_INTERRUPTIBLE로 호출

down_read_killable()
- down_read()와 동일하나 __down_read_common()을 TASK_KILLABLE로 호출

down_read_trylock()
- sem->count가 0이면 RWSEM_READER_BIAS 만큼 증가시킨 뒤 rwsem_set_reader_owned()로 owner 취득하고 1 리턴
- 실패하면 0 리턴

up_read()
- __up_read() 호출

__up_read()
- L1295 : rwsem_clear_reader_owned()는 디버그 함수이므로 빈 함수
- L1296 : sem->count를 RWSEM_READER_BIAS 만큼 감소
- L1298 : spinning reader/writer는 없는데 waiter는 있는 경우, clear_nonspinnable()로 non spinnable flag 지우고 rwsem_wake() 함수로 wait list에 있는 task를 깨운다

rwsem_wake()
- L1172 : wake_q 로컬 변수 선언
- L1174 : wait lock 잡고 irqsave
- L1176 : wait list가 비어 있지 않으면 rwsem_mark_wake() 함수를 RWSEM_WAKE_ANY로 호출, wake_q에 깨울 task 이동
- L1179 : wait unlock 및 irqrestore
- L1180 : wake_q()로 wake_q에 있는 task를 깨움
- L1182 : sem 리턴하면서 종료

down_write()
- L1516 : might_sleep()으로 양보
- L1518 : LOCK_CONTENDED() 매크로로 __down_write() 호출

__down_write()
- __down_write_common()을 TASK_UNINTERRUPTIBLE로 호출

__down_write_common()
- L1261 : 함수 rwsem_write_trylock()로 fast path 시도
- L1262 : 실패하면 rwsem_down_write_slowpath()로 slowpath 수행 후 실패하면 EINTR 리턴
- L1266 : 성공시 0 리턴

rwsem_write_trylock()
- L255 : sem->count == 0 이면 write locked set 하고 owner를 현재 task로 설정한 후 true 리턴
- L260 : 0이 아니면 false 리턴

rwsem_down_write_slowpath()
- 인자로 rw_semaphore sem, state를 받는다
- L1023 : wake_q 로컬 변수 선언
- L1026 : optimistic spinning 및 steal lock 관련 부분은 생략
- L1035 : waiter의 task, type, timeout을 각각 current, RWSEM_WAITING_FOR_WRITE, jiffies + RWSEM_WAIT_TIMEOUT 로 설정
- L1039 : wait lock
- L1042 : wait list가 비어 있으면 wstate를 WRITER_FIRST 아니면 WRITER_NOT_FIRST로 설정
- L1044 : wait list tail에 현재 task를 추가
- L1047 : WRITER_NOT_FIRST인 경우 if 문 진입
- L1058 : 이미 writer locked이 잡혀 있으면 wait로 점프
- L1061 : active read spinner가 없으면 RWSEM_WAKE_ANY로 아니면 RWSEM_WAKE_READERS로 rwsem_mark_wake() 함수 호출하여 wait list의 task 깨울 준비
- L1065 : wake_q에 task가 존재하면 wait unlock —> wake_up_q() —> wake_q_init() —> wait lock 차례로 수행하여 wake_q의 task들을 깨움, if 문 종료
- L1076 : WRITER_FIRST인 경우 sem->count에 waiter 설정
- L1079 : wait 시작
- L1081 : task state 설정
- L1082 : wait for 문 루프 시작
- L1083 : rwsem_try_write_lock() 함수로 write lock 시도하고 성공하면 break
- L1088 : wait unlock
- L1098 : state == HANDOFF 이고 현재 owner가 없으면 (writer가 up하고 나간 직후) trylock_again으로 점프
- L1103 : for 문 시작. active locker가 모두 사라질 때까지 여기서 루프
- L1104 : task에 signal 도달하면 out_nolock으로 점프
- L1107 : schedule()로 sleep
- L1109 : task state set
- L1114 : wstate == HANDOFF 이면 break
- L1117 : wstate ==  WRITER_NOT_FIRST 이지만 내가 wait list의 첫 번째이면 wstate를 WRITER_FIRST로 변경
- L1121 : sem->count에 read/write spinner 없으면 break
- L1129 : wstate == WRITER_FIRST이고, current가 RT task이거나 시간이 timeout보다 더 많이 지났으면 wstate를 HANDOFF로 변경하고 break
- L1135 : loop 끝
- L1136 : trylock_again 시작
- L1137 : wait lock
- L1138 : for loop 끝
- L1139 : task 상태를 TASK_RUNNING으로 변경
- L1140 : task를 wait list에서 제거
- L1141 : wait unlock
- L1144 : 리턴

rwsem_try_write_lock()
- L546 : sem->count를 읽어온다
- L547 : do 시작
- L548 : count에 handoff가 있는지 has_handoff에 표시
- L550 : count에 handoff가 있고 wstate가 WRITER_NOT_FIRST이면 false 리턴
- L553 : new = count
- L555 : count에 active spinner가 있으면 진입
- L556 : count에 handoff가 있고 wstate != HANDOFF 이면 false 리턴
- L559 : new에 HANDOFF 추가
- L560 : count에 active spinner 없으면 진입
- L561 : writer locked 추가 및 handoff 제거
- L564 : wait list에 나 혼자이면 waiter 표시 제거
- L567 : sem->count를 new로 업데이트
- L573 : new에 handoff 있으면 false 리턴
- L576 : owner를 task로 변경하고 true 리턴

down_write_killable()
- down_write()와 동일하나 TASK_KILLABLE로 호출

down_write_trylock()
- 결과적으로 rwsem_write_trylock() 호출

rwsem_write_trylock()
- sem->count == 0이면 count에 write lock 표시하고 owner를 current task로 설정한 뒤 true 리턴
- 아니면 false 리턴

up_write()
- __up_write() 호출

__up_write()
- L1320 : owner를 clear
- L1321 : sem->count에서 writer lock 제거
- L1322 : waiter가 남아 있는 경우 rwsem_wake()로 waiter task들을 모두 깨움