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