What Every C Programmer Should Know About Undefined behavior

What Every C Programmer Should Know About Undefined behavior #1/3

LLVM으로 컴파일된 코드는 가끔 SIGTRAP signal을 일으킬 때가 있습니다. 그 원인을 자세히 분석해보면, Clang⁠이 생성한 (x86 code로 가정) binary code안에 ud2 instruction이 있기 때문입니다. ud2 instruction은 __builtin_trap()= 함수와 같은 역할을 합니다이는 프로그램을 비정상적으로 종료시키는데 쓰이며, abort()⁠와 비슷한 역할을 한다고 가정하기 바랍니다. 왜 이 instruction이 프로그램 안에 들어있는지는 여러가지 이유가 있지만, 근본 원인은 C code에서 발생한 undefined behavior와 LLVM이 이를 처리하는 방식에 관련되어 있습니다.

Introduction to Undefined Behavior

LLVM IRintermediate representation과 C 언어 모두 "undefined behavior"란 개념이 있습니다. Undefined behavior는 여러 뜻을 가지는 매우 넓은 개념이며, John Regehr blog 에서 잘 소개되어 있습니다. 요약하면, C 언어에서 일리가 있다고 여겨지는 많은 부분도 사실 undefined behavior를 가지고 있으며, 여러 버그의 원인이 된다는 것입니다. 나아가서, C 언어의 undefined behavior는 (컴파일러와 런타임 모두 포함) implementation이 하드 디스크를 포맷하거나, 전혀 엉뚱한 일을 하거나, 심각한 문제를 발생시켜도 전혀 문제될 것이 없다는 것을 나타내고 있습니다. 다시 강조하지만, 꼭 John Regehr씨의 blog를 읽어보기 바랍니다또, C FAQ의 11.33을 읽어보기 바랍니다.

Undefined behavior가 존재하는 이유는, C 언어 설계자가, 매우 효율적인 저수준 프로그래밍 언어로 C 언어를 만들었기 때문입니다. 이와 반대로 Java와 같은 (여러 'safe'한 언어들 포함) 언어는, 안전하고 어떤 implementation에서 동작하더라도 같은 결과를 얻길 원했기 때문에, undefined behavior가 거의 없습니다. 그 대신 성능을 일부 포기했습니다. 두 방식 모두 완벽하다고 할 수는 없지만, 적어도, C 언어 프로그래머라면 undefined behavior가 무엇인지는 알아야 합니다.

먼저, 컴파일러가 빠른 성능을 얻기 위해 수행하는 최적화 작업에 있어서, 만병통치약은magic bullet 없습니다. 컴파일러가 최적화를 수행하는 방식을 간단하게 훑어보면, a) register allocation, scheduling등과 같은 간단한 작업이 있고 b) peehole optimization이나 loop transformation과 같은 여러가지 트릭을 가능한 적용하며, c) 가능한 불필요한 abstraction을 없애고, (이 원인으로는 C macro, inline function, C++에서 temporary object 등이 있습니다) d) 앞 작업들을 수행할 때, 원래 의미를 망치지 않아야 합니다. 이 작업들이 별 것 아닌것 같지만, (codec 등에서) 반복되는 작업에서 한 cycle이 달라질 경우, 전체 작업이 10% 빨라지거나, 10% 전력을 덜 소모할 수도 있습니다.

Advantages of Undefined Behavior in C, with Examples

Undefined behavior를 좀 더 깊게 파해치고, LLVM C 컴파일러의 policy를 살펴보기 전에, undefined behavior의 몇 가지 예를 들어서 왜 몇몇 undefined behavior가 (Java와 같은 안전한 언어에 비해) 성능 향상에 도움이 되는지 설명하려고 합니다. 크게 두 가지가 있는데, 하나는 undefined behavior로 인해 가능한 최적화 기법들, 하나는 undefined behavior로 인해 overhead를 피하는 법이 있습니다. 물론 모든 경우에 이를 수행할 수 있는 것은 아니며, 모든 경우를 다 해결하기 위해서는 halting program 문제Halting problem 참고 포함 여러 어려운 문제를 풀어야 합니다.

한가지 알아둘 점은, C 언어 표준이 undefined behavior라고 명시한 것 중 일부에 대해서는 Clang과 GCC에서 확실히 정의하고 있습니다. 즉 일부에 대해서는 더 이상 undefined behavior가 아닌 셈입니다. 이 장에서 설명할 내용들은 표준에서 undefined behavior로 명시한 것이며, 이 두 컴파일러에서도 (default mode에서) undefined behavior라고 정의한 것들입니다.

  • 초기화하지 않은 변수를 쓰기Use of an uninitialized variable

    초기화 되지 않은 변수를 쓰는 것은 버그를 일으키는 가장 흔한 원인이기도 하며, 이 것을 잡기 위한 여러가지 도구들이 꽤 많습니다. 여기에는 컴파일러 경고warning부터, static analyzer, dynamic analyer등이 있습니다. Java의 경우, 모든 변수를 0으로 초기화하는데 반하여, C 언어의 경우, 모든 변수를 초기화할 필요가 없기 때문에, 성능 향상의 여지가 있습니다. 대부분 scalar type의 변수의 경우에는 초기화에 들어가는 overhead가 미미하지만, stack array나 malloc으로 할당한 memory에 대해서는 memset()⁠과 같은 작업이 필요하므로, (이런 공간이 자주 overwrite될 경우에) 초기화에 들어가는 overhead가 꽤 큽니다.

  • Signed Integer Overflow

    int type 연산의 결과가 overflow될 때, 그 결과는 undefined입니다. 예를 들어 INT_MAX + 1⁠는 INT_MIN⁠이라고 보장할 수 없습니다. 그리고 바로 이런 이유에서, 일부 코드에서 최적화 수행이 가능해집니다. 예를 들어, INT_MAX + 1⁠이 undefined이기 때문에, X + 1 > X⁠가 항상 true라고 단정할 수 있습니다다시 말하면, INT_MAX + 1⁠이 overflow된다라는 것을 생각할 필요가 없으므로, overflow 가능성을 아예 무시하고 해석이 가능하므로 X + 1 > X⁠를 true라고 단정할 수 있습니다 또, signed type에서 곱셈이 overflow를 일으키지 않기 때문에왜냐하면 undefined이므로X * 2 / 2⁠를 X⁠라고 단정할 수 있습니다. 이게 별 것 아닌 것 같지만, inline이나 macro 확장에 아주 자주 나오기 때문에, 성능 향상에 도움이 됩니다. 또 중요한 예를 들면,

    for (i = 0; i <= N; ++i) { ... }
    

    컴파일러는 위 반복문에서 i⁠가 overflow될 경우 undefined라는 것을 알기 때문에, 위 반복문에 정확히 N+1⁠번만큼 반복된다는 것을 알 수 있습니다달리 말하면, overflow가 undefined이기 때문에, 컴파일러는 overflow가 일어날 가능성에 대해 전혀 생각할 필요없이, 일어나지 않는다고 단정하고 이 코드를 해석할 수 있습니다. 만약 C 언어 정의가, signed type 연산 도중 overflow시 (unsigned type처럼) wrap around된다고 되어 있었다면, 컴파일러는 위 코드가 N+1⁠번 반복된다고 생각할 수 없습니다. 왜냐하면, N⁠이 INT_MAX⁠일 경우, 위 코드는 무한 반복문이 되기 때문입니다. 따라서 이 경우 최적화를 수행하기가 거의 불가능해집니다. 게다가 대부분 64-bit platform에서는 반복문에 int⁠ type을 쓰기 때문에 문제는 더욱 심각해집니다.

    이와 반대로, unsigned overflow는 2's complement (wrapping) overflow가 된다고 정의되어 있기 때문에, 프로그래머는 overflow 걱정없이 쓸 수 있습니다. 만약 signed integer overflow가 정의되어 있다면, 앞에서 설명한 것과 같은 최적화는 불가능합니다. (예를 들어, 64-bit target에서 반복문 안에서 끊임없이 sign extension을 수행해야될 수도 있습니다.) Clang⁠과 GCC⁠의 경우, -fwrap 옵션을 써서 signed integer overflow가 일어날 때, (INT_MIN⁠을 -1⁠로 나누는 것을 제외하고) 2's complement overflow가 일어나도록 정의할 수 있습니다.

  • Oversized Shift Amounts

    uint32_t⁠를 32 bit 또는 그 이상 shift하는 것은 undefined 입니다. 제원 저자 추측으론, CPU들이 이 경우에 각각 다른 결과를 만들어내기 때문에 C 언어 정의가 이렇게 결정된 것이 아닐까 추측하고 있습니다. 예를 들어, x86은 32-bit만큼의 shift를 5 bit로 잘라냅니다truncate. (즉 32-bit만큼 shift는 0-bit shift가 됩니다.) 반면에, PowerPC의 경우, 32-bit만큼의 shift가 6 bit로 잘라냅니다. (그래서, 32-bit만큼 shift를 수행하면, hard drive가 포맷되는 등 undefined behavior가 일어날 수 있으며, 0 bit shift가 된다고 보장할 수 없습니다.) 이런 불일치성을 없애려면, 컴파일러가 추가 연산(and 연산)을 해야하기 때문에, 일반적인 CPU에서 (shift 연산만큼) 약 두 배 정도 시간이 더 걸리게 됩니다.

    (역자 주: 그래서, 이런 overhead를 피하고자, 32 bit 이상 shift하는 것을 undefined로 결정하고, implementation에 맞긴 것으로 판단됩니다.)

  • 무작위 포인터 참조와 배열 범위 밖 접근Dereferences of Wild Pointers and Out of Bounds Array Accesses

    무작위적인 (예를 들어 free⁠된 메모리에 대한 포인터 또는 NULL) 포인터를 역참조dereference하는 것과 배열 밖을 접근하는 것은 설명이 필요없는, undefined behavior입니다. 이런 형태의 undefined behavior를 없애려면 array에 접근할 때마다 범위 검사range check를 해야 하며, pointer 연산을 수행할 때마다 이 범위에 대한 정보가 전달되도록 ABI가 바뀌어야 합니다. 또, 이런 변화는 여러 수치 연산을 필요로 하는 프로그램에 큰 overhead가 되며, 기존 C 라이브러리와 binary 호환성에 문제를 일으키게 됩니다.

  • NULL 포인터 역참조Dereferencing a NULL Pointer

    널리 알려져있는 것과 반대로, C 언어에서 null 포인터를 역참조dereference하는 것은 undefine입니다. 다시 말해 null 포인터를 dereference한다고 해서 trap이 발생한다는 보장이 없으며, 주소 0에 mmap⁠을 할 경우, 해당 page에 접근할 수 없습니다. 이는 무작위 포인터 참조나, NULL을 sentinel로 쓰는 것과는 다른 이야기입니다. NULL pointer dereference가 undefined라는 규칙이 있기에, 여러 최적화 수행이 가능합니다. 이와 반대로 Java의 경우, 컴파일러가 pointer가 null이 아니라는 것을 보장할 수 없으면, side effect가 발생할 수 있는 dereference 연산의 위치를 마음대로 바꿀 수가 없기에 최적화가 거의 불가능합니다. 또한 scheduling과 다른 형태의 최적화 수행도 매우 힘들어지게 됩니다. C 기반의 언어는, NULL dereference가 undefined이기 때문에, macro expansion이나 inline 상황에서 수많은 간단한 scalar optimization이 가능합니다.

    LLVM 기반의 컴파일러를 쓴다는 전제로, NULL을 dereference했을 때, crash나는 것을 원한다면, 해당 포인터를 volatile⁠로 선언하면 됩니다. (volatile⁠의 경우, 대부분 최적화가 일어나지 않습니다.) 현재, NULL pointer를 올바른 주소로서 loading하거나 또는 pointer를 통한 dereference가 null일 수도 있다를 나타내는 컴파일러 옵션은 없습니다.

  • Violating Type Rules

    int * 타입을 float * 타입으로 캐스팅한 다음 dereference하는 (int⁠를 float⁠으로 해석하는) 것은 undefined behavior입니다. 그런데, memcpy 함수에서 이런 비슷한 작업을 하지만, pointer cast를 쓰는 것은 올바른 방법이 아니며, undefined behavior가 발생합니다. 이 규칙은 꽤 미묘하며quite nuanced, 여기서 다루지는 않겠지만, =char *=로 casting하거나, special property가 있는 vector, union 등은 예외입니다. 이 규칙에 의하여, Type-Based Alias Analysis (TBAA)가 가능하며, 이는 컴파일러가 memory access 최적화하는데 널리 쓰이고 있는 분석입니다. 이를 통하여 생성된 코드의 성능을 크게 개선할 수 있습니다. 예를 들어 아래 코드를 보면,

    float *P;
    
    void zero_array() {
      int i;
      for (i = 0; i < 10000; ++i)
        P[i] = 0.0f;
    }
    

    Clang⁠은 위 코드를 memset(P, 0, 40000)⁠로 최적화를 수행합니다. 이 최적화 기법은 또한 여러 load 연산을 loop 밖으로 뺀다거나, 중복된 식 제거common subexpression elimiation에 쓰입니다. 이 형태의 undefined behavior는 -fno-strict-aliasing 옵션을 써서 제거할 수 있으며, 이럴 경우 위와 같은 분석을 할 수 없으며, 따라서 Clang⁠은 위 코드를 (몇 배 느린) 4-byte store 연산을 10000번 반복하는 코드를 생성합니다. 왜냐하면, 아래 코드처럼, store 연산이 P 값을 변경하지 않는다는 보장이 없기 때문입니다:

    int main() {
      P = (float*)&P;  // cast causes TBAA violation in zero_array.
      zero_array();
    }
    

    위와 같이 남용하는 것은, 드물게 일어나기 때문에, 표준 위원회는 괜찮아보이는 type cast를 undefined behavior로 하는 대신 최적화가 가능하도록 결정했습니다. Java의 경우, unsafe pointer casting이 전혀 불가능하기 때문에, 위와 같은 단점없이 type-based 최적화가 가능합니다.

    어쨋든, 위 글에서 소개한 바와 같이, C 언어 undefined behavior를 통해 몇몇 최적화가 가능하다는 것을 소개했습니다. 위에서 소개한 undefined behavior 이외에도, foo(i, ++i)⁠와 같은 sequence point violation, multithread 환경에서 race condition, restrict violation, divide by zero 등의 undefined behavior도 있다는 것을 알아두시기 바랍니다.

    다음 단원에서는 성능에 중점을 두지 않더라도 undefined behavior가 꽤 위험하다는 것을 다룰 예정입니다. In our final post in the series, we'll talk about how LLVM and Clang handle it.

