1.4 C Memory Mangement, Usage

resources

ppt youtube

Review

指针

• 指针是抽象的机器存储地址

• 指针在 memory 中，并且指针变量是可以被软件操作的数字

• C 的 array name 和指针有很近关系

• 指针知道指向对象的类型 （除了void *）

  C strings

• String in C is just an array of characters

  char string[] = "abc";

• 计算 string 长度

  • Last character is followed by a 0 byte(aka "null terminator")

    int strlen(char s[]) {
    int n = 0;
    while(s[n] != 0) n++;
    return n;
    }

    Concise strlen()

    int strlen(char *s) {
    char *p = s;
    while(*p++);
    return (p-s-1);
    }

    Vaild Pointer Arithmetic

• pointer + integer

• pointer - pointer

• compare pointers(<,<=,==,!=,>,>=)

• compare pointer to NULL

illegal

• pointer + pointer

• pointer * pointer

• interger - pointer

main 的参数

int main(int args,char *argv[])

• args 是 strings 的个数

• argv is a pointer to an array containing the arguments as strings

  foo hello 87
  argc = 3
  argv[0] = "foo",
  argv[1] = "hello",
  argv[2] = "87"

  • Array of pointers to strings

C Memory Management

• C编译器如何确定将所有变量放入机器内存的位置？

• 如何创建 动态调整大小 的对象？

• 为了简化讨论，我们假设一次运行一个程序，其可以访问所有内存。

• 稍后，我们将讨论虚拟内存，它允许多个程序同时运行，每个程序都认为自己拥有所有内存。

内存地址如下图（假设32bits）

~FFFF FFFF(hex) stack
⬇
/////////////////////
/////////////////////
/////////////////////
⬆
heap
staic data
~0000 0000(hex) code

• 程序的地址空间包含4个区域：

  • stack: 函数内的局部变量，向下增长

  • heap: 通过malloc()为动态数据请求的空间；动态调整大小，向上增长

  • static data: 在函数外部声明的变量。不会增大或缩小。程序启动时加载，可以修改

  • code: 程序启动时加载，不会更改

举例：

int myGlobal;
main() {
    int myTemp;
}

• 如果在 function 外部声明，则分配在 “static data” 存储中

• 如果在函数 内部 声明，则在“stack”上分配，并在函数 return 时 free

  • main() 被认为是一个 function

提问： 如果在 function 外声明 array 并尝试在 function 内调整其大小？ 在 function 外声明 array 将是 static 的，因此无法 resize。

The stack

fooA() {
    fooB();
}
fooB() {
    fooC();
}
fooC() {
    fooD();
}

fooA frame
fooB frame
fooC frame
fooD frame
Stack Point ⬇

• 每次调用 function 时，都会在 stack 上分配一个 frame

• Stack frame 包括

  • Return address(who called me?)

  • Arguments

  • local variables 的空间

• stack frame 是连续内存块；Stack Point 指示stack frame 的开始

• function 结束时，Stack frame 将被抛出Stack；free 内存以供将来的堆栈帧使用

• 我们将在稍后介绍MIPS处理器的详细信息

管理 heap

C 为管理 heap 提供了五个方法:

• malloc() 分配一块未初始化的内存块

• calloc() 分配一块 zeroed 的内存块

• free() 释放先前分配的内存块

• cfree() 别用，用free()

• realloc() 更改以前分配的块的大小，会重新分配位置。 careful - it might move!

Malloc()

• void *malloc(size_t n):

  • size_t 是一种 unsigned integer, 取值大到足以“计算”内存 bytes ,与操作系统有关 x64是2^64

  • 注意：后续调用可能不会在连续地址中产生块

  • n ：分配内存的大小，以 bytes 为单位

  • sizeof 返回给定类型的大小(以bytes 为单位)

  • 返回void*指向块的指针；NULL返回表示没有更多内存

  • 可以将 pointer 视为描述所分配的内存块的 handle(门把手)；额外的控制信息存储在 heap（在所分配的 block 周围） 中。

例子：

int *ip;
ip = (int *) malloc(sizeof(int));

typedef struct { … } TreeNode;
TreeNode *tp = (TreeNode *) malloc(sizeof(TreeNode));

• void free(void *p):

  • 释放由 malloc() 收集的内存

  • p 是指针，含由 malloc() originally（本来得） 返回的地址

    int *ip;
    ip = (int *) malloc(sizeof(int));
    ... .. ..
    free((void*) ip);    /* Can you f(ip) after ip++ ? NO */

