Table of Contents

Virtual Memory:MallocLab
#

A few brief notes on virtual memory from CSAPP.

1. Physical and Virtual Addressing
#

Here the CPU looks up addresses directly.

The CPU generates virtual addresses; the MMU translates them.

MMU (Memory Management Unit) — uses lookup tables in main memory to translate virtual addresses.

2. Address Spaces
#

Address Space

There are physical address spaces and virtual address spaces.

An ordered contiguous finite set of natural numbers:

$$ {0, 1, 2, … N - 1} $$

3. Virtual Memory as a Cache Tool
#

Cache ideas show up again.

Conceptually, virtual memory is organized as a byte array stored on disk, and disk contents are cached in main memory.

Disk contents are split into pages.

Virtual memory is divided into virtual pages (VP); physical memory into physical pages (PP).

Sets of VPs:

Unallocated (that disk-backed address range has not been allocated yet)
Allocated but uncached (allocated, but not yet cached in physical memory)
Allocated and cached

Below we use SRAM for L1/L2/L3 caches.

DRAM caches virtual pages in main memory.

DRAM acts as a fully associative cache — any physical page can hold any virtual page.

1. Page Tables
#

VM must decide whether a virtual page resides somewhere in DRAM, and which physical page holds it; on a miss it replaces, moving the virtual page from disk into a physical page in main memory.

Main memory holds a page table, mapping virtual addresses → physical addresses.

The OS maintains the page table and transfers pages between DRAM and disk.

An array of PTEs.

Process
#

page hit
#

e.g., reading contents of VP2 yields a page hit.

page fault
#

A page-fault exception:

Here we want VP3, but valid is 0 — it has not been loaded into DRAM.

A page fault invokes the page-fault handler, which picks a physical page in DRAM to replace; if that page was dirty it is written back; then the needed page is loaded from virtual memory into DRAM and the access retries.

This is paging — again the cache idea.

Allocating pages

Notes.

Such page-replacement policies still rely on locality to keep programs fast.

4. Virtual Memory as a Memory-Management Tool
#

Each process has its own page table — i.e., its own virtual address space.

Simplifies linking: e.g., the text segment always starts at 0x400000; executables are loaded into physical memory when needed.
Simplifies loading? mmap for memory-mapped files/regions.
Simplifies sharing — e.g., shared pages as above.
Simplifies memory allocation: when calling malloc, VM allocates K contiguous VPs that map onto K scattered PPs — one reason heap memory can feel slow.

5. Virtual Memory as a Protection Tool
#

PTE bits can restrict user actions; violations raise a segmentation fault.

6. *Address Translation
#

First some abbreviations.

Simulated flow:

How is a virtual address translated?

PTBR: page-table base register, pointing at the current page table.

Given a VA, the low P bits are VPO (virtual page offset), equal to PPO.

The high n − p bits are the VPN; look up the matching PTE. If valid = 1, extract the PPN (physical page number) and concatenate with PPO to form the physical address.

What is the page-hit path?

CPU gives VA to the MMU.
MMU computes the PTE address and sends it to main memory.
Main memory returns the PTE.
MMU builds the PA from the PTE and requests data from main memory.
Main memory returns the data to the CPU.

What if a page fault occurs?

Steps 1–3 same as before.

An exception transfers control to the page-fault handler.
The handler chooses a victim page; if dirty, write it back to disk.
Load from disk into memory and update the PTE.
Return to the faulting instruction, which now hits.

This needs hardware working with the OS.

1. Combining Caches and Virtual Memory
#

PTE entries can themselves be cached — no fundamental conflict.

L1 lookup happens after the MMU, so it uses physical addresses; fetching those addresses then follows the usual cache path.

Address translation happens before the cache lookup.

2. TLBs Speed Up Translation
#

Cache ideas again.

The MMU holds a small cache of PTEs: the Translation Lookaside Buffer (TLB).

How a VA indexes the TLB.

Like a cache: split the VPN — low bits as set index, high n − p − t bits as tag.

The flow is similar:

VA to MMU.
Take VPN; look up the PTE in the TLB.

And so on.

On a miss, the PTE fetched from memory is also installed in the TLB.

3. Multi-Level Page Tables
#

Problem: a single-level page table can be huge; with many processes each owning a table, memory pressure grows.

A level-1 PTE covers a chunk of virtual memory.

Each level-2 PTE maps one VP.

Why does this reduce memory pressure?

1. A level-2 table exists in memory only when some part of it has mappings. A process rarely uses a full 4GB, so you roughly create PTEs only for VPs that are mapped. Create on use.

2. Only the level-1 table must always reside in main memory.

How does k-level translation work?

For level j, VPNj indexes the j-th page table; PTE at that index is the base of the next table. Repeat until you get a PPN, then concatenate with VPO for the PA.

“Accessing k PTEs may seem expensive and impractical at first glance. However, the TLB comes to the rescue here by caching PTEs from the page tables at the different levels. In practice, address translation with multi-level page tables is not significantly slower than with single-level page tables.”

