xref: /linux/fs/xfs/libxfs/xfs_ialloc_btree.c (revision ca55b2fef3a9373fcfc30f82fd26bc7fccbda732) 
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 
37 STATIC int
38 xfs_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 
45 STATIC struct xfs_btree_cur *
46 xfs_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 
54 STATIC void
55 xfs_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 
68 STATIC void
69 xfs_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 
83 STATIC int
84 xfs_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 
123 STATIC int
124 xfs_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 
140 STATIC int
141 xfs_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 
148 STATIC void
149 xfs_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 
156 STATIC void
157 xfs_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 
164 STATIC void
165 xfs_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 	if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
171 		rec->inobt.ir_u.sp.ir_holemask =
172 					cpu_to_be16(cur->bc_rec.i.ir_holemask);
173 		rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count;
174 		rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount;
175 	} else {
176 		/* ir_holemask/ir_count not supported on-disk */
177 		rec->inobt.ir_u.f.ir_freecount =
178 					cpu_to_be32(cur->bc_rec.i.ir_freecount);
179 	}
180 	rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
181 }
182 
183 /*
184  * initial value of ptr for lookup
185  */
186 STATIC void
187 xfs_inobt_init_ptr_from_cur(
188 	struct xfs_btree_cur	*cur,
189 	union xfs_btree_ptr	*ptr)
190 {
191 	struct xfs_agi		*agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
192 
193 	ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
194 
195 	ptr->s = agi->agi_root;
196 }
197 
198 STATIC void
199 xfs_finobt_init_ptr_from_cur(
200 	struct xfs_btree_cur	*cur,
201 	union xfs_btree_ptr	*ptr)
202 {
203 	struct xfs_agi		*agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
204 
205 	ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
206 	ptr->s = agi->agi_free_root;
207 }
208 
209 STATIC __int64_t
210 xfs_inobt_key_diff(
211 	struct xfs_btree_cur	*cur,
212 	union xfs_btree_key	*key)
213 {
214 	return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
215 			  cur->bc_rec.i.ir_startino;
216 }
217 
218 static int
219 xfs_inobt_verify(
220 	struct xfs_buf		*bp)
221 {
222 	struct xfs_mount	*mp = bp->b_target->bt_mount;
223 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
224 	struct xfs_perag	*pag = bp->b_pag;
225 	unsigned int		level;
226 
227 	/*
228 	 * During growfs operations, we can't verify the exact owner as the
229 	 * perag is not fully initialised and hence not attached to the buffer.
230 	 *
231 	 * Similarly, during log recovery we will have a perag structure
232 	 * attached, but the agi information will not yet have been initialised
233 	 * from the on disk AGI. We don't currently use any of this information,
234 	 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
235 	 * ever do.
236 	 */
237 	switch (block->bb_magic) {
238 	case cpu_to_be32(XFS_IBT_CRC_MAGIC):
239 	case cpu_to_be32(XFS_FIBT_CRC_MAGIC):
240 		if (!xfs_sb_version_hascrc(&mp->m_sb))
241 			return false;
242 		if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
243 			return false;
244 		if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
245 			return false;
246 		if (pag &&
247 		    be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
248 			return false;
249 		/* fall through */
250 	case cpu_to_be32(XFS_IBT_MAGIC):
251 	case cpu_to_be32(XFS_FIBT_MAGIC):
252 		break;
253 	default:
254 		return 0;
255 	}
256 
257 	/* numrecs and level verification */
258 	level = be16_to_cpu(block->bb_level);
259 	if (level >= mp->m_in_maxlevels)
260 		return false;
261 	if (be16_to_cpu(block->bb_numrecs) > mp->m_inobt_mxr[level != 0])
262 		return false;
263 
264 	/* sibling pointer verification */
265 	if (!block->bb_u.s.bb_leftsib ||
266 	    (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks &&
267 	     block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK)))
268 		return false;
269 	if (!block->bb_u.s.bb_rightsib ||
270 	    (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks &&
271 	     block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK)))
272 		return false;
273 
274 	return true;
275 }
276 
277 static void
278 xfs_inobt_read_verify(
279 	struct xfs_buf	*bp)
280 {
281 	if (!xfs_btree_sblock_verify_crc(bp))
282 		xfs_buf_ioerror(bp, -EFSBADCRC);
283 	else if (!xfs_inobt_verify(bp))
284 		xfs_buf_ioerror(bp, -EFSCORRUPTED);
285 
286 	if (bp->b_error) {
287 		trace_xfs_btree_corrupt(bp, _RET_IP_);
288 		xfs_verifier_error(bp);
289 	}
290 }
291 
292 static void
293 xfs_inobt_write_verify(
294 	struct xfs_buf	*bp)
295 {
296 	if (!xfs_inobt_verify(bp)) {
297 		trace_xfs_btree_corrupt(bp, _RET_IP_);
298 		xfs_buf_ioerror(bp, -EFSCORRUPTED);
299 		xfs_verifier_error(bp);
300 		return;
301 	}
302 	xfs_btree_sblock_calc_crc(bp);
303 
304 }
305 
306 const struct xfs_buf_ops xfs_inobt_buf_ops = {
307 	.verify_read = xfs_inobt_read_verify,
308 	.verify_write = xfs_inobt_write_verify,
309 };
310 
311 #if defined(DEBUG) || defined(XFS_WARN)
312 STATIC int
313 xfs_inobt_keys_inorder(
314 	struct xfs_btree_cur	*cur,
315 	union xfs_btree_key	*k1,
316 	union xfs_btree_key	*k2)
317 {
318 	return be32_to_cpu(k1->inobt.ir_startino) <
319 		be32_to_cpu(k2->inobt.ir_startino);
320 }
321 
322 STATIC int
323 xfs_inobt_recs_inorder(
324 	struct xfs_btree_cur	*cur,
325 	union xfs_btree_rec	*r1,
326 	union xfs_btree_rec	*r2)
327 {
328 	return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
329 		be32_to_cpu(r2->inobt.ir_startino);
330 }
331 #endif	/* DEBUG */
332 
333 static const struct xfs_btree_ops xfs_inobt_ops = {
334 	.rec_len		= sizeof(xfs_inobt_rec_t),
335 	.key_len		= sizeof(xfs_inobt_key_t),
336 
337 	.dup_cursor		= xfs_inobt_dup_cursor,
338 	.set_root		= xfs_inobt_set_root,
339 	.alloc_block		= xfs_inobt_alloc_block,
340 	.free_block		= xfs_inobt_free_block,
341 	.get_minrecs		= xfs_inobt_get_minrecs,
342 	.get_maxrecs		= xfs_inobt_get_maxrecs,
343 	.init_key_from_rec	= xfs_inobt_init_key_from_rec,
344 	.init_rec_from_key	= xfs_inobt_init_rec_from_key,
345 	.init_rec_from_cur	= xfs_inobt_init_rec_from_cur,
346 	.init_ptr_from_cur	= xfs_inobt_init_ptr_from_cur,
347 	.key_diff		= xfs_inobt_key_diff,
348 	.buf_ops		= &xfs_inobt_buf_ops,
349 #if defined(DEBUG) || defined(XFS_WARN)
350 	.keys_inorder		= xfs_inobt_keys_inorder,
351 	.recs_inorder		= xfs_inobt_recs_inorder,
352 #endif
353 };
354 
355 static const struct xfs_btree_ops xfs_finobt_ops = {
356 	.rec_len		= sizeof(xfs_inobt_rec_t),
357 	.key_len		= sizeof(xfs_inobt_key_t),
358 
359 	.dup_cursor		= xfs_inobt_dup_cursor,
360 	.set_root		= xfs_finobt_set_root,
361 	.alloc_block		= xfs_inobt_alloc_block,
362 	.free_block		= xfs_inobt_free_block,
363 	.get_minrecs		= xfs_inobt_get_minrecs,
364 	.get_maxrecs		= xfs_inobt_get_maxrecs,
365 	.init_key_from_rec	= xfs_inobt_init_key_from_rec,
366 	.init_rec_from_key	= xfs_inobt_init_rec_from_key,
367 	.init_rec_from_cur	= xfs_inobt_init_rec_from_cur,
368 	.init_ptr_from_cur	= xfs_finobt_init_ptr_from_cur,
369 	.key_diff		= xfs_inobt_key_diff,
370 	.buf_ops		= &xfs_inobt_buf_ops,
371 #if defined(DEBUG) || defined(XFS_WARN)
372 	.keys_inorder		= xfs_inobt_keys_inorder,
373 	.recs_inorder		= xfs_inobt_recs_inorder,
374 #endif
375 };
376 
377 /*
378  * Allocate a new inode btree cursor.
379  */
380 struct xfs_btree_cur *				/* new inode btree cursor */
381 xfs_inobt_init_cursor(
382 	struct xfs_mount	*mp,		/* file system mount point */
383 	struct xfs_trans	*tp,		/* transaction pointer */
384 	struct xfs_buf		*agbp,		/* buffer for agi structure */
385 	xfs_agnumber_t		agno,		/* allocation group number */
386 	xfs_btnum_t		btnum)		/* ialloc or free ino btree */
387 {
388 	struct xfs_agi		*agi = XFS_BUF_TO_AGI(agbp);
389 	struct xfs_btree_cur	*cur;
390 
391 	cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
392 
393 	cur->bc_tp = tp;
394 	cur->bc_mp = mp;
395 	cur->bc_btnum = btnum;
396 	if (btnum == XFS_BTNUM_INO) {
397 		cur->bc_nlevels = be32_to_cpu(agi->agi_level);
398 		cur->bc_ops = &xfs_inobt_ops;
399 	} else {
400 		cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
401 		cur->bc_ops = &xfs_finobt_ops;
402 	}
403 
404 	cur->bc_blocklog = mp->m_sb.sb_blocklog;
405 
406 	if (xfs_sb_version_hascrc(&mp->m_sb))
407 		cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
408 
409 	cur->bc_private.a.agbp = agbp;
410 	cur->bc_private.a.agno = agno;
411 
412 	return cur;
413 }
414 
415 /*
416  * Calculate number of records in an inobt btree block.
417  */
418 int
419 xfs_inobt_maxrecs(
420 	struct xfs_mount	*mp,
421 	int			blocklen,
422 	int			leaf)
423 {
424 	blocklen -= XFS_INOBT_BLOCK_LEN(mp);
425 
426 	if (leaf)
427 		return blocklen / sizeof(xfs_inobt_rec_t);
428 	return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
429 }
430 
431 /*
432  * Convert the inode record holemask to an inode allocation bitmap. The inode
433  * allocation bitmap is inode granularity and specifies whether an inode is
434  * physically allocated on disk (not whether the inode is considered allocated
435  * or free by the fs).
436  *
437  * A bit value of 1 means the inode is allocated, a value of 0 means it is free.
438  */
439 uint64_t
440 xfs_inobt_irec_to_allocmask(
441 	struct xfs_inobt_rec_incore	*rec)
442 {
443 	uint64_t			bitmap = 0;
444 	uint64_t			inodespbit;
445 	int				nextbit;
446 	uint				allocbitmap;
447 
448 	/*
449 	 * The holemask has 16-bits for a 64 inode record. Therefore each
450 	 * holemask bit represents multiple inodes. Create a mask of bits to set
451 	 * in the allocmask for each holemask bit.
452 	 */
453 	inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1;
454 
455 	/*
456 	 * Allocated inodes are represented by 0 bits in holemask. Invert the 0
457 	 * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask
458 	 * anything beyond the 16 holemask bits since this casts to a larger
459 	 * type.
460 	 */
461 	allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1);
462 
463 	/*
464 	 * allocbitmap is the inverted holemask so every set bit represents
465 	 * allocated inodes. To expand from 16-bit holemask granularity to
466 	 * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target
467 	 * bitmap for every holemask bit.
468 	 */
469 	nextbit = xfs_next_bit(&allocbitmap, 1, 0);
470 	while (nextbit != -1) {
471 		ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY));
472 
473 		bitmap |= (inodespbit <<
474 			   (nextbit * XFS_INODES_PER_HOLEMASK_BIT));
475 
476 		nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1);
477 	}
478 
479 	return bitmap;
480 }
481 
482 #if defined(DEBUG) || defined(XFS_WARN)
483 /*
484  * Verify that an in-core inode record has a valid inode count.
485  */
486 int
487 xfs_inobt_rec_check_count(
488 	struct xfs_mount		*mp,
489 	struct xfs_inobt_rec_incore	*rec)
490 {
491 	int				inocount = 0;
492 	int				nextbit = 0;
493 	uint64_t			allocbmap;
494 	int				wordsz;
495 
496 	wordsz = sizeof(allocbmap) / sizeof(unsigned int);
497 	allocbmap = xfs_inobt_irec_to_allocmask(rec);
498 
499 	nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit);
500 	while (nextbit != -1) {
501 		inocount++;
502 		nextbit = xfs_next_bit((uint *) &allocbmap, wordsz,
503 				       nextbit + 1);
504 	}
505 
506 	if (inocount != rec->ir_count)
507 		return -EFSCORRUPTED;
508 
509 	return 0;
510 }
511 #endif	/* DEBUG */
512