dir.c 52.1 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))
85 86
#define GFS2_HASH_INDEX_MASK 0xffffc000
#define GFS2_USE_HASH_FLAG 0x2000
D
David Teigland 已提交
87

88 89 90
struct qstr gfs2_qdot __read_mostly;
struct qstr gfs2_qdotdot __read_mostly;

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

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

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

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

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

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;

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

	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,
158
			       u64 offset, unsigned int size)
159
{
160
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
161
	struct buffer_head *dibh;
162 163
	u64 lblock, dblock;
	u32 extlen = 0;
164 165 166
	unsigned int o;
	int copied = 0;
	int error = 0;
167
	int new = 0;
168 169 170 171 172 173

	if (!size)
		return 0;

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

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

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

	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;
199
			error = gfs2_extent_map(&ip->i_inode, lblock, &new,
S
Steven Whitehouse 已提交
200
						&dblock, &extlen);
201 202 203 204 205 206 207
			if (error)
				goto fail;
			error = -EIO;
			if (gfs2_assert_withdraw(sdp, dblock))
				goto fail;
		}

208 209 210 211 212
		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);

213 214 215
		if (error)
			goto fail;

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

220
		buf += amount;
221 222 223 224 225 226 227 228 229 230 231 232 233
		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 已提交
234 235
	if (ip->i_inode.i_size < offset + copied)
		i_size_write(&ip->i_inode, offset + copied);
236
	ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
237

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

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

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

	error = gfs2_meta_inode_buffer(ip, &dibh);
	if (!error) {
257
		memcpy(buf, dibh->b_data + sizeof(struct gfs2_dinode), size);
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
		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
 */
273 274
static int gfs2_dir_read_data(struct gfs2_inode *ip, __be64 *buf,
			      unsigned int size)
275
{
276
	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
277 278
	u64 lblock, dblock;
	u32 extlen = 0;
279 280 281 282 283
	unsigned int o;
	int copied = 0;
	int error = 0;

	if (gfs2_is_stuffed(ip))
284
		return gfs2_dir_read_stuffed(ip, buf, size);
285 286 287 288

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

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

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

334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
/**
 * 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);
	}

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

365 366 367
	if (hc == NULL)
		return ERR_PTR(-ENOMEM);

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

	spin_lock(&inode->i_lock);
375
	if (likely(!ip->i_hash_cache)) {
376
		ip->i_hash_cache = hc;
377 378
		hc = NULL;
	}
379
	spin_unlock(&inode->i_lock);
380
	kvfree(hc);
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)
{
393 394 395 396
	__be64 *hc;

	spin_lock(&ip->i_inode.i_lock);
	hc = ip->i_hash_cache;
397
	ip->i_hash_cache = NULL;
398 399
	spin_unlock(&ip->i_inode.i_lock);

400
	kvfree(hc);
401 402
}

403 404 405 406 407
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;
}

408 409 410
static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent,
				     const struct qstr *name, int ret)
{
411
	if (!gfs2_dirent_sentinel(dent) &&
412 413
	    be32_to_cpu(dent->de_hash) == name->hash &&
	    be16_to_cpu(dent->de_name_len) == name->len &&
414
	    memcmp(dent+1, name->name, name->len) == 0)
415 416 417 418 419
		return ret;
	return 0;
}

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

static int gfs2_dirent_prev(const struct gfs2_dirent *dent,
427 428
			    const struct qstr *name,
			    void *opaque)
429 430 431 432 433 434 435
{
	return __gfs2_dirent_find(dent, name, 2);
}

/*
 * name->name holds ptr to start of block.
 * name->len holds size of block.
D
David Teigland 已提交
436
 */
437
static int gfs2_dirent_last(const struct gfs2_dirent *dent,
438 439
			    const struct qstr *name,
			    void *opaque)
440 441 442 443 444 445 446
{
	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 已提交
447

448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468
/* Look for the dirent that contains the offset specified in data. Once we
 * find that dirent, there must be space available there for the new dirent */
static int gfs2_dirent_find_offset(const struct gfs2_dirent *dent,
				  const struct qstr *name,
				  void *ptr)
{
	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);

	if (ptr < (void *)dent || ptr >= (void *)dent + totlen)
		return 0;
	if (gfs2_dirent_sentinel(dent))
		actual = 0;
	if (ptr < (void *)dent + actual)
		return -1;
	if ((void *)dent + totlen >= ptr + required)
		return 1;
	return -1;
}

469
static int gfs2_dirent_find_space(const struct gfs2_dirent *dent,
470 471
				  const struct qstr *name,
				  void *opaque)
D
David Teigland 已提交
472
{
473 474 475 476
	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);

477
	if (gfs2_dirent_sentinel(dent))
B
Bob Peterson 已提交
478
		actual = 0;
J
Jan Engelhardt 已提交
479
	if (totlen - actual >= required)
480 481 482 483
		return 1;
	return 0;
}

484 485 486 487 488 489 490 491 492 493
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;
494
	if (!gfs2_dirent_sentinel(dent)) {
495 496 497 498 499
		g->pdent[g->offset++] = dent;
	}
	return 0;
}

500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521
/*
 * 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";
522
	if (unlikely(!first && gfs2_dirent_sentinel(dent)))
523 524
		goto error;
	msg = "name length is greater than space in dirent";
525
	if (!gfs2_dirent_sentinel(dent) &&
526 527 528 529 530
	    unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) >
		     size))
		goto error;
	return 0;
error:
531 532
	pr_warn("%s: %s (%s)\n",
		__func__, msg, first ? "first in block" : "not first in block");
533
	return -EIO;
D
David Teigland 已提交
534 535
}

536
static int gfs2_dirent_offset(const void *buf)
537
{
538 539
	const struct gfs2_meta_header *h = buf;
	int offset;
540 541 542

	BUG_ON(buf == NULL);

543
	switch(be32_to_cpu(h->mh_type)) {
544 545 546 547 548 549 550 551 552
	case GFS2_METATYPE_LF:
		offset = sizeof(struct gfs2_leaf);
		break;
	case GFS2_METATYPE_DI:
		offset = sizeof(struct gfs2_dinode);
		break;
	default:
		goto wrong_type;
	}
553 554
	return offset;
wrong_type:
555
	pr_warn("%s: wrong block type %u\n", __func__, be32_to_cpu(h->mh_type));
556 557 558
	return -1;
}

559
static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf,
560 561 562 563 564 565 566 567
					    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;
568

569 570 571 572 573
	ret = gfs2_dirent_offset(buf);
	if (ret < 0)
		goto consist_inode;

	offset = ret;
574
	prev = NULL;
575
	dent = buf + offset;
576 577 578 579
	size = be16_to_cpu(dent->de_rec_len);
	if (gfs2_check_dirent(dent, offset, size, len, 1))
		goto consist_inode;
	do {
580
		ret = scan(dent, name, opaque);
581 582 583 584 585 586
		if (ret)
			break;
		offset += size;
		if (offset == len)
			break;
		prev = dent;
587
		dent = buf + offset;
588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605
		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:
606
	gfs2_consist_inode(GFS2_I(inode));
607 608 609
	return ERR_PTR(-EIO);
}

610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627
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 已提交
628 629 630 631 632 633 634 635 636 637 638 639
/**
 * 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)
{
640 641 642
	struct gfs2_dirent *cur = *dent, *tmp;
	char *bh_end = bh->b_data + bh->b_size;
	int ret;
D
David Teigland 已提交
643

644 645 646
	ret = dirent_check_reclen(dip, cur, bh_end);
	if (ret < 0)
		return ret;
647

648 649 650 651
	tmp = (void *)cur + ret;
	ret = dirent_check_reclen(dip, tmp, bh_end);
	if (ret == -EIO)
		return ret;
652

D
David Teigland 已提交
653
        /* Only the first dent could ever have de_inum.no_addr == 0 */
