From patchwork Wed Sep 30 03:51:44 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Omar Sandoval X-Patchwork-Id: 7292601 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork1.web.kernel.org (Postfix) with ESMTP id A40339FC02 for ; Wed, 30 Sep 2015 03:52:08 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 60FB420654 for ; Wed, 30 Sep 2015 03:52:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 7300E20656 for ; Wed, 30 Sep 2015 03:52:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753049AbbI3Dvw (ORCPT ); Tue, 29 Sep 2015 23:51:52 -0400 Received: from mail-pa0-f42.google.com ([209.85.220.42]:35602 "EHLO mail-pa0-f42.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752854AbbI3Dvv (ORCPT ); Tue, 29 Sep 2015 23:51:51 -0400 Received: by pacfv12 with SMTP id fv12so26700587pac.2 for ; Tue, 29 Sep 2015 20:51:50 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=dY+1xlcWUT0MBtbkNBjgekrRa1n3x1wFk/FjXyglwZg=; b=NerTcZUFc78ZBMhomTWgsvkaBDyn5ViBa8n+9iKS5e9DGhUaMHuRZTQ7Y0XrnLRmiX gf8++zuavCLaw6O2aZzyKjANx6I6ACSg+LmlQxETzMpmOEs+eJmCeuD2LHnPc/D5lr3X gvDKVaDb7mjJBG8M7jXLsaclSr0ojK/oZimpxw4PNdhNkOCHAf/0IwkMobHovHi6hQO9 vcm8IPXcOG4LfChN3rgoNnSJRU9ylEzxRW/1xTEHs4kMBAR8OJlLYEiw0tVA3p9XGE3j RoprXIU10xjhuGDlz0eBuIRGAuRP/nVwawy1q/6UUah0WU/RiGPgSYFcT6f1WrcOC17F KMlg== X-Gm-Message-State: ALoCoQmCQkVMlI7PeodNWx0W7UvIQpsIpi20dlin/ubhvu/a3f0P1jIDjKv9GQn32RXEOxNLqrFY X-Received: by 10.66.63.39 with SMTP id d7mr2081557pas.38.1443585110578; Tue, 29 Sep 2015 20:51:50 -0700 (PDT) Received: from mew.localdomain (c-73-239-7-70.hsd1.wa.comcast.net. [73.239.7.70]) by smtp.gmail.com with ESMTPSA id xz5sm28393492pbb.12.2015.09.29.20.51.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 29 Sep 2015 20:51:50 -0700 (PDT) From: Omar Sandoval To: linux-btrfs@vger.kernel.org Cc: Omar Sandoval Subject: [PATCH v4 1/2] btrfs-progs: add basic awareness of the free space tree Date: Tue, 29 Sep 2015 20:51:44 -0700 Message-Id: <892a99e13b712431a5fd917fa7ed88347986f102.1443583914.git.osandov@osandov.com> X-Mailer: git-send-email 2.6.0 In-Reply-To: References: Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Omar Sandoval To start, let's tell btrfs-progs to read the free space root and how to print the on-disk format of the free space tree. However, we're not adding the FREE_SPACE_TREE read-only compat bit to the set of supported bits because progs doesn't know how to keep the free space tree consistent. Signed-off-by: Omar Sandoval --- btrfs-debug-tree.c | 4 ++++ ctree.h | 49 ++++++++++++++++++++++++++++++++++++++++++++++++- disk-io.c | 16 +++++++++++++++- print-tree.c | 25 +++++++++++++++++++++++++ 4 files changed, 92 insertions(+), 2 deletions(-) diff --git a/btrfs-debug-tree.c b/btrfs-debug-tree.c index 7d8e876f1a2d..2aa5bd11d1b6 100644 --- a/btrfs-debug-tree.c +++ b/btrfs-debug-tree.c @@ -375,6 +375,10 @@ again: if (!skip) printf("uuid"); break; + case BTRFS_FREE_SPACE_TREE_OBJECTID: + if (!skip) + printf("free space"); + break; case BTRFS_MULTIPLE_OBJECTIDS: if (!skip) { printf("multiple"); diff --git a/ctree.h b/ctree.h index c57f9cad5082..a37f3d1fcc48 100644 --- a/ctree.h +++ b/ctree.h @@ -76,6 +76,9 @@ struct btrfs_free_space_ctl; /* for storing items that use the BTRFS_UUID_KEY* */ #define BTRFS_UUID_TREE_OBJECTID 9ULL +/* tracks free space in block groups. */ +#define BTRFS_FREE_SPACE_TREE_OBJECTID 10ULL + /* for storing balance parameters in the root tree */ #define BTRFS_BALANCE_OBJECTID -4ULL @@ -453,6 +456,8 @@ struct btrfs_super_block { * Compat flags that we support. If any incompat flags are set other than the * ones specified below then we will fail to mount */ +#define BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE (1ULL << 0) + #define BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF (1ULL << 0) #define BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL (1ULL << 1) #define BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS (1ULL << 2) @@ -476,9 +481,10 @@ struct btrfs_super_block { #define BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA (1ULL << 8) #define BTRFS_FEATURE_INCOMPAT_NO_HOLES (1ULL << 9) - #define BTRFS_FEATURE_COMPAT_SUPP 0ULL + #define BTRFS_FEATURE_COMPAT_RO_SUPP 0ULL + #define BTRFS_FEATURE_INCOMPAT_SUPP \ (BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF | \ BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL | \ @@ -898,6 +904,13 @@ struct btrfs_block_group_item { __le64 flags; } __attribute__ ((__packed__)); +struct btrfs_free_space_info { + __le32 extent_count; + __le32 flags; +} __attribute__ ((__packed__)); + +#define BTRFS_FREE_SPACE_USING_BITMAPS (1ULL << 0) + struct btrfs_qgroup_info_item { __le64 generation; __le64 referenced; @@ -965,6 +978,7 @@ struct btrfs_fs_info { struct btrfs_root *dev_root; struct btrfs_root *csum_root; struct btrfs_root *quota_root; + struct btrfs_root *free_space_root; struct rb_root fs_root_tree; @@ -1157,6 +1171,27 @@ struct btrfs_root { */ #define BTRFS_BLOCK_GROUP_ITEM_KEY 192 +/* + * Every block group is represented in the free space tree by a free space info + * item, which stores some accounting information. It is keyed on + * (block_group_start, FREE_SPACE_INFO, block_group_length). + */ +#define BTRFS_FREE_SPACE_INFO_KEY 198 + +/* + * A free space extent tracks an extent of space that is free in a block group. + * It is keyed on (start, FREE_SPACE_EXTENT, length). + */ +#define BTRFS_FREE_SPACE_EXTENT_KEY 199 + +/* + * When a block group becomes very fragmented, we convert it to use bitmaps + * instead of extents. A free space bitmap is keyed on + * (start, FREE_SPACE_BITMAP, length); the corresponding item is a bitmap with + * (length / sectorsize) bits. + */ +#define BTRFS_FREE_SPACE_BITMAP_KEY 200 + #define BTRFS_DEV_EXTENT_KEY 204 #define BTRFS_DEV_ITEM_KEY 216 #define BTRFS_CHUNK_ITEM_KEY 228 @@ -1394,6 +1429,11 @@ BTRFS_SETGET_FUNCS(disk_block_group_flags, BTRFS_SETGET_STACK_FUNCS(block_group_flags, struct btrfs_block_group_item, flags, 64); +/* struct btrfs_free_space_info */ +BTRFS_SETGET_FUNCS(free_space_extent_count, struct btrfs_free_space_info, + extent_count, 32); +BTRFS_SETGET_FUNCS(free_space_flags, struct btrfs_free_space_info, flags, 32); + /* struct btrfs_inode_ref */ BTRFS_SETGET_FUNCS(inode_ref_name_len, struct btrfs_inode_ref, name_len, 16); BTRFS_SETGET_STACK_FUNCS(stack_inode_ref_name_len, struct btrfs_inode_ref, name_len, 16); @@ -2193,6 +2233,13 @@ static inline int btrfs_fs_incompat(struct btrfs_fs_info *fs_info, u64 flag) return !!(btrfs_super_incompat_flags(disk_super) & flag); } +static inline int btrfs_fs_compat_ro(struct btrfs_fs_info *fs_info, u64 flag) +{ + struct btrfs_super_block *disk_super; + disk_super = fs_info->super_copy; + return !!(btrfs_super_compat_ro_flags(disk_super) & flag); +} + /* helper function to cast into the data area of the leaf. */ #define btrfs_item_ptr(leaf, slot, type) \ ((type *)(btrfs_leaf_data(leaf) + \ diff --git a/disk-io.c b/disk-io.c index 8496aded31c4..ae9d6e1abb23 100644 --- a/disk-io.c +++ b/disk-io.c @@ -818,6 +818,7 @@ void btrfs_free_fs_info(struct btrfs_fs_info *fs_info) free(fs_info->dev_root); free(fs_info->csum_root); free(fs_info->quota_root); + free(fs_info->free_space_root); free(fs_info->super_copy); free(fs_info->log_root_tree); free(fs_info); @@ -839,12 +840,13 @@ struct btrfs_fs_info *btrfs_new_fs_info(int writable, u64 sb_bytenr) fs_info->dev_root = calloc(1, sizeof(struct btrfs_root)); fs_info->csum_root = calloc(1, sizeof(struct btrfs_root)); fs_info->quota_root = calloc(1, sizeof(struct btrfs_root)); + fs_info->free_space_root = calloc(1, sizeof(struct btrfs_root)); fs_info->super_copy = calloc(1, BTRFS_SUPER_INFO_SIZE); if (!fs_info->tree_root || !fs_info->extent_root || !fs_info->chunk_root || !fs_info->dev_root || !fs_info->csum_root || !fs_info->quota_root || - !fs_info->super_copy) + !fs_info->free_space_root || !fs_info->super_copy) goto free_all; extent_io_tree_init(&fs_info->extent_cache); @@ -1025,6 +1027,16 @@ int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info, u64 root_tree_bytenr, if (ret == 0) fs_info->quota_enabled = 1; + if (btrfs_fs_compat_ro(fs_info, BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) { + ret = find_and_setup_root(root, fs_info, BTRFS_FREE_SPACE_TREE_OBJECTID, + fs_info->free_space_root); + if (ret) { + printk("Couldn't read free space tree\n"); + return -EIO; + } + fs_info->free_space_root->track_dirty = 1; + } + ret = find_and_setup_log_root(root, fs_info, sb); if (ret) { printk("Couldn't setup log root tree\n"); @@ -1050,6 +1062,8 @@ int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info, u64 root_tree_bytenr, void btrfs_release_all_roots(struct btrfs_fs_info *fs_info) { + if (fs_info->free_space_root) + free_extent_buffer(fs_info->free_space_root->node); if (fs_info->quota_root) free_extent_buffer(fs_info->quota_root->node); if (fs_info->csum_root) diff --git a/print-tree.c b/print-tree.c index dc1d2764ae91..9dc058b58bde 100644 --- a/print-tree.c +++ b/print-tree.c @@ -610,6 +610,15 @@ static void print_key_type(u64 objectid, u8 type) case BTRFS_BLOCK_GROUP_ITEM_KEY: printf("BLOCK_GROUP_ITEM"); break; + case BTRFS_FREE_SPACE_INFO_KEY: + printf("FREE_SPACE_INFO"); + break; + case BTRFS_FREE_SPACE_EXTENT_KEY: + printf("FREE_SPACE_EXTENT"); + break; + case BTRFS_FREE_SPACE_BITMAP_KEY: + printf("FREE_SPACE_BITMAP"); + break; case BTRFS_CHUNK_ITEM_KEY: printf("CHUNK_ITEM"); break; @@ -728,6 +737,9 @@ static void print_objectid(u64 objectid, u8 type) case BTRFS_UUID_TREE_OBJECTID: printf("UUID_TREE"); break; + case BTRFS_FREE_SPACE_TREE_OBJECTID: + printf("FREE_SPACE_TREE"); + break; case BTRFS_MULTIPLE_OBJECTIDS: printf("MULTIPLE"); break; @@ -810,6 +822,7 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l) struct btrfs_dev_extent *dev_extent; struct btrfs_disk_key disk_key; struct btrfs_block_group_item bg_item; + struct btrfs_free_space_info *free_info; struct btrfs_dir_log_item *dlog; struct btrfs_qgroup_info_item *qg_info; struct btrfs_qgroup_limit_item *qg_limit; @@ -947,6 +960,18 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l) (unsigned long long)btrfs_block_group_chunk_objectid(&bg_item), flags_str); break; + case BTRFS_FREE_SPACE_INFO_KEY: + free_info = btrfs_item_ptr(l, i, struct btrfs_free_space_info); + printf("\t\tfree space info extent count %u flags %u\n", + (unsigned)btrfs_free_space_extent_count(l, free_info), + (unsigned)btrfs_free_space_flags(l, free_info)); + break; + case BTRFS_FREE_SPACE_EXTENT_KEY: + printf("\t\tfree space extent\n"); + break; + case BTRFS_FREE_SPACE_BITMAP_KEY: + printf("\t\tfree space bitmap\n"); + break; case BTRFS_CHUNK_ITEM_KEY: print_chunk(l, btrfs_item_ptr(l, i, struct btrfs_chunk)); break;