namei.c 68.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 43 44 45 46 47

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

/*
 * define how far ahead to read directories while searching them.
 */
#define NAMEI_RA_CHUNKS  2
#define NAMEI_RA_BLOCKS  4
D
Dave Kleikamp 已提交
48
#define NAMEI_RA_SIZE	     (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
49 50
#define NAMEI_RA_INDEX(c,b)  (((c) * NAMEI_RA_BLOCKS) + (b))

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

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

59 60
	bh = ext4_bread(handle, inode, *block, 1, err);
	if (bh) {
61
		inode->i_size += inode->i_sb->s_blocksize;
62
		EXT4_I(inode)->i_disksize = inode->i_size;
63 64 65 66 67
		*err = ext4_journal_get_write_access(handle, bh);
		if (*err) {
			brelse(bh);
			bh = NULL;
		}
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 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
	}
	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;
143 144
	u16 offs;
	u16 size;
145 146
};

A
Aneesh Kumar K.V 已提交
147 148
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);
149 150 151 152 153 154 155 156
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);
157
static struct dx_frame *dx_probe(const struct qstr *d_name,
158 159 160 161
				 struct inode *dir,
				 struct dx_hash_info *hinfo,
				 struct dx_frame *frame,
				 int *err);
162
static void dx_release(struct dx_frame *frames);
163
static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
164
		       struct dx_hash_info *hinfo, struct dx_map_entry map[]);
165
static void dx_sort_map(struct dx_map_entry *map, unsigned count);
166
static struct ext4_dir_entry_2 *dx_move_dirents(char *from, char *to,
167
		struct dx_map_entry *offsets, int count, unsigned blocksize);
168
static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize);
A
Aneesh Kumar K.V 已提交
169 170
static void dx_insert_block(struct dx_frame *frame,
					u32 hash, ext4_lblk_t block);
171
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
172 173 174
				 struct dx_frame *frame,
				 struct dx_frame *frames,
				 __u32 *start_hash);
175 176 177 178
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);
179
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
180 181
			     struct inode *inode);

182 183 184 185
/*
 * p is at least 6 bytes before the end of page
 */
static inline struct ext4_dir_entry_2 *
186
ext4_next_entry(struct ext4_dir_entry_2 *p, unsigned long blocksize)
187 188
{
	return (struct ext4_dir_entry_2 *)((char *)p +
189
		ext4_rec_len_from_disk(p->rec_len, blocksize));
190 191
}

192 193 194 195 196
/*
 * Future: use high four bits of block for coalesce-on-delete flags
 * Mask them off for now.
 */

A
Aneesh Kumar K.V 已提交
197
static inline ext4_lblk_t dx_get_block(struct dx_entry *entry)
198 199 200 201
{
	return le32_to_cpu(entry->block) & 0x00ffffff;
}

A
Aneesh Kumar K.V 已提交
202
static inline void dx_set_block(struct dx_entry *entry, ext4_lblk_t value)
203 204 205 206
{
	entry->block = cpu_to_le32(value);
}

207
static inline unsigned dx_get_hash(struct dx_entry *entry)
208 209 210 211
{
	return le32_to_cpu(entry->hash);
}

212
static inline void dx_set_hash(struct dx_entry *entry, unsigned value)
213 214 215 216
{
	entry->hash = cpu_to_le32(value);
}

217
static inline unsigned dx_get_count(struct dx_entry *entries)
218 219 220 221
{
	return le16_to_cpu(((struct dx_countlimit *) entries)->count);
}

222
static inline unsigned dx_get_limit(struct dx_entry *entries)
223 224 225 226
{
	return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
}

227
static inline void dx_set_count(struct dx_entry *entries, unsigned value)
228 229 230 231
{
	((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
}

232
static inline void dx_set_limit(struct dx_entry *entries, unsigned value)
233 234 235 236
{
	((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
}

237
static inline unsigned dx_root_limit(struct inode *dir, unsigned infosize)
238
{
239 240
	unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(1) -
		EXT4_DIR_REC_LEN(2) - infosize;
241
	return entry_space / sizeof(struct dx_entry);
242 243
}

244
static inline unsigned dx_node_limit(struct inode *dir)
245
{
246
	unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(0);
247
	return entry_space / sizeof(struct dx_entry);
248 249 250 251 252 253
}

/*
 * Debug
 */
#ifdef DX_DEBUG
254
static void dx_show_index(char * label, struct dx_entry *entries)
255
{
A
Andrew Morton 已提交
256
	int i, n = dx_get_count (entries);
257
	printk(KERN_DEBUG "%s index ", label);
A
Andrew Morton 已提交
258
	for (i = 0; i < n; i++) {
259
		printk("%x->%lu ", i ? dx_get_hash(entries + i) :
A
Aneesh Kumar K.V 已提交
260
				0, (unsigned long)dx_get_block(entries + i));
A
Andrew Morton 已提交
261 262
	}
	printk("\n");
263 264 265 266 267 268 269 270 271
}

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

272
static struct stats dx_show_leaf(struct dx_hash_info *hinfo, struct ext4_dir_entry_2 *de,
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
				 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++);
289
				ext4fs_dirhash(de->name, de->name_len, &h);
290 291 292
				printk(":%x.%u ", h.hash,
				       ((char *) de - base));
			}
293
			space += EXT4_DIR_REC_LEN(de->name_len);
294 295
			names++;
		}
296
		de = ext4_next_entry(de, size);
297 298 299 300 301 302 303 304 305
	}
	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;
306
	unsigned count = dx_get_count(entries), names = 0, space = 0, i;
307 308 309 310 311 312
	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 已提交
313 314
		ext4_lblk_t block = dx_get_block(entries);
		ext4_lblk_t hash  = i ? dx_get_hash(entries): 0;
315 316 317
		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);
318
		if (!(bh = ext4_bread (NULL,dir, block, 0,&err))) continue;
319 320
		stats = levels?
		   dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
321
		   dx_show_leaf(hinfo, (struct ext4_dir_entry_2 *) bh->b_data, blocksize, 0);
322 323 324
		names += stats.names;
		space += stats.space;
		bcount += stats.bcount;
325
		brelse(bh);
326 327
	}
	if (bcount)
328
		printk(KERN_DEBUG "%snames %u, fullness %u (%u%%)\n",
329 330
		       levels ? "" : "   ", names, space/bcount,
		       (space/bcount)*100/blocksize);
331 332 333 334 335 336 337 338 339 340 341 342 343 344
	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 *
345
dx_probe(const struct qstr *d_name, struct inode *dir,
346 347 348 349 350 351 352 353 354 355
	 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;
356
	if (!(bh = ext4_bread (NULL,dir, 0, 0, err)))
357 358 359 360 361
		goto fail;
	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) {
362
		ext4_warning(dir->i_sb, "Unrecognised inode hash code %d",
363 364 365 366 367 368
			     root->info.hash_version);
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}
	hinfo->hash_version = root->info.hash_version;
369 370
	if (hinfo->hash_version <= DX_HASH_TEA)
		hinfo->hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
371
	hinfo->seed = EXT4_SB(dir->i_sb)->s_hash_seed;
372 373
	if (d_name)
		ext4fs_dirhash(d_name->name, d_name->len, hinfo);
374 375 376
	hash = hinfo->hash;

	if (root->info.unused_flags & 1) {
377
		ext4_warning(dir->i_sb, "Unimplemented inode hash flags: %#06x",
378 379 380 381 382 383 384
			     root->info.unused_flags);
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}

	if ((indirect = root->info.indirect_levels) > 1) {
385
		ext4_warning(dir->i_sb, "Unimplemented inode hash depth: %#06x",
386 387 388 389 390 391 392 393
			     root->info.indirect_levels);
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}

	entries = (struct dx_entry *) (((char *)&root->info) +
				       root->info.info_length);
394 395 396

	if (dx_get_limit(entries) != dx_root_limit(dir,
						   root->info.info_length)) {
397
		ext4_warning(dir->i_sb, "dx entry: limit != root limit");
398 399 400 401 402
		brelse(bh);
		*err = ERR_BAD_DX_DIR;
		goto fail;
	}

403
	dxtrace(printk("Look up %x", hash));
404 405 406
	while (1)
	{
		count = dx_get_count(entries);
407
		if (!count || count > dx_get_limit(entries)) {
408
			ext4_warning(dir->i_sb,
409 410 411 412 413 414
				     "dx entry: no count or count > limit");
			brelse(bh);
			*err = ERR_BAD_DX_DIR;
			goto fail2;
		}

415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448
		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;
449
		if (!(bh = ext4_bread (NULL,dir, dx_get_block(at), 0, err)))
450 451
			goto fail2;
		at = entries = ((struct dx_node *) bh->b_data)->entries;
452
		if (dx_get_limit(entries) != dx_node_limit (dir)) {
453
			ext4_warning(dir->i_sb,
454 455 456 457 458
				     "dx entry: limit != node limit");
			brelse(bh);
			*err = ERR_BAD_DX_DIR;
			goto fail2;
		}
459
		frame++;
460
		frame->bh = NULL;
461 462 463 464 465 466 467
	}
