dir.c 49.3 KB
Newer Older
D
David Teigland 已提交
1 2
/*
 * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
3
 * Copyright (C) 2004-2006 Red Hat, Inc.  All rights reserved.
D
David Teigland 已提交
4 5 6
 *
 * This copyrighted material is made available to anyone wishing to use,
 * modify, copy, or redistribute it subject to the terms and conditions
7
 * of the GNU General Public License version 2.
D
David Teigland 已提交
8 9 10
 */

/*
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
 * Implements Extendible Hashing as described in:
 *   "Extendible Hashing" by Fagin, et al in
 *     __ACM Trans. on Database Systems__, Sept 1979.
 *
 *
 * Here's the layout of dirents which is essentially the same as that of ext2
 * within a single block. The field de_name_len is the number of bytes
 * actually required for the name (no null terminator). The field de_rec_len
 * is the number of bytes allocated to the dirent. The offset of the next
 * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is
 * deleted, the preceding dirent inherits its allocated space, ie
 * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained
 * by adding de_rec_len to the current dirent, this essentially causes the
 * deleted dirent to get jumped over when iterating through all the dirents.
 *
 * When deleting the first dirent in a block, there is no previous dirent so
 * the field de_ino is set to zero to designate it as deleted. When allocating
 * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the
 * first dirent has (de_ino == 0) and de_rec_len is large enough, this first
 * dirent is allocated. Otherwise it must go through all the 'used' dirents
 * searching for one in which the amount of total space minus the amount of
 * used space will provide enough space for the new dirent.
 *
 * There are two types of blocks in which dirents reside. In a stuffed dinode,
 * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of
 * the block.  In leaves, they begin at offset sizeof(struct gfs2_leaf) from the
 * beginning of the leaf block. The dirents reside in leaves when
 *
39
 * dip->i_diskflags & GFS2_DIF_EXHASH is true
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
 *
 * Otherwise, the dirents are "linear", within a single stuffed dinode block.
 *
 * When the dirents are in leaves, the actual contents of the directory file are
 * used as an array of 64-bit block pointers pointing to the leaf blocks. The
 * dirents are NOT in the directory file itself. There can be more than one
 * block pointer in the array that points to the same leaf. In fact, when a
 * directory is first converted from linear to exhash, all of the pointers
 * point to the same leaf.
 *
 * When a leaf is completely full, the size of the hash table can be
 * doubled unless it is already at the maximum size which is hard coded into
 * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,
 * but never before the maximum hash table size has been reached.
 */
D
David Teigland 已提交
55

56 57
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

D
David Teigland 已提交
58 59 60 61
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/buffer_head.h>
#include <linux/sort.h>
62
#include <linux/gfs2_ondisk.h>
63
#include <linux/crc32.h>
64
#include <linux/vmalloc.h>
D
David Teigland 已提交
65 66

#include "gfs2.h"
67
#include "incore.h"
D
David Teigland 已提交
68 69 70 71 72 73 74
#include "dir.h"
#include "glock.h"
#include "inode.h"
#include "meta_io.h"
#include "quota.h"
#include "rgrp.h"
#include "trans.h"
75
#include "bmap.h"
76
#include "util.h"
D
David Teigland 已提交
77 78 79 80

#define IS_LEAF     1 /* Hashed (leaf) directory */
#define IS_DINODE   2 /* Linear (stuffed dinode block) directory */

81 82
#define MAX_RA_BLOCKS 32 /* max read-ahead blocks */

83 84
#define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1)
#define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1))
D
David Teigland 已提交
85

86 87 88
struct qstr gfs2_qdot __read_mostly;
struct qstr gfs2_qdotdot __read_mostly;

89 90
typedef int (*gfs2_dscan_t)(const struct gfs2_dirent *dent,
			    const struct qstr *name, void *opaque);
D
David Teigland 已提交
91

92
int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block,
93
			    struct buffer_head **bhp)
94 95 96
{
	struct buffer_head *bh;

97
	bh = gfs2_meta_new(ip->i_gl, block);
98
	gfs2_trans_add_meta(ip->i_gl, bh);
99 100
	gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
	gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
101 102 103 104
	*bhp = bh;
	return 0;
}

105
static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block,
106 107 108 109
					struct buffer_head **bhp)
{
	struct buffer_head *bh;
	int error;
110

S
Steven Whitehouse 已提交
111
	error = gfs2_meta_read(ip->i_gl, block, DIO_WAIT, &bh);
112 113
	if (error)
		return error;
114
	if (gfs2_metatype_check(GFS2_SB(&ip->i_inode), bh, GFS2_METATYPE_JD)) {
115 116 117 118 119 120
		brelse(bh);
		return -EIO;
	}
	*bhp = bh;
	return 0;
}
121 122 123 124 125 126 127 128 129 130 131

static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
				  unsigned int offset, unsigned int size)
{
	struct buffer_head *dibh;
	int error;

	error = gfs2_meta_inode_buffer(ip, &dibh);
	if (error)
		return error;

132
	gfs2_trans_add_meta(ip->i_gl, dibh);
133
	memcpy(dibh->b_data + offset + sizeof(struct gfs2_dinode), buf, size);
S
Steven Whitehouse 已提交
134 135
	if (ip->i_inode.i_size < offset + size)
		i_size_write(&ip->i_inode, offset + size);
136
	ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
137
	gfs2_dinode_out(ip, dibh->b_data);
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155

	brelse(dibh);

	return size;
}



/**
 * gfs2_dir_write_data - Write directory information to the inode
 * @ip: The GFS2 inode
 * @buf: The buffer containing information to be written
 * @offset: The file offset to start writing at
 * @size: The amount of data to write
 *
 * Returns: The number of bytes correctly written or error code
 */
static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf,
156
			       u64 offset, unsigned int size)
157
{
158
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
159
	struct buffer_head *dibh;
160 161
	u64 lblock, dblock;
	u32 extlen = 0;
162 163 164
	unsigned int o;
	int copied = 0;
	int error = 0;
165
	int new = 0;
166 167 168 169 170 171

	if (!size)
		return 0;

	if (gfs2_is_stuffed(ip) &&
	    offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode))
172 173
		return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset,
					      size);
174 175 176 177 178

	if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
		return -EINVAL;

	if (gfs2_is_stuffed(ip)) {
179
		error = gfs2_unstuff_dinode(ip, NULL);
180
		if (error)
181
			return error;
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
	}

	lblock = offset;
	o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);

	while (copied < size) {
		unsigned int amount;
		struct buffer_head *bh;

		amount = size - copied;
		if (amount > sdp->sd_sb.sb_bsize - o)
			amount = sdp->sd_sb.sb_bsize - o;

		if (!extlen) {
			new = 1;
197
			error = gfs2_extent_map(&ip->i_inode, lblock, &new,
S
Steven Whitehouse 已提交
198
						&dblock, &extlen);
199 200 201 202 203 204 205
			if (error)
				goto fail;
			error = -EIO;
			if (gfs2_assert_withdraw(sdp, dblock))
				goto fail;
		}

206 207 208 209 210
		if (amount == sdp->sd_jbsize || new)
			error = gfs2_dir_get_new_buffer(ip, dblock, &bh);
		else
			error = gfs2_dir_get_existing_buffer(ip, dblock, &bh);

211 212 213
		if (error)
			goto fail;

214
		gfs2_trans_add_meta(ip->i_gl, bh);
215 216 217
		memcpy(bh->b_data + o, buf, amount);
		brelse(bh);

218
		buf += amount;
219 220 221 222 223 224 225 226 227 228 229 230 231
		copied += amount;
		lblock++;
		dblock++;
		extlen--;

		o = sizeof(struct gfs2_meta_header);
	}

out:
	error = gfs2_meta_inode_buffer(ip, &dibh);
	if (error)
		return error;

S
Steven Whitehouse 已提交
232 233
	if (ip->i_inode.i_size < offset + copied)
		i_size_write(&ip->i_inode, offset + copied);
234
	ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
235

236
	gfs2_trans_add_meta(ip->i_gl, dibh);
237
	gfs2_dinode_out(ip, dibh->b_data);
238 239 240 241 242 243 244 245 246
	brelse(dibh);

	return copied;
fail:
	if (copied)
		goto out;
	return error;
}

247 248
static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, __be64 *buf,
				 unsigned int size)
249 250 251 252 253 254
{
	struct buffer_head *dibh;
	int error;

	error = gfs2_meta_inode_buffer(ip, &dibh);
	if (!error) {
255
		memcpy(buf, dibh->b_data + sizeof(struct gfs2_dinode), size);
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
		brelse(dibh);
	}

	return (error) ? error : size;
}


/**
 * gfs2_dir_read_data - Read a data from a directory inode
 * @ip: The GFS2 Inode
 * @buf: The buffer to place result into
 * @size: Amount of data to transfer
 *
 * Returns: The amount of data actually copied or the error
 */
271 272
static int gfs2_dir_read_data(struct gfs2_inode *ip, __be64 *buf,
			      unsigned int size)
