Драйверы режима ядра: Часть 7: Работа с памятью. Использование ассоциативных списков — Архив WASM.RU

Все статьи

Драйверы режима ядра: Часть 7: Работа с памятью. Использование ассоциативных списков — Архив WASM.RU



7.1 Ассоциативные списки

Диспетчер куч (heap manager) управляет кучами, как системными, так и пользовательскими, разбивая пространство кучи на блоки и организуя списки блоков одинакового размера. Если приходит запрос на выделение блока памяти из кучи, то диспетчер куч пытается подобрать свободный блок подходящего размера. На это, естественно, требуется какое-то время. Если же заранее известно, что потребуются блоки памяти фиксированного размера, но количество этих блоков и частота их использования не известны, то следует использовать, по соображениям лучшей производительности, так называемые ассоциативные списки (look-aside lists), которые существуют только в ядре. Главное отличие ассоциативных списков от пулов в том, что из ассоциативных списков можно выделять блоки памяти только фиксированного и заранее определенного размера, а из пулов любого, причем память из ассоциативных списков выделяется быстрее, так как нет необходимости подбирать подходящую область свободной памяти.

Если Вам когда-либо придется работать с ассоциативным списком, то первой же проблемой, которую придется решить, кроме, конечно, создания самого ассоциативного списка, будет проблема управления блоками памяти, которые Вы из этого ассоциативного списка будете выделять. В частности, где и как хранить адреса блоков - ведь к ним надо обращаться, а потом еще и освобождать. Поскольку количество этих блоков заранее не известно, то проблема достаточно серьезная. Для решения подобных задач существуют особые конструкции. Всего таких конструкций три:

  • Односвязный список (singly linked list);
  • S-список (S-list, sequenced singly-linked list.), являющийся развитием односвязного списка;
  • Двусвязный список (doubly linked list).

Мы рассмотрим только двусвязный список, как наиболее универсальный.

Код, представленный в этой статье довольно прост, но может показаться очень сложным, если Вы впервые сталкиваетесь с такими понятиями как ассоциативный и двусвязный списки.

Хотя обе эти конструкции называются списками, по сути, это совершенно разные вещи. Перевод английского термина look-aside list на русский язык крайне абстрактен и плохо отражает суть. Look-aside дословно можно перевести как: "смотреть по сторонам". Смысл с том, что look-aside list представляет собой набор или список заранее выделенных системой блоков памяти. В каждый момент времени какие-то блоки могут быть свободны, а какие-то заняты. При запросе на выделение очередного блока задача системы пройти по списку ("посмотреть по сторонам ") и найти близлежащий свободный блок. В русском же переводе, look-aside превращается в "ассоциативный", и становится совершенно непонятно, что с чем здесь ассоциируется. Тем не менее, перевод этот устоявшийся - хочешь, не хочешь, придется применять. Т.о. ассоциативный список - это фактически особая системная куча, работающая по определенным правилам.

Двусвязный же список - это просто форма организации данных. С помощью двусвязных списков удобно связывать друг с другом однородные структуры данных и иметь возможность перебирать их в любом направлении. Возможно, Вам и удастся избежать использования ассоциативных списков, но пройти мимо двусвязного списка трудно. Двусвязные списки очень интенсивно используются самой системой для организации внутренних структур.



7.2 Исходный текст драйвера LookasideList

Сколько я не думал, мне так и не удалось изобразить что-то осмысленное и в то же время простое. Поэтому, этот драйвер будет делать достаточно бессмысленные манипуляции. Однако, это не должно помешать понять принципы работы с ассоциативным и двусвязным списками.

