# I. Introduction
- I'm learning memory management using the [`valgrind`](https://valgrind.org/) tool and documenting it in this note.
## Environment setting
- Ubuntu Linux version: 24.04.1 LTS
- gcc version: 13.3.0
- Valgrind version: 3.22.0
# II. `Valgrind` tool
- Memory leak types:
1. **`definitely lost`**: program is leaking memory
2. **`indirectly lost`**: program is leaking memory in a pointer-based structure. (E.g. if the root node of a binary tree is "definitely lost", all the children will be "indirectly lost".) If you fix the "definitely lost" leaks, the "indirectly lost" leaks should go away.
3. **`possibly lost`**: program is leaking memory, unless you're doing unusual things with pointers that could cause them to point into the middle of an allocated block.
4. **`still reachable`**: program is probably ok -- it didn't free some memory it could have. This is quite common and often reasonable.
5. **`suppressed`**: means that a leak error has been suppressed. There are some suppressions in the default suppression files. You can ignore suppressed errors.
- command: `$ valgrind --tool=<toolname> <program>`
# III. Experiment
## Case 1: Memory Leak - Definitely Lost
- I created a C code file that does not `free()` allocated memory after using `malloc` as shown below.

    #include<stdlib.h>

    void func(void){
        char *buff = malloc(10);
    }

    int main(void){
        func();
        return 0;
    }

- Use the command below to compile the C code into an object file.
`gcc -g -o memLeak memLeak.c`
- Next, use the command below to launch `Valgrind` tool to check for memory leaks.
`valgrind --leak-check=full ./memLeak`
- The result is shown as the figure below.
- The number 14354 indicates the process ID.
- In `Heap SUMMARY`, the console reports: "total heap usage: 1 allocs, 0 frees, 10 bytes allocated", which is due to the missing `free(buff)` operation.
- Additionally, it indicates that the memory leak occures in line 4 (inside the `func` function) and line 8 (inside the ` main` function).
- In `LEAK SUMMARY`, the message "definitely lost: 10 bytes in 1 blocks" confirms the memory leak.
- I added the `free(buff)` operation inside the `func` function.

    #include<stdlib.h>
    
    void func(){
        char *buff = malloc(10);
        free(buff);
    }
    
    int main(){
        func();
        return 0;
    }

- The updated memory leak detection result is shown below.
- In 'HEAP SUMMARY', the message confirms that the heap memory allocated by `buff` has been successfully freed.
## Case 2: Memory Leak - Indirectly Lost
- I created a binary tree and allocated memory without freeing it.

#include<stdio.h>

typedef struct Node{
    int val;
    struct Node *left;
    strucr Node *right;
}Node;

void createTree(){
    Node *root = malloc(sizeof(Node));
    root->val = 1;
    root->left = malloc(sizeof(Node));
    root->right = malloc(sizeof(Node));
}

int main(){
    createTree();
    return 0;
}

- The memory leak is shown below.
- There are both *definitely lost* and *indirectly loss* blocks in this code.
- The block size of *indirectly lost* memory is twice that of *definitely lost* memory due to the left and right subtrees.
- If I free only the root node or both the right and left child nodes, the memory remaining is *definitely lost*.
- free the root:

        #include <stdlib.h>

        typedef struct Node{
            int val;
            struct Node *left;
            struct Node *right;
        }Node;

        void createTree(){
            Node *root = malloc(sizeof(Node));
            root->val = 1;
            root->left = malloc(sizeof(Node));
            root->right = malloc(sizeof(Node));
            free(root);
        }

        int main(){
            createTree();
            return 0;
        }

- free the right and left node:

        #include <stdlib.h>

        typedef struct Node{
            int val;
            struct Node *left;
            struct Node *right;
        }Node;

        void createTree(){
            Node *root = malloc(sizeof(Node));
            root->val = 1;
            root->left = malloc(sizeof(Node));
            root->right = malloc(sizeof(Node));
            free(root->left);
            free(root->right);
        }

        int main(){
            createTree();
            return 0;
        }

## Case 3: Memory Leak - Possibly Lost
- The `abort()` function terminates this program, preventing `free(p)` from being executed, which leads to a *possibly* memory leak as shown below.

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>

    int main(int argc, char **argv){
        char *s = "string";
        char *p = strdup(s);

        p+=1;
        abort();
        
        // the codes below would not be executed.
        p-=1;
        free(p);

        return 0;
    }

## Case 4: Memory Leak - Still Reachable
- A *still reachable* memory leak indicates that when the process terminated, its dynamically allocated memory can still be accessed by other processes because a pointer still references it.
- A *still reachable* memory leak typically occurs when a global or static pointer references allocated memory. Since global and static variables persist from the start to the end of the process, failing to free the allocated memory before termination leads to a *still reachable* memory leak.

    #include <stdlib.h>

    static int *ptr;

    void func(){
        ptr = malloc(sizeof(int));
        *ptr = 100;
    }

    int main(){
        func();
        return 0;
    }


## Case 5: Invalid Access
- I created a C code file as follows:

    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    
    int main(void){
        
        // Invalid write
        char *str = malloc(4);
        strcpy(str, "Curry");
        free(str);
        
        // Invalid read
        int *arr = malloc(3);
        printf("%d", arr[4])
        free(arr);
        
        // Invalid read
        printf("%d", arr[0]);
        
        // Invalid free
        free(arr);
        
        return 0;
    }    

- There are four memory misoperations in the code above. However, after compiling it, only one warning message appears, and no error messages are generated.
- Using the `valgrind` command I used earlier, the `valgrind` tool detects memory usage errors, including:
1. **Invalid memory write** in line 9: `strcpy(str, "Curry");`.
2. **Invalid memory read** in line 14: `printf("%d", arr[4]);`, and in line 18: `printf("%d", arr[0])` after the memory has already been freed.
3. **Invalid memory free** in line 21: `free(arr)` after the specified memory had already been freed.
- Additionally, we can observe that there is no memory leak in the `HEAP SUMMARY` section.
# IV. Reference
- [The Valgrind Quick Start Guide](https://valgrind.org/docs/manual/quick-start.html)
- [Valgrind Frequently Asked Questions](https://valgrind.org/docs/manual/faq.html#faq.deflost)
- [Valgrind: can possibly lost be treated as definitely lost?](https://stackoverflow.com/questions/3537713/valgrind-can-possibly-lost-be-treated-as-definitely-lost)
- [C語言的記憶體洩漏(Memory Leak)偵測 - Valgrind ](http://blog.yslin.tw/2014/03/c-valgrind.html)
- [Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b)