1 /* 2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. 3 * All Rights Reserved. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it would be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #include "xfs.h" 19 #include "xfs_fs.h" 20 #include "xfs_shared.h" 21 #include "xfs_format.h" 22 #include "xfs_log_format.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_bit.h" 25 #include "xfs_sb.h" 26 #include "xfs_ag.h" 27 #include "xfs_mount.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" 33 #include "xfs_error.h" 34 #include "xfs_trace.h" 35 #include "xfs_cksum.h" 36 #include "xfs_trans.h" 37 38 39 STATIC int 40 xfs_inobt_get_minrecs( 41 struct xfs_btree_cur *cur, 42 int level) 43 { 44 return cur->bc_mp->m_inobt_mnr[level != 0]; 45 } 46 47 STATIC struct xfs_btree_cur * 48 xfs_inobt_dup_cursor( 49 struct xfs_btree_cur *cur) 50 { 51 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp, 52 cur->bc_private.a.agbp, cur->bc_private.a.agno, 53 cur->bc_btnum); 54 } 55 56 STATIC void 57 xfs_inobt_set_root( 58 struct xfs_btree_cur *cur, 59 union xfs_btree_ptr *nptr, 60 int inc) /* level change */ 61 { 62 struct xfs_buf *agbp = cur->bc_private.a.agbp; 63 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 64 65 agi->agi_root = nptr->s; 66 be32_add_cpu(&agi->agi_level, inc); 67 xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL); 68 } 69 70 STATIC void 71 xfs_finobt_set_root( 72 struct xfs_btree_cur *cur, 73 union xfs_btree_ptr *nptr, 74 int inc) /* level change */ 75 { 76 struct xfs_buf *agbp = cur->bc_private.a.agbp; 77 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 78 79 agi->agi_free_root = nptr->s; 80 be32_add_cpu(&agi->agi_free_level, inc); 81 xfs_ialloc_log_agi(cur->bc_tp, agbp, 82 XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL); 83 } 84 85 STATIC int 86 xfs_inobt_alloc_block( 87 struct xfs_btree_cur *cur, 88 union xfs_btree_ptr *start, 89 union xfs_btree_ptr *new, 90 int *stat) 91 { 92 xfs_alloc_arg_t args; /* block allocation args */ 93 int error; /* error return value */ 94 xfs_agblock_t sbno = be32_to_cpu(start->s); 95 96 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 97 98 memset(&args, 0, sizeof(args)); 99 args.tp = cur->bc_tp; 100 args.mp = cur->bc_mp; 101 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno); 102 args.minlen = 1; 103 args.maxlen = 1; 104 args.prod = 1; 105 args.type = XFS_ALLOCTYPE_NEAR_BNO; 106 107 error = xfs_alloc_vextent(&args); 108 if (error) { 109 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 110 return error; 111 } 112 if (args.fsbno == NULLFSBLOCK) { 113 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 114 *stat = 0; 115 return 0; 116 } 117 ASSERT(args.len == 1); 118 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 119 120 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno)); 121 *stat = 1; 122 return 0; 123 } 124 125 STATIC int 126 xfs_inobt_free_block( 127 struct xfs_btree_cur *cur, 128 struct xfs_buf *bp) 129 { 130 xfs_fsblock_t fsbno; 131 int error; 132 133 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)); 134 error = xfs_free_extent(cur->bc_tp, fsbno, 1); 135 if (error) 136 return error; 137 138 xfs_trans_binval(cur->bc_tp, bp); 139 return error; 140 } 141 142 STATIC int 143 xfs_inobt_get_maxrecs( 144 struct xfs_btree_cur *cur, 145 int level) 146 { 147 return cur->bc_mp->m_inobt_mxr[level != 0]; 148 } 149 150 STATIC void 151 xfs_inobt_init_key_from_rec( 152 union xfs_btree_key *key, 153 union xfs_btree_rec *rec) 154 { 155 key->inobt.ir_startino = rec->inobt.ir_startino; 156 } 157 158 STATIC void 159 xfs_inobt_init_rec_from_key( 160 union xfs_btree_key *key, 161 union xfs_btree_rec *rec) 162 { 163 rec->inobt.ir_startino = key->inobt.ir_startino; 164 } 165 166 STATIC void 167 xfs_inobt_init_rec_from_cur( 168 struct xfs_btree_cur *cur, 169 union xfs_btree_rec *rec) 170 { 171 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino); 172 rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount); 173 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free); 174 } 175 176 /* 177 * initial value of ptr for lookup 178 */ 179 STATIC void 180 xfs_inobt_init_ptr_from_cur( 181 struct xfs_btree_cur *cur, 182 union xfs_btree_ptr *ptr) 183 { 184 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 185 186 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 187 188 ptr->s = agi->agi_root; 189 } 190 191 STATIC void 192 xfs_finobt_init_ptr_from_cur( 193 struct xfs_btree_cur *cur, 194 union xfs_btree_ptr *ptr) 195 { 196 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 197 198 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 199 ptr->s = agi->agi_free_root; 200 } 201 202 STATIC __int64_t 203 xfs_inobt_key_diff( 204 struct xfs_btree_cur *cur, 205 union xfs_btree_key *key) 206 { 207 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) - 208 cur->bc_rec.i.ir_startino; 209 } 210 211 static int 212 xfs_inobt_verify( 213 struct xfs_buf *bp) 214 { 215 struct xfs_mount *mp = bp->b_target->bt_mount; 216 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 217 struct xfs_perag *pag = bp->b_pag; 218 unsigned int level; 219 220 /* 221 * During growfs operations, we can't verify the exact owner as the 222 * perag is not fully initialised and hence not attached to the buffer. 223 * 224 * Similarly, during log recovery we will have a perag structure 225 * attached, but the agi information will not yet have been initialised 226 * from the on disk AGI. We don't currently use any of this information, 227 * but beware of the landmine (i.e. need to check pag->pagi_init) if we 228 * ever do. 229 */ 230 switch (block->bb_magic) { 231 case cpu_to_be32(XFS_IBT_CRC_MAGIC): 232 case cpu_to_be32(XFS_FIBT_CRC_MAGIC): 233 if (!xfs_sb_version_hascrc(&mp->m_sb)) 234 return false; 235 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid)) 236 return false; 237 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) 238 return false; 239 if (pag && 240 be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) 241 return false; 242 /* fall through */ 243 case cpu_to_be32(XFS_IBT_MAGIC): 244 case cpu_to_be32(XFS_FIBT_MAGIC): 245 break; 246 default: 247 return 0; 248 } 249 250 /* numrecs and level verification */ 251 level = be16_to_cpu(block->bb_level); 252 if (level >= mp->m_in_maxlevels) 253 return false; 254 if (be16_to_cpu(block->bb_numrecs) > mp->m_inobt_mxr[level != 0]) 255 return false; 256 257 /* sibling pointer verification */ 258 if (!block->bb_u.s.bb_leftsib || 259 (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks && 260 block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK))) 261 return false; 262 if (!block->bb_u.s.bb_rightsib || 263 (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks && 264 block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK))) 265 return false; 266 267 return true; 268 } 269 270 static void 271 xfs_inobt_read_verify( 272 struct xfs_buf *bp) 273 { 274 if (!xfs_btree_sblock_verify_crc(bp)) 275 xfs_buf_ioerror(bp, -EFSBADCRC); 276 else if (!xfs_inobt_verify(bp)) 277 xfs_buf_ioerror(bp, -EFSCORRUPTED); 278 279 if (bp->b_error) { 280 trace_xfs_btree_corrupt(bp, _RET_IP_); 281 xfs_verifier_error(bp); 282 } 283 } 284 285 static void 286 xfs_inobt_write_verify( 287 struct xfs_buf *bp) 288 { 289 if (!xfs_inobt_verify(bp)) { 290 trace_xfs_btree_corrupt(bp, _RET_IP_); 291 xfs_buf_ioerror(bp, -EFSCORRUPTED); 292 xfs_verifier_error(bp); 293 return; 294 } 295 xfs_btree_sblock_calc_crc(bp); 296 297 } 298 299 const struct xfs_buf_ops xfs_inobt_buf_ops = { 300 .verify_read = xfs_inobt_read_verify, 301 .verify_write = xfs_inobt_write_verify, 302 }; 303 304 #if defined(DEBUG) || defined(XFS_WARN) 305 STATIC int 306 xfs_inobt_keys_inorder( 307 struct xfs_btree_cur *cur, 308 union xfs_btree_key *k1, 309 union xfs_btree_key *k2) 310 { 311 return be32_to_cpu(k1->inobt.ir_startino) < 312 be32_to_cpu(k2->inobt.ir_startino); 313 } 314 315 STATIC int 316 xfs_inobt_recs_inorder( 317 struct xfs_btree_cur *cur, 318 union xfs_btree_rec *r1, 319 union xfs_btree_rec *r2) 320 { 321 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <= 322 be32_to_cpu(r2->inobt.ir_startino); 323 } 324 #endif /* DEBUG */ 325 326 static const struct xfs_btree_ops xfs_inobt_ops = { 327 .rec_len = sizeof(xfs_inobt_rec_t), 328 .key_len = sizeof(xfs_inobt_key_t), 329 330 .dup_cursor = xfs_inobt_dup_cursor, 331 .set_root = xfs_inobt_set_root, 332 .alloc_block = xfs_inobt_alloc_block, 333 .free_block = xfs_inobt_free_block, 334 .get_minrecs = xfs_inobt_get_minrecs, 335 .get_maxrecs = xfs_inobt_get_maxrecs, 336 .init_key_from_rec = xfs_inobt_init_key_from_rec, 337 .init_rec_from_key = xfs_inobt_init_rec_from_key, 338 .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 339 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, 340 .key_diff = xfs_inobt_key_diff, 341 .buf_ops = &xfs_inobt_buf_ops, 342 #if defined(DEBUG) || defined(XFS_WARN) 343 .keys_inorder = xfs_inobt_keys_inorder, 344 .recs_inorder = xfs_inobt_recs_inorder, 345 #endif 346 }; 347 348 static const struct xfs_btree_ops xfs_finobt_ops = { 349 .rec_len = sizeof(xfs_inobt_rec_t), 350 .key_len = sizeof(xfs_inobt_key_t), 351 352 .dup_cursor = xfs_inobt_dup_cursor, 353 .set_root = xfs_finobt_set_root, 354 .alloc_block = xfs_inobt_alloc_block, 355 .free_block = xfs_inobt_free_block, 356 .get_minrecs = xfs_inobt_get_minrecs, 357 .get_maxrecs = xfs_inobt_get_maxrecs, 358 .init_key_from_rec = xfs_inobt_init_key_from_rec, 359 .init_rec_from_key = xfs_inobt_init_rec_from_key, 360 .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 361 .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur, 362 .key_diff = xfs_inobt_key_diff, 363 .buf_ops = &xfs_inobt_buf_ops, 364 #if defined(DEBUG) || defined(XFS_WARN) 365 .keys_inorder = xfs_inobt_keys_inorder, 366 .recs_inorder = xfs_inobt_recs_inorder, 367 #endif 368 }; 369 370 /* 371 * Allocate a new inode btree cursor. 372 */ 373 struct xfs_btree_cur * /* new inode btree cursor */ 374 xfs_inobt_init_cursor( 375 struct xfs_mount *mp, /* file system mount point */ 376 struct xfs_trans *tp, /* transaction pointer */ 377 struct xfs_buf *agbp, /* buffer for agi structure */ 378 xfs_agnumber_t agno, /* allocation group number */ 379 xfs_btnum_t btnum) /* ialloc or free ino btree */ 380 { 381 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 382 struct xfs_btree_cur *cur; 383 384 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP); 385 386 cur->bc_tp = tp; 387 cur->bc_mp = mp; 388 cur->bc_btnum = btnum; 389 if (btnum == XFS_BTNUM_INO) { 390 cur->bc_nlevels = be32_to_cpu(agi->agi_level); 391 cur->bc_ops = &xfs_inobt_ops; 392 } else { 393 cur->bc_nlevels = be32_to_cpu(agi->agi_free_level); 394 cur->bc_ops = &xfs_finobt_ops; 395 } 396 397 cur->bc_blocklog = mp->m_sb.sb_blocklog; 398 399 if (xfs_sb_version_hascrc(&mp->m_sb)) 400 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 401 402 cur->bc_private.a.agbp = agbp; 403 cur->bc_private.a.agno = agno; 404 405 return cur; 406 } 407 408 /* 409 * Calculate number of records in an inobt btree block. 410 */ 411 int 412 xfs_inobt_maxrecs( 413 struct xfs_mount *mp, 414 int blocklen, 415 int leaf) 416 { 417 blocklen -= XFS_INOBT_BLOCK_LEN(mp); 418 419 if (leaf) 420 return blocklen / sizeof(xfs_inobt_rec_t); 421 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); 422 } 423