Commit | Line | Data |
---|---|---|
b4d0d230 | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
63a4681f DH |
2 | /* AFS filesystem directory editing |
3 | * | |
4 | * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved. | |
5 | * Written by David Howells (dhowells@redhat.com) | |
63a4681f DH |
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 | } |