aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/xfs/xfs_alloc_btree.c136
-rw-r--r--fs/xfs/xfs_bmap_btree.c142
-rw-r--r--fs/xfs/xfs_btree.c319
-rw-r--r--fs/xfs/xfs_btree.h7
-rw-r--r--fs/xfs/xfs_ialloc_btree.c135
5 files changed, 331 insertions, 408 deletions
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index c5c32999b810..31e42891fc9a 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -49,7 +49,6 @@ STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
49STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 49STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
50STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *); 50STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
51STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *); 51STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
52STATIC int xfs_alloc_rshift(xfs_btree_cur_t *, int, int *);
53STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *, 52STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
54 xfs_alloc_key_t *, xfs_btree_cur_t **, int *); 53 xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
55 54
@@ -391,7 +390,7 @@ xfs_alloc_delrec(
391 */ 390 */
392 if (be16_to_cpu(left->bb_numrecs) - 1 >= 391 if (be16_to_cpu(left->bb_numrecs) - 1 >=
393 XFS_ALLOC_BLOCK_MINRECS(level, cur)) { 392 XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
394 if ((error = xfs_alloc_rshift(tcur, level, &i))) 393 if ((error = xfs_btree_rshift(tcur, level, &i)))
395 goto error0; 394 goto error0;
396 if (i) { 395 if (i) {
397 ASSERT(be16_to_cpu(block->bb_numrecs) >= 396 ASSERT(be16_to_cpu(block->bb_numrecs) >=
@@ -683,7 +682,7 @@ xfs_alloc_insrec(
683 /* 682 /*
684 * First, try shifting an entry to the right neighbor. 683 * First, try shifting an entry to the right neighbor.
685 */ 684 */
686 if ((error = xfs_alloc_rshift(cur, level, &i))) 685 if ((error = xfs_btree_rshift(cur, level, &i)))
687 return error; 686 return error;
688 if (i) { 687 if (i) {
689 /* nothing */ 688 /* nothing */
@@ -1233,137 +1232,6 @@ xfs_alloc_newroot(
1233} 1232}
1234 1233
1235/* 1234/*
1236 * Move 1 record right from cur/level if possible.
1237 * Update cur to reflect the new path.
1238 */
1239STATIC int /* error */
1240xfs_alloc_rshift(
1241 xfs_btree_cur_t *cur, /* btree cursor */
1242 int level, /* level to shift record on */
1243 int *stat) /* success/failure */
1244{
1245 int error; /* error return value */
1246 int i; /* loop index */
1247 xfs_alloc_key_t key; /* key value for leaf level upward */
1248 xfs_buf_t *lbp; /* buffer for left (current) block */
1249 xfs_alloc_block_t *left; /* left (current) btree block */
1250 xfs_buf_t *rbp; /* buffer for right neighbor block */
1251 xfs_alloc_block_t *right; /* right neighbor btree block */
1252 xfs_alloc_key_t *rkp; /* key pointer for right block */
1253 xfs_btree_cur_t *tcur; /* temporary cursor */
1254
1255 /*
1256 * Set up variables for this block as "left".
1257 */
1258 lbp = cur->bc_bufs[level];
1259 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1260#ifdef DEBUG
1261 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1262 return error;
1263#endif
1264 /*
1265 * If we've got no right sibling then we can't shift an entry right.
1266 */
1267 if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
1268 *stat = 0;
1269 return 0;
1270 }
1271 /*
1272 * If the cursor entry is the one that would be moved, don't
1273 * do it... it's too complicated.
1274 */
1275 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
1276 *stat = 0;
1277 return 0;
1278 }
1279 /*
1280 * Set up the right neighbor as "right".
1281 */
1282 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1283 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
1284 0, &rbp, XFS_ALLOC_BTREE_REF)))
1285 return error;
1286 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1287 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1288 return error;
1289 /*
1290 * If it's full, it can't take another entry.
1291 */
1292 if (be16_to_cpu(right->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1293 *stat = 0;
1294 return 0;
1295 }
1296 /*
1297 * Make a hole at the start of the right neighbor block, then
1298 * copy the last left block entry to the hole.
1299 */
1300 if (level > 0) {
1301 xfs_alloc_key_t *lkp; /* key pointer for left block */
1302 xfs_alloc_ptr_t *lpp; /* address pointer for left block */
1303 xfs_alloc_ptr_t *rpp; /* address pointer for right block */
1304
1305 lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1306 lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1307 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1308 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1309#ifdef DEBUG
1310 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1311 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
1312 return error;
1313 }
1314#endif
1315 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1316 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1317#ifdef DEBUG
1318 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
1319 return error;
1320#endif
1321 *rkp = *lkp;
1322 *rpp = *lpp;
1323 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1324 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1325 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
1326 } else {
1327 xfs_alloc_rec_t *lrp; /* record pointer for left block */
1328 xfs_alloc_rec_t *rrp; /* record pointer for right block */
1329
1330 lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1331 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1332 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1333 *rrp = *lrp;
1334 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1335 key.ar_startblock = rrp->ar_startblock;
1336 key.ar_blockcount = rrp->ar_blockcount;
1337 rkp = &key;
1338 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
1339 }
1340 /*
1341 * Decrement and log left's numrecs, bump and log right's numrecs.
1342 */
1343 be16_add_cpu(&left->bb_numrecs, -1);
1344 xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1345 be16_add_cpu(&right->bb_numrecs, 1);
1346 xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1347 /*
1348 * Using a temporary cursor, update the parent key values of the
1349 * block on the right.
1350 */
1351 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1352 return error;
1353 i = xfs_btree_lastrec(tcur, level);
1354 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1355 if ((error = xfs_btree_increment(tcur, level, &i)) ||
1356 (error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1)))
1357 goto error0;
1358 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1359 *stat = 1;
1360 return 0;
1361error0:
1362 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1363 return error;
1364}
1365
1366/*
1367 * Split cur/level block in half. 1235 * Split cur/level block in half.
1368 * Return new block number and its first record (to be inserted into parent). 1236 * Return new block number and its first record (to be inserted into parent).
1369 */ 1237 */
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 99200a9898f7..9d18fa8aa1da 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -53,7 +53,6 @@ STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
53STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int); 53STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
54STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 54STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
55STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *); 55STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
56STATIC int xfs_bmbt_rshift(xfs_btree_cur_t *, int, int *);
57STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *, 56STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
58 __uint64_t *, xfs_btree_cur_t **, int *); 57 __uint64_t *, xfs_btree_cur_t **, int *);
59 58
@@ -327,7 +326,7 @@ xfs_bmbt_delrec(
327 bno = be64_to_cpu(left->bb_rightsib); 326 bno = be64_to_cpu(left->bb_rightsib);
328 if (be16_to_cpu(left->bb_numrecs) - 1 >= 327 if (be16_to_cpu(left->bb_numrecs) - 1 >=
329 XFS_BMAP_BLOCK_IMINRECS(level, cur)) { 328 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
330 if ((error = xfs_bmbt_rshift(tcur, level, &i))) { 329 if ((error = xfs_btree_rshift(tcur, level, &i))) {
331 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 330 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
332 goto error0; 331 goto error0;
333 } 332 }
@@ -538,7 +537,7 @@ xfs_bmbt_insrec(
538 logflags); 537 logflags);
539 block = xfs_bmbt_get_block(cur, level, &bp); 538 block = xfs_bmbt_get_block(cur, level, &bp);
540 } else { 539 } else {
541 if ((error = xfs_bmbt_rshift(cur, level, &i))) { 540 if ((error = xfs_btree_rshift(cur, level, &i))) {
542 XFS_BMBT_TRACE_CURSOR(cur, ERROR); 541 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
543 return error; 542 return error;
544 } 543 }
@@ -945,143 +944,6 @@ xfs_bmbt_lshift(
945} 944}
946 945
947/* 946/*
948 * Move 1 record right from cur/level if possible.
949 * Update cur to reflect the new path.
950 */
951STATIC int /* error */
952xfs_bmbt_rshift(
953 xfs_btree_cur_t *cur,
954 int level,
955 int *stat) /* success/failure */
956{
957 int error; /* error return value */
958 int i; /* loop counter */
959 xfs_bmbt_key_t key; /* bmap btree key */
960 xfs_buf_t *lbp; /* left buffer pointer */
961 xfs_bmbt_block_t *left; /* left btree block */
962 xfs_bmbt_key_t *lkp; /* left btree key */
963 xfs_bmbt_ptr_t *lpp; /* left address pointer */
964 xfs_bmbt_rec_t *lrp; /* left record pointer */
965 xfs_mount_t *mp; /* file system mount point */
966 xfs_buf_t *rbp; /* right buffer pointer */
967 xfs_bmbt_block_t *right; /* right btree block */
968 xfs_bmbt_key_t *rkp; /* right btree key */
969 xfs_bmbt_ptr_t *rpp; /* right address pointer */
970 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
971 struct xfs_btree_cur *tcur; /* temporary btree cursor */
972
973 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
974 XFS_BMBT_TRACE_ARGI(cur, level);
975 if (level == cur->bc_nlevels - 1) {
976 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
977 *stat = 0;
978 return 0;
979 }
980 lbp = cur->bc_bufs[level];
981 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
982#ifdef DEBUG
983 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
984 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
985 return error;
986 }
987#endif
988 if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
989 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
990 *stat = 0;
991 return 0;
992 }
993 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
994 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
995 *stat = 0;
996 return 0;
997 }
998 mp = cur->bc_mp;
999 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
1000 &rbp, XFS_BMAP_BTREE_REF))) {
1001 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1002 return error;
1003 }
1004 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1005 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1006 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1007 return error;
1008 }
1009 if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1010 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1011 *stat = 0;
1012 return 0;
1013 }
1014 if (level > 0) {
1015 lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1016 lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1017 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1018 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1019#ifdef DEBUG
1020 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1021 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
1022 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1023 return error;
1024 }
1025 }
1026#endif
1027 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1028 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1029#ifdef DEBUG
1030 if ((error = xfs_btree_check_lptr_disk(cur, *lpp, level))) {
1031 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1032 return error;
1033 }
1034#endif
1035 *rkp = *lkp;
1036 *rpp = *lpp;
1037 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1038 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1039 } else {
1040 lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1041 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1042 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1043 *rrp = *lrp;
1044 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1045 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1046 rkp = &key;
1047 }
1048 be16_add_cpu(&left->bb_numrecs, -1);
1049 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1050 be16_add_cpu(&right->bb_numrecs, 1);
1051#ifdef DEBUG
1052 if (level > 0)
1053 xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
1054 else
1055 xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
1056#endif
1057 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1058 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
1059 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1060 return error;
1061 }
1062 i = xfs_btree_lastrec(tcur, level);
1063 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1064 if ((error = xfs_btree_increment(tcur, level, &i))) {
1065 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1066 goto error1;
1067 }
1068 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1069 if ((error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1))) {
1070 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1071 goto error1;
1072 }
1073 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1074 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1075 *stat = 1;
1076 return 0;
1077error0:
1078 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1079error1:
1080 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1081 return error;
1082}
1083
1084/*
1085 * Determine the extent state. 947 * Determine the extent state.
1086 */ 948 */
1087/* ARGSUSED */ 949/* ARGSUSED */
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index 205272f282d9..e1a213781849 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -1118,6 +1118,77 @@ xfs_btree_copy_recs(
1118} 1118}
1119 1119
1120/* 1120/*
1121 * Copy block pointers from one btree block to another.
1122 */
1123STATIC void
1124xfs_btree_copy_ptrs(
1125 struct xfs_btree_cur *cur,
1126 union xfs_btree_ptr *dst_ptr,
1127 union xfs_btree_ptr *src_ptr,
1128 int numptrs)
1129{
1130 ASSERT(numptrs >= 0);
1131 memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1132}
1133
1134/*
1135 * Shift keys one index left/right inside a single btree block.
1136 */
1137STATIC void
1138xfs_btree_shift_keys(
1139 struct xfs_btree_cur *cur,
1140 union xfs_btree_key *key,
1141 int dir,
1142 int numkeys)
1143{
1144 char *dst_key;
1145
1146 ASSERT(numkeys >= 0);
1147 ASSERT(dir == 1 || dir == -1);
1148
1149 dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1150 memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1151}
1152
1153/*
1154 * Shift records one index left/right inside a single btree block.
1155 */
1156STATIC void
1157xfs_btree_shift_recs(
1158 struct xfs_btree_cur *cur,
1159 union xfs_btree_rec *rec,
1160 int dir,
1161 int numrecs)
1162{
1163 char *dst_rec;
1164
1165 ASSERT(numrecs >= 0);
1166 ASSERT(dir == 1 || dir == -1);
1167
1168 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1169 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1170}
1171
1172/*
1173 * Shift block pointers one index left/right inside a single btree block.
1174 */
1175STATIC void
1176xfs_btree_shift_ptrs(
1177 struct xfs_btree_cur *cur,
1178 union xfs_btree_ptr *ptr,
1179 int dir,
1180 int numptrs)
1181{
1182 char *dst_ptr;
1183
1184 ASSERT(numptrs >= 0);
1185 ASSERT(dir == 1 || dir == -1);
1186
1187 dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1188 memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1189}
1190
1191/*
1121 * Log key values from the btree block. 1192 * Log key values from the btree block.
1122 */ 1193 */
1123STATIC void 1194STATIC void
@@ -1163,6 +1234,79 @@ xfs_btree_log_recs(
1163} 1234}
1164 1235
1165/* 1236/*
1237 * Log block pointer fields from a btree block (nonleaf).
1238 */
1239STATIC void
1240xfs_btree_log_ptrs(
1241 struct xfs_btree_cur *cur, /* btree cursor */
1242 struct xfs_buf *bp, /* buffer containing btree block */
1243 int first, /* index of first pointer to log */
1244 int last) /* index of last pointer to log */
1245{
1246 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1247 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1248
1249 if (bp) {
1250 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
1251 int level = xfs_btree_get_level(block);
1252
1253 xfs_trans_log_buf(cur->bc_tp, bp,
1254 xfs_btree_ptr_offset(cur, first, level),
1255 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1256 } else {
1257 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1258 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1259 }
1260
1261 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1262}
1263
1264/*
1265 * Log fields from a btree block header.
1266 */
1267STATIC void
1268xfs_btree_log_block(
1269 struct xfs_btree_cur *cur, /* btree cursor */
1270 struct xfs_buf *bp, /* buffer containing btree block */
1271 int fields) /* mask of fields: XFS_BB_... */
1272{
1273 int first; /* first byte offset logged */
1274 int last; /* last byte offset logged */
1275 static const short soffsets[] = { /* table of offsets (short) */
1276 offsetof(struct xfs_btree_sblock, bb_magic),
1277 offsetof(struct xfs_btree_sblock, bb_level),
1278 offsetof(struct xfs_btree_sblock, bb_numrecs),
1279 offsetof(struct xfs_btree_sblock, bb_leftsib),
1280 offsetof(struct xfs_btree_sblock, bb_rightsib),
1281 sizeof(struct xfs_btree_sblock)
1282 };
1283 static const short loffsets[] = { /* table of offsets (long) */
1284 offsetof(struct xfs_btree_lblock, bb_magic),
1285 offsetof(struct xfs_btree_lblock, bb_level),
1286 offsetof(struct xfs_btree_lblock, bb_numrecs),
1287 offsetof(struct xfs_btree_lblock, bb_leftsib),
1288 offsetof(struct xfs_btree_lblock, bb_rightsib),
1289 sizeof(struct xfs_btree_lblock)
1290 };
1291
1292 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1293 XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
1294
1295 if (bp) {
1296 xfs_btree_offsets(fields,
1297 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1298 loffsets : soffsets,
1299 XFS_BB_NUM_BITS, &first, &last);
1300 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1301 } else {
1302 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1303 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1304 }
1305
1306 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1307}
1308
1309/*
1166 * Increment cursor by one record at the level. 1310 * Increment cursor by one record at the level.
1167 * For nonzero levels the leaf-ward information is untouched. 1311 * For nonzero levels the leaf-ward information is untouched.
1168 */ 1312 */
@@ -1368,7 +1512,6 @@ error0:
1368 return error; 1512 return error;
1369} 1513}
1370 1514
1371
1372STATIC int 1515STATIC int
1373xfs_btree_lookup_get_block( 1516xfs_btree_lookup_get_block(
1374 struct xfs_btree_cur *cur, /* btree cursor */ 1517 struct xfs_btree_cur *cur, /* btree cursor */
@@ -1697,3 +1840,177 @@ error0:
1697 return error; 1840 return error;
1698} 1841}
1699 1842
1843/*
1844 * Move 1 record right from cur/level if possible.
1845 * Update cur to reflect the new path.
1846 */
1847int /* error */
1848xfs_btree_rshift(
1849 struct xfs_btree_cur *cur,
1850 int level,
1851 int *stat) /* success/failure */
1852{
1853 union xfs_btree_key key; /* btree key */
1854 struct xfs_buf *lbp; /* left buffer pointer */
1855 struct xfs_btree_block *left; /* left btree block */
1856 struct xfs_buf *rbp; /* right buffer pointer */
1857 struct xfs_btree_block *right; /* right btree block */
1858 struct xfs_btree_cur *tcur; /* temporary btree cursor */
1859 union xfs_btree_ptr rptr; /* right block pointer */
1860 union xfs_btree_key *rkp; /* right btree key */
1861 int rrecs; /* right record count */
1862 int lrecs; /* left record count */
1863 int error; /* error return value */
1864 int i; /* loop counter */
1865
1866 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1867 XFS_BTREE_TRACE_ARGI(cur, level);
1868
1869 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1870 (level == cur->bc_nlevels - 1))
1871 goto out0;
1872
1873 /* Set up variables for this block as "left". */
1874 left = xfs_btree_get_block(cur, level, &lbp);
1875
1876#ifdef DEBUG
1877 error = xfs_btree_check_block(cur, left, level, lbp);
1878 if (error)
1879 goto error0;
1880#endif
1881
1882 /* If we've got no right sibling then we can't shift an entry right. */
1883 xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
1884 if (xfs_btree_ptr_is_null(cur, &rptr))
1885 goto out0;
1886
1887 /*
1888 * If the cursor entry is the one that would be moved, don't
1889 * do it... it's too complicated.
1890 */
1891 lrecs = xfs_btree_get_numrecs(left);
1892 if (cur->bc_ptrs[level] >= lrecs)
1893 goto out0;
1894
1895 /* Set up the right neighbor as "right". */
1896 error = xfs_btree_read_buf_block(cur, &rptr, level, 0, &right, &rbp);
1897 if (error)
1898 goto error0;
1899
1900 /* If it's full, it can't take another entry. */
1901 rrecs = xfs_btree_get_numrecs(right);
1902 if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
1903 goto out0;
1904
1905 XFS_BTREE_STATS_INC(cur, rshift);
1906 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
1907
1908 /*
1909 * Make a hole at the start of the right neighbor block, then
1910 * copy the last left block entry to the hole.
1911 */
1912 if (level > 0) {
1913 /* It's a nonleaf. make a hole in the keys and ptrs */
1914 union xfs_btree_key *lkp;
1915 union xfs_btree_ptr *lpp;
1916 union xfs_btree_ptr *rpp;
1917
1918 lkp = xfs_btree_key_addr(cur, lrecs, left);
1919 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
1920 rkp = xfs_btree_key_addr(cur, 1, right);
1921 rpp = xfs_btree_ptr_addr(cur, 1, right);
1922
1923#ifdef DEBUG
1924 for (i = rrecs - 1; i >= 0; i--) {
1925 error = xfs_btree_check_ptr(cur, rpp, i, level);
1926 if (error)
1927 goto error0;
1928 }
1929#endif
1930
1931 xfs_btree_shift_keys(cur, rkp, 1, rrecs);
1932 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
1933
1934#ifdef DEBUG
1935 error = xfs_btree_check_ptr(cur, lpp, 0, level);
1936 if (error)
1937 goto error0;
1938#endif
1939
1940 /* Now put the new data in, and log it. */
1941 xfs_btree_copy_keys(cur, rkp, lkp, 1);
1942 xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
1943
1944 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
1945 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
1946
1947 xfs_btree_check_key(cur->bc_btnum, rkp,
1948 xfs_btree_key_addr(cur, 2, right));
1949 } else {
1950 /* It's a leaf. make a hole in the records */
1951 union xfs_btree_rec *lrp;
1952 union xfs_btree_rec *rrp;
1953
1954 lrp = xfs_btree_rec_addr(cur, lrecs, left);
1955 rrp = xfs_btree_rec_addr(cur, 1, right);
1956
1957 xfs_btree_shift_recs(cur, rrp, 1, rrecs);
1958
1959 /* Now put the new data in, and log it. */
1960 xfs_btree_copy_recs(cur, rrp, lrp, 1);
1961 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
1962
1963 cur->bc_ops->init_key_from_rec(&key, rrp);
1964 rkp = &key;
1965
1966 xfs_btree_check_rec(cur->bc_btnum, rrp,
1967 xfs_btree_rec_addr(cur, 2, right));
1968 }
1969
1970 /*
1971 * Decrement and log left's numrecs, bump and log right's numrecs.
1972 */
1973 xfs_btree_set_numrecs(left, --lrecs);
1974 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
1975
1976 xfs_btree_set_numrecs(right, ++rrecs);
1977 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
1978
1979 /*
1980 * Using a temporary cursor, update the parent key values of the
1981 * block on the right.
1982 */
1983 error = xfs_btree_dup_cursor(cur, &tcur);
1984 if (error)
1985 goto error0;
1986 i = xfs_btree_lastrec(tcur, level);
1987 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1988
1989 error = xfs_btree_increment(tcur, level, &i);
1990 if (error)
1991 goto error1;
1992
1993 error = xfs_btree_updkey(tcur, rkp, level + 1);
1994 if (error)
1995 goto error1;
1996
1997 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1998
1999 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2000 *stat = 1;
2001 return 0;
2002
2003out0:
2004 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2005 *stat = 0;
2006 return 0;
2007
2008error0:
2009 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2010 return error;
2011
2012error1:
2013 XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR);
2014 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2015 return error;
2016}
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index c3bfa5556c19..04311dbeff19 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -533,6 +533,7 @@ int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
533int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *); 533int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
534int xfs_btree_updkey(struct xfs_btree_cur *, union xfs_btree_key *, int); 534int xfs_btree_updkey(struct xfs_btree_cur *, union xfs_btree_key *, int);
535int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *); 535int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
536int xfs_btree_rshift(struct xfs_btree_cur *, int, int *);
536 537
537/* 538/*
538 * Helpers. 539 * Helpers.
@@ -542,6 +543,12 @@ static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
542 return be16_to_cpu(block->bb_numrecs); 543 return be16_to_cpu(block->bb_numrecs);
543} 544}
544 545
546static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
547 __uint16_t numrecs)
548{
549 block->bb_numrecs = cpu_to_be16(numrecs);
550}
551
545static inline int xfs_btree_get_level(struct xfs_btree_block *block) 552static inline int xfs_btree_get_level(struct xfs_btree_block *block)
546{ 553{
547 return be16_to_cpu(block->bb_level); 554 return be16_to_cpu(block->bb_level);
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index d080a6833a8d..457f88a76e10 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -45,7 +45,6 @@ STATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
45STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int); 45STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
46STATIC int xfs_inobt_lshift(xfs_btree_cur_t *, int, int *); 46STATIC int xfs_inobt_lshift(xfs_btree_cur_t *, int, int *);
47STATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *); 47STATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *);
48STATIC int xfs_inobt_rshift(xfs_btree_cur_t *, int, int *);
49STATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *, 48STATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
50 xfs_inobt_key_t *, xfs_btree_cur_t **, int *); 49 xfs_inobt_key_t *, xfs_btree_cur_t **, int *);
51 50
@@ -337,7 +336,7 @@ xfs_inobt_delrec(
337 */ 336 */
338 if (be16_to_cpu(left->bb_numrecs) - 1 >= 337 if (be16_to_cpu(left->bb_numrecs) - 1 >=
339 XFS_INOBT_BLOCK_MINRECS(level, cur)) { 338 XFS_INOBT_BLOCK_MINRECS(level, cur)) {
340 if ((error = xfs_inobt_rshift(tcur, level, &i))) 339 if ((error = xfs_btree_rshift(tcur, level, &i)))
341 goto error0; 340 goto error0;
342 if (i) { 341 if (i) {
343 ASSERT(be16_to_cpu(block->bb_numrecs) >= 342 ASSERT(be16_to_cpu(block->bb_numrecs) >=
@@ -608,7 +607,7 @@ xfs_inobt_insrec(
608 /* 607 /*
609 * First, try shifting an entry to the right neighbor. 608 * First, try shifting an entry to the right neighbor.
610 */ 609 */
611 if ((error = xfs_inobt_rshift(cur, level, &i))) 610 if ((error = xfs_btree_rshift(cur, level, &i)))
612 return error; 611 return error;
613 if (i) { 612 if (i) {
614 /* nothing */ 613 /* nothing */
@@ -1117,136 +1116,6 @@ xfs_inobt_newroot(
1117} 1116}
1118 1117
1119/* 1118/*
1120 * Move 1 record right from cur/level if possible.
1121 * Update cur to reflect the new path.
1122 */
1123STATIC int /* error */
1124xfs_inobt_rshift(
1125 xfs_btree_cur_t *cur, /* btree cursor */
1126 int level, /* level to shift record on */
1127 int *stat) /* success/failure */
1128{
1129 int error; /* error return value */
1130 int i; /* loop index */
1131 xfs_inobt_key_t key; /* key value for leaf level upward */
1132 xfs_buf_t *lbp; /* buffer for left (current) block */
1133 xfs_inobt_block_t *left; /* left (current) btree block */
1134 xfs_inobt_key_t *lkp; /* key pointer for left block */
1135 xfs_inobt_ptr_t *lpp; /* address pointer for left block */
1136 xfs_inobt_rec_t *lrp; /* record pointer for left block */
1137 xfs_buf_t *rbp; /* buffer for right neighbor block */
1138 xfs_inobt_block_t *right; /* right neighbor btree block */
1139 xfs_inobt_key_t *rkp; /* key pointer for right block */
1140 xfs_inobt_ptr_t *rpp; /* address pointer for right block */
1141 xfs_inobt_rec_t *rrp=NULL; /* record pointer for right block */
1142 xfs_btree_cur_t *tcur; /* temporary cursor */
1143
1144 /*
1145 * Set up variables for this block as "left".
1146 */
1147 lbp = cur->bc_bufs[level];
1148 left = XFS_BUF_TO_INOBT_BLOCK(lbp);
1149#ifdef DEBUG
1150 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1151 return error;
1152#endif
1153 /*
1154 * If we've got no right sibling then we can't shift an entry right.
1155 */
1156 if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
1157 *stat = 0;
1158 return 0;
1159 }
1160 /*
1161 * If the cursor entry is the one that would be moved, don't
1162 * do it... it's too complicated.
1163 */
1164 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
1165 *stat = 0;
1166 return 0;
1167 }
1168 /*
1169 * Set up the right neighbor as "right".
1170 */
1171 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1172 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
1173 0, &rbp, XFS_INO_BTREE_REF)))
1174 return error;
1175 right = XFS_BUF_TO_INOBT_BLOCK(rbp);
1176 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1177 return error;
1178 /*
1179 * If it's full, it can't take another entry.
1180 */
1181 if (be16_to_cpu(right->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
1182 *stat = 0;
1183 return 0;
1184 }
1185 /*
1186 * Make a hole at the start of the right neighbor block, then
1187 * copy the last left block entry to the hole.
1188 */
1189 if (level > 0) {
1190 lkp = XFS_INOBT_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1191 lpp = XFS_INOBT_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1192 rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
1193 rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
1194#ifdef DEBUG
1195 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1196 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
1197 return error;
1198 }
1199#endif
1200 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1201 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1202#ifdef DEBUG
1203 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
1204 return error;
1205#endif
1206 *rkp = *lkp;
1207 *rpp = *lpp;
1208 xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1209 xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1210 } else {
1211 lrp = XFS_INOBT_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1212 rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
1213 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1214 *rrp = *lrp;
1215 xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1216 key.ir_startino = rrp->ir_startino;
1217 rkp = &key;
1218 }
1219 /*
1220 * Decrement and log left's numrecs, bump and log right's numrecs.
1221 */
1222 be16_add_cpu(&left->bb_numrecs, -1);
1223 xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1224 be16_add_cpu(&right->bb_numrecs, 1);
1225#ifdef DEBUG
1226 if (level > 0)
1227 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
1228 else
1229 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
1230#endif
1231 xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1232 /*
1233 * Using a temporary cursor, update the parent key values of the
1234 * block on the right.
1235 */
1236 if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1237 return error;
1238 xfs_btree_lastrec(tcur, level);
1239 if ((error = xfs_btree_increment(tcur, level, &i)) ||
1240 (error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1))) {
1241 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1242 return error;
1243 }
1244 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1245 *stat = 1;
1246 return 0;
1247}
1248
1249/*
1250 * Split cur/level block in half. 1119 * Split cur/level block in half.
1251 * Return new block number and its first record (to be inserted into parent). 1120 * Return new block number and its first record (to be inserted into parent).
1252 */ 1121 */
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-16 13:53:18 -0500