fs/afs/dir_edit.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* AFS filesystem directory editing
   3  *
   4  * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
   5  * Written by David Howells (dhowells@redhat.com)
   6  */
   7
   8 #include <linux/kernel.h>
   9 #include <linux/fs.h>
  10 #include <linux/namei.h>
  11 #include <linux/pagemap.h>
  12 #include <linux/iversion.h>
  13 #include "internal.h"
  14 #include "xdr_fs.h"
  15
  16 /*
  17  * Find a number of contiguous clear bits in a directory block bitmask.
  18  *
  19  * There are 64 slots, which means we can load the entire bitmap into a
  20  * variable.  The first bit doesn't count as it corresponds to the block header
  21  * slot.  nr_slots is between 1 and 9.
  22  */
  23 static int afs_find_contig_bits(union afs_xdr_dir_block *block, unsigned int nr_slots)
  24 {
  25         u64 bitmap;
  26         u32 mask;
  27         int bit, n;
  28
  29         bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
  30         bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
  31         bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
  32         bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
  33         bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
  34         bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
  35         bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
  36         bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
  37         bitmap >>= 1; /* The first entry is metadata */
  38         bit = 1;
  39         mask = (1 << nr_slots) - 1;
  40
  41         do {
  42                 if (sizeof(unsigned long) == 8)
  43                         n = ffz(bitmap);
  44                 else
  45                         n = ((u32)bitmap) != 0 ?
  46                                 ffz((u32)bitmap) :
  47                                 ffz((u32)(bitmap >> 32)) + 32;
  48                 bitmap >>= n;
  49                 bit += n;
  50
  51                 if ((bitmap & mask) == 0) {
  52                         if (bit > 64 - nr_slots)
  53                                 return -1;
  54                         return bit;
  55                 }
  56
  57                 n = __ffs(bitmap);
  58                 bitmap >>= n;
  59                 bit += n;
  60         } while (bitmap);
  61
  62         return -1;
  63 }
  64
  65 /*
  66  * Set a number of contiguous bits in the directory block bitmap.
  67  */
  68 static void afs_set_contig_bits(union afs_xdr_dir_block *block,
  69                                 int bit, unsigned int nr_slots)
  70 {
  71         u64 mask;
  72
  73         mask = (1 << nr_slots) - 1;
  74         mask <<= bit;
  75
  76         block->hdr.bitmap[0] |= (u8)(mask >> 0 * 8);
  77         block->hdr.bitmap[1] |= (u8)(mask >> 1 * 8);
  78         block->hdr.bitmap[2] |= (u8)(mask >> 2 * 8);
  79         block->hdr.bitmap[3] |= (u8)(mask >> 3 * 8);
  80         block->hdr.bitmap[4] |= (u8)(mask >> 4 * 8);
  81         block->hdr.bitmap[5] |= (u8)(mask >> 5 * 8);
  82         block->hdr.bitmap[6] |= (u8)(mask >> 6 * 8);
  83         block->hdr.bitmap[7] |= (u8)(mask >> 7 * 8);
  84 }
  85
  86 /*
  87  * Clear a number of contiguous bits in the directory block bitmap.
  88  */
  89 static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
  90                                   int bit, unsigned int nr_slots)
  91 {
  92         u64 mask;
  93
  94         mask = (1 << nr_slots) - 1;
  95         mask <<= bit;
  96
  97         block->hdr.bitmap[0] &= ~(u8)(mask >> 0 * 8);
  98         block->hdr.bitmap[1] &= ~(u8)(mask >> 1 * 8);
  99         block->hdr.bitmap[2] &= ~(u8)(mask >> 2 * 8);
 100         block->hdr.bitmap[3] &= ~(u8)(mask >> 3 * 8);
 101         block->hdr.bitmap[4] &= ~(u8)(mask >> 4 * 8);
 102         block->hdr.bitmap[5] &= ~(u8)(mask >> 5 * 8);
 103         block->hdr.bitmap[6] &= ~(u8)(mask >> 6 * 8);
 104         block->hdr.bitmap[7] &= ~(u8)(mask >> 7 * 8);
 105 }
 106
 107 /*
 108  * Scan a directory block looking for a dirent of the right name.
 109  */
 110 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
 111                               unsigned int blocknum)
 112 {
 113         union afs_xdr_dirent *de;
 114         u64 bitmap;
 115         int d, len, n;
 116
 117         _enter("");
 118
 119         bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
 120         bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
 121         bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
 122         bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
 123         bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
 124         bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
 125         bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
 126         bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
 127
 128         for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
 129              d < AFS_DIR_SLOTS_PER_BLOCK;
 130              d++) {
 131                 if (!((bitmap >> d) & 1))
 132                         continue;
 133                 de = &block->dirents[d];
 134                 if (de->u.valid != 1)
 135                         continue;
 136
 137                 /* The block was NUL-terminated by afs_dir_check_page(). */
 138                 len = strlen(de->u.name);
 139                 if (len == name->len &&
 140                     memcmp(de->u.name, name->name, name->len) == 0)
 141                         return d;
 142
 143                 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 144                 n /= AFS_DIR_DIRENT_SIZE;
 145                 d += n - 1;
 146         }
 147
 148         return -1;
 149 }
 150
 151 /*
 152  * Initialise a new directory block.  Note that block 0 is special and contains
 153  * some extra metadata.
 154  */
 155 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
 156                                 union afs_xdr_dir_block *block, int block_num)
 157 {
 158         memset(block, 0, sizeof(*block));
 159         block->hdr.npages = htons(1);
 160         block->hdr.magic = AFS_DIR_MAGIC;
 161         block->hdr.bitmap[0] = 1;
 162
 163         if (block_num == 0) {
 164                 block->hdr.bitmap[0] = 0xff;
 165                 block->hdr.bitmap[1] = 0x1f;
 166                 memset(block->meta.alloc_ctrs,
 167                        AFS_DIR_SLOTS_PER_BLOCK,
 168                        sizeof(block->meta.alloc_ctrs));
 169                 meta->meta.alloc_ctrs[0] =
 170                         AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
 171         }
 172
 173         if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
 174                 meta->meta.alloc_ctrs[block_num] =
 175                         AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
 176 }
 177
 178 /*
 179  * Edit a directory's file data to add a new directory entry.  Doing this after
 180  * create, mkdir, symlink, link or rename if the data version number is
 181  * incremented by exactly one avoids the need to re-download the entire
 182  * directory contents.
 183  *
 184  * The caller must hold the inode locked.
 185  */
 186 void afs_edit_dir_add(struct afs_vnode *vnode,
 187                       struct qstr *name, struct afs_fid *new_fid,
 188                       enum afs_edit_dir_reason why)
 189 {
 190         union afs_xdr_dir_block *meta, *block;
 191         struct afs_xdr_dir_page *meta_page, *dir_page;
 192         union afs_xdr_dirent *de;
 193         struct page *page0, *page;
 194         unsigned int need_slots, nr_blocks, b;
 195         pgoff_t index;
 196         loff_t i_size;
 197         gfp_t gfp;
 198         int slot;
 199
 200         _enter(",,{%d,%s},", name->len, name->name);
 201
 202         i_size = i_size_read(&vnode->vfs_inode);
 203         if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
 204             (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
 205                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 206                 return;
 207         }
 208
 209         gfp = vnode->vfs_inode.i_mapping->gfp_mask;
 210         page0 = find_or_create_page(vnode->vfs_inode.i_mapping, 0, gfp);
 211         if (!page0) {
 212                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 213                 _leave(" [fgp]");
 214                 return;
 215         }
 216
 217         /* Work out how many slots we're going to need. */
 218         need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 219         need_slots /= AFS_DIR_DIRENT_SIZE;
 220
 221         meta_page = kmap(page0);
 222         meta = &meta_page->blocks[0];
 223         if (i_size == 0)
 224                 goto new_directory;
 225         nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
 226
 227         /* Find a block that has sufficient slots available.  Each VM page
 228          * contains two or more directory blocks.
 229          */
 230         for (b = 0; b < nr_blocks + 1; b++) {
 231                 /* If the directory extended into a new page, then we need to
 232                  * tack a new page on the end.
 233                  */
 234                 index = b / AFS_DIR_BLOCKS_PER_PAGE;
 235                 if (index == 0) {
 236                         page = page0;
 237                         dir_page = meta_page;
 238                 } else {
 239                         if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
 240                                 goto error;
 241                         gfp = vnode->vfs_inode.i_mapping->gfp_mask;
 242                         page = find_or_create_page(vnode->vfs_inode.i_mapping,
 243                                                    index, gfp);
 244                         if (!page)
 245                                 goto error;
 246                         if (!PagePrivate(page))
 247                                 attach_page_private(page, (void *)1);
 248                         dir_page = kmap(page);
 249                 }
 250
 251                 /* Abandon the edit if we got a callback break. */
 252                 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
 253                         goto invalidated;
 254
 255                 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
 256
 257                 _debug("block %u: %2u %3u %u",
 258                        b,
 259                        (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
 260                        ntohs(block->hdr.npages),
 261                        ntohs(block->hdr.magic));
 262
 263                 /* Initialise the block if necessary. */
 264                 if (b == nr_blocks) {
 265                         _debug("init %u", b);
 266                         afs_edit_init_block(meta, block, b);
 267                         i_size_write(&vnode->vfs_inode, (b + 1) * AFS_DIR_BLOCK_SIZE);
 268                 }
 269
 270                 /* Only lower dir pages have a counter in the header. */
 271                 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
 272                     meta->meta.alloc_ctrs[b] >= need_slots) {
 273                         /* We need to try and find one or more consecutive
 274                          * slots to hold the entry.
 275                          */
 276                         slot = afs_find_contig_bits(block, need_slots);
 277                         if (slot >= 0) {
 278                                 _debug("slot %u", slot);
 279                                 goto found_space;
 280                         }
 281                 }
 282
 283                 if (page != page0) {
 284                         unlock_page(page);
 285                         kunmap(page);
 286                         put_page(page);
 287                 }
 288         }
 289
 290         /* There are no spare slots of sufficient size, yet the operation
 291          * succeeded.  Download the directory again.
 292          */
 293         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
 294         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 295         goto out_unmap;
 296
 297 new_directory:
 298         afs_edit_init_block(meta, meta, 0);
 299         i_size = AFS_DIR_BLOCK_SIZE;
 300         i_size_write(&vnode->vfs_inode, i_size);
 301         slot = AFS_DIR_RESV_BLOCKS0;
 302         page = page0;
 303         block = meta;
 304         nr_blocks = 1;
 305         b = 0;
 306
 307 found_space:
 308         /* Set the dirent slot. */
 309         trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
 310                            new_fid->vnode, new_fid->unique, name->name);
 311         de = &block->dirents[slot];
 312         de->u.valid     = 1;
 313         de->u.unused[0] = 0;
 314         de->u.hash_next = 0; // TODO: Really need to maintain this
 315         de->u.vnode     = htonl(new_fid->vnode);
 316         de->u.unique    = htonl(new_fid->unique);
 317         memcpy(de->u.name, name->name, name->len + 1);
 318         de->u.name[name->len] = 0;
 319
 320         /* Adjust the bitmap. */
 321         afs_set_contig_bits(block, slot, need_slots);
 322         if (page != page0) {
 323                 unlock_page(page);
 324                 kunmap(page);
 325                 put_page(page);
 326         }
 327
 328         /* Adjust the allocation counter. */
 329         if (b < AFS_DIR_BLOCKS_WITH_CTR)
 330                 meta->meta.alloc_ctrs[b] -= need_slots;
 331
 332         inode_inc_iversion_raw(&vnode->vfs_inode);
 333         afs_stat_v(vnode, n_dir_cr);
 334         _debug("Insert %s in %u[%u]", name->name, b, slot);
 335
 336 out_unmap:
 337         unlock_page(page0);
 338         kunmap(page0);
 339         put_page(page0);
 340         _leave("");
 341         return;
 342
 343 invalidated:
 344         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
 345         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 346         if (page != page0) {
 347                 kunmap(page);
 348                 put_page(page);
 349         }
 350         goto out_unmap;
 351
 352 error:
 353         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
 354         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 355         goto out_unmap;
 356 }
 357
 358 /*
 359  * Edit a directory's file data to remove a new directory entry.  Doing this
 360  * after unlink, rmdir or rename if the data version number is incremented by
 361  * exactly one avoids the need to re-download the entire directory contents.
 362  *
 363  * The caller must hold the inode locked.
 364  */
 365 void afs_edit_dir_remove(struct afs_vnode *vnode,
 366                          struct qstr *name, enum afs_edit_dir_reason why)
 367 {
 368         struct afs_xdr_dir_page *meta_page, *dir_page;
 369         union afs_xdr_dir_block *meta, *block;
 370         union afs_xdr_dirent *de;
 371         struct page *page0, *page;
 372         unsigned int need_slots, nr_blocks, b;
 373         pgoff_t index;
 374         loff_t i_size;
 375         int slot;
 376
 377         _enter(",,{%d,%s},", name->len, name->name);
 378
 379         i_size = i_size_read(&vnode->vfs_inode);
 380         if (i_size < AFS_DIR_BLOCK_SIZE ||
 381             i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
 382             (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
 383                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 384                 return;
 385         }
 386         nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
 387
 388         page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
 389         if (!page0) {
 390                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 391                 _leave(" [fgp]");
 392                 return;
 393         }
 394
 395         /* Work out how many slots we're going to discard. */
 396         need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 397         need_slots /= AFS_DIR_DIRENT_SIZE;
 398
 399         meta_page = kmap(page0);
 400         meta = &meta_page->blocks[0];
 401
 402         /* Find a page that has sufficient slots available.  Each VM page
 403          * contains two or more directory blocks.
 404          */
 405         for (b = 0; b < nr_blocks; b++) {
 406                 index = b / AFS_DIR_BLOCKS_PER_PAGE;
 407                 if (index != 0) {
 408                         page = find_lock_page(vnode->vfs_inode.i_mapping, index);
 409                         if (!page)
 410                                 goto error;
 411                         dir_page = kmap(page);
 412                 } else {
 413                         page = page0;
 414                         dir_page = meta_page;
 415                 }
 416
 417                 /* Abandon the edit if we got a callback break. */
 418                 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
 419                         goto invalidated;
 420
 421                 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
 422
 423                 if (b > AFS_DIR_BLOCKS_WITH_CTR ||
 424                     meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
 425                         slot = afs_dir_scan_block(block, name, b);
 426                         if (slot >= 0)
 427                                 goto found_dirent;
 428                 }
 429
 430                 if (page != page0) {
 431                         unlock_page(page);
 432                         kunmap(page);
 433                         put_page(page);
 434                 }
 435         }
 436
 437         /* Didn't find the dirent to clobber.  Download the directory again. */
 438         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
 439                            0, 0, 0, 0, name->name);
 440         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 441         goto out_unmap;
 442
 443 found_dirent:
 444         de = &block->dirents[slot];
 445
 446         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
 447                            ntohl(de->u.vnode), ntohl(de->u.unique),
 448                            name->name);
 449
 450         memset(de, 0, sizeof(*de) * need_slots);
 451
 452         /* Adjust the bitmap. */
 453         afs_clear_contig_bits(block, slot, need_slots);
 454         if (page != page0) {
 455                 unlock_page(page);
 456                 kunmap(page);
 457                 put_page(page);
 458         }
 459
 460         /* Adjust the allocation counter. */
 461         if (b < AFS_DIR_BLOCKS_WITH_CTR)
 462                 meta->meta.alloc_ctrs[b] += need_slots;
 463
 464         inode_set_iversion_raw(&vnode->vfs_inode, vnode->status.data_version);
 465         afs_stat_v(vnode, n_dir_rm);
 466         _debug("Remove %s from %u[%u]", name->name, b, slot);
 467
 468 out_unmap:
 469         unlock_page(page0);
 470         kunmap(page0);
 471         put_page(page0);
 472         _leave("");
 473         return;
 474
 475 invalidated:
 476         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
 477                            0, 0, 0, 0, name->name);
 478         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 479         if (page != page0) {
 480                 unlock_page(page);
 481                 kunmap(page);
 482                 put_page(page);
 483         }
 484         goto out_unmap;
 485
 486 error:
 487         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
 488                            0, 0, 0, 0, name->name);
 489         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 490         goto out_unmap;
 491 }