/* * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com) * 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_dir_idx.c * @brief Directory indexing procedures. */ #include <ext4_config.h>#include <ext4_types.h>#include <ext4_misc.h>#include <ext4_errno.h>#include <ext4_debug.h> #include <ext4_trans.h>#include <ext4_dir_idx.h>#include <ext4_dir.h>#include <ext4_blockdev.h>#include <ext4_fs.h>#include <ext4_super.h>#include <ext4_inode.h>#include <ext4_crc32.h>#include <ext4_hash.h> #include <string.h>#include <stdlib.h> /**@brief Get hash version used in directory index. * @param root_info Pointer to root info structure of index * @return Hash algorithm version */static inline uint8_text4_dir_dx_rinfo_get_hash_version(struct ext4_dir_idx_rinfo *ri){	return ri->hash_version;} /**@brief Set hash version, that will be used in directory index. * @param root_info Pointer to root info structure of index * @param v Hash algorithm version */static inline voidext4_dir_dx_rinfo_set_hash_version(struct ext4_dir_idx_rinfo *ri, uint8_t v){	ri->hash_version = v;} /**@brief Get length of root_info structure in bytes. * @param root_info Pointer to root info structure of index * @return Length of the structure */static inline uint8_text4_dir_dx_rinfo_get_info_length(struct ext4_dir_idx_rinfo *ri){	return ri->info_length;} /**@brief Set length of root_info structure in bytes. * @param root_info   Pointer to root info structure of index * @param info_length Length of the structure */static inline voidext4_dir_dx_root_info_set_info_length(struct ext4_dir_idx_rinfo *ri,				      uint8_t len){	ri->info_length = len;} /**@brief Get number of indirect levels of HTree. * @param root_info Pointer to root info structure of index * @return Height of HTree (actually only 0 or 1) */static inline uint8_text4_dir_dx_rinfo_get_indirect_levels(struct ext4_dir_idx_rinfo *ri){	return ri->indirect_levels;} /**@brief Set number of indirect levels of HTree. * @param root_info Pointer to root info structure of index * @param lvl Height of HTree (actually only 0 or 1) */static inline voidext4_dir_dx_rinfo_set_indirect_levels(struct ext4_dir_idx_rinfo *ri, uint8_t l){	ri->indirect_levels = l;} /**@brief Get maximum number of index node entries. * @param climit Pointer to counlimit structure * @return Maximum of entries in node */static inline uint16_text4_dir_dx_climit_get_limit(struct ext4_dir_idx_climit *climit){	return to_le16(climit->limit);} /**@brief Set maximum number of index node entries. * @param climit Pointer to counlimit structure * @param limit Maximum of entries in node */static inline voidext4_dir_dx_climit_set_limit(struct ext4_dir_idx_climit *climit, uint16_t limit){	climit->limit = to_le16(limit);} /**@brief Get current number of index node entries. * @param climit Pointer to counlimit structure * @return Number of entries in node */static inline uint16_text4_dir_dx_climit_get_count(struct ext4_dir_idx_climit *climit){	return to_le16(climit->count);} /**@brief Set current number of index node entries. * @param climit Pointer to counlimit structure * @param count Number of entries in node */static inline voidext4_dir_dx_climit_set_count(struct ext4_dir_idx_climit *climit, uint16_t count){	climit->count = to_le16(count);} /**@brief Get hash value of index entry. * @param entry Pointer to index entry * @return Hash value */static inline uint32_text4_dir_dx_entry_get_hash(struct ext4_dir_idx_entry *entry){	return to_le32(entry->hash);} /**@brief Set hash value of index entry. * @param entry Pointer to index entry * @param hash  Hash value */static inline voidext4_dir_dx_entry_set_hash(struct ext4_dir_idx_entry *entry, uint32_t hash){	entry->hash = to_le32(hash);} /**@brief Get block address where child node is located. * @param entry Pointer to index entry * @return Block address of child node */static inline uint32_text4_dir_dx_entry_get_block(struct ext4_dir_idx_entry *entry){	return to_le32(entry->block);} /**@brief Set block address where child node is located. * @param entry Pointer to index entry * @param block Block address of child node */static inline voidext4_dir_dx_entry_set_block(struct ext4_dir_idx_entry *entry, uint32_t block){	entry->block = to_le32(block);} /**@brief Sort entry item.*/struct ext4_dx_sort_entry {	uint32_t hash;	uint32_t rec_len;	void *dentry;}; static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,				   const char *name){	return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,			       &hinfo->hash, &hinfo->minor_hash);} #if CONFIG_META_CSUM_ENABLEstatic uint32_t ext4_dir_dx_checksum(struct ext4_inode_ref *inode_ref, void *de,				     int count_offset, int count,				     struct ext4_dir_idx_tail *t){	uint32_t orig_cum, csum = 0;	struct ext4_sblock *sb = &inode_ref->fs->sb;	int sz; 	/* Compute the checksum only if the filesystem supports it */	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;		ino_gen = to_le32(ext4_inode_get_generation(inode_ref->inode)); 		sz = count_offset + (count * sizeof(struct ext4_dir_idx_tail));		orig_cum = t->checksum;		t->checksum = 0;		/* First calculate crc32 checksum against fs uuid */		csum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid, sizeof(sb->uuid));		/* Then calculate crc32 checksum against inode number		 * and inode generation */		csum = ext4_crc32c(csum, &ino_index, sizeof(ino_index));		csum = ext4_crc32c(csum, &ino_gen, sizeof(ino_gen));		/* After that calculate crc32 checksum against all the dx_entry */		csum = ext4_crc32c(csum, de, sz);		/* Finally calculate crc32 checksum for dx_tail */		csum = ext4_crc32c(csum, t, sizeof(struct ext4_dir_idx_tail));		t->checksum = orig_cum;	}	return csum;} static struct ext4_dir_idx_climit *ext4_dir_dx_get_climit(struct ext4_inode_ref *inode_ref,			   struct ext4_dir_en *dirent, int *offset){	struct ext4_dir_en *dp;	struct ext4_dir_idx_root *root;	struct ext4_sblock *sb = &inode_ref->fs->sb;	uint32_t block_size = ext4_sb_get_block_size(sb);	uint16_t entry_len = ext4_dir_en_get_entry_len(dirent);	int count_offset;  	if (entry_len == 12) {		root = (struct ext4_dir_idx_root *)dirent;		dp = (struct ext4_dir_en *)&root->dots[1];		if (ext4_dir_en_get_entry_len(dp) != (block_size - 12))			return NULL;		if (root->info.reserved_zero)			return NULL;		if (root->info.info_length != sizeof(struct ext4_dir_idx_rinfo))			return NULL;		count_offset = 32;	} else if (entry_len == block_size) {		count_offset = 8;	} else {		return NULL;	} 	if (offset)		*offset = count_offset;	return (struct ext4_dir_idx_climit *)(((char *)dirent) + count_offset);} /* * BIG FAT NOTES: *       Currently we do not verify the checksum of HTree node. */static bool ext4_dir_dx_csum_verify(struct ext4_inode_ref *inode_ref,				    struct ext4_dir_en *de){	struct ext4_sblock *sb = &inode_ref->fs->sb;	uint32_t block_size = ext4_sb_get_block_size(sb);	int coff, limit, cnt; 	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {		struct ext4_dir_idx_climit *climit;		climit = ext4_dir_dx_get_climit(inode_ref, de, &coff);		if (!climit) {			/* Directory seems corrupted. */			return true;		}		struct ext4_dir_idx_tail *t;		limit = ext4_dir_dx_climit_get_limit(climit);		cnt = ext4_dir_dx_climit_get_count(climit);		if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) >		    (block_size - sizeof(struct ext4_dir_idx_tail))) {			/* There is no space to hold the checksum */			return true;		}		t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit); 		uint32_t c;		c = to_le32(ext4_dir_dx_checksum(inode_ref, de, coff, cnt, t));		if (t->checksum != c)			return false;	}	return true;}  static void ext4_dir_set_dx_csum(struct ext4_inode_ref *inode_ref,				 struct ext4_dir_en *dirent){	int coff, limit, count;	struct ext4_sblock *sb = &inode_ref->fs->sb;	uint32_t block_size = ext4_sb_get_block_size(sb); 	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {		struct ext4_dir_idx_climit *climit;		climit = ext4_dir_dx_get_climit(inode_ref, dirent, &coff);		if (!climit) {			/* Directory seems corrupted. */			return;		}		struct ext4_dir_idx_tail *t;		limit = ext4_dir_dx_climit_get_limit(climit);		count = ext4_dir_dx_climit_get_count(climit);		if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) >		   (block_size - sizeof(struct ext4_dir_idx_tail))) {			/* There is no space to hold the checksum */			return;		} 		t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit);		t->checksum = to_le32(ext4_dir_dx_checksum(inode_ref, dirent,					coff, count, t));	}}#else#define ext4_dir_dx_csum_verify(...) true#define ext4_dir_set_dx_csum(...)#endif /****************************************************************************/ int ext4_dir_dx_init(struct ext4_inode_ref *dir, struct ext4_inode_ref *parent){	/* Load block 0, where will be index root located */	ext4_fsblk_t fblock;	uint32_t iblock = 0;	bool need_append =		(ext4_inode_get_size(&dir->fs->sb, dir->inode)			< EXT4_DIR_DX_INIT_BCNT)		? true : false;	struct ext4_sblock *sb = &dir->fs->sb;	uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);	struct ext4_block block; 	int rc; 	if (!need_append)		rc = ext4_fs_init_inode_dblk_idx(dir, iblock, &fblock);	else		rc = ext4_fs_append_inode_dblk(dir, &fblock, &iblock); 	if (rc != EOK)		return rc; 	rc = ext4_trans_block_get_noread(dir->fs->bdev, &block, fblock);	if (rc != EOK)		return rc; 	/* Initialize pointers to data structures */	struct ext4_dir_idx_root *root = (void *)block.data;	struct ext4_dir_idx_rinfo *info = &(root->info); 	memset(root, 0, sizeof(struct ext4_dir_idx_root));	struct ext4_dir_en *de; 	/* Initialize dot entries */	de = (struct ext4_dir_en *)root->dots;	ext4_dir_write_entry(sb, de, 12, dir, ".", strlen(".")); 	de = (struct ext4_dir_en *)(root->dots + 1);	uint16_t elen = block_size - 12;	ext4_dir_write_entry(sb, de, elen, parent, "..", strlen("..")); 	/* Initialize root info structure */	uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version); 	ext4_dir_dx_rinfo_set_hash_version(info, hash_version);	ext4_dir_dx_rinfo_set_indirect_levels(info, 0);	ext4_dir_dx_root_info_set_info_length(info, 8); 	/* Set limit and current number of entries */	struct ext4_dir_idx_climit *climit;	climit = (struct ext4_dir_idx_climit *)root->en; 	ext4_dir_dx_climit_set_count(climit, 1); 	uint32_t entry_space;	entry_space = block_size - 2 * sizeof(struct ext4_dir_idx_dot_en) -			sizeof(struct ext4_dir_idx_rinfo); 	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))		entry_space -= sizeof(struct ext4_dir_idx_tail); 	uint16_t root_limit = entry_space / sizeof(struct ext4_dir_idx_entry);	ext4_dir_dx_climit_set_limit(climit, root_limit); 	/* Append new block, where will be new entries inserted in the future */	iblock++;	if (!need_append)		rc = ext4_fs_init_inode_dblk_idx(dir, iblock, &fblock);	else		rc = ext4_fs_append_inode_dblk(dir, &fblock, &iblock); 	if (rc != EOK) {		ext4_block_set(dir->fs->bdev, &block);		return rc;	} 	struct ext4_block new_block;	rc = ext4_trans_block_get_noread(dir->fs->bdev, &new_block, fblock);	if (rc != EOK) {		ext4_block_set(dir->fs->bdev, &block);		return rc;	} 	/* Fill the whole block with empty entry */	struct ext4_dir_en *be = (void *)new_block.data; 	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {		uint16_t len = block_size - sizeof(struct ext4_dir_entry_tail);		ext4_dir_en_set_entry_len(be, len);		ext4_dir_en_set_name_len(sb, be, 0);		ext4_dir_en_set_inode_type(sb, be, EXT4_DE_UNKNOWN);		ext4_dir_init_entry_tail(EXT4_DIRENT_TAIL(be, block_size));		ext4_dir_set_csum(dir, be);	} else {		ext4_dir_en_set_entry_len(be, block_size);	} 	ext4_dir_en_set_inode(be, 0); 	ext4_trans_set_block_dirty(new_block.buf);	rc = ext4_block_set(dir->fs->bdev, &new_block);	if (rc != EOK) {		ext4_block_set(dir->fs->bdev, &block);		return rc;	} 	/* Connect new block to the only entry in index */	struct ext4_dir_idx_entry *entry = root->en;	ext4_dir_dx_entry_set_block(entry, iblock); 	ext4_dir_set_dx_csum(dir, (struct ext4_dir_en *)block.data);	ext4_trans_set_block_dirty(block.buf); 	return ext4_block_set(dir->fs->bdev, &block);} /**@brief Initialize hash info structure necessary for index operations. * @param hinfo      Pointer to hinfo to be initialized * @param root_block Root block (number 0) of index * @param sb         Pointer to superblock * @param name_len   Length of name to be computed hash value from * @param name       Name to be computed hash value from * @return Standard error code */static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,			       struct ext4_block *root_block,			       struct ext4_sblock *sb, size_t name_len,			       const char *name){	struct ext4_dir_idx_root *root; 	root = (struct ext4_dir_idx_root *)root_block->data;	if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&	    (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&	    (root->info.hash_version != EXT2_HTREE_TEA))		return EXT4_ERR_BAD_DX_DIR; 	/* Check unused flags */	if (root->info.unused_flags != 0)		return EXT4_ERR_BAD_DX_DIR; 	/* Check indirect levels */	if (root->info.indirect_levels > 1)		return EXT4_ERR_BAD_DX_DIR; 	/* Check if node limit is correct */	uint32_t block_size = ext4_sb_get_block_size(sb);	uint32_t entry_space = block_size;	entry_space -= 2 * sizeof(struct ext4_dir_idx_dot_en);	entry_space -= sizeof(struct ext4_dir_idx_rinfo);	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))

Lines 1–500 of 1404. Load more