Why does this program allocate 8 pages but can only fit into 2048 nodes, which are 8 bytes in size?
A node is defined like this:
struct node{
int value;
struct node *next;
};
Using sizeof(struct node)
, I find out that node is 8 bytes (in xv6). So I use malloc
to allocate some memory space to store some nodes. One page in xv6 is 4096 bytes, if I have 8 pages I can store 4096 such nodes. However, what's not what happens, after I have malloc
2048 such nodes, if I am malloc
different, more pages are allocated for the current process, why is that?
// Now display how many pages are allocated to the process
// Suppose there is a system call named memcount(), it is given by
// my professor, I wouldn't think there any problem with that
//
memcount(); // which prints 3, meaning that initially, without
// allocaing anything, 3 pages = 12288 bytes of memory allocated
for(i = 0; i < 2048; ++i){
struct node *nd = (struct node *)malloc(sizeof(struct node));
}
memcount(); // which prints 11, so 8 more pages are allocated
// If we allocated 1 more node
struct node *nd = (struct node *)malloc(sizeof(struct node));
memcount(); // which prints 19, another 8 pages are allocated
What if I'm so confused there shouldn't be much space on the first 8 pages? Since one node is only 8 bytes in size, why are there more pages in this process?
source to share
The question has already been answered in a comment: malloc()
you need some storage space how memory is used.
The memory handler sees the heap as one large array of bytes (because RAM is one large array in most memory models). (There are other memory models, or the memory manager may store some data in extra pages, but to keep it simple we ignore such cases)
As an example, we could think of a system where the first 4 bytes are used as a pointer ( p0
), where the next valid blocks start and the next 4 bytes for a variable ( size_t
, s0
) how many bytes are used for this block (we need 2 variables to detect when a block between two blocks is freed). The next block also has a pointer ( p1
) to the next (next next) block and a variable for the block size ( s1
)
After this header is data you can use, malloc()
return a pointer to the first byte after this header. The variable s0
will store the number of bytes you requested. After a new one malloc()
after the first block, a new header will be created and p0 will point to that header:
Address: 0x10 0x14 0x18 0x1B 0x20 0x24 0x28 ...
Name: p0 s0 value next p1 s1 value...
Value: 0x20 8 ?? 0x28 0 8 ??
Here is a situation where you allocate 2 blocks, p1
and s1
are variables for the second block header. You can use variable next
and value
. The pointer to return malloc()
, 0x18
and 0x28
.
To avoid using up half of the memory handler space, you could allocate a larger array in one step. You can use struct
like this:
struct Node_T
{
int values[512];
size_t usedValues;
struct Node_T *next;
}
Then you will need 4 * 4 = 16 bytes of the total overhead (including the memory handler overhead), and the memory handler is assumed to have 8 bytes per block and int
, pointers and size_t
- 4 bytes). But you will need an extra copy or move overhead when you delete or add a value between other values.
source to share