Algorithm 문제 풀기(TopCoder, Hackerrank)

 다양한 사이트에서 알고리즘 문제를 풀고 만들어진 코드를 github project 로 올리고 있다. 아직 많이는 풀지 못했지만,

언젠가는 다양한 문제를 많이 올릴 수 있기를...

https://github.com/SolvingProblems/Code4Algorithm/tree/master/Daeseok.Youn

Extended system call error reporting

the original link : https://lwn.net/Articles/657341

Kernel 과 User 영역 사이에 Interface 의 복잡도는 굉장이 높다. H/W 설정, 프로세스 상태 등의 자세한 정보를 어느 방향으로든 전달해주는 많은 task 들이 있다. 그런 task 들이 많기는 하지만, 뭔가 잘못 진행되는 경우 단지 integer 의 error code 만을 보여주기 때문에 종종 개발자들이 그것이 무엇이 잘못된 것인지 알아내기가 어렵다. 과거에도 그런 error-reporting 을 위해 다양한 제안히 있었다; 마지막 제안은(Alexander Shishkin) 이전 제안에 비해 많이 나아지질 않았으나 이 문제에 대해 나아가야 할 만한 포인트를 보여줬다.

예를 들어, Media subsystem 에 의해 제공되는 VIDIOC_S_FMT ioctl() 을 고려해보자. VIDIOC_S_FMT 는 capture 장치(카메라와 같은)로 부터 user 영역으로 Image 들의 포멧 정보를 설정하는 ioctl 이다. (http://linuxtv.org/downloads/v4l-dvb-apis/vidioc-g-fmt.html) 이런 가능한 이미지 포멧정보는 놀랍도록 다양하고 User 영역에서 연관된 파라미터와 함께 Kernel 로 포멧 디스크립션을 넘기도록 하고 있다. 이런 디스크립션 정보의 조합에 의한 문제가 발생할 수 있는데 이때, User 는 단지 VIDIOC_S_FMT 실패로 EINVAL 의 error code 만을 받게 될 것이다. 물론, kernel 은 무슨일 있었는지 알고 있지만, user 영역과 그 지식(?)을 공유하는 방법은 없었던 것이다.

이 문제는 고치는 것은 쉽지 않다; errno 매커니즘은 명백히 부족함을 느낀다. 그렇지만 Unix 전통적으로 오랫동안 사용되어 왔고 이것을 바꾸기엔 쉽지 않을 것이다. 그래서 어떤 확장된 error 정보를 잘 넘겨줄 수 있는 새로운 채널이 있어야 할 것이다. error 정보를 자세히 하여 전달하도록 kernel 에 추가하는 작업은 조심스럽게 이루어져야 한다. 이유는, kernel 의 중요한 기능을 느리게 한다던가 과도한 error 메시지 설정으로 소스의 흐름을 방해하는 것 등이다. Alexander 의 패치는 이런 두가지의 경우를 모두 만족하도록 설계되었다. 

error reporting 의 매커니즘을 잘 설명한 예제가 있다. Alexander 의 패치는 perf_event_open() 시스템 콜을 목표로 삼았다. 그것은 파라미터로 perf_event_attr 구조체를 받는데, 이 구조체는 event 캡쳐를 위해 설정해야 하는 파라미터 셋 들이 엄청나게 많이 있다. 이로 인해 이 system call의 운영은 잘못될 가능성을 갖고 있게 된다.

Describing errors

첫번째로는 error site 를 표현하는 구조체를 만들어야 한다. 그 구조체는 error 가 발견되고 user 영역으로 넘겨줄 수 있는 위치어야 한다. 그 구조체는 ext_err_site 구조체인 site 변수를 갖고 있어야 한다. 이 변수는 error 에 대한 전체적인 사항을 보고 할 수 있도록 어떤 정보든지 갖고 있을 수 있다. perf 의 경우에 이 구조체는 아래와 같이 생겼다.

    #include <linux/exterr.h>

    struct perf_ext_err_site {
	struct ext_err_site	site;
	const char		*attr_field;
    };

attr_field 멤버 변수는 error 가 생긴 struct perf_event_attr 내부의 field 의 이름을 갖고 있도록 한다.

그리고 나서, user 영역으로 넘겨질 이 구조체의 어떤 추가적인 정보를 담는 문자열을 넘겨줄 수 있는 함수를 정의할 필요가 있다. perf 버전에서는 :

    static char *perf_exterr_format(void *site)
    {
	struct perf_ext_err_site *psite = site;

	return kasprintf(GFP_KERNEL, "\t\"attr_field\": \"%s\"\n",
			 psite->attr_field);
    }

이 함수는 동적으로 할당된 문자열을 반환한다; 확장된 error reporting 구조에서 이 문자열이 더이상 필요없을때 할당 해제를 자동으로 한다.

이 두 코드 조각을 적절히 위치 시키면, 특정 error class 를 처리할 수 있는 "error domain"을 정의할 수 있게 된다. perf 의 경우를 보자

    DECLARE_EXTERR_DOMAIN(perf, perf_exterr_format);

error 정보를 실질적으로 보고하는 것은 ext_err() macro를 통해 완성된다. 실제 사용자는 wrapper 를 통해 사용할 수 있을 것이다. 어떻게 만들어 졌는지 perf code를 보자:

    #define perf_err(__code, __attr, __msg)				\
	({ /* make sure it's a real field before stringifying it */	\
	    struct perf_event_attr __x; (void)__x.__attr;		\
	    ext_err(perf, __code, __msg, 				\
	        .attr_field = __stringify(__attr));			\
	})

ext_err() 의 파라미터 들은 위에서 정의된 domain (error code, user 영역에 전달될 메시지)이다. 그리고 error-site 구조체의 나머지를 초기화된 문자열을 설정(set)한다. 이 경우, ext_err() 의 마지막 파라미터는 잘못된 속성으로 설정된 perf_ext_err_site 구조체의 이름을 attr_field 에 넣는다. 이 패치를 보면 peft_err() 매크로가 어떻게 실행되는지 볼 수 있다.

또 다른 중요한 세부 내용이 있다. 하나는 EXTERR_MODNAME 심볼인데 이것은 ext_err() 이 불리기 전에 반드시 set되어 있어야 한다.

    #define EXTERR_MODNAME	"perf"

다른 하나는 ext_err() 는 함수 파라미터로 넘어온 error 코드를 변경하여 값을 반환한다. 이 코든는 kernel 이 알고있는 모든 확장된 error 에 대한 설명이 되어 있는 ext_err_site 구조체의 index 라 보면 된다. 일반적인 방법으로는 user 영역에 반환하기 위해서 아래와 같이 사용한다.

    return ext_err_errno(code);

ext_err() 가 변환한 코드는 application 이 무슨 의미인지 알수 없기 때문에 user 영역에 직접적으로 전달되지는 않는다. 그래서 원래 error code 는 ext_err_errno() 를 호출하지 않고 반환되어서는 안된다. 이런 호출은 확장된 error 정보를 kernel 이 다 기억을 해야한다는 조건이 성립해야 한다. 간략하게 말하면, 새로운 ext_err_code 라 불리는 field 를 새로운 task_struct 내부에 있도록 해야 한다. 그래서 ext_err_errno() 의 호출은 그 field 에 위치한 특별한 error code를 바라보도록 해야 한다는 것이다. 만약 확장되기 이전 error code를 ext_err_errno() 에 넘기게 되더라도 정상동작할 것이며 그것은 안전하게 기존과 확장된 error code 모두를 지원할 것이다.

The user-space side

kernel은 user 영역에 확장된 error 메시지를 알려줄 준비가 다 되어 있지만, system call 로 부터 반환된 값을 여전히 예전 errno를 사용하는 경우가 많을 것이다. 만약 application 에서 더 많은 정보를 원한다면, 아래 처럼 사용하면 된다.

    char message[SIZE];

    len = prctl(PR_GET_ERR_DESC, message, SIZE);

반환 값을 기존 메시지와는 다를 것이다. JSON 포멧으로 에러가 발생된 곳의 file 과 line, error 코드, 모듈 이름, 실제 메시지 그리고 앞서 설명한 domain format 함수에 의해 추가된 정보를 줄 것이다. 이 변경으로 user 영역에 perf tool 에 JSON parser 를 사용하여 메시를 잘 분리하여 적절히 분석 가능할 것이다. prctl() 호출은 kernel 영역에서 error 정보를 지울 것이며, 다시 호출한다면 아무런 data를 받을 수 없을 것이다.

이 패치는 review 커멘트가 많이 보이지는 않는다. 끝으로 error 보고 문제는 많은 개발자가 인지하고 있으며, 이것을 고치기 위해 몇몇은 노력까지 한다. 그리고 커널로 부터 error-reporting 채널을 넓히는 시도를 하여 성공하는지는 알수 없지만, 전통적으로 누군가가 고민하고 변경을 시도한다면 언젠가는 누군가가 성공으로 이끌 것이다.

[책 소개] 리눅스 커널 패치와 커밋

블로그에 쓰려던 내용들을 모으다 보니, 양이 상당하니 책으로 쓰면 어떨까 하고 진행했다. 거의 10개월만에 완성하고 E-book 으로 출간이 되었다!! (종이책은 5월말에 출간 예정.)

책은 간단히 리눅스 커널의 코딩 스타일을 고치는데서 부터 정적 분석 툴을 쓰고, QEMU 를 이용한 리눅스 커널 디버깅 방법들을 정리했다.