slub shuffle_freelist

shuffle_freelist()是 SLUBfreelist 随机化机制的建链函数：它利用预先计算好的随机序列s->random_seq，把一个新 slab 页里的所有对象按随机顺序串成 freelist，使分配顺序不可预测，增加堆溢出攻击的难度。

一、函数签名

static bool shuffle_freelist(struct kmem_cache *s, struct slab *slab)

返回bool：true表示随机建链成功，false表示条件不满足、回退到顺序建链。

二、典型实现

static bool shuffle_freelist(struct kmem_cache *s, struct slab *slab) { void *freelist; void *cur; void *next; unsigned long idx, pos, page_limit, freelist_count; if (slab->objects < 2 || !s->random_seq) return false; freelist_count = oo_objects(s->oo); pos = get_random_u32_below(freelist_count); page_limit = slab->objects * s->size; start = fixup_red_left(s, slab_address(slab)); /* First entry is used as the base of the freelist */ cur = next_freelist_entry(s, &pos, start, page_limit, freelist_count); cur = setup_object(s, cur); slab->freelist = cur; for (idx = 1; idx < slab->objects; idx++) { next = next_freelist_entry(s, &pos, start, page_limit, freelist_count); next = setup_object(s, next); set_freepointer(s, cur, next); cur = next; } set_freepointer(s, cur, NULL); return true; }

三、逐段解析

1. 条件检查

if (slab->objects < 2 || !s->random_seq) return false;

两种情况回退到顺序建链：

返回false，调用者allocate_slab()走普通建链路径。

2. 随机起始位置

freelist_count = oo_objects(s->oo); pos = get_random_u32_below(freelist_count);

• freelist_count：缓存标称的对象数（序列长度）。

• pos：从random_seq的随机位置开始取，而不是固定从 0 开始。

• 双重随机：序列本身是随机的，起始位置也随机，进一步增强不可预测性。

• get_random_u32_below()：内核的高效随机数，避免取模偏差。

3. 计算边界

page_limit = slab->objects * s->size; start = fixup_red_left(s, slab_address(slab));

• page_limit：当前 slab 实际对象区的字节上限。

  • 如果发生ORDER_FALLBACK，slab->objects会小于freelist_count，所以要用实际对象数算。

• start：对象真实起点（含左红区），经fixup_red_left()修正。

4. 建链：头对象

cur = next_freelist_entry(s, &pos, start, page_limit, freelist_count); cur = setup_object(s, cur); slab->freelist = cur;

• 取第一个随机对象，设为slab->freelist（链表头）。

• setup_object()对它做调试/KASAN/构造函数初始化。

5. 建链：循环串接

for (idx = 1; idx < slab->objects; idx++) { next = next_freelist_entry(s, &pos, start, page_limit, freelist_count); next = setup_object(s, next); set_freepointer(s, cur, next); cur = next; }

• 循环slab->objects - 1次，每次取下一个随机对象。

• set_freepointer(s, cur, next)：把当前对象的 freepointer 指向下一个（编码后写入）。

• cur = next：推进。

• 用slab->objects而非freelist_count作为循环上限，正确处理回退场景。

6. 收尾

set_freepointer(s, cur, NULL);

最后一个对象的 freepointer 设为NULL，链表结束。

7. 返回成功

return true;

告诉调用者随机建链已完成。

四、与顺序建链的对比

未开随机化或条件不满足时，allocate_slab()走普通路径：

// 顺序建链（简化） for_each_object(p, s, addr, slab->objects) { setup_object(s, p); set_freepointer(s, p, next); next = p; } set_freepointer(s, last, NULL);

五、与其他函数的配合

init_cache_random_seq() // 预计算 s->random_seq │ ▼ shuffle_freelist(s, slab) // 建链时消费 ├─ get_random_u32_below() // 随机起始 pos ├─ next_freelist_entry() // 从 random_seq 取偏移 │ └─ 跳过越界偏移 ├─ setup_object() // 调试/KASAN/构造函数 └─ set_freepointer() // 串成链表（编码写入）

六、调用时机

在allocate_slab()/new_slab()里，对象初始化之后、slab 投入使用之前：

static struct slab *allocate_slab(...) { ... for_each_object(p, s, addr, slab->objects) setup_object(s, p); if (!shuffle_freelist(s, slab)) { // 回退：顺序建链 ... } ... }

实际上较新版本会把建链统一到shuffle_freelist()或普通路径，由allocate_slab()调用。

七、安全意义

shuffle_freelist()是CONFIG_SLAB_FREELIST_RANDOM的核心：

• 未随机化时，攻击者通过一次堆溢出预测下一个分配地址，可精准覆盖目标。

• 随机化后，每个 slab 页的 freelist 顺序不可预测，攻击者难以构造稳定的利用。

• 与CONFIG_SLAB_FREELIST_HARDENED（freepointer 编码）配合，形成双重防护：

  • HARDENED：让攻击者无法构造合法 freepointer。

  • RANDOM：让攻击者无法预测下一个分配地址。

八、知识呼应

九、总结

shuffle_freelist(s, slab)在CONFIG_SLAB_FREELIST_RANDOM开启且s->random_seq就绪时，从随机位置开始，循环调用next_freelist_entry()从随机序列取对象地址、setup_object()初始化、set_freepointer()串成 freelist，使新 slab 页的对象链接顺序完全随机。条件不满足时返回false，回退到顺序建链。它是 SLUB 对抗堆溢出攻击的关键安全机制。