JFS 文件係統概述及布局分析（四）
B+樹這一節描述文件布局使用的B+樹數據結構。選擇B+樹是為了提高讀寫盤區的性能，這是JFS必須進行的最普通操作。B+樹為讀取文件的特定盤區提供快速搜索。它還提供有效方法將盤區添加或插入文件中。較為少見的情形是：當刪除文件時，JFS需要遍歷整個B+樹。為了保證JFS會刪除B+樹使用的塊以及文件數據，對於遍歷B+樹效率也很高。
中國
盤區分配描述符（xad結構）描述盤區並且又添加了表示文件所需的兩個字段：描述盤區表示的邏輯字節地址的偏移量和標志字段。盤區分配描述符結構在jfs_xtree.h,structxad中定義。
xad結構為：
[table=95%][tr][td][color=#ff0000]以下為引用的內容：[/color]
structxad{
unsignedflag:8;
unsignedrsvrd:16;
unsignedoff1:8;
uint32off2;
unsignedlen:24;
unsignedaddr1:8;
uint32addr2;
}xad_t;[/td][/tr][/table]
其中： [color=#f5fafe]中國[/color] flag是包含各種標志的8位字段。這些標志能夠表示寫入時復制、是否分配了盤區但沒有記錄它、壓縮信息等等。
rsvrd是保留供將來使用的16位字段。它總為零。
off1,off2是40位字段，包含盤區中第一個塊的邏輯偏移量。邏輯偏移量是以聚集塊尺寸為單位表示；也就是說，要取得一個字節，偏移量必須乘以聚集塊尺寸。
len是24位字段，包含盤區的長度。長度以聚集塊尺寸為單位表示。
addr1,addr2是40位字段，包含盤區的地址。地址以聚集塊尺寸為單位表示。
xad結構描述了兩個抽象範圍：
磁盤上磁盤塊的物理範圍。它以聚集塊號xad_address開始，並且延伸為xad_length聚集塊。 [color=#f5fafe][/color]
文件內字節的邏輯範圍。它以字節號xad_offset*AGBS（聚集塊尺寸）開始，並且延伸為xad_length*AGBS字節。
當然，物理範圍和邏輯範圍有相同長度的字節。請注意，xad_offset以聚集塊尺寸為單位存儲（例如，在xad_offset中值"3"意味著3個聚集塊，而不是3個字節）。它遵循文件內盤區總是以聚集塊尺寸為邊界。
JFS中的所有索引對象（除目錄外），有一個類屬B+樹索引結構。索引的數據將取決於對象。B+樹以由樹描述的數據的xad偏移量為鍵。項按xad結構的偏移量排序。xad結構是B+樹節點中的項。
磁盤inode第二扇區底部包含數據描述符，它描述在inode的後半部分內存儲的內容。對於足夠小的文件，後半部分可能包含內嵌數據。如果文件數據不適合inode的內嵌數據空間，它將包含在盤區中，inode將包含B+樹的根節點。頭部指出在使用的xad個數，可用的xad個數。通常， inode將包含8個xad結構B+樹的根。如果文件有8個或更少盤區，那么這8個xad結構也是B+樹的葉節點。它們將描述盤區。否則，inode中的 8個xad結構將指向B+樹的葉節點或內部節點。
中國
一旦inode中的8個xad結構均已填充，為了有更多的xad結構，就會嘗試使用inode的最後四分之一。如果INLINEEA位在inode的di_mode字段中設置，那么inode的最後四分之一可用。 [color=#f5fafe]Www.[/color]
一旦inode中所有可用的xad結構都被使用，就必須拆分B+樹。JFS將把4K的磁盤空間分配給B+樹的葉節點。葉節點邏輯上是帶頭的xad項的數組。頭部指向節點中第一個空閒的xad項，沒有分配緊跟其後的所有xad項。8個xad項從inode復制到葉節點，初始化頭部以指向第9個項作為第一個空閒項。然後JFS將把B+樹的根更新為inode的第一個xad結構；該xad結構將指向最新分配的葉節點。這個新的xad結構的偏移量是葉節點中第一個項的偏移量。將更新inode中的頭部以表示當前B+樹只使用1個xad。還需要更新inode頭部以表示當前inode包含B+樹的純根。
當把新盤區添加到文件時，將以必需的次序，繼續把它們添加到相同的葉節點。這將持續直到節點填滿為止。一旦節點填滿了，將為B+樹的另一個葉節點分配新的4K磁盤空間。將把該inode的第二個xad結構設置成指向新分配的節點。 [color=#f5fafe][/color]
這將持續直到填滿inode的所有8個xad結構為止，這時，將再次拆分B+樹。這種拆分將創建B+樹的內部inode，它們是純粹用來記錄樹的搜索路徑。JFS將為B+樹的內部inode分配4K磁盤空間。內部節點看起來如同葉節點。從inode復制8個xad項到內部節點，初始化頭部以指向第9 個項作為第一個空閒項。然後，通過使inode的第一個xad結構指向新分配的內部節點，JFS更新B+樹的根。將更新inode中的頭部以表示當前B+ 樹只使用1個xad。
文件jfs_xtree.h在structxtpage_t中描述B+樹根的頭部。文件jfs_btree.h是在structbtpage_t中的內部節點或葉節點的頭部。
例子
下列例子進一步分析了盤區描述符和xad結構的用法：
Www.
連續分配的1041377字節文件。
同的1041377字節文件，但在磁盤上拆分成三段。
1041377字節的文件，但裏面有一個"洞"（稀疏文件）。
連續分配的16GB文件。
在所有這些例子中，聚集塊尺寸都是1KB。
Www.
連續分配的1041377字節尺寸文件：該文件需要1017個1KB聚集塊，（在最後一個聚集塊中，有31個字節丟失成為內部存儲碎片）。要描述這個連續文件只需要一個xad結構：
flag這裏不討論
[table=95%][tr][td][color=#ff0000]以下為引用的內容：[/color]
offset0/*thebeginningofthefile*/
length1017/*10171KBaggregateblocks*/
addressxxxxx/*aggregateblock#*/[/td][/tr][/table]
相同的xad結構能夠表示任何長度為1040385（1016*1024+1）到1041408（1017*1024）的連續文件，因為盤區描述符只表示小於聚集塊大小粒度的尺寸。只有inode的di_size字段記錄字節粒度。
在1041377字節文件分三段：假設相同的文件拆分成磁盤上三個不同盤區：一個為495個聚集塊長，一個為22，一個為500。需要三個xad結構來表示該文件，每個物理盤區需要一個：
[table=95%][tr][td][color=#ff0000]以下為引用的內容：[/color]
xad#0:
flag這裏不討論
offset0/*thebeginningofthefile*/
length495/*4951KBaggregateblocks*/
addressxxxxx/*aggregateblock#*/
xad#1:
flag這裏不討論
offset495/*thebeginningofthefile*/
length22/*221KBaggregateblocks*/
addressyyyyy/*aggregateblock#*/
xad#2:
flag這裏不討論
offset517/*thebeginningofthefile*/
length500/*5001KBaggregateblocks*/
addresszzzzz/*aggregateblock#*/[/td][/tr][/table]
該例中，0號xad描述文件開始的495個物理聚集塊。xad_offset字段包含0，因為該xad描述以邏輯偏移量0開始的字節。第二個xad，1號xad，描述文件接下來的22個物理聚集塊。xad_offset字段包含495，因為該xad描述以邏輯偏移量506880 (495*1024)開始的字節；前面的字節由xad0描述。最後一個xad描述文件的最後500塊。這裏，xad_offset字段是517。請注意，對於非稀疏文件，給定xad的xad_offset字段等於所有以前xad結構長度和（在本例中，517=495+22）。如果這一關係總是成立的，那么 xad_offset字段就是冗餘的，可以消除。然而，下一個例子顯示，對於稀疏文件，xad_offset字段不是冗餘的。 1041377字節的稀疏文件：考慮經由以下POSIX風格的操作而創建的文件：
[table=95%][tr][td][color=#ff0000]以下為引用的內容：[/color]
fd=create("newfile",blahblahblah);
write(fd,"hi",2);
lseek(fd,1041374,0);
write(fd,"bye",3);[/td][/tr][/table]
該文件有以邏輯字節偏移量0開始的兩字節數據（"hi"），還有以邏輯字節偏移量1,041,374開始的三字節數據("bye")，並且在這兩者之間全為0（稀疏的）。文件的長度為1041377字節。 通常，JFS不分配物理磁盤空間以保存從不寫入文件的字節範圍。因此，將佔用兩個xad結構來表示該文件：一個為包含"hi"數據的盤區，一個為包含"bye"數據的盤區：
[table=95%][tr][td][color=#ff0000]以下為引用的內容：[/color]
xad#0:
flag這裏不討論
offset0/*thebeginningofthefile*/
length1/*11KBaggregateblocks*/
addressxxxxx/*aggregateblock#*/
xad#1:
flag這裏不討論
offset1016/*thebeginningofthefile*/
length1/*11KBaggregateblocks*/
addressyyyyy/*aggregateblock*/[/td][/tr][/table]
在該例中，第一個盤區(xad0)包含字節"hi"，緊接著是1022字節0。最後一個盤區(xad1)包含990字節0，緊接著是3字節"bye"。1KB盤區中剩餘的31字節不是文件的組成部分。（它們與第一個例子中丟失成為內部存儲碎片的31個字節相同）。 [color=#f5fafe][/color]
請注意，該例中，xad_offset字段是必需的；這是知道xad1表示文件內在無法預料的邏輯偏移量字節序列的唯一方法（也即，xad1的偏移量不等於xad0的偏移量加長度）。這是表示稀疏文件的方法。
inode的di_size字段包含寫入的最後一個字節偏移值加1。
連續分配的16GB的文件：xad結構中的長度字段僅有24位長：因此，它能包含的最大值是2(24)-1。如果聚集塊大小是1KB（例如），那么一個 xad能夠表示的最大盤區是(2(24)-1)*2(10)=1KB，小於16G。暗示這也是xad結構能夠表示的最大盤區。因此，如果文件夠大的話，就算它在磁盤上是相連的，也需要多個xad結構來表示它。本例中顯示了這樣一個連續分配的文件：一個16G文件，它從聚集塊號12345開始連續分配，獲取 16777216個1KB的聚集塊(16G)。
[table=95%][tr][td][color=#ff0000]以下為引用的內容：[/color] [color=#f5fafe][/color]
xad#0:
flag這裏不討論
offset0/*thebeginningofthefile*/
length16777215/*11KBaggregateblocks*/
address12345/*aggregateblock*/
xad#1:
flag這裏不討論
offset16777215/*thebeginningofthefile*/
length1/*11KBaggregateblocks*/
address16789560/*aggregateblock#*/[/td][/tr][/table]
在該例中，不論文件在磁盤上是否相連，要表示它至少需要兩個xad結構，這是由於單個盤區的長度限制。
頁:
[1]