[입 개발] SipHash의 사용, Data DDOS를 방지해볼까?

Python 3.3 부터는 내장 hash 함수가 RANDOM SEED를 이용하는 방식으로 바뀌었고, 내부 함수도 내부적으로 SipHash 를 쓰도록 바뀌었고, Redis 에서도 4.x 부터는 내부 해쉬 방식이 SipHash 를 쓰는 것으로 바뀌었습니다.

그러면 잘 쓰고 있던(?) 기존의 hash를 왜 siphash라는 구조로 바꾸는 것일가요? 아, 일단 먼저 고백할 것은 전 siphash 가 뭔지는 잘 모릅니다. siphash 홈페이지를 방문하면 다음과 같은 내용을 볼 수 있습니다.

SipHash is a family of pseudorandom functions (a.k.a. keyed hash functions) optimized for speed on short messages.

Target applications include network traffic authentication and defense against hash-flooding DoS attacks.

SipHash is secure, fast, and simple (for real):
SipHash is simpler and faster than previous cryptographic algorithms (e.g. MACs based on universal hashing)
SipHash is competitive in performance with insecure non-cryptographic algorithms (e.g. MurmurHash)
We propose that hash tables switch to SipHash as a hash function. Users of SipHash already include FreeBSD, OpenDNS, Perl 5, Ruby, or Rust.

The original SipHash returns 64-bit strings. A version returning 128-bit strings was later created, based on demand from users.

Intellectual property: We aren’t aware of any patents or patent applications relevant to SipHash, and we aren’t planning to apply for any. The reference code of SipHash is released under CC0 license, a public domain-like license.

뭔지 잘 모르겠지만, 자애로운 구글신을 영접하면 다음과 같이 번역되어 나옵니다.(아휴… 이제 번역은 구글느님이시죠.)

SipHash는 단문 메시지의 속도에 최적화 된 의사 난수 함수 (a.k.a. 키 해시 함수)의 계열입니다.

대상 응용 프로그램에는 네트워크 트래픽 인증 및 해시 넘침 DoS 공격 방어가 포함됩니다.

SipHash는 안전하고 빠르며 간단합니다 (실제).
SipHash는 이전의 암호화 알고리즘 (예 : 범용 해시 기반의 MAC)보다 간단하고 빠릅니다.
SipHash는 안전하지 않은 비 암호화 알고리즘 (예 : MurmurHash)
우리는 해시 테이블을 해시 함수로 SipHash로 전환 할 것을 제안합니다. SipHash 사용자는 이미 FreeBSD, OpenDNS, Perl 5, Ruby 또는 Rust를 포함합니다.

원래 SipHash는 64 비트 문자열을 반환합니다. 128 비트 문자열을 반환하는 버전이 나중에 사용자의 요구에 따라 만들어졌습니다.

지적 재산권 : 우리는 SipHash와 관련된 특허 또는 특허 출원을 모르고 있으며, 신청할 계획이 없습니다. SipHash의 참조 코드는 공개 도메인과 같은 라이센스 인 CC0 라이센스에 따라 릴리스됩니다.

그럼 왜 이런걸 사용하는가라고 한다면, 다음과 같은 예를 하나 들어보려고 합니다. Java 7이나 .NET의 Set 자료구조를 보면, 실제로 내부에는 Hash 자료구조를 사용하고 있습니다.(당연하지!!! 그것도 몰랐냐 이넘아 하시면… 전… 굽신굽신) Set이라는 자료구조는 특정 item 이 존재하는지 아닌지를 상수시간(이라고 적고 빠른 시간에) 확인할 수 있는 자료구조입니다. 그런데 Hash는 보통 충돌이라고 불리는 Hash 값이 겹칠 수 밖에 없는 경우가 존재하고 이를 막기 위해서, 링크드 리스트를 이용한 이중 체인 같은 것을 많이 사용합니다.

즉 다음 그림과 같은 구조가 됩니다. 일단 다음 그림은 아주 이상적으로 Hash 가 하나씩 차지한 경우이구요.
siphash1

다음은 이제 삐꾸가 나서 한 hash slot 에만 비정상적으로 몰리는 경우입니다.
siphash2

그런데 지금 이러한 내용을 왜 말하는가 하면, 이런 특성을 이용해서 특정 서비스에 DOS(Denial of Service) 서비스를 할 수 있다는 것입니다.(아니 자네, 지금 무슨 말을 하는 것인가?)

우리가 흔히 아는 DOS 또는 DDOS는 무수한 클라이언트를 이용해서, 특정 사이트에 접속을 시도하거나 해서, 서비스를 못할 정도로 네트웍을 사용하거나, 특정 서비스에 시간이 오래걸리는 무거운 작업을 하도록 하여서, 서비스를 하지 못하게 하는 공격입니다.

자, 여기서 힌트를 얻으신 분들이 있으실지도 모르겠습니다. 앞에서 말한 Hash를 바꾼 이유와, 시간이 오래걸리는 무거운 작업을 하도록 한다를 섞으면… 설마라고 생각하시는 분들이 계실텐데… 넵 바로 그 이유입니다.(전 사실 그 이유를 모르죠!!! 퍽퍽퍽…)

자, 만약에 특정 사이트에서 어떤 컴포넌트를 이용하는 걸 알고 있습니다. 그리고 그 툴에서 자료구조를 어떻게 처리하는 지도 안다면? 예를 들어, Java 7의 Set 이나 HashMap 을 사용하는 걸 알고, 거기에 데이터를 넣을 것이라는 걸 안다면…(오픈소스들이 위험할 수 있습니다.) 특정 패턴의 Key를 넣는 것으로, Hash 검색 속도를 미친듯이 느리게 만들 수 있습니다.

한 곳에 데이터가 몰리는 것을 skew 라고 하고 이진 트리등에서도 skew 가 되면 엄청 느린 검색 속도를 보여주게 되는데.. 위의 그림 처럼, 충돌이 일어날 경우에 linked list를 이용한 체이닝으로 문제를 푼다면, 거기에만, 천개, 만개, 십만개가 있다면, 이제 해당 슬롯에 있는 key를 조회하는 명령이 들어오면, 속도는 점점 느려지게 될 것입니다.(정말?)

먼저 java7 에서의 HashMap에서 hash 함수를 확인해보도록 하겠습니다.(왜 자바7이냐 하면 자바8에서는 HashMap이 충돌시에 Tree 형태로 저장되게 됩니다. – 그러나 이것도 효율적이긴 하지만, 정말 많은 데이터를 한 곳에 넣으면… 문제의 소지가!!!)

java7 에서의 HashMap 에서 사용하는 hash 함수는 다음과 같습니다.

    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

hash(key.hashCode()) 이런식으로 이용하게 되는데 만약에 key가 string class의 경우 hashCode() 함수는 다음과 같습니다.

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

즉 특정 string 의 hash table의 위치는 항상 그대로 입니다. 이걸 이용해서 같은 해쉬 슬롯에 들어가는 데이터를 대량으로 던져준다면?(사실 이게 쉽지는 않습니다., 어떤 key를 추가하게 할 것인가라는게 사용자 입장에서는 접근할 여지가 적은… 하지만… 가능하다면?) 물론 java7에서도 아이템 개수가 커지면 Table을 키우게 되긴 합니다만… 이것 역시 동일한게 만들어주면… 사실 더 최악인 메모리는 계속 팩터 만큼 커지는데… 아이템은 계속 같은 곳에 몰리는 형상이 벌어질 수 있습니다.(이걸 의도한 공격이죠.)

실제로 java7 에서는 resize(), transfer() 함수가 테이블 확장을 하게됩니다.

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

그럼 siphash를 쓰면 어떤 부분에서 도움이 될까요? 위에서 보여준 java7에서의 hash 나 python의 기존방식이나, redis 3.x대의 hash 또는 MD5, SHA1, SHA256 계열의 경우, 우리가 알듯이 항상 특정 key 의 hash는 같은 알고리즘에서 항상 같은 결과가 나옵니다.(consistent hashing 같은 경우는 이런 특성을 이용한 방식이죠.)

그런데 siphash 종류의 hash는 seedkey라는 것을 hash 시에 추가로 받습니다. 그리고 이 seedkey로 인해 hash 결과가 바뀌게 됩니다. 그럼 이걸 어떻게 해야하는가? 예를 들어 프로세스가 시작되는 타이밍에 저 seedkey를 랜덤으로 생성합니다. 그러면, 해당 프로세스 내에서는 항상 동일한 값을 보장하지만, 새로운 프로세스가 뜨면, 동일한 key에 다른 hash값을 내놓을 것입니다.(물론 해당 프로세스 내에서는 항상 동일하겠죠.) 즉 어떤 서버에서 실행될 때, 이 key가 어떤 위치에 위치할지를 알 수 없게 됩니다. 그로 인해서 위의 알고리즘을 알더라도, 같은 슬롯에 충돌을 유도하기가 힘들어집니다. 다음은 Redis에서 패치된 코드입니다. 기본 hash가 내부적으로 siphash를 쓰도록 되어 있습니다.

