TFS Implementation

To cover all of the code in TFS would involve getting into details that are beyond the scope of this text. I will, however, use the remainder of this chapter to walk through the major blocks of TFS code. (The entire implementation is, of course, on the CD.) I will cover several key points in the design and implementation of TFS. The next few sections cover the process of flash defragmentation, file addition and deletion, the TFS file loader, file compression, and the ability to execute in place despite TFSs load model.

The Power-Safe Defragmentation Process

This defragmentation process conceptually shifts all of the active files in the TFS storage space toward the front of the flash address space and all of the space that was occupied by deleted files toward the end of the flash address space. After rearranging the files, the procedure erases all of the space following the last active file, making space that was occupied by inactive files available for new file storage. At first glance, this process doesnt sound too complicated, but there is one complicating gotcha. At any point in the defragmentation process, the hardware can be reset or powered off, and the defragmentation algorithm needs to be able to recover without losing any of the files that existed in TFS prior to the start of the interrupted defragmentation.

We start with an example TFS space containing seven sectors for storage and a spare sector. For this discussion, I am assuming that all the sectors are of equal size but that is not a requirement. The example in Figure 7.4 shows TFS space with four files (F1, F2, F3, and F4), two areas of dead space (deleted files), a small amount of available space, and the space needed for defragmentation overhead (spare sector and state storage).

Note that the relative sizes are inaccurate (typically, a header is about 92 bytes, and a sector can range in size from 2K to 256K, depending on the device).

Figure 7.4: Example File Store Configuration.

This figure shows how TFS space might be allocated after the system had been in use for a while. The segments labelled F1, F2, F3, and F4 are active files. Notice that there are also segments of dead space associated with deleted files.

Defragmentation becomes necessary when the file you want to add is larger than the available space but not larger than the total available space plus all of the dead space fragments . The goal is to push all of the files to the left (lower address) and all of the dead space to the right (higher address space). This process turns the dead space into available space, allowing TFS to append a new file to the linear list. The three high-level steps to this defragmentation algorithm are:

1. DSI Creation Build the defragmentation state information (DSI) based on the current state of the sectors and active (non-deleted) files. The DSI consists of three parts : a sector CRC table (SCT), a post-defragmentation header table (DHT), and a CRC of the two tables (DSICRC).

2. File Relocation Start with the first sector of TFS space and perform the following steps on each sector:

   • Determine if anything is to change within the sector. If not, increment to the next sector.

   • Copy the sector to be modified (the active sector) to the spare sector.

   • Erase the active sector.

   • Using the information in the DHT, scan through each non-deleted file to see if any part of it (header or data) is to be relocated into the active sector. This process must take into account the fact that the file transfer can be from a later sector or from the spare sector (depending on from where the file is relocated ).

3. Cleanup Clean up all remaining space after the last relocated file (so that the space becomes part of the new block of available space), and erase the spare sector.

The SCT contains two 32-bit CRCs per sector. The SCT is a fixed size, based on the number of sectors in the TFS area covered by the table. The CRCs in this table are used to help a restarted defragmentation process figure out which sectors have already been defragmented, thus allowing the restart to continue from where it was interrupted. The DHT contains one header per non-deleted file. This header is not a file header; it is the data needed by the defragmentation process to relocate each file to its new space in flash memory. After both the SCT and DHT have been constructed in flash memory, a 32-bit CRC of those tables is placed at the base of the DSI space as a mechanism to verify that the DSI space is valid. The DSI area is considered under construction if any of the area is not erased but the CRC test fails.

The defragmentation initiation routine is coded as a nested loop. The outer loop steps through each sector dedicated to TFS for file storage. At any point in time, only one sector is considered to be the active sector. The first step in the outer loop is to determine if anything in the sector is going to change as a result of the defragmentation. If not, then the outer loop steps to the next sector. Prior to any work (flash writes ) being done on the active sector, the active sector is copied to the spare and then erased. At this point, the inner loop begins. For each file in the DHT, the innerloop determines if the space that the file will occupy after relocation overlaps the active sector in any way. If an overlap occurs, then that portion of the file is copied to the active sector. Note that the portion copied could be the entire file or any sub-section of the file for example, the header and part of the data, part of the header, or part of the data. How much is copied depends on how the relocated version of the file overlaps the active sector.

Note that the source of the copy may be a later sector (some TFS sector after the currently active sector) or the spare sector. The source data will be in the spare if the relocated file is moved from some location that was previously in the now active sector. Figures7.57.10 give a pictorial view of the relocation process for the example TFS configuration.

In Figure 7.5, the first sector (sector 8) is copied to the spare and erased. Then the data that is destined to reside in sector 8 after defragmentation is copied back into sector 8. Notice that some of the data comes from the spare sector and some from a later sector.

Figure 7.5: Defragmentation Active Sector = 8.

