Inbox

“SkipList, 跳表, 跳跃表” SkipList SkipList(跳表)这种数据结构是由 William Pugh 于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList 的设计初衷是作为替换 平衡树 的一种选择。 我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。 但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，SkipList 需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。 SkipList还有一个优势就是实现简单，SkipList的实现只花了2个小时，而红黑树，我可能得2天。 时隔将近三十多年，SkipList 这种数据结构仍在许多途径有用武之地，比如Redis, 还有Google的著名项目 Bigtable, leveldb 原理及实现 其实跳表就是在普通单向链表的基础上增加了一些索引，而且这些索引是分层的，从而可以快速地查的到数据。 比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤: 从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1 然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0 在结点17上，level==0索引到19,查找完毕。 如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败 https://zhuanlan.zhihu.com/p/33674267 skiplist, 红黑树 skiplist 的复杂度和红黑树一样，而且实现起来更简单。 在并发环境下红黑树在插入和删除时需要 rebalance，性能不如跳表。 http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

“Cuckoo filter, 布谷过滤器” 过滤器系列 (二) —— Cuckoo filter 这一篇讲的是布谷过滤器(cuckoo fliter)，这个名字来源于更早发表的布谷散列(cuckoo hash)，尽管我也不知道为什么当初要给这种散列表起个鸟名=_= 由于布谷过滤器本身的思想就源自于布谷散列，那么我们就从布谷散列开始说它的设计思想。产生布谷散列表的一个重要背景是人们对于球盒问题的分析: 给定N个球，随机的放在N个盒子里，在装球最多的盒子里，球的个数的期望是多少？答案是Θ(logN/loglogN)，这个问题其实就是散列表装填因子为1时的情况分析。后来有一天，人们发现: 每次放球的时候，如果随机选择两个盒子，将球放到当时较空的那个盒子里，那么这个期望就变成了Θ(loglogN)，这个界小于之前的界，这给了布谷散列表作者启发。 一个布谷散列表通常有两张 (一般来说) 表，分别有一个对应的Hash函数，当有新的项插入的时候，它会计算出这个项在两张表中对应的两个位置，这个项一定会被存在这两个位置之一，而具体是哪一个却不确定。 下图是一个布谷散列表的初始化示意图: image 现在我们假设有一些项要存入散列表，其每个项都有其对应的两个位置，先插入第一项A image 由于插入A的时候其两个候选位置 (0,2) 都没有占用，所以选择第一张表或者是第二张表都可以，我们在这里默认先选择第一张表，然后插入第二项B image 我们看到原来的A的位置被B占用，而A被“踢”到它的备选位置表二的2号位置上了，这就是当发生位置冲突时，布谷散列表的处理逻辑，后来的数据项将会把之前占用的项踢到另一个位置上。我们接下来插入第三项C image 没有冲突，顺利搞定，接着插入D image D成功的把C踢走了，其实看到这里读者应该在猜想，会不会有一种情况，即被踢走的数据的另一个备选位置也被占用了，这样怎么办？答案是继续踢，一个踢一个，直到大家都找到自己合适的归宿为止。那么如果发现出现了循环怎么办？答案是GG，这代表布谷散列表走到了极限 image 插入E image 这里就发生了多次替换的情况，F代替了E，E代替了A，A代替了B，B找到了空余的位子 读者可以考虑一下，如果这个时候要想插入一个“G”，其备选位置是1,2，这样的话会出现什么情况？ 好了，布谷散列表大概介绍完了，现在该布谷过滤器了。布谷过滤器的主要也是通过布谷散列来实现的，其主要变化是: 1.我们不将原来的数据完整的存进来，作为过滤器，当然要省点空间，选用的办法设计一个指纹，将比较大的原数据变成了一个个指纹串，这样就大大节省了空间。 2.由于第一点所说，存储的不是原数据，那么在替换位置的时候，我们需要再次计算原来的数据的备选位置，这样一来布谷散列表的方法就失效了。在这里，作者设计了一个方法，他将两个Hash函数变成了一个Hash函数，第一张表的备选位置是Hash(x),第二张表的备选位置是Hash(x)⊕hash(fingerprint(x))，即第一张表的位置与存储的指纹的Hash值做异或运算。这样做的优点就是不用再另外存储元素的备选位置，在替换时，可以直接用异或来计算出其另一个备选位置。 (读者可以想想如何通过表二的位置计算出元素在表一中的位置) 3.插入时，优先选择空位置，而不是尽可能的踢走其他元素。 插入伪代码如下: Copy Algorithm 1: Insert(x) f = fingerprint(x) i1 = hash(x) i2 = i1 xor hash(f) if bucket[i1] or bucket[i2] has an empty entry then //只要有空位就先插入空位里 add f to that bucket return Done i = randomly pick i1 or i2 for n=0;n<MaxNumKicks;++n randomly select an entry e from bucket[i]; swap f and the fingerprint stored in entry e; i = i xor hash(f) if bucket[i] has an empty entry then add f to bucket[i] return Done return Failure // 已经出现循环情况了 查找伪代码如下: ...

