xref: /linux/fs/xfs/libxfs/xfs_ialloc.c (revision ff30564411ffdcee49d579cb15eb13185a36e253)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
4  * All Rights Reserved.
5  */
6 #include "xfs.h"
7 #include "xfs_fs.h"
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
12 #include "xfs_bit.h"
13 #include "xfs_mount.h"
14 #include "xfs_inode.h"
15 #include "xfs_btree.h"
16 #include "xfs_ialloc.h"
17 #include "xfs_ialloc_btree.h"
18 #include "xfs_alloc.h"
19 #include "xfs_errortag.h"
20 #include "xfs_error.h"
21 #include "xfs_bmap.h"
22 #include "xfs_trans.h"
23 #include "xfs_buf_item.h"
24 #include "xfs_icreate_item.h"
25 #include "xfs_icache.h"
26 #include "xfs_trace.h"
27 #include "xfs_log.h"
28 #include "xfs_rmap.h"
29 #include "xfs_ag.h"
30 #include "xfs_health.h"
31 
32 /*
33  * Lookup a record by ino in the btree given by cur.
34  */
35 int					/* error */
36 xfs_inobt_lookup(
37 	struct xfs_btree_cur	*cur,	/* btree cursor */
38 	xfs_agino_t		ino,	/* starting inode of chunk */
39 	xfs_lookup_t		dir,	/* <=, >=, == */
40 	int			*stat)	/* success/failure */
41 {
42 	cur->bc_rec.i.ir_startino = ino;
43 	cur->bc_rec.i.ir_holemask = 0;
44 	cur->bc_rec.i.ir_count = 0;
45 	cur->bc_rec.i.ir_freecount = 0;
46 	cur->bc_rec.i.ir_free = 0;
47 	return xfs_btree_lookup(cur, dir, stat);
48 }
49 
50 /*
51  * Update the record referred to by cur to the value given.
52  * This either works (return 0) or gets an EFSCORRUPTED error.
53  */
54 STATIC int				/* error */
55 xfs_inobt_update(
56 	struct xfs_btree_cur	*cur,	/* btree cursor */
57 	xfs_inobt_rec_incore_t	*irec)	/* btree record */
58 {
59 	union xfs_btree_rec	rec;
60 
61 	rec.inobt.ir_startino = cpu_to_be32(irec->ir_startino);
62 	if (xfs_has_sparseinodes(cur->bc_mp)) {
63 		rec.inobt.ir_u.sp.ir_holemask = cpu_to_be16(irec->ir_holemask);
64 		rec.inobt.ir_u.sp.ir_count = irec->ir_count;
65 		rec.inobt.ir_u.sp.ir_freecount = irec->ir_freecount;
66 	} else {
67 		/* ir_holemask/ir_count not supported on-disk */
68 		rec.inobt.ir_u.f.ir_freecount = cpu_to_be32(irec->ir_freecount);
69 	}
70 	rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
71 	return xfs_btree_update(cur, &rec);
72 }
73 
74 /* Convert on-disk btree record to incore inobt record. */
75 void
76 xfs_inobt_btrec_to_irec(
77 	struct xfs_mount		*mp,
78 	const union xfs_btree_rec	*rec,
79 	struct xfs_inobt_rec_incore	*irec)
80 {
81 	irec->ir_startino = be32_to_cpu(rec->inobt.ir_startino);
82 	if (xfs_has_sparseinodes(mp)) {
83 		irec->ir_holemask = be16_to_cpu(rec->inobt.ir_u.sp.ir_holemask);
84 		irec->ir_count = rec->inobt.ir_u.sp.ir_count;
85 		irec->ir_freecount = rec->inobt.ir_u.sp.ir_freecount;
86 	} else {
87 		/*
88 		 * ir_holemask/ir_count not supported on-disk. Fill in hardcoded
89 		 * values for full inode chunks.
90 		 */
91 		irec->ir_holemask = XFS_INOBT_HOLEMASK_FULL;
92 		irec->ir_count = XFS_INODES_PER_CHUNK;
93 		irec->ir_freecount =
94 				be32_to_cpu(rec->inobt.ir_u.f.ir_freecount);
95 	}
96 	irec->ir_free = be64_to_cpu(rec->inobt.ir_free);
97 }
98 
99 /* Compute the freecount of an incore inode record. */
100 uint8_t
101 xfs_inobt_rec_freecount(
102 	const struct xfs_inobt_rec_incore	*irec)
103 {
104 	uint64_t				realfree = irec->ir_free;
105 
106 	if (xfs_inobt_issparse(irec->ir_holemask))
107 		realfree &= xfs_inobt_irec_to_allocmask(irec);
108 	return hweight64(realfree);
109 }
110 
111 /* Simple checks for inode records. */
112 xfs_failaddr_t
113 xfs_inobt_check_irec(
114 	struct xfs_perag			*pag,
115 	const struct xfs_inobt_rec_incore	*irec)
116 {
117 	/* Record has to be properly aligned within the AG. */
118 	if (!xfs_verify_agino(pag, irec->ir_startino))
119 		return __this_address;
120 	if (!xfs_verify_agino(pag,
121 				irec->ir_startino + XFS_INODES_PER_CHUNK - 1))
122 		return __this_address;
123 	if (irec->ir_count < XFS_INODES_PER_HOLEMASK_BIT ||
124 	    irec->ir_count > XFS_INODES_PER_CHUNK)
125 		return __this_address;
126 	if (irec->ir_freecount > XFS_INODES_PER_CHUNK)
127 		return __this_address;
128 
129 	if (xfs_inobt_rec_freecount(irec) != irec->ir_freecount)
130 		return __this_address;
131 
132 	return NULL;
133 }
134 
135 static inline int
136 xfs_inobt_complain_bad_rec(
137 	struct xfs_btree_cur		*cur,
138 	xfs_failaddr_t			fa,
139 	const struct xfs_inobt_rec_incore *irec)
140 {
141 	struct xfs_mount		*mp = cur->bc_mp;
142 
143 	xfs_warn(mp,
144 		"%sbt record corruption in AG %d detected at %pS!",
145 		cur->bc_ops->name, cur->bc_ag.pag->pag_agno, fa);
146 	xfs_warn(mp,
147 "start inode 0x%x, count 0x%x, free 0x%x freemask 0x%llx, holemask 0x%x",
148 		irec->ir_startino, irec->ir_count, irec->ir_freecount,
149 		irec->ir_free, irec->ir_holemask);
150 	xfs_btree_mark_sick(cur);
151 	return -EFSCORRUPTED;
152 }
153 
154 /*
155  * Get the data from the pointed-to record.
156  */
157 int
158 xfs_inobt_get_rec(
159 	struct xfs_btree_cur		*cur,
160 	struct xfs_inobt_rec_incore	*irec,
161 	int				*stat)
162 {
163 	struct xfs_mount		*mp = cur->bc_mp;
164 	union xfs_btree_rec		*rec;
165 	xfs_failaddr_t			fa;
166 	int				error;
167 
168 	error = xfs_btree_get_rec(cur, &rec, stat);
169 	if (error || *stat == 0)
170 		return error;
171 
172 	xfs_inobt_btrec_to_irec(mp, rec, irec);
173 	fa = xfs_inobt_check_irec(cur->bc_ag.pag, irec);
174 	if (fa)
175 		return xfs_inobt_complain_bad_rec(cur, fa, irec);
176 
177 	return 0;
178 }
179 
180 /*
181  * Insert a single inobt record. Cursor must already point to desired location.
182  */
183 int
184 xfs_inobt_insert_rec(
185 	struct xfs_btree_cur	*cur,
186 	uint16_t		holemask,
187 	uint8_t			count,
188 	int32_t			freecount,
189 	xfs_inofree_t		free,
190 	int			*stat)
191 {
192 	cur->bc_rec.i.ir_holemask = holemask;
193 	cur->bc_rec.i.ir_count = count;
194 	cur->bc_rec.i.ir_freecount = freecount;
195 	cur->bc_rec.i.ir_free = free;
196 	return xfs_btree_insert(cur, stat);
197 }
198 
199 /*
200  * Insert records describing a newly allocated inode chunk into the inobt.
201  */
202 STATIC int
203 xfs_inobt_insert(
204 	struct xfs_perag	*pag,
205 	struct xfs_trans	*tp,
206 	struct xfs_buf		*agbp,
207 	xfs_agino_t		newino,
208 	xfs_agino_t		newlen,
209 	bool			is_finobt)
210 {
211 	struct xfs_btree_cur	*cur;
212 	xfs_agino_t		thisino;
213 	int			i;
214 	int			error;
215 
216 	if (is_finobt)
217 		cur = xfs_finobt_init_cursor(pag, tp, agbp);
218 	else
219 		cur = xfs_inobt_init_cursor(pag, tp, agbp);
220 
221 	for (thisino = newino;
222 	     thisino < newino + newlen;
223 	     thisino += XFS_INODES_PER_CHUNK) {
224 		error = xfs_inobt_lookup(cur, thisino, XFS_LOOKUP_EQ, &i);
225 		if (error) {
226 			xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
227 			return error;
228 		}
229 		ASSERT(i == 0);
230 
231 		error = xfs_inobt_insert_rec(cur, XFS_INOBT_HOLEMASK_FULL,
232 					     XFS_INODES_PER_CHUNK,
233 					     XFS_INODES_PER_CHUNK,
234 					     XFS_INOBT_ALL_FREE, &i);
235 		if (error) {
236 			xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
237 			return error;
238 		}
239 		ASSERT(i == 1);
240 	}
241 
242 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
243 
244 	return 0;
245 }
246 
247 /*
248  * Verify that the number of free inodes in the AGI is correct.
249  */
250 #ifdef DEBUG
251 static int
252 xfs_check_agi_freecount(
253 	struct xfs_btree_cur	*cur)
254 {
255 	if (cur->bc_nlevels == 1) {
256 		xfs_inobt_rec_incore_t rec;
257 		int		freecount = 0;
258 		int		error;
259 		int		i;
260 
261 		error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
262 		if (error)
263 			return error;
264 
265 		do {
266 			error = xfs_inobt_get_rec(cur, &rec, &i);
267 			if (error)
268 				return error;
269 
270 			if (i) {
271 				freecount += rec.ir_freecount;
272 				error = xfs_btree_increment(cur, 0, &i);
273 				if (error)
274 					return error;
275 			}
276 		} while (i == 1);
277 
278 		if (!xfs_is_shutdown(cur->bc_mp))
279 			ASSERT(freecount == cur->bc_ag.pag->pagi_freecount);
280 	}
281 	return 0;
282 }
283 #else
284 #define xfs_check_agi_freecount(cur)	0
285 #endif
286 
287 /*
288  * Initialise a new set of inodes. When called without a transaction context
289  * (e.g. from recovery) we initiate a delayed write of the inode buffers rather
290  * than logging them (which in a transaction context puts them into the AIL
291  * for writeback rather than the xfsbufd queue).
292  */
293 int
294 xfs_ialloc_inode_init(
295 	struct xfs_mount	*mp,
296 	struct xfs_trans	*tp,
297 	struct list_head	*buffer_list,
298 	int			icount,
299 	xfs_agnumber_t		agno,
300 	xfs_agblock_t		agbno,
301 	xfs_agblock_t		length,
302 	unsigned int		gen)
303 {
304 	struct xfs_buf		*fbuf;
305 	struct xfs_dinode	*free;
306 	int			nbufs;
307 	int			version;
308 	int			i, j;
309 	xfs_daddr_t		d;
310 	xfs_ino_t		ino = 0;
311 	int			error;
312 
313 	/*
314 	 * Loop over the new block(s), filling in the inodes.  For small block
315 	 * sizes, manipulate the inodes in buffers  which are multiples of the
316 	 * blocks size.
317 	 */
318 	nbufs = length / M_IGEO(mp)->blocks_per_cluster;
319 
320 	/*
321 	 * Figure out what version number to use in the inodes we create.  If
322 	 * the superblock version has caught up to the one that supports the new
323 	 * inode format, then use the new inode version.  Otherwise use the old
324 	 * version so that old kernels will continue to be able to use the file
325 	 * system.
326 	 *
327 	 * For v3 inodes, we also need to write the inode number into the inode,
328 	 * so calculate the first inode number of the chunk here as
329 	 * XFS_AGB_TO_AGINO() only works within a filesystem block, not
330 	 * across multiple filesystem blocks (such as a cluster) and so cannot
331 	 * be used in the cluster buffer loop below.
332 	 *
333 	 * Further, because we are writing the inode directly into the buffer
334 	 * and calculating a CRC on the entire inode, we have ot log the entire
335 	 * inode so that the entire range the CRC covers is present in the log.
336 	 * That means for v3 inode we log the entire buffer rather than just the
337 	 * inode cores.
338 	 */
339 	if (xfs_has_v3inodes(mp)) {
340 		version = 3;
341 		ino = XFS_AGINO_TO_INO(mp, agno, XFS_AGB_TO_AGINO(mp, agbno));
342 
343 		/*
344 		 * log the initialisation that is about to take place as an
345 		 * logical operation. This means the transaction does not
346 		 * need to log the physical changes to the inode buffers as log
347 		 * recovery will know what initialisation is actually needed.
348 		 * Hence we only need to log the buffers as "ordered" buffers so
349 		 * they track in the AIL as if they were physically logged.
350 		 */
351 		if (tp)
352 			xfs_icreate_log(tp, agno, agbno, icount,
353 					mp->m_sb.sb_inodesize, length, gen);
354 	} else
355 		version = 2;
356 
357 	for (j = 0; j < nbufs; j++) {
358 		/*
359 		 * Get the block.
360 		 */
361 		d = XFS_AGB_TO_DADDR(mp, agno, agbno +
362 				(j * M_IGEO(mp)->blocks_per_cluster));
363 		error = xfs_trans_get_buf(tp, mp->m_ddev_targp, d,
364 				mp->m_bsize * M_IGEO(mp)->blocks_per_cluster,
365 				XBF_UNMAPPED, &fbuf);
366 		if (error)
367 			return error;
368 
369 		/* Initialize the inode buffers and log them appropriately. */
370 		fbuf->b_ops = &xfs_inode_buf_ops;
371 		xfs_buf_zero(fbuf, 0, BBTOB(fbuf->b_length));
372 		for (i = 0; i < M_IGEO(mp)->inodes_per_cluster; i++) {
373 			int	ioffset = i << mp->m_sb.sb_inodelog;
374 
375 			free = xfs_make_iptr(mp, fbuf, i);
376 			free->di_magic = cpu_to_be16(XFS_DINODE_MAGIC);
377 			free->di_version = version;
378 			free->di_gen = cpu_to_be32(gen);
379 			free->di_next_unlinked = cpu_to_be32(NULLAGINO);
380 
381 			if (version == 3) {
382 				free->di_ino = cpu_to_be64(ino);
383 				ino++;
384 				uuid_copy(&free->di_uuid,
385 					  &mp->m_sb.sb_meta_uuid);
386 				xfs_dinode_calc_crc(mp, free);
387 			} else if (tp) {
388 				/* just log the inode core */
389 				xfs_trans_log_buf(tp, fbuf, ioffset,
390 					  ioffset + XFS_DINODE_SIZE(mp) - 1);
391 			}
392 		}
393 
394 		if (tp) {
395 			/*
396 			 * Mark the buffer as an inode allocation buffer so it
397 			 * sticks in AIL at the point of this allocation
398 			 * transaction. This ensures the they are on disk before
399 			 * the tail of the log can be moved past this
400 			 * transaction (i.e. by preventing relogging from moving
401 			 * it forward in the log).
402 			 */
403 			xfs_trans_inode_alloc_buf(tp, fbuf);
404 			if (version == 3) {
405 				/*
406 				 * Mark the buffer as ordered so that they are
407 				 * not physically logged in the transaction but
408 				 * still tracked in the AIL as part of the
409 				 * transaction and pin the log appropriately.
410 				 */
411 				xfs_trans_ordered_buf(tp, fbuf);
412 			}
413 		} else {
414 			fbuf->b_flags |= XBF_DONE;
415 			xfs_buf_delwri_queue(fbuf, buffer_list);
416 			xfs_buf_relse(fbuf);
417 		}
418 	}
419 	return 0;
420 }
421 
422 /*
423  * Align startino and allocmask for a recently allocated sparse chunk such that
424  * they are fit for insertion (or merge) into the on-disk inode btrees.
425  *
426  * Background:
427  *
428  * When enabled, sparse inode support increases the inode alignment from cluster
429  * size to inode chunk size. This means that the minimum range between two
430  * non-adjacent inode records in the inobt is large enough for a full inode
431  * record. This allows for cluster sized, cluster aligned block allocation
432  * without need to worry about whether the resulting inode record overlaps with
433  * another record in the tree. Without this basic rule, we would have to deal
434  * with the consequences of overlap by potentially undoing recent allocations in
435  * the inode allocation codepath.
436  *
437  * Because of this alignment rule (which is enforced on mount), there are two
438  * inobt possibilities for newly allocated sparse chunks. One is that the
439  * aligned inode record for the chunk covers a range of inodes not already
440  * covered in the inobt (i.e., it is safe to insert a new sparse record). The
441  * other is that a record already exists at the aligned startino that considers
442  * the newly allocated range as sparse. In the latter case, record content is
443  * merged in hope that sparse inode chunks fill to full chunks over time.
444  */
445 STATIC void
446 xfs_align_sparse_ino(
447 	struct xfs_mount		*mp,
448 	xfs_agino_t			*startino,
449 	uint16_t			*allocmask)
450 {
451 	xfs_agblock_t			agbno;
452 	xfs_agblock_t			mod;
453 	int				offset;
454 
455 	agbno = XFS_AGINO_TO_AGBNO(mp, *startino);
456 	mod = agbno % mp->m_sb.sb_inoalignmt;
457 	if (!mod)
458 		return;
459 
460 	/* calculate the inode offset and align startino */
461 	offset = XFS_AGB_TO_AGINO(mp, mod);
462 	*startino -= offset;
463 
464 	/*
465 	 * Since startino has been aligned down, left shift allocmask such that
466 	 * it continues to represent the same physical inodes relative to the
467 	 * new startino.
468 	 */
469 	*allocmask <<= offset / XFS_INODES_PER_HOLEMASK_BIT;
470 }
471 
472 /*
473  * Determine whether the source inode record can merge into the target. Both
474  * records must be sparse, the inode ranges must match and there must be no
475  * allocation overlap between the records.
476  */
477 STATIC bool
478 __xfs_inobt_can_merge(
479 	struct xfs_inobt_rec_incore	*trec,	/* tgt record */
480 	struct xfs_inobt_rec_incore	*srec)	/* src record */
481 {
482 	uint64_t			talloc;
483 	uint64_t			salloc;
484 
485 	/* records must cover the same inode range */
486 	if (trec->ir_startino != srec->ir_startino)
487 		return false;
488 
489 	/* both records must be sparse */
490 	if (!xfs_inobt_issparse(trec->ir_holemask) ||
491 	    !xfs_inobt_issparse(srec->ir_holemask))
492 		return false;
493 
494 	/* both records must track some inodes */
495 	if (!trec->ir_count || !srec->ir_count)
496 		return false;
497 
498 	/* can't exceed capacity of a full record */
499 	if (trec->ir_count + srec->ir_count > XFS_INODES_PER_CHUNK)
500 		return false;
501 
502 	/* verify there is no allocation overlap */
503 	talloc = xfs_inobt_irec_to_allocmask(trec);
504 	salloc = xfs_inobt_irec_to_allocmask(srec);
505 	if (talloc & salloc)
506 		return false;
507 
508 	return true;
509 }
510 
511 /*
512  * Merge the source inode record into the target. The caller must call
513  * __xfs_inobt_can_merge() to ensure the merge is valid.
514  */
515 STATIC void
516 __xfs_inobt_rec_merge(
517 	struct xfs_inobt_rec_incore	*trec,	/* target */
518 	struct xfs_inobt_rec_incore	*srec)	/* src */
519 {
520 	ASSERT(trec->ir_startino == srec->ir_startino);
521 
522 	/* combine the counts */
523 	trec->ir_count += srec->ir_count;
524 	trec->ir_freecount += srec->ir_freecount;
525 
526 	/*
527 	 * Merge the holemask and free mask. For both fields, 0 bits refer to
528 	 * allocated inodes. We combine the allocated ranges with bitwise AND.
529 	 */
530 	trec->ir_holemask &= srec->ir_holemask;
531 	trec->ir_free &= srec->ir_free;
532 }
533 
534 /*
535  * Insert a new sparse inode chunk into the associated inode allocation btree.
536  * The inode record for the sparse chunk is pre-aligned to a startino that
537  * should match any pre-existing sparse inode record in the tree. This allows
538  * sparse chunks to fill over time.
539  *
540  * If no preexisting record exists, the provided record is inserted.
541  * If there is a preexisting record, the provided record is merged with the
542  * existing record and updated in place. The merged record is returned in nrec.
543  *
544  * It is considered corruption if a merge is requested and not possible. Given
545  * the sparse inode alignment constraints, this should never happen.
546  */
547 STATIC int
548 xfs_inobt_insert_sprec(
549 	struct xfs_perag		*pag,
550 	struct xfs_trans		*tp,
551 	struct xfs_buf			*agbp,
552 	struct xfs_inobt_rec_incore	*nrec)	/* in/out: new/merged rec. */
553 {
554 	struct xfs_mount		*mp = pag->pag_mount;
555 	struct xfs_btree_cur		*cur;
556 	int				error;
557 	int				i;
558 	struct xfs_inobt_rec_incore	rec;
559 
560 	cur = xfs_inobt_init_cursor(pag, tp, agbp);
561 
562 	/* the new record is pre-aligned so we know where to look */
563 	error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i);
564 	if (error)
565 		goto error;
566 	/* if nothing there, insert a new record and return */
567 	if (i == 0) {
568 		error = xfs_inobt_insert_rec(cur, nrec->ir_holemask,
569 					     nrec->ir_count, nrec->ir_freecount,
570 					     nrec->ir_free, &i);
571 		if (error)
572 			goto error;
573 		if (XFS_IS_CORRUPT(mp, i != 1)) {
574 			xfs_btree_mark_sick(cur);
575 			error = -EFSCORRUPTED;
576 			goto error;
577 		}
578 
579 		goto out;
580 	}
581 
582 	/*
583 	 * A record exists at this startino.  Merge the records.
584 	 */
585 	error = xfs_inobt_get_rec(cur, &rec, &i);
586 	if (error)
587 		goto error;
588 	if (XFS_IS_CORRUPT(mp, i != 1)) {
589 		xfs_btree_mark_sick(cur);
590 		error = -EFSCORRUPTED;
591 		goto error;
592 	}
593 	if (XFS_IS_CORRUPT(mp, rec.ir_startino != nrec->ir_startino)) {
594 		xfs_btree_mark_sick(cur);
595 		error = -EFSCORRUPTED;
596 		goto error;
597 	}
598 
599 	/*
600 	 * This should never fail. If we have coexisting records that
601 	 * cannot merge, something is seriously wrong.
602 	 */
603 	if (XFS_IS_CORRUPT(mp, !__xfs_inobt_can_merge(nrec, &rec))) {
604 		xfs_btree_mark_sick(cur);
605 		error = -EFSCORRUPTED;
606 		goto error;
607 	}
608 
609 	trace_xfs_irec_merge_pre(mp, pag->pag_agno, rec.ir_startino,
610 				 rec.ir_holemask, nrec->ir_startino,
611 				 nrec->ir_holemask);
612 
613 	/* merge to nrec to output the updated record */
614 	__xfs_inobt_rec_merge(nrec, &rec);
615 
616 	trace_xfs_irec_merge_post(mp, pag->pag_agno, nrec->ir_startino,
617 				  nrec->ir_holemask);
618 
619 	error = xfs_inobt_rec_check_count(mp, nrec);
620 	if (error)
621 		goto error;
622 
623 	error = xfs_inobt_update(cur, nrec);
624 	if (error)
625 		goto error;
626 
627 out:
628 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
629 	return 0;
630 error:
631 	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
632 	return error;
633 }
634 
635 /*
636  * Insert a new sparse inode chunk into the free inode btree. The inode
637  * record for the sparse chunk is pre-aligned to a startino that should match
638  * any pre-existing sparse inode record in the tree. This allows sparse chunks
639  * to fill over time.
640  *
641  * The new record is always inserted, overwriting a pre-existing record if
642  * there is one.
643  */
644 STATIC int
645 xfs_finobt_insert_sprec(
646 	struct xfs_perag		*pag,
647 	struct xfs_trans		*tp,
648 	struct xfs_buf			*agbp,
649 	struct xfs_inobt_rec_incore	*nrec)	/* in/out: new rec. */
650 {
651 	struct xfs_mount		*mp = pag->pag_mount;
652 	struct xfs_btree_cur		*cur;
653 	int				error;
654 	int				i;
655 
656 	cur = xfs_finobt_init_cursor(pag, tp, agbp);
657 
658 	/* the new record is pre-aligned so we know where to look */
659 	error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i);
660 	if (error)
661 		goto error;
662 	/* if nothing there, insert a new record and return */
663 	if (i == 0) {
664 		error = xfs_inobt_insert_rec(cur, nrec->ir_holemask,
665 					     nrec->ir_count, nrec->ir_freecount,
666 					     nrec->ir_free, &i);
667 		if (error)
668 			goto error;
669 		if (XFS_IS_CORRUPT(mp, i != 1)) {
670 			xfs_btree_mark_sick(cur);
671 			error = -EFSCORRUPTED;
672 			goto error;
673 		}
674 	} else {
675 		error = xfs_inobt_update(cur, nrec);
676 		if (error)
677 			goto error;
678 	}
679 
680 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
681 	return 0;
682 error:
683 	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
684 	return error;
685 }
686 
687 
688 /*
689  * Allocate new inodes in the allocation group specified by agbp.  Returns 0 if
690  * inodes were allocated in this AG; -EAGAIN if there was no space in this AG so
691  * the caller knows it can try another AG, a hard -ENOSPC when over the maximum
692  * inode count threshold, or the usual negative error code for other errors.
693  */
694 STATIC int
695 xfs_ialloc_ag_alloc(
696 	struct xfs_perag	*pag,
697 	struct xfs_trans	*tp,
698 	struct xfs_buf		*agbp)
699 {
700 	struct xfs_agi		*agi;
701 	struct xfs_alloc_arg	args;
702 	int			error;
703 	xfs_agino_t		newino;		/* new first inode's number */
704 	xfs_agino_t		newlen;		/* new number of inodes */
705 	int			isaligned = 0;	/* inode allocation at stripe */
706 						/* unit boundary */
707 	/* init. to full chunk */
708 	struct xfs_inobt_rec_incore rec;
709 	struct xfs_ino_geometry	*igeo = M_IGEO(tp->t_mountp);
710 	uint16_t		allocmask = (uint16_t) -1;
711 	int			do_sparse = 0;
712 
713 	memset(&args, 0, sizeof(args));
714 	args.tp = tp;
715 	args.mp = tp->t_mountp;
716 	args.fsbno = NULLFSBLOCK;
717 	args.oinfo = XFS_RMAP_OINFO_INODES;
718 	args.pag = pag;
719 
720 #ifdef DEBUG
721 	/* randomly do sparse inode allocations */
722 	if (xfs_has_sparseinodes(tp->t_mountp) &&
723 	    igeo->ialloc_min_blks < igeo->ialloc_blks)
724 		do_sparse = get_random_u32_below(2);
725 #endif
726 
727 	/*
728 	 * Locking will ensure that we don't have two callers in here
729 	 * at one time.
730 	 */
731 	newlen = igeo->ialloc_inos;
732 	if (igeo->maxicount &&
733 	    percpu_counter_read_positive(&args.mp->m_icount) + newlen >
734 							igeo->maxicount)
735 		return -ENOSPC;
736 	args.minlen = args.maxlen = igeo->ialloc_blks;
737 	/*
738 	 * First try to allocate inodes contiguous with the last-allocated
739 	 * chunk of inodes.  If the filesystem is striped, this will fill
740 	 * an entire stripe unit with inodes.
741 	 */
742 	agi = agbp->b_addr;
743 	newino = be32_to_cpu(agi->agi_newino);
744 	args.agbno = XFS_AGINO_TO_AGBNO(args.mp, newino) +
745 		     igeo->ialloc_blks;
746 	if (do_sparse)
747 		goto sparse_alloc;
748 	if (likely(newino != NULLAGINO &&
749 		  (args.agbno < be32_to_cpu(agi->agi_length)))) {
750 		args.prod = 1;
751 
752 		/*
753 		 * We need to take into account alignment here to ensure that
754 		 * we don't modify the free list if we fail to have an exact
755 		 * block. If we don't have an exact match, and every oher
756 		 * attempt allocation attempt fails, we'll end up cancelling
757 		 * a dirty transaction and shutting down.
758 		 *
759 		 * For an exact allocation, alignment must be 1,
760 		 * however we need to take cluster alignment into account when
761 		 * fixing up the freelist. Use the minalignslop field to
762 		 * indicate that extra blocks might be required for alignment,
763 		 * but not to use them in the actual exact allocation.
764 		 */
765 		args.alignment = 1;
766 		args.minalignslop = igeo->cluster_align - 1;
767 
768 		/* Allow space for the inode btree to split. */
769 		args.minleft = igeo->inobt_maxlevels;
770 		error = xfs_alloc_vextent_exact_bno(&args,
771 				XFS_AGB_TO_FSB(args.mp, pag->pag_agno,
772 						args.agbno));
773 		if (error)
774 			return error;
775 
776 		/*
777 		 * This request might have dirtied the transaction if the AG can
778 		 * satisfy the request, but the exact block was not available.
779 		 * If the allocation did fail, subsequent requests will relax
780 		 * the exact agbno requirement and increase the alignment
781 		 * instead. It is critical that the total size of the request
782 		 * (len + alignment + slop) does not increase from this point
783 		 * on, so reset minalignslop to ensure it is not included in
784 		 * subsequent requests.
785 		 */
786 		args.minalignslop = 0;
787 	}
788 
789 	if (unlikely(args.fsbno == NULLFSBLOCK)) {
790 		/*
791 		 * Set the alignment for the allocation.
792 		 * If stripe alignment is turned on then align at stripe unit
793 		 * boundary.
794 		 * If the cluster size is smaller than a filesystem block
795 		 * then we're doing I/O for inodes in filesystem block size
796 		 * pieces, so don't need alignment anyway.
797 		 */
798 		isaligned = 0;
799 		if (igeo->ialloc_align) {
800 			ASSERT(!xfs_has_noalign(args.mp));
801 			args.alignment = args.mp->m_dalign;
802 			isaligned = 1;
803 		} else
804 			args.alignment = igeo->cluster_align;
805 		/*
806 		 * Allocate a fixed-size extent of inodes.
807 		 */
808 		args.prod = 1;
809 		/*
810 		 * Allow space for the inode btree to split.
811 		 */
812 		args.minleft = igeo->inobt_maxlevels;
813 		error = xfs_alloc_vextent_near_bno(&args,
814 				XFS_AGB_TO_FSB(args.mp, pag->pag_agno,
815 						be32_to_cpu(agi->agi_root)));
816 		if (error)
817 			return error;
818 	}
819 
820 	/*
821 	 * If stripe alignment is turned on, then try again with cluster
822 	 * alignment.
823 	 */
824 	if (isaligned && args.fsbno == NULLFSBLOCK) {
825 		args.alignment = igeo->cluster_align;
826 		error = xfs_alloc_vextent_near_bno(&args,
827 				XFS_AGB_TO_FSB(args.mp, pag->pag_agno,
828 						be32_to_cpu(agi->agi_root)));
829 		if (error)
830 			return error;
831 	}
832 
833 	/*
834 	 * Finally, try a sparse allocation if the filesystem supports it and
835 	 * the sparse allocation length is smaller than a full chunk.
836 	 */
837 	if (xfs_has_sparseinodes(args.mp) &&
838 	    igeo->ialloc_min_blks < igeo->ialloc_blks &&
839 	    args.fsbno == NULLFSBLOCK) {
840 sparse_alloc:
841 		args.alignment = args.mp->m_sb.sb_spino_align;
842 		args.prod = 1;
843 
844 		args.minlen = igeo->ialloc_min_blks;
845 		args.maxlen = args.minlen;
846 
847 		/*
848 		 * The inode record will be aligned to full chunk size. We must
849 		 * prevent sparse allocation from AG boundaries that result in
850 		 * invalid inode records, such as records that start at agbno 0
851 		 * or extend beyond the AG.
852 		 *
853 		 * Set min agbno to the first aligned, non-zero agbno and max to
854 		 * the last aligned agbno that is at least one full chunk from
855 		 * the end of the AG.
856 		 */
857 		args.min_agbno = args.mp->m_sb.sb_inoalignmt;
858 		args.max_agbno = round_down(args.mp->m_sb.sb_agblocks,
859 					    args.mp->m_sb.sb_inoalignmt) -
860 				 igeo->ialloc_blks;
861 
862 		error = xfs_alloc_vextent_near_bno(&args,
863 				XFS_AGB_TO_FSB(args.mp, pag->pag_agno,
864 						be32_to_cpu(agi->agi_root)));
865 		if (error)
866 			return error;
867 
868 		newlen = XFS_AGB_TO_AGINO(args.mp, args.len);
869 		ASSERT(newlen <= XFS_INODES_PER_CHUNK);
870 		allocmask = (1 << (newlen / XFS_INODES_PER_HOLEMASK_BIT)) - 1;
871 	}
872 
873 	if (args.fsbno == NULLFSBLOCK)
874 		return -EAGAIN;
875 
876 	ASSERT(args.len == args.minlen);
877 
878 	/*
879 	 * Stamp and write the inode buffers.
880 	 *
881 	 * Seed the new inode cluster with a random generation number. This
882 	 * prevents short-term reuse of generation numbers if a chunk is
883 	 * freed and then immediately reallocated. We use random numbers
884 	 * rather than a linear progression to prevent the next generation
885 	 * number from being easily guessable.
886 	 */
887 	error = xfs_ialloc_inode_init(args.mp, tp, NULL, newlen, pag->pag_agno,
888 			args.agbno, args.len, get_random_u32());
889 
890 	if (error)
891 		return error;
892 	/*
893 	 * Convert the results.
894 	 */
895 	newino = XFS_AGB_TO_AGINO(args.mp, args.agbno);
896 
897 	if (xfs_inobt_issparse(~allocmask)) {
898 		/*
899 		 * We've allocated a sparse chunk. Align the startino and mask.
900 		 */
901 		xfs_align_sparse_ino(args.mp, &newino, &allocmask);
902 
903 		rec.ir_startino = newino;
904 		rec.ir_holemask = ~allocmask;
905 		rec.ir_count = newlen;
906 		rec.ir_freecount = newlen;
907 		rec.ir_free = XFS_INOBT_ALL_FREE;
908 
909 		/*
910 		 * Insert the sparse record into the inobt and allow for a merge
911 		 * if necessary. If a merge does occur, rec is updated to the
912 		 * merged record.
913 		 */
914 		error = xfs_inobt_insert_sprec(pag, tp, agbp, &rec);
915 		if (error == -EFSCORRUPTED) {
916 			xfs_alert(args.mp,
917 	"invalid sparse inode record: ino 0x%llx holemask 0x%x count %u",
918 				  XFS_AGINO_TO_INO(args.mp, pag->pag_agno,
919 						   rec.ir_startino),
920 				  rec.ir_holemask, rec.ir_count);
921 			xfs_force_shutdown(args.mp, SHUTDOWN_CORRUPT_INCORE);
922 		}
923 		if (error)
924 			return error;
925 
926 		/*
927 		 * We can't merge the part we've just allocated as for the inobt
928 		 * due to finobt semantics. The original record may or may not
929 		 * exist independent of whether physical inodes exist in this
930 		 * sparse chunk.
931 		 *
932 		 * We must update the finobt record based on the inobt record.
933 		 * rec contains the fully merged and up to date inobt record
934 		 * from the previous call. Set merge false to replace any
935 		 * existing record with this one.
936 		 */
937 		if (xfs_has_finobt(args.mp)) {
938 			error = xfs_finobt_insert_sprec(pag, tp, agbp, &rec);
939 			if (error)
940 				return error;
941 		}
942 	} else {
943 		/* full chunk - insert new records to both btrees */
944 		error = xfs_inobt_insert(pag, tp, agbp, newino, newlen, false);
945 		if (error)
946 			return error;
947 
948 		if (xfs_has_finobt(args.mp)) {
949 			error = xfs_inobt_insert(pag, tp, agbp, newino,
950 						 newlen, true);
951 			if (error)
952 				return error;
953 		}
954 	}
955 
956 	/*
957 	 * Update AGI counts and newino.
958 	 */
959 	be32_add_cpu(&agi->agi_count, newlen);
960 	be32_add_cpu(&agi->agi_freecount, newlen);
961 	pag->pagi_freecount += newlen;
962 	pag->pagi_count += newlen;
963 	agi->agi_newino = cpu_to_be32(newino);
964 
965 	/*
966 	 * Log allocation group header fields
967 	 */
968 	xfs_ialloc_log_agi(tp, agbp,
969 		XFS_AGI_COUNT | XFS_AGI_FREECOUNT | XFS_AGI_NEWINO);
970 	/*
971 	 * Modify/log superblock values for inode count and inode free count.
972 	 */
973 	xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, (long)newlen);
974 	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, (long)newlen);
975 	return 0;
976 }
977 
978 /*
979  * Try to retrieve the next record to the left/right from the current one.
980  */
981 STATIC int
982 xfs_ialloc_next_rec(
983 	struct xfs_btree_cur	*cur,
984 	xfs_inobt_rec_incore_t	*rec,
985 	int			*done,
986 	int			left)
987 {
988 	int                     error;
989 	int			i;
990 
991 	if (left)
992 		error = xfs_btree_decrement(cur, 0, &i);
993 	else
994 		error = xfs_btree_increment(cur, 0, &i);
995 
996 	if (error)
997 		return error;
998 	*done = !i;
999 	if (i) {
1000 		error = xfs_inobt_get_rec(cur, rec, &i);
1001 		if (error)
1002 			return error;
1003 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1004 			xfs_btree_mark_sick(cur);
1005 			return -EFSCORRUPTED;
1006 		}
1007 	}
1008 
1009 	return 0;
1010 }
1011 
1012 STATIC int
1013 xfs_ialloc_get_rec(
1014 	struct xfs_btree_cur	*cur,
1015 	xfs_agino_t		agino,
1016 	xfs_inobt_rec_incore_t	*rec,
1017 	int			*done)
1018 {
1019 	int                     error;
1020 	int			i;
1021 
1022 	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_EQ, &i);
1023 	if (error)
1024 		return error;
1025 	*done = !i;
1026 	if (i) {
1027 		error = xfs_inobt_get_rec(cur, rec, &i);
1028 		if (error)
1029 			return error;
1030 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1031 			xfs_btree_mark_sick(cur);
1032 			return -EFSCORRUPTED;
1033 		}
1034 	}
1035 
1036 	return 0;
1037 }
1038 
1039 /*
1040  * Return the offset of the first free inode in the record. If the inode chunk
1041  * is sparsely allocated, we convert the record holemask to inode granularity
1042  * and mask off the unallocated regions from the inode free mask.
1043  */
1044 STATIC int
1045 xfs_inobt_first_free_inode(
1046 	struct xfs_inobt_rec_incore	*rec)
1047 {
1048 	xfs_inofree_t			realfree;
1049 
1050 	/* if there are no holes, return the first available offset */
1051 	if (!xfs_inobt_issparse(rec->ir_holemask))
1052 		return xfs_lowbit64(rec->ir_free);
1053 
1054 	realfree = xfs_inobt_irec_to_allocmask(rec);
1055 	realfree &= rec->ir_free;
1056 
1057 	return xfs_lowbit64(realfree);
1058 }
1059 
1060 /*
1061  * If this AG has corrupt inodes, check if allocating this inode would fail
1062  * with corruption errors.  Returns 0 if we're clear, or EAGAIN to try again
1063  * somewhere else.
1064  */
1065 static int
1066 xfs_dialloc_check_ino(
1067 	struct xfs_perag	*pag,
1068 	struct xfs_trans	*tp,
1069 	xfs_ino_t		ino)
1070 {
1071 	struct xfs_imap		imap;
1072 	struct xfs_buf		*bp;
1073 	int			error;
1074 
1075 	error = xfs_imap(pag, tp, ino, &imap, 0);
1076 	if (error)
1077 		return -EAGAIN;
1078 
1079 	error = xfs_imap_to_bp(pag->pag_mount, tp, &imap, &bp);
1080 	if (error)
1081 		return -EAGAIN;
1082 
1083 	xfs_trans_brelse(tp, bp);
1084 	return 0;
1085 }
1086 
1087 /*
1088  * Allocate an inode using the inobt-only algorithm.
1089  */
1090 STATIC int
1091 xfs_dialloc_ag_inobt(
1092 	struct xfs_perag	*pag,
1093 	struct xfs_trans	*tp,
1094 	struct xfs_buf		*agbp,
1095 	xfs_ino_t		parent,
1096 	xfs_ino_t		*inop)
1097 {
1098 	struct xfs_mount	*mp = tp->t_mountp;
1099 	struct xfs_agi		*agi = agbp->b_addr;
1100 	xfs_agnumber_t		pagno = XFS_INO_TO_AGNO(mp, parent);
1101 	xfs_agino_t		pagino = XFS_INO_TO_AGINO(mp, parent);
1102 	struct xfs_btree_cur	*cur, *tcur;
1103 	struct xfs_inobt_rec_incore rec, trec;
1104 	xfs_ino_t		ino;
1105 	int			error;
1106 	int			offset;
1107 	int			i, j;
1108 	int			searchdistance = 10;
1109 
1110 	ASSERT(xfs_perag_initialised_agi(pag));
1111 	ASSERT(xfs_perag_allows_inodes(pag));
1112 	ASSERT(pag->pagi_freecount > 0);
1113 
1114  restart_pagno:
1115 	cur = xfs_inobt_init_cursor(pag, tp, agbp);
1116 	/*
1117 	 * If pagino is 0 (this is the root inode allocation) use newino.
1118 	 * This must work because we've just allocated some.
1119 	 */
1120 	if (!pagino)
1121 		pagino = be32_to_cpu(agi->agi_newino);
1122 
1123 	error = xfs_check_agi_freecount(cur);
1124 	if (error)
1125 		goto error0;
1126 
1127 	/*
1128 	 * If in the same AG as the parent, try to get near the parent.
1129 	 */
1130 	if (pagno == pag->pag_agno) {
1131 		int		doneleft;	/* done, to the left */
1132 		int		doneright;	/* done, to the right */
1133 
1134 		error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i);
1135 		if (error)
1136 			goto error0;
1137 		if (XFS_IS_CORRUPT(mp, i != 1)) {
1138 			xfs_btree_mark_sick(cur);
1139 			error = -EFSCORRUPTED;
1140 			goto error0;
1141 		}
1142 
1143 		error = xfs_inobt_get_rec(cur, &rec, &j);
1144 		if (error)
1145 			goto error0;
1146 		if (XFS_IS_CORRUPT(mp, j != 1)) {
1147 			xfs_btree_mark_sick(cur);
1148 			error = -EFSCORRUPTED;
1149 			goto error0;
1150 		}
1151 
1152 		if (rec.ir_freecount > 0) {
1153 			/*
1154 			 * Found a free inode in the same chunk
1155 			 * as the parent, done.
1156 			 */
1157 			goto alloc_inode;
1158 		}
1159 
1160 
1161 		/*
1162 		 * In the same AG as parent, but parent's chunk is full.
1163 		 */
1164 
1165 		/* duplicate the cursor, search left & right simultaneously */
1166 		error = xfs_btree_dup_cursor(cur, &tcur);
1167 		if (error)
1168 			goto error0;
1169 
1170 		/*
1171 		 * Skip to last blocks looked up if same parent inode.
1172 		 */
1173 		if (pagino != NULLAGINO &&
1174 		    pag->pagl_pagino == pagino &&
1175 		    pag->pagl_leftrec != NULLAGINO &&
1176 		    pag->pagl_rightrec != NULLAGINO) {
1177 			error = xfs_ialloc_get_rec(tcur, pag->pagl_leftrec,
1178 						   &trec, &doneleft);
1179 			if (error)
1180 				goto error1;
1181 
1182 			error = xfs_ialloc_get_rec(cur, pag->pagl_rightrec,
1183 						   &rec, &doneright);
1184 			if (error)
1185 				goto error1;
1186 		} else {
1187 			/* search left with tcur, back up 1 record */
1188 			error = xfs_ialloc_next_rec(tcur, &trec, &doneleft, 1);
1189 			if (error)
1190 				goto error1;
1191 
1192 			/* search right with cur, go forward 1 record. */
1193 			error = xfs_ialloc_next_rec(cur, &rec, &doneright, 0);
1194 			if (error)
1195 				goto error1;
1196 		}
1197 
1198 		/*
1199 		 * Loop until we find an inode chunk with a free inode.
1200 		 */
1201 		while (--searchdistance > 0 && (!doneleft || !doneright)) {
1202 			int	useleft;  /* using left inode chunk this time */
1203 
1204 			/* figure out the closer block if both are valid. */
1205 			if (!doneleft && !doneright) {
1206 				useleft = pagino -
1207 				 (trec.ir_startino + XFS_INODES_PER_CHUNK - 1) <
1208 				  rec.ir_startino - pagino;
1209 			} else {
1210 				useleft = !doneleft;
1211 			}
1212 
1213 			/* free inodes to the left? */
1214 			if (useleft && trec.ir_freecount) {
1215 				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1216 				cur = tcur;
1217 
1218 				pag->pagl_leftrec = trec.ir_startino;
1219 				pag->pagl_rightrec = rec.ir_startino;
1220 				pag->pagl_pagino = pagino;
1221 				rec = trec;
1222 				goto alloc_inode;
1223 			}
1224 
1225 			/* free inodes to the right? */
1226 			if (!useleft && rec.ir_freecount) {
1227 				xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1228 
1229 				pag->pagl_leftrec = trec.ir_startino;
1230 				pag->pagl_rightrec = rec.ir_startino;
1231 				pag->pagl_pagino = pagino;
1232 				goto alloc_inode;
1233 			}
1234 
1235 			/* get next record to check */
1236 			if (useleft) {
1237 				error = xfs_ialloc_next_rec(tcur, &trec,
1238 								 &doneleft, 1);
1239 			} else {
1240 				error = xfs_ialloc_next_rec(cur, &rec,
1241 								 &doneright, 0);
1242 			}
1243 			if (error)
1244 				goto error1;
1245 		}
1246 
1247 		if (searchdistance <= 0) {
1248 			/*
1249 			 * Not in range - save last search
1250 			 * location and allocate a new inode
1251 			 */
1252 			xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1253 			pag->pagl_leftrec = trec.ir_startino;
1254 			pag->pagl_rightrec = rec.ir_startino;
1255 			pag->pagl_pagino = pagino;
1256 
1257 		} else {
1258 			/*
1259 			 * We've reached the end of the btree. because
1260 			 * we are only searching a small chunk of the
1261 			 * btree each search, there is obviously free
1262 			 * inodes closer to the parent inode than we
1263 			 * are now. restart the search again.
1264 			 */
1265 			pag->pagl_pagino = NULLAGINO;
1266 			pag->pagl_leftrec = NULLAGINO;
1267 			pag->pagl_rightrec = NULLAGINO;
1268 			xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1269 			xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1270 			goto restart_pagno;
1271 		}
1272 	}
1273 
1274 	/*
1275 	 * In a different AG from the parent.
1276 	 * See if the most recently allocated block has any free.
1277 	 */
1278 	if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
1279 		error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
1280 					 XFS_LOOKUP_EQ, &i);
1281 		if (error)
1282 			goto error0;
1283 
1284 		if (i == 1) {
1285 			error = xfs_inobt_get_rec(cur, &rec, &j);
1286 			if (error)
1287 				goto error0;
1288 
1289 			if (j == 1 && rec.ir_freecount > 0) {
1290 				/*
1291 				 * The last chunk allocated in the group
1292 				 * still has a free inode.
1293 				 */
1294 				goto alloc_inode;
1295 			}
1296 		}
1297 	}
1298 
1299 	/*
1300 	 * None left in the last group, search the whole AG
1301 	 */
1302 	error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
1303 	if (error)
1304 		goto error0;
1305 	if (XFS_IS_CORRUPT(mp, i != 1)) {
1306 		xfs_btree_mark_sick(cur);
1307 		error = -EFSCORRUPTED;
1308 		goto error0;
1309 	}
1310 
1311 	for (;;) {
1312 		error = xfs_inobt_get_rec(cur, &rec, &i);
1313 		if (error)
1314 			goto error0;
1315 		if (XFS_IS_CORRUPT(mp, i != 1)) {
1316 			xfs_btree_mark_sick(cur);
1317 			error = -EFSCORRUPTED;
1318 			goto error0;
1319 		}
1320 		if (rec.ir_freecount > 0)
1321 			break;
1322 		error = xfs_btree_increment(cur, 0, &i);
1323 		if (error)
1324 			goto error0;
1325 		if (XFS_IS_CORRUPT(mp, i != 1)) {
1326 			xfs_btree_mark_sick(cur);
1327 			error = -EFSCORRUPTED;
1328 			goto error0;
1329 		}
1330 	}
1331 
1332 alloc_inode:
1333 	offset = xfs_inobt_first_free_inode(&rec);
1334 	ASSERT(offset >= 0);
1335 	ASSERT(offset < XFS_INODES_PER_CHUNK);
1336 	ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
1337 				   XFS_INODES_PER_CHUNK) == 0);
1338 	ino = XFS_AGINO_TO_INO(mp, pag->pag_agno, rec.ir_startino + offset);
1339 
1340 	if (xfs_ag_has_sickness(pag, XFS_SICK_AG_INODES)) {
1341 		error = xfs_dialloc_check_ino(pag, tp, ino);
1342 		if (error)
1343 			goto error0;
1344 	}
1345 
1346 	rec.ir_free &= ~XFS_INOBT_MASK(offset);
1347 	rec.ir_freecount--;
1348 	error = xfs_inobt_update(cur, &rec);
1349 	if (error)
1350 		goto error0;
1351 	be32_add_cpu(&agi->agi_freecount, -1);
1352 	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1353 	pag->pagi_freecount--;
1354 
1355 	error = xfs_check_agi_freecount(cur);
1356 	if (error)
1357 		goto error0;
1358 
1359 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1360 	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
1361 	*inop = ino;
1362 	return 0;
1363 error1:
1364 	xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1365 error0:
1366 	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1367 	return error;
1368 }
1369 
1370 /*
1371  * Use the free inode btree to allocate an inode based on distance from the
1372  * parent. Note that the provided cursor may be deleted and replaced.
1373  */
1374 STATIC int
1375 xfs_dialloc_ag_finobt_near(
1376 	xfs_agino_t			pagino,
1377 	struct xfs_btree_cur		**ocur,
1378 	struct xfs_inobt_rec_incore	*rec)
1379 {
1380 	struct xfs_btree_cur		*lcur = *ocur;	/* left search cursor */
1381 	struct xfs_btree_cur		*rcur;	/* right search cursor */
1382 	struct xfs_inobt_rec_incore	rrec;
1383 	int				error;
1384 	int				i, j;
1385 
1386 	error = xfs_inobt_lookup(lcur, pagino, XFS_LOOKUP_LE, &i);
1387 	if (error)
1388 		return error;
1389 
1390 	if (i == 1) {
1391 		error = xfs_inobt_get_rec(lcur, rec, &i);
1392 		if (error)
1393 			return error;
1394 		if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1)) {
1395 			xfs_btree_mark_sick(lcur);
1396 			return -EFSCORRUPTED;
1397 		}
1398 
1399 		/*
1400 		 * See if we've landed in the parent inode record. The finobt
1401 		 * only tracks chunks with at least one free inode, so record
1402 		 * existence is enough.
1403 		 */
1404 		if (pagino >= rec->ir_startino &&
1405 		    pagino < (rec->ir_startino + XFS_INODES_PER_CHUNK))
1406 			return 0;
1407 	}
1408 
1409 	error = xfs_btree_dup_cursor(lcur, &rcur);
1410 	if (error)
1411 		return error;
1412 
1413 	error = xfs_inobt_lookup(rcur, pagino, XFS_LOOKUP_GE, &j);
1414 	if (error)
1415 		goto error_rcur;
1416 	if (j == 1) {
1417 		error = xfs_inobt_get_rec(rcur, &rrec, &j);
1418 		if (error)
1419 			goto error_rcur;
1420 		if (XFS_IS_CORRUPT(lcur->bc_mp, j != 1)) {
1421 			xfs_btree_mark_sick(lcur);
1422 			error = -EFSCORRUPTED;
1423 			goto error_rcur;
1424 		}
1425 	}
1426 
1427 	if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1 && j != 1)) {
1428 		xfs_btree_mark_sick(lcur);
1429 		error = -EFSCORRUPTED;
1430 		goto error_rcur;
1431 	}
1432 	if (i == 1 && j == 1) {
1433 		/*
1434 		 * Both the left and right records are valid. Choose the closer
1435 		 * inode chunk to the target.
1436 		 */
1437 		if ((pagino - rec->ir_startino + XFS_INODES_PER_CHUNK - 1) >
1438 		    (rrec.ir_startino - pagino)) {
1439 			*rec = rrec;
1440 			xfs_btree_del_cursor(lcur, XFS_BTREE_NOERROR);
1441 			*ocur = rcur;
1442 		} else {
1443 			xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR);
1444 		}
1445 	} else if (j == 1) {
1446 		/* only the right record is valid */
1447 		*rec = rrec;
1448 		xfs_btree_del_cursor(lcur, XFS_BTREE_NOERROR);
1449 		*ocur = rcur;
1450 	} else if (i == 1) {
1451 		/* only the left record is valid */
1452 		xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR);
1453 	}
1454 
1455 	return 0;
1456 
1457 error_rcur:
1458 	xfs_btree_del_cursor(rcur, XFS_BTREE_ERROR);
1459 	return error;
1460 }
1461 
1462 /*
1463  * Use the free inode btree to find a free inode based on a newino hint. If
1464  * the hint is NULL, find the first free inode in the AG.
1465  */
1466 STATIC int
1467 xfs_dialloc_ag_finobt_newino(
1468 	struct xfs_agi			*agi,
1469 	struct xfs_btree_cur		*cur,
1470 	struct xfs_inobt_rec_incore	*rec)
1471 {
1472 	int error;
1473 	int i;
1474 
1475 	if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
1476 		error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
1477 					 XFS_LOOKUP_EQ, &i);
1478 		if (error)
1479 			return error;
1480 		if (i == 1) {
1481 			error = xfs_inobt_get_rec(cur, rec, &i);
1482 			if (error)
1483 				return error;
1484 			if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1485 				xfs_btree_mark_sick(cur);
1486 				return -EFSCORRUPTED;
1487 			}
1488 			return 0;
1489 		}
1490 	}
1491 
1492 	/*
1493 	 * Find the first inode available in the AG.
1494 	 */
1495 	error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
1496 	if (error)
1497 		return error;
1498 	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1499 		xfs_btree_mark_sick(cur);
1500 		return -EFSCORRUPTED;
1501 	}
1502 
1503 	error = xfs_inobt_get_rec(cur, rec, &i);
1504 	if (error)
1505 		return error;
1506 	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1507 		xfs_btree_mark_sick(cur);
1508 		return -EFSCORRUPTED;
1509 	}
1510 
1511 	return 0;
1512 }
1513 
1514 /*
1515  * Update the inobt based on a modification made to the finobt. Also ensure that
1516  * the records from both trees are equivalent post-modification.
1517  */
1518 STATIC int
1519 xfs_dialloc_ag_update_inobt(
1520 	struct xfs_btree_cur		*cur,	/* inobt cursor */
1521 	struct xfs_inobt_rec_incore	*frec,	/* finobt record */
1522 	int				offset) /* inode offset */
1523 {
1524 	struct xfs_inobt_rec_incore	rec;
1525 	int				error;
1526 	int				i;
1527 
1528 	error = xfs_inobt_lookup(cur, frec->ir_startino, XFS_LOOKUP_EQ, &i);
1529 	if (error)
1530 		return error;
1531 	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1532 		xfs_btree_mark_sick(cur);
1533 		return -EFSCORRUPTED;
1534 	}
1535 
1536 	error = xfs_inobt_get_rec(cur, &rec, &i);
1537 	if (error)
1538 		return error;
1539 	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1540 		xfs_btree_mark_sick(cur);
1541 		return -EFSCORRUPTED;
1542 	}
1543 	ASSERT((XFS_AGINO_TO_OFFSET(cur->bc_mp, rec.ir_startino) %
1544 				   XFS_INODES_PER_CHUNK) == 0);
1545 
1546 	rec.ir_free &= ~XFS_INOBT_MASK(offset);
1547 	rec.ir_freecount--;
1548 
1549 	if (XFS_IS_CORRUPT(cur->bc_mp,
1550 			   rec.ir_free != frec->ir_free ||
1551 			   rec.ir_freecount != frec->ir_freecount)) {
1552 		xfs_btree_mark_sick(cur);
1553 		return -EFSCORRUPTED;
1554 	}
1555 
1556 	return xfs_inobt_update(cur, &rec);
1557 }
1558 
1559 /*
1560  * Allocate an inode using the free inode btree, if available. Otherwise, fall
1561  * back to the inobt search algorithm.
1562  *
1563  * The caller selected an AG for us, and made sure that free inodes are
1564  * available.
1565  */
1566 static int
1567 xfs_dialloc_ag(
1568 	struct xfs_perag	*pag,
1569 	struct xfs_trans	*tp,
1570 	struct xfs_buf		*agbp,
1571 	xfs_ino_t		parent,
1572 	xfs_ino_t		*inop)
1573 {
1574 	struct xfs_mount		*mp = tp->t_mountp;
1575 	struct xfs_agi			*agi = agbp->b_addr;
1576 	xfs_agnumber_t			pagno = XFS_INO_TO_AGNO(mp, parent);
1577 	xfs_agino_t			pagino = XFS_INO_TO_AGINO(mp, parent);
1578 	struct xfs_btree_cur		*cur;	/* finobt cursor */
1579 	struct xfs_btree_cur		*icur;	/* inobt cursor */
1580 	struct xfs_inobt_rec_incore	rec;
1581 	xfs_ino_t			ino;
1582 	int				error;
1583 	int				offset;
1584 	int				i;
1585 
1586 	if (!xfs_has_finobt(mp))
1587 		return xfs_dialloc_ag_inobt(pag, tp, agbp, parent, inop);
1588 
1589 	/*
1590 	 * If pagino is 0 (this is the root inode allocation) use newino.
1591 	 * This must work because we've just allocated some.
1592 	 */
1593 	if (!pagino)
1594 		pagino = be32_to_cpu(agi->agi_newino);
1595 
1596 	cur = xfs_finobt_init_cursor(pag, tp, agbp);
1597 
1598 	error = xfs_check_agi_freecount(cur);
1599 	if (error)
1600 		goto error_cur;
1601 
1602 	/*
1603 	 * The search algorithm depends on whether we're in the same AG as the
1604 	 * parent. If so, find the closest available inode to the parent. If
1605 	 * not, consider the agi hint or find the first free inode in the AG.
1606 	 */
1607 	if (pag->pag_agno == pagno)
1608 		error = xfs_dialloc_ag_finobt_near(pagino, &cur, &rec);
1609 	else
1610 		error = xfs_dialloc_ag_finobt_newino(agi, cur, &rec);
1611 	if (error)
1612 		goto error_cur;
1613 
1614 	offset = xfs_inobt_first_free_inode(&rec);
1615 	ASSERT(offset >= 0);
1616 	ASSERT(offset < XFS_INODES_PER_CHUNK);
1617 	ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
1618 				   XFS_INODES_PER_CHUNK) == 0);
1619 	ino = XFS_AGINO_TO_INO(mp, pag->pag_agno, rec.ir_startino + offset);
1620 
1621 	if (xfs_ag_has_sickness(pag, XFS_SICK_AG_INODES)) {
1622 		error = xfs_dialloc_check_ino(pag, tp, ino);
1623 		if (error)
1624 			goto error_cur;
1625 	}
1626 
1627 	/*
1628 	 * Modify or remove the finobt record.
1629 	 */
1630 	rec.ir_free &= ~XFS_INOBT_MASK(offset);
1631 	rec.ir_freecount--;
1632 	if (rec.ir_freecount)
1633 		error = xfs_inobt_update(cur, &rec);
1634 	else
1635 		error = xfs_btree_delete(cur, &i);
1636 	if (error)
1637 		goto error_cur;
1638 
1639 	/*
1640 	 * The finobt has now been updated appropriately. We haven't updated the
1641 	 * agi and superblock yet, so we can create an inobt cursor and validate
1642 	 * the original freecount. If all is well, make the equivalent update to
1643 	 * the inobt using the finobt record and offset information.
1644 	 */
1645 	icur = xfs_inobt_init_cursor(pag, tp, agbp);
1646 
1647 	error = xfs_check_agi_freecount(icur);
1648 	if (error)
1649 		goto error_icur;
1650 
1651 	error = xfs_dialloc_ag_update_inobt(icur, &rec, offset);
1652 	if (error)
1653 		goto error_icur;
1654 
1655 	/*
1656 	 * Both trees have now been updated. We must update the perag and
1657 	 * superblock before we can check the freecount for each btree.
1658 	 */
1659 	be32_add_cpu(&agi->agi_freecount, -1);
1660 	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1661 	pag->pagi_freecount--;
1662 
1663 	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
1664 
1665 	error = xfs_check_agi_freecount(icur);
1666 	if (error)
1667 		goto error_icur;
1668 	error = xfs_check_agi_freecount(cur);
1669 	if (error)
1670 		goto error_icur;
1671 
1672 	xfs_btree_del_cursor(icur, XFS_BTREE_NOERROR);
1673 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1674 	*inop = ino;
1675 	return 0;
1676 
1677 error_icur:
1678 	xfs_btree_del_cursor(icur, XFS_BTREE_ERROR);
1679 error_cur:
1680 	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1681 	return error;
1682 }
1683 
1684 static int
1685 xfs_dialloc_roll(
1686 	struct xfs_trans	**tpp,
1687 	struct xfs_buf		*agibp)
1688 {
1689 	struct xfs_trans	*tp = *tpp;
1690 	struct xfs_dquot_acct	*dqinfo;
1691 	int			error;
1692 
1693 	/*
1694 	 * Hold to on to the agibp across the commit so no other allocation can
1695 	 * come in and take the free inodes we just allocated for our caller.
1696 	 */
1697 	xfs_trans_bhold(tp, agibp);
1698 
1699 	/*
1700 	 * We want the quota changes to be associated with the next transaction,
1701 	 * NOT this one. So, detach the dqinfo from this and attach it to the
1702 	 * next transaction.
1703 	 */
1704 	dqinfo = tp->t_dqinfo;
1705 	tp->t_dqinfo = NULL;
1706 
1707 	error = xfs_trans_roll(&tp);
1708 
1709 	/* Re-attach the quota info that we detached from prev trx. */
1710 	tp->t_dqinfo = dqinfo;
1711 
1712 	/*
1713 	 * Join the buffer even on commit error so that the buffer is released
1714 	 * when the caller cancels the transaction and doesn't have to handle
1715 	 * this error case specially.
1716 	 */
1717 	xfs_trans_bjoin(tp, agibp);
1718 	*tpp = tp;
1719 	return error;
1720 }
1721 
1722 static bool
1723 xfs_dialloc_good_ag(
1724 	struct xfs_perag	*pag,
1725 	struct xfs_trans	*tp,
1726 	umode_t			mode,
1727 	int			flags,
1728 	bool			ok_alloc)
1729 {
1730 	struct xfs_mount	*mp = tp->t_mountp;
1731 	xfs_extlen_t		ineed;
1732 	xfs_extlen_t		longest = 0;
1733 	int			needspace;
1734 	int			error;
1735 
1736 	if (!pag)
1737 		return false;
1738 	if (!xfs_perag_allows_inodes(pag))
1739 		return false;
1740 
1741 	if (!xfs_perag_initialised_agi(pag)) {
1742 		error = xfs_ialloc_read_agi(pag, tp, 0, NULL);
1743 		if (error)
1744 			return false;
1745 	}
1746 
1747 	if (pag->pagi_freecount)
1748 		return true;
1749 	if (!ok_alloc)
1750 		return false;
1751 
1752 	if (!xfs_perag_initialised_agf(pag)) {
1753 		error = xfs_alloc_read_agf(pag, tp, flags, NULL);
1754 		if (error)
1755 			return false;
1756 	}
1757 
1758 	/*
1759 	 * Check that there is enough free space for the file plus a chunk of
1760 	 * inodes if we need to allocate some. If this is the first pass across
1761 	 * the AGs, take into account the potential space needed for alignment
1762 	 * of inode chunks when checking the longest contiguous free space in
1763 	 * the AG - this prevents us from getting ENOSPC because we have free
1764 	 * space larger than ialloc_blks but alignment constraints prevent us
1765 	 * from using it.
1766 	 *
1767 	 * If we can't find an AG with space for full alignment slack to be
1768 	 * taken into account, we must be near ENOSPC in all AGs.  Hence we
1769 	 * don't include alignment for the second pass and so if we fail
1770 	 * allocation due to alignment issues then it is most likely a real
1771 	 * ENOSPC condition.
1772 	 *
1773 	 * XXX(dgc): this calculation is now bogus thanks to the per-ag
1774 	 * reservations that xfs_alloc_fix_freelist() now does via
1775 	 * xfs_alloc_space_available(). When the AG fills up, pagf_freeblks will
1776 	 * be more than large enough for the check below to succeed, but
1777 	 * xfs_alloc_space_available() will fail because of the non-zero
1778 	 * metadata reservation and hence we won't actually be able to allocate
1779 	 * more inodes in this AG. We do soooo much unnecessary work near ENOSPC
1780 	 * because of this.
1781 	 */
1782 	ineed = M_IGEO(mp)->ialloc_min_blks;
1783 	if (flags && ineed > 1)
1784 		ineed += M_IGEO(mp)->cluster_align;
1785 	longest = pag->pagf_longest;
1786 	if (!longest)
1787 		longest = pag->pagf_flcount > 0;
1788 	needspace = S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode);
1789 
1790 	if (pag->pagf_freeblks < needspace + ineed || longest < ineed)
1791 		return false;
1792 	return true;
1793 }
1794 
1795 static int
1796 xfs_dialloc_try_ag(
1797 	struct xfs_perag	*pag,
1798 	struct xfs_trans	**tpp,
1799 	xfs_ino_t		parent,
1800 	xfs_ino_t		*new_ino,
1801 	bool			ok_alloc)
1802 {
1803 	struct xfs_buf		*agbp;
1804 	xfs_ino_t		ino;
1805 	int			error;
1806 
1807 	/*
1808 	 * Then read in the AGI buffer and recheck with the AGI buffer
1809 	 * lock held.
1810 	 */
1811 	error = xfs_ialloc_read_agi(pag, *tpp, 0, &agbp);
1812 	if (error)
1813 		return error;
1814 
1815 	if (!pag->pagi_freecount) {
1816 		if (!ok_alloc) {
1817 			error = -EAGAIN;
1818 			goto out_release;
1819 		}
1820 
1821 		error = xfs_ialloc_ag_alloc(pag, *tpp, agbp);
1822 		if (error < 0)
1823 			goto out_release;
1824 
1825 		/*
1826 		 * We successfully allocated space for an inode cluster in this
1827 		 * AG.  Roll the transaction so that we can allocate one of the
1828 		 * new inodes.
1829 		 */
1830 		ASSERT(pag->pagi_freecount > 0);
1831 		error = xfs_dialloc_roll(tpp, agbp);
1832 		if (error)
1833 			goto out_release;
1834 	}
1835 
1836 	/* Allocate an inode in the found AG */
1837 	error = xfs_dialloc_ag(pag, *tpp, agbp, parent, &ino);
1838 	if (!error)
1839 		*new_ino = ino;
1840 	return error;
1841 
1842 out_release:
1843 	xfs_trans_brelse(*tpp, agbp);
1844 	return error;
1845 }
1846 
1847 /*
1848  * Allocate an on-disk inode.
1849  *
1850  * Mode is used to tell whether the new inode is a directory and hence where to
1851  * locate it. The on-disk inode that is allocated will be returned in @new_ino
1852  * on success, otherwise an error will be set to indicate the failure (e.g.
1853  * -ENOSPC).
1854  */
1855 int
1856 xfs_dialloc(
1857 	struct xfs_trans	**tpp,
1858 	xfs_ino_t		parent,
1859 	umode_t			mode,
1860 	xfs_ino_t		*new_ino)
1861 {
1862 	struct xfs_mount	*mp = (*tpp)->t_mountp;
1863 	xfs_agnumber_t		agno;
1864 	int			error = 0;
1865 	xfs_agnumber_t		start_agno;
1866 	struct xfs_perag	*pag;
1867 	struct xfs_ino_geometry	*igeo = M_IGEO(mp);
1868 	bool			ok_alloc = true;
1869 	bool			low_space = false;
1870 	int			flags;
1871 	xfs_ino_t		ino = NULLFSINO;
1872 
1873 	/*
1874 	 * Directories, symlinks, and regular files frequently allocate at least
1875 	 * one block, so factor that potential expansion when we examine whether
1876 	 * an AG has enough space for file creation.
1877 	 */
1878 	if (S_ISDIR(mode))
1879 		start_agno = (atomic_inc_return(&mp->m_agirotor) - 1) %
1880 				mp->m_maxagi;
1881 	else {
1882 		start_agno = XFS_INO_TO_AGNO(mp, parent);
1883 		if (start_agno >= mp->m_maxagi)
1884 			start_agno = 0;
1885 	}
1886 
1887 	/*
1888 	 * If we have already hit the ceiling of inode blocks then clear
1889 	 * ok_alloc so we scan all available agi structures for a free
1890 	 * inode.
1891 	 *
1892 	 * Read rough value of mp->m_icount by percpu_counter_read_positive,
1893 	 * which will sacrifice the preciseness but improve the performance.
1894 	 */
1895 	if (igeo->maxicount &&
1896 	    percpu_counter_read_positive(&mp->m_icount) + igeo->ialloc_inos
1897 							> igeo->maxicount) {
1898 		ok_alloc = false;
1899 	}
1900 
1901 	/*
1902 	 * If we are near to ENOSPC, we want to prefer allocation from AGs that
1903 	 * have free inodes in them rather than use up free space allocating new
1904 	 * inode chunks. Hence we turn off allocation for the first non-blocking
1905 	 * pass through the AGs if we are near ENOSPC to consume free inodes
1906 	 * that we can immediately allocate, but then we allow allocation on the
1907 	 * second pass if we fail to find an AG with free inodes in it.
1908 	 */
1909 	if (percpu_counter_read_positive(&mp->m_fdblocks) <
1910 			mp->m_low_space[XFS_LOWSP_1_PCNT]) {
1911 		ok_alloc = false;
1912 		low_space = true;
1913 	}
1914 
1915 	/*
1916 	 * Loop until we find an allocation group that either has free inodes
1917 	 * or in which we can allocate some inodes.  Iterate through the
1918 	 * allocation groups upward, wrapping at the end.
1919 	 */
1920 	flags = XFS_ALLOC_FLAG_TRYLOCK;
1921 retry:
1922 	for_each_perag_wrap_at(mp, start_agno, mp->m_maxagi, agno, pag) {
1923 		if (xfs_dialloc_good_ag(pag, *tpp, mode, flags, ok_alloc)) {
1924 			error = xfs_dialloc_try_ag(pag, tpp, parent,
1925 					&ino, ok_alloc);
1926 			if (error != -EAGAIN)
1927 				break;
1928 			error = 0;
1929 		}
1930 
1931 		if (xfs_is_shutdown(mp)) {
1932 			error = -EFSCORRUPTED;
1933 			break;
1934 		}
1935 	}
1936 	if (pag)
1937 		xfs_perag_rele(pag);
1938 	if (error)
1939 		return error;
1940 	if (ino == NULLFSINO) {
1941 		if (flags) {
1942 			flags = 0;
1943 			if (low_space)
1944 				ok_alloc = true;
1945 			goto retry;
1946 		}
1947 		return -ENOSPC;
1948 	}
1949 
1950 	/*
1951 	 * Protect against obviously corrupt allocation btree records. Later
1952 	 * xfs_iget checks will catch re-allocation of other active in-memory
1953 	 * and on-disk inodes. If we don't catch reallocating the parent inode
1954 	 * here we will deadlock in xfs_iget() so we have to do these checks
1955 	 * first.
1956 	 */
1957 	if (ino == parent || !xfs_verify_dir_ino(mp, ino)) {
1958 		xfs_alert(mp, "Allocated a known in-use inode 0x%llx!", ino);
1959 		xfs_agno_mark_sick(mp, XFS_INO_TO_AGNO(mp, ino),
1960 				XFS_SICK_AG_INOBT);
1961 		return -EFSCORRUPTED;
1962 	}
1963 
1964 	*new_ino = ino;
1965 	return 0;
1966 }
1967 
1968 /*
1969  * Free the blocks of an inode chunk. We must consider that the inode chunk
1970  * might be sparse and only free the regions that are allocated as part of the
1971  * chunk.
1972  */
1973 static int
1974 xfs_difree_inode_chunk(
1975 	struct xfs_trans		*tp,
1976 	xfs_agnumber_t			agno,
1977 	struct xfs_inobt_rec_incore	*rec)
1978 {
1979 	struct xfs_mount		*mp = tp->t_mountp;
1980 	xfs_agblock_t			sagbno = XFS_AGINO_TO_AGBNO(mp,
1981 							rec->ir_startino);
1982 	int				startidx, endidx;
1983 	int				nextbit;
1984 	xfs_agblock_t			agbno;
1985 	int				contigblk;
1986 	DECLARE_BITMAP(holemask, XFS_INOBT_HOLEMASK_BITS);
1987 
1988 	if (!xfs_inobt_issparse(rec->ir_holemask)) {
1989 		/* not sparse, calculate extent info directly */
1990 		return xfs_free_extent_later(tp,
1991 				XFS_AGB_TO_FSB(mp, agno, sagbno),
1992 				M_IGEO(mp)->ialloc_blks, &XFS_RMAP_OINFO_INODES,
1993 				XFS_AG_RESV_NONE, 0);
1994 	}
1995 
1996 	/* holemask is only 16-bits (fits in an unsigned long) */
1997 	ASSERT(sizeof(rec->ir_holemask) <= sizeof(holemask[0]));
1998 	holemask[0] = rec->ir_holemask;
1999 
2000 	/*
2001 	 * Find contiguous ranges of zeroes (i.e., allocated regions) in the
2002 	 * holemask and convert the start/end index of each range to an extent.
2003 	 * We start with the start and end index both pointing at the first 0 in
2004 	 * the mask.
2005 	 */
2006 	startidx = endidx = find_first_zero_bit(holemask,
2007 						XFS_INOBT_HOLEMASK_BITS);
2008 	nextbit = startidx + 1;
2009 	while (startidx < XFS_INOBT_HOLEMASK_BITS) {
2010 		int error;
2011 
2012 		nextbit = find_next_zero_bit(holemask, XFS_INOBT_HOLEMASK_BITS,
2013 					     nextbit);
2014 		/*
2015 		 * If the next zero bit is contiguous, update the end index of
2016 		 * the current range and continue.
2017 		 */
2018 		if (nextbit != XFS_INOBT_HOLEMASK_BITS &&
2019 		    nextbit == endidx + 1) {
2020 			endidx = nextbit;
2021 			goto next;
2022 		}
2023 
2024 		/*
2025 		 * nextbit is not contiguous with the current end index. Convert
2026 		 * the current start/end to an extent and add it to the free
2027 		 * list.
2028 		 */
2029 		agbno = sagbno + (startidx * XFS_INODES_PER_HOLEMASK_BIT) /
2030 				  mp->m_sb.sb_inopblock;
2031 		contigblk = ((endidx - startidx + 1) *
2032 			     XFS_INODES_PER_HOLEMASK_BIT) /
2033 			    mp->m_sb.sb_inopblock;
2034 
2035 		ASSERT(agbno % mp->m_sb.sb_spino_align == 0);
2036 		ASSERT(contigblk % mp->m_sb.sb_spino_align == 0);
2037 		error = xfs_free_extent_later(tp,
2038 				XFS_AGB_TO_FSB(mp, agno, agbno), contigblk,
2039 				&XFS_RMAP_OINFO_INODES, XFS_AG_RESV_NONE, 0);
2040 		if (error)
2041 			return error;
2042 
2043 		/* reset range to current bit and carry on... */
2044 		startidx = endidx = nextbit;
2045 
2046 next:
2047 		nextbit++;
2048 	}
2049 	return 0;
2050 }
2051 
2052 STATIC int
2053 xfs_difree_inobt(
2054 	struct xfs_perag		*pag,
2055 	struct xfs_trans		*tp,
2056 	struct xfs_buf			*agbp,
2057 	xfs_agino_t			agino,
2058 	struct xfs_icluster		*xic,
2059 	struct xfs_inobt_rec_incore	*orec)
2060 {
2061 	struct xfs_mount		*mp = pag->pag_mount;
2062 	struct xfs_agi			*agi = agbp->b_addr;
2063 	struct xfs_btree_cur		*cur;
2064 	struct xfs_inobt_rec_incore	rec;
2065 	int				ilen;
2066 	int				error;
2067 	int				i;
2068 	int				off;
2069 
2070 	ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
2071 	ASSERT(XFS_AGINO_TO_AGBNO(mp, agino) < be32_to_cpu(agi->agi_length));
2072 
2073 	/*
2074 	 * Initialize the cursor.
2075 	 */
2076 	cur = xfs_inobt_init_cursor(pag, tp, agbp);
2077 
2078 	error = xfs_check_agi_freecount(cur);
2079 	if (error)
2080 		goto error0;
2081 
2082 	/*
2083 	 * Look for the entry describing this inode.
2084 	 */
2085 	if ((error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i))) {
2086 		xfs_warn(mp, "%s: xfs_inobt_lookup() returned error %d.",
2087 			__func__, error);
2088 		goto error0;
2089 	}
2090 	if (XFS_IS_CORRUPT(mp, i != 1)) {
2091 		xfs_btree_mark_sick(cur);
2092 		error = -EFSCORRUPTED;
2093 		goto error0;
2094 	}
2095 	error = xfs_inobt_get_rec(cur, &rec, &i);
2096 	if (error) {
2097 		xfs_warn(mp, "%s: xfs_inobt_get_rec() returned error %d.",
2098 			__func__, error);
2099 		goto error0;
2100 	}
2101 	if (XFS_IS_CORRUPT(mp, i != 1)) {
2102 		xfs_btree_mark_sick(cur);
2103 		error = -EFSCORRUPTED;
2104 		goto error0;
2105 	}
2106 	/*
2107 	 * Get the offset in the inode chunk.
2108 	 */
2109 	off = agino - rec.ir_startino;
2110 	ASSERT(off >= 0 && off < XFS_INODES_PER_CHUNK);
2111 	ASSERT(!(rec.ir_free & XFS_INOBT_MASK(off)));
2112 	/*
2113 	 * Mark the inode free & increment the count.
2114 	 */
2115 	rec.ir_free |= XFS_INOBT_MASK(off);
2116 	rec.ir_freecount++;
2117 
2118 	/*
2119 	 * When an inode chunk is free, it becomes eligible for removal. Don't
2120 	 * remove the chunk if the block size is large enough for multiple inode
2121 	 * chunks (that might not be free).
2122 	 */
2123 	if (!xfs_has_ikeep(mp) && rec.ir_free == XFS_INOBT_ALL_FREE &&
2124 	    mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) {
2125 		xic->deleted = true;
2126 		xic->first_ino = XFS_AGINO_TO_INO(mp, pag->pag_agno,
2127 				rec.ir_startino);
2128 		xic->alloc = xfs_inobt_irec_to_allocmask(&rec);
2129 
2130 		/*
2131 		 * Remove the inode cluster from the AGI B+Tree, adjust the
2132 		 * AGI and Superblock inode counts, and mark the disk space
2133 		 * to be freed when the transaction is committed.
2134 		 */
2135 		ilen = rec.ir_freecount;
2136 		be32_add_cpu(&agi->agi_count, -ilen);
2137 		be32_add_cpu(&agi->agi_freecount, -(ilen - 1));
2138 		xfs_ialloc_log_agi(tp, agbp, XFS_AGI_COUNT | XFS_AGI_FREECOUNT);
2139 		pag->pagi_freecount -= ilen - 1;
2140 		pag->pagi_count -= ilen;
2141 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
2142 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
2143 
2144 		if ((error = xfs_btree_delete(cur, &i))) {
2145 			xfs_warn(mp, "%s: xfs_btree_delete returned error %d.",
2146 				__func__, error);
2147 			goto error0;
2148 		}
2149 
2150 		error = xfs_difree_inode_chunk(tp, pag->pag_agno, &rec);
2151 		if (error)
2152 			goto error0;
2153 	} else {
2154 		xic->deleted = false;
2155 
2156 		error = xfs_inobt_update(cur, &rec);
2157 		if (error) {
2158 			xfs_warn(mp, "%s: xfs_inobt_update returned error %d.",
2159 				__func__, error);
2160 			goto error0;
2161 		}
2162 
2163 		/*
2164 		 * Change the inode free counts and log the ag/sb changes.
2165 		 */
2166 		be32_add_cpu(&agi->agi_freecount, 1);
2167 		xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
2168 		pag->pagi_freecount++;
2169 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, 1);
2170 	}
2171 
2172 	error = xfs_check_agi_freecount(cur);
2173 	if (error)
2174 		goto error0;
2175 
2176 	*orec = rec;
2177 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
2178 	return 0;
2179 
2180 error0:
2181 	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
2182 	return error;
2183 }
2184 
2185 /*
2186  * Free an inode in the free inode btree.
2187  */
2188 STATIC int
2189 xfs_difree_finobt(
2190 	struct xfs_perag		*pag,
2191 	struct xfs_trans		*tp,
2192 	struct xfs_buf			*agbp,
2193 	xfs_agino_t			agino,
2194 	struct xfs_inobt_rec_incore	*ibtrec) /* inobt record */
2195 {
2196 	struct xfs_mount		*mp = pag->pag_mount;
2197 	struct xfs_btree_cur		*cur;
2198 	struct xfs_inobt_rec_incore	rec;
2199 	int				offset = agino - ibtrec->ir_startino;
2200 	int				error;
2201 	int				i;
2202 
2203 	cur = xfs_finobt_init_cursor(pag, tp, agbp);
2204 
2205 	error = xfs_inobt_lookup(cur, ibtrec->ir_startino, XFS_LOOKUP_EQ, &i);
2206 	if (error)
2207 		goto error;
2208 	if (i == 0) {
2209 		/*
2210 		 * If the record does not exist in the finobt, we must have just
2211 		 * freed an inode in a previously fully allocated chunk. If not,
2212 		 * something is out of sync.
2213 		 */
2214 		if (XFS_IS_CORRUPT(mp, ibtrec->ir_freecount != 1)) {
2215 			xfs_btree_mark_sick(cur);
2216 			error = -EFSCORRUPTED;
2217 			goto error;
2218 		}
2219 
2220 		error = xfs_inobt_insert_rec(cur, ibtrec->ir_holemask,
2221 					     ibtrec->ir_count,
2222 					     ibtrec->ir_freecount,
2223 					     ibtrec->ir_free, &i);
2224 		if (error)
2225 			goto error;
2226 		ASSERT(i == 1);
2227 
2228 		goto out;
2229 	}
2230 
2231 	/*
2232 	 * Read and update the existing record. We could just copy the ibtrec
2233 	 * across here, but that would defeat the purpose of having redundant
2234 	 * metadata. By making the modifications independently, we can catch
2235 	 * corruptions that we wouldn't see if we just copied from one record
2236 	 * to another.
2237 	 */
2238 	error = xfs_inobt_get_rec(cur, &rec, &i);
2239 	if (error)
2240 		goto error;
2241 	if (XFS_IS_CORRUPT(mp, i != 1)) {
2242 		xfs_btree_mark_sick(cur);
2243 		error = -EFSCORRUPTED;
2244 		goto error;
2245 	}
2246 
2247 	rec.ir_free |= XFS_INOBT_MASK(offset);
2248 	rec.ir_freecount++;
2249 
2250 	if (XFS_IS_CORRUPT(mp,
2251 			   rec.ir_free != ibtrec->ir_free ||
2252 			   rec.ir_freecount != ibtrec->ir_freecount)) {
2253 		xfs_btree_mark_sick(cur);
2254 		error = -EFSCORRUPTED;
2255 		goto error;
2256 	}
2257 
2258 	/*
2259 	 * The content of inobt records should always match between the inobt
2260 	 * and finobt. The lifecycle of records in the finobt is different from
2261 	 * the inobt in that the finobt only tracks records with at least one
2262 	 * free inode. Hence, if all of the inodes are free and we aren't
2263 	 * keeping inode chunks permanently on disk, remove the record.
2264 	 * Otherwise, update the record with the new information.
2265 	 *
2266 	 * Note that we currently can't free chunks when the block size is large
2267 	 * enough for multiple chunks. Leave the finobt record to remain in sync
2268 	 * with the inobt.
2269 	 */
2270 	if (!xfs_has_ikeep(mp) && rec.ir_free == XFS_INOBT_ALL_FREE &&
2271 	    mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) {
2272 		error = xfs_btree_delete(cur, &i);
2273 		if (error)
2274 			goto error;
2275 		ASSERT(i == 1);
2276 	} else {
2277 		error = xfs_inobt_update(cur, &rec);
2278 		if (error)
2279 			goto error;
2280 	}
2281 
2282 out:
2283 	error = xfs_check_agi_freecount(cur);
2284 	if (error)
2285 		goto error;
2286 
2287 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
2288 	return 0;
2289 
2290 error:
2291 	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
2292 	return error;
2293 }
2294 
2295 /*
2296  * Free disk inode.  Carefully avoids touching the incore inode, all
2297  * manipulations incore are the caller's responsibility.
2298  * The on-disk inode is not changed by this operation, only the
2299  * btree (free inode mask) is changed.
2300  */
2301 int
2302 xfs_difree(
2303 	struct xfs_trans	*tp,
2304 	struct xfs_perag	*pag,
2305 	xfs_ino_t		inode,
2306 	struct xfs_icluster	*xic)
2307 {
2308 	/* REFERENCED */
2309 	xfs_agblock_t		agbno;	/* block number containing inode */
2310 	struct xfs_buf		*agbp;	/* buffer for allocation group header */
2311 	xfs_agino_t		agino;	/* allocation group inode number */
2312 	int			error;	/* error return value */
2313 	struct xfs_mount	*mp = tp->t_mountp;
2314 	struct xfs_inobt_rec_incore rec;/* btree record */
2315 
2316 	/*
2317 	 * Break up inode number into its components.
2318 	 */
2319 	if (pag->pag_agno != XFS_INO_TO_AGNO(mp, inode)) {
2320 		xfs_warn(mp, "%s: agno != pag->pag_agno (%d != %d).",
2321 			__func__, XFS_INO_TO_AGNO(mp, inode), pag->pag_agno);
2322 		ASSERT(0);
2323 		return -EINVAL;
2324 	}
2325 	agino = XFS_INO_TO_AGINO(mp, inode);
2326 	if (inode != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino))  {
2327 		xfs_warn(mp, "%s: inode != XFS_AGINO_TO_INO() (%llu != %llu).",
2328 			__func__, (unsigned long long)inode,
2329 			(unsigned long long)XFS_AGINO_TO_INO(mp, pag->pag_agno, agino));
2330 		ASSERT(0);
2331 		return -EINVAL;
2332 	}
2333 	agbno = XFS_AGINO_TO_AGBNO(mp, agino);
2334 	if (agbno >= mp->m_sb.sb_agblocks)  {
2335 		xfs_warn(mp, "%s: agbno >= mp->m_sb.sb_agblocks (%d >= %d).",
2336 			__func__, agbno, mp->m_sb.sb_agblocks);
2337 		ASSERT(0);
2338 		return -EINVAL;
2339 	}
2340 	/*
2341 	 * Get the allocation group header.
2342 	 */
2343 	error = xfs_ialloc_read_agi(pag, tp, 0, &agbp);
2344 	if (error) {
2345 		xfs_warn(mp, "%s: xfs_ialloc_read_agi() returned error %d.",
2346 			__func__, error);
2347 		return error;
2348 	}
2349 
2350 	/*
2351 	 * Fix up the inode allocation btree.
2352 	 */
2353 	error = xfs_difree_inobt(pag, tp, agbp, agino, xic, &rec);
2354 	if (error)
2355 		goto error0;
2356 
2357 	/*
2358 	 * Fix up the free inode btree.
2359 	 */
2360 	if (xfs_has_finobt(mp)) {
2361 		error = xfs_difree_finobt(pag, tp, agbp, agino, &rec);
2362 		if (error)
2363 			goto error0;
2364 	}
2365 
2366 	return 0;
2367 
2368 error0:
2369 	return error;
2370 }
2371 
2372 STATIC int
2373 xfs_imap_lookup(
2374 	struct xfs_perag	*pag,
2375 	struct xfs_trans	*tp,
2376 	xfs_agino_t		agino,
2377 	xfs_agblock_t		agbno,
2378 	xfs_agblock_t		*chunk_agbno,
2379 	xfs_agblock_t		*offset_agbno,
2380 	int			flags)
2381 {
2382 	struct xfs_mount	*mp = pag->pag_mount;
2383 	struct xfs_inobt_rec_incore rec;
2384 	struct xfs_btree_cur	*cur;
2385 	struct xfs_buf		*agbp;
2386 	int			error;
2387 	int			i;
2388 
2389 	error = xfs_ialloc_read_agi(pag, tp, 0, &agbp);
2390 	if (error) {
2391 		xfs_alert(mp,
2392 			"%s: xfs_ialloc_read_agi() returned error %d, agno %d",
2393 			__func__, error, pag->pag_agno);
2394 		return error;
2395 	}
2396 
2397 	/*
2398 	 * Lookup the inode record for the given agino. If the record cannot be
2399 	 * found, then it's an invalid inode number and we should abort. Once
2400 	 * we have a record, we need to ensure it contains the inode number
2401 	 * we are looking up.
2402 	 */
2403 	cur = xfs_inobt_init_cursor(pag, tp, agbp);
2404 	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i);
2405 	if (!error) {
2406 		if (i)
2407 			error = xfs_inobt_get_rec(cur, &rec, &i);
2408 		if (!error && i == 0)
2409 			error = -EINVAL;
2410 	}
2411 
2412 	xfs_trans_brelse(tp, agbp);
2413 	xfs_btree_del_cursor(cur, error);
2414 	if (error)
2415 		return error;
2416 
2417 	/* check that the returned record contains the required inode */
2418 	if (rec.ir_startino > agino ||
2419 	    rec.ir_startino + M_IGEO(mp)->ialloc_inos <= agino)
2420 		return -EINVAL;
2421 
2422 	/* for untrusted inodes check it is allocated first */
2423 	if ((flags & XFS_IGET_UNTRUSTED) &&
2424 	    (rec.ir_free & XFS_INOBT_MASK(agino - rec.ir_startino)))
2425 		return -EINVAL;
2426 
2427 	*chunk_agbno = XFS_AGINO_TO_AGBNO(mp, rec.ir_startino);
2428 	*offset_agbno = agbno - *chunk_agbno;
2429 	return 0;
2430 }
2431 
2432 /*
2433  * Return the location of the inode in imap, for mapping it into a buffer.
2434  */
2435 int
2436 xfs_imap(
2437 	struct xfs_perag	*pag,
2438 	struct xfs_trans	*tp,
2439 	xfs_ino_t		ino,	/* inode to locate */
2440 	struct xfs_imap		*imap,	/* location map structure */
2441 	uint			flags)	/* flags for inode btree lookup */
2442 {
2443 	struct xfs_mount	*mp = pag->pag_mount;
2444 	xfs_agblock_t		agbno;	/* block number of inode in the alloc group */
2445 	xfs_agino_t		agino;	/* inode number within alloc group */
2446 	xfs_agblock_t		chunk_agbno;	/* first block in inode chunk */
2447 	xfs_agblock_t		cluster_agbno;	/* first block in inode cluster */
2448 	int			error;	/* error code */
2449 	int			offset;	/* index of inode in its buffer */
2450 	xfs_agblock_t		offset_agbno;	/* blks from chunk start to inode */
2451 
2452 	ASSERT(ino != NULLFSINO);
2453 
2454 	/*
2455 	 * Split up the inode number into its parts.
2456 	 */
2457 	agino = XFS_INO_TO_AGINO(mp, ino);
2458 	agbno = XFS_AGINO_TO_AGBNO(mp, agino);
2459 	if (agbno >= mp->m_sb.sb_agblocks ||
2460 	    ino != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2461 		error = -EINVAL;
2462 #ifdef DEBUG
2463 		/*
2464 		 * Don't output diagnostic information for untrusted inodes
2465 		 * as they can be invalid without implying corruption.
2466 		 */
2467 		if (flags & XFS_IGET_UNTRUSTED)
2468 			return error;
2469 		if (agbno >= mp->m_sb.sb_agblocks) {
2470 			xfs_alert(mp,
2471 		"%s: agbno (0x%llx) >= mp->m_sb.sb_agblocks (0x%lx)",
2472 				__func__, (unsigned long long)agbno,
2473 				(unsigned long)mp->m_sb.sb_agblocks);
2474 		}
2475 		if (ino != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2476 			xfs_alert(mp,
2477 		"%s: ino (0x%llx) != XFS_AGINO_TO_INO() (0x%llx)",
2478 				__func__, ino,
2479 				XFS_AGINO_TO_INO(mp, pag->pag_agno, agino));
2480 		}
2481 		xfs_stack_trace();
2482 #endif /* DEBUG */
2483 		return error;
2484 	}
2485 
2486 	/*
2487 	 * For bulkstat and handle lookups, we have an untrusted inode number
2488 	 * that we have to verify is valid. We cannot do this just by reading
2489 	 * the inode buffer as it may have been unlinked and removed leaving
2490 	 * inodes in stale state on disk. Hence we have to do a btree lookup
2491 	 * in all cases where an untrusted inode number is passed.
2492 	 */
2493 	if (flags & XFS_IGET_UNTRUSTED) {
2494 		error = xfs_imap_lookup(pag, tp, agino, agbno,
2495 					&chunk_agbno, &offset_agbno, flags);
2496 		if (error)
2497 			return error;
2498 		goto out_map;
2499 	}
2500 
2501 	/*
2502 	 * If the inode cluster size is the same as the blocksize or
2503 	 * smaller we get to the buffer by simple arithmetics.
2504 	 */
2505 	if (M_IGEO(mp)->blocks_per_cluster == 1) {
2506 		offset = XFS_INO_TO_OFFSET(mp, ino);
2507 		ASSERT(offset < mp->m_sb.sb_inopblock);
2508 
2509 		imap->im_blkno = XFS_AGB_TO_DADDR(mp, pag->pag_agno, agbno);
2510 		imap->im_len = XFS_FSB_TO_BB(mp, 1);
2511 		imap->im_boffset = (unsigned short)(offset <<
2512 							mp->m_sb.sb_inodelog);
2513 		return 0;
2514 	}
2515 
2516 	/*
2517 	 * If the inode chunks are aligned then use simple maths to
2518 	 * find the location. Otherwise we have to do a btree
2519 	 * lookup to find the location.
2520 	 */
2521 	if (M_IGEO(mp)->inoalign_mask) {
2522 		offset_agbno = agbno & M_IGEO(mp)->inoalign_mask;
2523 		chunk_agbno = agbno - offset_agbno;
2524 	} else {
2525 		error = xfs_imap_lookup(pag, tp, agino, agbno,
2526 					&chunk_agbno, &offset_agbno, flags);
2527 		if (error)
2528 			return error;
2529 	}
2530 
2531 out_map:
2532 	ASSERT(agbno >= chunk_agbno);
2533 	cluster_agbno = chunk_agbno +
2534 		((offset_agbno / M_IGEO(mp)->blocks_per_cluster) *
2535 		 M_IGEO(mp)->blocks_per_cluster);
2536 	offset = ((agbno - cluster_agbno) * mp->m_sb.sb_inopblock) +
2537 		XFS_INO_TO_OFFSET(mp, ino);
2538 
2539 	imap->im_blkno = XFS_AGB_TO_DADDR(mp, pag->pag_agno, cluster_agbno);
2540 	imap->im_len = XFS_FSB_TO_BB(mp, M_IGEO(mp)->blocks_per_cluster);
2541 	imap->im_boffset = (unsigned short)(offset << mp->m_sb.sb_inodelog);
2542 
2543 	/*
2544 	 * If the inode number maps to a block outside the bounds
2545 	 * of the file system then return NULL rather than calling
2546 	 * read_buf and panicing when we get an error from the
2547 	 * driver.
2548 	 */
2549 	if ((imap->im_blkno + imap->im_len) >
2550 	    XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks)) {
2551 		xfs_alert(mp,
2552 	"%s: (im_blkno (0x%llx) + im_len (0x%llx)) > sb_dblocks (0x%llx)",
2553 			__func__, (unsigned long long) imap->im_blkno,
2554 			(unsigned long long) imap->im_len,
2555 			XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks));
2556 		return -EINVAL;
2557 	}
2558 	return 0;
2559 }
2560 
2561 /*
2562  * Log specified fields for the ag hdr (inode section). The growth of the agi
2563  * structure over time requires that we interpret the buffer as two logical
2564  * regions delineated by the end of the unlinked list. This is due to the size
2565  * of the hash table and its location in the middle of the agi.
2566  *
2567  * For example, a request to log a field before agi_unlinked and a field after
2568  * agi_unlinked could cause us to log the entire hash table and use an excessive
2569  * amount of log space. To avoid this behavior, log the region up through
2570  * agi_unlinked in one call and the region after agi_unlinked through the end of
2571  * the structure in another.
2572  */
2573 void
2574 xfs_ialloc_log_agi(
2575 	struct xfs_trans	*tp,
2576 	struct xfs_buf		*bp,
2577 	uint32_t		fields)
2578 {
2579 	int			first;		/* first byte number */
2580 	int			last;		/* last byte number */
2581 	static const short	offsets[] = {	/* field starting offsets */
2582 					/* keep in sync with bit definitions */
2583 		offsetof(xfs_agi_t, agi_magicnum),
2584 		offsetof(xfs_agi_t, agi_versionnum),
2585 		offsetof(xfs_agi_t, agi_seqno),
2586 		offsetof(xfs_agi_t, agi_length),
2587 		offsetof(xfs_agi_t, agi_count),
2588 		offsetof(xfs_agi_t, agi_root),
2589 		offsetof(xfs_agi_t, agi_level),
2590 		offsetof(xfs_agi_t, agi_freecount),
2591 		offsetof(xfs_agi_t, agi_newino),
2592 		offsetof(xfs_agi_t, agi_dirino),
2593 		offsetof(xfs_agi_t, agi_unlinked),
2594 		offsetof(xfs_agi_t, agi_free_root),
2595 		offsetof(xfs_agi_t, agi_free_level),
2596 		offsetof(xfs_agi_t, agi_iblocks),
2597 		sizeof(xfs_agi_t)
2598 	};
2599 #ifdef DEBUG
2600 	struct xfs_agi		*agi = bp->b_addr;
2601 
2602 	ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
2603 #endif
2604 
2605 	/*
2606 	 * Compute byte offsets for the first and last fields in the first
2607 	 * region and log the agi buffer. This only logs up through
2608 	 * agi_unlinked.
2609 	 */
2610 	if (fields & XFS_AGI_ALL_BITS_R1) {
2611 		xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R1,
2612 				  &first, &last);
2613 		xfs_trans_log_buf(tp, bp, first, last);
2614 	}
2615 
2616 	/*
2617 	 * Mask off the bits in the first region and calculate the first and
2618 	 * last field offsets for any bits in the second region.
2619 	 */
2620 	fields &= ~XFS_AGI_ALL_BITS_R1;
2621 	if (fields) {
2622 		xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R2,
2623 				  &first, &last);
2624 		xfs_trans_log_buf(tp, bp, first, last);
2625 	}
2626 }
2627 
2628 static xfs_failaddr_t
2629 xfs_agi_verify(
2630 	struct xfs_buf		*bp)
2631 {
2632 	struct xfs_mount	*mp = bp->b_mount;
2633 	struct xfs_agi		*agi = bp->b_addr;
2634 	xfs_failaddr_t		fa;
2635 	uint32_t		agi_seqno = be32_to_cpu(agi->agi_seqno);
2636 	uint32_t		agi_length = be32_to_cpu(agi->agi_length);
2637 	int			i;
2638 
2639 	if (xfs_has_crc(mp)) {
2640 		if (!uuid_equal(&agi->agi_uuid, &mp->m_sb.sb_meta_uuid))
2641 			return __this_address;
2642 		if (!xfs_log_check_lsn(mp, be64_to_cpu(agi->agi_lsn)))
2643 			return __this_address;
2644 	}
2645 
2646 	/*
2647 	 * Validate the magic number of the agi block.
2648 	 */
2649 	if (!xfs_verify_magic(bp, agi->agi_magicnum))
2650 		return __this_address;
2651 	if (!XFS_AGI_GOOD_VERSION(be32_to_cpu(agi->agi_versionnum)))
2652 		return __this_address;
2653 
2654 	fa = xfs_validate_ag_length(bp, agi_seqno, agi_length);
2655 	if (fa)
2656 		return fa;
2657 
2658 	if (be32_to_cpu(agi->agi_level) < 1 ||
2659 	    be32_to_cpu(agi->agi_level) > M_IGEO(mp)->inobt_maxlevels)
2660 		return __this_address;
2661 
2662 	if (xfs_has_finobt(mp) &&
2663 	    (be32_to_cpu(agi->agi_free_level) < 1 ||
2664 	     be32_to_cpu(agi->agi_free_level) > M_IGEO(mp)->inobt_maxlevels))
2665 		return __this_address;
2666 
2667 	for (i = 0; i < XFS_AGI_UNLINKED_BUCKETS; i++) {
2668 		if (agi->agi_unlinked[i] == cpu_to_be32(NULLAGINO))
2669 			continue;
2670 		if (!xfs_verify_ino(mp, be32_to_cpu(agi->agi_unlinked[i])))
2671 			return __this_address;
2672 	}
2673 
2674 	return NULL;
2675 }
2676 
2677 static void
2678 xfs_agi_read_verify(
2679 	struct xfs_buf	*bp)
2680 {
2681 	struct xfs_mount *mp = bp->b_mount;
2682 	xfs_failaddr_t	fa;
2683 
2684 	if (xfs_has_crc(mp) &&
2685 	    !xfs_buf_verify_cksum(bp, XFS_AGI_CRC_OFF))
2686 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
2687 	else {
2688 		fa = xfs_agi_verify(bp);
2689 		if (XFS_TEST_ERROR(fa, mp, XFS_ERRTAG_IALLOC_READ_AGI))
2690 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2691 	}
2692 }
2693 
2694 static void
2695 xfs_agi_write_verify(
2696 	struct xfs_buf	*bp)
2697 {
2698 	struct xfs_mount	*mp = bp->b_mount;
2699 	struct xfs_buf_log_item	*bip = bp->b_log_item;
2700 	struct xfs_agi		*agi = bp->b_addr;
2701 	xfs_failaddr_t		fa;
2702 
2703 	fa = xfs_agi_verify(bp);
2704 	if (fa) {
2705 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2706 		return;
2707 	}
2708 
2709 	if (!xfs_has_crc(mp))
2710 		return;
2711 
2712 	if (bip)
2713 		agi->agi_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2714 	xfs_buf_update_cksum(bp, XFS_AGI_CRC_OFF);
2715 }
2716 
2717 const struct xfs_buf_ops xfs_agi_buf_ops = {
2718 	.name = "xfs_agi",
2719 	.magic = { cpu_to_be32(XFS_AGI_MAGIC), cpu_to_be32(XFS_AGI_MAGIC) },
2720 	.verify_read = xfs_agi_read_verify,
2721 	.verify_write = xfs_agi_write_verify,
2722 	.verify_struct = xfs_agi_verify,
2723 };
2724 
2725 /*
2726  * Read in the allocation group header (inode allocation section)
2727  */
2728 int
2729 xfs_read_agi(
2730 	struct xfs_perag	*pag,
2731 	struct xfs_trans	*tp,
2732 	xfs_buf_flags_t		flags,
2733 	struct xfs_buf		**agibpp)
2734 {
2735 	struct xfs_mount	*mp = pag->pag_mount;
2736 	int			error;
2737 
2738 	trace_xfs_read_agi(pag->pag_mount, pag->pag_agno);
2739 
2740 	error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
2741 			XFS_AG_DADDR(mp, pag->pag_agno, XFS_AGI_DADDR(mp)),
2742 			XFS_FSS_TO_BB(mp, 1), flags, agibpp, &xfs_agi_buf_ops);
2743 	if (xfs_metadata_is_sick(error))
2744 		xfs_ag_mark_sick(pag, XFS_SICK_AG_AGI);
2745 	if (error)
2746 		return error;
2747 	if (tp)
2748 		xfs_trans_buf_set_type(tp, *agibpp, XFS_BLFT_AGI_BUF);
2749 
2750 	xfs_buf_set_ref(*agibpp, XFS_AGI_REF);
2751 	return 0;
2752 }
2753 
2754 /*
2755  * Read in the agi and initialise the per-ag data. If the caller supplies a
2756  * @agibpp, return the locked AGI buffer to them, otherwise release it.
2757  */
2758 int
2759 xfs_ialloc_read_agi(
2760 	struct xfs_perag	*pag,
2761 	struct xfs_trans	*tp,
2762 	int			flags,
2763 	struct xfs_buf		**agibpp)
2764 {
2765 	struct xfs_buf		*agibp;
2766 	struct xfs_agi		*agi;
2767 	int			error;
2768 
2769 	trace_xfs_ialloc_read_agi(pag->pag_mount, pag->pag_agno);
2770 
2771 	error = xfs_read_agi(pag, tp,
2772 			(flags & XFS_IALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
2773 			&agibp);
2774 	if (error)
2775 		return error;
2776 
2777 	agi = agibp->b_addr;
2778 	if (!xfs_perag_initialised_agi(pag)) {
2779 		pag->pagi_freecount = be32_to_cpu(agi->agi_freecount);
2780 		pag->pagi_count = be32_to_cpu(agi->agi_count);
2781 		set_bit(XFS_AGSTATE_AGI_INIT, &pag->pag_opstate);
2782 	}
2783 
2784 	/*
2785 	 * It's possible for these to be out of sync if
2786 	 * we are in the middle of a forced shutdown.
2787 	 */
2788 	ASSERT(pag->pagi_freecount == be32_to_cpu(agi->agi_freecount) ||
2789 		xfs_is_shutdown(pag->pag_mount));
2790 	if (agibpp)
2791 		*agibpp = agibp;
2792 	else
2793 		xfs_trans_brelse(tp, agibp);
2794 	return 0;
2795 }
2796 
2797 /* How many inodes are backed by inode clusters ondisk? */
2798 STATIC int
2799 xfs_ialloc_count_ondisk(
2800 	struct xfs_btree_cur		*cur,
2801 	xfs_agino_t			low,
2802 	xfs_agino_t			high,
2803 	unsigned int			*allocated)
2804 {
2805 	struct xfs_inobt_rec_incore	irec;
2806 	unsigned int			ret = 0;
2807 	int				has_record;
2808 	int				error;
2809 
2810 	error = xfs_inobt_lookup(cur, low, XFS_LOOKUP_LE, &has_record);
2811 	if (error)
2812 		return error;
2813 
2814 	while (has_record) {
2815 		unsigned int		i, hole_idx;
2816 
2817 		error = xfs_inobt_get_rec(cur, &irec, &has_record);
2818 		if (error)
2819 			return error;
2820 		if (irec.ir_startino > high)
2821 			break;
2822 
2823 		for (i = 0; i < XFS_INODES_PER_CHUNK; i++) {
2824 			if (irec.ir_startino + i < low)
2825 				continue;
2826 			if (irec.ir_startino + i > high)
2827 				break;
2828 
2829 			hole_idx = i / XFS_INODES_PER_HOLEMASK_BIT;
2830 			if (!(irec.ir_holemask & (1U << hole_idx)))
2831 				ret++;
2832 		}
2833 
2834 		error = xfs_btree_increment(cur, 0, &has_record);
2835 		if (error)
2836 			return error;
2837 	}
2838 
2839 	*allocated = ret;
2840 	return 0;
2841 }
2842 
2843 /* Is there an inode record covering a given extent? */
2844 int
2845 xfs_ialloc_has_inodes_at_extent(
2846 	struct xfs_btree_cur	*cur,
2847 	xfs_agblock_t		bno,
2848 	xfs_extlen_t		len,
2849 	enum xbtree_recpacking	*outcome)
2850 {
2851 	xfs_agino_t		agino;
2852 	xfs_agino_t		last_agino;
2853 	unsigned int		allocated;
2854 	int			error;
2855 
2856 	agino = XFS_AGB_TO_AGINO(cur->bc_mp, bno);
2857 	last_agino = XFS_AGB_TO_AGINO(cur->bc_mp, bno + len) - 1;
2858 
2859 	error = xfs_ialloc_count_ondisk(cur, agino, last_agino, &allocated);
2860 	if (error)
2861 		return error;
2862 
2863 	if (allocated == 0)
2864 		*outcome = XBTREE_RECPACKING_EMPTY;
2865 	else if (allocated == last_agino - agino + 1)
2866 		*outcome = XBTREE_RECPACKING_FULL;
2867 	else
2868 		*outcome = XBTREE_RECPACKING_SPARSE;
2869 	return 0;
2870 }
2871 
2872 struct xfs_ialloc_count_inodes {
2873 	xfs_agino_t			count;
2874 	xfs_agino_t			freecount;
2875 };
2876 
2877 /* Record inode counts across all inobt records. */
2878 STATIC int
2879 xfs_ialloc_count_inodes_rec(
2880 	struct xfs_btree_cur		*cur,
2881 	const union xfs_btree_rec	*rec,
2882 	void				*priv)
2883 {
2884 	struct xfs_inobt_rec_incore	irec;
2885 	struct xfs_ialloc_count_inodes	*ci = priv;
2886 	xfs_failaddr_t			fa;
2887 
2888 	xfs_inobt_btrec_to_irec(cur->bc_mp, rec, &irec);
2889 	fa = xfs_inobt_check_irec(cur->bc_ag.pag, &irec);
2890 	if (fa)
2891 		return xfs_inobt_complain_bad_rec(cur, fa, &irec);
2892 
2893 	ci->count += irec.ir_count;
2894 	ci->freecount += irec.ir_freecount;
2895 
2896 	return 0;
2897 }
2898 
2899 /* Count allocated and free inodes under an inobt. */
2900 int
2901 xfs_ialloc_count_inodes(
2902 	struct xfs_btree_cur		*cur,
2903 	xfs_agino_t			*count,
2904 	xfs_agino_t			*freecount)
2905 {
2906 	struct xfs_ialloc_count_inodes	ci = {0};
2907 	int				error;
2908 
2909 	ASSERT(xfs_btree_is_ino(cur->bc_ops));
2910 	error = xfs_btree_query_all(cur, xfs_ialloc_count_inodes_rec, &ci);
2911 	if (error)
2912 		return error;
2913 
2914 	*count = ci.count;
2915 	*freecount = ci.freecount;
2916 	return 0;
2917 }
2918 
2919 /*
2920  * Initialize inode-related geometry information.
2921  *
2922  * Compute the inode btree min and max levels and set maxicount.
2923  *
2924  * Set the inode cluster size.  This may still be overridden by the file
2925  * system block size if it is larger than the chosen cluster size.
2926  *
2927  * For v5 filesystems, scale the cluster size with the inode size to keep a
2928  * constant ratio of inode per cluster buffer, but only if mkfs has set the
2929  * inode alignment value appropriately for larger cluster sizes.
2930  *
2931  * Then compute the inode cluster alignment information.
2932  */
2933 void
2934 xfs_ialloc_setup_geometry(
2935 	struct xfs_mount	*mp)
2936 {
2937 	struct xfs_sb		*sbp = &mp->m_sb;
2938 	struct xfs_ino_geometry	*igeo = M_IGEO(mp);
2939 	uint64_t		icount;
2940 	uint			inodes;
2941 
2942 	igeo->new_diflags2 = 0;
2943 	if (xfs_has_bigtime(mp))
2944 		igeo->new_diflags2 |= XFS_DIFLAG2_BIGTIME;
2945 	if (xfs_has_large_extent_counts(mp))
2946 		igeo->new_diflags2 |= XFS_DIFLAG2_NREXT64;
2947 
2948 	/* Compute inode btree geometry. */
2949 	igeo->agino_log = sbp->sb_inopblog + sbp->sb_agblklog;
2950 	igeo->inobt_mxr[0] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, 1);
2951 	igeo->inobt_mxr[1] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, 0);
2952 	igeo->inobt_mnr[0] = igeo->inobt_mxr[0] / 2;
2953 	igeo->inobt_mnr[1] = igeo->inobt_mxr[1] / 2;
2954 
2955 	igeo->ialloc_inos = max_t(uint16_t, XFS_INODES_PER_CHUNK,
2956 			sbp->sb_inopblock);
2957 	igeo->ialloc_blks = igeo->ialloc_inos >> sbp->sb_inopblog;
2958 
2959 	if (sbp->sb_spino_align)
2960 		igeo->ialloc_min_blks = sbp->sb_spino_align;
2961 	else
2962 		igeo->ialloc_min_blks = igeo->ialloc_blks;
2963 
2964 	/* Compute and fill in value of m_ino_geo.inobt_maxlevels. */
2965 	inodes = (1LL << XFS_INO_AGINO_BITS(mp)) >> XFS_INODES_PER_CHUNK_LOG;
2966 	igeo->inobt_maxlevels = xfs_btree_compute_maxlevels(igeo->inobt_mnr,
2967 			inodes);
2968 	ASSERT(igeo->inobt_maxlevels <= xfs_iallocbt_maxlevels_ondisk());
2969 
2970 	/*
2971 	 * Set the maximum inode count for this filesystem, being careful not
2972 	 * to use obviously garbage sb_inopblog/sb_inopblock values.  Regular
2973 	 * users should never get here due to failing sb verification, but
2974 	 * certain users (xfs_db) need to be usable even with corrupt metadata.
2975 	 */
2976 	if (sbp->sb_imax_pct && igeo->ialloc_blks) {
2977 		/*
2978 		 * Make sure the maximum inode count is a multiple
2979 		 * of the units we allocate inodes in.
2980 		 */
2981 		icount = sbp->sb_dblocks * sbp->sb_imax_pct;
2982 		do_div(icount, 100);
2983 		do_div(icount, igeo->ialloc_blks);
2984 		igeo->maxicount = XFS_FSB_TO_INO(mp,
2985 				icount * igeo->ialloc_blks);
2986 	} else {
2987 		igeo->maxicount = 0;
2988 	}
2989 
2990 	/*
2991 	 * Compute the desired size of an inode cluster buffer size, which
2992 	 * starts at 8K and (on v5 filesystems) scales up with larger inode
2993 	 * sizes.
2994 	 *
2995 	 * Preserve the desired inode cluster size because the sparse inodes
2996 	 * feature uses that desired size (not the actual size) to compute the
2997 	 * sparse inode alignment.  The mount code validates this value, so we
2998 	 * cannot change the behavior.
2999 	 */
3000 	igeo->inode_cluster_size_raw = XFS_INODE_BIG_CLUSTER_SIZE;
3001 	if (xfs_has_v3inodes(mp)) {
3002 		int	new_size = igeo->inode_cluster_size_raw;
3003 
3004 		new_size *= mp->m_sb.sb_inodesize / XFS_DINODE_MIN_SIZE;
3005 		if (mp->m_sb.sb_inoalignmt >= XFS_B_TO_FSBT(mp, new_size))
3006 			igeo->inode_cluster_size_raw = new_size;
3007 	}
3008 
3009 	/* Calculate inode cluster ratios. */
3010 	if (igeo->inode_cluster_size_raw > mp->m_sb.sb_blocksize)
3011 		igeo->blocks_per_cluster = XFS_B_TO_FSBT(mp,
3012 				igeo->inode_cluster_size_raw);
3013 	else
3014 		igeo->blocks_per_cluster = 1;
3015 	igeo->inode_cluster_size = XFS_FSB_TO_B(mp, igeo->blocks_per_cluster);
3016 	igeo->inodes_per_cluster = XFS_FSB_TO_INO(mp, igeo->blocks_per_cluster);
3017 
3018 	/* Calculate inode cluster alignment. */
3019 	if (xfs_has_align(mp) &&
3020 	    mp->m_sb.sb_inoalignmt >= igeo->blocks_per_cluster)
3021 		igeo->cluster_align = mp->m_sb.sb_inoalignmt;
3022 	else
3023 		igeo->cluster_align = 1;
3024 	igeo->inoalign_mask = igeo->cluster_align - 1;
3025 	igeo->cluster_align_inodes = XFS_FSB_TO_INO(mp, igeo->cluster_align);
3026 
3027 	/*
3028 	 * If we are using stripe alignment, check whether
3029 	 * the stripe unit is a multiple of the inode alignment
3030 	 */
3031 	if (mp->m_dalign && igeo->inoalign_mask &&
3032 	    !(mp->m_dalign & igeo->inoalign_mask))
3033 		igeo->ialloc_align = mp->m_dalign;
3034 	else
3035 		igeo->ialloc_align = 0;
3036 }
3037 
3038 /* Compute the location of the root directory inode that is laid out by mkfs. */
3039 xfs_ino_t
3040 xfs_ialloc_calc_rootino(
3041 	struct xfs_mount	*mp,
3042 	int			sunit)
3043 {
3044 	struct xfs_ino_geometry	*igeo = M_IGEO(mp);
3045 	xfs_agblock_t		first_bno;
3046 
3047 	/*
3048 	 * Pre-calculate the geometry of AG 0.  We know what it looks like
3049 	 * because libxfs knows how to create allocation groups now.
3050 	 *
3051 	 * first_bno is the first block in which mkfs could possibly have
3052 	 * allocated the root directory inode, once we factor in the metadata
3053 	 * that mkfs formats before it.  Namely, the four AG headers...
3054 	 */
3055 	first_bno = howmany(4 * mp->m_sb.sb_sectsize, mp->m_sb.sb_blocksize);
3056 
3057 	/* ...the two free space btree roots... */
3058 	first_bno += 2;
3059 
3060 	/* ...the inode btree root... */
3061 	first_bno += 1;
3062 
3063 	/* ...the initial AGFL... */
3064 	first_bno += xfs_alloc_min_freelist(mp, NULL);
3065 
3066 	/* ...the free inode btree root... */
3067 	if (xfs_has_finobt(mp))
3068 		first_bno++;
3069 
3070 	/* ...the reverse mapping btree root... */
3071 	if (xfs_has_rmapbt(mp))
3072 		first_bno++;
3073 
3074 	/* ...the reference count btree... */
3075 	if (xfs_has_reflink(mp))
3076 		first_bno++;
3077 
3078 	/*
3079 	 * ...and the log, if it is allocated in the first allocation group.
3080 	 *
3081 	 * This can happen with filesystems that only have a single
3082 	 * allocation group, or very odd geometries created by old mkfs
3083 	 * versions on very small filesystems.
3084 	 */
3085 	if (xfs_ag_contains_log(mp, 0))
3086 		 first_bno += mp->m_sb.sb_logblocks;
3087 
3088 	/*
3089 	 * Now round first_bno up to whatever allocation alignment is given
3090 	 * by the filesystem or was passed in.
3091 	 */
3092 	if (xfs_has_dalign(mp) && igeo->ialloc_align > 0)
3093 		first_bno = roundup(first_bno, sunit);
3094 	else if (xfs_has_align(mp) &&
3095 			mp->m_sb.sb_inoalignmt > 1)
3096 		first_bno = roundup(first_bno, mp->m_sb.sb_inoalignmt);
3097 
3098 	return XFS_AGINO_TO_INO(mp, 0, XFS_AGB_TO_AGINO(mp, first_bno));
3099 }
3100 
3101 /*
3102  * Ensure there are not sparse inode clusters that cross the new EOAG.
3103  *
3104  * This is a no-op for non-spinode filesystems since clusters are always fully
3105  * allocated and checking the bnobt suffices.  However, a spinode filesystem
3106  * could have a record where the upper inodes are free blocks.  If those blocks
3107  * were removed from the filesystem, the inode record would extend beyond EOAG,
3108  * which will be flagged as corruption.
3109  */
3110 int
3111 xfs_ialloc_check_shrink(
3112 	struct xfs_perag	*pag,
3113 	struct xfs_trans	*tp,
3114 	struct xfs_buf		*agibp,
3115 	xfs_agblock_t		new_length)
3116 {
3117 	struct xfs_inobt_rec_incore rec;
3118 	struct xfs_btree_cur	*cur;
3119 	xfs_agino_t		agino;
3120 	int			has;
3121 	int			error;
3122 
3123 	if (!xfs_has_sparseinodes(pag->pag_mount))
3124 		return 0;
3125 
3126 	cur = xfs_inobt_init_cursor(pag, tp, agibp);
3127 
3128 	/* Look up the inobt record that would correspond to the new EOFS. */
3129 	agino = XFS_AGB_TO_AGINO(pag->pag_mount, new_length);
3130 	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &has);
3131 	if (error || !has)
3132 		goto out;
3133 
3134 	error = xfs_inobt_get_rec(cur, &rec, &has);
3135 	if (error)
3136 		goto out;
3137 
3138 	if (!has) {
3139 		xfs_ag_mark_sick(pag, XFS_SICK_AG_INOBT);
3140 		error = -EFSCORRUPTED;
3141 		goto out;
3142 	}
3143 
3144 	/* If the record covers inodes that would be beyond EOFS, bail out. */
3145 	if (rec.ir_startino + XFS_INODES_PER_CHUNK > agino) {
3146 		error = -ENOSPC;
3147 		goto out;
3148 	}
3149 out:
3150 	xfs_btree_del_cursor(cur, error);
3151 	return error;
3152 }
3153