# Project
## Today's topics
- `malloc()` and `free()`
- `#ifndef` and `#define`
- Macro definition
- Dynamic allocation of memory
- Project Walkthrough

## `malloc()` and `free()`
In the C language, `malloc` and `free` are part of the standard library for dynamic memory allocation and deallocation. Their declarations are found in the `<stdlib.h>` header file.

### malloc()

The `malloc` function is used for dynamic memory allocation. It takes one argument (the number of bytes to allocate) and returns a pointer to the allocated memory, or `NULL` if the memory can't be allocated.

Here's a typical declaration of `malloc`:

void* malloc(size_t size);

- `size_t size`: This is an unsigned integer type representing the number of bytes to allocate. `size_t` is a type definition used to represent sizes in bytes.
- Return Value: `void*`: This is a pointer to the allocated block of memory. If the memory cannot be allocated, it returns `NULL`.

### Usage Example

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

int main() {
    // Allocating enough memory for 10 integers
    int* ptr = (int*)malloc(10 * sizeof(int));  

    if (ptr == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }

    for (int i = 0; i < 10; i++) {
        ptr[i] = i * 2;  // Assigning values to the allocated memory
    }

    // ... (use the allocated memory)

    free(ptr);  // Freeing the memory
    return 0;
}

### free()

The `free` function is used to release memory that was previously allocated by `malloc`. It takes one pointer argument that points to the block of memory to be freed.

Here's a typical declaration of `free`:

void free(void* ptr);

- `void* ptr`: This is a pointer to the block of memory to be freed.
- Return Value: None.

### Note

- After using `free` to release memory, you should not access that memory area anymore, as it might have been reclaimed or reallocated by the operating system.
- Attempting to free unallocated memory (or memory that has already been freed) can lead to undefined behavior, including program crashes and data corruption.

After you `free()` a block of allocated memory, the pointer itself still exists, but it now points to a section of memory that has been released and is no longer part of your program. In most cases, you should not continue to use this pointer, as it has become a "dangling pointer."

### Dangling Pointer

A dangling pointer refers to a pointer that points to a memory location that has been freed or is invalid. Attempting to access memory through a dangling pointer can lead to several issues:

1. **Undefined Behavior**: You might read random, meaningless data or corrupt the contents of that memory, leading to program instability or errors.

2. **Program Crash**: In some cases, the operating system may detect that your program is trying to access an invalid memory address and terminate your program.

3. **Security Risks**: In certain scenarios, a dangling pointer can be exploited by attackers, leading to security vulnerabilities.

## `#ifndef` and `#define`

The `#ifndef` and `#define` directives are part of the C preprocessor's conditional compilation features, specifically for creating an include guard.

### Include Guard

An include guard is a mechanism used in C/C++ to prevent a header file from being included more than once in a given compilation unit (source file). Including a header file multiple times can lead to problems such as redefinition errors.

### How It Works

Here’s how the include guard in your example works:

#ifndef MYMALLOC_H
#define MYMALLOC_H

1. `#ifndef MYMALLOC_H` checks if `MYMALLOC_H` has not been defined yet. If `MYMALLOC_H` is not defined, the preprocessor proceeds to include the contents of the header file.

2. `#define MYMALLOC_H` defines `MYMALLOC_H`, so if the preprocessor encounters this header file again during the compilation (either through direct or indirect inclusion), `MYMALLOC_H` will already be defined.

3. All the content of the header file that follows will only be included if `MYMALLOC_H` was not defined before this point.

4. The `#endif` at the end of the file marks the end of the conditional inclusion.

Here is the general structure:

#ifndef MYMALLOC_H   // If MYMALLOC_H is not defined,
#define MYMALLOC_H   // define MYMALLOC_H, and include the following content.

// Content of the header file

#endif // Ends the conditional inclusion started by #ifndef.

### Why It’s Necessary

Include guards are essential because, in a large project, header files often include other header files, and those might, in turn, include yet others. Without an include guard, this could lead to a situation where a header file gets included multiple times, leading to errors and problems such as:

1. **Redefinition Errors**: The compiler will throw errors if it encounters multiple definitions of the same function, variable, or type.

2. **Increased Compilation Time**: Without include guards, the compiler might have to process the same file multiple times, leading to increased compilation times.

## Macro definition

Macro definition, used to "redefine" the malloc and free functions. When you call malloc or free in your code, the preprocessor replaces these calls with calls to mymalloc and myfree, passing the extra arguments __FILE__ and __LINE__.

#define malloc(x) mymalloc(x, __FILE__, __LINE__)
#define free(x) myfree(x, __FILE__, __LINE__)

### Macro Definition Example

#define ROUNDUP8(x) (((x) + 7) & (-8))

### Explanation
This macro is used to round up a given integer \(x\) to the nearest multiple of 8. It operates based on binary bit manipulation.

### Working Steps

1. **Add 7**:
The given integer \(x\) is added to 7. This ensures that if \(x\) is already a multiple of 8, it will still increment to the next multiple of 8.

