[컴퓨터 구조] Data Alignment

글의 참고

- http://www.songho.ca/misc/alignment/dataalign.html

- https://en.wikipedia.org/wiki/Data_structure_alignment

- https://fylux.github.io/2017/07/11/Memory_Alignment/

- http://books.gigatux.nl/mirror/kerneldevelopment/0672327201/ch19lev1sec3.html

---

글의 전제

- 내가 글을 쓰다가 궁금한 점은 파란색 볼드체로 표현했다. 나도 모르기 때문에 나중에 알아봐야 할 내용이라는 뜻이다.

- 밑줄로 작성된 글은 좀 더 긴 설명이 필요해서 친 것이다. 그러므로, 밑 줄 처친 글이 이해가 안간다면 링크를 따라서 관련 내용을 공부하자.

---

글의 내용

- Data alignment

" 우리 말로 데이터 정렬은 컴퓨터 분야에서 중의적인 표현인 느낌이 강하다. 대부분은 `Data Sorting`으로 해석되는 경우가 있는데, 이건 알고리즘적인 부분을 의미하는 것이다. 이 포스팅에서 말하고자 하는 데이터 정렬 `Data Alignment`를 의미하고 대게 Computer Architecture에서 주로 다뤄지는 내용이다.

 

 

" `Data structure alignment`는 computer memory에 존재하는 데이터를 정렬하고 접근하는 방법이다. 데이터 정렬은 크게 3가지 형태를 고려해 볼 수 있다.

1. data alignment
2. data structure padding
3. packing

 

 

" 현대의 CPU들은 메모리의 데이터들이 정렬되어 있을 때, read/write 속도가 가장 빠르고 효율적이다. 데이터가 자연스러운 정렬(`naturally aligned`) 을 이룬다는 것은 데이터의 주소가 데이터 크기의 배수여야 함을 의미한다.

The CPU in modern computer hardware performs reads and writes to memory most efficiently when the data is `naturally aligned`, which generally means that the data's memory address is a multiple of the data size. For instance, in a 32-bit architecture, the data may be aligned if the data is stored in four consecutive bytes and the first byte lies on a 4-byte boundary.

Data alignment is the aligning of elements according to their `natural alignment`. To ensure natural alignment, it may be necessary to insert some padding between structure elements or after the last element of a structure. For example, on a 32-bit machine, a data structure containing a 16-bit value followed by a 32-bit value could have 16 bits of padding between the 16-bit value and the 32-bit value to align the 32-bit value on a 32-bit boundary. Alternatively, one can pack the structure, omitting the padding, which may lead to slower access, but uses three quarters as much memory.

- 참고 : https://en.wikipedia.org/wiki/Data_structure_alignment

 

 

" 예를 들어, 32-bit 아키텍처에서 데이터가 연속된 4개의 바이트에 저장되어있고, 첫 번째 데이터의 주소가 4바이트의 경계라면 해당 데이터를 정렬되어 있다고 본다(참고로, 4바이트로 정렬되면 하위 2비트는 반드시 `0`이 된다). 데이터 정렬에서 `데이터 주소 정렬`과 `데이터 액세스 정렬`이 존재한다.

1. memory address 가 aligned 되어있다 -  데이터 주소가 정렬되어 있다고 말하려면, 데이터의 시작 주소가 데이터 크기의 배수여야 한다. 예를 들어, 접근하려는 데이터가 4바이트이면 해당 데이터의 시작 주소는 4의 배수(4, 8, 12, ... , 4x) 여야 한다. 이 때, 사이즈는 상관없다.

2. memory access 가 aligned 되어있다 - 데이터 액세스가 `정렬되어 있다`라고 말하려면, n 의 배수 크기로 액세스(READ/WRITE) 해야 하고, 데이터 주소도 n의 배수여야 한다. 예를 들어, 주소 `0x2321_F000` 에서 8192B(4KB*2)를 읽는 access 가 있다면, 이 데이터 액세스는 4KB or 8KB 에 정렬되어 있다고 말 할 수 있다. 

 

 

