83e81054ba1e3b096e03bf6cf636cbdcdefaf720
[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         for (i = 0, n = 0; i < sizeof(sb->s_uuid); i++)
279                 n += sb->s_uuid[i];
280         sb->s_max_mnt_count += n % EXT2_DFL_MAX_MNT_COUNT;
281
282         // open the device, get number of blocks
283         xmove_fd(xopen3(argv[0], O_WRONLY | O_CREAT, 0666), fd);
284         if (argv[1]) {
285                 nblocks = xatou(argv[1]);
286         } else {
287                 nblocks = ((uoff_t)xlseek(fd, 0, SEEK_END)) / blocksize;
288                 xlseek(fd, 0, SEEK_SET);
289         }
290         sb->s_blocks_count = nblocks;
291
292         // nblocks is the total number of blocks in the filesystem
293         if (nblocks < 8)
294                 bb_error_msg_and_die("nblocks");
295         // reserve blocks for superuser
296         sb->s_r_blocks_count = ((uint64_t) nblocks * nreserved) / 100;
297
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);
300         if (0 == ngroups)
301                 bb_error_msg_and_die("ngroups");
302         gdtsz = div_roundup(ngroups, EXT2_DESC_PER_BLOCK(sb));
303         /*
304          * From e2fsprogs: Calculate the number of GDT blocks to reserve for online
305          * filesystem growth.
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.
308          */
309         /* We set it at 1024x the current filesystem size, or
310          * the upper block count limit (2^32), whichever is lower.
311          */
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);
322 #else
323         rgdtsz = 0;
324 #endif
325
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;
333         }
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);
348         // total ninodes
349         ninodes = sb->s_inodes_count = ninodes_per_group * ngroups;
350
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;
353
354         // write the label, if any
355         if (opts & OPT_L)
356                 safe_strncpy((char *)sb->s_volume_name, label, sizeof(sb->s_volume_name));
357
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;
362                 i < ngroups;
363                 i++, pos += nblocks_per_group, n -= nblocks_per_group
364         ) {
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;
373                 if (0 == i) {
374                         overhead += 2;
375                         gd[i].bg_used_dirs_count = 2;
376                         gd[i].bg_free_inodes_count -= EXT2_GOOD_OLD_FIRST_INO;
377                 }
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;
382                 }
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;
385         }
386         STORE_LE(sb->s_free_blocks_count, sb->s_free_blocks_count);
387
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;
393                 uint32_t end;
394
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);
401                 }
402
403                 start = overhead + 1/*bbmp*/ + 1/*ibmp*/ + itsz;
404                 if (i == 0)
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);
409                 // dump block bitmap
410                 PUT((pos + overhead) * blocksize, buf, blocksize);
411
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
416                 );
417                 // dump inode bitmap
418                 PUT((pos + overhead + 1) * blocksize, buf, blocksize);
419
420         }
421
422         // zero boot sectors
423         memset(buf, 0, blocksize);
424         PUT(0, buf, 1024); // N.B. 1024 <= blocksize
425         // zero inode tables
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);
429
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);
438
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));
443
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));
448
449         // dump directories
450         memset(buf, 0, blocksize);
451         dir = (struct ext2_dir *)buf;
452
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);
458         dir->name1[0] = '.';
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);
465
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);
475
476         // cleanup
477         if (ENABLE_FEATURE_CLEAN_UP) {
478                 free(buf);
479                 free(gd);
480                 free(sb);
481                 close(fd);
482         }
483
484         return EXIT_SUCCESS;
485 }