654
	if (gfs2_dirent_sentinel(tmp)) {
D
David Teigland 已提交
655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674
		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)
{
675
	u16 cur_rec_len, prev_rec_len;
D
David Teigland 已提交
676

677
	if (gfs2_dirent_sentinel(cur)) {
D
David Teigland 已提交
678 679 680 681
		gfs2_consist_inode(dip);
		return;
	}

682
	gfs2_trans_add_meta(dip->i_gl, bh);
D
David Teigland 已提交
683 684 685 686 687 688

	/* 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) {
689 690
		cur->de_inum.no_addr = 0;
		cur->de_inum.no_formal_ino = 0;
D
David Teigland 已提交
691 692 693 694 695
		return;
	}

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

696 697
	prev_rec_len = be16_to_cpu(prev->de_rec_len);
	cur_rec_len = be16_to_cpu(cur->de_rec_len);
D
David Teigland 已提交
698 699 700 701 702 703 704

	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;
705
	prev->de_rec_len = cpu_to_be16(prev_rec_len);
D
David Teigland 已提交
706 707
}

708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728

static struct gfs2_dirent *do_init_dirent(struct inode *inode,
					  struct gfs2_dirent *dent,
					  const struct qstr *name,
					  struct buffer_head *bh,
					  unsigned offset)
{
	struct gfs2_inode *ip = GFS2_I(inode);
	struct gfs2_dirent *ndent;
	unsigned totlen;

	totlen = be16_to_cpu(dent->de_rec_len);
	BUG_ON(offset + name->len > totlen);
	gfs2_trans_add_meta(ip->i_gl, bh);
	ndent = (struct gfs2_dirent *)((char *)dent + offset);
	dent->de_rec_len = cpu_to_be16(offset);
	gfs2_qstr2dirent(name, totlen - offset, ndent);
	return ndent;
}


729 730 731
/*
 * Takes a dent from which to grab space as an argument. Returns the
 * newly created dent.
D
David Teigland 已提交
732
 */
733 734 735 736
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 已提交
737
{
738
	unsigned offset = 0;
739

740
	if (!gfs2_dirent_sentinel(dent))
741
		offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
742
	return do_init_dirent(inode, dent, name, bh, offset);
D
David Teigland 已提交
743 744
}

745 746 747 748
static struct gfs2_dirent *gfs2_dirent_split_alloc(struct inode *inode,
						   struct buffer_head *bh,
						   const struct qstr *name,
						   void *ptr)
D
David Teigland 已提交
749 750
{
	struct gfs2_dirent *dent;
751
	dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
752
				gfs2_dirent_find_offset, name, ptr);
753 754
	if (!dent || IS_ERR(dent))
		return dent;
755 756
	return do_init_dirent(inode, dent, name, bh,
			      (unsigned)(ptr - (void *)dent));
D
David Teigland 已提交
757 758
}

759
static int get_leaf(struct gfs2_inode *dip, u64 leaf_no,
D
David Teigland 已提交
760 761 762 763
		    struct buffer_head **bhp)
{
	int error;

764
	error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_WAIT, 0, bhp);
765
	if (!error && gfs2_metatype_check(GFS2_SB(&dip->i_inode), *bhp, GFS2_METATYPE_LF)) {
766
		/* pr_info("block num=%llu\n", leaf_no); */
D
David Teigland 已提交
767
		error = -EIO;
768
	}
D
David Teigland 已提交
769 770 771 772 773 774 775 776 777 778 779 780 781

	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
 */

782 783
static int get_leaf_nr(struct gfs2_inode *dip, u32 index,
		       u64 *leaf_out)
D
David Teigland 已提交
784
{
785
	__be64 *hash;
786
	int error;
D
David Teigland 已提交
787

788
	hash = gfs2_dir_get_hash_table(dip);
789 790 791 792 793 794
	error = PTR_ERR_OR_ZERO(hash);

	if (!error)
		*leaf_out = be64_to_cpu(*(hash + index));

	return error;
D
David Teigland 已提交
795 796
}

797
static int get_first_leaf(struct gfs2_inode *dip, u32 index,
D
David Teigland 已提交
798 799
			  struct buffer_head **bh_out)
{
800
	u64 leaf_no;
D
David Teigland 已提交
801 802 803
	int error;

	error = get_leaf_nr(dip, index, &leaf_no);
804
	if (!error)
D
David Teigland 已提交
805 806 807 808 809
		error = get_leaf(dip, leaf_no, bh_out);

	return error;
}

810 811 812 813
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 已提交
814
{
815 816
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
817
	struct gfs2_inode *ip = GFS2_I(inode);
D
David Teigland 已提交
818 819
	int error;

820
	if (ip->i_diskflags & GFS2_DIF_EXHASH) {
821
		struct gfs2_leaf *leaf;
822
		unsigned hsize = 1 << ip->i_depth;
823 824
		unsigned index;
		u64 ln;
S
Steven Whitehouse 已提交
825
		if (hsize * sizeof(u64) != i_size_read(inode)) {
826 827 828
			gfs2_consist_inode(ip);
			return ERR_PTR(-EIO);
		}
829

830
		index = name->hash >> (32 - ip->i_depth);
831 832 833 834 835
		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,
836
						scan, name, NULL);
837 838 839 840
			if (dent)
				goto got_dent;
			leaf = (struct gfs2_leaf *)bh->b_data;
			ln = be64_to_cpu(leaf->lf_next);
841
			brelse(bh);
842 843
			if (!ln)
				break;
844

845 846
			error = get_leaf(ip, ln, &bh);
		} while(!error);
D
David Teigland 已提交
847

848
		return error ? ERR_PTR(error) : NULL;
D
David Teigland 已提交
849 850
	}

851

852 853 854
	error = gfs2_meta_inode_buffer(ip, &bh);
	if (error)
		return ERR_PTR(error);
855
	dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, scan, name, NULL);
856
got_dent:
857
	if (unlikely(dent == NULL || IS_ERR(dent))) {
858 859 860
		brelse(bh);
		bh = NULL;
	}
