| Home | Classes | Papers | Essays | Short Fiction | About |

CS211: Memory

Table of Contents

Introduction

Programmers never die

They just lose their memory — Desk tchotchke I own

We now know that data is a fundamental abstraction which is necessary for the completion of computing tasks. By definition, it would be absurd to conceive of performing computations if there was no data to perform computations on. Logically, considering our computers are physical devices which hold physical information, it would follow that if we need to perform computations with data it must be had from somewhere. We call that "somewhere" memory.

What is Memory?

One possible definition of memory, provided by David Patterson and John Hennessy in their classic introductory text Computer Organization and Design, goes as follows: "Memory is where the programs are kept when they are running; it also contains the data needed by the running programs." That is to say that memory is a location. It is some space within the components that make up a computer. The simple term "memory" itself is often ambiguous when devoid of context; as it turns out, there's many different kinds of memory and devices which act as computer memory. For example, there's volatile and non-volatile memory, main and secondary memory, virtual and physical memory, etc. Functionally, memory is anything that cannot be stored purely in the CPU—specifically within its registers. Although there are many registers on the average x86-64 chip, all of them combined could not store the entirety of gcc.

Memory Hierarchy

Again, when we refer to "memory" its often a shorthand for a wide variety of components inside of the computer. These components can be arranged to form a memory hierarchy: 

+--------------------------------------------------+
|                      CPU                         |
|                                 [VOLATILE]       |
|   +------------------+                           |
|   |    Registers     |  <- Fastest, smallest     |
|   +------------------+        (~bytes)           |
|           |                                      |
|   +------------------+                           |
|   |    L1 Cache      |  <- (~KB)                 |
|   +------------------+                           |
|           |                                      |
|   +------------------+                           |
|   |    L2 Cache      |  <- (~MB)                 |
|   +------------------+                           |
|           |                                      |
|   +------------------+                           |
|   |    L3 Cache      |  <- (~MB)                 |
|   +------------------+                           |
|           |                                      |
+-----------|--------------------------------------+
            |
    +------------------+
    |   Main Memory    |  <- (~GB)          [VOLATILE]
    |      (RAM)       |
    +------------------+
            |
- - - - - - - - - - - - - - - - - - - - - - - - - -
            |                            [NON-VOLATILE]
    +------------------+
    |    Secondary     |  <- Slowest, largest
    |  Storage (Disk)  |        (~TB)
    +------------------+

The closer a component is to the CPU, the easier it is to retrieve information from it. Additionally, read/write speeds exist in an inverse relationship to cost and storage size. Very fast components, like registers, are as speedy as they are because they cannot store much information. This has to do with the physical make-up of memory devices (something that is outside the scope of this class to get into).

Additionally, there is a split between volatile and non-volatile memory. Volatile memory refers to memory components which lose their charge (data retention) after they are powered down. Dynamic random access memory, or DRAM, is one such example1—CPU registers and caches are another. Non-volatile memory is constructed in such a way that cells are capable of storing information long after the device is powered down. Non-volatile memory components, like solid-state drives (SSDs) and hard disk drives (HDDs), are the reason we can shut off our computers and turn them on again without losing precious files and programs.

Memory Semantics

What matters most to us as C programmers right now, is not so much the innerworkings of memory devices, but rather how the C runtime interacts with memory (how it is read, written, allocated, and deallocated). In the programming language community, we call that sort of behavior the memory semantics of a language. Luckily for us, C is about as "bare metal" as most high-level programming languages get, which means it doesn't take to much to describe its semantics. We can categorize data in our C runtime under two umbrellas: statically allocated memory and dynamically allocated memory.

Statically Allocated Memory

Statically allocated memory refers to memory that is available at the start of the program's runtime—meaning it has already been allocated by the time it has been compiled and linked into an executable.

Global Variables

