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 "volume_id/volume_id_internal.h"
15 #define ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT 0
16 #define ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX 1
19 #define s_reserved_gdt_blocks s_padding1
20 #define s_mkfs_time s_reserved[0]
21 #define s_flags s_reserved[22]
22 #define EXT2_HASH_HALF_MD4 1
23 #define EXT2_FLAGS_SIGNED_HASH 0x0001
25 // whiteout: for writable overlays
26 //#define LINUX_S_IFWHT 0160000
27 //#define EXT2_FEATURE_INCOMPAT_WHITEOUT 0x0020
30 void BUG_unsupported_field_size(void);
31 #define STORE_LE(field, value) \
33 if (sizeof(field) == 4) \
34 field = cpu_to_le32(value); \
35 else if (sizeof(field) == 2) \
36 field = cpu_to_le16(value); \
37 else if (sizeof(field) == 1) \
40 BUG_unsupported_field_size(); \
43 // All fields are little-endian
62 static inline int int_log2(int arg)
65 while ((arg >>= 1) != 0)
70 // taken from mkfs_minix.c. libbb candidate?
71 static ALWAYS_INLINE unsigned div_roundup(uint32_t size, uint32_t n)
73 return (size + n-1) / n;
76 static void allocate(uint8_t *bitmap, uint32_t blocksize, uint32_t start, uint32_t end)
79 memset(bitmap, 0, blocksize);
81 memset(bitmap, 0xFF, i);
82 bitmap[i] = 0xFF >> (8-(start&7));
83 //bb_info_msg("ALLOC: [%u][%u][%u]: [%u]:=[%x]", blocksize, start, end, blocksize - end/8 - 1, (uint8_t)(0xFF << (8-(end&7))));
85 bitmap[blocksize - i - 1] = 0xFF << (8-(end&7));
86 memset(bitmap + blocksize - i, 0xFF, i); // N.B. no overflow here!
90 // TODO: get rid of FPU
91 static bool is_power_of(uint32_t x, uint16_t n)
93 // return (!(x % n) && is_power_of(x / n, n));
94 double z = logf(x)/logf(n);
98 static uint32_t has_super(uint32_t x)
100 return (0 == x || 1 == x || is_power_of(x, 3) || is_power_of(x, 5) || is_power_of(x, 7));
105 static uint32_t has_super(uint32_t x)
107 static const uint32_t supers[] = {
108 0, 1, 3, 5, 7, 9, 25, 27, 49, 81, 125, 243, 343, 625, 729,
109 2187, 2401, 3125, 6561, 15625, 16807, 19683, 59049, 78125,
110 117649, 177147, 390625, 531441, 823543, 1594323, 1953125,
111 4782969, 5764801, 9765625, 14348907, 40353607, 43046721,
112 48828125, 129140163, 244140625, 282475249, 387420489,
113 1162261467, 1220703125, 1977326743, 3486784401/* >2^31 */,
115 const uint32_t *sp = supers + ARRAY_SIZE(supers)-1;
126 /* Standard mke2fs 1.41.9:
127 * Usage: mke2fs [-c|-l filename] [-b block-size] [-f fragment-size]
128 * [-i bytes-per-inode] [-I inode-size] [-J journal-options]
129 * [-G meta group size] [-N number-of-inodes]
130 * [-m reserved-blocks-percentage] [-o creator-os]
131 * [-g blocks-per-group] [-L volume-label] [-M last-mounted-directory]
132 * [-O feature[,...]] [-r fs-revision] [-E extended-option[,...]]
133 * [-T fs-type] [-U UUID] [-jnqvFSV] device [blocks-count]
135 // N.B. not commented below options are taken and silently ignored
139 OPT_b = 1 << 2, // block size, in bytes
141 OPT_i = 1 << 4, // bytes per inode
146 OPT_m = 1 << 9, // percentage of blocks reserved for superuser
149 OPT_L = 1 << 12, // label
162 //OPT_V = 1 << 25, // -V version. bbox applets don't support that
165 #define fd 3 /* predefined output descriptor */
167 static void PUT(uint64_t off, void *buf, uint32_t size)
169 if (!(option_mask32 & OPT_n)) {
170 xlseek(fd, off, SEEK_SET);
171 xwrite(fd, buf, size);
175 int mkfs_ext2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
176 int mkfs_ext2_main(int argc UNUSED_PARAM, char **argv)
179 unsigned bs, blocksize;
180 unsigned nreserved = 5;
183 unsigned bytes_per_inode;
184 uint32_t nblocks_per_group;
185 uint32_t first_data_block;
187 uint32_t ninodes_per_group;
188 uint32_t gdtsz, rgdtsz, itsz;
193 struct ext2_super_block *sb; // superblock
194 struct ext2_group_desc *gd; // group descriptors
195 struct ext2_inode *inode;
196 struct ext2_dir *dir;
199 bs = EXT2_MIN_BLOCK_SIZE;
200 opt_complementary = "-1:b+:m+:i+";
201 opts = getopt32(argv, "cl:b:f:i:I:J:G:N:m:o:g:L:M:O:r:E:T:U:jnqvFS",
202 NULL, &bs, NULL, &bytes_per_inode, NULL, NULL, NULL, NULL,
203 &nreserved, NULL, NULL, &label, NULL, NULL, NULL, NULL, NULL, NULL);
204 argv += optind; // argv[0] -- device
206 // block size minimax, block size is a multiple of minimum
208 if (blocksize < EXT2_MIN_BLOCK_SIZE
209 || blocksize > EXT2_MAX_BLOCK_SIZE
210 || (blocksize & (blocksize - 1)) // not power of 2
212 bb_error_msg_and_die("-%c is bad", 'b');
215 // reserved blocks count
217 bb_error_msg_and_die("-%c is bad", 'm');
219 // check the device is a block device
221 if (!S_ISBLK(st.st_mode) && !(opts & OPT_F))
222 bb_error_msg_and_die("not a block device");
224 // check if it is mounted
225 // N.B. what if we format a file? find_mount_point will return false negative since
226 // it is loop block device which mounted!
227 if (find_mount_point(argv[0], 0))
228 bb_error_msg_and_die("can't format mounted filesystem");
230 // TODO: 5?/5 WE MUST NOT DEPEND ON WHETHER DEVICE IS /dev/zero 'ed OR NOT
231 // TODO: 3/5 refuse if mounted
232 // TODO: 4/5 compat options
233 // TODO: 1/5 sanity checks
234 // TODO: 0/5 more verbose error messages
235 // TODO: 0/5 info printing
236 // TODO: 2/5 bigendianness! Spot where it comes to play! sb->, gd->
237 // TODO: 2/5 reserved GDT: how to mark but not allocate?
238 // TODO: 0/5 dir_index?
240 // fill the superblock
241 sb = xzalloc(blocksize);
242 sb->s_rev_level = 1; // revision 1 filesystem
243 sb->s_magic = EXT2_SUPER_MAGIC;
244 sb->s_inode_size = sizeof(*inode);
245 sb->s_first_ino = EXT2_GOOD_OLD_FIRST_INO;
246 sb->s_log_block_size = sb->s_log_frag_size = int_log2(blocksize >> EXT2_MIN_BLOCK_LOG_SIZE);
247 // first 1024 bytes of the device are for boot record. If block size is 1024 bytes, then
248 // the first block available for data is 1, otherwise 0
249 first_data_block = sb->s_first_data_block = (EXT2_MIN_BLOCK_SIZE == blocksize);
250 // block and inode bitmaps occupy no more than one block, so maximum number of blocks is
251 // number of bits in one block, i.e. 8*blocksize
252 nblocks_per_group = sb->s_blocks_per_group = sb->s_frags_per_group = sb->s_inodes_per_group = 8*blocksize;
253 timestamp = time(NULL);
254 sb->s_mkfs_time = sb->s_wtime = sb->s_lastcheck = timestamp;
256 sb->s_creator_os = EXT2_OS_LINUX;
257 sb->s_max_mnt_count = EXT2_DFL_MAX_MNT_COUNT;
258 sb->s_checkinterval = 24*60*60 * 180; // 180 days
259 sb->s_errors = EXT2_ERRORS_DEFAULT;
260 sb->s_feature_compat = EXT2_FEATURE_COMPAT_SUPP
261 | (EXT2_FEATURE_COMPAT_RESIZE_INO * ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT)
262 | (EXT2_FEATURE_COMPAT_DIR_INDEX * ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX)
264 // e2fsprogs-1.41.9 doesn't like EXT2_FEATURE_INCOMPAT_WHITEOUT
265 sb->s_feature_incompat = EXT2_FEATURE_INCOMPAT_FILETYPE;// | EXT2_FEATURE_INCOMPAT_WHITEOUT;
266 sb->s_feature_ro_compat = EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER;
267 sb->s_flags = EXT2_FLAGS_SIGNED_HASH * ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX;
268 generate_uuid(sb->s_uuid);
269 #if ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX
270 sb->s_def_hash_version = EXT2_HASH_HALF_MD4;
271 generate_uuid((uint8_t *)sb->s_hash_seed);
274 * From e2fsprogs: add "jitter" to the superblock's check interval so that we
275 * don't check all the filesystems at the same time. We use a
276 * kludgy hack of using the UUID to derive a random jitter value.
278 for (i = 0, n = 0; i < sizeof(sb->s_uuid); i++)
280 sb->s_max_mnt_count += n % EXT2_DFL_MAX_MNT_COUNT;
282 // open the device, get number of blocks
283 xmove_fd(xopen3(argv[0], O_WRONLY | O_CREAT, 0666), fd);
285 nblocks = xatou(argv[1]);
287 nblocks = ((uoff_t)xlseek(fd, 0, SEEK_END)) / blocksize;
288 xlseek(fd, 0, SEEK_SET);
290 sb->s_blocks_count = nblocks;
292 // nblocks is the total number of blocks in the filesystem
294 bb_error_msg_and_die("nblocks");
295 // reserve blocks for superuser
296 sb->s_r_blocks_count = ((uint64_t) nblocks * nreserved) / 100;
298 // N.B. a block group can have no more than nblocks_per_group blocks
299 ngroups = div_roundup(nblocks - first_data_block, nblocks_per_group);
301 bb_error_msg_and_die("ngroups");
302 gdtsz = div_roundup(ngroups, EXT2_DESC_PER_BLOCK(sb));
304 * From e2fsprogs: Calculate the number of GDT blocks to reserve for online
306 * The absolute maximum number of GDT blocks we can reserve is determined by
307 * the number of block pointers that can fit into a single block.
309 /* We set it at 1024x the current filesystem size, or
310 * the upper block count limit (2^32), whichever is lower.
312 #if ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT
313 rgdtsz = 0xFFFFFFFF; // maximum block number
314 if (nblocks < rgdtsz / 1024)
315 rgdtsz = nblocks * 1024;
316 rgdtsz = div_roundup(rgdtsz - first_data_block, nblocks_per_group);
317 rgdtsz = div_roundup(rgdtsz, EXT2_DESC_PER_BLOCK(sb)) - gdtsz;
318 if (rgdtsz > EXT2_ADDR_PER_BLOCK(sb))
319 rgdtsz = EXT2_ADDR_PER_BLOCK(sb);
320 sb->s_reserved_gdt_blocks = rgdtsz;
321 //bb_info_msg("RSRVD[%u]", n);
326 // ninodes is the total number of inodes (files) in the file system
327 if (!(opts & OPT_i)) {
328 bytes_per_inode = 16384;
329 if (nblocks < 512*1024)
330 bytes_per_inode = 4096;
331 if (nblocks < 3*1024)
332 bytes_per_inode = 8192;
334 ninodes = nblocks / (bytes_per_inode / blocksize);
335 if (ninodes < EXT2_GOOD_OLD_FIRST_INO+1)
336 ninodes = EXT2_GOOD_OLD_FIRST_INO+1;
337 ninodes_per_group = div_roundup(ninodes, ngroups);
338 if (ninodes_per_group < 16)
339 ninodes_per_group = 16; // minimum number because the first 10 are reserved
340 // N.B. a block group can have no more than 8*blocksize = sb->s_inodes_per_group inodes
341 if (ninodes_per_group > sb->s_inodes_per_group)
342 ninodes_per_group = sb->s_inodes_per_group;
343 // adjust inodes per group so they completely fill the inode table blocks in the descriptor
344 ninodes_per_group = ((div_roundup(ninodes_per_group * EXT2_INODE_SIZE(sb), blocksize) * blocksize) / EXT2_INODE_SIZE(sb));
345 // make sure the number of inodes per group is a multiple of 8
346 ninodes_per_group &= ~7;
347 sb->s_inodes_per_group = ninodes_per_group;// = div_roundup(ninodes_per_group * sb->s_inode_size, blocksize);
349 ninodes = sb->s_inodes_count = ninodes_per_group * ngroups;
351 itsz = ninodes_per_group * sb->s_inode_size / blocksize;
352 sb->s_free_inodes_count = sb->s_inodes_count - EXT2_GOOD_OLD_FIRST_INO;
354 // write the label, if any
356 safe_strncpy((char *)sb->s_volume_name, label, sizeof(sb->s_volume_name));
358 // fill group descriptors
359 gd = xzalloc((gdtsz + rgdtsz) * blocksize);
360 sb->s_free_blocks_count = 0;
361 for (i = 0, pos = first_data_block, n = nblocks;
363 i++, pos += nblocks_per_group, n -= nblocks_per_group
365 uint32_t overhead = pos + (has_super(i) ? (1/*sb*/ + gdtsz + rgdtsz) : 0);
366 gd[i].bg_block_bitmap = overhead + 0;
367 gd[i].bg_inode_bitmap = overhead + 1;
368 gd[i].bg_inode_table = overhead + 2;
369 overhead = overhead - pos + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
370 gd[i].bg_free_inodes_count = ninodes_per_group;
371 // N.B. both root and lost+found dirs are within the first block group, thus +2
372 //gd[i].bg_used_dirs_count = 0;
375 gd[i].bg_used_dirs_count = 2;
376 gd[i].bg_free_inodes_count -= EXT2_GOOD_OLD_FIRST_INO;
378 // N.B. the following is pure heuristics!
379 // Likely to cope with 1024-byte blocks, when first block is for boot sectors
380 if (ngroups-1 == i) {
381 overhead += first_data_block;
383 gd[i].bg_free_blocks_count = (n < nblocks_per_group ? n : nblocks_per_group) - overhead;
384 sb->s_free_blocks_count += gd[i].bg_free_blocks_count;
386 STORE_LE(sb->s_free_blocks_count, sb->s_free_blocks_count);
388 // dump filesystem skeleton structures
389 buf = xmalloc(blocksize);
390 for (i = 0, pos = first_data_block; i < ngroups; i++, pos += nblocks_per_group) {
391 uint32_t overhead = has_super(i) ? (1/*sb*/ + gdtsz + rgdtsz) : 0;
392 uint32_t start;// = has_super(i) ? (1/*sb*/ + gdtsz + rgdtsz) : 0;
395 // dump superblock and group descriptors and their backups
396 if (overhead) { // N.B. in fact, we want (has_super(i)) condition, but it is equal to (overhead != 0) and is cheaper
397 //bb_info_msg("SUPER@[%d]", pos);
398 // N.B. 1024 byte blocks are special
399 PUT(blocksize * pos + ((0 == i && 0 == first_data_block) ? 1024 : 0), sb, blocksize);
400 PUT(blocksize * pos + blocksize, gd, (gdtsz + rgdtsz) * blocksize);
403 start = overhead + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
405 start += 2; // for / and /lost+found
406 end = nblocks_per_group - (start + gd[i].bg_free_blocks_count);
407 // mark preallocated blocks as allocated
408 allocate(buf, blocksize, start, end);
410 PUT((pos + overhead) * blocksize, buf, blocksize);
412 // mark preallocated inodes as allocated
413 allocate(buf, blocksize,
414 ninodes_per_group - gd[i].bg_free_inodes_count,
415 8*blocksize - ninodes_per_group
418 PUT((pos + overhead + 1) * blocksize, buf, blocksize);
423 memset(buf, 0, blocksize);
424 PUT(0, buf, 1024); // N.B. 1024 <= blocksize
426 for (i = 0; i < ngroups; ++i)
427 for (n = 0; n < itsz; ++n)
428 PUT((gd[i].bg_inode_table + n) * blocksize, buf, blocksize);
430 // prepare directory inode
431 inode = (struct ext2_inode *)buf;
432 STORE_LE(inode->i_mode, S_IFDIR | S_IRWXU | S_IRGRP | S_IROTH | S_IXGRP | S_IXOTH);
433 inode->i_mtime = inode->i_atime = timestamp;
434 STORE_LE(inode->i_ctime, timestamp);
435 STORE_LE(inode->i_size, blocksize);
436 // N.B. inode->i_blocks stores the number of 512 byte data blocks. Why on Earth?!
437 STORE_LE(inode->i_blocks, blocksize / 512);
439 // dump root dir inode
440 STORE_LE(inode->i_links_count, 3); // "/.", "/..", "/lost+found/.." point to this inode
441 STORE_LE(inode->i_block[0], gd[0].bg_inode_table + itsz);
442 PUT(gd[0].bg_inode_table * blocksize + (EXT2_ROOT_INO-1) * sizeof(*inode), buf, sizeof(*inode));
444 // dump lost+found dir inode
445 STORE_LE(inode->i_links_count, 2); // both "/lost+found" and "/lost+found/." point to this inode
446 STORE_LE(inode->i_block[0], inode->i_block[0]+1); // use next block //= gd[0].bg_inode_table + itsz + 1;
447 PUT(gd[0].bg_inode_table * blocksize + (EXT2_GOOD_OLD_FIRST_INO-1) * sizeof(*inode), buf, sizeof(*inode));
450 memset(buf, 0, blocksize);
451 dir = (struct ext2_dir *)buf;
453 // dump lost+found dir block
454 STORE_LE(dir->inode1, EXT2_GOOD_OLD_FIRST_INO);
455 STORE_LE(dir->rec_len1, 12);
456 STORE_LE(dir->name_len1, 1);
457 STORE_LE(dir->file_type1, EXT2_FT_DIR);
459 STORE_LE(dir->inode2, EXT2_ROOT_INO);
460 STORE_LE(dir->rec_len2, blocksize - 12);
461 STORE_LE(dir->name_len2, 2);
462 STORE_LE(dir->file_type2, EXT2_FT_DIR);
463 dir->name2[0] = '.'; dir->name2[1] = '.';
464 PUT((gd[0].bg_inode_table + itsz + 1) * blocksize, buf, blocksize);
466 // dump root dir block
467 STORE_LE(dir->inode1, EXT2_ROOT_INO);
468 STORE_LE(dir->rec_len2, 12);
469 STORE_LE(dir->inode3, EXT2_GOOD_OLD_FIRST_INO);
470 STORE_LE(dir->rec_len3, blocksize - 12 - 12);
471 STORE_LE(dir->name_len3, 10);
472 STORE_LE(dir->file_type3, EXT2_FT_DIR);
473 strcpy(dir->name3, "lost+found");
474 PUT((gd[0].bg_inode_table + itsz + 0) * blocksize, buf, blocksize);
477 if (ENABLE_FEATURE_CLEAN_UP) {