fail2:
	while (frame >= frame_in) {
		brelse(frame->bh);
		frame--;
	}
fail:
468
	if (*err == ERR_BAD_DX_DIR)
469
		ext4_warning(dir->i_sb,
470 471
			     "Corrupt dir inode %ld, running e2fsck is "
			     "recommended.", dir->i_ino);
472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501
	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.
 */
502
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547
				 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--) {
548
		if (!(bh = ext4_bread(NULL, dir, dx_get_block(p->at),
549 550 551
				      0, &err)))
			return err; /* Failure */
		p++;
552
		brelse(p->bh);
553 554 555 556 557 558 559 560 561 562 563 564 565
		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 已提交
566
				  struct inode *dir, ext4_lblk_t block,
567 568 569 570
				  struct dx_hash_info *hinfo,
				  __u32 start_hash, __u32 start_minor_hash)
{
	struct buffer_head *bh;
571
	struct ext4_dir_entry_2 *de, *top;
572 573
	int err, count = 0;

A
Aneesh Kumar K.V 已提交
574 575
	dxtrace(printk(KERN_INFO "In htree dirblock_to_tree: block %lu\n",
							(unsigned long)block));
576
	if (!(bh = ext4_bread (NULL, dir, block, 0, &err)))
577 578
		return err;

579 580
	de = (struct ext4_dir_entry_2 *) bh->b_data;
	top = (struct ext4_dir_entry_2 *) ((char *) de +
581
					   dir->i_sb->s_blocksize -
582
					   EXT4_DIR_REC_LEN(0));
583
	for (; de < top; de = ext4_next_entry(de, dir->i_sb->s_blocksize)) {
584 585 586
		if (ext4_check_dir_entry(dir, de, bh,
				(block<<EXT4_BLOCK_SIZE_BITS(dir->i_sb))
					 + ((char *)de - bh->b_data))) {
587 588 589
			/* 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;
590
			brelse(bh);
591 592
			return count;
		}
593
		ext4fs_dirhash(de->name, de->name_len, hinfo);
594 595 596 597 598 599
		if ((hinfo->hash < start_hash) ||
		    ((hinfo->hash == start_hash) &&
		     (hinfo->minor_hash < start_minor_hash)))
			continue;
		if (de->inode == 0)
			continue;
600
		if ((err = ext4_htree_store_dirent(dir_file,
601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619
				   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.
 */
620
int ext4_htree_fill_tree(struct file *dir_file, __u32 start_hash,
621 622 623
			 __u32 start_minor_hash, __u32 *next_hash)
{
	struct dx_hash_info hinfo;
624
	struct ext4_dir_entry_2 *de;
625 626
	struct dx_frame frames[2], *frame;
	struct inode *dir;
A
Aneesh Kumar K.V 已提交
627
	ext4_lblk_t block;
628
	int count = 0;
A
Aneesh Kumar K.V 已提交
629
	int ret, err;
630 631
	__u32 hashval;

632
	dxtrace(printk(KERN_DEBUG "In htree_fill_tree, start hash: %x:%x\n",
633
		       start_hash, start_minor_hash));
634
	dir = dir_file->f_path.dentry->d_inode;
635
	if (!(ext4_test_inode_flag(dir, EXT4_INODE_INDEX))) {
636
		hinfo.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
637 638 639
		if (hinfo.hash_version <= DX_HASH_TEA)
			hinfo.hash_version +=
				EXT4_SB(dir->i_sb)->s_hash_unsigned;
640
		hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
641 642 643 644 645 646 647
		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;
648
	frame = dx_probe(NULL, dir, &hinfo, frames, &err);
649 650 651 652 653
	if (!frame)
		return err;

	/* Add '.' and '..' from the htree header */
	if (!start_hash && !start_minor_hash) {
654 655
		de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
		if ((err = ext4_htree_store_dirent(dir_file, 0, 0, de)) != 0)
656 657 658 659
			goto errout;
		count++;
	}
	if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
660
		de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
661
		de = ext4_next_entry(de, dir->i_sb->s_blocksize);
662
		if ((err = ext4_htree_store_dirent(dir_file, 2, 0, de)) != 0)
663 664 665 666 667 668 669 670 671 672 673 674 675 676
			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;
677
		ret = ext4_htree_next_block(dir, HASH_NB_ALWAYS,
678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693
					    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);
694 695
	dxtrace(printk(KERN_DEBUG "Fill tree: returned %d entries, "
		       "next hash: %x\n", count, *next_hash));
696 697 698 699 700 701 702 703 704 705 706
	return count;
errout:
	dx_release(frames);
	return (err);
}


/*
 * Directory block splitting, compacting
 */

707 708 709 710
/*
 * Create map of hash values, offsets, and sizes, stored at end of block.
 * Returns number of entries mapped.
 */
711 712 713
static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
		       struct dx_hash_info *hinfo,
		       struct dx_map_entry *map_tail)
714 715 716 717 718
{
	int count = 0;
	char *base = (char *) de;
	struct dx_hash_info h = *hinfo;

719
	while ((char *) de < base + blocksize) {
720
		if (de->name_len && de->inode) {
721
			ext4fs_dirhash(de->name, de->name_len, &h);
722 723
			map_tail--;
			map_tail->hash = h.hash;
724
			map_tail->offs = ((char *) de - base)>>2;
725
			map_tail->size = le16_to_cpu(de->rec_len);
726 727 728 729
			count++;
			cond_resched();
		}
		/* XXX: do we need to check rec_len == 0 case? -Chris */
730
		de = ext4_next_entry(de, blocksize);
731 732 733 734
	}
	return count;
}

735
/* Sort map by hash value */
736 737
static void dx_sort_map (struct dx_map_entry *map, unsigned count)
{
A
Andrew Morton 已提交
738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754
	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)
755
				continue;
A
Andrew Morton 已提交
756 757
			swap(*(q+1), *q);
			more = 1;
758 759 760 761
		}
	} while(more);
}

A
Aneesh Kumar K.V 已提交
762
static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
763 764 765 766 767 768 769 770 771 772 773 774 775
{
	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);
}

776
static void ext4_update_dx_flag(struct inode *inode)
777
{
778 779
	if (!EXT4_HAS_COMPAT_FEATURE(inode->i_sb,
				     EXT4_FEATURE_COMPAT_DIR_INDEX))
780
		ext4_clear_inode_flag(inode, EXT4_INODE_INDEX);
781 782 783
}

/*
784
 * NOTE! unlike strncmp, ext4_match returns 1 for success, 0 for failure.
785
 *
786
 * `len <= EXT4_NAME_LEN' is guaranteed by caller.
787 788
 * `de != NULL' is guaranteed by caller.
 */
789 790
static inline int ext4_match (int len, const char * const name,
			      struct ext4_dir_entry_2 * de)