What Every C Programmer Should Know About Undefined behavior #2/3

앞에서, undefined behavior가 무엇인지 그리고 C와 C++ 컴파일러가 undefined behavior를 통해 safe한 언어들에 비해 더 나은 성능을 가진 application을 만들 수 있다는 것을 다루었습니다. 이 장에서는 C 언어의 undefined behavior가 얼마나 위험한지unsafe에 대해 다루겠습니다. 이를 통해 undefined behavior가 원하지 않는 놀라운 결과를 가져올 수도 있다는 것을 보일 것입니다.

In Part #3, we talk about what friendly compilers can do to mitigate some of the surprise, even if they aren't required to.

I like to call this "Why undefined behavior is often a scary and terrible thing for C programmers". :-)

Interacting Compiler Optimizations Lead to Surprising Results

현대 컴파일러의 optimizer는 지정된 순서로 여러 최적화를 수행합니다. 때때로 이러한 최적화는 반복되어 수행되며, 컴파일러가 향상될 때마다 최적화가 달라질 수 있습니다. 또, 서로 다른 컴파일러는 매우 다른 optimizer를 가지고 있습니다. 최적화가 각각 다른 단계에서 수행되기 때문에, 앞 최적화 단계에서 이루어진 코드 변경 덕택에 엉뚱한emergent 현상이 발생할 수도 있습니다.

현실적인 예제로, (Linux Kernel에서 발견된 버그의 간단한 버전인) 아래 코드를 보기 바랍니다:

void contains_null_check(int *P) {
  int dead = *P;
  if (P == 0)
    return;
  *P = 4;
}

위 코드는 분명하게 null pointer를 검사하고 있습니다. 만약 컴파일러가 "불필요한 null 검사redundant null check" 단계 전에 "죽은 코드 제거dead code elimination"을 수행한다면, 위 코드는 아래 두 단계로 변경될 것입니다:

