آموزش لیست پیوندی در زبان C و مدیریت حافظه پویا (Heap)

آموزش – برنامه نویسی

19 بازدید

۱۴۰۵-۰۳-۲۶

10 دقیقه

نویسنده: Alireza Abbasi
درباره نویسنده: ---

لیست پیوندی

حال که از هیپ (heap) و قابلیت ذخیره‌سازی داده‌ها در آن بهره‌مندیم، می‌توانیم از یک ساختار داده اولیه به نام « لیست پیوندی یک‌طرفه» استفاده کنیم که نسبت به آرایه چندین مزیت دارد. لیست پیوندی اندازه ثابتی ندارد و در آن درج و حذف داده‌ها بسیار سریع‌تر از آرایه انجام می‌شود. (البته جستجو در آرایه‌ها سریع‌تر است).

فرض کنید می‌خواهیم تعدادی اسم را برای یک دفترچه تلفن ذخیره کنیم. مشکل اینجاست که تعداد اسم‌ها را نمی‌دانیم. همچنین ممکن است هر زمان اسمی اضافه یا حذف شود. برای سیستم‌های امبدد ساده یک راه‌حل، ایجاد آرایه‌ای برای ذخیره اسامی است.

اگر فضای آرایه تمام شود، به کاربر اعلام می‌کنیم که دیگر نمی‌توان اسم جدیدی اضافه کرد. اما لیست پیوندی راه‌حل بهتری است، به شرطی که حافظه کافی و heap در اختیار داشته باشیم. در یک سیستم امبدد با منابع بسیار محدود، هیچ‌کدام از این دو را نداریم.

هر عنصر از فهرست ما که گره (node) نامیده می‌شود، از heap اختصاص می‌یابد. برای ردیابی این عناصر، یک اشاره گر به اولین گره داریم. اولین گره، اشاره گری به گره دوم دارد و به همین ترتیب تا رسیدن به آخرین گره که اشاره گر آن NULL است و انتهای فهرست را نشان می‌دهد. تعداد گره‌ها ثابت نیست. هر زمان که به گره جدیدی نیاز داشته باشیم، آن را از heap اختصاص می‌دهیم.

در زیر ساختار لیست پیوندی آمده است:

#define NAME_SIZE 20 // Max number of characters in a
name
/**
* A node in the linked list
*/
struct linkedList {
struct linkedList* next; // Next node
char name[NAME_SIZE]; // Name of the node
};

#define NAME_SIZE 20 // Max number of characters in a

name