Variables declared in the global scope must be allocated before the execution of a program. These variables must be reachable by any and all functions that reference them. 

 1: int g = 100;
 2: 
 3: int foo(int a, int b){
 4:   int x, y, val;
 5:   //....
 6:   return val;
 7: }
 8: 
 9: int goo(int c, int d){
10:   int t, u, val;
11:   //...
12:   return val + g;
13: }
14: 
15: int main(){
16:   goo(1,2);
17: }

In Listing 2 we see a global variable g declared at the top. We also see three functions defined: foo, goo, and main. Neither main nor foo uses g, but they could have. Since g was defined in the global scope, any function is capable of referencing it. This necessitates the compiler reserving space a priori for any location in the code that may want to reference it.

String Constants

Think back to our first program in class, hello_world.c, represented below: 

1: #include <stdio.h>
2: int main(){
3:   printf("Hello, World!\n");
4: }

I had mentioned that the characters contained within the quotation marks were called a string. The colloquial type refers to the "string" of characters contained within the phrase. It so happens that these characters are stored in what's called "read-only" memory within the executable file. Let's take a look at the assembly dump of the .c file (using gcc -O0 -fno-omit-frame-pointer -fno-stack-protector -S hello_world.c): 

 1:         .file   "hello_world.c"
 2:         .text
 3:         .section        .rodata
 4: .LC0:
 5:         .string "Hello, World!"
 6:         .text
 7:         .globl  main
 8:         .type   main, @function
 9: main:
10: .LFB0:
11:         .cfi_startproc
12:         endbr64
13:         pushq   %rbp
14:         .cfi_def_cfa_offset 16
15:         .cfi_offset 6, -16
16:         movq    %rsp, %rbp
17:         .cfi_def_cfa_register 6
18:         leaq    .LC0(%rip), %rdi
19:         call    puts@PLT
20:         movl    $0, %eax
21:         popq    %rbp
22:         .cfi_def_cfa 7, 8
23:         ret
24:         .cfi_endproc
25: .LFE0:
26:         .size   main, .-main
27:         .ident  "GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0"
28:         .section        .note.GNU-stack,"",@progbits
29:         .section        .note.gnu.property,"a"
30:         .align 8
31:         .long    1f - 0f
32:         .long    4f - 1f
33:         .long    5
34: 0:
35:         .string  "GNU"
36: 1:
37:         .align 8
38:         .long    0xc0000002
39:         .long    3f - 2f
40: 2:
41:         .long    0x3
42: 3:
43:         .align 8
44: 4:

We can see on Line 3 the assembly code defines a section called .rodata which stands for "read only data". Lines 5 and 6 define the string constant "Hello, World!" which is later referenced on Line 18 for the call to printf (again, printf is optimized away and replaced by puts). If I were to add some code which tries to alter the string directly, by replacing "Hello, World!" with "Jello, World!", we'll find it doesn't work as expected: 

1: #include <stdio.h>
2: int main(){
3:   char * msg = "Hello, World!\n";
4:   msg[0] = 'J'; // Trying to reset the first character of the string
5:   printf("%s", msg);
6: }

Now if I try to compile and run that: 

josephraskind@stargazer:/tmp/mem$ gcc -O0 -fno-omit-frame-pointer -fno-stack-protector jello_world.c -o jello_world
josephraskind@stargazer:/tmp/mem$ ./jello_world 
Segmentation fault (core dumped)

I get a strange error! This happened because I tried to edit, or write to, memory that was set to read only. We'll learn more about this when we discuss pointers.

static Keyword

This one is a bit of a subtle point which I've added for completeness.

Variables tagged with the static keyword variables take on the same behavior as global variables do regarding memory allocation, although their lexical scope remains within the block they were defined in. Here is an example: 

 1: #include <stdio.h>
 2: 
 3: int foo(){
 4:   static int x = 100;
 5:   x = x + 1;
 6:   return x;
 7: }
 8: 
 9: int main(){
10:   printf("1st call to foo(): %d\n", foo());
11:   printf("2nd call to foo(): %d\n", foo());
12: }

