1 /* vi: set sw=4 ts=4: */
3 * mkfs_ext2: utility to create EXT2 filesystem
4 * inspired by genext2fs
6 * Busybox'ed (2009) by Vladimir Dronnikov <dronnikov@gmail.com>
8 * Licensed under GPLv2, see file LICENSE in this tarball for details.
12 #include <linux/ext2_fs.h>
13 #include <sys/user.h> /* PAGE_SIZE */
15 # define PAGE_SIZE 4096
17 #include "volume_id/volume_id_internal.h"
19 #define ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT 0
20 #define ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX 1
23 #define s_reserved_gdt_blocks s_padding1
24 #define s_mkfs_time s_reserved[0]
25 #define s_flags s_reserved[22]
26 #define EXT2_HASH_HALF_MD4 1
27 #define EXT2_FLAGS_SIGNED_HASH 0x0001
29 // whiteout: for writable overlays
30 //#define LINUX_S_IFWHT 0160000
31 //#define EXT2_FEATURE_INCOMPAT_WHITEOUT 0x0020
34 char BUG_wrong_field_size(void);
35 #define STORE_LE(field, value) \
37 if (sizeof(field) == 4) \
38 field = cpu_to_le32(value); \
39 else if (sizeof(field) == 2) \
40 field = cpu_to_le16(value); \
41 else if (sizeof(field) == 1) \
44 BUG_wrong_field_size(); \
47 #define FETCH_LE32(field) \
48 (sizeof(field) == 4 ? cpu_to_le32(field) : BUG_wrong_field_size())
50 // All fields are little-endian
69 static unsigned int_log2(unsigned arg)
72 while ((arg >>= 1) != 0)
77 // taken from mkfs_minix.c. libbb candidate?
78 // why "uint64_t size"? we never use it for anything >32 bits
79 static uint32_t div_roundup(uint64_t size, uint32_t n)
82 uint32_t res = size / n;
88 static void allocate(uint8_t *bitmap, uint32_t blocksize, uint32_t start, uint32_t end)
91 memset(bitmap, 0, blocksize);
93 memset(bitmap, 0xFF, i);
94 bitmap[i] = 0xFF >> (8 - (start & 7));
95 //bb_info_msg("ALLOC: [%u][%u][%u]: [%u-%u]:=[%x],[%x]", blocksize, start, end, start/8, blocksize - end/8 - 1, 0xFF >> (8 - (start & 7)), (uint8_t)(0xFF << (8-(end&7))));
97 bitmap[blocksize - i - 1] = 0xFF << (8 - (end & 7));
98 memset(bitmap + blocksize - i, 0xFF, i); // N.B. no overflow here!
101 static uint32_t has_super(uint32_t x)
103 // 0, 1 and powers of 3, 5, 7 up to 2^32 limit
104 static const uint32_t supers[] = {
105 0, 1, 3, 5, 7, 9, 25, 27, 49, 81, 125, 243, 343, 625, 729,
106 2187, 2401, 3125, 6561, 15625, 16807, 19683, 59049, 78125,
107 117649, 177147, 390625, 531441, 823543, 1594323, 1953125,
108 4782969, 5764801, 9765625, 14348907, 40353607, 43046721,
109 48828125, 129140163, 244140625, 282475249, 387420489,
110 1162261467, 1220703125, 1977326743, 3486784401/* >2^31 */,
112 const uint32_t *sp = supers + ARRAY_SIZE(supers);
122 /* Standard mke2fs 1.41.9:
123 * Usage: mke2fs [-c|-l filename] [-b block-size] [-f fragment-size]
124 * [-i bytes-per-inode] [-I inode-size] [-J journal-options]
125 * [-G meta group size] [-N number-of-inodes]
126 * [-m reserved-blocks-percentage] [-o creator-os]
127 * [-g blocks-per-group] [-L volume-label] [-M last-mounted-directory]
128 * [-O feature[,...]] [-r fs-revision] [-E extended-option[,...]]
129 * [-T fs-type] [-U UUID] [-jnqvFSV] device [blocks-count]
131 // N.B. not commented below options are taken and silently ignored
135 OPT_b = 1 << 2, // block size, in bytes
137 OPT_i = 1 << 4, // bytes per inode
142 OPT_m = 1 << 9, // percentage of blocks reserved for superuser
145 OPT_L = 1 << 12, // label
153 OPT_n = 1 << 20, // dry run: do not write anything
158 //OPT_V = 1 << 25, // -V version. bbox applets don't support that
161 #define fd 3 /* predefined output descriptor */
163 static void PUT(uint64_t off, void *buf, uint32_t size)
165 // bb_info_msg("PUT[%llu]:[%u]", off, size);
166 xlseek(fd, off, SEEK_SET);
167 xwrite(fd, buf, size);
170 int mkfs_ext2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
171 int mkfs_ext2_main(int argc UNUSED_PARAM, char **argv)
175 unsigned blocksize, blocksize_log2;
176 unsigned nreserved = 5;
177 unsigned long long kilobytes;
178 uint32_t nblocks, nblocks_full;
180 uint32_t bytes_per_inode;
181 uint32_t first_data_block;
182 uint32_t inodes_per_group;
183 uint32_t gdtsz, itsz;
186 const char *label = "";
188 struct ext2_super_block *sb; // superblock
189 struct ext2_group_desc *gd; // group descriptors
190 struct ext2_inode *inode;
191 struct ext2_dir *dir;
194 opt_complementary = "-1:b+:m+:i+";
195 opts = getopt32(argv, "cl:b:f:i:I:J:G:N:m:o:g:L:M:O:r:E:T:U:jnqvFS",
196 NULL, &bs, NULL, &bpi, NULL, NULL, NULL, NULL,
197 &nreserved, NULL, NULL, &label, NULL, NULL, NULL, NULL, NULL, NULL);
198 argv += optind; // argv[0] -- device
200 // reserved blocks percentage
202 bb_error_msg_and_die("-%c is bad", 'm');
204 // check the device is a block device
205 xmove_fd(xopen(argv[0], O_WRONLY), fd);
207 if (!S_ISBLK(st.st_mode) && !(opts & OPT_F))
208 bb_error_msg_and_die("not a block device");
210 // check if it is mounted
211 // N.B. what if we format a file? find_mount_point will return false negative since
212 // it is loop block device which mounted!
213 if (find_mount_point(argv[0], 0))
214 bb_error_msg_and_die("can't format mounted filesystem");
216 // open the device, get size in kbytes
218 kilobytes = xatoull(argv[1]);
220 kilobytes = (uoff_t)xlseek(fd, 0, SEEK_END) / 1024;
223 bytes_per_inode = 16384;
224 if (kilobytes < 512*1024)
225 bytes_per_inode = 4096;
226 if (kilobytes < 3*1024)
227 bytes_per_inode = 8192;
229 bytes_per_inode = bpi;
231 // block size is a multiple of 1024
233 if (kilobytes >= 512*1024) // mke2fs 1.41.9 compat
235 if (EXT2_MAX_BLOCK_SIZE > 4096) {
236 // kilobytes >> 22 == size in 4gigabyte chunks.
237 // if it is >= 16k gigs, blocksize must be increased.
238 // Try "mke2fs -F image_std $((16 * 1024*1024*1024))"
239 while ((kilobytes >> 22) >= blocksize)
244 if (blocksize < EXT2_MIN_BLOCK_SIZE
245 || blocksize > EXT2_MAX_BLOCK_SIZE
246 || (blocksize & (blocksize - 1)) // not power of 2
248 bb_error_msg_and_die("blocksize %u is bad", blocksize);
250 blocksize_log2 = int_log2(blocksize);
251 kilobytes >>= (blocksize_log2 - EXT2_MIN_BLOCK_LOG_SIZE);
252 // nblocks: the total number of blocks in the filesystem
254 if (nblocks != kilobytes)
255 bb_error_msg_and_die("block count doesn't fit in 32 bits");
256 #define kilobytes kilobytes_unused_after_this
258 if (blocksize < PAGE_SIZE)
259 nblocks &= ~((PAGE_SIZE / blocksize)-1);
261 // N.B. killing e2fsprogs feature! Unused blocks don't account in calculations
262 nblocks_full = nblocks;
265 bb_error_msg_and_die("need >= 8 blocks");
267 // number of bits in one block, i.e. 8*blocksize
268 #define blocks_per_group (8 * blocksize)
270 // N.B. a block group can have no more than blocks_per_group blocks
271 first_data_block = (EXT2_MIN_BLOCK_SIZE == blocksize);
272 ngroups = div_roundup(nblocks - first_data_block, blocks_per_group);
274 bb_error_msg_and_die("ngroups");
276 gdtsz = div_roundup(ngroups, blocksize / sizeof(*gd));
277 // TODO: reserved blocks must be marked as such in the bitmaps,
278 // or resulting filesystem is corrupt
279 if (ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT) {
281 * From e2fsprogs: Calculate the number of GDT blocks to reserve for online
283 * The absolute maximum number of GDT blocks we can reserve is determined by
284 * the number of block pointers that can fit into a single block.
285 * We set it at 1024x the current filesystem size, or
286 * the upper block count limit (2^32), whichever is lower.
288 uint32_t rgdtsz = 0xFFFFFFFF; // maximum block number
289 if (nblocks < rgdtsz / 1024)
290 rgdtsz = nblocks * 1024;
291 rgdtsz = div_roundup(rgdtsz - first_data_block, blocks_per_group);
292 rgdtsz = div_roundup(rgdtsz, blocksize / sizeof(*gd)) - gdtsz;
293 if (rgdtsz > blocksize / sizeof(uint32_t))
294 rgdtsz = blocksize / sizeof(uint32_t);
295 //TODO: STORE_LE(sb->s_reserved_gdt_blocks, rgdtsz);
300 // N.B. e2fsprogs does as follows!
301 // ninodes is the total number of inodes (files) in the file system
302 uint32_t ninodes = nblocks_full / (blocksize >= 4096 ? 1 : 4096 / blocksize);
303 uint32_t overhead, remainder;
304 if (ninodes < EXT2_GOOD_OLD_FIRST_INO+1)
305 ninodes = EXT2_GOOD_OLD_FIRST_INO+1;
306 inodes_per_group = div_roundup(ninodes, ngroups);
307 // minimum number because the first EXT2_GOOD_OLD_FIRST_INO-1 are reserved
308 if (inodes_per_group < 16)
309 inodes_per_group = 16;
311 // N.B. a block group can have no more than 8*blocksize inodes
312 if (inodes_per_group > blocks_per_group)
313 inodes_per_group = blocks_per_group;
314 // adjust inodes per group so they completely fill the inode table blocks in the descriptor
315 inodes_per_group = (div_roundup(inodes_per_group * sizeof(*inode), blocksize) << blocksize_log2) / sizeof(*inode);
316 // make sure the number of inodes per group is a multiple of 8
317 inodes_per_group &= ~7;
318 itsz = div_roundup(inodes_per_group * sizeof(*inode), blocksize);
320 // the last block needs more attention: doesn't it too small for possible overhead?
321 overhead = (has_super(ngroups - 1) ? (1/*sb*/ + gdtsz) : 0) + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
322 remainder = (nblocks - first_data_block) % blocks_per_group;
323 if ((1 == ngroups) && remainder && (remainder < overhead))
324 bb_error_msg_and_die("way small device");
325 if (remainder && (remainder < overhead + 50)) {
326 //bb_info_msg("CHOP[%u]", remainder);
327 nblocks -= remainder;
333 if (nblocks_full - nblocks)
334 printf("warning: %u blocks unused\n\n", nblocks_full - nblocks);
336 "Filesystem label=%s\n"
338 "Block size=%u (log=%u)\n"
339 "Fragment size=%u (log=%u)\n"
340 "%u inodes, %u blocks\n"
341 "%u blocks (%u%%) reserved for the super user\n"
342 "First data block=%u\n"
343 "Maximum filesystem blocks=%u\n"
345 "%u blocks per group, %u fragments per group\n"
346 "%u inodes per group"
348 , blocksize, blocksize_log2 - EXT2_MIN_BLOCK_LOG_SIZE
349 , blocksize, blocksize_log2 - EXT2_MIN_BLOCK_LOG_SIZE
350 , inodes_per_group * ngroups, nblocks
351 //, div_roundup((uint64_t) nblocks * nreserved, 100), nreserved
352 , (unsigned)((uint64_t) nblocks_full * nreserved / 100), nreserved
354 , gdtsz * (blocksize / sizeof(*gd)) * blocks_per_group
356 , blocks_per_group, blocks_per_group
360 const char *fmt = "\nSuperblock backups stored on blocks:\n"
362 pos = first_data_block;
363 for (i = 1; i < ngroups; i++) {
364 pos += blocks_per_group;
366 printf(fmt, (unsigned)pos);
373 // dry run? -> we are done
377 // TODO: 3/5 refuse if mounted
378 // TODO: 4/5 compat options
379 // TODO: 1/5 sanity checks
380 // TODO: 0/5 more verbose error messages
381 // TODO: 4/5 bigendianness: recheck, wait for ARM reporters
382 // TODO: 2/5 reserved GDT: how to mark but not allocate?
383 // TODO: 3/5 dir_index?
385 // fill the superblock
386 sb = xzalloc(blocksize);
387 STORE_LE(sb->s_rev_level, 1); // revision 1 filesystem
388 STORE_LE(sb->s_magic, EXT2_SUPER_MAGIC);
389 STORE_LE(sb->s_inode_size, sizeof(*inode));
390 STORE_LE(sb->s_first_ino, EXT2_GOOD_OLD_FIRST_INO);
391 STORE_LE(sb->s_log_block_size, blocksize_log2 - EXT2_MIN_BLOCK_LOG_SIZE);
392 STORE_LE(sb->s_log_frag_size, blocksize_log2 - EXT2_MIN_BLOCK_LOG_SIZE);
393 // first 1024 bytes of the device are for boot record. If block size is 1024 bytes, then
394 // the first block available for data is 1, otherwise 0
395 STORE_LE(sb->s_first_data_block, first_data_block); // 0 or 1
396 // block and inode bitmaps occupy no more than one block, so maximum number of blocks is
397 STORE_LE(sb->s_blocks_per_group, blocks_per_group);
398 STORE_LE(sb->s_frags_per_group, blocks_per_group);
400 STORE_LE(sb->s_blocks_count, nblocks);
401 // reserve blocks for superuser
402 STORE_LE(sb->s_r_blocks_count, (uint32_t)((uint64_t) nblocks_full * nreserved / 100));
404 STORE_LE(sb->s_inodes_per_group, inodes_per_group);
405 STORE_LE(sb->s_inodes_count, inodes_per_group * ngroups);
406 STORE_LE(sb->s_free_inodes_count, inodes_per_group * ngroups - EXT2_GOOD_OLD_FIRST_INO);
408 timestamp = time(NULL);
409 STORE_LE(sb->s_mkfs_time, timestamp);
410 STORE_LE(sb->s_wtime, timestamp);
411 STORE_LE(sb->s_lastcheck, timestamp);
413 STORE_LE(sb->s_state, 1); // TODO: what's 1?
414 STORE_LE(sb->s_creator_os, EXT2_OS_LINUX);
415 STORE_LE(sb->s_checkinterval, 24*60*60 * 180); // 180 days
416 STORE_LE(sb->s_errors, EXT2_ERRORS_DEFAULT);
417 STORE_LE(sb->s_feature_compat, EXT2_FEATURE_COMPAT_SUPP
418 | (EXT2_FEATURE_COMPAT_RESIZE_INO * ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT)
419 | (EXT2_FEATURE_COMPAT_DIR_INDEX * ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX)
421 // e2fsprogs-1.41.9 doesn't like EXT2_FEATURE_INCOMPAT_WHITEOUT
422 STORE_LE(sb->s_feature_incompat, EXT2_FEATURE_INCOMPAT_FILETYPE);// | EXT2_FEATURE_INCOMPAT_WHITEOUT;
423 STORE_LE(sb->s_feature_ro_compat, EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER);
424 STORE_LE(sb->s_flags, EXT2_FLAGS_SIGNED_HASH * ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX);
425 generate_uuid(sb->s_uuid);
426 if (ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX) {
427 STORE_LE(sb->s_def_hash_version, EXT2_HASH_HALF_MD4);
428 generate_uuid((uint8_t *)sb->s_hash_seed);
431 * From e2fsprogs: add "jitter" to the superblock's check interval so that we
432 * don't check all the filesystems at the same time. We use a
433 * kludgy hack of using the UUID to derive a random jitter value.
435 STORE_LE(sb->s_max_mnt_count, EXT2_DFL_MAX_MNT_COUNT
436 + (sb->s_uuid[ARRAY_SIZE(sb->s_uuid)-1] % EXT2_DFL_MAX_MNT_COUNT));
438 // write the label, if any
439 if (label) //opts & OPT_L)
440 safe_strncpy((char *)sb->s_volume_name, label, sizeof(sb->s_volume_name));
442 // fill group descriptors
443 gd = xzalloc(gdtsz * blocksize);
444 buf = xmalloc(blocksize);
445 sb->s_free_blocks_count = 0;
446 for (i = 0, pos = first_data_block, n = nblocks - first_data_block;
448 i++, pos += blocks_per_group, n -= blocks_per_group
450 uint32_t overhead = pos + (has_super(i) ? (1/*sb*/ + gdtsz) : 0);
452 STORE_LE(gd[i].bg_block_bitmap, overhead + 0);
453 STORE_LE(gd[i].bg_inode_bitmap, overhead + 1);
454 STORE_LE(gd[i].bg_inode_table, overhead + 2);
455 overhead = overhead - pos + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
456 gd[i].bg_free_inodes_count = inodes_per_group;
457 //STORE_LE(gd[i].bg_used_dirs_count, 0);
458 // N.B. both root and lost+found dirs are within the first block group, thus +2
461 STORE_LE(gd[i].bg_used_dirs_count, 2);
462 gd[i].bg_free_inodes_count -= EXT2_GOOD_OLD_FIRST_INO;
464 // // N.B. the following is pure heuristics!
465 // // Likely to cope with 1024-byte blocks, when first block is for boot sectors
466 // if (ngroups-1 == i) {
467 // n -= first_data_block;
470 // mark preallocated blocks as allocated
471 fb = (n < blocks_per_group ? n : blocks_per_group) - overhead;
472 //bb_info_msg("ALLOC: [%u][%u][%u]", blocksize, overhead, blocks_per_group - (fb + overhead));
473 allocate(buf, blocksize,
475 blocks_per_group - (fb + overhead)
478 PUT((uint64_t)(FETCH_LE32(gd[i].bg_block_bitmap)) * blocksize, buf, blocksize);
479 STORE_LE(gd[i].bg_free_blocks_count, fb);
481 // mark preallocated inodes as allocated
482 allocate(buf, blocksize,
483 inodes_per_group - gd[i].bg_free_inodes_count,
484 blocks_per_group - inodes_per_group
487 //PUT((uint64_t)(FETCH_LE32(gd[i].bg_block_bitmap)) * blocksize, buf, blocksize);
488 //but it's right after block bitmap, so we can just:
489 xwrite(fd, buf, blocksize);
490 STORE_LE(gd[i].bg_free_inodes_count, gd[i].bg_free_inodes_count);
492 // count overall free blocks
493 sb->s_free_blocks_count += fb;
495 STORE_LE(sb->s_free_blocks_count, sb->s_free_blocks_count);
497 // dump filesystem skeleton structures
498 // printf("Writing superblocks and filesystem accounting information: ");
499 for (i = 0, pos = first_data_block; i < ngroups; i++, pos += blocks_per_group) {
500 // dump superblock and group descriptors and their backups
502 // N.B. 1024 byte blocks are special
503 PUT(((uint64_t)pos << blocksize_log2) + ((0 == i && 0 == first_data_block) ? 1024 : 0), sb, 1024);//blocksize);
504 PUT(((uint64_t)pos << blocksize_log2) + blocksize, gd, gdtsz * blocksize);
509 memset(buf, 0, blocksize);
510 PUT(0, buf, 1024); // N.B. 1024 <= blocksize, so buf[0..1023] contains zeros
512 for (i = 0; i < ngroups; ++i)
513 for (n = 0; n < itsz; ++n)
514 PUT((uint64_t)(FETCH_LE32(gd[i].bg_inode_table) + n) * blocksize, buf, blocksize);
516 // prepare directory inode
517 inode = (struct ext2_inode *)buf;
518 STORE_LE(inode->i_mode, S_IFDIR | S_IRWXU | S_IRGRP | S_IROTH | S_IXGRP | S_IXOTH);
519 STORE_LE(inode->i_mtime, timestamp);
520 STORE_LE(inode->i_atime, timestamp);
521 STORE_LE(inode->i_ctime, timestamp);
522 STORE_LE(inode->i_size, blocksize);
523 // N.B. inode->i_blocks stores the number of 512 byte data blocks. Why on Earth?!
524 STORE_LE(inode->i_blocks, blocksize / 512);
526 // dump root dir inode
527 STORE_LE(inode->i_links_count, 3); // "/.", "/..", "/lost+found/.." point to this inode
528 STORE_LE(inode->i_block[0], FETCH_LE32(gd[0].bg_inode_table) + itsz);
529 PUT(((uint64_t)FETCH_LE32(gd[0].bg_inode_table) << blocksize_log2) + (EXT2_ROOT_INO-1) * sizeof(*inode), buf, sizeof(*inode));
531 // dump lost+found dir inode
532 STORE_LE(inode->i_links_count, 2); // both "/lost+found" and "/lost+found/." point to this inode
533 STORE_LE(inode->i_block[0], inode->i_block[0]+1); // use next block
534 PUT(((uint64_t)FETCH_LE32(gd[0].bg_inode_table) << blocksize_log2) + (EXT2_GOOD_OLD_FIRST_INO-1) * sizeof(*inode), buf, sizeof(*inode));
537 memset(buf, 0, blocksize);
538 dir = (struct ext2_dir *)buf;
540 // dump lost+found dir block
541 STORE_LE(dir->inode1, EXT2_GOOD_OLD_FIRST_INO);
542 STORE_LE(dir->rec_len1, 12);
543 STORE_LE(dir->name_len1, 1);
544 STORE_LE(dir->file_type1, EXT2_FT_DIR);
546 STORE_LE(dir->inode2, EXT2_ROOT_INO);
547 STORE_LE(dir->rec_len2, blocksize - 12);
548 STORE_LE(dir->name_len2, 2);
549 STORE_LE(dir->file_type2, EXT2_FT_DIR);
550 dir->name2[0] = '.'; dir->name2[1] = '.';
551 PUT((uint64_t)(FETCH_LE32(gd[0].bg_inode_table) + itsz + 1) * blocksize, buf, blocksize);
553 // dump root dir block
554 STORE_LE(dir->inode1, EXT2_ROOT_INO);
555 STORE_LE(dir->rec_len2, 12);
556 STORE_LE(dir->inode3, EXT2_GOOD_OLD_FIRST_INO);
557 STORE_LE(dir->rec_len3, blocksize - 12 - 12);
558 STORE_LE(dir->name_len3, 10);
559 STORE_LE(dir->file_type3, EXT2_FT_DIR);
560 strcpy(dir->name3, "lost+found");
561 PUT((uint64_t)(FETCH_LE32(gd[0].bg_inode_table) + itsz + 0) * blocksize, buf, blocksize);
565 if (ENABLE_FEATURE_CLEAN_UP) {