<pre> void containsnullcheckafterDCE(int *P) { <strike>//int dead = *P;</strike> // deleted by the optimizer. if (P == 0) return; *P = 4; } </pre>

다음으로 아래처럼 변경됩니다:

void contains_null_check_after_DCE(int *P) {
  if (P == 0)
    return;
  *P = 4;
}

하지만, optimizer가 이 두 최적화를 반대 순서로 수행했다면, 즉, DCE 전에 RNCE를 수행한다면, 코드가 아래 두 단계로 변경될 수 있습니다:

void contains_null_check_after_RNCE(int *P) {
  int dead = *P;
  if (false)  // P was dereferenced by this point, so it can't be null 
    return;
  *P = 4;
}

그리고, DCE가 수행되어 아래처럼 바뀝니다:

void contains_null_check_after_RNCE_and_DCE(int *P) {
  //int dead = *P;
  //if (false)
  //  return;
  *P = 4;
}

분별력있는reasonable 프로그래머라면, 컴파일러가 null 검사를 없애버렸다는 사실에 매우 놀랄 것입니다. (그리고 컴파일러 버그를 보고하겠지요) 하지만, 표준에 따르면, "DCE후에 RNCE"와 "RNCE 후에 DCE" 모두 올바른 최적화 방법이며, 두 최적화 기법 모두 다양한 프로그램에서 성능 향상을 위해 사용되는 중요한 기법입니다.

위 예는 매우 의도적으로 만든 간단한 코드이지만, inline 덕택에 이러한 일들이 매우 자주 일어납니다: inline으로 추가한 함수는 부가적인 최적화 기법을 적용할 기회를 제공하게 됩니다. 즉, optimizer가 함수를 inline으로 하겠다는 것을 결정하면, 여러 local 최적화 단계가 수행되며, 이에 따라 코드의 동작 방식이 바뀔 수 있습니다. 이는 표준에 따라 정당한 것이며, 현실적으로 성능 향상에 매우 중요한 기법입니다.

Undefined Behavior and Security Don't Mix Well

C 계열의 언어는 다양한, 보안이 중요한 코드, 예를 들어 kernel 또는 setuid daemon, web browser등의 프로그램을 작성하는데에 쓰입니다. 이런 프로그램들은 의도적인 공격이 담겨있는 적대적인 입력 데이터를 받을 수 있으며, 버그가 있을 경우, 여러 보안 문제를 일으킬 수 있습니다. 다행히도, (널리 알려진) C 언어의 한가지 장점은, code를 읽으면서, 실제 시스템에서 일어나는 일을 쉽게 파악할 수 있다는 것입니다.

그러나, undefined behavior 때문에 이런 장점이 가려지는 경항이 있습니다. 결국, 대부분 프로그래머들은 앞에서 다룬 null 검사 코드가 실제로 null을 검사할 것이라고 추측할 것입니다. 별로 놀라워하지 않을 수도 있지만 (왜냐하면, null check를 하지 않더라도, 그 다음 store 연산에서 프로그램이 crash할 것이므로), 이외에도 정상적으로 보이는 C 코드가 실제로는 전혀 엉뚱한 일을 하는 경우가 많습니다. 이러한 문제가 (Linux kernel, OpenSSL, glibc 등) 여러 프로젝트에 영향을 주었으며, CERT가 GCC 대상으로 보안 약점 보고를 만들게 되었습니다. (저자: 제 개인 의견으론 이는 단순히 GCC 문제가 아니며, 최적화 기능이 있는 대부분 C 컴파일러 모두 해당된다고 생각합니다.)

예를 들어, 다음 C 코드를 보기 바랍니다:

void process_something(int size) {
  // Catch integer overflow.
  if (size > size+1)
    abort();
  ...
  // Error checking from this code elided.
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

위 코드는 malloc⁠이 파일에서 읽은 데이터를 저장할 수 있는 충분한 공간을 확보하도록 (이때, nul terminator를 위해 추가 byte 확보) 검사하며, 이 때, integer overflow가 일어날 경우, 더 이상 작업을 수행하지 않도록 합니다. 그러나, 이 코드는 이전 Section에서 설명했던 signed integer overflow 문제를 그대로 갖고 있습니다. 즉, 컴파일러 optimizer가 위 코드의 검사 코드를 제거할 수 있습니다. 따라서 컴파일러는 아래와 같은 코드를 생성할 수 있습니다:

void process_something(int *data, int size) {
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

64-bit 플랫폼을 예로 들면, size⁠가 (아마도 디스크의 파일 크기가) INT_MAX⁠일 경우, 이는 attacker가 이용해 먹을 수 있는 버그가 됩니다. 이것이 얼마나 끔찍한 것이나면: 코드를 검사하는 사람auditor이 이 코드를 보고, 적절한 overflow 검사가 있다고 판단할 것이고, 테스트하는 사람은 구체적인 에러 경우를 검사하지 않은 한, 문제가 없다고 판단할 것이며, 이 코드는 안전하다고 결론이 날 것이니나, 누군가 이 헛점을 악용하는 경우가 발생하게 될 것입니다. 결국, 이는 놀랍지만, 꽤 심각한scary 버그입니다. 다행히도, 이 경우에는 문제가 간단합니다. 위 검사 대신 size == INT_MAX=⁠ 또는 이와 비슷한 코드를 쓰면 됩니다.

드러난 것처럼, integer overflow는 여러가지 이유로 인하여 보안상 문제가 됩니다. 완벽하게 정의된defined integer 연산을 쓰더라도 (예를 들어 -fwrapv 옵션을 쓰거나 unsigned integer만 사용), 전혀 다른 integer overflow bug가 발생할 수 있지만, 보통 이런 경우는 코드에서 발견하기 쉽거나 대부분 보안 검사자security auditor들이 알고 있는 문제일 것입니다.

Debugging Optimized Code May Not Make Any Sense

일부 개발자, 특히 생성된 machine code를 보는 것을 좋아하는 low level embedded 프로그래머들은 최적화를 활성화시킨 상태에서 개발하곤 합니다. 개발 도중에는 버그가 발생할 경우가 많기 때문에, (최적화를 활성화 시킨 상태에서 개발하게 되면) 놀랄만한 최적화가 불균형하게 일어나게 되어 runtime에 디버그하기 힘든 상황에 처하기 쉽습니다. 예를 들어, 앞 장에서 설명한 zero_array 함수에서 i = 0 초기화 코드를 실수로 빼먹었다면, 컴파일러는 (초기화되지 않은 변수를 쓰는 것은 undefined이므로) 전체 반복문을 제거할 수도 있기에, 결국 zero_array 함수는 단순한 return;⁠으로 전락하게 됩니다.

다른 예로, (global) function pointer를 쓰는 경우를 살펴보겠습니다:

static void (*FP)() = 0;

static void impl() {
  printf("hello\n");
}

void set() {
  FP = impl;
}

void call() {
  FP();
}

Clang⁠은 위 코드를 아래와 같이 최적화합니다:

void set() {}

void call() {
  printf("hello\n");

}

왜냐하면, null pointer를 호출하는 것은 undefined이므로, 컴파일러는 call 함수를 호출하기 전에 반드시 set 함수가 호출되어야 한다는 것으로 가정하게 되기에 이런 코드 생성이 가능하게 됩니다. 개발자가 set 함수를 호출하는 것을 빼먹은 상황이지만, (최적화를 활성화 시켰기 때문에) 이런 식으로 동작하는 게 가능하게 된 것입니다. 만약 (debug mode 등) 최적화를 끈 상태에서 build 했을 경우, null pointer dereference로 프로그램이 종료하게 되어, 훨씬 빠르게 실수를 알아차릴 수 있었을 것입니다.

결국, 이 문제는 해결하기 쉽습니다. 이상하게 돌아단가고 의심이 되면, -O0⁠를 써서 최적화를 끄게 되면 문제를 쉽게 발견할 가능성이 높아집니다.

Undefined behavior에 의존하는 동작하는 코드는 컴파일러가 변경되면 망가진다"Working" code that uses undefined behavior can "break" as the compiler evolves or changes

저희는 동작하는 (것처럼 보이는) 프로그램이 새 LLVM으로 build하면 동작하지 않거나, GCC로는 잘 동작하는 프로그램이 LLVM으로 옮겼을 경우, 망가지는 경우를 여러번 봤습니다. 때때로 이는 LLVM의 버그로 인한 것이지만, 대부분의 경우는 프로그램에 잠재하는 버그가 컴파일러에 의해 발견되었기 때문입니다. 이런 버그는 전혀 다른 방향으로 영향을 줄 수 있으며, 여기에서는 두가지 경우를 예로 들겠습니다:

  1. 초기화되지 않은 변수를 쓴 코드가 (기존에 운이 좋게도 0으로 초기화되어) 기존에는 동작했지만, 이제 0이 아닌 다른 register를 쓰게 되어 문제를 일으키는 경우, 이는 register 할당allocation이 바뀔 경우 흔하게 일어납니다.
  2. 스택에서 array overflow를 일으키는 코드가 (운이 좋게도 덮어 쓴 부분이 쓰이지 않은 영역이어서) 기존에 동작했지만, 지금은 문제를 일으키는 경우. 이 경우, 컴파일러가 stack에 변수를 배치하는 방식이 바뀌거나, 또는 변수의 lifetime이 겹치지 않는다고 판단될 경우, 같은 stack 영역을 공유하기 때문에 일어납니다.

중요한 점은, 버그가 있는 코드에서 발견된 undefined behavior 때문에, 향후 컴파일러가 어떤any 최적화라도 마음대로 수행할 수 있다는 것입니다. Inlining, loop unrolling, memory promotion 그리고 다른 최적화 기법이 갈 수록 향상되고 있으며, 한 가지 기법에 의해 최적화된 코드는 다른 최적화가 일어날 수 있는 기회가 되어 또 다른 최적화가 또 수행되게 됩니다.

제가원 저자 보기엔, 이는 매우 불편한 상황입니다. 왜냐하면, 이는 결국 컴파일러를 비난할 원인을 제공하는 것처럼 보이기 때문이기도 하지만, 수많은 C 코드들이 사실상 터지길 기다리는 지뢰밭이라는 것을 뜻하기 때문입니다. 이로 인해 더 큰 문제가 있는데…

큰 규모의 코드에서 undefined behavior가 있는지 판단하는 믿을 수 있는 방법은 없다

앞에서 말한 이 지뢰밭이 생각한 것보다 더 심각한데, 그 이유는, 큰 규모의 application에서 undefined behavior가 없기에 (향후에도) 문제 없다라고 판단할 좋은 방법이 없기 때문입니다. 일부 버그들을 발견하는데 도움을 주는 많은 도구들이 있지만, 향후에도 안전하다라는 보장을 줄 수 있는 도구는 없습니다. 이런 도구들의 장단점에 대해 좀 더 알아보면:

  1. The Valgrind memcheck는 초기화되지 않은uninitialized 변수와 기타 메모리 관련 버그를 잡는데 쓸 수 있는 기막히게 좋은fantastic 도구입니다. 단점은, 이 도구는 꽤 느리다는 것이며, 이는 생성된 machine code에 버그가 있는 경우에만 찾아낼 수 있다는 점입니다. (즉, optimizer가 제거한 코드는 찾을 수 없음). 그리고 프로그램이 C 코드로 작성되었다는 것을 알지 못합니다. 따라서 범위를 벗어나는 shift 문제shift-out-of-range나 signed integer overflow 문제를 찾아낼 수는 없습니다.
  2. Clang⁠은 experimental -fcatch-undefined-behavior 모드를 가지고 있으며, 이는 범위를 벗어나는 shift나 간단한 array 범위 에러 등을 검사하는 runtime 검사를 추가해 줍니다. 이는 application runtime을 느리게 하는 단점이 있으며, random pointer dereference와 같은 문제를 발견할 수는 없지만 (Valgrind는 가능), 대신 여러 다른 중요한 버그들을 잡을 수 있습니다. 또, Clang⁠은 -ftrapv 옵션을 완벽하게 지원합니다. (-fwrapv 옵션과 혼동하지 말기 바랍니다.) 이 옵션은 signed integer overflow가 일어날 경우, trap이 일어나도록program이 끝나도록 해 줍니다. (GCC도 이 옵션이 있지만, 제 경험상 버그가 있고 믿을 수 없습니다unreliable) 아래에 -fcatch-undefined-behavior 데모가 있습니다.
$ cat t.c
int foo(int i) {
  int x[2];
  x[i] = 12;
  return x[i];
}

int main() {
  return foo(2);
}
$ clang t.c 
$ ./a.out 
$ clang t.c -fcatch-undefined-behavior 
$ ./a.out 
Illegal instruction
  1. 컴파일러 경고 메시지는 uninitialized variable과 간단한 integer overflow 버그 등, 몇몇 종류의 버그를 잡는데 꽤 도움이 됩니다. 두 가지 제약이 있는데, 1) 실행될 때 코드에 대한 동적 정보가 없으며 2) 이 검사는 컴파일 시간을 늘리기 때문에 매우 빨리 수행되어야 한다는 점입니다. 따라서 제한적일 수 밖에 없습니다.
  2. Clang Static Analyzer는 좀 더 깊게 분석하며 (undefined behavior를 쓰거나, null pointer를 dereference하는 등) 버그를 찾아낼 수 있습니다. 이 툴은 (분석 시간에 제약을 받지 않으므로,) 좀 더 향상된 컴파일러 경고 메시지를 만들어 주는 툴이라 생각하시면 됩니다. 단점은 1) 프로그램 실행에서 얻을 수 있는 동적 정보가 없다와 2) 대부분 개발자의 일반적인 작업 방식에 통합되어 있지 않다입니다. (다행히, 이 도구는 이미 Xcode 3.2 버전부터 통합되어 있습니다)
  3. LLVM "Klee" Subproject는 symbolic analysis를 써서 코드의 모든 가능한 path를 분석해서, testcase를 생성해 줍니다. 대규모 application에 쓰기에는 현실적이지 않지만impractical, 그래도 꽤 좋은 툴입니다.
  4. 제가원 저자 직접 써 보지는 않았지만, Chucky Ellison씨와 nd Grigore Rosu씨가 만든 C-Semantics tool은 꽤 관심이 가는 툴이며, (sequence point violation과 같은) 종류의 버그를 잡아 줄 수 있습니다. 아직 연구 단계 prototype이지만, (독립적이며 작은) 프로그램 개발에 꽤 도움이 될 수 있습니다. John Regehr씨의 blog⁠를 읽어보시기를 추천합니다.

