namei.c 85.4 KB
Newer Older
1
/*
2
 *  linux/fs/ext4/namei.c
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
 *
 * 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/namei.c
 *
 *  Copyright (C) 1991, 1992  Linus Torvalds
 *
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995
 *  Directory entry file type support and forward compatibility hooks
 *	for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998
 *  Hash Tree Directory indexing (c)
 *	Daniel Phillips, 2001
 *  Hash Tree Directory indexing porting
 *	Christopher Li, 2002
 *  Hash Tree Directory indexing cleanup
 *	Theodore Ts'o, 2002
 */

#include <linux/fs.h>
#include <linux/pagemap.h>
29
#include <linux/jbd2.h>
30 31 32 33 34 35 36
#include <linux/time.h>
#include <linux/fcntl.h>
#include <linux/stat.h>
#include <linux/string.h>
#include <linux/quotaops.h>
#include <linux/buffer_head.h>
#include <linux/bio.h>
37 38
#include "ext4.h"
#include "ext4_jbd2.h"
39 40 41 42

#include "xattr.h"
#include "acl.h"

43
#include <trace/events/ext4.h>
44 45 46 47 48
/*
 * define how far ahead to read directories while searching them.
 */
#define NAMEI_RA_CHUNKS  2
#define NAMEI_RA_BLOCKS  4
D
Dave Kleikamp 已提交
49
#define NAMEI_RA_SIZE	     (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
50 51
#define NAMEI_RA_INDEX(c,b)  (((c) * NAMEI_RA_BLOCKS) + (b))

52
static struct buffer_head *ext4_append(handle_t *handle,
53
					struct inode *inode,
A
Aneesh Kumar K.V 已提交
54
					ext4_lblk_t *block, int *err)
55 56 57
{
	struct buffer_head *bh;

58 59 60 61 62 63 64
	if (unlikely(EXT4_SB(inode->i_sb)->s_max_dir_size_kb &&
		     ((inode->i_size >> 10) >=
		      EXT4_SB(inode->i_sb)->s_max_dir_size_kb))) {
		*err = -ENOSPC;
		return NULL;
	}

65 66
	*block = inode->i_size >> inode->i_sb->s_blocksize_bits;

67 68
	bh = ext4_bread(handle, inode, *block, 1, err);
	if (bh) {
69
		inode->i_size += inode->i_sb->s_blocksize;
70
		EXT4_I(inode)->i_disksize = inode->i_size;
71 72 73 74 75
		*err = ext4_journal_get_write_access(handle, bh);
		if (*err) {
			brelse(bh);
			bh = NULL;
		}
76
	}
C
Carlos Maiolino 已提交
77 78 79 80 81 82
	if (!bh && !(*err)) {
		*err = -EIO;
		ext4_error(inode->i_sb,
			   "Directory hole detected on inode %lu\n",
			   inode->i_ino);
	}
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
	return bh;
}

#ifndef assert
#define assert(test) J_ASSERT(test)
#endif

#ifdef DX_DEBUG
#define dxtrace(command) command
#else
#define dxtrace(command)
#endif

struct fake_dirent
{
	__le32 inode;
	__le16 rec_len;
	u8 name_len;
	u8 file_type;
};

struct dx_countlimit
{
	__le16 limit;
	__le16 count;
};

struct dx_entry
{
	__le32 hash;
	__le32 block;
};

/*
 * dx_root_info is laid out so that if it should somehow get overlaid by a
 * dirent the two low bits of the hash version will be zero.  Therefore, the
 * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
 */

struct dx_root
{
	struct fake_dirent dot;
	char dot_name[4];
	struct fake_dirent dotdot;
	char dotdot_name[4];
	struct dx_root_info
	{
		__le32 reserved_zero;
		u8 hash_version;
		u8 info_length; /* 8 */
		u8 indirect_levels;
		u8 unused_flags;
	}
	info;
	struct dx_entry	entries[0];
};

struct dx_node
{
	struct fake_dirent fake;
	struct dx_entry	entries[0];
};


struct dx_frame
{
	struct buffer_head *bh;
	struct dx_entry *entries;
	struct dx_entry *at;
};

struct dx_map_entry
{
	u32 hash;
157 158
	u16 offs;
	u16 size;
159 160
};

161 162 163 164 165 166 167 168
/*
 * This goes at the end of each htree block.
 */
struct dx_tail {
	u32 dt_reserved;
	__le32 dt_checksum;	/* crc32c(uuid+inum+dirblock) */
};

A
Aneesh Kumar K.V 已提交
169 170
static inline ext4_lblk_t dx_get_block(struct dx_entry *entry);
static void dx_set_block(struct dx_entry *entry, ext4_lblk_t value);
171 172 173 174 175 176 177 178
static inline unsigned dx_get_hash(struct dx_entry *entry);
static void dx_set_hash(struct dx_entry *entry, unsigned value);
static unsigned dx_get_count(struct dx_entry *entries);
static unsigned dx_get_limit(struct dx_entry *entries);
static void dx_set_count(struct dx_entry *entries, unsigned value);
static void dx_set_limit(struct dx_entry *entries, unsigned value);
static unsigned dx_root_limit(struct inode *dir, unsigned infosize);
static unsigned dx_node_limit(struct inode *dir);
179
static struct dx_frame *dx_probe(const struct qstr *d_name,
180 181 182 183
				 struct inode *dir,
				 struct dx_hash_info *hinfo,
				 struct dx_frame *frame,
				 int *err);
184
static void dx_release(struct dx_frame *frames);
185
static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
186
		       struct dx_hash_info *hinfo, struct dx_map_entry map[]);
187
static void dx_sort_map(struct dx_map_entry *map, unsigned count);
188
static struct ext4_dir_entry_2 *dx_move_dirents(char *from, char *to,
189
		struct dx_map_entry *offsets, int count, unsigned blocksize);
190
static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize);
A
Aneesh Kumar K.V 已提交
191 192
static void dx_insert_block(struct dx_frame *frame,
					u32 hash, ext4_lblk_t block);
193
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
194 195 196
				 struct dx_frame *frame,
				 struct dx_frame *frames,
				 __u32 *start_hash);
197 198 199 200
static struct buffer_head * ext4_dx_find_entry(struct inode *dir,
		const struct qstr *d_name,
		struct ext4_dir_entry_2 **res_dir,
		int *err);
201
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
202 203
			     struct inode *inode);

204
/* checksumming functions */
205 206
void initialize_dirent_tail(struct ext4_dir_entry_tail *t,
			    unsigned int blocksize)
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
{
	memset(t, 0, sizeof(struct ext4_dir_entry_tail));
	t->det_rec_len = ext4_rec_len_to_disk(
			sizeof(struct ext4_dir_entry_tail), blocksize);
	t->det_reserved_ft = EXT4_FT_DIR_CSUM;
}

/* Walk through a dirent block to find a checksum "dirent" at the tail */
static struct ext4_dir_entry_tail *get_dirent_tail(struct inode *inode,
						   struct ext4_dir_entry *de)
{
	struct ext4_dir_entry_tail *t;

#ifdef PARANOID
	struct ext4_dir_entry *d, *top;

	d = de;
	top = (struct ext4_dir_entry *)(((void *)de) +
		(EXT4_BLOCK_SIZE(inode->i_sb) -
		sizeof(struct ext4_dir_entry_tail)));
	while (d < top && d->rec_len)
		d = (struct ext4_dir_entry *)(((void *)d) +
		    le16_to_cpu(d->rec_len));

	if (d != top)
		return NULL;

	t = (struct ext4_dir_entry_tail *)d;
#else
	t = EXT4_DIRENT_TAIL(de, EXT4_BLOCK_SIZE(inode->i_sb));
#endif

	if (t->det_reserved_zero1 ||
	    le16_to_cpu(t->det_rec_len) != sizeof(struct ext4_dir_entry_tail) ||
	    t->det_reserved_zero2 ||
	    t->det_reserved_ft != EXT4_FT_DIR_CSUM)
		return NULL;

	return t;
}

static __le32 ext4_dirent_csum(struct inode *inode,
			       struct ext4_dir_entry *dirent, int size)
{
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
	struct ext4_inode_info *ei = EXT4_I(inode);
	__u32 csum;

	csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)dirent, size);
	return cpu_to_le32(csum);
}

259 260 261 262 263 264
static void warn_no_space_for_csum(struct inode *inode)
{
	ext4_warning(inode->i_sb, "no space in directory inode %lu leaf for "
		     "checksum.  Please run e2fsck -D.", inode->i_ino);
}

265 266 267 268 269 270 271 272 273 274
int ext4_dirent_csum_verify(struct inode *inode, struct ext4_dir_entry *dirent)
{
	struct ext4_dir_entry_tail *t;

	if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
					EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		return 1;

	t = get_dirent_tail(inode, dirent);
	if (!t) {
275
		warn_no_space_for_csum(inode);
276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
		return 0;
	}

	if (t->det_checksum != ext4_dirent_csum(inode, dirent,
						(void *)t - (void *)dirent))
		return 0;

	return 1;
}

static void ext4_dirent_csum_set(struct inode *inode,
				 struct ext4_dir_entry *dirent)
{
	struct ext4_dir_entry_tail *t;

	if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
					EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		return;

	t = get_dirent_tail(inode, dirent);
	if (!t) {
297
		warn_no_space_for_csum(inode);
298 299 300 301 302 303 304
		return;
	}

	t->det_checksum = ext4_dirent_csum(inode, dirent,
					   (void *)t - (void *)dirent);
}

305 306 307
int ext4_handle_dirty_dirent_node(handle_t *handle,
				  struct inode *inode,
				  struct buffer_head *bh)
308 309 310 311 312
{
	ext4_dirent_csum_set(inode, (struct ext4_dir_entry *)bh->b_data);
	return ext4_handle_dirty_metadata(handle, inode, bh);
}

313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
static struct dx_countlimit *get_dx_countlimit(struct inode *inode,
					       struct ext4_dir_entry *dirent,
					       int *offset)
{
	struct ext4_dir_entry *dp;
	struct dx_root_info *root;
	int count_offset;

	if (le16_to_cpu(dirent->rec_len) == EXT4_BLOCK_SIZE(inode->i_sb))
		count_offset = 8;
	else if (le16_to_cpu(dirent->rec_len) == 12) {
		dp = (struct ext4_dir_entry *)(((void *)dirent) + 12);
		if (le16_to_cpu(dp->rec_len) !=
		    EXT4_BLOCK_SIZE(inode->i_sb) - 12)
			return NULL;
		root = (struct dx_root_info *)(((void *)dp + 12));
		if (root->reserved_zero ||
		    root->info_length != sizeof(struct dx_root_info))
			return NULL;
		count_offset = 32;
	} else
		return NULL;

	if (offset)
		*offset = count_offset;
	return (struct dx_countlimit *)(((void *)dirent) + count_offset);
}

static __le32 ext4_dx_csum(struct inode *inode, struct ext4_dir_entry *dirent,
			   int count_offset, int count, struct dx_tail *t)
{
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
	struct ext4_inode_info *ei = EXT4_I(inode);
	__u32 csum, old_csum;
	int size;

	size = count_offset + (count * sizeof(struct dx_entry));
	old_csum = t->dt_checksum;
	t->dt_checksum = 0;
	csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)dirent, size);
	csum = ext4_chksum(sbi, csum, (__u8 *)t, sizeof(struct dx_tail));
	t->dt_checksum = old_csum;

	return cpu_to_le32(csum);
}

static int ext4_dx_csum_verify(struct inode *inode,
			       struct ext4_dir_entry *dirent)
{
	struct dx_countlimit *c;
	struct dx_tail *t;
	int count_offset, limit, count;

	if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
					EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		return 1;

	c = get_dx_countlimit(inode, dirent, &count_offset);
	if (!c) {
		EXT4_ERROR_INODE(inode, "dir seems corrupt?  Run e2fsck -D.");
		return 1;
	}
	limit = le16_to_cpu(c->limit);
	count = le16_to_cpu(c->count);
	if (count_offset + (limit * sizeof(struct dx_entry)) >
	    EXT4_BLOCK_SIZE(inode->i_sb) - sizeof(struct dx_tail)) {
379
		warn_no_space_for_csum(inode);
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
		return 1;
	}
	t = (struct dx_tail *)(((struct dx_entry *)c) + limit);

	if (t->dt_checksum != ext4_dx_csum(inode, dirent, count_offset,
					    count, t))
		return 0;
	return 1;
}

static void ext4_dx_csum_set(struct inode *inode, struct ext4_dir_entry *dirent)
{
	struct dx_countlimit *c;
	struct dx_tail *t;
	int count_offset, limit, count;

	if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
					EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		return;

	c = get_dx_countlimit(inode, dirent, &count_offset);
	if (!c) {
		EXT4_ERROR_INODE(inode, "dir seems corrupt?  Run e2fsck -D.");
		return;
	}
	limit = le16_to_cpu(c->limit);
	count = le16_to_cpu(c->count);
	if (count_offset + (limit * sizeof(struct dx_entry)) >
	    EXT4_BLOCK_SIZE(inode->i_sb) - sizeof(struct dx_tail)) {
409
		warn_no_space_for_csum(inode);
410 411 412 413 414 415 416 417 418 419 420 421 422 423 424
		return;
	}
	t = (struct dx_tail *)(((struct dx_entry *)c) + limit);

	t->dt_checksum = ext4_dx_csum(inode, dirent, count_offset, count, t);
}

static inline int ext4_handle_dirty_dx_node(handle_t *handle,
					    struct inode *inode,
					    struct buffer_head *bh)
{
	ext4_dx_csum_set(inode, (struct ext4_dir_entry *)bh->b_data);
	return ext4_handle_dirty_metadata(handle, inode, bh);
}

425 426 427 428
/*
 * p is at least 6 bytes before the end of page
 */
static inline struct ext4_dir_entry_2 *
429
ext4_next_entry(struct ext4_dir_entry_2 *p, unsigned long blocksize)
430 431
{
	return (struct ext4_dir_entry_2 *)((char *)p +
432
		ext4_rec_len_from_disk(p->rec_len, blocksize));
433 434
}

435 436 437 438 439
/*
 * Future: use high four bits of block for coalesce-on-delete flags
 * Mask them off for now.
 */

A
Aneesh Kumar K.V 已提交
440
static inline ext4_lblk_t dx_get_block(struct dx_entry *entry)
441 442 443 444
{
	return le32_to_cpu(entry->block) & 0x00ffffff;
}

A
Aneesh Kumar K.V 已提交
445
static inline void dx_set_block(struct dx_entry *entry, ext4_lblk_t value)
446 447 448 449
{
	entry->block = cpu_to_le32(value);
}

450
static inline unsigned dx_get_hash(struct dx_entry *entry)
451 452 453 454
{
	return le32_to_cpu(entry->hash);
}

