582 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/* AFS filesystem directory editing3 *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 a20 * variable. The first bit doesn't count as it corresponds to the block header21 * slot. nr_slots is between 1 and 9.22 */23static 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 else45 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 */68static 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 */89static 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 * Get a new directory folio.109 */110static struct folio *afs_dir_get_folio(struct afs_vnode *vnode, pgoff_t index)111{112 struct address_space *mapping = vnode->netfs.inode.i_mapping;113 struct folio *folio;114 115 folio = __filemap_get_folio(mapping, index,116 FGP_LOCK | FGP_ACCESSED | FGP_CREAT,117 mapping->gfp_mask);118 if (IS_ERR(folio)) {119 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);120 return NULL;121 }122 if (!folio_test_private(folio))123 folio_attach_private(folio, (void *)1);124 return folio;125}126 127/*128 * Scan a directory block looking for a dirent of the right name.129 */130static int afs_dir_scan_block(const union afs_xdr_dir_block *block, const struct qstr *name,131 unsigned int blocknum)132{133 const union afs_xdr_dirent *de;134 u64 bitmap;135 int d, len, n;136 137 _enter("");138 139 bitmap = (u64)block->hdr.bitmap[0] << 0 * 8;140 bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;141 bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;142 bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;143 bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;144 bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;145 bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;146 bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;147 148 for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);149 d < AFS_DIR_SLOTS_PER_BLOCK;150 d++) {151 if (!((bitmap >> d) & 1))152 continue;153 de = &block->dirents[d];154 if (de->u.valid != 1)155 continue;156 157 /* The block was NUL-terminated by afs_dir_check_page(). */158 len = strlen(de->u.name);159 if (len == name->len &&160 memcmp(de->u.name, name->name, name->len) == 0)161 return d;162 163 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);164 n /= AFS_DIR_DIRENT_SIZE;165 d += n - 1;166 }167 168 return -1;169}170 171/*172 * Initialise a new directory block. Note that block 0 is special and contains173 * some extra metadata.174 */175static void afs_edit_init_block(union afs_xdr_dir_block *meta,176 union afs_xdr_dir_block *block, int block_num)177{178 memset(block, 0, sizeof(*block));179 block->hdr.npages = htons(1);180 block->hdr.magic = AFS_DIR_MAGIC;181 block->hdr.bitmap[0] = 1;182 183 if (block_num == 0) {184 block->hdr.bitmap[0] = 0xff;185 block->hdr.bitmap[1] = 0x1f;186 memset(block->meta.alloc_ctrs,187 AFS_DIR_SLOTS_PER_BLOCK,188 sizeof(block->meta.alloc_ctrs));189 meta->meta.alloc_ctrs[0] =190 AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;191 }192 193 if (block_num < AFS_DIR_BLOCKS_WITH_CTR)194 meta->meta.alloc_ctrs[block_num] =195 AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;196}197 198/*199 * Edit a directory's file data to add a new directory entry. Doing this after200 * create, mkdir, symlink, link or rename if the data version number is201 * incremented by exactly one avoids the need to re-download the entire202 * directory contents.203 *204 * The caller must hold the inode locked.205 */206void afs_edit_dir_add(struct afs_vnode *vnode,207 struct qstr *name, struct afs_fid *new_fid,208 enum afs_edit_dir_reason why)209{210 union afs_xdr_dir_block *meta, *block;211 union afs_xdr_dirent *de;212 struct folio *folio0, *folio;213 unsigned int need_slots, nr_blocks, b;214 pgoff_t index;215 loff_t i_size;216 int slot;217 218 _enter(",,{%d,%s},", name->len, name->name);219 220 i_size = i_size_read(&vnode->netfs.inode);221 if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||222 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {223 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);224 return;225 }226 227 folio0 = afs_dir_get_folio(vnode, 0);228 if (!folio0) {229 _leave(" [fgp]");230 return;231 }232 233 /* Work out how many slots we're going to need. */234 need_slots = afs_dir_calc_slots(name->len);235 236 meta = kmap_local_folio(folio0, 0);237 if (i_size == 0)238 goto new_directory;239 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;240 241 /* Find a block that has sufficient slots available. Each folio242 * contains two or more directory blocks.243 */244 for (b = 0; b < nr_blocks + 1; b++) {245 /* If the directory extended into a new folio, then we need to246 * tack a new folio on the end.247 */248 index = b / AFS_DIR_BLOCKS_PER_PAGE;249 if (nr_blocks >= AFS_DIR_MAX_BLOCKS)250 goto error;251 if (index >= folio_nr_pages(folio0)) {252 folio = afs_dir_get_folio(vnode, index);253 if (!folio)254 goto error;255 } else {256 folio = folio0;257 }258 259 block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_pos(folio));260 261 /* Abandon the edit if we got a callback break. */262 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))263 goto invalidated;264 265 _debug("block %u: %2u %3u %u",266 b,267 (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,268 ntohs(block->hdr.npages),269 ntohs(block->hdr.magic));270 271 /* Initialise the block if necessary. */272 if (b == nr_blocks) {273 _debug("init %u", b);274 afs_edit_init_block(meta, block, b);275 afs_set_i_size(vnode, (b + 1) * AFS_DIR_BLOCK_SIZE);276 }277 278 /* Only lower dir blocks have a counter in the header. */279 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||280 meta->meta.alloc_ctrs[b] >= need_slots) {281 /* We need to try and find one or more consecutive282 * slots to hold the entry.283 */284 slot = afs_find_contig_bits(block, need_slots);285 if (slot >= 0) {286 _debug("slot %u", slot);287 goto found_space;288 }289 }290 291 kunmap_local(block);292 if (folio != folio0) {293 folio_unlock(folio);294 folio_put(folio);295 }296 }297 298 /* There are no spare slots of sufficient size, yet the operation299 * succeeded. Download the directory again.300 */301 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);302 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);303 goto out_unmap;304 305new_directory:306 afs_edit_init_block(meta, meta, 0);307 i_size = AFS_DIR_BLOCK_SIZE;308 afs_set_i_size(vnode, i_size);309 slot = AFS_DIR_RESV_BLOCKS0;310 folio = folio0;311 block = kmap_local_folio(folio, 0);312 nr_blocks = 1;313 b = 0;314 315found_space:316 /* Set the dirent slot. */317 trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,318 new_fid->vnode, new_fid->unique, name->name);319 de = &block->dirents[slot];320 de->u.valid = 1;321 de->u.unused[0] = 0;322 de->u.hash_next = 0; // TODO: Really need to maintain this323 de->u.vnode = htonl(new_fid->vnode);324 de->u.unique = htonl(new_fid->unique);325 memcpy(de->u.name, name->name, name->len + 1);326 de->u.name[name->len] = 0;327 328 /* Adjust the bitmap. */329 afs_set_contig_bits(block, slot, need_slots);330 kunmap_local(block);331 if (folio != folio0) {332 folio_unlock(folio);333 folio_put(folio);334 }335 336 /* Adjust the allocation counter. */337 if (b < AFS_DIR_BLOCKS_WITH_CTR)338 meta->meta.alloc_ctrs[b] -= need_slots;339 340 inode_inc_iversion_raw(&vnode->netfs.inode);341 afs_stat_v(vnode, n_dir_cr);342 _debug("Insert %s in %u[%u]", name->name, b, slot);343 344out_unmap:345 kunmap_local(meta);346 folio_unlock(folio0);347 folio_put(folio0);348 _leave("");349 return;350 351invalidated:352 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);353 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);354 kunmap_local(block);355 if (folio != folio0) {356 folio_unlock(folio);357 folio_put(folio);358 }359 goto out_unmap;360 361error:362 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);363 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);364 goto out_unmap;365}366 367/*368 * Edit a directory's file data to remove a new directory entry. Doing this369 * after unlink, rmdir or rename if the data version number is incremented by370 * exactly one avoids the need to re-download the entire directory contents.371 *372 * The caller must hold the inode locked.373 */374void afs_edit_dir_remove(struct afs_vnode *vnode,375 struct qstr *name, enum afs_edit_dir_reason why)376{377 union afs_xdr_dir_block *meta, *block;378 union afs_xdr_dirent *de;379 struct folio *folio0, *folio;380 unsigned int need_slots, nr_blocks, b;381 pgoff_t index;382 loff_t i_size;383 int slot;384 385 _enter(",,{%d,%s},", name->len, name->name);386 387 i_size = i_size_read(&vnode->netfs.inode);388 if (i_size < AFS_DIR_BLOCK_SIZE ||389 i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||390 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {391 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);392 return;393 }394 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;395 396 folio0 = afs_dir_get_folio(vnode, 0);397 if (!folio0) {398 _leave(" [fgp]");399 return;400 }401 402 /* Work out how many slots we're going to discard. */403 need_slots = afs_dir_calc_slots(name->len);404 405 meta = kmap_local_folio(folio0, 0);406 407 /* Find a block that has sufficient slots available. Each folio408 * contains two or more directory blocks.409 */410 for (b = 0; b < nr_blocks; b++) {411 index = b / AFS_DIR_BLOCKS_PER_PAGE;412 if (index >= folio_nr_pages(folio0)) {413 folio = afs_dir_get_folio(vnode, index);414 if (!folio)415 goto error;416 } else {417 folio = folio0;418 }419 420 block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_pos(folio));421 422 /* Abandon the edit if we got a callback break. */423 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))424 goto invalidated;425 426 if (b > AFS_DIR_BLOCKS_WITH_CTR ||427 meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {428 slot = afs_dir_scan_block(block, name, b);429 if (slot >= 0)430 goto found_dirent;431 }432 433 kunmap_local(block);434 if (folio != folio0) {435 folio_unlock(folio);436 folio_put(folio);437 }438 }439 440 /* Didn't find the dirent to clobber. Download the directory again. */441 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,442 0, 0, 0, 0, name->name);443 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);444 goto out_unmap;445 446found_dirent:447 de = &block->dirents[slot];448 449 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,450 ntohl(de->u.vnode), ntohl(de->u.unique),451 name->name);452 453 memset(de, 0, sizeof(*de) * need_slots);454 455 /* Adjust the bitmap. */456 afs_clear_contig_bits(block, slot, need_slots);457 kunmap_local(block);458 if (folio != folio0) {459 folio_unlock(folio);460 folio_put(folio);461 }462 463 /* Adjust the allocation counter. */464 if (b < AFS_DIR_BLOCKS_WITH_CTR)465 meta->meta.alloc_ctrs[b] += need_slots;466 467 inode_set_iversion_raw(&vnode->netfs.inode, vnode->status.data_version);468 afs_stat_v(vnode, n_dir_rm);469 _debug("Remove %s from %u[%u]", name->name, b, slot);470 471out_unmap:472 kunmap_local(meta);473 folio_unlock(folio0);474 folio_put(folio0);475 _leave("");476 return;477 478invalidated:479 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,480 0, 0, 0, 0, name->name);481 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);482 kunmap_local(block);483 if (folio != folio0) {484 folio_unlock(folio);485 folio_put(folio);486 }487 goto out_unmap;488 489error:490 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,491 0, 0, 0, 0, name->name);492 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);493 goto out_unmap;494}495 496/*497 * Edit a subdirectory that has been moved between directories to update the498 * ".." entry.499 */500void afs_edit_dir_update_dotdot(struct afs_vnode *vnode, struct afs_vnode *new_dvnode,501 enum afs_edit_dir_reason why)502{503 union afs_xdr_dir_block *block;504 union afs_xdr_dirent *de;505 struct folio *folio;506 unsigned int nr_blocks, b;507 pgoff_t index;508 loff_t i_size;509 int slot;510 511 _enter("");512 513 i_size = i_size_read(&vnode->netfs.inode);514 if (i_size < AFS_DIR_BLOCK_SIZE) {515 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);516 return;517 }518 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;519 520 /* Find a block that has sufficient slots available. Each folio521 * contains two or more directory blocks.522 */523 for (b = 0; b < nr_blocks; b++) {524 index = b / AFS_DIR_BLOCKS_PER_PAGE;525 folio = afs_dir_get_folio(vnode, index);526 if (!folio)527 goto error;528 529 block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_pos(folio));530 531 /* Abandon the edit if we got a callback break. */532 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))533 goto invalidated;534 535 slot = afs_dir_scan_block(block, &dotdot_name, b);536 if (slot >= 0)537 goto found_dirent;538 539 kunmap_local(block);540 folio_unlock(folio);541 folio_put(folio);542 }543 544 /* Didn't find the dirent to clobber. Download the directory again. */545 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_nodd,546 0, 0, 0, 0, "..");547 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);548 goto out;549 550found_dirent:551 de = &block->dirents[slot];552 de->u.vnode = htonl(new_dvnode->fid.vnode);553 de->u.unique = htonl(new_dvnode->fid.unique);554 555 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_dd, b, slot,556 ntohl(de->u.vnode), ntohl(de->u.unique), "..");557 558 kunmap_local(block);559 folio_unlock(folio);560 folio_put(folio);561 inode_set_iversion_raw(&vnode->netfs.inode, vnode->status.data_version);562 563out:564 _leave("");565 return;566 567invalidated:568 kunmap_local(block);569 folio_unlock(folio);570 folio_put(folio);571 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_inval,572 0, 0, 0, 0, "..");573 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);574 goto out;575 576error:577 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_error,578 0, 0, 0, 0, "..");579 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);580 goto out;581}582