CS计算机代考程序代写 chain compiler scheme data structure c++ Java algorithm Roadmap

Roadmap

Review
Pointers and arrays are very similar
Strings are just char pointers/arrays with a null terminator at the end
Pointer arithmetic moves the pointer by the size of the thing it’s pointing to
Pointers are the source of many C bugs!

CMPT 295
Memory Allocation in C

Multiple Ways to Store Program Data
Static global data
Fixed size at compile-time
Entire lifetime of the program
(loaded from executable)
Portion is read-only
(e.g. string literals)
Stack-allocated data
Local/temporary variables
Can be dynamically sized (in some versions of C)
Known lifetime (deallocated on return)
Dynamic (heap) data
Size known only at runtime (i.e. based on user-input)
Lifetime known only at runtime (long-lived data structures)
2
int array[1024];

void foo(int n) {
int tmp;
int local_array[n];

int* dyn =
(int*)malloc(n*sizeof(int));
}

CMPT 295
Memory Allocation in C
Agenda
C Memory Layout
Stack, Static Data, and Code
Dynamic Memory Allocation
Heap
Common Memory Problems
C Wrap-up: Linked List Example

CMPT 295
Memory Allocation in C

C Memory Layout
Program’s address space
contains 4 regions:
Stack: local variables, grows downward
Heap: space requested via malloc() and used with pointers; resizes dynamically, grows upward
Static Data: global and static variables, does not grow or shrink
Code: loaded when program
starts, does not change

code
static data
heap
stack
~ FFFF FFFFhex
~ 0hex
OS prevents accesses
between stack and heap
(via virtual memory)

CMPT 295
Memory Allocation in C

Where Do the Variables Go?
Declared outside a function:
Static Data
Declared inside a function:
Stack
main() is a function
Freed when function returns
Dynamically allocated:
Heap
i.e. malloc (we will cover this shortly)

5
#include

int varGlobal;

int main() {
int varLocal;
int *varDyn =
malloc(sizeof(int));
}

CMPT 295
Memory Allocation in C

The Stack
Each stack frame is a contiguous block of memory holding the local variables of a single procedure
A stack frame includes:
Location of caller function
Function arguments
Space for local variables
Stack pointer (SP) tells where lowest (current) stack frame is
When procedure ends, stack pointer is moved back (but data remains (garbage!)); frees memory for future stack frames;

frame

frame
SP
…

Function call:
Function returns:
SP

CMPT 295
Memory Allocation in C

The Stack
Last In, First Out (LIFO) data structure
int main() {
a(0);
return 1; }
void a(int m) {
b(1); }
void b(int n) {
c(2);
d(4); }
void c(int o) {
printf(“c”); }
void d(int p) {
printf(“d”); }

stack

Stack Pointer
Stack grows down
Stack Pointer
Stack Pointer
Stack Pointer

CMPT 295
Memory Allocation in C

Stack Misuse Example
int *getPtr() {
int y;
y = 3;
return &y;
};
int main () {
int *stackAddr,content;
stackAddr = getPtr();
content = *stackAddr;
printf(“%d”, content); /* 3 */
content = *stackAddr;
printf(“%d”, content); /* ? */
};

8
What’s BAD about
this function?

main

getPtr()
(y==3)
SP

main
SP

main

printf()
(y==?)
SP
printf
overwrites
stack frame
stackAddr
Never return pointers to
local variable from functions

Your compiler will warn you about this
– don’t ignore such warnings!

CMPT 295
Memory Allocation in C
Maybe delete the /* 0 */

Program’s address space
contains 4 regions:
Stack: local variables, grows downward
Heap: space requested via malloc() and used with pointers; resizes dynamically, grows upward
Static Data: global and static variables, does not grow or shrink
Code: loaded when program
starts, does not change
C Memory Layout

code
static data
heap
stack
~ FFFF FFFFhex
~ 0hex
OS prevents accesses
between stack and heap
(via virtual memory)

CMPT 295
Memory Allocation in C
Duplicate slide and put it before talkng about specific section in detail

Static Data
Place for variables that persist
Data not subject to comings and goings like function calls
Examples: String literals, global variables
String literal example: char * str = “hi”;
Size does not change, but sometimes data can
Notably string literals cannot

10
Code
Copy of your code goes here
C code becomes data too!
Does not change

CMPT 295
Memory Allocation in C
Give example of string literal declaration