“gcm cbc” 主要区别 AES-GCM可以并行加密解密，AES-CBC的模式决定了它只能串行地进行加密。因为加密是耗时较久的步骤，且加密的方式是相同的，所以并行地实现AES-GCM算法的时候，其效率是高于AES-CBC的； AES-GCM提供了GMAC信息校验码，用以校验密文的完整性。AES-CBC没有，无法有效地校验密文的完整性； AES-GCM是流加密的模式，不需要对明文进行填充。AES-CBC是块加密的模式，需要对明文进行填充。(AES-GCM中进行AES加密的是counter，AES-CBC中进行AES加密的是明文块)； 由于AES-CBC中必须要用到padding，导致最后一个明文块与其他密文块不同，因此可能会受到padding Oracle attacks，从而可以直接通过初始向量IV和密码，即可得到明文。 https://blog.csdn.net/weixin_39680609/article/details/111159600

“MESI” CPU 在执行指令的时候需要从 memory 中获取指令和需要的数据，但是 CPU 的速度要比 memory 快很多，这就导致了 CPU 大部分时间都不是在做运算上而是用在了和 memory 进行数据的 I/O 过程中，这样性能是很低的。这就导致了 CPU cache 的产生，CPU 将数据从 memory 读取到 cache 中，在 cache 中对数据进行读写的速度是很快的，这样就提高了性能。CPU 执行运算时不可能需要某一个数据就去读取一次，这样就增加了 I/O 的频率，导致性能低下。所以会一次性读取一块内存的数据存放到 cache 中， 这个块称为 “cache line” ， cache line 的大小是固定的， 通常是 2 的 N 次方，在 16 ~ 256 byte 不等。当某个数据首次被 CPU 访问时， cache 中不存在，这称为 “cache miss” (或 “startup” 或 “warmup” cache miss)。这意味着 CPU 必须要去 memory 中读取该数据，这时候 CPU 必须等待 (stalled)。当 cache 装满后，后续的 cache miss 需要置换 cache 中现有的数据，这样的 cache miss 被称为 “capacity miss” 。如果随后又访问了被替换的 cache line ，这时的 cache miss 被称为 “associativity miss” 。 ...

“Store Buffer” 就像spinlock的进化史，软件工程师会对自己的代码做足够的优化以提高性能。同样，硬件工程也不甘示弱，尽最大的努力设计硬件以获取更好的性能。我们引入高速缓存的目的就是为了降低内存访问的延迟，谁知硬件工程师依然不满足于高速缓存带来的延迟，当然软件工程师或许也不满足。为了进一步加快内存访问速度，硬件引入了新的缓存 - store buffer。随着store buffer的引入，彻底刷新了软件工程师对代码执行流的认知。store buffer又是怎么刷新我们的认知呢？ 文章测试代码已经开源，可以点击这里查看。 store buffer是什么 在之前的文章介绍中，我们了解到每个CPU都会有自己私有L1 Cache。从我了解的资料来说，L1 Cache命中的情况下，访问数据一般需要2个指令周期。而且当CPU遭遇写数据cache未命中时，内存访问延迟增加很多。硬件工程师为了追求极致的性能，在CPU和L1 Cache之间又加入一级缓存，我们称之为store buffer。store buffer和L1 Cache还有点区别，store buffer只缓存CPU的写操作。store buffer访问一般只需要1个指令周期，这在一定程度上降低了内存写延迟。不管cache是否命中，CPU都是将数据写入store buffer。store buffer负责后续以FIFO次序写入L1 Cache。store buffer大小一般只有几十个字节。大小和L1 Cache相比，确实是小巫见大巫了。 store buffer对程序的影响 我们现在知道，当存在store buffer的情况下。针对写操作，CPU直接把数据扔给store buffer。后续store buffer负责以FIFO次序写回L1 Cache。这会对我们的程序产生什么影响呢？我们来看个例子。 static int x = 0, y = 0; static int r1, r2; static void int thread_cpu0(void) { x = 1; /* 1) / r1 = y; / 2) */ } static void int thread_cpu1(void) { y = 1; /* 3) / r2 = x; / 4) */ } ...