int main(int argc, char **argv) {
    ......
    getRandomHexChars(hashseed,sizeof(hashseed));
    dictSetHashFunctionSeed((uint8_t*)hashseed);
    ......
}

uint64_t dictGenHashFunction(const void *key, int len) {
    return siphash(key,len,dict_hash_function_seed);
}

비슷한 이유로 Python 에서도 3.3 이후로는 기본으로 RANDOM SEED와 siphash류를 쓰도록 되어있습니다.

Advertisements

[입 생활] aws, github, 2FA 활성화나 수정 방법

이제 점점 더 귀찮아지지만 2 Factor Authentication 이 거의 필수처럼 여겨지고 있습니다. aws도 그렇고, github도, organization 에서 2FA가 안켜져 있으면 관리자가 계정 다 삭제해 버릴수도 있습니다. ㅋㅋㅋ

그런데 핸드폰은 2년마다 고장나고…(제껀 3년 만에…) 이럴 경우 이런 2FA를 바꿔야 하는데 aws나 github이나 다 쉽게 가능합니다만… -_-;;; 제가 워낙 바보라 저장해둡니다.

0] OPT 앱

구글 AUthentication 앱 사용

1] aws

my security credentials -> Multi-factor authentication (MFA) 를 선택해서 기존꺼를 삭제하고 추가하시면 됩니다.

2] Github

Settings -> Security -> Two-factor authentication -> Edit -> Delivery Option -> Reconfigure two-factor authentication -> Set up using an app -> Next 하면 바코드가 뜨니 이걸 OPT 앱으로 저장하면 됩니다.
이때 Next 가 비활성화 되어 있는데, 위의 Download, print, copy 중에 하나를 하시면 됩니다.

[입 개발] Python 3.3 부터는 hash 결과가 프로세스 마다 달라요!!!.

안녕하세요. 입개발자 charsyam 입니다. 아는 척, 있는 척 하기 위해서 예전에 만들었던 python 코드의 test 를 돌려봤는데… -_- 이게 웬일입니까… 테스트가 다 깨지는!!! 처음 만들었을 때는 분명히 돌아가는 테스트코드였는데… 이게 웬 일입니까…

일단 기본적으로 python 에는 hash 라는 built-in 함수가 존재합니다. 그런데 사실 이 hash 함수를 쓰는 것보다는, 명시적인 hashlib 함수를 사용하는 것을 권장합니다. 빌드에 따라 이 hash 함수가 바뀔 수도 있어서…

하여튼 편하게 가보겠다고 hash 함수를 사용했다가 버전이 2.7.x 에서 3.6.x를 쓰다가 피본 경험을 공유합니다. 먼저 증세를 살펴보면, 일단 프로세스가 기동된 상태에서는 결과는 항상 동일합니다. 그래서 항상 새로운 프로세스로 커맨드 라인에서 테스트를 진행합니다.

먼저 2.7.14의 결과입니다.

#2.7.14
python -c "print(hash('123'))"
163512108404620371
python -c "print(hash('123'))"
163512108404620371
python -c "print(hash('123'))"
163512108404620371
#3.6.x
python -c "print(hash('123'))"
8180009514858937698
python -c "print(hash('123'))"
-3358196339336188655
python -c "print(hash('123'))"
-5852881486981464238

일단 이것은 https://docs.python.org/3.3/using/cmdline.html 를 보면 Python 3.3.x 부터 기본적으로 다음과 같이 Hash Randomization 이라는 것이 들어갔다고 합니다. 이게 뭔지는 저는 몰라요, 며느리도 몰라요.

Kept for compatibility. On Python 3.3 and greater, hash randomization is turned on by default.

On previous versions of Python, this option turns on hash randomization, so that the __hash__() values of str, bytes and datetime are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.

Hash randomization is intended to provide protection against a denial-of-service caused by carefully-chosen inputs that exploit the worst case performance of a dict construction, O(n^2) complexity. See http://www.ocert.org/advisories/ocert-2011-003.html for details.

PYTHONHASHSEED allows you to set a fixed value for the hash seed secret.

보통 Hash의 값을 예상할 수 있으면, 특정 위치에만 데이터를 집어넣는 DDOS 공격이 가능한데, 이것을 막기 위한 것으로 보이고 그래서 보통 이런 것을 회피하기하기 위한 siphash를 3.x 부터 사용하는것으로 보입니다.(여담으로 Redis에서도 이런 DDOS를 막기위해서 siphash로 기존 hash 함수가 변경되었습니다.)

그럼 실제 어떻게 변화가 되었는지 2.7.14 기준으로 살펴보도록 하겠습니다.

2.7.14 분석

먼저 Python/bltinmodule.c 파일을 살펴보면 다음과 같은 builtin_methods 구조체를 발견할 수 있습니다. 이것은 python 에서 build-in(내장) 함수의 이름을 모아 놓는 것입니다.

static PyMethodDef builtin_methods[] = {
    ......
    {"hash",            builtin_hash,       METH_O, hash_doc},
    ......
}

그리고 builtin_methods 의 PyMethodDef 는 Include/methodobject.h 에 다음과 같이 정의되어 있습니다.

struct PyMethodDef {
    const char  *ml_name;   /* The name of the built-in function/method */
    PyCFunction  ml_meth;   /* The C function that implements it */
    int      ml_flags;  /* Combination of METH_xxx flags, which mostly
                   describe the args expected by the C func */
    const char  *ml_doc;    /* The __doc__ attribute, or NULL */
};
typedef struct PyMethodDef PyMethodDef;

넵, 그렇습니다. 위에 있는 builtin_hash 라는 함수가 실제 hash 명령을 사용했을 때 실행되는 함수입니다. 이제 builtin_hash 함수를 찾아보도록 하겠습니다.(Python/bltinmodule.c)

static PyObject *
builtin_hash(PyObject *self, PyObject *v)
{
    long x;

    x = PyObject_Hash(v);
    if (x == -1)
        return NULL;

    return PyInt_FromLong(x);
}

결론적으로는 PyObject_Hash 함수를 호출합니다. 구조체 안의 tp_hash 라는 것이 실제 hash 함수를 담고 있습니다.

long
PyObject_Hash(PyObject *v)
{
    PyTypeObject *tp = v->ob_type;
    if (tp->tp_hash != NULL) {
        long r = (*tp->tp_hash)(v);
        return r;
    }
    /* To keep to the general practice that inheriting
     * solely from object in C code should work without
     * an explicit call to PyType_Ready, we implicitly call
     * PyType_Ready here and then check the tp_hash slot again
     */
    if (tp->tp_dict == NULL) {
        if (PyType_Ready(tp) < 0)
            return -1;
        if (tp->tp_hash != NULL)
            return (*tp->tp_hash)(v);
    }
    if (tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL) {
        return _Py_HashPointer(v); /* Use address as hash value */
    }
    /* If there's a cmp but no hash defined, the object can't be hashed */
    return PyObject_HashNotImplemented(v);
}

그리고 string type 의 경우에는 저기서 tp_hash 가 string_hash 를 호출하게 됩니다. 재미난건 여기서도 _Py_HashSecret 이라는 것을 사용하고 있다는 것!!!(제가 참고한 버전이 2.7.14라서 이런 부분이 있을 수도 있지만… 더 자세한건 마음속에 있는 걸로… 귀찮아요!!!)

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

#ifdef Py_DEBUG
    assert(_Py_HashSecret_Initialized);
#endif
    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    /*
      We make the hash of the empty string be 0, rather than using
      (prefix ^ suffix), since this slightly obfuscates the hash secret
    */
    if (len == 0) {
        a->ob_shash = 0;
        return 0;
    }
    p = (unsigned char *) a->ob_sval;
    x = _Py_HashSecret.prefix;
    x ^= *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    x ^= _Py_HashSecret.suffix;
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}

저 _Py_HashSecret 은 다시 Python/random.c의 _PyRandom_Init() 에서 초기화 되게 됩니다. 이때 Py_HashRandomizationFlag 가 설정되어 있지 않아야 합니다. 코드는 간단하니… 알아서… PYTHONHASHSEED 가 설정되면 Py_HashRandomizationFlag 가 1로 셋팅됩니다.

