README 6.2 KB

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