2014년 6월 24일 화요일

[리눅스 커널] 커널 자료구조

reference : 리눅스 커널 심층 분석, 로버트 러브 지음, 황정동 옮김
6장 커널 자료구조

1. 연결 리스트
연결 리스트는 노드라고 부르는 가변적인 개수의 데이터를 저장하고 관리하는 기능을 제공한다. 정적 배열과 달리 연결 리스트는 동적으로 데이터를 새엇ㅇ해 리스트에 추가할 수 있다. 그러므로 컴파일 시점에 미리 개수를 알 수 없는 데이터를 관리할 수 있다. 데이터가 한꺼번에 동시에 만들어지지 않으므로, 이 데이터는 인접한 메모리 공간에 모여 있지 않을 수 있다.따라서 데이터를 서로 연결시키는 방법이 있어야 하므로 리스트의 각 데이터에는 다음 데이터의 위치를 가리키는 next 포인터가 들어 있다. 리스트에 데이터를 추가하거나 삭제할 때는 다음 노드를 가리키는 포인터를 조정하면 된다.

단일 연결리스트와 이중 연결 리스트

연결 리스트를 나타내는 가장 단순한 자료구조의 형태는 다음과 같다.

/* 연결 리스트의 데이터 항목 */
struct list_element {
void *data; /* 항목에 담긴 데이터(payload) */
struct list_element *next; /* 다음 항목을 가리키는 포인터 */
};

이중 연결 리스트를 나타내는 자료구조의 형태는 다음과 같다.

/* 연결 리스트의 데이터 항목 */
struct list_element {
void *data; /* 항목에 담긴 데이터(payload) */
struct list_element *next; /* 다음 항목을 가리키는 포인터 */
struct list_element *prev; /* 이전 항목을 가리키는 포인터 */
};

리눅스 커널의 연결 리스트는 독특한 방식으로 구현되지만, 본질적으로는 환형 이중 연결 리스트라고 할 수 있다. 이런 연결 리스트 형식을 사용함으로써 유연성을 최대한 확보할 수 있다.

연결 리스트 내에서 이동

연결 리스트 내의 이동은 선형으로 일어난다. 한 항목을 참조하고, 다음 포인터를 따라가 다음 항목을 참조한다. 이 과정을 반복하면 된다. 전체 리스트를 차례대로 훑는 작업이나 항목을 동적으로 삽입하고 제거하는 작업이 필요한 경웨 연결 리스트를 사용한다.
연결 리스트 구현에서 리스트의 '시작'부분에 접근하기 쉽게 리스트의 첫 번째 항목을 head라고 부르는 특별한 포인터로 표시하는 경우가 많다.

리눅스 커널의 구현 방식

연결 리스트 구조체

2.1 커널 개발 과정에서 커널의 연결 리스트 공식 구현이 도입되었다. 이제 모든 연결 리스트는 이 공식 구현 방법을 사용한다.
연결 리스트 코드는 <linux/list.h> 헤더 파일에 정의되며, 자료구조는 아래와 같이 간단하다.

struct list_head {
struct list_head *next;
struct list_head *prev;
};

이러한 구현 방식의 실제 유용성은 list_head 구조체의 사용법에 있다.

struct fox {
unsigned long tail_length; /* 꼬리의 길이(cm) */
unsigned long weight; /* 무게(kg) */
bool is_fantastic; /* 멋있는 여우인가? */
struct list_head list; /* fox 구조체 리스트 */
};

이렇게 하면 fox 구조체의 list.next는 다음 항목을 가리키고, list.prev는 이전 항목을 가리키게 할 수 있다. 커널은 이런 연결 리스트를 조작하는 일군의 함수를 제공한다. 예를 들어, list_add()를 사용하면 기존 연결 리스트에 새로운노드를 추가할 수 있다. 게다가 이런 함수는 범용성을 갖추고 있다. list_head 구조체만을 대상으로 처리하기 때문이다. container_of() 매크로를 사용하면 특정 변수 항목을 가지고 있는 부모 구조체를 쉽게 찾아낼 수 있다. C에서는 구조체내 특정변수의 상대적인위치(offset)가 컴파일 시점에 ABI 수준에서 고정되기 때문이다.

#define container_of(ptr, type, member) ({
const typeof( ((type *)0)->member ) *__mptr = (ptr);
(type *) ( (char *) __mptr - offsetof(type, member) );})

container_of() 매크로를 사용하면 list_head가 들어 있는 부모 구조체를 반환하는 함수를 간단하게 정의할 수 있다.

