tfstool.c 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. /**
  5. * ToaruFS is a simple, flexible filesystem designed to be a
  6. * dumbed-down ext2-like block-and-inode-based filesystem.
  7. *
  8. * ToaruFS employs a fixed block size of 4096 bytes (512×8 sectors)
  9. * which eases some pain of supporting multiple block sizes.
  10. *
  11. * ToaruFS has only one "block group" - a single bitmap describes
  12. * the allocation of blocks throughout the disk. Part of this is
  13. * to simplify lookups but also because the Authors assert that
  14. * block groups are no longer a necessary seek-reduction measure
  15. * on modern SSDs.
  16. *
  17. * ToaruFS adds chained inode tables, eliminating the problem
  18. * of pre-allocating space for inodes in exchange for requiring
  19. * the host driver to keep track of where a sporadic collection
  20. * of inode tables may be found. Inode tables are stored in
  21. * arbitrary blocks as a linked list, with each table pointing
  22. * to the next. Each table has a small bitmap describing which
  23. * entries are available.
  24. */
  25. /* BEGIN ToaruFS Structures */
  26. #define TOARUFS_SUPERBLOCK_MAGIC 0x46a881e3
  27. #define TOARUFS_VERSION 1
  28. /* Superblock */
  29. struct toarufs_superblock {
  30. uint32_t magic;
  31. uint32_t version;
  32. uint8_t partition_name[16];
  33. uint32_t block_count;
  34. uint32_t free_blocks;
  35. uint32_t last_mount;
  36. uint32_t last_write;
  37. uint32_t first_inode_block;
  38. uint32_t mount_count;
  39. };
  40. /* Inode Table Header */
  41. struct toarufs_inode_table {
  42. uint32_t checksum;
  43. uint32_t next_table;
  44. uint16_t table_id;
  45. uint8_t free_inodes;
  46. uint8_t inode_bitmap[5];
  47. };
  48. struct toarufs_inode_entry {
  49. uint16_t mode, owner;
  50. uint16_t group, flags;
  51. uint32_t bytes;
  52. uint32_t atime, ctime, mtime, dtime;
  53. uint32_t data_blocks[15];
  54. uint8_t reserved[12];
  55. };
  56. /* This is the same as ext2 */
  57. struct toarufs_directory_entry {
  58. uint32_t inode;
  59. uint16_t entry_length;
  60. uint8_t name_length;
  61. uint8_t file_type;
  62. char name[];
  63. };
  64. #define BLOCK_SIZE 4096
  65. #define INODE_TABLE_SIZE (sizeof(struct toarufs_inode_table))
  66. #define INODE_ENTRY_SIZE (sizeof(struct toarufs_inode_entry))
  67. #define INODE_SPACE (BLOCK_SIZE - INODE_TABLE_SIZE)
  68. #define INODES_PER_TABLE (INODE_SPACE / INODE_ENTRY_SIZE)
  69. #define INODE_TABLE_EXT (INODE_SPACE - (INODES_PER_TABLE * INODE_ENTRY_SIZE))
  70. #define INODE_TABLE_START (INODE_TABLE_SIZE + INODE_TABLE_EXT)
  71. static void toarufs_set_block(char * block_bitmap, int block) {
  72. /* Get index */
  73. uint32_t block_number = block / 8;
  74. uint32_t block_index = block % 8;
  75. block_bitmap[block_number] |= (1 << block_index);
  76. /* Write block bitmap back to disk */
  77. // TODO
  78. }
  79. static void toarufs_unset_block(char * block_bitmap, int block) {
  80. /* Get index */
  81. uint32_t block_number = block / 8;
  82. uint32_t block_index = block % 8;
  83. block_bitmap[block_number] &= ~(1 << block_index);
  84. /* Write block bitmap back to disk */
  85. // TODO
  86. }
  87. static int toarufs_test_block(char * block_bitmap, int block) {
  88. /* Get index */
  89. uint32_t block_number = block / 8;
  90. uint32_t block_index = block % 8;
  91. return block_bitmap[block_number] & (1 << block_index);
  92. }
  93. static uint32_t toarufs_allocate_block(char * block_bitmap, int bitmap_size) {
  94. for (int i = 0; i < bitmap_size; ++i) {
  95. if (block_bitmap[i] != 0xFF) {
  96. for (int j = 0; j < 8; ++j) {
  97. if (!(block_bitmap[i] & (1 << j))) {
  98. uint32_t out = ((uint32_t)i * 8 + (uint32_t)j);
  99. toarufs_set_block(block_bitmap, out);
  100. return out;
  101. }
  102. }
  103. }
  104. }
  105. return 0; /* 0 is always invalid (it's the reserved block) */
  106. }
  107. int main(int argc, char * argv[]) {
  108. if (argc < 2) {
  109. fprintf(stderr, "usage: %s FILE\n", argv[0]);
  110. return 1;
  111. }
  112. FILE * image = fopen(argv[1], "r+");
  113. if (!image) {
  114. fprintf(stderr, "%s: could not open %s\n", argv[0], argv[1]);
  115. return 1;
  116. }
  117. fprintf(stderr, "Building a ToaruFS v%d partition\n", TOARUFS_VERSION);
  118. fprintf(stderr, " inode table size = %zd\n", INODE_TABLE_SIZE);
  119. fprintf(stderr, " inode entry size = %zd\n", INODE_ENTRY_SIZE);
  120. fprintf(stderr, " remaining block size = %zd\n", INODE_SPACE);
  121. fprintf(stderr, " inodes per table = %zd\n", INODES_PER_TABLE);
  122. fprintf(stderr, " available additional inode table space = %zd\n", INODE_TABLE_EXT);
  123. fprintf(stderr, " this means table entries start at %zd\n", INODE_TABLE_START);
  124. fseek(image, 0, SEEK_END);
  125. long image_size = ftell(image);
  126. fseek(image, 0, SEEK_SET);
  127. long image_blocks = image_size / BLOCK_SIZE;
  128. fprintf(stderr, "Image is %ld bytes, can fit %ld blocks.\n", image_size, image_blocks);
  129. long bitmap_size = 0;
  130. for (int i = 0; i < image_blocks; ++i) {
  131. if (8 * BLOCK_SIZE * i >= image_blocks) {
  132. bitmap_size = i;
  133. break;
  134. }
  135. }
  136. fprintf(stderr, "With 8 blocks per per byte and %d bytes per block, need %ld blocks for block bitmaps.\n",
  137. BLOCK_SIZE, bitmap_size);
  138. fprintf(stderr, "This gives %ld potential blocks, wasting space for %ld.",
  139. bitmap_size * 8 * BLOCK_SIZE, bitmap_size * 8 * BLOCK_SIZE - image_blocks);
  140. fprintf(stderr, " (which amounts to %ld bytes of waste)\n",
  141. (bitmap_size * 8 * BLOCK_SIZE - image_blocks) / 8);
  142. /* Allocate block bitmap */
  143. char * block_bitmap = calloc(bitmap_size, BLOCK_SIZE);
  144. toarufs_set_block(block_bitmap, 0); /* Reserved space */
  145. toarufs_set_block(block_bitmap, 1); /* Super block */
  146. for (unsigned int i = 0; i < bitmap_size; ++i) {
  147. toarufs_set_block(block_bitmap, 1 + i); /* Block bitmap self-storage */
  148. }
  149. /* Allocate a block for the first inode table */
  150. fprintf(stderr, "Allocating a block yields: %u\n", toarufs_allocate_block(block_bitmap, bitmap_size));
  151. fprintf(stderr, "Allocating a block yields: %u\n", toarufs_allocate_block(block_bitmap, bitmap_size));
  152. fprintf(stderr, "Allocating a block yields: %u\n", toarufs_allocate_block(block_bitmap, bitmap_size));
  153. fprintf(stderr, "Allocating a block yields: %u\n", toarufs_allocate_block(block_bitmap, bitmap_size));
  154. return 0;
  155. }