void
_PyRandom_Init(void)
{
    char *env;
    void *secret = &_Py_HashSecret;
    Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);

    if (_Py_HashSecret_Initialized)
        return;
    _Py_HashSecret_Initialized = 1;

    /*
      By default, hash randomization is disabled, and only
      enabled if PYTHONHASHSEED is set to non-empty or if
      "-R" is provided at the command line:
    */
    if (!Py_HashRandomizationFlag) {
        /* Disable the randomized hash: */
        memset(secret, 0, secret_size);
        return;
    }

    /*
      Hash randomization is enabled.  Generate a per-process secret,
      using PYTHONHASHSEED if provided.
    */

    env = Py_GETENV("PYTHONHASHSEED");
    if (env && *env != '\0' && strcmp(env, "random") != 0) {
        char *endptr = env;
        unsigned long seed;
        seed = strtoul(env, &endptr, 10);
        if (*endptr != '\0'
            || seed > 4294967295UL
            || (errno == ERANGE && seed == ULONG_MAX))
        {
            Py_FatalError("PYTHONHASHSEED must be \"random\" or an integer "
                          "in range [0; 4294967295]");
        }
        if (seed == 0) {
            /* disable the randomized hash */
            memset(secret, 0, secret_size);
        }
        else {
            lcg_urandom(seed, (unsigned char*)secret, secret_size);
        }
    }
    else {
#ifdef MS_WINDOWS
        (void)win32_urandom((unsigned char *)secret, secret_size, 0);
#elif __VMS
        vms_urandom((unsigned char *)secret, secret_size, 0);
#elif defined(PY_GETENTROPY)
        (void)py_getentropy(secret, secret_size, 1);
#else
        dev_urandom_noraise(secret, secret_size);
#endif
    }
}

하여튼 PYTHONHASHSEED 를 설정하지 않거나 0으로 설정해주면 Randomize가 적용이 되지 않습니다.

그럼 이제 3.6.x 에서는 어떻게 변했을까요? 전 이걸 github에서 땡긴거라… 정확한 버전은 잘 모르겠네요.(라고 하고 찾아보니 3.7.0a4+ 네요.)

3.7.0a4+ 분석

2.7.14 의 분석과 마찬가지로 함수 정의 부터 따라가 보도록 하겠습니다. 3.7.0 에서는 Python/bltinmodule.c 에 builtin_methods 에 builtin 함수들이 정의되어 있고 다시 Python/clinic/bltinmodule.c.h 에 BUILTIN_HASH_METHODDEF 이 다음과 같이 정의되어 있습니다.

#define BUILTIN_HASH_METHODDEF    \
    {"hash", (PyCFunction)builtin_hash, METH_O, builtin_hash__doc__},

여기서도 실제로 builtin_hash 와 연결되어 있으므로 해당 함수를 확인해 봅니다. builtin_hash 는 2.7.14와 크게 다르지 않습니다.

static PyObject *
builtin_hash(PyObject *module, PyObject *obj)
/*[clinic end generated code: output=237668e9d7688db7 input=58c48be822bf9c54]*/
{
    Py_hash_t x;

    x = PyObject_Hash(obj);
    if (x == -1)
        return NULL;
    return PyLong_FromSsize_t(x);
}

친숙한 PyObject_Hash 가 보이네요. 코드도 거의 비슷하지만 사실은 아주 조금 줄어들었네요.

Py_hash_t
PyObject_Hash(PyObject *v)
{
    PyTypeObject *tp = Py_TYPE(v);
    if (tp->tp_hash != NULL)
        return (*tp->tp_hash)(v);
    /* To keep to the general practice that inheriting
     * solely from object in C code should work without
     * an explicit call to PyType_Ready, we implicitly call
     * PyType_Ready here and then check the tp_hash slot again
     */
    if (tp->tp_dict == NULL) {
        if (PyType_Ready(tp) < 0)
            return -1;
        if (tp->tp_hash != NULL)
            return (*tp->tp_hash)(v);
    }
    /* Otherwise, the object can't be hashed */
    return PyObject_HashNotImplemented(v);
}

Python 2.7 과 3.x의 가장 큰 차이라면 string 이 unicode가 되는 것인데, 여기서 보면, 2.7에서는 string_hash, 3.x에서는 unicode_hash를 호출하게 됩니다.

static Py_hash_t
unicode_hash(PyObject *self)
{
    Py_ssize_t len;
    Py_uhash_t x;  /* Unsigned for defined overflow behavior. */

#ifdef Py_DEBUG
    assert(_Py_HashSecret_Initialized);
#endif
    if (_PyUnicode_HASH(self) != -1)
        return _PyUnicode_HASH(self);
    if (PyUnicode_READY(self) == -1)
        return -1;
    len = PyUnicode_GET_LENGTH(self);
    /*
      We make the hash of the empty string be 0, rather than using
      (prefix ^ suffix), since this slightly obfuscates the hash secret
    */
    if (len == 0) {
        _PyUnicode_HASH(self) = 0;
        return 0;
    }
    x = _Py_HashBytes(PyUnicode_DATA(self),
                      PyUnicode_GET_LENGTH(self) * PyUnicode_KIND(self));
    _PyUnicode_HASH(self) = x;
    return x;
}

그리고 unicode_hash 는 조금 재미난 작업을 합니다. self 에 _PyUnicode_HASH 가 -1이 아니면 이미 자기 자신의 hash 값을 저장하고 있습니다. 그래서 값이 -1이 아니면 바로 전달하고, 그게 아니면 실제로 _Py_HashBytes 를 호출하게 됩니다.(PyUnicode_READY 는 뭔가 아주 복잡한 작업을 하지만… 패스…) 그리고 그 결과를 저장하게 됩니다.

Py_hash_t
_Py_HashBytes(const void *src, Py_ssize_t len)
{
    Py_hash_t x;
    /*
      We make the hash of the empty string be 0, rather than using
      (prefix ^ suffix), since this slightly obfuscates the hash secret
    */
    if (len == 0) {
        return 0;
    }

#ifdef Py_HASH_STATS
    hashstats[(len <= Py_HASH_STATS_MAX) ? len : 0]++;
#endif

#if Py_HASH_CUTOFF > 0
    if (len < Py_HASH_CUTOFF) {
        /* Optimize hashing of very small strings with inline DJBX33A. */
        Py_uhash_t hash;
        const unsigned char *p = src;
        hash = 5381; /* DJBX33A starts with 5381 */

        switch(len) {
            /* ((hash << 5) + hash) + *p == hash * 33 + *p */
            case 7: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
            case 6: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
            case 5: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
            case 4: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
            case 3: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
            case 2: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
            case 1: hash = ((hash << 5) + hash) + *p++; break;
            default:
                Py_UNREACHABLE();
        }
        hash ^= len;
        hash ^= (Py_uhash_t) _Py_HashSecret.djbx33a.suffix;
        x = (Py_hash_t)hash;
    }
    else
#endif /* Py_HASH_CUTOFF */
        x = PyHash_Func.hash(src, len);

    if (x == -1)
        return -2;
    return x;
}

중요한 부분만 보면 PyHash_Func.hash 이 코드가 됩니다. 그럼 PyHash_Func.hash는 어떻게 구성이 되는가?

다음과 같은 코드를 쉽게 찾을 수 있습니다. Py_HASH_ALGORITHM 가 무엇으로 설정되는가에 따라서 fnv 나 siphash24 로 설정이 되게 됩니다.(Python/pyhash.c)

typedef struct {
    Py_hash_t (*const hash)(const void *, Py_ssize_t);
    const char *name;
    const int hash_bits;
    const int seed_bits;
} PyHash_FuncDef;

#if Py_HASH_ALGORITHM == Py_HASH_FNV
static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * SIZEOF_PY_HASH_T,
                                     16 * SIZEOF_PY_HASH_T};
#endif

#if Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {pysiphash, "siphash24", 64, 128};
#endif

특별한 옵션을 주지 않으면 일단 Py_HASH_SIPHASH24 로 설정이 되게 됩니다. configure 파일을 보면

  --with-hash-algorithm=[fnv|siphash24]
                          select hash algorithm

로 되어있고, 이게 명시되지 않으면, MEMORY ALIGN 이 필요한 CPU(또는 cross compile을 지정해야해서) 쪽에서는 fnv가, 그렇지 않은 저 같은 맥이나 일반 x86 계열에서는 siphash24 가 설정이 되게 됩니다.

PyHash_Func.hash 가 호출되면 pysiphash 가 실제로 불리게 됩니다. 파라매터를 잘 보면 _Py_HashSecret 에서 사용하는 siphash 관련 값들이 넘어가게 됩니다.

static Py_hash_t
pysiphash(const void *src, Py_ssize_t src_sz) {
    return (Py_hash_t)siphash24(
        _le64toh(_Py_HashSecret.siphash.k0), _le64toh(_Py_HashSecret.siphash.k1),
        src, src_sz);
}

그럼 이제 마지막으로 3.x 에서 이 _Py_HashSecret 를 설정하는지 보면 됩니다. 먼저 _Py_HashSecret_t 는 다음과 같이 구성됩니다.

typedef union {
    /* ensure 24 bytes */
    unsigned char uc[24];
    /* two Py_hash_t for FNV */
    struct {
        Py_hash_t prefix;
        Py_hash_t suffix;
    } fnv;
    /* two uint64 for SipHash24 */
    struct {
        uint64_t k0;
        uint64_t k1;
    } siphash;
    /* a different (!) Py_hash_t for small string optimization */
    struct {
        unsigned char padding[16];
        Py_hash_t suffix;
    } djbx33a;
    struct {
        unsigned char padding[16];
        Py_hash_t hashsalt;
    } expat;
} _Py_HashSecret_t;

