dir.c 15.5 KB
Newer Older
1
/*
2
 *  linux/fs/ext4/dir.c
3 4 5 6 7 8 9 10 11 12 13 14
 *
 * Copyright (C) 1992, 1993, 1994, 1995
 * Remy Card (card@masi.ibp.fr)
 * Laboratoire MASI - Institut Blaise Pascal
 * Universite Pierre et Marie Curie (Paris VI)
 *
 *  from
 *
 *  linux/fs/minix/dir.c
 *
 *  Copyright (C) 1991, 1992  Linus Torvalds
 *
15
 *  ext4 directory handling functions
16 17 18 19 20 21 22 23 24 25 26
 *
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995
 *
 * Hash Tree Directory indexing (c) 2001  Daniel Phillips
 *
 */

#include <linux/fs.h>
#include <linux/buffer_head.h>
#include <linux/slab.h>
27
#include "ext4.h"
T
Tao Ma 已提交
28
#include "xattr.h"
29

A
Al Viro 已提交
30
static int ext4_dx_readdir(struct file *, struct dir_context *);
31

32 33
/**
 * Check if the given dir-inode refers to an htree-indexed directory
34
 * (or a directory which could potentially get converted to use htree
35 36 37 38 39 40 41 42 43 44 45
 * indexing).
 *
 * Return 1 if it is a dx dir, 0 if not
 */
static int is_dx_dir(struct inode *inode)
{
	struct super_block *sb = inode->i_sb;

	if (EXT4_HAS_COMPAT_FEATURE(inode->i_sb,
		     EXT4_FEATURE_COMPAT_DIR_INDEX) &&
	    ((ext4_test_inode_flag(inode, EXT4_INODE_INDEX)) ||
46 47
	     ((inode->i_size >> sb->s_blocksize_bits) == 1) ||
	     ext4_has_inline_data(inode)))
48 49 50 51 52
		return 1;

	return 0;
}

53 54 55 56
/*
 * Return 0 if the directory entry is OK, and 1 if there is a problem
 *
 * Note: this is the opposite of what ext2 and ext3 historically returned...
T
Tao Ma 已提交
57 58 59
 *
 * bh passed here can be an inode block or a dir data block, depending
 * on the inode inline data flag.
60
 */
61
int __ext4_check_dir_entry(const char *function, unsigned int line,
62
			   struct inode *dir, struct file *filp,
63
			   struct ext4_dir_entry_2 *de,
64
			   struct buffer_head *bh, char *buf, int size,
65
			   unsigned int offset)
66
{
67
	const char *error_msg = NULL;
68 69
	const int rlen = ext4_rec_len_from_disk(de->rec_len,
						dir->i_sb->s_blocksize);
70

71
	if (unlikely(rlen < EXT4_DIR_REC_LEN(1)))
72
		error_msg = "rec_len is smaller than minimal";
73
	else if (unlikely(rlen % 4 != 0))
74
		error_msg = "rec_len % 4 != 0";
75
	else if (unlikely(rlen < EXT4_DIR_REC_LEN(de->name_len)))
76
		error_msg = "rec_len is too small for name_len";
77 78
	else if (unlikely(((char *) de - buf) + rlen > size))
		error_msg = "directory entry across range";
79 80
	else if (unlikely(le32_to_cpu(de->inode) >
			le32_to_cpu(EXT4_SB(dir->i_sb)->s_es->s_inodes_count)))
81
		error_msg = "inode out of bounds";
82 83 84
	else
		return 0;

85
	if (filp)
86
		ext4_error_file(filp, function, line, bh->b_blocknr,
87 88
				"bad entry in directory: %s - offset=%u(%u), "
				"inode=%u, rec_len=%d, name_len=%d",
89
				error_msg, (unsigned) (offset % size),
90 91 92
				offset, le32_to_cpu(de->inode),
				rlen, de->name_len);
	else
93
		ext4_error_inode(dir, function, line, bh->b_blocknr,
94 95
				"bad entry in directory: %s - offset=%u(%u), "
				"inode=%u, rec_len=%d, name_len=%d",
96
				error_msg, (unsigned) (offset % size),
97 98 99
				offset, le32_to_cpu(de->inode),
				rlen, de->name_len);

100
	return 1;
101 102
}

