Heap memory: Gap of 16 bytes for 8 byte struct

问题:

I'm using the following code to create and insert a new node into a linked list, subsequently freeing them.

// the node
struct node
{
    int data;
    struct node *next;
};


// returns a pointer to a new node with data
struct node *new_node(int data)
{
    struct node *node;
    node = malloc(sizeof(struct node));
    node->data = data;
    node->next = NULL;
    return node;
}

// insert node at front of list
void push(struct node **head, int data)
{
    struct node *node = new_node(data);
    node->next = *head;
    *head = node;
}

// free the list, deallocate each node's memory
void delete_list(struct node** head)
{
    if(*head == NULL)
        return;

    struct node *next = NULL;
    next = (*head)->next;
    while(next != NULL)
    {
        next = (*head)->next;
                // print address of the memory released
        printf("Freeing %d\n", (int)*head);
        free(*head);
        *head = next;
    }
}

Now, the struct is 8 bytes in my machine (4 byte int and 4 byte pointer). Now, I'm a bit unsure about the following, so please help me out:

1. When I call push() in sequence, is the memory allocated contiguously? Is that always the case? I guess it cannot be, for the memory in heap can be fragmented.

2. Say the memory allocated was contiguous, then would it be spaced 8 bytes apart, since the struct's size is 8 bytes. On my machine, when I printed the address of the memory being freed, the memory addresses printed are 16 bytes apart, on every execution. Why?
   Freeing 148025480 Freeing 148025464 Freeing 148025448 Freeing 148025432 Freeing 148025416 Freeing 148025400 Freeing 148025384 Freeing 148025368 Freeing 148025352 <empty list>

3. Now if the memory was NOT allocated contiguously for our integer array (the heap was very much fragmented, and memory requirement was quite large), and we used pointer arithmetic to process each element of the array by incrementing the address by 4 each time(or whatever the size of int is), shouldn't we run into some memory not reserved by our program, throwing off the program? Or is the runtime environment smart enough to take care of this, as the compiler cannot, for it doesn't know how the memory will be allocated. Does the OS take care of this?

回答1:

Each time you call new_node, it calls malloc().

You cannot (or should not) predict where malloc() will find you memory. It is OS and runtime dependent.

Running on a particular OS, under certain circumstances, you might observe that allocations from consecutive calls to malloc() are contiguous. However that behaviour may change under load, or with a kernel update, a change in the implementation of libc, or under all kinds of other conditions.

You can assume that the chunk of memory allocated by a single call to malloc() is contiguous (at least, in terms of the pointers your program sees). Your program should not assume anything else about contiguity.

---

If this really bothers you, you can take charge of more of the memory management in your own code -- instead of calling malloc() for each node, call it at the start and get a larger chunk of memory. Subsequent calls to new_node can use part of this chunk. If you run out of space in that chunk, you can either malloc() another chunk (which probably won't be contiguous with the first) or realloc() to extend (and probably move) it.

You'll probably find that all this makes your code more complicated -- and it's up to you whether there are benefits to counter that. The authors of the Hotspot Java VM essentially do this - they malloc() a big block of memory at the start of execution, then rather than call malloc() and free() when the Java program wants memory, it uses its own routines to allocate parts of that block.

回答2:

Regarding #2, one reason for the results of calls to malloc not being exactly contiguous can be metadata: when you ask for x bytes, malloc implementations may allocate a little extra memory for internal bookkeeping processes (tagging the size of the block, pointers to other free blocks, etc). Thus a request for 8 bytes may actually cause 16 bytes to be allocated internally, hence the 16-byte spacing between successive allocations.

回答3:

If you allocate memory using malloc, the memory returned will always be contiguous.

If you call malloc twice, there's no guarantee that the two allocations will be placed next to each other, not even if the two malloc calls are right next to each other.