Lib.rs

› 内存管理 | WebAssembly
#allocator #heap #free #pointers #memory #list #projects

无 std alloc_cat

为 Rust 中的小型到微型 Wasm 项目提供的简单分配器

由 Robey Pointer 拥有。

1 个稳定版本

1.0.0 2024 年 7 月 27 日

#84 在 内存管理

Download history 147/week @ 2024-07-25 9/week @ 2024-08-01

每月 156 次下载

自定义许可

73KB
1.5K SLoC

alloc_cat

     |\_/|
     )   (
    =\___/=
     /   \       alloc_cat
     |   |
_   (     )  ______   ______   _
 \ / \_ _/\ /      \ /      \ /
  |   //   |        |        |
  |   \\   |        |        |
  |    \)  |        |        |
  |        |        |        |

alloc_cat 是一个为 Rust 中的小型到微型 Wasm 项目提供的简单分配器，与 #[no_std] 兼容。

它旨在替代现在已废弃的 wee_alloc，在 Rust 系统分配器过重的情况下。它不像 wee_alloc 那样复杂，而是专注于简单性和可测试性。

分配策略是一个基于 简单增量指针和空闲列表 的策略，针对很少使用超过 2MB 或分配大于 32KB 块的程序进行了优化，尽管它可以处理任何大小的堆或分配，只要不超过系统限制。此外，还可以收集指标，以帮助分析程序的内存使用情况。

快速入门

用 alloc_cat 的一个分配器替换 rust 系统分配器。这应该就像在您的顶级 lib.rs 中放入这个一样简单

extern crate alloc;

use alloc_cat::{ALLOCATOR, AllocCat};

#[global_allocator]
pub static GLOBAL_ALLOCATOR: &AllocCat = &ALLOCATOR;

然后所有的堆分配（如 Box）都将使用 alloc_cat。您可以通过在运行时调用 get_stats()（见下文）并检查值是否不为零来验证它。

使用方法

有三种不同的方法可以使用 alloc_cat

  • 在 Wasm 中 (target_arch = "wasm32")

    此模式提供了一种基于 Wasm 内存模型（在下面的单独部分中描述）的分配器，也是此库的主要目的。

  • 包装系统分配器

    此模式通过在非Wasm架构上运行时开启system_allocator功能（默认开启）来激活。它为系统分配器提供了一个包装器，除了分配指标外没有其他内置功能。

  • 在Wasm之外使用alloc_cat算法

    此模式通过在非Wasm架构上运行时关闭默认的system_allocator功能来激活。它使用mmap从操作系统获取一个静态内存池，并为它提供alloc_cat分配器来管理。它使用互斥锁来避免线程竞争，这可能会变慢。这实际上仅适用于在非Wasm环境中测试alloc_cat算法。

支持的cargo "功能"

  • system_allocator（默认）

    在运行任何非Wasm架构时使用rust系统分配器。这通常是您想要的，除非您正在测试alloc_cat本身。另一种选择是上述描述的基于mmap的池。

  • audit_sizes

    开启此功能将使alloc_cat跟踪每个大小和对齐方式的分配数量（除了其正常指标外），这会使分配器略微变慢，并额外使用2KB的内存，但可用于调试泄露。这也可能对好奇的人或注重细节的人有用。

当使用mmap分配器（target_arch不是Wasm且system_allocator功能已关闭）时，您可以通过环境变量设置用于堆的池的大小

  • ALLOC_CAT_MMAP_HEAP_SIZE（字节，默认 = 2097152 = 2MB）

指标

获取堆的基本统计信息

let stats = ALLOCATOR.get_stats();

根据使用的分配器，stats对象将填充各种字段（未使用的字段将为零）。

  • in_use: usize

  • high_water: usize

    in_use是应用程序当前分配的字节数，而high_water是in_use的最高值。由于碎片化和块大小舍入，堆使用的内存量将更大，这些将在下面的更详细指标中进行跟踪（如果您没有使用系统分配器）。

  • size_table: [SizeInfo; 257]（仅当feature = "audit_sizes"）

    数组中的每个元素都是一个按比例缩放的请求大小直方图的“桶”

    • size: usize -- 字节
    • count: usize -- 当前/活动分配的数量
    • high_water: usize -- count的最高值

    前48个桶的大小为1到48，其余的覆盖2的倍数（50, 52, 54, ...），4，8，以此类推，逐步达到512字节的范围，直到约22.5KB的大小。最后一个桶将覆盖任何大于22.5KB的分配，其size字段将为usize::MAX。

    分配请求将被分配到最接近的桶，该桶的大小大于或等于请求的大小，因此对于（..., 88, 92, 96, ...）的桶，92桶将计数所有89、90、91或92的分配请求。

  • align_table: [usize; 16] （仅在 feature = "audit_sizes"）

    数组中的每个元素代表一个位宽对齐，从字节对齐（align_table[0] 或 0 位）通过 u32 对齐（align_table[2]，2 位）直到更高。实际上，超过 3 位（8 字节）的对齐非常少见。

    数组中的值是每个对齐的分配请求次数，作为请求计数，而不是当前分配的数量。

