Ch8. Bottom Halves and Deferring Work

이전 장에서 다루었던 인터럽트 핸들러의 특징을 다시 확인해보면, 인터럽트 핸들러는 비동기적으로 실행되기 때문에 인터럽트 핸들러는 가능한 빨리 실행되어야한다. 또한 하드웨어를 다루기 때문에 timing-critical하며, block되지 말아야 하기 때문에 프로세스 컨텍스트에서 실행되면 안된다. 인터럽트 핸들러가 빠르고 즉각적으로 하드웨어 인터럽트를 처리한다는 운영체제의 요구를 충족한다면, 상대적으로 중요도가 낮은 일들은 나중에 인터럽트가 가능할 때로 미루어 두는 것이 괜찮으며 그렇게 요구된다. 따라서 인터럽트를 관리하는 것은 두 파트로 나누어 볼 수 있겠다. 첫번째 파트는 인터럽트 핸들러(top halves), 두번째 파트는 bottom halves이다.

1. Bottom Halves

Bottom half의 역할은 인터럽트 핸들러가 수행하지 않은 관련 일들을 수행하는 것이다. 하드웨어에 인터럽트를 수신했다고 알리거나, 하드웨어로부터 데이터를 복사하는 등 timing-sensitive한 일은 인터럽트 핸들러가 처리한다. Top half와 bottom half를 나누는 좋은 기준이 있다.

• 시간이 중요한 일이라면 인터럽트 핸들러에 맡긴다.
• 하드웨어에 연관된 일이라면 인터럽트 핸들러에게 맡긴다.
• 다른 인터럽트로 인해 작업이 중단되지 않도록 해야한다면 인터럽트 핸들러에게 맡긴다.
• 이외의 경우에는 bottom half에게 맡긴다.

핵심은 인터럽트 핸들러가 빠르게 실행되는 전략이 가장 좋다.

1.1. Why Bottom Halves?

인터럽트 핸들러가 실행되는 동안 모든 프로세서에 대해 현재 인터럽트 라인이 비활성화 된다. 만약 IRQF_DISABLED가 등록된 인터럽트 핸들러라면 모든 인터럽트 라인이 비활성화 된다. 따라서 인터럽트 핸들러에서의 시간을 최소화 하는 것이 시스템 반응과 성능면에서도 중요하고, 몇몇의 일들은 뒤로 미루는 것이 필요하다. 그럼 그 "나중"은 언제일까? 이는 시스템이 덜 바쁘고, 인터럽트가 다시 가능해지는 시기를 의미한다. 실질적으로 bottom half는 인터럽트가 돌아오면 즉각적으로 실행된다.

1.2. A World of Bottom Halves

Bottom half를 구현하기 위해 여러 메커니즘이 존재한다. 리눅스 초기에는 bottom half를 구현하기 위해 BH 인터페이스만을 제공했다. BH 인터페이스는 초기의 다른 인터페이스들 처럼 간단했다. 전체 시스템에서 32개의 bottom half로 이루어진 정적 리스트를 제공했다. 각각의 BH는 전역적으로 동기화 되었다. 동시에 실행될 수 없었고, 다른 프로세서에서 조차도 동시에 실행될 수 없었다. 이후 BH 인터페이스를 대체할 task queue가 공개되었다. 호출할 함수들의 linked list가 포함된 큐가 있고, 함수들은 큐에 들어온 시간에 따라 특정한 시간에 호출되었다. 하지만 이 역시도 네트워크와 같은 성능이 중요한 시스템에 대해 결고 가볍지 못했다. 리눅스 커널 2.3 개발시기에 sortirq와 tasklet이 공개되었고, 이는 BH 인터페이스를 완전히 대체하였다. Softirq는 어떤 프로세서에서든 동시에 실행될 수 있는 정적으로 정의된 bottom half이며, 심지어 같은 유형의 두 bottom half도 동시에 실행할 수 있다. Tasklet는 softirq를 기반으로 유연하고 동적으로 할당되는 bottom half이다. 두개의 다른 tasklet는 다른 프로세서에서 동시에 실행될 수 있으나, 같은 유형의 두 tasklet는 동시에 실행될 수 없다. 대부분의 bottom half 처리를 위해 tasklet이면 충분하다. Softirq는 성능이 네트워크와 같이 성능이 중요시 되는 데에 이용한다. 두개의 softirq가 같이 실행될 수 있다는 점에서 softirq를 사용하는 것은 더 많은 주의가 요구된다. 또한 컴파일 시점에 정적으로 등록되어야한다. 반면 tasklet는 동적으로 등록될 수 있다.
리눅스 커널 2.5 개발시기엔 BH 유저들이 bottom half 인터페이스를 변환하며 BH 인터페이스는 마침내 버려졌다. 그리고 task queue 인터페이스는 work queue 인터페이스로 변환되었다. 결론적으로 리눅스 커널 2.6에는 bottom-half 메커니즘이 3개가 남아있다: softirq, tasklet, work queue.

