2011년 8월 14일 일요일

브라우저는 어떻게 작동하는가 - 1. 렌더링 엔진의 기초

 원문글 - http://taligarsiel.com/Projects/howbrowserswork1.htm#The_rendering_engines_threads


본 글은 위 링크에 있는 원문글을 내 맘대로 번역하고 편집하여 작성하였다. =ㅅ=;;




1. 웹 브라우저의 소개


웹 브라우저는 아마도 오늘날 가장 많이 사용되는 소프트웨어중에 하나라 볼수 있다. 이 글에서 나는 브라우저가 작동하는 내부원리를 보여주고 한다.  즉 우리가 “http://www.google.com”을 주소창에 입력하고 브라우저의 화면에 구글의 페이지가 나타날때까지 브라우저의 내부에 작동하는 과정을 알수 있을것이다. 

- 대상이 되는 브라우저
요즘 가장 많이 사용하는 브라우저는 대략 다음 5가지라 볼수 있다.
인터넷 익스플로러, 파이어폭스, 사파리, 크롬, 오페라.

- 브라우저의 주요 기능
브라우저의 주요 기능은 선택한 웹 리소스(HTML, PDF, 이미지 등)를 브라우저의 화면상에 표현해주는 기능이다. 물론 이것은 서버에 리소스를 요청하고 수신하는 과정을 모두 포함한다. 브라우저가 HTML을 해석하고 화면에 나타내는 방법은 HTML, CSS 표준에 따르게 되는데 브라우저에 따라 스펙에 따르는 정도는 조금 상이하다고 볼수 있다. 

반대로 어떤 공식 스펙이 있는것이 아님에도 브라우저의 UI는 서로 많은 부분이 비슷한데 대략 다음과 같은 UI상의 공통의 구성요소를 가진다고 볼수 있다. 

- URI를 입력할수 있는 주소창
- 뒤로가기(BACK), 앞으로가기(FORWARD) 버튼
- 북마크 기능
- 새로고침과 새로고침 중지버튼, 로딩과 로딩 중지버튼
- 홈버튼

아마도 경험적으로 추가된 부분들과 브라우저들이 서로 조금씩 모방을 하는과정에서 이렇게 비슷해졌다고 볼수 있겠다. 

2. 브라우저의 구성

브라우저의 주요 구성요소는 대략 다음과 같다.

  1. UI (User Interface) - 각 브라우저의 UI는 앞서 설명한 바와 같이 주소바, 뒤로가기/앞으로가기 버튼, 북마킹 메뉴등을 공통적으로 포함한다.
  2. 브라우저 엔진 - 렌더링(rendering) 엔진에 작업을 요청하고 다루는 인터페이스 부분으로 볼수 있다.
  3. 렌더링 엔진 - 요청된 컨텐츠를 화면에 표시하기 위해 필수적인 부분이다. 예를 들어 요청된 페이지가 HTML이라할때, 렌더링 엔진은 HTML과 CSS를 파싱하고 화면에 파싱된 컨텐츠를 표현하는 역할을 수행한다. 
  4. 네트워킹 - HTTP request와 같은 네트워크 호출을 위해 필요한 부분이다. 각 플랫폼에 의존적인 부분과 플랫폼에 독립적인 인터페이스 부분으로 구성된다.
  5. UI 백엔드 - 콤보박스나 윈도우(window)와 같은 기본 위젯을 화면에 그리는데(drawing) 필요한 부분이다. 
  6. 자바스크립트 해석기 - 자바 스크립트 코드를 파싱하고 실행하는데 필요하다.
  7. 데이터 스토리지 - 퍼시스턴스 계층 (persistence layer). 브라우저는 쿠키등과 같이 데이터를 로컬영역에 저장할 공간이 필요하다. HTML5같은 경우에는 ‘web databse’를 따로 정의해 놓았는데 브라우저 안에 완전한 형태의 데이터베이스가 존재해야 한다. chrome의 경우에 기존에 sqlite와 같은 경량형 rdb를 사용하고 있으며 향후에는 LevelDB라는 Key/Value 기반 데이터베이스가 HTML5용으로 사용될듯 하다.


                                                  Figure 1: 브라우저의 주요 구성요소들


