1120 Alameda Orquidea, Atibaia, SP,  BRA

fernando@driverentry.com.br

Listas ligadas no DDK

Desde o início dos meus estudos, sempre optei por estudar algo que unisse informática com eletrônica, e isso me levou a escolher o finado curso de Informática Industrial na ETE Jorge Street. Uma excelente escola e aprendi muito por lá. Entretanto só fui aprender o que é lista ligada em um ambiente profissional durante meu estágio. Anos mais tarde, a universidade me apresentou estas listas em forma de classes escritas em Java, onde lidamos com referências e o Garbage Collector. Mesmo quem trabalha com Visual C/C++, lida com classes e templates oferecidas pela MFC, ATL, WTL e STL, que acabam abstraindo a real implementação da lista ligada. Neste post vou falar um pouco sobre os recursos oferecidos pelo DDK em relação a este assunto.

Mas já sou grandinho e sei construir listas ligadas em C/C++. Por que eu deveria utilizar os recursos do DDK?

Se você vai apenas armazenar dados particulares, tais como uma lista de buffers a serem enviados para o dispositivo, então tudo bem, mas para lidar com estruturas do DDK, seria no mínimo interessante saber como elas são armazenadas em listas. Algumas situações exigem que você saiba utilizar as listas do DDK. Um exemplo disso é: Se você implementar o controle personalizado da fila de IRPs do seu driver, o campo pIrp->Tail.Overlay.ListEntry estará livre para ser utilizado enquanto tal IRP é mantida pelo seu driver.

O mais simples destes recursos é a estrutura SINGLE_LIST_ENTRY que é definida no ntdef.h como exibido abaixo:

typedef struct _SINGLE_LIST_ENTRY {
  struct _SINGLE_LIST_ENTRY *Next;
} SINGLE_LIST_ENTRY, *PSINGLE_LIST_ENTRY;

Uma variável do tipo SINGLE_LIST_ENTRY deve ser definida para ser a ponta de nossa lista. Esta variável deveria ter seu membro Next incializado com NULL antes de ser utilizada. As funções PushEntryList e PopEntryList são utilizadas respectivamente para adicionar e remover elementos da ponta da lista. Como a maioria das listas ligadas, os nós são referenciados pelo membro Next até que este seja NULL, indicando assim, o fim da cadeia de nós.

VOID 
  PushEntryList(
    IN PSINGLE_LIST_ENTRY  ListHead,
    IN PSINGLE_LIST_ENTRY  Entry
    );
 
PSINGLE_LIST_ENTRY 
  PopEntryList(
    IN PSINGLE_LIST_ENTRY  ListHead
    );

Mas espere um pouco. Tudo isso é lindo, mas não está faltando nada? Como em qualquer estrutura de lista ligada, entre os membros de cada nó é preciso haver um que aponte para uma estrutura de mesmo tipo, que será o elo para o próximo nó da lista. No exemplo abaixo, o membro pNext é o responsável por isso.

//-f--> Estrutura que define o nó da lista
//      que será utilizada como exemplo
typedef struct _MY_NODE
{
    //-f--> Dados do seu driver definidos
    //      por você.
    UNICODE_STRING      usSomeData;
    ULONG               ulAnotherData;
    struct _MY_NODE     *pNext;
    PVOID               pMoreData;
 
} MY_NODE, *PMY_NODE;

Mas pelo que pudemos ver na estrutura do DDK, não existem membros úteis, ou seja, membros que contenham as informações que nos interessa armazenar, como os campos usSomeData ou pMoreData. Na estrutura oferecida pelo DDK, temos apenas o endereço do nó seguinte.

Qual o interesse em guardar somente os nós?

Na verdade, a estrutura SINGLE_LIST_ENTRY, assim como outras estruturas de listas do DDK, devem ser utilizadas em conjunto com a macro CONTAINING_RECORD. Esta macro nos retorna o endereço base da estrutura que tem um campo conhecido em um endereço conhecido. Bom, eu tentei reescrever esta frase umas três vezes, mas acho que você só irá entender quando ver o exemplo abaixo. Suponha que estamos utilizando o SINGLE_LIST_ENTRY em nosso exemplo anterior. Desta forma teríamos a seguinte estrutura:

//-f--> Estrutura que define o nó da lista
//      que será utilizada como exemplo
typedef struct _MY_NODE
{
    //-f--> Dados do seu driver definidos
    //      por você.
    UNICODE_STRING      usSomeData;
    ULONG               ulAnotherData;
 
    //-f--> Este membro não precisa ser necessariamente
    //      o primeiro ou o ultimo, ele pode estar em
    //      qualquer posição da sua estrutura.
    SINGLE_LIST_ENTRY   Entry;
 
    //-f--> Mais dados
    PVOID               pMoreData;
 
} MY_NODE, *PMY_NODE;

Nossa estrutura é basicamente a mesma, com exceção do membro pNext que agora foi mudado para utilizar a estrutura SINGLE_LIST_ENTRY. Reparem que o campo Entry não precisa estar nem no início e nem no final dos membros da nossa estrutura. O exemplo abaixo demonstra como incluir nós em listas formadas com SINGLE_LIST_ENTRY.

NTSTATUS PrepareDataAndPush(VOID)
{
    PMY_NODE            pMyNode;
 
    //-f--> Aqui obtemos o nó já alocado e com
    //      os campos devidamente preenchidos
    pMyNode = AllocateAndFillNode();
 
    //-f--> Testar nunca é demais
    ASSERT(pMyNode != NULL);
 
    //-f--> Para colocar o nó na lista, é necessário passar
    //      o endereço do membro do tipo SINGLE_LIST_ENTRY
    PushEntryList(&m_ListHead, &pMyNode->Entry);
 
    return STATUS_SUCCESS;
}

Na hora de incluir o nó na lista, devemos passar o endereço do membro do tipo SINGLE_LIST_ENTRY, como sugere o protótipo da função PushEntryList. Acompanhe o exemplo abaixo que demonstra como obter este nó utilizando a função PopEntryList. Esta função retorna o mesmo endereço passado na função PushEntryList, que é um PSINGLE_LIST_ENTRY. A partir deste endereço, conforme eu já havia comentado, podemos obter o endereço base de nossa estrutura utilizando a macro CONTAINING_RECORD. Veja o exemplo abaixo.

NTSTATUS PopAndProcessNode(VOID)
{
    PSINGLE_LIST_ENTRY  pEntry;
    PMY_NODE            pMyNode;
 
    //-f--> Aqui obtemos o nó da lista
    pEntry = PopEntryList(&m_ListHead);
 
    //-f--> Vamos verificar se realmente havia algo
    //      armazenado na lista
    if (!pEntry)
        return STATUS_NO_MORE_ENTRIES;
 
    //-f--> Agora vamos utilizar a macro CONTAINING_RECORD
    //      para obter o endereço base que precisamos
    pMyNode = (PMY_NODE) CONTAINING_RECORD(pEntry, MY_NODE, Entry);
 
    //-f--> Agora temos acesso a toda a estrutura
    ProcessAndFreeNode(pMyNode);
 
    return STATUS_SUCCESS;
}

Este mesmo estilo também é utilizado com a estrutura LIST_ENTRY, que é a estrutura de lista mais utilizada em drivers. Esta estrutura permite criar listas duplamente ligadas, e assim como o SINGLE_LIST_ENTRY, uma variável do tipo LIST_ENTRY é definida para ser a ponta de nossa lista. Sua inicialização é feita utilizando a função InitializeListHead, que inicializa os membros Blink e Flink com o endereço da ponta da lista.

