로그 버퍼 관련 패치

1. Lockless algorithm으로 변경 (2020/7)
- https://github.com/torvalds/linux/commit/896fbe20b4e2333fb55cc9b9b783ebcc49eee7c7

2. Safe buffer 및 NMI buffer 제거 (2021/7)
- https://github.com/torvalds/linux/commit/93d102f094be9beab28e5afb656c188b16a3793b

3. Finalization/extention support  추가 (2020/9)
https://github.com/torvalds/linux/commit/4cfc7258f876a7feba673ac6d050f525b39cc84c

로그 버퍼 내용
- 로그 버퍼는 링버퍼로 구성되어 있으며 최근 lockless algorithm으로 변경되었다 (2020/7)
- 링버퍼는 descriptor ring buffer와 data ring buffer로 구성됨
- Descriptor ring buffer는 info 배열과 desc 배열로 구성
- info 배열과 desc 배열은 엔트리 수가 같으며 같은 인덱스의 엔트리는 하나의 descriptor를 구성한다
- Data ring buffer는 data 바이트 배열로 구성되어 있으며 디폴트 기준 128KB 크기
- Descriptor ring buffer 엔트리 수는 data 바이트 배열 크기 / 평균 descriptor 당 바이트 수로 정해진다
- 평균 descriptor 당 바이트 수는 config로 정해지며 디폴트 기준 32B이다
- 따라서 디폴트 기준 Descriptor ring buffer 엔트리 수는 128KB/32B = 4K 개이다
- data 바이트 배열은 단순 바이트 배열이나 사용할 때는 data block 구조체로 단위로 캐스팅되어 사용된다
- data 바이트 배열은 data ring buffer의 정보만으로는 어느 부분이 엔트리 시작/끝 지점인지 알 수 없고 descriptor를 봐야 알 수 있다
- Desc 배열 엔트리에 logical position (lpos) begin, lpos end 값이 주어져서 해당 descriptor가 데이터 바이트 배열의 어느 지점을 가리키는지 나타낸다. lpos begin, lpos end는 바이트 배열의 엔트리의 시작지점과 다음 엔트리의 시작 지점을 나타낸다
- 반대로 data block 구조체는 앞의 8B가 id 값이며 그 다음에 바이트 배열이 있다. ID는 이 data block에 해당되는 descriptor의 인덱스를 나타낸다
- Descriptor ring buffer는 링버퍼이므로 마지막 인덱스 다음에는 첫 인덱스로 돌아온다
- Data ring buffer 역시 마찬가지이나, data 바이트 배열은 하나의 data block 단위가 항상 연속으로 쓰여져야 한다. 중간에 data block이 잘리면 안되므로, 마지막 엔트리 다음의 새 data block이 잘리는 경우, 바이트 배열의 첫 부분에 새 data block이 생성된다. 마지막 엔트리 다음에는 새 data block의 id만 기록한다
- 각 데이터 및 descriptor에는 state가 있는데 reserved, committed, finalized, reusable 4가지가 있음
- reserved는 해당 데이터를 writer가 modify하는 중이라는 것을 의미한다
- committed는 해당 데이터를 writer가 쓰기 완료했다는 것을 의미한다. committed 데이터는 sanity check 완료된 상태이며 동일한 writer에 의해 다시 reserved로 돌아갈 수 있다
- finalized는 committed된 데이터가 완전히 쓰기 종료되어 다시 수정될 수 없는 상태이다. finalized되어야 reader가 읽을 수 있다
- reusable은 읽기 불가능하고 새로 쓰는게 가능한 상태이다. finalized 데이터를 reader가 읽으면 reusable이 된다
- 이전 데이터 committed된 상태에서 새 데이터가 reserved되면 committed 데이터는 자동으로 finalized된다
- 이전 데이터, 새 데이터가 모두 reserved일때 이전 데이터가 committed되면 자동으로 finalized된다
- state는 descriptor 엔트리의 state_var에 저장되며, 상위 2비트가 state이고, 하위 62비트는 descriptor 인덱스이다
- state encoding은 reserved 0x0, committed 0x1, finalized 0x2, reusable 0x3이다
- lpos는 항상 8B align이 맞아야 하고, data block size 역시 8B align이 맞아야 한다
- lpos begin/end 모두 lsb가 1이면 dataless block으로 간주된다
- 읽기 쓰기를 위해서는 추가 구조체 printk_record가 필요하다
- printk_record에는 info, text_buf, text_buf_size가 있다
- 쓰기 수행을 위해서는 함수 prb_rec_init_wr()를 불러서 text_buf_size를 정해준 뒤 prb_reserve() 함수로 링버퍼 reserve를 수행하고, text_buf와 info에 데이터와 메타데이터를 copy하여 채워준 후 함수 prb_final_commit()으로 쓰기를 완료한다
- 읽기 수행을 위해서는 함수 prb_rec_init_rd()를 불러서 info, text_buf, text_buf_size를 정하고 prb_read_valid() 함수로 info, text_buf에 값을 링버퍼로 읽어온다
- 즉 쓰기는 printk_record에 있는 정보를 링버퍼에 쓰고, 읽기는 링버퍼에 있는 정보를 printk_record로 가져오는 식이다
- Descriptor ring buffer와 데이터 링버퍼 모두 head, tail이 있고 쓸 때마다 head가 늘어나고 읽을 때마다 tail이 줄어든다
- 만약 써야 하는데 링버퍼가 차있으면 가장 오래된 tail을 없애고 새 head를 만든다