791 792 793 794 795 796 797 798 799 800 801
{
	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
 */
802
static inline int search_dirblock(struct buffer_head *bh,
803
				  struct inode *dir,
804
				  const struct qstr *d_name,
805
				  unsigned int offset,
806
				  struct ext4_dir_entry_2 ** res_dir)
807
{
808
	struct ext4_dir_entry_2 * de;
809 810
	char * dlimit;
	int de_len;
811 812
	const char *name = d_name->name;
	int namelen = d_name->len;
813

814
	de = (struct ext4_dir_entry_2 *) bh->b_data;
815 816 817 818 819 820
	dlimit = bh->b_data + dir->i_sb->s_blocksize;
	while ((char *) de < dlimit) {
		/* this code is executed quadratically often */
		/* do minimal checking `by hand' */

		if ((char *) de + namelen <= dlimit &&
821
		    ext4_match (namelen, name, de)) {
822
			/* found a match - just to be sure, do a full check */
823
			if (ext4_check_dir_entry(dir, de, bh, offset))
824 825 826 827 828
				return -1;
			*res_dir = de;
			return 1;
		}
		/* prevent looping on a bad block */
829 830
		de_len = ext4_rec_len_from_disk(de->rec_len,
						dir->i_sb->s_blocksize);
831 832 833
		if (de_len <= 0)
			return -1;
		offset += de_len;
834
		de = (struct ext4_dir_entry_2 *) ((char *) de + de_len);
835 836 837 838 839 840
	}
	return 0;
}


/*
841
 *	ext4_find_entry()
842 843 844 845 846 847 848 849 850
 *
 * 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.
 */
851 852
static struct buffer_head * ext4_find_entry (struct inode *dir,
					const struct qstr *d_name,
853
					struct ext4_dir_entry_2 ** res_dir)
854
{
855 856 857
	struct super_block *sb;
	struct buffer_head *bh_use[NAMEI_RA_SIZE];
	struct buffer_head *bh, *ret = NULL;
A
Aneesh Kumar K.V 已提交
858
	ext4_lblk_t start, block, b;
859
	const u8 *name = d_name->name;
860 861 862 863 864
	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 已提交
865 866
	ext4_lblk_t  nblocks;
	int i, err;
867 868 869 870
	int namelen;

	*res_dir = NULL;
	sb = dir->i_sb;
871
	namelen = d_name->len;
872
	if (namelen > EXT4_NAME_LEN)
873
		return NULL;
874
	if ((namelen <= 2) && (name[0] == '.') &&
875
	    (name[1] == '.' || name[1] == '\0')) {
876 877 878 879 880 881 882 883
		/*
		 * "." 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;
	}
884
	if (is_dx(dir)) {
885
		bh = ext4_dx_find_entry(dir, d_name, res_dir, &err);
886 887 888 889 890 891 892
		/*
		 * 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;
893 894
		dxtrace(printk(KERN_DEBUG "ext4_find_entry: dx failed, "
			       "falling back\n"));
895
	}
896 897
	nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
	start = EXT4_I(dir)->i_dir_start_lookup;
898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920
	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++;
921
				bh = ext4_getblk(NULL, dir, b++, 0, &err);
922 923 924 925 926 927 928 929 930 931
				bh_use[ra_max] = bh;
				if (bh)
					ll_rw_block(READ_META, 1, &bh);
			}
		}
		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 */
932 933
			EXT4_ERROR_INODE(dir, "reading directory lblock %lu",
					 (unsigned long) block);
934 935 936
			brelse(bh);
			goto next;
		}
937
		i = search_dirblock(bh, dir, d_name,
938
			    block << EXT4_BLOCK_SIZE_BITS(sb), res_dir);
939
		if (i == 1) {
940
			EXT4_I(dir)->i_dir_start_lookup = block;
941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957
			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;
958
	nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
959 960 961 962 963 964 965 966
	if (block < nblocks) {
		start = 0;
		goto restart;
	}

cleanup_and_exit:
	/* Clean up the read-ahead blocks */
	for (; ra_ptr < ra_max; ra_ptr++)
967
		brelse(bh_use[ra_ptr]);
968 969 970
	return ret;
}

971
static struct buffer_head * ext4_dx_find_entry(struct inode *dir, const struct qstr *d_name,
972
		       struct ext4_dir_entry_2 **res_dir, int *err)
973
{
974
	struct super_block * sb = dir->i_sb;
975 976 977
	struct dx_hash_info	hinfo;
	struct dx_frame frames[2], *frame;
	struct buffer_head *bh;
A
Aneesh Kumar K.V 已提交
978
	ext4_lblk_t block;
979 980
	int retval;

981 982
	if (!(frame = dx_probe(d_name, dir, &hinfo, frames, err)))
		return NULL;
983 984
	do {
		block = dx_get_block(frame->at);
985
		if (!(bh = ext4_bread(NULL, dir, block, 0, err)))
986
			goto errout;
987

988 989 990 991 992 993
		retval = search_dirblock(bh, dir, d_name,
					 block << EXT4_BLOCK_SIZE_BITS(sb),
					 res_dir);
		if (retval == 1) { 	/* Success! */
			dx_release(frames);
			return bh;
994
		}
995
		brelse(bh);
996 997 998 999 1000
		if (retval == -1) {
			*err = ERR_BAD_DX_DIR;
			goto errout;
		}

1001
		/* Check to see if we should continue to search */
1002
		retval = ext4_htree_next_block(dir, hinfo.hash, frame,
1003 1004
					       frames, NULL);
		if (retval < 0) {
1005
			ext4_warning(sb,
1006 1007 1008 1009 1010 1011 1012 1013 1014
			     "error reading index page in directory #%lu",
			     dir->i_ino);
			*err = retval;
			goto errout;
		}
	} while (retval == 1);

	*err = -ENOENT;
errout:
1015
	dxtrace(printk(KERN_DEBUG "%s not found\n", name));
1016 1017 1018 1019
	dx_release (frames);
	return NULL;
}

1020
static struct dentry *ext4_lookup(struct inode *dir, struct dentry *dentry, struct nameidata *nd)
1021
{
1022 1023 1024
	struct inode *inode;
	struct ext4_dir_entry_2 *de;
	struct buffer_head *bh;
1025

1026
	if (dentry->d_name.len > EXT4_NAME_LEN)
1027 1028
		return ERR_PTR(-ENAMETOOLONG);

1029
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
1030 1031
	inode = NULL;
	if (bh) {
1032
		__u32 ino = le32_to_cpu(de->inode);
1033
		brelse(bh);
1034
		if (!ext4_valid_inum(dir->i_sb, ino)) {
1035
			EXT4_ERROR_INODE(dir, "bad inode number: %u", ino);
1036
			return ERR_PTR(-EIO);
1037
		}
1038
		inode = ext4_iget(dir->i_sb, ino);
T
Tobias Klauser 已提交
1039
		if (IS_ERR(inode)) {
1040
			if (PTR_ERR(inode) == -ESTALE) {
1041 1042 1043
				EXT4_ERROR_INODE(dir,
						 "deleted inode referenced: %u",
						 ino);
1044 1045 1046 1047 1048
				return ERR_PTR(-EIO);
			} else {
				return ERR_CAST(inode);
			}
		}
1049 1050 1051 1052 1053
	}
	return d_splice_alias(inode, dentry);
}


1054
struct dentry *ext4_get_parent(struct dentry *child)
1055
{
1056
	__u32 ino;
1057 1058 1059 1060
	static const struct qstr dotdot = {
		.name = "..",
		.len = 2,
	};
1061
	struct ext4_dir_entry_2 * de;
1062 1063
	struct buffer_head *bh;

1064
	bh = ext4_find_entry(child->d_inode, &dotdot, &de);
1065 1066 1067 1068 1069
	if (!bh)
		return ERR_PTR(-ENOENT);
	ino = le32_to_cpu(de->inode);
	brelse(bh);

1070
	if (!ext4_valid_inum(child->d_inode->i_sb, ino)) {
1071 1072
		EXT4_ERROR_INODE(child->d_inode,
				 "bad parent inode number: %u", ino);
1073
		return ERR_PTR(-EIO);
1074 1075
	}

1076
	return d_obtain_alias(ext4_iget(child->d_inode->i_sb, ino));
1077 1078 1079
}

#define S_SHIFT 12
1080 1081 1082 1083 1084 1085 1086 1087
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,
1088 1089
};

1090 1091
static inline void ext4_set_de_type(struct super_block *sb,
				struct ext4_dir_entry_2 *de,
1092
				umode_t mode) {
1093 1094
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FILETYPE))
		de->file_type = ext4_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
1095 1096
}

1097 1098 1099 1100
/*
 * Move count entries from end of map between two memory locations.
 * Returns pointer to last entry moved.
 */
1101
static struct ext4_dir_entry_2 *
1102 1103
dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count,
		unsigned blocksize)
1104 1105 1106 1107
{
	unsigned rec_len = 0;

	while (count--) {
1108
		struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)
1109
						(from + (map->offs<<2));
1110
		rec_len = EXT4_DIR_REC_LEN(de->name_len);
1111
		memcpy (to, de, rec_len);
1112
		((struct ext4_dir_entry_2 *) to)->rec_len =
1113
				ext4_rec_len_to_disk(rec_len, blocksize);
1114 1115 1116 1117
		de->inode = 0;
		map++;
		to += rec_len;
	}
1118
	return (struct ext4_dir_entry_2 *) (to - rec_len);
1119 1120
}

1121 1122 1123 1124
/*
 * Compact each dir entry in the range to the minimal rec_len.
 * Returns pointer to last entry in range.
 */
1125
static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize)
1126
{
1127
	struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base;
1128 1129 1130
	unsigned rec_len = 0;

	prev = to = de;
1131
	while ((char*)de < base + blocksize) {
1132
		next = ext4_next_entry(de, blocksize);
1133
		if (de->inode && de->name_len) {
1134
			rec_len = EXT4_DIR_REC_LEN(de->name_len);
1135 1136
			if (de > to)
				memmove(to, de, rec_len);
1137
			to->rec_len = ext4_rec_len_to_disk(rec_len, blocksize);
1138
			prev = to;
1139
			to = (struct ext4_dir_entry_2 *) (((char *) to) + rec_len);
1140 1141 1142 1143 1144 1145
		}
		de = next;
	}
	return prev;
}

1146 1147 1148 1149 1150
/*
 * 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.
 */
1151
static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
1152 1153 1154 1155 1156 1157
			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 已提交
1158
	ext4_lblk_t newblock;
1159 1160 1161
	u32 hash2;
	struct dx_map_entry *map;
	char *data1 = (*bh)->b_data, *data2;
1162
	unsigned split, move, size;
1163
	struct ext4_dir_entry_2 *de = NULL, *de2;
1164
	int	err = 0, i;
1165

1166
	bh2 = ext4_append (handle, dir, &newblock, &err);
1167 1168 1169 1170 1171 1172 1173
	if (!(bh2)) {
		brelse(*bh);
		*bh = NULL;
		goto errout;
	}

	BUFFER_TRACE(*bh, "get_write_access");
1174
	err = ext4_journal_get_write_access(handle, *bh);
1175 1176 1177
	if (err)
		goto journal_error;