“文件锁” 文件锁也被称为记录锁，文件锁如果深讲的话，内容不少 (比如文件锁最起码分为了建议锁和强制性锁) 这里不准备深纠，深纠没有任何意义 主要是为了对比学习各种的加锁机制，比如进程有进程信号量加锁机制，线程有线程互斥锁、线程信号量等 加锁机制，学习文件锁有助于我们对比理解，对于我们后续理解驱动课程中的内核锁，c++、java等库所提供的 资源保护的锁机制，都是很有意义的。 当然还有另一个目的，那就是练习fcntl函数的使用，因为文件锁也需要用到fcntl函数。 由于文件锁的知识点是刚才所讲的这样一种存在，所以对于文件锁内容的学习，理解>实际使用。 4.1 文件锁的作用 顾名思义，就是用来保护文件数据的。 当多个进程共享读写同一个文件时，为了不让进程们各自读写数据时相互干扰，我们可以使用进程信号量来 互斥实现，除了可以使用进程信号量以外，还可以使用我们这里的的“文件锁”来实现，而且功能更丰富， 使用起来相对还更容易些。 4.2 多进程读写文件 file_lock.png 多进程共享读写同一个文件时，如果数据很重要的话，为了防止数据相互修改，应该满足如下读写条件: (1) 写与写应该互斥 当某个进程正在写文件，而且在数据没有写完时，其它进程不能写，否者会相互打乱对方写的数据 (2) 读与写也应该是互斥的 分两种情况: 某个进程正在写数据，而且在数据没有写完时，其它进程不能读数据因为别人在没有写完之前，读到的数据是不完整的，所以读和写时互斥的 某个进程正在读数据，在数据没有读完之前，其它进程不能写数据因为可能会扰乱别人读到的数据 (3) 读与读共享 某个进程在读数时，就算数据没有读完，其它进程也可以共享读数据，并不需要互斥等别人读完后才能读。 因为读文件是不会修改文件的内容，所以不用担心数据相互干扰的问题 总结起来就是，多进程读写文件时，如果你想进行资源保护的话，完美的资源保护应该满足如下这样的。 写与写之间互斥 读与写之间互斥 读与读之间共享 如何实现以上读写要求？ 如果使用信号量来实现保护的话，只能是一律互斥，包括读与读都是互斥的，不能够向上面描述的，能互斥又能共享，但是文件锁可以做到 4.3 文件锁 4.3.1 文件锁的读锁与写锁 对文件加锁时可以加两种锁，分别是“读文件锁”和“写文件锁”，我们这里简称为读锁和写锁。 读锁、写锁之间关系 (1) 读锁和读锁共享: 可以重复加读锁，别人加了读锁在没有解锁之前，我依然可以加读锁，这就是共享。 (2) 读锁与写锁互斥: 别人加了读锁没有解锁前，加写锁会失败，反过来也是如此。 加锁失败后两种处理方式， 阻塞，直到别人解锁然后加锁成功为止 出错返回，不阻塞 (3) 写锁与写锁互斥: 别人加了写锁在没有解锁前，不能加写锁，加写锁会失败。 加锁失败后两种处理方式， 阻塞，直到别人解锁然后加锁成功为止 出错返回，不阻塞 常用的是阻塞加锁，至于如何实现阻塞和非阻塞，后面详细讲 4.3.2 使用文件锁对文件进行保护 读文件时加读锁，写文件时就加写锁，然后就可以很容易的实现符合如下要求的资源保护。 写与写之间互斥 读与写之间互斥 读与读之间共享 4.4 文件锁的加锁方式 (1) 对整个文件内容加锁 对整个文件加锁是最常用的文件锁的加锁方式。 当你对整个文件加锁时，如果文件的长度因为写入新数据或者截短而发生了变化，加锁内容的长度会 自动变化，保证对内容变化着的整个文件加锁。 (2) 对文件某部分内容加锁 不过一般来说是，对多少内容加锁，就对多少内容解锁，如果你是对整个文件加锁，就将整个文件解锁。 但是实际上加锁和实际解锁的长度可以不相同，比如我对1000个字节的内容加了锁，但是可以只对其中的 100字节解锁，不过这种情况用的少，知道有这么回事即可 4.5 文件锁的实现 实现文件锁时，我们还是需要使用fcntl函数 4.5.1 再看看fcntl的函数原型 ...

“taskset” 一、在Linux上修改进程的“CPU亲和力” 在Linux上，可以通过 taskset 命令进行修改。以Ubuntu为例，运行如下命令可以安装taskset工具。 apt-get install schedutils 对运行中的进程，文档上说可以用下面的命令，把CPU#1 #2 #3分配给PID为2345的进程: taskset -cp 1,2,3 2345 但我尝试没奏效，于是我关掉了MySQL，并用taskset将它启动: taskset -c 1,2,3 /etc/init.d/MySQL start 对于其他进程，也可如此处理 (nginx除外，详见下文) 。之后用top查看CPU的使用情况，原来空闲的#1 #2 #3，已经在辛勤工作了。 二、配置nginx绑定CPU 刚才说nginx除外，是因为nginx提供了更精确的控制。 在conf/nginx.conf中，有如下一行: worker_processes 1; 这是用来配置nginx启动几个工作进程的，默认为1。而nginx还支持一个名为worker_cpu_affinity的配置项，也就是说，nginx可以为每个工作进程绑定CPU。我做了如下配置: worker_processes 3; worker_cpu_affinity 0010 0100 1000; 这里0010 0100 1000是掩码，分别代表第2、3、4颗cpu核心。 重启nginx后，3个工作进程就可以各自用各自的CPU了。 三、刨根问底 如果自己写代码，要把进程绑定到CPU，该怎么做？可以用sched_setaffinity函数。在Linux上，这会触发一次系统调用。 如果父进程设置了affinity，之后其创建的子进程是否会有同样的属性？我发现子进程确实继承了父进程的affinity属性。 四、Windows？ 在Windows上修改“CPU亲和力”，可以通过任务管理器搞定。 个人感觉，Windows系统中翻译的“处理器关系”比“CPU亲和力”容易理解点儿 —————– 进行了这样的修改后，即使系统负载达到3以上，不带缓存打开blogkid.net首页 (有40多次查询) 依然顺畅；以前一旦负载超过了1.5，响应就很慢了。效果很明显。 linux taskset命令详解 SYNOPSIS taskset [options] [mask | list ] [pid | command [arg]…] OPTIONS -p, –pid operate on an existing PID and not launch a new task -c, –cpu-list specifiy a numerical list of processors instead of a bitmask. The list may contain multiple items, separated by comma, and ranges. For example, 0,5,7,9-11. -h, –help display usage information and exit -V, –version output version information and exit ...