273
{
274
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
275 276
	u64 lblock, dblock;
	u32 extlen = 0;
277 278 279 280 281
	unsigned int o;
	int copied = 0;
	int error = 0;

	if (gfs2_is_stuffed(ip))
282
		return gfs2_dir_read_stuffed(ip, buf, size);
283 284 285 286

	if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
		return -EINVAL;

287
	lblock = 0;
288 289 290 291 292 293 294 295 296 297 298 299 300
	o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);

	while (copied < size) {
		unsigned int amount;
		struct buffer_head *bh;
		int new;

		amount = size - copied;
		if (amount > sdp->sd_sb.sb_bsize - o)
			amount = sdp->sd_sb.sb_bsize - o;

		if (!extlen) {
			new = 0;
301
			error = gfs2_extent_map(&ip->i_inode, lblock, &new,
S
Steven Whitehouse 已提交
302
						&dblock, &extlen);
S
Steven Whitehouse 已提交
303
			if (error || !dblock)
304
				goto fail;
S
Steven Whitehouse 已提交
305 306
			BUG_ON(extlen < 1);
			bh = gfs2_meta_ra(ip->i_gl, dblock, extlen);
307
		} else {
S
Steven Whitehouse 已提交
308
			error = gfs2_meta_read(ip->i_gl, dblock, DIO_WAIT, &bh);
309 310
			if (error)
				goto fail;
S
Steven Whitehouse 已提交
311 312 313 314 315 316 317 318
		}
		error = gfs2_metatype_check(sdp, bh, GFS2_METATYPE_JD);
		if (error) {
			brelse(bh);
			goto fail;
		}
		dblock++;
		extlen--;
319 320
		memcpy(buf, bh->b_data + o, amount);
		brelse(bh);
321
		buf += (amount/sizeof(__be64));
322 323 324 325 326 327 328 329 330 331
		copied += amount;
		lblock++;
		o = sizeof(struct gfs2_meta_header);
	}

	return copied;
fail:
	return (copied) ? copied : error;
}

332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358
/**
 * gfs2_dir_get_hash_table - Get pointer to the dir hash table
 * @ip: The inode in question
 *
 * Returns: The hash table or an error
 */

static __be64 *gfs2_dir_get_hash_table(struct gfs2_inode *ip)
{
	struct inode *inode = &ip->i_inode;
	int ret;
	u32 hsize;
	__be64 *hc;

	BUG_ON(!(ip->i_diskflags & GFS2_DIF_EXHASH));

	hc = ip->i_hash_cache;
	if (hc)
		return hc;

	hsize = 1 << ip->i_depth;
	hsize *= sizeof(__be64);
	if (hsize != i_size_read(&ip->i_inode)) {
		gfs2_consist_inode(ip);
		return ERR_PTR(-EIO);
	}

359 360 361 362
	hc = kmalloc(hsize, GFP_NOFS | __GFP_NOWARN);
	if (hc == NULL)
		hc = __vmalloc(hsize, GFP_NOFS, PAGE_KERNEL);

363 364 365
	if (hc == NULL)
		return ERR_PTR(-ENOMEM);

366
	ret = gfs2_dir_read_data(ip, hc, hsize);
367
	if (ret < 0) {
368
		kvfree(hc);
369 370 371 372
		return ERR_PTR(ret);
	}

	spin_lock(&inode->i_lock);
373
	if (likely(!ip->i_hash_cache)) {
374
		ip->i_hash_cache = hc;
375 376
		hc = NULL;
	}
377
	spin_unlock(&inode->i_lock);
378
	kvfree(hc);
379 380 381 382 383 384 385 386 387 388 389 390 391 392

	return ip->i_hash_cache;
}

/**
 * gfs2_dir_hash_inval - Invalidate dir hash
 * @ip: The directory inode
 *
 * Must be called with an exclusive glock, or during glock invalidation.
 */
void gfs2_dir_hash_inval(struct gfs2_inode *ip)
{
	__be64 *hc = ip->i_hash_cache;
	ip->i_hash_cache = NULL;
393
	kvfree(hc);
394 395
}

396 397 398 399 400
static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent)
{
	return dent->de_inum.no_addr == 0 || dent->de_inum.no_formal_ino == 0;
}

401 402 403
static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent,
				     const struct qstr *name, int ret)
{
404
	if (!gfs2_dirent_sentinel(dent) &&
405 406
	    be32_to_cpu(dent->de_hash) == name->hash &&
	    be16_to_cpu(dent->de_name_len) == name->len &&
407
	    memcmp(dent+1, name->name, name->len) == 0)
408 409 410 411 412
		return ret;
	return 0;
}

static int gfs2_dirent_find(const struct gfs2_dirent *dent,
413 414
			    const struct qstr *name,
			    void *opaque)
415 416 417 418 419
{
	return __gfs2_dirent_find(dent, name, 1);
}

static int gfs2_dirent_prev(const struct gfs2_dirent *dent,
420 421
			    const struct qstr *name,
			    void *opaque)
422 423 424 425 426 427 428
{
	return __gfs2_dirent_find(dent, name, 2);
}

/*
 * name->name holds ptr to start of block.
 * name->len holds size of block.
D
David Teigland 已提交
429
 */
430
static int gfs2_dirent_last(const struct gfs2_dirent *dent,
431 432
			    const struct qstr *name,
			    void *opaque)
433 434 435 436 437 438 439
{
	const char *start = name->name;
	const char *end = (const char *)dent + be16_to_cpu(dent->de_rec_len);
	if (name->len == (end - start))
		return 1;
	return 0;
}
D
David Teigland 已提交
440

441
static int gfs2_dirent_find_space(const struct gfs2_dirent *dent,
442 443
				  const struct qstr *name,
				  void *opaque)
D
David Teigland 已提交
444
{
445 446 447 448
	unsigned required = GFS2_DIRENT_SIZE(name->len);
	unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
	unsigned totlen = be16_to_cpu(dent->de_rec_len);

449
	if (gfs2_dirent_sentinel(dent))
B
Bob Peterson 已提交
450
		actual = 0;
J
Jan Engelhardt 已提交
451
	if (totlen - actual >= required)
452 453 454 455
		return 1;
	return 0;
}

456 457 458 459 460 461 462 463 464 465
struct dirent_gather {
	const struct gfs2_dirent **pdent;
	unsigned offset;
};

static int gfs2_dirent_gather(const struct gfs2_dirent *dent,
			      const struct qstr *name,
			      void *opaque)
{
	struct dirent_gather *g = opaque;
466
	if (!gfs2_dirent_sentinel(dent)) {
467 468 469 470 471
		g->pdent[g->offset++] = dent;
	}
	return 0;
}

472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
/*
 * Other possible things to check:
 * - Inode located within filesystem size (and on valid block)
 * - Valid directory entry type
 * Not sure how heavy-weight we want to make this... could also check
 * hash is correct for example, but that would take a lot of extra time.
 * For now the most important thing is to check that the various sizes
 * are correct.
 */
static int gfs2_check_dirent(struct gfs2_dirent *dent, unsigned int offset,
			     unsigned int size, unsigned int len, int first)
{
	const char *msg = "gfs2_dirent too small";
	if (unlikely(size < sizeof(struct gfs2_dirent)))
		goto error;
	msg = "gfs2_dirent misaligned";
	if (unlikely(offset & 0x7))
		goto error;
	msg = "gfs2_dirent points beyond end of block";
	if (unlikely(offset + size > len))
		goto error;
	msg = "zero inode number";
494
	if (unlikely(!first && gfs2_dirent_sentinel(dent)))
495 496
		goto error;
	msg = "name length is greater than space in dirent";
497
	if (!gfs2_dirent_sentinel(dent) &&
498 499 500 501 502
	    unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) >
		     size))
		goto error;
	return 0;
error:
503 504
	pr_warn("%s: %s (%s)\n",
		__func__, msg, first ? "first in block" : "not first in block");
505
	return -EIO;
D
David Teigland 已提交
506 507
}

508
static int gfs2_dirent_offset(const void *buf)
509
{
510 511
	const struct gfs2_meta_header *h = buf;
	int offset;
512 513 514

	BUG_ON(buf == NULL);

515
	switch(be32_to_cpu(h->mh_type)) {
516 517 518 519 520 521 522 523 524
	case GFS2_METATYPE_LF:
		offset = sizeof(struct gfs2_leaf);
		break;
	case GFS2_METATYPE_DI:
		offset = sizeof(struct gfs2_dinode);
		break;
	default:
		goto wrong_type;
	}
525 526
	return offset;
wrong_type:
527
	pr_warn("%s: wrong block type %u\n", __func__, be32_to_cpu(h->mh_type));
528 529 530
	return -1;
}

531
static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf,
532 533 534 535 536 537 538 539
					    unsigned int len, gfs2_dscan_t scan,
					    const struct qstr *name,
					    void *opaque)
{
	struct gfs2_dirent *dent, *prev;
	unsigned offset;
	unsigned size;
	int ret = 0;
540

541 542 543 544 545
	ret = gfs2_dirent_offset(buf);
	if (ret < 0)
		goto consist_inode;

	offset = ret;
546
	prev = NULL;
547
	dent = buf + offset;
548 549 550 551
	size = be16_to_cpu(dent->de_rec_len);
	if (gfs2_check_dirent(dent, offset, size, len, 1))
		goto consist_inode;
	do {
552
		ret = scan(dent, name, opaque);
553 554 555 556 557 558
		if (ret)
			break;
		offset += size;
		if (offset == len)
			break;
		prev = dent;
559
		dent = buf + offset;
560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577
		size = be16_to_cpu(dent->de_rec_len);
		if (gfs2_check_dirent(dent, offset, size, len, 0))
			goto consist_inode;
	} while(1);

	switch(ret) {
	case 0:
		return NULL;
	case 1:
		return dent;
	case 2:
		return prev ? prev : dent;
	default:
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
	}

consist_inode:
578
	gfs2_consist_inode(GFS2_I(inode));
579 580 581
	return ERR_PTR(-EIO);
}

582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
static int dirent_check_reclen(struct gfs2_inode *dip,
			       const struct gfs2_dirent *d, const void *end_p)
{
	const void *ptr = d;
	u16 rec_len = be16_to_cpu(d->de_rec_len);

	if (unlikely(rec_len < sizeof(struct gfs2_dirent)))
		goto broken;
	ptr += rec_len;
	if (ptr < end_p)
		return rec_len;
	if (ptr == end_p)
		return -ENOENT;
broken:
	gfs2_consist_inode(dip);
	return -EIO;
}