/*
 * The high level structure representing the printk ringbuffer.
 *
 * @fail: Count of failed prb_reserve() calls where not even a data-less
 *        record was created.
 */
struct printk_ringbuffer {
    struct prb_desc_ring    desc_ring;
    struct prb_data_ring    text_data_ring;
    atomic_long_t       fail;
};

/* A ringbuffer of "struct prb_desc" elements. */
struct prb_desc_ring {
    unsigned int        count_bits;
    struct prb_desc     *descs;
    struct printk_info  *infos;
    atomic_long_t       head_id;
    atomic_long_t       tail_id;
};

/* A ringbuffer of "ID + data" elements. */
struct prb_data_ring {
    unsigned int    size_bits;
    char        *data;
    atomic_long_t   head_lpos;
    atomic_long_t   tail_lpos;
};

/*
 * A descriptor: the complete meta-data for a record.
 *
 * @state_var: A bitwise combination of descriptor ID and descriptor state.
 */
struct prb_desc {
    atomic_long_t           state_var;
    struct prb_data_blk_lpos    text_blk_lpos;
};

/* Specifies the logical position and span of a data block. */
struct prb_data_blk_lpos {
    unsigned long   begin;
    unsigned long   next;
};

/*
 * A data block: mapped directly to the beginning of the data block area
 * specified as a logical position within the data ring.
 *
 * @id:   the ID of the associated descriptor
 * @data: the writer data
 *
 * Note that the size of a data block is only known by its associated
 * descriptor.
 */
struct prb_data_block {
    unsigned long   id;  
    char        data[];
};

/*
 * A structure providing the buffers, used by writers and readers.
 *
 * Writers:
 * Using prb_rec_init_wr(), a writer sets @text_buf_size before calling
 * prb_reserve(). On success, prb_reserve() sets @info and @text_buf to
 * buffers reserved for that writer.
 *
 * Readers:
 * Using prb_rec_init_rd(), a reader sets all fields before calling
 * prb_read_valid(). Note that the reader provides the @info and @text_buf,
 * buffers. On success, the struct pointed to by @info will be filled and
 * the char array pointed to by @text_buf will be filled with text data.
 */
struct printk_record {
    struct printk_info  *info;
    char            *text_buf;
    unsigned int        text_buf_size;
};

setup_log_buf()
- local_irq_save() 부터 진행

