用一个 40KB 的文件跑一遍缓存程序,gdb 里 info proc mapping 会看到同一个文件出现了三行,偏移分别是 0x7000、0x8000、0x9000:

0x7ffff7fc8000  0x7ffff7fc9000  0x1000  0x7000  /home/whb/code/test/test/log.txt
0x7ffff7fca000  0x7ffff7fcb000  0x1000  0x9000  /home/whb/code/test/test/log.txt
0x7ffff7ffb000  0x7ffff7ffc000  0x1000  0x8000  /home/whb/code/test/test/log.txt

十个块的文件只映射了三块,这就是"缓存容量为 3"在这个进程里唯一可见的痕迹。每块一个页、偏移各不相同,mmap 的 offset 必须是页大小的整数倍,所以块的边界天然落在页边界上。

为什么把文件切块,而不是整份映射

整份映射最省代码:fstat 拿大小,一次 mmap,之后任意偏移就是指针加法。小文件确实如此。文件一大,代价就跑到地址空间以外去了:映射 10GB 时,进程的页表要为这段区间登记约两百六十万个页表项,其中真正被碰过的可能只有几十页。这些页表项本身占内存,也会把 TLB 的命中率拖下来。

按块映射把这份开销压到"容量 × 一块":容量 3、块 4096,进程里就只登记了 12KB 的文件窗口。其余部分压根没有映射,缺页也就无从发生。

块大小取 4096 不是为了整齐,而是因为它是页大小。块一定要是页的整数倍,否则块起点里有一大半不能作为 offset 传给 mmap。页大小在别的架构上可能是 16KB 或 64KB,所以这个值应当来自 sysconf(_SC_PAGESIZE),而不是写死 4096。

两件套:链表管顺序,哈希表管定位

LRU(least recently used,最近最少使用)的规则两句话:被访问的挪到队头;满了从队尾淘汰。要两步都花常数时间,得靠两件套:

  • 双向链表按访问顺序排列,头部是最新、尾部是最久未用,把节点挪到头部本身是 O(1);
  • 哈希表以文件偏移为键、块对象为值,定位是 O(1)。

两者的容量都是 O(n),n 是缓存里的块数。

课件给每个块挂了几个状态位,用 unsigned 打包:NORMAL、NEW、VISIT、DELETE。这里有一处必须改的错误:

#define VISIT  (1 << 2)
#define DELETE (1 << 2)

VISIT 和 DELETE 用了同一位。后果不是"偶尔判错",而是结构性的:Status2Delete() 写入的正是"被访问过"那一位,IsDelete() 也会在任何被访问过的块上返回真;UpdateStatus 又是先清零再赋值,两个状态互斥地互相覆盖。位标志必须是各占一位,DELETE 应当写 1 << 3。

一次 GetBlock 走过的路径

GetBlock 收到的是用户给的任意偏移,第一步把它对齐到块起点,第二步查缓存,第三步更新 LRU 链表。

#pragma once
#include <cstdio>
#include <list>
#include <memory>
#include <string>
#include <unordered_map>
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
 
namespace LRUCache
{
enum BlockState : unsigned {
    NORMAL = 1u << 0,
    NEW    = 1u << 1,
    VISIT  = 1u << 2,
    DELETE = 1u << 3
};
 
class DataBlock
{
public:
    DataBlock(off_t off, off_t size) : _off(off), _size(size), _addr(nullptr), _state(NEW) {}
 
    bool DoMap(int fd)
    {
        _addr = mmap(nullptr, (size_t)_size, PROT_READ | PROT_WRITE,
                     MAP_SHARED, fd, _off);
        if (_addr == MAP_FAILED) {
            perror("mmap");
            _addr = nullptr;
            return false;
        }
        return true;
    }
 
    bool DoUnmap()
    {
        if (_addr == nullptr)
            return true;
        if (munmap(_addr, (size_t)_size) < 0) {
            perror("munmap");
            return false;
        }
        _addr = nullptr;
        return true;
    }
 
    off_t Off() const { return _off; }
    off_t Size() const { return _size; }
    void *Addr() const { return _addr; }
    unsigned State() const { return _state; }
    void SetState(unsigned s) { _state = s; }
 
private:
    off_t _off;
    off_t _size;
    void *_addr;
    unsigned _state;
};
 
class FileCache
{
public:
    explicit FileCache(const std::string &file)
        : _file(file), _fd(-1), _total(0),
          _page((off_t)sysconf(_SC_PAGESIZE)), _cap(3)
    {
        _fd = open(_file.c_str(), O_RDWR);
        if (_fd < 0) {
            perror("open");
            return;
        }
        struct stat st;
        if (fstat(_fd, &st) < 0) {
            perror("fstat");
            return;
        }
        _total = st.st_size;
    }
 
    ~FileCache()
    {
        if (_fd >= 0)
            close(_fd);
    }
 
