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

/*
 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#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(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);
	}

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