git.sesse.net Git - bcachefs-tools-debian/blob - libbcache/dirent.c

   1
   2 #include "bcache.h"
   3 #include "bkey_methods.h"
   4 #include "btree_update.h"
   5 #include "extents.h"
   6 #include "dirent.h"
   7 #include "fs.h"
   8 #include "keylist.h"
   9 #include "str_hash.h"
  10
  11 #include <linux/dcache.h>
  12
  13 static unsigned dirent_name_bytes(struct bkey_s_c_dirent d)
  14 {
  15         unsigned len = bkey_val_bytes(d.k) - sizeof(struct bch_dirent);
  16
  17         while (len && !d.v->d_name[len - 1])
  18                 --len;
  19
  20         return len;
  21 }
  22
  23 static u64 bch_dirent_hash(const struct bch_hash_info *info,
  24                            const struct qstr *name)
  25 {
  26         switch (info->type) {
  27         case BCH_STR_HASH_SHA1: {
  28                 SHASH_DESC_ON_STACK(desc, bch_sha1);
  29                 u8 digest[SHA1_DIGEST_SIZE];
  30                 u64 ret;
  31                 desc->tfm = bch_sha1;
  32                 desc->flags = 0;
  33                 crypto_shash_init(desc);
  34
  35                 crypto_shash_update(desc, (void *) &info->seed, sizeof(info->seed));
  36
  37                 crypto_shash_update(desc, (void *) name->name, name->len);
  38                 crypto_shash_final(desc, digest);
  39                 memcpy(&ret, &digest, sizeof(ret));
  40                 return max_t(u64, ret >> 1, 2);
  41         }
  42         default: {
  43                 struct bch_str_hash_ctx ctx;
  44
  45                 bch_str_hash_init(&ctx, info->type);
  46                 bch_str_hash_update(&ctx, info->type, &info->seed, sizeof(info->seed));
  47
  48                 bch_str_hash_update(&ctx, info->type, name->name, name->len);
  49
  50                 /* [0,2) reserved for dots */
  51                 return max_t(u64, bch_str_hash_end(&ctx, info->type), 2);
  52         }
  53         }
  54 }
  55
  56 static u64 dirent_hash_key(const struct bch_hash_info *info, const void *key)
  57 {
  58         return bch_dirent_hash(info, key);
  59 }
  60
  61 static u64 dirent_hash_bkey(const struct bch_hash_info *info, struct bkey_s_c k)
  62 {
  63         struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);
  64         struct qstr name = QSTR_INIT(d.v->d_name, dirent_name_bytes(d));
  65
  66         return bch_dirent_hash(info, &name);
  67 }
  68
  69 static bool dirent_cmp_key(struct bkey_s_c _l, const void *_r)
  70 {
  71         struct bkey_s_c_dirent l = bkey_s_c_to_dirent(_l);
  72         int len = dirent_name_bytes(l);
  73         const struct qstr *r = _r;
  74
  75         return len - r->len ?: memcmp(l.v->d_name, r->name, len);
  76 }
  77
  78 static bool dirent_cmp_bkey(struct bkey_s_c _l, struct bkey_s_c _r)
  79 {
  80         struct bkey_s_c_dirent l = bkey_s_c_to_dirent(_l);
  81         struct bkey_s_c_dirent r = bkey_s_c_to_dirent(_r);
  82         int l_len = dirent_name_bytes(l);
  83         int r_len = dirent_name_bytes(r);
  84
  85         return l_len - r_len ?: memcmp(l.v->d_name, r.v->d_name, l_len);
  86 }
  87
  88 static const struct bch_hash_desc dirent_hash_desc = {
  89         .btree_id       = BTREE_ID_DIRENTS,
  90         .key_type       = BCH_DIRENT,
  91         .whiteout_type  = BCH_DIRENT_WHITEOUT,
  92         .hash_key       = dirent_hash_key,
  93         .hash_bkey      = dirent_hash_bkey,
  94         .cmp_key        = dirent_cmp_key,
  95         .cmp_bkey       = dirent_cmp_bkey,
  96 };
  97
  98 static const char *bch_dirent_invalid(const struct cache_set *c,
  99                                       struct bkey_s_c k)
 100 {
 101         switch (k.k->type) {
 102         case BCH_DIRENT:
 103                 return bkey_val_bytes(k.k) < sizeof(struct bch_dirent)
 104                         ? "value too small"
 105                         : NULL;
 106
 107         case BCH_DIRENT_WHITEOUT:
 108                 return bkey_val_bytes(k.k) != 0
 109                         ? "value size should be zero"
 110                         : NULL;
 111
 112         default:
 113                 return "invalid type";
 114         }
 115 }
 116
 117 static void bch_dirent_to_text(struct cache_set *c, char *buf,
 118                                size_t size, struct bkey_s_c k)
 119 {
 120         struct bkey_s_c_dirent d;
 121
 122         switch (k.k->type) {
 123         case BCH_DIRENT:
 124                 d = bkey_s_c_to_dirent(k);
 125
 126                 if (size) {
 127                         unsigned n = min_t(unsigned, size,
 128                                            dirent_name_bytes(d));
 129                         memcpy(buf, d.v->d_name, n);
 130                         buf[size - 1] = '\0';
 131                         buf += n;
 132                         size -= n;
 133                 }
 134
 135                 scnprintf(buf, size, " -> %llu", d.v->d_inum);
 136                 break;
 137         case BCH_DIRENT_WHITEOUT:
 138                 scnprintf(buf, size, "whiteout");
 139                 break;
 140         }
 141 }
 142
 143 const struct bkey_ops bch_bkey_dirent_ops = {
 144         .key_invalid    = bch_dirent_invalid,
 145         .val_to_text    = bch_dirent_to_text,
 146 };
 147
 148 static struct bkey_i_dirent *dirent_create_key(u8 type,
 149                                 const struct qstr *name, u64 dst)
 150 {
 151         struct bkey_i_dirent *dirent;
 152         unsigned u64s = BKEY_U64s +
 153                 DIV_ROUND_UP(sizeof(struct bch_dirent) + name->len,
 154                              sizeof(u64));
 155
 156         dirent = kmalloc(u64s * sizeof(u64), GFP_NOFS);
 157         if (!dirent)
 158                 return NULL;
 159
 160         bkey_dirent_init(&dirent->k_i);
 161         dirent->k.u64s = u64s;
 162         dirent->v.d_inum = cpu_to_le64(dst);
 163         dirent->v.d_type = type;
 164
 165         memcpy(dirent->v.d_name, name->name, name->len);
 166         memset(dirent->v.d_name + name->len, 0,
 167                bkey_val_bytes(&dirent->k) -
 168                (sizeof(struct bch_dirent) + name->len));
 169
 170         EBUG_ON(dirent_name_bytes(dirent_i_to_s_c(dirent)) != name->len);
 171
 172         return dirent;
 173 }
 174
 175 int bch_dirent_create(struct cache_set *c, struct inode *dir, u8 type,
 176                       const struct qstr *name, u64 dst_inum)
 177 {
 178         struct bch_inode_info *ei = to_bch_ei(dir);
 179         struct bkey_i_dirent *dirent;
 180         int ret;
 181
 182         dirent = dirent_create_key(type, name, dst_inum);
 183         if (!dirent)
 184                 return -ENOMEM;
 185
 186         ret = bch_hash_set(dirent_hash_desc, &ei->str_hash, c,
 187                            ei->vfs_inode.i_ino, &ei->journal_seq,
 188                            &dirent->k_i, BCH_HASH_SET_MUST_CREATE);
 189         kfree(dirent);
 190
 191         return ret;
 192 }
 193
 194 static void dirent_copy_target(struct bkey_i_dirent *dst,
 195                                struct bkey_s_c_dirent src)
 196 {
 197         dst->v.d_inum = src.v->d_inum;
 198         dst->v.d_type = src.v->d_type;
 199 }
 200
 201 static struct bpos bch_dirent_pos(struct bch_inode_info *ei,
 202                                   const struct qstr *name)
 203 {
 204         return POS(ei->vfs_inode.i_ino, bch_dirent_hash(&ei->str_hash, name));
 205 }
 206
 207 int bch_dirent_rename(struct cache_set *c,
 208                       struct inode *src_dir, const struct qstr *src_name,
 209                       struct inode *dst_dir, const struct qstr *dst_name,
 210                       u64 *journal_seq, enum bch_rename_mode mode)
 211 {
 212         struct bch_inode_info *src_ei = to_bch_ei(src_dir);
 213         struct bch_inode_info *dst_ei = to_bch_ei(dst_dir);
 214         struct btree_iter src_iter, dst_iter, whiteout_iter;
 215         struct bkey_s_c old_src, old_dst;
 216         struct bkey delete;
 217         struct bkey_i_dirent *new_src = NULL, *new_dst = NULL;
 218         struct bpos src_pos = bch_dirent_pos(src_ei, src_name);
 219         struct bpos dst_pos = bch_dirent_pos(dst_ei, dst_name);
 220         bool need_whiteout;
 221         int ret = -ENOMEM;
 222
 223         bch_btree_iter_init_intent(&src_iter, c, BTREE_ID_DIRENTS, src_pos);
 224         bch_btree_iter_init_intent(&dst_iter, c, BTREE_ID_DIRENTS, dst_pos);
 225         bch_btree_iter_link(&src_iter, &dst_iter);
 226
 227         bch_btree_iter_init(&whiteout_iter, c, BTREE_ID_DIRENTS, src_pos);
 228         bch_btree_iter_link(&src_iter, &whiteout_iter);
 229
 230         if (mode == BCH_RENAME_EXCHANGE) {
 231                 new_src = dirent_create_key(0, src_name, 0);
 232                 if (!new_src)
 233                         goto err;
 234         } else {
 235                 new_src = (void *) &delete;
 236         }
 237
 238         new_dst = dirent_create_key(0, dst_name, 0);
 239         if (!new_dst)
 240                 goto err;
 241 retry:
 242         /*
 243          * Note that on -EINTR/dropped locks we're not restarting the lookup
 244          * from the original hashed position (like we do when creating dirents,
 245          * in bch_hash_set) -  we never move existing dirents to different slot:
 246          */
 247         old_src = bch_hash_lookup_at(dirent_hash_desc,
 248                                      &src_ei->str_hash,
 249                                      &src_iter, src_name);
 250         if ((ret = btree_iter_err(old_src)))
 251                 goto err;
 252
 253         ret = bch_hash_needs_whiteout(dirent_hash_desc,
 254                                 &src_ei->str_hash,
 255                                 &whiteout_iter, &src_iter);
 256         if (ret < 0)
 257                 goto err;
 258         need_whiteout = ret;
 259
 260         /*
 261          * Note that in BCH_RENAME mode, we're _not_ checking if
 262          * the target already exists - we're relying on the VFS
 263          * to do that check for us for correctness:
 264          */
 265         old_dst = mode == BCH_RENAME
 266                 ? bch_hash_hole_at(dirent_hash_desc, &dst_iter)
 267                 : bch_hash_lookup_at(dirent_hash_desc,
 268                                      &dst_ei->str_hash,
 269                                      &dst_iter, dst_name);
 270         if ((ret = btree_iter_err(old_dst)))
 271                 goto err;
 272
 273         switch (mode) {
 274         case BCH_RENAME:
 275                 bkey_init(&new_src->k);
 276                 dirent_copy_target(new_dst, bkey_s_c_to_dirent(old_src));
 277
 278                 if (bkey_cmp(dst_pos, src_iter.pos) <= 0 &&
 279                     bkey_cmp(src_iter.pos, dst_iter.pos) < 0) {
 280                         /*
 281                          * If we couldn't insert new_dst at its hashed
 282                          * position (dst_pos) due to a hash collision,
 283                          * and we're going to be deleting in
 284                          * between the hashed position and first empty
 285                          * slot we found - just overwrite the pos we
 286                          * were going to delete:
 287                          *
 288                          * Note: this is a correctness issue, in this
 289                          * situation bch_hash_needs_whiteout() could
 290                          * return false when the whiteout would have
 291                          * been needed if we inserted at the pos
 292                          * __dirent_find_hole() found
 293                          */
 294                         new_dst->k.p = src_iter.pos;
 295                         ret = bch_btree_insert_at(c, NULL, NULL,
 296                                         journal_seq,
 297                                         BTREE_INSERT_ATOMIC,
 298                                         BTREE_INSERT_ENTRY(&src_iter,
 299                                                            &new_dst->k_i));
 300                         goto err;
 301                 }
 302
 303                 if (need_whiteout)
 304                         new_src->k.type = BCH_DIRENT_WHITEOUT;
 305                 break;
 306         case BCH_RENAME_OVERWRITE:
 307                 bkey_init(&new_src->k);
 308                 dirent_copy_target(new_dst, bkey_s_c_to_dirent(old_src));
 309
 310                 if (bkey_cmp(dst_pos, src_iter.pos) <= 0 &&
 311                     bkey_cmp(src_iter.pos, dst_iter.pos) < 0) {
 312                         /*
 313                          * Same case described above -
 314                          * bch_hash_needs_whiteout could spuriously
 315                          * return false, but we have to insert at
 316                          * dst_iter.pos because we're overwriting
 317                          * another dirent:
 318                          */
 319                         new_src->k.type = BCH_DIRENT_WHITEOUT;
 320                 } else if (need_whiteout)
 321                         new_src->k.type = BCH_DIRENT_WHITEOUT;
 322                 break;
 323         case BCH_RENAME_EXCHANGE:
 324                 dirent_copy_target(new_src, bkey_s_c_to_dirent(old_dst));
 325                 dirent_copy_target(new_dst, bkey_s_c_to_dirent(old_src));
 326                 break;
 327         }
 328
 329         new_src->k.p = src_iter.pos;
 330         new_dst->k.p = dst_iter.pos;
 331         ret = bch_btree_insert_at(c, NULL, NULL, journal_seq,
 332                         BTREE_INSERT_ATOMIC,
 333                         BTREE_INSERT_ENTRY(&src_iter, &new_src->k_i),
 334                         BTREE_INSERT_ENTRY(&dst_iter, &new_dst->k_i));
 335 err:
 336         if (ret == -EINTR)
 337                 goto retry;
 338
 339         bch_btree_iter_unlock(&whiteout_iter);
 340         bch_btree_iter_unlock(&dst_iter);
 341         bch_btree_iter_unlock(&src_iter);
 342
 343         if (new_src != (void *) &delete)
 344                 kfree(new_src);
 345         kfree(new_dst);
 346         return ret;
 347 }
 348
 349 int bch_dirent_delete(struct cache_set *c, struct inode *dir,
 350                       const struct qstr *name)
 351 {
 352         struct bch_inode_info *ei = to_bch_ei(dir);
 353
 354         return bch_hash_delete(dirent_hash_desc, &ei->str_hash,
 355                                c, ei->vfs_inode.i_ino,
 356                                &ei->journal_seq, name);
 357 }
 358
 359 u64 bch_dirent_lookup(struct cache_set *c, struct inode *dir,
 360                       const struct qstr *name)
 361 {
 362         struct bch_inode_info *ei = to_bch_ei(dir);
 363         struct btree_iter iter;
 364         struct bkey_s_c k;
 365         u64 inum;
 366
 367         k = bch_hash_lookup(dirent_hash_desc, &ei->str_hash, c,
 368                             ei->vfs_inode.i_ino, &iter, name);
 369         if (IS_ERR(k.k)) {
 370                 bch_btree_iter_unlock(&iter);
 371                 return 0;
 372         }
 373
 374         inum = le64_to_cpu(bkey_s_c_to_dirent(k).v->d_inum);
 375         bch_btree_iter_unlock(&iter);
 376
 377         return inum;
 378 }
 379
 380 int bch_empty_dir(struct cache_set *c, u64 dir_inum)
 381 {
 382         struct btree_iter iter;
 383         struct bkey_s_c k;
 384         int ret = 0;
 385
 386         for_each_btree_key(&iter, c, BTREE_ID_DIRENTS, POS(dir_inum, 0), k) {
 387                 if (k.k->p.inode > dir_inum)
 388                         break;
 389
 390                 if (k.k->type == BCH_DIRENT) {
 391                         ret = -ENOTEMPTY;
 392                         break;
 393                 }
 394         }
 395         bch_btree_iter_unlock(&iter);
 396
 397         return ret;
 398 }
 399
 400 int bch_readdir(struct cache_set *c, struct file *file,
 401                 struct dir_context *ctx)
 402 {
 403         struct inode *inode = file_inode(file);
 404         struct btree_iter iter;
 405         struct bkey_s_c k;
 406         struct bkey_s_c_dirent dirent;
 407         unsigned len;
 408
 409         if (!dir_emit_dots(file, ctx))
 410                 return 0;
 411
 412         pr_debug("listing for %lu from %llu", inode->i_ino, ctx->pos);
 413
 414         for_each_btree_key(&iter, c, BTREE_ID_DIRENTS,
 415                            POS(inode->i_ino, ctx->pos), k) {
 416                 if (k.k->type != BCH_DIRENT)
 417                         continue;
 418
 419                 dirent = bkey_s_c_to_dirent(k);
 420
 421                 pr_debug("saw %llu:%llu (%s) -> %llu",
 422                          k.k->p.inode, k.k->p.offset,
 423                          dirent.v->d_name, dirent.v->d_inum);
 424
 425                 if (bkey_cmp(k.k->p, POS(inode->i_ino, ctx->pos)) < 0)
 426                         continue;
 427
 428                 if (k.k->p.inode > inode->i_ino)
 429                         break;
 430
 431                 len = dirent_name_bytes(dirent);
 432
 433                 pr_debug("emitting %s", dirent.v->d_name);
 434
 435                 /*
 436                  * XXX: dir_emit() can fault and block, while we're holding
 437                  * locks
 438                  */
 439                 if (!dir_emit(ctx, dirent.v->d_name, len,
 440                               le64_to_cpu(dirent.v->d_inum),
 441                               dirent.v->d_type))
 442                         break;
 443
 444                 ctx->pos = k.k->p.offset + 1;
 445         }
 446         bch_btree_iter_unlock(&iter);
 447
 448         return 0;
 449 }