code cat

linux kenel timestamp
--------------------------------------
include
include

char tbuf[50], *tp;
unsigned tlen;
unsigned long long t;
unsigned long nanosec_rem;
int this_cpu = smp_processor_id();

t = cpu_clock(this_cpu);
nanosec_rem = do_div(t, 1000000000);
tlen = sprintf(tbuf, "[%5lu.%06lu] ",
(unsigned long) t,
nanosec_rem / 1000);

iPhone 에서 작성된 글입니다.

출처: virtual linux manager by Mel Gorman

memory 는 bank로 나뉘어짐
bank는 node라고 불리며,
node는 struct pglist_data로 표현됨.(UMA일때도 마찬가지)

pglist_data는 pg_data_t로 참조된다. 
시스템의 모든 node는 NULL로 끝나는 pgdata_list 이라는 리스트로 관리된다.
그리고 각 node는 pg_data_t->node_next로 다른 node와 연결된다.

UMA의 경우 contig_page_data라는 하나의 pg_data_t 구조체를 사용한다.(노드가 하나 이니까)

각 node는 'zone' 이라 불리는 여러개의 블록으로 나뉜다.

zone은 struct zone_struct 이라는 구조체로 정의되며, zone_t로 사용자정의된다.

zone의 종류에는,
ZONE_DMA 
ZONE_NORMAL
ZONE_HIGHMEM
(ZONE_MOVEABLE)
이 있다.
 
신경써야 할 부분은 ZONE_NORMAL이다.  ZONE_HIGHMEM은 ZONE_NORMAL의 상위 위쪽 부분이다.

시스템의 메모리는 page frame이라는 고정된 chunk들로 이루어져 있다.
각각의 physical page frame들은 struct page라는 구조체로 표현되며,
이 모든 구조체들은 mem_map이라는 배열에 저장된다.
(mem_map은 보통 ZONE_NORMAL 시작부분이나 지정된 커널 로딩 영역 뒤에 저장된다)

2.1 Nodes
리눅스는 page를 할당할 때, node-local alloocation policy를 사용해서
현재 실행 중인 CPU에서 가장 가까운 node의 메모리를 할당한다.

pg_data_t, 즉 pglist_data는 다음가 같이 정의되어 있다.
struct pglist_data { zone_t node_zones[MAX_NR_ZONES]; zonelist_t node_zonelists[GFP_ZONEMASK+1]; int nr_zones; struct page *node_mem_map; unsigned long *valid_addr_bitmap; struct bootmem_data *bdata; unsigned long node_start_paddr; unsigned long node_start_mapnr; unsigned long node_size; int node_id; struct pglist_data *node_next; } pg_data_t;

node_zones	ZONE_HIGHMEM, ZONE_NORMAL_ZNOE_DMA가 있다.
node_zonelists	zone들이 할당되는 순서를 가지고 있다.  free_area_init_core()에 호출 된 mm/page_alloc.c의 build_zonelists()가  순서를 정한다.
nr_zones	zones의 갯수
valid_addr_bitmap	메모리 node에 있는 "holes" 에 대한 비트맵
bdata	boot memory allocator
node_start_paddr	node의 시작 주소(physical)   Page Frame Number(PFN)에 기록하는게 좋다.   PFN은 physicla memory의 index이며, page-sized unit 단위로 세어진다. PFN 은 (page_phys_addr >> PAGE_SHIFT) 로 손쉽게 정의될 수 있다.
node_start_mapnr	전역 mem_map안의 page offset.    free_area_init_core()에서 mem_map과 지역적 mem_map사이의 페이지 개수로 계산됨
node_size	zone안의 총 page 수
node_id	node ID (NID).  0부터 시작함
node_next	위에서 말한 node list의 다음 node를 가리킴

             
앞서 말했듯이, 시스템의 모든 node들은 pgdat_list라는 리스트에서 관리되며, init_bootmem_core()에 의해 이 리스트에 추가된다.

2.2 Zones

각 zone들은 struct zone_struct으로 구성된다. (linux/mmzone.h 참조)

내용은 다음과 같다.

typedef struct zone_struct { spinlock_t lock; unsigned long free_pages; unsigned long pages_min, pages_low, pages_high; int need_balance; free_area_t free_area[MAX_ORDER]; wait_queue_head_t * wait_table; unsigned long wait_table_size; unsigned long wait_table_shift; struct pglist_data *zone_pgdat; struct page *zone_mem_map; unsigned long zone_start_paddr; unsigned long zone_start_mapnr; char *name; unsigned long size; } zone_t;

