FTL

From freemyipod.org
Jump to: navigation, search

The Nano 2G (and above) uses an FTL (Flash Translation Layer) from Whimory, which has a lot of similarities to the one implemented in openiboot, but seems to be a slightly older version.

The FTL is divided into two parts, the VFL (virtual flash layer?) and the FTL (flash translation layer).

The following has been reverse-engineered from the Nano 2G implementation of the FTL, but is likely accurate for subsequent releases.

Terminology

  • Logical page (lPage): A logical page (sector) number, as seen by the file system. The FTL block map is used to translate those into vPages.
  • Virtual page (vPage): A VFL page number, which is translated to pPages by adding a constant, or by a remap table lookup if that block is marked as bad.
  • Physical page (pPage): A physical page number on the flash.
  • The same prefixes also apply to blocks. "vBlock" and "lBlock" usually refer to hyperblocks. (Those are on top of the VFL, which handles the bank interleaving.)
  • Hyperblock: One block across all banks.
  • System (hyper)blocks: All hyperblocks until the start of the "Virtual blocks (directly mapped)" area in the diagram below.
  • System pages: All the pages in the system hyperblocks.

On-Flash layout

(assuming that all pages are good, part of it might be moved
 if there are bad pages, which is not fully understood yet.)
 ____________________________________________________
|                 Block 0: Signature                 |
|----------------------------------------------------|
|                4 VFL context blocks                |
|----------------------------------------------------|
|             Spare blocks for remapping             |
|----------------------------------------------------|
|          Virtual blocks (directly mapped)          |
|- - - - - - - - - - - - - --------------------------|
| Last few virtual blocks, |                         |
| always marked as bad to  |   Low level signature   |
| protect overlapping low  |     and BBT blocks      |
| level BBT and signature  |                         |
|__________________________|_________________________|

The lowlevel BBT

This is just a bitmap of all blocks on the flash. 1 means good, 0 means bad. The LSB of the first byte is block 0, the MSB block 7, ...

The VFL

The VFL is responsible for bad block handling, and emulates a "clean" flash to the FTL. It also contains some information about where to find the FTL context. When a block goes bad, it will be remapped to a spare block near the beginning of the flash. ftl_vfl_cxt_type.remaptable will keep track of those remaps. Each bank has its own independent VFL.

VFL context

 /* Keeps the state of the bank's VFL, both on flash and in memory.
    There is one of these per bank. */
 struct ftl_vfl_cxt_type
 {
 
   /* Cross-bank update sequence number, incremented on every VFL
      context commit on any bank. */
   uint32_t usn;
 
   /* See ftl_cxt.ftlctrlblocks. This is stored to the VFL contexts
      in order to be able to find the most recent FTL context copy
      when mounting the FTL. The VFL context number this will be
      written to on an FTL context commit is chosen semi-randomly. */
   uint16_t ftlctrlblocks[3];
 
   /* Alignment to 32 bits */
   uint8_t field_A[2];
 
   /* Decrementing update counter for VFL context commits per bank */
   uint32_t updatecount;
 
   /* Number of the currently active VFL context block, it's an index
      into vflcxtblocks. */
   uint16_t activecxtblock;
 
   /* Number of the first free page in the active VFL context block */
   uint16_t nextcxtpage;
 
   /* Seems to be unused */
   uint8_t field_14[4];
 
   /* Incremented every time a block erase error leads to a remap,
      but doesn't seem to be read anywhere. */
   uint16_t field_18;
 
   /* Number of spare blocks used */
   uint16_t spareused;
 
   /* pBlock number of the first spare block */
   uint16_t firstspare;
 
   /* Total number of spare blocks */
   uint16_t sparecount;
 
   /* Block remap table. Contains the vBlock number the n-th spare
      block is used as a replacement for. 0 = unused, 0xFFFF = bad. */
   uint16_t remaptable[0x334];
 
   /* Bad block table. Each bit represents 8 blocks. 1 = OK, 0 = Bad.
      If the entry is zero, you should look at the remap table to see
      if the block is remapped, and if yes, where the replacement is. */
   uint8_t bbt[0x11A];
 
   /* pBlock numbers used to store the VFL context. This is a ring
      buffer. On a VFL context write, always 8 pages are written,
      and it passes if at least 4 of them can be read back. */
   uint16_t vflcxtblocks[4];
 
   /* Blocks scheduled for remapping are stored at the end of the
      remap table. This is the first index used for them. */
   uint16_t scheduledstart;
 
   /* Probably padding */
   uint8_t field_7AC[0x4C];
 
   /* First checksum (addition) */
   uint32_t checksum1;
 
   /* Second checksum (XOR), there is a bug in whimory regarding this. */
   uint32_t checksum2;
 
 } __attribute__((packed));