455
static inline void dx_set_hash(struct dx_entry *entry, unsigned value)
456 457 458 459
{
	entry->hash = cpu_to_le32(value);
}

460
static inline unsigned dx_get_count(struct dx_entry *entries)
461 462 463 464
{
	return le16_to_cpu(((struct dx_countlimit *) entries)->count);
}

465
static inline unsigned dx_get_limit(struct dx_entry *entries)
466 467 468 469
{
	return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
}

470
static inline void dx_set_count(struct dx_entry *entries, unsigned value)
471 472 473 474
{
	((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
}

475
static inline void dx_set_limit(struct dx_entry *entries, unsigned value)
476 477 478 479
{
	((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
}

480
static inline unsigned dx_root_limit(struct inode *dir, unsigned infosize)
481
{
482 483
	unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(1) -
		EXT4_DIR_REC_LEN(2) - infosize;
484 485 486 487

	if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		entry_space -= sizeof(struct dx_tail);
488
	return entry_space / sizeof(struct dx_entry);
489 490
}

491
static inline unsigned dx_node_limit(struct inode *dir)
492
{
493
	unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(0);
494 495 496 497

	if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		entry_space -= sizeof(struct dx_tail);
498
	return entry_space / sizeof(struct dx_entry);
499 500 501 502 503 504
}

/*
 * Debug
 */
#ifdef DX_DEBUG
505
static void dx_show_index(char * label, struct dx_entry *entries)
506
{
A
Andrew Morton 已提交
507
	int i, n = dx_get_count (entries);
508
	printk(KERN_DEBUG "%s index ", label);
A
Andrew Morton 已提交
509
	for (i = 0; i < n; i++) {
510
		printk("%x->%lu ", i ? dx_get_hash(entries + i) :
A
Aneesh Kumar K.V 已提交
511
				0, (unsigned long)dx_get_block(entries + i));
A
Andrew Morton 已提交
512 513
	}
	printk("\n");
514 515 516 517 518 519 520 521 522
}

struct stats
{
	unsigned names;
	unsigned space;
	unsigned bcount;
};

523
static struct stats dx_show_leaf(struct dx_hash_info *hinfo, struct ext4_dir_entry_2 *de,
524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
				 int size, int show_names)
{
	unsigned names = 0, space = 0;
	char *base = (char *) de;
	struct dx_hash_info h = *hinfo;

	printk("names: ");
	while ((char *) de < base + size)
	{
		if (de->inode)
		{
			if (show_names)
			{
				int len = de->name_len;
				char *name = de->name;
				while (len--) printk("%c", *name++);
540
				ext4fs_dirhash(de->name, de->name_len, &h);
541
				printk(":%x.%u ", h.hash,
542
				       (unsigned) ((char *) de - base));
543
			}
544
			space += EXT4_DIR_REC_LEN(de->name_len);
545 546
			names++;
		}
547
		de = ext4_next_entry(de, size);
548 549 550 551 552 553 554 555 556
	}
	printk("(%i)\n", names);
	return (struct stats) { names, space, 1 };
}

struct stats dx_show_entries(struct dx_hash_info *hinfo, struct inode *dir,
			     struct dx_entry *entries, int levels)
{
	unsigned blocksize = dir->i_sb->s_blocksize;
557
	unsigned count = dx_get_count(entries), names = 0, space = 0, i;
558 559 560 561 562 563
	unsigned bcount = 0;
	struct buffer_head *bh;
	int err;
	printk("%i indexed blocks...\n", count);
	for (i = 0; i < count; i++, entries++)
	{
A
Aneesh Kumar K.V 已提交
564 565
		ext4_lblk_t block = dx_get_block(entries);
		ext4_lblk_t hash  = i ? dx_get_hash(entries): 0;
566 567 568
		u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
		struct stats stats;
		printk("%s%3u:%03u hash %8x/%8x ",levels?"":"   ", i, block, hash, range);
569
		if (!(bh = ext4_bread (NULL,dir, block, 0,&err))) continue;
570 571
		stats = levels?
		   dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
572
		   dx_show_leaf(hinfo, (struct ext4_dir_entry_2 *) bh->b_data, blocksize, 0);
573 574 575
		names += stats.names;
		space += stats.space;
		bcount += stats.bcount;
576
		brelse(bh);
577 578
	}
	if (bcount)
579
		printk(KERN_DEBUG "%snames %u, fullness %u (%u%%)\n",
580 581
		       levels ? "" : "   ", names, space/bcount,
		       (space/bcount)*100/blocksize);
582 583 584 585 586 587 588 589 590 591 592 593 594 595
	return (struct stats) { names, space, bcount};
}
#endif /* DX_DEBUG */

/*
 * Probe for a directory leaf block to search.
 *
 * dx_probe can return ERR_BAD_DX_DIR, which means there was a format
 * error in the directory index, and the caller should fall back to
 * searching the directory normally.  The callers of dx_probe **MUST**
 * check for this error code, and make sure it never gets reflected
 * back to userspace.
 */
static struct dx_frame *
596
dx_probe(const struct qstr *d_name, struct inode *dir,
597 598 599 600 601 602 603 604 605 606
	 struct dx_hash_info *hinfo, struct dx_frame *frame_in, int *err)
{
	unsigned count, indirect;
	struct dx_entry *at, *entries, *p, *q, *m;
	struct dx_root *root;
	struct buffer_head *bh;
	struct dx_frame *frame = frame_in;
	u32 hash;

	frame->bh = NULL;
C
Carlos Maiolino 已提交
607 608 609
	if (!(bh = ext4_bread(NULL, dir, 0, 0, err))) {
		if (*err == 0)
			*err = ERR_BAD_DX_DIR;
610
		goto fail;
C
Carlos Maiolino 已提交
611
	}
612 613 614 615
	root = (struct dx_root *) bh->b_data;
	if (root->info.hash_version != DX_HASH_TEA &&
	    root->info.hash_version != DX_HASH_HALF_MD4 &&
	    root->info.hash_version != DX_HASH_LEGACY) {
616
		ext4_warning(dir->i_sb, "Unrecognised inode hash code %d",
617 618 619 620 621 622
			     root->info.hash_version);
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}
	hinfo->hash_version = root->info.hash_version;
623 624
	if (hinfo->hash_version <= DX_HASH_TEA)
		hinfo->hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
625
	hinfo->seed = EXT4_SB(dir->i_sb)->s_hash_seed;
626 627
	if (d_name)
		ext4fs_dirhash(d_name->name, d_name->len, hinfo);
628 629 630
	hash = hinfo->hash;

	if (root->info.unused_flags & 1) {
631
		ext4_warning(dir->i_sb, "Unimplemented inode hash flags: %#06x",
632 633 634 635 636 637 638
			     root->info.unused_flags);
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}

	if ((indirect = root->info.indirect_levels) > 1) {
639
		ext4_warning(dir->i_sb, "Unimplemented inode hash depth: %#06x",
640 641 642 643 644 645
			     root->info.indirect_levels);
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}

646 647 648 649 650 651 652 653 654
	if (!buffer_verified(bh) &&
	    !ext4_dx_csum_verify(dir, (struct ext4_dir_entry *)bh->b_data)) {
		ext4_warning(dir->i_sb, "Root failed checksum");
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}
	set_buffer_verified(bh);

655 656
	entries = (struct dx_entry *) (((char *)&root->info) +
				       root->info.info_length);
657 658 659

	if (dx_get_limit(entries) != dx_root_limit(dir,
						   root->info.info_length)) {
660
		ext4_warning(dir->i_sb, "dx entry: limit != root limit");
661 662 663 664 665
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}

666
	dxtrace(printk("Look up %x", hash));
667 668 669
	while (1)
	{
		count = dx_get_count(entries);
670
		if (!count || count > dx_get_limit(entries)) {
671
			ext4_warning(dir->i_sb,
672 673 674 675 676 677
				     "dx entry: no count or count > limit");
			brelse(bh);
			*err = ERR_BAD_DX_DIR;
			goto fail2;
		}

678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
		p = entries + 1;
		q = entries + count - 1;
		while (p <= q)
		{
			m = p + (q - p)/2;
			dxtrace(printk("."));
			if (dx_get_hash(m) > hash)
				q = m - 1;
			else
				p = m + 1;
		}

		if (0) // linear search cross check
		{
			unsigned n = count - 1;
			at = entries;
			while (n--)
			{
				dxtrace(printk(","));
				if (dx_get_hash(++at) > hash)
				{
					at--;
					break;
				}
			}
			assert (at == p - 1);
		}

		at = p - 1;
		dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
		frame->bh = bh;
		frame->entries = entries;
		frame->at = at;
		if (!indirect--) return frame;
C
Carlos Maiolino 已提交
712 713 714
		if (!(bh = ext4_bread(NULL, dir, dx_get_block(at), 0, err))) {
			if (!(*err))
				*err = ERR_BAD_DX_DIR;
715
			goto fail2;
C
Carlos Maiolino 已提交
716
		}
717
		at = entries = ((struct dx_node *) bh->b_data)->entries;
718 719 720 721 722 723 724 725 726 727 728

		if (!buffer_verified(bh) &&
		    !ext4_dx_csum_verify(dir,
					 (struct ext4_dir_entry *)bh->b_data)) {
			ext4_warning(dir->i_sb, "Node failed checksum");
			brelse(bh);
			*err = ERR_BAD_DX_DIR;
			goto fail;
		}
		set_buffer_verified(bh);

729
		if (dx_get_limit(entries) != dx_node_limit (dir)) {
730
			ext4_warning(dir->i_sb,
731 732 733 734 735
				     "dx entry: limit != node limit");
			brelse(bh);
			*err = ERR_BAD_DX_DIR;
			goto fail2;
		}
736
		frame++;
737
		frame->bh = NULL;
738 739 740 741 742 743 744
	}
fail2:
	while (frame >= frame_in) {
		brelse(frame->bh);
		frame--;
	}
fail:
745
	if (*err == ERR_BAD_DX_DIR)
746
		ext4_warning(dir->i_sb,
Z
Zheng Liu 已提交
747
			     "Corrupt dir inode %lu, running e2fsck is "
748
			     "recommended.", dir->i_ino);
749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778
	return NULL;
}

static void dx_release (struct dx_frame *frames)
{
	if (frames[0].bh == NULL)
		return;

	if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
		brelse(frames[1].bh);
	brelse(frames[0].bh);
}

/*
 * This function increments the frame pointer to search the next leaf
 * block, and reads in the necessary intervening nodes if the search
 * should be necessary.  Whether or not the search is necessary is
 * controlled by the hash parameter.  If the hash value is even, then
 * the search is only continued if the next block starts with that
 * hash value.  This is used if we are searching for a specific file.
 *
 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
 *
 * This function returns 1 if the caller should continue to search,
 * or 0 if it should not.  If there is an error reading one of the
 * index blocks, it will a negative error code.
 *
 * If start_hash is non-null, it will be filled in with the starting
 * hash of the next page.
 */
779
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824
				 struct dx_frame *frame,
				 struct dx_frame *frames,
				 __u32 *start_hash)
{
	struct dx_frame *p;
	struct buffer_head *bh;
	int err, num_frames = 0;
	__u32 bhash;

	p = frame;
	/*
	 * Find the next leaf page by incrementing the frame pointer.
	 * If we run out of entries in the interior node, loop around and
	 * increment pointer in the parent node.  When we break out of
	 * this loop, num_frames indicates the number of interior
	 * nodes need to be read.
	 */
	while (1) {
		if (++(p->at) < p->entries + dx_get_count(p->entries))
			break;
		if (p == frames)
			return 0;
		num_frames++;
		p--;
	}

	/*
	 * If the hash is 1, then continue only if the next page has a
	 * continuation hash of any value.  This is used for readdir
	 * handling.  Otherwise, check to see if the hash matches the
	 * desired contiuation hash.  If it doesn't, return since
	 * there's no point to read in the successive index pages.
	 */
	bhash = dx_get_hash(p->at);
	if (start_hash)
		*start_hash = bhash;
	if ((hash & 1) == 0) {
		if ((bhash & ~1) != hash)
			return 0;
	}
	/*
	 * If the hash is HASH_NB_ALWAYS, we always go to the next
	 * block so no check is necessary
	 */
	while (num_frames--) {
825
		if (!(bh = ext4_bread(NULL, dir, dx_get_block(p->at),
C
Carlos Maiolino 已提交
826 827 828 829 830 831 832
				      0, &err))) {
			if (!err) {
				ext4_error(dir->i_sb,
					   "Directory hole detected on inode %lu\n",
					   dir->i_ino);
				return -EIO;
			}
833
			return err; /* Failure */
C
Carlos Maiolino 已提交
834
		}
835 836 837 838 839 840 841 842 843

		if (!buffer_verified(bh) &&
		    !ext4_dx_csum_verify(dir,
					 (struct ext4_dir_entry *)bh->b_data)) {
			ext4_warning(dir->i_sb, "Node failed checksum");
			return -EIO;
		}
		set_buffer_verified(bh);

844
		p++;
845
		brelse(p->bh);
846 847 848 849 850 851 852 853 854 855 856 857 858
		p->bh = bh;
		p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
	}
	return 1;
}


/*
 * This function fills a red-black tree with information from a
 * directory block.  It returns the number directory entries loaded
 * into the tree.  If there is an error it is returned in err.
 */
static int htree_dirblock_to_tree(struct file *dir_file,
A
Aneesh Kumar K.V 已提交
859
				  struct inode *dir, ext4_lblk_t block,
860 861 862 863
				  struct dx_hash_info *hinfo,
				  __u32 start_hash, __u32 start_minor_hash)
{
	struct buffer_head *bh;
864
	struct ext4_dir_entry_2 *de, *top;
865
	int err = 0, count = 0;
866

A
Aneesh Kumar K.V 已提交
867 868
	dxtrace(printk(KERN_INFO "In htree dirblock_to_tree: block %lu\n",
							(unsigned long)block));
C
Carlos Maiolino 已提交
869 870 871 872 873 874 875
	if (!(bh = ext4_bread(NULL, dir, block, 0, &err))) {
		if (!err) {
			err = -EIO;
			ext4_error(dir->i_sb,
				   "Directory hole detected on inode %lu\n",
				   dir->i_ino);
		}
876
		return err;
C
Carlos Maiolino 已提交
877
	}
878

879 880 881 882 883
	if (!buffer_verified(bh) &&
	    !ext4_dirent_csum_verify(dir, (struct ext4_dir_entry *)bh->b_data))
		return -EIO;
	set_buffer_verified(bh);

884 885
	de = (struct ext4_dir_entry_2 *) bh->b_data;
	top = (struct ext4_dir_entry_2 *) ((char *) de +
886
					   dir->i_sb->s_blocksize -
887
					   EXT4_DIR_REC_LEN(0));
888
	for (; de < top; de = ext4_next_entry(de, dir->i_sb->s_blocksize)) {
889
		if (ext4_check_dir_entry(dir, NULL, de, bh,
890
				bh->b_data, bh->b_size,
891 892
				(block<<EXT4_BLOCK_SIZE_BITS(dir->i_sb))
					 + ((char *)de - bh->b_data))) {
893 894 895
			/* On error, skip the f_pos to the next block. */
			dir_file->f_pos = (dir_file->f_pos |
					(dir->i_sb->s_blocksize - 1)) + 1;
896
			brelse(bh);
897 898
			return count;
		}
899
		ext4fs_dirhash(de->name, de->name_len, hinfo);
900 901 902 903 904 905
		if ((hinfo->hash < start_hash) ||
		    ((hinfo->hash == start_hash) &&
		     (hinfo->minor_hash < start_minor_hash)))
			continue;
		if (de->inode == 0)
			continue;
906
		if ((err = ext4_htree_store_dirent(dir_file,
907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925
				   hinfo->hash, hinfo->minor_hash, de)) != 0) {
			brelse(bh);
			return err;
		}
		count++;
	}
	brelse(bh);
	return count;
}


/*
 * This function fills a red-black tree with information from a
 * directory.  We start scanning the directory in hash order, starting
 * at start_hash and start_minor_hash.
 *
 * This function returns the number of entries inserted into the tree,
 * or a negative error code.
 */
926
int ext4_htree_fill_tree(struct file *dir_file, __u32 start_hash,
927 928 929
			 __u32 start_minor_hash, __u32 *next_hash)
{
	struct dx_hash_info hinfo;
930
	struct ext4_dir_entry_2 *de;
931 932
	struct dx_frame frames[2], *frame;
	struct inode *dir;
A
Aneesh Kumar K.V 已提交
933
	ext4_lblk_t block;
934
	int count = 0;
A
Aneesh Kumar K.V 已提交
935
	int ret, err;
936 937
	__u32 hashval;

938
	dxtrace(printk(KERN_DEBUG "In htree_fill_tree, start hash: %x:%x\n",
939
		       start_hash, start_minor_hash));
940
	dir = dir_file->f_path.dentry->d_inode;
941
	if (!(ext4_test_inode_flag(dir, EXT4_INODE_INDEX))) {
942
		hinfo.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
943 944 945
		if (hinfo.hash_version <= DX_HASH_TEA)
			hinfo.hash_version +=
				EXT4_SB(dir->i_sb)->s_hash_unsigned;
946
		hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
947 948 949 950 951 952 953
		count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
					       start_hash, start_minor_hash);
		*next_hash = ~0;
		return count;
	}
	hinfo.hash = start_hash;
	hinfo.minor_hash = 0;
954
	frame = dx_probe(NULL, dir, &hinfo, frames, &err);
955 956 957 958 959
	if (!frame)
		return err;

	/* Add '.' and '..' from the htree header */
	if (!start_hash && !start_minor_hash) {
960 961
		de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
		if ((err = ext4_htree_store_dirent(dir_file, 0, 0, de)) != 0)
962 963 964 965
			goto errout;
		count++;
	}
	if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
966
		de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
967
		de = ext4_next_entry(de, dir->i_sb->s_blocksize);
968
		if ((err = ext4_htree_store_dirent(dir_file, 2, 0, de)) != 0)
969 970 971 972 973 974 975 976 977 978 979 980 981 982
			goto errout;
		count++;
	}

	while (1) {
		block = dx_get_block(frame->at);
		ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo,
					     start_hash, start_minor_hash);
		if (ret < 0) {
			err = ret;
			goto errout;
		}
		count += ret;
		hashval = ~0;
983
		ret = ext4_htree_next_block(dir, HASH_NB_ALWAYS,
984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999
					    frame, frames, &hashval);
		*next_hash = hashval;
		if (ret < 0) {
			err = ret;
			goto errout;
		}
		/*
		 * Stop if:  (a) there are no more entries, or
		 * (b) we have inserted at least one entry and the
		 * next hash value is not a continuation
		 */
		if ((ret == 0) ||
		    (count && ((hashval & 1) == 0)))
			break;
	}
	dx_release(frames);
1000 1001
	dxtrace(printk(KERN_DEBUG "Fill tree: returned %d entries, "
		       "next hash: %x\n", count, *next_hash));
1002 1003 1004 1005 1006 1007
	return count;
errout:
	dx_release(frames);
	return (err);
}

