From patchwork Fri Mar 1 23:28:52 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 10836247 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 03D1A1390 for ; Fri, 1 Mar 2019 23:29:01 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CDA472CB88 for ; Fri, 1 Mar 2019 23:29:00 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id BF03B2C227; Fri, 1 Mar 2019 23:29:00 +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=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, 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 4463B2ACCD for ; Fri, 1 Mar 2019 23:28:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726002AbfCAX26 (ORCPT ); Fri, 1 Mar 2019 18:28:58 -0500 Received: from userp2130.oracle.com ([156.151.31.86]:47384 "EHLO userp2130.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725996AbfCAX26 (ORCPT ); Fri, 1 Mar 2019 18:28:58 -0500 Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.27/8.16.0.27) with SMTP id x21NSsaW126361 for ; Fri, 1 Mar 2019 23:28:54 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-2018-07-02; bh=Otw6ksLkj0A7fSaeIBEZ1pY9M13OMCGJdpvOm3oHHsY=; b=oUT215SZ9T1dVUeiAsA6c3Us+o3KThCS43zMYYw1wqsTZewfMTq4VdsV1bYcXqb2zraN B1a9XuVkWm3sK5L3tyYmkEnRvN2Txgut8GZNzsmEcj5AoN2C7OhQNechqkWRuxBT0QYF l3ATTGv6MO8fO4o83lmnE7E6D2AkxHPTXZDHcYcktaf6+8SUbwzAf6g3vCjtdSusUI/J 3Ykcwz3jYXLgOUjWY1CSyQRPNjvK5b5kfL8s6tqS1r18vdocapTbdZRrRvv7PoCfo/RF TKnas6iexI7R5YrNYpt7HH9BTHdP6bIAJffDVq+THgmn7CDtYfbgO6ZpllHLOYlNnoqR RA== Received: from userv0021.oracle.com (userv0021.oracle.com [156.151.31.71]) by userp2130.oracle.com with ESMTP id 2qtwkut932-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Fri, 01 Mar 2019 23:28:53 +0000 Received: from userv0122.oracle.com (userv0122.oracle.com [156.151.31.75]) by userv0021.oracle.com (8.14.4/8.14.4) with ESMTP id x21NSr9g011693 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Fri, 1 Mar 2019 23:28:53 GMT Received: from abhmp0020.oracle.com (abhmp0020.oracle.com [141.146.116.26]) by userv0122.oracle.com (8.14.4/8.14.4) with ESMTP id x21NSrO6021439 for ; Fri, 1 Mar 2019 23:28:53 GMT Received: from localhost (/10.159.229.175) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Fri, 01 Mar 2019 15:28:52 -0800 Subject: [PATCH 19/23] libfrog: hoist bitmap out of scrub From: "Darrick J. Wong" To: darrick.wong@oracle.com Cc: linux-xfs@vger.kernel.org Date: Fri, 01 Mar 2019 15:28:52 -0800 Message-ID: <155148293203.16677.14341643034136071964.stgit@magnolia> In-Reply-To: <155148280859.16677.6057998944865066232.stgit@magnolia> References: <155148280859.16677.6057998944865066232.stgit@magnolia> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=9182 signatures=668685 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 priorityscore=1501 malwarescore=0 suspectscore=3 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1810050000 definitions=main-1903010162 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 Move the bitmap code to libfrog so that we can use bitmaps in xfs_repair. Signed-off-by: Darrick J. Wong --- include/bitmap.h | 24 +++ libfrog/Makefile | 1 libfrog/bitmap.c | 393 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ scrub/Makefile | 2 scrub/bitmap.c | 393 ------------------------------------------------------ scrub/bitmap.h | 24 --- 6 files changed, 418 insertions(+), 419 deletions(-) create mode 100644 include/bitmap.h create mode 100644 libfrog/bitmap.c delete mode 100644 scrub/bitmap.c delete mode 100644 scrub/bitmap.h diff --git a/include/bitmap.h b/include/bitmap.h new file mode 100644 index 00000000..e29a4335 --- /dev/null +++ b/include/bitmap.h @@ -0,0 +1,24 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * Copyright (C) 2018 Oracle. All Rights Reserved. + * Author: Darrick J. Wong + */ +#ifndef LIBFROG_BITMAP_H_ +#define LIBFROG_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 /* LIBFROG_BITMAP_H_ */ diff --git a/libfrog/Makefile b/libfrog/Makefile index dbff9596..f5a0539b 100644 --- a/libfrog/Makefile +++ b/libfrog/Makefile @@ -12,6 +12,7 @@ LT_AGE = 0 CFILES = \ avl64.c \ +bitmap.c \ convert.c \ crc32.c \ fsgeom.c \ diff --git a/libfrog/bitmap.c b/libfrog/bitmap.c new file mode 100644 index 00000000..aecdba0d --- /dev/null +++ b/libfrog/bitmap.c @@ -0,0 +1,393 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * Copyright (C) 2018 Oracle. All Rights Reserved. + * Author: Darrick J. Wong + */ +#include "xfs.h" +#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/Makefile b/scrub/Makefile index 04921888..1fb9ed1d 100644 --- a/scrub/Makefile +++ b/scrub/Makefile @@ -31,7 +31,6 @@ endif endif # scrub_prereqs HFILES = \ -bitmap.h \ common.h \ counter.h \ disk.h \ @@ -48,7 +47,6 @@ vfs.h \ xfs_scrub.h CFILES = \ -bitmap.c \ common.c \ counter.c \ disk.c \ diff --git a/scrub/bitmap.c b/scrub/bitmap.c deleted file mode 100644 index aecdba0d..00000000 --- a/scrub/bitmap.c +++ /dev/null @@ -1,393 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0+ -/* - * Copyright (C) 2018 Oracle. All Rights Reserved. - * Author: Darrick J. Wong - */ -#include "xfs.h" -#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 deleted file mode 100644 index e9746a12..00000000 --- a/scrub/bitmap.h +++ /dev/null @@ -1,24 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0+ -/* - * Copyright (C) 2018 Oracle. All Rights Reserved. - * Author: Darrick J. Wong - */ -#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_ */