#At file:///C:/Work/bzr/Merge/mysql-6.0-falcon-team/
2823 Kevin Lewis 2008-09-10
Improvements to the Deadlock Detector in SyncHandler.
Keep track of whether a location locks a SyncObject in
exclusive of Shared mode.
Show that in the putput.
Eliminate possible deadlocks where the second SyncObject
occurs both before and after the first, but only within
the same call stack. This is OK as long as the lock does
not start with Shared and rises up to Exclusive.
modified:
storage/falcon/SyncHandler.cpp
storage/falcon/SyncHandler.h
storage/falcon/SyncObject.cpp
=== modified file 'storage/falcon/SyncHandler.cpp'
--- a/storage/falcon/SyncHandler.cpp 2008-09-03 21:49:18 +0000
+++ b/storage/falcon/SyncHandler.cpp 2008-09-10 21:30:08 +0000
@@ -143,7 +143,7 @@ SyncHandler::~SyncHandler(void)
#endif
}
-void SyncHandler::addLock(SyncObject *syncObj, const char* locationName)
+void SyncHandler::addLock(SyncObject *syncObj, const char* locationName, LockType type)
{
#ifdef USE_FALCON_SYNC_HANDLER
if (syncObj == &syncObject)
@@ -158,7 +158,7 @@ void SyncHandler::addLock(SyncObject *sy
SyncThreadInfo *thd = addThread(thread->threadId);
SyncObjectInfo *soi = addSyncObject(syncObj->getName());
- SyncLocationInfo *loc = addLocation(locationName, soi);
+ SyncLocationInfo *loc = addLocation(locationName, soi, type);
addToThread(thd, loc);
#endif
@@ -297,29 +297,30 @@ void SyncHandler::showSyncObjects(void)
Log::debug(" %s\n", soi->name);
}
-SyncLocationInfo *SyncHandler::findLocation(const char* locationName, int slot)
+SyncLocationInfo *SyncHandler::findLocation(const char* locationName, LockType type, int slot)
{
for (SyncLocationInfo *loc = locations[slot]; loc; loc = loc->collision)
{
- if (loc->name == locationName)
+ if ((loc->name == locationName) && (loc->type == type))
return loc;
}
return NULL;
}
-SyncLocationInfo *SyncHandler::addLocation(const char* locationName, SyncObjectInfo *soi)
+SyncLocationInfo *SyncHandler::addLocation(const char* locationName, SyncObjectInfo *soi, LockType type)
{
ASSERT(locationName != NULL);
ASSERT(strlen(locationName) != 0);
int slot = JString::hash(locationName, locationHashSize);
- SyncLocationInfo *loc = findLocation(locationName, slot);
+ SyncLocationInfo *loc = findLocation(locationName, type, slot);
if (!loc)
{
loc = new SyncLocationInfo;
loc->name = locationName;
loc->soi = soi;
+ loc->type = type;
loc->collision = locations[slot];
locations[slot] = loc;
if ((++locationCount % 100) == 0)
@@ -339,10 +340,9 @@ void SyncHandler::showLocations(void)
for (int slot = 0; slot < locationHashSize; slot++)
for (SyncLocationInfo *loc = locations[slot]; loc; loc = loc->collision)
- Log::debug(" %s\t%s\n", loc->name, loc->soi->name);
+ Log::debug(" %s\t%s\t%s\n", loc->name, loc->soi->name, (loc->type == Exclusive ? "Exclusive" : "Shared"));
}
-
void SyncHandler::addToThread(SyncThreadInfo* thd, SyncLocationInfo *loc)
{
// Be sure this soi is only recorded once.
@@ -480,14 +480,16 @@ void SyncHandler::showLocationStacks(voi
int stackHeight = 0;
stackCount++;
for (int n = 0; n < lsi->height - 1; n++)
- Log::debug(" %4d-%03d; %s (%s) ->\n",
+ Log::debug(" %4d-%03d; %s (%s) - %s ->\n",
stackCount, ++stackHeight,
- lsi->loc[n]->name, lsi->loc[n]->soi->name);
+ lsi->loc[n]->name, lsi->loc[n]->soi->name,
+ (lsi->loc[n]->type == Exclusive ? "Exclusive" : "Shared"));
- Log::debug(" %4d-%03d; %s (%s)\n\n",
+ Log::debug(" %4d-%03d; %s (%s) - %s\n\n",
stackCount, ++stackHeight,
lsi->loc[lsi->height - 1]->name,
- lsi->loc[lsi->height - 1]->soi->name);
+ lsi->loc[lsi->height - 1]->soi->name,
+ (lsi->loc[lsi->height - 1]->type == Exclusive ? "Exclusive" : "Shared"));
}
}
@@ -579,6 +581,74 @@ void SyncHandler::validate(void)
if (before[b] == after[c])
addPossibleDeadlock(soi, after[c]);
}
+
+ // Refine the list of possible deadlocks
+ // The second SOI was found before and after the first.
+ // But if that happened on the same stack, it is OK as long as
+ // the two calls do not go from shared up to exclusive.
+ for (a = 0; a < deadlockHashSize; a++)
+ for (DeadlockInfo *dli = possibleDeadlocks[a]; dli; dli = dli->collision)
+ {
+ bool foundBothInOneStack = false;
+ bool foundBefore = false;
+ bool foundAfter = false;
+ bool foundRisingLock = false;
+
+ // Quit seraching stacks when the possibility has been reconfirmed
+
+ for (b = 0; b < stackHashSize; b++)
+ for (LocationStackInfo *lsi = locationStacks[b]; lsi; lsi = lsi->collision)
+ {
+ SyncLocationInfo *reference = NULL;
+ SyncLocationInfo *first = NULL;
+ SyncLocationInfo *second = NULL;
+
+ for (c = 0; c < lsi->height; c++)
+ {
+ if (dli->soi[0] == lsi->loc[c]->soi)
+ reference = lsi->loc[c];
+ else if (dli->soi[1] == lsi->loc[c]->soi)
+ {
+ if ((first == NULL) && (reference == NULL))
+ first = lsi->loc[c];
+ else if ((first != NULL) && (reference != NULL))
+ {
+ second = lsi->loc[c];
+ if ((first->type == Shared) && (second->type == Exclusive))
+ {
+ foundRisingLock = true;
+ lsi->hasRisingLockTypes = true;
+ }
+ }
+ }
+ }
+
+ if (reference)
+ {
+ if (first)
+ {
+ foundBefore = true;
+ if (second)
+ {
+ if (foundRisingLock)
+ foundAfter = true;
+ else
+ // It's not really a possible deadlock
+ foundBothInOneStack = true;
+ }
+ }
+ else if (second)
+ foundAfter = true;
+ }
+ }
+
+ // Is this still a possible deadlock?
+ if (foundBothInOneStack && !(foundBefore && foundAfter) && !foundRisingLock)
+ {
+ // Take this possible deadlock out of the list.
+ removePossibleDeadlock(dli);
+ }
+ }
}
void SyncHandler::addPossibleDeadlock(SyncObjectInfo *soi1, SyncObjectInfo *soi2)
@@ -591,6 +661,7 @@ void SyncHandler::addPossibleDeadlock(Sy
dli->soi[0] = soi1;
dli->soi[1] = soi2;
+ dli->isPossible = true;
// Now calulate the hash number and slot.
// This hash algorithm must return the same slot for two SyncObjectInfo *
@@ -614,6 +685,17 @@ void SyncHandler::addPossibleDeadlock(Sy
delete dli;
}
+void SyncHandler::removePossibleDeadlock(DeadlockInfo* dli)
+{
+ int slot = dli->hash % deadlockHashSize;
+
+ for (DeadlockInfo* stack = possibleDeadlocks[slot]; stack; stack = stack->collision)
+ {
+ if (stack == dli)
+ dli->isPossible = false;
+ }
+}
+
#define FOUND_FIRST 1
#define FOUND_SECOND 2
#define FOUND_BOTH 3
@@ -623,41 +705,43 @@ void SyncHandler::showPossibleDeadlockSt
int possibleDeadlockCount = 0;
for (a = 0; a < deadlockHashSize; a++)
for (DeadlockInfo *dli = possibleDeadlocks[a]; dli; dli = dli->collision)
- possibleDeadlockCount++;
+ if (dli->isPossible)
+ possibleDeadlockCount++;
Log::debug("\n== SyncHandler has found %d possible deadlocks ==\n", possibleDeadlockCount);
for (a = 0; a < deadlockHashSize; a++)
for (DeadlockInfo *dli = possibleDeadlocks[a]; dli; dli = dli->collision)
- {
- int stackCount = 0;
- Log::debug("\n=== Possible Deadlock; %s and %s ===\n Stacks =", dli->soi[0]->name, dli->soi[1]->name);
-
- // Reference all call stacks with these two SyncObjects.
+ if (dli->isPossible)
+ {
+ int stackCount = 0;
+ Log::debug("\n=== Possible Deadlock; %s and %s ===\n Stacks =", dli->soi[0]->name, dli->soi[1]->name);
- for (b = 0; b < stackHashSize; b++)
- for (LocationStackInfo *lsi = locationStacks[b]; lsi; lsi = lsi->collision)
- {
- // Does this location stack have both SyncObjects?
+ // Reference all call stacks with these two SyncObjects.
- int numFound = 0;
- for (c = 0; c < lsi->height; c++)
+ for (b = 0; b < stackHashSize; b++)
+ for (LocationStackInfo *lsi = locationStacks[b]; lsi; lsi = lsi->collision)
{
- if (lsi->loc[c]->soi == dli->soi[0])
- numFound |= FOUND_FIRST;
- else if (lsi->loc[c]->soi == dli->soi[1])
- numFound |= FOUND_SECOND;
- }
+ // Does this location stack have both SyncObjects?
- if (numFound == FOUND_BOTH)
- {
- if (stackCount && ((stackCount % 10) == 0))
- Log::debug("\n ");
- stackCount++;
- Log::debug(" %d", lsi->count);
+ int numFound = 0;
+ for (c = 0; c < lsi->height; c++)
+ {
+ if (lsi->loc[c]->soi == dli->soi[0])
+ numFound |= FOUND_FIRST;
+ else if (lsi->loc[c]->soi == dli->soi[1])
+ numFound |= FOUND_SECOND;
+ }
+
+ if (numFound == FOUND_BOTH)
+ {
+ if (stackCount && ((stackCount % 10) == 0))
+ Log::debug("\n ");
+ stackCount++;
+ Log::debug(" %d", lsi->count);
+ }
}
- }
- Log::debug("\n");
- }
+ Log::debug("\n");
+ }
}
#endif
=== modified file 'storage/falcon/SyncHandler.h'
--- a/storage/falcon/SyncHandler.h 2008-09-03 21:49:18 +0000
+++ b/storage/falcon/SyncHandler.h 2008-09-10 21:30:08 +0000
@@ -43,6 +43,7 @@ struct SyncLocationInfo
{
JString name;
SyncObjectInfo *soi;
+ LockType type;
SyncLocationInfo *collision;
};
@@ -61,6 +62,7 @@ struct LocationStackInfo
int height;
int hash;
int count;
+ bool hasRisingLockTypes;
LocationStackInfo *collision;
};
@@ -68,6 +70,7 @@ struct DeadlockInfo
{
SyncObjectInfo *soi[2];
int hash;
+ bool isPossible;
DeadlockInfo *collision;
};
@@ -84,7 +87,7 @@ public:
SyncHandler(void);
virtual ~SyncHandler(void);
- void addLock(SyncObject *syncObj, const char *locationName);
+ void addLock(SyncObject *syncObj, const char *locationName, LockType type);
void delLock(SyncObject *syncObj);
void dump(void);
@@ -98,8 +101,8 @@ private:
SyncObjectInfo * findSyncObject(const char* syncObjectName, int slot);
SyncObjectInfo * addSyncObject(const char* syncObjectName);
void showSyncObjects(void);
- SyncLocationInfo * findLocation(const char* locationName, int slot);
- SyncLocationInfo * addLocation(const char* locationName, SyncObjectInfo *soi);
+ SyncLocationInfo * findLocation(const char* locationName, LockType type, int slot);
+ SyncLocationInfo * addLocation(const char* locationName, SyncObjectInfo *soi, LockType type);
void showLocations(void);
LocationStackInfo * findStack(LocationStackInfo* stk, int slot);
void addStack(SyncThreadInfo* thd);
@@ -113,6 +116,7 @@ private:
void validate(void);
void addPossibleDeadlock(SyncObjectInfo *soi1, SyncObjectInfo *soi2);
+ void removePossibleDeadlock(DeadlockInfo* dli);
void showPossibleDeadlockStacks(void);
SyncObject syncObject;
=== modified file 'storage/falcon/SyncObject.cpp'
--- a/storage/falcon/SyncObject.cpp 2008-09-03 21:49:18 +0000
+++ b/storage/falcon/SyncObject.cpp 2008-09-10 21:30:08 +0000
@@ -148,7 +148,7 @@ void SyncObject::lock(Sync *sync, LockTy
#ifdef USE_FALCON_SYNC_HANDLER
SyncHandler *syncHandler = getFalconSyncHandler();
if (sync && syncHandler)
- syncHandler->addLock(this, location);
+ syncHandler->addLock(this, location, type);
#endif
#endif
@@ -320,7 +320,7 @@ void SyncObject::lock(Sync *sync, LockTy
#ifdef USE_FALCON_SYNC_HANDLER
SyncHandler *syncHandler = getFalconSyncHandler();
if (sync && syncHandler)
- syncHandler->addLock(this, location);
+ syncHandler->addLock(this, location, type);
#endif
#endif
| Thread |
|---|
| • bzr commit into mysql-6.0-falcon branch (klewis:2823) | Kevin Lewis | 10 Sep |
