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 */,
116 for (i = ARRAY_SIZE(supers); --i >= 0;)
123 /* Standard mke2fs 1.41.9:
124 * Usage: mke2fs [-c|-l filename] [-b block-size] [-f fragment-size]
125 * [-i bytes-per-inode] [-I inode-size] [-J journal-options]
126 * [-G meta group size] [-N number-of-inodes]
127 * [-m reserved-blocks-percentage] [-o creator-os]
128 * [-g blocks-per-group] [-L volume-label] [-M last-mounted-directory]
129 * [-O feature[,...]] [-r fs-revision] [-E extended-option[,...]]
130 * [-T fs-type] [-U UUID] [-jnqvFSV] device [blocks-count]
132 // N.B. not commented below options are taken and silently ignored
136 OPT_b = 1 << 2, // block size, in bytes
138 OPT_i = 1 << 4, // bytes per inode
143 OPT_m = 1 << 9, // percentage of blocks reserved for superuser
146 OPT_L = 1 << 12, // label
159 //OPT_V = 1 << 25, // -V version. bbox applets don't support that
162 #define fd 3 /* predefined output descriptor */
164 static void PUT(uint64_t off, void *buf, uint32_t size)
166 if (!(option_mask32 & OPT_n)) {
167 xlseek(fd, off, SEEK_SET);
168 xwrite(fd, buf, size);
172 int mkfs_ext2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
173 int mkfs_ext2_main(int argc UNUSED_PARAM, char **argv)
176 unsigned bs, blocksize;
177 unsigned nreserved = 5;
180 unsigned bytes_per_inode;
181 uint32_t nblocks_per_group;
182 uint32_t first_data_block;
184 uint32_t ninodes_per_group;
185 uint32_t gdtsz, rgdtsz, itsz;
190 struct ext2_super_block *sb; // superblock
191 struct ext2_group_desc *gd; // group descriptors
192 struct ext2_inode *inode;
193 struct ext2_dir *dir;
196 bs = EXT2_MIN_BLOCK_SIZE;
197 opt_complementary = "-1:b+:m+:i+";
198 opts = getopt32(argv, "cl:b:f:i:I:J:G:N:m:o:g:L:M:O:r:E:T:U:jnqvFS",
199 NULL, &bs, NULL, &bytes_per_inode, NULL, NULL, NULL, NULL,
200 &nreserved, NULL, NULL, &label, NULL, NULL, NULL, NULL, NULL, NULL);
201 argv += optind; // argv[0] -- device
203 // block size minimax, block size is a multiple of minimum
205 if (blocksize < EXT2_MIN_BLOCK_SIZE
206 || blocksize > EXT2_MAX_BLOCK_SIZE
207 || (blocksize & (blocksize - 1)) // not power of 2
209 bb_error_msg_and_die("-%c is bad", 'b');
212 // reserved blocks count
214 bb_error_msg_and_die("-%c is bad", 'm');
216 // check the device is a block device
218 if (!S_ISBLK(st.st_mode) && !(opts & OPT_F))
219 bb_error_msg_and_die("not a block device");
221 // check if it is mounted
222 // N.B. what if we format a file? find_mount_point will return false negative since
223 // it is loop block device which mounted!
224 if (find_mount_point(argv[0], 0))
225 bb_error_msg_and_die("can't format mounted filesystem");
227 // TODO: 5?/5 WE MUST NOT DEPEND ON WHETHER DEVICE IS /dev/zero 'ed OR NOT
228 // TODO: 3/5 refuse if mounted
229 // TODO: 4/5 compat options
230 // TODO: 1/5 sanity checks
231 // TODO: 0/5 more verbose error messages
232 // TODO: 0/5 info printing
233 // TODO: 2/5 bigendianness! Spot where it comes to play! sb->, gd->
234 // TODO: 2/5 reserved GDT: how to mark but not allocate?
235 // TODO: 0/5 dir_index?
237 // fill the superblock
238 sb = xzalloc(blocksize);
239 sb->s_rev_level = 1; // revision 1 filesystem
240 sb->s_magic = EXT2_SUPER_MAGIC;
241 sb->s_inode_size = sizeof(*inode);
242 sb->s_first_ino = EXT2_GOOD_OLD_FIRST_INO;
243 sb->s_log_block_size = sb->s_log_frag_size = int_log2(blocksize >> EXT2_MIN_BLOCK_LOG_SIZE);
244 // first 1024 bytes of the device are for boot record. If block size is 1024 bytes, then
245 // the first block available for data is 1, otherwise 0
246 first_data_block = sb->s_first_data_block = (EXT2_MIN_BLOCK_SIZE == blocksize);
247 // block and inode bitmaps occupy no more than one block, so maximum number of blocks is
248 // number of bits in one block, i.e. 8*blocksize
249 nblocks_per_group = sb->s_blocks_per_group = sb->s_frags_per_group = sb->s_inodes_per_group = 8*blocksize;
250 timestamp = time(NULL);
251 sb->s_mkfs_time = sb->s_wtime = sb->s_lastcheck = timestamp;
253 sb->s_creator_os = EXT2_OS_LINUX;
254 sb->s_max_mnt_count = EXT2_DFL_MAX_MNT_COUNT;
255 sb->s_checkinterval = 24*60*60 * 180; // 180 days
256 sb->s_errors = EXT2_ERRORS_DEFAULT;
257 sb->s_feature_compat = EXT2_FEATURE_COMPAT_SUPP
258 | (EXT2_FEATURE_COMPAT_RESIZE_INO * ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT)
259 | (EXT2_FEATURE_COMPAT_DIR_INDEX * ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX)
261 // e2fsprogs-1.41.9 doesn't like EXT2_FEATURE_INCOMPAT_WHITEOUT
262 sb->s_feature_incompat = EXT2_FEATURE_INCOMPAT_FILETYPE;// | EXT2_FEATURE_INCOMPAT_WHITEOUT;
263 sb->s_feature_ro_compat = EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER;
264 sb->s_flags = EXT2_FLAGS_SIGNED_HASH * ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX;
265 generate_uuid(sb->s_uuid);
266 #if ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX
267 sb->s_def_hash_version = EXT2_HASH_HALF_MD4;
268 generate_uuid((uint8_t *)sb->s_hash_seed);
271 * From e2fsprogs: add "jitter" to the superblock's check interval so that we
272 * don't check all the filesystems at the same time. We use a
273 * kludgy hack of using the UUID to derive a random jitter value.
275 for (i = 0, n = 0; i < sizeof(sb->s_uuid); i++)
277 sb->s_max_mnt_count += n % EXT2_DFL_MAX_MNT_COUNT;
279 // open the device, get number of blocks
280 xmove_fd(xopen3(argv[0], O_WRONLY | O_CREAT, 0666), fd);
282 nblocks = xatou(argv[1]);
284 nblocks = ((uoff_t)xlseek(fd, 0, SEEK_END)) / blocksize;
285 xlseek(fd, 0, SEEK_SET);
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);
420 memset(buf, 0, blocksize);
421 PUT(0, buf, 1024); // N.B. 1024 <= blocksize
423 for (i = 0; i < ngroups; ++i)
424 for (n = 0; n < itsz; ++n)
425 PUT((gd[i].bg_inode_table + n) * blocksize, buf, blocksize);
427 // prepare directory inode
428 inode = (struct ext2_inode *)buf;
429 STORE_LE(inode->i_mode, S_IFDIR | S_IRWXU | S_IRGRP | S_IROTH | S_IXGRP | S_IXOTH);
430 inode->i_mtime = inode->i_atime = timestamp;
431 STORE_LE(inode->i_ctime, timestamp);
432 STORE_LE(inode->i_size, blocksize);
433 // N.B. inode->i_blocks stores the number of 512 byte data blocks. Why on Earth?!
434 STORE_LE(inode->i_blocks, blocksize / 512);
436 // dump root dir inode
437 STORE_LE(inode->i_links_count, 3); // "/.", "/..", "/lost+found/.." point to this inode
438 STORE_LE(inode->i_block[0], gd[0].bg_inode_table + itsz);
439 PUT(gd[0].bg_inode_table * blocksize + (EXT2_ROOT_INO-1) * sizeof(*inode), buf, sizeof(*inode));
441 // dump lost+found dir inode
442 STORE_LE(inode->i_links_count, 2); // both "/lost+found" and "/lost+found/." point to this inode
443 STORE_LE(inode->i_block[0], inode->i_block[0]+1); // use next block //= gd[0].bg_inode_table + itsz + 1;
444 PUT(gd[0].bg_inode_table * blocksize + (EXT2_GOOD_OLD_FIRST_INO-1) * sizeof(*inode), buf, sizeof(*inode));
447 memset(buf, 0, blocksize);
448 dir = (struct ext2_dir *)buf;
450 // dump lost+found dir block
451 STORE_LE(dir->inode1, EXT2_GOOD_OLD_FIRST_INO);
452 STORE_LE(dir->rec_len1, 12);
453 STORE_LE(dir->name_len1, 1);
454 STORE_LE(dir->file_type1, EXT2_FT_DIR);
456 STORE_LE(dir->inode2, EXT2_ROOT_INO);
457 STORE_LE(dir->rec_len2, blocksize - 12);
458 STORE_LE(dir->name_len2, 2);
459 STORE_LE(dir->file_type2, EXT2_FT_DIR);
460 dir->name2[0] = '.'; dir->name2[1] = '.';
461 PUT((gd[0].bg_inode_table + itsz + 1) * blocksize, buf, blocksize);
463 // dump root dir block
464 STORE_LE(dir->inode1, EXT2_ROOT_INO);
465 STORE_LE(dir->rec_len2, 12);
466 STORE_LE(dir->inode3, EXT2_GOOD_OLD_FIRST_INO);
467 STORE_LE(dir->rec_len3, blocksize - 12 - 12);
468 STORE_LE(dir->name_len3, 10);
469 STORE_LE(dir->file_type3, EXT2_FT_DIR);
470 strcpy(dir->name3, "lost+found");
471 PUT((gd[0].bg_inode_table + itsz + 0) * blocksize, buf, blocksize);
474 if (ENABLE_FEATURE_CLEAN_UP) {