typedef struct {… } TreeNode;
TreeNode *tp = (TreeNode *) mal(sizeof(TreeNode));
    ... .. ..
free((void *) tp);

• • 当没用足够内存，malloc() 返回 NULL指针。

/* CHECK FOR IT! */
if ((ip = (int *) malloc(sizeof(int))) == NULL){
    printf(“\nMemory is FULL\n”);
    exit(1); /* Crash and burn! */
}

• • 在释放内存时，必须确保将从 malloc() 返回的原始地址传递给 free() ；否则，将出现系统异常(或更糟)！

使用动态内存

#include <stdio.h>
#include <stdlib.h>
/* Create a Node type. */
typedef struct node {
    int key;
    struct node *left;
    struct node *right;
} Node;

/* Create a Node and return its address.*/
Node *create_node(int key, Node *left, Node *right) {
    Node *np;
    //always check for it
    if ( (np = (Node*) malloc(sizeof(Node))) == NULL) {
        printf("Memory exhausted!\n");
        exit(1);
    } else {
        np->key = key;
        np->left = left;
        np->right = right;
        return np;
    }
}

/* Node **tree is uesd to change Node itself. */
void insert(int key, Node **tree) {
    if ((*tree) == NULL){
        (*tree) = create_node(key, NULL, NULL);
        return;
    }
    if (key <= (*tree)->key) {
        insert(key, &((*tree)->left));
    } else {
        insert(key, &((*tree)->right));
    }
}

int main() {
/* root */
    Node *root = 0;
//we want to change the root itself
    insert(10, &root);
    insert(16, &root);
    insert(5, &root);
    insert(11, &root);
}

Observations

• 代码、静态存储都很简单：它们从不增加或缩小;

• stack 空间相对容易：stack frame 是按照后进先出(LIFO)的顺序创建和销毁的;

• 管理 heap 很 tricky：可以随时分配/释放内存

选择题

int x = 2;
int result;

int foo(int n) {   
    int y;
    if (n <= 0) { 
        printf("End case!\n"); 
        //how many copies of x and y？
        return 0; 
    } else {  
        y = n + foo(n-x);
        return y;
    }
}
result = foo(10);

Right after the printf executes but before the return 0, how many copies of x and y are there allocated in memory?

A: #x = 1, #y = 1 B: #x = 1, #y = 5 C: #x = 5, #y = 1 D: #x = 1, #y = 6 E: #x = 6, #y = 6

My answer: B: #x = 1, #y = 5

correct answer: D: #x = 1, #y = 6

f(0)时虽然不给 y 赋值，但已经给 y 分配空间了。

如何实现Malloc/Free？

• 底层操作系统允许malloc库请求在 heap 中使用较大的内存块(例如，使用Unix sbrk()调用)

• C标准 malloc 库，在未使用的部分内创建数据结构，以跟踪 free space

更快的malloc实现方式

• 为不同大小的对象保留单独的 pools

• “Buddy allocators”总是向上取“2次方大小”的块，以简化查找正确大小和合并相邻块的过程：

Malloc实现

• 所有都提供了相同的库接口，但可以有完全不同的实现方式(可以自定义malloc)

• 使用 headers 在 start of 分配的块和未分配的内存中的空间来保存 malloc 的内部数据结构

• 依赖于程序员记忆：free with same pointer returned by malloc

• 依赖于程序员 not messing wtih 内部数据结构 accidentally！

常见内存问题

• 使用未初始化值

• 使用不属于您的内存

  • 使用被释放了的 stack 或 heap 变量

  • 对堆栈或堆数组的越界引用。

  • 使用NULL或垃圾数据作为指针。

• 不正确使用 free/calloc (by messing with pointer handle returned by malloc/calloc)

• 内存泄漏(您分配了一些稍后忘记 free 的内容)

使用了不属于你的内存

• What is wrong with this code?

  int *ipr, *ipw;
  void ReadMem() {
        int i, j;
        ipr = malloc(4 * sizeof(int));
        i = *(ipr - 1000); 
        j = *(ipr + 1000);
        free(ipr);
   }
  
   void WriteMem() {
        ipw = malloc(5 * sizeof(int));
        *(ipw - 1000) = 0; 
        *(ipw + 1000) = 0; 
        free(ipw);
   }

  访问了错误的内存

