Introduction to Computer Systems 15-213/18-243, spring 2009 1st Lecture, Jan. 12th
Structs & Alignment
http://xkcd.com/163/
CS295
Structs, Multi-dimensional arrays & Alignment
Data Structures in Assembly
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structs
Alignment
2
CS295
Structs, Multi-dimensional arrays & Alignment
Compare all the arrays
2
Array Allocation
Basic Principle
T A[N]; array of data type T and length N
Contiguously allocated region of N*sizeof(T) bytes
Identifier A returns address of array (type T*)
3
char msg[12];
x
x + 12
int val[5];
x
x + 4
x + 8
x + 12
x + 16
x + 20
double a[3];
x + 24
x
x + 8
x + 16
char* p[3];
(or char *p[3];)
x
x + 8
x + 16
x + 24
CS295
Structs, Multi-dimensional arrays & Alignment
Basically all you need to know about arrays!
Array Access
Basic Principle
T A[N]; array of data type T and length N
Identifier A returns address of array (type T*)
Reference Type Value
4
int x[5];
3
7
1
9
5
a
a+4
a+8
a+12
a+16
a+20
x[4] int 5
x int* a
x+1 int* a + 4
&x[2] int* a + 8
x[5] int ?? (whatever’s in memory at addr x+20)
*(x+1) int 7
x+i int* a + 4*i
CS295
Structs, Multi-dimensional arrays & Alignment
Arrays explain the funky part of pointer arithmetic
Array Example
5
typedef int zip_dig[5];
zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig sfu = { 9, 8, 1, 9, 5 };
zip_dig ucb = { 9, 4, 7, 2, 0 };
initialization
typedef: Declaration “zip_dig sfu” equivalent to “int sfu[5]”
CS295
Structs, Multi-dimensional arrays & Alignment
Referencing Examples
6
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
56
60
64
68
72
76
Reference Address Value Guaranteed?
sfu[3]
sfu[6]
sfu[-1]
cmu[15]
zip_dig cmu;
zip_dig sfu;
zip_dig ucb;
No bounds checking
Example arrays happened to be allocated in successive 20 byte blocks
Not guaranteed to happen in general
CS295
Structs, Multi-dimensional arrays & Alignment
Don’t do this!
C Details: Arrays and Pointers
Arrays are (almost) identical to pointers
char *string and char string[] are nearly identical declarations
Differ in subtle ways: initialization, sizeof(), etc.
An array name looks like a pointer to the first (0th) element
ar[0] same as *ar; ar[2] same as *(ar+2)
An array name is read-only (no assignment)
Cannot use “ar =
7
CS295
Structs, Multi-dimensional arrays & Alignment
Sizeof
C Details: Arrays and Functions
Declared arrays only allocated while the scope is valid:
char* foo() {
char string[32]; …;
return string;
}
An array is passed to a function as a pointer:
Array size gets lost!
int foo(int ar[], unsigned int size) {
… ar[size-1] …
}
8
BAD!
Must explicitly
pass the size!
Really int *ar
CS295
Structs, Multi-dimensional arrays & Alignment
Arrays can be local variables
8
Referencing Examples
9
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
56
60
64
68
72
76
Reference Address Value Guaranteed?
sfu[3]
sfu[6]
sfu[-1]
cmu[15]
36 + 4* 3 = 48 9 Yes
36 + 4* 6 = 60 4 No
36 + 4*-1 = 32 3 No
16 + 4*15 = 76 ?? No
zip_dig cmu;
zip_dig sfu;
zip_dig ucb;
typedef int zip_dig[5];
No bounds checking
Example arrays happened to be allocated in successive 20 byte blocks
Not guaranteed to happen in general
CS295
Structs, Multi-dimensional arrays & Alignment
zip_dig sea[4] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};
Nested Array Example
10
Remember, T A[N] is an array with elements of type T, with length N
What is the layout in memory?
same as:
int sea[4][5];
typedef int zip_dig[5];
CS295
Structs, Multi-dimensional arrays & Alignment
Nested Array Example
“Row-major” ordering of all elements
Elements in the same row are contiguous
Guaranteed (in C)
11
76
96
116
136
156
9
8
1
9
5
9
8
1
0
5
9
8
1
0
3
9
8
1
1
5
sea[3][2];
Row 0
Row 1
Row 2
Row 3
typedef int zip_dig[5];
zip_dig sea[4] =
{{ 9, 8, 1, 9, 5 },
{ 9, 8, 1, 0, 5 },
{ 9, 8, 1, 0, 3 },
{ 9, 8, 1, 1, 5 }};
Remember, T A[N] is an array with elements of type T, with length N
CS295
Structs, Multi-dimensional arrays & Alignment
Two-Dimensional (Nested) Arrays
Declaration: T A[R][C];
2D array of data type T
R rows, C columns
Each element requires
sizeof(T) bytes
Array size?
12
A[0][0]
A[0][C-1]
A[R-1][0]
• • •
• • •
A[R-1][C-1]
•
•
•
•
•
•
CS295
Structs, Multi-dimensional arrays & Alignment
Down, then across
Two-Dimensional (Nested) Arrays
Declaration: T A[R][C];
2D array of data type T
R rows, C columns
Each element requires
sizeof(T) bytes
Array size:
R*C*sizeof(T) bytes
Arrangement: row-major ordering
13
int A[R][C];
• • •
A
[0]
[0]
A
[0]
[C-1]
• • •
A
[1]
[0]
A
[1]
[C-1]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
• • •
4*R*C bytes
A[0][0]
A[0][C-1]
A[R-1][0]
• • •
• • •
A[R-1][C-1]
•
•
•
•
•
•
CS295
Structs, Multi-dimensional arrays & Alignment
Memory is linear
Multi-Level Array Example
14
int cmu[5] = { 1, 5, 2, 1, 3 };
int sfu[5] = { 9, 8, 1, 9, 5 };
int ucb[5] = { 9, 4, 7, 2, 0 };
int* univ[3] = {sfu, cmu, ucb};
Is a multi-level array the
same thing as a 2D array?
zip_dig univ2D[3] = {
{ 9, 8, 1, 9, 5 },
{ 1, 5, 2, 1, 3 },
{ 9, 4, 7, 2, 0 }
};
One array declaration = one contiguous block of memory
NO
2D Array Declaration:
Multi-Level Array Declaration(s):
CS295
Structs, Multi-dimensional arrays & Alignment
Array Element Accesses
15
int get_sea_digit
(int index, int digit)
{
return sea[index][digit];
}
int get_univ_digit
(int index, int digit)
{
return univ[index][digit];
}
Nested array
Multi-level array
Access looks the same, but it isn’t:
Mem[sea+20*index+4*digit]
Mem[Mem[univ+8*index]+4*digit]
36
160
16
60
168
176
univ
cmu
sfu
ucb
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
60
64
68
72
76
80
CS295
Structs, Multi-dimensional arrays & Alignment
Depends on how array is declared, look at type
Multi-dimensional arrays are a special construct!
Multi-Level Referencing Examples
Reference Address Value Guaranteed?
univ[2][3]
univ[1][5]
univ[2][-2]
univ[3][-1]
univ[1][12]
C code does not do any bounds checking
Location of each lower-level array in memory is not guaranteed
16
36
160
16
60
168
176
univ
cmu
sfu
ucb
1
5
2
1
3
16
20
24
28
32
36
9
8
1
9
5
36
40
44
48
52
56
9
4
7
2
0
60
64
68
72
76
80
CS295
Structs, Multi-dimensional arrays & Alignment
72 2 yes
36 9 no
52 5 no
?? ?? No
64 4 no
Summary
Contiguous allocations of memory
No bounds checking (and no default initialization)
Can usually be treated like a pointer to first element
int a[4][5]; array of arrays
all levels in one contiguous block of memory
int* b[4]; array of pointers (to arrays)
First level in one contiguous block of memory
Each element in the first level points to another “sub” array
Parts anywhere in memory
17
CS295
Structs, Multi-dimensional arrays & Alignment
Data Structures in Assembly
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structs
Alignment
Unions
18
CS295
Structs, Multi-dimensional arrays & Alignment
18
Structs in C
typedef struct {
int lengthInSeconds;
int yearRecorded;
} Song;
Song song1;
song1.lengthInSeconds = 213;
song1.yearRecorded = 1994;
Song song2;
song2.lengthInSeconds = 248;
song2.yearRecorded = 1988;
19
Way of defining compound data types
A structured group of variables, possibly including other structs
CS295
Structs, Multi-dimensional arrays & Alignment
typedef
19
Accessing Structure Members
Given a struct instance, access
member using the . operator:
struct rec r1;
r1.i = val;
Given a pointer to a struct:
struct rec *r;
r = &r1; // or malloc space for r to point to
We have two options:
Use * and . operators: (*r).i = val;
Use -> operator for short: r->i = val;
In assembly: register holds address of the first byte
Access members with offsets
20
struct rec {
int a[4];
long i;
struct rec *next;
};
CS295
Structs, Multi-dimensional arrays & Alignment
How does a “.” access get translated into assembly? It looks exactly like a pointer access: an offset is added to the beginning of the struct to reach the appropriate member, then the access is performed. When a “.” access is performed, no “pointer” (i.e. no address kept in some register) is needed: the struct’s location on the current function’s stack frame (or in the args section of the caller’s stack frame) is always known, so the offsets can always be calculated relative to %rsp.
Structure Representation
Characteristics
Contiguously-allocated region of memory
Refer to members within structure by names
Members may be of different types
21
a
r
i
next
0
16
24
32
struct rec {
int a[4];
long i;
struct rec *next;
};
struct rec *r;
CS295
Structs, Multi-dimensional arrays & Alignment
Structure Representation
Structure represented as block of memory
Big enough to hold all of the fields
Fields ordered according to declaration order
Even if another ordering would be more compact
Compiler determines overall size + positions of fields
Machine-level program has no understanding of the structures in the source code
22
a
r
i
next
0
16
24
32
struct rec {
int a[4];
long i;
struct rec *next;
};
struct rec *r;
CS295
Structs, Multi-dimensional arrays & Alignment
No structs or field names in assembly! Just offsets
add a0, a1, 16 # Coming up in Week 3
ret
long get_i(struct rec *r)
{
return r->i;
}
Accessing a Structure Member
Compiler knows the offset of each member within a struct
Compute as *(r+offset)
Referring to absolute offset, so no pointer arithmetic
23
r->i
a
r
i
next
0
16
24
32
struct rec {
int a[4];
long i;
struct rec *next;
};
struct rec *r;
CS295
Structs, Multi-dimensional arrays & Alignment
int* find_addr_of_array_elem
(struct rec *r, long index)
{
return &r->a[index];
}
Generating Pointer to Array Element
Generating Pointer to
Array Element
Offset of each structure member determined at compile time
Compute as:
r+4*index
24
r+4*index
&(r->a[index])
a
r
i
next
0
16
24
32
struct rec {
int a[4];
long i;
struct rec *next;
};
struct rec *r;
CS295
Structs, Multi-dimensional arrays & Alignment
Note the order of operation: & applies to the entire expression
Also: 2 instances of “syntactic sugar”
Could use additional offset if not first elem of struct
Struct Definitions
Structure definition:
Does NOT declare a variable
Variable type is “struct name”
Joint struct definition and typedef
Don’t need to give struct a name in this case
struct name {
/* fields */
};
typedef struct {
/* fields */
} name;
name n1;
struct name name1, *pn, name_ar[3];
struct nm {
/* fields */
};
typedef struct nm name;
name n1;
pointer
array
Easy to forget semicolon!
CS295
Structs, Multi-dimensional arrays & Alignment
25
Scope of Struct Definition
Why is placement of struct definition important?
What actually happens when you declare a variable?
Creating space for it somewhere!
Without definition, program doesn’t know how much space
Almost always define structs in global scope near the top of your C file
Struct definitions follow normal rules of scope
26
struct data {
int ar[4];
long d;
};
Size = _____ bytes
struct rec {
int a[4];
long i;
struct rec* next;
};
Size = _____ bytes
CS295
Structs, Multi-dimensional arrays & Alignment
Fill in sizes
26
Nested Struct
27
&f->my_bar
&f->my_bar.y
a
b
0
8
16
struct foo {
long a;
long b;
struct bar my_bar;
};
struct bar {
long x;
long y;
};
struct foo *f;
x
y
24
32
CS295
Structs, Multi-dimensional arrays & Alignment
Note the difference of -> and .
Nested Struct
28
a
b
0
8
16
?????????
struct foo {
long a;
long b;
struct foo my_foo;
};
CS295
Structs, Multi-dimensional arrays & Alignment
Infinite struct!!!
This is why you need a pointer
Review: Memory Alignment
Aligned means that any primitive object of bytes must have an address that is a multiple of
Aligned addresses for data types:
29
Type Addresses
1 char No restrictions
2 short Lowest bit must be zero: …02
4 int, float Lowest 2 bits zero: …002
8 long, double, * Lowest 3 bits zero: …0002
CS295
Structs, Multi-dimensional arrays & Alignment
Lowest log(k) bits should be 0
29
Alignment Principles
Aligned Data
Primitive data type requires bytes
Address must be multiple of
Motivation for Aligning Data
Memory accessed by (aligned) chunks of bytes
(width is system dependent)
Inefficient to load or store value that spans quad word boundaries
Virtual memory trickier when value spans 2 pages (more on this later)
30
CS295
Structs, Multi-dimensional arrays & Alignment
Analogy?
30
Structures & Alignment
Unaligned Data
Aligned Data
Primitive data type requires bytes
Address must be multiple of
31
c
i[0]
i[1]
v
p
p+1
p+5
p+9
p+17
internal fragmentation
struct S1 {
char c;
int i[2];
double v;
} *p;
c
i[0]
i[1]
v
3 bytes
4 bytes
p+0
p+4
p+8
p+16
p+24
Multiple of 4
Multiple of 8
Multiple of 8
Multiple of 8
CS295
Structs, Multi-dimensional arrays & Alignment
struct S1 { … } *p; – this defines a new type “struct S1”, and creates a variable p with type “struct S1 *”
#include
printf(“sizeof p = %d\n”, (int) sizeof(p));
printf(“offset of v in p = %d\n”, (int) offsetof(struct S1, v));
31
Satisfying Alignment with Structures (1)
Within structure:
Must satisfy each element’s alignment requirement
Overall structure placement
Each structure has alignment requirement
= Largest alignment of any element
Counts array elements individually as elements
Inner structs are aligned to their largest alignment
Example:
= 8, due to double element
32
struct S1 {
char c;
int i[2];
double v;
} *p;
c
i[0]
i[1]
v
3 bytes
4 bytes
p+0
p+4
p+8
p+16
p+24
Multiple of 4
Multiple of 8
Multiple of 8
internal fragmentation
CS295
Structs, Multi-dimensional arrays & Alignment
Whole struct padded to 8, otherwise inner padding isn’t really possible
32
Satisfying Alignment with Structures (2)
Can find offset of individual fields
using offsetof()
Need to #include
Example: offsetof(struct S2,c) returns 16
For largest alignment requirement ,
overall structure size must be multiple of
Compiler will add padding at end of
structure to meet overall structure
alignment requirement
33
v i[0] i[1] c 7 bytes
p+0 p+8 p+16 p+24
external fragmentation
struct S2 {
double v;
int i[2];
char c;
} *p;
Multiple of 8
Multiple of 8
CS295
Structs, Multi-dimensional arrays & Alignment
Swapped double and char
Why end padding? Arrays
33
Arrays of Structures
Overall structure length multiple of
Satisfy alignment requirement
for every element in array
34
a[0] a[1] a[2] • • •
a+0 a+24 a+48 a+72
struct S2 {
double v;
int i[2];
char c;
} a[10];
v i[0] i[1] c 7 bytes
a+24 a+32 a+40 a+48
external fragmentation
CS295
Structs, Multi-dimensional arrays & Alignment
struct S2 { … } a[10]; – declares a new type “struct S2”, then declares an array a that contains 10 “struct S2” elements
34
Accessing Array Elements
Compute start of array element as: 12*index
sizeof(S3) = 12, including alignment padding
Element j is at offset 8 within structure
Assembler gives offset a+8
35
short get_j(int index)
{
return a[index].j;
}
a[0] • • • a[index] • • •
a+0 a+12 a+12*index
i 2 bytes v j 2 bytes
a+12*index
a+12*index+8
struct S3 {
short i;
float v;
short j;
} a[10];
CS295
Structs, Multi-dimensional arrays & Alignment
Alignment of Structs
Compiler will do the following:
Maintains declared ordering of fields in struct
Each field must be aligned within the struct
(may insert padding)
offsetof can be used to get actual field offset
Overall struct must be aligned according to largest field
Total struct size must be multiple of its alignment
(may insert padding)
sizeof should be used to get true size of structs
36
CS295
Structs, Multi-dimensional arrays & Alignment
How the Programmer Can Save Space
Compiler must respect order elements are declared in
Sometimes the programmer can save space by declaring large data types first
37
struct S4 {
char c;
int i;
char d;
} *p;
struct S5 {
int i;
char c;
char d;
} *p;
c
i
3 bytes
d
3 bytes
c
i
d
2 bytes
12 bytes
8 bytes
CS295
Structs, Multi-dimensional arrays & Alignment
Peer Instruction Question
Minimize the size of the struct by re-ordering the vars
What are the old and new sizes of the struct?
sizeof(struct old) = _____ sizeof(struct new) = _____
38
struct old {
int i;
short s[3];
char *c;
float f;
};
struct new {
int i;
______ ______;
______ ______;
______ ______;
};
CS295
Structs, Multi-dimensional arrays & Alignment
Biggest is 8 bytes
So 4 + 6 + (6) + 8 + 4 + (4) = 32
Char* first
8 + 4 + 4 + 6 + (2) = 24
38
Summary
Arrays in C
Aligned to satisfy every element’s alignment requirement
Structures
Allocate bytes in order declared
Pad in middle and at end to satisfy alignment
39
CS295
Structs, Multi-dimensional arrays & Alignment