typedef struct _LIST_ENTRY {
  struct _LIST_ENTRY *Flink;
  struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY;

O membro Flink aponta para o nó seguinte, enquanto que o membro Blink aponta para o nó anterior. Diferente da maioria das listas ligadas que conhecemos, suas pontas não são marcadas por NULL nos membros Blink ou Flink. Ao invés disso, suas pontas apontam para o endereço do nó designado como ponta de nossa lista. O exemplo abaixo demonstra como poderiamos varrer este tipo de lista em procura de um certo nó. Antes de realizar qualquer operação com as listas formadas por LIST_ENTRY, utilizamos a função IsListEmpty.

//-f--> Procura por um nó através de uma lista
//      formada por estruturas LIST_ENTRY
BOOLEAN SearchEntry(PUNICODE_STRING  pusLookFor)
{
    PLIST_ENTRY pEntry;
    PMY_NODE    pMyNode;
 
    //-f--> Antes de qualquer operação, é necessário
    //      verificar se existem nós na lista. Caso
    if (IsListEmpty(&m_ListHead))
        return FALSE;
 
    //-f--> Obtem o endereço do primeiro nó
    pEntry = m_ListHead.Flink;
 
    //-f--> Enquando pEntry não apontar para a ponta
    //      da lista, significa que ainda existem nós
    while(pEntry != &m_ListHead)
    {
        //-f--> Obtem o endereço base da estrutura
        pMyNode = (PMY_NODE) CONTAINING_RECORD(pEntry, MY_NODE, Entry);
 
        //-f--> Verifica se é o nó que estamos procurando
        if (RtlEqualUnicodeString(pusLookFor,
                                  &pMyNode->usSomeData,
                                  TRUE))
        {
            //-f--> Retorna TRUE sinalizando que o nó foi encontrado
            return TRUE;
        }
 
        //-f--> Obtem o endereço do próximo nó
        pEntry = pEntry->Flink;
    }
 
    //-f--> Se chegamos aqui, significa que não encontramos
    //      o nó desejado.
    return FALSE;
}

NOTA: O exemplo acima serve apenas para ilustrar a busca por um nó. Para implementar uma busca como essa em um ambiente de produção, é necessário ter em mente questões de sincronismo de acesso por multiplas threads e controle de referências.

Para manipular listas formadas com LIST_ENTRY são utilizadas as funções InsertHeadList, InsertTailList, RemoveHeadList e por aí vai. Não vou listar todas as funções aqui, tenho certeza que a referência do DDK faz isso melhor que eu.

Para ambos os tipos de listas, existem as funções ExInterlockedXxxList que recebem um Spin Lock a fim de sincronizar as alterações da lista. Lembre-se que caso você sincronize o acesso às listas utilizando Spin Locks, todos os nós devem residir em memória não paginada. Como alguns de vocês já devem saber, ao adquirir um Spin Lock, a IRQL da thread vai para DISPATCH_LEVEL. Nesta IRQL, o Memory Manager é incapaz de recuperar uma página de dados que foi paginada para disco, resultando em um BugCheck.

É importante lembrar também que não se deve misturar os uso das funções ExInterlockedXxxList com as não sincronizadas. Se uma lista é acessada por várias threads, todos os acessos à mesma devem ser controlados.

typedef struct _SLIST_ENTRY {
  struct _SLIST_ENTRY *Next;
} SLIST_ENTRY, *PSLIST_ENTRY;

A estrutura SLIST_ENTRY é uma alternativa para as listas do tipo SINGLE_LIST_ENTRY com acesso sincronizado. Esta versão se propôe ser mais eficiente utilizando as funções ExInterlockedPopEntryList e ExInterlockedPushEntryList. Diferente das outras estruturas aqui apresentadas, a ponta da lista é formada por uma estrutura diferente da estrutura utilizada nos nós, Esta estrutura é a SLIST_HEADER, que é uma estrutura opaca e que deve ser inicializada pela função ExInitializeSListHead.

Um outro diferencial deste tipo de lista é que o DDK oferece a função ExQueryDepthSList que retorna a quantidade de nós armazenados na lista.

Se o seu principal problema é performance, então o ideal seria utilizar o grupo de funções que trabalham com as Generic Tables. A ponta da lista é definida por uma estrutura opaca chamada RTL_GENERIC_TABLE. Esta estrutura juntamente com as funções de manipulação, tais como RtlGetElementGenericTable, criam arvores binárias com auto balanceamento. Que chique hein?

Mas Generic Tables é um assunto a parte e que merece um post dedicado. Até a próxima!

6 Responses

  1. Cara, você que escreve sobre isso meu me fascina esse tipo de programação avançada, poxa eu mexo com c/c++ e tenho até um nivel intermediário no assunto, mas eu não consigo compreender muito bem o device-driver programação, por que eu não tenho a base de onde começar, por exemplo lista ligado eu sei que é muito útil, mas será que você não poderia passar um exemplo real tipo um uso onde seria imprescidivel utilizar de linkedlist? .. claro em relação a driver.

    Abraços

    PS: Foi o Rodrigo Strauss que me indicou esse excelente blog, fico muito agradecido a ele também 😉

    Ricardo Silva
    []s.

    1. Olá Ricardo,

      Bom, descrever como listas ligadas poderiam ser utilizadas em drivers seria como descrever como laços de repetição poderiam ser utilizadas em drivers. Ou seja, é uma operação muito básica para se ter uma aplicação pré-definida. Mas se isso lhe servir de resposta…

      No final do ano passado, eu tive que desenvolver em uma espécie de personal firewall que avaliava os domínios nos quais o usuário estava navegando. Cada domínio deveria ter sua autorização em uma base de dados, que era verificada por uma aplicação nossa, mas caso não houvesse essa autorização, uma pergunta era lançada ao usuário. Como poderiam haver mais de uma requisição de página ao mesmo tempo, mesmo porque, mais de um browser poderia estar sendo utilizado ao mesmo tempo. As IRPs referentes aos GETs do HTTP eram enfilados em listas ligadas a fim de aguardar suas respectivas autorizações.

      Neste caso as listas ligadas poderiam ser substituídas por arrays. A lista na verdade é uma alternativa de desenvolvimento, da mesma forma que o desenvolvedor pode escolher entre usar o “for” ou o “while” em seu laço de repetição.

      Espero ter ajudado,
      []s.

  2. Cara entendi perfeitamente, muito obrigado por sua explicação, estou seguindo mesmo muito jovem ainda no que eu acredito ser o mais avançado, estou cursando bacharel em Ciências da Computação, e já tenho uma boa base em C/C++, para entender essas loucuras pelo menos parte delas, e eu gostaria muito de entrar no segmento de desenvolvimento kernel especificamente para Windows, e vejo que seu blog vai ser de muita, mais muita ajuda mesmo para min, agradeço pela resposta.

    Abraços

    Ricardo Silva
    []s.

  3. Fernando,

    além de um grande amigo, você é um dos caras que mais manjam do assunto de device drivers. Eu, que já me aventurei por esses caminhos e entendo um pouco das dificuldades desse tipo de desenvolvimento. Às vezes é a falta de documentação, a necessidade de compreender as mudanças no sistema operacional, as particularidades do sistema de arquivos, etc…
    Você tem feito um grande trabalho escrevendo esse blog popularizando o desenvolvimento de driver e até desmistificando um pouco esse tipo de desenvolvimento.

    Meu amigo, espero que você tenha muito sucesso com esse blog e terá, porque profissionalmente você é uma das pessoas mais competentes e capacitadas que já conheci.

    Um grande abraço,

    Heldai

    1. Oloco seu Hêldai,

      Olha só quem está falando. O cara é o maior dos cientista loco e seu trabalho é tornar os mais diversos projetos em realidade. Parabéns pela sua competência, um dia eu chego lá. Até lá, vou aprendendo com o senhor.

      Valeu pela força e toda a confiança depositada em mim.

      []s,
      Fernando.

      PS: Não esquenta que depois eu acerto aquele cachê lá.

Leave a Reply

Your email address will not be published.