From patchwork Mon May 13 15:42:05 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Radek Pazdera X-Patchwork-Id: 243450 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 4C86F2C0091 for ; Tue, 14 May 2013 02:42:59 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753950Ab3EMQmx (ORCPT ); Mon, 13 May 2013 12:42:53 -0400 Received: from mx1.redhat.com ([209.132.183.28]:61866 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753908Ab3EMQmt (ORCPT ); Mon, 13 May 2013 12:42:49 -0400 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r4DGglqb015736 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Mon, 13 May 2013 12:42:47 -0400 Received: from localhost (vpn1-6-144.ams2.redhat.com [10.36.6.144]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r4DGgk5G001740; Mon, 13 May 2013 12:42:46 -0400 From: Radek Pazdera To: linux-ext4@vger.kernel.org Cc: lczerner@redhat.com, kasparek@fit.vutbr.cz, Radek Pazdera Subject: [RFC v2 4/9] ext4: Adding itree structures Date: Mon, 13 May 2013 17:42:05 +0200 Message-Id: <1368459730-3405-5-git-send-email-rpazdera@redhat.com> In-Reply-To: <1368459730-3405-1-git-send-email-rpazdera@redhat.com> References: <1368459730-3405-1-git-send-email-rpazdera@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.24 Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org This commit adds 5 new structures that will be used in the itree code. On-disk: struct itree_entry Single entry in an itree_node. struct itree_node A non-leaf node in the itree. struct itree_leaf_head Comes first in every itree leaf block. struct itree_leaf_entry A dirent in itree leaf. Memory only: struct itree_frame Represents a path through a tree to one of its leaves. struct itree_key For representing the key for itree, which is an inode number and file name hash Signed-off-by: Radek Pazdera --- fs/ext4/namei.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+) diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c index 20cf635..c9b6c91 100644 --- a/fs/ext4/namei.c +++ b/fs/ext4/namei.c @@ -261,6 +261,56 @@ struct dx_tail { struct dx_itree_entry *itree; }; +/* + * itree structures + */ + +/* A single entry in the itree_node */ +struct itree_entry { + __le32 inode; + __le32 hash; + __le64 block; + __u8 fullness; + __u8 flags; +}; + +#define ITREE_NODE_FL_CONT 1 + +/* A non-leaf node of the itree */ +struct itree_node { + __le16 count; + __le16 limit; + __le32 checksum; + __u8 indirect_levels; + struct itree_entry entries[0]; +}; + +/* Comes first in every itree leaf block */ +struct itree_leaf_head { + __le32 checksum; + __le32 used_length; +}; + +/* A dirent with hash in an itree leaf block */ +#define ITREE_LE_HEAD_LEN 4 +struct itree_leaf_entry { + __le32 hash; + struct ext4_dir_entry_2 dirent; +}; + +/* For easier manipulation of the compound key */ +struct itree_key { + u32 inode; + u32 hash; +}; + +/* Represents a position within an itree_node block */ +struct itree_frame { + struct buffer_head *bh; + struct itree_entry *entries; + struct itree_entry *at; +}; + static inline ext4_lblk_t dx_get_block(struct dx_entry *entry); static void dx_set_block(struct dx_entry *entry, ext4_lblk_t value); static inline unsigned dx_get_hash(struct dx_entry *entry);