[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;

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

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