Windows Process IDs - Where do they come from?

[Polynomial]

This is something I wrote up for EvilZone a few weeks back, figured I'd share it here.

How do Windows process IDs get allocated, and what do they represent in the kernel itself?
This question had been bugging me for a month or two until a couple of days ago when I tackled the problem head on and found out the answer. I had sat looking at my task manager and noticed that whilst new processes IDs were usually larger than old ones, the amount they increased was non-uniform and sometimes they did make backward leaps. So, what internal mechanism is used to allocate new pIDs and tIDs in Windows, and what do process IDs really mean in the context of the kernel?

First I tried asking a few people in the know about this kind of thing. My first port of call was Dark_Byte, the creator of Cheat Engine. I talk to him online on a regular basis and he's pretty much an encyclopedia of low level programming. Unfortunately the problem stumped him, too, since he'd never really looked into it. He also posed some questions of his own and made the point that even after a process exits you can query its exit status via its process ID, so the IDs must remain cached somewhere and there must be some protocol as to when they can be disposed of or re-used. During our conversation I also suggested that process and thread IDs may actually come from the same pool, hence the seemingly non-uniform process IDs.

I then asked Mark Russinovich (the Microsoft Sysinternals guy who wrote the Windows Internals book) who explained that pIDs and tIDs are simply indices in certain object tables in the kernel, but couldn't go into the details. Damn the limitations of working for Microsoft! On a side note, it was REALLY cool to actually get a response from him, since he's practically my idol.

Since asking people didn't really give me a decent answer, I had to go my own route. After reading the leaked NT4 kernel source code (you should be able to find this on ThePirateBay), doing a little reversing on Win7 and a few hours playing with my results in WinDbg I can confidently say that I know the flow of how pIDs and tIDs are created.

The kernel needs to be able to generate a sequence of process and thread IDs that are unique across the whole system. To efficiently and safely do this, the kernel creates a pool of IDs that can be used for both processes and threads. This pool is exported in the kernel as a HANDLE_TABLE object called PspCidTable. During Phase0 startup of the system, the PspInitPhase0 function is called. This function creates a HANDLE_TABLE object using ExCreateHandleTable, which automatically populates the table with 65536 entires. Each entry is a 16-bit unsigned integer (at least it is on a 32-bit OS) stored inside a list item object that is part of a doubly linked list. Both process and thread IDs come from the PspCidTable pool.

When a new ID is needed one can be gained using ExCreateHandle, which removes a handle from the PspCidTable pool and makes it active. The bulk of ExCreateHandle's code is inside a critical region (i.e. code that can only execute on one processor at a time) therefore preventing duplicate handles from being fetched from the pool. The logic for disposal of these IDs is somewhat obscure, and seems to be somewhat like a garbage collector. When no handles in object handle tables reference the process ID, all references to it are disposed of and it can be dropped or re-used. The locations in the kernel referencing the PspCidTable are numerous, so it's difficult to pin down exactly how it's done. However, what I do know is that if the PspCidTable reaches a critically low level (i.e. there are very few remaining usable pIDs) it automatically expands to fill with unused IDs that were disposed of previously.

The difference between how NT4 pools these handles and how NT6.1 (Win7) does it is surprisingly negligable. Most of the changes are related to other operations in Windows such as how the enhanced security tokens needed by UAC get mapped to processes and threads.

If you're interested in taking a look yourself, grab the NT4 kernel source and take a look at nt4\private\ntos\ps\create.c and nt4\private\ntos\ex\handle.c

[maboroshi]

Very cool, I love reading about the windows low level internals and I think I am going to learn C maybe some assembly to get a better grasp on it

But I digress, very cool

[Polynomial]

Glad you enjoyed the read. It's part of a series I'm doing called "Stuff you (probably) didn't know about Windows". When I add more to the thread on EvilZone I'll post it here too.

[DNR]

Good post, I liked how you clearly explained your process of examination and your reasoning behind your theories.

DNR