Sunday, October 26, 2008

Backtracking

백트래킹은 주어진 어떤 집합에 대해 조건을 만족하는 모든 부분집합(subset)을 구하는 정형화된 알고리즘이다.

/*
a[] : 답중 하나가 되는 부분 집합을 저장할 공간
n : 전체 집합의 크기
k : 현재 집합의 크기
candidates[] : 조건들 (예, 포함되거나 안되거나)
*/
void process_solution(int a, int k)
{
for (int i = 1; i <= k;)
if (a[i] == 1) printf ("...", i);
}
void construct_candidates( ... c, *nc)
{
c[...] = condition
...
*nc = X; // number of conditions
return;
}
backtrack(a[], k, n)
{
if (k == n)
process_solution(a, k);
else
k++;
construct_candidates(c, &nc);
for (int i = 0; i < nc; i++)
a[k] = c[i]; // set condition
backtrack(a, k, n);
}
int main()
{
a = arr[MAXSIZE];
backtrack(a, 0, n);
}

Minimizing Memory Cost

프로그램이 사용하는 메모리를 절약하기 위한 방법들에 대해 정리해 보자.
  • 일단 단순해져야 한다.
    메모리의 구조를 단순하게 하면 크기도 줄어들고 실행속도도 빨리질 수 있다. (세금 계산 테이블을 메모리에 넣는 대신 이를 표현하는 하나의 함수를 사용할 수 있다)
  • 메모리 절약을 위해 사용되는 기법들은 아래와 같다.
    • Sparse data structure
      는 대부분의 엔트리가 같은 값을 가지는 데이터 구조를 의미하는데, 이를 리스트와 같은 자료구조를 사용하면 메모리를 절약할 수 있다. 혹은 같은 값을 가지는 부분만 떼어 내어 별도로 저장하므로 같은 값을 중복으로 저장하는 overhead를 줄일 수 있다.
    • 데이터 압축
      은 말그대로 압축을 하거나, 한 자료 타입안에 여러 데이터를 동시에 넣는 방법이다. (두 지점사이의 거리를 나타내는 행렬, 좌표 등)
    • 할당 정책의 변경
      을 통해 메모리를 절약할 수 있다. 공간을 정적으로 미리할당하지 않고 필요할 때 동적으로 할당해주는 것을 예로 들 수 있다.
  • 물론 메모리 절약에서도 Amdahl's law 가 적용된다. 특정 데이터 구조가 전체 메모리 공간의 대부분을 차지하는 경우를 찾아 개선하면 효율적으로 메모리를 절약할 수 있다.
  • 때로는 메모리 절약을 위해 성능을 희생해야하는 Trade-off 가 발생한다.

Wednesday, October 22, 2008

Using Macro is not always faster.

함수 콜하는 부분을 매크로로 치환하면 일반적으로 성능이 빨라진다. 그러나 항상 그렇지는 않다.


#define MAX(a,b) ((a) > (b) ? (a) : (b))

float arrmax(int n)
{
if (n == 1)
return x[0];
else
{
return MAX(x[n-1], arrmax(n-1));
}
}

위 코드는 매우 느리다. 배열의 최대값을 리턴하는 코드인데, 배열의 크기가 30개만 넘어가도 실행 속도가 수초이상 걸리게 된다. 왜냐하면 매크로 부분이 x[n-1] > arrmax(n-1) ? x[n-1] : arrmax(n-1) 로 치환되면서 수행시간이 (함수가 호출되는 횟수가) 매크로 대신 함수로 구현할 때 보다 O(n) 에서 O(2^n) 이 되기 때문이다. 재귀적 호출에서 이런 실수는 상당한 성능저하를 낳게 되니 주의 하자.

Tuesday, October 14, 2008

Code Tuning

코드 튜닝은 기본적으로 구조에 적합한 효율성을 얻는데서 만족해야지 지나친 최적화나 그 반대의 경우로 치우치면 곤란하다.
  1. Hotspot (병목) 찾아내기
  2. 그 부분 최적화 하기
의 식으로 진행하는데, 코드 튜닝의 팁&예를 들면 아래와 같다.

나눗셈은 다른 연산보다 비용이 많이 든다. 그래서 가능한 경우 아래처럼 할 수 있다고 한다.


k = (a+b) % n; // 요거 대신
k = a + b; if (k>=n) k -=n; // 요렇게

경우에 따라 2배의 성능 차이가 있다고 한다.

메모리 접근 빈도나 계산 시간 중 오래 걸리는 것을 개선해라

매크로가 항상 성능을 개선시키는 것은 아니다. recursive하게 호출되는 경우 책에서는 경우에 따라 1,000배까지 느려진다고 한다. 이건,.. 테스트 해봐야 겠다. (물론 매크로를 써서 성능이 향상된 경우도 있다.)

for loop 의 비교횟수를 줄여 5% 성능향상을 가져올 수도 있다. 좀, 심하긴 한데,


