git.oblomov.eu Git - linux-2.6/blob - fs/gfs2/dir.c

   1 /*
   2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
   3  * Copyright (C) 2004-2005 Red Hat, Inc.  All rights reserved.
   4  *
   5  * This copyrighted material is made available to anyone wishing to use,
   6  * modify, copy, or redistribute it subject to the terms and conditions
   7  * of the GNU General Public License v.2.
   8  */
   9
  10 /*
  11 * Implements Extendible Hashing as described in:
  12 *   "Extendible Hashing" by Fagin, et al in
  13 *     __ACM Trans. on Database Systems__, Sept 1979.
  14 *
  15 *
  16 * Here's the layout of dirents which is essentially the same as that of ext2
  17 * within a single block. The field de_name_len is the number of bytes
  18 * actually required for the name (no null terminator). The field de_rec_len
  19 * is the number of bytes allocated to the dirent. The offset of the next
  20 * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is
  21 * deleted, the preceding dirent inherits its allocated space, ie
  22 * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained
  23 * by adding de_rec_len to the current dirent, this essentially causes the
  24 * deleted dirent to get jumped over when iterating through all the dirents.
  25 *
  26 * When deleting the first dirent in a block, there is no previous dirent so
  27 * the field de_ino is set to zero to designate it as deleted. When allocating
  28 * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the
  29 * first dirent has (de_ino == 0) and de_rec_len is large enough, this first
  30 * dirent is allocated. Otherwise it must go through all the 'used' dirents
  31 * searching for one in which the amount of total space minus the amount of
  32 * used space will provide enough space for the new dirent.
  33 *
  34 * There are two types of blocks in which dirents reside. In a stuffed dinode,
  35 * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of
  36 * the block.  In leaves, they begin at offset sizeof(struct gfs2_leaf) from the
  37 * beginning of the leaf block. The dirents reside in leaves when
  38 *
  39 * dip->i_di.di_flags & GFS2_DIF_EXHASH is true
  40 *
  41 * Otherwise, the dirents are "linear", within a single stuffed dinode block.
  42 *
  43 * When the dirents are in leaves, the actual contents of the directory file are
  44 * used as an array of 64-bit block pointers pointing to the leaf blocks. The
  45 * dirents are NOT in the directory file itself. There can be more than one block
  46 * pointer in the array that points to the same leaf. In fact, when a directory
  47 * is first converted from linear to exhash, all of the pointers point to the
  48 * same leaf.
  49 *
  50 * When a leaf is completely full, the size of the hash table can be
  51 * doubled unless it is already at the maximum size which is hard coded into
  52 * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,
  53 * but never before the maximum hash table size has been reached.
  54 */
  55
  56 #include <linux/sched.h>
  57 #include <linux/slab.h>
  58 #include <linux/spinlock.h>
  59 #include <linux/completion.h>
  60 #include <linux/buffer_head.h>
  61 #include <linux/sort.h>
  62 #include <asm/semaphore.h>
  63
  64 #include "gfs2.h"
  65 #include "dir.h"
  66 #include "glock.h"
  67 #include "inode.h"
  68 #include "meta_io.h"
  69 #include "quota.h"
  70 #include "rgrp.h"
  71 #include "trans.h"
  72 #include "bmap.h"
  73
  74 #define IS_LEAF     1 /* Hashed (leaf) directory */
  75 #define IS_DINODE   2 /* Linear (stuffed dinode block) directory */
  76
  77 #if 1
  78 #define gfs2_disk_hash2offset(h) (((uint64_t)(h)) >> 1)
  79 #define gfs2_dir_offset2hash(p) ((uint32_t)(((uint64_t)(p)) << 1))
  80 #else
  81 #define gfs2_disk_hash2offset(h) (((uint64_t)(h)))
  82 #define gfs2_dir_offset2hash(p) ((uint32_t)(((uint64_t)(p))))
  83 #endif
  84
  85 typedef int (*leaf_call_t) (struct gfs2_inode *dip,
  86                             uint32_t index, uint32_t len, uint64_t leaf_no,
  87                             void *data);
  88
  89 int gfs2_dir_get_buffer(struct gfs2_inode *ip, uint64_t block, int new,
  90                          struct buffer_head **bhp)
  91 {
  92         struct buffer_head *bh;
  93         int error = 0;
  94
  95         if (new) {
  96                 bh = gfs2_meta_new(ip->i_gl, block);
  97                 gfs2_trans_add_bh(ip->i_gl, bh, 1);
  98                 gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
  99                 gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
 100         } else {
 101                 error = gfs2_meta_read(ip->i_gl, block, DIO_START | DIO_WAIT, &bh);
 102                 if (error)
 103                         return error;
 104                 if (gfs2_metatype_check(ip->i_sbd, bh, GFS2_METATYPE_JD)) {
 105                         brelse(bh);
 106                         return -EIO;
 107                 }
 108         }
 109
 110         *bhp = bh;
 111         return 0;
 112 }
 113
 114
 115
 116 static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
 117                                   unsigned int offset, unsigned int size)
 118
 119 {
 120         struct buffer_head *dibh;
 121         int error;
 122
 123         error = gfs2_meta_inode_buffer(ip, &dibh);
 124         if (error)
 125                 return error;
 126
 127         gfs2_trans_add_bh(ip->i_gl, dibh, 1);
 128         memcpy(dibh->b_data + offset + sizeof(struct gfs2_inode), buf, size);
 129         if (ip->i_di.di_size < offset + size)
 130                 ip->i_di.di_size = offset + size;
 131         ip->i_di.di_mtime = ip->i_di.di_ctime = get_seconds();
 132         gfs2_dinode_out(&ip->i_di, dibh->b_data);
 133
 134         brelse(dibh);
 135
 136         return size;
 137 }
 138
 139
 140
 141 /**
 142  * gfs2_dir_write_data - Write directory information to the inode
 143  * @ip: The GFS2 inode
 144  * @buf: The buffer containing information to be written
 145  * @offset: The file offset to start writing at
 146  * @size: The amount of data to write
 147  *
 148  * Returns: The number of bytes correctly written or error code
 149  */
 150 static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf,
 151                                uint64_t offset, unsigned int size)
 152 {
 153         struct gfs2_sbd *sdp = ip->i_sbd;
 154         struct buffer_head *dibh;
 155         uint64_t lblock, dblock;
 156         uint32_t extlen = 0;
 157         unsigned int o;
 158         int copied = 0;
 159         int error = 0;
 160
 161         if (!size)
 162                 return 0;
 163
 164         if (gfs2_is_stuffed(ip) &&
 165             offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode))
 166                 return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset, size);
 167
 168         if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
 169                 return -EINVAL;
 170
 171         if (gfs2_is_stuffed(ip)) {
 172                 error = gfs2_unstuff_dinode(ip, NULL, NULL);
 173                 if (error)
 174                 return error;
 175         }
 176
 177         lblock = offset;
 178         o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
 179
 180         while (copied < size) {
 181                 unsigned int amount;
 182                 struct buffer_head *bh;
 183                 int new;
 184
 185                 amount = size - copied;
 186                 if (amount > sdp->sd_sb.sb_bsize - o)
 187                         amount = sdp->sd_sb.sb_bsize - o;
 188
 189                 if (!extlen) {
 190                         new = 1;
 191                         error = gfs2_block_map(ip, lblock, &new, &dblock, &extlen);
 192                         if (error)
 193                                 goto fail;
 194                         error = -EIO;
 195                         if (gfs2_assert_withdraw(sdp, dblock))
 196                                 goto fail;
 197                 }
 198
 199                 error = gfs2_dir_get_buffer(ip, dblock, (amount == sdp->sd_jbsize) ? 1 : new, &bh);
 200                 if (error)
 201                         goto fail;
 202
 203                 gfs2_trans_add_bh(ip->i_gl, bh, 1);
 204                 memcpy(bh->b_data + o, buf, amount);
 205                 brelse(bh);
 206                 if (error)
 207                         goto fail;
 208
 209                 copied += amount;
 210                 lblock++;
 211                 dblock++;
 212                 extlen--;
 213
 214                 o = sizeof(struct gfs2_meta_header);
 215         }
 216
 217 out:
 218         error = gfs2_meta_inode_buffer(ip, &dibh);
 219         if (error)
 220                 return error;
 221
 222         if (ip->i_di.di_size < offset + copied)
 223                 ip->i_di.di_size = offset + copied;
 224         ip->i_di.di_mtime = ip->i_di.di_ctime = get_seconds();
 225
 226         gfs2_trans_add_bh(ip->i_gl, dibh, 1);
 227         gfs2_dinode_out(&ip->i_di, dibh->b_data);
 228         brelse(dibh);
 229
 230         return copied;
 231 fail:
 232         if (copied)
 233                 goto out;
 234         return error;
 235 }
 236
 237 static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, char *buf,
 238                                 unsigned int offset, unsigned int size)
 239 {
 240         struct buffer_head *dibh;
 241         int error;
 242
 243         error = gfs2_meta_inode_buffer(ip, &dibh);
 244         if (!error) {
 245                 offset += sizeof(struct gfs2_dinode);
 246                 memcpy(buf, dibh->b_data + offset, size);
 247                 brelse(dibh);
 248         }
 249
 250         return (error) ? error : size;
 251 }
 252
 253
 254 /**
 255  * gfs2_dir_read_data - Read a data from a directory inode
 256  * @ip: The GFS2 Inode
 257  * @buf: The buffer to place result into
 258  * @offset: File offset to begin jdata_readng from
 259  * @size: Amount of data to transfer
 260  *
 261  * Returns: The amount of data actually copied or the error
 262  */
 263 static int gfs2_dir_read_data(struct gfs2_inode *ip, char *buf,
 264                               uint64_t offset, unsigned int size)
 265 {
 266         struct gfs2_sbd *sdp = ip->i_sbd;
 267         uint64_t lblock, dblock;
 268         uint32_t extlen = 0;
 269         unsigned int o;
 270         int copied = 0;
 271         int error = 0;
 272
 273         if (offset >= ip->i_di.di_size)
 274                 return 0;
 275
 276         if ((offset + size) > ip->i_di.di_size)
 277                 size = ip->i_di.di_size - offset;
 278
 279         if (!size)
 280                 return 0;
 281
 282         if (gfs2_is_stuffed(ip))
 283                 return gfs2_dir_read_stuffed(ip, buf, (unsigned int)offset, size);
 284
 285         if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
 286                 return -EINVAL;
 287
 288         lblock = offset;
 289         o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
 290
 291         while (copied < size) {
 292                 unsigned int amount;
 293                 struct buffer_head *bh;
 294                 int new;
 295
 296                 amount = size - copied;
 297                 if (amount > sdp->sd_sb.sb_bsize - o)
 298                         amount = sdp->sd_sb.sb_bsize - o;
 299
 300                 if (!extlen) {
 301                         new = 0;
 302                         error = gfs2_block_map(ip, lblock, &new, &dblock, &extlen);
 303                         if (error)
 304                                 goto fail;
 305                 }
 306
 307                 if (extlen > 1)
 308                         gfs2_meta_ra(ip->i_gl, dblock, extlen);
 309
 310                 if (dblock) {
 311                         error = gfs2_dir_get_buffer(ip, dblock, new, &bh);
 312                         if (error)
 313                                 goto fail;
 314                         dblock++;
 315                         extlen--;
 316                 } else
 317                         bh = NULL;
 318
 319                 memcpy(buf, bh->b_data + o, amount);
 320                 brelse(bh);
 321                 if (error)
 322                         goto fail;
 323
 324                 copied += amount;
 325                 lblock++;
 326
 327                 o = sizeof(struct gfs2_meta_header);
 328         }
 329
 330         return copied;
 331 fail:
 332         return (copied) ? copied : error;
 333 }
 334
 335 /**
 336  * int gfs2_filecmp - Compare two filenames
 337  * @file1: The first filename
 338  * @file2: The second filename
 339  * @len_of_file2: The length of the second file
 340  *
 341  * This routine compares two filenames and returns 1 if they are equal.
 342  *
 343  * Returns: 1 if the files are the same, otherwise 0.
 344  */
 345
 346 int gfs2_filecmp(struct qstr *file1, char *file2, int len_of_file2)
 347 {
 348         if (file1->len != len_of_file2)
 349                 return 0;
 350         if (memcmp(file1->name, file2, file1->len))
 351                 return 0;
 352         return 1;
 353 }
 354
 355 /**
 356  * dirent_first - Return the first dirent
 357  * @dip: the directory
 358  * @bh: The buffer
 359  * @dent: Pointer to list of dirents
 360  *
 361  * return first dirent whether bh points to leaf or stuffed dinode
 362  *
 363  * Returns: IS_LEAF, IS_DINODE, or -errno
 364  */
 365
 366 static int dirent_first(struct gfs2_inode *dip, struct buffer_head *bh,
 367                         struct gfs2_dirent **dent)
 368 {
 369         struct gfs2_meta_header *h = (struct gfs2_meta_header *)bh->b_data;
 370
 371         if (be16_to_cpu(h->mh_type) == GFS2_METATYPE_LF) {
 372                 if (gfs2_meta_check(dip->i_sbd, bh))
 373                         return -EIO;
 374                 *dent = (struct gfs2_dirent *)(bh->b_data +
 375                                                sizeof(struct gfs2_leaf));
 376                 return IS_LEAF;
 377         } else {
 378                 if (gfs2_metatype_check(dip->i_sbd, bh, GFS2_METATYPE_DI))
 379                         return -EIO;
 380                 *dent = (struct gfs2_dirent *)(bh->b_data +
 381                                                sizeof(struct gfs2_dinode));
 382                 return IS_DINODE;
 383         }
 384 }
 385
 386 /**
 387  * dirent_next - Next dirent
 388  * @dip: the directory
 389  * @bh: The buffer
 390  * @dent: Pointer to list of dirents
 391  *
 392  * Returns: 0 on success, error code otherwise
 393  */
 394
 395 static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,
 396                        struct gfs2_dirent **dent)
 397 {
 398         struct gfs2_dirent *tmp, *cur;
 399         char *bh_end;
 400         uint16_t cur_rec_len;
 401
 402         cur = *dent;
 403         bh_end = bh->b_data + bh->b_size;
 404         cur_rec_len = be16_to_cpu(cur->de_rec_len);
 405
 406         if ((char *)cur + cur_rec_len >= bh_end) {
 407                 if ((char *)cur + cur_rec_len > bh_end) {
 408                         gfs2_consist_inode(dip);
 409                         return -EIO;
 410                 }
 411                 return -ENOENT;
 412         }
 413
 414         tmp = (struct gfs2_dirent *)((char *)cur + cur_rec_len);
 415
 416         if ((char *)tmp + be16_to_cpu(tmp->de_rec_len) > bh_end) {
 417                 gfs2_consist_inode(dip);
 418                 return -EIO;
 419         }
 420
 421         if (cur_rec_len == 0) {
 422                 gfs2_consist_inode(dip);
 423                 return -EIO;
 424         }
 425
 426         /* Only the first dent could ever have de_inum.no_addr == 0 */
 427         if (!tmp->de_inum.no_addr) {
 428                 gfs2_consist_inode(dip);
 429                 return -EIO;
 430         }
 431
 432         *dent = tmp;
 433
 434         return 0;
 435 }
 436
 437 /**
 438  * dirent_del - Delete a dirent
 439  * @dip: The GFS2 inode
 440  * @bh: The buffer
 441  * @prev: The previous dirent
 442  * @cur: The current dirent
 443  *
 444  */
 445
 446 static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,
 447                        struct gfs2_dirent *prev, struct gfs2_dirent *cur)
 448 {
 449         uint16_t cur_rec_len, prev_rec_len;
 450
 451         if (!cur->de_inum.no_addr) {
 452                 gfs2_consist_inode(dip);
 453                 return;
 454         }
 455
 456         gfs2_trans_add_bh(dip->i_gl, bh, 1);
 457
 458         /* If there is no prev entry, this is the first entry in the block.
 459            The de_rec_len is already as big as it needs to be.  Just zero
 460            out the inode number and return.  */
 461
 462         if (!prev) {
 463                 cur->de_inum.no_addr = 0;       /* No endianess worries */
 464                 return;
 465         }
 466
 467         /*  Combine this dentry with the previous one.  */
 468
 469         prev_rec_len = be16_to_cpu(prev->de_rec_len);
 470         cur_rec_len = be16_to_cpu(cur->de_rec_len);
 471
 472         if ((char *)prev + prev_rec_len != (char *)cur)
 473                 gfs2_consist_inode(dip);
 474         if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)
 475                 gfs2_consist_inode(dip);
 476
 477         prev_rec_len += cur_rec_len;
 478         prev->de_rec_len = cpu_to_be16(prev_rec_len);
 479 }
 480
 481 /**
 482  * gfs2_dirent_alloc - Allocate a directory entry
 483  * @dip: The GFS2 inode
 484  * @bh: The buffer
 485  * @name_len: The length of the name
 486  * @dent_out: Pointer to list of dirents
 487  *
 488  * Returns: 0 on success, error code otherwise
 489  */
 490
 491 int gfs2_dirent_alloc(struct gfs2_inode *dip, struct buffer_head *bh,
 492                       int name_len, struct gfs2_dirent **dent_out)
 493 {
 494         struct gfs2_dirent *dent, *new;
 495         unsigned int rec_len = GFS2_DIRENT_SIZE(name_len);
 496         unsigned int entries = 0, offset = 0;
 497         int type;
 498
 499         type = dirent_first(dip, bh, &dent);
 500         if (type < 0)
 501                 return type;
 502
 503         if (type == IS_LEAF) {
 504                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
 505                 entries = be16_to_cpu(leaf->lf_entries);
 506                 offset = sizeof(struct gfs2_leaf);
 507         } else {
 508                 struct gfs2_dinode *dinode = (struct gfs2_dinode *)bh->b_data;
 509                 entries = be32_to_cpu(dinode->di_entries);
 510                 offset = sizeof(struct gfs2_dinode);
 511         }
 512
 513         if (!entries) {
 514                 if (dent->de_inum.no_addr) {
 515                         gfs2_consist_inode(dip);
 516                         return -EIO;
 517                 }
 518
 519                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
 520
 521                 dent->de_rec_len = cpu_to_be16(bh->b_size - offset);
 522                 dent->de_name_len = cpu_to_be16(name_len);
 523
 524                 *dent_out = dent;
 525                 return 0;
 526         }
 527
 528         do {
 529                 uint16_t cur_rec_len;
 530                 uint16_t cur_name_len;
 531
 532                 cur_rec_len = be16_to_cpu(dent->de_rec_len);
 533                 cur_name_len = be16_to_cpu(dent->de_name_len);
 534
 535                 if ((!dent->de_inum.no_addr && cur_rec_len >= rec_len) ||
 536                     (cur_rec_len >= GFS2_DIRENT_SIZE(cur_name_len) + rec_len)) {
 537                         gfs2_trans_add_bh(dip->i_gl, bh, 1);
 538
 539                         if (dent->de_inum.no_addr) {
 540                                 new = (struct gfs2_dirent *)((char *)dent +
 541                                                             GFS2_DIRENT_SIZE(cur_name_len));
 542                                 memset(new, 0, sizeof(struct gfs2_dirent));
 543
 544                                 new->de_rec_len = cpu_to_be16(cur_rec_len - GFS2_DIRENT_SIZE(cur_name_len));
 545                                 new->de_name_len = cpu_to_be16(name_len);
 546
 547                                 dent->de_rec_len = cpu_to_be16(cur_rec_len - be16_to_cpu(new->de_rec_len));
 548
 549                                 *dent_out = new;
 550                                 return 0;
 551                         }
 552
 553                         dent->de_name_len = cpu_to_be16(name_len);
 554
 555                         *dent_out = dent;
 556                         return 0;
 557                 }
 558         } while (dirent_next(dip, bh, &dent) == 0);
 559
 560         return -ENOSPC;
 561 }
 562
 563 /**
 564  * dirent_fits - See if we can fit a entry in this buffer
 565  * @dip: The GFS2 inode
 566  * @bh: The buffer
 567  * @name_len: The length of the name
 568  *
 569  * Returns: 1 if it can fit, 0 otherwise
 570  */
 571
 572 static int dirent_fits(struct gfs2_inode *dip, struct buffer_head *bh,
 573                        int name_len)
 574 {
 575         struct gfs2_dirent *dent;
 576         unsigned int rec_len = GFS2_DIRENT_SIZE(name_len);
 577         unsigned int entries = 0;
 578         int type;
 579
 580         type = dirent_first(dip, bh, &dent);
 581         if (type < 0)
 582                 return type;
 583
 584         if (type == IS_LEAF) {
 585                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
 586                 entries = be16_to_cpu(leaf->lf_entries);
 587         } else {
 588                 struct gfs2_dinode *dinode = (struct gfs2_dinode *)bh->b_data;
 589                 entries = be32_to_cpu(dinode->di_entries);
 590         }
 591
 592         if (!entries)
 593                 return 1;
 594
 595         do {
 596                 uint16_t cur_rec_len;
 597                 uint32_t cur_name_len;
 598
 599                 cur_rec_len = be16_to_cpu(dent->de_rec_len);
 600                 cur_name_len = be16_to_cpu(dent->de_name_len);
 601
 602                 if ((!dent->de_inum.no_addr && cur_rec_len >= rec_len) ||
 603                     (cur_rec_len >= GFS2_DIRENT_SIZE(cur_name_len) + rec_len))
 604                         return 1;
 605         } while (dirent_next(dip, bh, &dent) == 0);
 606
 607         return 0;
 608 }
 609
 610 static int leaf_search(struct gfs2_inode *dip, struct buffer_head *bh,
 611                        struct qstr *filename, struct gfs2_dirent **dent_out,
 612                        struct gfs2_dirent **dent_prev)
 613 {
 614         uint32_t hash;
 615         struct gfs2_dirent *dent, *prev = NULL;
 616         unsigned int entries = 0;
 617         int type;
 618
 619         type = dirent_first(dip, bh, &dent);
 620         if (type < 0)
 621                 return type;
 622
 623         if (type == IS_LEAF) {
 624                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
 625                 entries = be16_to_cpu(leaf->lf_entries);
 626         } else if (type == IS_DINODE) {
 627                 struct gfs2_dinode *dinode = (struct gfs2_dinode *)bh->b_data;
 628                 entries = be32_to_cpu(dinode->di_entries);
 629         }
 630
 631         hash = gfs2_disk_hash(filename->name, filename->len);
 632
 633         do {
 634                 if (!dent->de_inum.no_addr) {
 635                         prev = dent;
 636                         continue;
 637                 }
 638
 639                 if (be32_to_cpu(dent->de_hash) == hash &&
 640                     gfs2_filecmp(filename, (char *)(dent + 1),
 641                                  be16_to_cpu(dent->de_name_len))) {
 642                         *dent_out = dent;
 643                         if (dent_prev)
 644                                 *dent_prev = prev;
 645
 646                         return 0;
 647                 }
 648
 649                 prev = dent;
 650         } while (dirent_next(dip, bh, &dent) == 0);
 651
 652         return -ENOENT;
 653 }
 654
 655 static int get_leaf(struct gfs2_inode *dip, uint64_t leaf_no,
 656                     struct buffer_head **bhp)
 657 {
 658         int error;
 659
 660         error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_START | DIO_WAIT, bhp);
 661         if (!error && gfs2_metatype_check(dip->i_sbd, *bhp, GFS2_METATYPE_LF))
 662                 error = -EIO;
 663
 664         return error;
 665 }
 666
 667 /**
 668  * get_leaf_nr - Get a leaf number associated with the index
 669  * @dip: The GFS2 inode
 670  * @index:
 671  * @leaf_out:
 672  *
 673  * Returns: 0 on success, error code otherwise
 674  */
 675
 676 static int get_leaf_nr(struct gfs2_inode *dip, uint32_t index,
 677                        uint64_t *leaf_out)
 678 {
 679         uint64_t leaf_no;
 680         int error;
 681
 682         error = gfs2_dir_read_data(dip, (char *)&leaf_no,
 683                                     index * sizeof(uint64_t),
 684                                     sizeof(uint64_t));
 685         if (error != sizeof(uint64_t))
 686                 return (error < 0) ? error : -EIO;
 687
 688         *leaf_out = be64_to_cpu(leaf_no);
 689
 690         return 0;
 691 }
 692
 693 static int get_first_leaf(struct gfs2_inode *dip, uint32_t index,
 694                           struct buffer_head **bh_out)
 695 {
 696         uint64_t leaf_no;
 697         int error;
 698
 699         error = get_leaf_nr(dip, index, &leaf_no);
 700         if (!error)
 701                 error = get_leaf(dip, leaf_no, bh_out);
 702
 703         return error;
 704 }
 705
 706 static int get_next_leaf(struct gfs2_inode *dip, struct buffer_head *bh_in,
 707                          struct buffer_head **bh_out)
 708 {
 709         struct gfs2_leaf *leaf;
 710         int error;
 711
 712         leaf = (struct gfs2_leaf *)bh_in->b_data;
 713
 714         if (!leaf->lf_next)
 715                 error = -ENOENT;
 716         else
 717                 error = get_leaf(dip, be64_to_cpu(leaf->lf_next), bh_out);
 718
 719         return error;
 720 }
 721
 722 static int linked_leaf_search(struct gfs2_inode *dip, struct qstr *filename,
 723                               struct gfs2_dirent **dent_out,
 724                               struct gfs2_dirent **dent_prev,
 725                               struct buffer_head **bh_out)
 726 {
 727         struct buffer_head *bh = NULL, *bh_next;
 728         uint32_t hsize, index;
 729         uint32_t hash;
 730         int error;
 731
 732         hsize = 1 << dip->i_di.di_depth;
 733         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
 734                 gfs2_consist_inode(dip);
 735                 return -EIO;
 736         }
 737
 738         /*  Figure out the address of the leaf node.  */
 739
 740         hash = gfs2_disk_hash(filename->name, filename->len);
 741         index = hash >> (32 - dip->i_di.di_depth);
 742
 743         error = get_first_leaf(dip, index, &bh_next);
 744         if (error)
 745                 return error;
 746
 747         /*  Find the entry  */
 748
 749         do {
 750                 brelse(bh);
 751
 752                 bh = bh_next;
 753
 754                 error = leaf_search(dip, bh, filename, dent_out, dent_prev);
 755                 switch (error) {
 756                 case 0:
 757                         *bh_out = bh;
 758                         return 0;
 759
 760                 case -ENOENT:
 761                         break;
 762
 763                 default:
 764                         brelse(bh);
 765                         return error;
 766                 }
 767
 768                 error = get_next_leaf(dip, bh, &bh_next);
 769         }
 770         while (!error);
 771
 772         brelse(bh);
 773
 774         return error;
 775 }
 776
 777 /**
 778  * dir_make_exhash - Convert a stuffed directory into an ExHash directory
 779  * @dip: The GFS2 inode
 780  *
 781  * Returns: 0 on success, error code otherwise
 782  */
 783
 784 static int dir_make_exhash(struct gfs2_inode *dip)
 785 {
 786         struct gfs2_sbd *sdp = dip->i_sbd;
 787         struct gfs2_dirent *dent;
 788         struct buffer_head *bh, *dibh;
 789         struct gfs2_leaf *leaf;
 790         int y;
 791         uint32_t x;
 792         uint64_t *lp, bn;
 793         int error;
 794
 795         error = gfs2_meta_inode_buffer(dip, &dibh);
 796         if (error)
 797                 return error;
 798
 799         /*  Allocate a new block for the first leaf node  */
 800
 801         bn = gfs2_alloc_meta(dip);
 802
 803         /*  Turn over a new leaf  */
 804
 805         bh = gfs2_meta_new(dip->i_gl, bn);
 806         gfs2_trans_add_bh(dip->i_gl, bh, 1);
 807         gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
 808         gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
 809
 810         /*  Fill in the leaf structure  */
 811
 812         leaf = (struct gfs2_leaf *)bh->b_data;
 813
 814         gfs2_assert(sdp, dip->i_di.di_entries < (1 << 16));
 815
 816         leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
 817         leaf->lf_entries = cpu_to_be16(dip->i_di.di_entries);
 818
 819         /*  Copy dirents  */
 820
 821         gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh,
 822                              sizeof(struct gfs2_dinode));
 823
 824         /*  Find last entry  */
 825
 826         x = 0;
 827         dirent_first(dip, bh, &dent);
 828
 829         do {
 830                 if (!dent->de_inum.no_addr)
 831                         continue;
 832                 if (++x == dip->i_di.di_entries)
 833                         break;
 834         }
 835         while (dirent_next(dip, bh, &dent) == 0);
 836
 837         /*  Adjust the last dirent's record length
 838            (Remember that dent still points to the last entry.)  */
 839
 840         dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) +
 841                 sizeof(struct gfs2_dinode) -
 842                 sizeof(struct gfs2_leaf));
 843
 844         brelse(bh);
 845
 846         /*  We're done with the new leaf block, now setup the new
 847             hash table.  */
 848
 849         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
 850         gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode));
 851
 852         lp = (uint64_t *)(dibh->b_data + sizeof(struct gfs2_dinode));
 853
 854         for (x = sdp->sd_hash_ptrs; x--; lp++)
 855                 *lp = cpu_to_be64(bn);
 856
 857         dip->i_di.di_size = sdp->sd_sb.sb_bsize / 2;
 858         dip->i_di.di_blocks++;
 859         dip->i_di.di_flags |= GFS2_DIF_EXHASH;
 860         dip->i_di.di_payload_format = 0;
 861
 862         for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ;
 863         dip->i_di.di_depth = y;
 864
 865         gfs2_dinode_out(&dip->i_di, dibh->b_data);
 866
 867         brelse(dibh);
 868
 869         return 0;
 870 }
 871
 872 /**
 873  * dir_split_leaf - Split a leaf block into two
 874  * @dip: The GFS2 inode
 875  * @index:
 876  * @leaf_no:
 877  *
 878  * Returns: 0 on success, error code on failure
 879  */
 880
 881 static int dir_split_leaf(struct gfs2_inode *dip, uint32_t index,
 882                           uint64_t leaf_no)
 883 {
 884         struct buffer_head *nbh, *obh, *dibh;
 885         struct gfs2_leaf *nleaf, *oleaf;
 886         struct gfs2_dirent *dent, *prev = NULL, *next = NULL, *new;
 887         uint32_t start, len, half_len, divider;
 888         uint64_t bn, *lp;
 889         uint32_t name_len;
 890         int x, moved = 0;
 891         int error;
 892
 893         /*  Allocate the new leaf block  */
 894
 895         bn = gfs2_alloc_meta(dip);
 896
 897         /*  Get the new leaf block  */
 898
 899         nbh = gfs2_meta_new(dip->i_gl, bn);
 900         gfs2_trans_add_bh(dip->i_gl, nbh, 1);
 901         gfs2_metatype_set(nbh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
 902         gfs2_buffer_clear_tail(nbh, sizeof(struct gfs2_meta_header));
 903
 904         nleaf = (struct gfs2_leaf *)nbh->b_data;
 905
 906         nleaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
 907
 908         /*  Get the old leaf block  */
 909
 910         error = get_leaf(dip, leaf_no, &obh);
 911         if (error)
 912                 goto fail;
 913
 914         gfs2_trans_add_bh(dip->i_gl, obh, 1);
 915
 916         oleaf = (struct gfs2_leaf *)obh->b_data;
 917
 918         /*  Compute the start and len of leaf pointers in the hash table.  */
 919
 920         len = 1 << (dip->i_di.di_depth - be16_to_cpu(oleaf->lf_depth));
 921         half_len = len >> 1;
 922         if (!half_len) {
 923                 gfs2_consist_inode(dip);
 924                 error = -EIO;
 925                 goto fail_brelse;
 926         }
 927
 928         start = (index & ~(len - 1));
 929
 930         /* Change the pointers.
 931            Don't bother distinguishing stuffed from non-stuffed.
 932            This code is complicated enough already. */
 933
 934         lp = kcalloc(half_len, sizeof(uint64_t), GFP_KERNEL | __GFP_NOFAIL);
 935
 936         error = gfs2_dir_read_data(dip, (char *)lp, start * sizeof(uint64_t),
 937                                     half_len * sizeof(uint64_t));
 938         if (error != half_len * sizeof(uint64_t)) {
 939                 if (error >= 0)
 940                         error = -EIO;
 941                 goto fail_lpfree;
 942         }
 943
 944         /*  Change the pointers  */
 945
 946         for (x = 0; x < half_len; x++)
 947                 lp[x] = cpu_to_be64(bn);
 948
 949         error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(uint64_t),
 950                                      half_len * sizeof(uint64_t));
 951         if (error != half_len * sizeof(uint64_t)) {
 952                 if (error >= 0)
 953                         error = -EIO;
 954                 goto fail_lpfree;
 955         }
 956
 957         kfree(lp);
 958
 959         /*  Compute the divider  */
 960
 961         divider = (start + half_len) << (32 - dip->i_di.di_depth);
 962
 963         /*  Copy the entries  */
 964
 965         dirent_first(dip, obh, &dent);
 966
 967         do {
 968                 next = dent;
 969                 if (dirent_next(dip, obh, &next))
 970                         next = NULL;
 971
 972                 if (dent->de_inum.no_addr &&
 973                     be32_to_cpu(dent->de_hash) < divider) {
 974                         name_len = be16_to_cpu(dent->de_name_len);
 975
 976                         gfs2_dirent_alloc(dip, nbh, name_len, &new);
 977
 978                         new->de_inum = dent->de_inum; /* No endian worries */
 979                         new->de_hash = dent->de_hash; /* No endian worries */
 980                         new->de_type = dent->de_type; /* No endian worries */
 981                         memcpy((char *)(new + 1), (char *)(dent + 1),
 982                                name_len);
 983
 984                         nleaf->lf_entries = be16_to_cpu(nleaf->lf_entries)+1;
 985                         nleaf->lf_entries = cpu_to_be16(nleaf->lf_entries);
 986
 987                         dirent_del(dip, obh, prev, dent);
 988
 989                         if (!oleaf->lf_entries)
 990                                 gfs2_consist_inode(dip);
 991                         oleaf->lf_entries = be16_to_cpu(oleaf->lf_entries)-1;
 992                         oleaf->lf_entries = cpu_to_be16(oleaf->lf_entries);
 993
 994                         if (!prev)
 995                                 prev = dent;
 996
 997                         moved = 1;
 998                 } else
 999                         prev = dent;
1000
1001                 dent = next;
1002         }
1003         while (dent);
1004
1005         /* If none of the entries got moved into the new leaf,
1006            artificially fill in the first entry. */
1007
1008         if (!moved) {
1009                 gfs2_dirent_alloc(dip, nbh, 0, &new);
1010                 new->de_inum.no_addr = 0;
1011         }
1012
1013         oleaf->lf_depth = be16_to_cpu(oleaf->lf_depth) + 1;
1014         oleaf->lf_depth = cpu_to_be16(oleaf->lf_depth);
1015         nleaf->lf_depth = oleaf->lf_depth;
1016
1017         error = gfs2_meta_inode_buffer(dip, &dibh);
1018         if (!gfs2_assert_withdraw(dip->i_sbd, !error)) {
1019                 dip->i_di.di_blocks++;
1020                 gfs2_dinode_out(&dip->i_di, dibh->b_data);
1021                 brelse(dibh);
1022         }
1023
1024         brelse(obh);
1025         brelse(nbh);
1026
1027         return error;
1028
1029  fail_lpfree:
1030         kfree(lp);
1031
1032  fail_brelse:
1033         brelse(obh);
1034
1035  fail:
1036         brelse(nbh);
1037         return error;
1038 }
1039
1040 /**
1041  * dir_double_exhash - Double size of ExHash table
1042  * @dip: The GFS2 dinode
1043  *
1044  * Returns: 0 on success, error code on failure
1045  */
1046
1047 static int dir_double_exhash(struct gfs2_inode *dip)
1048 {
1049         struct gfs2_sbd *sdp = dip->i_sbd;
1050         struct buffer_head *dibh;
1051         uint32_t hsize;
1052         uint64_t *buf;
1053         uint64_t *from, *to;
1054         uint64_t block;
1055         int x;
1056         int error = 0;
1057
1058         hsize = 1 << dip->i_di.di_depth;
1059         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
1060                 gfs2_consist_inode(dip);
1061                 return -EIO;
1062         }
1063
1064         /*  Allocate both the "from" and "to" buffers in one big chunk  */
1065
1066         buf = kcalloc(3, sdp->sd_hash_bsize, GFP_KERNEL | __GFP_NOFAIL);
1067
1068         for (block = dip->i_di.di_size >> sdp->sd_hash_bsize_shift; block--;) {
1069                 error = gfs2_dir_read_data(dip, (char *)buf,
1070                                             block * sdp->sd_hash_bsize,
1071                                             sdp->sd_hash_bsize);
1072                 if (error != sdp->sd_hash_bsize) {
1073                         if (error >= 0)
1074                                 error = -EIO;
1075                         goto fail;
1076                 }
1077
1078                 from = buf;
1079                 to = (uint64_t *)((char *)buf + sdp->sd_hash_bsize);
1080
1081                 for (x = sdp->sd_hash_ptrs; x--; from++) {
1082                         *to++ = *from;  /*  No endianess worries  */
1083                         *to++ = *from;
1084                 }
1085
1086                 error = gfs2_dir_write_data(dip,
1087                                              (char *)buf + sdp->sd_hash_bsize,
1088                                              block * sdp->sd_sb.sb_bsize,
1089                                              sdp->sd_sb.sb_bsize);
1090                 if (error != sdp->sd_sb.sb_bsize) {
1091                         if (error >= 0)
1092                                 error = -EIO;
1093                         goto fail;
1094                 }
1095         }
1096
1097         kfree(buf);
1098
1099         error = gfs2_meta_inode_buffer(dip, &dibh);
1100         if (!gfs2_assert_withdraw(sdp, !error)) {
1101                 dip->i_di.di_depth++;
1102                 gfs2_dinode_out(&dip->i_di, dibh->b_data);
1103                 brelse(dibh);
1104         }
1105
1106         return error;
1107
1108  fail:
1109         kfree(buf);
1110
1111         return error;
1112 }
1113
1114 /**
1115  * compare_dents - compare directory entries by hash value
1116  * @a: first dent
1117  * @b: second dent
1118  *
1119  * When comparing the hash entries of @a to @b:
1120  *   gt: returns 1
1121  *   lt: returns -1
1122  *   eq: returns 0
1123  */
1124
1125 static int compare_dents(const void *a, const void *b)
1126 {
1127         struct gfs2_dirent *dent_a, *dent_b;
1128         uint32_t hash_a, hash_b;
1129         int ret = 0;
1130
1131         dent_a = *(struct gfs2_dirent **)a;
1132         hash_a = dent_a->de_hash;
1133         hash_a = be32_to_cpu(hash_a);
1134
1135         dent_b = *(struct gfs2_dirent **)b;
1136         hash_b = dent_b->de_hash;
1137         hash_b = be32_to_cpu(hash_b);
1138
1139         if (hash_a > hash_b)
1140                 ret = 1;
1141         else if (hash_a < hash_b)
1142                 ret = -1;
1143         else {
1144                 unsigned int len_a = be16_to_cpu(dent_a->de_name_len);
1145                 unsigned int len_b = be16_to_cpu(dent_b->de_name_len);
1146
1147                 if (len_a > len_b)
1148                         ret = 1;
1149                 else if (len_a < len_b)
1150                         ret = -1;
1151                 else
1152                         ret = memcmp((char *)(dent_a + 1),
1153                                      (char *)(dent_b + 1),
1154                                      len_a);
1155         }
1156
1157         return ret;
1158 }
1159
1160 /**
1161  * do_filldir_main - read out directory entries
1162  * @dip: The GFS2 inode
1163  * @offset: The offset in the file to read from
1164  * @opaque: opaque data to pass to filldir
1165  * @filldir: The function to pass entries to
1166  * @darr: an array of struct gfs2_dirent pointers to read
1167  * @entries: the number of entries in darr
1168  * @copied: pointer to int that's non-zero if a entry has been copied out
1169  *
1170  * Jump through some hoops to make sure that if there are hash collsions,
1171  * they are read out at the beginning of a buffer.  We want to minimize
1172  * the possibility that they will fall into different readdir buffers or
1173  * that someone will want to seek to that location.
1174  *
1175  * Returns: errno, >0 on exception from filldir
1176  */
1177
1178 static int do_filldir_main(struct gfs2_inode *dip, uint64_t *offset,
1179                            void *opaque, gfs2_filldir_t filldir,
1180                            struct gfs2_dirent **darr, uint32_t entries,
1181                            int *copied)
1182 {
1183         struct gfs2_dirent *dent, *dent_next;
1184         struct gfs2_inum inum;
1185         uint64_t off, off_next;
1186         unsigned int x, y;
1187         int run = 0;
1188         int error = 0;
1189
1190         sort(darr, entries, sizeof(struct gfs2_dirent *), compare_dents, NULL);
1191
1192         dent_next = darr[0];
1193         off_next = be32_to_cpu(dent_next->de_hash);
1194         off_next = gfs2_disk_hash2offset(off_next);
1195
1196         for (x = 0, y = 1; x < entries; x++, y++) {
1197                 dent = dent_next;
1198                 off = off_next;
1199
1200                 if (y < entries) {
1201                         dent_next = darr[y];
1202                         off_next = be32_to_cpu(dent_next->de_hash);
1203                         off_next = gfs2_disk_hash2offset(off_next);
1204
1205                         if (off < *offset)
1206                                 continue;
1207                         *offset = off;
1208
1209                         if (off_next == off) {
1210                                 if (*copied && !run)
1211                                         return 1;
1212                                 run = 1;
1213                         } else
1214                                 run = 0;
1215                 } else {
1216                         if (off < *offset)
1217                                 continue;
1218                         *offset = off;
1219                 }
1220
1221                 gfs2_inum_in(&inum, (char *)&dent->de_inum);
1222
1223                 error = filldir(opaque, (char *)(dent + 1),
1224                                 be16_to_cpu(dent->de_name_len),
1225                                 off, &inum,
1226                                 be16_to_cpu(dent->de_type));
1227                 if (error)
1228                         return 1;
1229
1230                 *copied = 1;
1231         }
1232
1233         /* Increment the *offset by one, so the next time we come into the
1234            do_filldir fxn, we get the next entry instead of the last one in the
1235            current leaf */
1236
1237         (*offset)++;
1238
1239         return 0;
1240 }
1241
1242 /**
1243  * do_filldir_single - Read directory entries out of a single block
1244  * @dip: The GFS2 inode
1245  * @offset: The offset in the file to read from
1246  * @opaque: opaque data to pass to filldir
1247  * @filldir: The function to pass entries to
1248  * @bh: the block
1249  * @entries: the number of entries in the block
1250  * @copied: pointer to int that's non-zero if a entry has been copied out
1251  *
1252  * Returns: errno, >0 on exception from filldir
1253  */
1254
1255 static int do_filldir_single(struct gfs2_inode *dip, uint64_t *offset,
1256                              void *opaque, gfs2_filldir_t filldir,
1257                              struct buffer_head *bh, uint32_t entries,
1258                              int *copied)
1259 {
1260         struct gfs2_dirent **darr;
1261         struct gfs2_dirent *de;
1262         unsigned int e = 0;
1263         int error;
1264
1265         if (!entries)
1266                 return 0;
1267
1268         darr = kcalloc(entries, sizeof(struct gfs2_dirent *), GFP_KERNEL);
1269         if (!darr)
1270                 return -ENOMEM;
1271
1272         dirent_first(dip, bh, &de);
1273         do {
1274                 if (!de->de_inum.no_addr)
1275                         continue;
1276                 if (e >= entries) {
1277                         gfs2_consist_inode(dip);
1278                         error = -EIO;
1279                         goto out;
1280                 }
1281                 darr[e++] = de;
1282         }
1283         while (dirent_next(dip, bh, &de) == 0);
1284
1285         if (e != entries) {
1286                 gfs2_consist_inode(dip);
1287                 error = -EIO;
1288                 goto out;
1289         }
1290
1291         error = do_filldir_main(dip, offset, opaque, filldir, darr,
1292                                 entries, copied);
1293
1294  out:
1295         kfree(darr);
1296
1297         return error;
1298 }
1299
1300 /**
1301  * do_filldir_multi - Read directory entries out of a linked leaf list
1302  * @dip: The GFS2 inode
1303  * @offset: The offset in the file to read from
1304  * @opaque: opaque data to pass to filldir
1305  * @filldir: The function to pass entries to
1306  * @bh: the first leaf in the list
1307  * @copied: pointer to int that's non-zero if a entry has been copied out
1308  *
1309  * Returns: errno, >0 on exception from filldir
1310  */
1311
1312 static int do_filldir_multi(struct gfs2_inode *dip, uint64_t *offset,
1313                             void *opaque, gfs2_filldir_t filldir,
1314                             struct buffer_head *bh, int *copied)
1315 {
1316         struct buffer_head **larr = NULL;
1317         struct gfs2_dirent **darr;
1318         struct gfs2_leaf *leaf;
1319         struct buffer_head *tmp_bh;
1320         struct gfs2_dirent *de;
1321         unsigned int entries, e = 0;
1322         unsigned int leaves = 0, l = 0;
1323         unsigned int x;
1324         uint64_t ln;
1325         int error = 0;
1326
1327         /*  Count leaves and entries  */
1328
1329         leaf = (struct gfs2_leaf *)bh->b_data;
1330         entries = be16_to_cpu(leaf->lf_entries);
1331         ln = leaf->lf_next;
1332
1333         while (ln) {
1334                 ln = be64_to_cpu(ln);
1335
1336                 error = get_leaf(dip, ln, &tmp_bh);
1337                 if (error)
1338                         return error;
1339
1340                 leaf = (struct gfs2_leaf *)tmp_bh->b_data;
1341                 if (leaf->lf_entries) {
1342                         entries += be16_to_cpu(leaf->lf_entries);
1343                         leaves++;
1344                 }
1345                 ln = leaf->lf_next;
1346
1347                 brelse(tmp_bh);
1348         }
1349
1350         if (!entries)
1351                 return 0;
1352
1353         if (leaves) {
1354                 larr = kcalloc(leaves, sizeof(struct buffer_head *),GFP_KERNEL);
1355                 if (!larr)
1356                         return -ENOMEM;
1357         }
1358
1359         darr = kcalloc(entries, sizeof(struct gfs2_dirent *), GFP_KERNEL);
1360         if (!darr) {
1361                 kfree(larr);
1362                 return -ENOMEM;
1363         }
1364
1365         leaf = (struct gfs2_leaf *)bh->b_data;
1366         if (leaf->lf_entries) {
1367                 dirent_first(dip, bh, &de);
1368                 do {
1369                         if (!de->de_inum.no_addr)
1370                                 continue;
1371                         if (e >= entries) {
1372                                 gfs2_consist_inode(dip);
1373                                 error = -EIO;
1374                                 goto out;
1375                         }
1376                         darr[e++] = de;
1377                 }
1378                 while (dirent_next(dip, bh, &de) == 0);
1379         }
1380         ln = leaf->lf_next;
1381
1382         while (ln) {
1383                 ln = be64_to_cpu(ln);
1384
1385                 error = get_leaf(dip, ln, &tmp_bh);
1386                 if (error)
1387                         goto out;
1388
1389                 leaf = (struct gfs2_leaf *)tmp_bh->b_data;
1390                 if (leaf->lf_entries) {
1391                         dirent_first(dip, tmp_bh, &de);
1392                         do {
1393                                 if (!de->de_inum.no_addr)
1394                                         continue;
1395                                 if (e >= entries) {
1396                                         gfs2_consist_inode(dip);
1397                                         error = -EIO;
1398                                         goto out;
1399                                 }
1400                                 darr[e++] = de;
1401                         }
1402                         while (dirent_next(dip, tmp_bh, &de) == 0);
1403
1404                         larr[l++] = tmp_bh;
1405
1406                         ln = leaf->lf_next;
1407                 } else {
1408                         ln = leaf->lf_next;
1409                         brelse(tmp_bh);
1410                 }
1411         }
1412
1413         if (gfs2_assert_withdraw(dip->i_sbd, l == leaves)) {
1414                 error = -EIO;
1415                 goto out;
1416         }
1417         if (e != entries) {
1418                 gfs2_consist_inode(dip);
1419                 error = -EIO;
1420                 goto out;
1421         }
1422
1423         error = do_filldir_main(dip, offset, opaque, filldir, darr,
1424                                 entries, copied);
1425
1426  out:
1427         kfree(darr);
1428         for (x = 0; x < l; x++)
1429                 brelse(larr[x]);
1430         kfree(larr);
1431
1432         return error;
1433 }
1434
1435 /**
1436  * dir_e_search - Search exhash (leaf) dir for inode matching name
1437  * @dip: The GFS2 inode
1438  * @filename: Filename string
1439  * @inode: If non-NULL, function fills with formal inode # and block address
1440  * @type: If non-NULL, function fills with DT_... dinode type
1441  *
1442  * Returns:
1443  */
1444
1445 static int dir_e_search(struct gfs2_inode *dip, struct qstr *filename,
1446                         struct gfs2_inum *inum, unsigned int *type)
1447 {
1448         struct buffer_head *bh;
1449         struct gfs2_dirent *dent;
1450         int error;
1451
1452         error = linked_leaf_search(dip, filename, &dent, NULL, &bh);
1453         if (error)
1454                 return error;
1455
1456         if (inum)
1457                 gfs2_inum_in(inum, (char *)&dent->de_inum);
1458         if (type)
1459                 *type = be16_to_cpu(dent->de_type);
1460
1461         brelse(bh);
1462
1463         return 0;
1464 }
1465
1466 static int dir_e_add(struct gfs2_inode *dip, struct qstr *filename,
1467                      struct gfs2_inum *inum, unsigned int type)
1468 {
1469         struct buffer_head *bh, *nbh, *dibh;
1470         struct gfs2_leaf *leaf, *nleaf;
1471         struct gfs2_dirent *dent;
1472         uint32_t hsize, index;
1473         uint32_t hash;
1474         uint64_t leaf_no, bn;
1475         int error;
1476
1477  restart:
1478         hsize = 1 << dip->i_di.di_depth;
1479         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
1480                 gfs2_consist_inode(dip);
1481                 return -EIO;
1482         }
1483
1484         /*  Figure out the address of the leaf node.  */
1485
1486         hash = gfs2_disk_hash(filename->name, filename->len);
1487         index = hash >> (32 - dip->i_di.di_depth);
1488
1489         error = get_leaf_nr(dip, index, &leaf_no);
1490         if (error)
1491                 return error;
1492
1493         /*  Add entry to the leaf  */
1494
1495         for (;;) {
1496                 error = get_leaf(dip, leaf_no, &bh);
1497                 if (error)
1498                         return error;
1499
1500                 leaf = (struct gfs2_leaf *)bh->b_data;
1501
1502                 if (gfs2_dirent_alloc(dip, bh, filename->len, &dent)) {
1503
1504                         if (be16_to_cpu(leaf->lf_depth) < dip->i_di.di_depth) {
1505                                 /* Can we split the leaf? */
1506
1507                                 brelse(bh);
1508
1509                                 error = dir_split_leaf(dip, index, leaf_no);
1510                                 if (error)
1511                                         return error;
1512
1513                                 goto restart;
1514
1515                         } else if (dip->i_di.di_depth < GFS2_DIR_MAX_DEPTH) {
1516                                 /* Can we double the hash table? */
1517
1518                                 brelse(bh);
1519
1520                                 error = dir_double_exhash(dip);
1521                                 if (error)
1522                                         return error;
1523
1524                                 goto restart;
1525
1526                         } else if (leaf->lf_next) {
1527                                 /* Can we try the next leaf in the list? */
1528                                 leaf_no = be64_to_cpu(leaf->lf_next);
1529                                 brelse(bh);
1530                                 continue;
1531
1532                         } else {
1533                                 /* Create a new leaf and add it to the list. */
1534
1535                                 bn = gfs2_alloc_meta(dip);
1536
1537                                 nbh = gfs2_meta_new(dip->i_gl, bn);
1538                                 gfs2_trans_add_bh(dip->i_gl, nbh, 1);
1539                                 gfs2_metatype_set(nbh,
1540                                                  GFS2_METATYPE_LF,
1541                                                  GFS2_FORMAT_LF);
1542                                 gfs2_buffer_clear_tail(nbh,
1543                                         sizeof(struct gfs2_meta_header));
1544
1545                                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
1546                                 leaf->lf_next = cpu_to_be64(bn);
1547
1548                                 nleaf = (struct gfs2_leaf *)nbh->b_data;
1549                                 nleaf->lf_depth = leaf->lf_depth;
1550                                 nleaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
1551
1552                                 gfs2_dirent_alloc(dip, nbh, filename->len,
1553                                                   &dent);
1554
1555                                 dip->i_di.di_blocks++;
1556
1557                                 brelse(bh);
1558
1559                                 bh = nbh;
1560                                 leaf = nleaf;
1561                         }
1562                 }
1563
1564                 /* If the gfs2_dirent_alloc() succeeded, it pinned the "bh" */
1565
1566                 gfs2_inum_out(inum, (char *)&dent->de_inum);
1567                 dent->de_hash = cpu_to_be32(hash);
1568                 dent->de_type = cpu_to_be16(type);
1569                 memcpy((char *)(dent + 1), filename->name, filename->len);
1570
1571                 leaf->lf_entries = be16_to_cpu(leaf->lf_entries) + 1;
1572                 leaf->lf_entries = cpu_to_be16(leaf->lf_entries);
1573
1574                 brelse(bh);
1575
1576                 error = gfs2_meta_inode_buffer(dip, &dibh);
1577                 if (error)
1578                         return error;
1579
1580                 dip->i_di.di_entries++;
1581                 dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1582
1583                 gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1584                 gfs2_dinode_out(&dip->i_di, dibh->b_data);
1585                 brelse(dibh);
1586
1587                 return 0;
1588         }
1589
1590         return -ENOENT;
1591 }
1592
1593 static int dir_e_del(struct gfs2_inode *dip, struct qstr *filename)
1594 {
1595         struct buffer_head *bh, *dibh;
1596         struct gfs2_dirent *dent, *prev;
1597         struct gfs2_leaf *leaf;
1598         unsigned int entries;
1599         int error;
1600
1601         error = linked_leaf_search(dip, filename, &dent, &prev, &bh);
1602         if (error == -ENOENT) {
1603                 gfs2_consist_inode(dip);
1604                 return -EIO;
1605         }
1606         if (error)
1607                 return error;
1608
1609         dirent_del(dip, bh, prev, dent); /* Pins bh */
1610
1611         leaf = (struct gfs2_leaf *)bh->b_data;
1612         entries = be16_to_cpu(leaf->lf_entries);
1613         if (!entries)
1614                 gfs2_consist_inode(dip);
1615         entries--;
1616         leaf->lf_entries = cpu_to_be16(entries);
1617
1618         brelse(bh);
1619
1620         error = gfs2_meta_inode_buffer(dip, &dibh);
1621         if (error)
1622                 return error;
1623
1624         if (!dip->i_di.di_entries)
1625                 gfs2_consist_inode(dip);
1626         dip->i_di.di_entries--;
1627         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1628
1629         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1630         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1631         brelse(dibh);
1632
1633         return 0;
1634 }
1635
1636 /**
1637  * dir_e_read - Reads the entries from a directory into a filldir buffer
1638  * @dip: dinode pointer
1639  * @offset: the hash of the last entry read shifted to the right once
1640  * @opaque: buffer for the filldir function to fill
1641  * @filldir: points to the filldir function to use
1642  *
1643  * Returns: errno
1644  */
1645
1646 static int dir_e_read(struct gfs2_inode *dip, uint64_t *offset, void *opaque,
1647                       gfs2_filldir_t filldir)
1648 {
1649         struct gfs2_sbd *sdp = dip->i_sbd;
1650         struct buffer_head *bh;
1651         struct gfs2_leaf leaf;
1652         uint32_t hsize, len;
1653         uint32_t ht_offset, lp_offset, ht_offset_cur = -1;
1654         uint32_t hash, index;
1655         uint64_t *lp;
1656         int copied = 0;
1657         int error = 0;
1658
1659         hsize = 1 << dip->i_di.di_depth;
1660         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
1661                 gfs2_consist_inode(dip);
1662                 return -EIO;
1663         }
1664
1665         hash = gfs2_dir_offset2hash(*offset);
1666         index = hash >> (32 - dip->i_di.di_depth);
1667
1668         lp = kmalloc(sdp->sd_hash_bsize, GFP_KERNEL);
1669         if (!lp)
1670                 return -ENOMEM;
1671
1672         while (index < hsize) {
1673                 lp_offset = index & (sdp->sd_hash_ptrs - 1);
1674                 ht_offset = index - lp_offset;
1675
1676                 if (ht_offset_cur != ht_offset) {
1677                         error = gfs2_dir_read_data(dip, (char *)lp,
1678                                                 ht_offset * sizeof(uint64_t),
1679                                                 sdp->sd_hash_bsize);
1680                         if (error != sdp->sd_hash_bsize) {
1681                                 if (error >= 0)
1682                                         error = -EIO;
1683                                 goto out;
1684                         }
1685                         ht_offset_cur = ht_offset;
1686                 }
1687
1688                 error = get_leaf(dip, be64_to_cpu(lp[lp_offset]), &bh);
1689                 if (error)
1690                         goto out;
1691
1692                 gfs2_leaf_in(&leaf, bh->b_data);
1693
1694                 if (leaf.lf_next)
1695                         error = do_filldir_multi(dip, offset, opaque, filldir,
1696                                                  bh, &copied);
1697                 else
1698                         error = do_filldir_single(dip, offset, opaque, filldir,
1699                                                   bh, leaf.lf_entries, &copied);
1700
1701                 brelse(bh);
1702
1703                 if (error) {
1704                         if (error > 0)
1705                                 error = 0;
1706                         goto out;
1707                 }
1708
1709                 len = 1 << (dip->i_di.di_depth - leaf.lf_depth);
1710                 index = (index & ~(len - 1)) + len;
1711         }
1712
1713  out:
1714         kfree(lp);
1715
1716         return error;
1717 }
1718
1719 static int dir_e_mvino(struct gfs2_inode *dip, struct qstr *filename,
1720                        struct gfs2_inum *inum, unsigned int new_type)
1721 {
1722         struct buffer_head *bh, *dibh;
1723         struct gfs2_dirent *dent;
1724         int error;
1725
1726         error = linked_leaf_search(dip, filename, &dent, NULL, &bh);
1727         if (error == -ENOENT) {
1728                 gfs2_consist_inode(dip);
1729                 return -EIO;
1730         }
1731         if (error)
1732                 return error;
1733
1734         gfs2_trans_add_bh(dip->i_gl, bh, 1);
1735
1736         gfs2_inum_out(inum, (char *)&dent->de_inum);
1737         dent->de_type = cpu_to_be16(new_type);
1738
1739         brelse(bh);
1740
1741         error = gfs2_meta_inode_buffer(dip, &dibh);
1742         if (error)
1743                 return error;
1744
1745         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1746
1747         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1748         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1749         brelse(dibh);
1750
1751         return 0;
1752 }
1753
1754 /**
1755  * dir_l_search - Search linear (stuffed dinode) dir for inode matching name
1756  * @dip: The GFS2 inode
1757  * @filename: Filename string
1758  * @inode: If non-NULL, function fills with formal inode # and block address
1759  * @type: If non-NULL, function fills with DT_... dinode type
1760  *
1761  * Returns:
1762  */
1763
1764 static int dir_l_search(struct gfs2_inode *dip, struct qstr *filename,
1765                         struct gfs2_inum *inum, unsigned int *type)
1766 {
1767         struct buffer_head *dibh;
1768         struct gfs2_dirent *dent;
1769         int error;
1770
1771         if (!gfs2_is_stuffed(dip)) {
1772                 gfs2_consist_inode(dip);
1773                 return -EIO;
1774         }
1775
1776         error = gfs2_meta_inode_buffer(dip, &dibh);
1777         if (error)
1778                 return error;
1779
1780         error = leaf_search(dip, dibh, filename, &dent, NULL);
1781         if (!error) {
1782                 if (inum)
1783                         gfs2_inum_in(inum, (char *)&dent->de_inum);
1784                 if (type)
1785                         *type = be16_to_cpu(dent->de_type);
1786         }
1787
1788         brelse(dibh);
1789
1790         return error;
1791 }
1792
1793 static int dir_l_add(struct gfs2_inode *dip, struct qstr *filename,
1794                      struct gfs2_inum *inum, unsigned int type)
1795 {
1796         struct buffer_head *dibh;
1797         struct gfs2_dirent *dent;
1798         int error;
1799
1800         if (!gfs2_is_stuffed(dip)) {
1801                 gfs2_consist_inode(dip);
1802                 return -EIO;
1803         }
1804
1805         error = gfs2_meta_inode_buffer(dip, &dibh);
1806         if (error)
1807                 return error;
1808
1809         if (gfs2_dirent_alloc(dip, dibh, filename->len, &dent)) {
1810                 brelse(dibh);
1811
1812                 error = dir_make_exhash(dip);
1813                 if (!error)
1814                         error = dir_e_add(dip, filename, inum, type);
1815
1816                 return error;
1817         }
1818
1819         /*  gfs2_dirent_alloc() pins  */
1820
1821         gfs2_inum_out(inum, (char *)&dent->de_inum);
1822         dent->de_hash = gfs2_disk_hash(filename->name, filename->len);
1823         dent->de_hash = cpu_to_be32(dent->de_hash);
1824         dent->de_type = cpu_to_be16(type);
1825         memcpy((char *)(dent + 1), filename->name, filename->len);
1826
1827         dip->i_di.di_entries++;
1828         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1829
1830         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1831         brelse(dibh);
1832
1833         return 0;
1834 }
1835
1836 static int dir_l_del(struct gfs2_inode *dip, struct qstr *filename)
1837 {
1838         struct buffer_head *dibh;
1839         struct gfs2_dirent *dent, *prev;
1840         int error;
1841
1842         if (!gfs2_is_stuffed(dip)) {
1843                 gfs2_consist_inode(dip);
1844                 return -EIO;
1845         }
1846
1847         error = gfs2_meta_inode_buffer(dip, &dibh);
1848         if (error)
1849                 return error;
1850
1851         error = leaf_search(dip, dibh, filename, &dent, &prev);
1852         if (error == -ENOENT) {
1853                 gfs2_consist_inode(dip);
1854                 error = -EIO;
1855                 goto out;
1856         }
1857         if (error)
1858                 goto out;
1859
1860         dirent_del(dip, dibh, prev, dent);
1861
1862         /*  dirent_del() pins  */
1863
1864         if (!dip->i_di.di_entries)
1865                 gfs2_consist_inode(dip);
1866         dip->i_di.di_entries--;
1867
1868         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1869
1870         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1871
1872  out:
1873         brelse(dibh);
1874
1875         return error;
1876 }
1877
1878 static int dir_l_read(struct gfs2_inode *dip, uint64_t *offset, void *opaque,
1879                       gfs2_filldir_t filldir)
1880 {
1881         struct buffer_head *dibh;
1882         int copied = 0;
1883         int error;
1884
1885         if (!gfs2_is_stuffed(dip)) {
1886                 gfs2_consist_inode(dip);
1887                 return -EIO;
1888         }
1889
1890         if (!dip->i_di.di_entries)
1891                 return 0;
1892
1893         error = gfs2_meta_inode_buffer(dip, &dibh);
1894         if (error)
1895                 return error;
1896
1897         error = do_filldir_single(dip, offset,
1898                                   opaque, filldir,
1899                                   dibh, dip->i_di.di_entries,
1900                                   &copied);
1901         if (error > 0)
1902                 error = 0;
1903
1904         brelse(dibh);
1905
1906         return error;
1907 }
1908
1909 static int dir_l_mvino(struct gfs2_inode *dip, struct qstr *filename,
1910                        struct gfs2_inum *inum, unsigned int new_type)
1911 {
1912         struct buffer_head *dibh;
1913         struct gfs2_dirent *dent;
1914         int error;
1915
1916         if (!gfs2_is_stuffed(dip)) {
1917                 gfs2_consist_inode(dip);
1918                 return -EIO;
1919         }
1920
1921         error = gfs2_meta_inode_buffer(dip, &dibh);
1922         if (error)
1923                 return error;
1924
1925         error = leaf_search(dip, dibh, filename, &dent, NULL);
1926         if (error == -ENOENT) {
1927                 gfs2_consist_inode(dip);
1928                 error = -EIO;
1929                 goto out;
1930         }
1931         if (error)
1932                 goto out;
1933
1934         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1935
1936         gfs2_inum_out(inum, (char *)&dent->de_inum);
1937         dent->de_type = cpu_to_be16(new_type);
1938
1939         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1940
1941         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1942
1943  out:
1944         brelse(dibh);
1945
1946         return error;
1947 }
1948
1949 /**
1950  * gfs2_dir_search - Search a directory
1951  * @dip: The GFS2 inode
1952  * @filename:
1953  * @inode:
1954  *
1955  * This routine searches a directory for a file or another directory.
1956  * Assumes a glock is held on dip.
1957  *
1958  * Returns: errno
1959  */
1960
1961 int gfs2_dir_search(struct gfs2_inode *dip, struct qstr *filename,
1962                     struct gfs2_inum *inum, unsigned int *type)
1963 {
1964         int error;
1965
1966         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
1967                 error = dir_e_search(dip, filename, inum, type);
1968         else
1969                 error = dir_l_search(dip, filename, inum, type);
1970
1971         return error;
1972 }
1973
1974 /**
1975  * gfs2_dir_add - Add new filename into directory
1976  * @dip: The GFS2 inode
1977  * @filename: The new name
1978  * @inode: The inode number of the entry
1979  * @type: The type of the entry
1980  *
1981  * Returns: 0 on success, error code on failure
1982  */
1983
1984 int gfs2_dir_add(struct gfs2_inode *dip, struct qstr *filename,
1985                  struct gfs2_inum *inum, unsigned int type)
1986 {
1987         int error;
1988
1989         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
1990                 error = dir_e_add(dip, filename, inum, type);
1991         else
1992                 error = dir_l_add(dip, filename, inum, type);
1993
1994         return error;
1995 }
1996
1997 /**
1998  * gfs2_dir_del - Delete a directory entry
1999  * @dip: The GFS2 inode
2000  * @filename: The filename
2001  *
2002  * Returns: 0 on success, error code on failure
2003  */
2004
2005 int gfs2_dir_del(struct gfs2_inode *dip, struct qstr *filename)
2006 {
2007         int error;
2008
2009         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
2010                 error = dir_e_del(dip, filename);
2011         else
2012                 error = dir_l_del(dip, filename);
2013
2014         return error;
2015 }
2016
2017 int gfs2_dir_read(struct gfs2_inode *dip, uint64_t *offset, void *opaque,
2018                   gfs2_filldir_t filldir)
2019 {
2020         int error;
2021
2022         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
2023                 error = dir_e_read(dip, offset, opaque, filldir);
2024         else
2025                 error = dir_l_read(dip, offset, opaque, filldir);
2026
2027         return error;
2028 }
2029
2030 /**
2031  * gfs2_dir_mvino - Change inode number of directory entry
2032  * @dip: The GFS2 inode
2033  * @filename:
2034  * @new_inode:
2035  *
2036  * This routine changes the inode number of a directory entry.  It's used
2037  * by rename to change ".." when a directory is moved.
2038  * Assumes a glock is held on dvp.
2039  *
2040  * Returns: errno
2041  */
2042
2043 int gfs2_dir_mvino(struct gfs2_inode *dip, struct qstr *filename,
2044                    struct gfs2_inum *inum, unsigned int new_type)
2045 {
2046         int error;
2047
2048         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
2049                 error = dir_e_mvino(dip, filename, inum, new_type);
2050         else
2051                 error = dir_l_mvino(dip, filename, inum, new_type);
2052
2053         return error;
2054 }
2055
2056 /**
2057  * foreach_leaf - call a function for each leaf in a directory
2058  * @dip: the directory
2059  * @lc: the function to call for each each
2060  * @data: private data to pass to it
2061  *
2062  * Returns: errno
2063  */
2064
2065 static int foreach_leaf(struct gfs2_inode *dip, leaf_call_t lc, void *data)
2066 {
2067         struct gfs2_sbd *sdp = dip->i_sbd;
2068         struct buffer_head *bh;
2069         struct gfs2_leaf leaf;
2070         uint32_t hsize, len;
2071         uint32_t ht_offset, lp_offset, ht_offset_cur = -1;
2072         uint32_t index = 0;
2073         uint64_t *lp;
2074         uint64_t leaf_no;
2075         int error = 0;
2076
2077         hsize = 1 << dip->i_di.di_depth;
2078         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
2079                 gfs2_consist_inode(dip);
2080                 return -EIO;
2081         }
2082
2083         lp = kmalloc(sdp->sd_hash_bsize, GFP_KERNEL);
2084         if (!lp)
2085                 return -ENOMEM;
2086
2087         while (index < hsize) {
2088                 lp_offset = index & (sdp->sd_hash_ptrs - 1);
2089                 ht_offset = index - lp_offset;
2090
2091                 if (ht_offset_cur != ht_offset) {
2092                         error = gfs2_dir_read_data(dip, (char *)lp,
2093                                                 ht_offset * sizeof(uint64_t),
2094                                                 sdp->sd_hash_bsize);
2095                         if (error != sdp->sd_hash_bsize) {
2096                                 if (error >= 0)
2097                                         error = -EIO;
2098                                 goto out;
2099                         }
2100                         ht_offset_cur = ht_offset;
2101                 }
2102
2103                 leaf_no = be64_to_cpu(lp[lp_offset]);
2104                 if (leaf_no) {
2105                         error = get_leaf(dip, leaf_no, &bh);
2106                         if (error)
2107                                 goto out;
2108                         gfs2_leaf_in(&leaf, bh->b_data);
2109                         brelse(bh);
2110
2111                         len = 1 << (dip->i_di.di_depth - leaf.lf_depth);
2112
2113                         error = lc(dip, index, len, leaf_no, data);
2114                         if (error)
2115                                 goto out;
2116
2117                         index = (index & ~(len - 1)) + len;
2118                 } else
2119                         index++;
2120         }
2121
2122         if (index != hsize) {
2123                 gfs2_consist_inode(dip);
2124                 error = -EIO;
2125         }
2126
2127  out:
2128         kfree(lp);
2129
2130         return error;
2131 }
2132
2133 /**
2134  * leaf_dealloc - Deallocate a directory leaf
2135  * @dip: the directory
2136  * @index: the hash table offset in the directory
2137  * @len: the number of pointers to this leaf
2138  * @leaf_no: the leaf number
2139  * @data: not used
2140  *
2141  * Returns: errno
2142  */
2143
2144 static int leaf_dealloc(struct gfs2_inode *dip, uint32_t index, uint32_t len,
2145                         uint64_t leaf_no, void *data)
2146 {
2147         struct gfs2_sbd *sdp = dip->i_sbd;
2148         struct gfs2_leaf tmp_leaf;
2149         struct gfs2_rgrp_list rlist;
2150         struct buffer_head *bh, *dibh;
2151         uint64_t blk;
2152         unsigned int rg_blocks = 0, l_blocks = 0;
2153         char *ht;
2154         unsigned int x, size = len * sizeof(uint64_t);
2155         int error;
2156
2157         memset(&rlist, 0, sizeof(struct gfs2_rgrp_list));
2158
2159         ht = kzalloc(size, GFP_KERNEL);
2160         if (!ht)
2161                 return -ENOMEM;
2162
2163         gfs2_alloc_get(dip);
2164
2165         error = gfs2_quota_hold(dip, NO_QUOTA_CHANGE, NO_QUOTA_CHANGE);
2166         if (error)
2167                 goto out;
2168
2169         error = gfs2_rindex_hold(sdp, &dip->i_alloc.al_ri_gh);
2170         if (error)
2171                 goto out_qs;
2172
2173         /*  Count the number of leaves  */
2174
2175         for (blk = leaf_no; blk; blk = tmp_leaf.lf_next) {
2176                 error = get_leaf(dip, blk, &bh);
2177                 if (error)
2178                         goto out_rlist;
2179                 gfs2_leaf_in(&tmp_leaf, (bh)->b_data);
2180                 brelse(bh);
2181
2182                 gfs2_rlist_add(sdp, &rlist, blk);
2183                 l_blocks++;
2184         }
2185
2186         gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE, 0);
2187
2188         for (x = 0; x < rlist.rl_rgrps; x++) {
2189                 struct gfs2_rgrpd *rgd;
2190                 rgd = get_gl2rgd(rlist.rl_ghs[x].gh_gl);
2191                 rg_blocks += rgd->rd_ri.ri_length;
2192         }
2193
2194         error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs);
2195         if (error)
2196                 goto out_rlist;
2197
2198         error = gfs2_trans_begin(sdp,
2199                         rg_blocks + (DIV_RU(size, sdp->sd_jbsize) + 1) +
2200                         RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks);
2201         if (error)
2202                 goto out_rg_gunlock;
2203
2204         for (blk = leaf_no; blk; blk = tmp_leaf.lf_next) {
2205                 error = get_leaf(dip, blk, &bh);
2206                 if (error)
2207                         goto out_end_trans;
2208                 gfs2_leaf_in(&tmp_leaf, bh->b_data);
2209                 brelse(bh);
2210
2211                 gfs2_free_meta(dip, blk, 1);
2212
2213                 if (!dip->i_di.di_blocks)
2214                         gfs2_consist_inode(dip);
2215                 dip->i_di.di_blocks--;
2216         }
2217
2218         error = gfs2_dir_write_data(dip, ht, index * sizeof(uint64_t), size);
2219         if (error != size) {
2220                 if (error >= 0)
2221                         error = -EIO;
2222                 goto out_end_trans;
2223         }
2224
2225         error = gfs2_meta_inode_buffer(dip, &dibh);
2226         if (error)
2227                 goto out_end_trans;
2228
2229         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
2230         gfs2_dinode_out(&dip->i_di, dibh->b_data);
2231         brelse(dibh);
2232
2233  out_end_trans:
2234         gfs2_trans_end(sdp);
2235
2236  out_rg_gunlock:
2237         gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs);
2238
2239  out_rlist:
2240         gfs2_rlist_free(&rlist);
2241         gfs2_glock_dq_uninit(&dip->i_alloc.al_ri_gh);
2242
2243  out_qs:
2244         gfs2_quota_unhold(dip);
2245
2246  out:
2247         gfs2_alloc_put(dip);
2248         kfree(ht);
2249
2250         return error;
2251 }
2252
2253 /**
2254  * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory
2255  * @dip: the directory
2256  *
2257  * Dealloc all on-disk directory leaves to FREEMETA state
2258  * Change on-disk inode type to "regular file"
2259  *
2260  * Returns: errno
2261  */
2262
2263 int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip)
2264 {
2265         struct gfs2_sbd *sdp = dip->i_sbd;
2266         struct buffer_head *bh;
2267         int error;
2268
2269         /* Dealloc on-disk leaves to FREEMETA state */
2270         error = foreach_leaf(dip, leaf_dealloc, NULL);
2271         if (error)
2272                 return error;
2273
2274         /* Make this a regular file in case we crash.
2275            (We don't want to free these blocks a second time.)  */
2276
2277         error = gfs2_trans_begin(sdp, RES_DINODE, 0);
2278         if (error)
2279                 return error;
2280
2281         error = gfs2_meta_inode_buffer(dip, &bh);
2282         if (!error) {
2283                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
2284                 ((struct gfs2_dinode *)bh->b_data)->di_mode = cpu_to_be32(S_IFREG);
2285                 brelse(bh);
2286         }
2287
2288         gfs2_trans_end(sdp);
2289
2290         return error;
2291 }
2292
2293 /**
2294  * gfs2_diradd_alloc_required - find if adding entry will require an allocation
2295  * @ip: the file being written to
2296  * @filname: the filename that's going to be added
2297  * @alloc_required: set to 1 if an alloc is required, 0 otherwise
2298  *
2299  * Returns: errno
2300  */
2301
2302 int gfs2_diradd_alloc_required(struct gfs2_inode *dip, struct qstr *filename,
2303                                int *alloc_required)
2304 {
2305         struct buffer_head *bh = NULL, *bh_next;
2306         uint32_t hsize, hash, index;
2307         int error = 0;
2308
2309         *alloc_required = 0;
2310
2311         if (dip->i_di.di_flags & GFS2_DIF_EXHASH) {
2312                 hsize = 1 << dip->i_di.di_depth;
2313                 if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
2314                         gfs2_consist_inode(dip);
2315                         return -EIO;
2316                 }
2317
2318                 hash = gfs2_disk_hash(filename->name, filename->len);
2319                 index = hash >> (32 - dip->i_di.di_depth);
2320
2321                 error = get_first_leaf(dip, index, &bh_next);
2322                 if (error)
2323                         return error;
2324
2325                 do {
2326                         brelse(bh);
2327
2328                         bh = bh_next;
2329
2330                         if (dirent_fits(dip, bh, filename->len))
2331                                 break;
2332
2333                         error = get_next_leaf(dip, bh, &bh_next);
2334                         if (error == -ENOENT) {
2335                                 *alloc_required = 1;
2336                                 error = 0;
2337                                 break;
2338                         }
2339                 }
2340                 while (!error);
2341
2342                 brelse(bh);
2343         } else {
2344                 error = gfs2_meta_inode_buffer(dip, &bh);
2345                 if (error)
2346                         return error;
2347
2348                 if (!dirent_fits(dip, bh, filename->len))
2349                         *alloc_required = 1;
2350
2351                 brelse(bh);
2352         }
2353
2354         return error;
2355 }
2356