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!
Leave a Reply