실제 _Py_HashSecret 의 설정은 _Py_HashRandomization_Init 에서 이루어집니다. 제 맥에서는 _Py_HashRandomization_Init를 호출하는 call stack 은 다음과 같습니다. 이 이야기는 처음에 시작과 동시에 호출이 된다는 것입니다.

 * frame #0: 0x000000010027de16 python`_Py_HashRandomization_Init(config=0x00007fff5fbff778) at bootstrap_hash.c:569
    frame #1: 0x000000010026364f python`_Py_InitializeCore(core_config=0x00007fff5fbff778) at pylifecycle.c:649
    frame #2: 0x00000001002abd05 python`pymain_main(pymain=0x00007fff5fbff720) at main.c:2647
    frame #3: 0x00000001002abea7 python`_Py_UnixMain(argc=1, argv=0x00007fff5fbff8b8) at main.c:2695
    frame #4: 0x0000000100000e62 python`main(argc=1, argv=0x00007fff5fbff8b8) at python.c:15
    frame #5: 0x00007fffa8f62235 libdyld.dylib`start + 1
    frame #6: 0x00007fffa8f62235 libdyld.dylib`start + 1

_Py_HashRandomization_Init 는 Python/bootstrap_hash.c 에 있습니다. 2.7.14와의 차이는 2.7.14에서는 PYTHONHASHSEED 가 없으면 randomize 작업이 없지만, 3.x 에서는 PYTHONHASHSEED 가 설정되어 있으면 그 값으로 seed를, 없으면 pyurandom 을 호출해서 randomize 가 일어나게 된다는 것입니다.

_PyInitError
_Py_HashRandomization_Init(const _PyCoreConfig *config)
{
    void *secret = &_Py_HashSecret;
    Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);

    if (_Py_HashSecret_Initialized) {
        return _Py_INIT_OK();
    }
    _Py_HashSecret_Initialized = 1;

    if (config->use_hash_seed) {
        if (config->hash_seed == 0) {
            /* disable the randomized hash */
            memset(secret, 0, secret_size);
        }
        else {
            /* use the specified hash seed */
            lcg_urandom(config->hash_seed, secret, secret_size);
        }
    }
    else {
        /* use a random hash seed */
        int res;

        /* _PyRandom_Init() is called very early in the Python initialization
           and so exceptions cannot be used (use raise=0).

           _PyRandom_Init() must not block Python initialization: call
           pyurandom() is non-blocking mode (blocking=0): see the PEP 524. */
        res = pyurandom(secret, secret_size, 0, 0);
        if (res < 0) {
            return _Py_INIT_USER_ERR("failed to get random numbers "
                                     "to initialize Python");
        }
    }
    return _Py_INIT_OK();
}

python 에서 hash randomize를 끄고 싶다면, 양 버전 모두 PYTHONHASHSEED 을 0으로 설정하는 것입니다. 하지만, 권장하는 것은 python 의 built-in hash 함수를 쓰지말고, 명시적으로 알 수 있는 hash 함수를 사용하는 것이 훨씬 좋다는 것입니다.(결론은 마지막 한줄!!!)

[입 개발] IPv4 TCP Socket, Listen 에서 Accept 까지…

갑자기 초괴수 지인분이 TCP Socket 에서 Listen 하고 Accept 할 때 어떤 일이 벌어지는지에 대해서 궁금해 하시는 질문을 올리셨습니다. 사실 Accept 자체는 별로 하는게 없다라는 건 알고 있었는데, 실제로 그 사이에 어떤 일이 벌어지는지에 대해서는 저도 잘 모르고 있어서, 그냥 한번 살펴봤습니다. 먼저, 이걸 보기 전에 TCP의 Connection이 맺어지는 3-way handshake는 굉장히 유명하고 중요하니, 이미지를 도용해옵시다.

3whs

일단 위의 그림을 보면 client 가 connect 를 하기 전에 server 는 listen을 해둬야 합니다. 그럼 이 listen을 하는 동안 어떤 작업이 일어나게 될까요?(linux 4.12.2 기준입니다.)

먼저 봐야할 소스는 net/ipv4/af_inet.c 의 inet_stream_ops 설정입니다. 실제 c코드 등의 함수가 커널레벨에서는 이 함수들과 매핑이 된다고 보시면 됩니다. 여기서 listen 은 inet_listen, accept 은 inet_accept 이 설정되어 있는 것을 볼 수 있습니다.

const struct proto_ops inet_stream_ops = {
    .family        = PF_INET,
    .owner         = THIS_MODULE,
    .release       = inet_release,
    .bind          = inet_bind,
    .connect       = inet_stream_connect,
    .socketpair    = sock_no_socketpair,
    .accept        = inet_accept,
    .getname       = inet_getname,
    .poll          = tcp_poll,
    .ioctl         = inet_ioctl,
    .listen        = inet_listen,
    .shutdown      = inet_shutdown,
    .setsockopt    = sock_common_setsockopt,
    .getsockopt    = sock_common_getsockopt,
    .sendmsg       = inet_sendmsg,
    .recvmsg       = inet_recvmsg,
    .mmap          = sock_no_mmap,
    .sendpage      = inet_sendpage,
    .splice_read       = tcp_splice_read,
    .read_sock     = tcp_read_sock,
    .peek_len      = tcp_peek_len,
#ifdef CONFIG_COMPAT
    .compat_setsockopt = compat_sock_common_setsockopt,
    .compat_getsockopt = compat_sock_common_getsockopt,
    .compat_ioctl      = inet_compat_ioctl,
#endif
};

그럼 이제 inet_listen 함수를 찾아봅니다. 코드를 보면 TCP_FASTOPEN 에 대한 처리도 있는데, 이 부분은 일단은 생략합니다. inet_listen 함수에서는 해당 socket 이 TCP_LISTEN 상태가 아니면 inet_csk_listen_start 함수를 호출하고 listen의 파라매터로 넘어오는 backlog 를 설정합니다.

/*
 *  Move a socket into listening state.
 */
int inet_listen(struct socket *sock, int backlog)
{
    struct sock *sk = sock->sk;
    unsigned char old_state;
    int err;

    lock_sock(sk);

    err = -EINVAL;
    if (sock->state != SS_UNCONNECTED || sock->type != SOCK_STREAM)
        goto out;

    old_state = sk->sk_state;
    if (!((1 << old_state) & (TCPF_CLOSE | TCPF_LISTEN)))
        goto out;

    /* Really, if the socket is already in listen state
     * we can only allow the backlog to be adjusted.
     */
    if (old_state != TCP_LISTEN) {
        /* Enable TFO w/o requiring TCP_FASTOPEN socket option.
         * Note that only TCP sockets (SOCK_STREAM) will reach here.
         * Also fastopen backlog may already been set via the option
         * because the socket was in TCP_LISTEN state previously but
         * was shutdown() rather than close().
         */
        if ((sysctl_tcp_fastopen & TFO_SERVER_WO_SOCKOPT1) &&
            (sysctl_tcp_fastopen & TFO_SERVER_ENABLE) &&
            !inet_csk(sk)->icsk_accept_queue.fastopenq.max_qlen) {
            fastopen_queue_tune(sk, backlog);
            tcp_fastopen_init_key_once(true);
        }

        err = inet_csk_listen_start(sk, backlog);
        if (err)
            goto out;
    }
    sk->sk_max_ack_backlog = backlog;
    err = 0;

out:
    release_sock(sk);
    return err;
}

그럼 다시 inet_csk_listen_start 함수를 살펴봅니다 net/ipv4/inet_connection_sock.c 안에 있습니다. inet_csk_listen_start 함수에서 처음에 신경써서 볼 부분은 reqsk_queue_alloc 함수를 호출하는 부분입니다. 변수명이 뭔가 와 닫는가요? icsk_accept_queue 라는 이름으로 할당하고 있습니다. 네, 이것이 바로 TCP에서 실제 connect 하는 client 에 대한 연결 요청이 저장되는 queue 입니다. accept 에서는 여기에 있으면 바로 가져가고, 없으면 대기하게 되는거죠. 여기서 해당 포트를 확보하는데 문제가 발생하면 TCP_CLOSE 상태로 가게됩니다.

int inet_csk_listen_start(struct sock *sk, int backlog)
{
    struct inet_connection_sock *icsk = inet_csk(sk);
    struct inet_sock *inet = inet_sk(sk);
    int err = -EADDRINUSE;

    reqsk_queue_alloc(&icsk->icsk_accept_queue);

    sk->sk_max_ack_backlog = backlog;
    sk->sk_ack_backlog = 0;
    inet_csk_delack_init(sk);

    /* There is race window here: we announce ourselves listening,
     * but this transition is still not validated by get_port().
     * It is OK, because this socket enters to hash table only
     * after validation is complete.
     */
    sk_state_store(sk, TCP_LISTEN);
    if (!sk->sk_prot->get_port(sk, inet->inet_num)) {
        inet->inet_sport = htons(inet->inet_num);

        sk_dst_reset(sk);
        err = sk->sk_prot->hash(sk);

        if (likely(!err))
            return 0;
    }

    sk->sk_state = TCP_CLOSE;
    return err;
}