lock	zone을 보호하는 spinlock
free_pages	zone에 존재하는 free page
pages_min,   page_low, pages_high
zone_pgdata	pg_data_t 를 가리킨다.
zone_mem_map	전역 mem_map
zone_start_paddr	node_start_paddr와 유사
zone_start_mapnr	node_start_mapnr와 유사
name	zone 이름, "DMA", "NORMAL", "HighMem"
size	pages단위로 표현된 zone의 사이즈

 

2.2.1 Zone Watermarks

시스템에 남아있는 메모리가 적을 경우, kswapd라는 pageout 데몬이 실행되어 page들을 free하기 시작한다.  만약 메모리를 많이 회수해야 한다면, kswapd 데몬은 동기적으로 메모리를 free 한다.(이 방식은 direct-reclaim이라고 불리기도 한다.)

각 zoned은 세가지의 watermark를 가지고 있는데, 이들은 각각 다음과 같다.

pages_low	free page의 수가 pages_low에 이르면, kswapd가 buddy allocator에 의해 깨어나서 page들을 free한다
pages_min	pages_min에 이르면, buddy allocator는 kswapd를 동기화적으로 돌린다.
pages_high	page_high에 이르면 kswapd는 다시 sleep으로 돌아간다.

pages_min은 free_area_init_core()에서 메모리 초기화 과정에서 page 단위로 표현된 zone의 크기로 표현되어 계산된다.

2.2.2 Calculating the size of Zones

각 zone의 크기는 setup_memory()에서 계산된다.

PFN은 pages단위로 세어진 실제 메모리 맵(physical memory map)안의 오프셋이다.

min_low_pfn은 첫번째 PFN이며, _end 다음의 첫번째 페이지에 위치한다.  min_low_pfn은 나중에 쓰일 boot memory allocator를 위해 mm/bootmem.c 에 file scope 변수로 지정되어 있다.

unsigned long min_low_pfn;

unsigned long max_low_pfn;

unsigned long max_pfn;

마지막 페이지 프레임인 max_pfn 은 아키텍쳐 의존적으로 계산된다.  x86의 경우 find_max_pfn()으로 e820 map을  통해 가장 높은 값을 갖는 페이지 프레임을 읽는다. (e820은 BIOS를 통해 얻어지는 테이블이며, 어떤 physicla memory가 있는지, 예약되어 있는지등을 알려준다)  

max_low_pfn은 (x86의 경우) find_max_low_pfn()을 통해 계산되며, 이는 ZONE_NORMAL의 끝을 표시한다.

	ZONE
_end
min_low_pfn	first page
	pages ...
max_low_pfn	end of ZONE_NORMAL     <- kernel/userspace split point

2.2.3 Zone Wait Queue Table

(생략)

 

2.3 Zone Initialization

zone 들은 kernel page table 이 paginig_init()에 의해 완전히 세팅되고 나면 초기화 된다.  페이지 테이블 초기화에 대해서는 3.6을 참조하자.

아키텍쳐마다 방식에는 다르겠지만, 기본적으로 UMA 일 경우, free_area_init()에 보낼 매개변수를, NUMA일 경우, free_area_init_node()에 보낼 매게변수를 결정한다.  이 매게변수들은 다음과 같다.

nid	초기화 될 zone을 가지고 있는 NODE의 NODE id
pgdat	초기화되는 node의 pg_data_t이며, UMA의 경우 contig_page_data이다.
pmap	free_area_init_core()에 의해 지정되며, local mem_map의 시작부분을 가리킨다. NUMA는 mem_map을 PAGE_OFFSET에 시작하는 가상 배열로 생각하기 때문에 무시하며, UMA의 경우 pmap은 global mem_map을 가리킨다.
zone_sizes	각 zone의 크기를 담고 있는 배열
zone_start_paddr	첫번째 zone의 시작 실제 주소(starting physical address)
zone_holes	zones에 있는 메모리 홀의 총 사이즈를 담고 있는 배열

free_area_init_core()는 각 zone_t의 내용을 연관성이 있는 정보로 채우는 역활 및 mem_map 배열 할당을 한다.  현 상황에서는 어떤 페이지가 free인지는 알 수 없으며, boot memory allocator의 작업이 끝날 때 까지는 알 수 없다.

 

2.4 Initializing mem_map

mem_map은 시스템 초기화 과정에서 생성된다.