int search(int t) {
hold = x[n];
x[n] = t;
for (i = 0; ;i++) {
if (x[i] == t)
break;
x[n] = hold;
if (i == n)
return -1;
else
return i;
}
요렇게 해서 for 루프에서 매번하던 비교연산을 줄일 수 있다.

그리고, loop unrolling으로 속도를 개선할 수 있다. loop를 말그대로 조금 펼쳐서 pipeline이나 Multicore 에서 돌아가는 점을 살려 병렬로 실행시킬 수 있다. (요건 컴파일러에서도 어느정도 지원해줄 것 같다.)

위에서 소개된 방법들의 이름으로 정리를 해보면,

  • Exploit common cases 자주쓰이는 경우를 캐시하는 것과 비슷한 방법이고,
  • Exploit an algebric identity 요건 대수적인 최적화를 한다는 것이고,
  • Collapsing procedure hierarchy 는 함수콜 대신 매크로, 인라인 쓰는 것이고
  • Loop unrolling 은 아까 했고.
  • Data structure augmentation 은,. 설명하기 귀찮다. ㅡ.ㅡ;.

Friday, October 10, 2008

Dijkstra Algorithm

다익스트라 알고리즘은 가중치를 가지는 양방향 그래프에서 특정 정점에 대한 나머지 정점들로의 최단거리를 구하는 알고리즘이다.
가중치를 가지는 간선을 가지는 그래프를 G[V,E] 라하고 정점들의 집합을 S, Q두개로 가질 수 있다고 할때 알고리즘은 아래와 같이 기술될 수 있다.

while Q is not empty
S = empty
Q = G[V,E]
u = extract_min(Q);
for edge from u
relax(edge, u)

간단히 기술하면, 먼저 시작점 s 로부터 걸리는 경로 값을 각 정점에 기록할 수 있다고 할때, 모든 정점에 infinite 값 (아주 큰값)을 넣은 후 모든 정점들을 Q에 넣는다(s 에는 값 0을 넣는다). 그리고 Q 에서 최소 값을 가지는 정점을 하나 꺼내어 이 정점이 가지는 모든 간선들에 대해 relax를 수행한다. relax 란 간선들과 연결된 정점들에 최단 경로값을 갱신해 넣어주는 것을 말한다(이미 Q에서 빠져나온 노드들에 대해서도 갱신한다). 이 과정을 Q에 정점이 없을 때까지 반복한다.

Thursday, August 28, 2008

Collaborative Filtering

Collaborative Filtering

유사한 취향을 가진 사람들의 작은 집합을 만드는 것. 일종의 클러스터링.

관련 논문으로 "Using collaborative filtering to weave an information tapestry" 이 있음.

  • Similarity score 계산
    사람(혹은 아이템) 간의 취향이 얼마나 비슷한지 정도를 계산할 수 있는데, 아래의 방법들이 있음
  • Euclidean distance score
    각각의 항목들을 축으로 놓고 특정 사람에 대한 항목별 선호도를 점으로 표시하면 두사람간의 거리를 계산하여 유사도를 구할 수 있는데 이를 유클리디안 거리점수 라고 한다. 항목이 두개 (x, y)인 경우 두 사람 A(x1, y1), B(x2, y2) 간의 거리는 y = sqrt( (x1 - x2)^2 + (y1 - y2)^2 ) 이다. 마찬가지로 n 개의 항목에 대한 유클리디안 거리점수를 계산하면 아래처럼 표시될 수 있다.

    y = sqrt( (a1 - a2)^2 + ... + (n1 - n2)^2 )

    일반적으로 이렇게 구한 거리 d 를 1/d식으로 활용하여 서로 유사할 수록 높은 점수를 주는 방식으로 사용한다.
  • Pearson correlation score
    두개의 데이처 집합이 한 직선으로 잘 표현되는 정도를 나타낸 것이 상관계수인데, 정규화되지 않은 데이터에 대해 좋은 결과를 제공한다. 각각의 값이 점으로 표시된 좌표에서 모든 점들과 가장 가까운 직선을 그릴 수 있는데 이를 최적맞춤선(best-fit line)이라고 한다. 여러 항목들에 대한 두사람의 선호도 데이터를 가지고 있다면 이 두사람을 각 좌표의 축에 놓고 best-fit line을 그릴 수 있다.
    이 직선을 통해서 대체적으로 누가 더 많은 점수를 주었는지를 파악할 수도 있는데, 이를 grade inflation이라고 한다. 한쪽이 더 높은 점수를 꾸준하게 주었어도 선호도가 비슷하다면 직선으로 잘 표현될 수도 있다.
    때문에 Euclidean distance에서는 한쪽이 전체적으로 낮은 점수를 주었으면 두 사람의 유사도가 낮게 나오는 반면 Pearson correlation score에서는 이를 유사한 것으로 뽑아낼 수 있다.
    아래의 두 사람의 데이터에 대한 Pearson correlation score를 뽑아낸다고 하면,

    m1[] = { a1, a2, ... , an}
    m2[] = { b1, b2, ... , bn}

    아래와 같은 식으로 상관계수 값을 도출할 수 있다.

    sum1 = a1 + ... + an
    sum2 = b1 + ... + bn

    sq_sum1 = a1^2 + ... + an^2
    sq_sum2 = b1^2 + ... + bn^2

    mul_sum = a1 * b1 + ... + an * bn

    v1 = mul_sum - (sum1 * sum2 / n)
    v2 = sqrt( (sq_sum1 - (sum1^2) / n) * (sq_sum2 - (sum^2) / n) )

    return v2 == 0 ? 0 : n / v2

    값은 -1 ~ 1 사이이고 1은 모든 항목에 같은 점수를 준 것이다.

Thursday, August 21, 2008

Const pointer & pointer const

const pointer refers const variable.

pointer const refers variable constantly(Setting it to point another variable is not possible).

Wednesday, August 13, 2008

Advanced Generic Handle - Copy On Write

Generic Handle Class는 여러 클래스를 동일하게 다룰 수 있지만 메모리 복사가 많이 일어나는 오버헤드가 있다. Reference Count를 사용한 Generic Handle Class는 값을 항상 참조만 시키기 때문에 s2 = s1 처럼 대입하면 s2의 값을 바꾸었을때 s1의 값이 항상 바뀐다(같은 객체를 참조하니까). 때문에 경우에 따라 참조하고, 경우에 따라 복사를 하는 더 나은 형태의 Generic Handle Class 가 있으면 좋겠다.

즉, s3 = s2 = s1처럼 대입하면 실제 복사는 일어나지 않고 s3, s2가 s1의 레퍼런스만 가지고 있게 하다가, s3에 다른 새로운 값을 대입하거나 내부 멤버를 변경하는 작업이 일어날 때 비로소 s1의 멤버 값들을 복사한 후 s1에 대한 레퍼런스를 끊어 별개의 객체로 동작하게 하는 것이다.

linux memory management의 COW(Copy-On-Write)처럼 변경 사항이 일어날 때 비로소 복사를 하는 것이다.

실제 이러한 클래스를 구현하는 방법은 기존의 Reference Count를 사용하는 Generic Handle Class에 아래와 같이 reference count를 체크한 후 복사를 진행하는 멤버 함수를 추가한 후, 멤버를 변경시키는 함수 호출시 이 멤버함수를 실행시키면 된다.


template class Ptr {
public:
void make_uniue() {
if (*refptr != 1) {
--*refptr;
refptr = new size_t(1);
p = p ? p->clone() : 0;
}
}
...

Advanced Generic Handle - Reference Count

Generic Handle Class를 만들어 사용하게 되면 대입 연산과 같은 여러 작업을 진행할 때 불필요한 메모리 복사가 많이 일어나 오버헤드가 된다. 값을 읽기만 하기 위해 대입하는 경우 값을 복사하지 않고 레퍼런스만 넘겨주면 이를 줄일 수 있는데, 핸들 클래스를 통해 참조되는 값들은 동적으로 생성된 것들이기 때문에 해제를 하려면 자신을 참조하고 있는 객체가 몇개인지 확인해 보고 참조하고 있는 값이 없을 때 해제하면 된다.

이를 위해 제네릭 핸들 클래스에서 사용하는 방식이 reference count다. 복사나 대입 연산이 발생하는 경우 핸들 클래스에서 가지고 있는 reference count를 증가시키고 반대의 경우 감소시키는 방식으로 카운터를 유지하다가 레퍼런스가 없게 될 때 최종적으로 소멸시키게 된다.

Tuesday, August 12, 2008

Generic Handle Class

Handle Class는 기본 클래스에서 파생된 여러 클래스를 레퍼런스나 포인터를 통해 모두 다룰 수 있도록 캡슐화 해준다. 제대로 짠다면 이러한 Handle Class는 다루는 클래스에 대해 최대한 독립적이여야 한다. 그래서 다루는 클래스 자체를 탬플릿으로 선언하여 Handle Class를 구현하는데 이를 Generic Handle Class라고 한다.

핸들을 사용하기 않고 직접 저수준의 포인터를 사용하게 될 경우 아래와 같은 잠재적인 문제가 있다.

  • 포인터 복사만 하면 객체는 복사가 안된다.
  • 포인터 소멸시켜도 객체는 소멸 안된다.
  • 반대로 포인터를 두고 객체만 소멸시키면 Dangling Pointer가 된다.
  • 포인터 만들고 바인딩 안하고 쓰면 ... 알 수 없는 동작을 한다.

Generic Handle Class는 기본적으로 아래와 같은 기능을 제공한다.

  • Handle을 특정 객체를 참조하는 값으로 생각하면 된다.
  • 객체를 복사할 수 있다(복사 생성자, 대입연산자).
  • 바인딩 여부를 알 수 있다(bool() 연산을 정의하면 됨).
  • virtual 함수 호출을 통해 각 클래스별 메소드를 호출할 수 있다.

우리가 직접 포인터/레퍼런스를 쓰지 않고 핸들 클래스를 사용하기로 했기 때문에 당연히 이후부터는 객체를 포인터를 통해 직접 접근하면 안된다. 그리고 메모리 관리도 Handle Class에서 자동으로 해주므로 Handle을 소멸시키면 Handle에 연결된 객체도 같이 소멸된다.


template<class T> class Handle {
public:
Handle() : p(0) { }
Handle(const Handle& s) : p(0) { if(s.p) p = s.p->clone(); }
Handle& operator=(const Handle&);
~Handle() { delete p; }

Handle(T* t) : p(t) { }

operator bool() const { return p; }
T& operator*() const;
T* operator->() const;

private:
T* p;
};

template<class T>
Handle<T>& Handle<T>::operator=(const Handle& rhs)

if (&rhs != this) {
delete p;
p = rhs.p ? rhs.p->clone() : 0;
}
return *this;
}

template<class T>
T& Handle<T>::operator*() const
{
if (p)
return *p;
throw runtime_error("unbound Handle");
}

template<class T>
T* Handle<T>::operator->() const
{
if (p)
return p;
throw runtime_error("unbound Handle");
}


A를 B가 상속받은 경우, Handle <A> h(new B); 식으로 핸들을 생성하면 B클래스가 생성되어 핸들클래스의 포인터에 바인딩된다(virtual 함수를 사용할 수 있다).

operator* 를 정의하므로써 핸들이 가지고 있는 클래스 포인터로 클래스 레퍼런스를 반환하는 역할을 한다.

operator->는 이항연산자 인줄 알았는데 아니란다 ㅡ.ㅡ; 단지 이걸 통해서 오른쪽에 있는 멤버를 접근할 수 있게 해준덴다. 즉, x->y 인 경우 (x.operator->())->y 나 x.p->y와 같덴다. 요건 좀 비직관적인 듯하다.

아무튼 이 두 연산을 통해 Dynamic Binding이 가능해진다. 앗싸.

나는 generic handle class를 만들면 handle class가 필요없는 줄 알았다. Accelerated C++의 내용을 대강 정리해서 어쩌다 제네릭 핸들 클래스를 만들게 되었는지 요약해보면 아래와 같다.

  1. 클래스를 만들었다.
  2. 비슷하지만 다른 클래스도 필요하게 되었다.
  3. 두 클래스를 하나의 코드로 다룰려고 dynamic binding을 사용하려니 포인터/레퍼런스 사용이 복잡하다.
  4. 그래서 두 클래스를 사용하는 핸들 클래스를 만들고 이 핸들을 사용하기로 했다.
  5. 근데 핸들 클래스에도 포인터를 사용하려니 짜증난다.
  6. 포인터를 사용하는 부분만 제네릭 핸들 클래스로 빼버렸다.
  7. 결국 두 클래스 -> 제네릭 핸들 클래스 -> 핸들 클래스 -> 일반 코드 식으로 접근하도록 하여구현하게 되었다.

Monday, August 11, 2008

Basic concepts

상속
class drivedClass : public baseClass { ... }

public
interface의 일부로 상속한다는 의미 not as an implementation

protected
기본 클래스의 private멤버에 접근하고 싶을때 protected에 선언

baseClass::function
같은 이름의 기본클래스의 함수에 접근하고 싶을때

Polymorphism(다형성), binding
기본클래스의 레퍼런스를 인자로 받는 함수에서 파생클래스를 넣어도 되는 식
- 파생클래스의 기본 클래스 부분만 사용된다. (1)

virtual
(1)에서 파생클래스의 것을 자동으로 사용하게 해주고 싶을때 사용
클래스의 인자가 레퍼런스나 포인터로 호출된 경우에만 가능.

일반적으로 파생클래스에서 재정의 되는 virtual함수들은 기본클래스의 함수와 동일한 타입을 리턴해야하지만, 기본클래스의 virtual함수가 *this를 리턴하는 경우 파생클래스에서도 기본클래스의 포인터가아닌 파생클래스의 포인터(*this)를 리턴할 수 있다.

virtual function의 경우 기본/파생 클래스 함수들의 매개변수 갯수 타입이 다르면 별도의 함수로 동작하기 때문에 이를 고려해서 구현해야한다. 매개변수 개수가 다른 경우에는 아래와 같은 식의 구현을 통해 virtual function을 사용할 수 있다.

void BaseClass::func(double d1, double = 0) { ... }
void DerivedClass::func(double d1, double d2) { ... }

static binding
호출되기 전에 타입이 결정되어 그 타입으로 사용됨

dynamic binding
호출될 때 타입이 결정되어 그 타입으로 사용됨
레퍼런스나 포인터로 전달할 때 이루어짐 (실제 전달되는 값을 알지 못하므로)

virtual destructor
포인터나 레퍼런스에 대한 객체의 타입을 모르지만 delete 하고 싶은 경우 소멸자를 virtual로 선언하여 각 객체에 맞는 소멸자를 호출해주게 하는 것

Rule of three
복사생성자, 대입연산자, 소멸자 : 는 붙어 다닌다.

static member function
클래스의 멤버 함수로 호출되더라도 객체(this)의 멤버와 연관이 없는 작업을 수행하는 함수.
ex. static void func (classA& c1, classA& c2)

handle class
서로 상속관계를 가진 여러 클래스들을 하나의 클래스 처럼 사용하고자 할 때 인터페이스 역할을 하도록 하나의 클래스를 만들어 각 경우에 맞는 클래스의 객체를 생성하고 생성한 객체의 포인터(혹은 레퍼런스)를 가지게 하는데, 이를 핸들 클래스 라고 한다. 이 때 포인터는 기본클래스의 포인터를 가진다.
포인터를 가지고 연산하기 때문에 복사생성자, 대입연산자, 소멸자가 필요하다.

virtual clone function
복사 생성자의 경우, 핸들클래스는 생성한 클래스의 포인터를 가지고 있기 때문에 어떤 클래스를 생성해서 가지고 있는지 모르므로, 복사될 핸들 클래스의 포인터에 어떤 클래스를 생성해서 대입해야할지 모른다. 그래서 자기 자신을 복사하는 clone 함수를 각 클래스 별로 정의하고, 기본클래스에서 이를 virtual 로 선언해서 핸들 클래스에서 사용시에 각 타입에 맞는 방식의 clone함수를
사용해 복사후 핸들클래스의 포인터로 넘겨줄 수 있다.

ex. 대부분 각 클래스들은 아래와 같은 식으로 clone()을 만들어 놓는다.
protected:
// virtual 은 기본클래스의 경우에만.
virtual BaseClass* clone() const { return new BaseClass(*this); }

대신 핸들클래스가 이를 사용할 수 있도록 기본클래스의 friend로 등록되어야 한다.

핸들 클래스에서 기본클래스의 포인터를 가지고 있기 때문에 파생클래스의 clone에 대한 접근은 virtual call로 이루어 진다. 때문에 핸들클래스만 기본클래스의 friend 로 등록되면 된다.

friend
함수가 특정 클래스의 protected영역에 접근할 수 있도록 할 때 클래스에 이 함수를 friend로 등록할 수 있다. 클래스가 friend로 등록된 경우 클래스의 모든 멤버가 대상 클래스의 friend 가 된다.

friend관계는 상속되지 않는다.

Tuesday, June 24, 2008

Utility functions


struct hostent {
char *h_name;
char **h_aliases;
int h_addrtype; /* AF_INET */
int h_length; /* h_addr_list length */
char **h_addr_list;
}

위 hostent의 h_addr_list는 network byte order로 된 in_addr인데, h_addr_list는 char ** 이므로, 이를 실제로 사용할 때는 inet_ntoa(*(int *)h_addr_list[i]) 식으로 하면 4byte를 읽어 inet_ntoa에 넣게 되므로 값을 확인해볼 수 있다. 아래는 각 함수별 설명이다.

gethostbyname(...) 은 호스트 이름으로 hostent 를 가지고 오는 함수이다.

gethostbyaddr(...) 는 IP주소로 hostent를 가지고 오는 함수이다

getsockopt(...), setsockopt(...) 는 소켓 옵션 관련 함수이고, 앞에서 했고,..

getsockname(...) 은 bind된 sockaddr 정보를 얻어오는 함수이다 (자동 할당된 포트 번호 확인 시 사용)

getpeername(...) 은 반대로 연결된 상대편의 sockaddr정보를 얻어오는 함수이다

getservent(), getservbyname(), getservbyport() 함수들은 /etc/services파일을 가져오는 함수들이다(전체 다 가져오거나, 서비스 이름으로 찾거나, 포트 번호로 찾는 함수)


getprotoent(), getprotobyname(), getprotobynumber() 역시 마찬가지로 /etc/protocols 파일을 가져오는 함수들이다.


위 두그룹들은 각각 serverent, protoent 구조체를 알아야 한다.


주소변환 함수 그룹들은 지난번에 기록한것 같은데 이름만 다시 정리하면, inet_addr/inet_aton, inet_pton, inet_ntoa, inet_ntop 이다. pton, aton의 차이는 리턴되는 값을 static공간에 담아주냐 아니냐의 문제인데, reentrant를 고려하여 제공되는 함수가 pton, ntop 군이니 필요할 때 구별해서 쓰면된다.

Socket, options

소켓 사용시 여러 옵션을 줄 수 있는데, 아래 함수를 통해 set, get이 가능하다.

int getsockopt(int s, int level, int optname, void *optval, socklen_t *optlen);
int setsockopt(int s, int level, int optname, void *optval, socklen_t *optlen);

설정할 수 있는 옵션은 영역이 매우 다양한데(이를 테면, TCP에서의 옵션이라던가, IP레이어에서의 옵션이라던가 등...), 어느 영역에서의 옵션을 설정할 것인지를 두번째 인자인 level에서 선택할 수 있다. 몇개의 옵션들은 아래와 같다.
  • SOL_SOCKET
    • SO_BROADCAST
    • SO_REUSEADDR
      • TCP의 TIME_WAIT상태의 소켓을 다시 재사용할 수 있게 해주는 옵션으로 서버쪽에서 active close해서 TIME_WAIT상태로 빠지면 이 시간동안 listen이 실패하므로, 바로 listen할 수 있도록 TIME_WAIT상태에서소 소켓을 사용할 수 있도록 하기 위해 사용한다.
    • SO_LINGER
      • struct linger { int l_onoff; int l_linger; } 를 사용한다.
      • 데이터를 전송 후 끊기 위해 기다리는 시간을 l_linger에 지정할수 있는데, 0인경우 버퍼를 없에버리고 바로 close하며 client 쪽에도 RST를 보내서 TIME_WAIT되지 않고 바로 끊도록 한다. (aborty shutdown, aborty close. 0이 아닌 경우라면 graceful close/shutdown)
    • SO_KEEPALIVE
      • 일정시간마다 연결상태 확인
    • SO_OOBINLINE
    • SO_RCVBUF
      • 수신 버퍼크기 조정(실제로는 지정한 값의 두배가 잡힘). 자동으로 조정되는 경우에는 설정할 수 없는 경우도 있음
    • SO_SNDBUF
    • SO_RCVTIMEO
      • blocking 함수를 사용하는 경우(recv, ...) block에서 깨어날 시간을 지정할 수 있음. timeval로 지정하면 됨. timeout으로 빠져나오면 -1이 리턴되고, errno가 EAGAIN이 됨 (아래 SNDTIMEO도 마찬가지)
    • SO_SNDTIMEO
    • SO_RCVLOWAT
      • watermark인데 I/O를 발생할 최소단위의 크기를 지정한다. default로 1이다. (버전에 따라 지원정도가 다르다)
    • SO_SNDLOWAT
    • SO_TYPE
    • SO_ERROR
  • IPPROTO_IP
    • IP_TTL
    • IP_MULTICAST_TTL
    • IP_ADD_MEMBERSHIP
    • IP_DROP_MEMBERSHIP
    • IP_MULTICAST_LOOP
    • IP_MULTICAST_IF
  • IPPROTO_TCP
    • TCP_NODELAY
      • 1이면 Nagle Algorithm을 사용안함
    • TCP_MAXSEG
      • MSS크기 조절함(잘못 조절하면 ,... ㅡ.ㅡ;)

UDP Broadcasting

매우 간단하다. 소켓 옵션에 SO_BROADCAST를 주고 수신측 주소에 INADDR_BROADCAST를 주면된다. 특정 네트웍으로 broadcast하고 싶으면 해당 네트웍 주소를 주면된다. 소켓 옵션에 값을 줄때는 아래처럼 setsockopt를 사용한다.

int sockopt = 1;
if (setsockopt(fd, SOL_SOCKET, SO_BROADCAST, &sockopt, sizeof(sockopt)) == -1) {
/* Handle error */
}

TCP Options

TCP의 성능 향상을 위해 사용되는 여러가지 방법들을 정리해보자.

TCP autotuning은 소켓 버퍼의 크기를 동적으로 조절하는 기능인데, 2.6.8커널 이후 버전에서 지원되며, 아래 값들을 통해 설정할 수 있다.

  • net.ipv4.tcp_moderate_rcvbuf : 수신쪽의 autotuning 설정

  • net.ipv4.tcprmem : 수신 버퍼의 최소/기본/최대값 (송신쪽은 ...wmem)

  • net.core.rmem_max : 지정할 수 있는 수신 버퍼 크기의 최대값 (송신쪽은 wmem)


값들은 sysctl 커멘드로 확인할 수 있다.

그외, TCP timestamp 는 RTT 측정 오차를 줄이는 방법이고. WSCALE이라고 16bit로 제한된 윈도우 사이즈를 늘려주는 옵션이다.

그리고.. 여러개의 패킷 유실에 대해 ACK를 개별적으로 보내주는 selective ack도 있다.

Monday, June 23, 2008

TCP vs UDP

ALSP 책에서는 segment와 fragmentation을 구별하여 정의하고 있다. 둘다 데이터를 분할하는 것이지만 후자는 재결합이 가능하도록 쪼개는 것이고, 전자는 재결합과는 상관없이 데이터를 쪼개는 행위 자체를 말한다. TCP에서는 IP레이어로 내려가기 전에 segment 단위로 데이터를 쪼개는데, 이때 사용되는 크기가 MSS(Maximum Segment Size)이다. TCP에서는 이렇게 미리 데이터가 분할되어 내려오기 때문에 나중에 MTU 사이즈에 의해 재 분할 되지 않으며, UDP의 경우 IP레이어에서 MTU사이즈로 분할 된다.

TCP는 그 이름이 Transmission Control Protocol인 것처럼 헤더에 제어 flag이 붙는데, 이들은 URG, ACK, PSG, RST, SYN, FIN 으로 구성되어 있다.

UDP의 경우는 별도의 control flag 이 없어서 단순하게 사용 가능하나, 전송하는 데이터그램이 버퍼크기보다 작아야 함을 주의해야 한다. 버퍼보다 큰 데이터그램이 들어오는 경우 Drop되기 때문이다. 이것은 netstat -s 로 UDP overflow가 있는지 확인해 보므로써 알 수 있다.

UDP

UDP는 별도의 연결 과정이 없다. 때문에 매번 보낼때 송수신 주소를 담아서 보내고 받는다. 그리고 broadcast, multicast 식으로 한번에 여러 곳으로 데이터를 송신할 수 있다. 일단 bind()로 바인딩 후 sendto(), recvfrom()으로 주고 받는다. 송수신이 완료되면 close(), shutdown()으로 소켓을 닫는다. 연결이 없어서 server, client 구분이 없다. 간단하다.

int sendto (int s, const void *msg, size_t len, int flags, const struct sockaddr *to, socklen_t tolen);
int recvfrom(int s, void *buf, size_t len, int flags, struct sockaddr *from, socklen_t *fromlen);

인자는, 뭐 대충,.. 소켓, 데이터, 데이터길이, 옵션, 송(수)신 주소, 주소 길이.. 식이다.

Friday, June 20, 2008

TCP Status

TCP연결시에는 알다시피 3way handshaking을 한다. close시에는 client, server 가 각각 FIN을 보낸 후 ACK를 받는다(총 4번의 트랜젝션).

TCP연결에는 여러개의 상태가 있는데, netstat으로 확인할 수 있는 상태들에 대해 간단히 정리해보면,

  • 서버에서 listen()이 호출되면 상태는 LISTEN으로 바뀐다.

  • 이 때 client에서 SYN을 보낸 후 SYN_SENT로 상태가 바뀌면

  • 서버에서 이를 받고 SYN_RCVD로 바뀌고 SYN ACK를 보내준다.

  • 그리고 client에서 SYN을 다시 받게 되면 비로소 ESTABLISHED로 바뀐다.

  • 이 후 send(), recv()군의 함수들로 계속 통신을 하다가

  • client에서 close()호출로 인해 FIN 을 보내고 FIN_WAIT1상태가 되면

  • 서버에서 이를 받고 ACK를 보낸 후 CLOSE_WAIT으로 상태를 바꾸고

  • client에서는 이를 받으면 FIN_WAIT2로 바뀌게 된다.

  • client에서 close할 준비가 끝났으므로, 이제는 서버에서 close()가 호출되면 FIN이 전송되고, 상태는 LAST_ACK이 된다.

  • client에서는 ACK를 보낸 후 TIME_WAIT상태가 되고, Maximum Segment Lifetime x 2시간 정도 기다리다가 소켓을 닫는다.

  • 서버에서는 이 ACK를 받고 CLOSED로 상태가 바뀐다.


close시 일반적으로 client에서 먼저 FIN을 보내고(active close), 서버는 이를 받으면 recv()에 EOF가 전달된다. 서버는 자신이 보낸 FIN에 대한 ACK를 받아야 close된다(passive close).

TIME_WAIT이 필요한 이유 client에서 ACK를 보냈는데, 서버가 못받으면, 서버는 LAST_ACK상태에서 일정시간이 지나도 ACK가 안오므로 FIN을 다시 보낸다. 이때 client가 이미 close 한 상태이거나 같은 포트번호로 다른 접속을 시도하고 있다면 처리할 수 없으니까, TIME_WAIT을 두어 다시 들어온 FIN에 대해 ACK를 주는 것이다. (client에서는 그래서 재접속시 다른 포트 번호를 받게 된다).

Friday, June 6, 2008

Threads, condition variables

Thread를 동기화하는 다른 방법 중의 하나로 Condition variable을 사용하는 것이 있다. condition variable을 잘 사용하면 race-free한 thread 코드를 만들 수 있다.

condition variable자체는 mutex 에 의해 보호된다. 때문에 condition 상태를 바꾸기 위해서는 먼저 mutex lock을 걸어줘야한다. condition variable(이하 cv) 초기화는 두가지 방법이 있는데, cv가 static이면 PTHREAD_COND_INITIALIZER를 넣어주면 되고 dynamic 이면(동적 할당되었으면) pthread_conf_init()을 쓰면된다. 사용이 끝나면 pthread_cond_destroy()를 호출해준다.

#include <pthread.h>
// 0 for OK
int pthread_cond_init(pthread_cond_t *restrict cond, pthread_condattr_t *restrict attr);
int pthread_cond_destroy(pthread_cond_t *cond);

cv를 체크하는 방법으로는 아래의 두 함수를 사용할 수 있다. 아래 wait함수를 호출할 때는 인자로 넣어주는 mutex가 lock된 상태여야 한다. 그러면 wait 함수 내부에서 cv를 기다리는 threads list에 함수를 호출한 thread를 넣고 mutex를 unlock한 후 wait상태에 들어가게 된다. wait하다가 condition 이 true가 되면 mutex를 lock한 상태로 리턴하게 된다. timedwait함수의 경우는 얼만큼 오래 기다릴지를 timespec으로 지정해줄 수 있다. timedwait의 경우 condition이 발생하지 않았는데 expire된 경우 lock을 한 상태에서 ETIMEOUT error를 반환한다.

#include <pthread.h>
// 0 for OK
int pthread_cond_wait(pthread_cont_t *restrict cond, pthread_mutex_t *restrict mutex);
int pthread_cond_timedwait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex, const struct timespec *restrict timeout);

