OSDev

для всех
Текущее время: 25 сен 2018, 18:37

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
СообщениеДобавлено: 14 май 2010, 16:11 

Зарегистрирован: 16 фев 2010, 22:03
Сообщения: 101
Я не храню данные о выделенных страницах отдельно. Только о свободных. А когда уничтожаю процесс просто просматриваю его каталог страниц и освобождаю всё что ниже 0x7FFFFFFFFFFF (у меня 64 бита. а выше располагается ядро). разумеется я просматриваю таблицы рекурсивно и только те, что присутствуют, поэтому это занимает немного времени. Для общих разделяемых участков памяти я буду создавать информационные структуры, а пока мне это не надо. Для выделения памяти у меня реализововал два варианта:
1) битовая карта. просто в реализации. можно выделять не только оперативную память, но и страницы с произвольными адресами. Поскольку карта памяти занимает 8 ГБ (если читать что шина адреса не может быть шире 48 бит. в реальности она даже немного меньше) я поступаю так:
1. Выделяю память под карту памяти для всей оперативной памяти.
2. В обработчике Page Fault смотрю на адрес возврата. Если он внутри процедуры получения страницы с произвольным адресом, то выделяю страницу для этой части карты памяти.
Вот процедуры выделения и освобождения памяти:
Код:
; Получение RCX страниц физической памяти
alloc_phis_pages:
   cmp [phis_memory_mutex], FALSE
   jne alloc_phis_pages
   mov [phis_memory_mutex], TRUE
   push rax rbx rcx rdx
   mov rax, 0x100000 / 4096
   mov rcx, [memory_size]
   shr rcx, 12
   sub rcx, rax
   mov rbx, memory_map
.find:
   bt [rbx], rax
   jnc .check
   inc rax
   loop .find
   mov qword[rsp + 24], -1
.exit:
   pop rdx rcx rbx rax
   mov [phis_memory_mutex], FALSE
   ret
.check:
   mov [rsp + 24], rax
   mov rdx, rcx
   mov rcx, [rsp + 8]
@@:
   bt [rbx], rax
   jc .new_find
   inc rax
   dec rdx
   loop @b
   mov rcx, [rsp + 8]
   mov rax, [rsp + 24]
@@:
   bts [rbx], rax
   inc rax
   loop @b
   shl qword[rsp + 24], 12
   mov rcx, [rsp + 8]
   sub [free_pages_count], rcx
   jmp .exit
.new_find:
   mov rcx, rdx
   jmp .find
; Получение RCX страниц оперативной памяти начиная с RAX
get_phis_pages:
   cmp [phis_memory_mutex], FALSE
   jne get_phis_pages
   mov [phis_memory_mutex], TRUE
   push rax rbx rcx
   mov rbx, memory_map
@@:
..get_phis_pages_fault_place:
   bt [rbx], rax
   jc .error
   inc rax
   loop @b
   mov rax, [rsp + 16]
   mov rcx, [rsp]
@@:
   bts [rbx], rax
   inc rax
   loop @b
   mov rax, TRUE
.exit:
   pop rcx rbx rax
   mov [phis_memory_mutex], FALSE
   ret
.error:
   xor rax, rax
   jmp .exit
; Освобождение RCX страниц физической памяти, начиная с RAX
free_phis_pages:
   push rax rbx rcx
   shr rax, 12
   mov rbx, memory_map
@@:
   btc [rbx], rax
   inc rax
   loop @b
   pop rcx rbx rax
   add [free_pages_count], rcx
   ret


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 14 май 2010, 16:43 

Зарегистрирован: 16 фев 2010, 22:03
Сообщения: 101
А вот мой вариант со списком:
Код:

; Получение RCX страниц оперативной памяти (RAX - физический адрес)
align 8
alloc_phis_memory:
        mov rax, [free_pages_count]
        sub rax, rcx
        cmp rax, [min_free_pages_count]
        jl .error
        mov [free_pages_count], rax
        mov rax, [free_memory_pointer]
@@:
        call temp_mount_page
        cmp rcx, [temp_page + MEMORY_BLOCK.size]
        je .equals
        jb .below
        mov rax, [temp_page + MEMORY_BLOCK.next]
        cmp rax, [free_memory_pointer]
        jne @b
.error:
        mov rax, -1
        ret
.equals:
        push rax rdx
        mov rax, [temp_page + MEMORY_BLOCK.next]
        mov rdx, [temp_page + MEMORY_BLOCK.prev]
        call temp_mount_page
        mov [temp_page + MEMORY_BLOCK.prev], rdx
        xchg rax, rdx
        call temp_mount_page
        pop rdx rax
.exit:
        and rax, not 0xFFF
        ret