NUMA의 경우, global mem_map이 PAGE_OFFSET에서 시작하는 가상 배열로 취급되며, 각 node 마다 free_area_init_node()를 호출하여 이 가상 배열을 할당한다.  

UMA의 경우, free_area_init()이 contig_page_data를 node로, global mem_map을 local mem_map으로 동일하게 취급한다.

locla mem_map은 free_area_init_core()에 의해 할당되며, 이를 위한 배열은 boot memory allocator가 alloc_bootmem_node()를 호출하여 할당한다.  UMA의 경우, 이렇게 할당된 메모리는, 위에서 말한 거 처럼, global mem_map이 되나, NUMA의 경우 조금 다르다.  NUMA는 local mem_map을 각 node의 고유한 메모리에서 할당하며, global mem_map의 경우 따로 할당되지는 않으나, (가상 배열로 취급되는)PAGE_OFFSET으로 설정된다.  local map은 pg_data_t->node_mem_map에 저장된다.

node에 존재하는 각 zone들은  가상 mem_map의 주소를 zone_t->zone_mem_map에 저장한다.  이 외의 작업에서는 mem_map을 실제 배열로 취급한다.

 

2.5 Pages

모든 시스템의 physical page frame은 struct page를 가지고 있다.

      

출처: http://www.ibm.com/developerworks/linux/library/l-gcc-hacks/

GCC 확장(?)의 하나로서, GCC는 변수에 대한 참조를 통해서 타입을 확인할 수 있다. 이런 방법을 흔히 'generic programming'이라고 부르며 비슷한 기능을 제공하는 것을 현재 쓰이는 언어들에서 찾아 볼 수 있다.[1]
Linux의 경우, typeof를 사용하여 타입 종속적인 작업, (예를 들어 min/max 를 구별)을 할 수 있다.

간단한 예를 들어보자.(/linux/include/linux/kernel.h)
#define min(x, y) ({ \ typeof(x) _min1 = (x); \ typeof(y) _min2 = (y); \ (void) (&_min1 -- &_min2); \ _min1 < _min2 ? _min1 : _min2 })
보이는 바와 같이 _min1은 x가 어떤 타입이냐에 따라서 그 타입을 가지게 된다; _min2 역시 y에 따라 타입이 달라진다. 이렇게 타입을 가지게 되므로 크기를 비교할 수 있게 되며, 어떠한 타입이 들어와도 대응할 수 있게 된다.

[1] 제네릭 프로그래밍(Generic programming)은 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있는 기술에 중점을 두어 재사용성을 높일 수 있는 프로그래밍 방식이다