T
Tao Ma 已提交
1008 1009 1010 1011 1012 1013 1014 1015 1016 1017
static inline int search_dirblock(struct buffer_head *bh,
				  struct inode *dir,
				  const struct qstr *d_name,
				  unsigned int offset,
				  struct ext4_dir_entry_2 **res_dir)
{
	return search_dir(bh, bh->b_data, dir->i_sb->s_blocksize, dir,
			  d_name, offset, res_dir);
}

1018 1019 1020 1021
/*
 * Directory block splitting, compacting
 */

1022 1023 1024 1025
/*
 * Create map of hash values, offsets, and sizes, stored at end of block.
 * Returns number of entries mapped.
 */
1026 1027 1028
static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
		       struct dx_hash_info *hinfo,
		       struct dx_map_entry *map_tail)
1029 1030 1031 1032 1033
{
	int count = 0;
	char *base = (char *) de;
	struct dx_hash_info h = *hinfo;

1034
	while ((char *) de < base + blocksize) {
1035
		if (de->name_len && de->inode) {
1036
			ext4fs_dirhash(de->name, de->name_len, &h);
1037 1038
			map_tail--;
			map_tail->hash = h.hash;
1039
			map_tail->offs = ((char *) de - base)>>2;
1040
			map_tail->size = le16_to_cpu(de->rec_len);
1041 1042 1043 1044
			count++;
			cond_resched();
		}
		/* XXX: do we need to check rec_len == 0 case? -Chris */
1045
		de = ext4_next_entry(de, blocksize);
1046 1047 1048 1049
	}
	return count;
}

1050
/* Sort map by hash value */
1051 1052
static void dx_sort_map (struct dx_map_entry *map, unsigned count)
{
A
Andrew Morton 已提交
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
	struct dx_map_entry *p, *q, *top = map + count - 1;
	int more;
	/* Combsort until bubble sort doesn't suck */
	while (count > 2) {
		count = count*10/13;
		if (count - 9 < 2) /* 9, 10 -> 11 */
			count = 11;
		for (p = top, q = p - count; q >= map; p--, q--)
			if (p->hash < q->hash)
				swap(*p, *q);
	}
	/* Garden variety bubble sort */
	do {
		more = 0;
		q = top;
		while (q-- > map) {
			if (q[1].hash >= q[0].hash)
1070
				continue;
A
Andrew Morton 已提交
1071 1072
			swap(*(q+1), *q);
			more = 1;
1073 1074 1075 1076
		}
	} while(more);
}

A
Aneesh Kumar K.V 已提交
1077
static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091
{
	struct dx_entry *entries = frame->entries;
	struct dx_entry *old = frame->at, *new = old + 1;
	int count = dx_get_count(entries);

	assert(count < dx_get_limit(entries));
	assert(old < entries + count);
	memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
	dx_set_hash(new, hash);
	dx_set_block(new, block);
	dx_set_count(entries, count + 1);
}

/*
1092
 * NOTE! unlike strncmp, ext4_match returns 1 for success, 0 for failure.
1093
 *
1094
 * `len <= EXT4_NAME_LEN' is guaranteed by caller.
1095 1096
 * `de != NULL' is guaranteed by caller.
 */
1097 1098
static inline int ext4_match (int len, const char * const name,
			      struct ext4_dir_entry_2 * de)
1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109
{
	if (len != de->name_len)
		return 0;
	if (!de->inode)
		return 0;
	return !memcmp(name, de->name, len);
}

/*
 * Returns 0 if not found, -1 on failure, and 1 on success
 */
T
Tao Ma 已提交
1110 1111 1112 1113 1114 1115 1116
int search_dir(struct buffer_head *bh,
	       char *search_buf,
	       int buf_size,
	       struct inode *dir,
	       const struct qstr *d_name,
	       unsigned int offset,
	       struct ext4_dir_entry_2 **res_dir)
1117
{
1118
	struct ext4_dir_entry_2 * de;
1119 1120
	char * dlimit;
	int de_len;
1121 1122
	const char *name = d_name->name;
	int namelen = d_name->len;
1123

T
Tao Ma 已提交
1124 1125
	de = (struct ext4_dir_entry_2 *)search_buf;
	dlimit = search_buf + buf_size;
1126 1127 1128 1129 1130
	while ((char *) de < dlimit) {
		/* this code is executed quadratically often */
		/* do minimal checking `by hand' */

		if ((char *) de + namelen <= dlimit &&
1131
		    ext4_match (namelen, name, de)) {
1132
			/* found a match - just to be sure, do a full check */
1133 1134
			if (ext4_check_dir_entry(dir, NULL, de, bh, bh->b_data,
						 bh->b_size, offset))
1135 1136 1137 1138 1139
				return -1;
			*res_dir = de;
			return 1;
		}
		/* prevent looping on a bad block */
1140 1141
		de_len = ext4_rec_len_from_disk(de->rec_len,
						dir->i_sb->s_blocksize);
1142 1143 1144
		if (de_len <= 0)
			return -1;
		offset += de_len;
1145
		de = (struct ext4_dir_entry_2 *) ((char *) de + de_len);
1146 1147 1148 1149
	}
	return 0;
}

1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164
static int is_dx_internal_node(struct inode *dir, ext4_lblk_t block,
			       struct ext4_dir_entry *de)
{
	struct super_block *sb = dir->i_sb;

	if (!is_dx(dir))
		return 0;
	if (block == 0)
		return 1;
	if (de->inode == 0 &&
	    ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize) ==
			sb->s_blocksize)
		return 1;
	return 0;
}
1165 1166

/*
1167
 *	ext4_find_entry()
1168 1169 1170 1171 1172 1173 1174 1175 1176
 *
 * finds an entry in the specified directory with the wanted name. It
 * returns the cache buffer in which the entry was found, and the entry
 * itself (as a parameter - res_dir). It does NOT read the inode of the
 * entry - you'll have to do that yourself if you want to.
 *
 * The returned buffer_head has ->b_count elevated.  The caller is expected
 * to brelse() it when appropriate.
 */
1177 1178
static struct buffer_head * ext4_find_entry (struct inode *dir,
					const struct qstr *d_name,
1179
					struct ext4_dir_entry_2 ** res_dir)
1180
{
1181 1182 1183
	struct super_block *sb;
	struct buffer_head *bh_use[NAMEI_RA_SIZE];
	struct buffer_head *bh, *ret = NULL;
A
Aneesh Kumar K.V 已提交
1184
	ext4_lblk_t start, block, b;
1185
	const u8 *name = d_name->name;
1186 1187 1188 1189 1190
	int ra_max = 0;		/* Number of bh's in the readahead
				   buffer, bh_use[] */
	int ra_ptr = 0;		/* Current index into readahead
				   buffer */
	int num = 0;
A
Aneesh Kumar K.V 已提交
1191 1192
	ext4_lblk_t  nblocks;
	int i, err;
1193 1194 1195 1196
	int namelen;

	*res_dir = NULL;
	sb = dir->i_sb;
1197
	namelen = d_name->len;
1198
	if (namelen > EXT4_NAME_LEN)
1199
		return NULL;
1200 1201 1202 1203 1204 1205 1206 1207 1208

	if (ext4_has_inline_data(dir)) {
		int has_inline_data = 1;
		ret = ext4_find_inline_entry(dir, d_name, res_dir,
					     &has_inline_data);
		if (has_inline_data)
			return ret;
	}

1209
	if ((namelen <= 2) && (name[0] == '.') &&
1210
	    (name[1] == '.' || name[1] == '\0')) {
1211 1212 1213 1214 1215 1216 1217 1218
		/*
		 * "." or ".." will only be in the first block
		 * NFS may look up ".."; "." should be handled by the VFS
		 */
		block = start = 0;
		nblocks = 1;
		goto restart;
	}
1219
	if (is_dx(dir)) {
1220
		bh = ext4_dx_find_entry(dir, d_name, res_dir, &err);
1221 1222 1223 1224 1225 1226 1227
		/*
		 * On success, or if the error was file not found,
		 * return.  Otherwise, fall back to doing a search the
		 * old fashioned way.
		 */
		if (bh || (err != ERR_BAD_DX_DIR))
			return bh;
1228 1229
		dxtrace(printk(KERN_DEBUG "ext4_find_entry: dx failed, "
			       "falling back\n"));
1230
	}
1231 1232
	nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
	start = EXT4_I(dir)->i_dir_start_lookup;
1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255
	if (start >= nblocks)
		start = 0;
	block = start;
restart:
	do {
		/*
		 * We deal with the read-ahead logic here.
		 */
		if (ra_ptr >= ra_max) {
			/* Refill the readahead buffer */
			ra_ptr = 0;
			b = block;
			for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
				/*
				 * Terminate if we reach the end of the
				 * directory and must wrap, or if our
				 * search has finished at this block.
				 */
				if (b >= nblocks || (num && block == start)) {
					bh_use[ra_max] = NULL;
					break;
				}
				num++;
1256
				bh = ext4_getblk(NULL, dir, b++, 0, &err);
1257 1258
				bh_use[ra_max] = bh;
				if (bh)
1259 1260
					ll_rw_block(READ | REQ_META | REQ_PRIO,
						    1, &bh);
1261 1262 1263 1264 1265 1266 1267
			}
		}
		if ((bh = bh_use[ra_ptr++]) == NULL)
			goto next;
		wait_on_buffer(bh);
		if (!buffer_uptodate(bh)) {
			/* read error, skip block & hope for the best */
1268 1269
			EXT4_ERROR_INODE(dir, "reading directory lblock %lu",
					 (unsigned long) block);
1270 1271 1272
			brelse(bh);
			goto next;
		}
1273
		if (!buffer_verified(bh) &&
1274 1275
		    !is_dx_internal_node(dir, block,
					 (struct ext4_dir_entry *)bh->b_data) &&
1276 1277 1278 1279 1280 1281 1282 1283
		    !ext4_dirent_csum_verify(dir,
				(struct ext4_dir_entry *)bh->b_data)) {
			EXT4_ERROR_INODE(dir, "checksumming directory "
					 "block %lu", (unsigned long)block);
			brelse(bh);
			goto next;
		}
		set_buffer_verified(bh);
1284
		i = search_dirblock(bh, dir, d_name,
1285
			    block << EXT4_BLOCK_SIZE_BITS(sb), res_dir);
1286
		if (i == 1) {
1287
			EXT4_I(dir)->i_dir_start_lookup = block;
1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304
			ret = bh;
			goto cleanup_and_exit;
		} else {
			brelse(bh);
			if (i < 0)
				goto cleanup_and_exit;
		}
	next:
		if (++block >= nblocks)
			block = 0;
	} while (block != start);

	/*
	 * If the directory has grown while we were searching, then
	 * search the last part of the directory before giving up.
	 */
	block = nblocks;
