Circular Buffers

Circular Buffers 개요

저자는 David Howells <dhowells@redhat.com>와 Paul E. McKenney <paulmck@linux.ibm.com>입니다.

Linux는 circular buffering을 구현하는 데 사용할 수 있는 기능을 두 묶음으로 제공합니다.

• 크기가 power-of-2인 buffer의 상태 정보를 계산하는 convenience function
• Buffer의 object를 생산하는 producer와 소비하는 consumer가 lock을 공유하지 않으려 할 때 사용하는 memory barriers

아래의 기능은 producer가 정확히 하나이고 consumer도 정확히 하나일 때 사용할 수 있습니다. Producer가 여러 개라면 producer끼리 serialize하고, consumer가 여러 개라면 consumer끼리 serialize하여 처리할 수 있습니다.

문서는 다음 내용을 다룹니다.

• Circular buffer의 정의
• Power-of-2 buffer의 측정
• Circular buffer와 memory barrier의 사용: producer와 consumer

Circular buffer란 무엇인가

Circular buffer는 크기가 고정되고 유한하며 다음 두 index를 갖는 buffer입니다.

• `head` index: producer가 item을 buffer에 삽입하는 위치
• `tail` index: consumer가 다음 item을 찾는 위치

일반적으로 tail pointer와 head pointer가 같으면 buffer가 비어 있습니다. Head pointer가 tail pointer보다 하나 앞, 즉 circular 공간에서 tail 바로 전 위치에 있으면 buffer가 가득 찬 상태입니다.

Item을 추가할 때 head index를 증가시키고 제거할 때 tail index를 증가시킵니다. Tail은 head를 넘어서는 안 되며, 두 index 모두 buffer 끝에 도달하면 0으로 wrap해야 합니다. 이렇게 하면 유한한 buffer를 통해 양에 제한 없이 data를 흘려보낼 수 있습니다.

보통 모든 item의 unit size가 같지만 아래 기법을 쓰기 위한 필수 조건은 아닙니다. 여러 item이나 가변 크기 item을 넣으려면 어느 index도 다른 index를 추월하지 않는 범위에서 index를 1보다 크게 증가시킬 수 있습니다.

다만 크기가 한 unit보다 큰 영역은 buffer 끝에서 wrap되어 두 segment로 나뉠 수 있으므로 구현자가 주의해야 합니다.

Power-of-2 buffer 측정

임의 크기의 circular buffer에서 occupancy나 남은 capacity를 계산하려면 보통 느린 modulus, 즉 divide instruction이 필요합니다. Buffer 크기가 power-of-2이면 훨씬 빠른 bitwise-AND instruction으로 대신할 수 있습니다.

Linux의 power-of-2 circular buffer macro를 사용하려면 다음 header를 include합니다.

#include <linux/circ_buf.h>

CIRC_SPACE 및 CIRC_CNT macro

제공되는 macro는 다음과 같습니다.

CIRC_SPACE(head_index, tail_index, buffer_size);

CIRC_SPACE_TO_END(head_index, tail_index, buffer_size);

CIRC_CNT(head_index, tail_index, buffer_size);

CIRC_CNT_TO_END(head_index, tail_index, buffer_size);

Producer, consumer, 제3자 관점의 값

각 macro는 명목상 0부터 `buffer_size-1` 사이의 값을 반환하지만, 관찰 주체에 따라 의미가 달라집니다.

• `CIRC_SPACE*()`는 producer용입니다. Producer는 head index를 제어하지만 다른 CPU의 consumer가 buffer를 비우며 tail을 옮길 수 있으므로 producer에게는 lower bound를 반환합니다. Consumer가 보면 producer가 공간을 소모하고 있을 수 있으므로 upper bound입니다.
• `CIRC_CNT*()`는 consumer용입니다. Consumer는 tail index를 제어하지만 다른 CPU의 producer가 buffer를 채우며 head를 옮길 수 있으므로 consumer에게는 lower bound를 반환합니다. Producer가 보면 consumer가 buffer를 비우고 있을 수 있으므로 upper bound입니다.
• 제3자는 서로 독립적이며 다른 CPU에서 수행될 수 있는 producer와 consumer의 index write가 어떤 순서로 보일지 보장받지 못합니다. 따라서 제3자가 얻는 결과는 추정치에 불과하고 음수가 될 수도 있습니다.