Notice I have prefixed the static tag to my int declaration on Line 4. Now we can compile and run the code (): 

josephraskind@stargazer:/tmp/mem$ gcc static.c -o static; ./static
1st call to foo(): 101
2nd call to foo(): 102

How is this possible?! Again, turning to assembly will help us out (gcc -O0 -fno-omit-frame-pointer -fno-stack-protector -S static.c): 

 1:         .file   "static.c"
 2:         .text
 3:         .globl  foo
 4:         .type   foo, @function
 5: foo:
 6: .LFB0:
 7:         .cfi_startproc
 8:         endbr64
 9:         pushq   %rbp
10:         .cfi_def_cfa_offset 16
11:         .cfi_offset 6, -16
12:         movq    %rsp, %rbp
13:         .cfi_def_cfa_register 6
14:         movl    x.2315(%rip), %eax
15:         addl    $1, %eax
16:         movl    %eax, x.2315(%rip)
17:         movl    x.2315(%rip), %eax
18:         popq    %rbp
19:         .cfi_def_cfa 7, 8
20:         ret
21:         .cfi_endproc
22: .LFE0:
23:         .size   foo, .-foo
24:         .section        .rodata
25: .LC0:
26:         .string "1st call to foo(): %d\n"
27: .LC1:
28:         .string "2nd call to foo(): %d\n"
29:         .text
30:         .globl  main
31:         .type   main, @function
32: main:
33: .LFB1:
34:         .cfi_startproc
35:         endbr64
36:         pushq   %rbp
37:         .cfi_def_cfa_offset 16
38:         .cfi_offset 6, -16
39:         movq    %rsp, %rbp
40:         .cfi_def_cfa_register 6
41:         movl    $0, %eax
42:         call    foo
43:         movl    %eax, %esi
44:         leaq    .LC0(%rip), %rdi
45:         movl    $0, %eax
46:         call    printf@PLT
47:         movl    $0, %eax
48:         call    foo
49:         movl    %eax, %esi
50:         leaq    .LC1(%rip), %rdi
51:         movl    $0, %eax
52:         call    printf@PLT
53:         movl    $0, %eax
54:         popq    %rbp
55:         .cfi_def_cfa 7, 8
56:         ret
57:         .cfi_endproc
58: .LFE1:
59:         .size   main, .-main
60:         .data
61:         .align 4
62:         .type   x.2315, @object
63:         .size   x.2315, 4
64: x.2315:
65:         .long   100
66:         .ident  "GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0"
67:         .section        .note.GNU-stack,"",@progbits
68:         .section        .note.gnu.property,"a"
69:         .align 8
70:         .long    1f - 0f
71:         .long    4f - 1f
72:         .long    5
73: 0:
74:         .string  "GNU"
75: 1:
76:         .align 8
77:         .long    0xc0000002
78:         .long    3f - 2f
79: 2:
80:         .long    0x3
81: 3:
82:         .align 8
83: 4:

We can see on Line 60 a new section called .data is demarcated. .data refers to read/write memory. Lines 64 and 65 provide the label and starting value associated with the static int x defined in Listing 7 (the label name is a "mangled" version of the original variable name to separate it from other potential static variables named x in other lexical scopes). Lines 14-16 show the increment and store operation broken up into three instructions (load, add, and store). Even though the variable was defined within the local function scope it has a program-long shelf life due to the static keyword.

Dynamically Allocated Memory

Dynamically allocated memory refers to memory that is not available at the start of the program's runtime—meaning it must be allocated and set during the program's execution. There are two runtime memory data structures used to handle dynamic memory: the stack and the heap.

Stack

The stack is the primary method of dynamic allocation that we have interacted with so far. Almost all of our variables have been placed and manipulated on the stack without our involvement. This is because the C compiler is responsible for manageing the stack—i.e. reserving space, pushing the frame pointer, popping unneeded values, etc. A short example to illustrate the point: 

 1: #include <stdio.h>
 2: 
 3: void print_bool(int b){
 4:   b? printf("True\n") : printf("False\n");
 5: }
 6: 
 7: int is_negative(int n){
 8:   return n < 0;
 9: }