1305
	nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
1306 1307 1308 1309 1310 1311 1312 1313
	if (block < nblocks) {
		start = 0;
		goto restart;
	}

cleanup_and_exit:
	/* Clean up the read-ahead blocks */
	for (; ra_ptr < ra_max; ra_ptr++)
1314
		brelse(bh_use[ra_ptr]);
1315 1316 1317
	return ret;
}

1318
static struct buffer_head * ext4_dx_find_entry(struct inode *dir, const struct qstr *d_name,
1319
		       struct ext4_dir_entry_2 **res_dir, int *err)
1320
{
1321
	struct super_block * sb = dir->i_sb;
1322 1323 1324
	struct dx_hash_info	hinfo;
	struct dx_frame frames[2], *frame;
	struct buffer_head *bh;
A
Aneesh Kumar K.V 已提交
1325
	ext4_lblk_t block;
1326 1327
	int retval;

1328 1329
	if (!(frame = dx_probe(d_name, dir, &hinfo, frames, err)))
		return NULL;
1330 1331
	do {
		block = dx_get_block(frame->at);
C
Carlos Maiolino 已提交
1332 1333 1334 1335 1336 1337 1338
		if (!(bh = ext4_bread(NULL, dir, block, 0, err))) {
			if (!(*err)) {
				*err = -EIO;
				ext4_error(dir->i_sb,
					   "Directory hole detected on inode %lu\n",
					   dir->i_ino);
			}
1339
			goto errout;
C
Carlos Maiolino 已提交
1340
		}
1341

1342 1343 1344 1345 1346 1347 1348 1349 1350 1351
		if (!buffer_verified(bh) &&
		    !ext4_dirent_csum_verify(dir,
				(struct ext4_dir_entry *)bh->b_data)) {
			EXT4_ERROR_INODE(dir, "checksumming directory "
					 "block %lu", (unsigned long)block);
			brelse(bh);
			*err = -EIO;
			goto errout;
		}
		set_buffer_verified(bh);
1352 1353 1354 1355 1356 1357
		retval = search_dirblock(bh, dir, d_name,
					 block << EXT4_BLOCK_SIZE_BITS(sb),
					 res_dir);
		if (retval == 1) { 	/* Success! */
			dx_release(frames);
			return bh;
1358
		}
1359
		brelse(bh);
1360 1361 1362 1363 1364
		if (retval == -1) {
			*err = ERR_BAD_DX_DIR;
			goto errout;
		}

1365
		/* Check to see if we should continue to search */
1366
		retval = ext4_htree_next_block(dir, hinfo.hash, frame,
1367 1368
					       frames, NULL);
		if (retval < 0) {
1369
			ext4_warning(sb,
1370 1371 1372 1373 1374 1375 1376 1377 1378
			     "error reading index page in directory #%lu",
			     dir->i_ino);
			*err = retval;
			goto errout;
		}
	} while (retval == 1);

	*err = -ENOENT;
errout:
1379
	dxtrace(printk(KERN_DEBUG "%s not found\n", d_name->name));
1380 1381 1382 1383
	dx_release (frames);
	return NULL;
}

A
Al Viro 已提交
1384
static struct dentry *ext4_lookup(struct inode *dir, struct dentry *dentry, unsigned int flags)
1385
{
1386 1387 1388
	struct inode *inode;
	struct ext4_dir_entry_2 *de;
	struct buffer_head *bh;
1389

1390
	if (dentry->d_name.len > EXT4_NAME_LEN)
1391 1392
		return ERR_PTR(-ENAMETOOLONG);

1393
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
1394 1395
	inode = NULL;
	if (bh) {
1396
		__u32 ino = le32_to_cpu(de->inode);
1397
		brelse(bh);
1398
		if (!ext4_valid_inum(dir->i_sb, ino)) {
1399
			EXT4_ERROR_INODE(dir, "bad inode number: %u", ino);
1400
			return ERR_PTR(-EIO);
1401
		}
1402 1403 1404 1405 1406 1407
		if (unlikely(ino == dir->i_ino)) {
			EXT4_ERROR_INODE(dir, "'%.*s' linked to parent dir",
					 dentry->d_name.len,
					 dentry->d_name.name);
			return ERR_PTR(-EIO);
		}
1408
		inode = ext4_iget(dir->i_sb, ino);
1409 1410 1411 1412 1413
		if (inode == ERR_PTR(-ESTALE)) {
			EXT4_ERROR_INODE(dir,
					 "deleted inode referenced: %u",
					 ino);
			return ERR_PTR(-EIO);
1414
		}
1415 1416 1417 1418 1419
	}
	return d_splice_alias(inode, dentry);
}


1420
struct dentry *ext4_get_parent(struct dentry *child)
1421
{
1422
	__u32 ino;
1423
	static const struct qstr dotdot = QSTR_INIT("..", 2);
1424
	struct ext4_dir_entry_2 * de;
1425 1426
	struct buffer_head *bh;

1427
	bh = ext4_find_entry(child->d_inode, &dotdot, &de);
1428 1429 1430 1431 1432
	if (!bh)
		return ERR_PTR(-ENOENT);
	ino = le32_to_cpu(de->inode);
	brelse(bh);

1433
	if (!ext4_valid_inum(child->d_inode->i_sb, ino)) {
1434 1435
		EXT4_ERROR_INODE(child->d_inode,
				 "bad parent inode number: %u", ino);
1436
		return ERR_PTR(-EIO);
1437 1438
	}

1439
	return d_obtain_alias(ext4_iget(child->d_inode->i_sb, ino));
1440 1441 1442
}

#define S_SHIFT 12
1443 1444 1445 1446 1447 1448 1449 1450
static unsigned char ext4_type_by_mode[S_IFMT >> S_SHIFT] = {
	[S_IFREG >> S_SHIFT]	= EXT4_FT_REG_FILE,
	[S_IFDIR >> S_SHIFT]	= EXT4_FT_DIR,
	[S_IFCHR >> S_SHIFT]	= EXT4_FT_CHRDEV,
	[S_IFBLK >> S_SHIFT]	= EXT4_FT_BLKDEV,
	[S_IFIFO >> S_SHIFT]	= EXT4_FT_FIFO,
	[S_IFSOCK >> S_SHIFT]	= EXT4_FT_SOCK,
	[S_IFLNK >> S_SHIFT]	= EXT4_FT_SYMLINK,
1451 1452
};

1453 1454
static inline void ext4_set_de_type(struct super_block *sb,
				struct ext4_dir_entry_2 *de,
1455
				umode_t mode) {
1456 1457
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FILETYPE))
		de->file_type = ext4_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
1458 1459
}

1460 1461 1462 1463
/*
 * Move count entries from end of map between two memory locations.
 * Returns pointer to last entry moved.
 */
1464
static struct ext4_dir_entry_2 *
1465 1466
dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count,
		unsigned blocksize)
1467 1468 1469 1470
{
	unsigned rec_len = 0;

	while (count--) {
1471
		struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)
1472
						(from + (map->offs<<2));
1473
		rec_len = EXT4_DIR_REC_LEN(de->name_len);
1474
		memcpy (to, de, rec_len);
1475
		((struct ext4_dir_entry_2 *) to)->rec_len =
1476
				ext4_rec_len_to_disk(rec_len, blocksize);
1477 1478 1479 1480
		de->inode = 0;
		map++;
		to += rec_len;
	}
1481
	return (struct ext4_dir_entry_2 *) (to - rec_len);
1482 1483
}

1484 1485 1486 1487
/*
 * Compact each dir entry in the range to the minimal rec_len.
 * Returns pointer to last entry in range.
 */
1488
static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize)
1489
{
1490
	struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base;
1491 1492 1493
	unsigned rec_len = 0;

	prev = to = de;
1494
	while ((char*)de < base + blocksize) {
1495
		next = ext4_next_entry(de, blocksize);
1496
		if (de->inode && de->name_len) {
1497
			rec_len = EXT4_DIR_REC_LEN(de->name_len);
1498 1499
			if (de > to)
				memmove(to, de, rec_len);
1500
			to->rec_len = ext4_rec_len_to_disk(rec_len, blocksize);
1501
			prev = to;
1502
			to = (struct ext4_dir_entry_2 *) (((char *) to) + rec_len);
1503 1504 1505 1506 1507 1508
		}
		de = next;
	}
	return prev;
}

1509 1510 1511 1512 1513
/*
 * Split a full leaf block to make room for a new dir entry.
 * Allocate a new block, and move entries so that they are approx. equally full.
 * Returns pointer to de in block into which the new entry will be inserted.
 */
1514
static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
1515 1516 1517 1518 1519 1520
			struct buffer_head **bh,struct dx_frame *frame,
			struct dx_hash_info *hinfo, int *error)
{
	unsigned blocksize = dir->i_sb->s_blocksize;
	unsigned count, continued;
	struct buffer_head *bh2;
A
Aneesh Kumar K.V 已提交
1521
	ext4_lblk_t newblock;
1522 1523 1524
	u32 hash2;
	struct dx_map_entry *map;
	char *data1 = (*bh)->b_data, *data2;
1525
	unsigned split, move, size;
1526
	struct ext4_dir_entry_2 *de = NULL, *de2;
1527 1528
	struct ext4_dir_entry_tail *t;
	int	csum_size = 0;
1529
	int	err = 0, i;
1530

1531 1532 1533 1534
	if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		csum_size = sizeof(struct ext4_dir_entry_tail);

1535
	bh2 = ext4_append (handle, dir, &newblock, &err);
1536 1537 1538 1539 1540 1541 1542
	if (!(bh2)) {
		brelse(*bh);
		*bh = NULL;
		goto errout;
	}

	BUFFER_TRACE(*bh, "get_write_access");
1543
	err = ext4_journal_get_write_access(handle, *bh);
1544 1545 1546
	if (err)
		goto journal_error;

1547
	BUFFER_TRACE(frame->bh, "get_write_access");
1548
	err = ext4_journal_get_write_access(handle, frame->bh);
1549 1550 1551 1552 1553 1554 1555
	if (err)
		goto journal_error;

	data2 = bh2->b_data;

	/* create map in the end of data2 block */
	map = (struct dx_map_entry *) (data2 + blocksize);
1556
	count = dx_make_map((struct ext4_dir_entry_2 *) data1,
1557 1558
			     blocksize, hinfo, map);
	map -= count;
1559
	dx_sort_map(map, count);
1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571
	/* Split the existing block in the middle, size-wise */
	size = 0;
	move = 0;
	for (i = count-1; i >= 0; i--) {
		/* is more than half of this entry in 2nd half of the block? */
		if (size + map[i].size/2 > blocksize/2)
			break;
		size += map[i].size;
		move++;
	}
	/* map index at which we will split */
	split = count - move;
1572 1573
	hash2 = map[split].hash;
	continued = hash2 == map[split - 1].hash;
A
Aneesh Kumar K.V 已提交
1574 1575 1576
	dxtrace(printk(KERN_INFO "Split block %lu at %x, %i/%i\n",
			(unsigned long)dx_get_block(frame->at),
					hash2, split, count-split));
1577 1578

	/* Fancy dance to stay within two buffers */
1579
	de2 = dx_move_dirents(data1, data2, map + split, count - split, blocksize);
1580
	de = dx_pack_dirents(data1, blocksize);
1581 1582
	de->rec_len = ext4_rec_len_to_disk(data1 + (blocksize - csum_size) -
					   (char *) de,
1583
					   blocksize);
1584 1585
	de2->rec_len = ext4_rec_len_to_disk(data2 + (blocksize - csum_size) -
					    (char *) de2,
1586
					    blocksize);
1587 1588 1589 1590 1591 1592 1593 1594
	if (csum_size) {
		t = EXT4_DIRENT_TAIL(data2, blocksize);
		initialize_dirent_tail(t, blocksize);

		t = EXT4_DIRENT_TAIL(data1, blocksize);
		initialize_dirent_tail(t, blocksize);
	}

1595 1596
	dxtrace(dx_show_leaf (hinfo, (struct ext4_dir_entry_2 *) data1, blocksize, 1));
	dxtrace(dx_show_leaf (hinfo, (struct ext4_dir_entry_2 *) data2, blocksize, 1));
1597 1598 1599 1600 1601 1602 1603

	/* Which block gets the new entry? */
	if (hinfo->hash >= hash2)
	{
		swap(*bh, bh2);
		de = de2;
	}
1604
	dx_insert_block(frame, hash2 + continued, newblock);
1605
	err = ext4_handle_dirty_dirent_node(handle, dir, bh2);
1606 1607
	if (err)
		goto journal_error;
1608
	err = ext4_handle_dirty_dx_node(handle, dir, frame->bh);
1609 1610
	if (err)
		goto journal_error;
1611 1612
	brelse(bh2);
	dxtrace(dx_show_index("frame", frame->entries));
1613
	return de;
1614 1615 1616 1617 1618 1619 1620 1621 1622

journal_error:
	brelse(*bh);
	brelse(bh2);
	*bh = NULL;
	ext4_std_error(dir->i_sb, err);
errout:
	*error = err;
	return NULL;
1623 1624
}

1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681
int ext4_find_dest_de(struct inode *dir, struct inode *inode,
		      struct buffer_head *bh,
		      void *buf, int buf_size,
		      const char *name, int namelen,
		      struct ext4_dir_entry_2 **dest_de)
{
	struct ext4_dir_entry_2 *de;
	unsigned short reclen = EXT4_DIR_REC_LEN(namelen);
	int nlen, rlen;
	unsigned int offset = 0;
	char *top;

	de = (struct ext4_dir_entry_2 *)buf;
	top = buf + buf_size - reclen;
	while ((char *) de <= top) {
		if (ext4_check_dir_entry(dir, NULL, de, bh,
					 buf, buf_size, offset))
			return -EIO;
		if (ext4_match(namelen, name, de))
			return -EEXIST;
		nlen = EXT4_DIR_REC_LEN(de->name_len);
		rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
		if ((de->inode ? rlen - nlen : rlen) >= reclen)
			break;
		de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
		offset += rlen;
	}
	if ((char *) de > top)
		return -ENOSPC;

	*dest_de = de;
	return 0;
}

