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 unsigned int_log2(unsigned arg)
65 while ((arg >>= 1) != 0)
70 // taken from mkfs_minix.c. libbb candidate?
71 static 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 sb->s_max_mnt_count += sb->s_uuid[ARRAY_SIZE(sb->s_uuid)-1] % EXT2_DFL_MAX_MNT_COUNT;
280 // open the device, get number of blocks
281 xmove_fd(xopen3(argv[0], O_WRONLY | O_CREAT, 0666), fd);
283 nblocks = xatou(argv[1]);
285 nblocks = ((uoff_t)xlseek(fd, 0, SEEK_END)) / blocksize;
287 sb->s_blocks_count = nblocks;
289 // nblocks is the total number of blocks in the filesystem
291 bb_error_msg_and_die("nblocks");
292 // reserve blocks for superuser
293 sb->s_r_blocks_count = ((uint64_t) nblocks * nreserved) / 100;
295 // N.B. a block group can have no more than nblocks_per_group blocks
296 ngroups = div_roundup(nblocks - first_data_block, nblocks_per_group);
298 bb_error_msg_and_die("ngroups");
299 gdtsz = div_roundup(ngroups, EXT2_DESC_PER_BLOCK(sb));
301 * From e2fsprogs: Calculate the number of GDT blocks to reserve for online
303 * The absolute maximum number of GDT blocks we can reserve is determined by
304 * the number of block pointers that can fit into a single block.
306 /* We set it at 1024x the current filesystem size, or
307 * the upper block count limit (2^32), whichever is lower.
309 #if ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT
310 rgdtsz = 0xFFFFFFFF; // maximum block number
311 if (nblocks < rgdtsz / 1024)
312 rgdtsz = nblocks * 1024;
313 rgdtsz = div_roundup(rgdtsz - first_data_block, nblocks_per_group);
314 rgdtsz = div_roundup(rgdtsz, EXT2_DESC_PER_BLOCK(sb)) - gdtsz;
315 if (rgdtsz > EXT2_ADDR_PER_BLOCK(sb))
316 rgdtsz = EXT2_ADDR_PER_BLOCK(sb);
317 sb->s_reserved_gdt_blocks = rgdtsz;
318 //bb_info_msg("RSRVD[%u]", n);
323 // ninodes is the total number of inodes (files) in the file system
324 if (!(opts & OPT_i)) {
325 bytes_per_inode = 16384;
326 if (nblocks < 512*1024)
327 bytes_per_inode = 4096;
328 if (nblocks < 3*1024)
329 bytes_per_inode = 8192;
331 ninodes = nblocks / (bytes_per_inode / blocksize);
332 if (ninodes < EXT2_GOOD_OLD_FIRST_INO+1)
333 ninodes = EXT2_GOOD_OLD_FIRST_INO+1;
334 ninodes_per_group = div_roundup(ninodes, ngroups);
335 if (ninodes_per_group < 16)
336 ninodes_per_group = 16; // minimum number because the first 10 are reserved
337 // N.B. a block group can have no more than 8*blocksize = sb->s_inodes_per_group inodes
338 if (ninodes_per_group > sb->s_inodes_per_group)
339 ninodes_per_group = sb->s_inodes_per_group;
340 // adjust inodes per group so they completely fill the inode table blocks in the descriptor
341 ninodes_per_group = ((div_roundup(ninodes_per_group * EXT2_INODE_SIZE(sb), blocksize) * blocksize) / EXT2_INODE_SIZE(sb));
342 // make sure the number of inodes per group is a multiple of 8
343 ninodes_per_group &= ~7;
344 sb->s_inodes_per_group = ninodes_per_group;// = div_roundup(ninodes_per_group * sb->s_inode_size, blocksize);
346 ninodes = sb->s_inodes_count = ninodes_per_group * ngroups;
348 itsz = ninodes_per_group * sb->s_inode_size / blocksize;
349 sb->s_free_inodes_count = sb->s_inodes_count - EXT2_GOOD_OLD_FIRST_INO;
351 // write the label, if any
353 safe_strncpy((char *)sb->s_volume_name, label, sizeof(sb->s_volume_name));
355 // fill group descriptors
356 gd = xzalloc((gdtsz + rgdtsz) * blocksize);
357 sb->s_free_blocks_count = 0;
358 for (i = 0, pos = first_data_block, n = nblocks;
360 i++, pos += nblocks_per_group, n -= nblocks_per_group
362 uint32_t overhead = pos + (has_super(i) ? (1/*sb*/ + gdtsz + rgdtsz) : 0);
363 gd[i].bg_block_bitmap = overhead + 0;
364 gd[i].bg_inode_bitmap = overhead + 1;
365 gd[i].bg_inode_table = overhead + 2;
366 overhead = overhead - pos + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
367 gd[i].bg_free_inodes_count = ninodes_per_group;
368 // N.B. both root and lost+found dirs are within the first block group, thus +2
369 //gd[i].bg_used_dirs_count = 0;
372 gd[i].bg_used_dirs_count = 2;
373 gd[i].bg_free_inodes_count -= EXT2_GOOD_OLD_FIRST_INO;
375 // N.B. the following is pure heuristics!
376 // Likely to cope with 1024-byte blocks, when first block is for boot sectors
377 if (ngroups-1 == i) {
378 overhead += first_data_block;
380 gd[i].bg_free_blocks_count = (n < nblocks_per_group ? n : nblocks_per_group) - overhead;
381 sb->s_free_blocks_count += gd[i].bg_free_blocks_count;
383 STORE_LE(sb->s_free_blocks_count, sb->s_free_blocks_count);
385 // dump filesystem skeleton structures
386 buf = xmalloc(blocksize);
387 for (i = 0, pos = first_data_block; i < ngroups; i++, pos += nblocks_per_group) {
388 uint32_t overhead = has_super(i) ? (1/*sb*/ + gdtsz + rgdtsz) : 0;
389 uint32_t start;// = has_super(i) ? (1/*sb*/ + gdtsz + rgdtsz) : 0;
392 // dump superblock and group descriptors and their backups
393 if (overhead) { // N.B. in fact, we want (has_super(i)) condition, but it is equal to (overhead != 0) and is cheaper
394 //bb_info_msg("SUPER@[%d]", pos);
395 // N.B. 1024 byte blocks are special
396 PUT(blocksize * pos + ((0 == i && 0 == first_data_block) ? 1024 : 0), sb, blocksize);
397 PUT(blocksize * pos + blocksize, gd, (gdtsz + rgdtsz) * blocksize);
400 start = overhead + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
402 start += 2; // for / and /lost+found
403 end = nblocks_per_group - (start + gd[i].bg_free_blocks_count);
404 // mark preallocated blocks as allocated
405 allocate(buf, blocksize, start, end);
407 PUT((pos + overhead) * blocksize, buf, blocksize);
409 // mark preallocated inodes as allocated
410 allocate(buf, blocksize,
411 ninodes_per_group - gd[i].bg_free_inodes_count,
412 8*blocksize - ninodes_per_group
415 PUT((pos + overhead + 1) * blocksize, buf, blocksize);
419 memset(buf, 0, blocksize);
420 PUT(0, buf, 1024); // N.B. 1024 <= blocksize
422 for (i = 0; i < ngroups; ++i)
423 for (n = 0; n < itsz; ++n)
424 PUT((gd[i].bg_inode_table + n) * blocksize, buf, blocksize);
426 // prepare directory inode
427 inode = (struct ext2_inode *)buf;
428 STORE_LE(inode->i_mode, S_IFDIR | S_IRWXU | S_IRGRP | S_IROTH | S_IXGRP | S_IXOTH);
429 inode->i_mtime = inode->i_atime = timestamp;
430 STORE_LE(inode->i_ctime, timestamp);
431 STORE_LE(inode->i_size, blocksize);
432 // N.B. inode->i_blocks stores the number of 512 byte data blocks. Why on Earth?!
433 STORE_LE(inode->i_blocks, blocksize / 512);
435 // dump root dir inode
436 STORE_LE(inode->i_links_count, 3); // "/.", "/..", "/lost+found/.." point to this inode
437 STORE_LE(inode->i_block[0], gd[0].bg_inode_table + itsz);
438 PUT(gd[0].bg_inode_table * blocksize + (EXT2_ROOT_INO-1) * sizeof(*inode), buf, sizeof(*inode));
440 // dump lost+found dir inode
441 STORE_LE(inode->i_links_count, 2); // both "/lost+found" and "/lost+found/." point to this inode
442 STORE_LE(inode->i_block[0], inode->i_block[0]+1); // use next block //= gd[0].bg_inode_table + itsz + 1;
443 PUT(gd[0].bg_inode_table * blocksize + (EXT2_GOOD_OLD_FIRST_INO-1) * sizeof(*inode), buf, sizeof(*inode));
446 memset(buf, 0, blocksize);
447 dir = (struct ext2_dir *)buf;
449 // dump lost+found dir block
450 STORE_LE(dir->inode1, EXT2_GOOD_OLD_FIRST_INO);
451 STORE_LE(dir->rec_len1, 12);
452 STORE_LE(dir->name_len1, 1);
453 STORE_LE(dir->file_type1, EXT2_FT_DIR);
455 STORE_LE(dir->inode2, EXT2_ROOT_INO);
456 STORE_LE(dir->rec_len2, blocksize - 12);
457 STORE_LE(dir->name_len2, 2);
458 STORE_LE(dir->file_type2, EXT2_FT_DIR);
459 dir->name2[0] = '.'; dir->name2[1] = '.';
460 PUT((gd[0].bg_inode_table + itsz + 1) * blocksize, buf, blocksize);
462 // dump root dir block
463 STORE_LE(dir->inode1, EXT2_ROOT_INO);
464 STORE_LE(dir->rec_len2, 12);
465 STORE_LE(dir->inode3, EXT2_GOOD_OLD_FIRST_INO);
466 STORE_LE(dir->rec_len3, blocksize - 12 - 12);
467 STORE_LE(dir->name_len3, 10);
468 STORE_LE(dir->file_type3, EXT2_FT_DIR);
469 strcpy(dir->name3, "lost+found");
470 PUT((gd[0].bg_inode_table + itsz + 0) * blocksize, buf, blocksize);
473 if (ENABLE_FEATURE_CLEAN_UP) {