yaffs2文件系統(tǒng)分析

1、yaffs2文件系統(tǒng)分析作者：dreamice1前言略。2.yaffs文件系統(tǒng)簡(jiǎn)介按理說(shuō)這里應(yīng)該出現(xiàn)一些諸如“yaffs是一種適合于NAND Flash的文件系統(tǒng)XXXXX之類的字眼，不過(guò)考慮到網(wǎng)絡(luò)上關(guān)于yaffs/yaffs2的介紹已經(jīng)多如牛毛，所以同上，略。3本文內(nèi)容組織本文將模仿linux內(nèi)核源代碼情景分析一書，以情景分析的方式對(duì)yaffs2文件系統(tǒng)的源代碼進(jìn)行分析。首先將分析幾組底層函數(shù)，如存儲(chǔ)空間的分配和釋放等；其次分析文件 邏輯地址映射；然后是垃圾收集機(jī)制；接下來(lái) Sorry，本人還沒想好。:-）4說(shuō)明因?yàn)閥affs2貌似還在持續(xù)更新中，所以本文所列代碼可能和讀者手中的代碼不完全一

2、致。 另外，本文讀者應(yīng)熟悉C語(yǔ)言，熟悉NAND Flash的基本概念（如 block和page）。Ok，步入正題。首先分析存儲(chǔ)空間的分配。5.NAND Flash存儲(chǔ)空間分配和釋放我們知道，NAND Flash的基本擦除單位是 Block，而基本寫入單位是 page。yaffs2在分配 存儲(chǔ)空間的時(shí)候是以 page為單位的，不過(guò)在 yaffs2中把基本 存儲(chǔ)單位稱為chunk，和 page是一樣的大小，在大多數(shù)情況下和page是一個(gè)意思。在下文中我們使用chunk這個(gè)詞，以保持和yaffs2的源代碼一致。我們先看存儲(chǔ)空間的分配（在yaffs_guts.c中。這個(gè)文件也是 yaffs2文件系統(tǒng)的

3、核心部分）： Yaffs2中將該函數(shù)更名為 yaffs_alloc_chunk。static int yaffs_AllocateChu nk（yaffs_Device * dev, i nt useReserve, yaffs_BlockI nfo *blockUsedPtr）int retVal;yaffs_BlockI nfo *bi;if （dev-allocatio nBlock allocati on Block = yaffs_ Fin dBlockForAllocati on（ dev）; dev-allocati on Page = 0;函數(shù)有三個(gè)參數(shù)，dev是yaffs_D

4、evice結(jié)構(gòu)的指針，yaffs2用這個(gè)結(jié)構(gòu)來(lái)記錄一個(gè)NAND器件的屬性（如block和page的大?。┖拖到y(tǒng)運(yùn)行過(guò)程中的一些統(tǒng)計(jì)值（如器件中可用chunk的總數(shù)），還用這個(gè)結(jié)構(gòu)維護(hù)著一組NAND操作函數(shù)（如讀、寫、刪除）的指針。整個(gè)結(jié)構(gòu)體比較大，我們會(huì)按情景的不同分別分析。useReserve表示是否使用保留空間。yaffs2文件系統(tǒng)并不會(huì)將所有的存儲(chǔ)空間全部用于存儲(chǔ)文件系統(tǒng)數(shù)據(jù)，而要空出部分block用于垃圾收集時(shí)使用。一般情況下這個(gè)參數(shù)都是0，只有在垃圾收集時(shí)需要分配存儲(chǔ)空間的情況下將該參數(shù)置1。yaffs_BlockInfo 是描述block屬性的結(jié)構(gòu)，主要由一些統(tǒng)計(jì)變量組成，比如該

5、block內(nèi)還剩多少空閑page等。我們同樣在具體情景中再分析這個(gè)結(jié) 構(gòu)中的字段含義。函數(shù)首先判斷 dev-allocati on Block的值是否小于 0。yaffs_Device結(jié)構(gòu)內(nèi)的 allocati on Block字段用于 記錄當(dāng)前從中分配 chunk （page）的那個(gè)block的序號(hào)。當(dāng)一 個(gè)block內(nèi)的所有page全部分配完畢時(shí)，就將這個(gè)字段置為-1，下次進(jìn)入該函 數(shù)時(shí)就會(huì)重新挑選空閑的block。這里我們假定需要重新挑選空閑block，因此進(jìn)入yaffs_Fi ndBlockForAllocatio n 函數(shù)：yaffs_AllocateChu nk() = yaffs

