Wiley.Symbian.OS.Internals.Real.time.Kernel.Programming.Dec.2005.eBook-DDU (779891), страница 78
Текст из файла (страница 78)
As I mentioned earlier, the LFFS undoesinvalid operations, and reclaims the space they consume.9.4.2.3 File and directory structureNormal file and directory data storage is completely separate from the log.This data is arranged into File Data Blocks (FDBs), which are, by default,512 bytes in size. However, you could build the LFFS to use larger blocks(up to 4 KB) by changing a constant in one of its configuration headerfiles.
Although using a fixed data block size is wasteful of memory forsmall files, this allows the FDB pointer information to use an FDB indexrather than an absolute address, which reduces the data managementoverhead.Each FDB has an associated log entry that describes the purpose of theblock and provides a pointer to it.
However, the log is mainly intendedas a record of changes and does not provide a permanent mechanismto track the FDBs that hold a file’s data. Instead, the LFFS uses threestructures to hold this information.The first of these structures is an I-node. Each file has a single I-nodethat holds file-specific data, such as the file type, the file size and a uniqueI-node number (which is essential in identifying the file).An I-node also contains fourteen FDB pointers. These are known asthe direct pointers, and they hold address information for up to fourteenFDBs that make up the file.
With an FDB size of 512 bytes, this structurealone can handle files of up to 7 KB. For larger files, a second structureis involved – the indirect block (IDB). IDBs contain 64 pointers, eachaddressing either FDBs or further IDBs. The LFFS supports up to fourlayers of IDBs, giving a maximum file size of approximately 8 GB. AnI-node has an indirect pointer for each layer of IDBs.The organization of a file with a first-level IDB is shown in Figure 9.13.The LFFS gives the FDBs in a file sequential numbers, starting at zero.
Itgives IDBs the same number as the first FDB that they point to.370THE FILE SERVERFDB#0DirectpointersFDB#1FDB#13I-NodeFDB#14IndirectpointerFDB#15IDB#14Level 1IndirectBlockFDB#77Figure 9.13 The organization of files in the LFFS which uses a first level IDBThe following table lists the fields contained in an I-node:FieldSize (in bytes)DescriptionI-node number4The I-node number of the file.Reference count2The number of directory entries referring tothis I-node. This is always 1.File type2The type of file referred to by the I-node.
Thevalue can be any of the following:1 = User data file2 = Directory file3 = Metadata file.File length4The number of data bytes in the file.Data block size4The size of the FDBs referred to by theI-node and IDBs.Direct pointers4 * 14Pointers to the first 14 FDBs in the file. Thefirst pointer is to FDB#0, the second is toFDB#1, etc.FILE SYSTEMSFieldSize (in bytes)371DescriptionIndirect pointer L14Pointer to a level 1 IDB. The IDB containspointers to the FDBs following those foundthrough the direct pointers.Indirect pointer L24Pointer to a level 2 IDB. The IDB is the rootof a 2 level tree with pointers to the FDBsfollowing those found through Indirectpointer L1.Indirect pointer L34Pointer to a level 3 IDB. The IDB is the rootof a 3 level tree with pointers to the FDBsfollowing those found through Indirectpointer L2.Indirect pointer L44Pointer to a level 4 IDB.
The IDB is the rootof a 4 level tree with pointers to the FDBsfollowing those found through Indirectpointer L3.The LFFS uses a third structure to track the I-nodes: the LFFS partitioncontains a single I-file, which holds an array of pointers to the I-nodes.It adds new I-node references to the I-file at the array entry given by theI-node number. When it deletes a reference to an I-node from the I-file,it sets the array entry to zero.
This indicates that the I-node is not in useany more, and a new file can reuse the I-node number.Collectively, these FDB tracking structures are known as the LFFSmetadata. However, the metadata doesn’t hold filename or directoryinformation. Instead, we store this information in directory files.
Theseare really just normal data files, except that they are used by the filesystem, and are not directly visible to clients. A directory file contains anentry for each file in that directory. Directory entries contain the name ofthe file and the number of the I-node that points to the file’s data blocks.A directory entry’s size depends on the length of the filename, which canbe at most 256 characters.I-node number 2 always points to the root directory.9.4.2.4 SegmentsTo manage the erasing of blocks, the LFFS uses the notion of a segment.
Asegment is the smallest unit of media space that the file system can eraseand consists of one or more consecutive erase blocks. The LFFS viewsthe entire NOR device as a consecutive series of segments. It stores logentries and data entries (file data blocks and metadata) into each segment.372THE FILE SERVERIt stores the log starting at the bottom of the segment growing upwards,and the data entries at the top, growing downwards. Figure 9.14 showsthe layout of a segment.Data entriesgrow down fromhighest addressnew data entriesadded herenew log entriesadded hereLog entries growup from lowestaddressFigure 9.14The layout of an individual LFFS segmentIn this way, the log is split across segments, but log entries alwaysoccupy the same segment as their corresponding data entries.
The LFFSadds log and data entries to the current segment until that segmenteventually becomes full – at which point it moves on to the next erasedsegment.Figure 9.15 shows a section of an LFFS partition containing foursegments. The segment 2 is the current segment. Segment 1 is full, butsegments 3 and 4 are empty.As it adds and modifies file data, the LFFS moves on from one segmentto the next, until it approaches a point where it is running out of mediaspace. However, the total amount of valid data on the device will almostcertainly be much less than the capacity of the device.9.4.2.5 Reclaiming outdated media spaceWhen file data is modified, the LFFS has to replace each FDB affected. Itadds the replacement FDBs together with their associated log entries toFILE SYSTEMS373Keyemptyuser datalog1234Figure 9.15 The organization of the LFFS across multiple segmentsthe current segment.
At this point, the old FDBs and associated log entrieshave become out-dated. The LFFS will eventually have to reclaim thisspace to allow further updates to the drive. However, the LFFS has not yetfinished the file update, since it must also change the metadata to point tothe new FDBs. This means modifying the file’s I-node and IDBs – whichwill generate yet more out-dated log and data entries. (However, as I willexplain in Section 9.4.2.6, this metadata update is deferred until later.)When file data is deleted, this also leaves out-dated log and data entries,which the LFFS needs to reclaim.Reclaiming out-dated media space is not simple, as this space willnormally be spread across many segments, and these segments will alsocontain valid data.
The reclaim process has to identify the segment withthe largest amount of dirty data, copy any valid data from that segment,and then erase the segment allowing it to become active again. The LFFScan’t allow the device to run out of free space before it attempts a reclaim,because it needs reserve space into which to move the valid data beforeerasing. It has to reserve at least a segment to ensure this does not happen.The choice of which segment to reclaim is actually more complexthan I have just described. I mentioned earlier that Flash blocks have alimit on the number of erase cycles they can handle. To mitigate this,the LFFS employs a wear-leveling scheme.
This scheme aims to keep theerase count of each of the segments roughly equal, to avoid prematurefailure due to some blocks being used more than others. The LFFS storesthe erase count of each segment in a segment header, and the reclaimalgorithm takes this into account when identifying the next segment forreclaim. It avoids a segment containing a lot of dirty data but with a higherase count.Reclaiming a segment can be a slow process. First, the LFFS mustcopy valid data to another segment, and then it must erase the blockscontained by that segment. If the LFFS did not perform space reclamationuntil it needed space to service a request, then its performance would be374THE FILE SERVERpoor. Instead, the LFFS tries to reclaim early by using a reclaim thread.This is a low priority thread that uses what would otherwise be CPU idletime to reclaim data.9.4.2.6 Roll forwardWhen the user modifies a file, the LFFS does not update the metadataas part of the same transaction that updates the FDBs.
Instead it defersthe metadata update until later. It can do this because it can extractthe information it needs from the log. We call this update of metadatafrom the log ‘‘roll-forward’’. To improve performance, the LFFS generallyperforms roll-forward in batches, using the same low priority backgroundthread that it uses to perform early reclaim. If power is lost after the LFFShas updated the FDBs, but before it updates the metadata, then the writeoperation is still regarded as successful, because the LFFS can rebuild themetadata from the log when power is restored.However, the LFFS cannot allow too many metadata updates to accumulate, because this affects reclaiming.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
