[thirdparty/xfsprogs-dev.git] / scrub / 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. */
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
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. */
	69	bool
	70	bitmap_init(
	71	struct bitmap **bmapp)
	72	{
	73	struct bitmap *bmap;
74
75	bmap = calloc(1, sizeof(struct bitmap));
76	if (!bmap)
77	return false;
78	bmap->bt_tree = malloc(sizeof(struct avl64tree_desc));
79	if (!bmap->bt_tree) {
80	free(bmap);
81	return false;
82	}
83
84	pthread_mutex_init(&bmap->bt_lock, NULL);
85	avl64_init_tree(bmap->bt_tree, &bitmap_ops);
86	*bmapp = bmap;
87
88	return true;
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);
107	*bmapp = NULL;
108	}
109
110	/* Create a new bitmap extent node. */
111	static struct bitmap_node *
112	bitmap_node_init(
113	uint64_t start,
114	uint64_t len)
115	{
116	struct bitmap_node *ext;
117
118	ext = malloc(sizeof(struct bitmap_node));
119	if (!ext)
120	return NULL;
121
122	ext->btn_node.avl_nextino = NULL;
123	ext->btn_start = start;
124	ext->btn_length = len;
125
126	return ext;
127	}
128
129	/* Set a region of bits (locked). */
130	static bool
131	__bitmap_set(
132	struct bitmap *bmap,
133	uint64_t start,
134	uint64_t length)
135	{
136	struct avl64node *firstn;
137	struct avl64node *lastn;
138	struct avl64node *pos;
139	struct avl64node *n;
140	struct avl64node *l;
141	struct bitmap_node *ext;
142	uint64_t new_start;
143	uint64_t new_length;
144	struct avl64node *node;
145	bool res = true;
146
147	/* Find any existing nodes adjacent or within that range. */
148	avl64_findranges(bmap->bt_tree, start - 1, start + length + 1,
149	&firstn, &lastn);
150
151	/* Nothing, just insert a new extent. */
152	if (firstn == NULL && lastn == NULL) {
153	ext = bitmap_node_init(start, length);
154	if (!ext)
155	return false;
156
157	node = avl64_insert(bmap->bt_tree, &ext->btn_node);
158	if (node == NULL) {
159	free(ext);
160	errno = EEXIST;
161	return false;
162	}
163
164	return true;
165	}
166
167	assert(firstn != NULL && lastn != NULL);
168	new_start = start;
169	new_length = length;
170
171	avl_for_each_range_safe(pos, n, l, firstn, lastn) {
172	ext = container_of(pos, struct bitmap_node, btn_node);
173
174	/* Bail if the new extent is contained within an old one. */
175	if (ext->btn_start <= start &&
176	ext->btn_start + ext->btn_length >= start + length)
177	return res;
178
179	/* Check for overlapping and adjacent extents. */
180	if (ext->btn_start + ext->btn_length >= start \|\|
181	ext->btn_start <= start + length) {
182	if (ext->btn_start < start) {
183	new_start = ext->btn_start;
184	new_length += ext->btn_length;
185	}
186
187	if (ext->btn_start + ext->btn_length >
188	new_start + new_length)
189	new_length = ext->btn_start + ext->btn_length -
190	new_start;
191
192	avl64_delete(bmap->bt_tree, pos);
193	free(ext);
194	}
195	}
196
197	ext = bitmap_node_init(new_start, new_length);
198	if (!ext)
199	return false;
200
201	node = avl64_insert(bmap->bt_tree, &ext->btn_node);
202	if (node == NULL) {
203	free(ext);
204	errno = EEXIST;
205	return false;
206	}
207
208	return res;
209	}
210
211	/* Set a region of bits. */
212	bool
213	bitmap_set(
214	struct bitmap *bmap,
215	uint64_t start,
216	uint64_t length)
217	{
218	bool res;
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. */
310	bool
311	bitmap_iterate(
312	struct bitmap *bmap,
313	bool (fn)(uint64_t, uint64_t, void ),
314	void *arg)
315	{
316	struct avl64node *node;
317	struct bitmap_node *ext;
318	bool moveon = true;
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);
323	moveon = fn(ext->btn_start, ext->btn_length, arg);
324	if (!moveon)
325	break;
326	}
327	pthread_mutex_unlock(&bmap->bt_lock);
328
329	return moveon;
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
374	static bool
375	bitmap_dump_fn(
376	uint64_t startblock,
377	uint64_t blockcount,
378	void *arg)
379	{
380	printf("%"PRIu64":%"PRIu64"\n", startblock, blockcount);
381	return true;
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