크롬은 다른 브라우저와는 다르게 렌더링 엔진의 인스턴스를 각 탭별로 사용한다. 즉 각 탭별로 별도의 렌더링 엔진을 사용하여 화면을 표시한다. 

3. 렌더링 엔진의 기초 

그렇다면 렌더링 엔진에 대해서 알아보자. 렌더링은 브라우저 화면에 요청된 컨텐츠를 표시하는 과정을 말한다.

기본적으로 렌더링엔진이 화면에 표시할수 있는 리소스는 HTML 문서, XML 문서, 이미지들이다. 물론 브라우저의 플러그인을 통해서 다른 포맷을 표시하는 것도 가능하다. 예를 들어 PDF 뷰어 플러그인을 통해서 PDF를 표현할수 있다. 우선은 이챕터에서는 CSS를 사용하여 포맷팅된 HTML 문서와 이미지를 표현하는 과정에 대해서만 설명한다. 

3.1 rendering engines

렌더링 엔진을 설명하기 위해 참조하는 브라우저는 파이어폭스, 크롬, 사파리 들이다. 크롬과 사파리는 “Webkit”을 사용하며 파이어폭스는 “Gecko” 엔진을 사용한다. 

웹킷은 오픈 소스 렌더링 엔진이며 리눅스 플랫폼을 위한 엔진으로 시작되었다가 애플과 MS 윈도우를 공식지원하는 형태로 변화하였다. 더 자세한 사항을 보고 싶으면 http://webkit.org를 참조하라.

3.2 주요 플로우
렌더링 엔진은 네트워크 계층으로부터 요청된 페이지의 컨텐츠를 얻어 오는데 대략 8k 크기의 청크 단위로 이를 수행한다. 

이후의 렌더링 엔진의 기본 플로우는 다음과 같다. 



                                                       Figure2: Rendering engine basic flow

렌더링 엔진은 HTML 문서를 파싱할 것이고 “content tree”라 불리는 트리형태로 DOM 노드를 생성하게 되며 HTML의 스타일 정보들은 별도의 render tree로 구성된다. 렌더 트리는 색상이나 dimension들을 포함하는 그래픽적 속성들의 사각형을 포함하며 사각형들은 올바른 순서대로 화면에 표시될 것이다. 

렌더트리를 생성한후에 렌더트리의 “layout” 과정을 수행한다. 다시 말해서 각 노드들이 화면상에서 정확히 그들이 놓여있어야 할 곳에 나타나게 된다. 다음과정은 “painting”인데 이 과정에서 렌더 트리를 순회하면서 스타일 정보를 찾아서 UI 백엔드를 이용하여 각 노드들을 화면상에 표현하게 된다. 

다음의 각 엔진별 플로우를 한번 살펴보라.


      
                                                 figure 3. 웹킷 렌더링 엔진의 메인 플로우




                                                figure 4. Gecko 렌더링 엔진의 메인 플로우


4. Render 트리의 생성

브라우저는 DOM 트리를 생성하는 동시에 render 트리도 생성한다.  Render 트리는 화면상에 요소를 표시하는 스타일적인 요소와 배치순서등을 담당한다. 다시말해, 이 트리의 목적은 올바른 순서로 화면상에 컨텐츠를 표시하게 해주는 역할이다. 

파이어폭스에서는 render 트리의 각 요소들을 “frames”이라는 이름으로 부른다. 웹킷의 경우에는 “renderer” 또는 “render object”라 부른다. “renderer”는 layout을 어떻게 구성해야 할지, 자신과 트리상의 자신의 자식들을 어떻게 화면상에 그릴지를 알려준다. 
웹킷의 RenderObject 클래스가 이러한 renderer의 가장 기본이 되는 클래스이며 다음과 같이 정의 되어 있다. 


class RenderObject {
virtual void layout();
	virtual void paint(PaintInfo);
	virtual void rect repaintRect();
	Node* node;  //the DOM node
	RenderStyle* style;  // the computed style
	RenderLayer* containgLayer; //the containing z-index layer

}

각각의 렌더러는 각 노드의 css 박스에 대응하는 사각영역을 나타낸다. (CSS2 스펙을 참고하자)
이 박스는 보통 width, height, position과 같은 정보를 모두 포함한다. 박스의 타입은 “display” 스타일에 영향을 받는다.

