May 15
续上篇:

[译] C程序员该知道的内存知识 (1)

这是本系列的第二篇,预计还会有2篇,感兴趣的同学记得关注,以便接收推送,等不及的推荐阅读原文。 




先放图镇楼: 

点击在新窗口中浏览此图片

来源:Linux地址空间布局 - by Gustavo Duarte

关于图片的解释可参见上篇。

开始吧。 





# 理解堆上的内存分配

工具箱: 

* brk(), sbrk() - 修改数据段的大小
* malloc() 家族 - 可移植的 libc 内存分配器

堆上的内存分配,最简单的实现可以是修改 program break[2](译注:参见上图中部右侧)的上界,申请对原位置和新位置之间内存的访问权限。如果就这么搞的话,堆上内存分配和栈上分配一样快(除了换页的开销,一般我们认为栈是被锁定在内存中;译注:指栈不会被换出到磁盘,可以用mlock限制OS对一段地址空间使用swap)。但这里还是有只猫(cat),我是说,有点毛病(catch),见鬼。(译tu注cao:这个真难翻)

char *block = sbrk(1024 * sizeof(char));

* 我们无法回收不再使用的内存块   
* 它也不是线程安全的,因为堆是在线程间共享的
* 这个接口(译注:sbrk)也很难移植,因此库函数被禁止碰这个break。

[qoute]man 3 sbrk — 各种系统的 sbrk 使用多种不同的参数类型,常见的包括 int, ssize_t, ptrdiff_t, intptr_t[/quote]

由于这些问题,libc要求实现统一的内存分配接口,具体实现有很多[3](译注:例如glibc,jemalloc,tcmalloc等),但都给你提供了线程安全、支持任意尺寸的内存分配器……只是要付出点代价——延迟,因为得引入锁机制,以及用来维护已用/可用内存的数据结构,和额外的内存开销。还有,堆也不是唯一的选项,在大块内存分配的情况下常常也会用内存映射段(Memory Mapping Segment,MMS)。

[qoute]man 3 malloc —— 一般来说,malloc() 从堆上分配内存,  ... 当分配的内存块大于 MMAP_THRESHOLD 时,glibc的 malloc() 实现使用私有匿名映射来分配内存。[/qoute]

(译注:Linux 下 mmap 的 flags 参数是个 bitmap,其中有两个 bit 分别为 MAP_PRIVATE、MAP_ANONYMOUS,对应引用中提到的“私有”、“匿名”) 

由于堆空间在 start_brk 和 brk (译注:即 heap 的下界和上界,建议对照图中右侧的标注)之间总是连续的(译注:这里指的是虚拟地址空间连续,但其中每一页都可能映射到任一物理页),因此你无法在中间打个洞来减少数据段的尺寸。比如这个场景: 

char *truck = malloc(1024 * 1024 * sizeof(char));
char *bike  = malloc(sizeof(char));
free(truck);


堆分配器将会调大 brk,以便给 truck 腾出空间。对于 bike 也一样。但是当 truck 被释放后,brk 不能被调小,因为 bike 正占着高位的地址。结果是,你的进程 **可以** 重用 truck 的内存,但 **不能** 退还给OS,除非 bike 也被释放。当然你也可以用 mmap 来分配 truck 所需的空间,不放在堆内存段里,就可以不影响 program break ,但这仍然无法解决分配小块内存导致的空洞(换句话说就是“引起碎片化”)。

注意 free() 并不总是会缩小数据段,因为这是一个有很大潜在开销的操作(参见后文“对按需调页的解释”)。对于需要长时间运行的程序(例如守护进程)来说这会是个问题。有个叫  malloc_trim() 的 GNU 扩展可以用来从堆顶释放内存,但可能会慢得令人蛋疼,尤其对于大量小对象的情况,所以应该尽量少用。

## 什么时候应该使用自定义分配器

有一些实际场景中通用分配器有短板,例如大量分配固定尺寸的小内存。这看起来不像是典型的场景,但实际上出现得很频繁 。例如,用于查找的数据结构(典型如树、字典树)需要分配大量节点用于构造其层次结构。在这个场景下,不仅碎片化会是个问题,数据的局部性也是。cache效率高的数据结构会将key放在一起(最好在同一个内存页),而不是和数据混在一起。默认的分配器不能保证下次分配时还在同一个block,更糟的是分配小单元的额外空间开销。解决办法在此:

X

来源: Slab by wadem, on Flickr (CC-BY-SA)

(译注:原图无法打开了,另贴一张)

点击在新窗口中浏览此图片

来源:IBM - Linux slab 分配器剖析


## Slab分配器

工具箱:
* posix_memalign() - 分配对齐的内存

Bonwick 为内核对象缓存写的这篇文章[4]介绍了 slab 分配器的原理,也可用于用户空间。Okay,我们对绑定在CPU上的 slab 不感兴趣 —— 就是你找分配器要一块内存,例如说一整页,然后切成很多固定大小的小块。如果每个小块都能保存至少一个指针或一个整数,你就可以把他们串成一个链表 ,表头指向第一个空闲元素。

/* Super-simple slab. */
struct slab {
  void **head;
};

/* Create page-aligned slab */
struct slab *slab = NULL;
posix_memalign(&slab, page_size, page_size);
slab->head = (void **)((char*)slab + sizeof(struct slab));

/* Create a NULL-terminated slab freelist */
char* item = (char*)slab->head;
for(unsigned i = 0; i < item_count; ++i) {
  *((void**)item) = item + item_size;
  item += item_size;
}
*((void**)item) = NULL;


译注:
1. 代码里用的二级指针可能让人有点晕,这是Linus推崇的链表实现,推荐阅读"linus torvalds answers your questions"[5],在favorite hack这一节,是个很有趣的思维训练
2. 第8行 `posix_memalign` 分配了一页内存,并且对齐到页边界,这意味着正好拿到了一个物理页
3. 因为申请到的 slab 大小是一个page,所以 `item_count` = `page_size` / `item_size`;其中 `item_size` 可以根据应用需要指定。

然后内存分配就简单到只要弹出链表的头结点就行了,内存释放则是插入头结点。这里还有个优雅的小技巧:既然 slab 对齐到了页边界,你只要将指针向下取整到 page_size 就能得到这个 slab 的指针。

/* Free an element */
struct slab *slab = (void *)((size_t)ptr & PAGESIZE_BITS);
*((void**)ptr) = (void*)slab->head;
slab->head = (void**)ptr;

/* Allocate an element */
if((item = slab->head)) {
  slab->head = (void**)*item;
} else {
  /* No elements left. */
}


译注:对于 page_size = 4KB 的页面,PAGESIZE_BITS = 0xFFFFF000,ptr & PAGESIZE_BITS 清零了低12位,正好是这一页的开始,也就是这个slab的起始地址。

太棒了,但是还有binning(译注:应该是指按不同的长度分桶),变长存储,cache aliasing(译注:同一个物理地址中的数据出现在多个不同的缓存行中),咖啡因(译注:这应该是作者在逗逼了),...怎么办?可以看看我之前为 Knot DNS 写的代码[6],或者其他实现了这些点的库。例如,(喘口气),glib 里有个很整齐的文档[7],把它称为“memory slices”。 

译注:slab 分配器适合大量小对象的分配,可以避免常见的碎片问题;在内核中的实现还可以支持硬件缓存对齐,从而提高缓存的利用率。

## 内存池

工具箱:
* obstack_alloc() - 从object stack中分配内存
(译注:指 GNU 的 obstack ,用stack来保存object的内存池实现)

正如slab分配器一样,内存池比通用分配器好的地方在于,你每次申请一大块内存,然后像切蛋糕一样一小块一小块切出去,直到不够用了,然后你再申请一大块。还有,当你都处理完了以后,你就可以收工,一次性释放所有空间。

是不是特别傻瓜化?因为确实如此,但只是针对特定场景如此。你不需要考虑同步,也不需要考虑释放。再没有忘记回收的坑了,数据的局部性也更加符合预期,而且对于小对象的开销也几乎为0。

这个模式特别适合很多类型的任务,包括短生命周期的重复分配(例如网络请求处理),和长生命周期的不可变数据(例如frozen set;译注:创建后不再改变的集合)。你不再需要逐个释放对象(译注:可以最后批量释放)。如果你能合理推测出平均需要多少内存,你还可以将多余的内存释放,以便用于其他目的。这可以将内存分配问题简化成简单的指针运算。 

而且你很走运 —— GNU libc 提供了,嗬,一整套API来干这事儿。这就是 obstacks ,用栈来管理对象。它的 HTML 文档[8] 写得不咋地,不过抛开这些小缺陷,它允许你完成基于内存池的分配和回收(包括部分回收和全量回收)。

/* Define block allocator. */
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free

