Tại sao cần phải cấp phát vùng nhớ cho 1 node mới trong linked list

#1

Em có đoạn code sau đây

#include<stdio.h>
struct t_node
{
	int item;
	struct t_node *next;
};
typedef struct t_node *Node;
struct collection
{
	Node head;
};
typedef struct collection collect;
void AddToCollection(collect *c, int item)
{
	int arr[3];
	Node new; // CASE 1 khong ra kq gi
	//Node new = &arr;	CASE 2 in ra 10
	//Node new = malloc(sizeof(struct t_node));// CASE 3 in ra 10
	new->item = item;
	new->next = c->head;
	c->head = new;
}
int main()
{
	collect h;
	int a = 10;
	AddToCollection(&h, 10);
	printf("%d",h.head->item);
}

Em không hiểu sao nếu không cấp phát thì sẽ không in được ra kết quả gì ạ? Mong anh chị hỗ trợ

#2

biến local sẽ được tự động thu hồi sau khi ra khỏi phạm vi của biến local đó. Do arr là biến local của hàm AddToCollection nên sau khi hàm này chạy xong arr sẽ được thu hồi, phần tử trong collection c trỏ vào vùng nhớ đã được thu hồi thì khi truy cập vùng nhớ đó sẽ dẫn tới undefined behavior :V

vùng nhớ được cấp phát động thì ko được tự động thu hồi nên nó sống mãi tới khi có lệnh thu hồi nó hoặc tới khi chương trình kết thúc nếu ko có lệnh thu hồi.

đừng tưởng trong C ko có thu hồi bộ nhớ tự động nha :V biến local toàn được thu hồi sau khi ra khỏi phạm vi của biến đó hết đó :V :V

bổ sung/đính chính là trong C thu hồi theo kiểu đơn giản nha :V Nếu 1 biến ko trỏ tới vùng nhớ nào khác được cấp phát động thì nó thu hồi sạch hết, còn có con trỏ trỏ tới vùng nhớ được cấp phát động thì nó thu hồi thiếu các vùng nhớ đó. Ví dụ:

struct A {
  int a1[10];
  double a2;
  char a3[20];
  char* a4;
};

struct B {
  char b1[40];
  A b2[50];
};

struct C {
  char c1[20];
  int* c2;
};

void f() {
  struct B b;
  for (int i = 0; i < 50; ++i) b.b2[i].a4 = b.b1;
  // tuy b2 có con trỏ nhưng nó trỏ tới vùng nhớ ko được cấp phát động nên ko có vấn đề gì
} // b được thu hồi sạch sẽ vì cả B và A ko có cấp phát động gì

void g() {
  C c;
  c.c2 = malloc(sizeof(int));
} // c được thu hồi nhưng chỉ thu hồi 20 char của c1 và 1 con trỏ c2
  // ko thu hồi vùng nhớ mà c2 trỏ tới, ở đây c2 lại trỏ tới vùng nhớ
  // được cấp phát động nên thu hồi bộ nhớ ko sạch, có leak.
3 Likes
#3

Nhưng tại sao ở case 2 Node new = &arr; thì vẫn in ra bằng 10 được ạ

#4

xui thôi em, hên thì nó seg fault đó :V Em thử build debug/release rồi chạy 10 lần mỗi cái xem :V

3 Likes
#5

Nhưng mà em truyền tham chiếu địa chị của h vào mà anh

#6 
Node new = &arr;

thì new trỏ tới arr là biến local int arr[3] mà. Sau đó em gán c->head = new nghĩa là h.head sẽ trỏ tới arr[3] này.

mảng arr[3] sẽ bị thu hồi khi ra khỏi hàm AddToCollection, nên truy cập h.head->item là truy cập tới vùng nhớ arr[3] đã bị thu hồi đó nên sẽ bị undefined behavior, nghĩa là chuyện gì cũng có thể xảy ra. In ra 10 cũng có thể, seg fault cũng có thể :V Em muốn viết code chạy 1 tỷ lần đúng y 1 tỷ lần hay 1 tỷ lần có 10 lần bị lỗi :V

image
image348×561 10.7 KB

a chạy code nó in ra số “ngẫu nhiên” ko nè: https://rextester.com/PSKE75612

đáng lẽ phải seg fault, nó in ra ngẫu nhiên thế này biết đâu mà debug :V :V đó cũng là 1 cái kém của C :V vì nó cần tốc độ cao nên nó ko check lỗi truy cập vùng nhớ đã được giải phóng mà để cho hệ điều hành xử lý cái truy cập vùng nhớ bị giải phóng này :V

3 Likes
#7

Em cũng hơi hiểu ý anh nói rồi mà em dùng dev c nó ra 10

image
image1366×768 98.5 KB

#8

thì kệ dev c :V hoặc tốt hơn là bỏ dev c chứ sao :V :V

có thể thêm flag -fsanitize=address vào compiler cho nó check nhưng compiler cũ thì ko có flag này :V

hay em thử addtocollection 10 lần số 11 22 33 44 … rồi in ra tất cả các phần tử trong h xem, bảo đảm ko đúng hết

đây a bị báo lỗi đây:

image
image543×901 23.2 KB

cấp phát động thì ok:

image
image533×879 23.1 KB

có -fsanitize=address:

================================================================
==1==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffedf0c2dd8 at pc 0x000000401235 bp 0x7ffedf0c2d80 sp 0x7ffedf0c2d78
WRITE of size 8 at 0x7ffedf0c2dd8 thread T0
    #0 0x401234 in AddToCollection /app/example.c:20
    #1 0x401234 in main /app/example.c:28
    #2 0x7f63896580b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x240b2)
    #3 0x4012dd in _start (/app/output.s+0x4012dd)

Address 0x7ffedf0c2dd8 is located in stack of thread T0 at offset 72 in frame
    #0 0x4010ff in main /app/example.c:25

  This frame has 2 object(s):
    [32, 40) 'h' (line 26)
    [64, 76) 'arr' (line 15) <== Memory access at offset 72 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /app/example.c:20 in AddToCollection
Shadow bytes around the buggy address:
  0x10005be10560: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be10570: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be10580: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be10590: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be105a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10005be105b0: 00 00 f1 f1 f1 f1 00 f2 f2 f2 00[04]f3 f3 00 00
  0x10005be105c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be105d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be105e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be105f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005be10600: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==1==ABORTING

nó báo lỗi memory access ở biến ‘arr’ ngay :V :V
tên lỗi là “stack-buffer-overflow”, nghĩa là nó truy cập vùng nhớ nằm ngoài (overflow) stack :V

ủa hình như ko phải :V :V nó báo lỗi này là do xử lý int[3] như là struct t_node, nếu sửa lại là

struct t_node arr;

thì nó ko báo lỗi nữa, có fsanitize=address cũng ko thấy báo lỗi :V :V :V

nhưng nếu sửa code lại thành

#include<stdio.h>
struct t_node
{
	int item;
	struct t_node *next;
};
typedef struct t_node *Node;
struct collection
{
	Node head;
};
typedef struct collection collect;
void AddToCollection(collect *c, int item)
{
	struct t_node arr;
	//Node new; // CASE 1 khong ra kq gi
	Node new = &arr;	//CASE 2 in ra 10
	//Node new = malloc(sizeof(struct t_node));// CASE 3 in ra 10
	new->item = item;
	new->next = c->head;
	c->head = new;
}

int main()
{
	collect h;
	int a = 10;
	AddToCollection(&h, 10);
	AddToCollection(&h, 11);
	AddToCollection(&h, 22);
	AddToCollection(&h, 33);
	AddToCollection(&h, 44);
	printf("%d",h.head->item);
	printf("%d",h.head->next->item);
	printf("%d",h.head->next->next->item);
	printf("%d",h.head->next->next->next->item);
	printf("%d",h.head->next->next->next->next->item);
}

nó cũng chạy ko báo lỗi nhưng trên godbolt nó in ra 4444444444 :V còn ở rextester thì nó vẫn báo lỗi invalid memory reference :V

chứng tỏ 1 vài OS nó ko kiểm tra stack hay sao í :V biến arr local tuy bị thu hồi nhưng giá trị nó chứa lúc trước khi bị thu hồi vẫn ko bị thay đổi sau khi thu hồi.

edit nữa: =]] nãy thả flag -g nó ko báo lỗi, nhưng để flag -O2 nó lại báo lỗi mới lạ :V :V

================================================================
==1==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7ffe26a60060 at pc 0x00000040121e bp 0x7ffe26a60010 sp 0x7ffe26a60008
READ of size 4 at 0x7ffe26a60060 thread T0
    #0 0x40121d in main /app/example.c:29
    #1 0x7f8708ec50b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x240b2)
    #2 0x4012dd in _start (/app/output.s+0x4012dd)

Address 0x7ffe26a60060 is located in stack of thread T0 at offset 64 in frame
    #0 0x4010ff in main /app/example.c:25

  This frame has 2 object(s):
    [32, 40) 'h' (line 26)
    [64, 80) 'arr' (line 15) <== Memory access at offset 64 is inside this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)

lần này thì báo đúng lỗi “stack-use-after-scope” nghĩa là sử dụng biến trên stack sau khi đã ra khỏi phạm vi (đã bị thu hồi)

3 Likes
#9

em đang bị confused quá anh ạ. Tại giờ em nhớ lại kiểu hàm swap truyền tham chiếu

void swap(int *a, int *b){
 int tmp = *a; 
 *a = *b;
 *b = tmp;
}

thì nó lại swap đc

#10

vì *b = tmp là nó gán giá trị của tmp chứ đâu phải gán địa chỉ của biến tmp :V

3 Likes
#11

à rồi em hiểu rồi anh ạ tại phần này nhiều biến quá em loạn mấu chốt là c->head = new; anh nhỉ nên nó khác swap

#12

ờm :V dễ loạn lắm :V :V

hay mở excel ra cho dễ hình dung =]] ô A1 chứa giá trị 10 chẳng hạn thì 10 là giá trị còn A1 là địa chỉ =] gán head = &arr thì đồng nghĩa gán head = A1, còn *b = tmp kia là gán *b = 10.

3 Likes
#13

vậy anh cho em hỏi chút ạ nếu không cấp phát bộ nhớ động thì đơn giản là mình chỉ cần cho biến new trỏ đến 1 biến global là được hả anh

#14

global được nhưng 1 collection có 10 phần tử chả lẽ 10 pt cùng trỏ tới 1 biến global :V

cái em nghĩ là như kiểu “static” linked list nghĩa là dslk biết trước số lượng phần tử, thì có thể tạo cấp phát động 1 lần cái mảng N phần tử cho dslk này luôn, ko cần cấp phát N lần mỗi lần 1 phần tử :V

1 Like
#15

Tại thầy em đang yêu cầu không được dùng cấp phát động để quản lý 20 phần tử dùng linked list. Vậy em tạo 1 mảng 20 phần tử global đc không anh.

#16

ờm được :V mà tốt hơn là để mảng 20 phần tử đó trong struct collection luôn

struct collection {
  struct t_node arr[20];
  Node head;
};

thì dslk này có thể liên kết arr[0] -> arr[10] -> arr[19] -> arr[1] -> ... -> NULL cũng được :V

1 Like
#17

Em chưa hiểu ý anh đoạn này lắm.

#18

Chắc có gì để em thử làm xem sao. Chắc lúc đó mới dễ hình dung hơn

#19

a code vd luôn cho :V do khó giải thích chắc đọc code dễ hình dung hơn :V

#include<stdio.h>

typedef struct t_node
{
	int item;
	struct t_node *next;
} node_t;

typedef node_t * p_node;
    
typedef struct t_collection
{
    node_t arr[20];
	p_node head;
    int size;
} collection_t;

void AddToCollection(collection_t *c, int item)
{
    if (c->size >= sizeof(c->arr)) {
        perror("Collection can only hold up to 20 elements");
        exit(1);
    }
	p_node new = &c->arr[c->size];
    ++c->size;
	new->item = item;
	new->next = c->head;
	c->head = new;
}

int main()
{
	collection_t h;
    h.head = NULL;
    h.size = 0;
    
	int a = 10;
	AddToCollection(&h, 11);
	AddToCollection(&h, 22);
	AddToCollection(&h, 33);
	AddToCollection(&h, 44);
    
	printf("%d",h.head->item);
	printf("%d",h.head->next->item);
	printf("%d",h.head->next->next->item);
	printf("%d",h.head->next->next->next->item);
}

p_node new = &c->arr[c->size]; là new trỏ tới phần tử thứ size trong arr, size khởi tạo là 0 nghĩa là phần tử đầu tiên trong arr. Sau đó tăng size lên 1 đơn vị nghĩa là số phần tử trong c tăng lên 1 đơn vị do đang add thêm 1 phần tử vào c :V Do cố định 20 phần tử nên thêm

    if (c->size >= sizeof(c->arr)) {
        perror("Collection can only hold up to 20 elements");
        exit(1);
    }

để kiểm tra trước khi thêm phần tử vào :V Nếu ko muốn dừng chương trình sớm thì có thể sửa void AddToCollection thành int AddToCollection trả về 1 biến int, giá trị 0 nghĩa là ko add được thêm phần tử, 1 là add thành công 1 phần tử chẳng hạn rồi để ở dưới xử lý trường hợp ko add được thêm phần tử :V

khai báo biến arr[20] thuộc Collection thì bảo đảm các phần tử trong Collection h chỉ ra khỏi scope khi h ra khỏi scope, ko bị lỗi truy cập use-after-scope kia nữa :V

3 Likes
#20

Dạ thank anh ạ. Nhờ anh chỉ mà em hiểu thêm nhiều về con trỏ, hàm và dslk ạ!

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?