다음의 “display”속성에 따라 DOM 노드를 생성하는 웹킷의 코드를 잠깐 살펴보자. 

RenderObject* RenderObject::createObject(Node* node, RenderStyle* style)
{
    Document* doc = node->document();
    RenderArena* arena = doc->renderArena();
    ...
    RenderObject* o = 0;

    switch (style->display()) {
        case NONE:
            break;
        case INLINE:
            o = new (arena) RenderInline(node);
            break;
        case BLOCK:
            o = new (arena) RenderBlock(node);
            break;
        case INLINE_BLOCK:
            o = new (arena) RenderBlock(node);
            break;
        case LIST_ITEM:
            o = new (arena) RenderListItem(node);
            break;
       ...
    }

    return o;
}



element type도 함께 고려되어야 하는데 예를 들어 폼 컨트롤이나 테이블등은 특별한 프레임을 갖는다. 
웹킷에서 element는 특별한 renderer 객체를 요구하는데 “createRenderer” 메소드를 오버라이딩하여 이를 해결한다. 

4.1 render 트리와 dom 트리의 관계

앞서 설명한 바와 같이 renderer는 각 DOM 엘리먼트와 대응한다. 다만 그 관계가 1:1 대응은 아니다. 

DOM의 엘리먼트중 비쥬얼과 관련이 없는 요소는 render 트리에는 

없기 때문이다. 예를 들어, “head”같은 element나 display의 속성이 “none”인 경우에는 render 트리에 없다고 보면된다. (속성이 “hidden”인 경우는 render 트리에 존재한다는 점을 주의하자)

또한 하나의 DOM 엘리먼트가 여러개의 visual object와 대응할수도 있다.  보통 이렇게 복합적인 display 속성을 가진 엘리먼트를 하나의 renderer로 표현하는 것은 불가능하다. 예를 들어, “select”는 디스플레이 영역을 위한 것, 드롭다운 리스트 박스를 위한 것, 버튼을 위한 것등  3개의 renderer 객체를 가진다. 또한 텍스트가 여러줄에 나뉘어 표현되어야 할 경우에 한 줄의 넓이보다 텍스트의 전체 넓이가 크기 때문에 “new line”을 위한 추가적인 renderer가 필요하게 된다. 

DOM 노드와 대응하는 일부 render객체들은 트리상에서 같은 위치에 있지 않는 경우도 있다. “Float”나 “Absloute” 포지션 속성을 가진 엘리먼트의 경우 디스플레이의 플로우를 벗어나 있기 때문에 트리상에서 노드와는 다른 위치에 놓여있으며 실제 프레임과 맵핑하기 위해 “placeholder frame”이라는 별도의 프레임을 갖는다. 



4.2 생성된 render 트리의 플로우

파이어폭스에서 화면의 표시(presentation)는 DOM 업데이트를 위한 리스너에 기록된다. presentation은 실제로 frame의 생성을 “FrameConstructor”에 위임하고  constructor는 style의 처리와 프레임의 생성을 수행한다. 

웹킷에서는 스타일을 처리하고(computation) renderer를 생성하는 과정을 “attachment”라 부르며 모든 DOM 노드는 “attach” 메소드를 갖는다. attachment는 항상 동기화되어 있으며 DOM 트리에 노드를 삽입하는 경우에 그 노드의 “attach” 메소드를 호출함으로써 수행된다.

4.3 렌더링 엔진의 스레드

렌더링 엔진은 보통 단일 스레드이며 네트워킹을 제외한 거의 모든 작업이 이 단일 스레드에서 이루어진다.  파이어폭스나 사파리에서는 이 스레드가 브라우저의 메인스레드이지만 
크롬에서는 탭 프로세스의 메인 스레드이다. (즉, 크롬에서는 탭마다 렌더링엔진을 별도로 갖는다. )

네트워킹 작업은 보통 여러개의 병렬 스레드에 의해 수행하며 보통 2-6개의 커넥션을 동시에 갖도록 셋팅되어 있다. (파이어폭스3의 경우가 최대값인 6개였다.)

