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