/**

* A node in the linked list

struct linkedList {

struct linkedList* next; // Next node

char name[NAME_SIZE]; // Name of the node

};

در این ساختار، next اشاره گری به گره بعدی در لیست یا NULL در صورت رسیدن به انتهای لیست را نشان می‌دهد. آرایه name نیز برای ذخیره حداکثر 20 کاراکتر از نام گره استفاده می‌شود.

نمودار لیست پیوندی یک‌طرفه (شکل 1-33)

لیست‌های پیوندی یک‌طرفه، روشی بسیار ساده برای ذخیره تعداد نامحدودی از آیتم‌ها در heap ارائه می‌دهند.

اضافه کردن یک گره

برای اضافه کردن یک گره (فرض کنید با نام “fred”) به لیست، ابتدا باید آن را ایجاد کنیم. در کد، ما متغیر newNode را طوری تنظیم می کنیم که به گره تازه ساخته شده اشاره کند. حالا حافظه شبیه شکل 2-33 می شود.

گره جدید ایجاد شد (شکل 2-33)

شکل 2-33 لیست پیوندی ما (بدون “fred”) و گره جدیدی که برای “fred” اختصاص داده ایم را نشان می‌دهد. سپس، لینک بعدی گره جدید خود را طوری تنظیم می‌کنیم که به ابتدای لیست اشاره کند (به شکل 3-33 مراجعه کنید).

نشانگر بعدی گره جدید به ابتدای لیست اشاره می‌کند. (شکل 3-33)

آخرین مرحله اختصاص دادن theList = newNode است، که نشانگر را به ابتدای لیست، اولین گره جدید ما منتقل می‌کند (به شکل 4-33 مراجعه کنید).

انتقال گره جدید به ابتدای لیست (شکل 4-33)

کد زیر اضافه کردن گره جدید به ابتدای لیست را نشان می دهد:

static void addName(void)
{
printf("Enter word to add: ");
char line[NAME_SIZE]; // Input line
if (fgets(line, sizeof(line), stdin) == NULL)
return;
if (line[strlen(line)-1] == '\n')
line[strlen(line)-1] = '\0';
// Get a new node.
struct linkedList* newNode = malloc(sizeof(*newNode));
strncpy(newNode->name, line, sizeof(newNode->name)-1);
newNode->name[sizeof(newNode->name)-1] = '\0';
newNode->next = theList;
theList = newNode;
}

static void addName(void)

{

printf("Enter word to add: ");

char line[NAME_SIZE]; // Input line

if (fgets(line, sizeof(line), stdin) == NULL)

return;

if (line[strlen(line)-1] == '\n')

line[strlen(line)-1] = '\0';

// Get a new node.

struct linkedList* newNode = malloc(sizeof(*newNode));

strncpy(newNode->name, line, sizeof(newNode->name)-1);

newNode->name[sizeof(newNode->name)-1] = '\0';

newNode->next = theList;

theList = newNode;

}

اضافه کردن یک کلمه به لیست پیوندی

با تعریف یک تابع شروع می‌کنیم، کلیدواژه static نشان می‌دهد که این تابع فقط برای کدهای داخل این فایل قابل دسترسی است. ابتدا کلمه‌ای که می‌خواهیم اضافه کنیم را درخواست کرده و با استفاده از تابع fgets آن را دریافت می‌کنیم. این تابع به شکل زیر عمل می‌کند:

fgets(array, size, file)

1	fgets(array, size, file)

این تابع یک خط را از فایل خوانده و آن را داخل آرایه قرار می‌دهد. size تعداد بایت‌هایی است که باید داخل آرایه قرار گیرد همچنین شامل کاراکتر پایان رشته (0\) نیز می‌شود. در این مثال، آرایه line (خط ورودی) و فایل stdin (استاندارد ورودی یا به عبارتی ترمینال) است. اگر fgets مقدار NULL را برگرداند، به دلیل خطا یا تمام شدن اطلاعات قادر به خواندن stdin نیستیم. در این نقطه انصراف داده و برمی‌گردیم زیرا هیچ کلمه‌ای دریافت نکرده‌ایم.

تابع fgets حداکثر size-1 کاراکتر را می‌خواند، زیرا همیشه یک کاراکتر پایان رشته (0\) را در آرایه قرار می‌دهد. اگر خط وارد شده کوتاه تر از size باشد، کل خط شامل خط جدید داخل بافر قرار می‌گیرد. اگر طولانی‌تر باشد، ورودی قطع می‌شود.

نمی توانیم روی وجود کاراکتر خط جدید در بافر حساب کنیم و البته به آن نیازی نداریم. اگر آخرین کاراکتر در رشته (با استفاده از تابع strlen که تعداد کاراکترهای رشته را برمی‌گرداند، پیدا می‌شود) یک خط جدید باشد، با تغییر آن به null (‘\0’) آن را حذف می‌کنیم. سپس حافظه گره جدید را اختصاص داده و با کپی کردن line در فیلد name، گره آن را پر می‌کنیم.

شاید برای شما مفید باشد:

بررسی بهترین زبان، کامپایلر و محیط‌های برنامه نویسی مختلف برای میکروکنترلر AVR

تابع strncpy آرگومان دوم (line) را در آرگومان اول (newNode->name) کپی می‌کند، اما تنها تعداد کاراکترهای مشخص شده توسط آرگومان سوم را کپی می‌کند. اگر داده‌ای که باید کپی شود (line) کاراکترهای بیشتری نسبت به پارامتر size داشته باشد، تعداد کاراکترهای کپی شده را محدود می‌کند و کاراکتر پایان رشته (0\) را در انتها وارد نمی‌کند، بنابراین برای اطمینان، به صورت دستی یک کاراکتر پایان رشته در انتهای آرایه name اضافه می‌کنیم.

ما newNode را تنظیم می‌کنیم تا به گره اول اشاره کند، و سپس theList را برمی‌داریم و آن را تنظیم می‌کنیم تا به گره جدید اشاره کند، همانطور که در شکل‌های 4-33 و 3-33 نشان داده شده است.

چاپ کردن لیست پیوندی

چاپ کردن یک لیست پیوندی قوانین ساده‌ای دارد. در اینجا یک مثال آورده شده است:

for (const struct linkedList* curNode = 1 theList;
2 curNode != NULL;
3 curNode = curNode->next){
printf("%s, ", curNode->name);
}

for (const struct linkedList* curNode = 1 theList;

2 curNode != NULL;

3 curNode = curNode->next){

printf("%s, ", curNode->name);

}

ما با اولین گره شروع می‌کنیم، آن را چاپ می‌کنیم . (1)

و سپس به سراغ گره بعدی می‌رویم.(3)

ما به کار خود ادامه می‌دهیم تا زمانی که لیست تمام شود (2).

در این مثال، مقداردهی اولیه حلقه for، شرط پایان و دستور تکرار روی سه خط تقسیم شده‌اند. این کد یک کامای اضافی در انتهای لیست اضافه می‌کند، اما مطمئن هستم که می‌توانید راهی برای رفع آن پیدا کنید.

(شکل 5-33)

به دلیل اینکه لیست ما یک ساختار داده ساده است، چاپ کردن آن ساده است و انعطاف‌پذیری حلقه for در C باعث می‌شود به راحتی کل لیست را پیمایش کنیم.

حذف یک گره از لیست پیوندی

برای حذف یک گره، ابتدا لیست را پیمایش می‌کنیم و گره موردنظر را پیدا می‌کنیم. سپس، گره را حذف کرده و گره قبلی را به گره بعدی متصل می‌کنیم. کد مربوط به پیمایش لیست به این شکل است:

static void deleteWord(void)
{
printf("Enter word to delete: ");
char line[NAME_SIZE]; // Input line
if (fgets(line, sizeof(line), stdin) == NULL)
return;
if (line[strlen(line)-1] == '\n')
line[strlen(line)-1] = '\0';
struct linkedList* prevNode = NULL; // Pointer to
previous node
1 for (struct linkedList* curNode = theList;
curNode != NULL;
curNode = curNode->next) {
2 if (strcmp(curNode->name, line) == 0) {
if (prevNode == NULL) {
3 theList = curNode->next;
} else {
4 prevNode->next = curNode->next;
}
5 free(curNode);
curNode = NULL;
return;
}
6 prevNode = curNode;
}
printf("WARNING: Node not found %s\n", line);
}

static void deleteWord(void)

{

printf("Enter word to delete: ");

char line[NAME_SIZE]; // Input line

if (fgets(line, sizeof(line), stdin) == NULL)

return;

if (line[strlen(line)-1] == '\n')

line[strlen(line)-1] = '\0';

struct linkedList* prevNode = NULL; // Pointer to

previous node

1 for (struct linkedList* curNode = theList;

curNode != NULL;

curNode = curNode->next) {

2 if (strcmp(curNode->name, line) == 0) {

if (prevNode == NULL) {

3 theList = curNode->next;

} else {

4 prevNode->next = curNode->next;

}

5 free(curNode);

curNode = NULL;

return;

}

6 prevNode = curNode;

}

printf("WARNING: Node not found %s\n", line);

}

ما از یک حلقه for استفاده می‌کنیم، مشابه کاری که برای چاپ کردن انجام دادیم.(1)

اما به جای چاپ گره، با استفاده از تابع strcmp بررسی می‌کنیم که آیا این گره موردنظر ما است یا خیر.(2)

این تابع اگر رشته‌ها یکسان باشند، عدد ۰ را برمی‌گرداند.

اگر گره موردنظر نباشد، نشانگر به گره قبلی را به روز رسانی می‌کنیم(که برای حذف به آن نیاز داریم) و با استفاده از حلقه for به سراغ گره بعدی می‌رویم. اگر گره را پیدا کنیم (مثلا “Joe”)، prevNode به “sam” و curNode به “Joe” اشاره خواهد کرد، همانطور که در شکل 6-33 نشان داده شده است. (6)

سپس، لینک بین “sam” و “mac” را برقرار می‌کنیم و بدین ترتیب گره “Joe” را دور می‌زنیم. در نهایت، گره را با آزاد کردن حافظه آن و تنظیم نشانگر به null حذف می‌کنیم.(5)

این کار تا زمانی که prevNode تنظیم شده باشد، به درستی عمل می‌کند.(4)

اگر بخواهیم اولین گره (“sam”) را حذف کنیم، باید نشانگر به لیست را تغییر دهیم تا از گره حذف شده عبور کند.(3)

حذف گره (شکل 6-33)

جمع‌بندی

لیستینگ زیر یک برنامه خط کامند کوچک است که برای ویرایش و چاپ یک لیست پیوندی به صورت تعاملی طراحی شده است.

linked.c
/**
* Demonstrate a singly linked list.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define NAME_SIZE 20 // Max number of characters in a
name
/**
* A node in the linked list
*/
struct linkedList {
struct linkedList* next; // Next node
char name[NAME_SIZE]; // Name of the node
};
// The linked list of words
static struct linkedList* theList = NULL;
/**
* Add a name to the linked list.
*/
static void addName(void)
{
printf("Enter word to add: ");
char line[NAME_SIZE]; // Input line
if (fgets(line, sizeof(line), stdin) == NULL)
return;
if (line[strlen(line)-1] == '\n')
line[strlen(line)-1] = '\0';
// Get a new node.
struct linkedList* newNode = malloc(sizeof(*newNode));
strncpy(newNode->name, line, sizeof(newNode->name)-1);
newNode->name[sizeof(newNode->name)-1] = '\0';
newNode->next = theList;
theList = newNode;
}
/**
* Delete a word from the list.
*/
static void deleteWord(void)
{
printf("Enter word to delete: ");
char line[NAME_SIZE]; // Input line
if (fgets(line, sizeof(line), stdin) == NULL)
return;
if (line[strlen(line)-1] == '\n')
line[strlen(line)-1] = '\0';
struct linkedList* prevNode = NULL; // Pointer to the
previous node
for (struct linkedList* curNode = theList;
curNode != NULL;
curNode = curNode->next) {
if (strcmp(curNode->name, line) == 0) {
if (prevNode == NULL) {
theList = curNode->next;
} else {
prevNode->next = curNode->next;
}
free(curNode);
curNode = NULL;
return;
}
prevNode = curNode;
}
printf("WARNING: Node not found %s\n", line);
}
/**
* Print the linked list.
*/
static void printList(void)
{
// Loop over each node in the list.
for (const struct linkedList* curNode = theList;
curNode != NULL;
curNode = curNode->next) {
printf("%s, ", curNode->name);
}
printf("\n");
}
int main()
{
while (true) {
printf("a-add, d-delete, p-print, q-quit: ");
char line[100]; // An input line
if (fgets(line, sizeof(line), stdin) == NULL)
break;
switch (line[0]) {
case 'a':
addName();
break;
case 'd':
deleteWord();
break;
case 'p':
printList();
break;
case 'q':
exit(8);
default:
printf(
"ERROR: Unknown command %c\n",
line[0]);
break;
}
}
}

100

101

102

103

104

105

106

107

linked.c

/**

* Demonstrate a singly linked list.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

#define NAME_SIZE 20 // Max number of characters in a

name

/**

* A node in the linked list

struct linkedList {

struct linkedList* next; // Next node

char name[NAME_SIZE]; // Name of the node

};

// The linked list of words

static struct linkedList* theList = NULL;

/**

* Add a name to the linked list.

static void addName(void)

{

printf("Enter word to add: ");

char line[NAME_SIZE]; // Input line

if (fgets(line, sizeof(line), stdin) == NULL)

return;

if (line[strlen(line)-1] == '\n')

line[strlen(line)-1] = '\0';

// Get a new node.

struct linkedList* newNode = malloc(sizeof(*newNode));

strncpy(newNode->name, line, sizeof(newNode->name)-1);

newNode->name[sizeof(newNode->name)-1] = '\0';

newNode->next = theList;

theList = newNode;

}

/**

* Delete a word from the list.

static void deleteWord(void)

{

printf("Enter word to delete: ");

char line[NAME_SIZE]; // Input line

if (fgets(line, sizeof(line), stdin) == NULL)

return;

if (line[strlen(line)-1] == '\n')

line[strlen(line)-1] = '\0';

struct linkedList* prevNode = NULL; // Pointer to the

previous node

for (struct linkedList* curNode = theList;

curNode != NULL;

curNode = curNode->next) {

if (strcmp(curNode->name, line) == 0) {

if (prevNode == NULL) {

theList = curNode->next;

} else {

prevNode->next = curNode->next;

}

free(curNode);

curNode = NULL;

return;

}

prevNode = curNode;

}

printf("WARNING: Node not found %s\n", line);

}

/**

* Print the linked list.

static void printList(void)

{

// Loop over each node in the list.

for (const struct linkedList* curNode = theList;

curNode != NULL;

curNode = curNode->next) {

printf("%s, ", curNode->name);

}

printf("\n");

}

int main()

{

while (true) {

printf("a-add, d-delete, p-print, q-quit: ");

char line[100]; // An input line

if (fgets(line, sizeof(line), stdin) == NULL)

break;

switch (line[0]) {

case 'a':

addName();

break;

case 'd':

deleteWord();

break;

case 'p':

printList();

break;

case 'q':

exit(8);

default:

printf(

"ERROR: Unknown command %c\n",

line[0]);

break;

}

شاید برای شما مفید باشد:

Goto در آردوینو

برنامه‌ای که یک لیست پیوندی را پیاده سازی می‌کند

کاربر با وارد کردن کامند‌ها، می‌تواند گره‌ها را به لیست اضافه یا از آن حذف کند، لیست را چاپ کند یا از برنامه خارج شود. هنگامی که کاربر گره‌ای را اضافه یا حذف می‌کند، برنامه به طور پویا حافظه را اختصاص می‌دهد یا آزاد می‌کند.

مشکلات حافظه پویا

هنگام استفاده از حافظه پویا در برنامه‌نویسی C، چند خطای رایج ممکن است رخ دهد. در این بخش به بررسی این خطاها و روش‌های جلوگیری از آن‌ها می‌پردازیم.

انباشت حافظه (Memory Leak)

انباشت حافظه زمانی اتفاق می‌افتد که حافظه برای برنامه اختصاص داده شود، اما هرگز آزاد نشود. در اینجا یک مثال آورده شده است:

{
int* dynamicArray; // A dynamic array
// Allocate 100 elements.
dynamicArray = malloc(sizeof(int) * 100);
}

{

int* dynamicArray; // A dynamic array

// Allocate 100 elements.

dynamicArray = malloc(sizeof(int) * 100);

}

در این مثال، هر بار که برنامه این کد را اجرا می‌کند، 400 بایت حافظه جدید برای آرایه dynamicArray اختصاص می‌یابد. اگر برنامه به اندازه کافی اجرا شود، تمام حافظه در دسترس را مصرف کرده و از کار می‌افتد. (در واقع، برنامه به تدریج حافظه زیادی مصرف می‌کند که باعث کند شدن شدید تمام برنامه‌های دیگر می‌شود. این روند تا جایی ادامه پیدا می‌کند که دیگر حافظه کافی برای اجرای روان هیچ برنامه‌ای باقی نمی‌ماند. با این حال، برنامه برای مدت کوتاهی به کار خود ادامه می‌دهد تا اینکه در نهایت حافظه به طور کامل پر شده و برنامه از کار می‌افتد.)

برای جلوگیری از انباشت حافظه، همیشه باید حافظه اختصاص داده شده را با استفاده از تابع free() در زمانی که دیگر به آن نیاز ندارید، آزاد کنید. یک روش خوب برای مدیریت حافظه، استفاده از الگوهای طراحی مناسب و اطمینان از اینکه هر تخصیص حافظه با یک free() متناظر همراه است.

استفاده از اشاره گر بعد از آزاد شدن (Use After Free)

استفاده از یک اشاره گر بعد از اینکه حافظه آن با free() آزاد شده است، می‌تواند منجر به نتایج تصادفی یا بازنویسی حافظه تصادفی شود. بیایید به یک مثال نگاه کنیم:

free(nodePtr);
nextPtr = nodePtr->Next; // Illegal

1 2	free(nodePtr); nextPtr = nodePtr->Next; // Illegal

در این مثال، تابع free ممکن است داده‌های داخلی یا داده‌های دیگر را درون گره‌ای که با nodePtr اشاره شده است، بنویسد. در نتیجه، دسترسی به nodePtr->Next بعد از آزاد شدن آن، غیرمجاز است و مقدار nextPtr تعریف نشده‌ای خواهد داشت.

برای جلوگیری از این مشکل، می‌توانید بعد از آزاد کردن حافظه با free()‌، اشاره گر را روی NULL تنظیم کنید.

free(nodePtr);
nodePtr = NULL;
nextPtr = nodePtr->Next; // Crashes the program

free(nodePtr);

nodePtr = NULL;

nextPtr = nodePtr->Next; // Crashes the program

با تنظیم اشاره گر به NULL، یک رفتار قابل پیش‌بینی برای خطا ایجاد می‌کنیم. در این حالت، تلاش برای دسترسی به nodePtr->Next منجر به خراب شدن برنامه می‌شود که به راحتی قابل تشخیص است.نوشتن

فراتر از مرز حافظه اختصاص یافته

آخرین مشکل حافظه پویا که به آن می‌پردازیم، نوشتن داده فراتر از انتهای یک ساختار است. همانطور که قبلاً دیده‌اید، هیچ چیز شما را مانع نوشتن فراتر از انتهای یک آرایه نمی‌کند. شما می‌توانید همین کار را با حافظه اختصاص یافته انجام دهید:

در این مثال، تلاش برای نوشتن مقدار 10 در theData[10] ، باعث نوشتن در حافظه‌ای می‌شود که برای آرایه theData اختصاص داده نشده است و خطا ایجاد می‌کند.

متأسفانه، زبان سی امکانات مناسبی برای پیشگیری یا یافتن این نوع خطاها ارائه نمی‌دهد. برای این کار به ابزارهای خارجی یا کامپایلرهای ارتقا یافته نیاز است.

Valgrind و GCC Address Sanitizer

مشکلات حافظه به قدری زیاد شده که ابزارهای متعددی برای یافتن آنها ایجاد شده‌است، از جمله Valgrind و GCC address sanitizer.

Valgrind یک ابزار متن‌باز و رایگان برای سیستم‌ عامل‌های لینوکس و مک است. Valgrind برای شناسایی مشکلات زیر طراحی شده است:

انباشت حافظه: زمانی که حافظه به طور کامل آزاد نشده و به مرور زمان اشغال می‌شود.
نوشتن فراتر از انتهای آرایه یا بلوک حافظه اختصاص‌یافته: این اتفاق زمانی رخ می‌دهد که برنامه سعی می‌کند داده‌ای را در حافظه‌ای بنویسد که به آن اختصاص داده نشده است.
استفاده از اشاره گر پس از آزاد شدن: این اتفاق زمانی رخ می‌دهد که برنامه سعی می‌کند از حافظه‌ای استفاده کند که قبلاً آزاد شده است.
تصمیم‌گیری بر اساس مقدار حافظه مقداردهی نشده: این اتفاق زمانی رخ می‌دهد که برنامه بر اساس مقداری از حافظه تصمیم‌گیری می‌کند که هنوز به آن مقداری اختصاص داده نشده است.

Valgrind بر خلاف بسیاری از ابزارهای تحلیل کد که نیازمند کامپایل مجدد کد شما هستند، در مرحله اجرای برنامه عمل می‌کند. به این معنی که شما می‌توانید برنامه خود را به طور عادی کامپایل کنید و سپس از Valgrind برای بررسی و عیب‌یابی آن در حین اجرا استفاده کنید.

شاید برای شما مفید باشد:

اضافه کردن زیرماژول به ماژول اصلی

کد زیر: نمونه برنامه‌ای که حافظه را نشت می‌دهد.

/**
* Leaks memory and uses it badly.
* Generates warnings when compiled.
* Generates errors when run.
*
* Please don't program like this.
*/
#include <stdlib.h>
static void leak(void)
{
char* data = malloc(100);
}
int main()
{
leak();
return (0);
}

/**

* Leaks memory and uses it badly.

* Generates warnings when compiled.

* Generates errors when run.

* Please don't program like this.

#include <stdlib.h>

static void leak(void)

{

char* data = malloc(100);

}

int main()

{

leak();

return (0);

}

یک برنامه نشتی‌دار

نتیجه اجرای این برنامه با استفاده از Valgrind و فعال کردن حداکثر بررسی انباشت حافظه

$ valgrind --leak-check=full ./leaker
--snip--
==14500== 100 bytes in 1 blocks are definitely lost in
loss record 1 of 1
==14500== at 0x4C2FB0F: malloc (in
/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14500== by 0x10865B: leak (leaker.c:12) 1
==14500== by 0x10866B: main (leaker.c:17)
==14500==
==14500== LEAK SUMMARY:
==14500== definitely lost: 100 bytes in 1 blocks
--snip--

$ valgrind --leak-check=full ./leaker

--snip--

==14500== 100 bytes in 1 blocks are definitely lost in

loss record 1 of 1

==14500== at 0x4C2FB0F: malloc (in

/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==14500== by 0x10865B: leak (leaker.c:12) 1

==14500== by 0x10866B: main (leaker.c:17)

==14500==

==14500== LEAK SUMMARY:

==14500== definitely lost: 100 bytes in 1 blocks

--snip--

نتایج Valgrind

از این خروجی می‌توان مشاهده کرد که خط 12، حافظه را دچار انباشت می کند(1).

GCC address sanitizer فقط برای تشخیص انباشت حافظه و نوشتن فراتر از انتهای آرایه یا بلوک حافظه اختصاص‌یافته طراحی شده است. بر خلاف Valgrind، این ابزار در زمان کامپایل عمل می‌کند، بنابراین برای استفاده از آن باید کد خود را با پرچم -fsanitize=address کامپایل کنید. پس از آن، زمانی که برنامه را اجرا می‌کنید، به طور خودکار گزارش را تولید می‌کند، همانطور که در لیست زیر نشان داده شده است.

$ /leaker
==========================================================
=======
==14427==ERROR: LeakSanitizer: detected memory leaks
Direct leak of 100 byte(s) in 1 object(s) allocated from:
#0 0x7f07c712cb50 in __interceptor_malloc
(/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdeb50)
#1 0x5607aef0b7fb in leak
/home/sdo/bare/xx.leaker/leaker.c:15
#2 0x5607aef0b80b in main
/home/sdo/bare/xx.leaker/leaker.c:17
#3 0x7f07c6c7eb96 in __libc_start_main (/lib/x86_64-
linux-gnu/libc.so.6+0x21b96)
SUMMARY: AddressSanitizer: 100 byte(s) leaked in 1
allocation(s).

$ /leaker

==========================================================

=======

==14427==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 100 byte(s) in 1 object(s) allocated from:

#0 0x7f07c712cb50 in __interceptor_malloc

(/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdeb50)

#1 0x5607aef0b7fb in leak

/home/sdo/bare/xx.leaker/leaker.c:15

#2 0x5607aef0b80b in main

/home/sdo/bare/xx.leaker/leaker.c:17

#3 0x7f07c6c7eb96 in __libc_start_main (/lib/x86_64-

linux-gnu/libc.so.6+0x21b96)

SUMMARY: AddressSanitizer: 100 byte(s) leaked in 1

allocation(s).

نتایج address sanitizer

مشکلات حافظه از زمان اولین رایانه‌ها گریبانگیر برنامه‌ها بوده‌اند و یافتن آنها کار دشواری است. address sanitizer یکی از ابزارهایی است که به ما در پیدا کردن این مشکلات کمک می‌کند.