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>
17 static unsigned long dir_blocks(struct inode
*inode
)
19 return ((unsigned long long) (i_size_read(inode
) + PAGE_CACHE_SIZE
- 1))
23 static unsigned int dir_buckets(unsigned int level
)
25 if (level
< MAX_DIR_HASH_DEPTH
/ 2)
28 return 1 << ((MAX_DIR_HASH_DEPTH
/ 2) - 1);
31 static unsigned int bucket_blocks(unsigned int level
)
33 if (level
< MAX_DIR_HASH_DEPTH
/ 2)
39 static unsigned char f2fs_filetype_table
[F2FS_FT_MAX
] = {
40 [F2FS_FT_UNKNOWN
] = DT_UNKNOWN
,
41 [F2FS_FT_REG_FILE
] = DT_REG
,
42 [F2FS_FT_DIR
] = DT_DIR
,
43 [F2FS_FT_CHRDEV
] = DT_CHR
,
44 [F2FS_FT_BLKDEV
] = DT_BLK
,
45 [F2FS_FT_FIFO
] = DT_FIFO
,
46 [F2FS_FT_SOCK
] = DT_SOCK
,
47 [F2FS_FT_SYMLINK
] = DT_LNK
,
51 static unsigned char f2fs_type_by_mode
[S_IFMT
>> S_SHIFT
] = {
52 [S_IFREG
>> S_SHIFT
] = F2FS_FT_REG_FILE
,
53 [S_IFDIR
>> S_SHIFT
] = F2FS_FT_DIR
,
54 [S_IFCHR
>> S_SHIFT
] = F2FS_FT_CHRDEV
,
55 [S_IFBLK
>> S_SHIFT
] = F2FS_FT_BLKDEV
,
56 [S_IFIFO
>> S_SHIFT
] = F2FS_FT_FIFO
,
57 [S_IFSOCK
>> S_SHIFT
] = F2FS_FT_SOCK
,
58 [S_IFLNK
>> S_SHIFT
] = F2FS_FT_SYMLINK
,
61 static void set_de_type(struct f2fs_dir_entry
*de
, struct inode
*inode
)
63 mode_t mode
= inode
->i_mode
;
64 de
->file_type
= f2fs_type_by_mode
[(mode
& S_IFMT
) >> S_SHIFT
];
67 static unsigned long dir_block_index(unsigned int level
, unsigned int idx
)
70 unsigned long bidx
= 0;
72 for (i
= 0; i
< level
; i
++)
73 bidx
+= dir_buckets(i
) * bucket_blocks(i
);
74 bidx
+= idx
* bucket_blocks(level
);
78 static bool early_match_name(const char *name
, size_t namelen
,
79 f2fs_hash_t namehash
, struct f2fs_dir_entry
*de
)
81 if (le16_to_cpu(de
->name_len
) != namelen
)
84 if (de
->hash_code
!= namehash
)
90 static struct f2fs_dir_entry
*find_in_block(struct page
*dentry_page
,
91 const char *name
, size_t namelen
, int *max_slots
,
92 f2fs_hash_t namehash
, struct page
**res_page
)
94 struct f2fs_dir_entry
*de
;
95 unsigned long bit_pos
, end_pos
, next_pos
;
96 struct f2fs_dentry_block
*dentry_blk
= kmap(dentry_page
);
99 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
100 NR_DENTRY_IN_BLOCK
, 0);
101 while (bit_pos
< NR_DENTRY_IN_BLOCK
) {
102 de
= &dentry_blk
->dentry
[bit_pos
];
103 slots
= GET_DENTRY_SLOTS(le16_to_cpu(de
->name_len
));
105 if (early_match_name(name
, namelen
, namehash
, de
)) {
106 if (!memcmp(dentry_blk
->filename
[bit_pos
],
108 *res_page
= dentry_page
;
112 next_pos
= bit_pos
+ slots
;
113 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
114 NR_DENTRY_IN_BLOCK
, next_pos
);
115 if (bit_pos
>= NR_DENTRY_IN_BLOCK
)
116 end_pos
= NR_DENTRY_IN_BLOCK
;
119 if (*max_slots
< end_pos
- next_pos
)
120 *max_slots
= end_pos
- next_pos
;
129 static struct f2fs_dir_entry
*find_in_level(struct inode
*dir
,
130 unsigned int level
, const char *name
, size_t namelen
,
131 f2fs_hash_t namehash
, struct page
**res_page
)
133 int s
= GET_DENTRY_SLOTS(namelen
);
134 unsigned int nbucket
, nblock
;
135 unsigned int bidx
, end_block
;
136 struct page
*dentry_page
;
137 struct f2fs_dir_entry
*de
= NULL
;
141 BUG_ON(level
> MAX_DIR_HASH_DEPTH
);
143 nbucket
= dir_buckets(level
);
144 nblock
= bucket_blocks(level
);
146 bidx
= dir_block_index(level
, le32_to_cpu(namehash
) % nbucket
);
147 end_block
= bidx
+ nblock
;
149 for (; bidx
< end_block
; bidx
++) {
150 /* no need to allocate new dentry pages to all the indices */
151 dentry_page
= find_data_page(dir
, bidx
);
152 if (IS_ERR(dentry_page
)) {
157 de
= find_in_block(dentry_page
, name
, namelen
,
158 &max_slots
, namehash
, res_page
);
164 f2fs_put_page(dentry_page
, 0);
167 if (!de
&& room
&& F2FS_I(dir
)->chash
!= namehash
) {
168 F2FS_I(dir
)->chash
= namehash
;
169 F2FS_I(dir
)->clevel
= level
;
176 * Find an entry in the specified directory with the wanted name.
177 * It returns the page where the entry was found (as a parameter - res_page),
178 * and the entry itself. Page is returned mapped and unlocked.
179 * Entry is guaranteed to be valid.
181 struct f2fs_dir_entry
*f2fs_find_entry(struct inode
*dir
,
182 struct qstr
*child
, struct page
**res_page
)
184 const char *name
= child
->name
;
185 size_t namelen
= child
->len
;
186 unsigned long npages
= dir_blocks(dir
);
187 struct f2fs_dir_entry
*de
= NULL
;
188 f2fs_hash_t name_hash
;
189 unsigned int max_depth
;
197 name_hash
= f2fs_dentry_hash(name
, namelen
);
198 max_depth
= F2FS_I(dir
)->i_current_depth
;
200 for (level
= 0; level
< max_depth
; level
++) {
201 de
= find_in_level(dir
, level
, name
,
202 namelen
, name_hash
, res_page
);
206 if (!de
&& F2FS_I(dir
)->chash
!= name_hash
) {
207 F2FS_I(dir
)->chash
= name_hash
;
208 F2FS_I(dir
)->clevel
= level
- 1;
213 struct f2fs_dir_entry
*f2fs_parent_dir(struct inode
*dir
, struct page
**p
)
215 struct page
*page
= NULL
;
216 struct f2fs_dir_entry
*de
= NULL
;
217 struct f2fs_dentry_block
*dentry_blk
= NULL
;
219 page
= get_lock_data_page(dir
, 0);
223 dentry_blk
= kmap(page
);
224 de
= &dentry_blk
->dentry
[1];
230 ino_t
f2fs_inode_by_name(struct inode
*dir
, struct qstr
*qstr
)
233 struct f2fs_dir_entry
*de
;
236 de
= f2fs_find_entry(dir
, qstr
, &page
);
238 res
= le32_to_cpu(de
->ino
);
240 f2fs_put_page(page
, 0);
246 void f2fs_set_link(struct inode
*dir
, struct f2fs_dir_entry
*de
,
247 struct page
*page
, struct inode
*inode
)
249 struct f2fs_sb_info
*sbi
= F2FS_SB(dir
->i_sb
);
251 mutex_lock_op(sbi
, DENTRY_OPS
);
253 wait_on_page_writeback(page
);
254 de
->ino
= cpu_to_le32(inode
->i_ino
);
255 set_de_type(de
, inode
);
257 set_page_dirty(page
);
258 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
259 mark_inode_dirty(dir
);
261 /* update parent inode number before releasing dentry page */
262 F2FS_I(inode
)->i_pino
= dir
->i_ino
;
264 f2fs_put_page(page
, 1);
265 mutex_unlock_op(sbi
, DENTRY_OPS
);
268 void init_dent_inode(struct dentry
*dentry
, struct page
*ipage
)
270 struct f2fs_node
*rn
;
275 wait_on_page_writeback(ipage
);
277 /* copy dentry info. to this inode page */
278 rn
= (struct f2fs_node
*)page_address(ipage
);
279 rn
->i
.i_namelen
= cpu_to_le32(dentry
->d_name
.len
);
280 memcpy(rn
->i
.i_name
, dentry
->d_name
.name
, dentry
->d_name
.len
);
281 set_page_dirty(ipage
);
284 static int init_inode_metadata(struct inode
*inode
, struct dentry
*dentry
)
286 struct inode
*dir
= dentry
->d_parent
->d_inode
;
288 if (is_inode_flag_set(F2FS_I(inode
), FI_NEW_INODE
)) {
290 err
= new_inode_page(inode
, dentry
);
294 if (S_ISDIR(inode
->i_mode
)) {
295 err
= f2fs_make_empty(inode
, dir
);
297 remove_inode_page(inode
);
302 err
= f2fs_init_acl(inode
, dir
);
304 remove_inode_page(inode
);
309 ipage
= get_node_page(F2FS_SB(dir
->i_sb
), inode
->i_ino
);
311 return PTR_ERR(ipage
);
312 set_cold_node(inode
, ipage
);
313 init_dent_inode(dentry
, ipage
);
314 f2fs_put_page(ipage
, 1);
316 if (is_inode_flag_set(F2FS_I(inode
), FI_INC_LINK
)) {
318 f2fs_write_inode(inode
, NULL
);
323 static void update_parent_metadata(struct inode
*dir
, struct inode
*inode
,
324 unsigned int current_depth
)
326 bool need_dir_update
= false;
328 if (is_inode_flag_set(F2FS_I(inode
), FI_NEW_INODE
)) {
329 if (S_ISDIR(inode
->i_mode
)) {
331 need_dir_update
= true;
333 clear_inode_flag(F2FS_I(inode
), FI_NEW_INODE
);
335 dir
->i_mtime
= dir
->i_ctime
= CURRENT_TIME
;
336 if (F2FS_I(dir
)->i_current_depth
!= current_depth
) {
337 F2FS_I(dir
)->i_current_depth
= current_depth
;
338 need_dir_update
= true;
342 f2fs_write_inode(dir
, NULL
);
344 mark_inode_dirty(dir
);
346 if (is_inode_flag_set(F2FS_I(inode
), FI_INC_LINK
))
347 clear_inode_flag(F2FS_I(inode
), FI_INC_LINK
);
350 static int room_for_filename(struct f2fs_dentry_block
*dentry_blk
, int slots
)
353 int zero_start
, zero_end
;
355 zero_start
= find_next_zero_bit_le(&dentry_blk
->dentry_bitmap
,
358 if (zero_start
>= NR_DENTRY_IN_BLOCK
)
359 return NR_DENTRY_IN_BLOCK
;
361 zero_end
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
364 if (zero_end
- zero_start
>= slots
)
367 bit_start
= zero_end
+ 1;
369 if (zero_end
+ 1 >= NR_DENTRY_IN_BLOCK
)
370 return NR_DENTRY_IN_BLOCK
;
374 int f2fs_add_link(struct dentry
*dentry
, struct inode
*inode
)
376 unsigned int bit_pos
;
378 unsigned int current_depth
;
379 unsigned long bidx
, block
;
380 f2fs_hash_t dentry_hash
;
381 struct f2fs_dir_entry
*de
;
382 unsigned int nbucket
, nblock
;
383 struct inode
*dir
= dentry
->d_parent
->d_inode
;
384 struct f2fs_sb_info
*sbi
= F2FS_SB(dir
->i_sb
);
385 const char *name
= dentry
->d_name
.name
;
386 size_t namelen
= dentry
->d_name
.len
;
387 struct page
*dentry_page
= NULL
;
388 struct f2fs_dentry_block
*dentry_blk
= NULL
;
389 int slots
= GET_DENTRY_SLOTS(namelen
);
393 dentry_hash
= f2fs_dentry_hash(name
, dentry
->d_name
.len
);
395 current_depth
= F2FS_I(dir
)->i_current_depth
;
396 if (F2FS_I(dir
)->chash
== dentry_hash
) {
397 level
= F2FS_I(dir
)->clevel
;
398 F2FS_I(dir
)->chash
= 0;
402 if (current_depth
== MAX_DIR_HASH_DEPTH
)
405 /* Increase the depth, if required */
406 if (level
== current_depth
)
409 nbucket
= dir_buckets(level
);
410 nblock
= bucket_blocks(level
);
412 bidx
= dir_block_index(level
, (le32_to_cpu(dentry_hash
) % nbucket
));
414 for (block
= bidx
; block
<= (bidx
+ nblock
- 1); block
++) {
415 mutex_lock_op(sbi
, DENTRY_OPS
);
416 dentry_page
= get_new_data_page(dir
, block
, true);
417 if (IS_ERR(dentry_page
)) {
418 mutex_unlock_op(sbi
, DENTRY_OPS
);
419 return PTR_ERR(dentry_page
);
422 dentry_blk
= kmap(dentry_page
);
423 bit_pos
= room_for_filename(dentry_blk
, slots
);
424 if (bit_pos
< NR_DENTRY_IN_BLOCK
)
428 f2fs_put_page(dentry_page
, 1);
429 mutex_unlock_op(sbi
, DENTRY_OPS
);
432 /* Move to next level to find the empty slot for new dentry */
436 err
= init_inode_metadata(inode
, dentry
);
440 wait_on_page_writeback(dentry_page
);
442 de
= &dentry_blk
->dentry
[bit_pos
];
443 de
->hash_code
= dentry_hash
;
444 de
->name_len
= cpu_to_le16(namelen
);
445 memcpy(dentry_blk
->filename
[bit_pos
], name
, namelen
);
446 de
->ino
= cpu_to_le32(inode
->i_ino
);
447 set_de_type(de
, inode
);
448 for (i
= 0; i
< slots
; i
++)
449 test_and_set_bit_le(bit_pos
+ i
, &dentry_blk
->dentry_bitmap
);
450 set_page_dirty(dentry_page
);
452 update_parent_metadata(dir
, inode
, current_depth
);
454 /* update parent inode number before releasing dentry page */
455 F2FS_I(inode
)->i_pino
= dir
->i_ino
;
458 f2fs_put_page(dentry_page
, 1);
459 mutex_unlock_op(sbi
, DENTRY_OPS
);
464 * It only removes the dentry from the dentry page,corresponding name
465 * entry in name page does not need to be touched during deletion.
467 void f2fs_delete_entry(struct f2fs_dir_entry
*dentry
, struct page
*page
,
470 struct f2fs_dentry_block
*dentry_blk
;
471 unsigned int bit_pos
;
472 struct address_space
*mapping
= page
->mapping
;
473 struct inode
*dir
= mapping
->host
;
474 struct f2fs_sb_info
*sbi
= F2FS_SB(dir
->i_sb
);
475 int slots
= GET_DENTRY_SLOTS(le16_to_cpu(dentry
->name_len
));
476 void *kaddr
= page_address(page
);
479 mutex_lock_op(sbi
, DENTRY_OPS
);
482 wait_on_page_writeback(page
);
484 dentry_blk
= (struct f2fs_dentry_block
*)kaddr
;
485 bit_pos
= dentry
- (struct f2fs_dir_entry
*)dentry_blk
->dentry
;
486 for (i
= 0; i
< slots
; i
++)
487 test_and_clear_bit_le(bit_pos
+ i
, &dentry_blk
->dentry_bitmap
);
489 /* Let's check and deallocate this dentry page */
490 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
493 kunmap(page
); /* kunmap - pair of f2fs_find_entry */
494 set_page_dirty(page
);
496 dir
->i_ctime
= dir
->i_mtime
= CURRENT_TIME
;
498 if (inode
&& S_ISDIR(inode
->i_mode
)) {
500 f2fs_write_inode(dir
, NULL
);
502 mark_inode_dirty(dir
);
506 inode
->i_ctime
= dir
->i_ctime
= dir
->i_mtime
= CURRENT_TIME
;
508 if (S_ISDIR(inode
->i_mode
)) {
510 i_size_write(inode
, 0);
512 f2fs_write_inode(inode
, NULL
);
513 if (inode
->i_nlink
== 0)
514 add_orphan_inode(sbi
, inode
->i_ino
);
517 if (bit_pos
== NR_DENTRY_IN_BLOCK
) {
518 truncate_hole(dir
, page
->index
, page
->index
+ 1);
519 clear_page_dirty_for_io(page
);
520 ClearPageUptodate(page
);
521 dec_page_count(sbi
, F2FS_DIRTY_DENTS
);
522 inode_dec_dirty_dents(dir
);
524 f2fs_put_page(page
, 1);
526 mutex_unlock_op(sbi
, DENTRY_OPS
);
529 int f2fs_make_empty(struct inode
*inode
, struct inode
*parent
)
531 struct page
*dentry_page
;
532 struct f2fs_dentry_block
*dentry_blk
;
533 struct f2fs_dir_entry
*de
;
536 dentry_page
= get_new_data_page(inode
, 0, true);
537 if (IS_ERR(dentry_page
))
538 return PTR_ERR(dentry_page
);
540 kaddr
= kmap_atomic(dentry_page
);
541 dentry_blk
= (struct f2fs_dentry_block
*)kaddr
;
543 de
= &dentry_blk
->dentry
[0];
544 de
->name_len
= cpu_to_le16(1);
545 de
->hash_code
= f2fs_dentry_hash(".", 1);
546 de
->ino
= cpu_to_le32(inode
->i_ino
);
547 memcpy(dentry_blk
->filename
[0], ".", 1);
548 set_de_type(de
, inode
);
550 de
= &dentry_blk
->dentry
[1];
551 de
->hash_code
= f2fs_dentry_hash("..", 2);
552 de
->name_len
= cpu_to_le16(2);
553 de
->ino
= cpu_to_le32(parent
->i_ino
);
554 memcpy(dentry_blk
->filename
[1], "..", 2);
555 set_de_type(de
, inode
);
557 test_and_set_bit_le(0, &dentry_blk
->dentry_bitmap
);
558 test_and_set_bit_le(1, &dentry_blk
->dentry_bitmap
);
559 kunmap_atomic(kaddr
);
561 set_page_dirty(dentry_page
);
562 f2fs_put_page(dentry_page
, 1);
566 bool f2fs_empty_dir(struct inode
*dir
)
569 struct page
*dentry_page
;
570 unsigned int bit_pos
;
571 struct f2fs_dentry_block
*dentry_blk
;
572 unsigned long nblock
= dir_blocks(dir
);
574 for (bidx
= 0; bidx
< nblock
; bidx
++) {
576 dentry_page
= get_lock_data_page(dir
, bidx
);
577 if (IS_ERR(dentry_page
)) {
578 if (PTR_ERR(dentry_page
) == -ENOENT
)
584 kaddr
= kmap_atomic(dentry_page
);
585 dentry_blk
= (struct f2fs_dentry_block
*)kaddr
;
590 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
593 kunmap_atomic(kaddr
);
595 f2fs_put_page(dentry_page
, 1);
597 if (bit_pos
< NR_DENTRY_IN_BLOCK
)
603 static int f2fs_readdir(struct file
*file
, void *dirent
, filldir_t filldir
)
605 unsigned long pos
= file
->f_pos
;
606 struct inode
*inode
= file
->f_dentry
->d_inode
;
607 unsigned long npages
= dir_blocks(inode
);
608 unsigned char *types
= NULL
;
609 unsigned int bit_pos
= 0, start_bit_pos
= 0;
611 struct f2fs_dentry_block
*dentry_blk
= NULL
;
612 struct f2fs_dir_entry
*de
= NULL
;
613 struct page
*dentry_page
= NULL
;
615 unsigned char d_type
= DT_UNKNOWN
;
618 types
= f2fs_filetype_table
;
619 bit_pos
= (pos
% NR_DENTRY_IN_BLOCK
);
620 n
= (pos
/ NR_DENTRY_IN_BLOCK
);
622 for ( ; n
< npages
; n
++) {
623 dentry_page
= get_lock_data_page(inode
, n
);
624 if (IS_ERR(dentry_page
))
627 start_bit_pos
= bit_pos
;
628 dentry_blk
= kmap(dentry_page
);
629 while (bit_pos
< NR_DENTRY_IN_BLOCK
) {
631 bit_pos
= find_next_bit_le(&dentry_blk
->dentry_bitmap
,
634 if (bit_pos
>= NR_DENTRY_IN_BLOCK
)
637 de
= &dentry_blk
->dentry
[bit_pos
];
638 if (types
&& de
->file_type
< F2FS_FT_MAX
)
639 d_type
= types
[de
->file_type
];
641 over
= filldir(dirent
,
642 dentry_blk
->filename
[bit_pos
],
643 le16_to_cpu(de
->name_len
),
644 (n
* NR_DENTRY_IN_BLOCK
) + bit_pos
,
645 le32_to_cpu(de
->ino
), d_type
);
647 file
->f_pos
+= bit_pos
- start_bit_pos
;
650 slots
= GET_DENTRY_SLOTS(le16_to_cpu(de
->name_len
));
654 file
->f_pos
= (n
+ 1) * NR_DENTRY_IN_BLOCK
;
656 f2fs_put_page(dentry_page
, 1);
660 if (dentry_page
&& !IS_ERR(dentry_page
)) {
662 f2fs_put_page(dentry_page
, 1);
668 const struct file_operations f2fs_dir_operations
= {
669 .llseek
= generic_file_llseek
,
670 .read
= generic_read_dir
,
671 .readdir
= f2fs_readdir
,
672 .fsync
= f2fs_sync_file
,
673 .unlocked_ioctl
= f2fs_ioctl
,