1178
	BUFFER_TRACE(frame->bh, "get_write_access");
1179
	err = ext4_journal_get_write_access(handle, frame->bh);
1180 1181 1182 1183 1184 1185 1186
	if (err)
		goto journal_error;

	data2 = bh2->b_data;

	/* create map in the end of data2 block */
	map = (struct dx_map_entry *) (data2 + blocksize);
1187
	count = dx_make_map((struct ext4_dir_entry_2 *) data1,
1188 1189
			     blocksize, hinfo, map);
	map -= count;
1190
	dx_sort_map(map, count);
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202
	/* 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;
1203 1204
	hash2 = map[split].hash;
	continued = hash2 == map[split - 1].hash;
A
Aneesh Kumar K.V 已提交
1205 1206 1207
	dxtrace(printk(KERN_INFO "Split block %lu at %x, %i/%i\n",
			(unsigned long)dx_get_block(frame->at),
					hash2, split, count-split));
1208 1209

	/* Fancy dance to stay within two buffers */
1210
	de2 = dx_move_dirents(data1, data2, map + split, count - split, blocksize);
1211
	de = dx_pack_dirents(data1, blocksize);
1212 1213 1214 1215
	de->rec_len = ext4_rec_len_to_disk(data1 + blocksize - (char *) de,
					   blocksize);
	de2->rec_len = ext4_rec_len_to_disk(data2 + blocksize - (char *) de2,
					    blocksize);
1216 1217
	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));
1218 1219 1220 1221 1222 1223 1224

	/* Which block gets the new entry? */
	if (hinfo->hash >= hash2)
	{
		swap(*bh, bh2);
		de = de2;
	}
1225
	dx_insert_block(frame, hash2 + continued, newblock);
1226
	err = ext4_handle_dirty_metadata(handle, dir, bh2);
1227 1228
	if (err)
		goto journal_error;
1229
	err = ext4_handle_dirty_metadata(handle, dir, frame->bh);
1230 1231
	if (err)
		goto journal_error;
1232 1233
	brelse(bh2);
	dxtrace(dx_show_index("frame", frame->entries));
1234
	return de;
1235 1236 1237 1238 1239 1240 1241 1242 1243

journal_error:
	brelse(*bh);
	brelse(bh2);
	*bh = NULL;
	ext4_std_error(dir->i_sb, err);
errout:
	*error = err;
	return NULL;
1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254
}

/*
 * 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,
1255
			     struct inode *inode, struct ext4_dir_entry_2 *de,
1256
			     struct buffer_head *bh)
1257 1258 1259 1260
{
	struct inode	*dir = dentry->d_parent->d_inode;
	const char	*name = dentry->d_name.name;
	int		namelen = dentry->d_name.len;
1261
	unsigned int	offset = 0;
1262
	unsigned int	blocksize = dir->i_sb->s_blocksize;
1263 1264 1265 1266
	unsigned short	reclen;
	int		nlen, rlen, err;
	char		*top;

1267
	reclen = EXT4_DIR_REC_LEN(namelen);
1268
	if (!de) {
1269
		de = (struct ext4_dir_entry_2 *)bh->b_data;
1270
		top = bh->b_data + blocksize - reclen;
1271
		while ((char *) de <= top) {
1272
			if (ext4_check_dir_entry(dir, de, bh, offset))
1273
				return -EIO;
1274
			if (ext4_match(namelen, name, de))
1275
				return -EEXIST;
1276
			nlen = EXT4_DIR_REC_LEN(de->name_len);
1277
			rlen = ext4_rec_len_from_disk(de->rec_len, blocksize);
1278 1279
			if ((de->inode? rlen - nlen: rlen) >= reclen)
				break;
1280
			de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
1281 1282 1283 1284 1285 1286
			offset += rlen;
		}
		if ((char *) de > top)
			return -ENOSPC;
	}
	BUFFER_TRACE(bh, "get_write_access");
1287
	err = ext4_journal_get_write_access(handle, bh);
1288
	if (err) {
1289
		ext4_std_error(dir->i_sb, err);
1290 1291 1292 1293
		return err;
	}

	/* By now the buffer is marked for journaling */
1294
	nlen = EXT4_DIR_REC_LEN(de->name_len);
1295
	rlen = ext4_rec_len_from_disk(de->rec_len, blocksize);
1296
	if (de->inode) {
1297
		struct ext4_dir_entry_2 *de1 = (struct ext4_dir_entry_2 *)((char *)de + nlen);
1298 1299
		de1->rec_len = ext4_rec_len_to_disk(rlen - nlen, blocksize);
		de->rec_len = ext4_rec_len_to_disk(nlen, blocksize);
1300 1301
		de = de1;
	}
1302
	de->file_type = EXT4_FT_UNKNOWN;
1303 1304
	if (inode) {
		de->inode = cpu_to_le32(inode->i_ino);
1305
		ext4_set_de_type(dir->i_sb, de, inode->i_mode);
1306 1307 1308
	} else
		de->inode = 0;
	de->name_len = namelen;
1309
	memcpy(de->name, name, namelen);
1310 1311 1312 1313 1314 1315
	/*
	 * 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
1316
	 * ext4_new_inode() setting the times, but error
1317 1318 1319 1320
	 * 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 已提交
1321
	dir->i_mtime = dir->i_ctime = ext4_current_time(dir);
1322
	ext4_update_dx_flag(dir);
1323
	dir->i_version++;
1324
	ext4_mark_inode_dirty(handle, dir);
1325 1326
	BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
	err = ext4_handle_dirty_metadata(handle, dir, bh);
1327
	if (err)
1328
		ext4_std_error(dir->i_sb, err);
1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345
	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;
1346
	struct ext4_dir_entry_2	*de, *de2;
1347 1348 1349 1350 1351
	char		*data1, *top;
	unsigned	len;
	int		retval;
	unsigned	blocksize;
	struct dx_hash_info hinfo;
A
Aneesh Kumar K.V 已提交
1352
	ext4_lblk_t  block;
1353 1354 1355
	struct fake_dirent *fde;

	blocksize =  dir->i_sb->s_blocksize;
1356
	dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino));
1357
	retval = ext4_journal_get_write_access(handle, bh);
1358
	if (retval) {
1359
		ext4_std_error(dir->i_sb, retval);
1360 1361 1362 1363 1364
		brelse(bh);
		return retval;
	}
	root = (struct dx_root *) bh->b_data;

1365 1366 1367
	/* The 0th block becomes the root, move the dirents out */
	fde = &root->dotdot;
	de = (struct ext4_dir_entry_2 *)((char *)fde +
1368
		ext4_rec_len_from_disk(fde->rec_len, blocksize));
1369
	if ((char *) de >= (((char *) root) + blocksize)) {
1370
		EXT4_ERROR_INODE(dir, "invalid rec_len for '..'");
1371 1372 1373 1374 1375 1376
		brelse(bh);
		return -EIO;
	}
	len = ((char *) root) + blocksize - (char *) de;

	/* Allocate new block for the 0th block's dirents */
1377
	bh2 = ext4_append(handle, dir, &block, &retval);
1378 1379 1380 1381
	if (!(bh2)) {
		brelse(bh);
		return retval;
	}
1382
	ext4_set_inode_flag(dir, EXT4_INODE_INDEX);
1383 1384 1385
	data1 = bh2->b_data;

	memcpy (data1, de, len);
1386
	de = (struct ext4_dir_entry_2 *) data1;
1387
	top = data1 + len;
1388
	while ((char *)(de2 = ext4_next_entry(de, blocksize)) < top)
1389
		de = de2;
1390 1391
	de->rec_len = ext4_rec_len_to_disk(data1 + blocksize - (char *) de,
					   blocksize);
1392
	/* Initialize the root; the dot dirents already exist */
1393
	de = (struct ext4_dir_entry_2 *) (&root->dotdot);
1394 1395
	de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(2),
					   blocksize);
1396 1397
	memset (&root->info, 0, sizeof(root->info));
	root->info.info_length = sizeof(root->info);
1398
	root->info.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
1399
	entries = root->entries;
1400 1401 1402
	dx_set_block(entries, 1);
	dx_set_count(entries, 1);
	dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
1403 1404 1405

	/* Initialize as for dx_probe */
	hinfo.hash_version = root->info.hash_version;
1406 1407
	if (hinfo.hash_version <= DX_HASH_TEA)
		hinfo.hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
1408 1409
	hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
	ext4fs_dirhash(name, namelen, &hinfo);
1410 1411 1412 1413 1414 1415 1416 1417 1418 1419
	frame = frames;
	frame->entries = entries;
	frame->at = entries;
	frame->bh = bh;
	bh = bh2;
	de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
	dx_release (frames);
	if (!(de))
		return retval;

1420 1421 1422
	retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
	brelse(bh);
	return retval;
1423 1424 1425
}

/*
1426
 *	ext4_add_entry()
1427 1428
 *
 * adds a file entry to the specified directory, using the same
1429
 * semantics as ext4_find_entry(). It returns NULL if it failed.
1430 1431 1432 1433 1434
 *
 * 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.
 */