VFL mounting procedure

  • Search the last 10% of the flash downwards for a block with at least one of the last 8 pages starting with "DEVICEINFOSIGN\0\0". That page is supposed to also have "BBT\0" at 0x18.
  • Look for the BBT in the pages below, according to a scheme specified by that DEVICEINFOSIGN page. In the dumps I've seen, this was always searching the lower (pagesperblock-8) pages in ascending order, until a readable page was found. The data in that page is then used as the lowlevel BBT.
  • Scan the blocks from 1 to the end of the spare area for non-bad blocks where at least one of the first 8 pages is readable and of type 0x80 (VFL context page). Grab the VFL context block numbers from it.
  • Try to read the first 8 pages of the VFL context block, and remember which of the blocks had the highest USN.
  • Read as many pages as possible in that block, and use the last page that was read successfully as the VFL context.
  • Verify the VFL context checksum

vPage read procedure

  • First, the vPage number is translated to a pPage number by adding the number of system pages to it. Then the bank interleaving (round-robin) is applied, so the resulting page number will be divided by the number of banks. The block number of the resulting page is calculated, and a VFL BBT lookup is being done for that block. If the block is bad, the read will be remapped to a block in the spare area. (To the same page number within the block)
  • The resulting pPage will be read, and the code will return if the read was successful.
  • If there was an error, the read will be retried once. If it still didn't work, the pBlock will be scheduled for remapping.

