2 * Copyright (c) 2000-2001,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
20 #include "xfs_format.h"
21 #include "xfs_log_format.h"
22 #include "xfs_trans_resv.h"
26 #include "xfs_mount.h"
27 #include "xfs_inode.h"
28 #include "xfs_btree.h"
29 #include "xfs_ialloc.h"
30 #include "xfs_ialloc_btree.h"
31 #include "xfs_alloc.h"
32 #include "xfs_error.h"
33 #include "xfs_trace.h"
34 #include "xfs_cksum.h"
35 #include "xfs_trans.h"
39 xfs_inobt_get_minrecs(
40 struct xfs_btree_cur *cur,
43 return cur->bc_mp->m_inobt_mnr[level != 0];
46 STATIC struct xfs_btree_cur *
48 struct xfs_btree_cur *cur)
50 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
51 cur->bc_private.a.agbp, cur->bc_private.a.agno);
56 struct xfs_btree_cur *cur,
57 union xfs_btree_ptr *nptr,
58 int inc) /* level change */
60 struct xfs_buf *agbp = cur->bc_private.a.agbp;
61 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
63 agi->agi_root = nptr->s;
64 be32_add_cpu(&agi->agi_level, inc);
65 xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
69 xfs_inobt_alloc_block(
70 struct xfs_btree_cur *cur,
71 union xfs_btree_ptr *start,
72 union xfs_btree_ptr *new,
76 xfs_alloc_arg_t args; /* block allocation args */
77 int error; /* error return value */
78 xfs_agblock_t sbno = be32_to_cpu(start->s);
80 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
82 memset(&args, 0, sizeof(args));
85 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
89 args.type = XFS_ALLOCTYPE_NEAR_BNO;
91 error = xfs_alloc_vextent(&args);
93 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
96 if (args.fsbno == NULLFSBLOCK) {
97 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
101 ASSERT(args.len == 1);
102 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
104 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
110 xfs_inobt_free_block(
111 struct xfs_btree_cur *cur,
117 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp));
118 error = xfs_free_extent(cur->bc_tp, fsbno, 1);
122 xfs_trans_binval(cur->bc_tp, bp);
127 xfs_inobt_get_maxrecs(
128 struct xfs_btree_cur *cur,
131 return cur->bc_mp->m_inobt_mxr[level != 0];
135 xfs_inobt_init_key_from_rec(
136 union xfs_btree_key *key,
137 union xfs_btree_rec *rec)
139 key->inobt.ir_startino = rec->inobt.ir_startino;
143 xfs_inobt_init_rec_from_key(
144 union xfs_btree_key *key,
145 union xfs_btree_rec *rec)
147 rec->inobt.ir_startino = key->inobt.ir_startino;
151 xfs_inobt_init_rec_from_cur(
152 struct xfs_btree_cur *cur,
153 union xfs_btree_rec *rec)
155 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
156 rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
157 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
161 * initial value of ptr for lookup
164 xfs_inobt_init_ptr_from_cur(
165 struct xfs_btree_cur *cur,
166 union xfs_btree_ptr *ptr)
168 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
170 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
172 ptr->s = agi->agi_root;
177 struct xfs_btree_cur *cur,
178 union xfs_btree_key *key)
180 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
181 cur->bc_rec.i.ir_startino;
188 struct xfs_mount *mp = bp->b_target->bt_mount;
189 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
190 struct xfs_perag *pag = bp->b_pag;
194 * During growfs operations, we can't verify the exact owner as the
195 * perag is not fully initialised and hence not attached to the buffer.
197 * Similarly, during log recovery we will have a perag structure
198 * attached, but the agi information will not yet have been initialised
199 * from the on disk AGI. We don't currently use any of this information,
200 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
203 switch (block->bb_magic) {
204 case cpu_to_be32(XFS_IBT_CRC_MAGIC):
205 if (!xfs_sb_version_hascrc(&mp->m_sb))
207 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid))
209 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
212 be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
215 case cpu_to_be32(XFS_IBT_MAGIC):
221 /* numrecs and level verification */
222 level = be16_to_cpu(block->bb_level);
223 if (level >= mp->m_in_maxlevels)
225 if (be16_to_cpu(block->bb_numrecs) > mp->m_inobt_mxr[level != 0])
228 /* sibling pointer verification */
229 if (!block->bb_u.s.bb_leftsib ||
230 (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks &&
231 block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK)))
233 if (!block->bb_u.s.bb_rightsib ||
234 (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks &&
235 block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK)))
242 xfs_inobt_read_verify(
245 if (!(xfs_btree_sblock_verify_crc(bp) &&
246 xfs_inobt_verify(bp))) {
247 trace_xfs_btree_corrupt(bp, _RET_IP_);
248 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW,
249 bp->b_target->bt_mount, bp->b_addr);
250 xfs_buf_ioerror(bp, EFSCORRUPTED);
255 xfs_inobt_write_verify(
258 if (!xfs_inobt_verify(bp)) {
259 trace_xfs_btree_corrupt(bp, _RET_IP_);
260 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW,
261 bp->b_target->bt_mount, bp->b_addr);
262 xfs_buf_ioerror(bp, EFSCORRUPTED);
264 xfs_btree_sblock_calc_crc(bp);
268 const struct xfs_buf_ops xfs_inobt_buf_ops = {
269 .verify_read = xfs_inobt_read_verify,
270 .verify_write = xfs_inobt_write_verify,
273 #if defined(DEBUG) || defined(XFS_WARN)
275 xfs_inobt_keys_inorder(
276 struct xfs_btree_cur *cur,
277 union xfs_btree_key *k1,
278 union xfs_btree_key *k2)
280 return be32_to_cpu(k1->inobt.ir_startino) <
281 be32_to_cpu(k2->inobt.ir_startino);
285 xfs_inobt_recs_inorder(
286 struct xfs_btree_cur *cur,
287 union xfs_btree_rec *r1,
288 union xfs_btree_rec *r2)
290 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
291 be32_to_cpu(r2->inobt.ir_startino);
295 static const struct xfs_btree_ops xfs_inobt_ops = {
296 .rec_len = sizeof(xfs_inobt_rec_t),
297 .key_len = sizeof(xfs_inobt_key_t),
299 .dup_cursor = xfs_inobt_dup_cursor,
300 .set_root = xfs_inobt_set_root,
301 .alloc_block = xfs_inobt_alloc_block,
302 .free_block = xfs_inobt_free_block,
303 .get_minrecs = xfs_inobt_get_minrecs,
304 .get_maxrecs = xfs_inobt_get_maxrecs,
305 .init_key_from_rec = xfs_inobt_init_key_from_rec,
306 .init_rec_from_key = xfs_inobt_init_rec_from_key,
307 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
308 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
309 .key_diff = xfs_inobt_key_diff,
310 .buf_ops = &xfs_inobt_buf_ops,
311 #if defined(DEBUG) || defined(XFS_WARN)
312 .keys_inorder = xfs_inobt_keys_inorder,
313 .recs_inorder = xfs_inobt_recs_inorder,
318 * Allocate a new inode btree cursor.
320 struct xfs_btree_cur * /* new inode btree cursor */
321 xfs_inobt_init_cursor(
322 struct xfs_mount *mp, /* file system mount point */
323 struct xfs_trans *tp, /* transaction pointer */
324 struct xfs_buf *agbp, /* buffer for agi structure */
325 xfs_agnumber_t agno) /* allocation group number */
327 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
328 struct xfs_btree_cur *cur;
330 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
334 cur->bc_nlevels = be32_to_cpu(agi->agi_level);
335 cur->bc_btnum = XFS_BTNUM_INO;
336 cur->bc_blocklog = mp->m_sb.sb_blocklog;
338 cur->bc_ops = &xfs_inobt_ops;
339 if (xfs_sb_version_hascrc(&mp->m_sb))
340 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
342 cur->bc_private.a.agbp = agbp;
343 cur->bc_private.a.agno = agno;
349 * Calculate number of records in an inobt btree block.
353 struct xfs_mount *mp,
357 blocklen -= XFS_INOBT_BLOCK_LEN(mp);
360 return blocklen / sizeof(xfs_inobt_rec_t);
361 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));