文章还未完善 mallocNote:malloc is a glic function, not syscall overview mem structure physical page allocationbuddyLinux内核中引入了伙伴系统算法(Buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。如图： 假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。 从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。 slabTODO r ...

a1d442672885495a31a2ae2fad6179bb1c04d23b1577c24fbfe4ad3c7a23c2f33ca6de73b9b89594ad949f853bae76847fa7392e8586916645e0dd78434165fbb2501b1f850a245c55323b6329e36e00ac51a4850adef1ae2e5344a4ac7d91c512195f32c58b4b4d4b4851294cdef086ab478640e72732ccea2a4792ad25d68ed261e621250857974923bfb83873fc32474132e3d03fe654957646b1345edf9165bc2df653783ee4bddffb4c8c068943ac08d4510ab808bb28f6098a8c05b3d1325e3015ee03dab6abb1df1b327aebc6154f5dd7a0e2f2199ccaa06c8640d3ce6c51837dcfd52303a80336064eb14fef373a6ca87d141efc2 ...

本文将探讨当存储介质是外部存储，比如磁盘、闪存时，有哪些主流的存储数据结构(传统的二叉树将不再适用)。 本文以key-value数据库为例讲述不同数据结构的差异。其KV存储包含以下5个基本操作 get(K) 查找key K对应的value put(K,V) 插入键值对（K，V） update(K,V) 查找key K对应的value更新为V delete(K) 删除key K对应的条目 scan(K1,K2) 得到从K1到K2的所有key和value B 系列B ( B- ) TreeB树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。 应用的数据库 MongoDB 结构图示以一颗阶数为4的为例，图中数字对应key，data对应value 定义 每个结点最多有m-1个key。 根结点最少可以只有1个key。 非根结点至少有$⌈m/2⌉-1$个key。（最差节点利用率为50%） 每个结点中的关键字都按照顺序排列，每个关键字的左子树中的所有关键字都小 ...

The followings are decribed based on IA-64 Linux system. Machine LevelRegs in IA-64 16 integer register (8-byte long) %rax, %rcx, %rdx, %rbx, %rsi, %rdi, %rsp, %rbp %r8, %r9, %r10, %r11, %r12, %13, %r14, %r15 Note: %rsp only points to stack top 16 floating point register (32-byte long) InstructionNo instruction can load two address together push S (add the value in register S into the stack) R[%rsp] ← R[%rsp] - 8 M[R[%rsp]] ← S pop D (pop the value from the stack top) D ← M[R[%rsp]] R ...

为什么要KMP本文以一个非常常见的字符串匹配问题讲述字符串匹配的几种理解角度。即在字符串S(长为N)中找到模式串T(长为M)出现的第一个位置。 首先字符串匹配查找的方法大家都能想到一个暴力解法,复杂度是O(NM)，显然是太慢了的。希望能找到一个O(M+N)的方法，那就是KMP算法 本质是利用子串内部的信息加快检索。 比如当如下不匹配发生时： 暴力枚举法是让T串移动1格，重新枚举 而KMP则是移动4格，因为ABCDAB后缀和前缀有两个相同 next数组法跳转数组定义KMP算法需要首先设置一个跳转数组next，其next[i]代表以[0, j-1]区间后缀与前缀最大相同长度。其本质是 next整体[0, j-1]是后缀与前缀最大相同长度整体向右平移一位，然后首位补-1 i 0 1 2 3 4 5 6 模式串 A B C D A B D next -1 0 0 0 0 1 2 根据跳转数组的KMPKMP算法是一种母串指针不倒退，而去调整模式串位置的检索方法。 1234567891011121314151617181920212223242526/* 在 S 中找到 ...

这篇文章有待改进，内容还有比较多的内容需要补全。想要了解的建议直接移步reference。The blog is to be continued. layer UDP 保证正确性(cksum) 不保证顺序 不保证送达 资源占用少 包头短 无状态（无连接） TCP Logic transfer control retransmission fast retransmission due to 3 Acknowledgement Duplicates： timeout time adjustment: when accept each packet problem 为什么建立要3次，断开要4次？ 建立：确保client端开启。 关闭: 当收到对方的FIN报文时，仅仅表示对方不再发送数据了但是还能接收数据，己方也未必全部数据都发送给对方了，所以己方可以立即close，也可以发送一些数据给对方后，再发送FIN报文给对方来表示同意现在关闭连接，因此，己方ACK和FIN一般都会分开发送。 为什么TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOS ...

a1d442672885495a31a2ae2fad6179bb288cea116d9f743927f59cabddf46f5273a8f2079bec792c7212721455e9d01abeab67f96fa082f772ddb3bb6989e8cc66945d5fe6b4a1434d4e5934496536df9373ec34e40f78e8f5f33ff28ed2556a388d48d40bf86e683d3bd2b540543f8b31957c302769adf33a369fd51d346da89775a71470ffa0c4d8510b3e71a124274e04461e852e3a003b89adb51362adc519fb2fb1d61ce3b857c7a9243ef480695235c43f86b2fe742139c6ebcb25881cb1fe0f52ac3019a30a6ffb774dc28bf1f946d1ed0c1bcf0007557aad12f6b7603f0d7bae5f6ed69521643aaec5f324e34b6abfac7e7072dd2 ...

Concurrency and ParallelismParallelism ∈ ConcurrencyConcurrency: two or more actions(workflows) exists at the same timeParallelism: two or more actions(workflows) is running at the same time Why Multithreading? to achive Concurrency maximize (hardware)resource usage Process vs Thread vs Coroutine Process: is a program is a unit for resource distribution process has at least one thread, each process has isolated resources, such as address space. heavyWeight, it takes more to create a process ...

Simple ConceptsReference & Pointer Reference <=> alias, the variable stands for a address Pointer, the variable save the address Overload & Override Overload: just same name with same return type. Override：can only be done in derived class What will run before calling main static or global constructor Array & Pointer1234char a[] = “hello”;char *b = "world";sizeof(a) = length * sizeof(char) = 6sizeof(b) = sizeof(char*) = 4(32 bit os)/8(64 bit os) Function Poin ...

线段树适用场景固定范围内区间统计，统计只能是可以合并的操作如：最值、求和 树状数组在认识线段树之前，有个熟悉的结构，每一层分布跟归并排序过程类似，就是树状数组，如下： T的根结点代表整个数组所在的区间对应的信息，及arr[0:N]（不含N)所对应的信息。 T的每一个叶结点存储对应于输入数组的每一个单个元素构成的区间arr[i]所对应的信息，此处0≤i<N。 T的每一个中间结点存储对应于输入数组某一区间arr[i:j]对应的信息，此处0≤i<j<N。 其本质思想是分而治之。 代码详解以如下问题为例来描述样例代码： 我们有一个长度为n的int数组，即A[0..n-1] 需要支持以下几种操作： 找到区间[l..r]内的元素之和 对区间[l..r]内的所有元素都更新为一个新的值x，即a[l..r]=x 理论也可以用链表实现，但是实际效率比如直接用数组实现慢许多。 构建 O(N)可能有些人会当成N次更新，但是实际可以通过从树状数组尾部遍历来优化 递归版123456789101112131415161718void build(int node, in ...