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
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 
64 VOID DLDFree(VOID) {
65 
66     DLDFreePool(DLDThreadTable);
67 
68 }
69 
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 
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
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
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 
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 
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 
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 
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 
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