" 아래에 왼쪽 그림에서 하늘색 데이터 영역은 4바이트로 정렬되어 있다고 볼 수 있다. 물론, 아래 노란색과 붉은색의 경계 부분이 4의 배수여야 함도 주의해야 한다.

 

 

 

" 위에서 왼쪽 그림은 메모리 상위 4 바이트에 접근하고 있다. 그런데, 시작 주소가 4바이트에 정렬이 되어 있다. 오른쪽 그림도 4 바이트 데이터에 접근하고 있다. 그런데, 시작 주소가 4 바이트에 정렬되어 있지 않다. 그래서 CPU는 아래의 추가 사이클을 진행한다.

 

 

 

" 위 그림에서도 보다시피, 하나의 워드에서 가장 높은 바이트와 가장 낮은 바이트가 같은 메모리내에 있지 않으면, 프로세서는 메모리를 2개로 쪼갠다. 그리고, 이걸 합치는 과정을 통해서 우리가 원하는 데이터가 조합이 되는데, 이 과정은 상당히 복잡한 과정을 거치게 된다. 즉, 프로세서의 오버헤드가 증가하게 된다.

If the highest and lowest bytes in a datum are not within the same memory word the computer must split the datum access into multiple memory accesses. This requires a lot of complex circuitry to generate the memory accesses and coordinate them. To handle the case where the memory words are in different memory pages the processor must either verify that both pages are present before executing the instruction or be able to handle a TLB miss or a page fault on any memory access during the instruction execution.

- 참고 : https://en.wikipedia.org/wiki/Data_structure_alignment

 

 

" 위와 같은 예시를 코드로 어떻게 구현할까? 일반적으로 대부분의 운영 체제는 변수를 선언할 때, 변수 타입 크기에 맞게 정렬된 주소를 할당한다. 즉, 4 바이트 변수는 4바이트 정렬된 주소를, 2 바이트 변수는 2바이트 정렬된 주소를 할당한다. 이걸 `naturally aligned` 라고 한다. 아래에서 변수 `temp`는 `unsigned char` 타입이기 때문에 바이트 단위 주소가 temp에 할당된다.

 

" 그리고 이 `temp` 변수의 주소를 p 포인터가 참조하게 된다. 그런데, 3번째 줄에서 `*(unsigned int*)p`는 문제가 있다. 만약, `temp` 변수의 주소가 0x130F13이라면, 이 값은 4(unsigned int)로 나누어 떨어지지 않는다. 즉, `mis-aligned`가 발생한 것이다.

unsigned char temp[7];
unsigned char *p = &temp;
unsigned int mis_aligned = *(unsigned int*)p;

 

 

" 결국 우리가 데이터 정렬을 하지 않으면, 위와 같은 상황이 발생하는 것이다. 구조체의 경우에는 반드시 멤버 변수 중 가장 크기가 큰 멤버 변수로 패딩이 된다.

// size = 2 bytes, alignment = 1-byte, address can be divisible by 1
struct S1 {
    char m1;    // 1-byte
    char m2;    // 1-byte
};

// size = 4 bytes, alignment = 2-byte, address can be divisible by 2
struct S2 {
    char m1;    // 1-byte
                // padding 1-byte space here
    short m2;   // 2-byte
};

// size = 8 bytes, alignment = 4-byte, address can be divisible by 4
struct S3 {
    char m1;    // 1-byte
                // padding 3-byte space here
    int m2;     // 4-byte
};

// size = 16 bytes, alignment = 8-byte, address can be divisible by 8
struct S4 {
    char m1;    // 1-byte
                // padding 7-byte space here
    double m2;  // 8-byte
};

// size = 16 bytes, alignment = 8-byte, address can be divisible by 8
struct S5 {
    char m1;    // 1-byte
                // padding 3-byte space here
    int m2;     // 4-byte
    double m2;  // 8-byte
};

 

 