.below:
        sub [temp_page + MEMORY_BLOCK.size], rcx
        push rcx
        mov rcx, [temp_page + MEMORY_BLOCK.size]
        shl rcx, 12
        add rax, rcx
        pop rcx
        jmp .exit
; Освобожение RCX страниц оперативной памяти начиная с RAX
align 8
free_phis_memory:
        add [free_pages_count], rcx
        push rbx rcx rdx rdi
        mov rbx, rax
        mov rax, [free_memory_pointer]
@@:
        push rax
        call temp_mount_page
        pop rax
        mov rdx, [temp_page + MEMORY_BLOCK.size]
        shl rdx, 12
        add rdx, rax
        cmp rdx, rbx
        je .variant_2
        mov rax, [qword temp_page + MEMORY_BLOCK.next]
        cmp rax, [free_memory_pointer]
        jne @b
        mov rax, rcx
        shl rax, 12
        lea rdx, [rbx + rax]
        mov rax, [free_memory_pointer]
@@:
        push rax
        call temp_mount_page
        pop rax
        cmp rax, rdx
        je .variant_3
        mov rax, [qword temp_page + MEMORY_BLOCK.next]
        cmp rax, [free_memory_pointer]
        jne @b
.variant_1: ; Наш блок не соседствует c другими
        mov rax, [free_memory_pointer]
        call temp_mount_page
        mov rax, rbx
        xchg [temp_page + MEMORY_BLOCK.prev], rax
        mov rdi, rax
        call temp_mount_page
        mov rax, rbx
        mov [temp_page + MEMORY_BLOCK.next], rax
        call temp_mount_page
        mov rdx, rcx
        mov [temp_page + MEMORY_BLOCK.size], rdx
        mov rdx, [free_memory_pointer]
        mov [temp_page + MEMORY_BLOCK.next], rdx
        mov [temp_page + MEMORY_BLOCK.prev], rdi
.exit:
        pop rdi rdx rcx rbx
        mov rax, TRUE
        ret
.variant_2: ; Наш блок после другого
        push rax
        add [temp_page + MEMORY_BLOCK.size], rcx
        mov rcx, [temp_page + MEMORY_BLOCK.size]
        shl rcx, 12
        add rax, rcx
        mov rdx, rax
        mov rax, [free_memory_pointer]
@@:
        push rax
        call temp_mount_page
        pop rax
        cmp rdx, rax
        je .variant_4
        mov rax, [temp_page + MEMORY_BLOCK.next]
        cmp rax, [free_memory_pointer]
        jne @b
        pop rax
        jmp .exit
.variant_3: ; Наш блок перед другим
        mov rdi, [temp_page + MEMORY_BLOCK.size]
        mov rdx, [temp_page + MEMORY_BLOCK.next]
        mov rax, [temp_page + MEMORY_BLOCK.prev]
        push rax
        call temp_mount_page
        pop rax
        mov [temp_page + MEMORY_BLOCK.next], rdx
        xchg rax, rdx
        call temp_mount_page
        mov [temp_page + MEMORY_BLOCK.prev], rdx
        add rcx, rdi
        jmp .variant_1
.variant_4: ; Наш блок между другими (с первым блоком объединение выполненно)
        mov rdi, [temp_page + MEMORY_BLOCK.size]
        mov rdx, [temp_page + MEMORY_BLOCK.next]
        mov rax, [temp_page + MEMORY_BLOCK.prev]
        push rax
        call temp_mount_page
        pop rax
        mov [temp_page + MEMORY_BLOCK.next], rdx
        xchg rax, rdx
        call temp_mount_page
        mov [temp_page + MEMORY_BLOCK.prev], rdx
        pop rax
        call temp_mount_page
        add [temp_page + MEMORY_BLOCK.size], rdi
        jmp .exit                               

Что можно улучшить? Какой алгоритм стоит использовать в своей системе?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 май 2010, 13:13 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1197
Цитата:
Я не храню данные о выделенных страницах отдельно. Только о свободных. А когда уничтожаю процесс просто просматриваю его каталог страниц и освобождаю всё что ниже 0x7FFFFFFFFFFF (у меня 64 бита. а выше располагается ядро). разумеется я просматриваю таблицы рекурсивно и только те, что присутствуют, поэтому это занимает немного времени. Для общих разделяемых участков памяти я буду создавать информационные структуры, а пока мне это не надо.
Естественно, при освобождении выделенных страниц первичным (а часто и единственным) источником информации о них является таблица страниц. Я использую дополнительные структуры для управления рабочим набором страниц процесса, для быстрого высвобождения транс-страниц (4-кб таблиц страниц) в случае полного высвобождения конечных страниц, транслируемых через эти транс-страницы, для быстрого поиска свободных участков адресного пространства, а также для управления разделяемыми участками.

