namei.c 70.6 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 58 59
{
	struct buffer_head *bh;

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

60 61
	bh = ext4_bread(handle, inode, *block, 1, err);
	if (bh) {
62
		inode->i_size += inode->i_sb->s_blocksize;
63
		EXT4_I(inode)->i_disksize = inode->i_size;
64 65 66 67 68
		*err = ext4_journal_get_write_access(handle, bh);
		if (*err) {
			brelse(bh);
			bh = NULL;
		}
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 143
	}
	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;
144 145
	u16 offs;
	u16 size;
146 147
};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 449
		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;
450
		if (!(bh = ext4_bread (NULL,dir, dx_get_block(at), 0, err)))
451 452
			goto fail2;
		at = entries = ((struct dx_node *) bh->b_data)->entries;
453
		if (dx_get_limit(entries) != dx_node_limit (dir)) {
454
			ext4_warning(dir->i_sb,
455 456 457 458 459
				     "dx entry: limit != node limit");
			brelse(bh);
			*err = ERR_BAD_DX_DIR;
			goto fail2;
		}
460
		frame++;
461
		frame->bh = NULL;
462 463 464 465 466 467 468
	}
fail2:
	while (frame >= frame_in) {
		brelse(frame->bh);
		frame--;
	}
fail:
469
	if (*err == ERR_BAD_DX_DIR)
470
		ext4_warning(dir->i_sb,
471 472
			     "Corrupt dir inode %ld, running e2fsck is "
			     "recommended.", dir->i_ino);
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 502
	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.
 */
503
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
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 548
				 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--) {
549
		if (!(bh = ext4_bread(NULL, dir, dx_get_block(p->at),
550 551 552
				      0, &err)))
			return err; /* Failure */
		p++;
553
		brelse(p->bh);
554 555 556 557 558 559 560 561 562 563 564 565 566
		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 已提交
567
				  struct inode *dir, ext4_lblk_t block,
568 569 570 571
				  struct dx_hash_info *hinfo,
				  __u32 start_hash, __u32 start_minor_hash)
{
	struct buffer_head *bh;
572
	struct ext4_dir_entry_2 *de, *top;
573 574
	int err, count = 0;

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

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

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

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


/*
 * Directory block splitting, compacting
 */

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

	data2 = bh2->b_data;

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

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

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

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

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

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

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

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

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

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

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

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

	ext4_handle_dirty_metadata(handle, dir, frame->bh);
	ext4_handle_dirty_metadata(handle, dir, bh);

1420
	de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
1421 1422 1423 1424 1425 1426 1427 1428
	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);
1429
		return retval;
1430 1431
	}
	dx_release(frames);
1432

1433 1434 1435
	retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
	brelse(bh);
	return retval;
1436 1437 1438
}

/*
1439
 *	ext4_add_entry()
1440 1441
 *
 * adds a file entry to the specified directory, using the same
1442
 * semantics as ext4_find_entry(). It returns NULL if it failed.
1443 1444 1445 1446 1447
 *
 * 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.
 */
1448 1449
static int ext4_add_entry(handle_t *handle, struct dentry *dentry,
			  struct inode *inode)
1450 1451
{
	struct inode *dir = dentry->d_parent->d_inode;
1452
	struct buffer_head *bh;
1453
	struct ext4_dir_entry_2 *de;
1454
	struct super_block *sb;
1455 1456 1457
	int	retval;
	int	dx_fallback=0;
	unsigned blocksize;
A
Aneesh Kumar K.V 已提交
1458
	ext4_lblk_t block, blocks;
1459 1460 1461 1462 1463 1464

	sb = dir->i_sb;
	blocksize = sb->s_blocksize;
	if (!dentry->d_name.len)
		return -EINVAL;
	if (is_dx(dir)) {
1465
		retval = ext4_dx_add_entry(handle, dentry, inode);
1466 1467
		if (!retval || (retval != ERR_BAD_DX_DIR))
			return retval;
1468
		ext4_clear_inode_flag(dir, EXT4_INODE_INDEX);
1469
		dx_fallback++;
1470
		ext4_mark_inode_dirty(handle, dir);
1471 1472
	}
	blocks = dir->i_size >> sb->s_blocksize_bits;
1473
	for (block = 0; block < blocks; block++) {
1474
		bh = ext4_bread(handle, dir, block, 0, &retval);
1475 1476 1477
		if(!bh)
			return retval;
		retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1478 1479
		if (retval != -ENOSPC) {
			brelse(bh);
1480
			return retval;
1481
		}
1482 1483

		if (blocks == 1 && !dx_fallback &&
1484 1485
		    EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX))
			return make_indexed_dir(handle, dentry, inode, bh);
1486 1487
		brelse(bh);
	}
1488
	bh = ext4_append(handle, dir, &block, &retval);
1489 1490
	if (!bh)
		return retval;
1491
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1492
	de->inode = 0;