요약하면, 일정 부분의 버그를 찾는데 도움이 되는 툴은 많지만, 어느 것도, 프로그램에 undefined behavior가 없다는 것을 보장해주지 않습니다. real world에 돌아가는 application에 버그가 많다는 것과, c 언어가 여러 중요한 application에 쓰인다는 것을 생각할 때, 이는 꽤 심각하다고 갈 수 있습니다. 다음 장에서는 C 언어가 undefined behavior를 다룰 때 쓸 수 있는 Clang option들에 대해 알아보겠습니다.

What Every C Programmer Should Know About Undefined Behavior #3/3

컴파일는 왜 undefined behavior에 의존하는 최적화를 할 때 경고할 수 없는가?Why can't you warn when optimizing based on undefined behavior?

종종 "컴파일러는 undefined behavior에 의존하는 최적화를 수행할 때, 왜 경고하지 않는가"에 대한 질문을 받곤 합니다. 왜냐하면 그런 undefined behavior는 대부분 user code의 버그이기 때문입니다. 그렇게 경고를 하는 게 어려운 이유는, 1) 너무나도 많은 경고 메시지가 발생해서 사실상 쓸모없게 될 가능성이 높기 때문이며, (왜냐하면 bug가 있던 없던 최적화가 수많은 곳에서 일어날 것이기 때문에) 2) 사람들이 원하는 곳에서만 이러한 경고를 발생시키는 것은 까다로우며tricky 3) 결합된 최적화 기법들이 또다른 최적화가 가능한 기회를 제공하는 것에 대해, 사용자에게 알려줄 방법이 딱히 없기 때문입니다. 한 가지씩 좀 더 자세히 알아보면…

People often ask why the compiler doesn't produce warnings when it is taking advantage of undefined behavior to do an optimization, since any such case might actually be a bug in the user code. The challenges with this approach are that it is 1) likely to generate far too many warnings to be useful - because these optimizations kick in all the time when there is no bug, 2) it is really tricky to generate these warnings only when people want them, and 3) we have no good way to express (to the user) how a series of optimizations combined to expose the opportunity being optimized. Lets take each of these in turn:

  • It is "really hard" to make it actually useful

    예를 들어 설명하겠습니다. type 기반 alias analysis를 통해, 적절하지 않은invalid type casting bug를 찾아냈다고 하더라도, "optimizer가 P와 P[i]가 서로 참조하지alias 않는다고 간주했다"라고 경고를 발생하는 것이 별로 쓸모가 없을 수 있습니다. 예를 들어 Part 1에서 다룬 zero_array 함수를 다시 보겠습니다.

    float *P;
    
    void zero_array() {
      int i;
      for (i = 0; i < 10000; ++i)
        P[i] = 0.0f;
    }
    

    False positive 문제를 제외하더라도, optimizer가 합리적인 경고를 생성하기에 충분한 정보를 가지고 있지 않다는 문제가 있습니다. 무엇보다도 첫째, optimizer가 보는 코드는 이미 추상화된 코드already-abstract representation라서 (LLVM IR) C 언어 코드와 꽤 다르다는 것이며, 둘째, 컴파일러 내부는 상당히 많은 계층 구조를 가지고 있어서, optimizer가, P⁠에 대한 접근을 loop 밖으로 빼려고 하는 단계에서 TBAAType Based Alias Analysis가 pointer alias query를 해결하기 위해 쓰였다는 것을 알지 못합니다. 네. 사실 이건 컴파일러 개발자들의 불평이라고 치부하셔도 되지만, 상당히 해결하기 어려운 문제입니다.

  • It is hard to generate these warnings only when people want them

    /Clang/은 간단하거나 undefined behavior가 확실한 경우에 대해, 경고warning로 알려줍니다. 예를 들어 x << 421⁠과 같은 경우가 여기에 해당합니다. 이게 꽤 간단한 일로 보이지만, 사실은 어렵습니다. 왜냐하면, 사람들이 dead code에서 undefined behavior가 있다고 경고받는 것을 좋아하지 않기 때문입니다. (duplicate도 참고하기 바랍니다.)

    이 dead code에는 여러가지 형태가 있는데, 하나는 매크로 인자로 상수constant가 주어졌을 때 이상하게 확장된다는 불평이 있었습니다., 또, 특정 switch case⁠에 도달할 수 없는 것에 대해 경고가 필요하다는 요구도 있었습니다. 참고로, switch⁠에서 경고를 생성하려면 control flow analysis가 필요하기에 간단한 문제가 아닙니다. 엎친데 덮친 격으로, C 언어에서 switch⁠는 적절하게 쓰이지 않을 수도 있다는 점도 고려해야 합니다.

    이런 문제를 해결하기 위해, /Clang/은 runtime behavior wanring을 처리하기 위한 infrastructure를 두고, 이를 향상시키면서 경고를 발생시키게 하고, 만약 나중에 이 경고가 dead code에서 나왔다고 판단될 경우, 경고를 제거하는 방식을 쓰고 있습니다. This is something of an arms race with programmers though, because there are always idioms that we don't anticipate, and doing this sort of thing in the frontend means that it doesn't catch every case people would want it to catch.

  • Explaining a series of optimizations that exposed an opportunity

    컴파일러 frontend가 좋은 warning을 생성하게 하는 것이 힘들다면, optimizer가 생성하게 하면 어떨까요? 이 생각의 가장 큰 문제는 data tracking에 있습니다. 컴파일러 optimizer는 수많은 최적화 기법을 적용하려 하며, 각 단계에서 코드를 정규화canonicalize 하고, (바라건대) 더 빠른 코드를 생성할 것입니다. 예를 들어, inline 모듈이 함수를 inline하겠다고 결정했다면, 그 다음으로 inline으로 확장된 X*2/2⁠를 최적화하려고 할 것입니다.

    간단한 예로 설명하긴 했지만, 대부분의 최적화는 컴파일러가 수행하는 macro 확장instantiation, inline, 그리고 추상화 제거 작업에서 이루어집니다. 사실 프로그래머가 직접 불필요한 코드를 (예: X*2/2) 작성하는 것보다, 작성된 코드에서 컴파일러가 이런 작업을 수행하고 났더니, 불필요한 코드가 생성되는 것입니다. 실제 user의 code에 대해 경고를 생성하기 위해서는, 컴파일러가 어떤 과정을 통해 중간 단계의 코드를 생성해 냈는지 추적해야 하며, 다음과 같은 경고를 생성해야 할 수 있습니다:

    Warning: (잠재적으로 여러 파일과 Link Time 최적화까지 수행하고) 세 번의 inline 확장을 통해, common subexpression을 제거했고, 나머지 부분을 반복문 밖으로 뺐으며, 13개의 pointer가 서로 alias하지 않는 것을 확인했으며, 이 때, undefined behavior를 발견했습니다. 여러분의 코드에 버그가 있거나, 아니면 매크로 확장 또는 inline에 의해 생성된 코드에 버그가 있는데, 안쓰이는dead 코드라는 것을 증명할 수 없었습니다.

    Warning: after 3 levels of inlining (potentially across files with Link Time Optimization), some common subexpression elimination, after hoisting this thing out of a loop and proving that these 13 pointers don't alias, we found a case where you're doing something undefined. This could either be because there is a bug in your code, or because you have macros and inlining and the invalid code is dynamically unreachable but we can't prove that it is dead.

    안타깝지만, 간단히 말해, 우리는컴파일러 개발자 이런 경고를 생성하기에 충분한 코드 추적 infrastructure를 가지고 있지 않습니다. 설령 이런 것을 가지고 있더라도, 사용자에게 이런 정보를 제공하기에 충분한 user interface도 가지고 있지 않습니다.

    결과적으로, undefined behavior는 optimizer가 "이 operation은 올바른 것이 아니므로invalid 일어나지 않는다고 간주했다"라고 할 수 있기에 중요한 것입니다. 예를 들어, *P⁠와 같은 코드가 있을 때, optimizer는 이 코드를 보고, P⁠는 절대 NULL⁠일 수 없다고 간주할 수 있으며, 또, (constant propagation과 inline을 통해) *NULL⁠과 같은 코드를 봤을 때, 이 코드는 절대 도달할 수 없는unreachable 것으로 간주할 수 있다고 판단 할 수 있습니다.

    요점은, 컴파일러는 halting problem을 해결할 수 없으므로, 주어진 코드가 진짜 죽은, 쓰이지 않는dead 코드인지 (실제로 C 표준은 죽은 코드여야만 한다고 정의함), 아니면 여러 최적화 단계를 거친 이후 발견된 버그인지 알 방법이 없다는 것입니다. 이 두 가지를 구별할 좋은 방법이 없기 때문에, 대부분 경고들이 false positive (noise)인 것입니다.

