JS `WebAssembly` `Linear Memory` `Allocation` `Strategies` (`bump pointer`, `free list`)

各位听众，早上好/下午好/晚上好！ 今天咱们来聊聊 WebAssembly 线性内存分配那些事儿，保证让大家听完之后，感觉像是刚啃完一只香喷喷的烤鸡，回味无穷！

WebAssembly 线性内存：一块未经开垦的处女地

首先，我们要搞清楚什么是 WebAssembly 线性内存。 把它想象成一块巨大的、连续的字节数组，就像一块原始的、未经开垦的土地。WebAssembly 模块可以在这块土地上存储数据，就像农民伯伯可以在土地上种庄稼一样。 这块内存是 WebAssembly 模块与 JavaScript 之间进行数据交换的重要桥梁，也是 WebAssembly 程序运行时的主要存储区域。

这块内存的大小是固定的，在模块实例化的时候就确定了。 但是，我们可以通过 WebAssembly.Memory.grow() 方法来扩大这块土地，增加内存页数。 每一页的大小是 64KB，也就是 65536 字节。

线性内存的地址：门牌号

线性内存中的每一个字节都有一个唯一的地址，就像我们家的门牌号一样。 这些地址从 0 开始，一直递增到内存的最大容量。 WebAssembly 指令可以通过这些地址来读取或写入内存中的数据。

内存分配：盖房子

现在，问题来了：我们如何在这一大块连续的内存中存储各种各样的数据呢？ 这就需要内存分配。 内存分配就像在这块土地上盖房子，我们需要找到一块合适的空地，然后把房子（数据）盖上去。

更具体地说，内存分配器负责管理线性内存中的空闲空间，并根据程序的需求分配内存块。 当程序需要存储数据时，它会向内存分配器请求一块内存，内存分配器会在空闲空间中找到一块合适的区域，并将其分配给程序。 当程序不再需要这块内存时，它会将其释放回内存分配器，以便将来可以再次使用。

内存分配策略：盖房子的方法论

不同的内存分配策略就像不同的盖房子的方法论。 它们各有优缺点，适用于不同的场景。 今天我们主要介绍两种最常见的策略： Bump Pointer 和 Free List。

1. Bump Pointer (碰撞指针)：简单粗暴，一往无前

想象一下，你有一块空地，你想在上面盖很多小房子，一个接一个地排下去。 最简单的办法就是每次都在上一个房子的旁边盖新的房子，就像推土机一样，一直往前推。 这就是 Bump Pointer 的基本思想。

• 原理： Bump Pointer 维护一个指针，指向当前已分配内存的末尾。 当需要分配内存时，只需要将指针向前移动相应的字节数，然后返回之前指针指向的地址即可。
• 优点： 速度非常快，因为只需要进行简单的指针运算。 实现起来也非常简单。
• 缺点： 只能进行顺序分配，不能释放单独的内存块。 如果需要释放内存，只能一次性释放所有已分配的内存。 这就像推倒所有房子，回到最初的空地状态。

代码示例 (伪代码):

// 假设内存块起始地址是 memory_start
uint8_t* bump_pointer = memory_start;
size_t memory_size = ...; // 内存总大小

void* allocate(size_t size) {
  // 检查是否有足够的内存
  if (bump_pointer + size > memory_start + memory_size) {
    return nullptr; // 内存不足
  }

  // 分配内存
  void* allocated_memory = bump_pointer;
  bump_pointer += size;

  return allocated_memory;
}

void reset() {
  // 重置 bump pointer，释放所有内存
  bump_pointer = memory_start;
}

WebAssembly 实现示例 (WAT 格式):

(module
  (memory (export "memory") 1) ; 1 页内存 (64KB)

  (global $bump_pointer (mut i32) (i32.const 16)) ; Bump pointer, 初始地址 16 (留出一些空间)

  (func (export "allocate") (param $size i32) (result i32)
    ;; 获取当前 bump pointer 的值
    local.get $size
    global.get $bump_pointer
    i32.add

    ;; 检查是否超出内存边界 (简化版本，实际需要更完善的检查)
    i32.const 65536  ; 64KB
    i32.gt_u  ; 如果 bump_pointer + size > 65536，则返回 1，否则返回 0
    if
      i32.const 0  ; 返回 0 表示分配失败
      return
    end

    ;; 保存 bump pointer 的旧值
    global.get $bump_pointer
    local.set $old_pointer

    ;; 更新 bump pointer
    local.get $size
    global.get $bump_pointer
    i32.add
    global.set $bump_pointer

    ;; 返回旧的 bump pointer 值
    local.get $old_pointer
  )

  (func (export "reset")
    global.set $bump_pointer (i32.const 16)
  )
)