1435 1436
static int ext4_add_entry(handle_t *handle, struct dentry *dentry,
			  struct inode *inode)
1437 1438
{
	struct inode *dir = dentry->d_parent->d_inode;
1439
	struct buffer_head *bh;
1440
	struct ext4_dir_entry_2 *de;
1441
	struct super_block *sb;
1442 1443 1444
	int	retval;
	int	dx_fallback=0;
	unsigned blocksize;
A
Aneesh Kumar K.V 已提交
1445
	ext4_lblk_t block, blocks;
1446 1447 1448 1449 1450 1451

	sb = dir->i_sb;
	blocksize = sb->s_blocksize;
	if (!dentry->d_name.len)
		return -EINVAL;
	if (is_dx(dir)) {
1452
		retval = ext4_dx_add_entry(handle, dentry, inode);
1453 1454
		if (!retval || (retval != ERR_BAD_DX_DIR))
			return retval;
1455
		ext4_clear_inode_flag(dir, EXT4_INODE_INDEX);
1456
		dx_fallback++;
1457
		ext4_mark_inode_dirty(handle, dir);
1458 1459
	}
	blocks = dir->i_size >> sb->s_blocksize_bits;
1460
	for (block = 0; block < blocks; block++) {
1461
		bh = ext4_bread(handle, dir, block, 0, &retval);
1462 1463 1464
		if(!bh)
			return retval;
		retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1465 1466
		if (retval != -ENOSPC) {
			brelse(bh);
1467
			return retval;
1468
		}
1469 1470

		if (blocks == 1 && !dx_fallback &&
1471 1472
		    EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX))
			return make_indexed_dir(handle, dentry, inode, bh);
1473 1474
		brelse(bh);
	}
1475
	bh = ext4_append(handle, dir, &block, &retval);
1476 1477
	if (!bh)
		return retval;
1478
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1479
	de->inode = 0;
1480
	de->rec_len = ext4_rec_len_to_disk(blocksize, blocksize);
1481 1482
	retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
	brelse(bh);
1483 1484
	if (retval == 0)
		ext4_set_inode_state(inode, EXT4_STATE_NEWENTRY);
1485
	return retval;
1486 1487 1488 1489 1490
}

/*
 * Returns 0 for success, or a negative error value
 */
1491
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
1492 1493 1494 1495 1496
			     struct inode *inode)
{
	struct dx_frame frames[2], *frame;
	struct dx_entry *entries, *at;
	struct dx_hash_info hinfo;
1497
	struct buffer_head *bh;
1498
	struct inode *dir = dentry->d_parent->d_inode;
1499
	struct super_block *sb = dir->i_sb;
1500
	struct ext4_dir_entry_2 *de;
1501 1502
	int err;

1503
	frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
1504 1505 1506 1507 1508
	if (!frame)
		return err;
	entries = frame->entries;
	at = frame->at;

1509
	if (!(bh = ext4_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
1510 1511 1512
		goto cleanup;

	BUFFER_TRACE(bh, "get_write_access");
1513
	err = ext4_journal_get_write_access(handle, bh);
1514 1515 1516 1517
	if (err)
		goto journal_error;

	err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1518
	if (err != -ENOSPC)
1519 1520 1521
		goto cleanup;

	/* Block full, should compress but for now just split */
1522
	dxtrace(printk(KERN_DEBUG "using %u of %u node entries\n",
1523 1524 1525
		       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 已提交
1526
		ext4_lblk_t newblock;
1527 1528 1529 1530 1531 1532 1533 1534
		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))) {
1535
			ext4_warning(sb, "Directory index full!");
1536 1537 1538
			err = -ENOSPC;
			goto cleanup;
		}
1539
		bh2 = ext4_append (handle, dir, &newblock, &err);
1540 1541 1542 1543
		if (!(bh2))
			goto cleanup;
		node2 = (struct dx_node *)(bh2->b_data);
		entries2 = node2->entries;
1544
		memset(&node2->fake, 0, sizeof(struct fake_dirent));
1545 1546
		node2->fake.rec_len = ext4_rec_len_to_disk(sb->s_blocksize,
							   sb->s_blocksize);
1547
		BUFFER_TRACE(frame->bh, "get_write_access");
1548
		err = ext4_journal_get_write_access(handle, frame->bh);
1549 1550 1551 1552 1553
		if (err)
			goto journal_error;
		if (levels) {
			unsigned icount1 = icount/2, icount2 = icount - icount1;
			unsigned hash2 = dx_get_hash(entries + icount1);
1554 1555
			dxtrace(printk(KERN_DEBUG "Split index %i/%i\n",
				       icount1, icount2));
1556 1557

			BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
1558
			err = ext4_journal_get_write_access(handle,
1559 1560 1561 1562
							     frames[0].bh);
			if (err)
				goto journal_error;

1563 1564 1565 1566 1567
			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));
1568 1569 1570 1571 1572 1573 1574

			/* 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);
			}
1575 1576 1577
			dx_insert_block(frames + 0, hash2, newblock);
			dxtrace(dx_show_index("node", frames[1].entries));
			dxtrace(dx_show_index("node",
1578
			       ((struct dx_node *) bh2->b_data)->entries));
1579
			err = ext4_handle_dirty_metadata(handle, inode, bh2);
1580 1581 1582 1583
			if (err)
				goto journal_error;
			brelse (bh2);
		} else {
1584 1585
			dxtrace(printk(KERN_DEBUG
				       "Creating second level index...\n"));
1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599
			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;
1600
			err = ext4_journal_get_write_access(handle,
1601 1602 1603 1604
							     frame->bh);
			if (err)
				goto journal_error;
		}
1605
		ext4_handle_dirty_metadata(handle, inode, frames[0].bh);
1606 1607 1608 1609 1610 1611 1612 1613
	}
	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:
1614
	ext4_std_error(dir->i_sb, err);
1615 1616 1617 1618 1619 1620 1621 1622
cleanup:
	if (bh)
		brelse(bh);
	dx_release(frames);
	return err;
}

/*
1623
 * ext4_delete_entry deletes a directory entry by merging it with the
1624 1625
 * previous entry
 */
1626 1627 1628 1629
static int ext4_delete_entry(handle_t *handle,
			     struct inode *dir,
			     struct ext4_dir_entry_2 *de_del,
			     struct buffer_head *bh)
1630
{
1631
	struct ext4_dir_entry_2 *de, *pde;
1632
	unsigned int blocksize = dir->i_sb->s_blocksize;
1633 1634 1635 1636
	int i;

	i = 0;
	pde = NULL;
1637
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1638
	while (i < bh->b_size) {
1639
		if (ext4_check_dir_entry(dir, de, bh, i))
1640 1641 1642
			return -EIO;
		if (de == de_del)  {
			BUFFER_TRACE(bh, "get_write_access");
1643
			ext4_journal_get_write_access(handle, bh);
1644
			if (pde)
1645
				pde->rec_len = ext4_rec_len_to_disk(
1646 1647 1648 1649 1650
					ext4_rec_len_from_disk(pde->rec_len,
							       blocksize) +
					ext4_rec_len_from_disk(de->rec_len,
							       blocksize),
					blocksize);
1651 1652 1653
			else
				de->inode = 0;
			dir->i_version++;
1654 1655
			BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
			ext4_handle_dirty_metadata(handle, dir, bh);
1656 1657
			return 0;
		}
1658
		i += ext4_rec_len_from_disk(de->rec_len, blocksize);
1659
		pde = de;
1660
		de = ext4_next_entry(de, blocksize);
1661 1662 1663 1664
	}
	return -ENOENT;
}

1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693
/*
 * 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) {
			inode->i_nlink = 1;
			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)
{
	drop_nlink(inode);
	if (S_ISDIR(inode->i_mode) && inode->i_nlink == 0)
		inc_nlink(inode);
}


1694
static int ext4_add_nondir(handle_t *handle,
1695 1696
		struct dentry *dentry, struct inode *inode)
{
1697
	int err = ext4_add_entry(handle, dentry, inode);
1698
	if (!err) {
1699
		ext4_mark_inode_dirty(handle, inode);
1700
		d_instantiate(dentry, inode);
A
Al Viro 已提交
1701
		unlock_new_inode(inode);
1702 1703
		return 0;
	}
1704
	drop_nlink(inode);
A
Al Viro 已提交
1705
	unlock_new_inode(inode);
1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717
	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().
 */
1718 1719
static int ext4_create(struct inode *dir, struct dentry *dentry, int mode,
		       struct nameidata *nd)
1720 1721
{
	handle_t *handle;
1722
	struct inode *inode;
1723 1724
	int err, retries = 0;

1725
	dquot_initialize(dir);
1726

1727
retry:
1728 1729
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
1730
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
1731 1732 1733 1734
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
1735
		ext4_handle_sync(handle);
1736

1737
	inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0);
1738 1739
	err = PTR_ERR(inode);
	if (!IS_ERR(inode)) {
1740 1741 1742 1743
		inode->i_op = &ext4_file_inode_operations;
		inode->i_fop = &ext4_file_operations;
		ext4_set_aops(inode);
		err = ext4_add_nondir(handle, dentry, inode);
1744
	}
1745 1746
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
1747 1748 1749 1750
		goto retry;
	return err;
}

