8.html

linux 系统学习

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (!tmp || tmp-&gt;start &gt; end) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;sibling = tmp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *p = new;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;parent = root;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return NULL;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p = &amp;tmp-&gt;sibling;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (tmp-&gt;end &lt; start)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; continue;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return tmp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>
}<p>
<p>
　　对函数的NOTE：<p>
　　①前三个if语句判断new所描述的资源范围是否被包含在root内，以及是否是一段有效的资源（因为end必须大于start）。否则就返回root指针，表示与根结点相冲突。<p>
　　②接下来用一个for循环遍历根节点root的child链表，以便检查是否有资源冲突，并将new插入到child链表中的合适位置（child链表是以I/O资源物理地址从低到高的顺序排列的）。为此，它用tmp指针指向当前正被扫描的resource结构，用指针p指向前一个resource结构的sibling指针成员变量，p的初始值为指向root－&gt;sibling。For循环体的执行步骤如下：<p>
　　l 让tmp指向当前正被扫描的resource结构（tmp＝*p）。<p>
　　l 判断tmp指针是否为空（tmp指针为空说明已经遍历完整个child链表），或者当前被扫描节点的起始位置start是否比new的结束位置end还要大。只要这两个条件之一成立的话，就说明没有资源冲突，于是就可以把new链入child链表中：①设置new的sibling指针指向当前正被扫描的节点tmp（new-&gt;sibling=tmp）；②当前节点tmp的前一个兄弟节点的sibling指针被修改为指向new这个节点（*p=new）；③将new的parent指针设置为指向root。然后函数就可以返回了（返回值NULL表示没有资源冲突）。<p>
　　l 如果上述两个条件都不成立，这说明当前被扫描节点的资源域有可能与new相冲突（实际上就是两个闭区间有交集），因此需要进一步判断。为此它首先修改指针p，让它指向tmp-&gt;sibling，以便于继续扫描child链表。然后，判断tmp-&gt;end是否小于new-&gt;start，如果小于，则说明当前节点tmp和new没有资源冲突，因此执行continue语句，继续向下扫描child链表。否则，如果tmp-&gt;end大于或等于new-&gt;start，则说明tmp-&gt;[start,end]和new-&gt;[start,end]之间有交集。所以返回当前节点的指针tmp，表示发生资源冲突。<p>
　　3．2．2 资源的释放<p>
　　函数release_resource()用于实现I/O资源的释放。该函数只有一个参数——即指针old，它指向所要释放的资源。起源代码如下：<p>
<br>
int release_resource(struct resource *old)<br>
{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int retval;<p>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; write_lock(&amp;resource_lock);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; retval = __release_resource(old);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; write_unlock(&amp;resource_lock);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return retval;<br>
}<p>
<p>
　　可以看出，它实际上通过调用__release_resource()这个内部静态函数来完成实际的资源释放工作。函数__release_resource()的主要任务就是将资源区域old（如果已经存在的话）从其父资源的child链表重摘除，它的源代码如下：<p>
<br>
static int __release_resource(struct resource *old)<br>
{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct resource *tmp, **p;<p>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p = &amp;old-&gt;parent-&gt;child;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (;;) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp = *p;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (!tmp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (tmp == old) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *p = tmp-&gt;sibling;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; old-&gt;parent = NULL;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 0;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p = &amp;tmp-&gt;sibling;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return -EINVAL;<br>
}<p>
<p>
　　对上述函数代码的NOTE如下：<p>
　　同函数__request_resource()相类似，该函数也是通过一个for循环来遍历父资源的child链表。为此，它让tmp指针指向当前被扫描的资源，而指针p则指向当前节点的前一个节点的sibling成员（p的初始值为指向父资源的child指针）。循环体的步骤如下：<p>
　　①首先，让tmp指针指向当前被扫描的节点（tmp＝*p）。<p>
　　②如果tmp指针为空，说明已经遍历完整个child链表，因此执行break语句推出for循环。由于在遍历过程中没有在child链表中找到参数old所指定的资源节点，因此最后返回错误值－EINVAL，表示参数old是一个无效的值。<p>
　　③接下来，判断当前被扫描节点是否就是参数old所指定的资源节点。如果是，那就将old从child链表中去除，也即让当前结点tmp的前一个兄弟节点的sibling指针指向tmp的下一个节点，然后将old－&gt;parent指针设置为NULL。最后返回0值表示执行成功。<p>
　　④如果当前被扫描节点不是资源old，那就继续扫描child链表中的下一个元素。因此将指针p指向tmp－&gt;sibling成员。<p>
　　3．2．3 检查资源是否已被占用，<p>
　　函数check_resource()用于实现检查某一段I/O资源是否已被占用。其源代码如下：<p>
<br>
int check_resource(struct resource *root, unsigned long start, unsigned long len)<br>
{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct resource *conflict, tmp;<p>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp.start = start;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp.end = start + len - 1;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; write_lock(&amp;resource_lock);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; conflict = __request_resource(root, &amp;tmp);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (!conflict)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; __release_resource(&amp;tmp);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; write_unlock(&amp;resource_lock);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return conflict ? -EBUSY : 0;<br>
}<p>
<p>
　　对该函数的NOTE如下：<p>
　　①构造一个临时资源tmp，表示所要检查的资源[start,start+end-1]。<p>
　　②调用__request_resource()函数在根节点root申请tmp所表示的资源。如果tmp所描述的资源还被人使用，则该函数返回NULL，否则返回非空指针。因此接下来在conflict为NULL的情况下，调用__release_resource()将刚刚申请的资源释放掉。<p>
　　③最后根据conflict是否为NULL，返回－EBUSY或0值。<p>
　　3．2．4 寻找可用资源<p>
　　函数find_resource()用于在一颗资源树中寻找未被使用的、且满足给定条件的（也即资源长度大小为size，且在[min,max]区间内）的资源。其函数源代码如下：<p>
<br>
/*<br>
 * Find empty slot in the resource tree given range and alignment.<br>
 */<br>
static int find_resource(struct resource *root, struct resource *new,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; unsigned long size,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; unsigned long min, unsigned long max,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; unsigned long align,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; void (*alignf)(void *, struct resource *, unsigned long),<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; void *alignf_data)<br>
{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct resource *this = root-&gt;child;<p>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;start = root-&gt;start;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for(;;) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (this)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;end = this-&gt;start;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;end = root-&gt;end;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (new-&gt;start &lt; min)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;start = min;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (new-&gt;end &gt; max)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;end = max;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;start = (new-&gt;start + align - 1) &amp; ~(align - 1);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (alignf)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; alignf(alignf_data, new, size);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (new-&gt;start &lt; new-&gt;end &amp;&amp; new-&gt;end - new-&gt;start + 1 &gt;= size)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;end = new-&gt;start + size - 1;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 0;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (!this)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new-&gt;start = this-&gt;end + 1;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; this = this-&gt;sibling;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return -EBUSY;<br>
}<p>
<p>
　　对该函数的NOTE如下：<p>
　　同样，该函数也要遍历root的child链表，以寻找未被使用的资源空洞。为此，它让this指针表示当前正被扫描的子资源节点，其初始值等于root-&gt;child，即指向child链表中的第一个节点，并让new-&gt;start的初始值等于root-&gt;start，然后用一个for循环开始扫描child链表，对于每一个被扫描的节点，循环体执行如下操作：<p>
　　①首先，判断this指针是否为NULL。如果不为空，就让new-&gt;end等于this-&gt;start，也即让资源new表示当前资源节点this前面那一段未使用的资源区间。<p>
　　②如果this指针为空，那就让new-&gt;end等于root-&gt;end。这有两层意思：第一种情况就是根结点的child指针为NULL（即根节点没有任何子资源）。因此此时先暂时将new-&gt;end放到最大。第二种情况就是已经遍历完整个child链表，所以此时就让new表示最后一个子资源后面那一段未使用的资源区间。<p>
　　③根据参数min和max修正new-&gt;[start,end]的值，以使资源new被包含在[min,max]区域内。<p>
　　④接下来进行对齐操作。<p>
　　⑤然后，判断经过上述这些步骤所形成的资源区域new是否是一段有效的资源（end必须大于或等于start），而且资源区域的长度满足size参数的要求（end－start＋1&gt;=size）。如果这两个条件均满足，则说明我们已经找到了一段满足条件的资源空洞。因此在对new-&gt;end的值进行修正后，然后就可以返回了（返回值0表示成功）。<p>