6、_Fi ndBlockForAllocatio n()static int yaffs_ Fin dBlockForAllocati on( yaffs_Device * dev)int i;yaffs_BlockI nfo *bi;if (dev- nErasedBlocks nErasedBlocks記錄著器件內(nèi)所有可供分配的block的數(shù)量。如果該值小于1，那顯然是有問題了。不但正常的分配請(qǐng)求無(wú)法完成，就連垃圾收集都辦不到了。for (i = dev- intern alStartBlock; i intern alE ndBlock; i+) dev-allocati on Block

7、F in der+;if (dev-allocatio nBlockF in der intern alStartBlock| dev-allocati on BlockF in der dev- intern alE ndBlock) dev-allocati on BlockF in der = dev- intern alStartBlock;internalStartBlock和internalEndBlock分別是yaffs2使用的block的起始序號(hào)和結(jié)束 序號(hào)。也就是說(shuō)yaffs2文件系統(tǒng)不一定要占據(jù)整個(gè) Flash，可以只占用其中的一部分。dev-allocationBlock

8、Finder記錄著上次分配的塊的序號(hào)。如果已經(jīng)分配到系統(tǒng)尾部，就 從頭重新開始搜索可用塊。bi = yaffs_get_block_ in fo(dev, dev-alloc_block_fi nder);if (bi-block_state = Y AFFS_BLOCK_STATE_EMPTY) bi-block_state = YAFFS_BLOCK_STATE_ALLOCATING; dev-seq_ nu mber+;bi-seq_ nu mber = dev-seq_ nu mber;dev- n _erased_blocks-;yaffs_trace(YAFFS_TRACE_ALL

9、OCATE,Allocated block %d, seq %d, %d left,dev-alloc_block_fi nder, dev-seq_ nu mber, dev- n _erased_blocks);retur n dev-alloc_block_fi nder;yaffs_GetBlockInfo函數(shù)獲取指向block信息結(jié)構(gòu)的指針，該函數(shù)比較簡(jiǎn)單，就不詳細(xì)介紹了。yaffs_Blocklnfo 結(jié)構(gòu)中的blockState成員描述該 block的狀態(tài)，比如空，滿，已 損壞，當(dāng)前分配中，等等。因?yàn)槭且峙淇臻e塊，所以塊狀態(tài)必須是YAFFS_BLOCK_STATE_EMPTY

10、，如果不是，就繼續(xù)測(cè)試下一個(gè)block。找到以后將 block狀態(tài)修改為YAFFS_BLOCK_STATE_ALLOCATING，表示當(dāng)前正從該 block中分配存儲(chǔ)空間。正常情況下，系統(tǒng)中只會(huì)有一個(gè) block處于該狀 態(tài)。另外還要更新統(tǒng)計(jì)量 ErasedBlocks和 sequenceNumber。這個(gè)sequenceNumber記錄著各 block被分配出去的先后 順序，以后在 垃圾收集的時(shí)候會(huì)以此作為判斷該 block是否適合回收的依據(jù)?，F(xiàn)在讓我們返回到函數(shù)yaffs_AllocateChunk 中。yaffs_CheckSpaceForAllocation()函數(shù)檢查Flash上是否

11、有足夠的可用空間，通過(guò)檢查后，就從當(dāng)前供分配的block上切下一個(gè)if (dev-alloc_block = 0) bi = yaffs_get_block_ in fo(dev, dev-alloc_block);ret_val = (dev-alloc_block * dev-param.ch un ks_per_block) +dev-alloc_page;bi-pages_i n_use+; yaffs_set_ch un k_bit(dev, dev-alloc_block, dev-alloc_page); dev-alloc_page+;dev- n _free_ch un ks

12、-;/* If the block is full set the state to full */if (dev-alloc_page = dev-param.ch un ks_per_block) bi-block_state = YAFFS_BLOCK_STATE_FULL; dev-alloc_block = -1;if (block_ptr)*block_ptr = bi;return ret_val;dev-allocationPage記錄著上次分配的 chunk在block中的序號(hào)，每分配一次加1。從這里我們可以看出，系統(tǒng)在分配chunk的時(shí)候是從block的開頭到結(jié)尾按序分配的

13、，直到一個(gè)block內(nèi)的所有chunk全部分配完畢為止。retVal是該chunk在整個(gè)device內(nèi)的總序 號(hào)。Pages In Use記錄著該block中已分配使用的page的數(shù)量。系統(tǒng)在設(shè)備描述結(jié)構(gòu)yaffs_Device中維護(hù)著一張位圖，該位圖的每一位都代表著Flash上的一個(gè)chunk的狀態(tài)。yaffs_SetChunkBit()將剛分配得到的 chunk在位圖中的對(duì)應(yīng)位置1,表明該塊已被使用。更新一些統(tǒng)計(jì)量后，就可以返回了?？催^(guò)chunk分配以后，我們?cè)賮?lái)chunk的釋放。和chunk分配不同的是，chunk的釋放在大多數(shù)情況下并不釋放對(duì)應(yīng)的物理介質(zhì)，這是因?yàn)镹AND雖然可以按pa