Программы управления драйвером не будет. Используйте KmdManager (входит в пакет KmdKit) или аналогичную утилиту, а отладочные сообщения, выдаваемые драйвером, контролируйте с помощью утилиты DebugView (http://www.sysinternals.com) или консоли SoftICE.


 ;@echo off
 ;goto make

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;
 ;  LookasideList - Пример использования и управления ассоциативным списком.
 ;
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 .486
 .model flat, stdcall
 option casemap:none

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                              В К Л Ю Ч А Е М Ы Е    Ф А Й Л Ы
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 include \masm32\include\w2k\ntstatus.inc
 include \masm32\include\w2k\ntddk.inc
 include \masm32\include\w2k\ntoskrnl.inc

 includelib \masm32\lib\w2k\ntoskrnl.lib

 include \masm32\Macros\Strings.mac

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                                       С Т Р У К Т У Р Ы                                           
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 SOME_STRUCTURE STRUCT
     SomeField1    DWORD        ?
     SomeField2    DWORD        ?
     ; . . .                          ; Любое кол-во дополнительно необходимых членов

     ListEntry    LIST_ENTRY    <>    ; Двусвязный список для управления структурами
                                      ; Зтот член удобнее располагать первым в структуре,
                                      ; но здесь используется более общее решение

     ; . . .                          ; Любое кол-во дополнительно необходимых членов
     SomeFieldX    DWORD        ?
 SOME_STRUCTURE ENDS

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                       И Н И Ц И А Л И З И Р О В А Н Н Ы Е    Д А Н Н Ы Е
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 .data?

 g_pPagedLookasideList    PPAGED_LOOKASIDE_LIST    ?
 g_ListHead               LIST_ENTRY               <>
 g_dwIndex                DWORD                    ?

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                                           К О Д                                                   
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 .code

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                                         AddEntry                                                  
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 AddEntry proc uses esi

     invoke ExAllocateFromPagedLookasideList, g_pPagedLookasideList
     .if eax != NULL
         mov esi, eax

         invoke DbgPrint, \
                $CTA0("LookasideList: + Memory block allocated from lookaside list at address %08X\n"), esi

         invoke memset, esi, 0, sizeof SOME_STRUCTURE

         assume esi:ptr SOME_STRUCTURE

         lea eax, g_ListHead
         lea ecx, [esi].ListEntry
         InsertHeadList eax, ecx

         inc g_dwIndex
         mov eax, g_dwIndex
         mov [esi].SomeField1, eax

         invoke DbgPrint, $CTA0("LookasideList: + Entry #%d added\n"), [esi].SomeField1

         assume esi:nothing

     .else
         invoke DbgPrint, $CTA0("LookasideList: Very bad. Couldn't allocate from lookaside list\n")
     .endif

     ret

 AddEntry endp

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                                       RemoveEntry                                                 
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 RemoveEntry proc uses esi

     IsListEmpty addr g_ListHead
     .if eax != TRUE

         lea eax, g_ListHead
         RemoveHeadList eax
         sub eax, SOME_STRUCTURE.ListEntry
         mov esi, eax

         invoke DbgPrint, $CTA0("LookasideList: - Entry #%d removed\n"), \
                             (SOME_STRUCTURE PTR [esi]).SomeField1

         invoke ExFreeToPagedLookasideList, g_pPagedLookasideList, esi

         invoke DbgPrint, \
             $CTA0("LookasideList: - Memory block at address %08X returned to lookaside list\n"), esi
     .else
         invoke DbgPrint, \
             $CTA0("LookasideList: An attempt was made to remove entry from empty lookaside list\n")
     .endif

     ret

 RemoveEntry endp

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                                       DriverEntry                                                 
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 DriverEntry proc uses ebx pDriverObject:PDRIVER_OBJECT, pusRegistryPath:PUNICODE_STRING

     invoke DbgPrint, $CTA0("\nLookasideList: Entering DriverEntry\n")

     invoke ExAllocatePool, NonPagedPool, sizeof PAGED_LOOKASIDE_LIST
     .if eax != NULL

         mov g_pPagedLookasideList, eax
        
         invoke DbgPrint, \
         $CTA0("LookasideList: Nonpaged memory for lookaside list allocated at address %08X\n"), \
         g_pPagedLookasideList

         invoke ExInitializePagedLookasideList, g_pPagedLookasideList, NULL, NULL, \
                                                0, sizeof SOME_STRUCTURE, ' msaW', 0

         invoke DbgPrint, $CTA0("LookasideList: Lookaside list initialized\n")

         lea eax, g_ListHead
         InitializeListHead eax

         invoke DbgPrint, $CTA0("LookasideList: Doubly linked list head initialized\n")

         invoke DbgPrint, $CTA0("\nLookasideList: Start to allocate/free from/to lookaside list\n")

         and g_dwIndex, 0

         xor ebx, ebx
         .while ebx < 5

             invoke AddEntry
             invoke AddEntry

             invoke RemoveEntry

             inc ebx
         .endw

         invoke DbgPrint, $CTA0("\nLookasideList: Free the rest to lookaside list\n")

         .while TRUE

             invoke RemoveEntry

             lea eax, g_ListHead
             IsListEmpty eax
             .if eax == TRUE
                 invoke DbgPrint, $CTA0("LookasideList: Doubly linked list is empty\n\n")
                 .break
             .endif

         .endw

         invoke ExDeletePagedLookasideList, g_pPagedLookasideList

         invoke DbgPrint, $CTA0("LookasideList: Lookaside list deleted\n")



         invoke ExFreePool, g_pPagedLookasideList

         invoke DbgPrint, \
         $CTA0("LookasideList: Nonpaged memory for lookaside list at address %08X released\n"), \
         g_pPagedLookasideList

     .else
         invoke DbgPrint, \
  		$CTA0("LookasideList: Couldn't allocate nonpaged memory for lookaside list control structure")
     .endif

     invoke DbgPrint, $CTA0("LookasideList: Leaving DriverEntry\n")

     mov eax, STATUS_DEVICE_CONFIGURATION_ERROR
     ret

 DriverEntry endp

 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ;                                                                                                   
 ;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

 end DriverEntry

 :make

 set drv=LookasideList

 \masm32\bin\ml /nologo /c /coff %drv%.bat
 \masm32\bin\link /nologo /driver /base:0x10000 /align:32 /out:%drv%.sys /subsystem:native %drv%.obj

 del %drv%.obj

 echo.
 pause



7.3 Работаем с ассоциативным списком


     invoke ExAllocatePool, NonPagedPool, sizeof PAGED_LOOKASIDE_LIST
     .if eax != NULL

         mov g_pPagedLookasideList, eax

Выделяем неподкачиваемую память для структуры PAGED_LOOKASIDE_LIST, управляющей ассоциативным списком и сохраняем указатель на нее в переменной g_pPagedLookasideList. Обратите внимание на то, что сам ассоциативный список у нас будет подкачиваемым, т.е. память которую мы будем из него получать будет подкачиваемой, об этом говорит имя структуры и имена функций, которые мы используем, но для управляющей структуры память должна быть неподкачиваемой. Об этом явно написано в документации.


         invoke ExInitializePagedLookasideList, g_pPagedLookasideList, NULL, NULL, \
                                                0, sizeof SOME_STRUCTURE, ' msaW', 0

Вызываем функцию ExInitializePagedLookasideList, которая заполняет выделенную на предыдущем этапе структуру PAGED_LOOKASIDE_LIST. Только после этого ассоциативный список готов к использованию.

Обратите внимание на то, что при инициализации ассоциативного списка мы нигде не указываем, сколько всего блоков памяти нам может потребоваться. Откуда же система знает, сколько памяти она должна заблаговременно выделить? Ведь если этого не сделать заранее, то ассоциативный список не будет работать быстрее, чем системный пул. Дело в том, что изначально система выделяет всего несколько блоков, количество которых определяется самой системой. Если теперь мы начнем выделять память из ассоциативного списка, то будут возвращаться указатели именно на эти заранее выделенные блоки. Один раз в секунду система проводит настройку всех ассоциативных списков в системе, вызывая функцию ExAdjustLookasideDepth (В книге Дэвида Соломона и Марка Руссиновича "Внутреннее устройство Microsoft Windows 2000" в соответствующем разделе говорится, что эта функция называется KiAdjustLookasideDepth. Скорее всего это ошибка - такой функции я не нашел - и имелась ввиду ExAdjustLookasideDepth.). Если при настройке ассоциативного списка система увидит, что резерв свободных блоков уменьшился, то выделит новые. Количество вновь выделяемых блоков зависит от нагрузки на ассоциативный список, т.е. от частоты с которой мы выделяем из него память. Система пытается настроить ассоциативный список так, чтобы он работал наиболее эффективно. Если в интервале времени между двумя настройками мы исчерпали лимит заранее выделенных блоков, то система начинает использовать системный пул до следующей настройки, когда она увидит, что резерв равен нулю и выделит необходимый лимит. Здесь важно понять, что если скорость выделения блоков уж слишком велика, то можно и не получить выигрыша в производительности по сравнению с системным пулом. В этом случае придется организовывать собственную кучу. Оценить насколько эффективно работает ассоциативный список можно с помощью команды !lookaside отладчика MS Kernel Debugger либо в ручную, просмотрев с помощью SoftICE дамп структуры PAGED_LOOKASIDE_LIST. Информацию, извлекаемую именно из этой структуры, система использует для выбора стратегии управления ассоциативным списком.


 kd> !lookaside ed374840

 Lookaside "" @ ed374840 "Regm"
     Type     =     0001 PagedPool
     Current Depth  =        2   Max Depth  =        4
     Size           =     1024   Max Alloc  =     4096
     AllocateMisses =        4   FreeMisses =        0
     TotalAllocates =  1319722   TotalFrees =  1319720
     Hit Rate       =       99%  Hit Rate   =      100%

Это пример того, насколько эффективно работает ассоциативный список утилиты RegMon (http://www.sysinternals.com). Как видите, при огромном (более одного миллиона!) количестве операций выделения/освобождения эффективность стремится к 100%. Причина такой высокой эффективность в том, что RegMon не держит долго выделенный блок, а тут же использует и возвращает назад.


         lea eax, g_ListHead
         InitializeListHead eax

Вызовом макроса InitializeListHead, инициализируем голову двусвязного списка. Теперь оба поля структуры LIST_ENTRY содержат указатели на саму эту структуру. Это означает, что двусвязный список пуст (см. рис 7-1, иллюстрация 1).

Рис. 7-1. Этот рисунок позволит нагляднее увидеть работу двусвязного списка.


         and g_dwIndex, 0

Эта глобальная переменная нужна нам только для того, чтобы что-то помещать в выделяемые из ассоциативного списка структуры SOME_STRUCTURE и наблюдать этот процесс через отладочные сообщения.


         xor ebx, ebx
         .while ebx < 5

             invoke AddEntry
             invoke AddEntry

             invoke RemoveEntry

             inc ebx
         .endw

Пять раз прогоняем цикл, который добавляет два элемента и удаляет один. Каждый элемент представляет собой структуру SOME_STRUCTURE. Все выделенные структуры связаны посредством двусвязного списка. Функции AddEntry и RemoveEntry рассмотрим позже.

Этот цикл - имитация процесса, когда блоки памяти выделяются и возвращаются в ассоциативный список в случайном порядке. Т.е. здесь предполагается, что мы каким-то образом работаем с выделяемыми элементами. Например, мы могли бы написать драйвер, который перехватывает вызовы какого-нибудь системного сервиса, скажем ZwOpenKey , и записывает информацию о перехвате в структуру, выделенную из ассоциативного списка.


         .while TRUE

             invoke RemoveEntry

             lea eax, g_ListHead
             IsListEmpty eax
             .if eax == TRUE
                 .break
             .endif

         .endw

Т.к. в предыдущем цикле мы добавляли два элемента, а удаляли один, двусвязный список, а значит и ассоциативный список тоже, содержат сейчас какое-то количество элементов. Мы предполагаем, что эти элементы нам больше не нужны и хотим освободить вся занятую память.

В бесконечном цикле вызываем процедуру RemoveEntry, которая удаляет один элемент. Цикл работает до тех пор, пока двусвязный список не окажется пустым. Макрос IsListEmpty проверяет, пуст ли двусвязный список. Признаком пустоты является ситуация, когда оба поля головы двусвязного списка - структуры LIST_ENTRY - указывают на саму эту структуру, т.е. голова указывает на саму себя. В этот момент мы приходим к тому же состоянию, которое мы имели сразу после вызова макроса InitializeListHead (см. рис 7-1, иллюстрация 1).


         invoke ExDeletePagedLookasideList, g_pPagedLookasideList

Если двусвязный список пуст, то и в ассоциативном списке нет больше элементов, т.к. мы использовали двусвязный список как способ организации выделенных из ассоциативного списка блоков. Теперь мы можем удалить сам ассоциативный список, вызовом функции ExDeletePagedLookasideList. При этом система освобождает выделенную для ассоциативного списка память и прекращает его периодическую настройку.


         invoke ExFreePool, g_pPagedLookasideList

Вызовом функции ExFreePool, освобождаем неподкачиваемую память, занятую под структуру PAGED_LOOKASIDE_LIST. Если перед этим Вы забудете (я этого не забыл) вызвать ExDeletePagedLookasideList, то примерно через секунду увидите BSOD, т.к. система попытается произвести настройку отсутствующего ассоциативного списка.


     mov eax, STATUS_DEVICE_CONFIGURATION_ERROR
     ret

Мы освободили все выделенные нам ресурсы - драйвер можно выгружать.



7.4 Процедура AddEntry

Если нам нужен новый элемент, мы вызываем процедуру AddEntry, которая выделяет новый блок памяти из ассоциативного списка и добавляет его в двусвязный список.


     invoke ExAllocateFromPagedLookasideList, g_pPagedLookasideList
     .if eax != NULL
         mov esi, eax

Вызовом функции ExAllocateFromPagedLookasideList, получаем указатель на новый блок памяти и сохраняем его в регистре esi. Обратите внимание на то, что мы не сообщаем системе размер блока, т.к. этот размер определен ранее в вызове функции ExInitializePagedLookasideList и равен размеру структуры SOME_STRUCTURE.


         invoke memset, esi, 0, sizeof SOME_STRUCTURE

Обнуляем выделенный блок, хотя здесь этого и не требуется.


         assume esi:ptr SOME_STRUCTURE

Теперь мы имеем новый экземпляр структуры SOME_STRUCTURE. Но пока он существует сам по себе. Мы должны "привязать" его к нашему двусвязному списку, который при первом вызове AddEnrty еще пуст.


         lea eax, g_ListHead
         lea ecx, [esi].ListEntry
         InsertHeadList eax, ecx

После первого вызова макроса InsertHeadList мы имеем ситуацию изображенную на рис. 7-1, иллюстрация 2. Обратите внимание на то, что вторым параметром в макрос InsertHeadList мы передаем адрес не самой структуры SOME_STRUCTURE, а адрес её поля ListEntry. Т.е. макрос InsertHeadList получает указатель на две структуры LIST_ENTRY, первая из которых является головой двусвязного списка, а вторая элементом структуры, которую необходимо к этому двусвязному списку привязать. Причем макрос InsertHeadList привязывает новую структуру в голову двусвязного списка (справа, если смотреть на рис 7-1). Можно привязать и в хвост (слева по рисунку), если воспользоваться макросом InsertTailList.

При добавлении первой структуры в двусвязный список оба макроса произведут одинаковый эффект и двусвязный список будет выглядеть так, как изображено на рис 7-1, иллюстрация 2.

Если же двусвязный список не пустой, то макрос InsertHeadList "раздвинет" его между головой и идущей справа от нее структурой и вставит на это место новую структуру. Мы получим ситуацию изображенную на рис 7-1, иллюстрация 3. Если бы мы воспользовались макросом InsertTailList, то он сделал бы то же самое, но с хвоста двусвязного списка (см. рис 7-1, иллюстрация 4).

Надеюсь, здесь всё ясно.


         inc g_dwIndex
         mov eax, g_dwIndex
         mov [esi].SomeField1, eax

Запишем в поле SomeField1, добавленной только что структуры, её порядковый номер. Порядок, в котором структуры добавляются/удаляются можно будет посмотреть в окне DbgView.



7.5 Процедура RemoveEntry

Процедура RemoveEntry диаметрально противоположна AddEntry. Т.е. она отвязывает элемент с головы двусвязного списка и возвращает этот блок памяти в ассоциативный список.


     IsListEmpty addr g_ListHead
     .if eax != TRUE

На всякий случай, проверяем, не пуст ли двусвязный список.


         lea eax, g_ListHead
         RemoveHeadList eax

Отвязываем структуру с головы двусвязного списка (как Вы наверное догадываетесь, макрос RemoveTailList делает это с хвоста. Можно удалить и произвольный элемент макросом RemoveEntryList). В этот момент, извлеченная из двусвязного списка структура, опять начинает существовать сама по себе, а двусвязный список замыкается, чтобы связать оставшиеся элементы.


         sub eax, SOME_STRUCTURE.ListEntry
         mov esi, eax

Обратите внимание на этот момент. Макросы RemoveTailList/RemoveHeadList/RemoveEntryList возвращают указатель на связующий элемент (вложенную структуру LIST_ENTRY) отвязанной структуры, а не указатель на саму отвязанную структуру. Это вполне естественно, ведь эти макросы не знают, в каком месте располагается связующий элемент. И узнать это они никак не могут. Это знаем только мы. Поэтому мы должны вычесть из полученного указателя смещение поля ListEntry в структуре SOME_STRUCTURE и получить указатель на саму структуру (в DDK это делает макрос CONTAINING_RECORD). Вот теперь этот блок памяти можно возвратить в ассоциативный список.


         invoke ExFreeToPagedLookasideList, g_pPagedLookasideList, esi

Передаем функции ExFreeToPagedLookasideList адрес блока, который мы хотим вернуть в ассоциативный список.

Исходный код драйвера в архиве. Для компиляции требуется KmdKit версии не ниже 1.3 - берите на сайте

2002-2013 (c) wasm.ru