解释:

• (memory (export "memory") 1): 定义并导出了一块内存，大小为 1 页 (64KB)。
• (global $bump_pointer (mut i32) (i32.const 16)): 定义了一个全局变量 $bump_pointer，用于存储 bump pointer 的地址。 初始值为 16，留出一些空间。
• (func (export "allocate") (param $size i32) (result i32)): allocate 函数接受一个参数 $size，表示需要分配的内存大小，返回分配的内存地址。
• (func (export "reset")): reset 函数将 bump pointer 重置为初始值，相当于释放了所有已分配的内存。

使用 JavaScript 调用:

const wasmCode = `
(module
  (memory (export "memory") 1)
  (global $bump_pointer (mut i32) (i32.const 16))

  (func (export "allocate") (param $size i32) (result i32)
    local.get $size
    global.get $bump_pointer
    i32.add
    i32.const 65536
    i32.gt_u
    if
      i32.const 0
      return
    end
    global.get $bump_pointer
    local.set $old_pointer
    local.get $size
    global.get $bump_pointer
    i32.add
    global.set $bump_pointer
    local.get $old_pointer
  )

  (func (export "reset")
    global.set $bump_pointer (i32.const 16)
  )
)
`;

const wasmModule = new WebAssembly.Module(new TextEncoder().encode(wasmCode));
const wasmInstance = new WebAssembly.Instance(wasmModule);

const allocate = wasmInstance.exports.allocate;
const reset = wasmInstance.exports.reset;
const memory = wasmInstance.exports.memory;

// 分配 10 个字节
const ptr1 = allocate(10);
console.log("分配的地址:", ptr1);

// 分配 20 个字节
const ptr2 = allocate(20);
console.log("分配的地址:", ptr2);

// 重置内存
reset();

// 再次分配 10 个字节
const ptr3 = allocate(10);
console.log("分配的地址:", ptr3);

适用场景：

• 只需要进行大量的顺序分配，不需要释放单独的内存块。
• 适用于内存管理非常简单的场景，例如编译器的临时变量分配。

2. Free List (空闲链表)：灵活回收，资源再利用

想象一下，你有一个停车场，里面有很多停车位。 当有车要停进来的时候，你需要找到一个空闲的停车位，然后把车停进去。 当车要离开的时候，你需要把这个停车位标记为空闲，以便将来可以再次使用。 这就是 Free List 的基本思想。

• 原理： Free List 维护一个链表，链表中的每个节点代表一块空闲的内存块。 当需要分配内存时，内存分配器会遍历链表，找到一块足够大的空闲块，然后将其分割成两部分：一部分分配给程序，另一部分仍然保留在空闲链表中。 当程序释放内存时，内存分配器会将释放的内存块添加到空闲链表中，并尝试与相邻的空闲块合并，以减少内存碎片。
• 优点： 可以灵活地分配和释放内存，可以有效地利用内存空间。 可以避免内存碎片的问题。
• 缺点： 速度相对较慢，因为需要遍历链表才能找到合适的空闲块。 实现起来也比较复杂。

数据结构：

Free List 通常使用链表来实现，每个节点包含以下信息：

• size: 空闲块的大小。
• next: 指向下一个空闲块的指针。

代码示例 (伪代码):

struct FreeBlock {
  size_t size;
  FreeBlock* next;
};

FreeBlock* free_list_head = nullptr; // 空闲链表头

void* allocate(size_t size) {
  FreeBlock* current = free_list_head;
  FreeBlock* previous = nullptr;

  // 遍历空闲链表，找到合适的空闲块
  while (current != nullptr) {
    if (current->size >= size) {
      // 找到合适的空闲块
      if (current->size == size) {
        // 整个空闲块都分配出去
        if (previous == nullptr) {
          free_list_head = current->next;
        } else {
          previous->next = current->next;
        }
        return current; // 返回空闲块的地址
      } else {
        // 分割空闲块
        FreeBlock* new_block = (FreeBlock*)((uint8_t*)current + size);
        new_block->size = current->size - size;
        new_block->next = current->next;
        current->size = size;

        if (previous == nullptr) {
          free_list_head = new_block;
        } else {
          previous->next = new_block;
        }
        return current; // 返回空闲块的地址
      }
    }

    previous = current;
    current = current->next;
  }

  return nullptr; // 没有找到合适的空闲块
}

void deallocate(void* ptr, size_t size) {
  // 将释放的内存块添加到空闲链表中
  FreeBlock* block = (FreeBlock*)ptr;
  block->size = size;
  block->next = free_list_head;
  free_list_head = block;

  // TODO: 尝试与相邻的空闲块合并
}

WebAssembly 实现示例 (WAT 格式 – 简化版本，没有合并相邻空闲块):