14、ge寫，但只能按block擦除，所以物理介質(zhì)的釋放要留到垃圾收集或一個(gè)block上的所有page全部變成空閑的時(shí)候才進(jìn)行。根據(jù)應(yīng)用場(chǎng)合的不同，chunk的釋放方式并不唯一，分別由yaffs_DeleteChunk 函數(shù)和 yaffs_SoftDeleteChunk 函數(shù)完 成。我們先看yaffs_DeleteChunk :(該函數(shù)在后續(xù)版本中被更名為yaffs_chunk_del()void yaffs_DeleteChu nk(yaffs_Device * dev, i nt chu nkld, i nt markNAND, i nt lyn) chunkld就是要?jiǎng)h除的 chunk的序號(hào)，

15、markNand參數(shù)用于yaffs 一代的代碼中，yaffs2不 使用該參數(shù)。參數(shù)lyn在調(diào)用該函數(shù)時(shí)置成當(dāng)前行號(hào)(_LINE_)，用于調(diào)試。首先通過(guò)yaffs_GetBlockInfo獲得chunk所在block的信息描述結(jié)構(gòu)指針，然后就跑到 else里面去了。 if語(yǔ)句的判斷條件中有一條!dev-isYaffs2，所以對(duì)于yaffs2而言是不會(huì)執(zhí)行if分支的。在else分支里面只是遞增一下統(tǒng)計(jì)計(jì)數(shù)就出來(lái)了，我們接著往下看。if (bi-blockState = Y AFFS_BLOCK_STA TE_ALLOCATING | bi-blockState = Y AFFS_BLOCK_STA

16、TE_FULL |bi-blockState = Y AFFS_BLOCK_STATE_NEEDS_SCANNING |bi-blockState = Y AFFS_BLOCK_STATE_COLLECTING) dev- nF reeCh un ks+;yaffs_ClearCh un kBit(dev, block, page);bi-pages InU se-;if (bi-pages InUse = 0 &!bi-hasShri nkHeader &bi-blockState != Y AFFS_BLOCK_STATE_ALLOCATING &bi-blockState != Y AF

17、FS_BLOCK_STATE_NEEDS_SCANNING) yaffs_BlockBecameDirty(dev, block);首先要判斷一下該 block上是否確實(shí)存在著可釋放的chunk。block不能為空，不能是壞塊。YAFFS_BLOCK_STATE_NEEDS_SCANNING表明正對(duì)該塊進(jìn)行垃圾回收，我們后面會(huì)分析；YAFFS_BLOCK_STATE_NEEDS_SCANNING在我手上的源代碼中似乎沒有用到。通過(guò)判斷以后，所做的工作和chunk分配函數(shù)類似，只是一個(gè)遞增統(tǒng)計(jì)值，一個(gè)遞減。遞減統(tǒng)計(jì)值以后還要判斷該block上的page是否已全部釋放，如果已全部釋放，并且不是當(dāng)前

18、分配塊，就通過(guò) yaffs_BlockBecameDirty函數(shù)刪除該block，只要能通過(guò)刪除操作(不是壞塊)，該block就又可以用于分配了。相比較來(lái)說(shuō)，yaffs_SoftDeleteChunk所做的工作就簡(jiǎn)單多了。關(guān)鍵的代碼只有兩行：static void yaffs_SoftDeleteChu nk(yaffs_Device * dev, i nt chunk) theBlock-softDeleti on s+; dev- nF reeCh un ks+;這里遞增的是yaffs_blocklnfo結(jié)構(gòu)中的另一個(gè)統(tǒng)計(jì)量softDeletions ,而沒有修改pagesInUse成員，

19、也沒有修改 chunk狀態(tài)位圖。那么，這兩個(gè)函數(shù)的應(yīng)用場(chǎng)合有什么區(qū)別 呢？一般來(lái)說(shuō)，yaffs_DeleteChunk用于文件內(nèi)容的更新。比如我們要修改文件中的部分內(nèi)容， 這時(shí)候yaffs2會(huì)分配新的chunk，將更改后的內(nèi)容寫入新chunk中，原chunk的內(nèi)容自然就沒有用了，所以要將page In Use減1并修改位圖；yaffs_SoftDeleteChunk用于文件的刪除。yaffs2在刪除文件的時(shí)候只是刪除該文件在內(nèi)存中的一些描述結(jié)構(gòu)，而被刪除的文件所占用的chunk不會(huì)立即釋放，也就是不會(huì)刪除文件內(nèi)容，在后續(xù)的文件系統(tǒng)操作中一般也不會(huì)把這些chunk分配出去，直到系統(tǒng)進(jìn)行垃圾收集的

