From patchwork Mon Sep 14 06:04:12 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Omar Sandoval X-Patchwork-Id: 7173111 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 79F3E9F39B for ; Mon, 14 Sep 2015 06:04:51 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 82EAF206AA for ; Mon, 14 Sep 2015 06:04:50 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 7A3CE206A9 for ; Mon, 14 Sep 2015 06:04:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752047AbbINGEr (ORCPT ); Mon, 14 Sep 2015 02:04:47 -0400 Received: from mail-pa0-f52.google.com ([209.85.220.52]:34602 "EHLO mail-pa0-f52.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750801AbbINGE3 (ORCPT ); Mon, 14 Sep 2015 02:04:29 -0400 Received: by padhy16 with SMTP id hy16so133931500pad.1 for ; Sun, 13 Sep 2015 23:04:29 -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:in-reply-to:references; bh=rKl022siDwpxKtNmE8h+Dxc2j1aes8g/ldJq+NJuoUA=; b=WjjlLsvbTQ3Zzl/OBeOUmgqABjsUWTcyFkPL0PyTYg4FejYZ4ujdPR9QMU6/7UyjOd vMyQwAeMMynWIdtVacf/vZQXENqxNcVqn5s3Hez6lJi8U+HOyhfzGE9R5mQF/AjHSald t2UnTEqRKBueJM6phG8i5r3IwFpoReE3ApbCdZm7qYV9B3C+Me4CoCHdwgh4GDot3aX0 zBXh+cFOF4ZDiBxKOc4G9KblsdoWiL5cgPlqBVLqIppbgXcHaJ9KT1lw2qWD14pasNET /o2MXV4LKaFabwiyNxik7T+wNLHNm3pS7IrDsNTXgyZbp1NXjDfKvRNVPjMPjynK1juU M00Q== X-Gm-Message-State: ALoCoQlMSnA0sDs0TCu7XrboHCC1hN1PyVZVAgLHTXZ8N0a8+msX3lSEjSkufrjBhI6O1O12ImSZ X-Received: by 10.68.242.42 with SMTP id wn10mr31307257pbc.77.1442210669384; Sun, 13 Sep 2015 23:04:29 -0700 (PDT) Received: from mew.localdomain (c-76-22-74-63.hsd1.wa.comcast.net. [76.22.74.63]) by smtp.gmail.com with ESMTPSA id ns3sm13636477pbc.77.2015.09.13.23.04.28 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 13 Sep 2015 23:04:28 -0700 (PDT) From: Omar Sandoval To: linux-btrfs@vger.kernel.org Cc: Omar Sandoval Subject: [PATCH v3 5/9] Btrfs: introduce the free space B-tree on-disk format Date: Sun, 13 Sep 2015 23:04:12 -0700 Message-Id: X-Mailer: git-send-email 2.5.2 In-Reply-To: References: 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 The on-disk format for the free space tree is straightforward. Each block group is represented in the free space tree by a free space info item that stores accounting information: whether the free space for this block group is stored as bitmaps or extents and how many extents of free space exist for this block group (regardless of which format is being used in the tree). Extents are (start, FREE_SPACE_EXTENT, length) keys with no corresponding item, and bitmaps instead have the FREE_SPACE_BITMAP type and have a bitmap item attached, which is just an array of bytes. Reviewed-by: Josef Bacik Signed-off-by: Omar Sandoval --- fs/btrfs/ctree.h | 38 ++++++++++++++++++++++++++++++++++++++ include/trace/events/btrfs.h | 3 ++- 2 files changed, 40 insertions(+), 1 deletion(-) diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 7ad1bdb667db..b166e5c26afe 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -96,6 +96,9 @@ struct btrfs_ordered_sum; /* for storing items that use the BTRFS_UUID_KEY* types */ #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 @@ -500,6 +503,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) @@ -1061,6 +1066,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) + #define BTRFS_QGROUP_LEVEL_SHIFT 48 static inline u64 btrfs_qgroup_level(u64 qgroupid) { @@ -2064,6 +2076,27 @@ struct btrfs_ioctl_defrag_range_args { */ #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 @@ -2464,6 +2497,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_FUNCS(inode_ref_index, struct btrfs_inode_ref, index, 64); diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h index 0b73af9be12f..e6289e62a2a8 100644 --- a/include/trace/events/btrfs.h +++ b/include/trace/events/btrfs.h @@ -45,7 +45,8 @@ struct btrfs_qgroup_operation; { BTRFS_TREE_LOG_OBJECTID, "TREE_LOG" }, \ { BTRFS_QUOTA_TREE_OBJECTID, "QUOTA_TREE" }, \ { BTRFS_TREE_RELOC_OBJECTID, "TREE_RELOC" }, \ - { BTRFS_UUID_TREE_OBJECTID, "UUID_RELOC" }, \ + { BTRFS_UUID_TREE_OBJECTID, "UUID_TREE" }, \ + { BTRFS_FREE_SPACE_TREE_OBJECTID, "FREE_SPACE_TREE" }, \ { BTRFS_DATA_RELOC_TREE_OBJECTID, "DATA_RELOC_TREE" }) #define show_root_type(obj) \