void ext4_insert_dentry(struct inode *inode,
			struct ext4_dir_entry_2 *de,
			int buf_size,
			const char *name, int namelen)
{

	int nlen, rlen;

	nlen = EXT4_DIR_REC_LEN(de->name_len);
	rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
	if (de->inode) {
		struct ext4_dir_entry_2 *de1 =
				(struct ext4_dir_entry_2 *)((char *)de + nlen);
		de1->rec_len = ext4_rec_len_to_disk(rlen - nlen, buf_size);
		de->rec_len = ext4_rec_len_to_disk(nlen, buf_size);
		de = de1;
	}
	de->file_type = EXT4_FT_UNKNOWN;
	de->inode = cpu_to_le32(inode->i_ino);
	ext4_set_de_type(inode->i_sb, de, inode->i_mode);
	de->name_len = namelen;
	memcpy(de->name, name, namelen);
}
1682 1683 1684 1685 1686 1687 1688 1689 1690
/*
 * Add a new entry into a directory (leaf) block.  If de is non-NULL,
 * it points to a directory entry which is guaranteed to be large
 * enough for new directory entry.  If de is NULL, then
 * add_dirent_to_buf will attempt search the directory block for
 * space.  It will return -ENOSPC if no space is available, and -EIO
 * and -EEXIST if directory entry already exists.
 */
static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry,
1691
			     struct inode *inode, struct ext4_dir_entry_2 *de,
1692
			     struct buffer_head *bh)
1693 1694 1695 1696
{
	struct inode	*dir = dentry->d_parent->d_inode;
	const char	*name = dentry->d_name.name;
	int		namelen = dentry->d_name.len;
1697
	unsigned int	blocksize = dir->i_sb->s_blocksize;
1698
	unsigned short	reclen;
1699
	int		csum_size = 0;
1700
	int		err;
1701 1702 1703 1704

	if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		csum_size = sizeof(struct ext4_dir_entry_tail);
1705

1706
	reclen = EXT4_DIR_REC_LEN(namelen);
1707
	if (!de) {
1708 1709 1710 1711 1712
		err = ext4_find_dest_de(dir, inode,
					bh, bh->b_data, blocksize - csum_size,
					name, namelen, &de);
		if (err)
			return err;
1713 1714
	}
	BUFFER_TRACE(bh, "get_write_access");
1715
	err = ext4_journal_get_write_access(handle, bh);
1716
	if (err) {
1717
		ext4_std_error(dir->i_sb, err);
1718 1719 1720 1721
		return err;
	}

	/* By now the buffer is marked for journaling */
1722 1723
	ext4_insert_dentry(inode, de, blocksize, name, namelen);

1724 1725 1726 1727 1728 1729
	/*
	 * XXX shouldn't update any times until successful
	 * completion of syscall, but too many callers depend
	 * on this.
	 *
	 * XXX similarly, too many callers depend on
1730
	 * ext4_new_inode() setting the times, but error
1731 1732 1733 1734
	 * recovery deletes the inode, so the worst that can
	 * happen is that the times are slightly out of date
	 * and/or different from the directory change time.
	 */
K
Kalpak Shah 已提交
1735
	dir->i_mtime = dir->i_ctime = ext4_current_time(dir);
1736
	ext4_update_dx_flag(dir);
1737
	dir->i_version++;
1738
	ext4_mark_inode_dirty(handle, dir);
1739
	BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
1740
	err = ext4_handle_dirty_dirent_node(handle, dir, bh);
1741
	if (err)
1742
		ext4_std_error(dir->i_sb, err);
1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759
	return 0;
}

/*
 * This converts a one block unindexed directory to a 3 block indexed
 * directory, and adds the dentry to the indexed directory.
 */
static int make_indexed_dir(handle_t *handle, struct dentry *dentry,
			    struct inode *inode, struct buffer_head *bh)
{
	struct inode	*dir = dentry->d_parent->d_inode;
	const char	*name = dentry->d_name.name;
	int		namelen = dentry->d_name.len;
	struct buffer_head *bh2;
	struct dx_root	*root;
	struct dx_frame	frames[2], *frame;
	struct dx_entry *entries;
1760
	struct ext4_dir_entry_2	*de, *de2;
1761
	struct ext4_dir_entry_tail *t;
1762 1763 1764 1765 1766
	char		*data1, *top;
	unsigned	len;
	int		retval;
	unsigned	blocksize;
	struct dx_hash_info hinfo;
A
Aneesh Kumar K.V 已提交
1767
	ext4_lblk_t  block;
1768
	struct fake_dirent *fde;
1769 1770 1771 1772 1773
	int		csum_size = 0;

	if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		csum_size = sizeof(struct ext4_dir_entry_tail);
1774 1775

	blocksize =  dir->i_sb->s_blocksize;
1776
	dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino));
1777
	retval = ext4_journal_get_write_access(handle, bh);
1778
	if (retval) {
1779
		ext4_std_error(dir->i_sb, retval);
1780 1781 1782 1783 1784
		brelse(bh);
		return retval;
	}
	root = (struct dx_root *) bh->b_data;

1785 1786 1787
	/* The 0th block becomes the root, move the dirents out */
	fde = &root->dotdot;
	de = (struct ext4_dir_entry_2 *)((char *)fde +
1788
		ext4_rec_len_from_disk(fde->rec_len, blocksize));
1789
	if ((char *) de >= (((char *) root) + blocksize)) {
1790
		EXT4_ERROR_INODE(dir, "invalid rec_len for '..'");
1791 1792 1793
		brelse(bh);
		return -EIO;
	}
1794
	len = ((char *) root) + (blocksize - csum_size) - (char *) de;
1795 1796

	/* Allocate new block for the 0th block's dirents */
1797
	bh2 = ext4_append(handle, dir, &block, &retval);
1798 1799 1800 1801
	if (!(bh2)) {
		brelse(bh);
		return retval;
	}
1802
	ext4_set_inode_flag(dir, EXT4_INODE_INDEX);
1803 1804 1805
	data1 = bh2->b_data;

	memcpy (data1, de, len);
1806
	de = (struct ext4_dir_entry_2 *) data1;
1807
	top = data1 + len;
1808
	while ((char *)(de2 = ext4_next_entry(de, blocksize)) < top)
1809
		de = de2;
1810 1811
	de->rec_len = ext4_rec_len_to_disk(data1 + (blocksize - csum_size) -
					   (char *) de,
1812
					   blocksize);
1813 1814 1815 1816 1817 1818

	if (csum_size) {
		t = EXT4_DIRENT_TAIL(data1, blocksize);
		initialize_dirent_tail(t, blocksize);
	}

1819
	/* Initialize the root; the dot dirents already exist */
1820
	de = (struct ext4_dir_entry_2 *) (&root->dotdot);
1821 1822
	de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(2),
					   blocksize);
1823 1824
	memset (&root->info, 0, sizeof(root->info));
	root->info.info_length = sizeof(root->info);
1825
	root->info.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
1826
	entries = root->entries;
1827 1828 1829
	dx_set_block(entries, 1);
	dx_set_count(entries, 1);
	dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
1830 1831 1832

	/* Initialize as for dx_probe */
	hinfo.hash_version = root->info.hash_version;
1833 1834
	if (hinfo.hash_version <= DX_HASH_TEA)
		hinfo.hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
1835 1836
	hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
	ext4fs_dirhash(name, namelen, &hinfo);
1837 1838 1839 1840 1841
	frame = frames;
	frame->entries = entries;
	frame->at = entries;
	frame->bh = bh;
	bh = bh2;
1842

1843
	ext4_handle_dirty_dx_node(handle, dir, frame->bh);
1844
	ext4_handle_dirty_dirent_node(handle, dir, bh);
1845

1846
	de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
1847 1848 1849 1850 1851 1852 1853 1854
	if (!de) {
		/*
		 * Even if the block split failed, we have to properly write
		 * out all the changes we did so far. Otherwise we can end up
		 * with corrupted filesystem.
		 */
		ext4_mark_inode_dirty(handle, dir);
		dx_release(frames);
1855
		return retval;
1856 1857
	}
	dx_release(frames);
1858

1859 1860 1861
	retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
	brelse(bh);
	return retval;
1862 1863 1864
}

/*
1865
 *	ext4_add_entry()
1866 1867
 *
 * adds a file entry to the specified directory, using the same
1868
 * semantics as ext4_find_entry(). It returns NULL if it failed.
1869 1870 1871 1872 1873
 *
 * NOTE!! The inode part of 'de' is left at 0 - which means you
 * may not sleep between calling this and putting something into
 * the entry, as someone else might have used it while you slept.
 */
1874 1875
static int ext4_add_entry(handle_t *handle, struct dentry *dentry,
			  struct inode *inode)
1876 1877
{
	struct inode *dir = dentry->d_parent->d_inode;
1878
	struct buffer_head *bh;
1879
	struct ext4_dir_entry_2 *de;
1880
	struct ext4_dir_entry_tail *t;
1881
	struct super_block *sb;
1882 1883 1884
	int	retval;
	int	dx_fallback=0;
	unsigned blocksize;
A
Aneesh Kumar K.V 已提交
1885
	ext4_lblk_t block, blocks;
1886 1887 1888 1889 1890
	int	csum_size = 0;

	if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		csum_size = sizeof(struct ext4_dir_entry_tail);
1891 1892 1893 1894 1895

	sb = dir->i_sb;
	blocksize = sb->s_blocksize;
	if (!dentry->d_name.len)
		return -EINVAL;
1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906

	if (ext4_has_inline_data(dir)) {
		retval = ext4_try_add_inline_entry(handle, dentry, inode);
		if (retval < 0)
			return retval;
		if (retval == 1) {
			retval = 0;
			return retval;
		}
	}

1907
	if (is_dx(dir)) {
1908
		retval = ext4_dx_add_entry(handle, dentry, inode);
1909 1910
		if (!retval || (retval != ERR_BAD_DX_DIR))
			return retval;
1911
		ext4_clear_inode_flag(dir, EXT4_INODE_INDEX);
1912
		dx_fallback++;
1913
		ext4_mark_inode_dirty(handle, dir);
1914 1915
	}
	blocks = dir->i_size >> sb->s_blocksize_bits;
1916
	for (block = 0; block < blocks; block++) {
C
Carlos Maiolino 已提交
1917 1918 1919 1920 1921 1922 1923
		if (!(bh = ext4_bread(handle, dir, block, 0, &retval))) {
			if (!retval) {
				retval = -EIO;
				ext4_error(inode->i_sb,
					   "Directory hole detected on inode %lu\n",
					   inode->i_ino);
			}
1924
			return retval;
C
Carlos Maiolino 已提交
1925
		}
1926 1927 1928 1929 1930
		if (!buffer_verified(bh) &&
		    !ext4_dirent_csum_verify(dir,
				(struct ext4_dir_entry *)bh->b_data))
			return -EIO;
		set_buffer_verified(bh);
1931
		retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1932 1933
		if (retval != -ENOSPC) {
			brelse(bh);
1934
			return retval;
1935
		}
1936 1937

		if (blocks == 1 && !dx_fallback &&
1938 1939
		    EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX))
			return make_indexed_dir(handle, dentry, inode, bh);
1940 1941
		brelse(bh);
	}
1942
	bh = ext4_append(handle, dir, &block, &retval);
1943 1944
	if (!bh)
		return retval;
1945
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1946
	de->inode = 0;
1947 1948 1949 1950 1951 1952 1953
	de->rec_len = ext4_rec_len_to_disk(blocksize - csum_size, blocksize);

	if (csum_size) {
		t = EXT4_DIRENT_TAIL(bh->b_data, blocksize);
		initialize_dirent_tail(t, blocksize);
	}

1954 1955
	retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
	brelse(bh);
1956 1957
	if (retval == 0)
		ext4_set_inode_state(inode, EXT4_STATE_NEWENTRY);
1958
	return retval;
1959 1960 1961 1962 1963
}

/*
 * Returns 0 for success, or a negative error value
 */
1964
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
1965 1966 1967 1968 1969
			     struct inode *inode)
{
	struct dx_frame frames[2], *frame;
	struct dx_entry *entries, *at;
	struct dx_hash_info hinfo;
1970
	struct buffer_head *bh;
1971
	struct inode *dir = dentry->d_parent->d_inode;
1972
	struct super_block *sb = dir->i_sb;
1973
	struct ext4_dir_entry_2 *de;
1974 1975
	int err;

1976
	frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
1977 1978 1979 1980 1981
	if (!frame)
		return err;
	entries = frame->entries;
	at = frame->at;

C
Carlos Maiolino 已提交
1982 1983 1984 1985 1986 1987 1988
	if (!(bh = ext4_bread(handle, dir, dx_get_block(frame->at), 0, &err))) {
		if (!err) {
			err = -EIO;
			ext4_error(dir->i_sb,
				   "Directory hole detected on inode %lu\n",
				   dir->i_ino);
		}
1989
		goto cleanup;
C
Carlos Maiolino 已提交
1990
	}
1991

1992 1993 1994 1995 1996
	if (!buffer_verified(bh) &&
	    !ext4_dirent_csum_verify(dir, (struct ext4_dir_entry *)bh->b_data))
		goto journal_error;
	set_buffer_verified(bh);

1997
	BUFFER_TRACE(bh, "get_write_access");
1998
	err = ext4_journal_get_write_access(handle, bh);
1999 2000 2001 2002
	if (err)
		goto journal_error;

	err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
2003
	if (err != -ENOSPC)
2004 2005 2006
		goto cleanup;