861 862 863
	*pbh = bh;
	return dent;
}
D
David Teigland 已提交
864

865 866
static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth)
{
867
	struct gfs2_inode *ip = GFS2_I(inode);
868
	unsigned int n = 1;
869 870 871
	u64 bn;
	int error;
	struct buffer_head *bh;
872 873
	struct gfs2_leaf *leaf;
	struct gfs2_dirent *dent;
874
	struct qstr name = { .name = "" };
875
	struct timespec tv = CURRENT_TIME;
876

877
	error = gfs2_alloc_blocks(ip, &bn, &n, 0, NULL);
878 879 880
	if (error)
		return NULL;
	bh = gfs2_meta_new(ip->i_gl, bn);
881 882
	if (!bh)
		return NULL;
883

884
	gfs2_trans_add_unrevoke(GFS2_SB(inode), bn, 1);
885
	gfs2_trans_add_meta(ip->i_gl, bh);
886 887 888
	gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
	leaf = (struct gfs2_leaf *)bh->b_data;
	leaf->lf_depth = cpu_to_be16(depth);
889
	leaf->lf_entries = 0;
890
	leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
891
	leaf->lf_next = 0;
892 893 894 895 896
	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));
897
	dent = (struct gfs2_dirent *)(leaf+1);
898
	gfs2_qstr2dirent(&name, bh->b_size - sizeof(struct gfs2_leaf), dent);
899 900
	*pbh = bh;
	return leaf;
D
David Teigland 已提交
901 902 903 904 905 906 907 908 909
}

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

910
static int dir_make_exhash(struct inode *inode)
D
David Teigland 已提交
911
{
912 913
	struct gfs2_inode *dip = GFS2_I(inode);
	struct gfs2_sbd *sdp = GFS2_SB(inode);
D
David Teigland 已提交
914
	struct gfs2_dirent *dent;
915
	struct qstr args;
D
David Teigland 已提交
916 917 918
	struct buffer_head *bh, *dibh;
	struct gfs2_leaf *leaf;
	int y;
919
	u32 x;
A
Al Viro 已提交
920 921
	__be64 *lp;
	u64 bn;
D
David Teigland 已提交
922 923 924 925 926 927 928 929
	int error;

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

	/*  Turn over a new leaf  */

930 931 932 933
	leaf = new_leaf(inode, &bh, 0);
	if (!leaf)
		return -ENOSPC;
	bn = bh->b_blocknr;
D
David Teigland 已提交
934

935 936
	gfs2_assert(sdp, dip->i_entries < (1 << 16));
	leaf->lf_entries = cpu_to_be16(dip->i_entries);
D
David Teigland 已提交
937 938 939 940 941 942 943 944 945

	/*  Copy dirents  */

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

	/*  Find last entry  */

	x = 0;
946 947 948
	args.len = bh->b_size - sizeof(struct gfs2_dinode) +
		   sizeof(struct gfs2_leaf);
	args.name = bh->b_data;
949
	dent = gfs2_dirent_scan(&dip->i_inode, bh->b_data, bh->b_size,
950
				gfs2_dirent_last, &args, NULL);
951 952 953 954 955 956 957 958 959
	if (!dent) {
		brelse(bh);
		brelse(dibh);
		return -EIO;
	}
	if (IS_ERR(dent)) {
		brelse(bh);
		brelse(dibh);
		return PTR_ERR(dent);
D
David Teigland 已提交
960 961 962 963 964
	}

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

965
	dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) +
D
David Teigland 已提交
966
		sizeof(struct gfs2_dinode) -
967
		sizeof(struct gfs2_leaf));
D
David Teigland 已提交
968 969 970 971 972 973

	brelse(bh);

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

974
	gfs2_trans_add_meta(dip->i_gl, dibh);
D
David Teigland 已提交
975 976
	gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode));

A
Al Viro 已提交
977
	lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode));
D
David Teigland 已提交
978 979 980 981

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

S
Steven Whitehouse 已提交
982
	i_size_write(inode, sdp->sd_sb.sb_bsize / 2);
983
	gfs2_add_inode_blocks(&dip->i_inode, 1);
984
	dip->i_diskflags |= GFS2_DIF_EXHASH;
D
David Teigland 已提交
985 986

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

989
	gfs2_dinode_out(dip, dibh->b_data);
D
David Teigland 已提交
990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004

	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
 */

1005
static int dir_split_leaf(struct inode *inode, const struct qstr *name)
D
David Teigland 已提交
1006
{
1007
	struct gfs2_inode *dip = GFS2_I(inode);
D
David Teigland 已提交
1008 1009
	struct buffer_head *nbh, *obh, *dibh;
	struct gfs2_leaf *nleaf, *oleaf;
1010
	struct gfs2_dirent *dent = NULL, *prev = NULL, *next = NULL, *new;
1011
	u32 start, len, half_len, divider;
A
Al Viro 已提交
1012 1013
	u64 bn, leaf_no;
	__be64 *lp;
1014
	u32 index;
D
David Teigland 已提交
1015 1016 1017
	int x, moved = 0;
	int error;

1018
	index = name->hash >> (32 - dip->i_depth);
1019
	error = get_leaf_nr(dip, index, &leaf_no);
1020
	if (error)
1021
		return error;
D
David Teigland 已提交
1022 1023 1024 1025

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

	oleaf = (struct gfs2_leaf *)obh->b_data;
1029
	if (dip->i_depth == be16_to_cpu(oleaf->lf_depth)) {
1030 1031 1032 1033
		brelse(obh);
		return 1; /* can't split */
	}

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

1036 1037 1038 1039 1040 1041
	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 已提交
1042

1043
	/*  Compute the start and len of leaf pointers in the hash table.  */
1044
	len = 1 << (dip->i_depth - be16_to_cpu(oleaf->lf_depth));
D
David Teigland 已提交
1045 1046
	half_len = len >> 1;
	if (!half_len) {
1047 1048
		pr_warn("i_depth %u lf_depth %u index %u\n",
			dip->i_depth, be16_to_cpu(oleaf->lf_depth), index);
D
David Teigland 已提交
1049 1050 1051 1052 1053 1054 1055 1056 1057 1058
		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. */
1059 1060 1061 1062 1063 1064
	lp = kmalloc(half_len * sizeof(__be64), GFP_NOFS);
	if (!lp) {
		error = -ENOMEM;
		goto fail_brelse;
	}

D
David Teigland 已提交
1065 1066 1067 1068
	/*  Change the pointers  */
	for (x = 0; x < half_len; x++)
		lp[x] = cpu_to_be64(bn);

1069 1070
	gfs2_dir_hash_inval(dip);

1071 1072 1073
	error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(u64),
				    half_len * sizeof(u64));
	if (error != half_len * sizeof(u64)) {
D
David Teigland 已提交
1074 1075 1076 1077 1078 1079 1080 1081
		if (error >= 0)
			error = -EIO;
		goto fail_lpfree;
	}

	kfree(lp);

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

	/*  Copy the entries  */
1085
	dent = (struct gfs2_dirent *)(obh->b_data + sizeof(struct gfs2_leaf));
D
David Teigland 已提交
1086 1087 1088 1089 1090 1091

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

1092
		if (!gfs2_dirent_sentinel(dent) &&
D
David Teigland 已提交
1093
		    be32_to_cpu(dent->de_hash) < divider) {
1094
			struct qstr str;
1095
			void *ptr = ((char *)dent - obh->b_data) + nbh->b_data;
1096 1097 1098
			str.name = (char*)(dent+1);
			str.len = be16_to_cpu(dent->de_name_len);
			str.hash = be32_to_cpu(dent->de_hash);
1099
			new = gfs2_dirent_split_alloc(inode, nbh, &str, ptr);
1100 1101 1102 1103
			if (IS_ERR(new)) {
				error = PTR_ERR(new);
				break;
			}
D
David Teigland 已提交
1104 1105 1106

			new->de_inum = dent->de_inum; /* No endian worries */
			new->de_type = dent->de_type; /* No endian worries */
M
Marcin Slusarz 已提交
1107
			be16_add_cpu(&nleaf->lf_entries, 1);
D
David Teigland 已提交
1108 1109 1110 1111 1112

			dirent_del(dip, obh, prev, dent);

			if (!oleaf->lf_entries)
				gfs2_consist_inode(dip);
M
Marcin Slusarz 已提交
1113
			be16_add_cpu(&oleaf->lf_entries, -1);
D
David Teigland 已提交
1114 1115 1116 1117 1118

			if (!prev)
				prev = dent;

			moved = 1;
1119
		} else {
D
David Teigland 已提交
1120
			prev = dent;
1121
		}
D
David Teigland 已提交
1122
		dent = next;
1123
	} while (dent);
