[thirdparty/xfsprogs-dev.git] / libfrog / bitmap.c

// 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. */
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. */
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;
}
#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 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
Commit	Line	Data
959ef981	1	// SPDX-License-Identifier: GPL-2.0+
0cf6f686 DW	2	/*
0cf6f686 DW	3	* Copyright (C) 2018 Oracle. All Rights Reserved.
0cf6f686	4	* Author: Darrick J. Wong <darrick.wong@oracle.com>
0cf6f686	5	*/
a440f877	6	#include "xfs.h"
0cf6f686 DW	7	#include <stdint.h>
0cf6f686 DW	8	#include <stdlib.h>
0cf6f686	9	#include <assert.h>
0cf6f686 DW	10	#include <pthread.h>
	11	#include "platform_defs.h"
	12	#include "avl64.h"
	13	#include "list.h"
	14	#include "bitmap.h"
	15
	16	/*
	17	* Space Efficient Bitmap
	18	*
	19	* Implements a space-efficient bitmap. We use an AVL tree to manage
	20	* extent records that tell us which ranges are set; the bitmap key is
	21	* an arbitrary uint64_t. The usual bitmap operations (set, clear,
	22	* test, test and set) are supported, plus we can iterate set ranges.
	23	*/
	24
	25	#define avl_for_each_range_safe(pos, n, l, first, last) \
233fabee DW	26	for (pos = (first), n = pos->avl_nextino, l = (last)->avl_nextino; \
233fabee DW	27	pos != (l); \
0cf6f686 DW	28	pos = n, n = pos ? pos->avl_nextino : NULL)
	29
	30	#define avl_for_each_safe(tree, pos, n) \
	31	for (pos = (tree)->avl_firstino, n = pos ? pos->avl_nextino : NULL; \
	32	pos != NULL; \
	33	pos = n, n = pos ? pos->avl_nextino : NULL)
	34
	35	#define avl_for_each(tree, pos) \
	36	for (pos = (tree)->avl_firstino; pos != NULL; pos = pos->avl_nextino)
	37
	38	struct bitmap_node {
	39	struct avl64node btn_node;
	40	uint64_t btn_start;
	41	uint64_t btn_length;
	42	};
	43
	44	static uint64_t
	45	extent_start(
	46	struct avl64node *node)
	47	{
	48	struct bitmap_node *btn;
	49
	50	btn = container_of(node, struct bitmap_node, btn_node);
	51	return btn->btn_start;
	52	}
	53
	54	static uint64_t
	55	extent_end(
	56	struct avl64node *node)
	57	{
	58	struct bitmap_node *btn;
	59
	60	btn = container_of(node, struct bitmap_node, btn_node);
	61	return btn->btn_start + btn->btn_length;
	62	}
	63
	64	static struct avl64ops bitmap_ops = {
	65	extent_start,
	66	extent_end,
	67	};
	68
	69	/* Initialize a bitmap. */
93ab49dd	70	int
233fabee	71	bitmap_alloc(
0cf6f686 DW	72	struct bitmap **bmapp)
	73	{
	74	struct bitmap *bmap;
d504cf0b	75	int ret;
0cf6f686 DW	76
	77	bmap = calloc(1, sizeof(struct bitmap));
	78	if (!bmap)
233fabee	79	return errno;
0cf6f686 DW	80	bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
0cf6f686 DW	81	if (!bmap->bt_tree) {
d504cf0b DW	82	ret = errno;
d504cf0b DW	83	goto out;
0cf6f686 DW	84	}
0cf6f686 DW	85
d504cf0b DW	86	ret = pthread_mutex_init(&bmap->bt_lock, NULL);
	87	if (ret)
	88	goto out_tree;
	89
0cf6f686 DW	90	avl64_init_tree(bmap->bt_tree, &bitmap_ops);
	91	*bmapp = bmap;
	92
93ab49dd	93	return 0;
d504cf0b DW	94	out_tree:
	95	free(bmap->bt_tree);
	96	out:
	97	free(bmap);
	98	return ret;
0cf6f686 DW	99	}
	100
	101	/* Free a bitmap. */
	102	void
	103	bitmap_free(
	104	struct bitmap **bmapp)
	105	{
	106	struct bitmap *bmap;
	107	struct avl64node *node;
	108	struct avl64node *n;
	109	struct bitmap_node *ext;
	110
	111	bmap = *bmapp;
	112	avl_for_each_safe(bmap->bt_tree, node, n) {
	113	ext = container_of(node, struct bitmap_node, btn_node);
	114	free(ext);
	115	}
	116	free(bmap->bt_tree);
b0956ceb	117	free(bmap);
0cf6f686 DW	118	*bmapp = NULL;
	119	}
	120
	121	/* Create a new bitmap extent node. */
	122	static struct bitmap_node *
	123	bitmap_node_init(
	124	uint64_t start,
	125	uint64_t len)
	126	{
	127	struct bitmap_node *ext;
	128
	129	ext = malloc(sizeof(struct bitmap_node));
	130	if (!ext)
	131	return NULL;
	132
	133	ext->btn_node.avl_nextino = NULL;
	134	ext->btn_start = start;
	135	ext->btn_length = len;
	136
	137	return ext;
	138	}
	139