	/* Block full, should compress but for now just split */
2007
	dxtrace(printk(KERN_DEBUG "using %u of %u node entries\n",
2008 2009 2010
		       dx_get_count(entries), dx_get_limit(entries)));
	/* Need to split index? */
	if (dx_get_count(entries) == dx_get_limit(entries)) {
A
Aneesh Kumar K.V 已提交
2011
		ext4_lblk_t newblock;
2012 2013 2014 2015 2016 2017 2018 2019
		unsigned icount = dx_get_count(entries);
		int levels = frame - frames;
		struct dx_entry *entries2;
		struct dx_node *node2;
		struct buffer_head *bh2;

		if (levels && (dx_get_count(frames->entries) ==
			       dx_get_limit(frames->entries))) {
2020
			ext4_warning(sb, "Directory index full!");
2021 2022 2023
			err = -ENOSPC;
			goto cleanup;
		}
2024
		bh2 = ext4_append (handle, dir, &newblock, &err);
2025 2026 2027 2028
		if (!(bh2))
			goto cleanup;
		node2 = (struct dx_node *)(bh2->b_data);
		entries2 = node2->entries;
2029
		memset(&node2->fake, 0, sizeof(struct fake_dirent));
2030 2031
		node2->fake.rec_len = ext4_rec_len_to_disk(sb->s_blocksize,
							   sb->s_blocksize);
2032
		BUFFER_TRACE(frame->bh, "get_write_access");
2033
		err = ext4_journal_get_write_access(handle, frame->bh);
2034 2035 2036 2037 2038
		if (err)
			goto journal_error;
		if (levels) {
			unsigned icount1 = icount/2, icount2 = icount - icount1;
			unsigned hash2 = dx_get_hash(entries + icount1);
2039 2040
			dxtrace(printk(KERN_DEBUG "Split index %i/%i\n",
				       icount1, icount2));
2041 2042

			BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
2043
			err = ext4_journal_get_write_access(handle,
2044 2045 2046 2047
							     frames[0].bh);
			if (err)
				goto journal_error;

2048 2049 2050 2051 2052
			memcpy((char *) entries2, (char *) (entries + icount1),
			       icount2 * sizeof(struct dx_entry));
			dx_set_count(entries, icount1);
			dx_set_count(entries2, icount2);
			dx_set_limit(entries2, dx_node_limit(dir));
2053 2054 2055 2056 2057 2058 2059

			/* Which index block gets the new entry? */
			if (at - entries >= icount1) {
				frame->at = at = at - entries - icount1 + entries2;
				frame->entries = entries = entries2;
				swap(frame->bh, bh2);
			}
2060 2061 2062
			dx_insert_block(frames + 0, hash2, newblock);
			dxtrace(dx_show_index("node", frames[1].entries));
			dxtrace(dx_show_index("node",
2063
			       ((struct dx_node *) bh2->b_data)->entries));
2064
			err = ext4_handle_dirty_dx_node(handle, dir, bh2);
2065 2066 2067 2068
			if (err)
				goto journal_error;
			brelse (bh2);
		} else {
2069 2070
			dxtrace(printk(KERN_DEBUG
				       "Creating second level index...\n"));
2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084
			memcpy((char *) entries2, (char *) entries,
			       icount * sizeof(struct dx_entry));
			dx_set_limit(entries2, dx_node_limit(dir));

			/* Set up root */
			dx_set_count(entries, 1);
			dx_set_block(entries + 0, newblock);
			((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;

			/* Add new access path frame */
			frame = frames + 1;
			frame->at = at = at - entries + entries2;
			frame->entries = entries = entries2;
			frame->bh = bh2;
2085
			err = ext4_journal_get_write_access(handle,
2086 2087 2088 2089
							     frame->bh);
			if (err)
				goto journal_error;
		}
2090
		err = ext4_handle_dirty_dx_node(handle, dir, frames[0].bh);
2091 2092 2093 2094
		if (err) {
			ext4_std_error(inode->i_sb, err);
			goto cleanup;
		}
2095 2096 2097 2098 2099 2100 2101 2102
	}
	de = do_split(handle, dir, &bh, frame, &hinfo, &err);
	if (!de)
		goto cleanup;
	err = add_dirent_to_buf(handle, dentry, inode, de, bh);
	goto cleanup;

journal_error:
2103
	ext4_std_error(dir->i_sb, err);
2104 2105 2106 2107 2108 2109 2110 2111
cleanup:
	if (bh)
		brelse(bh);
	dx_release(frames);
	return err;
}

/*
T
Tao Ma 已提交
2112 2113
 * ext4_generic_delete_entry deletes a directory entry by merging it
 * with the previous entry
2114
 */
T
Tao Ma 已提交
2115 2116 2117 2118 2119 2120 2121
int ext4_generic_delete_entry(handle_t *handle,
			      struct inode *dir,
			      struct ext4_dir_entry_2 *de_del,
			      struct buffer_head *bh,
			      void *entry_buf,
			      int buf_size,
			      int csum_size)
2122
{
2123
	struct ext4_dir_entry_2 *de, *pde;
2124
	unsigned int blocksize = dir->i_sb->s_blocksize;
T
Tao Ma 已提交
2125
	int i;
2126

2127 2128
	i = 0;
	pde = NULL;
T
Tao Ma 已提交
2129 2130
	de = (struct ext4_dir_entry_2 *)entry_buf;
	while (i < buf_size - csum_size) {
2131 2132
		if (ext4_check_dir_entry(dir, NULL, de, bh,
					 bh->b_data, bh->b_size, i))
2133 2134 2135
			return -EIO;
		if (de == de_del)  {
			if (pde)
2136
				pde->rec_len = ext4_rec_len_to_disk(
2137 2138 2139 2140 2141
					ext4_rec_len_from_disk(pde->rec_len,
							       blocksize) +
					ext4_rec_len_from_disk(de->rec_len,
							       blocksize),
					blocksize);
2142 2143 2144 2145 2146
			else
				de->inode = 0;
			dir->i_version++;
			return 0;
		}
2147
		i += ext4_rec_len_from_disk(de->rec_len, blocksize);
2148
		pde = de;
2149
		de = ext4_next_entry(de, blocksize);
2150 2151 2152 2153
	}
	return -ENOENT;
}

T
Tao Ma 已提交
2154 2155 2156 2157 2158 2159 2160
static int ext4_delete_entry(handle_t *handle,
			     struct inode *dir,
			     struct ext4_dir_entry_2 *de_del,
			     struct buffer_head *bh)
{
	int err, csum_size = 0;

2161 2162 2163 2164 2165 2166 2167 2168
	if (ext4_has_inline_data(dir)) {
		int has_inline_data = 1;
		err = ext4_delete_inline_entry(handle, dir, de_del, bh,
					       &has_inline_data);
		if (has_inline_data)
			return err;
	}

T
Tao Ma 已提交
2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195
	if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		csum_size = sizeof(struct ext4_dir_entry_tail);

	BUFFER_TRACE(bh, "get_write_access");
	err = ext4_journal_get_write_access(handle, bh);
	if (unlikely(err))
		goto out;

	err = ext4_generic_delete_entry(handle, dir, de_del,
					bh, bh->b_data,
					dir->i_sb->s_blocksize, csum_size);
	if (err)
		goto out;

	BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_dirent_node(handle, dir, bh);
	if (unlikely(err))
		goto out;

	return 0;
out:
	if (err != -ENOENT)
		ext4_std_error(dir->i_sb, err);
	return err;
}

2196 2197 2198 2199 2200 2201 2202 2203 2204 2205
/*
 * DIR_NLINK feature is set if 1) nlinks > EXT4_LINK_MAX or 2) nlinks == 2,
 * since this indicates that nlinks count was previously 1.
 */
static void ext4_inc_count(handle_t *handle, struct inode *inode)
{
	inc_nlink(inode);
	if (is_dx(inode) && inode->i_nlink > 1) {
		/* limit is 16-bit i_links_count */
		if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
M
Miklos Szeredi 已提交
2206
			set_nlink(inode, 1);
2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218
			EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
					      EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
		}
	}
}

/*
 * If a directory had nlink == 1, then we should let it be 1. This indicates
 * directory has >EXT4_LINK_MAX subdirs.
 */
static void ext4_dec_count(handle_t *handle, struct inode *inode)
{
2219 2220
	if (!S_ISDIR(inode->i_mode) || inode->i_nlink > 2)
		drop_nlink(inode);
2221 2222 2223
}


2224
static int ext4_add_nondir(handle_t *handle,
2225 2226
		struct dentry *dentry, struct inode *inode)
{
2227
	int err = ext4_add_entry(handle, dentry, inode);
2228
	if (!err) {
2229
		ext4_mark_inode_dirty(handle, inode);
A
Al Viro 已提交
2230
		unlock_new_inode(inode);
2231
		d_instantiate(dentry, inode);
2232 2233
		return 0;
	}
2234
	drop_nlink(inode);
A
Al Viro 已提交
2235
	unlock_new_inode(inode);
2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247
	iput(inode);
	return err;
}

/*
 * By the time this is called, we already have created
 * the directory cache entry for the new file, but it
 * is so far negative - it has no inode.
 *
 * If the create succeeds, we fill in the inode information
 * with d_instantiate().
 */
A
Al Viro 已提交
2248
static int ext4_create(struct inode *dir, struct dentry *dentry, umode_t mode,
A
Al Viro 已提交
2249
		       bool excl)
2250 2251
{
	handle_t *handle;
2252
	struct inode *inode;
2253 2254
	int err, retries = 0;

2255
	dquot_initialize(dir);
2256

2257
retry:
2258 2259
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
2260
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
2261 2262 2263 2264
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2265
		ext4_handle_sync(handle);
2266

2267
	inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0, NULL);
2268 2269
	err = PTR_ERR(inode);
	if (!IS_ERR(inode)) {
2270 2271 2272 2273
		inode->i_op = &ext4_file_inode_operations;
		inode->i_fop = &ext4_file_operations;
		ext4_set_aops(inode);
		err = ext4_add_nondir(handle, dentry, inode);
2274
	}
2275 2276
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2277 2278 2279 2280
		goto retry;
	return err;
}

2281
static int ext4_mknod(struct inode *dir, struct dentry *dentry,
A
Al Viro 已提交
2282
		      umode_t mode, dev_t rdev)
2283 2284 2285 2286 2287 2288 2289 2290
{
	handle_t *handle;
	struct inode *inode;
	int err, retries = 0;

	if (!new_valid_dev(rdev))
		return -EINVAL;

2291
	dquot_initialize(dir);
2292

2293
retry:
2294 2295
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
2296
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
2297 2298 2299 2300
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2301
		ext4_handle_sync(handle);
2302

2303
	inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0, NULL);
2304 2305 2306
	err = PTR_ERR(inode);
	if (!IS_ERR(inode)) {
		init_special_inode(inode, inode->i_mode, rdev);
2307 2308
		inode->i_op = &ext4_special_inode_operations;
		err = ext4_add_nondir(handle, dentry, inode);
2309
	}
2310 2311
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2312 2313 2314 2315
		goto retry;
	return err;
}

2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345
struct ext4_dir_entry_2 *ext4_init_dot_dotdot(struct inode *inode,
			  struct ext4_dir_entry_2 *de,
			  int blocksize, int csum_size,
			  unsigned int parent_ino, int dotdot_real_len)
{
	de->inode = cpu_to_le32(inode->i_ino);
	de->name_len = 1;
	de->rec_len = ext4_rec_len_to_disk(EXT4_DIR_REC_LEN(de->name_len),
					   blocksize);
	strcpy(de->name, ".");
	ext4_set_de_type(inode->i_sb, de, S_IFDIR);

	de = ext4_next_entry(de, blocksize);
	de->inode = cpu_to_le32(parent_ino);
	de->name_len = 2;
	if (!dotdot_real_len)
		de->rec_len = ext4_rec_len_to_disk(blocksize -
					(csum_size + EXT4_DIR_REC_LEN(1)),
					blocksize);
	else
		de->rec_len = ext4_rec_len_to_disk(
				EXT4_DIR_REC_LEN(de->name_len), blocksize);
	strcpy(de->name, "..");
	ext4_set_de_type(inode->i_sb, de, S_IFDIR);

	return ext4_next_entry(de, blocksize);
}

static int ext4_init_new_dir(handle_t *handle, struct inode *dir,
			     struct inode *inode)
2346
{
2347
	struct buffer_head *dir_block = NULL;
2348
	struct ext4_dir_entry_2 *de;
2349
	struct ext4_dir_entry_tail *t;
2350
	unsigned int blocksize = dir->i_sb->s_blocksize;
2351
	int csum_size = 0;
2352
	int err;
2353

2354 2355 2356 2357
	if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
				       EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
		csum_size = sizeof(struct ext4_dir_entry_tail);

2358 2359 2360 2361 2362 2363 2364 2365
	if (ext4_test_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA)) {
		err = ext4_try_create_inline_dir(handle, dir, inode);
		if (err < 0 && err != -ENOSPC)
			goto out;
		if (!err)
			goto out;
	}

2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404
	inode->i_size = EXT4_I(inode)->i_disksize = blocksize;
	dir_block = ext4_bread(handle, inode, 0, 1, &err);
	if (!(dir_block = ext4_bread(handle, inode, 0, 1, &err))) {
		if (!err) {
			err = -EIO;
			ext4_error(inode->i_sb,
				   "Directory hole detected on inode %lu\n",
				   inode->i_ino);
		}
		goto out;
	}
	BUFFER_TRACE(dir_block, "get_write_access");
	err = ext4_journal_get_write_access(handle, dir_block);
	if (err)
		goto out;
	de = (struct ext4_dir_entry_2 *)dir_block->b_data;
	ext4_init_dot_dotdot(inode, de, blocksize, csum_size, dir->i_ino, 0);
	set_nlink(inode, 2);
	if (csum_size) {
		t = EXT4_DIRENT_TAIL(dir_block->b_data, blocksize);
		initialize_dirent_tail(t, blocksize);
	}

	BUFFER_TRACE(dir_block, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_dirent_node(handle, inode, dir_block);
	if (err)
		goto out;
	set_buffer_verified(dir_block);
out:
	brelse(dir_block);
	return err;
}

static int ext4_mkdir(struct inode *dir, struct dentry *dentry, umode_t mode)
{
	handle_t *handle;
	struct inode *inode;
	int err, retries = 0;

2405
	if (EXT4_DIR_LINK_MAX(dir))
2406 2407
		return -EMLINK;

2408
	dquot_initialize(dir);
2409

2410
retry:
2411 2412
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
2413
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
2414 2415 2416 2417
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2418
		ext4_handle_sync(handle);
2419

2420
	inode = ext4_new_inode(handle, dir, S_IFDIR | mode,
2421
			       &dentry->d_name, 0, NULL);
2422 2423 2424 2425
	err = PTR_ERR(inode);
	if (IS_ERR(inode))
		goto out_stop;

2426 2427
	inode->i_op = &ext4_dir_inode_operations;
	inode->i_fop = &ext4_dir_operations;
2428
	err = ext4_init_new_dir(handle, dir, inode);
2429 2430 2431 2432 2433
	if (err)
		goto out_clear_inode;
	err = ext4_mark_inode_dirty(handle, inode);
	if (!err)
		err = ext4_add_entry(handle, dentry, inode);
2434
	if (err) {
2435 2436
out_clear_inode:
		clear_nlink(inode);
A
Al Viro 已提交
2437
		unlock_new_inode(inode);
2438
		ext4_mark_inode_dirty(handle, inode);
2439
		iput(inode);
2440 2441
		goto out_stop;
	}
2442
	ext4_inc_count(handle, dir);
2443
	ext4_update_dx_flag(dir);
2444 2445 2446
	err = ext4_mark_inode_dirty(handle, dir);
	if (err)
		goto out_clear_inode;
A
Al Viro 已提交
2447
	unlock_new_inode(inode);
2448
	d_instantiate(dentry, inode);
2449
out_stop:
2450 2451
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2452 2453 2454 2455 2456 2457 2458
		goto retry;
	return err;
}

/*
 * routine to check that the specified directory is empty (for rmdir)
 */