브라우저의 메인 스레드는 하나의 이벤트 루프로 구성되어 있다. 보통의 경우 이는 무한루프이며 따라서 프로세스가 살아있는 동안 루프가 유지된다. 이 이벤트 루프를 간략화하면 이벤트를( 예) layout 이벤트나 paint 이벤트 ) 기다리고 그들을 처리하는 과정으로 볼수있다. 파이어폭스의 메인 이벤트 루프의 코드를 보면 대략 다음과 같다. 

while (!mExiting)
    NS_ProcessNextEvent(thread);



이상으로 브라우저와 렌더링 엔진의 기본 구조를 이해할수 있는 간단한 글을 소개하였다. 다음 글에서는 

본격적으로 html의 파싱과 css을 어떻게 해석하는지에 대해 연재하려고 한다. 

to be continue..



2011년 8월 3일 수요일

Hacker's Delight: 프로그래머의 필독서



 오해하면 안됀다. 해커가 그 해커가 아니다. ㅡ.ㅡ;;

 이 책은 비트연산의 모든것을 보여준다. 학부 2학년때 이 책을 처음

 접했는데 당시에는 나는 정말 신선한 충격을 받았었다.

 아마도 이책은 당신이 구현하기를 원하는 가장 효율적인 비트연산들의

 원리를 보여줄것이다.


 Hacker's Delight의 비트연산을 사용하는

 프로젝트 중 유명한것들의 예를 한번 들어보자.


 1. java jdk의 Integer 패키지


 2. Linux kernel


 3. apache lucene


 4. apache cassandra


 5. wnprolog

 리눅스 커널에도 이 저자의 소스가 들어있다는것에 주목하자.

 위의 리스트는 내가 아는것들만 적어놓은 것이므로 실제로는

 이보다 훨씬 많은 프로젝트에서 사용되었을 것이다.



 http://www.hackersdelight.org/HDcode.htm 이곳에 가면 친절하게

 직접 구현해 놓은 소스를 볼수 있다. 북마크해놓고 필요할때마다

 copy & paste를 사용하도록 하자. ㅡ.ㅡ;;;


 책 소개를 이정도로 끝내면 좀 싱거우니 많이 쓰는 코드를

 몇개 살펴보도록 하자.


 1. computing the number of 1-bits

 int pop(unsigned x) {
   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
   x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
   return x;
}


x의 전체 비트 수를 구하는 연산이다. 



소스의 첫라인을 보자. 0x5는 2진수로 0101이다. 



첫번째 라인을 거치게 되면 각각의 두비트에 대해서 카운팅한 값을 



합치게 된다. 마찬가지로 두번째 라인은 4비트의 카운팅한 값의 합을



구하게 된다. 최종적으로는 32비트의 카운팅 한값이 모두 합쳐지게 된다.

 

0xFF을 예로 들어보겠다. 



이진수로는 1111 1111이 된다. 



첫번째 라인(0x55555555)을 거치게 되면 



11 11 11 11 -> 01 01 01 01 + 01 01 01 01 = 10 10 10 10 



이 된다. 즉 두비트씩 살펴보면 두비트 단위로 카운팅한 값이 나온다. 




두번째 라인(0x33333333)을 거치게 되면 ( 4비트씩 살펴보자 )



1010 1010 -> 0010 0010 + 0010 0010 = 0100 0100 



이 된다. 즉 4비트씩 살펴보면 4비트 단위로 카운팅한 값이 나온다. 



이런식으로해서 최종적으로는 32비트 단위로 카운팅한 값이 나오게 된다. 



 

 2. round down to a power of 2


 
 unsigned flp2(unsigned x) {
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x - (x >> 1);
}



2의 지수승으로의 버림 연산이다. 다시 말해서 주어진 x와 같거나 작은



2의 지수승을 구하는 연산이다. 



예를 들어, 



flp2(1) = 1 (2^0), flp2(2) = 2 (2^1), flp2(3) = 2 (2^1)



flp2(63) = 32 (2^5), flp2(64) = 64 (2^6) 



이 된다. 



코드를 간단히 설명하면 다음과 같다.



2의 지수승은 2진수로 다음과 같이 표현할수 있다.



십진수                        이진수
 1   ---------          0001
 2   ---------          0010
 4   ---------          0100
 8   ---------          1000