이제 해당 socket 이 TCP_LISTEN 상태가 되었습니다. 그런데 젤 앞에 TCP 3-way handshake는 client 가 connect 함수를 호출하면서 SYN 패킷을 보내면서 부터 시작되게 됩니다. 이 부분은 어디서 처리하게 될까요? tcp_rcv_state_process 라는 함수가 net/ipv4/tcp_input.c 에 있습니다. 그런데 이 함수는 어디서 호출되는 것일까요? 다음과 같이 tcp_protocol 정의를 보면 실제 데이터를 처리하는 tcp_v4_rcv 라는 함수가 있습니다.

static struct net_protocol tcp_protocol = {
    .early_demux    =   tcp_v4_early_demux,
    .early_demux_handler =  tcp_v4_early_demux,
    .handler    =   tcp_v4_rcv,
    .err_handler    =   tcp_v4_err,
    .no_policy  =   1,
    .netns_ok   =   1,
    .icmp_strict_tag_validation = 1,
};

해당 socket 이 TCP_LISTEN 상태이면 다시 tcp_v4_do_rcv 라는 함수를 호출하게 되고 다시 tcp_child_process 함수를 호출하거나 하지 않더라도 최종적으로 tcp_rcv_state_process 함수를 호출하게 됩니다.(tcp_child_process가 호출되지 않아도 그 밑에 tcp_rcv_state_process가 호출됩니다.) TCP_LISTEN 인 경우를 보면, 앞에 TCP 3-way handshake를 한번 더 기억해야 합니다.

SYN -> SYN+ACK -> ACK 형태의 순서로 넘어가게 되는데, SYN과 ACK가 server 쪽에서 받게 되는 패킷입니다. ACK가 오면, 이제 ESTABLISH 가 되는 것이므로 여기서는 바로 return 1을 하게 됩니다. 그러면 실제로 SYN+ACK를 보내는 상황은 SYN을 받았을 때 입니다. FIN이 설정되어 있으면, TCP 접속을 종료하는 거니 discard 하게 되고, 정상적이면 conn_request 함수를 호출하게 됩니다.

    case TCP_LISTEN:
        if (th->ack)
            return 1;

        if (th->rst)
            goto discard;

        if (th->syn) {
            if (th->fin)
                goto discard;
            /* It is possible that we process SYN packets from backlog,
             * so we need to make sure to disable BH right there.
             */
            local_bh_disable();
            acceptable = icsk->icsk_af_ops->conn_request(sk, skb) >= 0;
            local_bh_enable();

            if (!acceptable)
                return 1;
            consume_skb(skb);
            return 0;
        }
        goto discard;

conn_request 함수는 다음 ipv4_specific를 살펴봐야 합니다. tcp_v4_conn_request 함수랑 매핑이 되어 있네요.

const struct inet_connection_sock_af_ops ipv4_specific = {
    .queue_xmit    = ip_queue_xmit,
    .send_check    = tcp_v4_send_check,
    .rebuild_header    = inet_sk_rebuild_header,
    .sk_rx_dst_set     = inet_sk_rx_dst_set,
    .conn_request      = tcp_v4_conn_request,
    .syn_recv_sock     = tcp_v4_syn_recv_sock,
    .net_header_len    = sizeof(struct iphdr),
    .setsockopt    = ip_setsockopt,
    .getsockopt    = ip_getsockopt,
    .addr2sockaddr     = inet_csk_addr2sockaddr,
    .sockaddr_len      = sizeof(struct sockaddr_in),
#ifdef CONFIG_COMPAT
    .compat_setsockopt = compat_ip_setsockopt,
    .compat_getsockopt = compat_ip_getsockopt,
#endif
    .mtu_reduced       = tcp_v4_mtu_reduced,
};

tcp_v4_conn_request 는 tcp_conn_request 라는 함수를 다시 호출합니다. TCP_FASTOPEN 이 아닐 때 보면 inet_csk_reqsk_queue_hash_add 를 호출하는데 이 함수가 실제로 accept_queue에 값을 집어넣는 함수입니다. 라고 생각했는데, 소스를 잘못 본것입니다. 여기서는 TIMEOUT만 설정하게 됩니다. 그리고 SYN+ACK를 보내고 되죠.

    if (fastopen_sk) {
        af_ops->send_synack(fastopen_sk, dst, &fl, req,
                    &foc, TCP_SYNACK_FASTOPEN);
        /* Add the child socket directly into the accept queue */
        inet_csk_reqsk_queue_add(sk, req, fastopen_sk);
        sk->sk_data_ready(sk);
        bh_unlock_sock(fastopen_sk);
        sock_put(fastopen_sk);
    } else {
        tcp_rsk(req)->tfo_listener = false;
        if (!want_cookie)
            inet_csk_reqsk_queue_hash_add(sk, req, TCP_TIMEOUT_INIT);
        af_ops->send_synack(sk, dst, &fl, req, &foc,
                    !want_cookie ? TCP_SYNACK_NORMAL :
                           TCP_SYNACK_COOKIE);
        if (want_cookie) {
            reqsk_free(req);
            return 0;
        }
    }

같은 tcp_conn_request 함수안의 앞부분을 보면 inet_reqsk_alloc 을 호출하는 부분이 있습니다.

int tcp_conn_request(struct request_sock_ops *rsk_ops,
             const struct tcp_request_sock_ops *af_ops,
             struct sock *sk, struct sk_buff *skb)
{
    struct tcp_fastopen_cookie foc = { .len = -1 };
    __u32 isn = TCP_SKB_CB(skb)->tcp_tw_isn;
    struct tcp_options_received tmp_opt;
    struct tcp_sock *tp = tcp_sk(sk);
    struct net *net = sock_net(sk);
    struct sock *fastopen_sk = NULL;
    struct dst_entry *dst = NULL;
    struct request_sock *req;
    bool want_cookie = false;
    struct flowi fl;

    /* TW buckets are converted to open requests without
     * limitations, they conserve resources and peer is
     * evidently real one.
     */
    if ((net->ipv4.sysctl_tcp_syncookies == 2 ||
         inet_csk_reqsk_queue_is_full(sk)) && !isn) {
        want_cookie = tcp_syn_flood_action(sk, skb, rsk_ops->slab_name);
        if (!want_cookie)
            goto drop;
    }

    if (sk_acceptq_is_full(sk)) {
        NET_INC_STATS(sock_net(sk), LINUX_MIB_LISTENOVERFLOWS);
        goto drop;
    }

    req = inet_reqsk_alloc(rsk_ops, sk, !want_cookie);
    if (!req)
        goto drop;

    ......

inet_reqsk_alloc 함수를 보면 TCP_NEW_SYN_RECV 로 셋팅하는 부분이 있습니다. 그러면서 새로운 child 소켓을 생성하기 위한 준비를 하는 것으로 보입니다. TCP_NEW_SYN_RECV는 https://patchwork.ozlabs.org/patch/449704/ 를 보시면 왜 추가되었는지 설명이 나옵니다.(저도 잘 몰라요 ㅋㅋㅋ)

struct request_sock *inet_reqsk_alloc(const struct request_sock_ops *ops,
                      struct sock *sk_listener,
                      bool attach_listener)
{
    struct request_sock *req = reqsk_alloc(ops, sk_listener,
                           attach_listener);

    if (req) {
        struct inet_request_sock *ireq = inet_rsk(req);

        kmemcheck_annotate_bitfield(ireq, flags);
        ireq->opt = NULL;
#if IS_ENABLED(CONFIG_IPV6)
        ireq->pktopts = NULL;
#endif
        atomic64_set(&ireq->ir_cookie, 0);
        ireq->ireq_state = TCP_NEW_SYN_RECV;
        write_pnet(&ireq->ireq_net, sock_net(sk_listener));
        ireq->ireq_family = sk_listener->sk_family;
    }

    return req;
}

다시 처음의 tcp_v4_rcv 함수로 돌아갑니다.(net/ipv4/tcp_ipv4.c), 여기서 tcp_check_req 함수가 호출이 됩니다.(net/ipv4/tcp_minisocks.c)

