blob: 5af5ab8dd6b3bb853d2ff3e8bdfadff4fb8a850f [file] [log] [blame]
// SPDX-License-Identifier: GPL-2.0+
/*
* Copyright (C) 2018 Oracle. All Rights Reserved.
* Author: Darrick J. Wong <darrick.wong@oracle.com>
*/
#include "xfs.h"
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>
#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. */
int
bitmap_alloc(
struct bitmap **bmapp)
{
struct bitmap *bmap;
int ret;
bmap = calloc(1, sizeof(struct bitmap));
if (!bmap)
return -errno;
bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
if (!bmap->bt_tree) {
ret = -errno;
goto out;
}
ret = -pthread_mutex_init(&bmap->bt_lock, NULL);
if (ret)
goto out_tree;
avl64_init_tree(bmap->bt_tree, &bitmap_ops);
*bmapp = bmap;
return 0;
out_tree:
free(bmap->bt_tree);
out:
free(bmap);
return ret;
}
/* 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);
free(bmap);
*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;
}
/* Create a new bitmap node and insert it. */
static inline int
__bitmap_insert(
struct bitmap *bmap,
uint64_t start,
uint64_t length)
{
struct bitmap_node *ext;
struct avl64node *node;
ext = bitmap_node_init(start, length);
if (!ext)
return -errno;
node = avl64_insert(bmap->bt_tree, &ext->btn_node);
if (node == NULL) {
free(ext);
return -EEXIST;
}
return 0;
}
/* Set a region of bits (locked). */
static int
__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;
/* 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)
return __bitmap_insert(bmap, start, length);
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 0;
/* 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);
}
}
return __bitmap_insert(bmap, new_start, new_length);
}
/* Set a region of bits. */
int
bitmap_set(
struct bitmap *bmap,
uint64_t start,
uint64_t length)
{
int 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. */
int
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 0;
}
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) {
ret = -errno;
goto out;
}
node = avl64_insert(bmap->bt_tree, &ext->btn_node);
if (node == NULL) {
ret = -EEXIST;
goto out;
}
break;
}
}
out:
pthread_mutex_unlock(&bmap->bt_lock);
return ret;
}
#endif
/* Iterate the set regions of this bitmap. */
int
bitmap_iterate(
struct bitmap *bmap,
int (*fn)(uint64_t, uint64_t, void *),
void *arg)
{
struct avl64node *node;
struct bitmap_node *ext;
int error = 0;
pthread_mutex_lock(&bmap->bt_lock);
avl_for_each(bmap->bt_tree, node) {
ext = container_of(node, struct bitmap_node, btn_node);
error = fn(ext->btn_start, ext->btn_length, arg);
if (error)
break;
}
pthread_mutex_unlock(&bmap->bt_lock);
return error;
}
/* Iterate the set regions of part of this bitmap. */
int
bitmap_iterate_range(
struct bitmap *bmap,
uint64_t start,
uint64_t length,
int (*fn)(uint64_t, uint64_t, void *),
void *arg)
{
struct avl64node *firstn;
struct avl64node *lastn;
struct avl64node *pos;
struct avl64node *n;
struct avl64node *l;
struct bitmap_node *ext;
int ret = 0;
pthread_mutex_lock(&bmap->bt_lock);
avl64_findranges(bmap->bt_tree, start, start + length, &firstn,
&lastn);
if (firstn == NULL && lastn == NULL)
goto out;
avl_for_each_range_safe(pos, n, l, firstn, lastn) {
ext = container_of(pos, struct bitmap_node, btn_node);
ret = fn(ext->btn_start, ext->btn_length, arg);
if (ret)
break;
}
out:
pthread_mutex_unlock(&bmap->bt_lock);
return ret;
}
/* 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 int
bitmap_dump_fn(
uint64_t startblock,
uint64_t blockcount,
void *arg)
{
printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount);
return 0;
}
/* 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