#define list_entry(ptr, type, member) container_of(ptr, type, member)

커널은 list_entry()를 비롯한 연결 리스트 생성, 조작 등의 관리 함수를 제공하며, 이런 함수는 list_head가 들어 있는 구조체에 상관없이 동작한다.

리스트 헤드

일반적으로 리스트 노드가 아닌 연결 리스트 자체를 가리키는 데 사용하는 특별한 포인터가 필요한 경우가 있다. 재미있게도 기본 list_head 구조체가 이 특별한 노드 역할을 할 수 있다.

static LIST_HEAD(fox_list);

이렇게 하면 fox_list라는 이름의 list_head 구조체를 초기화한다. 연결리스트와 관련된 다수의 함수는 하나 또는 두 개의 인자를 받는다. 헤드 노드 하나를 받거나 헤드 노드와 실제 리스트 노드를 받는다.

연결 리스트 조작

커널은 연결 리스트를 조작하는 일군의 함수를 제공한다. 모든 함수는 C 인라인 함수로 구현되어 있으며, <linux/list.h> 파일에 들어 있다.
이런 함수는 모두 O(1)이다. 즉 리스트나 다른 입력의 크기에 상관없이 일정한 시간 안에 실행된다.

연결 리스트에 노드 추가

연결 리스트에 노드를 추가하려면 다음 함수를 사용한다.

list_add(struct list_head *new, struct list_head *head)

이 함수는 head 노드 바로 뒤에 new 노드를 추가한다. 일반적으로 환형 리스트에는 첫 번째나 마지막 노드라는 개념이 없으므로 head에 어떤 항목을 지정해도 상관없다. '마지막' 항목을 전달한다면, 이 함수로 stack을 구현할 수 있다.
// 뒤에 추가하면서 뒤에서 빼면 스택 구현 가능
fox 리스트의 예로 돌아와서 fox_list 리스트에 새로운 struct fox를 추가해야 한다면 다음과 같이 한다.

list_add(&f->list, &fox_list);
// struct fox f; 인듯
// 연산자 우선순위 "->" > "&" 이므로 f->list 에 접근(포인터를 통해 요소 선택)하여 list의 주소(&)를 전달

연결 리스트의 마지막에 노드를 추가하려면 다음 함수를 사용한다.

list_add_tail(struct list_head *new, struct list_head *head)

이 함수는 head 노드 바로 앞에 new 노드를 추가한다. list_add()와 마찬가지로 환형 리스트이므로 head에 어떤 항목을 지정해도 상관없다. '첫 번째' 항목을 전달한다면, 이 함수로 큐를 구현할 수 있다.
// 뒤에 추가하면서 앞에서 빼면 큐 구현 가능

연결 리스트에서 노드 제거

연결 리스트에 노드를 추가하는 것 다음으로 리스트에서 노드를 제거하는 것이 가장 중요한 동작일 것이다. 연결 리스트에서 노드를 제거하려면 list_del() 함수를 사용한다.

list_del(struct list_head *entry)

이 함수는 리스트에서 entry 항목을 제거한다. 이 함수는 entry나 entry가 들어 있는 구조체가 차지하고 있던 메모리를 해제하지는 않는다. 보통 이 함수를 호출한 다음 list_head와 list_head가 들어 있는 자료구조의 메모리를 해제해야 한다.
예시

list_del(&f->list);

함수의 입력에 fox_list가 없다는 점에 주목하자. 이 함수는 특정 노드만을 입력으로 받아 해당 노드의 이전 및 다음 노드의 포인터를 조정해 해당 노드를 리스트에서 제거한다. 구현 내용을 보면 이해가 쉬울 것이다.

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}

연결 리스트에서 노드를 제거하고 다시 초기화할 때를 위해 커널은 list_del_init() 함수를 제공한다.

list_del_init(struct list_head *entry)

이 함수는 주어진 list_head를 초기화한다는 점만 제외하면 list_del() 함수와 같다. 해당 항목을 리스트에서 제거해야 하지만 자료구조 자체는 재사용이 필요한 경우에 이 함수를 사용한다. ( ??? )

2014년 6월 22일 일요일

[리눅스 시스템 프로그래밍] 6 세션과 프로세스 그룹

세션 시스템 호출

셸은 로그인 시점에 새로운 세션을 생성한다. 이러한 작업은 새로운 세션을 쉽게 생성하는 특수 시스템 호출을 사용해서 수행한다.

#include <unistd.h>

pid_t setsid (void);