D
David Teigland 已提交
600 601 602 603 604 605 606 607 608 609 610 611
/**
 * dirent_next - Next dirent
 * @dip: the directory
 * @bh: The buffer
 * @dent: Pointer to list of dirents
 *
 * Returns: 0 on success, error code otherwise
 */

static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,
		       struct gfs2_dirent **dent)
{
612 613 614
	struct gfs2_dirent *cur = *dent, *tmp;
	char *bh_end = bh->b_data + bh->b_size;
	int ret;
D
David Teigland 已提交
615

616 617 618
	ret = dirent_check_reclen(dip, cur, bh_end);
	if (ret < 0)
		return ret;
619

620 621 622 623
	tmp = (void *)cur + ret;
	ret = dirent_check_reclen(dip, tmp, bh_end);
	if (ret == -EIO)
		return ret;
624

D
David Teigland 已提交
625
        /* Only the first dent could ever have de_inum.no_addr == 0 */
626
	if (gfs2_dirent_sentinel(tmp)) {
D
David Teigland 已提交
627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646
		gfs2_consist_inode(dip);
		return -EIO;
	}

	*dent = tmp;
	return 0;
}

/**
 * dirent_del - Delete a dirent
 * @dip: The GFS2 inode
 * @bh: The buffer
 * @prev: The previous dirent
 * @cur: The current dirent
 *
 */

static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,
		       struct gfs2_dirent *prev, struct gfs2_dirent *cur)
{
647
	u16 cur_rec_len, prev_rec_len;
D
David Teigland 已提交
648

649
	if (gfs2_dirent_sentinel(cur)) {
D
David Teigland 已提交
650 651 652 653
		gfs2_consist_inode(dip);
		return;
	}

654
	gfs2_trans_add_meta(dip->i_gl, bh);
D
David Teigland 已提交
655 656 657 658 659 660

	/* If there is no prev entry, this is the first entry in the block.
	   The de_rec_len is already as big as it needs to be.  Just zero
	   out the inode number and return.  */

	if (!prev) {
661 662
		cur->de_inum.no_addr = 0;
		cur->de_inum.no_formal_ino = 0;
D
David Teigland 已提交
663 664 665 666 667
		return;
	}

	/*  Combine this dentry with the previous one.  */

668 669
	prev_rec_len = be16_to_cpu(prev->de_rec_len);
	cur_rec_len = be16_to_cpu(cur->de_rec_len);
D
David Teigland 已提交
670 671 672 673 674 675 676

	if ((char *)prev + prev_rec_len != (char *)cur)
		gfs2_consist_inode(dip);
	if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)
		gfs2_consist_inode(dip);

	prev_rec_len += cur_rec_len;
677
	prev->de_rec_len = cpu_to_be16(prev_rec_len);
D
David Teigland 已提交
678 679
}

680 681 682
/*
 * Takes a dent from which to grab space as an argument. Returns the
 * newly created dent.
D
David Teigland 已提交
683
 */
684 685 686 687
static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,
					    struct gfs2_dirent *dent,
					    const struct qstr *name,
					    struct buffer_head *bh)
D
David Teigland 已提交
688
{
689
	struct gfs2_inode *ip = GFS2_I(inode);
690 691 692
	struct gfs2_dirent *ndent;
	unsigned offset = 0, totlen;

693
	if (!gfs2_dirent_sentinel(dent))
694 695 696
		offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
	totlen = be16_to_cpu(dent->de_rec_len);
	BUG_ON(offset + name->len > totlen);
697
	gfs2_trans_add_meta(ip->i_gl, bh);
698 699 700 701
	ndent = (struct gfs2_dirent *)((char *)dent + offset);
	dent->de_rec_len = cpu_to_be16(offset);
	gfs2_qstr2dirent(name, totlen - offset, ndent);
	return ndent;
D
David Teigland 已提交
702 703
}

704 705 706
static struct gfs2_dirent *gfs2_dirent_alloc(struct inode *inode,
					     struct buffer_head *bh,
					     const struct qstr *name)
D
David Teigland 已提交
707 708
{
	struct gfs2_dirent *dent;
709
	dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
710
				gfs2_dirent_find_space, name, NULL);
711 712 713
	if (!dent || IS_ERR(dent))
		return dent;
	return gfs2_init_dirent(inode, dent, name, bh);
D
David Teigland 已提交
714 715
}

716
static int get_leaf(struct gfs2_inode *dip, u64 leaf_no,
D
David Teigland 已提交
717 718 719 720
		    struct buffer_head **bhp)
{
	int error;

S
Steven Whitehouse 已提交
721
	error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_WAIT, bhp);
722
	if (!error && gfs2_metatype_check(GFS2_SB(&dip->i_inode), *bhp, GFS2_METATYPE_LF)) {
723
		/* pr_info("block num=%llu\n", leaf_no); */
D
David Teigland 已提交
724
		error = -EIO;
725
	}
D
David Teigland 已提交
726 727 728 729 730 731 732 733 734 735 736 737 738

	return error;
}

/**
 * get_leaf_nr - Get a leaf number associated with the index
 * @dip: The GFS2 inode
 * @index:
 * @leaf_out:
 *
 * Returns: 0 on success, error code otherwise
 */

739 740
static int get_leaf_nr(struct gfs2_inode *dip, u32 index,
		       u64 *leaf_out)
D
David Teigland 已提交
741
{
742
	__be64 *hash;
D
David Teigland 已提交
743

744 745 746 747
	hash = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(hash))
		return PTR_ERR(hash);
	*leaf_out = be64_to_cpu(*(hash + index));
D
David Teigland 已提交
748 749 750
	return 0;
}

751
static int get_first_leaf(struct gfs2_inode *dip, u32 index,
D
David Teigland 已提交
752 753
			  struct buffer_head **bh_out)
{
754
	u64 leaf_no;
D
David Teigland 已提交
755 756 757 758 759 760 761 762 763
	int error;

	error = get_leaf_nr(dip, index, &leaf_no);
	if (!error)
		error = get_leaf(dip, leaf_no, bh_out);

	return error;
}

764 765 766 767
static struct gfs2_dirent *gfs2_dirent_search(struct inode *inode,
					      const struct qstr *name,
					      gfs2_dscan_t scan,
					      struct buffer_head **pbh)
D
David Teigland 已提交
768
{
769 770
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
771
	struct gfs2_inode *ip = GFS2_I(inode);
D
David Teigland 已提交
772 773
	int error;

774
	if (ip->i_diskflags & GFS2_DIF_EXHASH) {
775
		struct gfs2_leaf *leaf;
776
		unsigned hsize = 1 << ip->i_depth;
777 778
		unsigned index;
		u64 ln;
S
Steven Whitehouse 已提交
779
		if (hsize * sizeof(u64) != i_size_read(inode)) {
780 781 782
			gfs2_consist_inode(ip);
			return ERR_PTR(-EIO);
		}
783

784
		index = name->hash >> (32 - ip->i_depth);
785 786 787 788 789
		error = get_first_leaf(ip, index, &bh);
		if (error)
			return ERR_PTR(error);
		do {
			dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
790
						scan, name, NULL);
791 792 793 794
			if (dent)
				goto got_dent;
			leaf = (struct gfs2_leaf *)bh->b_data;
			ln = be64_to_cpu(leaf->lf_next);
795
			brelse(bh);
796 797
			if (!ln)
				break;
798

799 800
			error = get_leaf(ip, ln, &bh);
		} while(!error);
D
David Teigland 已提交
801

802
		return error ? ERR_PTR(error) : NULL;
D
David Teigland 已提交
803 804
	}

805

806 807 808
	error = gfs2_meta_inode_buffer(ip, &bh);
	if (error)
		return ERR_PTR(error);
809
	dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, scan, name, NULL);
810
got_dent:
811
	if (unlikely(dent == NULL || IS_ERR(dent))) {
812 813 814
		brelse(bh);
		bh = NULL;
	}
815 816 817
	*pbh = bh;
	return dent;
}
D
David Teigland 已提交
818

819 820
static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth)
{
821
	struct gfs2_inode *ip = GFS2_I(inode);
822
	unsigned int n = 1;
823 824 825
	u64 bn;
	int error;
	struct buffer_head *bh;
826 827
	struct gfs2_leaf *leaf;
	struct gfs2_dirent *dent;
828
	struct qstr name = { .name = "" };
829
	struct timespec tv = CURRENT_TIME;
830

831
	error = gfs2_alloc_blocks(ip, &bn, &n, 0, NULL);
832 833 834
	if (error)
		return NULL;
	bh = gfs2_meta_new(ip->i_gl, bn);
835 836
	if (!bh)
		return NULL;
837

838
	gfs2_trans_add_unrevoke(GFS2_SB(inode), bn, 1);
839
	gfs2_trans_add_meta(ip->i_gl, bh);
840 841 842
	gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
	leaf = (struct gfs2_leaf *)bh->b_data;
	leaf->lf_depth = cpu_to_be16(depth);
843
	leaf->lf_entries = 0;
844
	leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
845
	leaf->lf_next = 0;
846 847 848 849 850
	leaf->lf_inode = cpu_to_be64(ip->i_no_addr);
	leaf->lf_dist = cpu_to_be32(1);
	leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
	leaf->lf_sec = cpu_to_be64(tv.tv_sec);
	memset(leaf->lf_reserved2, 0, sizeof(leaf->lf_reserved2));
851
	dent = (struct gfs2_dirent *)(leaf+1);
852
	gfs2_qstr2dirent(&name, bh->b_size - sizeof(struct gfs2_leaf), dent);
853 854
	*pbh = bh;
	return leaf;
D
David Teigland 已提交
855 856 857 858 859 860 861 862 863
}