93ab49dd DW	140	/* Create a new bitmap node and insert it. */
	141	static inline int
	142	__bitmap_insert(
	143	struct bitmap *bmap,
	144	uint64_t start,
	145	uint64_t length)
	146	{
	147	struct bitmap_node *ext;
	148	struct avl64node *node;
	149
	150	ext = bitmap_node_init(start, length);
	151	if (!ext)
233fabee	152	return errno;
93ab49dd DW	153
	154	node = avl64_insert(bmap->bt_tree, &ext->btn_node);
	155	if (node == NULL) {
	156	free(ext);
233fabee	157	return EEXIST;
93ab49dd DW	158	}
	159
	160	return 0;
	161	}
	162
0cf6f686	163	/* Set a region of bits (locked). */
93ab49dd	164	static int
0cf6f686 DW	165	__bitmap_set(
	166	struct bitmap *bmap,
	167	uint64_t start,
	168	uint64_t length)
	169	{
	170	struct avl64node *firstn;
	171	struct avl64node *lastn;
	172	struct avl64node *pos;
	173	struct avl64node *n;
	174	struct avl64node *l;
	175	struct bitmap_node *ext;
	176	uint64_t new_start;
	177	uint64_t new_length;
0cf6f686 DW	178
	179	/* Find any existing nodes adjacent or within that range. */
	180	avl64_findranges(bmap->bt_tree, start - 1, start + length + 1,
	181	&firstn, &lastn);
	182
	183	/* Nothing, just insert a new extent. */
93ab49dd DW	184	if (firstn == NULL && lastn == NULL)
93ab49dd DW	185	return __bitmap_insert(bmap, start, length);
0cf6f686 DW	186
	187	assert(firstn != NULL && lastn != NULL);
	188	new_start = start;
	189	new_length = length;
	190
	191	avl_for_each_range_safe(pos, n, l, firstn, lastn) {
	192	ext = container_of(pos, struct bitmap_node, btn_node);
	193
	194	/* Bail if the new extent is contained within an old one. */
	195	if (ext->btn_start <= start &&
	196	ext->btn_start + ext->btn_length >= start + length)
93ab49dd	197	return 0;
0cf6f686 DW	198
	199	/* Check for overlapping and adjacent extents. */
	200	if (ext->btn_start + ext->btn_length >= start \|\|
	201	ext->btn_start <= start + length) {
	202	if (ext->btn_start < start) {
	203	new_start = ext->btn_start;
	204	new_length += ext->btn_length;
	205	}
	206
	207	if (ext->btn_start + ext->btn_length >
	208	new_start + new_length)
	209	new_length = ext->btn_start + ext->btn_length -
	210	new_start;
	211
	212	avl64_delete(bmap->bt_tree, pos);
	213	free(ext);
	214	}
	215	}
	216
93ab49dd	217	return __bitmap_insert(bmap, new_start, new_length);
0cf6f686 DW	218	}
	219
	220	/* Set a region of bits. */
