From patchwork Thu Sep 3 19:44:23 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Omar Sandoval X-Patchwork-Id: 7118751 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 E7A979F1D5 for ; Thu, 3 Sep 2015 19:44:50 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id E7C7A207C5 for ; Thu, 3 Sep 2015 19:44:49 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id E0CDD207C0 for ; Thu, 3 Sep 2015 19:44:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756924AbbICToo (ORCPT ); Thu, 3 Sep 2015 15:44:44 -0400 Received: from mail-pa0-f52.google.com ([209.85.220.52]:34424 "EHLO mail-pa0-f52.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756752AbbICTol (ORCPT ); Thu, 3 Sep 2015 15:44:41 -0400 Received: by padfa1 with SMTP id fa1so13299931pad.1 for ; Thu, 03 Sep 2015 12:44:40 -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=1XrBDmKz6AGH3c/Wpjlmc4IsfZfuO1Cfvij7Y2y7y2Q=; b=L1Bw6dsiFEYAXT6NC21s4tSklfsRa2bV6jYjC5F4G8uvG13actha4uDIEs/vrVS82O Usrn/M8Fx2pYYyAVqfCrG60Ni5L0/Ehc0DCuao05vmUpM6mgoQ5I1+cBo9il+LLZFcEG AdmCxbcxRrp+zlptF4274s/VlfJQUrQMusPK+5ETdGhHM+OEBVt1pXq3xJ4HRzSamqWw +IEoInBdY176404ja5iPtl9beetef204ULDXUdIzL41GTH1KoXB2qLzek0ex4skMsxu2 JuLDByvggOxMnq87o32wVSXu7ZNpg5QKUZ1tzZthcPQZ6PlDViGtr5Paq/n6O8++RJLN QJyQ== X-Gm-Message-State: ALoCoQmyKuUyJiglSahNdI2Xyyn8yNUDbb+HJfH8WluOnCxTYeYjk59+g/2E17PVH2XxTyh5Z1vl X-Received: by 10.68.57.143 with SMTP id i15mr31183030pbq.104.1441309480353; Thu, 03 Sep 2015 12:44:40 -0700 (PDT) Received: from huxley.thefacebook.com ([199.201.64.133]) by smtp.gmail.com with ESMTPSA id y9sm14682638pdp.17.2015.09.03.12.44.39 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 03 Sep 2015 12:44:39 -0700 (PDT) From: Omar Sandoval X-Google-Original-From: Omar Sandoval To: linux-btrfs@vger.kernel.org Cc: Omar Sandoval Subject: [PATCH v2 5/9] Btrfs: introduce the free space B-tree on-disk format Date: Thu, 3 Sep 2015 12:44:23 -0700 Message-Id: <99c35fde78f89920425fdc3973af0598f289d778.1441309178.git.osandov@fb.com> X-Mailer: git-send-email 2.5.1 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 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 147a4df46960..e97a923e9d44 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) \