16  ---------        1 0000
32  ---------       10 0000




즉 1을 left shift하면 2의 지수값을 구할수 있다. 



따라서 2의 지수승으로 버림을 하려면 가장왼쪽(leftmost)에 있는 1비트만을



남기고 나머지를 모두 0으로 만들어버리면 된다. 




위의 코드에서 x | ( x >> 1) , x | (x >> 2) 등의 코드는 leftmost를 기준으로



오른쪽의 모든 비트를 1로 만든다. 



마지막 라인 x - ( x >> 1)에서 leftmost bit를 제외한 모든 비트가 0으로 반전



되고 leftmost bit만 남게되어 2의 지수승으로 버림연산이 되게 된다.




이외에도 부동소수점 나누셈, 64비트 나누셈, hilbert curve 생성, 



CRC-32등 주옥같은 코드들이 있다. 



프로그래머라면 한권 구매하여 책장에 꽂아두도록 하자.


2011년 7월 31일 일요일

dalvik의 method 호출 opcode와 java bytecode의 비교


 java specification에는 메소드 호출시에 사용하는 바이트코드가 나와있는데

크게 다음 4가지를 사용한다고 볼수 있다. 

1. invokestatic

2. invokespecial

3. invokevirtual

4. invokeinterface

이름에서 대략 유추할수 있겠지만 invokestatic은 static 접근자로 지정된 메소드를 호출할때 

사용된다. 


일반적으로 jvm에서는 메소드 호출시에 인자의 첫번째로 객체 자신인 this 객체를 

저장한다. 정적 메소드 ( static method )의 경우 이러한 this 객체를 위한 공간이 필요없기

때문에 바로 인자만 들어가게 되므로 별도의 바이트 코드 invokestatic이 필요하다.


invokespecial은 주로 <init> 즉 객체의 생성자 메소드를 호출하기 위해 사용되고 
super class 메소드의 구현 메소드를 호출하기 위해서도 사용된다.

invokeinterface는 인터페이스의 메소드를 호출하기 위해 사용되고 나머지 대부분의

메소드들은 invokevirtual로 호출한다. 이름에서 알수있듯이 invokevirtual은 

dynamic method를 위한 바이트 코드임을 알수 있다. 

( java7에서는 invokedynamic이라는 bytecode가 새로 추가된듯 하다. )


source/android/dalvik/vm/meterp/out/ 폴더에 보면 하드웨어별로 

dalvik의 opcode 구현이 들어있다. dalvik에서는 

invoke-virtual, invoke-virtual/range, invoke-virtual-quick, invoke-virtual-quick/range

invoke-super, invoke-super/range, invoke-super-quick, invoke-super-quick/range

invoke-direct, invoke-direct/range

invoke-static, invoke-static/range

등등 꽤 많다. 크게 보아 종류는 똑같이 4종류인데 invokespecial이 invoke-direct로 이름이

더 직관적으로 바뀐듯하고 바로 위 부모 클래스의 메소드를 호출하는 invoke-super가 생기고

invokeinterface에 대응되는 바이트코드는 제거되었다. 

(직접 확인해 봐야 겠지만 아마도 invoke-virtual이 이 역할까지 함께 할듯 하다.)


range 계열은 parameter에 range를 쓸수 있는데 예를 들어,

invoke-virtual {v1,v2,v3} 처럼 호출하는 것을 range 계열은 invoke-virtual/range {v1 … v3}

처럼 호출한다.

quick 계열은 parameter외에도 부모 클래스의 인스턴스 포인터를 위한 별도의 테이블을 사용한다. 

즉 invoke-virtual-quick {parameter}, vtable 과 같은 형식으로 사용된다.

cvm이나 kvm의 구현부에서는 invokevirtual 바이트코드의 실행시 부모 클래스의 주소로 

한단계식 따라가며  메소드를 호출하게 되는데 테이블에 미리 부모 클래스들의 주소를 

로드시켜 놓고 빠르게 호출하기 위한 용도로 quick 계열의 메소드를 사용하는 듯하다.

2011년 7월 30일 토요일

Lucene에서 KStemmer 사용하기

정확한 명칭은 Krovertz Stemmer라고 부른다. Lucene등의 툴킷에서는 

