About ring(circular) buffer, double-linked list, reverse mapping table

 

---

 

 

  Ring Buffer를 구현하기 위해서는 Queue에 대해서 간략하게 알자면 Queue는 FIFO (First In First OUT) 구조로 먼저 들어온 데이터가 먼저 나가는 데이터 구조이다.

 

  Ring Buffer란 고정 크기의 Queue를 처음과 끝을 가상적으로 이어붙여서 연결된 구조를 말한다. 그리고 buffer에 읽고 쓸 위치를 알기 위해 head와 tail pointer가 있다.

 

 

Ring Buffer

 

 

  Ring Buffer를 구현하기 위해선 기본적으로 있어야 하는 API는

    - isEmpty() : buffer가 비었는지 확인한다. head == tail이면 비어있는 상태 

    - enQueue() : data를 buffer에 입력한다. 그리고 head pointer를 하나 증가시킴

    - deQueue() : buffer로부터 data를 출력한다. 그리고 tail pointer를 하나 증가

    - isAvailable() : buffer에 data가 몇개 있는지 확인, 없으면 0 return

 

 

---

 

 

  Linux system 분석중 QTAILQ_ENTRY에 대한 궁금증을 풀다가 메모한다. block size의 64배인 line data structure가 있다.

typedef struct line {
    int id;
    int ipc;
    int vpc;
    QTAILQ_ENTRY(line) entry;
    size_t pos;
} line;

 

  QTAILQ_ENTRY 는 double-linked list의 node로 사용될 line data structure 내에 필요한 pointer들을 생성한다. (double-linked list에서 각 node들은 앞뒤 node와 연결을 위한 prev와 front pointer 생성.)

  그리고 이 메크로를 통해서, line data structure를 queue의 요소로 쉽게 관리할 수 있다. 예를 들어, 요소를 queue의 끝에 추가하거나, 특정 위치의 요소를 찾거나, 요소를 큐에서 제거하는 등의 작업을 할 수 있다.

  종합하면 QTAILQ_ENTRY(line) entry 는 double-linked list를 위한 pointer를 포함하는 필드이다. 이 필드를 통해 line data structure는 (free, victim, full) 같은 리스트들에 쉽게 포함될 수 있다.

 

 

---

 

 

  이번에도 linux system에서 femu code를 분석하던중에 나왔던 rmap (reverse map)에 대해 설명해보겠다. rmap은 주로 NAND-based flash memory에서 PPA와 LPN사이의 관계를 추적하는 데 사용된다.

static void ssd_init_rmap(struct ssd *ssd){
    struct ssdparam *spp = &ssd->sp;
    
    ssd->rmap = g_malloc0(sizeof(uint64_t) * spp->tt_pgs);
    for (int i = 0; i < spp->tt_pgs; i++) {
    	ssd->rmap[i] = INVALID_LPN;
    }
}

 

  코드 설명을 잠깐하면 g_malloc0 로 rmap array에 사용할 memory를 할당한 후에 모든 비트를 0으로 초기화한다. 그리고 loop 를 통해서 rmap의 모든 배열의 요소를 INVALID_LPN 으로 설정한다.

 

  

---

 

 

// xx.h header file

#define BLK_BITS	(16)
#define PG_BITS 	(16)
#define SEC_BITS	(8)
#define PL_BITS		(8)
#define LUN_BITS	(8)
#define CH_BITS		(7)

struct ppa {
    union {
    	struct {
            uint64_t blk : BLK_BITS;
            uint64_t pg : PG_BITS;
            uint64_t sec : SEC_BITS;
            uint64_t pl : PL_BITS;
            uint64_t lun : LUN_BITS;
            uint64_t ch : CH_BITS;
            uint64_t rsv : 1
        } g;
        
        uint64_t ppa;
    };
};


// xx.c source file

return_type func_name (type param) {
    spp->secsz = 512;
    spp->secs_per_pg = 8;
    spp->pgs_per_blk = 256;
    spp->blks_per_pl = 256; /* 16GB */
    spp->pls_per_lun = 1;
    spp->luns_per_ch = 8;
    spp->nchs = 8;
    
    ...
}

 

 

    여기서 source file에 적힌 코드는 SSD의 parameter (SSD 구성의 측면)를 설정을 위한 것이고, 다른 하나는 Physical Page Address를 표현하기 위한 것이다. 여기서 각 비트 필드는 주소의 각 부분을 나타낸다. 이 사이의 연결을 이해해야할 필요가 있다.

    예를 들면, PG_BITS 가 16비트라는 것은 addressable한 page의 수를 나타낸다. 16 bits를 사용해서 주소를 지정하면 최대 2^16 개의 서로 다른 page를 구분할 수 있다. page의 실제 크기는 secsz * secs_per_pg 로 2*12bytes (4KB) 가 된다.

    즉, 전체 총 저장 공간은 64KB * 4KB = 256MB이다.

    

 

 

 

 

 

 

 

 

Reference

 

1. https://embeddedartistry.com/blog/2017/05/17/creating-a-circular-buffer-in-c-and-c/

2. http://lastweek.io/notes/rmap/

3. https://eteo.tistory.com/359