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 timespec tv = current_time(inode);
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);
D
David Howells 已提交
898
	gfs2_qstr2dirent(&empty_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

F
Fabian Frederick 已提交
935
	gfs2_assert(sdp, dip->i_entries < BIT(16));
936
	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.  */
F
Fabian Frederick 已提交
1044
	len = BIT(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;

F
Fabian Frederick 已提交
1166
	hsize = BIT(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
				gfs2_consist_inode(ip);
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 1517 1518
			submit_bh(REQ_OP_READ,
				  REQ_RAHEAD | REQ_META | REQ_PRIO,
				  bh);
1519 1520 1521 1522 1523
			continue;
		}
		brelse(bh);
	}
}
1524

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	brelse(dibh);

	return error;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1870

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	for (x = 0; x < rlist.rl_rgrps; x++) {
2036 2037
		struct gfs2_rgrpd *rgd = gfs2_glock2rgrp(rlist.rl_ghs[x].gh_gl);

2038
		rg_blocks += rgd->rd_length;
D
David Teigland 已提交
2039 2040 2041 2042 2043 2044 2045
	}

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

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

2051 2052
	bh = leaf_bh;

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

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

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

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

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

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

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

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

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

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

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

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

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