&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>　　對(duì)函數(shù)的NOTE：<p>　　①前三個(gè)if語(yǔ)句判斷new所描述的資源范圍是否被包含在root內(nèi)，以及是否是一段有效的資源（因?yàn)閑nd必須大于start）。否則就返回root指針，表示與根結(jié)點(diǎn)相沖突。<p>　　②接下來(lái)用一個(gè)for循環(huán)遍歷根節(jié)點(diǎn)root的child鏈表，以便檢查是否有資源沖突，并將new插入到child鏈表中的合適位置（child鏈表是以I/O資源物理地址從低到高的順序排列的）。為此，它用tmp指針指向當(dāng)前正被掃描的resource結(jié)構(gòu)，用指針p指向前一個(gè)resource結(jié)構(gòu)的sibling指針成員變量，p的初始值為指向root－&gt;sibling。For循環(huán)體的執(zhí)行步驟如下：<p>　　l 讓tmp指向當(dāng)前正被掃描的resource結(jié)構(gòu)（tmp＝*p）。<p>　　l 判斷tmp指針是否為空（tmp指針為空說(shuō)明已經(jīng)遍歷完整個(gè)child鏈表），或者當(dāng)前被掃描節(jié)點(diǎn)的起始位置start是否比new的結(jié)束位置end還要大。只要這兩個(gè)條件之一成立的話，就說(shuō)明沒(méi)有資源沖突，于是就可以把new鏈入child鏈表中：①設(shè)置new的sibling指針指向當(dāng)前正被掃描的節(jié)點(diǎn)tmp（new-&gt;sibling=tmp）；②當(dāng)前節(jié)點(diǎn)tmp的前一個(gè)兄弟節(jié)點(diǎn)的sibling指針被修改為指向new這個(gè)節(jié)點(diǎn)（*p=new）；③將new的parent指針設(shè)置為指向root。然后函數(shù)就可以返回了（返回值NULL表示沒(méi)有資源沖突）。<p>　　l 如果上述兩個(gè)條件都不成立，這說(shuō)明當(dāng)前被掃描節(jié)點(diǎn)的資源域有可能與new相沖突（實(shí)際上就是兩個(gè)閉區(qū)間有交集），因此需要進(jìn)一步判斷。為此它首先修改指針p，讓它指向tmp-&gt;sibling，以便于繼續(xù)掃描child鏈表。然后，判斷tmp-&gt;end是否小于new-&gt;start，如果小于，則說(shuō)明當(dāng)前節(jié)點(diǎn)tmp和new沒(méi)有資源沖突，因此執(zhí)行continue語(yǔ)句，繼續(xù)向下掃描child鏈表。否則，如果tmp-&gt;end大于或等于new-&gt;start，則說(shuō)明tmp-&gt;[start,end]和new-&gt;[start,end]之間有交集。所以返回當(dāng)前節(jié)點(diǎn)的指針tmp，表示發(fā)生資源沖突。<p>　　3．2．2 資源的釋放<p>　　函數(shù)release_resource()用于實(shí)現(xiàn)I/O資源的釋放。該函數(shù)只有一個(gè)參數(shù)——即指針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>　　可以看出，它實(shí)際上通過(guò)調(diào)用__release_resource()這個(gè)內(nèi)部靜態(tài)函數(shù)來(lái)完成實(shí)際的資源釋放工作。函數(shù)__release_resource()的主要任務(wù)就是將資源區(qū)域old（如果已經(jīng)存在的話）從其父資源的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>　　對(duì)上述函數(shù)代碼的NOTE如下：<p>　　同函數(shù)__request_resource()相類似，該函數(shù)也是通過(guò)一個(gè)for循環(huán)來(lái)遍歷父資源的child鏈表。為此，它讓tmp指針指向當(dāng)前被掃描的資源，而指針p則指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的sibling成員（p的初始值為指向父資源的child指針）。循環(huán)體的步驟如下：<p>　　①首先，讓tmp指針指向當(dāng)前被掃描的節(jié)點(diǎn)（tmp＝*p）。<p>　　②如果tmp指針為空，說(shuō)明已經(jīng)遍歷完整個(gè)child鏈表，因此執(zhí)行break語(yǔ)句推出for循環(huán)。由于在遍歷過(guò)程中沒(méi)有在child鏈表中找到參數(shù)old所指定的資源節(jié)點(diǎn)，因此最后返回錯(cuò)誤值－EINVAL，表示參數(shù)old是一個(gè)無(wú)效的值。<p>　　③接下來(lái)，判斷當(dāng)前被掃描節(jié)點(diǎn)是否就是參數(shù)old所指定的資源節(jié)點(diǎn)。如果是，那就將old從child鏈表中去除，也即讓當(dāng)前結(jié)點(diǎn)tmp的前一個(gè)兄弟節(jié)點(diǎn)的sibling指針指向tmp的下一個(gè)節(jié)點(diǎn)，然后將old－&gt;parent指針設(shè)置為NULL。最后返回0值表示執(zhí)行成功。<p>　　④如果當(dāng)前被掃描節(jié)點(diǎn)不是資源old，那就繼續(xù)掃描child鏈表中的下一個(gè)元素。因此將指針p指向tmp－&gt;sibling成員。<p>　　3．2．3 檢查資源是否已被占用，<p>　　函數(shù)check_resource()用于實(shí)現(xiàn)檢查某一段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>　　對(duì)該函數(shù)的NOTE如下：<p>　　①構(gòu)造一個(gè)臨時(shí)資源tmp，表示所要檢查的資源[start,start+end-1]。<p>　　②調(diào)用__request_resource()函數(shù)在根節(jié)點(diǎn)root申請(qǐng)tmp所表示的資源。如果tmp所描述的資源還被人使用，則該函數(shù)返回NULL，否則返回非空指針。因此接下來(lái)在conflict為NULL的情況下，調(diào)用__release_resource()將剛剛申請(qǐng)的資源釋放掉。<p>　　③最后根據(jù)conflict是否為NULL，返回－EBUSY或0值。<p>　　3．2．4 尋找可用資源<p>　　函數(shù)find_resource()用于在一顆資源樹(shù)中尋找未被使用的、且滿足給定條件的（也即資源長(zhǎng)度大小為size，且在[min,max]區(qū)間內(nèi)）的資源。其函數(shù)源代碼如下：<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>　　對(duì)該函數(shù)的NOTE如下：<p>　　同樣，該函數(shù)也要遍歷root的child鏈表，以尋找未被使用的資源空洞。為此，它讓this指針表示當(dāng)前正被掃描的子資源節(jié)點(diǎn)，其初始值等于root-&gt;child，即指向child鏈表中的第一個(gè)節(jié)點(diǎn)，并讓new-&gt;start的初始值等于root-&gt;start，然后用一個(gè)for循環(huán)開(kāi)始掃描child鏈表，對(duì)于每一個(gè)被掃描的節(jié)點(diǎn)，循環(huán)體執(zhí)行如下操作：<p>　　①首先，判斷this指針是否為NULL。如果不為空，就讓new-&gt;end等于this-&gt;start，也即讓資源new表示當(dāng)前資源節(jié)點(diǎn)this前面那一段未使用的資源區(qū)間。<p>　　②如果this指針為空，那就讓new-&gt;end等于root-&gt;end。這有兩層意思：第一種情況就是根結(jié)點(diǎn)的child指針為NULL（即根節(jié)點(diǎn)沒(méi)有任何子資源）。因此此時(shí)先暫時(shí)將new-&gt;end放到最大。第二種情況就是已經(jīng)遍歷完整個(gè)child鏈表，所以此時(shí)就讓new表示最后一個(gè)子資源后面那一段未使用的資源區(qū)間。<p>　　③根據(jù)參數(shù)min和max修正new-&gt;[start,end]的值，以使資源new被包含在[min,max]區(qū)域內(nèi)。<p>　　④接下來(lái)進(jìn)行對(duì)齊操作。<p>　　⑤然后，判斷經(jīng)過(guò)上述這些步驟所形成的資源區(qū)域new是否是一段有效的資源（end必須大于或等于start），而且資源區(qū)域的長(zhǎng)度滿足size參數(shù)的要求（end－start＋1&gt;=size）。如果這兩個(gè)條件均滿足，則說(shuō)明我們已經(jīng)找到了一段滿足條件的資源空洞。因此在對(duì)new-&gt;end的值進(jìn)行修正后，然后就可以返回了（返回值0表示成功）。<p>