- local_irq_save()로 인터럽트를 막는다
- 매크로 prb_for_each_record()를 돌면서 static 링버퍼로부터 엔트리를 하나씩 읽어와서 함수 add_to_rb()를 이용하여 dynamic 링버퍼에 추가한다
- 이 때 static 링버퍼에서 dynamic으로 옮겨진 데이터 양을 기록한다
- Dynamic 링버퍼로 링버퍼를 변경한다
- local_irq_restore()로 인터럽트를 다시 켠다
- 다시 prb_for_each_record()를 돌면서 static 링버퍼에 남아있는 엔트리를 함수 add_to_rb()를 이용하여 dynamic 링버퍼에 추가한다 (1140 번째 줄에서 추가된 로그들)
- static 링버퍼의 seq값이 현재 seq와 다르면 버려진 엔트리가 발견된 것으로 이 경우 로그에 출력한다. 현재는 이런 경우가 있을 수 없다
- 새 로그 버퍼 크기를 출력한다
- early 로그에서 사용하지 않고 남은 양을 출력한다
- 종료

prb_for_each_record() 매크로
- 초기값 seq로부터 seq를 1씩 증가시키면서 함수 prb_read_valid()를 수행하여 r에 seq에 해당하는 링버퍼 데이터값을 읽어온다

prb_read_valid()
- 함수 _prb_read_valid()를 호출

_prb_read_valid()
- 인자로 링버퍼, seq값을 받아서 seq에 해당하는 링버퍼 데이터를 읽어서 r에 저장하고 line count도 넘겨준다
- 함수 prb_read()를 이용해서 데이터를 읽어온다
- 함수 prb_read()를 읽다가 에러가 발생하면 함수 prb_first_seq()로 tail의 seq를 읽는다
- tail seq가 요청된 seq보다 크면 seq를 tail seq로 바꿔서 다시 읽는다
- 에러가 ENOENT이면 seq를 1 증가시켜서 다시 읽는다 (dataless block)
- 그 외의 에러면 false 리턴한다

prb_read()
- 인자로 링버퍼, seq, printk_record r을 받아서 seq에 해당하는 데이터와 info를 읽어서 r에 전달한다
- 요청이 있는 경우 line count도 같이 전달한다

- seq에 해당하는 info, descriptor를 가져오고 descriptor의 state_var도 읽어온다
- state_var로부터 id값을 읽어온다
- id와 seq로부터 함수 desc_read_finalized_seq()를 이용, descriptor copy본을 읽어온다
- descriptor copy읽어오는 데 에러가 발생하거나, r이 NULL이면 그냥 리턴한다 (caller가 데이터를 원하지 않고 descriptor의 유효함만 관심있는 경우)
- r에 info가 요청되면 r->info에 info를 복사한다
- 함수 copy_data()로 r에 descriptor에 해당하는 데이터블록을 r에 읽어온다
- 함수 desc_read_finalized_seq() 다시 descriptor를 체크하고 리턴한다

desc_read_finalized_seq()
- 인자로 descriptor 링버퍼, id, seq를 받아서 id, seq에 해당하는 descriptor entry를 리턴한다
- 함수 desc_read()로 id에 해당하는 descriptor를 읽어온다
- state가 desc_miss, reserved, committed이면 EINVAL 에러 리턴
- state가 reusable이거나 descriptor의 blk_lpos가 FAILDED_LPOS이면 ENOENT 에러 리턴
- 0과 함께 descriptor를 리턴한다

copy_data()
- 인자로 데이터 링버퍼, blk_lpos, len을 받아서 blk_lpos 위치의 데이터를 링버퍼로부터 len만큼 읽어서 리턴한다
- 읽은 데이터는 buf로 리턴하고 요청이 있으면 line count도 리턴한다

- buf가 NULL이거나 buf_size가 0이고 line count 요청도 없으면 그냥 true 리턴 (데이터를 caller가 원하지 않음)
- 함수 get_data()로 데이터 링버퍼로부터 blk_lpos 위치의 데이터를 읽어온다. 읽어온 데이터의 사이즈도 가져온다
- 읽어온 데이터 사이즈가 0이면 false 리턴
- 읽어온 데이터 사이즈가 요청된 len보다 작으면 false 리턴
- line count 요청이 있으면 함수 count_lines()로 line count를 계산해서 넘겨준다
- memcpy로 인자로 받은 buf에 읽어온 데이터를 len만큼 copy한다
- true를 리턴한다

