Author: JayceeZ
C++ 拷贝控制简述
用mmap接口访问文件时边界问题会导致的两个错误
本文主要探索以mmap接口访问文件时，文件自身大小、mmap映射范围和我们所能访问区间之间的关系。主要通过几个小的实验程序来说明。 本文假定读者了解mmap可以作为文件访问的接口，若没有用过可以在Linux中直接man mmap看相关说明，或者去网上搜索其他资料。简单来说，文件的某一段经过mmap系统调用映射后会返回一个地址，这样我们可以像操纵内存一样操纵磁盘上的数据，因此”open +mmap+memcpy+msync “这套文件操作可以在很多的时候代替”open+read/write+fsync“这套文件操作。 但是相比write进行追加写的操作，被mmap映射的地址是无法做到改变被映射文件大小的，那么我们如果想改变文件大小怎么办？如果我们写的地址大于实际文件大小会出现什么情况？如果我们写的地址大于所映射的地址范围会有什么情况？ 通过两组简单的测试，我们可以探究这个问题： 测试1：”文件范围内, mmap范围外” 会产生SIGSEGV段错误 测试1是简单的情况，我们mmap映射的范围小于文件的实际大小，那么当我们访问在文件范围内但不是映射区范围内的地址时，会产生”segmentation fault”(SIGSEGV)错误！这很好理解，因为我们访问了非法的内存地址。 如下图，具体的，我们创建一个1 MB的文件，然后将其前512 KB用mmap映射，然后尝试访问文件第800 KB，第800 KB虽然在文件的范围内，但是不在映射范围内。结果是产生segmentation fault (SIGSEGV) 段错误。 +——————+——————+ file_testmap: | mmapped | not mmapped | +——————+——————+ 0 (KB) 512 ^ 1024 | we try to access here –+ (it will cause seg. fault) 程序1： #define _GNU_SOURCE #include <stdio.h> #include <sys/types.h> #include <sys/stat.h> […]
从内核到用户空间(1) — 用户态缺页处理机制 userfaultfd 的使用
近年，一些本为内核处理的任务，分别出现用户态的实现，有的是为了提升开发灵活性(FUSE、userfaultfd)，有的则是为了提高与外设通信的性能(SPDK、DPDK)。本系列文章对我所了解到的用户空间实现的内核机制进行使用介绍或原理分析。第一篇文章介绍用户态的缺页处理 — userfaultfd机制，以后还可能根据我的学习进度介绍userfaultfd的内核实现原理、FUSE的使用和原理、SPDK等内容。文章若有错误，恳请指正。 userfaultfd 机制让在用户控制缺页处理提供可能，进程可以在用户空间为自己的程序定义page fault handler，增加了灵活性，但也可能由于类似FUSE之于内核FS的问题(调用层次加深)而影响性能。 1. 基本使用步骤 以最基本的用户空间进行匿名页缺页处理为例，(例子代码基本来自userfaultfd的man page[1]，)步骤大致如下： STEP 1. 创建一个描述符uffd 要使用此功能，首先应该用userfaultfd调用[1]来创建一个fd，例如: // userfaultfd系统调用创建并返回一个uffd，类似一个文件的fd uffd = syscall(__NR_userfaultfd, O_CLOEXEC | O_NONBLOCK); 然后，所有的注册内存区间、配置和最终的缺页处理等就都需要用ioctl来对这个uffd操作。ioctl-userfaultfd[2]支持UFFDIO_API、UFFDIO_REGISTER、UFFDIO_UNREGISTER、UFFDIO_COPY、UFFDIO_ZEROPAGE、UFFDIO_WAKE等选项。比如UFFDIO_REGISTER用来向userfaultfd机制注册一个监视区域，这个区域发生缺页时，需要用UFFDIO_COPY来向缺页的地址拷贝自定义数据。 STEP 2. 用ioctl的UFFDIO_REGISTER选项注册监视区域 比如，UFFDIO_REGISTER对应的注册操作如下： // 注册时要用一个struct uffdio_register结构传递注册信息: // struct uffdio_range { // __u64 start; /* Start of range */ // __u64 len; /* Length of range (bytes) */ // }; // […]
qemu-img 文档翻译
(翻译自qemu 3.0的文档) qemu-img [standard options] command [command options] qemu-img 允许你离线地创建、转换或者修改镜像文件。它可以处理所有QEMU支持的镜像格式。 注意： 千万不要用 qemu-img 修改虚拟机(或者其他程序)正使用着的镜像，因为那可能会破坏镜像；对应的，如果读正在修改的镜像，也可能会有不一致的状态产生。 1. Standard options： ‘-h, –help’ 显示帮助信息。 ‘-V, –version’ 显示版本信息。 ‘-T, –trace [[enable=]pattern][,events=file][,file=file]’ Specify tracing options. 指定tracing选项： ‘[enable=]pattern’ 以parttern来指定启动的events。这个选项仅在编译了simple、log或ftrace等3个tracing后端时才能用。要启用多个events或者patterns，用多个-trace即可，用-trace help可以打印列出trace points名称。 ‘events=file’ 马上开启file中列出了的events名称，file中每行为一项event名称或者patterns (存在于trace-events-all文件中的)。同样，这个选项仅在编译了simple、log或ftrace等3个tracing后端时才能用。 ‘file=file’ 将traces的输出打印到log文件中。同样，这个选项仅在编译了simple、log或ftrace等3个tracing后端时才能用。 2. Command: 以下是被支持的命令： amend [–object objectdef] [–image-opts] [-p] [-q] [-f fmt] [-t cache] -o options filename […]
文件打洞 (Hole Punching) 及其应用
一个文件的长度和它实际所占用的磁盘空间很可能是不同的，这主要涉及到稀疏文件(sparse file)和文件打洞(hole punching)的概念。这两个特性需要操作系统和文件系统的支持，目前Linux的ext4、XFS等文件系统都支持这两个特性。 稀疏文件 (Sparse File) 了解系数文件最直观的例子是，创建一个文件，然后用lseek定位到较大的偏移量，在这个偏移量实际写一些内容，这时实际占用的磁盘空间很小，但文件的长度却比较大。比如： #include <fcntl.h> #include <assert.h> int main() { // 打开两个文件file_normal和file_sparse int fd = open(“file_normal”, O_RDWR|O_CREAT, 0755); int fd_sparse = open(“file_sparse”, O_RDWR|O_CREAT, 0755); assert(fd != -1); // 一个从0写入3个字节，一个从1000偏移写入3个字节 lseek(fd, 0, SEEK_SET); lseek(fd_sparse, 100000, SEEK_SET); write(fd, “ABCDEFG”, 3); write(fd_sparse, “ABCDEFG”, 3); close(fd); close(fd_sparse); return 0; } ls的-s选项可以在第一列打印出文件所占的磁盘空间： zjc@~$ ./sparse_file zjc@~$ ls […]
统计代码行数 (LoC) 的超简单 Python 实现
为了统计代码行数(lines of code, LoC)，最简单的思路是用python读取每个所输入的代码文件的行数，然后加起来。 本实现分离了代码文件识别和统计，代码文件由用户给出。 1. 实现： Python实现，用enumerate函数统计可以防止内存占用过大的问题，我们要的只是一个计数，每行读完扔掉即可(pass)。代码如下： #!/usr/bin/env python import sys def file_len(fname): with open(fname) as f: for i, l in enumerate(f): pass return i + 1 file_n = len(sys.argv) – 1 print file_n, “files:” sum_line = 0 for i in range(file_n): this_line = file_len(sys.argv[i + 1]) sum_line += this_line print this_line, “\tLoC\t”, sys.argv[i […]
Bloom Filter 和 Cuckoo Filter 的源码简析
Bloom Filter 和 Cuckoo Filter有类似的用途，很多人将它们称为概率数据结构或者近似成员数据结构(approximate membership data structure)。最近看了一个Bloom Filter和一个Cuckoo Filter的比较好的实现，代码都是用C++实现，代码量也不大，读起来没有什么难度。 本文贴出来的是两个项目的大体构成，不涉及到空间、错误率等的理论分析，希望能给需要的新手一些帮助。 两个项目的网址如下： C++ Bloom filter library: https://code.google.com/p/bloom/ Cuckoo Filter: https://github.com/efficient/cuckoofilter 1. Bloom Filter (https://code.google.com/p/bloom/) 源码目录： $ tree . ├── Makefile ├── bloom_filter.hpp ├── bloom_filter_example01.cpp ├── bloom_filter_example02.cpp ├── bloom_filter_example03.cpp ├── random-list.txt ├── word-list-extra-large.txt ├── word-list-large.txt └── word-list.txt 文件包括三个用于测试example、三个用于测试insert的txt词典，bloom filter的实现在bloom_filter.hpp中。 bloom_filter.hpp中包括3个class：bloom_parameters、bloom_filter和compressible_bloom_filter。其中bloom_parameters是构建一个BF需要的参数，compressible_bloom_filter 类继承自bloom_filter类。 1.1 bloom_filter.hpp bloom_parameters 包含的成员： // […]
存储系统的崩溃一致性问题 (Crash Consistency)
Consistency这个词在计算机各领域用的很多，比如分布式系统、体系结构和存储系统等等。本文只探讨存储系统crash consistency。Crash Consistency问题在存储系统中都会存在(数据库、文件系统、dedup系统 …)，即系统遭遇断电、崩溃等情况时，相关联的数据没有全部持久化可能导致的不一致。本文以文件系统为例进行说明，所有内容基于自己对相关资料的理解，如有错误，恳请指正！ 崩溃为什么会导致不一致 下表整理自我的OSTEP笔记[1]，我们假设了一个有data和inode、bitmap两种metadata的简单文件系统，下表给出了一些可能导致不一致的情况，其中N表示断电时没有写完，F表示断电时已经完成： 多种metadata之间的一致性通常最麻烦：如上表的inode和bitmap，他们之间存在相同冗余信息（bitmap可以从inode推导出，但是这个推导是要遍历所有inode的，bitmap的作用就是用冗余的信息换取性能），并且由于并非在一个磁盘块，无法原子地同时更新，所以如果掉电时只有两者之一成功更新了，那么它们之间相同的信息便存在了不一致。metadata和data之间也存在不一致的情况：如上表中，若两种metadata都更新好了，但是data写到一半掉电了，那么下次开机后根据metadata读data时就会读到坏的数据，因此可以称为不一致。 追究其根本原因，是存储系统中底层硬件的一次磁盘I/O(512字节)，无法保证上层的一次请求的相关联的所有data和metadata的原子写入；反过来想，如果上层的每次请求中data和metadata都连在一起且小于512字节，那么就不用额外的一致性机制保证Crash Consistency。 保证一致性的方法–以WAL为例 由于硬件或者底层的原子写单元和上层存储系统一次请求所涉及的更改不匹配，所以我们只能在上层存储系统中用额外的手段保证crash consistency，常用的方法有: WAL(Write ahead logging, 也叫logging或journaling), CoW(Copy-on-Write, 也叫shadow paging), log-structuring, ordered write, soft updates等等。本文只简单举例说明一下WAL这种最常见的方法如何保证crash consistency： 比如，WAL为了保证bitmap和inode等不同种metadata之间一致性，在更改metadata时，一定要先将这些metadata写入到磁盘上的log区域，然后再对目标位置的metadata进行更改，这样，如果系统在写log时掉电了，原始的metadata没有影响，如果在写原位置metadata时掉电了，又可以在开机时从log进行重做(所以文件系统中的WAL类似于DBMS中的redo log)。 不同人对一致性有不同的认识 对于一个对任何事要求都很低的人来说，也许只有文件系统由于crash而被破坏了、不能再正常使用了才是不一致；他可能认为仅仅metadata和data的不一致可能并不算不一致，因为文件系统还会正常工作，只是被FS服务的用户或应用得到了错误的数据，谁叫他把电线拔了呢?。因此对一致性的定义、对一致性强弱的要求也是因人而异，因系统设计目标而异的。 比如，ext4是一种基于WAL的文件系统，具体提供了3种logging模式：journal, ordered(default), writeback。这三种方法对一致性的强度依次减弱，可以帮助我们理解为什么不同人、不同场景需要不同强度的一致性：journal是把所有data、metadata先进行logging[2]；ordered是用ordered write的方法保证data和metadata的一致性，用logging保证不同类别metadata之间的一致性，ordered write指但是先写data完成，再写metadata的顺序，data因此也不用进行logging；writeback则不管data和metadata的先后顺序，data也不写log，可能刚刚提到的要求很低的人和对性能要求更高的人才会用这个参数吧。 摘自kernel文档[2] data=journal All data are committed into the journal prior to being written into the main file system. Enabling this mode […]
A Primer on Memory Consistency & Cache Coherence 笔记1
本文是对《A Primer on Memory Consistency and Cache Coherence》这本书前一半内容的记录和理解，主要涉及memory consistency model。 1. 引言 对于多处理器共享内存系统来说，consistency和coherence都关注的是共享内存(shared memory)及cache的正确性问题，而人们把这个问题拆成两个方面是为了更好地将这个复杂问题分治解决。 1.1 Consistency 一般需要被详细讨论的是多核(或线程)共享内存(shared memory)的consistency模型，因为单核单线程问题相对简单直观。内存consistency模型规定的是：多线程同时进行load/store操作时，怎样的执行顺序是对的，怎样是错的。比较简单直接的consistency模型包括sequential consistency、TSO(total store consitency，x86使用)等。 1.2 Coherence 本文主要记录与consistency有关的内容，但因为consistency的实现与coherence有关，所以要简单介绍下coherence及其与consistency的关系。 虽然coherence的中文也翻译成“一致性”，但coherence这个词通常跟在cache后面，即缓存一致性(cache coherence)，解决缓存一致性问题的方法也被称为缓存一致性协议(cache coherence protocol)。那么共享内存系统的cache为什么需要coherence协议保证共享内存系统正确性呢？这是因为cache一般分为L1、L2和L3等很多层，L1等比较高的层级中，cache是每个核所独占的，一般只有L3、memory等层级才是共享的。在每个核独占的层级中，可能出现统一内存地址的数据在不同独占cache中数值不一样的情况，这时cache的状态可以称为incoherent。通过无效化等coherence协议，可以保证多核系统cache的正确性。 1.3 Consistency 和 Coherence的关系 对于sequential consistency和TSO等比较简单的consistency model来说，保证了coherence的cache可以被看成一个“黑盒”甚至对consistency model透明，黑盒中有cache实现有保证cache使用正确的coherence protocol，而consistency更关注程序(或处理器核)的访存顺序。因此对于简单的consistency model和coherence protocol来说，两者是解耦的。 1.4 一个小例子 如果上边几段不易理解，作者在书中用一个例子解释了这两个名词的基本含义，简单记录如下，有改编： consistency的例子 设想有三个人，计算机体系结构课程老师、教务处网站管理员和上课的学生，老师最开始在教务处上登记了上课的地点是152教室，但是开学第一节课后发现选课的人太多了152坐不下，于是准备下节课开始换到更大的252教室，于是老师先①找教务处网站管理员说“请你把网站上我课的教室信息改到252（要求①），随后通知学生们去教务处网站查询下节课的上课地点（要求②）。这就产生了一个问题，网站管理员可能是第二天才更新的网站，而学生是接到老师的通知马上重新查看了教务处网站，因此学生下周又来到了152教室，老师的计划和最后的结果出现了不一致情况。 问题就出在老师的做法无法保证学生在网站被修改之后再去网站查询。要想保证学生查到正确的信息，一种简单的办法就是保证管理员的确更新了数据，然后再通知学生们。这种简单的办法就可以称为一种一致性模型。 我们把这个例子对应到实际的内存系统中，给管理员和学生要做的两件事（要求①和②）可以分别看成一条store命令和一条load命令，目标都是教务处网站上老师的教室号，这个目标可以看成同一块内存地址，因此对同一内存地址执行的store和load命令是否可以调换顺序(管理员在学生查询才修改了网站)，调换顺序后是否破坏了程序的正确性，就是内存一致性模型memory consistency model所负责的。也就是说，出现上述情况算不算错，应该是当前的一致性模型所判断的：相对于我们每个人心中直觉上的一致性模型，这种走错教室的情况肯定是错了，但是对于一个性格怪异的老师，也许他觉得这样也是对的，比如他可以找他的同事帮他上152教室的课，他自己上252教室的课，也正因他如此怪异，所以他最开始联系网站管理员时也遵循了他心中的怪异的一致性模型，没有等网站确实修改就给学生们发了查询教室的通知。 coherence的例子 紧接上个例子，与之不同的是，很多学生在最开始选课的时候就把《体系结构》这门课的教室152记在了自己的小本本上，但是后来，管理员将网站上教室信息改成了252。虽然学生的小本本上和教务处网站上的信息应该是同一个信息，应该是一样的，但是这时两者一个152，一个252，这就出现了incoherent的情况。 在内存系统中，学生的小本本就相当于cache，而教务处网站相当于memory，学生将memory中的某个值拷贝到了cache中，当memory被其他人更新时，学生自己的cache就应该同时立即处于无效的状态。这里出现incoherent的原因就是没有一个cache coherence protocol来保证cache的正确性。比如，一个简单的coherence protocol可以这么干：在网站更新后，老师挨个找到每个学生，把他们的小本本记的152划掉?，无效化协议就是这种思想。 2. […]