“HyperLogLog” HyperLogLog HyperLogLog，下面简称为HLL，它是 LogLog 算法的升级版，作用是能够提供不精确的去重计数。 127.0.0.1:6379> PFADD language "PHP" "Python" "Perl" "Ruby" (integer) 1 127.0.0.1:6379> PFCOUNT language (integer) 4 127.0.0.1:6379> PFADD language "PHP" # Redis 已经存在，不必对估计数量进行更新 (integer) 0 127.0.0.1:6379> PFCOUNT language # 元素估计数量没有变化 (integer) 4 127.0.0.1:6379> PFADD language "JAVA" # 添加一个不存在的元素 (integer) 1 127.0.0.1:6379> PFCOUNT language # 估计数量增一 5 https://juejin.cn/post/6844903785744056333 https://www.cnblogs.com/wmyskxz/p/12396393.html http://content.research.neustar.biz/blog/hll.html 存在以下的特点: 代码实现较难。 能够使用极少的内存来统计巨量的数据，在 Redis 中实现的 HyperLogLog，只需要12K内存就能统计2^64个数据。 计数存在一定的误差，误差率整体较低。标准误差为 0.81% 。 误差可以被设置辅助计算因子进行降低。 稍微对编程中的基础数据类型内存占用有了解的同学，应该会对其只需要12K内存就能统计2^64个数据而感到惊讶。为什么这样说呢，下面我们举下例子: 取 Java 语言来说，一般long占用8字节，而一字节有8位，即: 1 byte = 8 bit，即long数据类型最大可以表示的数是: 2^63-1。对应上面的2^64个数，假设此时有2^63-1这么多个数，从 0 ~ 2^63-1，按照long以及1k = 1024字节的规则来计算内存总数，就是: ((2^63-1) * 8/1024)K，这是很庞大的一个数，存储空间远远超过12K。而 HyperLogLog 却可以用 12K 就能统计完。 伯努利试验 在认识为什么HyperLogLog能够使用极少的内存来统计巨量的数据之前，要先认识下伯努利试验。 ...

“redis bitmap” BitMap https://www.cnblogs.com/54chensongxia/p/13794391.html BitMap# BitMap 原本的含义是用一个比特位来映射某个元素的状态。由于一个比特位只能表示 0 和 1 两种状态，所以 BitMap 能映射的状态有限，但是使用比特位的优势是能大量的节省内存空间。 在 Redis 中，可以把 Bitmaps 想象成一个以比特位为单位的数组，数组的每个单元只能存储0和1，数组的下标在 Bitmaps 中叫做偏移量。 需要注意的是: BitMap 在 Redis 中并不是一个新的数据类型，其底层是 Redis 实现。 BitMap 相关命令# 设置值，其中value只能是 0 和 1 setbit key offset value 获取值 getbit key offset 获取指定范围内值为 1 的个数 start 和 end 以字节为单位 bitcount key start end BitMap间的运算 operations 位移操作符，枚举值 AND 与运算 & OR 或运算 | XOR 异或 ^ NOT 取反 ~ result 计算的结果，会存储在该key中 key1 … keyn 参与运算的key，可以有多个，空格分割，not运算只能一个key 当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0。返回值是保存到 destkey 的字符串的长度 (以字节byte为单位) ，和输入 key 中最长的字符串长度相等。 bitop [operations] [result] [key1] [keyn…] ...

“bloom filter, 布隆过滤器” Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one. 大意是不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。 在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、 大集合中重复元素的判断和缓存穿透等问题。 布隆过滤器 (Bloom Filter) 是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定地误识别率和删除困难。 什么是布隆过滤器 本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构 (probabilistic data structure) ，特点是高效地插入和查询， 可以用来告诉你 “某样东西一定不存在或者可能存在”。 ...