get_data()
- 인자로 데이터 링버퍼, blk_lpos를 받아서 blk_lpos 위치의 데이터를 리턴하고 읽어온 데이터의 사이즈도 리턴한다
- blk_lpos 위치가 dataless이면 “” 또는 NULL을 리턴한다
- 데이터블록이 같은 wrap에 있으면 함수 to_block()로 blk_lpos->begin 위치의 데이터 블록을 읽어오고, 데이터 사이즈는 blk_lpos->next - blk_lpos->begin으로 계산하고 리턴한다
- 데이터블록이 다른 wrap에 있으면 함수 to_block()로 데이터 링버퍼의 0번째 위치의 데이터 블록을 읽어오고 0부터 blk_lpos->next까지의 데이터 사이즈를 계산해서 리턴한다
- wrap이 2 이상 차이나면 NULL 리턴
- blk_lpos가 8B align이 안맞으면 NULL 리턴
- 계산된 데이터 사이즈가 8B보다 작으면 NULL 리턴
- 데이터 사이즈는 id 크기인 8B를 빼고 리턴한다
- 데이터블록은 id 영역이 아닌 실제 데이터 시작 주소로 리턴한다

count_lines()
- 인자로 text와 text_size를 받아서 ‘\n’ 개수를 읽어서 라인수를 계산해서 리턴한다

add_to_rb()
- 인자로 링버퍼와 printk_record r을 받아서 r에 있는 entry를 링버퍼에 추가한다

- 함수 prb_rec_init_wr()로 쓰기에 사용할 printk_record dest_r을 초기화한다. 쓰기 사이즈는 r에서 가져온다
- 함수 prb_reserve()로 링버퍼의 데이터블록을 reserve하고 dest_r이 링버퍼의 데이터 블록과 info를 가리키게 한다
- dest_r의 text_buf, info를 r의 text_buf, info의 값으로 채워서 쓰기 작업을 수행한다
- 함수 prb_final_commit()로 commit & finalize 한다
- 쓰기를 수행한 총 데이터블록의 사이즈를 리턴한다

prb_reserve()
- 인자로 prb_reserved_entry 구조체 e, printk_ringbuffer 구조체 rb, printk_record r을 받는다
- 링버퍼의 head를 하나 늘리고 그 head에 해당되는 datablock 주소와 info 주소를 printk_record r에 넘겨준다
- 또한 prb_reserved_entry 구조체 e에는 printk_ringbuffer 구조체 rb와 head id를 달아준다

- 함수 data_check_size()로 인자 r로 요청된 버퍼 사이즈를 링버퍼가 만족시킬 수 있는지 체크한다
- 함수 local_irq_save()로 인터럽트를 끈다
- 함수 desc_reserve()로 desctiptor 링버퍼 엔트리 1개를 reserve하고 그 id를 얻는다
- id에 해당하는 descriptor와 info를 구한다
- info의 seq값을 가져오고 info를 memset하여 지운다
- 인자로 받아온 prb_reserved_entry 구조체 e에 링버퍼와 reserve한 descriptor id값을 달아준다
- info의 seq에 한 바퀴에 해당하는 wrap 값을 더해준다. 만약 처음 seq인 경우엔 매크로 DESC_INDEX()로 초기화해준다
- info의 seq가 0이 아니면 이전 데이터가 있는 경우이다. 따라서 이전 데이터가 committed인 경우엔 함수 desc_make_final()로 finalize시켜준다
- 함수 data_alloc()으로 reserve한 descriptor의 id와 데이터 요청 사이즈로 데이터 링버퍼로부터 데이터 블록을 할당받아 인자 printk_record r에 넘겨준다
- 만약 할당이 실패하면 함수 prb_commit()로 data-less 블록을 commit하고 인자 printk_record r를 memset으로 0으로 만든 뒤 false 리턴한다
- 인자 printk_record r에 info를 달아준다
- 인자 prb_reserved_entry e의 text_space에 새로 할당된 데이터블록 크기를 적어준다 (함수 space_used())
- true 리턴한다

