Structures on the stack (ANSI C)

Question

Having started studying Ulrich Drapper "What Every Programmer Should Know About Memory" [1] of the series, I got stuck trying to reproduce the examples presented in the section

3.3.2 Cache Effect Measurements

As far as I understand, structures should be allocated on the stack, since they are in memory one by one. Checking 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 the program starts, exit:

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

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

I ran tests on a MacBook Pro with OSX 10.6 64bit.

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

Update: I also played with increasing / decreasing pointers. It seems to work in 32-bit mode, but not in 64-bit mode. Adding 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 that makes sense. Maybe I should just put all the structures in an array.

Answer 1

Mandatory warning: in general, you should not make any assumptions about the relative location in memory of independent variables (i.e., those that are not wrapped inside an array or structure). The compiler is allowed to set variables on the stack at its discretion, taking into account restrictions on the alignment of structure members.

However, I think you will find that if you change:

 printf("Element at %p", curr) 

to

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

Your result will make more sense.

Answer 2

read this:

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

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

Answer 3

An array of zero length causes undefined behavior, so you are lucky that it did not compile with system("rm -rf /"); ...

Answer 4

Change

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

to

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

and try again - did it work?

Here are my results (on a 32-bit machine) with different 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