2. Softirqs

Softirq가 직접적으로 사용되는 경우는 거의 없다. 하지만 tasklet이 softirq를 기반으로 만들어졌기 때문에, softirq에 대해 아는 것이 중요하다.

2.1. Implementing Softirqs

Softirq는 컴파일 시점에 정적으로 할당된다. Softirq는 softirq_action 구조체로 표현된다.

struct softirq_action {
	void (*action)(struct softirq_action *);
};

static struct softirq_action softirq_vec[NR_SOFTIRQS];

커널은 softirq의 개수를 32개로 제한한다. 현재 커널에는 9개만 남아있다.
Softirq는 다른 softirq를 preempt하지 않는다. Softirq를 preempt할 수 있는 유일한 방법은 인터럽트 핸들러이다. 다른 softirq는 다른 프로세서에서 실행될 수 있다.
등록된 softirq가 실행되기 전에 반드시 마킹되어야한다. 이를 raising the softirq라고 한다. 보통 인터럽트 핸들러가 반환 전에 softirq를 마킹한다. Softirq는 다음 상황에 확인되고 실행된다.

• 하드웨어 인터럽트 코드에서 나올 때
• ksoftirqd 커널 쓰레드에 있을 때
• 네트워킹 서브시스템과 같이 명시적으로 보류중인 softirqs를 체크하고 실행할 때

2.2. Using Softirqs

Softirq는 시스템에서 timing-critical하고 bottom-half 처리에 중요한 작업들을 위해 예약되어있다. 최근에는 네트워킹과 block 기기들에서만 이용된다. 추가로 커널 타이머와 tasklet도 softirq를 기반으로 생성된다. Tasklet이 성능도 준수하고, 사용하기도 간단하지만, timing-critical하고 스스로 락킹을 잘 수행하는 애플리케이션들에 대해서는 softirq가 더 좋은 해결책이 될지 모른다.
Softirq는 컴파일 시점에 정적으로 정의한다. 커널은 0부터 시작하는 인텍스를 이용해 우선순위를 설정한다. 인덱스 값이 낮을수록 먼저 실행된다.
새로운 softirq를 추가할 때, 우선순위에 따라 삽입하는 위치가 달라진다. 관습적으로 인덱스가 낮은 것이 처음에, 인덱스가 높은 것이 뒤에 배치되고, 새로운 엔트리는 보통 BLOCK_SOFTIRQ와 TASKLET_SOFTIRQ 사이에 배치된다.
다음으로는 softirq 핸들러가 open_softirq()함수에 의해 런타임에 등록된다.

open_softirq(NET_TX_SOFTIRQ, net_tx_action);
open_softirq(NET_RX_SOFTIRQ, net_rx_action);

이 함수는 두개의 인자를 갖는다. 첫번째는 softirq의 인덱스 값이고, 두번째는 핸들러 함수이다. Softirq 핸들러는 인터럽트가 활성화 되어있을 때 실행되고 sleep상태로 들어가지 않는다. 핸들러가 실행되는 동안 현재 프로세서는 비활성화된다. 다른 프로세서는 다른 softirq를 실행할 수 있다. 같은 softirq가 실행되는 동안에 다른 프로세서가 이를 동시에 실행할 수 있는데, 이는 어떤 공유된 데이터이건 적절한 locking이 필요하다는 것을 의미한다. 허나 locking 기법을 활용하는 것은 softirq를 이용하는 목적과 맞지 않고, 오히려 tasklet을 이용하는 것이 더 권장되는 이유이기도 하다. 따라서 대부분의 softirq 핸들러는 프로세서별 데이터에 의존, locking이 필요하지 않도록 한다.
Softirq의 존재 이유는 확장성이다. 만약 많은 프로세서로 확장할 필요가 없다면 tasklet을 쓰는 것이 좋다.

