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