由于 WebAssembly 没有指针的概念，我们需要使用线性内存的索引来模拟指针。 这使得 Free List 的实现变得比较复杂。 以下是一个简化的示例，只实现了基本的分配和释放功能，没有实现空闲块合并。

(module
  (memory (export "memory") 1) ; 1 页内存 (64KB)

  ;; 结构体定义：FreeBlock
  ;; size (i32): 空闲块的大小
  ;; next (i32): 指向下一个空闲块的地址 (线性内存中的索引)

  (global $free_list_head (mut i32) (i32.const 16)) ; 空闲链表头, 初始地址 16

  ;; 函数：allocate (分配内存)
  ;; 参数: $size (i32) - 需要分配的内存大小
  ;; 返回值: (i32) - 分配的内存地址 (线性内存中的索引)

  (func (export "allocate") (param $size i32) (result i32)
    local.get $size
    call $allocate_internal
  )

  (func $allocate_internal (param $size i32) (result i32)
    local.get $size
    i32.const 8  ; 每个 FreeBlock 占用 8 字节 (size: 4 字节, next: 4 字节)
    i32.add
    local.set $required_size ; 实际需要的内存大小 (包含 FreeBlock 头部)

    ;; 遍历空闲链表
    global.get $free_list_head
    local.set $current_block_ptr

    loop $loop
      local.get $current_block_ptr
      i32.eqz  ; 如果 current_block_ptr == 0 (空指针)，则跳出循环
      if (br_if $end)

        ;; 获取当前空闲块的大小
        local.get $current_block_ptr
        i32.load  ; 加载 size 字段 (地址: current_block_ptr + 0)
        local.set $current_block_size

        ;; 检查当前空闲块是否足够大
        local.get $current_block_size
        local.get $required_size
        i32.ge_u  ; 如果 current_block_size >= required_size，则跳转到 $found_block
        if (br_if $found_block)

          ;; 获取下一个空闲块的指针
          local.get $current_block_ptr
          i32.const 4
          i32.add
          i32.load  ; 加载 next 字段 (地址: current_block_ptr + 4)
          local.set $current_block_ptr ; 更新 current_block_ptr

          br $loop ; 继续循环
        end
      end

      $end
      ;; 没有找到合适的空闲块
      i32.const 0  ; 返回 0 表示分配失败
      return

    $found_block
    ;; 找到合适的空闲块
    local.get $current_block_ptr
    local.set $allocated_block_ptr ; 保存分配的块的地址

    ;; 从空闲链表中移除当前空闲块 (简化版本，没有分割空闲块)
    local.get $current_block_ptr
    i32.const 4
    i32.add
    i32.load
    global.set $free_list_head

    ;; 返回分配的内存地址 (跳过 FreeBlock 头部)
    local.get $allocated_block_ptr
    i32.const 8
    i32.add
    return
  )

  ;; 函数：deallocate (释放内存)
  ;; 参数: $ptr (i32) - 要释放的内存地址 (线性内存中的索引)
  ;; 参数: $size (i32) - 要释放的内存大小

  (func (export "deallocate") (param $ptr i32) (param $size i32)
    local.get $ptr
    local.get $size
    call $deallocate_internal
  )

  (func $deallocate_internal (param $ptr i32) (param $size i32)
    ;;  计算FreeBlock 地址
    local.get $ptr
    i32.const 8
    i32.sub
    local.set $free_block_ptr

    ;; 将释放的内存块添加到空闲链表中
    ;; 1. 设置 FreeBlock 的 size 字段
    local.get $free_block_ptr
    local.get $size
    i32.store

    ;; 2. 设置 FreeBlock 的 next 字段
    local.get $free_block_ptr
    i32.const 4
    i32.add
    global.get $free_list_head
    i32.store

    ;; 3. 更新 free_list_head
    global.get $free_block_ptr
    global.set $free_list_head
  )

  ;; 初始化空闲链表
  (func (export "init")
    i32.const 1024  ; 初始空闲块大小 (1KB)
    i32.const 0     ; 空闲块的 next 指针为 0 (空指针)
    call $create_free_block
  )

  ;; 创建空闲块的辅助函数
  (func $create_free_block (param $size i32) (param $next i32)
    ;; 分配空闲块的内存 (使用简单的 bump pointer 分配器)
    global.get $free_list_head
    local.set $block_ptr

    ;; 存储空闲块的大小
    local.get $block_ptr
    local.get $size
    i32.store

    ;; 存储空闲块的 next 指针
    local.get $block_ptr
    i32.const 4
    i32.add
    local.get $next
    i32.store

    ;; 更新 free_list_head
    global.get $free_list_head
    i32.add
    global.set $free_list_head
  )
)