20、時(shí)候才有選擇地釋放這些chunk。熟悉DOS的朋友可能還記得，DOS在刪除的文件的時(shí)候也不會(huì)立即刪除文件內(nèi)容，只是將文件名的第一個(gè)字符修改為0xA5，事后還可以恢復(fù)文件內(nèi)容。yaffs2在這點(diǎn)上是類似的。1文件地址映射chunk,也就是說(shuō),的flash上的存儲(chǔ)地上面說(shuō)到，yaffs文件系統(tǒng)在更新文件數(shù)據(jù)的時(shí)候，會(huì)分配一塊新的同樣的文件偏移地址，在該地址上的數(shù)據(jù)更新前和更新后，其對(duì)應(yīng)址是不一樣的。那么，如何根據(jù)文件內(nèi)偏移地址確定flash存儲(chǔ)地址呢？最容易想到的辦法，就是在內(nèi)存中維護(hù)一張映射表。由于 chunk描述的文件偏移量作為表索引，將flash基本存儲(chǔ)單位是 chunk，因此，只要將以 f

21、lash chunk序號(hào)作為表內(nèi)容，就可以解決該問題了。但是這個(gè)方法有幾個(gè)問題，首先就是在做seek操作的時(shí)候，要從表項(xiàng)0開始按序搜索，對(duì)于大文件會(huì)消耗很多時(shí)間；其次是在建立映射表的時(shí)候，無(wú)法預(yù)計(jì)文件大小的變化，于是就可能在后來(lái)的操作中頻繁釋放分配內(nèi)存以改變表長(zhǎng)，造成內(nèi)存碎片。yaffs的解決方法是將這張大的映射表拆分成若干個(gè)等長(zhǎng)的小表，并將這些小表組織成樹的結(jié)構(gòu)， 方便管理。我們先看小表的定義：struct yaffs_t node struct yaffs_t node *i nternalYAFFS_NTNODES_INTERNAL;；YAFFS_NTNODES_INTERNAL 定義為

22、(YAFFS_NTNODES_LEVEL0 / 2)，而YAFFS_NTNODES_LEVEL0 定義為16，所以這實(shí)際上是一個(gè)長(zhǎng)度為8的指針數(shù)組。不管是葉子節(jié)點(diǎn)還是非葉節(jié)點(diǎn)，都是這個(gè)結(jié)構(gòu)。當(dāng)節(jié)點(diǎn)為非葉節(jié)點(diǎn)時(shí)，數(shù)組中的每個(gè)元素都指向下一層子節(jié)點(diǎn)；當(dāng)節(jié)點(diǎn)為葉子節(jié)點(diǎn)時(shí)，該數(shù)組拆分為16個(gè)16位長(zhǎng)的短整數(shù)(也有例外，后面會(huì)說(shuō)到)，該短整數(shù)就是文件內(nèi)容在flash上的存儲(chǔ)位置(即 chunk序號(hào))。至于如何通過(guò)文件內(nèi)偏移找到對(duì)應(yīng)的flash存儲(chǔ)位置，源代碼所附文檔(Developme nt/yaffs/Docume ntatio n/yaffs-no tes2.html )已經(jīng)有說(shuō)明，俺就不在此處饒

23、舌了。下面看具體函數(shù)。為了行文方便，后文中將yaffs_T node這個(gè)指針數(shù)組稱為一組” Tn ode而將數(shù)組中的每個(gè)元素稱為 一個(gè)” Tnode樹中的每個(gè)節(jié)點(diǎn)，都是一組” Tnode先看 映射樹的節(jié)點(diǎn)的分配。struct yaffs_t node *yaffs_get_t no de(struct yaffs_dev *dev)struct yaffs_t node *tn = yaffs_alloc_raw_t no de(dev);if (tn) memset(t n, 0, dev-t no de_size);dev- n_tno des+;dev-checkpo in t_bloc

24、ks_required = 0; /* force recalculati on */ return tn;調(diào)用yaffs_GetTnodeRaw分配節(jié)點(diǎn)，然后將得到的節(jié)點(diǎn)初始化為零。static yaffs_T node *yaffs_GetT no deRaw(yaffs_Device * dev)yaffs_T node *tn = NULL;/* If there are none left make more */if (!dev-freeT no des) yaffs_CreateT nodes(dev, YAFFS_ALLOCATION_NTNODES);當(dāng)前所有空閑節(jié)點(diǎn)組成一個(gè)