Clang's Approach to Handling Undefined Behavior

현재 undefined behavior와 관련된 상황에서 Clang⁠과 LLVM⁠이 이런 상황을 개선하기 위해 무엇을 제공할 수 있느냐고 물으실 겁니다. 몇가지는 이미 제가 답변했으며: Clang Static Analyzer, Klee project, 그리고 -fcatch-undefined-behavior⁠가 있습니다. 다만 컴파일러만큼 널리 쓰이지는 않고 있기 때문에, 컴파일러에 이러한 기능을 추가하는 것이 훨씬 더 유용할 것이나, 컴파일러 자체는 동적 정보를 알 수 없으며, 컴파일 시간이라는 제약이 있다는 점을 아셔야 합니다.

Clang⁠은 이 문제 해결을 위한 첫 걸음으로, 다른 컴파일러들에 비해 훨씬 많은 경고를 default로 제공합니다. 일부 개발자들은 build할 때 -Wall -Wextra⁠를 쓰도록 훈련받았지만, 대바수는 이러한 옵션이 있는지도 모르며 알고 있다 하더라도 쓰지 않는 것이 현실이기 때문입니다. 좀 더 많은 경고를 하도록 하면 좀 더 많은 버그를 잡아낼 수 있습니다.

두번째로, Clang⁠은 (실수인 것이 ) 명백한, 여러 undefined behavior에 대해 (예를 들어 null dereference, oversized shift 등) 경고를 발생합니다. 이는 앞에서 다루었듯이 완벽하진 않지만, 실제로는 잘 쓰이고 있습니다.

세번째로, LLVM optimizer는 할 수 있는 것보다 훨씬 더 적은 범위의 undefined behavior를 쓰고 있습니다. 언어 표준은 "undefined behavior로 인하여 보장할 수 없는 일이 일어날 수 있다"고 하지만 현실적으로 쓸모있는 정보라고 할 수 없고, 개발자에게 도움이 되지도 않습니다. 대신 LLVM은 다음과 같이 조금 다른 방식으로 최적화를 수행합니다. (죄송하지만, 아래 링크??들은 C 언어 레벨이 아닌 LLVM IR 규칙을 다루고 있습니다.)

The third step is that the LLVM optimizer generally takes much less liberty with undefined behavior than it could. Though the standard says that any instance of undefined behavior has completely unbound effects on the program, this is not a particularly useful or developer friendly behavior to take advantage of. Instead, the LLVM optimizer handles these optimizations in a few different ways (the links describe rules of LLVM IR, not C, sorry!):

  1. Clang⁠은 특정 undefined behavior를 찾았을 때, 적절하다고 판단될 경우, 암암리에implicitly 예외적인trapping 연산으로 바꿉니다. 예를 들어 아래 C++ 함수는:
int *foo(long x) {
  return new int[x];
}

아래 X86-64 machine code로 변환됩니다:

__Z3fool:
	movl $4, %ecx
	movq %rdi, %rax
	mulq %rcx
	movq $-1, %rdi        # Set the size to -1 on overflow
	cmovnoq %rax, %rdi    # Which causes 'new' to throw std::bad_alloc
	jmp __Znam

GCC의 경우, 아래 machine code로 변환됩니다:

__Z3fool:
	salq $2, %rdi
	jmp __Znam             # Security bug on overflow!

우리(LLVM 측)는, buffer overflow나 프로그램에 심각한 결점exploit을 가져올 수 있는 심각한 integer overflow bug가 예상될 경우, 추가적인 (CPU) cycle을 투자해서, 이를 막는 것이 훨씬 더 낫다고 판단했기 때문에 위와 같은 차이가 있습니다. 어차피 new 연산자의 경우 꽤 비싼 연산이기 때문에, 추가된 overhead의 영향은 거의 느낄 수 없는 수준입니다. GCC 측은 이 문제를 적어도 2005년부터 알고 있었지만, 이 글을 쓰는 시점에도 고치지 않고 있습니다.

역자 주: GCC도 이제 이 기능을 가지고 있습니다. (Version 4.9.3에서 확인)

  1. undefined value를 다루는 사칙연산은 undefined behavior를 낳지 않고, undefined value를 낳도록 설계했습니다. 따라서 사칙 연산으로 인해 하드 디스크를 포맷하는 등의 undefined behavior는 발생하지 않습니다. 또한 이러한 사칙연산도, undefined value의 범위를 최소화하였습니다. 예를 들어 "undef & 1" 연산은 하위 1 bit만 undefined 값이며 나머지 bit들은 항상 0이 나오도록 만들었습니다. 따라서 LLVM으로 한정할 경우, ((undef & 1) >> 1)⁠은 undefined가 아니라 항상 0입니다.
  2. 동적으로 (signed integer overflow 등) undefined operation이 실행될 경우, logical trap value가 생성되며, 이는 이후 관련된 계산에 영향을 미치지만, 전체 프로그램을 망가트리지는 않습니다. 이런 이유로, optimizer는 초기화 되지 않은 변수를 사용하는 코드를 제거하게 됩니다.
  3. null 포인터를 통해 값을 저장하려 하거나 null pointer를 호출call하는 코드는 명백한obviously unreachable한 코드이기 때문에, 최적화 단계에서, 기존에는 이런 block들을 지워버렸습니다. (잘난 체하기 좋아하는 언어 학자 입장에서는) 이것이 매우 정상적인strictly true 것으로 보이지만, null pointer를 dereference하는 실수는 매우 자주 발견되며, 따라서 이 코드가 지워질 경우, 바로 다음 코드가 실행되는 것 때문에 이 버그를 발견하기가 매우 어렵다는 것을 깨달았습니다. 그래서 우리는 Clang⁠이 (이런 코드를 지우는 대신) __builtin_trap()⁠가 호출되도록 하여, 문제를 일으키는 코드가 바로 runtime trap을 일으키도록 바꿨습니다. 이 결정의 단점은 이러한 검사를 하는 부분과 trap을 일으키는 overhead가 있다는 점입니다.
  4. Optimizer는 프로그래머 의도를 파악할 수 있는 경우 (예를 들어 P⁠가 float⁠을 가리키는 pointer일 때, *(int *)P), 이를 프로그래머의 의도대로 처리하도록 했습니다. 여러 경우에 대해 이는 매우 도움이 되지만, 여기에 의존하는 것은 좋은 습관이 아닙니다. 그리고 여러 단계의 변환을 거친 경우, 당연히 동작해야 할 것 같지만, 그렇지 않은 경우가 많으므로 주의해야 합니다.
  5. 위에 해당하지 않는 경우, 즉, Part 1에서 다룬 zero_array⁠나 set/call 예제의 경우에는, 사용자에게 아무런 경고notification도 알리지 않고 최적화 됩니다. 그 이유는, 이 때 우리가 사용자에게 알려줄 쓸만한 정보도 없고, 또, 이런 최적화에 의해서 동작하는 (버그가 잠재되어 있는) 코드가 망가질broken 경우는 드물기 때문입니다.

우리가 개선할 수 있는 부분은 trap 추가에 관한 것입니다. Default로 off 이지만, 경고 옵션을 추가해서 trap instruction을 생성할 때마다 경고를 할 수 있다면 꽤 괜찮을 것이라 생각합니다. 어떤 코드에 대해서는 너무 의미없는 경고가 많이 발생할 수 있겠지만, 다른 코드에 대해서는 의미가 있을 수도 있으니까요. 이를 위해서는 optimizer가 경고를 발생시킬 수 있도록 수정되어야 할 것입니다. 현재로는 debugging 정보 추가 옵션이 on되어 있지 않는 한, 최적화 단계에서 소스 코드 위치를 알 방법도 없습니다. (수정될 가능성은 있음)

가장 어려운 부분은, 경고 단계에서 대상 코드가 (예를 들어) loop를 unrolling해서 나온 것인지, 네번의 함수 호출을 inline해서 나온 것인지 추적할 정보가 없다는 것입니다. 잘해봐야 우리가 할 수 있는 것은, 코드의 원래 위치, 즉 file/line/colum을 알려주는 것이며, 대부분 경우, 이 정보로도 충분하겠지만, 이 정보만으로도 부족할 수 있을 것입니다. 이런 기능은 우리가 해야 할 일 중에서 우선 순위가 낮은데, 첫째, 크게 쓸모있어 보이지도 않고, 둘째, default로 기능을 on할만한 것도 아니며, 세째, 꽤 많은 작업이 필요하기 때문입니다.

Using a Safer Dialect of C (and other options)

최고의 성능을 얻는 것에 큰 관심이 없다면, 여러가지 컴파일러 옵션을 써서 가능한 undefined behavior가 발생하지 않게 하면 됩니다. 예를 들어 -fwrapv 옵션을 쓰면 signed integer overflow에서 undefined behavior가 발생하지 않습니다. (그렇지만 이 옵션이 integer overflow로 인한 보안 문제를 해결해 주지는 않습니다). -fno-strict-aliasing 옵션을 쓰면 Type Based Alias Analysis를 끌disable 수 있습니다. 그래서 type 관련 규칙을 무시할 수 있습니다.