2. **Bitwise AND Operation**:
The result is then bitwise ANDed with -8. In binary, -8 is represented with all higher bits as 1 and the lowest 3 bits as 0 (assuming we are dealing with a 32-bit integer, then the binary representation of -8 would be `11111111 11111111 11111111 11111000`). This operation essentially zeroes out the lowest 3 bits of \(x+7\), yielding the closest multiple of 8 that is greater than or equal to \(x\).

### Example
Suppose \(x = 10\), and we want to find the smallest multiple of 8 that is greater or equal to 10.

1. With the macro, we first calculate \(x + 7 = 17\).
2. Then we perform a bitwise AND operation on 17 with -8, resulting in 16, as 16 is the smallest multiple of 8 that is greater or equal to 10.

Certainly! Here is an English-only version of the pseudocode and explanation for the `mymalloc` function.

## Dynamic allocation
* The layout of header and payload

* One little demo of dynamic allocation

## mymalloc

1. **Initialization:**

- `start` is a pointer initialized to the beginning of the `memory` array.

    char *start = memoryStart;

- `chunkSize` is an integer pointer pointing to the size of the first chunk of memory. size of the chunk,In a memory pool, the beginning location of each memory block stores the size of that block.

    int *chunkSize = getChunkSize(start);

- `free` is an integer pointer indicating whether the first chunk of memory is free or not.

    int *free = isFree(start);

- `res` is initialized to null. If an appropriate memory block is found, this pointer will be set to the address of that memory block.

    res = (void *)(start + 8)

### pseudocode

Function mymalloc(size):
    If size == 0:
        Print "Error: cannot allocate 0 bytes"
        Return null

    size = ROUNDUP8(size)

    Pointer res = null
    Pointer start = memoryStart

    While start is less than memoryEnd:
        Integer chunkSize = GetChunkSize(start)
        Boolean isFree = IsFree(start)

        If chunkSize == 0 and isFree == false:
            SetChunkSize(start, size + 8)
            MarkAsAllocated(start)
            res = start + 8
            isFree = true
            SetNextChunkSize(start, memoryEnd - (start + size + 8))
            Return res

        If isFree == false and chunkSize >= size + 8:
            SetChunkSize(start, size + 8)
            MarkAsAllocated(start)
            res = start + 8
            If NextChunkIsUninitialized(start):
                SetNextChunkSize(start, chunkSize - (size + 8))
            Return res

        If isFree == true or chunkSize < size + 8:
            start = GetNextChunk(start)

    Print "Error: no enough memory"
    Return null

### Detailed Explanation

1. **Checking the Requested Size**:
The function first checks if the requested size is 0. If it is, an error message is printed, and null is returned because it's not possible to allocate 0 bytes of memory.

    If size == 0:
        Print "Error: cannot allocate 0 bytes"
        Return null

2. **Rounding Up the Size**:
The requested size is rounded up to the nearest multiple of 8. This is done using the `ROUNDUP8` macro, ensuring that allocated memory blocks are always multiples of 8.

    size = ROUNDUP8(size)

3. **Initializing the Pointer**:
A pointer named `res` is initialized to null. If an appropriate memory block is found, this pointer will be set to the address of that memory block.

    Pointer res = null
    Pointer start = memoryStart

4. **Iterating Through the Memory Pool**:
A loop begins to iterate through the predefined memory pool, checking each memory block’s size and allocation status.

    While start is less than memoryEnd:
        Integer chunkSize = GetChunkSize(start)
        Boolean isFree = IsFree(start)

5. **First Allocation**:
If the memory pool is uninitialized (indicating the first call to `mymalloc`), the function sets the size and status of the first memory block and returns its address. That is, the size and state are both 0.
The function looks for a memory block that is not allocated, and is large enough to accommodate the requested size. If found, it sets the size and status of the memory block and returns its address.

    If chunkSize == 0 and isFree == false:
        SetChunkSize(start, size + 8)
        MarkAsAllocated(start)
        res = start + 8
        isFree = true
        SetNextChunkSize(start, memoryEnd - (start + size + 8))
        Return res

7. **Placement of initialized memory**:
If the current memory block is not allocated and enough to accommodate the requested size, the function set header in this memory block.

    If isFree == false and chunkSize >= size + 8:
        SetChunkSize(start, size + 8)
        MarkAsAllocated(start)
        res = start + 8
        If NextChunkIsUninitialized(start):
            SetNextChunkSize(start, chunkSize - (size + 8))
        Return res

8. **Insufficient Memory**:
If there isn't enough space available in the memory pool to satisfy the request, the function prints an error message and returns null.

        Print "Error: no enough memory"
        Return null

## myfree

void myfree(void *ptr) {
    char *start = memoryStart;

    while (start < memoryEnd) {
        if (isAdjacentAndFree(start, ptr)) {
            mergeBlocks(start, ptr);
            if (isFree(nextBlock(ptr))) {
                mergeBlocks(start, nextBlock(ptr));
            }
            invalidatePointer(ptr);
            return;
        }

        if (start == getMetadataStart(ptr)) {
            if (isFree(nextBlock(ptr))) {
                mergeBlocks(ptr, nextBlock(ptr));
            }
            markAsFree(ptr);
            invalidatePointer(ptr);
            return;
        }

        start = nextBlock(start);
    }

    exitWithError("Pointer not in heap");
}

