drivers/filesystems/udfs/dldetect.cpp

   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 }