fs/bcachefs/str_hash.c

   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 noinline 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 noinline 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 noinline 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 }