From patchwork Tue Jan 21 09:58:39 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ionut Nicu X-Patchwork-Id: 312841 X-Patchwork-Delegate: trini@ti.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from theia.denx.de (theia.denx.de [85.214.87.163]) by ozlabs.org (Postfix) with ESMTP id 869222C009B for ; Tue, 21 Jan 2014 20:59:11 +1100 (EST) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 956194B170; Tue, 21 Jan 2014 10:59:08 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at theia.denx.de Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7NDhkOxHi4XF; Tue, 21 Jan 2014 10:59:08 +0100 (CET) Received: from theia.denx.de (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id E760A4B184; Tue, 21 Jan 2014 10:59:03 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 8724C4B184 for ; Tue, 21 Jan 2014 10:58:56 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at theia.denx.de Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id XDwHjGdQnfUl for ; Tue, 21 Jan 2014 10:58:50 +0100 (CET) X-policyd-weight: NOT_IN_SBL_XBL_SPAMHAUS=-1.5 NOT_IN_SPAMCOP=-1.5 NOT_IN_BL_NJABL=-1.5 (only DNSBL check requested) Received: from demumfd001.nsn-inter.net (demumfd001.nsn-inter.net [93.183.12.32]) by theia.denx.de (Postfix) with ESMTPS id 620854B170 for ; Tue, 21 Jan 2014 10:58:43 +0100 (CET) Received: from demuprx016.emea.nsn-intra.net ([10.150.129.55]) by demumfd001.nsn-inter.net (8.12.11.20060308/8.12.11) with ESMTP id s0L9wfdU006442 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL); Tue, 21 Jan 2014 10:58:41 +0100 Received: from [10.151.38.129] ([10.151.38.129]) by demuprx016.emea.nsn-intra.net (8.12.11.20060308/8.12.11) with ESMTP id s0L9wdHX005280; Tue, 21 Jan 2014 10:58:40 +0100 Message-ID: <52DE44CF.9090700@nsn.com> Date: Tue, 21 Jan 2014 10:58:39 +0100 From: Ionut Nicu User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.1.0 MIME-Version: 1.0 To: u-boot@lists.denx.de, Manjunatha C Achar , trini@ti.com, Mathias Rulf X-purgate-type: clean X-purgate-Ad: Categorized by eleven eXpurgate (R) http://www.eleven.de X-purgate: clean X-purgate: This mail is considered clean (visit http://www.eleven.de for further information) X-purgate-size: 8816 X-purgate-ID: 151667::1390298322-000025D0-899934E2/0-0/0-0 Subject: [U-Boot] [PATCH] ext4fs: Add ext4 extent cache for read operations X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.11 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: u-boot-bounces@lists.denx.de Errors-To: u-boot-bounces@lists.denx.de In an ext4 filesystem, the inode corresponding to a file has a 60-byte area which contains an extent header structure and up to 4 extent structures (5 x 12 bytes). For files that need more than 4 extents to be represented (either files larger than 4 x 128MB = 512MB or smaller files but very fragmented), ext4 creates extent index structures. Each extent index points to a 4KB physical block where one extent header and additional 340 extents could be stored. The current u-boot ext4 code is very inefficient when it tries to load a file which has extent indexes. For each logical file block the code will read over and over again the same blocks of 4096 bytes from the disk. Since the extent tree in a file is always the same, we can cache the extent structures in memory before actually starting to read the file. This patch creates a simple linked list of structures holding information about all the extents used to represent a file. The list is sorted by the logical block number (ee_block) so that we can easily find the proper extent information for any file block. Without this patch, a 69MB file which had just one extent index pointing to a block with another 6 extents was read in approximately 3 minutes. With this patch applied the same file can be read in almost 20 seconds. Signed-off-by: Ionut Nicu --- fs/ext4/ext4_common.c | 163 +++++++++++++++++++++++++++++-------------------- fs/ext4/ext4_common.h | 3 + fs/ext4/ext4fs.c | 17 +++++- 3 files changed, 117 insertions(+), 66 deletions(-) diff --git a/fs/ext4/ext4_common.c b/fs/ext4/ext4_common.c index 02da75c..1d8c085 100644 --- a/fs/ext4/ext4_common.c +++ b/fs/ext4/ext4_common.c @@ -26,6 +26,7 @@ #include #include #include +#include #include #include "ext4_common.h" @@ -44,6 +45,14 @@ int ext4fs_indir3_blkno = -1; struct ext2_inode *g_parent_inode; static int symlinknest; +struct ext4_extent_node { + uint32_t block; + uint16_t len; + uint64_t start; + struct list_head lh; +}; +static LIST_HEAD(ext4_extent_lh); + #if defined(CONFIG_EXT4_WRITE) uint32_t ext4fs_div_roundup(uint32_t size, uint32_t n) { @@ -1407,45 +1416,101 @@ void ext4fs_allocate_blocks(struct ext2_inode *file_inode, #endif -static struct ext4_extent_header *ext4fs_get_extent_block - (struct ext2_data *data, char *buf, - struct ext4_extent_header *ext_block, - uint32_t fileblock, int log2_blksz) +static void ext4fs_extent_cache_insert(struct ext4_extent_node *new) +{ + struct ext4_extent_node *node; + + list_for_each_entry(node, &ext4_extent_lh, lh) + if (node->block > new->block) { + list_add_tail(&new->lh, &node->lh); + return; + } + list_add_tail(&new->lh, &ext4_extent_lh); +} + +static int __ext4fs_build_extent_cache(struct ext2_data *data, + struct ext4_extent_header *ext_block) { + int blksz = EXT2_BLOCK_SIZE(data); + int log2_blksz = LOG2_BLOCK_SIZE(data) + - get_fs()->dev_desc->log2blksz; + struct ext4_extent_node *node; struct ext4_extent_idx *index; + struct ext4_extent *extent; unsigned long long block; - int blksz = EXT2_BLOCK_SIZE(data); - int i; + char *buf; + int i, err; - while (1) { - index = (struct ext4_extent_idx *)(ext_block + 1); + if (le16_to_cpu(ext_block->eh_magic) != EXT4_EXT_MAGIC) + return -EINVAL; - if (le16_to_cpu(ext_block->eh_magic) != EXT4_EXT_MAGIC) - return 0; - - if (ext_block->eh_depth == 0) - return ext_block; - i = -1; - do { - i++; - if (i >= le16_to_cpu(ext_block->eh_entries)) - break; - } while (fileblock >= le32_to_cpu(index[i].ei_block)); + if (ext_block->eh_depth == 0) { + extent = (struct ext4_extent *)(ext_block + 1); + for (i = 0; i < le16_to_cpu(ext_block->eh_entries); i++) { + node = malloc(sizeof(*node)); + if (!node) + return -ENOMEM; + node->block = le32_to_cpu(extent[i].ee_block); + node->len = le16_to_cpu(extent[i].ee_len); + node->start = (le16_to_cpu(extent[i].ee_start_hi) << 16) + + le32_to_cpu(extent[i].ee_start_lo); + ext4fs_extent_cache_insert(node); + } + return 0; + } - if (--i < 0) - return 0; + index = (struct ext4_extent_idx *)(ext_block + 1); + for (i = 0; i < le16_to_cpu(ext_block->eh_entries); i++) { + buf = malloc(blksz); + if (!buf) + return -ENOMEM; block = le16_to_cpu(index[i].ei_leaf_hi); block = (block << 32) + le32_to_cpu(index[i].ei_leaf_lo); - if (ext4fs_devread((lbaint_t)block << log2_blksz, 0, blksz, - buf)) - ext_block = (struct ext4_extent_header *)buf; - else - return 0; + if (!ext4fs_devread(block << log2_blksz, 0, blksz, buf)) { + free(buf); + return -EIO; + } + + err = __ext4fs_build_extent_cache(data, + (struct ext4_extent_header *) buf); + free(buf); + if (err < 0) + return err; + } + + return 0; +} + +int ext4fs_build_extent_cache(struct ext2_inode *inode) +{ + return __ext4fs_build_extent_cache(ext4fs_root, + (struct ext4_extent_header *) + inode->b.blocks.dir_blocks); +} + +void ext4fs_free_extent_cache(void) +{ + struct ext4_extent_node *node, *tmp; + + list_for_each_entry_safe(node, tmp, &ext4_extent_lh, lh) { + list_del(&node->lh); + free(node); } } +static struct ext4_extent_node *ext4fs_extent_cache_get(uint32_t block) +{ + struct ext4_extent_node *node; + + list_for_each_entry(node, &ext4_extent_lh, lh) + if (block >= node->block && block < node->block + node->len) + return node; + + return NULL; +} + static int ext4fs_blockgroup (struct ext2_data *data, int group, struct ext2_block_group *blkgrp) { @@ -1508,54 +1573,22 @@ long int read_allocated_block(struct ext2_inode *inode, int fileblock) long int rblock; long int perblock_parent; long int perblock_child; - unsigned long long start; + /* get the blocksize of the filesystem */ blksz = EXT2_BLOCK_SIZE(ext4fs_root); log2_blksz = LOG2_BLOCK_SIZE(ext4fs_root) - get_fs()->dev_desc->log2blksz; if (le32_to_cpu(inode->flags) & EXT4_EXTENTS_FL) { - char *buf = zalloc(blksz); - if (!buf) - return -ENOMEM; - struct ext4_extent_header *ext_block; - struct ext4_extent *extent; - int i = -1; - ext_block = - ext4fs_get_extent_block(ext4fs_root, buf, - (struct ext4_extent_header *) - inode->b.blocks.dir_blocks, - fileblock, log2_blksz); - if (!ext_block) { - printf("invalid extent block\n"); - free(buf); - return -EINVAL; - } - - extent = (struct ext4_extent *)(ext_block + 1); - - do { - i++; - if (i >= le16_to_cpu(ext_block->eh_entries)) - break; - } while (fileblock >= le32_to_cpu(extent[i].ee_block)); - if (--i >= 0) { - fileblock -= le32_to_cpu(extent[i].ee_block); - if (fileblock >= le16_to_cpu(extent[i].ee_len)) { - free(buf); - return 0; - } + struct ext4_extent_node *node; - start = le16_to_cpu(extent[i].ee_start_hi); - start = (start << 32) + - le32_to_cpu(extent[i].ee_start_lo); - free(buf); - return fileblock + start; + node = ext4fs_extent_cache_get(fileblock); + if (!node) { + printf("Extent Error\n"); + return -1; } - printf("Extent Error\n"); - free(buf); - return -1; + return fileblock - node->block + node->start; } /* Direct blocks. */ diff --git a/fs/ext4/ext4_common.h b/fs/ext4/ext4_common.h index 5fa1719..a9fd8c6 100644 --- a/fs/ext4/ext4_common.h +++ b/fs/ext4/ext4_common.h @@ -57,6 +57,9 @@ int ext4fs_find_file(const char *path, struct ext2fs_node *rootnode, int ext4fs_iterate_dir(struct ext2fs_node *dir, char *name, struct ext2fs_node **fnode, int *ftype); +int ext4fs_build_extent_cache(struct ext2_inode *inode); +void ext4fs_free_extent_cache(void); + #if defined(CONFIG_EXT4_WRITE) uint32_t ext4fs_div_roundup(uint32_t size, uint32_t n); int ext4fs_checksum_update(unsigned int i); diff --git a/fs/ext4/ext4fs.c b/fs/ext4/ext4fs.c index 735b256..7963f1d 100644 --- a/fs/ext4/ext4fs.c +++ b/fs/ext4/ext4fs.c @@ -176,10 +176,25 @@ int ext4fs_ls(const char *dirname) int ext4fs_read(char *buf, unsigned len) { + int ret; + if (ext4fs_root == NULL || ext4fs_file == NULL) return 0; - return ext4fs_read_file(ext4fs_file, 0, len, buf); + if (le32_to_cpu(ext4fs_file->inode.flags) & EXT4_EXTENTS_FL) { + if (ext4fs_build_extent_cache(&(ext4fs_file->inode))) { + printf("Error building extent cache!\n"); + ret = -1; + goto out_exit; + } + } + + ret = ext4fs_read_file(ext4fs_file, 0, len, buf); + +out_exit: + ext4fs_free_extent_cache(); + + return ret; } int ext4fs_probe(block_dev_desc_t *fs_dev_desc,