    if (sk->sk_state == TCP_NEW_SYN_RECV) {
        struct request_sock *req = inet_reqsk(sk);
        struct sock *nsk;

        sk = req->rsk_listener;
        if (unlikely(tcp_v4_inbound_md5_hash(sk, skb))) {
            sk_drops_add(sk, skb);
            reqsk_put(req);
            goto discard_it;
        }
        if (unlikely(sk->sk_state != TCP_LISTEN)) {
            inet_csk_reqsk_queue_drop_and_put(sk, req);
            goto lookup;
        }
        /* We own a reference on the listener, increase it again
         * as we might lose it too soon.
         */
        sock_hold(sk);
        refcounted = true;
        nsk = tcp_check_req(sk, skb, req, false);
        if (!nsk) {
            reqsk_put(req);
            goto discard_and_relse;
        }
        if (nsk == sk) {
            reqsk_put(req);
        } else if (tcp_child_process(sk, nsk, skb)) {
            tcp_v4_send_reset(nsk, skb);
            goto discard_and_relse;
        } else {
            sock_put(sk);
            return 0;
        }
    }

tcp_check_req 에서는 뭔가 복잡한 작업을 하고 있습니다.(제가 이걸 보고 바로 이해할 능력은 안됩니다. 하하하하 T.T) 일단 SYN+ACK를 보내고 여기서 ACK를 받아야 정상적으로 연결이 완료되기 때문에, child 소켓이 만들어지고(accept 하면 server 소켓이 아니라 다른 소켓을 받게 되는거 기억나시죠?, tcp_v4_syn_recv_sock 함수에서 만들어집니다.) 마지막에 inet_csk_complete_hashdance 함수를 호출하면서

struct sock *tcp_check_req(struct sock *sk, struct sk_buff *skb,
               struct request_sock *req,
               bool fastopen)
{
     ......
     /* OK, ACK is valid, create big socket and
     * feed this segment to it. It will repeat all
     * the tests. THIS SEGMENT MUST MOVE SOCKET TO
     * ESTABLISHED STATE. If it will be dropped after
     * socket is created, wait for troubles.
     */
    child = inet_csk(sk)->icsk_af_ops->syn_recv_sock(sk, skb, req, NULL,
                             req, &own_req);
    if (!child)
        goto listen_overflow;

    sock_rps_save_rxhash(child, skb);
    tcp_synack_rtt_meas(child, req);
    return inet_csk_complete_hashdance(sk, child, req, own_req);

inet_csk_complete_hashdance 함수에서는 실제로 inet_csk_reqsk_queue_add 함수를 호출해서 실제로 accept_queue에 새로 생성된 child socket을 집어넣어줍니다.

struct sock *inet_csk_complete_hashdance(struct sock *sk, struct sock *child,
                     struct request_sock *req, bool own_req)
{
    if (own_req) {
        inet_csk_reqsk_queue_drop(sk, req);
        reqsk_queue_removed(&inet_csk(sk)->icsk_accept_queue, req);
        if (inet_csk_reqsk_queue_add(sk, req, child))
            return child;
    }
    /* Too bad, another child took ownership of the request, undo. */
    bh_unlock_sock(child);
    sock_put(child);
    return NULL;
}

지금까지 진행한 부분에서 새로 생성된 소켓을 TCP_ESTABLISHED 로 설정되는 부분이 안보입니다. 이건 어디서 할까요? 실제로 위에 살짝 빠지고 넘어간 tcp_v4_syn_recv_sock 함수를 살펴보면, 새로운 소켓을 만들기 위한 tcp_create_openreq_child 함수를 호출합니다. 여기서 다시 inet_csk_clone_lock 함수를 통해서 parent를 clone 하게 되는데 여기서 TCP_SYN_RECV 로 state가 설정되게 되고, 다시 tcp_rcv_state_process 에서 TCP_ESTABLISHED로 설정이 됩니다.(확실하지는 않습니다.)

이제 accept 이 호출되었을 때를 살펴보도록 하겠습니다. accept 은 처음에 inet_accept 함수를 호출하게 되고, 여기서 내부적으로 inet_csk_accept 을 호출하게 됩니다. 먼저 accept_queue를 확인해서 empty 이면, 하나도 존재하지 않으니, inet_csk_wait_for_connect 를 호출해서 내부적으로 대기하게 됩니다. O_NONBLOCK 이 설정되어 있으면 하나도 없을 때, 익숙한 -EAGAIN이 리턴됩니다.

/*
 * This will accept the next outstanding connection.
 */
struct sock *inet_csk_accept(struct sock *sk, int flags, int *err, bool kern)
{
    struct inet_connection_sock *icsk = inet_csk(sk);
    struct request_sock_queue *queue = &icsk->icsk_accept_queue;
    struct request_sock *req;
    struct sock *newsk;
    int error;

    lock_sock(sk);

    /* We need to make sure that this socket is listening,
     * and that it has something pending.
     */
    error = -EINVAL;
    if (sk->sk_state != TCP_LISTEN)
        goto out_err;

    /* Find already established connection */
    if (reqsk_queue_empty(queue)) {
        long timeo = sock_rcvtimeo(sk, flags & O_NONBLOCK);

        /* If this is a non blocking socket don't sleep */
        error = -EAGAIN;
        if (!timeo)
            goto out_err;

        error = inet_csk_wait_for_connect(sk, timeo);
        if (error)
            goto out_err;
    }
    req = reqsk_queue_remove(queue, sk);
    newsk = req->sk;

    if (sk->sk_protocol == IPPROTO_TCP &&
        tcp_rsk(req)->tfo_listener) {
        spin_lock_bh(&queue->fastopenq.lock);
        if (tcp_rsk(req)->tfo_listener) {
            /* We are still waiting for the final ACK from 3WHS
             * so can't free req now. Instead, we set req->sk to
             * NULL to signify that the child socket is taken
             * so reqsk_fastopen_remove() will free the req
             * when 3WHS finishes (or is aborted).
             */
            req->sk = NULL;
            req = NULL;
        }
        spin_unlock_bh(&queue->fastopenq.lock);
    }
out:
    release_sock(sk);
    if (req)
        reqsk_put(req);
    return newsk;
out_err:
    newsk = NULL;
    req = NULL;
    *err = error;
    goto out;
}

reqsk_queue_remove 를 호출하면 실제로 accept_queue 에서 연결을 하나 가져오게 됩니다.(링크드 리스트에서 head를 가져옵니다.)

[입 개발] DNS Caching in JVM

다음과 같은 오류가 발견되어서 정정합니다. 현재는 JVM에서의 DNS Caching 이 30초입니다.
자바6 이후로는 계속 그렇게 설정되어 있는듯 합니다. 흑흑흑 나는 왜 지금까지 그 옵션을 열심히 사용했을까요?
그러나 흐름 자체는 도움이 될듯하여 내용은 수정해서 남겨둡니다. 알려주신 역촋 정상혁님께 감사를

JVM 에서 (혹은 Java) 에서는 DNS Caching 이 디폴트로 FOREVER 입니다. 이 말은 한번 쿼리한 DNS 주소는 다시는 쿼리하지 않는다는 것입니다. 이러면 당연히 DNS 쿼리 시간이 들지 않으니, 속도면에서는 유리하지만, DNS 변화를 주는 것으로 뭔가 처리할려고 하면, 결국 계속 실패하게 됩니다.  이전 ip를 계속 써버리니… 그럼 이 동작을 어떻게 확인하는가? JDK 소스를 까보시면 간단하게 아실 수 있습니다.

./src/share/classes/java/net/InetAddress.java
./src/share/classes/sun/net/InetAddressCachePolicy.java

InetAddress class 는 getAllByName0 함수가 불려질 때 먼저 cache 되어있는지를 getCachedAddresses 함수를 통해서 확인합니다. 아래 코드르 보면 cache 에 없을때만 실제 DNS 질의를 하게 됩니다.

    private static InetAddress[] getAllByName0 (String host, InetAddress reqAddr, boolean check)
        throws UnknownHostException  {

        /* If it gets here it is presumed to be a hostname */
        /* Cache.get can return: null, unknownAddress, or InetAddress[] */

        /* make sure the connection to the host is allowed, before we
         * give out a hostname
         */
        if (check) {
            SecurityManager security = System.getSecurityManager();
            if (security != null) {
                security.checkConnect(host, -1);
            }
        }

        InetAddress[] addresses = getCachedAddresses(host);

        /* If no entry in cache, then do the host lookup */
        if (addresses == null) {
            addresses = getAddressesFromNameService(host, reqAddr);
        }

        if (addresses == unknown_array)
            throw new UnknownHostException(host);

        return addresses.clone();
}

그리고 getCachedAddresses 함수는 InetAddressCachePolicy 가 FOREVER일 때는 해당 값을 expire 시키지 않습니다.

private int getPolicy() {
    if (type == Type.Positive) {
        return InetAddressCachePolicy.get();
    } else {
        return InetAddressCachePolicy.getNegative();
   }
}

public CacheEntry get(String host) {
    int policy = getPolicy();
    if (policy == InetAddressCachePolicy.NEVER) {
        return null;
    }
    CacheEntry entry = cache.get(host);
 
    // check if entry has expired
    if (entry != null && policy != InetAddressCachePolicy.FOREVER) {
        if (entry.expiration >= 0 &&
            entry.expiration < System.currentTimeMillis()) {
            cache.remove(host);
            entry = null;
        }
    }
 
    return entry;
}

따로 설정을 하지 않으면 InetAddressCachePolicy 는 디폴트로 FOREVER 입니다.

// Controls the cache policy for successful lookups only
private static final String cachePolicyProp = "networkaddress.cache.ttl";
private static final String cachePolicyPropFallback =
    "sun.net.inetaddr.ttl";
 
// Controls the cache policy for negative lookups only
private static final String negativeCachePolicyProp =
    "networkaddress.cache.negative.ttl";
private static final String negativeCachePolicyPropFallback =
    "sun.net.inetaddr.negative.ttl";
 
public static final int FOREVER = -1;
public static final int NEVER = 0;
 
private static int cachePolicy = FOREVER;
 
public static synchronized int get() {
    return cachePolicy;
}

그리고 해당 값은 Security Property 와 System Property에 의해서 제어가 가능합니다.

스크린샷 2017-12-27 오후 5.28.32

단위는 초고, 초가 자동으로 밀리세컨으로 변경됩니다.

long expiration;
if (policy == InetAddressCachePolicy.FOREVER) {
    expiration = -1;
} else {
    expiration = System.currentTimeMillis() + (policy * 1000);
}

우선순위는 networkaddress.cache.ttl 가 있으면 이걸 먼저 사용하고, 없으면 그 다음에 sun.net.inetaddr.negative.ttl 을 사용합니다. 즉 Security Property 설정이 우선입니다.
아래 한글 주석을 확인하면 아무 옵션이 없을 때, SecurityManager 가 설정되어 있지 않으면 30초로 설정되게 됩니다.

Integer tmp = java.security.AccessController.doPrivileged(
  new PrivilegedAction<Integer>() {
    public Integer run() {
        try {
            String tmpString = Security.getProperty(cachePolicyProp);
            if (tmpString != null) {
                return Integer.valueOf(tmpString);
            }
        } catch (NumberFormatException ignored) {
            // Ignore
        }
 
        try {
            String tmpString = System.getProperty(cachePolicyPropFallback);
            if (tmpString != null) {
                return Integer.decode(tmpString);
            }
        } catch (NumberFormatException ignored) {
            // Ignore
        }
        return null;
    }
  });
if (tmp != null) {
    cachePolicy = tmp.intValue();
    if (cachePolicy < 0) {
        cachePolicy = FOREVER;
    }
    propertySet = true;
} else {
    /* SecurityManager 가 설정되어 있지 않으면, 여기서 cachePolicy 가 DEFAULT_POSITIVE 가
     * 30초로 설정됩니다.
     */
    /* No properties defined for positive caching. If there is no
     * security manager then use the default positive cache value.
     */
    if (System.getSecurityManager() == null) {
        cachePolicy = DEFAULT_POSITIVE;
    }
}

즉 위와 같이 해당 값을 설정하면 그 이후에는 캐시가 날라가서 다시 실제 쿼리를 날리게 됩니다. 보통 로컬에 dnsmasq 나 unbound 같은 로컬 DNS 캐시 서버를 둬서, 거기서 캐싱을 하면 실제적으로 외부로 날라가는 것보다는 훨씬 DNS 쿼리 비용을 줄일 수 있습니다.

참고문헌:
https://www.lesstif.com/pages/viewpage.action?pageId=17105897

[입 개발] I don’t know DNS Caching

흐음, 입 개발 전문가 CharSyam  입니다. 나름 입 개발을 오래해보긴 하고, DNS 프로토콜도 직접 구현해보고, Dynamic DNS를 Zookeeper 기반으로 만들어보기도 해서 잘 안다고(이렇게 적고 실제로는 일도 모른다고 읽으시면 됩니다.) 생각했는데… 제 상식을 깨는 일이 발생했습니다.(다른 분들의 상식이 아니라 제 상식이니 무시하시면 됩니다.)

아래와 같은 코드가 존재합니다. 여기서 http://www.naver.com 은 몇번 호출이 될까요?

import requests
requests.get('http://www.naver.com')
requests.get('http://www.naver.com')

 한번도 안한다. 한번만 한다. 두번 한다. 세번 한다. 네번 한다. 정답은 설정과 OS에 따라 다르다입니다.(퍽퍽퍽, 죽어!!!) 디폴트 설정이라는 가정하에서는 Windows와 Linux 에서의 설정이 또 다릅니다. 이게 무슨 소리냐 하면 Windows 는 OS 레벨에서의 DNS가 캐싱이 되므로 아마, 위의 코드는 한번도 안할 수도 있습니다.(이전에 했다면…), 처음 실행된다는 가정하에서는 그럼 한번만 되겠죠. 그런데 여기서는 이제 Linux 쪽, 특히 Debian 계열로 한정을 짓는다면, 위의 코드는 4번의 DNS 호출을 하게 됩니다.(왜 두번이 아니라… 그것은 http://www.naver.comhttps://www.naver.com 으로 redirection 되기 때문에~~~), 그런데 엉? 4번이라고? 처음이라도 한번만 되어야 되는게 아니야?

먼저 tcpdump 를 설치합니다.

sudo apt-get install tcpdump

그리고 udp 53번을 모니터링 합니다.

sudo tcpdump -i eth0 udp port 53

그리고 위의 코드를 실행시키면… 다음과 같은 결과가 나옵니다.

01:32:31.303838 IP 192.168.0.2.60630 > acns.uplus.co.kr.domain: 30077+ A? www.naver.com. (31)
01:32:31.303846 IP 192.168.0.2.60630 > pcns.bora.net.domain: 30077+ A? www.naver.com. (31)
01:32:31.303856 IP 192.168.0.2.60630 > pcns.bora.net.domain: 45919+ AAAA? www.naver.com. (31)
01:32:31.306473 IP pcns.bora.net.domain > 192.168.0.2.60630: 30077 3/3/3 CNAME www.naver.com.nheos.com., A 210.89.160.88, A 210.89.164.90 (199)
01:32:31.306983 IP acns.uplus.co.kr.domain > 192.168.0.2.60630: 30077 3/3/3 CNAME www.naver.com.nheos.com., A 125.209.222.142, A 210.89.164.90 (199)
01:32:31.311150 IP pcns.bora.net.domain > 192.168.0.2.60630: 45919 1/1/0 CNAME www.naver.com.nheos.com. (116)
01:33:08.638991 IP 192.168.0.2.60630 > acns.uplus.co.kr.domain: 31222+ A? www.naver.com. (31)
01:33:08.638999 IP 192.168.0.2.60630 > pcns.bora.net.domain: 31222+ A? www.naver.com. (31)
01:33:08.639010 IP 192.168.0.2.60630 > pcns.bora.net.domain: 64566+ AAAA? www.naver.com. (31)
01:33:08.642771 IP pcns.bora.net.domain > 192.168.0.2.60630: 64566 1/1/0 CNAME www.naver.com.nheos.com. (116)
01:33:08.642781 IP pcns.bora.net.domain > 192.168.0.2.60630: 31222 3/3/3 CNAME www.naver.com.nheos.com., A 125.209.222.141, A 210.89.160.88 (199)
01:33:08.643297 IP acns.uplus.co.kr.domain > 192.168.0.2.60630: 31222 3/3/3 CNAME www.naver.com.nheos.com., A 125.209.222.141, A 210.89.160.88 (199)
......

우리는 OS 레벨의 DNS Caching을 기대하지만, 이 얘기는 기본적으로 OS 레벨에서의 DNS 캐시가 꺼져있다라는 얘기가 됩니다.(대부분의 linux에서 꺼져있다라는…) DNS Level Failover를 적용할려고 하다가, Python 에서는 DNS Caching 이 어떻게 이루어지는지를 보려고 하다보니…, 우연히 https://stackoverflow.com/questions/11020027/dns-caching-in-linux 를 찾게 되었는데…(역시 갓 SO, 참고로 JVM 에서는 DNS Caching 이 영구적이라, 특정 옵션을 주지 않으면, 처음 받게 된 ip를 계속 사용하게 되므로, 기본 옵션으로는 DNS Level Failover를 쓸 수 없습니다.)

여기서 “꺼져있다”, “꺼져있다”, “꺼져있다”를 보고 충격을 받았습니다. 그래서 위와 같이 실험을 했더니… 사실이었습니다. 자세한 내용은 위의 SO 글을 읽으시면… 잘 알게 되는데, glibc의 getaddrinfo 자체에서 발생하는 이슈라고 해서, 다음과 같이 코드를 실행해 봤습니다.

#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netdb.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
    struct addrinfo hints;
    struct addrinfo *result;

    memset(&hints, 0, sizeof(struct addrinfo));
    hints.ai_family = AF_UNSPEC;
    hints.ai_socktype = SOCK_STREAM;
    hints.ai_flags = 0;
    hints.ai_protocol = 0;

    for (int i = 0; i < atoi(argv[1]); i++) {
        int s = getaddrinfo("www.naver.com", NULL, &hints, &result);
        if (s != 0) {
            fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(s));
            exit(-1);
        }
        printf("%d\n", i);
        sleep(10);
    }
    return 0;
}

실행해보면, 매번 쿼리가 날라가는 것을 볼 수 있습니다. 즉, 이 이야기는, DNS Caching을 app 수준에서 따로 제어하지 않는다면, DNS 쿼리를 매번 호출하게 된다라는 얘기가 됩니다. 보통 DNS 쿼리를 굉장히 자주 날리는 것은 성능상 문제를 일으킬 수 있습니다. 실제로 이걸 잘 하는게 쉽지는 않을듯 하네요.

glibc 코드를 살짝 까보면, getaddrinfo 는 gaih_inet 이라는 함수를 호출해서 결과를 가져옵니다. gaih_inet 는 USE_NSCD가 켜져있으면 NSCD에서 캐시된 결과를 찾는 것으로 보이고, 그게 아니라면, 일단 hosts 파일에 있는지 체크합니다. 이래서 hosts에 등록하면 DNS 쿼리 없이 항상 제일 먼저 가져오게 됩니다. 그 뒤에 옵션이나 상황에 따라, gethostbyname2_r, gethostbyname3_r, gethostbyname4_r 을 콜하게 됩니다. 이 함수들은 실제로 resolv/nss_dns/dns-host.c 에 있는 _nss_dns_gethostbynameX_r 함수들과 매핑이 되고 여기서 DNS Query를 날리고 가져오게 됩니다.

즉, 이 얘기는 OS단에서 해주는게 없을 가능성이 높고, 지금 DNS 쿼리는 여전히 발생하고 있을지 모른다는 얘기다 됩니다.(일단 저는 이렇게 이해했는데… 잘 아시는 분 답변좀 T.T), 이걸 해결하기 위해서는 nscd 를 설치해야만, OS 레벨의 캐싱이 적용이 되게 됩니다. 아니면, app 레벨에서 직접 해줘야…

일단 자바의 경우는 jvm 레벨에서 DNS 캐싱이 적용되어 있습니다. 그래서 DNS Based Failover를 하려면 좀 더 자세히 알아야 합니다. jdk 소스를 보면 InetAddress.java, InetAddressCachePolicy.java 이 있습니다. InetAddress.java 에서 InetAddressCachePolicy 클래스를 사용하는데, 여기의 기본 옵션이 FOREVER 입니다. 그리고 InetAddress 에서 getCachedAddresses 함수를 호출하면서, 매번 위의 Policy를 확인하고, 위의 값들을 조절하면 networkaddress.cache.ttl 는 내부적으로 사용할 TTL 의 값(가져와서 ttl 확인하고 expire 시키네요.) 두 definition networkaddress.cache.ttl 이나 sun.net.inetaddr.ttl 을 먼저 체크해서 하나라도 값이 있으면, 해당 값으로 설정이 되고 없으면 SecurityManager를 체크하는데 이때 SecurityManager도 없으면 기본 TTL이 30초로 설정되게 됩니다.

[혀로그래머 charsyam은 구라쟁이 Q&A] 레디스 관련 Q&A

안녕하세요. 혀로그래머 구라쟁이 charsyam 입니다. 오늘은 제가 자주 서식하는 페북 커뮤니티에 질문을 누군가 올려주셔서 거기에 대한 답변을 간단하게 달아놓은 것을… 질문이 워낙 좋으셔서… 정리해 봤습니다.

먼저 질문은 다음과 같습니다.

