Pileus Git - ~andy/linux/blob - fs/ocfs2/suballoc.c

   1 /* -*- mode: c; c-basic-offset: 8; -*-
   2  * vim: noexpandtab sw=8 ts=8 sts=0:
   3  *
   4  * suballoc.c
   5  *
   6  * metadata alloc and free
   7  * Inspired by ext3 block groups.
   8  *
   9  * Copyright (C) 2002, 2004 Oracle.  All rights reserved.
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2 of the License, or (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public
  22  * License along with this program; if not, write to the
  23  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  24  * Boston, MA 021110-1307, USA.
  25  */
  26
  27 #include <linux/fs.h>
  28 #include <linux/types.h>
  29 #include <linux/slab.h>
  30 #include <linux/highmem.h>
  31
  32 #define MLOG_MASK_PREFIX ML_DISK_ALLOC
  33 #include <cluster/masklog.h>
  34
  35 #include "ocfs2.h"
  36
  37 #include "alloc.h"
  38 #include "dlmglue.h"
  39 #include "inode.h"
  40 #include "journal.h"
  41 #include "localalloc.h"
  42 #include "suballoc.h"
  43 #include "super.h"
  44 #include "sysfile.h"
  45 #include "uptodate.h"
  46
  47 #include "buffer_head_io.h"
  48
  49 #define NOT_ALLOC_NEW_GROUP             0
  50 #define ALLOC_NEW_GROUP                 1
  51
  52 static inline void ocfs2_debug_bg(struct ocfs2_group_desc *bg);
  53 static inline void ocfs2_debug_suballoc_inode(struct ocfs2_dinode *fe);
  54 static inline u16 ocfs2_find_victim_chain(struct ocfs2_chain_list *cl);
  55 static int ocfs2_block_group_fill(handle_t *handle,
  56                                   struct inode *alloc_inode,
  57                                   struct buffer_head *bg_bh,
  58                                   u64 group_blkno,
  59                                   u16 my_chain,
  60                                   struct ocfs2_chain_list *cl);
  61 static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
  62                                    struct inode *alloc_inode,
  63                                    struct buffer_head *bh);
  64
  65 static int ocfs2_cluster_group_search(struct inode *inode,
  66                                       struct buffer_head *group_bh,
  67                                       u32 bits_wanted, u32 min_bits,
  68                                       u16 *bit_off, u16 *bits_found);
  69 static int ocfs2_block_group_search(struct inode *inode,
  70                                     struct buffer_head *group_bh,
  71                                     u32 bits_wanted, u32 min_bits,
  72                                     u16 *bit_off, u16 *bits_found);
  73 static int ocfs2_claim_suballoc_bits(struct ocfs2_super *osb,
  74                                      struct ocfs2_alloc_context *ac,
  75                                      handle_t *handle,
  76                                      u32 bits_wanted,
  77                                      u32 min_bits,
  78                                      u16 *bit_off,
  79                                      unsigned int *num_bits,
  80                                      u64 *bg_blkno);
  81 static int ocfs2_test_bg_bit_allocatable(struct buffer_head *bg_bh,
  82                                          int nr);
  83 static inline int ocfs2_block_group_set_bits(handle_t *handle,
  84                                              struct inode *alloc_inode,
  85                                              struct ocfs2_group_desc *bg,
  86                                              struct buffer_head *group_bh,
  87                                              unsigned int bit_off,
  88                                              unsigned int num_bits);
  89 static inline int ocfs2_block_group_clear_bits(handle_t *handle,
  90                                                struct inode *alloc_inode,
  91                                                struct ocfs2_group_desc *bg,
  92                                                struct buffer_head *group_bh,
  93                                                unsigned int bit_off,
  94                                                unsigned int num_bits);
  95
  96 static int ocfs2_relink_block_group(handle_t *handle,
  97                                     struct inode *alloc_inode,
  98                                     struct buffer_head *fe_bh,
  99                                     struct buffer_head *bg_bh,
 100                                     struct buffer_head *prev_bg_bh,
 101                                     u16 chain);
 102 static inline int ocfs2_block_group_reasonably_empty(struct ocfs2_group_desc *bg,
 103                                                      u32 wanted);
 104 static inline u32 ocfs2_desc_bitmap_to_cluster_off(struct inode *inode,
 105                                                    u64 bg_blkno,
 106                                                    u16 bg_bit_off);
 107 static inline void ocfs2_block_to_cluster_group(struct inode *inode,
 108                                                 u64 data_blkno,
 109                                                 u64 *bg_blkno,
 110                                                 u16 *bg_bit_off);
 111
 112 void ocfs2_free_alloc_context(struct ocfs2_alloc_context *ac)
 113 {
 114         struct inode *inode = ac->ac_inode;
 115
 116         if (inode) {
 117                 if (ac->ac_which != OCFS2_AC_USE_LOCAL)
 118                         ocfs2_inode_unlock(inode, 1);
 119
 120                 mutex_unlock(&inode->i_mutex);
 121
 122                 iput(inode);
 123         }
 124         if (ac->ac_bh)
 125                 brelse(ac->ac_bh);
 126         kfree(ac);
 127 }
 128
 129 static u32 ocfs2_bits_per_group(struct ocfs2_chain_list *cl)
 130 {
 131         return (u32)le16_to_cpu(cl->cl_cpg) * (u32)le16_to_cpu(cl->cl_bpc);
 132 }
 133
 134 /* somewhat more expensive than our other checks, so use sparingly. */
 135 int ocfs2_check_group_descriptor(struct super_block *sb,
 136                                  struct ocfs2_dinode *di,
 137                                  struct ocfs2_group_desc *gd)
 138 {
 139         unsigned int max_bits;
 140
 141         if (!OCFS2_IS_VALID_GROUP_DESC(gd)) {
 142                 OCFS2_RO_ON_INVALID_GROUP_DESC(sb, gd);
 143                 return -EIO;
 144         }
 145
 146         if (di->i_blkno != gd->bg_parent_dinode) {
 147                 ocfs2_error(sb, "Group descriptor # %llu has bad parent "
 148                             "pointer (%llu, expected %llu)",
 149                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
 150                             (unsigned long long)le64_to_cpu(gd->bg_parent_dinode),
 151                             (unsigned long long)le64_to_cpu(di->i_blkno));
 152                 return -EIO;
 153         }
 154
 155         max_bits = le16_to_cpu(di->id2.i_chain.cl_cpg) * le16_to_cpu(di->id2.i_chain.cl_bpc);
 156         if (le16_to_cpu(gd->bg_bits) > max_bits) {
 157                 ocfs2_error(sb, "Group descriptor # %llu has bit count of %u",
 158                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
 159                             le16_to_cpu(gd->bg_bits));
 160                 return -EIO;
 161         }
 162
 163         if (le16_to_cpu(gd->bg_chain) >=
 164             le16_to_cpu(di->id2.i_chain.cl_next_free_rec)) {
 165                 ocfs2_error(sb, "Group descriptor # %llu has bad chain %u",
 166                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
 167                             le16_to_cpu(gd->bg_chain));
 168                 return -EIO;
 169         }
 170
 171         if (le16_to_cpu(gd->bg_free_bits_count) > le16_to_cpu(gd->bg_bits)) {
 172                 ocfs2_error(sb, "Group descriptor # %llu has bit count %u but "
 173                             "claims that %u are free",
 174                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
 175                             le16_to_cpu(gd->bg_bits),
 176                             le16_to_cpu(gd->bg_free_bits_count));
 177                 return -EIO;
 178         }
 179
 180         if (le16_to_cpu(gd->bg_bits) > (8 * le16_to_cpu(gd->bg_size))) {
 181                 ocfs2_error(sb, "Group descriptor # %llu has bit count %u but "
 182                             "max bitmap bits of %u",
 183                             (unsigned long long)le64_to_cpu(gd->bg_blkno),
 184                             le16_to_cpu(gd->bg_bits),
 185                             8 * le16_to_cpu(gd->bg_size));
 186                 return -EIO;
 187         }
 188
 189         return 0;
 190 }
 191
 192 static int ocfs2_block_group_fill(handle_t *handle,
 193                                   struct inode *alloc_inode,
 194                                   struct buffer_head *bg_bh,
 195                                   u64 group_blkno,
 196                                   u16 my_chain,
 197                                   struct ocfs2_chain_list *cl)
 198 {
 199         int status = 0;
 200         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
 201         struct super_block * sb = alloc_inode->i_sb;
 202
 203         mlog_entry_void();
 204
 205         if (((unsigned long long) bg_bh->b_blocknr) != group_blkno) {
 206                 ocfs2_error(alloc_inode->i_sb, "group block (%llu) != "
 207                             "b_blocknr (%llu)",
 208                             (unsigned long long)group_blkno,
 209                             (unsigned long long) bg_bh->b_blocknr);
 210                 status = -EIO;
 211                 goto bail;
 212         }
 213
 214         status = ocfs2_journal_access(handle,
 215                                       alloc_inode,
 216                                       bg_bh,
 217                                       OCFS2_JOURNAL_ACCESS_CREATE);
 218         if (status < 0) {
 219                 mlog_errno(status);
 220                 goto bail;
 221         }
 222
 223         memset(bg, 0, sb->s_blocksize);
 224         strcpy(bg->bg_signature, OCFS2_GROUP_DESC_SIGNATURE);
 225         bg->bg_generation = cpu_to_le32(OCFS2_SB(sb)->fs_generation);
 226         bg->bg_size = cpu_to_le16(ocfs2_group_bitmap_size(sb));
 227         bg->bg_bits = cpu_to_le16(ocfs2_bits_per_group(cl));
 228         bg->bg_chain = cpu_to_le16(my_chain);
 229         bg->bg_next_group = cl->cl_recs[my_chain].c_blkno;
 230         bg->bg_parent_dinode = cpu_to_le64(OCFS2_I(alloc_inode)->ip_blkno);
 231         bg->bg_blkno = cpu_to_le64(group_blkno);
 232         /* set the 1st bit in the bitmap to account for the descriptor block */
 233         ocfs2_set_bit(0, (unsigned long *)bg->bg_bitmap);
 234         bg->bg_free_bits_count = cpu_to_le16(le16_to_cpu(bg->bg_bits) - 1);
 235
 236         status = ocfs2_journal_dirty(handle, bg_bh);
 237         if (status < 0)
 238                 mlog_errno(status);
 239
 240         /* There is no need to zero out or otherwise initialize the
 241          * other blocks in a group - All valid FS metadata in a block
 242          * group stores the superblock fs_generation value at
 243          * allocation time. */
 244
 245 bail:
 246         mlog_exit(status);
 247         return status;
 248 }
 249
 250 static inline u16 ocfs2_find_smallest_chain(struct ocfs2_chain_list *cl)
 251 {
 252         u16 curr, best;
 253
 254         best = curr = 0;
 255         while (curr < le16_to_cpu(cl->cl_count)) {
 256                 if (le32_to_cpu(cl->cl_recs[best].c_total) >
 257                     le32_to_cpu(cl->cl_recs[curr].c_total))
 258                         best = curr;
 259                 curr++;
 260         }
 261         return best;
 262 }
 263
 264 /*
 265  * We expect the block group allocator to already be locked.
 266  */
 267 static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
 268                                    struct inode *alloc_inode,
 269                                    struct buffer_head *bh)
 270 {
 271         int status, credits;
 272         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) bh->b_data;
 273         struct ocfs2_chain_list *cl;
 274         struct ocfs2_alloc_context *ac = NULL;
 275         handle_t *handle = NULL;
 276         u32 bit_off, num_bits;
 277         u16 alloc_rec;
 278         u64 bg_blkno;
 279         struct buffer_head *bg_bh = NULL;
 280         struct ocfs2_group_desc *bg;
 281
 282         BUG_ON(ocfs2_is_cluster_bitmap(alloc_inode));
 283
 284         mlog_entry_void();
 285
 286         cl = &fe->id2.i_chain;
 287         status = ocfs2_reserve_clusters(osb,
 288                                         le16_to_cpu(cl->cl_cpg),
 289                                         &ac);
 290         if (status < 0) {
 291                 if (status != -ENOSPC)
 292                         mlog_errno(status);
 293                 goto bail;
 294         }
 295
 296         credits = ocfs2_calc_group_alloc_credits(osb->sb,
 297                                                  le16_to_cpu(cl->cl_cpg));
 298         handle = ocfs2_start_trans(osb, credits);
 299         if (IS_ERR(handle)) {
 300                 status = PTR_ERR(handle);
 301                 handle = NULL;
 302                 mlog_errno(status);
 303                 goto bail;
 304         }
 305
 306         status = ocfs2_claim_clusters(osb,
 307                                       handle,
 308                                       ac,
 309                                       le16_to_cpu(cl->cl_cpg),
 310                                       &bit_off,
 311                                       &num_bits);
 312         if (status < 0) {
 313                 if (status != -ENOSPC)
 314                         mlog_errno(status);
 315                 goto bail;
 316         }
 317
 318         alloc_rec = ocfs2_find_smallest_chain(cl);
 319
 320         /* setup the group */
 321         bg_blkno = ocfs2_clusters_to_blocks(osb->sb, bit_off);
 322         mlog(0, "new descriptor, record %u, at block %llu\n",
 323              alloc_rec, (unsigned long long)bg_blkno);
 324
 325         bg_bh = sb_getblk(osb->sb, bg_blkno);
 326         if (!bg_bh) {
 327                 status = -EIO;
 328                 mlog_errno(status);
 329                 goto bail;
 330         }
 331         ocfs2_set_new_buffer_uptodate(alloc_inode, bg_bh);
 332
 333         status = ocfs2_block_group_fill(handle,
 334                                         alloc_inode,
 335                                         bg_bh,
 336                                         bg_blkno,
 337                                         alloc_rec,
 338                                         cl);
 339         if (status < 0) {
 340                 mlog_errno(status);
 341                 goto bail;
 342         }
 343
 344         bg = (struct ocfs2_group_desc *) bg_bh->b_data;
 345
 346         status = ocfs2_journal_access(handle, alloc_inode,
 347                                       bh, OCFS2_JOURNAL_ACCESS_WRITE);
 348         if (status < 0) {
 349                 mlog_errno(status);
 350                 goto bail;
 351         }
 352
 353         le32_add_cpu(&cl->cl_recs[alloc_rec].c_free,
 354                      le16_to_cpu(bg->bg_free_bits_count));
 355         le32_add_cpu(&cl->cl_recs[alloc_rec].c_total, le16_to_cpu(bg->bg_bits));
 356         cl->cl_recs[alloc_rec].c_blkno  = cpu_to_le64(bg_blkno);
 357         if (le16_to_cpu(cl->cl_next_free_rec) < le16_to_cpu(cl->cl_count))
 358                 le16_add_cpu(&cl->cl_next_free_rec, 1);
 359
 360         le32_add_cpu(&fe->id1.bitmap1.i_used, le16_to_cpu(bg->bg_bits) -
 361                                         le16_to_cpu(bg->bg_free_bits_count));
 362         le32_add_cpu(&fe->id1.bitmap1.i_total, le16_to_cpu(bg->bg_bits));
 363         le32_add_cpu(&fe->i_clusters, le16_to_cpu(cl->cl_cpg));
 364
 365         status = ocfs2_journal_dirty(handle, bh);
 366         if (status < 0) {
 367                 mlog_errno(status);
 368                 goto bail;
 369         }
 370
 371         spin_lock(&OCFS2_I(alloc_inode)->ip_lock);
 372         OCFS2_I(alloc_inode)->ip_clusters = le32_to_cpu(fe->i_clusters);
 373         fe->i_size = cpu_to_le64(ocfs2_clusters_to_bytes(alloc_inode->i_sb,
 374                                              le32_to_cpu(fe->i_clusters)));
 375         spin_unlock(&OCFS2_I(alloc_inode)->ip_lock);
 376         i_size_write(alloc_inode, le64_to_cpu(fe->i_size));
 377         alloc_inode->i_blocks = ocfs2_inode_sector_count(alloc_inode);
 378
 379         status = 0;
 380 bail:
 381         if (handle)
 382                 ocfs2_commit_trans(osb, handle);
 383
 384         if (ac)
 385                 ocfs2_free_alloc_context(ac);
 386
 387         if (bg_bh)
 388                 brelse(bg_bh);
 389
 390         mlog_exit(status);
 391         return status;
 392 }
 393
 394 static int ocfs2_reserve_suballoc_bits(struct ocfs2_super *osb,
 395                                        struct ocfs2_alloc_context *ac,
 396                                        int type,
 397                                        u32 slot,
 398                                        int alloc_new_group)
 399 {
 400         int status;
 401         u32 bits_wanted = ac->ac_bits_wanted;
 402         struct inode *alloc_inode;
 403         struct buffer_head *bh = NULL;
 404         struct ocfs2_dinode *fe;
 405         u32 free_bits;
 406
 407         mlog_entry_void();
 408
 409         alloc_inode = ocfs2_get_system_file_inode(osb, type, slot);
 410         if (!alloc_inode) {
 411                 mlog_errno(-EINVAL);
 412                 return -EINVAL;
 413         }
 414
 415         mutex_lock(&alloc_inode->i_mutex);
 416
 417         status = ocfs2_inode_lock(alloc_inode, &bh, 1);
 418         if (status < 0) {
 419                 mutex_unlock(&alloc_inode->i_mutex);
 420                 iput(alloc_inode);
 421
 422                 mlog_errno(status);
 423                 return status;
 424         }
 425
 426         ac->ac_inode = alloc_inode;
 427
 428         fe = (struct ocfs2_dinode *) bh->b_data;
 429         if (!OCFS2_IS_VALID_DINODE(fe)) {
 430                 OCFS2_RO_ON_INVALID_DINODE(alloc_inode->i_sb, fe);
 431                 status = -EIO;
 432                 goto bail;
 433         }
 434         if (!(fe->i_flags & cpu_to_le32(OCFS2_CHAIN_FL))) {
 435                 ocfs2_error(alloc_inode->i_sb, "Invalid chain allocator %llu",
 436                             (unsigned long long)le64_to_cpu(fe->i_blkno));
 437                 status = -EIO;
 438                 goto bail;
 439         }
 440
 441         free_bits = le32_to_cpu(fe->id1.bitmap1.i_total) -
 442                 le32_to_cpu(fe->id1.bitmap1.i_used);
 443
 444         if (bits_wanted > free_bits) {
 445                 /* cluster bitmap never grows */
 446                 if (ocfs2_is_cluster_bitmap(alloc_inode)) {
 447                         mlog(0, "Disk Full: wanted=%u, free_bits=%u\n",
 448                              bits_wanted, free_bits);
 449                         status = -ENOSPC;
 450                         goto bail;
 451                 }
 452
 453                 if (alloc_new_group != ALLOC_NEW_GROUP) {
 454                         mlog(0, "Alloc File %u Full: wanted=%u, free_bits=%u, "
 455                              "and we don't alloc a new group for it.\n",
 456                              slot, bits_wanted, free_bits);
 457                         status = -ENOSPC;
 458                         goto bail;
 459                 }
 460
 461                 status = ocfs2_block_group_alloc(osb, alloc_inode, bh);
 462                 if (status < 0) {
 463                         if (status != -ENOSPC)
 464                                 mlog_errno(status);
 465                         goto bail;
 466                 }
 467                 atomic_inc(&osb->alloc_stats.bg_extends);
 468
 469                 /* You should never ask for this much metadata */
 470                 BUG_ON(bits_wanted >
 471                        (le32_to_cpu(fe->id1.bitmap1.i_total)
 472                         - le32_to_cpu(fe->id1.bitmap1.i_used)));
 473         }
 474
 475         get_bh(bh);
 476         ac->ac_bh = bh;
 477 bail:
 478         if (bh)
 479                 brelse(bh);
 480
 481         mlog_exit(status);
 482         return status;
 483 }
 484
 485 int ocfs2_reserve_new_metadata(struct ocfs2_super *osb,
 486                                struct ocfs2_dinode *fe,
 487                                struct ocfs2_alloc_context **ac)
 488 {
 489         int status;
 490         u32 slot;
 491
 492         *ac = kzalloc(sizeof(struct ocfs2_alloc_context), GFP_KERNEL);
 493         if (!(*ac)) {
 494                 status = -ENOMEM;
 495                 mlog_errno(status);
 496                 goto bail;
 497         }
 498
 499         (*ac)->ac_bits_wanted = ocfs2_extend_meta_needed(fe);
 500         (*ac)->ac_which = OCFS2_AC_USE_META;
 501         slot = osb->slot_num;
 502         (*ac)->ac_group_search = ocfs2_block_group_search;
 503
 504         status = ocfs2_reserve_suballoc_bits(osb, (*ac),
 505                                              EXTENT_ALLOC_SYSTEM_INODE,
 506                                              slot, ALLOC_NEW_GROUP);
 507         if (status < 0) {
 508                 if (status != -ENOSPC)
 509                         mlog_errno(status);
 510                 goto bail;
 511         }
 512
 513         status = 0;
 514 bail:
 515         if ((status < 0) && *ac) {
 516                 ocfs2_free_alloc_context(*ac);
 517                 *ac = NULL;
 518         }
 519
 520         mlog_exit(status);
 521         return status;
 522 }
 523
 524 int ocfs2_reserve_new_inode(struct ocfs2_super *osb,
 525                             struct ocfs2_alloc_context **ac)
 526 {
 527         int status;
 528
 529         *ac = kzalloc(sizeof(struct ocfs2_alloc_context), GFP_KERNEL);
 530         if (!(*ac)) {
 531                 status = -ENOMEM;
 532                 mlog_errno(status);
 533                 goto bail;
 534         }
 535
 536         (*ac)->ac_bits_wanted = 1;
 537         (*ac)->ac_which = OCFS2_AC_USE_INODE;
 538
 539         (*ac)->ac_group_search = ocfs2_block_group_search;
 540
 541         status = ocfs2_reserve_suballoc_bits(osb, *ac,
 542                                              INODE_ALLOC_SYSTEM_INODE,
 543                                              osb->slot_num, ALLOC_NEW_GROUP);
 544         if (status < 0) {
 545                 if (status != -ENOSPC)
 546                         mlog_errno(status);
 547                 goto bail;
 548         }
 549
 550         status = 0;
 551 bail:
 552         if ((status < 0) && *ac) {
 553                 ocfs2_free_alloc_context(*ac);
 554                 *ac = NULL;
 555         }
 556
 557         mlog_exit(status);
 558         return status;
 559 }
 560
 561 /* local alloc code has to do the same thing, so rather than do this
 562  * twice.. */
 563 int ocfs2_reserve_cluster_bitmap_bits(struct ocfs2_super *osb,
 564                                       struct ocfs2_alloc_context *ac)
 565 {
 566         int status;
 567
 568         ac->ac_which = OCFS2_AC_USE_MAIN;
 569         ac->ac_group_search = ocfs2_cluster_group_search;
 570
 571         status = ocfs2_reserve_suballoc_bits(osb, ac,
 572                                              GLOBAL_BITMAP_SYSTEM_INODE,
 573                                              OCFS2_INVALID_SLOT,
 574                                              ALLOC_NEW_GROUP);
 575         if (status < 0 && status != -ENOSPC) {
 576                 mlog_errno(status);
 577                 goto bail;
 578         }
 579
 580 bail:
 581         return status;
 582 }
 583
 584 /* Callers don't need to care which bitmap (local alloc or main) to
 585  * use so we figure it out for them, but unfortunately this clutters
 586  * things a bit. */
 587 int ocfs2_reserve_clusters(struct ocfs2_super *osb,
 588                            u32 bits_wanted,
 589                            struct ocfs2_alloc_context **ac)
 590 {
 591         int status;
 592
 593         mlog_entry_void();
 594
 595         *ac = kzalloc(sizeof(struct ocfs2_alloc_context), GFP_KERNEL);
 596         if (!(*ac)) {
 597                 status = -ENOMEM;
 598                 mlog_errno(status);
 599                 goto bail;
 600         }
 601
 602         (*ac)->ac_bits_wanted = bits_wanted;
 603
 604         status = -ENOSPC;
 605         if (ocfs2_alloc_should_use_local(osb, bits_wanted)) {
 606                 status = ocfs2_reserve_local_alloc_bits(osb,
 607                                                         bits_wanted,
 608                                                         *ac);
 609                 if ((status < 0) && (status != -ENOSPC)) {
 610                         mlog_errno(status);
 611                         goto bail;
 612                 } else if (status == -ENOSPC) {
 613                         /* reserve_local_bits will return enospc with
 614                          * the local alloc inode still locked, so we
 615                          * can change this safely here. */
 616                         mlog(0, "Disabling local alloc\n");
 617                         /* We set to OCFS2_LA_DISABLED so that umount
 618                          * can clean up what's left of the local
 619                          * allocation */
 620                         osb->local_alloc_state = OCFS2_LA_DISABLED;
 621                 }
 622         }
 623
 624         if (status == -ENOSPC) {
 625                 status = ocfs2_reserve_cluster_bitmap_bits(osb, *ac);
 626                 if (status < 0) {
 627                         if (status != -ENOSPC)
 628                                 mlog_errno(status);
 629                         goto bail;
 630                 }
 631         }
 632
 633         status = 0;
 634 bail:
 635         if ((status < 0) && *ac) {
 636                 ocfs2_free_alloc_context(*ac);
 637                 *ac = NULL;
 638         }
 639
 640         mlog_exit(status);
 641         return status;
 642 }
 643
 644 /*
 645  * More or less lifted from ext3. I'll leave their description below:
 646  *
 647  * "For ext3 allocations, we must not reuse any blocks which are
 648  * allocated in the bitmap buffer's "last committed data" copy.  This
 649  * prevents deletes from freeing up the page for reuse until we have
 650  * committed the delete transaction.
 651  *
 652  * If we didn't do this, then deleting something and reallocating it as
 653  * data would allow the old block to be overwritten before the
 654  * transaction committed (because we force data to disk before commit).
 655  * This would lead to corruption if we crashed between overwriting the
 656  * data and committing the delete.
 657  *
 658  * @@@ We may want to make this allocation behaviour conditional on
 659  * data-writes at some point, and disable it for metadata allocations or
 660  * sync-data inodes."
 661  *
 662  * Note: OCFS2 already does this differently for metadata vs data
 663  * allocations, as those bitmaps are separate and undo access is never
 664  * called on a metadata group descriptor.
 665  */
 666 static int ocfs2_test_bg_bit_allocatable(struct buffer_head *bg_bh,
 667                                          int nr)
 668 {
 669         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
 670
 671         if (ocfs2_test_bit(nr, (unsigned long *)bg->bg_bitmap))
 672                 return 0;
 673         if (!buffer_jbd(bg_bh) || !bh2jh(bg_bh)->b_committed_data)
 674                 return 1;
 675
 676         bg = (struct ocfs2_group_desc *) bh2jh(bg_bh)->b_committed_data;
 677         return !ocfs2_test_bit(nr, (unsigned long *)bg->bg_bitmap);
 678 }
 679
 680 static int ocfs2_block_group_find_clear_bits(struct ocfs2_super *osb,
 681                                              struct buffer_head *bg_bh,
 682                                              unsigned int bits_wanted,
 683                                              unsigned int total_bits,
 684                                              u16 *bit_off,
 685                                              u16 *bits_found)
 686 {
 687         void *bitmap;
 688         u16 best_offset, best_size;
 689         int offset, start, found, status = 0;
 690         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
 691
 692         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
 693                 OCFS2_RO_ON_INVALID_GROUP_DESC(osb->sb, bg);
 694                 return -EIO;
 695         }
 696
 697         found = start = best_offset = best_size = 0;
 698         bitmap = bg->bg_bitmap;
 699
 700         while((offset = ocfs2_find_next_zero_bit(bitmap, total_bits, start)) != -1) {
 701                 if (offset == total_bits)
 702                         break;
 703
 704                 if (!ocfs2_test_bg_bit_allocatable(bg_bh, offset)) {
 705                         /* We found a zero, but we can't use it as it
 706                          * hasn't been put to disk yet! */
 707                         found = 0;
 708                         start = offset + 1;
 709                 } else if (offset == start) {
 710                         /* we found a zero */
 711                         found++;
 712                         /* move start to the next bit to test */
 713                         start++;
 714                 } else {
 715                         /* got a zero after some ones */
 716                         found = 1;
 717                         start = offset + 1;
 718                 }
 719                 if (found > best_size) {
 720                         best_size = found;
 721                         best_offset = start - found;
 722                 }
 723                 /* we got everything we needed */
 724                 if (found == bits_wanted) {
 725                         /* mlog(0, "Found it all!\n"); */
 726                         break;
 727                 }
 728         }
 729
 730         /* XXX: I think the first clause is equivalent to the second
 731          *      - jlbec */
 732         if (found == bits_wanted) {
 733                 *bit_off = start - found;
 734                 *bits_found = found;
 735         } else if (best_size) {
 736                 *bit_off = best_offset;
 737                 *bits_found = best_size;
 738         } else {
 739                 status = -ENOSPC;
 740                 /* No error log here -- see the comment above
 741                  * ocfs2_test_bg_bit_allocatable */
 742         }
 743
 744         return status;
 745 }
 746
 747 static inline int ocfs2_block_group_set_bits(handle_t *handle,
 748                                              struct inode *alloc_inode,
 749                                              struct ocfs2_group_desc *bg,
 750                                              struct buffer_head *group_bh,
 751                                              unsigned int bit_off,
 752                                              unsigned int num_bits)
 753 {
 754         int status;
 755         void *bitmap = bg->bg_bitmap;
 756         int journal_type = OCFS2_JOURNAL_ACCESS_WRITE;
 757
 758         mlog_entry_void();
 759
 760         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
 761                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, bg);
 762                 status = -EIO;
 763                 goto bail;
 764         }
 765         BUG_ON(le16_to_cpu(bg->bg_free_bits_count) < num_bits);
 766
 767         mlog(0, "block_group_set_bits: off = %u, num = %u\n", bit_off,
 768              num_bits);
 769
 770         if (ocfs2_is_cluster_bitmap(alloc_inode))
 771                 journal_type = OCFS2_JOURNAL_ACCESS_UNDO;
 772
 773         status = ocfs2_journal_access(handle,
 774                                       alloc_inode,
 775                                       group_bh,
 776                                       journal_type);
 777         if (status < 0) {
 778                 mlog_errno(status);
 779                 goto bail;
 780         }
 781
 782         le16_add_cpu(&bg->bg_free_bits_count, -num_bits);
 783
 784         while(num_bits--)
 785                 ocfs2_set_bit(bit_off++, bitmap);
 786
 787         status = ocfs2_journal_dirty(handle,
 788                                      group_bh);
 789         if (status < 0) {
 790                 mlog_errno(status);
 791                 goto bail;
 792         }
 793
 794 bail:
 795         mlog_exit(status);
 796         return status;
 797 }
 798
 799 /* find the one with the most empty bits */
 800 static inline u16 ocfs2_find_victim_chain(struct ocfs2_chain_list *cl)
 801 {
 802         u16 curr, best;
 803
 804         BUG_ON(!cl->cl_next_free_rec);
 805
 806         best = curr = 0;
 807         while (curr < le16_to_cpu(cl->cl_next_free_rec)) {
 808                 if (le32_to_cpu(cl->cl_recs[curr].c_free) >
 809                     le32_to_cpu(cl->cl_recs[best].c_free))
 810                         best = curr;
 811                 curr++;
 812         }
 813
 814         BUG_ON(best >= le16_to_cpu(cl->cl_next_free_rec));
 815         return best;
 816 }
 817
 818 static int ocfs2_relink_block_group(handle_t *handle,
 819                                     struct inode *alloc_inode,
 820                                     struct buffer_head *fe_bh,
 821                                     struct buffer_head *bg_bh,
 822                                     struct buffer_head *prev_bg_bh,
 823                                     u16 chain)
 824 {
 825         int status;
 826         /* there is a really tiny chance the journal calls could fail,
 827          * but we wouldn't want inconsistent blocks in *any* case. */
 828         u64 fe_ptr, bg_ptr, prev_bg_ptr;
 829         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) fe_bh->b_data;
 830         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) bg_bh->b_data;
 831         struct ocfs2_group_desc *prev_bg = (struct ocfs2_group_desc *) prev_bg_bh->b_data;
 832
 833         if (!OCFS2_IS_VALID_DINODE(fe)) {
 834                 OCFS2_RO_ON_INVALID_DINODE(alloc_inode->i_sb, fe);
 835                 status = -EIO;
 836                 goto out;
 837         }
 838         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
 839                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, bg);
 840                 status = -EIO;
 841                 goto out;
 842         }
 843         if (!OCFS2_IS_VALID_GROUP_DESC(prev_bg)) {
 844                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, prev_bg);
 845                 status = -EIO;
 846                 goto out;
 847         }
 848
 849         mlog(0, "Suballoc %llu, chain %u, move group %llu to top, prev = %llu\n",
 850              (unsigned long long)le64_to_cpu(fe->i_blkno), chain,
 851              (unsigned long long)le64_to_cpu(bg->bg_blkno),
 852              (unsigned long long)le64_to_cpu(prev_bg->bg_blkno));
 853
 854         fe_ptr = le64_to_cpu(fe->id2.i_chain.cl_recs[chain].c_blkno);
 855         bg_ptr = le64_to_cpu(bg->bg_next_group);
 856         prev_bg_ptr = le64_to_cpu(prev_bg->bg_next_group);
 857
 858         status = ocfs2_journal_access(handle, alloc_inode, prev_bg_bh,
 859                                       OCFS2_JOURNAL_ACCESS_WRITE);
 860         if (status < 0) {
 861                 mlog_errno(status);
 862                 goto out_rollback;
 863         }
 864
 865         prev_bg->bg_next_group = bg->bg_next_group;
 866
 867         status = ocfs2_journal_dirty(handle, prev_bg_bh);
 868         if (status < 0) {
 869                 mlog_errno(status);
 870                 goto out_rollback;
 871         }
 872
 873         status = ocfs2_journal_access(handle, alloc_inode, bg_bh,
 874                                       OCFS2_JOURNAL_ACCESS_WRITE);
 875         if (status < 0) {
 876                 mlog_errno(status);
 877                 goto out_rollback;
 878         }
 879
 880         bg->bg_next_group = fe->id2.i_chain.cl_recs[chain].c_blkno;
 881
 882         status = ocfs2_journal_dirty(handle, bg_bh);
 883         if (status < 0) {
 884                 mlog_errno(status);
 885                 goto out_rollback;
 886         }
 887
 888         status = ocfs2_journal_access(handle, alloc_inode, fe_bh,
 889                                       OCFS2_JOURNAL_ACCESS_WRITE);
 890         if (status < 0) {
 891                 mlog_errno(status);
 892                 goto out_rollback;
 893         }
 894
 895         fe->id2.i_chain.cl_recs[chain].c_blkno = bg->bg_blkno;
 896
 897         status = ocfs2_journal_dirty(handle, fe_bh);
 898         if (status < 0) {
 899                 mlog_errno(status);
 900                 goto out_rollback;
 901         }
 902
 903         status = 0;
 904 out_rollback:
 905         if (status < 0) {
 906                 fe->id2.i_chain.cl_recs[chain].c_blkno = cpu_to_le64(fe_ptr);
 907                 bg->bg_next_group = cpu_to_le64(bg_ptr);
 908                 prev_bg->bg_next_group = cpu_to_le64(prev_bg_ptr);
 909         }
 910 out:
 911         mlog_exit(status);
 912         return status;
 913 }
 914
 915 static inline int ocfs2_block_group_reasonably_empty(struct ocfs2_group_desc *bg,
 916                                                      u32 wanted)
 917 {
 918         return le16_to_cpu(bg->bg_free_bits_count) > wanted;
 919 }
 920
 921 /* return 0 on success, -ENOSPC to keep searching and any other < 0
 922  * value on error. */
 923 static int ocfs2_cluster_group_search(struct inode *inode,
 924                                       struct buffer_head *group_bh,
 925                                       u32 bits_wanted, u32 min_bits,
 926                                       u16 *bit_off, u16 *bits_found)
 927 {
 928         int search = -ENOSPC;
 929         int ret;
 930         struct ocfs2_group_desc *gd = (struct ocfs2_group_desc *) group_bh->b_data;
 931         u16 tmp_off, tmp_found;
 932         unsigned int max_bits, gd_cluster_off;
 933
 934         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
 935
 936         if (gd->bg_free_bits_count) {
 937                 max_bits = le16_to_cpu(gd->bg_bits);
 938
 939                 /* Tail groups in cluster bitmaps which aren't cpg
 940                  * aligned are prone to partial extention by a failed
 941                  * fs resize. If the file system resize never got to
 942                  * update the dinode cluster count, then we don't want
 943                  * to trust any clusters past it, regardless of what
 944                  * the group descriptor says. */
 945                 gd_cluster_off = ocfs2_blocks_to_clusters(inode->i_sb,
 946                                                           le64_to_cpu(gd->bg_blkno));
 947                 if ((gd_cluster_off + max_bits) >
 948                     OCFS2_I(inode)->ip_clusters) {
 949                         max_bits = OCFS2_I(inode)->ip_clusters - gd_cluster_off;
 950                         mlog(0, "Desc %llu, bg_bits %u, clusters %u, use %u\n",
 951                              (unsigned long long)le64_to_cpu(gd->bg_blkno),
 952                              le16_to_cpu(gd->bg_bits),
 953                              OCFS2_I(inode)->ip_clusters, max_bits);
 954                 }
 955
 956                 ret = ocfs2_block_group_find_clear_bits(OCFS2_SB(inode->i_sb),
 957                                                         group_bh, bits_wanted,
 958                                                         max_bits,
 959                                                         &tmp_off, &tmp_found);
 960                 if (ret)
 961                         return ret;
 962
 963                 /* ocfs2_block_group_find_clear_bits() might
 964                  * return success, but we still want to return
 965                  * -ENOSPC unless it found the minimum number
 966                  * of bits. */
 967                 if (min_bits <= tmp_found) {
 968                         *bit_off = tmp_off;
 969                         *bits_found = tmp_found;
 970                         search = 0; /* success */
 971                 }
 972         }
 973
 974         return search;
 975 }
 976
 977 static int ocfs2_block_group_search(struct inode *inode,
 978                                     struct buffer_head *group_bh,
 979                                     u32 bits_wanted, u32 min_bits,
 980                                     u16 *bit_off, u16 *bits_found)
 981 {
 982         int ret = -ENOSPC;
 983         struct ocfs2_group_desc *bg = (struct ocfs2_group_desc *) group_bh->b_data;
 984
 985         BUG_ON(min_bits != 1);
 986         BUG_ON(ocfs2_is_cluster_bitmap(inode));
 987
 988         if (bg->bg_free_bits_count)
 989                 ret = ocfs2_block_group_find_clear_bits(OCFS2_SB(inode->i_sb),
 990                                                         group_bh, bits_wanted,
 991                                                         le16_to_cpu(bg->bg_bits),
 992                                                         bit_off, bits_found);
 993
 994         return ret;
 995 }
 996
 997 static int ocfs2_alloc_dinode_update_counts(struct inode *inode,
 998                                        handle_t *handle,
 999                                        struct buffer_head *di_bh,
1000                                        u32 num_bits,
1001                                        u16 chain)
1002 {
1003         int ret;
1004         u32 tmp_used;
1005         struct ocfs2_dinode *di = (struct ocfs2_dinode *) di_bh->b_data;
1006         struct ocfs2_chain_list *cl = (struct ocfs2_chain_list *) &di->id2.i_chain;
1007
1008         ret = ocfs2_journal_access(handle, inode, di_bh,
1009                                    OCFS2_JOURNAL_ACCESS_WRITE);
1010         if (ret < 0) {
1011                 mlog_errno(ret);
1012                 goto out;
1013         }
1014
1015         tmp_used = le32_to_cpu(di->id1.bitmap1.i_used);
1016         di->id1.bitmap1.i_used = cpu_to_le32(num_bits + tmp_used);
1017         le32_add_cpu(&cl->cl_recs[chain].c_free, -num_bits);
1018
1019         ret = ocfs2_journal_dirty(handle, di_bh);
1020         if (ret < 0)
1021                 mlog_errno(ret);
1022
1023 out:
1024         return ret;
1025 }
1026
1027 static int ocfs2_search_one_group(struct ocfs2_alloc_context *ac,
1028                                   handle_t *handle,
1029                                   u32 bits_wanted,
1030                                   u32 min_bits,
1031                                   u16 *bit_off,
1032                                   unsigned int *num_bits,
1033                                   u64 gd_blkno,
1034                                   u16 *bits_left)
1035 {
1036         int ret;
1037         u16 found;
1038         struct buffer_head *group_bh = NULL;
1039         struct ocfs2_group_desc *gd;
1040         struct inode *alloc_inode = ac->ac_inode;
1041
1042         ret = ocfs2_read_block(OCFS2_SB(alloc_inode->i_sb), gd_blkno,
1043                                &group_bh, OCFS2_BH_CACHED, alloc_inode);
1044         if (ret < 0) {
1045                 mlog_errno(ret);
1046                 return ret;
1047         }
1048
1049         gd = (struct ocfs2_group_desc *) group_bh->b_data;
1050         if (!OCFS2_IS_VALID_GROUP_DESC(gd)) {
1051                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, gd);
1052                 ret = -EIO;
1053                 goto out;
1054         }
1055
1056         ret = ac->ac_group_search(alloc_inode, group_bh, bits_wanted, min_bits,
1057                                   bit_off, &found);
1058         if (ret < 0) {
1059                 if (ret != -ENOSPC)
1060                         mlog_errno(ret);
1061                 goto out;
1062         }
1063
1064         *num_bits = found;
1065
1066         ret = ocfs2_alloc_dinode_update_counts(alloc_inode, handle, ac->ac_bh,
1067                                                *num_bits,
1068                                                le16_to_cpu(gd->bg_chain));
1069         if (ret < 0) {
1070                 mlog_errno(ret);
1071                 goto out;
1072         }
1073
1074         ret = ocfs2_block_group_set_bits(handle, alloc_inode, gd, group_bh,
1075                                          *bit_off, *num_bits);
1076         if (ret < 0)
1077                 mlog_errno(ret);
1078
1079         *bits_left = le16_to_cpu(gd->bg_free_bits_count);
1080
1081 out:
1082         brelse(group_bh);
1083
1084         return ret;
1085 }
1086
1087 static int ocfs2_search_chain(struct ocfs2_alloc_context *ac,
1088                               handle_t *handle,
1089                               u32 bits_wanted,
1090                               u32 min_bits,
1091                               u16 *bit_off,
1092                               unsigned int *num_bits,
1093                               u64 *bg_blkno,
1094                               u16 *bits_left)
1095 {
1096         int status;
1097         u16 chain, tmp_bits;
1098         u32 tmp_used;
1099         u64 next_group;
1100         struct inode *alloc_inode = ac->ac_inode;
1101         struct buffer_head *group_bh = NULL;
1102         struct buffer_head *prev_group_bh = NULL;
1103         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) ac->ac_bh->b_data;
1104         struct ocfs2_chain_list *cl = (struct ocfs2_chain_list *) &fe->id2.i_chain;
1105         struct ocfs2_group_desc *bg;
1106
1107         chain = ac->ac_chain;
1108         mlog(0, "trying to alloc %u bits from chain %u, inode %llu\n",
1109              bits_wanted, chain,
1110              (unsigned long long)OCFS2_I(alloc_inode)->ip_blkno);
1111
1112         status = ocfs2_read_block(OCFS2_SB(alloc_inode->i_sb),
1113                                   le64_to_cpu(cl->cl_recs[chain].c_blkno),
1114                                   &group_bh, OCFS2_BH_CACHED, alloc_inode);
1115         if (status < 0) {
1116                 mlog_errno(status);
1117                 goto bail;
1118         }
1119         bg = (struct ocfs2_group_desc *) group_bh->b_data;
1120         status = ocfs2_check_group_descriptor(alloc_inode->i_sb, fe, bg);
1121         if (status) {
1122                 mlog_errno(status);
1123                 goto bail;
1124         }
1125
1126         status = -ENOSPC;
1127         /* for now, the chain search is a bit simplistic. We just use
1128          * the 1st group with any empty bits. */
1129         while ((status = ac->ac_group_search(alloc_inode, group_bh,
1130                                              bits_wanted, min_bits, bit_off,
1131                                              &tmp_bits)) == -ENOSPC) {
1132                 if (!bg->bg_next_group)
1133                         break;
1134
1135                 if (prev_group_bh) {
1136                         brelse(prev_group_bh);
1137                         prev_group_bh = NULL;
1138                 }
1139                 next_group = le64_to_cpu(bg->bg_next_group);
1140                 prev_group_bh = group_bh;
1141                 group_bh = NULL;
1142                 status = ocfs2_read_block(OCFS2_SB(alloc_inode->i_sb),
1143                                           next_group, &group_bh,
1144                                           OCFS2_BH_CACHED, alloc_inode);
1145                 if (status < 0) {
1146                         mlog_errno(status);
1147                         goto bail;
1148                 }
1149                 bg = (struct ocfs2_group_desc *) group_bh->b_data;
1150                 status = ocfs2_check_group_descriptor(alloc_inode->i_sb, fe, bg);
1151                 if (status) {
1152                         mlog_errno(status);
1153                         goto bail;
1154                 }
1155         }
1156         if (status < 0) {
1157                 if (status != -ENOSPC)
1158                         mlog_errno(status);
1159                 goto bail;
1160         }
1161
1162         mlog(0, "alloc succeeds: we give %u bits from block group %llu\n",
1163              tmp_bits, (unsigned long long)le64_to_cpu(bg->bg_blkno));
1164
1165         *num_bits = tmp_bits;
1166
1167         BUG_ON(*num_bits == 0);
1168
1169         /*
1170          * Keep track of previous block descriptor read. When
1171          * we find a target, if we have read more than X
1172          * number of descriptors, and the target is reasonably
1173          * empty, relink him to top of his chain.
1174          *
1175          * We've read 0 extra blocks and only send one more to
1176          * the transaction, yet the next guy to search has a
1177          * much easier time.
1178          *
1179          * Do this *after* figuring out how many bits we're taking out
1180          * of our target group.
1181          */
1182         if (ac->ac_allow_chain_relink &&
1183             (prev_group_bh) &&
1184             (ocfs2_block_group_reasonably_empty(bg, *num_bits))) {
1185                 status = ocfs2_relink_block_group(handle, alloc_inode,
1186                                                   ac->ac_bh, group_bh,
1187                                                   prev_group_bh, chain);
1188                 if (status < 0) {
1189                         mlog_errno(status);
1190                         goto bail;
1191                 }
1192         }
1193
1194         /* Ok, claim our bits now: set the info on dinode, chainlist
1195          * and then the group */
1196         status = ocfs2_journal_access(handle,
1197                                       alloc_inode,
1198                                       ac->ac_bh,
1199                                       OCFS2_JOURNAL_ACCESS_WRITE);
1200         if (status < 0) {
1201                 mlog_errno(status);
1202                 goto bail;
1203         }
1204
1205         tmp_used = le32_to_cpu(fe->id1.bitmap1.i_used);
1206         fe->id1.bitmap1.i_used = cpu_to_le32(*num_bits + tmp_used);
1207         le32_add_cpu(&cl->cl_recs[chain].c_free, -(*num_bits));
1208
1209         status = ocfs2_journal_dirty(handle,
1210                                      ac->ac_bh);
1211         if (status < 0) {
1212                 mlog_errno(status);
1213                 goto bail;
1214         }
1215
1216         status = ocfs2_block_group_set_bits(handle,
1217                                             alloc_inode,
1218                                             bg,
1219                                             group_bh,
1220                                             *bit_off,
1221                                             *num_bits);
1222         if (status < 0) {
1223                 mlog_errno(status);
1224                 goto bail;
1225         }
1226
1227         mlog(0, "Allocated %u bits from suballocator %llu\n", *num_bits,
1228              (unsigned long long)le64_to_cpu(fe->i_blkno));
1229
1230         *bg_blkno = le64_to_cpu(bg->bg_blkno);
1231         *bits_left = le16_to_cpu(bg->bg_free_bits_count);
1232 bail:
1233         if (group_bh)
1234                 brelse(group_bh);
1235         if (prev_group_bh)
1236                 brelse(prev_group_bh);
1237
1238         mlog_exit(status);
1239         return status;
1240 }
1241
1242 /* will give out up to bits_wanted contiguous bits. */
1243 static int ocfs2_claim_suballoc_bits(struct ocfs2_super *osb,
1244                                      struct ocfs2_alloc_context *ac,
1245                                      handle_t *handle,
1246                                      u32 bits_wanted,
1247                                      u32 min_bits,
1248                                      u16 *bit_off,
1249                                      unsigned int *num_bits,
1250                                      u64 *bg_blkno)
1251 {
1252         int status;
1253         u16 victim, i;
1254         u16 bits_left = 0;
1255         u64 hint_blkno = ac->ac_last_group;
1256         struct ocfs2_chain_list *cl;
1257         struct ocfs2_dinode *fe;
1258
1259         mlog_entry_void();
1260
1261         BUG_ON(ac->ac_bits_given >= ac->ac_bits_wanted);
1262         BUG_ON(bits_wanted > (ac->ac_bits_wanted - ac->ac_bits_given));
1263         BUG_ON(!ac->ac_bh);
1264
1265         fe = (struct ocfs2_dinode *) ac->ac_bh->b_data;
1266         if (!OCFS2_IS_VALID_DINODE(fe)) {
1267                 OCFS2_RO_ON_INVALID_DINODE(osb->sb, fe);
1268                 status = -EIO;
1269                 goto bail;
1270         }
1271         if (le32_to_cpu(fe->id1.bitmap1.i_used) >=
1272             le32_to_cpu(fe->id1.bitmap1.i_total)) {
1273                 ocfs2_error(osb->sb, "Chain allocator dinode %llu has %u used "
1274                             "bits but only %u total.",
1275                             (unsigned long long)le64_to_cpu(fe->i_blkno),
1276                             le32_to_cpu(fe->id1.bitmap1.i_used),
1277                             le32_to_cpu(fe->id1.bitmap1.i_total));
1278                 status = -EIO;
1279                 goto bail;
1280         }
1281
1282         if (hint_blkno) {
1283                 /* Attempt to short-circuit the usual search mechanism
1284                  * by jumping straight to the most recently used
1285                  * allocation group. This helps us mantain some
1286                  * contiguousness across allocations. */
1287                 status = ocfs2_search_one_group(ac, handle, bits_wanted,
1288                                                 min_bits, bit_off, num_bits,
1289                                                 hint_blkno, &bits_left);
1290                 if (!status) {
1291                         /* Be careful to update *bg_blkno here as the
1292                          * caller is expecting it to be filled in, and
1293                          * ocfs2_search_one_group() won't do that for
1294                          * us. */
1295                         *bg_blkno = hint_blkno;
1296                         goto set_hint;
1297                 }
1298                 if (status < 0 && status != -ENOSPC) {
1299                         mlog_errno(status);
1300                         goto bail;
1301                 }
1302         }
1303
1304         cl = (struct ocfs2_chain_list *) &fe->id2.i_chain;
1305
1306         victim = ocfs2_find_victim_chain(cl);
1307         ac->ac_chain = victim;
1308         ac->ac_allow_chain_relink = 1;
1309
1310         status = ocfs2_search_chain(ac, handle, bits_wanted, min_bits, bit_off,
1311                                     num_bits, bg_blkno, &bits_left);
1312         if (!status)
1313                 goto set_hint;
1314         if (status < 0 && status != -ENOSPC) {
1315                 mlog_errno(status);
1316                 goto bail;
1317         }
1318
1319         mlog(0, "Search of victim chain %u came up with nothing, "
1320              "trying all chains now.\n", victim);
1321
1322         /* If we didn't pick a good victim, then just default to
1323          * searching each chain in order. Don't allow chain relinking
1324          * because we only calculate enough journal credits for one
1325          * relink per alloc. */
1326         ac->ac_allow_chain_relink = 0;
1327         for (i = 0; i < le16_to_cpu(cl->cl_next_free_rec); i ++) {
1328                 if (i == victim)
1329                         continue;
1330                 if (!cl->cl_recs[i].c_free)
1331                         continue;
1332
1333                 ac->ac_chain = i;
1334                 status = ocfs2_search_chain(ac, handle, bits_wanted, min_bits,
1335                                             bit_off, num_bits, bg_blkno,
1336                                             &bits_left);
1337                 if (!status)
1338                         break;
1339                 if (status < 0 && status != -ENOSPC) {
1340                         mlog_errno(status);
1341                         goto bail;
1342                 }
1343         }
1344
1345 set_hint:
1346         if (status != -ENOSPC) {
1347                 /* If the next search of this group is not likely to
1348                  * yield a suitable extent, then we reset the last
1349                  * group hint so as to not waste a disk read */
1350                 if (bits_left < min_bits)
1351                         ac->ac_last_group = 0;
1352                 else
1353                         ac->ac_last_group = *bg_blkno;
1354         }
1355
1356 bail:
1357         mlog_exit(status);
1358         return status;
1359 }
1360
1361 int ocfs2_claim_metadata(struct ocfs2_super *osb,
1362                          handle_t *handle,
1363                          struct ocfs2_alloc_context *ac,
1364                          u32 bits_wanted,
1365                          u16 *suballoc_bit_start,
1366                          unsigned int *num_bits,
1367                          u64 *blkno_start)
1368 {
1369         int status;
1370         u64 bg_blkno;
1371
1372         BUG_ON(!ac);
1373         BUG_ON(ac->ac_bits_wanted < (ac->ac_bits_given + bits_wanted));
1374         BUG_ON(ac->ac_which != OCFS2_AC_USE_META);
1375
1376         status = ocfs2_claim_suballoc_bits(osb,
1377                                            ac,
1378                                            handle,
1379                                            bits_wanted,
1380                                            1,
1381                                            suballoc_bit_start,
1382                                            num_bits,
1383                                            &bg_blkno);
1384         if (status < 0) {
1385                 mlog_errno(status);
1386                 goto bail;
1387         }
1388         atomic_inc(&osb->alloc_stats.bg_allocs);
1389
1390         *blkno_start = bg_blkno + (u64) *suballoc_bit_start;
1391         ac->ac_bits_given += (*num_bits);
1392         status = 0;
1393 bail:
1394         mlog_exit(status);
1395         return status;
1396 }
1397
1398 int ocfs2_claim_new_inode(struct ocfs2_super *osb,
1399                           handle_t *handle,
1400                           struct ocfs2_alloc_context *ac,
1401                           u16 *suballoc_bit,
1402                           u64 *fe_blkno)
1403 {
1404         int status;
1405         unsigned int num_bits;
1406         u64 bg_blkno;
1407
1408         mlog_entry_void();
1409
1410         BUG_ON(!ac);
1411         BUG_ON(ac->ac_bits_given != 0);
1412         BUG_ON(ac->ac_bits_wanted != 1);
1413         BUG_ON(ac->ac_which != OCFS2_AC_USE_INODE);
1414
1415         status = ocfs2_claim_suballoc_bits(osb,
1416                                            ac,
1417                                            handle,
1418                                            1,
1419                                            1,
1420                                            suballoc_bit,
1421                                            &num_bits,
1422                                            &bg_blkno);
1423         if (status < 0) {
1424                 mlog_errno(status);
1425                 goto bail;
1426         }
1427         atomic_inc(&osb->alloc_stats.bg_allocs);
1428
1429         BUG_ON(num_bits != 1);
1430
1431         *fe_blkno = bg_blkno + (u64) (*suballoc_bit);
1432         ac->ac_bits_given++;
1433         status = 0;
1434 bail:
1435         mlog_exit(status);
1436         return status;
1437 }
1438
1439 /* translate a group desc. blkno and it's bitmap offset into
1440  * disk cluster offset. */
1441 static inline u32 ocfs2_desc_bitmap_to_cluster_off(struct inode *inode,
1442                                                    u64 bg_blkno,
1443                                                    u16 bg_bit_off)
1444 {
1445         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
1446         u32 cluster = 0;
1447
1448         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
1449
1450         if (bg_blkno != osb->first_cluster_group_blkno)
1451                 cluster = ocfs2_blocks_to_clusters(inode->i_sb, bg_blkno);
1452         cluster += (u32) bg_bit_off;
1453         return cluster;
1454 }
1455
1456 /* given a cluster offset, calculate which block group it belongs to
1457  * and return that block offset. */
1458 u64 ocfs2_which_cluster_group(struct inode *inode, u32 cluster)
1459 {
1460         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
1461         u32 group_no;
1462
1463         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
1464
1465         group_no = cluster / osb->bitmap_cpg;
1466         if (!group_no)
1467                 return osb->first_cluster_group_blkno;
1468         return ocfs2_clusters_to_blocks(inode->i_sb,
1469                                         group_no * osb->bitmap_cpg);
1470 }
1471
1472 /* given the block number of a cluster start, calculate which cluster
1473  * group and descriptor bitmap offset that corresponds to. */
1474 static inline void ocfs2_block_to_cluster_group(struct inode *inode,
1475                                                 u64 data_blkno,
1476                                                 u64 *bg_blkno,
1477                                                 u16 *bg_bit_off)
1478 {
1479         struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
1480         u32 data_cluster = ocfs2_blocks_to_clusters(osb->sb, data_blkno);
1481
1482         BUG_ON(!ocfs2_is_cluster_bitmap(inode));
1483
1484         *bg_blkno = ocfs2_which_cluster_group(inode,
1485                                               data_cluster);
1486
1487         if (*bg_blkno == osb->first_cluster_group_blkno)
1488                 *bg_bit_off = (u16) data_cluster;
1489         else
1490                 *bg_bit_off = (u16) ocfs2_blocks_to_clusters(osb->sb,
1491                                                              data_blkno - *bg_blkno);
1492 }
1493
1494 /*
1495  * min_bits - minimum contiguous chunk from this total allocation we
1496  * can handle. set to what we asked for originally for a full
1497  * contig. allocation, set to '1' to indicate we can deal with extents
1498  * of any size.
1499  */
1500 int __ocfs2_claim_clusters(struct ocfs2_super *osb,
1501                            handle_t *handle,
1502                            struct ocfs2_alloc_context *ac,
1503                            u32 min_clusters,
1504                            u32 max_clusters,
1505                            u32 *cluster_start,
1506                            u32 *num_clusters)
1507 {
1508         int status;
1509         unsigned int bits_wanted = max_clusters;
1510         u64 bg_blkno = 0;
1511         u16 bg_bit_off;
1512
1513         mlog_entry_void();
1514
1515         BUG_ON(ac->ac_bits_given >= ac->ac_bits_wanted);
1516
1517         BUG_ON(ac->ac_which != OCFS2_AC_USE_LOCAL
1518                && ac->ac_which != OCFS2_AC_USE_MAIN);
1519
1520         if (ac->ac_which == OCFS2_AC_USE_LOCAL) {
1521                 status = ocfs2_claim_local_alloc_bits(osb,
1522                                                       handle,
1523                                                       ac,
1524                                                       bits_wanted,
1525                                                       cluster_start,
1526                                                       num_clusters);
1527                 if (!status)
1528                         atomic_inc(&osb->alloc_stats.local_data);
1529         } else {
1530                 if (min_clusters > (osb->bitmap_cpg - 1)) {
1531                         /* The only paths asking for contiguousness
1532                          * should know about this already. */
1533                         mlog(ML_ERROR, "minimum allocation requested %u exceeds "
1534                              "group bitmap size %u!\n", min_clusters,
1535                              osb->bitmap_cpg);
1536                         status = -ENOSPC;
1537                         goto bail;
1538                 }
1539                 /* clamp the current request down to a realistic size. */
1540                 if (bits_wanted > (osb->bitmap_cpg - 1))
1541                         bits_wanted = osb->bitmap_cpg - 1;
1542
1543                 status = ocfs2_claim_suballoc_bits(osb,
1544                                                    ac,
1545                                                    handle,
1546                                                    bits_wanted,
1547                                                    min_clusters,
1548                                                    &bg_bit_off,
1549                                                    num_clusters,
1550                                                    &bg_blkno);
1551                 if (!status) {
1552                         *cluster_start =
1553                                 ocfs2_desc_bitmap_to_cluster_off(ac->ac_inode,
1554                                                                  bg_blkno,
1555                                                                  bg_bit_off);
1556                         atomic_inc(&osb->alloc_stats.bitmap_data);
1557                 }
1558         }
1559         if (status < 0) {
1560                 if (status != -ENOSPC)
1561                         mlog_errno(status);
1562                 goto bail;
1563         }
1564
1565         ac->ac_bits_given += *num_clusters;
1566
1567 bail:
1568         mlog_exit(status);
1569         return status;
1570 }
1571
1572 int ocfs2_claim_clusters(struct ocfs2_super *osb,
1573                          handle_t *handle,
1574                          struct ocfs2_alloc_context *ac,
1575                          u32 min_clusters,
1576                          u32 *cluster_start,
1577                          u32 *num_clusters)
1578 {
1579         unsigned int bits_wanted = ac->ac_bits_wanted - ac->ac_bits_given;
1580
1581         return __ocfs2_claim_clusters(osb, handle, ac, min_clusters,
1582                                       bits_wanted, cluster_start, num_clusters);
1583 }
1584
1585 static inline int ocfs2_block_group_clear_bits(handle_t *handle,
1586                                                struct inode *alloc_inode,
1587                                                struct ocfs2_group_desc *bg,
1588                                                struct buffer_head *group_bh,
1589                                                unsigned int bit_off,
1590                                                unsigned int num_bits)
1591 {
1592         int status;
1593         unsigned int tmp;
1594         int journal_type = OCFS2_JOURNAL_ACCESS_WRITE;
1595         struct ocfs2_group_desc *undo_bg = NULL;
1596
1597         mlog_entry_void();
1598
1599         if (!OCFS2_IS_VALID_GROUP_DESC(bg)) {
1600                 OCFS2_RO_ON_INVALID_GROUP_DESC(alloc_inode->i_sb, bg);
1601                 status = -EIO;
1602                 goto bail;
1603         }
1604
1605         mlog(0, "off = %u, num = %u\n", bit_off, num_bits);
1606
1607         if (ocfs2_is_cluster_bitmap(alloc_inode))
1608                 journal_type = OCFS2_JOURNAL_ACCESS_UNDO;
1609
1610         status = ocfs2_journal_access(handle, alloc_inode, group_bh,
1611                                       journal_type);
1612         if (status < 0) {
1613                 mlog_errno(status);
1614                 goto bail;
1615         }
1616
1617         if (ocfs2_is_cluster_bitmap(alloc_inode))
1618                 undo_bg = (struct ocfs2_group_desc *) bh2jh(group_bh)->b_committed_data;
1619
1620         tmp = num_bits;
1621         while(tmp--) {
1622                 ocfs2_clear_bit((bit_off + tmp),
1623                                 (unsigned long *) bg->bg_bitmap);
1624                 if (ocfs2_is_cluster_bitmap(alloc_inode))
1625                         ocfs2_set_bit(bit_off + tmp,
1626                                       (unsigned long *) undo_bg->bg_bitmap);
1627         }
1628         le16_add_cpu(&bg->bg_free_bits_count, num_bits);
1629
1630         status = ocfs2_journal_dirty(handle, group_bh);
1631         if (status < 0)
1632                 mlog_errno(status);
1633 bail:
1634         return status;
1635 }
1636
1637 /*
1638  * expects the suballoc inode to already be locked.
1639  */
1640 int ocfs2_free_suballoc_bits(handle_t *handle,
1641                              struct inode *alloc_inode,
1642                              struct buffer_head *alloc_bh,
1643                              unsigned int start_bit,
1644                              u64 bg_blkno,
1645                              unsigned int count)
1646 {
1647         int status = 0;
1648         u32 tmp_used;
1649         struct ocfs2_super *osb = OCFS2_SB(alloc_inode->i_sb);
1650         struct ocfs2_dinode *fe = (struct ocfs2_dinode *) alloc_bh->b_data;
1651         struct ocfs2_chain_list *cl = &fe->id2.i_chain;
1652         struct buffer_head *group_bh = NULL;
1653         struct ocfs2_group_desc *group;
1654
1655         mlog_entry_void();
1656
1657         if (!OCFS2_IS_VALID_DINODE(fe)) {
1658                 OCFS2_RO_ON_INVALID_DINODE(alloc_inode->i_sb, fe);
1659                 status = -EIO;
1660                 goto bail;
1661         }
1662         BUG_ON((count + start_bit) > ocfs2_bits_per_group(cl));
1663
1664         mlog(0, "%llu: freeing %u bits from group %llu, starting at %u\n",
1665              (unsigned long long)OCFS2_I(alloc_inode)->ip_blkno, count,
1666              (unsigned long long)bg_blkno, start_bit);
1667
1668         status = ocfs2_read_block(osb, bg_blkno, &group_bh, OCFS2_BH_CACHED,
1669                                   alloc_inode);
1670         if (status < 0) {
1671                 mlog_errno(status);
1672                 goto bail;
1673         }
1674
1675         group = (struct ocfs2_group_desc *) group_bh->b_data;
1676         status = ocfs2_check_group_descriptor(alloc_inode->i_sb, fe, group);
1677         if (status) {
1678                 mlog_errno(status);
1679                 goto bail;
1680         }
1681         BUG_ON((count + start_bit) > le16_to_cpu(group->bg_bits));
1682
1683         status = ocfs2_block_group_clear_bits(handle, alloc_inode,
1684                                               group, group_bh,
1685                                               start_bit, count);
1686         if (status < 0) {
1687                 mlog_errno(status);
1688                 goto bail;
1689         }
1690
1691         status = ocfs2_journal_access(handle, alloc_inode, alloc_bh,
1692                                       OCFS2_JOURNAL_ACCESS_WRITE);
1693         if (status < 0) {
1694                 mlog_errno(status);
1695                 goto bail;
1696         }
1697
1698         le32_add_cpu(&cl->cl_recs[le16_to_cpu(group->bg_chain)].c_free,
1699                      count);
1700         tmp_used = le32_to_cpu(fe->id1.bitmap1.i_used);
1701         fe->id1.bitmap1.i_used = cpu_to_le32(tmp_used - count);
1702
1703         status = ocfs2_journal_dirty(handle, alloc_bh);
1704         if (status < 0) {
1705                 mlog_errno(status);
1706                 goto bail;
1707         }
1708
1709 bail:
1710         if (group_bh)
1711                 brelse(group_bh);
1712
1713         mlog_exit(status);
1714         return status;
1715 }
1716
1717 int ocfs2_free_dinode(handle_t *handle,
1718                       struct inode *inode_alloc_inode,
1719                       struct buffer_head *inode_alloc_bh,
1720                       struct ocfs2_dinode *di)
1721 {
1722         u64 blk = le64_to_cpu(di->i_blkno);
1723         u16 bit = le16_to_cpu(di->i_suballoc_bit);
1724         u64 bg_blkno = ocfs2_which_suballoc_group(blk, bit);
1725
1726         return ocfs2_free_suballoc_bits(handle, inode_alloc_inode,
1727                                         inode_alloc_bh, bit, bg_blkno, 1);
1728 }
1729
1730 int ocfs2_free_clusters(handle_t *handle,
1731                        struct inode *bitmap_inode,
1732                        struct buffer_head *bitmap_bh,
1733                        u64 start_blk,
1734                        unsigned int num_clusters)
1735 {
1736         int status;
1737         u16 bg_start_bit;
1738         u64 bg_blkno;
1739         struct ocfs2_dinode *fe;
1740
1741         /* You can't ever have a contiguous set of clusters
1742          * bigger than a block group bitmap so we never have to worry
1743          * about looping on them. */
1744
1745         mlog_entry_void();
1746
1747         /* This is expensive. We can safely remove once this stuff has
1748          * gotten tested really well. */
1749         BUG_ON(start_blk != ocfs2_clusters_to_blocks(bitmap_inode->i_sb, ocfs2_blocks_to_clusters(bitmap_inode->i_sb, start_blk)));
1750
1751         fe = (struct ocfs2_dinode *) bitmap_bh->b_data;
1752
1753         ocfs2_block_to_cluster_group(bitmap_inode, start_blk, &bg_blkno,
1754                                      &bg_start_bit);
1755
1756         mlog(0, "want to free %u clusters starting at block %llu\n",
1757              num_clusters, (unsigned long long)start_blk);
1758         mlog(0, "bg_blkno = %llu, bg_start_bit = %u\n",
1759              (unsigned long long)bg_blkno, bg_start_bit);
1760
1761         status = ocfs2_free_suballoc_bits(handle, bitmap_inode, bitmap_bh,
1762                                           bg_start_bit, bg_blkno,
1763                                           num_clusters);
1764         if (status < 0)
1765                 mlog_errno(status);
1766
1767         mlog_exit(status);
1768         return status;
1769 }
1770
1771 static inline void ocfs2_debug_bg(struct ocfs2_group_desc *bg)
1772 {
1773         printk("Block Group:\n");
1774         printk("bg_signature:       %s\n", bg->bg_signature);
1775         printk("bg_size:            %u\n", bg->bg_size);
1776         printk("bg_bits:            %u\n", bg->bg_bits);
1777         printk("bg_free_bits_count: %u\n", bg->bg_free_bits_count);
1778         printk("bg_chain:           %u\n", bg->bg_chain);
1779         printk("bg_generation:      %u\n", le32_to_cpu(bg->bg_generation));
1780         printk("bg_next_group:      %llu\n",
1781                (unsigned long long)bg->bg_next_group);
1782         printk("bg_parent_dinode:   %llu\n",
1783                (unsigned long long)bg->bg_parent_dinode);
1784         printk("bg_blkno:           %llu\n",
1785                (unsigned long long)bg->bg_blkno);
1786 }
1787
1788 static inline void ocfs2_debug_suballoc_inode(struct ocfs2_dinode *fe)
1789 {
1790         int i;
1791
1792         printk("Suballoc Inode %llu:\n", (unsigned long long)fe->i_blkno);
1793         printk("i_signature:                  %s\n", fe->i_signature);
1794         printk("i_size:                       %llu\n",
1795                (unsigned long long)fe->i_size);
1796         printk("i_clusters:                   %u\n", fe->i_clusters);
1797         printk("i_generation:                 %u\n",
1798                le32_to_cpu(fe->i_generation));
1799         printk("id1.bitmap1.i_used:           %u\n",
1800                le32_to_cpu(fe->id1.bitmap1.i_used));
1801         printk("id1.bitmap1.i_total:          %u\n",
1802                le32_to_cpu(fe->id1.bitmap1.i_total));
1803         printk("id2.i_chain.cl_cpg:           %u\n", fe->id2.i_chain.cl_cpg);
1804         printk("id2.i_chain.cl_bpc:           %u\n", fe->id2.i_chain.cl_bpc);
1805         printk("id2.i_chain.cl_count:         %u\n", fe->id2.i_chain.cl_count);
1806         printk("id2.i_chain.cl_next_free_rec: %u\n",
1807                fe->id2.i_chain.cl_next_free_rec);
1808         for(i = 0; i < fe->id2.i_chain.cl_next_free_rec; i++) {
1809                 printk("fe->id2.i_chain.cl_recs[%d].c_free:  %u\n", i,
1810                        fe->id2.i_chain.cl_recs[i].c_free);
1811                 printk("fe->id2.i_chain.cl_recs[%d].c_total: %u\n", i,
1812                        fe->id2.i_chain.cl_recs[i].c_total);
1813                 printk("fe->id2.i_chain.cl_recs[%d].c_blkno: %llu\n", i,
1814                        (unsigned long long)fe->id2.i_chain.cl_recs[i].c_blkno);
1815         }
1816 }