freecalypso-reveng: mpffs/Description comparison

comparison mpffs/Description @ 41:86a494a5f2b0

MPFFS description: documented relocated chunks and the journal file

author	Michael Spacefalcon <msokolov@ivan.Harhan.ORG>
date	Fri, 05 Jul 2013 03:26:06 +0000
parents	c9f7a4afccc9
children

comparison

equal deleted inserted replaced

-:7ceab8bfacb3
+:86a494a5f2b0
 "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 such a mystery any more :-)
+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 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), and the descendant pointer of each continuation object
+sibling pointer is nil - but see below regarding relocated chunks), and the
-points to the next continuation object, if there is one - nil otherwise.
+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
 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
 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 most certainly don't
+within the proprietary firmware binary code images, and I haven't found an
-have anything from TI that would help in this case.  (The TSM30 code doesn't
+implementation of this particular FFS in any of the leaked sources yet either.
-seem to be of any use as its FFS appears to be totally different, and I haven't
+The TSM30 code doesn't seem to be of any use as its FFS appears to be totally
-looked at the FFS code in the more recently found LoCosto code leak because I
+different.  As to the more recently found LoCosto code leak, I found that one a
-assumed from the documentation in the latter that the FFS implemented there is
+few days *after* I got the Moko/Pirelli "MysteryFFS" reverse-engineered on my
-different as well.)
+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 11
+SE 52 Mes 16

FreeCalypso > hg > freecalypso-reveng

comparison mpffs/Description @ 41:86a494a5f2b0