3. Tasklets

Tasklet은 softirq를 기반으로 설계된 bottom-half 매커니즘이다. Tasklet은 더 간단한 인터페이스와 느슨한 locking 규칙을 제공한다. Softirq는 자주 사용되거나 다중 쓰레드 사용시에 요구되며, tasklet는 이보다 더 다양한 경우에 이용될 수 있다. 따라서 대부분은 tasklet를 이용해 bottom-half를 처리할 것이다.

3.1. Implementing Tasklets

Tasklet는 두개의 softirq(HI_SOFTIRQ, TASKLET_SOFTIRQ)로 표현된다. HI_SOFTIRQ가 TASKLET_SOFTIRQ보다 먼저 실행된다.
Tasklet은 tasklet_struct 구조체로 표현된다.

struct tasklet_struct {
	struct tasklet_struct *next; 
    unsigned long state; // 0, TASKLET_STATE_SCHED, TASKLET_STATE_RUN
    atomic_t count; // reference count, 0이면 tasklet 사용 가능
    void (*func)(unsigned long); // tasklet 핸들러
    unsigned long data; // 핸들러의 인자값
};

스케줄된 tasklet은 두개의 per-processor 구조체에 저장된다. 일반적인 tasklet은 tasklet_vec에, 높은 우선순위의 tasklet은 tasklet_hi_vec에 저장된다. tasklet의 스케줄링은 tasklet_schedule() 혹은 tasklet_hi_schedule()에 의해 진행된다.
Tasklet의 구현은 간단하지만 영리하다. 모든 tasklet은 두 softirq인 HI_SOFTIRQ, TASKLET_SOFTIRQ위에서 다중화된다. Tasklet이 스케줄되면, 커널은 하나의 softirq를 발생시킨다. 이 softirq들은 특별한 함수에 의해 처리된다. 이 함수는 주어진 유형중 하나의 tasklet만 실행될 수 있도록 보장한다.

3.2. Using Tasklets

Tasklet은 동적으로 생성되고 쉽게 이용할 수 있고 빠르기 때문에 가장 선호되는 메커니즘이다.
Tasklet의 생성은 다음과 같이 가능하다.

DECLARE_TASKLET(name, func, data); // 정적 생성, count가 0으로 초기화되어 tasklet이 활성화
DECLARE_TASKLET_DISABLED(name, func, data); // 정적 생성, count가 1로 초기화되어 tasklet이 비활성화

tasklet_init(t, tasklet_handler, dev); // 동적 생성

Softirq와 마찬가지로, Tasklet은 sleep할 수 없다. 그렇기 때문에 세마포어나 다른 blocking 함수를 이용할 수 없다. Tasklet은 인터럽트가 가능할 때에도 실행할 수 있기 때문에 tasklet이 데이터를 인터럽트 핸들러와 공유한다면 조심해야한다. Tasklet이 데이터를 다른 tasklet 및 softirq와 공유한다면, 적절한 락킹 기법을 이용해야한다.
Tasklet은 해당 tasklet을 스케줄한 프로세서에서만 실행한다. 이는 프로세서의 캐시를 더 잘 활용한다.

3.3. ksoftirqd

