Doubly linked lists

In this article I will talk about linked lists, specifically doubly linked list.

Linked lists are a sequential list data structure, that allows memory locations to be ‘linked’ together in a sequence, across an entire memory address space.

Windows was designed as a fast, reliable operating system, which meant support from sequential memory allocations, rather than just simple array data structures, was necessary. Bear in mind, that in the low level operations of Kernel execution, everything must be completed in a timely manner. Adding and removing values from arrays would prove very difficult, in the sense that shifting all entries in front of , or behind the target location, would prove to be a very costly process.

A linked list acts like a table, with data, and links. The data stores the necessary value, and the links provide the forward (or backward, in doubly linked lists) pointer to the subsequent entry.
Every linked list has a list head entry, which contains two entries, flink and blink. Pointing to the first, and last entries in the list. In the following image, you can see the parsed data structure of linked lists in Windbg.

Capture3

You can also see the ActiveProcessLinks entry in the EPROCESS data structure. This contains the linked list of all EPROCESS data structure instances running on the system, each process has their own instance.

Capture2

Finally, driver developers can use the Windows API to aid in driver development. Two API functions InsertHeadList and InsertTailList add the appropriate data entries at the start or end of the list. However, you might be wondering: What if I want to insert an entry into the middle of the list? Well you can, all that happens is a temporary variable is set up to hold the contents of the flink, or blink list head entry, then swapping of specific entries to move the flink and blink pointers, in order to inset the new entry into the middle.

You can pass the values of entry two, into the new entry, three. Thus adding a new entry into the middle.

So now we’ve looked at how entries are added, the removal is a very similar process, which simply involves changing the flink and blink values of the entries before and after the target, to prevent pointers dereferencing null, or freed memory addresses.

Lets look at a real example using Windbg.

dl

You might be thinking, well this is simply a block full of addresses. Well you wouldn’t be wrong. But I’ll state what they are.
The first column is the address of that entry. The second column is the flink pointer, and the second column is the blink point.
Notice anything strange?
The second row, and fourth row aren’t in use, and thus are invalid. Referencing them would result in a bugcheck.
They’re in the process of removal, as the address is still part of the list, but they aren’t being referenced. Notice how the flink and blinks of the entries before and after skip the address?

Finally, I thought it would be a good idea to show an example of how useful linked lists can be.

timer

This command shows various fields of information for timers which have made changes to the timer resolution on the system.
All of which is very useful in keeping track of which process has altered the timer resolution. It allows the system to identify which processes still have to restore the timer resolution, acting as a safety mechanism to prevent issues with thread execution later on.
Discussing timer processing is beyond the scope of this blog post, so I will not go into detail as to how Windows performs these operations. For more information on this see Windows Internals Part 1, Chapter 3, System Mechanisms

Sources
https://www.osronline.com/article.cfm?article=499

http://blogs.msdn.com/b/ntdebugging/archive/2009/05/29/reversing-in-reverse-linked-list-pool-corruption-a-complete-walkthrough.aspx

https://msdn.microsoft.com/en-us/library/windows/hardware/ff563802%28v=vs.85%29.aspx?f=255&MSPPError=-2147217396

https://msdn.microsoft.com/en-us/library/windows/hardware/ff554296%28v=vs.85%29.aspx?f=255&MSPPError=-2147217396

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s