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; |
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 | */ |
89 | static 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 | */ |
110 | static 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 | gfp: mapping->gfp_mask); |
118 | if (IS_ERR(ptr: folio)) { |
119 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
120 | return NULL; |
121 | } |
122 | if (!folio_test_private(folio)) |
123 | folio_attach_private(folio, data: (void *)1); |
124 | return folio; |
125 | } |
126 | |
127 | /* |
128 | * Scan a directory block looking for a dirent of the right name. |
129 | */ |
130 | static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name, |
131 | unsigned int blocknum) |
132 | { |
133 | 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(p: de->u.name, q: name->name, size: 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 contains |
173 | * some extra metadata. |
174 | */ |
175 | static 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 after |
200 | * create, mkdir, symlink, link or rename if the data version number is |
201 | * incremented by exactly one avoids the need to re-download the entire |
202 | * directory contents. |
203 | * |
204 | * The caller must hold the inode locked. |
205 | */ |
206 | void 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(inode: &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, addr: &vnode->flags); |
224 | return; |
225 | } |
226 | |
227 | folio0 = afs_dir_get_folio(vnode, index: 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: name->len); |
235 | |
236 | meta = kmap_local_folio(folio: folio0, offset: 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 folio |
242 | * 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 to |
246 | * 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(folio: 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, offset: b * AFS_DIR_BLOCK_SIZE - folio_file_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, block_num: b); |
275 | afs_set_i_size(vnode, size: (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 consecutive |
282 | * slots to hold the entry. |
283 | */ |
284 | slot = afs_find_contig_bits(block, nr_slots: 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 operation |
299 | * succeeded. Download the directory again. |
300 | */ |
301 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_create_nospc, block: 0, slot: 0, f_vnode: 0, f_unique: 0, name: name->name); |
302 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
303 | goto out_unmap; |
304 | |
305 | new_directory: |
306 | afs_edit_init_block(meta, block: meta, block_num: 0); |
307 | i_size = AFS_DIR_BLOCK_SIZE; |
308 | afs_set_i_size(vnode, size: i_size); |
309 | slot = AFS_DIR_RESV_BLOCKS0; |
310 | folio = folio0; |
311 | block = kmap_local_folio(folio, offset: 0); |
312 | nr_blocks = 1; |
313 | b = 0; |
314 | |
315 | found_space: |
316 | /* Set the dirent slot. */ |
317 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_create, block: b, slot, |
318 | f_vnode: new_fid->vnode, f_unique: new_fid->unique, name: 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 this |
323 | 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, bit: slot, nr_slots: 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(inode: &vnode->netfs.inode); |
341 | afs_stat_v(vnode, n_dir_cr); |
342 | _debug("Insert %s in %u[%u]" , name->name, b, slot); |
343 | |
344 | out_unmap: |
345 | kunmap_local(meta); |
346 | folio_unlock(folio: folio0); |
347 | folio_put(folio: folio0); |
348 | _leave("" ); |
349 | return; |
350 | |
351 | invalidated: |
352 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_create_inval, block: 0, slot: 0, f_vnode: 0, f_unique: 0, name: name->name); |
353 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
354 | kunmap_local(block); |
355 | if (folio != folio0) { |
356 | folio_unlock(folio); |
357 | folio_put(folio); |
358 | } |
359 | goto out_unmap; |
360 | |
361 | error: |
362 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_create_error, block: 0, slot: 0, f_vnode: 0, f_unique: 0, name: name->name); |
363 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
364 | goto out_unmap; |
365 | } |
366 | |
367 | /* |
368 | * Edit a directory's file data to remove a new directory entry. Doing this |
369 | * after unlink, rmdir or rename if the data version number is incremented by |
370 | * exactly one avoids the need to re-download the entire directory contents. |
371 | * |
372 | * The caller must hold the inode locked. |
373 | */ |
374 | void 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(inode: &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, addr: &vnode->flags); |
392 | return; |
393 | } |
394 | nr_blocks = i_size / AFS_DIR_BLOCK_SIZE; |
395 | |
396 | folio0 = afs_dir_get_folio(vnode, index: 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: name->len); |
404 | |
405 | meta = kmap_local_folio(folio: folio0, offset: 0); |
406 | |
407 | /* Find a block that has sufficient slots available. Each folio |
408 | * 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(folio: 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, offset: b * AFS_DIR_BLOCK_SIZE - folio_file_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, blocknum: 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(dvnode: vnode, why, op: afs_edit_dir_delete_noent, |
442 | block: 0, slot: 0, f_vnode: 0, f_unique: 0, name: name->name); |
443 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
444 | goto out_unmap; |
445 | |
446 | found_dirent: |
447 | de = &block->dirents[slot]; |
448 | |
449 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_delete, block: b, slot, |
450 | ntohl(de->u.vnode), ntohl(de->u.unique), |
451 | name: name->name); |
452 | |
453 | memset(de, 0, sizeof(*de) * need_slots); |
454 | |
455 | /* Adjust the bitmap. */ |
456 | afs_clear_contig_bits(block, bit: slot, nr_slots: 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(inode: &vnode->netfs.inode, val: vnode->status.data_version); |
468 | afs_stat_v(vnode, n_dir_rm); |
469 | _debug("Remove %s from %u[%u]" , name->name, b, slot); |
470 | |
471 | out_unmap: |
472 | kunmap_local(meta); |
473 | folio_unlock(folio: folio0); |
474 | folio_put(folio: folio0); |
475 | _leave("" ); |
476 | return; |
477 | |
478 | invalidated: |
479 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_delete_inval, |
480 | block: 0, slot: 0, f_vnode: 0, f_unique: 0, name: name->name); |
481 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
482 | kunmap_local(block); |
483 | if (folio != folio0) { |
484 | folio_unlock(folio); |
485 | folio_put(folio); |
486 | } |
487 | goto out_unmap; |
488 | |
489 | error: |
490 | trace_afs_edit_dir(dvnode: vnode, why, op: afs_edit_dir_delete_error, |
491 | block: 0, slot: 0, f_vnode: 0, f_unique: 0, name: name->name); |
492 | clear_bit(AFS_VNODE_DIR_VALID, addr: &vnode->flags); |
493 | goto out_unmap; |
494 | } |
495 | |