During the first cycle of the defragmentation cycle, the first sector (sector 8) is copied to the spare sector, and then it is refilled with a compacted image. Note that the compaction operation can bring material from anywhere in the file system.

Figure 7.6 repeats this process with sector 9. The data in the active sector is copied to the spare sector, the active sector is erased, and the new data is copied into the active sector. Some data comes from the spare sector, and some from a later sector.

Figure 7.6: Defragmentation Active Sector = 9.

This figure details the defragmentation cycle for sector 9.

Figure 7.7 is almost the same. Notice that sector 10 is the active sector copied to the spare sector, but that nothing is copied back from that spare sector to the active sector. Since nothing from sector 10s original contents is retained, there is really no need to copy the active sector. I only show this step for clarity. The next two figures (Figure 7.8 and Figure 7.9) finish up the defragmentation on active sectors 11 and 12, applying the same process.

Figure 7.7: Defragmentation Active Sector = 10.

This figure details the defragmentation cycle for sector 10.

Figure 7.8: Defragmentation Active Sector = 11.

This figure details the defragmentation cycle for sector 11.

Figure 7.9: Defragmentation Active Sector = 12.

This figure details the defragmentation cycle for sector 12.

Figure 7.10: Defragmentation Clean Up and Completion.

After sector 12 is processed , all that remains is to clean up and erase sectors 13, 14 and 15. Figure 7.10 shows the final result of the defragmentation, along with a shadow image of where the dead space has been shifted conceptually (the shortest segments after the last file). Notice that the size of the available space has significantly increased.

The Non-Power-Safe tfsclean() Function

Returning to the opposite end of the complexity spectrum, the non power-safe defragmentation algorithm mentioned on page145 can be coded quite simply. The function that does the defragmentation is called tfsclean() (see Listing 7.3). This function takes a single parameter, a TDEV structure pointer. The TDEV structure tells tfsclean() which flash device to defragment (there may be multiple flash devices in TFS).

Listing 7.3: tfsclean() .

 int _tfsclean(TDEV *tdp) {     TFILE   *tfp;     uchar   *tbuf;     ulong   appramstart;     int     dtot, nfadd, len, err;     if (TfsCleanEnable < 0)         return(TFSERR_CLEANOFF);     appramstart = getAppRamStart();     /* Determine how many "dead" files exist. */     dtot = 0;     tfp = (TFILE *)tdp->start;     while(validtfshdr(tfp)) {         if (!TFS_FILEEXISTS(tfp))             dtot++;         tfp = nextfp(tfp,tdp);     }     if (dtot == 0)         return(TFS_OKAY);     printf("Reconstructing device %s with %d dead file%s removed...\n",         tdp->prefix, dtot,dtot>1 ? "s":"");     tbuf = (char *)appramstart;     tfp = (TFILE *)(tdp->start);     nfadd = tdp->start;     while(validtfshdr(tfp)) {         if (TFS_FILEEXISTS(tfp)) {             len = TFS_SIZE(tfp) + sizeof(struct tfshdr);             if (len % TFS_FSIZEMOD)                 len += TFS_FSIZEMOD - (len % TFS_FSIZEMOD);             nfadd += len;             err = tfsmemcpy(tbuf,(uchar *)tfp,len,0,0);             if (err != TFS_OKAY)                 return(err);             ((struct tfshdr *)tbuf)->next = (struct tfshdr *)nfadd;             tbuf += len;         }         tfp = nextfp(tfp,tdp);     }     /* Erase the flash device: */     err = _tfsinit(tdp);     if (err != TFS_OKAY)         return(err);     /* Copy data placed in RAM back to flash: */     err = AppFlashWrite((ulong *)(tdp->start),(ulong *)appramstart,         (tbuf-(uchar*)appramstart));     if (err < 0)         return(TFSERR_FLASHFAILURE);     return(TFS_OKAY); } 

 

This function first checks to see if defragmentation has been disabled for some reason (see Listing 7.3). If so, it returns TFSERROR_CLEANOFF . The copy must have RAM space into which to concatenate all the active files. I assume that it can use the RAM immediately above the end of the .bss space used by MicroMonitor. The function getAppRamStart() returns a pointer to the start of this RAM. The tfsclean() function blindly assumes there is enough RAM space here to cover the possibility that the entire TFS flash device might be copied. (The memory map of the application must take this possibility into account.) The code scans through the file list of the specified device looking for files that have been deleted. If no deleted files exist, there is no need to do any cleanup, allowing an early, successful return.

The second while() loop performs the actual copy and concatenation. Each active file is copied back-to-back into the RAM space, starting at appramstart . Notice that the next pointer in each TFS header is updated in the copied header so that the new header properly reflects the fact that the file is in different flash space. Upon completion of the concatenation, the flash space allocated to TFS file storage is erased with the call to tfsinit() , using the same TDEV structure pointer that was passed to tfsclean() . The final step, now that the flash memory has been erased, is to copy all of the concatenated files from RAM back to the base of the flash device.