【Linux 内核分析课程作业 1】mmap 实现一个 key-valueMap

作业一

功能要求利用 mmap(虚拟内存映射文件) 机制实现一个带持久化能力的 key-valueMap 系统，至少支持单机单进程访问。(可能用到的 linux API: mmap、msync、mremap、munmap、ftruncate、fallocate 等)

电子版提交方式：
2023 年 11 月 20 日 18:00 前通过西电智课平台提交

提交内容

(1) 源代码，包含必要的注释;(2) 简单的说明文件，说明程序如何运行。

邮件主题、附件命名方式：主题：小作业 1-学号 - 姓名 (英文半角，非下划线).
附件：学号 - 姓名.rar，请严格按照命名规范提交!。
联系邮件：xxxxxxx
请勿抄袭，如有雷同，都将以零分计。

代码说明

运行测试结果

$gcc mmapMap.c && ./a.out
强制同步比 0.00 > 0.078 秒
强制同步比 0.10 > 0.276 秒
强制同步比 0.20 > 0.384 秒
强制同步比 0.30 > 0.513 秒
强制同步比 0.40 > 0.663 秒
强制同步比 0.50 > 0.602 秒
强制同步比 0.60 > 0.807 秒
强制同步比 0.70 > 0.775 秒
强制同步比 0.80 > 0.842 秒
强制同步比 0.90 > 0.910 秒
强制同步比 1.00 > 0.972 秒
1
2
3
4
5
6
7
8
9
10
11
12

背景

Linux 内存文件映射是一种将文件内容映射到进程地址空间的技术，它允许进程直接在内存中访问文件，而无需通过 read()​ 或 write()​ 等系统调用进行数据传输。这种技术的核心是 mmap()​ 系统调用，它允许将文件的一部分或全部映射到进程的地址空间，使得文件的内容可以直接通过内存地址来访问和修改。

内存文件映射的主要特点和使用方法：

1. 直接访问文件内容： 内存文件映射允许进程直接读取和写入文件内容，就好像操作内存一样，而不需要使用标准的文件 I/O 操作（例如 read()​ 和 write()​）。
2. 性能优势： 由于避免了频繁的系统调用和数据拷贝，因此内存文件映射通常可以提供更好的性能，特别是对于大文件的处理或者需要频繁读写的情况。
3. 共享内存： 多个进程可以通过内存文件映射共享同一个文件，这对于进程间通信很有用。
4. 写时复制： 当多个进程映射同一个文件时，对该文件的写操作会使用写时复制技术，每个进程会获得一个文件内容的独立副本，从而避免了相互之间的干扰。

使用 mmap()​ 函数进行内存文件映射时，需要指定文件描述符、映射大小、映射起始位置以及一些其他参数。通常的步骤如下：

1. 使用 open()​ 函数打开文件，获取文件描述符。
2. 使用 mmap()​ 函数创建映射，将文件映射到内存中。
3. 对映射区域进行读写操作。
4. 使用 munmap()​ 函数取消映射。

可能用到的 linux API: mmap、msync、mremap、munmap、ftruncate、fallocate 介绍：

1. mmap() ：
   • void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);​
   • 用于将文件或者设备映射到进程的地址空间。
   • 参数 addr​ 是映射的地址，一般设置为 NULL 以由系统自动选择。
   • length​ 是映射区域的大小。
   • prot​ 表示映射区域的保护方式（读、写、执行等）。
   • flags​ 包含映射的一些特性，比如是否共享、是否采用匿名映射等。
   • fd​ 是要映射的文件描述符。
   • offset​ 是文件中的偏移量。
2. msync() ：
   • int msync(void *addr, size_t length, int flags);​
   • 用于将指定地址范围的内存数据同步回文件，保持内存和文件内容的一致性。
   • addr​ 是内存区域的起始地址。
   • length​ 是要同步的长度。
   • flags​ 可以指定同步方式，如 MS_ASYNC（异步）、MS_SYNC（同步）等。
3. mremap() ：
   • void *mremap(void *old_address, size_t old_size, size_t new_size, int flags, ...);​
   • 允许重新调整内存映射的大小和位置。
   • old_address​ 是原映射区域的起始地址。
   • old_size​ 是原映射区域的大小。
   • new_size​ 是新的映射区域大小。
   • flags​ 可以指定一些选项，如 MREMAP_MAYMOVE（允许移动映射）等。
4. munmap() ：
   • int munmap(void *addr, size_t length);​
   • 用于取消内存映射，释放指定地址区域的内存。
   • addr​ 是要取消映射的起始地址。
   • length​ 是取消映射的长度。
5. ftruncate() ：
   • int ftruncate(int fd, off_t length);​
   • 用于改变一个打开文件的大小。
   • fd​ 是文件描述符。
   • length​ 是新的文件大小。
6. fallocate() ：
   • int fallocate(int fd, int mode, off_t offset, off_t len);​
   • 用于为文件分配空间。
   • fd​ 是文件描述符。
   • mode​ 可以指定预留空间或初始化空间。
   • offset​ 是文件中的偏移量。
   • len​ 是要分配的空间大小。

完整代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define FILENAME "kv_store.dat"

/***************************************************************
    - key-valueMap 数据结构部分
 **************************************************************/

#define MAX_KEY_SIZE 64
#define MAX_VALUE_SIZE 128
#define MAX_ENTRIES 4096

struct KeyValue {
    char key[MAX_KEY_SIZE];
    char value[MAX_VALUE_SIZE];
};

