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등 주옥같은 코드들이 있다. 



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