1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#define FOR_mke2fs
75#include "toys.h"
76
77GLOBALS(
78
79 long blocksize;
80 long bytes_per_inode;
81 long inodes;
82 long reserved_percent;
83 char *gendir;
84
85
86 struct dirtree *dt;
87 unsigned treeblocks;
88 unsigned treeinodes;
89
90 unsigned blocks;
91 unsigned freeblocks;
92 unsigned inodespg;
93 unsigned groups;
94 unsigned blockbits;
95
96
97 unsigned nextblock;
98 unsigned nextgroup;
99 int fsfd;
100)
101
102
103
104#define EXT2_SUPER_MAGIC 0xEF53
105
106struct ext2_superblock {
107 uint32_t inodes_count;
108 uint32_t blocks_count;
109 uint32_t r_blocks_count;
110 uint32_t free_blocks_count;
111 uint32_t free_inodes_count;
112 uint32_t first_data_block;
113 uint32_t log_block_size;
114 uint32_t log_frag_size;
115 uint32_t blocks_per_group;
116 uint32_t frags_per_group;
117 uint32_t inodes_per_group;
118 uint32_t mtime;
119 uint32_t wtime;
120 uint16_t mnt_count;
121 uint16_t max_mnt_count;
122 uint16_t magic;
123 uint16_t state;
124 uint16_t errors;
125 uint16_t minor_rev_level;
126 uint32_t lastcheck;
127 uint32_t checkinterval;
128 uint32_t creator_os;
129 uint32_t rev_level;
130 uint16_t def_resuid;
131 uint16_t def_resgid;
132 uint32_t first_ino;
133 uint16_t inode_size;
134 uint16_t block_group_nr;
135 uint32_t feature_compat;
136 uint32_t feature_incompat;
137 uint32_t feature_ro_compat;
138 char uuid[16];
139 char volume_name[16];
140 char last_mounted[64];
141 uint32_t alg_usage_bitmap;
142
143 uint8_t prealloc_blocks;
144 uint8_t prealloc_dir_blocks;
145 uint16_t padding1;
146
147 uint8_t journal_uuid[16];
148 uint32_t journal_inum;
149 uint32_t journal_dev;
150 uint32_t last_orphan;
151 uint32_t hash_seed[4];
152 uint8_t def_hash_version;
153 uint8_t padding2[3];
154 uint32_t default_mount_opts;
155 uint32_t first_meta_bg;
156 uint32_t mkfs_time;
157 uint32_t jnl_blocks[17];
158
159};
160
161struct ext2_group
162{
163 uint32_t block_bitmap;
164 uint32_t inode_bitmap;
165 uint32_t inode_table;
166 uint16_t free_blocks_count;
167 uint16_t free_inodes_count;
168 uint16_t used_dirs_count;
169 uint16_t reserved[7];
170};
171
172struct ext2_dentry {
173 uint32_t inode;
174 uint16_t rec_len;
175 uint8_t name_len;
176 uint8_t file_type;
177 char name[0];
178};
179
180struct ext2_inode {
181 uint16_t mode;
182 uint16_t uid;
183 uint32_t size;
184 uint32_t atime;
185 uint32_t ctime;
186 uint32_t mtime;
187 uint32_t dtime;
188 uint16_t gid;
189 uint16_t links_count;
190 uint32_t blocks;
191 uint32_t flags;
192 uint32_t reserved1;
193 uint32_t block[15];
194 uint32_t generation;
195 uint32_t file_acl;
196 uint32_t dir_acl;
197 uint32_t faddr;
198 uint8_t frag;
199 uint8_t fsize;
200 uint16_t pad1;
201 uint16_t uid_high;
202 uint16_t gid_high;
203 uint32_t reserved2;
204};
205
206#define EXT2_FEATURE_COMPAT_DIR_PREALLOC 0x0001
207#define EXT2_FEATURE_COMPAT_IMAGIC_INODES 0x0002
208#define EXT3_FEATURE_COMPAT_HAS_JOURNAL 0x0004
209#define EXT2_FEATURE_COMPAT_EXT_ATTR 0x0008
210#define EXT2_FEATURE_COMPAT_RESIZE_INO 0x0010
211#define EXT2_FEATURE_COMPAT_DIR_INDEX 0x0020
212
213#define EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER 0x0001
214#define EXT2_FEATURE_RO_COMPAT_LARGE_FILE 0x0002
215#define EXT2_FEATURE_RO_COMPAT_BTREE_DIR 0x0004
216
217#define EXT2_FEATURE_INCOMPAT_COMPRESSION 0x0001
218#define EXT2_FEATURE_INCOMPAT_FILETYPE 0x0002
219#define EXT3_FEATURE_INCOMPAT_RECOVER 0x0004
220#define EXT3_FEATURE_INCOMPAT_JOURNAL_DEV 0x0008
221#define EXT2_FEATURE_INCOMPAT_META_BG 0x0010
222
223#define EXT2_NAME_LEN 255
224
225
226
227
228enum {
229 EXT2_FT_UNKNOWN,
230 EXT2_FT_REG_FILE,
231 EXT2_FT_DIR,
232 EXT2_FT_CHRDEV,
233 EXT2_FT_BLKDEV,
234 EXT2_FT_FIFO,
235 EXT2_FT_SOCK,
236 EXT2_FT_SYMLINK,
237 EXT2_FT_MAX
238};
239
240#define INODES_RESERVED 10
241
242static uint32_t div_round_up(uint32_t a, uint32_t b)
243{
244 uint32_t c = a/b;
245
246 if (a%b) c++;
247 return c;
248}
249
250
251
252static uint32_t file_blocks_used(uint64_t size, uint32_t *blocklist)
253{
254 uint32_t dblocks = (uint32_t)((size+(TT.blocksize-1))/TT.blocksize);
255 uint32_t idx=TT.blocksize/4, iblocks=0, diblocks=0, tiblocks=0;
256
257
258
259 if (blocklist) {
260 int i;
261
262
263 for (i=0; i<13 && i<dblocks; i++) blocklist[i] = i;
264
265 if (dblocks > 13+idx) blocklist[13] = 13+idx;
266
267 idx = 13 + idx + (idx*idx);
268 if (dblocks > idx) blocklist[14] = idx;
269
270 return 0;
271 }
272
273
274
275 if (dblocks > 12) {
276 iblocks = ((dblocks-13)/idx)+1;
277 if (iblocks > 1) {
278 diblocks = ((iblocks-2)/idx)+1;
279 if (diblocks > 1)
280 tiblocks = ((diblocks-2)/idx)+1;
281 }
282 }
283
284 return dblocks + iblocks + diblocks + tiblocks;
285}
286
287
288static struct dirtree *treenext(struct dirtree *this)
289{
290 while (this && !this->next) this = this->parent;
291 if (this) this = this->next;
292
293 return this;
294}
295
296
297
298
299
300static long check_treesize(struct dirtree *that, off_t *size)
301{
302 long blocks;
303
304 while (that) {
305 *size += sizeof(struct ext2_dentry) + strlen(that->name);
306
307 if (that->child)
308 that->st.st_blocks = check_treesize(that->child, &that->st.st_size);
309 else if (S_ISREG(that->st.st_mode)) {
310 that->st.st_blocks = file_blocks_used(that->st.st_size, 0);
311 TT.treeblocks += that->st.st_blocks;
312 }
313 that = that->next;
314 }
315 TT.treeblocks += blocks = file_blocks_used(*size, 0);
316 TT.treeinodes++;
317
318 return blocks;
319}
320
321
322
323
324
325
326
327
328static void check_treelinks(struct dirtree *tree)
329{
330 struct dirtree *current=tree, *that;
331 long inode = INODES_RESERVED;
332
333 while (current) {
334 ++inode;
335
336 if (S_ISDIR(current->st.st_mode)) current->st.st_nlink = 2;
337 else {
338 dev_t new = current->st.st_dev;
339
340 if (!new) continue;
341
342
343 current->st.st_nlink = 0;
344 for (that = tree; that; that = treenext(that)) {
345 if (same_file(current, that)) {
346 current->st.st_nlink++;
347 current->st.st_ino = inode;
348 }
349 }
350 }
351 current->st.st_ino = inode;
352 current = treenext(current);
353 }
354}
355
356
357static uint32_t get_inodespg(uint32_t inodes)
358{
359 uint32_t temp;
360
361
362 temp = (inodes + TT.groups - 1) / TT.groups;
363 inodes = TT.blocksize/sizeof(struct ext2_inode);
364 return ((temp + inodes - 1)/inodes)*inodes;
365}
366
367
368
369static void init_superblock(struct ext2_superblock *sb)
370{
371 uint32_t temp;
372
373
374
375 for (temp = 0; temp < 4; temp++) if (TT.blocksize == 1024<<temp) break;
376 if (temp==4) error_exit("bad blocksize");
377 sb->log_block_size = sb->log_frag_size = SWAP_LE32(temp);
378
379
380
381 sb->blocks_count = SWAP_LE32(TT.blocks);
382 sb->free_blocks_count = SWAP_LE32(TT.freeblocks);
383 temp = (TT.blocks * (uint64_t)TT.reserved_percent) / 100;
384 sb->r_blocks_count = SWAP_LE32(temp);
385
386 sb->first_data_block = SWAP_LE32(TT.blocksize == 1024 ? 1 : 0);
387
388
389
390
391 sb->blocks_per_group = sb->frags_per_group = SWAP_LE32(TT.blockbits);
392
393
394 sb->inodes_per_group = SWAP_LE32(TT.inodespg);
395 sb->inodes_count = SWAP_LE32(TT.inodespg * TT.groups);
396
397
398 temp = TT.inodespg*TT.groups - INODES_RESERVED;
399 if (temp < TT.treeinodes) error_exit("Not enough inodes.\n");
400 sb->free_inodes_count = SWAP_LE32(temp - TT.treeinodes);
401
402
403 sb->max_mnt_count=0xFFFF;
404 sb->wtime = sb->lastcheck = sb->mkfs_time = SWAP_LE32(time(NULL));
405 sb->magic = SWAP_LE32(0xEF53);
406 sb->state = sb->errors = SWAP_LE16(1);
407
408 sb->rev_level = SWAP_LE32(1);
409 sb->first_ino = SWAP_LE32(INODES_RESERVED+1);
410 sb->inode_size = SWAP_LE16(sizeof(struct ext2_inode));
411 sb->feature_incompat = SWAP_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE);
412 sb->feature_ro_compat = SWAP_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER);
413
414 create_uuid(sb->uuid);
415
416
417
418
419
420}
421
422
423static int is_sb_group(uint32_t group)
424{
425 int i;
426
427
428 if(!group || group==1) return 1;
429 for (i=3; i<9; i+=2) {
430 int j = i;
431 while (j<group) j*=i;
432 if (j==group) return 1;
433 }
434 return 0;
435}
436
437
438
439static int group_superblock_overhead(uint32_t group)
440{
441 int used;
442
443 if (!is_sb_group(group)) return 0;
444
445
446 used = TT.groups * sizeof(struct ext2_group);
447 used += TT.blocksize - 1;
448 used /= TT.blocksize;
449
450 used++;
451
452 if (!group && TT.blocksize == 1024) used++;
453
454 return used;
455}
456
457
458static int group_overhead(uint32_t group)
459{
460
461
462 return group_superblock_overhead(group) + 2 + get_inodespg(TT.inodespg)
463 / (TT.blocksize/sizeof(struct ext2_inode));
464}
465
466
467static void bits_set(char *array, int start, int len)
468{
469 while(len) {
470 if ((start&7) || len<8) {
471 array[start/8]|=(1<<(start&7));
472 start++;
473 len--;
474 } else {
475 array[start/8]=255;
476 start+=8;
477 len-=8;
478 }
479 }
480}
481
482
483
484static void put_zeroes(int len)
485{
486 if(-1 == lseek(TT.fsfd, len, SEEK_SET)) {
487 memset(toybuf, 0, sizeof(toybuf));
488 while (len) {
489 int out = len > sizeof(toybuf) ? sizeof(toybuf) : len;
490 xwrite(TT.fsfd, toybuf, out);
491 len -= out;
492 }
493 }
494}
495
496
497static void fill_inode(struct ext2_inode *in, struct dirtree *that)
498{
499 uint32_t fbu[15];
500 int temp;
501
502 file_blocks_used(that->st.st_size, fbu);
503
504
505 if (that->st.st_size) {
506 int i, group = TT.nextblock/TT.blockbits;
507
508
509 for (i=0; i<15; i++) {
510
511 while (group >= TT.nextgroup)
512 TT.nextblock += group_overhead(TT.nextgroup++);
513 }
514 }
515
516 in->mode = SWAP_LE32(that->st.st_mode);
517
518 in->uid = SWAP_LE16(that->st.st_uid & 0xFFFF);
519 in->uid_high = SWAP_LE16(that->st.st_uid >> 16);
520 in->gid = SWAP_LE16(that->st.st_gid & 0xFFFF);
521 in->gid_high = SWAP_LE16(that->st.st_gid >> 16);
522 in->size = SWAP_LE32(that->st.st_size & 0xFFFFFFFF);
523
524
525
526 if (sizeof(that->st.st_size) > 4) temp = 32;
527 else temp = 0;
528 if (temp) in->dir_acl = SWAP_LE32(that->st.st_size >> temp);
529
530 in->atime = SWAP_LE32(that->st.st_atime);
531 in->ctime = SWAP_LE32(that->st.st_ctime);
532 in->mtime = SWAP_LE32(that->st.st_mtime);
533
534 in->links_count = SWAP_LE16(that->st.st_nlink);
535 in->blocks = SWAP_LE32(that->st.st_blocks);
536
537}
538
539
540
541
542
543void mke2fs_main(void)
544{
545 int i, temp;
546 off_t length;
547 uint32_t usedblocks, usedinodes, dtbblk;
548 struct dirtree *dti, *dtb;
549 struct ext2_superblock sb;
550
551
552
553 if (toys.optargs[1]) {
554 sscanf(toys.optargs[1], "%u", &TT.blocks);
555 temp = O_RDWR|O_CREAT;
556 } else temp = O_RDWR;
557 if (!TT.reserved_percent) TT.reserved_percent = 5;
558
559
560
561
562 TT.fsfd = xcreate(*toys.optargs, temp, 0777);
563
564
565
566
567 length = fdlength(TT.fsfd);
568 if (!TT.blocksize) TT.blocksize = (length && length < 1<<29) ? 1024 : 4096;
569 TT.blockbits = 8*TT.blocksize;
570 if (!TT.blocks) TT.blocks = length/TT.blocksize;
571
572
573
574 if (TT.gendir) {
575 strncpy(toybuf, TT.gendir, sizeof(toybuf));
576 dti = dirtree_read(toybuf, dirtree_notdotdot);
577 } else {
578 dti = xzalloc(sizeof(struct dirtree)+11);
579 strcpy(dti->name, "lost+found");
580 dti->st.st_mode = S_IFDIR|0755;
581 dti->st.st_ctime = dti->st.st_mtime = time(NULL);
582 }
583
584
585
586
587
588 dtb = xzalloc(sizeof(struct dirtree)+1);
589 dtb->st.st_mode = S_IFDIR|0755;
590 dtb->st.st_ctime = dtb->st.st_mtime = time(NULL);
591 dtb->child = dti;
592
593
594 length = check_treesize(dtb, &(dtb->st.st_size));
595 check_treelinks(dtb);
596
597
598
599 if (!TT.inodes) {
600 if (!TT.bytes_per_inode) TT.bytes_per_inode = 8192;
601 TT.inodes = (TT.blocks * (uint64_t)TT.blocksize) / TT.bytes_per_inode;
602 }
603
604
605
606
607 if (!TT.blocks) TT.groups = (TT.treeblocks/TT.blockbits)+1;
608 else TT.groups = div_round_up(TT.blocks, TT.blockbits);
609
610 for (;;) {
611 temp = TT.treeblocks;
612
613 for (i = 0; i<TT.groups; i++) temp += group_overhead(i);
614
615 if (TT.blocks) {
616 if (TT.blocks < temp) error_exit("Not enough space.\n");
617 break;
618 }
619 if (temp <= TT.groups * TT.blockbits) {
620 TT.blocks = temp;
621 break;
622 }
623 TT.groups++;
624 }
625 TT.freeblocks = TT.blocks - temp;
626
627
628
629 init_superblock(&sb);
630
631
632 put_zeroes(1024);
633
634
635 dtbblk = usedblocks = usedinodes = 0;
636 for (i=0; i<TT.groups; i++) {
637 struct ext2_inode *in = (struct ext2_inode *)toybuf;
638 uint32_t start, itable, used, end;
639 int j, slot;
640
641
642 end = TT.blockbits;
643 if ((i+1)*TT.blockbits > TT.blocks) end = TT.blocks & (TT.blockbits-1);
644
645
646 itable = (TT.inodespg*sizeof(struct ext2_inode))/TT.blocksize;
647
648
649 start = group_superblock_overhead(i);
650 if (start) {
651 struct ext2_group *bg = (struct ext2_group *)toybuf;
652 int treeblocks = TT.treeblocks, treeinodes = TT.treeinodes;
653
654 sb.block_group_nr = SWAP_LE16(i);
655
656
657 xwrite(TT.fsfd, &sb, sizeof(struct ext2_superblock));
658 temp = TT.blocksize - sizeof(struct ext2_superblock);
659 if (!i && TT.blocksize > 1024) temp -= 1024;
660 memset(toybuf, 0, TT.blocksize);
661 xwrite(TT.fsfd, toybuf, temp);
662
663
664 for(j=0; j<TT.groups; j++) {
665
666
667 used = group_superblock_overhead(j);
668
669
670 slot = j % (TT.blocksize/sizeof(struct ext2_group));
671 if (!slot) {
672 if (j) xwrite(TT.fsfd, bg, TT.blocksize);
673 memset(bg, 0, TT.blocksize);
674 }
675
676
677 temp = TT.inodespg;
678 if (!i) temp -= INODES_RESERVED;
679 if (temp > treeinodes) {
680 treeinodes -= temp;
681 temp = 0;
682 } else {
683 temp -= treeinodes;
684 treeinodes = 0;
685 }
686 bg[slot].free_inodes_count = SWAP_LE16(temp);
687
688
689 temp = TT.inodespg/(TT.blocksize/sizeof(struct ext2_inode)) + 2;
690 temp = end-used-temp;
691 if (temp > treeblocks) {
692 treeblocks -= temp;
693 temp = 0;
694 } else {
695 temp -= treeblocks;
696 treeblocks = 0;
697 }
698 bg[slot].free_blocks_count = SWAP_LE32(temp);
699
700
701 used += j*TT.blockbits;
702 bg[slot].block_bitmap = SWAP_LE32(used++);
703 bg[slot].inode_bitmap = SWAP_LE32(used++);
704 bg[slot].inode_table = SWAP_LE32(used);
705 bg[slot].used_dirs_count = 0;
706 }
707 xwrite(TT.fsfd, bg, TT.blocksize);
708 }
709
710
711
712
713
714 start += 2 + itable;
715 memset(toybuf, 0, TT.blocksize);
716 bits_set(toybuf, 0, start);
717 bits_set(toybuf, end, TT.blockbits-end);
718 temp = TT.treeblocks - usedblocks;
719 if (temp) {
720 if (end-start > temp) temp = end-start;
721 bits_set(toybuf, start, temp);
722 }
723 xwrite(TT.fsfd, toybuf, TT.blocksize);
724
725
726 memset(toybuf, 0, TT.blocksize);
727 j = 0;
728 if (!i) bits_set(toybuf, 0, j = INODES_RESERVED);
729 bits_set(toybuf, TT.inodespg, slot = TT.blockbits-TT.inodespg);
730 temp = TT.treeinodes - usedinodes;
731 if (temp) {
732 if (slot-j > temp) temp = slot-j;
733 bits_set(toybuf, j, temp);
734 }
735 xwrite(TT.fsfd, toybuf, TT.blocksize);
736
737
738 for (j = 0; j<TT.inodespg; j++) {
739 slot = j % (TT.blocksize/sizeof(struct ext2_inode));
740 if (!slot) {
741 if (j) xwrite(TT.fsfd, in, TT.blocksize);
742 memset(in, 0, TT.blocksize);
743 }
744 if (!i && j<INODES_RESERVED) {
745
746 if (j == 2) fill_inode(in+slot, dtb);
747 } else if (dti) {
748 fill_inode(in+slot, dti);
749 dti = treenext(dti);
750 }
751 }
752 xwrite(TT.fsfd, in, TT.blocksize);
753
754 while (dtb) {
755
756
757
758
759 put_zeroes(TT.blocksize);
760 start++;
761 if (start == end) break;
762 }
763
764 put_zeroes((end-start) * TT.blocksize);
765 }
766}
767