[thirdparty/xfsprogs-dev.git] / repair / incore.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 */

#include "libxfs.h"
#include "avl.h"
#include "btree.h"
#include "globals.h"
#include "incore.h"
#include "agheader.h"
#include "protos.h"
#include "err_protos.h"
#include "threads.h"

/*
 * The following manages the in-core bitmap of the entire filesystem
 * using extents in a btree.
 *
 * The btree items will point to one of the state values below,
 * rather than storing the value itself in the pointer.
 */
static int states[16] =
	{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

static struct btree_root	**ag_bmap;

static void
update_bmap(
	struct btree_root	*bmap,
	unsigned long		offset,
	xfs_extlen_t		blen,
	void			*new_state)
{
	unsigned long		end = offset + blen;
	int			*cur_state;
	unsigned long		cur_key;
	int			*next_state;
	unsigned long		next_key;
	int			*prev_state;

	cur_state = btree_find(bmap, offset, &cur_key);
	if (!cur_state)
		return;

	if (offset == cur_key) {
		/* if the start is the same as the "item" extent */
		if (cur_state == new_state)
			return;

		/*
		 * Note: this may be NULL if we are updating the map for
		 * the superblock.
		 */
		prev_state = btree_peek_prev(bmap, NULL);

		next_state = btree_peek_next(bmap, &next_key);
		if (next_key > end) {
			/* different end */
			if (new_state == prev_state) {
				/* #1: prev has same state, move offset up */
				btree_update_key(bmap, offset, end);
				return;
			}

			/* #4: insert new extent after, update current value */
			btree_update_value(bmap, offset, new_state);
			btree_insert(bmap, end, cur_state);
			return;
		}

		/* same end (and same start) */
		if (new_state == next_state) {
			/* next has same state */
			if (new_state == prev_state) {
				/* #3: merge prev & next */
				btree_delete(bmap, offset);
				btree_delete(bmap, end);
				return;
			}

			/* #8: merge next */
			btree_update_value(bmap, offset, new_state);
			btree_delete(bmap, end);
			return;
		}

		/* same start, same end, next has different state */
		if (new_state == prev_state) {
			/* #5: prev has same state */
			btree_delete(bmap, offset);
			return;
		}

		/* #6: update value only */
		btree_update_value(bmap, offset, new_state);
		return;
	}

	/* different start, offset is in the middle of "cur" */
	prev_state = btree_peek_prev(bmap, NULL);
	ASSERT(prev_state != NULL);
	if (prev_state == new_state)
		return;

	if (end == cur_key) {
		/* end is at the same point as the current extent */
		if (new_state == cur_state) {
			/* #7: move next extent down */
			btree_update_key(bmap, end, offset);
			return;
		}

		/* #9: different start, same end, add new extent */
		btree_insert(bmap, offset, new_state);
		return;
	}

	/* #2: insert an extent into the middle of another extent */
	btree_insert(bmap, offset, new_state);
	btree_insert(bmap, end, prev_state);
}

void
set_bmap_ext(
	xfs_agnumber_t		agno,
	xfs_agblock_t		agbno,
	xfs_extlen_t		blen,
	int			state)
{
	update_bmap(ag_bmap[agno], agbno, blen, &states[state]);
}

int
get_bmap_ext(
	xfs_agnumber_t		agno,
	xfs_agblock_t		agbno,
	xfs_agblock_t		maxbno,
	xfs_extlen_t		*blen)
{
	int			*statep;
	unsigned long		key;

	statep = btree_find(ag_bmap[agno], agbno, &key);
	if (!statep)
		return -1;

	if (key == agbno) {
		if (blen) {
			if (!btree_peek_next(ag_bmap[agno], &key))
				return -1;
			*blen = min(maxbno, key) - agbno;
		}
		return *statep;
	}

	statep = btree_peek_prev(ag_bmap[agno], NULL);
	if (!statep)
		return -1;
	if (blen)
		*blen = min(maxbno, key) - agbno;

	return *statep;
}

static uint64_t		*rt_bmap;
static size_t		rt_bmap_size;

/* block records fit into uint64_t's units */
#define XR_BB_UNIT	64			/* number of bits/unit */
#define XR_BB		4			/* bits per block record */
#define XR_BB_NUM	(XR_BB_UNIT/XR_BB)	/* number of records per unit */
#define XR_BB_MASK	0xF			/* block record mask */

/*
 * these work in real-time extents (e.g. fsbno == rt extent number)
 */
int
get_rtbmap(
	xfs_rtblock_t	bno)
{
	return (*(rt_bmap + bno /  XR_BB_NUM) >>
		((bno % XR_BB_NUM) * XR_BB)) & XR_BB_MASK;
}

void
set_rtbmap(
	xfs_rtblock_t	bno,
	int		state)
{
	*(rt_bmap + bno / XR_BB_NUM) =
	 ((*(rt_bmap + bno / XR_BB_NUM) &
	  (~((uint64_t) XR_BB_MASK << ((bno % XR_BB_NUM) * XR_BB)))) |
	 (((uint64_t) state) << ((bno % XR_BB_NUM) * XR_BB)));
}

static void
reset_rt_bmap(void)
{
	if (rt_bmap)
		memset(rt_bmap, 0x22, rt_bmap_size);	/* XR_E_FREE */
}

static void
init_rt_bmap(
	xfs_mount_t	*mp)
{
	if (mp->m_sb.sb_rextents == 0)
		return;

	rt_bmap_size = roundup(howmany(mp->m_sb.sb_rextents, (NBBY / XR_BB)),
			       sizeof(uint64_t));

	rt_bmap = memalign(sizeof(uint64_t), rt_bmap_size);
	if (!rt_bmap) {
		do_error(
	_("couldn't allocate realtime block map, size = %" PRIu64 "\n"),
			mp->m_sb.sb_rextents);
		return;
	}
}

static void
free_rt_bmap(xfs_mount_t *mp)
{
	free(rt_bmap);
	rt_bmap = NULL;
}


void
reset_bmaps(xfs_mount_t *mp)
{
	xfs_agnumber_t	agno;
	xfs_agblock_t	ag_size;
	int		ag_hdr_block;

	ag_hdr_block = howmany(4 * mp->m_sb.sb_sectsize, mp->m_sb.sb_blocksize);
	ag_size = mp->m_sb.sb_agblocks;

	for (agno = 0; agno < mp->m_sb.sb_agcount; agno++) {
		if (agno == mp->m_sb.sb_agcount - 1)
			ag_size = (xfs_extlen_t)(mp->m_sb.sb_dblocks -
				   (xfs_rfsblock_t)mp->m_sb.sb_agblocks * agno);
#ifdef BTREE_STATS
		if (btree_find(ag_bmap[agno], 0, NULL)) {
			printf("ag_bmap[%d] btree stats:\n", i);
			btree_print_stats(ag_bmap[agno], stdout);
		}
#endif
		/*
		 * We always insert an item for the first block having a
		 * given state.  So the code below means:
		 *
		 *	block 0..ag_hdr_block-1:	XR_E_INUSE_FS
		 *	ag_hdr_block..ag_size:		XR_E_UNKNOWN
		 *	ag_size...			XR_E_BAD_STATE
		 */
		btree_clear(ag_bmap[agno]);
		btree_insert(ag_bmap[agno], 0, &states[XR_E_INUSE_FS]);
		btree_insert(ag_bmap[agno],
				ag_hdr_block, &states[XR_E_UNKNOWN]);
		btree_insert(ag_bmap[agno], ag_size, &states[XR_E_BAD_STATE]);
	}

	if (mp->m_sb.sb_logstart != 0) {
		set_bmap_ext(XFS_FSB_TO_AGNO(mp, mp->m_sb.sb_logstart),
			     XFS_FSB_TO_AGBNO(mp, mp->m_sb.sb_logstart),
			     mp->m_sb.sb_logblocks, XR_E_INUSE_FS);
	}

	reset_rt_bmap();
}

void
init_bmaps(xfs_mount_t *mp)
{
	xfs_agnumber_t i;

	ag_bmap = calloc(mp->m_sb.sb_agcount, sizeof(struct btree_root *));
	if (!ag_bmap)
		do_error(_("couldn't allocate block map btree roots\n"));

	ag_locks = calloc(mp->m_sb.sb_agcount, sizeof(struct aglock));
	if (!ag_locks)
		do_error(_("couldn't allocate block map locks\n"));

	for (i = 0; i < mp->m_sb.sb_agcount; i++)  {
		btree_init(&ag_bmap[i]);
		pthread_mutex_init(&ag_locks[i].lock, NULL);
	}
	pthread_mutex_init(&rt_lock.lock, NULL);

	init_rt_bmap(mp);
	reset_bmaps(mp);
}

void
free_bmaps(xfs_mount_t *mp)
{
	xfs_agnumber_t i;

	for (i = 0; i < mp->m_sb.sb_agcount; i++)
		btree_destroy(ag_bmap[i]);
	free(ag_bmap);
	ag_bmap = NULL;

	free_rt_bmap(mp);
}
Commit	Line	Data
959ef981	1	// SPDX-License-Identifier: GPL-2.0
2bd0ea18	2	/*
da23017d NS	3	* Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
da23017d NS	4	* All Rights Reserved.
2bd0ea18 NS	5	*/
2bd0ea18 NS	6
6b803e5a	7	#include "libxfs.h"
2bd0ea18	8	#include "avl.h"
8961bfde	9	#include "btree.h"
2bd0ea18 NS	10	#include "globals.h"
	11	#include "incore.h"
	12	#include "agheader.h"
	13	#include "protos.h"
	14	#include "err_protos.h"
3b6ac903	15	#include "threads.h"
2bd0ea18	16
8961bfde BN	17	/*
	18	* The following manages the in-core bitmap of the entire filesystem
	19	* using extents in a btree.
	20	*
	21	* The btree items will point to one of the state values below,
	22	* rather than storing the value itself in the pointer.
	23	*/
	24	static int states[16] =
	25	{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
	26
	27	static struct btree_root **ag_bmap;
	28
	29	static void
	30	update_bmap(
	31	struct btree_root *bmap,
	32	unsigned long offset,
	33	xfs_extlen_t blen,
	34	void *new_state)
	35	{
	36	unsigned long end = offset + blen;
	37	int *cur_state;
	38	unsigned long cur_key;
	39	int *next_state;
	40	unsigned long next_key;
	41	int *prev_state;
	42
	43	cur_state = btree_find(bmap, offset, &cur_key);
	44	if (!cur_state)
	45	return;
	46
	47	if (offset == cur_key) {
	48	/* if the start is the same as the "item" extent */
	49	if (cur_state == new_state)
	50	return;
	51
	52	/*
	53	* Note: this may be NULL if we are updating the map for
	54	* the superblock.
	55	*/
	56	prev_state = btree_peek_prev(bmap, NULL);
	57
	58	next_state = btree_peek_next(bmap, &next_key);
	59	if (next_key > end) {
	60	/* different end */
	61	if (new_state == prev_state) {
	62	/* #1: prev has same state, move offset up */
	63	btree_update_key(bmap, offset, end);
	64	return;
	65	}
	66
	67	/* #4: insert new extent after, update current value */
	68	btree_update_value(bmap, offset, new_state);
	69	btree_insert(bmap, end, cur_state);
	70	return;
	71	}
	72
	73	/* same end (and same start) */
	74	if (new_state == next_state) {
	75	/* next has same state */
	76	if (new_state == prev_state) {
	77	/* #3: merge prev & next */
	78	btree_delete(bmap, offset);
	79	btree_delete(bmap, end);
	80	return;
81	}
82
83	/* #8: merge next */
84	btree_update_value(bmap, offset, new_state);
85	btree_delete(bmap, end);
86	return;
87	}
88
89	/* same start, same end, next has different state */
90	if (new_state == prev_state) {
91	/* #5: prev has same state */
92	btree_delete(bmap, offset);
93	return;
94	}
95
96	/* #6: update value only */
97	btree_update_value(bmap, offset, new_state);
98	return;
99	}
100
101	/* different start, offset is in the middle of "cur" */
102	prev_state = btree_peek_prev(bmap, NULL);
103	ASSERT(prev_state != NULL);
104	if (prev_state == new_state)
105	return;
106
107	if (end == cur_key) {
108	/* end is at the same point as the current extent */
109	if (new_state == cur_state) {
110	/* #7: move next extent down */
111	btree_update_key(bmap, end, offset);
112	return;
113	}
114
115	/* #9: different start, same end, add new extent */
116	btree_insert(bmap, offset, new_state);
117	return;
118	}
2bd0ea18	119
8961bfde BN	120	/* #2: insert an extent into the middle of another extent */
	121	btree_insert(bmap, offset, new_state);
	122	btree_insert(bmap, end, prev_state);
	123	}
	124
	125	void
	126	set_bmap_ext(
	127	xfs_agnumber_t agno,
	128	xfs_agblock_t agbno,
	129	xfs_extlen_t blen,
	130	int state)
	131	{
	132	update_bmap(ag_bmap[agno], agbno, blen, &states[state]);
	133	}
	134
	135	int
	136	get_bmap_ext(
	137	xfs_agnumber_t agno,
	138	xfs_agblock_t agbno,
	139	xfs_agblock_t maxbno,
	140	xfs_extlen_t *blen)
	141	{
	142	int *statep;
	143	unsigned long key;
	144
	145	statep = btree_find(ag_bmap[agno], agbno, &key);
	146	if (!statep)
	147	return -1;
	148
	149	if (key == agbno) {
	150	if (blen) {
	151	if (!btree_peek_next(ag_bmap[agno], &key))
	152	return -1;
68d16907	153	*blen = min(maxbno, key) - agbno;
8961bfde BN	154	}
	155	return *statep;
	156	}
	157
	158	statep = btree_peek_prev(ag_bmap[agno], NULL);
	159	if (!statep)
	160	return -1;
	161	if (blen)
68d16907	162	*blen = min(maxbno, key) - agbno;
8961bfde BN	163
	164	return *statep;
	165	}
	166
	167	static uint64_t *rt_bmap;
c1f7a46c	168	static size_t rt_bmap_size;
dfc130f3	169
14f8b681	170	/* block records fit into uint64_t's units */
8961bfde BN	171	#define XR_BB_UNIT 64 /* number of bits/unit */
	172	#define XR_BB 4 /* bits per block record */
	173	#define XR_BB_NUM (XR_BB_UNIT/XR_BB) /* number of records per unit */
	174	#define XR_BB_MASK 0xF /* block record mask */
	175
	176	/*
	177	* these work in real-time extents (e.g. fsbno == rt extent number)
	178	*/
	179	int
	180	get_rtbmap(
5a35bf2c	181	xfs_rtblock_t bno)
8961bfde BN	182	{
	183	return (*(rt_bmap + bno / XR_BB_NUM) >>
	184	((bno % XR_BB_NUM) * XR_BB)) & XR_BB_MASK;
	185	}
	186
	187	void
	188	set_rtbmap(
5a35bf2c	189	xfs_rtblock_t bno,
8961bfde BN	190	int state)
	191	{
	192	*(rt_bmap + bno / XR_BB_NUM) =
	193	((*(rt_bmap + bno / XR_BB_NUM) &
14f8b681 DW	194	(~((uint64_t) XR_BB_MASK << ((bno % XR_BB_NUM) * XR_BB)))) \|
14f8b681 DW	195	(((uint64_t) state) << ((bno % XR_BB_NUM) * XR_BB)));
8961bfde BN	196	}
8961bfde BN	197
c1f7a46c BN	198	static void
	199	reset_rt_bmap(void)
	200	{
8961bfde BN	201	if (rt_bmap)
8961bfde BN	202	memset(rt_bmap, 0x22, rt_bmap_size); /* XR_E_FREE */
c1f7a46c	203	}
2bd0ea18	204
c1f7a46c BN	205	static void
	206	init_rt_bmap(
	207	xfs_mount_t *mp)
	208	{
	209	if (mp->m_sb.sb_rextents == 0)
2bd0ea18	210	return;
2bd0ea18	211
3a7f7109	212	rt_bmap_size = roundup(howmany(mp->m_sb.sb_rextents, (NBBY / XR_BB)),
14f8b681	213	sizeof(uint64_t));
2bd0ea18	214
14f8b681	215	rt_bmap = memalign(sizeof(uint64_t), rt_bmap_size);
8961bfde	216	if (!rt_bmap) {
c1f7a46c	217	do_error(
5d1b7f0f	218	_("couldn't allocate realtime block map, size = %" PRIu64 "\n"),
c1f7a46c BN	219	mp->m_sb.sb_rextents);
c1f7a46c BN	220	return;
2bd0ea18	221	}
2bd0ea18 NS	222	}
2bd0ea18 NS	223
c1f7a46c BN	224	static void
c1f7a46c BN	225	free_rt_bmap(xfs_mount_t *mp)
2bd0ea18	226	{
8961bfde BN	227	free(rt_bmap);
8961bfde BN	228	rt_bmap = NULL;
2bd0ea18 NS	229	}
2bd0ea18 NS	230
2bd0ea18 NS	231
2bd0ea18 NS	232	void
c1f7a46c	233	reset_bmaps(xfs_mount_t *mp)
2bd0ea18	234	{
c1f7a46c	235	xfs_agnumber_t agno;
8961bfde	236	xfs_agblock_t ag_size;
c1f7a46c	237	int ag_hdr_block;
c1f7a46c BN	238
c1f7a46c BN	239	ag_hdr_block = howmany(4 * mp->m_sb.sb_sectsize, mp->m_sb.sb_blocksize);
8961bfde	240	ag_size = mp->m_sb.sb_agblocks;
c1f7a46c	241
8961bfde BN	242	for (agno = 0; agno < mp->m_sb.sb_agcount; agno++) {
	243	if (agno == mp->m_sb.sb_agcount - 1)
	244	ag_size = (xfs_extlen_t)(mp->m_sb.sb_dblocks -
5a35bf2c	245	(xfs_rfsblock_t)mp->m_sb.sb_agblocks * agno);
8961bfde BN	246	#ifdef BTREE_STATS
	247	if (btree_find(ag_bmap[agno], 0, NULL)) {
	248	printf("ag_bmap[%d] btree stats:\n", i);
	249	btree_print_stats(ag_bmap[agno], stdout);
	250	}
	251	#endif
	252	/*
	253	* We always insert an item for the first block having a
	254	* given state. So the code below means:
	255	*
	256	* block 0..ag_hdr_block-1: XR_E_INUSE_FS
	257	* ag_hdr_block..ag_size: XR_E_UNKNOWN
	258	* ag_size... XR_E_BAD_STATE
	259	*/
	260	btree_clear(ag_bmap[agno]);
	261	btree_insert(ag_bmap[agno], 0, &states[XR_E_INUSE_FS]);
	262	btree_insert(ag_bmap[agno],
	263	ag_hdr_block, &states[XR_E_UNKNOWN]);
	264	btree_insert(ag_bmap[agno], ag_size, &states[XR_E_BAD_STATE]);
2bd0ea18 NS	265	}
2bd0ea18 NS	266
c1f7a46c	267	if (mp->m_sb.sb_logstart != 0) {
8961bfde BN	268	set_bmap_ext(XFS_FSB_TO_AGNO(mp, mp->m_sb.sb_logstart),
	269	XFS_FSB_TO_AGBNO(mp, mp->m_sb.sb_logstart),
	270	mp->m_sb.sb_logblocks, XR_E_INUSE_FS);
2bd0ea18 NS	271	}
2bd0ea18 NS	272
c1f7a46c	273	reset_rt_bmap();
2bd0ea18 NS	274	}
	275
	276	void
c1f7a46c	277	init_bmaps(xfs_mount_t *mp)
2bd0ea18	278	{
8961bfde	279	xfs_agnumber_t i;
2bd0ea18	280
8961bfde BN	281	ag_bmap = calloc(mp->m_sb.sb_agcount, sizeof(struct btree_root *));
	282	if (!ag_bmap)
	283	do_error(_("couldn't allocate block map btree roots\n"));
2bd0ea18	284
586f8abf	285	ag_locks = calloc(mp->m_sb.sb_agcount, sizeof(struct aglock));
c1f7a46c BN	286	if (!ag_locks)
c1f7a46c BN	287	do_error(_("couldn't allocate block map locks\n"));
2bd0ea18	288
8961bfde BN	289	for (i = 0; i < mp->m_sb.sb_agcount; i++) {
8961bfde BN	290	btree_init(&ag_bmap[i]);
586f8abf	291	pthread_mutex_init(&ag_locks[i].lock, NULL);
2bd0ea18	292	}
86b8934d	293	pthread_mutex_init(&rt_lock.lock, NULL);
2bd0ea18	294
c1f7a46c BN	295	init_rt_bmap(mp);
c1f7a46c BN	296	reset_bmaps(mp);
2bd0ea18	297	}
2bd0ea18 NS	298
2bd0ea18 NS	299	void
c1f7a46c	300	free_bmaps(xfs_mount_t *mp)
2bd0ea18	301	{
c1f7a46c	302	xfs_agnumber_t i;
2bd0ea18	303
c1f7a46c	304	for (i = 0; i < mp->m_sb.sb_agcount; i++)
8961bfde BN	305	btree_destroy(ag_bmap[i]);
	306	free(ag_bmap);
	307	ag_bmap = NULL;
2bd0ea18	308
c1f7a46c	309	free_rt_bmap(mp);
2bd0ea18	310	}