1493
	de->rec_len = ext4_rec_len_to_disk(blocksize, blocksize);
1494 1495
	retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
	brelse(bh);
1496 1497
	if (retval == 0)
		ext4_set_inode_state(inode, EXT4_STATE_NEWENTRY);
1498
	return retval;
1499 1500 1501 1502 1503
}

/*
 * Returns 0 for success, or a negative error value
 */
1504
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
1505 1506 1507 1508 1509
			     struct inode *inode)
{
	struct dx_frame frames[2], *frame;
	struct dx_entry *entries, *at;
	struct dx_hash_info hinfo;
1510
	struct buffer_head *bh;
1511
	struct inode *dir = dentry->d_parent->d_inode;
1512
	struct super_block *sb = dir->i_sb;
1513
	struct ext4_dir_entry_2 *de;
1514 1515
	int err;

1516
	frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
1517 1518 1519 1520 1521
	if (!frame)
		return err;
	entries = frame->entries;
	at = frame->at;

1522
	if (!(bh = ext4_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
1523 1524 1525
		goto cleanup;

	BUFFER_TRACE(bh, "get_write_access");
1526
	err = ext4_journal_get_write_access(handle, bh);
1527 1528 1529 1530
	if (err)
		goto journal_error;

	err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1531
	if (err != -ENOSPC)
1532 1533 1534
		goto cleanup;

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

			BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
1571
			err = ext4_journal_get_write_access(handle,
1572 1573 1574 1575
							     frames[0].bh);
			if (err)
				goto journal_error;

1576 1577 1578 1579 1580
			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));
1581 1582 1583 1584 1585 1586 1587

			/* 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);
			}
1588 1589 1590
			dx_insert_block(frames + 0, hash2, newblock);
			dxtrace(dx_show_index("node", frames[1].entries));
			dxtrace(dx_show_index("node",
1591
			       ((struct dx_node *) bh2->b_data)->entries));
1592
			err = ext4_handle_dirty_metadata(handle, inode, bh2);
1593 1594 1595 1596
			if (err)
				goto journal_error;
			brelse (bh2);
		} else {
1597 1598
			dxtrace(printk(KERN_DEBUG
				       "Creating second level index...\n"));
1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612
			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;
1613
			err = ext4_journal_get_write_access(handle,
1614 1615 1616 1617
							     frame->bh);
			if (err)
				goto journal_error;
		}
1618 1619 1620 1621 1622
		err = ext4_handle_dirty_metadata(handle, inode, frames[0].bh);
		if (err) {
			ext4_std_error(inode->i_sb, err);
			goto cleanup;
		}
1623 1624 1625 1626 1627 1628 1629 1630
	}
	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:
1631
	ext4_std_error(dir->i_sb, err);
1632 1633 1634 1635 1636 1637 1638 1639
cleanup:
	if (bh)
		brelse(bh);
	dx_release(frames);
	return err;
}

/*
1640
 * ext4_delete_entry deletes a directory entry by merging it with the
1641 1642
 * previous entry
 */
1643 1644 1645 1646
static int ext4_delete_entry(handle_t *handle,
			     struct inode *dir,
			     struct ext4_dir_entry_2 *de_del,
			     struct buffer_head *bh)
1647
{
1648
	struct ext4_dir_entry_2 *de, *pde;
1649
	unsigned int blocksize = dir->i_sb->s_blocksize;
1650
	int i, err;
1651 1652 1653

	i = 0;
	pde = NULL;
1654
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1655
	while (i < bh->b_size) {
1656
		if (ext4_check_dir_entry(dir, NULL, de, bh, i))
1657 1658 1659
			return -EIO;
		if (de == de_del)  {
			BUFFER_TRACE(bh, "get_write_access");
1660 1661 1662 1663 1664
			err = ext4_journal_get_write_access(handle, bh);
			if (unlikely(err)) {
				ext4_std_error(dir->i_sb, err);
				return err;
			}
1665
			if (pde)
1666
				pde->rec_len = ext4_rec_len_to_disk(
1667 1668 1669 1670 1671
					ext4_rec_len_from_disk(pde->rec_len,
							       blocksize) +
					ext4_rec_len_from_disk(de->rec_len,
							       blocksize),
					blocksize);
1672 1673 1674
			else
				de->inode = 0;
			dir->i_version++;
1675
			BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
1676 1677 1678 1679 1680
			err = ext4_handle_dirty_metadata(handle, dir, bh);
			if (unlikely(err)) {
				ext4_std_error(dir->i_sb, err);
				return err;
			}
1681 1682
			return 0;
		}
1683
		i += ext4_rec_len_from_disk(de->rec_len, blocksize);
1684
		pde = de;
1685
		de = ext4_next_entry(de, blocksize);
1686 1687 1688 1689
	}
	return -ENOENT;
}

1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718
/*
 * 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);
}


1719
static int ext4_add_nondir(handle_t *handle,
1720 1721
		struct dentry *dentry, struct inode *inode)
{
1722
	int err = ext4_add_entry(handle, dentry, inode);
1723
	if (!err) {
1724
		ext4_mark_inode_dirty(handle, inode);
1725
		d_instantiate(dentry, inode);
A
Al Viro 已提交
1726
		unlock_new_inode(inode);
1727 1728
		return 0;
	}
1729
	drop_nlink(inode);
A
Al Viro 已提交
1730
	unlock_new_inode(inode);
1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742
	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().
 */
1743 1744
static int ext4_create(struct inode *dir, struct dentry *dentry, int mode,
		       struct nameidata *nd)
1745 1746
{
	handle_t *handle;
1747
	struct inode *inode;
1748 1749
	int err, retries = 0;

1750
	dquot_initialize(dir);
1751

1752
retry:
1753 1754
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
1755
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
1756 1757 1758 1759
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
1760
		ext4_handle_sync(handle);
1761

1762
	inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0);
1763 1764
	err = PTR_ERR(inode);
	if (!IS_ERR(inode)) {
1765 1766 1767 1768
		inode->i_op = &ext4_file_inode_operations;
		inode->i_fop = &ext4_file_operations;
		ext4_set_aops(inode);
		err = ext4_add_nondir(handle, dentry, inode);
1769
	}
1770 1771
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
1772 1773 1774 1775
		goto retry;
	return err;
}