/**
 * dir_make_exhash - Convert a stuffed directory into an ExHash directory
 * @dip: The GFS2 inode
 *
 * Returns: 0 on success, error code otherwise
 */

864
static int dir_make_exhash(struct inode *inode)
D
David Teigland 已提交
865
{
866 867
	struct gfs2_inode *dip = GFS2_I(inode);
	struct gfs2_sbd *sdp = GFS2_SB(inode);
D
David Teigland 已提交
868
	struct gfs2_dirent *dent;
869
	struct qstr args;
D
David Teigland 已提交
870 871 872
	struct buffer_head *bh, *dibh;
	struct gfs2_leaf *leaf;
	int y;
873
	u32 x;
A
Al Viro 已提交
874 875
	__be64 *lp;
	u64 bn;
D
David Teigland 已提交
876 877 878 879 880 881 882 883
	int error;

	error = gfs2_meta_inode_buffer(dip, &dibh);
	if (error)
		return error;

	/*  Turn over a new leaf  */

884 885 886 887
	leaf = new_leaf(inode, &bh, 0);
	if (!leaf)
		return -ENOSPC;
	bn = bh->b_blocknr;
D
David Teigland 已提交
888

889 890
	gfs2_assert(sdp, dip->i_entries < (1 << 16));
	leaf->lf_entries = cpu_to_be16(dip->i_entries);
D
David Teigland 已提交
891 892 893 894 895 896 897 898 899

	/*  Copy dirents  */

	gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh,
			     sizeof(struct gfs2_dinode));

	/*  Find last entry  */

	x = 0;
900 901 902
	args.len = bh->b_size - sizeof(struct gfs2_dinode) +
		   sizeof(struct gfs2_leaf);
	args.name = bh->b_data;
903
	dent = gfs2_dirent_scan(&dip->i_inode, bh->b_data, bh->b_size,
904
				gfs2_dirent_last, &args, NULL);
905 906 907 908 909 910 911 912 913
	if (!dent) {
		brelse(bh);
		brelse(dibh);
		return -EIO;
	}
	if (IS_ERR(dent)) {
		brelse(bh);
		brelse(dibh);
		return PTR_ERR(dent);
D
David Teigland 已提交
914 915 916 917 918
	}

	/*  Adjust the last dirent's record length
	   (Remember that dent still points to the last entry.)  */

919
	dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) +
D
David Teigland 已提交
920
		sizeof(struct gfs2_dinode) -
921
		sizeof(struct gfs2_leaf));
D
David Teigland 已提交
922 923 924 925 926 927

	brelse(bh);

	/*  We're done with the new leaf block, now setup the new
	    hash table.  */

928
	gfs2_trans_add_meta(dip->i_gl, dibh);
D
David Teigland 已提交
929 930
	gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode));

A
Al Viro 已提交
931
	lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode));
D
David Teigland 已提交
932 933 934 935

	for (x = sdp->sd_hash_ptrs; x--; lp++)
		*lp = cpu_to_be64(bn);

S
Steven Whitehouse 已提交
936
	i_size_write(inode, sdp->sd_sb.sb_bsize / 2);
937
	gfs2_add_inode_blocks(&dip->i_inode, 1);
938
	dip->i_diskflags |= GFS2_DIF_EXHASH;
D
David Teigland 已提交
939 940

	for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ;
941
	dip->i_depth = y;
D
David Teigland 已提交
942

943
	gfs2_dinode_out(dip, dibh->b_data);
D
David Teigland 已提交
944 945 946 947 948 949 950 951 952 953 954 955 956 957 958

	brelse(dibh);

	return 0;
}

/**
 * dir_split_leaf - Split a leaf block into two
 * @dip: The GFS2 inode
 * @index:
 * @leaf_no:
 *
 * Returns: 0 on success, error code on failure
 */

959
static int dir_split_leaf(struct inode *inode, const struct qstr *name)
D
David Teigland 已提交
960
{
961
	struct gfs2_inode *dip = GFS2_I(inode);
D
David Teigland 已提交
962 963
	struct buffer_head *nbh, *obh, *dibh;
	struct gfs2_leaf *nleaf, *oleaf;
964
	struct gfs2_dirent *dent = NULL, *prev = NULL, *next = NULL, *new;
965
	u32 start, len, half_len, divider;
A
Al Viro 已提交
966 967
	u64 bn, leaf_no;
	__be64 *lp;
968
	u32 index;
D
David Teigland 已提交
969 970 971
	int x, moved = 0;
	int error;

972
	index = name->hash >> (32 - dip->i_depth);
973 974 975
	error = get_leaf_nr(dip, index, &leaf_no);
	if (error)
		return error;
D
David Teigland 已提交
976 977 978 979

	/*  Get the old leaf block  */
	error = get_leaf(dip, leaf_no, &obh);
	if (error)
980
		return error;
D
David Teigland 已提交
981 982

	oleaf = (struct gfs2_leaf *)obh->b_data;
983
	if (dip->i_depth == be16_to_cpu(oleaf->lf_depth)) {
984 985 986 987
		brelse(obh);
		return 1; /* can't split */
	}

988
	gfs2_trans_add_meta(dip->i_gl, obh);
D
David Teigland 已提交
989

990 991 992 993 994 995
	nleaf = new_leaf(inode, &nbh, be16_to_cpu(oleaf->lf_depth) + 1);
	if (!nleaf) {
		brelse(obh);
		return -ENOSPC;
	}
	bn = nbh->b_blocknr;
D
David Teigland 已提交
996

997
	/*  Compute the start and len of leaf pointers in the hash table.  */
998
	len = 1 << (dip->i_depth - be16_to_cpu(oleaf->lf_depth));
D
David Teigland 已提交
999 1000
	half_len = len >> 1;
	if (!half_len) {
1001 1002
		pr_warn("i_depth %u lf_depth %u index %u\n",
			dip->i_depth, be16_to_cpu(oleaf->lf_depth), index);
D
David Teigland 已提交
1003 1004 1005 1006 1007 1008 1009 1010 1011 1012
		gfs2_consist_inode(dip);
		error = -EIO;
		goto fail_brelse;
	}

	start = (index & ~(len - 1));

	/* Change the pointers.
	   Don't bother distinguishing stuffed from non-stuffed.
	   This code is complicated enough already. */
1013 1014 1015 1016 1017 1018
	lp = kmalloc(half_len * sizeof(__be64), GFP_NOFS);
	if (!lp) {
		error = -ENOMEM;
		goto fail_brelse;
	}

D
David Teigland 已提交
1019 1020 1021 1022
	/*  Change the pointers  */
	for (x = 0; x < half_len; x++)
		lp[x] = cpu_to_be64(bn);

1023 1024
	gfs2_dir_hash_inval(dip);

1025 1026 1027
	error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(u64),
				    half_len * sizeof(u64));
	if (error != half_len * sizeof(u64)) {
D
David Teigland 已提交
1028 1029 1030 1031 1032 1033 1034 1035
		if (error >= 0)
			error = -EIO;
		goto fail_lpfree;
	}

	kfree(lp);

	/*  Compute the divider  */
1036
	divider = (start + half_len) << (32 - dip->i_depth);
D
David Teigland 已提交
1037 1038

	/*  Copy the entries  */
1039
	dent = (struct gfs2_dirent *)(obh->b_data + sizeof(struct gfs2_leaf));
D
David Teigland 已提交
1040 1041 1042 1043 1044 1045

	do {
		next = dent;
		if (dirent_next(dip, obh, &next))
			next = NULL;

1046
		if (!gfs2_dirent_sentinel(dent) &&
D
David Teigland 已提交
1047
		    be32_to_cpu(dent->de_hash) < divider) {
1048 1049 1050 1051
			struct qstr str;
			str.name = (char*)(dent+1);
			str.len = be16_to_cpu(dent->de_name_len);
			str.hash = be32_to_cpu(dent->de_hash);
1052
			new = gfs2_dirent_alloc(inode, nbh, &str);
1053 1054 1055 1056
			if (IS_ERR(new)) {
				error = PTR_ERR(new);
				break;
			}
D
David Teigland 已提交
1057 1058 1059

			new->de_inum = dent->de_inum; /* No endian worries */
			new->de_type = dent->de_type; /* No endian worries */
M
Marcin Slusarz 已提交
1060
			be16_add_cpu(&nleaf->lf_entries, 1);
D
David Teigland 已提交
1061 1062 1063 1064 1065

			dirent_del(dip, obh, prev, dent);

			if (!oleaf->lf_entries)
				gfs2_consist_inode(dip);
M
Marcin Slusarz 已提交
1066
			be16_add_cpu(&oleaf->lf_entries, -1);
D
David Teigland 已提交
1067 1068 1069 1070 1071

			if (!prev)
				prev = dent;

			moved = 1;
1072
		} else {
D
David Teigland 已提交
1073
			prev = dent;
1074
		}
D
David Teigland 已提交
1075
		dent = next;
1076
	} while (dent);
D
David Teigland 已提交
1077

1078
	oleaf->lf_depth = nleaf->lf_depth;
D
David Teigland 已提交
1079 1080

	error = gfs2_meta_inode_buffer(dip, &dibh);
1081
	if (!gfs2_assert_withdraw(GFS2_SB(&dip->i_inode), !error)) {
1082
		gfs2_trans_add_meta(dip->i_gl, dibh);
1083
		gfs2_add_inode_blocks(&dip->i_inode, 1);
1084
		gfs2_dinode_out(dip, dibh->b_data);
D
David Teigland 已提交
1085 1086 1087 1088 1089 1090 1091 1092
		brelse(dibh);
	}

	brelse(obh);
	brelse(nbh);

	return error;

1093
fail_lpfree:
D
David Teigland 已提交
1094 1095
	kfree(lp);

1096
fail_brelse:
D
David Teigland 已提交
1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111
	brelse(obh);
	brelse(nbh);
	return error;
}

