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 */ 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 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 */ 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 * Scan a directory block looking for a dirent of the right name. 109 */ 110static 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 */ 155static 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 */ 186void 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 afs_set_i_size(vnode, (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 297new_directory: 298 afs_edit_init_block(meta, meta, 0); 299 i_size = AFS_DIR_BLOCK_SIZE; 300 afs_set_i_size(vnode, i_size); 301 slot = AFS_DIR_RESV_BLOCKS0; 302 page = page0; 303 block = meta; 304 nr_blocks = 1; 305 b = 0; 306 307found_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 336out_unmap: 337 unlock_page(page0); 338 kunmap(page0); 339 put_page(page0); 340 _leave(""); 341 return; 342 343invalidated: 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 352error: 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 */ 365void 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 443found_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 468out_unmap: 469 unlock_page(page0); 470 kunmap(page0); 471 put_page(page0); 472 _leave(""); 473 return; 474 475invalidated: 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 486error: 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} 492