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, xfs_lookup_t: 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, b: fbuf, o: 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, irec: &rec, stat: &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, irec: rec, stat: &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, irec: rec, stat: &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	* Allocate an inode using the inobt-only algorithm.
1062	*/
1063	STATIC int
1064	xfs_dialloc_ag_inobt(
1065	struct xfs_perag *pag,
1066	struct xfs_trans *tp,
1067	struct xfs_buf *agbp,
1068	xfs_ino_t parent,
1069	xfs_ino_t *inop)
1070	{
1071	struct xfs_mount *mp = tp->t_mountp;
1072	struct xfs_agi *agi = agbp->b_addr;
1073	xfs_agnumber_t pagno = XFS_INO_TO_AGNO(mp, parent);
1074	xfs_agino_t pagino = XFS_INO_TO_AGINO(mp, parent);
1075	struct xfs_btree_cur *cur, *tcur;
1076	struct xfs_inobt_rec_incore rec, trec;
1077	xfs_ino_t ino;
1078	int error;
1079	int offset;
1080	int i, j;
1081	int searchdistance = 10;
1082
1083	ASSERT(xfs_perag_initialised_agi(pag));
1084	ASSERT(xfs_perag_allows_inodes(pag));
1085	ASSERT(pag->pagi_freecount > 0);
1086
1087	restart_pagno:
1088	cur = xfs_inobt_init_cursor(pag, tp, agbp);
1089	/*
1090	* If pagino is 0 (this is the root inode allocation) use newino.
1091	* This must work because we've just allocated some.
1092	*/
1093	if (!pagino)
1094	pagino = be32_to_cpu(agi->agi_newino);
1095
1096	error = xfs_check_agi_freecount(cur);
1097	if (error)
1098	goto error0;
1099
1100	/*
1101	* If in the same AG as the parent, try to get near the parent.
1102	*/
1103	if (pagno == pag->pag_agno) {
1104	int doneleft; /* done, to the left */
1105	int doneright; /* done, to the right */
1106
1107	error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i);
1108	if (error)
1109	goto error0;
1110	if (XFS_IS_CORRUPT(mp, i != 1)) {
1111	xfs_btree_mark_sick(cur);
1112	error = -EFSCORRUPTED;
1113	goto error0;
1114	}
1115
1116	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &j);
1117	if (error)
1118	goto error0;
1119	if (XFS_IS_CORRUPT(mp, j != 1)) {
1120	xfs_btree_mark_sick(cur);
1121	error = -EFSCORRUPTED;
1122	goto error0;
1123	}
1124
1125	if (rec.ir_freecount > 0) {
1126	/*
1127	* Found a free inode in the same chunk
1128	* as the parent, done.
1129	*/
1130	goto alloc_inode;
1131	}
1132
1133
1134	/*
1135	* In the same AG as parent, but parent's chunk is full.
1136	*/
1137
1138	/* duplicate the cursor, search left & right simultaneously */
1139	error = xfs_btree_dup_cursor(cur, ncur: &tcur);
1140	if (error)
1141	goto error0;
1142
1143	/*
1144	* Skip to last blocks looked up if same parent inode.
1145	*/
1146	if (pagino != NULLAGINO &&
1147	pag->pagl_pagino == pagino &&
1148	pag->pagl_leftrec != NULLAGINO &&
1149	pag->pagl_rightrec != NULLAGINO) {
1150	error = xfs_ialloc_get_rec(tcur, pag->pagl_leftrec,
1151	&trec, &doneleft);
1152	if (error)
1153	goto error1;
1154
1155	error = xfs_ialloc_get_rec(cur, pag->pagl_rightrec,
1156	&rec, &doneright);
1157	if (error)
1158	goto error1;
1159	} else {
1160	/* search left with tcur, back up 1 record */
1161	error = xfs_ialloc_next_rec(tcur, &trec, &doneleft, 1);
1162	if (error)
1163	goto error1;
1164
1165	/* search right with cur, go forward 1 record. */
1166	error = xfs_ialloc_next_rec(cur, &rec, &doneright, 0);
1167	if (error)
1168	goto error1;
1169	}
1170
1171	/*
1172	* Loop until we find an inode chunk with a free inode.
1173	*/
1174	while (--searchdistance > 0 && (!doneleft || !doneright)) {
1175	int useleft; /* using left inode chunk this time */
1176
1177	/* figure out the closer block if both are valid. */
1178	if (!doneleft && !doneright) {
1179	useleft = pagino -
1180	(trec.ir_startino + XFS_INODES_PER_CHUNK - 1) <
1181	rec.ir_startino - pagino;
1182	} else {
1183	useleft = !doneleft;
1184	}
1185
1186	/* free inodes to the left? */
1187	if (useleft && trec.ir_freecount) {
1188	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1189	cur = tcur;
1190
1191	pag->pagl_leftrec = trec.ir_startino;
1192	pag->pagl_rightrec = rec.ir_startino;
1193	pag->pagl_pagino = pagino;
1194	rec = trec;
1195	goto alloc_inode;
1196	}
1197
1198	/* free inodes to the right? */
1199	if (!useleft && rec.ir_freecount) {
1200	xfs_btree_del_cursor(cur: tcur, XFS_BTREE_NOERROR);
1201
1202	pag->pagl_leftrec = trec.ir_startino;
1203	pag->pagl_rightrec = rec.ir_startino;
1204	pag->pagl_pagino = pagino;
1205	goto alloc_inode;
1206	}
1207
1208	/* get next record to check */
1209	if (useleft) {
1210	error = xfs_ialloc_next_rec(tcur, &trec,
1211	&doneleft, 1);
1212	} else {
1213	error = xfs_ialloc_next_rec(cur, &rec,
1214	&doneright, 0);
1215	}
1216	if (error)
1217	goto error1;
1218	}
1219
1220	if (searchdistance <= 0) {
1221	/*
1222	* Not in range - save last search
1223	* location and allocate a new inode
1224	*/
1225	xfs_btree_del_cursor(cur: tcur, XFS_BTREE_NOERROR);
1226	pag->pagl_leftrec = trec.ir_startino;
1227	pag->pagl_rightrec = rec.ir_startino;
1228	pag->pagl_pagino = pagino;
1229
1230	} else {
1231	/*
1232	* We've reached the end of the btree. because
1233	* we are only searching a small chunk of the
1234	* btree each search, there is obviously free
1235	* inodes closer to the parent inode than we
1236	* are now. restart the search again.
1237	*/
1238	pag->pagl_pagino = NULLAGINO;
1239	pag->pagl_leftrec = NULLAGINO;
1240	pag->pagl_rightrec = NULLAGINO;
1241	xfs_btree_del_cursor(cur: tcur, XFS_BTREE_NOERROR);
1242	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1243	goto restart_pagno;
1244	}
1245	}
1246
1247	/*
1248	* In a different AG from the parent.
1249	* See if the most recently allocated block has any free.
1250	*/
1251	if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
1252	error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
1253	XFS_LOOKUP_EQ, &i);
1254	if (error)
1255	goto error0;
1256
1257	if (i == 1) {
1258	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &j);
1259	if (error)
1260	goto error0;
1261
1262	if (j == 1 && rec.ir_freecount > 0) {
1263	/*
1264	* The last chunk allocated in the group
1265	* still has a free inode.
1266	*/
1267	goto alloc_inode;
1268	}
1269	}
1270	}
1271
1272	/*
1273	* None left in the last group, search the whole AG
1274	*/
1275	error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
1276	if (error)
1277	goto error0;
1278	if (XFS_IS_CORRUPT(mp, i != 1)) {
1279	xfs_btree_mark_sick(cur);
1280	error = -EFSCORRUPTED;
1281	goto error0;
1282	}
1283
1284	for (;;) {
1285	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &i);
1286	if (error)
1287	goto error0;
1288	if (XFS_IS_CORRUPT(mp, i != 1)) {
1289	xfs_btree_mark_sick(cur);
1290	error = -EFSCORRUPTED;
1291	goto error0;
1292	}
1293	if (rec.ir_freecount > 0)
1294	break;
1295	error = xfs_btree_increment(cur, 0, &i);
1296	if (error)
1297	goto error0;
1298	if (XFS_IS_CORRUPT(mp, i != 1)) {
1299	xfs_btree_mark_sick(cur);
1300	error = -EFSCORRUPTED;
1301	goto error0;
1302	}
1303	}
1304
1305	alloc_inode:
1306	offset = xfs_inobt_first_free_inode(&rec);
1307	ASSERT(offset >= 0);
1308	ASSERT(offset < XFS_INODES_PER_CHUNK);
1309	ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
1310	XFS_INODES_PER_CHUNK) == 0);
1311	ino = XFS_AGINO_TO_INO(mp, pag->pag_agno, rec.ir_startino + offset);
1312	rec.ir_free &= ~XFS_INOBT_MASK(offset);
1313	rec.ir_freecount--;
1314	error = xfs_inobt_update(cur, &rec);
1315	if (error)
1316	goto error0;
1317	be32_add_cpu(&agi->agi_freecount, -1);
1318	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1319	pag->pagi_freecount--;
1320
1321	error = xfs_check_agi_freecount(cur);
1322	if (error)
1323	goto error0;
1324
1325	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1326	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
1327	*inop = ino;
1328	return 0;
1329	error1:
1330	xfs_btree_del_cursor(cur: tcur, XFS_BTREE_ERROR);
1331	error0:
1332	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1333	return error;
1334	}
1335
1336	/*
1337	* Use the free inode btree to allocate an inode based on distance from the
1338	* parent. Note that the provided cursor may be deleted and replaced.
1339	*/
1340	STATIC int
1341	xfs_dialloc_ag_finobt_near(
1342	xfs_agino_t pagino,
1343	struct xfs_btree_cur **ocur,
1344	struct xfs_inobt_rec_incore *rec)
1345	{
1346	struct xfs_btree_cur *lcur = *ocur; /* left search cursor */
1347	struct xfs_btree_cur *rcur; /* right search cursor */
1348	struct xfs_inobt_rec_incore rrec;
1349	int error;
1350	int i, j;
1351
1352	error = xfs_inobt_lookup(lcur, pagino, XFS_LOOKUP_LE, &i);
1353	if (error)
1354	return error;
1355
1356	if (i == 1) {
1357	error = xfs_inobt_get_rec(cur: lcur, irec: rec, stat: &i);
1358	if (error)
1359	return error;
1360	if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1)) {
1361	xfs_btree_mark_sick(cur: lcur);
1362	return -EFSCORRUPTED;
1363	}
1364
1365	/*
1366	* See if we've landed in the parent inode record. The finobt
1367	* only tracks chunks with at least one free inode, so record
1368	* existence is enough.
1369	*/
1370	if (pagino >= rec->ir_startino &&
1371	pagino < (rec->ir_startino + XFS_INODES_PER_CHUNK))
1372	return 0;
1373	}
1374
1375	error = xfs_btree_dup_cursor(cur: lcur, ncur: &rcur);
1376	if (error)
1377	return error;
1378
1379	error = xfs_inobt_lookup(rcur, pagino, XFS_LOOKUP_GE, &j);
1380	if (error)
1381	goto error_rcur;
1382	if (j == 1) {
1383	error = xfs_inobt_get_rec(cur: rcur, irec: &rrec, stat: &j);
1384	if (error)
1385	goto error_rcur;
1386	if (XFS_IS_CORRUPT(lcur->bc_mp, j != 1)) {
1387	xfs_btree_mark_sick(cur: lcur);
1388	error = -EFSCORRUPTED;
1389	goto error_rcur;
1390	}
1391	}
1392
1393	if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1 && j != 1)) {
1394	xfs_btree_mark_sick(cur: lcur);
1395	error = -EFSCORRUPTED;
1396	goto error_rcur;
1397	}
1398	if (i == 1 && j == 1) {
1399	/*
1400	* Both the left and right records are valid. Choose the closer
1401	* inode chunk to the target.
1402	*/
1403	if ((pagino - rec->ir_startino + XFS_INODES_PER_CHUNK - 1) >
1404	(rrec.ir_startino - pagino)) {
1405	*rec = rrec;
1406	xfs_btree_del_cursor(cur: lcur, XFS_BTREE_NOERROR);
1407	*ocur = rcur;
1408	} else {
1409	xfs_btree_del_cursor(cur: rcur, XFS_BTREE_NOERROR);
1410	}
1411	} else if (j == 1) {
1412	/* only the right record is valid */
1413	*rec = rrec;
1414	xfs_btree_del_cursor(cur: lcur, XFS_BTREE_NOERROR);
1415	*ocur = rcur;
1416	} else if (i == 1) {
1417	/* only the left record is valid */
1418	xfs_btree_del_cursor(cur: rcur, XFS_BTREE_NOERROR);
1419	}
1420
1421	return 0;
1422
1423	error_rcur:
1424	xfs_btree_del_cursor(cur: rcur, XFS_BTREE_ERROR);
1425	return error;
1426	}
1427
1428	/*
1429	* Use the free inode btree to find a free inode based on a newino hint. If
1430	* the hint is NULL, find the first free inode in the AG.
1431	*/
1432	STATIC int
1433	xfs_dialloc_ag_finobt_newino(
1434	struct xfs_agi *agi,
1435	struct xfs_btree_cur *cur,
1436	struct xfs_inobt_rec_incore *rec)
1437	{
1438	int error;
1439	int i;
1440
1441	if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
1442	error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
1443	XFS_LOOKUP_EQ, &i);
1444	if (error)
1445	return error;
1446	if (i == 1) {
1447	error = xfs_inobt_get_rec(cur, irec: rec, stat: &i);
1448	if (error)
1449	return error;
1450	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1451	xfs_btree_mark_sick(cur);
1452	return -EFSCORRUPTED;
1453	}
1454	return 0;
1455	}
1456	}
1457
1458	/*
1459	* Find the first inode available in the AG.
1460	*/
1461	error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
1462	if (error)
1463	return error;
1464	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1465	xfs_btree_mark_sick(cur);
1466	return -EFSCORRUPTED;
1467	}
1468
1469	error = xfs_inobt_get_rec(cur, irec: rec, stat: &i);
1470	if (error)
1471	return error;
1472	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1473	xfs_btree_mark_sick(cur);
1474	return -EFSCORRUPTED;
1475	}
1476
1477	return 0;
1478	}
1479
1480	/*
1481	* Update the inobt based on a modification made to the finobt. Also ensure that
1482	* the records from both trees are equivalent post-modification.
1483	*/
1484	STATIC int
1485	xfs_dialloc_ag_update_inobt(
1486	struct xfs_btree_cur *cur, /* inobt cursor */
1487	struct xfs_inobt_rec_incore *frec, /* finobt record */
1488	int offset) /* inode offset */
1489	{
1490	struct xfs_inobt_rec_incore rec;
1491	int error;
1492	int i;
1493
1494	error = xfs_inobt_lookup(cur, frec->ir_startino, XFS_LOOKUP_EQ, &i);
1495	if (error)
1496	return error;
1497	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1498	xfs_btree_mark_sick(cur);
1499	return -EFSCORRUPTED;
1500	}
1501
1502	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &i);
1503	if (error)
1504	return error;
1505	if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1506	xfs_btree_mark_sick(cur);
1507	return -EFSCORRUPTED;
1508	}
1509	ASSERT((XFS_AGINO_TO_OFFSET(cur->bc_mp, rec.ir_startino) %
1510	XFS_INODES_PER_CHUNK) == 0);
1511
1512	rec.ir_free &= ~XFS_INOBT_MASK(offset);
1513	rec.ir_freecount--;
1514
1515	if (XFS_IS_CORRUPT(cur->bc_mp,
1516	rec.ir_free != frec->ir_free ||
1517	rec.ir_freecount != frec->ir_freecount)) {
1518	xfs_btree_mark_sick(cur);
1519	return -EFSCORRUPTED;
1520	}
1521
1522	return xfs_inobt_update(cur, &rec);
1523	}
1524
1525	/*
1526	* Allocate an inode using the free inode btree, if available. Otherwise, fall
1527	* back to the inobt search algorithm.
1528	*
1529	* The caller selected an AG for us, and made sure that free inodes are
1530	* available.
1531	*/
1532	static int
1533	xfs_dialloc_ag(
1534	struct xfs_perag *pag,
1535	struct xfs_trans *tp,
1536	struct xfs_buf *agbp,
1537	xfs_ino_t parent,
1538	xfs_ino_t *inop)
1539	{
1540	struct xfs_mount *mp = tp->t_mountp;
1541	struct xfs_agi *agi = agbp->b_addr;
1542	xfs_agnumber_t pagno = XFS_INO_TO_AGNO(mp, parent);
1543	xfs_agino_t pagino = XFS_INO_TO_AGINO(mp, parent);
1544	struct xfs_btree_cur *cur; /* finobt cursor */
1545	struct xfs_btree_cur *icur; /* inobt cursor */
1546	struct xfs_inobt_rec_incore rec;
1547	xfs_ino_t ino;
1548	int error;
1549	int offset;
1550	int i;
1551
1552	if (!xfs_has_finobt(mp))
1553	return xfs_dialloc_ag_inobt(pag, tp, agbp, parent, inop);
1554
1555	/*
1556	* If pagino is 0 (this is the root inode allocation) use newino.
1557	* This must work because we've just allocated some.
1558	*/
1559	if (!pagino)
1560	pagino = be32_to_cpu(agi->agi_newino);
1561
1562	cur = xfs_finobt_init_cursor(pag, tp, agbp);
1563
1564	error = xfs_check_agi_freecount(cur);
1565	if (error)
1566	goto error_cur;
1567
1568	/*
1569	* The search algorithm depends on whether we're in the same AG as the
1570	* parent. If so, find the closest available inode to the parent. If
1571	* not, consider the agi hint or find the first free inode in the AG.
1572	*/
1573	if (pag->pag_agno == pagno)
1574	error = xfs_dialloc_ag_finobt_near(pagino, &cur, &rec);
1575	else
1576	error = xfs_dialloc_ag_finobt_newino(agi, cur, &rec);
1577	if (error)
1578	goto error_cur;
1579
1580	offset = xfs_inobt_first_free_inode(&rec);
1581	ASSERT(offset >= 0);
1582	ASSERT(offset < XFS_INODES_PER_CHUNK);
1583	ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
1584	XFS_INODES_PER_CHUNK) == 0);
1585	ino = XFS_AGINO_TO_INO(mp, pag->pag_agno, rec.ir_startino + offset);
1586
1587	/*
1588	* Modify or remove the finobt record.
1589	*/
1590	rec.ir_free &= ~XFS_INOBT_MASK(offset);
1591	rec.ir_freecount--;
1592	if (rec.ir_freecount)
1593	error = xfs_inobt_update(cur, &rec);
1594	else
1595	error = xfs_btree_delete(cur, &i);
1596	if (error)
1597	goto error_cur;
1598
1599	/*
1600	* The finobt has now been updated appropriately. We haven't updated the
1601	* agi and superblock yet, so we can create an inobt cursor and validate
1602	* the original freecount. If all is well, make the equivalent update to
1603	* the inobt using the finobt record and offset information.
1604	*/
1605	icur = xfs_inobt_init_cursor(pag, tp, agbp);
1606
1607	error = xfs_check_agi_freecount(icur);
1608	if (error)
1609	goto error_icur;
1610
1611	error = xfs_dialloc_ag_update_inobt(icur, &rec, offset);
1612	if (error)
1613	goto error_icur;
1614
1615	/*
1616	* Both trees have now been updated. We must update the perag and
1617	* superblock before we can check the freecount for each btree.
1618	*/
1619	be32_add_cpu(&agi->agi_freecount, -1);
1620	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1621	pag->pagi_freecount--;
1622
1623	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
1624
1625	error = xfs_check_agi_freecount(icur);
1626	if (error)
1627	goto error_icur;
1628	error = xfs_check_agi_freecount(cur);
1629	if (error)
1630	goto error_icur;
1631
1632	xfs_btree_del_cursor(cur: icur, XFS_BTREE_NOERROR);
1633	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1634	*inop = ino;
1635	return 0;
1636
1637	error_icur:
1638	xfs_btree_del_cursor(cur: icur, XFS_BTREE_ERROR);
1639	error_cur:
1640	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1641	return error;
1642	}
1643
1644	static int
1645	xfs_dialloc_roll(
1646	struct xfs_trans **tpp,
1647	struct xfs_buf *agibp)
1648	{
1649	struct xfs_trans *tp = *tpp;
1650	struct xfs_dquot_acct *dqinfo;
1651	int error;
1652
1653	/*
1654	* Hold to on to the agibp across the commit so no other allocation can
1655	* come in and take the free inodes we just allocated for our caller.
1656	*/
1657	xfs_trans_bhold(tp, agibp);
1658
1659	/*
1660	* We want the quota changes to be associated with the next transaction,
1661	* NOT this one. So, detach the dqinfo from this and attach it to the
1662	* next transaction.
1663	*/
1664	dqinfo = tp->t_dqinfo;
1665	tp->t_dqinfo = NULL;
1666
1667	error = xfs_trans_roll(&tp);
1668
1669	/* Re-attach the quota info that we detached from prev trx. */
1670	tp->t_dqinfo = dqinfo;
1671
1672	/*
1673	* Join the buffer even on commit error so that the buffer is released
1674	* when the caller cancels the transaction and doesn't have to handle
1675	* this error case specially.
1676	*/
1677	xfs_trans_bjoin(tp, agibp);
1678	*tpp = tp;
1679	return error;
1680	}
1681
1682	static bool
1683	xfs_dialloc_good_ag(
1684	struct xfs_perag *pag,
1685	struct xfs_trans *tp,
1686	umode_t mode,
1687	int flags,
1688	bool ok_alloc)
1689	{
1690	struct xfs_mount *mp = tp->t_mountp;
1691	xfs_extlen_t ineed;
1692	xfs_extlen_t longest = 0;
1693	int needspace;
1694	int error;
1695
1696	if (!pag)
1697	return false;
1698	if (!xfs_perag_allows_inodes(pag))
1699	return false;
1700
1701	if (!xfs_perag_initialised_agi(pag)) {
1702	error = xfs_ialloc_read_agi(pag, tp, NULL);
1703	if (error)
1704	return false;
1705	}
1706
1707	if (pag->pagi_freecount)
1708	return true;
1709	if (!ok_alloc)
1710	return false;
1711
1712	if (!xfs_perag_initialised_agf(pag)) {
1713	error = xfs_alloc_read_agf(pag, tp, flags, NULL);
1714	if (error)
1715	return false;
1716	}
1717
1718	/*
1719	* Check that there is enough free space for the file plus a chunk of
1720	* inodes if we need to allocate some. If this is the first pass across
1721	* the AGs, take into account the potential space needed for alignment
1722	* of inode chunks when checking the longest contiguous free space in
1723	* the AG - this prevents us from getting ENOSPC because we have free
1724	* space larger than ialloc_blks but alignment constraints prevent us
1725	* from using it.
1726	*
1727	* If we can't find an AG with space for full alignment slack to be
1728	* taken into account, we must be near ENOSPC in all AGs. Hence we
1729	* don't include alignment for the second pass and so if we fail
1730	* allocation due to alignment issues then it is most likely a real
1731	* ENOSPC condition.
1732	*
1733	* XXX(dgc): this calculation is now bogus thanks to the per-ag
1734	* reservations that xfs_alloc_fix_freelist() now does via
1735	* xfs_alloc_space_available(). When the AG fills up, pagf_freeblks will
1736	* be more than large enough for the check below to succeed, but
1737	* xfs_alloc_space_available() will fail because of the non-zero
1738	* metadata reservation and hence we won't actually be able to allocate
1739	* more inodes in this AG. We do soooo much unnecessary work near ENOSPC
1740	* because of this.
1741	*/
1742	ineed = M_IGEO(mp)->ialloc_min_blks;
1743	if (flags && ineed > 1)
1744	ineed += M_IGEO(mp)->cluster_align;
1745	longest = pag->pagf_longest;
1746	if (!longest)
1747	longest = pag->pagf_flcount > 0;
1748	needspace = S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode);
1749
1750	if (pag->pagf_freeblks < needspace + ineed || longest < ineed)
1751	return false;
1752	return true;
1753	}
1754
1755	static int
1756	xfs_dialloc_try_ag(
1757	struct xfs_perag *pag,
1758	struct xfs_trans **tpp,
1759	xfs_ino_t parent,
1760	xfs_ino_t *new_ino,
1761	bool ok_alloc)
1762	{
1763	struct xfs_buf *agbp;
1764	xfs_ino_t ino;
1765	int error;
1766
1767	/*
1768	* Then read in the AGI buffer and recheck with the AGI buffer
1769	* lock held.
1770	*/
1771	error = xfs_ialloc_read_agi(pag, tp: *tpp, agibpp: &agbp);
1772	if (error)
1773	return error;
1774
1775	if (!pag->pagi_freecount) {
1776	if (!ok_alloc) {
1777	error = -EAGAIN;
1778	goto out_release;
1779	}
1780
1781	error = xfs_ialloc_ag_alloc(pag, *tpp, agbp);
1782	if (error < 0)
1783	goto out_release;
1784
1785	/*
1786	* We successfully allocated space for an inode cluster in this
1787	* AG. Roll the transaction so that we can allocate one of the
1788	* new inodes.
1789	*/
1790	ASSERT(pag->pagi_freecount > 0);
1791	error = xfs_dialloc_roll(tpp, agibp: agbp);
1792	if (error)
1793	goto out_release;
1794	}
1795
1796	/* Allocate an inode in the found AG */
1797	error = xfs_dialloc_ag(pag, *tpp, agbp, parent, &ino);
1798	if (!error)
1799	*new_ino = ino;
1800	return error;
1801
1802	out_release:
1803	xfs_trans_brelse(*tpp, agbp);
1804	return error;
1805	}
1806
1807	/*
1808	* Allocate an on-disk inode.
1809	*
1810	* Mode is used to tell whether the new inode is a directory and hence where to
1811	* locate it. The on-disk inode that is allocated will be returned in @new_ino
1812	* on success, otherwise an error will be set to indicate the failure (e.g.
1813	* -ENOSPC).
1814	*/
1815	int
1816	xfs_dialloc(
1817	struct xfs_trans **tpp,
1818	xfs_ino_t parent,
1819	umode_t mode,
1820	xfs_ino_t *new_ino)
1821	{
1822	struct xfs_mount *mp = (*tpp)->t_mountp;
1823	xfs_agnumber_t agno;
1824	int error = 0;
1825	xfs_agnumber_t start_agno;
1826	struct xfs_perag *pag;
1827	struct xfs_ino_geometry *igeo = M_IGEO(mp);
1828	bool ok_alloc = true;
1829	bool low_space = false;
1830	int flags;
1831	xfs_ino_t ino = NULLFSINO;
1832
1833	/*
1834	* Directories, symlinks, and regular files frequently allocate at least
1835	* one block, so factor that potential expansion when we examine whether
1836	* an AG has enough space for file creation.
1837	*/
1838	if (S_ISDIR(mode))
1839	start_agno = (atomic_inc_return(&mp->m_agirotor) - 1) %
1840	mp->m_maxagi;
1841	else {
1842	start_agno = XFS_INO_TO_AGNO(mp, parent);
1843	if (start_agno >= mp->m_maxagi)
1844	start_agno = 0;
1845	}
1846
1847	/*
1848	* If we have already hit the ceiling of inode blocks then clear
1849	* ok_alloc so we scan all available agi structures for a free
1850	* inode.
1851	*
1852	* Read rough value of mp->m_icount by percpu_counter_read_positive,
1853	* which will sacrifice the preciseness but improve the performance.
1854	*/
1855	if (igeo->maxicount &&
1856	percpu_counter_read_positive(&mp->m_icount) + igeo->ialloc_inos
1857	> igeo->maxicount) {
1858	ok_alloc = false;
1859	}
1860
1861	/*
1862	* If we are near to ENOSPC, we want to prefer allocation from AGs that
1863	* have free inodes in them rather than use up free space allocating new
1864	* inode chunks. Hence we turn off allocation for the first non-blocking
1865	* pass through the AGs if we are near ENOSPC to consume free inodes
1866	* that we can immediately allocate, but then we allow allocation on the
1867	* second pass if we fail to find an AG with free inodes in it.
1868	*/
1869	if (percpu_counter_read_positive(&mp->m_fdblocks) <
1870	mp->m_low_space[XFS_LOWSP_1_PCNT]) {
1871	ok_alloc = false;
1872	low_space = true;
1873	}
1874
1875	/*
1876	* Loop until we find an allocation group that either has free inodes
1877	* or in which we can allocate some inodes. Iterate through the
1878	* allocation groups upward, wrapping at the end.
1879	*/
1880	flags = XFS_ALLOC_FLAG_TRYLOCK;
1881	retry:
1882	for_each_perag_wrap_at(mp, start_agno, mp->m_maxagi, agno, pag) {
1883	if (xfs_dialloc_good_ag(pag, *tpp, mode, flags, ok_alloc)) {
1884	error = xfs_dialloc_try_ag(pag, tpp, parent,
1885	&ino, ok_alloc);
1886	if (error != -EAGAIN)
1887	break;
1888	error = 0;
1889	}
1890
1891	if (xfs_is_shutdown(mp)) {
1892	error = -EFSCORRUPTED;
1893	break;
1894	}
1895	}
1896	if (pag)
1897	xfs_perag_rele(pag);
1898	if (error)
1899	return error;
1900	if (ino == NULLFSINO) {
1901	if (flags) {
1902	flags = 0;
1903	if (low_space)
1904	ok_alloc = true;
1905	goto retry;
1906	}
1907	return -ENOSPC;
1908	}
1909	*new_ino = ino;
1910	return 0;
1911	}
1912
1913	/*
1914	* Free the blocks of an inode chunk. We must consider that the inode chunk
1915	* might be sparse and only free the regions that are allocated as part of the
1916	* chunk.
1917	*/
1918	static int
1919	xfs_difree_inode_chunk(
1920	struct xfs_trans *tp,
1921	xfs_agnumber_t agno,
1922	struct xfs_inobt_rec_incore *rec)
1923	{
1924	struct xfs_mount *mp = tp->t_mountp;
1925	xfs_agblock_t sagbno = XFS_AGINO_TO_AGBNO(mp,
1926	rec->ir_startino);
1927	int startidx, endidx;
1928	int nextbit;
1929	xfs_agblock_t agbno;
1930	int contigblk;
1931	DECLARE_BITMAP(holemask, XFS_INOBT_HOLEMASK_BITS);
1932
1933	if (!xfs_inobt_issparse(rec->ir_holemask)) {
1934	/* not sparse, calculate extent info directly */
1935	return xfs_free_extent_later(tp,
1936	XFS_AGB_TO_FSB(mp, agno, sagbno),
1937	M_IGEO(mp)->ialloc_blks, &XFS_RMAP_OINFO_INODES,
1938	XFS_AG_RESV_NONE, false);
1939	}
1940
1941	/* holemask is only 16-bits (fits in an unsigned long) */
1942	ASSERT(sizeof(rec->ir_holemask) <= sizeof(holemask[0]));
1943	holemask[0] = rec->ir_holemask;
1944
1945	/*
1946	* Find contiguous ranges of zeroes (i.e., allocated regions) in the
1947	* holemask and convert the start/end index of each range to an extent.
1948	* We start with the start and end index both pointing at the first 0 in
1949	* the mask.
1950	*/
1951	startidx = endidx = find_first_zero_bit(holemask,
1952	XFS_INOBT_HOLEMASK_BITS);
1953	nextbit = startidx + 1;
1954	while (startidx < XFS_INOBT_HOLEMASK_BITS) {
1955	int error;
1956
1957	nextbit = find_next_zero_bit(holemask, XFS_INOBT_HOLEMASK_BITS,
1958	nextbit);
1959	/*
1960	* If the next zero bit is contiguous, update the end index of
1961	* the current range and continue.
1962	*/
1963	if (nextbit != XFS_INOBT_HOLEMASK_BITS &&
1964	nextbit == endidx + 1) {
1965	endidx = nextbit;
1966	goto next;
1967	}
1968
1969	/*
1970	* nextbit is not contiguous with the current end index. Convert
1971	* the current start/end to an extent and add it to the free
1972	* list.
1973	*/
1974	agbno = sagbno + (startidx * XFS_INODES_PER_HOLEMASK_BIT) /
1975	mp->m_sb.sb_inopblock;
1976	contigblk = ((endidx - startidx + 1) *
1977	XFS_INODES_PER_HOLEMASK_BIT) /
1978	mp->m_sb.sb_inopblock;
1979
1980	ASSERT(agbno % mp->m_sb.sb_spino_align == 0);
1981	ASSERT(contigblk % mp->m_sb.sb_spino_align == 0);
1982	error = xfs_free_extent_later(tp,
1983	XFS_AGB_TO_FSB(mp, agno, agbno), contigblk,
1984	&XFS_RMAP_OINFO_INODES, XFS_AG_RESV_NONE,
1985	false);
1986	if (error)
1987	return error;
1988
1989	/* reset range to current bit and carry on... */
1990	startidx = endidx = nextbit;
1991
1992	next:
1993	nextbit++;
1994	}
1995	return 0;
1996	}
1997
1998	STATIC int
1999	xfs_difree_inobt(
2000	struct xfs_perag *pag,
2001	struct xfs_trans *tp,
2002	struct xfs_buf *agbp,
2003	xfs_agino_t agino,
2004	struct xfs_icluster *xic,
2005	struct xfs_inobt_rec_incore *orec)
2006	{
2007	struct xfs_mount *mp = pag->pag_mount;
2008	struct xfs_agi *agi = agbp->b_addr;
2009	struct xfs_btree_cur *cur;
2010	struct xfs_inobt_rec_incore rec;
2011	int ilen;
2012	int error;
2013	int i;
2014	int off;
2015
2016	ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
2017	ASSERT(XFS_AGINO_TO_AGBNO(mp, agino) < be32_to_cpu(agi->agi_length));
2018
2019	/*
2020	* Initialize the cursor.
2021	*/
2022	cur = xfs_inobt_init_cursor(pag, tp, agbp);
2023
2024	error = xfs_check_agi_freecount(cur);
2025	if (error)
2026	goto error0;
2027
2028	/*
2029	* Look for the entry describing this inode.
2030	*/
2031	if ((error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i))) {
2032	xfs_warn(mp, "%s: xfs_inobt_lookup() returned error %d.",
2033	__func__, error);
2034	goto error0;
2035	}
2036	if (XFS_IS_CORRUPT(mp, i != 1)) {
2037	xfs_btree_mark_sick(cur);
2038	error = -EFSCORRUPTED;
2039	goto error0;
2040	}
2041	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &i);
2042	if (error) {
2043	xfs_warn(mp, "%s: xfs_inobt_get_rec() returned error %d.",
2044	__func__, error);
2045	goto error0;
2046	}
2047	if (XFS_IS_CORRUPT(mp, i != 1)) {
2048	xfs_btree_mark_sick(cur);
2049	error = -EFSCORRUPTED;
2050	goto error0;
2051	}
2052	/*
2053	* Get the offset in the inode chunk.
2054	*/
2055	off = agino - rec.ir_startino;
2056	ASSERT(off >= 0 && off < XFS_INODES_PER_CHUNK);
2057	ASSERT(!(rec.ir_free & XFS_INOBT_MASK(off)));
2058	/*
2059	* Mark the inode free & increment the count.
2060	*/
2061	rec.ir_free |= XFS_INOBT_MASK(off);
2062	rec.ir_freecount++;
2063
2064	/*
2065	* When an inode chunk is free, it becomes eligible for removal. Don't
2066	* remove the chunk if the block size is large enough for multiple inode
2067	* chunks (that might not be free).
2068	*/
2069	if (!xfs_has_ikeep(mp) && rec.ir_free == XFS_INOBT_ALL_FREE &&
2070	mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) {
2071	xic->deleted = true;
2072	xic->first_ino = XFS_AGINO_TO_INO(mp, pag->pag_agno,
2073	rec.ir_startino);
2074	xic->alloc = xfs_inobt_irec_to_allocmask(&rec);
2075
2076	/*
2077	* Remove the inode cluster from the AGI B+Tree, adjust the
2078	* AGI and Superblock inode counts, and mark the disk space
2079	* to be freed when the transaction is committed.
2080	*/
2081	ilen = rec.ir_freecount;
2082	be32_add_cpu(&agi->agi_count, -ilen);
2083	be32_add_cpu(&agi->agi_freecount, -(ilen - 1));
2084	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_COUNT | XFS_AGI_FREECOUNT);
2085	pag->pagi_freecount -= ilen - 1;
2086	pag->pagi_count -= ilen;
2087	xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
2088	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
2089
2090	if ((error = xfs_btree_delete(cur, &i))) {
2091	xfs_warn(mp, "%s: xfs_btree_delete returned error %d.",
2092	__func__, error);
2093	goto error0;
2094	}
2095
2096	error = xfs_difree_inode_chunk(tp, pag->pag_agno, &rec);
2097	if (error)
2098	goto error0;
2099	} else {
2100	xic->deleted = false;
2101
2102	error = xfs_inobt_update(cur, &rec);
2103	if (error) {
2104	xfs_warn(mp, "%s: xfs_inobt_update returned error %d.",
2105	__func__, error);
2106	goto error0;
2107	}
2108
2109	/*
2110	* Change the inode free counts and log the ag/sb changes.
2111	*/
2112	be32_add_cpu(&agi->agi_freecount, 1);
2113	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
2114	pag->pagi_freecount++;
2115	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, 1);
2116	}
2117
2118	error = xfs_check_agi_freecount(cur);
2119	if (error)
2120	goto error0;
2121
2122	*orec = rec;
2123	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
2124	return 0;
2125
2126	error0:
2127	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
2128	return error;
2129	}
2130
2131	/*
2132	* Free an inode in the free inode btree.
2133	*/
2134	STATIC int
2135	xfs_difree_finobt(
2136	struct xfs_perag *pag,
2137	struct xfs_trans *tp,
2138	struct xfs_buf *agbp,
2139	xfs_agino_t agino,
2140	struct xfs_inobt_rec_incore *ibtrec) /* inobt record */
2141	{
2142	struct xfs_mount *mp = pag->pag_mount;
2143	struct xfs_btree_cur *cur;
2144	struct xfs_inobt_rec_incore rec;
2145	int offset = agino - ibtrec->ir_startino;
2146	int error;
2147	int i;
2148
2149	cur = xfs_finobt_init_cursor(pag, tp, agbp);
2150
2151	error = xfs_inobt_lookup(cur, ibtrec->ir_startino, XFS_LOOKUP_EQ, &i);
2152	if (error)
2153	goto error;
2154	if (i == 0) {
2155	/*
2156	* If the record does not exist in the finobt, we must have just
2157	* freed an inode in a previously fully allocated chunk. If not,
2158	* something is out of sync.
2159	*/
2160	if (XFS_IS_CORRUPT(mp, ibtrec->ir_freecount != 1)) {
2161	xfs_btree_mark_sick(cur);
2162	error = -EFSCORRUPTED;
2163	goto error;
2164	}
2165
2166	error = xfs_inobt_insert_rec(cur, ibtrec->ir_holemask,
2167	ibtrec->ir_count,
2168	ibtrec->ir_freecount,
2169	ibtrec->ir_free, &i);
2170	if (error)
2171	goto error;
2172	ASSERT(i == 1);
2173
2174	goto out;
2175	}
2176
2177	/*
2178	* Read and update the existing record. We could just copy the ibtrec
2179	* across here, but that would defeat the purpose of having redundant
2180	* metadata. By making the modifications independently, we can catch
2181	* corruptions that we wouldn't see if we just copied from one record
2182	* to another.
2183	*/
2184	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &i);
2185	if (error)
2186	goto error;
2187	if (XFS_IS_CORRUPT(mp, i != 1)) {
2188	xfs_btree_mark_sick(cur);
2189	error = -EFSCORRUPTED;
2190	goto error;
2191	}
2192
2193	rec.ir_free |= XFS_INOBT_MASK(offset);
2194	rec.ir_freecount++;
2195
2196	if (XFS_IS_CORRUPT(mp,
2197	rec.ir_free != ibtrec->ir_free ||
2198	rec.ir_freecount != ibtrec->ir_freecount)) {
2199	xfs_btree_mark_sick(cur);
2200	error = -EFSCORRUPTED;
2201	goto error;
2202	}
2203
2204	/*
2205	* The content of inobt records should always match between the inobt
2206	* and finobt. The lifecycle of records in the finobt is different from
2207	* the inobt in that the finobt only tracks records with at least one
2208	* free inode. Hence, if all of the inodes are free and we aren't
2209	* keeping inode chunks permanently on disk, remove the record.
2210	* Otherwise, update the record with the new information.
2211	*
2212	* Note that we currently can't free chunks when the block size is large
2213	* enough for multiple chunks. Leave the finobt record to remain in sync
2214	* with the inobt.
2215	*/
2216	if (!xfs_has_ikeep(mp) && rec.ir_free == XFS_INOBT_ALL_FREE &&
2217	mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) {
2218	error = xfs_btree_delete(cur, &i);
2219	if (error)
2220	goto error;
2221	ASSERT(i == 1);
2222	} else {
2223	error = xfs_inobt_update(cur, &rec);
2224	if (error)
2225	goto error;
2226	}
2227
2228	out:
2229	error = xfs_check_agi_freecount(cur);
2230	if (error)
2231	goto error;
2232
2233	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
2234	return 0;
2235
2236	error:
2237	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
2238	return error;
2239	}
2240
2241	/*
2242	* Free disk inode. Carefully avoids touching the incore inode, all
2243	* manipulations incore are the caller's responsibility.
2244	* The on-disk inode is not changed by this operation, only the
2245	* btree (free inode mask) is changed.
2246	*/
2247	int
2248	xfs_difree(
2249	struct xfs_trans *tp,
2250	struct xfs_perag *pag,
2251	xfs_ino_t inode,
2252	struct xfs_icluster *xic)
2253	{
2254	/* REFERENCED */
2255	xfs_agblock_t agbno; /* block number containing inode */
2256	struct xfs_buf *agbp; /* buffer for allocation group header */
2257	xfs_agino_t agino; /* allocation group inode number */
2258	int error; /* error return value */
2259	struct xfs_mount *mp = tp->t_mountp;
2260	struct xfs_inobt_rec_incore rec;/* btree record */
2261
2262	/*
2263	* Break up inode number into its components.
2264	*/
2265	if (pag->pag_agno != XFS_INO_TO_AGNO(mp, inode)) {
2266	xfs_warn(mp, "%s: agno != pag->pag_agno (%d != %d).",
2267	__func__, XFS_INO_TO_AGNO(mp, inode), pag->pag_agno);
2268	ASSERT(0);
2269	return -EINVAL;
2270	}
2271	agino = XFS_INO_TO_AGINO(mp, inode);
2272	if (inode != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2273	xfs_warn(mp, "%s: inode != XFS_AGINO_TO_INO() (%llu != %llu).",
2274	__func__, (unsigned long long)inode,
2275	(unsigned long long)XFS_AGINO_TO_INO(mp, pag->pag_agno, agino));
2276	ASSERT(0);
2277	return -EINVAL;
2278	}
2279	agbno = XFS_AGINO_TO_AGBNO(mp, agino);
2280	if (agbno >= mp->m_sb.sb_agblocks) {
2281	xfs_warn(mp, "%s: agbno >= mp->m_sb.sb_agblocks (%d >= %d).",
2282	__func__, agbno, mp->m_sb.sb_agblocks);
2283	ASSERT(0);
2284	return -EINVAL;
2285	}
2286	/*
2287	* Get the allocation group header.
2288	*/
2289	error = xfs_ialloc_read_agi(pag, tp, agibpp: &agbp);
2290	if (error) {
2291	xfs_warn(mp, "%s: xfs_ialloc_read_agi() returned error %d.",
2292	__func__, error);
2293	return error;
2294	}
2295
2296	/*
2297	* Fix up the inode allocation btree.
2298	*/
2299	error = xfs_difree_inobt(pag, tp, agbp, agino, xic, &rec);
2300	if (error)
2301	goto error0;
2302
2303	/*
2304	* Fix up the free inode btree.
2305	*/
2306	if (xfs_has_finobt(mp)) {
2307	error = xfs_difree_finobt(pag, tp, agbp, agino, &rec);
2308	if (error)
2309	goto error0;
2310	}
2311
2312	return 0;
2313
2314	error0:
2315	return error;
2316	}
2317
2318	STATIC int
2319	xfs_imap_lookup(
2320	struct xfs_perag *pag,
2321	struct xfs_trans *tp,
2322	xfs_agino_t agino,
2323	xfs_agblock_t agbno,
2324	xfs_agblock_t *chunk_agbno,
2325	xfs_agblock_t *offset_agbno,
2326	int flags)
2327	{
2328	struct xfs_mount *mp = pag->pag_mount;
2329	struct xfs_inobt_rec_incore rec;
2330	struct xfs_btree_cur *cur;
2331	struct xfs_buf *agbp;
2332	int error;
2333	int i;
2334
2335	error = xfs_ialloc_read_agi(pag, tp, agibpp: &agbp);
2336	if (error) {
2337	xfs_alert(mp,
2338	"%s: xfs_ialloc_read_agi() returned error %d, agno %d",
2339	__func__, error, pag->pag_agno);
2340	return error;
2341	}
2342
2343	/*
2344	* Lookup the inode record for the given agino. If the record cannot be
2345	* found, then it's an invalid inode number and we should abort. Once
2346	* we have a record, we need to ensure it contains the inode number
2347	* we are looking up.
2348	*/
2349	cur = xfs_inobt_init_cursor(pag, tp, agbp);
2350	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i);
2351	if (!error) {
2352	if (i)
2353	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &i);
2354	if (!error && i == 0)
2355	error = -EINVAL;
2356	}
2357
2358	xfs_trans_brelse(tp, agbp);
2359	xfs_btree_del_cursor(cur, error);
2360	if (error)
2361	return error;
2362
2363	/* check that the returned record contains the required inode */
2364	if (rec.ir_startino > agino ||
2365	rec.ir_startino + M_IGEO(mp)->ialloc_inos <= agino)
2366	return -EINVAL;
2367
2368	/* for untrusted inodes check it is allocated first */
2369	if ((flags & XFS_IGET_UNTRUSTED) &&
2370	(rec.ir_free & XFS_INOBT_MASK(agino - rec.ir_startino)))
2371	return -EINVAL;
2372
2373	*chunk_agbno = XFS_AGINO_TO_AGBNO(mp, rec.ir_startino);
2374	*offset_agbno = agbno - *chunk_agbno;
2375	return 0;
2376	}
2377
2378	/*
2379	* Return the location of the inode in imap, for mapping it into a buffer.
2380	*/
2381	int
2382	xfs_imap(
2383	struct xfs_perag *pag,
2384	struct xfs_trans *tp,
2385	xfs_ino_t ino, /* inode to locate */
2386	struct xfs_imap *imap, /* location map structure */
2387	uint flags) /* flags for inode btree lookup */
2388	{
2389	struct xfs_mount *mp = pag->pag_mount;
2390	xfs_agblock_t agbno; /* block number of inode in the alloc group */
2391	xfs_agino_t agino; /* inode number within alloc group */
2392	xfs_agblock_t chunk_agbno; /* first block in inode chunk */
2393	xfs_agblock_t cluster_agbno; /* first block in inode cluster */
2394	int error; /* error code */
2395	int offset; /* index of inode in its buffer */
2396	xfs_agblock_t offset_agbno; /* blks from chunk start to inode */
2397
2398	ASSERT(ino != NULLFSINO);
2399
2400	/*
2401	* Split up the inode number into its parts.
2402	*/
2403	agino = XFS_INO_TO_AGINO(mp, ino);
2404	agbno = XFS_AGINO_TO_AGBNO(mp, agino);
2405	if (agbno >= mp->m_sb.sb_agblocks ||
2406	ino != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2407	error = -EINVAL;
2408	#ifdef DEBUG
2409	/*
2410	* Don't output diagnostic information for untrusted inodes
2411	* as they can be invalid without implying corruption.
2412	*/
2413	if (flags & XFS_IGET_UNTRUSTED)
2414	return error;
2415	if (agbno >= mp->m_sb.sb_agblocks) {
2416	xfs_alert(mp,
2417	"%s: agbno (0x%llx) >= mp->m_sb.sb_agblocks (0x%lx)",
2418	__func__, (unsigned long long)agbno,
2419	(unsigned long)mp->m_sb.sb_agblocks);
2420	}
2421	if (ino != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2422	xfs_alert(mp,
2423	"%s: ino (0x%llx) != XFS_AGINO_TO_INO() (0x%llx)",
2424	__func__, ino,
2425	XFS_AGINO_TO_INO(mp, pag->pag_agno, agino));
2426	}
2427	xfs_stack_trace();
2428	#endif /* DEBUG */
2429	return error;
2430	}
2431
2432	/*
2433	* For bulkstat and handle lookups, we have an untrusted inode number
2434	* that we have to verify is valid. We cannot do this just by reading
2435	* the inode buffer as it may have been unlinked and removed leaving
2436	* inodes in stale state on disk. Hence we have to do a btree lookup
2437	* in all cases where an untrusted inode number is passed.
2438	*/
2439	if (flags & XFS_IGET_UNTRUSTED) {
2440	error = xfs_imap_lookup(pag, tp, agino, agbno,
2441	&chunk_agbno, &offset_agbno, flags);
2442	if (error)
2443	return error;
2444	goto out_map;
2445	}
2446
2447	/*
2448	* If the inode cluster size is the same as the blocksize or
2449	* smaller we get to the buffer by simple arithmetics.
2450	*/
2451	if (M_IGEO(mp)->blocks_per_cluster == 1) {
2452	offset = XFS_INO_TO_OFFSET(mp, ino);
2453	ASSERT(offset < mp->m_sb.sb_inopblock);
2454
2455	imap->im_blkno = XFS_AGB_TO_DADDR(mp, pag->pag_agno, agbno);
2456	imap->im_len = XFS_FSB_TO_BB(mp, 1);
2457	imap->im_boffset = (unsigned short)(offset <<
2458	mp->m_sb.sb_inodelog);
2459	return 0;
2460	}
2461
2462	/*
2463	* If the inode chunks are aligned then use simple maths to
2464	* find the location. Otherwise we have to do a btree
2465	* lookup to find the location.
2466	*/
2467	if (M_IGEO(mp)->inoalign_mask) {
2468	offset_agbno = agbno & M_IGEO(mp)->inoalign_mask;
2469	chunk_agbno = agbno - offset_agbno;
2470	} else {
2471	error = xfs_imap_lookup(pag, tp, agino, agbno,
2472	&chunk_agbno, &offset_agbno, flags);
2473	if (error)
2474	return error;
2475	}
2476
2477	out_map:
2478	ASSERT(agbno >= chunk_agbno);
2479	cluster_agbno = chunk_agbno +
2480	((offset_agbno / M_IGEO(mp)->blocks_per_cluster) *
2481	M_IGEO(mp)->blocks_per_cluster);
2482	offset = ((agbno - cluster_agbno) * mp->m_sb.sb_inopblock) +
2483	XFS_INO_TO_OFFSET(mp, ino);
2484
2485	imap->im_blkno = XFS_AGB_TO_DADDR(mp, pag->pag_agno, cluster_agbno);
2486	imap->im_len = XFS_FSB_TO_BB(mp, M_IGEO(mp)->blocks_per_cluster);
2487	imap->im_boffset = (unsigned short)(offset << mp->m_sb.sb_inodelog);
2488
2489	/*
2490	* If the inode number maps to a block outside the bounds
2491	* of the file system then return NULL rather than calling
2492	* read_buf and panicing when we get an error from the
2493	* driver.
2494	*/
2495	if ((imap->im_blkno + imap->im_len) >
2496	XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks)) {
2497	xfs_alert(mp,
2498	"%s: (im_blkno (0x%llx) + im_len (0x%llx)) > sb_dblocks (0x%llx)",
2499	__func__, (unsigned long long) imap->im_blkno,
2500	(unsigned long long) imap->im_len,
2501	XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks));
2502	return -EINVAL;
2503	}
2504	return 0;
2505	}
2506
2507	/*
2508	* Log specified fields for the ag hdr (inode section). The growth of the agi
2509	* structure over time requires that we interpret the buffer as two logical
2510	* regions delineated by the end of the unlinked list. This is due to the size
2511	* of the hash table and its location in the middle of the agi.
2512	*
2513	* For example, a request to log a field before agi_unlinked and a field after
2514	* agi_unlinked could cause us to log the entire hash table and use an excessive
2515	* amount of log space. To avoid this behavior, log the region up through
2516	* agi_unlinked in one call and the region after agi_unlinked through the end of
2517	* the structure in another.
2518	*/
2519	void
2520	xfs_ialloc_log_agi(
2521	struct xfs_trans *tp,
2522	struct xfs_buf *bp,
2523	uint32_t fields)
2524	{
2525	int first; /* first byte number */
2526	int last; /* last byte number */
2527	static const short offsets[] = { /* field starting offsets */
2528	/* keep in sync with bit definitions */
2529	offsetof(xfs_agi_t, agi_magicnum),
2530	offsetof(xfs_agi_t, agi_versionnum),
2531	offsetof(xfs_agi_t, agi_seqno),
2532	offsetof(xfs_agi_t, agi_length),
2533	offsetof(xfs_agi_t, agi_count),
2534	offsetof(xfs_agi_t, agi_root),
2535	offsetof(xfs_agi_t, agi_level),
2536	offsetof(xfs_agi_t, agi_freecount),
2537	offsetof(xfs_agi_t, agi_newino),
2538	offsetof(xfs_agi_t, agi_dirino),
2539	offsetof(xfs_agi_t, agi_unlinked),
2540	offsetof(xfs_agi_t, agi_free_root),
2541	offsetof(xfs_agi_t, agi_free_level),
2542	offsetof(xfs_agi_t, agi_iblocks),
2543	sizeof(xfs_agi_t)
2544	};
2545	#ifdef DEBUG
2546	struct xfs_agi *agi = bp->b_addr;
2547
2548	ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
2549	#endif
2550
2551	/*
2552	* Compute byte offsets for the first and last fields in the first
2553	* region and log the agi buffer. This only logs up through
2554	* agi_unlinked.
2555	*/
2556	if (fields & XFS_AGI_ALL_BITS_R1) {
2557	xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R1,
2558	&first, &last);
2559	xfs_trans_log_buf(tp, bp, first, last);
2560	}
2561
2562	/*
2563	* Mask off the bits in the first region and calculate the first and
2564	* last field offsets for any bits in the second region.
2565	*/
2566	fields &= ~XFS_AGI_ALL_BITS_R1;
2567	if (fields) {
2568	xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R2,
2569	&first, &last);
2570	xfs_trans_log_buf(tp, bp, first, last);
2571	}
2572	}
2573
2574	static xfs_failaddr_t
2575	xfs_agi_verify(
2576	struct xfs_buf *bp)
2577	{
2578	struct xfs_mount *mp = bp->b_mount;
2579	struct xfs_agi *agi = bp->b_addr;
2580	xfs_failaddr_t fa;
2581	uint32_t agi_seqno = be32_to_cpu(agi->agi_seqno);
2582	uint32_t agi_length = be32_to_cpu(agi->agi_length);
2583	int i;
2584
2585	if (xfs_has_crc(mp)) {
2586	if (!uuid_equal(&agi->agi_uuid, &mp->m_sb.sb_meta_uuid))
2587	return __this_address;
2588	if (!xfs_log_check_lsn(mp, be64_to_cpu(agi->agi_lsn)))
2589	return __this_address;
2590	}
2591
2592	/*
2593	* Validate the magic number of the agi block.
2594	*/
2595	if (!xfs_verify_magic(bp, agi->agi_magicnum))
2596	return __this_address;
2597	if (!XFS_AGI_GOOD_VERSION(be32_to_cpu(agi->agi_versionnum)))
2598	return __this_address;
2599
2600	fa = xfs_validate_ag_length(bp, agi_seqno, agi_length);
2601	if (fa)
2602	return fa;
2603
2604	if (be32_to_cpu(agi->agi_level) < 1 ||
2605	be32_to_cpu(agi->agi_level) > M_IGEO(mp)->inobt_maxlevels)
2606	return __this_address;
2607
2608	if (xfs_has_finobt(mp) &&
2609	(be32_to_cpu(agi->agi_free_level) < 1 ||
2610	be32_to_cpu(agi->agi_free_level) > M_IGEO(mp)->inobt_maxlevels))
2611	return __this_address;
2612
2613	for (i = 0; i < XFS_AGI_UNLINKED_BUCKETS; i++) {
2614	if (agi->agi_unlinked[i] == cpu_to_be32(NULLAGINO))
2615	continue;
2616	if (!xfs_verify_ino(mp, be32_to_cpu(agi->agi_unlinked[i])))
2617	return __this_address;
2618	}
2619
2620	return NULL;
2621	}
2622
2623	static void
2624	xfs_agi_read_verify(
2625	struct xfs_buf *bp)
2626	{
2627	struct xfs_mount *mp = bp->b_mount;
2628	xfs_failaddr_t fa;
2629
2630	if (xfs_has_crc(mp) &&
2631	!xfs_buf_verify_cksum(bp, XFS_AGI_CRC_OFF))
2632	xfs_verifier_error(bp, -EFSBADCRC, __this_address);
2633	else {
2634	fa = xfs_agi_verify(bp);
2635	if (XFS_TEST_ERROR(fa, mp, XFS_ERRTAG_IALLOC_READ_AGI))
2636	xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2637	}
2638	}
2639
2640	static void
2641	xfs_agi_write_verify(
2642	struct xfs_buf *bp)
2643	{
2644	struct xfs_mount *mp = bp->b_mount;
2645	struct xfs_buf_log_item *bip = bp->b_log_item;
2646	struct xfs_agi *agi = bp->b_addr;
2647	xfs_failaddr_t fa;
2648
2649	fa = xfs_agi_verify(bp);
2650	if (fa) {
2651	xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2652	return;
2653	}
2654
2655	if (!xfs_has_crc(mp))
2656	return;
2657
2658	if (bip)
2659	agi->agi_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2660	xfs_buf_update_cksum(bp, XFS_AGI_CRC_OFF);
2661	}
2662
2663	const struct xfs_buf_ops xfs_agi_buf_ops = {
2664	.name = "xfs_agi",
2665	.magic = { cpu_to_be32(XFS_AGI_MAGIC), cpu_to_be32(XFS_AGI_MAGIC) },
2666	.verify_read = xfs_agi_read_verify,
2667	.verify_write = xfs_agi_write_verify,
2668	.verify_struct = xfs_agi_verify,
2669	};
2670
2671	/*
2672	* Read in the allocation group header (inode allocation section)
2673	*/
2674	int
2675	xfs_read_agi(
2676	struct xfs_perag *pag,
2677	struct xfs_trans *tp,
2678	struct xfs_buf **agibpp)
2679	{
2680	struct xfs_mount *mp = pag->pag_mount;
2681	int error;
2682
2683	trace_xfs_read_agi(pag->pag_mount, pag->pag_agno);
2684
2685	error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
2686	XFS_AG_DADDR(mp, pag->pag_agno, XFS_AGI_DADDR(mp)),
2687	XFS_FSS_TO_BB(mp, 1), 0, agibpp, &xfs_agi_buf_ops);
2688	if (xfs_metadata_is_sick(error))
2689	xfs_ag_mark_sick(pag, XFS_SICK_AG_AGI);
2690	if (error)
2691	return error;
2692	if (tp)
2693	xfs_trans_buf_set_type(tp, *agibpp, XFS_BLFT_AGI_BUF);
2694
2695	xfs_buf_set_ref(*agibpp, XFS_AGI_REF);
2696	return 0;
2697	}
2698
2699	/*
2700	* Read in the agi and initialise the per-ag data. If the caller supplies a
2701	* @agibpp, return the locked AGI buffer to them, otherwise release it.
2702	*/
2703	int
2704	xfs_ialloc_read_agi(
2705	struct xfs_perag *pag,
2706	struct xfs_trans *tp,
2707	struct xfs_buf **agibpp)
2708	{
2709	struct xfs_buf *agibp;
2710	struct xfs_agi *agi;
2711	int error;
2712
2713	trace_xfs_ialloc_read_agi(pag->pag_mount, pag->pag_agno);
2714
2715	error = xfs_read_agi(pag, tp, agibpp: &agibp);
2716	if (error)
2717	return error;
2718
2719	agi = agibp->b_addr;
2720	if (!xfs_perag_initialised_agi(pag)) {
2721	pag->pagi_freecount = be32_to_cpu(agi->agi_freecount);
2722	pag->pagi_count = be32_to_cpu(agi->agi_count);
2723	set_bit(XFS_AGSTATE_AGI_INIT, &pag->pag_opstate);
2724	}
2725
2726	/*
2727	* It's possible for these to be out of sync if
2728	* we are in the middle of a forced shutdown.
2729	*/
2730	ASSERT(pag->pagi_freecount == be32_to_cpu(agi->agi_freecount) ||
2731	xfs_is_shutdown(pag->pag_mount));
2732	if (agibpp)
2733	*agibpp = agibp;
2734	else
2735	xfs_trans_brelse(tp, agibp);
2736	return 0;
2737	}
2738
2739	/* How many inodes are backed by inode clusters ondisk? */
2740	STATIC int
2741	xfs_ialloc_count_ondisk(
2742	struct xfs_btree_cur *cur,
2743	xfs_agino_t low,
2744	xfs_agino_t high,
2745	unsigned int *allocated)
2746	{
2747	struct xfs_inobt_rec_incore irec;
2748	unsigned int ret = 0;
2749	int has_record;
2750	int error;
2751
2752	error = xfs_inobt_lookup(cur, low, XFS_LOOKUP_LE, &has_record);
2753	if (error)
2754	return error;
2755
2756	while (has_record) {
2757	unsigned int i, hole_idx;
2758
2759	error = xfs_inobt_get_rec(cur, irec: &irec, stat: &has_record);
2760	if (error)
2761	return error;
2762	if (irec.ir_startino > high)
2763	break;
2764
2765	for (i = 0; i < XFS_INODES_PER_CHUNK; i++) {
2766	if (irec.ir_startino + i < low)
2767	continue;
2768	if (irec.ir_startino + i > high)
2769	break;
2770
2771	hole_idx = i / XFS_INODES_PER_HOLEMASK_BIT;
2772	if (!(irec.ir_holemask & (1U << hole_idx)))
2773	ret++;
2774	}
2775
2776	error = xfs_btree_increment(cur, 0, &has_record);
2777	if (error)
2778	return error;
2779	}
2780
2781	*allocated = ret;
2782	return 0;
2783	}
2784
2785	/* Is there an inode record covering a given extent? */
2786	int
2787	xfs_ialloc_has_inodes_at_extent(
2788	struct xfs_btree_cur *cur,
2789	xfs_agblock_t bno,
2790	xfs_extlen_t len,
2791	enum xbtree_recpacking *outcome)
2792	{
2793	xfs_agino_t agino;
2794	xfs_agino_t last_agino;
2795	unsigned int allocated;
2796	int error;
2797
2798	agino = XFS_AGB_TO_AGINO(cur->bc_mp, bno);
2799	last_agino = XFS_AGB_TO_AGINO(cur->bc_mp, bno + len) - 1;
2800
2801	error = xfs_ialloc_count_ondisk(cur, agino, last_agino, &allocated);
2802	if (error)
2803	return error;
2804
2805	if (allocated == 0)
2806	*outcome = XBTREE_RECPACKING_EMPTY;
2807	else if (allocated == last_agino - agino + 1)
2808	*outcome = XBTREE_RECPACKING_FULL;
2809	else
2810	*outcome = XBTREE_RECPACKING_SPARSE;
2811	return 0;
2812	}
2813
2814	struct xfs_ialloc_count_inodes {
2815	xfs_agino_t count;
2816	xfs_agino_t freecount;
2817	};
2818
2819	/* Record inode counts across all inobt records. */
2820	STATIC int
2821	xfs_ialloc_count_inodes_rec(
2822	struct xfs_btree_cur *cur,
2823	const union xfs_btree_rec *rec,
2824	void *priv)
2825	{
2826	struct xfs_inobt_rec_incore irec;
2827	struct xfs_ialloc_count_inodes *ci = priv;
2828	xfs_failaddr_t fa;
2829
2830	xfs_inobt_btrec_to_irec(mp: cur->bc_mp, rec, irec: &irec);
2831	fa = xfs_inobt_check_irec(cur->bc_ag.pag, &irec);
2832	if (fa)
2833	return xfs_inobt_complain_bad_rec(cur, fa, &irec);
2834
2835	ci->count += irec.ir_count;
2836	ci->freecount += irec.ir_freecount;
2837
2838	return 0;
2839	}
2840
2841	/* Count allocated and free inodes under an inobt. */
2842	int
2843	xfs_ialloc_count_inodes(
2844	struct xfs_btree_cur *cur,
2845	xfs_agino_t *count,
2846	xfs_agino_t *freecount)
2847	{
2848	struct xfs_ialloc_count_inodes ci = {0};
2849	int error;
2850
2851	ASSERT(xfs_btree_is_ino(cur->bc_ops));
2852	error = xfs_btree_query_all(cur, fn: xfs_ialloc_count_inodes_rec, priv: &ci);
2853	if (error)
2854	return error;
2855
2856	*count = ci.count;
2857	*freecount = ci.freecount;
2858	return 0;
2859	}
2860
2861	/*
2862	* Initialize inode-related geometry information.
2863	*
2864	* Compute the inode btree min and max levels and set maxicount.
2865	*
2866	* Set the inode cluster size. This may still be overridden by the file
2867	* system block size if it is larger than the chosen cluster size.
2868	*
2869	* For v5 filesystems, scale the cluster size with the inode size to keep a
2870	* constant ratio of inode per cluster buffer, but only if mkfs has set the
2871	* inode alignment value appropriately for larger cluster sizes.
2872	*
2873	* Then compute the inode cluster alignment information.
2874	*/
2875	void
2876	xfs_ialloc_setup_geometry(
2877	struct xfs_mount *mp)
2878	{
2879	struct xfs_sb *sbp = &mp->m_sb;
2880	struct xfs_ino_geometry *igeo = M_IGEO(mp);
2881	uint64_t icount;
2882	uint inodes;
2883
2884	igeo->new_diflags2 = 0;
2885	if (xfs_has_bigtime(mp))
2886	igeo->new_diflags2 |= XFS_DIFLAG2_BIGTIME;
2887	if (xfs_has_large_extent_counts(mp))
2888	igeo->new_diflags2 |= XFS_DIFLAG2_NREXT64;
2889
2890	/* Compute inode btree geometry. */
2891	igeo->agino_log = sbp->sb_inopblog + sbp->sb_agblklog;
2892	igeo->inobt_mxr[0] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, 1);
2893	igeo->inobt_mxr[1] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, 0);
2894	igeo->inobt_mnr[0] = igeo->inobt_mxr[0] / 2;
2895	igeo->inobt_mnr[1] = igeo->inobt_mxr[1] / 2;
2896
2897	igeo->ialloc_inos = max_t(uint16_t, XFS_INODES_PER_CHUNK,
2898	sbp->sb_inopblock);
2899	igeo->ialloc_blks = igeo->ialloc_inos >> sbp->sb_inopblog;
2900
2901	if (sbp->sb_spino_align)
2902	igeo->ialloc_min_blks = sbp->sb_spino_align;
2903	else
2904	igeo->ialloc_min_blks = igeo->ialloc_blks;
2905
2906	/* Compute and fill in value of m_ino_geo.inobt_maxlevels. */
2907	inodes = (1LL << XFS_INO_AGINO_BITS(mp)) >> XFS_INODES_PER_CHUNK_LOG;
2908	igeo->inobt_maxlevels = xfs_btree_compute_maxlevels(igeo->inobt_mnr,
2909	inodes);
2910	ASSERT(igeo->inobt_maxlevels <= xfs_iallocbt_maxlevels_ondisk());
2911
2912	/*
2913	* Set the maximum inode count for this filesystem, being careful not
2914	* to use obviously garbage sb_inopblog/sb_inopblock values. Regular
2915	* users should never get here due to failing sb verification, but
2916	* certain users (xfs_db) need to be usable even with corrupt metadata.
2917	*/
2918	if (sbp->sb_imax_pct && igeo->ialloc_blks) {
2919	/*
2920	* Make sure the maximum inode count is a multiple
2921	* of the units we allocate inodes in.
2922	*/
2923	icount = sbp->sb_dblocks * sbp->sb_imax_pct;
2924	do_div(icount, 100);
2925	do_div(icount, igeo->ialloc_blks);
2926	igeo->maxicount = XFS_FSB_TO_INO(mp,
2927	icount * igeo->ialloc_blks);
2928	} else {
2929	igeo->maxicount = 0;
2930	}
2931
2932	/*
2933	* Compute the desired size of an inode cluster buffer size, which
2934	* starts at 8K and (on v5 filesystems) scales up with larger inode
2935	* sizes.
2936	*
2937	* Preserve the desired inode cluster size because the sparse inodes
2938	* feature uses that desired size (not the actual size) to compute the
2939	* sparse inode alignment. The mount code validates this value, so we
2940	* cannot change the behavior.
2941	*/
2942	igeo->inode_cluster_size_raw = XFS_INODE_BIG_CLUSTER_SIZE;
2943	if (xfs_has_v3inodes(mp)) {
2944	int new_size = igeo->inode_cluster_size_raw;
2945
2946	new_size *= mp->m_sb.sb_inodesize / XFS_DINODE_MIN_SIZE;
2947	if (mp->m_sb.sb_inoalignmt >= XFS_B_TO_FSBT(mp, new_size))
2948	igeo->inode_cluster_size_raw = new_size;
2949	}
2950
2951	/* Calculate inode cluster ratios. */
2952	if (igeo->inode_cluster_size_raw > mp->m_sb.sb_blocksize)
2953	igeo->blocks_per_cluster = XFS_B_TO_FSBT(mp,
2954	igeo->inode_cluster_size_raw);
2955	else
2956	igeo->blocks_per_cluster = 1;
2957	igeo->inode_cluster_size = XFS_FSB_TO_B(mp, igeo->blocks_per_cluster);
2958	igeo->inodes_per_cluster = XFS_FSB_TO_INO(mp, igeo->blocks_per_cluster);
2959
2960	/* Calculate inode cluster alignment. */
2961	if (xfs_has_align(mp) &&
2962	mp->m_sb.sb_inoalignmt >= igeo->blocks_per_cluster)
2963	igeo->cluster_align = mp->m_sb.sb_inoalignmt;
2964	else
2965	igeo->cluster_align = 1;
2966	igeo->inoalign_mask = igeo->cluster_align - 1;
2967	igeo->cluster_align_inodes = XFS_FSB_TO_INO(mp, igeo->cluster_align);
2968
2969	/*
2970	* If we are using stripe alignment, check whether
2971	* the stripe unit is a multiple of the inode alignment
2972	*/
2973	if (mp->m_dalign && igeo->inoalign_mask &&
2974	!(mp->m_dalign & igeo->inoalign_mask))
2975	igeo->ialloc_align = mp->m_dalign;
2976	else
2977	igeo->ialloc_align = 0;
2978	}
2979
2980	/* Compute the location of the root directory inode that is laid out by mkfs. */
2981	xfs_ino_t
2982	xfs_ialloc_calc_rootino(
2983	struct xfs_mount *mp,
2984	int sunit)
2985	{
2986	struct xfs_ino_geometry *igeo = M_IGEO(mp);
2987	xfs_agblock_t first_bno;
2988
2989	/*
2990	* Pre-calculate the geometry of AG 0. We know what it looks like
2991	* because libxfs knows how to create allocation groups now.
2992	*
2993	* first_bno is the first block in which mkfs could possibly have
2994	* allocated the root directory inode, once we factor in the metadata
2995	* that mkfs formats before it. Namely, the four AG headers...
2996	*/
2997	first_bno = howmany(4 * mp->m_sb.sb_sectsize, mp->m_sb.sb_blocksize);
2998
2999	/* ...the two free space btree roots... */
3000	first_bno += 2;
3001
3002	/* ...the inode btree root... */
3003	first_bno += 1;
3004
3005	/* ...the initial AGFL... */
3006	first_bno += xfs_alloc_min_freelist(mp, NULL);
3007
3008	/* ...the free inode btree root... */
3009	if (xfs_has_finobt(mp))
3010	first_bno++;
3011
3012	/* ...the reverse mapping btree root... */
3013	if (xfs_has_rmapbt(mp))
3014	first_bno++;
3015
3016	/* ...the reference count btree... */
3017	if (xfs_has_reflink(mp))
3018	first_bno++;
3019
3020	/*
3021	* ...and the log, if it is allocated in the first allocation group.
3022	*
3023	* This can happen with filesystems that only have a single
3024	* allocation group, or very odd geometries created by old mkfs
3025	* versions on very small filesystems.
3026	*/
3027	if (xfs_ag_contains_log(mp, 0))
3028	first_bno += mp->m_sb.sb_logblocks;
3029
3030	/*
3031	* Now round first_bno up to whatever allocation alignment is given
3032	* by the filesystem or was passed in.
3033	*/
3034	if (xfs_has_dalign(mp) && igeo->ialloc_align > 0)
3035	first_bno = roundup(first_bno, sunit);
3036	else if (xfs_has_align(mp) &&
3037	mp->m_sb.sb_inoalignmt > 1)
3038	first_bno = roundup(first_bno, mp->m_sb.sb_inoalignmt);
3039
3040	return XFS_AGINO_TO_INO(mp, 0, XFS_AGB_TO_AGINO(mp, first_bno));
3041	}
3042
3043	/*
3044	* Ensure there are not sparse inode clusters that cross the new EOAG.
3045	*
3046	* This is a no-op for non-spinode filesystems since clusters are always fully
3047	* allocated and checking the bnobt suffices. However, a spinode filesystem
3048	* could have a record where the upper inodes are free blocks. If those blocks
3049	* were removed from the filesystem, the inode record would extend beyond EOAG,
3050	* which will be flagged as corruption.
3051	*/
3052	int
3053	xfs_ialloc_check_shrink(
3054	struct xfs_perag *pag,
3055	struct xfs_trans *tp,
3056	struct xfs_buf *agibp,
3057	xfs_agblock_t new_length)
3058	{
3059	struct xfs_inobt_rec_incore rec;
3060	struct xfs_btree_cur *cur;
3061	xfs_agino_t agino;
3062	int has;
3063	int error;
3064
3065	if (!xfs_has_sparseinodes(pag->pag_mount))
3066	return 0;
3067
3068	cur = xfs_inobt_init_cursor(pag, tp, agbp: agibp);
3069
3070	/* Look up the inobt record that would correspond to the new EOFS. */
3071	agino = XFS_AGB_TO_AGINO(pag->pag_mount, new_length);
3072	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &has);
3073	if (error || !has)
3074	goto out;
3075
3076	error = xfs_inobt_get_rec(cur, irec: &rec, stat: &has);
3077	if (error)
3078	goto out;
3079
3080	if (!has) {
3081	xfs_ag_mark_sick(pag, XFS_SICK_AG_INOBT);
3082	error = -EFSCORRUPTED;
3083	goto out;
3084	}
3085
3086	/* If the record covers inodes that would be beyond EOFS, bail out. */
3087	if (rec.ir_startino + XFS_INODES_PER_CHUNK > agino) {
3088	error = -ENOSPC;
3089	goto out;
3090	}
3091	out:
3092	xfs_btree_del_cursor(cur, error);
3093	return error;
3094	}
3095