또, 사용자에게서 요청이 충분히 많다면, 우리가 Clang⁠에 옵션을 추가해서 모든 local variable을 0으로 초기화하는 옵션을 넣을 수도 있을 것이며, "and" 연산을 모든 shift 연산 앞에 추가하여 줄 수도 있습니다. 그렇다 하더라도 C 언어에서 undefined behavior를 완벽하게 제거하면서 ABI 호환성을 유지하고, 성능을 유지하는 것은 불가능합니다. 다른 관점에서 보면, 이 경우, 여러분은 C 언어를 쓰는 것이 아니라 portable하지 않은, C와 비슷한 언어를 쓰는 것이 되어 버릴 것입니다.

Portable하지 않는, C와 유사한 언어를 쓰는 것에 만족할 수 없을 경우, (앞에서 다룬 여러 툴들과 함께) -ftrapv, -fcatch-undefined-behavior 옵션을 debug build에서 쓰는 것이, 버그를 빨리 찾는데 도움이 됩니다. 또한 보안에 민감한 프로그램을 만든다면 release (production) 단계에서 이 옵션을 계속 쓰는 것도 의미가 있습니다. 이 옵션들이 모든 버그를 잡아 줄 수는 없지만, 일부는 잡을 수 있을 것입니다.

결과적으로, 가장 근본적인 문제는, (인기가 매우 많음에도) C 언어가 안전한safe 언어가 아니며, 많은 사람들이 언어가 어떻게 동작하는지 정확히 이해하고 있지 않다라는 것입니다. 1989년 C 언어 표준이 제정되기 전에, C 언어는 "PDP Assembly 언어를 가볍게 wrapping한 저수준 시스템 프로그래밍 언어"이었다면, 거기서 발전해서 현재 "대부분 사람의 예상을 (좋지 않은 방향으로) 깨트리면서, 우수한 성능을 내는 저수준 시스템 프로그래밍 언어"가 되었습니다. 달리 말하면, 대부분 사람의 기대를 저버리면서까지 성능에 집착한 언어이며, 이로 인해 정말 어려운 시기에 사람들의 뒤통수를 치는 언어가 되었습니다.

마지막으로, C 언어는 매우 놀라운 성능을 보여주는, portable한 assembler 그 이상입니다. 지금까지 내용이 (적어도 컴파일러 개발자 입장에서 ) C 언어에서 undefined behavior와 그 이면을 보여주는데 도움이 되었으면 합니다.

Starting blog again with Nikola

More than 2 years, I haven't updated my site. To say long story short, I was in UK for more than one years, and unable to set up my desktop machine, which has all the sources of my site, left in a luggage during in UK. Recently, I moved to the Bay area in US, and finally set up the old desktop again, and replace the site generator from Jekyll to Nikola.

Jekyll was great, however, it requires too many modification for my need, since my site requires some static pages plus blog entries, and I wrote all my posts in Org-mode, which was not supported by Jekyll so I had to come up with my own solution that convert .org files to .html files using Emacs myself, and insert YAML configuration to all of them, and uses Jekyll to generate the final output.

Now, I read a very interesting article, Blogging in org-mode with Nikola, which introduced Nikola to me, and I decided to experiment with it. After few hours of experimentation, I was really surprised as it contains everything that I imagined before!

  • org mode support using Emacs instead of custom converter.
  • RSS feed by default
  • support for non-blog site
  • Disqus integration.
  • support for multi-lingual site

I dare to say, (for my own need at least), Nikola is better than vanilla Jekyll, and still better than Octopress.

Of course, there are some problems that I found already, but they are minor enough. Hopefully, I may explain those in another post.

Anyway, here I am, restarted the blog again. Hope that I can find many interesting topics soon.

Remove a node from a linked list in almost O(1)

struct node {
  int data;
  /* ... */
  struct node *next;
};
typedef struct node NODE;

Suppose that we have a singular list of NODE or a circular list of NODE⁠. To remove a node from the list, we'd like to implement following function:

/* Remove NPTR from the list pointed by HEAD, and return it. */
NODE *list_extract(NODE **head, NODE *nptr);

The node that we need to extract from the list is pointed by nptr⁠. So we need to make sure that the next field of the node before nptr should point the node after nptr⁠. One way to find the previous node is to iterate all nodes from head to find the node whose next field is the node pointed by nptr⁠:

NODE *before;
for (before = head; before != 0; before = before->next)
  if (before->next == nptr)
    break;

However, it may not be so efficient to traverse lots of node before nptr if the list is very very long. There is another way to extract a node from a list without iterating the list to find the previous node.

head           nptr
[10] -> ... -> A:[12] -> B:[34] -> ...

Suppose we have a list like the above. head and nptr is the pointer to the head of the node and the node that needs to be extracted respectively. Let the node points by nptr is node A, and the next node of node A is node B. Node A has an integral data, 12, and node =⁠B= has 34⁠.

Instead of finding the node before nptr⁠, we like to swap the contents of the node A and node B. To do that, I'll introduce a temporary node, T⁠, and copy the contents of node =⁠A= into it.

head           nptr
[10] -> ... -> A:[12] -> B:[34] -> ...

                           ^
                           |
               T:[12] -----+

Note that we copied every fields of node A into node T⁠, so =⁠next= field of node T also points the same node as node A points. Then, we copy all fields of node B into node A:

head           nptr
[10] -> ... -> A:[34] -------------+
                                   |
                                   V
               T:[12] -> B:[34] -> ...

Then, we copy all fields of node T into node B⁠:

head           nptr
[10] -> ... -> A:[34] -----------> ...

                            +----+
                            |    |
                            V    |
               T:[12] -> B:[12] -+

Since we copyied next field from node =⁠T= to node B⁠, node =⁠B= turns to be a circular list of its own node, which we don't intent. So set next field of node B to NULL⁠.

head           nptr
[10] -> ... -> A:[34] -----------> ...

               T:[12] -> B:[12] -|

Now the node that we wanted to extracted is copyied to node B, which is accessible by next field of node T. And the list has successfully removed the contents of node pointed by nptr⁠.

However, when the target nptr is the last node, we cannot use this trick since there is no next node. In that case, we use the well known solution, to iterate all nodes to find the previous node.

The full source code of list_extract() is here:

NODE *
list_extract(NODE **head, NODE *nptr)
{
  NODE t;
  NODE *prev;

  if (*head == nptr) {
    if (nptr->next == NULL) {
      *head = 0;
      return nptr;
    }
    else {
      *head = nptr->next;
      nptr->next = NULL;
      return nptr;
    }
  }

  if (nptr->next) {
    memcpy(&t, nptr, sizeof(t));
    memcpy(nptr, nptr->next, sizeof(t));
    memcpy(t.next, &t, sizeof(t));
    t.next->next = 0;
    return t.next;
  }

  for (prev = *head; prev != NULL; prev = prev->next) {
    if (prev->next == nptr)
      break;
  }
  if (!prev)
    return 0;

  prev->next = nptr->next;
  nptr->next = 0;

  return nptr;
}

And the time complexity will be:

