2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 #include "libxfs_priv.h"
20 #include "xfs_shared.h"
21 #include "xfs_format.h"
22 #include "xfs_log_format.h"
23 #include "xfs_trans_resv.h"
26 #include "xfs_mount.h"
27 #include "xfs_defer.h"
28 #include "xfs_inode.h"
29 #include "xfs_btree.h"
30 #include "xfs_ialloc.h"
31 #include "xfs_ialloc_btree.h"
32 #include "xfs_alloc.h"
34 #include "xfs_cksum.h"
35 #include "xfs_trans.h"
36 #include "xfs_trace.h"
41 * Allocation group level functions.
44 xfs_ialloc_cluster_alignment(
47 if (xfs_sb_version_hasalign(&mp
->m_sb
) &&
48 mp
->m_sb
.sb_inoalignmt
>= xfs_icluster_size_fsb(mp
))
49 return mp
->m_sb
.sb_inoalignmt
;
54 * Lookup a record by ino in the btree given by cur.
58 struct xfs_btree_cur
*cur
, /* btree cursor */
59 xfs_agino_t ino
, /* starting inode of chunk */
60 xfs_lookup_t dir
, /* <=, >=, == */
61 int *stat
) /* success/failure */
63 cur
->bc_rec
.i
.ir_startino
= ino
;
64 cur
->bc_rec
.i
.ir_holemask
= 0;
65 cur
->bc_rec
.i
.ir_count
= 0;
66 cur
->bc_rec
.i
.ir_freecount
= 0;
67 cur
->bc_rec
.i
.ir_free
= 0;
68 return xfs_btree_lookup(cur
, dir
, stat
);
72 * Update the record referred to by cur to the value given.
73 * This either works (return 0) or gets an EFSCORRUPTED error.
75 STATIC
int /* error */
77 struct xfs_btree_cur
*cur
, /* btree cursor */
78 xfs_inobt_rec_incore_t
*irec
) /* btree record */
80 union xfs_btree_rec rec
;
82 rec
.inobt
.ir_startino
= cpu_to_be32(irec
->ir_startino
);
83 if (xfs_sb_version_hassparseinodes(&cur
->bc_mp
->m_sb
)) {
84 rec
.inobt
.ir_u
.sp
.ir_holemask
= cpu_to_be16(irec
->ir_holemask
);
85 rec
.inobt
.ir_u
.sp
.ir_count
= irec
->ir_count
;
86 rec
.inobt
.ir_u
.sp
.ir_freecount
= irec
->ir_freecount
;
88 /* ir_holemask/ir_count not supported on-disk */
89 rec
.inobt
.ir_u
.f
.ir_freecount
= cpu_to_be32(irec
->ir_freecount
);
91 rec
.inobt
.ir_free
= cpu_to_be64(irec
->ir_free
);
92 return xfs_btree_update(cur
, &rec
);
95 /* Convert on-disk btree record to incore inobt record. */
97 xfs_inobt_btrec_to_irec(
99 union xfs_btree_rec
*rec
,
100 struct xfs_inobt_rec_incore
*irec
)
102 irec
->ir_startino
= be32_to_cpu(rec
->inobt
.ir_startino
);
103 if (xfs_sb_version_hassparseinodes(&mp
->m_sb
)) {
104 irec
->ir_holemask
= be16_to_cpu(rec
->inobt
.ir_u
.sp
.ir_holemask
);
105 irec
->ir_count
= rec
->inobt
.ir_u
.sp
.ir_count
;
106 irec
->ir_freecount
= rec
->inobt
.ir_u
.sp
.ir_freecount
;
109 * ir_holemask/ir_count not supported on-disk. Fill in hardcoded
110 * values for full inode chunks.
112 irec
->ir_holemask
= XFS_INOBT_HOLEMASK_FULL
;
113 irec
->ir_count
= XFS_INODES_PER_CHUNK
;
115 be32_to_cpu(rec
->inobt
.ir_u
.f
.ir_freecount
);
117 irec
->ir_free
= be64_to_cpu(rec
->inobt
.ir_free
);
121 * Get the data from the pointed-to record.
125 struct xfs_btree_cur
*cur
,
126 struct xfs_inobt_rec_incore
*irec
,
129 union xfs_btree_rec
*rec
;
132 error
= xfs_btree_get_rec(cur
, &rec
, stat
);
133 if (error
|| *stat
== 0)
136 xfs_inobt_btrec_to_irec(cur
->bc_mp
, rec
, irec
);
142 * Insert a single inobt record. Cursor must already point to desired location.
145 xfs_inobt_insert_rec(
146 struct xfs_btree_cur
*cur
,
153 cur
->bc_rec
.i
.ir_holemask
= holemask
;
154 cur
->bc_rec
.i
.ir_count
= count
;
155 cur
->bc_rec
.i
.ir_freecount
= freecount
;
156 cur
->bc_rec
.i
.ir_free
= free
;
157 return xfs_btree_insert(cur
, stat
);
161 * Insert records describing a newly allocated inode chunk into the inobt.
165 struct xfs_mount
*mp
,
166 struct xfs_trans
*tp
,
167 struct xfs_buf
*agbp
,
172 struct xfs_btree_cur
*cur
;
173 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
174 xfs_agnumber_t agno
= be32_to_cpu(agi
->agi_seqno
);
179 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, btnum
);
181 for (thisino
= newino
;
182 thisino
< newino
+ newlen
;
183 thisino
+= XFS_INODES_PER_CHUNK
) {
184 error
= xfs_inobt_lookup(cur
, thisino
, XFS_LOOKUP_EQ
, &i
);
186 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
191 error
= xfs_inobt_insert_rec(cur
, XFS_INOBT_HOLEMASK_FULL
,
192 XFS_INODES_PER_CHUNK
,
193 XFS_INODES_PER_CHUNK
,
194 XFS_INOBT_ALL_FREE
, &i
);
196 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
202 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
208 * Verify that the number of free inodes in the AGI is correct.
212 xfs_check_agi_freecount(
213 struct xfs_btree_cur
*cur
,
216 if (cur
->bc_nlevels
== 1) {
217 xfs_inobt_rec_incore_t rec
;
222 error
= xfs_inobt_lookup(cur
, 0, XFS_LOOKUP_GE
, &i
);
227 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
232 freecount
+= rec
.ir_freecount
;
233 error
= xfs_btree_increment(cur
, 0, &i
);
239 if (!XFS_FORCED_SHUTDOWN(cur
->bc_mp
))
240 ASSERT(freecount
== be32_to_cpu(agi
->agi_freecount
));
245 #define xfs_check_agi_freecount(cur, agi) 0
249 * Initialise a new set of inodes. When called without a transaction context
250 * (e.g. from recovery) we initiate a delayed write of the inode buffers rather
251 * than logging them (which in a transaction context puts them into the AIL
252 * for writeback rather than the xfsbufd queue).
255 xfs_ialloc_inode_init(
256 struct xfs_mount
*mp
,
257 struct xfs_trans
*tp
,
258 struct list_head
*buffer_list
,
262 xfs_agblock_t length
,
265 struct xfs_buf
*fbuf
;
266 struct xfs_dinode
*free
;
267 int nbufs
, blks_per_cluster
, inodes_per_cluster
;
274 * Loop over the new block(s), filling in the inodes. For small block
275 * sizes, manipulate the inodes in buffers which are multiples of the
278 blks_per_cluster
= xfs_icluster_size_fsb(mp
);
279 inodes_per_cluster
= blks_per_cluster
<< mp
->m_sb
.sb_inopblog
;
280 nbufs
= length
/ blks_per_cluster
;
283 * Figure out what version number to use in the inodes we create. If
284 * the superblock version has caught up to the one that supports the new
285 * inode format, then use the new inode version. Otherwise use the old
286 * version so that old kernels will continue to be able to use the file
289 * For v3 inodes, we also need to write the inode number into the inode,
290 * so calculate the first inode number of the chunk here as
291 * XFS_OFFBNO_TO_AGINO() only works within a filesystem block, not
292 * across multiple filesystem blocks (such as a cluster) and so cannot
293 * be used in the cluster buffer loop below.
295 * Further, because we are writing the inode directly into the buffer
296 * and calculating a CRC on the entire inode, we have ot log the entire
297 * inode so that the entire range the CRC covers is present in the log.
298 * That means for v3 inode we log the entire buffer rather than just the
301 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
303 ino
= XFS_AGINO_TO_INO(mp
, agno
,
304 XFS_OFFBNO_TO_AGINO(mp
, agbno
, 0));
307 * log the initialisation that is about to take place as an
308 * logical operation. This means the transaction does not
309 * need to log the physical changes to the inode buffers as log
310 * recovery will know what initialisation is actually needed.
311 * Hence we only need to log the buffers as "ordered" buffers so
312 * they track in the AIL as if they were physically logged.
315 xfs_icreate_log(tp
, agno
, agbno
, icount
,
316 mp
->m_sb
.sb_inodesize
, length
, gen
);
320 for (j
= 0; j
< nbufs
; j
++) {
324 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
+ (j
* blks_per_cluster
));
325 fbuf
= xfs_trans_get_buf(tp
, mp
->m_ddev_targp
, d
,
326 mp
->m_bsize
* blks_per_cluster
,
331 /* Initialize the inode buffers and log them appropriately. */
332 fbuf
->b_ops
= &xfs_inode_buf_ops
;
333 xfs_buf_zero(fbuf
, 0, BBTOB(fbuf
->b_length
));
334 for (i
= 0; i
< inodes_per_cluster
; i
++) {
335 int ioffset
= i
<< mp
->m_sb
.sb_inodelog
;
336 uint isize
= xfs_dinode_size(version
);
338 free
= xfs_make_iptr(mp
, fbuf
, i
);
339 free
->di_magic
= cpu_to_be16(XFS_DINODE_MAGIC
);
340 free
->di_version
= version
;
341 free
->di_gen
= cpu_to_be32(gen
);
342 free
->di_next_unlinked
= cpu_to_be32(NULLAGINO
);
345 free
->di_ino
= cpu_to_be64(ino
);
347 uuid_copy(&free
->di_uuid
,
348 &mp
->m_sb
.sb_meta_uuid
);
349 xfs_dinode_calc_crc(mp
, free
);
351 /* just log the inode core */
352 xfs_trans_log_buf(tp
, fbuf
, ioffset
,
353 ioffset
+ isize
- 1);
359 * Mark the buffer as an inode allocation buffer so it
360 * sticks in AIL at the point of this allocation
361 * transaction. This ensures the they are on disk before
362 * the tail of the log can be moved past this
363 * transaction (i.e. by preventing relogging from moving
364 * it forward in the log).
366 xfs_trans_inode_alloc_buf(tp
, fbuf
);
369 * Mark the buffer as ordered so that they are
370 * not physically logged in the transaction but
371 * still tracked in the AIL as part of the
372 * transaction and pin the log appropriately.
374 xfs_trans_ordered_buf(tp
, fbuf
);
377 fbuf
->b_flags
|= XBF_DONE
;
378 xfs_buf_delwri_queue(fbuf
, buffer_list
);
386 * Align startino and allocmask for a recently allocated sparse chunk such that
387 * they are fit for insertion (or merge) into the on-disk inode btrees.
391 * When enabled, sparse inode support increases the inode alignment from cluster
392 * size to inode chunk size. This means that the minimum range between two
393 * non-adjacent inode records in the inobt is large enough for a full inode
394 * record. This allows for cluster sized, cluster aligned block allocation
395 * without need to worry about whether the resulting inode record overlaps with
396 * another record in the tree. Without this basic rule, we would have to deal
397 * with the consequences of overlap by potentially undoing recent allocations in
398 * the inode allocation codepath.
400 * Because of this alignment rule (which is enforced on mount), there are two
401 * inobt possibilities for newly allocated sparse chunks. One is that the
402 * aligned inode record for the chunk covers a range of inodes not already
403 * covered in the inobt (i.e., it is safe to insert a new sparse record). The
404 * other is that a record already exists at the aligned startino that considers
405 * the newly allocated range as sparse. In the latter case, record content is
406 * merged in hope that sparse inode chunks fill to full chunks over time.
409 xfs_align_sparse_ino(
410 struct xfs_mount
*mp
,
411 xfs_agino_t
*startino
,
418 agbno
= XFS_AGINO_TO_AGBNO(mp
, *startino
);
419 mod
= agbno
% mp
->m_sb
.sb_inoalignmt
;
423 /* calculate the inode offset and align startino */
424 offset
= mod
<< mp
->m_sb
.sb_inopblog
;
428 * Since startino has been aligned down, left shift allocmask such that
429 * it continues to represent the same physical inodes relative to the
432 *allocmask
<<= offset
/ XFS_INODES_PER_HOLEMASK_BIT
;
436 * Determine whether the source inode record can merge into the target. Both
437 * records must be sparse, the inode ranges must match and there must be no
438 * allocation overlap between the records.
441 __xfs_inobt_can_merge(
442 struct xfs_inobt_rec_incore
*trec
, /* tgt record */
443 struct xfs_inobt_rec_incore
*srec
) /* src record */
448 /* records must cover the same inode range */
449 if (trec
->ir_startino
!= srec
->ir_startino
)
452 /* both records must be sparse */
453 if (!xfs_inobt_issparse(trec
->ir_holemask
) ||
454 !xfs_inobt_issparse(srec
->ir_holemask
))
457 /* both records must track some inodes */
458 if (!trec
->ir_count
|| !srec
->ir_count
)
461 /* can't exceed capacity of a full record */
462 if (trec
->ir_count
+ srec
->ir_count
> XFS_INODES_PER_CHUNK
)
465 /* verify there is no allocation overlap */
466 talloc
= xfs_inobt_irec_to_allocmask(trec
);
467 salloc
= xfs_inobt_irec_to_allocmask(srec
);
475 * Merge the source inode record into the target. The caller must call
476 * __xfs_inobt_can_merge() to ensure the merge is valid.
479 __xfs_inobt_rec_merge(
480 struct xfs_inobt_rec_incore
*trec
, /* target */
481 struct xfs_inobt_rec_incore
*srec
) /* src */
483 ASSERT(trec
->ir_startino
== srec
->ir_startino
);
485 /* combine the counts */
486 trec
->ir_count
+= srec
->ir_count
;
487 trec
->ir_freecount
+= srec
->ir_freecount
;
490 * Merge the holemask and free mask. For both fields, 0 bits refer to
491 * allocated inodes. We combine the allocated ranges with bitwise AND.
493 trec
->ir_holemask
&= srec
->ir_holemask
;
494 trec
->ir_free
&= srec
->ir_free
;
498 * Insert a new sparse inode chunk into the associated inode btree. The inode
499 * record for the sparse chunk is pre-aligned to a startino that should match
500 * any pre-existing sparse inode record in the tree. This allows sparse chunks
503 * This function supports two modes of handling preexisting records depending on
504 * the merge flag. If merge is true, the provided record is merged with the
505 * existing record and updated in place. The merged record is returned in nrec.
506 * If merge is false, an existing record is replaced with the provided record.
507 * If no preexisting record exists, the provided record is always inserted.
509 * It is considered corruption if a merge is requested and not possible. Given
510 * the sparse inode alignment constraints, this should never happen.
513 xfs_inobt_insert_sprec(
514 struct xfs_mount
*mp
,
515 struct xfs_trans
*tp
,
516 struct xfs_buf
*agbp
,
518 struct xfs_inobt_rec_incore
*nrec
, /* in/out: new/merged rec. */
519 bool merge
) /* merge or replace */
521 struct xfs_btree_cur
*cur
;
522 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
523 xfs_agnumber_t agno
= be32_to_cpu(agi
->agi_seqno
);
526 struct xfs_inobt_rec_incore rec
;
528 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, btnum
);
530 /* the new record is pre-aligned so we know where to look */
531 error
= xfs_inobt_lookup(cur
, nrec
->ir_startino
, XFS_LOOKUP_EQ
, &i
);
534 /* if nothing there, insert a new record and return */
536 error
= xfs_inobt_insert_rec(cur
, nrec
->ir_holemask
,
537 nrec
->ir_count
, nrec
->ir_freecount
,
541 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error
);
547 * A record exists at this startino. Merge or replace the record
548 * depending on what we've been asked to do.
551 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
554 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error
);
555 XFS_WANT_CORRUPTED_GOTO(mp
,
556 rec
.ir_startino
== nrec
->ir_startino
,
560 * This should never fail. If we have coexisting records that
561 * cannot merge, something is seriously wrong.
563 XFS_WANT_CORRUPTED_GOTO(mp
, __xfs_inobt_can_merge(nrec
, &rec
),
566 trace_xfs_irec_merge_pre(mp
, agno
, rec
.ir_startino
,
567 rec
.ir_holemask
, nrec
->ir_startino
,
570 /* merge to nrec to output the updated record */
571 __xfs_inobt_rec_merge(nrec
, &rec
);
573 trace_xfs_irec_merge_post(mp
, agno
, nrec
->ir_startino
,
576 error
= xfs_inobt_rec_check_count(mp
, nrec
);
581 error
= xfs_inobt_update(cur
, nrec
);
586 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
589 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
594 * Allocate new inodes in the allocation group specified by agbp.
595 * Return 0 for success, else error code.
597 STATIC
int /* error code or 0 */
599 xfs_trans_t
*tp
, /* transaction pointer */
600 xfs_buf_t
*agbp
, /* alloc group buffer */
603 xfs_agi_t
*agi
; /* allocation group header */
604 xfs_alloc_arg_t args
; /* allocation argument structure */
607 xfs_agino_t newino
; /* new first inode's number */
608 xfs_agino_t newlen
; /* new number of inodes */
609 int isaligned
= 0; /* inode allocation at stripe unit */
611 uint16_t allocmask
= (uint16_t) -1; /* init. to full chunk */
612 struct xfs_inobt_rec_incore rec
;
613 struct xfs_perag
*pag
;
616 memset(&args
, 0, sizeof(args
));
618 args
.mp
= tp
->t_mountp
;
619 args
.fsbno
= NULLFSBLOCK
;
620 xfs_rmap_ag_owner(&args
.oinfo
, XFS_RMAP_OWN_INODES
);
623 /* randomly do sparse inode allocations */
624 if (xfs_sb_version_hassparseinodes(&tp
->t_mountp
->m_sb
) &&
625 args
.mp
->m_ialloc_min_blks
< args
.mp
->m_ialloc_blks
)
626 do_sparse
= prandom_u32() & 1;
630 * Locking will ensure that we don't have two callers in here
633 newlen
= args
.mp
->m_ialloc_inos
;
634 if (args
.mp
->m_maxicount
&&
635 percpu_counter_read_positive(&args
.mp
->m_icount
) + newlen
>
636 args
.mp
->m_maxicount
)
638 args
.minlen
= args
.maxlen
= args
.mp
->m_ialloc_blks
;
640 * First try to allocate inodes contiguous with the last-allocated
641 * chunk of inodes. If the filesystem is striped, this will fill
642 * an entire stripe unit with inodes.
644 agi
= XFS_BUF_TO_AGI(agbp
);
645 newino
= be32_to_cpu(agi
->agi_newino
);
646 agno
= be32_to_cpu(agi
->agi_seqno
);
647 args
.agbno
= XFS_AGINO_TO_AGBNO(args
.mp
, newino
) +
648 args
.mp
->m_ialloc_blks
;
651 if (likely(newino
!= NULLAGINO
&&
652 (args
.agbno
< be32_to_cpu(agi
->agi_length
)))) {
653 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, agno
, args
.agbno
);
654 args
.type
= XFS_ALLOCTYPE_THIS_BNO
;
658 * We need to take into account alignment here to ensure that
659 * we don't modify the free list if we fail to have an exact
660 * block. If we don't have an exact match, and every oher
661 * attempt allocation attempt fails, we'll end up cancelling
662 * a dirty transaction and shutting down.
664 * For an exact allocation, alignment must be 1,
665 * however we need to take cluster alignment into account when
666 * fixing up the freelist. Use the minalignslop field to
667 * indicate that extra blocks might be required for alignment,
668 * but not to use them in the actual exact allocation.
671 args
.minalignslop
= xfs_ialloc_cluster_alignment(args
.mp
) - 1;
673 /* Allow space for the inode btree to split. */
674 args
.minleft
= args
.mp
->m_in_maxlevels
- 1;
675 if ((error
= xfs_alloc_vextent(&args
)))
679 * This request might have dirtied the transaction if the AG can
680 * satisfy the request, but the exact block was not available.
681 * If the allocation did fail, subsequent requests will relax
682 * the exact agbno requirement and increase the alignment
683 * instead. It is critical that the total size of the request
684 * (len + alignment + slop) does not increase from this point
685 * on, so reset minalignslop to ensure it is not included in
686 * subsequent requests.
688 args
.minalignslop
= 0;
691 if (unlikely(args
.fsbno
== NULLFSBLOCK
)) {
693 * Set the alignment for the allocation.
694 * If stripe alignment is turned on then align at stripe unit
696 * If the cluster size is smaller than a filesystem block
697 * then we're doing I/O for inodes in filesystem block size
698 * pieces, so don't need alignment anyway.
701 if (args
.mp
->m_sinoalign
) {
702 ASSERT(!(args
.mp
->m_flags
& XFS_MOUNT_NOALIGN
));
703 args
.alignment
= args
.mp
->m_dalign
;
706 args
.alignment
= xfs_ialloc_cluster_alignment(args
.mp
);
708 * Need to figure out where to allocate the inode blocks.
709 * Ideally they should be spaced out through the a.g.
710 * For now, just allocate blocks up front.
712 args
.agbno
= be32_to_cpu(agi
->agi_root
);
713 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, agno
, args
.agbno
);
715 * Allocate a fixed-size extent of inodes.
717 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
720 * Allow space for the inode btree to split.
722 args
.minleft
= args
.mp
->m_in_maxlevels
- 1;
723 if ((error
= xfs_alloc_vextent(&args
)))
728 * If stripe alignment is turned on, then try again with cluster
731 if (isaligned
&& args
.fsbno
== NULLFSBLOCK
) {
732 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
733 args
.agbno
= be32_to_cpu(agi
->agi_root
);
734 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, agno
, args
.agbno
);
735 args
.alignment
= xfs_ialloc_cluster_alignment(args
.mp
);
736 if ((error
= xfs_alloc_vextent(&args
)))
741 * Finally, try a sparse allocation if the filesystem supports it and
742 * the sparse allocation length is smaller than a full chunk.
744 if (xfs_sb_version_hassparseinodes(&args
.mp
->m_sb
) &&
745 args
.mp
->m_ialloc_min_blks
< args
.mp
->m_ialloc_blks
&&
746 args
.fsbno
== NULLFSBLOCK
) {
748 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
749 args
.agbno
= be32_to_cpu(agi
->agi_root
);
750 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, agno
, args
.agbno
);
751 args
.alignment
= args
.mp
->m_sb
.sb_spino_align
;
754 args
.minlen
= args
.mp
->m_ialloc_min_blks
;
755 args
.maxlen
= args
.minlen
;
758 * The inode record will be aligned to full chunk size. We must
759 * prevent sparse allocation from AG boundaries that result in
760 * invalid inode records, such as records that start at agbno 0
761 * or extend beyond the AG.
763 * Set min agbno to the first aligned, non-zero agbno and max to
764 * the last aligned agbno that is at least one full chunk from
767 args
.min_agbno
= args
.mp
->m_sb
.sb_inoalignmt
;
768 args
.max_agbno
= round_down(args
.mp
->m_sb
.sb_agblocks
,
769 args
.mp
->m_sb
.sb_inoalignmt
) -
770 args
.mp
->m_ialloc_blks
;
772 error
= xfs_alloc_vextent(&args
);
776 newlen
= args
.len
<< args
.mp
->m_sb
.sb_inopblog
;
777 ASSERT(newlen
<= XFS_INODES_PER_CHUNK
);
778 allocmask
= (1 << (newlen
/ XFS_INODES_PER_HOLEMASK_BIT
)) - 1;
781 if (args
.fsbno
== NULLFSBLOCK
) {
785 ASSERT(args
.len
== args
.minlen
);
788 * Stamp and write the inode buffers.
790 * Seed the new inode cluster with a random generation number. This
791 * prevents short-term reuse of generation numbers if a chunk is
792 * freed and then immediately reallocated. We use random numbers
793 * rather than a linear progression to prevent the next generation
794 * number from being easily guessable.
796 error
= xfs_ialloc_inode_init(args
.mp
, tp
, NULL
, newlen
, agno
,
797 args
.agbno
, args
.len
, prandom_u32());
802 * Convert the results.
804 newino
= XFS_OFFBNO_TO_AGINO(args
.mp
, args
.agbno
, 0);
806 if (xfs_inobt_issparse(~allocmask
)) {
808 * We've allocated a sparse chunk. Align the startino and mask.
810 xfs_align_sparse_ino(args
.mp
, &newino
, &allocmask
);
812 rec
.ir_startino
= newino
;
813 rec
.ir_holemask
= ~allocmask
;
814 rec
.ir_count
= newlen
;
815 rec
.ir_freecount
= newlen
;
816 rec
.ir_free
= XFS_INOBT_ALL_FREE
;
819 * Insert the sparse record into the inobt and allow for a merge
820 * if necessary. If a merge does occur, rec is updated to the
823 error
= xfs_inobt_insert_sprec(args
.mp
, tp
, agbp
, XFS_BTNUM_INO
,
825 if (error
== -EFSCORRUPTED
) {
827 "invalid sparse inode record: ino 0x%llx holemask 0x%x count %u",
828 XFS_AGINO_TO_INO(args
.mp
, agno
,
830 rec
.ir_holemask
, rec
.ir_count
);
831 xfs_force_shutdown(args
.mp
, SHUTDOWN_CORRUPT_INCORE
);
837 * We can't merge the part we've just allocated as for the inobt
838 * due to finobt semantics. The original record may or may not
839 * exist independent of whether physical inodes exist in this
842 * We must update the finobt record based on the inobt record.
843 * rec contains the fully merged and up to date inobt record
844 * from the previous call. Set merge false to replace any
845 * existing record with this one.
847 if (xfs_sb_version_hasfinobt(&args
.mp
->m_sb
)) {
848 error
= xfs_inobt_insert_sprec(args
.mp
, tp
, agbp
,
849 XFS_BTNUM_FINO
, &rec
,
855 /* full chunk - insert new records to both btrees */
856 error
= xfs_inobt_insert(args
.mp
, tp
, agbp
, newino
, newlen
,
861 if (xfs_sb_version_hasfinobt(&args
.mp
->m_sb
)) {
862 error
= xfs_inobt_insert(args
.mp
, tp
, agbp
, newino
,
863 newlen
, XFS_BTNUM_FINO
);
870 * Update AGI counts and newino.
872 be32_add_cpu(&agi
->agi_count
, newlen
);
873 be32_add_cpu(&agi
->agi_freecount
, newlen
);
874 pag
= xfs_perag_get(args
.mp
, agno
);
875 pag
->pagi_freecount
+= newlen
;
877 agi
->agi_newino
= cpu_to_be32(newino
);
880 * Log allocation group header fields
882 xfs_ialloc_log_agi(tp
, agbp
,
883 XFS_AGI_COUNT
| XFS_AGI_FREECOUNT
| XFS_AGI_NEWINO
);
885 * Modify/log superblock values for inode count and inode free count.
887 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_ICOUNT
, (long)newlen
);
888 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_IFREE
, (long)newlen
);
893 STATIC xfs_agnumber_t
899 spin_lock(&mp
->m_agirotor_lock
);
900 agno
= mp
->m_agirotor
;
901 if (++mp
->m_agirotor
>= mp
->m_maxagi
)
903 spin_unlock(&mp
->m_agirotor_lock
);
909 * Select an allocation group to look for a free inode in, based on the parent
910 * inode and the mode. Return the allocation group buffer.
912 STATIC xfs_agnumber_t
913 xfs_ialloc_ag_select(
914 xfs_trans_t
*tp
, /* transaction pointer */
915 xfs_ino_t parent
, /* parent directory inode number */
916 umode_t mode
, /* bits set to indicate file type */
917 int okalloc
) /* ok to allocate more space */
919 xfs_agnumber_t agcount
; /* number of ag's in the filesystem */
920 xfs_agnumber_t agno
; /* current ag number */
921 int flags
; /* alloc buffer locking flags */
922 xfs_extlen_t ineed
; /* blocks needed for inode allocation */
923 xfs_extlen_t longest
= 0; /* longest extent available */
924 xfs_mount_t
*mp
; /* mount point structure */
925 int needspace
; /* file mode implies space allocated */
926 xfs_perag_t
*pag
; /* per allocation group data */
927 xfs_agnumber_t pagno
; /* parent (starting) ag number */
931 * Files of these types need at least one block if length > 0
932 * (and they won't fit in the inode, but that's hard to figure out).
934 needspace
= S_ISDIR(mode
) || S_ISREG(mode
) || S_ISLNK(mode
);
936 agcount
= mp
->m_maxagi
;
938 pagno
= xfs_ialloc_next_ag(mp
);
940 pagno
= XFS_INO_TO_AGNO(mp
, parent
);
941 if (pagno
>= agcount
)
945 ASSERT(pagno
< agcount
);
948 * Loop through allocation groups, looking for one with a little
949 * free space in it. Note we don't look for free inodes, exactly.
950 * Instead, we include whether there is a need to allocate inodes
951 * to mean that blocks must be allocated for them,
952 * if none are currently free.
955 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
957 pag
= xfs_perag_get(mp
, agno
);
958 if (!pag
->pagi_inodeok
) {
959 xfs_ialloc_next_ag(mp
);
963 if (!pag
->pagi_init
) {
964 error
= xfs_ialloc_pagi_init(mp
, tp
, agno
);
969 if (pag
->pagi_freecount
) {
977 if (!pag
->pagf_init
) {
978 error
= xfs_alloc_pagf_init(mp
, tp
, agno
, flags
);
984 * Check that there is enough free space for the file plus a
985 * chunk of inodes if we need to allocate some. If this is the
986 * first pass across the AGs, take into account the potential
987 * space needed for alignment of inode chunks when checking the
988 * longest contiguous free space in the AG - this prevents us
989 * from getting ENOSPC because we have free space larger than
990 * m_ialloc_blks but alignment constraints prevent us from using
993 * If we can't find an AG with space for full alignment slack to
994 * be taken into account, we must be near ENOSPC in all AGs.
995 * Hence we don't include alignment for the second pass and so
996 * if we fail allocation due to alignment issues then it is most
997 * likely a real ENOSPC condition.
999 ineed
= mp
->m_ialloc_min_blks
;
1000 if (flags
&& ineed
> 1)
1001 ineed
+= xfs_ialloc_cluster_alignment(mp
);
1002 longest
= pag
->pagf_longest
;
1004 longest
= pag
->pagf_flcount
> 0;
1006 if (pag
->pagf_freeblks
>= needspace
+ ineed
&&
1014 * No point in iterating over the rest, if we're shutting
1017 if (XFS_FORCED_SHUTDOWN(mp
))
1018 return NULLAGNUMBER
;
1020 if (agno
>= agcount
)
1022 if (agno
== pagno
) {
1024 return NULLAGNUMBER
;
1031 * Try to retrieve the next record to the left/right from the current one.
1034 xfs_ialloc_next_rec(
1035 struct xfs_btree_cur
*cur
,
1036 xfs_inobt_rec_incore_t
*rec
,
1044 error
= xfs_btree_decrement(cur
, 0, &i
);
1046 error
= xfs_btree_increment(cur
, 0, &i
);
1052 error
= xfs_inobt_get_rec(cur
, rec
, &i
);
1055 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1063 struct xfs_btree_cur
*cur
,
1065 xfs_inobt_rec_incore_t
*rec
,
1071 error
= xfs_inobt_lookup(cur
, agino
, XFS_LOOKUP_EQ
, &i
);
1076 error
= xfs_inobt_get_rec(cur
, rec
, &i
);
1079 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1086 * Return the offset of the first free inode in the record. If the inode chunk
1087 * is sparsely allocated, we convert the record holemask to inode granularity
1088 * and mask off the unallocated regions from the inode free mask.
1091 xfs_inobt_first_free_inode(
1092 struct xfs_inobt_rec_incore
*rec
)
1094 xfs_inofree_t realfree
;
1096 /* if there are no holes, return the first available offset */
1097 if (!xfs_inobt_issparse(rec
->ir_holemask
))
1098 return xfs_lowbit64(rec
->ir_free
);
1100 realfree
= xfs_inobt_irec_to_allocmask(rec
);
1101 realfree
&= rec
->ir_free
;
1103 return xfs_lowbit64(realfree
);
1107 * Allocate an inode using the inobt-only algorithm.
1110 xfs_dialloc_ag_inobt(
1111 struct xfs_trans
*tp
,
1112 struct xfs_buf
*agbp
,
1116 struct xfs_mount
*mp
= tp
->t_mountp
;
1117 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
1118 xfs_agnumber_t agno
= be32_to_cpu(agi
->agi_seqno
);
1119 xfs_agnumber_t pagno
= XFS_INO_TO_AGNO(mp
, parent
);
1120 xfs_agino_t pagino
= XFS_INO_TO_AGINO(mp
, parent
);
1121 struct xfs_perag
*pag
;
1122 struct xfs_btree_cur
*cur
, *tcur
;
1123 struct xfs_inobt_rec_incore rec
, trec
;
1128 int searchdistance
= 10;
1130 pag
= xfs_perag_get(mp
, agno
);
1132 ASSERT(pag
->pagi_init
);
1133 ASSERT(pag
->pagi_inodeok
);
1134 ASSERT(pag
->pagi_freecount
> 0);
1137 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_INO
);
1139 * If pagino is 0 (this is the root inode allocation) use newino.
1140 * This must work because we've just allocated some.
1143 pagino
= be32_to_cpu(agi
->agi_newino
);
1145 error
= xfs_check_agi_freecount(cur
, agi
);
1150 * If in the same AG as the parent, try to get near the parent.
1152 if (pagno
== agno
) {
1153 int doneleft
; /* done, to the left */
1154 int doneright
; /* done, to the right */
1156 error
= xfs_inobt_lookup(cur
, pagino
, XFS_LOOKUP_LE
, &i
);
1159 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1161 error
= xfs_inobt_get_rec(cur
, &rec
, &j
);
1164 XFS_WANT_CORRUPTED_GOTO(mp
, j
== 1, error0
);
1166 if (rec
.ir_freecount
> 0) {
1168 * Found a free inode in the same chunk
1169 * as the parent, done.
1176 * In the same AG as parent, but parent's chunk is full.
1179 /* duplicate the cursor, search left & right simultaneously */
1180 error
= xfs_btree_dup_cursor(cur
, &tcur
);
1185 * Skip to last blocks looked up if same parent inode.
1187 if (pagino
!= NULLAGINO
&&
1188 pag
->pagl_pagino
== pagino
&&
1189 pag
->pagl_leftrec
!= NULLAGINO
&&
1190 pag
->pagl_rightrec
!= NULLAGINO
) {
1191 error
= xfs_ialloc_get_rec(tcur
, pag
->pagl_leftrec
,
1196 error
= xfs_ialloc_get_rec(cur
, pag
->pagl_rightrec
,
1201 /* search left with tcur, back up 1 record */
1202 error
= xfs_ialloc_next_rec(tcur
, &trec
, &doneleft
, 1);
1206 /* search right with cur, go forward 1 record. */
1207 error
= xfs_ialloc_next_rec(cur
, &rec
, &doneright
, 0);
1213 * Loop until we find an inode chunk with a free inode.
1215 while (--searchdistance
> 0 && (!doneleft
|| !doneright
)) {
1216 int useleft
; /* using left inode chunk this time */
1218 /* figure out the closer block if both are valid. */
1219 if (!doneleft
&& !doneright
) {
1221 (trec
.ir_startino
+ XFS_INODES_PER_CHUNK
- 1) <
1222 rec
.ir_startino
- pagino
;
1224 useleft
= !doneleft
;
1227 /* free inodes to the left? */
1228 if (useleft
&& trec
.ir_freecount
) {
1229 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
1232 pag
->pagl_leftrec
= trec
.ir_startino
;
1233 pag
->pagl_rightrec
= rec
.ir_startino
;
1234 pag
->pagl_pagino
= pagino
;
1239 /* free inodes to the right? */
1240 if (!useleft
&& rec
.ir_freecount
) {
1241 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1243 pag
->pagl_leftrec
= trec
.ir_startino
;
1244 pag
->pagl_rightrec
= rec
.ir_startino
;
1245 pag
->pagl_pagino
= pagino
;
1249 /* get next record to check */
1251 error
= xfs_ialloc_next_rec(tcur
, &trec
,
1254 error
= xfs_ialloc_next_rec(cur
, &rec
,
1261 if (searchdistance
<= 0) {
1263 * Not in range - save last search
1264 * location and allocate a new inode
1266 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1267 pag
->pagl_leftrec
= trec
.ir_startino
;
1268 pag
->pagl_rightrec
= rec
.ir_startino
;
1269 pag
->pagl_pagino
= pagino
;
1273 * We've reached the end of the btree. because
1274 * we are only searching a small chunk of the
1275 * btree each search, there is obviously free
1276 * inodes closer to the parent inode than we
1277 * are now. restart the search again.
1279 pag
->pagl_pagino
= NULLAGINO
;
1280 pag
->pagl_leftrec
= NULLAGINO
;
1281 pag
->pagl_rightrec
= NULLAGINO
;
1282 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
1283 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
1289 * In a different AG from the parent.
1290 * See if the most recently allocated block has any free.
1292 if (agi
->agi_newino
!= cpu_to_be32(NULLAGINO
)) {
1293 error
= xfs_inobt_lookup(cur
, be32_to_cpu(agi
->agi_newino
),
1299 error
= xfs_inobt_get_rec(cur
, &rec
, &j
);
1303 if (j
== 1 && rec
.ir_freecount
> 0) {
1305 * The last chunk allocated in the group
1306 * still has a free inode.
1314 * None left in the last group, search the whole AG
1316 error
= xfs_inobt_lookup(cur
, 0, XFS_LOOKUP_GE
, &i
);
1319 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1322 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
1325 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1326 if (rec
.ir_freecount
> 0)
1328 error
= xfs_btree_increment(cur
, 0, &i
);
1331 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1335 offset
= xfs_inobt_first_free_inode(&rec
);
1336 ASSERT(offset
>= 0);
1337 ASSERT(offset
< XFS_INODES_PER_CHUNK
);
1338 ASSERT((XFS_AGINO_TO_OFFSET(mp
, rec
.ir_startino
) %
1339 XFS_INODES_PER_CHUNK
) == 0);
1340 ino
= XFS_AGINO_TO_INO(mp
, agno
, rec
.ir_startino
+ offset
);
1341 rec
.ir_free
&= ~XFS_INOBT_MASK(offset
);
1343 error
= xfs_inobt_update(cur
, &rec
);
1346 be32_add_cpu(&agi
->agi_freecount
, -1);
1347 xfs_ialloc_log_agi(tp
, agbp
, XFS_AGI_FREECOUNT
);
1348 pag
->pagi_freecount
--;
1350 error
= xfs_check_agi_freecount(cur
, agi
);
1354 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
1355 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_IFREE
, -1);
1360 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
1362 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
1368 * Use the free inode btree to allocate an inode based on distance from the
1369 * parent. Note that the provided cursor may be deleted and replaced.
1372 xfs_dialloc_ag_finobt_near(
1374 struct xfs_btree_cur
**ocur
,
1375 struct xfs_inobt_rec_incore
*rec
)
1377 struct xfs_btree_cur
*lcur
= *ocur
; /* left search cursor */
1378 struct xfs_btree_cur
*rcur
; /* right search cursor */
1379 struct xfs_inobt_rec_incore rrec
;
1383 error
= xfs_inobt_lookup(lcur
, pagino
, XFS_LOOKUP_LE
, &i
);
1388 error
= xfs_inobt_get_rec(lcur
, rec
, &i
);
1391 XFS_WANT_CORRUPTED_RETURN(lcur
->bc_mp
, i
== 1);
1394 * See if we've landed in the parent inode record. The finobt
1395 * only tracks chunks with at least one free inode, so record
1396 * existence is enough.
1398 if (pagino
>= rec
->ir_startino
&&
1399 pagino
< (rec
->ir_startino
+ XFS_INODES_PER_CHUNK
))
1403 error
= xfs_btree_dup_cursor(lcur
, &rcur
);
1407 error
= xfs_inobt_lookup(rcur
, pagino
, XFS_LOOKUP_GE
, &j
);
1411 error
= xfs_inobt_get_rec(rcur
, &rrec
, &j
);
1414 XFS_WANT_CORRUPTED_GOTO(lcur
->bc_mp
, j
== 1, error_rcur
);
1417 XFS_WANT_CORRUPTED_GOTO(lcur
->bc_mp
, i
== 1 || j
== 1, error_rcur
);
1418 if (i
== 1 && j
== 1) {
1420 * Both the left and right records are valid. Choose the closer
1421 * inode chunk to the target.
1423 if ((pagino
- rec
->ir_startino
+ XFS_INODES_PER_CHUNK
- 1) >
1424 (rrec
.ir_startino
- pagino
)) {
1426 xfs_btree_del_cursor(lcur
, XFS_BTREE_NOERROR
);
1429 xfs_btree_del_cursor(rcur
, XFS_BTREE_NOERROR
);
1431 } else if (j
== 1) {
1432 /* only the right record is valid */
1434 xfs_btree_del_cursor(lcur
, XFS_BTREE_NOERROR
);
1436 } else if (i
== 1) {
1437 /* only the left record is valid */
1438 xfs_btree_del_cursor(rcur
, XFS_BTREE_NOERROR
);
1444 xfs_btree_del_cursor(rcur
, XFS_BTREE_ERROR
);
1449 * Use the free inode btree to find a free inode based on a newino hint. If
1450 * the hint is NULL, find the first free inode in the AG.
1453 xfs_dialloc_ag_finobt_newino(
1454 struct xfs_agi
*agi
,
1455 struct xfs_btree_cur
*cur
,
1456 struct xfs_inobt_rec_incore
*rec
)
1461 if (agi
->agi_newino
!= cpu_to_be32(NULLAGINO
)) {
1462 error
= xfs_inobt_lookup(cur
, be32_to_cpu(agi
->agi_newino
),
1467 error
= xfs_inobt_get_rec(cur
, rec
, &i
);
1470 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1476 * Find the first inode available in the AG.
1478 error
= xfs_inobt_lookup(cur
, 0, XFS_LOOKUP_GE
, &i
);
1481 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1483 error
= xfs_inobt_get_rec(cur
, rec
, &i
);
1486 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1492 * Update the inobt based on a modification made to the finobt. Also ensure that
1493 * the records from both trees are equivalent post-modification.
1496 xfs_dialloc_ag_update_inobt(
1497 struct xfs_btree_cur
*cur
, /* inobt cursor */
1498 struct xfs_inobt_rec_incore
*frec
, /* finobt record */
1499 int offset
) /* inode offset */
1501 struct xfs_inobt_rec_incore rec
;
1505 error
= xfs_inobt_lookup(cur
, frec
->ir_startino
, XFS_LOOKUP_EQ
, &i
);
1508 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1510 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
1513 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
1514 ASSERT((XFS_AGINO_TO_OFFSET(cur
->bc_mp
, rec
.ir_startino
) %
1515 XFS_INODES_PER_CHUNK
) == 0);
1517 rec
.ir_free
&= ~XFS_INOBT_MASK(offset
);
1520 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, (rec
.ir_free
== frec
->ir_free
) &&
1521 (rec
.ir_freecount
== frec
->ir_freecount
));
1523 return xfs_inobt_update(cur
, &rec
);
1527 * Allocate an inode using the free inode btree, if available. Otherwise, fall
1528 * back to the inobt search algorithm.
1530 * The caller selected an AG for us, and made sure that free inodes are
1535 struct xfs_trans
*tp
,
1536 struct xfs_buf
*agbp
,
1540 struct xfs_mount
*mp
= tp
->t_mountp
;
1541 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
1542 xfs_agnumber_t agno
= be32_to_cpu(agi
->agi_seqno
);
1543 xfs_agnumber_t pagno
= XFS_INO_TO_AGNO(mp
, parent
);
1544 xfs_agino_t pagino
= XFS_INO_TO_AGINO(mp
, parent
);
1545 struct xfs_perag
*pag
;
1546 struct xfs_btree_cur
*cur
; /* finobt cursor */
1547 struct xfs_btree_cur
*icur
; /* inobt cursor */
1548 struct xfs_inobt_rec_incore rec
;
1554 if (!xfs_sb_version_hasfinobt(&mp
->m_sb
))
1555 return xfs_dialloc_ag_inobt(tp
, agbp
, parent
, inop
);
1557 pag
= xfs_perag_get(mp
, agno
);
1560 * If pagino is 0 (this is the root inode allocation) use newino.
1561 * This must work because we've just allocated some.
1564 pagino
= be32_to_cpu(agi
->agi_newino
);
1566 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_FINO
);
1568 error
= xfs_check_agi_freecount(cur
, agi
);
1573 * The search algorithm depends on whether we're in the same AG as the
1574 * parent. If so, find the closest available inode to the parent. If
1575 * not, consider the agi hint or find the first free inode in the AG.
1578 error
= xfs_dialloc_ag_finobt_near(pagino
, &cur
, &rec
);
1580 error
= xfs_dialloc_ag_finobt_newino(agi
, cur
, &rec
);
1584 offset
= xfs_inobt_first_free_inode(&rec
);
1585 ASSERT(offset
>= 0);
1586 ASSERT(offset
< XFS_INODES_PER_CHUNK
);
1587 ASSERT((XFS_AGINO_TO_OFFSET(mp
, rec
.ir_startino
) %
1588 XFS_INODES_PER_CHUNK
) == 0);
1589 ino
= XFS_AGINO_TO_INO(mp
, agno
, rec
.ir_startino
+ offset
);
1592 * Modify or remove the finobt record.
1594 rec
.ir_free
&= ~XFS_INOBT_MASK(offset
);
1596 if (rec
.ir_freecount
)
1597 error
= xfs_inobt_update(cur
, &rec
);
1599 error
= xfs_btree_delete(cur
, &i
);
1604 * The finobt has now been updated appropriately. We haven't updated the
1605 * agi and superblock yet, so we can create an inobt cursor and validate
1606 * the original freecount. If all is well, make the equivalent update to
1607 * the inobt using the finobt record and offset information.
1609 icur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_INO
);
1611 error
= xfs_check_agi_freecount(icur
, agi
);
1615 error
= xfs_dialloc_ag_update_inobt(icur
, &rec
, offset
);
1620 * Both trees have now been updated. We must update the perag and
1621 * superblock before we can check the freecount for each btree.
1623 be32_add_cpu(&agi
->agi_freecount
, -1);
1624 xfs_ialloc_log_agi(tp
, agbp
, XFS_AGI_FREECOUNT
);
1625 pag
->pagi_freecount
--;
1627 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_IFREE
, -1);
1629 error
= xfs_check_agi_freecount(icur
, agi
);
1632 error
= xfs_check_agi_freecount(cur
, agi
);
1636 xfs_btree_del_cursor(icur
, XFS_BTREE_NOERROR
);
1637 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
1643 xfs_btree_del_cursor(icur
, XFS_BTREE_ERROR
);
1645 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
1651 * Allocate an inode on disk.
1653 * Mode is used to tell whether the new inode will need space, and whether it
1656 * This function is designed to be called twice if it has to do an allocation
1657 * to make more free inodes. On the first call, *IO_agbp should be set to NULL.
1658 * If an inode is available without having to performn an allocation, an inode
1659 * number is returned. In this case, *IO_agbp is set to NULL. If an allocation
1660 * needs to be done, xfs_dialloc returns the current AGI buffer in *IO_agbp.
1661 * The caller should then commit the current transaction, allocate a
1662 * new transaction, and call xfs_dialloc() again, passing in the previous value
1663 * of *IO_agbp. IO_agbp should be held across the transactions. Since the AGI
1664 * buffer is locked across the two calls, the second call is guaranteed to have
1665 * a free inode available.
1667 * Once we successfully pick an inode its number is returned and the on-disk
1668 * data structures are updated. The inode itself is not read in, since doing so
1669 * would break ordering constraints with xfs_reclaim.
1673 struct xfs_trans
*tp
,
1677 struct xfs_buf
**IO_agbp
,
1680 struct xfs_mount
*mp
= tp
->t_mountp
;
1681 struct xfs_buf
*agbp
;
1682 xfs_agnumber_t agno
;
1686 xfs_agnumber_t start_agno
;
1687 struct xfs_perag
*pag
;
1691 * If the caller passes in a pointer to the AGI buffer,
1692 * continue where we left off before. In this case, we
1693 * know that the allocation group has free inodes.
1700 * We do not have an agbp, so select an initial allocation
1701 * group for inode allocation.
1703 start_agno
= xfs_ialloc_ag_select(tp
, parent
, mode
, okalloc
);
1704 if (start_agno
== NULLAGNUMBER
) {
1710 * If we have already hit the ceiling of inode blocks then clear
1711 * okalloc so we scan all available agi structures for a free
1714 * Read rough value of mp->m_icount by percpu_counter_read_positive,
1715 * which will sacrifice the preciseness but improve the performance.
1717 if (mp
->m_maxicount
&&
1718 percpu_counter_read_positive(&mp
->m_icount
) + mp
->m_ialloc_inos
1719 > mp
->m_maxicount
) {
1725 * Loop until we find an allocation group that either has free inodes
1726 * or in which we can allocate some inodes. Iterate through the
1727 * allocation groups upward, wrapping at the end.
1731 pag
= xfs_perag_get(mp
, agno
);
1732 if (!pag
->pagi_inodeok
) {
1733 xfs_ialloc_next_ag(mp
);
1737 if (!pag
->pagi_init
) {
1738 error
= xfs_ialloc_pagi_init(mp
, tp
, agno
);
1744 * Do a first racy fast path check if this AG is usable.
1746 if (!pag
->pagi_freecount
&& !okalloc
)
1750 * Then read in the AGI buffer and recheck with the AGI buffer
1753 error
= xfs_ialloc_read_agi(mp
, tp
, agno
, &agbp
);
1757 if (pag
->pagi_freecount
) {
1763 goto nextag_relse_buffer
;
1766 error
= xfs_ialloc_ag_alloc(tp
, agbp
, &ialloced
);
1768 xfs_trans_brelse(tp
, agbp
);
1770 if (error
!= -ENOSPC
)
1780 * We successfully allocated some inodes, return
1781 * the current context to the caller so that it
1782 * can commit the current transaction and call
1783 * us again where we left off.
1785 ASSERT(pag
->pagi_freecount
> 0);
1793 nextag_relse_buffer
:
1794 xfs_trans_brelse(tp
, agbp
);
1797 if (++agno
== mp
->m_sb
.sb_agcount
)
1799 if (agno
== start_agno
) {
1801 return noroom
? -ENOSPC
: 0;
1807 return xfs_dialloc_ag(tp
, agbp
, parent
, inop
);
1814 * Free the blocks of an inode chunk. We must consider that the inode chunk
1815 * might be sparse and only free the regions that are allocated as part of the
1819 xfs_difree_inode_chunk(
1820 struct xfs_mount
*mp
,
1821 xfs_agnumber_t agno
,
1822 struct xfs_inobt_rec_incore
*rec
,
1823 struct xfs_defer_ops
*dfops
)
1825 xfs_agblock_t sagbno
= XFS_AGINO_TO_AGBNO(mp
, rec
->ir_startino
);
1826 int startidx
, endidx
;
1828 xfs_agblock_t agbno
;
1830 struct xfs_owner_info oinfo
;
1831 DECLARE_BITMAP(holemask
, XFS_INOBT_HOLEMASK_BITS
);
1832 xfs_rmap_ag_owner(&oinfo
, XFS_RMAP_OWN_INODES
);
1834 if (!xfs_inobt_issparse(rec
->ir_holemask
)) {
1835 /* not sparse, calculate extent info directly */
1836 xfs_bmap_add_free(mp
, dfops
, XFS_AGB_TO_FSB(mp
, agno
, sagbno
),
1837 mp
->m_ialloc_blks
, &oinfo
);
1841 /* holemask is only 16-bits (fits in an unsigned long) */
1842 ASSERT(sizeof(rec
->ir_holemask
) <= sizeof(holemask
[0]));
1843 holemask
[0] = rec
->ir_holemask
;
1846 * Find contiguous ranges of zeroes (i.e., allocated regions) in the
1847 * holemask and convert the start/end index of each range to an extent.
1848 * We start with the start and end index both pointing at the first 0 in
1851 startidx
= endidx
= find_first_zero_bit(holemask
,
1852 XFS_INOBT_HOLEMASK_BITS
);
1853 nextbit
= startidx
+ 1;
1854 while (startidx
< XFS_INOBT_HOLEMASK_BITS
) {
1855 nextbit
= find_next_zero_bit(holemask
, XFS_INOBT_HOLEMASK_BITS
,
1858 * If the next zero bit is contiguous, update the end index of
1859 * the current range and continue.
1861 if (nextbit
!= XFS_INOBT_HOLEMASK_BITS
&&
1862 nextbit
== endidx
+ 1) {
1868 * nextbit is not contiguous with the current end index. Convert
1869 * the current start/end to an extent and add it to the free
1872 agbno
= sagbno
+ (startidx
* XFS_INODES_PER_HOLEMASK_BIT
) /
1873 mp
->m_sb
.sb_inopblock
;
1874 contigblk
= ((endidx
- startidx
+ 1) *
1875 XFS_INODES_PER_HOLEMASK_BIT
) /
1876 mp
->m_sb
.sb_inopblock
;
1878 ASSERT(agbno
% mp
->m_sb
.sb_spino_align
== 0);
1879 ASSERT(contigblk
% mp
->m_sb
.sb_spino_align
== 0);
1880 xfs_bmap_add_free(mp
, dfops
, XFS_AGB_TO_FSB(mp
, agno
, agbno
),
1883 /* reset range to current bit and carry on... */
1884 startidx
= endidx
= nextbit
;
1893 struct xfs_mount
*mp
,
1894 struct xfs_trans
*tp
,
1895 struct xfs_buf
*agbp
,
1897 struct xfs_defer_ops
*dfops
,
1898 struct xfs_icluster
*xic
,
1899 struct xfs_inobt_rec_incore
*orec
)
1901 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
1902 xfs_agnumber_t agno
= be32_to_cpu(agi
->agi_seqno
);
1903 struct xfs_perag
*pag
;
1904 struct xfs_btree_cur
*cur
;
1905 struct xfs_inobt_rec_incore rec
;
1911 ASSERT(agi
->agi_magicnum
== cpu_to_be32(XFS_AGI_MAGIC
));
1912 ASSERT(XFS_AGINO_TO_AGBNO(mp
, agino
) < be32_to_cpu(agi
->agi_length
));
1915 * Initialize the cursor.
1917 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_INO
);
1919 error
= xfs_check_agi_freecount(cur
, agi
);
1924 * Look for the entry describing this inode.
1926 if ((error
= xfs_inobt_lookup(cur
, agino
, XFS_LOOKUP_LE
, &i
))) {
1927 xfs_warn(mp
, "%s: xfs_inobt_lookup() returned error %d.",
1931 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1932 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
1934 xfs_warn(mp
, "%s: xfs_inobt_get_rec() returned error %d.",
1938 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1940 * Get the offset in the inode chunk.
1942 off
= agino
- rec
.ir_startino
;
1943 ASSERT(off
>= 0 && off
< XFS_INODES_PER_CHUNK
);
1944 ASSERT(!(rec
.ir_free
& XFS_INOBT_MASK(off
)));
1946 * Mark the inode free & increment the count.
1948 rec
.ir_free
|= XFS_INOBT_MASK(off
);
1952 * When an inode chunk is free, it becomes eligible for removal. Don't
1953 * remove the chunk if the block size is large enough for multiple inode
1954 * chunks (that might not be free).
1956 if (!(mp
->m_flags
& XFS_MOUNT_IKEEP
) &&
1957 rec
.ir_free
== XFS_INOBT_ALL_FREE
&&
1958 mp
->m_sb
.sb_inopblock
<= XFS_INODES_PER_CHUNK
) {
1959 xic
->deleted
= true;
1960 xic
->first_ino
= XFS_AGINO_TO_INO(mp
, agno
, rec
.ir_startino
);
1961 xic
->alloc
= xfs_inobt_irec_to_allocmask(&rec
);
1964 * Remove the inode cluster from the AGI B+Tree, adjust the
1965 * AGI and Superblock inode counts, and mark the disk space
1966 * to be freed when the transaction is committed.
1968 ilen
= rec
.ir_freecount
;
1969 be32_add_cpu(&agi
->agi_count
, -ilen
);
1970 be32_add_cpu(&agi
->agi_freecount
, -(ilen
- 1));
1971 xfs_ialloc_log_agi(tp
, agbp
, XFS_AGI_COUNT
| XFS_AGI_FREECOUNT
);
1972 pag
= xfs_perag_get(mp
, agno
);
1973 pag
->pagi_freecount
-= ilen
- 1;
1975 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_ICOUNT
, -ilen
);
1976 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_IFREE
, -(ilen
- 1));
1978 if ((error
= xfs_btree_delete(cur
, &i
))) {
1979 xfs_warn(mp
, "%s: xfs_btree_delete returned error %d.",
1984 xfs_difree_inode_chunk(mp
, agno
, &rec
, dfops
);
1986 xic
->deleted
= false;
1988 error
= xfs_inobt_update(cur
, &rec
);
1990 xfs_warn(mp
, "%s: xfs_inobt_update returned error %d.",
1996 * Change the inode free counts and log the ag/sb changes.
1998 be32_add_cpu(&agi
->agi_freecount
, 1);
1999 xfs_ialloc_log_agi(tp
, agbp
, XFS_AGI_FREECOUNT
);
2000 pag
= xfs_perag_get(mp
, agno
);
2001 pag
->pagi_freecount
++;
2003 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_IFREE
, 1);
2006 error
= xfs_check_agi_freecount(cur
, agi
);
2011 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
2015 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
2020 * Free an inode in the free inode btree.
2024 struct xfs_mount
*mp
,
2025 struct xfs_trans
*tp
,
2026 struct xfs_buf
*agbp
,
2028 struct xfs_inobt_rec_incore
*ibtrec
) /* inobt record */
2030 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
2031 xfs_agnumber_t agno
= be32_to_cpu(agi
->agi_seqno
);
2032 struct xfs_btree_cur
*cur
;
2033 struct xfs_inobt_rec_incore rec
;
2034 int offset
= agino
- ibtrec
->ir_startino
;
2038 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_FINO
);
2040 error
= xfs_inobt_lookup(cur
, ibtrec
->ir_startino
, XFS_LOOKUP_EQ
, &i
);
2045 * If the record does not exist in the finobt, we must have just
2046 * freed an inode in a previously fully allocated chunk. If not,
2047 * something is out of sync.
2049 XFS_WANT_CORRUPTED_GOTO(mp
, ibtrec
->ir_freecount
== 1, error
);
2051 error
= xfs_inobt_insert_rec(cur
, ibtrec
->ir_holemask
,
2053 ibtrec
->ir_freecount
,
2054 ibtrec
->ir_free
, &i
);
2063 * Read and update the existing record. We could just copy the ibtrec
2064 * across here, but that would defeat the purpose of having redundant
2065 * metadata. By making the modifications independently, we can catch
2066 * corruptions that we wouldn't see if we just copied from one record
2069 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
2072 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error
);
2074 rec
.ir_free
|= XFS_INOBT_MASK(offset
);
2077 XFS_WANT_CORRUPTED_GOTO(mp
, (rec
.ir_free
== ibtrec
->ir_free
) &&
2078 (rec
.ir_freecount
== ibtrec
->ir_freecount
),
2082 * The content of inobt records should always match between the inobt
2083 * and finobt. The lifecycle of records in the finobt is different from
2084 * the inobt in that the finobt only tracks records with at least one
2085 * free inode. Hence, if all of the inodes are free and we aren't
2086 * keeping inode chunks permanently on disk, remove the record.
2087 * Otherwise, update the record with the new information.
2089 * Note that we currently can't free chunks when the block size is large
2090 * enough for multiple chunks. Leave the finobt record to remain in sync
2093 if (rec
.ir_free
== XFS_INOBT_ALL_FREE
&&
2094 mp
->m_sb
.sb_inopblock
<= XFS_INODES_PER_CHUNK
&&
2095 !(mp
->m_flags
& XFS_MOUNT_IKEEP
)) {
2096 error
= xfs_btree_delete(cur
, &i
);
2101 error
= xfs_inobt_update(cur
, &rec
);
2107 error
= xfs_check_agi_freecount(cur
, agi
);
2111 xfs_btree_del_cursor(cur
, XFS_BTREE_NOERROR
);
2115 xfs_btree_del_cursor(cur
, XFS_BTREE_ERROR
);
2120 * Free disk inode. Carefully avoids touching the incore inode, all
2121 * manipulations incore are the caller's responsibility.
2122 * The on-disk inode is not changed by this operation, only the
2123 * btree (free inode mask) is changed.
2127 struct xfs_trans
*tp
, /* transaction pointer */
2128 xfs_ino_t inode
, /* inode to be freed */
2129 struct xfs_defer_ops
*dfops
, /* extents to free */
2130 struct xfs_icluster
*xic
) /* cluster info if deleted */
2133 xfs_agblock_t agbno
; /* block number containing inode */
2134 struct xfs_buf
*agbp
; /* buffer for allocation group header */
2135 xfs_agino_t agino
; /* allocation group inode number */
2136 xfs_agnumber_t agno
; /* allocation group number */
2137 int error
; /* error return value */
2138 struct xfs_mount
*mp
; /* mount structure for filesystem */
2139 struct xfs_inobt_rec_incore rec
;/* btree record */
2144 * Break up inode number into its components.
2146 agno
= XFS_INO_TO_AGNO(mp
, inode
);
2147 if (agno
>= mp
->m_sb
.sb_agcount
) {
2148 xfs_warn(mp
, "%s: agno >= mp->m_sb.sb_agcount (%d >= %d).",
2149 __func__
, agno
, mp
->m_sb
.sb_agcount
);
2153 agino
= XFS_INO_TO_AGINO(mp
, inode
);
2154 if (inode
!= XFS_AGINO_TO_INO(mp
, agno
, agino
)) {
2155 xfs_warn(mp
, "%s: inode != XFS_AGINO_TO_INO() (%llu != %llu).",
2156 __func__
, (unsigned long long)inode
,
2157 (unsigned long long)XFS_AGINO_TO_INO(mp
, agno
, agino
));
2161 agbno
= XFS_AGINO_TO_AGBNO(mp
, agino
);
2162 if (agbno
>= mp
->m_sb
.sb_agblocks
) {
2163 xfs_warn(mp
, "%s: agbno >= mp->m_sb.sb_agblocks (%d >= %d).",
2164 __func__
, agbno
, mp
->m_sb
.sb_agblocks
);
2169 * Get the allocation group header.
2171 error
= xfs_ialloc_read_agi(mp
, tp
, agno
, &agbp
);
2173 xfs_warn(mp
, "%s: xfs_ialloc_read_agi() returned error %d.",
2179 * Fix up the inode allocation btree.
2181 error
= xfs_difree_inobt(mp
, tp
, agbp
, agino
, dfops
, xic
, &rec
);
2186 * Fix up the free inode btree.
2188 if (xfs_sb_version_hasfinobt(&mp
->m_sb
)) {
2189 error
= xfs_difree_finobt(mp
, tp
, agbp
, agino
, &rec
);
2202 struct xfs_mount
*mp
,
2203 struct xfs_trans
*tp
,
2204 xfs_agnumber_t agno
,
2206 xfs_agblock_t agbno
,
2207 xfs_agblock_t
*chunk_agbno
,
2208 xfs_agblock_t
*offset_agbno
,
2211 struct xfs_inobt_rec_incore rec
;
2212 struct xfs_btree_cur
*cur
;
2213 struct xfs_buf
*agbp
;
2217 error
= xfs_ialloc_read_agi(mp
, tp
, agno
, &agbp
);
2220 "%s: xfs_ialloc_read_agi() returned error %d, agno %d",
2221 __func__
, error
, agno
);
2226 * Lookup the inode record for the given agino. If the record cannot be
2227 * found, then it's an invalid inode number and we should abort. Once
2228 * we have a record, we need to ensure it contains the inode number
2229 * we are looking up.
2231 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_INO
);
2232 error
= xfs_inobt_lookup(cur
, agino
, XFS_LOOKUP_LE
, &i
);
2235 error
= xfs_inobt_get_rec(cur
, &rec
, &i
);
2236 if (!error
&& i
== 0)
2240 xfs_trans_brelse(tp
, agbp
);
2241 xfs_btree_del_cursor(cur
, error
? XFS_BTREE_ERROR
: XFS_BTREE_NOERROR
);
2245 /* check that the returned record contains the required inode */
2246 if (rec
.ir_startino
> agino
||
2247 rec
.ir_startino
+ mp
->m_ialloc_inos
<= agino
)
2250 /* for untrusted inodes check it is allocated first */
2251 if ((flags
& XFS_IGET_UNTRUSTED
) &&
2252 (rec
.ir_free
& XFS_INOBT_MASK(agino
- rec
.ir_startino
)))
2255 *chunk_agbno
= XFS_AGINO_TO_AGBNO(mp
, rec
.ir_startino
);
2256 *offset_agbno
= agbno
- *chunk_agbno
;
2261 * Return the location of the inode in imap, for mapping it into a buffer.
2265 xfs_mount_t
*mp
, /* file system mount structure */
2266 xfs_trans_t
*tp
, /* transaction pointer */
2267 xfs_ino_t ino
, /* inode to locate */
2268 struct xfs_imap
*imap
, /* location map structure */
2269 uint flags
) /* flags for inode btree lookup */
2271 xfs_agblock_t agbno
; /* block number of inode in the alloc group */
2272 xfs_agino_t agino
; /* inode number within alloc group */
2273 xfs_agnumber_t agno
; /* allocation group number */
2274 int blks_per_cluster
; /* num blocks per inode cluster */
2275 xfs_agblock_t chunk_agbno
; /* first block in inode chunk */
2276 xfs_agblock_t cluster_agbno
; /* first block in inode cluster */
2277 int error
; /* error code */
2278 int offset
; /* index of inode in its buffer */
2279 xfs_agblock_t offset_agbno
; /* blks from chunk start to inode */
2281 ASSERT(ino
!= NULLFSINO
);
2284 * Split up the inode number into its parts.
2286 agno
= XFS_INO_TO_AGNO(mp
, ino
);
2287 agino
= XFS_INO_TO_AGINO(mp
, ino
);
2288 agbno
= XFS_AGINO_TO_AGBNO(mp
, agino
);
2289 if (agno
>= mp
->m_sb
.sb_agcount
|| agbno
>= mp
->m_sb
.sb_agblocks
||
2290 ino
!= XFS_AGINO_TO_INO(mp
, agno
, agino
)) {
2293 * Don't output diagnostic information for untrusted inodes
2294 * as they can be invalid without implying corruption.
2296 if (flags
& XFS_IGET_UNTRUSTED
)
2298 if (agno
>= mp
->m_sb
.sb_agcount
) {
2300 "%s: agno (%d) >= mp->m_sb.sb_agcount (%d)",
2301 __func__
, agno
, mp
->m_sb
.sb_agcount
);
2303 if (agbno
>= mp
->m_sb
.sb_agblocks
) {
2305 "%s: agbno (0x%llx) >= mp->m_sb.sb_agblocks (0x%lx)",
2306 __func__
, (unsigned long long)agbno
,
2307 (unsigned long)mp
->m_sb
.sb_agblocks
);
2309 if (ino
!= XFS_AGINO_TO_INO(mp
, agno
, agino
)) {
2311 "%s: ino (0x%llx) != XFS_AGINO_TO_INO() (0x%llx)",
2313 XFS_AGINO_TO_INO(mp
, agno
, agino
));
2320 blks_per_cluster
= xfs_icluster_size_fsb(mp
);
2323 * For bulkstat and handle lookups, we have an untrusted inode number
2324 * that we have to verify is valid. We cannot do this just by reading
2325 * the inode buffer as it may have been unlinked and removed leaving
2326 * inodes in stale state on disk. Hence we have to do a btree lookup
2327 * in all cases where an untrusted inode number is passed.
2329 if (flags
& XFS_IGET_UNTRUSTED
) {
2330 error
= xfs_imap_lookup(mp
, tp
, agno
, agino
, agbno
,
2331 &chunk_agbno
, &offset_agbno
, flags
);
2338 * If the inode cluster size is the same as the blocksize or
2339 * smaller we get to the buffer by simple arithmetics.
2341 if (blks_per_cluster
== 1) {
2342 offset
= XFS_INO_TO_OFFSET(mp
, ino
);
2343 ASSERT(offset
< mp
->m_sb
.sb_inopblock
);
2345 imap
->im_blkno
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
2346 imap
->im_len
= XFS_FSB_TO_BB(mp
, 1);
2347 imap
->im_boffset
= (unsigned short)(offset
<<
2348 mp
->m_sb
.sb_inodelog
);
2353 * If the inode chunks are aligned then use simple maths to
2354 * find the location. Otherwise we have to do a btree
2355 * lookup to find the location.
2357 if (mp
->m_inoalign_mask
) {
2358 offset_agbno
= agbno
& mp
->m_inoalign_mask
;
2359 chunk_agbno
= agbno
- offset_agbno
;
2361 error
= xfs_imap_lookup(mp
, tp
, agno
, agino
, agbno
,
2362 &chunk_agbno
, &offset_agbno
, flags
);
2368 ASSERT(agbno
>= chunk_agbno
);
2369 cluster_agbno
= chunk_agbno
+
2370 ((offset_agbno
/ blks_per_cluster
) * blks_per_cluster
);
2371 offset
= ((agbno
- cluster_agbno
) * mp
->m_sb
.sb_inopblock
) +
2372 XFS_INO_TO_OFFSET(mp
, ino
);
2374 imap
->im_blkno
= XFS_AGB_TO_DADDR(mp
, agno
, cluster_agbno
);
2375 imap
->im_len
= XFS_FSB_TO_BB(mp
, blks_per_cluster
);
2376 imap
->im_boffset
= (unsigned short)(offset
<< mp
->m_sb
.sb_inodelog
);
2379 * If the inode number maps to a block outside the bounds
2380 * of the file system then return NULL rather than calling
2381 * read_buf and panicing when we get an error from the
2384 if ((imap
->im_blkno
+ imap
->im_len
) >
2385 XFS_FSB_TO_BB(mp
, mp
->m_sb
.sb_dblocks
)) {
2387 "%s: (im_blkno (0x%llx) + im_len (0x%llx)) > sb_dblocks (0x%llx)",
2388 __func__
, (unsigned long long) imap
->im_blkno
,
2389 (unsigned long long) imap
->im_len
,
2390 XFS_FSB_TO_BB(mp
, mp
->m_sb
.sb_dblocks
));
2397 * Compute and fill in value of m_in_maxlevels.
2400 xfs_ialloc_compute_maxlevels(
2401 xfs_mount_t
*mp
) /* file system mount structure */
2405 inodes
= (1LL << XFS_INO_AGINO_BITS(mp
)) >> XFS_INODES_PER_CHUNK_LOG
;
2406 mp
->m_in_maxlevels
= xfs_btree_compute_maxlevels(mp
, mp
->m_inobt_mnr
,
2411 * Log specified fields for the ag hdr (inode section). The growth of the agi
2412 * structure over time requires that we interpret the buffer as two logical
2413 * regions delineated by the end of the unlinked list. This is due to the size
2414 * of the hash table and its location in the middle of the agi.
2416 * For example, a request to log a field before agi_unlinked and a field after
2417 * agi_unlinked could cause us to log the entire hash table and use an excessive
2418 * amount of log space. To avoid this behavior, log the region up through
2419 * agi_unlinked in one call and the region after agi_unlinked through the end of
2420 * the structure in another.
2424 xfs_trans_t
*tp
, /* transaction pointer */
2425 xfs_buf_t
*bp
, /* allocation group header buffer */
2426 int fields
) /* bitmask of fields to log */
2428 int first
; /* first byte number */
2429 int last
; /* last byte number */
2430 static const short offsets
[] = { /* field starting offsets */
2431 /* keep in sync with bit definitions */
2432 offsetof(xfs_agi_t
, agi_magicnum
),
2433 offsetof(xfs_agi_t
, agi_versionnum
),
2434 offsetof(xfs_agi_t
, agi_seqno
),
2435 offsetof(xfs_agi_t
, agi_length
),
2436 offsetof(xfs_agi_t
, agi_count
),
2437 offsetof(xfs_agi_t
, agi_root
),
2438 offsetof(xfs_agi_t
, agi_level
),
2439 offsetof(xfs_agi_t
, agi_freecount
),
2440 offsetof(xfs_agi_t
, agi_newino
),
2441 offsetof(xfs_agi_t
, agi_dirino
),
2442 offsetof(xfs_agi_t
, agi_unlinked
),
2443 offsetof(xfs_agi_t
, agi_free_root
),
2444 offsetof(xfs_agi_t
, agi_free_level
),
2448 xfs_agi_t
*agi
; /* allocation group header */
2450 agi
= XFS_BUF_TO_AGI(bp
);
2451 ASSERT(agi
->agi_magicnum
== cpu_to_be32(XFS_AGI_MAGIC
));
2455 * Compute byte offsets for the first and last fields in the first
2456 * region and log the agi buffer. This only logs up through
2459 if (fields
& XFS_AGI_ALL_BITS_R1
) {
2460 xfs_btree_offsets(fields
, offsets
, XFS_AGI_NUM_BITS_R1
,
2462 xfs_trans_log_buf(tp
, bp
, first
, last
);
2466 * Mask off the bits in the first region and calculate the first and
2467 * last field offsets for any bits in the second region.
2469 fields
&= ~XFS_AGI_ALL_BITS_R1
;
2471 xfs_btree_offsets(fields
, offsets
, XFS_AGI_NUM_BITS_R2
,
2473 xfs_trans_log_buf(tp
, bp
, first
, last
);
2479 xfs_check_agi_unlinked(
2480 struct xfs_agi
*agi
)
2484 for (i
= 0; i
< XFS_AGI_UNLINKED_BUCKETS
; i
++)
2485 ASSERT(agi
->agi_unlinked
[i
]);
2488 #define xfs_check_agi_unlinked(agi)
2495 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
2496 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(bp
);
2498 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
2499 if (!uuid_equal(&agi
->agi_uuid
, &mp
->m_sb
.sb_meta_uuid
))
2501 if (!xfs_log_check_lsn(mp
,
2502 be64_to_cpu(XFS_BUF_TO_AGI(bp
)->agi_lsn
)))
2507 * Validate the magic number of the agi block.
2509 if (agi
->agi_magicnum
!= cpu_to_be32(XFS_AGI_MAGIC
))
2511 if (!XFS_AGI_GOOD_VERSION(be32_to_cpu(agi
->agi_versionnum
)))
2514 if (be32_to_cpu(agi
->agi_level
) < 1 ||
2515 be32_to_cpu(agi
->agi_level
) > XFS_BTREE_MAXLEVELS
)
2518 if (xfs_sb_version_hasfinobt(&mp
->m_sb
) &&
2519 (be32_to_cpu(agi
->agi_free_level
) < 1 ||
2520 be32_to_cpu(agi
->agi_free_level
) > XFS_BTREE_MAXLEVELS
))
2524 * during growfs operations, the perag is not fully initialised,
2525 * so we can't use it for any useful checking. growfs ensures we can't
2526 * use it by using uncached buffers that don't have the perag attached
2527 * so we can detect and avoid this problem.
2529 if (bp
->b_pag
&& be32_to_cpu(agi
->agi_seqno
) != bp
->b_pag
->pag_agno
)
2532 xfs_check_agi_unlinked(agi
);
2537 xfs_agi_read_verify(
2540 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
2542 if (xfs_sb_version_hascrc(&mp
->m_sb
) &&
2543 !xfs_buf_verify_cksum(bp
, XFS_AGI_CRC_OFF
))
2544 xfs_buf_ioerror(bp
, -EFSBADCRC
);
2545 else if (XFS_TEST_ERROR(!xfs_agi_verify(bp
), mp
,
2546 XFS_ERRTAG_IALLOC_READ_AGI
))
2547 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
2550 xfs_verifier_error(bp
);
2554 xfs_agi_write_verify(
2557 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
2558 struct xfs_buf_log_item
*bip
= bp
->b_fspriv
;
2560 if (!xfs_agi_verify(bp
)) {
2561 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
2562 xfs_verifier_error(bp
);
2566 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
2570 XFS_BUF_TO_AGI(bp
)->agi_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
2571 xfs_buf_update_cksum(bp
, XFS_AGI_CRC_OFF
);
2574 const struct xfs_buf_ops xfs_agi_buf_ops
= {
2576 .verify_read
= xfs_agi_read_verify
,
2577 .verify_write
= xfs_agi_write_verify
,
2581 * Read in the allocation group header (inode allocation section)
2585 struct xfs_mount
*mp
, /* file system mount structure */
2586 struct xfs_trans
*tp
, /* transaction pointer */
2587 xfs_agnumber_t agno
, /* allocation group number */
2588 struct xfs_buf
**bpp
) /* allocation group hdr buf */
2592 trace_xfs_read_agi(mp
, agno
);
2594 ASSERT(agno
!= NULLAGNUMBER
);
2595 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
,
2596 XFS_AG_DADDR(mp
, agno
, XFS_AGI_DADDR(mp
)),
2597 XFS_FSS_TO_BB(mp
, 1), 0, bpp
, &xfs_agi_buf_ops
);
2601 xfs_trans_buf_set_type(tp
, *bpp
, XFS_BLFT_AGI_BUF
);
2603 xfs_buf_set_ref(*bpp
, XFS_AGI_REF
);
2608 xfs_ialloc_read_agi(
2609 struct xfs_mount
*mp
, /* file system mount structure */
2610 struct xfs_trans
*tp
, /* transaction pointer */
2611 xfs_agnumber_t agno
, /* allocation group number */
2612 struct xfs_buf
**bpp
) /* allocation group hdr buf */
2614 struct xfs_agi
*agi
; /* allocation group header */
2615 struct xfs_perag
*pag
; /* per allocation group data */
2618 trace_xfs_ialloc_read_agi(mp
, agno
);
2620 error
= xfs_read_agi(mp
, tp
, agno
, bpp
);
2624 agi
= XFS_BUF_TO_AGI(*bpp
);
2625 pag
= xfs_perag_get(mp
, agno
);
2626 if (!pag
->pagi_init
) {
2627 pag
->pagi_freecount
= be32_to_cpu(agi
->agi_freecount
);
2628 pag
->pagi_count
= be32_to_cpu(agi
->agi_count
);
2633 * It's possible for these to be out of sync if
2634 * we are in the middle of a forced shutdown.
2636 ASSERT(pag
->pagi_freecount
== be32_to_cpu(agi
->agi_freecount
) ||
2637 XFS_FORCED_SHUTDOWN(mp
));
2643 * Read in the agi to initialise the per-ag data in the mount structure
2646 xfs_ialloc_pagi_init(
2647 xfs_mount_t
*mp
, /* file system mount structure */
2648 xfs_trans_t
*tp
, /* transaction pointer */
2649 xfs_agnumber_t agno
) /* allocation group number */
2651 xfs_buf_t
*bp
= NULL
;
2654 error
= xfs_ialloc_read_agi(mp
, tp
, agno
, &bp
);
2658 xfs_trans_brelse(tp
, bp
);
2662 /* Calculate the first and last possible inode number in an AG. */
2664 xfs_ialloc_agino_range(
2665 struct xfs_mount
*mp
,
2666 xfs_agnumber_t agno
,
2673 eoag
= xfs_ag_block_count(mp
, agno
);
2676 * Calculate the first inode, which will be in the first
2677 * cluster-aligned block after the AGFL.
2679 bno
= round_up(XFS_AGFL_BLOCK(mp
) + 1,
2680 xfs_ialloc_cluster_alignment(mp
));
2681 *first
= XFS_OFFBNO_TO_AGINO(mp
, bno
, 0);
2684 * Calculate the last inode, which will be at the end of the
2685 * last (aligned) cluster that can be allocated in the AG.
2687 bno
= round_down(eoag
, xfs_ialloc_cluster_alignment(mp
));
2688 *last
= XFS_OFFBNO_TO_AGINO(mp
, bno
, 0) - 1;
2692 * Verify that an AG inode number pointer neither points outside the AG
2693 * nor points at static metadata.
2697 struct xfs_mount
*mp
,
2698 xfs_agnumber_t agno
,
2704 xfs_ialloc_agino_range(mp
, agno
, &first
, &last
);
2705 return agino
>= first
&& agino
<= last
;
2709 * Verify that an FS inode number pointer neither points outside the
2710 * filesystem nor points at static AG metadata.
2714 struct xfs_mount
*mp
,
2717 xfs_agnumber_t agno
= XFS_INO_TO_AGNO(mp
, ino
);
2718 xfs_agino_t agino
= XFS_INO_TO_AGINO(mp
, ino
);
2720 if (agno
>= mp
->m_sb
.sb_agcount
)
2722 if (XFS_AGINO_TO_INO(mp
, agno
, agino
) != ino
)
2724 return xfs_verify_agino(mp
, agno
, agino
);
2727 /* Is this an internal inode number? */
2730 struct xfs_mount
*mp
,
2733 return ino
== mp
->m_sb
.sb_rbmino
|| ino
== mp
->m_sb
.sb_rsumino
||
2734 (xfs_sb_version_hasquota(&mp
->m_sb
) &&
2735 xfs_is_quota_inode(&mp
->m_sb
, ino
));
2739 * Verify that a directory entry's inode number doesn't point at an internal
2740 * inode, empty space, or static AG metadata.
2744 struct xfs_mount
*mp
,
2747 if (xfs_internal_inum(mp
, ino
))
2749 return xfs_verify_ino(mp
, ino
);