14.

Memory API
Operating System: Three Easy Pieces

Recommended readings:
https://pages.cs.wisc.edu/~remzi/OSTEP/vm-api.pdf

1
Types of memory

 In a C program, two types of memory allocated:

 Stack memory (called automatic memory)
 Allocations and deallocations managed implicitly by compiler for us

 E.g., statement “int x;” will allocate memory for an integer on stack

 When we return from the function, the compiler deallocates the memory

 For storing information beyond a function call, don’t use stack—use heap!
 All allocations and deallocations are explicitly handled by programmer

How can we allocate memory on heap?

2
Memory API: malloc()

 Inlcude stdlib.h #include <stdlib.h>

 To use malloc void* malloc(size_t size)

 Allocate a memory region on the heap.

 Argument
 size_t size : size of the memory block(in bytes)

 size_t is an unsigned integer type.

 Return
 Success : a void type pointer to the memory block allocated by malloc

 Fail : a null pointer

◼ In C, NULL is simply a macro for the value zero

3
sizeof()

 Routines and macros are utilized for size in malloc instead typing
in a number directly.

 E.g., to allocate space for a double variable

 double *d = (double *) malloc(sizeof(double));

 sizeof(double) is a compile-time operator—actual size (8, for double) is kn

own at compile time

4
sizeof()

 A variable name can also be passed to sizeof()

 But in some cases you may not get accurate results with this

 Two types of results of sizeof with variables

 Actual size of ‘x’ is known at run-time. Sizeof() returns int pointer’s size
int *x = malloc(10 * sizeof(int));
printf(“%d\n”, sizeof(x));

 The actual size of ‘x’ is known at compile-time.

int x[10];
printf(“%d\n”, sizeof(x));

40

5
Malloc() for strings

 When declaring space for a string, use

 malloc(strlen(s) + 1)

 Get the string length using strlen()

 Add one to make room for the end-of-string character

 Using sizeof for string may lead to inaccuracies

 Note: malloc() returns void*

 Simply a way in C to pass back an address and let the programmer decide
what to do with it.

How to deallocate the memory allocated using malloc()?

6
Memory API: free()

#include <stdlib.h>

void free(void* ptr)

 Simply call free() to free a memory region allocated by a call to

malloc.
 Argument
 void *ptr : a pointer to a memory block returned by malloc()

 Note that size of the allocated region is not passed

◼ Size tracked by the memory allocation library

 Return
 none

7
Memory Allocating

2KB
pointer

heap

(free)
stack int *pi; // local variable

*pi
16KB
Address Space

2KB
allocated
2KB + 4
allocated
2KB + 8
allocated
2KB + 12
allocated pi = (int *)malloc(sizeof(int)* 4);

(free)

2KB *pi
16KB
Address Space

8
Memory Freeing

2KB
freed
2KB + 4
freed
2KB + 8
freed
2KB + 12 free(pi);
freed

(free)

2KB(invalid) *pi
16KB
Address Space

2KB

heap

(free)
stack
What are some common errors in
the use of malloc(), free()?
2KB(invalid) *pi
16KB
Address Space

9
Forgetting To Allocate Memory

 Incorrect code
char *src = “hello”; //character string constant
char *dst; //unallocated
strcpy(dst, src); //segfault and die

Many functions, like strcpy(), hello\0

expect memory to be allocated
before we call them

heap
strcpy(dst, src);
(free) unallocated

stack

*dst
*src
Address Space

10
Forgetting To Allocate Memory(Cont.)

 Correct code
char *src = “hello”; //character string constant
char *dst (char *)malloc(strlen(src) + 1 ); // allocated
strcpy(dst, src); //work properly

hello\0 hello\0

allocated hello\0

strcpy(dst, src); heap heap

(free) (free)
stack stack

*dst *dst
*src *src
Address Space Address Space

11
Not Allocating Enough Memory (buffer overflow)

 Incorrect code, but may sometimes work properly

char *src = “hello”; //character string constant
char *dst (char *)malloc(strlen(src)); // too small
strcpy(dst, src); //may work properly

h
e
strlen l
6 bytes
l
o
\0
Why the progra
‘\0’ is omitted 5 bytes hello\0
m may run prope
rly sometimes?
strcpy(dst, src); heap
(free)
stack

*dst
*src
Address Space
Not Allocating Enough Memory (buffer overflow)

 Why the code on previous slide may run properly sometimes?

 The copy code will write one byte out of the end of allocated space

 Sometimes it may be overwriting a variable not in use anymore

 Sometimes the malloc library may allocate some extra space anyhow

 However,
 In some cases the program will indeed fault and crash

 These overflows can be extremely harmful and are often the source of sec
urity vulnerabilities in systems

