e4c3e171e76c90d2a11f0c5464d8b767989fedd4
[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 inline int int_log2(int arg)
63 {
64         int r = 0;
65         while ((arg >>= 1) != 0)
66                 r++;
67         return r;
68 }
69
70 // taken from mkfs_minix.c. libbb candidate?
71 static ALWAYS_INLINE 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         unsigned i;
116         for (i = ARRAY_SIZE(supers); --i >= 0;)
117                 if (x == supers[i])
118                         return 1;
119         return 0;
120 }
121 #endif
122
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]
131 */
132 // N.B. not commented below options are taken and silently ignored
133 enum {
134         OPT_c = 1 << 0,
135         OPT_l = 1 << 1,
136         OPT_b = 1 << 2,         // block size, in bytes
137         OPT_f = 1 << 3,
138         OPT_i = 1 << 4,         // bytes per inode
139         OPT_I = 1 << 5,
140         OPT_J = 1 << 6,
141         OPT_G = 1 << 7,
142         OPT_N = 1 << 8,
143         OPT_m = 1 << 9,         // percentage of blocks reserved for superuser
144         OPT_o = 1 << 10,
145         OPT_g = 1 << 11,
146         OPT_L = 1 << 12,        // label
147         OPT_M = 1 << 13,
148         OPT_O = 1 << 14,
149         OPT_r = 1 << 15,
150         OPT_E = 1 << 16,
151         OPT_T = 1 << 17,
152         OPT_U = 1 << 18,
153         OPT_j = 1 << 19,
154         OPT_n = 1 << 20,
155         OPT_q = 1 << 21,
156         OPT_v = 1 << 22,
157         OPT_F = 1 << 23,
158         OPT_S = 1 << 24,
159         //OPT_V = 1 << 25,      // -V version. bbox applets don't support that
160 };
161
162 #define fd 3    /* predefined output descriptor */
163
164 static void PUT(uint64_t off, void *buf, uint32_t size)
165 {
166         if (!(option_mask32 & OPT_n)) {
167                 xlseek(fd, off, SEEK_SET);
168                 xwrite(fd, buf, size);
169         }
170 }
171
172 int mkfs_ext2_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
173 int mkfs_ext2_main(int argc UNUSED_PARAM, char **argv)
174 {
175         unsigned i, pos, n;
176         unsigned bs, blocksize;
177         unsigned nreserved = 5;
178         uint32_t nblocks;
179         uint32_t ngroups;
180         unsigned bytes_per_inode;
181         uint32_t nblocks_per_group;
182         uint32_t first_data_block;
183         uint32_t ninodes;
184         uint32_t ninodes_per_group;
185         uint32_t gdtsz, rgdtsz, itsz;
186         time_t timestamp;
187         unsigned opts;
188         const char *label;
189         struct stat st;
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;
194         uint8_t *buf;
195
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
202
203         // block size minimax, block size is a multiple of minimum
204         blocksize = bs;
205         if (blocksize < EXT2_MIN_BLOCK_SIZE
206          || blocksize > EXT2_MAX_BLOCK_SIZE
207          || (blocksize & (blocksize - 1)) // not power of 2
208         ) {
209                 bb_error_msg_and_die("-%c is bad", 'b');
210         }
211
212         // reserved blocks count
213         if (nreserved > 50)
214                 bb_error_msg_and_die("-%c is bad", 'm');
215
216         // check the device is a block device
217         xstat(argv[0], &st);
218         if (!S_ISBLK(st.st_mode) && !(opts & OPT_F))
219                 bb_error_msg_and_die("not a block device");
220
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");
226
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?
236
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;
252         sb->s_state = 1;
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)
260                 ;
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);
269 #endif
270         /*
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.
274          */
275         for (i = 0, n = 0; i < sizeof(sb->s_uuid); i++)
276                 n += sb->s_uuid[i];
277         sb->s_max_mnt_count += n % EXT2_DFL_MAX_MNT_COUNT;
278
279         // open the device, get number of blocks
280         xmove_fd(xopen3(argv[0], O_WRONLY | O_CREAT, 0666), fd);
281         if (argv[1]) {
282                 nblocks = xatou(argv[1]);
283         } else {
284                 nblocks = ((uoff_t)xlseek(fd, 0, SEEK_END)) / blocksize;
285                 xlseek(fd, 0, SEEK_SET);
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
419         // zero boot sectors
420         memset(buf, 0, blocksize);
421         PUT(0, buf, 1024); // N.B. 1024 <= blocksize
422         // zero inode tables
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);
426
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);
435
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));
440
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));
445
446         // dump directories
447         memset(buf, 0, blocksize);
448         dir = (struct ext2_dir *)buf;
449
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);
455         dir->name1[0] = '.';
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);
462
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);
472
473         // cleanup
474         if (ENABLE_FEATURE_CLEAN_UP) {
475                 free(buf);
476                 free(gd);
477                 free(sb);
478                 close(fd);
479         }
480
481         return EXIT_SUCCESS;
482 }