Strings and Structs(2)

Struct

So, what's a struct?

low level로 보면 struct는 단순히 연속된 메모리입니다. array처럼 struct는 그 멤버들을 저장한 충분한 메모리를 차지합니다. 하지만 array와는 달리 서로 다른 자료형을 저장할 수 있습니다.

구조체의 선언은 다음과 같습니다.

struct contact {
    char firstname[20];
    char lastname[20];
    unsigned int phone;
};

struct contact bhuvan;

위와 같은 구조체를 선언할 때마다 struct를 사용하고 싶지 않다면 typedef를 이용해 구조체를 자료형으로 정의해주면 됩니다.

typedef struct contact contact;
contact bhuvan;

/* You can also declare the struct like this to get
 it done in one statement */
typedef struct optional_name {
    ...
} contact;

위의 방법 둘 중 하나를 사용하면 struct contact로 선언하는 대신에 contact로 사용할 수 있습니다.

만약 처음 코드를 순서를 바꾸지 않고 최적화하지 않는다면 각각 멤버의 주소는 다음과 같이 추측할 수 있습니다.

&bhuvan           // 0x100
&bhuvan.firstname // 0x100 = 0x100+0x00
&bhuvan.lastname  // 0x114 = 0x100+0x14
&bhuvan.phone     // 0x128 = 0x100+0x28

왜냐하면 컴파일러가 하는 일은 구조체의 크기만큼 공간을 예약해 놓고 각각의 offset을 계산해 쓰기를 원하는 변수에 접근할 것이기 때문입니다.

What do these offsets mean?

offset은 변수가 어디서 시작하는지를 의미합니다. 위의 예제에서 볼 때 phone변수는 0x128에서 시작해 연속된 4바이트를 차지합니다. 하지만 항상 4바이트만을 차지하는 것은 아닙니다.  Offset은 변수가 어디서 끝나는지는 정해주지 않습니다. 커널에서 자주 볼수 있는 다음과 같은 코드를 생각해 봅시다.

typedef struct {
    int length;
    char c_str[0];
} string;

const char* to_convert = "bhuvan";
int length = strlen(to_convert);

// Let's convert to a c string
string* bhuvan_name;
bhuvan_name = malloc(sizeof(string) + length+1);
/*
Currently, our memory looks like this with junk in those black spaces
                ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
 bhuvan_name = |   |   |   |   |   |   |   |   |   |   |   |
                ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾
*/


bhuvan_name->length = length;
/*
This writes the following values to the first four bytes
The rest is still garbage
                ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
 bhuvan_name = | 0 | 0 | 0 | 6 |   |   |   |   |   |   |   |
                ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾
*/


strcpy(bhuvan_name->c_str, to_convert);
/*
Now our string is filled in correctly at the end of the struct

                ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ____
 bhuvan_name = | 0 | 0 | 0 | 6 | b | h | u | v | a | n | \0 |
                ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾‾
*/
 

strcmp(bhuvan_name->c_str, "bhuvan") == 0 //The strings are equal!

위 코드를 살펴보면 우선 string struct를 선언하고 있고, 이 struct의 크기는 char c_str[0]이 0바이트를 잡고 있으므로 4바이트입니다.

이 때 bhuvan이라는 문자열과 그 문자열의 길이를 length로 저장해 놓고 이 두 정보를 하나의 구조체에 저장하기 위해 malloc으로 적당한 크기를 string 구조체의 주소가 가리키는 곳에 할당합니다. 즉, int를 저장하기 위한 4바이트와 문자열을 저장하기 위해 문자열의 길이 + NULL byte를 위한 공간인 1을 더해 할당해줍니다.

이렇게 할당하면 string 구조체의 주소인 bhuvan_name은 문자열의 길이 + 1 + sizeof(int)만큼의 메모리를 할당받았습니다. 이 다음 각각의 멤버에게 값을 넣어주고 복사해 주면 이 구조체의 멤버는 길이와 문자열이 되어 정보를 잘 저장하고 있을 수 있습니다.

이처럼 구조체의 마지막 멤버는 크기가 정해지지 않아도 offset만을 계산해 사용할 수 있습니다.

But not all structs are perfect

구조체는 padding이 필요할 수도 있습니다.(구조체를 pack하지 않는다고 가정합니다.) 왜냐하면 초기에는(심지어 요즘에도) 메모리의 주소를 32비트나 64비트 단위로 접근할 수 있었기 때문입니다. 즉, 32비트나 64비트의 배수로만 주소를 요청할 수 있다는 것을 의미합니다.

struct picture{
    int height;
    pixel** data;
    int width;
    char* enconding;
}
// You think picture looks like this
           height      data         width     encoding
           ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
picture = |       |               |       |               |
           ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾

위와 같은 구조체는 실제로는 64비트 시스템에서 아래와 같은 메모리를 차지할 것입니다.

struct picture{
    int height;
    char slop1[4];
    pixel** data;
    int width;
    char slop2[4];
    char* enconding;
}
           height   slop1       data        width   slop2  encoding
           ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
picture = |       |       |               |       |       |               |
           ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾

64비트 시스템에서는 포인터 변수가 8 바이트를 사용하기 때문에 8 바이트의 배수로 접근할 수 있도록 height와 data 사이에 4바이트의 패딩이, width와 encoding 사이에 4바이트의 패딩이 들어가게 됩니다.

하지만 프로세서가 정렬되지 않은 접근을 지원할 수 있다면 항상 이런 것은 아닙니다.

struct __attribute__((packed, aligned(4))) picture{
    int height;
    pixel** data;
    int width;
    char* enconding;
}
// Will look like this
           height       data        width     encoding
           ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
picture = |       |               |       |               |
           ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾

위와 같이 선언된 구조체는 4바이트로 정렬하여 pack했기 때문에 패딩이 발생하지 않습니다.

하지만 이러한 선언은 data나 encoding에 접근하기 위해 두번의 메모리 access가 필요합니다. 

항상 가능한 것은 아니지만 패딩을 없애는 다른 방법은 구조체의 멤버 순서를 바꾸는 것입니다.

struct picture{
    int height;
    int width;
    pixel** data;
    char* enconding;
}
// You think picture looks like this
           height   width        data         encoding
           ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
picture = |       |       |               |               |
           ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾

위와 같이 구조체의 멤버 순서를 바꾸는 것만으로도 구조체 내의 패딩을 없앨 수 있습니다.