Kernel

如果稍微了解过 Linux 内核的内存管理，那么对内存分区的概念一定不陌生，Linux内核把物理内存分成了3个区， 0 – 16M 为ZONE_DMA区, 16M – 896M 为ZONE_NORMAL区， 高于896M 为ZONE_HIGHMEM区 我没有去考证过为什么要取896这个数字，但是可以肯定的是这样的划分在当时看来是合理的，然而计算机发展今非昔比，现在4G的物理内存已经成为PC的标配了，CPU也进入了64位时代，很多事情都发生着改变。 在CPU还是32位的时代，CPU最大的物理寻址范围是0-4G， 在这里为了方便讨论，我们不考虑物理地址扩展（PAE）。进程的虚拟地址空间也是 4G，Linux内核把 0-3G虚拟地址空间作为用户空间，3G-4G虚拟地址空间作为内核空间。 目前几乎所有介绍Linux内存管理的书籍还是停留在32位寻址的时代，所以大家对下面这张图一定很熟悉！ （这个图画得非常详细，本篇文章我们关注的重点是 3个分区 以及最右边的线性地址空间，也就是虚拟地址空间之间的关系，另外，应该是ZONE_DMA， ZONE_NORMAL, ZONE_HIGHMEM, 图中把ZONE 写成了ZUNE） 然而，现在是64位的时代了, 64位CPU的寻址空间是多大呢？ 16EB， 1EB = 1024 TB = 1024 * 1024 GB，我想很多人这辈子还没见过大于1TB的内存吧，事实上也是这样，几乎没有哪个服务器能有16EB的内存，实现64位长的地址只会增加系统的复杂度和地址转换的成本，所以目前的x86_64架构CPU都遵循AMD的 Canonical Form, 即只有虚拟地址的最低48位才会在地址转换时被使用, 且任何虚拟地址的48位至63位必须与47位一致, 也就是说总的虚拟地址空间为256TB。 那么在64位架构下，如何分配虚拟地址空间的呢？ 0000000000000000 – 00007fffffffffff(128TB)为用户空间, ffff800000000000 – ffffffffffffffff(128TB)为内核空间。 而且内核空间中有很多空洞, 越过第一个空洞后, ffff880000000000 – ffffc7ffffffffff(64TB) 才是直接映射物理内存的区域, 也就是说默认的PAGE_OFFSET为 ffff880000000000. 请关注下图的最左边，这就是目前64位的虚拟地址布局。 在本文的一开头提到的物理内存分区 ZONE_DMA， ZONE_NORMAL， ZONE_HIGHMEM 就是与内核虚拟地址的直接映射有关的，如果读者不了解 内核直接映射物理地址这个概念的话，建议你去google一下，这个很简单的一一映射的概念。 既然现在内核直接映射的物理内存区域有64TB， 而且一般情况下，极少有计算机的内存能达到64TB（别说64TB了，1TB内存的也很少很少），所以整个内核虚拟地址空间都能够一一映射到计算机的物理内存上，因此，不再需要 ZONE_HIGHMEM这个分区了，现在对物理内存的划分，只有ZONE_DMA， ZONE_NORMAL。 ...

时间倒回到2011年5月的一天，大学的最后一门课《计算机信息安全技术》，讲到《缓冲区溢出》这一章，并且给出了一段示例代码来演示缓冲区溢出，回到宿舍后出于好奇我运行了一下这段代码，发现结果并不是书上所说的那样，当时在人人网也发过一篇吐槽的日志，但是一直拖到现在都没有仔细的去研究过，正好现在十一放假没事，就花点时间搞搞啦。 书第136页-137页。代码如下，出于简单考虑（其实书上的C++代码格式也是错的），我除去了头文件和cout函数，这样就跟纯C语言代码是一样了。 void function(int a) { char buffer[5]; char *ret; ret = buffer + 12; *ret += 8; } int main() { int x; x = 10; function(7); x = 1; return 0; } 书上说最后x的值是10，不是1，而我的结果恰恰相反。 接着用gcc产生汇编代码，在这里用 gcc -O0 -S命令告诉编译器不采用任何优化措施，产生最原始的汇编代码，这样有利于我们分析，即使是采用-O1级优化的时候，汇编代码已经很难读了，大家可以试一试。 function: pushl %ebp movl %esp, %ebp subl $16, %esp leal -9(%ebp), %eax addl $12, %eax movl %eax, -4(%ebp) movl -4(%ebp), %eax movzbl (%eax), %eax addl $8, %eax movl %eax, %edx movl -4(%ebp), %eax movb %dl, (%eax) leave main: pushl %ebp movl %esp, %ebp subl $20, %esp movl $10, -4(%ebp) movl $7, (%esp) call function movl $1, -4(%ebp) leave ret 书上详细的解释了为什么结果是10，下面我来逐条分析。首先画一张内存图，同样处于简洁考虑，只画function函数附近的内存分布，不影响分析。 ...

Table {:toc} 问题 有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。 比如，31,-41,59,26是它的一个连续的子串，他们的和为75。但是75并不是最大值，有一个子串 59,26,-53,58,97它们的和187才是最大的。 解答 《Programming Pearls》第77页开始一共给出了4种解法，前两种非常简单，是大多数人思考几分钟就能想出的方法，但是复杂度却很高，分别为O(n^3)和O(n^2)。后两种解法则非常巧妙，更神奇的是第四种方法居然只有线性复杂度O(n) 解法1、解法2略。 解法 3：分治法 复杂度为O(nlogn)。 分治法在结构上是递归的，在保证不改变原问题的条件下，将问题的规模减小，生成多个子问题，并多次递归调用自身来解决子问题，之后再将子问题的求解结果合并成原问题的解。 对于case1，我们只要比较 ma 和 mb 的大小就可以得出原数组的最大子串的和了。 对于case2, 只要把ma和mb相加即可。以上只是将问题一次分解的过程，我们还需要将问题再分解直到不能在分解或是能直接得出结果为止。 什么时候能直接得出结果？当子数组只有一个元素的时候，此时ma就是它本身（为负数时我们让它为0）。 因此，原数组的最大和 = 2个子数组中最大和的较大者，或者，包括中间分界线的一段连续区域的和。 即，maxsum(orignial)=max(mc，maxsum(a)，maxsum(b)) 递归结束的条件是，子数组只有一个元素，如果是正返回它本身，为负返回0 代码如下。 int maxSubArray(std::vector<int>& nums) { return maxsum(nums, 0, nums.size()-1); } int maxsum(std::vector<int> &nums, int left, int right) { if (left > right) { return 0; } if (left == right) { return nums[left]; } int mid = (left + right)/2; int left_max = INT_MIN, right_max = INT_MIN; int tmp_max = 0; for (int i = mid; i >= left; i--) { tmp_max += nums[i]; left_max = std::max(left_max, tmp_max); } tmp_max = 0; for (int i = mid+1; i <= right; i++) { tmp_max += nums[i]; right_max = std::max(right_max, tmp_max); } return std::max(left_max+right_max, std::max(maxsum(nums, left, mid), maxsum(nums, mid+1, right))); } 解法4：扫描法 一次扫描数组即可得出答案，复杂度O(n)。这种方法用文字描述不容易说清楚，下面用每一步运算的图示来表达。伪代码如下： ...