“c, file, open, fopen” "" fopen 是 C 标准库函数,用于处理作为流对象的文件的打开。与本质上是系统调用的 open 函数不同,fopen 将 FILE 指针对象与给定的文件相关联。它需要两个参数；第一个参数代表要打开的文件的路径名,第二个参数是打开文件的模式。 open 函数本质上是一个低级的系统服务,即使使用 fopen 也会被调用。需要注意的是,系统调用通常是用 C 库的封装函数提供给最终用户的,但其特点和性能用例与 C stio 库中的函数不同。如: open 在创建新文件时,第二个参数取类型为 int,第三个参数可选,指定文件模式位。 https://www.delftstack.com/zh/howto/c/open-vs-fopen-in-c/

pve + openwrt 局域网网段: 192.168.50.0/24 pve 宿主机 ip: 192.168.50.6 软路由 ip: 192.168.50.1 download openwrt image 下载 “ext4-combined-efi” curl -O https://downloads.openwrt.org/releases/19.07.7/targets/x86/64/openwrt-19.07.7-x86-64-combined-ext4.img.gz curl -O https://downloads.openwrt.org/releases/21.02.3/targets/x86/64/openwrt-21.02.3-x86-64-generic-ext4-combined-efi.img.gz curl -O https://downloads.openwrt.org/releases/24.10.0/targets/x86/64/openwrt-24.10.0-x86-64-generic-ext4-combined-efi.img.gz upload image to pve # 解压出 .img 文件 gunzip openwrt-19.07.7-x86-64-combined-ext4.img.gz 把 openwrt-24.10.0-x86-64-generic-ext4-combined-efi.img 上传到 pve local pve>local(xxx)>ISO Images>upload 创建虚拟机 点击 “创建虚拟机(Create VM)”, 填写虚拟机名称 (例如 openwrt-24-10), 选"高级"，勾选"开机自启动" (软路由必须开机启动) ，点击"下一步"。 OS: CD/DVD 选择 “Do not use any media”(不要去选择刚才上传的镜像)，点击"下一步"。 System: 系统选项卡全部默认，点击"下一步"。 Disk: 硬盘不用改，之后会删除，会用上一步下载的 .img 镜像创建虚拟磁盘。 CPU 核心数量按需添加，一般双核足够了 内存 256MB 以上都是够的，系统有富余就多加一点，一般不用超过 2GB，点击"下一步" Network: PVE 虚拟机可选网卡模型 (虚拟网卡) 有 Intel E1000、VirtIO (半虚拟化) 、Realtek RTL8139和VMware vmxnet3四种。建议选用默认的 VirtIO (半虚拟化) ，其性能和效率最高。 分离不用的硬盘: 选择刚刚创建的虚拟机 > 硬件(Hardware) > Hard Disk(scsi0) > 点击"分离(Detach)", 然后它会变成 unused disk。 删除不用的硬盘和光驱: 选中"Unused disk 0"，点击"删除"；再用同样的方法删除不用的光驱。 添加启动盘 上传 Openwrt 镜像: 选择"pve"节点 > local存储空间 > 内容 > 点击上传 > 选择"openwrt-24.10.0-x86-64-generic-ext4-combined-efi.img"镜像 > 点击"上传"。 ...