Circular buffer와 memory barrier

Circular buffer에 memory barrier를 함께 사용하면 다음 작업을 피할 수 있습니다.

• Buffer 양쪽 끝의 접근을 하나의 lock으로 통제하는 것. 이를 피하면 buffer를 채우는 작업과 비우는 작업을 동시에 수행할 수 있습니다.
• Atomic counter operation을 사용하는 것

Buffer를 채우는 producer와 비우는 consumer라는 두 측면이 있습니다. 어느 시점이든 producer는 하나, consumer도 하나여야 하지만 양쪽은 동시에 동작할 수 있습니다.

Producer algorithm

Producer는 대략 다음과 같이 동작합니다.

spin_lock(&producer_lock);

unsigned long head = buffer->head;
/* The spin_unlock() and next spin_lock() provide needed ordering. */
unsigned long tail = READ_ONCE(buffer->tail);

if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
        /* insert one item into the buffer */
        struct item *item = buffer[head];

        produce_item(item);

        smp_store_release(buffer->head,
                          (head + 1) & (buffer->size - 1));

        /* wake_up() will make sure that the head is committed before
         * waking anyone up */
        wake_up(consumer);
}

spin_unlock(&producer_lock);

`smp_store_release()`는 새 item의 내용이 consumer에게 공개하는 head index보다 먼저 write되도록 CPU에 지시합니다. 이어 `wake_up()`은 변경된 head index가 consumer를 깨우기 전에 commit되도록 합니다.

단, `wake_up()`은 실제로 무언가를 깨우지 않는 한 어떤 barrier도 보장하지 않으므로 ordering을 이것에 의존할 수 없습니다.

Array에는 항상 element 하나를 비워 둡니다. 따라서 producer가 consumer가 읽는 중인 element를 손상하려면 최소 두 element를 생산해야 합니다. 연속된 consumer 호출 사이의 unlock-lock pair가 consumer가 특정 element를 비웠음을 나타내는 index read와 producer가 같은 element에 수행하는 write 사이에 필요한 ordering을 제공합니다.

Consumer algorithm

Consumer는 대략 다음과 같이 동작합니다.

spin_lock(&consumer_lock);

/* Read index before reading contents at that index. */
unsigned long head = smp_load_acquire(buffer->head);
unsigned long tail = buffer->tail;

if (CIRC_CNT(head, tail, buffer->size) >= 1) {

        /* extract one item from the buffer */
        struct item *item = buffer[tail];

        consume_item(item);

        /* Finish reading descriptor before incrementing tail. */
        smp_store_release(buffer->tail,
                          (tail + 1) & (buffer->size - 1));
}

spin_unlock(&consumer_lock);

`smp_load_acquire()`는 새 item을 읽기 전에 head index가 최신인지 확인하게 합니다. 이어 `smp_store_release()`는 item을 지우는 새 tail pointer를 쓰기 전에 CPU가 item 읽기를 끝내도록 보장합니다.

상대편 index를 읽을 때 producer는 `READ_ONCE()`, consumer는 `smp_load_acquire()`를 사용합니다. 이는 compiler가 cache한 값을 버리고 다시 load하는 일을 막습니다. 상대편 index를 정확히 한 번만 사용한다고 확신할 수 있다면 이 조치는 엄밀히는 필요하지 않습니다.

`smp_load_acquire()`는 추가로 이후 memory reference와의 CPU ordering을 강제합니다. 두 algorithm 모두 자기 thread의 index를 쓸 때 `smp_store_release()`를 사용합니다.

이 표기는 동시에 읽힐 수 있는 대상에 write한다는 사실을 문서화하고, compiler가 store를 찢어서 수행하지 못하게 하며, 이전 access에 대한 ordering을 강제합니다.

Further reading

Linux memory barrier 기능에 대한 설명은 `Documentation/memory-barriers.txt`도 참고하십시오.