setsid()는 새로운 세션 내부에 새로운 프로세스 그룹을 생성하며, 호출한 프로세스를 세션과 프로세스 그룹 모두의 리더로 만든다.(새로운 세션에서 제어하는 tty가 없는 유일한 구성원이 된다.) 이는 데몬이나 셸에 유용한 특성이다. 데몬은 세션 구성원과 터미널 제어를 원하지 않으며, 셸은 사용자가 로그인할 때마다 새로운 세션 생성을 원하기 때문이다.

여기서 tty는
유닉스 전문 용어로 tty는 단순히 읽기와 쓰기를 넘어 몇 가지 추가적인 명령어를 지원하는 디바이스 파일을 뜻합니다. 그리고 터미널은 사실상 이 tty와 동일한 의미로 사용됩니다. 일부 tty는 하드웨어 디바이스를 위해 커널이 제공하며 그 예로 키보드에서 들어오는 입력과 텍스트 모드 화면으로 나가는 출력, 시리얼 라인을 통해 전송되는 입출력이 있습니다. 그 외의 tty는 씬 커널 레이어를 통해 터미널 에뮬레이터라고 불리는 프로그램으로 제공되며 이런 tty를pseudo-tty로 부르기도 합니다. 터미널 에뮬레이터로는 Xterm(X 윈도우 시스템), Screen(프로그램과 다른 터미널 사이에 독립적인 계층을 제공), SSH(한 머신에서 프로그램으로 다른 머신의 터미널에 연결), Expect(스크립팅 터미널 인터랙션용) 등이 있습니다.
http://www.myservlab.com/144

성공하면 setsid()는 새롭게 생성된 세션의 세션 ID를 반환한다.
실패하면 호출은 -1을 반환하며 유일하게 가능한 errno 코드는 EPERM이다.(프로세스가 현재 프로세스 그룹 리더라는 사실을 알려준다.) 특정 프로세스가 프로세스 그룹 리더가 되지 않도록 만드는 확실한 방법은 fork이며, 부모 프로세스가 종료된 다음에 자식 프로세스가 setsid()를 수행하면 된다. 예를 들면 다음과 같다.

pid_t pid;

pid = fork ();
if (pid == -1) {
    perror ("fork");
        return -1;
    } else if (pid != 0)
        exit (EXIT_SUCCESS);

    if (setsid () == -1) {
        perror ("setsid");
        return -1;
    }

조금 덜 유용하긴 하지만, 현재 세션 ID를 얻으려면 다음과 같은 함수를 사용한다.

#define _XOPEN_SOURCE 500
#include <unistd.h>

pid_t getsid (pid_t pid);

getsid()는 pid가 가리키는 프로세스의 세션 ID를 반환한다. 오류 발생시 -1을 반환한다. 유일한 errno 값은 ESRCH로, pid가 유효한 프로세스에 대응하지 않음을 알려준다.
이 기능을 실제로 활용하는 경우는 드물며, 주로 진단 목적으로 쓰인다.

pid_t sid;

sid = getsid (0);
if (sid == -1)
    perror ("getsid"); /* 가능하지 않은 경우다. */
else
    printf ("My session id=%d\n", sid);

프로세스 그룹 시스템 호출

setpgid()를 호출하면 pid가 가리키는 프로세스의 그룹 ID를 pgid로 설정한다.

#define _XOPEN_SOURCE 500
#include <unistd.h>

int setpgid (pid_t pid, pid_t pgid);

-p230

출처 : 리눅스 시스템 프로그래밍, 로버트 러브 지음, 박재호 옮김, 한빛미디어 2009년 펴냄

2014년 6월 2일 월요일

[Security] SSH

Secure Shell

Secure Shell (SSH) is a cryptographic network protocol for secure data communication, remote command-line login, remote command execution, and other secure network services between two networked computers. It connects, via a secure channel over an insecure network, a server and a client running SSH server and SSH client programs, respectively.^[1] The protocol specification distinguishes between two major versions that are referred to as SSH-1 and SSH-2.

The best-known application of the protocol is for access to shell accounts on Unix-like operating systems, but it can also be used in a similar fashion for accounts on Windows. It was designed as a replacement for Telnet and other insecure remote shell protocols such as the Berkeley rsh and rexec protocols, which send information, notably passwords, in plaintext, rendering them susceptible to interception and disclosure using packet analysis.^[2] The encryption used by SSH is intended to provide confidentiality and integrity of data over an unsecured network, such as the Internet.

- http://en.wikipedia.org/wiki/Secure_Shell