“用户栈和内核栈” 进程是程序的一次执行过程。用剧本和演出来类比，程序相当于剧本，而进程则相当于剧本的一次演出，舞台、灯光则相当于进程的运行环境。 进程的堆栈 每个进程都有自己的堆栈，内核在创建一个新的进程时，在创建进程控制块 task_struct 的同时，也为进程创建自己堆栈。一个进程有2个堆栈，用户堆栈和内核堆栈；用户堆栈的空间指向用户地址空间，内核堆栈的空间指向内核地址空间。当进程在用户态运行时，CPU 堆栈指针寄存器指向用户堆栈地址，使用用户堆栈，当进程运行在内核态时，CPU 堆栈指针寄存器指向的是内核栈空间地址，使用的是内核栈； 进程用户栈和内核栈之间的切换 当进程由于中断或系统调用从用户态转换到内核态时，进程所使用的栈也要从用户栈切换到内核栈。系统调用实质就是通过指令产生中断，称为软中断。进程因为中断 (软中断或硬件产生中断) ，使得CPU切换到特权工作模式，此时进程陷入内核态，进程进入内核态后，首先把用户态的堆栈地址保存在内核堆栈中，然后设置堆栈指针寄存器的地址为内核栈地址，这样就完成了用户栈向内核栈的切换。 当进程从内核态切换到用户态时，最后把保存在内核栈中的用户栈地址恢复到CPU栈指针寄存器即可，这样就完成了内核栈向用户栈的切换。 这里要理解一下内核堆栈。前面我们讲到，进程从用户态进入内核态时，需要在内核栈中保存用户栈的地址。那么进入内核态时，从哪里获得内核栈的栈指针呢？ 要解决这个问题，先要理解从用户态刚切换到内核态以后，进程的内核栈总是空的。这点很好理解，当进程在用户空间运行时，使用的是用户栈；当进程在内核态运行时，内核栈中保存进程在内核态运行的相关信息，但是当进程完成了内核态的运行，重新回到用户态时，此时内核栈中保存的信息全部恢复，也就是说，进程在内核态中的代码执行完成回到用户态时，内核栈是空的。 理解了从用户态刚切换到内核态以后，进程的内核栈总是空的，那刚才这个问题就很好理解了，因为内核栈是空的，那当进程从用户态切换到内核态后，把内核栈的栈顶地址设置给CPU的栈指针寄存器就可以了。 X86 Linux内核栈定义如下 (可能现在的版本有所改变，但不妨碍我们对内核栈的理解) : 在/include/linux/sched.h中定义了如下一个联合结构: union task_union { struct task_struct task; unsigned long stack[2408]; }; 从这个结构可以看出，内核栈占8kb的内存区。实际上，进程的task_struct结构所占的内存是由内核动态分配的，更确切地说，内核根本不给task_struct分配内存，而仅仅给内核栈分配8K的内存，并把其中的一部分给task_struct使用。 这样内核栈的起始地址就是union task_union变量的地址+8K 字节的长度。例如: 我们动态分配一个union task_union类型的变量如下: unsigned char *gtaskkernelstack gtaskkernelstack = kmalloc(sizeof(union task_union)); 那么该进程每次进入内核态时，内核栈的起始地址均为: (unsigned char *) gtaskkernelstack + 8096 进程上下文 进程切换现场称为进程上下文(context)，包含了一个进程所具有的全部信息，一般包括: 进程控制块 (Process Control Block，PCB) 、有关程序段和相应的数据集。 进程控制块PCB (任务控制块) 进程控制块是进程在内存中的静态存在方式，Linux内核中用task_struct表示一个进程 (相当于进程的人事档案) 。进程的静态描述必须保证一个进程在获得CPU并重新进入运行态时，能够精确的接着上次运行的位置继续进行，相关的程序段，数据以及CPU现场信息必须保存。处理机 现场信息主要包括处理机内部寄存器和堆栈等基本数据。 进程控制块一般可以分为进程描述信息、进程控制信息，进程相关的资源信息和CPU现场保护机构。 进程的切换 当一个进程的时间片到时，进程需要让出CPU给其他进程运行，内核需要进行进程切换。 Linux 的进程切换是通过调用函数进程切换函数schedule来实现的。进程切换主要分为2个步骤: ...

redis basic commands redis-cli -h 127.0.0.1 -p 6379 # -a 使用认证密码登录 redis-cli -h 127.0.0.1 -p 6379 -a password0 # -n 指定 db redis-cli -h 127.0.0.1 -p 6379 -a password0 -n 10 # OBJECT ENCODING 命令可以查看一个数据库键的值对象的编码 OBJECT ENCODING key0 # 分析 redis key 大小 debug object key0 # Value at:0x7f6bffc22a00 refcount:1 encoding:raw serializedlength:7164 lru:12841785 lru_seconds_idle:95 # 查看各个库的 key 数量 info keyspace # 不进入交互模式, 直接执行命令 redis-cli -h 127.0.0.1 -p 6379 hget key0 field0 延迟时间 redis-cli --latency -h 192.168.50.100 -p 6379 sort https://segmentfault.com/a/1190000002806846 ...

challenge response, 挑战应答 挑战应答方式”：challenge-response，是零知识证明的方式。 Challenge/Response认证的过程如下: 客户端向服务器发出认证请求； 认证服务器从用户数据库中查询用户是否是合法的用户，若不是，则不做进一步的处理； 认证服务器内部产生一个随机数，作为 “提问” / Challenge，发送给用户； 客户将口令和随机数合并，使用单向 Hash 函数 ( 例如MD5算法 ) 生成一个字节串作为Response； 认证服务器将 Response 与自己的计算结果比较，如两者相同，则通过一次认证，反之认证失败； 认证服务器通知客户端认证成功或失败。 以后的认证由客户不定时发起，过程中没有了客户认证请求一步。两次认证的时间间隔不能太短，否则就给网络、客户和认证服务器带来太大的开销；但也不能太长，否则不能保证用户不被他人盗用IP地址，一般定为1-2分钟。 密钥的分配和管理 密钥的分配由维护模块负责，当用户进行注册时，自行设定自己的口令。用户的密钥由口令生成。 一个口令必须经过两次口令检查。第一次由注册程序检查，强制口令必须有足够的长度。口令被加密后送入数据库，这个口令标记为“未检查的”。第二次，由离线的口令检查工具进行检查，将弱口令进行标记，当下次用户认证时，认证服务器将强制用户修改口令。 密钥的在线修改由认证服务器完成，其过程与认证过程基本类似。 Challenge/Response认证的安全性分析: 下面就常见的对认证服务器攻击方法来分析其安全性。 网络侦听 ( sniffer ) 认证过程中，密钥和口令不是明文不在网络上传输，所以sniffer很难从听到的报文中得到用户的口令。在密钥在线修改过程中，新口令使用旧密钥加密传送，sniffer 攻击仍然无效。 replay attack, 重放攻击 每次 challenge 不同，所以 replay attack 无效。 password guessing 在知道了认证算法后，侦听者可以对用户的口令进行猜测。这种攻击方法直接有效，特别是当用户的口令有缺陷时。解决方法是使用合适的口令。 跟踪地址攻击 攻击者在看到用户认证后，设法将自己的机器地址改为用户的IP地址，从而冒充用户。但由于攻击者无法完成后续的认证，在1-2分钟内，攻击失效。 https://blog.csdn.net/zy531/article/details/6205306 https://en.wikipedia.org/wiki/Challenge%E2%80%93response_authentication