  1. 인프라 구조에서 Scale-Out 구조를 가진 경우 각 데이터를 어떤 Node에 저장되고 있는지를 판별하고 있어야 하며 데이터 유실을 대비하여 데이터 블럭을 보통 분리하여 저장합니다. 레디스의 경우 한 노드가 죽었을때 휘발성인 캐쉬임을 대비하여 어떤 방식을 구현하는지요?
  2. 본문에 사용량이 많아지면 메모리 파편화가 일어난다고 하였는데(보통 디스크나 메모리의 경우 영속성이 있어야 성능이 잘나오는걸로 알고 있습니다.) 해당 파편화를 줄이는 알고리즘이나 파편화가 일어난 경우 해당 데이터를 재배치를 하는건가요?
  3. 서버 아키텍처는 캐쉬의 경우 여러 종류의 캐쉬를 두어 각 캐쉬별 역할을 구분하게 되어지는데 레디스도 그런 방식을 차용하고 있는건가요?
  4. 이슈를 대비하여 서버 대수만 늘려야한다면 아키 설계가 어려울듯 한데 아키 설계는 보통 어떻게?
  5. 레디스 서버 한대 다운시 처리는 어케 하는지요

여기에 대한 답변을 다음과 같이 정리했습니다.

  1. 인프라 구조에서 Scale-Out 구조를 가진 경우 각 데이터를 어떤 Node에 저장되고 있는지를 판별하고 있어야 하며 데이터 유실을 대비하여 데이터 블럭을 보통 분리하여 저장합니다. 레디스의 경우 한 노드가 죽었을때 휘발성인 캐쉬임을 대비하여 어떤 방식을 구현하는지요?
    1. 글에서 언급한 것 처럼 그냥 버리는 케이스가 있습니다. 각 노드들에 데이터들이 날아가도 실제 DB에서 처리할 수 있는 정도라면… 예를 들어 한대 죽었을 때 10% 정도 부하가 올라가는데, 이 정도는 원래 처리할 수 있다면, 무시해도 되겠죠.
    2. 캐시도 중요할 경우 Master/Slave 로 레디스 같은 경우 설정해 둘 수 있습니다. 멤캐시는 이게 안되서, 따로 리플리케이션을 구현하셔야 합니다.(Mysql Binlog를 이용하든지, 서버 로직에서 두 군데를 쓰든지…)
  2. 본문에 사용량이 많아지면 메모리 파편화가 일어난다고 하였는데(보통 디스크나 메모리의 경우 영속성이 있어야 성능이 잘나오는걸로 알고 있습니다.) 해당 파편화를 줄이는 알고리즘이나 파편화가 일어난 경우 해당 데이터를 재배치를 하는건가요?
    1. 레디스의 메모리 파편화는 다른 장비로 이전하는 수 밖에 없습니다. 보통 메모리 파편화가, 잦은 메모리 할당과 해제로 인해서 발생하므로, 장비 이전을 하면, 삽입만 대량으로 발생하니, 단편화 이슈가 조금 덜합니다. 보통 이런 경우 메모리를 2배로 늘린 장비로 이전합니다. 이전 과정은 간단하지만, 모니터링이 필요합니다.
    2. 말씀하신것 처럼 해당 데이터를 재배치 하는 것은 현재 레디스 상황에서는 쉽지는 않습니다. 재배치를 해봐도, 메모리 상황이 바로 좋아지는 것이 아니라, jemalloc에서 내부적으로 관리하는 매커니즘과 섞여서, 좀 외부에서 알기 어렵습니다.
  3. 서버 아키텍처는 캐쉬의 경우 여러 종류의 캐쉬를 두어 각 캐쉬별 역할을 구분하게 되어지는데 레디스도 그런 방식을 차용하고 있는건가요?
    1. 레디스가 내부적으로 그렇게 나누는 것은 아니고, 캐시를 사용하는 비지니스 로직에서 보통은 종류를 나눠서 사용하는 것이 제 경험상 메모리 사용량이나 파편화면에서 유리했습니다.(보통 그렇게 많이 쓰구요.)
    2. 통합 캐시(그냥 다 때려박는 형태)의 경우는 아이템별 메모리 사이즈의 차이가 커서 파편화를 더 가속화 시키는 측면이 있습니다.
  4. 이슈를 대비하여 서버 대수만 늘려야한다면 아키 설계가 어려울듯 한데 아키 설계는 보통 어떻게?
    1. 클라우드냐, 자체 IDC냐에 따라서 고려해야 할 것들이 좀 바뀝니다. 일단, 공통적으로 서비스의 Configuration이 Dynamic 할 수 있어야 합니다. 뭘 쓰는지는 크게 중요하지 않지만, 서비스를 내리고 올리는 형태가 아니라, 특정 보드에 설정을 바꾸면, 그게 전체 서버에 자동으로 반영되서, 서비스를 중단하지 않을 수 있어야 합니다. 서버의 추가나 제거도 마찬가지 입니다.
    2. 그런 아키텍처가 구성이 되면, 이제 IDC냐 클라우드냐에 따라서 고민할 것이 네트웍 밴드위스와 상면의 이슈가 있습니다. 개발자 입장에서는 네트웍 스위치의 밴드위스를 고려하지 않는 경우가 있는데, 이럴 경우, 큰 문제를 일으킬 수 있습니다. 상면 위치도 마찬가지입니다. 미리 잘 고민 안하면, 장비가 추가가 안되서, 해당 캐시만 다른 IDC에 넣어야 하는 경우도…(레이턴시가…)
  5. 레디스 서버 한대 다운시 처리는 어케 하는지요
    1. 레디스 서버 한대 다운시는… 여러 가지 방법이 있습니다. 자동 failover를 원하시면 sentinel 을 쓰든지 자체로 간단한 agent 를 만들어서 하는 방법이 있습니다. 이걸 vip, dynamic dns랑 잘 활요하면 클라이언트 입장에서는 크게 신경을 쓰지 않게 auto failover 를 제공할 수도 있습니다.