D
David Teigland 已提交
1124

1125
	oleaf->lf_depth = nleaf->lf_depth;
D
David Teigland 已提交
1126 1127

	error = gfs2_meta_inode_buffer(dip, &dibh);
1128
	if (!gfs2_assert_withdraw(GFS2_SB(&dip->i_inode), !error)) {
1129
		gfs2_trans_add_meta(dip->i_gl, dibh);
1130
		gfs2_add_inode_blocks(&dip->i_inode, 1);
1131
		gfs2_dinode_out(dip, dibh->b_data);
D
David Teigland 已提交
1132 1133 1134 1135 1136 1137 1138 1139
		brelse(dibh);
	}

	brelse(obh);
	brelse(nbh);

	return error;

1140
fail_lpfree:
D
David Teigland 已提交
1141 1142
	kfree(lp);

1143
fail_brelse:
D
David Teigland 已提交
1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
	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;
1159
	u32 hsize;
1160 1161 1162
	u32 hsize_bytes;
	__be64 *hc;
	__be64 *hc2, *h;
D
David Teigland 已提交
1163 1164 1165
	int x;
	int error = 0;

1166
	hsize = 1 << dip->i_depth;
1167
	hsize_bytes = hsize * sizeof(__be64);
D
David Teigland 已提交
1168

1169 1170 1171
	hc = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(hc))
		return PTR_ERR(hc);
D
David Teigland 已提交
1172

1173
	hc2 = kmalloc(hsize_bytes * 2, GFP_NOFS | __GFP_NOWARN);
1174 1175 1176
	if (hc2 == NULL)
		hc2 = __vmalloc(hsize_bytes * 2, GFP_NOFS, PAGE_KERNEL);

1177
	if (!hc2)
1178
		return -ENOMEM;
D
David Teigland 已提交
1179

1180
	h = hc2;
1181 1182 1183
	error = gfs2_meta_inode_buffer(dip, &dibh);
	if (error)
		goto out_kfree;
D
David Teigland 已提交
1184

1185 1186 1187 1188
	for (x = 0; x < hsize; x++) {
		*h++ = *hc;
		*h++ = *hc;
		hc++;
D
David Teigland 已提交
1189 1190
	}

1191 1192 1193
	error = gfs2_dir_write_data(dip, (char *)hc2, 0, hsize_bytes * 2);
	if (error != (hsize_bytes * 2))
		goto fail;
D
David Teigland 已提交
1194

1195 1196 1197 1198 1199 1200
	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 已提交
1201

1202
fail:
1203 1204 1205 1206 1207 1208
	/* 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:
1209
	kvfree(hc2);
D
David Teigland 已提交
1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225
	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)
{
1226
	const struct gfs2_dirent *dent_a, *dent_b;
1227
	u32 hash_a, hash_b;
D
David Teigland 已提交
1228 1229
	int ret = 0;

1230
	dent_a = *(const struct gfs2_dirent **)a;
1231
	hash_a = dent_a->de_cookie;
D
David Teigland 已提交
1232

1233
	dent_b = *(const struct gfs2_dirent **)b;
1234
	hash_b = dent_b->de_cookie;
D
David Teigland 已提交
1235 1236 1237 1238 1239 1240

	if (hash_a > hash_b)
		ret = 1;
	else if (hash_a < hash_b)
		ret = -1;
	else {
1241 1242
		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 已提交
1243 1244 1245 1246 1247 1248

		if (len_a > len_b)
			ret = 1;
		else if (len_a < len_b)
			ret = -1;
		else
1249
			ret = memcmp(dent_a + 1, dent_b + 1, len_a);
D
David Teigland 已提交
1250 1251 1252 1253 1254 1255 1256 1257
	}

	return ret;
}

/**
 * do_filldir_main - read out directory entries
 * @dip: The GFS2 inode
A
Al Viro 已提交
1258
 * @ctx: what to feed the entries to
D
David Teigland 已提交
1259 1260 1261 1262 1263 1264 1265 1266 1267
 * @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 已提交
1268
 * Returns: errno, >0 if the actor tells you to stop
D
David Teigland 已提交
1269 1270
 */

A
Al Viro 已提交
1271
static int do_filldir_main(struct gfs2_inode *dip, struct dir_context *ctx,
1272 1273
			   struct gfs2_dirent **darr, u32 entries,
			   u32 sort_start, int *copied)
