Loading...
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 * Get a new directory folio.
109 */
110static 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 mapping->gfp_mask);
118 if (IS_ERR(folio)) {
119 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
120 return NULL;
121 }
122 if (!folio_test_private(folio))
123 folio_attach_private(folio, (void *)1);
124 return folio;
125}
126
127/*
128 * Scan a directory block looking for a dirent of the right name.
129 */
130static int afs_dir_scan_block(const union afs_xdr_dir_block *block, const struct qstr *name,
131 unsigned int blocknum)
132{
133 const 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(de->u.name, name->name, 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 */
175static 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 */
206void 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(&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, &vnode->flags);
224 return;
225 }
226
227 folio0 = afs_dir_get_folio(vnode, 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);
235
236 meta = kmap_local_folio(folio0, 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(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, b * AFS_DIR_BLOCK_SIZE - folio_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, b);
275 afs_set_i_size(vnode, (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, 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(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
302 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
303 goto out_unmap;
304
305new_directory:
306 afs_edit_init_block(meta, meta, 0);
307 i_size = AFS_DIR_BLOCK_SIZE;
308 afs_set_i_size(vnode, i_size);
309 slot = AFS_DIR_RESV_BLOCKS0;
310 folio = folio0;
311 block = kmap_local_folio(folio, 0);
312 nr_blocks = 1;
313 b = 0;
314
315found_space:
316 /* Set the dirent slot. */
317 trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
318 new_fid->vnode, new_fid->unique, 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, slot, 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(&vnode->netfs.inode);
341 afs_stat_v(vnode, n_dir_cr);
342 _debug("Insert %s in %u[%u]", name->name, b, slot);
343
344out_unmap:
345 kunmap_local(meta);
346 folio_unlock(folio0);
347 folio_put(folio0);
348 _leave("");
349 return;
350
351invalidated:
352 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
353 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
354 kunmap_local(block);
355 if (folio != folio0) {
356 folio_unlock(folio);
357 folio_put(folio);
358 }
359 goto out_unmap;
360
361error:
362 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
363 clear_bit(AFS_VNODE_DIR_VALID, &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 */
374void 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(&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, &vnode->flags);
392 return;
393 }
394 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
395
396 folio0 = afs_dir_get_folio(vnode, 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);
404
405 meta = kmap_local_folio(folio0, 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(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, b * AFS_DIR_BLOCK_SIZE - folio_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, 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(vnode, why, afs_edit_dir_delete_noent,
442 0, 0, 0, 0, name->name);
443 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
444 goto out_unmap;
445
446found_dirent:
447 de = &block->dirents[slot];
448
449 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
450 ntohl(de->u.vnode), ntohl(de->u.unique),
451 name->name);
452
453 memset(de, 0, sizeof(*de) * need_slots);
454
455 /* Adjust the bitmap. */
456 afs_clear_contig_bits(block, slot, 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(&vnode->netfs.inode, vnode->status.data_version);
468 afs_stat_v(vnode, n_dir_rm);
469 _debug("Remove %s from %u[%u]", name->name, b, slot);
470
471out_unmap:
472 kunmap_local(meta);
473 folio_unlock(folio0);
474 folio_put(folio0);
475 _leave("");
476 return;
477
478invalidated:
479 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
480 0, 0, 0, 0, name->name);
481 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
482 kunmap_local(block);
483 if (folio != folio0) {
484 folio_unlock(folio);
485 folio_put(folio);
486 }
487 goto out_unmap;
488
489error:
490 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
491 0, 0, 0, 0, name->name);
492 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
493 goto out_unmap;
494}
495
496/*
497 * Edit a subdirectory that has been moved between directories to update the
498 * ".." entry.
499 */
500void afs_edit_dir_update_dotdot(struct afs_vnode *vnode, struct afs_vnode *new_dvnode,
501 enum afs_edit_dir_reason why)
502{
503 union afs_xdr_dir_block *block;
504 union afs_xdr_dirent *de;
505 struct folio *folio;
506 unsigned int nr_blocks, b;
507 pgoff_t index;
508 loff_t i_size;
509 int slot;
510
511 _enter("");
512
513 i_size = i_size_read(&vnode->netfs.inode);
514 if (i_size < AFS_DIR_BLOCK_SIZE) {
515 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
516 return;
517 }
518 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
519
520 /* Find a block that has sufficient slots available. Each folio
521 * contains two or more directory blocks.
522 */
523 for (b = 0; b < nr_blocks; b++) {
524 index = b / AFS_DIR_BLOCKS_PER_PAGE;
525 folio = afs_dir_get_folio(vnode, index);
526 if (!folio)
527 goto error;
528
529 block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_pos(folio));
530
531 /* Abandon the edit if we got a callback break. */
532 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
533 goto invalidated;
534
535 slot = afs_dir_scan_block(block, &dotdot_name, b);
536 if (slot >= 0)
537 goto found_dirent;
538
539 kunmap_local(block);
540 folio_unlock(folio);
541 folio_put(folio);
542 }
543
544 /* Didn't find the dirent to clobber. Download the directory again. */
545 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_nodd,
546 0, 0, 0, 0, "..");
547 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
548 goto out;
549
550found_dirent:
551 de = &block->dirents[slot];
552 de->u.vnode = htonl(new_dvnode->fid.vnode);
553 de->u.unique = htonl(new_dvnode->fid.unique);
554
555 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_dd, b, slot,
556 ntohl(de->u.vnode), ntohl(de->u.unique), "..");
557
558 kunmap_local(block);
559 folio_unlock(folio);
560 folio_put(folio);
561 inode_set_iversion_raw(&vnode->netfs.inode, vnode->status.data_version);
562
563out:
564 _leave("");
565 return;
566
567invalidated:
568 kunmap_local(block);
569 folio_unlock(folio);
570 folio_put(folio);
571 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_inval,
572 0, 0, 0, 0, "..");
573 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
574 goto out;
575
576error:
577 trace_afs_edit_dir(vnode, why, afs_edit_dir_update_error,
578 0, 0, 0, 0, "..");
579 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
580 goto out;
581}
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 set_page_private(page, 1);
248 SetPagePrivate(page);
249 }
250 dir_page = kmap(page);
251 }
252
253 /* Abandon the edit if we got a callback break. */
254 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
255 goto invalidated;
256
257 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
258
259 _debug("block %u: %2u %3u %u",
260 b,
261 (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
262 ntohs(block->hdr.npages),
263 ntohs(block->hdr.magic));
264
265 /* Initialise the block if necessary. */
266 if (b == nr_blocks) {
267 _debug("init %u", b);
268 afs_edit_init_block(meta, block, b);
269 i_size_write(&vnode->vfs_inode, (b + 1) * AFS_DIR_BLOCK_SIZE);
270 }
271
272 /* Only lower dir pages have a counter in the header. */
273 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
274 meta->meta.alloc_ctrs[b] >= need_slots) {
275 /* We need to try and find one or more consecutive
276 * slots to hold the entry.
277 */
278 slot = afs_find_contig_bits(block, need_slots);
279 if (slot >= 0) {
280 _debug("slot %u", slot);
281 goto found_space;
282 }
283 }
284
285 if (page != page0) {
286 unlock_page(page);
287 kunmap(page);
288 put_page(page);
289 }
290 }
291
292 /* There are no spare slots of sufficient size, yet the operation
293 * succeeded. Download the directory again.
294 */
295 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
296 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
297 goto out_unmap;
298
299new_directory:
300 afs_edit_init_block(meta, meta, 0);
301 i_size = AFS_DIR_BLOCK_SIZE;
302 i_size_write(&vnode->vfs_inode, i_size);
303 slot = AFS_DIR_RESV_BLOCKS0;
304 page = page0;
305 block = meta;
306 nr_blocks = 1;
307 b = 0;
308
309found_space:
310 /* Set the dirent slot. */
311 trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
312 new_fid->vnode, new_fid->unique, name->name);
313 de = &block->dirents[slot];
314 de->u.valid = 1;
315 de->u.unused[0] = 0;
316 de->u.hash_next = 0; // TODO: Really need to maintain this
317 de->u.vnode = htonl(new_fid->vnode);
318 de->u.unique = htonl(new_fid->unique);
319 memcpy(de->u.name, name->name, name->len + 1);
320 de->u.name[name->len] = 0;
321
322 /* Adjust the bitmap. */
323 afs_set_contig_bits(block, slot, need_slots);
324 if (page != page0) {
325 unlock_page(page);
326 kunmap(page);
327 put_page(page);
328 }
329
330 /* Adjust the allocation counter. */
331 if (b < AFS_DIR_BLOCKS_WITH_CTR)
332 meta->meta.alloc_ctrs[b] -= need_slots;
333
334 inode_inc_iversion_raw(&vnode->vfs_inode);
335 afs_stat_v(vnode, n_dir_cr);
336 _debug("Insert %s in %u[%u]", name->name, b, slot);
337
338out_unmap:
339 unlock_page(page0);
340 kunmap(page0);
341 put_page(page0);
342 _leave("");
343 return;
344
345invalidated:
346 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
347 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
348 if (page != page0) {
349 kunmap(page);
350 put_page(page);
351 }
352 goto out_unmap;
353
354error:
355 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
356 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
357 goto out_unmap;
358}
359
360/*
361 * Edit a directory's file data to remove a new directory entry. Doing this
362 * after unlink, rmdir or rename if the data version number is incremented by
363 * exactly one avoids the need to re-download the entire directory contents.
364 *
365 * The caller must hold the inode locked.
366 */
367void afs_edit_dir_remove(struct afs_vnode *vnode,
368 struct qstr *name, enum afs_edit_dir_reason why)
369{
370 struct afs_xdr_dir_page *meta_page, *dir_page;
371 union afs_xdr_dir_block *meta, *block;
372 union afs_xdr_dirent *de;
373 struct page *page0, *page;
374 unsigned int need_slots, nr_blocks, b;
375 pgoff_t index;
376 loff_t i_size;
377 int slot;
378
379 _enter(",,{%d,%s},", name->len, name->name);
380
381 i_size = i_size_read(&vnode->vfs_inode);
382 if (i_size < AFS_DIR_BLOCK_SIZE ||
383 i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
384 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
385 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
386 return;
387 }
388 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
389
390 page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
391 if (!page0) {
392 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
393 _leave(" [fgp]");
394 return;
395 }
396
397 /* Work out how many slots we're going to discard. */
398 need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
399 need_slots /= AFS_DIR_DIRENT_SIZE;
400
401 meta_page = kmap(page0);
402 meta = &meta_page->blocks[0];
403
404 /* Find a page that has sufficient slots available. Each VM page
405 * contains two or more directory blocks.
406 */
407 for (b = 0; b < nr_blocks; b++) {
408 index = b / AFS_DIR_BLOCKS_PER_PAGE;
409 if (index != 0) {
410 page = find_lock_page(vnode->vfs_inode.i_mapping, index);
411 if (!page)
412 goto error;
413 dir_page = kmap(page);
414 } else {
415 page = page0;
416 dir_page = meta_page;
417 }
418
419 /* Abandon the edit if we got a callback break. */
420 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
421 goto invalidated;
422
423 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
424
425 if (b > AFS_DIR_BLOCKS_WITH_CTR ||
426 meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
427 slot = afs_dir_scan_block(block, name, b);
428 if (slot >= 0)
429 goto found_dirent;
430 }
431
432 if (page != page0) {
433 unlock_page(page);
434 kunmap(page);
435 put_page(page);
436 }
437 }
438
439 /* Didn't find the dirent to clobber. Download the directory again. */
440 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
441 0, 0, 0, 0, name->name);
442 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
443 goto out_unmap;
444
445found_dirent:
446 de = &block->dirents[slot];
447
448 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
449 ntohl(de->u.vnode), ntohl(de->u.unique),
450 name->name);
451
452 memset(de, 0, sizeof(*de) * need_slots);
453
454 /* Adjust the bitmap. */
455 afs_clear_contig_bits(block, slot, need_slots);
456 if (page != page0) {
457 unlock_page(page);
458 kunmap(page);
459 put_page(page);
460 }
461
462 /* Adjust the allocation counter. */
463 if (b < AFS_DIR_BLOCKS_WITH_CTR)
464 meta->meta.alloc_ctrs[b] += need_slots;
465
466 inode_set_iversion_raw(&vnode->vfs_inode, vnode->status.data_version);
467 afs_stat_v(vnode, n_dir_rm);
468 _debug("Remove %s from %u[%u]", name->name, b, slot);
469
470out_unmap:
471 unlock_page(page0);
472 kunmap(page0);
473 put_page(page0);
474 _leave("");
475 return;
476
477invalidated:
478 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
479 0, 0, 0, 0, name->name);
480 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
481 if (page != page0) {
482 unlock_page(page);
483 kunmap(page);
484 put_page(page);
485 }
486 goto out_unmap;
487
488error:
489 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
490 0, 0, 0, 0, name->name);
491 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
492 goto out_unmap;
493}