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_types.h" 21#include "xfs_bit.h" 22#include "xfs_log.h" 23#include "xfs_inum.h" 24#include "xfs_trans.h" 25#include "xfs_sb.h" 26#include "xfs_ag.h" 27#include "xfs_mount.h" 28#include "xfs_bmap_btree.h" 29#include "xfs_alloc_btree.h" 30#include "xfs_ialloc_btree.h" 31#include "xfs_dinode.h" 32#include "xfs_inode.h" 33#include "xfs_btree.h" 34#include "xfs_btree_trace.h" 35#include "xfs_ialloc.h" 36#include "xfs_alloc.h" 37#include "xfs_error.h" 38 39 40STATIC int 41xfs_inobt_get_minrecs( 42 struct xfs_btree_cur *cur, 43 int level) 44{ 45 return cur->bc_mp->m_inobt_mnr[level != 0]; 46} 47 48STATIC struct xfs_btree_cur * 49xfs_inobt_dup_cursor( 50 struct xfs_btree_cur *cur) 51{ 52 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp, 53 cur->bc_private.a.agbp, cur->bc_private.a.agno); 54} 55 56STATIC void 57xfs_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 70STATIC int 71xfs_inobt_alloc_block( 72 struct xfs_btree_cur *cur, 73 union xfs_btree_ptr *start, 74 union xfs_btree_ptr *new, 75 int length, 76 int *stat) 77{ 78 xfs_alloc_arg_t args; /* block allocation args */ 79 int error; /* error return value */ 80 xfs_agblock_t sbno = be32_to_cpu(start->s); 81 82 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 83 84 memset(&args, 0, sizeof(args)); 85 args.tp = cur->bc_tp; 86 args.mp = cur->bc_mp; 87 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno); 88 args.minlen = 1; 89 args.maxlen = 1; 90 args.prod = 1; 91 args.type = XFS_ALLOCTYPE_NEAR_BNO; 92 93 error = xfs_alloc_vextent(&args); 94 if (error) { 95 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 96 return error; 97 } 98 if (args.fsbno == NULLFSBLOCK) { 99 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 100 *stat = 0; 101 return 0; 102 } 103 ASSERT(args.len == 1); 104 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 105 106 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno)); 107 *stat = 1; 108 return 0; 109} 110 111STATIC int 112xfs_inobt_free_block( 113 struct xfs_btree_cur *cur, 114 struct xfs_buf *bp) 115{ 116 xfs_fsblock_t fsbno; 117 int error; 118 119 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)); 120 error = xfs_free_extent(cur->bc_tp, fsbno, 1); 121 if (error) 122 return error; 123 124 xfs_trans_binval(cur->bc_tp, bp); 125 return error; 126} 127 128STATIC int 129xfs_inobt_get_maxrecs( 130 struct xfs_btree_cur *cur, 131 int level) 132{ 133 return cur->bc_mp->m_inobt_mxr[level != 0]; 134} 135 136STATIC void 137xfs_inobt_init_key_from_rec( 138 union xfs_btree_key *key, 139 union xfs_btree_rec *rec) 140{ 141 key->inobt.ir_startino = rec->inobt.ir_startino; 142} 143 144STATIC void 145xfs_inobt_init_rec_from_key( 146 union xfs_btree_key *key, 147 union xfs_btree_rec *rec) 148{ 149 rec->inobt.ir_startino = key->inobt.ir_startino; 150} 151 152STATIC void 153xfs_inobt_init_rec_from_cur( 154 struct xfs_btree_cur *cur, 155 union xfs_btree_rec *rec) 156{ 157 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino); 158 rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount); 159 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free); 160} 161 162/* 163 * initial value of ptr for lookup 164 */ 165STATIC void 166xfs_inobt_init_ptr_from_cur( 167 struct xfs_btree_cur *cur, 168 union xfs_btree_ptr *ptr) 169{ 170 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 171 172 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 173 174 ptr->s = agi->agi_root; 175} 176 177STATIC __int64_t 178xfs_inobt_key_diff( 179 struct xfs_btree_cur *cur, 180 union xfs_btree_key *key) 181{ 182 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) - 183 cur->bc_rec.i.ir_startino; 184} 185 186STATIC int 187xfs_inobt_kill_root( 188 struct xfs_btree_cur *cur, 189 struct xfs_buf *bp, 190 int level, 191 union xfs_btree_ptr *newroot) 192{ 193 int error; 194 195 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 196 XFS_BTREE_STATS_INC(cur, killroot); 197 198 /* 199 * Update the root pointer, decreasing the level by 1 and then 200 * free the old root. 201 */ 202 xfs_inobt_set_root(cur, newroot, -1); 203 error = xfs_inobt_free_block(cur, bp); 204 if (error) { 205 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 206 return error; 207 } 208 209 XFS_BTREE_STATS_INC(cur, free); 210 211 cur->bc_bufs[level] = NULL; 212 cur->bc_nlevels--; 213 214 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 215 return 0; 216} 217 218#ifdef DEBUG 219STATIC int 220xfs_inobt_keys_inorder( 221 struct xfs_btree_cur *cur, 222 union xfs_btree_key *k1, 223 union xfs_btree_key *k2) 224{ 225 return be32_to_cpu(k1->inobt.ir_startino) < 226 be32_to_cpu(k2->inobt.ir_startino); 227} 228 229STATIC int 230xfs_inobt_recs_inorder( 231 struct xfs_btree_cur *cur, 232 union xfs_btree_rec *r1, 233 union xfs_btree_rec *r2) 234{ 235 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <= 236 be32_to_cpu(r2->inobt.ir_startino); 237} 238#endif /* DEBUG */ 239 240#ifdef XFS_BTREE_TRACE 241ktrace_t *xfs_inobt_trace_buf; 242 243STATIC void 244xfs_inobt_trace_enter( 245 struct xfs_btree_cur *cur, 246 const char *func, 247 char *s, 248 int type, 249 int line, 250 __psunsigned_t a0, 251 __psunsigned_t a1, 252 __psunsigned_t a2, 253 __psunsigned_t a3, 254 __psunsigned_t a4, 255 __psunsigned_t a5, 256 __psunsigned_t a6, 257 __psunsigned_t a7, 258 __psunsigned_t a8, 259 __psunsigned_t a9, 260 __psunsigned_t a10) 261{ 262 ktrace_enter(xfs_inobt_trace_buf, (void *)(__psint_t)type, 263 (void *)func, (void *)s, NULL, (void *)cur, 264 (void *)a0, (void *)a1, (void *)a2, (void *)a3, 265 (void *)a4, (void *)a5, (void *)a6, (void *)a7, 266 (void *)a8, (void *)a9, (void *)a10); 267} 268 269STATIC void 270xfs_inobt_trace_cursor( 271 struct xfs_btree_cur *cur, 272 __uint32_t *s0, 273 __uint64_t *l0, 274 __uint64_t *l1) 275{ 276 *s0 = cur->bc_private.a.agno; 277 *l0 = cur->bc_rec.i.ir_startino; 278 *l1 = cur->bc_rec.i.ir_free; 279} 280 281STATIC void 282xfs_inobt_trace_key( 283 struct xfs_btree_cur *cur, 284 union xfs_btree_key *key, 285 __uint64_t *l0, 286 __uint64_t *l1) 287{ 288 *l0 = be32_to_cpu(key->inobt.ir_startino); 289 *l1 = 0; 290} 291 292STATIC void 293xfs_inobt_trace_record( 294 struct xfs_btree_cur *cur, 295 union xfs_btree_rec *rec, 296 __uint64_t *l0, 297 __uint64_t *l1, 298 __uint64_t *l2) 299{ 300 *l0 = be32_to_cpu(rec->inobt.ir_startino); 301 *l1 = be32_to_cpu(rec->inobt.ir_freecount); 302 *l2 = be64_to_cpu(rec->inobt.ir_free); 303} 304#endif /* XFS_BTREE_TRACE */ 305 306static const struct xfs_btree_ops xfs_inobt_ops = { 307 .rec_len = sizeof(xfs_inobt_rec_t), 308 .key_len = sizeof(xfs_inobt_key_t), 309 310 .dup_cursor = xfs_inobt_dup_cursor, 311 .set_root = xfs_inobt_set_root, 312 .kill_root = xfs_inobt_kill_root, 313 .alloc_block = xfs_inobt_alloc_block, 314 .free_block = xfs_inobt_free_block, 315 .get_minrecs = xfs_inobt_get_minrecs, 316 .get_maxrecs = xfs_inobt_get_maxrecs, 317 .init_key_from_rec = xfs_inobt_init_key_from_rec, 318 .init_rec_from_key = xfs_inobt_init_rec_from_key, 319 .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 320 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, 321 .key_diff = xfs_inobt_key_diff, 322 323#ifdef DEBUG 324 .keys_inorder = xfs_inobt_keys_inorder, 325 .recs_inorder = xfs_inobt_recs_inorder, 326#endif 327 328#ifdef XFS_BTREE_TRACE 329 .trace_enter = xfs_inobt_trace_enter, 330 .trace_cursor = xfs_inobt_trace_cursor, 331 .trace_key = xfs_inobt_trace_key, 332 .trace_record = xfs_inobt_trace_record, 333#endif 334}; 335 336/* 337 * Allocate a new inode btree cursor. 338 */ 339struct xfs_btree_cur * /* new inode btree cursor */ 340xfs_inobt_init_cursor( 341 struct xfs_mount *mp, /* file system mount point */ 342 struct xfs_trans *tp, /* transaction pointer */ 343 struct xfs_buf *agbp, /* buffer for agi structure */ 344 xfs_agnumber_t agno) /* allocation group number */ 345{ 346 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 347 struct xfs_btree_cur *cur; 348 349 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP); 350 351 cur->bc_tp = tp; 352 cur->bc_mp = mp; 353 cur->bc_nlevels = be32_to_cpu(agi->agi_level); 354 cur->bc_btnum = XFS_BTNUM_INO; 355 cur->bc_blocklog = mp->m_sb.sb_blocklog; 356 357 cur->bc_ops = &xfs_inobt_ops; 358 359 cur->bc_private.a.agbp = agbp; 360 cur->bc_private.a.agno = agno; 361 362 return cur; 363} 364 365/* 366 * Calculate number of records in an inobt btree block. 367 */ 368int 369xfs_inobt_maxrecs( 370 struct xfs_mount *mp, 371 int blocklen, 372 int leaf) 373{ 374 blocklen -= XFS_INOBT_BLOCK_LEN(mp); 375 376 if (leaf) 377 return blocklen / sizeof(xfs_inobt_rec_t); 378 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); 379} 380