### Detailed Explanation

1. Start iterating from the beginning of the memory pool.

    char *start = memoryStart;

2. Check if the current memory block is adjacent and free to the block pointed to by `ptr`.
- If true, merge both blocks.
- Further check if the next block after the merged block is free. If true, merge them as well.
- Invalidate the pointer and return.

    if (isAdjacentAndFree(start, ptr)) {
        mergeBlocks(start, ptr);
        if (isFree(nextBlock(ptr))) {
            mergeBlocks(start, nextBlock(ptr));
        }
        invalidatePointer(ptr);
        return;
    }

3. If the current block is the one pointed to by `ptr`.
- Check if the next block is free. If true, merge both blocks.
- Mark the current block as free.
- Invalidate the pointer and return.

    if (start == getMetadataStart(ptr)) {
        if (isFree(nextBlock(ptr))) {
            mergeBlocks(ptr, nextBlock(ptr));
        }
        markAsFree(ptr);
        invalidatePointer(ptr);
        return;
    }

4. If the entire memory pool is iterated and the block pointed to by `ptr` is not found, exit the program with an error.

    exitWithError("Pointer not in heap");

## memCleared

int memCleared() {
    char *start = memoryStart;
    int *chunkSize = getChunkSize(start);
    int *free = isFree(start);

    // Case: Memory pool is uninitialized or fully cleared
    if (isUninitialized(*chunkSize, *free) || isFullyCleared(*chunkSize, *free)) {
        return 1;
    }

    return 0;
}

### Detailed Explanation

**Memory Uninitialized or Fully Cleared Check:**

- The function checks if the memory pool is either uninitialized (`*chunkSize == 0 && *free == 0`) or if the entire memory pool is cleared and marked as free (`*chunkSize == 8 * MEMLENGTH && *free == 0`).

    if (isUninitialized(*chunkSize, *free) || isFullyCleared(*chunkSize, *free)) {
        return 1;
    }

- `getChunkSize(start)` is a placeholder for obtaining the size of the memory chunk at the starting position.
- `isFree(start)` is a placeholder for checking if the memory chunk at the starting position is free or not.
- `isUninitialized(*chunkSize, *free)` is a condition checking if the memory pool is uninitialized.
- `isFullyCleared(*chunkSize, *free)` is a condition checking if the entire memory pool is cleared.
3. **Return Values:**
- If either of the above conditions is true, the function returns 1, indicating that the memory is either not yet utilized or is fully cleared.
- Otherwise, it returns 0, indicating that some portions of the memory are still in use.

## memgrind

### test1
In test1, the program allocates 1 byte of memory and immediately releases it 120 times. This test is designed to evaluate the performance of the memory management system when memory is allocated and immediately released.

void test1() {
    for(int i = 0; i < 120; i++) {
        char *ptr = malloc(1);  // Allocate 1 byte of memory
        free(ptr);  // Release the memory
    }
    printf("MemClear?: %d\n", memCleared());  // Check if memory is cleared
}

### test2
test2 allocates 1 byte of memory at 120 consecutive locations, then releases each allocation. This is meant to test the memory management system’s performance with consecutive memory allocations and deallocations.

void test2() {
    char *ptrArray[120];  // Array to store 120 pointers

    for(int i = 0; i < 120; i++) {
        ptrArray[i] = malloc(1);  // Allocate 1 byte of memory and store the address
    }

    for(int i = 0; i < 120; i++) {
        free(ptrArray[i]);  // Release the memory
    }

    printf("MemClear?: %d\n", memCleared());  // Check if memory is cleared
}

### test3
test3 is a bit more complex. It randomly decides whether to allocate 1 byte of memory or release an allocated memory, and it does this 120 times. This is designed to test the memory management system's performance under more complex memory allocation and deallocation scenarios.

void test3() {
    char *ptrArray[120];  // Array to store 120 pointers
    int allocated[120] = {0};  // Initialize the memory allocation status array
    int loc = 0;  // Current location

    for(int i = 0; i < 120; i++) {
        if(loc == 0 || (rand() % 2 == 0 && loc < 120)) {
            // Allocate 1 byte of memory and store the address
            printf("alloc loc=%d\n", loc);
            ptrArray[loc] = malloc(1);
            allocated[loc] = 1;
            loc++;
        } else {
            // Release the memory
            loc--;
            printf("free loc=%d\n", loc);
            free(ptrArray[loc]);
            allocated[loc] = 0;
        }
    }

    printf("Process is done.\n");

    // Clean up any unreleased memory
    for(int i = 0; i < 120; i++) {
        if(allocated[i] == 1) {
            free(ptrArray[i]);
        }
    }

    printf("MemClear?: %d\n", memCleared());  // Check if memory is cleared
}

At the end of each test function, the memCleared function is called to check if all allocated memory has been correctly released. In practical use, this can help us understand the performance and reliability of the memory management system.