D
David Teigland 已提交
1274
{
1275
	const struct gfs2_dirent *dent, *dent_next;
1276
	u64 off, off_next;
D
David Teigland 已提交
1277 1278 1279
	unsigned int x, y;
	int run = 0;

1280 1281 1282
	if (sort_start < entries)
		sort(&darr[sort_start], entries - sort_start,
		     sizeof(struct gfs2_dirent *), compare_dents, NULL);
D
David Teigland 已提交
1283 1284

	dent_next = darr[0];
1285
	off_next = dent_next->de_cookie;
D
David Teigland 已提交
1286 1287 1288 1289 1290 1291 1292

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

		if (y < entries) {
			dent_next = darr[y];
1293
			off_next = dent_next->de_cookie;
D
David Teigland 已提交
1294

A
Al Viro 已提交
1295
			if (off < ctx->pos)
D
David Teigland 已提交
1296
				continue;
A
Al Viro 已提交
1297
			ctx->pos = off;
D
David Teigland 已提交
1298 1299 1300 1301 1302 1303 1304 1305

			if (off_next == off) {
				if (*copied && !run)
					return 1;
				run = 1;
			} else
				run = 0;
		} else {
A
Al Viro 已提交
1306
			if (off < ctx->pos)
D
David Teigland 已提交
1307
				continue;
A
Al Viro 已提交
1308
			ctx->pos = off;
D
David Teigland 已提交
1309 1310
		}

A
Al Viro 已提交
1311
		if (!dir_emit(ctx, (const char *)(dent + 1),
1312
				be16_to_cpu(dent->de_name_len),
A
Al Viro 已提交
1313 1314
				be64_to_cpu(dent->de_inum.no_addr),
				be16_to_cpu(dent->de_type)))
D
David Teigland 已提交
1315 1316 1317 1318 1319
			return 1;

		*copied = 1;
	}

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

A
Al Viro 已提交
1324
	ctx->pos++;
D
David Teigland 已提交
1325 1326 1327 1328

	return 0;
}

1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339
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;
}

1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373

static int gfs2_set_cookies(struct gfs2_sbd *sdp, struct buffer_head *bh,
			    unsigned leaf_nr, struct gfs2_dirent **darr,
			    unsigned entries)
{
	int sort_id = -1;
	int i;
	
	for (i = 0; i < entries; i++) {
		unsigned offset;

		darr[i]->de_cookie = be32_to_cpu(darr[i]->de_hash);
		darr[i]->de_cookie = gfs2_disk_hash2offset(darr[i]->de_cookie);

		if (!sdp->sd_args.ar_loccookie)
			continue;
		offset = (char *)(darr[i]) -
			 (bh->b_data + gfs2_dirent_offset(bh->b_data));
		offset /= GFS2_MIN_DIRENT_SIZE;
		offset += leaf_nr * sdp->sd_max_dents_per_leaf;
		if (offset >= GFS2_USE_HASH_FLAG ||
		    leaf_nr >= GFS2_USE_HASH_FLAG) {
			darr[i]->de_cookie |= GFS2_USE_HASH_FLAG;
			if (sort_id < 0)
				sort_id = i;
			continue;
		}
		darr[i]->de_cookie &= GFS2_HASH_INDEX_MASK;
		darr[i]->de_cookie |= offset;
	}
	return sort_id;
}	


A
Al Viro 已提交
1374 1375
static int gfs2_dir_read_leaf(struct inode *inode, struct dir_context *ctx,
			      int *copied, unsigned *depth,
1376
			      u64 leaf_no)
D
David Teigland 已提交
1377
{
1378
	struct gfs2_inode *ip = GFS2_I(inode);
1379
	struct gfs2_sbd *sdp = GFS2_SB(inode);
1380 1381
	struct buffer_head *bh;
	struct gfs2_leaf *lf;
1382
	unsigned entries = 0, entries2 = 0;
1383 1384
	unsigned leaves = 0, leaf = 0, offset, sort_offset;
	struct gfs2_dirent **darr, *dent;
1385 1386
	struct dirent_gather g;
	struct buffer_head **larr;
1387
	int error, i, need_sort = 0, sort_id;
1388
	u64 lfn = leaf_no;
D
David Teigland 已提交
1389 1390

	do {
1391
		error = get_leaf(ip, lfn, &bh);
D
David Teigland 已提交
1392
		if (error)
1393 1394 1395 1396 1397 1398 1399 1400 1401
			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 已提交
1402

1403 1404 1405 1406 1407
	if (*depth < GFS2_DIR_MAX_DEPTH || !sdp->sd_args.ar_loccookie) {
		need_sort = 1;
		sort_offset = 0;
	}

D
David Teigland 已提交
1408 1409 1410
	if (!entries)
		return 0;

1411
	error = -ENOMEM;
1412 1413 1414 1415 1416 1417
	/*
	 * 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.
	 */
1418
	larr = gfs2_alloc_sort_buffer((leaves + entries + 99) * sizeof(void *));
1419 1420
	if (!larr)
		goto out;
1421 1422
	darr = (struct gfs2_dirent **)(larr + leaves);
	g.pdent = (const struct gfs2_dirent **)darr;
1423 1424
	g.offset = 0;
	lfn = leaf_no;
D
David Teigland 已提交
1425

1426 1427
	do {
		error = get_leaf(ip, lfn, &bh);
D
David Teigland 已提交
1428
		if (error)
1429
			goto out_free;
1430 1431 1432
		lf = (struct gfs2_leaf *)bh->b_data;
		lfn = be64_to_cpu(lf->lf_next);
		if (lf->lf_entries) {
1433
			offset = g.offset;
1434
			entries2 += be16_to_cpu(lf->lf_entries);
1435 1436 1437
			dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
						gfs2_dirent_gather, NULL, &g);
			error = PTR_ERR(dent);
1438
			if (IS_ERR(dent))
1439
				goto out_free;
1440
			if (entries2 != g.offset) {
1441 1442 1443 1444 1445
				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);
1446 1447
					
				error = -EIO;
1448
				goto out_free;
1449 1450
			}
			error = 0;
1451 1452 1453 1454 1455 1456
			sort_id = gfs2_set_cookies(sdp, bh, leaf, &darr[offset],
						   be16_to_cpu(lf->lf_entries));
			if (!need_sort && sort_id >= 0) {
				need_sort = 1;
				sort_offset = offset + sort_id;
			}
1457
			larr[leaf++] = bh;
D
David Teigland 已提交
1458
		} else {
1459
			larr[leaf++] = NULL;
1460
			brelse(bh);
D
David Teigland 已提交
1461
		}
1462
	} while(lfn);
D
David Teigland 已提交
1463

1464
	BUG_ON(entries2 != entries);
1465 1466
	error = do_filldir_main(ip, ctx, darr, entries, need_sort ?
				sort_offset : entries, copied);
1467
out_free:
1468
	for(i = 0; i < leaf; i++)
1469 1470
		if (larr[i])
			brelse(larr[i]);
1471
	kvfree(larr);
1472
out:
D
David Teigland 已提交
1473 1474 1475
	return error;
}

1476 1477
/**
 * gfs2_dir_readahead - Issue read-ahead requests for leaf blocks.
1478 1479 1480 1481
 *
 * 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
1482 1483
 * for the loss of information.
 */
1484 1485 1486 1487 1488 1489 1490 1491 1492 1493
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. */
1494
	if (index + MAX_RA_BLOCKS < f_ra->start)
1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515
		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;
1516
			submit_bh(REQ_OP_READ, REQ_RAHEAD | REQ_META, bh);
1517 1518 1519 1520 1521
			continue;
		}
		brelse(bh);
	}
}
1522