\begin{eqnarray} O(f(n)) & = & \left\{ \begin{array}{l l} O(1) & \quad \text{ if $nptr$ is the head} \\ O(n - 1) & \quad \text{ if $nptr$ is the last} \\ O(1) & \quad \text{ the rest } \\ \end{array} \right. \\ &=& \frac{1}{n}O(1) + \frac{1}{n}O(n-1) + \frac{n - 2}{n}O(1) \\ &=& \frac{n - 1}{n}O(1) + \frac{1}{n}O(n) \\ &\cong& O(1) \quad \text{ if $n$ is relatively large } \end{eqnarray}

Detect staled NFS mount

Check stale NFS

Here's a simple script to check whether the given directory (NFS mount point) is stale.

There are three points that needs some explanation here.

First, since any command that access the NFS file system would block (unresponsive) iff the NFS is stale, I am using read -t N for the timeout.

Second, I used process substitution feature of bash, <(list) form. Basically, read -t 1 < <(...) will timeout after 1 second unless =⁠…= part finished within the timeout. bash will create a new subshell to execute /⁠list/ in <(list) form. The problem is, if any of list will access the stale NFS, the command will hang, which makes the subshell also will hang. Even if the calling shell script finished, the subshell would not terminated, leaving the process in interruptible sleep state.

To prevent this, I recorded the sub-shell PID using $BASHPID in <(list) form. After =⁠read= command, I deleted all possible children of the subshell and the subshell itself. Note that using $$ won't work in <(list) form. =⁠$$= represents the mother shell's PID, not the sub-shell's.

SSH wrapper to connect Scalr-managed servers

It's annoying to connect one of the virtual machine managed by Scalr for various reasons. So I created small shell script for easy connection; browse the servers with its IP address, then connect to them.

Backgrounds

We created lots of Scalr managed servers. Some of them have external IP addresses, but some of them are not. So, we need to prepare a proxy machine, to connect those servers.

<pre>

Internet Firewall Cloud IaaS

--------- -----—+ ---------

Client   Proxy   Target
Machine   Server   Server
  ----–—>   ---–—>  
         
         

--------- -----—+ --------- 53.208.160.176 10.102.9.203

</pre>

For example, suppose that we've prepared the proxy machine at 53.208.160.176. Normally, you could connect to the destination server 10.102.9.203 by issuing ssh twice, like this (which is annoying):

$ ssh 53.208.160.176
$ ssh 10.102.9.203

We are using Scalr's auto-scaling feature; this means, the number of servers are dynamically increasing/decreasing depending on the server's load. In other words, at some instance, we do not exactly know how many servers are there, and we do not exactly know what IP addresses they have.

So, I created small shell script named sssh (stands for "Scalr-ssh") to find out the list of Scalr-managed servers, and provide easy ssh connection to one of the servers. With this, you can connect a server instantly even if the server does not have external IP address.

Download & Installation

First, you'll need to download the Scalr command line tool from Scalr Command Line Tools, and you'll need to finish scalr configure step.

$ sudo easy_install scalr
$ scalr configure -i d41d8cd98f00b204 \
    -a 3bEGXWzaoT92BMhOaqv13bEGXWzaoT92BMhOaqv13bEGXWzaoT92BMhOaqv1+0=

Above example will save your configuration in $HOME/.scalr/config.ini.

Then, you'll need to grab the source from here, and save it to some place like /usr/local/bin. Then, edit that file to update the proxy endpoint in SSH_PROXY_ENDPOINT to reflect your proxy endpoint. For example:

SSH_PROXY_ENDPOINT=${SSH_PROXY_ENDPOINT:="root@53.208.160.176}

You can test whether the installation was successful via following command. Note that the actual output may vary depending on your Scalr configuration/usage.

$ sssh env
  [149]  AWS-TEST-ENV
  [158]  US-EAST-9
  [161]  AP-KR-FOOBAR

Usage

If you have more than one Scalr environment, you'll need to list the environments using sssh env, then select one of the environment with the following command:

$ # select environment with id, 158
$ sssh set-env 158

Then, you'll need to select one of your farms. First, list the farms using sssh farms, then select one of it using sssh set-farm:

$ # list the farms
$ sssh farms
  [808]                          test-vpc (Stopped):   VPC farm for testing
  [809]      ec2-us-east-1-management-dev (Running):   None
  [814]           ec2-us-east-2-store-dev (Stopped):   None
  [953]                template-test-farm (Running):   None
$ # select one of the farm
$ sssh set-farm 809

Once the env/farm is selected, then you can browse the list of servers by sssh list:

$ sssh list
  [ 0]   53.208.160.176    10.102.9.174  proxy-server
  [ 1]      53.84.9.110    10.102.9.135  zookeeper-3-centos6-cl
  [ 2]     53.84.76.146    10.102.9.146  zookeeper-3-centos6-cl
  [ 3]     53.84.65.212      10.102.9.7  zookeeper-3-centos6-cl
  [ 4]             None    10.102.9.203  sessionmgr-master-centos6-cl
  [ 5]     53.84.72.223    10.102.9.132  cs-sessionmgr-master-centos6-cl
  [ 6]     53.84.74.122     10.102.9.52  cs-sessionmgr-master-centos6-cl
  [ 7]     53.84.64.155    10.102.9.112  cs-frontend-centos6-cl
  [ 8]       53.84.0.88    10.102.9.106  cs-frontend-centos6-cl
  [ 9]             None    10.102.3.210  cs-datastore-centos6-cl

Each item contains 4 fields: the server index, the external IP, the internal IP, and the name of the server. In above example, 4th and 9th server do not have external IP. Remember that we configured SSH_PROXY_ENDPOINT to point 0-th server endpoint, "root@53.208.160.176". This server is used for the ssh proxy for this demonstration.

These servers belong to the farm id, 809 as we selected this farm using sssh set-farm 809. To connect one of these servers, you need to download the PEM file of this farm, and place it in your $HOME/.ssh/809.pem. Finally, you can connect to one of the servers by following command:

$ # connect to 1st server
$ sssh connect 1
Last login: Tue Feb 11 05:32:28 2014 from 124.168.108.138

Appliance:	centos-6-scalr appliance 1.0
Hostname:	ip-10-102-9-135
IP Address:	10.102.9.135

[root@ec2-53-84-9-110 ~]# _

You can even connect to the server without external IP. For example:

$ # connect to 9th server
$ sssh connect 9
Last login: Wed Feb 12 09:04:02 2014 from 10.102.9.174

Appliance:	centos-6-scalr appliance 1.0
Hostname:	ip-10-102-9-210
IP Address:	10.102.9.210

[root@ip-10-101-3-210 ~]# _

Note that from the first message of the command; it says that the connection was from 10.102.9.174, which is the internal IP address of the 0-th server, which is used for the ssh proxy.

Internally, when we specify a server without external IP address, sssh will indirectly connect to the server via the pre-configured ssh proxy server using ssh ProxyCommand option with netcat(1):

ssh -i "$pem" -o "ProxyCommand ssh -i $pem $SSH_PROXY_ENDPOINT nc %h %p" root@${iip}

If you have interest on this, read the nice article Configure openssh to tunnel through another server using SSH.

Easy way to resize/select windows or frames of Emacs

Window/Frame Selection

When you're using Emacs in a graphic display (That is, not in a console nor a terminal), you'll have multiple Emacs frames and windows in them.

The default navigation interface of Emacs is quite surprising to the non Emacs users since Emacs provides relative selection machanism.

For example, suppose you have following Emacs frames and windows:

<pre>
+-Frame A------------+   +-Frame B------------+   +-Frame C------------+
|                    |   |                    |   |                    |
| Window A           |   | Window C           |   | Window F           |
|                    |   |                    |   |                    |
|                    |   +--------------------+   |                    |
|                    |   |                    |   |                    |
+--------------------+   | Window D           |   |                    |
|                    |   |                    |   |                    |
| Window B           |   |                    |   |                    |
|                    |   +--------------------+   |                    |
|                    |   |                    |   |                    |
|                    |   | Window E           |   |                    |
+--------------------+   +--------------------+   +--------------------+
</pre>

Emacs provides basic frame selection and window selection commands; other-frame and other-window. They select the next frame or next window from the list in cyclic order. The problem is, the default order may not reflect the coordinates of the frame/window, especially when you moved some frames/windows.

Suppose that the currently selected frame is Frame B in above figure. If Emacs kept the frame list in (Frame#B Frame#A Frame#C), the next frame would be Frame A. Of course, by using negative prefix argument to other-frame function, you can select the previous frame if you want.

What I want is, to select a frame in the order of the actual coordinate of the frames. That is, I want to give a command something like, "select the frame where its X coordinate is the closest to the origin.", or "select the frame where its X coordinate is the second closest to the origin.".

So I made a simple function, wfu/frame-list-ordered, to return an ordered list of frames. Similarly, I made another function, wfu/window-list-ordered, to return an ordered list of windows. Using these two functions, I made two commands; wfu/other-frame-or-window and wfu/other-window-or-frame. wfu/other-frame-or-window will select other(next) frame. If there is no other frame, it will select other(next) window. Similarly, wfu/other-window-or-frame will select other(next) window. If there is no other window, it will select other(next) frame.

Binding a key shortcut to an Emacs command is treaky thing. Since you don't know that whether you can easily memorize new keybindings. Anyway, I found following key sequences are best for my personal use:

Keys Description
C-<tab> bound to wfu/other-window-or-frame, it selects the next window of the current frame.
C-N C-<tab> Select the N-th window of the current frame.
C-- C-N C-<tab> Select the N-th frame.
C-x o bound to wfu/other-frame-or-window, it selects the next frame.

N is the number between 0 and 9. Note first window/frame starts from 1, not 0.

Normally, I just stick to C-<tab> to select other window. When I want to select other frame, I'll feed it a negative number; where the absolute value of the number denotes the N-th frame.

Source

You may download wfutils.el from the github.

A script to create Redis Cluster using GNU screen(1)

Easy way to setup the local redis replication using GNU screen(1)

One of my reponsibility is to write easy client library for Redis in C and Java. There are already well-known client C library, hiredis and Java library, jedis. At the time of development, none of these support our Redis replication cluster. I'll write later about the client libraries that support replication.

Anyway, during the development, I need to launch simple redis cluster, which consists of 1 master and 2 slaves. It is tiresome job to setup the configuration of master and slaves, and it is very likely to commit a mistake.

Thus, I wrote a small shell script (called redis-replica.sh) to launch redis cluster locally. Internally, it uses GNU screen to create multiple shell to launch required processes:

shell no. description
0 redis-sentinel, listening 26379
1 redis monitor to the sentinel
2 redis-cli to the sentinel
3 redis-server master, listening 6379
4 redis monitor to the master
5 redis-cli to the master
6 redis-server slave#1, listening 6380
7 redis monitor to the slave#1
8 redis-cli to the slave#1
9 redis-server slave#2, listening 6381
10 redis monitor to the slave#2
11 redis-cli to the slave#2

Since the master and slaves are managed by the sentinel process, if you shutdown the master, one of the slaves will be promoted to new master.

This way, you can easily experiment and test your client software or libraries.

Here is the source code of redis-replica.sh:

How I measured Emacs init script performance

Background

How did I load lots of init scripts?

If you're like me, you have a lot of elisp files for your Emacs configuration. Without considering unmaintained code or junk codes, I have almost 80 elisp files in my $HOME/.emacs.d/. This causes Emacs launching slower and slower. Normally, I don't turn-off my computer, nor I need to launch Emacs frequently. So it was not big deal.

However, sometimes it took more than 7 seconds to launch Emacs on my idle Gentoo machine. Why it took so much time before starting? Which file is the time-consuming monster? Unfortunately, I couldn't answer.

So I tried to clean-up my configurations. First, I remove all unused junk from my $HOME/.emacs.d/init.el. Even after that, my init file was too big to maintain easily. So I modulize the init file into separate code pieces. Now, there is just a small init.el, and lots of code pieces reside in $HOME/.emacs.d/init/. For example, my customization for dired package is stored in $HOME/.emacs.d/init/dired.el, and Korean language customization is stored in $HOME/.emacs.d/init/dired.el, and so on.

After that, I wrote simple macro, which loads the init code pieces from the specified directory, $HOME/.emacs.d/init/, if it was not loaded before, much like Emacs's require function.

(uinit/load "korean" enable-multibyte-characters)

You can interpret above code as "If enable-multibyte-characters is not nil, load $HOME/.emacs.d/init/korean.el, if it was not loaded before."

In detail, uinit/load function will search whether the given code piece (e.g. Korean.el in above) is loaded before, by searching the list uinit/loaded-init-files. Then if it does not exists, it call call load function to load the file. It also record the duration time of loading the piece, and save it in to the report buffer, "*uinit*".

After my init.el is loaded by Emacs, it will repeatedly call uinit/load to load lots of init code pieces, saving the timing of loading in "*uinit*" buffer. In the end of init.el file, I call uinit/summarize so that it will sort *uinit* buffer by the consumed time, and wrote the total amount of time to load my init code pieces. Here's the screenshot of *uinit* buffer:

nil

Usage

You can grab the source of uinit package from here.

Your emacs init script ($HOME/.emacs or $HOME/.emacs.d/init.el) modifies load-path, You must set load-path before using any of function in uinit because uinit will try to byte compile your init pieces on load. Otherwise byte compilation will fail. Especially, if you're using package, try to call (package-initialize) before loading uinit. For example:

(when (locate-library "package")
  (require 'package)
  (package-initialize))

(setq uinit/init-directory "~/.emacs.d/init")
(require 'uinit)

Then, you're free to call uinit/load to load your init code pieces. (Your init code pieces should be placed in uinit/init-directory.) For example:

(uinit/load "darwin" (eq system-type 'darwin))
(uinit/load "X" (eq window-system 'x))

Finally, add following code in the end of your init.

(uinit/summarize)

A dirty macro that convert the scala type to string type in binary representation

Handy function that convert the scala type to string type in C. This is a not-portable GCC macro to produce binary-represented string in C or C++.

Sometimes, it is useful to have a way to print a scala value in a binary representation. Unfortunately, there is no such format specifier for printf(3). Luckily, glibc has a customization feature for printf(3)-like functions. If you're interested in, read the code here. For example, you could write:

int i = 0xdeadbeef;
printf("%b\n", i);      /* print 11011110101011011011111011101111 */

If you're not using glibc, you could create some utility functions to do this. Here're some candidate function prototypes:

/* return the binary represented string of VALUE.  The width
 * of the string is CHAR_BIT * size.  The return value should
 * be free(3)ed after use. */
char *binstr(unsigned long long value, size_t size);

/* store the binary representation of VALUE in string pointed by BUF
 * with the size SIZE.  */
char *binstr(unsigned long long value, char *buf, size_t size);

I'm not satisfied with these. The first one, which returns a value that is dynamically allocated, looks heavy. Plus, the caller should supply the number of binary digit, since it always accept the value as unsigned long long. The second one, which works only when the user provided the buffer as in the second and the third parameters. It does not look heavy, but probably someone may be not happy with it, since the user always need to prepare the buffer.

I couldn't come up with a everybody-satisified solution with this.

Since most of my works are done in Linux and MacOS; both provides GCC, so I decided to drop the portability. :)

#define binstr(x)       ({ char *p = alloca(sizeof(x) * CHAR_BIT + 1);  \
      char *q = p + sizeof(x) * CHAR_BIT;                               \
      *q-- = '\0';                                                      \
      int i;                                                            \
      typeof(x) tmp = (x);                                              \
      for (i = 0; i < sizeof(x) * CHAR_BIT; i++) {                      \
	*q-- = (tmp & 1) ? '1' : '0';                                   \
	tmp >>= 1;                                                      \
      }                                                                 \
      q + 1;                                                            \
    })
  • I'm using alloca(3), instead of malloc(3), so that the memory buffer should be freed automatically. The caller no longer need to call free(3).
  • To decide the right number of digits of the value type, binstr is a macro function.
  • I used statement expression, ({…}) (GCC extension), which allows me to declare local variables.
  • I used typeof operator (GCC extension), which allows to declare a local variable, that has the same type as the parameter.

How I kill a process with suspicious TCP CLOSE_WAIT

During our server-side application development, we encontered a lot of connections are in CLOSEWAIT state, so that our server process is out of file descriptors. We are in the middle of development of a client application that runs in the mobile androids, and the server-side application that runs in a cloud infrastrure.

I'm in the server-side team, and our team is focusing on the development of server-side. Our server-side have multiple front-end server that expose the interface for the clients. Front-end servers are like load-balancers, they dispatch the client requests to the one of the several back-end workers. Since we're in the middle of the development, our front-end servers and back-end servers have a couple of bugs in them. They sometimes made the server crash, even hang unpredictively.

Unfortunately, while we were tring to stablize our server applications, the client team needed a prototype server cluster, so that they can develop their client application and test the interaction between client and the front-end. Personally, I don't want to provide our prototype servers to the client team until the server-side is stablized, but the client team also need to hurry, to meet the dead-line, so we have no choice but to provide them still-unstable-servers.

The biggest problem was, the server application leaves CLOSE_WAIT state TCP connections on unexpected network situation. So, after a couple of hours, the server process ran out of file descriptors, denying client requests. Since we use sophiscated third-party network library, it would take some times to fix the problem.

So, I need some kind of watchdog, which periodically check whether the server process leaves CLOSE_WAIT connections, and kill them, leave some logs, and so on. Our server application is managed by init(1) like launcher, so when the server processes are terminated, the launcher automatically raise them.

Implementation

I was in hurry to implement this wachdog program, so I decided to write small bash script, but later changed to Ruby script. Fortunately, all of our servers already have Ruby 1.8 installed.

At some time slice, the output of the netstat(1) would like this:

$ netstat -ntp
...
tcp  0  0  10.149.8.221:46271  54.235.151.255:6379  ESTABLISHED 16125/fe-server
tcp  0  0  10.149.8.221:46283  54.235.151.255:6379  ESTABLISHED 16118/fe-server          
tcp  0  0  10.149.8.221:46267  54.235.151.255:6379  ESTABLISHED 16120/fe-server          
tcp  0  0  10.149.8.221:35250  10.158.95.68:58964   CLOSE_WAIT  16063/fe-server   
tcp  0  0  10.149.8.221:43557  10.147.191.96:52421  ESTABLISHED 16063/fe-server
tcp  0  0  10.149.8.221:8010   107.22.161.62:37126  CLOSE_WAIT  -
...
$ _

The netstat(1) from net-tools, accept -n option, indicates to use numerical addresses and ports, -t options indicates to show only TCP connections, and -p options to show the related PID and program names.

It looks trival to catch the PID of the process that has one or more CLOSE_WAIT connections. One thing to keep in mind is, netstat(1) sometimes displays "-" in the PID/PROGRAM field. I don't have enough time when netstat(1) shows "-", but fortunately, fuser(1) can identify the owner PID of the connection.

$ fuser -n tcp 8010
35250/tcp:           16063
$ fuser -n tcp 8010 2>/dev/null
 16063$_

My first implementation was, just simply count the number of CLOSE_WAIT connections per process, and kill(1) $PID if the process has more than N CLOSE_WAIT connections.

The limitation of the first implementation is, it may kill the process with CLOSE_WAIT connection that the process just about to close(2) it.

So the second implementation work like this:

  1. save the connection information (source address:port, destination address:port) per process as a set-like container
  2. Wait for certain amount of the time
  3. save the connection information again, in another set-like container.
  4. Get the intersection of the two set.
  5. If the number of elements in the intersection exceeds N, kill the process.

I couldn't come up with a good implementation of set-like container in bash(1), so I re-implement from the scratch with ruby(1).

After few hours, another problem arised. Some server processes, goes coma, and does not adhere to SIGTERM. We can only kill them with SIGKILL, so I modified the killing line like this:

kill $pid; sleep 2; kill -0 $pid && kill -9 $pid

This line, first send SIGTERM to the $pid, then sleep for 2 seconds, and if it still can send a signal to the process (in other words, if the process is still alive), send SIGKILL to the $pid.

Usage

I named the script, resreap. The reason was, we call our server processes as resources, so it stands for 'RESource REAPer'. The full source code is available from here.

With some extra features, my script, called resreap, can accept following options:

$ ./resreap --help
Kill processes that have enough CLOSE_WAIT socket(s)
Usage: resreap [OPTION...]

    -f PAT        Kill only processes whose command matches PAT
    -F HOST:PORT  Ignore if foreign endpoint matches to HOST:PORT
		  HOST should be in IPv4 numerical notation.

    -l N          If a process has more than or equal to N CLOSE_WAIT
		  socket(s), it will be killed with a signal
		  (default: 2)

    -i N          Set sleep interval between checks in seconds
		  (default: 2)

    -c CMD        Before sending a signal, execute CMD in the shell,
		  If this CMD returns non-zero returns, the process
		  will not receive any signal.

    -s SIG        Set the signal name (e.g. TERM) that will be send
		  to a process (default: TERM)
    -w SEC        Set the waiting time in seconds between the signal and
		  SIGKILL (default: 2)

    -d            dry run, no kill
    -D            debug mode

    -h            show this poor help messages and exit
    -v            show version information and exit

Note that if a process receives the signal, and the process is alive
for 2 second(s), the process will receive SIGKILL.

If you are going to use "-f" option, I recommend to try "-d -D" option
first.  If you get the pid of the culprit process, try to get the
command name by "ps -p PID -o command=" where PID is the pid of that
process.

You could send two signal(s) before sending SIGKILL using '-S' option.
This can be useful since some JVM print stacktrace on SIGQUIT.

$ _

For example, if you want to kill a process if it has more than 2 CLOSE_WAIT connections, and you only care for java program, then you can do:

$ ./resreap -l 2 -f ^java

Plus, if you want to ignore CLOSE_WAIT connection on 127.0.0.1:2049, you could do:

$ ./resreap -F 127.0.0.1:2049

I really hope that we don't need to use this awful script for our servers. :)