wait 함수들은 condition이 발생했다는 것은 알려주지만 자신이 이를 처음으로 통보받았다고 보장하지는 않는다. (예를 들어 한개의 condition이 있고 4개의 thread 가 있다면 각각의 thread가 pthread_cond_wait()하다가 condition이 발생해서 pthread_cond_wait()을 빠져 나왔다면, condition이 발생한 것은 확실하지만, 제일 처음 이를 통보받은 thread가 condition과 관련된 부분을 변경했을 수도 있다는 것이다) 때문에 이를 위해 condition을 다시 체크해보아야 한다.

이번에는 반대로 condition을 변경해주는 부분을 생각해보자. 아래 함수들을 사용해서 두가지 방법으로 condition이 변경되었음을 알려줄 수 있는데, signal 은 기다리고 있는 thread중 하나만 wakeup시켜주고 broadcast는 모든 thread를 깨워준다.

#include <pthread.h>
// 0 for OK
int pthread_cond_sigal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);

아래 APUE 에서의 간단한 예제를 살펴보자.

#include <pthread.h>

// queue의 노드
struct msg {
struct msg *next;
/* ... */
}

struct msg *workq;
// condition variable
pthread_cond_t qready = PTHREAD_COND_INITIALIZER;
// mutex to protect c.v.
pthread_mutex_t qlock = PTHREAD_MUTEX_INITIALIZER;

void process_msg(void)
{
struct msg *mp;
while (1) {
pthread_mutex_lock(&qlock);
// 이미 lock했어도 아래 ...wait 에서
// condition variable을 등록 후 내부
// 적으로 unlock하기 때문에 block상
// 태가 된다.
while (workq == NULL)
pthread_cond_wait(&qready, &qlock);
// wait 에서 condition 이 바뀐 것을
// 통보 받고 lock된 상태로 빠져 나왔음
// 아래 enqueue_msg 에서 broadcast로
// 통보 했다면 여기서 queue가 비었는지
// 다시체크해야하나, 그렇게 할 경우
// thundering herd가 발생할 소지가 있음

// 원래 queue는 tail에서 값을 뽑아야 하는데,
// 여기서는 head에 넣었다가 head 에서 뽑는다
// (FIFO가 아니 LIFO,..stack이다..)
// 이유는... 글쎄 ㅡ.ㅡ;..
mp = workq;
workq = mp->next;
pthread_mutex_unlock(&qlock);
// processing msg here
}
}

void enqueue_msg(struct msg *mp)
{
pthread_mutex_lock(&qlock);
mp->next = workq;
workq = mp;
pthread_mutex_unlock(&qlock);
pthread_cond_signal(&qready);
}

Thread, manager worker model


Worker manager model 을 구현할 때 thread를 사용할 수 있다. 외부로 부터 요청된 job들을 관리하기 위해 manager는 일반적으로 queue를 사용한다. job 이 들어오면 어떤 thread가 처리해야할 지 판단한 후에 thread id와 함께 해당 job을 queue에 넣는다. 그럼 각각의 thread들이 queue를 보면서 자신에서 어떤 job이 assign되었는지 확인하고, 꺼내어 작업을 처리할 수 있다.
따라서 worker 나 manager 가 접근할 때 queue 가 lock 되어있어야 하는데, 이럴 때 mutex보다는 읽을 때는 shared mode 로 lock 할 수 있는 rwlock 을 사용한다.

Thursday, June 5, 2008

Thread, reader-writer locks

mutex는 잠금/해제 두가지 상태밖에 없다. 때문에 한 thread가 읽는 작업을 수행하는 동안 다른 thread들은 읽을 수 없다. reader-writer lock은 잠금의 경우가 read lock/write lock 두 가지 상태가 있기 때문에 여러 thread가 동시에 읽을 수 있다. 사용되는 함수들은 아래와 같다.

#include <pthread.h>

int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock, const pthread_rwlockattr_t *restrict attr);
int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);
// 0 for OK

int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);
// 0 for OK

int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_tryrwlock(pthread_rwlock_t *rwlock);
// 0 for OK

맨 위의 init/destroy 함수는 mutex를 만들때 사용하는 함수이고, rdlock, wrlock은 각각 읽기/쓰기를 lock하는 함수이다(lock될 때 까지 block되어 기다린다). tryrdlock, tryrwlock들은 non-block으로 동작하는 함수들이다.

rdlock으로 lock되어 있는 경우, shared mode로 lock된 것이고, wrlock으로 lock한 경우에는 exclusive mode로 lock한 것이다.

write lock이 된 상황에서 다른 thread들이 rwlock/wrlock 을 하려는 경우 lock이 풀릴 때까지 모두 block되는 반면, read lock이 걸린 경우에는 read lock을 거는 thread들은 바로 접근이 가능하게 되고, write lock을 시도하는 경우에는 걸려있는 모든 read lock들이 해제될 때까지 block 된다.

비동기 lock 함수들을 사용하는 경우 lock할 수 없는 경우 리턴 값으로 EBUSY에 해당하는 값을 반환한다.

Socket, getsockname

이미 binding 된 socket으로 부터 주소정보를 받아올 때 getsockname을 사용한다. 아래와 같이 사용하면 된다.

getsockname(sfd, (struct sockaddr *)&saddr, &len_saddr);

Wednesday, June 4, 2008

Socket, thundering herd problem

