comparison toys/other/mke2fs.c @ 694:786841fdb1e0

Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style. The actual code should be the same afterward, this is just cosmetic refactoring.
author Rob Landley <rob@landley.net>
date Tue, 13 Nov 2012 17:14:08 -0600
parents 7e846e281e38
children
comparison
equal deleted inserted replaced
693:4a5a250e0633 694:786841fdb1e0
1 /* vi: set ts=4: 1 /* mke2fs.c - Create an ext2 filesystem image.
2 *
3 * mke2fs.c - Create an ext2 filesystem image.
4 * 2 *
5 * Copyright 2006, 2007 Rob Landley <rob@landley.net> 3 * Copyright 2006, 2007 Rob Landley <rob@landley.net>
6 4
7 // Still to go: "E:jJ:L:m:O:" 5 // Still to go: "E:jJ:L:m:O:"
8 USE_MKE2FS(NEWTOY(mke2fs, "<1>2g:Fnqm#N#i#b#", TOYFLAG_SBIN)) 6 USE_MKE2FS(NEWTOY(mke2fs, "<1>2g:Fnqm#N#i#b#", TOYFLAG_SBIN))
9 7
10 config MKE2FS 8 config MKE2FS
11 bool "mke2fs (unfinished and broken by dirtree changes)" 9 bool "mke2fs (unfinished and broken by dirtree changes)"
12 default n 10 default n
13 help 11 help
14 usage: mke2fs [-Fnq] [-b ###] [-N|i ###] [-m ###] device 12 usage: mke2fs [-Fnq] [-b ###] [-N|i ###] [-m ###] device
15 13
16 Create an ext2 filesystem on a block device or filesystem image. 14 Create an ext2 filesystem on a block device or filesystem image.
17 15
18 -F Force to run on a mounted device 16 -F Force to run on a mounted device
19 -n Don't write to device 17 -n Don't write to device
20 -q Quiet (no output) 18 -q Quiet (no output)
21 -b size Block size (1024, 2048, or 4096) 19 -b size Block size (1024, 2048, or 4096)
22 -N inodes Allocate this many inodes 20 -N inodes Allocate this many inodes
23 -i bytes Allocate one inode for every XXX bytes of device 21 -i bytes Allocate one inode for every XXX bytes of device
24 -m percent Reserve this percent of filesystem space for root user 22 -m percent Reserve this percent of filesystem space for root user
25 23
26 config MKE2FS_JOURNAL 24 config MKE2FS_JOURNAL
27 bool "Journaling support (ext3)" 25 bool "Journaling support (ext3)"
28 default n 26 default n
29 depends on MKE2FS 27 depends on MKE2FS
30 help 28 help
31 usage: [-j] [-J size=###,device=XXX] 29 usage: [-j] [-J size=###,device=XXX]
32 30
33 -j Create journal (ext3) 31 -j Create journal (ext3)
34 -J Journal options 32 -J Journal options
35 size: Number of blocks (1024-102400) 33 size: Number of blocks (1024-102400)
36 device: Specify an external journal 34 device: Specify an external journal
37 35
38 config MKE2FS_GEN 36 config MKE2FS_GEN
39 bool "Generate (gene2fs)" 37 bool "Generate (gene2fs)"
40 default n 38 default n
41 depends on MKE2FS 39 depends on MKE2FS
42 help 40 help
43 usage: gene2fs [options] device filename 41 usage: gene2fs [options] device filename
44 42
45 The [options] are the same as mke2fs. 43 The [options] are the same as mke2fs.
46 44
47 config MKE2FS_LABEL 45 config MKE2FS_LABEL
48 bool "Label support" 46 bool "Label support"
49 default n 47 default n
50 depends on MKE2FS 48 depends on MKE2FS
51 help 49 help
52 usage: mke2fs [-L label] [-M path] [-o string] 50 usage: mke2fs [-L label] [-M path] [-o string]
53 51
54 -L Volume label 52 -L Volume label
55 -M Path to mount point 53 -M Path to mount point
56 -o Created by 54 -o Created by
57 55
58 config MKE2FS_EXTENDED 56 config MKE2FS_EXTENDED
59 bool "Extended options" 57 bool "Extended options"
60 default n 58 default n
61 depends on MKE2FS 59 depends on MKE2FS
62 help 60 help
63 usage: mke2fs [-E stride=###] [-O option[,option]] 61 usage: mke2fs [-E stride=###] [-O option[,option]]
64 62
65 -E stride= Set RAID stripe size (in blocks) 63 -E stride= Set RAID stripe size (in blocks)
66 -O [opts] Specify fewer ext2 option flags (for old kernels) 64 -O [opts] Specify fewer ext2 option flags (for old kernels)
67 All of these are on by default (as appropriate) 65 All of these are on by default (as appropriate)
68 none Clear default options (all but journaling) 66 none Clear default options (all but journaling)
69 dir_index Use htree indexes for large directories 67 dir_index Use htree indexes for large directories
70 filetype Store file type info in directory entry 68 filetype Store file type info in directory entry
71 has_journal Set by -j 69 has_journal Set by -j
72 journal_dev Set by -J device=XXX 70 journal_dev Set by -J device=XXX
73 sparse_super Don't allocate huge numbers of redundant superblocks 71 sparse_super Don't allocate huge numbers of redundant superblocks
74 */ 72 */
75 73
76 #define FOR_mke2fs 74 #define FOR_mke2fs
77 #include "toys.h" 75 #include "toys.h"
78 76
79 GLOBALS( 77 GLOBALS(
80 // Command line arguments. 78 // Command line arguments.
81 long blocksize; 79 long blocksize;
82 long bytes_per_inode; 80 long bytes_per_inode;
83 long inodes; // Total inodes in filesystem. 81 long inodes; // Total inodes in filesystem.
84 long reserved_percent; // Integer precent of space to reserve for root. 82 long reserved_percent; // Integer precent of space to reserve for root.
85 char *gendir; // Where to read dirtree from. 83 char *gendir; // Where to read dirtree from.
86 84
87 // Internal data. 85 // Internal data.
88 struct dirtree *dt; // Tree of files to copy into the new filesystem. 86 struct dirtree *dt; // Tree of files to copy into the new filesystem.
89 unsigned treeblocks; // Blocks used by dt 87 unsigned treeblocks; // Blocks used by dt
90 unsigned treeinodes; // Inodes used by dt 88 unsigned treeinodes; // Inodes used by dt
91 89
92 unsigned blocks; // Total blocks in the filesystem. 90 unsigned blocks; // Total blocks in the filesystem.
93 unsigned freeblocks; // Free blocks in the filesystem. 91 unsigned freeblocks; // Free blocks in the filesystem.
94 unsigned inodespg; // Inodes per group 92 unsigned inodespg; // Inodes per group
95 unsigned groups; // Total number of block groups. 93 unsigned groups; // Total number of block groups.
96 unsigned blockbits; // Bits per block. (Also blocks per group.) 94 unsigned blockbits; // Bits per block. (Also blocks per group.)
97 95
98 // For gene2fs 96 // For gene2fs
99 unsigned nextblock; // Next data block to allocate 97 unsigned nextblock; // Next data block to allocate
100 unsigned nextgroup; // Next group we'll be allocating from 98 unsigned nextgroup; // Next group we'll be allocating from
101 int fsfd; // File descriptor of filesystem (to output to). 99 int fsfd; // File descriptor of filesystem (to output to).
102 100
103 struct ext2_superblock sb; 101 struct ext2_superblock sb;
104 ) 102 )
105 103
106 #define INODES_RESERVED 10 104 #define INODES_RESERVED 10
107 105
108 static uint32_t div_round_up(uint32_t a, uint32_t b) 106 static uint32_t div_round_up(uint32_t a, uint32_t b)
109 { 107 {
110 uint32_t c = a/b; 108 uint32_t c = a/b;
111 109
112 if (a%b) c++; 110 if (a%b) c++;
113 return c; 111 return c;
114 } 112 }
115 113
116 // Calculate data blocks plus index blocks needed to hold a file. 114 // Calculate data blocks plus index blocks needed to hold a file.
117 115
118 static uint32_t file_blocks_used(uint64_t size, uint32_t *blocklist) 116 static uint32_t file_blocks_used(uint64_t size, uint32_t *blocklist)
119 { 117 {
120 uint32_t dblocks = (uint32_t)((size+(TT.blocksize-1))/TT.blocksize); 118 uint32_t dblocks = (uint32_t)((size+(TT.blocksize-1))/TT.blocksize);
121 uint32_t idx=TT.blocksize/4, iblocks=0, diblocks=0, tiblocks=0; 119 uint32_t idx=TT.blocksize/4, iblocks=0, diblocks=0, tiblocks=0;
122 120
123 // Fill out index blocks in inode. 121 // Fill out index blocks in inode.
124 122
125 if (blocklist) { 123 if (blocklist) {
126 int i; 124 int i;
127 125
128 // Direct index blocks 126 // Direct index blocks
129 for (i=0; i<13 && i<dblocks; i++) blocklist[i] = i; 127 for (i=0; i<13 && i<dblocks; i++) blocklist[i] = i;
130 // Singly indirect index blocks 128 // Singly indirect index blocks
131 if (dblocks > 13+idx) blocklist[13] = 13+idx; 129 if (dblocks > 13+idx) blocklist[13] = 13+idx;
132 // Doubly indirect index blocks 130 // Doubly indirect index blocks
133 idx = 13 + idx + (idx*idx); 131 idx = 13 + idx + (idx*idx);
134 if (dblocks > idx) blocklist[14] = idx; 132 if (dblocks > idx) blocklist[14] = idx;
135 133
136 return 0; 134 return 0;
137 } 135 }
138 136
139 // Account for direct, singly, doubly, and triply indirect index blocks 137 // Account for direct, singly, doubly, and triply indirect index blocks
140 138
141 if (dblocks > 12) { 139 if (dblocks > 12) {
142 iblocks = ((dblocks-13)/idx)+1; 140 iblocks = ((dblocks-13)/idx)+1;
143 if (iblocks > 1) { 141 if (iblocks > 1) {
144 diblocks = ((iblocks-2)/idx)+1; 142 diblocks = ((iblocks-2)/idx)+1;
145 if (diblocks > 1) 143 if (diblocks > 1)
146 tiblocks = ((diblocks-2)/idx)+1; 144 tiblocks = ((diblocks-2)/idx)+1;
147 } 145 }
148 } 146 }
149 147
150 return dblocks + iblocks + diblocks + tiblocks; 148 return dblocks + iblocks + diblocks + tiblocks;
151 } 149 }
152 150
153 // Use the parent pointer to iterate through the tree non-recursively. 151 // Use the parent pointer to iterate through the tree non-recursively.
154 static struct dirtree *treenext(struct dirtree *this) 152 static struct dirtree *treenext(struct dirtree *this)
155 { 153 {
156 while (this && !this->next) this = this->parent; 154 while (this && !this->next) this = this->parent;
157 if (this) this = this->next; 155 if (this) this = this->next;
158 156
159 return this; 157 return this;
160 } 158 }
161 159
162 // Recursively calculate the number of blocks used by each inode in the tree. 160 // Recursively calculate the number of blocks used by each inode in the tree.
163 // Returns blocks used by this directory, assigns bytes used to *size. 161 // Returns blocks used by this directory, assigns bytes used to *size.
164 // Writes total block count to TT.treeblocks and inode count to TT.treeinodes. 162 // Writes total block count to TT.treeblocks and inode count to TT.treeinodes.
165 163
166 static long check_treesize(struct dirtree *that, off_t *size) 164 static long check_treesize(struct dirtree *that, off_t *size)
167 { 165 {
168 long blocks; 166 long blocks;
169 167
170 while (that) { 168 while (that) {
171 *size += sizeof(struct ext2_dentry) + strlen(that->name); 169 *size += sizeof(struct ext2_dentry) + strlen(that->name);
172 170
173 if (that->child) 171 if (that->child)
174 that->st.st_blocks = check_treesize(that->child, &that->st.st_size); 172 that->st.st_blocks = check_treesize(that->child, &that->st.st_size);
175 else if (S_ISREG(that->st.st_mode)) { 173 else if (S_ISREG(that->st.st_mode)) {
176 that->st.st_blocks = file_blocks_used(that->st.st_size, 0); 174 that->st.st_blocks = file_blocks_used(that->st.st_size, 0);
177 TT.treeblocks += that->st.st_blocks; 175 TT.treeblocks += that->st.st_blocks;
178 } 176 }
179 that = that->next; 177 that = that->next;
180 } 178 }
181 TT.treeblocks += blocks = file_blocks_used(*size, 0); 179 TT.treeblocks += blocks = file_blocks_used(*size, 0);
182 TT.treeinodes++; 180 TT.treeinodes++;
183 181
184 return blocks; 182 return blocks;
185 } 183 }
186 184
187 // Calculate inode numbers and link counts. 185 // Calculate inode numbers and link counts.
188 // 186 //
189 // To do this right I need to copy the tree and sort it, but here's a really 187 // To do this right I need to copy the tree and sort it, but here's a really
190 // ugly n^2 way of dealing with the problem that doesn't scale well to large 188 // ugly n^2 way of dealing with the problem that doesn't scale well to large
191 // numbers of files (> 100,000) but can be done in very little code. 189 // numbers of files (> 100,000) but can be done in very little code.
192 // This rewrites inode numbers to their final values, allocating depth first. 190 // This rewrites inode numbers to their final values, allocating depth first.
193 191
194 static void check_treelinks(struct dirtree *tree) 192 static void check_treelinks(struct dirtree *tree)
195 { 193 {
196 struct dirtree *current=tree, *that; 194 struct dirtree *current=tree, *that;
197 long inode = INODES_RESERVED; 195 long inode = INODES_RESERVED;
198 196
199 while (current) { 197 while (current) {
200 ++inode; 198 ++inode;
201 // Since we can't hardlink to directories, we know their link count. 199 // Since we can't hardlink to directories, we know their link count.
202 if (S_ISDIR(current->st.st_mode)) current->st.st_nlink = 2; 200 if (S_ISDIR(current->st.st_mode)) current->st.st_nlink = 2;
203 else { 201 else {
204 dev_t new = current->st.st_dev; 202 dev_t new = current->st.st_dev;
205 203
206 if (!new) continue; 204 if (!new) continue;
207 205
208 // Look for other copies of current node 206 // Look for other copies of current node
209 current->st.st_nlink = 0; 207 current->st.st_nlink = 0;
210 for (that = tree; that; that = treenext(that)) { 208 for (that = tree; that; that = treenext(that)) {
211 if (current->st.st_ino == that->st.st_ino && 209 if (current->st.st_ino == that->st.st_ino &&
212 current->st.st_dev == that->st.st_dev) 210 current->st.st_dev == that->st.st_dev)
213 { 211 {
214 current->st.st_nlink++; 212 current->st.st_nlink++;
215 current->st.st_ino = inode; 213 current->st.st_ino = inode;
216 } 214 }
217 } 215 }
218 } 216 }
219 current->st.st_ino = inode; 217 current->st.st_ino = inode;
220 current = treenext(current); 218 current = treenext(current);
221 } 219 }
222 } 220 }
223 221
224 // According to http://www.opengroup.org/onlinepubs/9629399/apdxa.htm 222 // According to http://www.opengroup.org/onlinepubs/9629399/apdxa.htm
225 // we should generate a uuid structure by reading a clock with 100 nanosecond 223 // we should generate a uuid structure by reading a clock with 100 nanosecond
226 // precision, normalizing it to the start of the gregorian calendar in 1582, 224 // precision, normalizing it to the start of the gregorian calendar in 1582,
229 // On the other hand, we have 128 bits to come up with a unique identifier, of 227 // On the other hand, we have 128 bits to come up with a unique identifier, of
230 // which 6 have a defined value. /dev/urandom it is. 228 // which 6 have a defined value. /dev/urandom it is.
231 229
232 static void create_uuid(char *uuid) 230 static void create_uuid(char *uuid)
233 { 231 {
234 // Read 128 random bits 232 // Read 128 random bits
235 int fd = xopen("/dev/urandom", O_RDONLY); 233 int fd = xopen("/dev/urandom", O_RDONLY);
236 xreadall(fd, uuid, 16); 234 xreadall(fd, uuid, 16);
237 close(fd); 235 close(fd);
238 236
239 // Claim to be a DCE format UUID. 237 // Claim to be a DCE format UUID.
240 uuid[6] = (uuid[6] & 0x0F) | 0x40; 238 uuid[6] = (uuid[6] & 0x0F) | 0x40;
241 uuid[8] = (uuid[8] & 0x3F) | 0x80; 239 uuid[8] = (uuid[8] & 0x3F) | 0x80;
242 240
243 // rfc2518 section 6.4.1 suggests if we're not using a macaddr, we should 241 // rfc2518 section 6.4.1 suggests if we're not using a macaddr, we should
244 // set bit 1 of the node ID, which is the mac multicast bit. This means we 242 // set bit 1 of the node ID, which is the mac multicast bit. This means we
245 // should never collide with anybody actually using a macaddr. 243 // should never collide with anybody actually using a macaddr.
246 uuid[11] = uuid[11] | 128; 244 uuid[11] = uuid[11] | 128;
247 } 245 }
248 246
249 // Calculate inodes per group from total inodes. 247 // Calculate inodes per group from total inodes.
250 static uint32_t get_inodespg(uint32_t inodes) 248 static uint32_t get_inodespg(uint32_t inodes)
251 { 249 {
252 uint32_t temp; 250 uint32_t temp;
253 251
254 // Round up to fill complete inode blocks. 252 // Round up to fill complete inode blocks.
255 temp = (inodes + TT.groups - 1) / TT.groups; 253 temp = (inodes + TT.groups - 1) / TT.groups;
256 inodes = TT.blocksize/sizeof(struct ext2_inode); 254 inodes = TT.blocksize/sizeof(struct ext2_inode);
257 return ((temp + inodes - 1)/inodes)*inodes; 255 return ((temp + inodes - 1)/inodes)*inodes;
258 } 256 }
259 257
260 // Fill out superblock and TT structures. 258 // Fill out superblock and TT structures.
261 259
262 static void init_superblock(struct ext2_superblock *sb) 260 static void init_superblock(struct ext2_superblock *sb)
263 { 261 {
264 uint32_t temp; 262 uint32_t temp;
265 263
266 // Set log_block_size and log_frag_size. 264 // Set log_block_size and log_frag_size.
267 265
268 for (temp = 0; temp < 4; temp++) if (TT.blocksize == 1024<<temp) break; 266 for (temp = 0; temp < 4; temp++) if (TT.blocksize == 1024<<temp) break;
269 if (temp==4) error_exit("bad blocksize"); 267 if (temp==4) error_exit("bad blocksize");
270 sb->log_block_size = sb->log_frag_size = SWAP_LE32(temp); 268 sb->log_block_size = sb->log_frag_size = SWAP_LE32(temp);
271 269
272 // Fill out blocks_count, r_blocks_count, first_data_block 270 // Fill out blocks_count, r_blocks_count, first_data_block
273 271
274 sb->blocks_count = SWAP_LE32(TT.blocks); 272 sb->blocks_count = SWAP_LE32(TT.blocks);
275 sb->free_blocks_count = SWAP_LE32(TT.freeblocks); 273 sb->free_blocks_count = SWAP_LE32(TT.freeblocks);
276 temp = (TT.blocks * (uint64_t)TT.reserved_percent) / 100; 274 temp = (TT.blocks * (uint64_t)TT.reserved_percent) / 100;
277 sb->r_blocks_count = SWAP_LE32(temp); 275 sb->r_blocks_count = SWAP_LE32(temp);
278 276
279 sb->first_data_block = SWAP_LE32(TT.blocksize == 1024 ? 1 : 0); 277 sb->first_data_block = SWAP_LE32(TT.blocksize == 1024 ? 1 : 0);
280 278
281 // Set blocks_per_group and frags_per_group, which is the size of an 279 // Set blocks_per_group and frags_per_group, which is the size of an
282 // allocation bitmap that fits in one block (I.E. how many bits per block)? 280 // allocation bitmap that fits in one block (I.E. how many bits per block)?
283 281
284 sb->blocks_per_group = sb->frags_per_group = SWAP_LE32(TT.blockbits); 282 sb->blocks_per_group = sb->frags_per_group = SWAP_LE32(TT.blockbits);
285 283
286 // Set inodes_per_group and total inodes_count 284 // Set inodes_per_group and total inodes_count
287 sb->inodes_per_group = SWAP_LE32(TT.inodespg); 285 sb->inodes_per_group = SWAP_LE32(TT.inodespg);
288 sb->inodes_count = SWAP_LE32(TT.inodespg * TT.groups); 286 sb->inodes_count = SWAP_LE32(TT.inodespg * TT.groups);
289 287
290 // Determine free inodes. 288 // Determine free inodes.
291 temp = TT.inodespg*TT.groups - INODES_RESERVED; 289 temp = TT.inodespg*TT.groups - INODES_RESERVED;
292 if (temp < TT.treeinodes) error_exit("Not enough inodes.\n"); 290 if (temp < TT.treeinodes) error_exit("Not enough inodes.\n");
293 sb->free_inodes_count = SWAP_LE32(temp - TT.treeinodes); 291 sb->free_inodes_count = SWAP_LE32(temp - TT.treeinodes);
294 292
295 // Fill out the rest of the superblock. 293 // Fill out the rest of the superblock.
296 sb->max_mnt_count=0xFFFF; 294 sb->max_mnt_count=0xFFFF;
297 sb->wtime = sb->lastcheck = sb->mkfs_time = SWAP_LE32(time(NULL)); 295 sb->wtime = sb->lastcheck = sb->mkfs_time = SWAP_LE32(time(NULL));
298 sb->magic = SWAP_LE32(0xEF53); 296 sb->magic = SWAP_LE32(0xEF53);
299 sb->state = sb->errors = SWAP_LE16(1); 297 sb->state = sb->errors = SWAP_LE16(1);
300 298
301 sb->rev_level = SWAP_LE32(1); 299 sb->rev_level = SWAP_LE32(1);
302 sb->first_ino = SWAP_LE32(INODES_RESERVED+1); 300 sb->first_ino = SWAP_LE32(INODES_RESERVED+1);
303 sb->inode_size = SWAP_LE16(sizeof(struct ext2_inode)); 301 sb->inode_size = SWAP_LE16(sizeof(struct ext2_inode));
304 sb->feature_incompat = SWAP_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE); 302 sb->feature_incompat = SWAP_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE);
305 sb->feature_ro_compat = SWAP_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER); 303 sb->feature_ro_compat = SWAP_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER);
306 304
307 create_uuid(sb->uuid); 305 create_uuid(sb->uuid);
308 306
309 // TODO If we're called as mke3fs or mkfs.ext3, do a journal. 307 // TODO If we're called as mke3fs or mkfs.ext3, do a journal.
310 308
311 //if (strchr(toys.which->name,'3')) 309 //if (strchr(toys.which->name,'3'))
312 // sb->feature_compat |= SWAP_LE32(EXT3_FEATURE_COMPAT_HAS_JOURNAL); 310 // sb->feature_compat |= SWAP_LE32(EXT3_FEATURE_COMPAT_HAS_JOURNAL);
313 } 311 }
314 312
315 // Does this group contain a superblock backup (and group descriptor table)? 313 // Does this group contain a superblock backup (and group descriptor table)?
316 static int is_sb_group(uint32_t group) 314 static int is_sb_group(uint32_t group)
317 { 315 {
318 int i; 316 int i;
319 317
320 // Superblock backups are on groups 0, 1, and powers of 3, 5, and 7. 318 // Superblock backups are on groups 0, 1, and powers of 3, 5, and 7.
321 if(!group || group==1) return 1; 319 if(!group || group==1) return 1;
322 for (i=3; i<9; i+=2) { 320 for (i=3; i<9; i+=2) {
323 int j = i; 321 int j = i;
324 while (j<group) j*=i; 322 while (j<group) j*=i;
325 if (j==group) return 1; 323 if (j==group) return 1;
326 } 324 }
327 return 0; 325 return 0;
328 } 326 }
329 327
330 328
331 // Number of blocks used in group by optional superblock/group list backup. 329 // Number of blocks used in group by optional superblock/group list backup.
332 static int group_superblock_overhead(uint32_t group) 330 static int group_superblock_overhead(uint32_t group)
333 { 331 {
334 int used; 332 int used;
335 333
336 if (!is_sb_group(group)) return 0; 334 if (!is_sb_group(group)) return 0;
337 335
338 // How many blocks does the group descriptor table take up? 336 // How many blocks does the group descriptor table take up?
339 used = TT.groups * sizeof(struct ext2_group); 337 used = TT.groups * sizeof(struct ext2_group);
340 used += TT.blocksize - 1; 338 used += TT.blocksize - 1;
341 used /= TT.blocksize; 339 used /= TT.blocksize;
342 // Plus the superblock itself. 340 // Plus the superblock itself.
343 used++; 341 used++;
344 // And a corner case. 342 // And a corner case.
345 if (!group && TT.blocksize == 1024) used++; 343 if (!group && TT.blocksize == 1024) used++;
346 344
347 return used; 345 return used;
348 } 346 }
349 347
350 // Number of blocks used in group to store superblock/group/inode list 348 // Number of blocks used in group to store superblock/group/inode list
351 static int group_overhead(uint32_t group) 349 static int group_overhead(uint32_t group)
352 { 350 {
353 // Return superblock backup overhead (if any), plus block/inode 351 // Return superblock backup overhead (if any), plus block/inode
354 // allocation bitmaps, plus inode tables. 352 // allocation bitmaps, plus inode tables.
355 return group_superblock_overhead(group) + 2 + get_inodespg(TT.inodespg) 353 return group_superblock_overhead(group) + 2 + get_inodespg(TT.inodespg)
356 / (TT.blocksize/sizeof(struct ext2_inode)); 354 / (TT.blocksize/sizeof(struct ext2_inode));
357 } 355 }
358 356
359 // In bitmap "array" set "len" bits starting at position "start" (from 0). 357 // In bitmap "array" set "len" bits starting at position "start" (from 0).
360 static void bits_set(char *array, int start, int len) 358 static void bits_set(char *array, int start, int len)
361 { 359 {
362 while(len) { 360 while(len) {
363 if ((start&7) || len<8) { 361 if ((start&7) || len<8) {
364 array[start/8]|=(1<<(start&7)); 362 array[start/8]|=(1<<(start&7));
365 start++; 363 start++;
366 len--; 364 len--;
367 } else { 365 } else {
368 array[start/8]=255; 366 array[start/8]=255;
369 start+=8; 367 start+=8;
370 len-=8; 368 len-=8;
371 } 369 }
372 } 370 }
373 } 371 }
374 372
375 // Seek past len bytes (to maintain sparse file), or write zeroes if output 373 // Seek past len bytes (to maintain sparse file), or write zeroes if output
376 // not seekable 374 // not seekable
377 static void put_zeroes(int len) 375 static void put_zeroes(int len)
378 { 376 {
379 if(-1 == lseek(TT.fsfd, len, SEEK_SET)) { 377 if(-1 == lseek(TT.fsfd, len, SEEK_SET)) {
380 memset(toybuf, 0, sizeof(toybuf)); 378 memset(toybuf, 0, sizeof(toybuf));
381 while (len) { 379 while (len) {
382 int out = len > sizeof(toybuf) ? sizeof(toybuf) : len; 380 int out = len > sizeof(toybuf) ? sizeof(toybuf) : len;
383 xwrite(TT.fsfd, toybuf, out); 381 xwrite(TT.fsfd, toybuf, out);
384 len -= out; 382 len -= out;
385 } 383 }
386 } 384 }
387 } 385 }
388 386
389 // Fill out an inode structure from struct stat info in dirtree. 387 // Fill out an inode structure from struct stat info in dirtree.
390 static void fill_inode(struct ext2_inode *in, struct dirtree *that) 388 static void fill_inode(struct ext2_inode *in, struct dirtree *that)
391 { 389 {
392 uint32_t fbu[15]; 390 uint32_t fbu[15];
393 int temp; 391 int temp;
394 392
395 file_blocks_used(that->st.st_size, fbu); 393 file_blocks_used(that->st.st_size, fbu);
396 394
397 // If that inode needs data blocks allocated to it. 395 // If that inode needs data blocks allocated to it.
398 if (that->st.st_size) { 396 if (that->st.st_size) {
399 int i, group = TT.nextblock/TT.blockbits; 397 int i, group = TT.nextblock/TT.blockbits;
400 398
401 // TODO: teach this about indirect blocks. 399 // TODO: teach this about indirect blocks.
402 for (i=0; i<15; i++) { 400 for (i=0; i<15; i++) {
403 // If we just jumped into a new group, skip group overhead blocks. 401 // If we just jumped into a new group, skip group overhead blocks.
404 while (group >= TT.nextgroup) 402 while (group >= TT.nextgroup)
405 TT.nextblock += group_overhead(TT.nextgroup++); 403 TT.nextblock += group_overhead(TT.nextgroup++);
406 } 404 }
407 } 405 }
408 // TODO : S_ISREG/DIR/CHR/BLK/FIFO/LNK/SOCK(m) 406 // TODO : S_ISREG/DIR/CHR/BLK/FIFO/LNK/SOCK(m)
409 in->mode = SWAP_LE32(that->st.st_mode); 407 in->mode = SWAP_LE32(that->st.st_mode);
410 408
411 in->uid = SWAP_LE16(that->st.st_uid & 0xFFFF); 409 in->uid = SWAP_LE16(that->st.st_uid & 0xFFFF);
412 in->uid_high = SWAP_LE16(that->st.st_uid >> 16); 410 in->uid_high = SWAP_LE16(that->st.st_uid >> 16);
413 in->gid = SWAP_LE16(that->st.st_gid & 0xFFFF); 411 in->gid = SWAP_LE16(that->st.st_gid & 0xFFFF);
414 in->gid_high = SWAP_LE16(that->st.st_gid >> 16); 412 in->gid_high = SWAP_LE16(that->st.st_gid >> 16);
415 in->size = SWAP_LE32(that->st.st_size & 0xFFFFFFFF); 413 in->size = SWAP_LE32(that->st.st_size & 0xFFFFFFFF);
416 414
417 // Contortions to make the compiler not generate a warning for x>>32 415 // Contortions to make the compiler not generate a warning for x>>32
418 // when x is 32 bits. The optimizer should clean this up. 416 // when x is 32 bits. The optimizer should clean this up.
419 if (sizeof(that->st.st_size) > 4) temp = 32; 417 if (sizeof(that->st.st_size) > 4) temp = 32;
420 else temp = 0; 418 else temp = 0;
421 if (temp) in->dir_acl = SWAP_LE32(that->st.st_size >> temp); 419 if (temp) in->dir_acl = SWAP_LE32(that->st.st_size >> temp);
422 420
423 in->atime = SWAP_LE32(that->st.st_atime); 421 in->atime = SWAP_LE32(that->st.st_atime);
424 in->ctime = SWAP_LE32(that->st.st_ctime); 422 in->ctime = SWAP_LE32(that->st.st_ctime);
425 in->mtime = SWAP_LE32(that->st.st_mtime); 423 in->mtime = SWAP_LE32(that->st.st_mtime);
426 424
427 in->links_count = SWAP_LE16(that->st.st_nlink); 425 in->links_count = SWAP_LE16(that->st.st_nlink);
428 in->blocks = SWAP_LE32(that->st.st_blocks); 426 in->blocks = SWAP_LE32(that->st.st_blocks);
429 // in->faddr 427 // in->faddr
430 } 428 }
431 429
432 // Works like an archiver. 430 // Works like an archiver.
433 // The first argument is the name of the file to create. If it already 431 // The first argument is the name of the file to create. If it already
434 // exists, that size will be used. 432 // exists, that size will be used.
435 433
436 void mke2fs_main(void) 434 void mke2fs_main(void)
437 { 435 {
438 int i, temp; 436 int i, temp;
439 off_t length; 437 off_t length;
440 uint32_t usedblocks, usedinodes, dtiblk, dtbblk; 438 uint32_t usedblocks, usedinodes, dtiblk, dtbblk;
441 struct dirtree *dti, *dtb; 439 struct dirtree *dti, *dtb;
442 440
443 // Handle command line arguments. 441 // Handle command line arguments.
444 442
445 if (toys.optargs[1]) { 443 if (toys.optargs[1]) {
446 sscanf(toys.optargs[1], "%u", &TT.blocks); 444 sscanf(toys.optargs[1], "%u", &TT.blocks);
447 temp = O_RDWR|O_CREAT; 445 temp = O_RDWR|O_CREAT;
448 } else temp = O_RDWR; 446 } else temp = O_RDWR;
449 if (!TT.reserved_percent) TT.reserved_percent = 5; 447 if (!TT.reserved_percent) TT.reserved_percent = 5;
450 448
451 // TODO: Check if filesystem is mounted here 449 // TODO: Check if filesystem is mounted here
452 450
453 // For mke?fs, open file. For gene?fs, create file. 451 // For mke?fs, open file. For gene?fs, create file.
454 TT.fsfd = xcreate(*toys.optargs, temp, 0777); 452 TT.fsfd = xcreate(*toys.optargs, temp, 0777);
455 453
456 // Determine appropriate block size and block count from file length. 454 // Determine appropriate block size and block count from file length.
457 // (If no length, default to 4k. They can override it on the cmdline.) 455 // (If no length, default to 4k. They can override it on the cmdline.)
458 456
459 length = fdlength(TT.fsfd); 457 length = fdlength(TT.fsfd);
460 if (!TT.blocksize) TT.blocksize = (length && length < 1<<29) ? 1024 : 4096; 458 if (!TT.blocksize) TT.blocksize = (length && length < 1<<29) ? 1024 : 4096;
461 TT.blockbits = 8*TT.blocksize; 459 TT.blockbits = 8*TT.blocksize;
462 if (!TT.blocks) TT.blocks = length/TT.blocksize; 460 if (!TT.blocks) TT.blocks = length/TT.blocksize;
463 461
464 // Collect gene2fs list or lost+found, calculate requirements. 462 // Collect gene2fs list or lost+found, calculate requirements.
465 463
466 if (TT.gendir) { 464 if (TT.gendir) {
467 strncpy(toybuf, TT.gendir, sizeof(toybuf)); 465 strncpy(toybuf, TT.gendir, sizeof(toybuf));
468 dti = dirtree_read(toybuf, NULL, NULL); 466 dti = dirtree_read(toybuf, NULL, NULL);
469 } else { 467 } else {
470 dti = xzalloc(sizeof(struct dirtree)+11); 468 dti = xzalloc(sizeof(struct dirtree)+11);
471 strcpy(dti->name, "lost+found"); 469 strcpy(dti->name, "lost+found");
472 dti->st.st_mode = S_IFDIR|0755; 470 dti->st.st_mode = S_IFDIR|0755;
473 dti->st.st_ctime = dti->st.st_mtime = time(NULL); 471 dti->st.st_ctime = dti->st.st_mtime = time(NULL);
474 } 472 }
475 473
476 // Add root directory inode. This is iterated through for when finding 474 // Add root directory inode. This is iterated through for when finding
477 // blocks, but not when finding inodes. The tree's parent pointers don't 475 // blocks, but not when finding inodes. The tree's parent pointers don't
478 // point back into this. 476 // point back into this.
479 477
480 dtb = xzalloc(sizeof(struct dirtree)+1); 478 dtb = xzalloc(sizeof(struct dirtree)+1);
481 dtb->st.st_mode = S_IFDIR|0755; 479 dtb->st.st_mode = S_IFDIR|0755;
482 dtb->st.st_ctime = dtb->st.st_mtime = time(NULL); 480 dtb->st.st_ctime = dtb->st.st_mtime = time(NULL);
483 dtb->child = dti; 481 dtb->child = dti;
484 482
485 // Figure out how much space is used by preset files 483 // Figure out how much space is used by preset files
486 length = check_treesize(dtb, &(dtb->st.st_size)); 484 length = check_treesize(dtb, &(dtb->st.st_size));
487 check_treelinks(dtb); 485 check_treelinks(dtb);
488 486
489 // Figure out how many total inodes we need. 487 // Figure out how many total inodes we need.
490 488
491 if (!TT.inodes) { 489 if (!TT.inodes) {
492 if (!TT.bytes_per_inode) TT.bytes_per_inode = 8192; 490 if (!TT.bytes_per_inode) TT.bytes_per_inode = 8192;
493 TT.inodes = (TT.blocks * (uint64_t)TT.blocksize) / TT.bytes_per_inode; 491 TT.inodes = (TT.blocks * (uint64_t)TT.blocksize) / TT.bytes_per_inode;
494 } 492 }
495 493
496 // If we're generating a filesystem and have no idea how many blocks it 494 // If we're generating a filesystem and have no idea how many blocks it
497 // needs, start with a minimal guess, find the overhead of that many 495 // needs, start with a minimal guess, find the overhead of that many
498 // groups, and loop until this is enough groups to store this many blocks. 496 // groups, and loop until this is enough groups to store this many blocks.
499 if (!TT.blocks) TT.groups = (TT.treeblocks/TT.blockbits)+1; 497 if (!TT.blocks) TT.groups = (TT.treeblocks/TT.blockbits)+1;
500 else TT.groups = div_round_up(TT.blocks, TT.blockbits); 498 else TT.groups = div_round_up(TT.blocks, TT.blockbits);
501 499
502 for (;;) { 500 for (;;) {
503 temp = TT.treeblocks; 501 temp = TT.treeblocks;
504 502
505 for (i = 0; i<TT.groups; i++) temp += group_overhead(i); 503 for (i = 0; i<TT.groups; i++) temp += group_overhead(i);
506 504
507 if (TT.blocks) { 505 if (TT.blocks) {
508 if (TT.blocks < temp) error_exit("Not enough space.\n"); 506 if (TT.blocks < temp) error_exit("Not enough space.\n");
509 break; 507 break;
510 } 508 }
511 if (temp <= TT.groups * TT.blockbits) { 509 if (temp <= TT.groups * TT.blockbits) {
512 TT.blocks = temp; 510 TT.blocks = temp;
513 break; 511 break;
514 } 512 }
515 TT.groups++; 513 TT.groups++;
516 } 514 }
517 TT.freeblocks = TT.blocks - temp; 515 TT.freeblocks = TT.blocks - temp;
518 516
519 // Now we know all the TT data, initialize superblock structure. 517 // Now we know all the TT data, initialize superblock structure.
520 518
521 init_superblock(&TT.sb); 519 init_superblock(&TT.sb);
522 520
523 // Start writing. Skip the first 1k to avoid the boot sector (if any). 521 // Start writing. Skip the first 1k to avoid the boot sector (if any).
524 put_zeroes(1024); 522 put_zeroes(1024);
525 523
526 // Loop through block groups, write out each one. 524 // Loop through block groups, write out each one.
527 dtiblk = dtbblk = usedblocks = usedinodes = 0; 525 dtiblk = dtbblk = usedblocks = usedinodes = 0;
528 for (i=0; i<TT.groups; i++) { 526 for (i=0; i<TT.groups; i++) {
529 struct ext2_inode *in = (struct ext2_inode *)toybuf; 527 struct ext2_inode *in = (struct ext2_inode *)toybuf;
530 uint32_t start, itable, used, end; 528 uint32_t start, itable, used, end;
531 int j, slot; 529 int j, slot;
532 530
533 // Where does this group end? 531 // Where does this group end?
534 end = TT.blockbits; 532 end = TT.blockbits;
535 if ((i+1)*TT.blockbits > TT.blocks) end = TT.blocks & (TT.blockbits-1); 533 if ((i+1)*TT.blockbits > TT.blocks) end = TT.blocks & (TT.blockbits-1);
536 534
537 // Blocks used by inode table 535 // Blocks used by inode table
538 itable = (TT.inodespg*sizeof(struct ext2_inode))/TT.blocksize; 536 itable = (TT.inodespg*sizeof(struct ext2_inode))/TT.blocksize;
539 537
540 // If a superblock goes here, write it out. 538 // If a superblock goes here, write it out.
541 start = group_superblock_overhead(i); 539 start = group_superblock_overhead(i);
542 if (start) { 540 if (start) {
543 struct ext2_group *bg = (struct ext2_group *)toybuf; 541 struct ext2_group *bg = (struct ext2_group *)toybuf;
544 int treeblocks = TT.treeblocks, treeinodes = TT.treeinodes; 542 int treeblocks = TT.treeblocks, treeinodes = TT.treeinodes;
545 543
546 TT.sb.block_group_nr = SWAP_LE16(i); 544 TT.sb.block_group_nr = SWAP_LE16(i);
547 545
548 // Write superblock and pad it up to block size 546 // Write superblock and pad it up to block size
549 xwrite(TT.fsfd, &TT.sb, sizeof(struct ext2_superblock)); 547 xwrite(TT.fsfd, &TT.sb, sizeof(struct ext2_superblock));
550 temp = TT.blocksize - sizeof(struct ext2_superblock); 548 temp = TT.blocksize - sizeof(struct ext2_superblock);
551 if (!i && TT.blocksize > 1024) temp -= 1024; 549 if (!i && TT.blocksize > 1024) temp -= 1024;
552 memset(toybuf, 0, TT.blocksize); 550 memset(toybuf, 0, TT.blocksize);
553 xwrite(TT.fsfd, toybuf, temp); 551 xwrite(TT.fsfd, toybuf, temp);
554 552
555 // Loop through groups to write group descriptor table. 553 // Loop through groups to write group descriptor table.
556 for(j=0; j<TT.groups; j++) { 554 for(j=0; j<TT.groups; j++) {
557 555
558 // Figure out what sector this group starts in. 556 // Figure out what sector this group starts in.
559 used = group_superblock_overhead(j); 557 used = group_superblock_overhead(j);
560 558
561 // Find next array slot in this block (flush block if full). 559 // Find next array slot in this block (flush block if full).
562 slot = j % (TT.blocksize/sizeof(struct ext2_group)); 560 slot = j % (TT.blocksize/sizeof(struct ext2_group));
563 if (!slot) { 561 if (!slot) {
564 if (j) xwrite(TT.fsfd, bg, TT.blocksize); 562 if (j) xwrite(TT.fsfd, bg, TT.blocksize);
565 memset(bg, 0, TT.blocksize); 563 memset(bg, 0, TT.blocksize);
566 } 564 }
567 565
568 // How many free inodes in this group? 566 // How many free inodes in this group?
569 temp = TT.inodespg; 567 temp = TT.inodespg;
570 if (!i) temp -= INODES_RESERVED; 568 if (!i) temp -= INODES_RESERVED;
571 if (temp > treeinodes) { 569 if (temp > treeinodes) {
572 treeinodes -= temp; 570 treeinodes -= temp;
573 temp = 0; 571 temp = 0;
574 } else { 572 } else {
575 temp -= treeinodes; 573 temp -= treeinodes;
576 treeinodes = 0; 574 treeinodes = 0;
577 } 575 }
578 bg[slot].free_inodes_count = SWAP_LE16(temp); 576 bg[slot].free_inodes_count = SWAP_LE16(temp);
579 577
580 // How many free blocks in this group? 578 // How many free blocks in this group?
581 temp = TT.inodespg/(TT.blocksize/sizeof(struct ext2_inode)) + 2; 579 temp = TT.inodespg/(TT.blocksize/sizeof(struct ext2_inode)) + 2;
582 temp = end-used-temp; 580 temp = end-used-temp;
583 if (temp > treeblocks) { 581 if (temp > treeblocks) {
584 treeblocks -= temp; 582 treeblocks -= temp;
585 temp = 0; 583 temp = 0;
586 } else { 584 } else {
587 temp -= treeblocks; 585 temp -= treeblocks;
588 treeblocks = 0; 586 treeblocks = 0;
589 } 587 }
590 bg[slot].free_blocks_count = SWAP_LE32(temp); 588 bg[slot].free_blocks_count = SWAP_LE32(temp);
591 589
592 // Fill out rest of group structure 590 // Fill out rest of group structure
593 used += j*TT.blockbits; 591 used += j*TT.blockbits;
594 bg[slot].block_bitmap = SWAP_LE32(used++); 592 bg[slot].block_bitmap = SWAP_LE32(used++);
595 bg[slot].inode_bitmap = SWAP_LE32(used++); 593 bg[slot].inode_bitmap = SWAP_LE32(used++);
596 bg[slot].inode_table = SWAP_LE32(used); 594 bg[slot].inode_table = SWAP_LE32(used);
597 bg[slot].used_dirs_count = 0; // (TODO) 595 bg[slot].used_dirs_count = 0; // (TODO)
598 } 596 }
599 xwrite(TT.fsfd, bg, TT.blocksize); 597 xwrite(TT.fsfd, bg, TT.blocksize);
600 } 598 }
601 599
602 // Now write out stuff that every block group has. 600 // Now write out stuff that every block group has.
603 601
604 // Write block usage bitmap 602 // Write block usage bitmap
605 603
606 start += 2 + itable; 604 start += 2 + itable;
607 memset(toybuf, 0, TT.blocksize); 605 memset(toybuf, 0, TT.blocksize);
608 bits_set(toybuf, 0, start); 606 bits_set(toybuf, 0, start);
609 bits_set(toybuf, end, TT.blockbits-end); 607 bits_set(toybuf, end, TT.blockbits-end);
610 temp = TT.treeblocks - usedblocks; 608 temp = TT.treeblocks - usedblocks;
611 if (temp) { 609 if (temp) {
612 if (end-start > temp) temp = end-start; 610 if (end-start > temp) temp = end-start;
613 bits_set(toybuf, start, temp); 611 bits_set(toybuf, start, temp);
614 } 612 }
615 xwrite(TT.fsfd, toybuf, TT.blocksize); 613 xwrite(TT.fsfd, toybuf, TT.blocksize);
616 614
617 // Write inode bitmap 615 // Write inode bitmap
618 memset(toybuf, 0, TT.blocksize); 616 memset(toybuf, 0, TT.blocksize);
619 j = 0; 617 j = 0;
620 if (!i) bits_set(toybuf, 0, j = INODES_RESERVED); 618 if (!i) bits_set(toybuf, 0, j = INODES_RESERVED);
621 bits_set(toybuf, TT.inodespg, slot = TT.blockbits-TT.inodespg); 619 bits_set(toybuf, TT.inodespg, slot = TT.blockbits-TT.inodespg);
622 temp = TT.treeinodes - usedinodes; 620 temp = TT.treeinodes - usedinodes;
623 if (temp) { 621 if (temp) {
624 if (slot-j > temp) temp = slot-j; 622 if (slot-j > temp) temp = slot-j;
625 bits_set(toybuf, j, temp); 623 bits_set(toybuf, j, temp);
626 } 624 }
627 xwrite(TT.fsfd, toybuf, TT.blocksize); 625 xwrite(TT.fsfd, toybuf, TT.blocksize);
628 626
629 // Write inode table for this group (TODO) 627 // Write inode table for this group (TODO)
630 for (j = 0; j<TT.inodespg; j++) { 628 for (j = 0; j<TT.inodespg; j++) {
631 slot = j % (TT.blocksize/sizeof(struct ext2_inode)); 629 slot = j % (TT.blocksize/sizeof(struct ext2_inode));
632 if (!slot) { 630 if (!slot) {
633 if (j) xwrite(TT.fsfd, in, TT.blocksize); 631 if (j) xwrite(TT.fsfd, in, TT.blocksize);
634 memset(in, 0, TT.blocksize); 632 memset(in, 0, TT.blocksize);
635 } 633 }
636 if (!i && j<INODES_RESERVED) { 634 if (!i && j<INODES_RESERVED) {
637 // Write root inode 635 // Write root inode
638 if (j == 2) fill_inode(in+slot, dtb); 636 if (j == 2) fill_inode(in+slot, dtb);
639 } else if (dti) { 637 } else if (dti) {
640 fill_inode(in+slot, dti); 638 fill_inode(in+slot, dti);
641 dti = treenext(dti); 639 dti = treenext(dti);
642 } 640 }
643 } 641 }
644 xwrite(TT.fsfd, in, TT.blocksize); 642 xwrite(TT.fsfd, in, TT.blocksize);
645 643
646 while (dtb) { 644 while (dtb) {
647 // TODO write index data block 645 // TODO write index data block
648 // TODO write root directory data block 646 // TODO write root directory data block
649 // TODO write directory data block 647 // TODO write directory data block
650 // TODO write file data block 648 // TODO write file data block
651 put_zeroes(TT.blocksize); 649 put_zeroes(TT.blocksize);
652 start++; 650 start++;
653 if (start == end) break; 651 if (start == end) break;
654 } 652 }
655 // Write data blocks (TODO) 653 // Write data blocks (TODO)
656 put_zeroes((end-start) * TT.blocksize); 654 put_zeroes((end-start) * TT.blocksize);
657 } 655 }
658 } 656 }