Structs on the stack (ANSI C)

Question

Dear all

Having started to study Ulrich Dreppers "What every programmer should know about memory" [1] series I got stuck when trying to reproduce the examples presented in section

3.3.2 Measurements of Cache Effects

As far as I understand the structures should be allocated on the stack since then they are in memory one after another. Verifying this with a small program:

#include <stdio.h>
#include <stdlib.h>

#define NUMPAD 0

struct listelement
{ 
    struct listelement *next;
    long int padding[NUMPAD];
};

typedef struct listelement elem;

int main()
{
    int size_elem = sizeof(elem);
    printf("Size of a list elem: %i\n", size_elem);

    elem _1, _2, _3;

    _1.next = &_2;
    _2.next = &_3;
    _3.next = &_1;

    elem *first, *last, *curr;

    first = &_1;
    last = &_3;
    curr = &_1;

    int k=0;

    while(1)
    {
        printf("Element at %p", curr);
        for (int i=0; i<NUMPAD; i++)
        {
            (curr->padding)[i] = i+k;
            printf("%ld ", (curr->padding)[i]);
        }
        printf("\n");
        if (curr == last)
            break;
        k++;
        curr = curr->next;
    }

    return 0;
}

When running the program the output is:

Size of a list elem: 8
Element at 0x7fff5fbff540
Element at 0x7fff5fbff530
Element at 0x7fff5fbff520

The differences between the memory addresses, however is 16 why not 8? When increasing NUMPAD the difference seems to grow even more, for example for NUMPAD=2 I get a difference of 511.

I did the tests on a macbook pro running OSX 10.6 64bit.

[1] http://lwn.net/Articles/252125/

Update: I also played with incrementing/decrementing the pointers. It seems to work in 32bit mode, but not in 64bit mode. Adding the code

first--;
printf("first-- %p\n", first);
if (first == &_2) {
    printf("Decrementing works.\n");
}

macbook:blah nils$ gcc -m32 -DNUMPAD=0 -g -std=c99 -o blah blah.c && ./blah
Size of a list elem: 4
Element at 0xbffff5b8
Element at 0xbffff5b4
Element at 0xbffff5b0
first-- 0xbffff5b4
Decrementing works.
macbook:blah nils$ gcc -DNUMPAD=0 -g -std=c99 -o blah blah.c && ./blah
Size of a list elem: 8
Element at 0x7fff5fbff530
Element at 0x7fff5fbff520
Element at 0x7fff5fbff510
first-- 0x7fff5fbff528

I wonder how this makes sense.. maybe I should just place all the structs into an array.

Answer 1

A zero-length array invokes undefined behavior, so you're lucky it didn't compile to system("rm -rf /");...

Answer 2

read this:

http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Zero-Length.html

I suspect the [0] defaults to [] and has size 0 if you are compiling using C99

Answer 3

Obligatory warning: in general, you should not be making any assumptions about the relative location in memory of independent variables (i.e., ones that are not wrapped up inside an array or struct). The compiler is allowed to lay out variables on the stack as it sees fit, subject to the alignment restrictions of the struct members.

That said, I think you will find that if you change:

printf("Element at %p", curr)

to

printf("Element at %p\n", curr)

Your output will make a lot more sense.

Answer 4

Change

printf("%ld ", (curr->padding)[i]);

to

printf("\t%ld ", (curr->padding)[i]);

and try again - got it?

Here are my results (on a 32 bit machine) with various values for NUMPAD.

test $ gcc -std=c99 -DNUMPAD=0 test.c && ./a.out 
Size of a list elem: 4
Element at 0xbfd84df8
Element at 0xbfd84df4
Element at 0xbfd84df0
test $ gcc -std=c99 -DNUMPAD=1 test.c && ./a.out 
Size of a list elem: 8
Element at 0xbff7eff4   0 
Element at 0xbff7efec   1 
Element at 0xbff7efe4   2 
test $ gcc -std=c99 -DNUMPAD=2 test.c && ./a.out 
Size of a list elem: 12
Element at 0xbf9ea260   0   1 
Element at 0xbf9ea254   1   2 
Element at 0xbf9ea248   2   3