1751 1752
static int ext4_mknod(struct inode *dir, struct dentry *dentry,
		      int mode, dev_t rdev)
1753 1754 1755 1756 1757 1758 1759 1760
{
	handle_t *handle;
	struct inode *inode;
	int err, retries = 0;

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

1761
	dquot_initialize(dir);
1762

1763
retry:
1764 1765
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
1766
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
1767 1768 1769 1770
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
1771
		ext4_handle_sync(handle);
1772

1773
	inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0);
1774 1775 1776
	err = PTR_ERR(inode);
	if (!IS_ERR(inode)) {
		init_special_inode(inode, inode->i_mode, rdev);
T
Theodore Ts'o 已提交
1777
#ifdef CONFIG_EXT4_FS_XATTR
1778
		inode->i_op = &ext4_special_inode_operations;
1779
#endif
1780
		err = ext4_add_nondir(handle, dentry, inode);
1781
	}
1782 1783
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
1784 1785 1786 1787
		goto retry;
	return err;
}

1788
static int ext4_mkdir(struct inode *dir, struct dentry *dentry, int mode)
1789 1790
{
	handle_t *handle;
1791 1792 1793
	struct inode *inode;
	struct buffer_head *dir_block;
	struct ext4_dir_entry_2 *de;
1794
	unsigned int blocksize = dir->i_sb->s_blocksize;
1795 1796
	int err, retries = 0;

1797
	if (EXT4_DIR_LINK_MAX(dir))
1798 1799
		return -EMLINK;

1800
	dquot_initialize(dir);
1801

1802
retry:
1803 1804
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
1805
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
1806 1807 1808 1809
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
1810
		ext4_handle_sync(handle);
1811

1812 1813
	inode = ext4_new_inode(handle, dir, S_IFDIR | mode,
			       &dentry->d_name, 0);
1814 1815 1816 1817
	err = PTR_ERR(inode);
	if (IS_ERR(inode))
		goto out_stop;

1818 1819 1820
	inode->i_op = &ext4_dir_inode_operations;
	inode->i_fop = &ext4_dir_operations;
	inode->i_size = EXT4_I(inode)->i_disksize = inode->i_sb->s_blocksize;
1821
	dir_block = ext4_bread(handle, inode, 0, 1, &err);
1822 1823
	if (!dir_block)
		goto out_clear_inode;
1824
	BUFFER_TRACE(dir_block, "get_write_access");
1825 1826
	ext4_journal_get_write_access(handle, dir_block);
	de = (struct ext4_dir_entry_2 *) dir_block->b_data;
1827 1828
	de->inode = cpu_to_le32(inode->i_ino);
	de->name_len = 1;
1829 1830
	de->rec_len = ext4_rec_len_to_disk(EXT4_DIR_REC_LEN(de->name_len),
					   blocksize);
1831
	strcpy(de->name, ".");
1832
	ext4_set_de_type(dir->i_sb, de, S_IFDIR);
1833
	de = ext4_next_entry(de, blocksize);
1834
	de->inode = cpu_to_le32(dir->i_ino);
1835 1836
	de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(1),
					   blocksize);
1837
	de->name_len = 2;
1838
	strcpy(de->name, "..");
1839
	ext4_set_de_type(dir->i_sb, de, S_IFDIR);
1840
	inode->i_nlink = 2;
1841 1842
	BUFFER_TRACE(dir_block, "call ext4_handle_dirty_metadata");
	ext4_handle_dirty_metadata(handle, dir, dir_block);
1843
	brelse(dir_block);
1844
	ext4_mark_inode_dirty(handle, inode);
1845
	err = ext4_add_entry(handle, dentry, inode);
1846
	if (err) {
1847 1848
out_clear_inode:
		clear_nlink(inode);
A
Al Viro 已提交
1849
		unlock_new_inode(inode);
1850
		ext4_mark_inode_dirty(handle, inode);
1851
		iput(inode);
1852 1853
		goto out_stop;
	}
1854
	ext4_inc_count(handle, dir);
1855 1856
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
1857
	d_instantiate(dentry, inode);
A
Al Viro 已提交
1858
	unlock_new_inode(inode);
1859
out_stop:
1860 1861
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
1862 1863 1864 1865 1866 1867 1868
		goto retry;
	return err;
}

/*
 * routine to check that the specified directory is empty (for rmdir)
 */
1869
static int empty_dir(struct inode *inode)
1870
{
1871
	unsigned int offset;
1872 1873 1874
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de, *de1;
	struct super_block *sb;
1875 1876 1877
	int err = 0;

	sb = inode->i_sb;
1878
	if (inode->i_size < EXT4_DIR_REC_LEN(1) + EXT4_DIR_REC_LEN(2) ||
1879
	    !(bh = ext4_bread(NULL, inode, 0, 0, &err))) {
1880
		if (err)
1881 1882
			EXT4_ERROR_INODE(inode,
				"error %d reading directory lblock 0", err);
1883
		else
1884
			ext4_warning(inode->i_sb,
1885 1886 1887 1888
				     "bad directory (dir #%lu) - no data block",
				     inode->i_ino);
		return 1;
	}
1889
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1890
	de1 = ext4_next_entry(de, sb->s_blocksize);
1891 1892
	if (le32_to_cpu(de->inode) != inode->i_ino ||
			!le32_to_cpu(de1->inode) ||
1893 1894
			strcmp(".", de->name) ||
			strcmp("..", de1->name)) {
1895
		ext4_warning(inode->i_sb,
1896 1897 1898
			     "bad directory (dir #%lu) - no `.' or `..'",
			     inode->i_ino);
		brelse(bh);
1899 1900
		return 1;
	}
1901 1902 1903
	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);
1904
	while (offset < inode->i_size) {
1905
		if (!bh ||
1906 1907
		    (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
			unsigned int lblock;
1908
			err = 0;
1909
			brelse(bh);
1910 1911
			lblock = offset >> EXT4_BLOCK_SIZE_BITS(sb);
			bh = ext4_bread(NULL, inode, lblock, 0, &err);
1912 1913
			if (!bh) {
				if (err)
1914 1915 1916
					EXT4_ERROR_INODE(inode,
						"error %d reading directory "
						"lblock %u", err, lblock);
1917 1918 1919
				offset += sb->s_blocksize;
				continue;
			}
1920
			de = (struct ext4_dir_entry_2 *) bh->b_data;
1921
		}
1922
		if (ext4_check_dir_entry(inode, de, bh, offset)) {
1923
			de = (struct ext4_dir_entry_2 *)(bh->b_data +
1924 1925 1926 1927 1928
							 sb->s_blocksize);
			offset = (offset | (sb->s_blocksize - 1)) + 1;
			continue;
		}
		if (le32_to_cpu(de->inode)) {
1929
			brelse(bh);
1930 1931
			return 0;
		}
1932 1933
		offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
		de = ext4_next_entry(de, sb->s_blocksize);
1934
	}
1935
	brelse(bh);
1936 1937 1938
	return 1;
}

1939
/* ext4_orphan_add() links an unlinked or truncated inode into a list of
1940 1941 1942 1943 1944
 * 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
1945
 * inodes and truncating linked inodes in ext4_orphan_cleanup().
1946
 */
1947
int ext4_orphan_add(handle_t *handle, struct inode *inode)
1948 1949
{
	struct super_block *sb = inode->i_sb;
1950
	struct ext4_iloc iloc;
1951 1952
	int err = 0, rc;

1953 1954 1955
	if (!ext4_handle_valid(handle))
		return 0;

1956
	mutex_lock(&EXT4_SB(sb)->s_orphan_lock);
1957
	if (!list_empty(&EXT4_I(inode)->i_orphan))
1958 1959 1960 1961 1962 1963
		goto out_unlock;

	/* Orphan handling is only valid for files with data blocks
	 * being truncated, or files being unlinked. */

	/* @@@ FIXME: Observation from aviro:
1964
	 * I think I can trigger J_ASSERT in ext4_orphan_add().  We block
1965
	 * here (on s_orphan_lock), so race with ext4_link() which might bump
1966 1967
	 * ->i_nlink. For, say it, character device. Not a regular file,
	 * not a directory, not a symlink and ->i_nlink > 0.
1968 1969 1970 1971
	 *
	 * tytso, 4/25/2009: I'm not sure how that could happen;
	 * shouldn't the fs core protect us from these sort of
	 * unlink()/link() races?
1972
	 */
1973 1974
	J_ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
		  S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
1975

1976 1977
	BUFFER_TRACE(EXT4_SB(sb)->s_sbh, "get_write_access");
	err = ext4_journal_get_write_access(handle, EXT4_SB(sb)->s_sbh);
1978 1979 1980
	if (err)
		goto out_unlock;

1981
	err = ext4_reserve_inode_write(handle, inode, &iloc);
1982 1983
	if (err)
		goto out_unlock;
1984 1985 1986 1987 1988 1989 1990
	/*
	 * 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;
1991 1992

	/* Insert this inode at the head of the on-disk orphan list... */
1993 1994
	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);