data_check_size()
- 인자로 데이터 링버퍼와 요청 사이즈를 받아서 데이터 링버퍼가 요청된 사이즈를 받아서 쓰기를 할 수 있는지 체크한다
- 함수 to_blk_size()로 요청된 사이즈에 id값을 위한 8B를 더한 후 8B align을 맞춘 값을 구한다
- 데이터 링버퍼 사이즈에 8B를 뺸 값이 새로 구한 값보다 작으면 false, 아니면 true를 리턴한다

desc_reserve()
- 인자로 링버퍼를 받아서 새로 descriptor head를 하나 만들고 새 descriptor head id를 리턴한다

- descriptor 링버퍼의 head id를 읽어온다
- head id + 1에 해당하는 id와 이전 wrap의 head id + 1에 해당하는 id_prev_wrap을 가져온다
- descriptor 링버퍼의 tail id가 id_prev_wrap과 같으면 링버퍼가 가득 차있는 것이므로 함수 desc_push_tail()로 데이터를 한 칸 제거하여 공간을 확보한다
- atomic exchange로 descriptor 링버퍼의 head id를 1 증가시킨다
- 증가된 새 head id에 해당하는 descriptor를 가져온다
- 새 descriptor의 state가 reusable임을 확인한다. 이 때 id값이 id_prev_wrap인 것도 확인한다
- atomic exchange로 새 descriptor의 state를 reserved로 변경하고, id도 새 head id로 변경시킨다
- 변경된 새 head id를 리턴한다

desc_push_tail()
- 인자로 링버퍼와 tail id를 받아서 tail을 한 칸 advance 시킨다 (기존 tail 아이템은 제거)

- 함수 desc_read()로 tail id에 해당하는 descriptor를 읽어온다
- 해당 descriptor의 state를 보고 reserved나 committed면 false 리턴, desc_miss이면 tail id가 정확히 1 wrap 이전이면 아직 reserved인 것이므로 false, 아니면 이미 누군가가 desc_push 한 것으면 이미 누군가가 push한 것이므로 true 리턴한다
- 함수 data_push_tail()로 tail 아이템까지 데이터를 invalidate 시킨다
- 함수 desc_read()로 tail id + 1에 해당하는 descriptor를 읽어온다
- descriptor가 finalized이거나 reusable이면 atomic exchange로 현재 descriptor 링버퍼의 tail id를 1 증가시킨다
- 만약 아니면 descriptor의 링버퍼 tail id가 변경되었는지 살펴본다. 변경되었으면 이미 누군가가 desc_push_tail()을 한 것이므로 그냥 성공이고 아니면 잘못된 상태이므로 false 리턴을 수행한다

desc_read()
- 인자로 descriptor 링버퍼, id를 받아서 id에 해당하는 descriptor를 읽어서 리턴한다
- 이 때 descriptor의 sequence 값과 caller id값도 요청에 따라 리턴한다

data_push_tail()
- 인자로 링버퍼와 lpos를 받아서 lpos 위치 전까지 데이터 링버퍼의 tail을 밀어준다. 중간의 데이터는 소실된다
- 함수 data_make_reusable()로 while 루프를 돌리면서 tail을 밀어주게 되어있다

data_make_reusable()
- 인자로 링버퍼와 lpos begin, end를 받아서 lpos begin의 data block부터 lpos end 이전까지 모든 data block을 reusable로 바꾸어 준다
- 출력으로 reusable이 된 블록의 다음 주소 lpos값을 반환한다
- 만약 data block 중 flag가 desc_miss, reserved, committed가 있으면 동작 실패, finalized이면 함수 desc_make_reusable()로 reusable로 바꾼다
- Finalized 및 reusable block에 대해서는 lpos begin sanity check를 수행한다

desc_make_reusable()
- 인자로 descriptor ring과 id를 받아서 atomic compare & exchange 함수를 이용, id에 해당하는 descriptor의 state_var이 finalized이면 reusable로 바꿔준다

to_block()
- 데이터 링버퍼와 begin lpos를 받아서 begin lpos에 해당하는 데이터 블록 위치를 리턴한다