D
David Teigland 已提交
1523
/**
1524 1525
 * dir_e_read - Reads the entries from a directory into a filldir buffer
 * @dip: dinode pointer
A
Al Viro 已提交
1526
 * @ctx: actor to feed the entries to
D
David Teigland 已提交
1527
 *
1528
 * Returns: errno
D
David Teigland 已提交
1529 1530
 */

A
Al Viro 已提交
1531 1532
static int dir_e_read(struct inode *inode, struct dir_context *ctx,
		      struct file_ra_state *f_ra)
D
David Teigland 已提交
1533
{
1534
	struct gfs2_inode *dip = GFS2_I(inode);
1535 1536
	u32 hsize, len = 0;
	u32 hash, index;
A
Al Viro 已提交
1537
	__be64 *lp;
1538 1539
	int copied = 0;
	int error = 0;
1540
	unsigned depth = 0;
D
David Teigland 已提交
1541

1542
	hsize = 1 << dip->i_depth;
A
Al Viro 已提交
1543
	hash = gfs2_dir_offset2hash(ctx->pos);
1544
	index = hash >> (32 - dip->i_depth);
D
David Teigland 已提交
1545

1546
	if (dip->i_hash_cache == NULL)
1547
		f_ra->start = 0;
1548 1549 1550
	lp = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(lp))
		return PTR_ERR(lp);
D
David Teigland 已提交
1551

1552 1553
	gfs2_dir_readahead(inode, hsize, index, f_ra);

D
David Teigland 已提交
1554
	while (index < hsize) {
A
Al Viro 已提交
1555
		error = gfs2_dir_read_leaf(inode, ctx,
1556
					   &copied, &depth,
1557
					   be64_to_cpu(lp[index]));
D
David Teigland 已提交
1558
		if (error)
1559
			break;
D
David Teigland 已提交
1560

1561
		len = 1 << (dip->i_depth - depth);
D
David Teigland 已提交
1562 1563 1564
		index = (index & ~(len - 1)) + len;
	}

1565 1566
	if (error > 0)
		error = 0;
D
David Teigland 已提交
1567 1568 1569
	return error;
}

A
Al Viro 已提交
1570 1571
int gfs2_dir_read(struct inode *inode, struct dir_context *ctx,
		  struct file_ra_state *f_ra)
D
David Teigland 已提交
1572
{
1573
	struct gfs2_inode *dip = GFS2_I(inode);
1574
	struct gfs2_sbd *sdp = GFS2_SB(inode);
1575
	struct dirent_gather g;
1576
	struct gfs2_dirent **darr, *dent;
D
David Teigland 已提交
1577 1578 1579 1580
	struct buffer_head *dibh;
	int copied = 0;
	int error;

1581
	if (!dip->i_entries)
1582 1583
		return 0;

1584
	if (dip->i_diskflags & GFS2_DIF_EXHASH)
A
Al Viro 已提交
1585
		return dir_e_read(inode, ctx, f_ra);
1586

D
David Teigland 已提交
1587 1588 1589 1590 1591 1592 1593 1594 1595
	if (!gfs2_is_stuffed(dip)) {
		gfs2_consist_inode(dip);
		return -EIO;
	}

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

1596
	error = -ENOMEM;
1597
	/* 96 is max number of dirents which can be stuffed into an inode */
J
Josef Bacik 已提交
1598
	darr = kmalloc(96 * sizeof(struct gfs2_dirent *), GFP_NOFS);
1599
	if (darr) {
1600
		g.pdent = (const struct gfs2_dirent **)darr;
1601 1602 1603 1604 1605 1606 1607
		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;
		}
1608
		if (dip->i_entries != g.offset) {
1609
			fs_warn(sdp, "Number of entries corrupt in dir %llu, "
1610
				"ip->i_entries (%u) != g.offset (%u)\n",
1611
				(unsigned long long)dip->i_no_addr,
1612
				dip->i_entries,
1613 1614 1615 1616
				g.offset);
			error = -EIO;
			goto out;
		}
1617
		gfs2_set_cookies(sdp, dibh, 0, darr, dip->i_entries);
A
Al Viro 已提交
1618
		error = do_filldir_main(dip, ctx, darr,
1619
					dip->i_entries, 0, &copied);
1620 1621 1622 1623
out:
		kfree(darr);
	}

D
David Teigland 已提交
1624 1625 1626 1627 1628 1629 1630 1631 1632 1633
	if (error > 0)
		error = 0;

	brelse(dibh);

	return error;
}

/**
 * gfs2_dir_search - Search a directory
1634 1635 1636
 * @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 已提交
1637 1638 1639 1640 1641 1642 1643
 *
 * This routine searches a directory for a file or another directory.
 * Assumes a glock is held on dip.
 *
 * Returns: errno
 */

1644 1645
struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name,
			      bool fail_on_exist)
D
David Teigland 已提交
1646
{
1647 1648
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
1649 1650
	u64 addr, formal_ino;
	u16 dtype;
1651 1652 1653

	dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
	if (dent) {
1654 1655 1656
		struct inode *inode;
		u16 rahead;

1657
		if (IS_ERR(dent))
1658
			return ERR_CAST(dent);
1659
		dtype = be16_to_cpu(dent->de_type);
1660
		rahead = be16_to_cpu(dent->de_rahead);
1661 1662
		addr = be64_to_cpu(dent->de_inum.no_addr);
		formal_ino = be64_to_cpu(dent->de_inum.no_formal_ino);
1663
		brelse(bh);
1664 1665
		if (fail_on_exist)
			return ERR_PTR(-EEXIST);
1666 1667
		inode = gfs2_inode_lookup(dir->i_sb, dtype, addr, formal_ino,
					  GFS2_BLKST_FREE /* ignore */);
1668 1669 1670
		if (!IS_ERR(inode))
			GFS2_I(inode)->i_rahead = rahead;
		return inode;
1671 1672 1673 1674 1675 1676 1677 1678 1679 1680
	}
	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;
1681 1682 1683 1684 1685

	dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
	if (dent) {
		if (IS_ERR(dent))
			return PTR_ERR(dent);
1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700
		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:
1701 1702
		brelse(bh);
	}
1703
	return ret;
1704 1705
}

1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724
/**
 * 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
 */

