#At file:///C:/Work/bzr/Merge/mysql-6.0-falcon-team/
2869 Kevin Lewis 2008-10-15
Latest updates to the Deadlock Predictor.
Adds the type of lock and better reporting and analysis.
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-10-16 02:59:09 +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,31 @@ 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 +341,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.
@@ -476,19 +477,34 @@ void SyncHandler::showLocationStacks(voi
for (int slot = 0; slot < stackHashSize; slot++)
for (LocationStackInfo *lsi = locationStacks[slot]; lsi; lsi = lsi->collision)
- {
- int stackHeight = 0;
- stackCount++;
- for (int n = 0; n < lsi->height - 1; n++)
- Log::debug(" %4d-%03d; %s (%s) ->\n",
- stackCount, ++stackHeight,
- lsi->loc[n]->name, lsi->loc[n]->soi->name);
-
- Log::debug(" %4d-%03d; %s (%s)\n\n",
- stackCount, ++stackHeight,
- lsi->loc[lsi->height - 1]->name,
- lsi->loc[lsi->height - 1]->soi->name);
- }
+ showLocationStack(lsi);
+}
+
+void SyncHandler::showLocationStack(int stackNum)
+{
+ for (int slot = 0; slot < stackHashSize; slot++)
+ for (LocationStackInfo *lsi = locationStacks[slot]; lsi; lsi = lsi->collision)
+ if (lsi->count == stackNum)
+ {
+ showLocationStack(lsi);
+ return;
+ }
+}
+
+void SyncHandler::showLocationStack(LocationStackInfo *lsi)
+{
+ int stackHeight = 0;
+ for (int n = 0; n < lsi->height - 1; n++)
+ Log::debug(" %4d-%03d; %s (%s) - %s ->\n",
+ lsi->count, ++stackHeight,
+ lsi->loc[n]->name, lsi->loc[n]->soi->name,
+ (lsi->loc[n]->type == Exclusive ? "Exclusive" : "Shared"));
+
+ Log::debug(" %4d-%03d; %s (%s) - %s\n\n",
+ lsi->count, ++stackHeight,
+ lsi->loc[lsi->height - 1]->name,
+ lsi->loc[lsi->height - 1]->soi->name,
+ (lsi->loc[lsi->height - 1]->type == Exclusive ? "Exclusive" : "Shared"));
}
DeadlockInfo* SyncHandler::findDeadlock(DeadlockInfo* dli, int slot)
@@ -527,12 +543,10 @@ void SyncHandler::validate(void)
{
// Make a list of all SyncObjects that must occur before and after and this.
- SyncObjectInfo *before[1000];
- memset(before, 0, sizeof(before));
+ memset(soi->beforeList, 0, sizeof(soi->beforeList));
int beforeCount = 0;
- SyncObjectInfo *after[1000];
- memset(after, 0, sizeof(after));
+ memset(soi->afterList, 0, sizeof(soi->afterList));
int afterCount = 0;
// search each location stack for this soi, make a list of
@@ -544,29 +558,35 @@ void SyncHandler::validate(void)
for (c = 0; c < lsi->height; c++)
if (soi == lsi->loc[c]->soi)
{
+
+ // Record the SyncObjects that occur before this
+
for (d = 0; d < c; d++)
{
for (e = 0; e < beforeCount; e++)
- if (before[e] == lsi->loc[d]->soi)
+ if (soi->beforeList[e] == lsi->loc[d]->soi)
break;
if (e == beforeCount)
- before[beforeCount++] = lsi->loc[d]->soi;
+ soi->beforeList[beforeCount++] = lsi->loc[d]->soi;
ASSERT(lsi->loc[d]->soi);
- ASSERT(beforeCount < 1000);
+ ASSERT(beforeCount < beforeAfterSize);
}
+
+ // Record the SyncObjects that occur after this
+
for (d = c + 1; d < lsi->height; d++)
{
for (e = 0; e < afterCount; e++)
- if (after[e] == lsi->loc[d]->soi)
+ if (soi->afterList[e] == lsi->loc[d]->soi)
break;
if (e == afterCount)
- after[afterCount++] = lsi->loc[d]->soi;
+ soi->afterList[afterCount++] = lsi->loc[d]->soi;
ASSERT(lsi->loc[d]->soi);
- ASSERT(afterCount < 1000);
+ ASSERT(afterCount < beforeAfterSize);
}
}
}
@@ -574,10 +594,85 @@ void SyncHandler::validate(void)
// Make sure none of the SyncObjects in before are also in after.
for (b = 0; b < beforeCount; b++)
- if (soi != before[b])
+ if (soi != soi->beforeList[b])
for (c = 0; c < afterCount; c++)
- if (before[b] == after[c])
- addPossibleDeadlock(soi, after[c]);
+ if (soi->beforeList[b] == soi->afterList[c])
+ addPossibleDeadlock(soi, soi->afterList[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 foundOneBeforeTwo = false;
+ bool foundTwoBeforeOne = false;
+ bool foundRisingLock = false;
+
+ for (b = 0; b < stackHashSize; b++)
+ for (LocationStackInfo *lsi = locationStacks[b]; lsi; lsi = lsi->collision)
+ {
+ int firstOneNum = 0;
+ int lastOneNum = 0;
+ int firstTwoNum = 0;
+ int lastTwoNum = 0;
+
+ for (c = 0; c < lsi->height; c++)
+ {
+ if (dli->soi[0] == lsi->loc[c]->soi)
+ if (firstOneNum)
+ {
+ lastOneNum = c + 1;
+ if ( (lsi->loc[firstOneNum - 1]->type == Shared)
+ && (lsi->loc[c]->type == Exclusive))
+ {
+ foundRisingLock = true;
+ lsi->hasRisingLockTypes = true;
+ }
+ }
+ else
+ firstOneNum = c + 1;
+
+ else if (dli->soi[1] == lsi->loc[c]->soi)
+ if (firstTwoNum)
+ {
+ lastTwoNum = c + 1;
+ if ( (lsi->loc[firstTwoNum - 1]->type == Shared)
+ && (lsi->loc[c]->type == Exclusive))
+ {
+ foundRisingLock = true;
+ lsi->hasRisingLockTypes = true;
+ }
+ }
+ else
+ firstTwoNum = c + 1;
+ }
+
+ if (firstOneNum && firstTwoNum)
+ {
+ if (firstOneNum < lastTwoNum && lastTwoNum < lastOneNum)
+ foundBothInOneStack = true;
+ else if (firstTwoNum < lastOneNum && lastOneNum < lastTwoNum)
+ foundBothInOneStack = true;
+ else if (firstOneNum < firstTwoNum)
+ foundOneBeforeTwo = true;
+ else if (firstTwoNum < firstOneNum)
+ foundTwoBeforeOne = true;
+
+ }
+ }
+
+ // Is this still a possible deadlock?
+ if ( foundBothInOneStack
+ && !(foundOneBeforeTwo && foundTwoBeforeOne)
+ && !foundRisingLock)
+ {
+ // Take this possible deadlock out of the list.
+ removePossibleDeadlock(dli);
+ }
}
}
@@ -591,6 +686,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,50 +710,98 @@ 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
+#define ONE_TWO 1
+#define TWO_ONE 2
void SyncHandler::showPossibleDeadlockStacks(void)
{
- int a,b,c;
+ int a;
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);
+ if (dli->isPossible)
+ {
+ Log::debug("\n=== Possible Deadlock===\n");
+ showPossibleDeadlockStack(dli, ONE_TWO);
+ showPossibleDeadlockStack(dli, TWO_ONE);
+ }
+}
+
+void SyncHandler::showPossibleDeadlockStack(DeadlockInfo *dli, int showOrder)
+{
+ LocationStackInfo *sampleLsi1 = NULL;
+ LocationStackInfo *sampleLsi2 = NULL;
+ int stackCount = 0;
+ if (showOrder == ONE_TWO)
+ Log::debug(" %s before %s\n", dli->soi[0]->name, dli->soi[1]->name);
+ else
+ Log::debug(" %s before %s\n", dli->soi[1]->name, dli->soi[0]->name);
- // Reference all call stacks with these two SyncObjects.
+ // Find call stacks containing these two SyncObjects.
- for (b = 0; b < stackHashSize; b++)
- for (LocationStackInfo *lsi = locationStacks[b]; lsi; lsi = lsi->collision)
- {
- // Does this location stack have both SyncObjects?
+ for (int b = 0; b < stackHashSize; b++)
+ for (LocationStackInfo *lsi = locationStacks[b]; lsi; lsi = lsi->collision)
+ {
+ // Does this location stack have both SyncObjects?
- 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;
- }
+ int numFound = 0;
+ int order = 0;
+ for (int c = 0; c < lsi->height; c++)
+ {
+ if (lsi->loc[c]->soi == dli->soi[0])
+ {
+ numFound |= FOUND_FIRST;
+ if (!order)
+ order = ONE_TWO;
+ }
+ else if (lsi->loc[c]->soi == dli->soi[1])
+ {
+ numFound |= FOUND_SECOND;
+ if (!order)
+ order = TWO_ONE;
+ }
+ }
- if (numFound == FOUND_BOTH)
- {
- if (stackCount && ((stackCount % 10) == 0))
- Log::debug("\n ");
- stackCount++;
- Log::debug(" %d", lsi->count);
- }
+ if ( (numFound == FOUND_BOTH) && (order == showOrder) )
+ {
+ if (stackCount == 0)
+ {
+ sampleLsi1 = lsi;
+ Log::debug(" Stacks =", dli->soi[0]->name, dli->soi[1]->name);
}
- Log::debug("\n");
+ else if ((stackCount % 10) == 0)
+ Log::debug("\n ");
+
+ stackCount++;
+ Log::debug(" %d", lsi->count);
+ sampleLsi2 = lsi;
+ }
}
+
+ Log::debug("\n");
+ if (sampleLsi1)
+ showLocationStack(sampleLsi1);
+ if (sampleLsi2)
+ showLocationStack(sampleLsi2);
}
#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-10-16 02:59:09 +0000
@@ -28,6 +28,7 @@ static const int locationHashSize = 503;
static const int threadHashSize = 100;
static const int stackHashSize = 1000;
static const int deadlockHashSize = 100;
+static const int beforeAfterSize = 60;
static const int syncStackSize = 20;
struct SyncObjectInfo
@@ -36,6 +37,10 @@ struct SyncObjectInfo
SyncObjectInfo *prev;
SyncObjectInfo *next;
SyncObjectInfo *collision;
+ SyncObjectInfo *beforeList[beforeAfterSize];
+ SyncObjectInfo *afterList[beforeAfterSize];
+ SyncObjectInfo *before;
+ SyncObjectInfo *after;
bool multiple;
};
@@ -43,6 +48,7 @@ struct SyncLocationInfo
{
JString name;
SyncObjectInfo *soi;
+ LockType type;
SyncLocationInfo *collision;
};
@@ -61,6 +67,7 @@ struct LocationStackInfo
int height;
int hash;
int count;
+ bool hasRisingLockTypes;
LocationStackInfo *collision;
};
@@ -68,6 +75,7 @@ struct DeadlockInfo
{
SyncObjectInfo *soi[2];
int hash;
+ bool isPossible;
DeadlockInfo *collision;
};
@@ -84,7 +92,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,12 +106,14 @@ 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);
void showLocationStacks(void);
+ void showLocationStack(int stackNum);
+ void showLocationStack(LocationStackInfo *lsi);
void countLocationStacks(void);
DeadlockInfo * findDeadlock(DeadlockInfo* dli, int slot);
@@ -113,7 +123,9 @@ private:
void validate(void);
void addPossibleDeadlock(SyncObjectInfo *soi1, SyncObjectInfo *soi2);
+ void removePossibleDeadlock(DeadlockInfo* dli);
void showPossibleDeadlockStacks(void);
+ void showPossibleDeadlockStack(DeadlockInfo *dli, int showOrder);
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-10-16 02:59:09 +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-team branch (klewis:2869) | Kevin Lewis | 16 Oct |