解释：

• 数据结构： 使用线性内存来模拟 FreeBlock 结构体，size 存储在地址 block_ptr + 0， next 存储在地址 block_ptr + 4。
• allocate_internal 函数： 遍历空闲链表，找到第一个大小足够的空闲块，并将其从空闲链表中移除 (简化版本，没有分割空闲块)。
• deallocate_internal 函数： 将释放的内存块添加到空闲链表的头部。
• init 函数： 初始化空闲链表，创建一个初始的空闲块。
• 重要： 这个示例非常简化，没有实现空闲块分割和合并，也没有处理内存碎片问题。 实际的 Free List 实现要复杂得多。

使用 JavaScript 调用:

const wasmCode = `
(module
  (memory (export "memory") 1)

  (global $free_list_head (mut i32) (i32.const 1024)) ; 初始空闲链表放在地址 1024
  (global $next_free_block (mut i32) (i32.const 1024)) ; 用于简单bump分配

  (func (export "allocate") (param $size i32) (result i32)
    local.get $size
    i32.const 8  ; size + next
    i32.add
    local.set $required_size

    global.get $free_list_head
    local.set $current_block_ptr

    loop $loop
      local.get $current_block_ptr
      i32.eqz
      if (br_if $end)

        local.get $current_block_ptr
        i32.load
        local.set $current_block_size

        local.get $current_block_size
        local.get $required_size
        i32.ge_u
        if (br_if $found_block)

          global.get $free_list_head
          i32.const 4
          i32.add
          i32.load
          global.set $free_list_head

          local.get $current_block_ptr
          i32.const 8
          i32.add
          return
        end
      end

      $end
      i32.const 0
      return

    $found_block
    local.get $current_block_ptr
    i32.const 8
    i32.add
    return
  )

  (func (export "deallocate") (param $ptr i32) (param $size i32)
    local.get $ptr
    i32.const 8
    i32.sub
    local.set $free_block_ptr

    local.get $free_block_ptr
    local.get $size
    i32.store

    local.get $free_block_ptr
    i32.const 4
    i32.add
    global.get $free_list_head
    i32.store

    global.get $free_block_ptr
    global.set $free_list_head
  )

  (func (export "init")
    i32.const 1024
    i32.const 0
    call $create_free_block
  )

  (func $create_free_block (param $size i32) (param $next i32)
    global.get $next_free_block
    local.set $block_ptr

    local.get $block_ptr
    local.get $size
    i32.store

    local.get $block_ptr
    i32.const 4
    i32.add
    local.get $next
    i32.store

    global.get $next_free_block
    i32.add
    global.set $next_free_block
  )
)
`;

const wasmModule = new WebAssembly.Module(new TextEncoder().encode(wasmCode));
const wasmInstance = new WebAssembly.Instance(wasmModule);

const allocate = wasmInstance.exports.allocate;
const deallocate = wasmInstance.exports.deallocate;
const init = wasmInstance.exports.init;
const memory = wasmInstance.exports.memory;

init();

const ptr1 = allocate(10);
console.log("分配的地址:", ptr1);

const ptr2 = allocate(20);
console.log("分配的地址:", ptr2);

deallocate(ptr1, 10);

const ptr3 = allocate(10);
console.log("分配的地址:", ptr3);

适用场景：

• 需要频繁地分配和释放内存。
• 需要有效地利用内存空间，避免内存碎片。
• 适用于需要更复杂的内存管理的场景，例如游戏引擎。

总结：

特性	Bump Pointer	Free List
速度	非常快	相对较慢
内存利用率	较低，只能一次性释放所有内存	较高，可以灵活地分配和释放内存，减少碎片
实现复杂度	简单	复杂
适用场景	大量的顺序分配，不需要释放单独的内存块	频繁地分配和释放内存，需要有效地利用内存空间
WebAssembly实现	容易	相对复杂，需要模拟指针

选择合适的内存分配策略：

选择哪种内存分配策略取决于具体的应用场景。 如果只需要进行简单的顺序分配，Bump Pointer 是一个不错的选择。 如果需要更灵活的内存管理，Free List 则更加适合。

高级话题：

• 内存碎片： Free List 可能会导致内存碎片，需要进行碎片整理。
• 垃圾回收： WebAssembly 也可以使用垃圾回收来自动管理内存。
• 自定义内存分配器： 可以根据自己的需求实现自定义的内存分配器。

最后，记住一点： 内存管理是一门艺术，也是一门科学。 希望今天的讲解能够帮助大家更好地理解 WebAssembly 线性内存分配，并在实际开发中做出更明智的选择。

感谢大家的聆听！ 希望这次讲座能给你带来一些启发， 祝大家编码愉快！