1776 1777
static int ext4_mknod(struct inode *dir, struct dentry *dentry,
		      int mode, dev_t rdev)
1778 1779 1780 1781 1782 1783 1784 1785
{
	handle_t *handle;
	struct inode *inode;
	int err, retries = 0;

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

1786
	dquot_initialize(dir);
1787

1788
retry:
1789 1790
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
1791
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
1792 1793 1794 1795
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
1796
		ext4_handle_sync(handle);
1797

1798
	inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0);
1799 1800 1801
	err = PTR_ERR(inode);
	if (!IS_ERR(inode)) {
		init_special_inode(inode, inode->i_mode, rdev);
T
Theodore Ts'o 已提交
1802
#ifdef CONFIG_EXT4_FS_XATTR
1803
		inode->i_op = &ext4_special_inode_operations;
1804
#endif
1805
		err = ext4_add_nondir(handle, dentry, inode);
1806
	}
1807 1808
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
1809 1810 1811 1812
		goto retry;
	return err;
}

1813
static int ext4_mkdir(struct inode *dir, struct dentry *dentry, int mode)
1814 1815
{
	handle_t *handle;
1816
	struct inode *inode;
1817
	struct buffer_head *dir_block = NULL;
1818
	struct ext4_dir_entry_2 *de;
1819
	unsigned int blocksize = dir->i_sb->s_blocksize;
1820 1821
	int err, retries = 0;

1822
	if (EXT4_DIR_LINK_MAX(dir))
1823 1824
		return -EMLINK;

1825
	dquot_initialize(dir);
1826

1827
retry:
1828 1829
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
D
Dmitry Monakhov 已提交
1830
					EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
1831 1832 1833 1834
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
1835
		ext4_handle_sync(handle);
1836

1837 1838
	inode = ext4_new_inode(handle, dir, S_IFDIR | mode,
			       &dentry->d_name, 0);
1839 1840 1841 1842
	err = PTR_ERR(inode);
	if (IS_ERR(inode))
		goto out_stop;

1843 1844 1845
	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;
1846
	dir_block = ext4_bread(handle, inode, 0, 1, &err);
1847 1848
	if (!dir_block)
		goto out_clear_inode;
1849
	BUFFER_TRACE(dir_block, "get_write_access");
1850 1851 1852
	err = ext4_journal_get_write_access(handle, dir_block);
	if (err)
		goto out_clear_inode;
1853
	de = (struct ext4_dir_entry_2 *) dir_block->b_data;
1854 1855
	de->inode = cpu_to_le32(inode->i_ino);
	de->name_len = 1;
1856 1857
	de->rec_len = ext4_rec_len_to_disk(EXT4_DIR_REC_LEN(de->name_len),
					   blocksize);
1858
	strcpy(de->name, ".");
1859
	ext4_set_de_type(dir->i_sb, de, S_IFDIR);
1860
	de = ext4_next_entry(de, blocksize);
1861
	de->inode = cpu_to_le32(dir->i_ino);
1862 1863
	de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(1),
					   blocksize);
1864
	de->name_len = 2;
1865
	strcpy(de->name, "..");
1866
	ext4_set_de_type(dir->i_sb, de, S_IFDIR);
1867
	inode->i_nlink = 2;
1868
	BUFFER_TRACE(dir_block, "call ext4_handle_dirty_metadata");
1869 1870 1871 1872 1873 1874
	err = ext4_handle_dirty_metadata(handle, dir, dir_block);
	if (err)
		goto out_clear_inode;
	err = ext4_mark_inode_dirty(handle, inode);
	if (!err)
		err = ext4_add_entry(handle, dentry, inode);
