L03: Memory & Data II CMPT 295
Memory, Data, & Addressing II
http://xkcd.com/138/
L03: Memory & Data II CMPT 295
Roadmap
C:
Java:
Memory & data
Arrays & structs
Integers & floats RISC V assembly Procedures & stacks Executables Memory & caches Processor Pipeline Performance Parallelism
car *c = malloc(sizeof(car)); c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c); free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Assembly language:
Machine code:
Computer system:
OS:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
2
L03: Memory & Data II CMPT 295
Review
1)
If the word size of a machine is 64-bits, which of the
following is usually true? (pick all that apply) a) 64 bits is the size of a pointer
b) 64bitsisthesizeofaninteger
c) 64 bits is the width of a register
(True/False) By looking at the bits stored in memory, I can tell if a particular 4-bytes is being used to represent an integer, floating point number, or instruction.
If the size of a pointer on a machine is 6 bits, the address space is how many bytes?
2)
3)
3
L03: Memory & Data II CMPT 295
Memory, Data, and Addressing
! Representing information as bits and bytes ! Organizing and addressing data in memory
! Manipulating data in memory using C
! Boolean algebra and bit-level manipulations
4
L03: Memory & Data II CMPT 295
Addresses and Pointers in C
! & = “address of” operator
! * = “value at address” or “dereference” operator
* is also used with variable declarations
int* ptr; int x = 5;
int y = 2;
ptr = &x;
y = 1 + *ptr; “Dereference ptr”
Declares a variable, ptr, that is a pointer to (i.e. holds the address of) an int in memory
Declares two variables, x and y, that hold ints, and initializes them to 5 and 2, respectively
Sets ptr to the address of x (“ptr points to x”)
Sets y to “1 plus the value stored at the addressheldbyptr. Becauseptr points to x, this is equivalent to y=1+x;
What is *(&y) ?
5
L03: Memory & Data II CMPT 295
Assignment in C
! A variable is represented by a location
! Declaration ≠ initialization (initially holds “garbage”)
! int x, y;
” x is at address 0x04, y is at 0x18
0x00 0x01 0x02 0x03
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
x
y
A7
00
32
00
00
01
29
F3
EE
EE
EE
EE
FA
CE
CA
FE
26
00
00
00
00
00
10
00
01
00
00
00
FF
00
F4
96
DE
AD
BE
EF
00
00
00
00
6
L03: Memory & Data II CMPT 295
Assignment in C
! A variable is represented by a location
32-bit example (pointers are 32-bits wide)
! Declaration ≠ initialization (initially holds “garbage”)
! int x, y;
” x is at address 0x04, y is at 0x18
0x00 0x01 0x02 0x03
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
x
y
little-endian
00
01
29
F3
01
00
00
00
7
L03: Memory & Data II CMPT 295
Assignment in C
! left-hand side = right-hand side;
” LHS must evaluate to a location
32-bit example (pointers are 32-bits wide)
” RHS must evaluate to a value (could be an address)
” Store RHS value at LHS location ! int x, y;
! x = 0;
0x00 0x01 0x02 0x03
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
x
y
& = “address of” * = “dereference”
00
010
2090
0F30
01
00
00
00
8
L03: Memory & Data II CMPT 295
Assignment in C
! left-hand side = right-hand side;
” LHS must evaluate to a location
32-bit example (pointers are 32-bits wide)
” RHS must evaluate to a value (could be an address)
” Store RHS value at LHS location ! int x, y;
0x00 0x01 0x02 0x03
& = “address of” * = “dereference”
00
00
00
00
010
0207
D00
30C0
! x = 0;
! y = 0x3CD02700;
little endian!
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
x
y
9
L03: Memory & Data II CMPT 295
Assignment in C
! left-hand side = right-hand side;
” LHS must evaluate to a location
32-bit example (pointers are 32-bits wide)
” RHS must evaluate to a value (could be an address)
” Store RHS value at LHS location ! int x, y;
! x = 0;
! y = 0x3CD02700;
! x = y + 3;
“Get value aty, add 3, store inx
0x00 0x01 0x02 0x03
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
x
y
& = “address of” * = “dereference”
003
0207
D00
30C0
00
27
D0
3C
10
Assignment in C
! left-hand side = right-hand side;
” LHS must evaluate to a location
32-bit example (pointers are 32-bits wide)
& = “address of” * = “dereference”
L03: Memory & Data II
CMPT 295
” RHS must evaluate to a value (could be an address)
” Store RHS value at LHS location ! int x, y;
! x = 0;
! y = 0x3CD02700;
! x = y + 3;
“Get value aty, add 3, store inx
! int* z;
” z is at address 0x20
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
0x00 0x01 0x02 0x03
03 27 D0 3Cx 00 27 D0 3Cy
DE AD BE EFz 11
L03: Memory & Data II CMPT 295
Assignment in C
! left-hand side = right-hand side;
” LHS must evaluate to a location
32-bit example (pointers are 32-bits wide)
” RHS must evaluate to a value (could be an address)
” Store RHS value at LHS location ! int x, y;
! x = 0;
! y = 0x3CD02700;
! x = y + 3;
“Get value aty, add 3, store inx
! int* z = &y + 3;
” Get address of y, “add 3”, store in z
0x00 0x01 0x02 0x03
0x00 0x04 0x08 0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
x
y
z
12
& = “address of” * = “dereference”
03
27
D0
3C
00
27
D0
3C
24
00
00
00
Pointer
arithmetic
L03: Memory & Data II CMPT 295
13
L03: Memory & Data II CMPT 295
Pointer Arithmetic
! Pointer arithmetic is scaled by the size of target type ” In this example, sizeof(int) = 4
! int* z = &y + 3;
” Get address of y, add 3*sizeof(int), store in z “&y=0x18=1*161 +8*160 =24
” 24 + 3*(4) = 36
= 2*161 + 4*160 = 0x24
! Pointer arithmetic can be dangerous! ” Can easily lead to bad memory accesses ” Be careful with data types and casting
14
L03: Memory & Data II CMPT 295
Assignment in C
! int x, y;
! x = 0;
! y = 0x3CD02700;
! x = y + 3;
“Get value aty, add 3, store inx
! int* z = &y + 3; “Getaddressofy,add12,storeinz 0x14
32-bit example (pointers are 32-bits wide)
0x00 0x04 0x08 0x0C 0x10
x
y
z
& = “address of” * = “dereference”
0x00 0x01 0x02 0x03
03
27
D0
3C
00
27
D0
3C
24
00
00
00
! *z = y;
” What does this do?
0x18 0x1C 0x20 0x24
15
L03: Memory & Data II CMPT 295
Assignment in C
! int x, y;
! x = 0;
! y = 0x3CD02700;
! x = y + 3;
“Get value aty, add 3, store inx
! int* z = &y + 3; “Getaddressofy,add12,storeinz 0x14
32-bit example (pointers are 32-bits wide)
0x00 0x04 0x08 0x0C 0x10
x
y
z
& = “address of” * = “dereference”
0x00 0x01 0x02 0x03
03
27
D0
3C
00
27
D0
3C
24
00
00
00
00
27
D0
3C
The target of a pointer is also a location
! *z = y;
” Get value of y, put in address stored in z
0x18 0x1C 0x20 0x24
16
L03: Memory & Data II CMPT 295
Arrays in C
Declaration: int a[6]; element type
name
64-bit example (pointers are 64-bits wide)
number of elements
a[1]
a[3]
a[5]
0x0 0x8
0x1 0x9
0x2 0xA
0x3 0xB
0x4 0xC
0x5 0xD
0x6 0xE
0x7 0xF
a[0]
a[2]
a[4]
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
17
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
L03: Memory & Data II CMPT 295
Arrays Basics
• Pitfall: An array in C does not know its own length, and its bounds are not checked!
– We can accidentally access off the end of an array – We must pass the array and its size to any
procedure that is going to manipulate it • Mistakes with array bounds cause
segmentation faults and bus errors
– Be careful! These are VERY difficult to find (You’ll learn how to debug these in lab)
18
L03: Memory & Data II CMPT 295
Arrays in C
Declaration: int a[6];
Indexing:
a[0] = 0x015f;
a[5] = a[0];
0x0 0x8
0x1 0x9
0x2 0xA
0x3 0xB
0x4 0xC
0x5 0xD
0x6 0xE
0x7 0xF
5F
01
00
00
5F
01
00
00
a[0]
a[2]
a[4]
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
19
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
&a[i] is the address of a[0] plus i times the element size in bytes
L03: Memory & Data II CMPT 295
Arrays in C
Declaration: int a[6];
Indexing:
No bounds checking:
a[0] = 0x015f;
a[5] = a[0];
a[6] = 0xBAD;
a[-1] = 0xBAD;
a[0]
a[2]
a[4]
0x0 0x8
0x1 0x9
0x2 0xA
0x3 0xB
0x4 0xC
0x5 0xD
0x6 0xE
0x7 0xF
AD
0B
00
00
5F
01
00
00
5F
01
00
00
AD
0B
00
00
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
20
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
&a[i] is the address of a[0] plus i times the element size in bytes
L03: Memory & Data II CMPT 295
Arrays in C
Declaration: int a[6];
Indexing:
No bounds checking:
Pointers:
a[0] = 0x015f;
a[5] = a[0];
a[6] = 0xBAD;
a[-1] = 0xBAD;
int* p; p = a;
0x0 0x8
0x1 0x9
0x2 0xA
0x3 0xB
0x4 0xC
0x5 0xD
0x6 0xE
0x7 0xF
AD
0B
00
00
05AF
010
00
00
5F
01
00
00
AD
0B
00
00
10
00
00
00
00
00
00
00
equivalent p = &a[0]; a[0]
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
*p = 0xA;
a[2] a[4]
p
21
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
&a[i] is the address of a[0] plus i times the element size in bytes
L03: Memory & Data II CMPT 295
Arrays in C
Declaration: int a[6];
Indexing:
No bounds checking:
Pointers:
a[0] = 0x015f;
a[5] = a[0];
a[6] = 0xBAD;
a[-1] = 0xBAD;
int* p; p = a;
0x0 0x8
0x1 0x9
0x2 0xA
0x3 0xB
0x4 0xC
0x5 0xD
0x6 0xE
0x7 0xF
AD
0B
00
00
05AF
010
00
00
0B
00
00
00
5F
01
00
00
AD
0B
00
00
10
00
00
00
00
00
00
00
equivalent p = &a[0]; a[0]
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
*p = 0xA;
a[2] a[4]
p
array indexing = address arithmetic (both scaled by the size of the type)
p[1] = 0xB;
*(p+1) = 0xB;
p = p + 2;
equivalent
22
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
&a[i] is the address of a[0] plus i times the element size in bytes
L03: Memory & Data II CMPT 295
Arrays in C
Declaration: int a[6];
Indexing:
No bounds checking:
Pointers:
a[0] = 0x015f;
a[5] = a[0];
a[6] = 0xBAD;
a[-1] = 0xBAD;
int* p; p = a;
0x0 0x8
0x1 0x9
0x2 0xA
0x3 0xB
0x4 0xC
0x5 0xD
0x6 0xE
0x7 0xF
AD
0B
00
00
0A
00
00
00
0B
00
00
00
0C
00
00
00
5F
01
00
00
AD
0B
00
00
18
00
00
00
00
00
00
00
equivalent p = &a[0]; a[0]
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
*p = 0xA;
a[2] a[4]
p
array indexing = address arithmetic (both scaled by the size of the type)
p[1] = 0xB;
*(p+1) = 0xB;
p = p + 2;
equivalent
*p = a[1] + 1;
23
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
&a[i] is the address of a[0] plus i times the element size in bytes
L03: Memory & Data II CMPT 295
Arrays Stored Differently Than Pointers
void foo() {
int *p, a[4], x;
p = &x;
*p = 1; // or p[0]
printf(“*p:%u, p:%u, &p:%u\n”,*p,p,&p);
*a = 2; // or a[0]
printf(“*a:%u, a:%u, &a:%u\n”,*a,a,&a);
}
… 0 4 8 12162024283236404448… … px
4?0
2?
1?
? 24
a
*p:1, p:40, &p:20
*a:2, a:24, &a:24
K&R: “An array__. name is not a variable”.
24
L03: Memory & Data II CMPT 295
Representing strings
! C-style string stored as an array of bytes (char*) ” Elements are one-byte ASCII codes for each character
” No “String” keyword, unlike Java
32 space 33 ! 34 ” 35 # 36 $ 37 % 38 & 39 ’ 40 ( 41 ) 42 * 43 + 44 , 45 – 46 . 47 /
48 0 49 1 50 2 51 3 52 4 53 5 54 6 55 7 56 8 57 9 58 : 59 ; 60 < 61 = 62 > 63 ?
64 @ 65 A 66 B 67 C 68 D 69 E 70 F 71 G 72 H 73 I 74 J 75 K 76 L 77 M 78 N 79 O
80 P 81 Q 82 R 83 S 84 T 85 U 86 V 87 W 88 X 89 Y 90 Z 91 [ 92 \ 93 ] 94 ^ 95 _
96 ` 97 a 98 b 99 c 100 d 101 e 102 f 103 g 104 h 105 I 106 j 107 k 108 l 109 m 110 n 111 o
112 p 113 q 114 r 115 s 116 t 117 u 118 v 119 w 120 x 121 y 122 z 123 { 124 | 125 } 126 ~ 127 del
ASCII: American Standard Code for Information Interchange
25
L03: Memory & Data II CMPT 295
Null-Terminated Strings
! Example: “Donald Trump” stored as a 13-byte array
Decimal:.. 68 Hex:.. 0x44
Text:.. D o n a l d T r u m p \0
! Last character followed by a 0 byte (‘\0’) (a.k.a. “null terminator”)
” Must take into account when allocating space in memory
” Note that ‘0’ ≠ ‘\0’ (i.e. character 0 has non-zero value)
! How do we compute the length of a string? ” Traverse array until null terminator encountered
111
110
97
108
100
32
84
114
117
109
112
0
0x6F
0x6E
0x61
0x6C
0x64
0x20
0x54
0x72
0x75
0x6D
0x70
0x00
26
L03: Memory & Data II CMPT 295
Endianness and Strings
C (char = 1 byte)
(big-endian)
0x00 ‘1’ 0x01 ‘2’ 0x02 ‘3’ 0x03 ‘4’ 0x04 ‘5’ 0x05 ‘\0’
char s[6] = “12345”; String literal
IA32, x86-64
(little-endian)
0x00 0x01 0x02 0x03 0x04 0x05
SPARC
31
32
33
34
35
00
31
32
33
34
35
00
0x31 = 49 decimal = ASCII ‘1’
! Byte ordering (endianness) is not an issue for 1-byte values
” The whole array does not constitute a single value
” Individual elements are values; chars are single bytes
27
L03: Memory & Data II CMPT 295
Examining Data Representations
! Code to print byte representation of data
” Any data type can be treated as a byte array by casting it to char ” C has unchecked casts !! DANGER !!
void show_bytes(char* start, int len) { int i;
for (i = 0; i < len; i++) printf("%p\t0x%.2x\n", start+i, *(start+i));
printf("\n");
}
printf directives:
%p Print pointer
\t Tab
%x Print value as hex \n New line
28
L03: Memory & Data II CMPT 295
Examining Data Representations
! Code to print byte representation of data
" Any data type can be treated as a byte array by casting it to char " C has unchecked casts !! DANGER !!
void show_bytes(char* start, int len) { int i;
for (i = 0; i < len; i++) printf("%p\t0x%.2x\n", start+i, *(start+i));
printf("\n");
}
void show_int(int x) {
show_bytes( (char *) &x, sizeof(int));
}
29
L03: Memory & Data II CMPT 295
show_bytes Execution Example
int x = 12345; // 0x00003039
printf("int x = %d;\n",x);
show_int(x); // show_bytes((char *) &x, sizeof(int));
! Result (Linux x86-64):
" Note: The addresses will change on each run (try it!), but fall in same general range
int x = 12345; 0x7fffb7f71dbc 0x39 0x7fffb7f71dbd 0x30 0x7fffb7f71dbe 0x00 0x7fffb7f71dbf 0x00
30
L03: Memory & Data II CMPT 295
Summary
! Assignment in C results in value being put in memory location
! Pointer is a C representation of a data address " & = “address of” operator
" * = “value at address” or “dereference” operator
! Pointer arithmetic scales by size of target type
" Convenient when accessing array-like structures in memory " Be careful when using – particularly when casting variables
! Arrays are adjacent locations in memory storing the same type of data object
" Strings are null-terminated arrays of characters (ASCII)
31
L03: Memory & Data II CMPT 295
Assignment in C - Handout
! left-hand side = right-hand side;
" LHS must evaluate to a location
" RHS must evaluate to a value
" Store RHS value at LHS location
! y = 0x3CD02700; ! x = y + 3;
! int* z = &y + 3; ! *z = y;
32-bit example (pointers are 32-bits wide)
& = “address of” * = “dereference”
0x00
0x01
0x02
0x03
0x00
0x04 ! x = 0; 0x08
! int x, y;
x
0x0C 0x10 0x14 0x18 0x1C 0x20 0x24
y
z
L03: Memory & Data II CMPT 295
Arrays in C - Handout
Declaration: int a[6];
Indexing:
No bounds checking:
a[0] = 0x015f;
a[5] = a[0];
a[6] = 0xBAD;
a[-1] = 0xBAD; 0x8
0x0 0x1 0x2 0x3 0x9 0xA 0xB
0x4 0x5 0x6 0x7 0xC 0xD 0xE 0xF
Pointers:
int* p; 0x00
p = a; 0x08 equivalent p = &a[0]; a[0] 0x10
*p = 0xA;
a[2] 0x18 a[4] 0x20 0x28 0x30 0x38 p 0x40 0x48
array indexing = address arithmetic (both scaled by the size of the type)
p[1] = 0xB;
*(p+1) = 0xB;
p = p + 2;
equivalent
*p = a[1] + 1;
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
&a[i] is the address of a[0] plus i times the element size in bytes