1 // SPDX-License-Identifier: GPL-2.0 2 3 #include "bcachefs.h" 4 #include "btree_cache.h" 5 #include "btree_update.h" 6 #include "dirent.h" 7 #include "fsck.h" 8 #include "str_hash.h" 9 #include "subvolume.h" 10 11 static int bch2_dirent_has_target(struct btree_trans *trans, struct bkey_s_c_dirent d) 12 { 13 if (d.v->d_type == DT_SUBVOL) { 14 struct bch_subvolume subvol; 15 int ret = bch2_subvolume_get(trans, le32_to_cpu(d.v->d_child_subvol), 16 false, &subvol); 17 if (ret && !bch2_err_matches(ret, ENOENT)) 18 return ret; 19 return !ret; 20 } else { 21 struct btree_iter iter; 22 struct bkey_s_c k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes, 23 SPOS(0, le64_to_cpu(d.v->d_inum), d.k->p.snapshot), 0); 24 int ret = bkey_err(k); 25 if (ret) 26 return ret; 27 28 ret = bkey_is_inode(k.k); 29 bch2_trans_iter_exit(trans, &iter); 30 return ret; 31 } 32 } 33 34 static int fsck_rename_dirent(struct btree_trans *trans, 35 struct snapshots_seen *s, 36 const struct bch_hash_desc desc, 37 struct bch_hash_info *hash_info, 38 struct bkey_s_c_dirent old) 39 { 40 struct qstr old_name = bch2_dirent_get_name(old); 41 struct bkey_i_dirent *new = bch2_trans_kmalloc(trans, bkey_bytes(old.k) + 32); 42 int ret = PTR_ERR_OR_ZERO(new); 43 if (ret) 44 return ret; 45 46 bkey_dirent_init(&new->k_i); 47 dirent_copy_target(new, old); 48 new->k.p = old.k->p; 49 50 for (unsigned i = 0; i < 1000; i++) { 51 unsigned len = sprintf(new->v.d_name, "%.*s.fsck_renamed-%u", 52 old_name.len, old_name.name, i); 53 unsigned u64s = BKEY_U64s + dirent_val_u64s(len); 54 55 if (u64s > U8_MAX) 56 return -EINVAL; 57 58 new->k.u64s = u64s; 59 60 ret = bch2_hash_set_in_snapshot(trans, bch2_dirent_hash_desc, hash_info, 61 (subvol_inum) { 0, old.k->p.inode }, 62 old.k->p.snapshot, &new->k_i, 63 BTREE_UPDATE_internal_snapshot_node); 64 if (!bch2_err_matches(ret, EEXIST)) 65 break; 66 } 67 68 if (ret) 69 return ret; 70 71 return bch2_fsck_update_backpointers(trans, s, desc, hash_info, &new->k_i); 72 } 73 74 static int hash_pick_winner(struct btree_trans *trans, 75 const struct bch_hash_desc desc, 76 struct bch_hash_info *hash_info, 77 struct bkey_s_c k1, 78 struct bkey_s_c k2) 79 { 80 if (bkey_val_bytes(k1.k) == bkey_val_bytes(k2.k) && 81 !memcmp(k1.v, k2.v, bkey_val_bytes(k1.k))) 82 return 0; 83 84 switch (desc.btree_id) { 85 case BTREE_ID_dirents: { 86 int ret = bch2_dirent_has_target(trans, bkey_s_c_to_dirent(k1)); 87 if (ret < 0) 88 return ret; 89 if (!ret) 90 return 0; 91 92 ret = bch2_dirent_has_target(trans, bkey_s_c_to_dirent(k2)); 93 if (ret < 0) 94 return ret; 95 if (!ret) 96 return 1; 97 return 2; 98 } 99 default: 100 return 0; 101 } 102 } 103 104 static int repair_inode_hash_info(struct btree_trans *trans, 105 struct bch_inode_unpacked *snapshot_root) 106 { 107 struct btree_iter iter; 108 struct bkey_s_c k; 109 int ret = 0; 110 111 for_each_btree_key_reverse_norestart(trans, iter, BTREE_ID_inodes, 112 SPOS(0, snapshot_root->bi_inum, snapshot_root->bi_snapshot - 1), 113 BTREE_ITER_all_snapshots, k, ret) { 114 if (k.k->p.offset != snapshot_root->bi_inum) 115 break; 116 if (!bkey_is_inode(k.k)) 117 continue; 118 119 struct bch_inode_unpacked inode; 120 ret = bch2_inode_unpack(k, &inode); 121 if (ret) 122 break; 123 124 if (fsck_err_on(inode.bi_hash_seed != snapshot_root->bi_hash_seed || 125 INODE_STR_HASH(&inode) != INODE_STR_HASH(snapshot_root), 126 trans, inode_snapshot_mismatch, 127 "inode hash info in different snapshots don't match")) { 128 inode.bi_hash_seed = snapshot_root->bi_hash_seed; 129 SET_INODE_STR_HASH(&inode, INODE_STR_HASH(snapshot_root)); 130 ret = __bch2_fsck_write_inode(trans, &inode) ?: 131 bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc) ?: 132 -BCH_ERR_transaction_restart_nested; 133 break; 134 } 135 } 136 fsck_err: 137 bch2_trans_iter_exit(trans, &iter); 138 return ret; 139 } 140 141 /* 142 * All versions of the same inode in different snapshots must have the same hash 143 * seed/type: verify that the hash info we're using matches the root 144 */ 145 static int check_inode_hash_info_matches_root(struct btree_trans *trans, u64 inum, 146 struct bch_hash_info *hash_info) 147 { 148 struct bch_fs *c = trans->c; 149 struct btree_iter iter; 150 struct bkey_s_c k; 151 int ret = 0; 152 153 for_each_btree_key_reverse_norestart(trans, iter, BTREE_ID_inodes, SPOS(0, inum, U32_MAX), 154 BTREE_ITER_all_snapshots, k, ret) { 155 if (k.k->p.offset != inum) 156 break; 157 if (bkey_is_inode(k.k)) 158 goto found; 159 } 160 bch_err(c, "%s(): inum %llu not found", __func__, inum); 161 ret = -BCH_ERR_fsck_repair_unimplemented; 162 goto err; 163 found:; 164 struct bch_inode_unpacked inode; 165 ret = bch2_inode_unpack(k, &inode); 166 if (ret) 167 goto err; 168 169 struct bch_hash_info hash2 = bch2_hash_info_init(c, &inode); 170 if (hash_info->type != hash2.type || 171 memcmp(&hash_info->siphash_key, &hash2.siphash_key, sizeof(hash2.siphash_key))) { 172 ret = repair_inode_hash_info(trans, &inode); 173 if (!ret) { 174 bch_err(c, "inode hash info mismatch with root, but mismatch not found\n" 175 "%u %llx %llx\n" 176 "%u %llx %llx", 177 hash_info->type, 178 hash_info->siphash_key.k0, 179 hash_info->siphash_key.k1, 180 hash2.type, 181 hash2.siphash_key.k0, 182 hash2.siphash_key.k1); 183 ret = -BCH_ERR_fsck_repair_unimplemented; 184 } 185 } 186 err: 187 bch2_trans_iter_exit(trans, &iter); 188 return ret; 189 } 190 191 int __bch2_str_hash_check_key(struct btree_trans *trans, 192 struct snapshots_seen *s, 193 const struct bch_hash_desc *desc, 194 struct bch_hash_info *hash_info, 195 struct btree_iter *k_iter, struct bkey_s_c hash_k) 196 { 197 struct bch_fs *c = trans->c; 198 struct btree_iter iter = { NULL }; 199 struct printbuf buf = PRINTBUF; 200 struct bkey_s_c k; 201 int ret = 0; 202 203 u64 hash = desc->hash_bkey(hash_info, hash_k); 204 if (hash_k.k->p.offset < hash) 205 goto bad_hash; 206 207 for_each_btree_key_norestart(trans, iter, desc->btree_id, 208 SPOS(hash_k.k->p.inode, hash, hash_k.k->p.snapshot), 209 BTREE_ITER_slots, k, ret) { 210 if (bkey_eq(k.k->p, hash_k.k->p)) 211 break; 212 213 if (k.k->type == desc->key_type && 214 !desc->cmp_bkey(k, hash_k)) 215 goto duplicate_entries; 216 217 if (bkey_deleted(k.k)) { 218 bch2_trans_iter_exit(trans, &iter); 219 goto bad_hash; 220 } 221 } 222 out: 223 bch2_trans_iter_exit(trans, &iter); 224 printbuf_exit(&buf); 225 return ret; 226 bad_hash: 227 /* 228 * Before doing any repair, check hash_info itself: 229 */ 230 ret = check_inode_hash_info_matches_root(trans, hash_k.k->p.inode, hash_info); 231 if (ret) 232 goto out; 233 234 if (fsck_err(trans, hash_table_key_wrong_offset, 235 "hash table key at wrong offset: btree %s inode %llu offset %llu, hashed to %llu\n %s", 236 bch2_btree_id_str(desc->btree_id), hash_k.k->p.inode, hash_k.k->p.offset, hash, 237 (printbuf_reset(&buf), 238 bch2_bkey_val_to_text(&buf, c, hash_k), buf.buf))) { 239 struct bkey_i *new = bch2_bkey_make_mut_noupdate(trans, hash_k); 240 if (IS_ERR(new)) 241 return PTR_ERR(new); 242 243 k = bch2_hash_set_or_get_in_snapshot(trans, &iter, *desc, hash_info, 244 (subvol_inum) { 0, hash_k.k->p.inode }, 245 hash_k.k->p.snapshot, new, 246 STR_HASH_must_create| 247 BTREE_ITER_with_updates| 248 BTREE_UPDATE_internal_snapshot_node); 249 ret = bkey_err(k); 250 if (ret) 251 goto out; 252 if (k.k) 253 goto duplicate_entries; 254 255 ret = bch2_hash_delete_at(trans, *desc, hash_info, k_iter, 256 BTREE_UPDATE_internal_snapshot_node) ?: 257 bch2_fsck_update_backpointers(trans, s, *desc, hash_info, new) ?: 258 bch2_trans_commit(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc) ?: 259 -BCH_ERR_transaction_restart_nested; 260 goto out; 261 } 262 fsck_err: 263 goto out; 264 duplicate_entries: 265 ret = hash_pick_winner(trans, *desc, hash_info, hash_k, k); 266 if (ret < 0) 267 goto out; 268 269 if (!fsck_err(trans, hash_table_key_duplicate, 270 "duplicate hash table keys%s:\n%s", 271 ret != 2 ? "" : ", both point to valid inodes", 272 (printbuf_reset(&buf), 273 bch2_bkey_val_to_text(&buf, c, hash_k), 274 prt_newline(&buf), 275 bch2_bkey_val_to_text(&buf, c, k), 276 buf.buf))) 277 goto out; 278 279 switch (ret) { 280 case 0: 281 ret = bch2_hash_delete_at(trans, *desc, hash_info, k_iter, 0); 282 break; 283 case 1: 284 ret = bch2_hash_delete_at(trans, *desc, hash_info, &iter, 0); 285 break; 286 case 2: 287 ret = fsck_rename_dirent(trans, s, *desc, hash_info, bkey_s_c_to_dirent(hash_k)) ?: 288 bch2_hash_delete_at(trans, *desc, hash_info, k_iter, 0); 289 goto out; 290 } 291 292 ret = bch2_trans_commit(trans, NULL, NULL, 0) ?: 293 -BCH_ERR_transaction_restart_nested; 294 goto out; 295 } 296