Another clever design.

4. Work a Manual Example
#

Read the book — fairly straightforward, similar to the earlier cache simulations.

7. Real-World Case
#

Dry for now; revisit later.

Linux Virtual Memory System
#

Kernel virtual memory vs process virtual memory.

How virtual memory is organized:

Maintain a task structure; mm_struct tracks the current VM state; mmap points at a linked list whose nodes describe segments of the virtual address space.

8. Memory Mapping
#

Associating a virtual-memory region with a disk object is memory mapping: map a regular file or an anonymous file.

Anonymous files are created by the kernel and are all zeros.

When installing Linux you see a swap file; once a virtual page is initialized it can be swapped in and out within that space, which limits how many VPs a process can create.

Shared Objects Revisited
#

This is a shared object.

For private objects, use copy-on-write: only when a write is attempted do we copy in physical memory.

fork: when a process calls fork, the kernel creates new data structures and a PID; on return both processes share the same virtual addresses, marked copy-on-write; the first write by either triggers a COW copy.

execve loading a program:

Malloc Lab
#

Supposedly harder than CacheLab — let’s try.

Dynamic Memory Allocation
#

At runtime you may want extra virtual memory via a dynamic memory allocator.

In the process VA space there is a region called the heap:

The top-of-heap pointer is brk.

The heap grows upward — opposite the user stack.

The allocator treats heap memory as variable-sized blocks, each a contiguous chunk of virtual memory, either free or allocated. Allocated blocks are explicitly usable by the process; free blocks are available for allocation.

Allocators:

1. Explicit: explicit allocate and free — C’s malloc / free.

2. Implicit: GC (garbage collector) automatically reclaims unused allocated blocks (Java GC).

1. `malloc` and `free`
#

Call:

#include <stdlib.h>
void *malloc(size_t size)

Returns a block of at least size bytes; on failure returns NULL. The returned memory must satisfy a standard alignment.

calloc: allocate and zero-initialize.

realloc: change the size of an already allocated block (essentially reallocate without losing the original data).

Allocate / free sequence:

p2’s allocation reflects double-word alignment.

After freeing p2, the program must not use that pointer again (dangling pointer?).

When p4 requests memory, it can reuse previously freed space.

2. Why Dynamic Allocation?
#

As in first-year C: many data-structure sizes are known only at runtime, and we do not want that hard-coded.

3. Allocator Requirements and Goals
#

Handle arbitrary sequences of allocate/free requests — random order, not stack- or queue-like.
Respond immediately.
Use only heap memory.
Meet alignment requirements.
Must not modify already allocated blocks.

Performance:

Hk is the current allocated heap size; Pk is the aggregate useful payload of allocated blocks; we want to maximize peak utilization Uk.

4. Fragmentation
#

Internal fragmentation: an allocated block is larger than its payload (e.g., due to alignment); size is allocated bytes minus payload bytes.

External fragmentation: enough free bytes exist in total, but they are not contiguous enough to satisfy a request.

Allocators should try to keep a few large free blocks rather than many tiny ones.

5. Implementation Issues
#

Free-block organization: how to track free blocks?

Placement: which free block hosts a new allocation?

Splitting: after placing into a free block, what happens to the remainder?

Coalescing: what do we do with a just-freed block?

6. Implicit Free Lists
#

Allocator data structure:

Annotate header fields.

Note: a terminating header marks the end.

Why “implicit” free list?

Because the size in the header implicitly links blocks — add size to the current block address to reach the next.

Simple, but every operation costs O(n) where n is the total number of allocated and free blocks.

Note problem 9.6: the 29 size bits are used directly without shifting — unlike the cache bitfields.

7. Placing Allocated Blocks
#

Our implementation uses first-fit.

Search the free list according to a placement policy.

When looking for a suitable free block:

First-fit: from the start until the first that fits.

Next-fit: resume from where the previous search ended.

Best-fit: scan all blocks and pick the smallest free block that still fits.

Each of the three has clear trade-offs.

8. Splitting Free Blocks
#

Split an 8-word free block into two 4-word pieces — allocate the front, leave the back free — or allocate the whole thing and create internal fragmentation.

That choice is itself a policy decision.

9. Obtaining Extra Heap Memory
#

First coalesce free blocks as much as possible; if that still cannot satisfy the request, use sbrk for more heap, insert the new memory into the free list, then allocate.

10. Coalescing Free Blocks
#

Freeing a block may leave two free blocks adjacent — false fragmentation — so we coalesce.

When to coalesce?

1. Immediate coalescing: merge neighbors on free. (But this can thrash with pointless merge/split cycles.)

2. Deferred coalescing: scan and merge only when an allocation would otherwise fail.

11. Boundary-Tag Coalescing
#

With a linked-list mental model, finding the next block is easy — to merge with the next, add the next header’s size to the current. But what about the previous block?

Put a footer at the end of each block — a copy of the header that also indicates free/allocated. Rather like a doubly linked list?