" 만약 명시적으로 다른 정렬을 사용하고 싶다면, GCC의 확장 기능을 사용할 수 있다. `__attribute__((packed))` 을 구조체 정의부 뒤쪽에 작성해주면 1바이트 정렬을 통해서 패딩을 제거한다.

// 1-byte struct member alignment
// size = 9, alignment = 1-byte, no padding for these struct members
struct S6 {
    char m1;    // 1-byte
    double m2;  // 8-byte
} __attribute__((packed));

 

 

- 바이트 및 비트 정렬

" 하드웨어 메모리 관리 전략으로 페이징을 선택하거나, PCI BAR이 주소를 볼 때 LSB의 몇개의 비트들이 0인 경우가 있다. 예를 들어, 보자. RAM이 4G인데 페이지 사이즈가 4096일 때, 페이지 할당은 어떻게 될까?

1" 페이지 0 - 0x0000_0000
2" 페이지 1 - 0x0000_1000
3" 페이지 2 - 0x0000_2000
...
4" 페이지 n - 0xFFFF_F000

 

" LSB 12비트가 모두 0이다. 이럴 때, 해당 주소들이 4096B(12비트)에 정렬되어 있다고 한다. 물론, 전제가 있어야 한다. 시작 주소 또한 4096B로 나눠져야 정렬되어 있다고 말할 수 있다. 즉, 뒤쪽(LSB)비트들이 계속 0을 유지할 경우, 해당 비트들에 대해 정렬되어 있다고 볼 수 있다.

 

 

- 특정 숫자 정렬시키기

" 17을 8바이트 정렬하고 싶고, 232B를 256바이트로 정렬하고, 5728B 을 4096B 로 정렬하고 싶다. 아래의 식들을 보고 규칙을 찾아내면 된다. 아래의 내용은 인자로 전달된 숫자를 올림해서 정렬시킨다.

1" (17 + (8 - 1)) & (~(8-1)) = (17 + 0x7) & (~0x7) => 24
2" (232 + (256-1)) & (~(256-1)) = (232 + 0xFF) & (~0xFF) => 256
3" (5728 + (4096 - 1)) & (~(4096 - 1)) = (5728 + 0xFFF) & (~0xFFF) = 8192

 

" 내림 정렬은 더 쉽다.

1" (17) & (~(8-1)) = (17) & (~0x7) => 16
2" (232) & (~(256-1)) = (232) & (~0xFF) => 0
3" (5728) & (~(4096 - 1)) = (5728) & (~0xFFF) = 4096

 

" 1가지만 규칙만 알면된다.

1" 정렬하고 싶은 숫자의 하위 비트들은 모두 0 이다. 예를 들어, 8을 비트 단위로 보면 `1000` 이다. 여기서 하위 3비트(2,1,0)는 모두 0 이다. 256 는 0b1_0000_0000이다. 그 아래 8비트는(7,6,5,4,3,2,1,0) 모두 0 이다. 

 

 

" 그렇다면, 리눅스 커널은 어떻게 정렬할까? 위에 방법들과 비교해보자. 크게 다르지 않다는 것을 알 수 있다. __ALIGN_KERNEL(), __ALIGN_KERNEL_MASK() 매크로 함수가 실제적인 기능을 담당하고 있다.

// tools/include/linux/mm.h - v6.5
#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))
#define ALIGN(x, a)			__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)		__ALIGN_KERNEL((x) - ((a) - 1), (a))
....

 

- Memory Boundary [참고1]

" 4KB boundary 라는 것을 무슨뜻일까? 만약, 시스템에 4GB RAM 이 있다면, 4KB boundary 는 다음과 같다.

1. 0(4096 * 0)
2. 4096(4096 * 1)
3. 8192(4096 * 2)
....

 

 