其余字段仅与 Wasm 分配器相关。对于系统分配器，它们都将保持为 0。"单词"指的是 32 位（4 字节）单位，而"页"指的是 64KB 单位。

  • regions: usize -- 分配器管理的 2MB 区域数量

  • total_words: usize -- Wasm 分配给分配器的（4 字节）单词数量。这包括已分配的内存、在空闲列表中跟踪的内存以及尚未由 bump 指针分配的内存。

  • allocated_words: usize -- 已分配或处于空闲列表中的单词数量

  • unused_words: usize -- 可用（到目前为止）的单词数量，即 bump 指针可以使用的数量。这仅仅是 total_words - allocated_words。

  • fragment_words: usize -- 空闲列表中的单词数量，这是在活动分配之间的未分配空间

  • fragments: usize -- 组成空闲列表的独立段的数量

  • total_large_pages: usize -- 为“大”（>= 32KB）请求分配的 64KB 页数量

  • unused_large_pages: usize -- 已释放但尚未（重新）使用的 64KB 大页数量

  • allocated_large_pages_words: usize -- 所有活动大分配请求中请求的单词总数

  • heap_start: usize -- Wasm 堆起始地址，供好奇者参考。Wasm 堆的详细信息将在下面的部分中详细描述。

Wasm 内存如何工作

Wasm 引擎提供了一整块连续内存，作为一个“页”的整数，其中一页是 64KB。地址从 0（0x0000_0000）开始。

一个典型的程序将为全局数据和任务栈保留内存，然后留下其余部分可供按需增长的堆使用。随着堆的增长，它必须向 Wasm 请求更多页面。

    |                           |
    |                           +-- 192KB (3 pages)
    |                           |
    |                           |
    |   ^      not yet      ^   |
    |   |     allocated     |   |
    | - - - - - - - - - - - - - +-- 128KB (2 pages)
    |             ^             |
    |  heap       |             |
    +---------------------------+ (88KB)
    |  memory reserved before   |
    |  program start:           +-- 64KB (1 page)
    |      - task stack         |
    |      - data/bss           |
    |                           |
    |                           |
    +---------------------------+-- 0

在这个例子中，启动时分配了 128KB（或 2 页）。88KB 保留用于全局数据和栈，留下第二页的 40KB 用于堆。程序可以请求另一个页面，将总内存扩展到 192KB，并将可用堆从 40KB 扩展到 104KB（40KB + 一个新的 64KB 页）。

我们只有两个“系统调用”用于管理内存

  • 大小：memory_size() -> usize，它返回当前分配的页面数量
  • 增长：memory_grow(count: usize) -> usize，它分配count个新页面并返回之前的页面数量

在我们的示例中，memory_size()最初将返回2。为了将堆扩展到104KB，我们将调用memory_grow(1)（这将返回2），现在memory_size()将返回3。

没有方法可以将内存返回给系统。Wasm的堆可以增长，但永远不会缩小。

我们还有一个符号__heap_base，它指向保留内存的末尾，在这里地址是88KB（0x0001_6000）。

幸运的是，这足以实现一个堆。我们的内存从地址__heap_base开始，到地址memory_size() * 0x1_0000结束。这个范围内的所有内容都属于我们，用于在程序中分配和释放内存块。

如果Wasm耗尽内存，alloc_cat将报告失败，这通常会导致程序在恐慌中优雅地结束（就像任何其他分配器一样）。

alloc_cat是如何工作的

正常的分配请求（小于32KB）使用类似于20世纪以来任何教科书中都能找到的基本算法，基于跃进指针和空闲块链表。最初，分配器将跃进指针设置为空闲内存的起始位置（Wasm中的__heap_base），并将空闲列表设置为空列表。

每个请求都向上舍入到最接近的整数字节（4字节）。首先，我们遍历空闲列表，并返回第一个足够大且具有正确对齐的空闲块。如果块的大小大于请求的大小，我们将首先分割它。如果没有可用的空闲块，我们将增加跃进指针，如果需要的话，通过扩展堆增加另一个页面。

通过将块大小限制为32KB，并将每个区域的的大小限制为2MB，空闲列表中的每个“下一个”指针可以将大小和偏移量打包成一个单字

31            24        19    16                 8               0  <- bit
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   size, in words        |   offset to next block, in words      |
|   0-8KW (0-32KB)        |   0-512KW (0-2MB)                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
free list pointer, packed into one word (32 bits)

空闲列表按地址排序，因此当释放内存块时，它可以与任何相邻的空闲块合并。如果这导致最后一个空闲块与跃进指针相遇，我们将跃进指针向后移动。

如果我们想扩展堆，但已经达到2MB（或者下一个Wasm页面已经被用于其他目的，如大分配），我们开始一个新的堆区域，并将其链接到前一个区域，创建一个每个区域最多2MB的区域链表。

大分配（32KB或更大，没有限制）更简单。它们在一个链表中跟踪，每个链接包含两个单词：指向下一个块开始的指针和该下一个块中页面的数量。这个链接存储在每个后续块的最后一页的末尾的两个单词中。如果可能，释放的块将被重用，并且如果它们相邻，可以分割和合并，但仅以页面（64KB）为单位。

许可证

本代码的授权依据您个人或非商业使用的偏好，可以是繁荣许可(LICENSE-propserity.md)或反资本主义许可(LICENSE-anti-capitalist.txt)。

作者

标志设计深受多产ASCII艺术家"jgs"系列作品的启发。您可以在这里找到关于猫的酷炫艺术作品，包括她的作品。

依赖项

约2MB
约40K SLoC