A
Al Viro 已提交
103
static int ext4_readdir(struct file *file, struct dir_context *ctx)
104
{
105
	unsigned int offset;
106
	int i;
107
	struct ext4_dir_entry_2 *de;
108
	int err;
A
Al Viro 已提交
109
	struct inode *inode = file_inode(file);
110
	struct super_block *sb = inode->i_sb;
111
	int dir_has_error = 0;
112

113
	if (is_dx_dir(inode)) {
A
Al Viro 已提交
114
		err = ext4_dx_readdir(file, ctx);
115
		if (err != ERR_BAD_DX_DIR) {
A
Al Viro 已提交
116
			return err;
117 118 119 120 121
		}
		/*
		 * We don't set the inode dirty flag since it's not
		 * critical that it get flushed back to the disk.
		 */
A
Al Viro 已提交
122
		ext4_clear_inode_flag(file_inode(file),
123
				      EXT4_INODE_INDEX);
124
	}
125 126 127

	if (ext4_has_inline_data(inode)) {
		int has_inline_data = 1;
A
Al Viro 已提交
128
		int ret = ext4_read_inline_dir(file, ctx,
129 130 131 132 133
					   &has_inline_data);
		if (has_inline_data)
			return ret;
	}

A
Al Viro 已提交
134
	offset = ctx->pos & (sb->s_blocksize - 1);
135

A
Al Viro 已提交
136
	while (ctx->pos < inode->i_size) {
137
		struct ext4_map_blocks map;
138 139
		struct buffer_head *bh = NULL;

A
Al Viro 已提交
140
		map.m_lblk = ctx->pos >> EXT4_BLOCK_SIZE_BITS(sb);
141 142
		map.m_len = 1;
		err = ext4_map_blocks(NULL, inode, &map, 0);
143
		if (err > 0) {
144
			pgoff_t index = map.m_pblk >>
145
					(PAGE_CACHE_SHIFT - inode->i_blkbits);
A
Al Viro 已提交
146
			if (!ra_has_index(&file->f_ra, index))
147
				page_cache_sync_readahead(
148
					sb->s_bdev->bd_inode->i_mapping,
A
Al Viro 已提交
149
					&file->f_ra, file,
150
					index, 1);
A
Al Viro 已提交
151
			file->f_ra.prev_pos = (loff_t)index << PAGE_CACHE_SHIFT;
152 153 154
			bh = ext4_bread(NULL, inode, map.m_lblk, 0);
			if (IS_ERR(bh))
				return PTR_ERR(bh);
155 156 157
		}

		if (!bh) {
158
			if (!dir_has_error) {
A
Al Viro 已提交
159
				EXT4_ERROR_FILE(file, 0,
160 161
						"directory contains a "
						"hole at offset %llu",
A
Al Viro 已提交
162
					   (unsigned long long) ctx->pos);
163 164
				dir_has_error = 1;
			}
165
			/* corrupt size?  Maybe no more blocks to read */
A
Al Viro 已提交
166
			if (ctx->pos > inode->i_blocks << 9)
167
				break;
A
Al Viro 已提交
168
			ctx->pos += sb->s_blocksize - offset;
169 170 171
			continue;
		}

172 173 174 175
		/* Check the checksum */
		if (!buffer_verified(bh) &&
		    !ext4_dirent_csum_verify(inode,
				(struct ext4_dir_entry *)bh->b_data)) {
A
Al Viro 已提交
176
			EXT4_ERROR_FILE(file, 0, "directory fails checksum "
177
					"at offset %llu",
A
Al Viro 已提交
178 179
					(unsigned long long)ctx->pos);
			ctx->pos += sb->s_blocksize - offset;
180
			brelse(bh);
181 182 183 184
			continue;
		}
		set_buffer_verified(bh);

185 186 187 188
		/* If the dir block has changed since the last call to
		 * readdir(2), then we might be pointing to an invalid
		 * dirent right now.  Scan from the start of the block
		 * to make sure. */
A
Al Viro 已提交
189
		if (file->f_version != inode->i_version) {
190
			for (i = 0; i < sb->s_blocksize && i < offset; ) {
191
				de = (struct ext4_dir_entry_2 *)
192 193 194 195 196 197 198
					(bh->b_data + i);
				/* It's too expensive to do a full
				 * dirent test each time round this
				 * loop, but we do have to test at
				 * least that it is non-zero.  A
				 * failure will be detected in the
				 * dirent test below. */
199 200
				if (ext4_rec_len_from_disk(de->rec_len,
					sb->s_blocksize) < EXT4_DIR_REC_LEN(1))
201
					break;
202 203
				i += ext4_rec_len_from_disk(de->rec_len,
							    sb->s_blocksize);
204 205
			}
			offset = i;
A
Al Viro 已提交
206
			ctx->pos = (ctx->pos & ~(sb->s_blocksize - 1))
207
				| offset;
A
Al Viro 已提交
208
			file->f_version = inode->i_version;
209 210
		}

A
Al Viro 已提交
211
		while (ctx->pos < inode->i_size
212
		       && offset < sb->s_blocksize) {
213
			de = (struct ext4_dir_entry_2 *) (bh->b_data + offset);
A
Al Viro 已提交
214
			if (ext4_check_dir_entry(inode, file, de, bh,
215 216
						 bh->b_data, bh->b_size,
						 offset)) {
A
Andrew Morton 已提交
217
				/*
A
Al Viro 已提交
218
				 * On error, skip to the next block
A
Andrew Morton 已提交
219
				 */
A
Al Viro 已提交
220
				ctx->pos = (ctx->pos |
221
						(sb->s_blocksize - 1)) + 1;
A
Al Viro 已提交
222
				break;
223
			}
224 225
			offset += ext4_rec_len_from_disk(de->rec_len,
					sb->s_blocksize);
226
			if (le32_to_cpu(de->inode)) {
A
Al Viro 已提交
227
				if (!dir_emit(ctx, de->name,
228 229
						de->name_len,
						le32_to_cpu(de->inode),
A
Al Viro 已提交
230 231 232 233
						get_dtype(sb, de->file_type))) {
					brelse(bh);
					return 0;
				}
234
			}
A
Al Viro 已提交
235
			ctx->pos += ext4_rec_len_from_disk(de->rec_len,
236
						sb->s_blocksize);
237 238
		}
		offset = 0;
239
		brelse(bh);
A
Al Viro 已提交
240 241 242 243
		if (ctx->pos < inode->i_size) {
			if (!dir_relax(inode))
				return 0;
		}
244
	}
A
Al Viro 已提交
245
	return 0;
246 247
}

