学步园

Spare所儲存的資料如下所示：

圖十

• Tags：
• chunkID：指相對於此yaffs_Object的第幾個Chunk。當Chunk ID為0時，則表此Chunk所儲存的是yaffs_ObjectHeader。
• serialNumber：用以辨別哪個Chunk為最新的Chunk。當更新此Chunk時，其serialNumber會加1並寫入至其他Block的Chunk中，並將原Chunk的設為Invalid（表此Data Chunk已無效），但若在將該Chunk設為Invalid之前則發生了斷電（Power Lost）的突發事件，當電源回復並再重新掃描Flash Memory時，會檢查某一yaffs_Object到有兩個一樣的Chunk（其ChunkID相同），但其serialNumber不同，則會比較此二Chunk的serialNumber，以辨別出哪個Chunk為較新的Data，並將較舊Data的Chunk設為Invalid。如下表所示：

• objectID：此Chunk屬於哪個Object的Objecct ID。
• ECC：Tags的Error Correction Code。
• unusedStaff：保留未使用的欄位。
• ECC Data：Data Chunk的Error Correction Code。
• Page Status：當值為0時，表示此值為Invalid。
• Block Status：保留未使用的欄位。

3.2 Tree Node Structure(Tnode Structure)

　　系統欲存取裝置上的Data時是以Logical Address（相對於該File所產生出來的偏移位址）的方式到所指定的位址進行存取，若欲到實體儲存裝置上取得Data，則須再經過一個機制的轉換，將Logical Address轉換為Physical Address（實際儲存裝置的位址），才可從儲存裝置上讀出Data至RAM中。這個機制最簡單的方法就是在RAM上建立一個Logical Address到Physical Address的對映表格（Mapping Table）。直接將Logical Address對映至Physical
Address。如圖十一所示：

圖十一-在RAM中建立Logical Address對應至Physical Address的對映表格

在YAFFS中也使用了Logical Address到Physical Address 的對映機制。所使用的機制稱之為Tree Node Structure或Tnode Structure。

　　Flash Memory掛載時，YAFFS會為每個File在RAM中建立一個Tree，當有一個要求要存取某個Chunk（或Logical Address）時，則會經由Tree Node Structure的轉換方式，找到Chunk的Physical Address。

使用Tree Node Structure的優點為位址轉換時間較迅速。Tree Node Structure的轉換Time Complexity為O(log N)，若是直接使用Logical Address to Physical Address的Mapping Table，則位址轉換為線性搜尋（Linear Search），此種搜尋方式的Time Complexity為O(N)。YAFFS採用此種方式來做為位址轉換的機制可提升整體的存取速度。

　　Tree Node Structure是由多個Tree Node（或Tnode）所組成。依據Level的不同而分成兩個部份：

• Internal Tnode：每個Internal Tnode由8個Pointers所組成。
• Lowest-Level Tnode（Level 0 Tnode）：每個Lowest-Level Tnode由16個Entries所組成。

圖十二

在Tree建立好後，當系統發出要存取該File的某個Chunk時，例如：Chunk 0x235，就要在Tree上做Traverse的動作，以找尋到要求的Chunk。Traverse的步驟如下：

1. 將十六進制轉化為二進制：0x235  0000001000110101

2. 將二進制切割成000.000.100.011.0101，每一個切割區代表一個Level，由於Lowest-Level包含有16個Entries，因此切割出4個Bit（Bit 3 to 0）。Internal Level的Tnode皆包含8個Pointer，因此其餘皆切割為3個Bit。

3. 根據所切割出來的Bit整理成下表：

4. 根據表格中各Level的值進行Traverse。

當Tree Node Structure剛開始建立時，僅會建立Lowest-Level Tnode，當File所配置的Chunk數超過16個時，則此Tree會建立一個internal Tnode，並將其第0個Pointer指向原本的Lowest-Level Tnode。當讀取到的Chunk數愈來愈多時，會一直新增Tnode，且Tree亦會愈來愈高，其Max-Level最大為6。

　　在File已在RAM建立好Tree Node Structure後，若此File的Size變大時，則會再多配置Chunk給此File，在將Data寫入至Page後，則會去更新File的 Tree Node Structure，將新配置到的Chunk加入至Tree Node Structure中，更改步驟如下：

1. 搜尋新配置到的Chunk ID。

2. 若在Internal-Level搜尋的過程中，發現沒有Tnode，則建立一個Internal-Level的Tnode。

3. 當搜尋到Lowest-Level時，若也無Tnode存在，則建立一個Lowest-Level的Tnode。

4. 根據Chunk ID中Level 0所代表的值x，到Lowest-Level Tnode中的第x個Entry中檢查有無該Chunk的實體位址存在，若沒有則將實體位址填入該Entry，若已存在則將比較兩Chunk在Spare 中的serialNumber，將較新的Chunk的實體位址寫入該Entry中，並將舊的Chunk設為Invalid。

3.3 YAFFS Garbage Collection

Garbage Collection主要是用於將已不必要存在且浪費空間的Block做回收的動作，以增加可用的Block數。而Garbage Collection只有某些事件發生時才會執行。

在YAFFS中只有在下列事件發生時會執行Garbage Collection：

• 將Data寫入Flash Memory
• 更新yaffs_ObjectHeader

而YAFFS的Garbage Collection又分成兩種Mode：Aggressive Mode及Passive Mode，其相異點如下表所示：

　　YAFFS的Garbage Collection執行步驟如下：

1. 從currentDirtyChecker到End Block之間尋找Dirtiest Block（包含最多Invalid Chunk的Block）

圖十三

2. 將currentDirtyChecker重置至所發現的Dirtiest Block的位置

圖十四

3. 將Dirtiest Block中的Valid Page複製至其他的Empty Chunk中。

圖十五

4. 再將Dirtiest Block清除成Empty Block。

圖十六

3.4 Wear-Leveling

　　當Flash Memory在使用時，常常會對Flash Memory內的某個檔案做修改的動作，若此時檔案的大小更動而需要更多Page時，且在Flash Memory內仍有空的Block，則會配置空的Block給該檔案，若Flash Memory內已無空的Block，則會執行Garbage Collection的動作，清出空的Block以供使用。而在挑選空Block或使用Garbage Collection時挑選Dirtiest Block時，可能會造成部份的Block常常被挑選，而其他Block則很少被挑選配置。

圖十七

由於Flash Memory的特性，那些常常被挑選的Block可能會因為過度的使用而造成損毀，為了避免這種負擔不均的情形發生，因此在大部份的Flash- Specific File System上都會設計一種方法以避免此種情形發生，此方法即稱為Wear-Leveling。

使用Wear-Leveling時，在挑選Block時不會常常固定在某幾個Block上，而可使大部份Block的存取次數能夠平均，不會造成部份Block過度存度而造成毀損。

圖十八