KStemmer라는 이름의 약자로 되어 있다. 1993년 꽤 오래전에 논문이 나오고 

lucene, lemur, indri 등 대부분에 포함되어 있지만 생각보다는 많이 쓰이지는 

않는듯하다.

아무래도 사전기반의 알고리즘이다 보니 리소스가 꽤 많이 소비된다는 측면이 

클듯하다. 

가장 최신 버젼인 lucene-3.3.0 버젼에서는 추가된듯하다. 

( 이전 버젼부터 존재했었는지는 확실치 않다. )

자세한 사항이 궁금한 사람은 다음의 논문을 읽어 보도록 하자. 



다음의 표는 Porter Stemmer가 에러를 일으키는 경우를 나타낸다.



Krovetz Stemmer는 Porter Stemmer만큼은 공격적으로 stemming을 하지는 않기때문에 

에러가 적다. 

KStemmer의 알고리즘은 기존의 Porter Stemmer의 알고리즘과 사전기반의 알고리즘이 

결합된 형태이다. 

KStemmer는 Inflectional, Derivational 두가지 방법의 알고리즘을 적용한다.

전자는 suffix를 제거하는 쪽 후자는 추가해서 명사를 만드는 쪽이다.


Inflectional에서 단어가 사전에 있는지를 찾아본후 사전에서 단어를 발견하면

스템처리를 하지 않는다. 


Derivational 방법에서는 -er, -or, -ion, -ly, -ity, -al, ive, -ze, -ment, -able 등을 추가하는데 

논문에 따르면 longman 사전의 빈도수를 기반으로 이를 패턴화 시켜놓았다.

더 자세한 사항은 논문을 참조하도록 하자. 


lucene에는 KStemFilter는 포함되어 있으나 Analyzer는 없기때문에 클래스를 추가해주어야 한다.

간단히 다음과 같이 클래스를 만들어 사용해 보자. 

package org.apache.lucene.demo;

import org.apache.lucene.analysis.en.*;
import org.apache.lucene.analysis.*;
import org.apache.lucene.analysis.standard.*;
import org.apache.lucene.util.Version;

import java.io.Reader;

public class KStemAnalyzer extends Analyzer {
Version MatchVersion;
public KStemAnalyzer(Version matchVersion){
this.MatchVersion = matchVersion;
}
public TokenStream tokenStream(String fieldName, Reader reader){
return new KStemFilter(new StandardTokenizer(MatchVersion,reader));
}
}

코드는 lucene-3.3.0을 기준으로 작성하였다. 

Analyzer는 Filter와 Tokenizer를 모두 필요로 한다. 

위에서는 간단하게 StandardTokenizer를 사용하였지만 lucene에는 

ClassicTokenizer, WhitespaceTokenizer, LowerCaseTokenizer, 

KeywordTokenizer등 여러가지가 있으니 입맛에 맞게 사용하면 된다.

Tokenizer가 있으니 입맛에 따라 골라 사용하자. 

2011년 7월 28일 목요일

LUCENE으로 TREC WT10G dataset 인덱싱하기

WT10G dataset은 웹문서를 모아놓은 dataset으로 아직도 많이 쓰인다.

WT10G에는 1,692,096개의 문서가 있고 용량은 대략 4G정도 된다. 

데이터는 WTX001 ~ WTX104개의 폴더에 각각 B01.gz ~ B50.gz로 

되어 있다. 

하나의 BXX.gz 파일에는 여러개의 웹 문서가 들어있어서 독립적인 포맷으로 

합쳐져 있는데 포맷은 대략 다음과 같다. 























WT10G에 대해서 더 궁금하신 분은 

http://ir.dcs.gla.ac.uk/test_collections/wt10g.html를 가보시라.

검색을 해보면 lucene으로 WT10G 데이터를 인덱싱해서 낸 논문은 많지만

실제로 어떻게 인덱싱을 했지는 코드를 공개한 것은 거의 없다. 

http://code.google.com/p/lucene-web-search-and-trec-wt10g/ 주소로 

가보면 거의 유일하게 코드를 공개한 프로젝트이다. 중국의 어느대학

대학원생들이 텀프로젝트로 수행한 것을 공개한듯하다. 

