LXR linux/fs/afs/dir

   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 */
  27static 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 */
  72static 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 */
  97static 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 */
 122static 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 */
 167static 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 */
 198void 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
 311new_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
 321found_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
 350out_unmap:
 351        unlock_page(page0);
 352        kunmap(page0);
 353        put_page(page0);
 354        _leave("");
 355        return;
 356
 357invalidated:
 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
 366error:
 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 */
 379void 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
 457found_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
 482out_unmap:
 483        unlock_page(page0);
 484        kunmap(page0);
 485        put_page(page0);
 486        _leave("");
 487        return;
 488
 489invalidated:
 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
 500error:
 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}
 506