§ Used Physical Memory Map

Для того, чтобы обработчик страничного нарушения "знал", какие страницы физической памяти доступны и где именно они находятся, в нашем примере вводится битовая карта, которая будет называться UPMM (от англ. Used Physical Memory Map - карта использованной физической памяти). Эта аббревиатура и технология является число программным продуктом, придуманном мною лично, в процессорах Intel и их клонах нет ничего подобного; UPMM используется как один из возможных вариантов управления распределением памяти, при этом относительно простым и надёжным.
UPMM по сути представляет собой массив размером 4Кб, а по смыслу - битовую карту размером 32 Кбита. Каждый бит UPMM соответствует одной физической странице памяти; если он сброшен (т.е. равен 0), значит страница - свободна, если установлен (1) - то занята.
Работа с UPMM происходит блоками по 32 бита, т.е. если, например, нужно обратиться к 49-биту, производится чтение двойного слова по смещению 4 относительно начала UPMM, а уже в этом двойном слове обрабатывается 17-й бит.
Обработка битовой карты блоками по 32 бита позволяет максимально быстро обращаться к ней - ведь всё равно процессор тратит одинаковое число тактов при обращении к байту или двойному слову в памяти (если, конечно, процессор - не SX), а оптимизация по скорости у многих ранних моделей вообще относится только к командам, обрабатывающим 32-разрядные операнды.
Для удобства работы с UPMM, для неё создаётся отдельный сегмент данных, доступный через селектор UPMM_sel. Размер этого сегмента - 4Кб, что позволяет описать до 128Мб физической памяти. Для демонстрации страничного преобразования этого вполне достаточно, но для полнофункционального обработчика понадобится сегмент размером 128Кб, чтобы описать 4Гб памяти.
Установка сегмента, описывающего UPMM производится перед переходом в защищённый режим следующим образом:

1	mov  edx, UPMM_size
2	mov  eax, cr3	; UPMM создаём в странице, следующей сразу
3	add  eax, 2000h	; за первой таблицей страниц.
4	mov  cx, 92h    ; Сегмент данных.
5	call set_descriptor

Здесь в переменной UPMM_size содержится размер сегмента (4Кб). Для .com-программы его можно менять в небольших пределах, т.к. при работе наших примеров подразумевается, что они, во-первых, являются .com-программами, а во-вторых, вместе со всеми данными, занимают не более 64Кб памяти.
Прежде, чем будет создана UPMM, необходимо определить её размер в dd-переменной UPMM_size, а также какие страницы физической памяти 1-го мегабайта уже заняты и какие - свободны. Для этого предусмотрена процедура "setup_for_UPMM":

1setup_for_UPMM:
2;    Установка размера UPMM (в 4Кб), определение адреса и размера свободной
3; DOS-памяти и физических страниц, на которые она приходится.
4; Возврат: значения двух переменных:
5;	DOS_free_mem_start_page - страница, с которой начинается DOS-память,
6;	DOS_free_mem_pages - число целых страниц, на которые она приходится.
7
8	xor	ebp,ebp	;    Число страниц по умолчанию свободной
9				; DOS-памяти (пока - 0).
10
11	mov	UPMM_size,4096
12
13; Сокращаем выделенный блок памяти этой программе до 64Кб:
14
15	mov	ah,4ah
16	push	cs
17	pop	es
18	mov	bx,4096		; Число параграфов, соответствующее 64Кб.
19	int	21h
20
21; Выясняем размер свободной DOS-памяти.
22
23	mov	bx,-1
24	mov	ah,48h
25	int	21h
26
27; BX = максимальный размер в параграфах
28
29	movzx	ecx,bx
30	shl	ecx,4		;    ECX = число байт свободной памяти в
31				; первом мегабайте.
32
33	mov	ah,48h
34	int	21h		; Распределяем всю свободную DOS-память.
35
36	push	ax		; Сохраняем сегмент начала блока памяти.
37
38	mov	es,ax
39	mov	ah,49h
40	int	21h		; Освобождаем распределённую память.
41
42	pop	ax
43	movzx	eax,ax
44	shl	eax,4		;    EAX = физический адрес начала
45				; свободной DOS-памяти.
46	mov	ebx,eax
47	add	ebx,ecx	;    Максимальное значение адреса (+1) в
48				; свободном блоке DOS-памяти.
49
50	mov	dx,ax
51	and	ax,0f000h
52	sub	dx,ax
53	cmp	dx,0		; EAX был кратен 4Кб?
54	je	sfupmm_1	;    Если да, то свободная DOS-память
55				; начинается на границе страницы.
56
57	add	eax,1000h	;    Если нет - выравниваем блок на границу
58				; следующей страницы.
59
60sfupmm_1:
61	cmp	eax,ebx	;    Если начало блока (уже выравненное на
62				; границу страницы) превысило её предел,
63	jae	sfupmm_end	; то - выход из процедуры.
64
65
66	shr	eax,12		;    EAX = AL = номер страницы, с которой
67				; начинается блок DOS-памяти.
68	shr	ecx,12		; ECX = CL = число целых страниц этого блока.
69	mov	ebp,ecx
70
71	mov	DOS_free_mem_start_page,al
72
73sfupmm_end:
74	mov	ecx,ebp
75	mov	DOS_free_mem_pages,cl
76
77	ret