network 프로그래밍시 주의해야할 문제 중에 하나로 thundering herd problem이 있다. 천둥이 치면 소떼가 뛴다...는 상황을 비교해서 쓰는 말인데, 여러 thread/process 간에 공유된 자원이 있을 때 자원이 사용가능하게 되지마자 block되어 있던 모든 프로세스들이 깨어나지만 한 프로세스만 자원을 점유하고 나머지는 다시 block되어야 하므로 CPU time을 낭비하게 된다. Mutex 같은 lock을 통해 이런 문제를 해결할 수 있다고 하는데,.. 그런가 ㅡ.ㅡ;,..

Monday, June 2, 2008

Socket, code example

간단히 ... 잊지 않을 정도의 코드 예제를 적어본다.
server side

#include <unistd.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <sys/types.h>
#include <sys/socket.h>

int sfd, rsfd;
struct sockaddr saddr; // listener
struct sockaddr rsaddr;

sfd = socket(AF_INET, SOCK_STREAM, IPPROTO_IP);

saddr.sin_family = AF_INET;
saddr.sin_port = 10000;
saddr.sin_addr.s_addr = inet_addr("100.100.100.100");
// or inet_aton

bind(sfd, (struct sockaddr*)&saddr, sizeof(saddr));

listen(sfd, BACKLOG);

rsfd = accept(sfd, (struct sockaddr *)&saddr, &len_rsaddr);

recv(rsfd, rbuf, sizeof(rbuf), 0);

send(rsfd, sbuf, sizeof(sbuf), 0);

shutdown(rsfd, SHUT_RDWR); // or close

client side

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <sys/socket.h>

int sfd;
struct sockaddr saddr;

sfd = socket(AF_INET, SOCK_STREAM, IPPROTO_IP);

saddr.sin_family = AF_INET;
saddr.sin_port = 10000;
inet_aton("100.100.100.100", &saddr.sin_addr);
// or inet_addr

connect(sfd, (struct sockaddr*)saddr, sizeof(saddr));

send(sfd, sbuf, sizeof(sbuf), 0);

recv(sfd, rbuf, sizeof(rbuf), 0);

close(sfd); // or shutdown

Thread, mutex - deadlock/race condition avoidance

여러개의 thread가 같은 메모리에 접근할 때 발생할 수 있는 문제가 deadlock, race condition이다. deadlock을 만드는 가장 간단한 방법은 같은 mutex에 두번 lock을 거는 것이다. 혹은 두 thread A,B가 있고 mutex X,Y가 있을 때 A가 X를 lock하고 Y자원을 사용하고자 기다릴때 B가 Y를 lock하고 X자원을 사용하고자하는 경우 이런 상황이 발생한다. thread에서 이런 상황을 피하는 방법으로는 아래의 두가지가 있다.

  • 여러 mutex를 사용하는 경우 lock하는 순서를 항상 동일하게 한다. (위의 예라면 항상 X를 lock한 후 Y를 lock하는 식으로 정해서 deadlock을 피할 수 있다)

  • 자신이 사용하고자 하는 자원이 다른 thread에 의해 사용중인 경우 자신이 점유하고 있는 자원을 해제한 후 기다린다.


linux에서 사용가능한 mutex관련 함수로는 아래 것들이 있다.

#include <pthread.h>
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

mutex를 사용하기 위해서는 ..._init(), ..._destroy() 함수들을 사용해야한다. ..._init()함수 사용시 mutex의 종류를 정해줄 수 있는데, 아래와 같은 매크로로 지정할 수 있다.

  • PTHREAD_MUTEX_NORMAL : linux에서는 "timed" mutex이다.

  • PTHREAD_MUTEX_RECURSIVE : 여러번 잠글 수 있는 mutex

  • PTHREAD_MUTEX_ERRORCHECK : 에러 체크해주는 mutex

  • PTHREAD_MUTEX_MUTEX_DEFAULT : linux에서는 첫번째의 ..._NORMAL과 같다.


위에서 설명한 "timed mutex"는 기본 mutex인데, 중복으로 lock을 걸면 deadlock에 걸리고, 다른 thread가 lock한 상태에서 내가 풀려고 하면 undefined 상태가 된다. errorcheck 타입은 데드락의 경우 에러를 리턴해준다. 그 외에 adaptive mutex가 있는데, 표준은 아니고, 플랫폼에 따라 최적의 매커니즘으로 동작하게 된다. linux에서 SMP가 지원되는 경우 spinlock을 사용하게 되는데, 이때 adaptive mutex를 사용하게 되면 짧은 시간동안의 lock, unlock에 대해 최적의 성능을 지원한다. 대신 비 표준이라 PTHREAD_MUTEX_ADAPTIVE_NP를 통해 초기화 한다.

이런 mutex 타입을 mutex attribute 함수들을 통해 설정하여 mutex init시 사용하면 된다.

#include <pthread.h>
int pthread_mutexattr_init(pthread_mutexattr_t *attr);
int pthread_mutex_gettype(pthread_mutexattr_t *restrict attr);
int pthread_mutex_settype(pthread_mutexattr_t *attr, int type);
int pthread_mutexattr_destroy(pthread_mutexattr_t *attr);

Thursday, May 29, 2008

Thread, basic II

thread에 사용되는 함수들은 아래와 같다.

  • pthread_create()
    thread를 만든다.

  • pthread_exit()
    종료할때 return 대신 쓰면 cleanup함수들이 실행된다.

  • pthread_join()
    다른 thread가 종료될 때까지 현재 코드를 block한다. 종료될 때 그 thread의 리턴값을 받을 수 있다.

  • pthread_cancel()
    다른 thread에게 종료 신호를 보낸다. 종료하는 건 신호를 받은 thread 맘이다. 종료하게 되면 pthread_exit()가 호출된 것처럼 동작한다.

  • pthread_cleanup_push()
    종료시 실행할 함수를 등록한다 like atexit(). 종료시 stack처럼 최근 등록된 순서대로 pop되면서 실행된다.

  • pthread_cleanup_pop()
    위의 ..._push()함수로 등록한 것을 최근 순서로 해제(pop)한다. 단 인자가 0이 아니면 실행하면서 pop한다.

Socket, connect()

client에서 서버로 접속할 때는 connect()를 사용한다.

int connect(int sockfd, const struct sockaddr *serv_addr, socklen_t addr_len);

보다시피 사용방법은 아주 간단하다. 먼저 socket을 만들고, 만들 소켓을 접속한 주소가 담긴 sockaddr와 함께 인자로 주면 된다. 입력한 주소가 invalid한 경우에 0을 리턴하기 때문에 아래와 같이 코드를 만들게 된다.

#include <netinet/in.h>
#include <arpa/inet.h>
#include <sys/socket.h>

int sock_fd;
int saddr;

sfd = socket(AF_INET, SOCK_STREAM, IPPROTO_IP);

saddr.sin_family = AF_INET;
saddr.sin_port = 80; // port

if (inet_aton("100.100.100.100"), &(saddr.sin_addr) == 0)
fprintf(stderr, "error : inet_aton\n");
if (connect(sfd, (struct sockaddr *)&saddr, sizeof(saddr)) == -1)
perror("connect");

Tuesday, May 27, 2008

Socket, bind(), listen() and accept()

socket()을 통해 소켓을 생성했다면 다음은 bind()이다. bind()는 아래와 같다.

#include <sys/types.h>
#include <sys/socket.h>
int bind(int sockfd, struct sockaddr *my_addr, socklen_t addrlen);

sockfd는 앞서 만든 socket이고, sockaddr은 IP/Port 등의 주소 정보를 가진 구조체다. addrlen은 이 구조체의 크기이다. Unix socket을 사용하는 경우 sockaddr_un을 사용하지만, Network socket을 사용하는 경우 sockaddr_in을 사용한다. 두 구조체 모두 bind에 넣을 때는 (sockaddr *)로 캐스팅해서 넣어준다(bind내부에서 sockaddr로 캐스팅된 구조체의 앞부분을 보고 network socket인지 unix socket인지 알수 있다). 구조체를 잠깐 살펴 보자.

struct sockaddr_in {
unsigned short sin_family; // AF_INET
unsigned short sin_port;
struct in_addr sin_addr;
char sin_zero[8]; // not used
}
struct sockaddr_un {
short sun_family;
char sun_path[108];
}
struct in_addr {
unsigned long s_addr;
}


특별한 건 없고, AF_INET/AF_UNIX, 주소, 포트 번호 등이 들어가 있다. 주소는 in_addr 구조체로 들어가 있는데, unsigned long 타입으로 되어 있다. IP주소가 x.x.x.x 식으로 되어 있고 x < 256 이므로(8비트), 32bit 만 있으면 충분하다. 그래서 in_addr의 s_addr이 unsinged long (32bit) 이다. 여기에 INADDR_ANY (0)을 넣으면 서버에 지정된 모든 IP에 해당된다. 여기에 주소를 넣을 때는 inet_addr(), inet_aton()을 사용할 수 있는데, 전자의 경우에는 unix 표준이지만, 리턴되는 -1값이 INADDR_NONE(255.255.255.255) 인 경우와 에러인 경우를 모두 포함하므로 구별하기가 모호하다. inet_aton은 구분이 가능하지만 표준에 들어있지 않아.. 거시기 하다ㅡㅡ; 암튼 대충 이렇고, 실제로 주소를 넣는 코드는 아래와 같다.

struct sockaddr_in saddr_svr;
saddr_svr.sin_family = AF_INET;
saddr_svr.sin_port = htons(12000); //port number
// 방법1
saddr_svr.sin_addr.s_addr =
inet_addr ("192.168.100.20");
// 방법2
if (!inet_aton("192.168.100.20", &(saddr_svr.sin_addr.s_addr)))
{
fprintf (stderr, "inet_aton");
}

bind는 성공시 0을, 실패시 -1을 리턴하고 errno를 설정해준다. 위처럼 설정한 sockaddr_in을 아래처럼 binding하면된다.

if (bind(sock_fd, (sockaddr *)saddr_svr, sizeof(saddr_svr)) == -1)
perror("bind");

bind된 socket으로 실제 TCP 요청을 받기 위해(TCP 접속을 위해) listen()을 사용한다. 인자로 backlog 값이 사용되는데, 커널에서 큐로 구현되어 있으며 default로 1024 로 되어 1024개 까지 TCP 접속을 허용할 수 있게된다.

int listen (int s, int backlog);

생성된 소켓으로 외부 요청을 받을 수 있도록 주소를 binding하고 listen 하기 시작했다면, 요청을 기다리다가 들어온 요청을 accept() 하여 받을 수 있다. accept 함수는 bind 소켓과 client의 주소정보를 담을 sockaddr 구조체를 인자로 주면 요청이 들어올 때까지 코드를 block 한다.

int client_sockfd;
struct sockaddr_in client_saddr;
socklen_t client_socklen;

client_socklen = sizeof(client_saddr);
client_sockfd = accept(sock_fd, (struct sockaddr *)&client_saddr, &client_socklen);

printf("client : %s:%d\n", inet_ntoa(client_saddr.sin_addr), ntohs(client_saddr.sin_port));

close(...);

위 코드의 실행시 client의 요청에 대해 아래와 같이 출력된다.

./server 127.0.0.1 21650
Client : fd(4) 127.0.0.1:35130

Friday, May 23, 2008

Pointer's pointer - 포인터의 포인터

함수 인자에 포인터의 포인터를 사용하는 경우가 있으나, 가끔씩이라 햇갈릴 때가 있다. 어떤 경우에 사용하게 되는지와 그 이유를 정리해보자.



그림처럼 int a와 int *pa 가 있다고 치자. pa = a로 pa가 a를 가리키는 상황이면 pa는 a의 주소인 0x1001을 가지고 있다. 그래서 pa = 0x1001, *pa = 3 이다. 정수 포인터(int *)를 인자로 받는 함수 fa에서는 a값에 대해서만 참조가 가능하다. 그런데, 포인터가 가리키는 값을 바꾸고 싶은 경우가 있다. (스택이나 리스트 같은 자료구조를 구현하다 보면 필요하게 된다. 스택 포인터를 인자로 받는 push(node *stack, void* data) 같은 경우를 생각해보자. 새로운 공간을 할당하여 data를 넣은 후 이를 stack의 top node로 하고 node->next = stack로 바꿔줘야한다. 그러나 node *만을 받아서는 이를 변경하는 것이 불가능하다.) 그래서 사용하는 것이 포인터의 포인터이다. fb와 같이 포인터의 포인터를 인자로 받는 함수를 생각해보자. 함수 fb (int **ppa) 에 대해서 fb(&pa) 와 같이 인자를 주었다면, 함수에는 pa의 주소인 0x2001이 들어간다. 그래서 함수 fb 안에서는 ppa = 0x2001, *ppa = 0x1001, **ppa = 3 으로 포인터의 주소, 포인터가 가리키는 값의 주소, 포인터가 가리키는 값 세가지를 모두 접근할 수 있으며, 포인터가 다른 데이터를 가리키도록 바꿀 수도 있게 된다(스택에서는 그래서 push(node **stack, void* data) 와 같은 식이 되어야 한다). 이를 위해 포인터의 포인터가 사용된다.

Socket, TCP flow of both sides

TCP 소켓 통신은 서버와 클라이언트에 따라 아래와 같은 순서로 함수 호출이 일어난다.

  • Server

    socket() - bind() - listen() - accept() - recv(), send() - close()(passive)

  • Client

  • socket() - bin() - connect() - recv(),send() - close()(active)

웹상에 이쁜그림이 없어 간단히 그려보았다. (client에서는 connect()가 bind()를 포함 하므로 생략해도 된다)