On free there are four cases:

The benefit is clear; the cost is that header and footer consume space — each is 4 bytes / one word.

Once you understand this, most of the rest follows.

Start implementing now; fill in more notes later.

Implementation Requirements
#

Requirements from the handout.

Alignment. In C every type has alignment rules — e.g., an int* must be 4-byte aligned (sizeof(int)=4); a long long* must be 8-byte aligned. Here we require that pointers returned by malloc are 8-byte aligned.

malloc and free must not move or modify already allocated blocks; if you implement realloc, do not alter the original payload; new allocations must not overlap existing allocated blocks.

Your implementation should aim for:

High throughput — minimize time from a request to returning a block pointer.
High utilization — since the allocator also reclaims memory, reuse freed space rather than always growing the heap.

Helper Functions You May Use
#

Memory-copy helpers you may need in realloc, such as memcpy and memmove.
Math helpers such as log (needs math.h).

Driver helpers for controlling the heap — you will likely use:

void *mem_sbrk(int incr): extend the heap top by incr bytes.

void *mem_heap_lo(void): lowest accessible byte in the heap.

void *mem_heap_hi(void): highest accessible byte in the heap.

size_t mem_heapsize(void): current heap size.

size_t mem_pagesize(void): page size (typically 4KB).

Notes:
#

Because space is contiguous and newly requested memory is free, check whether the block before the newly extended region is free; if so, coalesce into one large free block.

An implicit free list uses prologue and epilogue blocks. The first four empty bytes are for alignment; then an 8-byte prologue (4-byte header + 4-byte footer, marked allocated). Our pointer points at the footer — an allocated block that is never freed — from which we can step to the next block.

Finally an epilogue: 4 bytes, allocated, size 0 — marks the end of the heap.

With a naive implicit list and simple first-fit we scored 70. Next, optimize further.

Optimizations:
#

Segregated Free Lists
#

Idea: keep free blocks of similar size together; maintain pointers, each heading a size class.

Bucket: a free list for one size class; head pointers live at the bottom of the heap.
Segregated free lists (free_lists): the array of bucket heads at the heap bottom.

Figure from https://arthals.ink/blog/malloc-lab#%E5%9D%97%E7%9A%84%E7%B2%BE%E7%BB%86%E7%BB%93%E6%9E%84

How to store them at the heap bottom? Does init need to change?

When touching free-list pointers, add/subtract mem_heap_lo() as needed.

Each pointer is 64 bits.

Finer Block Layout
#

Optimize by shrinking metadata.

For free blocks, store both header and footer — two words of metadata.
For allocated blocks, store only a header — one word of metadata.

For allocated blocks requesting an odd number of words, this can avoid one word of internal waste.

Free-block footers let neighbors learn status quickly.

Layouts for the two kinds of blocks:

A free block needs at least four words: header, footer, plus next and prev for an explicit free list.

Note: except for prologue/epilogue, a pointer from the allocator API points at the first payload byte (allocated) or the prev word (free).

Block headers are single-word aligned; block ends are double-word aligned.

Optimization for a pathological test:

The binary trace allocates with this pattern — how should we handle it?

After 20–30 painful hours, reflections:

Know exactly what every line does.

Subtracting two size_t values is never negative — Chapter 1 already taught this, and I still forgot.

Even when consulting others’ code, understand it and do not copy bugs — otherwise debugging is misery.

Finished code (96/100):

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <math.h>

#include "mm.h"
#include "memlib.h"
// 定义一些有用的宏，注意有些宏使用了其他的宏，那么你就要注意使用的顺序和方法

// 比较大小
#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))

// Header的大小
#define WORD_SIZE (sizeof(unsigned int))
#define CHUNK_SIZE (1 << 12)
// 用来在Header上写数据或者读取值
#define READ(PTR) (*(unsigned int *)(PTR))
#define WRITE(PTR, VALUE) ((*(unsigned int *)(PTR)) = (VALUE))

// 将块大小和是否被占用的信息合并，便于写入Header
#define PACK(SIZE, IS_ALLOC) ((SIZE) | (IS_ALLOC))
// 在alloc位的上一位记录这个块前面的块有没有被分配,这样类似，写入header
#define PACK_ALL(SIZE, IS_PREV_ALLOC, IS_ALLOC) ((SIZE) | (IS_PREV_ALLOC) | (IS_ALLOC))

// 传入指向Header的指针p，返回其后的负载块的长度
#define GET_SIZE(PTR) (unsigned int)((READ(PTR) >> 3) << 3)
// 传入指向Header的指针p，返回其后的负载块是否被占用
#define IS_ALLOC(PTR) (READ(PTR) & (unsigned int)1)
// 这是对于一个空闲块的操作，查看它前面的块有没有被分配
#define IS_PREV_ALLOC(PTR) (READ(PTR) & (unsigned int)2)
// 把这个块设置成已分配
#define SET_ALLOC(PTR) (READ(PTR) |= (unsigned int)1)
// 设置空闲
#define SET_FREE(PTR) (READ(PTR) &= ~0x1)
// 设置前面块已经分配
#define SET_PREV_ALLOC(PTR) (READ(PTR) |= (unsigned int)2)
// 设置前面块未分配
#define SET_PREV_FREE(PTR) (READ(PTR) &= ~0x2)

