Двусвязные списки в драйвере

Тема в разделе "WASM.NT.KERNEL", создана пользователем DoZENT, 12 мар 2007.

Страница 3 из 3
  1. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.552
    Адрес:
    Russia
    Советую почитать Walter Oney 2nd .. ТАМ очень по дробно описано про эти списки . Картинки приведены. Примеры реализации в ядре.

    Я приведу вам код.. но там нет ничего ТАКОГО. (Пс писал по памяти. могут быть ошибки..)
    Так же добавил синхронизацию... (для полного счастья)

    Вначале делаем инициализацию:

    Код (Text):
    1.         g_NPagedLookasideList = (PNPAGED_LOOKASIDE_LIST)ExAllocatePool(NonPagedPool,sizeof(NPAGED_LOOKASIDE_LIST));
    2.         if (NULL==g_NPagedLookasideList)
    3.         {
    4.             DBGPRINT0("Error ExAllocatePool for Lookaside list!");
    5.             return STATUS_MY_ERROR;
    6.         }
    7.         ExInitializeNPagedLookasideList(g_NPagedLookasideList,NULL,NULL,0,sizeof(MEMBLOC_LIST),'ms',0);
    8.         InitializeListHead(&g_ListHead);
    9.  
    10.         DBGPRINT0("init mutex");
    11.         KeInitializeMutex(&g_Mutex, 0);
    Далее есть функция добавления элемента в список:

    Код (Text):
    1. void AddToList(PMDL pBkpMdl, PELEM pElem)
    2. {
    3.     PVOID pResult;
    4.  
    5.     pResult = ExAllocateFromNPagedLookasideList(g_NPagedLookasideList);
    6.     if (pResult!=NULL)
    7.     {
    8.         memset(pResult,0,sizeof(MEMBLOC_LIST));
    9.         KeWaitForMutexObject(&g_Mutex,Executive,KernelMode,FALSE,NULL);
    10.         InsertHeadList(&g_ListHead,&((PMEMBLOC_LIST)pResult)->ListEntry);
    11.         ((PMEMBLOC_LIST)pResult)->pMdlRez = pBkpMdl;
    12.         ((PMEMBLOC_LIST)pResult)->pElemRez = pElem;
    13.         KeReleaseMutex(&g_Mutex,FALSE);
    14.     }
    15.     else
    16.         DBGPRINT0("Error ExAllocateFromNPagedLookasideList() !");
    17.    
    18.     return;
    19. }
    Далее процедура Поиска элемента :

    Код (Text):
    1. PLIST_ENTRY CheckListElem(PELEM pDelElem)
    2. {
    3.     KeWaitForSingleObject(&g_Mutex,Executive,KernelMode,FALSE,NULL);
    4.     PLIST_ENTRY pRezEntry = g_ListHead.Flink, pBkpEntry = &g_ListHead;
    5.     do
    6.     {
    7.         PVOID Entry = CONTAINING_RECORD(pRezEntry,MEMBLOC_LIST,ListEntry);
    8.         DBGPRINT2("ELEM : %x == %x",pDelElem,((PMEMBLOC_LIST)Entry)->pElemRez);
    9.         if (((PMEMBLOC_LIST)Entry)->pElemRez == pDelElem)
    10.         {  
    11.             KeReleaseMutex(&g_Mutex,FALSE);
    12.             return pRezEntry;
    13.         }
    14.         pRezEntry = pRezEntry->Flink;
    15.     }
    16.     while(pRezEntry->Flink!=pBkpEntry);
    17.  
    18.     KeReleaseMutex(&g_Mutex,FALSE);
    19.     return NULL;
    20. }
    Ну и процедура удаления (Очень примитивная - просто удаляет элемент) :

    Код (Text):
    1. VOID RemoveEntry()
    2. {
    3.     if (IsListEmpty(&g_ListHead)!=TRUE)
    4.     {
    5.         KeWaitForMutexObject(&g_Mutex,Executive,KernelMode,FALSE,NULL);
    6.         MmUnlockPages(((PMEMBLOC_LIST)&g_ListHead)->pMdlRez);
    7.         IoFreeMdl (((PMEMBLOC_LIST)&g_ListHead)->pMdlRez);
    8.         ExFreePool(((PMEMBLOC_LIST)&g_ListHead)->pElemRez);
    9.         PLIST_ENTRY pLink = RemoveHeadList(&g_ListHead);
    10.         PVOID Entry = CONTAINING_RECORD(pLink,MEMBLOC_LIST,ListEntry);
    11.         ExFreeToNPagedLookasideList(g_NPagedLookasideList,Entry);
    12.         KeReleaseMutex(&g_Mutex,FALSE);
    13.     }
    14.     else
    15.         DBGPRINT0("List is Empty!");
    16. }
    В общем приблизительно так...
    Народ, код не критиковать - писал с ходу. Структура MEMBLOC_LIST - содержит 2 элемента это когдато выделеный mdl и elem.
     
    TermoSINteZ, 17 мар 2007
    #41
  2. BAY

    BAY New Member

    Публикаций:
    0
    Регистрация:
    3 июл 2006
    Сообщения:
    23
    DoZENT: после ExInitializePagedLookasideList должна ОБЯЗАТЕЛЬНО следовать ExDeletePagedLookasideList!!!!
     
    BAY, 26 мар 2007
    #42
  3. DoZENT

    DoZENT New Member

    Публикаций:
    0
    Регистрация:
    12 мар 2007
    Сообщения:
    50
    TermoSINteZ, так lookaside list можно что ли использовать?? Или все это под двусвязный переписывать надо?
     
    DoZENT, 31 мар 2007
    #43
  4. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.552
    Адрес:
    Russia
    Ну список и так 2х связный - там есть LIST_ENTRY где Flink и Blink.
     
    TermoSINteZ, 31 мар 2007
    #44
  5. DoZENT

    DoZENT New Member

    Публикаций:
    0
    Регистрация:
    12 мар 2007
    Сообщения:
    50
    Просто на первой странице помнится lookaside list забраковали по причине выделения данных только определенного размера. Ну ОК, попробую с ними поработать, если что не получится напишу. В любом случае спасибо.
     
    DoZENT, 31 мар 2007
    #45
  6. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.552
    Адрес:
    Russia
    Ну если вам нужен переменный размер, то тогда надо другие функции использовать. Типа InitializeListHead, InsertTailList,IsListEmpty,RemoveHeadList. В той книге, что я говорил, это все описано.
     
    TermoSINteZ, 31 мар 2007
    #46
  7. DoZENT

    DoZENT New Member

    Публикаций:
    0
    Регистрация:
    12 мар 2007
    Сообщения:
    50
    Сделал точно так же как в примере выше, работает через раз(( Т.е.: приложение ring3 посылает драйверу строку А, он ее принимает, проверяет есть ли такая строка в листе, ее ессно нет, => записывает в лист норамально. Потом посылает точно такую же строку А, в драйвер принимает, проверяет ее наличие, говорит, что такая строка уже есть => в список ее не включает. Затем посылается еще одна строка B, драйвер говорит, что такой еще нет и записывает ее в лист. До этого момента все нормально. Но если после всего этого еще раз послать строку А, то драйвер скажет, что в листе ее нет и добавит!!. При освобождении листа кол-во удаляемых элементов = 3. Почему первый раз функция IsAdded сработала нормально, а второй раз нет?? Кстати, если в этой функции при пробеге всех элементов написать что-то типа DbgPrint ("Item: %S", ((POBJECT_DATA)Entry)->str), то в отладке вылезет Item (null).

    Я тут начал рассматривать такой вариант (откопал на сайте):

    Код (Text):
    1. typedef struct _ProcessList
    2. {
    3.     PVOID NextItem;
    4.     HANDLE Pid;
    5. } TProcessList, *PProcessList;
    6.  
    7. BOOLEAN IsAdded(PProcessList List, HANDLE Pid)
    8. {
    9.     PProcessList Item = List;
    10.     while (Item)
    11.     {
    12.         if (Pid == Item->Pid) return TRUE;
    13.         Item = Item->NextItem;
    14.     }
    15.     return FALSE;
    16. }
    17.  
    18. void DelItem(PProcessList *List, HANDLE Pid)
    19. {
    20.     PProcessList Item = *List;
    21.     PProcessList Prev = NULL;
    22.     while (Item)
    23.     {
    24.         if (Pid == Item->Pid)
    25.         {
    26.                    if (Prev) Prev->NextItem =
    27.                      Item->NextItem; else *List = Item->NextItem;
    28.                    ExFreePool(Item);
    29.                    return;
    30.         }
    31.         Prev = Item;
    32.         Item = Item->NextItem;
    33.     }
    34.     return;
    35. }
    36.  
    37.  
    38. void FreePointers(PProcessList List)
    39. {
    40.     PProcessList Item = List;
    41.     PVOID Mem;
    42.     while (Item)
    43.     {
    44.         Mem = Item;    
    45.         Item = Item->NextItem;
    46.         ExFreePool(Mem);
    47.     }
    48.     return;
    49. }
    50.  
    51.  
    52. void AddItem(PProcessList *List, HANDLE Pid)
    53. {
    54.     PProcessList wNewItem;
    55.     wNewItem = ExAllocatePool(NonPagedPool, sizeof(TProcessList));
    56.     wNewItem->NextItem = *List;
    57.     *List = wNewItem;
    58.     wNewItem->Pid = Pid;
    59.     return;
    60. }
    Как я понял - это односвязный список? Но здесь тип элемента - HANDLE. Насколько корректно данные функции будут работать с PWSTR или с UNICODE_STRING? В самом начале пробовал использовать эти функции, но с ними была такая проблема: когда пробегаешь список элементов первые секунд 5 все ОК, а потом в отладочном окне вместо строки вылезали крякозябры.

    З.Ы. Прошу прощения за столько вопросов)
     
    DoZENT, 5 апр 2007
    #47
  8. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.552
    Адрес:
    Russia
    DoZENT
    Во первых, для двусвязного списка используются структуры типа LIST_ENTRY. То есть ссылка и в перед и назад.

    По поводу твоего IsAdded ничего особого сказать не могу. Проверял алгоритм ваш - работает (проверял не в ядре - но не суть важно). Видимо у вас ошибка с выделением памяти или что-то в том же духе
    А вообще советую вначале все такие вещи проверяйте в юзере, а потом их переводить в ядро.
    Во вторых обязательно проверяйте ExAllocatePool на ошибку.

    По поводу элемента - все будет верно работать если верно выделять память для элементов..
    И следите за указателями

    Вот код ваш проверял в студии (немного изменив):
    Напишу только то что проверял
    Код (Text):
    1. #include <stdio.h>
    2. #include <Windows.h>
    3.  
    4. typedef struct _ProcessList
    5. {
    6.     PVOID NextItem;
    7.     int Pid;
    8. } TProcessList, *PProcessList;
    9.  
    10. BOOLEAN IsAdded(PProcessList List, int Pid)
    11. {
    12.     PProcessList Item = List;
    13.     while (Item)
    14.     {
    15.         if (Pid == Item->Pid) return TRUE;
    16.         Item = (TProcessList*)Item->NextItem;
    17.     }
    18.     return FALSE;
    19. }
    20.  
    21. void AddItem(PProcessList *List, int Pid)
    22. {
    23.     PProcessList wNewItem;
    24.     wNewItem = (TProcessList*)malloc(sizeof(TProcessList));
    25.     wNewItem->NextItem = *List;
    26.     *List = wNewItem;
    27.     wNewItem->Pid = Pid;
    28.     return;
    29. }
    30.  
    31. int main()
    32. {
    33.     TProcessList GList;
    34.     GList.NextItem = 0;
    35.     GList.Pid = 0;
    36.     PProcessList pList = 0;
    37.  
    38.     for (int i = 0; i<=10; i++)
    39.         AddItem((PProcessList*)&GList,i);
    40.  
    41.     pList = &GList;
    42.     for (int i = 0; i<=10; i++)
    43.     {
    44.         printf("Elem pid = %d\n",pList->Pid);
    45.         pList = (PProcessList)pList->NextItem;
    46.     }
    47.     pList = &GList;
    48.     for (int i = 0; i<=10; i++)
    49.         if (IsAdded(&GList,i))
    50.             printf("Elem <%d> is added\n",i);
    51.  
    52.     return 0;
    53. }
    В итоге

    Код (Text):
    1. Elem pid = 0
    2. Elem pid = 10
    3. Elem pid = 9
    4. Elem pid = 8
    5. Elem pid = 7
    6. Elem pid = 6
    7. Elem pid = 5
    8. Elem pid = 4
    9. Elem pid = 3
    10. Elem pid = 2
    11. Elem pid = 1
    12. Elem <0> is added
    13. Elem <1> is added
    14. Elem <2> is added
    15. Elem <3> is added
    16. Elem <4> is added
    17. Elem <5> is added
    18. Elem <6> is added
    19. Elem <7> is added
    20. Elem <8> is added
    21. Elem <9> is added
    22. Elem <10> is added
    23. Press any key to continue
     
    TermoSINteZ, 5 апр 2007
    #48
Страница 3 из 3