Linked Lists - Flink and Blink

Okay, linked lists are used often in Windows and are usually part of larger data structures. They are typically seen with the Windows Debugger (WinDbg) with the name of _LIST_ENTRY. This indicates a linked list data structure, or more specifically the list head of a linked list which contains information such as the Flink and Blink pointers. 

Here is some example output using WinDbg:

The data types being used here are 32-bit pointers, which is defined as follows:

This is stored in the BaseTsd.h header file.

For non-programmers or those who are simply interested, the #define preprocessor statement is used to substitute a identifier for something which shorter or easier to read.

Here's a very simple example which I wrote myself:

Getting back to the point, I started a discussion a while ago about Flink and Blink addresses, and what they meant on Sysnative - Understanding Flink and Blink Free-Lists (Stop 0x19)

If you ever see, the parameters of the Flink and Blink Free List, and the pool freelist being corrupt, then this usually because the linked list isn't valid anymore and doesn't point to the addresses it's supposed to. The pool allocation should be free and available to use by device drivers, but validation of the linked list indicates that that pool allocation isn't free, as a result of some buffer overrun or underrun.

The pool freelist is group of free pool allocations linked together in a chain.

In concept, a doubly linked list is shown as this:

We can view doubly linked lists with the !dflink and !dblink extensions, along with the use of the dt -l command. We can also use the !list extension.

Windows knows if a linked list is empty, since the FLINK pointer will point to the List Head address. The IsListEmpty API can be used with this, and return a Boolean value, therefore if the list is empty, it will return true. Boolean expressions are either true or false.

Windows and device drivers can add entries of data to the linked list, by using the InsertHeadList and InsertTailList API. The name of the routine is quite self explanatory, InsertHeadList adds an entry to the beginning of the linked list, whereas, InsertTailList does the opposite. In terms of code, the routine would be written as so:

The routine takes two parameters, which are both pointers; ListHead is a pointer to the List Head of the linked list and Entry is a pointer to the entry of the linked list which is going to be inserted. The routine is void and does not return anything. The same API can used to insert entries into middle of linked lists, since the previous entry will be used as a list head.

More Information - Kernel-Mode Basics: Linked Lists

 We have briefly discussed the API used with Linked Lists, and shown where Linked Lists are present in data structures formatted by WinDbg. Stop 0x19s are a common example of linked lists being corrupted; ensure you check the parameters first.

I would like to finally add, that arrays and linked lists have similar purposes of storing similar data which is easily accessible, although, arrays and linked lists are data structures which should be chosen for the appropriate task. A good discussion about the differences between linked lists and arrays is on Stack Overflow.

If you interested, you can learn or see how a linked list works in programming by reading this article on CodeProject.

Here is another simple program which demonstrates the use of a pointer to access a element of a array, and then print the address of that element to the user.

A character pointer named p is created, as well as, a empty character array of 50 elements called string. We then assign the pointer, the value and address of the first array element. The program then prints the memory address of the first element to the screen.