// 传入指向负载首个字节的指针，返回指向这个块的头/尾的指针
#define HEAD_PTR(PTR) ((char *)(PTR) - WORD_SIZE)
#define TAIL_PTR(PTR) ((char *)(PTR) + GET_SIZE(HEAD_PTR(PTR)) - WORD_SIZE * 2)

// 传入指向负载首个字节的指针，返回指相邻的下一个块/上一个块的指针
// 注意，指向的是负载块
#define NEXT_BLOCK(PTR) ((char *)(PTR) + GET_SIZE(HEAD_PTR(PTR)))
#define PREV_BLOCK(PTR) ((char *)(PTR) - GET_SIZE((char *)(PTR) - WORD_SIZE * 2))

// 用来debug的宏
#define IS_IN_HEAP(PTR) (((char *)(PTR) >= (char *)mem_heap_lo()) && ((char *)(PTR) <= (char *)mem_heap_hi()))

// 设置一个全局变量heap_list总是指向序言块
static char *heap_listp = 0;

// 空闲链表配置
#define FREE_LIST_NUMBER 14
// 一个头指针数组，每个指针指向该类链表的第一个空闲块
// 每个块存放的都是偏移量的大小
static char **free_lists;

#define FIND_TIMES 8
// 注意这里寻找的逻辑是相对于lo()的偏移量

#define PREV_OFFSET(bp) (*(unsigned *)(bp))
#define NEXT_OFFSET(bp) (*(unsigned *)((char *)(bp) + WORD_SIZE))

// 在这个位置我们只存放偏移量 prev next的
// 这两个一定要返回绝对的地址
#define PREV_NODE(bp) ((char *)(mem_heap_lo() + *(unsigned *)(bp)))
#define NEXT_NODE(bp) ((char *)(mem_heap_lo() + *(unsigned *)(bp + WORD_SIZE)))


//static int flag = 0;
// 我们在这里设置成偏移量
// #define SET_NODE_PREV(bp, val) (*(unsigned *)(bp) = ((unsigned)(val - mem_heap_lo())))
// #define SET_NODE_NEXT(bp, val) (*(unsigned *)((char *)bp + WORD_SIZE) = ((unsigned)(val - mem_heap_lo())))

#define SET_NODE_PREV(bp, val) (*(unsigned int *)(bp) = (unsigned int)((val) ? (char *)(val) - (char *)mem_heap_lo() : 0))
#define SET_NODE_NEXT(bp, val) (*(unsigned int *)((char *)(bp) + WORD_SIZE) = (unsigned int)((val) ? (char *)(val) - (char *)mem_heap_lo() : 0))

