歡迎大家移步 我的博客 查看原文。 1. 前言 上機時遇到如下 C++ 代碼 ( C 代碼)： //刪除帶頭結點的多項式單鏈表中繫數為 0 項 void DelZero(PolyNode *&L) { PolyNode *pre = L, *p = pre->next; while (p != NU ...
目錄
歡迎大家移步 我的博客 查看原文。
1. 前言
上機時遇到如下 C++ 代碼 ( C 代碼)：
//刪除帶頭結點的多項式單鏈表中繫數為 0 項
void DelZero(PolyNode *&L)
{
PolyNode *pre = L, *p = pre->next;
while (p != NULL)
{
if (p->coef == 0.0)
{
pre->next = p->next;
free(p);
}
pre = p;
p = p->next;
}
}
來源：《數據結構教程 (第 5 版) 上機實驗指導》(李春葆主編) 第二章實驗題 10
當 if 語句執行後，指針 p 指向的記憶體已經被釋放，接著又執行 p = p->next，使用了指向已經被釋放了的記憶體的指針。那麼，這樣的用法是否正確呢？
2. 正文
free(p) 後 p = p->next 能否正確執行，要看編譯器的具體實現，不同的編譯器可能會產生不同的結果。上述程式我在 VSCode 中使用 gcc 編譯能正常運行，但使用 VS2022 的 MSVC 編譯後不能正常運行。而且即便能夠正常運行，這種用法也會導致程式出現漏洞。
2.1. “分配” 與 “釋放”
在調用記憶體分配函數 (\(malloc、calloc\) 等) 在堆區分配一塊記憶體後，這塊記憶體會被標記為 已使用，確保在之後的記憶體分配中不會將這塊已經分配過的記憶體進行二次分配。
而調用 free 函數將記憶體釋放後，這塊記憶體便會被標記為 未使用，在往後的記憶體分配中這塊記憶體便能再次被分配了。而 free 後記憶體中的值是否改變這要看編譯器的具體實現，不同編譯器可能具有不同的實現方式。
2.2. 運行測試
2.2.1. VSCode 下使用 gcc 編譯
在調用 free 函數釋放動態分配的記憶體後，指針 p 仍然指向這塊已經被釋放的記憶體 (指針變數 p 中仍然保存著這塊記憶體的地址)，而使用 gcc 進行編譯，被釋放的記憶體中原有的內容並未被覆蓋 (前言中給出的代碼對應的程式是這樣，一會兒會舉個反例)，執行 p = p->next 後 p 指向單鏈表的下一個結點，因此程式能正常運行而不會錯誤中止。雖然能正常運行，但程式存在漏洞。
參見 2.3 程式漏洞測試
2.2.2. VS2022 下使用 MSVC 編譯
在 VS2022 下使用 MSVC 進行編譯，第一次執行 free(p) 前 p 指向的記憶體中的內容如下：
第一次執行 free(p) 後，p 指向的記憶體中的內容被覆蓋 (紅色部分)，這時再執行 p = p->next 便會產生錯誤，使程式卡死在這一步。
2.3. 程式漏洞測試
我們舉一個例子來說明在能正常運行的前提下 (gcc 編譯)，前言中的程式存在的漏洞。
- 根據多項式 \(x^9 + 0x^5 + 0x^3 + 3x^2 + 0x\) 創建一個多項式單鏈表 (如下, 這裡為了方便只寫出繫數)。
pre和p初始指向如圖。
- 此時
p != NULL，進行第 \(1\) 次迴圈，p->coef == 1，兩指針向後移。
- 此時
p != NULL，進行第 \(2\) 次迴圈，p->coef == 0, 刪除p指向的結點後兩指針向後移。整理一下這一步得到的單鏈表。
- 此時
p != NULL，進行第 \(3\) 次迴圈，p->coef == 0, 這時本應刪除p指向的結點後兩指針向後移，但此時pre指針指向的是已經被釋放的結點，pre->next = p->next改變的是已釋放結點的next域指向，從而導致 漏刪 了一個本應刪除的結點。
- 此時
p != NULL，進行第 \(4\) 次迴圈，p->coef != 0, 兩指針向後移。
- 此時
p != NULL，進行第 \(5\) 次迴圈，p->coef == 0, 刪除p指向的結點後兩指針向後移。
- 此時
p == NULL，迴圈結束，最終得到的單鏈表如圖。
測試代碼如下，這裡列印出 free(p) 執行前後指針變數 p 中內容以及 p 指向的記憶體中的內容。
//程式漏洞測試代碼 (僅列出與漏洞有關代碼)
void DelZero(PolyNode *&L) //刪除繫數為零的項
{
PolyNode *pre = L, *p = pre->next;
while (p != NULL)
{
if (p->coef == 0.0)
{
pre->next = p->next;
#ifdef DEBUG
printf("free(p) 前, p = %p, p->coef = %f, "
"p->exp = %d, p->next = %p\n", p, p->coef, p->exp, p->next);
#endif
free(p);
#ifdef DEBUG
printf("free(p) 後, p = %p, p->coef = %f, "
"p->exp = %d, p->next = %p\n\n", p, p->coef, p->exp, p->next);
#endif
p = pre->next;
continue;
}
pre = p;
p = p->next;
}
}
int main()
{
PolyArray a[] = {{1, 9}, {0, 5}, {0, 3}, {3, 2}, {0, 1}};
PolyNode *L;
int n = 5;
CreatePolyR(L, a, 5);
printf("原多項式為: ");
DispPoly(L);
printf("刪除繫數為 0 項後為: \n\n");
DelZero(L);
DispPoly(L);
DestroyPoly(L);
return 0;
}
執行結果如圖所示：
可以看到，free(p) 操作執行前後，指針變數 p 中內容以及 p 指向的記憶體中的內容均未發生改變，所以在 free(p) 後執行 p = p->next 編譯器並不會報錯，但卻給程式帶來了邏輯上的漏洞。
2.4. 程式漏洞修複
//刪除帶頭結點的多項式單鏈表中繫數為 0 項 (Beta)
void DelZero(PolyNode *&L)
{
PolyNode *pre = L, *p = pre->next;
while (p != NULL)
{
if (p->coef == 0.0)
{
pre->next = p->next;
free(p);
+ p = pre->next;
+ continue;
}
pre = p;
p = p->next;
}
}
漏洞修複後運行結果如圖：
2.5. 附加測試
在 VSCode 下使用 gcc 編譯以下 C 代碼：
//測試 1
#include <stdio.h>
#include <malloc.h>
int main()
{
int *p = (int *) malloc (sizeof(int));
*p = 9;
printf("p = %p\n", p);
printf("free(p) 前 *p = %d\n", *p);
printf("-----------------\n");
free(p);
printf("p = %p\n", p);
printf("free(p) 後 *p = %d\n", *p);
printf("------------------------\n");
*p = 9;
printf("p = %p\n", p);
printf("free(p) 後再執行 *p = 9, 此時 *p = %d\n\n", *p);
return 0;
}
測試 \(1\) 運行結果如下：
//測試 2
#include <stdio.h>
#include <malloc.h>
int main()
{
char *q = (char *) malloc (20 * sizeof(char));
q = "Hello World";
printf("q = %p\n", q);
printf("free(q) 前 q 指向記憶體中的內容為: %s\n", q);
printf("--------------------------------------------\n");
free(q);
printf("q = %p\n", q);
printf("free(q) 後 q 指向記憶體中的內容為: %s\n", q);
printf("--------------------------------------------\n");
q = "Hello World";
printf("q = %p\n", q);
printf("free(q) 後再執行 q = \"Hello World\", 此時 q 指向記憶體中的內容為: %s\n\n", q);
return 0;
}
測試 \(2\) 運行結果如下：
可以看到，測試 \(1\) 中 free(p) 後 p 指向記憶體中的內容發生了改變，而 測試 \(2\) 中 free(q) 後 q 指向記憶體中的內容並沒有發生變化，這又是為什麼呢？難道 gcc 編譯器對於是否覆蓋 free 後的記憶體中的內容還有什麼規則嗎？這個疑問暫時得不到解答，留待日後弄清。
3. 總結
調用 free 函數釋放記憶體後，原先指向這塊記憶體的指針 p 仍然指向這塊記憶體，不過這時候的指向已經是不合法的了。如果這塊記憶體被分配用作其他用途，這時再次引用指針 p (當做 free(p) 之前的用途來使用) 就有可能引發未知的錯誤 (前言中的程式儘管在 gcc 編譯下能夠正常運行，並且記憶體釋放後也沒有再分配，但引用指向已釋放記憶體的指針 p 還是使程式產生了漏洞)。所以，在 free(p) 後，最好不要出現使用指向已釋放記憶體的指針 p 的情況，必要時應將 p 置為 NULL。
參考資料
本文來自博客園，作者：chenxin5，轉載請註明原文鏈接：https://www.cnblogs.com/chenxin5/p/16576905.html