1875
	if (err) {
1876 1877
out_clear_inode:
		clear_nlink(inode);
A
Al Viro 已提交
1878
		unlock_new_inode(inode);
1879
		ext4_mark_inode_dirty(handle, inode);
1880
		iput(inode);
1881 1882
		goto out_stop;
	}
1883
	ext4_inc_count(handle, dir);
1884
	ext4_update_dx_flag(dir);
1885 1886 1887
	err = ext4_mark_inode_dirty(handle, dir);
	if (err)
		goto out_clear_inode;
1888
	d_instantiate(dentry, inode);
A
Al Viro 已提交
1889
	unlock_new_inode(inode);
1890
out_stop:
1891
	brelse(dir_block);
1892 1893
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
1894 1895 1896 1897 1898 1899 1900
		goto retry;
	return err;
}

/*
 * routine to check that the specified directory is empty (for rmdir)
 */
1901
static int empty_dir(struct inode *inode)
1902
{
1903
	unsigned int offset;
1904 1905 1906
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de, *de1;
	struct super_block *sb;
1907 1908 1909
	int err = 0;

	sb = inode->i_sb;
1910
	if (inode->i_size < EXT4_DIR_REC_LEN(1) + EXT4_DIR_REC_LEN(2) ||
1911
	    !(bh = ext4_bread(NULL, inode, 0, 0, &err))) {
1912
		if (err)
1913 1914
			EXT4_ERROR_INODE(inode,
				"error %d reading directory lblock 0", err);
1915
		else
1916
			ext4_warning(inode->i_sb,
1917 1918 1919 1920
				     "bad directory (dir #%lu) - no data block",
				     inode->i_ino);
		return 1;
	}
1921
	de = (struct ext4_dir_entry_2 *) bh->b_data;
1922
	de1 = ext4_next_entry(de, sb->s_blocksize);
1923 1924
	if (le32_to_cpu(de->inode) != inode->i_ino ||
			!le32_to_cpu(de1->inode) ||
1925 1926
			strcmp(".", de->name) ||
			strcmp("..", de1->name)) {
1927
		ext4_warning(inode->i_sb,
1928 1929 1930
			     "bad directory (dir #%lu) - no `.' or `..'",
			     inode->i_ino);
		brelse(bh);
1931 1932
		return 1;
	}
1933 1934 1935
	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);
1936
	while (offset < inode->i_size) {
1937
		if (!bh ||
1938 1939
		    (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
			unsigned int lblock;
1940
			err = 0;
1941
			brelse(bh);
1942 1943
			lblock = offset >> EXT4_BLOCK_SIZE_BITS(sb);
			bh = ext4_bread(NULL, inode, lblock, 0, &err);
1944 1945
			if (!bh) {
				if (err)
1946 1947 1948
					EXT4_ERROR_INODE(inode,
						"error %d reading directory "
						"lblock %u", err, lblock);
1949 1950 1951
				offset += sb->s_blocksize;
				continue;
			}
1952
			de = (struct ext4_dir_entry_2 *) bh->b_data;
1953
		}
1954
		if (ext4_check_dir_entry(inode, NULL, de, bh, offset)) {
1955
			de = (struct ext4_dir_entry_2 *)(bh->b_data +
1956 1957 1958 1959 1960
							 sb->s_blocksize);
			offset = (offset | (sb->s_blocksize - 1)) + 1;
			continue;
		}
		if (le32_to_cpu(de->inode)) {
1961
			brelse(bh);
1962 1963
			return 0;
		}
1964 1965
		offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
		de = ext4_next_entry(de, sb->s_blocksize);
1966
	}
1967
	brelse(bh);
1968 1969 1970
	return 1;
}

1971
/* ext4_orphan_add() links an unlinked or truncated inode into a list of
1972 1973 1974 1975 1976
 * 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
1977
 * inodes and truncating linked inodes in ext4_orphan_cleanup().
1978
 */
1979
int ext4_orphan_add(handle_t *handle, struct inode *inode)
1980 1981
{
	struct super_block *sb = inode->i_sb;
1982
	struct ext4_iloc iloc;
1983 1984
	int err = 0, rc;

1985 1986 1987
	if (!ext4_handle_valid(handle))
		return 0;

1988
	mutex_lock(&EXT4_SB(sb)->s_orphan_lock);
1989
	if (!list_empty(&EXT4_I(inode)->i_orphan))
1990 1991 1992 1993 1994 1995
		goto out_unlock;

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

	/* @@@ FIXME: Observation from aviro:
1996
	 * I think I can trigger J_ASSERT in ext4_orphan_add().  We block
1997
	 * here (on s_orphan_lock), so race with ext4_link() which might bump
1998 1999
	 * ->i_nlink. For, say it, character device. Not a regular file,
	 * not a directory, not a symlink and ->i_nlink > 0.
2000 2001 2002 2003
	 *
	 * 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?
2004
	 */
2005 2006
	J_ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
		  S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
2007

2008 2009
	BUFFER_TRACE(EXT4_SB(sb)->s_sbh, "get_write_access");
	err = ext4_journal_get_write_access(handle, EXT4_SB(sb)->s_sbh);
2010 2011 2012
	if (err)
		goto out_unlock;

2013
	err = ext4_reserve_inode_write(handle, inode, &iloc);
2014 2015
	if (err)
		goto out_unlock;
2016 2017 2018 2019 2020 2021 2022
	/*
	 * 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;
2023 2024

	/* Insert this inode at the head of the on-disk orphan list... */
2025 2026
	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);
