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