2459
static int empty_dir(struct inode *inode)
2460
{
2461
	unsigned int offset;
2462 2463 2464
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de, *de1;
	struct super_block *sb;
2465 2466
	int err = 0;

T
Tao Ma 已提交
2467 2468 2469 2470 2471 2472 2473 2474
	if (ext4_has_inline_data(inode)) {
		int has_inline_data = 1;

		err = empty_inline_dir(inode, &has_inline_data);
		if (has_inline_data)
			return err;
	}

2475
	sb = inode->i_sb;
2476
	if (inode->i_size < EXT4_DIR_REC_LEN(1) + EXT4_DIR_REC_LEN(2) ||
2477
	    !(bh = ext4_bread(NULL, inode, 0, 0, &err))) {
2478
		if (err)
2479 2480
			EXT4_ERROR_INODE(inode,
				"error %d reading directory lblock 0", err);
2481
		else
2482
			ext4_warning(inode->i_sb,
2483 2484 2485 2486
				     "bad directory (dir #%lu) - no data block",
				     inode->i_ino);
		return 1;
	}
2487 2488 2489 2490 2491 2492 2493 2494
	if (!buffer_verified(bh) &&
	    !ext4_dirent_csum_verify(inode,
			(struct ext4_dir_entry *)bh->b_data)) {
		EXT4_ERROR_INODE(inode, "checksum error reading directory "
				 "lblock 0");
		return -EIO;
	}
	set_buffer_verified(bh);
2495
	de = (struct ext4_dir_entry_2 *) bh->b_data;
2496
	de1 = ext4_next_entry(de, sb->s_blocksize);
2497 2498
	if (le32_to_cpu(de->inode) != inode->i_ino ||
			!le32_to_cpu(de1->inode) ||
2499 2500
			strcmp(".", de->name) ||
			strcmp("..", de1->name)) {
2501
		ext4_warning(inode->i_sb,
2502 2503 2504
			     "bad directory (dir #%lu) - no `.' or `..'",
			     inode->i_ino);
		brelse(bh);
2505 2506
		return 1;
	}
2507 2508 2509
	offset = ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize) +
		 ext4_rec_len_from_disk(de1->rec_len, sb->s_blocksize);
	de = ext4_next_entry(de1, sb->s_blocksize);
2510
	while (offset < inode->i_size) {
2511
		if (!bh ||
2512 2513
		    (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
			unsigned int lblock;
2514
			err = 0;
2515
			brelse(bh);
2516 2517
			lblock = offset >> EXT4_BLOCK_SIZE_BITS(sb);
			bh = ext4_bread(NULL, inode, lblock, 0, &err);
2518 2519
			if (!bh) {
				if (err)
2520 2521 2522
					EXT4_ERROR_INODE(inode,
						"error %d reading directory "
						"lblock %u", err, lblock);
C
Carlos Maiolino 已提交
2523 2524 2525 2526 2527
				else
					ext4_warning(inode->i_sb,
						"bad directory (dir #%lu) - no data block",
						inode->i_ino);

2528 2529 2530
				offset += sb->s_blocksize;
				continue;
			}
2531 2532 2533 2534 2535 2536 2537 2538
			if (!buffer_verified(bh) &&
			    !ext4_dirent_csum_verify(inode,
					(struct ext4_dir_entry *)bh->b_data)) {
				EXT4_ERROR_INODE(inode, "checksum error "
						 "reading directory lblock 0");
				return -EIO;
			}
			set_buffer_verified(bh);
2539
			de = (struct ext4_dir_entry_2 *) bh->b_data;
2540
		}
2541 2542
		if (ext4_check_dir_entry(inode, NULL, de, bh,
					 bh->b_data, bh->b_size, offset)) {
2543
			de = (struct ext4_dir_entry_2 *)(bh->b_data +
2544 2545 2546 2547 2548
							 sb->s_blocksize);
			offset = (offset | (sb->s_blocksize - 1)) + 1;
			continue;
		}
		if (le32_to_cpu(de->inode)) {
2549
			brelse(bh);
2550 2551
			return 0;
		}
2552 2553
		offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
		de = ext4_next_entry(de, sb->s_blocksize);
2554
	}
2555
	brelse(bh);
2556 2557 2558
	return 1;
}

2559
/* ext4_orphan_add() links an unlinked or truncated inode into a list of
2560 2561 2562 2563 2564
 * such inodes, starting at the superblock, in case we crash before the
 * file is closed/deleted, or in case the inode truncate spans multiple
 * transactions and the last transaction is not recovered after a crash.
 *
 * At filesystem recovery time, we walk this list deleting unlinked
2565
 * inodes and truncating linked inodes in ext4_orphan_cleanup().
2566
 */
2567
int ext4_orphan_add(handle_t *handle, struct inode *inode)
2568 2569
{
	struct super_block *sb = inode->i_sb;
2570
	struct ext4_iloc iloc;
2571 2572
	int err = 0, rc;

2573
	if (!EXT4_SB(sb)->s_journal)
2574 2575
		return 0;

2576
	mutex_lock(&EXT4_SB(sb)->s_orphan_lock);
2577
	if (!list_empty(&EXT4_I(inode)->i_orphan))
2578 2579
		goto out_unlock;

2580 2581 2582 2583 2584
	/*
	 * Orphan handling is only valid for files with data blocks
	 * being truncated, or files being unlinked. Note that we either
	 * hold i_mutex, or the inode can not be referenced from outside,
	 * so i_nlink should not be bumped due to race
2585
	 */
2586 2587
	J_ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
		  S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
2588

2589 2590
	BUFFER_TRACE(EXT4_SB(sb)->s_sbh, "get_write_access");
	err = ext4_journal_get_write_access(handle, EXT4_SB(sb)->s_sbh);
2591 2592 2593
	if (err)
		goto out_unlock;

2594
	err = ext4_reserve_inode_write(handle, inode, &iloc);
2595 2596
	if (err)
		goto out_unlock;
2597 2598 2599 2600 2601 2602 2603
	/*
	 * Due to previous errors inode may be already a part of on-disk
	 * orphan list. If so skip on-disk list modification.
	 */
	if (NEXT_ORPHAN(inode) && NEXT_ORPHAN(inode) <=
		(le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count)))
			goto mem_insert;
2604 2605

	/* Insert this inode at the head of the on-disk orphan list... */
2606 2607
	NEXT_ORPHAN(inode) = le32_to_cpu(EXT4_SB(sb)->s_es->s_last_orphan);
	EXT4_SB(sb)->s_es->s_last_orphan = cpu_to_le32(inode->i_ino);
2608
	err = ext4_handle_dirty_super(handle, sb);
2609
	rc = ext4_mark_iloc_dirty(handle, inode, &iloc);
2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620
	if (!err)
		err = rc;

	/* Only add to the head of the in-memory list if all the
	 * previous operations succeeded.  If the orphan_add is going to
	 * fail (possibly taking the journal offline), we can't risk
	 * leaving the inode on the orphan list: stray orphan-list
	 * entries can cause panics at unmount time.
	 *
	 * This is safe: on error we're going to ignore the orphan list
	 * anyway on the next recovery. */
2621
mem_insert:
2622
	if (!err)
2623
		list_add(&EXT4_I(inode)->i_orphan, &EXT4_SB(sb)->s_orphan);
2624 2625 2626 2627 2628

	jbd_debug(4, "superblock will point to %lu\n", inode->i_ino);
	jbd_debug(4, "orphan inode %lu will point to %d\n",
			inode->i_ino, NEXT_ORPHAN(inode));
out_unlock:
2629
	mutex_unlock(&EXT4_SB(sb)->s_orphan_lock);
2630
	ext4_std_error(inode->i_sb, err);
2631 2632 2633 2634
	return err;
}

/*
2635
 * ext4_orphan_del() removes an unlinked or truncated inode from the list
2636 2637
 * of such inodes stored on disk, because it is finally being cleaned up.
 */
2638
int ext4_orphan_del(handle_t *handle, struct inode *inode)
2639 2640
{
	struct list_head *prev;
2641 2642
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi;
2643
	__u32 ino_next;
2644
	struct ext4_iloc iloc;
2645 2646
	int err = 0;

2647
	if (!EXT4_SB(inode->i_sb)->s_journal)
2648 2649
		return 0;

2650 2651 2652
	mutex_lock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
	if (list_empty(&ei->i_orphan))
		goto out;
2653 2654 2655

	ino_next = NEXT_ORPHAN(inode);
	prev = ei->i_orphan.prev;
2656
	sbi = EXT4_SB(inode->i_sb);
2657 2658 2659 2660 2661 2662 2663 2664 2665

	jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino);

	list_del_init(&ei->i_orphan);

	/* If we're on an error path, we may not have a valid
	 * transaction handle with which to update the orphan list on
	 * disk, but we still need to remove the inode from the linked
	 * list in memory. */
2666
	if (!handle)
2667 2668
		goto out;

2669
	err = ext4_reserve_inode_write(handle, inode, &iloc);
2670 2671 2672 2673
	if (err)
		goto out_err;

	if (prev == &sbi->s_orphan) {
2674
		jbd_debug(4, "superblock will point to %u\n", ino_next);
2675
		BUFFER_TRACE(sbi->s_sbh, "get_write_access");
2676
		err = ext4_journal_get_write_access(handle, sbi->s_sbh);
2677 2678 2679
		if (err)
			goto out_brelse;
		sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
2680
		err = ext4_handle_dirty_super(handle, inode->i_sb);
2681
	} else {
2682
		struct ext4_iloc iloc2;
2683
		struct inode *i_prev =
2684
			&list_entry(prev, struct ext4_inode_info, i_orphan)->vfs_inode;
2685

2686
		jbd_debug(4, "orphan inode %lu will point to %u\n",
2687
			  i_prev->i_ino, ino_next);
2688
		err = ext4_reserve_inode_write(handle, i_prev, &iloc2);
2689 2690 2691
		if (err)
			goto out_brelse;
		NEXT_ORPHAN(i_prev) = ino_next;
2692
		err = ext4_mark_iloc_dirty(handle, i_prev, &iloc2);
2693 2694 2695 2696
	}
	if (err)
		goto out_brelse;
	NEXT_ORPHAN(inode) = 0;
2697
	err = ext4_mark_iloc_dirty(handle, inode, &iloc);
2698 2699

out_err:
2700
	ext4_std_error(inode->i_sb, err);
2701
out:
2702
	mutex_unlock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
2703 2704 2705 2706 2707 2708 2709
	return err;

out_brelse:
	brelse(iloc.bh);
	goto out_err;
}

2710
static int ext4_rmdir(struct inode *dir, struct dentry *dentry)
2711 2712
{
	int retval;
2713 2714 2715
	struct inode *inode;
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de;
2716 2717 2718 2719
	handle_t *handle;

	/* Initialize quotas before so that eventual writes go in
	 * separate transaction */
2720 2721
	dquot_initialize(dir);
	dquot_initialize(dentry->d_inode);
2722

2723
	handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
2724 2725 2726 2727
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	retval = -ENOENT;
2728
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
2729 2730 2731 2732
	if (!bh)
		goto end_rmdir;

	if (IS_DIRSYNC(dir))
2733
		ext4_handle_sync(handle);
2734 2735 2736 2737 2738 2739 2740 2741

	inode = dentry->d_inode;

	retval = -EIO;
	if (le32_to_cpu(de->inode) != inode->i_ino)
		goto end_rmdir;

	retval = -ENOTEMPTY;
2742
	if (!empty_dir(inode))
2743 2744
		goto end_rmdir;

2745
	retval = ext4_delete_entry(handle, dir, de, bh);
2746 2747
	if (retval)
		goto end_rmdir;
2748
	if (!EXT4_DIR_LINK_EMPTY(inode))
2749
		ext4_warning(inode->i_sb,
2750 2751
			     "empty directory has too many links (%d)",
			     inode->i_nlink);
2752 2753 2754 2755 2756 2757
	inode->i_version++;
	clear_nlink(inode);
	/* There's no need to set i_disksize: the fact that i_nlink is
	 * zero will ensure that the right thing happens during any
	 * recovery. */
	inode->i_size = 0;
2758
	ext4_orphan_add(handle, inode);
K
Kalpak Shah 已提交
2759
	inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
2760
	ext4_mark_inode_dirty(handle, inode);
2761
	ext4_dec_count(handle, dir);
2762 2763
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
2764 2765

end_rmdir:
2766
	ext4_journal_stop(handle);
2767
	brelse(bh);
2768 2769 2770
	return retval;
}

2771
static int ext4_unlink(struct inode *dir, struct dentry *dentry)
2772 2773
{
	int retval;
2774 2775 2776
	struct inode *inode;
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de;
2777 2778
	handle_t *handle;

2779
	trace_ext4_unlink_enter(dir, dentry);
2780 2781
	/* Initialize quotas before so that eventual writes go
	 * in separate transaction */
2782 2783
	dquot_initialize(dir);
	dquot_initialize(dentry->d_inode);
2784

2785
	handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
2786 2787 2788 2789
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2790
		ext4_handle_sync(handle);
2791 2792

	retval = -ENOENT;
2793
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
2794 2795 2796 2797 2798 2799 2800 2801 2802 2803
	if (!bh)
		goto end_unlink;

	inode = dentry->d_inode;

	retval = -EIO;
	if (le32_to_cpu(de->inode) != inode->i_ino)
		goto end_unlink;

	if (!inode->i_nlink) {
2804
		ext4_warning(inode->i_sb,
2805 2806
			     "Deleting nonexistent file (%lu), %d",
			     inode->i_ino, inode->i_nlink);
M
Miklos Szeredi 已提交
2807
		set_nlink(inode, 1);
2808
	}
2809
	retval = ext4_delete_entry(handle, dir, de, bh);
2810 2811
	if (retval)
		goto end_unlink;
K
Kalpak Shah 已提交
2812
	dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
2813 2814
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
2815
	drop_nlink(inode);
2816
	if (!inode->i_nlink)
2817
		ext4_orphan_add(handle, inode);
K
Kalpak Shah 已提交
2818
	inode->i_ctime = ext4_current_time(inode);
2819
	ext4_mark_inode_dirty(handle, inode);
2820 2821 2822
	retval = 0;

end_unlink:
2823
	ext4_journal_stop(handle);
2824
	brelse(bh);
2825
	trace_ext4_unlink_exit(dentry, retval);
2826 2827 2828
	return retval;
}

2829 2830
static int ext4_symlink(struct inode *dir,
			struct dentry *dentry, const char *symname)
2831 2832
{
	handle_t *handle;
2833
	struct inode *inode;
2834
	int l, err, retries = 0;
2835
	int credits;
2836 2837 2838 2839 2840

	l = strlen(symname)+1;
	if (l > dir->i_sb->s_blocksize)
		return -ENAMETOOLONG;

2841
	dquot_initialize(dir);
2842

2843 2844 2845 2846
	if (l > EXT4_N_BLOCKS * 4) {
		/*
		 * For non-fast symlinks, we just allocate inode and put it on
		 * orphan list in the first transaction => we need bitmap,
2847 2848
		 * group descriptor, sb, inode block, quota blocks, and
		 * possibly selinux xattr blocks.
2849
		 */
2850 2851
		credits = 4 + EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb) +
			  EXT4_XATTR_TRANS_BLOCKS;
2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862
	} else {
		/*
		 * Fast symlink. We have to add entry to directory
		 * (EXT4_DATA_TRANS_BLOCKS + EXT4_INDEX_EXTRA_TRANS_BLOCKS),
		 * allocate new inode (bitmap, group descriptor, inode block,
		 * quota blocks, sb is already counted in previous macros).
		 */
		credits = EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
			  EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
			  EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb);
	}