/**
 * dir_double_exhash - Double size of ExHash table
 * @dip: The GFS2 dinode
 *
 * Returns: 0 on success, error code on failure
 */

static int dir_double_exhash(struct gfs2_inode *dip)
{
	struct buffer_head *dibh;
1112
	u32 hsize;
1113 1114 1115
	u32 hsize_bytes;
	__be64 *hc;
	__be64 *hc2, *h;
D
David Teigland 已提交
1116 1117 1118
	int x;
	int error = 0;

1119
	hsize = 1 << dip->i_depth;
1120
	hsize_bytes = hsize * sizeof(__be64);
D
David Teigland 已提交
1121

1122 1123 1124
	hc = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(hc))
		return PTR_ERR(hc);
D
David Teigland 已提交
1125

1126
	hc2 = kmalloc(hsize_bytes * 2, GFP_NOFS | __GFP_NOWARN);
1127 1128 1129
	if (hc2 == NULL)
		hc2 = __vmalloc(hsize_bytes * 2, GFP_NOFS, PAGE_KERNEL);

1130
	if (!hc2)
1131
		return -ENOMEM;
D
David Teigland 已提交
1132

1133
	h = hc2;
1134 1135 1136
	error = gfs2_meta_inode_buffer(dip, &dibh);
	if (error)
		goto out_kfree;
D
David Teigland 已提交
1137

1138 1139 1140 1141
	for (x = 0; x < hsize; x++) {
		*h++ = *hc;
		*h++ = *hc;
		hc++;
D
David Teigland 已提交
1142 1143
	}

1144 1145 1146
	error = gfs2_dir_write_data(dip, (char *)hc2, 0, hsize_bytes * 2);
	if (error != (hsize_bytes * 2))
		goto fail;
D
David Teigland 已提交
1147

1148 1149 1150 1151 1152 1153
	gfs2_dir_hash_inval(dip);
	dip->i_hash_cache = hc2;
	dip->i_depth++;
	gfs2_dinode_out(dip, dibh->b_data);
	brelse(dibh);
	return 0;
D
David Teigland 已提交
1154

1155
fail:
1156 1157 1158 1159 1160 1161
	/* Replace original hash table & size */
	gfs2_dir_write_data(dip, (char *)hc, 0, hsize_bytes);
	i_size_write(&dip->i_inode, hsize_bytes);
	gfs2_dinode_out(dip, dibh->b_data);
	brelse(dibh);
out_kfree:
1162
	kvfree(hc2);
D
David Teigland 已提交
1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178
	return error;
}

/**
 * compare_dents - compare directory entries by hash value
 * @a: first dent
 * @b: second dent
 *
 * When comparing the hash entries of @a to @b:
 *   gt: returns 1
 *   lt: returns -1
 *   eq: returns 0
 */

static int compare_dents(const void *a, const void *b)
{
1179
	const struct gfs2_dirent *dent_a, *dent_b;
1180
	u32 hash_a, hash_b;
D
David Teigland 已提交
1181 1182
	int ret = 0;

1183
	dent_a = *(const struct gfs2_dirent **)a;
1184
	hash_a = be32_to_cpu(dent_a->de_hash);
D
David Teigland 已提交
1185

1186
	dent_b = *(const struct gfs2_dirent **)b;
1187
	hash_b = be32_to_cpu(dent_b->de_hash);
D
David Teigland 已提交
1188 1189 1190 1191 1192 1193

	if (hash_a > hash_b)
		ret = 1;
	else if (hash_a < hash_b)
		ret = -1;
	else {
1194 1195
		unsigned int len_a = be16_to_cpu(dent_a->de_name_len);
		unsigned int len_b = be16_to_cpu(dent_b->de_name_len);
D
David Teigland 已提交
1196 1197 1198 1199 1200 1201

		if (len_a > len_b)
			ret = 1;
		else if (len_a < len_b)
			ret = -1;
		else
1202
			ret = memcmp(dent_a + 1, dent_b + 1, len_a);
D
David Teigland 已提交
1203 1204 1205 1206 1207 1208 1209 1210
	}

	return ret;
}

/**
 * do_filldir_main - read out directory entries
 * @dip: The GFS2 inode
A
Al Viro 已提交
1211
 * @ctx: what to feed the entries to
D
David Teigland 已提交
1212 1213 1214 1215 1216 1217 1218 1219 1220
 * @darr: an array of struct gfs2_dirent pointers to read
 * @entries: the number of entries in darr
 * @copied: pointer to int that's non-zero if a entry has been copied out
 *
 * Jump through some hoops to make sure that if there are hash collsions,
 * they are read out at the beginning of a buffer.  We want to minimize
 * the possibility that they will fall into different readdir buffers or
 * that someone will want to seek to that location.
 *
A
Al Viro 已提交
1221
 * Returns: errno, >0 if the actor tells you to stop
D
David Teigland 已提交
1222 1223
 */

A
Al Viro 已提交
1224
static int do_filldir_main(struct gfs2_inode *dip, struct dir_context *ctx,
1225
			   const struct gfs2_dirent **darr, u32 entries,
D
David Teigland 已提交
1226 1227
			   int *copied)
{
1228
	const struct gfs2_dirent *dent, *dent_next;
1229
	u64 off, off_next;
D
David Teigland 已提交
1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247
	unsigned int x, y;
	int run = 0;

	sort(darr, entries, sizeof(struct gfs2_dirent *), compare_dents, NULL);

	dent_next = darr[0];
	off_next = be32_to_cpu(dent_next->de_hash);
	off_next = gfs2_disk_hash2offset(off_next);

	for (x = 0, y = 1; x < entries; x++, y++) {
		dent = dent_next;
		off = off_next;

		if (y < entries) {
			dent_next = darr[y];
			off_next = be32_to_cpu(dent_next->de_hash);
			off_next = gfs2_disk_hash2offset(off_next);

A
Al Viro 已提交
1248
			if (off < ctx->pos)
D
David Teigland 已提交
1249
				continue;
A
Al Viro 已提交
1250
			ctx->pos = off;
D
David Teigland 已提交
1251 1252 1253 1254 1255 1256 1257 1258

			if (off_next == off) {
				if (*copied && !run)
					return 1;
				run = 1;
			} else
				run = 0;
		} else {
A
Al Viro 已提交
1259
			if (off < ctx->pos)
D
David Teigland 已提交
1260
				continue;
A
Al Viro 已提交
1261
			ctx->pos = off;
D
David Teigland 已提交
1262 1263
		}

A
Al Viro 已提交
1264
		if (!dir_emit(ctx, (const char *)(dent + 1),
1265
				be16_to_cpu(dent->de_name_len),
A
Al Viro 已提交
1266 1267
				be64_to_cpu(dent->de_inum.no_addr),
				be16_to_cpu(dent->de_type)))
D
David Teigland 已提交
1268 1269 1270 1271 1272
			return 1;

		*copied = 1;
	}

A
Al Viro 已提交
1273
	/* Increment the ctx->pos by one, so the next time we come into the
D
David Teigland 已提交
1274 1275 1276
	   do_filldir fxn, we get the next entry instead of the last one in the
	   current leaf */

A
Al Viro 已提交
1277
	ctx->pos++;
D
David Teigland 已提交
1278 1279 1280 1281

	return 0;
}

1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
static void *gfs2_alloc_sort_buffer(unsigned size)
{
	void *ptr = NULL;

	if (size < KMALLOC_MAX_SIZE)
		ptr = kmalloc(size, GFP_NOFS | __GFP_NOWARN);
	if (!ptr)
		ptr = __vmalloc(size, GFP_NOFS, PAGE_KERNEL);
	return ptr;
}

A
Al Viro 已提交
1293 1294
static int gfs2_dir_read_leaf(struct inode *inode, struct dir_context *ctx,
			      int *copied, unsigned *depth,
1295
			      u64 leaf_no)
D
David Teigland 已提交
1296
{
1297
	struct gfs2_inode *ip = GFS2_I(inode);
1298
	struct gfs2_sbd *sdp = GFS2_SB(inode);
1299 1300
	struct buffer_head *bh;
	struct gfs2_leaf *lf;
1301
	unsigned entries = 0, entries2 = 0;
1302 1303 1304 1305 1306 1307 1308
	unsigned leaves = 0;
	const struct gfs2_dirent **darr, *dent;
	struct dirent_gather g;
	struct buffer_head **larr;
	int leaf = 0;
	int error, i;
	u64 lfn = leaf_no;
D
David Teigland 已提交
1309 1310

	do {
1311
		error = get_leaf(ip, lfn, &bh);
D
David Teigland 已提交
1312
		if (error)
1313 1314 1315 1316 1317 1318 1319 1320 1321
			goto out;
		lf = (struct gfs2_leaf *)bh->b_data;
		if (leaves == 0)
			*depth = be16_to_cpu(lf->lf_depth);
		entries += be16_to_cpu(lf->lf_entries);
		leaves++;
		lfn = be64_to_cpu(lf->lf_next);
		brelse(bh);
	} while(lfn);
D
David Teigland 已提交
1322 1323 1324 1325

	if (!entries)
		return 0;

1326
	error = -ENOMEM;
1327 1328 1329 1330 1331 1332
	/*
	 * The extra 99 entries are not normally used, but are a buffer
	 * zone in case the number of entries in the leaf is corrupt.
	 * 99 is the maximum number of entries that can fit in a single
	 * leaf block.
	 */
1333
	larr = gfs2_alloc_sort_buffer((leaves + entries + 99) * sizeof(void *));
1334 1335 1336 1337 1338 1339
	if (!larr)
		goto out;
	darr = (const struct gfs2_dirent **)(larr + leaves);
	g.pdent = darr;
	g.offset = 0;
	lfn = leaf_no;
D
David Teigland 已提交
1340

1341 1342
	do {
		error = get_leaf(ip, lfn, &bh);
D
David Teigland 已提交
1343
		if (error)
1344
			goto out_free;
1345 1346 1347
		lf = (struct gfs2_leaf *)bh->b_data;
		lfn = be64_to_cpu(lf->lf_next);
		if (lf->lf_entries) {
1348
			entries2 += be16_to_cpu(lf->lf_entries);
1349 1350 1351
			dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
						gfs2_dirent_gather, NULL, &g);
			error = PTR_ERR(dent);
1352
			if (IS_ERR(dent))
1353
				goto out_free;
1354
			if (entries2 != g.offset) {
1355 1356 1357 1358 1359
				fs_warn(sdp, "Number of entries corrupt in dir "
						"leaf %llu, entries2 (%u) != "
						"g.offset (%u)\n",
					(unsigned long long)bh->b_blocknr,
					entries2, g.offset);
1360 1361
					
				error = -EIO;
1362
				goto out_free;
1363 1364 1365
			}
			error = 0;
			larr[leaf++] = bh;
D
David Teigland 已提交
1366
		} else {
1367
			brelse(bh);
D
David Teigland 已提交
1368
		}
1369
	} while(lfn);