vPage write procedure

  • First, the vPage number is translated to a pPage number by adding the number of system pages to it. Then the bank interleaving (round-robin) is applied, so the resulting page number will be divided by the number of banks. The block number of the resulting page is calculated, and a VFL BBT lookup is being done for that block. If the block is bad, the write will be remapped to a block in the spare area. (To the same page number within the block)
  • The resulting pPage will be written, and the code will return if the write was successful.
  • If there was an error, page will be read back. If the resulting data is consistent (in terms of ECC, the contents *aren't* being compared), return success.
  • If it still didn't work, a problem with that pBlock will be logged (3 problem points). If there are more than 5 problem points for a block, it will be scheduled for remapping.

vBlock erase procedure

  • First, the vBlock number is translated to a pBlock number by adding the number of system hyperblocks to it.
  • If remapping is scheduled for the pBlock, remap it.
  • Remove one problem point from that pBlock, if there are some.
  • Follow the pBlock remapping, if it exists.
  • Erase the pBlock (up to 3 tries, if needed).
  • If all 3 tries failed:
    • If the block was already remapped, mark the spare block it was mapped to as bad. (And thereby un-remap it)
    • Remap the pBlock and commit the VFL context.
    • Try to overwrite the spare bits of the (bad) pBlock with zeroes to invalidate it.

VFL context update procedure

  • Yet to be documented

VFL context checksums

 /* Calculates the checksums for the VFL context page of the specified bank */
 void ftl_vfl_calculate_checksum(uint32_t bank,
                                 uint32_t* checksum1, uint32_t* checksum2)
 {
   uint32_t i;
   *checksum1 = 0xAABBCCDD;
   *checksum2 = 0xAABBCCDD;
   for (i = 0; i < 0x1FE; i++)
   {
     *checksum1 += ((uint32_t*)(&ftl_vfl_cxt[bank]))[i];
     *checksum2 ^= ((uint32_t*)(&ftl_vfl_cxt[bank]))[i];
   }
 }
 
 /* Checks if the checksums of the VFL context
    of the specified bank are correct */
 uint32_t ftl_vfl_verify_checksum(uint32_t bank)
 {
   uint32_t checksum1, checksum2;
   ftl_vfl_calculate_checksum(bank, &checksum1, &checksum2);
   if (checksum1 == ftl_vfl_cxt[bank].checksum1) return 0;
   /* The following line is pretty obviously a bug in Whimory,
      but we do it the same way for compatibility. */
   if (checksum2 != ftl_vfl_cxt[bank].checksum2) return 0;
   return 1;
 }

The FTL

The FTL is responsible for handling writes that are smaller than the smallest eraseable unit (1 "hyperblock") and performs wear leveling.

FTL Context

 /* Keeps the state of the FTL, both on flash and in memory */
 struct ftl_cxt_type
 {
 
   /* Update sequence number of the FTL context, decremented
      every time a new revision of FTL meta data is written. */
   uint32_t usn;
 
   /* Update sequence number for user data blocks. Incremented
      every time a portion of user pages is written, so that
      a consistency check can determine which copy of a user
      page is the most recent one. */
   uint32_t nextblockusn;
 
   /* Count of currently free pages in the block pool */
   uint16_t freecount;
 
   /* Index to the first free hyperblock in the blockpool ring buffer */
   uint16_t nextfreeidx;
 
   /* This is a counter that is used to better distribute block
      wear. It is incremented on every block erase, and if it
      gets too high (300 on writes, 20 on sync), the most and
      least worn hyperblock will be swapped (causing an additional
      block write) and the counter will be decreased by 20. */
   uint16_t swapcounter;
 
   /* Ring buffer of currently free hyperblocks. nextfreeidx is the
      index to freecount free ones, the other ones are currently
      allocated for scattered page hyperblocks. */
   uint16_t blockpool[0x14];
 
   /* Alignment to 32 bits */
   uint16_t field_36;
 
   /* vPages where the block map is stored */
   uint32_t ftl_map_pages[8];
 
   /* Probably additional map page number space for bigger chips */
   uint8_t field_58[0x28];
 
   /* vPages where the erase counters are stored */
   uint32_t ftl_erasectr_pages[8];
 
   /* Seems to be padding */
   uint8_t field_A0[0x70];
 
   /* Pointer to ftl_map used by Whimory, not used by us */
   uint32_t ftl_map_ptr;
 
   /* Pointer to ftl_erasectr used by Whimory, not used by us */
   uint32_t ftl_erasectr_ptr;
 
   /* Pointer to ftl_log used by Whimory, not used by us */
   uint32_t ftl_log_ptr;
 
   /* Flag used to indicate that some erase counter pages should be committed
      because they were changed more than 100 times since the last commit. */
   uint32_t erasedirty;
 
   /* Seems to be unused */
   uint16_t field_120;
 
   /* vBlocks used to store the FTL context, map, and erase
      counter pages. This is also a ring buffer, and the oldest
      page gets swapped with the least used page from the block
      pool ring buffer when a new one is allocated. */
   uint16_t ftlctrlblocks[3];
 
   /* The last used vPage number from ftlctrlblocks */
   uint32_t ftlctrlpage;
 
   /* Set on context sync, reset on write, so obviously never
      zero in the context written to the flash */
   uint32_t clean_flag;
 
   /* Seems to be unused, but gets loaded from flash by Whimory. */
   uint8_t field_130[0x15C];
 
 } __attribute__((packed));

FTL mounting procedure

  • Make sure the VFLs are mounted
  • Get the FTL context vBlock numbers from the most-recently updated VFL context
  • Read the first page of the FTL context vBlocks. Remember the number of the vBlock that contains the readable FTL meta page (of any kind) with the highest USN as it's first page.
  • Start reading pages from the end of that hyperblock, until a readable page is hit. If it is an FTL context page, use that as the FTL context, else complain about an unclean shutdown.
  • Read the block map and erase counter pages pointed to by the FTL context
  • Initialize the scattered page, problem log and erase counter dirt information.

lPage read procedure

  • Calculate the lBlock number from the lPage, and look it up in the block map. Use the same page number within the block.
  • If there is a scattered page entry for the lBlock, that contains the requested page, use that instead.
  • Read the vPage
  • If it was unprogrammed, return an all-zero result.
  • If there was an error, zero the result and return an error.

lPage write procedure

  • Yet to be documented

FTL sync/shutdown procedure

  • Yet to be documented

FTL context update procedure

  • Yet to be documented

Error handling

  • Yet to be documented

Scattered page blocks

  • Yet to be documented

Page metadata (spare bytes)

 /* Layout of the spare bytes of each page on the flash */
 union ftl_spare_data_type
 {
 
   /* The layout used for actual user data (types 0x40 and 0x41) */
   struct ftl_spare_data_user_type
   {
 
     /* The lPage, i.e. Sector, number */
     uint32_t lpn;
 
     /* The update sequence number of that page,
        copied from ftl_cxt.nextblockusn on write */
     uint32_t usn;
 
     /* Seems to be unused */
     uint8_t field_8;
 
     /* Type field, 0x40 (data page) or 0x41
        (last data page of hyperblock) */
     uint8_t type;
 
     /* ECC mark, usually 0xFF. If an error occurred while reading the
        page during a copying operation earlier, this will be 0x55. */
     uint8_t eccmark;
 
     /* Seems to be unused */
     uint8_t field_B;
 
     /* ECC data for the user data */
     uint8_t dataecc[0x28];
 
     /* ECC data for the first 0xC bytes above */
     uint8_t spareecc[0xC];
 
   } __attribute__((packed)) user;
 
   /* The layout used for meta data (other types) */
   struct ftl_spare_data_meta_type
   {
 
     /* ftl_cxt.usn for FTL stuff, ftl_vfl_cxt.updatecount for VFL stuff */
     uint32_t usn;
 
     /* Index of the thing inside the page,
        for example number / index of the map or erase counter page */
     uint16_t idx;
 
     /* Seems to be unused */
     uint8_t field_6;
 
     /* Seems to be unused */
     uint8_t field_7;
 
     /* Seems to be unused */
     uint8_t field_8;
 
    /* Type field:
         0x43: FTL context page
         0x44: Block map page
         0x46: Erase counter page
         0x47: "FTL is currently mounted", i.e. unclean shutdown, mark
         0x80: VFL context page */
     uint8_t type;
 
     /* ECC mark, usually 0xFF. If an error occurred while reading the
        page during a copying operation earlier, this will be 0x55. */
     uint8_t eccmark;
 
     /* Seems to be unused */
     uint8_t field_B;
 
     /* ECC data for the user data */
     uint8_t dataecc[0x28];
 
     /* ECC data for the first 0xC bytes above */
     uint8_t spareecc[0xC];
 
   } __attribute__((packed)) meta;
 
 };