2863
retry:
2864
	handle = ext4_journal_start(dir, credits);
2865 2866 2867 2868
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2869
		ext4_handle_sync(handle);
2870

2871
	inode = ext4_new_inode(handle, dir, S_IFLNK|S_IRWXUGO,
2872
			       &dentry->d_name, 0, NULL);
2873 2874 2875 2876
	err = PTR_ERR(inode);
	if (IS_ERR(inode))
		goto out_stop;

2877
	if (l > EXT4_N_BLOCKS * 4) {
2878 2879
		inode->i_op = &ext4_symlink_inode_operations;
		ext4_set_aops(inode);
2880
		/*
2881 2882 2883 2884 2885 2886 2887 2888
		 * We cannot call page_symlink() with transaction started
		 * because it calls into ext4_write_begin() which can wait
		 * for transaction commit if we are running out of space
		 * and thus we deadlock. So we have to stop transaction now
		 * and restart it when symlink contents is written.
		 * 
		 * To keep fs consistent in case of crash, we have to put inode
		 * to orphan list in the mean time.
2889
		 */
2890 2891 2892 2893 2894
		drop_nlink(inode);
		err = ext4_orphan_add(handle, inode);
		ext4_journal_stop(handle);
		if (err)
			goto err_drop_inode;
2895
		err = __page_symlink(inode, symname, l, 1);
2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908
		if (err)
			goto err_drop_inode;
		/*
		 * Now inode is being linked into dir (EXT4_DATA_TRANS_BLOCKS
		 * + EXT4_INDEX_EXTRA_TRANS_BLOCKS), inode is also modified
		 */
		handle = ext4_journal_start(dir,
				EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
				EXT4_INDEX_EXTRA_TRANS_BLOCKS + 1);
		if (IS_ERR(handle)) {
			err = PTR_ERR(handle);
			goto err_drop_inode;
		}
2909
		set_nlink(inode, 1);
2910
		err = ext4_orphan_del(handle, inode);
2911
		if (err) {
2912
			ext4_journal_stop(handle);
2913
			clear_nlink(inode);
2914
			goto err_drop_inode;
2915 2916
		}
	} else {
2917
		/* clear the extent format for fast symlink */
2918
		ext4_clear_inode_flag(inode, EXT4_INODE_EXTENTS);
2919
		inode->i_op = &ext4_fast_symlink_inode_operations;
2920
		memcpy((char *)&EXT4_I(inode)->i_data, symname, l);
2921 2922
		inode->i_size = l-1;
	}
2923 2924
	EXT4_I(inode)->i_disksize = inode->i_size;
	err = ext4_add_nondir(handle, dentry, inode);
2925
out_stop:
2926 2927
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2928 2929
		goto retry;
	return err;
2930 2931 2932 2933
err_drop_inode:
	unlock_new_inode(inode);
	iput(inode);
	return err;
2934 2935
}

2936 2937
static int ext4_link(struct dentry *old_dentry,
		     struct inode *dir, struct dentry *dentry)
2938 2939 2940 2941 2942
{
	handle_t *handle;
	struct inode *inode = old_dentry->d_inode;
	int err, retries = 0;

2943
	if (inode->i_nlink >= EXT4_LINK_MAX)
2944
		return -EMLINK;
2945

2946
	dquot_initialize(dir);
2947

2948
retry:
2949 2950
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS);
2951 2952 2953 2954
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2955
		ext4_handle_sync(handle);
2956

K
Kalpak Shah 已提交
2957
	inode->i_ctime = ext4_current_time(inode);
2958
	ext4_inc_count(handle, inode);
A
Al Viro 已提交
2959
	ihold(inode);
2960

A
Al Viro 已提交
2961 2962 2963 2964 2965 2966 2967 2968
	err = ext4_add_entry(handle, dentry, inode);
	if (!err) {
		ext4_mark_inode_dirty(handle, inode);
		d_instantiate(dentry, inode);
	} else {
		drop_nlink(inode);
		iput(inode);
	}
2969 2970
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2971 2972 2973 2974
		goto retry;
	return err;
}

2975 2976
#define PARENT_INO(buffer, size) \
	(ext4_next_entry((struct ext4_dir_entry_2 *)(buffer), size)->inode)
2977 2978 2979 2980 2981

/*
 * Anybody can rename anything with this: the permission checks are left to the
 * higher-level routines.
 */
2982 2983
static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry,
		       struct inode *new_dir, struct dentry *new_dentry)
2984 2985
{
	handle_t *handle;
2986 2987 2988
	struct inode *old_inode, *new_inode;
	struct buffer_head *old_bh, *new_bh, *dir_bh;
	struct ext4_dir_entry_2 *old_de, *new_de;
2989
	int retval, force_da_alloc = 0;
2990

2991 2992
	dquot_initialize(old_dir);
	dquot_initialize(new_dir);
2993

2994 2995 2996 2997 2998
	old_bh = new_bh = dir_bh = NULL;

	/* Initialize quotas before so that eventual writes go
	 * in separate transaction */
	if (new_dentry->d_inode)
2999
		dquot_initialize(new_dentry->d_inode);
3000 3001 3002
	handle = ext4_journal_start(old_dir, 2 *
					EXT4_DATA_TRANS_BLOCKS(old_dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2);
3003 3004 3005 3006
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir))
3007
		ext4_handle_sync(handle);
3008

3009
	old_bh = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de);
3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021
	/*
	 *  Check for inode number is _not_ due to possible IO errors.
	 *  We might rmdir the source, keep it as pwd of some process
	 *  and merrily kill the link to whatever was created under the
	 *  same name. Goodbye sticky bit ;-<
	 */
	old_inode = old_dentry->d_inode;
	retval = -ENOENT;
	if (!old_bh || le32_to_cpu(old_de->inode) != old_inode->i_ino)
		goto end_rename;

	new_inode = new_dentry->d_inode;
3022
	new_bh = ext4_find_entry(new_dir, &new_dentry->d_name, &new_de);
3023 3024
	if (new_bh) {
		if (!new_inode) {
3025
			brelse(new_bh);
3026 3027 3028 3029 3030 3031
			new_bh = NULL;
		}
	}
	if (S_ISDIR(old_inode->i_mode)) {
		if (new_inode) {
			retval = -ENOTEMPTY;
3032
			if (!empty_dir(new_inode))
3033 3034 3035
				goto end_rename;
		}
		retval = -EIO;
C
Carlos Maiolino 已提交
3036 3037 3038 3039 3040 3041 3042
		if (!(dir_bh = ext4_bread(handle, old_inode, 0, 0, &retval))) {
			if (!retval) {
				retval = -EIO;
				ext4_error(old_inode->i_sb,
					   "Directory hole detected on inode %lu\n",
					   old_inode->i_ino);
			}
3043
			goto end_rename;
C
Carlos Maiolino 已提交
3044
		}
3045 3046 3047 3048 3049
		if (!buffer_verified(dir_bh) &&
		    !ext4_dirent_csum_verify(old_inode,
				(struct ext4_dir_entry *)dir_bh->b_data))
			goto end_rename;
		set_buffer_verified(dir_bh);
3050 3051
		if (le32_to_cpu(PARENT_INO(dir_bh->b_data,
				old_dir->i_sb->s_blocksize)) != old_dir->i_ino)
3052 3053
			goto end_rename;
		retval = -EMLINK;
3054
		if (!new_inode && new_dir != old_dir &&
3055
		    EXT4_DIR_LINK_MAX(new_dir))
3056
			goto end_rename;
3057 3058 3059 3060
		BUFFER_TRACE(dir_bh, "get_write_access");
		retval = ext4_journal_get_write_access(handle, dir_bh);
		if (retval)
			goto end_rename;
3061 3062
	}
	if (!new_bh) {
3063
		retval = ext4_add_entry(handle, new_dentry, old_inode);
3064 3065 3066 3067
		if (retval)
			goto end_rename;
	} else {
		BUFFER_TRACE(new_bh, "get write access");
3068 3069 3070
		retval = ext4_journal_get_write_access(handle, new_bh);
		if (retval)
			goto end_rename;
3071
		new_de->inode = cpu_to_le32(old_inode->i_ino);
3072 3073
		if (EXT4_HAS_INCOMPAT_FEATURE(new_dir->i_sb,
					      EXT4_FEATURE_INCOMPAT_FILETYPE))
3074 3075
			new_de->file_type = old_de->file_type;
		new_dir->i_version++;
3076 3077 3078
		new_dir->i_ctime = new_dir->i_mtime =
					ext4_current_time(new_dir);
		ext4_mark_inode_dirty(handle, new_dir);
3079
		BUFFER_TRACE(new_bh, "call ext4_handle_dirty_metadata");
3080
		retval = ext4_handle_dirty_dirent_node(handle, new_dir, new_bh);
3081 3082 3083 3084
		if (unlikely(retval)) {
			ext4_std_error(new_dir->i_sb, retval);
			goto end_rename;
		}
3085 3086 3087 3088 3089 3090 3091 3092
		brelse(new_bh);
		new_bh = NULL;
	}

	/*
	 * Like most other Unix systems, set the ctime for inodes on a
	 * rename.
	 */
K
Kalpak Shah 已提交
3093
	old_inode->i_ctime = ext4_current_time(old_inode);
3094
	ext4_mark_inode_dirty(handle, old_inode);
3095 3096 3097 3098 3099 3100 3101

	/*
	 * ok, that's it
	 */
	if (le32_to_cpu(old_de->inode) != old_inode->i_ino ||
	    old_de->name_len != old_dentry->d_name.len ||
	    strncmp(old_de->name, old_dentry->d_name.name, old_de->name_len) ||
3102
	    (retval = ext4_delete_entry(handle, old_dir,
3103 3104 3105 3106 3107 3108
					old_de, old_bh)) == -ENOENT) {
		/* old_de could have moved from under us during htree split, so
		 * make sure that we are deleting the right entry.  We might
		 * also be pointing to a stale entry in the unused part of
		 * old_bh so just checking inum and the name isn't enough. */
		struct buffer_head *old_bh2;
3109
		struct ext4_dir_entry_2 *old_de2;
3110

3111
		old_bh2 = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de2);
3112
		if (old_bh2) {
3113
			retval = ext4_delete_entry(handle, old_dir,
3114 3115 3116 3117 3118
						   old_de2, old_bh2);
			brelse(old_bh2);
		}
	}
	if (retval) {
3119
		ext4_warning(old_dir->i_sb,
3120 3121 3122 3123 3124
				"Deleting old file (%lu), %d, error=%d",
				old_dir->i_ino, old_dir->i_nlink, retval);
	}

	if (new_inode) {
3125
		ext4_dec_count(handle, new_inode);
K
Kalpak Shah 已提交
3126
		new_inode->i_ctime = ext4_current_time(new_inode);
3127
	}
K
Kalpak Shah 已提交
3128
	old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
3129
	ext4_update_dx_flag(old_dir);
3130
	if (dir_bh) {
3131 3132
		PARENT_INO(dir_bh->b_data, new_dir->i_sb->s_blocksize) =
						cpu_to_le32(new_dir->i_ino);
3133
		BUFFER_TRACE(dir_bh, "call ext4_handle_dirty_metadata");
3134 3135 3136 3137 3138 3139 3140 3141 3142
		if (is_dx(old_inode)) {
			retval = ext4_handle_dirty_dx_node(handle,
							   old_inode,
							   dir_bh);
		} else {
			retval = ext4_handle_dirty_dirent_node(handle,
							       old_inode,
							       dir_bh);
		}
3143 3144 3145 3146
		if (retval) {
			ext4_std_error(old_dir->i_sb, retval);
			goto end_rename;
		}
3147
		ext4_dec_count(handle, old_dir);
3148
		if (new_inode) {
3149
			/* checked empty_dir above, can't have another parent,
3150
			 * ext4_dec_count() won't work for many-linked dirs */
3151
			clear_nlink(new_inode);
3152
		} else {
3153
			ext4_inc_count(handle, new_dir);
3154 3155
			ext4_update_dx_flag(new_dir);
			ext4_mark_inode_dirty(handle, new_dir);
3156 3157
		}
	}
3158
	ext4_mark_inode_dirty(handle, old_dir);
3159
	if (new_inode) {
3160
		ext4_mark_inode_dirty(handle, new_inode);
3161
		if (!new_inode->i_nlink)
3162
			ext4_orphan_add(handle, new_inode);
3163 3164
		if (!test_opt(new_dir->i_sb, NO_AUTO_DA_ALLOC))
			force_da_alloc = 1;
3165 3166 3167 3168
	}
	retval = 0;

end_rename:
3169 3170 3171
	brelse(dir_bh);
	brelse(old_bh);
	brelse(new_bh);
3172
	ext4_journal_stop(handle);
3173 3174
	if (retval == 0 && force_da_alloc)
		ext4_alloc_da_blocks(old_inode);
3175 3176 3177 3178 3179 3180
	return retval;
}

/*
 * directories can handle most operations...
 */
3181
const struct inode_operations ext4_dir_inode_operations = {
3182 3183 3184 3185 3186 3187 3188 3189 3190 3191
	.create		= ext4_create,
	.lookup		= ext4_lookup,
	.link		= ext4_link,
	.unlink		= ext4_unlink,
	.symlink	= ext4_symlink,
	.mkdir		= ext4_mkdir,
	.rmdir		= ext4_rmdir,
	.mknod		= ext4_mknod,
	.rename		= ext4_rename,
	.setattr	= ext4_setattr,
T
Theodore Ts'o 已提交
3192
#ifdef CONFIG_EXT4_FS_XATTR
3193 3194
	.setxattr	= generic_setxattr,
	.getxattr	= generic_getxattr,
3195
	.listxattr	= ext4_listxattr,
3196 3197
	.removexattr	= generic_removexattr,
#endif
3198
	.get_acl	= ext4_get_acl,
3199
	.fiemap         = ext4_fiemap,
3200 3201
};

3202
const struct inode_operations ext4_special_inode_operations = {
3203
	.setattr	= ext4_setattr,
T
Theodore Ts'o 已提交
3204
#ifdef CONFIG_EXT4_FS_XATTR
3205 3206
	.setxattr	= generic_setxattr,
	.getxattr	= generic_getxattr,
3207
	.listxattr	= ext4_listxattr,
3208 3209
	.removexattr	= generic_removexattr,
#endif
3210
	.get_acl	= ext4_get_acl,
3211
};