“fork” 一个进程,包括代码、数据和分配给进程的资源。fork() 函数通过系统调用创建一个与原来进程几乎完全相同的进程,也就是两个进程可以做完全相同的事,但如果初始参数或者传入的变量不同,两个进程也可以做不同的事。 一个进程调用fork() 函数后,系统先给新的进程分配资源,例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的新进程中,只有少数值与原来的进程的值不同。相当于克隆了一个自己。 我们来看一个例子: /* * fork_test.c * version 1 * Created on: 2010-5-29 * Author: wangth */ #include <unistd.h> #include <stdio.h> int main () { pid_t fpid; //fpid表示fork函数返回的值 int count=0; fpid=fork(); if (fpid < 0) printf("error in fork!"); else if (fpid == 0) { printf("i am the child process, my process id is %d/n",getpid()); printf("我是爹的儿子/n");//对某些人来说中文看着更直白。 count++; } else { printf("i am the parent process, my process id is %d/n",getpid()); printf("我是孩子他爹/n"); count++; } printf("统计结果是: %d/n",count); return 0; } 运行结果是: i am the child process, my process id is 5574 我是爹的儿子 统计结果是: 1 i am the parent process, my process id is 5573 我是孩子他爹 统计结果是: 1 在语句fpid=fork()之前,只有一个进程在执行这段代码,但在这条语句之后,就变成两个进程在执行了,这两个进程的几乎完全相同,将要执行的下一条语句都是if(fpid<0)…… 为什么两个进程的fpid不同呢,这与fork函数的特性有关。fork调用的一个奇妙之处就是它仅仅被调用一次,却能够返回两次,它可能有三种不同的返回值: 1) 在父进程中,fork返回新创建子进程的进程ID； 2) 在子进程中,fork返回0； 3) 如果出现错误,fork返回一个负值； ...

mmap mmap 函数是 unix/linux 下的系统调用 mmap() 函数用来将文件或者设备映射到内存中。 mmap 的特点是按需调页。最开始只申请 vma(Virtual Memory Area)，并不调真正的页。当对某些页进行引用的时候，会引起一个缺页中断，再将页面调入到内存当中，这样避免了对内存的浪费。 内存映射, 是将用户空间的一段内存区域映射到内核空间, 映射成功后,用户对这段内存区域的修改可以直接反映到内核空间,同样,内核空间对这段区域的修改也直接反映用户空间。 那么对于 内核空间 <—-> 用户空间 两者之间需要大量数据传输等操作的话效率是非常高的。 mmap 是一种内存映射文件的方法, 即将一个文件或者其它对象映射到进程的地址空间, 实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。实现这样的映射关系后,进程就可以采用指针的方式读写操作这一段内存,而系统会自动回写脏页面到对应的文件磁盘上, 即完成了对文件的操作而不必再调用 read, write 等系统调用。相反,内核空间对这段区域的修改也直接反映用户空间,从而可以实现不同进程间的文件共享 mmap 优点 对文件的读取操作跨过了页缓存, 减少了数据的拷贝次数, 用内存读写取代I/O读写, 提高了文件读取效率。 实现了用户空间和内核空间的高效交互方式。两空间的各自修改操作可以直接反映在映射的区域内, 从而被对方空间及时捕捉。 提供进程间共享内存及相互通信的方式。不管是父子进程还是无亲缘关系的进程,都可以将自身用户空间映射到同一个文件或匿名映射到同一片区域。从而通过各自对映射区域的改动, 达到进程间通信和进程间共享的目的。 同时, 如果进程A和进程B都映射了区域C, 当A第一次读取C 时通过缺页从磁盘复制文件页到内存中；但当B 再读C 的相同页面时, 虽然也会产生缺页异常,但是不再需要从磁盘中复制文件过来, 而可直接使用已经保存在内存中的文件数据。 可用于实现高效的大规模数据传输。 内存空间不足,是制约大数据操作的一个方面,解决方案往往是借助硬盘空间协助操作,补充内存的不足。但是进一步会造成大量的文件I/O操作,极大影响效率。这个问题可以通过mmap映射很好的解决。换句话说,但凡是需要用磁盘空间代替内存的时候, mmap 都可以发挥其功效。 操作文件就像操作内存一样，适合于对较大文件的读写。 用户也可创建匿名内存映射, 该映射没有对应的文件, 可用于存放程序数据。在 Linux中,若通过 malloc()请求一大块内存,C 运行库将创建一个匿名内存映射,而不使用堆内存。“大块” 意味着比阈值 MMAP_THRESHOLD还大,缺省为128KB,可通过 mallopt()调整。 mmap将一个文件或者其它对象映射进内存。文件被映射到多个页上,如果文件的大小不是所有页的大小之和,最后一个页不被使用的空间将会清零。munmap执行相反的操作,删除特定地址区域的对象映射。 prot: 期望的内存保护标志,不能与文件的打开模式冲突。是以下的某个值,可以通过or运算合理地组合在一起 PROT_EXEC //页内容可以被执行 PROT_READ //页内容可以被读取 PROT_WRITE //页可以被写入 PROT_NONE //页不可访问 ...

