projects/linux·blob master · refs

699 lines · 17.8 KiB

1// SPDX-License-Identifier: GPL-2.0+
2/*
3 * NILFS directory entry operations
4 *
5 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
6 *
7 * Modified for NILFS by Amagai Yoshiji.
8 */
9/*
10 * linux/fs/ext2/dir.c
11 *
12 * Copyright (C) 1992, 1993, 1994, 1995
13 * Remy Card ([email protected])
14 * Laboratoire MASI - Institut Blaise Pascal
15 * Universite Pierre et Marie Curie (Paris VI)
16 *
17 * from
18 *
19 * linux/fs/minix/dir.c
20 *
21 * Copyright (C) 1991, 1992 Linus Torvalds
22 *
23 * ext2 directory handling functions
24 *
25 * Big-endian to little-endian byte-swapping/bitmaps by
26 * David S. Miller ([email protected]), 1995
27 *
28 * All code that works with directory layout had been switched to pagecache
29 * and moved here. AV
30 */
31
32#include <linux/pagemap.h>
33#include <linux/filelock.h>
34#include "nilfs.h"
35#include "page.h"
36
37static inline unsigned int nilfs_rec_len_from_disk(__le16 dlen)
38{
39 unsigned int len = le16_to_cpu(dlen);
40
41#if (PAGE_SIZE >= 65536)
42 if (len == NILFS_MAX_REC_LEN)
43 return 1 << 16;
44#endif
45 return len;
46}
47
48static inline __le16 nilfs_rec_len_to_disk(unsigned int len)
49{
50#if (PAGE_SIZE >= 65536)
51 if (len == (1 << 16))
52 return cpu_to_le16(NILFS_MAX_REC_LEN);
53
54 BUG_ON(len > (1 << 16));
55#endif
56 return cpu_to_le16(len);
57}
58
59/*
60 * nilfs uses block-sized chunks. Arguably, sector-sized ones would be
61 * more robust, but we have what we have
62 */
63static inline unsigned int nilfs_chunk_size(struct inode *inode)
64{
65 return inode->i_sb->s_blocksize;
66}
67
68/*
69 * Return the offset into page `page_nr' of the last valid
70 * byte in that page, plus one.
71 */
72static unsigned int nilfs_last_byte(struct inode *inode, unsigned long page_nr)
73{
74 u64 last_byte = inode->i_size;
75
76 last_byte -= page_nr << PAGE_SHIFT;
77 if (last_byte > PAGE_SIZE)
78 last_byte = PAGE_SIZE;
79 return last_byte;
80}
81
82static int nilfs_prepare_chunk(struct folio *folio, unsigned int from,
83 unsigned int to)
84{
85 loff_t pos = folio_pos(folio) + from;
86
87 return __block_write_begin(folio, pos, to - from, nilfs_get_block);
88}
89
90static void nilfs_commit_chunk(struct folio *folio,
91 struct address_space *mapping, size_t from, size_t to)
92{
93 struct inode *dir = mapping->host;
94 loff_t pos = folio_pos(folio) + from;
95 size_t copied, len = to - from;
96 unsigned int nr_dirty;
97 int err;
98
99 nr_dirty = nilfs_page_count_clean_buffers(folio, from, to);
100 copied = block_write_end(pos, len, len, folio);
101 if (pos + copied > dir->i_size)
102 i_size_write(dir, pos + copied);
103 if (IS_DIRSYNC(dir))
104 nilfs_set_transaction_flag(NILFS_TI_SYNC);
105 err = nilfs_set_file_dirty(dir, nr_dirty);
106 WARN_ON(err); /* do not happen */
107 folio_unlock(folio);
108}
109
110static bool nilfs_check_folio(struct folio *folio, char *kaddr)
111{
112 struct inode *dir = folio->mapping->host;
113 struct super_block *sb = dir->i_sb;
114 unsigned int chunk_size = nilfs_chunk_size(dir);
115 size_t offs, rec_len;
116 size_t limit = folio_size(folio);
117 struct nilfs_dir_entry *p;
118 char *error;
119
120 if (dir->i_size < folio_pos(folio) + limit) {
121 limit = dir->i_size - folio_pos(folio);
122 if (limit & (chunk_size - 1))
123 goto Ebadsize;
124 if (!limit)
125 goto out;
126 }
127 for (offs = 0; offs <= limit - NILFS_DIR_REC_LEN(1); offs += rec_len) {
128 p = (struct nilfs_dir_entry *)(kaddr + offs);
129 rec_len = nilfs_rec_len_from_disk(p->rec_len);
130
131 if (rec_len < NILFS_DIR_REC_LEN(1))
132 goto Eshort;
133 if (rec_len & 3)
134 goto Ealign;
135 if (rec_len < NILFS_DIR_REC_LEN(p->name_len))
136 goto Enamelen;
137 if (((offs + rec_len - 1) ^ offs) & ~(chunk_size-1))
138 goto Espan;
139 if (unlikely(p->inode &&
140 NILFS_PRIVATE_INODE(le64_to_cpu(p->inode))))
141 goto Einumber;
142 }
143 if (offs != limit)
144 goto Eend;
145out:
146 folio_set_checked(folio);
147 return true;
148
149 /* Too bad, we had an error */
150
151Ebadsize:
152 nilfs_error(sb,
153 "size of directory #%llu is not a multiple of chunk size",
154 dir->i_ino);
155 goto fail;
156Eshort:
157 error = "rec_len is smaller than minimal";
158 goto bad_entry;
159Ealign:
160 error = "unaligned directory entry";
161 goto bad_entry;
162Enamelen:
163 error = "rec_len is too small for name_len";
164 goto bad_entry;
165Espan:
166 error = "directory entry across blocks";
167 goto bad_entry;
168Einumber:
169 error = "disallowed inode number";
170bad_entry:
171 nilfs_error(sb,
172 "bad entry in directory #%llu: %s - offset=%lu, inode=%llu, rec_len=%zd, name_len=%d",
173 dir->i_ino, error, (folio->index << PAGE_SHIFT) + offs,
174 le64_to_cpu(p->inode), rec_len, p->name_len);
175 goto fail;
176Eend:
177 p = (struct nilfs_dir_entry *)(kaddr + offs);
178 nilfs_error(sb,
179 "entry in directory #%llu spans the page boundary offset=%lu, inode=%llu",
180 dir->i_ino, (folio->index << PAGE_SHIFT) + offs,
181 le64_to_cpu(p->inode));
182fail:
183 return false;
184}
185
186static void *nilfs_get_folio(struct inode *dir, unsigned long n,
187 struct folio **foliop)
188{
189 struct address_space *mapping = dir->i_mapping;
190 struct folio *folio = read_mapping_folio(mapping, n, NULL);
191 void *kaddr;
192
193 if (IS_ERR(folio))
194 return folio;
195
196 kaddr = kmap_local_folio(folio, 0);
197 if (unlikely(!folio_test_checked(folio))) {
198 if (!nilfs_check_folio(folio, kaddr))
199 goto fail;
200 }
201
202 *foliop = folio;
203 return kaddr;
204
205fail:
206 folio_release_kmap(folio, kaddr);
207 return ERR_PTR(-EIO);
208}
209
210/*
211 * NOTE! unlike strncmp, nilfs_match returns 1 for success, 0 for failure.
212 *
213 * len <= NILFS_NAME_LEN and de != NULL are guaranteed by caller.
214 */
215static int
216nilfs_match(int len, const unsigned char *name, struct nilfs_dir_entry *de)
217{
218 if (len != de->name_len)
219 return 0;
220 if (!de->inode)
221 return 0;
222 return !memcmp(name, de->name, len);
223}
224
225/*
226 * p is at least 6 bytes before the end of page
227 */
228static struct nilfs_dir_entry *nilfs_next_entry(struct nilfs_dir_entry *p)
229{
230 return (struct nilfs_dir_entry *)((char *)p +
231 nilfs_rec_len_from_disk(p->rec_len));
232}
233
234static inline unsigned int
235nilfs_validate_entry(char *base, unsigned int offset, unsigned int mask)
236{
237 struct nilfs_dir_entry *de = (struct nilfs_dir_entry *)(base + offset);
238 struct nilfs_dir_entry *p =
239 (struct nilfs_dir_entry *)(base + (offset & mask));
240
241 while ((char *)p < (char *)de) {
242 if (p->rec_len == 0)
243 break;
244 p = nilfs_next_entry(p);
245 }
246 return (char *)p - base;
247}
248
249static int nilfs_readdir(struct file *file, struct dir_context *ctx)
250{
251 loff_t pos = ctx->pos;
252 struct inode *inode = file_inode(file);
253 struct super_block *sb = inode->i_sb;
254 unsigned int chunk_size = nilfs_chunk_size(inode);
255 unsigned int offset = pos & ~PAGE_MASK;
256 unsigned long n = pos >> PAGE_SHIFT;
257 unsigned long npages = dir_pages(inode);
258
259 if (pos > inode->i_size - NILFS_DIR_REC_LEN(1))
260 return 0;
261
262 for ( ; n < npages; n++, offset = 0) {
263 char *kaddr, *limit;
264 struct nilfs_dir_entry *de;
265 struct folio *folio;
266
267 kaddr = nilfs_get_folio(inode, n, &folio);
268 if (IS_ERR(kaddr)) {
269 nilfs_error(sb, "bad page in #%llu", inode->i_ino);
270 ctx->pos += PAGE_SIZE - offset;
271 return -EIO;
272 }
273 /*
274 * ctx->pos comes from userspace via llseek and may point
275 * into the middle of an entry -- or at unvalidated bytes
276 * of a crafted image. offset is only nonzero here on the
277 * very first iteration (subsequent pages always start at
278 * offset 0, which -- like any chunk boundary -- is always
279 * a legitimate entry start, since no rec_len chain crosses
280 * a chunk boundary). Snap a non-chunk-aligned offset onto
281 * a real entry boundary by walking the chain from the
282 * enclosing chunk's start, as ext2 does; otherwise
283 * dir_emit() copies name_len bytes from a fake entry,
284 * reading past the end of the folio.
285 */
286 if (offset & (chunk_size - 1)) {
287 offset = nilfs_validate_entry(kaddr, offset,
288 ~(chunk_size - 1));
289 ctx->pos = ((loff_t)n << PAGE_SHIFT) + offset;
290 }
291 de = (struct nilfs_dir_entry *)(kaddr + offset);
292 limit = kaddr + nilfs_last_byte(inode, n) -
293 NILFS_DIR_REC_LEN(1);
294 for ( ; (char *)de <= limit; de = nilfs_next_entry(de)) {
295 if (de->rec_len == 0) {
296 nilfs_error(sb, "zero-length directory entry");
297 folio_release_kmap(folio, kaddr);
298 return -EIO;
299 }
300 if (de->inode) {
301 unsigned char t;
302
303 t = fs_ftype_to_dtype(de->file_type);
304
305 if (!dir_emit(ctx, de->name, de->name_len,
306 le64_to_cpu(de->inode), t)) {
307 folio_release_kmap(folio, kaddr);
308 return 0;
309 }
310 }
311 ctx->pos += nilfs_rec_len_from_disk(de->rec_len);
312 }
313 folio_release_kmap(folio, kaddr);
314 }
315 return 0;
316}
317
318/*
319 * nilfs_find_entry()
320 *
321 * Finds an entry in the specified directory with the wanted name. It
322 * returns the folio in which the entry was found, and the entry itself.
323 * The folio is mapped and unlocked. When the caller is finished with
324 * the entry, it should call folio_release_kmap().
325 *
326 * On failure, returns an error pointer and the caller should ignore foliop.
327 */
328struct nilfs_dir_entry *nilfs_find_entry(struct inode *dir,
329 const struct qstr *qstr, struct folio **foliop)
330{
331 const unsigned char *name = qstr->name;
332 int namelen = qstr->len;
333 unsigned int reclen = NILFS_DIR_REC_LEN(namelen);
334 unsigned long start, n;
335 unsigned long npages = dir_pages(dir);
336 struct nilfs_inode_info *ei = NILFS_I(dir);
337 struct nilfs_dir_entry *de;
338
339 if (npages == 0)
340 goto out;
341
342 start = ei->i_dir_start_lookup;
343 if (start >= npages)
344 start = 0;
345 n = start;
346 do {
347 char *kaddr = nilfs_get_folio(dir, n, foliop);
348
349 if (IS_ERR(kaddr))
350 return ERR_CAST(kaddr);
351
352 de = (struct nilfs_dir_entry *)kaddr;
353 kaddr += nilfs_last_byte(dir, n) - reclen;
354 while ((char *)de <= kaddr) {
355 if (de->rec_len == 0) {
356 nilfs_error(dir->i_sb,
357 "zero-length directory entry");
358 folio_release_kmap(*foliop, kaddr);
359 goto out;
360 }
361 if (nilfs_match(namelen, name, de))
362 goto found;
363 de = nilfs_next_entry(de);
364 }
365 folio_release_kmap(*foliop, kaddr);
366
367 if (++n >= npages)
368 n = 0;
369 /* next folio is past the blocks we've got */
370 if (unlikely(n > (dir->i_blocks >> (PAGE_SHIFT - 9)))) {
371 nilfs_error(dir->i_sb,
372 "dir %llu size %lld exceeds block count %llu",
373 dir->i_ino, dir->i_size,
374 (unsigned long long)dir->i_blocks);
375 goto out;
376 }
377 } while (n != start);
378out:
379 return ERR_PTR(-ENOENT);
380
381found:
382 ei->i_dir_start_lookup = n;
383 return de;
384}
385
386struct nilfs_dir_entry *nilfs_dotdot(struct inode *dir, struct folio **foliop)
387{
388 struct folio *folio;
389 struct nilfs_dir_entry *de, *next_de;
390 size_t limit;
391 char *msg;
392
393 de = nilfs_get_folio(dir, 0, &folio);
394 if (IS_ERR(de))
395 return NULL;
396
397 limit = nilfs_last_byte(dir, 0); /* is a multiple of chunk size */
398 if (unlikely(!limit || le64_to_cpu(de->inode) != dir->i_ino ||
399 !nilfs_match(1, ".", de))) {
400 msg = "missing '.'";
401 goto fail;
402 }
403
404 next_de = nilfs_next_entry(de);
405 /*
406 * If "next_de" has not reached the end of the chunk, there is
407 * at least one more record. Check whether it matches "..".
408 */
409 if (unlikely((char *)next_de == (char *)de + nilfs_chunk_size(dir) ||
410 !nilfs_match(2, "..", next_de))) {
411 msg = "missing '..'";
412 goto fail;
413 }
414 *foliop = folio;
415 return next_de;
416
417fail:
418 nilfs_error(dir->i_sb, "directory #%llu %s", dir->i_ino, msg);
419 folio_release_kmap(folio, de);
420 return NULL;
421}
422
423int nilfs_inode_by_name(struct inode *dir, const struct qstr *qstr, u64 *ino)
424{
425 struct nilfs_dir_entry *de;
426 struct folio *folio;
427
428 de = nilfs_find_entry(dir, qstr, &folio);
429 if (IS_ERR(de))
430 return PTR_ERR(de);
431
432 *ino = le64_to_cpu(de->inode);
433 folio_release_kmap(folio, de);
434 return 0;
435}
436
437int nilfs_set_link(struct inode *dir, struct nilfs_dir_entry *de,
438 struct folio *folio, struct inode *inode)
439{
440 size_t from = offset_in_folio(folio, de);
441 size_t to = from + nilfs_rec_len_from_disk(de->rec_len);
442 struct address_space *mapping = folio->mapping;
443 int err;
444
445 folio_lock(folio);
446 err = nilfs_prepare_chunk(folio, from, to);
447 if (unlikely(err)) {
448 folio_unlock(folio);
449 return err;
450 }
451 de->inode = cpu_to_le64(inode->i_ino);
452 de->file_type = fs_umode_to_ftype(inode->i_mode);
453 nilfs_commit_chunk(folio, mapping, from, to);
454 inode_set_mtime_to_ts(dir, inode_set_ctime_current(dir));
455 return 0;
456}
457
458/*
459 * Parent is locked.
460 */
461int nilfs_add_link(struct dentry *dentry, struct inode *inode)
462{
463 struct inode *dir = d_inode(dentry->d_parent);
464 const unsigned char *name = dentry->d_name.name;
465 int namelen = dentry->d_name.len;
466 unsigned int chunk_size = nilfs_chunk_size(dir);
467 unsigned int reclen = NILFS_DIR_REC_LEN(namelen);
468 unsigned short rec_len, name_len;
469 struct folio *folio = NULL;
470 struct nilfs_dir_entry *de;
471 unsigned long npages = dir_pages(dir);
472 unsigned long n;
473 size_t from, to;
474 int err;
475
476 /*
477 * We take care of directory expansion in the same loop.
478 * This code plays outside i_size, so it locks the folio
479 * to protect that region.
480 */
481 for (n = 0; n <= npages; n++) {
482 char *kaddr = nilfs_get_folio(dir, n, &folio);
483 char *dir_end;
484
485 if (IS_ERR(kaddr))
486 return PTR_ERR(kaddr);
487 folio_lock(folio);
488 dir_end = kaddr + nilfs_last_byte(dir, n);
489 de = (struct nilfs_dir_entry *)kaddr;
490 kaddr += folio_size(folio) - reclen;
491 while ((char *)de <= kaddr) {
492 if ((char *)de == dir_end) {
493 /* We hit i_size */
494 name_len = 0;
495 rec_len = chunk_size;
496 de->rec_len = nilfs_rec_len_to_disk(chunk_size);
497 de->inode = 0;
498 goto got_it;
499 }
500 if (de->rec_len == 0) {
501 nilfs_error(dir->i_sb,
502 "zero-length directory entry");
503 err = -EIO;
504 goto out_unlock;
505 }
506 err = -EEXIST;
507 if (nilfs_match(namelen, name, de))
508 goto out_unlock;
509 name_len = NILFS_DIR_REC_LEN(de->name_len);
510 rec_len = nilfs_rec_len_from_disk(de->rec_len);
511 if (!de->inode && rec_len >= reclen)
512 goto got_it;
513 if (rec_len >= name_len + reclen)
514 goto got_it;
515 de = (struct nilfs_dir_entry *)((char *)de + rec_len);
516 }
517 folio_unlock(folio);
518 folio_release_kmap(folio, kaddr);
519 }
520 BUG();
521 return -EINVAL;
522
523got_it:
524 from = offset_in_folio(folio, de);
525 to = from + rec_len;
526 err = nilfs_prepare_chunk(folio, from, to);
527 if (err)
528 goto out_unlock;
529 if (de->inode) {
530 struct nilfs_dir_entry *de1;
531
532 de1 = (struct nilfs_dir_entry *)((char *)de + name_len);
533 de1->rec_len = nilfs_rec_len_to_disk(rec_len - name_len);
534 de->rec_len = nilfs_rec_len_to_disk(name_len);
535 de = de1;
536 }
537 de->name_len = namelen;
538 memcpy(de->name, name, namelen);
539 de->inode = cpu_to_le64(inode->i_ino);
540 de->file_type = fs_umode_to_ftype(inode->i_mode);
541 nilfs_commit_chunk(folio, folio->mapping, from, to);
542 inode_set_mtime_to_ts(dir, inode_set_ctime_current(dir));
543 nilfs_mark_inode_dirty(dir);
544 /* OFFSET_CACHE */
545out_put:
546 folio_release_kmap(folio, de);
547 return err;
548out_unlock:
549 folio_unlock(folio);
550 goto out_put;
551}
552
553/*
554 * nilfs_delete_entry deletes a directory entry by merging it with the
555 * previous entry. Folio is up-to-date.
556 */
557int nilfs_delete_entry(struct nilfs_dir_entry *dir, struct folio *folio)
558{
559 struct address_space *mapping = folio->mapping;
560 struct inode *inode = mapping->host;
561 char *kaddr = (char *)((unsigned long)dir & ~(folio_size(folio) - 1));
562 size_t from, to;
563 struct nilfs_dir_entry *de, *pde = NULL;
564 int err;
565
566 from = ((char *)dir - kaddr) & ~(nilfs_chunk_size(inode) - 1);
567 to = ((char *)dir - kaddr) + nilfs_rec_len_from_disk(dir->rec_len);
568 de = (struct nilfs_dir_entry *)(kaddr + from);
569
570 while ((char *)de < (char *)dir) {
571 if (de->rec_len == 0) {
572 nilfs_error(inode->i_sb,
573 "zero-length directory entry");
574 err = -EIO;
575 goto out;
576 }
577 pde = de;
578 de = nilfs_next_entry(de);
579 }
580 if (pde)
581 from = (char *)pde - kaddr;
582 folio_lock(folio);
583 err = nilfs_prepare_chunk(folio, from, to);
584 if (unlikely(err)) {
585 folio_unlock(folio);
586 goto out;
587 }
588 if (pde)
589 pde->rec_len = nilfs_rec_len_to_disk(to - from);
590 dir->inode = 0;
591 nilfs_commit_chunk(folio, mapping, from, to);
592 inode_set_mtime_to_ts(inode, inode_set_ctime_current(inode));
593out:
594 return err;
595}
596
597/*
598 * Set the first fragment of directory.
599 */
600int nilfs_make_empty(struct inode *inode, struct inode *parent)
601{
602 struct address_space *mapping = inode->i_mapping;
603 struct folio *folio = filemap_grab_folio(mapping, 0);
604 unsigned int chunk_size = nilfs_chunk_size(inode);
605 struct nilfs_dir_entry *de;
606 int err;
607 void *kaddr;
608
609 if (IS_ERR(folio))
610 return PTR_ERR(folio);
611
612 err = nilfs_prepare_chunk(folio, 0, chunk_size);
613 if (unlikely(err)) {
614 folio_unlock(folio);
615 goto fail;
616 }
617 kaddr = kmap_local_folio(folio, 0);
618 memset(kaddr, 0, chunk_size);
619 de = (struct nilfs_dir_entry *)kaddr;
620 de->name_len = 1;
621 de->rec_len = nilfs_rec_len_to_disk(NILFS_DIR_REC_LEN(1));
622 memcpy(de->name, ".\0\0", 4);
623 de->inode = cpu_to_le64(inode->i_ino);
624 de->file_type = fs_umode_to_ftype(inode->i_mode);
625
626 de = (struct nilfs_dir_entry *)(kaddr + NILFS_DIR_REC_LEN(1));
627 de->name_len = 2;
628 de->rec_len = nilfs_rec_len_to_disk(chunk_size - NILFS_DIR_REC_LEN(1));
629 de->inode = cpu_to_le64(parent->i_ino);
630 memcpy(de->name, "..\0", 4);
631 de->file_type = fs_umode_to_ftype(inode->i_mode);
632 kunmap_local(kaddr);
633 nilfs_commit_chunk(folio, mapping, 0, chunk_size);
634fail:
635 folio_put(folio);
636 return err;
637}
638
639/*
640 * routine to check that the specified directory is empty (for rmdir)
641 */
642int nilfs_empty_dir(struct inode *inode)
643{
644 struct folio *folio = NULL;
645 char *kaddr;
646 unsigned long i, npages = dir_pages(inode);
647
648 for (i = 0; i < npages; i++) {
649 struct nilfs_dir_entry *de;
650
651 kaddr = nilfs_get_folio(inode, i, &folio);
652 if (IS_ERR(kaddr))
653 return 0;
654
655 de = (struct nilfs_dir_entry *)kaddr;
656 kaddr += nilfs_last_byte(inode, i) - NILFS_DIR_REC_LEN(1);
657
658 while ((char *)de <= kaddr) {
659 if (de->rec_len == 0) {
660 nilfs_error(inode->i_sb,
661 "zero-length directory entry (kaddr=%p, de=%p)",
662 kaddr, de);
663 goto not_empty;
664 }
665 if (de->inode != 0) {
666 /* check for . and .. */
667 if (de->name[0] != '.')
668 goto not_empty;
669 if (de->name_len > 2)
670 goto not_empty;
671 if (de->name_len < 2) {
672 if (de->inode !=
673 cpu_to_le64(inode->i_ino))
674 goto not_empty;
675 } else if (de->name[1] != '.')
676 goto not_empty;
677 }
678 de = nilfs_next_entry(de);
679 }
680 folio_release_kmap(folio, kaddr);
681 }
682 return 1;
683
684not_empty:
685 folio_release_kmap(folio, kaddr);
686 return 0;
687}
688
689const struct file_operations nilfs_dir_operations = {
690 .llseek = generic_file_llseek,
691 .read = generic_read_dir,
692 .iterate_shared = nilfs_readdir,
693 .unlocked_ioctl = nilfs_ioctl,
694#ifdef CONFIG_COMPAT
695 .compat_ioctl = nilfs_compat_ioctl,
696#endif /* CONFIG_COMPAT */
697 .fsync = nilfs_sync_file,
698 .setlease = generic_setlease,
699};