D
David Teigland 已提交
1370

1371
	BUG_ON(entries2 != entries);
A
Al Viro 已提交
1372
	error = do_filldir_main(ip, ctx, darr, entries, copied);
1373
out_free:
1374 1375
	for(i = 0; i < leaf; i++)
		brelse(larr[i]);
1376
	kvfree(larr);
1377
out:
D
David Teigland 已提交
1378 1379 1380
	return error;
}

1381 1382
/**
 * gfs2_dir_readahead - Issue read-ahead requests for leaf blocks.
1383 1384 1385 1386
 *
 * Note: we can't calculate each index like dir_e_read can because we don't
 * have the leaf, and therefore we don't have the depth, and therefore we
 * don't have the length. So we have to just read enough ahead to make up
1387 1388
 * for the loss of information.
 */
1389 1390 1391 1392 1393 1394 1395 1396 1397 1398
static void gfs2_dir_readahead(struct inode *inode, unsigned hsize, u32 index,
			       struct file_ra_state *f_ra)
{
	struct gfs2_inode *ip = GFS2_I(inode);
	struct gfs2_glock *gl = ip->i_gl;
	struct buffer_head *bh;
	u64 blocknr = 0, last;
	unsigned count;

	/* First check if we've already read-ahead for the whole range. */
1399
	if (index + MAX_RA_BLOCKS < f_ra->start)
1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426
		return;

	f_ra->start = max((pgoff_t)index, f_ra->start);
	for (count = 0; count < MAX_RA_BLOCKS; count++) {
		if (f_ra->start >= hsize) /* if exceeded the hash table */
			break;

		last = blocknr;
		blocknr = be64_to_cpu(ip->i_hash_cache[f_ra->start]);
		f_ra->start++;
		if (blocknr == last)
			continue;

		bh = gfs2_getbuf(gl, blocknr, 1);
		if (trylock_buffer(bh)) {
			if (buffer_uptodate(bh)) {
				unlock_buffer(bh);
				brelse(bh);
				continue;
			}
			bh->b_end_io = end_buffer_read_sync;
			submit_bh(READA | REQ_META, bh);
			continue;
		}
		brelse(bh);
	}
}
1427

D
David Teigland 已提交
1428
/**
1429 1430
 * dir_e_read - Reads the entries from a directory into a filldir buffer
 * @dip: dinode pointer
A
Al Viro 已提交
1431
 * @ctx: actor to feed the entries to
D
David Teigland 已提交
1432
 *
1433
 * Returns: errno
D
David Teigland 已提交
1434 1435
 */

A
Al Viro 已提交
1436 1437
static int dir_e_read(struct inode *inode, struct dir_context *ctx,
		      struct file_ra_state *f_ra)
D
David Teigland 已提交
1438
{
1439
	struct gfs2_inode *dip = GFS2_I(inode);
1440 1441
	u32 hsize, len = 0;
	u32 hash, index;
A
Al Viro 已提交
1442
	__be64 *lp;
1443 1444
	int copied = 0;
	int error = 0;
1445
	unsigned depth = 0;
D
David Teigland 已提交
1446

1447
	hsize = 1 << dip->i_depth;
A
Al Viro 已提交
1448
	hash = gfs2_dir_offset2hash(ctx->pos);
1449
	index = hash >> (32 - dip->i_depth);
D
David Teigland 已提交
1450

1451
	if (dip->i_hash_cache == NULL)
1452
		f_ra->start = 0;
1453 1454 1455
	lp = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(lp))
		return PTR_ERR(lp);
D
David Teigland 已提交
1456

1457 1458
	gfs2_dir_readahead(inode, hsize, index, f_ra);

D
David Teigland 已提交
1459
	while (index < hsize) {
A
Al Viro 已提交
1460
		error = gfs2_dir_read_leaf(inode, ctx,
1461
					   &copied, &depth,
1462
					   be64_to_cpu(lp[index]));
D
David Teigland 已提交
1463
		if (error)
1464
			break;
D
David Teigland 已提交
1465

1466
		len = 1 << (dip->i_depth - depth);
D
David Teigland 已提交
1467 1468 1469
		index = (index & ~(len - 1)) + len;
	}

1470 1471
	if (error > 0)
		error = 0;
D
David Teigland 已提交
1472 1473 1474
	return error;
}

A
Al Viro 已提交
1475 1476
int gfs2_dir_read(struct inode *inode, struct dir_context *ctx,
		  struct file_ra_state *f_ra)
D
David Teigland 已提交
1477
{
1478
	struct gfs2_inode *dip = GFS2_I(inode);
1479
	struct gfs2_sbd *sdp = GFS2_SB(inode);
1480 1481
	struct dirent_gather g;
	const struct gfs2_dirent **darr, *dent;
D
David Teigland 已提交
1482 1483 1484 1485
	struct buffer_head *dibh;
	int copied = 0;
	int error;

1486
	if (!dip->i_entries)
1487 1488
		return 0;

1489
	if (dip->i_diskflags & GFS2_DIF_EXHASH)
A
Al Viro 已提交
1490
		return dir_e_read(inode, ctx, f_ra);
1491

D
David Teigland 已提交
1492 1493 1494 1495 1496 1497 1498 1499 1500
	if (!gfs2_is_stuffed(dip)) {
		gfs2_consist_inode(dip);
		return -EIO;
	}

	error = gfs2_meta_inode_buffer(dip, &dibh);
	if (error)
		return error;

1501
	error = -ENOMEM;
1502
	/* 96 is max number of dirents which can be stuffed into an inode */
J
Josef Bacik 已提交
1503
	darr = kmalloc(96 * sizeof(struct gfs2_dirent *), GFP_NOFS);
1504 1505 1506 1507 1508 1509 1510 1511 1512
	if (darr) {
		g.pdent = darr;
		g.offset = 0;
		dent = gfs2_dirent_scan(inode, dibh->b_data, dibh->b_size,
					gfs2_dirent_gather, NULL, &g);
		if (IS_ERR(dent)) {
			error = PTR_ERR(dent);
			goto out;
		}
1513
		if (dip->i_entries != g.offset) {
1514
			fs_warn(sdp, "Number of entries corrupt in dir %llu, "
1515
				"ip->i_entries (%u) != g.offset (%u)\n",
1516
				(unsigned long long)dip->i_no_addr,
1517
				dip->i_entries,
1518 1519 1520 1521
				g.offset);
			error = -EIO;
			goto out;
		}
A
Al Viro 已提交
1522
		error = do_filldir_main(dip, ctx, darr,
1523
					dip->i_entries, &copied);
1524 1525 1526 1527
out:
		kfree(darr);
	}

D
David Teigland 已提交
1528 1529 1530 1531 1532 1533 1534 1535 1536 1537
	if (error > 0)
		error = 0;

	brelse(dibh);

	return error;
}

/**
 * gfs2_dir_search - Search a directory
1538 1539 1540
 * @dip: The GFS2 dir inode
 * @name: The name we are looking up
 * @fail_on_exist: Fail if the name exists rather than looking it up
D
David Teigland 已提交
1541 1542 1543 1544 1545 1546 1547
 *
 * This routine searches a directory for a file or another directory.
 * Assumes a glock is held on dip.
 *
 * Returns: errno
 */

1548 1549
struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name,
			      bool fail_on_exist)
D
David Teigland 已提交
1550
{
1551 1552
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
1553 1554
	u64 addr, formal_ino;
	u16 dtype;
1555 1556 1557 1558

	dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
	if (dent) {
		if (IS_ERR(dent))
1559
			return ERR_CAST(dent);
1560 1561 1562
		dtype = be16_to_cpu(dent->de_type);
		addr = be64_to_cpu(dent->de_inum.no_addr);
		formal_ino = be64_to_cpu(dent->de_inum.no_formal_ino);
1563
		brelse(bh);
1564 1565 1566
		if (fail_on_exist)
			return ERR_PTR(-EEXIST);
		return gfs2_inode_lookup(dir->i_sb, dtype, addr, formal_ino, 0);
1567 1568 1569 1570 1571 1572 1573 1574 1575 1576
	}
	return ERR_PTR(-ENOENT);
}

