1 // SPDX-License-Identifier: GPL-2.0
5 * Copyright (C) 1992, 1993, 1994, 1995
6 * Remy Card (card@masi.ibp.fr)
7 * Laboratoire MASI - Institut Blaise Pascal
8 * Universite Pierre et Marie Curie (Paris VI)
12 * linux/fs/minix/dir.c
14 * Copyright (C) 1991, 1992 Linus Torvalds
16 * ext2 directory handling functions
18 * Big-endian to little-endian byte-swapping/bitmaps by
19 * David S. Miller (davem@caip.rutgers.edu), 1995
21 * All code that works with directory layout had been switched to pagecache
26 #include <linux/buffer_head.h>
27 #include <linux/pagemap.h>
28 #include <linux/swap.h>
29 #include <linux/iversion.h>
31 typedef struct ext2_dir_entry_2 ext2_dirent
;
34 * Tests against MAX_REC_LEN etc were put in place for 64k block
35 * sizes; if that is not possible on this arch, we can skip
36 * those tests and speed things up.
38 static inline unsigned ext2_rec_len_from_disk(__le16 dlen
)
40 unsigned len
= le16_to_cpu(dlen
);
42 #if (PAGE_SIZE >= 65536)
43 if (len
== EXT2_MAX_REC_LEN
)
49 static inline __le16
ext2_rec_len_to_disk(unsigned len
)
51 #if (PAGE_SIZE >= 65536)
53 return cpu_to_le16(EXT2_MAX_REC_LEN
);
55 BUG_ON(len
> (1 << 16));
57 return cpu_to_le16(len
);
61 * ext2 uses block-sized chunks. Arguably, sector-sized ones would be
62 * more robust, but we have what we have
64 static inline unsigned ext2_chunk_size(struct inode
*inode
)
66 return inode
->i_sb
->s_blocksize
;
70 * Return the offset into page `page_nr' of the last valid
71 * byte in that page, plus one.
74 ext2_last_byte(struct inode
*inode
, unsigned long page_nr
)
76 unsigned last_byte
= inode
->i_size
;
78 last_byte
-= page_nr
<< PAGE_SHIFT
;
79 if (last_byte
> PAGE_SIZE
)
80 last_byte
= PAGE_SIZE
;
84 static int ext2_commit_chunk(struct page
*page
, loff_t pos
, unsigned len
)
86 struct address_space
*mapping
= page
->mapping
;
87 struct inode
*dir
= mapping
->host
;
90 inode_inc_iversion(dir
);
91 block_write_end(NULL
, mapping
, pos
, len
, len
, page
, NULL
);
93 if (pos
+len
> dir
->i_size
) {
94 i_size_write(dir
, pos
+len
);
95 mark_inode_dirty(dir
);
98 if (IS_DIRSYNC(dir
)) {
99 err
= write_one_page(page
);
101 err
= sync_inode_metadata(dir
, 1);
109 static bool ext2_check_page(struct page
*page
, int quiet
, char *kaddr
)
111 struct inode
*dir
= page
->mapping
->host
;
112 struct super_block
*sb
= dir
->i_sb
;
113 unsigned chunk_size
= ext2_chunk_size(dir
);
114 u32 max_inumber
= le32_to_cpu(EXT2_SB(sb
)->s_es
->s_inodes_count
);
115 unsigned offs
, rec_len
;
116 unsigned limit
= PAGE_SIZE
;
120 if ((dir
->i_size
>> PAGE_SHIFT
) == page
->index
) {
121 limit
= dir
->i_size
& ~PAGE_MASK
;
122 if (limit
& (chunk_size
- 1))
127 for (offs
= 0; offs
<= limit
- EXT2_DIR_REC_LEN(1); offs
+= rec_len
) {
128 p
= (ext2_dirent
*)(kaddr
+ offs
);
129 rec_len
= ext2_rec_len_from_disk(p
->rec_len
);
131 if (unlikely(rec_len
< EXT2_DIR_REC_LEN(1)))
133 if (unlikely(rec_len
& 3))
135 if (unlikely(rec_len
< EXT2_DIR_REC_LEN(p
->name_len
)))
137 if (unlikely(((offs
+ rec_len
- 1) ^ offs
) & ~(chunk_size
-1)))
139 if (unlikely(le32_to_cpu(p
->inode
) > max_inumber
))
145 SetPageChecked(page
);
148 /* Too bad, we had an error */
152 ext2_error(sb
, __func__
,
153 "size of directory #%lu is not a multiple "
154 "of chunk size", dir
->i_ino
);
157 error
= "rec_len is smaller than minimal";
160 error
= "unaligned directory entry";
163 error
= "rec_len is too small for name_len";
166 error
= "directory entry across blocks";
169 error
= "inode out of bounds";
172 ext2_error(sb
, __func__
, "bad entry in directory #%lu: : %s - "
173 "offset=%lu, inode=%lu, rec_len=%d, name_len=%d",
174 dir
->i_ino
, error
, (page
->index
<<PAGE_SHIFT
)+offs
,
175 (unsigned long) le32_to_cpu(p
->inode
),
176 rec_len
, p
->name_len
);
180 p
= (ext2_dirent
*)(kaddr
+ offs
);
181 ext2_error(sb
, "ext2_check_page",
182 "entry in directory #%lu spans the page boundary"
183 "offset=%lu, inode=%lu",
184 dir
->i_ino
, (page
->index
<<PAGE_SHIFT
)+offs
,
185 (unsigned long) le32_to_cpu(p
->inode
));
193 * Calls to ext2_get_page()/ext2_put_page() must be nested according to the
194 * rules documented in kmap_local_page()/kunmap_local().
196 * NOTE: ext2_find_entry() and ext2_dotdot() act as a call to ext2_get_page()
197 * and should be treated as a call to ext2_get_page() for nesting purposes.
199 static struct page
* ext2_get_page(struct inode
*dir
, unsigned long n
,
200 int quiet
, void **page_addr
)
202 struct address_space
*mapping
= dir
->i_mapping
;
203 struct page
*page
= read_mapping_page(mapping
, n
, NULL
);
205 *page_addr
= kmap_local_page(page
);
206 if (unlikely(!PageChecked(page
))) {
207 if (PageError(page
) || !ext2_check_page(page
, quiet
,
215 ext2_put_page(page
, *page_addr
);
216 return ERR_PTR(-EIO
);
220 * NOTE! unlike strncmp, ext2_match returns 1 for success, 0 for failure.
222 * len <= EXT2_NAME_LEN and de != NULL are guaranteed by caller.
224 static inline int ext2_match (int len
, const char * const name
,
225 struct ext2_dir_entry_2
* de
)
227 if (len
!= de
->name_len
)
231 return !memcmp(name
, de
->name
, len
);
235 * p is at least 6 bytes before the end of page
237 static inline ext2_dirent
*ext2_next_entry(ext2_dirent
*p
)
239 return (ext2_dirent
*)((char *)p
+
240 ext2_rec_len_from_disk(p
->rec_len
));
243 static inline unsigned
244 ext2_validate_entry(char *base
, unsigned offset
, unsigned mask
)
246 ext2_dirent
*de
= (ext2_dirent
*)(base
+ offset
);
247 ext2_dirent
*p
= (ext2_dirent
*)(base
+ (offset
&mask
));
248 while ((char*)p
< (char*)de
) {
251 p
= ext2_next_entry(p
);
253 return (char *)p
- base
;
256 static inline void ext2_set_de_type(ext2_dirent
*de
, struct inode
*inode
)
258 if (EXT2_HAS_INCOMPAT_FEATURE(inode
->i_sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
))
259 de
->file_type
= fs_umode_to_ftype(inode
->i_mode
);
265 ext2_readdir(struct file
*file
, struct dir_context
*ctx
)
267 loff_t pos
= ctx
->pos
;
268 struct inode
*inode
= file_inode(file
);
269 struct super_block
*sb
= inode
->i_sb
;
270 unsigned int offset
= pos
& ~PAGE_MASK
;
271 unsigned long n
= pos
>> PAGE_SHIFT
;
272 unsigned long npages
= dir_pages(inode
);
273 unsigned chunk_mask
= ~(ext2_chunk_size(inode
)-1);
274 bool need_revalidate
= !inode_eq_iversion(inode
, file
->f_version
);
277 if (pos
> inode
->i_size
- EXT2_DIR_REC_LEN(1))
281 EXT2_HAS_INCOMPAT_FEATURE(sb
, EXT2_FEATURE_INCOMPAT_FILETYPE
);
283 for ( ; n
< npages
; n
++, offset
= 0) {
286 struct page
*page
= ext2_get_page(inode
, n
, 0, (void **)&kaddr
);
289 ext2_error(sb
, __func__
,
292 ctx
->pos
+= PAGE_SIZE
- offset
;
293 return PTR_ERR(page
);
295 if (unlikely(need_revalidate
)) {
297 offset
= ext2_validate_entry(kaddr
, offset
, chunk_mask
);
298 ctx
->pos
= (n
<<PAGE_SHIFT
) + offset
;
300 file
->f_version
= inode_query_iversion(inode
);
301 need_revalidate
= false;
303 de
= (ext2_dirent
*)(kaddr
+offset
);
304 limit
= kaddr
+ ext2_last_byte(inode
, n
) - EXT2_DIR_REC_LEN(1);
305 for ( ;(char*)de
<= limit
; de
= ext2_next_entry(de
)) {
306 if (de
->rec_len
== 0) {
307 ext2_error(sb
, __func__
,
308 "zero-length directory entry");
309 ext2_put_page(page
, kaddr
);
313 unsigned char d_type
= DT_UNKNOWN
;
316 d_type
= fs_ftype_to_dtype(de
->file_type
);
318 if (!dir_emit(ctx
, de
->name
, de
->name_len
,
319 le32_to_cpu(de
->inode
),
321 ext2_put_page(page
, kaddr
);
325 ctx
->pos
+= ext2_rec_len_from_disk(de
->rec_len
);
327 ext2_put_page(page
, kaddr
);
335 * finds an entry in the specified directory with the wanted name. It
336 * returns the page in which the entry was found (as a parameter - res_page),
337 * and the entry itself. Page is returned mapped and unlocked.
338 * Entry is guaranteed to be valid.
340 * On Success ext2_put_page() should be called on *res_page.
342 * NOTE: Calls to ext2_get_page()/ext2_put_page() must be nested according to
343 * the rules documented in kmap_local_page()/kunmap_local().
345 * ext2_find_entry() and ext2_dotdot() act as a call to ext2_get_page() and
346 * should be treated as a call to ext2_get_page() for nesting purposes.
348 struct ext2_dir_entry_2
*ext2_find_entry (struct inode
*dir
,
349 const struct qstr
*child
, struct page
**res_page
,
350 void **res_page_addr
)
352 const char *name
= child
->name
;
353 int namelen
= child
->len
;
354 unsigned reclen
= EXT2_DIR_REC_LEN(namelen
);
355 unsigned long start
, n
;
356 unsigned long npages
= dir_pages(dir
);
357 struct page
*page
= NULL
;
358 struct ext2_inode_info
*ei
= EXT2_I(dir
);
367 *res_page_addr
= NULL
;
369 start
= ei
->i_dir_start_lookup
;
375 page
= ext2_get_page(dir
, n
, 0, &page_addr
);
377 return ERR_CAST(page
);
380 de
= (ext2_dirent
*) kaddr
;
381 kaddr
+= ext2_last_byte(dir
, n
) - reclen
;
382 while ((char *) de
<= kaddr
) {
383 if (de
->rec_len
== 0) {
384 ext2_error(dir
->i_sb
, __func__
,
385 "zero-length directory entry");
386 ext2_put_page(page
, page_addr
);
389 if (ext2_match(namelen
, name
, de
))
391 de
= ext2_next_entry(de
);
393 ext2_put_page(page
, page_addr
);
397 /* next page is past the blocks we've got */
398 if (unlikely(n
> (dir
->i_blocks
>> (PAGE_SHIFT
- 9)))) {
399 ext2_error(dir
->i_sb
, __func__
,
400 "dir %lu size %lld exceeds block count %llu",
401 dir
->i_ino
, dir
->i_size
,
402 (unsigned long long)dir
->i_blocks
);
405 } while (n
!= start
);
407 return ERR_PTR(-ENOENT
);
411 *res_page_addr
= page_addr
;
412 ei
->i_dir_start_lookup
= n
;
417 * Return the '..' directory entry and the page in which the entry was found
418 * (as a parameter - p).
420 * On Success ext2_put_page() should be called on *p.
422 * NOTE: Calls to ext2_get_page()/ext2_put_page() must be nested according to
423 * the rules documented in kmap_local_page()/kunmap_local().
425 * ext2_find_entry() and ext2_dotdot() act as a call to ext2_get_page() and
426 * should be treated as a call to ext2_get_page() for nesting purposes.
428 struct ext2_dir_entry_2
*ext2_dotdot(struct inode
*dir
, struct page
**p
,
432 struct page
*page
= ext2_get_page(dir
, 0, 0, &page_addr
);
433 ext2_dirent
*de
= NULL
;
436 de
= ext2_next_entry((ext2_dirent
*) page_addr
);
443 int ext2_inode_by_name(struct inode
*dir
, const struct qstr
*child
, ino_t
*ino
)
445 struct ext2_dir_entry_2
*de
;
449 de
= ext2_find_entry(dir
, child
, &page
, &page_addr
);
453 *ino
= le32_to_cpu(de
->inode
);
454 ext2_put_page(page
, page_addr
);
458 static int ext2_prepare_chunk(struct page
*page
, loff_t pos
, unsigned len
)
460 return __block_write_begin(page
, pos
, len
, ext2_get_block
);
463 void ext2_set_link(struct inode
*dir
, struct ext2_dir_entry_2
*de
,
464 struct page
*page
, void *page_addr
, struct inode
*inode
,
467 loff_t pos
= page_offset(page
) +
468 (char *) de
- (char *) page_addr
;
469 unsigned len
= ext2_rec_len_from_disk(de
->rec_len
);
473 err
= ext2_prepare_chunk(page
, pos
, len
);
475 de
->inode
= cpu_to_le32(inode
->i_ino
);
476 ext2_set_de_type(de
, inode
);
477 err
= ext2_commit_chunk(page
, pos
, len
);
479 dir
->i_mtime
= dir
->i_ctime
= current_time(dir
);
480 EXT2_I(dir
)->i_flags
&= ~EXT2_BTREE_FL
;
481 mark_inode_dirty(dir
);
487 int ext2_add_link (struct dentry
*dentry
, struct inode
*inode
)
489 struct inode
*dir
= d_inode(dentry
->d_parent
);
490 const char *name
= dentry
->d_name
.name
;
491 int namelen
= dentry
->d_name
.len
;
492 unsigned chunk_size
= ext2_chunk_size(dir
);
493 unsigned reclen
= EXT2_DIR_REC_LEN(namelen
);
494 unsigned short rec_len
, name_len
;
495 struct page
*page
= NULL
;
496 void *page_addr
= NULL
;
498 unsigned long npages
= dir_pages(dir
);
504 * We take care of directory expansion in the same loop.
505 * This code plays outside i_size, so it locks the page
506 * to protect that region.
508 for (n
= 0; n
<= npages
; n
++) {
512 page
= ext2_get_page(dir
, n
, 0, &page_addr
);
518 dir_end
= kaddr
+ ext2_last_byte(dir
, n
);
519 de
= (ext2_dirent
*)kaddr
;
520 kaddr
+= PAGE_SIZE
- reclen
;
521 while ((char *)de
<= kaddr
) {
522 if ((char *)de
== dir_end
) {
525 rec_len
= chunk_size
;
526 de
->rec_len
= ext2_rec_len_to_disk(chunk_size
);
530 if (de
->rec_len
== 0) {
531 ext2_error(dir
->i_sb
, __func__
,
532 "zero-length directory entry");
537 if (ext2_match (namelen
, name
, de
))
539 name_len
= EXT2_DIR_REC_LEN(de
->name_len
);
540 rec_len
= ext2_rec_len_from_disk(de
->rec_len
);
541 if (!de
->inode
&& rec_len
>= reclen
)
543 if (rec_len
>= name_len
+ reclen
)
545 de
= (ext2_dirent
*) ((char *) de
+ rec_len
);
548 ext2_put_page(page
, page_addr
);
554 pos
= page_offset(page
) +
555 (char *)de
- (char *)page_addr
;
556 err
= ext2_prepare_chunk(page
, pos
, rec_len
);
560 ext2_dirent
*de1
= (ext2_dirent
*) ((char *) de
+ name_len
);
561 de1
->rec_len
= ext2_rec_len_to_disk(rec_len
- name_len
);
562 de
->rec_len
= ext2_rec_len_to_disk(name_len
);
565 de
->name_len
= namelen
;
566 memcpy(de
->name
, name
, namelen
);
567 de
->inode
= cpu_to_le32(inode
->i_ino
);
568 ext2_set_de_type (de
, inode
);
569 err
= ext2_commit_chunk(page
, pos
, rec_len
);
570 dir
->i_mtime
= dir
->i_ctime
= current_time(dir
);
571 EXT2_I(dir
)->i_flags
&= ~EXT2_BTREE_FL
;
572 mark_inode_dirty(dir
);
575 ext2_put_page(page
, page_addr
);
584 * ext2_delete_entry deletes a directory entry by merging it with the
585 * previous entry. Page is up-to-date.
587 int ext2_delete_entry (struct ext2_dir_entry_2
*dir
, struct page
*page
,
590 struct inode
*inode
= page
->mapping
->host
;
591 unsigned from
= ((char*)dir
- kaddr
) & ~(ext2_chunk_size(inode
)-1);
592 unsigned to
= ((char *)dir
- kaddr
) +
593 ext2_rec_len_from_disk(dir
->rec_len
);
595 ext2_dirent
* pde
= NULL
;
596 ext2_dirent
* de
= (ext2_dirent
*) (kaddr
+ from
);
599 while ((char*)de
< (char*)dir
) {
600 if (de
->rec_len
== 0) {
601 ext2_error(inode
->i_sb
, __func__
,
602 "zero-length directory entry");
607 de
= ext2_next_entry(de
);
610 from
= (char *)pde
- kaddr
;
611 pos
= page_offset(page
) + from
;
613 err
= ext2_prepare_chunk(page
, pos
, to
- from
);
616 pde
->rec_len
= ext2_rec_len_to_disk(to
- from
);
618 err
= ext2_commit_chunk(page
, pos
, to
- from
);
619 inode
->i_ctime
= inode
->i_mtime
= current_time(inode
);
620 EXT2_I(inode
)->i_flags
&= ~EXT2_BTREE_FL
;
621 mark_inode_dirty(inode
);
627 * Set the first fragment of directory.
629 int ext2_make_empty(struct inode
*inode
, struct inode
*parent
)
631 struct page
*page
= grab_cache_page(inode
->i_mapping
, 0);
632 unsigned chunk_size
= ext2_chunk_size(inode
);
633 struct ext2_dir_entry_2
* de
;
640 err
= ext2_prepare_chunk(page
, 0, chunk_size
);
645 kaddr
= kmap_atomic(page
);
646 memset(kaddr
, 0, chunk_size
);
647 de
= (struct ext2_dir_entry_2
*)kaddr
;
649 de
->rec_len
= ext2_rec_len_to_disk(EXT2_DIR_REC_LEN(1));
650 memcpy (de
->name
, ".\0\0", 4);
651 de
->inode
= cpu_to_le32(inode
->i_ino
);
652 ext2_set_de_type (de
, inode
);
654 de
= (struct ext2_dir_entry_2
*)(kaddr
+ EXT2_DIR_REC_LEN(1));
656 de
->rec_len
= ext2_rec_len_to_disk(chunk_size
- EXT2_DIR_REC_LEN(1));
657 de
->inode
= cpu_to_le32(parent
->i_ino
);
658 memcpy (de
->name
, "..\0", 4);
659 ext2_set_de_type (de
, inode
);
660 kunmap_atomic(kaddr
);
661 err
= ext2_commit_chunk(page
, 0, chunk_size
);
668 * routine to check that the specified directory is empty (for rmdir)
670 int ext2_empty_dir (struct inode
* inode
)
672 void *page_addr
= NULL
;
673 struct page
*page
= NULL
;
674 unsigned long i
, npages
= dir_pages(inode
);
675 int dir_has_error
= 0;
677 for (i
= 0; i
< npages
; i
++) {
680 page
= ext2_get_page(inode
, i
, dir_has_error
, &page_addr
);
688 de
= (ext2_dirent
*)kaddr
;
689 kaddr
+= ext2_last_byte(inode
, i
) - EXT2_DIR_REC_LEN(1);
691 while ((char *)de
<= kaddr
) {
692 if (de
->rec_len
== 0) {
693 ext2_error(inode
->i_sb
, __func__
,
694 "zero-length directory entry");
695 printk("kaddr=%p, de=%p\n", kaddr
, de
);
698 if (de
->inode
!= 0) {
699 /* check for . and .. */
700 if (de
->name
[0] != '.')
702 if (de
->name_len
> 2)
704 if (de
->name_len
< 2) {
706 cpu_to_le32(inode
->i_ino
))
708 } else if (de
->name
[1] != '.')
711 de
= ext2_next_entry(de
);
713 ext2_put_page(page
, page_addr
);
718 ext2_put_page(page
, page_addr
);
722 const struct file_operations ext2_dir_operations
= {
723 .llseek
= generic_file_llseek
,
724 .read
= generic_read_dir
,
725 .iterate_shared
= ext2_readdir
,
726 .unlocked_ioctl
= ext2_ioctl
,
728 .compat_ioctl
= ext2_compat_ioctl
,