linux/fs/cramfs/README
<<
>>
Prefs
   1Notes on Filesystem Layout
   2--------------------------
   3
   4These notes describe what mkcramfs generates.  Kernel requirements are
   5a bit looser, e.g. it doesn't care if the <file_data> items are
   6swapped around (though it does care that directory entries (inodes) in
   7a given directory are contiguous, as this is used by readdir).
   8
   9All data is currently in host-endian format; neither mkcramfs nor the
  10kernel ever do swabbing.  (See section `Block Size' below.)
  11
  12<filesystem>:
  13        <superblock>
  14        <directory_structure>
  15        <data>
  16
  17<superblock>: struct cramfs_super (see cramfs_fs.h).
  18
  19<directory_structure>:
  20        For each file:
  21                struct cramfs_inode (see cramfs_fs.h).
  22                Filename.  Not generally null-terminated, but it is
  23                 null-padded to a multiple of 4 bytes.
  24
  25The order of inode traversal is described as "width-first" (not to be
  26confused with breadth-first); i.e. like depth-first but listing all of
  27a directory's entries before recursing down its subdirectories: the
  28same order as `ls -AUR' (but without the /^\..*:$/ directory header
  29lines); put another way, the same order as `find -type d -exec
  30ls -AU1 {} \;'.
  31
  32Beginning in 2.4.7, directory entries are sorted.  This optimization
  33allows cramfs_lookup to return more quickly when a filename does not
  34exist, speeds up user-space directory sorts, etc.
  35
  36<data>:
  37        One <file_data> for each file that's either a symlink or a
  38         regular file of non-zero st_size.
  39
  40<file_data>:
  41        nblocks * <block_pointer>
  42         (where nblocks = (st_size - 1) / blksize + 1)
  43        nblocks * <block>
  44        padding to multiple of 4 bytes
  45
  46The i'th <block_pointer> for a file stores the byte offset of the
  47*end* of the i'th <block> (i.e. one past the last byte, which is the
  48same as the start of the (i+1)'th <block> if there is one).  The first
  49<block> immediately follows the last <block_pointer> for the file.
  50<block_pointer>s are each 32 bits long.
  51
  52When the CRAMFS_FLAG_EXT_BLOCK_POINTERS capability bit is set, each
  53<block_pointer>'s top bits may contain special flags as follows:
  54
  55CRAMFS_BLK_FLAG_UNCOMPRESSED (bit 31):
  56        The block data is not compressed and should be copied verbatim.
  57
  58CRAMFS_BLK_FLAG_DIRECT_PTR (bit 30):
  59        The <block_pointer> stores the actual block start offset and not
  60        its end, shifted right by 2 bits. The block must therefore be
  61        aligned to a 4-byte boundary. The block size is either blksize
  62        if CRAMFS_BLK_FLAG_UNCOMPRESSED is also specified, otherwise
  63        the compressed data length is included in the first 2 bytes of
  64        the block data. This is used to allow discontiguous data layout
  65        and specific data block alignments e.g. for XIP applications.
  66
  67
  68The order of <file_data>'s is a depth-first descent of the directory
  69tree, i.e. the same order as `find -size +0 \( -type f -o -type l \)
  70-print'.
  71
  72
  73<block>: The i'th <block> is the output of zlib's compress function
  74applied to the i'th blksize-sized chunk of the input data if the
  75corresponding CRAMFS_BLK_FLAG_UNCOMPRESSED <block_ptr> bit is not set,
  76otherwise it is the input data directly.
  77(For the last <block> of the file, the input may of course be smaller.)
  78Each <block> may be a different size.  (See <block_pointer> above.)
  79
  80<block>s are merely byte-aligned, not generally u32-aligned.
  81
  82When CRAMFS_BLK_FLAG_DIRECT_PTR is specified then the corresponding
  83<block> may be located anywhere and not necessarily contiguous with
  84the previous/next blocks. In that case it is minimally u32-aligned.
  85If CRAMFS_BLK_FLAG_UNCOMPRESSED is also specified then the size is always
  86blksize except for the last block which is limited by the file length.
  87If CRAMFS_BLK_FLAG_DIRECT_PTR is set and CRAMFS_BLK_FLAG_UNCOMPRESSED
  88is not set then the first 2 bytes of the block contains the size of the
  89remaining block data as this cannot be determined from the placement of
  90logically adjacent blocks.
  91
  92
  93Holes
  94-----
  95
  96This kernel supports cramfs holes (i.e. [efficient representation of]
  97blocks in uncompressed data consisting entirely of NUL bytes), but by
  98default mkcramfs doesn't test for & create holes, since cramfs in
  99kernels up to at least 2.3.39 didn't support holes.  Run mkcramfs
 100with -z if you want it to create files that can have holes in them.
 101
 102
 103Tools
 104-----
 105
 106The cramfs user-space tools, including mkcramfs and cramfsck, are
 107located at <http://sourceforge.net/projects/cramfs/>.
 108
 109
 110Future Development
 111==================
 112
 113Block Size
 114----------
 115
 116(Block size in cramfs refers to the size of input data that is
 117compressed at a time.  It's intended to be somewhere around
 118PAGE_SIZE for cramfs_readpage's convenience.)
 119
 120The superblock ought to indicate the block size that the fs was
 121written for, since comments in <linux/pagemap.h> indicate that
 122PAGE_SIZE may grow in future (if I interpret the comment
 123correctly).
 124
 125Currently, mkcramfs #define's PAGE_SIZE as 4096 and uses that
 126for blksize, whereas Linux-2.3.39 uses its PAGE_SIZE, which in
 127turn is defined as PAGE_SIZE (which can be as large as 32KB on arm).
 128This discrepancy is a bug, though it's not clear which should be
 129changed.
 130
 131One option is to change mkcramfs to take its PAGE_SIZE from
 132<asm/page.h>.  Personally I don't like this option, but it does
 133require the least amount of change: just change `#define
 134PAGE_SIZE (4096)' to `#include <asm/page.h>'.  The disadvantage
 135is that the generated cramfs cannot always be shared between different
 136kernels, not even necessarily kernels of the same architecture if
 137PAGE_SIZE is subject to change between kernel versions
 138(currently possible with arm and ia64).
 139
 140The remaining options try to make cramfs more sharable.
 141
 142One part of that is addressing endianness.  The two options here are
 143`always use little-endian' (like ext2fs) or `writer chooses
 144endianness; kernel adapts at runtime'.  Little-endian wins because of
 145code simplicity and little CPU overhead even on big-endian machines.
 146
 147The cost of swabbing is changing the code to use the le32_to_cpu
 148etc. macros as used by ext2fs.  We don't need to swab the compressed
 149data, only the superblock, inodes and block pointers.
 150
 151
 152The other part of making cramfs more sharable is choosing a block
 153size.  The options are:
 154
 155  1. Always 4096 bytes.
 156
 157  2. Writer chooses blocksize; kernel adapts but rejects blocksize >
 158     PAGE_SIZE.
 159
 160  3. Writer chooses blocksize; kernel adapts even to blocksize >
 161     PAGE_SIZE.
 162
 163It's easy enough to change the kernel to use a smaller value than
 164PAGE_SIZE: just make cramfs_readpage read multiple blocks.
 165
 166The cost of option 1 is that kernels with a larger PAGE_SIZE
 167value don't get as good compression as they can.
 168
 169The cost of option 2 relative to option 1 is that the code uses
 170variables instead of #define'd constants.  The gain is that people
 171with kernels having larger PAGE_SIZE can make use of that if
 172they don't mind their cramfs being inaccessible to kernels with
 173smaller PAGE_SIZE values.
 174
 175Option 3 is easy to implement if we don't mind being CPU-inefficient:
 176e.g. get readpage to decompress to a buffer of size MAX_BLKSIZE (which
 177must be no larger than 32KB) and discard what it doesn't need.
 178Getting readpage to read into all the covered pages is harder.
 179
 180The main advantage of option 3 over 1, 2, is better compression.  The
 181cost is greater complexity.  Probably not worth it, but I hope someone
 182will disagree.  (If it is implemented, then I'll re-use that code in
 183e2compr.)
 184
 185
 186Another cost of 2 and 3 over 1 is making mkcramfs use a different
 187block size, but that just means adding and parsing a -b option.
 188
 189
 190Inode Size
 191----------
 192
 193Given that cramfs will probably be used for CDs etc. as well as just
 194silicon ROMs, it might make sense to expand the inode a little from
 195its current 12 bytes.  Inodes other than the root inode are followed
 196by filename, so the expansion doesn't even have to be a multiple of 4
 197bytes.
 198