tools/mkext2.py

   1 #!/usr/bin/env python
   2 #
   3 # Copyright (c) 2011 Martin Sucha
   4 # All rights reserved.
   5 #
   6 # Redistribution and use in source and binary forms, with or without
   7 # modification, are permitted provided that the following conditions
   8 # are met:
   9 #
  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.
  17 #
  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.
  28 #
  29
  30 """
  31 EXT2 creator
  32 """
  33
  34 import sys
  35 import os
  36 import xstruct
  37 import array
  38 import time
  39 import uuid
  40 from imgutil import *
  41
  42 if sys.version >= '3':
  43         xrange = range
  44
  45 GDE_SIZE = 32
  46
  47 STRUCT_DIR_ENTRY_HEAD = """little:
  48         uint32_t inode       /* inode number */
  49         uint16_t skip        /* byte offset to the next record */
  50         uint8_t  name_length /* file attributes */
  51         uint8_t  inode_type  /* type of the referenced inode */
  52 """
  53
  54 STRUCT_SUPERBLOCK = """little:
  55         uint32_t total_inode_count    /* Total number of inodes */
  56         uint32_t total_block_count    /* Total number of blocks */
  57         uint32_t reserved_block_count /* Total number of reserved blocks */
  58         uint32_t free_block_count     /* Total number of free blocks */
  59         uint32_t free_inode_count     /* Total number of free inodes */
  60         uint32_t first_block          /* Block containing the superblock */
  61         uint32_t block_size_log2      /* log_2(block_size) */
  62         int32_t  fragment_size_log2   /* log_2(fragment size) */
  63         uint32_t blocks_per_group     /* Number of blocks in one block group */
  64         uint32_t fragments_per_group  /* Number of fragments per block group */
  65         uint32_t inodes_per_group     /* Number of inodes per block group */
  66         uint32_t mount_time           /* Time when the filesystem was last mounted */
  67         uint32_t write_time           /* Time when the filesystem was last written */
  68         uint16_t mount_count          /* Mount count since last full filesystem check */
  69         uint16_t max_mount_count      /* Number of mounts after which the fs must be checked */
  70         uint16_t magic                /* Magic value */
  71         uint16_t state                /* State (mounted/unmounted) */
  72         uint16_t error_behavior       /* What to do when errors are encountered */
  73         uint16_t rev_minor            /* Minor revision level */
  74         uint32_t last_check_time      /* Unix time of last fs check */
  75         uint32_t max_check_interval   /* Max unix time interval between checks */
  76         uint32_t os                   /* OS that created the filesystem */
  77         uint32_t rev_major            /* Major revision level */
  78         padding[4] /* default reserved uid and gid */
  79
  80         /* Following is for ext2 revision 1 only */
  81         uint32_t first_inode
  82         uint16_t inode_size
  83         uint16_t block_group_number /* Block group where this SB is stored */
  84         uint32_t features_compatible
  85         uint32_t features_incompatible
  86         uint32_t features_read_only
  87         char     uuid[16]
  88         char     volume_name[16]
  89 """
  90
  91 STRUCT_BLOCK_GROUP_DESCRIPTOR = """little:
  92         uint32_t block_bitmap_block      /* Block ID for block bitmap */
  93         uint32_t inode_bitmap_block      /* Block ID for inode bitmap */
  94         uint32_t inode_table_first_block /* Block ID of first block of inode table */
  95         uint16_t free_block_count        /* Count of free blocks */
  96         uint16_t free_inode_count        /* Count of free inodes */
  97         uint16_t directory_inode_count   /* Number of inodes allocated to directories */
  98 """
  99
 100 STRUCT_INODE = """little:
 101         uint16_t mode
 102         uint16_t user_id
 103         uint32_t size
 104         uint32_t access_time
 105         uint32_t creation_time
 106         uint32_t modification_time
 107         uint32_t deletion_time
 108         uint16_t group_id
 109         uint16_t usage_count /* Hard link count, when 0 the inode is to be freed */
 110         uint32_t reserved_512_blocks /* Size of this inode in 512-byte blocks */
 111         uint32_t flags
 112         padding[4]
 113         uint32_t direct_blocks[12] /* Direct block ids stored in this inode */
 114         uint32_t indirect_blocks[3]
 115         uint32_t version
 116         uint32_t file_acl
 117         uint32_t size_high /* For regular files in version >= 1, dir_acl if dir */
 118         padding[6]
 119         uint16_t mode_high /* Hurd only */
 120         uint16_t user_id_high /* Linux/Hurd only */
 121         uint16_t group_id_high /* Linux/Hurd only */
 122 """
 123
 124 # The following is here to handle byte-order conversion in indirect block lookups
 125 STRUCT_BLOCK_REFERENCE = """little:
 126         uint32_t block_id /* Referenced block ID */
 127 """
 128
 129 class Filesystem:
 130         def __init__(self, filename, block_groups, blocks_per_group, inodes_per_group, block_size, inode_size, reserved_inode_count):
 131                 "Initialize the filesystem writer"
 132
 133                 outf = open(filename, "w+b")
 134                 # Set the correct size of the image, so that we can read arbitrary position
 135                 outf.truncate(block_size * blocks_per_group * block_groups)
 136                 self.outf = outf
 137                 self.uuid = uuid.uuid4()
 138                 self.block_size = block_size
 139                 self.inode_size = inode_size
 140                 self.block_groups = block_groups
 141                 self.blocks_per_group = blocks_per_group
 142                 self.inodes_per_group = inodes_per_group
 143                 self.reserved_inode_count = reserved_inode_count
 144                 self.gdt_blocks = count_up(block_groups * GDE_SIZE, block_size)
 145                 self.inode_table_blocks_per_group = (inodes_per_group * inode_size) // block_size
 146                 self.inode_bitmap_blocks_per_group = count_up(inodes_per_group // 8, block_size)
 147                 self.block_bitmap_blocks_per_group = count_up(blocks_per_group // 8, block_size)
 148                 self.total_block_count = self.blocks_per_group * self.block_groups
 149                 self.total_inode_count = self.inodes_per_group * self.block_groups
 150                 self.inode_table_blocks = count_up(self.total_inode_count * inode_size, block_size)
 151                 self.inodes = {}
 152                 self.superblock_at_block = 2047 // block_size
 153                 self.block_ids_per_block = self.block_size // 4
 154                 self.indirect_limits = [12, None, None, None]
 155                 self.indirect_blocks_per_level = [1, None, None, None]
 156                 for i in range(1,4):
 157                         self.indirect_blocks_per_level[i] = self.indirect_blocks_per_level[i-1] * self.block_ids_per_block
 158                         self.indirect_limits[i] = self.indirect_limits[i-1] + self.indirect_blocks_per_level[i]
 159                 self.block_allocator = Allocator(0, self.total_block_count)
 160                 self.inode_allocator = Allocator(1, self.total_inode_count)
 161                 self.init_gdt()
 162                 # Set the callbacks after GDT has been initialized
 163                 self.block_allocator.mark_cb = self.mark_block_cb
 164                 self.inode_allocator.mark_cb = self.mark_inode_cb
 165                 self.block_allocator.mark_used_all(range(self.superblock_at_block))
 166                 self.inode_allocator.mark_used_all(range(1, self.reserved_inode_count + 1))
 167                 self.root_inode = Inode(self, 2, Inode.TYPE_DIR)
 168                 self.gdt[0].directory_inode_count += 1
 169                 self.lost_plus_found = Inode(self, self.inode_allocator.alloc(directory=True), Inode.TYPE_DIR)
 170                 lpf_dir = DirWriter(self.lost_plus_found)
 171                 lpf_dir.add(self.lost_plus_found.as_dirent('.'))
 172                 lpf_dir.add(self.root_inode.as_dirent('..'))
 173                 lpf_dir.finish()
 174
 175         def init_gdt(self):
 176                 "Initialize block group descriptor table"
 177
 178                 self.superblock_positions = []
 179                 self.gdt = []
 180                 consumed_blocks_per_group = (1 + self.gdt_blocks +
 181                             self.inode_bitmap_blocks_per_group +
 182                             self.block_bitmap_blocks_per_group +
 183                             self.inode_table_blocks_per_group)
 184                 initial_free_blocks = self.blocks_per_group - consumed_blocks_per_group
 185                 for bg in range(self.block_groups):
 186                         base = bg * self.blocks_per_group
 187                         if (bg == 0):
 188                                 base = self.superblock_at_block
 189                                 self.superblock_positions.append(1024)
 190                         else:
 191                                 self.superblock_positions.append(base * self.block_size)
 192                         self.block_allocator.mark_used_all(range(base, base+consumed_blocks_per_group))
 193                         pos = base + 1 + self.gdt_blocks
 194                         gde = xstruct.create(STRUCT_BLOCK_GROUP_DESCRIPTOR)
 195                         gde.block_bitmap_block = pos
 196                         pos += self.block_bitmap_blocks_per_group
 197                         gde.inode_bitmap_block = pos
 198                         pos += self.inode_bitmap_blocks_per_group
 199                         gde.inode_table_first_block = pos
 200                         gde.free_block_count = initial_free_blocks
 201                         gde.free_inode_count = self.inodes_per_group
 202                         gde.directory_inode_count = 0
 203                         self.gdt.append(gde)
 204
 205         def mark_block_cb(self, block):
 206                 "Called after a block has been allocated"
 207
 208                 self.gdt[block // self.blocks_per_group].free_block_count -= 1
 209
 210         def mark_inode_cb(self, index, directory=False):
 211                 "Called after an inode has been allocated"
 212
 213                 index -= 1
 214                 gde = self.gdt[index // self.inodes_per_group]
 215                 gde.free_inode_count -= 1
 216                 if directory:
 217                         gde.directory_inode_count += 1
 218
 219         def seek_to_block(self, block, offset=0):
 220                 "Seek to offset bytes after the start of the given block"
 221
 222                 if offset < 0 or offset > self.block_size:
 223                         raise Exception("Invalid in-block offset")
 224                 self.outf.seek(block * self.block_size + offset)
 225
 226         def seek_to_inode(self, index):
 227                 "Seek to the start of the inode structure for the inode number index"
 228
 229                 index -= 1
 230                 if index < 0:
 231                         raise Exception("Invalid inode number")
 232                 gde = self.gdt[index // self.inodes_per_group]
 233                 base_block = gde.inode_table_first_block
 234                 offset = (index % self.inodes_per_group) * self.inode_size
 235                 block = base_block + (offset // self.block_size)
 236                 self.seek_to_block(block, offset % self.block_size)
 237
 238         def subtree_add(self, inode, parent_inode, dirpath, is_root=False):
 239                 "Recursively add files to the filesystem"
 240
 241                 dir_writer = DirWriter(inode)
 242                 dir_writer.add(inode.as_dirent('.'))
 243                 dir_writer.add(parent_inode.as_dirent('..'))
 244
 245                 if is_root:
 246                         dir_writer.add(self.lost_plus_found.as_dirent('lost+found'))
 247
 248                 for item in listdir_items(dirpath):
 249                         newidx = self.inode_allocator.alloc(directory = item.is_dir)
 250                         if item.is_file:
 251                                 child_inode = Inode(self, newidx, Inode.TYPE_FILE)
 252                                 for data in chunks(item, self.block_size):
 253                                         child_inode.write(data)
 254                         elif item.is_dir:
 255                                 child_inode = Inode(self, newidx, Inode.TYPE_DIR)
 256                                 self.subtree_add(child_inode, inode, item.path)
 257
 258                         dir_writer.add(child_inode.as_dirent(item.name))
 259                         self.write_inode(child_inode)
 260
 261                 dir_writer.finish()
 262
 263         def write_inode(self, inode):
 264                 "Write inode information into the inode table"
 265
 266                 self.seek_to_inode(inode.index)
 267                 self.outf.write(inode.pack())
 268
 269         def write_gdt(self):
 270                 "Write group descriptor table at the current file position"
 271
 272                 for gde in self.gdt:
 273                         data = bytes(gde.pack())
 274                         self.outf.write(data)
 275                         self.outf.seek(GDE_SIZE-len(data), os.SEEK_CUR)
 276
 277         def write_superblock(self, block_group):
 278                 "Write superblock at the current position"
 279
 280                 sb = xstruct.create(STRUCT_SUPERBLOCK)
 281                 sb.total_inode_count = self.total_inode_count
 282                 sb.total_block_count = self.total_block_count
 283                 sb.reserved_block_count = 0
 284                 sb.free_block_count = self.block_allocator.free
 285                 sb.free_inode_count = self.inode_allocator.free
 286                 sb.first_block = self.superblock_at_block
 287                 sb.block_size_log2 = num_of_trailing_bin_zeros(self.block_size) - 10
 288                 sb.fragment_size_log2 = sb.block_size_log2
 289                 sb.blocks_per_group = self.blocks_per_group
 290                 sb.fragments_per_group = self.blocks_per_group
 291                 sb.inodes_per_group = self.inodes_per_group
 292                 curtime = int(time.time())
 293                 sb.mount_time = curtime
 294                 sb.write_time = curtime
 295                 sb.mount_count = 0
 296                 sb.max_mount_count = 21
 297                 sb.magic = 0xEF53
 298                 sb.state = 5 # clean
 299                 sb.error_behavior = 1 # continue on errors
 300                 sb.rev_minor = 0
 301                 sb.last_check_time = curtime
 302                 sb.max_check_interval = 15552000 # 6 months
 303                 sb.os = 0 # Linux
 304                 sb.rev_major = 1
 305                 sb.first_inode = self.reserved_inode_count + 1
 306                 sb.inode_size = self.inode_size
 307                 sb.block_group_number = block_group
 308                 sb.features_compatible = 0
 309                 sb.features_incompatible = 2 # filetype
 310                 sb.features_read_only = 0
 311                 sb.uuid = self.uuid.bytes_le
 312                 sb.volume_name = 'HelenOS-rd\0\0\0\0\0\0'
 313                 self.outf.write(bytes(sb.pack()))
 314
 315         def write_all_metadata(self):
 316                 "Write superblocks, block group tables, block and inode bitmaps"
 317
 318                 bbpg = self.blocks_per_group // 8
 319                 bipg = self.inodes_per_group // 8
 320                 def window(arr, index, size):
 321                         return arr[index * size:(index + 1) * size]
 322
 323                 for bg_index in xrange(len(self.gdt)):
 324                         sbpos = self.superblock_positions[bg_index]
 325                         sbblock = (sbpos + 1023) // self.block_size
 326                         gde = self.gdt[bg_index]
 327
 328                         self.outf.seek(sbpos)
 329                         self.write_superblock(bg_index)
 330
 331                         self.seek_to_block(sbblock+1)
 332                         self.write_gdt()
 333
 334                         self.seek_to_block(gde.block_bitmap_block)
 335                         self.outf.write(window(self.block_allocator.bitmap, bg_index, bbpg))
 336
 337                         self.seek_to_block(gde.inode_bitmap_block)
 338                         self.outf.write(window(self.inode_allocator.bitmap, bg_index, bipg))
 339
 340         def close(self):
 341                 "Write all remaining data to the filesystem and close the file"
 342
 343                 self.write_inode(self.root_inode)
 344                 self.write_inode(self.lost_plus_found)
 345                 self.write_all_metadata()
 346                 self.outf.close()
 347
 348 class Allocator:
 349         def __init__(self, base, count):
 350                 self.count = count
 351                 self.base = base
 352                 self.free = count
 353                 self.nextidx = 0
 354                 self.bitmap = array.array('B', [0] * (count // 8))
 355                 self.mark_cb = None
 356
 357         def __contains__(self, item):
 358                 "Check if the item is already used"
 359
 360                 bitidx = item - self.base
 361                 return get_bit(self.bitmap[bitidx // 8], bitidx % 8)
 362
 363         def alloc(self, **options):
 364                 "Allocate a new item"
 365
 366                 while self.nextidx < self.count and (self.base + self.nextidx) in self:
 367                         self.nextidx += 1
 368                 if self.nextidx == self.count:
 369                         raise Exception("No free item available")
 370                 item = self.base + self.nextidx
 371                 self.nextidx += 1
 372                 self.mark_used(item, **options)
 373                 return item
 374
 375         def mark_used(self, item, **options):
 376                 "Mark the specified item as used"
 377
 378                 bitidx = item - self.base
 379                 if item in self:
 380                         raise Exception("Item already used: " + str(item))
 381                 self.free -= 1
 382                 index = bitidx // 8
 383                 self.bitmap[index] = set_bit(self.bitmap[index], bitidx % 8)
 384                 if self.mark_cb:
 385                         self.mark_cb(item, **options)
 386
 387         def mark_used_all(self, items, **options):
 388                 "Mark all specified items as used"
 389
 390                 for item in items:
 391                         self.mark_used(item, **options)
 392
 393 class Inode:
 394         TYPE_FILE = 1
 395         TYPE_DIR = 2
 396         TYPE2MODE = {TYPE_FILE: 8, TYPE_DIR: 4}
 397
 398         def __init__(self, fs, index, typ):
 399                 self.fs = fs
 400                 self.direct = [None] * 12
 401                 self.indirect = [None] * 3
 402                 self.pos = 0
 403                 self.size = 0
 404                 self.blocks = 0
 405                 self.index = index
 406                 self.type = typ
 407                 self.refcount = 0
 408
 409         def as_dirent(self, name):
 410                 "Return a DirEntry corresponding to this inode"
 411                 self.refcount += 1
 412                 return DirEntry(name, self.index, self.type)
 413
 414         def new_block(self, data=True):
 415                 "Get a new block index from allocator and count it here as belonging to the file"
 416
 417                 block = self.fs.block_allocator.alloc()
 418                 self.blocks += 1
 419                 return block
 420
 421         def get_or_add_block(self, block):
 422                 "Get or add a real block to the file"
 423
 424                 if block < 12:
 425                         return self.get_or_add_block_direct(block)
 426                 return self.get_or_add_block_indirect(block)
 427
 428         def get_or_add_block_direct(self, block):
 429                 "Get or add a real block to the file (direct blocks)"
 430
 431                 if self.direct[block] == None:
 432                         self.direct[block] = self.new_block()
 433                 return self.direct[block]
 434
 435         def get_or_add_block_indirect(self, block):
 436                 "Get or add a real block to the file (indirect blocks)"
 437
 438                 # Determine the indirection level for the desired block
 439                 level = None
 440                 for i in range(4):
 441                         if block < self.fs.indirect_limits[i]:
 442                                 level = i
 443                                 break
 444
 445                 assert level != None
 446
 447                 # Compute offsets for the topmost level
 448                 block_offset_in_level = block - self.fs.indirect_limits[level-1];
 449                 if self.indirect[level-1] == None:
 450                         self.indirect[level-1] = self.new_block(data = False)
 451                 current_block = xstruct.create(STRUCT_BLOCK_REFERENCE)
 452                 current_block.block_id = self.indirect[level-1]
 453                 offset_in_block = block_offset_in_level // self.fs.indirect_blocks_per_level[level-1]
 454
 455                 # Navigate through other levels
 456                 while level > 0:
 457                         assert offset_in_block < self.fs.block_ids_per_block
 458
 459                         level -= 1
 460
 461                         self.fs.seek_to_block(current_block.block_id, offset_in_block*4)
 462                         current_block.unpack(self.fs.outf.read(4))
 463
 464                         if current_block.block_id == 0:
 465                                 # The block does not exist, so alloc one and write it there
 466                                 self.fs.outf.seek(-4, os.SEEK_CUR)
 467                                 current_block.block_id = self.new_block(data=(level==0))
 468                                 self.fs.outf.write(current_block.pack())
 469
 470                         # If we are on the last level, break here as
 471                         # there is no next level to visit
 472                         if level == 0:
 473                                 break
 474
 475                         # Visit the next level
 476                         block_offset_in_level %= self.fs.indirect_blocks_per_level[level];
 477                         offset_in_block = block_offset_in_level // self.fs.indirect_blocks_per_level[level-1]
 478
 479                 return current_block.block_id
 480
 481         def do_seek(self):
 482                 "Perform a seek to the position indicated by self.pos"
 483
 484                 block = self.pos // self.fs.block_size
 485                 real_block = self.get_or_add_block(block)
 486                 offset = self.pos % self.fs.block_size
 487                 self.fs.seek_to_block(real_block, offset)
 488
 489         def write(self, data):
 490                 "Write a piece of data (arbitrarily long) as the contents of the inode"
 491
 492                 data_pos = 0
 493                 while data_pos < len(data):
 494                         bytes_remaining_in_block = self.fs.block_size - (self.pos % self.fs.block_size)
 495                         bytes_to_write = min(bytes_remaining_in_block, len(data)-data_pos)
 496                         self.do_seek()
 497                         self.fs.outf.write(data[data_pos:data_pos + bytes_to_write])
 498                         self.pos += bytes_to_write
 499                         data_pos += bytes_to_write
 500                         self.size = max(self.pos, self.size)
 501
 502         def align_size_to_block(self):
 503                 "Align the size of the inode up to block size"
 504
 505                 self.size = align_up(self.size, self.fs.block_size)
 506
 507         def align_pos(self, bytes):
 508                 "Align the current position up to bytes boundary"
 509
 510                 self.pos = align_up(self.pos, bytes)
 511
 512         def set_pos(self, pos):
 513                 "Set the current position"
 514
 515                 self.pos = pos
 516
 517         def pack(self):
 518                 "Pack the inode structure and return the result"
 519
 520                 data = xstruct.create(STRUCT_INODE)
 521                 data.mode = (Inode.TYPE2MODE[self.type] << 12)
 522                 data.mode |= 0x1ff # ugo+rwx
 523                 data.user_id = 0
 524                 data.size = self.size & 0xFFFFFFFF
 525                 data.group_id = 0
 526                 curtime = int(time.time())
 527                 data.access_time = curtime
 528                 data.modification_time = curtime
 529                 data.creation_time = curtime
 530                 data.deletion_time = 0
 531                 data.usage_count = self.refcount
 532                 data.reserved_512_blocks = self.blocks * (self.fs.block_size // 512)
 533                 data.flags = 0
 534                 blockconv = lambda x: 0 if x == None else x
 535                 data.direct_blocks = list(map(blockconv, self.direct))
 536                 data.indirect_blocks = list(map(blockconv, self.indirect))
 537                 data.version = 0
 538                 data.file_acl = 0
 539                 if self.type == Inode.TYPE_FILE:
 540                         data.size_high = (self.size >> 32)
 541                 else:
 542                         # size_high represents dir_acl in this case
 543                         data.size_high = 0
 544                 data.mode_high = 0
 545                 data.user_id_high = 0
 546                 data.group_id_high = 0
 547                 return data.pack()
 548
 549 class DirEntry:
 550         "Represents a linked list directory entry"
 551
 552         def __init__(self, name, inode, typ):
 553                 self.name = name.encode('UTF-8')
 554                 self.inode = inode
 555                 self.skip = None
 556                 self.type = typ
 557
 558         def size(self):
 559                 "Return size of the entry in bytes"
 560
 561                 return align_up(8 + len(self.name)+1, 4)
 562
 563         def write(self, inode):
 564                 "Write the directory entry into the inode"
 565
 566                 head = xstruct.create(STRUCT_DIR_ENTRY_HEAD)
 567                 head.inode = self.inode
 568                 head.skip = self.skip
 569                 head.name_length = len(self.name)
 570                 head.inode_type = self.type
 571                 inode.write(head.pack())
 572                 inode.write(self.name+'\0'.encode())
 573                 inode.align_pos(4)
 574
 575 class DirWriter:
 576         "Manages writing directory entries into an inode (alignment, etc.)"
 577
 578         def __init__(self, inode):
 579                 self.pos = 0
 580                 self.inode = inode
 581                 self.prev_entry = None
 582                 self.prev_pos = None
 583
 584         def prev_write(self):
 585                 "Write a previously remembered entry"
 586
 587                 if self.prev_entry:
 588                         self.prev_entry.skip = self.pos - self.prev_pos
 589                         if self.inode:
 590                                 self.prev_entry.write(self.inode)
 591                                 self.inode.set_pos(self.pos)
 592
 593         def add(self, entry):
 594                 "Add a directory entry to the directory"
 595
 596                 size = entry.size()
 597                 block_size = self.inode.fs.block_size
 598                 if align_up(self.pos, block_size) < align_up(self.pos + size, block_size):
 599                         self.pos = align_up(self.pos, block_size)
 600                 self.prev_write()
 601                 self.prev_entry = entry
 602                 self.prev_pos = self.pos
 603                 self.pos += size
 604
 605         def finish(self):
 606                 "Write the last entry and finish writing the directory contents"
 607
 608                 if not self.inode:
 609                         return
 610                 self.pos = align_up(self.pos, self.inode.fs.block_size)
 611                 self.prev_write()
 612                 self.inode.align_size_to_block()
 613
 614 def subtree_stats(root, block_size):
 615         "Recursively calculate statistics"
 616
 617         blocks = 0
 618         inodes = 1
 619         dir_writer = DirWriter(None)
 620
 621         for item in listdir_items(root):
 622                 inodes += 1
 623                 if item.is_file:
 624                         blocks += count_up(item.size, block_size)
 625                 elif item.is_dir:
 626                         subtree_blocks, subtree_inodes = subtree_stats(item.path, block_size)
 627                         blocks += subtree_blocks
 628                         inodes += subtree_inodes
 629
 630         dir_writer.finish()
 631         blocks += count_up(dir_writer.pos, block_size)
 632         return (blocks, inodes)
 633
 634 def usage(prname):
 635         "Print usage syntax"
 636         print(prname + " <EXTRA_BYTES> <PATH> <IMAGE>")
 637
 638 def main():
 639         if (len(sys.argv) < 4):
 640                 usage(sys.argv[0])
 641                 return
 642
 643         if (not sys.argv[1].isdigit()):
 644                 print("<EXTRA_BYTES> must be a number")
 645                 return
 646
 647         extra_bytes = int(sys.argv[1])
 648
 649         path = os.path.abspath(sys.argv[2])
 650         if (not os.path.isdir(path)):
 651                 print("<PATH> must be a directory")
 652                 return
 653
 654         block_size = 4096
 655         inode_size = 128
 656         reserved_inode_count = 10
 657         blocks_per_group = 1024
 658         inodes_per_group = 512
 659
 660         blocks, inodes = subtree_stats(path, block_size)
 661         blocks += count_up(extra_bytes, block_size)
 662         inodes += reserved_inode_count
 663
 664         inodes_per_group = align_up(inodes_per_group, 8)
 665         blocks_per_group = align_up(blocks_per_group, 8)
 666
 667         inode_table_blocks_per_group = (inodes_per_group * inode_size) // block_size
 668         inode_bitmap_blocks_per_group = count_up(inodes_per_group // 8, block_size)
 669         block_bitmap_blocks_per_group = count_up(blocks_per_group // 8, block_size)
 670         free_blocks_per_group = blocks_per_group
 671         free_blocks_per_group -= inode_table_blocks_per_group
 672         free_blocks_per_group -= inode_bitmap_blocks_per_group
 673         free_blocks_per_group -= block_bitmap_blocks_per_group
 674         free_blocks_per_group -= 10 # one for SB and some reserve for GDT
 675
 676         block_groups = max(count_up(inodes, inodes_per_group), count_up(blocks, free_blocks_per_group))
 677
 678         fs = Filesystem(sys.argv[3], block_groups, blocks_per_group, inodes_per_group,
 679                                 block_size, inode_size, reserved_inode_count)
 680
 681         fs.subtree_add(fs.root_inode, fs.root_inode, path, is_root=True)
 682         fs.close()
 683
 684 if __name__ == '__main__':
 685         main()