The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/cramfs/

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

Name Size Last modified (GMT) Description
Back Parent directory 2009-05-27 19:04:47
File Makefile 203 bytes 2001-10-25 20:53:53
File README 6322 bytes 2002-08-03 00:39:45
C file inode.c 12000 bytes 2002-08-03 00:39:45
C file uncompress.c 1713 bytes 2002-11-28 23:53:15

    1 Notes on Filesystem Layout
    2 --------------------------
    3 
    4 These notes describe what mkcramfs generates.  Kernel requirements are
    5 a bit looser, e.g. it doesn't care if the <file_data> items are
    6 swapped around (though it does care that directory entries (inodes) in
    7 a given directory are contiguous, as this is used by readdir).
    8 
    9 All data is currently in host-endian format; neither mkcramfs nor the
   10 kernel 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 
   25 The order of inode traversal is described as "width-first" (not to be
   26 confused with breadth-first); i.e. like depth-first but listing all of
   27 a directory's entries before recursing down its subdirectories: the
   28 same order as `ls -AUR' (but without the /^\..*:$/ directory header
   29 lines); put another way, the same order as `find -type d -exec
   30 ls -AU1 {} \;'.
   31 
   32 Beginning in 2.4.7, directory entries are sorted.  This optimization
   33 allows cramfs_lookup to return more quickly when a filename does not
   34 exist, 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 
   46 The 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
   48 same 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 
   52 The order of <file_data>'s is a depth-first descent of the directory
   53 tree, i.e. the same order as `find -size +0 \( -type f -o -type l \)
   54 -print'.
   55 
   56 
   57 <block>: The i'th <block> is the output of zlib's compress function
   58 applied to the i'th blksize-sized chunk of the input data.
   59 (For the last <block> of the file, the input may of course be smaller.)
   60 Each <block> may be a different size.  (See <block_pointer> above.)
   61 <block>s are merely byte-aligned, not generally u32-aligned.
   62 
   63 
   64 Holes
   65 -----
   66 
   67 This kernel supports cramfs holes (i.e. [efficient representation of]
   68 blocks in uncompressed data consisting entirely of NUL bytes), but by
   69 default mkcramfs doesn't test for & create holes, since cramfs in
   70 kernels up to at least 2.3.39 didn't support holes.  Run mkcramfs
   71 with -z if you want it to create files that can have holes in them.
   72 
   73 
   74 Tools
   75 -----
   76 
   77 The cramfs user-space tools, including mkcramfs and cramfsck, are
   78 located at <http://sourceforge.net/projects/cramfs/>.
   79 
   80 
   81 Future Development
   82 ==================
   83 
   84 Block Size
   85 ----------
   86 
   87 (Block size in cramfs refers to the size of input data that is
   88 compressed at a time.  It's intended to be somewhere around
   89 PAGE_CACHE_SIZE for cramfs_readpage's convenience.)
   90 
   91 The superblock ought to indicate the block size that the fs was
   92 written for, since comments in <linux/pagemap.h> indicate that
   93 PAGE_CACHE_SIZE may grow in future (if I interpret the comment
   94 correctly).
   95 
   96 Currently, mkcramfs #define's PAGE_CACHE_SIZE as 4096 and uses that
   97 for blksize, whereas Linux-2.3.39 uses its PAGE_CACHE_SIZE, which in
   98 turn is defined as PAGE_SIZE (which can be as large as 32KB on arm).
   99 This discrepancy is a bug, though it's not clear which should be
  100 changed.
  101 
  102 One option is to change mkcramfs to take its PAGE_CACHE_SIZE from
  103 <asm/page.h>.  Personally I don't like this option, but it does
  104 require the least amount of change: just change `#define
  105 PAGE_CACHE_SIZE (4096)' to `#include <asm/page.h>'.  The disadvantage
  106 is that the generated cramfs cannot always be shared between different
  107 kernels, not even necessarily kernels of the same architecture if
  108 PAGE_CACHE_SIZE is subject to change between kernel versions
  109 (currently possible with arm and ia64).
  110 
  111 The remaining options try to make cramfs more sharable.
  112 
  113 One part of that is addressing endianness.  The two options here are
  114 `always use little-endian' (like ext2fs) or `writer chooses
  115 endianness; kernel adapts at runtime'.  Little-endian wins because of
  116 code simplicity and little CPU overhead even on big-endian machines.
  117 
  118 The cost of swabbing is changing the code to use the le32_to_cpu
  119 etc. macros as used by ext2fs.  We don't need to swab the compressed
  120 data, only the superblock, inodes and block pointers.
  121 
  122 
  123 The other part of making cramfs more sharable is choosing a block
  124 size.  The options are:
  125 
  126   1. Always 4096 bytes.
  127 
  128   2. Writer chooses blocksize; kernel adapts but rejects blocksize >
  129      PAGE_CACHE_SIZE.
  130 
  131   3. Writer chooses blocksize; kernel adapts even to blocksize >
  132      PAGE_CACHE_SIZE.
  133 
  134 It's easy enough to change the kernel to use a smaller value than
  135 PAGE_CACHE_SIZE: just make cramfs_readpage read multiple blocks.
  136 
  137 The cost of option 1 is that kernels with a larger PAGE_CACHE_SIZE
  138 value don't get as good compression as they can.
  139 
  140 The cost of option 2 relative to option 1 is that the code uses
  141 variables instead of #define'd constants.  The gain is that people
  142 with kernels having larger PAGE_CACHE_SIZE can make use of that if
  143 they don't mind their cramfs being inaccessible to kernels with
  144 smaller PAGE_CACHE_SIZE values.
  145 
  146 Option 3 is easy to implement if we don't mind being CPU-inefficient:
  147 e.g. get readpage to decompress to a buffer of size MAX_BLKSIZE (which
  148 must be no larger than 32KB) and discard what it doesn't need.
  149 Getting readpage to read into all the covered pages is harder.
  150 
  151 The main advantage of option 3 over 1, 2, is better compression.  The
  152 cost is greater complexity.  Probably not worth it, but I hope someone
  153 will disagree.  (If it is implemented, then I'll re-use that code in
  154 e2compr.)
  155 
  156 
  157 Another cost of 2 and 3 over 1 is making mkcramfs use a different
  158 block size, but that just means adding and parsing a -b option.
  159 
  160 
  161 Inode Size
  162 ----------
  163 
  164 Given that cramfs will probably be used for CDs etc. as well as just
  165 silicon ROMs, it might make sense to expand the inode a little from
  166 its current 12 bytes.  Inodes other than the root inode are followed
  167 by filename, so the expansion doesn't even have to be a multiple of 4
  168 bytes.

[ source navigation ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.