Signals, sending signal with payload

프로세스에 signal을 보낼 때 payload 를 줄 수 있다. kill(), raise()가 아닌 sigqueue()를 사용하는데, 아래와 같다.

#include <signal.h>

union sigval {
int sigval_int;
void *sigval_ptr;
}

int sigqueue (pid_t pid, int signo, const union sigval value);

그래서 아래와 같이 간단히 payload를 줄 수 있다.

sigval value;
int ret;

value.sigval_int = 404;

ret = sigqueue(4500, SIGUSR1, value);
if (ret)
perror("sigqueue");

Thursday, May 22, 2008

Socket, byte order

사용하는 시스템의 architecture가 big-endian인지 little-endian인지를 알아야 보낼 데이터를 socket에서 사용하는 endian에 맞게 고쳐 보낼 수 있다. system의 endian을 알기 위한 테스트는 아래처럼 할 수 있다.

union btye_long {
long l;
unsigned char c[4];
}

int main()
{
union byte_long bl;
bl.l = 1200000L;
printf ("%02x-%02x-%02x-%02x\n", bl.c[0], bl.c[1], bl.c[2], bl.c[3]);
bl.l = htonl(bl.l);
printf ("%02x-%02x-%02x-%02x\n", bl.c[0], bl.c[1], bl.c[2], bl.c[3]);
return 0;
}
// from ALSP

근데, 이건 좀 복잡하고, 사실 if (120000L == htonl(120000L)) 만 해도 알 수 있다 ㅡ.ㅡ; 인텔 계열은 little endian 인데 반해 network packet에서는 bigendian을 사용한다. 그래서 항상 byte order를 변경해주어여 하는데 이때 사용하는 함수군이 아래와 같다.

  • htons host endian to network endian converting of 2bytes short

  • htonl host endian to network endian converting of 4bytes long

  • ntohs network endian to host endian converting of 2bytes short

  • ntohl network endian to host endian converting of 2bytes long


double, float 등의 변환은 ... 일단 생략 --;

Signals, advanced management

signal()을 통한 signal 처리는 기본적인 것이다. 조금 진보된 형태의 signal 처리로 sigaction()이 있다.

#include <signal.h>
int sigaction (int signo, const struct sigaction *act, struct sigaction *oldact);

sigaction()은 핸들러가 돌아가는 동안에 특정 signal을 block할 수도 있고, 핸들러가 프로세스의 상태에 대한 여러 정보들을 제공받을 수도 있다. 위에서는 signo에 해당하는 signal에 대한 핸들을 act로 바꿔주며, 이전의 핸들(behavior)을 oldact에 담아준다. 핸들을 등록할 떄 사용하는 sigaction struct에 대해 간단히 알아보자.

struct sigaction {
void (*sa_handler)(int);
void (*sa_sigaction)(int, siginfo_t, void *);
sigset_t sa_mask;
int sa_flags;
void (*sa_restorer)(void); /* OBSOLETE */
}

이 구조체에서는 두가지 형태의 핸들러를 등록할 수 있다. sa_handler는 signal()에서 등록하던 핸들러와 같은 형태이고, sa_sigaction은 sa_flags에 SA_SIGINFO 가 켜져있는 경우 사용하는 핸들러인데 아래와 같은 형식을 취한다. 이 flag에 따라 둘 중 하나의 핸들러를 사용하기 때문에 어떤 시스템의 경우에는 이 부분을 union으로 정의하기도 하므로 두개의 핸들러를 모두 등록하는 일은 되도록 피하자. sa_flags에 SA_NODEFER가 켜져있지 않는 한 처리하고 있는 signal과 동일한 signal은 block되며 다른 signal의 block은 sa_mask를 통해 추가할 수 있다(물론 SIGKILL, SIGSTOP은 block안된다).

void handler(int signo, siginfo_t *si, void *ucontext);

인자로 signal 번호뿐 아니라 siginfo_t도 받고, void *인 ucontext도 받는다. 다시 sigaction 구조체로 돌아가서 sa_flag 얘기를 더하면, 아래와 같은 flag들을 사용할 수 있다.

  • SA_NOCLDSTOP child가 stop, resume되어도 noti안한다.

  • SA_NOCLDWAIT child 에 대해 wait() 안하겠다...

  • SA_ONSTACK signal이 왔을 때 alternative signal stack을 쓰겠다는 것인데... 잘모르겠다.

  • SA_RESETHAND 'one-shot' 모드이다. 현재 핸들러를 이번 한번만 쓰고 다음에는 default 핸들러를 쓰겠다는...

  • SA_RESTART signal에 의해 인터럽된 system call을 BSD style로 restart하겠다는 건데..ㅡ.ㅡ;.


SA_SIGINFO 일때 사용하는 핸들러에 전달해 주는 siginfo_t 구조체에 어떤 정보들이 있는지 살펴보자

typedef struct siginfo_t {
int si_signo;
int si_errno;
int si_code;
pid_t si_pid;
uid_t si_uid; /* process real UID */
int si_status;
clock_t si_utime;
clock_t si_stime;
sigval_t si_value; /* payload */
int si_int; /* POSIX.1b signal */
void *si_ptr; /* POSIX.1b signal */
void *si_addr; /* dault시 memory location */
int si_band;
int si_fd;
}



  • si_signo받은 signal number

  • si_errno이 signal과 관련된 error code

  • si_pid종료된 프로세스의 pid(SIGCHLD signal인 경우 사용)

  • si_uid(SIGCHLD signal인 경우 사용)

  • si_statusexit status (SIGCHLD signal인 경우 사용)

  • si_utime종료된 프로세스가 소비한 user time(SIGCHLD signal인 경우 사용)

  • si_stime종료된 프로세스가 소비한 system time(SIGCHLD signal인 경우 사용)

  • si_valueunion of si_int, si_ptr

  • si_intpayload type이 int인 상태에서 sigqueue()에 보내진 signals

  • si_ptrpayload type이 void *인 상태에서 sigqueue()에 보내진 signals

  • si_addrSIGBUS,SIGFPE,SIGILL,SIGESV 등인 경우 fault가 일어난 address를 가지고 있음

  • si_band OOB 인 경우 fd의 oob, priority info를 가지고 있음

  • si_fd SIGPOLL 일때 작업이 완료된 파일의 fd를 가지고 있음



siginfo_t의 다른 원소인 si_code는 signal을 누가 발생 시켰는지, 왜 발생했는지에 대한 정보를 알려주는데, 몇개만 살펴보면 아래와 같다.

  • SI_ASYNCIOasynchronous I/O 끝나서 발생

  • SI_KERNEL커널이 보냈음

  • SI_TIMERPOSIX timer expired

  • SI_USER사용자가 kill(), raise()로 보냈음

  • SIGCHLD 인경우에는 아래의 si_code 들이 넘어온다.

  • CLD_CONTINUED child stopped but resumed.

  • CLD_DUMPED child terminated abnormally.

  • CLD_EXITED child terminated via exit().

  • CLD_KILLED child was killed.

  • CLD_STOPPED child stopped.

  • CLD_TRAPPED child hit a trap.

  • POLL_ERR I/O error

  • POLL_HUP device hung up or disconnect

  • POLL_IN available to read

  • POLL_MSG message is available

  • POLL_OUT available to write

  • POLL_PRI available high-priority data to read


그외에 SIGFPE, SIGBUS, SIGILL 등의 경우는 넘어가자.

Wednesday, May 21, 2008

Socket, create

기왕 공부하는거 socket도 복습해보자.

소켓은 도메인에 따라 unix socket, network socket 으로 구분하는데 앞의 것은 한 host 내에서 사용할 때이고 뒤의 것은 여러 호스트에 걸친경우 이다.

소켓은 타입에 따라 datagram 이냐, stream이냐의 차이를 가지는데 데이터를 일정한 단위로 나누어 보내냐 혹 stream 형태로 연결을 유지하면서 보내냐의 차이다(거의 UDP, TCP의 차이).

소켓은 아래처럼 간단하게 만들어진다.

#include <sys/socket.h>

int socket(int domain, int type, int protocol);
// domain AF_UNIX (unix socket),
// AF_INET(network socket) (AF = PF)
// type SOCK_STREAM
// SOCK_DGRAM
// SOCK_RAW
// protocol IPPROTO_IP (0) (for both)
// IPPROTO_TCP (for SOCK_STREAM)
// IPPROTO_UDP (for SOCK_DGRAM)
// IPPROTO_ICMP
// ex.
if ((sd = socket(AF_INET, SOCK_STREAM, IPPROTO_IP)) == -1)
fprintf(stderr, "error socket\n");
if ((sd = socket(AF_INET, SOCK_DGRAM, IPPROTO_IP)) == -1)
fprintf(stderr, "error socket\n");


SOCK_DGRAM(UDP)이나 SOCK_STREAM(TCP)이나 IP 아래에서 동작하므로, 위처럼 IPPRORO_IP를 가지고 생성할 수 있다.

Signals, signal block with masking

프로세스는 여러개의 signal을 block 시킬 수 있는데,이 때 sigprocmask()를 사용한다.

#include <signal.h>
int sigprocmask (int how, const sigset_t *set,
sigset_t *oldset);

how에 SIG_BLOCK 를 주면 sigset에 해당하는 signal들이 block되고, SIG_UNBLOCK을 주면 해제된다. SIG_SETMASK는 ... 잘 모르겠다 ㅡㅡ; set이 NULL 인 경우에는 현재 block 되어 있는 signal들이 oldset에 찍혀 나온다.

이런식으로 block한 signal들은 unblock하면 프로세스에 전달되는데, pending된 signal들은 sigpending(sigset_t *set)을 통해 확인할 수 있다. 일반적으로 signal을 고려한 critical section의 처리는 아래와 같은 순서로 진행된다.

  • sigprocmask()로 특정 signal들을 block한다.

  • critical section 을 처리한다.

  • sigsuspend()로 block한 signal 들이 처리될 때 까지 기다린다.


이러한 식으로 signal set을 통해 간단한 코드를 짜보면,

#include <signal.h>
#include <stdio.h>

void sig_handler(int signo)
{
fprintf(stderr, "signal caught : %s\n", sys_siglist[signo]);
return;
}

int main()
{
sigset_t sigset;
sigset_t sigset_old;
sigset_t sigset_test;

if (signal(SIGINT, sig_handler) == SIG_ERR) {
fprintf(stderr, "SIGINT handle can't be registered\n");
}
if (signal(SIGQUIT, sig_handler) == SIG_ERR) {
fprintf(stderr, "SIGINT handle can't be registered\n");
}

sigemptyset(&sigset);
sigaddset(&sigset, SIGQUIT);
sigprocmask(SIG_BLOCK, &sigset, &sigset_old);
pause();
sigpending(&sigset_test);
if (sigismember(&sigset_test, SIGQUIT))
printf("SIGQUIT is pending\n");
sigsuspend(&sigset_old);
//sigprocmask(SIG_UNBLOCK, &sigset, NULL);
return;
}


SIGINT, SIGQUIT 핸들러를 등록하고, sigset에 SIGQUIT을 넣고 sigprocmask로 블럭한다음 pause()로 signal을 기다린다(SIGQUIT이 block되어 있기 때문에 Ctrl+\ 을 눌러도 반응이 없다). Ctrl-c를 누르면 block되지 않은 signal 이므로 pause()를 빠져나오고 handler가 호출된다. 그리고 sigpending()에서 현재 pending 된 signal을 확인한다. Ctrl+c전에 Ctrl+\를 눌렀다면 SIGQUIT이 pending되었다고 나오게 된다. 그리고 마지막 두줄이 중요한데, sigsuspend(&sigset_old) 를 호출하면 프로세스가 sigset_old에 있는 SIGQUIT signal이 일어나서 처리 될때까지 대기한다(때문에 SIGQUIT이 들어오지 않으면 계속 기다리고 있는다). sigsuspend 대신에 sigprocmask 로 UNBLOCK하면 그 순간 pending되어 있는 signal 이 프로세스에 전달되는데, pending 되어 있는 signal이 없으면 그냥 넘어간다. 즉 sigsuspend()를 쓰면 signal이 일어날때까지 기다리고, sigprocmask UNBLOCK을 쓰면 signal이 있을 때 handler가 호출되고 없으면 그냥 넘어가는 차이가 있다.

Monday, May 19, 2008

Thread, Basic

LSP에서는 thread를 다루고 있지 않다. 그래서 APUE의 내용을 통해 복습해 보려고 한다. 알다시피 thread는 한 프로세스 내에서 여러개로 되어 동작하기 때문에 프로세스 내의 메모리나 fd를 공유한다. 그렇기 때문에 이러한 프로세스 내 공유 자원들에 접근할 때는 항상 consistency를 생각해야 한다. thread를 사용하는 일반적인 장점들은 아래와 같다.

  • asyncronous event를 다루는 루틴을 event type에 따라 별개의 thread를 만들어 처리하면 코드가 간단해진다.

  • 여러 프로세스들을 사용하면서 fd, memory를 공유하려면 복잡한 커널의 system call을 사용해야하는 반면에 thread에서는 간단하게 처리할 수 있다.

  • 한 thread에서 직렬로 진행되던 루틴들이 병렬화 되어 성능 향상을 가져올 수 있다.

  • Single processor에서도 성능향상이 있을 수 있다(한 thread가 block일때 다른 thread는 돌 수 있으므로)

  • multiple thread를 사용하므로써 사용자 응답시간이 좋아진다(user input/output을 thread로 돌리면 되므로) .

  • Multi-processor 환경에서 성능 향상을 가져다 준다.


