3 # Copyright (c) 2011 Martin Sucha
6 # Redistribution and use in source and binary forms, with or without
7 # modification, are permitted provided that the following conditions
10 # - Redistributions of source code must retain the above copyright
11 # notice, this list of conditions and the following disclaimer.
12 # - Redistributions in binary form must reproduce the above copyright
13 # notice, this list of conditions and the following disclaimer in the
14 # documentation and/or other materials provided with the distribution.
15 # - The name of the author may not be used to endorse or promote products
16 # derived from this software without specific prior written permission.
18 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 STRUCT_DIR_ENTRY_HEAD
= """little:
45 uint32_t inode /* inode number */
46 uint16_t skip /* byte offset to the next record */
47 uint8_t name_length /* file attributes */
48 uint8_t inode_type /* type of the referenced inode */
51 STRUCT_SUPERBLOCK
= """little:
52 uint32_t total_inode_count /* Total number of inodes */
53 uint32_t total_block_count /* Total number of blocks */
54 uint32_t reserved_block_count /* Total number of reserved blocks */
55 uint32_t free_block_count /* Total number of free blocks */
56 uint32_t free_inode_count /* Total number of free inodes */
57 uint32_t first_block /* Block containing the superblock */
58 uint32_t block_size_log2 /* log_2(block_size) */
59 int32_t fragment_size_log2 /* log_2(fragment size) */
60 uint32_t blocks_per_group /* Number of blocks in one block group */
61 uint32_t fragments_per_group /* Number of fragments per block group */
62 uint32_t inodes_per_group /* Number of inodes per block group */
63 uint32_t mount_time /* Time when the filesystem was last mounted */
64 uint32_t write_time /* Time when the filesystem was last written */
65 uint16_t mount_count /* Mount count since last full filesystem check */
66 uint16_t max_mount_count /* Number of mounts after which the fs must be checked */
67 uint16_t magic /* Magic value */
68 uint16_t state /* State (mounted/unmounted) */
69 uint16_t error_behavior /* What to do when errors are encountered */
70 uint16_t rev_minor /* Minor revision level */
71 uint32_t last_check_time /* Unix time of last fs check */
72 uint32_t max_check_interval /* Max unix time interval between checks */
73 uint32_t os /* OS that created the filesystem */
74 uint32_t rev_major /* Major revision level */
75 padding[4] /* default reserved uid and gid */
77 /* Following is for ext2 revision 1 only */
80 uint16_t block_group_number /* Block group where this SB is stored */
81 uint32_t features_compatible
82 uint32_t features_incompatible
83 uint32_t features_read_only
88 STRUCT_BLOCK_GROUP_DESCRIPTOR
= """little:
89 uint32_t block_bitmap_block /* Block ID for block bitmap */
90 uint32_t inode_bitmap_block /* Block ID for inode bitmap */
91 uint32_t inode_table_first_block /* Block ID of first block of inode table */
92 uint16_t free_block_count /* Count of free blocks */
93 uint16_t free_inode_count /* Count of free inodes */
94 uint16_t directory_inode_count /* Number of inodes allocated to directories */
97 STRUCT_INODE
= """little:
102 uint32_t creation_time
103 uint32_t modification_time
104 uint32_t deletion_time
106 uint16_t usage_count /* Hard link count, when 0 the inode is to be freed */
107 uint32_t reserved_512_blocks /* Size of this inode in 512-byte blocks */
110 uint32_t direct_blocks[12] /* Direct block ids stored in this inode */
111 uint32_t indirect_blocks[3]
114 uint32_t size_high /* For regular files in version >= 1, dir_acl if dir */
116 uint16_t mode_high /* Hurd only */
117 uint16_t user_id_high /* Linux/Hurd only */
118 uint16_t group_id_high /* Linux/Hurd only */
121 # The following is here to handle byte-order conversion in indirect block lookups
122 STRUCT_BLOCK_REFERENCE
= """little:
123 uint32_t block_id /* Referenced block ID */
127 def __init__(self
, filename
, block_groups
, blocks_per_group
, inodes_per_group
, block_size
, inode_size
, reserved_inode_count
):
128 "Initialize the filesystem writer"
130 outf
= open(filename
, "w+b")
131 # Set the correct size of the image, so that we can read arbitrary position
132 outf
.truncate(block_size
* blocks_per_group
* block_groups
)
134 self
.uuid
= uuid
.uuid4()
135 self
.block_size
= block_size
136 self
.inode_size
= inode_size
137 self
.block_groups
= block_groups
138 self
.blocks_per_group
= blocks_per_group
139 self
.inodes_per_group
= inodes_per_group
140 self
.reserved_inode_count
= reserved_inode_count
141 self
.gdt_blocks
= count_up(block_groups
* GDE_SIZE
, block_size
)
142 self
.inode_table_blocks_per_group
= (inodes_per_group
* inode_size
) // block_size
143 self
.inode_bitmap_blocks_per_group
= count_up(inodes_per_group
// 8, block_size
)
144 self
.block_bitmap_blocks_per_group
= count_up(blocks_per_group
// 8, block_size
)
145 self
.total_block_count
= self
.blocks_per_group
* self
.block_groups
146 self
.total_inode_count
= self
.inodes_per_group
* self
.block_groups
147 self
.inode_table_blocks
= count_up(self
.total_inode_count
* inode_size
, block_size
)
149 self
.superblock_at_block
= 2047 // block_size
150 self
.block_ids_per_block
= self
.block_size
// 4
151 self
.indirect_limits
= [12, None, None, None]
152 self
.indirect_blocks_per_level
= [1, None, None, None]
154 self
.indirect_blocks_per_level
[i
] = self
.indirect_blocks_per_level
[i
-1] * self
.block_ids_per_block
155 self
.indirect_limits
[i
] = self
.indirect_limits
[i
-1] + self
.indirect_blocks_per_level
[i
]
156 self
.block_allocator
= Allocator(0, self
.total_block_count
)
157 self
.inode_allocator
= Allocator(1, self
.total_inode_count
)
159 # Set the callbacks after GDT has been initialized
160 self
.block_allocator
.mark_cb
= self
.mark_block_cb
161 self
.inode_allocator
.mark_cb
= self
.mark_inode_cb
162 self
.block_allocator
.mark_used_all(range(self
.superblock_at_block
))
163 self
.inode_allocator
.mark_used_all(range(1, self
.reserved_inode_count
+ 1))
164 self
.root_inode
= Inode(self
, 2, Inode
.TYPE_DIR
)
165 self
.gdt
[0].directory_inode_count
+= 1
166 self
.lost_plus_found
= Inode(self
, self
.inode_allocator
.alloc(directory
=True), Inode
.TYPE_DIR
)
167 lpf_dir
= DirWriter(self
.lost_plus_found
)
168 lpf_dir
.add(self
.lost_plus_found
.as_dirent('.'))
169 lpf_dir
.add(self
.root_inode
.as_dirent('..'))
173 "Initialize block group descriptor table"
175 self
.superblock_positions
= []
177 consumed_blocks_per_group
= (1 + self
.gdt_blocks
+
178 self
.inode_bitmap_blocks_per_group
+
179 self
.block_bitmap_blocks_per_group
+
180 self
.inode_table_blocks_per_group
)
181 initial_free_blocks
= self
.blocks_per_group
- consumed_blocks_per_group
182 for bg
in range(self
.block_groups
):
183 base
= bg
* self
.blocks_per_group
185 base
= self
.superblock_at_block
186 self
.superblock_positions
.append(1024)
188 self
.superblock_positions
.append(base
* self
.block_size
)
189 self
.block_allocator
.mark_used_all(range(base
, base
+consumed_blocks_per_group
))
190 pos
= base
+ 1 + self
.gdt_blocks
191 gde
= xstruct
.create(STRUCT_BLOCK_GROUP_DESCRIPTOR
)
192 gde
.block_bitmap_block
= pos
193 pos
+= self
.block_bitmap_blocks_per_group
194 gde
.inode_bitmap_block
= pos
195 pos
+= self
.inode_bitmap_blocks_per_group
196 gde
.inode_table_first_block
= pos
197 gde
.free_block_count
= initial_free_blocks
198 gde
.free_inode_count
= self
.inodes_per_group
199 gde
.directory_inode_count
= 0
202 def mark_block_cb(self
, block
):
203 "Called after a block has been allocated"
205 self
.gdt
[block
// self
.blocks_per_group
].free_block_count
-= 1
207 def mark_inode_cb(self
, index
, directory
=False):
208 "Called after an inode has been allocated"
211 gde
= self
.gdt
[index
// self
.inodes_per_group
]
212 gde
.free_inode_count
-= 1
214 gde
.directory_inode_count
+= 1
216 def seek_to_block(self
, block
, offset
=0):
217 "Seek to offset bytes after the start of the given block"
219 if offset
< 0 or offset
> self
.block_size
:
220 raise Exception("Invalid in-block offset")
221 self
.outf
.seek(block
* self
.block_size
+ offset
)
223 def seek_to_inode(self
, index
):
224 "Seek to the start of the inode structure for the inode number index"
228 raise Exception("Invalid inode number")
229 gde
= self
.gdt
[index
// self
.inodes_per_group
]
230 base_block
= gde
.inode_table_first_block
231 offset
= (index
% self
.inodes_per_group
) * self
.inode_size
232 block
= base_block
+ (offset
// self
.block_size
)
233 self
.seek_to_block(block
, offset
% self
.block_size
)
235 def subtree_add(self
, inode
, parent_inode
, dirpath
, is_root
=False):
236 "Recursively add files to the filesystem"
238 dir_writer
= DirWriter(inode
)
239 dir_writer
.add(inode
.as_dirent('.'))
240 dir_writer
.add(parent_inode
.as_dirent('..'))
243 dir_writer
.add(self
.lost_plus_found
.as_dirent('lost+found'))
245 for item
in listdir_items(dirpath
):
246 newidx
= self
.inode_allocator
.alloc(directory
= item
.is_dir
)
248 child_inode
= Inode(self
, newidx
, Inode
.TYPE_FILE
)
249 for data
in chunks(item
, self
.block_size
):
250 child_inode
.write(data
)
252 child_inode
= Inode(self
, newidx
, Inode
.TYPE_DIR
)
253 self
.subtree_add(child_inode
, inode
, item
.path
)
255 dir_writer
.add(child_inode
.as_dirent(item
.name
))
256 self
.write_inode(child_inode
)
260 def write_inode(self
, inode
):
261 "Write inode information into the inode table"
263 self
.seek_to_inode(inode
.index
)
264 self
.outf
.write(inode
.pack())
267 "Write group descriptor table at the current file position"
270 data
= bytes(gde
.pack())
271 self
.outf
.write(data
)
272 self
.outf
.seek(GDE_SIZE
-len(data
), os
.SEEK_CUR
)
274 def write_superblock(self
, block_group
):
275 "Write superblock at the current position"
277 sb
= xstruct
.create(STRUCT_SUPERBLOCK
)
278 sb
.total_inode_count
= self
.total_inode_count
279 sb
.total_block_count
= self
.total_block_count
280 sb
.reserved_block_count
= 0
281 sb
.free_block_count
= self
.block_allocator
.free
282 sb
.free_inode_count
= self
.inode_allocator
.free
283 sb
.first_block
= self
.superblock_at_block
284 sb
.block_size_log2
= num_of_trailing_bin_zeros(self
.block_size
) - 10
285 sb
.fragment_size_log2
= sb
.block_size_log2
286 sb
.blocks_per_group
= self
.blocks_per_group
287 sb
.fragments_per_group
= self
.blocks_per_group
288 sb
.inodes_per_group
= self
.inodes_per_group
289 curtime
= int(time
.time())
290 sb
.mount_time
= curtime
291 sb
.write_time
= curtime
293 sb
.max_mount_count
= 21
296 sb
.error_behavior
= 1 # continue on errors
298 sb
.last_check_time
= curtime
299 sb
.max_check_interval
= 15552000 # 6 months
302 sb
.first_inode
= self
.reserved_inode_count
+ 1
303 sb
.inode_size
= self
.inode_size
304 sb
.block_group_number
= block_group
305 sb
.features_compatible
= 0
306 sb
.features_incompatible
= 2 # filetype
307 sb
.features_read_only
= 0
308 sb
.uuid
= self
.uuid
.bytes_le
309 sb
.volume_name
= 'HelenOS rdimage\0'
310 self
.outf
.write(bytes(sb
.pack()))
312 def write_all_metadata(self
):
313 "Write superblocks, block group tables, block and inode bitmaps"
315 bbpg
= self
.blocks_per_group
// 8
316 bipg
= self
.inodes_per_group
// 8
317 def window(arr
, index
, size
):
318 return arr
[index
* size
:(index
+ 1) * size
]
320 for bg_index
in xrange(len(self
.gdt
)):
321 sbpos
= self
.superblock_positions
[bg_index
]
322 sbblock
= (sbpos
+ 1023) // self
.block_size
323 gde
= self
.gdt
[bg_index
]
325 self
.outf
.seek(sbpos
)
326 self
.write_superblock(bg_index
)
328 self
.seek_to_block(sbblock
+1)
331 self
.seek_to_block(gde
.block_bitmap_block
)
332 self
.outf
.write(window(self
.block_allocator
.bitmap
, bg_index
, bbpg
))
334 self
.seek_to_block(gde
.inode_bitmap_block
)
335 self
.outf
.write(window(self
.inode_allocator
.bitmap
, bg_index
, bipg
))
338 "Write all remaining data to the filesystem and close the file"
340 self
.write_inode(self
.root_inode
)
341 self
.write_inode(self
.lost_plus_found
)
342 self
.write_all_metadata()
346 def __init__(self
, base
, count
):
351 self
.bitmap
= array
.array('B', [0] * (count
// 8))
354 def __contains__(self
, item
):
355 "Check if the item is already used"
357 bitidx
= item
- self
.base
358 return get_bit(self
.bitmap
[bitidx
// 8], bitidx
% 8)
360 def alloc(self
, **options
):
361 "Allocate a new item"
363 while self
.nextidx
< self
.count
and (self
.base
+ self
.nextidx
) in self
:
365 if self
.nextidx
== self
.count
:
366 raise Exception("No free item available")
367 item
= self
.base
+ self
.nextidx
369 self
.mark_used(item
, **options
)
372 def mark_used(self
, item
, **options
):
373 "Mark the specified item as used"
375 bitidx
= item
- self
.base
377 raise Exception("Item already used: " + str(item
))
380 self
.bitmap
[index
] = set_bit(self
.bitmap
[index
], bitidx
% 8)
382 self
.mark_cb(item
, **options
)
384 def mark_used_all(self
, items
, **options
):
385 "Mark all specified items as used"
388 self
.mark_used(item
, **options
)
393 TYPE2MODE
= {TYPE_FILE
: 8, TYPE_DIR
: 4}
395 def __init__(self
, fs
, index
, typ
):
397 self
.direct
= [None] * 12
398 self
.indirect
= [None] * 3
406 def as_dirent(self
, name
):
407 "Return a DirEntry corresponding to this inode"
409 return DirEntry(name
, self
.index
, self
.type)
411 def new_block(self
, data
=True):
412 "Get a new block index from allocator and count it here as belonging to the file"
414 block
= self
.fs
.block_allocator
.alloc()
418 def get_or_add_block(self
, block
):
419 "Get or add a real block to the file"
422 return self
.get_or_add_block_direct(block
)
423 return self
.get_or_add_block_indirect(block
)
425 def get_or_add_block_direct(self
, block
):
426 "Get or add a real block to the file (direct blocks)"
428 if self
.direct
[block
] == None:
429 self
.direct
[block
] = self
.new_block()
430 return self
.direct
[block
]
432 def get_or_add_block_indirect(self
, block
):
433 "Get or add a real block to the file (indirect blocks)"
435 # Determine the indirection level for the desired block
438 if block
< self
.fs
.indirect_limits
[i
]:
444 # Compute offsets for the topmost level
445 block_offset_in_level
= block
- self
.fs
.indirect_limits
[level
-1];
446 if self
.indirect
[level
-1] == None:
447 self
.indirect
[level
-1] = self
.new_block(data
= False)
448 current_block
= xstruct
.create(STRUCT_BLOCK_REFERENCE
)
449 current_block
.block_id
= self
.indirect
[level
-1]
450 offset_in_block
= block_offset_in_level
// self
.fs
.indirect_blocks_per_level
[level
-1]
452 # Navigate through other levels
454 assert offset_in_block
< self
.fs
.block_ids_per_block
458 self
.fs
.seek_to_block(current_block
.block_id
, offset_in_block
*4)
459 current_block
.unpack(self
.fs
.outf
.read(4))
461 if current_block
.block_id
== 0:
462 # The block does not exist, so alloc one and write it there
463 self
.fs
.outf
.seek(-4, os
.SEEK_CUR
)
464 current_block
.block_id
= self
.new_block(data
=(level
==0))
465 self
.fs
.outf
.write(current_block
.pack())
467 # If we are on the last level, break here as
468 # there is no next level to visit
472 # Visit the next level
473 block_offset_in_level
%= self
.fs
.indirect_blocks_per_level
[level
];
474 offset_in_block
= block_offset_in_level
// self
.fs
.indirect_blocks_per_level
[level
-1]
476 return current_block
.block_id
479 "Perform a seek to the position indicated by self.pos"
481 block
= self
.pos
// self
.fs
.block_size
482 real_block
= self
.get_or_add_block(block
)
483 offset
= self
.pos
% self
.fs
.block_size
484 self
.fs
.seek_to_block(real_block
, offset
)
486 def write(self
, data
):
487 "Write a piece of data (arbitrarily long) as the contents of the inode"
490 while data_pos
< len(data
):
491 bytes_remaining_in_block
= self
.fs
.block_size
- (self
.pos
% self
.fs
.block_size
)
492 bytes_to_write
= min(bytes_remaining_in_block
, len(data
)-data_pos
)
494 self
.fs
.outf
.write(data
[data_pos
:data_pos
+ bytes_to_write
])
495 self
.pos
+= bytes_to_write
496 data_pos
+= bytes_to_write
497 self
.size
= max(self
.pos
, self
.size
)
499 def align_size_to_block(self
):
500 "Align the size of the inode up to block size"
502 self
.size
= align_up(self
.size
, self
.fs
.block_size
)
504 def align_pos(self
, bytes
):
505 "Align the current position up to bytes boundary"
507 self
.pos
= align_up(self
.pos
, bytes
)
510 "Pack the inode structure and return the result"
512 data
= xstruct
.create(STRUCT_INODE
)
513 data
.mode
= (Inode
.TYPE2MODE
[self
.type] << 12)
514 data
.mode |
= 0x1ff # ugo+rwx
516 data
.size
= self
.size
& 0xFFFFFFFF
518 curtime
= int(time
.time())
519 data
.access_time
= curtime
520 data
.modification_time
= curtime
521 data
.creation_time
= curtime
522 data
.deletion_time
= 0
523 data
.usage_count
= self
.refcount
524 data
.reserved_512_blocks
= self
.blocks
* (self
.fs
.block_size
// 512)
526 blockconv
= lambda x
: 0 if x
== None else x
527 data
.direct_blocks
= map(blockconv
, self
.direct
)
528 data
.indirect_blocks
= map(blockconv
, self
.indirect
)
531 if self
.type == Inode
.TYPE_FILE
:
532 data
.size_high
= (self
.size
>> 32)
534 # size_high represents dir_acl in this case
537 data
.user_id_high
= 0
538 data
.group_id_high
= 0
542 "Represents a linked list directory entry"
544 def __init__(self
, name
, inode
, typ
):
545 self
.name
= name
.encode('UTF-8')
551 "Return size of the entry in bytes"
553 return align_up(8 + len(self
.name
)+1, 4)
555 def write(self
, inode
):
556 "Write the directory entry into the inode"
558 head
= xstruct
.create(STRUCT_DIR_ENTRY_HEAD
)
559 head
.inode
= self
.inode
560 head
.skip
= self
.skip
561 head
.name_length
= len(self
.name
)
562 head
.inode_type
= self
.type
563 inode
.write(head
.pack())
564 inode
.write(self
.name
+'\0')
568 "Manages writing directory entries into an inode (alignment, etc.)"
570 def __init__(self
, inode
):
573 self
.prev_entry
= None
576 def prev_write(self
):
577 "Write a previously remembered entry"
580 self
.prev_entry
.skip
= self
.pos
- self
.prev_pos
582 self
.prev_entry
.write(self
.inode
)
584 def add(self
, entry
):
585 "Add a directory entry to the directory"
588 block_size
= self
.inode
.fs
.block_size
589 if align_up(self
.pos
, block_size
) < align_up(self
.pos
+ size
, block_size
):
590 self
.pos
= align_up(self
.pos
, block_size
)
592 self
.prev_entry
= entry
593 self
.prev_pos
= self
.pos
597 "Write the last entry and finish writing the directory contents"
601 self
.pos
= align_up(self
.pos
, self
.inode
.fs
.block_size
)
603 self
.inode
.align_size_to_block()
605 def subtree_stats(root
, block_size
):
606 "Recursively calculate statistics"
610 dir_writer
= DirWriter(None)
612 for item
in listdir_items(root
):
615 blocks
+= count_up(item
.size
, block_size
)
617 subtree_blocks
, subtree_inodes
= subtree_stats(item
.path
, block_size
)
618 blocks
+= subtree_blocks
619 inodes
+= subtree_inodes
622 blocks
+= count_up(dir_writer
.pos
, block_size
)
623 return (blocks
, inodes
)
627 print(prname
+ " <EXTRA_BYTES> <PATH> <IMAGE>")
630 if (len(sys
.argv
) < 4):
634 if (not sys
.argv
[1].isdigit()):
635 print("<EXTRA_BYTES> must be a number")
638 extra_bytes
= int(sys
.argv
[1])
640 path
= os
.path
.abspath(sys
.argv
[2])
641 if (not os
.path
.isdir(path
)):
642 print("<PATH> must be a directory")
647 reserved_inode_count
= 10
648 blocks_per_group
= 1024
649 inodes_per_group
= 512
651 blocks
, inodes
= subtree_stats(path
, block_size
)
652 blocks
+= count_up(extra_bytes
, block_size
)
653 inodes
+= reserved_inode_count
655 inodes_per_group
= align_up(inodes_per_group
, 8)
656 blocks_per_group
= align_up(blocks_per_group
, 8)
658 inode_table_blocks_per_group
= (inodes_per_group
* inode_size
) // block_size
659 inode_bitmap_blocks_per_group
= count_up(inodes_per_group
// 8, block_size
)
660 block_bitmap_blocks_per_group
= count_up(blocks_per_group
// 8, block_size
)
661 free_blocks_per_group
= blocks_per_group
662 free_blocks_per_group
-= inode_table_blocks_per_group
663 free_blocks_per_group
-= inode_bitmap_blocks_per_group
664 free_blocks_per_group
-= block_bitmap_blocks_per_group
665 free_blocks_per_group
-= 10 # one for SB and some reserve for GDT
667 block_groups
= max(count_up(inodes
, inodes_per_group
), count_up(blocks
, free_blocks_per_group
))
669 fs
= Filesystem(sys
.argv
[3], block_groups
, blocks_per_group
, inodes_per_group
,
670 block_size
, inode_size
, reserved_inode_count
)
672 fs
.subtree_add(fs
.root_inode
, fs
.root_inode
, path
, is_root
=True)
675 if __name__
== '__main__':