dir.c 52.2 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>
65
#include <linux/bio.h>
D
David Teigland 已提交
66 67

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

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

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

84 85
#define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1)
#define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1))
86 87
#define GFS2_HASH_INDEX_MASK 0xffffc000
#define GFS2_USE_HASH_FLAG 0x2000
D
David Teigland 已提交
88

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

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

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

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

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

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

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;

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

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

	if (!size)
		return 0;

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

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

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

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

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

214 215 216
		if (error)
			goto fail;

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

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

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

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

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

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

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

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

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

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

335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
/**
 * 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;

F
Fabian Frederick 已提交
355
	hsize = BIT(ip->i_depth);
356 357 358 359 360 361
	hsize *= sizeof(__be64);
	if (hsize != i_size_read(&ip->i_inode)) {
		gfs2_consist_inode(ip);
		return ERR_PTR(-EIO);
	}

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

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

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

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

	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)
{
394 395 396 397
	__be64 *hc;

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

401
	kvfree(hc);
402 403
}

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

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

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

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

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

449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469
/* 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;
}

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

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

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

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

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

	BUG_ON(buf == NULL);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;
}


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

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

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

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

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

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

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

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

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

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

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

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

	return error;
}

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

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

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

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

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

852

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

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

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

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

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

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

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

	/*  Turn over a new leaf  */

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

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

	/*  Copy dirents  */

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

	/*  Find last entry  */

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

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

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

	brelse(bh);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1070 1071
	gfs2_dir_hash_inval(dip);

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

	kfree(lp);

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

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

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

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

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

			dirent_del(dip, obh, prev, dent);

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

			if (!prev)
				prev = dent;

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

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

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

	brelse(obh);
	brelse(nbh);

	return error;

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

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

F
Fabian Frederick 已提交
1167
	hsize = BIT(dip->i_depth);
1168
	hsize_bytes = hsize * sizeof(__be64);
D
David Teigland 已提交
1169

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

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

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

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

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

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

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

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

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

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

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

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

	return ret;
}

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

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

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

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

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

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

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

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

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

		*copied = 1;
	}

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

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

	return 0;
}

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

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 1374

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

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

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

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

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

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

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

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

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

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

F
Fabian Frederick 已提交
1543
	hsize = BIT(dip->i_depth);
A
Al Viro 已提交
1544
	hash = gfs2_dir_offset2hash(ctx->pos);
1545
	index = hash >> (32 - dip->i_depth);
D
David Teigland 已提交
1546

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

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

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

F
Fabian Frederick 已提交
1562
		len = BIT(dip->i_depth - depth);
D
David Teigland 已提交
1563 1564 1565
		index = (index & ~(len - 1)) + len;
	}

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

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

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

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

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

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

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

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

	brelse(dibh);

	return error;
}

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

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

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

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

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

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

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

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

1753
	gfs2_trans_add_meta(ip->i_gl, obh);
1754 1755 1756 1757 1758 1759

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

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

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

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

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

1869

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1997 1998 1999 2000
	error = gfs2_rindex_update(sdp);
	if (error)
		return error;

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

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

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

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

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

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

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

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

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

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

2050 2051
	bh = leaf_bh;

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

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

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

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

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

F
Fabian Frederick 已提交
2118
	hsize = BIT(dip->i_depth);
2119

2120 2121 2122
	lp = gfs2_dir_get_hash_table(dip);
	if (IS_ERR(lp))
		return PTR_ERR(lp);
2123 2124

	while (index < hsize) {
2125
		leaf_no = be64_to_cpu(lp[index]);
2126 2127 2128 2129 2130
		if (leaf_no) {
			error = get_leaf(dip, leaf_no, &bh);
			if (error)
				goto out;
			leaf = (struct gfs2_leaf *)bh->b_data;
F
Fabian Frederick 已提交
2131
			len = BIT(dip->i_depth - be16_to_cpu(leaf->lf_depth));
2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152

			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 已提交
2153 2154 2155 2156 2157 2158
}

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

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

2173
	da->nr_blocks = 0;
2174 2175
	da->bh = NULL;
	da->dent = NULL;
2176

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

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