有缺陷的堆管理

• What is wrong with this code?

int *pi;
void foo() {
    pi = malloc(8*sizeof(int));
    …
    free(pi); 
}

void main() {
    // I cannot free it any more
    pi = malloc(4*sizeof(int));
    foo();
    …
}

• 内存泄露了

int *plk = NULL;
void genPLK() {
    plk = malloc(2 * sizeof(int));
    … … …
    plk++;    /* Potential leak: pointer variable incremented past beginning of block! */
}

• 潜在的内存泄漏: handle 已更改，你是否复制了这个 handle 以之后再 free？

void FreeMemX() {
    int fnh = 0;
    free(&fnh);  /* Oops! freeing stack memory */
}

free 会在相同的 heap 地址进行 free 操作 free 会认为有个pointer在它的内部数据结构，它会四处查找，在一个你不知道的地方做一些事情

void FreeMemY() {
    int *fum = malloc(4 * sizeof(int));
    free(fum+1);
    /* fum+1 is not a proper handle; points to middle  */
    free(fum);
    free(fum); 
    /* Oops! Attempt to free already freed memory */

}

不能 free 非 heap 内存；不能 free 为未分配的内存

Using Memory You Haven't Allocated

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

内存分配少了，需要额外一个来储存\0

Using Memory You Don’t Own

char *append(const char* s1, const char *s2) {
    const int MAXSIZE = 128;
    char result[128];
    int i=0, j=0;
    for (j=0; i<MAXSIZE-1 && j<strlen(s1); i++,j++) {
        result[i] = s1[j];
    }
    for (j=0; i<MAXSIZE-1 && j<strlen(s2); i++,j++) {
        result[i] = s2[j];
    }
    result[++i] = '\0';
    return result;
}

char result[128];是 stack 收集的 local array name 函数返回了指向 Stack 内存的指针 函数返回后无效

   typedef struct node {
        struct node* next;
        int val;
   } Node;

   int findLastNodeValue(Node* head) {
        while (head->next != NULL) { 
              head = head->next;
        }
        return head->val; 
   }

head恰好为空怎么办？

int* init_array(int *ptr, int new_size) {
    ptr = realloc(ptr, new_size*sizeof(int));
    memset(ptr, 0, new_size*sizeof(int));
    return ptr;
}

int* fill_fibonacci(int *fib, int size) {
    int i;
    init_array(fib, size);
    /* fib[0] = 0; */ fib[1] = 1;
    for (i=2; i<size; i++)
        fib[i] = fib[i-1] + fib[i-2];
    return fib;
}

Improper matched usage of mem handles 内存 handles 的匹配用法不正确 init_array(fib, size);修改为fib = init_array(fib, size);

请记住：realloc可能会移动整个块

• 您的程序中可能有多个指向同一内存位置的指针。

  例如，在遍历链表时，您可能有指向某个节点的指针，但指向该节点的指针也存储为前一个节点中的NEXT。

  因此，您有两个指向同一内存块的指针。

• 在释放该节点时，这些指针将变成堆悬挂指针，因为它们指向已经释放的内存。 此错误的另一个常见原因是使用realloc方法。

• 如果使用悬挂式指针并通过它访问内存，则程序的行为是未定义的。 这可能会导致奇怪的行为或崩溃。 从该位置读取的值将是完全无关的垃圾。

• 如果您通过悬挂式指针修改内存，然后将该值用于预期目的和不相关的上下文，则行为将不可预测。 当然，未初始化的指针或错误的指针算法也可能导致指向已释放的堆内存。

realloc

• realloc(p,size):

  • 将以前分配的块的大小(P)调整为新大小(size)

  • 如果p为NULL，则realloc的行为类似于malloc

  • 如果size为0，则realloc的行为类似于free，从heap中取消分配块

  • 返回内存块的新地址；注意：它可能已经移动了！

            int *ip;
            ip = (int *) malloc(10*sizeof(int));
            /* always check for ip == NULL */
            … … …
            ip = (int *) realloc(ip,20*sizeof(int));
            /* always check for ip == NULL */
            /* contents of first 10 elements retained */
            … … …
            realloc(ip,0); /* identical to free(ip) */

总结

• C有三个要在其中分配数据的主存储段：

  • Static Data：函数外部的变量

  • Stack: 函数的本地变量

  • Heap: Objects explicitly malloc-ed/free-d。

• Heap data 是 C 代码中错误的最大来源