1725 1726 1727
static int dir_new_leaf(struct inode *inode, const struct qstr *name)
{
	struct buffer_head *bh, *obh;
1728
	struct gfs2_inode *ip = GFS2_I(inode);
1729
	struct gfs2_leaf *leaf, *oleaf;
1730
	u32 dist = 1;
D
David Teigland 已提交
1731
	int error;
1732 1733
	u32 index;
	u64 bn;
D
David Teigland 已提交
1734

1735
	index = name->hash >> (32 - ip->i_depth);
1736 1737 1738 1739
	error = get_first_leaf(ip, index, &obh);
	if (error)
		return error;
	do {
1740
		dist++;
1741 1742 1743 1744 1745 1746 1747 1748 1749
		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 已提交
1750

1751
	gfs2_trans_add_meta(ip->i_gl, obh);
1752 1753 1754 1755 1756 1757

	leaf = new_leaf(inode, &bh, be16_to_cpu(oleaf->lf_depth));
	if (!leaf) {
		brelse(obh);
		return -ENOSPC;
	}
1758
	leaf->lf_dist = cpu_to_be32(dist);
1759
	oleaf->lf_next = cpu_to_be64(bh->b_blocknr);
1760 1761 1762 1763 1764 1765
	brelse(bh);
	brelse(obh);

	error = gfs2_meta_inode_buffer(ip, &bh);
	if (error)
		return error;
1766
	gfs2_trans_add_meta(ip->i_gl, bh);
1767
	gfs2_add_inode_blocks(&ip->i_inode, 1);
1768
	gfs2_dinode_out(ip, bh->b_data);
1769 1770
	brelse(bh);
	return 0;
D
David Teigland 已提交
1771 1772
}

1773 1774 1775 1776 1777 1778 1779 1780
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 已提交
1781 1782
/**
 * gfs2_dir_add - Add new filename into directory
1783 1784 1785 1786 1787 1788 1789 1790 1791 1792
 * @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 已提交
1793 1794 1795 1796
 *
 * Returns: 0 on success, error code on failure
 */

1797
int gfs2_dir_add(struct inode *inode, const struct qstr *name,
1798
		 const struct gfs2_inode *nip, struct gfs2_diradd *da)
D
David Teigland 已提交
1799
{
1800
	struct gfs2_inode *ip = GFS2_I(inode);
1801 1802
	struct buffer_head *bh = da->bh;
	struct gfs2_dirent *dent = da->dent;
1803
	struct timespec tv;
1804
	struct gfs2_leaf *leaf;
D
David Teigland 已提交
1805 1806
	int error;

1807
	while(1) {
1808 1809 1810 1811
		if (da->bh == NULL) {
			dent = gfs2_dirent_search(inode, name,
						  gfs2_dirent_find_space, &bh);
		}
1812 1813 1814 1815
		if (dent) {
			if (IS_ERR(dent))
				return PTR_ERR(dent);
			dent = gfs2_init_dirent(inode, dent, name, bh);
1816
			gfs2_inum_out(nip, dent);
1817
			dent->de_type = cpu_to_be16(IF2DT(nip->i_inode.i_mode));
1818
			dent->de_rahead = cpu_to_be16(gfs2_inode_ra_len(nip));
1819
			tv = CURRENT_TIME;
1820
			if (ip->i_diskflags & GFS2_DIF_EXHASH) {
1821
				leaf = (struct gfs2_leaf *)bh->b_data;
M
Marcin Slusarz 已提交
1822
				be16_add_cpu(&leaf->lf_entries, 1);
1823 1824
				leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
				leaf->lf_sec = cpu_to_be64(tv.tv_sec);
1825
			}
1826 1827
			da->dent = NULL;
			da->bh = NULL;
1828
			brelse(bh);
1829
			ip->i_entries++;
1830
			ip->i_inode.i_mtime = ip->i_inode.i_ctime = tv;
1831 1832
			if (S_ISDIR(nip->i_inode.i_mode))
				inc_nlink(&ip->i_inode);
1833
			mark_inode_dirty(inode);
1834 1835 1836
			error = 0;
			break;
		}
1837
		if (!(ip->i_diskflags & GFS2_DIF_EXHASH)) {
1838 1839 1840 1841 1842 1843 1844 1845
			error = dir_make_exhash(inode);
			if (error)
				break;
			continue;
		}
		error = dir_split_leaf(inode, name);
		if (error == 0)
			continue;
1846
		if (error < 0)
1847
			break;
1848
		if (ip->i_depth < GFS2_DIR_MAX_DEPTH) {
1849 1850 1851 1852
			error = dir_double_exhash(ip);
			if (error)
				break;
			error = dir_split_leaf(inode, name);
1853
			if (error < 0)
1854
				break;
1855 1856
			if (error == 0)
				continue;
1857 1858 1859 1860 1861 1862 1863
		}
		error = dir_new_leaf(inode, name);
		if (!error)
			continue;
		error = -ENOSPC;
		break;
	}
D
David Teigland 已提交
1864 1865 1866
	return error;
}

1867

D
David Teigland 已提交
1868 1869 1870 1871 1872 1873 1874 1875
/**
 * gfs2_dir_del - Delete a directory entry
 * @dip: The GFS2 inode
 * @filename: The filename
 *
 * Returns: 0 on success, error code on failure
 */

1876
int gfs2_dir_del(struct gfs2_inode *dip, const struct dentry *dentry)
D
David Teigland 已提交
1877
{
1878
	const struct qstr *name = &dentry->d_name;
1879 1880
	struct gfs2_dirent *dent, *prev = NULL;
	struct buffer_head *bh;
1881
	struct timespec tv = CURRENT_TIME;
D
David Teigland 已提交
1882

1883 1884
	/* Returns _either_ the entry (if its first in block) or the
	   previous entry otherwise */
1885
	dent = gfs2_dirent_search(&dip->i_inode, name, gfs2_dirent_prev, &bh);
1886 1887 1888 1889 1890 1891 1892 1893 1894
	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 */
1895
	if (gfs2_dirent_find(dent, name, NULL) == 0) {
1896 1897 1898 1899 1900
		prev = dent;
		dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len));
	}

	dirent_del(dip, bh, prev, dent);
1901
	if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1902 1903 1904 1905 1906
		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);
1907 1908
		leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
		leaf->lf_sec = cpu_to_be64(tv.tv_sec);
1909
	}
1910
	brelse(bh);
1911

1912
	if (!dip->i_entries)
1913
		gfs2_consist_inode(dip);
1914
	dip->i_entries--;
1915
	dip->i_inode.i_mtime = dip->i_inode.i_ctime = tv;
1916
	if (d_is_dir(dentry))
1917
		drop_nlink(&dip->i_inode);
1918
	mark_inode_dirty(&dip->i_inode);
D
David Teigland 已提交
1919

S
Steven Whitehouse 已提交
1920
	return 0;
D
David Teigland 已提交
1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935
}

/**
 * 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
 */

1936
int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename,
1937
		   const struct gfs2_inode *nip, unsigned int new_type)
D
David Teigland 已提交
1938
{
1939 1940
	struct buffer_head *bh;
	struct gfs2_dirent *dent;
D
David Teigland 已提交
1941 1942
	int error;

1943
	dent = gfs2_dirent_search(&dip->i_inode, filename, gfs2_dirent_find, &bh);
1944 1945 1946 1947 1948 1949
	if (!dent) {
		gfs2_consist_inode(dip);
		return -EIO;
	}
	if (IS_ERR(dent))
		return PTR_ERR(dent);
D
David Teigland 已提交
1950

1951
	gfs2_trans_add_meta(dip->i_gl, bh);
1952
	gfs2_inum_out(nip, dent);
1953 1954
	dent->de_type = cpu_to_be16(new_type);

1955
	if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1956 1957 1958 1959
		brelse(bh);
		error = gfs2_meta_inode_buffer(dip, &bh);
		if (error)
			return error;
1960
		gfs2_trans_add_meta(dip->i_gl, bh);
1961 1962
	}

