[Algorithm] Flexible Array
자동으로 자라는 array 구조를 설명한다.
int a[] = {1, 2, 3};
위 코드처럼 C에선 처음 array size가 내부 값을 초기화하면서 고정된다. 이 크기를 유동성 있게 사용하기 위해선 struct 내부로 넣으면 된다.
struct flex {
int count;
int a[];
};
위 구조체를 잡아서 크기를 확인해보면 4 bytes만 나오게 된다.
#include <stdio.h>
struct flex { int count; int a[]; };
int main() { struct flex f; printf("sizeof(f)=%lu\n", sizeof(f)); printf("&f =%p\n", &f); printf("&f.a=%p\n", &f.a);
return 0; }
sizeof(f)=4
f=0x7ffd8718a9d4
f.a=0x7ffd8718a9d8
이런 구조는 아래 코드처럼 활용 될 수 있다.
#include <stdio.h>
#include <stdlib.h>
struct flex {
int count;
int a[];
};
int main()
{
int count = 100;
struct flex *fa;
fa = malloc (sizeof(struct flex) + sizeof(int)*count);
fa->count = count;
fa->a[0] = 1;
fa->a[99] = 100;
return 0;
}
위 코드를 메모리 맵으로 보면 아래처럼 보일 것이다.
이를 통해서 data array의 정보를 따로 관리할 수 있으며, a는 특정한 값을 가지는게 아니라, 실제 우리가 저장하는 data의 시작 위치를 가리키는 역할을 하게 된다. 실제 Kernel code에서도 flexible array가 사용하게 되는데 아래 코드에서 사용처를 볼 수 있다.
struct flex_array {
union {
struct {
int element_size;
int total_nr_elements;
int elems_per_part;
struct reciprocal_value reciprocal_elems;
struct flex_array_part *parts[];
};
/*
* This little trick makes sure that
* sizeof(flex_array) == PAGE_SIZE
*/
char padding[FLEX_ARRAY_BASE_SIZE];
};
};
Flexible array 내부 구조는 union으로 되어있는데, union은 가장 큰 크기의 type으로 결정되는데 보면 char padding[FLEX_ARRAY_BASE_SIZE]가 가장 큰 4KB이기 때문에 전체 구조의 크기는 4KB로 결정된다 (define을 따라가보면 1<<12가 존재한다). 처음엔 page 정보들이 있고 parts 아래엔 page size만큼 메모리가 잡혀있다. 메모리 맵으로 보면 아래와 같을 것이다.
element_size: 우리가 넣는 data unit의 크기elems_per_part: 내부에 들어가보면 한 page를 element_size로 나누면 몇개로 나눌 수 있는지 의미하는 값이다. 한 page size는 4K로 정해져있기 때문에 이 값은 1024가 된다.reciprocal_elems: 역수를 의미하는 값으로, 위에 elems_per_part의 역수 값이다. 1/1024는 너무나 작은 소수점이기 때문에 데이터를 많이 사용하게 되기 때문에, 이를 회피하고자 이 값에다 양의 정수 최대값 (2^32)을 곱해준다. 따라서 4194304 가 저장된다. 성능 때문에 소수점 연산을 제거하기 위해 해당 연산이 수행된다.total_nr_elements: 위에서 정한 element_size가 최대 몇개가 될지를 말하는 값이다. 이 값은 최대 허용 가능한 값보단 작아야하는데, 전체 4K에서 information size(여기선 int가 4개이기 때문에 총 16 bytes)를 빼면 실제 크기는 4096-16=4080이다. 이 값을 우리가 쓰는 element_size로 나누면 최대 1020개 정보를 담을 수 있다. 만약 우리가 담고자 하는 data가 int 100개라고 하면 문제 없이 담을 수 있다. 그러나 flexible array를 사용하게되면 실제 크기는 510*1024=522240이 실제 정보를 담을 수 있는 크기다. (추후 설명)
Non-Expansion 구조
flex_array_alloc
초기화 코드를 보면, 위 정보들을 초기화 해준 뒤에 우리가 저장하고자 하는 메모리 크기는 4*100=400B이고 실제 사용 가능한 크기 (4080B)보다 작기 때문에 flexible array 사용 없이 메모리를 쓴다. 따라서 &ret->parts[0]이 의미하는 메모리의 처음부터 사이즈만큼 poisoning 값 (유저가 사용하지 않을 것 같은 값) 0x6c6c6c6c으로 초기화를 해놓고, 유저가 접근했을 때 바뀔테니 해당 값을 통해서 접근 여부를 확인 할 수 있다.
max_size를 계산할 때 FLEX_ARRAY_BASE_BYTES_LEFT값 (전체 4KB 중에서 information을 뺀 나머지 값인 4080B)을 pointer의 크기만큼인 8B로 나눈 값인 510이다. 위에서 설명한 것 처럼, 요소에 값을 넣거나 주소값을 넣을 수 있다.
elements_fit_in_base는 1개의 page 안으로 다 데이터를 저장 할 수 있는지 확인하는 함수로, 4080B보다 작은지를 확인하고, 만약 그렇다면 초기값을 설정하도록 한다.
결과적으로 flex_array_alloc(4, 100, 0)이 의미는 malloc(sizeof(int) * 100)가 동적으로는 400B를 할당하지만, 실제 내부를 보면 4KB를 할당해서 동적으로 사용 할 수 있다.
struct flex_array *flex_array_alloc(int element_size, unsigned int total,
gfp_t flags)
{
struct flex_array *ret;
int elems_per_part = 0;
int max_size = 0;
struct reciprocal_value reciprocal_elems = { 0 };
if (element_size) {
elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
reciprocal_elems = reciprocal_value(elems_per_part);
max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
}
/* max_size will end up 0 if element_size > PAGE_SIZE */
if (total > max_size)
return NULL;
ret = calloc( 1, sizeof(struct flex_array));
if (!ret)
return NULL;
ret->element_size = element_size;
ret->total_nr_elements = total;
ret->elems_per_part = elems_per_part;
ret->reciprocal_elems = reciprocal_elems;
if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
memset(&ret->parts[0], FLEX_ARRAY_FREE,
FLEX_ARRAY_BASE_BYTES_LEFT);
return ret;
}
flex_array_put
Flexible array에 값을 쓰는 함수다.
int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
gfp_t flags)
{
int part_nr = 0;
struct flex_array_part *part;
void *dst;
if (element_nr >= fa->total_nr_elements)
return -ENOSPC;
if (!fa->element_size)
return 0;
if (elements_fit_in_base(fa))
part = (struct flex_array_part *)&fa->parts[0];
else {
part_nr = fa_element_to_part_nr(fa, element_nr);
part = __fa_get_part(fa, part_nr, flags);
if (!part)
return -ENOMEM;
}
dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
memcpy(dst, src, fa->element_size);
return 0;
}
fa: flexible array 구조체 포인터element_nr: element 개수src: 우리가 전달하고자 하는 값의 포인터part에는 elements의 시작주소가 저장
만약 n=10이며, flex_array_put(fa, 1, &n, 0)이 호출이 되면 아래 그림과 같은 모습이 발생할 것이다.
flex_array_get
Flexible array에 저장된 값을 읽는 함수다.
void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
{
int part_nr = 0;
struct flex_array_part *part;
if (!fa->element_size)
return NULL;
if (element_nr >= fa->total_nr_elements)
return NULL;
if (elements_fit_in_base(fa))
part = (struct flex_array_part *)&fa->parts[0];
else {
part_nr = fa_element_to_part_nr(fa, element_nr);
part = fa->parts[part_nr];
if (!part)
return NULL;
}
return &part->elements[index_inside_part(fa, element_nr, part_nr)];
}
Expansion 구조
만약 4080B (4KB에서 data 정보를 담고 있는 부분을 제외한 나머지 크기)보다 큰 데이터를 저장하려고 할 때는 elements_fit_in_base() 함수가 false를 출력할 것이다. 이 때 memset()을 하지 않기 때문에 poison값으로 초기화되지 않는다.
만약 우리가 저장하고자 하는 index가 4KB보다 더 큰 index일 경우 (Ex. 1500), flex_array_put 함수를 보면, part_nr에 fa_element_to_part_nr 함수를 통해서 우리가 저장하고자 하는 data를 가리키는 pointer의 index를 구하는 것을 볼 수 있다.
각 index별로 flexible array pointer를 가지기 때문에 1024B까지 저장할 수 있기 때문에, index 1에 저장 될 것을 예상 할 수 있다. 실제로 part_nr의 값이 의미하는게 바로 해당 index다. 그리고 index 1에 4096B만큼 할당하게 되고, poison 값(0x6C6C6C6C)를 넣어준다. 우리가 part_nr이 1인 곳에서 내부 index는 part_offset 값인 1500 – 1024인 476이 된다.
위 구조가 가지는 장점은, 실제 우리가 사용하는 부분에 대해서만 할당을 해서 사용하기 때문에 불필요한 부분에 대해서는 할당하지 않는다. 결국 flexible array가 확장한 경우엔 최대 510 * 1024의 크기를 저장 할 수 있다. Read 동작 또한 write과 동일하다.
최종적으로, 32-bit / 64-bit address에 따라서, element size에 따라서 최대 사 할 수 있는 element 개수가 달라질 수 있다. 아래 표를 보면 우리의 경우 pointer size가 8B, element size는 4B로 잡았기 때문에 510 * 1024 = 522240가 나온 것이다. 만약 동일한 pointer size에 element size만 2B라면 2배 많은 element를 담을 수 있을 것이다.
* Element size | Objects | Objects | * PAGE_SIZE=4k | 32-bit | 64-bit | * ---------------------------------| * 1 bytes | 4177920 | 2088960 | * 2 bytes | 2088960 | 1044480 | * 3 bytes | 1392300 | 696150 | * 4 bytes | 1044480 | 522240 | * 32 bytes | 130560 | 65408 | * 33 bytes | 126480 | 63240 | * 2048 bytes | 2040 | 1020 | * 2049 bytes | 1020 | 510 | * void * | 1044480 | 261120 |
최종적으로 처음 4KB로 사용 할 수 있다면 확장하지 않고 내부 4080B로 저장하며, 그 크기보다 큰 경우엔 확장해서 4KB 단위로 사용 될 때마다 할당해서 사용하는 구조다.