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

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