2027
	err = ext4_handle_dirty_metadata(handle, NULL, EXT4_SB(sb)->s_sbh);
2028
	rc = ext4_mark_iloc_dirty(handle, inode, &iloc);
2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039
	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. */
2040
mem_insert:
2041
	if (!err)
2042
		list_add(&EXT4_I(inode)->i_orphan, &EXT4_SB(sb)->s_orphan);
2043 2044 2045 2046 2047

	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:
2048
	mutex_unlock(&EXT4_SB(sb)->s_orphan_lock);
2049
	ext4_std_error(inode->i_sb, err);
2050 2051 2052 2053
	return err;
}

/*
2054
 * ext4_orphan_del() removes an unlinked or truncated inode from the list
2055 2056
 * of such inodes stored on disk, because it is finally being cleaned up.
 */
2057
int ext4_orphan_del(handle_t *handle, struct inode *inode)
2058 2059
{
	struct list_head *prev;
2060 2061
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi;
2062
	__u32 ino_next;
2063
	struct ext4_iloc iloc;
2064 2065
	int err = 0;

2066 2067
	/* ext4_handle_valid() assumes a valid handle_t pointer */
	if (handle && !ext4_handle_valid(handle))
2068 2069
		return 0;

2070 2071 2072
	mutex_lock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
	if (list_empty(&ei->i_orphan))
		goto out;
2073 2074 2075

	ino_next = NEXT_ORPHAN(inode);
	prev = ei->i_orphan.prev;
2076
	sbi = EXT4_SB(inode->i_sb);
2077 2078 2079 2080 2081 2082 2083 2084 2085

	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. */
2086
	if (sbi->s_journal && !handle)
2087 2088
		goto out;

2089
	err = ext4_reserve_inode_write(handle, inode, &iloc);
2090 2091 2092 2093
	if (err)
		goto out_err;

	if (prev == &sbi->s_orphan) {
2094
		jbd_debug(4, "superblock will point to %u\n", ino_next);
2095
		BUFFER_TRACE(sbi->s_sbh, "get_write_access");
2096
		err = ext4_journal_get_write_access(handle, sbi->s_sbh);
2097 2098 2099
		if (err)
			goto out_brelse;
		sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
2100
		err = ext4_handle_dirty_metadata(handle, NULL, sbi->s_sbh);
2101
	} else {
2102
		struct ext4_iloc iloc2;
2103
		struct inode *i_prev =
2104
			&list_entry(prev, struct ext4_inode_info, i_orphan)->vfs_inode;
2105

2106
		jbd_debug(4, "orphan inode %lu will point to %u\n",
2107
			  i_prev->i_ino, ino_next);
2108
		err = ext4_reserve_inode_write(handle, i_prev, &iloc2);
2109 2110 2111
		if (err)
			goto out_brelse;
		NEXT_ORPHAN(i_prev) = ino_next;
2112
		err = ext4_mark_iloc_dirty(handle, i_prev, &iloc2);
2113 2114 2115 2116
	}
	if (err)
		goto out_brelse;
	NEXT_ORPHAN(inode) = 0;
2117
	err = ext4_mark_iloc_dirty(handle, inode, &iloc);
2118 2119

out_err:
2120
	ext4_std_error(inode->i_sb, err);
2121
out:
2122
	mutex_unlock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
2123 2124 2125 2126 2127 2128 2129
	return err;

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

2130
static int ext4_rmdir(struct inode *dir, struct dentry *dentry)
2131 2132
{
	int retval;
2133 2134 2135
	struct inode *inode;
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de;
2136 2137 2138 2139
	handle_t *handle;

	/* Initialize quotas before so that eventual writes go in
	 * separate transaction */
2140 2141
	dquot_initialize(dir);
	dquot_initialize(dentry->d_inode);
2142

2143
	handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
2144 2145 2146 2147
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	retval = -ENOENT;
2148
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
2149 2150 2151 2152
	if (!bh)
		goto end_rmdir;

	if (IS_DIRSYNC(dir))
2153
		ext4_handle_sync(handle);
2154 2155 2156 2157 2158 2159 2160 2161

	inode = dentry->d_inode;

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

	retval = -ENOTEMPTY;
2162
	if (!empty_dir(inode))
2163 2164
		goto end_rmdir;

2165
	retval = ext4_delete_entry(handle, dir, de, bh);
2166 2167
	if (retval)
		goto end_rmdir;
2168
	if (!EXT4_DIR_LINK_EMPTY(inode))
2169
		ext4_warning(inode->i_sb,
2170 2171
			     "empty directory has too many links (%d)",
			     inode->i_nlink);
2172 2173 2174 2175 2176 2177
	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;
2178
	ext4_orphan_add(handle, inode);
K
Kalpak Shah 已提交
2179
	inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
2180
	ext4_mark_inode_dirty(handle, inode);
2181
	ext4_dec_count(handle, dir);
2182 2183
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
2184 2185

end_rmdir:
2186
	ext4_journal_stop(handle);
2187
	brelse(bh);
2188 2189 2190
	return retval;
}

2191
static int ext4_unlink(struct inode *dir, struct dentry *dentry)
2192 2193
{
	int retval;
2194 2195 2196
	struct inode *inode;
	struct buffer_head *bh;
	struct ext4_dir_entry_2 *de;
2197 2198
	handle_t *handle;

2199
	trace_ext4_unlink_enter(dir, dentry);
2200 2201
	/* Initialize quotas before so that eventual writes go
	 * in separate transaction */
2202 2203
	dquot_initialize(dir);
	dquot_initialize(dentry->d_inode);
2204

2205
	handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
2206 2207 2208 2209
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2210
		ext4_handle_sync(handle);
2211 2212

	retval = -ENOENT;
2213
	bh = ext4_find_entry(dir, &dentry->d_name, &de);
2214 2215 2216 2217 2218 2219 2220 2221 2222 2223
	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) {
2224
		ext4_warning(inode->i_sb,
2225 2226
			     "Deleting nonexistent file (%lu), %d",
			     inode->i_ino, inode->i_nlink);
2227 2228
		inode->i_nlink = 1;
	}
2229
	retval = ext4_delete_entry(handle, dir, de, bh);
2230 2231
	if (retval)
		goto end_unlink;
K
Kalpak Shah 已提交
2232
	dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
2233 2234
	ext4_update_dx_flag(dir);
	ext4_mark_inode_dirty(handle, dir);
2235
	drop_nlink(inode);
2236
	if (!inode->i_nlink)
2237
		ext4_orphan_add(handle, inode);
K
Kalpak Shah 已提交
2238
	inode->i_ctime = ext4_current_time(inode);
2239
	ext4_mark_inode_dirty(handle, inode);
2240 2241 2242
	retval = 0;

end_unlink:
2243
	ext4_journal_stop(handle);
2244
	brelse(bh);
2245
	trace_ext4_unlink_exit(dentry, retval);
2246 2247 2248
	return retval;
}

