linux/fs/xfs/libxfs/xfs_ialloc.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   4 * All Rights Reserved.
   5 */
   6#include "xfs.h"
   7#include "xfs_fs.h"
   8#include "xfs_shared.h"
   9#include "xfs_format.h"
  10#include "xfs_log_format.h"
  11#include "xfs_trans_resv.h"
  12#include "xfs_bit.h"
  13#include "xfs_mount.h"
  14#include "xfs_inode.h"
  15#include "xfs_btree.h"
  16#include "xfs_ialloc.h"
  17#include "xfs_ialloc_btree.h"
  18#include "xfs_alloc.h"
  19#include "xfs_errortag.h"
  20#include "xfs_error.h"
  21#include "xfs_bmap.h"
  22#include "xfs_trans.h"
  23#include "xfs_buf_item.h"
  24#include "xfs_icreate_item.h"
  25#include "xfs_icache.h"
  26#include "xfs_trace.h"
  27#include "xfs_log.h"
  28#include "xfs_rmap.h"
  29#include "xfs_ag.h"
  30
  31/*
  32 * Lookup a record by ino in the btree given by cur.
  33 */
  34int                                     /* error */
  35xfs_inobt_lookup(
  36        struct xfs_btree_cur    *cur,   /* btree cursor */
  37        xfs_agino_t             ino,    /* starting inode of chunk */
  38        xfs_lookup_t            dir,    /* <=, >=, == */
  39        int                     *stat)  /* success/failure */
  40{
  41        cur->bc_rec.i.ir_startino = ino;
  42        cur->bc_rec.i.ir_holemask = 0;
  43        cur->bc_rec.i.ir_count = 0;
  44        cur->bc_rec.i.ir_freecount = 0;
  45        cur->bc_rec.i.ir_free = 0;
  46        return xfs_btree_lookup(cur, dir, stat);
  47}
  48
  49/*
  50 * Update the record referred to by cur to the value given.
  51 * This either works (return 0) or gets an EFSCORRUPTED error.
  52 */
  53STATIC int                              /* error */
  54xfs_inobt_update(
  55        struct xfs_btree_cur    *cur,   /* btree cursor */
  56        xfs_inobt_rec_incore_t  *irec)  /* btree record */
  57{
  58        union xfs_btree_rec     rec;
  59
  60        rec.inobt.ir_startino = cpu_to_be32(irec->ir_startino);
  61        if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
  62                rec.inobt.ir_u.sp.ir_holemask = cpu_to_be16(irec->ir_holemask);
  63                rec.inobt.ir_u.sp.ir_count = irec->ir_count;
  64                rec.inobt.ir_u.sp.ir_freecount = irec->ir_freecount;
  65        } else {
  66                /* ir_holemask/ir_count not supported on-disk */
  67                rec.inobt.ir_u.f.ir_freecount = cpu_to_be32(irec->ir_freecount);
  68        }
  69        rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
  70        return xfs_btree_update(cur, &rec);
  71}
  72
  73/* Convert on-disk btree record to incore inobt record. */
  74void
  75xfs_inobt_btrec_to_irec(
  76        struct xfs_mount                *mp,
  77        union xfs_btree_rec             *rec,
  78        struct xfs_inobt_rec_incore     *irec)
  79{
  80        irec->ir_startino = be32_to_cpu(rec->inobt.ir_startino);
  81        if (xfs_sb_version_hassparseinodes(&mp->m_sb)) {
  82                irec->ir_holemask = be16_to_cpu(rec->inobt.ir_u.sp.ir_holemask);
  83                irec->ir_count = rec->inobt.ir_u.sp.ir_count;
  84                irec->ir_freecount = rec->inobt.ir_u.sp.ir_freecount;
  85        } else {
  86                /*
  87                 * ir_holemask/ir_count not supported on-disk. Fill in hardcoded
  88                 * values for full inode chunks.
  89                 */
  90                irec->ir_holemask = XFS_INOBT_HOLEMASK_FULL;
  91                irec->ir_count = XFS_INODES_PER_CHUNK;
  92                irec->ir_freecount =
  93                                be32_to_cpu(rec->inobt.ir_u.f.ir_freecount);
  94        }
  95        irec->ir_free = be64_to_cpu(rec->inobt.ir_free);
  96}
  97
  98/*
  99 * Get the data from the pointed-to record.
 100 */
 101int
 102xfs_inobt_get_rec(
 103        struct xfs_btree_cur            *cur,
 104        struct xfs_inobt_rec_incore     *irec,
 105        int                             *stat)
 106{
 107        struct xfs_mount                *mp = cur->bc_mp;
 108        xfs_agnumber_t                  agno = cur->bc_ag.pag->pag_agno;
 109        union xfs_btree_rec             *rec;
 110        int                             error;
 111        uint64_t                        realfree;
 112
 113        error = xfs_btree_get_rec(cur, &rec, stat);
 114        if (error || *stat == 0)
 115                return error;
 116
 117        xfs_inobt_btrec_to_irec(mp, rec, irec);
 118
 119        if (!xfs_verify_agino(mp, agno, irec->ir_startino))
 120                goto out_bad_rec;
 121        if (irec->ir_count < XFS_INODES_PER_HOLEMASK_BIT ||
 122            irec->ir_count > XFS_INODES_PER_CHUNK)
 123                goto out_bad_rec;
 124        if (irec->ir_freecount > XFS_INODES_PER_CHUNK)
 125                goto out_bad_rec;
 126
 127        /* if there are no holes, return the first available offset */
 128        if (!xfs_inobt_issparse(irec->ir_holemask))
 129                realfree = irec->ir_free;
 130        else
 131                realfree = irec->ir_free & xfs_inobt_irec_to_allocmask(irec);
 132        if (hweight64(realfree) != irec->ir_freecount)
 133                goto out_bad_rec;
 134
 135        return 0;
 136
 137out_bad_rec:
 138        xfs_warn(mp,
 139                "%s Inode BTree record corruption in AG %d detected!",
 140                cur->bc_btnum == XFS_BTNUM_INO ? "Used" : "Free", agno);
 141        xfs_warn(mp,
 142"start inode 0x%x, count 0x%x, free 0x%x freemask 0x%llx, holemask 0x%x",
 143                irec->ir_startino, irec->ir_count, irec->ir_freecount,
 144                irec->ir_free, irec->ir_holemask);
 145        return -EFSCORRUPTED;
 146}
 147
 148/*
 149 * Insert a single inobt record. Cursor must already point to desired location.
 150 */
 151int
 152xfs_inobt_insert_rec(
 153        struct xfs_btree_cur    *cur,
 154        uint16_t                holemask,
 155        uint8_t                 count,
 156        int32_t                 freecount,
 157        xfs_inofree_t           free,
 158        int                     *stat)
 159{
 160        cur->bc_rec.i.ir_holemask = holemask;
 161        cur->bc_rec.i.ir_count = count;
 162        cur->bc_rec.i.ir_freecount = freecount;
 163        cur->bc_rec.i.ir_free = free;
 164        return xfs_btree_insert(cur, stat);
 165}
 166
 167/*
 168 * Insert records describing a newly allocated inode chunk into the inobt.
 169 */
 170STATIC int
 171xfs_inobt_insert(
 172        struct xfs_mount        *mp,
 173        struct xfs_trans        *tp,
 174        struct xfs_buf          *agbp,
 175        struct xfs_perag        *pag,
 176        xfs_agino_t             newino,
 177        xfs_agino_t             newlen,
 178        xfs_btnum_t             btnum)
 179{
 180        struct xfs_btree_cur    *cur;
 181        xfs_agino_t             thisino;
 182        int                     i;
 183        int                     error;
 184
 185        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, btnum);
 186
 187        for (thisino = newino;
 188             thisino < newino + newlen;
 189             thisino += XFS_INODES_PER_CHUNK) {
 190                error = xfs_inobt_lookup(cur, thisino, XFS_LOOKUP_EQ, &i);
 191                if (error) {
 192                        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
 193                        return error;
 194                }
 195                ASSERT(i == 0);
 196
 197                error = xfs_inobt_insert_rec(cur, XFS_INOBT_HOLEMASK_FULL,
 198                                             XFS_INODES_PER_CHUNK,
 199                                             XFS_INODES_PER_CHUNK,
 200                                             XFS_INOBT_ALL_FREE, &i);
 201                if (error) {
 202                        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
 203                        return error;
 204                }
 205                ASSERT(i == 1);
 206        }
 207
 208        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
 209
 210        return 0;
 211}
 212
 213/*
 214 * Verify that the number of free inodes in the AGI is correct.
 215 */
 216#ifdef DEBUG
 217static int
 218xfs_check_agi_freecount(
 219        struct xfs_btree_cur    *cur)
 220{
 221        if (cur->bc_nlevels == 1) {
 222                xfs_inobt_rec_incore_t rec;
 223                int             freecount = 0;
 224                int             error;
 225                int             i;
 226
 227                error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
 228                if (error)
 229                        return error;
 230
 231                do {
 232                        error = xfs_inobt_get_rec(cur, &rec, &i);
 233                        if (error)
 234                                return error;
 235
 236                        if (i) {
 237                                freecount += rec.ir_freecount;
 238                                error = xfs_btree_increment(cur, 0, &i);
 239                                if (error)
 240                                        return error;
 241                        }
 242                } while (i == 1);
 243
 244                if (!XFS_FORCED_SHUTDOWN(cur->bc_mp))
 245                        ASSERT(freecount == cur->bc_ag.pag->pagi_freecount);
 246        }
 247        return 0;
 248}
 249#else
 250#define xfs_check_agi_freecount(cur)    0
 251#endif
 252
 253/*
 254 * Initialise a new set of inodes. When called without a transaction context
 255 * (e.g. from recovery) we initiate a delayed write of the inode buffers rather
 256 * than logging them (which in a transaction context puts them into the AIL
 257 * for writeback rather than the xfsbufd queue).
 258 */
 259int
 260xfs_ialloc_inode_init(
 261        struct xfs_mount        *mp,
 262        struct xfs_trans        *tp,
 263        struct list_head        *buffer_list,
 264        int                     icount,
 265        xfs_agnumber_t          agno,
 266        xfs_agblock_t           agbno,
 267        xfs_agblock_t           length,
 268        unsigned int            gen)
 269{
 270        struct xfs_buf          *fbuf;
 271        struct xfs_dinode       *free;
 272        int                     nbufs;
 273        int                     version;
 274        int                     i, j;
 275        xfs_daddr_t             d;
 276        xfs_ino_t               ino = 0;
 277        int                     error;
 278
 279        /*
 280         * Loop over the new block(s), filling in the inodes.  For small block
 281         * sizes, manipulate the inodes in buffers  which are multiples of the
 282         * blocks size.
 283         */
 284        nbufs = length / M_IGEO(mp)->blocks_per_cluster;
 285
 286        /*
 287         * Figure out what version number to use in the inodes we create.  If
 288         * the superblock version has caught up to the one that supports the new
 289         * inode format, then use the new inode version.  Otherwise use the old
 290         * version so that old kernels will continue to be able to use the file
 291         * system.
 292         *
 293         * For v3 inodes, we also need to write the inode number into the inode,
 294         * so calculate the first inode number of the chunk here as
 295         * XFS_AGB_TO_AGINO() only works within a filesystem block, not
 296         * across multiple filesystem blocks (such as a cluster) and so cannot
 297         * be used in the cluster buffer loop below.
 298         *
 299         * Further, because we are writing the inode directly into the buffer
 300         * and calculating a CRC on the entire inode, we have ot log the entire
 301         * inode so that the entire range the CRC covers is present in the log.
 302         * That means for v3 inode we log the entire buffer rather than just the
 303         * inode cores.
 304         */
 305        if (xfs_sb_version_has_v3inode(&mp->m_sb)) {
 306                version = 3;
 307                ino = XFS_AGINO_TO_INO(mp, agno, XFS_AGB_TO_AGINO(mp, agbno));
 308
 309                /*
 310                 * log the initialisation that is about to take place as an
 311                 * logical operation. This means the transaction does not
 312                 * need to log the physical changes to the inode buffers as log
 313                 * recovery will know what initialisation is actually needed.
 314                 * Hence we only need to log the buffers as "ordered" buffers so
 315                 * they track in the AIL as if they were physically logged.
 316                 */
 317                if (tp)
 318                        xfs_icreate_log(tp, agno, agbno, icount,
 319                                        mp->m_sb.sb_inodesize, length, gen);
 320        } else
 321                version = 2;
 322
 323        for (j = 0; j < nbufs; j++) {
 324                /*
 325                 * Get the block.
 326                 */
 327                d = XFS_AGB_TO_DADDR(mp, agno, agbno +
 328                                (j * M_IGEO(mp)->blocks_per_cluster));
 329                error = xfs_trans_get_buf(tp, mp->m_ddev_targp, d,
 330                                mp->m_bsize * M_IGEO(mp)->blocks_per_cluster,
 331                                XBF_UNMAPPED, &fbuf);
 332                if (error)
 333                        return error;
 334
 335                /* Initialize the inode buffers and log them appropriately. */
 336                fbuf->b_ops = &xfs_inode_buf_ops;
 337                xfs_buf_zero(fbuf, 0, BBTOB(fbuf->b_length));
 338                for (i = 0; i < M_IGEO(mp)->inodes_per_cluster; i++) {
 339                        int     ioffset = i << mp->m_sb.sb_inodelog;
 340                        uint    isize = XFS_DINODE_SIZE(&mp->m_sb);
 341
 342                        free = xfs_make_iptr(mp, fbuf, i);
 343                        free->di_magic = cpu_to_be16(XFS_DINODE_MAGIC);
 344                        free->di_version = version;
 345                        free->di_gen = cpu_to_be32(gen);
 346                        free->di_next_unlinked = cpu_to_be32(NULLAGINO);
 347
 348                        if (version == 3) {
 349                                free->di_ino = cpu_to_be64(ino);
 350                                ino++;
 351                                uuid_copy(&free->di_uuid,
 352                                          &mp->m_sb.sb_meta_uuid);
 353                                xfs_dinode_calc_crc(mp, free);
 354                        } else if (tp) {
 355                                /* just log the inode core */
 356                                xfs_trans_log_buf(tp, fbuf, ioffset,
 357                                                  ioffset + isize - 1);
 358                        }
 359                }
 360
 361                if (tp) {
 362                        /*
 363                         * Mark the buffer as an inode allocation buffer so it
 364                         * sticks in AIL at the point of this allocation
 365                         * transaction. This ensures the they are on disk before
 366                         * the tail of the log can be moved past this
 367                         * transaction (i.e. by preventing relogging from moving
 368                         * it forward in the log).
 369                         */
 370                        xfs_trans_inode_alloc_buf(tp, fbuf);
 371                        if (version == 3) {
 372                                /*
 373                                 * Mark the buffer as ordered so that they are
 374                                 * not physically logged in the transaction but
 375                                 * still tracked in the AIL as part of the
 376                                 * transaction and pin the log appropriately.
 377                                 */
 378                                xfs_trans_ordered_buf(tp, fbuf);
 379                        }
 380                } else {
 381                        fbuf->b_flags |= XBF_DONE;
 382                        xfs_buf_delwri_queue(fbuf, buffer_list);
 383                        xfs_buf_relse(fbuf);
 384                }
 385        }
 386        return 0;
 387}
 388
 389/*
 390 * Align startino and allocmask for a recently allocated sparse chunk such that
 391 * they are fit for insertion (or merge) into the on-disk inode btrees.
 392 *
 393 * Background:
 394 *
 395 * When enabled, sparse inode support increases the inode alignment from cluster
 396 * size to inode chunk size. This means that the minimum range between two
 397 * non-adjacent inode records in the inobt is large enough for a full inode
 398 * record. This allows for cluster sized, cluster aligned block allocation
 399 * without need to worry about whether the resulting inode record overlaps with
 400 * another record in the tree. Without this basic rule, we would have to deal
 401 * with the consequences of overlap by potentially undoing recent allocations in
 402 * the inode allocation codepath.
 403 *
 404 * Because of this alignment rule (which is enforced on mount), there are two
 405 * inobt possibilities for newly allocated sparse chunks. One is that the
 406 * aligned inode record for the chunk covers a range of inodes not already
 407 * covered in the inobt (i.e., it is safe to insert a new sparse record). The
 408 * other is that a record already exists at the aligned startino that considers
 409 * the newly allocated range as sparse. In the latter case, record content is
 410 * merged in hope that sparse inode chunks fill to full chunks over time.
 411 */
 412STATIC void
 413xfs_align_sparse_ino(
 414        struct xfs_mount                *mp,
 415        xfs_agino_t                     *startino,
 416        uint16_t                        *allocmask)
 417{
 418        xfs_agblock_t                   agbno;
 419        xfs_agblock_t                   mod;
 420        int                             offset;
 421
 422        agbno = XFS_AGINO_TO_AGBNO(mp, *startino);
 423        mod = agbno % mp->m_sb.sb_inoalignmt;
 424        if (!mod)
 425                return;
 426
 427        /* calculate the inode offset and align startino */
 428        offset = XFS_AGB_TO_AGINO(mp, mod);
 429        *startino -= offset;
 430
 431        /*
 432         * Since startino has been aligned down, left shift allocmask such that
 433         * it continues to represent the same physical inodes relative to the
 434         * new startino.
 435         */
 436        *allocmask <<= offset / XFS_INODES_PER_HOLEMASK_BIT;
 437}
 438
 439/*
 440 * Determine whether the source inode record can merge into the target. Both
 441 * records must be sparse, the inode ranges must match and there must be no
 442 * allocation overlap between the records.
 443 */
 444STATIC bool
 445__xfs_inobt_can_merge(
 446        struct xfs_inobt_rec_incore     *trec,  /* tgt record */
 447        struct xfs_inobt_rec_incore     *srec)  /* src record */
 448{
 449        uint64_t                        talloc;
 450        uint64_t                        salloc;
 451
 452        /* records must cover the same inode range */
 453        if (trec->ir_startino != srec->ir_startino)
 454                return false;
 455
 456        /* both records must be sparse */
 457        if (!xfs_inobt_issparse(trec->ir_holemask) ||
 458            !xfs_inobt_issparse(srec->ir_holemask))
 459                return false;
 460
 461        /* both records must track some inodes */
 462        if (!trec->ir_count || !srec->ir_count)
 463                return false;
 464
 465        /* can't exceed capacity of a full record */
 466        if (trec->ir_count + srec->ir_count > XFS_INODES_PER_CHUNK)
 467                return false;
 468
 469        /* verify there is no allocation overlap */
 470        talloc = xfs_inobt_irec_to_allocmask(trec);
 471        salloc = xfs_inobt_irec_to_allocmask(srec);
 472        if (talloc & salloc)
 473                return false;
 474
 475        return true;
 476}
 477
 478/*
 479 * Merge the source inode record into the target. The caller must call
 480 * __xfs_inobt_can_merge() to ensure the merge is valid.
 481 */
 482STATIC void
 483__xfs_inobt_rec_merge(
 484        struct xfs_inobt_rec_incore     *trec,  /* target */
 485        struct xfs_inobt_rec_incore     *srec)  /* src */
 486{
 487        ASSERT(trec->ir_startino == srec->ir_startino);
 488
 489        /* combine the counts */
 490        trec->ir_count += srec->ir_count;
 491        trec->ir_freecount += srec->ir_freecount;
 492
 493        /*
 494         * Merge the holemask and free mask. For both fields, 0 bits refer to
 495         * allocated inodes. We combine the allocated ranges with bitwise AND.
 496         */
 497        trec->ir_holemask &= srec->ir_holemask;
 498        trec->ir_free &= srec->ir_free;
 499}
 500
 501/*
 502 * Insert a new sparse inode chunk into the associated inode btree. The inode
 503 * record for the sparse chunk is pre-aligned to a startino that should match
 504 * any pre-existing sparse inode record in the tree. This allows sparse chunks
 505 * to fill over time.
 506 *
 507 * This function supports two modes of handling preexisting records depending on
 508 * the merge flag. If merge is true, the provided record is merged with the
 509 * existing record and updated in place. The merged record is returned in nrec.
 510 * If merge is false, an existing record is replaced with the provided record.
 511 * If no preexisting record exists, the provided record is always inserted.
 512 *
 513 * It is considered corruption if a merge is requested and not possible. Given
 514 * the sparse inode alignment constraints, this should never happen.
 515 */
 516STATIC int
 517xfs_inobt_insert_sprec(
 518        struct xfs_mount                *mp,
 519        struct xfs_trans                *tp,
 520        struct xfs_buf                  *agbp,
 521        struct xfs_perag                *pag,
 522        int                             btnum,
 523        struct xfs_inobt_rec_incore     *nrec,  /* in/out: new/merged rec. */
 524        bool                            merge)  /* merge or replace */
 525{
 526        struct xfs_btree_cur            *cur;
 527        int                             error;
 528        int                             i;
 529        struct xfs_inobt_rec_incore     rec;
 530
 531        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, btnum);
 532
 533        /* the new record is pre-aligned so we know where to look */
 534        error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i);
 535        if (error)
 536                goto error;
 537        /* if nothing there, insert a new record and return */
 538        if (i == 0) {
 539                error = xfs_inobt_insert_rec(cur, nrec->ir_holemask,
 540                                             nrec->ir_count, nrec->ir_freecount,
 541                                             nrec->ir_free, &i);
 542                if (error)
 543                        goto error;
 544                if (XFS_IS_CORRUPT(mp, i != 1)) {
 545                        error = -EFSCORRUPTED;
 546                        goto error;
 547                }
 548
 549                goto out;
 550        }
 551
 552        /*
 553         * A record exists at this startino. Merge or replace the record
 554         * depending on what we've been asked to do.
 555         */
 556        if (merge) {
 557                error = xfs_inobt_get_rec(cur, &rec, &i);
 558                if (error)
 559                        goto error;
 560                if (XFS_IS_CORRUPT(mp, i != 1)) {
 561                        error = -EFSCORRUPTED;
 562                        goto error;
 563                }
 564                if (XFS_IS_CORRUPT(mp, rec.ir_startino != nrec->ir_startino)) {
 565                        error = -EFSCORRUPTED;
 566                        goto error;
 567                }
 568
 569                /*
 570                 * This should never fail. If we have coexisting records that
 571                 * cannot merge, something is seriously wrong.
 572                 */
 573                if (XFS_IS_CORRUPT(mp, !__xfs_inobt_can_merge(nrec, &rec))) {
 574                        error = -EFSCORRUPTED;
 575                        goto error;
 576                }
 577
 578                trace_xfs_irec_merge_pre(mp, pag->pag_agno, rec.ir_startino,
 579                                         rec.ir_holemask, nrec->ir_startino,
 580                                         nrec->ir_holemask);
 581
 582                /* merge to nrec to output the updated record */
 583                __xfs_inobt_rec_merge(nrec, &rec);
 584
 585                trace_xfs_irec_merge_post(mp, pag->pag_agno, nrec->ir_startino,
 586                                          nrec->ir_holemask);
 587
 588                error = xfs_inobt_rec_check_count(mp, nrec);
 589                if (error)
 590                        goto error;
 591        }
 592
 593        error = xfs_inobt_update(cur, nrec);
 594        if (error)
 595                goto error;
 596
 597out:
 598        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
 599        return 0;
 600error:
 601        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
 602        return error;
 603}
 604
 605/*
 606 * Allocate new inodes in the allocation group specified by agbp.  Returns 0 if
 607 * inodes were allocated in this AG; -EAGAIN if there was no space in this AG so
 608 * the caller knows it can try another AG, a hard -ENOSPC when over the maximum
 609 * inode count threshold, or the usual negative error code for other errors.
 610 */
 611STATIC int
 612xfs_ialloc_ag_alloc(
 613        struct xfs_trans        *tp,
 614        struct xfs_buf          *agbp,
 615        struct xfs_perag        *pag)
 616{
 617        struct xfs_agi          *agi;
 618        struct xfs_alloc_arg    args;
 619        int                     error;
 620        xfs_agino_t             newino;         /* new first inode's number */
 621        xfs_agino_t             newlen;         /* new number of inodes */
 622        int                     isaligned = 0;  /* inode allocation at stripe */
 623                                                /* unit boundary */
 624        /* init. to full chunk */
 625        struct xfs_inobt_rec_incore rec;
 626        struct xfs_ino_geometry *igeo = M_IGEO(tp->t_mountp);
 627        uint16_t                allocmask = (uint16_t) -1;
 628        int                     do_sparse = 0;
 629
 630        memset(&args, 0, sizeof(args));
 631        args.tp = tp;
 632        args.mp = tp->t_mountp;
 633        args.fsbno = NULLFSBLOCK;
 634        args.oinfo = XFS_RMAP_OINFO_INODES;
 635
 636#ifdef DEBUG
 637        /* randomly do sparse inode allocations */
 638        if (xfs_sb_version_hassparseinodes(&tp->t_mountp->m_sb) &&
 639            igeo->ialloc_min_blks < igeo->ialloc_blks)
 640                do_sparse = prandom_u32() & 1;
 641#endif
 642
 643        /*
 644         * Locking will ensure that we don't have two callers in here
 645         * at one time.
 646         */
 647        newlen = igeo->ialloc_inos;
 648        if (igeo->maxicount &&
 649            percpu_counter_read_positive(&args.mp->m_icount) + newlen >
 650                                                        igeo->maxicount)
 651                return -ENOSPC;
 652        args.minlen = args.maxlen = igeo->ialloc_blks;
 653        /*
 654         * First try to allocate inodes contiguous with the last-allocated
 655         * chunk of inodes.  If the filesystem is striped, this will fill
 656         * an entire stripe unit with inodes.
 657         */
 658        agi = agbp->b_addr;
 659        newino = be32_to_cpu(agi->agi_newino);
 660        args.agbno = XFS_AGINO_TO_AGBNO(args.mp, newino) +
 661                     igeo->ialloc_blks;
 662        if (do_sparse)
 663                goto sparse_alloc;
 664        if (likely(newino != NULLAGINO &&
 665                  (args.agbno < be32_to_cpu(agi->agi_length)))) {
 666                args.fsbno = XFS_AGB_TO_FSB(args.mp, pag->pag_agno, args.agbno);
 667                args.type = XFS_ALLOCTYPE_THIS_BNO;
 668                args.prod = 1;
 669
 670                /*
 671                 * We need to take into account alignment here to ensure that
 672                 * we don't modify the free list if we fail to have an exact
 673                 * block. If we don't have an exact match, and every oher
 674                 * attempt allocation attempt fails, we'll end up cancelling
 675                 * a dirty transaction and shutting down.
 676                 *
 677                 * For an exact allocation, alignment must be 1,
 678                 * however we need to take cluster alignment into account when
 679                 * fixing up the freelist. Use the minalignslop field to
 680                 * indicate that extra blocks might be required for alignment,
 681                 * but not to use them in the actual exact allocation.
 682                 */
 683                args.alignment = 1;
 684                args.minalignslop = igeo->cluster_align - 1;
 685
 686                /* Allow space for the inode btree to split. */
 687                args.minleft = igeo->inobt_maxlevels;
 688                if ((error = xfs_alloc_vextent(&args)))
 689                        return error;
 690
 691                /*
 692                 * This request might have dirtied the transaction if the AG can
 693                 * satisfy the request, but the exact block was not available.
 694                 * If the allocation did fail, subsequent requests will relax
 695                 * the exact agbno requirement and increase the alignment
 696                 * instead. It is critical that the total size of the request
 697                 * (len + alignment + slop) does not increase from this point
 698                 * on, so reset minalignslop to ensure it is not included in
 699                 * subsequent requests.
 700                 */
 701                args.minalignslop = 0;
 702        }
 703
 704        if (unlikely(args.fsbno == NULLFSBLOCK)) {
 705                /*
 706                 * Set the alignment for the allocation.
 707                 * If stripe alignment is turned on then align at stripe unit
 708                 * boundary.
 709                 * If the cluster size is smaller than a filesystem block
 710                 * then we're doing I/O for inodes in filesystem block size
 711                 * pieces, so don't need alignment anyway.
 712                 */
 713                isaligned = 0;
 714                if (igeo->ialloc_align) {
 715                        ASSERT(!(args.mp->m_flags & XFS_MOUNT_NOALIGN));
 716                        args.alignment = args.mp->m_dalign;
 717                        isaligned = 1;
 718                } else
 719                        args.alignment = igeo->cluster_align;
 720                /*
 721                 * Need to figure out where to allocate the inode blocks.
 722                 * Ideally they should be spaced out through the a.g.
 723                 * For now, just allocate blocks up front.
 724                 */
 725                args.agbno = be32_to_cpu(agi->agi_root);
 726                args.fsbno = XFS_AGB_TO_FSB(args.mp, pag->pag_agno, args.agbno);
 727                /*
 728                 * Allocate a fixed-size extent of inodes.
 729                 */
 730                args.type = XFS_ALLOCTYPE_NEAR_BNO;
 731                args.prod = 1;
 732                /*
 733                 * Allow space for the inode btree to split.
 734                 */
 735                args.minleft = igeo->inobt_maxlevels;
 736                if ((error = xfs_alloc_vextent(&args)))
 737                        return error;
 738        }
 739
 740        /*
 741         * If stripe alignment is turned on, then try again with cluster
 742         * alignment.
 743         */
 744        if (isaligned && args.fsbno == NULLFSBLOCK) {
 745                args.type = XFS_ALLOCTYPE_NEAR_BNO;
 746                args.agbno = be32_to_cpu(agi->agi_root);
 747                args.fsbno = XFS_AGB_TO_FSB(args.mp, pag->pag_agno, args.agbno);
 748                args.alignment = igeo->cluster_align;
 749                if ((error = xfs_alloc_vextent(&args)))
 750                        return error;
 751        }
 752
 753        /*
 754         * Finally, try a sparse allocation if the filesystem supports it and
 755         * the sparse allocation length is smaller than a full chunk.
 756         */
 757        if (xfs_sb_version_hassparseinodes(&args.mp->m_sb) &&
 758            igeo->ialloc_min_blks < igeo->ialloc_blks &&
 759            args.fsbno == NULLFSBLOCK) {
 760sparse_alloc:
 761                args.type = XFS_ALLOCTYPE_NEAR_BNO;
 762                args.agbno = be32_to_cpu(agi->agi_root);
 763                args.fsbno = XFS_AGB_TO_FSB(args.mp, pag->pag_agno, args.agbno);
 764                args.alignment = args.mp->m_sb.sb_spino_align;
 765                args.prod = 1;
 766
 767                args.minlen = igeo->ialloc_min_blks;
 768                args.maxlen = args.minlen;
 769
 770                /*
 771                 * The inode record will be aligned to full chunk size. We must
 772                 * prevent sparse allocation from AG boundaries that result in
 773                 * invalid inode records, such as records that start at agbno 0
 774                 * or extend beyond the AG.
 775                 *
 776                 * Set min agbno to the first aligned, non-zero agbno and max to
 777                 * the last aligned agbno that is at least one full chunk from
 778                 * the end of the AG.
 779                 */
 780                args.min_agbno = args.mp->m_sb.sb_inoalignmt;
 781                args.max_agbno = round_down(args.mp->m_sb.sb_agblocks,
 782                                            args.mp->m_sb.sb_inoalignmt) -
 783                                 igeo->ialloc_blks;
 784
 785                error = xfs_alloc_vextent(&args);
 786                if (error)
 787                        return error;
 788
 789                newlen = XFS_AGB_TO_AGINO(args.mp, args.len);
 790                ASSERT(newlen <= XFS_INODES_PER_CHUNK);
 791                allocmask = (1 << (newlen / XFS_INODES_PER_HOLEMASK_BIT)) - 1;
 792        }
 793
 794        if (args.fsbno == NULLFSBLOCK)
 795                return -EAGAIN;
 796
 797        ASSERT(args.len == args.minlen);
 798
 799        /*
 800         * Stamp and write the inode buffers.
 801         *
 802         * Seed the new inode cluster with a random generation number. This
 803         * prevents short-term reuse of generation numbers if a chunk is
 804         * freed and then immediately reallocated. We use random numbers
 805         * rather than a linear progression to prevent the next generation
 806         * number from being easily guessable.
 807         */
 808        error = xfs_ialloc_inode_init(args.mp, tp, NULL, newlen, pag->pag_agno,
 809                        args.agbno, args.len, prandom_u32());
 810
 811        if (error)
 812                return error;
 813        /*
 814         * Convert the results.
 815         */
 816        newino = XFS_AGB_TO_AGINO(args.mp, args.agbno);
 817
 818        if (xfs_inobt_issparse(~allocmask)) {
 819                /*
 820                 * We've allocated a sparse chunk. Align the startino and mask.
 821                 */
 822                xfs_align_sparse_ino(args.mp, &newino, &allocmask);
 823
 824                rec.ir_startino = newino;
 825                rec.ir_holemask = ~allocmask;
 826                rec.ir_count = newlen;
 827                rec.ir_freecount = newlen;
 828                rec.ir_free = XFS_INOBT_ALL_FREE;
 829
 830                /*
 831                 * Insert the sparse record into the inobt and allow for a merge
 832                 * if necessary. If a merge does occur, rec is updated to the
 833                 * merged record.
 834                 */
 835                error = xfs_inobt_insert_sprec(args.mp, tp, agbp, pag,
 836                                XFS_BTNUM_INO, &rec, true);
 837                if (error == -EFSCORRUPTED) {
 838                        xfs_alert(args.mp,
 839        "invalid sparse inode record: ino 0x%llx holemask 0x%x count %u",
 840                                  XFS_AGINO_TO_INO(args.mp, pag->pag_agno,
 841                                                   rec.ir_startino),
 842                                  rec.ir_holemask, rec.ir_count);
 843                        xfs_force_shutdown(args.mp, SHUTDOWN_CORRUPT_INCORE);
 844                }
 845                if (error)
 846                        return error;
 847
 848                /*
 849                 * We can't merge the part we've just allocated as for the inobt
 850                 * due to finobt semantics. The original record may or may not
 851                 * exist independent of whether physical inodes exist in this
 852                 * sparse chunk.
 853                 *
 854                 * We must update the finobt record based on the inobt record.
 855                 * rec contains the fully merged and up to date inobt record
 856                 * from the previous call. Set merge false to replace any
 857                 * existing record with this one.
 858                 */
 859                if (xfs_sb_version_hasfinobt(&args.mp->m_sb)) {
 860                        error = xfs_inobt_insert_sprec(args.mp, tp, agbp, pag,
 861                                       XFS_BTNUM_FINO, &rec, false);
 862                        if (error)
 863                                return error;
 864                }
 865        } else {
 866                /* full chunk - insert new records to both btrees */
 867                error = xfs_inobt_insert(args.mp, tp, agbp, pag, newino, newlen,
 868                                         XFS_BTNUM_INO);
 869                if (error)
 870                        return error;
 871
 872                if (xfs_sb_version_hasfinobt(&args.mp->m_sb)) {
 873                        error = xfs_inobt_insert(args.mp, tp, agbp, pag, newino,
 874                                                 newlen, XFS_BTNUM_FINO);
 875                        if (error)
 876                                return error;
 877                }
 878        }
 879
 880        /*
 881         * Update AGI counts and newino.
 882         */
 883        be32_add_cpu(&agi->agi_count, newlen);
 884        be32_add_cpu(&agi->agi_freecount, newlen);
 885        pag->pagi_freecount += newlen;
 886        pag->pagi_count += newlen;
 887        agi->agi_newino = cpu_to_be32(newino);
 888
 889        /*
 890         * Log allocation group header fields
 891         */
 892        xfs_ialloc_log_agi(tp, agbp,
 893                XFS_AGI_COUNT | XFS_AGI_FREECOUNT | XFS_AGI_NEWINO);
 894        /*
 895         * Modify/log superblock values for inode count and inode free count.
 896         */
 897        xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, (long)newlen);
 898        xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, (long)newlen);
 899        return 0;
 900}
 901
 902/*
 903 * Try to retrieve the next record to the left/right from the current one.
 904 */
 905STATIC int
 906xfs_ialloc_next_rec(
 907        struct xfs_btree_cur    *cur,
 908        xfs_inobt_rec_incore_t  *rec,
 909        int                     *done,
 910        int                     left)
 911{
 912        int                     error;
 913        int                     i;
 914
 915        if (left)
 916                error = xfs_btree_decrement(cur, 0, &i);
 917        else
 918                error = xfs_btree_increment(cur, 0, &i);
 919
 920        if (error)
 921                return error;
 922        *done = !i;
 923        if (i) {
 924                error = xfs_inobt_get_rec(cur, rec, &i);
 925                if (error)
 926                        return error;
 927                if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
 928                        return -EFSCORRUPTED;
 929        }
 930
 931        return 0;
 932}
 933
 934STATIC int
 935xfs_ialloc_get_rec(
 936        struct xfs_btree_cur    *cur,
 937        xfs_agino_t             agino,
 938        xfs_inobt_rec_incore_t  *rec,
 939        int                     *done)
 940{
 941        int                     error;
 942        int                     i;
 943
 944        error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_EQ, &i);
 945        if (error)
 946                return error;
 947        *done = !i;
 948        if (i) {
 949                error = xfs_inobt_get_rec(cur, rec, &i);
 950                if (error)
 951                        return error;
 952                if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
 953                        return -EFSCORRUPTED;
 954        }
 955
 956        return 0;
 957}
 958
 959/*
 960 * Return the offset of the first free inode in the record. If the inode chunk
 961 * is sparsely allocated, we convert the record holemask to inode granularity
 962 * and mask off the unallocated regions from the inode free mask.
 963 */
 964STATIC int
 965xfs_inobt_first_free_inode(
 966        struct xfs_inobt_rec_incore     *rec)
 967{
 968        xfs_inofree_t                   realfree;
 969
 970        /* if there are no holes, return the first available offset */
 971        if (!xfs_inobt_issparse(rec->ir_holemask))
 972                return xfs_lowbit64(rec->ir_free);
 973
 974        realfree = xfs_inobt_irec_to_allocmask(rec);
 975        realfree &= rec->ir_free;
 976
 977        return xfs_lowbit64(realfree);
 978}
 979
 980/*
 981 * Allocate an inode using the inobt-only algorithm.
 982 */
 983STATIC int
 984xfs_dialloc_ag_inobt(
 985        struct xfs_trans        *tp,
 986        struct xfs_buf          *agbp,
 987        struct xfs_perag        *pag,
 988        xfs_ino_t               parent,
 989        xfs_ino_t               *inop)
 990{
 991        struct xfs_mount        *mp = tp->t_mountp;
 992        struct xfs_agi          *agi = agbp->b_addr;
 993        xfs_agnumber_t          pagno = XFS_INO_TO_AGNO(mp, parent);
 994        xfs_agino_t             pagino = XFS_INO_TO_AGINO(mp, parent);
 995        struct xfs_btree_cur    *cur, *tcur;
 996        struct xfs_inobt_rec_incore rec, trec;
 997        xfs_ino_t               ino;
 998        int                     error;
 999        int                     offset;
1000        int                     i, j;
1001        int                     searchdistance = 10;
1002
1003        ASSERT(pag->pagi_init);
1004        ASSERT(pag->pagi_inodeok);
1005        ASSERT(pag->pagi_freecount > 0);
1006
1007 restart_pagno:
1008        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_INO);
1009        /*
1010         * If pagino is 0 (this is the root inode allocation) use newino.
1011         * This must work because we've just allocated some.
1012         */
1013        if (!pagino)
1014                pagino = be32_to_cpu(agi->agi_newino);
1015
1016        error = xfs_check_agi_freecount(cur);
1017        if (error)
1018                goto error0;
1019
1020        /*
1021         * If in the same AG as the parent, try to get near the parent.
1022         */
1023        if (pagno == pag->pag_agno) {
1024                int             doneleft;       /* done, to the left */
1025                int             doneright;      /* done, to the right */
1026
1027                error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i);
1028                if (error)
1029                        goto error0;
1030                if (XFS_IS_CORRUPT(mp, i != 1)) {
1031                        error = -EFSCORRUPTED;
1032                        goto error0;
1033                }
1034
1035                error = xfs_inobt_get_rec(cur, &rec, &j);
1036                if (error)
1037                        goto error0;
1038                if (XFS_IS_CORRUPT(mp, j != 1)) {
1039                        error = -EFSCORRUPTED;
1040                        goto error0;
1041                }
1042
1043                if (rec.ir_freecount > 0) {
1044                        /*
1045                         * Found a free inode in the same chunk
1046                         * as the parent, done.
1047                         */
1048                        goto alloc_inode;
1049                }
1050
1051
1052                /*
1053                 * In the same AG as parent, but parent's chunk is full.
1054                 */
1055
1056                /* duplicate the cursor, search left & right simultaneously */
1057                error = xfs_btree_dup_cursor(cur, &tcur);
1058                if (error)
1059                        goto error0;
1060
1061                /*
1062                 * Skip to last blocks looked up if same parent inode.
1063                 */
1064                if (pagino != NULLAGINO &&
1065                    pag->pagl_pagino == pagino &&
1066                    pag->pagl_leftrec != NULLAGINO &&
1067                    pag->pagl_rightrec != NULLAGINO) {
1068                        error = xfs_ialloc_get_rec(tcur, pag->pagl_leftrec,
1069                                                   &trec, &doneleft);
1070                        if (error)
1071                                goto error1;
1072
1073                        error = xfs_ialloc_get_rec(cur, pag->pagl_rightrec,
1074                                                   &rec, &doneright);
1075                        if (error)
1076                                goto error1;
1077                } else {
1078                        /* search left with tcur, back up 1 record */
1079                        error = xfs_ialloc_next_rec(tcur, &trec, &doneleft, 1);
1080                        if (error)
1081                                goto error1;
1082
1083                        /* search right with cur, go forward 1 record. */
1084                        error = xfs_ialloc_next_rec(cur, &rec, &doneright, 0);
1085                        if (error)
1086                                goto error1;
1087                }
1088
1089                /*
1090                 * Loop until we find an inode chunk with a free inode.
1091                 */
1092                while (--searchdistance > 0 && (!doneleft || !doneright)) {
1093                        int     useleft;  /* using left inode chunk this time */
1094
1095                        /* figure out the closer block if both are valid. */
1096                        if (!doneleft && !doneright) {
1097                                useleft = pagino -
1098                                 (trec.ir_startino + XFS_INODES_PER_CHUNK - 1) <
1099                                  rec.ir_startino - pagino;
1100                        } else {
1101                                useleft = !doneleft;
1102                        }
1103
1104                        /* free inodes to the left? */
1105                        if (useleft && trec.ir_freecount) {
1106                                xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1107                                cur = tcur;
1108
1109                                pag->pagl_leftrec = trec.ir_startino;
1110                                pag->pagl_rightrec = rec.ir_startino;
1111                                pag->pagl_pagino = pagino;
1112                                rec = trec;
1113                                goto alloc_inode;
1114                        }
1115
1116                        /* free inodes to the right? */
1117                        if (!useleft && rec.ir_freecount) {
1118                                xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1119
1120                                pag->pagl_leftrec = trec.ir_startino;
1121                                pag->pagl_rightrec = rec.ir_startino;
1122                                pag->pagl_pagino = pagino;
1123                                goto alloc_inode;
1124                        }
1125
1126                        /* get next record to check */
1127                        if (useleft) {
1128                                error = xfs_ialloc_next_rec(tcur, &trec,
1129                                                                 &doneleft, 1);
1130                        } else {
1131                                error = xfs_ialloc_next_rec(cur, &rec,
1132                                                                 &doneright, 0);
1133                        }
1134                        if (error)
1135                                goto error1;
1136                }
1137
1138                if (searchdistance <= 0) {
1139                        /*
1140                         * Not in range - save last search
1141                         * location and allocate a new inode
1142                         */
1143                        xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1144                        pag->pagl_leftrec = trec.ir_startino;
1145                        pag->pagl_rightrec = rec.ir_startino;
1146                        pag->pagl_pagino = pagino;
1147
1148                } else {
1149                        /*
1150                         * We've reached the end of the btree. because
1151                         * we are only searching a small chunk of the
1152                         * btree each search, there is obviously free
1153                         * inodes closer to the parent inode than we
1154                         * are now. restart the search again.
1155                         */
1156                        pag->pagl_pagino = NULLAGINO;
1157                        pag->pagl_leftrec = NULLAGINO;
1158                        pag->pagl_rightrec = NULLAGINO;
1159                        xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1160                        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1161                        goto restart_pagno;
1162                }
1163        }
1164
1165        /*
1166         * In a different AG from the parent.
1167         * See if the most recently allocated block has any free.
1168         */
1169        if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
1170                error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
1171                                         XFS_LOOKUP_EQ, &i);
1172                if (error)
1173                        goto error0;
1174
1175                if (i == 1) {
1176                        error = xfs_inobt_get_rec(cur, &rec, &j);
1177                        if (error)
1178                                goto error0;
1179
1180                        if (j == 1 && rec.ir_freecount > 0) {
1181                                /*
1182                                 * The last chunk allocated in the group
1183                                 * still has a free inode.
1184                                 */
1185                                goto alloc_inode;
1186                        }
1187                }
1188        }
1189
1190        /*
1191         * None left in the last group, search the whole AG
1192         */
1193        error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
1194        if (error)
1195                goto error0;
1196        if (XFS_IS_CORRUPT(mp, i != 1)) {
1197                error = -EFSCORRUPTED;
1198                goto error0;
1199        }
1200
1201        for (;;) {
1202                error = xfs_inobt_get_rec(cur, &rec, &i);
1203                if (error)
1204                        goto error0;
1205                if (XFS_IS_CORRUPT(mp, i != 1)) {
1206                        error = -EFSCORRUPTED;
1207                        goto error0;
1208                }
1209                if (rec.ir_freecount > 0)
1210                        break;
1211                error = xfs_btree_increment(cur, 0, &i);
1212                if (error)
1213                        goto error0;
1214                if (XFS_IS_CORRUPT(mp, i != 1)) {
1215                        error = -EFSCORRUPTED;
1216                        goto error0;
1217                }
1218        }
1219
1220alloc_inode:
1221        offset = xfs_inobt_first_free_inode(&rec);
1222        ASSERT(offset >= 0);
1223        ASSERT(offset < XFS_INODES_PER_CHUNK);
1224        ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
1225                                   XFS_INODES_PER_CHUNK) == 0);
1226        ino = XFS_AGINO_TO_INO(mp, pag->pag_agno, rec.ir_startino + offset);
1227        rec.ir_free &= ~XFS_INOBT_MASK(offset);
1228        rec.ir_freecount--;
1229        error = xfs_inobt_update(cur, &rec);
1230        if (error)
1231                goto error0;
1232        be32_add_cpu(&agi->agi_freecount, -1);
1233        xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1234        pag->pagi_freecount--;
1235
1236        error = xfs_check_agi_freecount(cur);
1237        if (error)
1238                goto error0;
1239
1240        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1241        xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
1242        *inop = ino;
1243        return 0;
1244error1:
1245        xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1246error0:
1247        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1248        return error;
1249}
1250
1251/*
1252 * Use the free inode btree to allocate an inode based on distance from the
1253 * parent. Note that the provided cursor may be deleted and replaced.
1254 */
1255STATIC int
1256xfs_dialloc_ag_finobt_near(
1257        xfs_agino_t                     pagino,
1258        struct xfs_btree_cur            **ocur,
1259        struct xfs_inobt_rec_incore     *rec)
1260{
1261        struct xfs_btree_cur            *lcur = *ocur;  /* left search cursor */
1262        struct xfs_btree_cur            *rcur;  /* right search cursor */
1263        struct xfs_inobt_rec_incore     rrec;
1264        int                             error;
1265        int                             i, j;
1266
1267        error = xfs_inobt_lookup(lcur, pagino, XFS_LOOKUP_LE, &i);
1268        if (error)
1269                return error;
1270
1271        if (i == 1) {
1272                error = xfs_inobt_get_rec(lcur, rec, &i);
1273                if (error)
1274                        return error;
1275                if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1))
1276                        return -EFSCORRUPTED;
1277
1278                /*
1279                 * See if we've landed in the parent inode record. The finobt
1280                 * only tracks chunks with at least one free inode, so record
1281                 * existence is enough.
1282                 */
1283                if (pagino >= rec->ir_startino &&
1284                    pagino < (rec->ir_startino + XFS_INODES_PER_CHUNK))
1285                        return 0;
1286        }
1287
1288        error = xfs_btree_dup_cursor(lcur, &rcur);
1289        if (error)
1290                return error;
1291
1292        error = xfs_inobt_lookup(rcur, pagino, XFS_LOOKUP_GE, &j);
1293        if (error)
1294                goto error_rcur;
1295        if (j == 1) {
1296                error = xfs_inobt_get_rec(rcur, &rrec, &j);
1297                if (error)
1298                        goto error_rcur;
1299                if (XFS_IS_CORRUPT(lcur->bc_mp, j != 1)) {
1300                        error = -EFSCORRUPTED;
1301                        goto error_rcur;
1302                }
1303        }
1304
1305        if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1 && j != 1)) {
1306                error = -EFSCORRUPTED;
1307                goto error_rcur;
1308        }
1309        if (i == 1 && j == 1) {
1310                /*
1311                 * Both the left and right records are valid. Choose the closer
1312                 * inode chunk to the target.
1313                 */
1314                if ((pagino - rec->ir_startino + XFS_INODES_PER_CHUNK - 1) >
1315                    (rrec.ir_startino - pagino)) {
1316                        *rec = rrec;
1317                        xfs_btree_del_cursor(lcur, XFS_BTREE_NOERROR);
1318                        *ocur = rcur;
1319                } else {
1320                        xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR);
1321                }
1322        } else if (j == 1) {
1323                /* only the right record is valid */
1324                *rec = rrec;
1325                xfs_btree_del_cursor(lcur, XFS_BTREE_NOERROR);
1326                *ocur = rcur;
1327        } else if (i == 1) {
1328                /* only the left record is valid */
1329                xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR);
1330        }
1331
1332        return 0;
1333
1334error_rcur:
1335        xfs_btree_del_cursor(rcur, XFS_BTREE_ERROR);
1336        return error;
1337}
1338
1339/*
1340 * Use the free inode btree to find a free inode based on a newino hint. If
1341 * the hint is NULL, find the first free inode in the AG.
1342 */
1343STATIC int
1344xfs_dialloc_ag_finobt_newino(
1345        struct xfs_agi                  *agi,
1346        struct xfs_btree_cur            *cur,
1347        struct xfs_inobt_rec_incore     *rec)
1348{
1349        int error;
1350        int i;
1351
1352        if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
1353                error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino),
1354                                         XFS_LOOKUP_EQ, &i);
1355                if (error)
1356                        return error;
1357                if (i == 1) {
1358                        error = xfs_inobt_get_rec(cur, rec, &i);
1359                        if (error)
1360                                return error;
1361                        if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
1362                                return -EFSCORRUPTED;
1363                        return 0;
1364                }
1365        }
1366
1367        /*
1368         * Find the first inode available in the AG.
1369         */
1370        error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
1371        if (error)
1372                return error;
1373        if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
1374                return -EFSCORRUPTED;
1375
1376        error = xfs_inobt_get_rec(cur, rec, &i);
1377        if (error)
1378                return error;
1379        if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
1380                return -EFSCORRUPTED;
1381
1382        return 0;
1383}
1384
1385/*
1386 * Update the inobt based on a modification made to the finobt. Also ensure that
1387 * the records from both trees are equivalent post-modification.
1388 */
1389STATIC int
1390xfs_dialloc_ag_update_inobt(
1391        struct xfs_btree_cur            *cur,   /* inobt cursor */
1392        struct xfs_inobt_rec_incore     *frec,  /* finobt record */
1393        int                             offset) /* inode offset */
1394{
1395        struct xfs_inobt_rec_incore     rec;
1396        int                             error;
1397        int                             i;
1398
1399        error = xfs_inobt_lookup(cur, frec->ir_startino, XFS_LOOKUP_EQ, &i);
1400        if (error)
1401                return error;
1402        if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
1403                return -EFSCORRUPTED;
1404
1405        error = xfs_inobt_get_rec(cur, &rec, &i);
1406        if (error)
1407                return error;
1408        if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
1409                return -EFSCORRUPTED;
1410        ASSERT((XFS_AGINO_TO_OFFSET(cur->bc_mp, rec.ir_startino) %
1411                                   XFS_INODES_PER_CHUNK) == 0);
1412
1413        rec.ir_free &= ~XFS_INOBT_MASK(offset);
1414        rec.ir_freecount--;
1415
1416        if (XFS_IS_CORRUPT(cur->bc_mp,
1417                           rec.ir_free != frec->ir_free ||
1418                           rec.ir_freecount != frec->ir_freecount))
1419                return -EFSCORRUPTED;
1420
1421        return xfs_inobt_update(cur, &rec);
1422}
1423
1424/*
1425 * Allocate an inode using the free inode btree, if available. Otherwise, fall
1426 * back to the inobt search algorithm.
1427 *
1428 * The caller selected an AG for us, and made sure that free inodes are
1429 * available.
1430 */
1431static int
1432xfs_dialloc_ag(
1433        struct xfs_trans        *tp,
1434        struct xfs_buf          *agbp,
1435        struct xfs_perag        *pag,
1436        xfs_ino_t               parent,
1437        xfs_ino_t               *inop)
1438{
1439        struct xfs_mount                *mp = tp->t_mountp;
1440        struct xfs_agi                  *agi = agbp->b_addr;
1441        xfs_agnumber_t                  pagno = XFS_INO_TO_AGNO(mp, parent);
1442        xfs_agino_t                     pagino = XFS_INO_TO_AGINO(mp, parent);
1443        struct xfs_btree_cur            *cur;   /* finobt cursor */
1444        struct xfs_btree_cur            *icur;  /* inobt cursor */
1445        struct xfs_inobt_rec_incore     rec;
1446        xfs_ino_t                       ino;
1447        int                             error;
1448        int                             offset;
1449        int                             i;
1450
1451        if (!xfs_sb_version_hasfinobt(&mp->m_sb))
1452                return xfs_dialloc_ag_inobt(tp, agbp, pag, parent, inop);
1453
1454        /*
1455         * If pagino is 0 (this is the root inode allocation) use newino.
1456         * This must work because we've just allocated some.
1457         */
1458        if (!pagino)
1459                pagino = be32_to_cpu(agi->agi_newino);
1460
1461        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_FINO);
1462
1463        error = xfs_check_agi_freecount(cur);
1464        if (error)
1465                goto error_cur;
1466
1467        /*
1468         * The search algorithm depends on whether we're in the same AG as the
1469         * parent. If so, find the closest available inode to the parent. If
1470         * not, consider the agi hint or find the first free inode in the AG.
1471         */
1472        if (pag->pag_agno == pagno)
1473                error = xfs_dialloc_ag_finobt_near(pagino, &cur, &rec);
1474        else
1475                error = xfs_dialloc_ag_finobt_newino(agi, cur, &rec);
1476        if (error)
1477                goto error_cur;
1478
1479        offset = xfs_inobt_first_free_inode(&rec);
1480        ASSERT(offset >= 0);
1481        ASSERT(offset < XFS_INODES_PER_CHUNK);
1482        ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
1483                                   XFS_INODES_PER_CHUNK) == 0);
1484        ino = XFS_AGINO_TO_INO(mp, pag->pag_agno, rec.ir_startino + offset);
1485
1486        /*
1487         * Modify or remove the finobt record.
1488         */
1489        rec.ir_free &= ~XFS_INOBT_MASK(offset);
1490        rec.ir_freecount--;
1491        if (rec.ir_freecount)
1492                error = xfs_inobt_update(cur, &rec);
1493        else
1494                error = xfs_btree_delete(cur, &i);
1495        if (error)
1496                goto error_cur;
1497
1498        /*
1499         * The finobt has now been updated appropriately. We haven't updated the
1500         * agi and superblock yet, so we can create an inobt cursor and validate
1501         * the original freecount. If all is well, make the equivalent update to
1502         * the inobt using the finobt record and offset information.
1503         */
1504        icur = xfs_inobt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_INO);
1505
1506        error = xfs_check_agi_freecount(icur);
1507        if (error)
1508                goto error_icur;
1509
1510        error = xfs_dialloc_ag_update_inobt(icur, &rec, offset);
1511        if (error)
1512                goto error_icur;
1513
1514        /*
1515         * Both trees have now been updated. We must update the perag and
1516         * superblock before we can check the freecount for each btree.
1517         */
1518        be32_add_cpu(&agi->agi_freecount, -1);
1519        xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1520        pag->pagi_freecount--;
1521
1522        xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
1523
1524        error = xfs_check_agi_freecount(icur);
1525        if (error)
1526                goto error_icur;
1527        error = xfs_check_agi_freecount(cur);
1528        if (error)
1529                goto error_icur;
1530
1531        xfs_btree_del_cursor(icur, XFS_BTREE_NOERROR);
1532        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1533        *inop = ino;
1534        return 0;
1535
1536error_icur:
1537        xfs_btree_del_cursor(icur, XFS_BTREE_ERROR);
1538error_cur:
1539        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1540        return error;
1541}
1542
1543static int
1544xfs_dialloc_roll(
1545        struct xfs_trans        **tpp,
1546        struct xfs_buf          *agibp)
1547{
1548        struct xfs_trans        *tp = *tpp;
1549        struct xfs_dquot_acct   *dqinfo;
1550        int                     error;
1551
1552        /*
1553         * Hold to on to the agibp across the commit so no other allocation can
1554         * come in and take the free inodes we just allocated for our caller.
1555         */
1556        xfs_trans_bhold(tp, agibp);
1557
1558        /*
1559         * We want the quota changes to be associated with the next transaction,
1560         * NOT this one. So, detach the dqinfo from this and attach it to the
1561         * next transaction.
1562         */
1563        dqinfo = tp->t_dqinfo;
1564        tp->t_dqinfo = NULL;
1565
1566        error = xfs_trans_roll(&tp);
1567
1568        /* Re-attach the quota info that we detached from prev trx. */
1569        tp->t_dqinfo = dqinfo;
1570
1571        /*
1572         * Join the buffer even on commit error so that the buffer is released
1573         * when the caller cancels the transaction and doesn't have to handle
1574         * this error case specially.
1575         */
1576        xfs_trans_bjoin(tp, agibp);
1577        *tpp = tp;
1578        return error;
1579}
1580
1581static xfs_agnumber_t
1582xfs_ialloc_next_ag(
1583        xfs_mount_t     *mp)
1584{
1585        xfs_agnumber_t  agno;
1586
1587        spin_lock(&mp->m_agirotor_lock);
1588        agno = mp->m_agirotor;
1589        if (++mp->m_agirotor >= mp->m_maxagi)
1590                mp->m_agirotor = 0;
1591        spin_unlock(&mp->m_agirotor_lock);
1592
1593        return agno;
1594}
1595
1596static bool
1597xfs_dialloc_good_ag(
1598        struct xfs_trans        *tp,
1599        struct xfs_perag        *pag,
1600        umode_t                 mode,
1601        int                     flags,
1602        bool                    ok_alloc)
1603{
1604        struct xfs_mount        *mp = tp->t_mountp;
1605        xfs_extlen_t            ineed;
1606        xfs_extlen_t            longest = 0;
1607        int                     needspace;
1608        int                     error;
1609
1610        if (!pag->pagi_inodeok)
1611                return false;
1612
1613        if (!pag->pagi_init) {
1614                error = xfs_ialloc_pagi_init(mp, tp, pag->pag_agno);
1615                if (error)
1616                        return false;
1617        }
1618
1619        if (pag->pagi_freecount)
1620                return true;
1621        if (!ok_alloc)
1622                return false;
1623
1624        if (!pag->pagf_init) {
1625                error = xfs_alloc_pagf_init(mp, tp, pag->pag_agno, flags);
1626                if (error)
1627                        return false;
1628        }
1629
1630        /*
1631         * Check that there is enough free space for the file plus a chunk of
1632         * inodes if we need to allocate some. If this is the first pass across
1633         * the AGs, take into account the potential space needed for alignment
1634         * of inode chunks when checking the longest contiguous free space in
1635         * the AG - this prevents us from getting ENOSPC because we have free
1636         * space larger than ialloc_blks but alignment constraints prevent us
1637         * from using it.
1638         *
1639         * If we can't find an AG with space for full alignment slack to be
1640         * taken into account, we must be near ENOSPC in all AGs.  Hence we
1641         * don't include alignment for the second pass and so if we fail
1642         * allocation due to alignment issues then it is most likely a real
1643         * ENOSPC condition.
1644         *
1645         * XXX(dgc): this calculation is now bogus thanks to the per-ag
1646         * reservations that xfs_alloc_fix_freelist() now does via
1647         * xfs_alloc_space_available(). When the AG fills up, pagf_freeblks will
1648         * be more than large enough for the check below to succeed, but
1649         * xfs_alloc_space_available() will fail because of the non-zero
1650         * metadata reservation and hence we won't actually be able to allocate
1651         * more inodes in this AG. We do soooo much unnecessary work near ENOSPC
1652         * because of this.
1653         */
1654        ineed = M_IGEO(mp)->ialloc_min_blks;
1655        if (flags && ineed > 1)
1656                ineed += M_IGEO(mp)->cluster_align;
1657        longest = pag->pagf_longest;
1658        if (!longest)
1659                longest = pag->pagf_flcount > 0;
1660        needspace = S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode);
1661
1662        if (pag->pagf_freeblks < needspace + ineed || longest < ineed)
1663                return false;
1664        return true;
1665}
1666
1667static int
1668xfs_dialloc_try_ag(
1669        struct xfs_trans        **tpp,
1670        struct xfs_perag        *pag,
1671        xfs_ino_t               parent,
1672        xfs_ino_t               *new_ino,
1673        bool                    ok_alloc)
1674{
1675        struct xfs_buf          *agbp;
1676        xfs_ino_t               ino;
1677        int                     error;
1678
1679        /*
1680         * Then read in the AGI buffer and recheck with the AGI buffer
1681         * lock held.
1682         */
1683        error = xfs_ialloc_read_agi(pag->pag_mount, *tpp, pag->pag_agno, &agbp);
1684        if (error)
1685                return error;
1686
1687        if (!pag->pagi_freecount) {
1688                if (!ok_alloc) {
1689                        error = -EAGAIN;
1690                        goto out_release;
1691                }
1692
1693                error = xfs_ialloc_ag_alloc(*tpp, agbp, pag);
1694                if (error < 0)
1695                        goto out_release;
1696
1697                /*
1698                 * We successfully allocated space for an inode cluster in this
1699                 * AG.  Roll the transaction so that we can allocate one of the
1700                 * new inodes.
1701                 */
1702                ASSERT(pag->pagi_freecount > 0);
1703                error = xfs_dialloc_roll(tpp, agbp);
1704                if (error)
1705                        goto out_release;
1706        }
1707
1708        /* Allocate an inode in the found AG */
1709        error = xfs_dialloc_ag(*tpp, agbp, pag, parent, &ino);
1710        if (!error)
1711                *new_ino = ino;
1712        return error;
1713
1714out_release:
1715        xfs_trans_brelse(*tpp, agbp);
1716        return error;
1717}
1718
1719/*
1720 * Allocate an on-disk inode.
1721 *
1722 * Mode is used to tell whether the new inode is a directory and hence where to
1723 * locate it. The on-disk inode that is allocated will be returned in @new_ino
1724 * on success, otherwise an error will be set to indicate the failure (e.g.
1725 * -ENOSPC).
1726 */
1727int
1728xfs_dialloc(
1729        struct xfs_trans        **tpp,
1730        xfs_ino_t               parent,
1731        umode_t                 mode,
1732        xfs_ino_t               *new_ino)
1733{
1734        struct xfs_mount        *mp = (*tpp)->t_mountp;
1735        xfs_agnumber_t          agno;
1736        int                     error = 0;
1737        xfs_agnumber_t          start_agno;
1738        struct xfs_perag        *pag;
1739        struct xfs_ino_geometry *igeo = M_IGEO(mp);
1740        bool                    ok_alloc = true;
1741        int                     flags;
1742        xfs_ino_t               ino;
1743
1744        /*
1745         * Directories, symlinks, and regular files frequently allocate at least
1746         * one block, so factor that potential expansion when we examine whether
1747         * an AG has enough space for file creation.
1748         */
1749        if (S_ISDIR(mode))
1750                start_agno = xfs_ialloc_next_ag(mp);
1751        else {
1752                start_agno = XFS_INO_TO_AGNO(mp, parent);
1753                if (start_agno >= mp->m_maxagi)
1754                        start_agno = 0;
1755        }
1756
1757        /*
1758         * If we have already hit the ceiling of inode blocks then clear
1759         * ok_alloc so we scan all available agi structures for a free
1760         * inode.
1761         *
1762         * Read rough value of mp->m_icount by percpu_counter_read_positive,
1763         * which will sacrifice the preciseness but improve the performance.
1764         */
1765        if (igeo->maxicount &&
1766            percpu_counter_read_positive(&mp->m_icount) + igeo->ialloc_inos
1767                                                        > igeo->maxicount) {
1768                ok_alloc = false;
1769        }
1770
1771        /*
1772         * Loop until we find an allocation group that either has free inodes
1773         * or in which we can allocate some inodes.  Iterate through the
1774         * allocation groups upward, wrapping at the end.
1775         */
1776        agno = start_agno;
1777        flags = XFS_ALLOC_FLAG_TRYLOCK;
1778        for (;;) {
1779                pag = xfs_perag_get(mp, agno);
1780                if (xfs_dialloc_good_ag(*tpp, pag, mode, flags, ok_alloc)) {
1781                        error = xfs_dialloc_try_ag(tpp, pag, parent,
1782                                        &ino, ok_alloc);
1783                        if (error != -EAGAIN)
1784                                break;
1785                }
1786
1787                if (XFS_FORCED_SHUTDOWN(mp)) {
1788                        error = -EFSCORRUPTED;
1789                        break;
1790                }
1791                if (++agno == mp->m_maxagi)
1792                        agno = 0;
1793                if (agno == start_agno) {
1794                        if (!flags) {
1795                                error = -ENOSPC;
1796                                break;
1797                        }
1798                        flags = 0;
1799                }
1800                xfs_perag_put(pag);
1801        }
1802
1803        if (!error)
1804                *new_ino = ino;
1805        xfs_perag_put(pag);
1806        return error;
1807}
1808
1809/*
1810 * Free the blocks of an inode chunk. We must consider that the inode chunk
1811 * might be sparse and only free the regions that are allocated as part of the
1812 * chunk.
1813 */
1814STATIC void
1815xfs_difree_inode_chunk(
1816        struct xfs_trans                *tp,
1817        xfs_agnumber_t                  agno,
1818        struct xfs_inobt_rec_incore     *rec)
1819{
1820        struct xfs_mount                *mp = tp->t_mountp;
1821        xfs_agblock_t                   sagbno = XFS_AGINO_TO_AGBNO(mp,
1822                                                        rec->ir_startino);
1823        int                             startidx, endidx;
1824        int                             nextbit;
1825        xfs_agblock_t                   agbno;
1826        int                             contigblk;
1827        DECLARE_BITMAP(holemask, XFS_INOBT_HOLEMASK_BITS);
1828
1829        if (!xfs_inobt_issparse(rec->ir_holemask)) {
1830                /* not sparse, calculate extent info directly */
1831                xfs_bmap_add_free(tp, XFS_AGB_TO_FSB(mp, agno, sagbno),
1832                                  M_IGEO(mp)->ialloc_blks,
1833                                  &XFS_RMAP_OINFO_INODES);
1834                return;
1835        }
1836
1837        /* holemask is only 16-bits (fits in an unsigned long) */
1838        ASSERT(sizeof(rec->ir_holemask) <= sizeof(holemask[0]));
1839        holemask[0] = rec->ir_holemask;
1840
1841        /*
1842         * Find contiguous ranges of zeroes (i.e., allocated regions) in the
1843         * holemask and convert the start/end index of each range to an extent.
1844         * We start with the start and end index both pointing at the first 0 in
1845         * the mask.
1846         */
1847        startidx = endidx = find_first_zero_bit(holemask,
1848                                                XFS_INOBT_HOLEMASK_BITS);
1849        nextbit = startidx + 1;
1850        while (startidx < XFS_INOBT_HOLEMASK_BITS) {
1851                nextbit = find_next_zero_bit(holemask, XFS_INOBT_HOLEMASK_BITS,
1852                                             nextbit);
1853                /*
1854                 * If the next zero bit is contiguous, update the end index of
1855                 * the current range and continue.
1856                 */
1857                if (nextbit != XFS_INOBT_HOLEMASK_BITS &&
1858                    nextbit == endidx + 1) {
1859                        endidx = nextbit;
1860                        goto next;
1861                }
1862
1863                /*
1864                 * nextbit is not contiguous with the current end index. Convert
1865                 * the current start/end to an extent and add it to the free
1866                 * list.
1867                 */
1868                agbno = sagbno + (startidx * XFS_INODES_PER_HOLEMASK_BIT) /
1869                                  mp->m_sb.sb_inopblock;
1870                contigblk = ((endidx - startidx + 1) *
1871                             XFS_INODES_PER_HOLEMASK_BIT) /
1872                            mp->m_sb.sb_inopblock;
1873
1874                ASSERT(agbno % mp->m_sb.sb_spino_align == 0);
1875                ASSERT(contigblk % mp->m_sb.sb_spino_align == 0);
1876                xfs_bmap_add_free(tp, XFS_AGB_TO_FSB(mp, agno, agbno),
1877                                  contigblk, &XFS_RMAP_OINFO_INODES);
1878
1879                /* reset range to current bit and carry on... */
1880                startidx = endidx = nextbit;
1881
1882next:
1883                nextbit++;
1884        }
1885}
1886
1887STATIC int
1888xfs_difree_inobt(
1889        struct xfs_mount                *mp,
1890        struct xfs_trans                *tp,
1891        struct xfs_buf                  *agbp,
1892        struct xfs_perag                *pag,
1893        xfs_agino_t                     agino,
1894        struct xfs_icluster             *xic,
1895        struct xfs_inobt_rec_incore     *orec)
1896{
1897        struct xfs_agi                  *agi = agbp->b_addr;
1898        struct xfs_btree_cur            *cur;
1899        struct xfs_inobt_rec_incore     rec;
1900        int                             ilen;
1901        int                             error;
1902        int                             i;
1903        int                             off;
1904
1905        ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
1906        ASSERT(XFS_AGINO_TO_AGBNO(mp, agino) < be32_to_cpu(agi->agi_length));
1907
1908        /*
1909         * Initialize the cursor.
1910         */
1911        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_INO);
1912
1913        error = xfs_check_agi_freecount(cur);
1914        if (error)
1915                goto error0;
1916
1917        /*
1918         * Look for the entry describing this inode.
1919         */
1920        if ((error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i))) {
1921                xfs_warn(mp, "%s: xfs_inobt_lookup() returned error %d.",
1922                        __func__, error);
1923                goto error0;
1924        }
1925        if (XFS_IS_CORRUPT(mp, i != 1)) {
1926                error = -EFSCORRUPTED;
1927                goto error0;
1928        }
1929        error = xfs_inobt_get_rec(cur, &rec, &i);
1930        if (error) {
1931                xfs_warn(mp, "%s: xfs_inobt_get_rec() returned error %d.",
1932                        __func__, error);
1933                goto error0;
1934        }
1935        if (XFS_IS_CORRUPT(mp, i != 1)) {
1936                error = -EFSCORRUPTED;
1937                goto error0;
1938        }
1939        /*
1940         * Get the offset in the inode chunk.
1941         */
1942        off = agino - rec.ir_startino;
1943        ASSERT(off >= 0 && off < XFS_INODES_PER_CHUNK);
1944        ASSERT(!(rec.ir_free & XFS_INOBT_MASK(off)));
1945        /*
1946         * Mark the inode free & increment the count.
1947         */
1948        rec.ir_free |= XFS_INOBT_MASK(off);
1949        rec.ir_freecount++;
1950
1951        /*
1952         * When an inode chunk is free, it becomes eligible for removal. Don't
1953         * remove the chunk if the block size is large enough for multiple inode
1954         * chunks (that might not be free).
1955         */
1956        if (!(mp->m_flags & XFS_MOUNT_IKEEP) &&
1957            rec.ir_free == XFS_INOBT_ALL_FREE &&
1958            mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) {
1959                struct xfs_perag        *pag = agbp->b_pag;
1960
1961                xic->deleted = true;
1962                xic->first_ino = XFS_AGINO_TO_INO(mp, pag->pag_agno,
1963                                rec.ir_startino);
1964                xic->alloc = xfs_inobt_irec_to_allocmask(&rec);
1965
1966                /*
1967                 * Remove the inode cluster from the AGI B+Tree, adjust the
1968                 * AGI and Superblock inode counts, and mark the disk space
1969                 * to be freed when the transaction is committed.
1970                 */
1971                ilen = rec.ir_freecount;
1972                be32_add_cpu(&agi->agi_count, -ilen);
1973                be32_add_cpu(&agi->agi_freecount, -(ilen - 1));
1974                xfs_ialloc_log_agi(tp, agbp, XFS_AGI_COUNT | XFS_AGI_FREECOUNT);
1975                pag->pagi_freecount -= ilen - 1;
1976                pag->pagi_count -= ilen;
1977                xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
1978                xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
1979
1980                if ((error = xfs_btree_delete(cur, &i))) {
1981                        xfs_warn(mp, "%s: xfs_btree_delete returned error %d.",
1982                                __func__, error);
1983                        goto error0;
1984                }
1985
1986                xfs_difree_inode_chunk(tp, pag->pag_agno, &rec);
1987        } else {
1988                xic->deleted = false;
1989
1990                error = xfs_inobt_update(cur, &rec);
1991                if (error) {
1992                        xfs_warn(mp, "%s: xfs_inobt_update returned error %d.",
1993                                __func__, error);
1994                        goto error0;
1995                }
1996
1997                /* 
1998                 * Change the inode free counts and log the ag/sb changes.
1999                 */
2000                be32_add_cpu(&agi->agi_freecount, 1);
2001                xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
2002                pag->pagi_freecount++;
2003                xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, 1);
2004        }
2005
2006        error = xfs_check_agi_freecount(cur);
2007        if (error)
2008                goto error0;
2009
2010        *orec = rec;
2011        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
2012        return 0;
2013
2014error0:
2015        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
2016        return error;
2017}
2018
2019/*
2020 * Free an inode in the free inode btree.
2021 */
2022STATIC int
2023xfs_difree_finobt(
2024        struct xfs_mount                *mp,
2025        struct xfs_trans                *tp,
2026        struct xfs_buf                  *agbp,
2027        struct xfs_perag                *pag,
2028        xfs_agino_t                     agino,
2029        struct xfs_inobt_rec_incore     *ibtrec) /* inobt record */
2030{
2031        struct xfs_btree_cur            *cur;
2032        struct xfs_inobt_rec_incore     rec;
2033        int                             offset = agino - ibtrec->ir_startino;
2034        int                             error;
2035        int                             i;
2036
2037        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_FINO);
2038
2039        error = xfs_inobt_lookup(cur, ibtrec->ir_startino, XFS_LOOKUP_EQ, &i);
2040        if (error)
2041                goto error;
2042        if (i == 0) {
2043                /*
2044                 * If the record does not exist in the finobt, we must have just
2045                 * freed an inode in a previously fully allocated chunk. If not,
2046                 * something is out of sync.
2047                 */
2048                if (XFS_IS_CORRUPT(mp, ibtrec->ir_freecount != 1)) {
2049                        error = -EFSCORRUPTED;
2050                        goto error;
2051                }
2052
2053                error = xfs_inobt_insert_rec(cur, ibtrec->ir_holemask,
2054                                             ibtrec->ir_count,
2055                                             ibtrec->ir_freecount,
2056                                             ibtrec->ir_free, &i);
2057                if (error)
2058                        goto error;
2059                ASSERT(i == 1);
2060
2061                goto out;
2062        }
2063
2064        /*
2065         * Read and update the existing record. We could just copy the ibtrec
2066         * across here, but that would defeat the purpose of having redundant
2067         * metadata. By making the modifications independently, we can catch
2068         * corruptions that we wouldn't see if we just copied from one record
2069         * to another.
2070         */
2071        error = xfs_inobt_get_rec(cur, &rec, &i);
2072        if (error)
2073                goto error;
2074        if (XFS_IS_CORRUPT(mp, i != 1)) {
2075                error = -EFSCORRUPTED;
2076                goto error;
2077        }
2078
2079        rec.ir_free |= XFS_INOBT_MASK(offset);
2080        rec.ir_freecount++;
2081
2082        if (XFS_IS_CORRUPT(mp,
2083                           rec.ir_free != ibtrec->ir_free ||
2084                           rec.ir_freecount != ibtrec->ir_freecount)) {
2085                error = -EFSCORRUPTED;
2086                goto error;
2087        }
2088
2089        /*
2090         * The content of inobt records should always match between the inobt
2091         * and finobt. The lifecycle of records in the finobt is different from
2092         * the inobt in that the finobt only tracks records with at least one
2093         * free inode. Hence, if all of the inodes are free and we aren't
2094         * keeping inode chunks permanently on disk, remove the record.
2095         * Otherwise, update the record with the new information.
2096         *
2097         * Note that we currently can't free chunks when the block size is large
2098         * enough for multiple chunks. Leave the finobt record to remain in sync
2099         * with the inobt.
2100         */
2101        if (rec.ir_free == XFS_INOBT_ALL_FREE &&
2102            mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK &&
2103            !(mp->m_flags & XFS_MOUNT_IKEEP)) {
2104                error = xfs_btree_delete(cur, &i);
2105                if (error)
2106                        goto error;
2107                ASSERT(i == 1);
2108        } else {
2109                error = xfs_inobt_update(cur, &rec);
2110                if (error)
2111                        goto error;
2112        }
2113
2114out:
2115        error = xfs_check_agi_freecount(cur);
2116        if (error)
2117                goto error;
2118
2119        xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
2120        return 0;
2121
2122error:
2123        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
2124        return error;
2125}
2126
2127/*
2128 * Free disk inode.  Carefully avoids touching the incore inode, all
2129 * manipulations incore are the caller's responsibility.
2130 * The on-disk inode is not changed by this operation, only the
2131 * btree (free inode mask) is changed.
2132 */
2133int
2134xfs_difree(
2135        struct xfs_trans        *tp,
2136        struct xfs_perag        *pag,
2137        xfs_ino_t               inode,
2138        struct xfs_icluster     *xic)
2139{
2140        /* REFERENCED */
2141        xfs_agblock_t           agbno;  /* block number containing inode */
2142        struct xfs_buf          *agbp;  /* buffer for allocation group header */
2143        xfs_agino_t             agino;  /* allocation group inode number */
2144        int                     error;  /* error return value */
2145        struct xfs_mount        *mp = tp->t_mountp;
2146        struct xfs_inobt_rec_incore rec;/* btree record */
2147
2148        /*
2149         * Break up inode number into its components.
2150         */
2151        if (pag->pag_agno != XFS_INO_TO_AGNO(mp, inode)) {
2152                xfs_warn(mp, "%s: agno != pag->pag_agno (%d != %d).",
2153                        __func__, XFS_INO_TO_AGNO(mp, inode), pag->pag_agno);
2154                ASSERT(0);
2155                return -EINVAL;
2156        }
2157        agino = XFS_INO_TO_AGINO(mp, inode);
2158        if (inode != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino))  {
2159                xfs_warn(mp, "%s: inode != XFS_AGINO_TO_INO() (%llu != %llu).",
2160                        __func__, (unsigned long long)inode,
2161                        (unsigned long long)XFS_AGINO_TO_INO(mp, pag->pag_agno, agino));
2162                ASSERT(0);
2163                return -EINVAL;
2164        }
2165        agbno = XFS_AGINO_TO_AGBNO(mp, agino);
2166        if (agbno >= mp->m_sb.sb_agblocks)  {
2167                xfs_warn(mp, "%s: agbno >= mp->m_sb.sb_agblocks (%d >= %d).",
2168                        __func__, agbno, mp->m_sb.sb_agblocks);
2169                ASSERT(0);
2170                return -EINVAL;
2171        }
2172        /*
2173         * Get the allocation group header.
2174         */
2175        error = xfs_ialloc_read_agi(mp, tp, pag->pag_agno, &agbp);
2176        if (error) {
2177                xfs_warn(mp, "%s: xfs_ialloc_read_agi() returned error %d.",
2178                        __func__, error);
2179                return error;
2180        }
2181
2182        /*
2183         * Fix up the inode allocation btree.
2184         */
2185        error = xfs_difree_inobt(mp, tp, agbp, pag, agino, xic, &rec);
2186        if (error)
2187                goto error0;
2188
2189        /*
2190         * Fix up the free inode btree.
2191         */
2192        if (xfs_sb_version_hasfinobt(&mp->m_sb)) {
2193                error = xfs_difree_finobt(mp, tp, agbp, pag, agino, &rec);
2194                if (error)
2195                        goto error0;
2196        }
2197
2198        return 0;
2199
2200error0:
2201        return error;
2202}
2203
2204STATIC int
2205xfs_imap_lookup(
2206        struct xfs_mount        *mp,
2207        struct xfs_trans        *tp,
2208        struct xfs_perag        *pag,
2209        xfs_agino_t             agino,
2210        xfs_agblock_t           agbno,
2211        xfs_agblock_t           *chunk_agbno,
2212        xfs_agblock_t           *offset_agbno,
2213        int                     flags)
2214{
2215        struct xfs_inobt_rec_incore rec;
2216        struct xfs_btree_cur    *cur;
2217        struct xfs_buf          *agbp;
2218        int                     error;
2219        int                     i;
2220
2221        error = xfs_ialloc_read_agi(mp, tp, pag->pag_agno, &agbp);
2222        if (error) {
2223                xfs_alert(mp,
2224                        "%s: xfs_ialloc_read_agi() returned error %d, agno %d",
2225                        __func__, error, pag->pag_agno);
2226                return error;
2227        }
2228
2229        /*
2230         * Lookup the inode record for the given agino. If the record cannot be
2231         * found, then it's an invalid inode number and we should abort. Once
2232         * we have a record, we need to ensure it contains the inode number
2233         * we are looking up.
2234         */
2235        cur = xfs_inobt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_INO);
2236        error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i);
2237        if (!error) {
2238                if (i)
2239                        error = xfs_inobt_get_rec(cur, &rec, &i);
2240                if (!error && i == 0)
2241                        error = -EINVAL;
2242        }
2243
2244        xfs_trans_brelse(tp, agbp);
2245        xfs_btree_del_cursor(cur, error);
2246        if (error)
2247                return error;
2248
2249        /* check that the returned record contains the required inode */
2250        if (rec.ir_startino > agino ||
2251            rec.ir_startino + M_IGEO(mp)->ialloc_inos <= agino)
2252                return -EINVAL;
2253
2254        /* for untrusted inodes check it is allocated first */
2255        if ((flags & XFS_IGET_UNTRUSTED) &&
2256            (rec.ir_free & XFS_INOBT_MASK(agino - rec.ir_startino)))
2257                return -EINVAL;
2258
2259        *chunk_agbno = XFS_AGINO_TO_AGBNO(mp, rec.ir_startino);
2260        *offset_agbno = agbno - *chunk_agbno;
2261        return 0;
2262}
2263
2264/*
2265 * Return the location of the inode in imap, for mapping it into a buffer.
2266 */
2267int
2268xfs_imap(
2269        struct xfs_mount         *mp,   /* file system mount structure */
2270        struct xfs_trans         *tp,   /* transaction pointer */
2271        xfs_ino_t               ino,    /* inode to locate */
2272        struct xfs_imap         *imap,  /* location map structure */
2273        uint                    flags)  /* flags for inode btree lookup */
2274{
2275        xfs_agblock_t           agbno;  /* block number of inode in the alloc group */
2276        xfs_agino_t             agino;  /* inode number within alloc group */
2277        xfs_agblock_t           chunk_agbno;    /* first block in inode chunk */
2278        xfs_agblock_t           cluster_agbno;  /* first block in inode cluster */
2279        int                     error;  /* error code */
2280        int                     offset; /* index of inode in its buffer */
2281        xfs_agblock_t           offset_agbno;   /* blks from chunk start to inode */
2282        struct xfs_perag        *pag;
2283
2284        ASSERT(ino != NULLFSINO);
2285
2286        /*
2287         * Split up the inode number into its parts.
2288         */
2289        pag = xfs_perag_get(mp, XFS_INO_TO_AGNO(mp, ino));
2290        agino = XFS_INO_TO_AGINO(mp, ino);
2291        agbno = XFS_AGINO_TO_AGBNO(mp, agino);
2292        if (!pag || agbno >= mp->m_sb.sb_agblocks ||
2293            ino != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2294                error = -EINVAL;
2295#ifdef DEBUG
2296                /*
2297                 * Don't output diagnostic information for untrusted inodes
2298                 * as they can be invalid without implying corruption.
2299                 */
2300                if (flags & XFS_IGET_UNTRUSTED)
2301                        goto out_drop;
2302                if (!pag) {
2303                        xfs_alert(mp,
2304                                "%s: agno (%d) >= mp->m_sb.sb_agcount (%d)",
2305                                __func__, XFS_INO_TO_AGNO(mp, ino),
2306                                mp->m_sb.sb_agcount);
2307                }
2308                if (agbno >= mp->m_sb.sb_agblocks) {
2309                        xfs_alert(mp,
2310                "%s: agbno (0x%llx) >= mp->m_sb.sb_agblocks (0x%lx)",
2311                                __func__, (unsigned long long)agbno,
2312                                (unsigned long)mp->m_sb.sb_agblocks);
2313                }
2314                if (pag && ino != XFS_AGINO_TO_INO(mp, pag->pag_agno, agino)) {
2315                        xfs_alert(mp,
2316                "%s: ino (0x%llx) != XFS_AGINO_TO_INO() (0x%llx)",
2317                                __func__, ino,
2318                                XFS_AGINO_TO_INO(mp, pag->pag_agno, agino));
2319                }
2320                xfs_stack_trace();
2321#endif /* DEBUG */
2322                goto out_drop;
2323        }
2324
2325        /*
2326         * For bulkstat and handle lookups, we have an untrusted inode number
2327         * that we have to verify is valid. We cannot do this just by reading
2328         * the inode buffer as it may have been unlinked and removed leaving
2329         * inodes in stale state on disk. Hence we have to do a btree lookup
2330         * in all cases where an untrusted inode number is passed.
2331         */
2332        if (flags & XFS_IGET_UNTRUSTED) {
2333                error = xfs_imap_lookup(mp, tp, pag, agino, agbno,
2334                                        &chunk_agbno, &offset_agbno, flags);
2335                if (error)
2336                        goto out_drop;
2337                goto out_map;
2338        }
2339
2340        /*
2341         * If the inode cluster size is the same as the blocksize or
2342         * smaller we get to the buffer by simple arithmetics.
2343         */
2344        if (M_IGEO(mp)->blocks_per_cluster == 1) {
2345                offset = XFS_INO_TO_OFFSET(mp, ino);
2346                ASSERT(offset < mp->m_sb.sb_inopblock);
2347
2348                imap->im_blkno = XFS_AGB_TO_DADDR(mp, pag->pag_agno, agbno);
2349                imap->im_len = XFS_FSB_TO_BB(mp, 1);
2350                imap->im_boffset = (unsigned short)(offset <<
2351                                                        mp->m_sb.sb_inodelog);
2352                error = 0;
2353                goto out_drop;
2354        }
2355
2356        /*
2357         * If the inode chunks are aligned then use simple maths to
2358         * find the location. Otherwise we have to do a btree
2359         * lookup to find the location.
2360         */
2361        if (M_IGEO(mp)->inoalign_mask) {
2362                offset_agbno = agbno & M_IGEO(mp)->inoalign_mask;
2363                chunk_agbno = agbno - offset_agbno;
2364        } else {
2365                error = xfs_imap_lookup(mp, tp, pag, agino, agbno,
2366                                        &chunk_agbno, &offset_agbno, flags);
2367                if (error)
2368                        goto out_drop;
2369        }
2370
2371out_map:
2372        ASSERT(agbno >= chunk_agbno);
2373        cluster_agbno = chunk_agbno +
2374                ((offset_agbno / M_IGEO(mp)->blocks_per_cluster) *
2375                 M_IGEO(mp)->blocks_per_cluster);
2376        offset = ((agbno - cluster_agbno) * mp->m_sb.sb_inopblock) +
2377                XFS_INO_TO_OFFSET(mp, ino);
2378
2379        imap->im_blkno = XFS_AGB_TO_DADDR(mp, pag->pag_agno, cluster_agbno);
2380        imap->im_len = XFS_FSB_TO_BB(mp, M_IGEO(mp)->blocks_per_cluster);
2381        imap->im_boffset = (unsigned short)(offset << mp->m_sb.sb_inodelog);
2382
2383        /*
2384         * If the inode number maps to a block outside the bounds
2385         * of the file system then return NULL rather than calling
2386         * read_buf and panicing when we get an error from the
2387         * driver.
2388         */
2389        if ((imap->im_blkno + imap->im_len) >
2390            XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks)) {
2391                xfs_alert(mp,
2392        "%s: (im_blkno (0x%llx) + im_len (0x%llx)) > sb_dblocks (0x%llx)",
2393                        __func__, (unsigned long long) imap->im_blkno,
2394                        (unsigned long long) imap->im_len,
2395                        XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks));
2396                error = -EINVAL;
2397                goto out_drop;
2398        }
2399        error = 0;
2400out_drop:
2401        if (pag)
2402                xfs_perag_put(pag);
2403        return error;
2404}
2405
2406/*
2407 * Log specified fields for the ag hdr (inode section). The growth of the agi
2408 * structure over time requires that we interpret the buffer as two logical
2409 * regions delineated by the end of the unlinked list. This is due to the size
2410 * of the hash table and its location in the middle of the agi.
2411 *
2412 * For example, a request to log a field before agi_unlinked and a field after
2413 * agi_unlinked could cause us to log the entire hash table and use an excessive
2414 * amount of log space. To avoid this behavior, log the region up through
2415 * agi_unlinked in one call and the region after agi_unlinked through the end of
2416 * the structure in another.
2417 */
2418void
2419xfs_ialloc_log_agi(
2420        xfs_trans_t     *tp,            /* transaction pointer */
2421        struct xfs_buf  *bp,            /* allocation group header buffer */
2422        int             fields)         /* bitmask of fields to log */
2423{
2424        int                     first;          /* first byte number */
2425        int                     last;           /* last byte number */
2426        static const short      offsets[] = {   /* field starting offsets */
2427                                        /* keep in sync with bit definitions */
2428                offsetof(xfs_agi_t, agi_magicnum),
2429                offsetof(xfs_agi_t, agi_versionnum),
2430                offsetof(xfs_agi_t, agi_seqno),
2431                offsetof(xfs_agi_t, agi_length),
2432                offsetof(xfs_agi_t, agi_count),
2433                offsetof(xfs_agi_t, agi_root),
2434                offsetof(xfs_agi_t, agi_level),
2435                offsetof(xfs_agi_t, agi_freecount),
2436                offsetof(xfs_agi_t, agi_newino),
2437                offsetof(xfs_agi_t, agi_dirino),
2438                offsetof(xfs_agi_t, agi_unlinked),
2439                offsetof(xfs_agi_t, agi_free_root),
2440                offsetof(xfs_agi_t, agi_free_level),
2441                offsetof(xfs_agi_t, agi_iblocks),
2442                sizeof(xfs_agi_t)
2443        };
2444#ifdef DEBUG
2445        struct xfs_agi          *agi = bp->b_addr;
2446
2447        ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
2448#endif
2449
2450        /*
2451         * Compute byte offsets for the first and last fields in the first
2452         * region and log the agi buffer. This only logs up through
2453         * agi_unlinked.
2454         */
2455        if (fields & XFS_AGI_ALL_BITS_R1) {
2456                xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R1,
2457                                  &first, &last);
2458                xfs_trans_log_buf(tp, bp, first, last);
2459        }
2460
2461        /*
2462         * Mask off the bits in the first region and calculate the first and
2463         * last field offsets for any bits in the second region.
2464         */
2465        fields &= ~XFS_AGI_ALL_BITS_R1;
2466        if (fields) {
2467                xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R2,
2468                                  &first, &last);
2469                xfs_trans_log_buf(tp, bp, first, last);
2470        }
2471}
2472
2473static xfs_failaddr_t
2474xfs_agi_verify(
2475        struct xfs_buf  *bp)
2476{
2477        struct xfs_mount *mp = bp->b_mount;
2478        struct xfs_agi  *agi = bp->b_addr;
2479        int             i;
2480
2481        if (xfs_sb_version_hascrc(&mp->m_sb)) {
2482                if (!uuid_equal(&agi->agi_uuid, &mp->m_sb.sb_meta_uuid))
2483                        return __this_address;
2484                if (!xfs_log_check_lsn(mp, be64_to_cpu(agi->agi_lsn)))
2485                        return __this_address;
2486        }
2487
2488        /*
2489         * Validate the magic number of the agi block.
2490         */
2491        if (!xfs_verify_magic(bp, agi->agi_magicnum))
2492                return __this_address;
2493        if (!XFS_AGI_GOOD_VERSION(be32_to_cpu(agi->agi_versionnum)))
2494                return __this_address;
2495
2496        if (be32_to_cpu(agi->agi_level) < 1 ||
2497            be32_to_cpu(agi->agi_level) > M_IGEO(mp)->inobt_maxlevels)
2498                return __this_address;
2499
2500        if (xfs_sb_version_hasfinobt(&mp->m_sb) &&
2501            (be32_to_cpu(agi->agi_free_level) < 1 ||
2502             be32_to_cpu(agi->agi_free_level) > M_IGEO(mp)->inobt_maxlevels))
2503                return __this_address;
2504
2505        /*
2506         * during growfs operations, the perag is not fully initialised,
2507         * so we can't use it for any useful checking. growfs ensures we can't
2508         * use it by using uncached buffers that don't have the perag attached
2509         * so we can detect and avoid this problem.
2510         */
2511        if (bp->b_pag && be32_to_cpu(agi->agi_seqno) != bp->b_pag->pag_agno)
2512                return __this_address;
2513
2514        for (i = 0; i < XFS_AGI_UNLINKED_BUCKETS; i++) {
2515                if (agi->agi_unlinked[i] == cpu_to_be32(NULLAGINO))
2516                        continue;
2517                if (!xfs_verify_ino(mp, be32_to_cpu(agi->agi_unlinked[i])))
2518                        return __this_address;
2519        }
2520
2521        return NULL;
2522}
2523
2524static void
2525xfs_agi_read_verify(
2526        struct xfs_buf  *bp)
2527{
2528        struct xfs_mount *mp = bp->b_mount;
2529        xfs_failaddr_t  fa;
2530
2531        if (xfs_sb_version_hascrc(&mp->m_sb) &&
2532            !xfs_buf_verify_cksum(bp, XFS_AGI_CRC_OFF))
2533                xfs_verifier_error(bp, -EFSBADCRC, __this_address);
2534        else {
2535                fa = xfs_agi_verify(bp);
2536                if (XFS_TEST_ERROR(fa, mp, XFS_ERRTAG_IALLOC_READ_AGI))
2537                        xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2538        }
2539}
2540
2541static void
2542xfs_agi_write_verify(
2543        struct xfs_buf  *bp)
2544{
2545        struct xfs_mount        *mp = bp->b_mount;
2546        struct xfs_buf_log_item *bip = bp->b_log_item;
2547        struct xfs_agi          *agi = bp->b_addr;
2548        xfs_failaddr_t          fa;
2549
2550        fa = xfs_agi_verify(bp);
2551        if (fa) {
2552                xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2553                return;
2554        }
2555
2556        if (!xfs_sb_version_hascrc(&mp->m_sb))
2557                return;
2558
2559        if (bip)
2560                agi->agi_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2561        xfs_buf_update_cksum(bp, XFS_AGI_CRC_OFF);
2562}
2563
2564const struct xfs_buf_ops xfs_agi_buf_ops = {
2565        .name = "xfs_agi",
2566        .magic = { cpu_to_be32(XFS_AGI_MAGIC), cpu_to_be32(XFS_AGI_MAGIC) },
2567        .verify_read = xfs_agi_read_verify,
2568        .verify_write = xfs_agi_write_verify,
2569        .verify_struct = xfs_agi_verify,
2570};
2571
2572/*
2573 * Read in the allocation group header (inode allocation section)
2574 */
2575int
2576xfs_read_agi(
2577        struct xfs_mount        *mp,    /* file system mount structure */
2578        struct xfs_trans        *tp,    /* transaction pointer */
2579        xfs_agnumber_t          agno,   /* allocation group number */
2580        struct xfs_buf          **bpp)  /* allocation group hdr buf */
2581{
2582        int                     error;
2583
2584        trace_xfs_read_agi(mp, agno);
2585
2586        ASSERT(agno != NULLAGNUMBER);
2587        error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
2588                        XFS_AG_DADDR(mp, agno, XFS_AGI_DADDR(mp)),
2589                        XFS_FSS_TO_BB(mp, 1), 0, bpp, &xfs_agi_buf_ops);
2590        if (error)
2591                return error;
2592        if (tp)
2593                xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_AGI_BUF);
2594
2595        xfs_buf_set_ref(*bpp, XFS_AGI_REF);
2596        return 0;
2597}
2598
2599int
2600xfs_ialloc_read_agi(
2601        struct xfs_mount        *mp,    /* file system mount structure */
2602        struct xfs_trans        *tp,    /* transaction pointer */
2603        xfs_agnumber_t          agno,   /* allocation group number */
2604        struct xfs_buf          **bpp)  /* allocation group hdr buf */
2605{
2606        struct xfs_agi          *agi;   /* allocation group header */
2607        struct xfs_perag        *pag;   /* per allocation group data */
2608        int                     error;
2609
2610        trace_xfs_ialloc_read_agi(mp, agno);
2611
2612        error = xfs_read_agi(mp, tp, agno, bpp);
2613        if (error)
2614                return error;
2615
2616        agi = (*bpp)->b_addr;
2617        pag = (*bpp)->b_pag;
2618        if (!pag->pagi_init) {
2619                pag->pagi_freecount = be32_to_cpu(agi->agi_freecount);
2620                pag->pagi_count = be32_to_cpu(agi->agi_count);
2621                pag->pagi_init = 1;
2622        }
2623
2624        /*
2625         * It's possible for these to be out of sync if
2626         * we are in the middle of a forced shutdown.
2627         */
2628        ASSERT(pag->pagi_freecount == be32_to_cpu(agi->agi_freecount) ||
2629                XFS_FORCED_SHUTDOWN(mp));
2630        return 0;
2631}
2632
2633/*
2634 * Read in the agi to initialise the per-ag data in the mount structure
2635 */
2636int
2637xfs_ialloc_pagi_init(
2638        xfs_mount_t     *mp,            /* file system mount structure */
2639        xfs_trans_t     *tp,            /* transaction pointer */
2640        xfs_agnumber_t  agno)           /* allocation group number */
2641{
2642        struct xfs_buf  *bp = NULL;
2643        int             error;
2644
2645        error = xfs_ialloc_read_agi(mp, tp, agno, &bp);
2646        if (error)
2647                return error;
2648        if (bp)
2649                xfs_trans_brelse(tp, bp);
2650        return 0;
2651}
2652
2653/* Is there an inode record covering a given range of inode numbers? */
2654int
2655xfs_ialloc_has_inode_record(
2656        struct xfs_btree_cur    *cur,
2657        xfs_agino_t             low,
2658        xfs_agino_t             high,
2659        bool                    *exists)
2660{
2661        struct xfs_inobt_rec_incore     irec;
2662        xfs_agino_t             agino;
2663        uint16_t                holemask;
2664        int                     has_record;
2665        int                     i;
2666        int                     error;
2667
2668        *exists = false;
2669        error = xfs_inobt_lookup(cur, low, XFS_LOOKUP_LE, &has_record);
2670        while (error == 0 && has_record) {
2671                error = xfs_inobt_get_rec(cur, &irec, &has_record);
2672                if (error || irec.ir_startino > high)
2673                        break;
2674
2675                agino = irec.ir_startino;
2676                holemask = irec.ir_holemask;
2677                for (i = 0; i < XFS_INOBT_HOLEMASK_BITS; holemask >>= 1,
2678                                i++, agino += XFS_INODES_PER_HOLEMASK_BIT) {
2679                        if (holemask & 1)
2680                                continue;
2681                        if (agino + XFS_INODES_PER_HOLEMASK_BIT > low &&
2682                                        agino <= high) {
2683                                *exists = true;
2684                                return 0;
2685                        }
2686                }
2687
2688                error = xfs_btree_increment(cur, 0, &has_record);
2689        }
2690        return error;
2691}
2692
2693/* Is there an inode record covering a given extent? */
2694int
2695xfs_ialloc_has_inodes_at_extent(
2696        struct xfs_btree_cur    *cur,
2697        xfs_agblock_t           bno,
2698        xfs_extlen_t            len,
2699        bool                    *exists)
2700{
2701        xfs_agino_t             low;
2702        xfs_agino_t             high;
2703
2704        low = XFS_AGB_TO_AGINO(cur->bc_mp, bno);
2705        high = XFS_AGB_TO_AGINO(cur->bc_mp, bno + len) - 1;
2706
2707        return xfs_ialloc_has_inode_record(cur, low, high, exists);
2708}
2709
2710struct xfs_ialloc_count_inodes {
2711        xfs_agino_t                     count;
2712        xfs_agino_t                     freecount;
2713};
2714
2715/* Record inode counts across all inobt records. */
2716STATIC int
2717xfs_ialloc_count_inodes_rec(
2718        struct xfs_btree_cur            *cur,
2719        union xfs_btree_rec             *rec,
2720        void                            *priv)
2721{
2722        struct xfs_inobt_rec_incore     irec;
2723        struct xfs_ialloc_count_inodes  *ci = priv;
2724
2725        xfs_inobt_btrec_to_irec(cur->bc_mp, rec, &irec);
2726        ci->count += irec.ir_count;
2727        ci->freecount += irec.ir_freecount;
2728
2729        return 0;
2730}
2731
2732/* Count allocated and free inodes under an inobt. */
2733int
2734xfs_ialloc_count_inodes(
2735        struct xfs_btree_cur            *cur,
2736        xfs_agino_t                     *count,
2737        xfs_agino_t                     *freecount)
2738{
2739        struct xfs_ialloc_count_inodes  ci = {0};
2740        int                             error;
2741
2742        ASSERT(cur->bc_btnum == XFS_BTNUM_INO);
2743        error = xfs_btree_query_all(cur, xfs_ialloc_count_inodes_rec, &ci);
2744        if (error)
2745                return error;
2746
2747        *count = ci.count;
2748        *freecount = ci.freecount;
2749        return 0;
2750}
2751
2752/*
2753 * Initialize inode-related geometry information.
2754 *
2755 * Compute the inode btree min and max levels and set maxicount.
2756 *
2757 * Set the inode cluster size.  This may still be overridden by the file
2758 * system block size if it is larger than the chosen cluster size.
2759 *
2760 * For v5 filesystems, scale the cluster size with the inode size to keep a
2761 * constant ratio of inode per cluster buffer, but only if mkfs has set the
2762 * inode alignment value appropriately for larger cluster sizes.
2763 *
2764 * Then compute the inode cluster alignment information.
2765 */
2766void
2767xfs_ialloc_setup_geometry(
2768        struct xfs_mount        *mp)
2769{
2770        struct xfs_sb           *sbp = &mp->m_sb;
2771        struct xfs_ino_geometry *igeo = M_IGEO(mp);
2772        uint64_t                icount;
2773        uint                    inodes;
2774
2775        igeo->new_diflags2 = 0;
2776        if (xfs_sb_version_hasbigtime(&mp->m_sb))
2777                igeo->new_diflags2 |= XFS_DIFLAG2_BIGTIME;
2778
2779        /* Compute inode btree geometry. */
2780        igeo->agino_log = sbp->sb_inopblog + sbp->sb_agblklog;
2781        igeo->inobt_mxr[0] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, 1);
2782        igeo->inobt_mxr[1] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, 0);
2783        igeo->inobt_mnr[0] = igeo->inobt_mxr[0] / 2;
2784        igeo->inobt_mnr[1] = igeo->inobt_mxr[1] / 2;
2785
2786        igeo->ialloc_inos = max_t(uint16_t, XFS_INODES_PER_CHUNK,
2787                        sbp->sb_inopblock);
2788        igeo->ialloc_blks = igeo->ialloc_inos >> sbp->sb_inopblog;
2789
2790        if (sbp->sb_spino_align)
2791                igeo->ialloc_min_blks = sbp->sb_spino_align;
2792        else
2793                igeo->ialloc_min_blks = igeo->ialloc_blks;
2794
2795        /* Compute and fill in value of m_ino_geo.inobt_maxlevels. */
2796        inodes = (1LL << XFS_INO_AGINO_BITS(mp)) >> XFS_INODES_PER_CHUNK_LOG;
2797        igeo->inobt_maxlevels = xfs_btree_compute_maxlevels(igeo->inobt_mnr,
2798                        inodes);
2799
2800        /*
2801         * Set the maximum inode count for this filesystem, being careful not
2802         * to use obviously garbage sb_inopblog/sb_inopblock values.  Regular
2803         * users should never get here due to failing sb verification, but
2804         * certain users (xfs_db) need to be usable even with corrupt metadata.
2805         */
2806        if (sbp->sb_imax_pct && igeo->ialloc_blks) {
2807                /*
2808                 * Make sure the maximum inode count is a multiple
2809                 * of the units we allocate inodes in.
2810                 */
2811                icount = sbp->sb_dblocks * sbp->sb_imax_pct;
2812                do_div(icount, 100);
2813                do_div(icount, igeo->ialloc_blks);
2814                igeo->maxicount = XFS_FSB_TO_INO(mp,
2815                                icount * igeo->ialloc_blks);
2816        } else {
2817                igeo->maxicount = 0;
2818        }
2819
2820        /*
2821         * Compute the desired size of an inode cluster buffer size, which
2822         * starts at 8K and (on v5 filesystems) scales up with larger inode
2823         * sizes.
2824         *
2825         * Preserve the desired inode cluster size because the sparse inodes
2826         * feature uses that desired size (not the actual size) to compute the
2827         * sparse inode alignment.  The mount code validates this value, so we
2828         * cannot change the behavior.
2829         */
2830        igeo->inode_cluster_size_raw = XFS_INODE_BIG_CLUSTER_SIZE;
2831        if (xfs_sb_version_has_v3inode(&mp->m_sb)) {
2832                int     new_size = igeo->inode_cluster_size_raw;
2833
2834                new_size *= mp->m_sb.sb_inodesize / XFS_DINODE_MIN_SIZE;
2835                if (mp->m_sb.sb_inoalignmt >= XFS_B_TO_FSBT(mp, new_size))
2836                        igeo->inode_cluster_size_raw = new_size;
2837        }
2838
2839        /* Calculate inode cluster ratios. */
2840        if (igeo->inode_cluster_size_raw > mp->m_sb.sb_blocksize)
2841                igeo->blocks_per_cluster = XFS_B_TO_FSBT(mp,
2842                                igeo->inode_cluster_size_raw);
2843        else
2844                igeo->blocks_per_cluster = 1;
2845        igeo->inode_cluster_size = XFS_FSB_TO_B(mp, igeo->blocks_per_cluster);
2846        igeo->inodes_per_cluster = XFS_FSB_TO_INO(mp, igeo->blocks_per_cluster);
2847
2848        /* Calculate inode cluster alignment. */
2849        if (xfs_sb_version_hasalign(&mp->m_sb) &&
2850            mp->m_sb.sb_inoalignmt >= igeo->blocks_per_cluster)
2851                igeo->cluster_align = mp->m_sb.sb_inoalignmt;
2852        else
2853                igeo->cluster_align = 1;
2854        igeo->inoalign_mask = igeo->cluster_align - 1;
2855        igeo->cluster_align_inodes = XFS_FSB_TO_INO(mp, igeo->cluster_align);
2856
2857        /*
2858         * If we are using stripe alignment, check whether
2859         * the stripe unit is a multiple of the inode alignment
2860         */
2861        if (mp->m_dalign && igeo->inoalign_mask &&
2862            !(mp->m_dalign & igeo->inoalign_mask))
2863                igeo->ialloc_align = mp->m_dalign;
2864        else
2865                igeo->ialloc_align = 0;
2866}
2867
2868/* Compute the location of the root directory inode that is laid out by mkfs. */
2869xfs_ino_t
2870xfs_ialloc_calc_rootino(
2871        struct xfs_mount        *mp,
2872        int                     sunit)
2873{
2874        struct xfs_ino_geometry *igeo = M_IGEO(mp);
2875        xfs_agblock_t           first_bno;
2876
2877        /*
2878         * Pre-calculate the geometry of AG 0.  We know what it looks like
2879         * because libxfs knows how to create allocation groups now.
2880         *
2881         * first_bno is the first block in which mkfs could possibly have
2882         * allocated the root directory inode, once we factor in the metadata
2883         * that mkfs formats before it.  Namely, the four AG headers...
2884         */
2885        first_bno = howmany(4 * mp->m_sb.sb_sectsize, mp->m_sb.sb_blocksize);
2886
2887        /* ...the two free space btree roots... */
2888        first_bno += 2;
2889
2890        /* ...the inode btree root... */
2891        first_bno += 1;
2892
2893        /* ...the initial AGFL... */
2894        first_bno += xfs_alloc_min_freelist(mp, NULL);
2895
2896        /* ...the free inode btree root... */
2897        if (xfs_sb_version_hasfinobt(&mp->m_sb))
2898                first_bno++;
2899
2900        /* ...the reverse mapping btree root... */
2901        if (xfs_sb_version_hasrmapbt(&mp->m_sb))
2902                first_bno++;
2903
2904        /* ...the reference count btree... */
2905        if (xfs_sb_version_hasreflink(&mp->m_sb))
2906                first_bno++;
2907
2908        /*
2909         * ...and the log, if it is allocated in the first allocation group.
2910         *
2911         * This can happen with filesystems that only have a single
2912         * allocation group, or very odd geometries created by old mkfs
2913         * versions on very small filesystems.
2914         */
2915        if (mp->m_sb.sb_logstart &&
2916            XFS_FSB_TO_AGNO(mp, mp->m_sb.sb_logstart) == 0)
2917                 first_bno += mp->m_sb.sb_logblocks;
2918
2919        /*
2920         * Now round first_bno up to whatever allocation alignment is given
2921         * by the filesystem or was passed in.
2922         */
2923        if (xfs_sb_version_hasdalign(&mp->m_sb) && igeo->ialloc_align > 0)
2924                first_bno = roundup(first_bno, sunit);
2925        else if (xfs_sb_version_hasalign(&mp->m_sb) &&
2926                        mp->m_sb.sb_inoalignmt > 1)
2927                first_bno = roundup(first_bno, mp->m_sb.sb_inoalignmt);
2928
2929        return XFS_AGINO_TO_INO(mp, 0, XFS_AGB_TO_AGINO(mp, first_bno));
2930}
2931
2932/*
2933 * Ensure there are not sparse inode clusters that cross the new EOAG.
2934 *
2935 * This is a no-op for non-spinode filesystems since clusters are always fully
2936 * allocated and checking the bnobt suffices.  However, a spinode filesystem
2937 * could have a record where the upper inodes are free blocks.  If those blocks
2938 * were removed from the filesystem, the inode record would extend beyond EOAG,
2939 * which will be flagged as corruption.
2940 */
2941int
2942xfs_ialloc_check_shrink(
2943        struct xfs_trans        *tp,
2944        xfs_agnumber_t          agno,
2945        struct xfs_buf          *agibp,
2946        xfs_agblock_t           new_length)
2947{
2948        struct xfs_inobt_rec_incore rec;
2949        struct xfs_btree_cur    *cur;
2950        struct xfs_mount        *mp = tp->t_mountp;
2951        struct xfs_perag        *pag;
2952        xfs_agino_t             agino = XFS_AGB_TO_AGINO(mp, new_length);
2953        int                     has;
2954        int                     error;
2955
2956        if (!xfs_sb_version_hassparseinodes(&mp->m_sb))
2957                return 0;
2958
2959        pag = xfs_perag_get(mp, agno);
2960        cur = xfs_inobt_init_cursor(mp, tp, agibp, pag, XFS_BTNUM_INO);
2961
2962        /* Look up the inobt record that would correspond to the new EOFS. */
2963        error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &has);
2964        if (error || !has)
2965                goto out;
2966
2967        error = xfs_inobt_get_rec(cur, &rec, &has);
2968        if (error)
2969                goto out;
2970
2971        if (!has) {
2972                error = -EFSCORRUPTED;
2973                goto out;
2974        }
2975
2976        /* If the record covers inodes that would be beyond EOFS, bail out. */
2977        if (rec.ir_startino + XFS_INODES_PER_CHUNK > agino) {
2978                error = -ENOSPC;
2979                goto out;
2980        }
2981out:
2982        xfs_btree_del_cursor(cur, error);
2983        xfs_perag_put(pag);
2984        return error;
2985}
2986