Цитата:
Что можно улучшить? Какой алгоритм стоит использовать в своей системе?
Будет лучше, если ты действительно опишешь алгоритмы, а не покажешь код. По поводу связных списков я уже высказался, но применительно к 32-разрядной системе (для себя я нашел более эффективное решение), однако в 64-разрядной системе возможно это будет хорошим решением. Битовые карты в чистом виде использовать точно не стоит. В основе этого метода все равно остается последовательный поиск, который нужно выполнять уж в слишком большой битовой карте. Скорее всего самым оптимальным будет какой-нибудь комбинированный вариант. Какой именно, пока сказать не могу, т.к. опыта разработки 64-разрядной системы у меня нет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 17 май 2010, 11:35 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1197
Код:
alloc_phis_pages:
   cmp [phis_memory_mutex], FALSE
   jne alloc_phis_pages
   mov [phis_memory_mutex], TRUE
   ...

Я конечно извиняюсь, но разве так делают? Если функция вытесняема или может выполняться на другом ядре, то лучше сделать так.
Код:
alloc_phis_pages:
   mov al, TRUE
   xchg al, [phis_memory_mutex]
   and al, al ; cmp al, FALSE
   jnz alloc_phis_pages ; +2
   ...

А еще лучше "быстрые" системные функции делать невытесняемыми и применять блокировки только для многоядерных систем.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 17 май 2010, 15:30 

Зарегистрирован: 16 фев 2010, 22:03
Сообщения: 101
Цитата:
alloc_phis_pages:
mov al, TRUE
xchg al, [phis_memory_mutex]
and al, al ; cmp al, FALSE
jnz alloc_phis_pages ; +2
...

Спасибо. Так действительно будет лучше. Тем более в далёком-далёком будущем я планирую сделать поддержку многоядерности.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 01 апр 2011, 14:49 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 945
Откуда: Дагоба
Вообще-то, так тоже не делают. Хотя исторически команда XCHG применяется в качестве атомарной на самых разных архитектурах, у i86 есть специальные атомарные инструкции, эффективно осуществляющие и проверку и модификацию - BTR (bit test and reverse), BTS (bit test and set) и BTC (bit test and clear). Это раз. А кроме того, несмотря на замечание про многоядерность, такой код всё равно опасен. Нужно использовать префикс LOCK для запрета доступа по шине другим процессорам на время исполнения команды и записи в память мимо кэша. Это два.
Например, так:
Код:
.1:     lock bts byte [si], 0 ; Проверка и установка бита 0
        jc .1 ; Повторить процедуру, если бит был установлен ранее

Кроме того, надо тщательно следить за тем, чтобы этот код везде выполнялся только с разрешёнными прерываниями или, наоборот, с запрещёнными. В однопроцессорной системе нельзя допускать, чтобы в одном месте прерывания были запрещены, в другом разрешены. Иначе чрезвычайно редко система будет виснуть мёртвым колом. И хрен найдёшь, откуда растут зависоны.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 01 апр 2011, 15:43 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1346
Откуда: Зеленоград
Насколько помню, BTC и прочие не являются сами по себе атомарными и требуют указания префикса LOCK, и лишь XCHG является атомарной и при его отсутствии.

Что же касается прерываний (да и вообще внутриядерной синхронизации), надо это дело тщательно продумать, задокументировать, а в дальнейшем -- неукоснительно следовать. В Винде отнюдь не на пустом месте возникли требования о выполнении того или иного кода на определённых уровнях IRQL. Правда, сама система уровней там переусложнена, но это уже другой вопрос.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 01 апр 2011, 15:54 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 945
Откуда: Дагоба
Да, действительно, от природы атомарные операции только CMPXCHG/CMPXCHG8B/CMPXCHG16B и XCHG.
Но с BTx код проще и понятней.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 01 апр 2011, 16:10 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1346
Откуда: Зеленоград
Бывают случаи, когда выгодней именно обмен или сравнение с обменом, но это довольно специфично, ну а в качестве обычных семафоров удобней битовые, конечно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 20 июн 2011, 20:48 

Зарегистрирован: 16 фев 2010, 22:03
Сообщения: 101
Теперь уже интересует другой менеджер памяти. Более высокоуровневый.
Есть:
1) Функции монтирования страниц и получения информкации о страницы (физ. адрес и флаги)
2) Функции выеления освобождения физических страниц
Надо:
1) Выделение память блоками меньше размера страницы (типа malloc), при этом не просто округление до 4 КБ.
2) Выделение памяти по конкретному адресу.
3) Монтирование физических страниц.
4) Возможность не очень сложной работы с кучами из каталогов страниц других процессов.
5) Поддержка многозадачности.
Пробовал различные варианты, но никак не могу придумать что-то нормально. Можете подкинуть идеи?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3, 4  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB