Cách hoạt động của Heap

korokoro · November 22, 2022, 10:12am

Em chào mọi người,

Hôm trước em có nghỉ trúng bài về Heap trên lớp nên giờ tự coi lại nhưng không biết cách hiểu của em thế này có đúng không?
Như em hiểu thì

data bytes allocated: sẽ luôn là kiểu 8 * n, ví dụ malloc(32) thì nó sẽ là 8*4 = 32
block size: Giả sử của malloc(32) sẽ bằng 40. Vì sao? Em nghĩ tại vì nó sẽ có một byte cho header và một byte cho footer (?)
Block header in hex: Đây chính là phần em còn cấn, em không hiểu tại sao 40 chuyển sang hex phải cộng thêm 1.

Em có thử áp dụng vào một bài tập như hình ảnh bên dưới

(1) Address of the header of the first allocated block: 0x1770
–> Vì sao: Luôn luôn là byte đầu tiên sẽ là header

(2) Length: 16
–> Vì sao: Vì từ 0x00000010 -> 0x00000010 gồm có 4 byte.

(3) User-data can be stored in this block: 8
–> Vì sao: Vì 1 byte dành cho header và 1 byte cho footer

(4) Address returned by malloc( ) when this header was set: 0x1774
–> Vì sao: Em vẫn chưa tìm được nguyên nhân tại sao

(5) Address of the header of the first free block: 0x1798
–> Vì sao: Như bạn em giảng lại thì free block sẽ có value số cuối cùng là even, vì thế nên em chọn 0x1798 mang giá trị 0x00000010

(6) Length (including header and footers): 16

(7) Data could potentially be stored in this block: 8

(8) If this heap uses a simple explicit free list, what is the address of the next free block: Em chọn 0x17d8 vì ở đó giá trị mang số cuối là even.

Theo như cách hiểu của em và áp dụng như thế thì có đúng không, và nếu sai anh chị có thể chỉ dẫn em với được không ạ?

Em cảm ơn.

korokoro · November 22, 2022, 2:13pm

Có anh chị nào rành phần này có thể chỉ dạy em một tí được không ạ :3

drgnz · November 22, 2022, 3:21pm

chỉ thêm 1 header, nhưng vì heap của glibc luôn align theo 8-byte, nên 32+4 = 36 mod 8 = 4 -> phải thêm 4 bytes để thành 8-byte aligned

theo bạn bit cuối cùng để làm gì? nó có bao nhiu giá trị và các giá trị để làm gì?

trả lời được câu trên là hiểu câu này

header có bao nhiêu bytes?

sai rồi. tương tự, bit cuối của header để làm gì?

korokoro · November 23, 2022, 8:32am

Em cảm ơn.
Khi em check ví dụ mà thầy cho thì.
Chẳng hạn malloc(9).
Với nội dung kèm theo như sau
“The memory allocator enforces 8-byte alignment
(i.e., that the allocator will make sure that all blocks have size that’s a multiple of 8), and that headers
and footers are 4 bytes each.” .
Thì em nghĩ cách áp dụng của em đúng chứ ạ :3
vì malloc(9) sẽ cho:

Data byte allocated: 16 (theo nội dung là multiple of 8).
Block size: 16 + 8 (vì như hướng dẫn header và footer mỗi cái 4 byte).
Về block header in hex em vẫn chưa suy nghĩ ra được không biết anh có thể gợi ý giúp em không.
Dựa trên phần nội dung thầy em cho thì nếu em giải câu 1-> 8 vậy có bị lỗi chỗ nào không ạ? Và việc em chọn value có bit cuối even là nơi bắt đầu free block có được không ạ?

Em cảm ơn.

drgnz · November 23, 2022, 8:47am

uhm đúng, mà cách đó không hiệu quả, thường chủ yếu để làm reverse nagivation. mà chắc kết quả lại muốn theo hướng đó. nên nói như bạn cũng được nha

bạn cứ đọc lý thuyết ra rồi mình đi từ đó cho bạn dễ hiểu

korokoro · November 23, 2022, 9:15am

Em cảm ơn anh ạ.
Vậy là nếu em áp dụng theo cách trên thì những câu hỏi mà em trả lời vẫn đúng, chỉ riêng câu 8 em bị sai huh anh?
Tức là việc mà em mặc định last bit even là sai hay là sao ấy ạ.
Còn theo như em hiểu block header in hex chắc thêm 1 để sau free block (?) , hoặc là để transverse lại block cũ :3

drgnz · November 23, 2022, 9:40am

đúng rồi, thêm 1 để đánh dấu là free hay ko. 0 là free, 1 là có. mà cái này bị hơi sai là, đáng lẽ nó phải shift bit. nhưng thay vì shift thì nó thêm 1 vô cái capacity luôn.
một lý do mình có đc giải thích là, vì 8-byte align, nên 3 bit cuối coi như ko sử dụng -> chiếm dụng luôn nên sẽ ko bị ảnh hưởng.

nên khi quét heap trống, thì xem theo header block, nếu header block nào bit cuối là 0 thì block đó đang free -> câu 8 thì ngay block 0x1770 ko có bit 1 set nên đã free rồi. thì coi tiếp next và prev của nó. next của nó đang trỏ vô 0x1798 mới đúng

p/s: nói tới đây thì biết bài bạn sai hết rồi đó

korokoro · November 23, 2022, 9:48am

Nếu giải thích như thế thì em nghĩ em sai hết toàn bộ rồi :>
Để em làm lại

Address of the header of the first allocated block: 0x1780

Lí do: Vì value ở 0x1770 có bit cuối 0, nên đó là phần của free block.

Its length: 24

Lí do: Vì từ 0x1780 đến 0x1794 mới trùng lại value, và tổng cộng thì bao gồm 6 byte nên suy ra là 24 bits

User-data can be stored in this block: 24 - 8 = 16

Lí do: 1 byte cho header, 1 byte cho footer

Address returned by malloc( ) when this header was set: 0x1784

Lí do: Vì 0x1780 là cho header nên return sẽ là byte tiếp theo hay còn gọi là byte đầu tiên trong allocated block (?)

Address of the header of the first free block: 0x1770
Length: 16

Lí do: Từ 0x1770 đến 0x177C mới trùng lại value

Data could potentially be stored in this block: 16 - 8 = 8
If this heap uses a simple explicit free list, what is the address of the next free block: 0x1798
_+ Lí do: Vì free block 1 là ở 0x1770

Không biết như em làm lại như thế anh đã thấy đúng hết chưa?
Và nếu đúng thì những gì em rút ra có đúng không:

Trong bảng phía dưới, không phải cứ address đầu tiên là sẽ block header đầu tiên, cái em cần chú ý đến chính là last bit value của địa chỉ đó.

Nếu bằng 0, tức là free.
Nếu bằng 1, tức là header.
Và như thế cứ thay nhau tuần tự bằng việc check value của address để biết nó là free block hay là header của allocated block?
Em cảm ơn anh đã chỉ dẫn ạ

drgnz · November 23, 2022, 9:57am

này phải dựa vào giá trị 0x19 mới đúng. tại heap data có khi bị trùng với header, nếu nói vậy là bị sai.
vd

0x00 -- 0x19
0x08 -- 0x19 // data in heap memory -> 0 byte?
...

đủng rồi

mình coi sơ thấy đúng rồi nha

korokoro · November 23, 2022, 10:02am

Ý em chỗ

tức là em check 0x1780 mang value 0x19, nên kiểu nó sẽ kết thúc khi đạt tới địa chỉ 0x1794 mang giá trị cũng là 0x19 á ^^.

Còn như về phần malloc(value) xong kiểu em cứ lấy multiple of 8 xong đi tính, rồi cộng 8 cho block size, xong chuyển qua hex thì auto add 1 thì tuy nó đúng nhưng kiểu bản chất thì em hiểu sai huh anh :3

Nguyên nhân để là multiple of 8 thì em nghĩ là vì nó làm theo block, nên không để lẻ ra được.

drgnz · November 23, 2022, 10:05am

ủa hiểu sai sao mình không để ý. cách giải thích bạn đúng mà. +1 là việc set bit cuối ấy, nó tương đương việc +1 vô thôi

korokoro · November 23, 2022, 10:06am

Sorry anh, em đọc nhầm phần trên.
Còn như ý em có giải thích ở trên là em dựa vào giá trị của địa chỉ 0x19 để tìm đến địa chỉ có giá trị trùng á.
Tức là khi nào tìm được thằng mang value 0x19 thì dừng.

korokoro · November 24, 2022, 9:10am

Xin lỗi anh em lại làm phiền.
Ý là kiểu nếu như phần kiến thức em diễn giải thì anh thấy phần chỉnh sửa của em đã đúng chưa á :3
Kiểu nếu áp dụng trên những gì anh chỉ thì em nghĩ đã chuẩn rồi

drgnz · November 24, 2022, 9:50am

theo mình thấy thì đúng theo những gì mình biết. còn đúng ý thầy không thì chờ điểm

korokoro · November 30, 2022, 6:57am

Nếu được anh có thể cho em hỏi 1 tí về cách hoạt động của byte được không?

Chẳng hạn như phần này nó hỏi bao nhiêu byte được truyền vào func01, func02 và func04.

Thì func01 em nghĩ là 4, nhưng em hơi phân vân về việc tại sao func02 lại là 4.
Đối với func04 thì em tính mỗi biến lấy value của nó thì tổng cộng là 32 không biết phải không? Nhưng đến đây em lại nhớ về memory allocation là luôn là multiple của cái variable size lớn nhất, vậy tính ra 4*8 = 32 cũng là phù hợp (?)

drgnz · November 30, 2022, 7:12am

nhìn vô definition của func02 là biết vì sao nó 4 bytes liền
còn func04 thì tính tổng của các field trong struct, lý thuyết bạn nói là struct alignment, khi có 2 field A và B, nếu size của A nhỏ hơn B thì nó sẽ dựa vào số byte của field lớn hơn để align theo. nên tính ra phải là 4 * 10 + 4 + 4 = 48 vì đều nhau hết

korokoro · November 30, 2022, 7:16am

Nãy em tính lộn, tính ra là 10 * 4 + 4 + 4 là đúng cái em nghĩ á.
Là nó chia hết cho 4, nhưng giả sử nó là tổng có 33 đi thì size cần có phải là 36 :3
Em cảm ơn nhiều ạ.
Kiểu phần này em còn tí thắc mắc liên quan đến lý thuyết assembly mà không biết tiện hỏi không :v
Kiểu em check đề trên mạng xong giải theo á :)))

drgnz · November 30, 2022, 8:36am

33 bytes thì tuỳ bạn sắp xếp fields mà nó sẽ padding hoặc pack lại. không hẳn lúc nào cũng sẽ thành 36. nếu là 33 bytes char thì nó chả thèm align gì luôn.