/* Initialize obstack and allocate a bunch of animals. */
struct obstack animal_stack;
obstack_init (&animal_stack);
char *bob = obstack_alloc(&animal_stack, sizeof(animal));
char *fred = obstack_alloc(&animal_stack, sizeof(animal));
char *roger = obstack_alloc(&animal_stack, sizeof(animal));

/* Free everything after fred (i.e. fred and roger). */
obstack_free(&animal_stack, fred);

/* Free everything. */
obstack_free(&animal_stack, NULL);


译注:obstack这些api实际都是宏;需要通过宏来指定找OS分配和回收整块内存用的方法,如上第2、3行所示。由于对象使用栈的方式管理(先分配的最后释放),所以释放 fred 的时候,会把 fred 和在 fred 之后分配的对象(roger)一起释放掉。 

还有个小技巧:你可以扩展栈顶的那个对象。例如带缓冲的输入,变长数组,或者用来替代 realloc()-strcpy() 模式(译注:重新分配内存,然后把原数据拷贝过去): 

/* This is wrong, I better cancel it. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "fred", 5);
obstack_free (&animal_stack, obstack_finish(&animal_stack));

/* This time for real. */
obstack_grow(&animal_stack, "long", 4);
obstack_grow(&animal_stack, "bob", 4);
char *result = obstack_finish(&animal_stack);
printf("%s\n", result); /* "longbob" */


译注:前三行是作者逗逼了,看后四行就行;用 obstack_grow 扩展栈顶元素占用的内存,扩展结束后调用 obstack_finish 结束扩展,并返回栈顶元素的地址。

## 对按需调页(demand paging)的解释

工具箱:
* mlock() - 锁定/解锁内存(避免被换出到swap)
* madvise() - 给(内核)建议指定内存范围的处置方式

通用内存分配器不立即将内存返回给系统的原因之一是,这个操作开销很大。系统需要做两件事:(1) 建立 **虚拟** 页到 **真实(real)** 页的映射,和 (2) 给你一个清零的**真实**页。这个真实页被称为**帧(frame)**,现在你知道它们的差别了。每一帧都必须被清空,毕竟你不希望 OS 泄漏其他进程的秘密,对吧。这里还有个小技巧,还记得 **overcommit** 吗?虚拟内存分配器只把这个交易刚开始的那部分当回事,然后就开始变魔术了 —— 页表里的大部分页面并不指向一个真实页,而是指向一个特殊的全 0 页面。 

每次你想要访问这个页面时,就会触发一个 page fault,这意味着内核会暂停 进程的执行,分配一个真实页、更新页表,然后恢复进程,并假装什么也没发生。这是汇总在一句话里、我能做出的最好解释了,这里[9]还有更个详细的版本。这也被称作**“按需调页”(demand paging)** 或 **“延迟加载”(lazy loading)**。

引用
斯波克船长说“人无法召唤未来”,但这里你可以操控它。


(译注:星际迷航,斯波克说“One man cannot summon the future.”,柯克说“But one man can change the present.”)

内存管理器不是先知,他只是保守地预测你访问内存的方式,而你自己也未必更清楚(你将会怎样访问内存)。(如果你知道)你可以将一段连续的内存块锁定在**物理**内存中,以避免后续的page fault: 

char *block = malloc(1024 * sizeof(char));
mlock(block, 1024 * sizeof(char));


(译注:访问被换出到swap的页面会触发page fault,然后内存管理器会从磁盘中载入页面,这会导致较严重的性能问题;用 mlock 将这段区域锁定后,OS就不会被操作系统换出到swap;例如,在允许的情况下,MySQL会用mlock将索引保持在物理内存中)

注意:你还可以根据自己的内存使用模式,给内核提出建议 

char *block = malloc(1024 * sizeof(block));
madvise(block, 1024 * sizeof(block), MADV_SEQUENTIAL);


对建议的解释是平台相关的,系统甚至可能选择忽略它,但大部分平台都处理得很好。但不是所有建议都有良好的支持,有些平台可能会改变建议的语义(如MADV_FREE移除私有脏页;译注:“脏页”,dirty page,是指分配以后有过写入,其中可能有未保存的数据),但是最常用的还是MADV_SEQUENTIAL, MADV_WILLNEED, 和 MADV_DONTNEED 这神圣三人组(译注:holy trinity,圣经里的三位一体,作者用词太跳脱……)。

译注:还记得《踩坑记:go服务内存暴涨》里对 MADV_DONTNEED 和 MADV_FREE 的解释吗?这里再回顾下
* MADV_DONTNEED:不再需要的页面,Linux会立即回收
* MADV_FREE:不再需要的页面,Linux会在需要时回收
* MADV_SEQUENTIAL:将会按顺序访问的页面,内核可以通过预读随后的页面来优化,已经访问过的页面也可以提前回收
* MADV_WILLNEED:很快将访问,建议内核提前加载




又到休息点,这篇暂时到这里。 

下一篇会继续翻译下一节《Fun with memory mapping》,还有很多有意思的内容,敬请关注~

顺便再贴下之前推送的几篇文章,祝过个充实的五一假期~

* 《踩坑记:go服务内存暴涨》 
* 《TCP:学得越多越不懂》 
* 《UTF-8:一些好像没什么用的冷知识
* 《关于RSA的一些趣事
* 《程序员面试指北:面试官视角