10: 
11: int main(){
12:   int x = 1;
13:   int y = -1;
14:   print_bool(is_negative(x));
15:   print_bool(is_negative(y));
16: }

Above we have a program which checks to see if two variables, x and y, are negative and then prints "True" or "False" depending on the outcome. We can take a look at the assembly genrated here (gcc -O0 -fno-omit-frame-pointer -fno-stack-protector -S is_negative.c): 

 1:         .file   "is_negative.c"
 2:         .text
 3:         .section        .rodata
 4: .LC0:
 5:         .string "True\n"
 6: .LC1:
 7:         .string "False\n"
 8:         .text
 9:         .globl  print_bool
10:         .type   print_bool, @function
11: print_bool:
12: .LFB0:
13:         .cfi_startproc
14:         endbr64
15:         pushq   %rbp
16:         .cfi_def_cfa_offset 16
17:         .cfi_offset 6, -16
18:         movq    %rsp, %rbp
19:         .cfi_def_cfa_register 6
20:         subq    $16, %rsp
21:         movl    %edi, -4(%rbp)
22:         cmpl    $0, -4(%rbp)
23:         je      .L2
24:         leaq    .LC0(%rip), %rdi
25:         movl    $0, %eax
26:         call    printf@PLT
27:         jmp     .L4
28: .L2:
29:         leaq    .LC1(%rip), %rdi
30:         movl    $0, %eax
31:         call    printf@PLT
32: .L4:
33:         nop
34:         leave
35:         .cfi_def_cfa 7, 8
36:         ret
37:         .cfi_endproc
38: .LFE0:
39:         .size   print_bool, .-print_bool
40:         .globl  is_negative
41:         .type   is_negative, @function
42: is_negative:
43: .LFB1:
44:         .cfi_startproc
45:         endbr64
46:         pushq   %rbp
47:         .cfi_def_cfa_offset 16
48:         .cfi_offset 6, -16
49:         movq    %rsp, %rbp
50:         .cfi_def_cfa_register 6
51:         movl    %edi, -4(%rbp)
52:         movl    -4(%rbp), %eax
53:         shrl    $31, %eax
54:         movzbl  %al, %eax
55:         popq    %rbp
56:         .cfi_def_cfa 7, 8
57:         ret
58:         .cfi_endproc
59: .LFE1:
60:         .size   is_negative, .-is_negative
61:         .globl  main
62:         .type   main, @function
63: main:
64: .LFB2:
65:         .cfi_startproc
66:         endbr64
67:         pushq   %rbp
68:         .cfi_def_cfa_offset 16
69:         .cfi_offset 6, -16
70:         movq    %rsp, %rbp
71:         .cfi_def_cfa_register 6
72:         subq    $16, %rsp
73:         movl    $1, -4(%rbp)
74:         movl    $-1, -8(%rbp)
75:         movl    -4(%rbp), %eax
76:         movl    %eax, %edi
77:         call    is_negative
78:         movl    %eax, %edi
79:         call    print_bool
80:         movl    -8(%rbp), %eax
81:         movl    %eax, %edi
82:         call    is_negative
83:         movl    %eax, %edi
84:         call    print_bool
85:         movl    $0, %eax
86:         leave
87:         .cfi_def_cfa 7, 8
88:         ret
89:         .cfi_endproc

We detailed the calling convention in the lecture on functions, so I'll spare the overly detailed process here. Suffice it to say that it can be seen that %rbp, or the base/frame pointer register, is often being manipulated at the beginning of functions and anytime there should be an instruction where a local variable is being manipulated.

Heap