어찌됐든 lucene으로 WT10G를 인덱싱하는 간단한 코드 IndexTrec.java와

TrecDocument.java를 첨부한다. 

두개의 파일을 org.apache.lucene.demo 패키지 폴더에 추가해 놓고 실행하면

된다. 

IndexTrec.java는 org.apache.lucene.demo 패키지의 IndexFiles.java를 기반으로

만들었으며 코드는 어렵지 않으니 직접 살펴보고 수정해도 좋을것이다.

크게 수정된 부분은 readDocs() 메소드이며 이 메소드에서 WT10G의 gz압축

파일의 스트림을 읽어들여 파싱하는 역할을 한다. 


TrecDocument.java에서는 인덱싱하는 필드를 조금 수정했다. 아래의 그림을 참고하자.














문서가 파일단위가 아닌 <DOCNO> </DOCNO>인 태그의 값으로 설정되어야 

해서 이부분을 추가했으며 기본적으로 WT10G는 웹문서의 집합이므로 

HTMLParser를 써야한다.  


소스 파일을 첨부한다.


2011년 7월 27일 수요일

OMAP2 processor에서 kernel의 secondary bootup

리눅스 커널을 스터디를 통해서 분석한지가 벌써 4년전인것 같다.

그떄 당시는 2.6.15버젼인가가 최신이고 2.6.13이 안정판이라 arm rearview 기반으로

2.6.13 버젼을 분석했던 기억이 난다. 

분석 초기에 개인적으로는 smp 머신에서 초기화는 1개의 cpu에서 해주고 

나머지 cpu를 어떻게 startup 해주는지가 상당히 궁금했다. 

다음은  당시에 내가 썼던 글이다. 

===============================
kernel_init  커널 쓰레드에서 다른 CPU를 다 꺠워준다. 

호출 순서는 다음과 같다.

start_kernel() -> rest_init() -> kernel_init -> smp_prepare_cpus() -> poke_milo() ( SYS_FLAGSCLR 레지스터의 
하위 2비트를 클리어) -> (pen_release = -1, realview_secondary_startup() )

후에 rearview_secondary_startup 루틴이 pen 값이 release 될때까지 루프

kernel_init -> smp_init() -> cpu_up() -> _cpu_up() -> __cpu_up() -> boot_secondary() -> pen relase

후에 realview_secondary_startup() 루틴이 secondary_startup()으로 점프하면

secondary_startup() 함수에서 나머지 cpu를 up 해준다. 

=================================

omap2에서도 크게 달라지지 않았지만 달라진 부분이 있다면 boot_secondary() 에서 

omap_modify_auxcoreboot0(0x200, 0xfffffdff);로 두번째 core의 startup을 준비하는 부분과

를 부팅한다는 점과  정도이다. 

Dalvik VM의 개괄적 Source 분석

Dalvik VM은 Android에서 돌아가는 VM이다. 이전에도 포스트 한바와 같이 

Phoneme project, harmony의 코드와도 외형과 핵심 구조체 등이 상당히 유사하다.

이전 포스트 이후 harmony를 대략적으로 분석해 보았으며 

결론은 대략 비슷한데 phoneme와 harmony는 상당히 일치하고 dalvik은 harmony를

바탕으로 만들어진 것이 맞다고 봐야 할듯하다. 

직접적인 코드 외에도 초기화시 로드하는 핵심클래스가 동일한 것들도 몇가지 있다.

예를 들면 다음과 같은 것들이 있다. ( dalvik/vm/Init.c의 dvmJniStartup()을 참고하자. )

org/apache/harmony/luni/platform/PlatformAddress.java
org/apache/harmony/luni/platform/PlatformAddressFactory.java
org/apache/harmony/nio/internal/DirectBuffer.java

간단히 dalvik vm이 실행되는 process를 정리해 보자.

main() -> option을 위한 메모리 할당 -> option 파싱 -> JNI_CreateJavaVM() -> findClass()
-> GetStaticMethodID() -> CallStaticVoidMethod() -> DetachCurrentThread() -> DestroyJavaVM() 

dalvik/vm/main.c의 main() 함수가 entry point이다. 대략 위와 같은 과정을 거치는데 거의 모든 