25、鏈表，dev-freeTnodes是這個(gè)鏈表的表頭。我們假定已經(jīng)沒有空閑節(jié)點(diǎn)可用，需通過(guò) yaffs_CreateTnodes創(chuàng)建一批新的節(jié)點(diǎn)。static int yaffs_CreateT no des(yaffs_Device * dev, int nTno des) tno deSize = (dev-t nodeWidth * YAFFS_NTNODES_LEVEL0)/8; newT nodes = YMALLOC( nTn odes * tn odeSize);mem = (_u8 *)n ewT no des;(其實(shí)在最新版本的yaffs中已經(jīng)加入了 slab緩沖區(qū)，這樣提高了

26、效率)上面說(shuō)過(guò)，葉節(jié)點(diǎn)中一個(gè)Tnode的位寬默認(rèn)為16位，也就是可以表示 65536個(gè)chunk。對(duì)于時(shí)下的大容量flash，chunk的大小為2K，因此在默認(rèn)情況下 yaffs2所能尋址的最大 flash空間就是128M。為了能將yaffs2用于大容量flash上，代碼作者試圖通過(guò)兩種手段 解決這個(gè) 問題。第一種手段就是這里的dev-tnodeWidth，通過(guò)增加單個(gè) Tnode的位寬，就可以增加其所能表示的最大chunk Id ;另一種手段是我們后面將看到的chunk group，通過(guò)將若干個(gè)chunk合成一組用同一個(gè)id來(lái)表示，也可以增加系統(tǒng)所能尋址的chunk范圍。俺為了簡(jiǎn)單，分析的時(shí)

27、候不考慮這兩種情況，因此tnodeWidth取默認(rèn)值16,也不考慮將多個(gè)chunk合成一組的情況，只在遇到跟這兩種情況有關(guān)的代碼時(shí)作簡(jiǎn)單說(shuō)明。在32位的系統(tǒng)中，指針的寬度為32位，而chunk id的寬度為16位，因此相同大小的Tn ode組，可以用來(lái)表示 N個(gè)非葉Tnode (作為指針使用)，也可以用來(lái)表示 N * 2個(gè)葉子Tnode (作為 chunk id 使用)。代碼中分另U用 YAFFS_NTNODES_INTERNAL 禾口YAFFS_NTNODES_LEVELO 來(lái)表示。前者取值為 8，后者取值為16。從這里我們也可以看 出若將yaffs2用于64位系統(tǒng)需要作哪些修改。針對(duì)上一段