Softirq의 처리는 프로세서별 커널 쓰레드에 의해 도움받는다. 커널은 많은 시기에 softirq를 처리한다. 가장 흔한 경우는 인터럽트를 처리하고 나올 때이다. Softirq는 큰 네트워크 트래픽을 처리하는 등 높은 비율로 발생될 수 있고, 심지어 softirq 함수는 스스로를 재활성화할 수 있다. Softirq가 높은 비율로 발생하고, 스스로 활성화 시키는 가능성들이 user-space의 프로그램들로 하여금 프로세서 타임을 적게 가져가도록 초래할 수 있다. 이를 해결하기 위해 두가지 방안이 제시되었다.
첫번째 방안은 softirq가 들어오면 계속 처리하고, 반환하기 전에 보류중인 softirq를 다시 확인하고 다시 처리하는 것이다. 이 방안의 문제는 과부화 환경에서 많은 softirq가 발생하고 계속해 재활성화 하는 경우에 user-space가 무시된다는 것이다.
두번째 방안은 재활성화된 softirq를 처리하지 않는 것이다. 인터럽트로부터 돌아오면 커널은 보류중인 softirq만 확인하고 평소처럼 실행한다. 스스로 재활성화된 softirq가 있으면, 커널이 보류중인 softirq를 실행하는 다음시기(다음 인터럽트가 발생할 때 까지)까지 실행되지 않는다. 더 안좋은 점은, idle하지 않은 시스템에서도 softirq를 바로 처리하는 것이 이득이다. 따라서 이런 접근은 user-space가 굶는 것을 방지하긴 하지만, softirq를 굶길 수 있고, idle 시스템의 장점도 챙기지 못한다.
Softirq를 디자인한 개발자들은 커널이 재생산된 softirq를 바로 처리하지 못하도록 구현하였다. 대신 softirq의 수가 과도하게 증가하면 커널 쓰레드를 통해 부하를 처리하며 커널 쓰레드는 가장 낮은 우선순위로 실행되도록 하여 중요한 것들이 먼저 처리될 수 있도록하였다. 이 방법으로 user-space가 프로세서 타임이 부족한 현상을 방지할 수 있었고, 과도한 softirq도 실행되도록 보장했다.
프로세서당 하나의 쓰레드가 있고, 각각의 쓰레드는 ksoftirqd/n으로 불린다(n은 프로세서 번호).

3.4. The Old BH Mechanism

과거의 BH 인터페이스는 정적으로 정의되고, 32개 까지만 정의할 수 있었다. 핸들러가 컴파일 타임에 정의되어야 했기 때문에 모듈에서 BH 인터페이스를 직접 사용할 수 없었다. 나중에는 32개의 bottom half만 정적으로 등록할 수 있다는 사실이 주요한 장애 원인이 되었다. BH 핸들러는 다른 타입이여도 동시에 실행될 수 없었다. 동기화는 쉬웠지만, 멀티 프로세서의 확장성에서는 이점을 가져오지 못했다. 리눅스 2.4에서는 BH 인터페이스가 tasklet을 기반으로 구현되었다. 커널 개발자들은 bottom half를 대체하기 위해 task queue를 제안하였다. 결론적으로 BH 인터페이스 유저들이 모두 softirq로 옮겨가며 BH 인터페이스가 제거되었다.
(해당 부분 내용 정리 후 다시 작성 예정)

4. Work Queues

Work queue는 일을 커널 쓰레드로 미룬다-이는 항상 프로세스 컨텍스트에서 실행된다. Work queue는 또한 스케줄링 가능하고, sleep 상태에 들어갈 수 있다.
Work queue는 미루어진 일이 sleep 상태에 놓일 필요가 있으면 사용된다. 만약 그럴 필요 없는 일들이라면 softirq나 tasklet을 이용하는 것이 좋다. Work queue는 많은 메모리를 할당해야하거나 세마포어가 필요하거나, block I/O를 수행하는 상황에서 유용하다.

4.1. Implementing Work Queues

Worker thread라고 하는 커널 쓰레드를 생성해(보통은 default worker thread를 이용) work queue를 처리한다. Default worker thread는 events/n으로 불린다(n은 프로세서 번호). Worker 쓰레드는 시스템의 각각의 프로세서에 존재한다.

상위 레벨에 worker 쓰레드가 존재한다. 여러 타입의 worker 쓰레드가 존재할 수 있다. 기본적으로 events worker thread가 존재한다. 각각의 worker 쓰레드는 cpu_workqueue_struct 구조체로 표현된다. workqueue_struct 구조체는 주어진 타입의 모든 worker 쓰레드를 표현한다.
예를 들어 4-프로세서 컴퓨터 기준으로 falcon 타입의 worker를 만들면 4개의 events worker 쓰레드와 4개의 falcon worker 쓰레드가 존재한다. 총 8개의 cpu_workqueue_struct가 존재(events worker: 4, falcon worker: 4)하고, 2개의 workqueue_struct(events, falcon)이 존재한다.
하위 레벨에서 보면, 드라이버는 work_struct로 표현되는 work를 생성한다. 이 구조체에는 핸들러 함수가 있다. Worker 쓰레드는 깨어나서 미루어진 일을 실행한다.