한개의 thread는 여러 정보들을 가지고 있는데 아래와 같다.

  • thread ID, 레지스터 값들, 스택, 스케쥴 priority, policy, signal mask and errno


소위 pthread라 불리는 것들은 POSIX.1-2001의 optional feature이다. 이게(optional한 부분이) 지원되는지 안되는지는 _POSIX_THREADS 를 #ifdef로 테스트 해보면 된다(아님, sysconf에서 _SC_THREADS로 호출해보거나..)

thread identification pid_t 처럼 thread에서는 pthread_t 를 쓴다. 그런데, 구현에 따라 pthread_t를 구조체로 만드는 경우도 있기 때문에 tid1 == tid2 식으로 비교할 수는 없고 아래 함수를 사용한다. 자신의 tid를 보기 위해서는 pthread_self()를 사용한다.

#include <pthread.h>
int pthread_equal(pthread_t tid1, pthread_t tid2);
pthread_t pthread_self(void);

일단 thread 만드는 함수를 알아야 할텐데, 아래와 같다.

#include <pthread.h>
int pthread_create(pthread_t *restrict tidp, const pthread_attr_t *restrict attr, void *(*start_rtn)(void), void *restrict arg);

좀 어려워 보이지만 인자부터 체크해보자, 첫번째는 tid가 반환 될 것이고 두번째는 attributes를 넘겨줄 때 쓴다. 새로 생성된 thread는 start_rtn 루틴 부터 시행을 시작할 것이고, 이 함수는 arg를 인자로 받는다. thread는 signal mask를 상속받지만, pending 되어 있던 signal들은 clear된다. 조심할 점은 thread가 만들어지면 어떤 것이 먼저 실행될지 알 수 없다는 것이다. 대충 알았으니 한번 만들어보자.

#include <pthread.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>

pthread_t ntid;

void * thr_func(void *arg)
{
printf("new thread id(%u)pid(%u)\n",
(unsigned int)pthread_self(), (unsigned int)getpid());

return (void *)0;
}

int main()
{
int err;

err = pthread_create(&ntid, NULL, thr_func, NULL);
if (err != 0)
fprintf(stderr, "pthread_create error\n");

printf("main thread id(%u)pid(%u)\n",
(unsigned int)pthread_self(), (unsigned int)getpid());
sleep(1);
return 0;
}

linux에서는 pid가 다른 경우도 있고, tid는 4자리로 나타나는 것으로 되어 있는데, 실제 돌려보니 pid가 같고, tid도 연관성이 없는 것처럼 보인다(FreeBSD처럼 나온다) 왜일까. pthread_self 대신 gettid()를 사용하면 pid와 비슷하게 생긴 tid를 얻을 수 있다.

Friday, May 16, 2008

Signals, signal set

편리하게, 여러 signal을 묶어서 처리할 수 있다. 묶어진 signal set을 통해 특정 signal들을 block하거나, block을 통해 pending된 signal을 처리하고 혹은 특정 signal들을 기다리는 것도 가능하다. 조작에 쓰이는 기본적인 함수들은 아래와 같다.


#include <signal.h>
int sigemptyset(sigset_t *set);
int sigfillset(sigset_t *set);
int sigaddset(sigset_t *set, int signo);
int sigdelset(sigset_t *set, int signo);
int sigismember(const sigset_t *set, int signo);
int sigisemptyset(sigset_t *set);
int sigorset(sigset_t *dest, sigset_t *left, sigset_t *right);
int sigandset(sigset_t *dest, sigset_t *left, sigset_t *right);

sigset_t 는 signal들을 bit에 하나씩 맵핑시킨 것인데, sigemptyset은 이를 0으로 AND 시키고, sigfullset 은 0xF...F 로 OR 시킨다고 생각하면된다. sigandset 은 left, right를 and해서 dest에 넘겨주고, sigorset은 OR한다. 나머지 함수들은 직관적이므로 생략.

Signals, reentrancy

signal을 처리하고 있는데 다른 signal이 들어와서 중간에 다른 루틴을 수행한다면? 그 과정이 계속 반복된다면? 혼란스러운 일이다. 그래서 signal을 처리할 때는 이를 약간 고려해줘야한다. global 데이터는 손데지 않고, shared data도 안건드리는 것은, 좋은 습관이다. handler에서 malloc()을 호춣거나 strsignal()과 같이 static buffer를 사용하는 경우 중간에 들어오는 signal에 대해 어떻게 처리될지 알아두는 것은 좋은 일이다. reentrant function 이라함은 같은 프로세스내의 다른 thread에 의해 호출되어도 '안전'한 경우를 말한다. 이를 위해서는 아래 내용들이 지켜져야한다.

  • static data를 조작하면 안되고,

  • stack에 있는 데이터나 caller가 준 데이터만 조작한다

  • 다른 nonreentrant function을 호출하지 않는다,


재진입가능한 함수들에 대해서는 ... 종류가 많은데 필요하면 그때 책을 참조하는 것으로 하자. 일반적으로 abort, bind, connect, fork, fsync, kill, read, send, signal, time, wait, open, pipe, select, poll, recv, sock 등은 reentrant하지만, malloc 등은 그렇지 않다.

Wednesday, May 14, 2008

Signals, basic manipulation

아주 기초, 기본적인 signal 처리함수는 아래와 같다.

#include <signal.h>
typedef void (*sighandler_t)(int);
sighandler_t signal(int signo, sighandler_t handler);

signo에 해당하는 signal이 발생할 때 handler 함수를 호출하겠다는 얘기다.

#include <stdio.h>
#include <signal.h>

void handle_sigtstp(int signal)
{
printf("ctrl-z pressed. "
"You shouldn't use printf!\n");
return;
}

int main()
{
signal(SIGTSTP, handle_sigtstp);

sleep(10);
}

위 예제 처럼 간단하게 등록, 사용할 수 있다. printf 같은 함수를 호출하면 안되는 이유는 이 함수가 reentrancy를 보장하기 않기 때문인데, 일단 나중에 얘기하자.

사용자 handler 대신에 default로 동작하기를 원하는경우 handler 대신 'SIG_DFL'을 주면 되고, signal을 무시하고자 하는 경우에는 SIG_IGN을 주면된다. signal()은 등록된 handler의 포인터나 SIG_DFL, SIG_IGN 을 주는데, 실패한 경우 SIG_ERR을 준다(errno를 설정하지는 않는다)

signal을 테스트할 때 편한 함수로 pause()가 있다(signal을 받을 때 까지 기다린다). 이러한 부분을 고려하면 코드는 아래와 같아진다.

if(signal(SIGINT, handler) == SIG_ERR) {
fprintf(stderr, "Can't handle SIGINT\n");
}

프로세스가 실행(exec)되면 Signal handle은 default로 잡힌다. 부모 프로세스가 특정 signal을 무시하고 있었다면, exec된 프로세스도 무시하게 된다. 그리고 부모 프로세스가 잡아서 처리하던 signal은 default action으로 바뀐다(부모 프로세스의 주소공간을 공유하고 있지 않아서 handler도 공유/상속되지 않기 때문이다).

쉘에서 특정 job을 bg로 돌리는 경우 bg로 돌아가는 job은 SIGINT, SIGQUIT 등을 무시해야 한다. 그래서 쉘에서 bg job들을 실행하기 전에 아래처럼 SIGINT, SIGQUIT을 무시하는 코드를 수행한다(그래야 bg job들도 무시하게 되니까)

if(signal(SIGINT, SIG_IGN) != SIG_IGN) {
if(signal(SIGINT, sight_handler) == SIG_ERR) {
fprintf(stderr, "Can't handle SIGINT\n");
}
}
/* SIGQUIT도 마찬가지 */

그런데 fork()의 경우에는 좀 다르다. 부모의 주소공간을 공유하기 때문에 signal handler 까지 모두 받아서 똑같이 signal을 처리한다.

특정 signal이 발생했을 때 SIGINT인지 SIGKILL인지 숫자로 되어있어 햇갈릴 수 있다. 그래서 sys_siglist[] 를 통해서 각각 signal을 string으로 찍어볼 수 있다. linux에서 char *strsignal(int signo)를 제공하지만 표준은 아니다(thread-safe하지도 않다). sys_siglist[]를 추천한다.

#include <signal.h>
#include <stdio.h>

void sig_handler(int signo)
{
printf("signal caught : %s\n", sys_siglist[signo]);
return;
}

int main()
{
if (signal(SIGINT, sig_handler) == SIG_ERR) {
fprintf(stderr, "SIGINT handle can't be registered\n");
}
pause();
return;
}

signal을 보내는 방법은 아래처럼 매우 간단하다. 혹은 kill로 바로 보내도 된다(like, kill -HUP [pid]).

#include <sys/types.h>
#include <signal.h>

int kill(pid_t pid, int signo);

kill()은 세가지 값을 반환하는데, invalid signal인 경우 EINVAL, 권한이 없는 경우 EPERM, pid가 없거나 좀비인 경우 ESRCH이다.

다른 user나 그룹등...에 signal을 보내고자 하는 경우에는 프로세스가 CAP_KILL capability가 있어야 한다. 내가 다른 프로세스에 signal을 보낼 권한이 있는지 체크하는 좋은 방법으로는 signal로 '0'을 보내보는 것이다(실제 signal을 보내지는 않으므로 err만 체크할 수 있다).

자기자신에게 signal을 보낼 때는 간단히 raise()를 사용한다(like, int raise(int signo)). 이것은 kill(getpid(), signo) 와 같다. 전체 프로세스 그룹에 보내는 경우에는 killpg(int pgrp, int signo)를 사용한다(kill을 사용해서 kill(int -pgrp, signo)처럼 해도된다). pgrp = 0 이면 자신이 띄운 프로세스들에 모두 보낸다.

Signals, brief

Signal은 비동기적인 이벤트를 핸들링하는 매커니즘을 제공하는 Software Interrupt이다. Signal은 IPC의 원시적인 형태라고 봐도 된다. Unix의 역사상 Signal의 구현은 여러 갈래로 나누어 지려 했으나, 다행히 POSIX에서 표준을 제공하고, 이를 Linux에서 제공하고 있다.

일단 Signal이 발생하면 커널은 전달 가능한 상태가 될 때까지 기다렸다가 이를 해당 프로세스에 전달해준다. Signal의 처리는 아래 세가지 방식으로 진행된다.

  • 무시한다.

  • 잡아서 처리한다.

  • Default로 처리되게 둔다.


Signal 관련 함수들은 signal.h 에 정의되어 있고, kill()함수를 통해 보낼 수 있다. 쉘에서도 kill 을 통해 보낼 수 있으며, -l옵션으로 그 종류를 볼 수 있다. 각각의 signal을 간략히 정리해보면,

SIGABRT 코어내고 종료. assert(), abort() 호출시 이 signal 발생

SIGALRM alarm(), setitimer() with ITIMER_REAL

SIGBUS 이전에는 비메모리 시스템 에러였는데, 지금은 mmap()안된 영역 접근시 발생한다.

SIGCHLD default로는 무시되나, wait() 호출시 child 종료되면 발생

SIGCONT 프로세스 중단 후 재시작시 발생. 터미널, 에디터에서 refresh위해 사용함

SIGFPE floating point 관련 에러

SIGHUP 세션 종료시 발생. 많은 daemon 프로그램에서 이를 사용해서 conf 파일을 다시 읽게 함(convention) 예. apache에서 SIGHUP 받으면 httpd.conf 읽음

SIGILL illegal machine instruction

SIGINT Ctrl-C

SIGKILL

SIGPIPE PIPE 만들어 쓰고 있는데, 받는쪽이 종료한 경우 발생. default로는 종료됨

SIGPROF profiling timer expires (setitimer() with ITIMER_PROF)

SIGPWR low-bat, UPS system -> init process -> system terminate

SIGQUIT Ctrl-\ 모든 foreground 프로세스에게 전달. (코어 후 종료)

SIGSEGV Segmentation Violation

SIGSTOP kill에의해서만 보내질 수 있음. (무시안됨)

SIGSYS invalid system call (최신 바이너리를 오래된 커널에서 돌리지 않는 이상 거의 일어날 일이 없음)

SIGTERM 바로 종료 (이걸 catch 하면 manner 없음 ㅡ.ㅡ;)

SIGTRAP when it cross breakpoint

SIGTSTP Ctrl-z

SIGTTIN, SIGTTOU bg job 들이 읽거나 쓰려고 하는 경우 발생

SIGURG 소켓에 OOB(out of band) 데이터 들어오면 발생

SIGUSR1 SIGUSR2 user-defined purpose

SIGVTALRM setitimer() 관련 signal

SIGWINCH terminal window 값이 바뀐 경우 발생(예, top해놓고 터미널 사이즈를 조절할 때 화면 refresh를 위해 발생).

SIGXCPU 프로세스가 soft processor limit를 초과할 때 발생 (1초에 한번씩 계속.. hard limit까지 넘으면, SIGKILL받고 죽음)

SIGXFSZ process가 file size limit을 넘을 때 발생

Friday, May 9, 2008

Memory, Opportunistic Allocation

linux는 opportunistic allocation을 사용한다. 프로세스가 메모리 할당을 추가로 요구하면 바로 commit 해주지만 실제로 할당은 안되어 있다. 프로세스가 할당되어 있다고 생각한 이 영역에 뭔가를 쓰려고 하면 그때야 비로소 메모리를 할당해주는데 여기에는 demand paging, cow 등이 사용될 수 있다.

