lab_discussion_1

简析lab2中page组织结构中指针问题

应陈一文gg的邀请简要分析一下lab2中Exercise 2.2链表指针指向理解的问题

前言

在周一写lab2时我遇到了一个指针的问题。如下图，这是一个在listelm前插入elm元素的问题，但我当时并不太理解这部分代码的行为，这主要是由于lab2中的链表的结构设计和我们常见的链表有所不同,导致代码并不是非常易于理解。

关于常见的链表，相信大家在经过数据结构的历练后对于链表的前插问题并不是非常的难以理解，所以我在此就忽略这部分的介绍，将注意力转移到这份代码上。

正文

首先如果当做我们之前学习的链表来理解的话，也不难理解前面两行代码的含义（虽然实际上有一些不同），你会理解为将elm的prev指针指向了listelm的prev指针所指的元素（第一行），然后将elm的next指针指向了listelm（第二行），但紧接着你就会不理解第三行和第四行在干什么了。所以要想真正理解这几行代码，首先我们要看一下lab2中page的体系结构是什么样的。

在lab2实验中，Page是我们用于管理物理内存块的结构体，该结构体包含两部分——一个是"数据域"（pp_ref）,另一个是"指针域"（pp_link）。通过上面的思考题我们知道最终page结构可以简化到以下这种形式：

struct Page{
	struct {
		struct Page *le_next;
		struct Page **le_prev;
	} pp_link;
    u_short pp_ref;
}; 

其中，pp_ref代表着该物理内存块被引用的次数，即有多少个虚拟地址映射到该物理内存块。pp_link中包含两个指针变量——le_next和le_prev，前者是指向后一个Page结构体的指针，后者是指向前一个Page的le_next的指针。

说到这里，大家有没有注意到什么不同,le_prev指针指向的并不是该elm的前一个对象，而是前一个对象的next指针，换言之，prev是一个二级指针。具体而言，该链表实际上是一个双向链表，但和我们常见的双向链表又有区别，该双向链表可以直接通过le_next来访问下一个链表项，但却无法直接访问上一个链表项，因为le_prev仅仅是指向了前一个Page的le_next，换句话说，就是一个指向了"指向自己的指针"的指针。

上图是我在提出疑惑后助教给我解答时画的一张图，在此我就借用这张图介绍一下上面那四行代码，首先第一行是将elm的前向指针指向了listelm的前一个元素的next指针，第二行是将elm的next指针指向后面一个元素,值得一提的是在这种体系定义下只有第二行和原来指针起到的作用相同,而另外三行的含义都已经产生了一些变化。

接下来是第三行*(listelm)->field.le_prev=(elm)，这里我在刚开始理解时理解成了将listelm的前向指针指向elm，但事实上并不是这么理解的，应该是将listelm前向指针所指向的next指针所指的元素改为elm，这句话可能有点绕，拆开说我们先看(listelm)->field.le_prev部分，这个是指向插入前listelm的前一个元素（下文用elmA替代)的next指针，之后用*来获得了该指针指向的元素（即elmA的next指向的值），最后将elmA的next指向的元素改成了elm。这两行看似是对二级指针prev进行操作，但结果而言实际上其实是一个将一级指针指向元素本体的效果。

最后第四行(listelm)->field.le_prev=&LIST_NEXT((elm),field)这一行又是起到了什么作用呢？这一行将listelm的prev指针指向elm的next指针，也是一个将二级指针指向一级指针的操作，到此指针部分就完成了。

后言

这题的破题关键在于正确理解prev指针的作用，而关于为什么要这么设计，微信群里叶gg给出了一个很好的理解，我们在lab2中最后用page结构最终实现的是一个page_list的列表，而如果不使用这种方式将不太好定义头指针，因为头指针并不是一个elm形式的struct。