数组和链表的区别 - 简书
数组和链表的区别
昨天弟弟问我数组和链表有啥区别，我脱口而出，数组查询快增删慢，链表查询慢增删快。弟: 为啥？我：呃...忘了...于是重新回顾了下，总结如下：
1.数组查询快：数组要求是一块连续的内存空间来存储，这就要求在物理上这一片空间是连续的，每个元素都有指定的索引index指向内存地址，因此查询对时候，可根据index快速找到对应地址存储的信息，此为查询快.增删慢：但要进行增删的时候，就必须将目标位置后的所有元素都整体移动，因此就比较耗时，此为增删慢.2.链表增删快：链表在物理上是动态地分配储存空间，不要求连续性，但是要求逻辑上的连续。它需要存储每个元素在内存中的地址，以及它相邻元素的地址，然后像链条一样把各元素链起来，保证了在逻辑上的连续性。比如:单链表，每个元素除了存储本身的值外，还存储了前驱的引用，也就是存储了前驱所在的内存地址信息。双链表就是不仅存储了前驱的引用还存储了后继的引用.
增加元素的时候，只需给增加元素添加其前元素或后元素的地址；删除元素的时候，修改目标元素前驱和后驱的首位连接地址. 故此为增删快。
查询慢：由于没有像数组那样的索引，因此，查询的时候需要遍历整个链表所有元素的内存地址，然后才能确定目标元素，此为查询慢。
内存中的存储形式可以分为连续存储和离散存储两种。因此，数据的物理存储结构就有连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。
*因为数组是连续存储的，在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据，但是如果要在数据组中任意位置上插入一个元素，就需要先把后面的元素集体向后移一位为其空出存储空间。
与之相反，链表是离散存储的，所以在插入一个数据时只要申请一片新空间，然后将其中的连接关系做一个修改就可以，但是显然在链表上查找一个数据时就要逐个遍历了。考虑以上的总结可见，数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组；当对数据集中的数据进行添加或删除比较多时最好选择链表。｀
IT资料搬运工
Evernote症候群
法国生活砖家
专业撰写法国计算机类实习报告，毕业设计，小项目，作业...链表和数组的区别在哪里？ - CSDN博客
链表和数组的区别在哪里？
我一直有这样的困惑：链表和数字的区别在哪里？数组是线性结构，可以直接索引，即要去第i个元素，a[i]即可。链表也是线性结构，要取第i个元素，只需用指针往后遍历i次就可。貌似链表比数组还要麻烦些，而且效率低些。
想到这些相同处中的一些细微的不同处，于是他们的真正不同处渐渐显现了：链表的效率为何比数组低些？先从两者的初始化开始。数组无需初始化，因为数组的元素在内存的栈区，系统自动申请空间。而链表的结点元素在内存的堆区，每个元素须手动申请空间，如malloc。也就是说数组是静态分配内存，而链表是动态分配内存。链表如此麻烦为何还要用链表呢？数组不能完全代替链表吗？回到这个问题只需想想我们当初是怎么完成学生信息管理系统的。为何那时候要用链表？因为学生管理系统中的插入，删除等操作都很灵活，而数组则大小固定，也无法灵活高效的插入，删除。因为堆操作灵活性更强。数组每次插入一个元素就需要移动已有元素，而链表元素在堆上，无需这么麻烦。
说了这么多，数组和链表的区别整理如下：
数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续；
数组元素在栈区，链表元素在堆区；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
本文已收录于以下专栏：
相关文章推荐
数组结构：
数组结构在通过索引进行查询数据时效率比较高，而对于数组插入和删除操作，则效率会比较低，在第一个位置进行插入数据，其余数据就需要依次向后移动，而第一个数据进行删除，则需要所有数...
首先从逻辑结构上说，两者都是数据结构的一种。
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量...
1、数组的存储空间是一大片连续的，链表的存储空间是不定的，每个链表的节点元素都会存储该节点的数据和下个节点的地址指向。数组初使化必须制定大小，而链表却不需要便是这个原因。2、就增删改查而言，数组因为地...
数组,在内存上给出了连续的空间.链表,内存地址上可以是不连续的,每个链表的节点包括原来的内存和下一个节点的信息(单向的一个,双向链表的话,会有两个).
数组优于链表的:
1.内存空间占用的少,因...
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要
在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加...
链表和数组都可用来存放指定的数据类型。
首先分别介绍一下链表和数组。
链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。通常链表每一个元素都...
链表和数组一样是一种数据结构。
数组是将元素在内存中连续存放，由于每个元素占用内存相同，所以可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中...
数组和链表的区别以及数组和结构体的区别，这个对于理解数组，链表以及结构体有些帮助...
线性表的顺序存储结构，最大的缺点就是改变其中一个元素的排列时都会引起整个合集的变化，其原因就是在内存中的存储本来就是连贯没有间隙的，删除一个自然就要补上。针对这种结构的优化之后就出现了链式存储结构，换...
数组和链表是两种基本的数据结构，他们在内存存储上的表现不一样，所以也有各自的特点。大致总结一下特点和区别，拿几个人一起去看电影时坐座位为例。数组的特点
在内存中，数组是一块连续的区域。 拿上面的看电影...
他的最新文章
讲师：王禹华
讲师：宋宝华
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)博客分类：
在程序中，存放指定的数据最常用的数据结构有两种：数组和链表。
数组和链表的区别：
1、数组是将元素在内存中连续存放。
链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。
2、数组必须事先定义固定的长度，不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
链表动态地进行存储分配，可以适应数据动态地增减的情况。
3、(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小。
链表从堆中分配空间, 自由度大但是申请管理比较麻烦。
数组和链表在存储数据方面到底孰优孰劣呢？根据数组和链表的特性，分两类情况讨论。
一、当进行数据查询时，数组可以直接通过下标迅速访问数组中的元素。而链表则需要从第一个元素开始一直找到需要的元素位置，显然，数组的查询效率会比链表的高。
二、当进行增加或删除元素时，在数组中增加一个元素，需要移动大量元
素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样，如果想删除一个元素，需要移动大量元素去填掉被移动的元素。而链表只需改动元素中的指针即可实现增加或删除元素。
那么，我们开始思考：有什么方式既能够具备数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势？HASH呼之欲出。
所谓的hash，简单的说就是散列，即将输入的数据通过hash函数得到一个key值，输入的数据存储到数组中下标为key值的数组单元中去。
我们发现，不相同的数据通过hash函数得到相同的key值。这时候，就产生了hash冲突。解决hash冲突的方式有两种。一种是挂链式，也叫拉链法。挂链式的思想在产生冲突的hash地址指向一个链表，将具有相同的key值的数据存放到链表中。另一种是建立一个公共溢出区。将所有产生冲突的数据都存放到公共溢出区，也可以使问题解决。
如何实现hash的动态增加空间的效果？这和装在因子密切相关。装填因子 = 填入表中的元素个数 / 散列表的长度。当装填因子达到一定值a时，我们就让数组增加一定的内存空间，同时rehash。
下面用两个示例来加深理解。
示例一：用链表实现队列
package cn.netjava.
public class LinkNode {
//构造器：传入Object对象
public LinkNode(Object obj){
public O //Object对象
public LinkN//下一个节点
//重写toString方法
public String toString(){
//System.out.println(data);
return (String)
//返回Object对象
public Object getData(){
//修改Onject对象
public Object Update(Object o){
package cn.netjava.
public class LinkQueue {
public LinkNode front=//第一个节点
public LinkNode last=//最后一个节点
public static void main(String args[]){
LinkQueue lq=new LinkQueue();
LinkNode lq1=new LinkNode("郑睿1");
LinkNode lq2=new LinkNode("郑睿2");
LinkNode lq3=new LinkNode("郑睿3");
LinkNode lq4=new LinkNode("郑睿4");
lq.InsertLinkNode(lq1);
lq.InsertLinkNode(lq2);
lq.InsertLinkNode(lq3);
lq.InsertLinkNode(lq4);
int count=lq.getLength();
System.out.println("链表的长度为"+count);
for(int i=0;i&i++){
LinkNode ln = lq.getLinkNode(i);
System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
lq.deleteLinkNode(2);
count=lq.getLength();
System.out.println("链表现在的长度是"+lq.getLength());
for(int i=0;i&i++){
LinkNode ln = lq.getLinkNode(i);
System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
lq.getLinkNode(1).Update("更新后的对象郑睿");
for(int i=0;i&i++){
LinkNode ln = lq.getLinkNode(i);
System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
for(int i=0;i&200;i++){
LinkNode ln = new LinkNode(i);
lq.InsertLinkNode(ln);
System.out.println("数组长度为"+lq.getLength());
* 插入节点
* @param obj：插入节点的对象
public void InsertLinkNode(Object obj){
//当链表为空，新建一个节点并设置为第一个节点
if(front==null){
front=new LinkNode(obj);
//当链表不为空，新建一个节点并插入到最后一个节点的后面
LinkNode next=new LinkNode(obj);
last.next=
*在指定索引下插入节点
* @param index
public void insertIndexObj(int index,Object obj){
//判断输入的索引是否越界，如果越界，则抛出异常
int total=getLength();
if(index&total||index&0)
throw new java.lang.RuntimeException("输入的索引越界了！");
LinkNode lNode=getLinkNode(index);
LinkNode linkNode=new LinkNode(obj);
lNode.insert(linkNode);
* 根据索引删除链表
* @param index：索引
public void deleteLinkNode(int index){
//判断输入的索引是否越界，如果越界，则抛出异常
int total=getLength();
if(index&total||index&0)
throw new java.lang.RuntimeException("输入的索引越界了！");
if(front!=null){
LinkNode n=
LinkNode m=
int count=0;
while(n!=null){
if(count==index){
if(n.equals(front)){
front=front.
* 根据索引取出节点
* @param lNode:节点
* @return：根据索引返回的节点
public LinkNode getLinkNode(int index){
if(front==null)
LinkNode l=
int count=0;
while(l!=null){
if(count==index)
* 得到链表的长度
* @return：链表的长度
public int getLength(){
if(front==null)
LinkNode l=
int count=0;
while(l!=null){
* 修改对象节点
* @param index：对象节点索引
* @param obj：修改对象内容
public void UpdateLinkNode(int index,Object obj){
LinkNode lNode=getLinkNode(index);
lNode.Update(obj);
示例二：保存QQ号码及QQ用户
package cn.netjava.
public class QQUser {
public String userN//用户姓名
public String passW//用户密码
public S//用户性别
//用户年龄
public String getUserName() {
return userN
public void setUserName(String userName) {
this.userName = userN
public String getPassWord() {
return passW
public void setPassWord(String passWord) {
this.passWord = passW
public String getSex() {
public void setSex(String sex) {
this.sex =
public int getAge() {
public void setAge(int age) {
this.age =
package cn.netjava.
public class LinkQueue {
public LinkNode front=//第一个节点
public LinkNode last=//最后一个节点
* 根据索引删除链表
* @param index：索引
public void deleteLinkNode(int index){
if(index&0||index&)
if(front!=null){
LinkNode n=
LinkNode m=
int count=0;
while(n!=null){
if(count==index){
if(n.equals(front)){
front=front.
* 根据索引取出节点
* @param lNode:节点
* @return：根据索引返回的节点
public LinkNode getLinkNode(int index){
if(front==null)
LinkNode l=
int count=0;
while(l!=null){
if(count==index)
* 得到链表的长度
* @return：链表的长度
public int getLength(){
if(front==null)
LinkNode l=
int count=0;
while(l!=null){
* 修改对象节点
* @param index：对象节点索引
* @param obj：修改对象内容
public void UpdateLinkNode(int index,Object obj){
LinkNode lNode=getLinkNode(index);
lNode.Update(obj);
package cn.netjava.
public class QQNode {
//构造器：传入QQ号，QQ用户对象
public QQNode(int qq,QQUser user){
this.user=
public QQU//QQ用户
public QQN//下一个QQ节点对象
public LinkQ//队列
public LinkQueue getLq() {
public void setLq(LinkQueue lq) {
public int getQq() {
public void setQq(int qq) {
public QQUser getUser() {
public void setUser(QQUser user) {
this.user =
public QQNode getNext() {
public void setNext(QQNode next) {
this.next =
Hash方法类
package cn.netjava.
public class QQHash {
private QQNode[] table=new QQNode[100];
private float load=0.75F;//装载因子
private int count=0;
private int gain=100;
public static void main(String args[]){
QQHash qqHash=new QQHash();
QQUser user1=new QQUser();
user1.setUserName("用户一");
user1.setPassWord("1");
user1.setAge(20);
user1.setSex("女");
qqHash.put(1, user1);
QQUser user2=new QQUser();
user2.setUserName("用户二");
user2.setPassWord("12");
user2.setAge(20);
user2.setSex("男");
qqHash.put(2, user2);
QQUser user3=new QQUser();
user3.setUserName("用户三");
user3.setPassWord("123");
user3.setAge(20);
user3.setSex("男");
qqHash.put(3, user3);
QQUser user4=new QQUser();
user4.setUserName("用户四");
user4.setPassWord("1234");
user4.setAge(20);
user4.setSex("女");
qqHash.put(101, user4);
qqHash.returnQQNode();
user1=qqHash.get(1);
user2=qqHash.get(2);
user3=qqHash.get(3);
user4=qqHash.get(101);
QQNode[] table=qqHash.returnQQNode();
System.out.println("表的长度为
"+table.length);
qqHash.returnTabLen();
for(int i=0;i&table.i++){
if(table[i]!=null){
System.out.println("实际存在的Table["+i+"]的值"+table[i].getQq());
LinkQueue lq=table[i].getLq();
if(lq.getLength()&0){
System.out.println("存在挂链");
for(int j=0;j&lq.getLength();j++)
System.out.println("挂链第"+i+"个值为"+((QQNode)lq.getLinkNode(i).getData()).getUser().getUserName());
* 存放QQ及用户
* @param qq:QQ号
* @param user：QQ用户
public void put(int qq,QQUser user){
//判断己放对象的个数和table的长度比是否达到装载因子,
//如果超过,则reHash一次,增长,
//然后再放!
float rate=(float)count/table.
if(rate&=load){
QQNode[] table1=new QQNode[table.length+gain];
for(int i=0;i&table.i++){
QQNode q=table[i];
int qqnum=q.getQq();
QQUser u=q.getUser();
int qqhash=hashQQ(qqnum);
q.setQq(qqnum);
q.setUser(user);
table1[qqhash]=q;
table=table1;
System.out.println("table长度："+table.length);
//判断是否存在hash冲突
boolean judge=exist(qq);
System.out.println("是否存在冲突"+judge);
int index=hashQQ(qq);
System.out.println("hash值"+index);
if(judge){//不存在hash冲突，直接将qq和用户存放在通过hash函数获得的地址中
QQNode q=new QQNode(qq,user);
q.setQq(qq);
q.setUser(user);
table[index]=q;
else{//存在hash冲突
QQNode q=new QQNode(qq,user);
q.setQq(qq);
q.setUser(user);
System.out.println("
"+q.getQq()+"
"+q.getUser());
LinkQueue lq=q.getLq();
lq.InsertLinkNode(q);
for(int i=0;i&lq.getLength();i++)
System.out.println("======"+((QQNode)lq.getLinkNode(i).getData()).getQq());
if(lq.getLength()==0){
table[index].setNext(q);
* 根据QQ号取得QQ用户信息
* @param qq：QQ号
* @return:QQ用户
public QQUser get(int qq){
int index=hashQQ(qq);
QQNode q=table[index];
System.out.println("节点"+q.getQq());
//看是否有下了个节点,如有,则是冲突的,就要一个一个比较
if(q.next==null)
return q.getUser();
LinkQueue lq=q.getLq();
for(int i=0;i&lq.getLength();i++){
QQNode aa=(QQNode)lq.getLinkNode(i).
int qqq=aa.getQq();
if(qqq==qq)
System.out.println("查找到了！");
return aa.getUser();
//计算QQ号的has值,自定义has函数
private int hashQQ(int qq){
return qq%table.
//判断是否存在hash冲突
private boolean exist(int qq){
int qqhash=hashQQ(qq);
if(table[qqhash]!=null)
private QQNode[] returnQQNode(){
System.out.println("已存在数据个数为"+count);
return this.
//返回表中实际存在的数据的个数
private int returnTabLen(){
return this.
浏览: 114745 次
来自: 浙江
yaqing503 写道您好！我按照您给的步骤完成了环境的配置 ...
/adminhttp ...
sjsmilelife 写道imread读取不了sdcard
imread读取不了sdcard 的图片，已经加权限了还是不行 ...
yaqing503 写道您好！我按照您给的步骤完成了环境的配置 ...
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'516被浏览137435分享邀请回答16125 条评论分享收藏感谢收起8添加评论分享收藏感谢收起查看更多回答当前位置： >>
基于ARM CPU的Linux物理内存管理
基于 ARM CPU 的 Linux 物理内存管理基于 ARM CPU 的 Linux 物理内存管理 刘永生Page 1 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理本文一共分为四个部分 第一部分介绍内存布局的演进。 这样方便理解为什么内存管理中需要虚拟地址， 物理内存和 访问保护。 第二部分介绍在 ARMC CPU 上是如何支持内存管理的。 操作系统对内存的管理的目的就是满 足应用程序（当然也有部分内核代码）的内存申请和释放，而内存的申请和释放都是围绕 CPU 硬件上的内存管理单元（MMU）而进行的。所以不了解 ARM MMU 对地址映射的一些 概念和要求，就没办法理解内核中的某些数据结构和执行操作。如果对这部分比较了解，可 以越过。 第三部分介绍 Linux 内核对物理内存管理的思想和原理。如果能在原理和框架上理解内核对 物理内存如何管理的，那么就能更快和深入地理解内核代码是如何实现内核管理的。 第四部分在源代码中介绍 Linux 内核是如何实现物理内存管理的。 注，本文只介绍了内核是如何管理物理内存的，并不包括内存管理的其他部分。本文的介绍 内容到 buddy 系统建立为止，而建立在 buddy 系统之上的 cache-cache 机制，如 Slob，Slab 和 Slub 等则不在本文范围。Page 2 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理第一部分，内存布局的演进首先在一个设备上，CPU 执行所需要的代码可以存放在 Rom 中，也可以存放在 Ram 里 存放在 ROM 中的代码，虽然可以被直接执行，但因为 Rom 不能被改变（或需要复杂的命令 序列来改变） ，所以系统还需要一些 Ram 来存放用于程序执行所需要的数据，例如全局变量 和堆栈。 因为 RAM 在断电的情况下是不能继续保持其中内容的， 所以在 RAM 中的程序代码 需要系统上电的时候从外面的存储介质中加载，可以是从一个 Rom 中把代码读入到 Ram， 也可以其他的存储介质，比如 Nand Flash 或 SD/MMC 卡。而在 PC 上典型的是从硬盘（SATA 接口）读入。无论哪种启动执行方式，CPU 都需要一块能够可读写的 RAM。我们的问题是， 系统中 RAM 是如何使用的呢？ 最直接和简单就是把一块内存划分成不同的区域， 用来存放不同目的数据， 例如下图所 示，直接把 Ram 划分成代码，数据和堆栈，也是程序执行必须的三要素。这是最直接的内存使用方式， 没有什么技巧和也不需要管理， 直接简单粗暴的把内存分 为三部分。 每部分有各自的使用目的和大小， 在使用期间也不需要改变大小和使用目的。 在某些单片机或 DSP 上就是这么使用物理内存的，直接高效。它的缺点就是只能运行 一个程序，所解决问题的也比较单一和固定。 随着使用需求的变化，这样的布局就出现了局限。如果我们需要运行多个程序，每 个程序以时间片的方式共享 CPU 时间。如上图所示，系统中需要有三个程序来完成不同的任务， CPU 会轮流地执行不同程 序的代码。CPU 在切换到不同程序前，要把当前程序的状态保留下来，以便之后再轮到 当前程序运行时能从当前的状态开始继续执行。 这个需要被保存下来的状态， 也就做程 序的 CPU 上下文（cpu context)。每个程序都需要自己的运行数据，那么相应地，根据 运行程序的数量也要把内存分成三部分。 每部分为一个程序服务， 又把内存划分成更小 的代码， 数据和堆栈区。如下图Page 3 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理系统中既然有了多于一个的 CPU 上下文，就需要 CPU 能不断地在不同的上下文之 中切换。例如 CPU 可以先执行 A，然后执行 B，然后有要切换去执行 C。那么 CPU 什么 时候需要切换和如何进行切换？解决它， 系统就要有一个独立于所运行程序之外的模块 来仲裁和调度不同的程序，执行 CPU 上下文的切换。这样系统还需要一个管理 CPU 上 下文切换的模块。如下图所示，这个模块我们先叫它为系统代码。结束地址代码A 全局数据 堆栈 代码B 全局数据 堆栈 代码C 全局数据 堆栈 系统代码 系统数据 系统堆栈系统代码除了管理 CPU 上下文切换之外，还要管理一些外围设备并提供统一的使用接 口。 这样不同的应用程序就能直接调用这些通用接口来直接使用外设， 而不需要每个程 序各自编写自己的程序来控制外设。 这些外设管理程序也被叫做去驱动。 这样做的好处 是 - 外设管理的代码统一集中，不需要需要每个程序自己都编写设备使用代码 - 易于定义统一通用的接口，这样在理想情况下，应用程序就可以在不改面代码的情 况在其他操作上运行。 - 简化了应用程序使用外设的设计和编码 - 便于协调和同步不同程序使用同一外设，驱动程序可以决定应用程序是共享式的使 用当前设备还是排他式的使用。 此时，上图中的系统代码就有了管理 CPU 上下文切换和各种外部设备的功能，具有这 么多功能的系统代码，也可以被称为操作系统（Operating System） 。 这样每个程序都有了属于自己的，预定义的代码，数据和堆栈区间。但问题是不同 的程序在运行的过程中， 所需要的数据和堆栈空间是不一样的。 如何给系统中的程序分 配或预定义内存就成了一个问题。 例如可以采取平均分配， 也就是给每个程序上下文都 分配尽可能多的内存并大小相等。 如果按照系统中所需内存最大的程序所需的内存量来 为所有的程序预留物理内存， 那么系统就需要准备更大的物理内存。 这样做虽然可以保 证系统的正常运行， 结果会是浪费一些物理内存。 或者根据每个程序所需要的实际内存 大小而为每个程序预分配。 这样做的一个问题就是有的程序在运行之前， 并不知道所需 要内存的最大量，因为有些内存需要在程序运行中才能确定，比如要浏览一个网页，程 序在运行之前并不知道要浏览网页的大小。综合上面的问题： 1， 在一个 32 位的 CPU 系统中，尽可能地为每个程序分配足够多的空间 2， 按分配方式，把程序所用的内存分为两类，一类是静态的，一类是动态的。静态的 内存在程序设计和编译时就可以确定的，比如程序的代码，使用的全局变量等。这 些内存在程序运行的生命周期中是一直存在。动态的内存是在程序运行过程中根据 需要而向系统动态地申请的内存。 解决上面的问题， 系统引入了虚拟内存的概念。 虚拟内存是如何解决这个问题的呢？Page 4 刘永生 微信: eternalvita 邮箱：开始地址基于 ARM CPU 的 Linux 物理内存管理如下图在上图中， 1， 程序执行过程中所看到的不在是物理内存，而是虚拟内存。就是说程序执行的代码地址 和所要访问的数据地址都是使用虚拟地址。虚拟地址不是物理地址，它是 CPU 能看到的 所有寻址空间，换句话说虚拟地址是始终存在的。所以就可以在 CPU 所支持的 4G 空间 里，为每个程序预先分配最大可能的虚拟地址空间。如上图，程序 A，程序 B，程序 C 和系统代码分别得到了 1G 的虚拟地址空间。 2， 虚拟地址可以和物理内存绑定，也可以不和物理内存绑定。这种绑定也就做映射，默认 状态下虚拟地址是没有映射物理内存的。只有被映射之后的虚拟地址才能被 CPU 访问， 否则系统会产生异常。 3， 在程序被加载的时候， 可以把程序所需要的静态内存部分进行映射。 如上图中的代码段， 数据段和一个堆栈。堆栈大小虽然不是在编译时候就知道，但程序运行必须要有栈，所 以这里可以为每个程序预分配一个合适大小的栈，比如 4K。如果程序运行中，所需要的 栈超过 4K 了， 那么就动态地向系统申请和映射一块更大的栈。 这个过程也就做栈扩展。 4， 连续的虚拟内存映射的物理内存上不一定或不需要是连续的。 5， CPU 在运行中所关心的是它所能访问的指令和数据是否是连续的，通过虚拟内存就能保 证 CPU 所看到的地址始终是连续的，比如对一个数组进行操作，这个数组所占据的虚拟 内存对应的物理地址是否连续，CPU 并不关心也看不到，因为它只需要连续地访问虚拟 地址就可以实现数据的读写操作。这也是为什么虚拟地址又被成为线性地址。CPU 为了 达到这个目的，也就是在执行过程中直接操作虚拟地址而结果被自动地保存在物理内存 中，需要额外的硬件支持。这个能够把 CPU 执行过程中需要的虚拟地址自动地翻译成物 理内存地址的附属硬件，被称为内存管理单元（MMU） 。所以映射需要 CPU 在硬件上支 持，而存放这种映射关系的矩阵被称为地址映射表。 6， 在运行过程中，如果函数调用的层次变多或局部变量累积变大而导致堆栈空间不断变大 并超过了预分配的栈空间（比如超过了预分配的 4K 栈） ，那么就需要动态地增加堆栈的 空间。而系统中虚拟空间是早就分配好只是没有映射实际的物理内存，所以问题就简化 成，如果堆栈空间不够，只要继续映射更多的物理内存就可以了。从上图可以看到，每 个程序都有一些可使用但没被映射的虚拟地址，在物理内存上也有一些能被使用但未被 映射的物理内存。这些未被使用的物理内存在运行过程中被动态分配给所需要的程序， 也就是按照实际把更多的物理内存映射到某个程序所需要的虚拟空间上的过程，就是动 态分配。除了堆栈，动态分配也适用于运行中处理预留的数据段不足的场景，如前面所 说的动态下载网页的例子。这个动态分配的数据区域，也叫做堆（heap）用以区分静态 分配的数据段。既然，数据和堆栈区都需要动态的伸缩，上图的布局在动态改变数据和 堆栈区时就会产生互相间隔（interleave） 。为了使各功能区间连续，可以把布局做点改Page 5 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理动，如下图。这样数据区间就可以在运行时向高地址扩展形成堆（heap） ，而堆栈的扩 展也可以连续地从高地址向低地址移动。堆（heap）和堆栈（stack）区始终是分开的， 不会互相间隔。这也是为什么大多数系统的‘栈’都是从上到下（高地址到低地址）增长的原因（也系 统的栈是向上增长的例外） 。这样就解决了动态需要内存的问题，同时在没有增加实际物理 内存总量的情况下， 增加了系统中物理内存的使用效率。 所以就需要在系统代码中增加对动 态申请和释放内存的支持，因此操作系统引入了另一个重要的功能―‘内存管理’ 。一个完 整的操作系统应该具有如下功能， a) 调度模块以使不同的 cpu 上下文都能得到 CPU 的时间来运行 b) 同步机制来协调不同 CPU 上下文同时访问同一资源的竞争问题 c) 驱动和具有服务性质的软件协议栈，例如网卡和 TCP/IP 协议栈，硬盘和文件系统 等 d) 静态和动态内存管理 e) 加载和运行应用程序 此时，每个程序在操作系统的调度下运行在系统划分好的虚拟空间内，互相不干扰相安 无事。 但程序是人编写的， 总会由于失误而出现这样或那样的问题。 随着程序复杂性的增高， 程序出现问题的概率也变得越来越大。例如，程序 A 运行中出现了问题，它破坏了自己代 码区的内容， 但此时操作系统并知道程序 A 的代码被破坏了， 还在继续调度执行 A 的代码， 那么执行的结果就是错误的和不可预期的，甚至是破坏整个系统。比如继续执行被修改的 A 代码破坏了程序 B 的代码或数据，那么程序 B 就不能正常工作了。或者更严重一点，程序 A 的代码破坏了操作系统的代码和数据，那么整个系统都不能正常工作，系统就会崩溃。这并 不是我们想要看到的，而我们希望系统应该是足够健壮的。理想的系统应该是： 1， 某个区间应该是只读的，比如代码区间，那么它就不会在运行过程中被修改 2， 某个程序只能访问被限制的或指定的区间，比如程序 A 不能访问程序 B 的区间，不但包 括 B 的代码，还包括程序 B 的数据和堆栈段都不能被程序 A 访问。 3， 任何程序代码不能破坏操作系统的代码和数据。 为了解决这个问题，引入了内存保护的概念，如下图Page 6 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理同内存映射一样，内存保护也需要在硬件上支持。如上图所示，这个保护机制应该能： 1， 设定任一内存区域的读写属性，这样就可以设置任何程序的代码区为只读； 2， 设定程序的访问权限这样可以防止程序越界破坏其他程序管理的空间。一旦发生越 界的事情，能被捕获并通知 CPU。 3， 在操作系统中支持因破坏保护而产生的异常。异常被捕获之后，操作系统需要执行 进一步的处理，比如终止程序 A 的调度，结束 A 程序的运行，释放程序 A 占据的外 设使用权等。 在上图中可以看到，内存的保护是作用在虚拟地址上的，所以就在硬件的内存管理单元 中加入了内存的权限管理。因此内存管理单元就有了如下功能： a) 设置内存访问权限和捕获异常 b) 虚拟地址的转换 从此， 系统可以在线性的虚拟地址上运行并得到了来自硬件上的保护。 每个程序都在自 己的相对大的空间里执行，享受着操作系统提供的各种服务。 有一天程序 A 需要升级，升级后的程序 A 需要 2G 的空间。此时程序 B 和 C 也需要至少 1G 的内存地址空间。还有，系统需要动态地执行一个新的程序 D，因为空间都已经被分配 出去了，并没有可用的空间给程序 D 使用。但运行新程序是一个普遍的使用场景和需求。 为解决这些问题， 继续对上面讨论过的布局进行优化。 现在先分析下上图中虚拟地址使用的 特点： 1， 不同程序之间是分时执行的，也就是程序 A 执行的时候，程序 B 是没有运行的。而程序 A 又被限制不能访问程序 B 的空间，所以在程序 A 运行时，程序 B 和程序 C 的空间是完 全无效的。那么假如此时程序 A 能利用程序 B 或 C 管理的虚拟空间， 那么程序 A 所覆盖 的虚拟空间就会变的更大，最大到 3G。然后在程序 B 开始运行时，程序 A‘归还’属于 程序 B 的虚拟空间，这样程序 B 就可以正常地运行，并且还可以‘借用‘程序 A 和程序 C 的虚拟空间。 2， 在程序 A‘借用’程序 B 的虚拟空间时，不能使用程序 B 所映射的物理内存。那么程序 A 虽然借用了 B 的虚拟空间，但不会破坏程序 B 使用的物理内存中的内容。 3， 无论哪个程序运行，都需要使用和享受操作系统作提供的基本功能和服务。 所以，系统的内存布局就变成了下面的样子1， 这样每个程序所能看到的虚拟空间就变成了 3G， 这个 3G 的空间也被称为应用空间， 也叫做用户空间。 2， 操作系统代码和数据以及栈的空间映射保持不变，这样对于每个程序，操作系统都是统Page 7 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理一的地址布局和调用接口。作操作系统所占的空间叫做内核空间。 3， 系统中任一时刻 CPU 上只有一个程序在运行，运行的程序占据了整个 3G 的虚拟空间。 每个程序所使用的物理内存都是独立的。虽然程序间可以共享物理内存，但并没有改变 进程独占物理内存的本质。进程需要有自己的内存映射表，这样进程所有的物理内存就 映射在自己独享的内存映射表中。当程序 A，B 进行切换时，不仅要变更 CPU 的上下文 （通用寄存器的内容） ， 还有变更内存上下文（虚拟程序映射表） 。 4， 程序间的通信变得了困难，列如在程序 A 运行时不能访问也看不到程序 B 的地址空间， 无法直接访问程序 B 的内容。解决这个问题，引入了 IPC（跨进程通信）的概念。IPC 的 实现方法有很多，例如在不同进程共享一块物理内存，或者通过操作系统代码和操作系 统数据段来实现 IPC 等。IPC 虽然能实现通信，但效率比较低下。 演进到此， 上图的样子是几乎所有现代流行操作系统所采用的内存布局了。 操作系统的 内核空间的划分并不是固定的，也可以划分在 2G 处。但这只是分界不同，主要思想没变。 这只是个原理图，实际的系统在内存管理上会复杂一点，但其思想都是源于的，没有脱离上 图的范围。 现在的操作系统管理内存看似很复杂， 但都是为了解决某些问题而一步一步演进 而来的。所以，不是内存的管理复杂，而是使用内存的场景变得更复杂，从而导致系统增加 了各种方式方法来满足这些复杂的需求 ?。如果我们把复杂的内存管理去掉一些容错和某 些特殊的操作后，就会发现其实它挺简单的，如上图一样清晰明了?。 内存布局的演进就是不断地解决所遇到的问题，不断地满足新的需求。 而为了满足新 的需求而出现的方法和程序更新本身就是一种创新或发明。 问题不会终结， 解决问题也不会 停止，就需要有更多的创新和发明出现。 上面的演进只是列子，不是全部，需求永无止境，演进也不会停止。内存使用过程中， 还有很多其他的问题。比如从硬件角度，随着 CPU 的频率越来越快，内存的读写速度已经 严重的制约了 CPU 的执行速度。为解决这个问题，而发明了 Cache；随着 Cache 的应用，发 早期 VIVT 型的 cache 虽然查找和比对的速度快， 但在运行中需要不断的同步 cache 的内容， 为解决这个问题， 增加了 VIPT 和 PIPI 类型的 Cache。 同时为加快地址翻译速度， 又引入 TLB， 用来缓存地址映射。 为了增加物理内存管理的灵活和颗粒度， 又把虚拟内存映射表分成几级。 为了支持多个操作系统，又引入了 Hypervisor。 而软件上的演进更是一日千里，除了要支 持上述的硬件演进外，还要解决系统面临的其他问题，比如内存管理方法和策略，任务调度 的方法和策略等。 在内存管理中， 另一个重要的需求就是尽量地降低内存使用过程中产生的碎片， 这也是 提高内存使用效率的一个要求。Page 8 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理第二部分 ARM 的内存映射表如前所说，内存布局和使用的演进需要 CPU 在硬件上支持。这部分主要介绍 ARMV7 硬 件上如何支持内存映射的。 ARMV7 是 ARM 体系结构第 7 个版本 （Version 7） ， 而 Cortex A9， A7 或 A15 都是基于 V7，只是在功能实现和功耗上有些差异， 而这种差异所产生的变种， 也是针对不同的目标市场或产品所做的优化，或是为了解决不同的应用问题。比如 ，A7 就 是属于低功耗的一款产品，相应它的计算能力（相同时钟频率下的 DMIPs）也比 A9 和 A15 低很多。A7 和 A15 支持 Hypervisor 而 A9 则不支持。所以，这里所说的 ARM 地址映射表， 对所有基于 ARMV7 的产品都有效。 在 ARMV7 上支持两种内存管理，一个是 VMSA，另一个是 PMSA。PMSA 的管理相对比 较简单直接，属于过时的 MMU 管理。而 VMSA 的功能更强大和灵活，也是被大多数 CPU 产 品所采纳使用的，满足了所有内存管理的需求。 VMSA 支持很多功能，包括虚拟内存映射，Cache， Write Buffer， TLB， 访问权限管 理等。 其中最主要或基础的功能就是物理和虚拟内存映射， 其他的功能和特性都是围绕着这 个内存映射而引入的功能和优化。 其中 Cache 是缓存物理内存的内容来加快 CPU 读效率的， Write Buffer 是优化写速度， 而 TLB 是缓存‘虚拟地址和物理地址对‘来加快地址转换的速 度。对于内存管理来说更关心的是内存映射。ARM 的 Architecture Reference Manual 对内存 管理有着非常详细的描述，这里只引用和说明本文所需要的地址映射表。 既然是一个表， 那么它就需要占用一定空间， 所以在系统中需要一片物理内存来存储这 个虚拟映射表。 然后把这个虚拟映射表的地址告诉 ARM，cp15 中 TTBR （Translation Table Base Register ）做为 ARM 内置的寄存器就是用来来保存这个表地址的。系统启动的时候这个寄 存器的默认值为 0，代表系统中没有有效的虚拟内存映射表，也意味着 ARM 不知道如何转 换地址，因此默认状态下 MMU 是禁止的（disabled） ，因此 CPU 的执行是基于物理地址的。 在之后的运行中，由操作系统来决定啥时使用 MMU。 但在使用 MMU 之前，操作系统需要 配置虚拟映射表，并把配置好的虚拟映射表的首地址写入 TTBR，这样 ARM 的 MMU 硬件单 元才能通过访问虚拟映射表，自动地翻译 CPU 所需要的虚拟地址。 这个写入 TTBR 的地址 必须是物理地址而不能是虚拟地址，如果是虚拟地址， MMU 工作起来就变成了一个先有 鸡还是先有蛋的问题了。注：如果 Cache 的类型是 VIPT 和 PIPT 类型，那么内存映射表可以 使用 Cache。 除了在打开 MMU 功能之前需要设置 TTBR 寄存器，操作系统软件在运行中也需要不断 地改变 TTBR 寄存器来完成进程上下文的切换。 操作的系统的执行过程为： 1， 找到下一个要执行的进程（线程） 。注，线程才是 CPU 执行的主体 2， 保存 ARM CPU 执行当前线程所使用的通用和状态寄存器的值，并把下一个线程之 前保存的内容恢复到通用和状态寄存器，这个过程也叫做 CPU 上下文的切换。 3， 更新下一个进程（线程）的内存映射表到 TTBR 寄存器，这个过程就是内存上下文 的切换。注，理论上切换线程时，TTBR 的内容不一定必须要更新。但进程更新时， TTBR 的内容必须更新。 为了统一操作， linux 操作系统总是切换线程时候更新 TTBR， 而无论当前线程和下一个线程是否属于同一个进程，是否有相同的映射表。内核线 程是个例外。 TTBR 寄存器中存储的是一个物理地址和一些控制位， 格式如下：Page 9 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理这里的 x， 是由 BBTCR 寄存器中的 N 来决定的，默认值是 14。它会影响 TTBR 地址的 对齐属性。如果 x==14，那么内存中的虚拟地址映射表就需要 对齐，这个值可以通过配 置 BBTCR 来改变。寄存器中的其他 bit 的含义和如何设置在 ARM 的公开文档中有着详细叙 述，可以具体参考。这里只要知道这个寄存器长啥样就行了。 确切说上面的 TTBR 结构是 TTBR0 的， ARM 还设置了另一个叫做 TTBR1 的寄存器。 TTBR1 和 TTBR0 的定义有些区别，但基本是完全一样的。那么问题是，为啥 ARM 要设置两个寄存 器来存储内存的映射表呢？这需要先讨论一下 ARM 的另一个寄存器 BBTCR （Translation Table Base Control Register）, 它除了能控制之前提到的 TTBR 中地址如何对齐（X 的值）之外，还 能告诉 ARM 啥时使用 TTBR0 和啥时使用 TTBR1 来转换虚拟地址。先看一下 BBTCR 的定义：这里我们最关心的是 N，其他的 bit 可以从 ARM 的开发文档中找到详细的介绍。这是从 ARM 文档中粘贴过来的。解释下： 如果 N==0，也就是系统中没有配置 TTBCR 的默认值，那么 ARM 总是使用 TTBR0 来翻 译虚拟地址。 所以默认情况下，TTBR1 是没有用的。 如果把 N 设成 1，也就是 N==1， 那么当 ARM 遇到大于等于 0x 时，就需要使 用 TTBR1 寄存器指向的映射表来转换虚拟地址。相应地落在[0xx8000000)范围内 的虚拟地址需要使用 TTBR0 的映射表来翻译。这个是不是看着有点眼熟？ 没错，WinCE6.0 中就是通过把 N 设成 1 来同时使用两个映射表的。在 WinCE6.0 中，内核和用户空间的分割 在 0x 处，在把 N 设成 1 后，所有内核内存的访问都是使用 BBTR1 指向的映射表来 翻译的，而用户空间的地址访问使用 BBTR0 指向的映射表。这个有很大的好处，比如某个 用户进程在内核空间里映射一块物理内存， 那么其他进程中的线程在执行内核代码也需要这 个映射关系时就简单多了，因为所有内核空间的映射都是通过 BBTR1 的，也就是无论哪个 进程做的映射，都是使用同一张映射表操作的。我们可以把这个称为映射共享。 看起来这是一个很好的东西，但是没办法区分 0xC000000 ，而 Linux 默认就是以 0xC0000000 为临界地址划分内核和用户空间的（虽然这个临界空间可以改） 。但问题是，为 什么当初 ARM 不设计成是判断高位是否为全‘1’呢？。按全‘0‘区分，那么地址的分界 就只能是 0xxx 等。如果要是按全‘1’区分，那么地址的分Page 10 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理界就可以是 0xxCxE0000000 等了。ARM 这么设置应该是有原因，但可 以设计的更灵活一些。 不过，就算是能区分 0xC0000000， Linux Kernel 看起来多半也不会引入这个机制，因为 它和 Linux Kernel 已有的机制不同。 虽然这个机制没有在 Linux 中使用，但不代表 Linux 内核不会面临映射同步的问题。那 么当 Linux 面对这个问题时如何解决的呢？也就是在 Linux 中是如何解决内核空间映射同步 的问题呢？问题描述：某个进程 A 在内核中动态的映射了一个物理内存或 I/O 地址，这个寄 存 器 它 的 物 理 地 址 是 [0xx] ， 而 映 射 的 虚 拟 内 存 为 [0xFExFE001000]。这个映射的完成意味着要把这个映射关系写入到相应的虚拟内存映射表中， 以使当前进程 A 能够通过虚拟地址 0xFE000000 毫无错误的访问它所代表的 0x 物理 地址。那问题是，如果进程 B 也需要访问这个物理外设。而在进程 B 运行时， 内核会把进 程 B 的虚拟内存映射表地址写入 TTBR 中。而进程 B 的虚拟映射表并没有进程 A 动态映射的 内容， 那么进程 B 就需要再次把进程 A 做过的映射再做一遍。这不是好的做法，先不论重 复映射可能会引起的潜在的一致性问题（如果映射的是内存的话） ，从内存使用的角度，它 也是一种浪费， 因为任何映射都需要在内存中请求一块物理内存来存储映射关系的。 所以最 好的方法就是只映射一次，然后在其他进程中能共享这个映射。后面会介绍 Linux 是如何解 决这个问题的 既然 ARM 是通过映射表的内容来转换虚拟地址的，那么这个表的内容必须有一个预定 义的固定格式，这样 ARM 才能正确地使用这张表。 ARMV7 的映射表支持两种结构，一种 是为 32 位系统设计的，叫做 Short-descriptor format， 而另一种是支持 64 位的，叫做 Long-descriptor format。发展的趋势是 64 位，但目前流行的应用还是基于 32 位的。所以这 里只引用 short-descriptor 格式，它也是 V7 之前，ARM 唯一支持的格式。对于长描述表，在 Linux 内核也开始得到支持，随着应用的场景越来越广泛和程序变得越来越复杂，基于 ARM 方案的 CPU 支持 4G 以上内存是迟早的事，所以 long-descriptor format 一定会成为以后的主 流。但目前，大多数基于 ARM 方案的还是 32 位的，并且 32 位和 64 位从物理内存管理的角 度看区别不大，只是提供了更大的可访问空间。 基于 Short-descriptor format 虚拟映射表的布局结构如下：从上图可以看到，虚拟映射表包含二级。其中一级表是必须有的，而二级表是可选的。 一级页表支持两种格式，一种是叫做 section 可以用映射 1M 空间，对应的二级页表有 256 个表项， 每个表项可以映射 4K 的物理内存。 另外一种是叫做 supersection 可以用来映射 16MPage 11 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理空间，对应的二级页表有 256 个表项，单一表项可以映射 64K 的物理内存。在目前大多数 操作系统中像 WinCE 和 Linux 使用的都是 Section + Small Page 这样的设置，余下部分都以此 设置讨论。 在一个映射表中，一级页表的表项可以直接映射一片连续的 1M 物理内存，也通过一个 二级页表来间接的映射 1M 物理内存。 多数情况下系统都记基于二级页表来映射物理内存的， 但也有使用一级页表来直接映射一片 1M 物理内存的场景。在第三部分介绍 Linux 内核时会 详细说明。 使用一级页表直接映射的好处是节省映射表所占的物理内存，但副作用是内存必须以 1M 为单位来映射，不利于内存管理。ARM 判断有没有二级页表是通过一级页表的表项的低 2 位 bit 来决定的。 操作系统在初始化映射表时，没有被使用的表项会被设置成 0。Arm 的 MMU 硬件单元 在翻译一个虚拟地址时，首先以虚拟地址的高 12 位作为索引来定位此虚拟地址在一级表中 的表项。如果表项的内容是‘0’ ，则说明此虚拟地址没有被映射到某个物理内存（确切的说 MMU 判断如果最低 bit0 和 bit1 都是‘0’ ， 则认为此地址没有映射） ，MMU 硬件单元会产 生一个异常并迫使 CPU 进入‘data abort’模式执行异常向量表中的异常处理代码（如果针 对代码也可能会产生’prefetch abort’的异常 ） 。 如果表项有效 （低位的两个 bit 不是 0） ， MMU 硬件单元会进一步判断。 如果低两位 0xb00==0b01， 则此表项的内容是一个二级页表的地址。 如果低两位 0xb00==0b10, 则没有二级页表， 则此表项的内容直接指向 1M 的连续物理内存。 去掉 supersection 部分，ARM MMU 的 TTBR 和内存映射表的关系如下图所示：二级页表 一级页表 TTBR0 Section[0] Section[1] Section[2] …... …... …... …... Section[4K-1] Small Page[0] Small Page[1] …... Small Page[255] 4K memory 4K memory 4K memory Small Page[0] Small Page[1] …... Small Page[255] 4K memory 4K memory 4K memory在 MMU 使能的系统中，物理内存的使用和释放都是通过这个表来完成的。虽然这个表 是在内存中，但是他的格式是 ARM 定义的。ARM MMU 硬件单元是这个表的使用者，而操 作系统则是这个表的生产者。物理内存只有被映射到某个虚拟地址才能被 CPU 使用，操作 系统中内存管理必须通过配置这个表来达到使用或共享物理内存目的。因此在 linux 内核在 管理物理内存过程中需要： ? 不断地配置不同的虚拟映射表到 arm 的 TTBR0 中，已到达切换进程的目的，不同进程 的映射表不同；注：linux 内核切换线程时和切换进程时的操作一样，也会配置 TTBR0。Page 12 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理?不断地修改虚拟映射表中的一级或二级页表的表项， 以完成物理内存的使用和释放。 注： 这里的使用和释放是指从 CPU 可见的角度。除了 TTBR0/1 之外， ARM 还需要配置异常向量表 （Vector） ， 如上面提到的 ‘data abort’ 异常产生后，CPU 会调用内核预设的异常处理函数。系统启动后 ARM 认为 Vector 默认的位 置是在 0x0000000 的地址处，但通过配置 SCTLR, CP15 中的 System Control Register 中的 V bit （第 13 bit） 可以改变这个异常向量表(Vector)的位置。 当 V bit 为 1 时， ARM 会从 0xFFFF0000 地址开始访问异常向量表。 目前基本所有基于 ARM 的操作系统都会把 V 位设置成‘1’ ，这 样系统就可以使用地址‘0x0000000’来标记指针无效。Linux 内核会在启动时配置这个寄存 器的 V bit 为 1，并把异常向量表的代码复制到虚拟地址为 0xFFFF0000 的位置。 在第一部分我们讨论的内存演进，加上 ARM MMU 之后就变成了下图的样子：二级页表 一级页表 TTBR0 Section[0] Section[1] Section[2] …... …... …... …... Section[4K-1] Small Page[0] Small Page[1] …... Small Page[255] 4K memory 4K memory 4K memory Small Page[0] Small Page[1] …... Small Page[255] 4K memory 4K memory 4K memory所以，有了 MMU 之后，物理内存被 MMU 隐藏起来，程序代码所见的全是虚拟内存。内核 要通过配置内存映射表来实现虚拟内存到物理内存的映射。而整个 4G 的虚拟空间被分为用 户空间和内核空间， 内核代码始终运行在内核空间。 应用程序运行在用户空间而不能方位内 核空间。 那么剩下的问题是： 1， 内核是如何布局内核空间的？ 2， 内核是如何组织物理内存的？ 3， 备注： 从 ARMV7 开始，相比较之前的版本增加了对安全和虚拟的支持。比如多了 Monitor 和 Hyper 两个模式。 和 Monitor 相关， 还增加了 Secure World 的支持， 用以区分传统的 Normal World。 以上的叙述并没有对这些加以区分，除了从安全和权限的不同之外，他们对内Page 13 刘永生 微信: eternalvita 邮箱：?基于 ARM CPU 的 Linux 物理内存管理?存，尤其是地址映射表和 Vector 的使用和访问没有本质的区别。不过他们都有自己各 自的配置寄存器，由于配置的寄存器不同，这本身的区别在 ARM 的文档中有着非常详 细的描。因为其涉及的操作不在本篇范围，所以就没有提及。上面叙述的内容适用于 Secure world 和 Normal World。不适用于 Hyper 模式和 Hypervisor 的工作方式。相对于 Hyper 模式，又引入了额外的二级映射的概念（stage 2） （不是二级页表） ，目的是使多 个操作系统都可以在自己看来是连续的虚拟地址上管理和操作内存， 就像为了使多个应 用程序都可以在自己看来是在连续的虚拟地址上工作而引入了虚拟映射表一样（stage 1） 。 简单的说就是从这个多出来的映射表中翻译出来的地址不是直接的物理地址， 而是 一个需要继续翻译的虚拟地址。本文忽略 Hyper 模式的映射。 除了地址映射表和异常向量表，ARM 还需要其他的地址设置来完成一些特殊的功能。 这些地址设置有些可以是在设计时预先配置的， 比如系统上电后执行的第一条语句的位 置，这个位置默认是 0x0000000,但是在 SoC 或 CPU 产品设计时，可以把它配置到其他 的位置， 只要系统总线能够寻址到。 比如物理内存的地址空间在 0x 开始的空 间，而启动代码在 0x 开始的 ROM 上或在一个 SD/MMC 卡上。而现在的嵌入 式系统的存储硬件是 eMMC。 例如，如果一个系统的启动存储介质是 SD 卡，那么 CPU 本身是无法直接读取 SD 卡上的内容，因为读取 SD 需要特殊的命令，而不是 CPU 总线 所支持的寻址和访问方式。 所以， 要想读取 SD 卡上的内容， CPU 就需要一个驱动程序。 CPU 需要先启动了这个驱动程序，然后通过这个驱动程序来访问 SD 卡，并把 SD 卡上 的启动代码例如 UBoot 加载到内存，当然如果内存不是 SRam 而是 DDR，那么 DDR 也 需要有个控制器先被配置才能正常工作。解决这个问题，目前较流行的做法是在 SoC 中加一块 ROM，然后把 DDR 和 SDR 卡的驱动程序放在其中，然后一个控制逻辑来启动 DDR 和 SDR 驱动并把 SD 卡上的 boot loader 例如 UBoot 加载到 DDR 中， 然后跳转到 DDR 中开始 执行 boot loader 的代码。如下图所示：SoC 0x3001000 DDR Controller Boot loader(copy) DDRam0x ARM CPU ROM Booting codes SD CardSD/MMC Controller 0xBoot loader如上图例子中， ARM CPU 启动后执行的首地址是在 0x 的物理地址。 存在 0x 中的 booting 代码会配置位于 0x 位置的 DDR 控制器和位于 0x 位置的 SD/MMC 控制器，然后下一步就是把位于 SD 卡中的 boot loader 复制到外部的 DDRam 中，然 后跳转到 boot loader 中的代码继续执行。目前市面上大多数 SoC 都是如此操作的。 通过 这个例子也会更好的把后面的内存管理和一个真实的系统相联系起来， 了解系统的代码是如 何开始执行的。Page 14 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理另外还有一些在运行时需要动态配置 ARM 及其附属硬件所需要的内存，比如配置用于调 试和记录运行状态的一些内存等Page 15 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理第三部分：Linux 内核的物理内存管理 以 ARM 硬件 MMU 的虚拟内存映功能为基础，以上面所说的内存布局为框架，勾勒了 现代 Linux 系统基于 ARM CPU 的内存管理框架。这部分我们从细节上总结 Linux 是如何管理 系统物理内存的。 在第一部分所演进的内存布局的框架下，Linux 内核对内核虚拟空间进行了进一步的细 化，如下图所示：注：此图是基于 3.18 内核的默认配置 一，Vector area。 上图中的 Vector Area 是为 ARM 硬件准备的。事实上 ARMV7 异常向量表 一个有 8 个入口总共需要 32 个字节的空间，在 Linux 预留的这么大的空间里还包括了 一些异常处理代码。Linux 通过在 ARM 直接访问的异常向量处存放的跳转指令使 CPU 进入真正的异常处理函数。 这部分的代码细节不属于内存管理， 但需要内核为其预留一 段空间。关于 Vector 的具体实现，可以参考 entry_armv.S 中的__vectors_start。 二，固定映射区 （Direct Mapping Area， Low memory） 。 顾名思义， 内核用这个预留的空间， 固定地映射了全部或部分物理内存。 为什么需要这个固定映射区？如第一部分所述， 操 作系统在内核空间执行，管理着整个系统的物理内存（接受请求，分配物理页面，配置 内存映射表） 。而操作系统本身有代码段，有数据段等静态映射的需求，也有在运行中 动态地申请内存的需求。 从这个角度操作系统和一个普通的进程是一样的。 我们可以认 为固定映射区包括了内核运行所需要的静态映射和动态映射。 而在上图中所示的动态映 射区，目的并不是为了映射物理内存的。 早期系统的物理内存并不多大，为了方便内核对内存操作和管理，Linux 就把全部 的物理内存全部的映射到了内核空间。 如下图所示， 物理地址和虚拟地址是顺序映射的。 这样在操作系统需要的时候， 直接申请一块物理页面， 而通过偏移量就可以得到虚拟地 址， 相反通过虚拟地址也可以很方便的得到其对应的物理地址。 这样针对内核自己所有 使用的内存不需要动态映射， 但内存映射之后并不代表被使用了， 内存是否被使用是通 过其他数据记录的。Page 16 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理有了固定映射区后的，内存的管理有如下特点： 1， 在内核动态使用内存时，不需要进行映射和解除映射的操作，因为在固定映射区的 映射是始终存在的。内核在使用某块物理内存时，虽然不需要操作映射表，但需要 记录这块内存已经被使用，也就是只管理内存申请和释放就可以了。 2， 如果用户空间申请的物理内存位于固定映射时时，除了记录该物理内存被使用外， 还需要把这块内存映射到用户空间，以确保应用程序可以通过用户空间地址访问这 块内存。如下图所示，同一块物理内存会被映射两次3， 早期系统硬件的内存容量都比较小，内核空间的固定映射区足够固定地映射全部的 物理内存。 但随着内存的成本下降和系统对内存需求量的增大， 内存变得越来越大， 逐渐地物理内存尺寸超过了固定映射区的尺寸限制。 内核的虚拟空间一共只有 1G， 当物理内存超过 1G 后，就算全部的内核空间全部用来进行固定映射，也没办法满 足需要。在 3.18 kernel 的默认配置下，Linux 用来固定映射的空间为 760M 左右。也 就是说内核只能直接地，固定地映射 760M 的物理内存。在其他老一点的版本中， 默认定义的这段内存区间是 896M。虽然可以把内核分界的 0xC0000000 地址下调， 但应用程序所需要的空间也在变大，所以能调整的空间也不大。而 32 位系统，CPU 总共能支持的物理内存有 4G， 内核是没办法把 CPU 所能支持的所有物理内存全部 映射到内核空间的。所以这段区域只要能保证内核运行所必需要的内存就行了，这 个需要包括如内核代码和数据段的静态内存以及运行中需要的动态内存。 三，IO remapping area 是一个和固定映射区域类似的预留空间， 但是目的不是为了映射物理 内存而是用来映射一些 CPU 需要访问和控制的外部设备和控制器的。 当 MMU 使能之后， 所有 CPU 的访问都必须是基于虚拟地址的，况且外设的驱动程序通常都在内核空间， 所以这些硬件控制器必须要映射到内核空间。 为了节省内核的虚拟空间或许可以把驱动 移到应用程序中， 事实上是有些驱动就是在用户空间的， 但在用户空间的驱动的效率比 较低下，因为它所提供的功能和服务需要 IPC。因此大部分的驱动还是运行在内核空间 的， 为此内核预留了 IO remapping area 用来映射驱动需要访问的外部设备， 比如可以把 物理地址为 0x 的 SD/MMC 控制器，映射到 0xF0001000 的虚拟地址上，这样 SD/MMC 驱动就可以通过 0xF0001000 的虚拟地址来访问和控制 SD/MMC 控制器。 当然， 程序或驱动也可以映射任意的物理内存到这个区域， 但这个区间地址范围有限， 默认为 240M，使用需慎重。 四，在内核空间里， 除了上述的 3 个主要区域， 为了某些特殊目的， 还预留一些其他的空间。Page 17 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理这些空间不大， 主要集中在 0xFF000000 到 0xFFFFFFFF 之间的 16M 空间， 比如为了 TCM 预留的空间等。 五，上图还有一个在用户空间， 0xC0000000 地址下面， 预留的空间， 叫做 Kernel Mapping Area， 其大小是 2M。 这个地址虽然小于 0xC0000000， 表面属于用户空间的地址范围但它是 为了内核代码程序使用的。当 CONFIG_HIGHMEM 配置的时候，这个区域才有效。后面 会介绍这个区间的作用。 ARM 的内存映射表，如我们在上一部分中的讨论，通常都是以 section 直接映射一块大 的内存或以 4K 映射一块小内存的。提到的固定映射区就适合以 section 来映射以 M 为单位 的物理内存。因为： 1， 所映射的物理内存具有相同的访问权限，以 Section 来映射可以节省二级映射表所占的 内存。 2， 这个映射在内核空间是固定的， 不需要解除， 也不需要动态地通过映射分解成更小的块。 3， 内核空间的内存在动态申请时也是以 4K 大小为单位来记录的，这样在内存使用上和 4K 大小的块管理时一致的。 除了在固定映射区外， 所有的虚拟地址的映射都是以 4K 为单位的。 虽然映射时的物理 内存有大小的区别，但在管理上内核把所有的物理内存划分成 4K 大小均等的物理页，包括 固定映射和非固定映射的内存。 内核并不是通过映射与否来判断物理页是否被使用， 而是使 用一个叫做页面结构（struct page）的元数据来管理每个物理页面的。每个物理页对应一个 页面结构，如下图所示：这里所示的是一片连续内存时的示意图。大小为 N*4K 的物理内存，对应有 N 个页面结构。 这 N 个页面结构一般也是连续的，可以看做是一个页面结构数组，相对应数组的索引就是 从 0 到 N-1。 实际物理内存可以是不连续的， 那么针对不连续的内存， 可以用不连续的页面结构数组。 例如，如果有两片内存，可以用两个互相独立的页面结构数组来分别管理一片物理内存。内 核支持这样的配置，但需要定义 CONFIG_SPARSEMEM。默认针对不连续的物理内存，内核 还是像只有一片连续物理内存一样，使用一片连续的页面结构数组来管理，如下图：start1 end10Start 20Page 18 刘永生 微信: eternalvita 邮箱：end2基于 ARM CPU 的 Linux 物理内存管理上图中： 1. end2 & start2 & end1 & start1 2. 3. 在连续的页面结构数组中，一个有（end2-start1）/4K 个元素 红色的页面结构代表没有对应物理内存的页面结构，一共有(start2-end1)/4K 个元素这样做的好处是处理简单效率也高些， 而对应的副作用就是会浪费一块内存， 因为在没有物 理内存的区域（start2-end1）处依然有页面结构，如上图的红色块所示。 在有的系统中，内存不但是不不连续的，在访问速度上也有很大的差异。例如，在某 个系统中有两个内存控制器，一个是 DDR2，一个是 DDR3 的。DDR2 的控制器上的内存的频 率是 200M*32 位，而 DDR3 上的可以支持到 800M*32 位。那么在相同的硬件访问效率下， CPU 对于访问这两块内存上所付出的时间代价是 1:4。这种内存结构叫做非一致性内存，因 此对其的分配策略也应该有差别。Linux 内核对这种非一致性内存提供了支持，但需要定义 CONFIG_NEED_MULTIPLE_NODES，这样对应系统中会有多个内存节点（pglist_data） ，分别用 来管理速度不一致的内存。 下面的讨论不包含这种情况， 大多数系统中的内存都是访问一致 的，尤其在嵌入式系统中更不多见，也就只有一个 pglist_data 的实例。 我 们 以 内 核 默 认 的 配 置 为 例 ， 在 没 有 定 义 CONFIG_SPARSEMEM 和 CONFIG_NEED_MULTIPLE_NODES 的情况下， 内核中只有一个 pglist_data 实例并且用一块连 续的页面结构数组来管理所有的物理内存， 而无论物理内存是否是连续的。 其中页面结构数 组所占的物理页面数量为 页面数量 = (sizeof(struct page)*N + 4K -1)/4K 这些页面的数量虽然是和系统中物理内存总量有关的，但所占的比例是不变的，比例为 sizeof(struct page)/4K *100%，对于默认的情况下，sizeof(struct page)=32bytes, 所以内核中用 于物理页面管理所使用的元数据大约为 0.8%左右。 另 外 如 果 系 统 的 物 理 内 存 超 过 了 760M 不 能 被 固 定 映 射 时 ， 那 么 就 应 该 配 置 CONFIG_HIGHMEM。配置 CONFIG_HIGHMEM 就是为了解决使用大物理内存时不能全部映射 到固定区域的问题。如果系统中的物理内存总量超过了 760M，那么内核就把在 760M 以下 的内存叫做 Normal Memory，也叫 Low Memory，而把超过 760 的部分叫做 High Memory。 如下图所示：Page 19 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理如上图所示，如果系统中的内存太大超过了固定区域的限制， 那么 Linux 内核就只映 射 760M 的物理内存到固定映射区，而剩下的超出部分的物理内存保持未映射状态。当为内 核操作请求物理页面时，如果 NORMAL 区间没有可用的物理页面，则返回失败。如果有， 则把页面结构的_count（做为物理页面的引用次数）设置为 1，表示这个页面结构所代表的 物理页面被使用了。 然后内核不需要把它映射到其他地址， 而直接使用固定映射的虚拟地址 就可以访问这个物理内存了。 对于在 Normal memory 中的物理内存，而又被分配到内核空间使用，那么内核可以通 过_va(physical address)直接得到某个物理地址对应的虚拟地址， 相对应也可以通过_pa(virtual address)来得到虚拟地址对应物理地址。_va 和_pa 实现也比较简单，假如系统中的物理内存 的起始地址是 0x0，而内核的起始虚拟地址是 0xC0000000，就可以通过下面的代码来访问 0x2000 的物理内存。 unsigned int *virtual_address = 0x000000; //_va 的实现与此类似 *virtual_address = 0x80; 内核在以页面（4K）划分物理内存后，系统中的物理内存，页面结构和内核空间的虚拟地址 的关系如下图所示：1， 上图中的物理内存连续并且大小超过了 760M。图中的绿色虚线是表示连续的低 760M 物理内存被连续的映射在固定区域。虽然 HIGHMEM 区的物理内存没有被映 射，但内核为其分配了页面结构。页面结构数组是连续的，并且一定位于在固定映 射区间的某个位置如图中红色虚线所示，而无论被管理的物理内存有没有被固定映 射，这很重要。这也说明在 HIGHMEM 中的内存虽然没被固定地映射，但内核需要 对其管理。 2， 内核把这个连续的页面结构数组保存在全局变量 mem_map 中。在管理中，可以很 方便的通过页面结构的索引计算出对应的物理内存，也可以通过物理内存地址很容 易地找到对应的页面结构。例如，在物理内存的物理地址起始为 0x0 的系统中，物 理地址 0x2000，对应的页面结构是： struct page *page = mem_map + (0x2000&&12)。相应地，某个页面结构 page 所Page 20 刘永生 微信: eternalvita 邮箱：内核空间基于 ARM CPU 的 Linux 物理内存管理管理的物理内存区间为：[（page-mem_map）&&12, +4K） 。其中，(物理地址&&12) 的值，也被称为 pfn。内核代码，凡是名字中 pfn 都是指(物理地址&&12)，也叫物理 页面索引。 同 时 这 个 页 面 结 构 数 组 也 被 保 存 在 内 存 节 点 （ pglist_data ） 的 成 员 变 量 node_mem_map 中，这样对于有多节点（存在访问不一致的内存时）的系统，很容 易定位不同节点中的页面和页面结构，因为不同节点有独立的页面结构来管理所覆 盖的物理页面。 3， 页面结构（struct page）黄色方框中的数字 0，1，2，是页面结构的索引。如果系统 的物理内存的物理地址是 0x0 开始的，那么这个页面结构的索引就和页面索引（物 理地址&&12）相等。如果不是从 0x0 开始的，那么页面结构索引和物理页面索引的 关系为： 某个页面结构索引 page_idx = (某个物理地址-物理内存的起始地址)&&12。 没有被固定映射的物理内存，会在系统运行过程中，根据应用程序的申请映射到用户空间， 而不会在内核空间使用（除了临时使用或特殊情况下的个别物理页面） ，如下如所示：0x固定映射的 物理内存 NORMAL4K 4K 4K 4K 4K 4K+760M连续的物 理内存 N*4K没被固定映 射的物理内 存 HIGHMEM4K 4K 4K 4K 4K4K连续的页面结构 数组 struct page[N] mem_map=pglist_data&node_mem_map0 1 2N1HIMEM 映射用户空间内核空间Virtual memory用户空间0xCM固定映 射区页面结构数组在 固定映射区的位 置0x1， 上图中的蓝色虚线表示 HIGHMEM 内的物理内存会被映射到用户空间。用户空间的大小 是 3G，因为进程的用户空间是彼此独立，那么整个可以映射的物理内存会有‘进程数 *3G’ 。 这样 32 位的系统就支持高达 4G 的物理内存就没问题了， 因此内核总是首先使用 HIGHMEM 区的物理内存来响应来自用户空间的请求。 2， 内核通过进程的内存映射表可以把在 HIGHMEM 中物理内存映射到用户空间， 但如 果内核代码要访问这部分内存就成了问题， 因为内核空间默认只映射了 NORMAL 中的物 理内存。 举个这样的例子， 假如进程 A 新 Fork 出来的线程 A1 在调用 exec 来执行一个新 程序 B 时，内核代码要为新的可执行程序配置位于用户空间内的运行环境，比如传入的 参数和环境变量等。内核首先要申请一块物理内存，然后把这个新申请的物理内存映射 到即将要运行的新程序 B 的用户空间里，也就是添加到进序 B 的映射表中。完成映射表 配置后，运行在线程 A1 映射表下的内核代码并不能直接访问这块内存，因为它只存在 于进程 B 的映射表中，而进程 B 的映射表不是当前 ARM 使用的映射表，ARM 正在使用 进程 A 的映射表。假如这个新申请的物理内存位于固定映射区，那么内核可以通过_va （page）得到所对应的在固定映射区的虚拟地址。但如上第一条所说，内核总是优先为Page 21 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理用户空间的虚拟地址分配 HIGHMEM 区间的物理内存，而 HIGHMEM 区间的内存在内核 空间是没有映射的。此时内核需要临时把这块物理内存映射到内核空间，写入参数后再 解除这个临时映射。为实现这个目的，内核可以使用 VM 区来完成这个临时映射。但内 核实际上使用了一个扩展的区域来完成这个临时映射，就是上面提到的 KMA 区。KMA 虽然在内核分界地址中处在用户空间（位于 0xC0000000 以下） ，但它完全是为内核使用 的。内核为提高效率，在 KMA 区做了一些额外的预处理来提高效率。总结一下 KMA 区 ? KMA 是一片位于用户空间， 但完全为内核使用的地址区域， 也就是 KMA 是在 init_mm 的映射表中映射和覆盖的。 ? KMA 中的映射都是临时的。目的是为了使内核能访问 HIGHMEM 区的物理内存，因 为 HIGHMEM 内的物理内存在内核空间是没有映射或固定映射的。 ? KMA 有 2M 虚拟空间，内核为这 1M 空间的映射表预先分配了二级映射表，并把在 2M 范 围 内 的 二 级 映 射 表 保 存 在 pkmap_page_table ， 用 static int pkmap_count[LAST_PKMAP]来记录相应表项被使用与否。 其中 LAST_PKMAP = 2M/4K = 512。因为二级映射表已经分配好了，在运行中如果要映射某个在 HIGHMEM 中的 页面，可以使用如下操作完成映射： pkmap_page_table[last_pkmap_nr] = mk_pte(page, kmap_prot)；// last_pkmap_nr 是 在[0, 511]之间的某个数值。 注：事实上这里为啥是 2M 还和内核用 3 级来管理映射表有关，而 ARM 的映射表 是 2 级。 内核可以通过物理内存的地址本身就可以很容易的区分开某个物理内存是属于 NORMAL 部分，还是 HIGHMEM 部分。由于这两部分的管理是有区别的，内核为了区分和管理这两部 分内存，引入了 ZONE 的概念。针对上面所示意的系统，内核就把它分为两个 ZONE，一个 叫做 NORMAL ZONE，用来管理属于 NORMAL 内的物理内存，另一个叫做 HIGHMEM ZONE， 用来管理属于 HIGHMEM 内的物理内存。如下图所示：1， 上图中的两个 ZONE，分别管理固定映射区的内存和 HIGHMEM 的内存。内核以 ZONE 为 单位来管理物理内存。 某个具体的物理内存页面， 必须排它地属于某个 ZONE。 每个 ZONE 的内存管理过程也是互相独立的。 2， 内核不会跨 ZONE 来分配和回收内存。 例如， 某次操作请求两个页面， 内核不会从 NORMAL ZONE 返回一个，从 HIGHMEM ZONE 返回一个页面。 3， ZONE 的数据和属性记录在 pglist_data 中的 node_zones，Page 22 刘永生 微信: eternalvita 邮箱：内核空间基于 ARM CPU 的 Linux 物理内存管理typedef strcut pglist_data{ struct zone node_zones[MAX_NR_ZONES]; ...... …… struct page *node_mem_ …… } pg_data_t; 4， 除了 NORMAL 和 HIGHMEM 之外， 内核还支持更多的 ZONE 划分。 比如为了 DMA 控制器 使用而设置的 DMA ZONE（DMA 需要连续的物理地址，有的 DMA 控制器对访问的内存 有限制，比如只能访问低 128M 的物理内存，所以设置一个单独的 ZONE 来管理，也便 于预留 DMA 需要的内存） ， 为支持移动内存（可动态插拔）而设置的 MOVABLE ZONE。 上面的 MAX_NR_ZONES 等于多少，就代表系统把物理内存分成了几个 ZONE 来管理。但 无论多少个 ZONE，每个 ZONE 的管理始终是独立和分开的，所管理的物理页面在 ZONE 之间也没有重叠和重复。 5， 在 ZONE 管 理 中 ， 内 核 通 过 索 引 来 找 到 相 应 的 ZONE 。 NORMAL ZONE 的 索 引 为 ZONE_NORMAL 而 ZONE_HIGHMEM 是 HIGHMEM ZONE 的索引。内核有时也通过 ZONE 的索引来表示所管里的 ZONE。如下图所示，6， 由上图可以看出，每个物理页面都是在 ZONE 管理下的。所以在页面结构中有个成员变 量记录所对应的 ZONE 索引（通过 set_page_zone()） ，这样通过某个页面结构能够快速的 找到所对应的 ZONE 索引 （通过 page_zone()） 。 而 ZONE 索引本身就标称了 ZONE_NORMAL 还是 ZONE_HIGHMEM ，从而就可以知道当前的物理页面是属于固定映射区，还是 HIGHMEM 区了。 有了 ZONE 之后，每个 ZONE 都会管理一片物理内存。有物理内存请求时，内核会通过 对应的 ZONE 来实现查找和分配的。那么 ZONE 是如何完成查找和分配的呢？为此内核引入 了 buddy 系统。Buddy 系统是建立在 ZONE 基础上来分配和回收内存的，相应地每个 ZONE 分别有自己独立的 buddy 系统，如下图所示。 buddy 系统简单讲就是一个链表头数组， 数组中的每个表项作为一个独立链表的表头来 记录系统中未被分配的物理内存。而这个数组是如何管理和记录内存的，就是 buddy 系统 的运作方式。 Buddy 的数组就是在 ZONE 结构中定义的 struct free_area free_area[MAX_ORDER]。Page 23 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理Buddy 系统中主要有两个操作，获得页面（get page）和归还页面（free page） 。举个例 子说明 Buddy 系统是如何工作的，如下图：上图是 buddy 系统的简化图 1， 在这个简化的例子中，系统中有 16M 的内存，并且在创建 buddy 系统时，所有的内存 都是未分配的（freed） 。 注意，事实上，系统在创建 buddy 系统时，不可能全部内存都 是未分配的，内核所需要的静态内存部分是必须要使用的，还有一些其他内核数据所占 用的内存。 2， 绿色方块是链表头数组，其中的数字即代表其索引，也代表 order。这个索引的另外一 个含义就是链入此链表头的页面是有(1&&order)个连续可用的物理页面的首页面。 例如 上图中， 连接入 order 为 10 的页面分别为 page 0， page 1024， page2048 和 page3072。 其中 page 0 表示不知 page #0 是可用的，它表示的是从第 0 个物理页面到到第 1023 的 物理页面都是没被分配，可用的。上图是示意，而真正是以如下图方式链接的。Page 24 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理在链表中，只记录了连续可用区间的首页面，通过（struct page-&lru）互相链接。上图 表示 [0, 1024), [), [), [）的物理页面是有效可供分配的。 3， Linux 系统中，默认的 MAX_ORDER 是 11，最大的索引是 10，所以支持链入最大连续内 存有 2&&10 个页面。通过 buddy 系统只能分配最大为 4M 的连续物理内存。如果需要更 大的物理内存，可以通过预留的方式。 4， 此例子中，除了 order 为 10 链表外，都是空，即系统中所有的可用内存全部链接在最高 order 的链表中。 Buddy 系统为了减少碎片的机制，总是试图把可用的物理内存链入到高级 order 中。而当分 配时，总是试图从低级 order 中申请。 具体来说当需要物理页面时，系统通过查找 buddy 系统中的数组来找到最小连续可用 的物理页面并把该物理页面从链表中移除。通过一个例子来说明是如何操作的。 例如有个请求，需要从系统中获取大小为 2M 的连续的物理内存。先把 2M 转成页面数， 2M&&12，也就是需要 512（0x）个连续的物理页面。 Buddy 系统以如下的方式开始工作， 1， 因为 512=1&&9， 本着从最小可用 order 分配的原则， 所以首先从 order 为 9 的列表查 找。上图中，所有 freed 的页面，全部被链接到了 order 为 10 的列表中，在 order 为 9 的链表中没有可用的物理页面。 2， 通过 index++继续搜索下一个的链表头，, 即 order 为（9+1）=10 的链表。此时链表不为 空，则一定存在满足请求大小的页面，搜索结束，并把该物理页面从 index（order）为 10 的表头中移除。 3， 找到的可连续使用的物理页面是 page[0] C page[1023] = 4M, 大于所请求的空间 2M，还 有 2M 多余的物理页面。内核需在返回可用的 2M 物理内存后还要把多余的页面返回给 buddy 系统， 也就是要把多出的 2M 页面 （page[512] C page[1023] ） 重新加入 buddy 列 表。Buddy 系统的结构如下图所示。再复杂一点，在此系统的基础上继续请求一个 4K 物理内存，也就是一个物理页面。继 续上面的例子， 1， 因为是请求一个页面， 所以所要申请的 order 为 0。 从 order 为 0 的链表开始搜索。Page 25 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理没有可用的页面，继续搜索高级 order 的链表 order 为 0+1 的列表。也没有，重复 这个过程，直到在 order==9 的链表中，才发现有可用的页面，停止搜索，把发现页 面从链表中移出。 2， 因为发现的连续可用的物理页面是 512 个，而需要的是一个页面。此时需要把多余 的 511 个页面需要返还给 buddy 系统。 3， 由于 511 是小于 512（order 为 9） ，而大于 256（256=1&&8， order 为 8） ， 所以从 order=8 的列表开始回添。返还了 256（1&&8）个页面后，还有 255 个页面多余。继 续回添多余的页面到 order 为 7（1&&7 个页面）的链表。返还了 128 个页面后，还 有 127 个页面多余。 重复这个过程直到把所有未用的页面都回添到 buddy 链表之后， buddy 系统的链表结构如下图所示： 注意，在内核的实际操作中，order 为 0 的 page 并不会直接加入到 buddy list，而是 会先加入 pcp 列表中，在多核系统中，每个 CPU 都有一个 PCP 链表来保存 order 为 0 的页面。当 PCP 中的页面超过一定数量时，内核才会把单个未被分配的页面加入 到 order 为 0 的链表中。 上面的操作后，Buddy 系统结果如下图所示回收页面是相反的过程，当页面不需要而被使用者释放时，内核就将其加入到 buddy 链 表。释放的页面可以是单个页，也可以是一片连续的页面。如果是一片连续的页面，那么必 须满足如下条件 1， 首页面的 page_idx 必须是(1&&order)对齐的。例如，如果要释放的页面有 32(1&&5) 个，那么首页面的 page_idx 必须满足 page_idx & (1&&5 -1) ==0 。 (page_idx = physical_address&&12)。 2， 页面的数量必须是 (1&&order)个。例如，如果有 32 个页面，那么就可以一次性的 加入到 buddy 中索引为 5 的链表中。但如果有 31 个页面，则不能一次回收，要分 成多次加入 buddy 系统。 回收页面时，buddy 系统不会直接把要释放的页面链接到相应 order 的链表中，而是会 先试图与保存在 buddy 系统相同 order 链表中的物理页进行合并。如果不能合并，则直接链 入。如果能够合并，则先合并，然后更新到（order++） ，继续判断是否能与 order++链表上 的页面合并。重复这个过程直到超过最大 order 或没有发现可继续合并的物理页。这个能够Page 26 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理与其合并的页面，叫做 buddy。这也是 buddy 系统称呼的来源。但 buddy 要满足如下条件： 1， Buddy 页面与当前的页面是连续的，合并后连续可用的物理页变成（1&&(order+1)） 个，并且 2， 合并后的页面不能跨（1&&(order+1)）的边界，否则就不是 buddy 页面。比如第 32 个页面到第 63 个页面[32, 63]，总共有 32 个连续页面，满足 order 5 的要求。那么 它的伙伴是[0, 31]， 而不是[64, 95]。 虽然[64, 95]和[32, 63] 可组成 64 个连续的页面， 但[32, 95]跨过了 64（order 为 6）的界限。 3， 可合并的 Buddy 页面必须与当前的页面属于同一个 ZONE，因为 buddy 系统不能跨 ZONE 存在。并且还要存在于 buddy 数组中（未被使用状态） 。 具体的合并过程，可参见后面的代码分析部分。 使用 buddy 系统管理物理内存的好处是： 1， 效率高。如果系统中存在可用的连续物理内存，找到满足条件的搜索路径最大为 MAX_ORDER， 默认为 11。 2， 碎片管理。 在页面回收的时候会做合并处理， 合并处理最大复杂度也是 MAX_ORDER。 也有缺点，比如最多只能分配 4M 的物理内存，虽然说 4M 对于一般应用足够了。当然 可以把 MAX_ORDER 改为更大的值， 这样就能支持更大的物理内存分配， 但还是有限制。 注，虽然能尽可能的降低碎片，但不能从根本上解决碎片的问题，因为在分配时不能控 制被分配出去的物理内存什么时候会被释放，那么在释放内存时就无法控制被释放内存 的伙伴是否被使用和什么时候被释放。解决碎片最好的办法是内存迁移，这样才能保证 系统中没有碎片，但耗时长，效率低。 上述的 ZONE 和 buddy 系统解决了内核如何分配和回收物理内存。 如果分配出去的物理 内存是在内核空间使用，则从 NORMAL ZONE 的 buddy 系统开始查找，并且不需要额外的内 存映射，因为在 NORMAL ZONE 中的物理内存已经在系统初始化时被固定的映射过了。如果 分配的物理内存是在用户空间使用的， 则从 HIGHMEM ZONE 的 buddy 系统来申请。 如果 buddy 系统没有合适，内核会继续在 NORMAL ZONE 的 buddy 系统中搜索，找到后把该物理页面映 射到申请该内存的进程的用户空间。 在 Linux 上说，基本的调度单位是线程。对 CPU 来说线程和进程没有区别（或者进程只 是一个逻辑的概念，而线程才是 CPU 的执行主体） ，那么对于内存来说，二者的区别就是进 程有自己的内存映射表，而线程是共享映射表。在同一进程中，所有的线程都是共享同一个 内存映射表的。 这才是进程和线程的最本质的区别。 如果不同线程拥有相同的内存映射表， 就可以被认为它们属于同一个进程（内核线程除外，内核线程也没有自己的映射表，它们在 事实共享 Init 进程的映射表，或者也可以认为内核线程同属于内核进程） 。系统是按照进程 来管理映射表的， 也就是系统中每个进程都有自己的内存映射表。 对于属于不同进程的线程， 因为映射表不同，通信需要 IPC 而不能互相直接访问。 按照映射表的使用方式，Linux 系统中的进程分为两类： 1， 应用进程。系统中的应用进程有很多，每一个可执行程序或脚本在执行过程中，都是进 程。每个进程都有自己的内存映射表，应用进程所属的内存映射表负责映射用户空间的 虚拟地址，包括代码段，数据段和堆栈。代码所允许访问的地址必须在该进程所属的内 存映射表中有映射，否则 CPU 会发出异常。进程的映射表保存在 task_struct 结构中的 mm 中，通过调用 fork 时指定 CLONE_VM 标志可以在线程间共享这个 mm。 2， 内核进程。内核进程只有一个，就是 init_task，相应地，它也有属于自己的映射表保存Page 27 刘永生 微信: eternalvita 邮箱：基于 ARM CPU 的 Linux 物理内存管理在 init_mm 中。 内核线程的 mm 为 NULL，隐形地共享了内核的映射表。同时，内核的 映射表所覆盖的内核空间，被所有进程隐形地共享。隐形的意思是在进程的结构体中并 没有哪个成员变量指向内核的 init_mm 或内核的映射表。 内存映射表在内核中也叫页表 （page table） ， 并且同时使用三级映射关系来管理映射表， 如下图所示pte pmd Pmd[0] Pte[0]Pte[j-1] Pgd[0] Pmd[M-1]pte pte Pte[0] pmd Pmd[0] Pte[j-1] Pgd[N-1] Pmd[M-1] Pte[j-1] Pte[0]pte Pte[0]Pte[j-1]而 arm 的映射表是二级，如我们之前所述二级页表 一级页表 TTBR0 Section[0] Section[1] Section[2] …... …... …... ….