Для создания UPMM используется процедура "create_UPMM". Она способна создать UPMM размером до 128Кб, но используется для 4 килобайтовой UPMM. Эта процедура вызывается сразу после процедуры "get_phys_mem_size" и в качестве входного параметра использует размер памяти, возвращённый ею в EAX. Процедура "create_UPMM" использует также dd-переменную UPMM_size и макрос UPMM_sel - селектор дескриптора сегмента, описывающего UPMM:

1create_UPMM:
2;    Создаёт UPMM (Used Physical Memory Map - битовая карта
3; использованной физической памяти).
4; EAX = число байт физической памяти; используеюся UPMM_sel, UPMM_size.
5
6	push	eax
7	push	ecx
8	push	edx
9	push	es
10	push	edi
11
12	shr	eax,12		;    Теперь в EAX - число страниц
13				; физической памяти.
14	mov	ecx,eax
15	and	cl,11100000b
16	sub	eax,ecx
17	shr	ecx,5		; ECX = (число страниц физической памяти) / 32.
18				; EAX = AL = остаток от этого деления.
19	mov	dl,al		; Сохраняем остаток.
20
21 ; ECX = CX = число двойных слов, из которых состоит UPMM.
22
23; Устанавливаем все биты в UPMM
24
25	push	cx
26
27	mov	ax,UPMM_sel
28	mov	es,ax
29	xor	edi,edi
30
31	mov	ecx,UPMM_size	;    Размер сегмента, в котором будет
32					; хранится UPMM.
33
34	shr	ecx,2	;    ECX = CX. Максимальный размер UPMM = 128Кб
35			; (для 4Гб памяти), следовательно, число двойных
36			; слов, из которых она состоит не превысит 65'536
37
38	cld
39	xor	eax,eax
40	dec	eax	; EAX = -1 = FFFF FFFFh
41
42	db	67h	; Атрибут размера опреранда - цикл будет по ECX.
43	rep	stosd	; Заполняем таблицу.
44
45; Сбрасываем свободные страницы 1-го мегабайта
46
47	push	dx
48
49	mov	al,DOS_free_mem_start_page
50	mov	ah,al
51	and	al,11100000b
52	sub	ah,al
53	shr	al,3		;    AL = AL / 8, AH = остаток от деления
54				; DOS_free_mem_start_page на 32.
55
56	movzx	edi,al		;    ES:EDI указывает в UPMM на двойное,
57				; слово в котором начинается описание
58				; блока свободной DOS-памяти.
59
60	mov	edx,-1		;    EDX будет использоваться как XOR-маска
61				; для сброса битов в двойном слове из UPMM.
62
63 ; AH = число бит, которые должны остаться установленными, начиная
64 ;  с 0-го разряда регистра.
65
66	mov	cl,ah		;    CL = число бит, на которое нужно
67				; сдвинуть маску в EDX.
68	shr	edx,cl		; Сбрасываем биты.
69	shl	edx,cl
70
71	mov	eax,es:[ edi ]
72	xor	eax,edx
73
74	mov	ch,32
75	sub	ch,cl
76	mov	cl,ch		; CL = число бит, сброшенных в EDX (и в EAX).
77
78	mov	ch,DOS_free_mem_pages
79	cmp	ch,cl
80	ja	cupmm_1
81
82 ; Если свободных страниц меньше, чем сброшенных бит в EAX, то нужно
83 ;  установить обратно те, которые заняты.
84
85	sub	cl,ch
86	mov	ch,32
87	sub	ch,cl
88	mov	cl,ch		; Число бит, на которое нужно сдвинуть EDX
89
90	mov	edx,-1		;    Теперь EDX будет использоваться
91				; как OR-маска.
92
93	shr	edx,cl		; Сбрасываем младшие биты
94	shl	edx,cl
95
96	or	eax,edx
97
98	stosd			; Всё, установили.
99	jmp	cupmm_2
100
101cupmm_1:
102	sub	ch,cl
103	stosd
104
105	mov	eax,es:[ edi ]
106
107	xor	eax,eax
108	mov	cl,32
109	cmp	ch,cl
110	jae	cupmm_1	;    Очищаем нулями все двойные слова,
111				; пока CH > 32
112
113	cmp	ch,0
114	je	cupmm_2
115
116	sub	cl,ch
117	shl	eax,cl
118	shr	eax,cl		; Сбрасываем оставшиеся биты
119
120	stosd			; Всё, установили.
121
122cupmm_2:
123;    Страницы, используемые как HMA (первые 64Кб 2-го мегабайта), оставляем
124; как занятые.
125
126; Теперь, используя значение в CX и DX можно записывать UPMM:
127
128	pop	dx	;    Восстанавливаем остаток деления числа страниц
129			; физической памяти на 32.
130	pop	cx	;    Восстанавливаем число двойных слов, из
131			; которых состоит UPMM. Значение в CX - не менее 8.
132
133	sub	cx,8	;    Вычитаем 256 страниц, соответствующих
134			; первому мегабайту (8 двойных слов
135			; содержат 256 бит и описывают 256 страниц).
136
137	jcxz	cupmm_end	; Всё? Памяти только 1Мб?
138
139	mov	edi,32		;    ES:EDI указывает в UPMM на начало
140				; 2-го мегабайта.
141
142	mov	eax,es:[ edi ]
143	shl	eax,16		;    Сбрасываем старшие 16 бит (младшие
144	shr	eax,16		; описывают HMA).
145
146	stosd
147
148; Теперь нужно вычесть 32 из числа оставшихся физических страниц:
149
150	dec	cx
151	jcxz	cupmm_3
152
153; Сбрасываем все биты, соответствующие свободным страницам:
154 ; сначала блоками по 32 страницы:
155
156	xor	eax,eax
157	rep	stosd
158
159cupmm_3:
160 ; потом - оставшееся число страниц:
161
162	mov	cl,dl
163	mov	eax,es:[ edi ]
164	shr	eax,cl
165	shl	eax,cl
166
167	stosd
168
169cupmm_end:
170	pop	edi
171	pop	es
172	pop	edx
173	pop	ecx
174	pop	eax
175
176	ret