초기화의 과정이 JNI_CreateJavaVM()에서 이루어진다. 

이후에는 실행시킬 클래스를 findClass()로 실행시킬 main 메소드를 GetStaticMethodID()로 찾는다.

이후 CallStaticVoidMethod()로 class의 main 메소드를 실행시키면 이후의 과정은 main 메소드가

종료할때까지는 intepreter와 dex 파일과의 상호작용이라 봐야 하겠다. 

종료는 DetachCurrentThread()와 DestroyJavaVM()의 두가지 과정으로 볼수 있는데 

Exception에 의한 종료와 정상 종료 크게 두가지 경우가 있을수 있다.

jvm의 경우 일반적으로 따로 Thread를 사용하지 않아도 최소 1개의 쓰레드를 가지고 있는데 

이를 main thread라고 부른다. 일반적으로 static void main(String[] args)으로 선언한 메소드의

코드를 실행하는 역할을 한다고 보면 된다. 


dalvik vm의 전체개요를 이해하기 위해서는 JavaVM, JNIEnv의 두가지 구조체를 이해하는 것이

상당히 중요한데 코드에서는 다음과 같이 정의되어 있다. 

#if defined(__cplusplus)
typedef _JNIEnv JNIEnv;
typedef _JavaVM JavaVM;
#else
typedef const struct JNINativeInterface* JNIEnv;
typedef const struct JNIInvokeInterface* JavaVM;
#endif

C로 정의된 JNINativeInterface나 JNIInvokeInterface의 경우 디바이스 드라이버를 개발해

보신분들은 상당히 익숙한 구조일듯한 변수와 함수 포인터의 집합으로 구조체를 만들어 놓았다.

정리해 보면

JNIEnv는 대략적으로 dalvik vm의 환경 설정과 관련된 함수들이 쭈욱 모아져 있는데 

코드를 분석하기 위해서는 우선 CallMethod 계열, GetMethod 계열, FindClass 부분을 우선적으로

보는 것이 좋을 것이다.

JavaVM의 경우는 

DestroyJavaVM, AttachCurrentThread, DetachCurrentThread, GetEnv, AttachCurrentThreadAsDeamon

등의 단촐하게 5가지만 있다. 

JNIEnv와 JavaVM 구조체의 함수 포인터들은 각각

JavaVM: main -> JNI_CreateJavaVM()에서 gInvokeInterface의 값으로
JNIEnv: main()->JNI_CreateJavaVM()에서 gNativeInterface의 값으로 

셋팅된다. 


이후의 과정은 서술한 바와 같이 class를 찾고 class의 static main 메소드를 찾고 이를 호출하는

과정이다. 실제 코드는 다음과 같이 되어 있다.

(*env)->CallStaticVoidMethod(env, startClass, startMeth, strArray);


gInvokeInterface에서 찾아보아도 호출하는 함수의 실제 이름도 CallStaticVoidMethod로 동일하다.

CallStaticVoidMethod는 내부에서 CallStaticVoidMethodV를 호출하는데 이함수는 crags, scope

등으로 찾으려하면 잘 나오지 않는데 이는 코드의 선언이 다음처럼 되어 있기 떄문이다. 



 "##"은 변수 또는 함수의 이름을 접합시켜 주는 역할을 한다. 

위의 코드에서는 CallStatic##_jname##MethodA 처럼 사용됐는데 _jname이 컴파일 타임에 결정되어

반드시 결정되어 있어야만 하며 

예를 들어, CALL_STATIC(jbyte,Byte,result.b, false); 의 코드가 있다면

CallStaticByteMethodA와 같은 함수선언이 된것과 같은 효과가 있다. 

그럼 CallStaticVoidMethodV를 잠깐 살펴보자. 

JNI_ENTER()로 쓰레드의 상태를 변경해준후 바로 dvmCallMethodV()를 호출해준다. 

프레임에 공간을 확보한후에 argument를 처리하고 dvmInterpret()를 호출하여 

본격적으로 dex의 opcode의 처리를 시작한다. 

여기서 부터는 다시 복잡해 지므로 자바의 메소드 호출 방식 및 메소프 스택을 

처리하는 법에 관해서는 다음글에서 이어서 포스트한다.