Index: HelenOS.config =================================================================== --- HelenOS.config (revision a2271a385d521c53eb7137d1142971451edc6aaa) +++ HelenOS.config (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -88,4 +88,5 @@ @ "tmpfs" TMPFS image @ "fat" FAT16 image +@ "ext2fs" EXT2 image ! RDFMT (choice) Index: boot/Makefile =================================================================== --- boot/Makefile (revision a2271a385d521c53eb7137d1142971451edc6aaa) +++ boot/Makefile (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -50,4 +50,7 @@ $(MKFAT) 1048576 $(DIST_PATH) $@ endif +ifeq ($(RDFMT),ext2fs) + $(MKEXT2) 1048576 $(DIST_PATH) $@ +endif build_dist: clean_dist Index: boot/Makefile.common =================================================================== --- boot/Makefile.common (revision a2271a385d521c53eb7137d1142971451edc6aaa) +++ boot/Makefile.common (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -56,4 +56,5 @@ MKTMPFS = $(TOOLS_PATH)/mktmpfs.py MKFAT = $(TOOLS_PATH)/mkfat.py +MKEXT2 = $(TOOLS_PATH)/mkext2.py MKUIMAGE = $(TOOLS_PATH)/mkuimage.py @@ -82,4 +83,8 @@ ifeq ($(RDFMT),fat) INIT_TASKS += $(USPACE_PATH)/srv/fs/fat/fat +endif + +ifeq ($(RDFMT),ext2fs) + INIT_TASKS += $(USPACE_PATH)/srv/fs/ext2fs/ext2fs endif Index: tools/imgutil.py =================================================================== --- tools/imgutil.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) +++ tools/imgutil.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -0,0 +1,108 @@ +#!/usr/bin/env python +# +# Copyright (c) 2008 Martin Decky +# Copyright (c) 2011 Martin Sucha +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# + +""" +Utilities for filesystem image creators +""" + +import os +import stat + +exclude_names = set(['.svn', '.bzr']) + +def align_up(size, alignment): + "Return size aligned up to alignment" + + if (size % alignment == 0): + return size + + return ((size // alignment) + 1) * alignment + +def count_up(size, alignment): + "Return units necessary to fit the size" + + if (size % alignment == 0): + return (size // alignment) + + return ((size // alignment) + 1) + +def num_of_trailing_bin_zeros(num): + "Return number of trailing zeros in binary representation" + + i = 0 + if (num == 0): raise ValueError() + while num & 1 == 0: + i += 1 + num = num >> 1 + return i + +def get_bit(number, n): + "Return True if n-th least-significant bit is set in the given number" + + return bool((number >> n) & 1) + +def set_bit(number, n): + "Return the number with n-th least-significant bit set" + + return number | (1 << n) + +class ItemToPack: + "Stores information about one directory item to be added to the image" + + def __init__(self, parent, name): + self.parent = parent + self.name = name + self.path = os.path.join(parent, name) + self.stat = os.stat(self.path) + self.is_dir = stat.S_ISDIR(self.stat.st_mode) + self.is_file = stat.S_ISREG(self.stat.st_mode) + self.size = self.stat.st_size + +def listdir_items(path): + "Return a list of items to be packed inside a fs image" + + for name in os.listdir(path): + if name in exclude_names: + continue + item = ItemToPack(path, name) + if not (item.is_dir or item.is_file): + continue + yield item + +def chunks(item, chunk_size): + "Iterate contents of a file in chunks of a given size" + + inf = open(item.path, 'rb') + rd = 0 + while (rd < item.size): + data = bytes(inf.read(chunk_size)) + yield data + rd += len(data) + inf.close() Index: tools/mkext2.py =================================================================== --- tools/mkext2.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) +++ tools/mkext2.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -0,0 +1,676 @@ +#!/usr/bin/env python +# +# Copyright (c) 2011 Martin Sucha +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# + +""" +EXT2 creator +""" + +import sys +import os +import xstruct +import array +import time +import uuid +from imgutil import * + +GDE_SIZE = 32 + +STRUCT_DIR_ENTRY_HEAD = """little: + uint32_t inode /* inode number */ + uint16_t skip /* byte offset to the next record */ + uint8_t name_length /* file attributes */ + uint8_t inode_type /* type of the referenced inode */ +""" + +STRUCT_SUPERBLOCK = """little: + uint32_t total_inode_count /* Total number of inodes */ + uint32_t total_block_count /* Total number of blocks */ + uint32_t reserved_block_count /* Total number of reserved blocks */ + uint32_t free_block_count /* Total number of free blocks */ + uint32_t free_inode_count /* Total number of free inodes */ + uint32_t first_block /* Block containing the superblock */ + uint32_t block_size_log2 /* log_2(block_size) */ + int32_t fragment_size_log2 /* log_2(fragment size) */ + uint32_t blocks_per_group /* Number of blocks in one block group */ + uint32_t fragments_per_group /* Number of fragments per block group */ + uint32_t inodes_per_group /* Number of inodes per block group */ + uint32_t mount_time /* Time when the filesystem was last mounted */ + uint32_t write_time /* Time when the filesystem was last written */ + uint16_t mount_count /* Mount count since last full filesystem check */ + uint16_t max_mount_count /* Number of mounts after which the fs must be checked */ + uint16_t magic /* Magic value */ + uint16_t state /* State (mounted/unmounted) */ + uint16_t error_behavior /* What to do when errors are encountered */ + uint16_t rev_minor /* Minor revision level */ + uint32_t last_check_time /* Unix time of last fs check */ + uint32_t max_check_interval /* Max unix time interval between checks */ + uint32_t os /* OS that created the filesystem */ + uint32_t rev_major /* Major revision level */ + padding[4] /* default reserved uid and gid */ + + /* Following is for ext2 revision 1 only */ + uint32_t first_inode + uint16_t inode_size + uint16_t block_group_number /* Block group where this SB is stored */ + uint32_t features_compatible + uint32_t features_incompatible + uint32_t features_read_only + char uuid[16] + char volume_name[16] +""" + +STRUCT_BLOCK_GROUP_DESCRIPTOR = """little: + uint32_t block_bitmap_block /* Block ID for block bitmap */ + uint32_t inode_bitmap_block /* Block ID for inode bitmap */ + uint32_t inode_table_first_block /* Block ID of first block of inode table */ + uint16_t free_block_count /* Count of free blocks */ + uint16_t free_inode_count /* Count of free inodes */ + uint16_t directory_inode_count /* Number of inodes allocated to directories */ +""" + +STRUCT_INODE = """little: + uint16_t mode + uint16_t user_id + uint32_t size + uint32_t access_time + uint32_t creation_time + uint32_t modification_time + uint32_t deletion_time + uint16_t group_id + uint16_t usage_count /* Hard link count, when 0 the inode is to be freed */ + uint32_t reserved_512_blocks /* Size of this inode in 512-byte blocks */ + uint32_t flags + padding[4] + uint32_t direct_blocks[12] /* Direct block ids stored in this inode */ + uint32_t indirect_blocks[3] + uint32_t version + uint32_t file_acl + uint32_t size_high /* For regular files in version >= 1, dir_acl if dir */ + padding[6] + uint16_t mode_high /* Hurd only */ + uint16_t user_id_high /* Linux/Hurd only */ + uint16_t group_id_high /* Linux/Hurd only */ +""" + +# The following is here to handle byte-order conversion in indirect block lookups +STRUCT_BLOCK_REFERENCE = """little: + uint32_t block_id /* Referenced block ID */ +""" + +class Filesystem: + def __init__(self, filename, block_groups, blocks_per_group, inodes_per_group, block_size, inode_size, reserved_inode_count): + "Initialize the filesystem writer" + + outf = open(filename, "w+b") + # Set the correct size of the image, so that we can read arbitrary position + outf.truncate(block_size * blocks_per_group * block_groups) + self.outf = outf + self.uuid = uuid.uuid4() + self.block_size = block_size + self.inode_size = inode_size + self.block_groups = block_groups + self.blocks_per_group = blocks_per_group + self.inodes_per_group = inodes_per_group + self.reserved_inode_count = reserved_inode_count + self.gdt_blocks = count_up(block_groups * GDE_SIZE, block_size) + self.inode_table_blocks_per_group = (inodes_per_group * inode_size) // block_size + self.inode_bitmap_blocks_per_group = count_up(inodes_per_group // 8, block_size) + self.block_bitmap_blocks_per_group = count_up(blocks_per_group // 8, block_size) + self.total_block_count = self.blocks_per_group * self.block_groups + self.total_inode_count = self.inodes_per_group * self.block_groups + self.inode_table_blocks = count_up(self.total_inode_count * inode_size, block_size) + self.inodes = {} + self.superblock_at_block = 2047 // block_size + self.block_ids_per_block = self.block_size // 4 + self.indirect_limits = [12, None, None, None] + self.indirect_blocks_per_level = [1, None, None, None] + for i in range(1,4): + self.indirect_blocks_per_level[i] = self.indirect_blocks_per_level[i-1] * self.block_ids_per_block + self.indirect_limits[i] = self.indirect_limits[i-1] + self.indirect_blocks_per_level[i] + self.block_allocator = Allocator(0, self.total_block_count) + self.inode_allocator = Allocator(1, self.total_inode_count) + self.init_gdt() + # Set the callbacks after GDT has been initialized + self.block_allocator.mark_cb = self.mark_block_cb + self.inode_allocator.mark_cb = self.mark_inode_cb + self.block_allocator.mark_used_all(range(self.superblock_at_block)) + self.inode_allocator.mark_used_all(range(1, self.reserved_inode_count + 1)) + self.root_inode = Inode(self, 2, Inode.TYPE_DIR) + self.gdt[0].directory_inode_count += 1 + self.lost_plus_found = Inode(self, self.inode_allocator.alloc(directory=True), Inode.TYPE_DIR) + lpf_dir = DirWriter(self.lost_plus_found) + lpf_dir.add(self.lost_plus_found.as_dirent('.')) + lpf_dir.add(self.root_inode.as_dirent('..')) + lpf_dir.finish() + + def init_gdt(self): + "Initialize block group descriptor table" + + self.superblock_positions = [] + self.gdt = [] + consumed_blocks_per_group = (1 + self.gdt_blocks + + self.inode_bitmap_blocks_per_group + + self.block_bitmap_blocks_per_group + + self.inode_table_blocks_per_group) + initial_free_blocks = self.blocks_per_group - consumed_blocks_per_group + for bg in range(self.block_groups): + base = bg * self.blocks_per_group + if (bg == 0): + base = self.superblock_at_block + self.superblock_positions.append(1024) + else: + self.superblock_positions.append(base * self.block_size) + self.block_allocator.mark_used_all(range(base, base+consumed_blocks_per_group)) + pos = base + 1 + self.gdt_blocks + gde = xstruct.create(STRUCT_BLOCK_GROUP_DESCRIPTOR) + gde.block_bitmap_block = pos + pos += self.block_bitmap_blocks_per_group + gde.inode_bitmap_block = pos + pos += self.inode_bitmap_blocks_per_group + gde.inode_table_first_block = pos + gde.free_block_count = initial_free_blocks + gde.free_inode_count = self.inodes_per_group + gde.directory_inode_count = 0 + self.gdt.append(gde) + + def mark_block_cb(self, block): + "Called after a block has been allocated" + + self.gdt[block // self.blocks_per_group].free_block_count -= 1 + + def mark_inode_cb(self, index, directory=False): + "Called after an inode has been allocated" + + index -= 1 + gde = self.gdt[index // self.inodes_per_group] + gde.free_inode_count -= 1 + if directory: + gde.directory_inode_count += 1 + + def seek_to_block(self, block, offset=0): + "Seek to offset bytes after the start of the given block" + + if offset < 0 or offset > self.block_size: + raise Exception("Invalid in-block offset") + self.outf.seek(block * self.block_size + offset) + + def seek_to_inode(self, index): + "Seek to the start of the inode structure for the inode number index" + + index -= 1 + if index < 0: + raise Exception("Invalid inode number") + gde = self.gdt[index // self.inodes_per_group] + base_block = gde.inode_table_first_block + offset = (index % self.inodes_per_group) * self.inode_size + block = base_block + (offset // self.block_size) + self.seek_to_block(block, offset % self.block_size) + + def subtree_add(self, inode, parent_inode, dirpath, is_root=False): + "Recursively add files to the filesystem" + + dir_writer = DirWriter(inode) + dir_writer.add(inode.as_dirent('.')) + dir_writer.add(parent_inode.as_dirent('..')) + + if is_root: + dir_writer.add(self.lost_plus_found.as_dirent('lost+found')) + + for item in listdir_items(dirpath): + newidx = self.inode_allocator.alloc(directory = item.is_dir) + if item.is_file: + child_inode = Inode(self, newidx, Inode.TYPE_FILE) + for data in chunks(item, self.block_size): + child_inode.write(data) + elif item.is_dir: + child_inode = Inode(self, newidx, Inode.TYPE_DIR) + self.subtree_add(child_inode, inode, item.path) + + dir_writer.add(child_inode.as_dirent(item.name)) + self.write_inode(child_inode) + + dir_writer.finish() + + def write_inode(self, inode): + "Write inode information into the inode table" + + self.seek_to_inode(inode.index) + self.outf.write(inode.pack()) + + def write_gdt(self): + "Write group descriptor table at the current file position" + + for gde in self.gdt: + data = bytes(gde.pack()) + self.outf.write(data) + self.outf.seek(GDE_SIZE-len(data), os.SEEK_CUR) + + def write_superblock(self, block_group): + "Write superblock at the current position" + + sb = xstruct.create(STRUCT_SUPERBLOCK) + sb.total_inode_count = self.total_inode_count + sb.total_block_count = self.total_block_count + sb.reserved_block_count = 0 + sb.free_block_count = self.block_allocator.free + sb.free_inode_count = self.inode_allocator.free + sb.first_block = self.superblock_at_block + sb.block_size_log2 = num_of_trailing_bin_zeros(self.block_size) - 10 + sb.fragment_size_log2 = sb.block_size_log2 + sb.blocks_per_group = self.blocks_per_group + sb.fragments_per_group = self.blocks_per_group + sb.inodes_per_group = self.inodes_per_group + curtime = int(time.time()) + sb.mount_time = curtime + sb.write_time = curtime + sb.mount_count = 0 + sb.max_mount_count = 21 + sb.magic = 0xEF53 + sb.state = 5 # clean + sb.error_behavior = 1 # continue on errors + sb.rev_minor = 0 + sb.last_check_time = curtime + sb.max_check_interval = 15552000 # 6 months + sb.os = 0 # Linux + sb.rev_major = 1 + sb.first_inode = self.reserved_inode_count + 1 + sb.inode_size = self.inode_size + sb.block_group_number = block_group + sb.features_compatible = 0 + sb.features_incompatible = 2 # filetype + sb.features_read_only = 0 + sb.uuid = self.uuid.bytes_le + sb.volume_name = 'HelenOS rdimage\0' + self.outf.write(bytes(sb.pack())) + + def write_all_metadata(self): + "Write superblocks, block group tables, block and inode bitmaps" + + bbpg = self.blocks_per_group // 8 + bipg = self.inodes_per_group // 8 + def window(arr, index, size): + return arr[index * size:(index + 1) * size] + + for bg_index in xrange(len(self.gdt)): + sbpos = self.superblock_positions[bg_index] + sbblock = (sbpos + 1023) // self.block_size + gde = self.gdt[bg_index] + + self.outf.seek(sbpos) + self.write_superblock(bg_index) + + self.seek_to_block(sbblock+1) + self.write_gdt() + + self.seek_to_block(gde.block_bitmap_block) + self.outf.write(window(self.block_allocator.bitmap, bg_index, bbpg)) + + self.seek_to_block(gde.inode_bitmap_block) + self.outf.write(window(self.inode_allocator.bitmap, bg_index, bipg)) + + def close(self): + "Write all remaining data to the filesystem and close the file" + + self.write_inode(self.root_inode) + self.write_inode(self.lost_plus_found) + self.write_all_metadata() + self.outf.close() + +class Allocator: + def __init__(self, base, count): + self.count = count + self.base = base + self.free = count + self.nextidx = 0 + self.bitmap = array.array('B', [0] * (count // 8)) + self.mark_cb = None + + def __contains__(self, item): + "Check if the item is already used" + + bitidx = item - self.base + return get_bit(self.bitmap[bitidx // 8], bitidx % 8) + + def alloc(self, **options): + "Allocate a new item" + + while self.nextidx < self.count and (self.base + self.nextidx) in self: + self.nextidx += 1 + if self.nextidx == self.count: + raise Exception("No free item available") + item = self.base + self.nextidx + self.nextidx += 1 + self.mark_used(item, **options) + return item + + def mark_used(self, item, **options): + "Mark the specified item as used" + + bitidx = item - self.base + if item in self: + raise Exception("Item already used: " + str(item)) + self.free -= 1 + index = bitidx // 8 + self.bitmap[index] = set_bit(self.bitmap[index], bitidx % 8) + if self.mark_cb: + self.mark_cb(item, **options) + + def mark_used_all(self, items, **options): + "Mark all specified items as used" + + for item in items: + self.mark_used(item, **options) + +class Inode: + TYPE_FILE = 1 + TYPE_DIR = 2 + TYPE2MODE = {TYPE_FILE: 8, TYPE_DIR: 4} + + def __init__(self, fs, index, typ): + self.fs = fs + self.direct = [None] * 12 + self.indirect = [None] * 3 + self.pos = 0 + self.size = 0 + self.blocks = 0 + self.index = index + self.type = typ + self.refcount = 0 + + def as_dirent(self, name): + "Return a DirEntry corresponding to this inode" + self.refcount += 1 + return DirEntry(name, self.index, self.type) + + def new_block(self, data=True): + "Get a new block index from allocator and count it here as belonging to the file" + + block = self.fs.block_allocator.alloc() + self.blocks += 1 + return block + + def get_or_add_block(self, block): + "Get or add a real block to the file" + + if block < 12: + return self.get_or_add_block_direct(block) + return self.get_or_add_block_indirect(block) + + def get_or_add_block_direct(self, block): + "Get or add a real block to the file (direct blocks)" + + if self.direct[block] == None: + self.direct[block] = self.new_block() + return self.direct[block] + + def get_or_add_block_indirect(self, block): + "Get or add a real block to the file (indirect blocks)" + + # Determine the indirection level for the desired block + level = None + for i in range(4): + if block < self.fs.indirect_limits[i]: + level = i + break + + assert level != None + + # Compute offsets for the topmost level + block_offset_in_level = block - self.fs.indirect_limits[level-1]; + if self.indirect[level-1] == None: + self.indirect[level-1] = self.new_block(data = False) + current_block = xstruct.create(STRUCT_BLOCK_REFERENCE) + current_block.block_id = self.indirect[level-1] + offset_in_block = block_offset_in_level // self.fs.indirect_blocks_per_level[level-1] + + # Navigate through other levels + while level > 0: + assert offset_in_block < self.fs.block_ids_per_block + + level -= 1 + + self.fs.seek_to_block(current_block.block_id, offset_in_block*4) + current_block.unpack(self.fs.outf.read(4)) + + if current_block.block_id == 0: + # The block does not exist, so alloc one and write it there + self.fs.outf.seek(-4, os.SEEK_CUR) + current_block.block_id = self.new_block(data=(level==0)) + self.fs.outf.write(current_block.pack()) + + # If we are on the last level, break here as + # there is no next level to visit + if level == 0: + break + + # Visit the next level + block_offset_in_level %= self.fs.indirect_blocks_per_level[level]; + offset_in_block = block_offset_in_level // self.fs.indirect_blocks_per_level[level-1] + + return current_block.block_id + + def do_seek(self): + "Perform a seek to the position indicated by self.pos" + + block = self.pos // self.fs.block_size + real_block = self.get_or_add_block(block) + offset = self.pos % self.fs.block_size + self.fs.seek_to_block(real_block, offset) + + def write(self, data): + "Write a piece of data (arbitrarily long) as the contents of the inode" + + data_pos = 0 + while data_pos < len(data): + bytes_remaining_in_block = self.fs.block_size - (self.pos % self.fs.block_size) + bytes_to_write = min(bytes_remaining_in_block, len(data)-data_pos) + self.do_seek() + self.fs.outf.write(data[data_pos:data_pos + bytes_to_write]) + self.pos += bytes_to_write + data_pos += bytes_to_write + self.size = max(self.pos, self.size) + + def align_size_to_block(self): + "Align the size of the inode up to block size" + + self.size = align_up(self.size, self.fs.block_size) + + def align_pos(self, bytes): + "Align the current position up to bytes boundary" + + self.pos = align_up(self.pos, bytes) + + def pack(self): + "Pack the inode structure and return the result" + + data = xstruct.create(STRUCT_INODE) + data.mode = (Inode.TYPE2MODE[self.type] << 12) + data.mode |= 0x1ff # ugo+rwx + data.user_id = 0 + data.size = self.size & 0xFFFFFFFF + data.group_id = 0 + curtime = int(time.time()) + data.access_time = curtime + data.modification_time = curtime + data.creation_time = curtime + data.deletion_time = 0 + data.usage_count = self.refcount + data.reserved_512_blocks = self.blocks * (self.fs.block_size // 512) + data.flags = 0 + blockconv = lambda x: 0 if x == None else x + data.direct_blocks = map(blockconv, self.direct) + data.indirect_blocks = map(blockconv, self.indirect) + data.version = 0 + data.file_acl = 0 + if self.type == Inode.TYPE_FILE: + data.size_high = (self.size >> 32) + else: + # size_high represents dir_acl in this case + data.size_high = 0 + data.mode_high = 0 + data.user_id_high = 0 + data.group_id_high = 0 + return data.pack() + +class DirEntry: + "Represents a linked list directory entry" + + def __init__(self, name, inode, typ): + self.name = name.encode('UTF-8') + self.inode = inode + self.skip = None + self.type = typ + + def size(self): + "Return size of the entry in bytes" + + return align_up(8 + len(self.name)+1, 4) + + def write(self, inode): + "Write the directory entry into the inode" + + head = xstruct.create(STRUCT_DIR_ENTRY_HEAD) + head.inode = self.inode + head.skip = self.skip + head.name_length = len(self.name) + head.inode_type = self.type + inode.write(head.pack()) + inode.write(self.name+'\0') + inode.align_pos(4) + +class DirWriter: + "Manages writing directory entries into an inode (alignment, etc.)" + + def __init__(self, inode): + self.pos = 0 + self.inode = inode + self.prev_entry = None + self.prev_pos = None + + def prev_write(self): + "Write a previously remembered entry" + + if self.prev_entry: + self.prev_entry.skip = self.pos - self.prev_pos + if self.inode: + self.prev_entry.write(self.inode) + + def add(self, entry): + "Add a directory entry to the directory" + + size = entry.size() + block_size = self.inode.fs.block_size + if align_up(self.pos, block_size) < align_up(self.pos + size, block_size): + self.pos = align_up(self.pos, block_size) + self.prev_write() + self.prev_entry = entry + self.prev_pos = self.pos + self.pos += size + + def finish(self): + "Write the last entry and finish writing the directory contents" + + if not self.inode: + return + self.pos = align_up(self.pos, self.inode.fs.block_size) + self.prev_write() + self.inode.align_size_to_block() + +def subtree_stats(root, block_size): + "Recursively calculate statistics" + + blocks = 0 + inodes = 1 + dir_writer = DirWriter(None) + + for item in listdir_items(root): + inodes += 1 + if item.is_file: + blocks += count_up(item.size, block_size) + elif item.is_dir: + subtree_blocks, subtree_inodes = subtree_stats(item.path, block_size) + blocks += subtree_blocks + inodes += subtree_inodes + + dir_writer.finish() + blocks += count_up(dir_writer.pos, block_size) + return (blocks, inodes) + +def usage(prname): + "Print usage syntax" + print(prname + " ") + +def main(): + if (len(sys.argv) < 4): + usage(sys.argv[0]) + return + + if (not sys.argv[1].isdigit()): + print(" must be a number") + return + + extra_bytes = int(sys.argv[1]) + + path = os.path.abspath(sys.argv[2]) + if (not os.path.isdir(path)): + print(" must be a directory") + return + + block_size = 4096 + inode_size = 128 + reserved_inode_count = 10 + blocks_per_group = 1024 + inodes_per_group = 512 + + blocks, inodes = subtree_stats(path, block_size) + blocks += count_up(extra_bytes, block_size) + inodes += reserved_inode_count + + inodes_per_group = align_up(inodes_per_group, 8) + blocks_per_group = align_up(blocks_per_group, 8) + + inode_table_blocks_per_group = (inodes_per_group * inode_size) // block_size + inode_bitmap_blocks_per_group = count_up(inodes_per_group // 8, block_size) + block_bitmap_blocks_per_group = count_up(blocks_per_group // 8, block_size) + free_blocks_per_group = blocks_per_group + free_blocks_per_group -= inode_table_blocks_per_group + free_blocks_per_group -= inode_bitmap_blocks_per_group + free_blocks_per_group -= block_bitmap_blocks_per_group + free_blocks_per_group -= 10 # one for SB and some reserve for GDT + + block_groups = max(count_up(inodes, inodes_per_group), count_up(blocks, free_blocks_per_group)) + + fs = Filesystem(sys.argv[3], block_groups, blocks_per_group, inodes_per_group, + block_size, inode_size, reserved_inode_count) + + fs.subtree_add(fs.root_inode, fs.root_inode, path, is_root=True) + fs.close() + +if __name__ == '__main__': + main() Index: tools/mkfat.py =================================================================== --- tools/mkfat.py (revision a2271a385d521c53eb7137d1142971451edc6aaa) +++ tools/mkfat.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -37,14 +37,5 @@ import xstruct import array - -exclude_names = set(['.svn', '.bzr']) - -def align_up(size, alignment): - "Return size aligned up to alignment" - - if (size % alignment == 0): - return size - - return ((size // alignment) + 1) * alignment +from imgutil import * def subtree_size(root, cluster_size, dirent_size): @@ -54,13 +45,10 @@ files = 2 - for name in os.listdir(root): - canon = os.path.join(root, name) - - if (os.path.isfile(canon) and (not name in exclude_names)): - size += align_up(os.path.getsize(canon), cluster_size) + for item in listdir_items(root): + if item.is_file: + size += align_up(item.size, cluster_size) files += 1 - - if (os.path.isdir(canon) and (not name in exclude_names)): - size += subtree_size(canon, cluster_size, dirent_size) + elif item.is_dir: + size += subtree_size(item.path, cluster_size, dirent_size) files += 1 @@ -72,14 +60,11 @@ return len(os.listdir(root)) -def write_file(path, outf, cluster_size, data_start, fat, reserved_clusters): +def write_file(item, outf, cluster_size, data_start, fat, reserved_clusters): "Store the contents of a file" - size = os.path.getsize(path) prev = -1 first = 0 - inf = open(path, "rb") - rd = 0; - while (rd < size): + for data in chunks(item, cluster_size): empty_cluster = fat.index(0) fat[empty_cluster] = 0xffff @@ -92,11 +77,8 @@ prev = empty_cluster - data = bytes(inf.read(cluster_size)); outf.seek(data_start + (empty_cluster - reserved_clusters) * cluster_size) outf.write(data) - rd += len(data) - inf.close() - - return first, size + + return first, item.size def write_directory(directory, outf, cluster_size, data_start, fat, reserved_clusters, dirent_size, empty_cluster): @@ -303,14 +285,11 @@ empty_cluster = 0 - for name in os.listdir(root): - canon = os.path.join(root, name) - - if (os.path.isfile(canon) and (not name in exclude_names)): - rv = write_file(canon, outf, cluster_size, data_start, fat, reserved_clusters) - directory.append(create_dirent(name, False, rv[0], rv[1])) - - if (os.path.isdir(canon) and (not name in exclude_names)): - rv = recursion(False, canon, outf, cluster_size, root_start, data_start, fat, reserved_clusters, dirent_size, empty_cluster) - directory.append(create_dirent(name, True, rv[0], rv[1])) + for item in listdir_items(root): + if item.is_file: + rv = write_file(item, outf, cluster_size, data_start, fat, reserved_clusters) + directory.append(create_dirent(item.name, False, rv[0], rv[1])) + elif item.is_dir: + rv = recursion(False, item.path, outf, cluster_size, root_start, data_start, fat, reserved_clusters, dirent_size, empty_cluster) + directory.append(create_dirent(item.name, True, rv[0], rv[1])) if (head): Index: tools/mktmpfs.py =================================================================== --- tools/mktmpfs.py (revision a2271a385d521c53eb7137d1142971451edc6aaa) +++ tools/mktmpfs.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -35,6 +35,5 @@ import os import xstruct - -exclude_names = set(['.svn', '.bzr']) +from imgutil import listdir_items, chunks HEADER = """little: @@ -71,35 +70,26 @@ "Recursive directory walk" - for name in os.listdir(root): - canon = os.path.join(root, name) - - if (os.path.isfile(canon) and (not name in exclude_names)): - size = os.path.getsize(canon) - - dentry = xstruct.create(DENTRY_FILE % len(name)) + for item in listdir_items(root): + if item.is_file: + dentry = xstruct.create(DENTRY_FILE % len(item.name)) dentry.kind = TMPFS_FILE - dentry.fname_len = len(name) - dentry.fname = name.encode('ascii') - dentry.flen = size + dentry.fname_len = len(item.name) + dentry.fname = item.name.encode('ascii') + dentry.flen = item.size outf.write(dentry.pack()) - inf = open(canon, "rb") - rd = 0; - while (rd < size): - data = inf.read(4096); + for data in chunks(item, 4096): outf.write(data) - rd += len(data) - inf.close() - if (os.path.isdir(canon) and (not name in exclude_names)): - dentry = xstruct.create(DENTRY_DIRECTORY % len(name)) + elif item.is_dir: + dentry = xstruct.create(DENTRY_DIRECTORY % len(item.name)) dentry.kind = TMPFS_DIRECTORY - dentry.fname_len = len(name) - dentry.fname = name.encode('ascii') + dentry.fname_len = len(item.name) + dentry.fname = item.name.encode('ascii') outf.write(dentry.pack()) - recursion(canon, outf) + recursion(item.path, outf) dentry = xstruct.create(DENTRY_NONE) Index: tools/xstruct.py =================================================================== --- tools/xstruct.py (revision a2271a385d521c53eb7137d1142971451edc6aaa) +++ tools/xstruct.py (revision b0d309f4768e78374754c1e98aa8d1a4a1eadd6c) @@ -1,4 +1,5 @@ # # Copyright (c) 2008 Martin Decky +# Copyright (c) 2011 Martin Sucha # All rights reserved. # @@ -31,4 +32,29 @@ import struct +import types + +ranges = { + 'B': ((int, long), 0x00, 0xff), + 'H': ((int, long), 0x0000, 0xffff), + 'L': ((int, long), 0x00000000, 0xffffffff), + 'Q': ((int, long), 0x0000000000000000, 0xffffffffffffffff), + 'b': ((int, long), -0x80, 0x7f), + 'h': ((int, long), -0x8000, 0x7fff), + 'l': ((int, long), -0x80000000, 0x7fffffff) , + 'q': ((int, long), -0x8000000000000000, 0x7fffffffffffffff), +} + +def check_range(varname, fmt, value): + if value == None: + raise ValueError('Variable "%s" not set' % varname) + if not fmt in ranges: + return + vartype, varmin, varmax = ranges[fmt] + if not isinstance(value, vartype): + raise ValueError('Variable "%s" is %s but should be %s' % + (varname, str(type(value)), str(vartype))) + if value < varmin or value > varmax: + raise ValueError('Variable "%s" value %s out of range %s..%s' % + (varname, repr(value), repr(varmin), repr(varmax))) class Struct: @@ -38,12 +64,24 @@ def pack(self): args = [] - for variable in self._args_: - if (isinstance(self.__dict__[variable], list)): - for item in self.__dict__[variable]: + for variable, fmt, length in self._args_: + value = self.__dict__[variable] + if isinstance(value, list): + if length != None and length != len(value): + raise ValueError('Variable "%s" length %u does not match %u' % + (variable, len(value), length)) + for index, item in enumerate(value): + check_range(variable + '[' + repr(index) + ']', fmt, item) args.append(item) else: - args.append(self.__dict__[variable]) - + check_range(variable, fmt, value) + args.append(value) return struct.pack(self._format_, *args) + + def unpack(self, data): + values = struct.unpack(self._format_, data) + i = 0 + for variable, fmt, length in self._args_: + self.__dict__[variable] = values[i] + i += 1 def create(definition): @@ -77,11 +115,13 @@ subtokens = token.split("[") + length = None if (len(subtokens) > 1): - format += "%d" % int(subtokens[1].split("]")[0]) + length = int(subtokens[1].split("]")[0]) + format += "%d" % length format += variable inst.__dict__[subtokens[0]] = None - args.append(subtokens[0]) + args.append((subtokens[0], variable, length)) variable = None