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