1995
	err = ext4_handle_dirty_metadata(handle, NULL, EXT4_SB(sb)->s_sbh);
1996
	rc = ext4_mark_iloc_dirty(handle, inode, &iloc);
1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007
	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. */
2008
mem_insert:
2009
	if (!err)
2010
		list_add(&EXT4_I(inode)->i_orphan, &EXT4_SB(sb)->s_orphan);
2011 2012 2013 2014 2015

	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:
2016
	mutex_unlock(&EXT4_SB(sb)->s_orphan_lock);
2017
	ext4_std_error(inode->i_sb, err);
2018 2019 2020 2021
	return err;
}

/*
2022
 * ext4_orphan_del() removes an unlinked or truncated inode from the list
2023 2024
 * of such inodes stored on disk, because it is finally being cleaned up.
 */
2025
int ext4_orphan_del(handle_t *handle, struct inode *inode)
2026 2027
{
	struct list_head *prev;
2028 2029
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi;
2030
	__u32 ino_next;
2031
	struct ext4_iloc iloc;
2032 2033
	int err = 0;

2034 2035
	/* ext4_handle_valid() assumes a valid handle_t pointer */
	if (handle && !ext4_handle_valid(handle))
2036 2037
		return 0;

2038 2039 2040
	mutex_lock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
	if (list_empty(&ei->i_orphan))
		goto out;
2041 2042 2043

	ino_next = NEXT_ORPHAN(inode);
	prev = ei->i_orphan.prev;
2044
	sbi = EXT4_SB(inode->i_sb);
2045 2046 2047 2048 2049 2050 2051 2052 2053

	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. */
2054
	if (sbi->s_journal && !handle)
2055 2056
		goto out;

2057
	err = ext4_reserve_inode_write(handle, inode, &iloc);
2058 2059 2060 2061
	if (err)
		goto out_err;

	if (prev == &sbi->s_orphan) {
2062
		jbd_debug(4, "superblock will point to %u\n", ino_next);
2063
		BUFFER_TRACE(sbi->s_sbh, "get_write_access");
2064
		err = ext4_journal_get_write_access(handle, sbi->s_sbh);
2065 2066 2067
		if (err)
			goto out_brelse;
		sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
2068
		err = ext4_handle_dirty_metadata(handle, NULL, sbi->s_sbh);
2069
	} else {
2070
		struct ext4_iloc iloc2;
2071
		struct inode *i_prev =
2072
			&list_entry(prev, struct ext4_inode_info, i_orphan)->vfs_inode;
2073

2074
		jbd_debug(4, "orphan inode %lu will point to %u\n",
2075
			  i_prev->i_ino, ino_next);
2076
		err = ext4_reserve_inode_write(handle, i_prev, &iloc2);
2077 2078 2079
		if (err)
			goto out_brelse;
		NEXT_ORPHAN(i_prev) = ino_next;
2080
		err = ext4_mark_iloc_dirty(handle, i_prev, &iloc2);
2081 2082 2083 2084
	}
	if (err)
		goto out_brelse;
	NEXT_ORPHAN(inode) = 0;
2085
	err = ext4_mark_iloc_dirty(handle, inode, &iloc);
2086 2087

out_err:
2088
	ext4_std_error(inode->i_sb, err);
2089
out:
2090
	mutex_unlock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
2091 2092 2093 2094 2095 2096 2097
	return err;

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

2098
static int ext4_rmdir(struct inode *dir, struct dentry *dentry)
2099 2100
{
	int retval;
2101 2102 2103
	struct inode *inode;
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de;
2104 2105 2106 2107
	handle_t *handle;

	/* Initialize quotas before so that eventual writes go in
	 * separate transaction */
2108 2109
	dquot_initialize(dir);
	dquot_initialize(dentry->d_inode);
2110

2111
	handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
2112 2113 2114 2115
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	retval = -ENOENT;
2116
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
2117 2118 2119 2120
	if (!bh)
		goto end_rmdir;

	if (IS_DIRSYNC(dir))
2121
		ext4_handle_sync(handle);
2122 2123 2124 2125 2126 2127 2128 2129

	inode = dentry->d_inode;

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

	retval = -ENOTEMPTY;
2130
	if (!empty_dir(inode))
2131 2132
		goto end_rmdir;

2133
	retval = ext4_delete_entry(handle, dir, de, bh);
2134 2135
	if (retval)
		goto end_rmdir;
2136
	if (!EXT4_DIR_LINK_EMPTY(inode))
2137
		ext4_warning(inode->i_sb,
2138 2139
			     "empty directory has too many links (%d)",
			     inode->i_nlink);
2140 2141 2142 2143 2144 2145
	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;
2146
	ext4_orphan_add(handle, inode);
K
Kalpak Shah 已提交
2147
	inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
2148
	ext4_mark_inode_dirty(handle, inode);
2149
	ext4_dec_count(handle, dir);
2150 2151
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
2152 2153

end_rmdir:
2154
	ext4_journal_stop(handle);
2155
	brelse(bh);
2156 2157 2158
	return retval;
}

2159
static int ext4_unlink(struct inode *dir, struct dentry *dentry)
2160 2161
{
	int retval;
2162 2163 2164
	struct inode *inode;
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de;
2165 2166 2167 2168
	handle_t *handle;

	/* Initialize quotas before so that eventual writes go
	 * in separate transaction */
2169 2170
	dquot_initialize(dir);
	dquot_initialize(dentry->d_inode);
2171

2172
	handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
2173 2174 2175 2176
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2177
		ext4_handle_sync(handle);
2178 2179

	retval = -ENOENT;
2180
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
2181 2182 2183 2184 2185 2186 2187 2188 2189 2190
	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) {
2191
		ext4_warning(inode->i_sb,
2192 2193
			     "Deleting nonexistent file (%lu), %d",
			     inode->i_ino, inode->i_nlink);
2194 2195
		inode->i_nlink = 1;
	}
2196
	retval = ext4_delete_entry(handle, dir, de, bh);
2197 2198
	if (retval)
		goto end_unlink;
K
Kalpak Shah 已提交
2199
	dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
2200 2201
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
2202
	drop_nlink(inode);
2203
	if (!inode->i_nlink)
2204
		ext4_orphan_add(handle, inode);
K
Kalpak Shah 已提交
2205
	inode->i_ctime = ext4_current_time(inode);
2206
	ext4_mark_inode_dirty(handle, inode);
2207 2208 2209
	retval = 0;

end_unlink:
2210
	ext4_journal_stop(handle);
2211
	brelse(bh);
2212 2213 2214
	return retval;
}

2215 2216
static int ext4_symlink(struct inode *dir,
			struct dentry *dentry, const char *symname)
2217 2218
{
	handle_t *handle;
2219
	struct inode *inode;
2220 2221 2222 2223 2224 2225
	int l, err, retries = 0;

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

2226
	dquot_initialize(dir);
2227

2228
retry:
2229 2230
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 5 +
D
Dmitry Monakhov 已提交
2231
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
2232 2233 2234 2235
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2236
		ext4_handle_sync(handle);
2237

2238 2239
	inode = ext4_new_inode(handle, dir, S_IFLNK|S_IRWXUGO,
			       &dentry->d_name, 0);
2240 2241 2242 2243
	err = PTR_ERR(inode);
	if (IS_ERR(inode))
		goto out_stop;

2244
	if (l > sizeof(EXT4_I(inode)->i_data)) {
2245 2246
		inode->i_op = &ext4_symlink_inode_operations;
		ext4_set_aops(inode);
2247
		/*
2248
		 * page_symlink() calls into ext4_prepare/commit_write.
2249 2250 2251
		 * We have a transaction open.  All is sweetness.  It also sets
		 * i_size in generic_commit_write().
		 */
2252
		err = __page_symlink(inode, symname, l, 1);
2253
		if (err) {
2254
			clear_nlink(inode);
A
Al Viro 已提交
2255
			unlock_new_inode(inode);
2256
			ext4_mark_inode_dirty(handle, inode);
2257
			iput(inode);
2258 2259 2260
			goto out_stop;
		}
	} else {
2261
		/* clear the extent format for fast symlink */
2262
		ext4_clear_inode_flag(inode, EXT4_INODE_EXTENTS);
2263
		inode->i_op = &ext4_fast_symlink_inode_operations;
2264
		memcpy((char *)&EXT4_I(inode)->i_data, symname, l);
2265 2266
		inode->i_size = l-1;
	}
2267 2268
	EXT4_I(inode)->i_disksize = inode->i_size;
	err = ext4_add_nondir(handle, dentry, inode);
2269
out_stop:
2270 2271
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2272 2273 2274 2275
		goto retry;
	return err;
}

2276 2277
static int ext4_link(struct dentry *old_dentry,
		     struct inode *dir, struct dentry *dentry)
