Index: uspace/lib/ext4/Makefile =================================================================== --- uspace/lib/ext4/Makefile (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/Makefile (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,48 @@ +# +# Copyright (c) 2011 Frantisek Princ +# 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. +# + +USPACE_PREFIX = ../.. +LIBRARY = libext4 +EXTRA_CFLAGS = -I$(LIBBLOCK_PREFIX) -I$(LIBPOSIX_PREFIX) +LIBS = $(LIBBLOCK_PREFIX)/libblock.a $(LIBPOSIX_PREFIX)/libposix.a + +SOURCES = \ + libext4_balloc.c \ + libext4_bitmap.c \ + libext4_block_group.c \ + libext4_directory.c \ + libext4_directory_index.c \ + libext4_extent.c \ + libext4_filesystem.c \ + libext4_hash.c \ + libext4_ialloc.c \ + libext4_inode.c \ + libext4_superblock.c + + +include $(USPACE_PREFIX)/Makefile.common Index: uspace/lib/ext4/libext4.h =================================================================== --- uspace/lib/ext4/libext4.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,56 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_H_ +#define LIBEXT4_LIBEXT4_H_ + +#include "libext4_balloc.h" +#include "libext4_bitmap.h" +#include "libext4_block_group.h" +#include "libext4_directory.h" +#include "libext4_directory_index.h" +#include "libext4_extent.h" +#include "libext4_filesystem.h" +#include "libext4_hash.h" +#include "libext4_ialloc.h" +#include "libext4_inode.h" +#include "libext4_superblock.h" +#include "libext4_types.h" + +#include +#define EXT4FS_DBG(format, ...) {if (true) printf("ext4fs: %s: " format "\n", __FUNCTION__, ##__VA_ARGS__);} + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_balloc.c =================================================================== --- uspace/lib/ext4/libext4_balloc.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_balloc.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,489 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_balloc.c + * @brief Physical block allocator. + */ + +#include +#include +#include "libext4.h" + +static uint32_t ext4_balloc_blockaddr2_index_in_group(ext4_superblock_t *sb, + uint32_t block_addr) +{ + uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb); + uint32_t first_block = ext4_superblock_get_first_data_block(sb); + + // First block == 0 or 1 + if (first_block == 0) { + return block_addr % blocks_per_group; + } else { + return (block_addr - 1) % blocks_per_group; + } +} + +static uint32_t ext4_balloc_index_in_group2blockaddr(ext4_superblock_t *sb, + uint32_t index, uint32_t bgid) +{ + uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb); + + if (ext4_superblock_get_first_data_block(sb) == 0) { + return bgid * blocks_per_group + index; + } else { + return bgid * blocks_per_group + index + 1; + } + +} + +static uint32_t ext4_balloc_get_bgid_of_block(ext4_superblock_t *sb, + uint32_t block_addr) +{ + uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb); + uint32_t first_block = ext4_superblock_get_first_data_block(sb); + + // First block == 0 or 1 + if (first_block == 0) { + return block_addr / blocks_per_group; + } else { + return (block_addr - 1) / blocks_per_group; + } +} + + +int ext4_balloc_free_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t block_addr) +{ + int rc; + + uint32_t block_group = ext4_balloc_get_bgid_of_block(fs->superblock, block_addr); + uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(fs->superblock, block_addr); + + ext4_block_group_ref_t *bg_ref; + rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); + if (rc != EOK) { + EXT4FS_DBG("error in loading bg_ref \%d", rc); + return rc; + } + + uint32_t bitmap_block_addr = ext4_block_group_get_block_bitmap( + bg_ref->block_group, fs->superblock); + block_t *bitmap_block; + rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0); + if (rc != EOK) { + EXT4FS_DBG("error in loading bitmap \%d", rc); + return rc; + } + + ext4_bitmap_free_bit(bitmap_block->data, index_in_group); + bitmap_block->dirty = true; + + rc = block_put(bitmap_block); + if (rc != EOK) { + // Error in saving bitmap + ext4_filesystem_put_block_group_ref(bg_ref); + EXT4FS_DBG("error in saving bitmap \%d", rc); + return rc; + } + + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + + // Update superblock free blocks count + uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(fs->superblock); + sb_free_blocks--; + ext4_superblock_set_free_blocks_count(fs->superblock, sb_free_blocks); + + // Update inode blocks count + uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode); + ino_blocks -= block_size / EXT4_INODE_BLOCK_SIZE; + ext4_inode_set_blocks_count(fs->superblock, inode_ref->inode, ino_blocks); + inode_ref->dirty = true; + + // Update block group free blocks count + uint32_t free_blocks = ext4_block_group_get_free_blocks_count( + bg_ref->block_group, fs->superblock); + free_blocks++; + ext4_block_group_set_free_blocks_count(bg_ref->block_group, + fs->superblock, free_blocks); + bg_ref->dirty = true; + + rc = ext4_filesystem_put_block_group_ref(bg_ref); + if (rc != EOK) { + EXT4FS_DBG("error in saving bg_ref \%d", rc); + // TODO error + return rc; + } + + return EOK; +} + +static uint32_t ext4_balloc_get_first_data_block_in_group( + ext4_superblock_t *sb, ext4_block_group_t *bg, uint32_t bgid) +{ + uint32_t block_group_count = ext4_superblock_get_block_group_count(sb); + uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block( + bg, sb); + uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb); + uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); + uint32_t block_size = ext4_superblock_get_block_size(sb); + uint32_t inode_table_bytes; + + if (bgid < block_group_count - 1) { + inode_table_bytes = inodes_per_group * inode_table_item_size; + } else { + // last block group could be smaller + uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb); + inode_table_bytes = + (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) + * inode_table_item_size; + } + + uint32_t inode_table_blocks = inode_table_bytes / block_size; + + if (inode_table_bytes % block_size) { + inode_table_blocks++; + } + + return inode_table_first_block + inode_table_blocks; +} + + +static uint32_t ext4_balloc_find_goal(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref) +{ + int rc; + uint32_t goal = 0; + + uint64_t inode_size = ext4_inode_get_size(fs->superblock, inode_ref->inode); + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + uint32_t inode_block_count = inode_size / block_size; + + if (inode_size % block_size != 0) { + inode_block_count++; + } + + if (inode_block_count > 0) { + // TODO check retval + ext4_filesystem_get_inode_data_block_index(fs, inode_ref, inode_block_count - 1, &goal); + + // TODO + // If goal == 0 -> SPARSE file !!! + + goal++; + return goal; + } + + // Identify block group of inode + uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(fs->superblock); + uint32_t block_group = (inode_ref->index - 1) / inodes_per_group; + block_size = ext4_superblock_get_block_size(fs->superblock); + + ext4_block_group_ref_t *bg_ref; + rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); + if (rc != EOK) { + return 0; + } + + uint32_t block_group_count = ext4_superblock_get_block_group_count(fs->superblock); + uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block( + bg_ref->block_group, fs->superblock); + uint16_t inode_table_item_size = ext4_superblock_get_inode_size(fs->superblock); + uint32_t inode_table_bytes; + + if (block_group < block_group_count - 1) { + inode_table_bytes = inodes_per_group * inode_table_item_size; + } else { + // last block group could be smaller + uint32_t inodes_count_total = ext4_superblock_get_inodes_count(fs->superblock); + inode_table_bytes = + (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) + * inode_table_item_size; + } + + uint32_t inode_table_blocks = inode_table_bytes / block_size; + + if (inode_table_bytes % block_size) { + inode_table_blocks++; + } + + goal = inode_table_first_block + inode_table_blocks; + + ext4_filesystem_put_block_group_ref(bg_ref); + + return goal; +} + +int ext4_balloc_alloc_block(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, uint32_t *fblock) +{ + int rc; + uint32_t allocated_block = 0; + + uint32_t bitmap_block_addr; + block_t *bitmap_block; + uint32_t rel_block_idx = 0; + + // Find GOAL + uint32_t goal = ext4_balloc_find_goal(fs, inode_ref); + if (goal == 0) { + // TODO + EXT4FS_DBG("ERRORR (goal == 0)"); + return ENOSPC; + } + + // Load block group number for goal and relative index + uint32_t block_group = ext4_balloc_get_bgid_of_block(fs->superblock, goal); + uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(fs->superblock, goal); + + + ext4_block_group_ref_t *bg_ref; + rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); + if (rc != EOK) { + EXT4FS_DBG("initial BG ref not loaded"); + return rc; + } + + uint32_t first_in_group = + ext4_balloc_get_first_data_block_in_group(fs->superblock, + bg_ref->block_group, block_group); + + uint32_t first_in_group_index = ext4_balloc_blockaddr2_index_in_group( + fs->superblock, first_in_group); + + if (index_in_group < first_in_group_index) { + index_in_group = first_in_group_index; + } + + // Load bitmap + bitmap_block_addr = ext4_block_group_get_block_bitmap(bg_ref->block_group, + fs->superblock); + + rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0); + if (rc != EOK) { + ext4_filesystem_put_block_group_ref(bg_ref); + EXT4FS_DBG("initial bitmap not loaded"); + return rc; + } + + // Check if goal is free + if (ext4_bitmap_is_free_bit(bitmap_block->data, index_in_group)) { + ext4_bitmap_set_bit(bitmap_block->data, index_in_group); + bitmap_block->dirty = true; + rc = block_put(bitmap_block); + if (rc != EOK) { + // TODO error + EXT4FS_DBG("goal check: error in saving initial bitmap \%d", rc); + ext4_filesystem_put_block_group_ref(bg_ref); + return rc; + } + + allocated_block = goal; + goto success; + + } + + uint32_t blocks_in_group = ext4_superblock_get_blocks_in_group(fs->superblock, block_group); + + uint32_t end_idx = (index_in_group + 63) & ~63; + if (end_idx > blocks_in_group) { + end_idx = blocks_in_group; + } + + // Try to find free block near to goal + for (uint32_t tmp_idx = index_in_group + 1; tmp_idx < end_idx; ++tmp_idx) { + if (ext4_bitmap_is_free_bit(bitmap_block->data, tmp_idx)) { + + ext4_bitmap_set_bit(bitmap_block->data, tmp_idx); + bitmap_block->dirty = true; + rc = block_put(bitmap_block); + if (rc != EOK) { + // TODO error + EXT4FS_DBG("near blocks: error in saving initial bitmap \%d", rc); + } + + allocated_block = ext4_balloc_index_in_group2blockaddr( + fs->superblock, tmp_idx, block_group); + + goto success; + } + + } + + // Find free BYTE in bitmap + rc = ext4_bitmap_find_free_byte_and_set_bit(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group); + if (rc == EOK) { + bitmap_block->dirty = true; + rc = block_put(bitmap_block); + if (rc != EOK) { + // TODO error + EXT4FS_DBG("free byte: error in saving initial bitmap \%d", rc); + } + + allocated_block = ext4_balloc_index_in_group2blockaddr( + fs->superblock, rel_block_idx, block_group); + + goto success; + } + + // Find free bit in bitmap + rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group); + if (rc == EOK) { + bitmap_block->dirty = true; + rc = block_put(bitmap_block); + if (rc != EOK) { + // TODO error + EXT4FS_DBG("free bit: error in saving initial bitmap \%d", rc); + } + + allocated_block = ext4_balloc_index_in_group2blockaddr( + fs->superblock, rel_block_idx, block_group); + + goto success; + } + + // No free block found yet + block_put(bitmap_block); + ext4_filesystem_put_block_group_ref(bg_ref); + + // Try other block groups + uint32_t block_group_count = ext4_superblock_get_block_group_count(fs->superblock); + + uint32_t bgid = (block_group + 1) % block_group_count; + uint32_t count = block_group_count; + + while (count > 0) { + rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref); + if (rc != EOK) { + EXT4FS_DBG("errrrrrrrrrrr"); + return rc; + } + + // Load bitmap + bitmap_block_addr = ext4_block_group_get_block_bitmap( + bg_ref->block_group, fs->superblock); + + rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0); + if (rc != EOK) { + ext4_filesystem_put_block_group_ref(bg_ref); + EXT4FS_DBG("errrrrrrrrrr"); + return rc; + } + + first_in_group = ext4_balloc_get_first_data_block_in_group( + fs->superblock, bg_ref->block_group, bgid); + index_in_group = ext4_balloc_blockaddr2_index_in_group(fs->superblock, + first_in_group); + blocks_in_group = ext4_superblock_get_blocks_in_group(fs->superblock, bgid); + + first_in_group_index = ext4_balloc_blockaddr2_index_in_group( + fs->superblock, first_in_group); + + if (index_in_group < first_in_group_index) { + index_in_group = first_in_group_index; + } + + + rc = ext4_bitmap_find_free_byte_and_set_bit(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group); + if (rc == EOK) { + bitmap_block->dirty = true; + rc = block_put(bitmap_block); + if (rc != EOK) { + // TODO error + EXT4FS_DBG("error in saving bitmap \%d", rc); + } + + allocated_block = ext4_balloc_index_in_group2blockaddr( + fs->superblock, rel_block_idx, bgid); + + goto success; + } + + // Find free bit in bitmap + rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group); + if (rc == EOK) { + bitmap_block->dirty = true; + rc = block_put(bitmap_block); + if (rc != EOK) { + // TODO error + EXT4FS_DBG("error in saving bitmap \%d", rc); + } + + allocated_block = ext4_balloc_index_in_group2blockaddr( + fs->superblock, rel_block_idx, bgid); + + goto success; + } + + + // Next group + block_put(bitmap_block); + ext4_filesystem_put_block_group_ref(bg_ref); + bgid = (bgid + 1) % block_group_count; + count--; + } + + return ENOSPC; + +success: + ; // Empty command - because of syntax + + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + + // Update superblock free blocks count + uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(fs->superblock); + sb_free_blocks--; + ext4_superblock_set_free_blocks_count(fs->superblock, sb_free_blocks); + + // Update inode blocks (different block size!) count + + uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode); + ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE; + ext4_inode_set_blocks_count(fs->superblock, inode_ref->inode, ino_blocks); + inode_ref->dirty = true; + + // Update block group free blocks count + uint32_t bg_free_blocks = ext4_block_group_get_free_blocks_count( + bg_ref->block_group, fs->superblock); + bg_free_blocks--; + ext4_block_group_set_free_blocks_count(bg_ref->block_group, + fs->superblock, bg_free_blocks); + bg_ref->dirty = true; + + ext4_filesystem_put_block_group_ref(bg_ref); + + *fblock = allocated_block; + return EOK; +} + + +/** + * @} + */ Index: uspace/lib/ext4/libext4_balloc.h =================================================================== --- uspace/lib/ext4/libext4_balloc.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_balloc.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_BALLOC_H_ +#define LIBEXT4_LIBEXT4_BALLOC_H_ + +#include +#include "libext4_types.h" + +extern int ext4_balloc_free_block(ext4_filesystem_t *, + ext4_inode_ref_t *, uint32_t); +extern int ext4_balloc_alloc_block(ext4_filesystem_t *, + ext4_inode_ref_t *, uint32_t *); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_bitmap.c =================================================================== --- uspace/lib/ext4/libext4_bitmap.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_bitmap.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,158 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_bitmap.c + * @brief Ext4 bitmap operations. + */ + +#include +#include +#include +#include "libext4.h" + +void ext4_bitmap_free_bit(uint8_t *bitmap, uint32_t index) +{ + uint32_t byte_index = index / 8; + uint32_t bit_index = index % 8; + + uint8_t *target = bitmap + byte_index; + + *target &= ~ (1 << bit_index); +} + +void ext4_bitmap_set_bit(uint8_t *bitmap, uint32_t index) +{ + uint32_t byte_index = index / 8; + uint32_t bit_index = index % 8; + + uint8_t *target = bitmap + byte_index; + + *target |= 1 << bit_index; +} + +bool ext4_bitmap_is_free_bit(uint8_t *bitmap, uint32_t index) +{ + uint32_t byte_index = index / 8; + uint32_t bit_index = index % 8; + + uint8_t *target = bitmap + byte_index; + + if (*target & (1 << bit_index)) { + return false; + } else { + return true; + } + +} + +int ext4_bitmap_find_free_byte_and_set_bit(uint8_t *bitmap, uint32_t start, uint32_t *index, uint32_t max) +{ + uint32_t idx; + if (start % 8) { + idx = start + (8 - (start % 8)); + } else { + idx = start; + } + + uint8_t *pos = bitmap + (idx / 8); + + while (idx < max) { + + if (*pos == 0) { + *pos |= 1; + + *index = idx; + return EOK; + } + + idx += 8; + ++pos; + } + + return ENOSPC; +} + +int ext4_bitmap_find_free_bit_and_set(uint8_t *bitmap, uint32_t start_idx, + uint32_t *index, uint32_t max) +{ + uint8_t *pos = bitmap + (start_idx / 8); + uint32_t idx = start_idx; + bool byte_part = false; + + // Check the rest of byte + while ((idx % 8) != 0) { + byte_part = true; + + if ((*pos & (1 << (idx % 8))) == 0) { + *pos |= (1 << (idx % 8)); + *index = idx; + return EOK; + } + + ++idx; + } + + if (byte_part) { + ++pos; + } + + while (idx < max) { + + if ((*pos & 255) != 255) { + // free bit found + break; + } + + idx += 8; + ++pos; + } + + + if (idx < max) { + for (uint8_t i = 0; i < 8; ++i) { + if ((*pos & (1 << i)) == 0) { + // free bit found + *pos |= (1 << i); + *index = idx; + return EOK; + } + idx++; + } + } + + return ENOSPC; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_bitmap.h =================================================================== --- uspace/lib/ext4/libext4_bitmap.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_bitmap.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_BITMAP_H_ +#define LIBEXT4_LIBEXT4_BITMAP_H_ + +#include + +extern void ext4_bitmap_free_bit(uint8_t *, uint32_t); +extern void ext4_bitmap_set_bit(uint8_t *, uint32_t); +extern bool ext4_bitmap_is_free_bit(uint8_t *, uint32_t); +extern int ext4_bitmap_find_free_byte_and_set_bit(uint8_t *, uint32_t, + uint32_t *, uint32_t); +extern int ext4_bitmap_find_free_bit_and_set(uint8_t *, uint32_t, + uint32_t *, uint32_t); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_block_group.c =================================================================== --- uspace/lib/ext4/libext4_block_group.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_block_group.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,204 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_block_group.c + * @brief Ext4 block group structure operations + */ + +#include +#include "libext4.h" + +uint64_t ext4_block_group_get_block_bitmap(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint64_t)uint32_t_le2host(bg->block_bitmap_hi) << 32) | + uint32_t_le2host(bg->block_bitmap_lo); + } else { + return uint32_t_le2host(bg->block_bitmap_lo); + } +} + +void ext4_block_group_set_block_bitmap(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint64_t block_bitmap) +{ + bg->block_bitmap_lo = host2uint32_t_le((block_bitmap << 32) >> 32); + + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->block_bitmap_hi = host2uint32_t_le(block_bitmap >> 32); + } +} + +uint64_t ext4_block_group_get_inode_bitmap(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint64_t)uint32_t_le2host(bg->inode_bitmap_hi) << 32) | + uint32_t_le2host(bg->inode_bitmap_lo); + } else { + return uint32_t_le2host(bg->inode_bitmap_lo); + } + +} + +void ext4_block_group_set_inode_bitmap(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint64_t inode_bitmap) +{ + bg->inode_bitmap_lo = host2uint32_t_le((inode_bitmap << 32) >> 32); + + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->inode_bitmap_hi = host2uint32_t_le(inode_bitmap >> 32); + } +} + +uint64_t ext4_block_group_get_inode_table_first_block(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint64_t)uint32_t_le2host(bg->inode_table_first_block_hi) << 32) | + uint32_t_le2host(bg->inode_table_first_block_lo); + } else { + return uint32_t_le2host(bg->inode_table_first_block_lo); + } +} + +void ext4_block_group_set_inode_table_first_block(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint64_t ino_tbl_first) +{ + bg->inode_table_first_block_lo = host2uint32_t_le((ino_tbl_first << 32) >> 32); + + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->inode_table_first_block_hi = host2uint32_t_le(ino_tbl_first >> 32); + } +} + +uint32_t ext4_block_group_get_free_blocks_count(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint32_t)uint16_t_le2host(bg->free_blocks_count_hi) << 16) | + uint16_t_le2host(bg->free_blocks_count_lo); + } else { + return uint16_t_le2host(bg->free_blocks_count_lo); + } +} + +void ext4_block_group_set_free_blocks_count(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint32_t value) +{ + bg->free_blocks_count_lo = host2uint16_t_le((value << 16) >> 16); + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->free_blocks_count_hi = host2uint16_t_le(value >> 16); + } +} + +uint32_t ext4_block_group_get_free_inodes_count(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint32_t)uint16_t_le2host(bg->free_inodes_count_hi) << 16) | + uint16_t_le2host(bg->free_inodes_count_lo); + } else { + return uint16_t_le2host(bg->free_inodes_count_lo); + } +} + +void ext4_block_group_set_free_inodes_count(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint32_t value) +{ + bg->free_inodes_count_lo = host2uint16_t_le((value << 16) >> 16); + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->free_inodes_count_hi = host2uint16_t_le(value >> 16); + } +} + + +uint32_t ext4_block_group_get_used_dirs_count(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint32_t)uint16_t_le2host(bg->used_dirs_count_hi) << 16) | + uint16_t_le2host(bg->used_dirs_count_lo); + } else { + return uint16_t_le2host(bg->used_dirs_count_lo); + } +} + +void ext4_block_group_set_used_dirs_count(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint32_t count) +{ + bg->used_dirs_count_lo = host2uint16_t_le((count << 16) >> 16); + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->used_dirs_count_hi = host2uint16_t_le(count >> 16); + } +} + +uint16_t ext4_block_group_get_flags(ext4_block_group_t *bg) +{ + return uint16_t_le2host(bg->flags); +} + +uint32_t ext4_block_group_get_itable_unused(ext4_block_group_t *bg, + ext4_superblock_t *sb) +{ + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + return ((uint32_t)uint16_t_le2host(bg->itable_unused_hi) << 16) | + uint16_t_le2host(bg->itable_unused_lo); + } else { + return uint16_t_le2host(bg->itable_unused_lo); + } +} + +void ext4_block_group_set_itable_unused(ext4_block_group_t *bg, + ext4_superblock_t *sb, uint32_t value) +{ + bg->itable_unused_lo = host2uint16_t_le((value << 16) >> 16); + if (ext4_superblock_get_desc_size(sb) > EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + bg->itable_unused_hi = host2uint16_t_le(value >> 16); + } + +} + +uint16_t ext4_block_group_get_checksum(ext4_block_group_t *bg) +{ + return uint16_t_le2host(bg->checksum); +} + +void ext4_block_group_set_checksum(ext4_block_group_t *bg, uint16_t checksum) +{ + bg->checksum = host2uint16_t_le(checksum); +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_block_group.h =================================================================== --- uspace/lib/ext4/libext4_block_group.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_block_group.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,79 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_BLOCK_GROUP_H_ +#define LIBEXT4_LIBEXT4_BLOCK_GROUP_H_ + +#include +#include +#include "libext4_types.h" + +extern uint64_t ext4_block_group_get_block_bitmap(ext4_block_group_t *, + ext4_superblock_t *); +extern void ext4_block_group_set_block_bitmap(ext4_block_group_t *, + ext4_superblock_t *, uint64_t); +extern uint64_t ext4_block_group_get_inode_bitmap(ext4_block_group_t *, + ext4_superblock_t *); +extern void ext4_block_group_set_inode_bitmap(ext4_block_group_t *, + ext4_superblock_t *, uint64_t); +extern uint64_t ext4_block_group_get_inode_table_first_block( + ext4_block_group_t *, ext4_superblock_t *); +extern void ext4_block_group_set_inode_table_first_block( + ext4_block_group_t *, ext4_superblock_t *, uint64_t); +extern uint32_t ext4_block_group_get_free_blocks_count(ext4_block_group_t *, + ext4_superblock_t *); +extern void ext4_block_group_set_free_blocks_count(ext4_block_group_t *, + ext4_superblock_t *, uint32_t); +extern uint32_t ext4_block_group_get_free_inodes_count(ext4_block_group_t *, + ext4_superblock_t *); +extern void ext4_block_group_set_free_inodes_count(ext4_block_group_t *, + ext4_superblock_t *, uint32_t); +extern void ext4_block_group_set_free_inodes_count(ext4_block_group_t *, + ext4_superblock_t *, uint32_t); +extern uint32_t ext4_block_group_get_used_dirs_count(ext4_block_group_t *, + ext4_superblock_t *); +extern void ext4_block_group_set_used_dirs_count(ext4_block_group_t *, + ext4_superblock_t *, uint32_t); +extern uint16_t ext4_block_group_get_flags(ext4_block_group_t *); +extern void ext4_block_group_set_flags(ext4_block_group_t *, uint16_t); +extern uint32_t ext4_block_group_get_itable_unused(ext4_block_group_t *, + ext4_superblock_t *); +extern void ext4_block_group_set_itable_unused(ext4_block_group_t *, + ext4_superblock_t *, uint32_t); +extern uint16_t ext4_block_group_get_checksum(ext4_block_group_t *); +extern void ext4_block_group_set_checksum(ext4_block_group_t *, uint16_t); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_directory.c =================================================================== --- uspace/lib/ext4/libext4_directory.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_directory.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,630 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_directory.c + * @brief Ext4 directory structure operations. + */ + +#include +#include +#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); +} + +void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *de, + uint32_t inode) +{ + de->inode = host2uint32_t_le(inode); +} + +uint16_t ext4_directory_entry_ll_get_entry_length( + ext4_directory_entry_ll_t *de) +{ + return uint16_t_le2host(de->entry_length); +} + +void ext4_directory_entry_ll_set_entry_length(ext4_directory_entry_ll_t *de, + uint16_t length) +{ + de->entry_length = host2uint16_t_le(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; + +} + +void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *sb, + ext4_directory_entry_ll_t *de, uint16_t length) +{ + de->name_length = (length << 8) >> 8; + + if (ext4_superblock_get_rev_level(sb) == 0 && + ext4_superblock_get_minor_rev_level(sb) < 5) { + + de->name_length_high = length >> 8; + } +} + +uint8_t ext4_directory_entry_ll_get_inode_type( + 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 de->inode_type; + } + + return EXT4_DIRECTORY_FILETYPE_UNKNOWN; + +} + +void ext4_directory_entry_ll_set_inode_type( + ext4_superblock_t *sb, ext4_directory_entry_ll_t *de, uint8_t type) +{ + if (ext4_superblock_get_rev_level(sb) > 0 || + ext4_superblock_get_minor_rev_level(sb) >= 5) { + + de->inode_type = type; + } + + // else do nothing + +} + +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 = 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; + } + + uint32_t block_size = ext4_superblock_get_block_size(it->fs->superblock); + aoff64_t current_block_idx = it->current_offset / block_size; + aoff64_t 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; + } + } + + uint32_t next_block_phys_idx; + rc = ext4_filesystem_get_inode_data_block_index(it->fs, + it->inode_ref, 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) +{ + + it->current = NULL; + + uint32_t offset_in_block = it->current_offset % block_size; + + /* 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; +} + +int ext4_directory_append_block(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, uint32_t *fblock, uint32_t *iblock) +{ + int rc; + + // Compute next block index and allocate data block + uint64_t inode_size = ext4_inode_get_size(fs->superblock, inode_ref->inode); + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + + assert(inode_size % block_size == 0); + + // Logical blocks are numbered from 0 + uint32_t new_block_idx = inode_size / block_size; + + uint32_t phys_block; + rc = ext4_balloc_alloc_block(fs, inode_ref, &phys_block); + if (rc != EOK) { + return rc; + } + + rc = ext4_filesystem_set_inode_data_block_index(fs, inode_ref, new_block_idx, phys_block); + if (rc != EOK) { + ext4_balloc_free_block(fs, inode_ref, phys_block); + return rc; + } + + ext4_inode_set_size(inode_ref->inode, inode_size + block_size); + + inode_ref->dirty = true; + + *fblock = phys_block; + *iblock = new_block_idx; + return EOK; +} + +void ext4_directory_write_entry(ext4_superblock_t *sb, + ext4_directory_entry_ll_t *entry, uint16_t entry_len, + ext4_inode_ref_t *child, const char *name, size_t name_len) +{ + ext4_directory_entry_ll_set_inode(entry, child->index); + ext4_directory_entry_ll_set_entry_length(entry, entry_len); + ext4_directory_entry_ll_set_name_length(sb, entry, name_len); + + if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY)) { + ext4_directory_entry_ll_set_inode_type( + sb, entry, EXT4_DIRECTORY_FILETYPE_DIR); + } else { + ext4_directory_entry_ll_set_inode_type( + sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE); + } + memcpy(entry->name, name, name_len); +} + +int ext4_directory_add_entry(ext4_filesystem_t *fs, ext4_inode_ref_t * parent, + const char *name, ext4_inode_ref_t *child) +{ + int rc; + + EXT4FS_DBG("adding entry to directory \%u [ino = \%u, name = \%s]", parent->index, child->index, name); + + // Index adding (if allowed) + if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) && + ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) { + + rc = ext4_directory_dx_add_entry(fs, parent, child, name); + + // Check if index is not corrupted + if (rc != EXT4_ERR_BAD_DX_DIR) { + + if (rc != EOK) { + return rc; + } + + return EOK; + } + + // Needed to clear dir index flag + ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX); + parent->dirty = true; + + EXT4FS_DBG("index is corrupted - doing linear algorithm, index flag cleared"); + } + + // Linear algorithm + + uint32_t iblock, fblock; + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode); + uint32_t total_blocks = inode_size / block_size; + + uint32_t name_len = strlen(name); + + // Find block, where is space for new entry + bool success = false; + for (iblock = 0; iblock < total_blocks; ++iblock) { + + rc = ext4_filesystem_get_inode_data_block_index(fs, parent, iblock, &fblock); + if (rc != EOK) { + return rc; + } + + block_t *block; + rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + rc = ext4_directory_try_insert_entry(fs->superblock, block, child, name, name_len); + if (rc == EOK) { + success = true; + } + + rc = block_put(block); + if (rc != EOK) { + return rc; + } + + if (success) { + return EOK; + } + } + + // No free block found - needed to allocate next block + + rc = ext4_directory_append_block(fs, parent, &fblock, &iblock); + if (rc != EOK) { + return rc; + } + + // Load new block + block_t *new_block; + rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD); + if (rc != EOK) { + return rc; + } + + // Fill block with zeroes + memset(new_block->data, 0, block_size); + ext4_directory_entry_ll_t *block_entry = new_block->data; + ext4_directory_write_entry(fs->superblock, block_entry, block_size, child, name, name_len); + + // Save new block + new_block->dirty = true; + rc = block_put(new_block); + if (rc != EOK) { + return rc; + } + + return EOK; +} + +int ext4_directory_find_entry(ext4_filesystem_t *fs, + ext4_directory_search_result_t *result, ext4_inode_ref_t *parent, + const char *name) +{ + int rc; + uint32_t name_len = strlen(name); + + // Index search + if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) && + ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) { + + rc = ext4_directory_dx_find_entry(result, fs, parent, name_len, name); + + // Check if index is not corrupted + if (rc != EXT4_ERR_BAD_DX_DIR) { + + if (rc != EOK) { + return rc; + } + return EOK; + } + + EXT4FS_DBG("index is corrupted - doing linear search"); + } + + uint32_t iblock, fblock; + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode); + uint32_t total_blocks = inode_size / block_size; + + for (iblock = 0; iblock < total_blocks; ++iblock) { + + rc = ext4_filesystem_get_inode_data_block_index(fs, parent, iblock, &fblock); + if (rc != EOK) { + return rc; + } + + block_t *block; + rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + // find block entry + ext4_directory_entry_ll_t *res_entry; + rc = ext4_directory_find_in_block(block, fs->superblock, name_len, name, &res_entry); + if (rc == EOK) { + result->block = block; + result->dentry = res_entry; + return EOK; + } + + rc = block_put(block); + if (rc != EOK) { + return rc; + } + } + + result->block = NULL; + result->dentry = NULL; + + return ENOENT; +} + + +int ext4_directory_remove_entry(ext4_filesystem_t* fs, + ext4_inode_ref_t *parent, const char *name) +{ + int rc; + + if (!ext4_inode_is_type(fs->superblock, parent->inode, + EXT4_INODE_MODE_DIRECTORY)) { + return ENOTDIR; + } + + ext4_directory_search_result_t result; + rc = ext4_directory_find_entry(fs, &result, parent, name); + if (rc != EOK) { + return rc; + } + + ext4_directory_entry_ll_set_inode(result.dentry, 0); + + uint32_t pos = (void *)result.dentry - result.block->data; + + uint32_t offset = 0; + if (pos != 0) { + + ext4_directory_entry_ll_t *tmp_dentry = result.block->data; + uint16_t tmp_dentry_length = + ext4_directory_entry_ll_get_entry_length(tmp_dentry); + + while ((offset + tmp_dentry_length) < pos) { + offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry); + tmp_dentry = result.block->data + offset; + tmp_dentry_length = + ext4_directory_entry_ll_get_entry_length(tmp_dentry); + } + + assert(tmp_dentry_length + offset == pos); + + uint16_t del_entry_length = + ext4_directory_entry_ll_get_entry_length(result.dentry); + ext4_directory_entry_ll_set_entry_length(tmp_dentry, + tmp_dentry_length + del_entry_length); + + } + + result.block->dirty = true; + + return ext4_directory_destroy_result(&result); +} + + +int ext4_directory_try_insert_entry(ext4_superblock_t *sb, + block_t *target_block, ext4_inode_ref_t *child, + const char *name, uint32_t name_len) +{ + uint32_t block_size = ext4_superblock_get_block_size(sb); + uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len; + if ((required_len % 4) != 0) { + required_len += 4 - (required_len % 4); + } + + ext4_directory_entry_ll_t *dentry = target_block->data; + ext4_directory_entry_ll_t *stop = target_block->data + block_size; + + while (dentry < stop) { + + uint32_t inode = ext4_directory_entry_ll_get_inode(dentry); + uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry); + + if ((inode == 0) && (rec_len >= required_len)) { + ext4_directory_write_entry(sb, dentry, rec_len, child, name, name_len); + target_block->dirty = true; + return EOK; + } + + if (inode != 0) { + uint16_t used_name_len = + ext4_directory_entry_ll_get_name_length(sb, dentry); + + uint16_t used_space = + sizeof(ext4_fake_directory_entry_t) + used_name_len; + if ((used_name_len % 4) != 0) { + used_space += 4 - (used_name_len % 4); + } + uint16_t free_space = rec_len - used_space; + + if (free_space >= required_len) { + + // Cut tail of current entry + ext4_directory_entry_ll_set_entry_length(dentry, used_space); + ext4_directory_entry_ll_t *new_entry = + (void *)dentry + used_space; + ext4_directory_write_entry(sb, new_entry, + free_space, child, name, name_len); + + target_block->dirty = true; + return EOK; + } + } + + dentry = (void *)dentry + rec_len; + } + + return ENOSPC; +} + +int ext4_directory_find_in_block(block_t *block, + ext4_superblock_t *sb, size_t name_len, const char *name, + ext4_directory_entry_ll_t **res_entry) +{ + + ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data; + uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb); + + while ((uint8_t *)dentry < addr_limit) { + + if ((uint8_t*) dentry + name_len > addr_limit) { + break; + } + + if (dentry->inode != 0) { + if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) { + // Compare names + if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) { + *res_entry = dentry; + return EOK; + } + } + } + + // Goto next entry + uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry); + + if (dentry_len == 0) { + return EINVAL; + } + + dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len); + } + + return ENOENT; +} + +int ext4_directory_destroy_result(ext4_directory_search_result_t *result) +{ + if (result->block) { + return block_put(result->block); + } + + return EOK; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_directory.h =================================================================== --- uspace/lib/ext4/libext4_directory.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_directory.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_DIRECTORY_H_ +#define LIBEXT4_LIBEXT4_DIRECTORY_H_ + +#include "libext4_types.h" + +extern uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *); +extern void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *, + uint32_t); +extern uint16_t ext4_directory_entry_ll_get_entry_length( + ext4_directory_entry_ll_t *); +extern void ext4_directory_entry_ll_set_entry_length( + ext4_directory_entry_ll_t *, uint16_t); +extern uint16_t ext4_directory_entry_ll_get_name_length( + ext4_superblock_t *, ext4_directory_entry_ll_t *); +extern void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *, + ext4_directory_entry_ll_t *, uint16_t); +extern uint8_t ext4_directory_entry_ll_get_inode_type(ext4_superblock_t *, + ext4_directory_entry_ll_t *); +extern void ext4_directory_entry_ll_set_inode_type(ext4_superblock_t *, + ext4_directory_entry_ll_t *, uint8_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); +extern int ext4_directory_iterator_fini(ext4_directory_iterator_t *); + +extern int ext4_directory_append_block(ext4_filesystem_t *, + ext4_inode_ref_t *, uint32_t *, uint32_t *); + +extern void ext4_directory_write_entry(ext4_superblock_t *, + ext4_directory_entry_ll_t *, uint16_t, ext4_inode_ref_t *, + const char *, size_t); +extern int ext4_directory_add_entry(ext4_filesystem_t *, ext4_inode_ref_t *, + const char *, ext4_inode_ref_t *); +extern int ext4_directory_find_entry(ext4_filesystem_t *, + ext4_directory_search_result_t *, ext4_inode_ref_t *, const char *); +extern int ext4_directory_remove_entry(ext4_filesystem_t* , + ext4_inode_ref_t *, const char *); + +extern int ext4_directory_try_insert_entry(ext4_superblock_t *, + block_t *, ext4_inode_ref_t *, const char *, uint32_t); + +extern int ext4_directory_find_in_block(block_t *, + ext4_superblock_t *, size_t, const char *, + ext4_directory_entry_ll_t **); + +extern int ext4_directory_destroy_result(ext4_directory_search_result_t *); +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_directory_index.c =================================================================== --- uspace/lib/ext4/libext4_directory_index.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_directory_index.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,864 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_directory_index.c + * @brief Ext4 directory index operations. + */ + +#include +#include +#include +#include +#include +#include "libext4.h" + +typedef struct ext4_dx_sort_entry { + uint32_t hash; + uint32_t rec_len; + void *dentry; +} ext4_dx_sort_entry_t; + + +uint8_t ext4_directory_dx_root_info_get_hash_version( + ext4_directory_dx_root_info_t *root_info) +{ + return root_info->hash_version; +} + +void ext4_directory_dx_root_info_set_hash_version( + ext4_directory_dx_root_info_t *root_info, uint8_t version) +{ + root_info->hash_version = version; +} + +uint8_t ext4_directory_dx_root_info_get_info_length( + ext4_directory_dx_root_info_t *root_info) +{ + return root_info->info_length; +} + +void ext4_directory_dx_root_info_set_info_length( + ext4_directory_dx_root_info_t *root_info, uint8_t info_length) +{ + root_info->info_length = info_length; +} + +uint8_t ext4_directory_dx_root_info_get_indirect_levels( + ext4_directory_dx_root_info_t *root_info) +{ + return root_info->indirect_levels; +} + +void ext4_directory_dx_root_info_set_indirect_levels( + ext4_directory_dx_root_info_t *root_info, uint8_t levels) +{ + root_info->indirect_levels = levels; +} + +uint16_t ext4_directory_dx_countlimit_get_limit( + ext4_directory_dx_countlimit_t *countlimit) +{ + return uint16_t_le2host(countlimit->limit); +} + +void ext4_directory_dx_countlimit_set_limit( + ext4_directory_dx_countlimit_t *countlimit, uint16_t limit) +{ + countlimit->limit = host2uint16_t_le(limit); +} + +uint16_t ext4_directory_dx_countlimit_get_count( + ext4_directory_dx_countlimit_t *countlimit) +{ + return uint16_t_le2host(countlimit->count); +} + +void ext4_directory_dx_countlimit_set_count( + ext4_directory_dx_countlimit_t *countlimit, uint16_t count) +{ + countlimit->count = host2uint16_t_le(count); +} + +uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry) +{ + return uint32_t_le2host(entry->hash); +} + +void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry, + uint32_t hash) +{ + entry->hash = host2uint32_t_le(hash); +} + +uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry) +{ + return uint32_t_le2host(entry->block); +} + +void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry, + uint32_t block) +{ + entry->block = host2uint32_t_le(block); +} + + +/**************************************************************************/ + + +static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block, + ext4_superblock_t *sb, size_t name_len, const char *name) +{ + + ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data; + + if (root->info.hash_version != EXT4_HASH_VERSION_TEA && + root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 && + root->info.hash_version != EXT4_HASH_VERSION_LEGACY) { + return EXT4_ERR_BAD_DX_DIR; + } + + // Check unused flags + if (root->info.unused_flags != 0) { + EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags); + return EXT4_ERR_BAD_DX_DIR; + } + + // Check indirect levels + if (root->info.indirect_levels > 1) { + EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels); + return EXT4_ERR_BAD_DX_DIR; + } + + uint32_t block_size = ext4_superblock_get_block_size(sb); + + uint32_t entry_space = block_size; + entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t); + entry_space -= sizeof(ext4_directory_dx_root_info_t); + entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); + + uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries); + if (limit != entry_space) { + return EXT4_ERR_BAD_DX_DIR; + } + + hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info); + if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA) + && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { + // 3 is magic from ext4 linux implementation + hinfo->hash_version += 3; + } + + hinfo->seed = ext4_superblock_get_hash_seed(sb); + + if (name) { + ext4_hash_string(hinfo, name_len, name); + } + + return EOK; +} + +static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo, + ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, block_t *root_block, + ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks) +{ + int rc; + + ext4_directory_dx_block_t *tmp_dx_block = dx_blocks; + + ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data; + ext4_directory_dx_entry_t *entries = (ext4_directory_dx_entry_t *)&root->entries; + + uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); + uint8_t indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info); + + block_t *tmp_block = root_block; + ext4_directory_dx_entry_t *p, *q, *m, *at; + while (true) { + + uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries); + if ((count == 0) || (count > limit)) { + return EXT4_ERR_BAD_DX_DIR; + } + + p = entries + 1; + q = entries + count - 1; + + while (p <= q) { + m = p + (q - p) / 2; + if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) { + q = m - 1; + } else { + p = m + 1; + } + } + + at = p - 1; + + tmp_dx_block->block = tmp_block; + tmp_dx_block->entries = entries; + tmp_dx_block->position = at; + + if (indirect_level == 0) { + *dx_block = tmp_dx_block; + return EOK; + } + + uint32_t next_block = ext4_directory_dx_entry_get_block(at); + + indirect_level--; + + uint32_t fblock; + rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref, next_block, &fblock); + if (rc != EOK) { + return rc; + } + + rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries; + limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); + + uint16_t entry_space = ext4_superblock_get_block_size(fs->superblock) + - sizeof(ext4_directory_dx_dot_entry_t); + entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); + + + if (limit != entry_space) { + block_put(tmp_block); + return EXT4_ERR_BAD_DX_DIR; + } + + ++tmp_dx_block; + } + + // Unreachable + return EOK; +} + + +static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, uint32_t hash, + ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles) +{ + int rc; + + + uint32_t num_handles = 0; + ext4_directory_dx_block_t *p = handle; + + while (1) { + + p->position++; + uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries); + + if (p->position < p->entries + count) { + break; + } + + if (p == handles) { + return 0; + } + + num_handles++; + p--; + } + + uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position); + + if ((hash & 1) == 0) { + if ((current_hash & ~1) != hash) { + return 0; + } + } + + + while (num_handles--) { + + uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position); + uint32_t block_addr; + rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref, block_idx, &block_addr); + if (rc != EOK) { + return rc; + } + + block_t *block; + rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + p++; + + block_put(p->block); + p->block = block; + p->entries = ((ext4_directory_dx_node_t *) block->data)->entries; + p->position = p->entries; + } + + return 1; + +} + +int ext4_directory_dx_find_entry(ext4_directory_search_result_t *result, + ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t name_len, const char *name) +{ + int rc; + + // get direct block 0 (index root) + uint32_t root_block_addr; + rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref, 0, &root_block_addr); + if (rc != EOK) { + return rc; + } + + block_t *root_block; + rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + ext4_hash_info_t hinfo; + rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name); + if (rc != EOK) { + block_put(root_block); + return EXT4_ERR_BAD_DX_DIR; + } + + // Hardcoded number 2 means maximum height of index tree !!! + ext4_directory_dx_block_t dx_blocks[2]; + ext4_directory_dx_block_t *dx_block, *tmp; + rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref, root_block, &dx_block, dx_blocks); + if (rc != EOK) { + block_put(root_block); + return EXT4_ERR_BAD_DX_DIR; + } + + + do { + + uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); + uint32_t leaf_block_addr; + rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref, leaf_block_idx, &leaf_block_addr); + if (rc != EOK) { + goto cleanup; + } + + block_t *leaf_block; + rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + goto cleanup; + } + + ext4_directory_entry_ll_t *res_dentry; + rc = ext4_directory_find_in_block(leaf_block, fs->superblock, name_len, name, &res_dentry); + + // Found => return it + if (rc == EOK) { + result->block = leaf_block; + result->dentry = res_dentry; + goto cleanup; + } + + // Not found, leave untouched + block_put(leaf_block); + + if (rc != ENOENT) { + goto cleanup; + } + + rc = ext4_directory_dx_next_block(fs, inode_ref, hinfo.hash, dx_block, &dx_blocks[0]); + if (rc < 0) { + goto cleanup; + } + + } while (rc == 1); + + rc = ENOENT; + +cleanup: + + tmp = dx_blocks; + while (tmp <= dx_block) { + block_put(tmp->block); + ++tmp; + } + return rc; +} + +static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy) +{ + ext4_dx_sort_entry_t *entry1 = arg1; + ext4_dx_sort_entry_t *entry2 = arg2; + + if (entry1->hash == entry2->hash) { + return 0; + } + + if (entry1->hash < entry2->hash) { + return -1; + } else { + return 1; + } + +} + +static void ext4_directory_dx_insert_entry( + ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock) +{ + ext4_directory_dx_entry_t *old_index_entry = index_block->position; + ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1; + + ext4_directory_dx_countlimit_t *countlimit = + (ext4_directory_dx_countlimit_t *)index_block->entries; + uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit); + + ext4_directory_dx_entry_t *start_index = index_block->entries; + size_t bytes = (void *)(start_index + count) - (void *)(new_index_entry); + + memmove(new_index_entry + 1, new_index_entry, bytes); + + ext4_directory_dx_entry_set_block(new_index_entry, iblock); + ext4_directory_dx_entry_set_hash(new_index_entry, hash); + + ext4_directory_dx_countlimit_set_count(countlimit, count + 1); + + index_block->block->dirty = true; +} + +static int ext4_directory_dx_split_data(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo, + block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block) +{ + int rc = EOK; + + // Allocate buffer for directory entries + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + void *entry_buffer = malloc(block_size); + if (entry_buffer == NULL) { + return ENOMEM; + } + + // dot entry has the smallest size available + uint32_t max_entry_count = block_size / sizeof(ext4_directory_dx_dot_entry_t); + + // Allocate sort entry + ext4_dx_sort_entry_t *sort_array = malloc(max_entry_count * sizeof(ext4_dx_sort_entry_t)); + if (sort_array == NULL) { + free(entry_buffer); + return ENOMEM; + } + + uint32_t idx = 0; + uint32_t real_size = 0; + + // Initialize hinfo + ext4_hash_info_t tmp_hinfo; + memcpy(&tmp_hinfo, hinfo, sizeof(ext4_hash_info_t)); + + // Load all valid entries to the buffer + ext4_directory_entry_ll_t *dentry = old_data_block->data; + void *entry_buffer_ptr = entry_buffer; + while ((void *)dentry < old_data_block->data + block_size) { + + // Read only valid entries + if (ext4_directory_entry_ll_get_inode(dentry) != 0) { + + uint8_t len = ext4_directory_entry_ll_get_name_length(fs->superblock, dentry); + ext4_hash_string(&tmp_hinfo, len, (char *)dentry->name); + + uint32_t rec_len = 8 + len; + + if ((rec_len % 4) != 0) { + rec_len += 4 - (rec_len % 4); + } + + memcpy(entry_buffer_ptr, dentry, rec_len); + + sort_array[idx].dentry = entry_buffer_ptr; + sort_array[idx].rec_len = rec_len; + sort_array[idx].hash = tmp_hinfo.hash; + + entry_buffer_ptr += rec_len; + real_size += rec_len; + idx++; + } + + dentry = (void *)dentry + ext4_directory_entry_ll_get_entry_length(dentry); + } + + qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t), ext4_directory_dx_entry_comparator, NULL); + + uint32_t new_fblock; + uint32_t new_iblock; + rc = ext4_directory_append_block(fs, inode_ref, &new_fblock, &new_iblock); + if (rc != EOK) { + free(sort_array); + free(entry_buffer); + return rc; + } + + // Load new block + block_t *new_data_block_tmp; + rc = block_get(&new_data_block_tmp, fs->device, new_fblock, BLOCK_FLAGS_NOREAD); + if (rc != EOK) { + free(sort_array); + free(entry_buffer); + return rc; + } + + // Distribute entries to splitted blocks (by size) + uint32_t new_hash = 0; + uint32_t current_size = 0; + uint32_t mid = 0; + for (uint32_t i = 0; i < idx; ++i) { + if ((current_size + sort_array[i].rec_len) > (real_size / 2)) { + new_hash = sort_array[i].hash; + mid = i; + break; + } + + current_size += sort_array[i].rec_len; + } + + uint32_t continued = 0; + if (new_hash == sort_array[mid-1].hash) { + continued = 1; + } + + uint32_t offset = 0; + void *ptr; + + // First part - to the old block + for (uint32_t i = 0; i < mid; ++i) { + ptr = old_data_block->data + offset; + memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len); + + ext4_directory_entry_ll_t *tmp = ptr; + if (i < (mid - 1)) { + ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len); + } else { + ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset); + } + + offset += sort_array[i].rec_len; + } + + // Second part - to the new block + offset = 0; + for (uint32_t i = mid; i < idx; ++i) { + ptr = new_data_block_tmp->data + offset; + memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len); + + ext4_directory_entry_ll_t *tmp = ptr; + if (i < (idx - 1)) { + ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len); + } else { + ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset); + } + + offset += sort_array[i].rec_len; + } + + old_data_block->dirty = true; + new_data_block_tmp->dirty = true; + + free(sort_array); + free(entry_buffer); + + ext4_directory_dx_insert_entry(index_block, new_hash + continued, new_iblock); + + *new_data_block = new_data_block_tmp; + + return EOK; +} + + +static int ext4_directory_dx_split_index(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, ext4_directory_dx_block_t *dx_blocks, + ext4_directory_dx_block_t *dx_block) +{ + int rc; + + ext4_directory_dx_entry_t *entries; + if (dx_block == dx_blocks) { + entries = ((ext4_directory_dx_root_t *) dx_block->block->data)->entries; + } else { + entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries; + } + + ext4_directory_dx_countlimit_t *countlimit = + (ext4_directory_dx_countlimit_t *)entries; + uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit(countlimit); + uint16_t leaf_count = ext4_directory_dx_countlimit_get_count(countlimit); + + // Check if is necessary to split index block + if (leaf_limit == leaf_count) { + EXT4FS_DBG("need to split index block !!!"); + + unsigned int levels = dx_block - dx_blocks; + + ext4_directory_dx_entry_t *root_entries = + ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->entries; + + ext4_directory_dx_countlimit_t *root_countlimit = + (ext4_directory_dx_countlimit_t *)root_entries; + uint16_t root_limit = + ext4_directory_dx_countlimit_get_limit(root_countlimit); + uint16_t root_count = + ext4_directory_dx_countlimit_get_count(root_countlimit); + + if ((levels > 0) && (root_limit == root_count)) { + EXT4FS_DBG("Directory index is full"); + return ENOSPC; + } + + uint32_t new_fblock; + uint32_t new_iblock; + rc = ext4_directory_append_block(fs, inode_ref, &new_fblock, &new_iblock); + if (rc != EOK) { + return rc; + } + + // New block allocated + block_t * new_block; + rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD); + if (rc != EOK) { + return rc; + } + + ext4_directory_dx_node_t *new_node = new_block->data; + ext4_directory_dx_entry_t *new_entries = new_node->entries; + + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + + if (levels > 0) { + EXT4FS_DBG("split index leaf node"); + uint32_t count_left = leaf_count / 2; + uint32_t count_right = leaf_count - count_left; + uint32_t hash_right = + ext4_directory_dx_entry_get_hash(entries + count_left); + + memcpy((void *) new_entries, (void *) (entries + count_left), + count_right * sizeof(ext4_directory_dx_entry_t)); + + ext4_directory_dx_countlimit_t *left_countlimit = + (ext4_directory_dx_countlimit_t *)entries; + ext4_directory_dx_countlimit_t *right_countlimit = + (ext4_directory_dx_countlimit_t *)new_entries; + + ext4_directory_dx_countlimit_set_count(left_countlimit, count_left); + ext4_directory_dx_countlimit_set_count(right_countlimit, count_right); + + uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t); + uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t); + ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit); + + // Which index block is target for new entry + uint32_t position_index = (dx_block->position - dx_block->entries); + if (position_index >= count_left) { + + dx_block->block->dirty = true; + + block_t *block_tmp = dx_block->block; + dx_block->block = new_block; + dx_block->position = new_entries + position_index - count_left; + dx_block->entries = new_entries; + + new_block = block_tmp; + + } + + ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock); + + return block_put(new_block); + + } else { + EXT4FS_DBG("create second level"); + + memcpy((void *) new_entries, (void *) entries, + leaf_count * sizeof(ext4_directory_dx_entry_t)); + + ext4_directory_dx_countlimit_t *new_countlimit = + (ext4_directory_dx_countlimit_t *)new_entries; + + uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t); + uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t); + ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit); + + // Set values in root node + ext4_directory_dx_countlimit_t *new_root_countlimit = + (ext4_directory_dx_countlimit_t *)entries; + + ext4_directory_dx_countlimit_set_count(new_root_countlimit, 1); + ext4_directory_dx_entry_set_block(entries, new_iblock); + + ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1; + + /* Add new access path frame */ + dx_block = dx_blocks + 1; + dx_block->position = dx_block->position - entries + new_entries; + dx_block->entries = new_entries; + dx_block->block = new_block; + } + + } + + return EOK; +} + +int ext4_directory_dx_add_entry(ext4_filesystem_t *fs, + ext4_inode_ref_t *parent, ext4_inode_ref_t *child, const char *name) +{ + int rc = EOK; + int rc2 = EOK; + + // get direct block 0 (index root) + uint32_t root_block_addr; + rc = ext4_filesystem_get_inode_data_block_index(fs, parent, 0, &root_block_addr); + if (rc != EOK) { + return rc; + } + + block_t *root_block; + rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + uint32_t name_len = strlen(name); + ext4_hash_info_t hinfo; + rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name); + if (rc != EOK) { + block_put(root_block); + return EXT4_ERR_BAD_DX_DIR; + } + + // Hardcoded number 2 means maximum height of index tree !!! + ext4_directory_dx_block_t dx_blocks[2]; + ext4_directory_dx_block_t *dx_block, *dx_it; + rc = ext4_directory_dx_get_leaf(&hinfo, fs, parent, root_block, &dx_block, dx_blocks); + if (rc != EOK) { + rc = EXT4_ERR_BAD_DX_DIR; + goto release_index; + } + + + // Try to insert to existing data block + uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); + uint32_t leaf_block_addr; + rc = ext4_filesystem_get_inode_data_block_index(fs, parent, leaf_block_idx, &leaf_block_addr); + if (rc != EOK) { + goto release_index; + } + + + block_t *target_block; + rc = block_get(&target_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + goto release_index; + } + + + rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len); + if (rc == EOK) { + goto release_target_index; + } + + EXT4FS_DBG("no free space found"); + + rc = ext4_directory_dx_split_index(fs, parent, dx_blocks, dx_block); + if (rc != EOK) { + goto release_target_index; + } + + block_t *new_block = NULL; + rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target_block, dx_block, &new_block); + if (rc != EOK) { + rc2 = rc; + goto release_target_index; + } + + // Where to save new entry + uint32_t new_block_hash = ext4_directory_dx_entry_get_hash(dx_block->position + 1); + if (hinfo.hash >= new_block_hash) { + rc = ext4_directory_try_insert_entry(fs->superblock, new_block, child, name, name_len); + } else { + rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len); + } + + + + + rc = block_put(new_block); + if (rc != EOK) { + EXT4FS_DBG("error writing new block"); + return rc; + } + +release_target_index: + + rc2 = rc; + + rc = block_put(target_block); + if (rc != EOK) { + EXT4FS_DBG("error writing target block"); + return rc; + } + +release_index: + + if (rc != EOK) { + rc2 = rc; + } + + dx_it = dx_blocks; + + while (dx_it <= dx_block) { + rc = block_put(dx_it->block); + if (rc != EOK) { + EXT4FS_DBG("error writing index block"); + return rc; + } + dx_it++; + } + + return rc2; +} + + +/** + * @} + */ Index: uspace/lib/ext4/libext4_directory_index.h =================================================================== --- uspace/lib/ext4/libext4_directory_index.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_directory_index.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,77 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_DIRECTORY_INDEX_H_ +#define LIBEXT4_LIBEXT4_DIRECTORY_INDEX_H_ + +#include "libext4_types.h" + +extern uint8_t ext4_directory_dx_root_info_get_hash_version( + ext4_directory_dx_root_info_t *); +extern void ext4_directory_dx_root_info_set_hash_version( + ext4_directory_dx_root_info_t *, uint8_t); +extern uint8_t ext4_directory_dx_root_info_get_info_length( + ext4_directory_dx_root_info_t *); +extern void ext4_directory_dx_root_info_set_info_length( + ext4_directory_dx_root_info_t *, uint8_t); +extern uint8_t ext4_directory_dx_root_info_get_indirect_levels( + ext4_directory_dx_root_info_t *); +extern void ext4_directory_dx_root_info_set_indirect_levels( + ext4_directory_dx_root_info_t *, uint8_t); + +extern uint16_t ext4_directory_dx_countlimit_get_limit( + ext4_directory_dx_countlimit_t *); +extern void ext4_directory_dx_countlimit_set_limit( + ext4_directory_dx_countlimit_t *, uint16_t); +extern uint16_t ext4_directory_dx_countlimit_get_count( + ext4_directory_dx_countlimit_t *); +extern void ext4_directory_dx_countlimit_set_count( + ext4_directory_dx_countlimit_t *, uint16_t); + +extern uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *); +extern void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *, + uint32_t); +extern uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *); +void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *, uint32_t); + +/*********************************************************************************/ + +extern int ext4_directory_dx_find_entry(ext4_directory_search_result_t *, + ext4_filesystem_t *, ext4_inode_ref_t *, size_t, const char *); +extern int ext4_directory_dx_add_entry(ext4_filesystem_t *, + ext4_inode_ref_t *, ext4_inode_ref_t *, const char *); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_extent.c =================================================================== --- uspace/lib/ext4/libext4_extent.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_extent.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,372 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_extent.c + * @brief Ext4 extent structures operations. + */ + +#include +#include +#include +#include "libext4.h" + +uint32_t ext4_extent_get_first_block(ext4_extent_t *extent) +{ + return uint32_t_le2host(extent->first_block); +} + +void ext4_extent_set_first_block(ext4_extent_t *extent, uint32_t first_block) +{ + extent->first_block = host2uint32_t_le(first_block); +} + +uint16_t ext4_extent_get_block_count(ext4_extent_t *extent) +{ + return uint16_t_le2host(extent->block_count); +} + +void ext4_extent_set_block_count(ext4_extent_t *extent, uint16_t block_count) +{ + extent->block_count = host2uint16_t_le(block_count); +} + +uint64_t ext4_extent_get_start(ext4_extent_t *extent) +{ + return ((uint64_t)uint16_t_le2host(extent->start_hi)) << 32 | + ((uint64_t)uint32_t_le2host(extent->start_lo)); +} + +void ext4_extent_set_start(ext4_extent_t *extent, uint64_t start) +{ + extent->start_lo = host2uint32_t_le((start << 32) >> 32); + extent->start_hi = host2uint16_t_le((uint16_t)(start >> 32)); +} + +uint32_t ext4_extent_index_get_first_block(ext4_extent_index_t *index) +{ + return uint32_t_le2host(index->first_block); +} + +void ext4_extent_index_set_first_block(ext4_extent_index_t *index, + uint32_t first) +{ + index->first_block = host2uint32_t_le(first); +} + +uint64_t ext4_extent_index_get_leaf(ext4_extent_index_t *index) +{ + return ((uint64_t)uint16_t_le2host(index->leaf_hi)) << 32 | + ((uint64_t)uint32_t_le2host(index->leaf_lo)); +} + +void ext4_extent_index_set_leaf(ext4_extent_index_t *index, uint64_t leaf) +{ + index->leaf_lo = host2uint32_t_le((leaf << 32) >> 32); + index->leaf_hi = host2uint16_t_le((uint16_t)(leaf >> 32)); +} + +uint16_t ext4_extent_header_get_magic(ext4_extent_header_t *header) +{ + return uint16_t_le2host(header->magic); +} + +void ext4_extent_header_set_magic(ext4_extent_header_t *header, uint16_t magic) +{ + header->magic = host2uint16_t_le(magic); +} + +uint16_t ext4_extent_header_get_entries_count(ext4_extent_header_t *header) +{ + return uint16_t_le2host(header->entries_count); +} + +void ext4_extent_header_set_entries_count(ext4_extent_header_t *header, + uint16_t count) +{ + header->entries_count = host2uint16_t_le(count); +} + +uint16_t ext4_extent_header_get_max_entries_count(ext4_extent_header_t *header) +{ + return uint16_t_le2host(header->max_entries_count); +} + +void ext4_extent_header_set_max_entries_count(ext4_extent_header_t *header, + uint16_t max_count) +{ + header->max_entries_count = host2uint16_t_le(max_count); +} + +uint16_t ext4_extent_header_get_depth(ext4_extent_header_t *header) +{ + return uint16_t_le2host(header->depth); +} + +void ext4_extent_header_set_depth(ext4_extent_header_t *header, uint16_t depth) +{ + header->depth = host2uint16_t_le(depth); +} + +uint32_t ext4_extent_header_get_generation(ext4_extent_header_t *header) +{ + return uint32_t_le2host(header->generation); +} + +void ext4_extent_header_set_generation(ext4_extent_header_t *header, + uint32_t generation) +{ + header->generation = host2uint32_t_le(generation); +} + +//static void ext4_extent_binsearch_idx(ext4_extent_path_t *path, uint32_t iblock) +//{ +// ext4_extent_header_t *header = path->header; +// ext4_extent_index_t *r, *l, *m; +// +// uint16_t entries_count = ext4_extent_header_get_entries_count(header); +// l = EXT4_EXTENT_FIRST_INDEX(header) + 1; +// r = l + entries_count - 1; +// +// while (l <= r) { +// m = l + (r - l) / 2; +// uint32_t block = ext4_extent_index_get_first_block(m); +// if (iblock < block) { +// r = m - 1; +// } else { +// l = m + 1; +// } +// } +// +// path->index = l - 1; +//} +// +static void ext4_extent_binsearch(ext4_extent_path_t *path, uint32_t iblock) +{ + ext4_extent_header_t *header = path->header; + ext4_extent_t *r, *l, *m; + + uint16_t entries_count = ext4_extent_header_get_entries_count(header); + + if (entries_count == 0) { + // this leaf is empty + return; + } + + l = EXT4_EXTENT_FIRST(header) + 1; + r = l + entries_count - 1; + + while (l <= r) { + m = l + (r - l) / 2; + uint32_t block = ext4_extent_get_first_block(m); + if (iblock < block) { + r = m - 1; + } else { + l = m + 1; + } + } + + path->extent = l - 1; + +} + +static int ext4_extent_find_extent(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, uint32_t iblock, ext4_extent_t **ret_extent) +{ + int rc; + + block_t* block = NULL; + + ext4_extent_header_t *header = ext4_inode_get_extent_header(inode_ref->inode); + while (ext4_extent_header_get_depth(header) != 0) { + + ext4_extent_index_t *extent_index = EXT4_EXTENT_FIRST_INDEX(header); + + for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i) { + if (iblock >= ext4_extent_index_get_first_block(extent_index)) { + + uint64_t child = ext4_extent_index_get_leaf(extent_index); + + if (block != NULL) { + block_put(block); + } + + rc = block_get(&block, fs->device, child, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + header = (ext4_extent_header_t *)block->data; + break; + } + } + } + + + ext4_extent_path_t path; + + path.header = header; + path.extent = NULL; + + ext4_extent_binsearch(&path, iblock); + + *ret_extent = path.extent; + +// for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i) { +// +// uint32_t first_block = ext4_extent_get_first_block(extent); +// uint16_t block_count = ext4_extent_get_block_count(extent); +// +// if ((iblock >= first_block) && (iblock < first_block + block_count)) { +// break; +// } +// // Go to the next extent +// ++extent; +// } +// +// *ret_extent = extent; + + return EOK; +} + +int ext4_extent_find_block(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, uint32_t iblock, uint32_t *fblock) +{ + int rc; + + ext4_extent_t *extent = NULL; + rc = ext4_extent_find_extent(fs, inode_ref, iblock, &extent); + if (rc != EOK) { + return rc; + } + + uint32_t phys_block; + phys_block = ext4_extent_get_start(extent) + iblock; + phys_block -= ext4_extent_get_first_block(extent); + + + *fblock = phys_block; + + return EOK; + + +// ext4_extent_header_t *eh = +// ext4_inode_get_extent_header(inode_ref->inode); +// +// uint16_t depth = ext4_extent_header_get_depth(eh); +// +// ext4_extent_path_t *tmp_path; +// +// // Added 2 for possible tree growing +// tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2)); +// if (tmp_path == NULL) { +// *path = NULL; +// return ENOMEM; +// } +// +// tmp_path[0].block = inode_ref->block; +// tmp_path[0].header = eh; +// +// uint16_t pos = 0; +// while (ext4_extent_header_get_depth(eh) != 0) { +// +// EXT4FS_DBG("count == \%u", ext4_extent_header_get_entries_count(eh)); +// +// ext4_extent_binsearch_idx(tmp_path + pos, iblock); +// +// uint32_t offset = (void *)tmp_path[pos].index - (void *)EXT4_EXTENT_FIRST_INDEX(eh); +// +// EXT4FS_DBG("offset = \%u", offset); +// +// EXT4FS_DBG("first block = \%u, leaf = \%u", +// ext4_extent_index_get_first_block(tmp_path[pos].index), +// (uint32_t)ext4_extent_index_get_leaf(tmp_path[pos].index)); +// +// tmp_path[pos].depth = depth; +// tmp_path[pos].extent = NULL; +// +// assert(tmp_path[pos].index != NULL); +// +// uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index); +// +// EXT4FS_DBG("fblock = \%u", (uint32_t)fblock); +// +// block_t *block; +// rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); +// if (rc != EOK) { +// // TODO cleanup +// EXT4FS_DBG("ERRRR"); +// return rc; +// } +// +// EXT4FS_DBG("block loaded"); +// +// pos++; +// +// eh = (ext4_extent_header_t *)block->data; +// tmp_path[pos].block = block; +// tmp_path[pos].header = eh; +// +// } +// +// tmp_path[pos].depth = 0; +// tmp_path[pos].extent = NULL; +// tmp_path[pos].index = NULL; +// +// EXT4FS_DBG("pos = \%u", pos); +// +// /* find extent */ +// ext4_extent_binsearch(tmp_path + pos, iblock); +// +// EXT4FS_DBG("after binsearch in extent"); +// +// /* if not an empty leaf */ +// if (tmp_path[pos].extent) { +// EXT4FS_DBG("nonempty leaf"); +// +//// uint64_t fblock = ext4_extent_get_start(tmp_path[pos].extent); +//// block_t *block; +//// rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); +//// if (rc != EOK) { +//// // TODO cleanup +//// } +//// tmp_path[pos].block = block; +// } +// +// *path = tmp_path; +// +// return EOK; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_extent.h =================================================================== --- uspace/lib/ext4/libext4_extent.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_extent.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_EXTENT_H_ +#define LIBEXT4_LIBEXT4_EXTENT_H_ + +#include "libext4_types.h" + +extern uint32_t ext4_extent_get_first_block(ext4_extent_t *); +extern void ext4_extent_set_first_block(ext4_extent_t *, uint32_t); +extern uint16_t ext4_extent_get_block_count(ext4_extent_t *); +extern void ext4_extent_set_block_count(ext4_extent_t *, uint16_t); +extern uint64_t ext4_extent_get_start(ext4_extent_t *); +extern void ext4_extent_set_start(ext4_extent_t *, uint64_t); + +extern uint32_t ext4_extent_index_get_first_block(ext4_extent_index_t *); +extern void ext4_extent_index_set_first_block(ext4_extent_index_t *, uint32_t); +extern uint64_t ext4_extent_index_get_leaf(ext4_extent_index_t *); +extern void ext4_extent_index_set_leaf(ext4_extent_index_t *, uint64_t); + +extern uint16_t ext4_extent_header_get_magic(ext4_extent_header_t *); +extern void ext4_extent_header_set_magic(ext4_extent_header_t *, uint16_t); +extern uint16_t ext4_extent_header_get_entries_count(ext4_extent_header_t *); +extern void ext4_extent_header_set_entries_count(ext4_extent_header_t *, + uint16_t); +extern uint16_t ext4_extent_header_get_max_entries_count(ext4_extent_header_t *); +extern void ext4_extent_header_set_max_entries_count(ext4_extent_header_t *, + uint16_t); +extern uint16_t ext4_extent_header_get_depth(ext4_extent_header_t *); +extern void ext4_extent_header_set_depth(ext4_extent_header_t *, uint16_t); +extern uint32_t ext4_extent_header_get_generation(ext4_extent_header_t *); +extern void ext4_extent_header_set_generation(ext4_extent_header_t *, uint32_t); + +extern int ext4_extent_find_block(ext4_filesystem_t *, ext4_inode_ref_t *, + uint32_t, uint32_t *); +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_filesystem.c =================================================================== --- uspace/lib/ext4/libext4_filesystem.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_filesystem.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,892 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_filesystem.c + * @brief More complex filesystem operations. + */ + +#include +#include +#include +#include "libext4.h" + +int ext4_filesystem_init(ext4_filesystem_t *fs, service_id_t service_id) +{ + int rc; + + fs->device = service_id; + + // TODO what does constant 2048 mean? + rc = block_init(EXCHANGE_SERIALIZE, fs->device, 2048); + if (rc != EOK) { + return rc; + } + + /* Read superblock from device */ + ext4_superblock_t *temp_superblock; + rc = ext4_superblock_read_direct(fs->device, &temp_superblock); + if (rc != EOK) { + block_fini(fs->device); + return rc; + } + + /* Read block size from superblock and check */ + uint32_t block_size = ext4_superblock_get_block_size(temp_superblock); + if (block_size > EXT4_MAX_BLOCK_SIZE) { + block_fini(fs->device); + return ENOTSUP; + } + + /* Initialize block caching */ + rc = block_cache_init(service_id, block_size, 0, CACHE_MODE_WT); + if (rc != EOK) { + block_fini(fs->device); + return rc; + } + + uint32_t block_ids_per_block = block_size / sizeof(uint32_t); + fs->inode_block_limits[0] = EXT4_INODE_DIRECT_BLOCK_COUNT; + fs->inode_blocks_per_level[0] = 1; + for (int i = 1; i < 4; i++) { + fs->inode_blocks_per_level[i] = fs->inode_blocks_per_level[i-1] * + block_ids_per_block; + fs->inode_block_limits[i] = fs->inode_block_limits[i-1] + + fs->inode_blocks_per_level[i]; + } + + /* Return loaded superblock */ + fs->superblock = temp_superblock; + + return EOK; +} + +int ext4_filesystem_fini(ext4_filesystem_t *fs, bool write_sb) +{ + int rc = EOK; + + if (write_sb) { + rc = ext4_superblock_write_direct(fs->device, fs->superblock); + } + + free(fs->superblock); + block_fini(fs->device); + + return rc; +} + +int ext4_filesystem_check_sanity(ext4_filesystem_t *fs) +{ + int rc; + + rc = ext4_superblock_check_sanity(fs->superblock); + if (rc != EOK) { + return rc; + } + + return EOK; +} + +int ext4_filesystem_check_features(ext4_filesystem_t *fs, bool *o_read_only) +{ + /* Feature flags are present in rev 1 and later */ + if (ext4_superblock_get_rev_level(fs->superblock) == 0) { + *o_read_only = false; + return EOK; + } + + uint32_t incompatible_features; + incompatible_features = ext4_superblock_get_features_incompatible(fs->superblock); + incompatible_features &= ~EXT4_FEATURE_INCOMPAT_SUPP; + if (incompatible_features > 0) { + *o_read_only = true; + return ENOTSUP; + } + + uint32_t compatible_read_only; + compatible_read_only = ext4_superblock_get_features_read_only(fs->superblock); + compatible_read_only &= ~EXT4_FEATURE_RO_COMPAT_SUPP; + if (compatible_read_only > 0) { + *o_read_only = true; + } + + return EOK; +} + +int ext4_filesystem_get_block_group_ref(ext4_filesystem_t *fs, uint32_t bgid, + ext4_block_group_ref_t **ref) +{ + int rc; + + ext4_block_group_ref_t *newref = malloc(sizeof(ext4_block_group_ref_t)); + if (newref == NULL) { + return ENOMEM; + } + + uint32_t descriptors_per_block = ext4_superblock_get_block_size(fs->superblock) + / ext4_superblock_get_desc_size(fs->superblock); + + /* Block group descriptor table starts at the next block after superblock */ + aoff64_t block_id = ext4_superblock_get_first_data_block(fs->superblock) + 1; + + /* Find the block containing the descriptor we are looking for */ + block_id += bgid / descriptors_per_block; + uint32_t offset = (bgid % descriptors_per_block) * ext4_superblock_get_desc_size(fs->superblock); + + rc = block_get(&newref->block, fs->device, block_id, 0); + if (rc != EOK) { + free(newref); + return rc; + } + + newref->block_group = newref->block->data + offset; + newref->dirty = false; + + *ref = newref; + + return EOK; +} + +int ext4_filesystem_put_block_group_ref(ext4_block_group_ref_t *ref) +{ + int rc; + + if (ref->dirty) { + ref->block->dirty = true; + } + + rc = block_put(ref->block); + free(ref); + + return rc; +} + +int ext4_filesystem_get_inode_ref(ext4_filesystem_t *fs, uint32_t index, + ext4_inode_ref_t **ref) +{ + int rc; + + ext4_inode_ref_t *newref = malloc(sizeof(ext4_inode_ref_t)); + if (newref == NULL) { + return ENOMEM; + } + + uint32_t inodes_per_group = + ext4_superblock_get_inodes_per_group(fs->superblock); + + /* inode numbers are 1-based, but it is simpler to work with 0-based + * when computing indices + */ + index -= 1; + uint32_t block_group = index / inodes_per_group; + uint32_t offset_in_group = index % inodes_per_group; + + ext4_block_group_ref_t *bg_ref; + rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); + if (rc != EOK) { + free(newref); + return rc; + } + + uint32_t inode_table_start = ext4_block_group_get_inode_table_first_block( + bg_ref->block_group, fs->superblock); + + rc = ext4_filesystem_put_block_group_ref(bg_ref); + if (rc != EOK) { + free(newref); + return rc; + } + + uint16_t inode_size = ext4_superblock_get_inode_size(fs->superblock); + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + uint32_t byte_offset_in_group = offset_in_group * inode_size; + + aoff64_t block_id = inode_table_start + (byte_offset_in_group / block_size); + rc = block_get(&newref->block, fs->device, block_id, 0); + if (rc != EOK) { + free(newref); + return rc; + } + + uint32_t offset_in_block = byte_offset_in_group % block_size; + newref->inode = newref->block->data + offset_in_block; + /* we decremented index above, but need to store the original value + * in the reference + */ + newref->index = index+1; + newref->dirty = false; + + *ref = newref; + + return EOK; +} + + +int ext4_filesystem_put_inode_ref(ext4_inode_ref_t *ref) +{ + int rc; + + if (ref->dirty) { + ref->block->dirty = true; + } + + rc = block_put(ref->block); + free(ref); + + return rc; +} + +int ext4_filesystem_alloc_inode(ext4_filesystem_t *fs, + ext4_inode_ref_t **inode_ref, int flags) +{ + int rc; + + bool is_dir = false; + if (flags & L_DIRECTORY) { + is_dir = true; + } + + // allocate inode + uint32_t index; + rc = ext4_ialloc_alloc_inode(fs, &index, is_dir); + if (rc != EOK) { + return rc; + } + + // TODO extents, dir_index etc... + + rc = ext4_filesystem_get_inode_ref(fs, index, inode_ref); + if (rc != EOK) { + ext4_ialloc_free_inode(fs, index, is_dir); + return rc; + } + + // init inode + ext4_inode_t *inode = (*inode_ref)->inode; + + if (is_dir) { + ext4_inode_set_mode(fs->superblock, inode, EXT4_INODE_MODE_DIRECTORY); + ext4_inode_set_links_count(inode, 1); // '.' entry + } else { + ext4_inode_set_mode(fs->superblock, inode, EXT4_INODE_MODE_FILE); + ext4_inode_set_links_count(inode, 0); + } + + ext4_inode_set_uid(inode, 0); + ext4_inode_set_gid(inode, 0); + ext4_inode_set_size(inode, 0); + ext4_inode_set_access_time(inode, 0); + ext4_inode_set_change_inode_time(inode, 0); + ext4_inode_set_modification_time(inode, 0); + ext4_inode_set_deletion_time(inode, 0); + ext4_inode_set_blocks_count(fs->superblock, inode, 0); + ext4_inode_set_flags(inode, 0); + ext4_inode_set_generation(inode, 0); + + for (uint32_t i = 0; i < EXT4_INODE_BLOCKS; i++) { + inode->blocks[i] = 0; + } + + (*inode_ref)->dirty = true; + + return EOK; +} + +int ext4_filesystem_free_inode(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref) +{ + int rc; + + // release all indirect (no data) blocks + + // 1) Single indirect + uint32_t fblock = ext4_inode_get_indirect_block(inode_ref->inode, 0); + if (fblock != 0) { + rc = ext4_balloc_free_block(fs, inode_ref, fblock); + if (rc != EOK) { + return rc; + } + + ext4_inode_set_indirect_block(inode_ref->inode, 0, 0); + } + + block_t *block; + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + uint32_t count = block_size / sizeof(uint32_t); + + // 2) Double indirect + fblock = ext4_inode_get_indirect_block(inode_ref->inode, 1); + if (fblock != 0) { + rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + uint32_t ind_block; + for (uint32_t offset = 0; offset < count; ++offset) { + ind_block = uint32_t_le2host(((uint32_t*)block->data)[offset]); + + if (ind_block != 0) { + rc = ext4_balloc_free_block(fs, inode_ref, ind_block); + if (rc != EOK) { + block_put(block); + return rc; + } + } + } + + block_put(block); + rc = ext4_balloc_free_block(fs, inode_ref, fblock); + if (rc != EOK) { + return rc; + } + + ext4_inode_set_indirect_block(inode_ref->inode, 1, 0); + } + + + // 3) Tripple indirect + block_t *subblock; + fblock = ext4_inode_get_indirect_block(inode_ref->inode, 2); + if (fblock != 0) { + rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + uint32_t ind_block; + for (uint32_t offset = 0; offset < count; ++offset) { + ind_block = uint32_t_le2host(((uint32_t*)block->data)[offset]); + + if (ind_block != 0) { + rc = block_get(&subblock, fs->device, ind_block, BLOCK_FLAGS_NONE); + if (rc != EOK) { + block_put(block); + return rc; + } + + uint32_t ind_subblock; + for (uint32_t suboffset = 0; suboffset < count; ++suboffset) { + ind_subblock = uint32_t_le2host(((uint32_t*)subblock->data)[suboffset]); + + if (ind_subblock != 0) { + rc = ext4_balloc_free_block(fs, inode_ref, ind_subblock); + if (rc != EOK) { + block_put(subblock); + block_put(block); + return rc; + } + } + + } + block_put(subblock); + + } + + rc = ext4_balloc_free_block(fs, inode_ref, ind_block); + if (rc != EOK) { + block_put(block); + return rc; + } + + + } + + block_put(block); + rc = ext4_balloc_free_block(fs, inode_ref, fblock); + if (rc != EOK) { + return rc; + } + + ext4_inode_set_indirect_block(inode_ref->inode, 2, 0); + } + + inode_ref->dirty = true; + + // Free inode + if (ext4_inode_is_type(fs->superblock, inode_ref->inode, + EXT4_INODE_MODE_DIRECTORY)) { + rc = ext4_ialloc_free_inode(fs, inode_ref->index, true); + } else { + rc = ext4_ialloc_free_inode(fs, inode_ref->index, false); + } + if (rc != EOK) { + return rc; + } + + return EOK; +} + +int ext4_filesystem_truncate_inode(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, aoff64_t new_size) +{ + int rc; + + if (! ext4_inode_can_truncate(fs->superblock, inode_ref->inode)) { + // Unable to truncate + return EINVAL; + } + + aoff64_t old_size = ext4_inode_get_size(fs->superblock, inode_ref->inode); + if (old_size == new_size) { + // Nothing to do + return EOK; + } + + // It's not suppported to make the larger file + if (old_size < new_size) { + return EINVAL; + } + + aoff64_t size_diff = old_size - new_size; + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + uint32_t diff_blocks_count = size_diff / block_size; + if (size_diff % block_size != 0) { + diff_blocks_count++; + } + + uint32_t old_blocks_count = old_size / block_size; + if (old_size % block_size != 0) { + old_blocks_count++; + } + + // starting from 1 because of logical blocks are numbered from 0 + for (uint32_t i = 1; i <= diff_blocks_count; ++i) { + rc = ext4_filesystem_release_inode_block(fs, inode_ref, old_blocks_count - i); + if (rc != EOK) { + return rc; + } + } + + ext4_inode_set_size(inode_ref->inode, new_size); + + inode_ref->dirty = true; + + return EOK; +} + +int ext4_filesystem_get_inode_data_block_index(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, aoff64_t iblock, uint32_t* fblock) +{ + int rc; + + + uint32_t current_block; + + /* Handle inode using extents */ + if (ext4_superblock_has_feature_incompatible(fs->superblock, EXT4_FEATURE_INCOMPAT_EXTENTS) && + ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS)) { + rc = ext4_extent_find_block(fs, inode_ref, iblock, ¤t_block); + + if (rc != EOK) { + return rc; + } + + *fblock = current_block; + return EOK; + + } + + ext4_inode_t *inode = inode_ref->inode; + + /* Handle simple case when we are dealing with direct reference */ + if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) { + current_block = ext4_inode_get_direct_block(inode, (uint32_t)iblock); + *fblock = current_block; + return EOK; + } + + /* Determine the indirection level needed to get the desired block */ + int level = -1; + for (int i = 1; i < 4; i++) { + if (iblock < fs->inode_block_limits[i]) { + level = i; + break; + } + } + + if (level == -1) { + return EIO; + } + + /* Compute offsets for the topmost level */ + aoff64_t block_offset_in_level = iblock - fs->inode_block_limits[level-1]; + current_block = ext4_inode_get_indirect_block(inode, level-1); + uint32_t offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1]; + + if (current_block == 0) { + *fblock = 0; + return EOK; + } + + block_t *block; + + /* 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; + } + + 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 %= fs->inode_blocks_per_level[level]; + offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1]; + } + + *fblock = current_block; + + return EOK; +} + + +int ext4_filesystem_set_inode_data_block_index(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, aoff64_t iblock, uint32_t fblock) +{ + int rc; + + + /* Handle inode using extents */ + if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_INCOMPAT_EXTENTS) && + ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS)) { + // TODO + return ENOTSUP; + } + + /* Handle simple case when we are dealing with direct reference */ + if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) { + ext4_inode_set_direct_block(inode_ref->inode, (uint32_t)iblock, fblock); + inode_ref->dirty = true; + return EOK; + } + + /* Determine the indirection level needed to get the desired block */ + int level = -1; + for (int i = 1; i < 4; i++) { + if (iblock < fs->inode_block_limits[i]) { + level = i; + break; + } + } + + if (level == -1) { + return EIO; + } + + uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); + + /* Compute offsets for the topmost level */ + aoff64_t block_offset_in_level = iblock - fs->inode_block_limits[level-1]; + uint32_t current_block = ext4_inode_get_indirect_block(inode_ref->inode, level-1); + uint32_t offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1]; + + uint32_t new_block_addr; + block_t *block, *new_block; + + if (current_block == 0) { + rc = ext4_balloc_alloc_block(fs, inode_ref, &new_block_addr); + if (rc != EOK) { + return rc; + } + + ext4_inode_set_indirect_block(inode_ref->inode, level - 1, new_block_addr); + + inode_ref->dirty = true; + + rc = block_get(&new_block, fs->device, new_block_addr, BLOCK_FLAGS_NOREAD); + if (rc != EOK) { + ext4_balloc_free_block(fs, inode_ref, new_block_addr); + return rc; + } + + memset(new_block->data, 0, block_size); + new_block->dirty = true; + + rc = block_put(new_block); + if (rc != EOK) { + return rc; + } + + current_block = new_block_addr; + } + + /* 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; + } + + current_block = uint32_t_le2host(((uint32_t*)block->data)[offset_in_block]); + + if ((level > 1) && (current_block == 0)) { + rc = ext4_balloc_alloc_block(fs, inode_ref, &new_block_addr); + if (rc != EOK) { + block_put(block); + return rc; + } + + rc = block_get(&new_block, fs->device, new_block_addr, BLOCK_FLAGS_NOREAD); + if (rc != EOK) { + block_put(block); + return rc; + } + + memset(new_block->data, 0, block_size); + new_block->dirty = true; + + rc = block_put(new_block); + if (rc != EOK) { + block_put(block); + return rc; + } + + ((uint32_t*)block->data)[offset_in_block] = host2uint32_t_le(new_block_addr); + block->dirty = true; + current_block = new_block_addr; + } + + if (level == 1) { + ((uint32_t*)block->data)[offset_in_block] = host2uint32_t_le(fblock); + block->dirty = true; + } + + rc = block_put(block); + if (rc != EOK) { + return rc; + } + + 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 %= fs->inode_blocks_per_level[level]; + offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1]; + } + + return EOK; +} + +int ext4_filesystem_release_inode_block(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref, uint32_t iblock) +{ + int rc; + + + /* TODO handle extents */ + + + uint32_t fblock; + ext4_inode_t *inode = inode_ref->inode; + + /* Handle simple case when we are dealing with direct reference */ + if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) { + fblock = ext4_inode_get_direct_block(inode, iblock); + // Sparse file + if (fblock == 0) { + return EOK; + } + + ext4_inode_set_direct_block(inode, iblock, 0); + return ext4_balloc_free_block(fs, inode_ref, fblock); + } + + + /* Determine the indirection level needed to get the desired block */ + int level = -1; + for (int i = 1; i < 4; i++) { + if (iblock < fs->inode_block_limits[i]) { + level = i; + break; + } + } + + if (level == -1) { + return EIO; + } + + /* Compute offsets for the topmost level */ + aoff64_t block_offset_in_level = iblock - fs->inode_block_limits[level-1]; + uint32_t current_block = ext4_inode_get_indirect_block(inode, level-1); + uint32_t offset_in_block = block_offset_in_level / fs->inode_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 + */ + block_t *block; + while (level > 0) { + rc = block_get(&block, fs->device, current_block, 0); + if (rc != EOK) { + return rc; + } + + current_block = uint32_t_le2host(((uint32_t*)block->data)[offset_in_block]); + + // Set zero + if (level == 1) { + ((uint32_t*)block->data)[offset_in_block] = host2uint32_t_le(0); + block->dirty = true; + } + + rc = block_put(block); + if (rc != EOK) { + return rc; + } + + 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 %= fs->inode_blocks_per_level[level]; + offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1]; + } + + fblock = current_block; + + if (fblock == 0) { + return EOK; + } + + return ext4_balloc_free_block(fs, inode_ref, fblock); + +} + +int ext4_filesystem_add_orphan(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref) +{ + uint32_t next_orphan = ext4_superblock_get_last_orphan(fs->superblock); + ext4_inode_set_deletion_time(inode_ref->inode, next_orphan); + ext4_superblock_set_last_orphan(fs->superblock, inode_ref->index); + inode_ref->dirty = true; + + return EOK; +} + +int ext4_filesystem_delete_orphan(ext4_filesystem_t *fs, + ext4_inode_ref_t *inode_ref) +{ + int rc; + + uint32_t last_orphan = ext4_superblock_get_last_orphan(fs->superblock); + assert(last_orphan > 0); + + uint32_t next_orphan = ext4_inode_get_deletion_time(inode_ref->inode); + + if (last_orphan == inode_ref->index) { + ext4_superblock_set_last_orphan(fs->superblock, next_orphan); + ext4_inode_set_deletion_time(inode_ref->inode, 0); + inode_ref->dirty = true; + return EOK; + } + + ext4_inode_ref_t *current; + rc = ext4_filesystem_get_inode_ref(fs, last_orphan, ¤t); + if (rc != EOK) { + return rc; + } + next_orphan = ext4_inode_get_deletion_time(current->inode); + + bool found; + + while (next_orphan != 0) { + if (next_orphan == inode_ref->index) { + next_orphan = ext4_inode_get_deletion_time(inode_ref->inode); + ext4_inode_set_deletion_time(current->inode, next_orphan); + current->dirty = true; + found = true; + break; + } + + ext4_filesystem_put_inode_ref(current); + + rc = ext4_filesystem_get_inode_ref(fs, next_orphan, ¤t); + if (rc != EOK) { + return rc; + } + next_orphan = ext4_inode_get_deletion_time(current->inode); + + } + + ext4_inode_set_deletion_time(inode_ref->inode, 0); + + rc = ext4_filesystem_put_inode_ref(current); + if (rc != EOK) { + return rc; + } + + if (!found) { + return ENOENT; + } + + return EOK; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_filesystem.h =================================================================== --- uspace/lib/ext4/libext4_filesystem.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_filesystem.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_FILESYSTEM_H_ +#define LIBEXT4_LIBEXT4_FILESYSTEM_H_ + +#include +#include "libext4_types.h" + +extern int ext4_filesystem_init(ext4_filesystem_t *, service_id_t); +extern int ext4_filesystem_fini(ext4_filesystem_t *fs, bool); +extern int ext4_filesystem_check_sanity(ext4_filesystem_t *fs); +extern int ext4_filesystem_check_features(ext4_filesystem_t *, bool *); +extern int ext4_filesystem_get_block_group_ref(ext4_filesystem_t *, uint32_t, + ext4_block_group_ref_t **); +extern int ext4_filesystem_put_block_group_ref(ext4_block_group_ref_t *); +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_alloc_inode(ext4_filesystem_t *, + ext4_inode_ref_t **, int); +extern int ext4_filesystem_free_inode(ext4_filesystem_t *, ext4_inode_ref_t *); +extern int ext4_filesystem_truncate_inode(ext4_filesystem_t *, + ext4_inode_ref_t *, aoff64_t); +extern int ext4_filesystem_get_inode_data_block_index(ext4_filesystem_t *, + ext4_inode_ref_t *, aoff64_t iblock, uint32_t *); +extern int ext4_filesystem_set_inode_data_block_index(ext4_filesystem_t *, + ext4_inode_ref_t *, aoff64_t, uint32_t); +extern int ext4_filesystem_release_inode_block(ext4_filesystem_t *, + ext4_inode_ref_t *, uint32_t); +extern int ext4_filesystem_add_orphan(ext4_filesystem_t *, + ext4_inode_ref_t *); +extern int ext4_filesystem_delete_orphan(ext4_filesystem_t *, + ext4_inode_ref_t *); +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_hash.c =================================================================== --- uspace/lib/ext4/libext4_hash.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_hash.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,315 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_hash.c + * @brief Hashing algorithms for ext4 HTree. + */ + +#include +#include + +#include "libext4.h" + +#define TEA_DELTA 0x9E3779B9 + + +/* F, G and H are basic MD4 functions: selection, majority, parity */ +#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) +#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) +#define H(x, y, z) ((x) ^ (y) ^ (z)) + + +/* + * The generic round function. The application is so specific that + * we don't bother protecting all the arguments with parens, as is generally + * good macro practice, in favor of extra legibility. + * Rotation is separate from addition to prevent recomputation + */ +#define ROUND(f, a, b, c, d, x, s) \ + (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s))) +#define K1 0 +#define K2 013240474631UL +#define K3 015666365641UL + + +static void tea_transform(uint32_t buf[4], uint32_t const in[]) +{ + uint32_t sum = 0; + uint32_t b0 = buf[0], b1 = buf[1]; + uint32_t a = in[0], b = in[1], c = in[2], d = in[3]; + int n = 16; + + do { + sum += TEA_DELTA; + b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); + b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); + } while (--n); + + buf[0] += b0; + buf[1] += b1; +} + + +static void half_md4_transform(uint32_t buf[4], const uint32_t in[8]) +{ + uint32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3]; + + /* Round 1 */ + ROUND(F, a, b, c, d, in[0] + K1, 3); + ROUND(F, d, a, b, c, in[1] + K1, 7); + ROUND(F, c, d, a, b, in[2] + K1, 11); + ROUND(F, b, c, d, a, in[3] + K1, 19); + ROUND(F, a, b, c, d, in[4] + K1, 3); + ROUND(F, d, a, b, c, in[5] + K1, 7); + ROUND(F, c, d, a, b, in[6] + K1, 11); + ROUND(F, b, c, d, a, in[7] + K1, 19); + + /* Round 2 */ + ROUND(G, a, b, c, d, in[1] + K2, 3); + ROUND(G, d, a, b, c, in[3] + K2, 5); + ROUND(G, c, d, a, b, in[5] + K2, 9); + ROUND(G, b, c, d, a, in[7] + K2, 13); + ROUND(G, a, b, c, d, in[0] + K2, 3); + ROUND(G, d, a, b, c, in[2] + K2, 5); + ROUND(G, c, d, a, b, in[4] + K2, 9); + ROUND(G, b, c, d, a, in[6] + K2, 13); + + /* Round 3 */ + ROUND(H, a, b, c, d, in[3] + K3, 3); + ROUND(H, d, a, b, c, in[7] + K3, 9); + ROUND(H, c, d, a, b, in[2] + K3, 11); + ROUND(H, b, c, d, a, in[6] + K3, 15); + ROUND(H, a, b, c, d, in[1] + K3, 3); + ROUND(H, d, a, b, c, in[5] + K3, 9); + ROUND(H, c, d, a, b, in[0] + K3, 11); + ROUND(H, b, c, d, a, in[4] + K3, 15); + + buf[0] += a; + buf[1] += b; + buf[2] += c; + buf[3] += d; + +} + +static uint32_t hash_unsigned(const char *name, int len) +{ + uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + const unsigned char *ucp = (const unsigned char *) name; + + while (len--) { + hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); + + if (hash & 0x80000000) { + hash -= 0x7fffffff; + } + hash1 = hash0; + hash0 = hash; + } + return hash0 << 1; +} + +static uint32_t hash_signed(const char *name, int len) +{ + uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + const signed char *scp = (const signed char *) name; + + while (len--) { + hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); + + if (hash & 0x80000000) { + hash -= 0x7fffffff; + } + hash1 = hash0; + hash0 = hash; + } + return hash0 << 1; +} + +static void str2hashbuf_signed(const char *msg, int len, uint32_t *buf, int num) +{ + uint32_t pad, val; + int i; + const signed char *scp = (const signed char *) msg; + + pad = (uint32_t)len | ((uint32_t)len << 8); + pad |= pad << 16; + + val = pad; + if (len > num*4) { + len = num * 4; + } + + for (i = 0; i < len; i++) { + if ((i % 4) == 0) { + val = pad; + } + val = ((int) scp[i]) + (val << 8); + if ((i % 4) == 3) { + *buf++ = val; + val = pad; + num--; + } + } + + if (--num >= 0) { + *buf++ = val; + } + + while (--num >= 0) { + *buf++ = pad; + } +} + + +static void str2hashbuf_unsigned(const char *msg, int len, uint32_t *buf, int num) +{ + uint32_t pad, val; + int i; + const unsigned char *ucp = (const unsigned char *) msg; + + pad = (uint32_t)len | ((uint32_t)len << 8); + pad |= pad << 16; + + val = pad; + if (len > num*4) { + len = num * 4; + } + + for (i = 0; i < len; i++) { + if ((i % 4) == 0) { + val = pad; + } + val = ((int) ucp[i]) + (val << 8); + if ((i % 4) == 3) { + *buf++ = val; + val = pad; + num--; + } + } + + if (--num >= 0) { + *buf++ = val; + } + + while (--num >= 0) { + *buf++ = pad; + } +} + +int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name) +{ + uint32_t hash = 0; + uint32_t minor_hash = 0; + const char *p; + int i; + uint32_t in[8], buf[4]; + void (*str2hashbuf)(const char *, int, uint32_t *, int) = str2hashbuf_signed; + + /* Initialize the default seed for the hash checksum functions */ + buf[0] = 0x67452301; + buf[1] = 0xefcdab89; + buf[2] = 0x98badcfe; + buf[3] = 0x10325476; + + /* Check if the seed is all zero's */ + if (hinfo->seed) { + for (i = 0; i < 4; i++) { + if (hinfo->seed[i] != 0) { + break; + } + } + if (i < 4) { + memcpy(buf, hinfo->seed, sizeof(buf)); + } + } + + switch (hinfo->hash_version) { + case EXT4_HASH_VERSION_LEGACY_UNSIGNED: + hash = hash_unsigned(name, len); + break; + + case EXT4_HASH_VERSION_LEGACY: + hash = hash_signed(name, len); + break; + + + case EXT4_HASH_VERSION_HALF_MD4_UNSIGNED: + str2hashbuf = str2hashbuf_unsigned; + + case EXT4_HASH_VERSION_HALF_MD4: + p = name; + while (len > 0) { + (*str2hashbuf)(p, len, in, 8); + half_md4_transform(buf, in); + len -= 32; + p += 32; + } + minor_hash = buf[2]; + hash = buf[1]; + break; + + + case EXT4_HASH_VERSION_TEA_UNSIGNED: + str2hashbuf = str2hashbuf_unsigned; + + case EXT4_HASH_VERSION_TEA: + p = name; + while (len > 0) { + (*str2hashbuf)(p, len, in, 4); + tea_transform(buf, in); + len -= 16; + p += 16; + } + hash = buf[0]; + minor_hash = buf[1]; + break; + + default: + hinfo->hash = 0; + return EINVAL; + } + + hash = hash & ~1; + if (hash == (EXT4_DIRECTORY_HTREE_EOF << 1)) { + hash = (EXT4_DIRECTORY_HTREE_EOF-1) << 1; + } + + hinfo->hash = hash; + hinfo->minor_hash = minor_hash; + + return EOK; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_hash.h =================================================================== --- uspace/lib/ext4/libext4_hash.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_hash.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_HASH_H_ +#define LIBEXT4_LIBEXT4_HASH_H_ + +#include +#include "libext4_types.h" + +extern int ext4_hash_string(ext4_hash_info_t *, int, const char *); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_ialloc.c =================================================================== --- uspace/lib/ext4/libext4_ialloc.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_ialloc.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,220 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_ialloc.c + * @brief Inode (de)allocation operations. + */ + +#include +#include +#include "libext4.h" + +static uint32_t ext4_ialloc_inode2index_in_group(ext4_superblock_t *sb, + uint32_t inode) +{ + uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); + return (inode - 1) % inodes_per_group; +} + +static uint32_t ext4_ialloc_index_in_group2inode(ext4_superblock_t *sb, + uint32_t index, uint32_t bgid) +{ + uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); + return bgid * inodes_per_group + (index + 1); +} + +static uint32_t ext4_ialloc_get_bgid_of_inode(ext4_superblock_t *sb, + uint32_t inode) +{ + uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); + return (inode - 1) / inodes_per_group; + +} + + +int ext4_ialloc_free_inode(ext4_filesystem_t *fs, uint32_t index, bool is_dir) +{ + int rc; + + ext4_superblock_t *sb = fs->superblock; + + uint32_t block_group = ext4_ialloc_get_bgid_of_inode(sb, index); + + ext4_block_group_ref_t *bg_ref; + rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref); + if (rc != EOK) { + return rc; + } + + uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap( + bg_ref->block_group, sb); + block_t *bitmap_block; + rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + uint32_t index_in_group = ext4_ialloc_inode2index_in_group(sb, index); + ext4_bitmap_free_bit(bitmap_block->data, index_in_group); + bitmap_block->dirty = true; + + rc = block_put(bitmap_block); + if (rc != EOK) { + // Error in saving bitmap + ext4_filesystem_put_block_group_ref(bg_ref); + return rc; + } + + // if inode is directory, decrement used directories count + if (is_dir) { + uint32_t bg_used_dirs = ext4_block_group_get_used_dirs_count( + bg_ref->block_group, sb); + bg_used_dirs--; + ext4_block_group_set_used_dirs_count( + bg_ref->block_group, sb, bg_used_dirs); + } + + // Update block group free inodes count + uint32_t free_inodes = ext4_block_group_get_free_inodes_count( + bg_ref->block_group, sb); + free_inodes++; + ext4_block_group_set_free_inodes_count(bg_ref->block_group, + sb, free_inodes); + bg_ref->dirty = true; + + rc = ext4_filesystem_put_block_group_ref(bg_ref); + if (rc != EOK) { + return rc; + } + + // Update superblock free inodes count + uint32_t sb_free_inodes = ext4_superblock_get_free_inodes_count(sb); + sb_free_inodes++; + ext4_superblock_set_free_inodes_count(sb, sb_free_inodes); + + return EOK; +} + +int ext4_ialloc_alloc_inode(ext4_filesystem_t *fs, uint32_t *index, bool is_dir) +{ + int rc; + + ext4_superblock_t *sb = fs->superblock; + + uint32_t bgid = 0; + uint32_t bg_count = ext4_superblock_get_block_group_count(sb); + uint32_t sb_free_inodes = ext4_superblock_get_free_inodes_count(sb); + uint32_t avg_free_inodes = sb_free_inodes / bg_count; + + while (bgid < bg_count) { + + ext4_block_group_ref_t *bg_ref; + rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref); + if (rc != EOK) { + return rc; + } + ext4_block_group_t *bg = bg_ref->block_group; + + uint32_t free_blocks = ext4_block_group_get_free_blocks_count(bg, sb); + uint32_t free_inodes = ext4_block_group_get_free_inodes_count(bg, sb); + uint32_t used_dirs = ext4_block_group_get_used_dirs_count(bg, sb); + + if ((free_inodes >= avg_free_inodes) && (free_blocks > 0)) { + + uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap( + bg_ref->block_group, sb); + + block_t *bitmap_block; + rc = block_get(&bitmap_block, fs->device, + bitmap_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + // Alloc bit + uint32_t inodes_in_group = ext4_superblock_get_inodes_in_group(sb, bgid); + uint32_t index_in_group; + rc = ext4_bitmap_find_free_bit_and_set( + bitmap_block->data, 0, &index_in_group, inodes_in_group); + + // TODO check + if (rc == ENOSPC) { + block_put(bitmap_block); + ext4_filesystem_put_block_group_ref(bg_ref); + continue; + } + + bitmap_block->dirty = true; + + rc = block_put(bitmap_block); + if (rc != EOK) { + return rc; + } + + // Modify filesystem counters + free_inodes--; + ext4_block_group_set_free_inodes_count(bg, sb, free_inodes); + + if (is_dir) { + used_dirs++; + ext4_block_group_set_used_dirs_count(bg, sb, used_dirs); + } + + bg_ref->dirty = true; + + rc = ext4_filesystem_put_block_group_ref(bg_ref); + if (rc != EOK) { + // TODO + EXT4FS_DBG("ERRRRR"); + } + + sb_free_inodes--; + ext4_superblock_set_free_inodes_count(sb, sb_free_inodes); + + *index = ext4_ialloc_index_in_group2inode(sb, index_in_group, bgid); + + return EOK; + + } + + // Not modified + ext4_filesystem_put_block_group_ref(bg_ref); + ++bgid; + } + + return ENOSPC; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_ialloc.h =================================================================== --- uspace/lib/ext4/libext4_ialloc.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_ialloc.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_IALLOC_H_ +#define LIBEXT4_LIBEXT4_IALLOC_H_ + +#include "libext4_types.h" + +extern int ext4_ialloc_free_inode(ext4_filesystem_t *, uint32_t, bool); +extern int ext4_ialloc_alloc_inode(ext4_filesystem_t *, uint32_t *, bool); +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_inode.c =================================================================== --- uspace/lib/ext4/libext4_inode.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_inode.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,332 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_inode.c + * @brief Ext4 inode structure operations. + */ + +#include +#include +#include +#include "libext4.h" + +static uint32_t ext4_inode_block_bits_count(uint32_t block_size) +{ + uint32_t bits = 8; + uint32_t size = block_size; + + do { + bits++; + size = size >> 1; + } while (size > 256); + + return bits; +} + +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); +} + +void ext4_inode_set_mode(ext4_superblock_t *sb, ext4_inode_t *inode, uint32_t mode) +{ + inode->mode = host2uint16_t_le((mode << 16) >> 16); + + if (ext4_superblock_get_creator_os(sb) == EXT4_SUPERBLOCK_OS_HURD) { + inode->osd2.hurd2.mode_high = host2uint16_t_le(mode >> 16); + } +} + +uint32_t ext4_inode_get_uid(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->uid); +} + +void ext4_inode_set_uid(ext4_inode_t *inode, uint32_t uid) +{ + inode->uid = host2uint32_t_le(uid); +} + +uint64_t ext4_inode_get_size(ext4_superblock_t *sb, ext4_inode_t *inode) +{ + 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); +} + +void ext4_inode_set_size(ext4_inode_t *inode, uint64_t value) { + inode->size_lo = host2uint32_t_le((value << 32) >> 32); + inode->size_hi = host2uint32_t_le(value >> 32); +} + +uint32_t ext4_inode_get_access_time(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->access_time); +} + +void ext4_inode_set_access_time(ext4_inode_t *inode, uint32_t time) +{ + inode->access_time = host2uint32_t_le(time); +} + +uint32_t ext4_inode_get_change_inode_time(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->change_inode_time); +} + +void ext4_inode_set_change_inode_time(ext4_inode_t *inode, uint32_t time) +{ + inode->change_inode_time = host2uint32_t_le(time); +} + +uint32_t ext4_inode_get_modification_time(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->modification_time); +} + +void ext4_inode_set_modification_time(ext4_inode_t *inode, uint32_t time) +{ + inode->modification_time = host2uint32_t_le(time); +} + +uint32_t ext4_inode_get_deletion_time(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->deletion_time); +} + +void ext4_inode_set_deletion_time(ext4_inode_t *inode, uint32_t time) +{ + inode->deletion_time = host2uint32_t_le(time); +} + +uint32_t ext4_inode_get_gid(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->gid); +} + +void ext4_inode_set_gid(ext4_inode_t *inode, uint32_t gid) +{ + inode->gid = host2uint32_t_le(gid); +} + +uint16_t ext4_inode_get_links_count(ext4_inode_t *inode) +{ + return uint16_t_le2host(inode->links_count); +} + +void ext4_inode_set_links_count(ext4_inode_t *inode, uint16_t count) +{ + inode->links_count = host2uint16_t_le(count); +} + +uint64_t ext4_inode_get_blocks_count(ext4_superblock_t *sb, ext4_inode_t *inode) +{ + if (ext4_superblock_has_feature_read_only(sb, EXT4_FEATURE_RO_COMPAT_HUGE_FILE)) { + + /* 48-bit field */ + uint64_t count = ((uint64_t)uint16_t_le2host(inode->osd2.linux2.blocks_high)) << 32 | + uint32_t_le2host(inode->blocks_count_lo); + + if (ext4_inode_has_flag(inode, EXT4_INODE_FLAG_HUGE_FILE)) { + uint32_t block_size = ext4_superblock_get_block_size(sb); + uint32_t block_bits = ext4_inode_block_bits_count(block_size); + return count << (block_bits - 9); + } else { + return count; + } + } else { + return uint32_t_le2host(inode->blocks_count_lo); + } + +} + +int ext4_inode_set_blocks_count(ext4_superblock_t *sb, ext4_inode_t *inode, + uint64_t count) +{ + // 32-bit maximum + uint64_t max = 0; + max = ~max >> 32; + + if (count <= max) { + inode->blocks_count_lo = host2uint32_t_le(count); + inode->osd2.linux2.blocks_high = 0; + ext4_inode_clear_flag(inode, EXT4_INODE_FLAG_HUGE_FILE); + return EOK; + } + + if (!ext4_superblock_has_feature_read_only(sb, EXT4_FEATURE_RO_COMPAT_HUGE_FILE)) { + return EINVAL; + } + + // 48-bit maximum + max = 0; + max = ~max >> 16; + + if (count <= max) { + inode->blocks_count_lo = host2uint32_t_le(count); + inode->osd2.linux2.blocks_high = host2uint16_t_le(count >> 32); + ext4_inode_clear_flag(inode, EXT4_INODE_FLAG_HUGE_FILE); + } else { + uint32_t block_size = ext4_superblock_get_block_size(sb); + uint32_t block_bits = ext4_inode_block_bits_count(block_size); + ext4_inode_set_flag(inode, EXT4_INODE_FLAG_HUGE_FILE); + count = count >> (block_bits - 9); + inode->blocks_count_lo = host2uint32_t_le(count); + inode->osd2.linux2.blocks_high = host2uint16_t_le(count >> 32); + } + return EOK; +} + +uint32_t ext4_inode_get_flags(ext4_inode_t *inode) { + return uint32_t_le2host(inode->flags); +} + +void ext4_inode_set_flags(ext4_inode_t *inode, uint32_t flags) { + inode->flags = host2uint32_t_le(flags); +} + +uint32_t ext4_inode_get_generation(ext4_inode_t *inode) +{ + return uint32_t_le2host(inode->generation); +} + +void ext4_inode_set_generation(ext4_inode_t *inode, uint32_t generation) +{ + inode->generation = host2uint32_t_le(generation); +} + +uint64_t ext4_inode_get_file_acl(ext4_inode_t *inode, ext4_superblock_t *sb) +{ + if (ext4_superblock_get_creator_os(sb) == EXT4_SUPERBLOCK_OS_LINUX) { + return ((uint32_t)uint16_t_le2host(inode->osd2.linux2.file_acl_high)) << 16 | + (uint32_t_le2host(inode->file_acl_lo)); + } + + return uint32_t_le2host(inode->file_acl_lo); +} + +void ext4_inode_set_file_acl(ext4_inode_t *inode, ext4_superblock_t *sb, + uint64_t file_acl) +{ + inode->file_acl_lo = host2uint32_t_le((file_acl << 32) >> 32); + + if (ext4_superblock_get_creator_os(sb) == EXT4_SUPERBLOCK_OS_LINUX) { + inode->osd2.linux2.file_acl_high = host2uint16_t_le(file_acl >> 32); + } +} + +/***********************************************************************/ + +uint32_t ext4_inode_get_direct_block(ext4_inode_t *inode, uint32_t idx) +{ + assert(idx < EXT4_INODE_DIRECT_BLOCK_COUNT); + return uint32_t_le2host(inode->blocks[idx]); +} + +void ext4_inode_set_direct_block(ext4_inode_t *inode, uint32_t idx, uint32_t fblock) +{ + assert(idx < EXT4_INODE_DIRECT_BLOCK_COUNT); + inode->blocks[idx] = host2uint32_t_le(fblock); +} + +uint32_t ext4_inode_get_indirect_block(ext4_inode_t *inode, uint32_t idx) +{ + return uint32_t_le2host(inode->blocks[idx + EXT4_INODE_INDIRECT_BLOCK]); +} + +void ext4_inode_set_indirect_block(ext4_inode_t *inode, uint32_t idx, uint32_t fblock) +{ + inode->blocks[idx + EXT4_INODE_INDIRECT_BLOCK] = host2uint32_t_le(fblock); +} + +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; +} + + +ext4_extent_header_t * ext4_inode_get_extent_header(ext4_inode_t *inode) +{ + return (ext4_extent_header_t *)inode->blocks; +} + +// Flags operations +bool ext4_inode_has_flag(ext4_inode_t *inode, uint32_t flag) +{ + if (ext4_inode_get_flags(inode) & flag) { + return true; + } + return false; +} + +void ext4_inode_clear_flag(ext4_inode_t *inode, uint32_t clear_flag) +{ + uint32_t flags = ext4_inode_get_flags(inode); + flags = flags & (~clear_flag); + ext4_inode_set_flags(inode, flags); +} + +void ext4_inode_set_flag(ext4_inode_t *inode, uint32_t set_flag) +{ + uint32_t flags = ext4_inode_get_flags(inode); + flags = flags | set_flag; + ext4_inode_set_flags(inode, flags); +} + +bool ext4_inode_can_truncate(ext4_superblock_t *sb, ext4_inode_t *inode) +{ + if (ext4_inode_has_flag(inode, EXT4_INODE_FLAG_APPEND) + || ext4_inode_has_flag(inode, EXT4_INODE_FLAG_IMMUTABLE)) { + return false; + } + + if (ext4_inode_is_type(sb, inode, EXT4_INODE_MODE_FILE) + || ext4_inode_is_type(sb, inode, EXT4_INODE_MODE_DIRECTORY)) { + return true; + } + + return false; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_inode.h =================================================================== --- uspace/lib/ext4/libext4_inode.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_inode.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_INODE_H_ +#define LIBEXT4_LIBEXT4_INODE_H_ + +#include +#include +#include "libext4_types.h" + +extern uint32_t ext4_inode_get_mode(ext4_superblock_t *, ext4_inode_t *); +extern void ext4_inode_set_mode(ext4_superblock_t *, ext4_inode_t *, uint32_t); +extern uint32_t ext4_inode_get_uid(ext4_inode_t *); +extern void ext4_inode_set_uid(ext4_inode_t *, uint32_t); +extern uint64_t ext4_inode_get_size(ext4_superblock_t *, ext4_inode_t *); +extern void ext4_inode_set_size(ext4_inode_t *, uint64_t); +extern uint32_t ext4_inode_get_access_time(ext4_inode_t *); +extern void ext4_inode_set_access_time(ext4_inode_t *, uint32_t); +extern uint32_t ext4_inode_get_change_inode_time(ext4_inode_t *); +extern void ext4_inode_set_change_inode_time(ext4_inode_t *, uint32_t); +extern uint32_t ext4_inode_get_modification_time(ext4_inode_t *); +extern void ext4_inode_set_modification_time(ext4_inode_t *, uint32_t); +extern uint32_t ext4_inode_get_deletion_time(ext4_inode_t *); +extern void ext4_inode_set_deletion_time(ext4_inode_t *, uint32_t); +extern uint32_t ext4_inode_get_gid(ext4_inode_t *); +extern void ext4_inode_set_gid(ext4_inode_t *, uint32_t); +extern uint16_t ext4_inode_get_links_count(ext4_inode_t *); +extern void ext4_inode_set_links_count(ext4_inode_t *, uint16_t); +extern uint64_t ext4_inode_get_blocks_count(ext4_superblock_t *, ext4_inode_t *); +extern int ext4_inode_set_blocks_count(ext4_superblock_t *, ext4_inode_t *, uint64_t); +extern uint32_t ext4_inode_get_flags(ext4_inode_t *); +extern void ext4_inode_set_flags(ext4_inode_t *, uint32_t); +extern uint32_t ext4_inode_get_generation(ext4_inode_t *); +extern void ext4_inode_set_generation(ext4_inode_t *, uint32_t); +extern uint64_t ext4_inode_get_file_acl(ext4_inode_t *, ext4_superblock_t *); +extern void ext4_inode_set_file_acl(ext4_inode_t *, ext4_superblock_t *, uint64_t); +/* +uint16_t extra_isize; +uint32_t ctime_extra; // Extra change time (nsec << 2 | epoch) +uint32_t mtime_extra; // Extra Modification time (nsec << 2 | epoch) +uint32_t atime_extra; // Extra Access time (nsec << 2 | epoch) +uint32_t crtime; // File creation time +uint32_t crtime_extra; // Extra file creation time (nsec << 2 | epoch) +uint32_t version_hi; // High 32 bits for 64-bit version +*/ + +/******************************************/ + +extern uint32_t ext4_inode_get_direct_block(ext4_inode_t *, uint32_t); +extern void ext4_inode_set_direct_block(ext4_inode_t *, uint32_t, uint32_t); +extern uint32_t ext4_inode_get_indirect_block(ext4_inode_t *, uint32_t); +extern void ext4_inode_set_indirect_block(ext4_inode_t *, uint32_t, uint32_t); +extern ext4_extent_header_t * ext4_inode_get_extent_header(ext4_inode_t *); +extern bool ext4_inode_is_type(ext4_superblock_t *, ext4_inode_t *, uint32_t); +extern bool ext4_inode_has_flag(ext4_inode_t *, uint32_t); +extern void ext4_inode_clear_flag(ext4_inode_t *, uint32_t); +extern void ext4_inode_set_flag(ext4_inode_t *, uint32_t); +extern bool ext4_inode_can_truncate(ext4_superblock_t *, ext4_inode_t *); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_superblock.c =================================================================== --- uspace/lib/ext4/libext4_superblock.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_superblock.c (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,543 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_superblock.c + * @brief Ext4 superblock operations. + */ + +#include +#include +#include +#include +#include "libext4.h" + +uint32_t ext4_superblock_get_inodes_count(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->inodes_count); +} + +void ext4_superblock_set_inodes_count(ext4_superblock_t *sb, uint32_t count) +{ + sb->inodes_count = host2uint32_t_le(count); +} + +uint64_t ext4_superblock_get_blocks_count(ext4_superblock_t *sb) +{ + return ((uint64_t)uint32_t_le2host(sb->blocks_count_hi) << 32) | + uint32_t_le2host(sb->blocks_count_lo); +} + +void ext4_superblock_set_blocks_count(ext4_superblock_t *sb, uint64_t count) +{ + sb->blocks_count_lo = host2uint32_t_le((count << 32) >> 32); + sb->blocks_count_hi = host2uint32_t_le(count >> 32); +} + +uint64_t ext4_superblock_get_reserved_blocks_count(ext4_superblock_t *sb) +{ + return ((uint64_t)uint32_t_le2host(sb->reserved_blocks_count_hi) << 32) | + uint32_t_le2host(sb->reserved_blocks_count_lo); +} + +void ext4_superblock_set_reserved_blocks_count(ext4_superblock_t *sb, uint64_t count) +{ + sb->reserved_blocks_count_lo = host2uint32_t_le((count << 32) >> 32); + sb->reserved_blocks_count_hi = host2uint32_t_le(count >> 32); +} + +uint64_t ext4_superblock_get_free_blocks_count(ext4_superblock_t *sb) +{ + return ((uint64_t)uint32_t_le2host(sb->free_blocks_count_hi) << 32) | + uint32_t_le2host(sb->free_blocks_count_lo); +} + +void ext4_superblock_set_free_blocks_count(ext4_superblock_t *sb, uint64_t count) +{ + sb->free_blocks_count_lo = host2uint32_t_le((count << 32) >> 32); + sb->free_blocks_count_hi = host2uint32_t_le(count >> 32); +} + +uint32_t ext4_superblock_get_free_inodes_count(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->free_inodes_count); +} + +void ext4_superblock_set_free_inodes_count(ext4_superblock_t *sb, uint32_t count) +{ + sb->free_inodes_count = host2uint32_t_le(count); +} + +uint32_t ext4_superblock_get_first_data_block(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->first_data_block); +} + +void ext4_superblock_set_first_data_block(ext4_superblock_t *sb, uint32_t first) +{ + sb->first_data_block = host2uint32_t_le(first); +} + +uint32_t ext4_superblock_get_log_block_size(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->log_block_size); +} + +void ext4_superblock_set_log_block_size(ext4_superblock_t *sb, uint32_t log_size) +{ + sb->log_block_size = host2uint32_t_le(log_size); +} + +uint32_t ext4_superblock_get_block_size(ext4_superblock_t *sb) +{ + return 1024 << ext4_superblock_get_log_block_size(sb); +} + +void ext4_superblock_set_block_size(ext4_superblock_t *sb, uint32_t size) +{ + uint32_t log = 0; + uint32_t tmp = size / EXT4_MIN_BLOCK_SIZE; + + tmp >>= 1; + while (tmp) { + log++; + tmp >>= 1; + } + + ext4_superblock_set_log_block_size(sb, log); +} + +uint32_t ext4_superblock_get_blocks_per_group(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->blocks_per_group); +} + +void ext4_superblock_set_blocks_per_group(ext4_superblock_t *sb, uint32_t blocks) +{ + sb->blocks_per_group = host2uint32_t_le(blocks); +} + +uint32_t ext4_superblock_get_inodes_per_group(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->inodes_per_group); +} + +void ext4_superblock_set_inodes_per_group(ext4_superblock_t *sb, uint32_t inodes) +{ + sb->inodes_per_group = host2uint32_t_le(inodes); +} + +uint32_t ext4_superblock_get_mount_time(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->mount_time); +} + +void ext4_superblock_set_mount_time(ext4_superblock_t *sb, uint32_t time) +{ + sb->mount_time = host2uint32_t_le(time); +} + +uint32_t ext4_superblock_get_write_time(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->write_time); +} + +void ext4_superblock_set_write_time(ext4_superblock_t *sb, uint32_t time) +{ + sb->write_time = host2uint32_t_le(time); +} + +uint16_t ext4_superblock_get_mount_count(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->mount_count); +} + +void ext4_superblock_set_mount_count(ext4_superblock_t *sb, uint16_t count) +{ + sb->mount_count = host2uint16_t_le(count); +} + +uint16_t ext4_superblock_get_max_mount_count(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->max_mount_count); +} + +void ext4_superblock_set_max_mount_count(ext4_superblock_t *sb, uint16_t count) +{ + sb->max_mount_count = host2uint16_t_le(count); +} + +uint16_t ext4_superblock_get_magic(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->magic); +} + +uint16_t ext4_superblock_get_state(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->state); +} + +void ext4_superblock_set_state(ext4_superblock_t *sb, uint16_t state) +{ + sb->state = host2uint16_t_le(state); +} + +uint16_t ext4_superblock_get_errors(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->errors); +} + +void ext4_superblock_set_errors(ext4_superblock_t *sb, uint16_t errors) +{ + sb->errors = host2uint16_t_le(errors); +} + +uint16_t ext4_superblock_get_minor_rev_level(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->minor_rev_level); +} + +void ext4_superblock_set_minor_rev_level(ext4_superblock_t *sb, uint16_t level) +{ + sb->minor_rev_level = host2uint16_t_le(level); +} + +uint32_t ext4_superblock_get_last_check_time(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->last_check_time); +} + +void ext4_superblock_set_last_check_time(ext4_superblock_t *sb, uint32_t time) +{ + sb->state = host2uint32_t_le(time); +} + +uint32_t ext4_superblock_get_check_interval(ext4_superblock_t *sb){ + return uint32_t_le2host(sb->check_interval); +} + +void ext4_superblock_set_check_interval(ext4_superblock_t *sb, uint32_t interval) +{ + sb->check_interval = host2uint32_t_le(interval); +} + +uint32_t ext4_superblock_get_creator_os(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->creator_os); +} + +void ext4_superblock_set_creator_os(ext4_superblock_t *sb, uint32_t os) +{ + sb->creator_os = host2uint32_t_le(os); +} + +uint32_t ext4_superblock_get_rev_level(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->rev_level); +} + +void ext4_superblock_set_rev_level(ext4_superblock_t *sb, uint32_t level) +{ + sb->rev_level = host2uint32_t_le(level); +} + +uint16_t ext4_superblock_get_def_resuid(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->def_resuid); +} + +void ext4_superblock_set_def_resuid(ext4_superblock_t *sb, uint16_t uid) +{ + sb->def_resuid = host2uint16_t_le(uid); +} + +uint16_t ext4_superblock_get_def_resgid(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->def_resgid); +} + +void ext4_superblock_set_def_resgid(ext4_superblock_t *sb, uint16_t gid) +{ + sb->def_resgid = host2uint16_t_le(gid); +} + +uint32_t ext4_superblock_get_first_inode(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->first_inode); +} + +void ext4_superblock_set_first_inode(ext4_superblock_t *sb, uint32_t first_inode) +{ + sb->first_inode = host2uint32_t_le(first_inode); +} + +uint16_t ext4_superblock_get_inode_size(ext4_superblock_t *sb) +{ + if (ext4_superblock_get_rev_level(sb) == 0) { + return EXT4_REV0_INODE_SIZE; + } + return uint16_t_le2host(sb->inode_size); +} + +void ext4_superblock_set_inode_size(ext4_superblock_t *sb, uint16_t size) +{ + sb->inode_size = host2uint16_t_le(size); +} + +uint16_t ext4_superblock_get_block_group_number(ext4_superblock_t *sb) +{ + return uint16_t_le2host(sb->block_group_number); +} + +void ext4_superblock_set_block_group_number(ext4_superblock_t *sb, uint16_t bg) +{ + sb->block_group_number = host2uint16_t_le(bg); +} + +uint32_t ext4_superblock_get_features_compatible(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->features_compatible); +} + +void ext4_superblock_set_features_compatible(ext4_superblock_t *sb, uint32_t features) +{ + sb->features_compatible = host2uint32_t_le(features); +} + +uint32_t ext4_superblock_get_features_incompatible(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->features_incompatible); +} + +void ext4_superblock_set_features_incompatible(ext4_superblock_t *sb, uint32_t features) +{ + sb->features_incompatible = host2uint32_t_le(features); +} + +uint32_t ext4_superblock_get_features_read_only(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->features_read_only); +} + +void ext4_superblock_set_features_read_only(ext4_superblock_t *sb, uint32_t features) +{ + sb->features_read_only = host2uint32_t_le(features); +} + +uint32_t ext4_superblock_get_last_orphan(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->last_orphan); +} + +void ext4_superblock_set_last_orphan(ext4_superblock_t *sb, uint32_t last_orphan) +{ + sb->last_orphan = host2uint32_t_le(last_orphan); +} + +uint32_t* ext4_superblock_get_hash_seed(ext4_superblock_t *sb) +{ + return sb->hash_seed; +} + +uint16_t ext4_superblock_get_desc_size(ext4_superblock_t *sb) +{ + uint16_t size = uint16_t_le2host(sb->desc_size); + + if (size < EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE) { + size = EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE; + } + + return size; +} + +void ext4_superblock_set_desc_size(ext4_superblock_t *sb, uint16_t size) +{ + sb->desc_size = host2uint16_t_le(size); +} + +uint32_t ext4_superblock_get_flags(ext4_superblock_t *sb) +{ + return uint32_t_le2host(sb->flags); +} + +void ext4_superblock_set_flags(ext4_superblock_t *sb, uint32_t flags) +{ + sb->flags = host2uint32_t_le(flags); +} + + +/* + * More complex superblock operations + */ + +bool ext4_superblock_has_flag(ext4_superblock_t *sb, uint32_t flag) +{ + if (ext4_superblock_get_flags(sb) & flag) { + return true; + } + return false; +} + +// Feature checkers +bool ext4_superblock_has_feature_compatible(ext4_superblock_t *sb, uint32_t feature) +{ + if (ext4_superblock_get_features_compatible(sb) & feature) { + return true; + } + return false; +} + +bool ext4_superblock_has_feature_incompatible(ext4_superblock_t *sb, uint32_t feature) +{ + if (ext4_superblock_get_features_incompatible(sb) & feature) { + return true; + } + return false; +} + +bool ext4_superblock_has_feature_read_only(ext4_superblock_t *sb, uint32_t feature) +{ + if (ext4_superblock_get_features_read_only(sb) & feature) { + return true; + } + return false; +} + + +int ext4_superblock_read_direct(service_id_t service_id, + ext4_superblock_t **superblock) +{ + int rc; + + void *data = malloc(EXT4_SUPERBLOCK_SIZE); + if (data == NULL) { + return ENOMEM; + } + + rc = block_read_bytes_direct(service_id, EXT4_SUPERBLOCK_OFFSET, + EXT4_SUPERBLOCK_SIZE, data); + + if (rc != EOK) { + free(data); + return rc; + } + + (*superblock) = data; + + return EOK; +} + +int ext4_superblock_write_direct(service_id_t service_id, + ext4_superblock_t *sb) +{ + int rc; + uint32_t phys_block_size; + + rc = block_get_bsize(service_id, &phys_block_size); + if (rc != EOK) { + // TODO error + return rc; + } + + uint64_t first_block = EXT4_SUPERBLOCK_OFFSET / phys_block_size; + uint32_t block_count = EXT4_SUPERBLOCK_SIZE / phys_block_size; + + if (EXT4_SUPERBLOCK_SIZE % phys_block_size) { + block_count++; + } + + return block_write_direct(service_id, first_block, block_count, sb); + +} + + +int ext4_superblock_check_sanity(ext4_superblock_t *sb) +{ + if (ext4_superblock_get_magic(sb) != EXT4_SUPERBLOCK_MAGIC) { + return ENOTSUP; + } + + // block size + // desc size + + + // TODO more checks !!! + + return EOK; +} + +uint32_t ext4_superblock_get_block_group_count(ext4_superblock_t *sb) +{ + uint64_t blocks_count = ext4_superblock_get_blocks_count(sb); + uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb); + + uint32_t block_groups_count = blocks_count / blocks_per_group; + + if (blocks_count % blocks_per_group) { + block_groups_count++; + } + + return block_groups_count; + +} + +uint32_t ext4_superblock_get_blocks_in_group(ext4_superblock_t *sb, uint32_t bgid) +{ + uint32_t block_group_count = ext4_superblock_get_block_group_count(sb); + uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb); + uint64_t total_blocks = ext4_superblock_get_blocks_count(sb); + + if (bgid < block_group_count - 1) { + return blocks_per_group; + } else { + return (total_blocks - ((block_group_count - 1) * blocks_per_group)); + } + +} + +uint32_t ext4_superblock_get_inodes_in_group(ext4_superblock_t *sb, uint32_t bgid) +{ + uint32_t block_group_count = ext4_superblock_get_block_group_count(sb); + uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb); + uint32_t total_inodes = ext4_superblock_get_inodes_count(sb); + + if (bgid < block_group_count - 1) { + return inodes_per_group; + } else { + return (total_inodes - ((block_group_count - 1) * inodes_per_group)); + } + +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_superblock.h =================================================================== --- uspace/lib/ext4/libext4_superblock.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_superblock.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,178 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_SUPERBLOCK_H_ +#define LIBEXT4_LIBEXT4_SUPERBLOCK_H_ + +#include +#include + +#include "libext4_types.h" + +extern uint32_t ext4_superblock_get_inodes_count(ext4_superblock_t *); +extern void ext4_superblock_set_inodes_count(ext4_superblock_t *, uint32_t); +extern uint64_t ext4_superblock_get_blocks_count(ext4_superblock_t *); +extern void ext4_superblock_set_blocks_count(ext4_superblock_t *, uint64_t); +extern uint64_t ext4_superblock_get_reserved_blocks_count(ext4_superblock_t *); +extern void ext4_superblock_set_reserved_blocks_count(ext4_superblock_t *, uint64_t); +extern uint64_t ext4_superblock_get_free_blocks_count(ext4_superblock_t *); +extern void ext4_superblock_set_free_blocks_count(ext4_superblock_t *, uint64_t); +extern uint32_t ext4_superblock_get_free_inodes_count(ext4_superblock_t *); +extern void ext4_superblock_set_free_inodes_count(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_first_data_block(ext4_superblock_t *); +extern void ext4_superblock_set_first_data_block(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_log_block_size(ext4_superblock_t *); +extern void ext4_superblock_set_log_block_size(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_block_size(ext4_superblock_t *); +extern void ext4_superblock_set_block_size(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_blocks_per_group(ext4_superblock_t *); +extern void ext4_superblock_set_blocks_per_group(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_inodes_per_group(ext4_superblock_t *); +extern void ext4_superblock_set_inodes_per_group(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_mount_time(ext4_superblock_t *); +extern void ext4_superblock_set_mount_time(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_write_time(ext4_superblock_t *); +extern void ext4_superblock_set_write_time(ext4_superblock_t *, uint32_t); +extern uint16_t ext4_superblock_get_mount_count(ext4_superblock_t *); +extern void ext4_superblock_set_mount_count(ext4_superblock_t *, uint16_t); +extern uint16_t ext4_superblock_get_max_mount_count(ext4_superblock_t *); +extern void ext4_superblock_set_max_mount_count(ext4_superblock_t *, uint16_t); +extern uint16_t ext4_superblock_get_magic(ext4_superblock_t *); +extern uint16_t ext4_superblock_get_state(ext4_superblock_t *); +extern void ext4_superblock_set_state(ext4_superblock_t *, uint16_t); +extern uint16_t ext4_superblock_get_errors(ext4_superblock_t *); +extern void ext4_superblock_set_errors(ext4_superblock_t *, uint16_t); +extern uint16_t ext4_superblock_get_minor_rev_level(ext4_superblock_t *); +extern void ext4_superblock_set_minor_rev_level(ext4_superblock_t *, uint16_t); +extern uint32_t ext4_superblock_get_last_check_time(ext4_superblock_t *); +extern void ext4_superblock_set_last_check_time(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_check_interval(ext4_superblock_t *); +extern void ext4_superblock_set_check_interval(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_creator_os(ext4_superblock_t *); +extern void ext4_superblock_set_creator_os(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_rev_level(ext4_superblock_t *); +extern void ext4_superblock_set_rev_level(ext4_superblock_t *, uint32_t); +extern uint16_t ext4_superblock_get_def_resuid(ext4_superblock_t *); +extern void ext4_superblock_set_def_resuid(ext4_superblock_t *, uint16_t); +extern uint16_t ext4_superblock_get_def_resgid(ext4_superblock_t *); +extern void ext4_superblock_set_def_resgid(ext4_superblock_t *, uint16_t); +extern uint32_t ext4_superblock_get_first_inode(ext4_superblock_t *); +extern void ext4_superblock_set_first_inode(ext4_superblock_t *, uint32_t); +extern uint16_t ext4_superblock_get_inode_size(ext4_superblock_t *); +extern void ext4_superblock_set_inode_size(ext4_superblock_t *, uint16_t); +extern uint16_t ext4_superblock_get_block_group_number(ext4_superblock_t *); +extern void ext4_superblock_set_block_group_number(ext4_superblock_t *, uint16_t); +extern uint32_t ext4_superblock_get_features_compatible(ext4_superblock_t *); +extern void ext4_superblock_set_features_compatible(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_features_incompatible(ext4_superblock_t *); +extern void ext4_superblock_set_features_incompatible(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_features_read_only(ext4_superblock_t *); +extern void ext4_superblock_set_features_read_only(ext4_superblock_t *, uint32_t); + +/* +uint8_t s_uuid[16]; // 128-bit uuid for volume +char volume_name[16]; // Volume name +char last_mounted[64]; // Directory where last mounted +uint32_t s_algorithm_usage_bitmap; // For compression +uint8_t s_prealloc_blocks; // Number of blocks to try to preallocate +uint8_t s_prealloc_dir_blocks; // Number to preallocate for dirs +uint16_t s_reserved_gdt_blocks; // Per group desc for online growth +uint8_t s_journal_uuid[16]; // UUID of journal superblock +uint32_t s_journal_inum; // Inode number of journal file +uint32_t s_journal_dev; // Device number of journal file +*/ +extern uint32_t ext4_superblock_get_last_orphan(ext4_superblock_t *); +extern void ext4_superblock_set_last_orphan(ext4_superblock_t *, uint32_t); +extern uint32_t* ext4_superblock_get_hash_seed(ext4_superblock_t *); +/* +uint8_t s_def_hash_version; // Default hash version to use +uint8_t s_jnl_backup_type; +*/ + +extern uint16_t ext4_superblock_get_desc_size(ext4_superblock_t *); +extern void ext4_superblock_set_desc_size(ext4_superblock_t *, uint16_t); + +/* +uint32_t s_default_mount_opts; // Default mount options +uint32_t s_first_meta_bg; // First metablock block group +uint32_t s_mkfs_time; // When the filesystem was created +uint32_t s_jnl_blocks[17]; // Backup of the journal inode +uint16_t s_min_extra_isize; // All inodes have at least # bytes +uint16_t s_want_extra_isize; // New inodes should reserve # bytes +*/ +extern uint32_t ext4_superblock_get_flags(ext4_superblock_t *); +extern void ext4_superblock_set_flags(ext4_superblock_t *, uint32_t); +/* +uint16_t s_raid_stride; // RAID stride +uint16_t s_mmp_interval; // # seconds to wait in MMP checking +uint64_t s_mmp_block; // Block for multi-mount protection +uint32_t s_raid_stripe_width; // blocks on all data disks (N*stride) +uint8_t s_log_groups_per_flex; // FLEX_BG group size +uint8_t s_reserved_char_pad; +uint16_t s_reserved_pad; +uint64_t s_kbytes_written; // Number of lifetime kilobytes written +uint32_t s_snapshot_inum; // Inode number of active snapshot +uint32_t s_snapshot_id; // Sequential ID of active snapshot +uint64_t s_snapshot_r_blocks_count; // reserved blocks for active snapshot's future use +uint32_t s_snapshot_list; // inode number of the head of the on-disk snapshot list +uint32_t s_error_count; // number of fs errors +uint32_t s_first_error_time; // First time an error happened +uint32_t s_first_error_ino; // Inode involved in first error +uint64_t s_first_error_block; // block involved of first error +uint8_t s_first_error_func[32]; // Function where the error happened +uint32_t s_first_error_line; // Line number where error happened +uint32_t s_last_error_time; // Most recent time of an error +uint32_t s_last_error_ino; // Inode involved in last error +uint32_t s_last_error_line; // Line number where error happened +uint64_t s_last_error_block; // block involved of last error +uint8_t s_last_error_func[32]; // function where the error happened +uint8_t s_mount_opts[64]; +*/ + +/* More complex superblock functions */ +extern bool ext4_superblock_has_flag(ext4_superblock_t *, uint32_t); +extern bool ext4_superblock_has_feature_compatible(ext4_superblock_t *, uint32_t); +extern bool ext4_superblock_has_feature_incompatible(ext4_superblock_t *, uint32_t); +extern bool ext4_superblock_has_feature_read_only(ext4_superblock_t *, uint32_t); +extern int ext4_superblock_read_direct(service_id_t, ext4_superblock_t **); +extern int ext4_superblock_write_direct(service_id_t, ext4_superblock_t *); +extern int ext4_superblock_check_sanity(ext4_superblock_t *); + +extern uint32_t ext4_superblock_get_block_group_count(ext4_superblock_t *); +extern uint32_t ext4_superblock_get_blocks_in_group(ext4_superblock_t *, uint32_t); +extern uint32_t ext4_superblock_get_inodes_in_group(ext4_superblock_t *, uint32_t); + +#endif + +/** + * @} + */ Index: uspace/lib/ext4/libext4_types.h =================================================================== --- uspace/lib/ext4/libext4_types.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) +++ uspace/lib/ext4/libext4_types.h (revision 6514d1fb449f3749f80ab6141dc5ee12e418e3dd) @@ -0,0 +1,523 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_TYPES_H_ +#define LIBEXT4_LIBEXT4_TYPES_H_ + +#include + +/* + * Structure of the super block + */ +typedef struct ext4_superblock { + uint32_t inodes_count; // Inodes count + uint32_t blocks_count_lo; // Blocks count + uint32_t reserved_blocks_count_lo; // Reserved blocks count + uint32_t free_blocks_count_lo; // Free blocks count + uint32_t free_inodes_count; // Free inodes count + uint32_t first_data_block; // First Data Block + uint32_t log_block_size; // Block size + uint32_t obso_log_frag_size; // Obsoleted fragment size + uint32_t blocks_per_group; // Number of blocks per group + uint32_t obso_frags_per_group; // Obsoleted fragments per group + uint32_t inodes_per_group; // Number of inodes per group + uint32_t mount_time; // Mount time + uint32_t write_time; // Write time + uint16_t mount_count; // Mount count + uint16_t max_mount_count; // Maximal mount count + uint16_t magic; // Magic signature + uint16_t state; // File system state + uint16_t errors; // Behaviour when detecting errors + uint16_t minor_rev_level; // Minor revision level + uint32_t last_check_time; // Time of last check + uint32_t check_interval; // Maximum time between checks + uint32_t creator_os; // Creator OS + uint32_t rev_level; // Revision level + uint16_t def_resuid; // Default uid for reserved blocks + uint16_t def_resgid; // Default gid for reserved blocks + + // Fields for EXT4_DYNAMIC_REV superblocks only. + uint32_t first_inode; // First non-reserved inode + uint16_t inode_size; // Size of inode structure + uint16_t block_group_number; // Block group number of this superblock + uint32_t features_compatible; // Compatible feature set + uint32_t features_incompatible; // Incompatible feature set + uint32_t features_read_only; // Readonly-compatible feature set + uint8_t uuid[16]; // 128-bit uuid for volume + char volume_name[16]; // Volume name + char last_mounted[64]; // Directory where last mounted + uint32_t algorithm_usage_bitmap; // For compression + + /* + * Performance hints. Directory preallocation should only + * happen if the EXT4_FEATURE_COMPAT_DIR_PREALLOC flag is on. + */ + uint8_t s_prealloc_blocks; // Number of blocks to try to preallocate + uint8_t s_prealloc_dir_blocks; // Number to preallocate for dirs + uint16_t s_reserved_gdt_blocks; // Per group desc for online growth + + /* + * Journaling support valid if EXT4_FEATURE_COMPAT_HAS_JOURNAL set. + */ + uint8_t journal_uuid[16]; // UUID of journal superblock + uint32_t journal_inode_number; // Inode number of journal file + uint32_t journal_dev; // Device number of journal file + uint32_t last_orphan; // Head of list of inodes to delete + uint32_t hash_seed[4]; // HTREE hash seed + uint8_t default_hash_version; // Default hash version to use + uint8_t journal_backup_type; + uint16_t desc_size; // Size of group descriptor + uint32_t default_mount_opts; // Default mount options + uint32_t first_meta_bg; // First metablock block group + uint32_t mkfs_time; // When the filesystem was created + uint32_t journal_blocks[17]; // Backup of the journal inode + + /* 64bit support valid if EXT4_FEATURE_COMPAT_64BIT */ + uint32_t blocks_count_hi; // Blocks count + uint32_t reserved_blocks_count_hi; // Reserved blocks count + uint32_t free_blocks_count_hi; // Free blocks count + uint16_t min_extra_isize; // All inodes have at least # bytes + uint16_t want_extra_isize; // New inodes should reserve # bytes + uint32_t flags; // Miscellaneous flags + uint16_t raid_stride; // RAID stride + uint16_t mmp_interval; // # seconds to wait in MMP checking + uint64_t mmp_block; // Block for multi-mount protection + uint32_t raid_stripe_width; // blocks on all data disks (N*stride) + uint8_t log_groups_per_flex; // FLEX_BG group size + uint8_t reserved_char_pad; + uint16_t reserved_pad; + uint64_t kbytes_written; // Number of lifetime kilobytes written + uint32_t snapshot_inum; // Inode number of active snapshot + uint32_t snapshot_id; // Sequential ID of active snapshot + uint64_t snapshot_r_blocks_count; /* reserved blocks for active snapshot's future use */ + uint32_t snapshot_list; // inode number of the head of the on-disk snapshot list + uint32_t error_count; // number of fs errors + uint32_t first_error_time; // First time an error happened + uint32_t first_error_ino; // Inode involved in first error + uint64_t first_error_block; // block involved of first error + uint8_t first_error_func[32]; // Function where the error happened + uint32_t first_error_line; // Line number where error happened + uint32_t last_error_time; // Most recent time of an error + uint32_t last_error_ino; // Inode involved in last error + uint32_t last_error_line; // Line number where error happened + uint64_t last_error_block; // Block involved of last error + uint8_t last_error_func[32]; // Function where the error happened + uint8_t mount_opts[64]; + uint32_t padding[112]; // Padding to the end of the block +} __attribute__((packed)) ext4_superblock_t; + +#define EXT4_SUPERBLOCK_MAGIC 0xEF53 +#define EXT4_SUPERBLOCK_SIZE 1024 +#define EXT4_SUPERBLOCK_OFFSET 1024 + +#define EXT4_SUPERBLOCK_OS_LINUX 0 +#define EXT4_SUPERBLOCK_OS_HURD 1 + +/* + * Misc. filesystem flags + */ +#define EXT4_SUPERBLOCK_FLAGS_SIGNED_HASH 0x0001 /* Signed dirhash in use */ +#define EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH 0x0002 /* Unsigned dirhash in use */ +#define EXT4_SUPERBLOCK_FLAGS_TEST_FILESYS 0x0004 /* to test development code */ + +/* Compatible features */ +#define EXT4_FEATURE_COMPAT_DIR_PREALLOC 0x0001 +#define EXT4_FEATURE_COMPAT_IMAGIC_INODES 0x0002 +#define EXT4_FEATURE_COMPAT_HAS_JOURNAL 0x0004 +#define EXT4_FEATURE_COMPAT_EXT_ATTR 0x0008 +#define EXT4_FEATURE_COMPAT_RESIZE_INODE 0x0010 +#define EXT4_FEATURE_COMPAT_DIR_INDEX 0x0020 + +/* Read-only compatible features */ +#define EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER 0x0001 +#define EXT4_FEATURE_RO_COMPAT_LARGE_FILE 0x0002 +#define EXT4_FEATURE_RO_COMPAT_BTREE_DIR 0x0004 +#define EXT4_FEATURE_RO_COMPAT_HUGE_FILE 0x0008 +#define EXT4_FEATURE_RO_COMPAT_GDT_CSUM 0x0010 +#define EXT4_FEATURE_RO_COMPAT_DIR_NLINK 0x0020 +#define EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE 0x0040 + +/* Incompatible features */ +#define EXT4_FEATURE_INCOMPAT_COMPRESSION 0x0001 +#define EXT4_FEATURE_INCOMPAT_FILETYPE 0x0002 +#define EXT4_FEATURE_INCOMPAT_RECOVER 0x0004 /* Needs recovery */ +#define EXT4_FEATURE_INCOMPAT_JOURNAL_DEV 0x0008 /* Journal device */ +#define EXT4_FEATURE_INCOMPAT_META_BG 0x0010 +#define EXT4_FEATURE_INCOMPAT_EXTENTS 0x0040 /* extents support */ +#define EXT4_FEATURE_INCOMPAT_64BIT 0x0080 +#define EXT4_FEATURE_INCOMPAT_MMP 0x0100 +#define EXT4_FEATURE_INCOMPAT_FLEX_BG 0x0200 +#define EXT4_FEATURE_INCOMPAT_EA_INODE 0x0400 /* EA in inode */ +#define EXT4_FEATURE_INCOMPAT_DIRDATA 0x1000 /* data in dirent */ + +// TODO MODIFY features corresponding with implementation +#define EXT4_FEATURE_COMPAT_SUPP (EXT4_FEATURE_COMPAT_DIR_INDEX) + +#define EXT4_FEATURE_INCOMPAT_SUPP (EXT4_FEATURE_INCOMPAT_FILETYPE | \ + EXT4_FEATURE_INCOMPAT_EXTENTS | \ + EXT4_FEATURE_INCOMPAT_64BIT | \ + EXT4_FEATURE_INCOMPAT_FLEX_BG) + +#define EXT4_FEATURE_RO_COMPAT_SUPP (EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER | \ + EXT4_FEATURE_RO_COMPAT_DIR_NLINK | \ + EXT4_FEATURE_RO_COMPAT_HUGE_FILE) + + +/*****************************************************************************/ +/* + * Structure of a blocks group descriptor + */ +typedef struct ext4_block_group { + uint32_t block_bitmap_lo; // Blocks bitmap block + uint32_t inode_bitmap_lo; // Inodes bitmap block + uint32_t inode_table_first_block_lo; // Inodes table block + uint16_t free_blocks_count_lo; // Free blocks count + uint16_t free_inodes_count_lo; // Free inodes count + uint16_t used_dirs_count_lo; // Directories count + uint16_t flags; // EXT4_BG_flags (INODE_UNINIT, etc) + uint32_t reserved[2]; // Likely block/inode bitmap checksum + uint16_t itable_unused_lo; // Unused inodes count + uint16_t checksum; // crc16(sb_uuid+group+desc) + /* -------------- */ + uint32_t block_bitmap_hi; // Blocks bitmap block MSB + uint32_t inode_bitmap_hi; // Inodes bitmap block MSB + uint32_t inode_table_first_block_hi; // Inodes table block MSB + uint16_t free_blocks_count_hi; // Free blocks count MSB + uint16_t free_inodes_count_hi; // Free inodes count MSB + uint16_t used_dirs_count_hi; // Directories count MSB + uint16_t itable_unused_hi; // Unused inodes count MSB + uint32_t reserved2[3]; // Padding +} ext4_block_group_t; + +typedef struct ext4_block_group_ref { + block_t *block; // Reference to a block containing this block group descr + ext4_block_group_t *block_group; + bool dirty; +} ext4_block_group_ref_t; + + +#define EXT4_BLOCK_MIN_GROUP_DESCRIPTOR_SIZE 32 +#define EXT4_BLOCK_MAX_GROUP_DESCRIPTOR_SIZE 64 + + +/*****************************************************************************/ + +typedef struct ext4_filesystem { + service_id_t device; + ext4_superblock_t * superblock; + aoff64_t inode_block_limits[4]; + aoff64_t inode_blocks_per_level[4]; +} ext4_filesystem_t; + +#define EXT4_MIN_BLOCK_SIZE 1024 //1 KiB +#define EXT4_MAX_BLOCK_SIZE 65536 //64 KiB +#define EXT4_REV0_INODE_SIZE 128 + +/*****************************************************************************/ + + +#define EXT4_INODE_BLOCK_SIZE 512 + +#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) + +/* + * Structure of an inode on the disk + */ +typedef struct ext4_inode { + uint16_t mode; // File mode + uint16_t uid; // Low 16 bits of owner uid + uint32_t size_lo; // Size in bytes + uint32_t access_time; // Access time + uint32_t change_inode_time; // Inode change time + uint32_t modification_time; // Modification time + uint32_t deletion_time; // Deletion time + uint16_t gid; // Low 16 bits of group id + uint16_t links_count; // Links count + uint32_t blocks_count_lo; // Blocks count + uint32_t flags; // File flags + uint32_t unused_osd1; // OS dependent - not used in HelenOS + uint32_t blocks[EXT4_INODE_BLOCKS]; // Pointers to blocks + uint32_t generation; // File version (for NFS) + uint32_t file_acl_lo; // File ACL + uint32_t size_hi; + uint32_t obso_faddr; // Obsoleted fragment address + 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; + } __attribute__ ((packed)) osd2; + + uint16_t extra_isize; + uint16_t pad1; + uint32_t ctime_extra; // Extra change time (nsec << 2 | epoch) + uint32_t mtime_extra; // Extra Modification time (nsec << 2 | epoch) + uint32_t atime_extra; // Extra Access time (nsec << 2 | epoch) + uint32_t crtime; // File creation time + uint32_t crtime_extra; // Extra file creation time (nsec << 2 | epoch) + uint32_t version_hi; // High 32 bits for 64-bit version +} __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 + +/* + * Inode flags + */ +#define EXT4_INODE_FLAG_SECRM 0x00000001 // Secure deletion +#define EXT4_INODE_FLAG_UNRM 0x00000002 // Undelete +#define EXT4_INODE_FLAG_COMPR 0x00000004 // Compress file +#define EXT4_INODE_FLAG_SYNC 0x00000008 // Synchronous updates +#define EXT4_INODE_FLAG_IMMUTABLE 0x00000010 // Immutable file +#define EXT4_INODE_FLAG_APPEND 0x00000020 // writes to file may only append +#define EXT4_INODE_FLAG_NODUMP 0x00000040 // do not dump file +#define EXT4_INODE_FLAG_NOATIME 0x00000080 // do not update atime +/* Compression flags */ +#define EXT4_INODE_FLAG_DIRTY 0x00000100 +#define EXT4_INODE_FLAG_COMPRBLK 0x00000200 // One or more compressed clusters +#define EXT4_INODE_FLAG_NOCOMPR 0x00000400 // Don't compress +#define EXT4_INODE_FLAG_ECOMPR 0x00000800 // Compression error +/* End compression flags --- maybe not all used */ +#define EXT4_INODE_FLAG_INDEX 0x00001000 // hash-indexed directory +#define EXT4_INODE_FLAG_IMAGIC 0x00002000 // AFS directory */ +#define EXT4_INODE_FLAG_JOURNAL_DATA 0x00004000 // File data should be journaled +#define EXT4_INODE_FLAG_NOTAIL 0x00008000 // File tail should not be merged +#define EXT4_INODE_FLAG_DIRSYNC 0x00010000 // Dirsync behaviour (directories only) +#define EXT4_INODE_FLAG_TOPDIR 0x00020000 // Top of directory hierarchies +#define EXT4_INODE_FLAG_HUGE_FILE 0x00040000 // Set to each huge file +#define EXT4_INODE_FLAG_EXTENTS 0x00080000 // Inode uses extents +#define EXT4_INODE_FLAG_EA_INODE 0x00200000 // Inode used for large EA +#define EXT4_INODE_FLAG_EOFBLOCKS 0x00400000 // Blocks allocated beyond EOF +#define EXT4_INODE_FLAG_RESERVED 0x80000000 // reserved for ext4 lib + +#define EXT4_INODE_ROOT_INDEX 2 + +typedef struct ext4_inode_ref { + block_t *block; // Reference to a block containing this inode + ext4_inode_t *inode; + uint32_t index; // Index number of this inode + bool dirty; +} ext4_inode_ref_t; + +/*****************************************************************************/ + +#define EXT4_DIRECTORY_FILENAME_LEN 255 + +#define EXT4_DIRECTORY_FILETYPE_UNKNOWN 0 +#define EXT4_DIRECTORY_FILETYPE_REG_FILE 1 +#define EXT4_DIRECTORY_FILETYPE_DIR 2 +#define EXT4_DIRECTORY_FILETYPE_CHRDEV 3 +#define EXT4_DIRECTORY_FILETYPE_BLKDEV 4 +#define EXT4_DIRECTORY_FILETYPE_FIFO 5 +#define EXT4_DIRECTORY_FILETYPE_SOCK 6 +#define EXT4_DIRECTORY_FILETYPE_SYMLINK 7 + +/** + * 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[EXT4_DIRECTORY_FILENAME_LEN]; // Entry name +} __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; + +typedef struct ext4_directory_search_result { + block_t *block; + ext4_directory_entry_ll_t *dentry; +} ext4_directory_search_result_t; + + +/*****************************************************************************/ + +/* Structures for indexed directory */ + +typedef struct ext4_directory_dx_countlimit { + uint16_t limit; + uint16_t count; +} ext4_directory_dx_countlimit_t; + +typedef struct ext4_directory_dx_dot_entry { + uint32_t inode; + uint16_t entry_length; + uint8_t name_length; + uint8_t inode_type; + uint8_t name[4]; +} ext4_directory_dx_dot_entry_t; + +typedef struct ext4_directory_dx_root_info { + uint32_t reserved_zero; + uint8_t hash_version; + uint8_t info_length; + uint8_t indirect_levels; + uint8_t unused_flags; +} ext4_directory_dx_root_info_t; + +typedef struct ext4_directory_dx_entry { + uint32_t hash; + uint32_t block; +} ext4_directory_dx_entry_t; + +typedef struct ext4_directory_dx_root { + ext4_directory_dx_dot_entry_t dots[2]; + ext4_directory_dx_root_info_t info; + ext4_directory_dx_entry_t entries[0]; +} ext4_directory_dx_root_t; + +typedef struct ext4_fake_directory_entry { + uint32_t inode; + uint16_t entry_length; + uint8_t name_length; + uint8_t inode_type; +} ext4_fake_directory_entry_t; + +typedef struct ext4_directory_dx_node { + ext4_fake_directory_entry_t fake; + ext4_directory_dx_entry_t entries[0]; +} ext4_directory_dx_node_t; + + +typedef struct ext4_directory_dx_block { + block_t *block; + ext4_directory_dx_entry_t *entries; + ext4_directory_dx_entry_t *position; +} ext4_directory_dx_block_t; + + + +#define EXT4_ERR_BAD_DX_DIR (-75000) +#define EXT4_DIRECTORY_HTREE_EOF (uint32_t)0x7fffffff + +/*****************************************************************************/ + +/* + * This is the extent on-disk structure. + * It's used at the bottom of the tree. + */ +typedef struct ext4_extent { + uint32_t first_block; // First logical block extent covers + uint16_t block_count; // Number of blocks covered by extent + uint16_t start_hi; // High 16 bits of physical block + uint32_t start_lo; // Low 32 bits of physical block +} ext4_extent_t; + +/* + * This is index on-disk structure. + * It's used at all the levels except the bottom. + */ +typedef struct ext4_extent_index { + uint32_t first_block; // Index covers logical blocks from 'block' + uint32_t leaf_lo; /* Pointer to the physical block of the next + * level. leaf or next index could be there */ + uint16_t leaf_hi; /* high 16 bits of physical block */ + uint16_t padding; +} ext4_extent_index_t; + +/* + * Each block (leaves and indexes), even inode-stored has header. + */ +typedef struct ext4_extent_header { + uint16_t magic; + uint16_t entries_count; // Number of valid entries + uint16_t max_entries_count; // Capacity of store in entries + uint16_t depth; // Has tree real underlying blocks? + uint32_t generation; // generation of the tree +} ext4_extent_header_t; + +typedef struct ext4_extent_path { + block_t *block; + uint16_t depth; + ext4_extent_header_t *header; + ext4_extent_index_t *index; + ext4_extent_t *extent; +} ext4_extent_path_t; + +#define EXT4_EXTENT_MAGIC 0xF30A +#define EXT4_EXTENT_FIRST(header) \ + ((ext4_extent_t *) (((void *) (header)) + sizeof(ext4_extent_header_t))) +#define EXT4_EXTENT_FIRST_INDEX(header) \ + ((ext4_extent_index_t *) (((void *) (header)) + sizeof(ext4_extent_header_t))) + +/*****************************************************************************/ + +#define EXT4_HASH_VERSION_LEGACY 0 +#define EXT4_HASH_VERSION_HALF_MD4 1 +#define EXT4_HASH_VERSION_TEA 2 +#define EXT4_HASH_VERSION_LEGACY_UNSIGNED 3 +#define EXT4_HASH_VERSION_HALF_MD4_UNSIGNED 4 +#define EXT4_HASH_VERSION_TEA_UNSIGNED 5 + +typedef struct ext4_hash_info { + uint32_t hash; + uint32_t minor_hash; + uint32_t hash_version; + uint32_t *seed; +} ext4_hash_info_t; + +#endif + +/** + * @} + */