1 ////////////////////////////////////////////////////////////////////
2 // Copyright (C) Alexander Telyatnikov, Ivan Keliukh, Yegor Anchishkin, SKIF Software, 1999-2013. Kiev, Ukraine
3 // All rights reserved
4 // This file was released under the GPLv2 on June 2015.
5 ////////////////////////////////////////////////////////////////////
6 /*
7
8 Module Name:
9
10 DLDetect.cpp
11
12 Abstract:
13
14 This file contains all source code related to DeadLock Detector.
15
16 Environment:
17
18 NT Kernel Mode
19
20 */
21
22 #include "udffs.h"
23
24 /// define the file specific bug-check id
25 #define UDF_BUG_CHECK_ID UDF_FILE_DLD
26
27
28 /// Resource event (ExclusiveWaiters)
29 #define RESOURCE_EVENT_TAG 'vEeR'
30 /// Resource semaphore (SharedWaiters)
31 #define RESOURCE_SEMAFORE_TAG 'eSeR'
32 /// Resource owner table (OwnerTable)
33 #define RESOURCE_TABLE_TAG 'aTeR'
34
35 /// Maxmum recurse level while exploring thread-resource aquisition graf
36 #define DLD_MAX_REC_LEVEL 40
37
38 /// Maximum supported number of threads (initialized by DLDInit())
39 ULONG MaxThreadCount = 0;
40
41 /// Waiters table
42 PTHREAD_STRUCT DLDThreadTable;
43 /// 4 sec
44 LARGE_INTEGER DLDpTimeout;
45 /// 8 sec
46 ULONG DLDpResourceTimeoutCount = 0x2;
47
48 THREAD_REC_BLOCK DLDThreadAcquireChain[DLD_MAX_REC_LEVEL];
49
50 /// Initialize deadlock detector
DLDInit(ULONG MaxThrdCount)51 VOID DLDInit(ULONG MaxThrdCount /// Maximum supported number of threads
52 ) {
53 if (KeNumberProcessors>1) {
54 UDFPrint(("Deadlock Detector is designed for uniprocessor machines only!\n"));
55 BrutePoint();
56 }
57 DLDpTimeout.QuadPart = -40000000I64;
58
59 MaxThreadCount = MaxThrdCount;
60 DLDThreadTable = (PTHREAD_STRUCT) DLDAllocatePool(MaxThreadCount*sizeof(THREAD_STRUCT));
61 RtlZeroMemory(DLDThreadTable, sizeof(THREAD_STRUCT)*MaxThreadCount);
62 }
63
DLDFree(VOID)64 VOID DLDFree(VOID) {
65
66 DLDFreePool(DLDThreadTable);
67
68 }
69
DLDAllocFindThread(ULONG ThreadId)70 PTHREAD_STRUCT DLDAllocFindThread(ULONG ThreadId) {
71 ULONG i = 0;
72 PTHREAD_STRUCT Temp = DLDThreadTable;
73 ULONG FirstEmpty = -1;
74
75 while (i<MaxThreadCount) {
76 if (Temp->ThreadId == ThreadId) {
77 return Temp;
78 } else if (FirstEmpty == -1 && !Temp->ThreadId) {
79 FirstEmpty = i;
80 }
81 Temp++;
82 i++;
83 }
84 // Not found. Allocate new one.
85 if (i == MaxThreadCount) {
86 if (FirstEmpty == -1) {
87 UDFPrint(("Not enough table entries. Try to increase MaxThrdCount on next build"));
88 BrutePoint();
89 }
90 i = FirstEmpty;
91 }
92 Temp = DLDThreadTable + i;
93
94 RtlZeroMemory(Temp, sizeof(THREAD_STRUCT));
95 Temp->ThreadId = ThreadId;
96
97 return Temp;
98 }
99
DLDFindThread(ULONG ThreadId)100 PTHREAD_STRUCT DLDFindThread(ULONG ThreadId) {
101 ULONG i = 0;
102 PTHREAD_STRUCT Temp = DLDThreadTable;
103 ULONG FirstEmpty = -1;
104
105
106 while (i<MaxThreadCount) {
107 if (Temp->ThreadId == ThreadId) {
108 return Temp;
109 }
110 Temp++;
111 i++;
112 }
113
114 return NULL;
115 }
116
117 BOOLEAN DLDProcessResource(PERESOURCE Resource,
118 PTHREAD_STRUCT ThrdStruct,
119 ULONG RecLevel);
120
121
122 /// TRUE Indicates deadlock
DLDProcessThread(PTHREAD_STRUCT ThrdOwner,PTHREAD_STRUCT ThrdStruct,PERESOURCE Resource,ULONG RecLevel)123 BOOLEAN DLDProcessThread(PTHREAD_STRUCT ThrdOwner,
124 PTHREAD_STRUCT ThrdStruct,
125 PERESOURCE Resource,
126 ULONG RecLevel) {
127
128 if (ThrdOwner == ThrdStruct) {
129 // ERESOURCE wait cycle. Deadlock detected.
130 UDFPrint(("DLD: *********DEADLOCK DETECTED*********\n"));
131 UDFPrint(("Thread %x holding resource %x\n",ThrdOwner->ThreadId,Resource));
132 return TRUE;
133 }
134
135 for (int i=RecLevel+1;i<DLD_MAX_REC_LEVEL;i++) {
136 if (DLDThreadAcquireChain[i].Thread->ThreadId == ThrdOwner->ThreadId) {
137 // ERESOURCE wait cycle. Deadlock detected.
138 UDFPrint(("DLD: *********DEADLOCK DETECTED*********\n"));
139 UDFPrint(("Thread %x holding resource %x\n",ThrdOwner->ThreadId,Resource));
140 for (int j=RecLevel+1;j<=i;j++) {
141 UDFPrint((" awaited by thread %x at (BugCheckId:%x:Line:%d) holding resource %x\n",
142 DLDThreadAcquireChain[i].Thread->ThreadId,
143 DLDThreadAcquireChain[i].Thread->BugCheckId,
144 DLDThreadAcquireChain[i].Thread->Line,
145 Resource));
146 }
147 BrutePoint();
148 return FALSE;
149 }
150 }
151 DLDThreadAcquireChain[RecLevel].Thread = ThrdOwner;
152 DLDThreadAcquireChain[RecLevel].HoldingResource = Resource;
153
154 // Find resource, awaited by thread
155 if (ThrdOwner->WaitingResource) {
156 if (DLDProcessResource(ThrdOwner->WaitingResource, ThrdStruct,RecLevel)) {
157 UDFPrint((" awaited by thread %x at (BugCheckId:%x:Line:%d) holding resource %x\n",
158 ThrdOwner->ThreadId,
159 ThrdOwner->BugCheckId,
160 ThrdOwner->Line,
161 Resource));
162 return TRUE;
163 }
164 }
165
166 return FALSE;
167 }
168
169
170 /// TRUE Indicates deadlock
DLDProcessResource(PERESOURCE Resource,PTHREAD_STRUCT ThrdStruct,ULONG RecLevel)171 BOOLEAN DLDProcessResource( PERESOURCE Resource, // resource to process
172 PTHREAD_STRUCT ThrdStruct, // thread structure of caller's thread
173 ULONG RecLevel) // current recurse level
174 {
175 if (RecLevel <= 0) {
176 BrutePoint();
177 return FALSE;
178 }
179
180
181 // If resource is free, just return. Not possible, but we must check.
182 if (!Resource->ActiveCount) {
183 return FALSE;
184 }
185
186 PTHREAD_STRUCT ThreadOwner;
187
188
189 if (Resource->Flag & ResourceOwnedExclusive || (Resource->OwnerThreads[1].OwnerCount == 1)) {
190
191 // If only one owner
192
193 // Find thread owning this resource
194 if (Resource->Flag & ResourceOwnedExclusive) {
195 ThreadOwner = DLDFindThread(Resource->OwnerThreads[0].OwnerThread);
196 } else {
197 ThreadOwner = DLDFindThread(Resource->OwnerThreads[1].OwnerThread);
198 }
199
200 BOOLEAN Result = FALSE;
201 if (ThreadOwner) {
202 Result = DLDProcessThread(ThreadOwner, ThrdStruct, Resource,RecLevel-1);
203 }
204 return Result;
205 } else {
206 // Many owners
207 int i;
208 for (i=0; i<Resource->OwnerThreads[0].TableSize; i++) {
209 if (Resource->OwnerTable[i].OwnerThread) {
210
211 ThreadOwner = DLDFindThread(Resource->OwnerTable[i].OwnerThread);
212 if (ThreadOwner && DLDProcessThread(ThreadOwner, ThrdStruct, Resource,RecLevel-1)) {
213
214 return TRUE;
215 }
216 }
217 }
218 }
219
220 return FALSE;
221 }
222
223
224
DLDpWaitForResource(IN PERESOURCE Resource,IN DISPATCHER_HEADER * DispatcherObject,IN PTHREAD_STRUCT ThrdStruct)225 VOID DLDpWaitForResource(
226 IN PERESOURCE Resource,
227 IN DISPATCHER_HEADER *DispatcherObject,
228 IN PTHREAD_STRUCT ThrdStruct
229 ) {
230 KIRQL oldIrql;
231 ULONG ResourceWaitCount = 0;
232
233 Resource->ContentionCount++;
234
235 while (KeWaitForSingleObject(DispatcherObject,Executive,KernelMode,FALSE,&DLDpTimeout) == STATUS_TIMEOUT) {
236 KeAcquireSpinLock(&Resource->SpinLock, &oldIrql);
237 if (++ResourceWaitCount>DLDpResourceTimeoutCount) {
238 // May be deadlock?
239 ResourceWaitCount = 0;
240
241 if (DLDProcessResource(Resource, ThrdStruct,DLD_MAX_REC_LEVEL)) {
242 UDFPrint((" which thread %x has tried to acquire at (BugCheckId:%x:Line:%d)\n",
243 ThrdStruct->ThreadId,
244 ThrdStruct->BugCheckId,
245 ThrdStruct->Line
246 ));
247 BrutePoint();
248 }
249 }
250 // Priority boosts
251 // .....
252 // End of priority boosts
253 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
254 }
255
256 }
257
258
259
260
DLDpAcquireResourceExclusiveLite(IN PERESOURCE Resource,IN ERESOURCE_THREAD Thread,IN KIRQL oldIrql,IN ULONG BugCheckId,IN ULONG Line)261 VOID DLDpAcquireResourceExclusiveLite(
262 IN PERESOURCE Resource,
263 IN ERESOURCE_THREAD Thread,
264 IN KIRQL oldIrql,
265 IN ULONG BugCheckId,
266 IN ULONG Line
267 ) {
268 KIRQL oldIrql2;
269
270 if (!(Resource->ExclusiveWaiters)) {
271
272 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
273 KeAcquireSpinLock(&Resource->SpinLock, &oldIrql2);
274
275 // If ExclusiveWaiters Event not yet allocated allocate new one
276 if (!(Resource->ExclusiveWaiters)) {
277 Resource->ExclusiveWaiters = (PKEVENT)ExAllocatePoolWithTag(NonPagedPool, sizeof(KEVENT),RESOURCE_EVENT_TAG);
278 KeInitializeEvent(Resource->ExclusiveWaiters,SynchronizationEvent,FALSE);
279 }
280 KeReleaseSpinLock(&Resource->SpinLock, oldIrql2);
281 DLDAcquireExclusive(Resource,BugCheckId,Line);
282
283 } else {
284 Resource->NumberOfExclusiveWaiters++;
285
286 PTHREAD_STRUCT ThrdStruct = DLDAllocFindThread(Thread);
287
288
289 // Set WaitingResource for current thread
290 ThrdStruct->WaitingResource = Resource;
291 ThrdStruct->BugCheckId = BugCheckId;
292 ThrdStruct->Line = Line;
293
294 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
295
296 DLDpWaitForResource(Resource,&(Resource->ExclusiveWaiters->Header),ThrdStruct);
297
298 KeAcquireSpinLock(&Resource->SpinLock, &oldIrql);
299
300 ThrdStruct->WaitingResource = NULL;
301 ThrdStruct->ThreadId = 0;
302 ThrdStruct->BugCheckId = 0;
303 ThrdStruct->Line = 0;
304 Resource->OwnerThreads[0].OwnerThread = Thread;
305
306 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
307 }
308 }
309
310
311
312
DLDAcquireExclusive(PERESOURCE Resource,ULONG BugCheckId,ULONG Line)313 VOID DLDAcquireExclusive(PERESOURCE Resource,
314 ULONG BugCheckId,
315 ULONG Line
316 ) {
317
318 KIRQL oldIrql;
319
320 KeAcquireSpinLock(&Resource->SpinLock, &oldIrql);
321
322 ERESOURCE_THREAD Thread = (ERESOURCE_THREAD)PsGetCurrentThread();
323
324 if (!Resource->ActiveCount) goto SimpleAcquire;
325 if ((Resource->Flag & ResourceOwnedExclusive) && Resource->OwnerThreads[0].OwnerThread == Thread) {
326 Resource->OwnerThreads[0].OwnerCount++;
327 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
328 return;
329 }
330
331 DLDpAcquireResourceExclusiveLite(Resource, Thread, oldIrql,BugCheckId,Line);
332 return;
333
334 SimpleAcquire:
335
336 Resource->Flag |= ResourceOwnedExclusive;
337 Resource->ActiveCount = 1;
338 Resource->OwnerThreads[0].OwnerThread = Thread;
339 Resource->OwnerThreads[0].OwnerCount = 1;
340
341 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
342 }
343
344
DLDpFindCurrentThread(IN PERESOURCE Resource,IN ERESOURCE_THREAD Thread)345 POWNER_ENTRY DLDpFindCurrentThread(
346 IN PERESOURCE Resource,
347 IN ERESOURCE_THREAD Thread
348 ) {
349
350 if (Resource->OwnerThreads[0].OwnerThread == Thread) return &(Resource->OwnerThreads[0]);
351 if (Resource->OwnerThreads[1].OwnerThread == Thread) return &(Resource->OwnerThreads[1]);
352
353 POWNER_ENTRY LastEntry, CurrentEntry, FirstEmptyEntry = NULL;
354 if (!(Resource->OwnerThreads[1].OwnerThread)) FirstEmptyEntry = &(Resource->OwnerThreads[1]);
355
356 CurrentEntry = Resource->OwnerTable;
357 LastEntry = &(Resource->OwnerTable[Resource->OwnerThreads[0].TableSize]);
358
359 while (CurrentEntry != LastEntry) {
360 if (CurrentEntry->OwnerThread == Thread) {
361 PCHAR CurrentThread = (PCHAR)PsGetCurrentThread();
362 *((PULONG)(CurrentThread + 0x136)) = CurrentEntry - Resource->OwnerTable;
363 return CurrentEntry;
364 }
365 if (!(CurrentEntry->OwnerThread)) {
366 FirstEmptyEntry = CurrentEntry;
367 }
368 CurrentEntry++;
369 }
370 if (FirstEmptyEntry) {
371 PCHAR CurrentThread = (PCHAR)PsGetCurrentThread();
372 *((PULONG)(CurrentThread + 0x136)) = FirstEmptyEntry - Resource->OwnerTable;
373 return FirstEmptyEntry;
374 } else {
375 // Grow OwnerTable
376
377
378 USHORT OldSize = Resource->OwnerThreads[0].TableSize;
379 USHORT NewSize = 3;
380 if (OldSize) NewSize = OldSize + 4;
381 POWNER_ENTRY NewEntry = (POWNER_ENTRY)ExAllocatePoolWithTag(NonPagedPool, sizeof(OWNER_ENTRY)*NewSize,RESOURCE_TABLE_TAG);
382 RtlZeroMemory(NewEntry,sizeof(OWNER_ENTRY)*NewSize);
383 if (Resource->OwnerTable) {
384 RtlMoveMemory(NewEntry,Resource->OwnerTable,sizeof(OWNER_ENTRY)*OldSize);
385 ExFreePool(Resource->OwnerTable);
386 }
387 Resource->OwnerTable = NewEntry;
388
389 PCHAR CurrentThread = (PCHAR)PsGetCurrentThread();
390 *((PULONG)(CurrentThread + 0x136)) = OldSize;
391 Resource->OwnerThreads[0].TableSize = NewSize;
392
393 return &(NewEntry[OldSize]);
394 }
395 }
396
397
DLDAcquireShared(PERESOURCE Resource,ULONG BugCheckId,ULONG Line,BOOLEAN WaitForExclusive)398 VOID DLDAcquireShared(PERESOURCE Resource,
399 ULONG BugCheckId,
400 ULONG Line,
401 BOOLEAN WaitForExclusive)
402 {
403
404 KIRQL oldIrql;
405
406 ERESOURCE_THREAD Thread = (ERESOURCE_THREAD)PsGetCurrentThread();
407 POWNER_ENTRY pOwnerEntry;
408
409 KeAcquireSpinLock(&Resource->SpinLock, &oldIrql);
410
411 if (!Resource->ActiveCount) {
412 Resource->Flag &= ~ResourceOwnedExclusive;
413 Resource->ActiveCount = 1;
414 Resource->OwnerThreads[1].OwnerThread = Thread;
415 Resource->OwnerThreads[1].OwnerCount = 1;
416 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
417 return;
418 }
419
420 if (Resource->Flag & ResourceOwnedExclusive ) {
421 if (Resource->OwnerThreads[0].OwnerThread == Thread) {
422 Resource->OwnerThreads[0].OwnerCount++;
423 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
424 return;
425 }
426
427 pOwnerEntry = DLDpFindCurrentThread(Resource, 0);
428
429 } else {
430 // owned shared by some thread(s)
431
432 pOwnerEntry = DLDpFindCurrentThread(Resource, Thread);
433
434 if (!WaitForExclusive && pOwnerEntry->OwnerThread == Thread) {
435 pOwnerEntry->OwnerCount++;
436 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
437 return;
438 }
439
440 if (!(Resource->NumberOfExclusiveWaiters)) {
441
442 pOwnerEntry->OwnerThread = Thread;
443 pOwnerEntry->OwnerCount = 1;
444 Resource->ActiveCount++;
445 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
446
447 return;
448 }
449 }
450
451 if (!(Resource->SharedWaiters)) {
452 Resource->SharedWaiters = (PKSEMAPHORE)ExAllocatePoolWithTag(NonPagedPool, sizeof(KSEMAPHORE),RESOURCE_SEMAFORE_TAG);
453 KeInitializeSemaphore(Resource->SharedWaiters,0,0x7fffffff);
454 }
455
456 Resource->NumberOfSharedWaiters++;
457
458 PTHREAD_STRUCT ThrdStruct = DLDAllocFindThread(Thread);
459
460
461 // Set WaitingResource for current thread
462 ThrdStruct->WaitingResource = Resource;
463 ThrdStruct->BugCheckId = BugCheckId;
464 ThrdStruct->Line = Line;
465
466 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
467
468 DLDpWaitForResource(Resource,&(Resource->SharedWaiters->Header),ThrdStruct);
469
470 KeAcquireSpinLock(&Resource->SpinLock, &oldIrql);
471
472 pOwnerEntry = DLDpFindCurrentThread(Resource, Thread);
473 pOwnerEntry->OwnerThread = Thread;
474 pOwnerEntry->OwnerCount = 1;
475
476 ThrdStruct->WaitingResource = NULL;
477 ThrdStruct->ThreadId = 0;
478 ThrdStruct->BugCheckId = 0;
479 ThrdStruct->Line = 0;
480
481 KeReleaseSpinLock(&Resource->SpinLock, oldIrql);
482
483 return;
484
485 }
486