dir_edit.c 13 KB

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