# HG changeset patch # User Michael Spacefalcon # Date 1391299346 0 # Node ID 4eeab025b502b6ea1b92a1402e1ee739206f9f1d # Parent 475887e6b396144493e406ec955c6b90001ab324 doc/TIFFS-old-description: the original description from SE 52 Mes 16 diff -r 475887e6b396 -r 4eeab025b502 doc/TIFFS-old-description --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/TIFFS-old-description Sun Feb 02 00:02:26 2014 +0000 @@ -0,0 +1,461 @@ +The description of TIFFS that follows was originally written in the summer of +SE52 (A.D. 2013), before the major TI source discoveries which happened later +that year. The text following the dividing line below has not been edited in +content since it was written; for a newer write-up based on the current source- +enabled understanding and reflecting the current FreeCalypso plans with respect +to this FFS, see TIFFS-Overview. + +------------------------------------------------------------------------------- + +This is a description, based on reverse engineering, of the flash file system +(FFS) implemented in Pirelli's original firmware for the DP-L10 GSM/WiFi dual +mode mobile phone, and in the Closedmoko GTA0x modem firmware. Not knowing the +"proper" name for this FFS, and needing _some_ identifier to refer to it, I +have named it Mokopir-FFS, from "Moko" and "Pirelli" - sometimes abbreviated +further to MPFFS. + +(I have previously called the FFS in question MysteryFFS; but now that I've + successfully reverse-engineered it, it isn't as much of a mystery any more :-) + +At a high functional level, Mokopir-FFS presents the following features: + +* Has a directory tree structure like UNIX file systems; + +* The file system API that must be implemented inside the proprietary firmware + appears to use UNIX-style pathnames; doing strings on firmware images reveals + pathname strings like these: + + /var/dbg/dar + /gsm/l3/rr_white_list + /gsm/l3/rr_medium_rxlev_thr + /gsm/l3/rr_upper_rxlev_thr + /gsm/l3/shield + + Parsing the corresponding FFS image with tools included in the present + package has confirmed that the directory structure implied by these pathnames + does indeed exist in the FFS. + +* Absolutely no DOS-ish semantics seen anywhere: no 8.3 filenames and no + colon-separated device names (seen in the TSM30 file system source, for + example) are visible in the Closedmoko/Pirelli FFS. + +* File contents are stored uncompressed, but not necessarily contiguous: one + could probably store a file in FFS which is bigger than the flash sector + size, it which case it can never be contiguous in a writable FFS (see below), + and the firmware implementation seems to limit chunk sizes to a fairly small + number: on the Pirelli phones all largish files are divided into chunks of + 8 KiB each, and on my GTA02 the largest observed chunk size is only 2 KiB. + + The smaller files, like the IMEI and the firmware ID strings in my GTA02 FFS, + are contiguous. + +* The FFS structure is such that the length of "user" payload data stored in + each chunk (and consequently, in each file) can be known exactly in bytes, + with the files/chunks able to contain arbitrary binary data. (This property + may seem obvious or trivial, as all familiar UNIX and DOS file systems have + it, but contrast with RT-11 for example.) + +* The flash file system is a writable one: the running firmware can create, + delete and overwrite files (and possibly directories too) in the live FFS; + thus the FFS design is such that allows these operations to be performed + within the physical constraints of NOR flash write operations. + +I have reverse-engineered this Mokopir-FFS on a read-only level. What it means +is that I, or anyone else who can read this document and the accompanying +source for the listing/extraction utilities, can take a Mokopir-FFS image read +out of a device and see/extract its full content: the complete directory tree +and the exact binary byte content of all files contained therein. + +However, the knowledge possessed by the present hacker (and conveyed in this +document and the accompanying source code) is NOT sufficient for constructing a +valid Mokopir-FFS image "in vitro" given a tree of directories and files, or +for making modifications to the file or directory content of an existing image +and producing a content-modified image that is also valid; valid as in suitable +for the original proprietary firmware to make its normal read and write +operations without noticing anything amiss. + +Constructing "de novo" Mokopir-FFS images or modifying existing images in such +a way that they remain 100% valid for all read and write operations of the +original proprietary firmware would, at the very minimum, require an +understanding of the meaning of *all* fields of the on-media FFS format. Some +of these fields are still left as "non-understood" for now though: a read-only +implementation can get away with simply ignoring them, but a writer/generator +would have to put *something* in those fields. + +As you read the "read-only" description of the Mokopir-FFS on-media format in +the remainder of this document, it should become fairly obvious which pieces +are missing before our understanding of this FFS can be elevated to a +"writable" level. + +However, when it comes to writing new code to run on the two Calypso phones in +question (Closedmoko and Pirelli), it seems, at least to the present hacker, +that a read-only understanding of Mokopir-FFS should be sufficient: + +* In the case of Closedmoko GTA0x modems, the FFS is seen to contain the IMEI + and the RF calibration data. The format of the former is obvious; the latter + not so much - but in any case, the information of interest is clearly of a + read-only nature. It's difficult to tell (or rather, I haven't bothered to + experiment enough) whether the Closedmoko firmware does any writes to FFS or + if the FFS is treated as read-only outside of the production line environment, + but in any case, it seems to me that for any 3rd party replacement firmware, + the best strategy would be to treat the FFS as a read-only source of IMEI and + RF calibration data, and nothing more. + +* In the case of Pirelli phones, the FFS is used to store user data: sent and + received SMS (and MMS/email/whatever), call history, UI settings, pictures + taken with the camera, and whatever else. It also stores a ton of files + which I can only presume were meant to be immutable except at the time of + firmware updates: graphics for the UI, ringtones, i18n UI strings, and even + "helper" firmware images for the WiFi and VoIP processors. However, no IMEI + or RF calibration data are anywhere to be found in the FFS - instead this + information appears to be stored in the "factory block" at the end of the + flash (in its own sector) outside of the FFS. + + Being able to parse FFS images extracted out of Pirelli phones "in vitro" + allows us to steal some of these helper files (UI artwork, ringtones, + WiFi/VoIP helpers), and some of these might even come useful to firmware + replacement projects, but it seems to me that a replacement firmware would + be better off using its own FFS design for storing user data, and as to + retrieving the original IMEI and RF calibration data, the original FFS isn't + of any use for that anyway. + +======================= +Moko/Pirelli FFS format +======================= + +OK, now that I'm done with the introduction, we can get to the actual +Mokopir-FFS format. + +* On the GTA0x modem (or at least on my GTA02; my sample size is 1) the FFS + occupies 7 flash sectors of 64 KiB each at offsets 0x380000 through 0x3E0000, + inclusive. + +(The 4 MiB NOR flash chip used by Closedmoko has an independent R/W bank + division between the first 3 MiB and the last 1 MiB. The first 3 MiB are used + to hold the field-flashable closed firmware images distributed as *.m0 files; + the independent last megabyte holds the FFS, and thus the FW could be + implemented to do FFS writes while running from flash in the main bank. + Less than half of that last megabyte appears to be used for the FFS though; + the rest appears to be unused - blank flash observed.) + +* On the Pirelli the FFS occupies 18 sectors of 256 KiB each at offsets 0 + through 0x440000 (inclusive) of the 2nd flash chip select, the one wired to + nCS3 on the Calypso. + +Each flash sector allocated to FFS begins with the following signature: + +00000000: 46 66 73 23 10 02 xx yy zz FF FF FF FF FF FF FF Ffs#............ + +The bytes shown as xx and yy above serve a non-understood purpose; as a guess, +they may hold some info for the flash wear leveling algorithm: in a "virgin" +FFS image like that found in my GTA02 (which never had a SIM card in it and +never made or received a call) or read out of a "virgin" Pirelli phone that +hasn't seen any active use yet, both of these bytes are FFs, but when I look at +FFS images read out of the Pirelli which I currently use as my everyday-use +cellphone, I see other values in sectors which must have been erased and +rewritten. A read-only implementation can ignore these bytes, as mine does. + +The byte shown as zz is more important though, even to a read-only +implementation. The 3 values I've encountered in this byte so far are AB, BD +and BF. Per my current understanding, in a "healthy" FFS exactly one sector +will have AB in its header, exactly one will have BF, and the rest will have +BD. The meanings are (or appear to be): + +AB: the sector holds a vital data structure which I have called the active + index block; +BD: the sector holds regular data; +BF: the sector is blank except for the header, can be turned into a new AB or + BD. + +(Note that a flash program operation, which can turn 1s into 0s but not the + other way around, can turn BF into either AB or BD - but neither AB nor BD can + be turned into any other valid value.) + +In a "virgin" FFS image (as explained above) the first FFS sector is AB, the +last one is BF, and the ones in between are BDs. + +An FFS read operation (a search for a given pathname, or a listing of all +present directories and files) needs to start with locating the active index +block - the FFS sector with AB in the header. Following this header, which is +treated as being 16 bytes long (almost everything in Mokopir-FFS is aligned on +16-byte boundaries), the active index block contains a linear array of 16-byte +records, each record describing an FFS object: directory, file or file +continuation chunk. + +Here is my current understanding of the 16-byte index block record structure: + +2 bytes: Length of the described chunk in bytes +1 byte: Purpose/meaning not understood, ignored by my current code +1 byte: Object type +2 bytes: Descendant pointer +2 bytes: Sibling pointer +4 bytes: Data pointer +4 bytes: Purpose/meaning not understood, ignored by my current code + +(On the Calypso phones of interest, all multibyte fields are in the native + little-endian byte order of the ARM7TDMI processor.) + +The active index block gets filled with these records as objects are created; +the first record goes right after the 'Ffs#'...AB header (padded to 16 bytes); +the last record (at any given moment) is followed by blank flash for the +remainder of the sector. Records thus appear in the order in which they are +created, which bears no direct relation to the directory tree structure. + +The objects, each described by a record in the index block, are organized into +a tree structure by the descendant and sibling pointers, plus the object type +indicator byte. Let's start with the latter; the following objtype byte values +have been observed: + +00: deleted object - a read-only implementation should ignore everything except + the descendant and sibling pointers. (A write-capable implementation would + need more care - it would need a way of reclaiming dirty flash space taken + up by deleted/overwritten files.) + +E1: a special file - see the description of the /.journal file further down +F1: a regular file (head chunk thereof) +F2: a directory +F4: file continuation chunk (explained below) + +Each record in the index block has an associated chunk in one of the data +sectors; the index record contains fields giving the address and length of this +chunk. The length of a chunk is always a nonzero multiple of 16 bytes, and is +stored (as a number in bytes) in the first 16-bit field of the 16-byte index +entry. The address of each chunk is given by the data pointer field of the +index record, and it is reckoned in 16-byte units (thereby 16-byte alignment is +required) from the beginning of the FFS sector group in the flash address space. + +For objects of type F1 and F2 (regular files and directories) the just-described +chunk begins with the name of the file or subdirectory as a NUL-terminated ASCII +string. This name is just for the current level of the directory tree, just +like in UNIX directories, thus one will have chunk names like gsm, l3, eplmn +etc, rather than /gsm/l3/eplmn. One practical effect is that one can't readily +see pathnames or any of the directory structure by looking at an FFS image as a +raw hex dump; the structure is only revealed when one uses a parsing program +like those which accompany this document. + +In the case of directories, the "chunk" part of the object contains only the +name of the directory itself, padded with FFs to a 16-byte boundary. For +example, an FFS directory named /gsm would be represented by an object +consisting of two flash writes: a 16-byte entry in the active index block, with +the object type byte set to F2, and a corresponding 16-byte chunk in one of the +data sectors, with the 16 bytes containing "gsm", a terminating NUL byte, and +12 FF bytes to pad up to 16. In the case of files, this name may be followed +by the first chunk of file data content, as explained further down. + +In order to parse the FFS directory tree (whether the objective is to dump the +whole thing recursively or to find a specific file given a pathname), one needs +to first (well, after finding the active AB block) find the root directory node. +The root directory object is similar to other directory objects: it has a type +of F2, and an associated chunk of 16 bytes in one of the data sectors. The +latter contains the name of the root node: on the Pirelli it is "/", whereas on +my GTA02 it is "/ffs-root". + +The astute reader should notice that it really makes no sense to store a name +for the root node, and indeed, this name plays no part in the traversal of the +directory tree given an absolute pathname. But instead this name, or rather +its first character, appears to be used for the purpose of locating the root +node itself. At first I had assumed that the index record for the root node is +always the first record in the active index block right after the signature +header - that is how it is in "virgin" FFS images, and also in some quite non- +virgin ones I have pulled from my daily-use Pirelli. Naturally my first version +of the Mokopir-FFS (then called MysteryFFS) extraction utility expected the root +node to always be at index #1. But then I got some additional Pirelli phones, +and discovered that in certain cases, index record #1 is a deleted object (the +original root node which has been deleted), and the new active root node is +somewhere in the middle of the index! + +Thus it appears that in order to find the active root node, one needs to scan +the active index block linearly from the beginning (disregarding the tree +structure pointers in this initial pass), looking for a non-deleted object of +type F2 (a directory) whose corresponding name chunk sports a name beginning +with the '/' character. (Anyone who's been raised in UNIX will immediately +know that the path separator character '/' is the only character other than NUL +that's absolutely forbidden in the individual filenames - so this special +"root node name" is the only case of a '/' character appearing in what would +otherwise be a regular filename.) + +[What causes the root node to be somewhere other than at index #1? I assume it + has to do with the dirty space reclamation / data movement algorithm. In a + "virgin" FFS image the very first sector is the active index block, and the + following sector is the first to hold chunks, beginning with the name chunk of + the root node. Now what happens if all data in that sector aside from the + root node name and some other mostly-static directory names becomes dirty, + i.e., belonging to deleted or overwritten files? How would that flash space + get reclaimed? I assume that the FFS firmware algorithm moves all still-active + chunks to a new flash sector, invalidating the old copies - turning the latter + into deleted objects. The root node will be among them. Then at some point + the active index block is going to fill up too, and will need to be rewritten + into a new sector - at which point the previously-deleted index entries are + omitted and the root node becomes #1 again...] + +Tree structure + +Once the root node has been found, the descendant and sibling pointers are used +to traverse the tree structure. For each directory object, including the root +node, the descendant pointer points to the first child object of this directory: +the first file or subdirectory contained therein. (Descendant and sibling +pointers take the form of index numbers in the active index block. A "nil" +pointer is indicated by all 1s (FFFF) - the usual all-0s NULL pointer convention +couldn't be used because it's flash, where the blank state is all 1s.) If the +descendant pointer of a directory object is nil, that means an empty directory. +The sibling pointer of each file or directory points to its next sibling, i.e., +the next member of the same parent directory. The sibling pointer of the root +node is nil. + +Data content of files + +Objects of type F1 are the head chunks of files. Each file has a head chunk, +and may or may not have continuation chunks. More precisely, the head chunk +may contain only the name (or viewed alternatively, 0 bytes of data), or it may +contain a nonzero number of payload bytes; orthogonally to this variability, +there may or may not be continuation chunk(s) present. + +Continuation chunks + +The descendant pointer of each file head object (the object of type F1, the one +reached by traversing the directory tree) indicates whether or not there are +any continuation chunks present. If this descendant pointer is nil, there are +no continuation chunks; otherwise it points to the first continuation chunk +object. File continuation objects have type F4, don't have any siblings (the +sibling pointer is nil - but see below regarding relocated chunks), and the +descendant pointer of each continuation object points to the next continuation +object, if there is one - nil otherwise. + +Payload data delineation + +Each chunk, whether head or continuation, always has a length that is a nonzero +multiple of 16 bytes. The length of the chunk here means the amount of flash +space it occupies in its data sector - which is NOT equal to the payload data +length. + +The head chunk of each file begins with the filename, terminated by a NUL byte. +If there are any payload data bytes present in this head chunk (I'll explain +momentarily how you would tell), the byte immediately after the NUL that +terminates the filename is the first byte of the payload. In the case of a +continuation chunk, there is no filename and the first byte of the chunk is the +first byte of that chunk's portion of the user data payload. + +Each data-containing chunk (head or continuation) has the following termination +after the last byte of that chunk's payload data: one byte of 00, followed by +however many bytes are needed ([0,15] range) of FFs to pad to a 16-byte +boundary. A file head chunk that has no payload data has the same format as a +directory name chunk: filename followed by its terminating NUL followed by +[0,15] bytes of FFs to pad to the next 16-byte boundary. + +When working with a head chunk, find the beginning of possible payload data (1 +byte after the filename terminating NUL) and find the end per the standard +termination logic: scanning from the end of the chunk, skip FFs until 00 is +found (encountering anything else is an error). If the head chunk has no data, +the effective data length (end_pointer - start_pointer) will be 0 or -1. (The +latter possibility is the most likely, as there will normally be a "shared" 00 +byte, serving as both the filename terminator and the 00 before the padding +FF bytes.) + +Relocated chunks + +Let's go back to the scenario in which a particular data sector is full (no more +usable free space left) and contains a mixture of active and dirty (deleted or +invalidated) data. How does the dirty flash space get reclaimed, so that the +amount of available space (blank flash ready to hold new data) becomes equal to +the total FFS size minus the total size of active files and overhead? It can +only be done by relocating the still-active objects from the full sector to a +new one, invalidating the old copies, and once the old sector consists of +nothing but invalidated data, subjecting it to flash erasure. + +So how do the active FFS objects get relocated from a "condemned" sector to a +new one? If the object is a directory, a new index entry is created, pointing +to the newly relocated name chunk, but it is then made to fit into the old tree +structure without disrupting the latter: the new index entry is added at the +tail of the sibling-chain of the parent directory's descendants, the old index +entry for the same directory is invalidated (as if the directory were rmdir'ed), +and the descendant pointer of the newly written index entry is set to a copy of +the descendant pointer from the old index entry for the same directory. The +same approach is used when the head chunk of a file needs to be relocated; in +both cases a read-only FFS implementation doesn't need to do anything special to +support reading file and directory objects that have been relocated in this +manner. + +However, if the relocated object is a file continuation chunk, then the manner +in which such objects get relocated does affect file reading code. What if a +chunk in the middle of a chain linked by "descend" pointers needs to be moved? +What happens in this case is that the old copy of the chunk gets invalidated +(the object type byte turned to 00) like in the other object relocating cases, +and the sibling pointer of that old index entry (which was originally FFFF as +continuation objects have no siblings) is set to point to the new index entry +for the same chunk. The "descend" pointer in the new index entry is a copy of +that pointer from the old index entry. + +The manner of chunk relocation just described has been observed in the FFS +images read out of my most recent batch of Pirelli phones - the same ones in +which the root directory object is not at index #1. Thinking about it as I +write this, I've realized that the way in which continuation objects get +relocated is exactly the same as for other object types - thus the compaction +code in the firmware doesn't need to examine what object type it is moving. +However, the case of continuation chunk relocation deserves special attention +because it affects a read-only implementation like ours - the utilities whose +source accompanies this document used to fail on these FFS images until I +implemented the following additional handling: + +When following the chunk chain of a file, normally the only object type that's +expected is F4 - any other object type is an error. However, as a result of +chunk relocation, one can also encounter deleted objects, i.e., type == 00. +If such a deleted object is encountered, follow its sibling pointer, which must +be non-nil. + +Journal file + +Every Mokopir-FFS image I've seen so far contains a special file named +/.journal; this file is special in the following ways: + +* The object type byte is E1 instead of F1; +* Unlike regular files, this special file is internally-writable. + +What I mean by the above is that regular files are mostly immutable: once a +file has been created with some data content in the head chunk, it can only be +either appended to (one or more continuation chunks added), or overwritten by +creating a new file with the same name at the same level in the tree hierarchy +and invalidating the old one. But the special /.journal file is different: I +have never observed it to consist of more than the head chunk, and this head +chunk is pre-allocated with some largish and apparently fixed length (4 KiB on +my GTA02, 16 KiB on the Pirelli). This pre-allocated chunk contains what look +like 16-byte records at the beginning (on the first 4-byte boundary after the +NUL terminating the ".journal" name), followed by blank flash for the remainder +of the pre-allocated chunk - so it surely looks like new flash writes happen +within this chunk. + +I do not currently know the purpose of this /.journal file or the meaning of the +records it seems to contain. This understanding would surely be needed if one +wanted to create FFS images from scratch or to implement FFS write operations, +but I reason that a read-only implementation can get away with simply ignoring +this file. I reason that this file can't be necessary in order to parse an FFS +image for reading because one needs to parse the tree structure first in order +to locate this journal file itself. + +------------------------------------------------------------------------------- + +That's all I can think of right now. If anything is unclear, see the +accompanying source code for the listing/extraction utilities: with the general +explanation given by this document, it should be clear what my code does and +why. And if a given piece of knowledge is found neither in this document nor +in my source code, then I don't know it myself either, and my read-only +Mokopir-FFS implementation makes do without it. + +All knowledge contained herein has been recovered by reverse engineering. +Believe it or not, I have figured it out by staring at the hex dump of FFS +sectors, reasoning about how one could possibly implement an FFS given the +requirement of dynamic writability and the physical constraints of flash memory, +and writing listing/extraction test code iteratively until I got something that +appears to correctly parse all FFS images available to me - the result is the +code in this package. + +I never got as far as attempting to locate the FFS implementation routines +within the proprietary firmware binary code images, and I haven't found an +implementation of this particular FFS in any of the leaked sources yet either. +The TSM30 code doesn't seem to be of any use as its FFS appears to be totally +different. As to the more recently found LoCosto code leak, I found that one a +few days *after* I got the Moko/Pirelli "MysteryFFS" reverse-engineered on my +own, and when I did look at the FFS in the LoCosto code later, I saw what seems +to be a different FFS as well. + +Michael Spacefalcon +SE 52 Mes 16