void funcA() {int x; printf(“A”);}
void funcB() {
int y;
printf(“B”);
funcA();
}
void main() {char *s = “s”; funcB();}
&x < &y (A) x and y are in adjacent frames (B) &x < s (C) y is in the 2nd frame from the top of the Stack (D) 11 Question: Which statement below is FALSE? All statements assume each variable exists. CMPT 295 Memory Allocation in C void funcA() {int x; printf(“A”);} void funcB() { int y; printf(“B”); funcA(); } void main() {char *s = “s”; funcB();} &x < &y (A) x and y are in adjacent frames (B) &x < s (C) y is in the 2nd frame from the top of the Stack (D) 12 Question: Which statement below is FALSE? All statements assume each variable exists. This is a string literal, and thus stored in STATIC DATA. Note: We’re talking about *s, not s, i.e. the location where s points! CMPT 295 Memory Allocation in C Addresses The size of an address (and thus, the size of a pointer) in bytes depends on architecture (eg: 32-bit Windows, 64-bit Mac OS) eg: for 32-bit, have 232 possible addresses If a machine is byte-addressed, then each of its addresses points to a unique byte word-addresses = address points to a word Question: on a byte-addressed machine, how can we order the bytes of an integer in mem? Answer: it depends 13 CMPT 295 Memory Allocation in C 13 Endianness Big Endian: Descending numerical significance with ascending memory addresses Little Endian Ascending numerical significance with ascending memory addresses 14 Source: https://en.wikipedia.org/wiki/Endianness CMPT 295 Memory Allocation in C Before this slide, add slide about byte -addressed machines and address’ meanings; Add Rotate egg and put into a shelf 28 Endianness In what order are the bytes within a data type stored in memory? Remember: 28 = 0x 00 00 00 1C Big Endian: Descending numerical significance with ascending memory addresses Little Endian Ascending numerical significance with ascending memory addresses 15 ... ... 0 4 8 12 16 20 24 28 32 36 40 44 48 … ... ... ? 16 17 18 19 20 21 22 23 24 25 26 27 28 … ? ? ? ? 1C 0 0 0 1C 0 CMPT 295 Memory Allocation in C Invert addresses for little endian example Common Mistakes Endianness ONLY APPLIES to values that occupy multiple bytes Endianness refers to STORAGE IN MEMORY NOT number representation Ex: char c = 97 c == 0b01100001 in both big and little endian Arrays and pointers still have the same order int a[5] = {1, 2, 3, 4, 5} (assume address 0x40) &(a[0]) == 0x40 && a[0] == 1 in both big and little endian 16 CMPT 295 Memory Allocation in C 16 Agenda C Memory Layout Stack, Static Data, and Code Administrivia Dynamic Memory Allocation Heap Common Memory Problems C Wrap-up: Linked List Example 17 CMPT 295 Memory Allocation in C C Memory Layout Program’s address space contains 4 regions: Stack: local variables, grows downward Heap: space requested via malloc() and used with pointers; resizes dynamically, grows upward Static Data: global and static variables, does not grow or shrink Code: loaded when program starts, does not change 18 code static data heap stack ~ FFFF FFFFhex ~ 0hex OS prevents accesses between stack and heap (via virtual memory) Program’s address space contains 4 regions: Stack: local variables, grows downward Heap: space requested via malloc() and used with pointers; resizes dynamically, grows upward Static Data: global and static variables, does not grow or shrink Code: loaded when program starts, does not change CMPT 295 Memory Allocation in C Duplicate slide and put it before talkng about specific section in detail Dynamic Memory Allocation Want persisting memory (like static) even when we don’t know size at compile time? e.g. input files, user input Stack won’t work because stack frames aren’t persistent Dynamically allocated memory goes on the Heap – more permanent than Stack Need as much space as possible without interfering with Stack Start at opposite end and grow towards Stack 19 CMPT 295 Memory Allocation in C sizeof() 20 If integer sizes are machine dependent, how do we tell? Use sizeof() function Returns size in bytes of variable or data type name Examples: int x; sizeof(x); sizeof(int); Acts differently with arrays and structs, which we will cover later Arrays: returns size of whole array Structs: returns size of one instance of struct (sum of sizes of all struct variables + padding) CMPT 295 Memory Allocation in C 20 Allocating Memory in C Need to #include
void* malloc(size_t size)
Allocates a continuous block of size bytes of uninitialized memory
Returns a pointer to the beginning of the allocated block; NULL indicates failed request
Typically aligned to an 8-byte (x86) or 16-byte (x86-64) boundary
Returns NULL if allocation failed (also sets errno) or size==0
Different blocks not necessarily adjacent
Related functions:
void* calloc(size_t nitems, size_t size)
“Zeros out” allocated block
void* realloc(void* ptr, size_t size)
Changes the size of a previously allocated block (if possible)
void* sbrk(intptr_t increment)
Used internally by allocators to grow or shrink the heap
21