2249 2250
static int ext4_symlink(struct inode *dir,
			struct dentry *dentry, const char *symname)
2251 2252
{
	handle_t *handle;
2253
	struct inode *inode;
2254
	int l, err, retries = 0;
2255
	int credits;
2256 2257 2258 2259 2260

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

2261
	dquot_initialize(dir);
2262

2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280
	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,
		 * group descriptor, sb, inode block, quota blocks.
		 */
		credits = 4 + EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb);
	} 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);
	}
2281
retry:
2282
	handle = ext4_journal_start(dir, credits);
2283 2284 2285 2286
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2287
		ext4_handle_sync(handle);
2288

2289 2290
	inode = ext4_new_inode(handle, dir, S_IFLNK|S_IRWXUGO,
			       &dentry->d_name, 0);
2291 2292 2293 2294
	err = PTR_ERR(inode);
	if (IS_ERR(inode))
		goto out_stop;

2295
	if (l > EXT4_N_BLOCKS * 4) {
2296 2297
		inode->i_op = &ext4_symlink_inode_operations;
		ext4_set_aops(inode);
2298
		/*
2299 2300 2301 2302 2303 2304 2305 2306
		 * 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.
2307
		 */
2308 2309 2310 2311 2312
		drop_nlink(inode);
		err = ext4_orphan_add(handle, inode);
		ext4_journal_stop(handle);
		if (err)
			goto err_drop_inode;
2313
		err = __page_symlink(inode, symname, l, 1);
2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328
		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;
		}
		inc_nlink(inode);
		err = ext4_orphan_del(handle, inode);
2329
		if (err) {
2330
			ext4_journal_stop(handle);
2331
			clear_nlink(inode);
2332
			goto err_drop_inode;
2333 2334
		}
	} else {
2335
		/* clear the extent format for fast symlink */
2336
		ext4_clear_inode_flag(inode, EXT4_INODE_EXTENTS);
2337
		inode->i_op = &ext4_fast_symlink_inode_operations;
2338
		memcpy((char *)&EXT4_I(inode)->i_data, symname, l);
2339 2340
		inode->i_size = l-1;
	}
2341 2342
	EXT4_I(inode)->i_disksize = inode->i_size;
	err = ext4_add_nondir(handle, dentry, inode);
