So I have checked off that bucket list item of speaking at a SQLSaturday. In the process of getting my act together, I learned a thing or two about the undocumented youth of SQLOS threads, between birth and entering the workplace. And you didn’t, which seems unfair.
We normally see stack traces while looking at the top of the stack, typically during a wait, at which point the thread is wearing full worker garb, and has been executing a task for a while. Let’s today reflect on those happy times when our thread was in diapers.
Conception and birth
Threads are born because the system as a whole decides they are cute and it wants more of them. The decision is made in the SystemThreadDispatcher, which is a component of a SchedulerManager, itself a component of an SOS_Node, aka CPU node.
We can simplify this: Threads are born into nodes.
Now a thread isn’t created at the moment that it is needed, and it isn’t legally able to perform work right from birth. The idea is to have a reasonable number of grown-up threads in the population, ready to be put to work at short notice. We are just at the first step.
Thread creation is done through a CreateRemoteThreadEx() call, within the function SystemThreadDispatcher::CreateNewSysThreadIfRequired(), which is invoked as a side task by another thread when it leaves the pool of unemployed threads.
The function pointer passed in as thread entry point is SchedulerManager::ThreadEntryPoint(), and the parameter that will be passed to that entry point is a pointer to the target node’s SchedulerManager. In other words, when the function runs, it will be a completely normal instance method call on that SchedulerManager, parameterless except for the This pointer. And since the SchedulerManager knows what node it belongs to, our newborn thread will instinctively be able to crawl into the arms of the maternal SOS_Node.
But I am getting ahead of myself here. Before even running that entry point function, the thread creation callback registered during SQLOS boot (SystemThread::DllMainCallback()) is invoked by the OS runtime in the context of the new thread. And that gives us a SystemThread associated with the thread, meaning it has – among other things – the Windows event that will let it participate in SQLOS context switching.
So the very first thing our newborn thread, cosily wrapped up in a SystemThread, does is to enlist itself in the parent SOS_Node – and by “enlist” I literally mean adding itself to a linked list. Strictly speaking, it enlists the SystemThread, which is now SQLOS’s proxy to the thread: whenever we want to refer to a thread, we do so through a pointer to its SystemThread. Looking at it from one direction, the SystemThread contains a handle to the thread. From the other direction, any running code can find the ambient SystemThread through a thread-local storage lookup.
As it stands, the thread can’t do much useful in polite company yet, other than suspend itself. SystemThread::Suspend() is the most rudimentary of scheduling functions, just calling WaitForSingleObject() on the thread’s personal Event.
When a thread loves a Worker
ThreadEntryPoint now calls SystemThreadDispatcher::ProcessWorker() on the SOS_Node’s SystemThreadDispatcher, i.e. the one within the current SchedulerManager.
The SystemThreadDispatcher shows itself to be a dating agency, keeping separate linked lists of unattached SystemThreads and idle Workers, and pairing them off according to supply and demand.
From the viewpoint of the thread running it, ProcessWorker() means “find me an unattached Worker so we can change the world together”. If there isn’t a spare Worker at this moment though, the thread goes to sleep through the aforementioned SystemThread::Suspend() call, only to be woken up when a fresh young Worker arrives on the dating scene. This moment is celebrated by ProcessWorker() moving on to call SystemThread::RunWorker()
Pairing the two up includes the SystemThread swearing a vow of loyalty to the Worker’s associated SOS_Scheduler. Up to this point, the thread was “in the SystemThreadDispatcher” and associated with an SOS_Node, but not a specific scheduler. From here onwards, the SystemThread and Worker are fully part of the family of workers for that scheduler.
We now move on to SchedulerManager::WorkerEntryPoint() which initialises the Worker, e.g. setting timestamps and the first quantum target, before invoking the first SOS_Scheduler method, ProcessTasks().
Interesting aside regarding waits: The suspension of a thread within the SystemThreadDispatcher isn’t a measured wait, because waiting is measured at the level of workers and schedulers, neither of which have yet entered the picture.
Your task, should you choose to accept it…
Moving into the family home of the Worker, the first stop within ProcessTasks() is a courtesy call on that scheduler’s WorkDispatcher. If the SystemThreadDispatcher was a dating agency for Workers and SystemThreads, the WorkDispatcher is an employment agency for those couples, pairing them up with jobs in the form of SOS_Tasks.
Entering the WorkDispatcher initially, the pair generally wouldn’t find a pending tasks. At this point they (though the pair is now just viewed as a Worker by the scheduler) are put to sleep through a full-fledged scheduler method, SOS_Scheduler::SuspendNonPreemptive(). This means that the Worker ends up on a suspend queue, specifically the WorkDispatcher’s list of idle workers.
When a task is lobbed over the wall into the scheduler from elsewhere, the WorkDispatcher will assign it to an idle Worker, and the worker made runnable. In due course it will be chosen as the next worker to run, continuing with the ProcessTasks() call to run the specific function specified through the task: this is SOS_Scheduler:RunTask() into SOS_Task::Param::Execute().
The task gets executed, through all the joys and heartaches of taskhood, and if parallelism is involved, child tasks may even be spawned. Ultimately though, the task will be done, and the pair return to the WorkDispatcher’s idle list, blocked in SOS_Scheduler::ProcessTasks() but ready for the next challenge.
You want pictures? Sure.
The relationship between SOS_Node, SOS_Scheduler and their dispatching components
(For the sake of honesty, I should note that a node actually has separate SchedulerManagers for normal and hidden schedulers.)
Up next
This takes care of how tasks, workers, and threads interact – at least in thread mode, which is the only mode we probably care about. In the next blog post I will look into how tasks actually get instantiated.
I was surprised to find it within me to submit a session abstract to SQL Saturday 645 in Manchester. Not to mention delighted when my session on SQLOS scheduling got chosen.
This will be my first time speaking at a SQL Saturday, so I’m pretty excited about the experience. The plan is to cover some fundamentals, revisit a few things I have blogged about, and add bits that have probably never been covered anywhere before.
What can possibly go wrong if I get up on stage? Here endeth the SQL section of this blog post.
This can possibly go wrong when I get up on stage
In a previous life, I spent 7.5 years as a cruise ship musician, first playing in a lounge band, then moving to the show band. I ended up as music director, leading the show band from the piano, and vaguely responsible for supervising and scheduling all music around the ship. Fortunately the latter mostly involved letting people do what they’re good at, and I wasn’t in a position of any responsibility during the below incident.
Back in the mists of early 2001, I worked on a ship that was doing a series of musical theme cruises. One particular cruise was really juicy: the star attraction was a Frank Sinatra impersonator, and our normal 7-piece band got expanded to a 20-piece big band for the occasion. The act was great, the stage was satisfyingly full, and those classic arrangements were a joy to play.
The full show early in the week was over, and regular entertainment went on as usual, except that the star singer was doing a short segment in a variety show on the last night: a magician to open, the singer in the prime spot, and then a short production number from the dance cast.
In line with dinner, which was split between two seatings, shows were done twice each night, at 20:30 and then again at 22:15. Except for the last night, when the second seating had an early 18:45 show before their meal.
Somehow it never occurred to anyone to explicitly mention the flipped showtimes to the headliner. No big deal when we didn’t see his face before curtain up, because he still had twenty minutes to get backstage. But around this time we started asking whether he knows about the early show. Frantic phone calls were made, and towards the end of the magician’s act someone managed to get him on the phone after he just stepped out of the shower.
With one minute to go, and the hope that he can get dressed and ready in three more, the cruise director shouted at the band to play something – anything – while we figure out what to do. The cast was roused from their backstage lazing and told they might have to go on in two.
It was around this point where things completely fell apart. Like any production deployment, stage management works on reasonable certainty and a pre-arranged set of cues. Improvisation rarely has a happy ending.
Keeping a token brave face, the cruise director did a hand-over to the band, who figured we may as well play “A-train” and see where it goes. And the curtain opened up as a half-naked dancer frantically ran across the stage, trailing bits of costume.
The singer turned up a minute after the production cast finished their bit, culminating with the stage being littered with the disgorged content of streamer cannons and unfit for further use. The cruise director, having completely lost the erstwhile brave face, had by then walked on to tell the audience that this was indeed it, and could they please swallow their disappointment as they fill in their feedback forms rating the week’s experience.
The curtain resolutely stayed down. Muffled swearing could be heard backstage. Fingers pointed impotently.
The good news
None of this will happen at SQL Saturday Manchester. I have learned about the dangers of confetti cannons, I will turn up on time, and I probably won’t be in drag.
But if you are interested in the gubbins of context switching, what a SystemThreadDispatcher really does for a living, and you don’t live too far away, do drop by.
So I’ve been having this ongoing discussion with Lonny Niederstadt (b | t) recently, where he tries to make sense of how CheckDB performs, and I fixate on a possibly irrelevant detail. In other words, he talks over my head, and I talk under his feet. Seems fair to me.
Today is the day to air my funny bits, and with some luck Lonny will continue to take us to interesting places in his own explorations.
I’m going to go out on a limb and suggest that none of us are very clear about what external waits are. Code external to SQL Server? External to the CPU? Code that was dropped by aliens?
Previously I dug into preemptive waits in SQLOS, and to be honest, I equated “preemptive” with “external”. For the most part the two go hand in hand after all.
To recap, a preemptive wait isn’t necessarily a wait at all. What happens is that a worker needs to run some code that can’t be trusted to play by cooperative scheduling rules. And rather than put the SQLOS scheduler (and all its sibling workers) at the mercy of that code, the worker detaches itself from the scheduler and cedes control to a sibling runnable worker.
The time period from this moment until the worker returns to cooperative scheduling is labeled as a preemptive wait. During this time, one would hope that the thread did indeed sleep a bit, because it would be directly competing for CPU with its sibling through the mediation of the operating system scheduler. In other words, the time ascribed to a preemptive wait covers an unknown combination of working and sleeping.
In that blog post, I also covered the possibility of external waits getting nested: during the time where we’re executing code but counting each passing tick as external wait A, it is possible to declare another external wait B, and temporarily double count the same slice of time against both. Even more confusingly, we could temporarily dip back into cooperative scheduling while the external “wait” continues.
First, a fundamental premise. A wait type is just a label – a task name someone decided to fill in on a notional time card. Different pieces of code can use the same label for different things, or if we’re lucky, a given wait type is used in one place only, and its presence pinpoints the exact function that was running.
Today I’m only talking about the OLEDB wait as it manifests in CheckDB, although a similar story may pertain elsewhere. In case you didn’t read the title, OLEDB is an external wait type that isn’t preemptive. But what does this mean?
It means that some of what I said about preemptive waits still applies, most significantly the idea that code can actively be running while advertising itself as being in a wait. This can be seen as a slight slant on what the wait type measures: we are using an existing mechanism as a profiling tool that surfaces how much time is spend in a certain chunk of code.
However, in this case the worker doesn’t go preemptive, i.e. it doesn’t yield the scheduler to a sibling while it does the work advertised as a wait.
Here it really gets weird. This worker is cooperatively scheduled, and has a conscience that tells it not to hog the scheduler. Every so often, it will offer to yield, and if the scheduler accepts the offer the CheckDB worker will properly go to sleep, with this sleep time labeled as SOS_SCHEDULER_YIELD.
But at the same time, the clock is still ticking on the OLEDB wait!
This is an entirely new twist on double counting. We claim to be waiting, but are working, except that sometimes we do stop working, counting a bit of time against both OLEDB and SOS_SCHEDULER_YIELD.
I am not saying that this happens all the time, but this is the way that a certain branch of code is written, as least in SQL Server 2014. The OLEDB “wait” is declared within CQScanRmtScanNew::GetRowHelper(), and during this “wait” we get a call to CUtRowset::GetNextRows(), which itself calls CTRowsetInstance::FGetNextRow(). However, within GetNextRows(), after every 16 invocations a courtesy call is made to YieldAndCheckForAbort(), which may yield the scheduler with an SOS_SCHEDULER_YIELD wait.
To visualise broadly:
Visualisation of time spent and time measured
Bonus material: The little preemptive wait that wasn’t
The OLEDB wait is neatly encapsulated in an instance of the CAutoOledbWait class, which in turn contains an SOS_ExternalAutoWait, the same object used by preemptive waits.
Now if we look into SOS_ExternalAutoWait, it comes with three constructors. One gives us a bland UNKNOWN/MISCELLANEOUS wait, presumably on the historic premise that folks didn’t always want to bother categorising their wait activity. Another is fully parameterised, and can emit any supplied wait type. But the third one really catches one’s eye: it’s wired to emit PREEMPTIVE_OS_GETPROCADDRESS.
Clearly PREEMPTIVE_OS_GETPROCADDRESS must serve as a convenient “smoke break” wait type for certain callers, and I’d find it hard to believe that so many people really call GetProcAddress(). So on the premise that nothing in this external wait guarantees it is used preemptively, I am inclined to think that:
When you see this particular wait, you have to read it as MISCELLANEOUS
As with the droppings of the Questing Beast, we recognise synchronisation code paths by their emissions. But even when not leaving telltale fewmets, these creatures wander among us unseen, unsung, until shutdown doth us part.
Today I’ll be examining the SOS_UnfairMutexPair, the synchronisation object behind memory allocations. While I’m going to describe synchronisation as a standalone subject, it’s useful to think of it as theCMEMTHREAD wait; to the best of my knowledge nothing other than memory allocations currently uses this class.
For context, I have previously described a bunch of other synchronisation classes:
The EventInternal, which underpins all cooperative waiting. Note that this has been reborn as WaitableBase in SQL Server 2017.
Latches, which may not be part of SQLOS, but have influenced SQLOS synchronisation. The Latch Files: Out for the count is a good intro to the rich use of atomic compare-and-set operations we’ll see in simplified form today.
One picture which emerges from all these synchronisation flavours is that a developer can choose between busy waiting (eagerly burning CPU), politely going to sleep (thread rescheduling), or a blend between the two. As we’ll see the SOS_UnfairMutexPair goes for a peculiar combination, which was clearly tuned to work with the grain of SQLOS scheduling.
The shape of the object
With the exception of the central atomic lock member, everything comes in pairs here. The class models a pair of waitable objects, each having an associated pair of members to note which scheduler and task currently owns it:
Layout of the SOS_UnfairMutexPair (2016 incarnation)
Although it exposes semantics to acquire either both mutexes or just the second, in its memory allocation guise we always grab the pair, and it effectively acts as a single mutex. I’ll therefore restrict my description by only describing half of the pair.
Acquisition: broad outline
The focal point of the mutex’s state – in fact one might say the mutex itself – is the single Spinlock bit within the 32-bit lock member. Anybody who finds it zero, and manages to set it to one atomically, becomes the owner.
Additionally, if you express an interest in acquiring the lock, you need to increment the WaiterCount, whether or not you managed to achieve ownership at the first try. Finally, to release the lock, atomically set the spinlock to zero and decrement the WaiterCount; if the resultant WaiterCount is nonzero, wake up all waiters.
Now one hallmark of a light-footed synchronisation object is that it is very cheap to acquire in the non-contended case, and this class checks that box. If not owned, taking ownership (the method SOS_UnfairMutexPair::AcquirePair()) requires just a handful of instructions, and no looping. The synchronisation doesn’t get in the way until it is needed.
However, if the lock is currently owned, we enter a more complicated world within the SOS_UnfairMutexPair::LongWait() method. This broadly gives us a four-step loop:
If the lock isn’t taken at this moment we re-check it, grab it, simultaneously increment WaiterCount, then exit triumphantly, holding aloft the prize.
Fall back on only incrementing WaiterCount for now, if this is the first time around the loop and the increment has therefore not been done yet.
Now wait on the EventInternal, i.e. yield the thread to the scheduler.
Upon being woken up by the outgoing owner releasing the lock as described above, try again to acquire the lock. Repeat the whole loop.
The unfairness derives from the fact that there is no “first come, first served” rule, in other words the wait list isn’t a queue. This is not a very British class at all, but as we’ll see, there is a system within the chaos.
The finicky detail
Before giving up and waiting on the event, there is a bit of aggressive spinning on the spinlock. As is standard with spinlocks, spinning burns CPU on the optimistic premise that it wouldn’t have to do it for long, so it’s worth a go. However, the number of spin iterations is limited. Here is a slight simplification of the algorithm:
If the scheduler owning the lock is the ambient scheduler, restrict to a single spin.
Else, give it a thousand tries before sleeping.
Each spin involves first trying to grab both the lock and (if not yet done) incrementing WaiterCount. If that doesn’t work, just try and increment the WaiterCount.
This being of course the bit where the class knows a thing or two about SQLOS scheduling: If I am currently running, then no other worker on my scheduler can be running. But if another worker on my scheduler currently holds the lock, it can’t possibly wake up and progress towards releasing it unless *I* go to sleep. Mind you, this is already a edge case, because we’d hope that the owner of this kind of lock wouldn’t go to sleep holding it.
To see how scheduling awareness comes into play, I’m going to walk through a scenario involving contention on such a mutex. If some of the scheduling detail makes you frown, you may want to read Scheduler stories: The myth of the waiter list.
A chronicle of contention
In this toy scenario, we have two schedulers with two active workers each. Three of the four workers will at some point during their execution try and acquire the same mutex, and one of them will try twice. Time flows from left to right, and the numbered callouts are narrated below. A red horizontal bracket represents the period where a worker owns the mutex, which may be a while after the acquisition attempt started.
The mutex acquisition tango
A1 wants to acquire the mutex and, finding it uncontended, gets it straight away.
B2 tries to acquire it, but since it is held by A1, it gives up after a bit of optimistic spinning, going to sleep. This gives B1 a turn on the scheduler.
A1 releases the mutex, and finding that there is a waiter, signals it. This moves B2 off the mutex’s waiter list and onto scheduler B’s runnable queue, so it will be considered eligible for running at the next scheduler yield point.
B1 wants the mutex, and since it isn’t taken, grabs it. Even though B2 has been waiting for a while, it wasn’t running, and it’s just tough luck that B1 gets it first.
A1 wants the mutex again, but now B1 is holding it, so A1 goes to sleep, yielding to A2.
B1 releases the mutex and signals the waiter A1 – note that B2 isn’t waiting on the resource anymore, but is just in a signal wait.
B1 reaches the end of its quantum and politely yields the scheduler. B2 is picked as the next worker to run, and upon waking, the first thing it does is to try and grab that mutex. It succeeds.
A2 reaches a yield point, and now A1 can get scheduled, starting its quantum by trying to acquire the mutex. However, B2 is still holding it, and after some angry spinning, A2 is forced to go to sleep again, yielding to A1.
B2 releases the mutex and signals the waiting A1, who will hopefully have better luck acquiring it when it wakes up again.
While this may come across as a bit complex, remember that an acquisition attempt (whether immediately successful or not) may also involve spinning on the lock bit. And this spinning manifests as “useful” work which doesn’t show up in spinlock statistics; the only thing that gets exposed is the CMEMTHREAD waiting between the moment a worker gives up and goes to sleep and the moment it is woken up. This may be followed by another bout of unsuccessful and unmeasured spinning.
All in all though, you can see that this unfair acquisition pattern keeps the protected object busy doling out its resource: in this case, an memory object providing blocks of memory. In an alternative universe, the mutex class may well have decided on its next owner at the moment that the previous owner releases it. However, this means that the allocator won’t do useful work until the chosen worker has woken up; in the meantime, the unlucky ones on less busy schedulers may have missed an opportunity to get woken up and do a successful acquire/release cycle. So while the behaviour may look unfair from the viewpoint of the longest waiter, it can turn out better for overall system throughput.
Of course, partitioning memory objects reduced the possibility of even having contention. But the fact remains: while any resources whatsoever are shared, we need to consider how they behave in contended scenarios.
Compare-and-swap trivia
Assuming we want the whole pair, as these memory allocations do, there are four atomic operations performed against the lock member:
Increment the waiter count: add 0x00010001
Increment the waiter count and grab the locks: add 0x80018001
Just grab the locks (after the waiter count was previously incremented): add 0x80008000
Release the locks and decrement the waiter count: deduct 0x80018001
For the first three, the usual multi-step pattern comes into play:
Retrieve the current value of the lock member
Add the desired value to it, or abandon the operation, e.g. if we find the lock bit set and we’re not planning to spin
Perform the atomic compare-and-swap (lock cmpxchg instruction) to replace the current value with the new one as long as the current value has not changed since the retrieval in step 1
Repeat if not successful
The release is simpler, since we know that the lock bits are set (we own it!) and there is no conditional logic. Here the operation is simple interlocked arithmetic, but two’s complement messes with your mind a bit: the arithmetic operation is the addition of 0x7ffe7fff. Not a typo: that fourth digit is an “e”!
This all comes down to thinking of the lock bit as a sign bit we need to overflow in order to set to 1. The higher one overflows out of the 32-bit space, but the lower one overflows into the lowest bit of the first count. To demonstrate, we expect 0x80018001 to turn to zero after applying this operation:
8001 8001
+ 7ffe 7fff
---------
(1) 0000 0000
Final thoughts
So you thought we’ve reached the end of scheduling and bit twiddling? This may turn out to be a perfect opportunity to revisit waits, and to start exploring those memory objects themselves.
I’d like to thank Brian Gianforcaro (b | t) for feedback in helping me confirm some observations.
Like many good things, it started with a #sqlhelp question, this time from Todd Histed (b | t):
Including a bit of back and forth, the issue boiled down to this:
A job is scheduled every minute and takes pretty much exactly 55 seconds to run, due to an included WAITFOR delay of 55 seconds
On SQL Server 2014, this did reliably run every minute
On SQL Server 2016, it skips minutes, effectively running only every two minutes
Reducing the WAITFOR to 30 seconds fixed the issue
Now I get unreasonably excited both by date manipulation and by scheduling issues, so this firmly grabbed my attention. After a bit of unwarranted thinking out loud, I figured it is time to go and do some spelunking.
TL;DR
I understand: you’re a busy elf. Here is the quick summary of what I found.
Disclaimer: the different schedule types, e.g. daily vs monthly, have different special case logic; I’m just concerning myself with (intra-) daily schedules here.
Upon completion of a job, the next run time is calculated based on the last scheduled time plus the schedule interval. However, allowance is made for the edge cases where the completed invocation overruns into the next start time. In such a situation, there isn’t a “catch-up” run; instead, the schedule is advanced iteratively until it reaches a future point in time.
However, 2016 introduces a new twist. When applying the “is the proposed next schedule time after Now()?” check, it adds five seconds to Now(). In other words, the question becomes “Is the proposed next schedule time more than five seconds in the future?”
This looks more like a bug fix than a bug. Clearly cases were found where erroneous schedule invocations were happening, perhaps caused by some combination of job duration, high schedule frequency, and clock adjustments. Whatever the story, this is the behaviour we now live with going forward.
Scheduling is a notoriously tricky subject, because we tend to have an intuitive understanding of how things “ought to work,” while merrily ignoring a million little edge cases that keep developers on their toes. Just in case you needed proof.
Spelunking time
In the course of researching this, a few more fun details emerged.
Please send two mongooses Please send two mongeese
Please send a mongoose. While you’re at it, send another.
When date and time manipulation is needed, where do you turn to? If you’re SQL Agent, this involves custom structures and functions living in SQLSVC.dll. Internally it works with date and time structures with separate 32-bit integer components for the component parts like seconds or months, but translates between this and the funky “packed decimal” pair we see persisted in tables like sysjobhistory, e.g. the integer values 20180321 and 200000 for 20h00 on 21 March 2018.
What I find really cute is the simple approach to implementing Dateadd. We get two functions here, QScheduleDateModify() and QScheduleTimeModify() to operate on such a date/time structure pair. These will only increment or decrement the structure by one tick of the specified unit, so if you want to add six hours to a time, you call QScheduleTimeModify six times with parameter values indicating Increment and Hours.
This may seem primitive, but I suppose it has the advantage of straightforward implementation: as long as overflow of your chosen unit is dealt with correctly, you never need to deal with weird questions like “how many year boundaries are crossed when I add 23,655,101 seconds to the current date?” It isn’t a generic date library, but then it doesn’t need to be. And by definition, normal calculations for schedule times don’t involve a large number of increments, so there isn’t a case for hyper-optimisation.
At this point you probably expect me to whip out Windbg. Here you go then.
Having created a job that was due to fire, I attached to the SQL Agent process, put a breakpoint on SQLSVC!QScheduleCalcNextOccurrence and waited. At the appointed hour, the job ran and the breakpoint was hit as the schedule’s next occurrence needed to get calculated.
Now whether this was C or C++ source code, the Windows x64 ABI tells us that the first parameter passed into the function lives in rcx (highlighted above). I’ll dump a chunk of memory starting at the address it points to, displaying it as 32-bit doublewords:
I’ll push this along – the numbers highlighted in red are of interest. Windbg will oblige us by translating the hexadecimal representation into decimal if we ask nicely:
Well, those kinds of numbers look more familiar, especially if you consider that the schedule fired at 19h19 on 17 April.
The rest of the experiment consisted of deliberately keeping the process frozen in the debugger for ten minutes before letting it run again; because this job was scheduled to run every five minutes, this guaranteed missing at least one run. As expected, and confirmed through a breakpoint on QScheduleTimeModify(), we went through three sets of five 1-minute increments to reach a next invocation time that was in the future.
Of course, some intent peering into assembly language was also involved, but I’ll not bore you further.
Where next?
I have a hunch that I’ll be revisiting SQL Agent at some point in the future again. However, the “Context in perspective” series is still hanging in the air, and will be picked up again. Let’s wait and see.
It’s SQLbits this week, and I’m as excited as a query going through the compile semaphore for the first time, so I’m taking a break from the heavy stuff and gossiping about bugs instead.
The thing about linked lists
I’ve previously done a blog post on doubly linked lists, but here is all you really need to know:
A list entry consists of two pointers, flink (forward link) and blink (backward link).
This structure is embedded at a known offset within the object that wants to be within the list. Because the offset is known, no extra pointer is required to point to the containing object.
The list head is also a flink/blink pair, living within the object that owns the list. An empty list is denoted by both flink and blink pointing to the list head iself.
Because list manipulation needs multiple updates, it can’t be done atomically, and inevitably the list is protected by a spinlock. Even reading it safely requires acquiring the spinlock first, and this is one of the reasons why singly linked lists feature in Hekaton.
Traversing a list involves getting the address of the next entry – flink or blink, depending on direction- and then doing something with the containing record. This may be as simple as checking an attribute and returning that object if it is the desired item, or continuing the traversal if it is not.
On the implementation detail side, you’ll normally find that a function to retrieve a list entry will return a null pointer, i.e. the value zero, when it finds an empty list, because it can’t validly return the address of the list head itself. Consuming code will then treat the null pointer as a signal value that nothing was found, and it will most certainly not try and dereference that value by treating it as an address.
Examples from the wild
These beasties are sometimes easy to recognise from a data dump alone. Here is what the list head for an empty list looks like, in this case from the very CBatch instance I was looking at while researching last week’s post:
Two pointer-sized members, the first one pointing to itself, and the second also pointing to the first, or strictly speaking to the pair starting with the first.
Then we have a list with a single entry, which is also easy to recognise by sight: both flink and blink of the list head point to the same list entry, and both flink and blink of that list entry point back to the list head. Interestingly, from those two bits of information alone, it’s impossible to tell which is the list head and which is the list item.
Here is the listhead within a CSession instance pointing at the list item for the single CBatch within that session:
This is a lovely textbook example. Firstly the vftable symbol confirms that we’re dealing with a CBatch, but the list entry starts at offset 8 and not 0. What this means is that one gets at the CBatch instance linked into this particular list by deducting 8 from the list entry’s address.
One way to cause a stack dump
In my previous post, I referenced one of Kendra Little’s Dear SQL DBA episodes, where she demonstrates a stack dump. The exception that led to the stack dump in question was a particular variation on a null reference:
Now I must admit that I didn’t get around to running Kendra’s repro and checking for myself, but this looks like a slam dunk for a dereference problem on a linked list while simultaneously demonstrating a clever safety convention.
Let’s start with the safety convention. The “null” of a null pointer isn’t a magic value, but in real-life implementation is simply zero, which is a perfectly valid virtual address. However, on the premise that trying to access address zero or addresses near it probably indicates a program error, the OS will map that page in such a way that trying to access it causes an access violation. This is not a bug or an accident, but a damn clever feature! Robert Love explains it very nicely over here for Linux, and it applies equally to Windows.
Now recall the convention that trying to retrieve the head or tail of an empty list will – by convention – bring you back a null pointer. When iterating, a related convention may also return a zero when you’ve gone all the way around and come back to the list head. Clearly the onus is on the developer to recognise that null pointer and not dereference it, but attempting to do so sets in motion the safety feature of an access violation, which can then be neatly caught through standard exception handling, for instance yielding a diagnostic stack dump.
Finding a dereference of address zero doesn’t suggest much in itself – zeroes can come from lots of sources. But the address 8 is far more evocative. If you are doing linked list traversal, the normal direction is through blink, which is accessed by adding eight to the address of the list item. And let’s say that you got the value zero as the address of your list item, but didn’t check the value before doing that dereference, you’d be dereferencing address 8. Hey, there can be other ways to get to address 8, but this is a strong candidate.
I should of course emphasise that diagnostic code such as DBCC PAGE jumps through hoops to avoid standard safety features like taking out locks while remaining “safe enough”, so finding a null pointer bug in such an area is just a reinforcement of the idea that this is unsupported, undocumented, and doesn’t necessarily live by the platinum standards expected in the rest of the product.
Lurking bugs that don’t bite
Ah, the thrill of the chase. There is a perverse delight in reading through a bit of disassembly and finding that logical hole where a safety check was only half-done. Here is an example from the beginning of a function (which will remain unnamed) to the point where we have a null-reference bug – I added simple labels and ASCII-art arrows for control flow.
mov rax,qword ptr [rcx+58h]
add rcx,50h
cmp rax,rcx
+------ je *1*
|
| text rax,rax ; is rax == 0?
+------ je *1*
|
| add rax, 0FFFFFFFFFFFFFFF8h ; i.e. subtract 8
| +- jmp *2*
v |
*1* | xor eax,eax ; i.e. mov rax,0
v
*2* cmp dword ptr [rax+1ACh], r8d ; <-- may dereference address 1AC
It's all in the last two instructions. A path exists where rax may contain the value 0, and while you'd normally expect the zero-check before the dereference, that zero-check is missing.
Now unlike the DBCC PAGE example, which has been known to go wrong, this is in a "production" function which doesn't appear to blow up all the time, i.e. the preconditions for the bug coming to light simply aren't there. In practical terms, at the point this function is called, clearly the list in question is never empty. Does that kind of code pattern even count as a bug? I guess the only thing that makes it stand out is the acknowledgement that we may find rax to be zero, or even force it to zero, right before the dereference. But this is probably inherited from an inlined function, and it is only in the disassembly that we see the juxtaposition so clearly.
For my part, I shall continue to delight in finding oddities like this. But at the same time it reminds me that I have a lot to be humble about: if I can spot these little things in the code produced by seriously good programmers, just think of the horrors they would be able to find in my code.
A few weeks ago, Kendra Little did a very entertaining Dear SQL DBA episode about stack dumps. That gave me a light bulb moment when I tied the preamble of her stack dump example to a DBCC command that I’ve had on the back burner for a while. The command puts some session-related objects on stage together, and those objects bridge the gap between a DMV-centric view of the SQL Server execution model and the underlying implementation.
Let’s revisit the purpose of a dump. When you catch one of these happening on your server, it’s sensible to be alarmed, but it is rather negative to say “Oh no, something horrible went wrong!” A more positive angle is that a disturbance was detected, BUT the authorities arrived within milliseconds, pumped the whole building full of Halon gas, and then took detailed forensic notes. Pity if innocent folks were harmed by that response, but there was cause to presume the involvement of a bad hombre, and that is the way we roll around here.
Today we’ll be learning lessons from those forensic notes.
Meet DBCC TEC
Boring old disclaimer: What I am describing here is undocumented, unsupported, likely to change between versions, and will probably make you go blind. In fact, the depth of detail exposed illustrates one reason why Microsoft would not want to document it: if end users of SQL Server found a way to start relying on this not changing, it would hamstring ongoing SQL Server improvement and refactoring.
With that out of the way, let’s dive right into DBCC TEC, a command which can dump a significant chunk of the object tree supporting a SQL Server session. This result is the same thing that shows up within a dump file, namely the output of the CSession::Dump() function – it’s just that you can invoke this through DBCC without taking a dump (cue staring match with Kendra). Until corrected, I shall imagine that TEC stands for Thread Execution Context.
In session 53 on a 2014 instance, I start a batch running the boring old WAITFOR DELAY ’01:00:00′, and while it is running, I use another session to run DBCC TEC against this session 53. The DBCC command requires traceflag 3604, and I’m going to ignore the first and third parameters today; my SQL batch then looks like this:
DBCC TRACEON(3604);
DBCC TEC(0,53,0);
Here is the output I got, reformatted for readability, and with the bulk of the long output buffer omitted:
First observation: this is a treasure trove, or perhaps a garbage dump. Second observation: the output could actually get a lot more verbose, depending on what the session under scrutiny is doing.
All in all, the fact of its inclusion in dump files tells us that it contains useful information to support personnel, and helps to add context in a crash investigation.
A glimpse of the object tree
You certainly can’t accuse DBCC TEC of being easy on the eyes. But with a bit of digging (my homework, not yours) it helps to piece together how some classes fit together, tying up tasks, sessions and execution contexts.
Recall that Part 5 demonstrated how one can find the CSession for a given thread. DBCC TEC walks this relationship in the other direction, by deriving tasks and threads – among other things – from sessions.
While this isn’t made obvious in the text dump, below diagram illustrates the classes involved, and their linkages.
The object tree revealed by DBCC TEC
Of course these are very chunky classes, and I’m only including a few members of interest, but you should get the idea.
Observations on DBCC TEC and class relationships
Let’s stick to a few interesting tidbits. CSession is the Big Daddy, and it executes CBatches. Although we’d normally only see a single batch, under MARS there can be more; this manifests by the session actually having a linked list of batches, even though normally the list would contain a single item (I simplified to a scalar on the diagram).
A session keeps state and settings within a CUEnvTransient, which in turn refers to a CDbAndSetOpts. You should recognise many of those attributes from the flattened model we see in DMVs.
However, to make it more interesting, a task (indirectly) has its own CUenvTransient; this is one reflection on the difference between batch-scoped and session-scoped state. And on top of that, even a session actually has two of them, with the ability to revert to a saved copy.
Although a CBatch may execute CStatements, we don’t see this here. The actual work done by a batch is of course expressed as a SOS_Task, which is a generic SQLOS object with no knowledge of SQL Server.
At this point the DBCC output layout is a bit misleading. Where we see EXCEPT (null) it is SOS_Task state being dumped, and we’re not within the CBatch anymore. However, the SOS_Task is actually just the public interface that SQLOS presents to SQL Server, and some of the state it presents live in the associated Worker. The exception information lives within an ExcHandler pointed to by the Worker, and things like CPU Ticks used come directly from the Worker. Task State is the same rather convoluted derivation exposed in sys.dm_os_tasks, as outlined in Worker, Task, Request and Session state. ThreadID is an attribute of the SystemThread pointed to by the task’s Worker, and similarly SchedulerID comes indirectly via the Task’s SOS_Scheduler.
WAITINFO_INTERNAL and (where applicable) WAITINFO_EXTERNAL describe cooperative and preemptive waits respectively. The latter can actually get nested, giving us a little stack of waits, as described in Going Preemptive.
Now we start peering deeper into the task, or rather through it into its associated worker’s LocalStorage as described in Part 5. The first two slots, respectively pointing to a CCompExecCtxtBasic and an ExecutionContext, have their contents dumped at this point.
The ExecutionContext points to one instance each of SEInternalTLS and SEParams. Pause here for a moment while I mess with your mind: should the task in question be executing a DBCC command, for instance DBCC TEC, the m_pDbccContext within the SEInternalTLS will be pointing to a structure that gives DBCC its own sense of context.
Another fun observation: while SEInternalTLS claims with a straight face to have an m_owningTask member, I call bull on that one. Probably it did in the past, and some poor developer was required to keep exposing something semi-meaningful, but the address reported is the address of the ambient task, i.e. the one running DBCC TEC. The idea of ownership is simply not modelled in the class.
Then (still down in the LocalStorage of a Task performed by the Batch under scrutiny) we get the CCompExecCtxtBasic we saw in Part 5. This now shows us a few more members, starting with a CConnection which in turn points to a CNetConnection getting its buffers dumped for out viewing pleasure. This CConnection is in fact the same one pointed to directly by the Batch as m_pConn.
Now, as already mentioned, we see the CUEnvTransient with associated CDbAndSetOpts belonging to the task at hand (through its Worker’s LocalStorage->CCompExecCtxtBasic).
The next CCompExecCtxtBasic member is a pointer to a CEvevLvlIntCtxt which in turn references an IBHFDispenser; in case you’re wondering, BHF stands for BlobHandleFactory, but I’m not going to spill the beans on that yet, because I am fresh out of beans.
Finally, CCompExecCtxtBasic’s performance ends with the duo of CExecLvlRepresentation and a CStmtCurState, neither of whom has much to say.
Whew. That was the superficial version.
Are we all on the same page?
While we could spend a lot of time on what all these classes really do, that feels like material for multiple separate blog posts. Let’s finish off by looking at the pretty memory layout.
Recall that addresses on an 8k SQLOS page will cover ranges ending in 0000 – 1FFF, 2000 – 3FFF, 4000 – 5FFF etc, and that all addresses within a single such page will have been allocated by the same memory object. Now note that the objects which expose a pmo (pointer to memory object) all point to 0x38772040. This sits on (and manages) a page stretching from 0x38772000 to 0x38773FFF.
Have a look through those object addresses now. Do you see how many of them live on that page? This is a great example of memory locality in action. If a standard library’s heap allocation was used, those addresses would be all over the place. Instead, we see that the memory was allocated, and the objects instantiated, with a clear sense of family membership, even though the objects are notionally independent entities.
As a final note on the subject of memory addresses, the eagle-eyed may have noticed that the CPhysicalConnection has a m_pSess pointer which is close to, but not equal to the address of the CSession at the top of the object tree. This is because it is an ILogonSession interface pointer to this CSession instance, with the interface’s vftable living at an offset of 0x58 within the CSession class. See Part 3 for more background.
Further reading
Go on and re-read Remus Rusanu’s excellent How SQL Server executes a query. If you’ve never read it, do so now – it’s both broad and deep, and you can trust Remus on the details.
While reading it, see in how many places you can replace e.g. “Session” with “CSession”, and you will be that bit closer to Remus’s source code-flavoured subtext.
Time to switch context to an old thread, specifically the SystemThread class. I have done this to death in an Unsung SQLOS post, but if you don’t want to sit through that, here are the bits we care about today:
All work in SQLOS is performed by good old-fashioned operating system threads.
SQLOS notionally extends threads with extra attributes like an associated OS event object, and behaviour like a method for for waiting on that event. This bonus material lives in the SystemThread class, which is conceptually a subclass of an operating system thread, although this isn’t literally class inheritance.
A SystemThread instance lives in memory which is either allocated on the heap and pointed to by a thread-local storage slot, or it squats right across a range of TLS slots within the Thread Environment Block.
Due to the nature of thread-local storage, at any moment any code running on a SQLOS thread can get a reference to the SystemThread it’s running on; this is described in gory detail in Windows, Mirrors and a sense of Self. Powerful stuff, because this ambient SystemThread indirectly exposes EVERYTHING that defines the current SQL Server context, from connection settings to user identity and beyond.
Life is a box of ogres
LS through the looking glass
Understanding SQLOS takes us only so far, because it is after all just the substrate upon which SQL Server is built. We’ve now reached the point where SQLOS hands SQL Server a blank slate and says “knock yourself out”.
This blank slate is a small but delicious slice of local storage: an array of eighteen pointers living within the SystemThread. SQLOS has no interest in what these are used for and what they mean. As far as it is concerned, it’s just a bunch of bytes of no known type. But of course SQL Server cares a lot more.
Park that thought for a moment to consider that we’re starting to build up a hierarchy of thread-local storage:
Upon an OS context switch, the kernel swaps the value held in the CPU’s GS register to point to the Thread Environment Block of the incoming thread.
Within this Thread Environment block lives TLS slots that SQLOS takes advantage of. One of these will always point to the currently running SystemThread instance. In other words, when the kernel does a context switch, the change of OS thread brings with it a change in the ambient SystemThread which can be retrieved from TLS.
Now within this SystemThread, an array of eighteen pointer-sized slots are made available for the client application (SQL Server) to build upon.
What does this mean from the viewpoint of SQL Server? Well, even within the parts that don’t care about SQLOS and the underlying OS, code can express and find current thread-specific state – at a useful abstraction level – somewhere within those eighteen slots.
Worker LocalStorage vs thread-local storage
We often skirt around the distinction between a worker and a thread. This is a benign simplification, because instances of Worker and SystemThread classes are bound together in a 1:1 paired relationship during all times when SQL Server code is running.
The only time the distinction becomes particularly interesting is when we’re in fiber mode, because now a single SystemThread can promiscuously service multiple Workers in a round-robin fashion. I have documented some details in The Joy of Fiber Mode, but of special interest today is the treatment of these local storage slots.
These now become a more volatile part of thread context, and a SQLOS context switch (in this case, a fiber switch) must include copying the Worker’s LocalStorage payload into the SystemThread slots, because there is no guarantee that two different Workers will share the exact same context; in fact it is close to certain they won’t.
So clearly the context that matters to the Task at hand lives within the Worker, and SQLOS makes sure that this is the context loaded into a SystemThread while it runs; it’s just that the SQLOS scheduler has to intervene more in fiber mode, whereas it can let this bit of state freewheel in thread mode.
On to the implementation details then. Unlike the case with the SystemThread, a Worker’s local storage isn’t a chunk of memory within the class, but lives in a heap allocation, represented by an instance of the LocalStorage class embedded within the Worker.
Additionally, while the SystemThread’s slot count is baked into SQLOS, somebody clearly wanted a bit more abstraction in the Worker class, so the slot count becomes an attribute of a LocalStorage instance, which thus consists of a grand total of two members:
The slot count, passed into the LocalStorage constructor
A pointer to the actual chunk of memory living somewhere on the heap and allocated by the LocalStorage constructor, which is a thin wrapper around a standard page allocator
Show me some numbers, and don’t spare the horses
On to the fun bit, but you’re going to have to take my word on two things. Firstly, the SystemThread’s local storage slots are right at the start of the object. And secondly, the LocalStorage instance lives at an offset of 0x30 within a Worker, at least on the version I’m using here.
To prepare, I needed to capture the addresses of a bound SystemThread:Worker pair before breaking into the debugger, so I started a request running in session 53, executing nothing but a long WAITFOR – this should keep things static enough while I fumble around running a DMV query in another session:
Capturing the worker and thread addresses of our dummy request
So we’re off yet again to stage a break-in within Windbg. Having done this, everything is frozen in time, and I can poke around to my heart’s content while the business users wonder what just happened to their server. No seriously, you don’t want to do this on an instance that anyone else needs at the same time.
Here is the dump of the first 64 bytes of that Worker. As in Part 4, I’m dumping in pointer format, although only some of these entries are pointers or even necessarily 64 bits wide. In case it isn’t clear, the first column is the address we’re looking at, and the second column is the contents found at that address. The dps command sweetens the deal a bit: if that payload is an address corresponding to a known symbol (e.g. a the name of a function), that symbol will be displayed in a third column.
Those highlighted last two represent the LocalStorage instance, confirming that we do indeed have eighteen (=0x12) slots, and telling us the address where that slot array starts. Let’s see what payload we find there:
It seems that only five out of the eighteen are in use. Oh well, that’s neither here nor there. Let’s compare this to the first eighteen quadwords at the bound SystemThread’s address we found in sys.dm_os_threads:
This isn’t the same address as the Worker’s local storage array, but the contents is the same, which is consistent with my expectation. I’m highlighting that first entry, because we’ll be visiting it later.
Just out of interest, I’m also going to try and tie things back to memory page observations made in Part 4. Let’s peek at the top of the 8k page that the LocalStorage lives on. Its address is 0x3b656c80, which rounded down to the nearest 8k (=0x2000) gives us a page starting address of 0x3b656000.
The shape of that page header looks familiar. The second quadword is a pointer to the address 0x40 bytes into this very page. And just to hand it to us on a plate, the object starting there reveals itself by its vftable symbol to be a CMemObj.
In other words, this particular bit of LocalStorage is managed by a memory object which lives on its very page – obviously it would be wasteful if a memory object refused to share its page with some of the objects it allocated memory for. Also note that this is a plain CMemObj and not a CMemThread<CMemObj>, i.e. it isn’t natively thread-safe. This may simply confirm that local storage is not intended for sharing across threads; see Dorr for more.
Cutting to the chase
So far, this is all rather abstract, and we’re just seeing numbers which may or may not be pointers, pointing to heaven knows what. Let me finish off by illuminating one trail to something we can relate to.
Out of the five local storage slots which contain something, the first one here points to 00000000`3b656040. As it turns out, this is an instance of the CCompExecCtxtBasic class, and you’ll just have to take my word for it today. Anyway, we’re hunting it for its meat, rather than for its name. Have some:
You may recognise by the range of memory addresses we’ve seen so far that most of these are likely themselves pointers. I’ll now lead you by the hand to the highlighted fourth member of CCompExecCtxtBasic, and demonstrate what that member points to:
Bam! Given away by the vftable yet again – this is a CSession instance, in other words probably the session object associated with that running thread. As per Part 3, the presence of more than one vftable indicates that we may be dealing with multiple virtual inheritance in the CSession class.
We’ll leave the last word for the highlighted third line, containing the value 0x35 as payload.
What does 0x35 translate to in decimal? Would you believe it, it’s 53, the session_id of the session associated with the thread. If we were feeling bored, we could go and edit it to be another number, essentially tinkering with the identity of that session. But today is not that day.
Putting it all together in a diagram, here then is one trail by which an arbitrary chunk of SQL Server code can find the current session, given nothing more than the contents of the GS register:
Sure, your programming language and framework may very well abstract away this kind of thing. But that doesn’t mean you aren’t relying on it all the time.
Final thoughts
This exercise would qualify as a classic case of spelunking, where we have a general sense of what we’d expect to find, perhaps egged on by a few clues. Just as I’m writing this, I see that Niels Berglund has also been writing about spelunking in Windbg. So many angles, so much interesting stuff to uncover!
The key takeaway should be a reminder of how much one can do with thread-local storage, which forms the third and often forgotten member of this trio of places to put state:
Globally accessible heap storage – this covers objects which are accessible everywhere in a process, including ones where lexical scope attempts to keep them private.
Function parameters and local variables – these have limited lifespans and live in registers or on the stack, but remain private to an invocation of a function unless explicitly shared.
Thread-local storage – this appears global in scope, but is restricted to a single thread, and each thread gets its own version of the “same” global object. This is a great place to squirrel away the kind of state we’d associate with a session, assuming we leverage a link between sessions and threads.
I hope that the theme of this series is starting to come together now. One or two more to go, and the next one will cover sessions and their ancillary context in a lot more breadth.
It’s the second Tuesday of the month, and we all know what that means. T-SQL Tuesday, the brainchild of Adam Machanic, is hosted by Kennie Pontoppidan this month, and his chosen theme is The daily database-related WTF.
What could possibly go wrong?
The story
Basic algorithms are a bit passe when it comes to interview questions nowadays, but time was when it was reasonable to sound out a developer by asking them simple things like how to measure the length of a string. After all, edge cases lurk in unexpected places.
Of course, nobody rolls their own strlen() or String.length() anymore. It’s a solved problem, and we can spend our time on more interesting questions, like “how can we wrap up the string length puzzle in a suitably odd framework?” Enter the Universal Enterprise Form Workflow System, stage left.
Because developers are expensive
When you spend a reasonable amount of time churning out simple form-based UI workflows, you inevitably get bored. And you try and abstract away the drudgery of building forms into something the Common Folks can manage, by building a framework, because Lord knows you can’t buy this sort of thing off the shelf. Inevitably, the arcane knowledge of how to churn out expensive work without obviously doing expensive work can safely stay within an inner circle of senior developers who will be the only people ever allowed to try and configure a no-programming-needed workflow.
Never mind. Their hearts were in the right place.
Workflows were strung together by stored procedures following standard templates, bound to form inputs using some manner of configuration sacrament. The details are lost in the mists of time. But one thing was clear: a configured workflow could not involve any logic other than simple switch statements driven from the output of these stored procedures.
Then arrived the day when stone tablets carven with business requirements arrived from on high, and lo, there was a need for data validation of the form “Twenty shall be the length of the string, and the length of the string shall not exceed twenty.”
After the requisite number of arguments against sullying the purity of the framework by trying to make it measure strings, the solution was agreed upon. From this day hence, there shall be deployéd a stored procedure which, given a varchar parameter, wouldst return a result set containing one column. And the value of that column shall be as a sign unto the unbelieving masses, proclaiming the final judgement of an enterprise-class relational database management system upon the question “Was my input string no more than twenty characters long?”
Although today’s post is loosely related to the esoterica of multiple virtual inheritance I unearthed in part 3, it is far more straightforward and goes no further than single inheritance. Spoiler alert: people come up with clever stuff.
Part 3 was a riff on the theme of finding the address of an object, given the address of an interface (vftable) within that object. This was made possible by a combination of member offsets known at compile time and offsets explicitly stored within the object. Now we move on to discover how the address of one object can be derived from the address of another, purely by convention and without relying on magic numbers known only to the compiler or stored in runtime structures. Sounds interesting?
I have often walked down this deck before
But the water always stayed beneath my neck before
It’s the first time I’ve had to scuba dive
When I’m down on the deck where you live.
Come dive with me
In Part 2, the last example was a function which optionally called commondelete as object disposal after the class destructor:
sqllang!CSecContextToken::`vector deleting destructor':
=======================================================
mov qword ptr [rsp+8],rbx
push rdi
sub rsp,20h
mov ebx,edx
mov rdi,rcx
call sqllang!CSecContextToken::~CSecContextToken
test bl,1
+-+- je LabelX
| |
| | { if low bit of original edx was set
| -> mov rcx,rdi
| call sqllang!commondelete
| }
|
LabelX:
+--> mov rax,rdi
mov rbx,qword ptr [rsp+30h]
add rsp,20h
pop rdi
ret
So what does commondelete() do? Well, quite simply it is a global function that releases a previously allocated block of memory starting at the supplied address. Prior to the construction of an object, we need to allocate a chunk of memory to store it in, and after its destruction, this memory must be given back to the pool of available memory. Forgetting to do the latter leads to memory leaks, not to mention getting grounded for a week.
Notionally we can imagine a global portfolio of active memory allocations, each chunk uniquely identified by its starting address. When we want memory, we ask the global memory manager to lend us some from the unused pool, and when we’re done with it, we hand it back to that memory manager, who carefully locks its internal structures during such operations, because we should only access mutable global state in a single-threaded manner, and…. Oops. No, no, double no. That is not how SQL Server does things, right?
Okay, we know that there are actually a variety of memory allocators out there. If nothing else, this avoid the single bottleneck problem. But now the question becomes one of knowing which allocator to return a chunk of memory to after we’re done with it.
One possible solution would be for the object which constructs a child object to store its own reference to the allocator, and this parent object is then the only object who is allowed to destroy its child object. However, this yields a system where all objects have to exist in a strict parent-child hierarchy, which is very restrictive.
As it turns out, many interesting SQL Server objects control their lifetime through reference counting. If object A wants to interact with object B, it first announces that interest, which increases the reference count on B. This serves as a signal that B can’t be disposed, i.e. the pointer held by A remains valid. Once done, A releases the reference to B, which decreases B’s reference count again. Ultimately, B can only be destroyed after its reference count has reached zero. One upshot of this is that objects can live independent lives, without forever being tied to the apron strings of a parent object.
From that given, the problem becomes this: an object playing in this ecosystem must carry around a reference to its memory allocator. Doing it explicitly is conceptually simple. However, it would be onerous, because this pointer would take up an eight-byte chunk of memory within the object itself, which can be a significant tax when you have a large number of small objects. Perhaps more significantly, it raises the complexity bar to playing along, because now all objects must be born with a perfectly-developed plan for their own eventual death, and they must implement standardised semantics for postmortem disposal of their bodies. That’s harsh, not to mention bug-prone.
Far better then would be a way for an outside agent to look at an object and know exactly where to press the Recycle button, although the location of that button is neither global nor stored within the target object.
Pleasant little kingdom
Imagine a perfectly rational urban design; American grid layout taken to the extreme. Say you live at #1137 Main Street and want to find the nearest dentist, dentistry being of particular importance in this kingdom. Well, the rule is simple: every house number divisible by 100 contains a dentist, and to find your local one you just replace the last two digits of your house number with zeros.
That is the relationship that objects have with their memory allocators under SQLOS, except that we are dealing with 8192-byte pages. Take the address of any object in memory, round that address down to the next lower page boundary, and you will find a page header that leads you directly or indirectly to the memory object (allocator) that owns the object’s memory; this object will happily receive the notification that it can put your chunk of memory back into the bank.
I’m skipping some detail around conditionals and an indirect path, but the below is the guts of how commondelete() takes an address and crafts a call to the owning memory object to deallocate that target object and recycle the corpse:
mov rdx, rcx
and rcx, 0FFFFFFFFFFFFE000h
; now rdx contain the address we want to free
; and rcx is the start of the containing page
mov rcx, qword ptr [rcx+8]
; now rcx contains the 2nd qword on the page.
; This is the address of the memory object,
; aka pmo (pointer to memory object)
mov rax, qword ptr [rcx]
; 1st qword of object = pointer to vftable
; Now rax points to the vftable
call qword ptr [rax+28h]
; vftable is an array of (8-byte) function
; pointers. This calls the 6th one. Param 1
; (rcx) is the pmo. Param 2 (rdx) is the
; address we want to free.
See, assembler isn’t really that bad once you put comments in.
Show me
Let’s find ourselves some SQLOS objects. SOS_Schedulers are sitting ducks, because you can easily find their addresses from a DMV query, and they don’t suddenly fly away. And of course I have explored them before. Below from a sad little VM:
I’m getting scheduled in the morning
Got myself a few candidate addresses, so it’s time to break into song the debugger. I’m going to dump a section of memory in 8-byte chunks, and to make it more interesting, I’ll do so with the dps command, which assumes all the memory contents are pointers, and will call out any that it recognises from public symbols. Never mind that this regimented 8-byte view may be at odds with the underlying data’s shape – it’s just a convenient way to slice it.
Because I know where I’m heading, I’m rounding the starting address down to the start of that 8Kb page:
Firstly, we have a beautiful piece of confirmation that the object starting at 0040 is indeed a scheduler, because its very first quadword contains a pointer to the ThreadScheduler vftable. But we knew that already 🙂
What I’d like to know is what the second quadword on the page, at 0008, is pointing to. Interesting, its address also ends in 0040…
Same thing then, let’s dump a bit of that, starting from the top of that page:
Aha! On a freaking platter. The vftable symbol name confirms that the scheduler’s parent memory object is in fact a CMemThread<CMemObj>. Not only that, but if you look at the second slot, it seems that a memory object is its own owner!
But speaking of the vftable, since we’re now familiar with these creatures as simple arrays of function pointers, let’s dump a bit of it. The full thing is rather long; this is just to give you the idea:
Recall that commondelete() calls the sixth entry, located 0x28 bytes from the start. Unsurprisingly, this is the Free() function. And look, the first three tell us that COM is spoken here.
Takeaway
This is not the time to get into the details of how memory objects actually work, but we sure got a nice little glimpse of what SQLOS does with the memory space. Also, the charming side of vftables was laid bare.
Although the assembler view might look daunting, we saw how a virtual method, in this case Free(), is called, using nothing more than the address of the vftable and the knowledge that the object residing there is (or is derived from) the base type exposing that method.
But let’s not lose sight of the “Context in perspective” goal. Here the context is the address of a single object, and the perspective is seeing it framed by convention within a memory page. By its placement in memory, the object gains the all-important implicit attribute of an owning memory object.