We'll learn more about the heap later when we discuss pointers. You can think of the heap as "the other stack", which it more or less is. The only difference is the heap is persistent between function calls, unlike the stack which is often riddled with pushes and pops that allow for old memory to be overwritten without programmer input.

Default Values

We know by now that variables do not need to be initialized with a value. By what are the values associated with an uninitialized variable? It turns out in C the behavior is undefined. If we declare a variable, say, int x;, we cannot guarantee the value that will contained in x. We can see that represented by compiling a simple C program, 

1: int main(){
2:   int x;
3:   int y = 10;
4:   return x + y;
5: }

Which can be compiled down into assembly (gcc -O0 -fno-omit-frame-pointer -fno-stack-protector -S uninit.c): 

 1: main:
 2: .LFB0:
 3:         .cfi_startproc
 4:         endbr64
 5:         pushq   %rbp
 6:         .cfi_def_cfa_offset 16
 7:         .cfi_offset 6, -16
 8:         movq    %rsp, %rbp
 9:         .cfi_def_cfa_register 6
10:         movl    $10, -4(%rbp)
11:         movl    -8(%rbp), %edx
12:         movl    -4(%rbp), %eax
13:         addl    %edx, %eax
14:         popq    %rbp
15:         .cfi_def_cfa 7, 8
16:         ret

We can see that on Line 10 a constant value of 10 was moved into -4(%rbp), the stack location for y. However, there's no equivalent movement for -8(%rbp) (the stack location for x). This means that x will store whatever value happens to be in that memory location at startup!

Exercises

  1. The lecture shows that trying to modify a string constant causes a segmentation fault as in Listing 6. Compile and run Listing 5 yourself and confirm the segfault. Then look at the assembly from Listing 9 and identify which section directive indicates that the string is stored in read-only memory. Why does the OS enforce this protection?
  2. Compile Listing 7 and run it. Then remove the static keyword from the declaration of x and recompile. What changes in the output? Explain why in terms of storage duration.
  3. Looking at the assembly in Listing 9, identify the label and section used to store the string constant "Hello, World!". Now write a C program with two string constants and compile it to assembly. How many .rodata entries are produced?
  4. The assembly for the static variable in Listing 9 uses a mangled name x.2315 instead of just x. Why does the compiler do this? What problem would arise if it used the plain name x instead?
  5. Write a C program with two functions where the first function declares a local variable, sets it to a known value, and returns. The second function then declares a local variable without initializing it and prints it. Call them in sequence from main. Based on what you know about how the stack works from Listing 11, predict what value the uninitialized variable might hold and explain why. Does the output match your prediction? What does this tell you about relying on uninitialized variables?
  6. The lecture states that the heap is "persistent between function calls" unlike the stack. Based on what you know about how the stack works from the assembly in Listing 11, explain in your own words why local variables do not persist between function calls.
  7. Write a C program with a static local variable inside a function that counts how many times that function has been called, printing the count each time. Call it five times from main. Compile to assembly and identify where in the assembly the static variable is stored compared to the local variables.
  8. The lecture states that global variables must be reachable by any function that references them. Write a program based on Listing 2 that has two functions both modifying the same global variable and print it after each modification. What does this demonstrate about the risks of using global variables?
  9. Looking at Listing 13, the assembly shows no instruction initializing -8(%rbp) for the uninitialized variable x. Compile the same program with gcc -Wall and record the warning produced. Then initialize x to 0 and recompile to assembly — what new instruction appears?
  10. The lecture distinguishes between statically and dynamically allocated memory. Categorize each of the following as static or dynamic and justify your answer:
    • A const int declared at the top of a file
    • A loop counter int i declared inside main
    • A static int declared inside a function
    • The string "CS211" passed directly to printf
    • A function argument int x

Footnotes:

1

Back in the day, giant tubes filled with mercury called "mercury delay lines" were used as volatile memory.

Previous | Index | Next

Contact: [email protected] | rss feed | Compiled with org-mode | Licensed under CC BY-NC-SA 4.0