8df9f1a66c80713e93952df7b78def1c0dceafed
[oweals/busybox.git] / util-linux / mkfs_ext2.c
1 /* vi: set sw=4 ts=4: */
2 /*
3  * mkfs_ext2: utility to create EXT2 filesystem
4  * inspired by genext2fs
5  *
6  * Busybox'ed (2009) by Vladimir Dronnikov <dronnikov@gmail.com>
7  *
8  * Licensed under GPLv2, see file LICENSE in this tarball for details.
9  */
10 #include "libbb.h"
11 #include <linux/fs.h>
12 #include <linux/ext2_fs.h>
13 #include "volume_id/volume_id_internal.h"
14
15 #define ENABLE_FEATURE_MKFS_EXT2_RESERVED_GDT 0
16 #define ENABLE_FEATURE_MKFS_EXT2_DIR_INDEX 1
17
18 // from e2fsprogs
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
24
25 // whiteout: for writable overlays
26 //#define LINUX_S_IFWHT                  0160000
27 //#define EXT2_FEATURE_INCOMPAT_WHITEOUT 0x0020
28
29 // storage helper
30 void BUG_unsupported_field_size(void);
31 #define STORE_LE(field, value) \
32 do { \
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) \
38                 field = (value); \
39         else \
40                 BUG_unsupported_field_size(); \
41 } while (0)
42
43 // All fields are little-endian
44 struct ext2_dir {
45         uint32_t inode1;
46         uint16_t rec_len1;
47         uint8_t  name_len1;
48         uint8_t  file_type1;
49         char     name1[4];
50         uint32_t inode2;
51         uint16_t rec_len2;
52         uint8_t  name_len2;
53         uint8_t  file_type2;
54         char     name2[4];
55         uint32_t inode3;
56         uint16_t rec_len3;
57         uint8_t  name_len3;
58         uint8_t  file_type3;
59         char     name3[12];
60 };
61
62 static unsigned int_log2(unsigned arg)
63 {
64         unsigned r = 0;
65         while ((arg >>= 1) != 0)
66                 r++;
67         return r;
68 }
69
70 // taken from mkfs_minix.c. libbb candidate?
71 static unsigned div_roundup(uint32_t size, uint32_t n)
72 {
73         return (size + n-1) / n;
74 }
75
76 static void allocate(uint8_t *bitmap, uint32_t blocksize, uint32_t start, uint32_t end)
77 {
78         uint32_t i;
79         memset(bitmap, 0, blocksize);
80         i = start/8;
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))));
84         i = end/8;
85         bitmap[blocksize - i - 1] = 0xFF << (8-(end&7));
86         memset(bitmap + blocksize - i, 0xFF, i); // N.B. no overflow here!
87 }
88
89 #if 0
90 // TODO: get rid of FPU
91 static bool is_power_of(uint32_t x, uint16_t n)
92 {
93 //      return (!(x % n) && is_power_of(x / n, n));
94         double z = logf(x)/logf(n);
95         return (z == (int)z);
96 }
97
98 static uint32_t has_super(uint32_t x)
99 {
100         return (0 == x || 1 == x || is_power_of(x, 3) || is_power_of(x, 5) || is_power_of(x, 7));
101 }
102
103 #else
104
105 static uint32_t has_super(uint32_t x)
106 {
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 */,
114         };
115         const uint32_t *sp = supers + ARRAY_SIZE(supers)-1;
116         while (1) {
117                 if (x == *sp)
118                         return 1;
119                 if (0 == *sp)
120                         return 0;
121                 sp--;
122         }
123 }
124 #endif
125
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]
134 */
135 // N.B. not commented below options are taken and silently ignored
136 enum {
137         OPT_c = 1 << 0,
138         OPT_l = 1 << 1,
139         OPT_b = 1 << 2,         // block size, in bytes
140         OPT_f = 1 << 3,
141         OPT_i = 1 << 4,         // bytes per inode
142         OPT_I = 1 << 5,
143         OPT_J = 1 << 6,
144         OPT_G = 1 << 7,
145         OPT_N = 1 << 8,
146         OPT_m = 1 << 9,         // percentage of blocks reserved for superuser
147         OPT_o = 1 << 10,
148         OPT_g = 1 << 11,
149         OPT_L = 1 << 12,        // label
150         OPT_M = 1 << 13,
151         OPT_O = 1 << 14,
152         OPT_r = 1 << 15,
153         OPT_E = 1 << 16,
154         OPT_T = 1 << 17,
155         OPT_U = 1 << 18,
156         OPT_j = 1 << 19,
157         OPT_n = 1 << 20,
158         OPT_q = 1 << 21,
159         OPT_v = 1 << 22,
160         OPT_F = 1 << 23,
161         OPT_S = 1 << 24,
162         //OPT_V = 1 << 25,      // -V version. bbox applets don't support that
163 };
164
165 #define fd 3    /* predefined output descriptor */
166
167 static void PUT(uint64_t off, void *buf, uint32_t size)
168 {
169         if (!(option_mask32 & OPT_n)) {
170                 xlseek(fd, off, SEEK_SET);
171                 xwrite(fd, buf, size);
172         }
173 }
174
175 int mkfs_ext2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
176 int mkfs_ext2_main(int argc UNUSED_PARAM, char **argv)
177 {
178         unsigned i, pos, n;
179         unsigned bs, blocksize;
180         unsigned nreserved = 5;
181         uint32_t nblocks;
182         uint32_t ngroups;
183         unsigned bytes_per_inode;
184         uint32_t nblocks_per_group;
185         uint32_t first_data_block;
186         uint32_t ninodes;
187         uint32_t ninodes_per_group;
188         uint32_t gdtsz, rgdtsz, itsz;
189         time_t timestamp;
190         unsigned opts;
191         const char *label;
192         struct stat st;
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;
197         uint8_t *buf;
198
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
205
206         // block size minimax, block size is a multiple of minimum
207         blocksize = bs;
208         if (blocksize < EXT2_MIN_BLOCK_SIZE
209          || blocksize > EXT2_MAX_BLOCK_SIZE
210          || (blocksize & (blocksize - 1)) // not power of 2
211         ) {
212                 bb_error_msg_and_die("-%c is bad", 'b');
213         }
214
215         // reserved blocks count
216         if (nreserved > 50)
217                 bb_error_msg_and_die("-%c is bad", 'm');
218
219         // check the device is a block device
220         xstat(argv[0], &st);
221         if (!S_ISBLK(st.st_mode) && !(opts & OPT_F))
222                 bb_error_msg_and_die("not a block device");
223
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");
229
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?
239
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;
255         sb->s_state = 1;
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)
263                 ;
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);
272 #endif
273         /*
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.
277          */
278         sb->s_max_mnt_count += sb->s_uuid[ARRAY_SIZE(sb->s_uuid)-1] % EXT2_DFL_MAX_MNT_COUNT;
279
280         // open the device, get number of blocks
281         xmove_fd(xopen3(argv[0], O_WRONLY | O_CREAT, 0666), fd);
282         if (argv[1]) {
283                 nblocks = xatou(argv[1]);
284         } else {
285                 nblocks = ((uoff_t)xlseek(fd, 0, SEEK_END)) / blocksize;
286         }
287         sb->s_blocks_count = nblocks;
288
289         // nblocks is the total number of blocks in the filesystem
290         if (nblocks < 8)
291                 bb_error_msg_and_die("nblocks");
292         // reserve blocks for superuser
293         sb->s_r_blocks_count = ((uint64_t) nblocks * nreserved) / 100;
294
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);
297         if (0 == ngroups)
298                 bb_error_msg_and_die("ngroups");
299         gdtsz = div_roundup(ngroups, EXT2_DESC_PER_BLOCK(sb));
300         /*
301          * From e2fsprogs: Calculate the number of GDT blocks to reserve for online
302          * filesystem growth.
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.
305          */
306         /* We set it at 1024x the current filesystem size, or
307          * the upper block count limit (2^32), whichever is lower.
308          */
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);
319 #else
320         rgdtsz = 0;
321 #endif
322
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;
330         }
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);
345         // total ninodes
346         ninodes = sb->s_inodes_count = ninodes_per_group * ngroups;
347
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;
350
351         // write the label, if any
352         if (opts & OPT_L)
353                 safe_strncpy((char *)sb->s_volume_name, label, sizeof(sb->s_volume_name));
354
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;
359                 i < ngroups;
360                 i++, pos += nblocks_per_group, n -= nblocks_per_group
361         ) {
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;
370                 if (0 == i) {
371                         overhead += 2;
372                         gd[i].bg_used_dirs_count = 2;
373                         gd[i].bg_free_inodes_count -= EXT2_GOOD_OLD_FIRST_INO;
374                 }
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;
379                 }
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;
382         }
383         STORE_LE(sb->s_free_blocks_count, sb->s_free_blocks_count);
384
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;
390                 uint32_t end;
391
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);
398                 }
399
400                 start = overhead + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
401                 if (i == 0)
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);
406                 // dump block bitmap
407                 PUT((pos + overhead) * blocksize, buf, blocksize);
408
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
413                 );
414                 // dump inode bitmap
415                 PUT((pos + overhead + 1) * blocksize, buf, blocksize);
416         }
417
418         // zero boot sectors
419         memset(buf, 0, blocksize);
420         PUT(0, buf, 1024); // N.B. 1024 <= blocksize
421         // zero inode tables
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);
425
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);
434
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));
439
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));
444
445         // dump directories
446         memset(buf, 0, blocksize);
447         dir = (struct ext2_dir *)buf;
448
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);
454         dir->name1[0] = '.';
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);
461
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);
471
472         // cleanup
473         if (ENABLE_FEATURE_CLEAN_UP) {
474                 free(buf);
475                 free(gd);
476                 free(sb);
477                 close(fd);
478         }
479
480         return EXIT_SUCCESS;
481 }