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