1153323Srodrigc/* 2159451Srodrigc * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. 3159451Srodrigc * All Rights Reserved. 4153323Srodrigc * 5159451Srodrigc * This program is free software; you can redistribute it and/or 6159451Srodrigc * modify it under the terms of the GNU General Public License as 7153323Srodrigc * published by the Free Software Foundation. 8153323Srodrigc * 9159451Srodrigc * This program is distributed in the hope that it would be useful, 10159451Srodrigc * but WITHOUT ANY WARRANTY; without even the implied warranty of 11159451Srodrigc * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12159451Srodrigc * GNU General Public License for more details. 13153323Srodrigc * 14159451Srodrigc * You should have received a copy of the GNU General Public License 15159451Srodrigc * along with this program; if not, write the Free Software Foundation, 16159451Srodrigc * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17153323Srodrigc */ 18153323Srodrigc#include "xfs.h" 19159451Srodrigc#include "xfs_fs.h" 20153323Srodrigc#include "xfs_types.h" 21159451Srodrigc#include "xfs_bit.h" 22159451Srodrigc#include "xfs_log.h" 23153323Srodrigc#include "xfs_inum.h" 24153323Srodrigc#include "xfs_trans.h" 25153323Srodrigc#include "xfs_sb.h" 26153323Srodrigc#include "xfs_ag.h" 27153323Srodrigc#include "xfs_dir.h" 28159451Srodrigc#include "xfs_dir2.h" 29153323Srodrigc#include "xfs_dmapi.h" 30153323Srodrigc#include "xfs_mount.h" 31159451Srodrigc#include "xfs_bmap_btree.h" 32153323Srodrigc#include "xfs_alloc_btree.h" 33153323Srodrigc#include "xfs_ialloc_btree.h" 34159451Srodrigc#include "xfs_dir_sf.h" 35159451Srodrigc#include "xfs_dir2_sf.h" 36159451Srodrigc#include "xfs_attr_sf.h" 37159451Srodrigc#include "xfs_dinode.h" 38159451Srodrigc#include "xfs_inode.h" 39153323Srodrigc#include "xfs_btree.h" 40153323Srodrigc#include "xfs_ialloc.h" 41153323Srodrigc#include "xfs_alloc.h" 42153323Srodrigc#include "xfs_error.h" 43153323Srodrigc 44153323SrodrigcSTATIC void xfs_inobt_log_block(xfs_trans_t *, xfs_buf_t *, int); 45153323SrodrigcSTATIC void xfs_inobt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int); 46153323SrodrigcSTATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 47153323SrodrigcSTATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 48153323SrodrigcSTATIC int xfs_inobt_lshift(xfs_btree_cur_t *, int, int *); 49153323SrodrigcSTATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *); 50153323SrodrigcSTATIC int xfs_inobt_rshift(xfs_btree_cur_t *, int, int *); 51153323SrodrigcSTATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *, 52153323Srodrigc xfs_inobt_key_t *, xfs_btree_cur_t **, int *); 53153323SrodrigcSTATIC int xfs_inobt_updkey(xfs_btree_cur_t *, xfs_inobt_key_t *, int); 54153323Srodrigc 55153323Srodrigc/* 56153323Srodrigc * Single level of the xfs_inobt_delete record deletion routine. 57153323Srodrigc * Delete record pointed to by cur/level. 58153323Srodrigc * Remove the record from its block then rebalance the tree. 59153323Srodrigc * Return 0 for error, 1 for done, 2 to go on to the next level. 60153323Srodrigc */ 61153323SrodrigcSTATIC int /* error */ 62153323Srodrigcxfs_inobt_delrec( 63153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 64153323Srodrigc int level, /* level removing record from */ 65153323Srodrigc int *stat) /* fail/done/go-on */ 66153323Srodrigc{ 67153323Srodrigc xfs_buf_t *agbp; /* buffer for a.g. inode header */ 68153323Srodrigc xfs_mount_t *mp; /* mount structure */ 69153323Srodrigc xfs_agi_t *agi; /* allocation group inode header */ 70153323Srodrigc xfs_inobt_block_t *block; /* btree block record/key lives in */ 71153323Srodrigc xfs_agblock_t bno; /* btree block number */ 72153323Srodrigc xfs_buf_t *bp; /* buffer for block */ 73153323Srodrigc int error; /* error return value */ 74153323Srodrigc int i; /* loop index */ 75153323Srodrigc xfs_inobt_key_t key; /* kp points here if block is level 0 */ 76153323Srodrigc xfs_inobt_key_t *kp = NULL; /* pointer to btree keys */ 77153323Srodrigc xfs_agblock_t lbno; /* left block's block number */ 78153323Srodrigc xfs_buf_t *lbp; /* left block's buffer pointer */ 79153323Srodrigc xfs_inobt_block_t *left; /* left btree block */ 80153323Srodrigc xfs_inobt_key_t *lkp; /* left block key pointer */ 81153323Srodrigc xfs_inobt_ptr_t *lpp; /* left block address pointer */ 82153323Srodrigc int lrecs = 0; /* number of records in left block */ 83153323Srodrigc xfs_inobt_rec_t *lrp; /* left block record pointer */ 84153323Srodrigc xfs_inobt_ptr_t *pp = NULL; /* pointer to btree addresses */ 85153323Srodrigc int ptr; /* index in btree block for this rec */ 86153323Srodrigc xfs_agblock_t rbno; /* right block's block number */ 87153323Srodrigc xfs_buf_t *rbp; /* right block's buffer pointer */ 88153323Srodrigc xfs_inobt_block_t *right; /* right btree block */ 89153323Srodrigc xfs_inobt_key_t *rkp; /* right block key pointer */ 90153323Srodrigc xfs_inobt_rec_t *rp; /* pointer to btree records */ 91153323Srodrigc xfs_inobt_ptr_t *rpp; /* right block address pointer */ 92153323Srodrigc int rrecs = 0; /* number of records in right block */ 93153323Srodrigc int numrecs; 94153323Srodrigc xfs_inobt_rec_t *rrp; /* right block record pointer */ 95153323Srodrigc xfs_btree_cur_t *tcur; /* temporary btree cursor */ 96153323Srodrigc 97153323Srodrigc mp = cur->bc_mp; 98153323Srodrigc 99153323Srodrigc /* 100153323Srodrigc * Get the index of the entry being deleted, check for nothing there. 101153323Srodrigc */ 102153323Srodrigc ptr = cur->bc_ptrs[level]; 103153323Srodrigc if (ptr == 0) { 104153323Srodrigc *stat = 0; 105153323Srodrigc return 0; 106153323Srodrigc } 107153323Srodrigc 108153323Srodrigc /* 109153323Srodrigc * Get the buffer & block containing the record or key/ptr. 110153323Srodrigc */ 111153323Srodrigc bp = cur->bc_bufs[level]; 112153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 113153323Srodrigc#ifdef DEBUG 114153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, level, bp))) 115153323Srodrigc return error; 116153323Srodrigc#endif 117153323Srodrigc /* 118153323Srodrigc * Fail if we're off the end of the block. 119153323Srodrigc */ 120153323Srodrigc 121159451Srodrigc numrecs = be16_to_cpu(block->bb_numrecs); 122153323Srodrigc if (ptr > numrecs) { 123153323Srodrigc *stat = 0; 124153323Srodrigc return 0; 125153323Srodrigc } 126153323Srodrigc /* 127153323Srodrigc * It's a nonleaf. Excise the key and ptr being deleted, by 128153323Srodrigc * sliding the entries past them down one. 129153323Srodrigc * Log the changed areas of the block. 130153323Srodrigc */ 131153323Srodrigc if (level > 0) { 132153323Srodrigc kp = XFS_INOBT_KEY_ADDR(block, 1, cur); 133153323Srodrigc pp = XFS_INOBT_PTR_ADDR(block, 1, cur); 134153323Srodrigc#ifdef DEBUG 135153323Srodrigc for (i = ptr; i < numrecs; i++) { 136159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i]), level))) 137153323Srodrigc return error; 138153323Srodrigc } 139153323Srodrigc#endif 140153323Srodrigc if (ptr < numrecs) { 141153323Srodrigc memmove(&kp[ptr - 1], &kp[ptr], 142153323Srodrigc (numrecs - ptr) * sizeof(*kp)); 143153323Srodrigc memmove(&pp[ptr - 1], &pp[ptr], 144153323Srodrigc (numrecs - ptr) * sizeof(*kp)); 145153323Srodrigc xfs_inobt_log_keys(cur, bp, ptr, numrecs - 1); 146153323Srodrigc xfs_inobt_log_ptrs(cur, bp, ptr, numrecs - 1); 147153323Srodrigc } 148153323Srodrigc } 149153323Srodrigc /* 150153323Srodrigc * It's a leaf. Excise the record being deleted, by sliding the 151153323Srodrigc * entries past it down one. Log the changed areas of the block. 152153323Srodrigc */ 153153323Srodrigc else { 154153323Srodrigc rp = XFS_INOBT_REC_ADDR(block, 1, cur); 155153323Srodrigc if (ptr < numrecs) { 156153323Srodrigc memmove(&rp[ptr - 1], &rp[ptr], 157153323Srodrigc (numrecs - ptr) * sizeof(*rp)); 158153323Srodrigc xfs_inobt_log_recs(cur, bp, ptr, numrecs - 1); 159153323Srodrigc } 160153323Srodrigc /* 161153323Srodrigc * If it's the first record in the block, we'll need a key 162153323Srodrigc * structure to pass up to the next level (updkey). 163153323Srodrigc */ 164153323Srodrigc if (ptr == 1) { 165153323Srodrigc key.ir_startino = rp->ir_startino; 166153323Srodrigc kp = &key; 167153323Srodrigc } 168153323Srodrigc } 169153323Srodrigc /* 170153323Srodrigc * Decrement and log the number of entries in the block. 171153323Srodrigc */ 172153323Srodrigc numrecs--; 173159451Srodrigc block->bb_numrecs = cpu_to_be16(numrecs); 174153323Srodrigc xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS); 175153323Srodrigc /* 176153323Srodrigc * Is this the root level? If so, we're almost done. 177153323Srodrigc */ 178153323Srodrigc if (level == cur->bc_nlevels - 1) { 179153323Srodrigc /* 180153323Srodrigc * If this is the root level, 181153323Srodrigc * and there's only one entry left, 182153323Srodrigc * and it's NOT the leaf level, 183153323Srodrigc * then we can get rid of this level. 184153323Srodrigc */ 185153323Srodrigc if (numrecs == 1 && level > 0) { 186153323Srodrigc agbp = cur->bc_private.i.agbp; 187153323Srodrigc agi = XFS_BUF_TO_AGI(agbp); 188153323Srodrigc /* 189153323Srodrigc * pp is still set to the first pointer in the block. 190153323Srodrigc * Make it the new root of the btree. 191153323Srodrigc */ 192159451Srodrigc bno = be32_to_cpu(agi->agi_root); 193153323Srodrigc agi->agi_root = *pp; 194159451Srodrigc be32_add(&agi->agi_level, -1); 195153323Srodrigc /* 196153323Srodrigc * Free the block. 197153323Srodrigc */ 198153323Srodrigc if ((error = xfs_free_extent(cur->bc_tp, 199153323Srodrigc XFS_AGB_TO_FSB(mp, cur->bc_private.i.agno, bno), 1))) 200153323Srodrigc return error; 201153323Srodrigc xfs_trans_binval(cur->bc_tp, bp); 202153323Srodrigc xfs_ialloc_log_agi(cur->bc_tp, agbp, 203153323Srodrigc XFS_AGI_ROOT | XFS_AGI_LEVEL); 204153323Srodrigc /* 205153323Srodrigc * Update the cursor so there's one fewer level. 206153323Srodrigc */ 207153323Srodrigc cur->bc_bufs[level] = NULL; 208153323Srodrigc cur->bc_nlevels--; 209153323Srodrigc } else if (level > 0 && 210153323Srodrigc (error = xfs_inobt_decrement(cur, level, &i))) 211153323Srodrigc return error; 212153323Srodrigc *stat = 1; 213153323Srodrigc return 0; 214153323Srodrigc } 215153323Srodrigc /* 216153323Srodrigc * If we deleted the leftmost entry in the block, update the 217153323Srodrigc * key values above us in the tree. 218153323Srodrigc */ 219153323Srodrigc if (ptr == 1 && (error = xfs_inobt_updkey(cur, kp, level + 1))) 220153323Srodrigc return error; 221153323Srodrigc /* 222153323Srodrigc * If the number of records remaining in the block is at least 223153323Srodrigc * the minimum, we're done. 224153323Srodrigc */ 225153323Srodrigc if (numrecs >= XFS_INOBT_BLOCK_MINRECS(level, cur)) { 226153323Srodrigc if (level > 0 && 227153323Srodrigc (error = xfs_inobt_decrement(cur, level, &i))) 228153323Srodrigc return error; 229153323Srodrigc *stat = 1; 230153323Srodrigc return 0; 231153323Srodrigc } 232153323Srodrigc /* 233153323Srodrigc * Otherwise, we have to move some records around to keep the 234153323Srodrigc * tree balanced. Look at the left and right sibling blocks to 235153323Srodrigc * see if we can re-balance by moving only one record. 236153323Srodrigc */ 237159451Srodrigc rbno = be32_to_cpu(block->bb_rightsib); 238159451Srodrigc lbno = be32_to_cpu(block->bb_leftsib); 239153323Srodrigc bno = NULLAGBLOCK; 240153323Srodrigc ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK); 241153323Srodrigc /* 242153323Srodrigc * Duplicate the cursor so our btree manipulations here won't 243153323Srodrigc * disrupt the next level up. 244153323Srodrigc */ 245153323Srodrigc if ((error = xfs_btree_dup_cursor(cur, &tcur))) 246153323Srodrigc return error; 247153323Srodrigc /* 248153323Srodrigc * If there's a right sibling, see if it's ok to shift an entry 249153323Srodrigc * out of it. 250153323Srodrigc */ 251153323Srodrigc if (rbno != NULLAGBLOCK) { 252153323Srodrigc /* 253153323Srodrigc * Move the temp cursor to the last entry in the next block. 254153323Srodrigc * Actually any entry but the first would suffice. 255153323Srodrigc */ 256153323Srodrigc i = xfs_btree_lastrec(tcur, level); 257153323Srodrigc XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 258153323Srodrigc if ((error = xfs_inobt_increment(tcur, level, &i))) 259153323Srodrigc goto error0; 260153323Srodrigc XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 261153323Srodrigc i = xfs_btree_lastrec(tcur, level); 262153323Srodrigc XFS_WANT_CORRUPTED_GOTO(i == 1, error0); 263153323Srodrigc /* 264153323Srodrigc * Grab a pointer to the block. 265153323Srodrigc */ 266153323Srodrigc rbp = tcur->bc_bufs[level]; 267153323Srodrigc right = XFS_BUF_TO_INOBT_BLOCK(rbp); 268153323Srodrigc#ifdef DEBUG 269153323Srodrigc if ((error = xfs_btree_check_sblock(cur, right, level, rbp))) 270153323Srodrigc goto error0; 271153323Srodrigc#endif 272153323Srodrigc /* 273153323Srodrigc * Grab the current block number, for future use. 274153323Srodrigc */ 275159451Srodrigc bno = be32_to_cpu(right->bb_leftsib); 276153323Srodrigc /* 277153323Srodrigc * If right block is full enough so that removing one entry 278153323Srodrigc * won't make it too empty, and left-shifting an entry out 279153323Srodrigc * of right to us works, we're done. 280153323Srodrigc */ 281159451Srodrigc if (be16_to_cpu(right->bb_numrecs) - 1 >= 282153323Srodrigc XFS_INOBT_BLOCK_MINRECS(level, cur)) { 283153323Srodrigc if ((error = xfs_inobt_lshift(tcur, level, &i))) 284153323Srodrigc goto error0; 285153323Srodrigc if (i) { 286159451Srodrigc ASSERT(be16_to_cpu(block->bb_numrecs) >= 287153323Srodrigc XFS_INOBT_BLOCK_MINRECS(level, cur)); 288153323Srodrigc xfs_btree_del_cursor(tcur, 289153323Srodrigc XFS_BTREE_NOERROR); 290153323Srodrigc if (level > 0 && 291153323Srodrigc (error = xfs_inobt_decrement(cur, level, 292153323Srodrigc &i))) 293153323Srodrigc return error; 294153323Srodrigc *stat = 1; 295153323Srodrigc return 0; 296153323Srodrigc } 297153323Srodrigc } 298153323Srodrigc /* 299153323Srodrigc * Otherwise, grab the number of records in right for 300153323Srodrigc * future reference, and fix up the temp cursor to point 301153323Srodrigc * to our block again (last record). 302153323Srodrigc */ 303159451Srodrigc rrecs = be16_to_cpu(right->bb_numrecs); 304153323Srodrigc if (lbno != NULLAGBLOCK) { 305153323Srodrigc xfs_btree_firstrec(tcur, level); 306153323Srodrigc if ((error = xfs_inobt_decrement(tcur, level, &i))) 307153323Srodrigc goto error0; 308153323Srodrigc } 309153323Srodrigc } 310153323Srodrigc /* 311153323Srodrigc * If there's a left sibling, see if it's ok to shift an entry 312153323Srodrigc * out of it. 313153323Srodrigc */ 314153323Srodrigc if (lbno != NULLAGBLOCK) { 315153323Srodrigc /* 316153323Srodrigc * Move the temp cursor to the first entry in the 317153323Srodrigc * previous block. 318153323Srodrigc */ 319153323Srodrigc xfs_btree_firstrec(tcur, level); 320153323Srodrigc if ((error = xfs_inobt_decrement(tcur, level, &i))) 321153323Srodrigc goto error0; 322153323Srodrigc xfs_btree_firstrec(tcur, level); 323153323Srodrigc /* 324153323Srodrigc * Grab a pointer to the block. 325153323Srodrigc */ 326153323Srodrigc lbp = tcur->bc_bufs[level]; 327153323Srodrigc left = XFS_BUF_TO_INOBT_BLOCK(lbp); 328153323Srodrigc#ifdef DEBUG 329153323Srodrigc if ((error = xfs_btree_check_sblock(cur, left, level, lbp))) 330153323Srodrigc goto error0; 331153323Srodrigc#endif 332153323Srodrigc /* 333153323Srodrigc * Grab the current block number, for future use. 334153323Srodrigc */ 335159451Srodrigc bno = be32_to_cpu(left->bb_rightsib); 336153323Srodrigc /* 337153323Srodrigc * If left block is full enough so that removing one entry 338153323Srodrigc * won't make it too empty, and right-shifting an entry out 339153323Srodrigc * of left to us works, we're done. 340153323Srodrigc */ 341159451Srodrigc if (be16_to_cpu(left->bb_numrecs) - 1 >= 342153323Srodrigc XFS_INOBT_BLOCK_MINRECS(level, cur)) { 343153323Srodrigc if ((error = xfs_inobt_rshift(tcur, level, &i))) 344153323Srodrigc goto error0; 345153323Srodrigc if (i) { 346159451Srodrigc ASSERT(be16_to_cpu(block->bb_numrecs) >= 347153323Srodrigc XFS_INOBT_BLOCK_MINRECS(level, cur)); 348153323Srodrigc xfs_btree_del_cursor(tcur, 349153323Srodrigc XFS_BTREE_NOERROR); 350153323Srodrigc if (level == 0) 351153323Srodrigc cur->bc_ptrs[0]++; 352153323Srodrigc *stat = 1; 353153323Srodrigc return 0; 354153323Srodrigc } 355153323Srodrigc } 356153323Srodrigc /* 357153323Srodrigc * Otherwise, grab the number of records in right for 358153323Srodrigc * future reference. 359153323Srodrigc */ 360159451Srodrigc lrecs = be16_to_cpu(left->bb_numrecs); 361153323Srodrigc } 362153323Srodrigc /* 363153323Srodrigc * Delete the temp cursor, we're done with it. 364153323Srodrigc */ 365153323Srodrigc xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 366153323Srodrigc /* 367153323Srodrigc * If here, we need to do a join to keep the tree balanced. 368153323Srodrigc */ 369153323Srodrigc ASSERT(bno != NULLAGBLOCK); 370153323Srodrigc /* 371153323Srodrigc * See if we can join with the left neighbor block. 372153323Srodrigc */ 373153323Srodrigc if (lbno != NULLAGBLOCK && 374153323Srodrigc lrecs + numrecs <= XFS_INOBT_BLOCK_MAXRECS(level, cur)) { 375153323Srodrigc /* 376153323Srodrigc * Set "right" to be the starting block, 377153323Srodrigc * "left" to be the left neighbor. 378153323Srodrigc */ 379153323Srodrigc rbno = bno; 380153323Srodrigc right = block; 381159451Srodrigc rrecs = be16_to_cpu(right->bb_numrecs); 382153323Srodrigc rbp = bp; 383153323Srodrigc if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, 384153323Srodrigc cur->bc_private.i.agno, lbno, 0, &lbp, 385153323Srodrigc XFS_INO_BTREE_REF))) 386153323Srodrigc return error; 387153323Srodrigc left = XFS_BUF_TO_INOBT_BLOCK(lbp); 388159451Srodrigc lrecs = be16_to_cpu(left->bb_numrecs); 389153323Srodrigc if ((error = xfs_btree_check_sblock(cur, left, level, lbp))) 390153323Srodrigc return error; 391153323Srodrigc } 392153323Srodrigc /* 393153323Srodrigc * If that won't work, see if we can join with the right neighbor block. 394153323Srodrigc */ 395153323Srodrigc else if (rbno != NULLAGBLOCK && 396153323Srodrigc rrecs + numrecs <= XFS_INOBT_BLOCK_MAXRECS(level, cur)) { 397153323Srodrigc /* 398153323Srodrigc * Set "left" to be the starting block, 399153323Srodrigc * "right" to be the right neighbor. 400153323Srodrigc */ 401153323Srodrigc lbno = bno; 402153323Srodrigc left = block; 403159451Srodrigc lrecs = be16_to_cpu(left->bb_numrecs); 404153323Srodrigc lbp = bp; 405153323Srodrigc if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, 406153323Srodrigc cur->bc_private.i.agno, rbno, 0, &rbp, 407153323Srodrigc XFS_INO_BTREE_REF))) 408153323Srodrigc return error; 409153323Srodrigc right = XFS_BUF_TO_INOBT_BLOCK(rbp); 410159451Srodrigc rrecs = be16_to_cpu(right->bb_numrecs); 411153323Srodrigc if ((error = xfs_btree_check_sblock(cur, right, level, rbp))) 412153323Srodrigc return error; 413153323Srodrigc } 414153323Srodrigc /* 415153323Srodrigc * Otherwise, we can't fix the imbalance. 416153323Srodrigc * Just return. This is probably a logic error, but it's not fatal. 417153323Srodrigc */ 418153323Srodrigc else { 419153323Srodrigc if (level > 0 && (error = xfs_inobt_decrement(cur, level, &i))) 420153323Srodrigc return error; 421153323Srodrigc *stat = 1; 422153323Srodrigc return 0; 423153323Srodrigc } 424153323Srodrigc /* 425153323Srodrigc * We're now going to join "left" and "right" by moving all the stuff 426153323Srodrigc * in "right" to "left" and deleting "right". 427153323Srodrigc */ 428153323Srodrigc if (level > 0) { 429153323Srodrigc /* 430153323Srodrigc * It's a non-leaf. Move keys and pointers. 431153323Srodrigc */ 432153323Srodrigc lkp = XFS_INOBT_KEY_ADDR(left, lrecs + 1, cur); 433153323Srodrigc lpp = XFS_INOBT_PTR_ADDR(left, lrecs + 1, cur); 434153323Srodrigc rkp = XFS_INOBT_KEY_ADDR(right, 1, cur); 435153323Srodrigc rpp = XFS_INOBT_PTR_ADDR(right, 1, cur); 436153323Srodrigc#ifdef DEBUG 437153323Srodrigc for (i = 0; i < rrecs; i++) { 438159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level))) 439153323Srodrigc return error; 440153323Srodrigc } 441153323Srodrigc#endif 442153323Srodrigc memcpy(lkp, rkp, rrecs * sizeof(*lkp)); 443153323Srodrigc memcpy(lpp, rpp, rrecs * sizeof(*lpp)); 444153323Srodrigc xfs_inobt_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs); 445153323Srodrigc xfs_inobt_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs); 446153323Srodrigc } else { 447153323Srodrigc /* 448153323Srodrigc * It's a leaf. Move records. 449153323Srodrigc */ 450153323Srodrigc lrp = XFS_INOBT_REC_ADDR(left, lrecs + 1, cur); 451153323Srodrigc rrp = XFS_INOBT_REC_ADDR(right, 1, cur); 452153323Srodrigc memcpy(lrp, rrp, rrecs * sizeof(*lrp)); 453153323Srodrigc xfs_inobt_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs); 454153323Srodrigc } 455153323Srodrigc /* 456153323Srodrigc * If we joined with the left neighbor, set the buffer in the 457153323Srodrigc * cursor to the left block, and fix up the index. 458153323Srodrigc */ 459153323Srodrigc if (bp != lbp) { 460153323Srodrigc xfs_btree_setbuf(cur, level, lbp); 461153323Srodrigc cur->bc_ptrs[level] += lrecs; 462153323Srodrigc } 463153323Srodrigc /* 464153323Srodrigc * If we joined with the right neighbor and there's a level above 465153323Srodrigc * us, increment the cursor at that level. 466153323Srodrigc */ 467153323Srodrigc else if (level + 1 < cur->bc_nlevels && 468153323Srodrigc (error = xfs_alloc_increment(cur, level + 1, &i))) 469153323Srodrigc return error; 470153323Srodrigc /* 471153323Srodrigc * Fix up the number of records in the surviving block. 472153323Srodrigc */ 473153323Srodrigc lrecs += rrecs; 474159451Srodrigc left->bb_numrecs = cpu_to_be16(lrecs); 475153323Srodrigc /* 476153323Srodrigc * Fix up the right block pointer in the surviving block, and log it. 477153323Srodrigc */ 478153323Srodrigc left->bb_rightsib = right->bb_rightsib; 479153323Srodrigc xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB); 480153323Srodrigc /* 481153323Srodrigc * If there is a right sibling now, make it point to the 482153323Srodrigc * remaining block. 483153323Srodrigc */ 484159451Srodrigc if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) { 485153323Srodrigc xfs_inobt_block_t *rrblock; 486153323Srodrigc xfs_buf_t *rrbp; 487153323Srodrigc 488153323Srodrigc if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, 489159451Srodrigc cur->bc_private.i.agno, be32_to_cpu(left->bb_rightsib), 0, 490153323Srodrigc &rrbp, XFS_INO_BTREE_REF))) 491153323Srodrigc return error; 492153323Srodrigc rrblock = XFS_BUF_TO_INOBT_BLOCK(rrbp); 493153323Srodrigc if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp))) 494153323Srodrigc return error; 495159451Srodrigc rrblock->bb_leftsib = cpu_to_be32(lbno); 496153323Srodrigc xfs_inobt_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB); 497153323Srodrigc } 498153323Srodrigc /* 499153323Srodrigc * Free the deleting block. 500153323Srodrigc */ 501153323Srodrigc if ((error = xfs_free_extent(cur->bc_tp, XFS_AGB_TO_FSB(mp, 502153323Srodrigc cur->bc_private.i.agno, rbno), 1))) 503153323Srodrigc return error; 504153323Srodrigc xfs_trans_binval(cur->bc_tp, rbp); 505153323Srodrigc /* 506153323Srodrigc * Readjust the ptr at this level if it's not a leaf, since it's 507153323Srodrigc * still pointing at the deletion point, which makes the cursor 508153323Srodrigc * inconsistent. If this makes the ptr 0, the caller fixes it up. 509153323Srodrigc * We can't use decrement because it would change the next level up. 510153323Srodrigc */ 511153323Srodrigc if (level > 0) 512153323Srodrigc cur->bc_ptrs[level]--; 513153323Srodrigc /* 514153323Srodrigc * Return value means the next level up has something to do. 515153323Srodrigc */ 516153323Srodrigc *stat = 2; 517153323Srodrigc return 0; 518153323Srodrigc 519153323Srodrigcerror0: 520153323Srodrigc xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 521153323Srodrigc return error; 522153323Srodrigc} 523153323Srodrigc 524153323Srodrigc/* 525153323Srodrigc * Insert one record/level. Return information to the caller 526153323Srodrigc * allowing the next level up to proceed if necessary. 527153323Srodrigc */ 528153323SrodrigcSTATIC int /* error */ 529153323Srodrigcxfs_inobt_insrec( 530153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 531153323Srodrigc int level, /* level to insert record at */ 532153323Srodrigc xfs_agblock_t *bnop, /* i/o: block number inserted */ 533153323Srodrigc xfs_inobt_rec_t *recp, /* i/o: record data inserted */ 534153323Srodrigc xfs_btree_cur_t **curp, /* output: new cursor replacing cur */ 535153323Srodrigc int *stat) /* success/failure */ 536153323Srodrigc{ 537153323Srodrigc xfs_inobt_block_t *block; /* btree block record/key lives in */ 538153323Srodrigc xfs_buf_t *bp; /* buffer for block */ 539153323Srodrigc int error; /* error return value */ 540153323Srodrigc int i; /* loop index */ 541153323Srodrigc xfs_inobt_key_t key; /* key value being inserted */ 542153323Srodrigc xfs_inobt_key_t *kp=NULL; /* pointer to btree keys */ 543153323Srodrigc xfs_agblock_t nbno; /* block number of allocated block */ 544153323Srodrigc xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */ 545153323Srodrigc xfs_inobt_key_t nkey; /* new key value, from split */ 546153323Srodrigc xfs_inobt_rec_t nrec; /* new record value, for caller */ 547153323Srodrigc int numrecs; 548153323Srodrigc int optr; /* old ptr value */ 549153323Srodrigc xfs_inobt_ptr_t *pp; /* pointer to btree addresses */ 550153323Srodrigc int ptr; /* index in btree block for this rec */ 551153323Srodrigc xfs_inobt_rec_t *rp=NULL; /* pointer to btree records */ 552153323Srodrigc 553153323Srodrigc /* 554159451Srodrigc * GCC doesn't understand the (arguably complex) control flow in 555159451Srodrigc * this function and complains about uninitialized structure fields 556159451Srodrigc * without this. 557159451Srodrigc */ 558159451Srodrigc memset(&nrec, 0, sizeof(nrec)); 559159451Srodrigc 560159451Srodrigc /* 561153323Srodrigc * If we made it to the root level, allocate a new root block 562153323Srodrigc * and we're done. 563153323Srodrigc */ 564153323Srodrigc if (level >= cur->bc_nlevels) { 565153323Srodrigc error = xfs_inobt_newroot(cur, &i); 566153323Srodrigc *bnop = NULLAGBLOCK; 567153323Srodrigc *stat = i; 568153323Srodrigc return error; 569153323Srodrigc } 570153323Srodrigc /* 571153323Srodrigc * Make a key out of the record data to be inserted, and save it. 572153323Srodrigc */ 573153323Srodrigc key.ir_startino = recp->ir_startino; /* INT_: direct copy */ 574153323Srodrigc optr = ptr = cur->bc_ptrs[level]; 575153323Srodrigc /* 576153323Srodrigc * If we're off the left edge, return failure. 577153323Srodrigc */ 578153323Srodrigc if (ptr == 0) { 579153323Srodrigc *stat = 0; 580153323Srodrigc return 0; 581153323Srodrigc } 582153323Srodrigc /* 583153323Srodrigc * Get pointers to the btree buffer and block. 584153323Srodrigc */ 585153323Srodrigc bp = cur->bc_bufs[level]; 586153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 587159451Srodrigc numrecs = be16_to_cpu(block->bb_numrecs); 588153323Srodrigc#ifdef DEBUG 589153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, level, bp))) 590153323Srodrigc return error; 591153323Srodrigc /* 592153323Srodrigc * Check that the new entry is being inserted in the right place. 593153323Srodrigc */ 594153323Srodrigc if (ptr <= numrecs) { 595153323Srodrigc if (level == 0) { 596153323Srodrigc rp = XFS_INOBT_REC_ADDR(block, ptr, cur); 597153323Srodrigc xfs_btree_check_rec(cur->bc_btnum, recp, rp); 598153323Srodrigc } else { 599153323Srodrigc kp = XFS_INOBT_KEY_ADDR(block, ptr, cur); 600153323Srodrigc xfs_btree_check_key(cur->bc_btnum, &key, kp); 601153323Srodrigc } 602153323Srodrigc } 603153323Srodrigc#endif 604153323Srodrigc nbno = NULLAGBLOCK; 605153323Srodrigc ncur = (xfs_btree_cur_t *)0; 606153323Srodrigc /* 607153323Srodrigc * If the block is full, we can't insert the new entry until we 608153323Srodrigc * make the block un-full. 609153323Srodrigc */ 610153323Srodrigc if (numrecs == XFS_INOBT_BLOCK_MAXRECS(level, cur)) { 611153323Srodrigc /* 612153323Srodrigc * First, try shifting an entry to the right neighbor. 613153323Srodrigc */ 614153323Srodrigc if ((error = xfs_inobt_rshift(cur, level, &i))) 615153323Srodrigc return error; 616153323Srodrigc if (i) { 617153323Srodrigc /* nothing */ 618153323Srodrigc } 619153323Srodrigc /* 620153323Srodrigc * Next, try shifting an entry to the left neighbor. 621153323Srodrigc */ 622153323Srodrigc else { 623153323Srodrigc if ((error = xfs_inobt_lshift(cur, level, &i))) 624153323Srodrigc return error; 625153323Srodrigc if (i) { 626153323Srodrigc optr = ptr = cur->bc_ptrs[level]; 627153323Srodrigc } else { 628153323Srodrigc /* 629153323Srodrigc * Next, try splitting the current block 630153323Srodrigc * in half. If this works we have to 631153323Srodrigc * re-set our variables because 632153323Srodrigc * we could be in a different block now. 633153323Srodrigc */ 634153323Srodrigc if ((error = xfs_inobt_split(cur, level, &nbno, 635153323Srodrigc &nkey, &ncur, &i))) 636153323Srodrigc return error; 637153323Srodrigc if (i) { 638153323Srodrigc bp = cur->bc_bufs[level]; 639153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 640153323Srodrigc#ifdef DEBUG 641153323Srodrigc if ((error = xfs_btree_check_sblock(cur, 642153323Srodrigc block, level, bp))) 643153323Srodrigc return error; 644153323Srodrigc#endif 645153323Srodrigc ptr = cur->bc_ptrs[level]; 646153323Srodrigc nrec.ir_startino = nkey.ir_startino; /* INT_: direct copy */ 647153323Srodrigc } else { 648153323Srodrigc /* 649153323Srodrigc * Otherwise the insert fails. 650153323Srodrigc */ 651153323Srodrigc *stat = 0; 652153323Srodrigc return 0; 653153323Srodrigc } 654153323Srodrigc } 655153323Srodrigc } 656153323Srodrigc } 657153323Srodrigc /* 658153323Srodrigc * At this point we know there's room for our new entry in the block 659153323Srodrigc * we're pointing at. 660153323Srodrigc */ 661159451Srodrigc numrecs = be16_to_cpu(block->bb_numrecs); 662153323Srodrigc if (level > 0) { 663153323Srodrigc /* 664153323Srodrigc * It's a non-leaf entry. Make a hole for the new data 665153323Srodrigc * in the key and ptr regions of the block. 666153323Srodrigc */ 667153323Srodrigc kp = XFS_INOBT_KEY_ADDR(block, 1, cur); 668153323Srodrigc pp = XFS_INOBT_PTR_ADDR(block, 1, cur); 669153323Srodrigc#ifdef DEBUG 670153323Srodrigc for (i = numrecs; i >= ptr; i--) { 671159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level))) 672153323Srodrigc return error; 673153323Srodrigc } 674153323Srodrigc#endif 675153323Srodrigc memmove(&kp[ptr], &kp[ptr - 1], 676153323Srodrigc (numrecs - ptr + 1) * sizeof(*kp)); 677153323Srodrigc memmove(&pp[ptr], &pp[ptr - 1], 678153323Srodrigc (numrecs - ptr + 1) * sizeof(*pp)); 679153323Srodrigc /* 680153323Srodrigc * Now stuff the new data in, bump numrecs and log the new data. 681153323Srodrigc */ 682153323Srodrigc#ifdef DEBUG 683153323Srodrigc if ((error = xfs_btree_check_sptr(cur, *bnop, level))) 684153323Srodrigc return error; 685153323Srodrigc#endif 686153323Srodrigc kp[ptr - 1] = key; /* INT_: struct copy */ 687159451Srodrigc pp[ptr - 1] = cpu_to_be32(*bnop); 688153323Srodrigc numrecs++; 689159451Srodrigc block->bb_numrecs = cpu_to_be16(numrecs); 690153323Srodrigc xfs_inobt_log_keys(cur, bp, ptr, numrecs); 691153323Srodrigc xfs_inobt_log_ptrs(cur, bp, ptr, numrecs); 692153323Srodrigc } else { 693153323Srodrigc /* 694153323Srodrigc * It's a leaf entry. Make a hole for the new record. 695153323Srodrigc */ 696153323Srodrigc rp = XFS_INOBT_REC_ADDR(block, 1, cur); 697153323Srodrigc memmove(&rp[ptr], &rp[ptr - 1], 698153323Srodrigc (numrecs - ptr + 1) * sizeof(*rp)); 699153323Srodrigc /* 700153323Srodrigc * Now stuff the new record in, bump numrecs 701153323Srodrigc * and log the new data. 702153323Srodrigc */ 703153323Srodrigc rp[ptr - 1] = *recp; /* INT_: struct copy */ 704153323Srodrigc numrecs++; 705159451Srodrigc block->bb_numrecs = cpu_to_be16(numrecs); 706153323Srodrigc xfs_inobt_log_recs(cur, bp, ptr, numrecs); 707153323Srodrigc } 708153323Srodrigc /* 709153323Srodrigc * Log the new number of records in the btree header. 710153323Srodrigc */ 711153323Srodrigc xfs_inobt_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS); 712153323Srodrigc#ifdef DEBUG 713153323Srodrigc /* 714153323Srodrigc * Check that the key/record is in the right place, now. 715153323Srodrigc */ 716153323Srodrigc if (ptr < numrecs) { 717153323Srodrigc if (level == 0) 718153323Srodrigc xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1, 719153323Srodrigc rp + ptr); 720153323Srodrigc else 721153323Srodrigc xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1, 722153323Srodrigc kp + ptr); 723153323Srodrigc } 724153323Srodrigc#endif 725153323Srodrigc /* 726153323Srodrigc * If we inserted at the start of a block, update the parents' keys. 727153323Srodrigc */ 728153323Srodrigc if (optr == 1 && (error = xfs_inobt_updkey(cur, &key, level + 1))) 729153323Srodrigc return error; 730153323Srodrigc /* 731153323Srodrigc * Return the new block number, if any. 732153323Srodrigc * If there is one, give back a record value and a cursor too. 733153323Srodrigc */ 734153323Srodrigc *bnop = nbno; 735153323Srodrigc if (nbno != NULLAGBLOCK) { 736153323Srodrigc *recp = nrec; /* INT_: struct copy */ 737153323Srodrigc *curp = ncur; 738153323Srodrigc } 739153323Srodrigc *stat = 1; 740153323Srodrigc return 0; 741153323Srodrigc} 742153323Srodrigc 743153323Srodrigc/* 744153323Srodrigc * Log header fields from a btree block. 745153323Srodrigc */ 746153323SrodrigcSTATIC void 747153323Srodrigcxfs_inobt_log_block( 748153323Srodrigc xfs_trans_t *tp, /* transaction pointer */ 749153323Srodrigc xfs_buf_t *bp, /* buffer containing btree block */ 750153323Srodrigc int fields) /* mask of fields: XFS_BB_... */ 751153323Srodrigc{ 752153323Srodrigc int first; /* first byte offset logged */ 753153323Srodrigc int last; /* last byte offset logged */ 754153323Srodrigc static const short offsets[] = { /* table of offsets */ 755153323Srodrigc offsetof(xfs_inobt_block_t, bb_magic), 756153323Srodrigc offsetof(xfs_inobt_block_t, bb_level), 757153323Srodrigc offsetof(xfs_inobt_block_t, bb_numrecs), 758153323Srodrigc offsetof(xfs_inobt_block_t, bb_leftsib), 759153323Srodrigc offsetof(xfs_inobt_block_t, bb_rightsib), 760153323Srodrigc sizeof(xfs_inobt_block_t) 761153323Srodrigc }; 762153323Srodrigc 763153323Srodrigc xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last); 764153323Srodrigc xfs_trans_log_buf(tp, bp, first, last); 765153323Srodrigc} 766153323Srodrigc 767153323Srodrigc/* 768153323Srodrigc * Log keys from a btree block (nonleaf). 769153323Srodrigc */ 770153323SrodrigcSTATIC void 771153323Srodrigcxfs_inobt_log_keys( 772153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 773153323Srodrigc xfs_buf_t *bp, /* buffer containing btree block */ 774153323Srodrigc int kfirst, /* index of first key to log */ 775153323Srodrigc int klast) /* index of last key to log */ 776153323Srodrigc{ 777153323Srodrigc xfs_inobt_block_t *block; /* btree block to log from */ 778153323Srodrigc int first; /* first byte offset logged */ 779153323Srodrigc xfs_inobt_key_t *kp; /* key pointer in btree block */ 780153323Srodrigc int last; /* last byte offset logged */ 781153323Srodrigc 782153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 783153323Srodrigc kp = XFS_INOBT_KEY_ADDR(block, 1, cur); 784153323Srodrigc first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block); 785153323Srodrigc last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block); 786153323Srodrigc xfs_trans_log_buf(cur->bc_tp, bp, first, last); 787153323Srodrigc} 788153323Srodrigc 789153323Srodrigc/* 790153323Srodrigc * Log block pointer fields from a btree block (nonleaf). 791153323Srodrigc */ 792153323SrodrigcSTATIC void 793153323Srodrigcxfs_inobt_log_ptrs( 794153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 795153323Srodrigc xfs_buf_t *bp, /* buffer containing btree block */ 796153323Srodrigc int pfirst, /* index of first pointer to log */ 797153323Srodrigc int plast) /* index of last pointer to log */ 798153323Srodrigc{ 799153323Srodrigc xfs_inobt_block_t *block; /* btree block to log from */ 800153323Srodrigc int first; /* first byte offset logged */ 801153323Srodrigc int last; /* last byte offset logged */ 802153323Srodrigc xfs_inobt_ptr_t *pp; /* block-pointer pointer in btree blk */ 803153323Srodrigc 804153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 805153323Srodrigc pp = XFS_INOBT_PTR_ADDR(block, 1, cur); 806153323Srodrigc first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block); 807153323Srodrigc last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block); 808153323Srodrigc xfs_trans_log_buf(cur->bc_tp, bp, first, last); 809153323Srodrigc} 810153323Srodrigc 811153323Srodrigc/* 812153323Srodrigc * Log records from a btree block (leaf). 813153323Srodrigc */ 814153323SrodrigcSTATIC void 815153323Srodrigcxfs_inobt_log_recs( 816153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 817153323Srodrigc xfs_buf_t *bp, /* buffer containing btree block */ 818153323Srodrigc int rfirst, /* index of first record to log */ 819153323Srodrigc int rlast) /* index of last record to log */ 820153323Srodrigc{ 821153323Srodrigc xfs_inobt_block_t *block; /* btree block to log from */ 822153323Srodrigc int first; /* first byte offset logged */ 823153323Srodrigc int last; /* last byte offset logged */ 824153323Srodrigc xfs_inobt_rec_t *rp; /* record pointer for btree block */ 825153323Srodrigc 826153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 827153323Srodrigc rp = XFS_INOBT_REC_ADDR(block, 1, cur); 828153323Srodrigc first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block); 829153323Srodrigc last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block); 830153323Srodrigc xfs_trans_log_buf(cur->bc_tp, bp, first, last); 831153323Srodrigc} 832153323Srodrigc 833153323Srodrigc/* 834153323Srodrigc * Lookup the record. The cursor is made to point to it, based on dir. 835153323Srodrigc * Return 0 if can't find any such record, 1 for success. 836153323Srodrigc */ 837153323SrodrigcSTATIC int /* error */ 838153323Srodrigcxfs_inobt_lookup( 839153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 840153323Srodrigc xfs_lookup_t dir, /* <=, ==, or >= */ 841153323Srodrigc int *stat) /* success/failure */ 842153323Srodrigc{ 843153323Srodrigc xfs_agblock_t agbno; /* a.g. relative btree block number */ 844153323Srodrigc xfs_agnumber_t agno; /* allocation group number */ 845153323Srodrigc xfs_inobt_block_t *block=NULL; /* current btree block */ 846153323Srodrigc __int64_t diff; /* difference for the current key */ 847153323Srodrigc int error; /* error return value */ 848153323Srodrigc int keyno=0; /* current key number */ 849153323Srodrigc int level; /* level in the btree */ 850153323Srodrigc xfs_mount_t *mp; /* file system mount point */ 851153323Srodrigc 852153323Srodrigc /* 853153323Srodrigc * Get the allocation group header, and the root block number. 854153323Srodrigc */ 855153323Srodrigc mp = cur->bc_mp; 856153323Srodrigc { 857153323Srodrigc xfs_agi_t *agi; /* a.g. inode header */ 858153323Srodrigc 859153323Srodrigc agi = XFS_BUF_TO_AGI(cur->bc_private.i.agbp); 860159451Srodrigc agno = be32_to_cpu(agi->agi_seqno); 861159451Srodrigc agbno = be32_to_cpu(agi->agi_root); 862153323Srodrigc } 863153323Srodrigc /* 864153323Srodrigc * Iterate over each level in the btree, starting at the root. 865153323Srodrigc * For each level above the leaves, find the key we need, based 866153323Srodrigc * on the lookup record, then follow the corresponding block 867153323Srodrigc * pointer down to the next level. 868153323Srodrigc */ 869153323Srodrigc for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { 870153323Srodrigc xfs_buf_t *bp; /* buffer pointer for btree block */ 871153323Srodrigc xfs_daddr_t d; /* disk address of btree block */ 872153323Srodrigc 873153323Srodrigc /* 874153323Srodrigc * Get the disk address we're looking for. 875153323Srodrigc */ 876153323Srodrigc d = XFS_AGB_TO_DADDR(mp, agno, agbno); 877153323Srodrigc /* 878153323Srodrigc * If the old buffer at this level is for a different block, 879153323Srodrigc * throw it away, otherwise just use it. 880153323Srodrigc */ 881153323Srodrigc bp = cur->bc_bufs[level]; 882153323Srodrigc if (bp && XFS_BUF_ADDR(bp) != d) 883153323Srodrigc bp = (xfs_buf_t *)0; 884153323Srodrigc if (!bp) { 885153323Srodrigc /* 886153323Srodrigc * Need to get a new buffer. Read it, then 887153323Srodrigc * set it in the cursor, releasing the old one. 888153323Srodrigc */ 889153323Srodrigc if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, 890153323Srodrigc agno, agbno, 0, &bp, XFS_INO_BTREE_REF))) 891153323Srodrigc return error; 892153323Srodrigc xfs_btree_setbuf(cur, level, bp); 893153323Srodrigc /* 894153323Srodrigc * Point to the btree block, now that we have the buffer 895153323Srodrigc */ 896153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 897153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, level, 898153323Srodrigc bp))) 899153323Srodrigc return error; 900153323Srodrigc } else 901153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 902153323Srodrigc /* 903153323Srodrigc * If we already had a key match at a higher level, we know 904153323Srodrigc * we need to use the first entry in this block. 905153323Srodrigc */ 906153323Srodrigc if (diff == 0) 907153323Srodrigc keyno = 1; 908153323Srodrigc /* 909153323Srodrigc * Otherwise we need to search this block. Do a binary search. 910153323Srodrigc */ 911153323Srodrigc else { 912153323Srodrigc int high; /* high entry number */ 913153323Srodrigc xfs_inobt_key_t *kkbase=NULL;/* base of keys in block */ 914153323Srodrigc xfs_inobt_rec_t *krbase=NULL;/* base of records in block */ 915153323Srodrigc int low; /* low entry number */ 916153323Srodrigc 917153323Srodrigc /* 918153323Srodrigc * Get a pointer to keys or records. 919153323Srodrigc */ 920153323Srodrigc if (level > 0) 921153323Srodrigc kkbase = XFS_INOBT_KEY_ADDR(block, 1, cur); 922153323Srodrigc else 923153323Srodrigc krbase = XFS_INOBT_REC_ADDR(block, 1, cur); 924153323Srodrigc /* 925153323Srodrigc * Set low and high entry numbers, 1-based. 926153323Srodrigc */ 927153323Srodrigc low = 1; 928159451Srodrigc if (!(high = be16_to_cpu(block->bb_numrecs))) { 929153323Srodrigc /* 930153323Srodrigc * If the block is empty, the tree must 931153323Srodrigc * be an empty leaf. 932153323Srodrigc */ 933153323Srodrigc ASSERT(level == 0 && cur->bc_nlevels == 1); 934153323Srodrigc cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE; 935153323Srodrigc *stat = 0; 936153323Srodrigc return 0; 937153323Srodrigc } 938153323Srodrigc /* 939153323Srodrigc * Binary search the block. 940153323Srodrigc */ 941153323Srodrigc while (low <= high) { 942153323Srodrigc xfs_agino_t startino; /* key value */ 943153323Srodrigc 944153323Srodrigc /* 945153323Srodrigc * keyno is average of low and high. 946153323Srodrigc */ 947153323Srodrigc keyno = (low + high) >> 1; 948153323Srodrigc /* 949153323Srodrigc * Get startino. 950153323Srodrigc */ 951153323Srodrigc if (level > 0) { 952153323Srodrigc xfs_inobt_key_t *kkp; 953153323Srodrigc 954153323Srodrigc kkp = kkbase + keyno - 1; 955153323Srodrigc startino = INT_GET(kkp->ir_startino, ARCH_CONVERT); 956153323Srodrigc } else { 957153323Srodrigc xfs_inobt_rec_t *krp; 958153323Srodrigc 959153323Srodrigc krp = krbase + keyno - 1; 960153323Srodrigc startino = INT_GET(krp->ir_startino, ARCH_CONVERT); 961153323Srodrigc } 962153323Srodrigc /* 963153323Srodrigc * Compute difference to get next direction. 964153323Srodrigc */ 965153323Srodrigc diff = (__int64_t) 966153323Srodrigc startino - cur->bc_rec.i.ir_startino; 967153323Srodrigc /* 968153323Srodrigc * Less than, move right. 969153323Srodrigc */ 970153323Srodrigc if (diff < 0) 971153323Srodrigc low = keyno + 1; 972153323Srodrigc /* 973153323Srodrigc * Greater than, move left. 974153323Srodrigc */ 975153323Srodrigc else if (diff > 0) 976153323Srodrigc high = keyno - 1; 977153323Srodrigc /* 978153323Srodrigc * Equal, we're done. 979153323Srodrigc */ 980153323Srodrigc else 981153323Srodrigc break; 982153323Srodrigc } 983153323Srodrigc } 984153323Srodrigc /* 985153323Srodrigc * If there are more levels, set up for the next level 986153323Srodrigc * by getting the block number and filling in the cursor. 987153323Srodrigc */ 988153323Srodrigc if (level > 0) { 989153323Srodrigc /* 990153323Srodrigc * If we moved left, need the previous key number, 991153323Srodrigc * unless there isn't one. 992153323Srodrigc */ 993153323Srodrigc if (diff > 0 && --keyno < 1) 994153323Srodrigc keyno = 1; 995159451Srodrigc agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, keyno, cur)); 996153323Srodrigc#ifdef DEBUG 997153323Srodrigc if ((error = xfs_btree_check_sptr(cur, agbno, level))) 998153323Srodrigc return error; 999153323Srodrigc#endif 1000153323Srodrigc cur->bc_ptrs[level] = keyno; 1001153323Srodrigc } 1002153323Srodrigc } 1003153323Srodrigc /* 1004153323Srodrigc * Done with the search. 1005153323Srodrigc * See if we need to adjust the results. 1006153323Srodrigc */ 1007153323Srodrigc if (dir != XFS_LOOKUP_LE && diff < 0) { 1008153323Srodrigc keyno++; 1009153323Srodrigc /* 1010153323Srodrigc * If ge search and we went off the end of the block, but it's 1011153323Srodrigc * not the last block, we're in the wrong block. 1012153323Srodrigc */ 1013153323Srodrigc if (dir == XFS_LOOKUP_GE && 1014159451Srodrigc keyno > be16_to_cpu(block->bb_numrecs) && 1015159451Srodrigc be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) { 1016153323Srodrigc int i; 1017153323Srodrigc 1018153323Srodrigc cur->bc_ptrs[0] = keyno; 1019153323Srodrigc if ((error = xfs_inobt_increment(cur, 0, &i))) 1020153323Srodrigc return error; 1021153323Srodrigc ASSERT(i == 1); 1022153323Srodrigc *stat = 1; 1023153323Srodrigc return 0; 1024153323Srodrigc } 1025153323Srodrigc } 1026153323Srodrigc else if (dir == XFS_LOOKUP_LE && diff > 0) 1027153323Srodrigc keyno--; 1028153323Srodrigc cur->bc_ptrs[0] = keyno; 1029153323Srodrigc /* 1030153323Srodrigc * Return if we succeeded or not. 1031153323Srodrigc */ 1032159451Srodrigc if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) 1033153323Srodrigc *stat = 0; 1034153323Srodrigc else 1035153323Srodrigc *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0)); 1036153323Srodrigc return 0; 1037153323Srodrigc} 1038153323Srodrigc 1039153323Srodrigc/* 1040153323Srodrigc * Move 1 record left from cur/level if possible. 1041153323Srodrigc * Update cur to reflect the new path. 1042153323Srodrigc */ 1043153323SrodrigcSTATIC int /* error */ 1044153323Srodrigcxfs_inobt_lshift( 1045153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1046153323Srodrigc int level, /* level to shift record on */ 1047153323Srodrigc int *stat) /* success/failure */ 1048153323Srodrigc{ 1049153323Srodrigc int error; /* error return value */ 1050153323Srodrigc#ifdef DEBUG 1051153323Srodrigc int i; /* loop index */ 1052153323Srodrigc#endif 1053153323Srodrigc xfs_inobt_key_t key; /* key value for leaf level upward */ 1054153323Srodrigc xfs_buf_t *lbp; /* buffer for left neighbor block */ 1055153323Srodrigc xfs_inobt_block_t *left; /* left neighbor btree block */ 1056153323Srodrigc xfs_inobt_key_t *lkp=NULL; /* key pointer for left block */ 1057153323Srodrigc xfs_inobt_ptr_t *lpp; /* address pointer for left block */ 1058153323Srodrigc xfs_inobt_rec_t *lrp=NULL; /* record pointer for left block */ 1059153323Srodrigc int nrec; /* new number of left block entries */ 1060153323Srodrigc xfs_buf_t *rbp; /* buffer for right (current) block */ 1061153323Srodrigc xfs_inobt_block_t *right; /* right (current) btree block */ 1062153323Srodrigc xfs_inobt_key_t *rkp=NULL; /* key pointer for right block */ 1063153323Srodrigc xfs_inobt_ptr_t *rpp=NULL; /* address pointer for right block */ 1064153323Srodrigc xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */ 1065153323Srodrigc 1066153323Srodrigc /* 1067153323Srodrigc * Set up variables for this block as "right". 1068153323Srodrigc */ 1069153323Srodrigc rbp = cur->bc_bufs[level]; 1070153323Srodrigc right = XFS_BUF_TO_INOBT_BLOCK(rbp); 1071153323Srodrigc#ifdef DEBUG 1072153323Srodrigc if ((error = xfs_btree_check_sblock(cur, right, level, rbp))) 1073153323Srodrigc return error; 1074153323Srodrigc#endif 1075153323Srodrigc /* 1076153323Srodrigc * If we've got no left sibling then we can't shift an entry left. 1077153323Srodrigc */ 1078159451Srodrigc if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) { 1079153323Srodrigc *stat = 0; 1080153323Srodrigc return 0; 1081153323Srodrigc } 1082153323Srodrigc /* 1083153323Srodrigc * If the cursor entry is the one that would be moved, don't 1084153323Srodrigc * do it... it's too complicated. 1085153323Srodrigc */ 1086153323Srodrigc if (cur->bc_ptrs[level] <= 1) { 1087153323Srodrigc *stat = 0; 1088153323Srodrigc return 0; 1089153323Srodrigc } 1090153323Srodrigc /* 1091153323Srodrigc * Set up the left neighbor as "left". 1092153323Srodrigc */ 1093153323Srodrigc if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp, 1094159451Srodrigc cur->bc_private.i.agno, be32_to_cpu(right->bb_leftsib), 1095159451Srodrigc 0, &lbp, XFS_INO_BTREE_REF))) 1096153323Srodrigc return error; 1097153323Srodrigc left = XFS_BUF_TO_INOBT_BLOCK(lbp); 1098153323Srodrigc if ((error = xfs_btree_check_sblock(cur, left, level, lbp))) 1099153323Srodrigc return error; 1100153323Srodrigc /* 1101153323Srodrigc * If it's full, it can't take another entry. 1102153323Srodrigc */ 1103159451Srodrigc if (be16_to_cpu(left->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) { 1104153323Srodrigc *stat = 0; 1105153323Srodrigc return 0; 1106153323Srodrigc } 1107159451Srodrigc nrec = be16_to_cpu(left->bb_numrecs) + 1; 1108153323Srodrigc /* 1109153323Srodrigc * If non-leaf, copy a key and a ptr to the left block. 1110153323Srodrigc */ 1111153323Srodrigc if (level > 0) { 1112153323Srodrigc lkp = XFS_INOBT_KEY_ADDR(left, nrec, cur); 1113153323Srodrigc rkp = XFS_INOBT_KEY_ADDR(right, 1, cur); 1114153323Srodrigc *lkp = *rkp; 1115153323Srodrigc xfs_inobt_log_keys(cur, lbp, nrec, nrec); 1116153323Srodrigc lpp = XFS_INOBT_PTR_ADDR(left, nrec, cur); 1117153323Srodrigc rpp = XFS_INOBT_PTR_ADDR(right, 1, cur); 1118153323Srodrigc#ifdef DEBUG 1119159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level))) 1120153323Srodrigc return error; 1121153323Srodrigc#endif 1122153323Srodrigc *lpp = *rpp; /* INT_: no-change copy */ 1123153323Srodrigc xfs_inobt_log_ptrs(cur, lbp, nrec, nrec); 1124153323Srodrigc } 1125153323Srodrigc /* 1126153323Srodrigc * If leaf, copy a record to the left block. 1127153323Srodrigc */ 1128153323Srodrigc else { 1129153323Srodrigc lrp = XFS_INOBT_REC_ADDR(left, nrec, cur); 1130153323Srodrigc rrp = XFS_INOBT_REC_ADDR(right, 1, cur); 1131153323Srodrigc *lrp = *rrp; 1132153323Srodrigc xfs_inobt_log_recs(cur, lbp, nrec, nrec); 1133153323Srodrigc } 1134153323Srodrigc /* 1135153323Srodrigc * Bump and log left's numrecs, decrement and log right's numrecs. 1136153323Srodrigc */ 1137159451Srodrigc be16_add(&left->bb_numrecs, 1); 1138153323Srodrigc xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS); 1139153323Srodrigc#ifdef DEBUG 1140153323Srodrigc if (level > 0) 1141153323Srodrigc xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp); 1142153323Srodrigc else 1143153323Srodrigc xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp); 1144153323Srodrigc#endif 1145159451Srodrigc be16_add(&right->bb_numrecs, -1); 1146153323Srodrigc xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS); 1147153323Srodrigc /* 1148153323Srodrigc * Slide the contents of right down one entry. 1149153323Srodrigc */ 1150153323Srodrigc if (level > 0) { 1151153323Srodrigc#ifdef DEBUG 1152159451Srodrigc for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) { 1153159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]), 1154153323Srodrigc level))) 1155153323Srodrigc return error; 1156153323Srodrigc } 1157153323Srodrigc#endif 1158159451Srodrigc memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp)); 1159159451Srodrigc memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp)); 1160159451Srodrigc xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs)); 1161159451Srodrigc xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs)); 1162153323Srodrigc } else { 1163159451Srodrigc memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp)); 1164159451Srodrigc xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs)); 1165153323Srodrigc key.ir_startino = rrp->ir_startino; /* INT_: direct copy */ 1166153323Srodrigc rkp = &key; 1167153323Srodrigc } 1168153323Srodrigc /* 1169153323Srodrigc * Update the parent key values of right. 1170153323Srodrigc */ 1171153323Srodrigc if ((error = xfs_inobt_updkey(cur, rkp, level + 1))) 1172153323Srodrigc return error; 1173153323Srodrigc /* 1174153323Srodrigc * Slide the cursor value left one. 1175153323Srodrigc */ 1176153323Srodrigc cur->bc_ptrs[level]--; 1177153323Srodrigc *stat = 1; 1178153323Srodrigc return 0; 1179153323Srodrigc} 1180153323Srodrigc 1181153323Srodrigc/* 1182153323Srodrigc * Allocate a new root block, fill it in. 1183153323Srodrigc */ 1184153323SrodrigcSTATIC int /* error */ 1185153323Srodrigcxfs_inobt_newroot( 1186153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1187153323Srodrigc int *stat) /* success/failure */ 1188153323Srodrigc{ 1189153323Srodrigc xfs_agi_t *agi; /* a.g. inode header */ 1190153323Srodrigc xfs_alloc_arg_t args; /* allocation argument structure */ 1191153323Srodrigc xfs_inobt_block_t *block; /* one half of the old root block */ 1192153323Srodrigc xfs_buf_t *bp; /* buffer containing block */ 1193153323Srodrigc int error; /* error return value */ 1194153323Srodrigc xfs_inobt_key_t *kp; /* btree key pointer */ 1195153323Srodrigc xfs_agblock_t lbno; /* left block number */ 1196153323Srodrigc xfs_buf_t *lbp; /* left buffer pointer */ 1197153323Srodrigc xfs_inobt_block_t *left; /* left btree block */ 1198153323Srodrigc xfs_buf_t *nbp; /* new (root) buffer */ 1199153323Srodrigc xfs_inobt_block_t *new; /* new (root) btree block */ 1200153323Srodrigc int nptr; /* new value for key index, 1 or 2 */ 1201153323Srodrigc xfs_inobt_ptr_t *pp; /* btree address pointer */ 1202153323Srodrigc xfs_agblock_t rbno; /* right block number */ 1203153323Srodrigc xfs_buf_t *rbp; /* right buffer pointer */ 1204153323Srodrigc xfs_inobt_block_t *right; /* right btree block */ 1205153323Srodrigc xfs_inobt_rec_t *rp; /* btree record pointer */ 1206153323Srodrigc 1207153323Srodrigc ASSERT(cur->bc_nlevels < XFS_IN_MAXLEVELS(cur->bc_mp)); 1208153323Srodrigc 1209153323Srodrigc /* 1210153323Srodrigc * Get a block & a buffer. 1211153323Srodrigc */ 1212153323Srodrigc agi = XFS_BUF_TO_AGI(cur->bc_private.i.agbp); 1213153323Srodrigc args.tp = cur->bc_tp; 1214153323Srodrigc args.mp = cur->bc_mp; 1215153323Srodrigc args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.i.agno, 1216159451Srodrigc be32_to_cpu(agi->agi_root)); 1217153323Srodrigc args.mod = args.minleft = args.alignment = args.total = args.wasdel = 1218153323Srodrigc args.isfl = args.userdata = args.minalignslop = 0; 1219153323Srodrigc args.minlen = args.maxlen = args.prod = 1; 1220153323Srodrigc args.type = XFS_ALLOCTYPE_NEAR_BNO; 1221153323Srodrigc if ((error = xfs_alloc_vextent(&args))) 1222153323Srodrigc return error; 1223153323Srodrigc /* 1224153323Srodrigc * None available, we fail. 1225153323Srodrigc */ 1226153323Srodrigc if (args.fsbno == NULLFSBLOCK) { 1227153323Srodrigc *stat = 0; 1228153323Srodrigc return 0; 1229153323Srodrigc } 1230153323Srodrigc ASSERT(args.len == 1); 1231153323Srodrigc nbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0); 1232153323Srodrigc new = XFS_BUF_TO_INOBT_BLOCK(nbp); 1233153323Srodrigc /* 1234153323Srodrigc * Set the root data in the a.g. inode structure. 1235153323Srodrigc */ 1236159451Srodrigc agi->agi_root = cpu_to_be32(args.agbno); 1237159451Srodrigc be32_add(&agi->agi_level, 1); 1238153323Srodrigc xfs_ialloc_log_agi(args.tp, cur->bc_private.i.agbp, 1239153323Srodrigc XFS_AGI_ROOT | XFS_AGI_LEVEL); 1240153323Srodrigc /* 1241153323Srodrigc * At the previous root level there are now two blocks: the old 1242153323Srodrigc * root, and the new block generated when it was split. 1243153323Srodrigc * We don't know which one the cursor is pointing at, so we 1244153323Srodrigc * set up variables "left" and "right" for each case. 1245153323Srodrigc */ 1246153323Srodrigc bp = cur->bc_bufs[cur->bc_nlevels - 1]; 1247153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1248153323Srodrigc#ifdef DEBUG 1249153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, cur->bc_nlevels - 1, bp))) 1250153323Srodrigc return error; 1251153323Srodrigc#endif 1252159451Srodrigc if (be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) { 1253153323Srodrigc /* 1254153323Srodrigc * Our block is left, pick up the right block. 1255153323Srodrigc */ 1256153323Srodrigc lbp = bp; 1257153323Srodrigc lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp)); 1258153323Srodrigc left = block; 1259159451Srodrigc rbno = be32_to_cpu(left->bb_rightsib); 1260153323Srodrigc if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno, 1261153323Srodrigc rbno, 0, &rbp, XFS_INO_BTREE_REF))) 1262153323Srodrigc return error; 1263153323Srodrigc bp = rbp; 1264153323Srodrigc right = XFS_BUF_TO_INOBT_BLOCK(rbp); 1265153323Srodrigc if ((error = xfs_btree_check_sblock(cur, right, 1266153323Srodrigc cur->bc_nlevels - 1, rbp))) 1267153323Srodrigc return error; 1268153323Srodrigc nptr = 1; 1269153323Srodrigc } else { 1270153323Srodrigc /* 1271153323Srodrigc * Our block is right, pick up the left block. 1272153323Srodrigc */ 1273153323Srodrigc rbp = bp; 1274153323Srodrigc rbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(rbp)); 1275153323Srodrigc right = block; 1276159451Srodrigc lbno = be32_to_cpu(right->bb_leftsib); 1277153323Srodrigc if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno, 1278153323Srodrigc lbno, 0, &lbp, XFS_INO_BTREE_REF))) 1279153323Srodrigc return error; 1280153323Srodrigc bp = lbp; 1281153323Srodrigc left = XFS_BUF_TO_INOBT_BLOCK(lbp); 1282153323Srodrigc if ((error = xfs_btree_check_sblock(cur, left, 1283153323Srodrigc cur->bc_nlevels - 1, lbp))) 1284153323Srodrigc return error; 1285153323Srodrigc nptr = 2; 1286153323Srodrigc } 1287153323Srodrigc /* 1288153323Srodrigc * Fill in the new block's btree header and log it. 1289153323Srodrigc */ 1290159451Srodrigc new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]); 1291159451Srodrigc new->bb_level = cpu_to_be16(cur->bc_nlevels); 1292159451Srodrigc new->bb_numrecs = cpu_to_be16(2); 1293159451Srodrigc new->bb_leftsib = cpu_to_be32(NULLAGBLOCK); 1294159451Srodrigc new->bb_rightsib = cpu_to_be32(NULLAGBLOCK); 1295153323Srodrigc xfs_inobt_log_block(args.tp, nbp, XFS_BB_ALL_BITS); 1296153323Srodrigc ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK); 1297153323Srodrigc /* 1298153323Srodrigc * Fill in the key data in the new root. 1299153323Srodrigc */ 1300153323Srodrigc kp = XFS_INOBT_KEY_ADDR(new, 1, cur); 1301159451Srodrigc if (be16_to_cpu(left->bb_level) > 0) { 1302153323Srodrigc kp[0] = *XFS_INOBT_KEY_ADDR(left, 1, cur); /* INT_: struct copy */ 1303153323Srodrigc kp[1] = *XFS_INOBT_KEY_ADDR(right, 1, cur); /* INT_: struct copy */ 1304153323Srodrigc } else { 1305153323Srodrigc rp = XFS_INOBT_REC_ADDR(left, 1, cur); 1306153323Srodrigc INT_COPY(kp[0].ir_startino, rp->ir_startino, ARCH_CONVERT); 1307153323Srodrigc rp = XFS_INOBT_REC_ADDR(right, 1, cur); 1308153323Srodrigc INT_COPY(kp[1].ir_startino, rp->ir_startino, ARCH_CONVERT); 1309153323Srodrigc } 1310153323Srodrigc xfs_inobt_log_keys(cur, nbp, 1, 2); 1311153323Srodrigc /* 1312153323Srodrigc * Fill in the pointer data in the new root. 1313153323Srodrigc */ 1314153323Srodrigc pp = XFS_INOBT_PTR_ADDR(new, 1, cur); 1315159451Srodrigc pp[0] = cpu_to_be32(lbno); 1316159451Srodrigc pp[1] = cpu_to_be32(rbno); 1317153323Srodrigc xfs_inobt_log_ptrs(cur, nbp, 1, 2); 1318153323Srodrigc /* 1319153323Srodrigc * Fix up the cursor. 1320153323Srodrigc */ 1321153323Srodrigc xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); 1322153323Srodrigc cur->bc_ptrs[cur->bc_nlevels] = nptr; 1323153323Srodrigc cur->bc_nlevels++; 1324153323Srodrigc *stat = 1; 1325153323Srodrigc return 0; 1326153323Srodrigc} 1327153323Srodrigc 1328153323Srodrigc/* 1329153323Srodrigc * Move 1 record right from cur/level if possible. 1330153323Srodrigc * Update cur to reflect the new path. 1331153323Srodrigc */ 1332153323SrodrigcSTATIC int /* error */ 1333153323Srodrigcxfs_inobt_rshift( 1334153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1335153323Srodrigc int level, /* level to shift record on */ 1336153323Srodrigc int *stat) /* success/failure */ 1337153323Srodrigc{ 1338153323Srodrigc int error; /* error return value */ 1339153323Srodrigc int i; /* loop index */ 1340153323Srodrigc xfs_inobt_key_t key; /* key value for leaf level upward */ 1341153323Srodrigc xfs_buf_t *lbp; /* buffer for left (current) block */ 1342153323Srodrigc xfs_inobt_block_t *left; /* left (current) btree block */ 1343153323Srodrigc xfs_inobt_key_t *lkp; /* key pointer for left block */ 1344153323Srodrigc xfs_inobt_ptr_t *lpp; /* address pointer for left block */ 1345153323Srodrigc xfs_inobt_rec_t *lrp; /* record pointer for left block */ 1346153323Srodrigc xfs_buf_t *rbp; /* buffer for right neighbor block */ 1347153323Srodrigc xfs_inobt_block_t *right; /* right neighbor btree block */ 1348153323Srodrigc xfs_inobt_key_t *rkp; /* key pointer for right block */ 1349153323Srodrigc xfs_inobt_ptr_t *rpp; /* address pointer for right block */ 1350153323Srodrigc xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */ 1351153323Srodrigc xfs_btree_cur_t *tcur; /* temporary cursor */ 1352153323Srodrigc 1353153323Srodrigc /* 1354153323Srodrigc * Set up variables for this block as "left". 1355153323Srodrigc */ 1356153323Srodrigc lbp = cur->bc_bufs[level]; 1357153323Srodrigc left = XFS_BUF_TO_INOBT_BLOCK(lbp); 1358153323Srodrigc#ifdef DEBUG 1359153323Srodrigc if ((error = xfs_btree_check_sblock(cur, left, level, lbp))) 1360153323Srodrigc return error; 1361153323Srodrigc#endif 1362153323Srodrigc /* 1363153323Srodrigc * If we've got no right sibling then we can't shift an entry right. 1364153323Srodrigc */ 1365159451Srodrigc if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) { 1366153323Srodrigc *stat = 0; 1367153323Srodrigc return 0; 1368153323Srodrigc } 1369153323Srodrigc /* 1370153323Srodrigc * If the cursor entry is the one that would be moved, don't 1371153323Srodrigc * do it... it's too complicated. 1372153323Srodrigc */ 1373159451Srodrigc if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) { 1374153323Srodrigc *stat = 0; 1375153323Srodrigc return 0; 1376153323Srodrigc } 1377153323Srodrigc /* 1378153323Srodrigc * Set up the right neighbor as "right". 1379153323Srodrigc */ 1380153323Srodrigc if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp, 1381159451Srodrigc cur->bc_private.i.agno, be32_to_cpu(left->bb_rightsib), 1382159451Srodrigc 0, &rbp, XFS_INO_BTREE_REF))) 1383153323Srodrigc return error; 1384153323Srodrigc right = XFS_BUF_TO_INOBT_BLOCK(rbp); 1385153323Srodrigc if ((error = xfs_btree_check_sblock(cur, right, level, rbp))) 1386153323Srodrigc return error; 1387153323Srodrigc /* 1388153323Srodrigc * If it's full, it can't take another entry. 1389153323Srodrigc */ 1390159451Srodrigc if (be16_to_cpu(right->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) { 1391153323Srodrigc *stat = 0; 1392153323Srodrigc return 0; 1393153323Srodrigc } 1394153323Srodrigc /* 1395153323Srodrigc * Make a hole at the start of the right neighbor block, then 1396153323Srodrigc * copy the last left block entry to the hole. 1397153323Srodrigc */ 1398153323Srodrigc if (level > 0) { 1399159451Srodrigc lkp = XFS_INOBT_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur); 1400159451Srodrigc lpp = XFS_INOBT_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur); 1401153323Srodrigc rkp = XFS_INOBT_KEY_ADDR(right, 1, cur); 1402153323Srodrigc rpp = XFS_INOBT_PTR_ADDR(right, 1, cur); 1403153323Srodrigc#ifdef DEBUG 1404159451Srodrigc for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) { 1405159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level))) 1406153323Srodrigc return error; 1407153323Srodrigc } 1408153323Srodrigc#endif 1409159451Srodrigc memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp)); 1410159451Srodrigc memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp)); 1411153323Srodrigc#ifdef DEBUG 1412159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level))) 1413153323Srodrigc return error; 1414153323Srodrigc#endif 1415153323Srodrigc *rkp = *lkp; /* INT_: no change copy */ 1416153323Srodrigc *rpp = *lpp; /* INT_: no change copy */ 1417159451Srodrigc xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1); 1418159451Srodrigc xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1); 1419153323Srodrigc } else { 1420159451Srodrigc lrp = XFS_INOBT_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur); 1421153323Srodrigc rrp = XFS_INOBT_REC_ADDR(right, 1, cur); 1422159451Srodrigc memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp)); 1423153323Srodrigc *rrp = *lrp; 1424159451Srodrigc xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1); 1425153323Srodrigc key.ir_startino = rrp->ir_startino; /* INT_: direct copy */ 1426153323Srodrigc rkp = &key; 1427153323Srodrigc } 1428153323Srodrigc /* 1429153323Srodrigc * Decrement and log left's numrecs, bump and log right's numrecs. 1430153323Srodrigc */ 1431159451Srodrigc be16_add(&left->bb_numrecs, -1); 1432153323Srodrigc xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS); 1433159451Srodrigc be16_add(&right->bb_numrecs, 1); 1434153323Srodrigc#ifdef DEBUG 1435153323Srodrigc if (level > 0) 1436153323Srodrigc xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1); 1437153323Srodrigc else 1438153323Srodrigc xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1); 1439153323Srodrigc#endif 1440153323Srodrigc xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS); 1441153323Srodrigc /* 1442153323Srodrigc * Using a temporary cursor, update the parent key values of the 1443153323Srodrigc * block on the right. 1444153323Srodrigc */ 1445153323Srodrigc if ((error = xfs_btree_dup_cursor(cur, &tcur))) 1446153323Srodrigc return error; 1447153323Srodrigc xfs_btree_lastrec(tcur, level); 1448153323Srodrigc if ((error = xfs_inobt_increment(tcur, level, &i)) || 1449153323Srodrigc (error = xfs_inobt_updkey(tcur, rkp, level + 1))) { 1450153323Srodrigc xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 1451153323Srodrigc return error; 1452153323Srodrigc } 1453153323Srodrigc xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 1454153323Srodrigc *stat = 1; 1455153323Srodrigc return 0; 1456153323Srodrigc} 1457153323Srodrigc 1458153323Srodrigc/* 1459153323Srodrigc * Split cur/level block in half. 1460153323Srodrigc * Return new block number and its first record (to be inserted into parent). 1461153323Srodrigc */ 1462153323SrodrigcSTATIC int /* error */ 1463153323Srodrigcxfs_inobt_split( 1464153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1465153323Srodrigc int level, /* level to split */ 1466153323Srodrigc xfs_agblock_t *bnop, /* output: block number allocated */ 1467153323Srodrigc xfs_inobt_key_t *keyp, /* output: first key of new block */ 1468153323Srodrigc xfs_btree_cur_t **curp, /* output: new cursor */ 1469153323Srodrigc int *stat) /* success/failure */ 1470153323Srodrigc{ 1471153323Srodrigc xfs_alloc_arg_t args; /* allocation argument structure */ 1472153323Srodrigc int error; /* error return value */ 1473153323Srodrigc int i; /* loop index/record number */ 1474153323Srodrigc xfs_agblock_t lbno; /* left (current) block number */ 1475153323Srodrigc xfs_buf_t *lbp; /* buffer for left block */ 1476153323Srodrigc xfs_inobt_block_t *left; /* left (current) btree block */ 1477153323Srodrigc xfs_inobt_key_t *lkp; /* left btree key pointer */ 1478153323Srodrigc xfs_inobt_ptr_t *lpp; /* left btree address pointer */ 1479153323Srodrigc xfs_inobt_rec_t *lrp; /* left btree record pointer */ 1480153323Srodrigc xfs_buf_t *rbp; /* buffer for right block */ 1481153323Srodrigc xfs_inobt_block_t *right; /* right (new) btree block */ 1482153323Srodrigc xfs_inobt_key_t *rkp; /* right btree key pointer */ 1483153323Srodrigc xfs_inobt_ptr_t *rpp; /* right btree address pointer */ 1484153323Srodrigc xfs_inobt_rec_t *rrp; /* right btree record pointer */ 1485153323Srodrigc 1486153323Srodrigc /* 1487153323Srodrigc * Set up left block (current one). 1488153323Srodrigc */ 1489153323Srodrigc lbp = cur->bc_bufs[level]; 1490153323Srodrigc args.tp = cur->bc_tp; 1491153323Srodrigc args.mp = cur->bc_mp; 1492153323Srodrigc lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp)); 1493153323Srodrigc /* 1494153323Srodrigc * Allocate the new block. 1495153323Srodrigc * If we can't do it, we're toast. Give up. 1496153323Srodrigc */ 1497153323Srodrigc args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.i.agno, lbno); 1498153323Srodrigc args.mod = args.minleft = args.alignment = args.total = args.wasdel = 1499153323Srodrigc args.isfl = args.userdata = args.minalignslop = 0; 1500153323Srodrigc args.minlen = args.maxlen = args.prod = 1; 1501153323Srodrigc args.type = XFS_ALLOCTYPE_NEAR_BNO; 1502153323Srodrigc if ((error = xfs_alloc_vextent(&args))) 1503153323Srodrigc return error; 1504153323Srodrigc if (args.fsbno == NULLFSBLOCK) { 1505153323Srodrigc *stat = 0; 1506153323Srodrigc return 0; 1507153323Srodrigc } 1508153323Srodrigc ASSERT(args.len == 1); 1509153323Srodrigc rbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0); 1510153323Srodrigc /* 1511153323Srodrigc * Set up the new block as "right". 1512153323Srodrigc */ 1513153323Srodrigc right = XFS_BUF_TO_INOBT_BLOCK(rbp); 1514153323Srodrigc /* 1515153323Srodrigc * "Left" is the current (according to the cursor) block. 1516153323Srodrigc */ 1517153323Srodrigc left = XFS_BUF_TO_INOBT_BLOCK(lbp); 1518153323Srodrigc#ifdef DEBUG 1519153323Srodrigc if ((error = xfs_btree_check_sblock(cur, left, level, lbp))) 1520153323Srodrigc return error; 1521153323Srodrigc#endif 1522153323Srodrigc /* 1523153323Srodrigc * Fill in the btree header for the new block. 1524153323Srodrigc */ 1525159451Srodrigc right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]); 1526159451Srodrigc right->bb_level = left->bb_level; 1527159451Srodrigc right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2); 1528153323Srodrigc /* 1529153323Srodrigc * Make sure that if there's an odd number of entries now, that 1530153323Srodrigc * each new block will have the same number of entries. 1531153323Srodrigc */ 1532159451Srodrigc if ((be16_to_cpu(left->bb_numrecs) & 1) && 1533159451Srodrigc cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1) 1534159451Srodrigc be16_add(&right->bb_numrecs, 1); 1535159451Srodrigc i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1; 1536153323Srodrigc /* 1537153323Srodrigc * For non-leaf blocks, copy keys and addresses over to the new block. 1538153323Srodrigc */ 1539153323Srodrigc if (level > 0) { 1540153323Srodrigc lkp = XFS_INOBT_KEY_ADDR(left, i, cur); 1541153323Srodrigc lpp = XFS_INOBT_PTR_ADDR(left, i, cur); 1542153323Srodrigc rkp = XFS_INOBT_KEY_ADDR(right, 1, cur); 1543153323Srodrigc rpp = XFS_INOBT_PTR_ADDR(right, 1, cur); 1544153323Srodrigc#ifdef DEBUG 1545159451Srodrigc for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) { 1546159451Srodrigc if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level))) 1547153323Srodrigc return error; 1548153323Srodrigc } 1549153323Srodrigc#endif 1550159451Srodrigc memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp)); 1551159451Srodrigc memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp)); 1552159451Srodrigc xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs)); 1553159451Srodrigc xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs)); 1554153323Srodrigc *keyp = *rkp; 1555153323Srodrigc } 1556153323Srodrigc /* 1557153323Srodrigc * For leaf blocks, copy records over to the new block. 1558153323Srodrigc */ 1559153323Srodrigc else { 1560153323Srodrigc lrp = XFS_INOBT_REC_ADDR(left, i, cur); 1561153323Srodrigc rrp = XFS_INOBT_REC_ADDR(right, 1, cur); 1562159451Srodrigc memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp)); 1563159451Srodrigc xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs)); 1564153323Srodrigc keyp->ir_startino = rrp->ir_startino; /* INT_: direct copy */ 1565153323Srodrigc } 1566153323Srodrigc /* 1567153323Srodrigc * Find the left block number by looking in the buffer. 1568153323Srodrigc * Adjust numrecs, sibling pointers. 1569153323Srodrigc */ 1570159451Srodrigc be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs))); 1571159451Srodrigc right->bb_rightsib = left->bb_rightsib; 1572159451Srodrigc left->bb_rightsib = cpu_to_be32(args.agbno); 1573159451Srodrigc right->bb_leftsib = cpu_to_be32(lbno); 1574153323Srodrigc xfs_inobt_log_block(args.tp, rbp, XFS_BB_ALL_BITS); 1575153323Srodrigc xfs_inobt_log_block(args.tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB); 1576153323Srodrigc /* 1577153323Srodrigc * If there's a block to the new block's right, make that block 1578153323Srodrigc * point back to right instead of to left. 1579153323Srodrigc */ 1580159451Srodrigc if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) { 1581153323Srodrigc xfs_inobt_block_t *rrblock; /* rr btree block */ 1582153323Srodrigc xfs_buf_t *rrbp; /* buffer for rrblock */ 1583153323Srodrigc 1584153323Srodrigc if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno, 1585159451Srodrigc be32_to_cpu(right->bb_rightsib), 0, &rrbp, 1586153323Srodrigc XFS_INO_BTREE_REF))) 1587153323Srodrigc return error; 1588153323Srodrigc rrblock = XFS_BUF_TO_INOBT_BLOCK(rrbp); 1589153323Srodrigc if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp))) 1590153323Srodrigc return error; 1591159451Srodrigc rrblock->bb_leftsib = cpu_to_be32(args.agbno); 1592153323Srodrigc xfs_inobt_log_block(args.tp, rrbp, XFS_BB_LEFTSIB); 1593153323Srodrigc } 1594153323Srodrigc /* 1595153323Srodrigc * If the cursor is really in the right block, move it there. 1596153323Srodrigc * If it's just pointing past the last entry in left, then we'll 1597153323Srodrigc * insert there, so don't change anything in that case. 1598153323Srodrigc */ 1599159451Srodrigc if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) { 1600153323Srodrigc xfs_btree_setbuf(cur, level, rbp); 1601159451Srodrigc cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs); 1602153323Srodrigc } 1603153323Srodrigc /* 1604153323Srodrigc * If there are more levels, we'll need another cursor which refers 1605153323Srodrigc * the right block, no matter where this cursor was. 1606153323Srodrigc */ 1607153323Srodrigc if (level + 1 < cur->bc_nlevels) { 1608153323Srodrigc if ((error = xfs_btree_dup_cursor(cur, curp))) 1609153323Srodrigc return error; 1610153323Srodrigc (*curp)->bc_ptrs[level + 1]++; 1611153323Srodrigc } 1612153323Srodrigc *bnop = args.agbno; 1613153323Srodrigc *stat = 1; 1614153323Srodrigc return 0; 1615153323Srodrigc} 1616153323Srodrigc 1617153323Srodrigc/* 1618153323Srodrigc * Update keys at all levels from here to the root along the cursor's path. 1619153323Srodrigc */ 1620153323SrodrigcSTATIC int /* error */ 1621153323Srodrigcxfs_inobt_updkey( 1622153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1623153323Srodrigc xfs_inobt_key_t *keyp, /* new key value to update to */ 1624153323Srodrigc int level) /* starting level for update */ 1625153323Srodrigc{ 1626153323Srodrigc int ptr; /* index of key in block */ 1627153323Srodrigc 1628153323Srodrigc /* 1629153323Srodrigc * Go up the tree from this level toward the root. 1630153323Srodrigc * At each level, update the key value to the value input. 1631153323Srodrigc * Stop when we reach a level where the cursor isn't pointing 1632153323Srodrigc * at the first entry in the block. 1633153323Srodrigc */ 1634153323Srodrigc for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { 1635153323Srodrigc xfs_buf_t *bp; /* buffer for block */ 1636153323Srodrigc xfs_inobt_block_t *block; /* btree block */ 1637153323Srodrigc#ifdef DEBUG 1638153323Srodrigc int error; /* error return value */ 1639153323Srodrigc#endif 1640153323Srodrigc xfs_inobt_key_t *kp; /* ptr to btree block keys */ 1641153323Srodrigc 1642153323Srodrigc bp = cur->bc_bufs[level]; 1643153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1644153323Srodrigc#ifdef DEBUG 1645153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, level, bp))) 1646153323Srodrigc return error; 1647153323Srodrigc#endif 1648153323Srodrigc ptr = cur->bc_ptrs[level]; 1649153323Srodrigc kp = XFS_INOBT_KEY_ADDR(block, ptr, cur); 1650153323Srodrigc *kp = *keyp; 1651153323Srodrigc xfs_inobt_log_keys(cur, bp, ptr, ptr); 1652153323Srodrigc } 1653153323Srodrigc return 0; 1654153323Srodrigc} 1655153323Srodrigc 1656153323Srodrigc/* 1657153323Srodrigc * Externally visible routines. 1658153323Srodrigc */ 1659153323Srodrigc 1660153323Srodrigc/* 1661153323Srodrigc * Decrement cursor by one record at the level. 1662153323Srodrigc * For nonzero levels the leaf-ward information is untouched. 1663153323Srodrigc */ 1664153323Srodrigcint /* error */ 1665153323Srodrigcxfs_inobt_decrement( 1666153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1667153323Srodrigc int level, /* level in btree, 0 is leaf */ 1668153323Srodrigc int *stat) /* success/failure */ 1669153323Srodrigc{ 1670153323Srodrigc xfs_inobt_block_t *block; /* btree block */ 1671153323Srodrigc int error; 1672153323Srodrigc int lev; /* btree level */ 1673153323Srodrigc 1674153323Srodrigc ASSERT(level < cur->bc_nlevels); 1675153323Srodrigc /* 1676153323Srodrigc * Read-ahead to the left at this level. 1677153323Srodrigc */ 1678153323Srodrigc xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA); 1679153323Srodrigc /* 1680153323Srodrigc * Decrement the ptr at this level. If we're still in the block 1681153323Srodrigc * then we're done. 1682153323Srodrigc */ 1683153323Srodrigc if (--cur->bc_ptrs[level] > 0) { 1684153323Srodrigc *stat = 1; 1685153323Srodrigc return 0; 1686153323Srodrigc } 1687153323Srodrigc /* 1688153323Srodrigc * Get a pointer to the btree block. 1689153323Srodrigc */ 1690153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[level]); 1691153323Srodrigc#ifdef DEBUG 1692153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, level, 1693153323Srodrigc cur->bc_bufs[level]))) 1694153323Srodrigc return error; 1695153323Srodrigc#endif 1696153323Srodrigc /* 1697153323Srodrigc * If we just went off the left edge of the tree, return failure. 1698153323Srodrigc */ 1699159451Srodrigc if (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK) { 1700153323Srodrigc *stat = 0; 1701153323Srodrigc return 0; 1702153323Srodrigc } 1703153323Srodrigc /* 1704153323Srodrigc * March up the tree decrementing pointers. 1705153323Srodrigc * Stop when we don't go off the left edge of a block. 1706153323Srodrigc */ 1707153323Srodrigc for (lev = level + 1; lev < cur->bc_nlevels; lev++) { 1708153323Srodrigc if (--cur->bc_ptrs[lev] > 0) 1709153323Srodrigc break; 1710153323Srodrigc /* 1711153323Srodrigc * Read-ahead the left block, we're going to read it 1712153323Srodrigc * in the next loop. 1713153323Srodrigc */ 1714153323Srodrigc xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA); 1715153323Srodrigc } 1716153323Srodrigc /* 1717153323Srodrigc * If we went off the root then we are seriously confused. 1718153323Srodrigc */ 1719153323Srodrigc ASSERT(lev < cur->bc_nlevels); 1720153323Srodrigc /* 1721153323Srodrigc * Now walk back down the tree, fixing up the cursor's buffer 1722153323Srodrigc * pointers and key numbers. 1723153323Srodrigc */ 1724153323Srodrigc for (block = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[lev]); lev > level; ) { 1725153323Srodrigc xfs_agblock_t agbno; /* block number of btree block */ 1726153323Srodrigc xfs_buf_t *bp; /* buffer containing btree block */ 1727153323Srodrigc 1728159451Srodrigc agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, cur->bc_ptrs[lev], cur)); 1729153323Srodrigc if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp, 1730153323Srodrigc cur->bc_private.i.agno, agbno, 0, &bp, 1731153323Srodrigc XFS_INO_BTREE_REF))) 1732153323Srodrigc return error; 1733153323Srodrigc lev--; 1734153323Srodrigc xfs_btree_setbuf(cur, lev, bp); 1735153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1736153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, lev, bp))) 1737153323Srodrigc return error; 1738159451Srodrigc cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs); 1739153323Srodrigc } 1740153323Srodrigc *stat = 1; 1741153323Srodrigc return 0; 1742153323Srodrigc} 1743153323Srodrigc 1744153323Srodrigc/* 1745153323Srodrigc * Delete the record pointed to by cur. 1746153323Srodrigc * The cursor refers to the place where the record was (could be inserted) 1747153323Srodrigc * when the operation returns. 1748153323Srodrigc */ 1749153323Srodrigcint /* error */ 1750153323Srodrigcxfs_inobt_delete( 1751153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1752153323Srodrigc int *stat) /* success/failure */ 1753153323Srodrigc{ 1754153323Srodrigc int error; 1755153323Srodrigc int i; /* result code */ 1756153323Srodrigc int level; /* btree level */ 1757153323Srodrigc 1758153323Srodrigc /* 1759153323Srodrigc * Go up the tree, starting at leaf level. 1760153323Srodrigc * If 2 is returned then a join was done; go to the next level. 1761153323Srodrigc * Otherwise we are done. 1762153323Srodrigc */ 1763153323Srodrigc for (level = 0, i = 2; i == 2; level++) { 1764153323Srodrigc if ((error = xfs_inobt_delrec(cur, level, &i))) 1765153323Srodrigc return error; 1766153323Srodrigc } 1767153323Srodrigc if (i == 0) { 1768153323Srodrigc for (level = 1; level < cur->bc_nlevels; level++) { 1769153323Srodrigc if (cur->bc_ptrs[level] == 0) { 1770153323Srodrigc if ((error = xfs_inobt_decrement(cur, level, &i))) 1771153323Srodrigc return error; 1772153323Srodrigc break; 1773153323Srodrigc } 1774153323Srodrigc } 1775153323Srodrigc } 1776153323Srodrigc *stat = i; 1777153323Srodrigc return 0; 1778153323Srodrigc} 1779153323Srodrigc 1780153323Srodrigc 1781153323Srodrigc/* 1782153323Srodrigc * Get the data from the pointed-to record. 1783153323Srodrigc */ 1784153323Srodrigcint /* error */ 1785153323Srodrigcxfs_inobt_get_rec( 1786153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1787153323Srodrigc xfs_agino_t *ino, /* output: starting inode of chunk */ 1788153323Srodrigc __int32_t *fcnt, /* output: number of free inodes */ 1789153323Srodrigc xfs_inofree_t *free, /* output: free inode mask */ 1790159451Srodrigc int *stat) /* output: success/failure */ 1791153323Srodrigc{ 1792153323Srodrigc xfs_inobt_block_t *block; /* btree block */ 1793153323Srodrigc xfs_buf_t *bp; /* buffer containing btree block */ 1794153323Srodrigc#ifdef DEBUG 1795153323Srodrigc int error; /* error return value */ 1796153323Srodrigc#endif 1797153323Srodrigc int ptr; /* record number */ 1798153323Srodrigc xfs_inobt_rec_t *rec; /* record data */ 1799153323Srodrigc 1800153323Srodrigc bp = cur->bc_bufs[0]; 1801153323Srodrigc ptr = cur->bc_ptrs[0]; 1802153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1803153323Srodrigc#ifdef DEBUG 1804153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, 0, bp))) 1805153323Srodrigc return error; 1806153323Srodrigc#endif 1807153323Srodrigc /* 1808153323Srodrigc * Off the right end or left end, return failure. 1809153323Srodrigc */ 1810159451Srodrigc if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) { 1811153323Srodrigc *stat = 0; 1812153323Srodrigc return 0; 1813153323Srodrigc } 1814153323Srodrigc /* 1815153323Srodrigc * Point to the record and extract its data. 1816153323Srodrigc */ 1817153323Srodrigc rec = XFS_INOBT_REC_ADDR(block, ptr, cur); 1818159451Srodrigc *ino = INT_GET(rec->ir_startino, ARCH_CONVERT); 1819159451Srodrigc *fcnt = INT_GET(rec->ir_freecount, ARCH_CONVERT); 1820159451Srodrigc *free = INT_GET(rec->ir_free, ARCH_CONVERT); 1821153323Srodrigc *stat = 1; 1822153323Srodrigc return 0; 1823153323Srodrigc} 1824153323Srodrigc 1825153323Srodrigc/* 1826153323Srodrigc * Increment cursor by one record at the level. 1827153323Srodrigc * For nonzero levels the leaf-ward information is untouched. 1828153323Srodrigc */ 1829153323Srodrigcint /* error */ 1830153323Srodrigcxfs_inobt_increment( 1831153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1832153323Srodrigc int level, /* level in btree, 0 is leaf */ 1833153323Srodrigc int *stat) /* success/failure */ 1834153323Srodrigc{ 1835153323Srodrigc xfs_inobt_block_t *block; /* btree block */ 1836153323Srodrigc xfs_buf_t *bp; /* buffer containing btree block */ 1837153323Srodrigc int error; /* error return value */ 1838153323Srodrigc int lev; /* btree level */ 1839153323Srodrigc 1840153323Srodrigc ASSERT(level < cur->bc_nlevels); 1841153323Srodrigc /* 1842153323Srodrigc * Read-ahead to the right at this level. 1843153323Srodrigc */ 1844153323Srodrigc xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); 1845153323Srodrigc /* 1846153323Srodrigc * Get a pointer to the btree block. 1847153323Srodrigc */ 1848153323Srodrigc bp = cur->bc_bufs[level]; 1849153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1850153323Srodrigc#ifdef DEBUG 1851153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, level, bp))) 1852153323Srodrigc return error; 1853153323Srodrigc#endif 1854153323Srodrigc /* 1855153323Srodrigc * Increment the ptr at this level. If we're still in the block 1856153323Srodrigc * then we're done. 1857153323Srodrigc */ 1858159451Srodrigc if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) { 1859153323Srodrigc *stat = 1; 1860153323Srodrigc return 0; 1861153323Srodrigc } 1862153323Srodrigc /* 1863153323Srodrigc * If we just went off the right edge of the tree, return failure. 1864153323Srodrigc */ 1865159451Srodrigc if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) { 1866153323Srodrigc *stat = 0; 1867153323Srodrigc return 0; 1868153323Srodrigc } 1869153323Srodrigc /* 1870153323Srodrigc * March up the tree incrementing pointers. 1871153323Srodrigc * Stop when we don't go off the right edge of a block. 1872153323Srodrigc */ 1873153323Srodrigc for (lev = level + 1; lev < cur->bc_nlevels; lev++) { 1874153323Srodrigc bp = cur->bc_bufs[lev]; 1875153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1876153323Srodrigc#ifdef DEBUG 1877153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, lev, bp))) 1878153323Srodrigc return error; 1879153323Srodrigc#endif 1880159451Srodrigc if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs)) 1881153323Srodrigc break; 1882153323Srodrigc /* 1883153323Srodrigc * Read-ahead the right block, we're going to read it 1884153323Srodrigc * in the next loop. 1885153323Srodrigc */ 1886153323Srodrigc xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA); 1887153323Srodrigc } 1888153323Srodrigc /* 1889153323Srodrigc * If we went off the root then we are seriously confused. 1890153323Srodrigc */ 1891153323Srodrigc ASSERT(lev < cur->bc_nlevels); 1892153323Srodrigc /* 1893153323Srodrigc * Now walk back down the tree, fixing up the cursor's buffer 1894153323Srodrigc * pointers and key numbers. 1895153323Srodrigc */ 1896153323Srodrigc for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_INOBT_BLOCK(bp); 1897153323Srodrigc lev > level; ) { 1898153323Srodrigc xfs_agblock_t agbno; /* block number of btree block */ 1899153323Srodrigc 1900159451Srodrigc agbno = be32_to_cpu(*XFS_INOBT_PTR_ADDR(block, cur->bc_ptrs[lev], cur)); 1901153323Srodrigc if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp, 1902153323Srodrigc cur->bc_private.i.agno, agbno, 0, &bp, 1903153323Srodrigc XFS_INO_BTREE_REF))) 1904153323Srodrigc return error; 1905153323Srodrigc lev--; 1906153323Srodrigc xfs_btree_setbuf(cur, lev, bp); 1907153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 1908153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, lev, bp))) 1909153323Srodrigc return error; 1910153323Srodrigc cur->bc_ptrs[lev] = 1; 1911153323Srodrigc } 1912153323Srodrigc *stat = 1; 1913153323Srodrigc return 0; 1914153323Srodrigc} 1915153323Srodrigc 1916153323Srodrigc/* 1917153323Srodrigc * Insert the current record at the point referenced by cur. 1918153323Srodrigc * The cursor may be inconsistent on return if splits have been done. 1919153323Srodrigc */ 1920153323Srodrigcint /* error */ 1921153323Srodrigcxfs_inobt_insert( 1922153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1923153323Srodrigc int *stat) /* success/failure */ 1924153323Srodrigc{ 1925153323Srodrigc int error; /* error return value */ 1926153323Srodrigc int i; /* result value, 0 for failure */ 1927153323Srodrigc int level; /* current level number in btree */ 1928153323Srodrigc xfs_agblock_t nbno; /* new block number (split result) */ 1929153323Srodrigc xfs_btree_cur_t *ncur; /* new cursor (split result) */ 1930153323Srodrigc xfs_inobt_rec_t nrec; /* record being inserted this level */ 1931153323Srodrigc xfs_btree_cur_t *pcur; /* previous level's cursor */ 1932153323Srodrigc 1933153323Srodrigc level = 0; 1934153323Srodrigc nbno = NULLAGBLOCK; 1935153323Srodrigc INT_SET(nrec.ir_startino, ARCH_CONVERT, cur->bc_rec.i.ir_startino); 1936153323Srodrigc INT_SET(nrec.ir_freecount, ARCH_CONVERT, cur->bc_rec.i.ir_freecount); 1937153323Srodrigc INT_SET(nrec.ir_free, ARCH_CONVERT, cur->bc_rec.i.ir_free); 1938153323Srodrigc ncur = (xfs_btree_cur_t *)0; 1939153323Srodrigc pcur = cur; 1940153323Srodrigc /* 1941153323Srodrigc * Loop going up the tree, starting at the leaf level. 1942153323Srodrigc * Stop when we don't get a split block, that must mean that 1943153323Srodrigc * the insert is finished with this level. 1944153323Srodrigc */ 1945153323Srodrigc do { 1946153323Srodrigc /* 1947153323Srodrigc * Insert nrec/nbno into this level of the tree. 1948153323Srodrigc * Note if we fail, nbno will be null. 1949153323Srodrigc */ 1950153323Srodrigc if ((error = xfs_inobt_insrec(pcur, level++, &nbno, &nrec, &ncur, 1951153323Srodrigc &i))) { 1952153323Srodrigc if (pcur != cur) 1953153323Srodrigc xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR); 1954153323Srodrigc return error; 1955153323Srodrigc } 1956153323Srodrigc /* 1957153323Srodrigc * See if the cursor we just used is trash. 1958153323Srodrigc * Can't trash the caller's cursor, but otherwise we should 1959153323Srodrigc * if ncur is a new cursor or we're about to be done. 1960153323Srodrigc */ 1961153323Srodrigc if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) { 1962153323Srodrigc cur->bc_nlevels = pcur->bc_nlevels; 1963153323Srodrigc xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR); 1964153323Srodrigc } 1965153323Srodrigc /* 1966153323Srodrigc * If we got a new cursor, switch to it. 1967153323Srodrigc */ 1968153323Srodrigc if (ncur) { 1969153323Srodrigc pcur = ncur; 1970153323Srodrigc ncur = (xfs_btree_cur_t *)0; 1971153323Srodrigc } 1972153323Srodrigc } while (nbno != NULLAGBLOCK); 1973153323Srodrigc *stat = i; 1974153323Srodrigc return 0; 1975153323Srodrigc} 1976153323Srodrigc 1977153323Srodrigc/* 1978153323Srodrigc * Lookup the record equal to ino in the btree given by cur. 1979153323Srodrigc */ 1980153323Srodrigcint /* error */ 1981153323Srodrigcxfs_inobt_lookup_eq( 1982153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 1983153323Srodrigc xfs_agino_t ino, /* starting inode of chunk */ 1984153323Srodrigc __int32_t fcnt, /* free inode count */ 1985153323Srodrigc xfs_inofree_t free, /* free inode mask */ 1986153323Srodrigc int *stat) /* success/failure */ 1987153323Srodrigc{ 1988153323Srodrigc cur->bc_rec.i.ir_startino = ino; 1989153323Srodrigc cur->bc_rec.i.ir_freecount = fcnt; 1990153323Srodrigc cur->bc_rec.i.ir_free = free; 1991153323Srodrigc return xfs_inobt_lookup(cur, XFS_LOOKUP_EQ, stat); 1992153323Srodrigc} 1993153323Srodrigc 1994153323Srodrigc/* 1995153323Srodrigc * Lookup the first record greater than or equal to ino 1996153323Srodrigc * in the btree given by cur. 1997153323Srodrigc */ 1998153323Srodrigcint /* error */ 1999153323Srodrigcxfs_inobt_lookup_ge( 2000153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 2001153323Srodrigc xfs_agino_t ino, /* starting inode of chunk */ 2002153323Srodrigc __int32_t fcnt, /* free inode count */ 2003153323Srodrigc xfs_inofree_t free, /* free inode mask */ 2004153323Srodrigc int *stat) /* success/failure */ 2005153323Srodrigc{ 2006153323Srodrigc cur->bc_rec.i.ir_startino = ino; 2007153323Srodrigc cur->bc_rec.i.ir_freecount = fcnt; 2008153323Srodrigc cur->bc_rec.i.ir_free = free; 2009153323Srodrigc return xfs_inobt_lookup(cur, XFS_LOOKUP_GE, stat); 2010153323Srodrigc} 2011153323Srodrigc 2012153323Srodrigc/* 2013153323Srodrigc * Lookup the first record less than or equal to ino 2014153323Srodrigc * in the btree given by cur. 2015153323Srodrigc */ 2016153323Srodrigcint /* error */ 2017153323Srodrigcxfs_inobt_lookup_le( 2018153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 2019153323Srodrigc xfs_agino_t ino, /* starting inode of chunk */ 2020153323Srodrigc __int32_t fcnt, /* free inode count */ 2021153323Srodrigc xfs_inofree_t free, /* free inode mask */ 2022153323Srodrigc int *stat) /* success/failure */ 2023153323Srodrigc{ 2024153323Srodrigc cur->bc_rec.i.ir_startino = ino; 2025153323Srodrigc cur->bc_rec.i.ir_freecount = fcnt; 2026153323Srodrigc cur->bc_rec.i.ir_free = free; 2027153323Srodrigc return xfs_inobt_lookup(cur, XFS_LOOKUP_LE, stat); 2028153323Srodrigc} 2029153323Srodrigc 2030153323Srodrigc/* 2031153323Srodrigc * Update the record referred to by cur, to the value given 2032153323Srodrigc * by [ino, fcnt, free]. 2033153323Srodrigc * This either works (return 0) or gets an EFSCORRUPTED error. 2034153323Srodrigc */ 2035153323Srodrigcint /* error */ 2036153323Srodrigcxfs_inobt_update( 2037153323Srodrigc xfs_btree_cur_t *cur, /* btree cursor */ 2038153323Srodrigc xfs_agino_t ino, /* starting inode of chunk */ 2039153323Srodrigc __int32_t fcnt, /* free inode count */ 2040153323Srodrigc xfs_inofree_t free) /* free inode mask */ 2041153323Srodrigc{ 2042153323Srodrigc xfs_inobt_block_t *block; /* btree block to update */ 2043153323Srodrigc xfs_buf_t *bp; /* buffer containing btree block */ 2044153323Srodrigc int error; /* error return value */ 2045153323Srodrigc int ptr; /* current record number (updating) */ 2046153323Srodrigc xfs_inobt_rec_t *rp; /* pointer to updated record */ 2047153323Srodrigc 2048153323Srodrigc /* 2049153323Srodrigc * Pick up the current block. 2050153323Srodrigc */ 2051153323Srodrigc bp = cur->bc_bufs[0]; 2052153323Srodrigc block = XFS_BUF_TO_INOBT_BLOCK(bp); 2053153323Srodrigc#ifdef DEBUG 2054153323Srodrigc if ((error = xfs_btree_check_sblock(cur, block, 0, bp))) 2055153323Srodrigc return error; 2056153323Srodrigc#endif 2057153323Srodrigc /* 2058153323Srodrigc * Get the address of the rec to be updated. 2059153323Srodrigc */ 2060153323Srodrigc ptr = cur->bc_ptrs[0]; 2061153323Srodrigc rp = XFS_INOBT_REC_ADDR(block, ptr, cur); 2062153323Srodrigc /* 2063153323Srodrigc * Fill in the new contents and log them. 2064153323Srodrigc */ 2065153323Srodrigc INT_SET(rp->ir_startino, ARCH_CONVERT, ino); 2066153323Srodrigc INT_SET(rp->ir_freecount, ARCH_CONVERT, fcnt); 2067153323Srodrigc INT_SET(rp->ir_free, ARCH_CONVERT, free); 2068153323Srodrigc xfs_inobt_log_recs(cur, bp, ptr, ptr); 2069153323Srodrigc /* 2070153323Srodrigc * Updating first record in leaf. Pass new key value up to our parent. 2071153323Srodrigc */ 2072153323Srodrigc if (ptr == 1) { 2073153323Srodrigc xfs_inobt_key_t key; /* key containing [ino] */ 2074153323Srodrigc 2075153323Srodrigc INT_SET(key.ir_startino, ARCH_CONVERT, ino); 2076153323Srodrigc if ((error = xfs_inobt_updkey(cur, &key, 1))) 2077153323Srodrigc return error; 2078153323Srodrigc } 2079153323Srodrigc return 0; 2080153323Srodrigc} 2081