2343
out_stop:
2344 2345
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2346 2347
		goto retry;
	return err;
2348 2349 2350 2351
err_drop_inode:
	unlock_new_inode(inode);
	iput(inode);
	return err;
2352 2353
}

2354 2355
static int ext4_link(struct dentry *old_dentry,
		     struct inode *dir, struct dentry *dentry)
2356 2357 2358 2359 2360
{
	handle_t *handle;
	struct inode *inode = old_dentry->d_inode;
	int err, retries = 0;

2361
	if (inode->i_nlink >= EXT4_LINK_MAX)
2362
		return -EMLINK;
2363

2364
	dquot_initialize(dir);
2365

2366
retry:
2367 2368
	handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS);
2369 2370 2371 2372
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(dir))
2373
		ext4_handle_sync(handle);
2374

K
Kalpak Shah 已提交
2375
	inode->i_ctime = ext4_current_time(inode);
2376
	ext4_inc_count(handle, inode);
A
Al Viro 已提交
2377
	ihold(inode);
2378

A
Al Viro 已提交
2379 2380 2381 2382 2383 2384 2385 2386
	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);
	}
2387 2388
	ext4_journal_stop(handle);
	if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2389 2390 2391 2392
		goto retry;
	return err;
}

2393 2394
#define PARENT_INO(buffer, size) \
	(ext4_next_entry((struct ext4_dir_entry_2 *)(buffer), size)->inode)
2395 2396 2397 2398 2399

/*
 * Anybody can rename anything with this: the permission checks are left to the
 * higher-level routines.
 */
2400 2401
static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry,
		       struct inode *new_dir, struct dentry *new_dentry)
2402 2403
{
	handle_t *handle;
2404 2405 2406
	struct inode *old_inode, *new_inode;
	struct buffer_head *old_bh, *new_bh, *dir_bh;
	struct ext4_dir_entry_2 *old_de, *new_de;
2407
	int retval, force_da_alloc = 0;
2408

2409 2410
	dquot_initialize(old_dir);
	dquot_initialize(new_dir);
2411

2412 2413 2414 2415 2416
	old_bh = new_bh = dir_bh = NULL;

	/* Initialize quotas before so that eventual writes go
	 * in separate transaction */
	if (new_dentry->d_inode)
2417
		dquot_initialize(new_dentry->d_inode);
2418 2419 2420
	handle = ext4_journal_start(old_dir, 2 *
					EXT4_DATA_TRANS_BLOCKS(old_dir->i_sb) +
					EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2);
2421 2422 2423 2424
	if (IS_ERR(handle))
		return PTR_ERR(handle);

	if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir))
2425
		ext4_handle_sync(handle);
2426

2427
	old_bh = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de);
2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439
	/*
	 *  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;
2440
	new_bh = ext4_find_entry(new_dir, &new_dentry->d_name, &new_de);
2441 2442
	if (new_bh) {
		if (!new_inode) {
2443
			brelse(new_bh);
2444 2445 2446 2447 2448 2449
			new_bh = NULL;
		}
	}
	if (S_ISDIR(old_inode->i_mode)) {
		if (new_inode) {
			retval = -ENOTEMPTY;
2450
			if (!empty_dir(new_inode))
2451 2452 2453
				goto end_rename;
		}
		retval = -EIO;
2454
		dir_bh = ext4_bread(handle, old_inode, 0, 0, &retval);
2455 2456
		if (!dir_bh)
			goto end_rename;
2457 2458
		if (le32_to_cpu(PARENT_INO(dir_bh->b_data,
				old_dir->i_sb->s_blocksize)) != old_dir->i_ino)
2459 2460
			goto end_rename;
		retval = -EMLINK;
2461
		if (!new_inode && new_dir != old_dir &&
2462
		    EXT4_DIR_LINK_MAX(new_dir))
2463
			goto end_rename;
2464 2465 2466 2467
		BUFFER_TRACE(dir_bh, "get_write_access");
		retval = ext4_journal_get_write_access(handle, dir_bh);
		if (retval)
			goto end_rename;
2468 2469
	}
	if (!new_bh) {
2470
		retval = ext4_add_entry(handle, new_dentry, old_inode);
2471 2472 2473 2474
		if (retval)
			goto end_rename;
	} else {
		BUFFER_TRACE(new_bh, "get write access");
2475 2476 2477
		retval = ext4_journal_get_write_access(handle, new_bh);
		if (retval)
			goto end_rename;
2478
		new_de->inode = cpu_to_le32(old_inode->i_ino);
2479 2480
		if (EXT4_HAS_INCOMPAT_FEATURE(new_dir->i_sb,
					      EXT4_FEATURE_INCOMPAT_FILETYPE))
2481 2482
			new_de->file_type = old_de->file_type;
		new_dir->i_version++;
2483 2484 2485
		new_dir->i_ctime = new_dir->i_mtime =
					ext4_current_time(new_dir);
		ext4_mark_inode_dirty(handle, new_dir);
2486
		BUFFER_TRACE(new_bh, "call ext4_handle_dirty_metadata");
2487 2488 2489 2490 2491
		retval = ext4_handle_dirty_metadata(handle, new_dir, new_bh);
		if (unlikely(retval)) {
			ext4_std_error(new_dir->i_sb, retval);
			goto end_rename;
		}
2492 2493 2494 2495 2496 2497 2498 2499
		brelse(new_bh);
		new_bh = NULL;
	}

	/*
	 * Like most other Unix systems, set the ctime for inodes on a
	 * rename.
	 */