int gfs2_dir_check(struct inode *dir, const struct qstr *name,
		   const struct gfs2_inode *ip)
{
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
	int ret = -ENOENT;
1577 1578 1579 1580 1581

	dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
	if (dent) {
		if (IS_ERR(dent))
			return PTR_ERR(dent);
1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596
		if (ip) {
			if (be64_to_cpu(dent->de_inum.no_addr) != ip->i_no_addr)
				goto out;
			if (be64_to_cpu(dent->de_inum.no_formal_ino) !=
			    ip->i_no_formal_ino)
				goto out;
			if (unlikely(IF2DT(ip->i_inode.i_mode) !=
			    be16_to_cpu(dent->de_type))) {
				gfs2_consist_inode(GFS2_I(dir));
				ret = -EIO;
				goto out;
			}
		}
		ret = 0;
out:
1597 1598
		brelse(bh);
	}
1599
	return ret;
1600 1601
}

1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620
/**
 * dir_new_leaf - Add a new leaf onto hash chain
 * @inode: The directory
 * @name: The name we are adding
 *
 * This adds a new dir leaf onto an existing leaf when there is not
 * enough space to add a new dir entry. This is a last resort after
 * we've expanded the hash table to max size and also split existing
 * leaf blocks, so it will only occur for very large directories.
 *
 * The dist parameter is set to 1 for leaf blocks directly attached
 * to the hash table, 2 for one layer of indirection, 3 for two layers
 * etc. We are thus able to tell the difference between an old leaf
 * with dist set to zero (i.e. "don't know") and a new one where we
 * set this information for debug/fsck purposes.
 *
 * Returns: 0 on success, or -ve on error
 */

1621 1622 1623
static int dir_new_leaf(struct inode *inode, const struct qstr *name)
{
	struct buffer_head *bh, *obh;
1624
	struct gfs2_inode *ip = GFS2_I(inode);
1625
	struct gfs2_leaf *leaf, *oleaf;
1626
	u32 dist = 1;
D
David Teigland 已提交
1627
	int error;
1628 1629
	u32 index;
	u64 bn;
D
David Teigland 已提交
1630

1631
	index = name->hash >> (32 - ip->i_depth);
1632 1633 1634 1635
	error = get_first_leaf(ip, index, &obh);
	if (error)
		return error;
	do {
1636
		dist++;
1637 1638 1639 1640 1641 1642 1643 1644 1645
		oleaf = (struct gfs2_leaf *)obh->b_data;
		bn = be64_to_cpu(oleaf->lf_next);
		if (!bn)
			break;
		brelse(obh);
		error = get_leaf(ip, bn, &obh);
		if (error)
			return error;
	} while(1);
D
David Teigland 已提交
1646

1647
	gfs2_trans_add_meta(ip->i_gl, obh);
1648 1649 1650 1651 1652 1653

	leaf = new_leaf(inode, &bh, be16_to_cpu(oleaf->lf_depth));
	if (!leaf) {
		brelse(obh);
		return -ENOSPC;
	}
1654
	leaf->lf_dist = cpu_to_be32(dist);
1655
	oleaf->lf_next = cpu_to_be64(bh->b_blocknr);
1656 1657 1658 1659 1660 1661
	brelse(bh);
	brelse(obh);

	error = gfs2_meta_inode_buffer(ip, &bh);
	if (error)
		return error;
1662
	gfs2_trans_add_meta(ip->i_gl, bh);
1663
	gfs2_add_inode_blocks(&ip->i_inode, 1);
1664
	gfs2_dinode_out(ip, bh->b_data);
1665 1666
	brelse(bh);
	return 0;
D
David Teigland 已提交
1667 1668
}

1669 1670 1671 1672 1673 1674 1675 1676
static u16 gfs2_inode_ra_len(const struct gfs2_inode *ip)
{
	u64 where = ip->i_no_addr + 1;
	if (ip->i_eattr == where)
		return 1;
	return 0;
}

D
David Teigland 已提交
1677 1678
/**
 * gfs2_dir_add - Add new filename into directory
1679 1680 1681 1682 1683 1684 1685 1686 1687 1688
 * @inode: The directory inode
 * @name: The new name
 * @nip: The GFS2 inode to be linked in to the directory
 * @da: The directory addition info
 *
 * If the call to gfs2_diradd_alloc_required resulted in there being
 * no need to allocate any new directory blocks, then it will contain
 * a pointer to the directory entry and the bh in which it resides. We
 * can use that without having to repeat the search. If there was no
 * free space, then we must now create more space.
D
David Teigland 已提交
1689 1690 1691 1692
 *
 * Returns: 0 on success, error code on failure
 */

1693
int gfs2_dir_add(struct inode *inode, const struct qstr *name,
1694
		 const struct gfs2_inode *nip, struct gfs2_diradd *da)
D
David Teigland 已提交
1695
{
1696
	struct gfs2_inode *ip = GFS2_I(inode);
1697 1698
	struct buffer_head *bh = da->bh;
	struct gfs2_dirent *dent = da->dent;
1699
	struct timespec tv;
1700
	struct gfs2_leaf *leaf;
D
David Teigland 已提交
1701 1702
	int error;

1703
	while(1) {
1704 1705 1706 1707
		if (da->bh == NULL) {
			dent = gfs2_dirent_search(inode, name,
						  gfs2_dirent_find_space, &bh);
		}
1708 1709 1710 1711
		if (dent) {
			if (IS_ERR(dent))
				return PTR_ERR(dent);
			dent = gfs2_init_dirent(inode, dent, name, bh);
1712
			gfs2_inum_out(nip, dent);
1713
			dent->de_type = cpu_to_be16(IF2DT(nip->i_inode.i_mode));
1714
			dent->de_rahead = cpu_to_be16(gfs2_inode_ra_len(nip));
1715
			tv = CURRENT_TIME;
1716
			if (ip->i_diskflags & GFS2_DIF_EXHASH) {
1717
				leaf = (struct gfs2_leaf *)bh->b_data;
M
Marcin Slusarz 已提交
1718
				be16_add_cpu(&leaf->lf_entries, 1);
1719 1720
				leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
				leaf->lf_sec = cpu_to_be64(tv.tv_sec);
1721
			}
1722 1723
			da->dent = NULL;
			da->bh = NULL;
1724
			brelse(bh);
1725
			ip->i_entries++;
1726
			ip->i_inode.i_mtime = ip->i_inode.i_ctime = tv;
1727 1728
			if (S_ISDIR(nip->i_inode.i_mode))
				inc_nlink(&ip->i_inode);
1729
			mark_inode_dirty(inode);
1730 1731 1732
			error = 0;
			break;
		}
1733
		if (!(ip->i_diskflags & GFS2_DIF_EXHASH)) {
1734 1735 1736 1737 1738 1739 1740 1741
			error = dir_make_exhash(inode);
			if (error)
				break;
			continue;
		}
		error = dir_split_leaf(inode, name);
		if (error == 0)
			continue;
1742
		if (error < 0)
1743
			break;
1744
		if (ip->i_depth < GFS2_DIR_MAX_DEPTH) {
1745 1746 1747 1748
			error = dir_double_exhash(ip);
			if (error)
				break;
			error = dir_split_leaf(inode, name);
1749
			if (error < 0)
1750
				break;
1751 1752
			if (error == 0)
				continue;
1753 1754 1755 1756 1757 1758 1759
		}
		error = dir_new_leaf(inode, name);
		if (!error)
			continue;
		error = -ENOSPC;
		break;
	}
D
David Teigland 已提交
1760 1761 1762
	return error;
}

1763

D
David Teigland 已提交
1764 1765 1766 1767 1768 1769 1770 1771
/**
 * gfs2_dir_del - Delete a directory entry
 * @dip: The GFS2 inode
 * @filename: The filename
 *
 * Returns: 0 on success, error code on failure
 */

1772
int gfs2_dir_del(struct gfs2_inode *dip, const struct dentry *dentry)
D
David Teigland 已提交
1773
{
1774
	const struct qstr *name = &dentry->d_name;
1775 1776
	struct gfs2_dirent *dent, *prev = NULL;
	struct buffer_head *bh;
1777
	struct timespec tv = CURRENT_TIME;
D
David Teigland 已提交
1778

1779 1780
	/* Returns _either_ the entry (if its first in block) or the
	   previous entry otherwise */
1781
	dent = gfs2_dirent_search(&dip->i_inode, name, gfs2_dirent_prev, &bh);
1782 1783 1784 1785 1786 1787 1788 1789 1790
	if (!dent) {
		gfs2_consist_inode(dip);
		return -EIO;
	}
	if (IS_ERR(dent)) {
		gfs2_consist_inode(dip);
		return PTR_ERR(dent);
	}
	/* If not first in block, adjust pointers accordingly */
1791
	if (gfs2_dirent_find(dent, name, NULL) == 0) {
1792 1793 1794 1795 1796
		prev = dent;
		dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len));
	}

	dirent_del(dip, bh, prev, dent);
1797
	if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1798 1799 1800 1801 1802
		struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
		u16 entries = be16_to_cpu(leaf->lf_entries);
		if (!entries)
			gfs2_consist_inode(dip);
		leaf->lf_entries = cpu_to_be16(--entries);
1803 1804
		leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
		leaf->lf_sec = cpu_to_be64(tv.tv_sec);
1805
	}
1806
	brelse(bh);
1807

1808
	if (!dip->i_entries)
1809
		gfs2_consist_inode(dip);
1810
	dip->i_entries--;
1811
	dip->i_inode.i_mtime = dip->i_inode.i_ctime = tv;
1812 1813
	if (S_ISDIR(dentry->d_inode->i_mode))
		drop_nlink(&dip->i_inode);
1814
	mark_inode_dirty(&dip->i_inode);
D
David Teigland 已提交
1815

S
Steven Whitehouse 已提交
1816
	return 0;
D
David Teigland 已提交
1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831
}

/**
 * gfs2_dir_mvino - Change inode number of directory entry
 * @dip: The GFS2 inode
 * @filename:
 * @new_inode:
 *
 * This routine changes the inode number of a directory entry.  It's used
 * by rename to change ".." when a directory is moved.
 * Assumes a glock is held on dvp.
 *
 * Returns: errno
 */

