1/*
2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
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.
13 *
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
17 */
18#include "xfs.h"
19#include "xfs_fs.h"
20#include "xfs_shared.h"
21#include "xfs_format.h"
22#include "xfs_log_format.h"
23#include "xfs_trans_resv.h"
24#include "xfs_bit.h"
25#include "xfs_mount.h"
26#include "xfs_inode.h"
27#include "xfs_btree.h"
28#include "xfs_ialloc.h"
29#include "xfs_ialloc_btree.h"
30#include "xfs_alloc.h"
31#include "xfs_error.h"
32#include "xfs_trace.h"
33#include "xfs_cksum.h"
34#include "xfs_trans.h"
35
36
37STATIC int
38xfs_inobt_get_minrecs(
39	struct xfs_btree_cur	*cur,
40	int			level)
41{
42	return cur->bc_mp->m_inobt_mnr[level != 0];
43}
44
45STATIC struct xfs_btree_cur *
46xfs_inobt_dup_cursor(
47	struct xfs_btree_cur	*cur)
48{
49	return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
50			cur->bc_private.a.agbp, cur->bc_private.a.agno,
51			cur->bc_btnum);
52}
53
54STATIC void
55xfs_inobt_set_root(
56	struct xfs_btree_cur	*cur,
57	union xfs_btree_ptr	*nptr,
58	int			inc)	/* level change */
59{
60	struct xfs_buf		*agbp = cur->bc_private.a.agbp;
61	struct xfs_agi		*agi = XFS_BUF_TO_AGI(agbp);
62
63	agi->agi_root = nptr->s;
64	be32_add_cpu(&agi->agi_level, inc);
65	xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
66}
67
68STATIC void
69xfs_finobt_set_root(
70	struct xfs_btree_cur	*cur,
71	union xfs_btree_ptr	*nptr,
72	int			inc)	/* level change */
73{
74	struct xfs_buf		*agbp = cur->bc_private.a.agbp;
75	struct xfs_agi		*agi = XFS_BUF_TO_AGI(agbp);
76
77	agi->agi_free_root = nptr->s;
78	be32_add_cpu(&agi->agi_free_level, inc);
79	xfs_ialloc_log_agi(cur->bc_tp, agbp,
80			   XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL);
81}
82
83STATIC int
84xfs_inobt_alloc_block(
85	struct xfs_btree_cur	*cur,
86	union xfs_btree_ptr	*start,
87	union xfs_btree_ptr	*new,
88	int			*stat)
89{
90	xfs_alloc_arg_t		args;		/* block allocation args */
91	int			error;		/* error return value */
92	xfs_agblock_t		sbno = be32_to_cpu(start->s);
93
94	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
95
96	memset(&args, 0, sizeof(args));
97	args.tp = cur->bc_tp;
98	args.mp = cur->bc_mp;
99	args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
100	args.minlen = 1;
101	args.maxlen = 1;
102	args.prod = 1;
103	args.type = XFS_ALLOCTYPE_NEAR_BNO;
104
105	error = xfs_alloc_vextent(&args);
106	if (error) {
107		XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
108		return error;
109	}
110	if (args.fsbno == NULLFSBLOCK) {
111		XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
112		*stat = 0;
113		return 0;
114	}
115	ASSERT(args.len == 1);
116	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
117
118	new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
119	*stat = 1;
120	return 0;
121}
122
123STATIC int
124xfs_inobt_free_block(
125	struct xfs_btree_cur	*cur,
126	struct xfs_buf		*bp)
127{
128	xfs_fsblock_t		fsbno;
129	int			error;
130
131	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp));
132	error = xfs_free_extent(cur->bc_tp, fsbno, 1);
133	if (error)
134		return error;
135
136	xfs_trans_binval(cur->bc_tp, bp);
137	return error;
138}
139
140STATIC int
141xfs_inobt_get_maxrecs(
142	struct xfs_btree_cur	*cur,
143	int			level)
144{
145	return cur->bc_mp->m_inobt_mxr[level != 0];
146}
147
148STATIC void
149xfs_inobt_init_key_from_rec(
150	union xfs_btree_key	*key,
151	union xfs_btree_rec	*rec)
152{
153	key->inobt.ir_startino = rec->inobt.ir_startino;
154}
155
156STATIC void
157xfs_inobt_init_rec_from_key(
158	union xfs_btree_key	*key,
159	union xfs_btree_rec	*rec)
160{
161	rec->inobt.ir_startino = key->inobt.ir_startino;
162}
163
164STATIC void
165xfs_inobt_init_rec_from_cur(
166	struct xfs_btree_cur	*cur,
167	union xfs_btree_rec	*rec)
168{
169	rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
170	rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
171	rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
172}
173
174/*
175 * initial value of ptr for lookup
176 */
177STATIC void
178xfs_inobt_init_ptr_from_cur(
179	struct xfs_btree_cur	*cur,
180	union xfs_btree_ptr	*ptr)
181{
182	struct xfs_agi		*agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
183
184	ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
185
186	ptr->s = agi->agi_root;
187}
188
189STATIC void
190xfs_finobt_init_ptr_from_cur(
191	struct xfs_btree_cur	*cur,
192	union xfs_btree_ptr	*ptr)
193{
194	struct xfs_agi		*agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
195
196	ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
197	ptr->s = agi->agi_free_root;
198}
199
200STATIC __int64_t
201xfs_inobt_key_diff(
202	struct xfs_btree_cur	*cur,
203	union xfs_btree_key	*key)
204{
205	return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
206			  cur->bc_rec.i.ir_startino;
207}
208
209static int
210xfs_inobt_verify(
211	struct xfs_buf		*bp)
212{
213	struct xfs_mount	*mp = bp->b_target->bt_mount;
214	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
215	struct xfs_perag	*pag = bp->b_pag;
216	unsigned int		level;
217
218	/*
219	 * During growfs operations, we can't verify the exact owner as the
220	 * perag is not fully initialised and hence not attached to the buffer.
221	 *
222	 * Similarly, during log recovery we will have a perag structure
223	 * attached, but the agi information will not yet have been initialised
224	 * from the on disk AGI. We don't currently use any of this information,
225	 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
226	 * ever do.
227	 */
228	switch (block->bb_magic) {
229	case cpu_to_be32(XFS_IBT_CRC_MAGIC):
230	case cpu_to_be32(XFS_FIBT_CRC_MAGIC):
231		if (!xfs_sb_version_hascrc(&mp->m_sb))
232			return false;
233		if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid))
234			return false;
235		if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
236			return false;
237		if (pag &&
238		    be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
239			return false;
240		/* fall through */
241	case cpu_to_be32(XFS_IBT_MAGIC):
242	case cpu_to_be32(XFS_FIBT_MAGIC):
243		break;
244	default:
245		return 0;
246	}
247
248	/* numrecs and level verification */
249	level = be16_to_cpu(block->bb_level);
250	if (level >= mp->m_in_maxlevels)
251		return false;
252	if (be16_to_cpu(block->bb_numrecs) > mp->m_inobt_mxr[level != 0])
253		return false;
254
255	/* sibling pointer verification */
256	if (!block->bb_u.s.bb_leftsib ||
257	    (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks &&
258	     block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK)))
259		return false;
260	if (!block->bb_u.s.bb_rightsib ||
261	    (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks &&
262	     block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK)))
263		return false;
264
265	return true;
266}
267
268static void
269xfs_inobt_read_verify(
270	struct xfs_buf	*bp)
271{
272	if (!xfs_btree_sblock_verify_crc(bp))
273		xfs_buf_ioerror(bp, -EFSBADCRC);
274	else if (!xfs_inobt_verify(bp))
275		xfs_buf_ioerror(bp, -EFSCORRUPTED);
276
277	if (bp->b_error) {
278		trace_xfs_btree_corrupt(bp, _RET_IP_);
279		xfs_verifier_error(bp);
280	}
281}
282
283static void
284xfs_inobt_write_verify(
285	struct xfs_buf	*bp)
286{
287	if (!xfs_inobt_verify(bp)) {
288		trace_xfs_btree_corrupt(bp, _RET_IP_);
289		xfs_buf_ioerror(bp, -EFSCORRUPTED);
290		xfs_verifier_error(bp);
291		return;
292	}
293	xfs_btree_sblock_calc_crc(bp);
294
295}
296
297const struct xfs_buf_ops xfs_inobt_buf_ops = {
298	.verify_read = xfs_inobt_read_verify,
299	.verify_write = xfs_inobt_write_verify,
300};
301
302#if defined(DEBUG) || defined(XFS_WARN)
303STATIC int
304xfs_inobt_keys_inorder(
305	struct xfs_btree_cur	*cur,
306	union xfs_btree_key	*k1,
307	union xfs_btree_key	*k2)
308{
309	return be32_to_cpu(k1->inobt.ir_startino) <
310		be32_to_cpu(k2->inobt.ir_startino);
311}
312
313STATIC int
314xfs_inobt_recs_inorder(
315	struct xfs_btree_cur	*cur,
316	union xfs_btree_rec	*r1,
317	union xfs_btree_rec	*r2)
318{
319	return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
320		be32_to_cpu(r2->inobt.ir_startino);
321}
322#endif	/* DEBUG */
323
324static const struct xfs_btree_ops xfs_inobt_ops = {
325	.rec_len		= sizeof(xfs_inobt_rec_t),
326	.key_len		= sizeof(xfs_inobt_key_t),
327
328	.dup_cursor		= xfs_inobt_dup_cursor,
329	.set_root		= xfs_inobt_set_root,
330	.alloc_block		= xfs_inobt_alloc_block,
331	.free_block		= xfs_inobt_free_block,
332	.get_minrecs		= xfs_inobt_get_minrecs,
333	.get_maxrecs		= xfs_inobt_get_maxrecs,
334	.init_key_from_rec	= xfs_inobt_init_key_from_rec,
335	.init_rec_from_key	= xfs_inobt_init_rec_from_key,
336	.init_rec_from_cur	= xfs_inobt_init_rec_from_cur,
337	.init_ptr_from_cur	= xfs_inobt_init_ptr_from_cur,
338	.key_diff		= xfs_inobt_key_diff,
339	.buf_ops		= &xfs_inobt_buf_ops,
340#if defined(DEBUG) || defined(XFS_WARN)
341	.keys_inorder		= xfs_inobt_keys_inorder,
342	.recs_inorder		= xfs_inobt_recs_inorder,
343#endif
344};
345
346static const struct xfs_btree_ops xfs_finobt_ops = {
347	.rec_len		= sizeof(xfs_inobt_rec_t),
348	.key_len		= sizeof(xfs_inobt_key_t),
349
350	.dup_cursor		= xfs_inobt_dup_cursor,
351	.set_root		= xfs_finobt_set_root,
352	.alloc_block		= xfs_inobt_alloc_block,
353	.free_block		= xfs_inobt_free_block,
354	.get_minrecs		= xfs_inobt_get_minrecs,
355	.get_maxrecs		= xfs_inobt_get_maxrecs,
356	.init_key_from_rec	= xfs_inobt_init_key_from_rec,
357	.init_rec_from_key	= xfs_inobt_init_rec_from_key,
358	.init_rec_from_cur	= xfs_inobt_init_rec_from_cur,
359	.init_ptr_from_cur	= xfs_finobt_init_ptr_from_cur,
360	.key_diff		= xfs_inobt_key_diff,
361	.buf_ops		= &xfs_inobt_buf_ops,
362#if defined(DEBUG) || defined(XFS_WARN)
363	.keys_inorder		= xfs_inobt_keys_inorder,
364	.recs_inorder		= xfs_inobt_recs_inorder,
365#endif
366};
367
368/*
369 * Allocate a new inode btree cursor.
370 */
371struct xfs_btree_cur *				/* new inode btree cursor */
372xfs_inobt_init_cursor(
373	struct xfs_mount	*mp,		/* file system mount point */
374	struct xfs_trans	*tp,		/* transaction pointer */
375	struct xfs_buf		*agbp,		/* buffer for agi structure */
376	xfs_agnumber_t		agno,		/* allocation group number */
377	xfs_btnum_t		btnum)		/* ialloc or free ino btree */
378{
379	struct xfs_agi		*agi = XFS_BUF_TO_AGI(agbp);
380	struct xfs_btree_cur	*cur;
381
382	cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
383
384	cur->bc_tp = tp;
385	cur->bc_mp = mp;
386	cur->bc_btnum = btnum;
387	if (btnum == XFS_BTNUM_INO) {
388		cur->bc_nlevels = be32_to_cpu(agi->agi_level);
389		cur->bc_ops = &xfs_inobt_ops;
390	} else {
391		cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
392		cur->bc_ops = &xfs_finobt_ops;
393	}
394
395	cur->bc_blocklog = mp->m_sb.sb_blocklog;
396
397	if (xfs_sb_version_hascrc(&mp->m_sb))
398		cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
399
400	cur->bc_private.a.agbp = agbp;
401	cur->bc_private.a.agno = agno;
402
403	return cur;
404}
405
406/*
407 * Calculate number of records in an inobt btree block.
408 */
409int
410xfs_inobt_maxrecs(
411	struct xfs_mount	*mp,
412	int			blocklen,
413	int			leaf)
414{
415	blocklen -= XFS_INOBT_BLOCK_LEN(mp);
416
417	if (leaf)
418		return blocklen / sizeof(xfs_inobt_rec_t);
419	return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
420}
421