1 Booting ARM Linux
2 =================
3
4 Author: Russell King
5 Date : 18 May 2002
6
7 The following documentation is relevant to 2.4.18-rmk6 and beyond.
8
9 In order to boot ARM Linux, you require a boot loader, which is a small
10 program that runs before the main kernel. The boot loader is expected
11 to initialise various devices, and eventually call the Linux kernel,
12 passing information to the kernel.
13
14 Essentially, the boot loader should provide (as a minimum) the
15 following:
16
17 1. Setup and initialise the RAM.
18 2. Initialise one serial port.
19 3. Detect the machine type.
20 4. Setup the kernel tagged list.
21 5. Call the kernel image.
22
23
24 1. Setup and initialise RAM
25 ---------------------------
26
27 Existing boot loaders: MANDATORY
28 New boot loaders: MANDATORY
29
30 The boot loader is expected to find and initialise all RAM that the
31 kernel will use for volatile data storage in the system. It performs
32 this in a machine dependent manner. (It may use internal algorithms
33 to automatically locate and size all RAM, or it may use knowledge of
34 the RAM in the machine, or any other method the boot loader designer
35 sees fit.)
36
37
38 2. Initialise one serial port
39 -----------------------------
40
41 Existing boot loaders: OPTIONAL, RECOMMENDED
42 New boot loaders: OPTIONAL, RECOMMENDED
43
44 The boot loader should initialise and enable one serial port on the
45 target. This allows the kernel serial driver to automatically detect
46 which serial port it should use for the kernel console (generally
47 used for debugging purposes, or communication with the target.)
48
49 As an alternative, the boot loader can pass the relevant 'console='
50 option to the kernel via the tagged lists specifying the port, and
51 serial format options as described in
52
53 Documentation/kernel-parameters.txt.
54
55
56 3. Detect the machine type
57 --------------------------
58
59 Existing boot loaders: OPTIONAL
60 New boot loaders: MANDATORY
61
62 The boot loader should detect the machine type its running on by some
63 method. Whether this is a hard coded value or some algorithm that
64 looks at the connected hardware is beyond the scope of this document.
65 The boot loader must ultimately be able to provide a MACH_TYPE_xxx
66 value to the kernel. (see linux/arch/arm/tools/mach-types).
67
68
69 4. Setup the kernel tagged list
70 -------------------------------
71
72 Existing boot loaders: OPTIONAL, HIGHLY RECOMMENDED
73 New boot loaders: MANDATORY
74
75 The boot loader must create and initialise the kernel tagged list.
76 A valid tagged list starts with ATAG_CORE and ends with ATAG_NONE.
77 The ATAG_CORE tag may or may not be empty. An empty ATAG_CORE tag
78 has the size field set to '2' (0x00000002). The ATAG_NONE must set
79 the size field to zero.
80
81 Any number of tags can be placed in the list. It is undefined
82 whether a repeated tag appends to the information carried by the
83 previous tag, or whether it replaces the information in its
84 entirety; some tags behave as the former, others the latter.
85
86 The boot loader must pass at a minimum the size and location of
87 the system memory, and root filesystem location. Therefore, the
88 minimum tagged list should look:
89
90 +-----------+
91 base -> | ATAG_CORE | |
92 +-----------+ |
93 | ATAG_MEM | | increasing address
94 +-----------+ |
95 | ATAG_NONE | |
96 +-----------+ v
97
98 The tagged list should be stored in system RAM.
99
100 The tagged list must be placed in a region of memory where neither
101 the kernel decompressor nor initrd 'bootp' program will overwrite
102 it. The recommended placement is in the first 16KiB of RAM.
103
104 5. Calling the kernel image
105 ---------------------------
106
107 Existing boot loaders: MANDATORY
108 New boot loaders: MANDATORY
109
110 There are two options for calling the kernel zImage. If the zImage
111 is stored in flash, and is linked correctly to be run from flash,
112 then it is legal for the boot loader to call the zImage in flash
113 directly.
114
115 The zImage may also be placed in system RAM (at any location) and
116 called there. Note that the kernel uses 16K of RAM below the image
117 to store page tables. The recommended placement is 32KiB into RAM.
118
119 In either case, the following conditions must be met:
120
121 - Quiesce all DMA capable devices so that memory does not get
122 corrupted by bogus network packets or disk data. This will save
123 you many hours of debug.
124
125 - CPU register settings
126 r0 = 0,
127 r1 = machine type number discovered in (3) above.
128 r2 = physical address of tagged list in system RAM.
129
130 - CPU mode
131 All forms of interrupts must be disabled (IRQs and FIQs)
132 The CPU must be in SVC mode. (A special exception exists for Angel)
133
134 - Caches, MMUs
135 The MMU must be off.
136 Instruction cache may be on or off.
137 Data cache must be off.
138
139 - The boot loader is expected to call the kernel image by jumping
140 directly to the first instruction of the kernel image.

툴체인 설치 하고 커널 컴파일 준비 끝!

커널의 선점조건
예전에는 커널은 비선점형이었으나 2.6 버젼부터 선점형으로 바뀌었다. 그러기 위해서 각 프로세스 스택의 thread_info에 preempt_count 라는 변수를 추가하였고, 이 값은 락의 숫자가 증가함에 따라 증가하고 감소하면 같이 감소한다. preemt_count 값이 0일 때에 비로서 선점이 가능하다. 락이 해제될 시 preemt_count 값이 0 이면 락을 푸는 코드는 need_resched() 를 통하여 스케쥴이 필요한지 체크한다. 한편 커널은 태스크가 커널 블록내에 있거나 단도직입적으로 schedule() 를 호출시에도 선점 가능하다.

커널 스레드와 일반 프로세스와 다른 점 중 가장 두드러진 부분은 커널 스레드는 어드레스 스페이스가 없다는 것이다(mm 포인터 = NULL)

커널 스레드는 커널 스페이스에서만 실행되며 유저공간으로 컨텍스트 스위칭 하지 않는다. 하지만 일반 프로세스와 같이 스케쥴되고 선점 가능하다.

대표적인 커널 스레드로는 flush 와 ksoftirqd가 있으며 ps -ef 로 커널 스레드 리스트를 확인할 수 있다. 커널 스레드는 오직 다른 커널 스레드만이 생성 할 수 있다


iPhone 에서 작성된 글입니다.