28、敘述的問題，俺以為在內(nèi)存不緊張的情況下，不如將葉節(jié)點(diǎn)Tn ode和非葉節(jié)點(diǎn)Tnode都設(shè)為一個(gè)指針的長(zhǎng)度。分配得到所需的內(nèi)存后，就將這些空閑空間組成Tn ode鏈表：for(i = 0; i intern al0 = n ext;每組Tn ode的第一個(gè)元素作為指針指向下一組Tn ode。完成鏈表構(gòu)造后，還要遞增統(tǒng)計(jì)量，并將新得到的Tn odes掛入一個(gè)全局管理鏈表yaffs_Tn odeList :dev- nF reeT no des += nTno des;dev- nTno desCreated += nTno des;tnl = YMALLOC(sizeof(yaffs_T node

29、List);if (!t nl) T(YAFFS_TRACE_ERROR,(TSTR(yaffs: Could n ot add tn odes to ma nageme nt list TENDSTR); else tn l-t no des = n ewT no des;tn I-n ext = dev-allocatedT no deList;dev-allocatedT no deList = tnl;回到y(tǒng)affs_GetT nodeRaw，創(chuàng)建了若干組新的Tn ode以后，從中切下所需的Tn ode，并修改空閑鏈表表頭指針：if (dev-freeT no des) tn = de

30、v-freeT no des;dev-freeT no des = dev-freeT no des-intern al0;dev- nF reeT no des-;至此，分配工作就完成了。相比較來(lái)說(shuō)，釋放Tnodes的工作就簡(jiǎn)單多了，簡(jiǎn)單的鏈表和統(tǒng)計(jì)值操作：static void yaffs_FreeT no de(yaffs_Device * dev, yaffs_T node * tn)if (tn) tn-intern al0 = dev-freeT no des;dev-freeT no des = tn;dev- nF reeT no des+;看過(guò)Tn ode的分配和釋放，我們?cè)?/p>

31、來(lái)看看這些Tn ode是如何使用的。在后文中，我們把以chunk為單位的文件內(nèi)偏移稱作邏輯chunk id，文件內(nèi)容在flash上的實(shí)際存儲(chǔ)位置稱作物理chunk id。先看一個(gè)比較簡(jiǎn)單的函數(shù)。void yaffs_PutLevelOT no de(yaffs_Device *dev, yaffs_T node *tn, un sig ned pos,un sig ned val)這個(gè)函數(shù)將某個(gè) Tn ode設(shè)置為指定的值。tn是指向一組Tn ode的指針；pos是所要設(shè)置的 那個(gè)Tn ode在該組Tn ode中的索引；val就是所要設(shè)置的值，也就是物理 chunk id。函數(shù) 名中的Leve

32、l0指映射樹的葉節(jié)點(diǎn)。函數(shù)開頭幾行如下：pos &= YAFFS_TNODES_LEVELO_MASK;val = dev-ch un kGroupBits;bit InMap = pos * dev-t nodeWidth;wordI nMap = bit In Map /32;bit InWord = bit InMap & (32 -1);mask = dev-t no deMask tnodeWidth中。yaffs2允許使用非字節(jié)對(duì)齊的tnodeWidth，因此可能出現(xiàn)某個(gè)chunk id跨32位邊界存儲(chǔ)的情況。所以在下面的代碼中，需要分邊界前和邊界后兩部分處理：mapwordl n

33、Map &= mask;mapwordl nMap |= (mask & (val t nodeWidth (32-bitI nWord) bit InWord = (32 - bit In Word);word InM ap+;mask = dev-t nodeMask (/*dev-t nodeWidth -*/ bitI nWord); mapwordI nMap &= mask; mapwordI nMap |= (mask & (val bit In Word);if語(yǔ)句判斷當(dāng)前chunk序號(hào)是否跨越當(dāng)前 32位邊界。整個(gè)代碼初看起來(lái)比較難理解，其 實(shí)只要將dev-tnodeWidt

34、h以16或32代入，就很好懂了。還有一個(gè)類似的函數(shù)yaffs_GetChunkGroupBase，返回由tn和pos確定的一組 chunk的起始序號(hào)，就不詳細(xì)分析了?，F(xiàn)在我們假設(shè)有這樣一個(gè)情景：已知文件偏移地址，要找到flash上對(duì)應(yīng)的存儲(chǔ)地址，該怎么做呢？這項(xiàng)工作的主體是由函數(shù)yaffs_FindLevelOTnode完成的。static yaffs_T node *yaffs_ Fin dLevel0T no de(yaffs_Device * dev,yaffs_FileStructure * fStruct,_u32 chu nkld)yaffs_T node *tn = fStruc

35、t-top;_u32 i;int requiredTall ness;in t level = fStruct-topLevel;函數(shù)參數(shù)中，fStruct是指向文件描述結(jié)構(gòu)的指針，該結(jié)構(gòu)保存著文件大小、映射樹層高、映射樹頂層節(jié)點(diǎn)指針等信息。chunkld是邏輯chunk id。fStruct-top是映射樹頂層節(jié)點(diǎn)指針，fStruct-topLevel是映射樹層高。注意：當(dāng)只有一層時(shí)，層高為 0。/* First check were tall eno ugh (ie eno ugh topLevel) */i = chun kld YAFFS_TNODES_LEVEL0_BITS;requ

36、iredTall ness = 0;while (i) i = YAFFS_TNODES_INTERNAL_BITS;requiredTall ness+;if (requiredTall ness fStruct-topLevel) /* Not tall en ough, so we cant find it, return NULL. */return NULL;在看這段代碼之前，我們先用一個(gè)例子來(lái)回顧一下映射樹的組成。假定我們有一個(gè)大小為128K的文件，flash的page大小為2K，那么我們就需要 64個(gè)page (或者說(shuō)chunk)來(lái) 存儲(chǔ)該文件。一組 Tn ode的size是8個(gè)

37、指針，或者16個(gè)16位整數(shù)，所以我們需要64 / 16=4組Tn ode來(lái)存儲(chǔ)物理chunk序號(hào)。這4組Tnode就是映射樹的葉節(jié)點(diǎn)，也就是LevelO節(jié)點(diǎn)。由于這4組Tn ode在內(nèi)存中不一定連續(xù)，所以我們需要另外一組 Tn ode，將其作為指針數(shù)組使用，這個(gè)指針數(shù)組的前4個(gè)元素分別指向4組LevelO節(jié)點(diǎn)，而fStruct-top就指向這 組作為指針數(shù)組使用的Tn ode。隨著文件長(zhǎng)度的增大，所需的葉節(jié)點(diǎn)越多，非葉節(jié)點(diǎn)也越多，樹也就越長(zhǎng)越高?；剡^(guò)頭來(lái)看代碼，首先是檢查函數(shù)參數(shù)chunkld是否超過(guò)文件長(zhǎng)度。作為非葉節(jié)點(diǎn)使用的Tn ode每組有8個(gè)指針，需要3位二進(jìn)制碼對(duì)其進(jìn)行索引，因此樹每

38、長(zhǎng)高一層，邏輯chunkld就多出3位。相反，每3位非零chunkld就代表一層非葉節(jié)點(diǎn)。while循環(huán)根據(jù)這個(gè)原則計(jì)算參數(shù)chunkld所對(duì)應(yīng)的樹高。如果樹高超過(guò)了文件結(jié)構(gòu)中保存的樹高，那就 說(shuō)明該邏輯chunkld已經(jīng)超出文件長(zhǎng)度了。通過(guò)文件長(zhǎng)度檢查之后，同樣根據(jù)上面的原則， 就可以 找到邏輯chunkld對(duì)應(yīng)的物理chunkld 了。具體的操作通過(guò)一個(gè)while循環(huán)完成：/* Traverse dow n to level 0 */while (level 0 & tn) tn = tn-intern al(ch un kid (YAFFS_TNODES_LEVELO_BITS +(le

39、vel - 1) *YAFFS_TNODES_INTERNAL_BITS)& (YAFFS_TNODES_INTERNAL_MASK;level-;return tn;將返回值和邏輯 chunk id作為參數(shù)調(diào)用yaffs_GetChunkGroupBase，就可以得到物理 chunk id 了。下面我們看另一個(gè)情景，看看當(dāng)文件長(zhǎng)度增加的時(shí)候，映射樹是如何擴(kuò)展的。主要函數(shù)為static yaffs_T node *yaffs_AddOr Fin dLevelOT no de(yaffs_Device * dev,yaffs_FileStructure * fStruct,_u32 chu nk

40、ld,yaffs_T node *passedT n)函數(shù)的前幾行和 yaffs_ Fin dLevelOT node 樣，對(duì)函數(shù)參數(shù)作一些檢查。通過(guò)檢查之后, 首先看原映射樹是否有足夠的高度，如果高度不夠，就先將其拔高”if (required_depth file_struct-top_level) /* Not tall eno ugh, gotta make the tree taller */for (i = file_struct-top_level; i intern al0 = file_struct-top;file_struct-top = tn;file_struct-t

41、op_level+; else yaffs_trace(YAFFS_TRACE_ERROR,yaffs: no more tno des);return NULL;for循環(huán)完成增加新層的功能。新增的每一層都只有一個(gè)節(jié)點(diǎn)(即一組Tn ode)，fStruct-top始終指向最新分配的節(jié)點(diǎn)。將映射樹擴(kuò)展到所需的高度之后，再 根據(jù)需要將其 增肥”擴(kuò)展其 寬度”l = file_struct-top_level;tn = file_struct-top;if (l O) while (l 0 & tn) x = (ch un k_id (YAFFS_TNODES_LEVELO_BITS +(l -

42、1) * YAFFS_TNODES_INTERNAL_BITS) & YAFFS_TNODES_INTERNAL_MASK;if (l 1) & !tn-i nternal x) /* Add miss ing non-level-zero tnode */ tn-intern alx = yaffs_get_t no de(dev); if (!t n-intern alx)return NULL; else if (l = 1) /* Looki ng from level 1 at level 0 */if (passed_t n) /* If we already have one,

43、release it */if (tn-i nternalx)yaffs_free_t no de(dev,tn-i nternalx);tn-intern alx = passed_t n; else if (!t n-i nternalx) /* Dont have one, none passed in */tn-intern alx = yaffs_get_t no de(dev);if (!t n-intern alx)return NULL;tn = tn-i nternalx;l-;上面 拔高”的時(shí)候是從下往上蓋樓”這里 增肥”的時(shí)候是從上往下擴(kuò)展”tn-internalx為空表

44、示下層節(jié)點(diǎn)尚未創(chuàng)建，需要通過(guò)yaffs_GetTnode分配之，就是 “增肥了。如果函數(shù)參數(shù)passedTn有效，就用該組Tnode代替levelO上原先的那組 Tnode ；否則按需分配新的Tn ode組。所以這里的函數(shù)名似乎應(yīng)該取作yaffs_AddOrFi ndOrReplaceLevelOT node 更加恰當(dāng)。不過(guò)這個(gè)新名字也太長(zhǎng)了些 樹的創(chuàng)建、搜索和擴(kuò)展說(shuō)完了，下面該說(shuō)什么？對(duì)了，收縮和刪除。不過(guò)看過(guò)創(chuàng)建搜索擴(kuò)展之后，收縮和刪除已經(jīng)沒什么味道了。主要函數(shù)有：yaffs_DeleteWorker()yaffs_SoftDeleteWorker()yaffs_Pru neWorker(

45、)前兩者用于刪除，第三個(gè)用于收縮。都是從 levelO開始，以遞歸的方式從葉節(jié)點(diǎn)向上刪， 并釋放被刪除Tnode所對(duì)應(yīng)的物理chunk。遞歸，偉大的遞歸啊俺不想把這篇文章做成遞歸算法教程，除了遞歸這三個(gè)函數(shù)也就不剩啥了，所以一概從略。唯一要說(shuō)的就是 yaffs_DeleteWorker和yaffs_SoftDeleteWorker的區(qū)別，這兩個(gè)函數(shù)非常類似，只是在釋放物理chunk的時(shí)候分別調(diào)用 yaffs_DeleteChunk和yaffs_SoftDeleteChunk。其中函 數(shù) yaffs_DeleteWorker 在 yaffs2 中似乎是不用的，而 yaffs_SoftDelete

46、Worker 主要用于 在刪除文件時(shí)資源的釋放。7文件系統(tǒng)對(duì)象在yaffs2中，不管是文件還是目錄或者是鏈接，在內(nèi)存都用一個(gè)結(jié)構(gòu)體 yaffs_ObjectStruct來(lái)描述。我們先簡(jiǎn)要介紹一下這個(gè)結(jié)構(gòu)體中的幾個(gè)關(guān)鍵字段，然后再來(lái)看代碼。在后文中提到文件”或 文件對(duì)象”，若不加特別說(shuō)明，都指廣義的文 件”既可以是文件，也可以是目錄。_u8 deleted; /* This should only apply to unlinked files. */_u8 softDeleted:1; /* it has also bee n soft deleted */_u8 unlin ked:1; /

47、* An unlinked file. The file should be in the unlin keddirectory.*/這三個(gè)字段用于描述該文件對(duì)象在刪除過(guò)程中所處的階段。在刪除文件時(shí)，首先要將文件 從原目錄移至一個(gè)特殊的系統(tǒng)目錄/unlinked，以此拒絕應(yīng)用程序?qū)υ撐募脑L問，此時(shí)將unlinked置1;然后判斷該文件長(zhǎng)度是否為0，如果為0,該文件就可以直接刪除，此時(shí)將deleted置1;如果不為0，就將deleted和softDelted都置1，表明該文件數(shù)據(jù)所占據(jù) 的chunk還沒有釋放，要留待后繼處理。struct yaffs_ObjectStruct *pare nt

48、;看名字就知道，該指針指向上層目錄。int chun kId;每個(gè)文件在flash上都有一個(gè)文件頭，存儲(chǔ)著該文件的大小、所有者、創(chuàng)建修改時(shí)間等信 息。chunkld就是該文件頭在 flash上的chunk序號(hào)。_u32 objectId; /* the object id value */每一個(gè)文件系統(tǒng)對(duì)象都被賦予一個(gè)唯一的編號(hào)，作為對(duì)象標(biāo)識(shí)，也用于將該對(duì)象掛入一個(gè) 散列表，加快對(duì)象的搜索速度。yaffs_ObjectType varia ntType; yaffs_ObjectVaria nt varia nt;前者表示該對(duì)象的類型，是目錄、普通文件還是鏈接文件。后者是一個(gè)聯(lián)合體，根據(jù)對(duì)象

49、類型的不同有不同的解釋。其余的成員變量，我們?cè)诤竺娼Y(jié)合函數(shù)一起分析。下面我們來(lái)看相關(guān)的函數(shù)。先看一個(gè)簡(jiǎn)單的：static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device * dev, int nu mber,_u32 mode)所謂Fake Directory，就是僅存在于內(nèi)存中，用于管理目的的目錄對(duì)象，比如我們上面提 到的unlinked目錄。這種類型的目錄有一些特別的地方，如禁止改名、禁止刪除等。由于對(duì)象僅存在于內(nèi)存中，因此不涉及對(duì)硬件的操作，所以函數(shù)體很簡(jiǎn)單。首先通過(guò) yaffs_CreateNewObject獲得一個(gè)新對(duì)象，然后

50、對(duì)其中的一些字段初始化。先把字段初始化看一下，順便再介紹一些字段：renameAllowed表示是否允許改名，對(duì)于 fake對(duì)象為0;unlinkAllowed表示是否允許刪除，對(duì)于fake對(duì)象同樣為0;yst_mode就是linux中的訪問權(quán)限位；chunkld是對(duì)象頭所在 chunk，由于fake對(duì)象不占flash存儲(chǔ)空間，所以置 0?；剡^(guò)頭來(lái)看 yaffs_CreateNewObject :yaffs_CreateFakeDirectory - yaffs_CreateNewObject yaffs_Object *yaffs_CreateNewObject(yaffs_Device *

51、 dev, i nt nu mber, yaffs_ObjectType type)yaffs_Object *theObject;if (nu mber 0) nu mber = yaffs_CreateNewObjectNumber(dev);theObject = yaffs_AllocateEmptyObject(dev);前面說(shuō)過(guò)，每個(gè) yaffs_Object都有一個(gè)唯一的序列號(hào)，這個(gè)序號(hào)既可以在創(chuàng)建對(duì)象的時(shí) 候由上層函數(shù)指定，也可以由系統(tǒng)分配。如果number = 0;theObject- = 0; theObject- = OxFFFFFFFF; /* max _u32 */t

52、heObject- = 0;theObject- = yaffs_GetT no de(dev);break;case YAFFS_OBJECT_TYPE_DIRECTORY:INIT_LIST_HEAD(&theObject-;break;fileSize很好理解；topLevel就是映射樹層高，新建的文件層高為0。還要預(yù)先分配一組Tn ode供該對(duì)象使用。 sca nn edFileSize和shri nkSize用于yaffs2初始化時(shí)的flash掃描 階段，這里先跳過(guò)。如果該對(duì)象是目錄，那么所做的工作只是初始化子對(duì)象(就是該目錄下的文件或子目錄)雙向鏈表指針，前后指針都指向鏈表頭自身。看過(guò)Fake對(duì)象創(chuàng)建，我們?cè)倏纯雌胀▽?duì)