[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_init(
	struct bitmap		**bmapp)
{
	struct bitmap		*bmap;

	bmap = calloc(1, sizeof(struct bitmap));
	if (!bmap)
		return -ENOMEM;
	bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
	if (!bmap->bt_tree) {
		free(bmap);
		return -ENOMEM;
	}

	pthread_mutex_init(&bmap->bt_lock, NULL);
	avl64_init_tree(bmap->bt_tree, &bitmap_ops);
	*bmapp = bmap;

	return 0;
}

/* 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 -ENOMEM;

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