93ab49dd	221	int
0cf6f686 DW	222	bitmap_set(
	223	struct bitmap *bmap,
	224	uint64_t start,
	225	uint64_t length)
	226	{
93ab49dd	227	int res;
0cf6f686 DW	228
	229	pthread_mutex_lock(&bmap->bt_lock);
	230	res = __bitmap_set(bmap, start, length);
	231	pthread_mutex_unlock(&bmap->bt_lock);
	232
	233	return res;
	234	}
	235
	236	#if 0 /* Unused, provided for completeness. */
	237	/* Clear a region of bits. */
	238	bool
	239	bitmap_clear(
	240	struct bitmap *bmap,
	241	uint64_t start,
	242	uint64_t len)
	243	{
	244	struct avl64node *firstn;
	245	struct avl64node *lastn;
	246	struct avl64node *pos;
	247	struct avl64node *n;
	248	struct avl64node *l;
	249	struct bitmap_node *ext;
	250	uint64_t new_start;
	251	uint64_t new_length;
	252	struct avl64node *node;
	253	int stat;
	254
	255	pthread_mutex_lock(&bmap->bt_lock);
	256	/* Find any existing nodes over that range. */
	257	avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
	258
	259	/* Nothing, we're done. */
	260	if (firstn == NULL && lastn == NULL) {
	261	pthread_mutex_unlock(&bmap->bt_lock);
	262	return true;
	263	}
	264
	265	assert(firstn != NULL && lastn != NULL);
	266
	267	/* Delete or truncate everything in sight. */
	268	avl_for_each_range_safe(pos, n, l, firstn, lastn) {
	269	ext = container_of(pos, struct bitmap_node, btn_node);
	270
	271	stat = 0;
	272	if (ext->btn_start < start)
	273	stat \|= 1;
	274	if (ext->btn_start + ext->btn_length > start + len)
	275	stat \|= 2;
	276	switch (stat) {
	277	case 0:
	278	/* Extent totally within range; delete. */
	279	avl64_delete(bmap->bt_tree, pos);
	280	free(ext);
	281	break;
	282	case 1:
	283	/* Extent is left-adjacent; truncate. */
	284	ext->btn_length = start - ext->btn_start;
	285	break;
	286	case 2:
	287	/* Extent is right-adjacent; move it. */
	288	ext->btn_length = ext->btn_start + ext->btn_length -
	289	(start + len);
	290	ext->btn_start = start + len;
	291	break;
292	case 3:
293	/* Extent overlaps both ends. */
294	ext->btn_length = start - ext->btn_start;
295	new_start = start + len;
296	new_length = ext->btn_start + ext->btn_length -
297	new_start;
298
299	ext = bitmap_node_init(new_start, new_length);
300	if (!ext)
301	return false;
302
303	node = avl64_insert(bmap->bt_tree, &ext->btn_node);
304	if (node == NULL) {
305	errno = EEXIST;
306	return false;
307	}
308	break;
309	}
310	}
311
312	pthread_mutex_unlock(&bmap->bt_lock);
313	return true;
314	}
315	#endif
316
317	#ifdef DEBUG
318	/* Iterate the set regions of this bitmap. */
93ab49dd	319	int
0cf6f686 DW	320	bitmap_iterate(
0cf6f686 DW	321	struct bitmap *bmap,
93ab49dd	322	int (fn)(uint64_t, uint64_t, void ),
0cf6f686 DW	323	void *arg)
	324	{
	325	struct avl64node *node;
	326	struct bitmap_node *ext;
93ab49dd	327	int error = 0;
0cf6f686 DW	328
	329	pthread_mutex_lock(&bmap->bt_lock);
	330	avl_for_each(bmap->bt_tree, node) {
	331	ext = container_of(node, struct bitmap_node, btn_node);
93ab49dd DW	332	error = fn(ext->btn_start, ext->btn_length, arg);
93ab49dd DW	333	if (error)
0cf6f686 DW	334	break;
	335	}
	336	pthread_mutex_unlock(&bmap->bt_lock);
	337
93ab49dd	338	return error;
0cf6f686 DW	339	}
	340	#endif
	341
	342	/* Do any bitmap extents overlap the given one? (locked) */
	343	static bool
	344	__bitmap_test(
	345	struct bitmap *bmap,
	346	uint64_t start,
	347	uint64_t len)
	348	{
	349	struct avl64node *firstn;
	350	struct avl64node *lastn;
	351
	352	/* Find any existing nodes over that range. */
	353	avl64_findranges(bmap->bt_tree, start, start + len, &firstn, &lastn);
	354
	355	return firstn != NULL && lastn != NULL;
	356	}
	357
	358	/* Is any part of this range set? */
	359	bool
	360	bitmap_test(
	361	struct bitmap *bmap,
	362	uint64_t start,
	363	uint64_t len)
	364	{
	365	bool res;
	366
	367	pthread_mutex_lock(&bmap->bt_lock);
	368	res = __bitmap_test(bmap, start, len);
	369	pthread_mutex_unlock(&bmap->bt_lock);
	370
	371	return res;
	372	}
	373
	374	/* Are none of the bits set? */
	375	bool
	376	bitmap_empty(
	377	struct bitmap *bmap)
	378	{
	379	return bmap->bt_tree->avl_firstino == NULL;
	380	}
	381
	382	#ifdef DEBUG
93ab49dd	383	static int
0cf6f686 DW	384	bitmap_dump_fn(
	385	uint64_t startblock,
	386	uint64_t blockcount,
	387	void *arg)
	388	{
	389	printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount);
93ab49dd	390	return 0;
0cf6f686 DW	391	}
	392
	393	/* Dump bitmap. */
	394	void
	395	bitmap_dump(
	396	struct bitmap *bmap)
	397	{
	398	printf("BITMAP DUMP %p\n", bmap);
	399	bitmap_iterate(bmap, bitmap_dump_fn, NULL);
	400	printf("BITMAP DUMP DONE\n");
	401	}
	402	#endif