参考链接:
[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/

[2] sbrk(2) - Linux man page
https://linux.die.net/man/2/sbrk

[3] C Programming/stdlib.h/malloc
https://en.wikibooks.org/wiki/C_Programming/C_Reference/stdlib.h/malloc#Implementations

[4] The Slab Allocator: An Object-Caching Kernel Memory Allocator
https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a

[5] linus torvalds answers your questions
https://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions

[6] Knot DNS - slab.h
https://github.com/CZNIC-Labs/knot/blob/1.5/src/common-knot/slab/slab.h

[7] glib  - memory slices
https://developer.gnome.org/glib/stable/glib-Memory-Slices.html

[8] GNU libc - Obstacks
https://www.gnu.org/software/libc/manual/html_node/Obstacks.html

[9] How the kernel manages your memory
http://duartes.org/gustavo/blog/post/how-the-kernel-manages-your-memory/
May 2
上篇 《踩坑记:go服务内存暴涨》还挺受欢迎的。虽然文中的核心内容很少,但是为了让大多数人能读懂,中间花了很大的篇幅来解释。

尽管如此,我仍然觉得讲得不够透,思来想去觉得还是文中提到的《What a C programmer should know about memory》[1]讲得好,想借着假期翻译一下,也借机再学习一遍(顺便练习英文)。

内容有点长,我会分成几篇。

以下是正文。

# C程序员应该知道的内存知识

2007年,Ulrich Drepper 大佬写了一篇“每个程序员都应该知道的内存知识”[2],特别长,但干货满满。

但过去了这么多年(译注:原文写于2015年2月),“虚拟内存”这个概念对很多人依然很迷,就像*某种魔法*。呃,实在是忍不住引用一下(译注:应该是指皇后乐队的 A Kind of Magic)。

即使是该文的正确性,这么多年以后仍然被质疑[3](译注:有人在stackoverflow上提问文中内容有多少还有效)。出了什么事?

引用
北桥?这是什么鬼?这可不是街头械斗。


(译注:北桥是早年电脑主板上的重要芯片,用来处理来自CPU、内存等设备的高速信号)

我会试着展现学习这些知识的实用性(即你可以做什么),包括“学习锁的基本原理”,和更多有趣的东西。你可以把这当成那篇文章和你日常使用的东西之间的胶水。

文中例子会使用 Linux 下的 C99 来写(译注:1999年版的c语言标准),但很多主题都是通用的。注:我对 Windows 不太熟悉,但我会很高兴附上能解释它的文章链接(如果有的话)。我会尽量标注哪些方法是特定平台相关的。但我只是个凡人,如果你发现有出入,请告诉我。

# 理解虚拟内存 - 错综复杂

除非你在处理某些嵌入式系统或内核空间代码,否则你会在保护模式下工作。(译注:指的是x86 CPU提出的保护模式,通过硬件提供的一系列机制,操作系统可以用低权限运行用户代码)。这*太棒了*,你的程序可以有独立的 [虚拟] 地址空间。“虚拟”这个词在这里很重要。这表示,包括其他一些情况,你不会被可用内存限制住,但也没有资格使用任何可用内存。想用这个空间,你得找OS要一些真东西来做“里子”,这叫 映射(mapping)。这个里子(backing)可以是物理内存(并不一定需要是RAM),或者持久存储(译注:一般指硬盘 )。前者被称为*“匿名映射”*。别急,马上讲重点。

虚拟内存分配器(VMA,virtual memory allocator)可能会给你一段并不由他持有的内存,并且徒劳地希望你不去用它。就像如今的银行一样(译注:应该是指银行存款)。这被称为 overcommiting\[4\](译注:指允许申请超过可用空间的内存),有一些正当的应用有这种需求(例如稀疏数组),这也意味着内存分配不会简单被拒绝。

char *block = malloc(1024 * sizeof(char));
if (block == NULL) {
    return -ENOMEM; /* sad :( */
}


检查 NULL 返回值是个好习惯,但已经没有过去那么强大了。由于 overcommit 机制的存在,OS可能会给你的内存分配器一个有效的指针,但是当你要访问它的时候 —— 铛*。这里的“*铛”是平台相关的,但是通常表现为你的进程被 OOM Killer [5]干掉。(译注:OOM 即 Out Of Memory,当内存不足时,Linux会根据一定规则挑出一个进程杀掉,并在 dmesg 里留下记录)

—— 这里有点过度简化了;在后面的章节里有进一步的解释,但我倾向于在钻研细节之前先过一遍这些更基础的东西。

# 进程的内存布局

进程的内存布局在 Gustavo Duarte 的《Anatomy of a Program in Memory》[6] 里解释得很好了,所以我只引用原文,希望这算是*合理使用*。我只有一些小意见,因为该文只介绍了 x86-32 的内存布局,不过还好 x86-64 变化不大,除了进程可以用大得多的空间 —— 在 Linux 下高达 48 位。

点击在新窗口中浏览此图片

(来源:Linux地址空间布局 - by Gustavo Duarte)

译注:针对上图加一些解释备查

1. 图中显示的地址空间是由高到低,0x00000000在底部,最高0xFFFFFFFF,一共4GB(2^32)。
2. 高位的1GB是内核空间,用户代码 **不能** 读写,否则会触发段错误。图右侧标注的 0xC0000000 即 3GB;TASK\_SIZE 是Linux内核编译配置的名称,表示内核空间的起始地址。
3. Random stack offset:加上随机偏移量以后可以大幅降低被栈溢出攻击的风险。
4. Stack(grows down): 进程的栈空间,向下增长,栈底在高位地址,PUSH指令会减小CPU的SP寄存器(stack pointer)。图右侧的 RLIMIT\_STACK 是内核对栈空间大小的限制,一般是8MB,可以用 setrlimit 系统调用修改。
5. Memory Mapping Segment:内存映射区,通过mmap系统调用,将文件映射到进程的地址空间(包括 libc.so 这样的动态库),或者匿名映射(不需要映射文件,让OS分配更多有里子的地址空间)。
6. Heap:我们常说的堆空间,从下往上增长,通过brk/sbrk系统调用扩展其上限
7. BSS段:包含未初始化的静态变量   
8. Data段:代码里静态初始化的变量
9. Text段(ELF):进程的可执行文件(机器码)
10. 这里说的段(segment)的概念,源于x86 cpu的段页式内存管理

图中也展示了 内存映射段(memory mapping segment, MMS)是向下增长的,但并不总是这样。MMS通常(详见Linux 内核代码 x86/mm/mmap.c:113 和 arch/mm/mmap.c:1953)开始于栈的最低地址(译注:即栈底)以下的某个随机地址。注意是“通常”,因为它也可能在栈的上方 ,如果栈空间限制很大(或无限;译注:可用setrlimit修改),或者启用了兼容布局。这一点有多重要?——不重要,但可以让你了解到*自由地址范围*(free address ranges)。

在上图中,你可以看到3个不同的变量存放区:进程的数据段(静态存储,或堆内存分配),内存映射段,和栈。我们从这里开始。


# 理解栈上的内存分配

装备箱:
* alloca() - 在调用方的栈帧上分配内存
* getrlimit() - 获取/设置 resource limits
* sigaltstack() - 设置或获取信号栈上下文

栈相对比较容易理解,毕竟每个人都知道如何在栈上放一个变量,对吧 ?比如:

int stairway = 2;
int heaven[] = { 6, 5, 4 };


变量的有效性受到作用域的限制。在 C 里,作用域指的就是一对大括号 `{}`。因此每次遇到一个右大括号,对应的变量作用域就结束了。

然后是 alloca(),在当前 *栈帧*上动态分配内存。栈帧和内存帧(也叫做物理页)不太一样,它只是一组被压到栈上的数据(函数,参数,变量等)。由于我们在栈顶(译注:SP寄存器总是指向栈顶),我们可以使用剩下的栈空间,只要不超过栈大小限制。

这就是变长数组(variable-length,VLA)和 alloca 的原理,区别在于 ,VLA受限于作用域,alloca分配的内存的有效性可以持续到当前函数返回。这里没有语言律师业务(译注:没人管你,爱咋咋地),但如果你在循环里用alloca可能会踩坑,因为你没办法释放它分配的空间:

void laugh(void) {
    for (unsigned i = 0; i < megatron; ++i) {
        char *res = alloca(2);
        memcpy(res, "ha", 2);
        char vla[2] = {'h','a'}
    } /* vla dies, res lives */
} /* all allocas die */


如果要申请大量内存,VLA和alloca都不太好使,因为你几乎无法控制可用的栈空间,如果分配内存超过栈限制,就会遇到令人喜闻乐见的stack overflow。有两种办法可以绕过它,但都不太实用:

第一种是用  `sigaltstack()` 来捕获并处理 SIGSEGV 信号,但这只能让你捕获栈溢出(译注:程序仍然无法获得所需的内存)。

另一种是编译时指定“split-stacks”,这会将一个大的stack分割成用链表组织的“栈碎片”(stacklet)。就我所知,GCC 和 clang 编译器可以用 `-fsplit-stasck` 选项来启用这个特性。理论上这会改善内存消耗,并降低创建线程的开销,因为刚开始的时候栈可以很小,并按需扩展。但实际上可能会遇到兼容问题,因为这需要一个支持 split-stack 的链接器(例如 gold;译注:这是GNU的ELF链接器,不同于我们常用的链接器 ld,针对ELF链接性能更好)、而这是对库透明的,还可能有性能问题,例如 Go 的 hot-split 问题,在 Agis Anastasopoulos 的这篇文章[7] 中有详细解释。(译注:Go 1.3 之前用 split stack,即前述用链表串起来的栈,在某些情况可能因反复的栈扩展和收缩带来性能问题;1.3 开始改成使用连续的栈空间,空间不够时重新分配、拷贝内容、修改指向栈空间的指针,因此也要求编译器能准确分析指针逃逸的情况)


* * *
 

休息一下,第一篇就到这里。

下一篇接着翻译下一节 Understanding  heap allocation,感兴趣的记得关注,等不及的推荐阅读原文。

顺便再贴下之前推送的几篇文章,祝过个充实的五一假期~

* 《踩坑记:go服务内存暴涨》 
* 《TCP:学得越多越不懂》 
* 《UTF-8:一些好像没什么用的冷知识
* 《关于RSA的一些趣事
* 《程序员面试指北:面试官视角


* * *


# 参考链接:


[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/

[2] What every programmer should know about memory
http://www.akkadia.org/drepper/cpumemory.pdf

[3] stackoverflow.com - What Every Programmer Should Know About Memory?
https://stackoverflow.com/questions/8126311/what-every-programmer-should-know-about-memory

[4] Kernel - overcommit accounting
https://www.kernel.org/doc/Documentation/vm/overcommit-accounting

[5] Linux - Overcommit and OOM
https://www.win.tue.nl/~aeb/linux/lk/lk-9.html#ss9.6

[6] anatomy of a program in memory
http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/

[7] Contiguous stacks in Go
http://agis.io/2014/03/25/contiguous-stacks-in-go.html
Apr 27
这周换换口味,记录一下去年踩的一个大坑。 



大概是去年8月份,那会儿我们还在用着64GB的“小内存”机器。

由于升级一次版本需要较长的时间(1~2小时),因此我们每天只发一次车,由值班的同学负责,发布所有已merge的commit。 

当天负责值班的我正开着车,突然收到 Bytedance-System 的夺命连环call,打开Lark一看:

引用

[规则]:机器资源报警
[报警上下文]:
 host: 10.x.x.x
内存使用率: 0.944
[报警方式]:电话&Lark


打开ganglia一看,更令人害怕:
Apr 20

TCP#2: 西厢记和西厢计划 不指定

felix021 @ 2020-4-20 17:39 [IT » 网络] 评论(0) , 引用(0) , 阅读(875) | Via 本站原创
TCP#2: 西厢记和西厢计划

引用
自那日听琴之后,多日不见莺莺,张生害了相思病,趁红娘探病之机会,托她捎信给莺莺,莺莺回信约张生月下相会。夜晚,小姐莺莺在后花园弹琴,张生听到琴声,攀上墙头一看,是莺莺在弹琴。急欲与小姐相见,便翻墙而入,莺莺见他翻墙而入,反怪他行为下流,发誓不再见他,致使张生病情愈发严重。

《西厢记》



上篇《TCP:学得越多越不懂》发出来以后,有朋友很委婉地说:“如果能结合现实生产场景会有意义一点。”

经过深刻的反思,我决定虚心接受建议,写一点理论结合实践的内容。


# == 回忆杀 ==

曾经在猫扑和天涯冲浪的网虫应该都还记得,谷歌当时还是Goooooogle,是可以直接访问的。

但是如果想搜索一些奇怪的词汇(比如███),一点击"手气不错",浏览器马上就会显示无法访问,并且这个现象会持续几分钟。

点击在新窗口中浏览此图片

于是很多小伙伴就换到一个号称自己更懂中文的搜索引擎了。

(该爬虫当年有个广告拍得不错:https://v.qq.com/x/page/r0137s2op5j.html

作为一个曾被新自由主义(Neoliberalism)洗脑的年轻人,我在寻找“自由”的路上发现了墙的存在,也知道了这是方校长的杰作。

但是墙到底是个什么样的存在呢?



# == 防火墙 ==

我们的防火墙,其名源自《The Great Firewall of China: How to Build and Control an Alternative Version of the Internet》这本书。

虽然名字叫防火墙(Firewall,简称FW),但严格来说,(在早期)它其实是一个入侵检测系统(Instrusion Detection System,简称IDS)。

和FW不同的是,IDS是监听设备,不需要部署在链路中间,只要能把流量旁路引出供它分析即可。

点击在新窗口中浏览此图片

通过旁路分析,IDS可以在不影响现有流量的情况下部署(只要路由器/交换机上有镜像端口即可),在IDS出现异常时(例如在流量高峰IDS设备性能不足时 )也不会导致网络中断。

曾经有人发现,在流量特别大的时候,墙的检测功能有时会失效,因此推测其是旁路引流进行分析的(符合IDS的特征)。

既然是旁路的,就无法直接Drop数据包,为了达到阻断通信的目的,需要利用协议的特性来实现。


# == RST大法 ==

看了上篇《TCP:学得越多越不懂》的同学,对报文的控制位里的 RST 可能还有点印象,在遇到异常情况时,可用于通知对方重置连接(细节详见RFC 793):

引用
If the receiving TCP is in a non-synchronized state (i.e. SYN-SENT, SYN-RECEIVED), it returns to LISTEN on receiving an acceptable reset. If the TCP is in one of the synchronized states (ESTABLISHED, FIN-WAIT1, FIN-WAIT2, CLOSE-WAIT, CLOSING, LAST-ACK, TIME-WAIT), it aborts the connection and informs its user

https://tools.ietf.org/html/rfc793


有些同学可能像我一样懒得读英文原文,所以翻译一下:

* 如果连接状态处于“非连接完成”状态(例如SYN-SEND, SYN-RECEIVED),当收到reset时会将状态返回LISTEN;

* 如果TCP状态是 ESTABLISHED, FIN-WAIT-1, ..., LAST-ACK, TIME-WAIT 其中之一时,放弃连接并通知用户。

忘了上述状态含义的话,可以再回顾下这张状态流转图:

点击在新窗口中浏览此图片
(tcp连接状态图,截取自rfc 793)

这就是上篇里提到的“我们敬爱的防火墙很爱用它”的原因了:

当检测到“入侵行为”时(例如HTTP报文中出现了███)发送RST,按照RFC 793规范的TCP协议栈实现,收到RST后就应当放弃本次连接。

于是你就在浏览器上看到连接被重置(reset)了。



# == 反RST大法 ==

那么,如果我忽略RST包,不就可以不被墙欺骗吗?

实际上,用 iptables 来实现这一点很简单:

$ iptables -A INPUT -p tcp --tcp-flags RST RST -j DROP


很不幸,方校长的团队对此的解决方法也非常简单,只要向双方都发送RST包就可以了。

当然如果在服务器一端也忽略RST,就可以成功绕过墙的忽悠——据说剑桥大学有人实验验证过,确实可行。

可惜的是,用户通常没法控制服务器端忽略RST,因此这个方法的实用价值不高。

但是这个思路为西厢计划做好了铺垫。



# == 西厢计划 ==

我看到这个项目的名字的时候 ,真佩服作者的脑洞。

了解这个计划的原理之后,就更佩服作者的脑洞了。

前面说到,墙是在检测到某个关键词的时候才会发送RST包。

为了检测关键词,它需要工作在应用层(HTTP协议)。

而为了工作在应用层,它需要维护TCP连接的状态。

由于那时的设备性能比较弱(所以会出现高峰期检测失效的情况),为了提高吞吐量,方校长团队的方案是:实现一个简化的TCP栈。

RFC 793规范中定义了很多有效性检测,例如检测序列号是否有效来过滤old duplicates等,以保证通信的可靠性。

但这不是墙的需求,因此可以去掉很多规则,从而提高分析性能。

那么,如果我可以欺骗墙,这个连接已经被关闭,那么后续该连接的包就会被墙认为是网络中滞留的无效包,绕过关键词检测。

具体该怎么办呢?



# == 第一阶段 ==

上篇提到了一个细节:

引用
虽然ISN=4000,但是发送方发送的第一个包,SEQ是4001开始的,TCP协议规定 SYN 需要占一个序号(虽然SYN并不是实际传输的数据),所以前面示意图中ACK的seq是 x+1 。同样,FIN也会占用一个序号,这样可以保证FIN报文的重传和确认不会有歧义。

TCP:学得越多越不懂
https://mp.weixin.qq.com/s/xyPUEFUr_v9sSKKqlBkI7w



我们知道,在三次握手的最后一步,A本应发送一个ACK(seq=y+1)。

但如果这时候 A 发送了一个 FIN 呢?

B收到以后,由于此时连接尚未建立,会直接忽略这个包。

点击在新窗口中浏览此图片

而墙实现的TCP栈比较简陋,它认为A已经关闭了链接,因此A后续发送的包就不会再触发关键词检测。

但是注意,TCP是双向的,虽然A主动关闭连接,但是B仍然可能有数据要发送(划重点:面试题“为什么TCP断开连接需要4次”的答案),因此还需要欺骗墙说在B这侧也终止链接了。

这又该怎么办呢?



# == 第二阶段  ==

显然我们不能让服务器直接发一个FIN,否则这个连接就真完了。

幸运的是,RFC 793给了一个“梯子”:

引用
If the connection is in any non-synchronized state (LISTEN, SYN-SENT, SYN-RECEIVED), and the incoming segment acknowledges something not yet sent (the segment carries an unacceptable ACK), or ...(省略)..., a reset is sent.

Reset Generation, RFC 793 [Page 35]


翻译:如果连接处于“非连接完成”状态,收到一个无效的ACK,应当发出一个reset。

如果A在三次握手的最后一步,没有按规范要求发送ACK(seq=y+1),而是发送ACK(seq=y),那么B在收到以后就会按照协议的要求回复一个RST:

点击在新窗口中浏览此图片

这时我们可以在 A 上用“反RST大法”,忽略服务端返回的RST,这个连接就不受影响。

但是墙的TCP栈认为客户端会按照协议终止连接,于是就不再有必要检测服务端后续的报文了。


# == 大结局 ==

从此张生和崔莺莺过上了幸福的生活。

方校长的团队当然不会放任这种事情的发生,西厢计划没过多久就失效了。

随着技术的进步、性能的提升,现在墙似乎已经集成到了链路中、可以直接DROP数据包,不再需要RST大法了。

不过为了业务需要,企业可以向电信主管部门申请VPN用于正常的生产经营。

例如字节跳动,为了建设21世纪数字丝绸之路,通过技术出海,在40多个国家和地区排在应用商店总榜前列,包括韩国、印尼、马来西亚、俄罗斯、土耳其等“一带一路”沿线的主要国家。

如果你也想过上幸福的生活,不妨投个简历,一起为一带一路做贡献吧。

关于字节跳动面试的详情,可参考我之前写的《程序员面试指北:面试官视角》

https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw

# ~ 投递链接 ~

网盟广告(穿山甲)-后端开发(上海)
https://job.toutiao.com/s/sBAvKe

网盟广告(穿山甲)-后端开发(北京)
https://job.toutiao.com/s/sBMyxk

网盟广告(穿山甲)-广告策略研发(上海)
https://job.toutiao.com/s/sBDMAK

其他地区、其他职能线
https://job.toutiao.com/s/sB9Jqk


# 参考文章

[1] “西厢计划”原理小解
https://blog.youxu.info/2010/03/14/west-chamber/

[2] 从Linux协议栈代码和RFC看西厢计划原理
https://blog.csdn.net/dog250/article/details/7246895

[3] RFC 793 - TRANSMISSION CONTROL PROTOCOL
https://tools.ietf.org/html/rfc793
Apr 6

TCP:学得越多越不懂 不指定

felix021 @ 2020-4-6 13:25 [IT » 网络] 评论(0) , 引用(0) , 阅读(576) | Via 本站原创
周末小课堂又开张了,这次我们来聊一聊TCP协议。


== 握手 ==

多少有点令人意外的是,大多数程序员对TCP协议的印象仅限于在创建连接时的三次握手。

严格地说,“三次握手”其实是一个不太准确的翻译,英文原文是 "3-way handshake",意思是握手有三个步骤。

不过既然教科书都这么翻译,我就只能先忍了。

“三次握手”的步骤相信各位都非常熟悉了:

引用
A: 喂,听得到吗 (SYN)
B: 阔以,你呢 (SYN-ACK)
A: 我也阔以,开始唠吧 (ACK)


(咦,这不是远程面试的开场白吗)

那么问题来了:为什么不是2次握手或者4次握手呢?


== 3次 ==

针对“为什么不是4次”,知乎的段子手是这么回答的:

引用
A: 喂,听得到吗 (SYN)
B: 阔以,你呢 (SYN-ACK)
A: 我也阔以,你呢 (SYN-ACK)
B: ...我不想和傻*说话 (FIN)


由此可见知乎质量的下降。


实际上,上面省略了真正重要的信息,在握手过程中传输的,不是“你能不能听得到”,而是:


引用
A: 喂,我的数据从x开始编号 (SYN)
B: 知道了,我的从y开始编号 (SYN-ACK)
A: 行,咱俩开始唠吧 (ACK)


协商一个序号的过程需要一个来回(告知 + 确认),理论上需要2个来回(4次),互相确认了双方的初始序号(ISN,Initial Sequence Number),才能真正开始通信。

由于第二个来回的“告知”可以和前一次的“确认”合并在同一个报文里(具体怎么结合后面讲),因此最终只需要3次握手,就可以建立起一个tcp链接。

这也解释了为什么不能只有2次握手:因为只能协商一个序号。

不过话说回来,知乎段子手的回复也不是全在抖机灵:毕竟,发起方怎么才能确认接收方已经知道发起方知道接收方知道了呢?即使发起方再问一遍,接收方又怎么知道发起方知道了接收方知道了呢?

很遗憾,结论是:无论多少个来回都不能保证双方达成一致。

由于实践中丢包率通常不高,因此最合理的做法就是3次握手(2个来回),少了不够,多了白搭;同时配上相应的容错机制。

例如 SYN+ACK 包丢失,那么发起方在等待超时后重传SYN包即可。

引用
想想看,如果最后一个ACK丢了会怎样?


然后问题又来了:为什么需要协商初始序号,才能开始通信呢?

== 可靠 ==

我们都知道,tcp是一个“可靠”(Reliable)的协议。

这里“可靠”指的不是保证送达,毕竟网络链路中存在太多不可靠因素。

在 IETF 的 RFC 793(TCP协议)中,Reliability的具体定义是:TCP协议必须能够应对网络通信系统中损坏、丢失、重复或者乱序发送的数据。

引用
Reliability:

The TCP must recover from data that is damaged, lost, duplicated, or delivered out of order by the internet communication system.

https://tools.ietf.org/html/rfc793


为了保证这一点,tcp需要给每一个 [字节] 编号:双方通过三次握手,互相确定了对方的初始序号,后续 [每个包的序号 - 初始序号] 就能标识该包在字节流中所处的位置,这样就可以通过重传来保证数据的连续性。

举个例子:

* 发送方(ISN=4000)
    * 发出 4001、4002、4003、4004
    * (假设每个包只有1字节的数据)
* 接收方
    * 收到 4001、4002、4004
    * 4003因为某种原因没有抵达
    * 这时上层应用只能读到4001、4002中的信息

由于接收方没有收到4003,因此给发送方的ACK中,序号最大值是4003(表示收到了4003之前的数据)。

过了一段时间(Linux下默认是1s),发送方发现4003一直没被ACK,就会重传这个包。

当接收方最终收到 4003 以后,上层应用才可以读到4003和4004,从而保证其收到的消息都是可靠的。(以及,接收方需要给发送方ACK,序号是4005)

注意:虽然ISN=4000,但是发送方发送的第一个包,SEQ是4001开始的,TCP协议规定 SYN 需要占一个序号(虽然SYN并不是实际传输的数据),所以前面示意图中ACK的seq是 x+1 。同样,FIN也会占用一个序号,这样可以保证FIN报文的重传和确认不会有歧义。

但是,为什么序号不能从 0 开始呢?

== 可靠² ==

真实世界的复杂性总是让人头秃。

我们知道,操作系统使用五元组(协议=tcp,源IP,源端口,目的IP,目的端口)来标识一个连接,当一个包抵达时,会根据这个包的信息,将它分发到对应的连接去处理。

一般情况下,服务器的端口号通常是固定的(如http 80),而操作系统会为客户端随机分配一个最近没有被使用的端口号,因此包总能被分发到正确的连接里。

但在某些特殊的场景下(例如快速、连续地开启和关闭连接),客户端使用的端口号也可能和上一次一样(或者用了其他刚断开的连接的端口号)。

而TCP协议并不对此作出限制:

引用
The protocol places no restriction on a particular connection being used over and over again. ... New instances of a connection will be referred to as incarnations of the connection.


那么:

* 如果前一个连接的包,因为某种原因滞留在网络中,这会儿才送达,客户端可能无法区分(其sequence number在本连接中可能是有效的)。

* 恶意第三方伪造报文的难度很小。注意,在这个场景里,第三方并 [不需要] 处于通信双方的链路之间,只要他发出的报文可以抵达通信的一方即可。

因此我们需要精心挑选一个ISN,使得上述case发生的可能性尽可能低。

注意:不是在tcp协议的层面上100%避免,因为这会导致协议变得更复杂,实现上增加额外的开销,而在绝大多数情况下是不必要的。如果需要“100%可靠”,需要在应用层协议上增加额外的校验机制;或者使用类似IPSec这样的网络层协议来保证对包的有效识别。

那么,ISN应该如何挑选呢?

== ISN生成器 ==

说起来其实很简单:

TCP协议的要求是,实现一个大约每 4 微秒加 1 的 32bit 计数器(时钟),在每次创建一个新连接时,使用这个计数器的值作为ISN。

假设传输速度是 2 Mb/s,连接使用的sequence number大约需要 4.55 小时才会溢出并绕回(wrap-around)到ISN。即使提高到 100 Mb/s,也需要大约 5.4 分钟。

而一个包在网络中滞留的时间通常是有限的,这个时间我们称之为MSL(Maximum Segment Lifetime),工程实践中一般认为不会超过2分钟。

所以我们一般不用担心本次连接的早期segment(tcp协议称之为 old duplicates)导致的混淆。

注:在家用千兆以太网已经逐渐普及、服务器间开始使用万兆以太网卡的今天,wrap-around的时间已经降低到32.8s(千兆)、3.28s(万兆),这个假定已经不太站得住脚了,因此 rfc1185 针对这种高带宽环境提出了一种扩展方案,通过在报文中加上时间戳,从而可以识别出这些 old duplicates。

主要风险在于前面提到的场景:前一个连接可能传输了较多数据,因此其序列号可能大于当前连接的ISN;如果该连接的报文因为某种原因滞留、现在又突然冒出来,当前连接将无法分辨。

因此,TCP协议要求在断开连接时,TIME-WAIT 状态需要保留 2 MSL 的时间才能转成 CLOSED(如下图底部所示)。

点击在新窗口中浏览此图片

(tcp连接状态图,截取自rfc 793)

那么问题又来了:为什么只有 TIME-WAIT 需要等待 2MSL,而LAST-ACK不需要呢?

== 报文 ==

针对TCP协议可以提的问题太多了,写得有点累,所以这里不打算继续自问自答了。

但写了这么多,还没有看一下TCP报文是什么结构的,实在不应该,这里还是祭出 rfc 793 里的 ascii art(并顺便佩服rfc大佬的画图功力)

点击在新窗口中浏览此图片

简单介绍下:

* 一行是4个字节(32 bits),header一般共5行(options和padding是可选的)
* 第一行包含了源端口和目的端口
    * 每个端口16bits,所以端口最大是65535
    * 源IP和目的IP在IP报文头里
* 第二行是本次报文的Sequence Number
* 第三行是ACK序列号
* 第四行包含了较多信息:
    * 数据偏移量:4字节的倍数,最小是0101(5),表示数据从第20个字节开始(大部分情况)
    * 控制位(CTL):一共6个,其中的ACK、SYN、FIN就不介绍了
    * RST是Reset,遇到异常情况时通知对方重置连接(我们敬爱的防火墙很爱用它)
    * URG表示这个报文很重要,应该优先传送、接收方应该及时给上层应用。URG的数据不影响seq,实际很少被用到,感兴趣的话可以参考下RFC 854(Telnet协议)
    * PSH表示这个报文不应该被缓存、应当立即被发送出去。在交互式应用中比较常用,如ssh,用户每按下一个键都应该及时发出去。注意和Nagle算法可能会有一些冲突。
    * 窗口大小:表示这个包的发送方当前可以接受的数据量(字节数),从这个包里的ack序号开始算起。**用于控制滑动窗口大小的关键字段就是它了。**

举个例子,三次握手的第二步,SYN和ACK合并的报文就是这么生成的:

* Sequence Number填入从ISN生成器中获取的值
* Acknowledgement Number填入 [发送方的序号 + 1]
* 将控制位中的ACK位、SYN位都置1

写不动了,真是没完没了(相信看到这里的同学已经不多了),但是TCP协议中还有很多有意思的设计本文完全没有涉及,文末我给出一些推荐阅读的链接,供感兴趣的同学参考。

== 总结 ==

* TCP“三次握手”翻译不准确
* 握手的目的是双方协商初始序列号ISN
* 序列号是用于保证通信的可靠性
* 不使用 0 作为ISN可以避免一些坑
* TCP报文里包含了端口号、2个序列号、一些控制位、滑动窗口大小
* 我在字节跳动网盟广告业务线(穿山甲),由于业务持续高速发展,长期缺人。关于字节跳动面试的详情,可参考我之前写的
    * 《程序员面试指北:面试官视角》
    * https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw

~ 投递链接 ~

后端开发(上海) https://job.toutiao.com/s/sBAvKe

后端开发(北京) https://job.toutiao.com/s/sBMyxk

广告策略研发(上海) https://job.toutiao.com/s/sBDMAK

其他地区、职能线 https://job.toutiao.com/s/sB9Jqk


== 推荐阅读 ==

[1] RFC 793:TRANSMISSION CONTROL PROTOCOL

https://tools.ietf.org/html/rfc793


[2] Coolshell - TCP 的那些事儿 (上 & 下)

https://coolshell.cn/articles/11564.html

https://coolshell.cn/articles/11609.html


[3] 知乎 - TCP 为什么是三次握手,而不是两次或四?

https://www.zhihu.com/question/24853633
Mar 29
原发于我的公众号:felix021

在乔纳森·斯威夫特的著名讽刺小说《格列夫游记》中,小人国内部分裂成 Big-endian 和 Little-endian 两派,区别在于一派要求从鸡蛋的大头把鸡蛋打破,另一派要求从鸡蛋的小头把鸡蛋打破。

然后忘了这个故事,咱们开始吧。

== 坑 ==
Charles 同学这周又踩了个坑,数据插入 MySQL 时报错:

引用
1366 Incorrect string value: '\xF0\x90\x8D\x83...' for column 'content' at row 1


按惯例搜一下,据说是因为 mysql 用的 utf8 不支持 emoji,需要修改配置文件,将字符集改成 utf8mb4:

引用
[mysqld]
character-set-server = utf8mb4
stackoverflow.com/questions/10957238


但是 Charles 已经给 MySQL 加上了这个配置,仍然报错。

实际上,MySQL 还有另外一个配置,用于指定客户端和服务器之间连接时使用的字符集:

引用
[mysqld]
character-set-client-handshake = utf8mb4


当然,也可以在 MySQL Client 中指定,具体需要参考 client 的文档,或者简单粗暴地在连接成功以后执行(但不推荐):

引用
SET NAMES utf8mb4;


== utf8 和 utf8mb4 ==

那么,什么是 utf8mb4 ?和 utf8 有啥区别呢?

根据 MySQL 的 manual:

引用
The utfmb4 character set has these characteristics:
- Supports BMP and supplementary characters.
- Requires a maximum of four bytes per multibyte character.
https://dev.mysql.com/doc/refman/8.0/en/charset-unicode-utf8mb4.html

(文档中 utf8mb4 打错了,我是原样复制的)

翻译过来就是,utf8mb4 支持 BMP ( Unicode Basic Multilingual Plane )和补充字符,每个字符最多 4 字节(这里 “mb4” 大概就是 multi byte 4 的简写了)。

冷知识:Unicode 编码一共有 17 个 "Plane"( 0~16 ),其中 Plane 0 就是 BMP,包含绝大多数常用字符,比如希腊、希伯来、阿拉伯、CJK ( Chinese-Japanese-Korean )字符等。Plane 1~16 被称为 "supplementary planes",包含不常用的其他字符,例如 emoji 和某些特殊的 CJK 字符。所以目前 Unicode 字符的最大编码为 0x10FFFF 。

至于 utf8,MySQL 文档里也有说明:

引用
utf8 is an alias for the utf8mb3 character set.

Note
The utf8mb3 character set is deprecated and will be removed in a future MySQL release. Please use utf8mb4 instead
https://dev.mysql.com/doc/refman/8.0/en/charset-unicode-utf8.html

简单说就是挂羊头卖狗肉了,看到的是 utf8,实际用的是 utf8mb3

utf8mb3 的文档就不贴了(懒),和 ut8mb4 的区别就在于最多只支持 3 个字节,因此不支持 Unicode 的补充字符集。

也就是说,MySQL 里的 utf8,实际上是一个阉割版的 utf8 。

MySQL 从 5.5.3 才开始支持完整版的 utf8 ( utf8mb4 ),并且后续计划移除 utf8mb3,utf8 未来在 mysql 中也会变成 utf8mb4 的别名,所以以后默认都使用 utf8mb4 就对了。

话说回来,MySQL 为什么会有这种奇怪的设定呢?

其实最初是从性能上考虑的,这个精简版的 utf8 在运行的时候可以更快一点点。

要知道 MySQL 已经是一个 24 岁的老项目了,在 1995 年诞生时,Intel 才只推出了 Pentium Pro,对比现在的 CPU,性能可以说是非常差了。

冷知识:差到什么程度呢?举个例子,早期的 Windows Beta 版,桌面右下角时间是可以显示秒数的,但由于当时硬件的性能问题,微软在发布 Windows 95 之前就移除了该功能,直到 Windows 7 ( 2009 年)才允许通过修改注册表开启。

== 真正的 utf8 ==

那么真正的 utf8 长什么样呢?

在查文档之前,不妨先动手创建一个文档看一下

$ echo '0Aa 你好' > utf-8.txt

$ file utf-8.txt
utf-8.txt: UTF-8 Unicode text

$ xxd utf-8.txt #用 16 进制的方式查看
0000: 3041 61e4 bda0 e5a5 bd0a      0Aa.......

可以看到,开头"0Aa" 对应 3 个字节 0x30 、0x41 、0x61 (十进制 48 、65 、97,大写 A < 小写 a 就是这么来的)。

最后一个字符 0x0a 是 echo 默认输出的换行。

冷知识:可以加上 -n 参数让 echo 不输出换行符。换行符在不同 OS 下不同,在 Linux/Unix 下是 "\n" ( 0x0a ),在 Windows 下是 "\r\n"( 0x0d 0x0a ),在早期 Mac 下是 "\r" ( 0x0d ),从 Mac OS 10.0 ( 2001 )开始也和 Unix 一样用 "\n" 了。在 C/Python 等语言下,fopen/open 默认使用“文本模式”打开文件,读取时会统一转换成 "\n",写入时将"\n"转换为按 os 的默认值。还有一些其他场景可能需要注意,例如 http 协议中 header 使用 "\r\n" 换行。

中间的 "e4bda0e5a5bd" 这 6 个字节对应的就是 “你好” 了,每个字符 3 个字节。

那到底如何确定一个 utf8 字符是几个字节呢?

这里贴一个 wikipedia 的表格 Number

引用
字节数 | 比特数 | Unicode 区间 开始~结束 | 字节 1~4
1  7  U+0000  U+00007F  0xxxxxxx     
2  11  U+0080  U+0007FF  110xxxxx 10xxxxxx   
3  16  U+0800  U+00FFFF  1110xxxx 10xxxxxx 10xxxxxx
4  21  U+10000  U+10FFFF  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

简单解释一下:

1. 第一个字节中,开头 1 的数量表明了这个 utf8 字符包含几个字节
2. 0 开头,表示只需要 1 个字节,剩余 7 bit 可以表示 unicode 中的 0~127,正好和 ascii 编码兼容。
3. 110 开头,表示需要 2 个字节,包含 11 bit,可以表示大部分非 CJK 字符(希腊、阿拉伯等字符)
4. 1110 开头,表示需要 3 个字节,包含 16 bit,正好可以表示所有 BMP 的字符,比如 “你好”都在 这个 Plane 里面,所以一共需要 6 个字节。
5. 11110 开头,表示需要 4 个字节,包含 21 bit,最多可以包含 32 个 Plane,超过了当前 17 个 Plane 的
6. 后续字符都是 10 开头,不会和首字符混淆,因此在解析的时候很容易识别,就算遇到了错误的编码字符(例如按字节截断到字符中间),也可以简单跳过,定位下一个字符。

前面展示了 ASCII 字符和中文,咱们顺便再看看 emoji 的 utf-8 编码长什么样:

$ echo -n  > 1.txt
$ xxd 1.txt
0000: f09f 9880    ....


根据上面的表格,我们可以算出,这个 GRIN FACE (露齿笑)的 Unicode 码点是 0x1F600,在 Unicode 的 Plain 1 中,因此 utf-8 编码需要 4 个字节。

== 字符集和编码规范 ==

上文提到了 Unicode 和 utf-8 这两个名词,但是很多同学其实没搞明白他俩的区别是啥。

一般我们提到 Unicode 时指的是字符集( Character Set ),其中包含了一系列字符,并为每一个字符指定了码点( Code Point,即该字符的编号)。

Unicode 标准里包含了很多编码规范,utf-8 是其中一种,指定了一个 Unicode 字符的码点应该如何存储,例如 ASCII 用一个字节,超过一个字节的根据需要的 bit 数量,分别存储到多个字节中。

除了 utf-8 之外,Unicode 还有多种不同的编码规范,例如

1. ucs-2,就是简单地一一对应 BMP 的编码,每个字符使用 2 个字节,因此不支持补充字符。
2. ucs-4,用 4 个字节来存储 unicode 编码,因此支持 Unicode 中的所有 plain 。Unicode 后续的修订也会保证添加的码点都在 31bit 范围内。
3. utf-16,BMP 内的字符等于 ucs-2,其他 plane 用 4 个字节表示; windows 和 ecma 规范( javascript )使用 utf-16 作为其内部编码。
4. utf-32,ucs-4 的子集,一般可以认为就是 ucs-4 。

然鹅 utf-8 几乎统治了互联网,超过 93%的网页是用 UTF-8 编码的,以至于 IETF 要求所有网络协议都需要标明内容的编码,并且必须支持 UTF-8 。

至于原因么,还记得开头的那个故事吗? utf-8 避免了上述编码中的字节序( big endian 、little endian )的问题。

当然这只是一个原因,我认为更重要的是,utf-8 保持了对 ascii 的兼容,路径依赖的强大惯性,会导致上述 4 种编码在实际推广中带来很高的迁移成本(按理应该在这里讲讲马屁股宽度的故事,不过跑题太远了)。

utf-8 在保持后向兼容的前提下,能支持所有 Unicode 字符,相比 ucs4 还能节省大量存储空间、数据传输量,因此统治了互联网,也就在情理之中了。

除了 Unicode 之外,还有很多其他字符集,例如最经典的 ASCII,由于字符少,其编码规范也相当简单。

在中国,比较常见的字符集还有 GB2312 ( 1980 年)、GBK ( 1993 年)、GB18030 ( 2000 年),这些标准都规定了对应的编码规范,所以这些名字既可以表示字符集,也可以表示编码规范。

其中 GB2312 只包含 7445 个字符,其中汉字 6763 个(只包含常用汉字,很多生僻字都不支持),编码规范也兼容 ASCII 。GBK ( GB13000 )兼容 GB2312,添加了更多字符,GB18030 是进一步的补充。

冷知识:我们可以使用 iconv 命令行工具来修改文件的字符编码

$ iconv -f gb18030 -t utf-8 < gb18030.txt
0Aa 你好

也可以在 vim 中这干
:set fileencoding=gb18030


此外,使用 windows 的同学可能还见到过一个奇怪的代号 "cp936"(在上述 iconv 命令、vim 中都可以使用),这是微软对 GB2312 的实现,在 Win95 以后实际上也支持了大部分 GBK 字符。

== 总结 ==

1.  Unicode 是一个字符集,包含 17 个 Plane,每个 Plane 65536 个码点,Plane0 是 BMP,其他 Plane 是补充字符
2. UTF-8 是一种编码规范,用 1~4 个字节编码 Unicode 字符,兼容 ASCII,中文 3 字节,补充字符如 emoji 需要 4 字节)
3. MySQL 中的 utf8 是阉割版的、只支持 BMP 的编码,以后记得都使用 utf8mb4 ;除了 server 编码,记得也要修改连接的编码(客户端编码)。
4. 除了 utf-8 之外,还有好几个没什么卵用的字符集 /编码。
5. 我在网盟广告业务线(穿山甲),由于业务持续高速发展,长期缺人、不限 HC 。关于字节跳动面试的详情,可参考我之前写的《程序员面试指北:面试官视角》: https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw

~ 投递链接 ~

后端开发(上海) https://job.toutiao.com/s/sBAvKe

后端开发(北京) https://job.toutiao.com/s/sBMyxk

广告策略研发(上海) https://job.toutiao.com/s/sBDMAK

其他地区、职能线 https://job.toutiao.com/s/sB9Jq

----

再补充一个冷知识。

可能有些 PHP 程序员还踩过一个坑 :

用windows的 notepad 编辑utf-8编码的php文件并保存以后,代码执行不正常了。

这是因为 notepad 给文件开头打了个标记 (你可以用 xxd 或者 ultraedit 打开试试看)。

这个标记被称为 UTF-8 BOM,具体值为 0xEF 0xBB 0xBF,用来告诉文件的读取方,这个文件是使用 UTF-8 编码的。

比如说,你的csv是使用utf-8编码的,如果没有这个BOM,使用微软的Excel打开就会出现乱码。

至于PHP的问题,由于它在code tag(<?php)之前,PHP的解释器会把它当成 html 文件的一部分,可能就会导致 session 相关函数启动之前,就输出了http body。

最后,再学习一下移除 BOM 的方法吧:

vim:不要炸弹
引用
:set nobomb

sed:inplace
引用
$ sed -i '1s/^\xEF\xBB\xBF//' bom.txt
Mar 23

关于 RSA 的一些趣事 不指定

felix021 @ 2020-3-23 20:54 [IT » 其他] 评论(0) , 引用(0) , 阅读(783) | Via 本站原创
文章有点长(一共 2300 字), 但最后一个故事最有意思, 看不完的话可以直接拉到底

== 1 ==

从面试题说起好了。

在考察到网络这一块的时候,可能会问问 http 协议,聊安全相关问题时,就顺便聊聊 https 。

大多数候选人知道非对称加密,了解客户端会用 RSA 公钥进行加密。

那么,服务器在返回响应报文之前,会用什么来进行加密呢?

有些候选人回答:“用服务器私钥进行加密”。

内心呵呵一笑

接着问,那服务器返回的信息岂不是可以被中间人拦截并解密吗?

候选人一般就放弃挣扎,只能强颜欢笑了。

有进一步了解过 https 的同学,能够说出在 SSL/TLS 握手以后,会生成一个对称加密密钥。

那么,既然有非对称加密,为什么还需要使用对称加密呢?

有些候选人就回答不上来了,只能强颜欢笑+1 。

实际上这是因为非对称加密的性能通常比对称加密算法差几个数量级。

以 RSA 为例,在加解密的时候,需要对大整数(典型值是 2048bit,256 字节)做大量乘法、取模等运算;相比之下如 AES 这样的对称加密算法会简单很多,一些 XOR 、移位,以及在 4x4 的矩阵上做些变换,还可以通过查表来加速。

此外,由于 AES 的广泛应用,主流 CPU ( Intel, AMD, ARM )都有相应的扩展指令集,可以将性能提升一个数量级,实际每秒能处理的数据在数百 MB 这个量级上。

有些硬盘号称有全盘加密功能,实际上就是硬盘的主控芯片在写入前通过 AES 进行加密,在电脑启动时 BIOS 会要求输入密码。这样即使电脑丢了,或者硬盘被人拆下挂到其他机器上也不用担心数据泄露。

关于 RSA 算法的实现细节,推荐阮一峰写的《 RSA 算法原理》

https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

== 2 ==

另一个有趣的事情是 2017 年,当时在钱厂,对接某银行系统的时候,在通信协议的加密这块,对方给了一个 jar 包(不给源码),以及不知什么编码的公钥、私钥文件,既不是 PEM 也不是 X509,是个奇怪的二进制文件。

然鹅,钱厂用的是 PHP,这就有点尴尬了。

幸好这个 jar 包没有经过混淆,用安卓开发小伙伴提供的反编译工具,得到了源码,并经过一番努力重写成了 PHP 的源码。

然后发现那个公私钥是 java object 序列化后得到的字节码。

更有趣的还在后面。

为了方便测试,我们按银行给的 API 写了一套 mock 系统,这样就可以在不依赖银行在内部完成全流程自测,大幅提高了开发效率。

在部署 mock 系统的时候,没想太多,就用银行提供的这对公私钥,然后竟然调通了

也就是说,银行给的公钥和私钥文件竟然是一对,把他们的私钥直接给我们了……

我猜,应该是银行的安全审计部门在项目需求中要求用非对称加密,但是又没有对最终代码进行审查吧

顺便一提,正式上线时,对方给的 API url 是 https 的,但是 url 中的域名是 IP,钱厂在代码中只能把 CURLOPT_SSL_VERIFYHOST 设为 false 。

过了一段时间,他们决定用个正式的域名,才给安上了 https 证书。

又过了一段时间,他们的证书过期了。

并且在故障期间不允许我们忽略证书进行访问。

== 3 ==

故事 2 里提到,把那段 java 代码“经过一番努力”重写成了 PHP,其实中间还是遇到了个不大不小的麻烦。

Java 代码里用了一个叫 bouncycastle 的库来进行 RSA 的加解密,而我用 PHP 的 openssl_private_encrypt 加密的文本,并不能被他们提供的 java 代码正常解密。

经过多次尝试,我发现了一个现象:对同一个消息,java 代码加密生成的密文,每次都一样,而 PHP 生成的密文,则总是在变化。

作为一个信息安全专业的毕业生,我竟然不知道这是为什么,真是愧对国家愧对党,只好默默点开桌面上的小飞机,在一些不存在的网站上摸索。

根据这个现象,我在 stackoverflow 找到了 "data encrypted with openssl_public_encrypt is different every time?" 这个问题,答案中给了个线索:

The PKCS#1 encryption algorithm uses some random seed to make the cipher-text different every time. This protects the cipher-text against several attacks, like frequency analysis, ciphertext matching.

FROM stackoverflow.com/questions/36627518

经过进一步的搜索,终于找到了如何在 PHP 中解决这个问题。

具体解决办法后面说,这里先介绍一些背景知识。

RSA 加密的基本流程是:将一个和密钥长度相同的输入(明文),通过一系列运算(加密),得到一个和密钥长度相同的输出(密文)。

以 1024 bit 的 RSA 密钥为例,每次输入 128 字节,输出 128 字节。

对于超过 128 字节的情况,就需要将原始数据切成 128 字节的块,分别加密后再拼起来;解密时,按 128 字节拆开解密。

但是不足 128 字节的情况,比如像密码这种短数据,或者长数据也并不总是 128 的倍数,会留下小尾巴,这就有点尴尬。

因此我们还需要用某种方法,将不足 128 字节的数据拼( padding )到 128 字节,再进行加密;解密得到的数据,需要把 padding 的数据去掉,才能得原始数据。

真是让人头秃。

继续。

对于普通文本,一个简单的做法是用 ASCII 0 进行填充。

但这会带来 2 个问题:

如果原文中包含了 ASCII 0,就无法有效识别

对于相同的输入,总是能得到相同的密文。

问题 2 可能招致某些类型的攻击,例如前面引用中提到的 "frequency analysis",以一个简化的场景为例,假设每个单词是单独加密的,在英文中单词 a 出现的次数最多,通过统计密文出现的频率,可以破译对应的明文。

一个改进的方案是,使用一些随机数进行填充,这样可以保证相同明文每次加密得到不同的密文。

基于这个思路,RFC 2313 制定了 RSA 的加密标准 PKCS #1: RSA Encryption Version 1.5,通过在 128 字节中的前 11 个字节里加入一些随机数,保证每次加密得到的密文不同。

回到最初的问题,通过查看 PHP 的 openssl_public_encrypt 文档,可以发现它有一个 $padding 参数,默认值是 OPENSSL_PKCS1_PADDING 。

而银行给的 Java 代码是 Cipher.getInstance("RSA", new BouncyCastleProvider()); 按照官方文档的说明,这里的 RSA 等于 "RSA/NONE/NoPadding"。

最后,通过在 PHP 代码中给数据手动填充前导 ASCII 0,并指定 OPENSSL_NO_PADDING,终于和 Java 代码兼容了。

问题圆满解决。

等等……

银行用的是 NoPadding ?

== THE END ==

其实关于 RSA 还有一些其他有趣的事情,这次就先写到这里,下次(如果我还记得的话),可以聊聊 RSA 和币圈的一点小八卦。

按照前几篇的套路,文末还是要贴一下招聘广告:

我在网盟广告业务线(穿山甲),由于业务持续高速发展,长期缺人、不限 HC 。关于字节跳动面试的详情,可参考我之前写的《程序员面试指北:面试官视角》

https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw

~ 投递链接 ~

后端开发(上海) https://job.toutiao.com/s/sBAvKe

后端开发(北京) https://job.toutiao.com/s/sBMyxk

广告策略研发(上海) https://job.toutiao.com/s/sBDMAK

其他地区、职能线 https://job.toutiao.com/s/sB9Jqk

Mar 22

PYTHON RSA加解密 不指定

felix021 @ 2020-3-22 00:31 [IT » 其他] 评论(0) , 引用(0) , 阅读(850) | Via 本站原创
和某厂通信需要按其要求用rsa加密某段数据,该厂给了个Example.java,和一个X509 Certificate。

之前是把java编译好,然后在python里用system来调用它,有点丑。

最近需要复用这段代码,希望代码干净点,所以在Python里重新实现一遍。

# 1. 将 x509cer 转成  PEM 格式
import java.io.*;
import java.util.Base64;
import java.security.PublicKey;
import java.security.cert.CertificateFactory;
import java.security.cert.X509Certificate;

public class Test2
{
    public static PublicKey getPublicKeyByX509Cer(String cerFilePath) throws Exception
    {
        InputStream x509Is = new FileInputStream(cerFilePath);
        CertificateFactory certificatefactory = CertificateFactory.getInstance("X.509");
        X509Certificate cert = (X509Certificate)certificatefactory.generateCertificate(x509Is);
        x509Is.close();
        return cert.getPublicKey();
    }

    public static void main(String[] args) throws Exception {
        PublicKey pubKey = getPublicKeyByX509Cer("public.cer");
        System.out.println(Base64.getEncoder().encodeToString(pubKey.getEncoded()));
    }
}


输出PEM编码的公钥,类似:MIGfMA0GCSqGSIb3DQ...(中间省略)...rAvxiOfQIDAQAB


# 2. 在Python中加密

#!/usr/bin/python
#coding:utf-8
import base64
import binascii
import Crypto
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

PUBLIC_KEY = "MIGfMA0GCSqGSIb3DQ...(中间省略)...rAvxiOfQIDAQAB"

#返回base64编码后的密文
def RSAEncrypt(message, pubkey):
    binary = base64.b64decode(pubkey)
    key = RSA.importKey(binary)
    #PKCS#1建议的padding需要占用11个字节
    length = (key.size() + 1) / 8 - 11

    cipher = PKCS1_v1_5.new(key)
    res = []
    for i in range(0, len(message), length):
        res.append(cipher.encrypt(message[i:i+length]))
    result = ''.join(res)
    return binascii.hexlify(result)

print RSAEncrypt("123456", PUBLIC_KEY)


由于该厂在Java代码中使用 "RSA/NONE/PKCS1Padding",和PKCS1_v1_5的默认padding一致,因此不需要特殊处理。

注:
如果希望使用 NoPadding,看起来Python的Crypto没有直接提供支持,可能需要用PKCS1_OAEP并自己填充ASCII 0(但不确定,好像OAEP也包含了某种padding,encrypt的文档里说"长度需要 - 2 - 2倍hashcode长度"),几年前用PHP的时候踩过坑,详见
  https://www.felix021.com/blog/read.php?2169
  RSA: Java bouncy castle 与 PHP openssl_public_encrypt 兼容的那点事儿

# 3. 解密

反向处理就好,先base64 decode,分段解密再拼起来

PRIVATE_KEY = "MIICXQIBAAKBgQ....."

# 输入是base64编码的密文
def RSADecrypt(message, prikey):
    binary = base64.b64decode(prikey)
    key = RSA.importKey(binary)
    length = (key.size() + 1) / 8
    cipher = PKCS1_v1_5.new(key)
    message = binascii.unhexlify(message)
    res = []
    for i in range(0, len(message), length):
        res.append(cipher.decrypt(message[i:i+length], 'sentinel: random message'))
    result = ''.join(res)
    return result


注:decrypt方法的文档里说,"sentinel" 应当是一个无意义的字符串,并且尽量应当和典型的明文长度相似(这里偷懒了)。因为PKCS1_v1_5没有完善的完整性校验,某个构造的输入可能可以被正确解码,虽然看起来是一串没有意义的随机文字。加上sentinel以后,当解密出错的时候,会返回指定的 sentinel 继续后续处理流程,从而可以躲避选择密文攻击的检测。

关于这个选择密文攻击的细节可参考这篇文章:SSL.TLS协议安全系列:SSL的Padding Oracle攻击


# 4. 其他

可以用这个命令来生成RSA的公私钥对
引用
$ openssl genrsa -out test.pem 1024
$ openssl rsa -in test.pem -pubout -out test_public.pem


RSA.importKey(key) 方法的 key 也可以直接使用 PEM 文件的内容,也可以用 base64 decode 以后的 binary data。
分页: 3/99 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]