13
Forgetting to Initialize

 Encounter an uninitialized read

int *x = (int *)malloc(sizeof(int)); // allocated

printf(“*x = %d\n”, *x); // uninitialized memory access

value used allocated

before with value used
(free) before

heap heap

(free) (free)

stack stack

*x *x
Address Space Address Space

14
Forgetting to free memory (memory leak)

 Forgetting to free dynamically allocated memory after its usefulness is

done leads to memory leaks

 In long running applications, systems

 Slowly leaking memory eventually leads one to run out of memory

 Eventually, a restart is required

 When you are done with a chunk of dynamically allocated memory, de

lete it using free()

 When a program terminates, OS cleans up all its allocated pages

 Hence no memory leak eventually for short-lived programs

 Nevertheless, good to get in habit of freeing all the dynamically allocated

memory

15
Memory Leak

 A program runs out of memory and eventually dies.

unused : unused, but not freed

allocated unused unused

allocated unused

heap heap
unused
heap
(free) allocated
(free)
stack (free)
stack *d
*c
*b *b
*a *a *a
Address Space Address Space Address Space

run out of memory

16
Dangling Pointer

 Freeing memory before program is finished using it creates dangling ptr

 A program accesses memory with an invalid pointer; could cause crash

*b free()
*b unreachable
*a *a

dangling pointer

2KB 2KB
3KB 3KB
3KB 4KB 3KB
freed
free(b)
4KB 4KB
NULL NULL
Heap Heap

(free) (free)

Stack Stack
*b 3KB *b 3KB
*a 2KB *a 2KB
Address Space Address Space

17
Double Free

 Free memory that was freed already.

int *x = (int *)malloc(sizeof(int)); // allocated
free(x); // free memory
free(x); // free repeatedly

2KB 2KB
allocated freed
Heap Heap
free(x) free(x)
Undefined
(free) (free)
Error
Stack Stack
2KB *x 2KB(invalid) Results are undefined.
16KB 16KB *x
Address Space Address Space Crashes are a
common outcome

18
System Calls

#include <unistd.h>

int brk(void *addr)

void *sbrk(intptr_t increment);

 malloc library call use brk system call.

 brk is called to expand the program’s break.
 break: The location of the end of the heap in address space

 sbrk is an additional call similar with brk.

 Programmers should never directly call either brk or sbrk.

19
Problem 1

 Consider the following line of code in a function of a process.

 int *x = (int *)malloc(10 * sizeof(int));

 When this function is invoked and executed, where is the memory for
the variable x allocated within the memory image of the process? (stac
k or heap?)

23
Problem 1 (solution)

 Consider the following line of code in a function of a process.

 int *x = (int *)malloc(10 * sizeof(int));

 When this function is invoked and executed, where is the memory for
the variable x allocated within the memory image of the process? (stac
k or heap?)

 Ans: stack

24
Problem 2

 Consider the following line of code in a function of a process.

 int *x = (int *)malloc(10 * sizeof(int));

 When this function is invoked and executed where is the memory for t
he 10 integer variables allocated within the memory image of the proc
ess? (stack/heap?)

25
Problem 2 (solution)

 Consider the following line of code in a function of a process.

 int *x = (int *)malloc(10 * sizeof(int));

 When this function is invoked and executed where is the memory for t
he 10 integer variables allocated within the memory image of the proc
ess? (stack/heap?)

 Ans: heap

26
Problem 3

 Consider the following piece of code:

 int *x = malloc(20 * sizeof(int));

 printf(“%d \n”, sizeof(x));

 What would be the output of the print statement printing the size of x
? Justify your answer. Assume the size of an integer is 4 bytes and size
of a pointer to int is also 4 B.

27
Problem 3 (solution)

 Consider the following piece of code:

 int *x = malloc(20 * sizeof(int));

 printf(“%d \n”, sizeof(x));

 What would be the output of the print statement printing the size of x
? Justify your answer. Assume the size of an integer is 4 bytes and size
of a pointer to int is also 4 B.

 4 B, since the memory using malloc is allocated at the run time. Size o
f pointer will be printed.

28
Problem 4

 Consider the following piece of code:

 int x[30];

 printf(“%d\n”, sizeof(x));

 What would be the output of the print statement printing the size of x
? Justify your answer. Assume the size of an integer is 4 bytes and size
of a pointer to int is also 4 B.

29
Problem 4 (solutions)

 Consider the following piece of code:

 int x[30];

 printf(“%d\n”, sizeof(x));

 What would be the output of the print statement printing the size of x
? Justify your answer. Assume the size of an integer is 4 bytes and size
of a pointer to int is also 4 B.

 120 B, since the size of the array x will be known at the compile time.

30