Index: uspace/lib/ext4/libext4.h =================================================================== --- uspace/lib/ext4/libext4.h (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4.h (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -40,4 +40,7 @@ #include "libext4_superblock.h" +#include +#define EXT4FS_DBG(format, ...) {if (true) printf("ext4fs: %s: " format "\n", __FUNCTION__, ##__VA_ARGS__);} + #endif Index: uspace/lib/ext4/libext4_directory.c =================================================================== --- uspace/lib/ext4/libext4_directory.c (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_directory.c (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -36,5 +36,175 @@ */ +#include +#include #include "libext4.h" + +static int ext4_directory_iterator_set(ext4_directory_iterator_t *, + uint32_t); + + +uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de) +{ + return uint32_t_le2host(de->inode); +} + +uint16_t ext4_directory_entry_ll_get_entry_length( + ext4_directory_entry_ll_t *de) +{ + return uint16_t_le2host(de->entry_length); +} + +uint16_t ext4_directory_entry_ll_get_name_length( + ext4_superblock_t *sb, ext4_directory_entry_ll_t *de) +{ + if (ext4_superblock_get_rev_level(sb) == 0 && + ext4_superblock_get_minor_rev_level(sb) < 5) { + return ((uint16_t)de->name_length_high) << 8 | + ((uint16_t)de->name_length); + } + return de->name_length; +} + +int ext4_directory_iterator_init(ext4_directory_iterator_t *it, + ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos) +{ + it->inode_ref = inode_ref; + it->fs = fs; + it->current = NULL; + it->current_offset = 0; + it->current_block = NULL; + + return ext4_directory_iterator_seek(it, pos); +} + + +int ext4_directory_iterator_next(ext4_directory_iterator_t *it) +{ + uint16_t skip; + + assert(it->current != NULL); + + skip = ext4_directory_entry_ll_get_entry_length(it->current); + + return ext4_directory_iterator_seek(it, it->current_offset + skip); +} + + +int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos) +{ + int rc; + + uint64_t size; + aoff64_t current_block_idx; + aoff64_t next_block_idx; + uint32_t next_block_phys_idx; + uint32_t block_size; + + size = ext4_inode_get_size(it->fs->superblock, it->inode_ref->inode); + + /* The iterator is not valid until we seek to the desired position */ + it->current = NULL; + + /* Are we at the end? */ + if (pos >= size) { + if (it->current_block) { + rc = block_put(it->current_block); + it->current_block = NULL; + if (rc != EOK) { + return rc; + } + } + + it->current_offset = pos; + return EOK; + } + + block_size = ext4_superblock_get_block_size(it->fs->superblock); + current_block_idx = it->current_offset / block_size; + next_block_idx = pos / block_size; + + /* If we don't have a block or are moving accross block boundary, + * we need to get another block + */ + if (it->current_block == NULL || current_block_idx != next_block_idx) { + if (it->current_block) { + rc = block_put(it->current_block); + it->current_block = NULL; + if (rc != EOK) { + return rc; + } + } + + rc = ext4_filesystem_get_inode_data_block_index(it->fs, + it->inode_ref->inode, next_block_idx, &next_block_phys_idx); + if (rc != EOK) { + return rc; + } + + rc = block_get(&it->current_block, it->fs->device, next_block_phys_idx, + BLOCK_FLAGS_NONE); + if (rc != EOK) { + it->current_block = NULL; + return rc; + } + } + + it->current_offset = pos; + return ext4_directory_iterator_set(it, block_size); +} + +static int ext4_directory_iterator_set(ext4_directory_iterator_t *it, + uint32_t block_size) +{ + uint32_t offset_in_block = it->current_offset % block_size; + + it->current = NULL; + + /* Ensure proper alignment */ + if ((offset_in_block % 4) != 0) { + return EIO; + } + + /* Ensure that the core of the entry does not overflow the block */ + if (offset_in_block > block_size - 8) { + return EIO; + } + + ext4_directory_entry_ll_t *entry = it->current_block->data + offset_in_block; + + /* Ensure that the whole entry does not overflow the block */ + uint16_t length = ext4_directory_entry_ll_get_entry_length(entry); + if (offset_in_block + length > block_size) { + return EIO; + } + + /* Ensure the name length is not too large */ + if (ext4_directory_entry_ll_get_name_length(it->fs->superblock, + entry) > length-8) { + return EIO; + } + + it->current = entry; + return EOK; +} + + +int ext4_directory_iterator_fini(ext4_directory_iterator_t *it) +{ + int rc; + + it->fs = NULL; + it->inode_ref = NULL; + it->current = NULL; + + if (it->current_block) { + rc = block_put(it->current_block); + if (rc != EOK) { + return rc; + } + } + + return EOK; +} Index: uspace/lib/ext4/libext4_directory.h =================================================================== --- uspace/lib/ext4/libext4_directory.h (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_directory.h (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -34,4 +34,40 @@ #define LIBEXT4_LIBEXT4_DIRECTORY_H_ +#include "libext4_filesystem.h" +#include "libext4_inode.h" + +/** + * Linked list directory entry structure + */ +typedef struct ext4_directory_entry_ll { + uint32_t inode; // Inode for the entry + uint16_t entry_length; // Distance to the next directory entry + uint8_t name_length; // Lower 8 bits of name length + union { + uint8_t name_length_high; // Higher 8 bits of name length + uint8_t inode_type; // Type of referenced inode (in rev >= 0.5) + } __attribute__ ((packed)); + uint8_t name; // First byte of name, if present +} __attribute__ ((packed)) ext4_directory_entry_ll_t; + +typedef struct ext4_directory_iterator { + ext4_filesystem_t *fs; + ext4_inode_ref_t *inode_ref; + block_t *current_block; + aoff64_t current_offset; + ext4_directory_entry_ll_t *current; +} ext4_directory_iterator_t; + +extern uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *); +extern uint16_t ext4_directory_entry_ll_get_entry_length( + ext4_directory_entry_ll_t *); +extern uint16_t ext4_directory_entry_ll_get_name_length( + ext4_superblock_t *, ext4_directory_entry_ll_t *); + +extern int ext4_directory_iterator_init(ext4_directory_iterator_t *, + ext4_filesystem_t *, ext4_inode_ref_t *, aoff64_t); +extern int ext4_directory_iterator_next(ext4_directory_iterator_t *); +extern int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t pos); +extern int ext4_directory_iterator_fini(ext4_directory_iterator_t *); #endif Index: uspace/lib/ext4/libext4_filesystem.c =================================================================== --- uspace/lib/ext4/libext4_filesystem.c (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_filesystem.c (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -36,4 +36,5 @@ */ +#include #include #include @@ -144,4 +145,6 @@ ext4_block_group_ref_t **ref) { + EXT4FS_DBG(""); + int rc; aoff64_t block_id; @@ -161,17 +164,31 @@ block_id = ext4_superblock_get_first_data_block(fs->superblock) + 1; + EXT4FS_DBG("block_size = \%d", ext4_superblock_get_block_size(fs->superblock)); + EXT4FS_DBG("descriptors_per_block = \%d", descriptors_per_block); + EXT4FS_DBG("bgid = \%d", bgid); + EXT4FS_DBG("first_data_block: \%d", (uint32_t)block_id); + /* Find the block containing the descriptor we are looking for */ block_id += bgid / descriptors_per_block; offset = (bgid % descriptors_per_block) * EXT4_BLOCK_GROUP_DESCRIPTOR_SIZE; + EXT4FS_DBG("updated block_id: \%d", (uint32_t)block_id); + rc = block_get(&newref->block, fs->device, block_id, 0); if (rc != EOK) { + + EXT4FS_DBG("block_get error: \%d", rc); + free(newref); return rc; } + EXT4FS_DBG("block read"); + newref->block_group = newref->block->data + offset; *ref = newref; + + EXT4FS_DBG("finished"); return EOK; @@ -184,4 +201,6 @@ ext4_inode_ref_t **ref) { + EXT4FS_DBG(""); + int rc; aoff64_t block_id; @@ -202,5 +221,9 @@ } + EXT4FS_DBG("allocated"); + inodes_per_group = ext4_superblock_get_inodes_per_group(fs->superblock); + + EXT4FS_DBG("inodes_per_group_loaded"); /* inode numbers are 1-based, but it is simpler to work with 0-based @@ -211,4 +234,8 @@ offset_in_group = index % inodes_per_group; + EXT4FS_DBG("index: \%d", index); + EXT4FS_DBG("inodes_per_group: \%d", inodes_per_group); + EXT4FS_DBG("bg_id: \%d", block_group); + rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); if (rc != EOK) { @@ -216,8 +243,12 @@ return rc; } + + EXT4FS_DBG("block_group_ref loaded"); inode_table_start = ext4_block_group_get_inode_table_first_block( bg_ref->block_group); + EXT4FS_DBG("inode_table block loaded"); + inode_size = ext4_superblock_get_inode_size(fs->superblock); block_size = ext4_superblock_get_block_size(fs->superblock); @@ -228,4 +259,6 @@ offset_in_block = byte_offset_in_group % block_size; + EXT4FS_DBG("superblock info loaded"); + rc = block_get(&newref->block, fs->device, block_id, 0); if (rc != EOK) { @@ -233,4 +266,6 @@ return rc; } + + EXT4FS_DBG("block got"); newref->inode = newref->block->data + offset_in_block; @@ -242,4 +277,109 @@ *ref = newref; + EXT4FS_DBG("finished"); + + return EOK; +} + +int ext4_filesystem_put_inode_ref(ext4_inode_ref_t *ref) +{ + int rc; + + rc = block_put(ref->block); + free(ref); + + return rc; +} + +int ext4_filesystem_get_inode_data_block_index(ext4_filesystem_t *fs, ext4_inode_t* inode, + aoff64_t iblock, uint32_t* fblock) +{ + int rc; + aoff64_t limits[4]; + uint32_t block_ids_per_block; + aoff64_t blocks_per_level[4]; + uint32_t offset_in_block; + uint32_t current_block; + aoff64_t block_offset_in_level; + int i; + int level; + block_t *block; + + /* Handle simple case when we are dealing with direct reference */ + if (iblock < EXT4_INODE_DIRECT_BLOCKS) { + current_block = ext4_inode_get_direct_block(inode, (uint32_t)iblock); + *fblock = current_block; + return EOK; + } + + /* Compute limits for indirect block levels + * TODO: compute this once when loading filesystem and store in ext2_filesystem_t + */ + block_ids_per_block = ext4_superblock_get_block_size(fs->superblock) / sizeof(uint32_t); + limits[0] = EXT4_INODE_DIRECT_BLOCKS; + blocks_per_level[0] = 1; + for (i = 1; i < 4; i++) { + blocks_per_level[i] = blocks_per_level[i-1] * + block_ids_per_block; + limits[i] = limits[i-1] + blocks_per_level[i]; + } + + /* Determine the indirection level needed to get the desired block */ + level = -1; + for (i = 1; i < 4; i++) { + if (iblock < limits[i]) { + level = i; + break; + } + } + + if (level == -1) { + return EIO; + } + + /* Compute offsets for the topmost level */ + block_offset_in_level = iblock - limits[level-1]; + current_block = ext4_inode_get_indirect_block(inode, level-1); + offset_in_block = block_offset_in_level / blocks_per_level[level-1]; + + /* Navigate through other levels, until we find the block number + * or find null reference meaning we are dealing with sparse file + */ + while (level > 0) { + rc = block_get(&block, fs->device, current_block, 0); + if (rc != EOK) { + return rc; + } + + assert(offset_in_block < block_ids_per_block); + current_block = uint32_t_le2host(((uint32_t*)block->data)[offset_in_block]); + + rc = block_put(block); + if (rc != EOK) { + return rc; + } + + if (current_block == 0) { + /* This is a sparse file */ + *fblock = 0; + return EOK; + } + + level -= 1; + + /* 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 %= blocks_per_level[level]; + offset_in_block = block_offset_in_level / blocks_per_level[level-1]; + } + + *fblock = current_block; + return EOK; } Index: uspace/lib/ext4/libext4_filesystem.h =================================================================== --- uspace/lib/ext4/libext4_filesystem.h (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_filesystem.h (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -108,5 +108,7 @@ extern int ext4_filesystem_get_inode_ref(ext4_filesystem_t *, uint32_t, ext4_inode_ref_t **); - +extern int ext4_filesystem_put_inode_ref(ext4_inode_ref_t *); +extern int ext4_filesystem_get_inode_data_block_index(ext4_filesystem_t *, + ext4_inode_t *, aoff64_t iblock, uint32_t *); #endif Index: uspace/lib/ext4/libext4_inode.c =================================================================== --- uspace/lib/ext4/libext4_inode.c (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_inode.c (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -39,13 +39,32 @@ #include "libext4.h" +uint32_t ext4_inode_get_mode(ext4_superblock_t *sb, ext4_inode_t *inode) +{ + if (ext4_superblock_get_creator_os(sb) == EXT4_SUPERBLOCK_OS_HURD) { + return ((uint32_t)uint16_t_le2host(inode->osd2.hurd2.mode_high)) << 16 | + ((uint32_t)uint16_t_le2host(inode->mode)); + } + return uint16_t_le2host(inode->mode); +} + +bool ext4_inode_is_type(ext4_superblock_t *sb, ext4_inode_t *inode, uint32_t type) +{ + uint32_t mode = ext4_inode_get_mode(sb, inode); + return (mode & EXT4_INODE_MODE_TYPE_MASK) == type; +} + /* -uint32_t ext4_inode_get_mode(ext4_inode_t *inode) uint32_t ext4_inode_get_uid(ext4_inode_t *inode) */ -uint64_t ext4_inode_get_size(ext4_inode_t *inode) +uint64_t ext4_inode_get_size(ext4_superblock_t *sb, ext4_inode_t *inode) { - return ((uint64_t)uint32_t_le2host(inode->size_hi)) << 32 | - ((uint64_t)uint32_t_le2host(inode->size_lo)); + uint32_t major_rev = ext4_superblock_get_rev_level(sb); + + if (major_rev > 0 && ext4_inode_is_type(sb, inode, EXT4_INODE_MODE_FILE)) { + return ((uint64_t)uint32_t_le2host(inode->size_hi)) << 32 | + ((uint64_t)uint32_t_le2host(inode->size_lo)); + } + return uint32_t_le2host(inode->size_lo); } @@ -68,4 +87,16 @@ */ +uint32_t ext4_inode_get_direct_block(ext4_inode_t *inode, uint8_t idx) +{ + assert(idx < EXT4_INODE_DIRECT_BLOCK_COUNT); + return uint32_t_le2host(inode->blocks[idx]); +} + +uint32_t ext4_inode_get_indirect_block(ext4_inode_t *inode, uint8_t idx) +{ + assert(idx < EXT4_INODE_INDIRECT_BLOCK_COUNT); + return uint32_t_le2host(inode->blocks[idx + EXT4_INODE_INDIRECT_BLOCK]); +} + /** * @} Index: uspace/lib/ext4/libext4_inode.h =================================================================== --- uspace/lib/ext4/libext4_inode.h (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_inode.h (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -36,10 +36,13 @@ #include #include +#include "libext4_superblock.h" -#define EXT4_DIRECT_BLOCK_COUNT 12 -#define EXT4_INDIRECT_BLOCK EXT4_DIRECT_BLOCK_COUNT -#define EXT4_DOUBLE_INDIRECT_BLOCK (EXT4_INDIRECT_BLOCK + 1) -#define EXT4_TRIPPLE_INDIRECT_BLOCK (EXT4_DOUBLE_INDIRECT_BLOCK + 1) -#define EXT4_INODE_BLOCKS (EXT4_TRIPPLE_INDIRECT_BLOCK + 1) + +#define EXT4_INODE_DIRECT_BLOCK_COUNT 12 +#define EXT4_INODE_INDIRECT_BLOCK EXT4_INODE_DIRECT_BLOCK_COUNT +#define EXT4_INODE_DOUBLE_INDIRECT_BLOCK (EXT4_INODE_INDIRECT_BLOCK + 1) +#define EXT4_INODE_TRIPPLE_INDIRECT_BLOCK (EXT4_INODE_DOUBLE_INDIRECT_BLOCK + 1) +#define EXT4_INODE_BLOCKS (EXT4_INODE_TRIPPLE_INDIRECT_BLOCK + 1) +#define EXT4_INODE_INDIRECT_BLOCK_COUNT (EXT4_INODE_BLOCKS - EXT4_INODE_DIRECT_BLOCK_COUNT) /* @@ -64,5 +67,26 @@ uint32_t size_hi; uint32_t obso_faddr; // Obsoleted fragment address - uint32_t unused_osd2[3]; // OS dependent - not used in HelenOS + union { + struct { + uint16_t blocks_high; /* were l_i_reserved1 */ + uint16_t file_acl_high; + uint16_t uid_high; /* these 2 fields */ + uint16_t gid_high; /* were reserved2[0] */ + uint32_t reserved2; + } linux2; + struct { + uint16_t reserved1; /* Obsoleted fragment number/size which are removed in ext4 */ + uint16_t mode_high; + uint16_t uid_high; + uint16_t gid_high; + uint32_t author; + } hurd2; + struct { + uint16_t reserved1; /* Obsoleted fragment number/size which are removed in ext4 */ + uint16_t file_acl_high; + uint32_t reserved2[2]; + } masix2; + } __attribute__ ((packed)) osd2; + uint16_t extra_isize; uint16_t pad1; @@ -75,4 +99,12 @@ } __attribute__ ((packed)) ext4_inode_t; +#define EXT4_INODE_MODE_FIFO 0x1000 +#define EXT4_INODE_MODE_CHARDEV 0x2000 +#define EXT4_INODE_MODE_DIRECTORY 0x4000 +#define EXT4_INODE_MODE_BLOCKDEV 0x6000 +#define EXT4_INODE_MODE_FILE 0x8000 +#define EXT4_INODE_MODE_SOFTLINK 0xA000 +#define EXT4_INODE_MODE_SOCKET 0xC000 +#define EXT4_INODE_MODE_TYPE_MASK 0xF000 #define EXT4_INODE_ROOT_INDEX 2 @@ -84,9 +116,11 @@ } ext4_inode_ref_t; + +extern uint32_t ext4_inode_get_mode(ext4_superblock_t *, ext4_inode_t *); +extern bool ext4_inode_is_type(ext4_superblock_t *, ext4_inode_t *, uint32_t); /* -extern uint16_t ext4_inode_get_mode(ext4_inode_t *); extern uint32_t ext4_inode_get_uid(ext4_inode_t *); */ -extern uint64_t ext4_inode_get_size(ext4_inode_t *); +extern uint64_t ext4_inode_get_size(ext4_superblock_t *, ext4_inode_t *); /* extern uint32_t ext4_inode_get_access_time(ext4_inode_t *); @@ -101,4 +135,7 @@ extern uint32_t ext4_inode_get_flags(ext4_inode_t *); */ + +uint32_t ext4_inode_get_direct_block(ext4_inode_t *, uint8_t); +uint32_t ext4_inode_get_indirect_block(ext4_inode_t *, uint8_t); /* Index: uspace/lib/ext4/libext4_superblock.h =================================================================== --- uspace/lib/ext4/libext4_superblock.h (revision 3712434180942faca7a9305462e63eaffa18debb) +++ uspace/lib/ext4/libext4_superblock.h (revision 9b9d37bb7640f27fb362f617f494669ddd3490d3) @@ -140,4 +140,7 @@ #define EXT4_SUPERBLOCK_SIZE 1024 #define EXT4_SUPERBLOCK_OFFSET 1024 + +#define EXT4_SUPERBLOCK_OS_LINUX 0 +#define EXT4_SUPERBLOCK_OS_HURD 1 extern uint32_t ext4_superblock_get_inodes_count(ext4_superblock_t *);