typedef struct keyValueStore {
    struct KeyValue entries[MAX_ENTRIES];
    size_t size;
} KeyValueStore;

// 增加一个条目
// 返回值：-1 表示失败，>=0 表示成功
int add_entry(KeyValueStore *kv_store, const char *key, const char *value) {
    if (kv_store->size < MAX_ENTRIES) {
        // 查重
        for (size_t i = 0; i < kv_store->size; ++i) {
            if (strcmp(kv_store->entries[i].key, key) == 0) {
                return -1;
            }
        }
        struct KeyValue new_entry;
        strncpy(new_entry.key, key, MAX_KEY_SIZE - 1);
        strncpy(new_entry.value, value, MAX_VALUE_SIZE - 1);

        kv_store->entries[kv_store->size++] = new_entry;
        return kv_store->size - 1;
    } else {
        // printf("错误：已达到最大条目数。\n");
        return -1;
    }
}

// 删除一个条目
// 返回值：-1 表示失败，>=0 表示成功
int delete_entry(KeyValueStore *kv_store, const char *key) {
    for (size_t i = 0; i < kv_store->size; ++i) {
        if (strcmp(kv_store->entries[i].key, key) == 0) {
            // 移动元素来删除
            memmove(&kv_store->entries[i], &kv_store->entries[i + 1],
                    (kv_store->size - i - 1) * sizeof(struct KeyValue));
            kv_store->size--;
            return kv_store->size;
        }
    }
    // printf("错误：找不到项。\n");
    return -1;
}

/***************************************************************
    - mmap 部分
 **************************************************************/

// 打开一个文件，初始化内存为 mmap, 但是置空
KeyValueStore *mmap_init() {
    KeyValueStore kv_store;
    memset(&kv_store, 0, sizeof(KeyValueStore));
    int fd = open(FILENAME, O_RDWR | O_CREAT,
                  (mode_t)0600); // 如果文件不存在也会新建
    if (fd == -1) {
        perror("Error opening file for writing");
        exit(EXIT_FAILURE);
    }

    size_t file_size = sizeof(KeyValueStore);
    // 转变一个文件的大小
    if (ftruncate(fd, file_size) == -1) {
        perror("Error truncating file");
        exit(EXIT_FAILURE);
    }

    void *buf = mmap(0, file_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (buf == MAP_FAILED) {
        close(fd);
        perror("Error mapping the file");
        exit(EXIT_FAILURE);
    }

    memcpy(buf, &kv_store, sizeof(KeyValueStore));
    close(fd);
    return buf;
}

// 打开一个文件，初始化内存为 mmap, 为读取的文件内容
KeyValueStore *mmap_load() {
    int fd = open(FILENAME, O_RDWR); // 文件必须存在
    if (fd == -1) {
        perror("Error opening file for writing");
        exit(EXIT_FAILURE);
    }

    size_t file_size = sizeof(KeyValueStore);
    if (ftruncate(fd, file_size) == -1) {
        perror("Error truncating file");
        exit(EXIT_FAILURE);
    }

    void *buf = mmap(0, file_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (buf == MAP_FAILED) {
        close(fd);
        perror("Error mapping the file");
        exit(EXIT_FAILURE);
    }

    close(fd);
    return buf;
}

// 关闭 mmap
void mmap_destroy(KeyValueStore *buf) {
    size_t file_size = sizeof(KeyValueStore);
    if (munmap(buf, file_size) == -1) {
        perror("Error unmapping the file");
        exit(EXIT_FAILURE);
    }
}

// 强制同步 mmap
void mmap_persist(KeyValueStore *buf) {
    size_t file_size = sizeof(KeyValueStore);
    if (msync(buf, file_size, MS_SYNC) == -1) {
        perror("Error syncing to disk");
    }
}

/***************************************************************
    - 测试和运行
 **************************************************************/

// 测试运行时间
// - rate: 强制同步比
void test_time(KeyValueStore *buf, double rate) {
    // Start measuring time
    clock_t start = clock();

    // 操作
    char key[MAX_KEY_SIZE];
    char value[MAX_VALUE_SIZE];
    int r;
    for (int i = 0; i < 10000; i++) {
        r = rand() % MAX_ENTRIES;
        // Add
        sprintf(key, "key%d", r);
        sprintf(value, "value%d", r);
        add_entry(buf, key, value);

        r = rand() % MAX_ENTRIES;
        // Delete
        sprintf(key, "key%d", r);
        delete_entry(buf, key);

        // 强制同步
        if (rate > 0 && i % (int)(1 / rate) == 0) {
            mmap_persist(buf);
        }
    }

    // 停止计时
    clock_t end = clock();
    double elapsed = (double)(end - start) / CLOCKS_PER_SEC;

    printf("强制同步比 %.2f > %.3f 秒\n", rate, elapsed);
}

int main() {
    KeyValueStore *buf = mmap_init();
    for (double rate = 0; rate <= 1; rate += 0.1) {
        test_time(buf, rate);
    }
    mmap_destroy(buf);

    // 打印存储数据
    KeyValueStore *buf1 = mmap_load();
    // printf("Stored Data:\n");
    // for (size_t i = 0; i < buf->size; ++i) {
    //     printf("Key: %s, Value: %s\n", buf->entries[i].key,
    //            buf->entries[i].value);
    // }
    mmap_destroy(buf1);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

参考

Linux mmap 内存映射 - 掘金 (juejin.cn)

‍