From patchwork Wed Jan 31 03:08:32 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 10193139 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 654346020C for ; Wed, 31 Jan 2018 03:08:47 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 54618281DB for ; Wed, 31 Jan 2018 03:08:47 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 4895428329; Wed, 31 Jan 2018 03:08:47 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI, T_DKIM_INVALID, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 70010281DB for ; Wed, 31 Jan 2018 03:08:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751647AbeAaDIp (ORCPT ); Tue, 30 Jan 2018 22:08:45 -0500 Received: from userp2120.oracle.com ([156.151.31.85]:42962 "EHLO userp2120.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751968AbeAaDIp (ORCPT ); Tue, 30 Jan 2018 22:08:45 -0500 Received: from pps.filterd (userp2120.oracle.com [127.0.0.1]) by userp2120.oracle.com (8.16.0.22/8.16.0.22) with SMTP id w0V373V6024681; Wed, 31 Jan 2018 03:08:42 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=subject : from : to : cc : date : message-id : in-reply-to : references : mime-version : content-type : content-transfer-encoding; s=corp-2017-10-26; bh=lXnKvP6inrH7YOy62s20juC2Ce8DtXKL709o2yfjErM=; b=hUGF7E1RzLWEGyI3Z8cFOX8ldHkmshPBtj3Hxrgh3WKtSU4ogp1uHrOKmQI6GFZApOdz b93E6Cq1GWD1uEv4eImg50PNoL6Txc5/+4BUUPSlnvHqAyPFsTlECBhrzsvvxtcXPXcj GoQTpiY2iSsuLtDjkVLm3urWzdxfS9G2S5t+ao4AX6HdF4tMA9dHmQiRpmvvc7JTaIft PpCRrjSYSu3ox6sHaARewN85h4YTUOGDw/9F4O7cPKY4OQIEvvGnqEFDF9oEtraNhZ/V fBIL6EBsv+gQdwFE7yEjmnXywhFKQjgnH74qAGLHmQ3OftTQx6+lOwJGCPKj9MAs1mij 4Q== Received: from userv0021.oracle.com (userv0021.oracle.com [156.151.31.71]) by userp2120.oracle.com with ESMTP id 2fu5bwr18e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 31 Jan 2018 03:08:42 +0000 Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by userv0021.oracle.com (8.14.4/8.14.4) with ESMTP id w0V38gZC008757 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Wed, 31 Jan 2018 03:08:42 GMT Received: from abhmp0019.oracle.com (abhmp0019.oracle.com [141.146.116.25]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id w0V38ff0014506; Wed, 31 Jan 2018 03:08:41 GMT Received: from localhost (/67.169.218.210) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Tue, 30 Jan 2018 19:08:41 -0800 Subject: [PATCH 19/29] xfs_scrub: create a bitmap data structure From: "Darrick J. Wong" To: sandeen@redhat.com, darrick.wong@oracle.com Cc: linux-xfs@vger.kernel.org Date: Tue, 30 Jan 2018 19:08:32 -0800 Message-ID: <151736811230.32164.14128593583786118625.stgit@magnolia> In-Reply-To: <151736799098.32164.15446216987522359103.stgit@magnolia> References: <151736799098.32164.15446216987522359103.stgit@magnolia> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=8790 signatures=668657 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=2 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1711220000 definitions=main-1801310037 Sender: linux-xfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Darrick J. Wong Create an efficient tree-based bitmap data structure. We will use this during the data block scan to record the LBAs of IO errors so that we can report broken files to userspace. Signed-off-by: Darrick J. Wong --- scrub/Makefile | 2 scrub/bitmap.c | 410 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ scrub/bitmap.h | 38 +++++ 3 files changed, 450 insertions(+) create mode 100644 scrub/bitmap.c create mode 100644 scrub/bitmap.h -- To unsubscribe from this list: send the line "unsubscribe linux-xfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/scrub/Makefile b/scrub/Makefile index 858bc40..a9aaa99 100644 --- a/scrub/Makefile +++ b/scrub/Makefile @@ -16,6 +16,7 @@ INSTALL_SCRUB = install-scrub endif # scrub_prereqs HFILES = \ +bitmap.h \ common.h \ counter.h \ disk.h \ @@ -28,6 +29,7 @@ unicrash.h \ xfs_scrub.h CFILES = \ +bitmap.c \ common.c \ counter.c \ disk.c \ diff --git a/scrub/bitmap.c b/scrub/bitmap.c new file mode 100644 index 0000000..a88fd0e --- /dev/null +++ b/scrub/bitmap.c @@ -0,0 +1,410 @@ +/* + * Copyright (C) 2018 Oracle. All Rights Reserved. + * + * Author: Darrick J. Wong + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. + */ +#include +#include +#include +#include +#include +#include +#include +#include +#include "platform_defs.h" +#include "avl64.h" +#include "list.h" +#include "bitmap.h" + +/* + * Space Efficient Bitmap + * + * Implements a space-efficient bitmap. We use an AVL tree to manage + * extent records that tell us which ranges are set; the bitmap key is + * an arbitrary uint64_t. The usual bitmap operations (set, clear, + * test, test and set) are supported, plus we can iterate set ranges. + */ + +#define avl_for_each_range_safe(pos, n, l, first, last) \ + for (pos = (first), n = pos->avl_nextino, l = (last)->avl_nextino; pos != (l); \ + pos = n, n = pos ? pos->avl_nextino : NULL) + +#define avl_for_each_safe(tree, pos, n) \ + for (pos = (tree)->avl_firstino, n = pos ? pos->avl_nextino : NULL; \ + pos != NULL; \ + pos = n, n = pos ? pos->avl_nextino : NULL) + +#define avl_for_each(tree, pos) \ + for (pos = (tree)->avl_firstino; pos != NULL; pos = pos->avl_nextino) + +struct bitmap_node { + struct avl64node btn_node; + uint64_t btn_start; + uint64_t btn_length; +}; + +static uint64_t +extent_start( + struct avl64node *node) +{ + struct bitmap_node *btn; + + btn = container_of(node, struct bitmap_node, btn_node); + return btn->btn_start; +} + +static uint64_t +extent_end( + struct avl64node *node) +{ + struct bitmap_node *btn; + + btn = container_of(node, struct bitmap_node, btn_node); + return btn->btn_start + btn->btn_length; +} + +static struct avl64ops bitmap_ops = { + extent_start, + extent_end, +}; + +/* Initialize a bitmap. */ +bool +bitmap_init( + struct bitmap **bmapp) +{ + struct bitmap *bmap; + + bmap = calloc(1, sizeof(struct bitmap)); + if (!bmap) + return false; + bmap->bt_tree = malloc(sizeof(struct avl64tree_desc)); + if (!bmap->bt_tree) { + free(bmap); + return false; + } + + pthread_mutex_init(&bmap->bt_lock, NULL); + avl64_init_tree(bmap->bt_tree, &bitmap_ops); + *bmapp = bmap; + + return true; +} + +/* Free a bitmap. */ +void +bitmap_free( + struct bitmap **bmapp) +{ + struct bitmap *bmap; + struct avl64node *node; + struct avl64node *n; + struct bitmap_node *ext; + + bmap = *bmapp; + avl_for_each_safe(bmap->bt_tree, node, n) { + ext = container_of(node, struct bitmap_node, btn_node); + free(ext); + } + free(bmap->bt_tree); + *bmapp = NULL; +} + +/* Create a new bitmap extent node. */ +static struct bitmap_node * +bitmap_node_init( + uint64_t start, + uint64_t len) +{ + struct bitmap_node *ext; + + ext = malloc(sizeof(struct bitmap_node)); + if (!ext) + return NULL; + + ext->btn_node.avl_nextino = NULL; + ext->btn_start = start; + ext->btn_length = len; + + return ext; +} + +/* Set a region of bits (locked). */ +static bool +__bitmap_set( + struct bitmap *bmap, + uint64_t start, + uint64_t length) +{ + struct avl64node *firstn; + struct avl64node *lastn; + struct avl64node *pos; + struct avl64node *n; + struct avl64node *l; + struct bitmap_node *ext; + uint64_t new_start; + uint64_t new_length; + struct avl64node *node; + bool res = true; + + /* Find any existing nodes adjacent or within that range. */ + avl64_findranges(bmap->bt_tree, start - 1, start + length + 1, + &firstn, &lastn); + + /* Nothing, just insert a new extent. */ + if (firstn == NULL && lastn == NULL) { + ext = bitmap_node_init(start, length); + if (!ext) + return false; + + node = avl64_insert(bmap->bt_tree, &ext->btn_node); + if (node == NULL) { + free(ext); + errno = EEXIST; + return false; + } + + return true; + } + + assert(firstn != NULL && lastn != NULL); + new_start = start; + new_length = length; + + avl_for_each_range_safe(pos, n, l, firstn, lastn) { + ext = container_of(pos, struct bitmap_node, btn_node); + + /* Bail if the new extent is contained within an old one. */ + if (ext->btn_start <= start && + ext->btn_start + ext->btn_length >= start + length) + return res; + + /* Check for overlapping and adjacent extents. */ + if (ext->btn_start + ext->btn_length >= start || + ext->btn_start <= start + length) { + if (ext->btn_start < start) { + new_start = ext->btn_start; + new_length += ext->btn_length; + } + + if (ext->btn_start + ext->btn_length > + new_start + new_length) + new_length = ext->btn_start + ext->btn_length - + new_start; + + avl64_delete(bmap->bt_tree, pos); + free(ext); + } + } + + ext = bitmap_node_init(new_start, new_length); + if (!ext) + return false; + + node = avl64_insert(bmap->bt_tree, &ext->btn_node); + if (node == NULL) { + free(ext); + errno = EEXIST; + return false; + } + + return res; +} + +/* Set a region of bits. */ +bool +bitmap_set( + struct bitmap *bmap, + uint64_t start, + uint64_t length) +{ + bool res; + + pthread_mutex_lock(&bmap->bt_lock); + res = __bitmap_set(bmap, start, length); + pthread_mutex_unlock(&bmap->bt_lock); + + return res; +} + +#if 0 /* Unused, provided for completeness. */ +/* Clear a region of bits. */ +bool +bitmap_clear( + struct bitmap *bmap, + uint64_t start, + uint64_t len) +{ + struct avl64node *firstn; + struct avl64node *lastn; + struct avl64node *pos; + struct avl64node *n; + struct avl64node *l; + struct bitmap_node *ext; + uint64_t new_start; + uint64_t new_length; + struct avl64node *node; + int stat; + + pthread_mutex_lock(&bmap->bt_lock); + /* Find any existing nodes over that range. */ + avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn); + + /* Nothing, we're done. */ + if (firstn == NULL && lastn == NULL) { + pthread_mutex_unlock(&bmap->bt_lock); + return true; + } + + assert(firstn != NULL && lastn != NULL); + + /* Delete or truncate everything in sight. */ + avl_for_each_range_safe(pos, n, l, firstn, lastn) { + ext = container_of(pos, struct bitmap_node, btn_node); + + stat = 0; + if (ext->btn_start < start) + stat |= 1; + if (ext->btn_start + ext->btn_length > start + len) + stat |= 2; + switch (stat) { + case 0: + /* Extent totally within range; delete. */ + avl64_delete(bmap->bt_tree, pos); + free(ext); + break; + case 1: + /* Extent is left-adjacent; truncate. */ + ext->btn_length = start - ext->btn_start; + break; + case 2: + /* Extent is right-adjacent; move it. */ + ext->btn_length = ext->btn_start + ext->btn_length - + (start + len); + ext->btn_start = start + len; + break; + case 3: + /* Extent overlaps both ends. */ + ext->btn_length = start - ext->btn_start; + new_start = start + len; + new_length = ext->btn_start + ext->btn_length - + new_start; + + ext = bitmap_node_init(new_start, new_length); + if (!ext) + return false; + + node = avl64_insert(bmap->bt_tree, &ext->btn_node); + if (node == NULL) { + errno = EEXIST; + return false; + } + break; + } + } + + pthread_mutex_unlock(&bmap->bt_lock); + return true; +} +#endif + +#ifdef DEBUG +/* Iterate the set regions of this bitmap. */ +bool +bitmap_iterate( + struct bitmap *bmap, + bool (*fn)(uint64_t, uint64_t, void *), + void *arg) +{ + struct avl64node *node; + struct bitmap_node *ext; + bool moveon = true; + + pthread_mutex_lock(&bmap->bt_lock); + avl_for_each(bmap->bt_tree, node) { + ext = container_of(node, struct bitmap_node, btn_node); + moveon = fn(ext->btn_start, ext->btn_length, arg); + if (!moveon) + break; + } + pthread_mutex_unlock(&bmap->bt_lock); + + return moveon; +} +#endif + +/* Do any bitmap extents overlap the given one? (locked) */ +static bool +__bitmap_test( + struct bitmap *bmap, + uint64_t start, + uint64_t len) +{ + struct avl64node *firstn; + struct avl64node *lastn; + + /* Find any existing nodes over that range. */ + avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn); + + return firstn != NULL && lastn != NULL; +} + +/* Is any part of this range set? */ +bool +bitmap_test( + struct bitmap *bmap, + uint64_t start, + uint64_t len) +{ + bool res; + + pthread_mutex_lock(&bmap->bt_lock); + res = __bitmap_test(bmap, start, len); + pthread_mutex_unlock(&bmap->bt_lock); + + return res; +} + +/* Are none of the bits set? */ +bool +bitmap_empty( + struct bitmap *bmap) +{ + return bmap->bt_tree->avl_firstino == NULL; +} + +#ifdef DEBUG +static bool +bitmap_dump_fn( + uint64_t startblock, + uint64_t blockcount, + void *arg) +{ + printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount); + return true; +} + +/* Dump bitmap. */ +void +bitmap_dump( + struct bitmap *bmap) +{ + printf("BITMAP DUMP %p\n", bmap); + bitmap_iterate(bmap, bitmap_dump_fn, NULL); + printf("BITMAP DUMP DONE\n"); +} +#endif diff --git a/scrub/bitmap.h b/scrub/bitmap.h new file mode 100644 index 0000000..e8dcd4f --- /dev/null +++ b/scrub/bitmap.h @@ -0,0 +1,38 @@ +/* + * Copyright (C) 2018 Oracle. All Rights Reserved. + * + * Author: Darrick J. Wong + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. + */ +#ifndef XFS_SCRUB_BITMAP_H_ +#define XFS_SCRUB_BITMAP_H_ + +struct bitmap { + pthread_mutex_t bt_lock; + struct avl64tree_desc *bt_tree; +}; + +bool bitmap_init(struct bitmap **bmap); +void bitmap_free(struct bitmap **bmap); +bool bitmap_set(struct bitmap *bmap, uint64_t start, uint64_t length); +bool bitmap_iterate(struct bitmap *bmap, + bool (*fn)(uint64_t, uint64_t, void *), void *arg); +bool bitmap_test(struct bitmap *bmap, uint64_t start, + uint64_t len); +bool bitmap_empty(struct bitmap *bmap); +void bitmap_dump(struct bitmap *bmap); + +#endif /* XFS_SCRUB_BITMAP_H_ */