1832
int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename,
1833
		   const struct gfs2_inode *nip, unsigned int new_type)
D
David Teigland 已提交
1834
{
1835 1836
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
D
David Teigland 已提交
1837 1838
	int error;

1839
	dent = gfs2_dirent_search(&dip->i_inode, filename, gfs2_dirent_find, &bh);
1840 1841 1842 1843 1844 1845
	if (!dent) {
		gfs2_consist_inode(dip);
		return -EIO;
	}
	if (IS_ERR(dent))
		return PTR_ERR(dent);
D
David Teigland 已提交
1846

1847
	gfs2_trans_add_meta(dip->i_gl, bh);
1848
	gfs2_inum_out(nip, dent);
1849 1850
	dent->de_type = cpu_to_be16(new_type);

1851
	if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1852 1853 1854 1855
		brelse(bh);
		error = gfs2_meta_inode_buffer(dip, &bh);
		if (error)
			return error;
1856
		gfs2_trans_add_meta(dip->i_gl, bh);
1857 1858
	}

1859
	dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME;
1860
	gfs2_dinode_out(dip, bh->b_data);
1861 1862
	brelse(bh);
	return 0;
D
David Teigland 已提交
1863 1864 1865 1866 1867 1868 1869 1870
}

/**
 * leaf_dealloc - Deallocate a directory leaf
 * @dip: the directory
 * @index: the hash table offset in the directory
 * @len: the number of pointers to this leaf
 * @leaf_no: the leaf number
1871
 * @leaf_bh: buffer_head for the starting leaf
1872
 * last_dealloc: 1 if this is the final dealloc for the leaf, else 0
D
David Teigland 已提交
1873 1874 1875 1876
 *
 * Returns: errno
 */

1877
static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len,
1878 1879
			u64 leaf_no, struct buffer_head *leaf_bh,
			int last_dealloc)
D
David Teigland 已提交
1880
{
1881
	struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode);
1882
	struct gfs2_leaf *tmp_leaf;
D
David Teigland 已提交
1883 1884
	struct gfs2_rgrp_list rlist;
	struct buffer_head *bh, *dibh;
1885
	u64 blk, nblk;
D
David Teigland 已提交
1886 1887
	unsigned int rg_blocks = 0, l_blocks = 0;
	char *ht;
1888
	unsigned int x, size = len * sizeof(u64);
D
David Teigland 已提交
1889 1890
	int error;

1891 1892 1893 1894
	error = gfs2_rindex_update(sdp);
	if (error)
		return error;

D
David Teigland 已提交
1895 1896
	memset(&rlist, 0, sizeof(struct gfs2_rgrp_list));

1897
	ht = kzalloc(size, GFP_NOFS | __GFP_NOWARN);
1898 1899
	if (ht == NULL)
		ht = vzalloc(size);
D
David Teigland 已提交
1900 1901 1902
	if (!ht)
		return -ENOMEM;

1903
	error = gfs2_quota_hold(dip, NO_UID_QUOTA_CHANGE, NO_GID_QUOTA_CHANGE);
D
David Teigland 已提交
1904
	if (error)
1905
		goto out;
D
David Teigland 已提交
1906 1907

	/*  Count the number of leaves  */
1908
	bh = leaf_bh;
D
David Teigland 已提交
1909

1910
	for (blk = leaf_no; blk; blk = nblk) {
1911 1912 1913 1914 1915
		if (blk != leaf_no) {
			error = get_leaf(dip, blk, &bh);
			if (error)
				goto out_rlist;
		}
1916 1917
		tmp_leaf = (struct gfs2_leaf *)bh->b_data;
		nblk = be64_to_cpu(tmp_leaf->lf_next);
1918 1919
		if (blk != leaf_no)
			brelse(bh);
D
David Teigland 已提交
1920

1921
		gfs2_rlist_add(dip, &rlist, blk);
D
David Teigland 已提交
1922 1923 1924
		l_blocks++;
	}

1925
	gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE);
D
David Teigland 已提交
1926 1927 1928

	for (x = 0; x < rlist.rl_rgrps; x++) {
		struct gfs2_rgrpd *rgd;
1929
		rgd = rlist.rl_ghs[x].gh_gl->gl_object;
1930
		rg_blocks += rgd->rd_length;
D
David Teigland 已提交
1931 1932 1933 1934 1935 1936 1937
	}

	error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs);
	if (error)
		goto out_rlist;

	error = gfs2_trans_begin(sdp,
1938
			rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) +
D
David Teigland 已提交
1939 1940 1941 1942
			RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks);
	if (error)
		goto out_rg_gunlock;

1943 1944
	bh = leaf_bh;

1945
	for (blk = leaf_no; blk; blk = nblk) {
1946 1947 1948 1949 1950
		if (blk != leaf_no) {
			error = get_leaf(dip, blk, &bh);
			if (error)
				goto out_end_trans;
		}
1951 1952
		tmp_leaf = (struct gfs2_leaf *)bh->b_data;
		nblk = be64_to_cpu(tmp_leaf->lf_next);
1953 1954
		if (blk != leaf_no)
			brelse(bh);
D
David Teigland 已提交
1955 1956

		gfs2_free_meta(dip, blk, 1);
1957
		gfs2_add_inode_blocks(&dip->i_inode, -1);
D
David Teigland 已提交
1958 1959
	}

1960
	error = gfs2_dir_write_data(dip, ht, index * sizeof(u64), size);
D
David Teigland 已提交
1961 1962 1963 1964 1965 1966 1967 1968 1969 1970
	if (error != size) {
		if (error >= 0)
			error = -EIO;
		goto out_end_trans;
	}

	error = gfs2_meta_inode_buffer(dip, &dibh);
	if (error)
		goto out_end_trans;

1971
	gfs2_trans_add_meta(dip->i_gl, dibh);
1972 1973 1974 1975
	/* On the last dealloc, make this a regular file in case we crash.
	   (We don't want to free these blocks a second time.)  */
	if (last_dealloc)
		dip->i_inode.i_mode = S_IFREG;
1976
	gfs2_dinode_out(dip, dibh->b_data);
D
David Teigland 已提交
1977 1978
	brelse(dibh);

1979
out_end_trans:
D
David Teigland 已提交
1980
	gfs2_trans_end(sdp);
1981
out_rg_gunlock:
D
David Teigland 已提交
1982
	gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs);
1983
out_rlist:
D
David Teigland 已提交
1984 1985
	gfs2_rlist_free(&rlist);
	gfs2_quota_unhold(dip);
1986
out:
1987
	kvfree(ht);
D
David Teigland 已提交
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002
	return error;
}

/**
 * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory
 * @dip: the directory
 *
 * Dealloc all on-disk directory leaves to FREEMETA state
 * Change on-disk inode type to "regular file"
 *
 * Returns: errno
 */

int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip)
{
2003 2004 2005 2006 2007 2008 2009 2010 2011 2012
	struct buffer_head *bh;
	struct gfs2_leaf *leaf;
	u32 hsize, len;
	u32 index = 0, next_index;
	__be64 *lp;
	u64 leaf_no;
	int error = 0, last;

	hsize = 1 << dip->i_depth;

2013 2014 2015
	lp = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(lp))
		return PTR_ERR(lp);
2016 2017

	while (index < hsize) {
2018
		leaf_no = be64_to_cpu(lp[index]);
2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045
		if (leaf_no) {
			error = get_leaf(dip, leaf_no, &bh);
			if (error)
				goto out;
			leaf = (struct gfs2_leaf *)bh->b_data;
			len = 1 << (dip->i_depth - be16_to_cpu(leaf->lf_depth));

			next_index = (index & ~(len - 1)) + len;
			last = ((next_index >= hsize) ? 1 : 0);
			error = leaf_dealloc(dip, index, len, leaf_no, bh,
					     last);
			brelse(bh);
			if (error)
				goto out;
			index = next_index;
		} else
			index++;
	}

	if (index != hsize) {
		gfs2_consist_inode(dip);
		error = -EIO;
	}

out:

	return error;
D
David Teigland 已提交
2046 2047 2048 2049 2050 2051
}

/**
 * gfs2_diradd_alloc_required - find if adding entry will require an allocation
 * @ip: the file being written to
 * @filname: the filename that's going to be added
2052
 * @da: The structure to return dir alloc info
D
David Teigland 已提交
2053
 *
2054
 * Returns: 0 if ok, -ve on error
D
David Teigland 已提交
2055 2056
 */

2057 2058
int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name,
			       struct gfs2_diradd *da)
D
David Teigland 已提交
2059
{
2060
	struct gfs2_inode *ip = GFS2_I(inode);
2061
	struct gfs2_sbd *sdp = GFS2_SB(inode);
2062
	const unsigned int extra = sizeof(struct gfs2_dinode) - sizeof(struct gfs2_leaf);
2063 2064
	struct gfs2_dirent *dent;
	struct buffer_head *bh;
D
David Teigland 已提交
2065

2066
	da->nr_blocks = 0;
2067 2068
	da->bh = NULL;
	da->dent = NULL;
2069

2070
	dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh);
2071
	if (!dent) {
2072
		da->nr_blocks = sdp->sd_max_dirres;
2073 2074 2075
		if (!(ip->i_diskflags & GFS2_DIF_EXHASH) &&
		    (GFS2_DIRENT_SIZE(name->len) < extra))
			da->nr_blocks = 1;
2076
		return 0;
2077
	}
2078 2079
	if (IS_ERR(dent))
		return PTR_ERR(dent);
2080 2081 2082 2083 2084 2085 2086

	if (da->save_loc) {
		da->bh = bh;
		da->dent = dent;
	} else {
		brelse(bh);
	}
2087
	return 0;
D
David Teigland 已提交
2088 2089
}