accord, grant https://www.tjxz.cc/11067 give、accord、award、confer、grant、endow、present与bestow这组动词均含有“给予、赠给”之意。 give 最普通用词，泛指将自己的东西给予他人，所给予的东西，物质或非物质的均可。 She gave us a set of saucepans as a wedding present. 她送我的结婚礼物是一套深平底锅。 Can you give me a date for another appointment? 我能再和您约个时间吗？ They never gave me a chance/choice. 他们从来就没给过我机会／选择余地。 Has the director given you permission to do that? 主任允许你那样做了吗？ accord 侧重所给予的是应得的或是恰当的，或是因某种原因而适于接受的。 The massed crowds of supporters accorded him a hero’s welcome. 蜂拥云集的支持者们给予他英雄般的欢迎。 Certainly in our society teachers don’t enjoy the respect that is accorded to doctors and lawyers. 的确，在我们这个社会中，老师没有得到像医生和律师所受到的那种尊敬。 ...

“线程模型” 多线程模型: 一对一模型、多对一模型和多对多模型 迄今为止，我们只是泛泛地讨论了线程。不过，有两种不同方法来提供线程支持: 用户层的用户线程或内核层的内核线程。 用户线程位于内核之上，它的管理无需内核支持；而内核线程由操作系统来直接支持与管理。几乎所有的现代操作系统，包括 Windows、Linux、Mac OS X 和 Solaris，都支持内核线程。 最终，用户线程和内核线程之间必然存在某种关系。本节研究三种常用的建立这种关系的方法: 多对一模型、一对一模型和多对多模型。 多对一模型 多对一模型 多对一模型 (图 1) 映射多个用户级线程到一个内核线程。 线程管理是由用户空间的线程库来完成的，因此效率更高。不过，如果一个线程执行阻塞系统调用，那么整个进程将会阻塞。再者，因为任一时间只有一个线程可以访问内核，所以多个线程不能并行运行在多处理核系统上。 Green threads 线程库为 Solaris 所采用，也为早期版本的 Java 所采纳，它就使用了多对一模型。然而，现在几乎没有系统继续使用这个模型，因为它无法利用多个处理核。 一对一模型 一对一模型 图 2 一对一模型 一对一模型 (图 2) 映射每个用户线程到一个内核线程。 该模型在一个线程执行阻塞系统调用时，能够允许另一个线程继续执行，所以它提供了比多对一模型更好的并发功能；它也允许多个线程并行运行在多处理器系统上。 这种模型的唯一缺点是，创建一个用户线程就要创建一个相应的内核线程。由于创建内核线程的开销会影响应用程序的性能，所以这种模型的大多数实现限制了系统支持的线程数量。Linux，还有 Windows 操作系统的家族，都实现了一对一模型。 多对多模型 多对多模型 图 3 多对多模型 多对多模型 (图 3) 多路复用多个用户级线程到同样数量或更少数量的内核线程。内核线程的数量可能与特定应用程序或特定机器有关 (应用程序在多处理器上比在单处理器上可能分配到更多数量的线程) 。 现在我们考虑一下这些设计对并发性的影响。虽然多对一模型允许开发人员创建任意多的用户线程，但是由于内核只能一次调度一个线程，所以并未增加并发性。虽然一对一模型提供了更大的并发性，但是开发人员应小心，不要在应用程序内创建太多线程 (有时系统可能会限制创建线程的数量) 。 多对多模型没有这两个缺点: 开发人员可以创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行。而且，当一个线程执行阻塞系统调用时，内核可以调度另一个线程来执行。 多对多模型的一种变种仍然多路复用多个用户级线程到同样数量或更少数量的内核线程，但也允许绑定某个用户线程到一个内核线程。这个变种，有时称为双层模型 (图 4) 。 双层模型 图 4 双层模型 Solaris 操作系统在第 9 版以前支持这种双层模型；但从第 9 版后，就使用了一对一模型。

“炼妖壶” https://zhuanlan.zhihu.com/p/50584002