fs/afs/dir_edit.c

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