TECH_SPEC 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  1. * USING SPIFFS
  2. TODO
  3. * SPIFFS DESIGN
  4. Spiffs is inspired by YAFFS. However, YAFFS is designed for NAND flashes, and
  5. for bigger targets with much more ram. Nevertheless, many wise thoughts have
  6. been borrowed from YAFFS when writing spiffs. Kudos!
  7. The main complication writing spiffs was that it cannot be assumed the target
  8. has a heap. Spiffs must go along only with the work ram buffer given to it.
  9. This forces extra implementation on many areas of spiffs.
  10. ** SPI flash devices using NOR technology
  11. Below is a small description of how SPI flashes work internally. This is to
  12. give an understanding of the design choices made in spiffs.
  13. SPI flash devices are physically divided in blocks. On some SPI flash devices,
  14. blocks are further divided into sectors. Datasheets sometimes name blocks as
  15. sectors and vice versa.
  16. Common memory capacaties for SPI flashes are 512kB up to 8MB of data, where
  17. blocks may be 64kB. Sectors can be e.g. 4kB, if supported. Many SPI flashes
  18. have uniform block sizes, whereas others have non-uniform - the latter meaning
  19. that e.g. the first 16 blocks are 4kB big, and the rest are 64kB.
  20. The entire memory is linear and can be read and written in random access.
  21. Erasing can only be done block- or sectorwise; or by mass erase.
  22. SPI flashes can normally be erased from 100.000 up to 1.000.000 cycles before
  23. they fail.
  24. A clean SPI flash from factory have all bits in entire memory set to one. A
  25. mass erase will reset the device to this state. Block or sector erasing will
  26. put the all bits in the area given by the sector or block to ones. Writing to a
  27. NOR flash pulls ones to zeroes. Writing 0xFF to an address is simply a no-op.
  28. Writing 0b10101010 to a flash address holding 0b00001111 will yield 0b00001010.
  29. This way of "write by nand" is used considerably in spiffs.
  30. Common characteristics of NOR flashes are quick reads, but slow writes.
  31. And finally, unlike NAND flashes, NOR flashes seem to not need any error
  32. correction. They always write correctly I gather.
  33. ** Spiffs logical structure
  34. Some terminology before proceeding. Physical blocks/sectors means sizes stated
  35. in the datasheet. Logical blocks and pages is something the integrator choose.
  36. ** Blocks and pages
  37. Spiffs is allocated to a part or all of the memory of the SPI flash device.
  38. This area is divided into logical blocks, which in turn are divided into
  39. logical pages. The boundary of a logical block must coincide with one or more
  40. physical blocks. The sizes for logical blocks and logical pages always remain
  41. the same, they are uniform.
  42. Example: non-uniform flash mapped to spiffs with 128kB logical blocks
  43. PHYSICAL FLASH BLOCKS SPIFFS LOGICAL BLOCKS: 128kB
  44. +-----------------------+ - - - +-----------------------+
  45. | Block 1 : 16kB | | Block 1 : 128kB |
  46. +-----------------------+ | |
  47. | Block 2 : 16kB | | |
  48. +-----------------------+ | |
  49. | Block 3 : 16kB | | |
  50. +-----------------------+ | |
  51. | Block 4 : 16kB | | |
  52. +-----------------------+ | |
  53. | Block 5 : 64kB | | |
  54. +-----------------------+ - - - +-----------------------+
  55. | Block 6 : 64kB | | Block 2 : 128kB |
  56. +-----------------------+ | |
  57. | Block 7 : 64kB | | |
  58. +-----------------------+ - - - +-----------------------+
  59. | Block 8 : 64kB | | Block 3 : 128kB |
  60. +-----------------------+ | |
  61. | Block 9 : 64kB | | |
  62. +-----------------------+ - - - +-----------------------+
  63. | ... | | ... |
  64. A logical block is divided further into a number of logical pages. A page
  65. defines the smallest data holding element known to spiffs. Hence, if a file
  66. is created being one byte big, it will occupy one page for index and one page
  67. for data - it will occupy 2 x size of a logical page on flash.
  68. So it seems it is good to select a small page size.
  69. Each page has a metadata header being normally 5 to 9 bytes. This said, a very
  70. small page size will make metadata occupy a lot of the memory on the flash. A
  71. page size of 64 bytes will waste 8-14% on metadata, while 256 bytes 2-4%.
  72. So it seems it is good to select a big page size.
  73. Also, spiffs uses a ram buffer being two times the page size. This ram buffer
  74. is used for loading and manipulating pages, but it is also used for algorithms
  75. to find free file ids, scanning the file system, etc. Having too small a page
  76. size means less work buffer for spiffs, ending up in more reads operations and
  77. eventually gives a slower file system.
  78. Choosing the page size for the system involves many factors:
  79. - How big is the logical block size
  80. - What is the normal size of most files
  81. - How much ram can be spent
  82. - How much data (vs metadata) must be crammed into the file system
  83. - How fast must spiffs be
  84. - Other things impossible to find out
  85. So, chosing the Optimal Page Size (tm) seems tricky, to say the least. Don't
  86. fret - there is no optimal page size. This varies from how the target will use
  87. spiffs. Use the golden rule:
  88. ~~~ Logical Page Size = Logical Block Size / 256 ~~~
  89. This is a good starting point. The final page size can then be derived through
  90. heuristical experimenting for us non-analytical minds.
  91. ** Objects, indices and look-ups
  92. A file, or an object as called in spiffs, is identified by an object id.
  93. Another YAFFS rip-off. This object id is a part of the page header. So, all
  94. pages know to which object/file they belong - not counting the free pages.
  95. An object is made up of two types of pages: object index pages and data pages.
  96. Data pages contain the data written by user. Index pages contain metadata about
  97. the object, more specifically what data pages are part of the object.
  98. The page header also includes something called a span index. Let's say a file
  99. is written covering three data pages. The first data page will then have span
  100. index 0, the second span index 1, and the last data page will have span index
  101. 2. Simple as that.
  102. Finally, each page header contain flags, telling if the page is used,
  103. deleted, finalized, holds index or data, and more.
  104. Object indices also have span indices, where an object index with span index 0
  105. is referred to as the object index header. This page does not only contain
  106. references to data pages, but also extra info such as object name, object size
  107. in bytes, flags for file or directory, etc.
  108. If one were to create a file covering three data pages, named e.g.
  109. "spandex-joke.txt", given object id 12, it could look like this:
  110. PAGE 0 <things to be unveiled soon>
  111. PAGE 1 page header: [obj_id:12 span_ix:0 flags:USED|DATA]
  112. <first data page of joke>
  113. PAGE 2 page header: [obj_id:12 span_ix:1 flags:USED|DATA]
  114. <second data page of joke>
  115. PAGE 3 page header: [obj_id:545 span_ix:13 flags:USED|DATA]
  116. <some data belonging to object 545, probably not very amusing>
  117. PAGE 4 page header: [obj_id:12 span_ix:2 flags:USED|DATA]
  118. <third data page of joke>
  119. PAGE 5 page header: [obj_id:12 span_ix:0 flags:USED|INDEX]
  120. obj ix header: [name:spandex-joke.txt size:600 bytes flags:FILE]
  121. obj ix: [1 2 4]
  122. Looking in detail at page 5, the object index header page, the object index
  123. array refers to each data page in order, as mentioned before. The index of the
  124. object index array correlates with the data page span index.
  125. entry ix: 0 1 2
  126. obj ix: [1 2 4]
  127. | | |
  128. PAGE 1, DATA, SPAN_IX 0 --------/ | |
  129. PAGE 2, DATA, SPAN_IX 1 --------/ |
  130. PAGE 4, DATA, SPAN_IX 2 --------/
  131. Things to be unveiled in page 0 - well.. Spiffs is designed for systems low on
  132. ram. We cannot keep a dynamic list on the whereabouts of each object index
  133. header so we can find a file fast. There might not even be a heap! But, we do
  134. not want to scan all page headers on the flash to find the object index header.
  135. The first page(s) of each block contains the so called object look-up. These
  136. are not normal pages, they do not have a header. Instead, they are arrays
  137. pointing out what object-id the rest of all pages in the block belongs to.
  138. By this look-up, only the first page(s) in each block must to scanned to find
  139. the actual page which contains the object index header of the desired object.
  140. The object lookup is redundant metadata. The assumption is that it presents
  141. less overhead reading a full page of data to memory from each block and search
  142. that, instead of reading a small amount of data from each page (i.e. the page
  143. header) in all blocks. Each read operation from SPI flash normally contains
  144. extra data as the read command itself and the flash address. Also, depending on
  145. the underlying implementation, other criterions may need to be passed for each
  146. read transaction, like mutexes and such.
  147. The veiled example unveiled would look like this, with some extra pages:
  148. PAGE 0 [ 12 12 545 12 12 34 34 4 0 0 0 0 ...]
  149. PAGE 1 page header: [obj_id:12 span_ix:0 flags:USED|DATA] ...
  150. PAGE 2 page header: [obj_id:12 span_ix:1 flags:USED|DATA] ...
  151. PAGE 3 page header: [obj_id:545 span_ix:13 flags:USED|DATA] ...
  152. PAGE 4 page header: [obj_id:12 span_ix:2 flags:USED|DATA] ...
  153. PAGE 5 page header: [obj_id:12 span_ix:0 flags:USED|INDEX] ...
  154. PAGE 6 page header: [obj_id:34 span_ix:0 flags:USED|DATA] ...
  155. PAGE 7 page header: [obj_id:34 span_ix:1 flags:USED|DATA] ...
  156. PAGE 8 page header: [obj_id:4 span_ix:1 flags:USED|INDEX] ...
  157. PAGE 9 page header: [obj_id:23 span_ix:0 flags:DELETED|INDEX] ...
  158. PAGE 10 page header: [obj_id:23 span_ix:0 flags:DELETED|DATA] ...
  159. PAGE 11 page header: [obj_id:23 span_ix:1 flags:DELETED|DATA] ...
  160. PAGE 12 page header: [obj_id:23 span_ix:2 flags:DELETED|DATA] ...
  161. ...
  162. Ok, so why are page 9 to 12 marked as 0 when they belong to object id 23? These
  163. pages are deleted, so this is marked both in page header flags and in the look
  164. up. This is an example where spiffs uses NOR flashes "nand-way" of writing.
  165. As a matter of fact, there are two object id's which are special:
  166. obj id 0 (all bits zeroes) - indicates a deleted page in object look up
  167. obj id 0xff.. (all bits ones) - indicates a free page in object look up
  168. Actually, the object id's have another quirk: if the most significant bit is
  169. set, this indicates an object index page. If the most significant bit is zero,
  170. this indicates a data page. So to be fully correct, page 0 in above example
  171. would look like this:
  172. PAGE 0 [ 12 12 545 12 *12 34 34 *4 0 0 0 0 ...]
  173. where the asterisk means the msb of the object id is set.
  174. This is another way to speed up the searches when looking for object indices.
  175. By looking on the object id's msb in the object lookup, it is also possible
  176. to find out whether the page is an object index page or a data page.