fs/ocfs2/dir.c

   1 /* -*- mode: c; c-basic-offset: 8; -*-
   2  * vim: noexpandtab sw=8 ts=8 sts=0:
   3  *
   4  * dir.c
   5  *
   6  * Creates, reads, walks and deletes directory-nodes
   7  *
   8  * Copyright (C) 2002, 2004 Oracle.  All rights reserved.
   9  *
  10  *  Portions of this code from linux/fs/ext3/dir.c
  11  *
  12  *  Copyright (C) 1992, 1993, 1994, 1995
  13  *  Remy Card (card@masi.ibp.fr)
  14  *  Laboratoire MASI - Institut Blaise pascal
  15  *  Universite Pierre et Marie Curie (Paris VI)
  16  *
  17  *   from
  18  *
  19  *   linux/fs/minix/dir.c
  20  *
  21  *   Copyright (C) 1991, 1992 Linus Torvalds
  22  *
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public
  25  * License as published by the Free Software Foundation; either
  26  * version 2 of the License, or (at your option) any later version.
  27  *
  28  * This program is distributed in the hope that it will be useful,
  29  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  30  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  31  * General Public License for more details.
  32  *
  33  * You should have received a copy of the GNU General Public
  34  * License along with this program; if not, write to the
  35  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  36  * Boston, MA 021110-1307, USA.
  37  */
  38
  39 #include <linux/fs.h>
  40 #include <linux/types.h>
  41 #include <linux/slab.h>
  42 #include <linux/highmem.h>
  43 #include <linux/quotaops.h>
  44 #include <linux/sort.h>
  45 #include <linux/iversion.h>
  46
  47 #include <cluster/masklog.h>
  48
  49 #include "ocfs2.h"
  50
  51 #include "alloc.h"
  52 #include "blockcheck.h"
  53 #include "dir.h"
  54 #include "dlmglue.h"
  55 #include "extent_map.h"
  56 #include "file.h"
  57 #include "inode.h"
  58 #include "journal.h"
  59 #include "namei.h"
  60 #include "suballoc.h"
  61 #include "super.h"
  62 #include "sysfile.h"
  63 #include "uptodate.h"
  64 #include "ocfs2_trace.h"
  65
  66 #include "buffer_head_io.h"
  67
  68 #define NAMEI_RA_CHUNKS  2
  69 #define NAMEI_RA_BLOCKS  4
  70 #define NAMEI_RA_SIZE        (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
  71
  72 static unsigned char ocfs2_filetype_table[] = {
  73         DT_UNKNOWN, DT_REG, DT_DIR, DT_CHR, DT_BLK, DT_FIFO, DT_SOCK, DT_LNK
  74 };
  75
  76 static int ocfs2_do_extend_dir(struct super_block *sb,
  77                                handle_t *handle,
  78                                struct inode *dir,
  79                                struct buffer_head *parent_fe_bh,
  80                                struct ocfs2_alloc_context *data_ac,
  81                                struct ocfs2_alloc_context *meta_ac,
  82                                struct buffer_head **new_bh);
  83 static int ocfs2_dir_indexed(struct inode *inode);
  84
  85 /*
  86  * These are distinct checks because future versions of the file system will
  87  * want to have a trailing dirent structure independent of indexing.
  88  */
  89 static int ocfs2_supports_dir_trailer(struct inode *dir)
  90 {
  91         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
  92
  93         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
  94                 return 0;
  95
  96         return ocfs2_meta_ecc(osb) || ocfs2_dir_indexed(dir);
  97 }
  98
  99 /*
 100  * "new' here refers to the point at which we're creating a new
 101  * directory via "mkdir()", but also when we're expanding an inline
 102  * directory. In either case, we don't yet have the indexing bit set
 103  * on the directory, so the standard checks will fail in when metaecc
 104  * is turned off. Only directory-initialization type functions should
 105  * use this then. Everything else wants ocfs2_supports_dir_trailer()
 106  */
 107 static int ocfs2_new_dir_wants_trailer(struct inode *dir)
 108 {
 109         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
 110
 111         return ocfs2_meta_ecc(osb) ||
 112                 ocfs2_supports_indexed_dirs(osb);
 113 }
 114
 115 static inline unsigned int ocfs2_dir_trailer_blk_off(struct super_block *sb)
 116 {
 117         return sb->s_blocksize - sizeof(struct ocfs2_dir_block_trailer);
 118 }
 119
 120 #define ocfs2_trailer_from_bh(_bh, _sb) ((struct ocfs2_dir_block_trailer *) ((_bh)->b_data + ocfs2_dir_trailer_blk_off((_sb))))
 121
 122 /* XXX ocfs2_block_dqtrailer() is similar but not quite - can we make
 123  * them more consistent? */
 124 struct ocfs2_dir_block_trailer *ocfs2_dir_trailer_from_size(int blocksize,
 125                                                             void *data)
 126 {
 127         char *p = data;
 128
 129         p += blocksize - sizeof(struct ocfs2_dir_block_trailer);
 130         return (struct ocfs2_dir_block_trailer *)p;
 131 }
 132
 133 /*
 134  * XXX: This is executed once on every dirent. We should consider optimizing
 135  * it.
 136  */
 137 static int ocfs2_skip_dir_trailer(struct inode *dir,
 138                                   struct ocfs2_dir_entry *de,
 139                                   unsigned long offset,
 140                                   unsigned long blklen)
 141 {
 142         unsigned long toff = blklen - sizeof(struct ocfs2_dir_block_trailer);
 143
 144         if (!ocfs2_supports_dir_trailer(dir))
 145                 return 0;
 146
 147         if (offset != toff)
 148                 return 0;
 149
 150         return 1;
 151 }
 152
 153 static void ocfs2_init_dir_trailer(struct inode *inode,
 154                                    struct buffer_head *bh, u16 rec_len)
 155 {
 156         struct ocfs2_dir_block_trailer *trailer;
 157
 158         trailer = ocfs2_trailer_from_bh(bh, inode->i_sb);
 159         strcpy(trailer->db_signature, OCFS2_DIR_TRAILER_SIGNATURE);
 160         trailer->db_compat_rec_len =
 161                         cpu_to_le16(sizeof(struct ocfs2_dir_block_trailer));
 162         trailer->db_parent_dinode = cpu_to_le64(OCFS2_I(inode)->ip_blkno);
 163         trailer->db_blkno = cpu_to_le64(bh->b_blocknr);
 164         trailer->db_free_rec_len = cpu_to_le16(rec_len);
 165 }
 166 /*
 167  * Link an unindexed block with a dir trailer structure into the index free
 168  * list. This function will modify dirdata_bh, but assumes you've already
 169  * passed it to the journal.
 170  */
 171 static int ocfs2_dx_dir_link_trailer(struct inode *dir, handle_t *handle,
 172                                      struct buffer_head *dx_root_bh,
 173                                      struct buffer_head *dirdata_bh)
 174 {
 175         int ret;
 176         struct ocfs2_dx_root_block *dx_root;
 177         struct ocfs2_dir_block_trailer *trailer;
 178
 179         ret = ocfs2_journal_access_dr(handle, INODE_CACHE(dir), dx_root_bh,
 180                                       OCFS2_JOURNAL_ACCESS_WRITE);
 181         if (ret) {
 182                 mlog_errno(ret);
 183                 goto out;
 184         }
 185         trailer = ocfs2_trailer_from_bh(dirdata_bh, dir->i_sb);
 186         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
 187
 188         trailer->db_free_next = dx_root->dr_free_blk;
 189         dx_root->dr_free_blk = cpu_to_le64(dirdata_bh->b_blocknr);
 190
 191         ocfs2_journal_dirty(handle, dx_root_bh);
 192
 193 out:
 194         return ret;
 195 }
 196
 197 static int ocfs2_free_list_at_root(struct ocfs2_dir_lookup_result *res)
 198 {
 199         return res->dl_prev_leaf_bh == NULL;
 200 }
 201
 202 void ocfs2_free_dir_lookup_result(struct ocfs2_dir_lookup_result *res)
 203 {
 204         brelse(res->dl_dx_root_bh);
 205         brelse(res->dl_leaf_bh);
 206         brelse(res->dl_dx_leaf_bh);
 207         brelse(res->dl_prev_leaf_bh);
 208 }
 209
 210 static int ocfs2_dir_indexed(struct inode *inode)
 211 {
 212         if (OCFS2_I(inode)->ip_dyn_features & OCFS2_INDEXED_DIR_FL)
 213                 return 1;
 214         return 0;
 215 }
 216
 217 static inline int ocfs2_dx_root_inline(struct ocfs2_dx_root_block *dx_root)
 218 {
 219         return dx_root->dr_flags & OCFS2_DX_FLAG_INLINE;
 220 }
 221
 222 /*
 223  * Hashing code adapted from ext3
 224  */
 225 #define DELTA 0x9E3779B9
 226
 227 static void TEA_transform(__u32 buf[4], __u32 const in[])
 228 {
 229         __u32   sum = 0;
 230         __u32   b0 = buf[0], b1 = buf[1];
 231         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
 232         int     n = 16;
 233
 234         do {
 235                 sum += DELTA;
 236                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
 237                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
 238         } while (--n);
 239
 240         buf[0] += b0;
 241         buf[1] += b1;
 242 }
 243
 244 static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
 245 {
 246         __u32   pad, val;
 247         int     i;
 248
 249         pad = (__u32)len | ((__u32)len << 8);
 250         pad |= pad << 16;
 251
 252         val = pad;
 253         if (len > num*4)
 254                 len = num * 4;
 255         for (i = 0; i < len; i++) {
 256                 if ((i % 4) == 0)
 257                         val = pad;
 258                 val = msg[i] + (val << 8);
 259                 if ((i % 4) == 3) {
 260                         *buf++ = val;
 261                         val = pad;
 262                         num--;
 263                 }
 264         }
 265         if (--num >= 0)
 266                 *buf++ = val;
 267         while (--num >= 0)
 268                 *buf++ = pad;
 269 }
 270
 271 static void ocfs2_dx_dir_name_hash(struct inode *dir, const char *name, int len,
 272                                    struct ocfs2_dx_hinfo *hinfo)
 273 {
 274         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
 275         const char      *p;
 276         __u32           in[8], buf[4];
 277
 278         /*
 279          * XXX: Is this really necessary, if the index is never looked
 280          * at by readdir? Is a hash value of '0' a bad idea?
 281          */
 282         if ((len == 1 && !strncmp(".", name, 1)) ||
 283             (len == 2 && !strncmp("..", name, 2))) {
 284                 buf[0] = buf[1] = 0;
 285                 goto out;
 286         }
 287
 288 #ifdef OCFS2_DEBUG_DX_DIRS
 289         /*
 290          * This makes it very easy to debug indexing problems. We
 291          * should never allow this to be selected without hand editing
 292          * this file though.
 293          */
 294         buf[0] = buf[1] = len;
 295         goto out;
 296 #endif
 297
 298         memcpy(buf, osb->osb_dx_seed, sizeof(buf));
 299
 300         p = name;
 301         while (len > 0) {
 302                 str2hashbuf(p, len, in, 4);
 303                 TEA_transform(buf, in);
 304                 len -= 16;
 305                 p += 16;
 306         }
 307
 308 out:
 309         hinfo->major_hash = buf[0];
 310         hinfo->minor_hash = buf[1];
 311 }
 312
 313 /*
 314  * bh passed here can be an inode block or a dir data block, depending
 315  * on the inode inline data flag.
 316  */
 317 static int ocfs2_check_dir_entry(struct inode * dir,
 318                                  struct ocfs2_dir_entry * de,
 319                                  struct buffer_head * bh,
 320                                  unsigned long offset)
 321 {
 322         const char *error_msg = NULL;
 323         const int rlen = le16_to_cpu(de->rec_len);
 324
 325         if (unlikely(rlen < OCFS2_DIR_REC_LEN(1)))
 326                 error_msg = "rec_len is smaller than minimal";
 327         else if (unlikely(rlen % 4 != 0))
 328                 error_msg = "rec_len % 4 != 0";
 329         else if (unlikely(rlen < OCFS2_DIR_REC_LEN(de->name_len)))
 330                 error_msg = "rec_len is too small for name_len";
 331         else if (unlikely(
 332                  ((char *) de - bh->b_data) + rlen > dir->i_sb->s_blocksize))
 333                 error_msg = "directory entry across blocks";
 334
 335         if (unlikely(error_msg != NULL))
 336                 mlog(ML_ERROR, "bad entry in directory #%llu: %s - "
 337                      "offset=%lu, inode=%llu, rec_len=%d, name_len=%d\n",
 338                      (unsigned long long)OCFS2_I(dir)->ip_blkno, error_msg,
 339                      offset, (unsigned long long)le64_to_cpu(de->inode), rlen,
 340                      de->name_len);
 341
 342         return error_msg == NULL ? 1 : 0;
 343 }
 344
 345 static inline int ocfs2_match(int len,
 346                               const char * const name,
 347                               struct ocfs2_dir_entry *de)
 348 {
 349         if (len != de->name_len)
 350                 return 0;
 351         if (!de->inode)
 352                 return 0;
 353         return !memcmp(name, de->name, len);
 354 }
 355
 356 /*
 357  * Returns 0 if not found, -1 on failure, and 1 on success
 358  */
 359 static inline int ocfs2_search_dirblock(struct buffer_head *bh,
 360                                         struct inode *dir,
 361                                         const char *name, int namelen,
 362                                         unsigned long offset,
 363                                         char *first_de,
 364                                         unsigned int bytes,
 365                                         struct ocfs2_dir_entry **res_dir)
 366 {
 367         struct ocfs2_dir_entry *de;
 368         char *dlimit, *de_buf;
 369         int de_len;
 370         int ret = 0;
 371
 372         de_buf = first_de;
 373         dlimit = de_buf + bytes;
 374
 375         while (de_buf < dlimit) {
 376                 /* this code is executed quadratically often */
 377                 /* do minimal checking `by hand' */
 378
 379                 de = (struct ocfs2_dir_entry *) de_buf;
 380
 381                 if (de_buf + namelen <= dlimit &&
 382                     ocfs2_match(namelen, name, de)) {
 383                         /* found a match - just to be sure, do a full check */
 384                         if (!ocfs2_check_dir_entry(dir, de, bh, offset)) {
 385                                 ret = -1;
 386                                 goto bail;
 387                         }
 388                         *res_dir = de;
 389                         ret = 1;
 390                         goto bail;
 391                 }
 392
 393                 /* prevent looping on a bad block */
 394                 de_len = le16_to_cpu(de->rec_len);
 395                 if (de_len <= 0) {
 396                         ret = -1;
 397                         goto bail;
 398                 }
 399
 400                 de_buf += de_len;
 401                 offset += de_len;
 402         }
 403
 404 bail:
 405         trace_ocfs2_search_dirblock(ret);
 406         return ret;
 407 }
 408
 409 static struct buffer_head *ocfs2_find_entry_id(const char *name,
 410                                                int namelen,
 411                                                struct inode *dir,
 412                                                struct ocfs2_dir_entry **res_dir)
 413 {
 414         int ret, found;
 415         struct buffer_head *di_bh = NULL;
 416         struct ocfs2_dinode *di;
 417         struct ocfs2_inline_data *data;
 418
 419         ret = ocfs2_read_inode_block(dir, &di_bh);
 420         if (ret) {
 421                 mlog_errno(ret);
 422                 goto out;
 423         }
 424
 425         di = (struct ocfs2_dinode *)di_bh->b_data;
 426         data = &di->id2.i_data;
 427
 428         found = ocfs2_search_dirblock(di_bh, dir, name, namelen, 0,
 429                                       data->id_data, i_size_read(dir), res_dir);
 430         if (found == 1)
 431                 return di_bh;
 432
 433         brelse(di_bh);
 434 out:
 435         return NULL;
 436 }
 437
 438 static int ocfs2_validate_dir_block(struct super_block *sb,
 439                                     struct buffer_head *bh)
 440 {
 441         int rc;
 442         struct ocfs2_dir_block_trailer *trailer =
 443                 ocfs2_trailer_from_bh(bh, sb);
 444
 445
 446         /*
 447          * We don't validate dirents here, that's handled
 448          * in-place when the code walks them.
 449          */
 450         trace_ocfs2_validate_dir_block((unsigned long long)bh->b_blocknr);
 451
 452         BUG_ON(!buffer_uptodate(bh));
 453
 454         /*
 455          * If the ecc fails, we return the error but otherwise
 456          * leave the filesystem running.  We know any error is
 457          * local to this block.
 458          *
 459          * Note that we are safe to call this even if the directory
 460          * doesn't have a trailer.  Filesystems without metaecc will do
 461          * nothing, and filesystems with it will have one.
 462          */
 463         rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &trailer->db_check);
 464         if (rc)
 465                 mlog(ML_ERROR, "Checksum failed for dinode %llu\n",
 466                      (unsigned long long)bh->b_blocknr);
 467
 468         return rc;
 469 }
 470
 471 /*
 472  * Validate a directory trailer.
 473  *
 474  * We check the trailer here rather than in ocfs2_validate_dir_block()
 475  * because that function doesn't have the inode to test.
 476  */
 477 static int ocfs2_check_dir_trailer(struct inode *dir, struct buffer_head *bh)
 478 {
 479         int rc = 0;
 480         struct ocfs2_dir_block_trailer *trailer;
 481
 482         trailer = ocfs2_trailer_from_bh(bh, dir->i_sb);
 483         if (!OCFS2_IS_VALID_DIR_TRAILER(trailer)) {
 484                 rc = ocfs2_error(dir->i_sb,
 485                                  "Invalid dirblock #%llu: signature = %.*s\n",
 486                                  (unsigned long long)bh->b_blocknr, 7,
 487                                  trailer->db_signature);
 488                 goto out;
 489         }
 490         if (le64_to_cpu(trailer->db_blkno) != bh->b_blocknr) {
 491                 rc = ocfs2_error(dir->i_sb,
 492                                  "Directory block #%llu has an invalid db_blkno of %llu\n",
 493                                  (unsigned long long)bh->b_blocknr,
 494                                  (unsigned long long)le64_to_cpu(trailer->db_blkno));
 495                 goto out;
 496         }
 497         if (le64_to_cpu(trailer->db_parent_dinode) !=
 498             OCFS2_I(dir)->ip_blkno) {
 499                 rc = ocfs2_error(dir->i_sb,
 500                                  "Directory block #%llu on dinode #%llu has an invalid parent_dinode of %llu\n",
 501                                  (unsigned long long)bh->b_blocknr,
 502                                  (unsigned long long)OCFS2_I(dir)->ip_blkno,
 503                                  (unsigned long long)le64_to_cpu(trailer->db_blkno));
 504                 goto out;
 505         }
 506 out:
 507         return rc;
 508 }
 509
 510 /*
 511  * This function forces all errors to -EIO for consistency with its
 512  * predecessor, ocfs2_bread().  We haven't audited what returning the
 513  * real error codes would do to callers.  We log the real codes with
 514  * mlog_errno() before we squash them.
 515  */
 516 static int ocfs2_read_dir_block(struct inode *inode, u64 v_block,
 517                                 struct buffer_head **bh, int flags)
 518 {
 519         int rc = 0;
 520         struct buffer_head *tmp = *bh;
 521
 522         rc = ocfs2_read_virt_blocks(inode, v_block, 1, &tmp, flags,
 523                                     ocfs2_validate_dir_block);
 524         if (rc) {
 525                 mlog_errno(rc);
 526                 goto out;
 527         }
 528
 529         if (!(flags & OCFS2_BH_READAHEAD) &&
 530             ocfs2_supports_dir_trailer(inode)) {
 531                 rc = ocfs2_check_dir_trailer(inode, tmp);
 532                 if (rc) {
 533                         if (!*bh)
 534                                 brelse(tmp);
 535                         mlog_errno(rc);
 536                         goto out;
 537                 }
 538         }
 539
 540         /* If ocfs2_read_virt_blocks() got us a new bh, pass it up. */
 541         if (!*bh)
 542                 *bh = tmp;
 543
 544 out:
 545         return rc ? -EIO : 0;
 546 }
 547
 548 /*
 549  * Read the block at 'phys' which belongs to this directory
 550  * inode. This function does no virtual->physical block translation -
 551  * what's passed in is assumed to be a valid directory block.
 552  */
 553 static int ocfs2_read_dir_block_direct(struct inode *dir, u64 phys,
 554                                        struct buffer_head **bh)
 555 {
 556         int ret;
 557         struct buffer_head *tmp = *bh;
 558
 559         ret = ocfs2_read_block(INODE_CACHE(dir), phys, &tmp,
 560                                ocfs2_validate_dir_block);
 561         if (ret) {
 562                 mlog_errno(ret);
 563                 goto out;
 564         }
 565
 566         if (ocfs2_supports_dir_trailer(dir)) {
 567                 ret = ocfs2_check_dir_trailer(dir, tmp);
 568                 if (ret) {
 569                         if (!*bh)
 570                                 brelse(tmp);
 571                         mlog_errno(ret);
 572                         goto out;
 573                 }
 574         }
 575
 576         if (!ret && !*bh)
 577                 *bh = tmp;
 578 out:
 579         return ret;
 580 }
 581
 582 static int ocfs2_validate_dx_root(struct super_block *sb,
 583                                   struct buffer_head *bh)
 584 {
 585         int ret;
 586         struct ocfs2_dx_root_block *dx_root;
 587
 588         BUG_ON(!buffer_uptodate(bh));
 589
 590         dx_root = (struct ocfs2_dx_root_block *) bh->b_data;
 591
 592         ret = ocfs2_validate_meta_ecc(sb, bh->b_data, &dx_root->dr_check);
 593         if (ret) {
 594                 mlog(ML_ERROR,
 595                      "Checksum failed for dir index root block %llu\n",
 596                      (unsigned long long)bh->b_blocknr);
 597                 return ret;
 598         }
 599
 600         if (!OCFS2_IS_VALID_DX_ROOT(dx_root)) {
 601                 ret = ocfs2_error(sb,
 602                                   "Dir Index Root # %llu has bad signature %.*s\n",
 603                                   (unsigned long long)le64_to_cpu(dx_root->dr_blkno),
 604                                   7, dx_root->dr_signature);
 605         }
 606
 607         return ret;
 608 }
 609
 610 static int ocfs2_read_dx_root(struct inode *dir, struct ocfs2_dinode *di,
 611                               struct buffer_head **dx_root_bh)
 612 {
 613         int ret;
 614         u64 blkno = le64_to_cpu(di->i_dx_root);
 615         struct buffer_head *tmp = *dx_root_bh;
 616
 617         ret = ocfs2_read_block(INODE_CACHE(dir), blkno, &tmp,
 618                                ocfs2_validate_dx_root);
 619
 620         /* If ocfs2_read_block() got us a new bh, pass it up. */
 621         if (!ret && !*dx_root_bh)
 622                 *dx_root_bh = tmp;
 623
 624         return ret;
 625 }
 626
 627 static int ocfs2_validate_dx_leaf(struct super_block *sb,
 628                                   struct buffer_head *bh)
 629 {
 630         int ret;
 631         struct ocfs2_dx_leaf *dx_leaf = (struct ocfs2_dx_leaf *)bh->b_data;
 632
 633         BUG_ON(!buffer_uptodate(bh));
 634
 635         ret = ocfs2_validate_meta_ecc(sb, bh->b_data, &dx_leaf->dl_check);
 636         if (ret) {
 637                 mlog(ML_ERROR,
 638                      "Checksum failed for dir index leaf block %llu\n",
 639                      (unsigned long long)bh->b_blocknr);
 640                 return ret;
 641         }
 642
 643         if (!OCFS2_IS_VALID_DX_LEAF(dx_leaf)) {
 644                 ret = ocfs2_error(sb, "Dir Index Leaf has bad signature %.*s\n",
 645                                   7, dx_leaf->dl_signature);
 646         }
 647
 648         return ret;
 649 }
 650
 651 static int ocfs2_read_dx_leaf(struct inode *dir, u64 blkno,
 652                               struct buffer_head **dx_leaf_bh)
 653 {
 654         int ret;
 655         struct buffer_head *tmp = *dx_leaf_bh;
 656
 657         ret = ocfs2_read_block(INODE_CACHE(dir), blkno, &tmp,
 658                                ocfs2_validate_dx_leaf);
 659
 660         /* If ocfs2_read_block() got us a new bh, pass it up. */
 661         if (!ret && !*dx_leaf_bh)
 662                 *dx_leaf_bh = tmp;
 663
 664         return ret;
 665 }
 666
 667 /*
 668  * Read a series of dx_leaf blocks. This expects all buffer_head
 669  * pointers to be NULL on function entry.
 670  */
 671 static int ocfs2_read_dx_leaves(struct inode *dir, u64 start, int num,
 672                                 struct buffer_head **dx_leaf_bhs)
 673 {
 674         int ret;
 675
 676         ret = ocfs2_read_blocks(INODE_CACHE(dir), start, num, dx_leaf_bhs, 0,
 677                                 ocfs2_validate_dx_leaf);
 678         if (ret)
 679                 mlog_errno(ret);
 680
 681         return ret;
 682 }
 683
 684 static struct buffer_head *ocfs2_find_entry_el(const char *name, int namelen,
 685                                                struct inode *dir,
 686                                                struct ocfs2_dir_entry **res_dir)
 687 {
 688         struct super_block *sb;
 689         struct buffer_head *bh_use[NAMEI_RA_SIZE];
 690         struct buffer_head *bh, *ret = NULL;
 691         unsigned long start, block, b;
 692         int ra_max = 0;         /* Number of bh's in the readahead
 693                                    buffer, bh_use[] */
 694         int ra_ptr = 0;         /* Current index into readahead
 695                                    buffer */
 696         int num = 0;
 697         int nblocks, i, err;
 698
 699         sb = dir->i_sb;
 700
 701         nblocks = i_size_read(dir) >> sb->s_blocksize_bits;
 702         start = OCFS2_I(dir)->ip_dir_start_lookup;
 703         if (start >= nblocks)
 704                 start = 0;
 705         block = start;
 706
 707 restart:
 708         do {
 709                 /*
 710                  * We deal with the read-ahead logic here.
 711                  */
 712                 if (ra_ptr >= ra_max) {
 713                         /* Refill the readahead buffer */
 714                         ra_ptr = 0;
 715                         b = block;
 716                         for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
 717                                 /*
 718                                  * Terminate if we reach the end of the
 719                                  * directory and must wrap, or if our
 720                                  * search has finished at this block.
 721                                  */
 722                                 if (b >= nblocks || (num && block == start)) {
 723                                         bh_use[ra_max] = NULL;
 724                                         break;
 725                                 }
 726                                 num++;
 727
 728                                 bh = NULL;
 729                                 err = ocfs2_read_dir_block(dir, b++, &bh,
 730                                                            OCFS2_BH_READAHEAD);
 731                                 bh_use[ra_max] = bh;
 732                         }
 733                 }
 734                 if ((bh = bh_use[ra_ptr++]) == NULL)
 735                         goto next;
 736                 if (ocfs2_read_dir_block(dir, block, &bh, 0)) {
 737                         /* read error, skip block & hope for the best.
 738                          * ocfs2_read_dir_block() has released the bh. */
 739                         mlog(ML_ERROR, "reading directory %llu, "
 740                                     "offset %lu\n",
 741                                     (unsigned long long)OCFS2_I(dir)->ip_blkno,
 742                                     block);
 743                         goto next;
 744                 }
 745                 i = ocfs2_search_dirblock(bh, dir, name, namelen,
 746                                           block << sb->s_blocksize_bits,
 747                                           bh->b_data, sb->s_blocksize,
 748                                           res_dir);
 749                 if (i == 1) {
 750                         OCFS2_I(dir)->ip_dir_start_lookup = block;
 751                         ret = bh;
 752                         goto cleanup_and_exit;
 753                 } else {
 754                         brelse(bh);
 755                         if (i < 0)
 756                                 goto cleanup_and_exit;
 757                 }
 758         next:
 759                 if (++block >= nblocks)
 760                         block = 0;
 761         } while (block != start);
 762
 763         /*
 764          * If the directory has grown while we were searching, then
 765          * search the last part of the directory before giving up.
 766          */
 767         block = nblocks;
 768         nblocks = i_size_read(dir) >> sb->s_blocksize_bits;
 769         if (block < nblocks) {
 770                 start = 0;
 771                 goto restart;
 772         }
 773
 774 cleanup_and_exit:
 775         /* Clean up the read-ahead blocks */
 776         for (; ra_ptr < ra_max; ra_ptr++)
 777                 brelse(bh_use[ra_ptr]);
 778
 779         trace_ocfs2_find_entry_el(ret);
 780         return ret;
 781 }
 782
 783 static int ocfs2_dx_dir_lookup_rec(struct inode *inode,
 784                                    struct ocfs2_extent_list *el,
 785                                    u32 major_hash,
 786                                    u32 *ret_cpos,
 787                                    u64 *ret_phys_blkno,
 788                                    unsigned int *ret_clen)
 789 {
 790         int ret = 0, i, found;
 791         struct buffer_head *eb_bh = NULL;
 792         struct ocfs2_extent_block *eb;
 793         struct ocfs2_extent_rec *rec = NULL;
 794
 795         if (el->l_tree_depth) {
 796                 ret = ocfs2_find_leaf(INODE_CACHE(inode), el, major_hash,
 797                                       &eb_bh);
 798                 if (ret) {
 799                         mlog_errno(ret);
 800                         goto out;
 801                 }
 802
 803                 eb = (struct ocfs2_extent_block *) eb_bh->b_data;
 804                 el = &eb->h_list;
 805
 806                 if (el->l_tree_depth) {
 807                         ret = ocfs2_error(inode->i_sb,
 808                                           "Inode %lu has non zero tree depth in btree tree block %llu\n",
 809                                           inode->i_ino,
 810                                           (unsigned long long)eb_bh->b_blocknr);
 811                         goto out;
 812                 }
 813         }
 814
 815         found = 0;
 816         for (i = le16_to_cpu(el->l_next_free_rec) - 1; i >= 0; i--) {
 817                 rec = &el->l_recs[i];
 818
 819                 if (le32_to_cpu(rec->e_cpos) <= major_hash) {
 820                         found = 1;
 821                         break;
 822                 }
 823         }
 824
 825         if (!found) {
 826                 ret = ocfs2_error(inode->i_sb,
 827                                   "Inode %lu has bad extent record (%u, %u, 0) in btree\n",
 828                                   inode->i_ino,
 829                                   le32_to_cpu(rec->e_cpos),
 830                                   ocfs2_rec_clusters(el, rec));
 831                 goto out;
 832         }
 833
 834         if (ret_phys_blkno)
 835                 *ret_phys_blkno = le64_to_cpu(rec->e_blkno);
 836         if (ret_cpos)
 837                 *ret_cpos = le32_to_cpu(rec->e_cpos);
 838         if (ret_clen)
 839                 *ret_clen = le16_to_cpu(rec->e_leaf_clusters);
 840
 841 out:
 842         brelse(eb_bh);
 843         return ret;
 844 }
 845
 846 /*
 847  * Returns the block index, from the start of the cluster which this
 848  * hash belongs too.
 849  */
 850 static inline unsigned int __ocfs2_dx_dir_hash_idx(struct ocfs2_super *osb,
 851                                                    u32 minor_hash)
 852 {
 853         return minor_hash & osb->osb_dx_mask;
 854 }
 855
 856 static inline unsigned int ocfs2_dx_dir_hash_idx(struct ocfs2_super *osb,
 857                                           struct ocfs2_dx_hinfo *hinfo)
 858 {
 859         return __ocfs2_dx_dir_hash_idx(osb, hinfo->minor_hash);
 860 }
 861
 862 static int ocfs2_dx_dir_lookup(struct inode *inode,
 863                                struct ocfs2_extent_list *el,
 864                                struct ocfs2_dx_hinfo *hinfo,
 865                                u32 *ret_cpos,
 866                                u64 *ret_phys_blkno)
 867 {
 868         int ret = 0;
 869         unsigned int cend, uninitialized_var(clen);
 870         u32 uninitialized_var(cpos);
 871         u64 uninitialized_var(blkno);
 872         u32 name_hash = hinfo->major_hash;
 873
 874         ret = ocfs2_dx_dir_lookup_rec(inode, el, name_hash, &cpos, &blkno,
 875                                       &clen);
 876         if (ret) {
 877                 mlog_errno(ret);
 878                 goto out;
 879         }
 880
 881         cend = cpos + clen;
 882         if (name_hash >= cend) {
 883                 /* We want the last cluster */
 884                 blkno += ocfs2_clusters_to_blocks(inode->i_sb, clen - 1);
 885                 cpos += clen - 1;
 886         } else {
 887                 blkno += ocfs2_clusters_to_blocks(inode->i_sb,
 888                                                   name_hash - cpos);
 889                 cpos = name_hash;
 890         }
 891
 892         /*
 893          * We now have the cluster which should hold our entry. To
 894          * find the exact block from the start of the cluster to
 895          * search, we take the lower bits of the hash.
 896          */
 897         blkno += ocfs2_dx_dir_hash_idx(OCFS2_SB(inode->i_sb), hinfo);
 898
 899         if (ret_phys_blkno)
 900                 *ret_phys_blkno = blkno;
 901         if (ret_cpos)
 902                 *ret_cpos = cpos;
 903
 904 out:
 905
 906         return ret;
 907 }
 908
 909 static int ocfs2_dx_dir_search(const char *name, int namelen,
 910                                struct inode *dir,
 911                                struct ocfs2_dx_root_block *dx_root,
 912                                struct ocfs2_dir_lookup_result *res)
 913 {
 914         int ret, i, found;
 915         u64 uninitialized_var(phys);
 916         struct buffer_head *dx_leaf_bh = NULL;
 917         struct ocfs2_dx_leaf *dx_leaf;
 918         struct ocfs2_dx_entry *dx_entry = NULL;
 919         struct buffer_head *dir_ent_bh = NULL;
 920         struct ocfs2_dir_entry *dir_ent = NULL;
 921         struct ocfs2_dx_hinfo *hinfo = &res->dl_hinfo;
 922         struct ocfs2_extent_list *dr_el;
 923         struct ocfs2_dx_entry_list *entry_list;
 924
 925         ocfs2_dx_dir_name_hash(dir, name, namelen, &res->dl_hinfo);
 926
 927         if (ocfs2_dx_root_inline(dx_root)) {
 928                 entry_list = &dx_root->dr_entries;
 929                 goto search;
 930         }
 931
 932         dr_el = &dx_root->dr_list;
 933
 934         ret = ocfs2_dx_dir_lookup(dir, dr_el, hinfo, NULL, &phys);
 935         if (ret) {
 936                 mlog_errno(ret);
 937                 goto out;
 938         }
 939
 940         trace_ocfs2_dx_dir_search((unsigned long long)OCFS2_I(dir)->ip_blkno,
 941                                   namelen, name, hinfo->major_hash,
 942                                   hinfo->minor_hash, (unsigned long long)phys);
 943
 944         ret = ocfs2_read_dx_leaf(dir, phys, &dx_leaf_bh);
 945         if (ret) {
 946                 mlog_errno(ret);
 947                 goto out;
 948         }
 949
 950         dx_leaf = (struct ocfs2_dx_leaf *) dx_leaf_bh->b_data;
 951
 952         trace_ocfs2_dx_dir_search_leaf_info(
 953                         le16_to_cpu(dx_leaf->dl_list.de_num_used),
 954                         le16_to_cpu(dx_leaf->dl_list.de_count));
 955
 956         entry_list = &dx_leaf->dl_list;
 957
 958 search:
 959         /*
 960          * Empty leaf is legal, so no need to check for that.
 961          */
 962         found = 0;
 963         for (i = 0; i < le16_to_cpu(entry_list->de_num_used); i++) {
 964                 dx_entry = &entry_list->de_entries[i];
 965
 966                 if (hinfo->major_hash != le32_to_cpu(dx_entry->dx_major_hash)
 967                     || hinfo->minor_hash != le32_to_cpu(dx_entry->dx_minor_hash))
 968                         continue;
 969
 970                 /*
 971                  * Search unindexed leaf block now. We're not
 972                  * guaranteed to find anything.
 973                  */
 974                 ret = ocfs2_read_dir_block_direct(dir,
 975                                           le64_to_cpu(dx_entry->dx_dirent_blk),
 976                                           &dir_ent_bh);
 977                 if (ret) {
 978                         mlog_errno(ret);
 979                         goto out;
 980                 }
 981
 982                 /*
 983                  * XXX: We should check the unindexed block here,
 984                  * before using it.
 985                  */
 986
 987                 found = ocfs2_search_dirblock(dir_ent_bh, dir, name, namelen,
 988                                               0, dir_ent_bh->b_data,
 989                                               dir->i_sb->s_blocksize, &dir_ent);
 990                 if (found == 1)
 991                         break;
 992
 993                 if (found == -1) {
 994                         /* This means we found a bad directory entry. */
 995                         ret = -EIO;
 996                         mlog_errno(ret);
 997                         goto out;
 998                 }
 999
1000                 brelse(dir_ent_bh);
1001                 dir_ent_bh = NULL;
1002         }
1003
1004         if (found <= 0) {
1005                 ret = -ENOENT;
1006                 goto out;
1007         }
1008
1009         res->dl_leaf_bh = dir_ent_bh;
1010         res->dl_entry = dir_ent;
1011         res->dl_dx_leaf_bh = dx_leaf_bh;
1012         res->dl_dx_entry = dx_entry;
1013
1014         ret = 0;
1015 out:
1016         if (ret) {
1017                 brelse(dx_leaf_bh);
1018                 brelse(dir_ent_bh);
1019         }
1020         return ret;
1021 }
1022
1023 static int ocfs2_find_entry_dx(const char *name, int namelen,
1024                                struct inode *dir,
1025                                struct ocfs2_dir_lookup_result *lookup)
1026 {
1027         int ret;
1028         struct buffer_head *di_bh = NULL;
1029         struct ocfs2_dinode *di;
1030         struct buffer_head *dx_root_bh = NULL;
1031         struct ocfs2_dx_root_block *dx_root;
1032
1033         ret = ocfs2_read_inode_block(dir, &di_bh);
1034         if (ret) {
1035                 mlog_errno(ret);
1036                 goto out;
1037         }
1038
1039         di = (struct ocfs2_dinode *)di_bh->b_data;
1040
1041         ret = ocfs2_read_dx_root(dir, di, &dx_root_bh);
1042         if (ret) {
1043                 mlog_errno(ret);
1044                 goto out;
1045         }
1046         dx_root = (struct ocfs2_dx_root_block *) dx_root_bh->b_data;
1047
1048         ret = ocfs2_dx_dir_search(name, namelen, dir, dx_root, lookup);
1049         if (ret) {
1050                 if (ret != -ENOENT)
1051                         mlog_errno(ret);
1052                 goto out;
1053         }
1054
1055         lookup->dl_dx_root_bh = dx_root_bh;
1056         dx_root_bh = NULL;
1057 out:
1058         brelse(di_bh);
1059         brelse(dx_root_bh);
1060         return ret;
1061 }
1062
1063 /*
1064  * Try to find an entry of the provided name within 'dir'.
1065  *
1066  * If nothing was found, -ENOENT is returned. Otherwise, zero is
1067  * returned and the struct 'res' will contain information useful to
1068  * other directory manipulation functions.
1069  *
1070  * Caller can NOT assume anything about the contents of the
1071  * buffer_heads - they are passed back only so that it can be passed
1072  * into any one of the manipulation functions (add entry, delete
1073  * entry, etc). As an example, bh in the extent directory case is a
1074  * data block, in the inline-data case it actually points to an inode,
1075  * in the indexed directory case, multiple buffers are involved.
1076  */
1077 int ocfs2_find_entry(const char *name, int namelen,
1078                      struct inode *dir, struct ocfs2_dir_lookup_result *lookup)
1079 {
1080         struct buffer_head *bh;
1081         struct ocfs2_dir_entry *res_dir = NULL;
1082
1083         if (ocfs2_dir_indexed(dir))
1084                 return ocfs2_find_entry_dx(name, namelen, dir, lookup);
1085
1086         /*
1087          * The unindexed dir code only uses part of the lookup
1088          * structure, so there's no reason to push it down further
1089          * than this.
1090          */
1091         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
1092                 bh = ocfs2_find_entry_id(name, namelen, dir, &res_dir);
1093         else
1094                 bh = ocfs2_find_entry_el(name, namelen, dir, &res_dir);
1095
1096         if (bh == NULL)
1097                 return -ENOENT;
1098
1099         lookup->dl_leaf_bh = bh;
1100         lookup->dl_entry = res_dir;
1101         return 0;
1102 }
1103
1104 /*
1105  * Update inode number and type of a previously found directory entry.
1106  */
1107 int ocfs2_update_entry(struct inode *dir, handle_t *handle,
1108                        struct ocfs2_dir_lookup_result *res,
1109                        struct inode *new_entry_inode)
1110 {
1111         int ret;
1112         ocfs2_journal_access_func access = ocfs2_journal_access_db;
1113         struct ocfs2_dir_entry *de = res->dl_entry;
1114         struct buffer_head *de_bh = res->dl_leaf_bh;
1115
1116         /*
1117          * The same code works fine for both inline-data and extent
1118          * based directories, so no need to split this up.  The only
1119          * difference is the journal_access function.
1120          */
1121
1122         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
1123                 access = ocfs2_journal_access_di;
1124
1125         ret = access(handle, INODE_CACHE(dir), de_bh,
1126                      OCFS2_JOURNAL_ACCESS_WRITE);
1127         if (ret) {
1128                 mlog_errno(ret);
1129                 goto out;
1130         }
1131
1132         de->inode = cpu_to_le64(OCFS2_I(new_entry_inode)->ip_blkno);
1133         ocfs2_set_de_type(de, new_entry_inode->i_mode);
1134
1135         ocfs2_journal_dirty(handle, de_bh);
1136
1137 out:
1138         return ret;
1139 }
1140
1141 /*
1142  * __ocfs2_delete_entry deletes a directory entry by merging it with the
1143  * previous entry
1144  */
1145 static int __ocfs2_delete_entry(handle_t *handle, struct inode *dir,
1146                                 struct ocfs2_dir_entry *de_del,
1147                                 struct buffer_head *bh, char *first_de,
1148                                 unsigned int bytes)
1149 {
1150         struct ocfs2_dir_entry *de, *pde;
1151         int i, status = -ENOENT;
1152         ocfs2_journal_access_func access = ocfs2_journal_access_db;
1153
1154         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
1155                 access = ocfs2_journal_access_di;
1156
1157         i = 0;
1158         pde = NULL;
1159         de = (struct ocfs2_dir_entry *) first_de;
1160         while (i < bytes) {
1161                 if (!ocfs2_check_dir_entry(dir, de, bh, i)) {
1162                         status = -EIO;
1163                         mlog_errno(status);
1164                         goto bail;
1165                 }
1166                 if (de == de_del)  {
1167                         status = access(handle, INODE_CACHE(dir), bh,
1168                                         OCFS2_JOURNAL_ACCESS_WRITE);
1169                         if (status < 0) {
1170                                 status = -EIO;
1171                                 mlog_errno(status);
1172                                 goto bail;
1173                         }
1174                         if (pde)
1175                                 le16_add_cpu(&pde->rec_len,
1176                                                 le16_to_cpu(de->rec_len));
1177                         de->inode = 0;
1178                         inode_inc_iversion(dir);
1179                         ocfs2_journal_dirty(handle, bh);
1180                         goto bail;
1181                 }
1182                 i += le16_to_cpu(de->rec_len);
1183                 pde = de;
1184                 de = (struct ocfs2_dir_entry *)((char *)de + le16_to_cpu(de->rec_len));
1185         }
1186 bail:
1187         return status;
1188 }
1189
1190 static unsigned int ocfs2_figure_dirent_hole(struct ocfs2_dir_entry *de)
1191 {
1192         unsigned int hole;
1193
1194         if (le64_to_cpu(de->inode) == 0)
1195                 hole = le16_to_cpu(de->rec_len);
1196         else
1197                 hole = le16_to_cpu(de->rec_len) -
1198                         OCFS2_DIR_REC_LEN(de->name_len);
1199
1200         return hole;
1201 }
1202
1203 static int ocfs2_find_max_rec_len(struct super_block *sb,
1204                                   struct buffer_head *dirblock_bh)
1205 {
1206         int size, this_hole, largest_hole = 0;
1207         char *trailer, *de_buf, *limit, *start = dirblock_bh->b_data;
1208         struct ocfs2_dir_entry *de;
1209
1210         trailer = (char *)ocfs2_trailer_from_bh(dirblock_bh, sb);
1211         size = ocfs2_dir_trailer_blk_off(sb);
1212         limit = start + size;
1213         de_buf = start;
1214         de = (struct ocfs2_dir_entry *)de_buf;
1215         do {
1216                 if (de_buf != trailer) {
1217                         this_hole = ocfs2_figure_dirent_hole(de);
1218                         if (this_hole > largest_hole)
1219                                 largest_hole = this_hole;
1220                 }
1221
1222                 de_buf += le16_to_cpu(de->rec_len);
1223                 de = (struct ocfs2_dir_entry *)de_buf;
1224         } while (de_buf < limit);
1225
1226         if (largest_hole >= OCFS2_DIR_MIN_REC_LEN)
1227                 return largest_hole;
1228         return 0;
1229 }
1230
1231 static void ocfs2_dx_list_remove_entry(struct ocfs2_dx_entry_list *entry_list,
1232                                        int index)
1233 {
1234         int num_used = le16_to_cpu(entry_list->de_num_used);
1235
1236         if (num_used == 1 || index == (num_used - 1))
1237                 goto clear;
1238
1239         memmove(&entry_list->de_entries[index],
1240                 &entry_list->de_entries[index + 1],
1241                 (num_used - index - 1)*sizeof(struct ocfs2_dx_entry));
1242 clear:
1243         num_used--;
1244         memset(&entry_list->de_entries[num_used], 0,
1245                sizeof(struct ocfs2_dx_entry));
1246         entry_list->de_num_used = cpu_to_le16(num_used);
1247 }
1248
1249 static int ocfs2_delete_entry_dx(handle_t *handle, struct inode *dir,
1250                                  struct ocfs2_dir_lookup_result *lookup)
1251 {
1252         int ret, index, max_rec_len, add_to_free_list = 0;
1253         struct buffer_head *dx_root_bh = lookup->dl_dx_root_bh;
1254         struct buffer_head *leaf_bh = lookup->dl_leaf_bh;
1255         struct ocfs2_dx_leaf *dx_leaf;
1256         struct ocfs2_dx_entry *dx_entry = lookup->dl_dx_entry;
1257         struct ocfs2_dir_block_trailer *trailer;
1258         struct ocfs2_dx_root_block *dx_root;
1259         struct ocfs2_dx_entry_list *entry_list;
1260
1261         /*
1262          * This function gets a bit messy because we might have to
1263          * modify the root block, regardless of whether the indexed
1264          * entries are stored inline.
1265          */
1266
1267         /*
1268          * *Only* set 'entry_list' here, based on where we're looking
1269          * for the indexed entries. Later, we might still want to
1270          * journal both blocks, based on free list state.
1271          */
1272         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
1273         if (ocfs2_dx_root_inline(dx_root)) {
1274                 entry_list = &dx_root->dr_entries;
1275         } else {
1276                 dx_leaf = (struct ocfs2_dx_leaf *) lookup->dl_dx_leaf_bh->b_data;
1277                 entry_list = &dx_leaf->dl_list;
1278         }
1279
1280         /* Neither of these are a disk corruption - that should have
1281          * been caught by lookup, before we got here. */
1282         BUG_ON(le16_to_cpu(entry_list->de_count) <= 0);
1283         BUG_ON(le16_to_cpu(entry_list->de_num_used) <= 0);
1284
1285         index = (char *)dx_entry - (char *)entry_list->de_entries;
1286         index /= sizeof(*dx_entry);
1287
1288         if (index >= le16_to_cpu(entry_list->de_num_used)) {
1289                 mlog(ML_ERROR, "Dir %llu: Bad dx_entry ptr idx %d, (%p, %p)\n",
1290                      (unsigned long long)OCFS2_I(dir)->ip_blkno, index,
1291                      entry_list, dx_entry);
1292                 return -EIO;
1293         }
1294
1295         /*
1296          * We know that removal of this dirent will leave enough room
1297          * for a new one, so add this block to the free list if it
1298          * isn't already there.
1299          */
1300         trailer = ocfs2_trailer_from_bh(leaf_bh, dir->i_sb);
1301         if (trailer->db_free_rec_len == 0)
1302                 add_to_free_list = 1;
1303
1304         /*
1305          * Add the block holding our index into the journal before
1306          * removing the unindexed entry. If we get an error return
1307          * from __ocfs2_delete_entry(), then it hasn't removed the
1308          * entry yet. Likewise, successful return means we *must*
1309          * remove the indexed entry.
1310          *
1311          * We're also careful to journal the root tree block here as
1312          * the entry count needs to be updated. Also, we might be
1313          * adding to the start of the free list.
1314          */
1315         ret = ocfs2_journal_access_dr(handle, INODE_CACHE(dir), dx_root_bh,
1316                                       OCFS2_JOURNAL_ACCESS_WRITE);
1317         if (ret) {
1318                 mlog_errno(ret);
1319                 goto out;
1320         }
1321
1322         if (!ocfs2_dx_root_inline(dx_root)) {
1323                 ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir),
1324                                               lookup->dl_dx_leaf_bh,
1325                                               OCFS2_JOURNAL_ACCESS_WRITE);
1326                 if (ret) {
1327                         mlog_errno(ret);
1328                         goto out;
1329                 }
1330         }
1331
1332         trace_ocfs2_delete_entry_dx((unsigned long long)OCFS2_I(dir)->ip_blkno,
1333                                     index);
1334
1335         ret = __ocfs2_delete_entry(handle, dir, lookup->dl_entry,
1336                                    leaf_bh, leaf_bh->b_data, leaf_bh->b_size);
1337         if (ret) {
1338                 mlog_errno(ret);
1339                 goto out;
1340         }
1341
1342         max_rec_len = ocfs2_find_max_rec_len(dir->i_sb, leaf_bh);
1343         trailer->db_free_rec_len = cpu_to_le16(max_rec_len);
1344         if (add_to_free_list) {
1345                 trailer->db_free_next = dx_root->dr_free_blk;
1346                 dx_root->dr_free_blk = cpu_to_le64(leaf_bh->b_blocknr);
1347                 ocfs2_journal_dirty(handle, dx_root_bh);
1348         }
1349
1350         /* leaf_bh was journal_accessed for us in __ocfs2_delete_entry */
1351         ocfs2_journal_dirty(handle, leaf_bh);
1352
1353         le32_add_cpu(&dx_root->dr_num_entries, -1);
1354         ocfs2_journal_dirty(handle, dx_root_bh);
1355
1356         ocfs2_dx_list_remove_entry(entry_list, index);
1357
1358         if (!ocfs2_dx_root_inline(dx_root))
1359                 ocfs2_journal_dirty(handle, lookup->dl_dx_leaf_bh);
1360
1361 out:
1362         return ret;
1363 }
1364
1365 static inline int ocfs2_delete_entry_id(handle_t *handle,
1366                                         struct inode *dir,
1367                                         struct ocfs2_dir_entry *de_del,
1368                                         struct buffer_head *bh)
1369 {
1370         int ret;
1371         struct buffer_head *di_bh = NULL;
1372         struct ocfs2_dinode *di;
1373         struct ocfs2_inline_data *data;
1374
1375         ret = ocfs2_read_inode_block(dir, &di_bh);
1376         if (ret) {
1377                 mlog_errno(ret);
1378                 goto out;
1379         }
1380
1381         di = (struct ocfs2_dinode *)di_bh->b_data;
1382         data = &di->id2.i_data;
1383
1384         ret = __ocfs2_delete_entry(handle, dir, de_del, bh, data->id_data,
1385                                    i_size_read(dir));
1386
1387         brelse(di_bh);
1388 out:
1389         return ret;
1390 }
1391
1392 static inline int ocfs2_delete_entry_el(handle_t *handle,
1393                                         struct inode *dir,
1394                                         struct ocfs2_dir_entry *de_del,
1395                                         struct buffer_head *bh)
1396 {
1397         return __ocfs2_delete_entry(handle, dir, de_del, bh, bh->b_data,
1398                                     bh->b_size);
1399 }
1400
1401 /*
1402  * Delete a directory entry. Hide the details of directory
1403  * implementation from the caller.
1404  */
1405 int ocfs2_delete_entry(handle_t *handle,
1406                        struct inode *dir,
1407                        struct ocfs2_dir_lookup_result *res)
1408 {
1409         if (ocfs2_dir_indexed(dir))
1410                 return ocfs2_delete_entry_dx(handle, dir, res);
1411
1412         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
1413                 return ocfs2_delete_entry_id(handle, dir, res->dl_entry,
1414                                              res->dl_leaf_bh);
1415
1416         return ocfs2_delete_entry_el(handle, dir, res->dl_entry,
1417                                      res->dl_leaf_bh);
1418 }
1419
1420 /*
1421  * Check whether 'de' has enough room to hold an entry of
1422  * 'new_rec_len' bytes.
1423  */
1424 static inline int ocfs2_dirent_would_fit(struct ocfs2_dir_entry *de,
1425                                          unsigned int new_rec_len)
1426 {
1427         unsigned int de_really_used;
1428
1429         /* Check whether this is an empty record with enough space */
1430         if (le64_to_cpu(de->inode) == 0 &&
1431             le16_to_cpu(de->rec_len) >= new_rec_len)
1432                 return 1;
1433
1434         /*
1435          * Record might have free space at the end which we can
1436          * use.
1437          */
1438         de_really_used = OCFS2_DIR_REC_LEN(de->name_len);
1439         if (le16_to_cpu(de->rec_len) >= (de_really_used + new_rec_len))
1440             return 1;
1441
1442         return 0;
1443 }
1444
1445 static void ocfs2_dx_dir_leaf_insert_tail(struct ocfs2_dx_leaf *dx_leaf,
1446                                           struct ocfs2_dx_entry *dx_new_entry)
1447 {
1448         int i;
1449
1450         i = le16_to_cpu(dx_leaf->dl_list.de_num_used);
1451         dx_leaf->dl_list.de_entries[i] = *dx_new_entry;
1452
1453         le16_add_cpu(&dx_leaf->dl_list.de_num_used, 1);
1454 }
1455
1456 static void ocfs2_dx_entry_list_insert(struct ocfs2_dx_entry_list *entry_list,
1457                                        struct ocfs2_dx_hinfo *hinfo,
1458                                        u64 dirent_blk)
1459 {
1460         int i;
1461         struct ocfs2_dx_entry *dx_entry;
1462
1463         i = le16_to_cpu(entry_list->de_num_used);
1464         dx_entry = &entry_list->de_entries[i];
1465
1466         memset(dx_entry, 0, sizeof(*dx_entry));
1467         dx_entry->dx_major_hash = cpu_to_le32(hinfo->major_hash);
1468         dx_entry->dx_minor_hash = cpu_to_le32(hinfo->minor_hash);
1469         dx_entry->dx_dirent_blk = cpu_to_le64(dirent_blk);
1470
1471         le16_add_cpu(&entry_list->de_num_used, 1);
1472 }
1473
1474 static int __ocfs2_dx_dir_leaf_insert(struct inode *dir, handle_t *handle,
1475                                       struct ocfs2_dx_hinfo *hinfo,
1476                                       u64 dirent_blk,
1477                                       struct buffer_head *dx_leaf_bh)
1478 {
1479         int ret;
1480         struct ocfs2_dx_leaf *dx_leaf;
1481
1482         ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir), dx_leaf_bh,
1483                                       OCFS2_JOURNAL_ACCESS_WRITE);
1484         if (ret) {
1485                 mlog_errno(ret);
1486                 goto out;
1487         }
1488
1489         dx_leaf = (struct ocfs2_dx_leaf *)dx_leaf_bh->b_data;
1490         ocfs2_dx_entry_list_insert(&dx_leaf->dl_list, hinfo, dirent_blk);
1491         ocfs2_journal_dirty(handle, dx_leaf_bh);
1492
1493 out:
1494         return ret;
1495 }
1496
1497 static void ocfs2_dx_inline_root_insert(struct inode *dir, handle_t *handle,
1498                                         struct ocfs2_dx_hinfo *hinfo,
1499                                         u64 dirent_blk,
1500                                         struct ocfs2_dx_root_block *dx_root)
1501 {
1502         ocfs2_dx_entry_list_insert(&dx_root->dr_entries, hinfo, dirent_blk);
1503 }
1504
1505 static int ocfs2_dx_dir_insert(struct inode *dir, handle_t *handle,
1506                                struct ocfs2_dir_lookup_result *lookup)
1507 {
1508         int ret = 0;
1509         struct ocfs2_dx_root_block *dx_root;
1510         struct buffer_head *dx_root_bh = lookup->dl_dx_root_bh;
1511
1512         ret = ocfs2_journal_access_dr(handle, INODE_CACHE(dir), dx_root_bh,
1513                                       OCFS2_JOURNAL_ACCESS_WRITE);
1514         if (ret) {
1515                 mlog_errno(ret);
1516                 goto out;
1517         }
1518
1519         dx_root = (struct ocfs2_dx_root_block *)lookup->dl_dx_root_bh->b_data;
1520         if (ocfs2_dx_root_inline(dx_root)) {
1521                 ocfs2_dx_inline_root_insert(dir, handle,
1522                                             &lookup->dl_hinfo,
1523                                             lookup->dl_leaf_bh->b_blocknr,
1524                                             dx_root);
1525         } else {
1526                 ret = __ocfs2_dx_dir_leaf_insert(dir, handle, &lookup->dl_hinfo,
1527                                                  lookup->dl_leaf_bh->b_blocknr,
1528                                                  lookup->dl_dx_leaf_bh);
1529                 if (ret)
1530                         goto out;
1531         }
1532
1533         le32_add_cpu(&dx_root->dr_num_entries, 1);
1534         ocfs2_journal_dirty(handle, dx_root_bh);
1535
1536 out:
1537         return ret;
1538 }
1539
1540 static void ocfs2_remove_block_from_free_list(struct inode *dir,
1541                                        handle_t *handle,
1542                                        struct ocfs2_dir_lookup_result *lookup)
1543 {
1544         struct ocfs2_dir_block_trailer *trailer, *prev;
1545         struct ocfs2_dx_root_block *dx_root;
1546         struct buffer_head *bh;
1547
1548         trailer = ocfs2_trailer_from_bh(lookup->dl_leaf_bh, dir->i_sb);
1549
1550         if (ocfs2_free_list_at_root(lookup)) {
1551                 bh = lookup->dl_dx_root_bh;
1552                 dx_root = (struct ocfs2_dx_root_block *)bh->b_data;
1553                 dx_root->dr_free_blk = trailer->db_free_next;
1554         } else {
1555                 bh = lookup->dl_prev_leaf_bh;
1556                 prev = ocfs2_trailer_from_bh(bh, dir->i_sb);
1557                 prev->db_free_next = trailer->db_free_next;
1558         }
1559
1560         trailer->db_free_rec_len = cpu_to_le16(0);
1561         trailer->db_free_next = cpu_to_le64(0);
1562
1563         ocfs2_journal_dirty(handle, bh);
1564         ocfs2_journal_dirty(handle, lookup->dl_leaf_bh);
1565 }
1566
1567 /*
1568  * This expects that a journal write has been reserved on
1569  * lookup->dl_prev_leaf_bh or lookup->dl_dx_root_bh
1570  */
1571 static void ocfs2_recalc_free_list(struct inode *dir, handle_t *handle,
1572                                    struct ocfs2_dir_lookup_result *lookup)
1573 {
1574         int max_rec_len;
1575         struct ocfs2_dir_block_trailer *trailer;
1576
1577         /* Walk dl_leaf_bh to figure out what the new free rec_len is. */
1578         max_rec_len = ocfs2_find_max_rec_len(dir->i_sb, lookup->dl_leaf_bh);
1579         if (max_rec_len) {
1580                 /*
1581                  * There's still room in this block, so no need to remove it
1582                  * from the free list. In this case, we just want to update
1583                  * the rec len accounting.
1584                  */
1585                 trailer = ocfs2_trailer_from_bh(lookup->dl_leaf_bh, dir->i_sb);
1586                 trailer->db_free_rec_len = cpu_to_le16(max_rec_len);
1587                 ocfs2_journal_dirty(handle, lookup->dl_leaf_bh);
1588         } else {
1589                 ocfs2_remove_block_from_free_list(dir, handle, lookup);
1590         }
1591 }
1592
1593 /* we don't always have a dentry for what we want to add, so people
1594  * like orphan dir can call this instead.
1595  *
1596  * The lookup context must have been filled from
1597  * ocfs2_prepare_dir_for_insert.
1598  */
1599 int __ocfs2_add_entry(handle_t *handle,
1600                       struct inode *dir,
1601                       const char *name, int namelen,
1602                       struct inode *inode, u64 blkno,
1603                       struct buffer_head *parent_fe_bh,
1604                       struct ocfs2_dir_lookup_result *lookup)
1605 {
1606         unsigned long offset;
1607         unsigned short rec_len;
1608         struct ocfs2_dir_entry *de, *de1;
1609         struct ocfs2_dinode *di = (struct ocfs2_dinode *)parent_fe_bh->b_data;
1610         struct super_block *sb = dir->i_sb;
1611         int retval;
1612         unsigned int size = sb->s_blocksize;
1613         struct buffer_head *insert_bh = lookup->dl_leaf_bh;
1614         char *data_start = insert_bh->b_data;
1615
1616         if (!namelen)
1617                 return -EINVAL;
1618
1619         if (ocfs2_dir_indexed(dir)) {
1620                 struct buffer_head *bh;
1621
1622                 /*
1623                  * An indexed dir may require that we update the free space
1624                  * list. Reserve a write to the previous node in the list so
1625                  * that we don't fail later.
1626                  *
1627                  * XXX: This can be either a dx_root_block, or an unindexed
1628                  * directory tree leaf block.
1629                  */
1630                 if (ocfs2_free_list_at_root(lookup)) {
1631                         bh = lookup->dl_dx_root_bh;
1632                         retval = ocfs2_journal_access_dr(handle,
1633                                                  INODE_CACHE(dir), bh,
1634                                                  OCFS2_JOURNAL_ACCESS_WRITE);
1635                 } else {
1636                         bh = lookup->dl_prev_leaf_bh;
1637                         retval = ocfs2_journal_access_db(handle,
1638                                                  INODE_CACHE(dir), bh,
1639                                                  OCFS2_JOURNAL_ACCESS_WRITE);
1640                 }
1641                 if (retval) {
1642                         mlog_errno(retval);
1643                         return retval;
1644                 }
1645         } else if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {
1646                 data_start = di->id2.i_data.id_data;
1647                 size = i_size_read(dir);
1648
1649                 BUG_ON(insert_bh != parent_fe_bh);
1650         }
1651
1652         rec_len = OCFS2_DIR_REC_LEN(namelen);
1653         offset = 0;
1654         de = (struct ocfs2_dir_entry *) data_start;
1655         while (1) {
1656                 BUG_ON((char *)de >= (size + data_start));
1657
1658                 /* These checks should've already been passed by the
1659                  * prepare function, but I guess we can leave them
1660                  * here anyway. */
1661                 if (!ocfs2_check_dir_entry(dir, de, insert_bh, offset)) {
1662                         retval = -ENOENT;
1663                         goto bail;
1664                 }
1665                 if (ocfs2_match(namelen, name, de)) {
1666                         retval = -EEXIST;
1667                         goto bail;
1668                 }
1669
1670                 /* We're guaranteed that we should have space, so we
1671                  * can't possibly have hit the trailer...right? */
1672                 mlog_bug_on_msg(ocfs2_skip_dir_trailer(dir, de, offset, size),
1673                                 "Hit dir trailer trying to insert %.*s "
1674                                 "(namelen %d) into directory %llu.  "
1675                                 "offset is %lu, trailer offset is %d\n",
1676                                 namelen, name, namelen,
1677                                 (unsigned long long)parent_fe_bh->b_blocknr,
1678                                 offset, ocfs2_dir_trailer_blk_off(dir->i_sb));
1679
1680                 if (ocfs2_dirent_would_fit(de, rec_len)) {
1681                         dir->i_mtime = dir->i_ctime = current_time(dir);
1682                         retval = ocfs2_mark_inode_dirty(handle, dir, parent_fe_bh);
1683                         if (retval < 0) {
1684                                 mlog_errno(retval);
1685                                 goto bail;
1686                         }
1687
1688                         if (insert_bh == parent_fe_bh)
1689                                 retval = ocfs2_journal_access_di(handle,
1690                                                                  INODE_CACHE(dir),
1691                                                                  insert_bh,
1692                                                                  OCFS2_JOURNAL_ACCESS_WRITE);
1693                         else {
1694                                 retval = ocfs2_journal_access_db(handle,
1695                                                                  INODE_CACHE(dir),
1696                                                                  insert_bh,
1697                                               OCFS2_JOURNAL_ACCESS_WRITE);
1698
1699                                 if (!retval && ocfs2_dir_indexed(dir))
1700                                         retval = ocfs2_dx_dir_insert(dir,
1701                                                                 handle,
1702                                                                 lookup);
1703                         }
1704
1705                         if (retval) {
1706                                 mlog_errno(retval);
1707                                 goto bail;
1708                         }
1709
1710                         /* By now the buffer is marked for journaling */
1711                         offset += le16_to_cpu(de->rec_len);
1712                         if (le64_to_cpu(de->inode)) {
1713                                 de1 = (struct ocfs2_dir_entry *)((char *) de +
1714                                         OCFS2_DIR_REC_LEN(de->name_len));
1715                                 de1->rec_len =
1716                                         cpu_to_le16(le16_to_cpu(de->rec_len) -
1717                                         OCFS2_DIR_REC_LEN(de->name_len));
1718                                 de->rec_len = cpu_to_le16(OCFS2_DIR_REC_LEN(de->name_len));
1719                                 de = de1;
1720                         }
1721                         de->file_type = OCFS2_FT_UNKNOWN;
1722                         if (blkno) {
1723                                 de->inode = cpu_to_le64(blkno);
1724                                 ocfs2_set_de_type(de, inode->i_mode);
1725                         } else
1726                                 de->inode = 0;
1727                         de->name_len = namelen;
1728                         memcpy(de->name, name, namelen);
1729
1730                         if (ocfs2_dir_indexed(dir))
1731                                 ocfs2_recalc_free_list(dir, handle, lookup);
1732
1733                         inode_inc_iversion(dir);
1734                         ocfs2_journal_dirty(handle, insert_bh);
1735                         retval = 0;
1736                         goto bail;
1737                 }
1738
1739                 offset += le16_to_cpu(de->rec_len);
1740                 de = (struct ocfs2_dir_entry *) ((char *) de + le16_to_cpu(de->rec_len));
1741         }
1742
1743         /* when you think about it, the assert above should prevent us
1744          * from ever getting here. */
1745         retval = -ENOSPC;
1746 bail:
1747         if (retval)
1748                 mlog_errno(retval);
1749
1750         return retval;
1751 }
1752
1753 static int ocfs2_dir_foreach_blk_id(struct inode *inode,
1754                                     u64 *f_version,
1755                                     struct dir_context *ctx)
1756 {
1757         int ret, i;
1758         unsigned long offset = ctx->pos;
1759         struct buffer_head *di_bh = NULL;
1760         struct ocfs2_dinode *di;
1761         struct ocfs2_inline_data *data;
1762         struct ocfs2_dir_entry *de;
1763
1764         ret = ocfs2_read_inode_block(inode, &di_bh);
1765         if (ret) {
1766                 mlog(ML_ERROR, "Unable to read inode block for dir %llu\n",
1767                      (unsigned long long)OCFS2_I(inode)->ip_blkno);
1768                 goto out;
1769         }
1770
1771         di = (struct ocfs2_dinode *)di_bh->b_data;
1772         data = &di->id2.i_data;
1773
1774         while (ctx->pos < i_size_read(inode)) {
1775                 /* If the dir block has changed since the last call to
1776                  * readdir(2), then we might be pointing to an invalid
1777                  * dirent right now.  Scan from the start of the block
1778                  * to make sure. */
1779                 if (!inode_eq_iversion(inode, *f_version)) {
1780                         for (i = 0; i < i_size_read(inode) && i < offset; ) {
1781                                 de = (struct ocfs2_dir_entry *)
1782                                         (data->id_data + i);
1783                                 /* It's too expensive to do a full
1784                                  * dirent test each time round this
1785                                  * loop, but we do have to test at
1786                                  * least that it is non-zero.  A
1787                                  * failure will be detected in the
1788                                  * dirent test below. */
1789                                 if (le16_to_cpu(de->rec_len) <
1790                                     OCFS2_DIR_REC_LEN(1))
1791                                         break;
1792                                 i += le16_to_cpu(de->rec_len);
1793                         }
1794                         ctx->pos = offset = i;
1795                         *f_version = inode_query_iversion(inode);
1796                 }
1797
1798                 de = (struct ocfs2_dir_entry *) (data->id_data + ctx->pos);
1799                 if (!ocfs2_check_dir_entry(inode, de, di_bh, ctx->pos)) {
1800                         /* On error, skip the f_pos to the end. */
1801                         ctx->pos = i_size_read(inode);
1802                         break;
1803                 }
1804                 offset += le16_to_cpu(de->rec_len);
1805                 if (le64_to_cpu(de->inode)) {
1806                         unsigned char d_type = DT_UNKNOWN;
1807
1808                         if (de->file_type < OCFS2_FT_MAX)
1809                                 d_type = ocfs2_filetype_table[de->file_type];
1810
1811                         if (!dir_emit(ctx, de->name, de->name_len,
1812                                       le64_to_cpu(de->inode), d_type))
1813                                 goto out;
1814                 }
1815                 ctx->pos += le16_to_cpu(de->rec_len);
1816         }
1817 out:
1818         brelse(di_bh);
1819         return 0;
1820 }
1821
1822 /*
1823  * NOTE: This function can be called against unindexed directories,
1824  * and indexed ones.
1825  */
1826 static int ocfs2_dir_foreach_blk_el(struct inode *inode,
1827                                     u64 *f_version,
1828                                     struct dir_context *ctx,
1829                                     bool persist)
1830 {
1831         unsigned long offset, blk, last_ra_blk = 0;
1832         int i;
1833         struct buffer_head * bh, * tmp;
1834         struct ocfs2_dir_entry * de;
1835         struct super_block * sb = inode->i_sb;
1836         unsigned int ra_sectors = 16;
1837         int stored = 0;
1838
1839         bh = NULL;
1840
1841         offset = ctx->pos & (sb->s_blocksize - 1);
1842
1843         while (ctx->pos < i_size_read(inode)) {
1844                 blk = ctx->pos >> sb->s_blocksize_bits;
1845                 if (ocfs2_read_dir_block(inode, blk, &bh, 0)) {
1846                         /* Skip the corrupt dirblock and keep trying */
1847                         ctx->pos += sb->s_blocksize - offset;
1848                         continue;
1849                 }
1850
1851                 /* The idea here is to begin with 8k read-ahead and to stay
1852                  * 4k ahead of our current position.
1853                  *
1854                  * TODO: Use the pagecache for this. We just need to
1855                  * make sure it's cluster-safe... */
1856                 if (!last_ra_blk
1857                     || (((last_ra_blk - blk) << 9) <= (ra_sectors / 2))) {
1858                         for (i = ra_sectors >> (sb->s_blocksize_bits - 9);
1859                              i > 0; i--) {
1860                                 tmp = NULL;
1861                                 if (!ocfs2_read_dir_block(inode, ++blk, &tmp,
1862                                                           OCFS2_BH_READAHEAD))
1863                                         brelse(tmp);
1864                         }
1865                         last_ra_blk = blk;
1866                         ra_sectors = 8;
1867                 }
1868
1869                 /* If the dir block has changed since the last call to
1870                  * readdir(2), then we might be pointing to an invalid
1871                  * dirent right now.  Scan from the start of the block
1872                  * to make sure. */
1873                 if (!inode_eq_iversion(inode, *f_version)) {
1874                         for (i = 0; i < sb->s_blocksize && i < offset; ) {
1875                                 de = (struct ocfs2_dir_entry *) (bh->b_data + i);
1876                                 /* It's too expensive to do a full
1877                                  * dirent test each time round this
1878                                  * loop, but we do have to test at
1879                                  * least that it is non-zero.  A
1880                                  * failure will be detected in the
1881                                  * dirent test below. */
1882                                 if (le16_to_cpu(de->rec_len) <
1883                                     OCFS2_DIR_REC_LEN(1))
1884                                         break;
1885                                 i += le16_to_cpu(de->rec_len);
1886                         }
1887                         offset = i;
1888                         ctx->pos = (ctx->pos & ~(sb->s_blocksize - 1))
1889                                 | offset;
1890                         *f_version = inode_query_iversion(inode);
1891                 }
1892
1893                 while (ctx->pos < i_size_read(inode)
1894                        && offset < sb->s_blocksize) {
1895                         de = (struct ocfs2_dir_entry *) (bh->b_data + offset);
1896                         if (!ocfs2_check_dir_entry(inode, de, bh, offset)) {
1897                                 /* On error, skip the f_pos to the
1898                                    next block. */
1899                                 ctx->pos = (ctx->pos | (sb->s_blocksize - 1)) + 1;
1900                                 brelse(bh);
1901                                 continue;
1902                         }
1903                         if (le64_to_cpu(de->inode)) {
1904                                 unsigned char d_type = DT_UNKNOWN;
1905
1906                                 if (de->file_type < OCFS2_FT_MAX)
1907                                         d_type = ocfs2_filetype_table[de->file_type];
1908                                 if (!dir_emit(ctx, de->name,
1909                                                 de->name_len,
1910                                                 le64_to_cpu(de->inode),
1911                                                 d_type)) {
1912                                         brelse(bh);
1913                                         return 0;
1914                                 }
1915                                 stored++;
1916                         }
1917                         offset += le16_to_cpu(de->rec_len);
1918                         ctx->pos += le16_to_cpu(de->rec_len);
1919                 }
1920                 offset = 0;
1921                 brelse(bh);
1922                 bh = NULL;
1923                 if (!persist && stored)
1924                         break;
1925         }
1926         return 0;
1927 }
1928
1929 static int ocfs2_dir_foreach_blk(struct inode *inode, u64 *f_version,
1930                                  struct dir_context *ctx,
1931                                  bool persist)
1932 {
1933         if (OCFS2_I(inode)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
1934                 return ocfs2_dir_foreach_blk_id(inode, f_version, ctx);
1935         return ocfs2_dir_foreach_blk_el(inode, f_version, ctx, persist);
1936 }
1937
1938 /*
1939  * This is intended to be called from inside other kernel functions,
1940  * so we fake some arguments.
1941  */
1942 int ocfs2_dir_foreach(struct inode *inode, struct dir_context *ctx)
1943 {
1944         u64 version = inode_query_iversion(inode);
1945         ocfs2_dir_foreach_blk(inode, &version, ctx, true);
1946         return 0;
1947 }
1948
1949 /*
1950  * ocfs2_readdir()
1951  *
1952  */
1953 int ocfs2_readdir(struct file *file, struct dir_context *ctx)
1954 {
1955         int error = 0;
1956         struct inode *inode = file_inode(file);
1957         int lock_level = 0;
1958
1959         trace_ocfs2_readdir((unsigned long long)OCFS2_I(inode)->ip_blkno);
1960
1961         error = ocfs2_inode_lock_atime(inode, file->f_path.mnt, &lock_level, 1);
1962         if (lock_level && error >= 0) {
1963                 /* We release EX lock which used to update atime
1964                  * and get PR lock again to reduce contention
1965                  * on commonly accessed directories. */
1966                 ocfs2_inode_unlock(inode, 1);
1967                 lock_level = 0;
1968                 error = ocfs2_inode_lock(inode, NULL, 0);
1969         }
1970         if (error < 0) {
1971                 if (error != -ENOENT)
1972                         mlog_errno(error);
1973                 /* we haven't got any yet, so propagate the error. */
1974                 goto bail_nolock;
1975         }
1976
1977         error = ocfs2_dir_foreach_blk(inode, &file->f_version, ctx, false);
1978
1979         ocfs2_inode_unlock(inode, lock_level);
1980         if (error)
1981                 mlog_errno(error);
1982
1983 bail_nolock:
1984
1985         return error;
1986 }
1987
1988 /*
1989  * NOTE: this should always be called with parent dir i_mutex taken.
1990  */
1991 int ocfs2_find_files_on_disk(const char *name,
1992                              int namelen,
1993                              u64 *blkno,
1994                              struct inode *inode,
1995                              struct ocfs2_dir_lookup_result *lookup)
1996 {
1997         int status = -ENOENT;
1998
1999         trace_ocfs2_find_files_on_disk(namelen, name, blkno,
2000                                 (unsigned long long)OCFS2_I(inode)->ip_blkno);
2001
2002         status = ocfs2_find_entry(name, namelen, inode, lookup);
2003         if (status)
2004                 goto leave;
2005
2006         *blkno = le64_to_cpu(lookup->dl_entry->inode);
2007
2008         status = 0;
2009 leave:
2010
2011         return status;
2012 }
2013
2014 /*
2015  * Convenience function for callers which just want the block number
2016  * mapped to a name and don't require the full dirent info, etc.
2017  */
2018 int ocfs2_lookup_ino_from_name(struct inode *dir, const char *name,
2019                                int namelen, u64 *blkno)
2020 {
2021         int ret;
2022         struct ocfs2_dir_lookup_result lookup = { NULL, };
2023
2024         ret = ocfs2_find_files_on_disk(name, namelen, blkno, dir, &lookup);
2025         ocfs2_free_dir_lookup_result(&lookup);
2026
2027         return ret;
2028 }
2029
2030 /* Check for a name within a directory.
2031  *
2032  * Return 0 if the name does not exist
2033  * Return -EEXIST if the directory contains the name
2034  *
2035  * Callers should have i_mutex + a cluster lock on dir
2036  */
2037 int ocfs2_check_dir_for_entry(struct inode *dir,
2038                               const char *name,
2039                               int namelen)
2040 {
2041         int ret = 0;
2042         struct ocfs2_dir_lookup_result lookup = { NULL, };
2043
2044         trace_ocfs2_check_dir_for_entry(
2045                 (unsigned long long)OCFS2_I(dir)->ip_blkno, namelen, name);
2046
2047         if (ocfs2_find_entry(name, namelen, dir, &lookup) == 0) {
2048                 ret = -EEXIST;
2049                 mlog_errno(ret);
2050         }
2051
2052         ocfs2_free_dir_lookup_result(&lookup);
2053
2054         return ret;
2055 }
2056
2057 struct ocfs2_empty_dir_priv {
2058         struct dir_context ctx;
2059         unsigned seen_dot;
2060         unsigned seen_dot_dot;
2061         unsigned seen_other;
2062         unsigned dx_dir;
2063 };
2064 static int ocfs2_empty_dir_filldir(struct dir_context *ctx, const char *name,
2065                                    int name_len, loff_t pos, u64 ino,
2066                                    unsigned type)
2067 {
2068         struct ocfs2_empty_dir_priv *p =
2069                 container_of(ctx, struct ocfs2_empty_dir_priv, ctx);
2070
2071         /*
2072          * Check the positions of "." and ".." records to be sure
2073          * they're in the correct place.
2074          *
2075          * Indexed directories don't need to proceed past the first
2076          * two entries, so we end the scan after seeing '..'. Despite
2077          * that, we allow the scan to proceed In the event that we
2078          * have a corrupted indexed directory (no dot or dot dot
2079          * entries). This allows us to double check for existing
2080          * entries which might not have been found in the index.
2081          */
2082         if (name_len == 1 && !strncmp(".", name, 1) && pos == 0) {
2083                 p->seen_dot = 1;
2084                 return 0;
2085         }
2086
2087         if (name_len == 2 && !strncmp("..", name, 2) &&
2088             pos == OCFS2_DIR_REC_LEN(1)) {
2089                 p->seen_dot_dot = 1;
2090
2091                 if (p->dx_dir && p->seen_dot)
2092                         return 1;
2093
2094                 return 0;
2095         }
2096
2097         p->seen_other = 1;
2098         return 1;
2099 }
2100
2101 static int ocfs2_empty_dir_dx(struct inode *inode,
2102                               struct ocfs2_empty_dir_priv *priv)
2103 {
2104         int ret;
2105         struct buffer_head *di_bh = NULL;
2106         struct buffer_head *dx_root_bh = NULL;
2107         struct ocfs2_dinode *di;
2108         struct ocfs2_dx_root_block *dx_root;
2109
2110         priv->dx_dir = 1;
2111
2112         ret = ocfs2_read_inode_block(inode, &di_bh);
2113         if (ret) {
2114                 mlog_errno(ret);
2115                 goto out;
2116         }
2117         di = (struct ocfs2_dinode *)di_bh->b_data;
2118
2119         ret = ocfs2_read_dx_root(inode, di, &dx_root_bh);
2120         if (ret) {
2121                 mlog_errno(ret);
2122                 goto out;
2123         }
2124         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
2125
2126         if (le32_to_cpu(dx_root->dr_num_entries) != 2)
2127                 priv->seen_other = 1;
2128
2129 out:
2130         brelse(di_bh);
2131         brelse(dx_root_bh);
2132         return ret;
2133 }
2134
2135 /*
2136  * routine to check that the specified directory is empty (for rmdir)
2137  *
2138  * Returns 1 if dir is empty, zero otherwise.
2139  *
2140  * XXX: This is a performance problem for unindexed directories.
2141  */
2142 int ocfs2_empty_dir(struct inode *inode)
2143 {
2144         int ret;
2145         struct ocfs2_empty_dir_priv priv = {
2146                 .ctx.actor = ocfs2_empty_dir_filldir,
2147         };
2148
2149         if (ocfs2_dir_indexed(inode)) {
2150                 ret = ocfs2_empty_dir_dx(inode, &priv);
2151                 if (ret)
2152                         mlog_errno(ret);
2153                 /*
2154                  * We still run ocfs2_dir_foreach to get the checks
2155                  * for "." and "..".
2156                  */
2157         }
2158
2159         ret = ocfs2_dir_foreach(inode, &priv.ctx);
2160         if (ret)
2161                 mlog_errno(ret);
2162
2163         if (!priv.seen_dot || !priv.seen_dot_dot) {
2164                 mlog(ML_ERROR, "bad directory (dir #%llu) - no `.' or `..'\n",
2165                      (unsigned long long)OCFS2_I(inode)->ip_blkno);
2166                 /*
2167                  * XXX: Is it really safe to allow an unlink to continue?
2168                  */
2169                 return 1;
2170         }
2171
2172         return !priv.seen_other;
2173 }
2174
2175 /*
2176  * Fills "." and ".." dirents in a new directory block. Returns dirent for
2177  * "..", which might be used during creation of a directory with a trailing
2178  * header. It is otherwise safe to ignore the return code.
2179  */
2180 static struct ocfs2_dir_entry *ocfs2_fill_initial_dirents(struct inode *inode,
2181                                                           struct inode *parent,
2182                                                           char *start,
2183                                                           unsigned int size)
2184 {
2185         struct ocfs2_dir_entry *de = (struct ocfs2_dir_entry *)start;
2186
2187         de->inode = cpu_to_le64(OCFS2_I(inode)->ip_blkno);
2188         de->name_len = 1;
2189         de->rec_len =
2190                 cpu_to_le16(OCFS2_DIR_REC_LEN(de->name_len));
2191         strcpy(de->name, ".");
2192         ocfs2_set_de_type(de, S_IFDIR);
2193
2194         de = (struct ocfs2_dir_entry *) ((char *)de + le16_to_cpu(de->rec_len));
2195         de->inode = cpu_to_le64(OCFS2_I(parent)->ip_blkno);
2196         de->rec_len = cpu_to_le16(size - OCFS2_DIR_REC_LEN(1));
2197         de->name_len = 2;
2198         strcpy(de->name, "..");
2199         ocfs2_set_de_type(de, S_IFDIR);
2200
2201         return de;
2202 }
2203
2204 /*
2205  * This works together with code in ocfs2_mknod_locked() which sets
2206  * the inline-data flag and initializes the inline-data section.
2207  */
2208 static int ocfs2_fill_new_dir_id(struct ocfs2_super *osb,
2209                                  handle_t *handle,
2210                                  struct inode *parent,
2211                                  struct inode *inode,
2212                                  struct buffer_head *di_bh)
2213 {
2214         int ret;
2215         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
2216         struct ocfs2_inline_data *data = &di->id2.i_data;
2217         unsigned int size = le16_to_cpu(data->id_count);
2218
2219         ret = ocfs2_journal_access_di(handle, INODE_CACHE(inode), di_bh,
2220                                       OCFS2_JOURNAL_ACCESS_WRITE);
2221         if (ret) {
2222                 mlog_errno(ret);
2223                 goto out;
2224         }
2225
2226         ocfs2_fill_initial_dirents(inode, parent, data->id_data, size);
2227         ocfs2_journal_dirty(handle, di_bh);
2228
2229         i_size_write(inode, size);
2230         set_nlink(inode, 2);
2231         inode->i_blocks = ocfs2_inode_sector_count(inode);
2232
2233         ret = ocfs2_mark_inode_dirty(handle, inode, di_bh);
2234         if (ret < 0)
2235                 mlog_errno(ret);
2236
2237 out:
2238         return ret;
2239 }
2240
2241 static int ocfs2_fill_new_dir_el(struct ocfs2_super *osb,
2242                                  handle_t *handle,
2243                                  struct inode *parent,
2244                                  struct inode *inode,
2245                                  struct buffer_head *fe_bh,
2246                                  struct ocfs2_alloc_context *data_ac,
2247                                  struct buffer_head **ret_new_bh)
2248 {
2249         int status;
2250         unsigned int size = osb->sb->s_blocksize;
2251         struct buffer_head *new_bh = NULL;
2252         struct ocfs2_dir_entry *de;
2253
2254         if (ocfs2_new_dir_wants_trailer(inode))
2255                 size = ocfs2_dir_trailer_blk_off(parent->i_sb);
2256
2257         status = ocfs2_do_extend_dir(osb->sb, handle, inode, fe_bh,
2258                                      data_ac, NULL, &new_bh);
2259         if (status < 0) {
2260                 mlog_errno(status);
2261                 goto bail;
2262         }
2263
2264         ocfs2_set_new_buffer_uptodate(INODE_CACHE(inode), new_bh);
2265
2266         status = ocfs2_journal_access_db(handle, INODE_CACHE(inode), new_bh,
2267                                          OCFS2_JOURNAL_ACCESS_CREATE);
2268         if (status < 0) {
2269                 mlog_errno(status);
2270                 goto bail;
2271         }
2272         memset(new_bh->b_data, 0, osb->sb->s_blocksize);
2273
2274         de = ocfs2_fill_initial_dirents(inode, parent, new_bh->b_data, size);
2275         if (ocfs2_new_dir_wants_trailer(inode)) {
2276                 int size = le16_to_cpu(de->rec_len);
2277
2278                 /*
2279                  * Figure out the size of the hole left over after
2280                  * insertion of '.' and '..'. The trailer wants this
2281                  * information.
2282                  */
2283                 size -= OCFS2_DIR_REC_LEN(2);
2284                 size -= sizeof(struct ocfs2_dir_block_trailer);
2285
2286                 ocfs2_init_dir_trailer(inode, new_bh, size);
2287         }
2288
2289         ocfs2_journal_dirty(handle, new_bh);
2290
2291         i_size_write(inode, inode->i_sb->s_blocksize);
2292         set_nlink(inode, 2);
2293         inode->i_blocks = ocfs2_inode_sector_count(inode);
2294         status = ocfs2_mark_inode_dirty(handle, inode, fe_bh);
2295         if (status < 0) {
2296                 mlog_errno(status);
2297                 goto bail;
2298         }
2299
2300         status = 0;
2301         if (ret_new_bh) {
2302                 *ret_new_bh = new_bh;
2303                 new_bh = NULL;
2304         }
2305 bail:
2306         brelse(new_bh);
2307
2308         return status;
2309 }
2310
2311 static int ocfs2_dx_dir_attach_index(struct ocfs2_super *osb,
2312                                      handle_t *handle, struct inode *dir,
2313                                      struct buffer_head *di_bh,
2314                                      struct buffer_head *dirdata_bh,
2315                                      struct ocfs2_alloc_context *meta_ac,
2316                                      int dx_inline, u32 num_entries,
2317                                      struct buffer_head **ret_dx_root_bh)
2318 {
2319         int ret;
2320         struct ocfs2_dinode *di = (struct ocfs2_dinode *) di_bh->b_data;
2321         u16 dr_suballoc_bit;
2322         u64 suballoc_loc, dr_blkno;
2323         unsigned int num_bits;
2324         struct buffer_head *dx_root_bh = NULL;
2325         struct ocfs2_dx_root_block *dx_root;
2326         struct ocfs2_dir_block_trailer *trailer =
2327                 ocfs2_trailer_from_bh(dirdata_bh, dir->i_sb);
2328
2329         ret = ocfs2_claim_metadata(handle, meta_ac, 1, &suballoc_loc,
2330                                    &dr_suballoc_bit, &num_bits, &dr_blkno);
2331         if (ret) {
2332                 mlog_errno(ret);
2333                 goto out;
2334         }
2335
2336         trace_ocfs2_dx_dir_attach_index(
2337                                 (unsigned long long)OCFS2_I(dir)->ip_blkno,
2338                                 (unsigned long long)dr_blkno);
2339
2340         dx_root_bh = sb_getblk(osb->sb, dr_blkno);
2341         if (dx_root_bh == NULL) {
2342                 ret = -ENOMEM;
2343                 goto out;
2344         }
2345         ocfs2_set_new_buffer_uptodate(INODE_CACHE(dir), dx_root_bh);
2346
2347         ret = ocfs2_journal_access_dr(handle, INODE_CACHE(dir), dx_root_bh,
2348                                       OCFS2_JOURNAL_ACCESS_CREATE);
2349         if (ret < 0) {
2350                 mlog_errno(ret);
2351                 goto out;
2352         }
2353
2354         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
2355         memset(dx_root, 0, osb->sb->s_blocksize);
2356         strcpy(dx_root->dr_signature, OCFS2_DX_ROOT_SIGNATURE);
2357         dx_root->dr_suballoc_slot = cpu_to_le16(meta_ac->ac_alloc_slot);
2358         dx_root->dr_suballoc_loc = cpu_to_le64(suballoc_loc);
2359         dx_root->dr_suballoc_bit = cpu_to_le16(dr_suballoc_bit);
2360         dx_root->dr_fs_generation = cpu_to_le32(osb->fs_generation);
2361         dx_root->dr_blkno = cpu_to_le64(dr_blkno);
2362         dx_root->dr_dir_blkno = cpu_to_le64(OCFS2_I(dir)->ip_blkno);
2363         dx_root->dr_num_entries = cpu_to_le32(num_entries);
2364         if (le16_to_cpu(trailer->db_free_rec_len))
2365                 dx_root->dr_free_blk = cpu_to_le64(dirdata_bh->b_blocknr);
2366         else
2367                 dx_root->dr_free_blk = cpu_to_le64(0);
2368
2369         if (dx_inline) {
2370                 dx_root->dr_flags |= OCFS2_DX_FLAG_INLINE;
2371                 dx_root->dr_entries.de_count =
2372                         cpu_to_le16(ocfs2_dx_entries_per_root(osb->sb));
2373         } else {
2374                 dx_root->dr_list.l_count =
2375                         cpu_to_le16(ocfs2_extent_recs_per_dx_root(osb->sb));
2376         }
2377         ocfs2_journal_dirty(handle, dx_root_bh);
2378
2379         ret = ocfs2_journal_access_di(handle, INODE_CACHE(dir), di_bh,
2380                                       OCFS2_JOURNAL_ACCESS_CREATE);
2381         if (ret) {
2382                 mlog_errno(ret);
2383                 goto out;
2384         }
2385
2386         di->i_dx_root = cpu_to_le64(dr_blkno);
2387
2388         spin_lock(&OCFS2_I(dir)->ip_lock);
2389         OCFS2_I(dir)->ip_dyn_features |= OCFS2_INDEXED_DIR_FL;
2390         di->i_dyn_features = cpu_to_le16(OCFS2_I(dir)->ip_dyn_features);
2391         spin_unlock(&OCFS2_I(dir)->ip_lock);
2392
2393         ocfs2_journal_dirty(handle, di_bh);
2394
2395         *ret_dx_root_bh = dx_root_bh;
2396         dx_root_bh = NULL;
2397
2398 out:
2399         brelse(dx_root_bh);
2400         return ret;
2401 }
2402
2403 static int ocfs2_dx_dir_format_cluster(struct ocfs2_super *osb,
2404                                        handle_t *handle, struct inode *dir,
2405                                        struct buffer_head **dx_leaves,
2406                                        int num_dx_leaves, u64 start_blk)
2407 {
2408         int ret, i;
2409         struct ocfs2_dx_leaf *dx_leaf;
2410         struct buffer_head *bh;
2411
2412         for (i = 0; i < num_dx_leaves; i++) {
2413                 bh = sb_getblk(osb->sb, start_blk + i);
2414                 if (bh == NULL) {
2415                         ret = -ENOMEM;
2416                         goto out;
2417                 }
2418                 dx_leaves[i] = bh;
2419
2420                 ocfs2_set_new_buffer_uptodate(INODE_CACHE(dir), bh);
2421
2422                 ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir), bh,
2423                                               OCFS2_JOURNAL_ACCESS_CREATE);
2424                 if (ret < 0) {
2425                         mlog_errno(ret);
2426                         goto out;
2427                 }
2428
2429                 dx_leaf = (struct ocfs2_dx_leaf *) bh->b_data;
2430
2431                 memset(dx_leaf, 0, osb->sb->s_blocksize);
2432                 strcpy(dx_leaf->dl_signature, OCFS2_DX_LEAF_SIGNATURE);
2433                 dx_leaf->dl_fs_generation = cpu_to_le32(osb->fs_generation);
2434                 dx_leaf->dl_blkno = cpu_to_le64(bh->b_blocknr);
2435                 dx_leaf->dl_list.de_count =
2436                         cpu_to_le16(ocfs2_dx_entries_per_leaf(osb->sb));
2437
2438                 trace_ocfs2_dx_dir_format_cluster(
2439                                 (unsigned long long)OCFS2_I(dir)->ip_blkno,
2440                                 (unsigned long long)bh->b_blocknr,
2441                                 le16_to_cpu(dx_leaf->dl_list.de_count));
2442
2443                 ocfs2_journal_dirty(handle, bh);
2444         }
2445
2446         ret = 0;
2447 out:
2448         return ret;
2449 }
2450
2451 /*
2452  * Allocates and formats a new cluster for use in an indexed dir
2453  * leaf. This version will not do the extent insert, so that it can be
2454  * used by operations which need careful ordering.
2455  */
2456 static int __ocfs2_dx_dir_new_cluster(struct inode *dir,
2457                                       u32 cpos, handle_t *handle,
2458                                       struct ocfs2_alloc_context *data_ac,
2459                                       struct buffer_head **dx_leaves,
2460                                       int num_dx_leaves, u64 *ret_phys_blkno)
2461 {
2462         int ret;
2463         u32 phys, num;
2464         u64 phys_blkno;
2465         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
2466
2467         /*
2468          * XXX: For create, this should claim cluster for the index
2469          * *before* the unindexed insert so that we have a better
2470          * chance of contiguousness as the directory grows in number
2471          * of entries.
2472          */
2473         ret = __ocfs2_claim_clusters(handle, data_ac, 1, 1, &phys, &num);
2474         if (ret) {
2475                 mlog_errno(ret);
2476                 goto out;
2477         }
2478
2479         /*
2480          * Format the new cluster first. That way, we're inserting
2481          * valid data.
2482          */
2483         phys_blkno = ocfs2_clusters_to_blocks(osb->sb, phys);
2484         ret = ocfs2_dx_dir_format_cluster(osb, handle, dir, dx_leaves,
2485                                           num_dx_leaves, phys_blkno);
2486         if (ret) {
2487                 mlog_errno(ret);
2488                 goto out;
2489         }
2490
2491         *ret_phys_blkno = phys_blkno;
2492 out:
2493         return ret;
2494 }
2495
2496 static int ocfs2_dx_dir_new_cluster(struct inode *dir,
2497                                     struct ocfs2_extent_tree *et,
2498                                     u32 cpos, handle_t *handle,
2499                                     struct ocfs2_alloc_context *data_ac,
2500                                     struct ocfs2_alloc_context *meta_ac,
2501                                     struct buffer_head **dx_leaves,
2502                                     int num_dx_leaves)
2503 {
2504         int ret;
2505         u64 phys_blkno;
2506
2507         ret = __ocfs2_dx_dir_new_cluster(dir, cpos, handle, data_ac, dx_leaves,
2508                                          num_dx_leaves, &phys_blkno);
2509         if (ret) {
2510                 mlog_errno(ret);
2511                 goto out;
2512         }
2513
2514         ret = ocfs2_insert_extent(handle, et, cpos, phys_blkno, 1, 0,
2515                                   meta_ac);
2516         if (ret)
2517                 mlog_errno(ret);
2518 out:
2519         return ret;
2520 }
2521
2522 static struct buffer_head **ocfs2_dx_dir_kmalloc_leaves(struct super_block *sb,
2523                                                         int *ret_num_leaves)
2524 {
2525         int num_dx_leaves = ocfs2_clusters_to_blocks(sb, 1);
2526         struct buffer_head **dx_leaves;
2527
2528         dx_leaves = kcalloc(num_dx_leaves, sizeof(struct buffer_head *),
2529                             GFP_NOFS);
2530         if (dx_leaves && ret_num_leaves)
2531                 *ret_num_leaves = num_dx_leaves;
2532
2533         return dx_leaves;
2534 }
2535
2536 static int ocfs2_fill_new_dir_dx(struct ocfs2_super *osb,
2537                                  handle_t *handle,
2538                                  struct inode *parent,
2539                                  struct inode *inode,
2540                                  struct buffer_head *di_bh,
2541                                  struct ocfs2_alloc_context *data_ac,
2542                                  struct ocfs2_alloc_context *meta_ac)
2543 {
2544         int ret;
2545         struct buffer_head *leaf_bh = NULL;
2546         struct buffer_head *dx_root_bh = NULL;
2547         struct ocfs2_dx_hinfo hinfo;
2548         struct ocfs2_dx_root_block *dx_root;
2549         struct ocfs2_dx_entry_list *entry_list;
2550
2551         /*
2552          * Our strategy is to create the directory as though it were
2553          * unindexed, then add the index block. This works with very
2554          * little complication since the state of a new directory is a
2555          * very well known quantity.
2556          *
2557          * Essentially, we have two dirents ("." and ".."), in the 1st
2558          * block which need indexing. These are easily inserted into
2559          * the index block.
2560          */
2561
2562         ret = ocfs2_fill_new_dir_el(osb, handle, parent, inode, di_bh,
2563                                     data_ac, &leaf_bh);
2564         if (ret) {
2565                 mlog_errno(ret);
2566                 goto out;
2567         }
2568
2569         ret = ocfs2_dx_dir_attach_index(osb, handle, inode, di_bh, leaf_bh,
2570                                         meta_ac, 1, 2, &dx_root_bh);
2571         if (ret) {
2572                 mlog_errno(ret);
2573                 goto out;
2574         }
2575         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
2576         entry_list = &dx_root->dr_entries;
2577
2578         /* Buffer has been journaled for us by ocfs2_dx_dir_attach_index */
2579         ocfs2_dx_dir_name_hash(inode, ".", 1, &hinfo);
2580         ocfs2_dx_entry_list_insert(entry_list, &hinfo, leaf_bh->b_blocknr);
2581
2582         ocfs2_dx_dir_name_hash(inode, "..", 2, &hinfo);
2583         ocfs2_dx_entry_list_insert(entry_list, &hinfo, leaf_bh->b_blocknr);
2584
2585 out:
2586         brelse(dx_root_bh);
2587         brelse(leaf_bh);
2588         return ret;
2589 }
2590
2591 int ocfs2_fill_new_dir(struct ocfs2_super *osb,
2592                        handle_t *handle,
2593                        struct inode *parent,
2594                        struct inode *inode,
2595                        struct buffer_head *fe_bh,
2596                        struct ocfs2_alloc_context *data_ac,
2597                        struct ocfs2_alloc_context *meta_ac)
2598
2599 {
2600         BUG_ON(!ocfs2_supports_inline_data(osb) && data_ac == NULL);
2601
2602         if (OCFS2_I(inode)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
2603                 return ocfs2_fill_new_dir_id(osb, handle, parent, inode, fe_bh);
2604
2605         if (ocfs2_supports_indexed_dirs(osb))
2606                 return ocfs2_fill_new_dir_dx(osb, handle, parent, inode, fe_bh,
2607                                              data_ac, meta_ac);
2608
2609         return ocfs2_fill_new_dir_el(osb, handle, parent, inode, fe_bh,
2610                                      data_ac, NULL);
2611 }
2612
2613 static int ocfs2_dx_dir_index_block(struct inode *dir,
2614                                     handle_t *handle,
2615                                     struct buffer_head **dx_leaves,
2616                                     int num_dx_leaves,
2617                                     u32 *num_dx_entries,
2618                                     struct buffer_head *dirent_bh)
2619 {
2620         int ret = 0, namelen, i;
2621         char *de_buf, *limit;
2622         struct ocfs2_dir_entry *de;
2623         struct buffer_head *dx_leaf_bh;
2624         struct ocfs2_dx_hinfo hinfo;
2625         u64 dirent_blk = dirent_bh->b_blocknr;
2626
2627         de_buf = dirent_bh->b_data;
2628         limit = de_buf + dir->i_sb->s_blocksize;
2629
2630         while (de_buf < limit) {
2631                 de = (struct ocfs2_dir_entry *)de_buf;
2632
2633                 namelen = de->name_len;
2634                 if (!namelen || !de->inode)
2635                         goto inc;
2636
2637                 ocfs2_dx_dir_name_hash(dir, de->name, namelen, &hinfo);
2638
2639                 i = ocfs2_dx_dir_hash_idx(OCFS2_SB(dir->i_sb), &hinfo);
2640                 dx_leaf_bh = dx_leaves[i];
2641
2642                 ret = __ocfs2_dx_dir_leaf_insert(dir, handle, &hinfo,
2643                                                  dirent_blk, dx_leaf_bh);
2644                 if (ret) {
2645                         mlog_errno(ret);
2646                         goto out;
2647                 }
2648
2649                 *num_dx_entries = *num_dx_entries + 1;
2650
2651 inc:
2652                 de_buf += le16_to_cpu(de->rec_len);
2653         }
2654
2655 out:
2656         return ret;
2657 }
2658
2659 /*
2660  * XXX: This expects dx_root_bh to already be part of the transaction.
2661  */
2662 static void ocfs2_dx_dir_index_root_block(struct inode *dir,
2663                                          struct buffer_head *dx_root_bh,
2664                                          struct buffer_head *dirent_bh)
2665 {
2666         char *de_buf, *limit;
2667         struct ocfs2_dx_root_block *dx_root;
2668         struct ocfs2_dir_entry *de;
2669         struct ocfs2_dx_hinfo hinfo;
2670         u64 dirent_blk = dirent_bh->b_blocknr;
2671
2672         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
2673
2674         de_buf = dirent_bh->b_data;
2675         limit = de_buf + dir->i_sb->s_blocksize;
2676
2677         while (de_buf < limit) {
2678                 de = (struct ocfs2_dir_entry *)de_buf;
2679
2680                 if (!de->name_len || !de->inode)
2681                         goto inc;
2682
2683                 ocfs2_dx_dir_name_hash(dir, de->name, de->name_len, &hinfo);
2684
2685                 trace_ocfs2_dx_dir_index_root_block(
2686                                 (unsigned long long)dir->i_ino,
2687                                 hinfo.major_hash, hinfo.minor_hash,
2688                                 de->name_len, de->name,
2689                                 le16_to_cpu(dx_root->dr_entries.de_num_used));
2690
2691                 ocfs2_dx_entry_list_insert(&dx_root->dr_entries, &hinfo,
2692                                            dirent_blk);
2693
2694                 le32_add_cpu(&dx_root->dr_num_entries, 1);
2695 inc:
2696                 de_buf += le16_to_cpu(de->rec_len);
2697         }
2698 }
2699
2700 /*
2701  * Count the number of inline directory entries in di_bh and compare
2702  * them against the number of entries we can hold in an inline dx root
2703  * block.
2704  */
2705 static int ocfs2_new_dx_should_be_inline(struct inode *dir,
2706                                          struct buffer_head *di_bh)
2707 {
2708         int dirent_count = 0;
2709         char *de_buf, *limit;
2710         struct ocfs2_dir_entry *de;
2711         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
2712
2713         de_buf = di->id2.i_data.id_data;
2714         limit = de_buf + i_size_read(dir);
2715
2716         while (de_buf < limit) {
2717                 de = (struct ocfs2_dir_entry *)de_buf;
2718
2719                 if (de->name_len && de->inode)
2720                         dirent_count++;
2721
2722                 de_buf += le16_to_cpu(de->rec_len);
2723         }
2724
2725         /* We are careful to leave room for one extra record. */
2726         return dirent_count < ocfs2_dx_entries_per_root(dir->i_sb);
2727 }
2728
2729 /*
2730  * Expand rec_len of the rightmost dirent in a directory block so that it
2731  * contains the end of our valid space for dirents. We do this during
2732  * expansion from an inline directory to one with extents. The first dir block
2733  * in that case is taken from the inline data portion of the inode block.
2734  *
2735  * This will also return the largest amount of contiguous space for a dirent
2736  * in the block. That value is *not* necessarily the last dirent, even after
2737  * expansion. The directory indexing code wants this value for free space
2738  * accounting. We do this here since we're already walking the entire dir
2739  * block.
2740  *
2741  * We add the dir trailer if this filesystem wants it.
2742  */
2743 static unsigned int ocfs2_expand_last_dirent(char *start, unsigned int old_size,
2744                                              struct inode *dir)
2745 {
2746         struct super_block *sb = dir->i_sb;
2747         struct ocfs2_dir_entry *de;
2748         struct ocfs2_dir_entry *prev_de;
2749         char *de_buf, *limit;
2750         unsigned int new_size = sb->s_blocksize;
2751         unsigned int bytes, this_hole;
2752         unsigned int largest_hole = 0;
2753
2754         if (ocfs2_new_dir_wants_trailer(dir))
2755                 new_size = ocfs2_dir_trailer_blk_off(sb);
2756
2757         bytes = new_size - old_size;
2758
2759         limit = start + old_size;
2760         de_buf = start;
2761         de = (struct ocfs2_dir_entry *)de_buf;
2762         do {
2763                 this_hole = ocfs2_figure_dirent_hole(de);
2764                 if (this_hole > largest_hole)
2765                         largest_hole = this_hole;
2766
2767                 prev_de = de;
2768                 de_buf += le16_to_cpu(de->rec_len);
2769                 de = (struct ocfs2_dir_entry *)de_buf;
2770         } while (de_buf < limit);
2771
2772         le16_add_cpu(&prev_de->rec_len, bytes);
2773
2774         /* We need to double check this after modification of the final
2775          * dirent. */
2776         this_hole = ocfs2_figure_dirent_hole(prev_de);
2777         if (this_hole > largest_hole)
2778                 largest_hole = this_hole;
2779
2780         if (largest_hole >= OCFS2_DIR_MIN_REC_LEN)
2781                 return largest_hole;
2782         return 0;
2783 }
2784
2785 /*
2786  * We allocate enough clusters to fulfill "blocks_wanted", but set
2787  * i_size to exactly one block. Ocfs2_extend_dir() will handle the
2788  * rest automatically for us.
2789  *
2790  * *first_block_bh is a pointer to the 1st data block allocated to the
2791  *  directory.
2792  */
2793 static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,
2794                                    unsigned int blocks_wanted,
2795                                    struct ocfs2_dir_lookup_result *lookup,
2796                                    struct buffer_head **first_block_bh)
2797 {
2798         u32 alloc, dx_alloc, bit_off, len, num_dx_entries = 0;
2799         struct super_block *sb = dir->i_sb;
2800         int ret, i, num_dx_leaves = 0, dx_inline = 0,
2801                 credits = ocfs2_inline_to_extents_credits(sb);
2802         u64 dx_insert_blkno, blkno,
2803                 bytes = blocks_wanted << sb->s_blocksize_bits;
2804         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
2805         struct ocfs2_inode_info *oi = OCFS2_I(dir);
2806         struct ocfs2_alloc_context *data_ac = NULL;
2807         struct ocfs2_alloc_context *meta_ac = NULL;
2808         struct buffer_head *dirdata_bh = NULL;
2809         struct buffer_head *dx_root_bh = NULL;
2810         struct buffer_head **dx_leaves = NULL;
2811         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
2812         handle_t *handle;
2813         struct ocfs2_extent_tree et;
2814         struct ocfs2_extent_tree dx_et;
2815         int did_quota = 0, bytes_allocated = 0;
2816
2817         ocfs2_init_dinode_extent_tree(&et, INODE_CACHE(dir), di_bh);
2818
2819         alloc = ocfs2_clusters_for_bytes(sb, bytes);
2820         dx_alloc = 0;
2821
2822         down_write(&oi->ip_alloc_sem);
2823
2824         if (ocfs2_supports_indexed_dirs(osb)) {
2825                 credits += ocfs2_add_dir_index_credits(sb);
2826
2827                 dx_inline = ocfs2_new_dx_should_be_inline(dir, di_bh);
2828                 if (!dx_inline) {
2829                         /* Add one more cluster for an index leaf */
2830                         dx_alloc++;
2831                         dx_leaves = ocfs2_dx_dir_kmalloc_leaves(sb,
2832                                                                 &num_dx_leaves);
2833                         if (!dx_leaves) {
2834                                 ret = -ENOMEM;
2835                                 mlog_errno(ret);
2836                                 goto out;
2837                         }
2838                 }
2839
2840                 /* This gets us the dx_root */
2841                 ret = ocfs2_reserve_new_metadata_blocks(osb, 1, &meta_ac);
2842                 if (ret) {
2843                         mlog_errno(ret);
2844                         goto out;
2845                 }
2846         }
2847
2848         /*
2849          * We should never need more than 2 clusters for the unindexed
2850          * tree - maximum dirent size is far less than one block. In
2851          * fact, the only time we'd need more than one cluster is if
2852          * blocksize == clustersize and the dirent won't fit in the
2853          * extra space that the expansion to a single block gives. As
2854          * of today, that only happens on 4k/4k file systems.
2855          */
2856         BUG_ON(alloc > 2);
2857
2858         ret = ocfs2_reserve_clusters(osb, alloc + dx_alloc, &data_ac);
2859         if (ret) {
2860                 mlog_errno(ret);
2861                 goto out;
2862         }
2863
2864         /*
2865          * Prepare for worst case allocation scenario of two separate
2866          * extents in the unindexed tree.
2867          */
2868         if (alloc == 2)
2869                 credits += OCFS2_SUBALLOC_ALLOC;
2870
2871         handle = ocfs2_start_trans(osb, credits);
2872         if (IS_ERR(handle)) {
2873                 ret = PTR_ERR(handle);
2874                 mlog_errno(ret);
2875                 goto out;
2876         }
2877
2878         ret = dquot_alloc_space_nodirty(dir,
2879                 ocfs2_clusters_to_bytes(osb->sb, alloc + dx_alloc));
2880         if (ret)
2881                 goto out_commit;
2882         did_quota = 1;
2883
2884         if (ocfs2_supports_indexed_dirs(osb) && !dx_inline) {
2885                 /*
2886                  * Allocate our index cluster first, to maximize the
2887                  * possibility that unindexed leaves grow
2888                  * contiguously.
2889                  */
2890                 ret = __ocfs2_dx_dir_new_cluster(dir, 0, handle, data_ac,
2891                                                  dx_leaves, num_dx_leaves,
2892                                                  &dx_insert_blkno);
2893                 if (ret) {
2894                         mlog_errno(ret);
2895                         goto out_commit;
2896                 }
2897                 bytes_allocated += ocfs2_clusters_to_bytes(dir->i_sb, 1);
2898         }
2899
2900         /*
2901          * Try to claim as many clusters as the bitmap can give though
2902          * if we only get one now, that's enough to continue. The rest
2903          * will be claimed after the conversion to extents.
2904          */
2905         if (ocfs2_dir_resv_allowed(osb))
2906                 data_ac->ac_resv = &oi->ip_la_data_resv;
2907         ret = ocfs2_claim_clusters(handle, data_ac, 1, &bit_off, &len);
2908         if (ret) {
2909                 mlog_errno(ret);
2910                 goto out_commit;
2911         }
2912         bytes_allocated += ocfs2_clusters_to_bytes(dir->i_sb, 1);
2913
2914         /*
2915          * Operations are carefully ordered so that we set up the new
2916          * data block first. The conversion from inline data to
2917          * extents follows.
2918          */
2919         blkno = ocfs2_clusters_to_blocks(dir->i_sb, bit_off);
2920         dirdata_bh = sb_getblk(sb, blkno);
2921         if (!dirdata_bh) {
2922                 ret = -ENOMEM;
2923                 mlog_errno(ret);
2924                 goto out_commit;
2925         }
2926
2927         ocfs2_set_new_buffer_uptodate(INODE_CACHE(dir), dirdata_bh);
2928
2929         ret = ocfs2_journal_access_db(handle, INODE_CACHE(dir), dirdata_bh,
2930                                       OCFS2_JOURNAL_ACCESS_CREATE);
2931         if (ret) {
2932                 mlog_errno(ret);
2933                 goto out_commit;
2934         }
2935
2936         memcpy(dirdata_bh->b_data, di->id2.i_data.id_data, i_size_read(dir));
2937         memset(dirdata_bh->b_data + i_size_read(dir), 0,
2938                sb->s_blocksize - i_size_read(dir));
2939         i = ocfs2_expand_last_dirent(dirdata_bh->b_data, i_size_read(dir), dir);
2940         if (ocfs2_new_dir_wants_trailer(dir)) {
2941                 /*
2942                  * Prepare the dir trailer up front. It will otherwise look
2943                  * like a valid dirent. Even if inserting the index fails
2944                  * (unlikely), then all we'll have done is given first dir
2945                  * block a small amount of fragmentation.
2946                  */
2947                 ocfs2_init_dir_trailer(dir, dirdata_bh, i);
2948         }
2949
2950         ocfs2_update_inode_fsync_trans(handle, dir, 1);
2951         ocfs2_journal_dirty(handle, dirdata_bh);
2952
2953         if (ocfs2_supports_indexed_dirs(osb) && !dx_inline) {
2954                 /*
2955                  * Dx dirs with an external cluster need to do this up
2956                  * front. Inline dx root's get handled later, after
2957                  * we've allocated our root block. We get passed back
2958                  * a total number of items so that dr_num_entries can
2959                  * be correctly set once the dx_root has been
2960                  * allocated.
2961                  */
2962                 ret = ocfs2_dx_dir_index_block(dir, handle, dx_leaves,
2963                                                num_dx_leaves, &num_dx_entries,
2964                                                dirdata_bh);
2965                 if (ret) {
2966                         mlog_errno(ret);
2967                         goto out_commit;
2968                 }
2969         }
2970
2971         /*
2972          * Set extent, i_size, etc on the directory. After this, the
2973          * inode should contain the same exact dirents as before and
2974          * be fully accessible from system calls.
2975          *
2976          * We let the later dirent insert modify c/mtime - to the user
2977          * the data hasn't changed.
2978          */
2979         ret = ocfs2_journal_access_di(handle, INODE_CACHE(dir), di_bh,
2980                                       OCFS2_JOURNAL_ACCESS_CREATE);
2981         if (ret) {
2982                 mlog_errno(ret);
2983                 goto out_commit;
2984         }
2985
2986         spin_lock(&oi->ip_lock);
2987         oi->ip_dyn_features &= ~OCFS2_INLINE_DATA_FL;
2988         di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features);
2989         spin_unlock(&oi->ip_lock);
2990
2991         ocfs2_dinode_new_extent_list(dir, di);
2992
2993         i_size_write(dir, sb->s_blocksize);
2994         dir->i_mtime = dir->i_ctime = current_time(dir);
2995
2996         di->i_size = cpu_to_le64(sb->s_blocksize);
2997         di->i_ctime = di->i_mtime = cpu_to_le64(dir->i_ctime.tv_sec);
2998         di->i_ctime_nsec = di->i_mtime_nsec = cpu_to_le32(dir->i_ctime.tv_nsec);
2999         ocfs2_update_inode_fsync_trans(handle, dir, 1);
3000
3001         /*
3002          * This should never fail as our extent list is empty and all
3003          * related blocks have been journaled already.
3004          */
3005         ret = ocfs2_insert_extent(handle, &et, 0, blkno, len,
3006                                   0, NULL);
3007         if (ret) {
3008                 mlog_errno(ret);
3009                 goto out_commit;
3010         }
3011
3012         /*
3013          * Set i_blocks after the extent insert for the most up to
3014          * date ip_clusters value.
3015          */
3016         dir->i_blocks = ocfs2_inode_sector_count(dir);
3017
3018         ocfs2_journal_dirty(handle, di_bh);
3019
3020         if (ocfs2_supports_indexed_dirs(osb)) {
3021                 ret = ocfs2_dx_dir_attach_index(osb, handle, dir, di_bh,
3022                                                 dirdata_bh, meta_ac, dx_inline,
3023                                                 num_dx_entries, &dx_root_bh);
3024                 if (ret) {
3025                         mlog_errno(ret);
3026                         goto out_commit;
3027                 }
3028
3029                 if (dx_inline) {
3030                         ocfs2_dx_dir_index_root_block(dir, dx_root_bh,
3031                                                       dirdata_bh);
3032                 } else {
3033                         ocfs2_init_dx_root_extent_tree(&dx_et,
3034                                                        INODE_CACHE(dir),
3035                                                        dx_root_bh);
3036                         ret = ocfs2_insert_extent(handle, &dx_et, 0,
3037                                                   dx_insert_blkno, 1, 0, NULL);
3038                         if (ret)
3039                                 mlog_errno(ret);
3040                 }
3041         }
3042
3043         /*
3044          * We asked for two clusters, but only got one in the 1st
3045          * pass. Claim the 2nd cluster as a separate extent.
3046          */
3047         if (alloc > len) {
3048                 ret = ocfs2_claim_clusters(handle, data_ac, 1, &bit_off,
3049                                            &len);
3050                 if (ret) {
3051                         mlog_errno(ret);
3052                         goto out_commit;
3053                 }
3054                 blkno = ocfs2_clusters_to_blocks(dir->i_sb, bit_off);
3055
3056                 ret = ocfs2_insert_extent(handle, &et, 1,
3057                                           blkno, len, 0, NULL);
3058                 if (ret) {
3059                         mlog_errno(ret);
3060                         goto out_commit;
3061                 }
3062                 bytes_allocated += ocfs2_clusters_to_bytes(dir->i_sb, 1);
3063         }
3064
3065         *first_block_bh = dirdata_bh;
3066         dirdata_bh = NULL;
3067         if (ocfs2_supports_indexed_dirs(osb)) {
3068                 unsigned int off;
3069
3070                 if (!dx_inline) {
3071                         /*
3072                          * We need to return the correct block within the
3073                          * cluster which should hold our entry.
3074                          */
3075                         off = ocfs2_dx_dir_hash_idx(osb,
3076                                                     &lookup->dl_hinfo);
3077                         get_bh(dx_leaves[off]);
3078                         lookup->dl_dx_leaf_bh = dx_leaves[off];
3079                 }
3080                 lookup->dl_dx_root_bh = dx_root_bh;
3081                 dx_root_bh = NULL;
3082         }
3083
3084 out_commit:
3085         if (ret < 0 && did_quota)
3086                 dquot_free_space_nodirty(dir, bytes_allocated);
3087
3088         ocfs2_commit_trans(osb, handle);
3089
3090 out:
3091         up_write(&oi->ip_alloc_sem);
3092         if (data_ac)
3093                 ocfs2_free_alloc_context(data_ac);
3094         if (meta_ac)
3095                 ocfs2_free_alloc_context(meta_ac);
3096
3097         if (dx_leaves) {
3098                 for (i = 0; i < num_dx_leaves; i++)
3099                         brelse(dx_leaves[i]);
3100                 kfree(dx_leaves);
3101         }
3102
3103         brelse(dirdata_bh);
3104         brelse(dx_root_bh);
3105
3106         return ret;
3107 }
3108
3109 /* returns a bh of the 1st new block in the allocation. */
3110 static int ocfs2_do_extend_dir(struct super_block *sb,
3111                                handle_t *handle,
3112                                struct inode *dir,
3113                                struct buffer_head *parent_fe_bh,
3114                                struct ocfs2_alloc_context *data_ac,
3115                                struct ocfs2_alloc_context *meta_ac,
3116                                struct buffer_head **new_bh)
3117 {
3118         int status;
3119         int extend, did_quota = 0;
3120         u64 p_blkno, v_blkno;
3121
3122         spin_lock(&OCFS2_I(dir)->ip_lock);
3123         extend = (i_size_read(dir) == ocfs2_clusters_to_bytes(sb, OCFS2_I(dir)->ip_clusters));
3124         spin_unlock(&OCFS2_I(dir)->ip_lock);
3125
3126         if (extend) {
3127                 u32 offset = OCFS2_I(dir)->ip_clusters;
3128
3129                 status = dquot_alloc_space_nodirty(dir,
3130                                         ocfs2_clusters_to_bytes(sb, 1));
3131                 if (status)
3132                         goto bail;
3133                 did_quota = 1;
3134
3135                 status = ocfs2_add_inode_data(OCFS2_SB(sb), dir, &offset,
3136                                               1, 0, parent_fe_bh, handle,
3137                                               data_ac, meta_ac, NULL);
3138                 BUG_ON(status == -EAGAIN);
3139                 if (status < 0) {
3140                         mlog_errno(status);
3141                         goto bail;
3142                 }
3143         }
3144
3145         v_blkno = ocfs2_blocks_for_bytes(sb, i_size_read(dir));
3146         status = ocfs2_extent_map_get_blocks(dir, v_blkno, &p_blkno, NULL, NULL);
3147         if (status < 0) {
3148                 mlog_errno(status);
3149                 goto bail;
3150         }
3151
3152         *new_bh = sb_getblk(sb, p_blkno);
3153         if (!*new_bh) {
3154                 status = -ENOMEM;
3155                 mlog_errno(status);
3156                 goto bail;
3157         }
3158         status = 0;
3159 bail:
3160         if (did_quota && status < 0)
3161                 dquot_free_space_nodirty(dir, ocfs2_clusters_to_bytes(sb, 1));
3162         return status;
3163 }
3164
3165 /*
3166  * Assumes you already have a cluster lock on the directory.
3167  *
3168  * 'blocks_wanted' is only used if we have an inline directory which
3169  * is to be turned into an extent based one. The size of the dirent to
3170  * insert might be larger than the space gained by growing to just one
3171  * block, so we may have to grow the inode by two blocks in that case.
3172  *
3173  * If the directory is already indexed, dx_root_bh must be provided.
3174  */
3175 static int ocfs2_extend_dir(struct ocfs2_super *osb,
3176                             struct inode *dir,
3177                             struct buffer_head *parent_fe_bh,
3178                             unsigned int blocks_wanted,
3179                             struct ocfs2_dir_lookup_result *lookup,
3180                             struct buffer_head **new_de_bh)
3181 {
3182         int status = 0;
3183         int credits, num_free_extents, drop_alloc_sem = 0;
3184         loff_t dir_i_size;
3185         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) parent_fe_bh->b_data;
3186         struct ocfs2_extent_list *el = &fe->id2.i_list;
3187         struct ocfs2_alloc_context *data_ac = NULL;
3188         struct ocfs2_alloc_context *meta_ac = NULL;
3189         handle_t *handle = NULL;
3190         struct buffer_head *new_bh = NULL;
3191         struct ocfs2_dir_entry * de;
3192         struct super_block *sb = osb->sb;
3193         struct ocfs2_extent_tree et;
3194         struct buffer_head *dx_root_bh = lookup->dl_dx_root_bh;
3195
3196         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {
3197                 /*
3198                  * This would be a code error as an inline directory should
3199                  * never have an index root.
3200                  */
3201                 BUG_ON(dx_root_bh);
3202
3203                 status = ocfs2_expand_inline_dir(dir, parent_fe_bh,
3204                                                  blocks_wanted, lookup,
3205                                                  &new_bh);
3206                 if (status) {
3207                         mlog_errno(status);
3208                         goto bail;
3209                 }
3210
3211                 /* Expansion from inline to an indexed directory will
3212                  * have given us this. */
3213                 dx_root_bh = lookup->dl_dx_root_bh;
3214
3215                 if (blocks_wanted == 1) {
3216                         /*
3217                          * If the new dirent will fit inside the space
3218                          * created by pushing out to one block, then
3219                          * we can complete the operation
3220                          * here. Otherwise we have to expand i_size
3221                          * and format the 2nd block below.
3222                          */
3223                         BUG_ON(new_bh == NULL);
3224                         goto bail_bh;
3225                 }
3226
3227                 /*
3228                  * Get rid of 'new_bh' - we want to format the 2nd
3229                  * data block and return that instead.
3230                  */
3231                 brelse(new_bh);
3232                 new_bh = NULL;
3233
3234                 down_write(&OCFS2_I(dir)->ip_alloc_sem);
3235                 drop_alloc_sem = 1;
3236                 dir_i_size = i_size_read(dir);
3237                 credits = OCFS2_SIMPLE_DIR_EXTEND_CREDITS;
3238                 goto do_extend;
3239         }
3240
3241         down_write(&OCFS2_I(dir)->ip_alloc_sem);
3242         drop_alloc_sem = 1;
3243         dir_i_size = i_size_read(dir);
3244         trace_ocfs2_extend_dir((unsigned long long)OCFS2_I(dir)->ip_blkno,
3245                                dir_i_size);
3246
3247         /* dir->i_size is always block aligned. */
3248         spin_lock(&OCFS2_I(dir)->ip_lock);
3249         if (dir_i_size == ocfs2_clusters_to_bytes(sb, OCFS2_I(dir)->ip_clusters)) {
3250                 spin_unlock(&OCFS2_I(dir)->ip_lock);
3251                 ocfs2_init_dinode_extent_tree(&et, INODE_CACHE(dir),
3252                                               parent_fe_bh);
3253                 num_free_extents = ocfs2_num_free_extents(&et);
3254                 if (num_free_extents < 0) {
3255                         status = num_free_extents;
3256                         mlog_errno(status);
3257                         goto bail;
3258                 }
3259
3260                 if (!num_free_extents) {
3261                         status = ocfs2_reserve_new_metadata(osb, el, &meta_ac);
3262                         if (status < 0) {
3263                                 if (status != -ENOSPC)
3264                                         mlog_errno(status);
3265                                 goto bail;
3266                         }
3267                 }
3268
3269                 status = ocfs2_reserve_clusters(osb, 1, &data_ac);
3270                 if (status < 0) {
3271                         if (status != -ENOSPC)
3272                                 mlog_errno(status);
3273                         goto bail;
3274                 }
3275
3276                 if (ocfs2_dir_resv_allowed(osb))
3277                         data_ac->ac_resv = &OCFS2_I(dir)->ip_la_data_resv;
3278
3279                 credits = ocfs2_calc_extend_credits(sb, el);
3280         } else {
3281                 spin_unlock(&OCFS2_I(dir)->ip_lock);
3282                 credits = OCFS2_SIMPLE_DIR_EXTEND_CREDITS;
3283         }
3284
3285 do_extend:
3286         if (ocfs2_dir_indexed(dir))
3287                 credits++; /* For attaching the new dirent block to the
3288                             * dx_root */
3289
3290         handle = ocfs2_start_trans(osb, credits);
3291         if (IS_ERR(handle)) {
3292                 status = PTR_ERR(handle);
3293                 handle = NULL;
3294                 mlog_errno(status);
3295                 goto bail;
3296         }
3297
3298         status = ocfs2_do_extend_dir(osb->sb, handle, dir, parent_fe_bh,
3299                                      data_ac, meta_ac, &new_bh);
3300         if (status < 0) {
3301                 mlog_errno(status);
3302                 goto bail;
3303         }
3304
3305         ocfs2_set_new_buffer_uptodate(INODE_CACHE(dir), new_bh);
3306
3307         status = ocfs2_journal_access_db(handle, INODE_CACHE(dir), new_bh,
3308                                          OCFS2_JOURNAL_ACCESS_CREATE);
3309         if (status < 0) {
3310                 mlog_errno(status);
3311                 goto bail;
3312         }
3313         memset(new_bh->b_data, 0, sb->s_blocksize);
3314
3315         de = (struct ocfs2_dir_entry *) new_bh->b_data;
3316         de->inode = 0;
3317         if (ocfs2_supports_dir_trailer(dir)) {
3318                 de->rec_len = cpu_to_le16(ocfs2_dir_trailer_blk_off(sb));
3319
3320                 ocfs2_init_dir_trailer(dir, new_bh, le16_to_cpu(de->rec_len));
3321
3322                 if (ocfs2_dir_indexed(dir)) {
3323                         status = ocfs2_dx_dir_link_trailer(dir, handle,
3324                                                            dx_root_bh, new_bh);
3325                         if (status) {
3326                                 mlog_errno(status);
3327                                 goto bail;
3328                         }
3329                 }
3330         } else {
3331                 de->rec_len = cpu_to_le16(sb->s_blocksize);
3332         }
3333         ocfs2_update_inode_fsync_trans(handle, dir, 1);
3334         ocfs2_journal_dirty(handle, new_bh);
3335
3336         dir_i_size += dir->i_sb->s_blocksize;
3337         i_size_write(dir, dir_i_size);
3338         dir->i_blocks = ocfs2_inode_sector_count(dir);
3339         status = ocfs2_mark_inode_dirty(handle, dir, parent_fe_bh);
3340         if (status < 0) {
3341                 mlog_errno(status);
3342                 goto bail;
3343         }
3344
3345 bail_bh:
3346         *new_de_bh = new_bh;
3347         get_bh(*new_de_bh);
3348 bail:
3349         if (handle)
3350                 ocfs2_commit_trans(osb, handle);
3351         if (drop_alloc_sem)
3352                 up_write(&OCFS2_I(dir)->ip_alloc_sem);
3353
3354         if (data_ac)
3355                 ocfs2_free_alloc_context(data_ac);
3356         if (meta_ac)
3357                 ocfs2_free_alloc_context(meta_ac);
3358
3359         brelse(new_bh);
3360
3361         return status;
3362 }
3363
3364 static int ocfs2_find_dir_space_id(struct inode *dir, struct buffer_head *di_bh,
3365                                    const char *name, int namelen,
3366                                    struct buffer_head **ret_de_bh,
3367                                    unsigned int *blocks_wanted)
3368 {
3369         int ret;
3370         struct super_block *sb = dir->i_sb;
3371         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
3372         struct ocfs2_dir_entry *de, *last_de = NULL;
3373         char *de_buf, *limit;
3374         unsigned long offset = 0;
3375         unsigned int rec_len, new_rec_len, free_space = dir->i_sb->s_blocksize;
3376
3377         /*
3378          * This calculates how many free bytes we'd have in block zero, should
3379          * this function force expansion to an extent tree.
3380          */
3381         if (ocfs2_new_dir_wants_trailer(dir))
3382                 free_space = ocfs2_dir_trailer_blk_off(sb) - i_size_read(dir);
3383         else
3384                 free_space = dir->i_sb->s_blocksize - i_size_read(dir);
3385
3386         de_buf = di->id2.i_data.id_data;
3387         limit = de_buf + i_size_read(dir);
3388         rec_len = OCFS2_DIR_REC_LEN(namelen);
3389
3390         while (de_buf < limit) {
3391                 de = (struct ocfs2_dir_entry *)de_buf;
3392
3393                 if (!ocfs2_check_dir_entry(dir, de, di_bh, offset)) {
3394                         ret = -ENOENT;
3395                         goto out;
3396                 }
3397                 if (ocfs2_match(namelen, name, de)) {
3398                         ret = -EEXIST;
3399                         goto out;
3400                 }
3401                 /*
3402                  * No need to check for a trailing dirent record here as
3403                  * they're not used for inline dirs.
3404                  */
3405
3406                 if (ocfs2_dirent_would_fit(de, rec_len)) {
3407                         /* Ok, we found a spot. Return this bh and let
3408                          * the caller actually fill it in. */
3409                         *ret_de_bh = di_bh;
3410                         get_bh(*ret_de_bh);
3411                         ret = 0;
3412                         goto out;
3413                 }
3414
3415                 last_de = de;
3416                 de_buf += le16_to_cpu(de->rec_len);
3417                 offset += le16_to_cpu(de->rec_len);
3418         }
3419
3420         /*
3421          * We're going to require expansion of the directory - figure
3422          * out how many blocks we'll need so that a place for the
3423          * dirent can be found.
3424          */
3425         *blocks_wanted = 1;
3426         new_rec_len = le16_to_cpu(last_de->rec_len) + free_space;
3427         if (new_rec_len < (rec_len + OCFS2_DIR_REC_LEN(last_de->name_len)))
3428                 *blocks_wanted = 2;
3429
3430         ret = -ENOSPC;
3431 out:
3432         return ret;
3433 }
3434
3435 static int ocfs2_find_dir_space_el(struct inode *dir, const char *name,
3436                                    int namelen, struct buffer_head **ret_de_bh)
3437 {
3438         unsigned long offset;
3439         struct buffer_head *bh = NULL;
3440         unsigned short rec_len;
3441         struct ocfs2_dir_entry *de;
3442         struct super_block *sb = dir->i_sb;
3443         int status;
3444         int blocksize = dir->i_sb->s_blocksize;
3445
3446         status = ocfs2_read_dir_block(dir, 0, &bh, 0);
3447         if (status)
3448                 goto bail;
3449
3450         rec_len = OCFS2_DIR_REC_LEN(namelen);
3451         offset = 0;
3452         de = (struct ocfs2_dir_entry *) bh->b_data;
3453         while (1) {
3454                 if ((char *)de >= sb->s_blocksize + bh->b_data) {
3455                         brelse(bh);
3456                         bh = NULL;
3457
3458                         if (i_size_read(dir) <= offset) {
3459                                 /*
3460                                  * Caller will have to expand this
3461                                  * directory.
3462                                  */
3463                                 status = -ENOSPC;
3464                                 goto bail;
3465                         }
3466                         status = ocfs2_read_dir_block(dir,
3467                                              offset >> sb->s_blocksize_bits,
3468                                              &bh, 0);
3469                         if (status)
3470                                 goto bail;
3471
3472                         /* move to next block */
3473                         de = (struct ocfs2_dir_entry *) bh->b_data;
3474                 }
3475                 if (!ocfs2_check_dir_entry(dir, de, bh, offset)) {
3476                         status = -ENOENT;
3477                         goto bail;
3478                 }
3479                 if (ocfs2_match(namelen, name, de)) {
3480                         status = -EEXIST;
3481                         goto bail;
3482                 }
3483
3484                 if (ocfs2_skip_dir_trailer(dir, de, offset % blocksize,
3485                                            blocksize))
3486                         goto next;
3487
3488                 if (ocfs2_dirent_would_fit(de, rec_len)) {
3489                         /* Ok, we found a spot. Return this bh and let
3490                          * the caller actually fill it in. */
3491                         *ret_de_bh = bh;
3492                         get_bh(*ret_de_bh);
3493                         status = 0;
3494                         goto bail;
3495                 }
3496 next:
3497                 offset += le16_to_cpu(de->rec_len);
3498                 de = (struct ocfs2_dir_entry *)((char *) de + le16_to_cpu(de->rec_len));
3499         }
3500
3501 bail:
3502         brelse(bh);
3503         if (status)
3504                 mlog_errno(status);
3505
3506         return status;
3507 }
3508
3509 static int dx_leaf_sort_cmp(const void *a, const void *b)
3510 {
3511         const struct ocfs2_dx_entry *entry1 = a;
3512         const struct ocfs2_dx_entry *entry2 = b;
3513         u32 major_hash1 = le32_to_cpu(entry1->dx_major_hash);
3514         u32 major_hash2 = le32_to_cpu(entry2->dx_major_hash);
3515         u32 minor_hash1 = le32_to_cpu(entry1->dx_minor_hash);
3516         u32 minor_hash2 = le32_to_cpu(entry2->dx_minor_hash);
3517
3518         if (major_hash1 > major_hash2)
3519                 return 1;
3520         if (major_hash1 < major_hash2)
3521                 return -1;
3522
3523         /*
3524          * It is not strictly necessary to sort by minor
3525          */
3526         if (minor_hash1 > minor_hash2)
3527                 return 1;
3528         if (minor_hash1 < minor_hash2)
3529                 return -1;
3530         return 0;
3531 }
3532
3533 static void dx_leaf_sort_swap(void *a, void *b, int size)
3534 {
3535         struct ocfs2_dx_entry *entry1 = a;
3536         struct ocfs2_dx_entry *entry2 = b;
3537
3538         BUG_ON(size != sizeof(*entry1));
3539
3540         swap(*entry1, *entry2);
3541 }
3542
3543 static int ocfs2_dx_leaf_same_major(struct ocfs2_dx_leaf *dx_leaf)
3544 {
3545         struct ocfs2_dx_entry_list *dl_list = &dx_leaf->dl_list;
3546         int i, num = le16_to_cpu(dl_list->de_num_used);
3547
3548         for (i = 0; i < (num - 1); i++) {
3549                 if (le32_to_cpu(dl_list->de_entries[i].dx_major_hash) !=
3550                     le32_to_cpu(dl_list->de_entries[i + 1].dx_major_hash))
3551                         return 0;
3552         }
3553
3554         return 1;
3555 }
3556
3557 /*
3558  * Find the optimal value to split this leaf on. This expects the leaf
3559  * entries to be in sorted order.
3560  *
3561  * leaf_cpos is the cpos of the leaf we're splitting. insert_hash is
3562  * the hash we want to insert.
3563  *
3564  * This function is only concerned with the major hash - that which
3565  * determines which cluster an item belongs to.
3566  */
3567 static int ocfs2_dx_dir_find_leaf_split(struct ocfs2_dx_leaf *dx_leaf,
3568                                         u32 leaf_cpos, u32 insert_hash,
3569                                         u32 *split_hash)
3570 {
3571         struct ocfs2_dx_entry_list *dl_list = &dx_leaf->dl_list;
3572         int i, num_used = le16_to_cpu(dl_list->de_num_used);
3573         int allsame;
3574
3575         /*
3576          * There's a couple rare, but nasty corner cases we have to
3577          * check for here. All of them involve a leaf where all value
3578          * have the same hash, which is what we look for first.
3579          *
3580          * Most of the time, all of the above is false, and we simply
3581          * pick the median value for a split.
3582          */
3583         allsame = ocfs2_dx_leaf_same_major(dx_leaf);
3584         if (allsame) {
3585                 u32 val = le32_to_cpu(dl_list->de_entries[0].dx_major_hash);
3586
3587                 if (val == insert_hash) {
3588                         /*
3589                          * No matter where we would choose to split,
3590                          * the new entry would want to occupy the same
3591                          * block as these. Since there's no space left
3592                          * in their existing block, we know there
3593                          * won't be space after the split.
3594                          */
3595                         return -ENOSPC;
3596                 }
3597
3598                 if (val == leaf_cpos) {
3599                         /*
3600                          * Because val is the same as leaf_cpos (which
3601                          * is the smallest value this leaf can have),
3602                          * yet is not equal to insert_hash, then we
3603                          * know that insert_hash *must* be larger than
3604                          * val (and leaf_cpos). At least cpos+1 in value.
3605                          *
3606                          * We also know then, that there cannot be an
3607                          * adjacent extent (otherwise we'd be looking
3608                          * at it). Choosing this value gives us a
3609                          * chance to get some contiguousness.
3610                          */
3611                         *split_hash = leaf_cpos + 1;
3612                         return 0;
3613                 }
3614
3615                 if (val > insert_hash) {
3616                         /*
3617                          * val can not be the same as insert hash, and
3618                          * also must be larger than leaf_cpos. Also,
3619                          * we know that there can't be a leaf between
3620                          * cpos and val, otherwise the entries with
3621                          * hash 'val' would be there.
3622                          */
3623                         *split_hash = val;
3624                         return 0;
3625                 }
3626
3627                 *split_hash = insert_hash;
3628                 return 0;
3629         }
3630
3631         /*
3632          * Since the records are sorted and the checks above
3633          * guaranteed that not all records in this block are the same,
3634          * we simple travel forward, from the median, and pick the 1st
3635          * record whose value is larger than leaf_cpos.
3636          */
3637         for (i = (num_used / 2); i < num_used; i++)
3638                 if (le32_to_cpu(dl_list->de_entries[i].dx_major_hash) >
3639                     leaf_cpos)
3640                         break;
3641
3642         BUG_ON(i == num_used); /* Should be impossible */
3643         *split_hash = le32_to_cpu(dl_list->de_entries[i].dx_major_hash);
3644         return 0;
3645 }
3646
3647 /*
3648  * Transfer all entries in orig_dx_leaves whose major hash is equal to or
3649  * larger than split_hash into new_dx_leaves. We use a temporary
3650  * buffer (tmp_dx_leaf) to make the changes to the original leaf blocks.
3651  *
3652  * Since the block offset inside a leaf (cluster) is a constant mask
3653  * of minor_hash, we can optimize - an item at block offset X within
3654  * the original cluster, will be at offset X within the new cluster.
3655  */
3656 static void ocfs2_dx_dir_transfer_leaf(struct inode *dir, u32 split_hash,
3657                                        handle_t *handle,
3658                                        struct ocfs2_dx_leaf *tmp_dx_leaf,
3659                                        struct buffer_head **orig_dx_leaves,
3660                                        struct buffer_head **new_dx_leaves,
3661                                        int num_dx_leaves)
3662 {
3663         int i, j, num_used;
3664         u32 major_hash;
3665         struct ocfs2_dx_leaf *orig_dx_leaf, *new_dx_leaf;
3666         struct ocfs2_dx_entry_list *orig_list, *new_list, *tmp_list;
3667         struct ocfs2_dx_entry *dx_entry;
3668
3669         tmp_list = &tmp_dx_leaf->dl_list;
3670
3671         for (i = 0; i < num_dx_leaves; i++) {
3672                 orig_dx_leaf = (struct ocfs2_dx_leaf *) orig_dx_leaves[i]->b_data;
3673                 orig_list = &orig_dx_leaf->dl_list;
3674                 new_dx_leaf = (struct ocfs2_dx_leaf *) new_dx_leaves[i]->b_data;
3675                 new_list = &new_dx_leaf->dl_list;
3676
3677                 num_used = le16_to_cpu(orig_list->de_num_used);
3678
3679                 memcpy(tmp_dx_leaf, orig_dx_leaf, dir->i_sb->s_blocksize);
3680                 tmp_list->de_num_used = cpu_to_le16(0);
3681                 memset(&tmp_list->de_entries, 0, sizeof(*dx_entry)*num_used);
3682
3683                 for (j = 0; j < num_used; j++) {
3684                         dx_entry = &orig_list->de_entries[j];
3685                         major_hash = le32_to_cpu(dx_entry->dx_major_hash);
3686                         if (major_hash >= split_hash)
3687                                 ocfs2_dx_dir_leaf_insert_tail(new_dx_leaf,
3688                                                               dx_entry);
3689                         else
3690                                 ocfs2_dx_dir_leaf_insert_tail(tmp_dx_leaf,
3691                                                               dx_entry);
3692                 }
3693                 memcpy(orig_dx_leaf, tmp_dx_leaf, dir->i_sb->s_blocksize);
3694
3695                 ocfs2_journal_dirty(handle, orig_dx_leaves[i]);
3696                 ocfs2_journal_dirty(handle, new_dx_leaves[i]);
3697         }
3698 }
3699
3700 static int ocfs2_dx_dir_rebalance_credits(struct ocfs2_super *osb,
3701                                           struct ocfs2_dx_root_block *dx_root)
3702 {
3703         int credits = ocfs2_clusters_to_blocks(osb->sb, 3);
3704
3705         credits += ocfs2_calc_extend_credits(osb->sb, &dx_root->dr_list);
3706         credits += ocfs2_quota_trans_credits(osb->sb);
3707         return credits;
3708 }
3709
3710 /*
3711  * Find the median value in dx_leaf_bh and allocate a new leaf to move
3712  * half our entries into.
3713  */
3714 static int ocfs2_dx_dir_rebalance(struct ocfs2_super *osb, struct inode *dir,
3715                                   struct buffer_head *dx_root_bh,
3716                                   struct buffer_head *dx_leaf_bh,
3717                                   struct ocfs2_dx_hinfo *hinfo, u32 leaf_cpos,
3718                                   u64 leaf_blkno)
3719 {
3720         struct ocfs2_dx_leaf *dx_leaf = (struct ocfs2_dx_leaf *)dx_leaf_bh->b_data;
3721         int credits, ret, i, num_used, did_quota = 0;
3722         u32 cpos, split_hash, insert_hash = hinfo->major_hash;
3723         u64 orig_leaves_start;
3724         int num_dx_leaves;
3725         struct buffer_head **orig_dx_leaves = NULL;
3726         struct buffer_head **new_dx_leaves = NULL;
3727         struct ocfs2_alloc_context *data_ac = NULL, *meta_ac = NULL;
3728         struct ocfs2_extent_tree et;
3729         handle_t *handle = NULL;
3730         struct ocfs2_dx_root_block *dx_root;
3731         struct ocfs2_dx_leaf *tmp_dx_leaf = NULL;
3732
3733         trace_ocfs2_dx_dir_rebalance((unsigned long long)OCFS2_I(dir)->ip_blkno,
3734                                      (unsigned long long)leaf_blkno,
3735                                      insert_hash);
3736
3737         ocfs2_init_dx_root_extent_tree(&et, INODE_CACHE(dir), dx_root_bh);
3738
3739         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
3740         /*
3741          * XXX: This is a rather large limit. We should use a more
3742          * realistic value.
3743          */
3744         if (le32_to_cpu(dx_root->dr_clusters) == UINT_MAX)
3745                 return -ENOSPC;
3746
3747         num_used = le16_to_cpu(dx_leaf->dl_list.de_num_used);
3748         if (num_used < le16_to_cpu(dx_leaf->dl_list.de_count)) {
3749                 mlog(ML_ERROR, "DX Dir: %llu, Asked to rebalance empty leaf: "
3750                      "%llu, %d\n", (unsigned long long)OCFS2_I(dir)->ip_blkno,
3751                      (unsigned long long)leaf_blkno, num_used);
3752                 ret = -EIO;
3753                 goto out;
3754         }
3755
3756         orig_dx_leaves = ocfs2_dx_dir_kmalloc_leaves(osb->sb, &num_dx_leaves);
3757         if (!orig_dx_leaves) {
3758                 ret = -ENOMEM;
3759                 mlog_errno(ret);
3760                 goto out;
3761         }
3762
3763         new_dx_leaves = ocfs2_dx_dir_kmalloc_leaves(osb->sb, NULL);
3764         if (!new_dx_leaves) {
3765                 ret = -ENOMEM;
3766                 mlog_errno(ret);
3767                 goto out;
3768         }
3769
3770         ret = ocfs2_lock_allocators(dir, &et, 1, 0, &data_ac, &meta_ac);
3771         if (ret) {
3772                 if (ret != -ENOSPC)
3773                         mlog_errno(ret);
3774                 goto out;
3775         }
3776
3777         credits = ocfs2_dx_dir_rebalance_credits(osb, dx_root);
3778         handle = ocfs2_start_trans(osb, credits);
3779         if (IS_ERR(handle)) {
3780                 ret = PTR_ERR(handle);
3781                 handle = NULL;
3782                 mlog_errno(ret);
3783                 goto out;
3784         }
3785
3786         ret = dquot_alloc_space_nodirty(dir,
3787                                        ocfs2_clusters_to_bytes(dir->i_sb, 1));
3788         if (ret)
3789                 goto out_commit;
3790         did_quota = 1;
3791
3792         ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir), dx_leaf_bh,
3793                                       OCFS2_JOURNAL_ACCESS_WRITE);
3794         if (ret) {
3795                 mlog_errno(ret);
3796                 goto out_commit;
3797         }
3798
3799         /*
3800          * This block is changing anyway, so we can sort it in place.
3801          */
3802         sort(dx_leaf->dl_list.de_entries, num_used,
3803              sizeof(struct ocfs2_dx_entry), dx_leaf_sort_cmp,
3804              dx_leaf_sort_swap);
3805
3806         ocfs2_journal_dirty(handle, dx_leaf_bh);
3807
3808         ret = ocfs2_dx_dir_find_leaf_split(dx_leaf, leaf_cpos, insert_hash,
3809                                            &split_hash);
3810         if (ret) {
3811                 mlog_errno(ret);
3812                 goto  out_commit;
3813         }
3814
3815         trace_ocfs2_dx_dir_rebalance_split(leaf_cpos, split_hash, insert_hash);
3816
3817         /*
3818          * We have to carefully order operations here. There are items
3819          * which want to be in the new cluster before insert, but in
3820          * order to put those items in the new cluster, we alter the
3821          * old cluster. A failure to insert gets nasty.
3822          *
3823          * So, start by reserving writes to the old
3824          * cluster. ocfs2_dx_dir_new_cluster will reserve writes on
3825          * the new cluster for us, before inserting it. The insert
3826          * won't happen if there's an error before that. Once the
3827          * insert is done then, we can transfer from one leaf into the
3828          * other without fear of hitting any error.
3829          */
3830
3831         /*
3832          * The leaf transfer wants some scratch space so that we don't
3833          * wind up doing a bunch of expensive memmove().
3834          */
3835         tmp_dx_leaf = kmalloc(osb->sb->s_blocksize, GFP_NOFS);
3836         if (!tmp_dx_leaf) {
3837                 ret = -ENOMEM;
3838                 mlog_errno(ret);
3839                 goto out_commit;
3840         }
3841
3842         orig_leaves_start = ocfs2_block_to_cluster_start(dir->i_sb, leaf_blkno);
3843         ret = ocfs2_read_dx_leaves(dir, orig_leaves_start, num_dx_leaves,
3844                                    orig_dx_leaves);
3845         if (ret) {
3846                 mlog_errno(ret);
3847                 goto out_commit;
3848         }
3849
3850         cpos = split_hash;
3851         ret = ocfs2_dx_dir_new_cluster(dir, &et, cpos, handle,
3852                                        data_ac, meta_ac, new_dx_leaves,
3853                                        num_dx_leaves);
3854         if (ret) {
3855                 mlog_errno(ret);
3856                 goto out_commit;
3857         }
3858
3859         for (i = 0; i < num_dx_leaves; i++) {
3860                 ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir),
3861                                               orig_dx_leaves[i],
3862                                               OCFS2_JOURNAL_ACCESS_WRITE);
3863                 if (ret) {
3864                         mlog_errno(ret);
3865                         goto out_commit;
3866                 }
3867
3868                 ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir),
3869                                               new_dx_leaves[i],
3870                                               OCFS2_JOURNAL_ACCESS_WRITE);
3871                 if (ret) {
3872                         mlog_errno(ret);
3873                         goto out_commit;
3874                 }
3875         }
3876
3877         ocfs2_dx_dir_transfer_leaf(dir, split_hash, handle, tmp_dx_leaf,
3878                                    orig_dx_leaves, new_dx_leaves, num_dx_leaves);
3879
3880 out_commit:
3881         if (ret < 0 && did_quota)
3882                 dquot_free_space_nodirty(dir,
3883                                 ocfs2_clusters_to_bytes(dir->i_sb, 1));
3884
3885         ocfs2_update_inode_fsync_trans(handle, dir, 1);
3886         ocfs2_commit_trans(osb, handle);
3887
3888 out:
3889         if (orig_dx_leaves || new_dx_leaves) {
3890                 for (i = 0; i < num_dx_leaves; i++) {
3891                         if (orig_dx_leaves)
3892                                 brelse(orig_dx_leaves[i]);
3893                         if (new_dx_leaves)
3894                                 brelse(new_dx_leaves[i]);
3895                 }
3896                 kfree(orig_dx_leaves);
3897                 kfree(new_dx_leaves);
3898         }
3899
3900         if (meta_ac)
3901                 ocfs2_free_alloc_context(meta_ac);
3902         if (data_ac)
3903                 ocfs2_free_alloc_context(data_ac);
3904
3905         kfree(tmp_dx_leaf);
3906         return ret;
3907 }
3908
3909 static int ocfs2_find_dir_space_dx(struct ocfs2_super *osb, struct inode *dir,
3910                                    struct buffer_head *di_bh,
3911                                    struct buffer_head *dx_root_bh,
3912                                    const char *name, int namelen,
3913                                    struct ocfs2_dir_lookup_result *lookup)
3914 {
3915         int ret, rebalanced = 0;
3916         struct ocfs2_dx_root_block *dx_root;
3917         struct buffer_head *dx_leaf_bh = NULL;
3918         struct ocfs2_dx_leaf *dx_leaf;
3919         u64 blkno;
3920         u32 leaf_cpos;
3921
3922         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
3923
3924 restart_search:
3925         ret = ocfs2_dx_dir_lookup(dir, &dx_root->dr_list, &lookup->dl_hinfo,
3926                                   &leaf_cpos, &blkno);
3927         if (ret) {
3928                 mlog_errno(ret);
3929                 goto out;
3930         }
3931
3932         ret = ocfs2_read_dx_leaf(dir, blkno, &dx_leaf_bh);
3933         if (ret) {
3934                 mlog_errno(ret);
3935                 goto out;
3936         }
3937
3938         dx_leaf = (struct ocfs2_dx_leaf *)dx_leaf_bh->b_data;
3939
3940         if (le16_to_cpu(dx_leaf->dl_list.de_num_used) >=
3941             le16_to_cpu(dx_leaf->dl_list.de_count)) {
3942                 if (rebalanced) {
3943                         /*
3944                          * Rebalancing should have provided us with
3945                          * space in an appropriate leaf.
3946                          *
3947                          * XXX: Is this an abnormal condition then?
3948                          * Should we print a message here?
3949                          */
3950                         ret = -ENOSPC;
3951                         goto out;
3952                 }
3953
3954                 ret = ocfs2_dx_dir_rebalance(osb, dir, dx_root_bh, dx_leaf_bh,
3955                                              &lookup->dl_hinfo, leaf_cpos,
3956                                              blkno);
3957                 if (ret) {
3958                         if (ret != -ENOSPC)
3959                                 mlog_errno(ret);
3960                         goto out;
3961                 }
3962
3963                 /*
3964                  * Restart the lookup. The rebalance might have
3965                  * changed which block our item fits into. Mark our
3966                  * progress, so we only execute this once.
3967                  */
3968                 brelse(dx_leaf_bh);
3969                 dx_leaf_bh = NULL;
3970                 rebalanced = 1;
3971                 goto restart_search;
3972         }
3973
3974         lookup->dl_dx_leaf_bh = dx_leaf_bh;
3975         dx_leaf_bh = NULL;
3976
3977 out:
3978         brelse(dx_leaf_bh);
3979         return ret;
3980 }
3981
3982 static int ocfs2_search_dx_free_list(struct inode *dir,
3983                                      struct buffer_head *dx_root_bh,
3984                                      int namelen,
3985                                      struct ocfs2_dir_lookup_result *lookup)
3986 {
3987         int ret = -ENOSPC;
3988         struct buffer_head *leaf_bh = NULL, *prev_leaf_bh = NULL;
3989         struct ocfs2_dir_block_trailer *db;
3990         u64 next_block;
3991         int rec_len = OCFS2_DIR_REC_LEN(namelen);
3992         struct ocfs2_dx_root_block *dx_root;
3993
3994         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
3995         next_block = le64_to_cpu(dx_root->dr_free_blk);
3996
3997         while (next_block) {
3998                 brelse(prev_leaf_bh);
3999                 prev_leaf_bh = leaf_bh;
4000                 leaf_bh = NULL;
4001
4002                 ret = ocfs2_read_dir_block_direct(dir, next_block, &leaf_bh);
4003                 if (ret) {
4004                         mlog_errno(ret);
4005                         goto out;
4006                 }
4007
4008                 db = ocfs2_trailer_from_bh(leaf_bh, dir->i_sb);
4009                 if (rec_len <= le16_to_cpu(db->db_free_rec_len)) {
4010                         lookup->dl_leaf_bh = leaf_bh;
4011                         lookup->dl_prev_leaf_bh = prev_leaf_bh;
4012                         leaf_bh = NULL;
4013                         prev_leaf_bh = NULL;
4014                         break;
4015                 }
4016
4017                 next_block = le64_to_cpu(db->db_free_next);
4018         }
4019
4020         if (!next_block)
4021                 ret = -ENOSPC;
4022
4023 out:
4024
4025         brelse(leaf_bh);
4026         brelse(prev_leaf_bh);
4027         return ret;
4028 }
4029
4030 static int ocfs2_expand_inline_dx_root(struct inode *dir,
4031                                        struct buffer_head *dx_root_bh)
4032 {
4033         int ret, num_dx_leaves, i, j, did_quota = 0;
4034         struct buffer_head **dx_leaves = NULL;
4035         struct ocfs2_extent_tree et;
4036         u64 insert_blkno;
4037         struct ocfs2_alloc_context *data_ac = NULL;
4038         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
4039         handle_t *handle = NULL;
4040         struct ocfs2_dx_root_block *dx_root;
4041         struct ocfs2_dx_entry_list *entry_list;
4042         struct ocfs2_dx_entry *dx_entry;
4043         struct ocfs2_dx_leaf *target_leaf;
4044
4045         ret = ocfs2_reserve_clusters(osb, 1, &data_ac);
4046         if (ret) {
4047                 mlog_errno(ret);
4048                 goto out;
4049         }
4050
4051         dx_leaves = ocfs2_dx_dir_kmalloc_leaves(osb->sb, &num_dx_leaves);
4052         if (!dx_leaves) {
4053                 ret = -ENOMEM;
4054                 mlog_errno(ret);
4055                 goto out;
4056         }
4057
4058         handle = ocfs2_start_trans(osb, ocfs2_calc_dxi_expand_credits(osb->sb));
4059         if (IS_ERR(handle)) {
4060                 ret = PTR_ERR(handle);
4061                 mlog_errno(ret);
4062                 goto out;
4063         }
4064
4065         ret = dquot_alloc_space_nodirty(dir,
4066                                        ocfs2_clusters_to_bytes(osb->sb, 1));
4067         if (ret)
4068                 goto out_commit;
4069         did_quota = 1;
4070
4071         /*
4072          * We do this up front, before the allocation, so that a
4073          * failure to add the dx_root_bh to the journal won't result
4074          * us losing clusters.
4075          */
4076         ret = ocfs2_journal_access_dr(handle, INODE_CACHE(dir), dx_root_bh,
4077                                       OCFS2_JOURNAL_ACCESS_WRITE);
4078         if (ret) {
4079                 mlog_errno(ret);
4080                 goto out_commit;
4081         }
4082
4083         ret = __ocfs2_dx_dir_new_cluster(dir, 0, handle, data_ac, dx_leaves,
4084                                          num_dx_leaves, &insert_blkno);
4085         if (ret) {
4086                 mlog_errno(ret);
4087                 goto out_commit;
4088         }
4089
4090         /*
4091          * Transfer the entries from our dx_root into the appropriate
4092          * block
4093          */
4094         dx_root = (struct ocfs2_dx_root_block *) dx_root_bh->b_data;
4095         entry_list = &dx_root->dr_entries;
4096
4097         for (i = 0; i < le16_to_cpu(entry_list->de_num_used); i++) {
4098                 dx_entry = &entry_list->de_entries[i];
4099
4100                 j = __ocfs2_dx_dir_hash_idx(osb,
4101                                             le32_to_cpu(dx_entry->dx_minor_hash));
4102                 target_leaf = (struct ocfs2_dx_leaf *)dx_leaves[j]->b_data;
4103
4104                 ocfs2_dx_dir_leaf_insert_tail(target_leaf, dx_entry);
4105
4106                 /* Each leaf has been passed to the journal already
4107                  * via __ocfs2_dx_dir_new_cluster() */
4108         }
4109
4110         dx_root->dr_flags &= ~OCFS2_DX_FLAG_INLINE;
4111         memset(&dx_root->dr_list, 0, osb->sb->s_blocksize -
4112                offsetof(struct ocfs2_dx_root_block, dr_list));
4113         dx_root->dr_list.l_count =
4114                 cpu_to_le16(ocfs2_extent_recs_per_dx_root(osb->sb));
4115
4116         /* This should never fail considering we start with an empty
4117          * dx_root. */
4118         ocfs2_init_dx_root_extent_tree(&et, INODE_CACHE(dir), dx_root_bh);
4119         ret = ocfs2_insert_extent(handle, &et, 0, insert_blkno, 1, 0, NULL);
4120         if (ret)
4121                 mlog_errno(ret);
4122         did_quota = 0;
4123
4124         ocfs2_update_inode_fsync_trans(handle, dir, 1);
4125         ocfs2_journal_dirty(handle, dx_root_bh);
4126
4127 out_commit:
4128         if (ret < 0 && did_quota)
4129                 dquot_free_space_nodirty(dir,
4130                                           ocfs2_clusters_to_bytes(dir->i_sb, 1));
4131
4132         ocfs2_commit_trans(osb, handle);
4133
4134 out:
4135         if (data_ac)
4136                 ocfs2_free_alloc_context(data_ac);
4137
4138         if (dx_leaves) {
4139                 for (i = 0; i < num_dx_leaves; i++)
4140                         brelse(dx_leaves[i]);
4141                 kfree(dx_leaves);
4142         }
4143         return ret;
4144 }
4145
4146 static int ocfs2_inline_dx_has_space(struct buffer_head *dx_root_bh)
4147 {
4148         struct ocfs2_dx_root_block *dx_root;
4149         struct ocfs2_dx_entry_list *entry_list;
4150
4151         dx_root = (struct ocfs2_dx_root_block *) dx_root_bh->b_data;
4152         entry_list = &dx_root->dr_entries;
4153
4154         if (le16_to_cpu(entry_list->de_num_used) >=
4155             le16_to_cpu(entry_list->de_count))
4156                 return -ENOSPC;
4157
4158         return 0;
4159 }
4160
4161 static int ocfs2_prepare_dx_dir_for_insert(struct inode *dir,
4162                                            struct buffer_head *di_bh,
4163                                            const char *name,
4164                                            int namelen,
4165                                            struct ocfs2_dir_lookup_result *lookup)
4166 {
4167         int ret, free_dx_root = 1;
4168         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
4169         struct buffer_head *dx_root_bh = NULL;
4170         struct buffer_head *leaf_bh = NULL;
4171         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4172         struct ocfs2_dx_root_block *dx_root;
4173
4174         ret = ocfs2_read_dx_root(dir, di, &dx_root_bh);
4175         if (ret) {
4176                 mlog_errno(ret);
4177                 goto out;
4178         }
4179
4180         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
4181         if (le32_to_cpu(dx_root->dr_num_entries) == OCFS2_DX_ENTRIES_MAX) {
4182                 ret = -ENOSPC;
4183                 mlog_errno(ret);
4184                 goto out;
4185         }
4186
4187         if (ocfs2_dx_root_inline(dx_root)) {
4188                 ret = ocfs2_inline_dx_has_space(dx_root_bh);
4189
4190                 if (ret == 0)
4191                         goto search_el;
4192
4193                 /*
4194                  * We ran out of room in the root block. Expand it to
4195                  * an extent, then allow ocfs2_find_dir_space_dx to do
4196                  * the rest.
4197                  */
4198                 ret = ocfs2_expand_inline_dx_root(dir, dx_root_bh);
4199                 if (ret) {
4200                         mlog_errno(ret);
4201                         goto out;
4202                 }
4203         }
4204
4205         /*
4206          * Insert preparation for an indexed directory is split into two
4207          * steps. The call to find_dir_space_dx reserves room in the index for
4208          * an additional item. If we run out of space there, it's a real error
4209          * we can't continue on.
4210          */
4211         ret = ocfs2_find_dir_space_dx(osb, dir, di_bh, dx_root_bh, name,
4212                                       namelen, lookup);
4213         if (ret) {
4214                 mlog_errno(ret);
4215                 goto out;
4216         }
4217
4218 search_el:
4219         /*
4220          * Next, we need to find space in the unindexed tree. This call
4221          * searches using the free space linked list. If the unindexed tree
4222          * lacks sufficient space, we'll expand it below. The expansion code
4223          * is smart enough to add any new blocks to the free space list.
4224          */
4225         ret = ocfs2_search_dx_free_list(dir, dx_root_bh, namelen, lookup);
4226         if (ret && ret != -ENOSPC) {
4227                 mlog_errno(ret);
4228                 goto out;
4229         }
4230
4231         /* Do this up here - ocfs2_extend_dir might need the dx_root */
4232         lookup->dl_dx_root_bh = dx_root_bh;
4233         free_dx_root = 0;
4234
4235         if (ret == -ENOSPC) {
4236                 ret = ocfs2_extend_dir(osb, dir, di_bh, 1, lookup, &leaf_bh);
4237
4238                 if (ret) {
4239                         mlog_errno(ret);
4240                         goto out;
4241                 }
4242
4243                 /*
4244                  * We make the assumption here that new leaf blocks are added
4245                  * to the front of our free list.
4246                  */
4247                 lookup->dl_prev_leaf_bh = NULL;
4248                 lookup->dl_leaf_bh = leaf_bh;
4249         }
4250
4251 out:
4252         if (free_dx_root)
4253                 brelse(dx_root_bh);
4254         return ret;
4255 }
4256
4257 /*
4258  * Get a directory ready for insert. Any directory allocation required
4259  * happens here. Success returns zero, and enough context in the dir
4260  * lookup result that ocfs2_add_entry() will be able complete the task
4261  * with minimal performance impact.
4262  */
4263 int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
4264                                  struct inode *dir,
4265                                  struct buffer_head *parent_fe_bh,
4266                                  const char *name,
4267                                  int namelen,
4268                                  struct ocfs2_dir_lookup_result *lookup)
4269 {
4270         int ret;
4271         unsigned int blocks_wanted = 1;
4272         struct buffer_head *bh = NULL;
4273
4274         trace_ocfs2_prepare_dir_for_insert(
4275                 (unsigned long long)OCFS2_I(dir)->ip_blkno, namelen);
4276
4277         if (!namelen) {
4278                 ret = -EINVAL;
4279                 mlog_errno(ret);
4280                 goto out;
4281         }
4282
4283         /*
4284          * Do this up front to reduce confusion.
4285          *
4286          * The directory might start inline, then be turned into an
4287          * indexed one, in which case we'd need to hash deep inside
4288          * ocfs2_find_dir_space_id(). Since
4289          * ocfs2_prepare_dx_dir_for_insert() also needs this hash
4290          * done, there seems no point in spreading out the calls. We
4291          * can optimize away the case where the file system doesn't
4292          * support indexing.
4293          */
4294         if (ocfs2_supports_indexed_dirs(osb))
4295                 ocfs2_dx_dir_name_hash(dir, name, namelen, &lookup->dl_hinfo);
4296
4297         if (ocfs2_dir_indexed(dir)) {
4298                 ret = ocfs2_prepare_dx_dir_for_insert(dir, parent_fe_bh,
4299                                                       name, namelen, lookup);
4300                 if (ret)
4301                         mlog_errno(ret);
4302                 goto out;
4303         }
4304
4305         if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {
4306                 ret = ocfs2_find_dir_space_id(dir, parent_fe_bh, name,
4307                                               namelen, &bh, &blocks_wanted);
4308         } else
4309                 ret = ocfs2_find_dir_space_el(dir, name, namelen, &bh);
4310
4311         if (ret && ret != -ENOSPC) {
4312                 mlog_errno(ret);
4313                 goto out;
4314         }
4315
4316         if (ret == -ENOSPC) {
4317                 /*
4318                  * We have to expand the directory to add this name.
4319                  */
4320                 BUG_ON(bh);
4321
4322                 ret = ocfs2_extend_dir(osb, dir, parent_fe_bh, blocks_wanted,
4323                                        lookup, &bh);
4324                 if (ret) {
4325                         if (ret != -ENOSPC)
4326                                 mlog_errno(ret);
4327                         goto out;
4328                 }
4329
4330                 BUG_ON(!bh);
4331         }
4332
4333         lookup->dl_leaf_bh = bh;
4334         bh = NULL;
4335 out:
4336         brelse(bh);
4337         return ret;
4338 }
4339
4340 static int ocfs2_dx_dir_remove_index(struct inode *dir,
4341                                      struct buffer_head *di_bh,
4342                                      struct buffer_head *dx_root_bh)
4343 {
4344         int ret;
4345         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
4346         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4347         struct ocfs2_dx_root_block *dx_root;
4348         struct inode *dx_alloc_inode = NULL;
4349         struct buffer_head *dx_alloc_bh = NULL;
4350         handle_t *handle;
4351         u64 blk;
4352         u16 bit;
4353         u64 bg_blkno;
4354
4355         dx_root = (struct ocfs2_dx_root_block *) dx_root_bh->b_data;
4356
4357         dx_alloc_inode = ocfs2_get_system_file_inode(osb,
4358                                         EXTENT_ALLOC_SYSTEM_INODE,
4359                                         le16_to_cpu(dx_root->dr_suballoc_slot));
4360         if (!dx_alloc_inode) {
4361                 ret = -ENOMEM;
4362                 mlog_errno(ret);
4363                 goto out;
4364         }
4365         inode_lock(dx_alloc_inode);
4366
4367         ret = ocfs2_inode_lock(dx_alloc_inode, &dx_alloc_bh, 1);
4368         if (ret) {
4369                 mlog_errno(ret);
4370                 goto out_mutex;
4371         }
4372
4373         handle = ocfs2_start_trans(osb, OCFS2_DX_ROOT_REMOVE_CREDITS);
4374         if (IS_ERR(handle)) {
4375                 ret = PTR_ERR(handle);
4376                 mlog_errno(ret);
4377                 goto out_unlock;
4378         }
4379
4380         ret = ocfs2_journal_access_di(handle, INODE_CACHE(dir), di_bh,
4381                                       OCFS2_JOURNAL_ACCESS_WRITE);
4382         if (ret) {
4383                 mlog_errno(ret);
4384                 goto out_commit;
4385         }
4386
4387         spin_lock(&OCFS2_I(dir)->ip_lock);
4388         OCFS2_I(dir)->ip_dyn_features &= ~OCFS2_INDEXED_DIR_FL;
4389         di->i_dyn_features = cpu_to_le16(OCFS2_I(dir)->ip_dyn_features);
4390         spin_unlock(&OCFS2_I(dir)->ip_lock);
4391         di->i_dx_root = cpu_to_le64(0ULL);
4392         ocfs2_update_inode_fsync_trans(handle, dir, 1);
4393
4394         ocfs2_journal_dirty(handle, di_bh);
4395
4396         blk = le64_to_cpu(dx_root->dr_blkno);
4397         bit = le16_to_cpu(dx_root->dr_suballoc_bit);
4398         if (dx_root->dr_suballoc_loc)
4399                 bg_blkno = le64_to_cpu(dx_root->dr_suballoc_loc);
4400         else
4401                 bg_blkno = ocfs2_which_suballoc_group(blk, bit);
4402         ret = ocfs2_free_suballoc_bits(handle, dx_alloc_inode, dx_alloc_bh,
4403                                        bit, bg_blkno, 1);
4404         if (ret)
4405                 mlog_errno(ret);
4406
4407 out_commit:
4408         ocfs2_commit_trans(osb, handle);
4409
4410 out_unlock:
4411         ocfs2_inode_unlock(dx_alloc_inode, 1);
4412
4413 out_mutex:
4414         inode_unlock(dx_alloc_inode);
4415         brelse(dx_alloc_bh);
4416 out:
4417         iput(dx_alloc_inode);
4418         return ret;
4419 }
4420
4421 int ocfs2_dx_dir_truncate(struct inode *dir, struct buffer_head *di_bh)
4422 {
4423         int ret;
4424         unsigned int uninitialized_var(clen);
4425         u32 major_hash = UINT_MAX, p_cpos, uninitialized_var(cpos);
4426         u64 uninitialized_var(blkno);
4427         struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
4428         struct buffer_head *dx_root_bh = NULL;
4429         struct ocfs2_dx_root_block *dx_root;
4430         struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
4431         struct ocfs2_cached_dealloc_ctxt dealloc;
4432         struct ocfs2_extent_tree et;
4433
4434         ocfs2_init_dealloc_ctxt(&dealloc);
4435
4436         if (!ocfs2_dir_indexed(dir))
4437                 return 0;
4438
4439         ret = ocfs2_read_dx_root(dir, di, &dx_root_bh);
4440         if (ret) {
4441                 mlog_errno(ret);
4442                 goto out;
4443         }
4444         dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
4445
4446         if (ocfs2_dx_root_inline(dx_root))
4447                 goto remove_index;
4448
4449         ocfs2_init_dx_root_extent_tree(&et, INODE_CACHE(dir), dx_root_bh);
4450
4451         /* XXX: What if dr_clusters is too large? */
4452         while (le32_to_cpu(dx_root->dr_clusters)) {
4453                 ret = ocfs2_dx_dir_lookup_rec(dir, &dx_root->dr_list,
4454                                               major_hash, &cpos, &blkno, &clen);
4455                 if (ret) {
4456                         mlog_errno(ret);
4457                         goto out;
4458                 }
4459
4460                 p_cpos = ocfs2_blocks_to_clusters(dir->i_sb, blkno);
4461
4462                 ret = ocfs2_remove_btree_range(dir, &et, cpos, p_cpos, clen, 0,
4463                                                &dealloc, 0, false);
4464                 if (ret) {
4465                         mlog_errno(ret);
4466                         goto out;
4467                 }
4468
4469                 if (cpos == 0)
4470                         break;
4471
4472                 major_hash = cpos - 1;
4473         }
4474
4475 remove_index:
4476         ret = ocfs2_dx_dir_remove_index(dir, di_bh, dx_root_bh);
4477         if (ret) {
4478                 mlog_errno(ret);
4479                 goto out;
4480         }
4481
4482         ocfs2_remove_from_cache(INODE_CACHE(dir), dx_root_bh);
4483 out:
4484         ocfs2_schedule_truncate_log_flush(osb, 1);
4485         ocfs2_run_deallocs(osb, &dealloc);
4486
4487         brelse(dx_root_bh);
4488         return ret;
4489 }