1963
	dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME;
1964
	gfs2_dinode_out(dip, bh->b_data);
1965 1966
	brelse(bh);
	return 0;
D
David Teigland 已提交
1967 1968 1969 1970 1971 1972 1973 1974
}

/**
 * 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
1975
 * @leaf_bh: buffer_head for the starting leaf
1976
 * last_dealloc: 1 if this is the final dealloc for the leaf, else 0
D
David Teigland 已提交
1977 1978 1979 1980
 *
 * Returns: errno
 */

1981
static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len,
1982 1983
			u64 leaf_no, struct buffer_head *leaf_bh,
			int last_dealloc)
D
David Teigland 已提交
1984
{
1985
	struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode);
1986
	struct gfs2_leaf *tmp_leaf;
D
David Teigland 已提交
1987 1988
	struct gfs2_rgrp_list rlist;
	struct buffer_head *bh, *dibh;
1989
	u64 blk, nblk;
D
David Teigland 已提交
1990 1991
	unsigned int rg_blocks = 0, l_blocks = 0;
	char *ht;
1992
	unsigned int x, size = len * sizeof(u64);
D
David Teigland 已提交
1993 1994
	int error;

1995 1996 1997 1998
	error = gfs2_rindex_update(sdp);
	if (error)
		return error;

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

2001
	ht = kzalloc(size, GFP_NOFS | __GFP_NOWARN);
2002
	if (ht == NULL)
2003 2004
		ht = __vmalloc(size, GFP_NOFS | __GFP_NOWARN | __GFP_ZERO,
			       PAGE_KERNEL);
D
David Teigland 已提交
2005 2006 2007
	if (!ht)
		return -ENOMEM;

2008
	error = gfs2_quota_hold(dip, NO_UID_QUOTA_CHANGE, NO_GID_QUOTA_CHANGE);
D
David Teigland 已提交
2009
	if (error)
2010
		goto out;
D
David Teigland 已提交
2011 2012

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

2015
	for (blk = leaf_no; blk; blk = nblk) {
2016 2017 2018 2019 2020
		if (blk != leaf_no) {
			error = get_leaf(dip, blk, &bh);
			if (error)
				goto out_rlist;
		}
2021 2022
		tmp_leaf = (struct gfs2_leaf *)bh->b_data;
		nblk = be64_to_cpu(tmp_leaf->lf_next);
2023 2024
		if (blk != leaf_no)
			brelse(bh);
D
David Teigland 已提交
2025

2026
		gfs2_rlist_add(dip, &rlist, blk);
D
David Teigland 已提交
2027 2028 2029
		l_blocks++;
	}

2030
	gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE);
D
David Teigland 已提交
2031 2032 2033

	for (x = 0; x < rlist.rl_rgrps; x++) {
		struct gfs2_rgrpd *rgd;
2034
		rgd = rlist.rl_ghs[x].gh_gl->gl_object;
2035
		rg_blocks += rgd->rd_length;
D
David Teigland 已提交
2036 2037 2038 2039 2040 2041 2042
	}

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

	error = gfs2_trans_begin(sdp,
2043
			rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) +
D
David Teigland 已提交
2044 2045 2046 2047
			RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks);
	if (error)
		goto out_rg_gunlock;

2048 2049
	bh = leaf_bh;

2050
	for (blk = leaf_no; blk; blk = nblk) {
2051 2052 2053 2054 2055
		if (blk != leaf_no) {
			error = get_leaf(dip, blk, &bh);
			if (error)
				goto out_end_trans;
		}
2056 2057
		tmp_leaf = (struct gfs2_leaf *)bh->b_data;
		nblk = be64_to_cpu(tmp_leaf->lf_next);
2058 2059
		if (blk != leaf_no)
			brelse(bh);
D
David Teigland 已提交
2060 2061

		gfs2_free_meta(dip, blk, 1);
2062
		gfs2_add_inode_blocks(&dip->i_inode, -1);
D
David Teigland 已提交
2063 2064
	}

2065
	error = gfs2_dir_write_data(dip, ht, index * sizeof(u64), size);
D
David Teigland 已提交
2066 2067 2068 2069 2070 2071 2072 2073 2074 2075
	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;

2076
	gfs2_trans_add_meta(dip->i_gl, dibh);
2077 2078 2079 2080
	/* 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;
2081
	gfs2_dinode_out(dip, dibh->b_data);
D
David Teigland 已提交
2082 2083
	brelse(dibh);

2084
out_end_trans:
D
David Teigland 已提交
2085
	gfs2_trans_end(sdp);
2086
out_rg_gunlock:
D
David Teigland 已提交
2087
	gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs);
2088
out_rlist:
D
David Teigland 已提交
2089 2090
	gfs2_rlist_free(&rlist);
	gfs2_quota_unhold(dip);
2091
out:
2092
	kvfree(ht);
D
David Teigland 已提交
2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107
	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)
{
2108 2109 2110 2111 2112 2113 2114 2115 2116 2117
	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;

2118 2119 2120
	lp = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(lp))
		return PTR_ERR(lp);
2121 2122

	while (index < hsize) {
2123
		leaf_no = be64_to_cpu(lp[index]);
2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150
		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 已提交
2151 2152 2153 2154 2155 2156
}

/**
 * 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
2157
 * @da: The structure to return dir alloc info
D
David Teigland 已提交
2158
 *
2159
 * Returns: 0 if ok, -ve on error
D
David Teigland 已提交
2160 2161
 */

2162 2163
int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name,
			       struct gfs2_diradd *da)
D
David Teigland 已提交
2164
{
2165
	struct gfs2_inode *ip = GFS2_I(inode);
2166
	struct gfs2_sbd *sdp = GFS2_SB(inode);
2167
	const unsigned int extra = sizeof(struct gfs2_dinode) - sizeof(struct gfs2_leaf);
2168 2169
	struct gfs2_dirent *dent;
	struct buffer_head *bh;
D
David Teigland 已提交
2170

2171
	da->nr_blocks = 0;
2172 2173
	da->bh = NULL;
	da->dent = NULL;
2174

2175
	dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh);
2176
	if (!dent) {
2177
		da->nr_blocks = sdp->sd_max_dirres;
2178 2179 2180
		if (!(ip->i_diskflags & GFS2_DIF_EXHASH) &&
		    (GFS2_DIRENT_SIZE(name->len) < extra))
			da->nr_blocks = 1;
2181
		return 0;
2182
	}
2183 2184
	if (IS_ERR(dent))
		return PTR_ERR(dent);
2185 2186 2187 2188 2189 2190 2191

	if (da->save_loc) {
		da->bh = bh;
		da->dent = dent;
	} else {
		brelse(bh);
	}
2192
	return 0;
D
David Teigland 已提交
2193 2194
}