/* * Copyright (c) 2017 Kaho Ng (ngkaho1234@gmail.com) * Copyright (c) 2017 Grzegorz Kostka (kostka.grzegorz@gmail.com) * * * HelenOS: * Copyright (c) 2012 Martin Sucha * Copyright (c) 2012 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 lwext4 * @{ *//** * @file  ext4_extent.c * @brief More complex filesystem functions. */ #include <ext4_config.h>#include <ext4_errno.h>#include <ext4_debug.h> #include <ext4_fs.h>#include <ext4_trans.h>#include <ext4_blockdev.h>#include <ext4_extent.h>#include <ext4_inode.h>#include <ext4_super.h>#include <ext4_crc32.h>#include <ext4_balloc.h> #include <string.h>#include <stdlib.h> #if CONFIG_EXTENT_ENABLE /**@brief Return the extent tree depth * @param inode_ref I-node reference the tree belongs to * @return Depth of extent tree */static inline uint16_text4_extent_tree_depth(struct ext4_inode_ref *inode_ref){	struct ext4_extent_header *eh;	eh = ext4_inode_get_extent_header(inode_ref->inode);	return ext4_extent_header_get_depth(eh);} static struct ext4_extent_tail *ext4_extent_get_csum_tail(struct ext4_extent_header *eh){	return (struct ext4_extent_tail *)(((char *)eh) +	    EXT4_EXTENT_TAIL_OFFSET(eh));} #if CONFIG_META_CSUM_ENABLEstatic uint32_t ext4_extent_block_csum(struct ext4_inode_ref *inode_ref,				       struct ext4_extent_header *eh){	uint32_t checksum = 0;	struct ext4_sblock *sb = &inode_ref->fs->sb; 	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {		uint32_t ino_index = to_le32(inode_ref->index);		uint32_t ino_gen =			to_le32(ext4_inode_get_generation(inode_ref->inode));		/* First calculate crc32 checksum against fs uuid */		checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,				sizeof(sb->uuid));		/* Then calculate crc32 checksum against inode number		 * and inode generation */		checksum = ext4_crc32c(checksum, &ino_index,				     sizeof(ino_index));		checksum = ext4_crc32c(checksum, &ino_gen,				     sizeof(ino_gen));		/* Finally calculate crc32 checksum against		 * the entire extent block up to the checksum field */		checksum = ext4_crc32c(checksum, eh,		    EXT4_EXTENT_TAIL_OFFSET(eh));	}	return checksum;} static boolext4_extent_verify_block_csum(struct ext4_inode_ref *inode_ref,			      struct ext4_block *block){	uint16_t rootdepth;	struct ext4_extent_tail *tail;	struct ext4_extent_header *eh; 	rootdepth = ext4_extent_tree_depth(inode_ref); 	if (!ext4_sb_feature_ro_com(&inode_ref->fs->sb,				    EXT4_FRO_COM_METADATA_CSUM))		return true; 	eh = (struct ext4_extent_header *)block->data;	if (ext4_extent_header_get_depth(eh) < rootdepth) {		tail = ext4_extent_get_csum_tail(eh);		return tail->checksum ==		    to_le32(ext4_extent_block_csum(inode_ref, eh));	} 	return true;}#else /* CONFIG_META_CSUM_ENABLE */#define ext4_ext_block_csum(...) 0#define ext4_extent_verify_block_csum(...) true#endif /* CONFIG_META_CSUM_ENABLE */ static voidext4_extent_block_csum_set(struct ext4_inode_ref *inode_ref,			   struct ext4_extent_header *eh){	uint16_t rootdepth;	struct ext4_extent_tail *tail; 	rootdepth = ext4_extent_tree_depth(inode_ref); 	if (!ext4_sb_feature_ro_com(&inode_ref->fs->sb,				    EXT4_FRO_COM_METADATA_CSUM))		return; 	if (ext4_extent_header_get_depth(eh) < rootdepth) {		tail = ext4_extent_get_csum_tail(eh);		tail->checksum = to_le32(ext4_extent_block_csum(inode_ref, eh));	}} #if CONFIG_EXTENT_DEBUG_VERBOSEstatic voidext4_extent_print_path(struct ext4_inode_ref *inode_ref,		       struct ext4_extent_path *path){	uint16_t rootdepth;	struct ext4_extent_path *p; 	rootdepth = ext4_extent_tree_depth(inode_ref);	p = path + rootdepth; 	ext4_dbg(DEBUG_EXTENT,		 DBG_INFO "Path address: %p\n", path);	while (p >= path) {		uint16_t i;		uint16_t entries =		    ext4_extent_header_get_nentries(p->header);		uint16_t limit =		    ext4_extent_header_get_max_nentries(p->header); 		ext4_dbg(DEBUG_EXTENT,DBG_INFO "-- Block: %" PRIu64 ", Depth: %" PRIu16 ", Entries: %" PRIu16 ", Limit: %" PRIu16 "\n",			 p->block.lb_id, p->depth, entries, limit);		for (i = 0; i < entries; i++) {			if (p->depth) {				struct ext4_extent_index *index; 				index = EXT4_EXTENT_FIRST_INDEX(p->header) + i;				ext4_dbg(DEBUG_EXTENT,DBG_INFO "Index: iblock: %" PRIu32 ", fsblock: %" PRIu64 "\n",					 ext4_extent_index_get_iblock(index),					 ext4_extent_index_get_fblock(index));			} else {				struct ext4_extent *extent; 				extent = EXT4_EXTENT_FIRST(p->header) + i;				ext4_dbg(DEBUG_EXTENT,DBG_INFO "Extent: iblock: %" PRIu32 ", fsblock: %" PRIu64 ", count: %" PRIu16 "\n",					 ext4_extent_get_iblock(extent),					 ext4_extent_get_fblock(extent),					 ext4_extent_get_nblocks(extent));			}		} 		p--;	} 	ext4_dbg(DEBUG_EXTENT,		 DBG_INFO "====================\n");}#else /* CONFIG_EXTENT_DEBUG_VERBOSE */#define ext4_extent_print_path(...)#endif /* CONFIG_EXTENT_DEBUG_VERBOSE */ /**@brief Binary search in extent index node. * @param header Extent header of index node * @param index  Output value - found index will be set here * @param iblock Logical block number to find in index node */static void ext4_extent_binsearch_idx(struct ext4_extent_header *header,				      struct ext4_extent_index **index,				      ext4_lblk_t iblock){	struct ext4_extent_index *r;	struct ext4_extent_index *l;	struct ext4_extent_index *m; 	uint16_t nentries = ext4_extent_header_get_nentries(header); 	/* Initialize bounds */	l = EXT4_EXTENT_FIRST_INDEX(header) + 1;	r = EXT4_EXTENT_FIRST_INDEX(header) + nentries - 1; 	/* Do binary search */	while (l <= r) {		m = l + (r - l) / 2;		ext4_lblk_t eiiblock = ext4_extent_index_get_iblock(m); 		if (iblock < eiiblock)			r = m - 1;		else			l = m + 1;	} 	/* Set output value */	*index = l - 1;} /**@brief Binary search in extent leaf node. * @param header Extent header of leaf node * @param extent Output value - found extent will be set here, *               or NULL if node is empty * @param iblock Logical block number to find in leaf node */static void ext4_extent_binsearch(struct ext4_extent_header *header,				  struct ext4_extent **extent,				  ext4_lblk_t iblock){	struct ext4_extent *r;	struct ext4_extent *l;	struct ext4_extent *m; 	uint16_t nentries = ext4_extent_header_get_nentries(header); 	if (nentries == 0) {		/* this leaf is empty */		*extent = NULL;		return;	} 	/* Initialize bounds */	l = EXT4_EXTENT_FIRST(header) + 1;	r = EXT4_EXTENT_FIRST(header) + nentries - 1; 	/* Do binary search */	while (l <= r) {		m = l + (r - l) / 2;		ext4_lblk_t eiblock = ext4_extent_get_iblock(m); 		if (iblock < eiblock)			r = m - 1;		else			l = m + 1;	} 	/* Set output value */	*extent = l - 1;} static voidext4_extent_path_dirty(struct ext4_inode_ref *inode_ref,		       struct ext4_extent_path *path,		       uint16_t depth){	uint16_t rootdepth;	rootdepth = ext4_extent_tree_depth(inode_ref); 	if (rootdepth != depth) {		struct ext4_extent_path *p;		p = path + depth;		ext4_extent_block_csum_set(inode_ref, p->header);		ext4_trans_set_block_dirty(p->block.buf);	} else		inode_ref->dirty = true;} static intext4_extent_path_release(struct ext4_inode_ref *inode_ref,			 struct ext4_extent_path *path){	int ret = EOK;	uint16_t i, rootdepth; 	rootdepth = ext4_extent_tree_depth(inode_ref); 	for (i = 0; i < rootdepth; i++) {		if (path[i].block.lb_id) {			ret = ext4_block_set(inode_ref->fs->bdev,					     &path[i].block);			if (ret != EOK)				break;		}	} 	return ret;} /**@brief Physical block allocation hint for extent tree manipulation * routines * @param inode_ref I-node * @return Physical block allocation hint */static ext4_fsblk_text4_extent_tree_alloc_goal(struct ext4_inode_ref *inode_ref){	uint32_t bgid;	struct ext4_sblock *sb; 	sb = &inode_ref->fs->sb;	bgid = inode_ref->index / ext4_get32(sb, inodes_per_group); 	/* Currently for allocations from extent tree manipulation routines,	 * we try the blocks in the block group the inode table block refers	 * to */	return ext4_fs_first_bg_block_no(sb, bgid);} /**@brief Physical block allocation hint for data blocks routines * @param inode_ref I-node * @param path      path in the extent tree * @param iblock    the starting logical block of the * mapping to be inserted * @return Physical block allocation hint */static ext4_fsblk_text4_extent_data_alloc_goal(struct ext4_inode_ref *inode_ref,			    struct ext4_extent_path *path,			    ext4_lblk_t iblock){	ext4_fsblk_t ret;	struct ext4_extent *ext; 	ext = path[0].extent;	if (!ext)		/* If there is no mapping yet, we return		 * ext4_extent_tree_alloc_goal() as hints */		return ext4_extent_tree_alloc_goal(inode_ref) + iblock; 	/* We want the whole file to be continuous. */	if (ext4_extent_get_iblock(ext) < iblock)		ret = ext4_extent_get_fblock(ext) +		    iblock - ext4_extent_get_iblock(ext);	else {		if (ext4_extent_get_iblock(ext) - iblock >		    ext4_extent_get_fblock(ext))			ret = ext4_extent_get_fblock(ext);		else			ret = ext4_extent_get_fblock(ext) -			    (ext4_extent_get_iblock(ext) - iblock);	} 	return ret;} /**@brief Verify the extent node block is valid * @param inode_ref I-node * @param block     block buffer of the extent node block * @param depth     the depth of extent node wanted * @return true if the block passes verification, otherwise false */static bool ext4_extent_block_verify(struct ext4_inode_ref *inode_ref,				     struct ext4_block *block,				     uint16_t depth){	uint32_t blocksz;	uint16_t maxnentries __unused;	struct ext4_extent_header *eh; 	eh = (struct ext4_extent_header *)block->data;	blocksz = ext4_sb_get_block_size(&inode_ref->fs->sb); 	/* Check if the magic number of the extent node header is correct */	if (ext4_extent_header_get_magic(eh) != EXT4_EXTENT_MAGIC) {		ext4_dbg(DEBUG_EXTENT,DBG_ERROR "Extent node block header mismatch! Block number: %" PRIu64 "\n",			 block->lb_id);		return false;	} 	/* Check if the depth field of extent node header matches what the	 * caller wants */	if (ext4_extent_header_get_depth(eh) != depth) {		ext4_dbg(DEBUG_EXTENT,DBG_ERROR "Extent node block depth mismatch! Expected: %" PRIu16 ", Got: %" PRIu16 ". Block number: %" PRIu64 "\n",			 depth, ext4_extent_header_get_depth(eh),			 block->lb_id);		return false;	} 	/* Check if the non-root node contains entries */	if (!ext4_extent_header_get_nentries(eh)) {		ext4_dbg(DEBUG_EXTENT,DBG_ERROR "Extent node block does not contain any entries! Block number: %" PRIu64 "\n",			 block->lb_id);		return false;	} #if !CONFIG_EXTENT_DEBUG_AGGRESSIVE	/* Make sure that the maximum entries field of the	 * extent node header is correct */	maxnentries = (blocksz - sizeof(struct ext4_extent_header)) /	    sizeof(struct ext4_extent); 	if (ext4_extent_header_get_max_nentries(eh) != maxnentries) {		ext4_dbg(DEBUG_EXTENT,DBG_ERROR "Incorrect extent node block maximum entries field! Expected: %" PRIu16 ", Got: %" PRIu16 ". Block number: %" PRIu64 "\n",			 maxnentries,			 ext4_extent_header_get_max_nentries(eh),			 block->lb_id);		return false;	}#endif 	/* Check if the checksum of the block is correct */	if (!ext4_extent_verify_block_csum(inode_ref,					   block)) {		ext4_dbg(DEBUG_EXTENT,DBG_ERROR "Extent node block checksum failed! Block number: %" PRIu64"\n",			 block->lb_id);		return false;	} 	/* The block passes verification */	return true;} /**@brief Find extent for specified iblock. * This function is used for finding block in the extent tree with * saving the path through the tree for possible future modifications. * @param inode_ref I-node to read extent tree from * @param iblock    Iblock to find extent for * @param ppath  Output value - loaded path from extent tree * @return Error code */static int ext4_extent_find_extent(struct ext4_inode_ref *inode_ref,				   ext4_lblk_t iblock,				   struct ext4_extent_path **ppath){	struct ext4_extent_header *eh;	int ret;	uint16_t depth;	uint16_t k;	struct ext4_extent_path *tpath; 	depth = ext4_extent_tree_depth(inode_ref);	eh = ext4_inode_get_extent_header(inode_ref->inode); 	/* Added 2 for possible tree growing (1 extra depth) */	tpath = ext4_malloc(sizeof(struct ext4_extent_path) * (depth + 2));	if (tpath == NULL)		return ENOMEM; 	/* Zero the path array because we need to make sure that	 * lb_id field of block buffer is zero */	memset(tpath, 0, sizeof(struct ext4_extent_path) * (depth + 2)); 	/* Initialize structure for algorithm start */	k = depth;	tpath[k].block = inode_ref->block;	tpath[k].header = eh; 	/* Walk through the extent tree */	while ((depth = ext4_extent_header_get_depth(eh)) != 0) {		/* Search index in index node by iblock */		ext4_extent_binsearch_idx(tpath[k].header,					  &tpath[k].index, iblock); 		tpath[k].depth = depth;		tpath[k].extent = NULL; 		ext4_assert(tpath[k].index != 0); 		/* Load information for the next iteration */		uint64_t fblock =		    ext4_extent_index_get_fblock(tpath[k].index); 		struct ext4_block block;		ret = ext4_trans_block_get(inode_ref->fs->bdev, &block, fblock);		if (ret != EOK)			goto errout0; 		if (!ext4_extent_block_verify(inode_ref, &block, depth - 1)) {

Lines 1–500 of 2294. Load more