" diagram 으로 나타내면 다음과 같다. 각 메모리를 4096B 로 등분했다고 생각하면 된다. 여기서 만약, `... not cross 4KB address boundary` 라는 말은 무슨뜻일까?

 

 

 

" 리눅스 커널에 `dma_pool_create()` 함수가 있다. 이 함수는 DMA 를 위한 별도의 메모리 영역을 할당해주는 함수다. 이 때, name 과 dev 는 무시하자. 그렇면, size, align, boundary 만 남는다.

/**
 * dma_pool_create - Creates a pool of consistent memory blocks, for dma.
 * ....
 * @size: size of the blocks in this pool.
 * @align: alignment requirement for blocks; must be a power of two
 * @boundary: returned blocks won't cross this power of two boundary
 * Context: not in_interrupt()
 *
 * Given one of these pools, dma_pool_alloc()
 * may be used to allocate memory.  Such memory will all have "consistent"
 * DMA mappings, accessible by the device and its driver without using
 * cache flushing primitives.  The actual size of blocks allocated may be
 * larger than requested because of alignment.
 *
 * If @boundary is nonzero, objects returned from dma_pool_alloc() won't
 * cross that size boundary.  This is useful for devices which have
 * addressing restrictions on individual DMA transfers, such as not crossing
 * boundaries of 4KBytes.
 * ....
 */
struct dma_pool *dma_pool_create(const char *name, struct device *dev,
				 size_t size, size_t align, size_t boundary)

 

 

" size 는 말 그대로 DMA 를 위한 메모리 영역 사이즈를 의미한다. align 은 하드웨어 스펙을 참고해야 한다. DMA 는 1 byte 단위로 data transfer 를 하는게 아니라, 16B, 32B 처럼 block 단위로 작업을 진행한다. align 때문에 실제 요청한 사이즈보다 더 큰 사이즈를 할당받을 수 있다. 이게 무슨말일까? 예를 들어, size 를 300B 를 요청했다. 그런데, align 을 16B 로 설정했다. 그렇면, 할당받는 주소는 16 으로 나누어 떨어진다는 것이다. 즉, 할당받는 메모리 영역의 주소가 16 에 배수여야 한다는 소리다. 원래는 `주소가 aligned` 되어있다는 뜻이 주소만16B align 이면 되지만, dma_pool_create() 함수에서 align 은 할당받는 공간의 사이즈 또한 16 의 배수여야 할것으로 보인다. 왜냐면, DMA 의 data transfer 단위가 16B 일 경우, 반드시 사이즈 또한 16B 에 aligned 되어야 한다. 이럴 경우, size 를 300B 를 요청하더라도, 16 의 배수로 할당해야 하기 때문에, 300 보다 크면서 가장 작은 304B 를 할당하게 된다. 그리고, 주소 또한 16B 에 aligned 되어야한다. 아래의 그림을 보자.

 

 

" 만약, 정렬을 하지 않을 경우, 그냥 아무곳에서 300B 를 할당받으면 된다. 그냥 할당받는 경우를 검은색을 표시했다. 하지만, 제약 사항에 alignment 가 들어가면, start address 와 allocated size 가 16B 에 aligned 되어야 한다. 해당 부분은 빨간색으로 표시 되었다. 

 

" 그렇다면, 다시 본론으로 돌아와서 `... not cross 4KB address boundary` 는 무슨뜻일까? dma_pool_create() 함수의 `boundary` 에 4096 을 전달하면, 할당받은 메모리가 4KB boundary 를 넘을 수 없다는 뜻이된다. 이건 diagarm 으로 이해해보자.

 

 

" 위에 그림은 `size` 로 0x400, `align` 이 16 을 전달했다. 그리고, `boundary` 로 0x1000 을 전달했다. 커널은 0x2700 에서 0x400 만큼 메모리를 할당해주려고 하고 있다. 그런데, 0x2700 ~ 0x3100 은 4KB boundary(0x3000) 를 넘어버린다. 즉, 0x3000 ~ 0x3100 은 invalid 함을 의미한다.