team_t team = {
    /* Team name */
    "Ciallo",
    /* First member's full name */
    "Quanye Yang",
    /* First member's email address */
    "2236115135@xjtu.edu.cn",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

/* 用来做对齐的操作 */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

// 一些静态辅助inline函数的定义，减少开销

/* 合并空闲块 */
static inline void *coalesce(void *hp, size_t size);
/* 在一块找到的空间内分配内存 */
static inline void place(void *ptr, size_t size);
/* 首次适配的逻辑 */
static inline void *first_fit(size_t size);
/* 当对内存不够用时，堆内存扩展的逻辑 */
static inline void *extend_heap(size_t words);
static inline size_t get_index(size_t size);
static inline size_t adjust_size(size_t size);
static inline void insert_node(void *bp, size_t size);
static inline void delete_node(void *bp);
//static void debug_heap();
//static int test_number = 0;
// 合并空闲块
// check!!!
// void*是任意类型的指针
// 最容易出错的逻辑
static inline void *coalesce(void *hp, size_t size)
{
    size_t is_prev_alloc = IS_PREV_ALLOC(HEAD_PTR(hp));
    size_t is_next_alloc = IS_ALLOC(HEAD_PTR(NEXT_BLOCK(hp)));

    if (is_next_alloc && is_prev_alloc)
    {
        // printf("两边都没有空闲块，大小为 %ld \n", size);
        // 每次free都是前后已经分配并且是4096的大小？
        // printf(" %ld ",size);
        //++test_number;
        // printf(" %d : %ld \n", test_number, size);
        SET_PREV_FREE(HEAD_PTR(NEXT_BLOCK(hp)));
    }
    else if (is_prev_alloc && !is_next_alloc)
    {
        delete_node(NEXT_BLOCK(hp));
        size += GET_SIZE(HEAD_PTR(NEXT_BLOCK(hp)));
        //printf("后面有一个空闲块，合并之后大小为 %ld \n", size);
        WRITE(HEAD_PTR(hp), PACK_ALL(size, 2, 0));
        WRITE(TAIL_PTR(hp), PACK_ALL(size, 2, 0));
    }
    else if (!is_prev_alloc && is_next_alloc)
    {
        // 前面没有分配，稍微复杂一些
        delete_node(PREV_BLOCK(hp));
        SET_PREV_FREE(HEAD_PTR(NEXT_BLOCK(hp)));
        size += GET_SIZE(HEAD_PTR(PREV_BLOCK(hp)));
        //printf("前面有空闲块，合并之后大小为 %ld \n", size);
        size_t is_prev_prev_alloc = IS_PREV_ALLOC(HEAD_PTR(PREV_BLOCK(hp)));
        WRITE(HEAD_PTR(PREV_BLOCK(hp)), PACK_ALL(size, is_prev_prev_alloc, 0));
        WRITE(TAIL_PTR(hp), PACK_ALL(size, is_prev_prev_alloc, 0));
        hp = PREV_BLOCK(hp);
    }
    else
    {
        delete_node(PREV_BLOCK(hp));
        delete_node(NEXT_BLOCK(hp));

        size += (GET_SIZE(HEAD_PTR(PREV_BLOCK(hp)))) + (GET_SIZE(HEAD_PTR(NEXT_BLOCK(hp))));
        //printf("两边都有空闲块，合并之后大小为 %ld \n", size);
        size_t is_prev_prev_alloc = IS_PREV_ALLOC(HEAD_PTR(PREV_BLOCK(hp)));
        WRITE(HEAD_PTR(PREV_BLOCK(hp)), PACK_ALL(size, is_prev_prev_alloc, 0));
        WRITE(TAIL_PTR(NEXT_BLOCK(hp)), PACK_ALL(size, is_prev_prev_alloc, 0));
        hp = PREV_BLOCK(hp);
    }

    insert_node(hp, size);

    // debug_heap();
    return hp;
}

// check!!! 如果有问题，大概就是空闲链表的设计有问题。
//  place函数的全部，它传入指向一个空闲块的负载部分第一个字节的指针，以及需要从中分割出多少空间，你需要把分割出的一段或两段空间填写好相应的头部与尾部。
// 被binary攻击了，我们应当选取怎样的策略。
static inline void place(void *ptr, size_t size)
{
    // assert(ptr != NULL);
    size_t curr_size = GET_SIZE(HEAD_PTR(ptr));
    size_t remaining_size = curr_size - size;

    // printf("place(): ptr = %p, curr_size = %zu\n", ptr, curr_size);

    // void *next = NEXT_BLOCK(ptr);
    // printf("place(): next = %p\n", next);

    // printf("place(): tail of next = %p, heap_hi = %p\n", TAIL_PTR(next), mem_heap_hi());

    delete_node(ptr);

    // 小于最小块的大小，那么我们就不会分割
    if (remaining_size < 4 * WORD_SIZE)
    {
        SET_ALLOC(HEAD_PTR(ptr));

        SET_PREV_ALLOC(HEAD_PTR(NEXT_BLOCK(ptr)));
        // 如果下一个块是空闲块，那么尾部也要设置已经分配
        if (!IS_ALLOC(HEAD_PTR(NEXT_BLOCK(ptr))))
        {
            SET_PREV_ALLOC(TAIL_PTR(NEXT_BLOCK(ptr)));
        }
    }
    else
    {

        // 产生分割
        WRITE(HEAD_PTR(ptr), PACK_ALL(size, IS_PREV_ALLOC(HEAD_PTR(ptr)), 1));
        WRITE(HEAD_PTR(NEXT_BLOCK(ptr)), PACK_ALL(remaining_size, 2, 0));
        WRITE(TAIL_PTR(NEXT_BLOCK(ptr)), PACK_ALL(remaining_size, 2, 0));
        insert_node(NEXT_BLOCK(ptr), remaining_size);

        // 我们来进行一些关于面向数据点的优化
        // if (size <= 72)
        // {
        //     //printf("分配成功了一下......");
        //     WRITE(HEAD_PTR(ptr), PACK_ALL(size, IS_PREV_ALLOC(HEAD_PTR(ptr)), 1));
        //     WRITE(HEAD_PTR(NEXT_BLOCK(ptr)), PACK_ALL(remaining_size, 2, 0));
        //     WRITE(TAIL_PTR(NEXT_BLOCK(ptr)), PACK_ALL(remaining_size, 2, 0));
        //     insert_node(NEXT_BLOCK(ptr), remaining_size);
        // }
        // else
        // {
        //     // 把大的块放到后面去
        //     WRITE(HEAD_PTR(ptr), PACK_ALL(remaining_size, IS_PREV_ALLOC(HEAD_PTR(ptr)), 0));
        //     WRITE(TAIL_PTR(ptr), PACK_ALL(remaining_size, IS_PREV_ALLOC(HEAD_PTR(ptr)), 0));
        //     insert_node(ptr, remaining_size);

        //     ptr = NEXT_BLOCK(ptr);

        //     WRITE(HEAD_PTR(ptr), PACK_ALL(size, 0, 1));

        //     SET_PREV_ALLOC(HEAD_PTR(NEXT_BLOCK(ptr)));
        //     if(!IS_ALLOC(HEAD_PTR(NEXT_BLOCK(ptr)))){
        //         SET_PREV_ALLOC(TAIL_PTR(NEXT_BLOCK(ptr)));
        //     }
            
        // }
    }

    // // 实验全部分配的代码
    // size_t curr_size = GET_SIZE(HEAD_PTR(ptr));
    // delete_node(ptr);

    // WRITE(HEAD_PTR(ptr), PACK_ALL(curr_size, IS_PREV_ALLOC(ptr), 1));
    // SET_PREV_ALLOC(HEAD_PTR(NEXT_BLOCK(ptr)));

    // if(!IS_ALLOC(HEAD_PTR(NEXT_BLOCK(ptr)))){
    //     SET_PREV_ALLOC(TAIL_PTR(NEXT_BLOCK(ptr)));
    // }
}

// check 逻辑应该没有问题，如果有问题，应该是显式链表的设计有问题
// 从开头开始遍历，直到找到第一个满足条件的分配块，并且返回指向负载部分第一个字节的指针
static inline void *first_fit(size_t size)
{
    // 找一个合适的桶
    int number = get_index(size);
    char *hp;

    // 从这个桶之后开始向后方进行遍历
    for (; number < FREE_LIST_NUMBER; ++number)
    {
        // 怎么设计的显示分离空闲链表???
        // 注意使用的是偏移量
        // 但是在调用的时候，我们使用的都是真实的地址
        for (hp = (char *)mem_heap_lo() + (size_t)free_lists[number]; hp != mem_heap_lo(); hp = NEXT_NODE(hp))
        {
            // 首次适配的逻辑
            long diff = GET_SIZE(HEAD_PTR(hp)) - size;
            if (diff >= 0)
            {
                //printf("The free block size is %d and the required size is %d...\n", GET_SIZE(HEAD_PTR(hp)), size);
                long min_diff = diff;
                char *cur = hp;
                for (int index = 0; index < FIND_TIMES && cur != mem_heap_lo(); cur = NEXT_NODE(cur), ++index)
                {
                    long s = GET_SIZE(HEAD_PTR(cur)) - size;
                    if (s >= 0 && s < min_diff)
                    {
                        min_diff = s;
                        hp = cur;
                    }
                }
                return hp;
            }
        }
    }

    return NULL;
}

// check!!!
// 用新的空闲块扩展堆
// 要扩展多少个字的大小
// 当我们指向尾部节点的时候，我们会扩展内存，这里的hp指向的是负载的内存（也就是才分配的），那么hp的前面就是刚才的结束foot，那么我们把刚才的结束foot设置成新的header，并且把才分配的内存的最后一个设置成结束foot，那么就处理了边界问题
static inline void *extend_heap(size_t words)
{
    char *hp;
    size_t size;

    // 首先分配堆内存,必须要是偶数,因为要对齐8字节
    size = (words % 2 == 1 ? ((words + 1) * WORD_SIZE) : (words * WORD_SIZE));
    hp = mem_sbrk(size);
    // printf("Here, we extended %d bytes\n", size);
    if (hp == (void *)-1)
    {
        return NULL;
    }

    // 仔细思考一下，这是很精妙的处理边界情况的方式
    // WRITE(HEAD_PTR(hp), PACK(size, 0));
    // WRITE(TAIL_PTR(hp), PACK(size, 0));
    // WRITE(HEAD_PTR(NEXT_BLOCK(hp)), PACK(0, 1));

    size_t is_prev_alloc = IS_PREV_ALLOC(HEAD_PTR(hp));

    WRITE(HEAD_PTR(hp), PACK_ALL(size, is_prev_alloc, 0));
    WRITE(TAIL_PTR(hp), PACK_ALL(size, is_prev_alloc, 0));
    WRITE(HEAD_PTR(NEXT_BLOCK(hp)), PACK(0, 1));

    // 假如前面的一个块也是空闲的，调用合并空闲块的函数
    return coalesce(hp, size);
}

// 根据不同的数值来获取不同大小的桶对应的链表位置
static inline size_t get_index(size_t size)
{
    // if(size <= 4096)
    //     return 1;
    // if (size <= 15360)
    //     return 11;
    // if (size <= 30720)
    //     return 12;
    // if (size <= 61440)
    //     return 13;
    // else
    //     return 14;

    // if (size <= 1)
    //     return 0;
    // if (size <= 2)
    //     return 1;
    // if (size <= 4)
    //     return 2;
    // if (size <= 8)
    //     return 3;
    // if (size <= 16)
    //     return 4;
    // if (size <= 32)
    //     return 5;
    // if (size <= 64)
    //     return 6;
    // if (size <= 128)
    //     return 7;
    // if (size <= 256)
    //     return 8;
    // if (size <= 512)
    //     return 9;
    // if (size <= 1024)
    //     return 10;
    // if (size <= 2048)
    //     return 11;
    // if (size <= 4096)
    //     return 12;
    // if (size <= 8192)
    //     return 13;
    // if (size <= 16384)
    //     return 14;
    // if (size <= 32768)
    //     return 15;
    // else
    //     return 16;

    if (size <= 1)
        return 0;
    if (size <= 16)
        return 1;
    if (size <= 32)
        return 2;
    if (size <= 64)
        return 3;
    if (size <= 128)
        return 4;
    if (size <= 256)
        return 5;
    if (size <= 512)
        return 6;
    if (size <= 1024)
        return 7;
    if (size <= 2048)
        return 8;
    if (size <= 4096)
        return 9;
    if (size <= 8192)
        return 10;
    if (size <= 16384)
        return 11;
    if (size <= 32768)
        return 12;
    else
        return 13;

    // return 0;
}

static inline size_t adjust_size(size_t size)
{
    if (size >= 112 && size < 128)
    {
        return 128;
    }
    // binary.rep
    if (size >= 448 && size < 512)
    {
        // printf("Allocated size changed from %ld to %d...\n", size, 512);
        return 512;
    }
    return size;
}

// 关于空闲链表的插入和删除
static inline void insert_node(void *bp, size_t size)
{
    // 我们是往链表的头部进行插入
    // 找到是属于第几个桶
    size_t number = get_index(size);

    // 该链表的头节点先拿出来
    char *curr = (char *)mem_heap_lo() + (size_t)free_lists[number];

    // free_lists存放了一系列的头节点
    // 直接更新头节点为插入的节点
    free_lists[number] = (char*)((char *)bp - (char *)mem_heap_lo());
    // 插入的节点不是第一个节点
    if (curr != mem_heap_lo())
    {
        // 把插入的bp作为链表的头节点
        // 这里设置的是指向链表的地址
        // 设置双向链表
        SET_NODE_PREV(bp, mem_heap_lo());
        SET_NODE_NEXT(bp, curr);
        SET_NODE_PREV(curr, bp);
    }
    else
    {
        // bp是插入的第一个节点
        SET_NODE_NEXT(bp, mem_heap_lo());
        SET_NODE_PREV(bp, mem_heap_lo());
    }
}

// check!!!
static inline void delete_node(void *bp)
{
    assert(bp != NULL);
    assert(!IS_ALLOC(HEAD_PTR(bp)));

    size_t size = GET_SIZE(HEAD_PTR(bp));
    size_t number = get_index(size);

    char *next_node = NEXT_NODE(bp);
    char *prev_node = PREV_NODE(bp);

    // 是否是头节点
    if (prev_node == mem_heap_lo())
    {
        // 是头节点就直接设置成下一个节点
        free_lists[number] = (char*)((char *)next_node - (char *)mem_heap_lo());

        // 是否是唯一的头节点
        if (next_node != mem_heap_lo())
        {
            SET_NODE_PREV(next_node, mem_heap_lo());
        }
    }
    else
    {
        // assert((int*)prev_node >= (int*)mem_heap_lo());
        SET_NODE_NEXT(prev_node, next_node);
        if (next_node != mem_heap_lo())
        {
            SET_NODE_PREV(next_node, prev_node);
        }
    }
}

/*
 * mm_init - initialize the malloc package.
 */
// 这个实现要求返回的指针8字节对齐
// check!!!
// 设计上哪里还有漏洞，再比对一下
int mm_init(void)
{
    // 先初始化空闲链表free_lists
    // 开始时空闲链表的每个指针都定义成堆底的指针
    free_lists = mem_heap_lo();
    for (int index = 0; index < FREE_LIST_NUMBER; ++index)
    {
        // 每个分四字节
        // 我们分配了FREE_LIST_NUMBER个双字，每个双字都用来存放链表的头指针
        if ((heap_listp = mem_sbrk(2 * WORD_SIZE)) == (void *)-1)
        {
            return -1;
        }

        // 开始时free_lists所有的指向的地址都为堆底的地址
        // 这里就是从堆底开始的15个双字，每个都存放着堆底的地址
        free_lists[index] = 0;
    }

    // 此时双字对齐，我们开四个字来存放序言块和结尾块
    if ((heap_listp = mem_sbrk(4 * WORD_SIZE)) == (void *)-1)
    {
        return -1;
    }

    // 紧接着我们来分配头部
    // 第一个字填充
    WRITE(heap_listp, 0);
    // 后两个字是序言块，已分配的8字节
    WRITE(heap_listp + (1 * WORD_SIZE), PACK(2 * WORD_SIZE, 1));
    WRITE(heap_listp + (2 * WORD_SIZE), PACK(2 * WORD_SIZE, 1));
    // 然后是结束标志的header,(Epilogue Header),大小为0,但是已经分配
    // 这里的PACK3是自己分配，并且自己前方的块也已经分配的意思。
    WRITE(heap_listp + (3 * WORD_SIZE), PACK(0, 3));

    // heap_listp指向序言块的header，这样序言块就不会被释放
    heap_listp += 2 * (WORD_SIZE);

    // 申请一个page的内存失败。
    if (extend_heap(CHUNK_SIZE / WORD_SIZE) == NULL)
    {
        return -1;
    }
    return 0;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
// check!!! 唯一有可能是因为取整的问题出错
// 接下来要检查其余的函数
void *mm_malloc(size_t size)
{
    // malloc的新逻辑
    size_t alloc_size, extend_size;
    void *hp;
    if (heap_listp == NULL)
    {
        mm_init();
    }

    if (size == 0)
    {
        return NULL;
    }

    size = adjust_size(size);

    // 保证对齐，可以用来存储头部或者脚部
    if (size <= 2 * WORD_SIZE)
    {
        alloc_size = 4 * WORD_SIZE;
    }
    else
    {
        // 要分配的块向上取整
        // 多了8个字节的大小
        alloc_size = (2 * WORD_SIZE) * ((size + (WORD_SIZE) + (2 * WORD_SIZE - 1)) / (2 * WORD_SIZE));
        // alloc_size = adjust_size(alloc_size);
        //  ++test_number;
        //  printf("%d:要分配%ld个字节......\n", test_number, alloc_size);
        //   printf("Alloc size is %ld...\n", alloc_size);
        //    size_t number = size / (2 * WORD_SIZE);
        //    number += 1;
        //    alloc_size = 2 * WORD_SIZE * number;
    }

    if ((hp = first_fit(alloc_size)) != NULL)
    {
        // ++test_number;
        // printf("%d Alloc Size IS %d !!!\n", test_number, alloc_size);
        place(hp, alloc_size);
        return hp;
    }

    // 扩展堆，内存不足
    // 也就是堆内存扩展的时候出了问题
    extend_size = MAX(CHUNK_SIZE, alloc_size);
    //++test_number;
    // printf("%d:产生了堆扩展，扩展大小为 %ld 个字节\n", test_number, extend_size);
    if ((hp = extend_heap(extend_size / WORD_SIZE)) == NULL)
    {
        return NULL;
    }

    
    place(hp, alloc_size);
    return hp;
}

/*
 * mm_free - Freeing a block does nothing.
 * 释放本身是很简单的逻辑
 */
// check!!!
void mm_free(void *ptr)
{
    if (ptr == NULL)
    {
        return;
    }

    if (heap_listp == NULL)
    {
        mm_init();
        return;
    }

    size_t size = GET_SIZE(HEAD_PTR(ptr));
    size_t is_prev_alloc = IS_PREV_ALLOC(HEAD_PTR(ptr));
    // // 更改头部和尾部

    // 因为这是一个空闲块，所以我们前后都要进行写入
    WRITE(HEAD_PTR(ptr), PACK_ALL(size, is_prev_alloc, 0));
    WRITE(TAIL_PTR(ptr), PACK_ALL(size, is_prev_alloc, 0));

    // 合并空闲块的逻辑
    coalesce(ptr, size);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;

    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

// void debug_heap()
// {
//     printf("======= 空闲链表状态 =======\n");
//     for (int i = 0; i < FREE_LIST_NUMBER; ++i)
//     {
//         printf("FreeLists[%d]: ", i);
//         char *bp = (char *)mem_heap_lo() + (size_t)free_lists[i];
//         while (bp != mem_heap_lo())
//         {
//             printf("[%u] -> ", GET_SIZE(HEAD_PTR(bp)));
//             bp = NEXT_NODE(bp);
//         }
//         printf("NULL\n");
//     }
// }

Some comments are only fragmentary debug notes — definitely reflect!!!

I am truly terrible……

Virtual Memory:MallocLab #

1. Physical and Virtual Addressing #

2. Address Spaces #

3. Virtual Memory as a Cache Tool #

1. Page Tables #

Process #

page hit #

page fault #

4. Virtual Memory as a Memory-Management Tool #

5. Virtual Memory as a Protection Tool #

6. *Address Translation #

1. Combining Caches and Virtual Memory #

2. TLBs Speed Up Translation #

3. Multi-Level Page Tables #

4. Work a Manual Example #

7. Real-World Case #

Linux Virtual Memory System #

8. Memory Mapping #

Shared Objects Revisited #

Malloc Lab #

Dynamic Memory Allocation #

1. malloc and free #

2. Why Dynamic Allocation? #

3. Allocator Requirements and Goals #

4. Fragmentation #

5. Implementation Issues #

6. Implicit Free Lists #

7. Placing Allocated Blocks #

8. Splitting Free Blocks #

9. Obtaining Extra Heap Memory #

10. Coalescing Free Blocks #

11. Boundary-Tag Coalescing #

Implementation Requirements #

Helper Functions You May Use #

Notes: #

Optimizations: #

Segregated Free Lists #

Finer Block Layout #