desc_make_final()
- 인자로 descriptor 링버퍼와 id를 받아서 id에 해당하는 descriptor가 committed인 경우 finalized로 state를 바꿔준다

data_alloc()
- 인자로 링버퍼, 요청 사이즈와 descriptor id를 받아서 데이터 링버퍼에 사이즈를 만족하는 데이터 블록을 만들고 descriptor id를 등록한 뒤 데이터 블록의 위치를 blk_lpos로 리턴하고 데이터 블록의 시작점도 리턴한다

- 요청 사이즈가 0이면 리턴하는 blk_lpos를 NO_LPOS(0x3)으로 만들고 NULL을 리턴한다
- 요청 사이즈를 함수 to_blk_size()로 링버퍼에 유효한 크기로 변환한다
- 데이터 링버퍼의 head lpos를 가져온다
- 함수 get_next_lpos()로 요청 크기에 맞는 next_lpos를 계산한다
- 함수 data_push_tail()로 next_lpos 이전의 데이터들을 모두 무효화한다
- 데이터 링버퍼의 head lpos를 next lpos로 업데이트한다
- 새로 할당된 데이터 블록을 가져온다
- 새로운 데이터 블록의 id에 descriptor id를 기록한다
- 만약 wrap이 넘어가는 경우이면 blk 위치를 데이터 링버퍼의 0번째 위치로 조정하고 0번째 위치에도 descriptor id를 기록한다
- 리턴할 blk_lpos를 새로 할당된 데이터 블록의 begin_lpos와 next_lpos로 업데이트한다
- 새로 할당된 데이터 블록의 시작 주소를 리턴한다

get_next_lpos()
- 인자로 데이터 링버퍼, 시작 lpos, 사이즈를 받아서 데이터 링버퍼에 유효한 next_lpos를 만들어 리턴한다
- 기본적으로 lpos + 사이즈로 계산하되 만약 wrap이 넘어가는 경우에는 0 + 요청된 사이즈를 리턴한다

space_used()
- 인자로 데이터 링버퍼, 데이터 블록의 blk_lpos를 받아서 데이터 블록의 사이즈를 계산해서 리턴한다

prb_commit()
- 인자로 prb_reserved_entry 구조체 e를 받아서 reserved entry를 commit한다

- e가 가리키는 링버퍼의 descriptor 링버퍼를 가져온다
- 함수 _prb_commit()로 e가 나타내는 reserved entry를 commit한다
- descriptor 링버퍼의 head id를 가져와서 e의 id와 비교한다. 만약 다르면 그 사이에 누군가가 새로운 entry를 reserve한 것이므로 commit한 entry를 함수 desc_make_final()로 finalized로 상태를 바꿔준다

_prb_commit()
- 인자로 prb_reserved_entry 구조체 e와 commit할 state값을 받는다 (보통 desc_committed 일 듯)

- e가 가리키는 링버퍼로부터 descriptor 링버퍼를 가져온다
- Descriptor 링버퍼로부터 e->id에 해당하는 descriptor를 가져오고 해당 descriptor의 state_var를 가져온다
- descriptor의 state_var가 reserved일 경우 committed로 업데이트한다
- 함수 local_irq_restore() 인터럽트를 켜고 리턴한다

prb_final_commit()
- 인자로 prb_reserved_entry 구조체 e를 받는다
- 함수 _prb_commit()로 e가 나타내는 entry를 finalized상태로 바꿔준다

이후엔 lock-free 개념 스터디 진행

- https://lwn.net/Articles/827180/
- https://lwn.net/Articles/844224/
- https://lwn.net/Articles/847973/
- https://developer.arm.com/documentation/den0024/a/Memory-Ordering/Barriers/One-way-barriers
- https://en.wikipedia.org/wiki/Non-blocking_algorithm#Obstruction-freedom
- https://en.wikipedia.org/wiki/ABA_problem
- https://preshing.com/20120612/an-introduction-to-lock-free-programming/
- https://www.singlestore.com/blog/common-pitfalls-in-writing-lock-free-algorithms/
- https://www.baeldung.com/lock-free-programming
- https://en.wikipedia.org/wiki/Memory_ordering