692 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * linux/fs/ext4/dir.c4 *5 * Copyright (C) 1992, 1993, 1994, 19956 * Remy Card (card@masi.ibp.fr)7 * Laboratoire MASI - Institut Blaise Pascal8 * Universite Pierre et Marie Curie (Paris VI)9 *10 * from11 *12 * linux/fs/minix/dir.c13 *14 * Copyright (C) 1991, 1992 Linus Torvalds15 *16 * ext4 directory handling functions17 *18 * Big-endian to little-endian byte-swapping/bitmaps by19 * David S. Miller (davem@caip.rutgers.edu), 199520 *21 * Hash Tree Directory indexing (c) 2001 Daniel Phillips22 *23 */24 25#include <linux/fs.h>26#include <linux/buffer_head.h>27#include <linux/slab.h>28#include <linux/iversion.h>29#include <linux/unicode.h>30#include "ext4.h"31#include "xattr.h"32 33static int ext4_dx_readdir(struct file *, struct dir_context *);34 35/**36 * is_dx_dir() - check if a directory is using htree indexing37 * @inode: directory inode38 *39 * Check if the given dir-inode refers to an htree-indexed directory40 * (or a directory which could potentially get converted to use htree41 * indexing).42 *43 * Return 1 if it is a dx dir, 0 if not44 */45static int is_dx_dir(struct inode *inode)46{47 struct super_block *sb = inode->i_sb;48 49 if (ext4_has_feature_dir_index(inode->i_sb) &&50 ((ext4_test_inode_flag(inode, EXT4_INODE_INDEX)) ||51 ((inode->i_size >> sb->s_blocksize_bits) == 1) ||52 ext4_has_inline_data(inode)))53 return 1;54 55 return 0;56}57 58static bool is_fake_dir_entry(struct ext4_dir_entry_2 *de)59{60 /* Check if . or .. , or skip if namelen is 0 */61 if ((de->name_len > 0) && (de->name_len <= 2) && (de->name[0] == '.') &&62 (de->name[1] == '.' || de->name[1] == '\0'))63 return true;64 /* Check if this is a csum entry */65 if (de->file_type == EXT4_FT_DIR_CSUM)66 return true;67 return false;68}69 70/*71 * Return 0 if the directory entry is OK, and 1 if there is a problem72 *73 * Note: this is the opposite of what ext2 and ext3 historically returned...74 *75 * bh passed here can be an inode block or a dir data block, depending76 * on the inode inline data flag.77 */78int __ext4_check_dir_entry(const char *function, unsigned int line,79 struct inode *dir, struct file *filp,80 struct ext4_dir_entry_2 *de,81 struct buffer_head *bh, char *buf, int size,82 unsigned int offset)83{84 const char *error_msg = NULL;85 const int rlen = ext4_rec_len_from_disk(de->rec_len,86 dir->i_sb->s_blocksize);87 const int next_offset = ((char *) de - buf) + rlen;88 bool fake = is_fake_dir_entry(de);89 bool has_csum = ext4_has_metadata_csum(dir->i_sb);90 91 if (unlikely(rlen < ext4_dir_rec_len(1, fake ? NULL : dir)))92 error_msg = "rec_len is smaller than minimal";93 else if (unlikely(rlen % 4 != 0))94 error_msg = "rec_len % 4 != 0";95 else if (unlikely(rlen < ext4_dir_rec_len(de->name_len,96 fake ? NULL : dir)))97 error_msg = "rec_len is too small for name_len";98 else if (unlikely(next_offset > size))99 error_msg = "directory entry overrun";100 else if (unlikely(next_offset > size - ext4_dir_rec_len(1,101 has_csum ? NULL : dir) &&102 next_offset != size))103 error_msg = "directory entry too close to block end";104 else if (unlikely(le32_to_cpu(de->inode) >105 le32_to_cpu(EXT4_SB(dir->i_sb)->s_es->s_inodes_count)))106 error_msg = "inode out of bounds";107 else108 return 0;109 110 if (filp)111 ext4_error_file(filp, function, line, bh->b_blocknr,112 "bad entry in directory: %s - offset=%u, "113 "inode=%u, rec_len=%d, size=%d fake=%d",114 error_msg, offset, le32_to_cpu(de->inode),115 rlen, size, fake);116 else117 ext4_error_inode(dir, function, line, bh->b_blocknr,118 "bad entry in directory: %s - offset=%u, "119 "inode=%u, rec_len=%d, size=%d fake=%d",120 error_msg, offset, le32_to_cpu(de->inode),121 rlen, size, fake);122 123 return 1;124}125 126static int ext4_readdir(struct file *file, struct dir_context *ctx)127{128 unsigned int offset;129 int i;130 struct ext4_dir_entry_2 *de;131 int err;132 struct inode *inode = file_inode(file);133 struct super_block *sb = inode->i_sb;134 struct buffer_head *bh = NULL;135 struct fscrypt_str fstr = FSTR_INIT(NULL, 0);136 struct dir_private_info *info = file->private_data;137 138 err = fscrypt_prepare_readdir(inode);139 if (err)140 return err;141 142 if (is_dx_dir(inode)) {143 err = ext4_dx_readdir(file, ctx);144 if (err != ERR_BAD_DX_DIR)145 return err;146 147 /* Can we just clear INDEX flag to ignore htree information? */148 if (!ext4_has_metadata_csum(sb)) {149 /*150 * We don't set the inode dirty flag since it's not151 * critical that it gets flushed back to the disk.152 */153 ext4_clear_inode_flag(inode, EXT4_INODE_INDEX);154 }155 }156 157 if (ext4_has_inline_data(inode)) {158 int has_inline_data = 1;159 err = ext4_read_inline_dir(file, ctx,160 &has_inline_data);161 if (has_inline_data)162 return err;163 }164 165 if (IS_ENCRYPTED(inode)) {166 err = fscrypt_fname_alloc_buffer(EXT4_NAME_LEN, &fstr);167 if (err < 0)168 return err;169 }170 171 while (ctx->pos < inode->i_size) {172 struct ext4_map_blocks map;173 174 if (fatal_signal_pending(current)) {175 err = -ERESTARTSYS;176 goto errout;177 }178 cond_resched();179 offset = ctx->pos & (sb->s_blocksize - 1);180 map.m_lblk = ctx->pos >> EXT4_BLOCK_SIZE_BITS(sb);181 map.m_len = 1;182 err = ext4_map_blocks(NULL, inode, &map, 0);183 if (err == 0) {184 /* m_len should never be zero but let's avoid185 * an infinite loop if it somehow is */186 if (map.m_len == 0)187 map.m_len = 1;188 ctx->pos += map.m_len * sb->s_blocksize;189 continue;190 }191 if (err > 0) {192 pgoff_t index = map.m_pblk >>193 (PAGE_SHIFT - inode->i_blkbits);194 if (!ra_has_index(&file->f_ra, index))195 page_cache_sync_readahead(196 sb->s_bdev->bd_mapping,197 &file->f_ra, file,198 index, 1);199 file->f_ra.prev_pos = (loff_t)index << PAGE_SHIFT;200 bh = ext4_bread(NULL, inode, map.m_lblk, 0);201 if (IS_ERR(bh)) {202 err = PTR_ERR(bh);203 bh = NULL;204 goto errout;205 }206 }207 208 if (!bh) {209 /* corrupt size? Maybe no more blocks to read */210 if (ctx->pos > inode->i_blocks << 9)211 break;212 ctx->pos += sb->s_blocksize - offset;213 continue;214 }215 216 /* Check the checksum */217 if (!buffer_verified(bh) &&218 !ext4_dirblock_csum_verify(inode, bh)) {219 EXT4_ERROR_FILE(file, 0, "directory fails checksum "220 "at offset %llu",221 (unsigned long long)ctx->pos);222 ctx->pos += sb->s_blocksize - offset;223 brelse(bh);224 bh = NULL;225 continue;226 }227 set_buffer_verified(bh);228 229 /* If the dir block has changed since the last call to230 * readdir(2), then we might be pointing to an invalid231 * dirent right now. Scan from the start of the block232 * to make sure. */233 if (!inode_eq_iversion(inode, info->cookie)) {234 for (i = 0; i < sb->s_blocksize && i < offset; ) {235 de = (struct ext4_dir_entry_2 *)236 (bh->b_data + i);237 /* It's too expensive to do a full238 * dirent test each time round this239 * loop, but we do have to test at240 * least that it is non-zero. A241 * failure will be detected in the242 * dirent test below. */243 if (ext4_rec_len_from_disk(de->rec_len,244 sb->s_blocksize) < ext4_dir_rec_len(1,245 inode))246 break;247 i += ext4_rec_len_from_disk(de->rec_len,248 sb->s_blocksize);249 }250 offset = i;251 ctx->pos = (ctx->pos & ~(sb->s_blocksize - 1))252 | offset;253 info->cookie = inode_query_iversion(inode);254 }255 256 while (ctx->pos < inode->i_size257 && offset < sb->s_blocksize) {258 de = (struct ext4_dir_entry_2 *) (bh->b_data + offset);259 if (ext4_check_dir_entry(inode, file, de, bh,260 bh->b_data, bh->b_size,261 offset)) {262 /*263 * On error, skip to the next block264 */265 ctx->pos = (ctx->pos |266 (sb->s_blocksize - 1)) + 1;267 break;268 }269 offset += ext4_rec_len_from_disk(de->rec_len,270 sb->s_blocksize);271 if (le32_to_cpu(de->inode)) {272 if (!IS_ENCRYPTED(inode)) {273 if (!dir_emit(ctx, de->name,274 de->name_len,275 le32_to_cpu(de->inode),276 get_dtype(sb, de->file_type)))277 goto done;278 } else {279 int save_len = fstr.len;280 struct fscrypt_str de_name =281 FSTR_INIT(de->name,282 de->name_len);283 u32 hash;284 u32 minor_hash;285 286 if (IS_CASEFOLDED(inode)) {287 hash = EXT4_DIRENT_HASH(de);288 minor_hash = EXT4_DIRENT_MINOR_HASH(de);289 } else {290 hash = 0;291 minor_hash = 0;292 }293 294 /* Directory is encrypted */295 err = fscrypt_fname_disk_to_usr(inode,296 hash, minor_hash, &de_name, &fstr);297 de_name = fstr;298 fstr.len = save_len;299 if (err)300 goto errout;301 if (!dir_emit(ctx,302 de_name.name, de_name.len,303 le32_to_cpu(de->inode),304 get_dtype(sb, de->file_type)))305 goto done;306 }307 }308 ctx->pos += ext4_rec_len_from_disk(de->rec_len,309 sb->s_blocksize);310 }311 if ((ctx->pos < inode->i_size) && !dir_relax_shared(inode))312 goto done;313 brelse(bh);314 bh = NULL;315 }316done:317 err = 0;318errout:319 fscrypt_fname_free_buffer(&fstr);320 brelse(bh);321 return err;322}323 324static inline int is_32bit_api(void)325{326#ifdef CONFIG_COMPAT327 return in_compat_syscall();328#else329 return (BITS_PER_LONG == 32);330#endif331}332 333/*334 * These functions convert from the major/minor hash to an f_pos335 * value for dx directories336 *337 * Upper layer (for example NFS) should specify FMODE_32BITHASH or338 * FMODE_64BITHASH explicitly. On the other hand, we allow ext4 to be mounted339 * directly on both 32-bit and 64-bit nodes, under such case, neither340 * FMODE_32BITHASH nor FMODE_64BITHASH is specified.341 */342static inline loff_t hash2pos(struct file *filp, __u32 major, __u32 minor)343{344 if ((filp->f_mode & FMODE_32BITHASH) ||345 (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))346 return major >> 1;347 else348 return ((__u64)(major >> 1) << 32) | (__u64)minor;349}350 351static inline __u32 pos2maj_hash(struct file *filp, loff_t pos)352{353 if ((filp->f_mode & FMODE_32BITHASH) ||354 (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))355 return (pos << 1) & 0xffffffff;356 else357 return ((pos >> 32) << 1) & 0xffffffff;358}359 360static inline __u32 pos2min_hash(struct file *filp, loff_t pos)361{362 if ((filp->f_mode & FMODE_32BITHASH) ||363 (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))364 return 0;365 else366 return pos & 0xffffffff;367}368 369/*370 * Return 32- or 64-bit end-of-file for dx directories371 */372static inline loff_t ext4_get_htree_eof(struct file *filp)373{374 if ((filp->f_mode & FMODE_32BITHASH) ||375 (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))376 return EXT4_HTREE_EOF_32BIT;377 else378 return EXT4_HTREE_EOF_64BIT;379}380 381 382/*383 * ext4_dir_llseek() calls generic_file_llseek_size to handle htree384 * directories, where the "offset" is in terms of the filename hash385 * value instead of the byte offset.386 *387 * Because we may return a 64-bit hash that is well beyond offset limits,388 * we need to pass the max hash as the maximum allowable offset in389 * the htree directory case.390 *391 * For non-htree, ext4_llseek already chooses the proper max offset.392 */393static loff_t ext4_dir_llseek(struct file *file, loff_t offset, int whence)394{395 struct inode *inode = file->f_mapping->host;396 struct dir_private_info *info = file->private_data;397 int dx_dir = is_dx_dir(inode);398 loff_t ret, htree_max = ext4_get_htree_eof(file);399 400 if (likely(dx_dir))401 ret = generic_file_llseek_size(file, offset, whence,402 htree_max, htree_max);403 else404 ret = ext4_llseek(file, offset, whence);405 info->cookie = inode_peek_iversion(inode) - 1;406 return ret;407}408 409/*410 * This structure holds the nodes of the red-black tree used to store411 * the directory entry in hash order.412 */413struct fname {414 __u32 hash;415 __u32 minor_hash;416 struct rb_node rb_hash;417 struct fname *next;418 __u32 inode;419 __u8 name_len;420 __u8 file_type;421 char name[];422};423 424/*425 * This function implements a non-recursive way of freeing all of the426 * nodes in the red-black tree.427 */428static void free_rb_tree_fname(struct rb_root *root)429{430 struct fname *fname, *next;431 432 rbtree_postorder_for_each_entry_safe(fname, next, root, rb_hash)433 while (fname) {434 struct fname *old = fname;435 fname = fname->next;436 kfree(old);437 }438 439 *root = RB_ROOT;440}441 442static void ext4_htree_init_dir_info(struct file *filp, loff_t pos)443{444 struct dir_private_info *p = filp->private_data;445 446 if (is_dx_dir(file_inode(filp)) && !p->initialized) {447 p->curr_hash = pos2maj_hash(filp, pos);448 p->curr_minor_hash = pos2min_hash(filp, pos);449 p->initialized = true;450 }451}452 453void ext4_htree_free_dir_info(struct dir_private_info *p)454{455 free_rb_tree_fname(&p->root);456 kfree(p);457}458 459/*460 * Given a directory entry, enter it into the fname rb tree.461 *462 * When filename encryption is enabled, the dirent will hold the463 * encrypted filename, while the htree will hold decrypted filename.464 * The decrypted filename is passed in via ent_name. parameter.465 */466int ext4_htree_store_dirent(struct file *dir_file, __u32 hash,467 __u32 minor_hash,468 struct ext4_dir_entry_2 *dirent,469 struct fscrypt_str *ent_name)470{471 struct rb_node **p, *parent = NULL;472 struct fname *fname, *new_fn;473 struct dir_private_info *info;474 int len;475 476 info = dir_file->private_data;477 p = &info->root.rb_node;478 479 /* Create and allocate the fname structure */480 len = sizeof(struct fname) + ent_name->len + 1;481 new_fn = kzalloc(len, GFP_KERNEL);482 if (!new_fn)483 return -ENOMEM;484 new_fn->hash = hash;485 new_fn->minor_hash = minor_hash;486 new_fn->inode = le32_to_cpu(dirent->inode);487 new_fn->name_len = ent_name->len;488 new_fn->file_type = dirent->file_type;489 memcpy(new_fn->name, ent_name->name, ent_name->len);490 491 while (*p) {492 parent = *p;493 fname = rb_entry(parent, struct fname, rb_hash);494 495 /*496 * If the hash and minor hash match up, then we put497 * them on a linked list. This rarely happens...498 */499 if ((new_fn->hash == fname->hash) &&500 (new_fn->minor_hash == fname->minor_hash)) {501 new_fn->next = fname->next;502 fname->next = new_fn;503 return 0;504 }505 506 if (new_fn->hash < fname->hash)507 p = &(*p)->rb_left;508 else if (new_fn->hash > fname->hash)509 p = &(*p)->rb_right;510 else if (new_fn->minor_hash < fname->minor_hash)511 p = &(*p)->rb_left;512 else /* if (new_fn->minor_hash > fname->minor_hash) */513 p = &(*p)->rb_right;514 }515 516 rb_link_node(&new_fn->rb_hash, parent, p);517 rb_insert_color(&new_fn->rb_hash, &info->root);518 return 0;519}520 521 522 523/*524 * This is a helper function for ext4_dx_readdir. It calls filldir525 * for all entries on the fname linked list. (Normally there is only526 * one entry on the linked list, unless there are 62 bit hash collisions.)527 */528static int call_filldir(struct file *file, struct dir_context *ctx,529 struct fname *fname)530{531 struct dir_private_info *info = file->private_data;532 struct inode *inode = file_inode(file);533 struct super_block *sb = inode->i_sb;534 535 if (!fname) {536 ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: comm %s: "537 "called with null fname?!?", __func__, __LINE__,538 inode->i_ino, current->comm);539 return 0;540 }541 ctx->pos = hash2pos(file, fname->hash, fname->minor_hash);542 while (fname) {543 if (!dir_emit(ctx, fname->name,544 fname->name_len,545 fname->inode,546 get_dtype(sb, fname->file_type))) {547 info->extra_fname = fname;548 return 1;549 }550 fname = fname->next;551 }552 return 0;553}554 555static int ext4_dx_readdir(struct file *file, struct dir_context *ctx)556{557 struct dir_private_info *info = file->private_data;558 struct inode *inode = file_inode(file);559 struct fname *fname;560 int ret = 0;561 562 ext4_htree_init_dir_info(file, ctx->pos);563 564 if (ctx->pos == ext4_get_htree_eof(file))565 return 0; /* EOF */566 567 /* Some one has messed with f_pos; reset the world */568 if (info->last_pos != ctx->pos) {569 free_rb_tree_fname(&info->root);570 info->curr_node = NULL;571 info->extra_fname = NULL;572 info->curr_hash = pos2maj_hash(file, ctx->pos);573 info->curr_minor_hash = pos2min_hash(file, ctx->pos);574 }575 576 /*577 * If there are any leftover names on the hash collision578 * chain, return them first.579 */580 if (info->extra_fname) {581 if (call_filldir(file, ctx, info->extra_fname))582 goto finished;583 info->extra_fname = NULL;584 goto next_node;585 } else if (!info->curr_node)586 info->curr_node = rb_first(&info->root);587 588 while (1) {589 /*590 * Fill the rbtree if we have no more entries,591 * or the inode has changed since we last read in the592 * cached entries.593 */594 if ((!info->curr_node) ||595 !inode_eq_iversion(inode, info->cookie)) {596 info->curr_node = NULL;597 free_rb_tree_fname(&info->root);598 info->cookie = inode_query_iversion(inode);599 ret = ext4_htree_fill_tree(file, info->curr_hash,600 info->curr_minor_hash,601 &info->next_hash);602 if (ret < 0)603 goto finished;604 if (ret == 0) {605 ctx->pos = ext4_get_htree_eof(file);606 break;607 }608 info->curr_node = rb_first(&info->root);609 }610 611 fname = rb_entry(info->curr_node, struct fname, rb_hash);612 info->curr_hash = fname->hash;613 info->curr_minor_hash = fname->minor_hash;614 if (call_filldir(file, ctx, fname))615 break;616 next_node:617 info->curr_node = rb_next(info->curr_node);618 if (info->curr_node) {619 fname = rb_entry(info->curr_node, struct fname,620 rb_hash);621 info->curr_hash = fname->hash;622 info->curr_minor_hash = fname->minor_hash;623 } else {624 if (info->next_hash == ~0) {625 ctx->pos = ext4_get_htree_eof(file);626 break;627 }628 info->curr_hash = info->next_hash;629 info->curr_minor_hash = 0;630 }631 }632finished:633 info->last_pos = ctx->pos;634 return ret < 0 ? ret : 0;635}636 637static int ext4_release_dir(struct inode *inode, struct file *filp)638{639 if (filp->private_data)640 ext4_htree_free_dir_info(filp->private_data);641 642 return 0;643}644 645int ext4_check_all_de(struct inode *dir, struct buffer_head *bh, void *buf,646 int buf_size)647{648 struct ext4_dir_entry_2 *de;649 int rlen;650 unsigned int offset = 0;651 char *top;652 653 de = buf;654 top = buf + buf_size;655 while ((char *) de < top) {656 if (ext4_check_dir_entry(dir, NULL, de, bh,657 buf, buf_size, offset))658 return -EFSCORRUPTED;659 rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);660 de = (struct ext4_dir_entry_2 *)((char *)de + rlen);661 offset += rlen;662 }663 if ((char *) de > top)664 return -EFSCORRUPTED;665 666 return 0;667}668 669static int ext4_dir_open(struct inode *inode, struct file *file)670{671 struct dir_private_info *info;672 673 info = kzalloc(sizeof(*info), GFP_KERNEL);674 if (!info)675 return -ENOMEM;676 file->private_data = info;677 return 0;678}679 680const struct file_operations ext4_dir_operations = {681 .open = ext4_dir_open,682 .llseek = ext4_dir_llseek,683 .read = generic_read_dir,684 .iterate_shared = ext4_readdir,685 .unlocked_ioctl = ext4_ioctl,686#ifdef CONFIG_COMPAT687 .compat_ioctl = ext4_compat_ioctl,688#endif689 .fsync = ext4_sync_file,690 .release = ext4_release_dir,691};692