248 249 250 251 252 253 254 255 256
static inline int is_32bit_api(void)
{
#ifdef CONFIG_COMPAT
	return is_compat_task();
#else
	return (BITS_PER_LONG == 32);
#endif
}

257 258
/*
 * These functions convert from the major/minor hash to an f_pos
259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
 * value for dx directories
 *
 * Upper layer (for example NFS) should specify FMODE_32BITHASH or
 * FMODE_64BITHASH explicitly. On the other hand, we allow ext4 to be mounted
 * directly on both 32-bit and 64-bit nodes, under such case, neither
 * FMODE_32BITHASH nor FMODE_64BITHASH is specified.
 */
static inline loff_t hash2pos(struct file *filp, __u32 major, __u32 minor)
{
	if ((filp->f_mode & FMODE_32BITHASH) ||
	    (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
		return major >> 1;
	else
		return ((__u64)(major >> 1) << 32) | (__u64)minor;
}

static inline __u32 pos2maj_hash(struct file *filp, loff_t pos)
{
	if ((filp->f_mode & FMODE_32BITHASH) ||
	    (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
		return (pos << 1) & 0xffffffff;
	else
		return ((pos >> 32) << 1) & 0xffffffff;
}

static inline __u32 pos2min_hash(struct file *filp, loff_t pos)
{
	if ((filp->f_mode & FMODE_32BITHASH) ||
	    (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
		return 0;
	else
		return pos & 0xffffffff;
}

/*
 * Return 32- or 64-bit end-of-file for dx directories
 */
static inline loff_t ext4_get_htree_eof(struct file *filp)
{
	if ((filp->f_mode & FMODE_32BITHASH) ||
	    (!(filp->f_mode & FMODE_64BITHASH) && is_32bit_api()))
		return EXT4_HTREE_EOF_32BIT;
	else
		return EXT4_HTREE_EOF_64BIT;
}


/*
307 308 309
 * ext4_dir_llseek() calls generic_file_llseek_size to handle htree
 * directories, where the "offset" is in terms of the filename hash
 * value instead of the byte offset.
310
 *
311 312 313 314 315
 * Because we may return a 64-bit hash that is well beyond offset limits,
 * we need to pass the max hash as the maximum allowable offset in
 * the htree directory case.
 *
 * For non-htree, ext4_llseek already chooses the proper max offset.
316
 */
317
static loff_t ext4_dir_llseek(struct file *file, loff_t offset, int whence)
318 319 320
{
	struct inode *inode = file->f_mapping->host;
	int dx_dir = is_dx_dir(inode);
321
	loff_t htree_max = ext4_get_htree_eof(file);
322

323
	if (likely(dx_dir))
324
		return generic_file_llseek_size(file, offset, whence,
325 326
						    htree_max, htree_max);
	else
327
		return ext4_llseek(file, offset, whence);
328
}
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350

/*
 * This structure holds the nodes of the red-black tree used to store
 * the directory entry in hash order.
 */
struct fname {
	__u32		hash;
	__u32		minor_hash;
	struct rb_node	rb_hash;
	struct fname	*next;
	__u32		inode;
	__u8		name_len;
	__u8		file_type;
	char		name[0];
};

/*
 * This functoin implements a non-recursive way of freeing all of the
 * nodes in the red-black tree.
 */
static void free_rb_tree_fname(struct rb_root *root)
{
351 352 353
	struct fname *fname, *next;

	rbtree_postorder_for_each_entry_safe(fname, next, root, rb_hash)
354
		while (fname) {
355
			struct fname *old = fname;
356
			fname = fname->next;
357
			kfree(old);
358
		}
359 360

	*root = RB_ROOT;
361 362 363
}


364 365
static struct dir_private_info *ext4_htree_create_dir_info(struct file *filp,
							   loff_t pos)
366 367 368
{
	struct dir_private_info *p;

369
	p = kzalloc(sizeof(struct dir_private_info), GFP_KERNEL);
370 371
	if (!p)
		return NULL;
372 373
	p->curr_hash = pos2maj_hash(filp, pos);
	p->curr_minor_hash = pos2min_hash(filp, pos);
374 375 376
	return p;
}

377
void ext4_htree_free_dir_info(struct dir_private_info *p)
378 379 380 381 382 383 384 385
{
	free_rb_tree_fname(&p->root);
	kfree(p);
}

/*
 * Given a directory entry, enter it into the fname rb tree.
 */
386
int ext4_htree_store_dirent(struct file *dir_file, __u32 hash,
387
			     __u32 minor_hash,
388
			     struct ext4_dir_entry_2 *dirent)
389 390
{
	struct rb_node **p, *parent = NULL;
391
	struct fname *fname, *new_fn;
392 393 394
	struct dir_private_info *info;
	int len;

395
	info = dir_file->private_data;
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443
	p = &info->root.rb_node;

	/* Create and allocate the fname structure */
	len = sizeof(struct fname) + dirent->name_len + 1;
	new_fn = kzalloc(len, GFP_KERNEL);
	if (!new_fn)
		return -ENOMEM;
	new_fn->hash = hash;
	new_fn->minor_hash = minor_hash;
	new_fn->inode = le32_to_cpu(dirent->inode);
	new_fn->name_len = dirent->name_len;
	new_fn->file_type = dirent->file_type;
	memcpy(new_fn->name, dirent->name, dirent->name_len);
	new_fn->name[dirent->name_len] = 0;

	while (*p) {
		parent = *p;
		fname = rb_entry(parent, struct fname, rb_hash);

		/*
		 * If the hash and minor hash match up, then we put
		 * them on a linked list.  This rarely happens...
		 */
		if ((new_fn->hash == fname->hash) &&
		    (new_fn->minor_hash == fname->minor_hash)) {
			new_fn->next = fname->next;
			fname->next = new_fn;
			return 0;
		}

		if (new_fn->hash < fname->hash)
			p = &(*p)->rb_left;
		else if (new_fn->hash > fname->hash)
			p = &(*p)->rb_right;
		else if (new_fn->minor_hash < fname->minor_hash)
			p = &(*p)->rb_left;
		else /* if (new_fn->minor_hash > fname->minor_hash) */
			p = &(*p)->rb_right;
	}

	rb_link_node(&new_fn->rb_hash, parent, p);
	rb_insert_color(&new_fn->rb_hash, &info->root);
	return 0;
}



/*
444
 * This is a helper function for ext4_dx_readdir.  It calls filldir
445 446 447
 * for all entres on the fname linked list.  (Normally there is only
 * one entry on the linked list, unless there are 62 bit hash collisions.)
 */
A
Al Viro 已提交
448 449
static int call_filldir(struct file *file, struct dir_context *ctx,
			struct fname *fname)
450
{
A
Al Viro 已提交
451 452 453
	struct dir_private_info *info = file->private_data;
	struct inode *inode = file_inode(file);
	struct super_block *sb = inode->i_sb;
454 455

	if (!fname) {
456 457 458
		ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: comm %s: "
			 "called with null fname?!?", __func__, __LINE__,
			 inode->i_ino, current->comm);
459 460
		return 0;
	}
A
Al Viro 已提交
461
	ctx->pos = hash2pos(file, fname->hash, fname->minor_hash);
462
	while (fname) {
A
Al Viro 已提交
463 464
		if (!dir_emit(ctx, fname->name,
				fname->name_len,
465
				fname->inode,
A
Al Viro 已提交
466
				get_dtype(sb, fname->file_type))) {
467
			info->extra_fname = fname;
A
Al Viro 已提交
468
			return 1;
469 470 471 472 473 474
		}
		fname = fname->next;
	}
	return 0;
}

A
Al Viro 已提交
475
static int ext4_dx_readdir(struct file *file, struct dir_context *ctx)
476
{
A
Al Viro 已提交
477 478
	struct dir_private_info *info = file->private_data;
	struct inode *inode = file_inode(file);
479 480 481 482
	struct fname *fname;
	int	ret;

	if (!info) {
A
Al Viro 已提交
483
		info = ext4_htree_create_dir_info(file, ctx->pos);
484 485
		if (!info)
			return -ENOMEM;
A
Al Viro 已提交
486
		file->private_data = info;
487 488
	}

A
Al Viro 已提交
489
	if (ctx->pos == ext4_get_htree_eof(file))
490 491 492
		return 0;	/* EOF */

	/* Some one has messed with f_pos; reset the world */
A
Al Viro 已提交
493
	if (info->last_pos != ctx->pos) {
494 495 496
		free_rb_tree_fname(&info->root);
		info->curr_node = NULL;
		info->extra_fname = NULL;
A
Al Viro 已提交
497 498
		info->curr_hash = pos2maj_hash(file, ctx->pos);
		info->curr_minor_hash = pos2min_hash(file, ctx->pos);
499 500 501 502 503 504
	}

	/*
	 * If there are any leftover names on the hash collision
	 * chain, return them first.
	 */
505
	if (info->extra_fname) {
A
Al Viro 已提交
506
		if (call_filldir(file, ctx, info->extra_fname))
507 508
			goto finished;
		info->extra_fname = NULL;
509
		goto next_node;
510
	} else if (!info->curr_node)
511 512 513 514 515 516 517 518 519
		info->curr_node = rb_first(&info->root);

	while (1) {
		/*
		 * Fill the rbtree if we have no more entries,
		 * or the inode has changed since we last read in the
		 * cached entries.
		 */
		if ((!info->curr_node) ||
A
Al Viro 已提交
520
		    (file->f_version != inode->i_version)) {
521 522
			info->curr_node = NULL;
			free_rb_tree_fname(&info->root);
A
Al Viro 已提交
523 524
			file->f_version = inode->i_version;
			ret = ext4_htree_fill_tree(file, info->curr_hash,
525 526 527 528 529
						   info->curr_minor_hash,
						   &info->next_hash);
			if (ret < 0)
				return ret;
			if (ret == 0) {
A
Al Viro 已提交
530
				ctx->pos = ext4_get_htree_eof(file);
531 532 533 534 535 536 537 538
				break;
			}
			info->curr_node = rb_first(&info->root);
		}

		fname = rb_entry(info->curr_node, struct fname, rb_hash);
		info->curr_hash = fname->hash;
		info->curr_minor_hash = fname->minor_hash;
A
Al Viro 已提交
539
		if (call_filldir(file, ctx, fname))
540
			break;
541
	next_node:
542
		info->curr_node = rb_next(info->curr_node);
543 544 545 546 547 548
		if (info->curr_node) {
			fname = rb_entry(info->curr_node, struct fname,
					 rb_hash);
			info->curr_hash = fname->hash;
			info->curr_minor_hash = fname->minor_hash;
		} else {
549
			if (info->next_hash == ~0) {
A
Al Viro 已提交
550
				ctx->pos = ext4_get_htree_eof(file);
551 552 553 554 555 556 557
				break;
			}
			info->curr_hash = info->next_hash;
			info->curr_minor_hash = 0;
		}
	}
finished:
A
Al Viro 已提交
558
	info->last_pos = ctx->pos;
559 560 561
	return 0;
}

562
static int ext4_release_dir(struct inode *inode, struct file *filp)
563
{
A
Andrew Morton 已提交
564
	if (filp->private_data)
565
		ext4_htree_free_dir_info(filp->private_data);
566 567 568

	return 0;
}
569

570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594
int ext4_check_all_de(struct inode *dir, struct buffer_head *bh, void *buf,
		      int buf_size)
{
	struct ext4_dir_entry_2 *de;
	int nlen, rlen;
	unsigned int offset = 0;
	char *top;

	de = (struct ext4_dir_entry_2 *)buf;
	top = buf + buf_size;
	while ((char *) de < top) {
		if (ext4_check_dir_entry(dir, NULL, de, bh,
					 buf, buf_size, offset))
			return -EIO;
		nlen = EXT4_DIR_REC_LEN(de->name_len);
		rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
		de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
		offset += rlen;
	}
	if ((char *) de > top)
		return -EIO;

	return 0;
}

595 596 597
const struct file_operations ext4_dir_operations = {
	.llseek		= ext4_dir_llseek,
	.read		= generic_read_dir,
A
Al Viro 已提交
598
	.iterate	= ext4_readdir,
599 600 601 602 603 604 605
	.unlocked_ioctl = ext4_ioctl,
#ifdef CONFIG_COMPAT
	.compat_ioctl	= ext4_compat_ioctl,
#endif
	.fsync		= ext4_sync_file,
	.release	= ext4_release_dir,
};