2278 2279 2280 2281 2282
{
	handle_t *handle;
	struct inode *inode = old_dentry->d_inode;
	int err, retries = 0;

2283
	if (inode->i_nlink >= EXT4_LINK_MAX)
2284
		return -EMLINK;
2285

2286
	dquot_initialize(dir);
2287

2288 2289 2290 2291 2292 2293
	/*
	 * Return -ENOENT if we've raced with unlink and i_nlink is 0.  Doing
	 * otherwise has the potential to corrupt the orphan inode list.
	 */
	if (inode->i_nlink == 0)
		return -ENOENT;
2294 2295

retry:
2296 2297
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS);
2298 2299 2300 2301
	if (IS_ERR(handle))
		return PTR_ERR(handle);

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

K
Kalpak Shah 已提交
2304
	inode->i_ctime = ext4_current_time(inode);
2305
	ext4_inc_count(handle, inode);
A
Al Viro 已提交
2306
	ihold(inode);
2307

A
Al Viro 已提交
2308 2309 2310 2311 2312 2313 2314 2315
	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);
	}
2316 2317
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2318 2319 2320 2321
		goto retry;
	return err;
}

2322 2323
#define PARENT_INO(buffer, size) \
	(ext4_next_entry((struct ext4_dir_entry_2 *)(buffer), size)->inode)
2324 2325 2326 2327 2328

/*
 * Anybody can rename anything with this: the permission checks are left to the
 * higher-level routines.
 */
2329 2330
static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry,
		       struct inode *new_dir, struct dentry *new_dentry)
2331 2332
{
	handle_t *handle;
2333 2334 2335
	struct inode *old_inode, *new_inode;
	struct buffer_head *old_bh, *new_bh, *dir_bh;
	struct ext4_dir_entry_2 *old_de, *new_de;
2336
	int retval, force_da_alloc = 0;
2337

2338 2339
	dquot_initialize(old_dir);
	dquot_initialize(new_dir);
2340

2341 2342 2343 2344 2345
	old_bh = new_bh = dir_bh = NULL;

	/* Initialize quotas before so that eventual writes go
	 * in separate transaction */
	if (new_dentry->d_inode)
2346
		dquot_initialize(new_dentry->d_inode);
2347 2348 2349
	handle = ext4_journal_start(old_dir, 2 *
					EXT4_DATA_TRANS_BLOCKS(old_dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2);
2350 2351 2352 2353
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir))
2354
		ext4_handle_sync(handle);
2355

2356
	old_bh = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de);
2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368
	/*
	 *  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;
2369
	new_bh = ext4_find_entry(new_dir, &new_dentry->d_name, &new_de);
2370 2371
	if (new_bh) {
		if (!new_inode) {
2372
			brelse(new_bh);
2373 2374 2375 2376 2377 2378
			new_bh = NULL;
		}
	}
	if (S_ISDIR(old_inode->i_mode)) {
		if (new_inode) {
			retval = -ENOTEMPTY;
2379
			if (!empty_dir(new_inode))
2380 2381 2382
				goto end_rename;
		}
		retval = -EIO;
2383
		dir_bh = ext4_bread(handle, old_inode, 0, 0, &retval);
2384 2385
		if (!dir_bh)
			goto end_rename;
2386 2387
		if (le32_to_cpu(PARENT_INO(dir_bh->b_data,
				old_dir->i_sb->s_blocksize)) != old_dir->i_ino)
2388 2389
			goto end_rename;
		retval = -EMLINK;
2390
		if (!new_inode && new_dir != old_dir &&
2391
		    EXT4_DIR_LINK_MAX(new_dir))
2392 2393 2394
			goto end_rename;
	}
	if (!new_bh) {
2395
		retval = ext4_add_entry(handle, new_dentry, old_inode);
2396 2397 2398 2399
		if (retval)
			goto end_rename;
	} else {
		BUFFER_TRACE(new_bh, "get write access");
2400
		ext4_journal_get_write_access(handle, new_bh);
2401
		new_de->inode = cpu_to_le32(old_inode->i_ino);
2402 2403
		if (EXT4_HAS_INCOMPAT_FEATURE(new_dir->i_sb,
					      EXT4_FEATURE_INCOMPAT_FILETYPE))
2404 2405
			new_de->file_type = old_de->file_type;
		new_dir->i_version++;
2406 2407 2408
		new_dir->i_ctime = new_dir->i_mtime =
					ext4_current_time(new_dir);
		ext4_mark_inode_dirty(handle, new_dir);
2409 2410
		BUFFER_TRACE(new_bh, "call ext4_handle_dirty_metadata");
		ext4_handle_dirty_metadata(handle, new_dir, new_bh);
2411 2412 2413 2414 2415 2416 2417 2418
		brelse(new_bh);
		new_bh = NULL;
	}

	/*
	 * Like most other Unix systems, set the ctime for inodes on a
	 * rename.
	 */
K
Kalpak Shah 已提交
2419
	old_inode->i_ctime = ext4_current_time(old_inode);
2420
	ext4_mark_inode_dirty(handle, old_inode);
2421 2422 2423 2424 2425 2426 2427

	/*
	 * 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) ||
2428
	    (retval = ext4_delete_entry(handle, old_dir,
2429 2430 2431 2432 2433 2434
					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;
2435
		struct ext4_dir_entry_2 *old_de2;
2436

2437
		old_bh2 = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de2);
2438
		if (old_bh2) {
2439
			retval = ext4_delete_entry(handle, old_dir,
2440 2441 2442 2443 2444
						   old_de2, old_bh2);
			brelse(old_bh2);
		}
	}
	if (retval) {
2445
		ext4_warning(old_dir->i_sb,
2446 2447 2448 2449 2450
				"Deleting old file (%lu), %d, error=%d",
				old_dir->i_ino, old_dir->i_nlink, retval);
	}

	if (new_inode) {
2451
		ext4_dec_count(handle, new_inode);
K
Kalpak Shah 已提交
2452
		new_inode->i_ctime = ext4_current_time(new_inode);
2453
	}
K
Kalpak Shah 已提交
2454
	old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
2455
	ext4_update_dx_flag(old_dir);
2456 2457
	if (dir_bh) {
		BUFFER_TRACE(dir_bh, "get_write_access");
2458
		ext4_journal_get_write_access(handle, dir_bh);
2459 2460
		PARENT_INO(dir_bh->b_data, new_dir->i_sb->s_blocksize) =
						cpu_to_le32(new_dir->i_ino);
2461 2462
		BUFFER_TRACE(dir_bh, "call ext4_handle_dirty_metadata");
		ext4_handle_dirty_metadata(handle, old_dir, dir_bh);
2463
		ext4_dec_count(handle, old_dir);
2464
		if (new_inode) {
2465
			/* checked empty_dir above, can't have another parent,
2466
			 * ext4_dec_count() won't work for many-linked dirs */
2467
			new_inode->i_nlink = 0;
2468
		} else {
2469
			ext4_inc_count(handle, new_dir);
2470 2471
			ext4_update_dx_flag(new_dir);
			ext4_mark_inode_dirty(handle, new_dir);
2472 2473
		}
	}
2474
	ext4_mark_inode_dirty(handle, old_dir);
2475
	if (new_inode) {
2476
		ext4_mark_inode_dirty(handle, new_inode);
2477
		if (!new_inode->i_nlink)
2478
			ext4_orphan_add(handle, new_inode);
2479 2480
		if (!test_opt(new_dir->i_sb, NO_AUTO_DA_ALLOC))
			force_da_alloc = 1;
2481 2482 2483 2484
	}
	retval = 0;

end_rename:
2485 2486 2487
	brelse(dir_bh);
	brelse(old_bh);
	brelse(new_bh);
2488
	ext4_journal_stop(handle);
2489 2490
	if (retval == 0 && force_da_alloc)
		ext4_alloc_da_blocks(old_inode);
2491 2492 2493 2494 2495 2496
	return retval;
}

/*
 * directories can handle most operations...
 */
2497
const struct inode_operations ext4_dir_inode_operations = {
2498 2499 2500 2501 2502 2503 2504 2505 2506 2507
	.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 已提交
2508
#ifdef CONFIG_EXT4_FS_XATTR
2509 2510
	.setxattr	= generic_setxattr,
	.getxattr	= generic_getxattr,
2511
	.listxattr	= ext4_listxattr,
2512 2513
	.removexattr	= generic_removexattr,
#endif
2514
	.check_acl	= ext4_check_acl,
2515
	.fiemap         = ext4_fiemap,
2516 2517
};

2518
const struct inode_operations ext4_special_inode_operations = {
2519
	.setattr	= ext4_setattr,
T
Theodore Ts'o 已提交
2520
#ifdef CONFIG_EXT4_FS_XATTR
2521 2522
	.setxattr	= generic_setxattr,
	.getxattr	= generic_getxattr,
2523
	.listxattr	= ext4_listxattr,
2524 2525
	.removexattr	= generic_removexattr,
#endif
2526
	.check_acl	= ext4_check_acl,
2527
};