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

Debugging and my story

I thought is write a blot post about myself and how I started debugging as I haven’t posted in a long time, the reason is I’m actually on holiday in Greece so I can’t write much about debugging as I don’t have access to my computer.

So here’s my story on how I got to where I am today…
Before time began… Wait, that’s not right.
Okay, I first got my own computer in March 2013 from a local computer shop, I saved up from Xmas and birthday money, my parents didn’t agree getting my own computer was a good idea but I insisted so I went to this shop and poured out a sum of £590 to pay for a gaming computer.
At the time I knew nothing, literally… I mean nothing about computers, I just wanted to play better games than what was on my Xbox at the time.
So here I carried it upstairs (my Uncle fetched the computer in his car for me at the time) into my bedroom, here comes the phone call of my mum ringing up and to her disbelief I told her I bought a computer.
She came home and to no surprise wasn’t happy at all, we had no where to put it at all, eventually she decided to move everything around to put a desk in.
Here’s where the irony comes in, she said it was a bad idea to buy the computer and especially from this local shop, so here I was setting it up, buying a few games on Steam, starting playing the games and… (You guessed it) blue screen!
Oh no, what am I going to do?
Panic, panic…
I eventually ring the shop and say this has happened, so I took it down to the shop, he looked at it and told me to come back in a few days, I came back and it ran fine until it happened again.
I remember him saying it was a driver issue and I’m installing something that’s causing problems, funny how he never told me what it was.
This is the point where I decided to go online and see if I can find any solutions, all gibberish as I knew nothing of computing.
That’s when I stumbled upon http://www.sevenforums.com
I asked for help and I got all these solutions that wouldn’t work, from somebody called Arc, I then contacted somebody else called X Blue Robot to help me which happens to be a good friend now over at http://www.sysnative.com
Anyway, the problems still persisted so joined another forum which was http://www.windowsforum.com and made a thread, Vir Gnarus and two others helped me and it was appearing to be a hardware failure, especially given it was a 0x124, (discussed in another post).
I still couldn’t fix the problem, I got numerous errors to the point where I contacted the supplier where the local shop got the computers from. They told me to send it to them free of charge, they contacted me days after and said they couldn’t replicate the issue but replaced the PSU and GPU as the GPU had a loose bearing as wasn’t actually supplied with the computer, the local shop bought that seperate so the 450w PSU couldn’t really handle it so that was replaced to an el cheapo 750w Ace switching PSU which can be bought from around £10, that’s good…
I gave up and changed what software I could as the supplier still couldn’t find any problems.
I started then posting BSOD instructions over at http://www.sevenforums.com to help some BSOD analysts.
I got a few thanks, I then installed the Windows Debugger to take a look at some files, still gibberish, no luck in finding useful commands on my own, thanks to some of x BlueRobot’s posts (Harry Miller) I managed to use some commands to find simply BSOD cases.
I then started learning basics and reading blog posts by Harry on learning debugging. Afterwards I bought Windows Internals and read a bit of that.
Without causing more wars I got into a large disagreement over at sevenforums.com and got banned, after already having an account on Sysnative about freezing I decided to take my knowledge over there.
Shorty after I made friends with two fellow BSOD analysts Patrick Barker and John Griffith.
I’ve been there ever since at my new online home, I then joined http://www.techsupportforum.com and helped people out there (which I still do).
And now here I am (in Greece) helping people out with BSODs and hopefully starting a Computer Science degree at Sheffield Hallam University this time next year.
Oh and over at http://www.windowsforum.com Vir Gnarus who is now a good friend but he recently switched to IT Infrastructure as apposed to debugging but I’m hoping he’ll return soon.
I’m undecided in what to do as a career at the moment but an Escalation Engineer at Microsoft looks like a very interesting job.
So that’s my story so far, debugging is very interesting and so hard to believe that if I hadn’t had bought that specific computer I wouldn’t be here today.