4.2. Using Work Queues

events 큐를 이용하는것과 새로운 worker 쓰레드를 생성하는 것을 다룬다.
미룰 일은 DECLARE_WORK(정적) 혹은 INIT_WORK(동적, 포인터)를 통해 생성할 수 있고, 핸들러와 데이터 인자를 갖는다. Worker 쓰레드는 핸들러 함수를 프로세스 컨텍스트에서 실행시킨다. 프로세스 컨텍스트에서 실행한다 하더라도 핸들러는 user-space 메모리에 접근할 수 없다. 생성된 일은 기본 events worker 쓰레드에 스케줄할 수 있다

schedule_work(&work);
schedule_delayed_work(&work, delay);

일괄 작업이 계속되기 전 완료되는 것을 보장하거나, 커널에서 race condition을 방지하기 위해 flush가 필요하다.

void flush_scheduled_work(void);
void cancel_delayed_work(struct work_struct *work);

이 함수는 큐의 모든 엔트리가 실행되고 종료될 때 까지 기다린다.
기본 events work queue가 아닌 다른 것을 생성할 수도 있다.

struct workqueue_struct *create_workqueue(const char *name); // name에 workqueue의 이름 넣기(falcon 등)

int queue_work(struct workqueue_struct *wq, struct work_struct *work)
int queue_delayed_work(struct workqueue_struct *wq,
					   struct work_struct *work,
                       unsigned long delay)
flush_workqueue(struct workqueue_struct *wq)

4.3. The Old Task Queue Mechanism

Work queue의 과거에 task queue 인터페이스가 있었다. 리눅스 커널 2.5버전즈음부터 절반의 유저들은 tasklet으로 전환하였고, 남은 유저들은 후에 work queue로 전환하였다.
Task queue는 수많은 큐를 정의한다. 각각의 큐는 이름도 있었고, 커널의 특정 위치에서 실행되었다. 또한 task queue는 동적으로 생성할 수도 있었다. 하지만 모든 큐가 필수적으로 추상화 되어있고 흩뿌려져 있다. 이런 점 때문에 정말정말 간단한 인터페이스이다.

5. Which Bottom Half Should I Use?

리눅스 커널 2.6 버전 기준으로 bottom half는 총 3가지(softirq, tasklet, work queue)가 있다.
Softirq는 적은 직렬화를 제공한다. 이는 핸들러로 하여금 공유 데이터가 안전한지 확인하기 위해 추가적인 절차를 요구한다(동시에 실행이 가능하기 때문). 따라서 이미 충분히 threaded된 상태라면 softirq를 사용하는 것이 좋으며, 이 외에도 timing-critical하고 자주 사용되는 경우에도 사용하기 좋다.
Tasklet은 반대로 코드가 적당히 threaded하지 않은 경우 쓰기 좋다. 동시에 실행 불가능 하기 때문에 더 쉽고 간단히 구현할 수 있다.
만약 프로세스 컨텍스트에서 실행되어야 하는 일이라면 work queue를 이용하면 된다. Work queue는 커널쓰레드를 포함해 context switch가 발생하기 때문에 오버헤드가 크다.

6. Locking Between the Bottom Halves

Tasklet은 동시에 실행할 수 없기 때문에 locking과 관련해서 고민할 필요가 없다. 반면 softirq는 직렬화를 제공하지 않기 때문에 모든 공유 데이터는 적절한 lock이 필요하다. 프로세스 컨텍스트와 bottom half가 데이터를 공유한다면 인터럽트를 비활성화 시키고 데이터 접근전 lock을 획득해야한다. Work queue의 공유 데이터도 locking이 필요하다.

7. Disabling Bottom Halves

보통 공유 데이터를 보호하기 위해 lock을 획득하고 bottom half를 비활성화 한다.

void local_bh_disable() // local 프로세서에서 softirq와 tasklet 처리를 비활성화
void local_bh_enable() // local 프로세서에서 softirq와 tasklet 처리를 활성화

위의 함수는 중첩될 수 있다.

---

References

• Linux Kernel Development (3rd Edition) by Robert Love