我有一个函数shortestPath(),它是Dijkstra算法的修改实现,用于我正在为我的comp2类工作的棋盘游戏AI。我已经通过网站和使用gdb和valgrind我确切地知道在哪里段故障发生(实际上知道,几个小时前),但无法找出什么未定义的行为或逻辑错误是导致问题。
发生问题的函数在10x左右被调用,并按预期工作,直到它与GDB发生分段故障:"读取变量错误:无法访问内存"和valgrind:"无效读取大小为8"
正常情况下这就足够了,但是我不能解决这个问题。此外,任何一般的建议和提示都很感激…谢谢!
GDB: https://gist.github.com/mckayryan/b8d1e9cdcc58dd1627ea
Valgrind: https://gist.github.com/mckayryan/8495963f6e62a51a734f
下面是发生分段错误的函数:
static void processBuffer (GameView currentView, Link pQ, int *pQLen,
LocationID *buffer, int bufferLen, Link prev,
LocationID cur)
{
//printLinkIndex("prev", prev, NUM_MAP_LOCATIONS);
// adds newly retrieved buffer Locations to queue adding link types
appendLocationsToQueue(currentView, pQ, pQLen, buffer, bufferLen, cur);
// calculates distance of new locations and updates prev when needed
updatePrev(currentView, pQ, pQLen, prev, cur); <--- this line here
qsort((void *) pQ, *pQLen, sizeof(link), (compfn)cmpDist);
// qsort sanity check
int i, qsortErr = 0;
for (i = 0; i < *pQLen-1; i++)
if (pQ[i].dist > pQ[i+1].dist) qsortErr = 1;
if (qsortErr) {
fprintf(stderr, "loadToPQ: qsort did not sort succesfully");
abort();
}
}
和函数,在调用它之后,一切都崩溃了:
static void appendLocationsToQueue (GameView currentView, Link pQ,
int *pQLen, LocationID *buffer,
int bufferLen, LocationID cur)
{
int i, c, conns;
TransportID type[MAX_TRANSPORT] = { NONE };
for (i = 0; i < bufferLen; i++) {
// get connection information (up to 3 possible)
conns = connections(currentView->gameMap, cur, buffer[i], type);
for (c = 0; c < conns; c++) {
pQ[*pQLen].loc = buffer[i];
pQ[(*pQLen)++].type = type[c];
}
}
}
所以我认为指针被覆盖到错误的地址,但在GDB中大量打印后,情况似乎并非如此。我还通过对所讨论的变量进行读/写来查看触发故障的变量,并且它们都在appendLocationsToQueue()之后执行,而不是在此之前(或在该函数的末尾)。
下面是剩下的相关代码:shortestPath ():
Link shortestPath (GameView currentView, LocationID from, LocationID to, PlayerID player, int road, int rail, int boat)
{
if (!RAIL_MOVE) rail = 0;
// index of locations that have been visited
int visited[NUM_MAP_LOCATIONS] = { 0 };
// current shortest distance from the source
// the previous node for current known shortest path
Link prev;
if(!(prev = malloc(NUM_MAP_LOCATIONS*sizeof(link))))
fprintf(stderr, "GameView.c: shortestPath: malloc failure (prev)");
int i;
// intialise link data structure
for (i = 0; i < NUM_MAP_LOCATIONS; i++) {
prev[i].loc = NOWHERE;
prev[i].type = NONE;
if (i != from) prev[i].dist = INF;
else prev[i].dist = LAST;
}
LocationID *buffer, cur;
// a priority queue that dictates the order LocationID's are checked
Link pQ;
int bufferLen, pQLen = 0;
if (!(pQ = malloc(MAX_QUEUE*sizeof(link))))
fprintf(stderr, "GameView.c: shortestPath: malloc failure (pQ)");
// load initial location into queue
pQ[pQLen++].loc = from;
while (!visited[to]) {
// remove first item from queue into cur
shift(pQ, &pQLen, &cur);
if (visited[cur]) continue;
// freeing malloc from connectedLocations()
if (cur != from) free(buffer);
// find all locations connected to
buffer = connectedLocations(currentView, &bufferLen, cur,
player, currentView->roundNum, road,
rail, boat);
// mark current node as visited
visited[cur] = VISITED;
// locations from buffer are used to update priority queue (pQ)
// and distance information in prev
processBuffer(currentView, pQ, &pQLen, buffer, bufferLen, prev,
cur);
}
free(buffer);
free(pQ);
return prev;
}
所有参数在这行之前看起来都很好:
appendLocationsToQueue(currentView, pQ, pQLen, buffer, bufferLen, cur);
并且在它告诉我您已经踩上(将0x7fff00000000
写入)$rbp
寄存器后变得不可用(所有局部变量和参数在没有优化的情况下构建时都相对于$rbp
)。
您可以在调用appendLocationsToQueue
之前和之后用print $rbp
在GDB中确认这一点($rbp
应该在给定函数中始终具有相同的值,但会发生变化)。
假设这是真的,只有几种可能发生这种情况的方式,最可能的方式是appendLocationsToQueue
中的堆栈缓冲区溢出(或它调用的其他东西)。
您应该能够使用地址杀毒器(g++ -fsanitize=address ...
)相当容易地找到这个错误。
在GDB中查找溢出也相当容易:进入appendLocationsToQueue
,然后进入watch -l *(char**)$rbp
, continue
。当您的代码覆盖$rbp
保存位置时,应该触发观察点。