이런식의 메모리 할당은 실제 필요한 메모리만 할당해줄 수 있어 공간 효율적이고, 할당 작업을 실제 필요할 때까지 늦출 수 있으며, 실제 가능한 공간 이상으로 할당 해줄 수도 있다(overcommitment)

경우에 따라서 가용한 메모리 공간 보다 더 큰 영역을 할당해달라고 요청하는 프로세스들도 있는데, 커널에서 이를 수용하는 것을 overcommitment라고 한다. 이렇게 overcommitment되어 잘사용되면 다행이고, 진짜로 실제 메모리 이상을 사용하게 되면 OOM (out of memory)에러를 내어 OOM Killer가 해당 프로세스를 종료시키므로, 전체 동작에는 지장이 없다. overcommit 에도 옵션이 있는데, /proc/sys/vm/overcommit_memory 의 값을 통해 조정할 수 있다 (혹은 sysctl의 vm.overcommit_memory).

값이 0인 경우 휴리스틱한 overcommitment를 허용해주고, 1인경우 모든 요청을 허용해준다. 2인 경우에는 overcommitment를 disable하고 strict accounting을 enable하는데, 메모리 할당이 스왑영역 + 물리적 메모리의 일정 비율부분 까지로 제한된다. 일정 비율 부분은 /proc/sys/vm/overcommit_ratio에 정의되어 있는데, 이 값이 50인경우(default) 할당 가능한 메모리 공간은 스왑크기 + 물리적 메모리 크기의 50% 이다.

OOM Killer에 의해 프로세스가 죽는 것을 원치 않기 때문에 strict accounting을 하려고 하지만, 이게 만병통치약은 아니다. ( 가상 메모리는 대부분의 프로세스가 필요이상의 메모리를 할당하여 동작하려한다는 패턴에 기초하여 제공되는 메커니즘인데, 이를 사용하지 않겠다는 것이기 때문이다 )

Memory, Locking

알다시피 Linux는 demang paging(필요하면 그때 swap in 해주고 안쓰면 디스크로 다시 swap out하는) 이다. 그래서 실제 가지고 있는 물리적 메모리 공간 보다 더 큰 공간을 가상으로 제공해준다. 하지만, 경우에 따라서 자신의 메모리가 디스크로 swap out 되면 안되는 경우도 있다.

  • Determinism 특정 메모리에 올라가 있는 루틴이 일정시간내에 반드시 끝나야 하는 경우이다. 디스크에 swap out 되어 있으면 swap in 하는데 걸리는 시간이 상당하므로 정해진 시간에 응답하지 못할 수도 있다.

  • Security암호화된 비밀 정보를 디스크에서 읽어 복호화 한다음 메모리에 가지고 있었는데, 이 영역이 swap out되면 디스크에 복호화된 비밀정보가 남아 보안상의 취약점이 될 수 있다.


그래서 메모리의 일정 부분은 swap out 되지 않도록 잠글 수 있는데, 이 때 사용되는 함수가 mlock() 이다.

#include <sys/mman.h>

int mlock(const void *addr, size_t len);
int mlockall(int flags);

그 외에 특정 프로세스의 모든 부분을 locking 하고싶은 경우에는 mlockall()을 사용하면 된다. mlockall()에서 사용되는 flag으로는 아래 두가지가 있는데 일반적으로 두개를 다 OR해서 사용한다.

  • MCL_CURRENT 현재 프로세스가 사용하는 모든 메모리를 lock

  • MCL_FUTURE 앞으로 사용할 메모리까지도 lock


lock된 메모리의 해제는 munlock(), munlockall(void)을 통해 진행하면 된다. CAP_IPC_LOCK이 설정된 경우에는 무한정으로 메모리를 잠글 수 있지만, 그렇지 않은 경우에는 RLIMIT_MEMLOCK 에 설정된 바이트 까지만 locking할 수 있다. (default로 32KB 이다)

특정 페이지가 디스크에 있는지, 메모리에 있는지를 확인하는 함수로 mincore()가 있다. 아래와 같은데, 이 함수는 bit vector 형식으로 페이지의 메모리/디스크 상주 여부를 리턴해준다.

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

int mincore(void *start,
size_t length,
unsigned char *vec);

안따깝게도 이 함수는 MAP_SHARED 옵션으로 mmap 맵핑된(실제 파일에) 영역에 대해서만 정상적으로 동작한다.

Wednesday, April 30, 2008

Manipulating Memory

메모리를 다루는 여러 함수들을 살짝 다루고 넘어가자.

특정 값으로 초기화 는 memset을 사용한다. BSD에서는 bzero를 사용하기도 한다. malloc 한 후 memset 하는 짓... 하지 말고 그냥 calloc() 을 사용하는 것이 함수 호출도 줄이고, 코드도 짧아지고, 성능도 향상된다.

#include <string.h>
void * memset(void *s, int c, size_t n);

메모리 비교하기 는 memcmp를 쓰면된다. 마찬가지로 BSD에서는 bcmp를 지원한다. 주의할 것은 구조체의 경우 패딩값으로 쓰레기 값들이 들어갈 수 있어서 구조체의 비교를 memcmp로 하면 안된다(같아도 다른 값이 나올 수 있기 때문이다). 구조체는 해당 값들을 일일이, 직접 비교해줘야 한다.

#include <string.h>
int memcmp (const void *s1, const void *s2, size_t n);

메모리 복사(이동) 은 memmove 와 좀더 친근한 memcpy가 있다. 둘간에 차이가 있는데, memmove는 src, dst 공간의 overlap을 허용한다는 것과, memcpy는 overlap되는 경우 동작이 unknown이라는 거다. overlap된 메모리의 데이터를 변환할거라면 구지 이런 함수들 쓰지 말고 포인터로 직접 해줘야 겠다.

#include <string.h>
void * memmove(void * dst, void * src, size_t n);
void * memcpy(void * dst, void * src, size_t n);

그외에도 특정 문자가 나타날 때까지만 복사하는 memccpy(*dst, *src, size) 가 있고, 특정 바이트를 찾는 memchr 가 있다(memrchr은 GNU에서 제공하는 것인데, 뒤에서부터 꺼꾸로 찾는다).

#include <string.h>
void * memchr(const void *s, int c, size_t n);
#define _GNU_SOURCE
void * memrchr(/* same as above*/);

그리고 haystack에서 needle을 찾는 함수 (일종의 strstr...?) memmem도 있다.

#define _GNU_SOURCE
#include <string.h>
void * memmem(const void *haystack,
size_t hatstacklen,
const void *needle,
size_t needlelen);

조금 희한한 함수로, 무조건 '42'와 XOR 해서 넘겨주는 memfrob이 있는데, 두번 XOR하면 원래 것이 나오므로, 임시로 데이터를 희끄므리 ... 하게 하고 싶을 때 쓴다(아마도 encryption이 중시되지 않을 때 만든 것인듯).

#define _GNU_SOURCE
#include <string.h>
void * memfrob(void *s, size_t n);
memfrob(memfrob(text, len), len); // same!

Memory Allocation Mechanism

메모리를 할당하는 여러가지 방법들이 있는데, 각각의 장단점을 생각해보자.
  • malloc 일반적인데, 초기화 안된다.
  • calloc 0으로 초기화 되나 malloc보단 조금 복잡하다
  • realloc resize
  • brk, sbrk 아주,.. low level 하다.
  • Anonymous Memory Mappings 큰 공간 할당시 유용하고, 쉽고, 공유가능하다. 작은 공간 사용시에는 낭비가 있다(페이지 단위로 할당하니까... 맞나 ㅡ.ㅡ;).
  • posix_memalign align이 중요할때만 사용...
  • alloca 스택에서 할당. 편리. 해제할 필요없음. 큰 공간할당에는 부적절. 안되는 시스템도 있고..
  • VLA scope 내에서 할당 가능. 배열인 경우만 유용.

VLA Variable Length Array

C99에서 도입한 것으로 VLA - 가변 길이 배열이 있다. 알다시피 일반적인 배열은 compile time에 해당 영역이 고정된다. 그러나 함수안에서 가변으로 배열을 선언하면 VLA로 잡히는데, (확실치는 않지만) 스택에 잡힌다. 아래와 같이 VLA를 사용할 수 있다.

for (i = 0; i < n; ++i) {
char foo[i+1];
/* ... */
}

거의 둘이 흡사하나, alloca와 VLA가 다른 점이 있다. alloca로 스택에 잡은 메모리는 함수가 리턴하는 시점에 해제되지만, VLA의 경우는 위 코드와 같이 for loop을 벋어나는 순간, 즉 scope를 벗어나는 순간 해제 된다(위의 경우에 alloca를 사용한다면 loop을 도는 수만큼 공간을 사용했을 것이다).

alloca() : Allocating memory from the stack

스택은 프로그램의 자동변수들이 들어있는 공간이다. heap말고 이 스택에서 메모리를 할당받으려면 alloca()를 사용하면 된다. 스택에서 메모리를 할당받을 때의 장점은 별도의 메모리 해제가 필요없다는 것이다. 함수가 종료되면 메모리는 자동으로 해제된다. 왜? 스택에 있으니까. alloca()는 에러를 반환하지 않는다. 스택 메모리 할당의 실패는 stack overflow로 처리되기 때문이다. 아래와 같이 함수내에서 간단한 스트링 처리를 위해 사용하는 것이 일반적이다.

#include <alloca.h>

int func(const char* tail) {
const char *str = "temporal string";
char * fullstr;

fullstr = alloca(strlen(tail)+strlen(str)+1);
strcpy(fullstr, str);
strcat(fullstr, tail);

/* do something */

return 0;
}

주의할 사항은 이렇게 alloca로 할당된 메모리 영역을 함수 호출시에 인자로 사용해서는 안된다는 것이다. (다른 함수 호출시 alloca로 할당 받은 스택 영역은 push 되니까!) 그리고 alloca()는 그다지 portable하지 않으므로 사용에 주의할 필요가 있다. 그러나 메모리 해제가 필요 없다는 점, 할당시 malloc에 비해 오버헤드가 적다는 점에서 자주 사용할 수 있는 유용한 함수이다.

스트링을 스택 메모리에 복사해서 사용하는 경우도 있는데, 이를 위해서 Linux에서 제공하는 함수로 아래와 같은 것들이 있다(POSIX에서는 제공하지 않는다)

#define _GNU_SOURCE
#include <string.h>
char * strdupa(const char *s);
char * strndupa(const char *s, size_t n);

예상되다시피 스트링을 스택 메모리에 복사한 후 포인터를 넘겨준다.

Monday, April 28, 2008

Memory, advanced memory allocation

메모리 할당과 관련된 커널의 제한 값은 mallopt()를 통해 변경할 수 있다.

#include <malloc.h>
int mallopt(int param, int value);

자세한 옵션값은 ... 넘어가자 ㅡ.ㅡ;

glibc에서 할당된 메모리는 실제보다 클수도 있다. 그래서 실제로 할당된 메모리 사이즈를 malloc_usable_size(void *ptr)를 통해 확인할 수 있다. 또 malloc_trim(size_t padding)함수를 사용하면 padding공간으로 있던 영역을 해제하여 여분의 메모리를 (아주 조금 이겠지만) 확보하는데 일반적으로 이런 과정은 자동으로 이루어진다.

메모리를 디버깅할 때는 MALLOC_CHECK_ 환경 변수를 사용할 수 있다. 아래 처럼 이 값을 1로 주면 동작시에 메모리와 관련된 메세지들을 stderr로 뿌여준다. 2로 설정되어 있는 경우에는 바로 abort()를 호출하고 종료한다.


$ MALLOC_CHECK_=1 ./test

그외에도 사용하고 있는 memory alocation system에 대한 정보를 mallinfo()를 통해서 볼 수 있다(이 함수가 리턴하는 구조체는 return by value이다. 포인터가 아니다). 그리고 malloc_stats()를 호출하면 메모리 관련된 정보를 stderr로 뿌려주기도 한다.

Memory, Anonymous Memory Mappings

glibc에서 메모리를 할당할 때는 data segment나 memory mapping을 사용한다. 초기에는 2의 배수로 메모리를 쪼개 놓고 malloc호출시 요청한 size와 비슷한 free 공간을 할당해주는 식으로 동작했는데, 이 경우 실제 할당되는 메모리가 요청되 메모리보다 커서 낭비인 internal fragmentation 이 발생하고, 여러개의 작은 free memory로 쪼개져 있는 경우 공간은 있는데, 할당은 못하는 external fragmentation이 발생하는 문제가 있었다. - 이렇게 할당하던 방식을 buddy memory allocation scheme라고 불렀다(glibc는 이 알고리즘 말고도 arena algorithm이라는 더 발전된 알고리즘도 사용한다).

glibc에서 메모리를 할당할 때 사용하는 heap이 free를 한다고 바로 줄어들지는 않고 할당된 메모리보다 heap이 너무 커진 경우에만 shrink 한다. 그리고 glibc는 큰 메모리 할당의 경우에는 heap을 사용하지 않는다. 일반적으로 요청된 메모리의 크기가 128 KB 이상인 경우 glibc는 anonymous memory mapping을 사용한다(mmap 과 비슷한 식으로 메모리를 커널로 부터 할당받는다). anonymous memory mapping은 아래와 같은 장단점이 있다.

  • fragmentation이 없다.

  • 할당 후 크기조절이 가능하다.

  • heap을 거칠 필요가 없다.



  • 커널의 페이지 사이즈 크기 배수로 할당 받는다(공간 낭비가 있을 수 있다).

  • 새로운 공간을 할당받는 overhead가 heap에거 가져오는 건 보다는 크다


