linux/fs/gfs2/dir.c
<<
>>
Prefs
   1/*
   2 * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
   3 * Copyright (C) 2004-2006 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 version 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_diskflags & 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
  46 * block pointer in the array that points to the same leaf. In fact, when a
  47 * directory is first converted from linear to exhash, all of the pointers
  48 * point to the 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/slab.h>
  57#include <linux/spinlock.h>
  58#include <linux/buffer_head.h>
  59#include <linux/sort.h>
  60#include <linux/gfs2_ondisk.h>
  61#include <linux/crc32.h>
  62#include <linux/vmalloc.h>
  63
  64#include "gfs2.h"
  65#include "incore.h"
  66#include "dir.h"
  67#include "glock.h"
  68#include "inode.h"
  69#include "meta_io.h"
  70#include "quota.h"
  71#include "rgrp.h"
  72#include "trans.h"
  73#include "bmap.h"
  74#include "util.h"
  75
  76#define IS_LEAF     1 /* Hashed (leaf) directory */
  77#define IS_DINODE   2 /* Linear (stuffed dinode block) directory */
  78
  79#define MAX_RA_BLOCKS 32 /* max read-ahead blocks */
  80
  81#define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1)
  82#define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1))
  83
  84struct qstr gfs2_qdot __read_mostly;
  85struct qstr gfs2_qdotdot __read_mostly;
  86
  87typedef int (*gfs2_dscan_t)(const struct gfs2_dirent *dent,
  88                            const struct qstr *name, void *opaque);
  89
  90int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block,
  91                            struct buffer_head **bhp)
  92{
  93        struct buffer_head *bh;
  94
  95        bh = gfs2_meta_new(ip->i_gl, block);
  96        gfs2_trans_add_meta(ip->i_gl, bh);
  97        gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
  98        gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
  99        *bhp = bh;
 100        return 0;
 101}
 102
 103static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block,
 104                                        struct buffer_head **bhp)
 105{
 106        struct buffer_head *bh;
 107        int error;
 108
 109        error = gfs2_meta_read(ip->i_gl, block, DIO_WAIT, &bh);
 110        if (error)
 111                return error;
 112        if (gfs2_metatype_check(GFS2_SB(&ip->i_inode), bh, GFS2_METATYPE_JD)) {
 113                brelse(bh);
 114                return -EIO;
 115        }
 116        *bhp = bh;
 117        return 0;
 118}
 119
 120static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
 121                                  unsigned int offset, unsigned int size)
 122{
 123        struct buffer_head *dibh;
 124        int error;
 125
 126        error = gfs2_meta_inode_buffer(ip, &dibh);
 127        if (error)
 128                return error;
 129
 130        gfs2_trans_add_meta(ip->i_gl, dibh);
 131        memcpy(dibh->b_data + offset + sizeof(struct gfs2_dinode), buf, size);
 132        if (ip->i_inode.i_size < offset + size)
 133                i_size_write(&ip->i_inode, offset + size);
 134        ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
 135        gfs2_dinode_out(ip, dibh->b_data);
 136
 137        brelse(dibh);
 138
 139        return size;
 140}
 141
 142
 143
 144/**
 145 * gfs2_dir_write_data - Write directory information to the inode
 146 * @ip: The GFS2 inode
 147 * @buf: The buffer containing information to be written
 148 * @offset: The file offset to start writing at
 149 * @size: The amount of data to write
 150 *
 151 * Returns: The number of bytes correctly written or error code
 152 */
 153static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf,
 154                               u64 offset, unsigned int size)
 155{
 156        struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 157        struct buffer_head *dibh;
 158        u64 lblock, dblock;
 159        u32 extlen = 0;
 160        unsigned int o;
 161        int copied = 0;
 162        int error = 0;
 163        int new = 0;
 164
 165        if (!size)
 166                return 0;
 167
 168        if (gfs2_is_stuffed(ip) &&
 169            offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode))
 170                return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset,
 171                                              size);
 172
 173        if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
 174                return -EINVAL;
 175
 176        if (gfs2_is_stuffed(ip)) {
 177                error = gfs2_unstuff_dinode(ip, NULL);
 178                if (error)
 179                        return error;
 180        }
 181
 182        lblock = offset;
 183        o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
 184
 185        while (copied < size) {
 186                unsigned int amount;
 187                struct buffer_head *bh;
 188
 189                amount = size - copied;
 190                if (amount > sdp->sd_sb.sb_bsize - o)
 191                        amount = sdp->sd_sb.sb_bsize - o;
 192
 193                if (!extlen) {
 194                        new = 1;
 195                        error = gfs2_extent_map(&ip->i_inode, lblock, &new,
 196                                                &dblock, &extlen);
 197                        if (error)
 198                                goto fail;
 199                        error = -EIO;
 200                        if (gfs2_assert_withdraw(sdp, dblock))
 201                                goto fail;
 202                }
 203
 204                if (amount == sdp->sd_jbsize || new)
 205                        error = gfs2_dir_get_new_buffer(ip, dblock, &bh);
 206                else
 207                        error = gfs2_dir_get_existing_buffer(ip, dblock, &bh);
 208
 209                if (error)
 210                        goto fail;
 211
 212                gfs2_trans_add_meta(ip->i_gl, bh);
 213                memcpy(bh->b_data + o, buf, amount);
 214                brelse(bh);
 215
 216                buf += amount;
 217                copied += amount;
 218                lblock++;
 219                dblock++;
 220                extlen--;
 221
 222                o = sizeof(struct gfs2_meta_header);
 223        }
 224
 225out:
 226        error = gfs2_meta_inode_buffer(ip, &dibh);
 227        if (error)
 228                return error;
 229
 230        if (ip->i_inode.i_size < offset + copied)
 231                i_size_write(&ip->i_inode, offset + copied);
 232        ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
 233
 234        gfs2_trans_add_meta(ip->i_gl, dibh);
 235        gfs2_dinode_out(ip, dibh->b_data);
 236        brelse(dibh);
 237
 238        return copied;
 239fail:
 240        if (copied)
 241                goto out;
 242        return error;
 243}
 244
 245static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, __be64 *buf,
 246                                 unsigned int size)
 247{
 248        struct buffer_head *dibh;
 249        int error;
 250
 251        error = gfs2_meta_inode_buffer(ip, &dibh);
 252        if (!error) {
 253                memcpy(buf, dibh->b_data + sizeof(struct gfs2_dinode), size);
 254                brelse(dibh);
 255        }
 256
 257        return (error) ? error : size;
 258}
 259
 260
 261/**
 262 * gfs2_dir_read_data - Read a data from a directory inode
 263 * @ip: The GFS2 Inode
 264 * @buf: The buffer to place result into
 265 * @size: Amount of data to transfer
 266 *
 267 * Returns: The amount of data actually copied or the error
 268 */
 269static int gfs2_dir_read_data(struct gfs2_inode *ip, __be64 *buf,
 270                              unsigned int size)
 271{
 272        struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
 273        u64 lblock, dblock;
 274        u32 extlen = 0;
 275        unsigned int o;
 276        int copied = 0;
 277        int error = 0;
 278
 279        if (gfs2_is_stuffed(ip))
 280                return gfs2_dir_read_stuffed(ip, buf, size);
 281
 282        if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
 283                return -EINVAL;
 284
 285        lblock = 0;
 286        o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
 287
 288        while (copied < size) {
 289                unsigned int amount;
 290                struct buffer_head *bh;
 291                int new;
 292
 293                amount = size - copied;
 294                if (amount > sdp->sd_sb.sb_bsize - o)
 295                        amount = sdp->sd_sb.sb_bsize - o;
 296
 297                if (!extlen) {
 298                        new = 0;
 299                        error = gfs2_extent_map(&ip->i_inode, lblock, &new,
 300                                                &dblock, &extlen);
 301                        if (error || !dblock)
 302                                goto fail;
 303                        BUG_ON(extlen < 1);
 304                        bh = gfs2_meta_ra(ip->i_gl, dblock, extlen);
 305                } else {
 306                        error = gfs2_meta_read(ip->i_gl, dblock, DIO_WAIT, &bh);
 307                        if (error)
 308                                goto fail;
 309                }
 310                error = gfs2_metatype_check(sdp, bh, GFS2_METATYPE_JD);
 311                if (error) {
 312                        brelse(bh);
 313                        goto fail;
 314                }
 315                dblock++;
 316                extlen--;
 317                memcpy(buf, bh->b_data + o, amount);
 318                brelse(bh);
 319                buf += (amount/sizeof(__be64));
 320                copied += amount;
 321                lblock++;
 322                o = sizeof(struct gfs2_meta_header);
 323        }
 324
 325        return copied;
 326fail:
 327        return (copied) ? copied : error;
 328}
 329
 330/**
 331 * gfs2_dir_get_hash_table - Get pointer to the dir hash table
 332 * @ip: The inode in question
 333 *
 334 * Returns: The hash table or an error
 335 */
 336
 337static __be64 *gfs2_dir_get_hash_table(struct gfs2_inode *ip)
 338{
 339        struct inode *inode = &ip->i_inode;
 340        int ret;
 341        u32 hsize;
 342        __be64 *hc;
 343
 344        BUG_ON(!(ip->i_diskflags & GFS2_DIF_EXHASH));
 345
 346        hc = ip->i_hash_cache;
 347        if (hc)
 348                return hc;
 349
 350        hsize = 1 << ip->i_depth;
 351        hsize *= sizeof(__be64);
 352        if (hsize != i_size_read(&ip->i_inode)) {
 353                gfs2_consist_inode(ip);
 354                return ERR_PTR(-EIO);
 355        }
 356
 357        hc = kmalloc(hsize, GFP_NOFS | __GFP_NOWARN);
 358        if (hc == NULL)
 359                hc = __vmalloc(hsize, GFP_NOFS, PAGE_KERNEL);
 360
 361        if (hc == NULL)
 362                return ERR_PTR(-ENOMEM);
 363
 364        ret = gfs2_dir_read_data(ip, hc, hsize);
 365        if (ret < 0) {
 366                if (is_vmalloc_addr(hc))
 367                        vfree(hc);
 368                else
 369                        kfree(hc);
 370                return ERR_PTR(ret);
 371        }
 372
 373        spin_lock(&inode->i_lock);
 374        if (ip->i_hash_cache) {
 375                if (is_vmalloc_addr(hc))
 376                        vfree(hc);
 377                else
 378                        kfree(hc);
 379        } else {
 380                ip->i_hash_cache = hc;
 381        }
 382        spin_unlock(&inode->i_lock);
 383
 384        return ip->i_hash_cache;
 385}
 386
 387/**
 388 * gfs2_dir_hash_inval - Invalidate dir hash
 389 * @ip: The directory inode
 390 *
 391 * Must be called with an exclusive glock, or during glock invalidation.
 392 */
 393void gfs2_dir_hash_inval(struct gfs2_inode *ip)
 394{
 395        __be64 *hc = ip->i_hash_cache;
 396        ip->i_hash_cache = NULL;
 397        if (is_vmalloc_addr(hc))
 398                vfree(hc);
 399        else
 400                kfree(hc);
 401}
 402
 403static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent)
 404{
 405        return dent->de_inum.no_addr == 0 || dent->de_inum.no_formal_ino == 0;
 406}
 407
 408static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent,
 409                                     const struct qstr *name, int ret)
 410{
 411        if (!gfs2_dirent_sentinel(dent) &&
 412            be32_to_cpu(dent->de_hash) == name->hash &&
 413            be16_to_cpu(dent->de_name_len) == name->len &&
 414            memcmp(dent+1, name->name, name->len) == 0)
 415                return ret;
 416        return 0;
 417}
 418
 419static int gfs2_dirent_find(const struct gfs2_dirent *dent,
 420                            const struct qstr *name,
 421                            void *opaque)
 422{
 423        return __gfs2_dirent_find(dent, name, 1);
 424}
 425
 426static int gfs2_dirent_prev(const struct gfs2_dirent *dent,
 427                            const struct qstr *name,
 428                            void *opaque)
 429{
 430        return __gfs2_dirent_find(dent, name, 2);
 431}
 432
 433/*
 434 * name->name holds ptr to start of block.
 435 * name->len holds size of block.
 436 */
 437static int gfs2_dirent_last(const struct gfs2_dirent *dent,
 438                            const struct qstr *name,
 439                            void *opaque)
 440{
 441        const char *start = name->name;
 442        const char *end = (const char *)dent + be16_to_cpu(dent->de_rec_len);
 443        if (name->len == (end - start))
 444                return 1;
 445        return 0;
 446}
 447
 448static int gfs2_dirent_find_space(const struct gfs2_dirent *dent,
 449                                  const struct qstr *name,
 450                                  void *opaque)
 451{
 452        unsigned required = GFS2_DIRENT_SIZE(name->len);
 453        unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
 454        unsigned totlen = be16_to_cpu(dent->de_rec_len);
 455
 456        if (gfs2_dirent_sentinel(dent))
 457                actual = 0;
 458        if (totlen - actual >= required)
 459                return 1;
 460        return 0;
 461}
 462
 463struct dirent_gather {
 464        const struct gfs2_dirent **pdent;
 465        unsigned offset;
 466};
 467
 468static int gfs2_dirent_gather(const struct gfs2_dirent *dent,
 469                              const struct qstr *name,
 470                              void *opaque)
 471{
 472        struct dirent_gather *g = opaque;
 473        if (!gfs2_dirent_sentinel(dent)) {
 474                g->pdent[g->offset++] = dent;
 475        }
 476        return 0;
 477}
 478
 479/*
 480 * Other possible things to check:
 481 * - Inode located within filesystem size (and on valid block)
 482 * - Valid directory entry type
 483 * Not sure how heavy-weight we want to make this... could also check
 484 * hash is correct for example, but that would take a lot of extra time.
 485 * For now the most important thing is to check that the various sizes
 486 * are correct.
 487 */
 488static int gfs2_check_dirent(struct gfs2_dirent *dent, unsigned int offset,
 489                             unsigned int size, unsigned int len, int first)
 490{
 491        const char *msg = "gfs2_dirent too small";
 492        if (unlikely(size < sizeof(struct gfs2_dirent)))
 493                goto error;
 494        msg = "gfs2_dirent misaligned";
 495        if (unlikely(offset & 0x7))
 496                goto error;
 497        msg = "gfs2_dirent points beyond end of block";
 498        if (unlikely(offset + size > len))
 499                goto error;
 500        msg = "zero inode number";
 501        if (unlikely(!first && gfs2_dirent_sentinel(dent)))
 502                goto error;
 503        msg = "name length is greater than space in dirent";
 504        if (!gfs2_dirent_sentinel(dent) &&
 505            unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) >
 506                     size))
 507                goto error;
 508        return 0;
 509error:
 510        printk(KERN_WARNING "gfs2_check_dirent: %s (%s)\n", msg,
 511               first ? "first in block" : "not first in block");
 512        return -EIO;
 513}
 514
 515static int gfs2_dirent_offset(const void *buf)
 516{
 517        const struct gfs2_meta_header *h = buf;
 518        int offset;
 519
 520        BUG_ON(buf == NULL);
 521
 522        switch(be32_to_cpu(h->mh_type)) {
 523        case GFS2_METATYPE_LF:
 524                offset = sizeof(struct gfs2_leaf);
 525                break;
 526        case GFS2_METATYPE_DI:
 527                offset = sizeof(struct gfs2_dinode);
 528                break;
 529        default:
 530                goto wrong_type;
 531        }
 532        return offset;
 533wrong_type:
 534        printk(KERN_WARNING "gfs2_scan_dirent: wrong block type %u\n",
 535               be32_to_cpu(h->mh_type));
 536        return -1;
 537}
 538
 539static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf,
 540                                            unsigned int len, gfs2_dscan_t scan,
 541                                            const struct qstr *name,
 542                                            void *opaque)
 543{
 544        struct gfs2_dirent *dent, *prev;
 545        unsigned offset;
 546        unsigned size;
 547        int ret = 0;
 548
 549        ret = gfs2_dirent_offset(buf);
 550        if (ret < 0)
 551                goto consist_inode;
 552
 553        offset = ret;
 554        prev = NULL;
 555        dent = buf + offset;
 556        size = be16_to_cpu(dent->de_rec_len);
 557        if (gfs2_check_dirent(dent, offset, size, len, 1))
 558                goto consist_inode;
 559        do {
 560                ret = scan(dent, name, opaque);
 561                if (ret)
 562                        break;
 563                offset += size;
 564                if (offset == len)
 565                        break;
 566                prev = dent;
 567                dent = buf + offset;
 568                size = be16_to_cpu(dent->de_rec_len);
 569                if (gfs2_check_dirent(dent, offset, size, len, 0))
 570                        goto consist_inode;
 571        } while(1);
 572
 573        switch(ret) {
 574        case 0:
 575                return NULL;
 576        case 1:
 577                return dent;
 578        case 2:
 579                return prev ? prev : dent;
 580        default:
 581                BUG_ON(ret > 0);
 582                return ERR_PTR(ret);
 583        }
 584
 585consist_inode:
 586        gfs2_consist_inode(GFS2_I(inode));
 587        return ERR_PTR(-EIO);
 588}
 589
 590static int dirent_check_reclen(struct gfs2_inode *dip,
 591                               const struct gfs2_dirent *d, const void *end_p)
 592{
 593        const void *ptr = d;
 594        u16 rec_len = be16_to_cpu(d->de_rec_len);
 595
 596        if (unlikely(rec_len < sizeof(struct gfs2_dirent)))
 597                goto broken;
 598        ptr += rec_len;
 599        if (ptr < end_p)
 600                return rec_len;
 601        if (ptr == end_p)
 602                return -ENOENT;
 603broken:
 604        gfs2_consist_inode(dip);
 605        return -EIO;
 606}
 607
 608/**
 609 * dirent_next - Next dirent
 610 * @dip: the directory
 611 * @bh: The buffer
 612 * @dent: Pointer to list of dirents
 613 *
 614 * Returns: 0 on success, error code otherwise
 615 */
 616
 617static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,
 618                       struct gfs2_dirent **dent)
 619{
 620        struct gfs2_dirent *cur = *dent, *tmp;
 621        char *bh_end = bh->b_data + bh->b_size;
 622        int ret;
 623
 624        ret = dirent_check_reclen(dip, cur, bh_end);
 625        if (ret < 0)
 626                return ret;
 627
 628        tmp = (void *)cur + ret;
 629        ret = dirent_check_reclen(dip, tmp, bh_end);
 630        if (ret == -EIO)
 631                return ret;
 632
 633        /* Only the first dent could ever have de_inum.no_addr == 0 */
 634        if (gfs2_dirent_sentinel(tmp)) {
 635                gfs2_consist_inode(dip);
 636                return -EIO;
 637        }
 638
 639        *dent = tmp;
 640        return 0;
 641}
 642
 643/**
 644 * dirent_del - Delete a dirent
 645 * @dip: The GFS2 inode
 646 * @bh: The buffer
 647 * @prev: The previous dirent
 648 * @cur: The current dirent
 649 *
 650 */
 651
 652static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,
 653                       struct gfs2_dirent *prev, struct gfs2_dirent *cur)
 654{
 655        u16 cur_rec_len, prev_rec_len;
 656
 657        if (gfs2_dirent_sentinel(cur)) {
 658                gfs2_consist_inode(dip);
 659                return;
 660        }
 661
 662        gfs2_trans_add_meta(dip->i_gl, bh);
 663
 664        /* If there is no prev entry, this is the first entry in the block.
 665           The de_rec_len is already as big as it needs to be.  Just zero
 666           out the inode number and return.  */
 667
 668        if (!prev) {
 669                cur->de_inum.no_addr = 0;
 670                cur->de_inum.no_formal_ino = 0;
 671                return;
 672        }
 673
 674        /*  Combine this dentry with the previous one.  */
 675
 676        prev_rec_len = be16_to_cpu(prev->de_rec_len);
 677        cur_rec_len = be16_to_cpu(cur->de_rec_len);
 678
 679        if ((char *)prev + prev_rec_len != (char *)cur)
 680                gfs2_consist_inode(dip);
 681        if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)
 682                gfs2_consist_inode(dip);
 683
 684        prev_rec_len += cur_rec_len;
 685        prev->de_rec_len = cpu_to_be16(prev_rec_len);
 686}
 687
 688/*
 689 * Takes a dent from which to grab space as an argument. Returns the
 690 * newly created dent.
 691 */
 692static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,
 693                                            struct gfs2_dirent *dent,
 694                                            const struct qstr *name,
 695                                            struct buffer_head *bh)
 696{
 697        struct gfs2_inode *ip = GFS2_I(inode);
 698        struct gfs2_dirent *ndent;
 699        unsigned offset = 0, totlen;
 700
 701        if (!gfs2_dirent_sentinel(dent))
 702                offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
 703        totlen = be16_to_cpu(dent->de_rec_len);
 704        BUG_ON(offset + name->len > totlen);
 705        gfs2_trans_add_meta(ip->i_gl, bh);
 706        ndent = (struct gfs2_dirent *)((char *)dent + offset);
 707        dent->de_rec_len = cpu_to_be16(offset);
 708        gfs2_qstr2dirent(name, totlen - offset, ndent);
 709        return ndent;
 710}
 711
 712static struct gfs2_dirent *gfs2_dirent_alloc(struct inode *inode,
 713                                             struct buffer_head *bh,
 714                                             const struct qstr *name)
 715{
 716        struct gfs2_dirent *dent;
 717        dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
 718                                gfs2_dirent_find_space, name, NULL);
 719        if (!dent || IS_ERR(dent))
 720                return dent;
 721        return gfs2_init_dirent(inode, dent, name, bh);
 722}
 723
 724static int get_leaf(struct gfs2_inode *dip, u64 leaf_no,
 725                    struct buffer_head **bhp)
 726{
 727        int error;
 728
 729        error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_WAIT, bhp);
 730        if (!error && gfs2_metatype_check(GFS2_SB(&dip->i_inode), *bhp, GFS2_METATYPE_LF)) {
 731                /* printk(KERN_INFO "block num=%llu\n", leaf_no); */
 732                error = -EIO;
 733        }
 734
 735        return error;
 736}
 737
 738/**
 739 * get_leaf_nr - Get a leaf number associated with the index
 740 * @dip: The GFS2 inode
 741 * @index:
 742 * @leaf_out:
 743 *
 744 * Returns: 0 on success, error code otherwise
 745 */
 746
 747static int get_leaf_nr(struct gfs2_inode *dip, u32 index,
 748                       u64 *leaf_out)
 749{
 750        __be64 *hash;
 751
 752        hash = gfs2_dir_get_hash_table(dip);
 753        if (IS_ERR(hash))
 754                return PTR_ERR(hash);
 755        *leaf_out = be64_to_cpu(*(hash + index));
 756        return 0;
 757}
 758
 759static int get_first_leaf(struct gfs2_inode *dip, u32 index,
 760                          struct buffer_head **bh_out)
 761{
 762        u64 leaf_no;
 763        int error;
 764
 765        error = get_leaf_nr(dip, index, &leaf_no);
 766        if (!error)
 767                error = get_leaf(dip, leaf_no, bh_out);
 768
 769        return error;
 770}
 771
 772static struct gfs2_dirent *gfs2_dirent_search(struct inode *inode,
 773                                              const struct qstr *name,
 774                                              gfs2_dscan_t scan,
 775                                              struct buffer_head **pbh)
 776{
 777        struct buffer_head *bh;
 778        struct gfs2_dirent *dent;
 779        struct gfs2_inode *ip = GFS2_I(inode);
 780        int error;
 781
 782        if (ip->i_diskflags & GFS2_DIF_EXHASH) {
 783                struct gfs2_leaf *leaf;
 784                unsigned hsize = 1 << ip->i_depth;
 785                unsigned index;
 786                u64 ln;
 787                if (hsize * sizeof(u64) != i_size_read(inode)) {
 788                        gfs2_consist_inode(ip);
 789                        return ERR_PTR(-EIO);
 790                }
 791
 792                index = name->hash >> (32 - ip->i_depth);
 793                error = get_first_leaf(ip, index, &bh);
 794                if (error)
 795                        return ERR_PTR(error);
 796                do {
 797                        dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
 798                                                scan, name, NULL);
 799                        if (dent)
 800                                goto got_dent;
 801                        leaf = (struct gfs2_leaf *)bh->b_data;
 802                        ln = be64_to_cpu(leaf->lf_next);
 803                        brelse(bh);
 804                        if (!ln)
 805                                break;
 806
 807                        error = get_leaf(ip, ln, &bh);
 808                } while(!error);
 809
 810                return error ? ERR_PTR(error) : NULL;
 811        }
 812
 813
 814        error = gfs2_meta_inode_buffer(ip, &bh);
 815        if (error)
 816                return ERR_PTR(error);
 817        dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, scan, name, NULL);
 818got_dent:
 819        if (unlikely(dent == NULL || IS_ERR(dent))) {
 820                brelse(bh);
 821                bh = NULL;
 822        }
 823        *pbh = bh;
 824        return dent;
 825}
 826
 827static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth)
 828{
 829        struct gfs2_inode *ip = GFS2_I(inode);
 830        unsigned int n = 1;
 831        u64 bn;
 832        int error;
 833        struct buffer_head *bh;
 834        struct gfs2_leaf *leaf;
 835        struct gfs2_dirent *dent;
 836        struct qstr name = { .name = "" };
 837
 838        error = gfs2_alloc_blocks(ip, &bn, &n, 0, NULL);
 839        if (error)
 840                return NULL;
 841        bh = gfs2_meta_new(ip->i_gl, bn);
 842        if (!bh)
 843                return NULL;
 844
 845        gfs2_trans_add_unrevoke(GFS2_SB(inode), bn, 1);
 846        gfs2_trans_add_meta(ip->i_gl, bh);
 847        gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
 848        leaf = (struct gfs2_leaf *)bh->b_data;
 849        leaf->lf_depth = cpu_to_be16(depth);
 850        leaf->lf_entries = 0;
 851        leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
 852        leaf->lf_next = 0;
 853        memset(leaf->lf_reserved, 0, sizeof(leaf->lf_reserved));
 854        dent = (struct gfs2_dirent *)(leaf+1);
 855        gfs2_qstr2dirent(&name, bh->b_size - sizeof(struct gfs2_leaf), dent);
 856        *pbh = bh;
 857        return leaf;
 858}
 859
 860/**
 861 * dir_make_exhash - Convert a stuffed directory into an ExHash directory
 862 * @dip: The GFS2 inode
 863 *
 864 * Returns: 0 on success, error code otherwise
 865 */
 866
 867static int dir_make_exhash(struct inode *inode)
 868{
 869        struct gfs2_inode *dip = GFS2_I(inode);
 870        struct gfs2_sbd *sdp = GFS2_SB(inode);
 871        struct gfs2_dirent *dent;
 872        struct qstr args;
 873        struct buffer_head *bh, *dibh;
 874        struct gfs2_leaf *leaf;
 875        int y;
 876        u32 x;
 877        __be64 *lp;
 878        u64 bn;
 879        int error;
 880
 881        error = gfs2_meta_inode_buffer(dip, &dibh);
 882        if (error)
 883                return error;
 884
 885        /*  Turn over a new leaf  */
 886
 887        leaf = new_leaf(inode, &bh, 0);
 888        if (!leaf)
 889                return -ENOSPC;
 890        bn = bh->b_blocknr;
 891
 892        gfs2_assert(sdp, dip->i_entries < (1 << 16));
 893        leaf->lf_entries = cpu_to_be16(dip->i_entries);
 894
 895        /*  Copy dirents  */
 896
 897        gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh,
 898                             sizeof(struct gfs2_dinode));
 899
 900        /*  Find last entry  */
 901
 902        x = 0;
 903        args.len = bh->b_size - sizeof(struct gfs2_dinode) +
 904                   sizeof(struct gfs2_leaf);
 905        args.name = bh->b_data;
 906        dent = gfs2_dirent_scan(&dip->i_inode, bh->b_data, bh->b_size,
 907                                gfs2_dirent_last, &args, NULL);
 908        if (!dent) {
 909                brelse(bh);
 910                brelse(dibh);
 911                return -EIO;
 912        }
 913        if (IS_ERR(dent)) {
 914                brelse(bh);
 915                brelse(dibh);
 916                return PTR_ERR(dent);
 917        }
 918
 919        /*  Adjust the last dirent's record length
 920           (Remember that dent still points to the last entry.)  */
 921
 922        dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) +
 923                sizeof(struct gfs2_dinode) -
 924                sizeof(struct gfs2_leaf));
 925
 926        brelse(bh);
 927
 928        /*  We're done with the new leaf block, now setup the new
 929            hash table.  */
 930
 931        gfs2_trans_add_meta(dip->i_gl, dibh);
 932        gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode));
 933
 934        lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode));
 935
 936        for (x = sdp->sd_hash_ptrs; x--; lp++)
 937                *lp = cpu_to_be64(bn);
 938
 939        i_size_write(inode, sdp->sd_sb.sb_bsize / 2);
 940        gfs2_add_inode_blocks(&dip->i_inode, 1);
 941        dip->i_diskflags |= GFS2_DIF_EXHASH;
 942
 943        for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ;
 944        dip->i_depth = y;
 945
 946        gfs2_dinode_out(dip, dibh->b_data);
 947
 948        brelse(dibh);
 949
 950        return 0;
 951}
 952
 953/**
 954 * dir_split_leaf - Split a leaf block into two
 955 * @dip: The GFS2 inode
 956 * @index:
 957 * @leaf_no:
 958 *
 959 * Returns: 0 on success, error code on failure
 960 */
 961
 962static int dir_split_leaf(struct inode *inode, const struct qstr *name)
 963{
 964        struct gfs2_inode *dip = GFS2_I(inode);
 965        struct buffer_head *nbh, *obh, *dibh;
 966        struct gfs2_leaf *nleaf, *oleaf;
 967        struct gfs2_dirent *dent = NULL, *prev = NULL, *next = NULL, *new;
 968        u32 start, len, half_len, divider;
 969        u64 bn, leaf_no;
 970        __be64 *lp;
 971        u32 index;
 972        int x, moved = 0;
 973        int error;
 974
 975        index = name->hash >> (32 - dip->i_depth);
 976        error = get_leaf_nr(dip, index, &leaf_no);
 977        if (error)
 978                return error;
 979
 980        /*  Get the old leaf block  */
 981        error = get_leaf(dip, leaf_no, &obh);
 982        if (error)
 983                return error;
 984
 985        oleaf = (struct gfs2_leaf *)obh->b_data;
 986        if (dip->i_depth == be16_to_cpu(oleaf->lf_depth)) {
 987                brelse(obh);
 988                return 1; /* can't split */
 989        }
 990
 991        gfs2_trans_add_meta(dip->i_gl, obh);
 992
 993        nleaf = new_leaf(inode, &nbh, be16_to_cpu(oleaf->lf_depth) + 1);
 994        if (!nleaf) {
 995                brelse(obh);
 996                return -ENOSPC;
 997        }
 998        bn = nbh->b_blocknr;
 999
1000        /*  Compute the start and len of leaf pointers in the hash table.  */
1001        len = 1 << (dip->i_depth - be16_to_cpu(oleaf->lf_depth));
1002        half_len = len >> 1;
1003        if (!half_len) {
1004                printk(KERN_WARNING "i_depth %u lf_depth %u index %u\n", dip->i_depth, be16_to_cpu(oleaf->lf_depth), index);
1005                gfs2_consist_inode(dip);
1006                error = -EIO;
1007                goto fail_brelse;
1008        }
1009
1010        start = (index & ~(len - 1));
1011
1012        /* Change the pointers.
1013           Don't bother distinguishing stuffed from non-stuffed.
1014           This code is complicated enough already. */
1015        lp = kmalloc(half_len * sizeof(__be64), GFP_NOFS);
1016        if (!lp) {
1017                error = -ENOMEM;
1018                goto fail_brelse;
1019        }
1020
1021        /*  Change the pointers  */
1022        for (x = 0; x < half_len; x++)
1023                lp[x] = cpu_to_be64(bn);
1024
1025        gfs2_dir_hash_inval(dip);
1026
1027        error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(u64),
1028                                    half_len * sizeof(u64));
1029        if (error != half_len * sizeof(u64)) {
1030                if (error >= 0)
1031                        error = -EIO;
1032                goto fail_lpfree;
1033        }
1034
1035        kfree(lp);
1036
1037        /*  Compute the divider  */
1038        divider = (start + half_len) << (32 - dip->i_depth);
1039
1040        /*  Copy the entries  */
1041        dent = (struct gfs2_dirent *)(obh->b_data + sizeof(struct gfs2_leaf));
1042
1043        do {
1044                next = dent;
1045                if (dirent_next(dip, obh, &next))
1046                        next = NULL;
1047
1048                if (!gfs2_dirent_sentinel(dent) &&
1049                    be32_to_cpu(dent->de_hash) < divider) {
1050                        struct qstr str;
1051                        str.name = (char*)(dent+1);
1052                        str.len = be16_to_cpu(dent->de_name_len);
1053                        str.hash = be32_to_cpu(dent->de_hash);
1054                        new = gfs2_dirent_alloc(inode, nbh, &str);
1055                        if (IS_ERR(new)) {
1056                                error = PTR_ERR(new);
1057                                break;
1058                        }
1059
1060                        new->de_inum = dent->de_inum; /* No endian worries */
1061                        new->de_type = dent->de_type; /* No endian worries */
1062                        be16_add_cpu(&nleaf->lf_entries, 1);
1063
1064                        dirent_del(dip, obh, prev, dent);
1065
1066                        if (!oleaf->lf_entries)
1067                                gfs2_consist_inode(dip);
1068                        be16_add_cpu(&oleaf->lf_entries, -1);
1069
1070                        if (!prev)
1071                                prev = dent;
1072
1073                        moved = 1;
1074                } else {
1075                        prev = dent;
1076                }
1077                dent = next;
1078        } while (dent);
1079
1080        oleaf->lf_depth = nleaf->lf_depth;
1081
1082        error = gfs2_meta_inode_buffer(dip, &dibh);
1083        if (!gfs2_assert_withdraw(GFS2_SB(&dip->i_inode), !error)) {
1084                gfs2_trans_add_meta(dip->i_gl, dibh);
1085                gfs2_add_inode_blocks(&dip->i_inode, 1);
1086                gfs2_dinode_out(dip, dibh->b_data);
1087                brelse(dibh);
1088        }
1089
1090        brelse(obh);
1091        brelse(nbh);
1092
1093        return error;
1094
1095fail_lpfree:
1096        kfree(lp);
1097
1098fail_brelse:
1099        brelse(obh);
1100        brelse(nbh);
1101        return error;
1102}
1103
1104/**
1105 * dir_double_exhash - Double size of ExHash table
1106 * @dip: The GFS2 dinode
1107 *
1108 * Returns: 0 on success, error code on failure
1109 */
1110
1111static int dir_double_exhash(struct gfs2_inode *dip)
1112{
1113        struct buffer_head *dibh;
1114        u32 hsize;
1115        u32 hsize_bytes;
1116        __be64 *hc;
1117        __be64 *hc2, *h;
1118        int x;
1119        int error = 0;
1120
1121        hsize = 1 << dip->i_depth;
1122        hsize_bytes = hsize * sizeof(__be64);
1123
1124        hc = gfs2_dir_get_hash_table(dip);
1125        if (IS_ERR(hc))
1126                return PTR_ERR(hc);
1127
1128        hc2 = kmalloc(hsize_bytes * 2, GFP_NOFS | __GFP_NOWARN);
1129        if (hc2 == NULL)
1130                hc2 = __vmalloc(hsize_bytes * 2, GFP_NOFS, PAGE_KERNEL);
1131
1132        if (!hc2)
1133                return -ENOMEM;
1134
1135        h = hc2;
1136        error = gfs2_meta_inode_buffer(dip, &dibh);
1137        if (error)
1138                goto out_kfree;
1139
1140        for (x = 0; x < hsize; x++) {
1141                *h++ = *hc;
1142                *h++ = *hc;
1143                hc++;
1144        }
1145
1146        error = gfs2_dir_write_data(dip, (char *)hc2, 0, hsize_bytes * 2);
1147        if (error != (hsize_bytes * 2))
1148                goto fail;
1149
1150        gfs2_dir_hash_inval(dip);
1151        dip->i_hash_cache = hc2;
1152        dip->i_depth++;
1153        gfs2_dinode_out(dip, dibh->b_data);
1154        brelse(dibh);
1155        return 0;
1156
1157fail:
1158        /* Replace original hash table & size */
1159        gfs2_dir_write_data(dip, (char *)hc, 0, hsize_bytes);
1160        i_size_write(&dip->i_inode, hsize_bytes);
1161        gfs2_dinode_out(dip, dibh->b_data);
1162        brelse(dibh);
1163out_kfree:
1164        if (is_vmalloc_addr(hc2))
1165                vfree(hc2);
1166        else
1167                kfree(hc2);
1168        return error;
1169}
1170
1171/**
1172 * compare_dents - compare directory entries by hash value
1173 * @a: first dent
1174 * @b: second dent
1175 *
1176 * When comparing the hash entries of @a to @b:
1177 *   gt: returns 1
1178 *   lt: returns -1
1179 *   eq: returns 0
1180 */
1181
1182static int compare_dents(const void *a, const void *b)
1183{
1184        const struct gfs2_dirent *dent_a, *dent_b;
1185        u32 hash_a, hash_b;
1186        int ret = 0;
1187
1188        dent_a = *(const struct gfs2_dirent **)a;
1189        hash_a = be32_to_cpu(dent_a->de_hash);
1190
1191        dent_b = *(const struct gfs2_dirent **)b;
1192        hash_b = be32_to_cpu(dent_b->de_hash);
1193
1194        if (hash_a > hash_b)
1195                ret = 1;
1196        else if (hash_a < hash_b)
1197                ret = -1;
1198        else {
1199                unsigned int len_a = be16_to_cpu(dent_a->de_name_len);
1200                unsigned int len_b = be16_to_cpu(dent_b->de_name_len);
1201
1202                if (len_a > len_b)
1203                        ret = 1;
1204                else if (len_a < len_b)
1205                        ret = -1;
1206                else
1207                        ret = memcmp(dent_a + 1, dent_b + 1, len_a);
1208        }
1209
1210        return ret;
1211}
1212
1213/**
1214 * do_filldir_main - read out directory entries
1215 * @dip: The GFS2 inode
1216 * @ctx: what to feed the entries to
1217 * @darr: an array of struct gfs2_dirent pointers to read
1218 * @entries: the number of entries in darr
1219 * @copied: pointer to int that's non-zero if a entry has been copied out
1220 *
1221 * Jump through some hoops to make sure that if there are hash collsions,
1222 * they are read out at the beginning of a buffer.  We want to minimize
1223 * the possibility that they will fall into different readdir buffers or
1224 * that someone will want to seek to that location.
1225 *
1226 * Returns: errno, >0 if the actor tells you to stop
1227 */
1228
1229static int do_filldir_main(struct gfs2_inode *dip, struct dir_context *ctx,
1230                           const struct gfs2_dirent **darr, u32 entries,
1231                           int *copied)
1232{
1233        const struct gfs2_dirent *dent, *dent_next;
1234        u64 off, off_next;
1235        unsigned int x, y;
1236        int run = 0;
1237
1238        sort(darr, entries, sizeof(struct gfs2_dirent *), compare_dents, NULL);
1239
1240        dent_next = darr[0];
1241        off_next = be32_to_cpu(dent_next->de_hash);
1242        off_next = gfs2_disk_hash2offset(off_next);
1243
1244        for (x = 0, y = 1; x < entries; x++, y++) {
1245                dent = dent_next;
1246                off = off_next;
1247
1248                if (y < entries) {
1249                        dent_next = darr[y];
1250                        off_next = be32_to_cpu(dent_next->de_hash);
1251                        off_next = gfs2_disk_hash2offset(off_next);
1252
1253                        if (off < ctx->pos)
1254                                continue;
1255                        ctx->pos = off;
1256
1257                        if (off_next == off) {
1258                                if (*copied && !run)
1259                                        return 1;
1260                                run = 1;
1261                        } else
1262                                run = 0;
1263                } else {
1264                        if (off < ctx->pos)
1265                                continue;
1266                        ctx->pos = off;
1267                }
1268
1269                if (!dir_emit(ctx, (const char *)(dent + 1),
1270                                be16_to_cpu(dent->de_name_len),
1271                                be64_to_cpu(dent->de_inum.no_addr),
1272                                be16_to_cpu(dent->de_type)))
1273                        return 1;
1274
1275                *copied = 1;
1276        }
1277
1278        /* Increment the ctx->pos by one, so the next time we come into the
1279           do_filldir fxn, we get the next entry instead of the last one in the
1280           current leaf */
1281
1282        ctx->pos++;
1283
1284        return 0;
1285}
1286
1287static void *gfs2_alloc_sort_buffer(unsigned size)
1288{
1289        void *ptr = NULL;
1290
1291        if (size < KMALLOC_MAX_SIZE)
1292                ptr = kmalloc(size, GFP_NOFS | __GFP_NOWARN);
1293        if (!ptr)
1294                ptr = __vmalloc(size, GFP_NOFS, PAGE_KERNEL);
1295        return ptr;
1296}
1297
1298static void gfs2_free_sort_buffer(void *ptr)
1299{
1300        if (is_vmalloc_addr(ptr))
1301                vfree(ptr);
1302        else
1303                kfree(ptr);
1304}
1305
1306static int gfs2_dir_read_leaf(struct inode *inode, struct dir_context *ctx,
1307                              int *copied, unsigned *depth,
1308                              u64 leaf_no)
1309{
1310        struct gfs2_inode *ip = GFS2_I(inode);
1311        struct gfs2_sbd *sdp = GFS2_SB(inode);
1312        struct buffer_head *bh;
1313        struct gfs2_leaf *lf;
1314        unsigned entries = 0, entries2 = 0;
1315        unsigned leaves = 0;
1316        const struct gfs2_dirent **darr, *dent;
1317        struct dirent_gather g;
1318        struct buffer_head **larr;
1319        int leaf = 0;
1320        int error, i;
1321        u64 lfn = leaf_no;
1322
1323        do {
1324                error = get_leaf(ip, lfn, &bh);
1325                if (error)
1326                        goto out;
1327                lf = (struct gfs2_leaf *)bh->b_data;
1328                if (leaves == 0)
1329                        *depth = be16_to_cpu(lf->lf_depth);
1330                entries += be16_to_cpu(lf->lf_entries);
1331                leaves++;
1332                lfn = be64_to_cpu(lf->lf_next);
1333                brelse(bh);
1334        } while(lfn);
1335
1336        if (!entries)
1337                return 0;
1338
1339        error = -ENOMEM;
1340        /*
1341         * The extra 99 entries are not normally used, but are a buffer
1342         * zone in case the number of entries in the leaf is corrupt.
1343         * 99 is the maximum number of entries that can fit in a single
1344         * leaf block.
1345         */
1346        larr = gfs2_alloc_sort_buffer((leaves + entries + 99) * sizeof(void *));
1347        if (!larr)
1348                goto out;
1349        darr = (const struct gfs2_dirent **)(larr + leaves);
1350        g.pdent = darr;
1351        g.offset = 0;
1352        lfn = leaf_no;
1353
1354        do {
1355                error = get_leaf(ip, lfn, &bh);
1356                if (error)
1357                        goto out_free;
1358                lf = (struct gfs2_leaf *)bh->b_data;
1359                lfn = be64_to_cpu(lf->lf_next);
1360                if (lf->lf_entries) {
1361                        entries2 += be16_to_cpu(lf->lf_entries);
1362                        dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
1363                                                gfs2_dirent_gather, NULL, &g);
1364                        error = PTR_ERR(dent);
1365                        if (IS_ERR(dent))
1366                                goto out_free;
1367                        if (entries2 != g.offset) {
1368                                fs_warn(sdp, "Number of entries corrupt in dir "
1369                                                "leaf %llu, entries2 (%u) != "
1370                                                "g.offset (%u)\n",
1371                                        (unsigned long long)bh->b_blocknr,
1372                                        entries2, g.offset);
1373                                        
1374                                error = -EIO;
1375                                goto out_free;
1376                        }
1377                        error = 0;
1378                        larr[leaf++] = bh;
1379                } else {
1380                        brelse(bh);
1381                }
1382        } while(lfn);
1383
1384        BUG_ON(entries2 != entries);
1385        error = do_filldir_main(ip, ctx, darr, entries, copied);
1386out_free:
1387        for(i = 0; i < leaf; i++)
1388                brelse(larr[i]);
1389        gfs2_free_sort_buffer(larr);
1390out:
1391        return error;
1392}
1393
1394/**
1395 * gfs2_dir_readahead - Issue read-ahead requests for leaf blocks.
1396 *
1397 * Note: we can't calculate each index like dir_e_read can because we don't
1398 * have the leaf, and therefore we don't have the depth, and therefore we
1399 * don't have the length. So we have to just read enough ahead to make up
1400 * for the loss of information.
1401 */
1402static void gfs2_dir_readahead(struct inode *inode, unsigned hsize, u32 index,
1403                               struct file_ra_state *f_ra)
1404{
1405        struct gfs2_inode *ip = GFS2_I(inode);
1406        struct gfs2_glock *gl = ip->i_gl;
1407        struct buffer_head *bh;
1408        u64 blocknr = 0, last;
1409        unsigned count;
1410
1411        /* First check if we've already read-ahead for the whole range. */
1412        if (index + MAX_RA_BLOCKS < f_ra->start)
1413                return;
1414
1415        f_ra->start = max((pgoff_t)index, f_ra->start);
1416        for (count = 0; count < MAX_RA_BLOCKS; count++) {
1417                if (f_ra->start >= hsize) /* if exceeded the hash table */
1418                        break;
1419
1420                last = blocknr;
1421                blocknr = be64_to_cpu(ip->i_hash_cache[f_ra->start]);
1422                f_ra->start++;
1423                if (blocknr == last)
1424                        continue;
1425
1426                bh = gfs2_getbuf(gl, blocknr, 1);
1427                if (trylock_buffer(bh)) {
1428                        if (buffer_uptodate(bh)) {
1429                                unlock_buffer(bh);
1430                                brelse(bh);
1431                                continue;
1432                        }
1433                        bh->b_end_io = end_buffer_read_sync;
1434                        submit_bh(READA | REQ_META, bh);
1435                        continue;
1436                }
1437                brelse(bh);
1438        }
1439}
1440
1441/**
1442 * dir_e_read - Reads the entries from a directory into a filldir buffer
1443 * @dip: dinode pointer
1444 * @ctx: actor to feed the entries to
1445 *
1446 * Returns: errno
1447 */
1448
1449static int dir_e_read(struct inode *inode, struct dir_context *ctx,
1450                      struct file_ra_state *f_ra)
1451{
1452        struct gfs2_inode *dip = GFS2_I(inode);
1453        u32 hsize, len = 0;
1454        u32 hash, index;
1455        __be64 *lp;
1456        int copied = 0;
1457        int error = 0;
1458        unsigned depth = 0;
1459
1460        hsize = 1 << dip->i_depth;
1461        hash = gfs2_dir_offset2hash(ctx->pos);
1462        index = hash >> (32 - dip->i_depth);
1463
1464        if (dip->i_hash_cache == NULL)
1465                f_ra->start = 0;
1466        lp = gfs2_dir_get_hash_table(dip);
1467        if (IS_ERR(lp))
1468                return PTR_ERR(lp);
1469
1470        gfs2_dir_readahead(inode, hsize, index, f_ra);
1471
1472        while (index < hsize) {
1473                error = gfs2_dir_read_leaf(inode, ctx,
1474                                           &copied, &depth,
1475                                           be64_to_cpu(lp[index]));
1476                if (error)
1477                        break;
1478
1479                len = 1 << (dip->i_depth - depth);
1480                index = (index & ~(len - 1)) + len;
1481        }
1482
1483        if (error > 0)
1484                error = 0;
1485        return error;
1486}
1487
1488int gfs2_dir_read(struct inode *inode, struct dir_context *ctx,
1489                  struct file_ra_state *f_ra)
1490{
1491        struct gfs2_inode *dip = GFS2_I(inode);
1492        struct gfs2_sbd *sdp = GFS2_SB(inode);
1493        struct dirent_gather g;
1494        const struct gfs2_dirent **darr, *dent;
1495        struct buffer_head *dibh;
1496        int copied = 0;
1497        int error;
1498
1499        if (!dip->i_entries)
1500                return 0;
1501
1502        if (dip->i_diskflags & GFS2_DIF_EXHASH)
1503                return dir_e_read(inode, ctx, f_ra);
1504
1505        if (!gfs2_is_stuffed(dip)) {
1506                gfs2_consist_inode(dip);
1507                return -EIO;
1508        }
1509
1510        error = gfs2_meta_inode_buffer(dip, &dibh);
1511        if (error)
1512                return error;
1513
1514        error = -ENOMEM;
1515        /* 96 is max number of dirents which can be stuffed into an inode */
1516        darr = kmalloc(96 * sizeof(struct gfs2_dirent *), GFP_NOFS);
1517        if (darr) {
1518                g.pdent = darr;
1519                g.offset = 0;
1520                dent = gfs2_dirent_scan(inode, dibh->b_data, dibh->b_size,
1521                                        gfs2_dirent_gather, NULL, &g);
1522                if (IS_ERR(dent)) {
1523                        error = PTR_ERR(dent);
1524                        goto out;
1525                }
1526                if (dip->i_entries != g.offset) {
1527                        fs_warn(sdp, "Number of entries corrupt in dir %llu, "
1528                                "ip->i_entries (%u) != g.offset (%u)\n",
1529                                (unsigned long long)dip->i_no_addr,
1530                                dip->i_entries,
1531                                g.offset);
1532                        error = -EIO;
1533                        goto out;
1534                }
1535                error = do_filldir_main(dip, ctx, darr,
1536                                        dip->i_entries, &copied);
1537out:
1538                kfree(darr);
1539        }
1540
1541        if (error > 0)
1542                error = 0;
1543
1544        brelse(dibh);
1545
1546        return error;
1547}
1548
1549/**
1550 * gfs2_dir_search - Search a directory
1551 * @dip: The GFS2 dir inode
1552 * @name: The name we are looking up
1553 * @fail_on_exist: Fail if the name exists rather than looking it up
1554 *
1555 * This routine searches a directory for a file or another directory.
1556 * Assumes a glock is held on dip.
1557 *
1558 * Returns: errno
1559 */
1560
1561struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name,
1562                              bool fail_on_exist)
1563{
1564        struct buffer_head *bh;
1565        struct gfs2_dirent *dent;
1566        u64 addr, formal_ino;
1567        u16 dtype;
1568
1569        dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
1570        if (dent) {
1571                if (IS_ERR(dent))
1572                        return ERR_CAST(dent);
1573                dtype = be16_to_cpu(dent->de_type);
1574                addr = be64_to_cpu(dent->de_inum.no_addr);
1575                formal_ino = be64_to_cpu(dent->de_inum.no_formal_ino);
1576                brelse(bh);
1577                if (fail_on_exist)
1578                        return ERR_PTR(-EEXIST);
1579                return gfs2_inode_lookup(dir->i_sb, dtype, addr, formal_ino, 0);
1580        }
1581        return ERR_PTR(-ENOENT);
1582}
1583
1584int gfs2_dir_check(struct inode *dir, const struct qstr *name,
1585                   const struct gfs2_inode *ip)
1586{
1587        struct buffer_head *bh;
1588        struct gfs2_dirent *dent;
1589        int ret = -ENOENT;
1590
1591        dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
1592        if (dent) {
1593                if (IS_ERR(dent))
1594                        return PTR_ERR(dent);
1595                if (ip) {
1596                        if (be64_to_cpu(dent->de_inum.no_addr) != ip->i_no_addr)
1597                                goto out;
1598                        if (be64_to_cpu(dent->de_inum.no_formal_ino) !=
1599                            ip->i_no_formal_ino)
1600                                goto out;
1601                        if (unlikely(IF2DT(ip->i_inode.i_mode) !=
1602                            be16_to_cpu(dent->de_type))) {
1603                                gfs2_consist_inode(GFS2_I(dir));
1604                                ret = -EIO;
1605                                goto out;
1606                        }
1607                }
1608                ret = 0;
1609out:
1610                brelse(bh);
1611        }
1612        return ret;
1613}
1614
1615static int dir_new_leaf(struct inode *inode, const struct qstr *name)
1616{
1617        struct buffer_head *bh, *obh;
1618        struct gfs2_inode *ip = GFS2_I(inode);
1619        struct gfs2_leaf *leaf, *oleaf;
1620        int error;
1621        u32 index;
1622        u64 bn;
1623
1624        index = name->hash >> (32 - ip->i_depth);
1625        error = get_first_leaf(ip, index, &obh);
1626        if (error)
1627                return error;
1628        do {
1629                oleaf = (struct gfs2_leaf *)obh->b_data;
1630                bn = be64_to_cpu(oleaf->lf_next);
1631                if (!bn)
1632                        break;
1633                brelse(obh);
1634                error = get_leaf(ip, bn, &obh);
1635                if (error)
1636                        return error;
1637        } while(1);
1638
1639        gfs2_trans_add_meta(ip->i_gl, obh);
1640
1641        leaf = new_leaf(inode, &bh, be16_to_cpu(oleaf->lf_depth));
1642        if (!leaf) {
1643                brelse(obh);
1644                return -ENOSPC;
1645        }
1646        oleaf->lf_next = cpu_to_be64(bh->b_blocknr);
1647        brelse(bh);
1648        brelse(obh);
1649
1650        error = gfs2_meta_inode_buffer(ip, &bh);
1651        if (error)
1652                return error;
1653        gfs2_trans_add_meta(ip->i_gl, bh);
1654        gfs2_add_inode_blocks(&ip->i_inode, 1);
1655        gfs2_dinode_out(ip, bh->b_data);
1656        brelse(bh);
1657        return 0;
1658}
1659
1660/**
1661 * gfs2_dir_add - Add new filename into directory
1662 * @dip: The GFS2 inode
1663 * @filename: The new name
1664 * @inode: The inode number of the entry
1665 * @type: The type of the entry
1666 *
1667 * Returns: 0 on success, error code on failure
1668 */
1669
1670int gfs2_dir_add(struct inode *inode, const struct qstr *name,
1671                 const struct gfs2_inode *nip)
1672{
1673        struct gfs2_inode *ip = GFS2_I(inode);
1674        struct buffer_head *bh;
1675        struct gfs2_dirent *dent;
1676        struct gfs2_leaf *leaf;
1677        int error;
1678
1679        while(1) {
1680                dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space,
1681                                          &bh);
1682                if (dent) {
1683                        if (IS_ERR(dent))
1684                                return PTR_ERR(dent);
1685                        dent = gfs2_init_dirent(inode, dent, name, bh);
1686                        gfs2_inum_out(nip, dent);
1687                        dent->de_type = cpu_to_be16(IF2DT(nip->i_inode.i_mode));
1688                        if (ip->i_diskflags & GFS2_DIF_EXHASH) {
1689                                leaf = (struct gfs2_leaf *)bh->b_data;
1690                                be16_add_cpu(&leaf->lf_entries, 1);
1691                        }
1692                        brelse(bh);
1693                        ip->i_entries++;
1694                        ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
1695                        if (S_ISDIR(nip->i_inode.i_mode))
1696                                inc_nlink(&ip->i_inode);
1697                        mark_inode_dirty(inode);
1698                        error = 0;
1699                        break;
1700                }
1701                if (!(ip->i_diskflags & GFS2_DIF_EXHASH)) {
1702                        error = dir_make_exhash(inode);
1703                        if (error)
1704                                break;
1705                        continue;
1706                }
1707                error = dir_split_leaf(inode, name);
1708                if (error == 0)
1709                        continue;
1710                if (error < 0)
1711                        break;
1712                if (ip->i_depth < GFS2_DIR_MAX_DEPTH) {
1713                        error = dir_double_exhash(ip);
1714                        if (error)
1715                                break;
1716                        error = dir_split_leaf(inode, name);
1717                        if (error < 0)
1718                                break;
1719                        if (error == 0)
1720                                continue;
1721                }
1722                error = dir_new_leaf(inode, name);
1723                if (!error)
1724                        continue;
1725                error = -ENOSPC;
1726                break;
1727        }
1728        return error;
1729}
1730
1731
1732/**
1733 * gfs2_dir_del - Delete a directory entry
1734 * @dip: The GFS2 inode
1735 * @filename: The filename
1736 *
1737 * Returns: 0 on success, error code on failure
1738 */
1739
1740int gfs2_dir_del(struct gfs2_inode *dip, const struct dentry *dentry)
1741{
1742        const struct qstr *name = &dentry->d_name;
1743        struct gfs2_dirent *dent, *prev = NULL;
1744        struct buffer_head *bh;
1745
1746        /* Returns _either_ the entry (if its first in block) or the
1747           previous entry otherwise */
1748        dent = gfs2_dirent_search(&dip->i_inode, name, gfs2_dirent_prev, &bh);
1749        if (!dent) {
1750                gfs2_consist_inode(dip);
1751                return -EIO;
1752        }
1753        if (IS_ERR(dent)) {
1754                gfs2_consist_inode(dip);
1755                return PTR_ERR(dent);
1756        }
1757        /* If not first in block, adjust pointers accordingly */
1758        if (gfs2_dirent_find(dent, name, NULL) == 0) {
1759                prev = dent;
1760                dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len));
1761        }
1762
1763        dirent_del(dip, bh, prev, dent);
1764        if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1765                struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
1766                u16 entries = be16_to_cpu(leaf->lf_entries);
1767                if (!entries)
1768                        gfs2_consist_inode(dip);
1769                leaf->lf_entries = cpu_to_be16(--entries);
1770        }
1771        brelse(bh);
1772
1773        if (!dip->i_entries)
1774                gfs2_consist_inode(dip);
1775        dip->i_entries--;
1776        dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME;
1777        if (S_ISDIR(dentry->d_inode->i_mode))
1778                drop_nlink(&dip->i_inode);
1779        mark_inode_dirty(&dip->i_inode);
1780
1781        return 0;
1782}
1783
1784/**
1785 * gfs2_dir_mvino - Change inode number of directory entry
1786 * @dip: The GFS2 inode
1787 * @filename:
1788 * @new_inode:
1789 *
1790 * This routine changes the inode number of a directory entry.  It's used
1791 * by rename to change ".." when a directory is moved.
1792 * Assumes a glock is held on dvp.
1793 *
1794 * Returns: errno
1795 */
1796
1797int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename,
1798                   const struct gfs2_inode *nip, unsigned int new_type)
1799{
1800        struct buffer_head *bh;
1801        struct gfs2_dirent *dent;
1802        int error;
1803
1804        dent = gfs2_dirent_search(&dip->i_inode, filename, gfs2_dirent_find, &bh);
1805        if (!dent) {
1806                gfs2_consist_inode(dip);
1807                return -EIO;
1808        }
1809        if (IS_ERR(dent))
1810                return PTR_ERR(dent);
1811
1812        gfs2_trans_add_meta(dip->i_gl, bh);
1813        gfs2_inum_out(nip, dent);
1814        dent->de_type = cpu_to_be16(new_type);
1815
1816        if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1817                brelse(bh);
1818                error = gfs2_meta_inode_buffer(dip, &bh);
1819                if (error)
1820                        return error;
1821                gfs2_trans_add_meta(dip->i_gl, bh);
1822        }
1823
1824        dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME;
1825        gfs2_dinode_out(dip, bh->b_data);
1826        brelse(bh);
1827        return 0;
1828}
1829
1830/**
1831 * leaf_dealloc - Deallocate a directory leaf
1832 * @dip: the directory
1833 * @index: the hash table offset in the directory
1834 * @len: the number of pointers to this leaf
1835 * @leaf_no: the leaf number
1836 * @leaf_bh: buffer_head for the starting leaf
1837 * last_dealloc: 1 if this is the final dealloc for the leaf, else 0
1838 *
1839 * Returns: errno
1840 */
1841
1842static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len,
1843                        u64 leaf_no, struct buffer_head *leaf_bh,
1844                        int last_dealloc)
1845{
1846        struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode);
1847        struct gfs2_leaf *tmp_leaf;
1848        struct gfs2_rgrp_list rlist;
1849        struct buffer_head *bh, *dibh;
1850        u64 blk, nblk;
1851        unsigned int rg_blocks = 0, l_blocks = 0;
1852        char *ht;
1853        unsigned int x, size = len * sizeof(u64);
1854        int error;
1855
1856        error = gfs2_rindex_update(sdp);
1857        if (error)
1858                return error;
1859
1860        memset(&rlist, 0, sizeof(struct gfs2_rgrp_list));
1861
1862        ht = kzalloc(size, GFP_NOFS | __GFP_NOWARN);
1863        if (ht == NULL)
1864                ht = vzalloc(size);
1865        if (!ht)
1866                return -ENOMEM;
1867
1868        error = gfs2_quota_hold(dip, NO_UID_QUOTA_CHANGE, NO_GID_QUOTA_CHANGE);
1869        if (error)
1870                goto out;
1871
1872        /*  Count the number of leaves  */
1873        bh = leaf_bh;
1874
1875        for (blk = leaf_no; blk; blk = nblk) {
1876                if (blk != leaf_no) {
1877                        error = get_leaf(dip, blk, &bh);
1878                        if (error)
1879                                goto out_rlist;
1880                }
1881                tmp_leaf = (struct gfs2_leaf *)bh->b_data;
1882                nblk = be64_to_cpu(tmp_leaf->lf_next);
1883                if (blk != leaf_no)
1884                        brelse(bh);
1885
1886                gfs2_rlist_add(dip, &rlist, blk);
1887                l_blocks++;
1888        }
1889
1890        gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE);
1891
1892        for (x = 0; x < rlist.rl_rgrps; x++) {
1893                struct gfs2_rgrpd *rgd;
1894                rgd = rlist.rl_ghs[x].gh_gl->gl_object;
1895                rg_blocks += rgd->rd_length;
1896        }
1897
1898        error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs);
1899        if (error)
1900                goto out_rlist;
1901
1902        error = gfs2_trans_begin(sdp,
1903                        rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) +
1904                        RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks);
1905        if (error)
1906                goto out_rg_gunlock;
1907
1908        bh = leaf_bh;
1909
1910        for (blk = leaf_no; blk; blk = nblk) {
1911                if (blk != leaf_no) {
1912                        error = get_leaf(dip, blk, &bh);
1913                        if (error)
1914                                goto out_end_trans;
1915                }
1916                tmp_leaf = (struct gfs2_leaf *)bh->b_data;
1917                nblk = be64_to_cpu(tmp_leaf->lf_next);
1918                if (blk != leaf_no)
1919                        brelse(bh);
1920
1921                gfs2_free_meta(dip, blk, 1);
1922                gfs2_add_inode_blocks(&dip->i_inode, -1);
1923        }
1924
1925        error = gfs2_dir_write_data(dip, ht, index * sizeof(u64), size);
1926        if (error != size) {
1927                if (error >= 0)
1928                        error = -EIO;
1929                goto out_end_trans;
1930        }
1931
1932        error = gfs2_meta_inode_buffer(dip, &dibh);
1933        if (error)
1934                goto out_end_trans;
1935
1936        gfs2_trans_add_meta(dip->i_gl, dibh);
1937        /* On the last dealloc, make this a regular file in case we crash.
1938           (We don't want to free these blocks a second time.)  */
1939        if (last_dealloc)
1940                dip->i_inode.i_mode = S_IFREG;
1941        gfs2_dinode_out(dip, dibh->b_data);
1942        brelse(dibh);
1943
1944out_end_trans:
1945        gfs2_trans_end(sdp);
1946out_rg_gunlock:
1947        gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs);
1948out_rlist:
1949        gfs2_rlist_free(&rlist);
1950        gfs2_quota_unhold(dip);
1951out:
1952        if (is_vmalloc_addr(ht))
1953                vfree(ht);
1954        else
1955                kfree(ht);
1956        return error;
1957}
1958
1959/**
1960 * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory
1961 * @dip: the directory
1962 *
1963 * Dealloc all on-disk directory leaves to FREEMETA state
1964 * Change on-disk inode type to "regular file"
1965 *
1966 * Returns: errno
1967 */
1968
1969int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip)
1970{
1971        struct buffer_head *bh;
1972        struct gfs2_leaf *leaf;
1973        u32 hsize, len;
1974        u32 index = 0, next_index;
1975        __be64 *lp;
1976        u64 leaf_no;
1977        int error = 0, last;
1978
1979        hsize = 1 << dip->i_depth;
1980
1981        lp = gfs2_dir_get_hash_table(dip);
1982        if (IS_ERR(lp))
1983                return PTR_ERR(lp);
1984
1985        while (index < hsize) {
1986                leaf_no = be64_to_cpu(lp[index]);
1987                if (leaf_no) {
1988                        error = get_leaf(dip, leaf_no, &bh);
1989                        if (error)
1990                                goto out;
1991                        leaf = (struct gfs2_leaf *)bh->b_data;
1992                        len = 1 << (dip->i_depth - be16_to_cpu(leaf->lf_depth));
1993
1994                        next_index = (index & ~(len - 1)) + len;
1995                        last = ((next_index >= hsize) ? 1 : 0);
1996                        error = leaf_dealloc(dip, index, len, leaf_no, bh,
1997                                             last);
1998                        brelse(bh);
1999                        if (error)
2000                                goto out;
2001                        index = next_index;
2002                } else
2003                        index++;
2004        }
2005
2006        if (index != hsize) {
2007                gfs2_consist_inode(dip);
2008                error = -EIO;
2009        }
2010
2011out:
2012
2013        return error;
2014}
2015
2016/**
2017 * gfs2_diradd_alloc_required - find if adding entry will require an allocation
2018 * @ip: the file being written to
2019 * @filname: the filename that's going to be added
2020 *
2021 * Returns: 1 if alloc required, 0 if not, -ve on error
2022 */
2023
2024int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name)
2025{
2026        struct gfs2_dirent *dent;
2027        struct buffer_head *bh;
2028
2029        dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh);
2030        if (!dent) {
2031                return 1;
2032        }
2033        if (IS_ERR(dent))
2034                return PTR_ERR(dent);
2035        brelse(bh);
2036        return 0;
2037}
2038
2039