K
Kalpak Shah 已提交
2500
	old_inode->i_ctime = ext4_current_time(old_inode);
2501
	ext4_mark_inode_dirty(handle, old_inode);
2502 2503 2504 2505 2506 2507 2508

	/*
	 * 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) ||
2509
	    (retval = ext4_delete_entry(handle, old_dir,
2510 2511 2512 2513 2514 2515
					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;
2516
		struct ext4_dir_entry_2 *old_de2;
2517

2518
		old_bh2 = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de2);
2519
		if (old_bh2) {
2520
			retval = ext4_delete_entry(handle, old_dir,
2521 2522 2523 2524 2525
						   old_de2, old_bh2);
			brelse(old_bh2);
		}
	}
	if (retval) {
2526
		ext4_warning(old_dir->i_sb,
2527 2528 2529 2530 2531
				"Deleting old file (%lu), %d, error=%d",
				old_dir->i_ino, old_dir->i_nlink, retval);
	}

	if (new_inode) {
2532
		ext4_dec_count(handle, new_inode);
K
Kalpak Shah 已提交
2533
		new_inode->i_ctime = ext4_current_time(new_inode);
2534
	}
K
Kalpak Shah 已提交
2535
	old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
2536
	ext4_update_dx_flag(old_dir);
2537
	if (dir_bh) {
2538 2539
		PARENT_INO(dir_bh->b_data, new_dir->i_sb->s_blocksize) =
						cpu_to_le32(new_dir->i_ino);
2540
		BUFFER_TRACE(dir_bh, "call ext4_handle_dirty_metadata");
2541 2542 2543 2544 2545
		retval = ext4_handle_dirty_metadata(handle, old_dir, dir_bh);
		if (retval) {
			ext4_std_error(old_dir->i_sb, retval);
			goto end_rename;
		}
2546
		ext4_dec_count(handle, old_dir);
2547
		if (new_inode) {
2548
			/* checked empty_dir above, can't have another parent,
2549
			 * ext4_dec_count() won't work for many-linked dirs */
2550
			new_inode->i_nlink = 0;
2551
		} else {
2552
			ext4_inc_count(handle, new_dir);
2553 2554
			ext4_update_dx_flag(new_dir);
			ext4_mark_inode_dirty(handle, new_dir);
2555 2556
		}
	}
2557
	ext4_mark_inode_dirty(handle, old_dir);
2558
	if (new_inode) {
2559
		ext4_mark_inode_dirty(handle, new_inode);
2560
		if (!new_inode->i_nlink)
2561
			ext4_orphan_add(handle, new_inode);
2562 2563
		if (!test_opt(new_dir->i_sb, NO_AUTO_DA_ALLOC))
			force_da_alloc = 1;
2564 2565 2566 2567
	}
	retval = 0;

end_rename:
2568 2569 2570
	brelse(dir_bh);
	brelse(old_bh);
	brelse(new_bh);
2571
	ext4_journal_stop(handle);
2572 2573
	if (retval == 0 && force_da_alloc)
		ext4_alloc_da_blocks(old_inode);
2574 2575 2576 2577 2578 2579
	return retval;
}

/*
 * directories can handle most operations...
 */
2580
const struct inode_operations ext4_dir_inode_operations = {
2581 2582 2583 2584 2585 2586 2587 2588 2589 2590
	.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 已提交
2591
#ifdef CONFIG_EXT4_FS_XATTR
2592 2593
	.setxattr	= generic_setxattr,
	.getxattr	= generic_getxattr,
2594
	.listxattr	= ext4_listxattr,
2595 2596
	.removexattr	= generic_removexattr,
#endif
2597
	.check_acl	= ext4_check_acl,
2598
	.fiemap         = ext4_fiemap,
2599 2600
};

2601
const struct inode_operations ext4_special_inode_operations = {
2602
	.setattr	= ext4_setattr,
T
Theodore Ts'o 已提交
2603
#ifdef CONFIG_EXT4_FS_XATTR
2604 2605
	.setxattr	= generic_setxattr,
	.getxattr	= generic_getxattr,
2606
	.listxattr	= ext4_listxattr,
2607 2608
	.removexattr	= generic_removexattr,
#endif
2609
	.check_acl	= ext4_check_acl,
2610
};