태그 보관물: c++

C++ template 선언과 구현을 서로 다른 파일에 나눌 수 없다

커스텀 Queue 클래스를 작성하는데 queue의 item은 추후에 변경 될 수 있으므로 템플릿으로 작성하고자 한다. Queue class를 header에 정의하고 구현을 cpp 파일에 작성해 준다음 main 함수에서 다음과 같이 queue를 생성하고 컴파일을 시도한다.

다음은 해당 template을 사용하는 caller(main 함수)이다.

//
// C++ template instantiation test.
//
//                                             - litcoder

#include <iostream>
#include "queue.h"

using namespace std;
int main() {
    // Create an integer type queue.
    queue<int> q;

    // Push elements from the queue.
    q.push(0);
    q.push(1);
    q.push(2);

    // Pop and print all elements.
    while (! q.empty()) {
        cout << "Popped: " << q.pop() << endl;
    }

    return 0;
}

하지만 별 문제 없을것이라는 생각과 달리 안타깝게도 빌드는 실패한다. 공들여서 만든 method가 링커에 의해 하나도 빠짐없이 “undefined reference” 오류를 뱉으면서 실패한다.

$ make
g++  -g -Wall  -c -o queue.o queue.cpp
g++  -g -Wall  -c -o main.o main.cpp
g++ -o qtest queue.o main.o
/usr/bin/ld: main.o: in function `main':
/home/litcoder/Downloads/cpptemplate/main.cpp:12: undefined reference to `queue<int>::queue()'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:15: undefined reference to `queue<int>::push(int)'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:16: undefined reference to `queue<int>::push(int)'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:17: undefined reference to `queue<int>::push(int)'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:21: undefined reference to `queue<int>::pop()'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:20: undefined reference to `queue<int>::empty()'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:25: undefined reference to `queue<int>::~queue()'
/usr/bin/ld: /home/litcoder/cpptemplate/main.cpp:25: undefined reference to `queue<int>::~queue()'
collect2: error: ld returned 1 exit status
make: *** [Makefile:7: qtest] Error 1

이 문제에 대한 해결책은 생각보다 간단한데, cpp파일에 따로 분리했던 구현 부분을 선언들과 함께 header file에 두는 것이다. (해치웠나?)

$ make
g++  -g -Wall  -c -o queue.o queue.cpp
g++  -g -Wall  -c -o main.o main.cpp
g++ -o qtest queue.o main.o
$ ./qtest
Popped: 0
Popped: 1
Popped: 2

왜 undefined reference 오류가 났을까?

Queue.o가 빌드됐으니 거기 보면 분명히 저 method들이 선언되어 있을텐데 말이다. 빌드된 symbol들을 살펴보자,

$ objdump -t ./queue.o

./queue.o:     file format elf64-x86-64

SYMBOL TABLE:
0000000000000000 l    df *ABS*	0000000000000000 queue.cpp

O.O 없다. 아무것도. queue.o는 아무 symbol이 없는 빈 파일이었다.

앞서 해결됐다고 했던 header에서 template 선언과 구현을 모두 수행하는 경우에도 queue.o의 symbol table이 비어 있는것은 마찬가지 이지만, 이 경우, caller인 main.o에는 template이 실제 사용하는 type에 binding되어 embed되어 있다. main.o의 symbol들을 살펴보면 다음과 같이 mangle된 symbol들을 볼 수 있다.

$ objdump -t ./main.o

./main.o:     file format elf64-x86-64

SYMBOL TABLE:
0000000000000000 l    df *ABS*	0000000000000000 main.cpp
...
0000000000000000  w    F .text._ZN5queueIiEC2Ev	0000000000000048 _ZN5queueIiEC1Ev
0000000000000000  w    F .text._ZN5queueIiE4pushEi	000000000000003f _ZN5queueIiE4pushEi
...

참고로, C++ symbol의 type은 demangler를 이용하면 볼 수 있는데, demangle한 결과는 다음과 같다.

_ZN5queueIiEC2Ev -> queue<int>::queue()
_ZN5queueIiE4pushEi -> queue<int>::push(int)

결론

C++ template은 빌드하는 시점에서 어떤 data type으로 binding될 지 알 수 없기 때문에 구현 부분을 별도의 파일로 만들어 봤자 아무 것도 빌드 되지 않는다. Header file에 선언과 구현을 함께 두고 이 template을 사용하는 code가 이를 include하여 어떤 data type으로 binding될 지 결정해 주면 그때서야 실제 symbol이 caller module에 포함된다.

즉, template을 선언과 구현으로 나누어서 따로 빌드하는 것은 불가능할 뿐더러 의미도 없으니 include될 하나의 파일(주로 header)에 넣어서 선언과 구현을 합쳐두는게 가장 좋다.

Linux에서 메모리 포인터의 유효성 검증

Windows에서와 달리 Linux환경에서는 딱히 포인터의 유효성을 검증할 수 있는 system call이 없다. 이 포스팅은 Linux환경에서 이와 유사한 기능을 구현하기 위해 “정보의 바다”에서 찾은 내용들을 정리해 둔 것이다.

1. _etext를 이용하는 방법

첫번째 방법은 Define and use a pointer validation function 이라는 위키문서에서 가져온 것인데 컴파일러가 생성하는 text 영역의 시작점을 이용해서 포인터 값이 이를 침범 하는지 여부를 검사하고 유효성을 판단한다. 하지만 위 링크의 커멘트에도 나와 있듯이 시스템에 따라 동작하지 않을 수도 있으므로 reliable 한 구현이라 볼 수는 없다.

bool isValidPointer_ET(void *ptr) {
    extern const char _etext;
    return (ptr != nullptr) && ((const char*)ptr > &_etext);
}

2. msync()를 이용하는 방법

Checking whether a pointer is valid in Linux라는 블로그 포스트에 소개된 방법으로 매핑된 메모리 공간을 동기화 할 때 쓰는 msync() 시스템 콜을 호출 하면서 유효하지 않은 page 시작 주소를 넘겨 주면 0이 아닌 음수 값을 반환하는 것을 이용하는 방법이다. (이 경우 errno에 ENOMEM이 설정된다)

#include <sys/mman.h>
#include <unistd.h>

bool isValidPointer_MS(void *ptr) {
    const size_t pageSize = sysconf(_SC_PAGESIZE);
    void *basePtr = (void *)((((size_t)ptr) / pageSize) * pageSize);
    return msync(basePtr, pageSize, MS_SYNC) == 0;
}

3. mincore()를 이용하는 방법

Stackoverflow에 올려진 Testing pointers for validity (C/C++)라는 질문에 대한 답변에 있는 아이디어 중 하나인데 메모리 페이지의 swap 상태를 확인해서 반환해 주는 mincore()을 이용하는 방법이다. 해당 답변에는 다른 아이디어 들도 있으니 필요에 따라 참고.

#include <sys/mman.h>
#include <unistd.h>

bool isValidPointer_MC(void *ptr) {
    unsigned char vec = 0;
    const size_t pageSize = sysconf(_SC_PAGESIZE);
    void *basePtr = (void *)((((size_t)ptr) / pageSize) * pageSize);
    int ret = mincore(basePtr, pageSize, &vec);
    return (ret == 0 && ((vec & 0x1) == 0x1));
}

시험 결과와 결론

위의 함수들에 대해 Linux환경에서 전역 변수 포인터, 지역 변수 포인터, 널 포인터, 널 포인터는 아니지만 명백하게 무효한 포인터(0x04 같은), 동적 할당된 공간에 대한 유효성 여부는 잘 동작한다.

하지만, 이미 해제된 포인터나 할당되지 않은 heap 공간 내의 임의 주소에 대해서는 제대로 유효성 여부를 판단하지 못하고, 주소 범위가 유효 하다면 포인터 역시 유효 하다고 판단하는 오류가 세가지 구현 모두에 있다.

    // 해제된 heap공간에 대한 유효성 여부 확인. 모두 실패함.
    unsigned int* dynamicVar = new unsigned int[100];
    delete[] dynamicVar;
    EXPECT_FALSE(isValidPointer_ET(dynamicVar));
    EXPECT_FALSE(isValidPointer_MS(dynamicVar));
    EXPECT_FALSE(isValidPointer_MC(dynamicVar));


    // 할당 되지 않은 Heap공간 내의 임의 포인터에 대한 유효성 확인. 모두 실패함.
    unsigned int* dynamicUnallocVar = dynamicVar + 100;
    EXPECT_FALSE(isValidPointer_ET(dynamicUnallocVar));
    EXPECT_FALSE(isValidPointer_MS(dynamicUnallocVar));
    EXPECT_FALSE(isValidPointer_MC(dynamicUnallocVar)); 

즉, 위의 구현 들은 주어진 포인터가 유효한 메모리 공간내에 속하는지는 확인할 수 있어도, 동적 할당 영역의 메모리 포인터가 실제 read/write 가능한 상태인지 여부는 정확히 반환 할 수 없다.

시험에 사용한 code는 여기에 붙여 둔다.

연관 컨테이너에 find_if()를 쓴다구요?

연관 컨테이너는 데이터를 추가 할 때 내부에 hash table이나 tree 구조를 유지해서 많은 원소가 삽입 되더라도 원하는 값을 빠른 속도로 검색 하는것이 가능하도록 해준다.

어떤 key가 주어 졌을 때 이것이 정확히 원하는 값이 아니 더 라도 특정한 범위에 들면 해당 Block을 반환하는 코딩을 하고 있었는데, 생각보다 map이나 set 같은 연관 컨테이너에 find_if()로 조건을 주는 코드 레퍼런스들이 많았다. 예를 들면 다음과 같이 주어진 set에 대해 find_if()로 모든 원소들을 돌면서 주어진 key가 들어 갈 수 있는 Block 찾는 것과 같은 경우이다.

find_if(
  s.begin(), s.end(),
  [findKey](const Block* el) {
    return findKey >= el->blkBase \
      && findKey < (el->blkBase + el->blkSize); });

주어진 원소의 수가 얼마 없다면 이런 종류의 코드가 별 무리가 없겠지만, 원소의 수가 많아지면 두드러지는 성능 차이를 보인다. 다음은 이와 같이 find_if()로 모든 원소들을 방문해 가며 range에 속하는지 검사하는 코드를 vector, map, set에 대해서 10만개의 원소로 돌린 것인데, 오히려 vector에 비해 map과 set이 각각 4배에서 6배 정도의 느린 검색 성능을 보여 준다.

[Vector]
100000 items pushed to vector.
Insertion: 13ms
Searching: 28879ms

[Map]
100000 items pushed to map.
Insertion: 63ms
Searching: 120259ms

[Set]
100000 items pushed to set.
Insertion: 60ms
Searching: 193998ms

연관 컨테이너 들은 원소를 추가할 때 효율적인 검색을 위한 부가적인 동작을 수행해야 하므로 insertion에 시간이 조금 더 걸리는 건 그렇다 쳐도, 원소의 수에 따라 선형적으로 검색 시간이 증가하는 vector에 비해 4배에서 6배 정도의 검색 시간이 더 드는 결과는 연관 컨테이너에 대해 find_if()를 들이 대는 자체가 현명한 생각인가 하는 의구심이 들게 한다. 즉, find_if()를 사용하면 주어진 컨테이너의 구조에 맞게 효율적으로 iteration을 해 주고 그런거 없다. 적어도 g++(v7.5.0)에서는.

그렇다면 이 경우 처럼, C++에서 특정한 값이 아니라 주어진 키가 범위에 드는지 검사하고 싶은 경우는 어떻게 해야 할까? Java의 Navigatable* 만큼은 세부적이진 않지만 C++의 map과 set 모두 주어진 key에서 가장 가까운 값을 반환하는 lower_bound() / upper_bound()를 제공한다. 이를 이용해서 다음과 같이 반환된 객체에 대해서만 추가로 검사를 해서 범위에 드는지 확인하면 보다 효율적으로 구현할 수 있다.

auto re = s.lower_bound(&findBlk);
auto el = *re;
if (re != s.end()
    && (findKey >= el->blkBase && findKey < (el->blkBase + el->blkSize))) {
}

이렇게 find_if()로 모든 원소들을 방문하는 것이 아닌, lower_bound()로 반환 받은 결과만 검사하는 방법으로 위와 같은 10만개의 원소에 대해 돌려보면 기대했던 바와 같이 vector보다 훨씬 좋은 연관 컨테이너의 검색 속도를 볼 수 있다.

[Vector]
100000 items pushed to vector.
Insertion: 13ms
Searching: 29765ms

[Map]
100000 items pushed to map.
Insertion: 62ms
Searching: 35ms

[Set]
100000 items pushed to set.
Insertion: 62ms
Searching: 36ms

시험에 사용한 전체 코드는 GitHub Gist에 붙여둔다.

GCC에서 integer arithmetic overflow 방지 대책

Arithmetic overflow는 부호 있는 변수(signed variable)가 표시 할 수 있는 최댓값 / 최솟값을 넘어 섰을 때 부호가 바뀌면서 원하지 않는 결과가 나타나는 경우를 말한다.

#include <iostream>
#include <climits>

using namespace std;
int main(void) {
    int r = 0;
    int op = INT_MAX;
    cout << op << " + 1 = " << op + 1 << endl;
    return 0;
}

위의 코드를 다음과 같이 컴파일하고 실행하면 overflow가 발생한다.

$ g++ ./overflow.cpp
$ ./a.out
2147483647 + 1 = -2147483648

이와 같은 경우를 방지 하려면 물론 꼼꼼한 코드 리뷰도 중요 하지겠만 컴파일러에서 제공하는 overflow를 점검하는 빌트인 함수를 사용하거나 Safeint 혹은 이와 유사한 Boost의 Safe numerics의 사용을 고려해 볼 수도 있겠다. 하지만 이 방법들은 처음부터 사용이 고려되어야 하거나 이미 작성한 코드를 수정해야 하는 단점이 있다.

-ftrapv compiler switch

GCC 컴파일러에서 제공하는 -ftrapv switch를 사용하면 코드 수정 없이 arithmetic overflow가 발생 했을 때 SIGABRT를 발생 시키도록 컴파일러가 trap을 추가하게 할 수 있는데, 발견 되지 않은 overflow를 일으킨 후 오동작을 하게 되는 것 보다는 프로세스 중단이 낫다고 생각하면 이 switch를 고려해 볼 수 있다.

$ g++ -ftrapv ./overflow.cpp
$ ./a.out
Aborted (core dumped)

-fwrapv compiler switch

또 다른 경우로 최적화 옵션에 따라 실행 결과가 달라 지는 경우도 있다. 다음의 예제는 Stack overflow의 What does -fwrapv do?를 약간 변형한 것이다.

#include <iostream>
#include <climits>
 
using namespace std;
int optFunc(int i) {
    return i+1 > i;
}
 
int main(void) {
    int v = INT_MAX;
 
    if (optFunc(v)) {
        cout << "Unexpected." << endl;
    } else {
        cout << "Terminated OK." << endl;
    }
	
    return 0;
}

현실에서 쓰일 법한 코드는 아니지만 optFunc()를 작성한 사람의 의도가 INT_MAX가 인자로 주어질 때 “INT_MAX + 1“이 음수가 되면서 “INT_MAX + 1 > INT_MAX”가 false(0)를 반환하도록 하는 것이었다 하더라도 이 코드는 최적화 옵션에 따라 다른 결과 값을 내게 된다.

디버깅 등의 이유로 컴파일 할 때 최적화를 옵션을 -O0로 주면 원하는 대로 동작한다.

$ g++ -O0 ./fwrapv.cpp
$ ./a.out 
Terminated OK.

하지만, -O3 옵션을 주면, 컴파일러는 optFunc()가 항상 true(1)을 반환 할 것이라 가정하고 컴파일러가 이를 최적화 시켜 버려서 코드가 의도한 대로 동작하지 않게 된다.

$ g++ -O3 ./fwrapv.cpp
$ ./a.out 
Unexpected.

이러한 경우를 방지 하기 위해 -fwrapv switch를 주면 -O3 이상의 최적화 옵션에서도 해당 부분이 ‘wrapping’ 되어서 의도한 대로 코드가 동작하게 된다.

$ g++ -O3 -fwrapv ./fwrapv.cpp
$ ./a.out 
Terminated OK.

-Wconversion compiler switch

보다 쉬운 경우로, 표현 범위가 큰 타입에서 작은 타입으로 변환 될 때 값을 잃어 버려서 원하지 않는 결과가 생길 수도 있는데, 이 경우는 -Wconversion switch를 추가하면 컴파일시간에 잡아내서 경고를 출력하도록 할 수 있다. 예를 들어 64bit 시스템에서 unsigned long type인 size_t를 실수로 unsigned int에 할당한 것과 같은 경우들을 컴파일 시간에 찾아 경고를 출력해 주는데 -Weror와 함께 사용하면 컴파일이 멈추게 된다.

결론

코딩의 처음부터 안전한 연산을 고려 한다면 이를 지원하기 위한 라이브러리들을 고려해 볼 수 있겠지만, 컴파일러 스위치를 활용하여 arithmetic integer overflow 발생에 대한 대비를 할 수도 있다.

* 위의 예제들은 Ubuntu 18.04에서 g++ 7.5.0으로 시험 되었다.
** 위의 fwrapv 예제에 -fwrapv와 -ftrapv switch를 모두 사용하면 -fwrapv로 동작한다.

GDB에서 인스턴스의 실제 타입 표시하기

Base class로 부터 상속 받은 Derived class의 인스턴스를 Base class 포인터에 넣으면 GDB에서 타입이 제대로 표시되지 않는다. 이 때는 ‘set print object on’을 설정해서 GDB의 ptype <var> 명령 결과에 해당 인스턴스의 실제 타입이 함께 표시 되도록 할 수 있다.

예를 들어 다음과 같은 코드가 있다고 할 때

#include <iostream>
using namespace std;

class Base {
public:
  virtual void identify() {
      cout << "Base class" << endl;
  }
};

class Derived: public Base {
public:
  void identify() override {
      cout << "Derived class" << endl;
  }
};


int main(void) {
  // Derived class instance 이지만
  // GDB에서 Base type으로 표시된다.
  Base *c = new Derived();
  c->identify();

  delete c;
}

main() 함수 내의 “Base *c”를 GDB에서 확인해 보면 실제 인스턴스의 타입과 관련 없이 Base class로 표시된다.

(gdb) ptype c
type = class Base {
  public:
    virtual void identify(void);
} *

실제 인스턴스가 무엇인지 알고 싶다면, set print ojbect on을 설정해서 ptype 결과에 실제 인스턴스가 함께 표시되도록 할 수 있다. ( /* real type = … */)

(gdb) set print object on
(gdb) ptype c
type = /* real type = Derived * */
class Base {
  public:
    virtual void identify(void);
} *

이 설정을 다른 유용한 것들과 함께 ~/.gdbinit에 넣어두면 gdb가 실행될 때 자동으로 설정된다.

$ cat ~/.gdbinit
set print object on
set print pretty on
set print static-members on
set print vtbl on