Для поиска свободной страницы в UPMM используется процедура "find_free_phys_page", которая, по сути, ищет первый нулевой бит в UPMM. После того, как он будет найден, процедура вычисляет адрес физической страницы, которой соответствует этот бит и возвращает его в EAX.
При возврате из этой процедуры флаг переноса CF (в EFLAGS) содержит информацию о процессе поиска - если он сброшен, значит всё в порядке, страница найдена и её адрес находится в EAX. Если же CF установлен, то в UPMM больше нет нулевых бит, следовательно, вся доступная физическая память уже занята. Везде в нашем примере после вызова этой процедуры проверяется флаг CF и если он установлен, выводится сообщение о недостатке памяти и производится аварийное прекращение программы. При реализации системы виртуальной памяти, в таком случае следовало бы найти наименее используемую физическую страницу, свопнуть её на диск и использовать её далее как свободную страницу, но в нашем примере внимание концентрируется именно на обработчике исключения страничного нарушения, а не механизме виртуальной памяти.

1find_free_phys_page:
2; Ищет свободную физическую страницу используя битовую карту UPMM.
3; Возврат:	CF = 1 - свободных страниц нет.
4;		CF = 0 - EAX = физический адрес найденной страницы.
5
6	push	ebx
7	push	ecx
8	push	edx
9	push	es
10	push	edi
11
12	mov	ax,UPMM_sel
13	mov	es,ax
14	xor	edi,edi
15	mov	ecx,phys_mem_size
16	shr	ecx,12		;    Если разделить phys_mem_size на 4096, то мы
17				; получим число страниц физической памяти.
18	mov	edx,ecx
19	and	cl,11100000b
20	sub	edx,ecx
21	shr	ecx,5	;   Если это число страниц физической памяти
22			; разделить ещё на 32, то мы получим число блоков
23			; по 32 страницы - его мы и будем использовать
24			; в цикле просмотра UPMM. При этом в EDX = DL будет
25			; остаток от этого деления.
26
27; Цикл будет по CX, т.к. ECX был сдвинут на 17 разрядов вправо.
28
29ffpp_1:
30	mov	eax,es:[ edi ]
31
32	cmp	eax,-1		;    -1 = FFFF FFFFh - проверяем, все ли
33				; страницы заняты в данном блоке
34				; из 32-х страниц.
35	je	ffpp_3		;    Если все, то переходим на "ffpp_3".
36
37	push	cx
38	mov	cx,32
39
40ffpp_2:
41	shr	eax,1		;    Сдвиг помещает бит во флаг CF.
42	jnc	ffpp_find	;    Если был сдвинут бит, равный 0, то мы
43				; нашли свободную страницу.
44	loop	ffpp_2
45
46	pop	cx
47
48ffpp_3:
49	add	edi,4
50	loop	ffpp_1
51
52	mov	cl,dl
53	jcxz	ffpp_bad_end
54	push	cx
55
56ffpp_4:
57	mov	eax,es:[ edi ]
58	shr	eax,1
59	jnc	ffpp_find
60
61	loop	ffpp_4
62
63	pop	cx
64
65ffpp_bad_end:
66	stc		; CF = 1 - страница не найдена.
67
68ffpp_end:
69	pop	edi
70	pop	es
71	pop	edx
72	pop	ecx
73	pop	ebx
74
75	ret
76
77ffpp_find:
78	mov	al,32
79	sub	al,cl
80	mov	cl,al		;    Теперь CL содержит номер обнаруженного
81				; нулевого бита.
82
83	pop	ax		;    Восстанавливаем сохранённое значение,
84				; CX теперь оно нам не нужно.
85
86;    Теперь нужно установить в UPMM найденный бит - теперь эта страница
87; будет занята.
88
89	mov	eax,1
90	shl	eax,cl		; В EAX установлен только найденный бит.
91	or	es:[ edi ],eax	; Устанавливаем его в UPMM.
92
93; Теперь по позиции этого бита в UPMM вычисляем физический адрес страницы.
94
95	mov	eax,edi	;    EDI используется как указатель в UPMM. Т.к.
96				; каждый байт UPMM описывает 8 страниц (это - 32Кб
97				; памяти), а EDI у нас увеличивался в цикле на 4
98				; то умножив EDI на 32Кб мы получим физический
99				; адрес первой страницы блока из 32-х страниц.
100				;    Все вычисления адреса мы будем производить
101				; в EAX.
102
103	shl	eax,15		; EAX = EAX * 32K.
104	movzx	ecx,cl		; CL = ECX = номер бита в блоке из 32-х бит.
105
106	shl	ecx,12		;    Т.к. этот бит определяет страницу, то
107				; умножив его позицию на 4096 мы получим
108				; смещение адреса этой страницы
109				; относительно блока.
110
111	add	eax,ecx	;    Всё. EAX содержит физический адрес
112				; найденной свободной страницы физической
113				; памяти.
114
115	clc		; CF = 0 - страница найдена.
116
117	jmp	ffpp_end
118