CMPT 295
Memory Allocation in C
man 3 malloc
21
11/27/2017

Using malloc()
Almost always used for arrays or structs
Good practice to use sizeof() and typecasting
int *p = (int *) malloc(n*sizeof(int));
sizeof() makes code more portable
malloc() returns void *; typecast will help you catch coding errors when pointer types don’t match
Can use array or pointer syntax to access

CMPT 295
Memory Allocation in C

Releasing Memory
Release memory on the Heap using free()
Memory is limited, release when done
free(p)
Pass it pointer p to beginning of allocated block; releases the whole block
p must be the address originally returned by m/c/realloc(), otherwise throws system exception
Don’t call free() on a block that has already been released or on NULL
Make sure you don’t lose the original address
eg: p++ is a BAD IDEA; use a separate pointer

CMPT 295
Memory Allocation in C
freeing non heap = undef beahvior

End-to-End Example
24
void foo(int n, int m) {
int i, *p;
p = (int*) malloc(n*sizeof(int)); /* allocate block of n ints */
if (p == NULL) { /* check for allocation error */
perror(“malloc”);
exit(0);
}
for (i=0; i
typedef struct {
int x;
int y;
} point;
point *rect; /* opposite corners = rectangle */
…
if( !(rect=(point *) malloc(2*sizeof(point))) )
{
printf(“\nOut of memory!\n”);
exit(1);
}
…
free(rect);

25
Check for returned NULL
Do NOT change rect during this time!!!

CMPT 295
Memory Allocation in C
Remember to mention the malloc call and assignment

1 #define N 3
2 int *makeArray(int n) {
3 int *ar;
4 ar = (int *) malloc(n * sizeof(int));
5 return ar;
6 }
7 void main() {
8 int i,*a = makeArray(N);
9 for(i=0; inext != NULL)
head = head->next;
return head->val;
}

32
What if head
is NULL?
No warnings!
Just Seg Fault
that needs finding!

CMPT 295
Memory Allocation in C
Explicit memory management and pointer arithmetic present opportunities for designing compact and efficient programs. However, incorrect use of these features can lead to complex defects, such as a pointer referring to memory that you don’t own. In this case, too, reading memory through such pointers may give garbage value or cause segmentation faults and core dumps, and using garbage values can cause unpredictable program behavior or crashes.

Null Pointer Read/Write (NPR, NPW) and Zero Page Read/Write (ZPR, ZPW):
If a pointer’s value can potentially be null (NULL), the pointer should not be de-referenced without checking it for being null. For example, a call to malloc can return a null result if no memory is available. Before using the pointer returned by malloc, you need to check it to make sure that isn’t null. For example, a linked list or tree traversal algorithm needs to check whether the next node or child node is null.
It is common to forget these checks. Purify detects any memory access through de-referencing a null pointer, and reports an NPR or NPW error. When you see this error, examine whether you need to add a null pointer check or whether you wrongly assumed that your program logic guaranteed a non-null pointer. On AIX, HP, and under some linker options in Solaris, dereferencing a null pointer produces a zero value, not a segmentation fault signal.

The memory is divided into pages, and it is “illegal” to read from or write to a memory location on the zero’th page. This error is typically due to null pointer or incorrect pointer arithmetic computations. For example, if you have a null pointer to a structure and you attempt to access various fields of that structure, it will lead to a zero page read error, or ZPR.

Shows a simple example of both NPR and ZPR problems. The findLastNodeValue method has a defect, in that it does not check whether the head parameter is null. NPR and ZPR errors occur when the next and val fields are accessed, respectively.

Using Memory You Don’t Own (2)
What is wrong with this code?
char *append(const char* s1, const char *s2) {
const int MAXSIZE = 128;
char result[MAXSIZE];
int i=0, j=0;
for (; iname = malloc(sizeof(char)*strlen(name));
strcpy(person->name,name);
… // Do stuff (that isn’t buggy)
free(person);
free(person->name);

Accessing memory after you’ve freed it.
These statements should be switched.
Did not allocate space for the null terminator! Want (strlen(name)+1) here.

CMPT 295
Memory Allocation in C
Free Memory Read or Write (FMR, FMW):
When you use malloc or new, the operating system allocates memory from heap and returns a pointer to the location of that memory. When you don’t need this memory anymore, you de-allocate it by calling free. Ideally, after de-allocation, the memory at that location should not be accessed thereafter.
However, you may have more than one pointer in your program pointing to the same memory location. For instance, while traversing a linked list, you may have a pointer to a node, but a pointer to that node is also stored as next in the previous node. Therefore, you have two pointers to the same memory block. Upon freeing that node, these pointers will become heap dangling pointers, because they point to memory that has already been freed. Another common cause for this error is usage of realloc method. (See Listing 6 code.)
The heap management system may respond to another malloc call in the same program and allocate this freed memory to other, unrelated objects. If you use a dangling pointer and access the memory through it, the behavior of the program is undefined. It may result in strange behavior or crash. The value read from that location would be completely unrelated and garbage. If you modify memory through a dangling pointer, and later that value is used for the intended purpose and unrelated context, the behavior will be unpredictable. Of course, either an uninitialized pointer or incorrect pointer arithmetic can also result in pointing to already freed heap memory.

Using Memory You Haven’t Allocated
What is wrong with this code?

void StringManipulate() {
const char *name = “Safety Critical”;
char *str = malloc(sizeof (char) * 10);
strncpy(str, name, 10);
str[10] = ‘\0’;
printf(“%s\n”, str);
}

35
Write beyond array bounds
Read beyond array bounds

CMPT 295
Memory Allocation in C
Using memory that you haven’t allocated, or buffer overruns
When you don’t do a boundary check correctly on an array, and then you go beyond the array boundary while in a loop, that is called buffer overrun. Buffer overruns are a very common programming error resulting from using more memory than you have allocated. Purify can detect buffer overruns in arrays residing in heap memory, and it reports them as array bound read (ABR) or array bound write (ABW) errors. (See Listing 8.)

Using Memory You Haven’t Allocated
What is wrong with this code?

char buffer[1024]; /* global */
int foo(char *str) {
strcpy(buffer,str);
…
}

36
What if more than
a kibi characters?
This is called BUFFER OVERRUN or BUFFER OVERFLOW and is a security flaw!!!

Freeing Invalid Memory
What is wrong with this code?
void FreeMemX() {
int fnh = 0;
free(&fnh);
}
void FreeMemY() {
int *fum = malloc(4*sizeof(int));
free(fum+1);
free(fum);
free(fum);
}

37
1) Free of a Stack variable
2) Free of middle of block
3) Free of already freed block

CMPT 295
Memory Allocation in C
Freeing invalid memory:
This error occurs whenever you attempt to free memory that you are not allowed to free. This may happen for various reasons: allocating and freeing memory through inconsistent mechanisms, freeing a non-heap memory (say, freeing a pointer that points to stack memory), or freeing memory that you haven’t allocated. When using Purify for the Windows platform, all such errors are reported as freeing invalid memory (FIM). On the UNIX® system, Purify further classifies these errors by reporting freeing mismatched memory (FMM), freeing non-heap memory (FNH), and freeing unallocated memory (FUM) to indicate the exact reason for the error.
Freeing mismatched memory (FMM) is reported when a memory location is de-allocated by using a function from a different family than the one used for allocation. For example, you use new operator to allocate memory, but use method free to de-allocate it. Purify checks for the following families, or matching pairs:
malloc() / free()
calloc() / free()
realloc() / free()
operator new / operator delete
operator new[] / operator delete[]
Purify reports any incompatible use of memory allocation and de-allocation routine as an FMM error. In the example in Listing 11, the memory was allocated using the malloc method but freed using the delete operator, which is not the correct counterpart, thus incompatible. Another common example of an FMM error is C++ programs that allocate an array using the new[] operator, but free the memory using a scalar delete operator instead of array delete[] operator. These errors are hard to detect through code inspection, because the memory allocation and de-allocation locations may not be located close to each other, and because there is no difference in syntax between an integer pointer and a pointer to an integer array.

Memory Leaks
What is wrong with this code?
int *pi;
void foo() {
pi = (int*)malloc(8*sizeof(int));
…
free(pi);
}
void main() {
pi = (int*)malloc(4*sizeof(int));
foo();
}

38
foo() leaks memory
Overrode old pointer!
No way to free those 4*sizeof(int) bytes now

CMPT 295
Memory Allocation in C
Using faulty heap memory management
Explicit memory management in C and C++ programming puts the onus of managing memory on the programmers. Therefore, you must be vigilant while allocating and freeing heap memory. These are the common memory management mistakes:
Memory leaks and potential memory leaks (MLK, PLK, MPK)
Freeing invalid memory (FIM)
Freeing mismatched memory (FMM)
Freeing non-heap memory (FNH)
Freeing unallocated memory (FUM)
Memory leaks and potential memory leaks:
When all pointers to a heap memory block are lost, that is commonly called a memory leak. With no valid pointer to that memory, there is no way you can use or release that memory. You lose a pointer to a memory when you overwrite it with another address, or when a pointer variable goes out of the scope, or when you free a structure or an array that has pointers stored in it. Purify scans all of the memory and reports all memory blocks without any pointers pointing to them as memory leaks (MLK). In addition, it reports all blocks as potential leaks, or PLK (called MPK on Windows platforms) when there are no pointers to the beginning of the block but there are pointers to the middle of the block.
Linsting 9 shows a simple example of a memory leak and a heap dangling pointer. In this example, interestingly, methods foo and main independently seem to be error-free, but together they manifest both errors. This example demonstrates that interactions between methods may expose multiple flaws that you may not find simply by inspecting individual functions. Real-world applications are very complex, thus tedious and time-consuming for you to inspect and to analyze the control flow and its consequences. Using Purify gives you vital help in detecting errors in such situations.
First, in the method foo, the pointer pi is overwritten with a new memory allocation, and all pointers to the old memory block are lost. This results in leaking the memory block that was allocated in method main. Purify reports a memory leak (MLK) and specifies the line where the leaked memory was allocated. It eliminates the slow process of hunting down the memory block that is leaking, therefore shortens the debugging time. You can start debugging at the memory allocation site where the leak is reported, and then track what you are doing with that pointer and where you are overwriting it.
Later, the method foo frees up the memory it has allocated, but the pointer pi still holds the address (it is not set to null). After returning from method foo to main, when you use the pointer pi, it refers to the memory that has already been freed, so pi becomes a dangling pointer. Purify promptly reports a FMW error at that location.

Memory Leaks
Remember that Java has garbage collection but C doesn’t
Memory Leak: when you allocate memory but lose the pointer necessary to free it
Rule of Thumb: More mallocs than frees probably indicates a memory leak
Potential memory leak: Changing pointer – do you still have copy to use with free later?

plk = (int *)malloc(2*sizeof(int));
…
plk++;

39
Mem Leak! Typically happens through incrementation or reassignment

CMPT 295
Memory Allocation in C
Listing 10 shows an example of a potential memory leak. After incrementing pointer plk, it points to the middle of the memory block, but there is no pointer pointing to the beginning of that memory block. Therefore, a potential memory leak is reported at the memory allocation site for that block.

Agenda
C Memory Layout
Stack, Static Data, and Code
Administrivia
Dynamic Memory Allocation
Heap
Common Memory Problems
C Wrap-up: Linked List Example

CMPT 295
Memory Allocation in C

Linked List Example
We want to generate a linked list of strings
This example uses structs, pointers, malloc(), and free()
Create a structure for nodes of the list:
struct Node {
char *value;
struct Node *next;
} node;

41
The link of the linked list

CMPT 295
Memory Allocation in C

Adding a Node to the List
Want to write addNode to support functionality as shown:
char *s1 = “start”, *s2 = “middle”,
*s3 = “end”;
struct node *theList = NULL;
theList = addNode(s3, theList);
theList = addNode(s2, theList);
theList = addNode(s1, theList);

42
If you’re more familiar with Lisp/Scheme, you could name this function cons instead.
Must be able to
handle a
NULL input
In what part of
memory are
these stored?

CMPT 295
Memory Allocation in C

Adding a Node to the List
Let’s examine the 3rd call (“start”):
node *addNode(char *s, node *list) {
node *new =(node *) malloc(sizeof(NodeStruct));
new->value = (char *) malloc (strlen(s) + 1);
strcpy(new->value, s);
new->next = list;
return new;
}

43
s:
list:
new:

NULL
“start”
“middle”
“end”

?
?
???
“start”
Don’t forget this for the null terminator!
theList:

CMPT 295
Memory Allocation in C

Removing a Node from the List
Delete/free the first node (“start”):
node *deleteNode(node *list) {
node *temp = list->next;
free(list->value);
free(list);
return temp;
}

44
list:

NULL
“middle”
“end”

“start”
???
temp:

???

What happens if you do these in the wrong order?
theList:

CMPT 295
Memory Allocation in C

Additional Functionality
How might you implement the following?
Append node to end of a list
Delete/free an entire list
Join two lists together
Reorder a list alphabetically (sort)

CMPT 295
Memory Allocation in C

Summary
C Memory Layout
Stack: local variables (grows & shrinks in LIFO manner)
Static Data: globals and string literals
Code: copy of machine code
Heap: dynamic storage using malloc and free
The source of most memory bugs!
Common Memory Problems
Last C Lecture!

code
static data
heap
stack
~ FFFF FFFFhex
~ 0hex
OS prevents accesses
between stack and heap
(via virtual memory)

CMPT 295
Memory Allocation in C
picture of mem layout for the last time

/docProps/thumbnail.jpeg

Related Posts