    std::shared_ptr<DataBlock> GetBlock(off_t raw)
    {
        if (raw < 0 || raw >= _total)
            return nullptr;
 
        off_t off = raw & ~(_page - 1);
 
        auto it = _hash.find(off);
        if (it != _hash.end()) {
            it->second->SetState(VISIT);
        } else {
            off_t size = BlockSize(off);
            if (size <= 0)
                return nullptr;
 
            std::shared_ptr<DataBlock> block = std::make_shared<DataBlock>(off, size);
            if (!block->DoMap(_fd))
                return nullptr;
 
            _hash[off] = block;
            _cache.push_front(block);
        }
 
        DoLRU(off);
        return _hash[off];
    }
 
private:
    off_t BlockSize(off_t off) const
    {
        off_t rest = _total - off;
        return rest < _page ? rest : _page;
    }
 
    void DoLRU(off_t off)
    {
        auto it = _hash.find(off);
        if (it == _hash.end())
            return;
        std::shared_ptr<DataBlock> b = it->second;
 
        if (b->State() & NEW) {
            b->SetState(NORMAL);
            while (_cache.size() > (size_t)_cap) {
                std::shared_ptr<DataBlock> last = _cache.back();
                last->DoUnmap();
                _hash.erase(last->Off());
                _cache.pop_back();
            }
        } else if (b->State() & VISIT) {
            b->SetState(NORMAL);
            _cache.remove(b);
            _cache.push_front(b);
        }
    }
 
    std::string _file;
    int _fd;
    off_t _total;
    off_t _page;
    int _cap;
    std::list<std::shared_ptr<DataBlock>> _cache;
    std::unordered_map<off_t, std::shared_ptr<DataBlock>> _hash;
};
}

几个要点按顺序说。

对齐用的是 raw & ~(_page - 1),前提是页大小是 2 的幂,这一点成立。课件写的是 off & ~(0xFFF),只在 4KB 页上正确;在 16KB 页的机器上算出来的块起点不是页的整数倍,mmap 会直接返回 EINVAL,缓存一块也加载不起来。

合法性检查要拒掉负数。off_t 是有符号的,raw < _total 对 -1 也成立,对齐之后是 -4096,落到 BlockSize 里算出负数长度,mmap 报错。所以条件必须写成 raw < 0 || raw >= _total。

末尾块的长度要单独算,否则会映射到文件末尾之外。文件长度不一定被页整除,最后一块的可用长度是 _total - off;按页向下取,BlockSize 返回 rest < _page ? rest : _page。课件那句 size = _total % gblocksize 在文件大小恰好是页的整数倍时会算出 0,只是因为外面的判断条件刚好把它挡掉了——写 rest 更直接,也不依赖那条等式。

DoLRU 的两个分支对应两种进入方式。新块已经插在头部,状态是 NEW,把它标成 NORMAL 后从尾部淘汰,直到块数回到容量以内;命中块的状态是 VISIT,把它从链表中间摘下来重新插到头部。命中路径不触发淘汰,所以块数不会因为命中而变。

淘汰回收的是地址空间,不是数据

DoUnmap 里的 munmap 解除的只是这段虚拟地址和页表项,页缓存里的数据不受影响。清洁页仍然留在内核页缓存中,下次再映射回来读,通常不再需要读盘;MAP_SHARED 弄脏的页会由内核在合适时机写回文件。"淘汰"在这里省下的是进程的地址空间和页表开销,而不是文件内容——这两件事经常被混为一谈。

这份实现还有一个边界要交代清楚:GetBlock 把 shared_ptr<DataBlock> 交给调用方,而淘汰逻辑会在缓存满时对最久未用的块执行 munmap。调用方手里的指针因此可能在用着的时候失效。要安全,只能在缓存内部拷贝数据,或者在淘汰前检查 use_count()——后者等于放弃"缓存容量固定"这个前提。课件这份代码是演示结构,不是可以拿去直接用于生产的缓存。

跑一遍

造一个 40KB 的文件,然后依次访问前十二个块:

dd if=/dev/zero of=log.txt bs=4096 count=10
#include <cstdio>
#include "LRUCache.hpp"
 
int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "usage: %s file\n", argv[0]);
        return 1;
    }
 
    LRUCache::FileCache fc(argv[1]);
 
    for (int i = 0; i < 12; i++) {
        std::shared_ptr<LRUCache::DataBlock> b = fc.GetBlock((off_t)i * 4096);
        if (b == nullptr) {
            printf("block %d: out of file\n", i);
            continue;
        }
        printf("block %d: off=%ld size=%ld addr=%p\n",
               i, (long)b->Off(), (long)b->Size(), b->Addr());
    }
    return 0;
}

前十个块依次未命中、加载、入队;访问到第四个块(偏移 12288)时缓存里有四块,队尾的块 0 被淘汰,此后每次新块进来都会挤掉队尾那一个。第 10、11 块已经越过文件末尾,GetBlock 返回空指针。课件那份 Main.cc 拿到返回值后直接 b->Addr(),没判空,越界输入会让程序死在这一行——空指针不是"异常情况",在这个接口上是正常返回值,必须判。

编译时注意 C++17:std::shared_ptr 和 unordered_map 的组合在旧标准下也能过,但课件的 Makefile 里写的就是 -std=c++17,按这个来最省事:

lrucache: Main.cc
	g++ -o $@ $^ -std=c++17 -g
 
.PHONY: clean
clean:
	rm -f lrucache

前三次访问的输出会看到块数逐次增加,到第四次之后稳定在 3;gdb 里那三行映射的偏移也就跟着往后滑,这正是 LRU 的全部可见行为。