anonymous memory mapping은 직접할 수도 있는데, 아래처럼 mmap을 사용하면 된다.

void *p;

p = mmap(NULL,
512*1024, // size
PROT_READ|PROT|WRITE, // 권한
MAP_ANONYMOUS|MAP_PRIVATE, // anonymous !
-1, // fd 인데, -1안줘도 되긴 함
0); // offset (ignored)

if (p == MAP_FAILED) perror("mmap");


이렇게 할당된 메모리에서 특정 코드를 수행하려 할 수도 있겠으나, 심각한 보안 취약점이 될 수 있으므로, 하지 않는다. 할당된 메모리들은 모두 0으로 초기화 되어 있다(커널에서 이렇게 할당된 메모리들은 copy on write 로 zero filled 하기 때문에 효율적으로 0으로 초기화 된 메모리를 사용할 수 있다.)

다른 unix 시스템들의 경우에는 MAP_ANONYMOUS 같은 flag이 없다. 대신에 mmap시 /dev/zero를 사용한다(이전의 linux에서도 이 방식을 사용하였다). 하지만 이 경우 추가적인 system call을 수반하기 때문에 anonymous memory가 더 빠른 방식이다.

Friday, April 25, 2008

links

book

Pthreads Programming

url

https://computing.llnl.gov/tutorials/pthreads/

Memory, Data Segment, Break Point

지금이야 heap과 stack 영역이 별도로 구분되어 있지만, 옛날에는 한 Data Segment 안에 들어있었다(학교 때 이렇게 배웠는데, 벌써 옛날이 되었네..). 그래서 스택은 제일 윗쪽 주소로 부터 내려오고, 힙은 아래서 부터 올라갔다. 두 영역이 만나는 지점을 Break 혹은 Break point 라고 하는데, 따로 구분되어 있는 지금에도 이 이름은 계속 사용된다. POSIX나 C에서 공식적으로 제공하는 것은 아니지만 brk() 함수를 통해 break point 값을 조정할 수 있고, sbrk()를 통해 현재 break point 값에서 증감할 수 있다(sbrk(0)으로 호출하면 현재 break point의 값을 알 수 있다.).

Thursday, April 24, 2008

Vector Juggling Rotation

임의의 벡터를 쉬프트 시킬 때 최소한의 메모리를 사용하여 구현할 수 있는데, 이 때 각 백터 원소의 크기 x 2 의 공간만 있으면 되고 연산은 벡터의 길이에 비례하도록 할 수 있다 ( O(n) ). 저글링 연산인데, 예를들어 8개의 원소를 가지는 벡터를 왼쪽으로 2만큼 쉬프트 시키면 아래와 순서와 같다.


1 2 3 4 5 6 7 8 - 임시공간 - 연산횟수

x 2 3 4 5 6 1 8 - 7 - 1 // 1을 왼쪽으로 2만큼 이동 시키고 전에 있던 7을 보관

x 2 3 4 7 6 1 8 - 5 - 2 // 7을 왼쪽으로 2만큼 이동한 공간에 놓고 5를 보관

x 2 5 4 7 6 1 8 - 3 - 3 // ...

3 2 5 4 7 6 1 8 - x - 4

3 x 5 4 7 6 1 2 - 8 - 5

3 x 5 4 7 8 1 2 - 6 - 6

3 x 5 6 7 8 1 2 - 4 - 7

3 4 5 6 7 8 1 2 - x - 8

막상 코드로 짤려니 아주 햇갈렸다 ㅡ.ㅡ;...

#include <stdio.h>
struct vector
{
char *data;
int size;
};
void * vec_init (int size)
{
struct vector *pvec;
pvec = (struct vector *) malloc (sizeof (struct vector));
pvec->data = malloc (sizeof (char) * (size + 1));
*(pvec->data + size) = '\0';
pvec->size = size;
return pvec;
}

void vec_free (struct vector *pvec)
{
free (pvec->data);
free (pvec);
}

// juggling rotation
void vec_rotate (struct vector *pvec, int shift_by)
{
char tmp;
int i, j, k, f, t;
int cnt = 0;;
for (i = 0; i < pvec->size - 1; i++)
{
j = i;
k = (pvec->size + j - shift_by) % pvec->size;
f = *(pvec->data + j);
do
{
k = (pvec->size + j - shift_by) % pvec->size;
t = *(pvec->data + k);
*(pvec->data + k) = f;
cnt++;
f = t;
j = k;
}
while (j != i);
if (cnt >= pvec->size)
break;
}
return;
}

int main ()
{
int i;
struct vector *pvec = vec_init (20);

for (i = 0; i < pvec->size; i++)
*(pvec->data + i) = 'a' + i;

printf ("%s\n", pvec->data);
vec_rotate (pvec, 12);
printf ("%s\n", pvec->data);
vec_free (pvec);

return 0;
}

실행시키니 정상동작한다. 다행 ^^;

Wednesday, April 23, 2008

Memory, Alignment

어떤 변수가 자신의 size의 정수배가 되는 위치에 align된 경우 naturally aligned라고 한다(예로, 32bit 정수가 4bytes 정수배의 메모리에 위치한 경우 - 이 경우 주소의 마지막 두자리가 '00'이 된다). 따라서 2^n 크기의 변수가 naturally aligned 되려면 주소의 마지막 n 비트들이 0이 된다.

시스템에 따라서 alignment가 잘못되는 경우 비정상적으로 동작하거나 심각한 성능 저하를 초래할 수 있다. posix에서 alignment를 맞춰주는 함수를 제공하는데 아래와 같다.

#include <stdlib.h>

int posix_memalign (void **memptr, size_t alignment, size_t size);

위 함수는 alignment의 정수배에 해당하는 주소에 size 만큼의 메모리를 할당한 후 그 주소를 **memptr에 담아 돌려준다.

Friday, April 18, 2008

Memory, free

free()를 사용한다. 알다시피, Linux에서 이미 할당된 메모리공간의 일부만을 free할 수는 없다(애초에 나눠서 할당하는 수밖에는). SunOS같은 경우는 cfree()같은 것을 제공하지만, linux에서는 이게 free와 같이 동작하므로(기대치 않은 동작을 발생시키는 경우가 있으니) 사용하지 않는 게 낫다.

메모리 free할 때 조심해야하는 게 memory leak 이다. 이를 위해 제공되는 툴이 electric fence와 잘 알고 있는 valgrind 이다. (전자는 이름 그대로 '전기 울타리' 라서 구글링하기 상당히 불편하다 ㅡ.ㅡ;)

Memory, reallocation

그렇다. realloc()으로 할당된 메모리 공간을 조절한다.

void *realloc(void *ptr, size_t size);

리턴되는 포인터는 원래의 것과 다를 수 있다(더 큰 메모리 공간을 연속적으로 얻기 위해 원래 위치에서 다른 위치로 옮길 수 있기 때문이다. 이 때 복사 cost가 있다). size 가 0인 경우 free와 같으나 이렇게 변태적으로 사용할 사람은 없을 거 같다.

realloc()을 통해 사이즈를 더 줄일 수도 있는데, 이때 원래 ptr도 사용가능하다 (심리적으로는 이렇게 안 쓰기 마련이다.) 만약 realloc이 실패하면 원해 ptr는 유효하게 된다.

Memory, Allocation

메모리는 잘 알다시피 malloc(size_t size)로 할당하여 사용할 수 있다. C에서는 해당 포인터에 바로 대입할 수 있지만, C++에서는 void 포인터를 자동으로 캐스팅 해주지 않으므로 아래처럼 명시적으로 케스팅 해줘야 한다.

char * name;

name = (char *)malloc(512);

일부 프로그래머는 포인터를 리턴하는 함수 일부를 호출할 때 void로 변환하여(리턴값을 확인하지 않고) 쓰는데, 상당히 좋지 않은 습관이다.

malloc()은 NULL을 리턴할수 있기 때문에 에러체크를 꼭해줘야한다. 그래서 일반적으로 아래 처럼 wrapper를 둬서 사용한다.

void * xmalloc(size_t size)
{
void *p;
p = malloc(size);
if (!p) perror("xmalloc"), exit (EXIT_FAILURE);
return p;
}

배열을 할당할 때는 calloc()을 사용할 수 있는데, 이 함수는 값들을 0으로 초기화 해준다.

#include <stdlib.h>
void *calloc(size_t nr, size_t size);

nr x size 만큼의 공간을 할당해서 0으로 초기화 한 후 포인터를 돌려준다(이미 0으로 초기화된 메모리를 돌려주기 때문에 효율적이다). 이 함수를 사용해서 아래 처럼 0으로 초기화하는 malloc의 wrapper를 따로 두기도 한다.

void *xmalloc0(size_t size)
{
void *p;
p = calloc(1, size); // 1 x size
if (!p) perror("xmalloc0"), exit(EXIT_FAILURE);
return p;
}

Memory, Paging and etc.

알다시피 Linux의 메모리는 페이지로 나누어져 있다(대략 4kb인데 64비트에서는 8kb이다). 실제 물리적 메모리나 하드디스크에 mapping 되어 있는 경우가 valid page이고 그외에는 fault를 일으키는 invalid page이다. 상주되지 않은 디스크를 읽으려 하는 경우 page fault가 발생하고 커널에서 해당 페이지를 하드에서 읽어 메모리로 올리는 paging in을 해준다. 반대로 메모리가 없으면 앞으로 가장 덜 사용될 것 같은 메모리의 부분을 디스크로 옮겨는 paging out을 한다.

때때로 한 물리적인 공간을 여러 (virtual memory address)메모리 주소가 가지고 있는 경우가 있는데, 이때 두가지로 동작이 가능하다. 하나는 share - 말그대로 공유하게 되어 한 프로세스가 write한 내용이 다른 프로세스에 의해 보이는 경우이고, 다른 경우는 그렇게 write 동작이 일어날 때 해당 프로세스에게 독자적인 영역을 할당해주는 COW(Copy-on-write) 동작을 하는 경우이다.

메모리는 여러 블럭을 묶어 memory region, segment, mapping 라고 부를 수 있는데, 각각은 아래와 같이 구분된다.

  • text segment 는 프로그램 영역이고,

  • stack

  • data segment(heap) : 동적 메모리 영역

  • bss segment : 초기화 안된 전역 변수공간 (이 변수들에 대해 object file에서 초기값이 없으므로 값을 저장하지 않는다. 그래서 바이너리 사이즈를 줄일 수 있다. 또 실행시에 메모리에 올라갈 때에도 copy-on-write로 동작하여 0으로 초기화 하는 작업을 효율적으로 진행한다)


이러한 영역들은 /proc/self/maps나 pmap을 통해 프로세스별로 어떻게 메모리가 할당되어 있는지 확인할 수 있다.

Monday, April 14, 2008

Resource Limits

시스템의 리소스 제한값을 보거나 설정하는 것은 아래 함수를 통해 할 수 있다.

#include <sys/time.h>
#include <sys/resource.h>

struct {
rlim_t rlim_cur; // soft
rlim_t rlim_max; // hard
};

int getrlimit(int resource, struct rlimit *rlim);
int setrlimit(int resource, const struct rlimit *rlim);

리소스 제한 값에는 soft limit과 hard limit 두가지가 있는데, soft limit는 hard limit 한도내에서 자유롭게 변경할 수 있다. 각 값들은 0인 경우 disable이고, RLIM_INFINITY(-1) 인 경우 무한대이다. limit 값들의 flag 이름들은 아래와 같다.

  • RLIMIT_AS : address space 제한

  • RLIMIT_CORE : 코어파일 크기

  • RLIMIT_CPU : 최대 CPU 사용시간

  • RLIMIT_DATA : data segment 크기 제한

  • RLIMIT_FSIZE : File size

  • RLIMIT_LOCKS : 최대 File Lock 개수

  • RLIMIT_MEMLOCK : CPY_SYS_IPC 설정없이 mlock(), shmctl()등으로 가질수 있는 메모리 크기

  • RLIMIT_MSGQUEUE : massage queue 크기

  • RLIMIT_NICE

  • RLIMIT_NOFILE : fd갯수 제한

  • RLIMIT_NPROC : user가 돌릴 수 있는 process 수 제한

  • RLIMIT_RSS : maximun number of pages

  • RLIMIT_RTPRIO

  • RLIMIT_SIGPENDING : 최대로 queue될 수 있는 signal갯수

  • RLIMIT_STACK : 프로세스 스택 크기 제한


이러한 값들을 가지고 설정하거나, 값을 확인하는 코드 예는 아래와 같다.

struct rlimit rlim;
int ret;

// get RLIMIT_CORE value
ret = getrlimit(RLIMIT_CORE, &rlim);
if (ret == -1) perror("getrlimit"), return 1;

printf ("RLIMIT_CORE sft(%ld), hrd(%ld)\n", rlim.rlim_cur, rlim.rlim_max);

// set RLIMIT_CORE value
rlim.rlim_cur = 32 * 1024 * 1024;
rlim.rlim_max = RLIM_INFINITY;
ret = setrlimit(RLIMIT_CORE, &rlim);
if (ret == -1) perror("setrlimit"), return 1;