4 * Copyright (c) 2012 Samsung Electronics Co., Ltd.
5 * http://www.samsung.com/
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License version 2 as
9 * published by the Free Software Foundation.
12 #include <linux/f2fs_fs.h>
18 static unsigned long dir_blocks(struct inode
*inode
)
20 return ((unsigned long long) (i_size_read(inode
) + PAGE_CACHE_SIZE
- 1))
24 static unsigned int dir_buckets(unsigned int level
, int dir_level
)
26 if (level
< MAX_DIR_HASH_DEPTH
/ 2)
27 return 1 << (level
+ dir_level
);
29 return 1 << ((MAX_DIR_HASH_DEPTH
/ 2 + dir_level
) - 1);
32 static unsigned int bucket_blocks(unsigned int level
)
34 if (level
< MAX_DIR_HASH_DEPTH
/ 2)
40 static unsigned char f2fs_filetype_table
[F2FS_FT_MAX
] = {
41 [F2FS_FT_UNKNOWN
] = DT_UNKNOWN
,
42 [F2FS_FT_REG_FILE
] = DT_REG
,
43 [F2FS_FT_DIR
] = DT_DIR
,
44 [F2FS_FT_CHRDEV
] = DT_CHR
,
45 [F2FS_FT_BLKDEV
] = DT_BLK
,
46 [F2FS_FT_FIFO
] = DT_FIFO
,
47 [F2FS_FT_SOCK
] = DT_SOCK
,
48 [F2FS_FT_SYMLINK
] = DT_LNK
,
52 static unsigned char f2fs_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
53 [S_IFREG
>> S_SHIFT
] = F2FS_FT_REG_FILE
,
54 [S_IFDIR
>> S_SHIFT
] = F2FS_FT_DIR
,
55 [S_IFCHR
>> S_SHIFT
] = F2FS_FT_CHRDEV
,
56 [S_IFBLK
>> S_SHIFT
] = F2FS_FT_BLKDEV
,
57 [S_IFIFO
>> S_SHIFT
] = F2FS_FT_FIFO
,
58 [S_IFSOCK
>> S_SHIFT
] = F2FS_FT_SOCK
,
59 [S_IFLNK
>> S_SHIFT
] = F2FS_FT_SYMLINK
,
62 static void set_de_type(struct f2fs_dir_entry
*de
, struct inode
*inode
)
64 umode_t mode
= inode
->i_mode
;
65 de
->file_type
= f2fs_type_by_mode
[(mode
& S_IFMT
) >> S_SHIFT
];
68 static unsigned long dir_block_index(unsigned int level
,
69 int dir_level
, unsigned int idx
)
72 unsigned long bidx
= 0;
74 for (i
= 0; i
< level
; i
++)
75 bidx
+= dir_buckets(i
, dir_level
) * bucket_blocks(i
);
76 bidx
+= idx
* bucket_blocks(level
);
80 static bool early_match_name(const char *name
, size_t namelen
,
81 f2fs_hash_t namehash
, struct f2fs_dir_entry
*de
)
83 if (le16_to_cpu(de
->name_len
) != namelen
)
86 if (de
->hash_code
!= namehash
)
92 static struct f2fs_dir_entry
*find_in_block(struct page
*dentry_page
,
93 const char *name
, size_t namelen
, int *max_slots
,
94 f2fs_hash_t namehash
, struct page
**res_page
)
96 struct f2fs_dir_entry
*de
;
97 unsigned long bit_pos
= 0;
98 struct f2fs_dentry_block
*dentry_blk
= kmap(dentry_page
);
99 const void *dentry_bits
= &dentry_blk
->dentry_bitmap
;
102 while (bit_pos
< NR_DENTRY_IN_BLOCK
) {
103 if (!test_bit_le(bit_pos
, dentry_bits
)) {
106 else if (!test_bit_le(bit_pos
- 1, dentry_bits
))
111 de
= &dentry_blk
->dentry
[bit_pos
];
112 if (early_match_name(name
, namelen
, namehash
, de
)) {
113 if (!memcmp(dentry_blk
->filename
[bit_pos
],
115 *res_page
= dentry_page
;
119 if (max_len
> *max_slots
) {
120 *max_slots
= max_len
;
123 bit_pos
+= GET_DENTRY_SLOTS(le16_to_cpu(de
->name_len
));
129 if (max_len
> *max_slots
)
130 *max_slots
= max_len
;
134 static struct f2fs_dir_entry
*find_in_level(struct inode
*dir
,
135 unsigned int level
, const char *name
, size_t namelen
,
136 f2fs_hash_t namehash
, struct page
**res_page
)
138 int s
= GET_DENTRY_SLOTS(namelen
);
139 unsigned int nbucket
, nblock
;
140 unsigned int bidx
, end_block
;
141 struct page
*dentry_page
;
142 struct f2fs_dir_entry
*de
= NULL
;
146 f2fs_bug_on(level
> MAX_DIR_HASH_DEPTH
);
148 nbucket
= dir_buckets(level
, F2FS_I(dir
)->i_dir_level
);
149 nblock
= bucket_blocks(level
);
151 bidx
= dir_block_index(level
, F2FS_I(dir
)->i_dir_level
,
152 le32_to_cpu(namehash
) % nbucket
);
153 end_block
= bidx
+ nblock
;
155 for (; bidx
< end_block
; bidx
++) {
156 /* no need to allocate new dentry pages to all the indices */
157 dentry_page
= find_data_page(dir
, bidx
, true);
158 if (IS_ERR(dentry_page
)) {
163 de
= find_in_block(dentry_page
, name
, namelen
,
164 &max_slots
, namehash
, res_page
);
170 f2fs_put_page(dentry_page
, 0);
173 if (!de
&& room
&& F2FS_I(dir
)->chash
!= namehash
) {
174 F2FS_I(dir
)->chash
= namehash
;
175 F2FS_I(dir
)->clevel
= level
;
182 * Find an entry in the specified directory with the wanted name.
183 * It returns the page where the entry was found (as a parameter - res_page),
184 * and the entry itself. Page is returned mapped and unlocked.
185 * Entry is guaranteed to be valid.
187 struct f2fs_dir_entry
*f2fs_find_entry(struct inode
*dir
,
188 struct qstr
*child
, struct page
**res_page
)
190 const char *name
= child
->name
;
191 size_t namelen
= child
->len
;
192 unsigned long npages
= dir_blocks(dir
);
193 struct f2fs_dir_entry
*de
= NULL
;
194 f2fs_hash_t name_hash
;
195 unsigned int max_depth
;
203 name_hash
= f2fs_dentry_hash(name
, namelen
);
204 max_depth
= F2FS_I(dir
)->i_current_depth
;
206 for (level
= 0; level
< max_depth
; level
++) {
207 de
= find_in_level(dir
, level
, name
,
208 namelen
, name_hash
, res_page
);
212 if (!de
&& F2FS_I(dir
)->chash
!= name_hash
) {
213 F2FS_I(dir
)->chash
= name_hash
;
214 F2FS_I(dir
)->clevel
= level
- 1;
219 struct f2fs_dir_entry
*f2fs_parent_dir(struct inode
*dir
, struct page
**p
)
222 struct f2fs_dir_entry
*de
;
223 struct f2fs_dentry_block
*dentry_blk
;
225 page
= get_lock_data_page(dir
, 0);
229 dentry_blk
= kmap(page
);
230 de
= &dentry_blk
->dentry
[1];
236 ino_t
f2fs_inode_by_name(struct inode
*dir
, struct qstr
*qstr
)
239 struct f2fs_dir_entry
*de
;
242 de
= f2fs_find_entry(dir
, qstr
, &page
);
244 res
= le32_to_cpu(de
->ino
);
246 f2fs_put_page(page
, 0);
252 void f2fs_set_link(struct inode
*dir
, struct f2fs_dir_entry
*de
,
253 struct page
*page
, struct inode
*inode
)
256 f2fs_wait_on_page_writeback(page
, DATA
);
257 de
->ino
= cpu_to_le32(inode
->i_ino
);
258 set_de_type(de
, inode
);
260 set_page_dirty(page
);
261 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
262 mark_inode_dirty(dir
);
264 f2fs_put_page(page
, 1);
267 static void init_dent_inode(const struct qstr
*name
, struct page
*ipage
)
269 struct f2fs_inode
*ri
;
271 /* copy name info. to this inode page */
272 ri
= F2FS_INODE(ipage
);
273 ri
->i_namelen
= cpu_to_le32(name
->len
);
274 memcpy(ri
->i_name
, name
->name
, name
->len
);
275 set_page_dirty(ipage
);
278 int update_dent_inode(struct inode
*inode
, const struct qstr
*name
)
280 struct f2fs_sb_info
*sbi
= F2FS_SB(inode
->i_sb
);
283 page
= get_node_page(sbi
, inode
->i_ino
);
285 return PTR_ERR(page
);
287 init_dent_inode(name
, page
);
288 f2fs_put_page(page
, 1);
293 static int make_empty_dir(struct inode
*inode
,
294 struct inode
*parent
, struct page
*page
)
296 struct page
*dentry_page
;
297 struct f2fs_dentry_block
*dentry_blk
;
298 struct f2fs_dir_entry
*de
;
301 dentry_page
= get_new_data_page(inode
, page
, 0, true);
302 if (IS_ERR(dentry_page
))
303 return PTR_ERR(dentry_page
);
305 kaddr
= kmap_atomic(dentry_page
);
306 dentry_blk
= (struct f2fs_dentry_block
*)kaddr
;
308 de
= &dentry_blk
->dentry
[0];
309 de
->name_len
= cpu_to_le16(1);
311 de
->ino
= cpu_to_le32(inode
->i_ino
);
312 memcpy(dentry_blk
->filename
[0], ".", 1);
313 set_de_type(de
, inode
);
315 de
= &dentry_blk
->dentry
[1];
317 de
->name_len
= cpu_to_le16(2);
318 de
->ino
= cpu_to_le32(parent
->i_ino
);
319 memcpy(dentry_blk
->filename
[1], "..", 2);
320 set_de_type(de
, inode
);
322 test_and_set_bit_le(0, &dentry_blk
->dentry_bitmap
);
323 test_and_set_bit_le(1, &dentry_blk
->dentry_bitmap
);
324 kunmap_atomic(kaddr
);
326 set_page_dirty(dentry_page
);
327 f2fs_put_page(dentry_page
, 1);
331 static struct page
*init_inode_metadata(struct inode
*inode
,
332 struct inode
*dir
, const struct qstr
*name
)
337 if (is_inode_flag_set(F2FS_I(inode
), FI_NEW_INODE
)) {
338 page
= new_inode_page(inode
, name
);
342 if (S_ISDIR(inode
->i_mode
)) {
343 err
= make_empty_dir(inode
, dir
, page
);
348 err
= f2fs_init_acl(inode
, dir
, page
);
352 err
= f2fs_init_security(inode
, dir
, name
, page
);
356 page
= get_node_page(F2FS_SB(dir
->i_sb
), inode
->i_ino
);
360 set_cold_node(inode
, page
);
363 init_dent_inode(name
, page
);
366 * This file should be checkpointed during fsync.
367 * We lost i_pino from now on.
369 if (is_inode_flag_set(F2FS_I(inode
), FI_INC_LINK
)) {
370 file_lost_pino(inode
);
376 f2fs_put_page(page
, 1);
377 /* once the failed inode becomes a bad inode, i_mode is S_IFREG */
378 truncate_inode_pages(&inode
->i_data
, 0);
379 truncate_blocks(inode
, 0);
380 remove_dirty_dir_inode(inode
);
382 remove_inode_page(inode
);
386 static void update_parent_metadata(struct inode
*dir
, struct inode
*inode
,
387 unsigned int current_depth
)
389 if (is_inode_flag_set(F2FS_I(inode
), FI_NEW_INODE
)) {
390 if (S_ISDIR(inode
->i_mode
)) {
392 set_inode_flag(F2FS_I(dir
), FI_UPDATE_DIR
);
394 clear_inode_flag(F2FS_I(inode
), FI_NEW_INODE
);
396 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
397 mark_inode_dirty(dir
);
399 if (F2FS_I(dir
)->i_current_depth
!= current_depth
) {
400 F2FS_I(dir
)->i_current_depth
= current_depth
;
401 set_inode_flag(F2FS_I(dir
), FI_UPDATE_DIR
);
404 if (is_inode_flag_set(F2FS_I(inode
), FI_INC_LINK
))
405 clear_inode_flag(F2FS_I(inode
), FI_INC_LINK
);
408 static int room_for_filename(struct f2fs_dentry_block
*dentry_blk
, int slots
)
411 int zero_start
, zero_end
;
413 zero_start
= find_next_zero_bit_le(&dentry_blk
->dentry_bitmap
,
416 if (zero_start
>= NR_DENTRY_IN_BLOCK
)
417 return NR_DENTRY_IN_BLOCK
;
419 zero_end
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
422 if (zero_end
- zero_start
>= slots
)
425 bit_start
= zero_end
+ 1;
427 if (zero_end
+ 1 >= NR_DENTRY_IN_BLOCK
)
428 return NR_DENTRY_IN_BLOCK
;
433 * Caller should grab and release a rwsem by calling f2fs_lock_op() and
436 int __f2fs_add_link(struct inode
*dir
, const struct qstr
*name
,
439 unsigned int bit_pos
;
441 unsigned int current_depth
;
442 unsigned long bidx
, block
;
443 f2fs_hash_t dentry_hash
;
444 struct f2fs_dir_entry
*de
;
445 unsigned int nbucket
, nblock
;
446 size_t namelen
= name
->len
;
447 struct page
*dentry_page
= NULL
;
448 struct f2fs_dentry_block
*dentry_blk
= NULL
;
449 int slots
= GET_DENTRY_SLOTS(namelen
);
454 dentry_hash
= f2fs_dentry_hash(name
->name
, name
->len
);
456 current_depth
= F2FS_I(dir
)->i_current_depth
;
457 if (F2FS_I(dir
)->chash
== dentry_hash
) {
458 level
= F2FS_I(dir
)->clevel
;
459 F2FS_I(dir
)->chash
= 0;
463 if (unlikely(current_depth
== MAX_DIR_HASH_DEPTH
))
466 /* Increase the depth, if required */
467 if (level
== current_depth
)
470 nbucket
= dir_buckets(level
, F2FS_I(dir
)->i_dir_level
);
471 nblock
= bucket_blocks(level
);
473 bidx
= dir_block_index(level
, F2FS_I(dir
)->i_dir_level
,
474 (le32_to_cpu(dentry_hash
) % nbucket
));
476 for (block
= bidx
; block
<= (bidx
+ nblock
- 1); block
++) {
477 dentry_page
= get_new_data_page(dir
, NULL
, block
, true);
478 if (IS_ERR(dentry_page
))
479 return PTR_ERR(dentry_page
);
481 dentry_blk
= kmap(dentry_page
);
482 bit_pos
= room_for_filename(dentry_blk
, slots
);
483 if (bit_pos
< NR_DENTRY_IN_BLOCK
)
487 f2fs_put_page(dentry_page
, 1);
490 /* Move to next level to find the empty slot for new dentry */
494 f2fs_wait_on_page_writeback(dentry_page
, DATA
);
496 down_write(&F2FS_I(inode
)->i_sem
);
497 page
= init_inode_metadata(inode
, dir
, name
);
502 de
= &dentry_blk
->dentry
[bit_pos
];
503 de
->hash_code
= dentry_hash
;
504 de
->name_len
= cpu_to_le16(namelen
);
505 memcpy(dentry_blk
->filename
[bit_pos
], name
->name
, name
->len
);
506 de
->ino
= cpu_to_le32(inode
->i_ino
);
507 set_de_type(de
, inode
);
508 for (i
= 0; i
< slots
; i
++)
509 test_and_set_bit_le(bit_pos
+ i
, &dentry_blk
->dentry_bitmap
);
510 set_page_dirty(dentry_page
);
512 /* we don't need to mark_inode_dirty now */
513 F2FS_I(inode
)->i_pino
= dir
->i_ino
;
514 update_inode(inode
, page
);
515 f2fs_put_page(page
, 1);
517 update_parent_metadata(dir
, inode
, current_depth
);
519 up_write(&F2FS_I(inode
)->i_sem
);
521 if (is_inode_flag_set(F2FS_I(dir
), FI_UPDATE_DIR
)) {
522 update_inode_page(dir
);
523 clear_inode_flag(F2FS_I(dir
), FI_UPDATE_DIR
);
526 f2fs_put_page(dentry_page
, 1);
531 * It only removes the dentry from the dentry page,corresponding name
532 * entry in name page does not need to be touched during deletion.
534 void f2fs_delete_entry(struct f2fs_dir_entry
*dentry
, struct page
*page
,
537 struct f2fs_dentry_block
*dentry_blk
;
538 unsigned int bit_pos
;
539 struct address_space
*mapping
= page
->mapping
;
540 struct inode
*dir
= mapping
->host
;
541 int slots
= GET_DENTRY_SLOTS(le16_to_cpu(dentry
->name_len
));
542 void *kaddr
= page_address(page
);
546 f2fs_wait_on_page_writeback(page
, DATA
);
548 dentry_blk
= (struct f2fs_dentry_block
*)kaddr
;
549 bit_pos
= dentry
- (struct f2fs_dir_entry
*)dentry_blk
->dentry
;
550 for (i
= 0; i
< slots
; i
++)
551 test_and_clear_bit_le(bit_pos
+ i
, &dentry_blk
->dentry_bitmap
);
553 /* Let's check and deallocate this dentry page */
554 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
557 kunmap(page
); /* kunmap - pair of f2fs_find_entry */
558 set_page_dirty(page
);
560 dir
->i_ctime
= dir
->i_mtime
= CURRENT_TIME
;
563 struct f2fs_sb_info
*sbi
= F2FS_SB(dir
->i_sb
);
565 down_write(&F2FS_I(inode
)->i_sem
);
567 if (S_ISDIR(inode
->i_mode
)) {
569 update_inode_page(dir
);
571 inode
->i_ctime
= CURRENT_TIME
;
573 if (S_ISDIR(inode
->i_mode
)) {
575 i_size_write(inode
, 0);
577 up_write(&F2FS_I(inode
)->i_sem
);
578 update_inode_page(inode
);
580 if (inode
->i_nlink
== 0)
581 add_orphan_inode(sbi
, inode
->i_ino
);
583 release_orphan_inode(sbi
);
586 if (bit_pos
== NR_DENTRY_IN_BLOCK
) {
587 truncate_hole(dir
, page
->index
, page
->index
+ 1);
588 clear_page_dirty_for_io(page
);
589 ClearPageUptodate(page
);
590 inode_dec_dirty_dents(dir
);
592 f2fs_put_page(page
, 1);
595 bool f2fs_empty_dir(struct inode
*dir
)
598 struct page
*dentry_page
;
599 unsigned int bit_pos
;
600 struct f2fs_dentry_block
*dentry_blk
;
601 unsigned long nblock
= dir_blocks(dir
);
603 for (bidx
= 0; bidx
< nblock
; bidx
++) {
605 dentry_page
= get_lock_data_page(dir
, bidx
);
606 if (IS_ERR(dentry_page
)) {
607 if (PTR_ERR(dentry_page
) == -ENOENT
)
613 kaddr
= kmap_atomic(dentry_page
);
614 dentry_blk
= (struct f2fs_dentry_block
*)kaddr
;
619 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
622 kunmap_atomic(kaddr
);
624 f2fs_put_page(dentry_page
, 1);
626 if (bit_pos
< NR_DENTRY_IN_BLOCK
)
632 static int f2fs_readdir(struct file
*file
, struct dir_context
*ctx
)
634 struct inode
*inode
= file_inode(file
);
635 unsigned long npages
= dir_blocks(inode
);
636 unsigned int bit_pos
= 0;
637 struct f2fs_dentry_block
*dentry_blk
= NULL
;
638 struct f2fs_dir_entry
*de
= NULL
;
639 struct page
*dentry_page
= NULL
;
640 unsigned int n
= ((unsigned long)ctx
->pos
/ NR_DENTRY_IN_BLOCK
);
641 unsigned char d_type
= DT_UNKNOWN
;
643 bit_pos
= ((unsigned long)ctx
->pos
% NR_DENTRY_IN_BLOCK
);
645 for (; n
< npages
; n
++) {
646 dentry_page
= get_lock_data_page(inode
, n
);
647 if (IS_ERR(dentry_page
))
650 dentry_blk
= kmap(dentry_page
);
651 while (bit_pos
< NR_DENTRY_IN_BLOCK
) {
652 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
655 if (bit_pos
>= NR_DENTRY_IN_BLOCK
)
658 de
= &dentry_blk
->dentry
[bit_pos
];
659 if (de
->file_type
< F2FS_FT_MAX
)
660 d_type
= f2fs_filetype_table
[de
->file_type
];
664 dentry_blk
->filename
[bit_pos
],
665 le16_to_cpu(de
->name_len
),
666 le32_to_cpu(de
->ino
), d_type
))
669 bit_pos
+= GET_DENTRY_SLOTS(le16_to_cpu(de
->name_len
));
670 ctx
->pos
= n
* NR_DENTRY_IN_BLOCK
+ bit_pos
;
673 ctx
->pos
= (n
+ 1) * NR_DENTRY_IN_BLOCK
;
675 f2fs_put_page(dentry_page
, 1);
679 if (dentry_page
&& !IS_ERR(dentry_page
)) {
681 f2fs_put_page(dentry_page
, 1);
687 const struct file_operations f2fs_dir_operations
= {
688 .llseek
= generic_file_llseek
,
689 .read
= generic_read_dir
,
690 .iterate
= f2fs_readdir
,
691 .fsync
= f2fs_sync_file
,
692 .unlocked_ioctl
= f2fs_ioctl
,