fs/xfs/xfs_inode_fork.c

   1 /*
   2  * Copyright (c) 2000-2006 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include <linux/log2.h>
  19
  20 #include "xfs.h"
  21 #include "xfs_fs.h"
  22 #include "xfs_format.h"
  23 #include "xfs_log.h"
  24 #include "xfs_inum.h"
  25 #include "xfs_trans.h"
  26 #include "xfs_trans_priv.h"
  27 #include "xfs_sb.h"
  28 #include "xfs_ag.h"
  29 #include "xfs_mount.h"
  30 #include "xfs_bmap_btree.h"
  31 #include "xfs_alloc_btree.h"
  32 #include "xfs_ialloc_btree.h"
  33 #include "xfs_attr_sf.h"
  34 #include "xfs_dinode.h"
  35 #include "xfs_inode.h"
  36 #include "xfs_buf_item.h"
  37 #include "xfs_inode_item.h"
  38 #include "xfs_btree.h"
  39 #include "xfs_alloc.h"
  40 #include "xfs_ialloc.h"
  41 #include "xfs_bmap.h"
  42 #include "xfs_error.h"
  43 #include "xfs_quota.h"
  44 #include "xfs_filestream.h"
  45 #include "xfs_cksum.h"
  46 #include "xfs_trace.h"
  47 #include "xfs_icache.h"
  48
  49 kmem_zone_t *xfs_ifork_zone;
  50
  51 STATIC int xfs_iformat_local(xfs_inode_t *, xfs_dinode_t *, int, int);
  52 STATIC int xfs_iformat_extents(xfs_inode_t *, xfs_dinode_t *, int);
  53 STATIC int xfs_iformat_btree(xfs_inode_t *, xfs_dinode_t *, int);
  54
  55 #ifdef DEBUG
  56 /*
  57  * Make sure that the extents in the given memory buffer
  58  * are valid.
  59  */
  60 void
  61 xfs_validate_extents(
  62         xfs_ifork_t             *ifp,
  63         int                     nrecs,
  64         xfs_exntfmt_t           fmt)
  65 {
  66         xfs_bmbt_irec_t         irec;
  67         xfs_bmbt_rec_host_t     rec;
  68         int                     i;
  69
  70         for (i = 0; i < nrecs; i++) {
  71                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, i);
  72                 rec.l0 = get_unaligned(&ep->l0);
  73                 rec.l1 = get_unaligned(&ep->l1);
  74                 xfs_bmbt_get_all(&rec, &irec);
  75                 if (fmt == XFS_EXTFMT_NOSTATE)
  76                         ASSERT(irec.br_state == XFS_EXT_NORM);
  77         }
  78 }
  79 #else /* DEBUG */
  80 #define xfs_validate_extents(ifp, nrecs, fmt)
  81 #endif /* DEBUG */
  82
  83
  84 /*
  85  * Move inode type and inode format specific information from the
  86  * on-disk inode to the in-core inode.  For fifos, devs, and sockets
  87  * this means set if_rdev to the proper value.  For files, directories,
  88  * and symlinks this means to bring in the in-line data or extent
  89  * pointers.  For a file in B-tree format, only the root is immediately
  90  * brought in-core.  The rest will be in-lined in if_extents when it
  91  * is first referenced (see xfs_iread_extents()).
  92  */
  93 int
  94 xfs_iformat_fork(
  95         xfs_inode_t             *ip,
  96         xfs_dinode_t            *dip)
  97 {
  98         xfs_attr_shortform_t    *atp;
  99         int                     size;
 100         int                     error = 0;
 101         xfs_fsize_t             di_size;
 102
 103         if (unlikely(be32_to_cpu(dip->di_nextents) +
 104                      be16_to_cpu(dip->di_anextents) >
 105                      be64_to_cpu(dip->di_nblocks))) {
 106                 xfs_warn(ip->i_mount,
 107                         "corrupt dinode %Lu, extent total = %d, nblocks = %Lu.",
 108                         (unsigned long long)ip->i_ino,
 109                         (int)(be32_to_cpu(dip->di_nextents) +
 110                               be16_to_cpu(dip->di_anextents)),
 111                         (unsigned long long)
 112                                 be64_to_cpu(dip->di_nblocks));
 113                 XFS_CORRUPTION_ERROR("xfs_iformat(1)", XFS_ERRLEVEL_LOW,
 114                                      ip->i_mount, dip);
 115                 return XFS_ERROR(EFSCORRUPTED);
 116         }
 117
 118         if (unlikely(dip->di_forkoff > ip->i_mount->m_sb.sb_inodesize)) {
 119                 xfs_warn(ip->i_mount, "corrupt dinode %Lu, forkoff = 0x%x.",
 120                         (unsigned long long)ip->i_ino,
 121                         dip->di_forkoff);
 122                 XFS_CORRUPTION_ERROR("xfs_iformat(2)", XFS_ERRLEVEL_LOW,
 123                                      ip->i_mount, dip);
 124                 return XFS_ERROR(EFSCORRUPTED);
 125         }
 126
 127         if (unlikely((ip->i_d.di_flags & XFS_DIFLAG_REALTIME) &&
 128                      !ip->i_mount->m_rtdev_targp)) {
 129                 xfs_warn(ip->i_mount,
 130                         "corrupt dinode %Lu, has realtime flag set.",
 131                         ip->i_ino);
 132                 XFS_CORRUPTION_ERROR("xfs_iformat(realtime)",
 133                                      XFS_ERRLEVEL_LOW, ip->i_mount, dip);
 134                 return XFS_ERROR(EFSCORRUPTED);
 135         }
 136
 137         switch (ip->i_d.di_mode & S_IFMT) {
 138         case S_IFIFO:
 139         case S_IFCHR:
 140         case S_IFBLK:
 141         case S_IFSOCK:
 142                 if (unlikely(dip->di_format != XFS_DINODE_FMT_DEV)) {
 143                         XFS_CORRUPTION_ERROR("xfs_iformat(3)", XFS_ERRLEVEL_LOW,
 144                                               ip->i_mount, dip);
 145                         return XFS_ERROR(EFSCORRUPTED);
 146                 }
 147                 ip->i_d.di_size = 0;
 148                 ip->i_df.if_u2.if_rdev = xfs_dinode_get_rdev(dip);
 149                 break;
 150
 151         case S_IFREG:
 152         case S_IFLNK:
 153         case S_IFDIR:
 154                 switch (dip->di_format) {
 155                 case XFS_DINODE_FMT_LOCAL:
 156                         /*
 157                          * no local regular files yet
 158                          */
 159                         if (unlikely(S_ISREG(be16_to_cpu(dip->di_mode)))) {
 160                                 xfs_warn(ip->i_mount,
 161                         "corrupt inode %Lu (local format for regular file).",
 162                                         (unsigned long long) ip->i_ino);
 163                                 XFS_CORRUPTION_ERROR("xfs_iformat(4)",
 164                                                      XFS_ERRLEVEL_LOW,
 165                                                      ip->i_mount, dip);
 166                                 return XFS_ERROR(EFSCORRUPTED);
 167                         }
 168
 169                         di_size = be64_to_cpu(dip->di_size);
 170                         if (unlikely(di_size < 0 ||
 171                                      di_size > XFS_DFORK_DSIZE(dip, ip->i_mount))) {
 172                                 xfs_warn(ip->i_mount,
 173                         "corrupt inode %Lu (bad size %Ld for local inode).",
 174                                         (unsigned long long) ip->i_ino,
 175                                         (long long) di_size);
 176                                 XFS_CORRUPTION_ERROR("xfs_iformat(5)",
 177                                                      XFS_ERRLEVEL_LOW,
 178                                                      ip->i_mount, dip);
 179                                 return XFS_ERROR(EFSCORRUPTED);
 180                         }
 181
 182                         size = (int)di_size;
 183                         error = xfs_iformat_local(ip, dip, XFS_DATA_FORK, size);
 184                         break;
 185                 case XFS_DINODE_FMT_EXTENTS:
 186                         error = xfs_iformat_extents(ip, dip, XFS_DATA_FORK);
 187                         break;
 188                 case XFS_DINODE_FMT_BTREE:
 189                         error = xfs_iformat_btree(ip, dip, XFS_DATA_FORK);
 190                         break;
 191                 default:
 192                         XFS_ERROR_REPORT("xfs_iformat(6)", XFS_ERRLEVEL_LOW,
 193                                          ip->i_mount);
 194                         return XFS_ERROR(EFSCORRUPTED);
 195                 }
 196                 break;
 197
 198         default:
 199                 XFS_ERROR_REPORT("xfs_iformat(7)", XFS_ERRLEVEL_LOW, ip->i_mount);
 200                 return XFS_ERROR(EFSCORRUPTED);
 201         }
 202         if (error) {
 203                 return error;
 204         }
 205         if (!XFS_DFORK_Q(dip))
 206                 return 0;
 207
 208         ASSERT(ip->i_afp == NULL);
 209         ip->i_afp = kmem_zone_zalloc(xfs_ifork_zone, KM_SLEEP | KM_NOFS);
 210
 211         switch (dip->di_aformat) {
 212         case XFS_DINODE_FMT_LOCAL:
 213                 atp = (xfs_attr_shortform_t *)XFS_DFORK_APTR(dip);
 214                 size = be16_to_cpu(atp->hdr.totsize);
 215
 216                 if (unlikely(size < sizeof(struct xfs_attr_sf_hdr))) {
 217                         xfs_warn(ip->i_mount,
 218                                 "corrupt inode %Lu (bad attr fork size %Ld).",
 219                                 (unsigned long long) ip->i_ino,
 220                                 (long long) size);
 221                         XFS_CORRUPTION_ERROR("xfs_iformat(8)",
 222                                              XFS_ERRLEVEL_LOW,
 223                                              ip->i_mount, dip);
 224                         return XFS_ERROR(EFSCORRUPTED);
 225                 }
 226
 227                 error = xfs_iformat_local(ip, dip, XFS_ATTR_FORK, size);
 228                 break;
 229         case XFS_DINODE_FMT_EXTENTS:
 230                 error = xfs_iformat_extents(ip, dip, XFS_ATTR_FORK);
 231                 break;
 232         case XFS_DINODE_FMT_BTREE:
 233                 error = xfs_iformat_btree(ip, dip, XFS_ATTR_FORK);
 234                 break;
 235         default:
 236                 error = XFS_ERROR(EFSCORRUPTED);
 237                 break;
 238         }
 239         if (error) {
 240                 kmem_zone_free(xfs_ifork_zone, ip->i_afp);
 241                 ip->i_afp = NULL;
 242                 xfs_idestroy_fork(ip, XFS_DATA_FORK);
 243         }
 244         return error;
 245 }
 246
 247 /*
 248  * The file is in-lined in the on-disk inode.
 249  * If it fits into if_inline_data, then copy
 250  * it there, otherwise allocate a buffer for it
 251  * and copy the data there.  Either way, set
 252  * if_data to point at the data.
 253  * If we allocate a buffer for the data, make
 254  * sure that its size is a multiple of 4 and
 255  * record the real size in i_real_bytes.
 256  */
 257 STATIC int
 258 xfs_iformat_local(
 259         xfs_inode_t     *ip,
 260         xfs_dinode_t    *dip,
 261         int             whichfork,
 262         int             size)
 263 {
 264         xfs_ifork_t     *ifp;
 265         int             real_size;
 266
 267         /*
 268          * If the size is unreasonable, then something
 269          * is wrong and we just bail out rather than crash in
 270          * kmem_alloc() or memcpy() below.
 271          */
 272         if (unlikely(size > XFS_DFORK_SIZE(dip, ip->i_mount, whichfork))) {
 273                 xfs_warn(ip->i_mount,
 274         "corrupt inode %Lu (bad size %d for local fork, size = %d).",
 275                         (unsigned long long) ip->i_ino, size,
 276                         XFS_DFORK_SIZE(dip, ip->i_mount, whichfork));
 277                 XFS_CORRUPTION_ERROR("xfs_iformat_local", XFS_ERRLEVEL_LOW,
 278                                      ip->i_mount, dip);
 279                 return XFS_ERROR(EFSCORRUPTED);
 280         }
 281         ifp = XFS_IFORK_PTR(ip, whichfork);
 282         real_size = 0;
 283         if (size == 0)
 284                 ifp->if_u1.if_data = NULL;
 285         else if (size <= sizeof(ifp->if_u2.if_inline_data))
 286                 ifp->if_u1.if_data = ifp->if_u2.if_inline_data;
 287         else {
 288                 real_size = roundup(size, 4);
 289                 ifp->if_u1.if_data = kmem_alloc(real_size, KM_SLEEP | KM_NOFS);
 290         }
 291         ifp->if_bytes = size;
 292         ifp->if_real_bytes = real_size;
 293         if (size)
 294                 memcpy(ifp->if_u1.if_data, XFS_DFORK_PTR(dip, whichfork), size);
 295         ifp->if_flags &= ~XFS_IFEXTENTS;
 296         ifp->if_flags |= XFS_IFINLINE;
 297         return 0;
 298 }
 299
 300 /*
 301  * The file consists of a set of extents all
 302  * of which fit into the on-disk inode.
 303  * If there are few enough extents to fit into
 304  * the if_inline_ext, then copy them there.
 305  * Otherwise allocate a buffer for them and copy
 306  * them into it.  Either way, set if_extents
 307  * to point at the extents.
 308  */
 309 STATIC int
 310 xfs_iformat_extents(
 311         xfs_inode_t     *ip,
 312         xfs_dinode_t    *dip,
 313         int             whichfork)
 314 {
 315         xfs_bmbt_rec_t  *dp;
 316         xfs_ifork_t     *ifp;
 317         int             nex;
 318         int             size;
 319         int             i;
 320
 321         ifp = XFS_IFORK_PTR(ip, whichfork);
 322         nex = XFS_DFORK_NEXTENTS(dip, whichfork);
 323         size = nex * (uint)sizeof(xfs_bmbt_rec_t);
 324
 325         /*
 326          * If the number of extents is unreasonable, then something
 327          * is wrong and we just bail out rather than crash in
 328          * kmem_alloc() or memcpy() below.
 329          */
 330         if (unlikely(size < 0 || size > XFS_DFORK_SIZE(dip, ip->i_mount, whichfork))) {
 331                 xfs_warn(ip->i_mount, "corrupt inode %Lu ((a)extents = %d).",
 332                         (unsigned long long) ip->i_ino, nex);
 333                 XFS_CORRUPTION_ERROR("xfs_iformat_extents(1)", XFS_ERRLEVEL_LOW,
 334                                      ip->i_mount, dip);
 335                 return XFS_ERROR(EFSCORRUPTED);
 336         }
 337
 338         ifp->if_real_bytes = 0;
 339         if (nex == 0)
 340                 ifp->if_u1.if_extents = NULL;
 341         else if (nex <= XFS_INLINE_EXTS)
 342                 ifp->if_u1.if_extents = ifp->if_u2.if_inline_ext;
 343         else
 344                 xfs_iext_add(ifp, 0, nex);
 345
 346         ifp->if_bytes = size;
 347         if (size) {
 348                 dp = (xfs_bmbt_rec_t *) XFS_DFORK_PTR(dip, whichfork);
 349                 xfs_validate_extents(ifp, nex, XFS_EXTFMT_INODE(ip));
 350                 for (i = 0; i < nex; i++, dp++) {
 351                         xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, i);
 352                         ep->l0 = get_unaligned_be64(&dp->l0);
 353                         ep->l1 = get_unaligned_be64(&dp->l1);
 354                 }
 355                 XFS_BMAP_TRACE_EXLIST(ip, nex, whichfork);
 356                 if (whichfork != XFS_DATA_FORK ||
 357                         XFS_EXTFMT_INODE(ip) == XFS_EXTFMT_NOSTATE)
 358                                 if (unlikely(xfs_check_nostate_extents(
 359                                     ifp, 0, nex))) {
 360                                         XFS_ERROR_REPORT("xfs_iformat_extents(2)",
 361                                                          XFS_ERRLEVEL_LOW,
 362                                                          ip->i_mount);
 363                                         return XFS_ERROR(EFSCORRUPTED);
 364                                 }
 365         }
 366         ifp->if_flags |= XFS_IFEXTENTS;
 367         return 0;
 368 }
 369
 370 /*
 371  * The file has too many extents to fit into
 372  * the inode, so they are in B-tree format.
 373  * Allocate a buffer for the root of the B-tree
 374  * and copy the root into it.  The i_extents
 375  * field will remain NULL until all of the
 376  * extents are read in (when they are needed).
 377  */
 378 STATIC int
 379 xfs_iformat_btree(
 380         xfs_inode_t             *ip,
 381         xfs_dinode_t            *dip,
 382         int                     whichfork)
 383 {
 384         struct xfs_mount        *mp = ip->i_mount;
 385         xfs_bmdr_block_t        *dfp;
 386         xfs_ifork_t             *ifp;
 387         /* REFERENCED */
 388         int                     nrecs;
 389         int                     size;
 390
 391         ifp = XFS_IFORK_PTR(ip, whichfork);
 392         dfp = (xfs_bmdr_block_t *)XFS_DFORK_PTR(dip, whichfork);
 393         size = XFS_BMAP_BROOT_SPACE(mp, dfp);
 394         nrecs = be16_to_cpu(dfp->bb_numrecs);
 395
 396         /*
 397          * blow out if -- fork has less extents than can fit in
 398          * fork (fork shouldn't be a btree format), root btree
 399          * block has more records than can fit into the fork,
 400          * or the number of extents is greater than the number of
 401          * blocks.
 402          */
 403         if (unlikely(XFS_IFORK_NEXTENTS(ip, whichfork) <=
 404                                         XFS_IFORK_MAXEXT(ip, whichfork) ||
 405                      XFS_BMDR_SPACE_CALC(nrecs) >
 406                                         XFS_DFORK_SIZE(dip, mp, whichfork) ||
 407                      XFS_IFORK_NEXTENTS(ip, whichfork) > ip->i_d.di_nblocks)) {
 408                 xfs_warn(mp, "corrupt inode %Lu (btree).",
 409                                         (unsigned long long) ip->i_ino);
 410                 XFS_CORRUPTION_ERROR("xfs_iformat_btree", XFS_ERRLEVEL_LOW,
 411                                          mp, dip);
 412                 return XFS_ERROR(EFSCORRUPTED);
 413         }
 414
 415         ifp->if_broot_bytes = size;
 416         ifp->if_broot = kmem_alloc(size, KM_SLEEP | KM_NOFS);
 417         ASSERT(ifp->if_broot != NULL);
 418         /*
 419          * Copy and convert from the on-disk structure
 420          * to the in-memory structure.
 421          */
 422         xfs_bmdr_to_bmbt(ip, dfp, XFS_DFORK_SIZE(dip, ip->i_mount, whichfork),
 423                          ifp->if_broot, size);
 424         ifp->if_flags &= ~XFS_IFEXTENTS;
 425         ifp->if_flags |= XFS_IFBROOT;
 426
 427         return 0;
 428 }
 429
 430 /*
 431  * Read in extents from a btree-format inode.
 432  * Allocate and fill in if_extents.  Real work is done in xfs_bmap.c.
 433  */
 434 int
 435 xfs_iread_extents(
 436         xfs_trans_t     *tp,
 437         xfs_inode_t     *ip,
 438         int             whichfork)
 439 {
 440         int             error;
 441         xfs_ifork_t     *ifp;
 442         xfs_extnum_t    nextents;
 443
 444         if (unlikely(XFS_IFORK_FORMAT(ip, whichfork) != XFS_DINODE_FMT_BTREE)) {
 445                 XFS_ERROR_REPORT("xfs_iread_extents", XFS_ERRLEVEL_LOW,
 446                                  ip->i_mount);
 447                 return XFS_ERROR(EFSCORRUPTED);
 448         }
 449         nextents = XFS_IFORK_NEXTENTS(ip, whichfork);
 450         ifp = XFS_IFORK_PTR(ip, whichfork);
 451
 452         /*
 453          * We know that the size is valid (it's checked in iformat_btree)
 454          */
 455         ifp->if_bytes = ifp->if_real_bytes = 0;
 456         ifp->if_flags |= XFS_IFEXTENTS;
 457         xfs_iext_add(ifp, 0, nextents);
 458         error = xfs_bmap_read_extents(tp, ip, whichfork);
 459         if (error) {
 460                 xfs_iext_destroy(ifp);
 461                 ifp->if_flags &= ~XFS_IFEXTENTS;
 462                 return error;
 463         }
 464         xfs_validate_extents(ifp, nextents, XFS_EXTFMT_INODE(ip));
 465         return 0;
 466 }
 467 /*
 468  * Reallocate the space for if_broot based on the number of records
 469  * being added or deleted as indicated in rec_diff.  Move the records
 470  * and pointers in if_broot to fit the new size.  When shrinking this
 471  * will eliminate holes between the records and pointers created by
 472  * the caller.  When growing this will create holes to be filled in
 473  * by the caller.
 474  *
 475  * The caller must not request to add more records than would fit in
 476  * the on-disk inode root.  If the if_broot is currently NULL, then
 477  * if we are adding records, one will be allocated.  The caller must also
 478  * not request that the number of records go below zero, although
 479  * it can go to zero.
 480  *
 481  * ip -- the inode whose if_broot area is changing
 482  * ext_diff -- the change in the number of records, positive or negative,
 483  *       requested for the if_broot array.
 484  */
 485 void
 486 xfs_iroot_realloc(
 487         xfs_inode_t             *ip,
 488         int                     rec_diff,
 489         int                     whichfork)
 490 {
 491         struct xfs_mount        *mp = ip->i_mount;
 492         int                     cur_max;
 493         xfs_ifork_t             *ifp;
 494         struct xfs_btree_block  *new_broot;
 495         int                     new_max;
 496         size_t                  new_size;
 497         char                    *np;
 498         char                    *op;
 499
 500         /*
 501          * Handle the degenerate case quietly.
 502          */
 503         if (rec_diff == 0) {
 504                 return;
 505         }
 506
 507         ifp = XFS_IFORK_PTR(ip, whichfork);
 508         if (rec_diff > 0) {
 509                 /*
 510                  * If there wasn't any memory allocated before, just
 511                  * allocate it now and get out.
 512                  */
 513                 if (ifp->if_broot_bytes == 0) {
 514                         new_size = XFS_BMAP_BROOT_SPACE_CALC(mp, rec_diff);
 515                         ifp->if_broot = kmem_alloc(new_size, KM_SLEEP | KM_NOFS);
 516                         ifp->if_broot_bytes = (int)new_size;
 517                         return;
 518                 }
 519
 520                 /*
 521                  * If there is already an existing if_broot, then we need
 522                  * to realloc() it and shift the pointers to their new
 523                  * location.  The records don't change location because
 524                  * they are kept butted up against the btree block header.
 525                  */
 526                 cur_max = xfs_bmbt_maxrecs(mp, ifp->if_broot_bytes, 0);
 527                 new_max = cur_max + rec_diff;
 528                 new_size = XFS_BMAP_BROOT_SPACE_CALC(mp, new_max);
 529                 ifp->if_broot = kmem_realloc(ifp->if_broot, new_size,
 530                                 XFS_BMAP_BROOT_SPACE_CALC(mp, cur_max),
 531                                 KM_SLEEP | KM_NOFS);
 532                 op = (char *)XFS_BMAP_BROOT_PTR_ADDR(mp, ifp->if_broot, 1,
 533                                                      ifp->if_broot_bytes);
 534                 np = (char *)XFS_BMAP_BROOT_PTR_ADDR(mp, ifp->if_broot, 1,
 535                                                      (int)new_size);
 536                 ifp->if_broot_bytes = (int)new_size;
 537                 ASSERT(XFS_BMAP_BMDR_SPACE(ifp->if_broot) <=
 538                         XFS_IFORK_SIZE(ip, whichfork));
 539                 memmove(np, op, cur_max * (uint)sizeof(xfs_dfsbno_t));
 540                 return;
 541         }
 542
 543         /*
 544          * rec_diff is less than 0.  In this case, we are shrinking the
 545          * if_broot buffer.  It must already exist.  If we go to zero
 546          * records, just get rid of the root and clear the status bit.
 547          */
 548         ASSERT((ifp->if_broot != NULL) && (ifp->if_broot_bytes > 0));
 549         cur_max = xfs_bmbt_maxrecs(mp, ifp->if_broot_bytes, 0);
 550         new_max = cur_max + rec_diff;
 551         ASSERT(new_max >= 0);
 552         if (new_max > 0)
 553                 new_size = XFS_BMAP_BROOT_SPACE_CALC(mp, new_max);
 554         else
 555                 new_size = 0;
 556         if (new_size > 0) {
 557                 new_broot = kmem_alloc(new_size, KM_SLEEP | KM_NOFS);
 558                 /*
 559                  * First copy over the btree block header.
 560                  */
 561                 memcpy(new_broot, ifp->if_broot,
 562                         XFS_BMBT_BLOCK_LEN(ip->i_mount));
 563         } else {
 564                 new_broot = NULL;
 565                 ifp->if_flags &= ~XFS_IFBROOT;
 566         }
 567
 568         /*
 569          * Only copy the records and pointers if there are any.
 570          */
 571         if (new_max > 0) {
 572                 /*
 573                  * First copy the records.
 574                  */
 575                 op = (char *)XFS_BMBT_REC_ADDR(mp, ifp->if_broot, 1);
 576                 np = (char *)XFS_BMBT_REC_ADDR(mp, new_broot, 1);
 577                 memcpy(np, op, new_max * (uint)sizeof(xfs_bmbt_rec_t));
 578
 579                 /*
 580                  * Then copy the pointers.
 581                  */
 582                 op = (char *)XFS_BMAP_BROOT_PTR_ADDR(mp, ifp->if_broot, 1,
 583                                                      ifp->if_broot_bytes);
 584                 np = (char *)XFS_BMAP_BROOT_PTR_ADDR(mp, new_broot, 1,
 585                                                      (int)new_size);
 586                 memcpy(np, op, new_max * (uint)sizeof(xfs_dfsbno_t));
 587         }
 588         kmem_free(ifp->if_broot);
 589         ifp->if_broot = new_broot;
 590         ifp->if_broot_bytes = (int)new_size;
 591         if (ifp->if_broot)
 592                 ASSERT(XFS_BMAP_BMDR_SPACE(ifp->if_broot) <=
 593                         XFS_IFORK_SIZE(ip, whichfork));
 594         return;
 595 }
 596
 597
 598 /*
 599  * This is called when the amount of space needed for if_data
 600  * is increased or decreased.  The change in size is indicated by
 601  * the number of bytes that need to be added or deleted in the
 602  * byte_diff parameter.
 603  *
 604  * If the amount of space needed has decreased below the size of the
 605  * inline buffer, then switch to using the inline buffer.  Otherwise,
 606  * use kmem_realloc() or kmem_alloc() to adjust the size of the buffer
 607  * to what is needed.
 608  *
 609  * ip -- the inode whose if_data area is changing
 610  * byte_diff -- the change in the number of bytes, positive or negative,
 611  *       requested for the if_data array.
 612  */
 613 void
 614 xfs_idata_realloc(
 615         xfs_inode_t     *ip,
 616         int             byte_diff,
 617         int             whichfork)
 618 {
 619         xfs_ifork_t     *ifp;
 620         int             new_size;
 621         int             real_size;
 622
 623         if (byte_diff == 0) {
 624                 return;
 625         }
 626
 627         ifp = XFS_IFORK_PTR(ip, whichfork);
 628         new_size = (int)ifp->if_bytes + byte_diff;
 629         ASSERT(new_size >= 0);
 630
 631         if (new_size == 0) {
 632                 if (ifp->if_u1.if_data != ifp->if_u2.if_inline_data) {
 633                         kmem_free(ifp->if_u1.if_data);
 634                 }
 635                 ifp->if_u1.if_data = NULL;
 636                 real_size = 0;
 637         } else if (new_size <= sizeof(ifp->if_u2.if_inline_data)) {
 638                 /*
 639                  * If the valid extents/data can fit in if_inline_ext/data,
 640                  * copy them from the malloc'd vector and free it.
 641                  */
 642                 if (ifp->if_u1.if_data == NULL) {
 643                         ifp->if_u1.if_data = ifp->if_u2.if_inline_data;
 644                 } else if (ifp->if_u1.if_data != ifp->if_u2.if_inline_data) {
 645                         ASSERT(ifp->if_real_bytes != 0);
 646                         memcpy(ifp->if_u2.if_inline_data, ifp->if_u1.if_data,
 647                               new_size);
 648                         kmem_free(ifp->if_u1.if_data);
 649                         ifp->if_u1.if_data = ifp->if_u2.if_inline_data;
 650                 }
 651                 real_size = 0;
 652         } else {
 653                 /*
 654                  * Stuck with malloc/realloc.
 655                  * For inline data, the underlying buffer must be
 656                  * a multiple of 4 bytes in size so that it can be
 657                  * logged and stay on word boundaries.  We enforce
 658                  * that here.
 659                  */
 660                 real_size = roundup(new_size, 4);
 661                 if (ifp->if_u1.if_data == NULL) {
 662                         ASSERT(ifp->if_real_bytes == 0);
 663                         ifp->if_u1.if_data = kmem_alloc(real_size,
 664                                                         KM_SLEEP | KM_NOFS);
 665                 } else if (ifp->if_u1.if_data != ifp->if_u2.if_inline_data) {
 666                         /*
 667                          * Only do the realloc if the underlying size
 668                          * is really changing.
 669                          */
 670                         if (ifp->if_real_bytes != real_size) {
 671                                 ifp->if_u1.if_data =
 672                                         kmem_realloc(ifp->if_u1.if_data,
 673                                                         real_size,
 674                                                         ifp->if_real_bytes,
 675                                                         KM_SLEEP | KM_NOFS);
 676                         }
 677                 } else {
 678                         ASSERT(ifp->if_real_bytes == 0);
 679                         ifp->if_u1.if_data = kmem_alloc(real_size,
 680                                                         KM_SLEEP | KM_NOFS);
 681                         memcpy(ifp->if_u1.if_data, ifp->if_u2.if_inline_data,
 682                                 ifp->if_bytes);
 683                 }
 684         }
 685         ifp->if_real_bytes = real_size;
 686         ifp->if_bytes = new_size;
 687         ASSERT(ifp->if_bytes <= XFS_IFORK_SIZE(ip, whichfork));
 688 }
 689
 690 void
 691 xfs_idestroy_fork(
 692         xfs_inode_t     *ip,
 693         int             whichfork)
 694 {
 695         xfs_ifork_t     *ifp;
 696
 697         ifp = XFS_IFORK_PTR(ip, whichfork);
 698         if (ifp->if_broot != NULL) {
 699                 kmem_free(ifp->if_broot);
 700                 ifp->if_broot = NULL;
 701         }
 702
 703         /*
 704          * If the format is local, then we can't have an extents
 705          * array so just look for an inline data array.  If we're
 706          * not local then we may or may not have an extents list,
 707          * so check and free it up if we do.
 708          */
 709         if (XFS_IFORK_FORMAT(ip, whichfork) == XFS_DINODE_FMT_LOCAL) {
 710                 if ((ifp->if_u1.if_data != ifp->if_u2.if_inline_data) &&
 711                     (ifp->if_u1.if_data != NULL)) {
 712                         ASSERT(ifp->if_real_bytes != 0);
 713                         kmem_free(ifp->if_u1.if_data);
 714                         ifp->if_u1.if_data = NULL;
 715                         ifp->if_real_bytes = 0;
 716                 }
 717         } else if ((ifp->if_flags & XFS_IFEXTENTS) &&
 718                    ((ifp->if_flags & XFS_IFEXTIREC) ||
 719                     ((ifp->if_u1.if_extents != NULL) &&
 720                      (ifp->if_u1.if_extents != ifp->if_u2.if_inline_ext)))) {
 721                 ASSERT(ifp->if_real_bytes != 0);
 722                 xfs_iext_destroy(ifp);
 723         }
 724         ASSERT(ifp->if_u1.if_extents == NULL ||
 725                ifp->if_u1.if_extents == ifp->if_u2.if_inline_ext);
 726         ASSERT(ifp->if_real_bytes == 0);
 727         if (whichfork == XFS_ATTR_FORK) {
 728                 kmem_zone_free(xfs_ifork_zone, ip->i_afp);
 729                 ip->i_afp = NULL;
 730         }
 731 }
 732
 733 /*
 734  * xfs_iextents_copy()
 735  *
 736  * This is called to copy the REAL extents (as opposed to the delayed
 737  * allocation extents) from the inode into the given buffer.  It
 738  * returns the number of bytes copied into the buffer.
 739  *
 740  * If there are no delayed allocation extents, then we can just
 741  * memcpy() the extents into the buffer.  Otherwise, we need to
 742  * examine each extent in turn and skip those which are delayed.
 743  */
 744 int
 745 xfs_iextents_copy(
 746         xfs_inode_t             *ip,
 747         xfs_bmbt_rec_t          *dp,
 748         int                     whichfork)
 749 {
 750         int                     copied;
 751         int                     i;
 752         xfs_ifork_t             *ifp;
 753         int                     nrecs;
 754         xfs_fsblock_t           start_block;
 755
 756         ifp = XFS_IFORK_PTR(ip, whichfork);
 757         ASSERT(xfs_isilocked(ip, XFS_ILOCK_EXCL|XFS_ILOCK_SHARED));
 758         ASSERT(ifp->if_bytes > 0);
 759
 760         nrecs = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
 761         XFS_BMAP_TRACE_EXLIST(ip, nrecs, whichfork);
 762         ASSERT(nrecs > 0);
 763
 764         /*
 765          * There are some delayed allocation extents in the
 766          * inode, so copy the extents one at a time and skip
 767          * the delayed ones.  There must be at least one
 768          * non-delayed extent.
 769          */
 770         copied = 0;
 771         for (i = 0; i < nrecs; i++) {
 772                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, i);
 773                 start_block = xfs_bmbt_get_startblock(ep);
 774                 if (isnullstartblock(start_block)) {
 775                         /*
 776                          * It's a delayed allocation extent, so skip it.
 777                          */
 778                         continue;
 779                 }
 780
 781                 /* Translate to on disk format */
 782                 put_unaligned_be64(ep->l0, &dp->l0);
 783                 put_unaligned_be64(ep->l1, &dp->l1);
 784                 dp++;
 785                 copied++;
 786         }
 787         ASSERT(copied != 0);
 788         xfs_validate_extents(ifp, copied, XFS_EXTFMT_INODE(ip));
 789
 790         return (copied * (uint)sizeof(xfs_bmbt_rec_t));
 791 }
 792
 793 /*
 794  * Each of the following cases stores data into the same region
 795  * of the on-disk inode, so only one of them can be valid at
 796  * any given time. While it is possible to have conflicting formats
 797  * and log flags, e.g. having XFS_ILOG_?DATA set when the fork is
 798  * in EXTENTS format, this can only happen when the fork has
 799  * changed formats after being modified but before being flushed.
 800  * In these cases, the format always takes precedence, because the
 801  * format indicates the current state of the fork.
 802  */
 803 void
 804 xfs_iflush_fork(
 805         xfs_inode_t             *ip,
 806         xfs_dinode_t            *dip,
 807         xfs_inode_log_item_t    *iip,
 808         int                     whichfork,
 809         xfs_buf_t               *bp)
 810 {
 811         char                    *cp;
 812         xfs_ifork_t             *ifp;
 813         xfs_mount_t             *mp;
 814         static const short      brootflag[2] =
 815                 { XFS_ILOG_DBROOT, XFS_ILOG_ABROOT };
 816         static const short      dataflag[2] =
 817                 { XFS_ILOG_DDATA, XFS_ILOG_ADATA };
 818         static const short      extflag[2] =
 819                 { XFS_ILOG_DEXT, XFS_ILOG_AEXT };
 820
 821         if (!iip)
 822                 return;
 823         ifp = XFS_IFORK_PTR(ip, whichfork);
 824         /*
 825          * This can happen if we gave up in iformat in an error path,
 826          * for the attribute fork.
 827          */
 828         if (!ifp) {
 829                 ASSERT(whichfork == XFS_ATTR_FORK);
 830                 return;
 831         }
 832         cp = XFS_DFORK_PTR(dip, whichfork);
 833         mp = ip->i_mount;
 834         switch (XFS_IFORK_FORMAT(ip, whichfork)) {
 835         case XFS_DINODE_FMT_LOCAL:
 836                 if ((iip->ili_fields & dataflag[whichfork]) &&
 837                     (ifp->if_bytes > 0)) {
 838                         ASSERT(ifp->if_u1.if_data != NULL);
 839                         ASSERT(ifp->if_bytes <= XFS_IFORK_SIZE(ip, whichfork));
 840                         memcpy(cp, ifp->if_u1.if_data, ifp->if_bytes);
 841                 }
 842                 break;
 843
 844         case XFS_DINODE_FMT_EXTENTS:
 845                 ASSERT((ifp->if_flags & XFS_IFEXTENTS) ||
 846                        !(iip->ili_fields & extflag[whichfork]));
 847                 if ((iip->ili_fields & extflag[whichfork]) &&
 848                     (ifp->if_bytes > 0)) {
 849                         ASSERT(xfs_iext_get_ext(ifp, 0));
 850                         ASSERT(XFS_IFORK_NEXTENTS(ip, whichfork) > 0);
 851                         (void)xfs_iextents_copy(ip, (xfs_bmbt_rec_t *)cp,
 852                                 whichfork);
 853                 }
 854                 break;
 855
 856         case XFS_DINODE_FMT_BTREE:
 857                 if ((iip->ili_fields & brootflag[whichfork]) &&
 858                     (ifp->if_broot_bytes > 0)) {
 859                         ASSERT(ifp->if_broot != NULL);
 860                         ASSERT(XFS_BMAP_BMDR_SPACE(ifp->if_broot) <=
 861                                 XFS_IFORK_SIZE(ip, whichfork));
 862                         xfs_bmbt_to_bmdr(mp, ifp->if_broot, ifp->if_broot_bytes,
 863                                 (xfs_bmdr_block_t *)cp,
 864                                 XFS_DFORK_SIZE(dip, mp, whichfork));
 865                 }
 866                 break;
 867
 868         case XFS_DINODE_FMT_DEV:
 869                 if (iip->ili_fields & XFS_ILOG_DEV) {
 870                         ASSERT(whichfork == XFS_DATA_FORK);
 871                         xfs_dinode_put_rdev(dip, ip->i_df.if_u2.if_rdev);
 872                 }
 873                 break;
 874
 875         case XFS_DINODE_FMT_UUID:
 876                 if (iip->ili_fields & XFS_ILOG_UUID) {
 877                         ASSERT(whichfork == XFS_DATA_FORK);
 878                         memcpy(XFS_DFORK_DPTR(dip),
 879                                &ip->i_df.if_u2.if_uuid,
 880                                sizeof(uuid_t));
 881                 }
 882                 break;
 883
 884         default:
 885                 ASSERT(0);
 886                 break;
 887         }
 888 }
 889
 890 /*
 891  * Return a pointer to the extent record at file index idx.
 892  */
 893 xfs_bmbt_rec_host_t *
 894 xfs_iext_get_ext(
 895         xfs_ifork_t     *ifp,           /* inode fork pointer */
 896         xfs_extnum_t    idx)            /* index of target extent */
 897 {
 898         ASSERT(idx >= 0);
 899         ASSERT(idx < ifp->if_bytes / sizeof(xfs_bmbt_rec_t));
 900
 901         if ((ifp->if_flags & XFS_IFEXTIREC) && (idx == 0)) {
 902                 return ifp->if_u1.if_ext_irec->er_extbuf;
 903         } else if (ifp->if_flags & XFS_IFEXTIREC) {
 904                 xfs_ext_irec_t  *erp;           /* irec pointer */
 905                 int             erp_idx = 0;    /* irec index */
 906                 xfs_extnum_t    page_idx = idx; /* ext index in target list */
 907
 908                 erp = xfs_iext_idx_to_irec(ifp, &page_idx, &erp_idx, 0);
 909                 return &erp->er_extbuf[page_idx];
 910         } else if (ifp->if_bytes) {
 911                 return &ifp->if_u1.if_extents[idx];
 912         } else {
 913                 return NULL;
 914         }
 915 }
 916
 917 /*
 918  * Insert new item(s) into the extent records for incore inode
 919  * fork 'ifp'.  'count' new items are inserted at index 'idx'.
 920  */
 921 void
 922 xfs_iext_insert(
 923         xfs_inode_t     *ip,            /* incore inode pointer */
 924         xfs_extnum_t    idx,            /* starting index of new items */
 925         xfs_extnum_t    count,          /* number of inserted items */
 926         xfs_bmbt_irec_t *new,           /* items to insert */
 927         int             state)          /* type of extent conversion */
 928 {
 929         xfs_ifork_t     *ifp = (state & BMAP_ATTRFORK) ? ip->i_afp : &ip->i_df;
 930         xfs_extnum_t    i;              /* extent record index */
 931
 932         trace_xfs_iext_insert(ip, idx, new, state, _RET_IP_);
 933
 934         ASSERT(ifp->if_flags & XFS_IFEXTENTS);
 935         xfs_iext_add(ifp, idx, count);
 936         for (i = idx; i < idx + count; i++, new++)
 937                 xfs_bmbt_set_all(xfs_iext_get_ext(ifp, i), new);
 938 }
 939
 940 /*
 941  * This is called when the amount of space required for incore file
 942  * extents needs to be increased. The ext_diff parameter stores the
 943  * number of new extents being added and the idx parameter contains
 944  * the extent index where the new extents will be added. If the new
 945  * extents are being appended, then we just need to (re)allocate and
 946  * initialize the space. Otherwise, if the new extents are being
 947  * inserted into the middle of the existing entries, a bit more work
 948  * is required to make room for the new extents to be inserted. The
 949  * caller is responsible for filling in the new extent entries upon
 950  * return.
 951  */
 952 void
 953 xfs_iext_add(
 954         xfs_ifork_t     *ifp,           /* inode fork pointer */
 955         xfs_extnum_t    idx,            /* index to begin adding exts */
 956         int             ext_diff)       /* number of extents to add */
 957 {
 958         int             byte_diff;      /* new bytes being added */
 959         int             new_size;       /* size of extents after adding */
 960         xfs_extnum_t    nextents;       /* number of extents in file */
 961
 962         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
 963         ASSERT((idx >= 0) && (idx <= nextents));
 964         byte_diff = ext_diff * sizeof(xfs_bmbt_rec_t);
 965         new_size = ifp->if_bytes + byte_diff;
 966         /*
 967          * If the new number of extents (nextents + ext_diff)
 968          * fits inside the inode, then continue to use the inline
 969          * extent buffer.
 970          */
 971         if (nextents + ext_diff <= XFS_INLINE_EXTS) {
 972                 if (idx < nextents) {
 973                         memmove(&ifp->if_u2.if_inline_ext[idx + ext_diff],
 974                                 &ifp->if_u2.if_inline_ext[idx],
 975                                 (nextents - idx) * sizeof(xfs_bmbt_rec_t));
 976                         memset(&ifp->if_u2.if_inline_ext[idx], 0, byte_diff);
 977                 }
 978                 ifp->if_u1.if_extents = ifp->if_u2.if_inline_ext;
 979                 ifp->if_real_bytes = 0;
 980         }
 981         /*
 982          * Otherwise use a linear (direct) extent list.
 983          * If the extents are currently inside the inode,
 984          * xfs_iext_realloc_direct will switch us from
 985          * inline to direct extent allocation mode.
 986          */
 987         else if (nextents + ext_diff <= XFS_LINEAR_EXTS) {
 988                 xfs_iext_realloc_direct(ifp, new_size);
 989                 if (idx < nextents) {
 990                         memmove(&ifp->if_u1.if_extents[idx + ext_diff],
 991                                 &ifp->if_u1.if_extents[idx],
 992                                 (nextents - idx) * sizeof(xfs_bmbt_rec_t));
 993                         memset(&ifp->if_u1.if_extents[idx], 0, byte_diff);
 994                 }
 995         }
 996         /* Indirection array */
 997         else {
 998                 xfs_ext_irec_t  *erp;
 999                 int             erp_idx = 0;
1000                 int             page_idx = idx;
1001
1002                 ASSERT(nextents + ext_diff > XFS_LINEAR_EXTS);
1003                 if (ifp->if_flags & XFS_IFEXTIREC) {
1004                         erp = xfs_iext_idx_to_irec(ifp, &page_idx, &erp_idx, 1);
1005                 } else {
1006                         xfs_iext_irec_init(ifp);
1007                         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1008                         erp = ifp->if_u1.if_ext_irec;
1009                 }
1010                 /* Extents fit in target extent page */
1011                 if (erp && erp->er_extcount + ext_diff <= XFS_LINEAR_EXTS) {
1012                         if (page_idx < erp->er_extcount) {
1013                                 memmove(&erp->er_extbuf[page_idx + ext_diff],
1014                                         &erp->er_extbuf[page_idx],
1015                                         (erp->er_extcount - page_idx) *
1016                                         sizeof(xfs_bmbt_rec_t));
1017                                 memset(&erp->er_extbuf[page_idx], 0, byte_diff);
1018                         }
1019                         erp->er_extcount += ext_diff;
1020                         xfs_iext_irec_update_extoffs(ifp, erp_idx + 1, ext_diff);
1021                 }
1022                 /* Insert a new extent page */
1023                 else if (erp) {
1024                         xfs_iext_add_indirect_multi(ifp,
1025                                 erp_idx, page_idx, ext_diff);
1026                 }
1027                 /*
1028                  * If extent(s) are being appended to the last page in
1029                  * the indirection array and the new extent(s) don't fit
1030                  * in the page, then erp is NULL and erp_idx is set to
1031                  * the next index needed in the indirection array.
1032                  */
1033                 else {
1034                         int     count = ext_diff;
1035
1036                         while (count) {
1037                                 erp = xfs_iext_irec_new(ifp, erp_idx);
1038                                 erp->er_extcount = count;
1039                                 count -= MIN(count, (int)XFS_LINEAR_EXTS);
1040                                 if (count) {
1041                                         erp_idx++;
1042                                 }
1043                         }
1044                 }
1045         }
1046         ifp->if_bytes = new_size;
1047 }
1048
1049 /*
1050  * This is called when incore extents are being added to the indirection
1051  * array and the new extents do not fit in the target extent list. The
1052  * erp_idx parameter contains the irec index for the target extent list
1053  * in the indirection array, and the idx parameter contains the extent
1054  * index within the list. The number of extents being added is stored
1055  * in the count parameter.
1056  *
1057  *    |-------|   |-------|
1058  *    |       |   |       |    idx - number of extents before idx
1059  *    |  idx  |   | count |
1060  *    |       |   |       |    count - number of extents being inserted at idx
1061  *    |-------|   |-------|
1062  *    | count |   | nex2  |    nex2 - number of extents after idx + count
1063  *    |-------|   |-------|
1064  */
1065 void
1066 xfs_iext_add_indirect_multi(
1067         xfs_ifork_t     *ifp,                   /* inode fork pointer */
1068         int             erp_idx,                /* target extent irec index */
1069         xfs_extnum_t    idx,                    /* index within target list */
1070         int             count)                  /* new extents being added */
1071 {
1072         int             byte_diff;              /* new bytes being added */
1073         xfs_ext_irec_t  *erp;                   /* pointer to irec entry */
1074         xfs_extnum_t    ext_diff;               /* number of extents to add */
1075         xfs_extnum_t    ext_cnt;                /* new extents still needed */
1076         xfs_extnum_t    nex2;                   /* extents after idx + count */
1077         xfs_bmbt_rec_t  *nex2_ep = NULL;        /* temp list for nex2 extents */
1078         int             nlists;                 /* number of irec's (lists) */
1079
1080         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1081         erp = &ifp->if_u1.if_ext_irec[erp_idx];
1082         nex2 = erp->er_extcount - idx;
1083         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1084
1085         /*
1086          * Save second part of target extent list
1087          * (all extents past */
1088         if (nex2) {
1089                 byte_diff = nex2 * sizeof(xfs_bmbt_rec_t);
1090                 nex2_ep = (xfs_bmbt_rec_t *) kmem_alloc(byte_diff, KM_NOFS);
1091                 memmove(nex2_ep, &erp->er_extbuf[idx], byte_diff);
1092                 erp->er_extcount -= nex2;
1093                 xfs_iext_irec_update_extoffs(ifp, erp_idx + 1, -nex2);
1094                 memset(&erp->er_extbuf[idx], 0, byte_diff);
1095         }
1096
1097         /*
1098          * Add the new extents to the end of the target
1099          * list, then allocate new irec record(s) and
1100          * extent buffer(s) as needed to store the rest
1101          * of the new extents.
1102          */
1103         ext_cnt = count;
1104         ext_diff = MIN(ext_cnt, (int)XFS_LINEAR_EXTS - erp->er_extcount);
1105         if (ext_diff) {
1106                 erp->er_extcount += ext_diff;
1107                 xfs_iext_irec_update_extoffs(ifp, erp_idx + 1, ext_diff);
1108                 ext_cnt -= ext_diff;
1109         }
1110         while (ext_cnt) {
1111                 erp_idx++;
1112                 erp = xfs_iext_irec_new(ifp, erp_idx);
1113                 ext_diff = MIN(ext_cnt, (int)XFS_LINEAR_EXTS);
1114                 erp->er_extcount = ext_diff;
1115                 xfs_iext_irec_update_extoffs(ifp, erp_idx + 1, ext_diff);
1116                 ext_cnt -= ext_diff;
1117         }
1118
1119         /* Add nex2 extents back to indirection array */
1120         if (nex2) {
1121                 xfs_extnum_t    ext_avail;
1122                 int             i;
1123
1124                 byte_diff = nex2 * sizeof(xfs_bmbt_rec_t);
1125                 ext_avail = XFS_LINEAR_EXTS - erp->er_extcount;
1126                 i = 0;
1127                 /*
1128                  * If nex2 extents fit in the current page, append
1129                  * nex2_ep after the new extents.
1130                  */
1131                 if (nex2 <= ext_avail) {
1132                         i = erp->er_extcount;
1133                 }
1134                 /*
1135                  * Otherwise, check if space is available in the
1136                  * next page.
1137                  */
1138                 else if ((erp_idx < nlists - 1) &&
1139                          (nex2 <= (ext_avail = XFS_LINEAR_EXTS -
1140                           ifp->if_u1.if_ext_irec[erp_idx+1].er_extcount))) {
1141                         erp_idx++;
1142                         erp++;
1143                         /* Create a hole for nex2 extents */
1144                         memmove(&erp->er_extbuf[nex2], erp->er_extbuf,
1145                                 erp->er_extcount * sizeof(xfs_bmbt_rec_t));
1146                 }
1147                 /*
1148                  * Final choice, create a new extent page for
1149                  * nex2 extents.
1150                  */
1151                 else {
1152                         erp_idx++;
1153                         erp = xfs_iext_irec_new(ifp, erp_idx);
1154                 }
1155                 memmove(&erp->er_extbuf[i], nex2_ep, byte_diff);
1156                 kmem_free(nex2_ep);
1157                 erp->er_extcount += nex2;
1158                 xfs_iext_irec_update_extoffs(ifp, erp_idx + 1, nex2);
1159         }
1160 }
1161
1162 /*
1163  * This is called when the amount of space required for incore file
1164  * extents needs to be decreased. The ext_diff parameter stores the
1165  * number of extents to be removed and the idx parameter contains
1166  * the extent index where the extents will be removed from.
1167  *
1168  * If the amount of space needed has decreased below the linear
1169  * limit, XFS_IEXT_BUFSZ, then switch to using the contiguous
1170  * extent array.  Otherwise, use kmem_realloc() to adjust the
1171  * size to what is needed.
1172  */
1173 void
1174 xfs_iext_remove(
1175         xfs_inode_t     *ip,            /* incore inode pointer */
1176         xfs_extnum_t    idx,            /* index to begin removing exts */
1177         int             ext_diff,       /* number of extents to remove */
1178         int             state)          /* type of extent conversion */
1179 {
1180         xfs_ifork_t     *ifp = (state & BMAP_ATTRFORK) ? ip->i_afp : &ip->i_df;
1181         xfs_extnum_t    nextents;       /* number of extents in file */
1182         int             new_size;       /* size of extents after removal */
1183
1184         trace_xfs_iext_remove(ip, idx, state, _RET_IP_);
1185
1186         ASSERT(ext_diff > 0);
1187         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1188         new_size = (nextents - ext_diff) * sizeof(xfs_bmbt_rec_t);
1189
1190         if (new_size == 0) {
1191                 xfs_iext_destroy(ifp);
1192         } else if (ifp->if_flags & XFS_IFEXTIREC) {
1193                 xfs_iext_remove_indirect(ifp, idx, ext_diff);
1194         } else if (ifp->if_real_bytes) {
1195                 xfs_iext_remove_direct(ifp, idx, ext_diff);
1196         } else {
1197                 xfs_iext_remove_inline(ifp, idx, ext_diff);
1198         }
1199         ifp->if_bytes = new_size;
1200 }
1201
1202 /*
1203  * This removes ext_diff extents from the inline buffer, beginning
1204  * at extent index idx.
1205  */
1206 void
1207 xfs_iext_remove_inline(
1208         xfs_ifork_t     *ifp,           /* inode fork pointer */
1209         xfs_extnum_t    idx,            /* index to begin removing exts */
1210         int             ext_diff)       /* number of extents to remove */
1211 {
1212         int             nextents;       /* number of extents in file */
1213
1214         ASSERT(!(ifp->if_flags & XFS_IFEXTIREC));
1215         ASSERT(idx < XFS_INLINE_EXTS);
1216         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1217         ASSERT(((nextents - ext_diff) > 0) &&
1218                 (nextents - ext_diff) < XFS_INLINE_EXTS);
1219
1220         if (idx + ext_diff < nextents) {
1221                 memmove(&ifp->if_u2.if_inline_ext[idx],
1222                         &ifp->if_u2.if_inline_ext[idx + ext_diff],
1223                         (nextents - (idx + ext_diff)) *
1224                          sizeof(xfs_bmbt_rec_t));
1225                 memset(&ifp->if_u2.if_inline_ext[nextents - ext_diff],
1226                         0, ext_diff * sizeof(xfs_bmbt_rec_t));
1227         } else {
1228                 memset(&ifp->if_u2.if_inline_ext[idx], 0,
1229                         ext_diff * sizeof(xfs_bmbt_rec_t));
1230         }
1231 }
1232
1233 /*
1234  * This removes ext_diff extents from a linear (direct) extent list,
1235  * beginning at extent index idx. If the extents are being removed
1236  * from the end of the list (ie. truncate) then we just need to re-
1237  * allocate the list to remove the extra space. Otherwise, if the
1238  * extents are being removed from the middle of the existing extent
1239  * entries, then we first need to move the extent records beginning
1240  * at idx + ext_diff up in the list to overwrite the records being
1241  * removed, then remove the extra space via kmem_realloc.
1242  */
1243 void
1244 xfs_iext_remove_direct(
1245         xfs_ifork_t     *ifp,           /* inode fork pointer */
1246         xfs_extnum_t    idx,            /* index to begin removing exts */
1247         int             ext_diff)       /* number of extents to remove */
1248 {
1249         xfs_extnum_t    nextents;       /* number of extents in file */
1250         int             new_size;       /* size of extents after removal */
1251
1252         ASSERT(!(ifp->if_flags & XFS_IFEXTIREC));
1253         new_size = ifp->if_bytes -
1254                 (ext_diff * sizeof(xfs_bmbt_rec_t));
1255         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1256
1257         if (new_size == 0) {
1258                 xfs_iext_destroy(ifp);
1259                 return;
1260         }
1261         /* Move extents up in the list (if needed) */
1262         if (idx + ext_diff < nextents) {
1263                 memmove(&ifp->if_u1.if_extents[idx],
1264                         &ifp->if_u1.if_extents[idx + ext_diff],
1265                         (nextents - (idx + ext_diff)) *
1266                          sizeof(xfs_bmbt_rec_t));
1267         }
1268         memset(&ifp->if_u1.if_extents[nextents - ext_diff],
1269                 0, ext_diff * sizeof(xfs_bmbt_rec_t));
1270         /*
1271          * Reallocate the direct extent list. If the extents
1272          * will fit inside the inode then xfs_iext_realloc_direct
1273          * will switch from direct to inline extent allocation
1274          * mode for us.
1275          */
1276         xfs_iext_realloc_direct(ifp, new_size);
1277         ifp->if_bytes = new_size;
1278 }
1279
1280 /*
1281  * This is called when incore extents are being removed from the
1282  * indirection array and the extents being removed span multiple extent
1283  * buffers. The idx parameter contains the file extent index where we
1284  * want to begin removing extents, and the count parameter contains
1285  * how many extents need to be removed.
1286  *
1287  *    |-------|   |-------|
1288  *    | nex1  |   |       |    nex1 - number of extents before idx
1289  *    |-------|   | count |
1290  *    |       |   |       |    count - number of extents being removed at idx
1291  *    | count |   |-------|
1292  *    |       |   | nex2  |    nex2 - number of extents after idx + count
1293  *    |-------|   |-------|
1294  */
1295 void
1296 xfs_iext_remove_indirect(
1297         xfs_ifork_t     *ifp,           /* inode fork pointer */
1298         xfs_extnum_t    idx,            /* index to begin removing extents */
1299         int             count)          /* number of extents to remove */
1300 {
1301         xfs_ext_irec_t  *erp;           /* indirection array pointer */
1302         int             erp_idx = 0;    /* indirection array index */
1303         xfs_extnum_t    ext_cnt;        /* extents left to remove */
1304         xfs_extnum_t    ext_diff;       /* extents to remove in current list */
1305         xfs_extnum_t    nex1;           /* number of extents before idx */
1306         xfs_extnum_t    nex2;           /* extents after idx + count */
1307         int             page_idx = idx; /* index in target extent list */
1308
1309         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1310         erp = xfs_iext_idx_to_irec(ifp,  &page_idx, &erp_idx, 0);
1311         ASSERT(erp != NULL);
1312         nex1 = page_idx;
1313         ext_cnt = count;
1314         while (ext_cnt) {
1315                 nex2 = MAX((erp->er_extcount - (nex1 + ext_cnt)), 0);
1316                 ext_diff = MIN(ext_cnt, (erp->er_extcount - nex1));
1317                 /*
1318                  * Check for deletion of entire list;
1319                  * xfs_iext_irec_remove() updates extent offsets.
1320                  */
1321                 if (ext_diff == erp->er_extcount) {
1322                         xfs_iext_irec_remove(ifp, erp_idx);
1323                         ext_cnt -= ext_diff;
1324                         nex1 = 0;
1325                         if (ext_cnt) {
1326                                 ASSERT(erp_idx < ifp->if_real_bytes /
1327                                         XFS_IEXT_BUFSZ);
1328                                 erp = &ifp->if_u1.if_ext_irec[erp_idx];
1329                                 nex1 = 0;
1330                                 continue;
1331                         } else {
1332                                 break;
1333                         }
1334                 }
1335                 /* Move extents up (if needed) */
1336                 if (nex2) {
1337                         memmove(&erp->er_extbuf[nex1],
1338                                 &erp->er_extbuf[nex1 + ext_diff],
1339                                 nex2 * sizeof(xfs_bmbt_rec_t));
1340                 }
1341                 /* Zero out rest of page */
1342                 memset(&erp->er_extbuf[nex1 + nex2], 0, (XFS_IEXT_BUFSZ -
1343                         ((nex1 + nex2) * sizeof(xfs_bmbt_rec_t))));
1344                 /* Update remaining counters */
1345                 erp->er_extcount -= ext_diff;
1346                 xfs_iext_irec_update_extoffs(ifp, erp_idx + 1, -ext_diff);
1347                 ext_cnt -= ext_diff;
1348                 nex1 = 0;
1349                 erp_idx++;
1350                 erp++;
1351         }
1352         ifp->if_bytes -= count * sizeof(xfs_bmbt_rec_t);
1353         xfs_iext_irec_compact(ifp);
1354 }
1355
1356 /*
1357  * Create, destroy, or resize a linear (direct) block of extents.
1358  */
1359 void
1360 xfs_iext_realloc_direct(
1361         xfs_ifork_t     *ifp,           /* inode fork pointer */
1362         int             new_size)       /* new size of extents */
1363 {
1364         int             rnew_size;      /* real new size of extents */
1365
1366         rnew_size = new_size;
1367
1368         ASSERT(!(ifp->if_flags & XFS_IFEXTIREC) ||
1369                 ((new_size >= 0) && (new_size <= XFS_IEXT_BUFSZ) &&
1370                  (new_size != ifp->if_real_bytes)));
1371
1372         /* Free extent records */
1373         if (new_size == 0) {
1374                 xfs_iext_destroy(ifp);
1375         }
1376         /* Resize direct extent list and zero any new bytes */
1377         else if (ifp->if_real_bytes) {
1378                 /* Check if extents will fit inside the inode */
1379                 if (new_size <= XFS_INLINE_EXTS * sizeof(xfs_bmbt_rec_t)) {
1380                         xfs_iext_direct_to_inline(ifp, new_size /
1381                                 (uint)sizeof(xfs_bmbt_rec_t));
1382                         ifp->if_bytes = new_size;
1383                         return;
1384                 }
1385                 if (!is_power_of_2(new_size)){
1386                         rnew_size = roundup_pow_of_two(new_size);
1387                 }
1388                 if (rnew_size != ifp->if_real_bytes) {
1389                         ifp->if_u1.if_extents =
1390                                 kmem_realloc(ifp->if_u1.if_extents,
1391                                                 rnew_size,
1392                                                 ifp->if_real_bytes, KM_NOFS);
1393                 }
1394                 if (rnew_size > ifp->if_real_bytes) {
1395                         memset(&ifp->if_u1.if_extents[ifp->if_bytes /
1396                                 (uint)sizeof(xfs_bmbt_rec_t)], 0,
1397                                 rnew_size - ifp->if_real_bytes);
1398                 }
1399         }
1400         /*
1401          * Switch from the inline extent buffer to a direct
1402          * extent list. Be sure to include the inline extent
1403          * bytes in new_size.
1404          */
1405         else {
1406                 new_size += ifp->if_bytes;
1407                 if (!is_power_of_2(new_size)) {
1408                         rnew_size = roundup_pow_of_two(new_size);
1409                 }
1410                 xfs_iext_inline_to_direct(ifp, rnew_size);
1411         }
1412         ifp->if_real_bytes = rnew_size;
1413         ifp->if_bytes = new_size;
1414 }
1415
1416 /*
1417  * Switch from linear (direct) extent records to inline buffer.
1418  */
1419 void
1420 xfs_iext_direct_to_inline(
1421         xfs_ifork_t     *ifp,           /* inode fork pointer */
1422         xfs_extnum_t    nextents)       /* number of extents in file */
1423 {
1424         ASSERT(ifp->if_flags & XFS_IFEXTENTS);
1425         ASSERT(nextents <= XFS_INLINE_EXTS);
1426         /*
1427          * The inline buffer was zeroed when we switched
1428          * from inline to direct extent allocation mode,
1429          * so we don't need to clear it here.
1430          */
1431         memcpy(ifp->if_u2.if_inline_ext, ifp->if_u1.if_extents,
1432                 nextents * sizeof(xfs_bmbt_rec_t));
1433         kmem_free(ifp->if_u1.if_extents);
1434         ifp->if_u1.if_extents = ifp->if_u2.if_inline_ext;
1435         ifp->if_real_bytes = 0;
1436 }
1437
1438 /*
1439  * Switch from inline buffer to linear (direct) extent records.
1440  * new_size should already be rounded up to the next power of 2
1441  * by the caller (when appropriate), so use new_size as it is.
1442  * However, since new_size may be rounded up, we can't update
1443  * if_bytes here. It is the caller's responsibility to update
1444  * if_bytes upon return.
1445  */
1446 void
1447 xfs_iext_inline_to_direct(
1448         xfs_ifork_t     *ifp,           /* inode fork pointer */
1449         int             new_size)       /* number of extents in file */
1450 {
1451         ifp->if_u1.if_extents = kmem_alloc(new_size, KM_NOFS);
1452         memset(ifp->if_u1.if_extents, 0, new_size);
1453         if (ifp->if_bytes) {
1454                 memcpy(ifp->if_u1.if_extents, ifp->if_u2.if_inline_ext,
1455                         ifp->if_bytes);
1456                 memset(ifp->if_u2.if_inline_ext, 0, XFS_INLINE_EXTS *
1457                         sizeof(xfs_bmbt_rec_t));
1458         }
1459         ifp->if_real_bytes = new_size;
1460 }
1461
1462 /*
1463  * Resize an extent indirection array to new_size bytes.
1464  */
1465 STATIC void
1466 xfs_iext_realloc_indirect(
1467         xfs_ifork_t     *ifp,           /* inode fork pointer */
1468         int             new_size)       /* new indirection array size */
1469 {
1470         int             nlists;         /* number of irec's (ex lists) */
1471         int             size;           /* current indirection array size */
1472
1473         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1474         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1475         size = nlists * sizeof(xfs_ext_irec_t);
1476         ASSERT(ifp->if_real_bytes);
1477         ASSERT((new_size >= 0) && (new_size != size));
1478         if (new_size == 0) {
1479                 xfs_iext_destroy(ifp);
1480         } else {
1481                 ifp->if_u1.if_ext_irec = (xfs_ext_irec_t *)
1482                         kmem_realloc(ifp->if_u1.if_ext_irec,
1483                                 new_size, size, KM_NOFS);
1484         }
1485 }
1486
1487 /*
1488  * Switch from indirection array to linear (direct) extent allocations.
1489  */
1490 STATIC void
1491 xfs_iext_indirect_to_direct(
1492          xfs_ifork_t    *ifp)           /* inode fork pointer */
1493 {
1494         xfs_bmbt_rec_host_t *ep;        /* extent record pointer */
1495         xfs_extnum_t    nextents;       /* number of extents in file */
1496         int             size;           /* size of file extents */
1497
1498         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1499         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1500         ASSERT(nextents <= XFS_LINEAR_EXTS);
1501         size = nextents * sizeof(xfs_bmbt_rec_t);
1502
1503         xfs_iext_irec_compact_pages(ifp);
1504         ASSERT(ifp->if_real_bytes == XFS_IEXT_BUFSZ);
1505
1506         ep = ifp->if_u1.if_ext_irec->er_extbuf;
1507         kmem_free(ifp->if_u1.if_ext_irec);
1508         ifp->if_flags &= ~XFS_IFEXTIREC;
1509         ifp->if_u1.if_extents = ep;
1510         ifp->if_bytes = size;
1511         if (nextents < XFS_LINEAR_EXTS) {
1512                 xfs_iext_realloc_direct(ifp, size);
1513         }
1514 }
1515
1516 /*
1517  * Free incore file extents.
1518  */
1519 void
1520 xfs_iext_destroy(
1521         xfs_ifork_t     *ifp)           /* inode fork pointer */
1522 {
1523         if (ifp->if_flags & XFS_IFEXTIREC) {
1524                 int     erp_idx;
1525                 int     nlists;
1526
1527                 nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1528                 for (erp_idx = nlists - 1; erp_idx >= 0 ; erp_idx--) {
1529                         xfs_iext_irec_remove(ifp, erp_idx);
1530                 }
1531                 ifp->if_flags &= ~XFS_IFEXTIREC;
1532         } else if (ifp->if_real_bytes) {
1533                 kmem_free(ifp->if_u1.if_extents);
1534         } else if (ifp->if_bytes) {
1535                 memset(ifp->if_u2.if_inline_ext, 0, XFS_INLINE_EXTS *
1536                         sizeof(xfs_bmbt_rec_t));
1537         }
1538         ifp->if_u1.if_extents = NULL;
1539         ifp->if_real_bytes = 0;
1540         ifp->if_bytes = 0;
1541 }
1542
1543 /*
1544  * Return a pointer to the extent record for file system block bno.
1545  */
1546 xfs_bmbt_rec_host_t *                   /* pointer to found extent record */
1547 xfs_iext_bno_to_ext(
1548         xfs_ifork_t     *ifp,           /* inode fork pointer */
1549         xfs_fileoff_t   bno,            /* block number to search for */
1550         xfs_extnum_t    *idxp)          /* index of target extent */
1551 {
1552         xfs_bmbt_rec_host_t *base;      /* pointer to first extent */
1553         xfs_filblks_t   blockcount = 0; /* number of blocks in extent */
1554         xfs_bmbt_rec_host_t *ep = NULL; /* pointer to target extent */
1555         xfs_ext_irec_t  *erp = NULL;    /* indirection array pointer */
1556         int             high;           /* upper boundary in search */
1557         xfs_extnum_t    idx = 0;        /* index of target extent */
1558         int             low;            /* lower boundary in search */
1559         xfs_extnum_t    nextents;       /* number of file extents */
1560         xfs_fileoff_t   startoff = 0;   /* start offset of extent */
1561
1562         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1563         if (nextents == 0) {
1564                 *idxp = 0;
1565                 return NULL;
1566         }
1567         low = 0;
1568         if (ifp->if_flags & XFS_IFEXTIREC) {
1569                 /* Find target extent list */
1570                 int     erp_idx = 0;
1571                 erp = xfs_iext_bno_to_irec(ifp, bno, &erp_idx);
1572                 base = erp->er_extbuf;
1573                 high = erp->er_extcount - 1;
1574         } else {
1575                 base = ifp->if_u1.if_extents;
1576                 high = nextents - 1;
1577         }
1578         /* Binary search extent records */
1579         while (low <= high) {
1580                 idx = (low + high) >> 1;
1581                 ep = base + idx;
1582                 startoff = xfs_bmbt_get_startoff(ep);
1583                 blockcount = xfs_bmbt_get_blockcount(ep);
1584                 if (bno < startoff) {
1585                         high = idx - 1;
1586                 } else if (bno >= startoff + blockcount) {
1587                         low = idx + 1;
1588                 } else {
1589                         /* Convert back to file-based extent index */
1590                         if (ifp->if_flags & XFS_IFEXTIREC) {
1591                                 idx += erp->er_extoff;
1592                         }
1593                         *idxp = idx;
1594                         return ep;
1595                 }
1596         }
1597         /* Convert back to file-based extent index */
1598         if (ifp->if_flags & XFS_IFEXTIREC) {
1599                 idx += erp->er_extoff;
1600         }
1601         if (bno >= startoff + blockcount) {
1602                 if (++idx == nextents) {
1603                         ep = NULL;
1604                 } else {
1605                         ep = xfs_iext_get_ext(ifp, idx);
1606                 }
1607         }
1608         *idxp = idx;
1609         return ep;
1610 }
1611
1612 /*
1613  * Return a pointer to the indirection array entry containing the
1614  * extent record for filesystem block bno. Store the index of the
1615  * target irec in *erp_idxp.
1616  */
1617 xfs_ext_irec_t *                        /* pointer to found extent record */
1618 xfs_iext_bno_to_irec(
1619         xfs_ifork_t     *ifp,           /* inode fork pointer */
1620         xfs_fileoff_t   bno,            /* block number to search for */
1621         int             *erp_idxp)      /* irec index of target ext list */
1622 {
1623         xfs_ext_irec_t  *erp = NULL;    /* indirection array pointer */
1624         xfs_ext_irec_t  *erp_next;      /* next indirection array entry */
1625         int             erp_idx;        /* indirection array index */
1626         int             nlists;         /* number of extent irec's (lists) */
1627         int             high;           /* binary search upper limit */
1628         int             low;            /* binary search lower limit */
1629
1630         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1631         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1632         erp_idx = 0;
1633         low = 0;
1634         high = nlists - 1;
1635         while (low <= high) {
1636                 erp_idx = (low + high) >> 1;
1637                 erp = &ifp->if_u1.if_ext_irec[erp_idx];
1638                 erp_next = erp_idx < nlists - 1 ? erp + 1 : NULL;
1639                 if (bno < xfs_bmbt_get_startoff(erp->er_extbuf)) {
1640                         high = erp_idx - 1;
1641                 } else if (erp_next && bno >=
1642                            xfs_bmbt_get_startoff(erp_next->er_extbuf)) {
1643                         low = erp_idx + 1;
1644                 } else {
1645                         break;
1646                 }
1647         }
1648         *erp_idxp = erp_idx;
1649         return erp;
1650 }
1651
1652 /*
1653  * Return a pointer to the indirection array entry containing the
1654  * extent record at file extent index *idxp. Store the index of the
1655  * target irec in *erp_idxp and store the page index of the target
1656  * extent record in *idxp.
1657  */
1658 xfs_ext_irec_t *
1659 xfs_iext_idx_to_irec(
1660         xfs_ifork_t     *ifp,           /* inode fork pointer */
1661         xfs_extnum_t    *idxp,          /* extent index (file -> page) */
1662         int             *erp_idxp,      /* pointer to target irec */
1663         int             realloc)        /* new bytes were just added */
1664 {
1665         xfs_ext_irec_t  *prev;          /* pointer to previous irec */
1666         xfs_ext_irec_t  *erp = NULL;    /* pointer to current irec */
1667         int             erp_idx;        /* indirection array index */
1668         int             nlists;         /* number of irec's (ex lists) */
1669         int             high;           /* binary search upper limit */
1670         int             low;            /* binary search lower limit */
1671         xfs_extnum_t    page_idx = *idxp; /* extent index in target list */
1672
1673         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1674         ASSERT(page_idx >= 0);
1675         ASSERT(page_idx <= ifp->if_bytes / sizeof(xfs_bmbt_rec_t));
1676         ASSERT(page_idx < ifp->if_bytes / sizeof(xfs_bmbt_rec_t) || realloc);
1677
1678         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1679         erp_idx = 0;
1680         low = 0;
1681         high = nlists - 1;
1682
1683         /* Binary search extent irec's */
1684         while (low <= high) {
1685                 erp_idx = (low + high) >> 1;
1686                 erp = &ifp->if_u1.if_ext_irec[erp_idx];
1687                 prev = erp_idx > 0 ? erp - 1 : NULL;
1688                 if (page_idx < erp->er_extoff || (page_idx == erp->er_extoff &&
1689                      realloc && prev && prev->er_extcount < XFS_LINEAR_EXTS)) {
1690                         high = erp_idx - 1;
1691                 } else if (page_idx > erp->er_extoff + erp->er_extcount ||
1692                            (page_idx == erp->er_extoff + erp->er_extcount &&
1693                             !realloc)) {
1694                         low = erp_idx + 1;
1695                 } else if (page_idx == erp->er_extoff + erp->er_extcount &&
1696                            erp->er_extcount == XFS_LINEAR_EXTS) {
1697                         ASSERT(realloc);
1698                         page_idx = 0;
1699                         erp_idx++;
1700                         erp = erp_idx < nlists ? erp + 1 : NULL;
1701                         break;
1702                 } else {
1703                         page_idx -= erp->er_extoff;
1704                         break;
1705                 }
1706         }
1707         *idxp = page_idx;
1708         *erp_idxp = erp_idx;
1709         return(erp);
1710 }
1711
1712 /*
1713  * Allocate and initialize an indirection array once the space needed
1714  * for incore extents increases above XFS_IEXT_BUFSZ.
1715  */
1716 void
1717 xfs_iext_irec_init(
1718         xfs_ifork_t     *ifp)           /* inode fork pointer */
1719 {
1720         xfs_ext_irec_t  *erp;           /* indirection array pointer */
1721         xfs_extnum_t    nextents;       /* number of extents in file */
1722
1723         ASSERT(!(ifp->if_flags & XFS_IFEXTIREC));
1724         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1725         ASSERT(nextents <= XFS_LINEAR_EXTS);
1726
1727         erp = kmem_alloc(sizeof(xfs_ext_irec_t), KM_NOFS);
1728
1729         if (nextents == 0) {
1730                 ifp->if_u1.if_extents = kmem_alloc(XFS_IEXT_BUFSZ, KM_NOFS);
1731         } else if (!ifp->if_real_bytes) {
1732                 xfs_iext_inline_to_direct(ifp, XFS_IEXT_BUFSZ);
1733         } else if (ifp->if_real_bytes < XFS_IEXT_BUFSZ) {
1734                 xfs_iext_realloc_direct(ifp, XFS_IEXT_BUFSZ);
1735         }
1736         erp->er_extbuf = ifp->if_u1.if_extents;
1737         erp->er_extcount = nextents;
1738         erp->er_extoff = 0;
1739
1740         ifp->if_flags |= XFS_IFEXTIREC;
1741         ifp->if_real_bytes = XFS_IEXT_BUFSZ;
1742         ifp->if_bytes = nextents * sizeof(xfs_bmbt_rec_t);
1743         ifp->if_u1.if_ext_irec = erp;
1744
1745         return;
1746 }
1747
1748 /*
1749  * Allocate and initialize a new entry in the indirection array.
1750  */
1751 xfs_ext_irec_t *
1752 xfs_iext_irec_new(
1753         xfs_ifork_t     *ifp,           /* inode fork pointer */
1754         int             erp_idx)        /* index for new irec */
1755 {
1756         xfs_ext_irec_t  *erp;           /* indirection array pointer */
1757         int             i;              /* loop counter */
1758         int             nlists;         /* number of irec's (ex lists) */
1759
1760         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1761         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1762
1763         /* Resize indirection array */
1764         xfs_iext_realloc_indirect(ifp, ++nlists *
1765                                   sizeof(xfs_ext_irec_t));
1766         /*
1767          * Move records down in the array so the
1768          * new page can use erp_idx.
1769          */
1770         erp = ifp->if_u1.if_ext_irec;
1771         for (i = nlists - 1; i > erp_idx; i--) {
1772                 memmove(&erp[i], &erp[i-1], sizeof(xfs_ext_irec_t));
1773         }
1774         ASSERT(i == erp_idx);
1775
1776         /* Initialize new extent record */
1777         erp = ifp->if_u1.if_ext_irec;
1778         erp[erp_idx].er_extbuf = kmem_alloc(XFS_IEXT_BUFSZ, KM_NOFS);
1779         ifp->if_real_bytes = nlists * XFS_IEXT_BUFSZ;
1780         memset(erp[erp_idx].er_extbuf, 0, XFS_IEXT_BUFSZ);
1781         erp[erp_idx].er_extcount = 0;
1782         erp[erp_idx].er_extoff = erp_idx > 0 ?
1783                 erp[erp_idx-1].er_extoff + erp[erp_idx-1].er_extcount : 0;
1784         return (&erp[erp_idx]);
1785 }
1786
1787 /*
1788  * Remove a record from the indirection array.
1789  */
1790 void
1791 xfs_iext_irec_remove(
1792         xfs_ifork_t     *ifp,           /* inode fork pointer */
1793         int             erp_idx)        /* irec index to remove */
1794 {
1795         xfs_ext_irec_t  *erp;           /* indirection array pointer */
1796         int             i;              /* loop counter */
1797         int             nlists;         /* number of irec's (ex lists) */
1798
1799         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1800         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1801         erp = &ifp->if_u1.if_ext_irec[erp_idx];
1802         if (erp->er_extbuf) {
1803                 xfs_iext_irec_update_extoffs(ifp, erp_idx + 1,
1804                         -erp->er_extcount);
1805                 kmem_free(erp->er_extbuf);
1806         }
1807         /* Compact extent records */
1808         erp = ifp->if_u1.if_ext_irec;
1809         for (i = erp_idx; i < nlists - 1; i++) {
1810                 memmove(&erp[i], &erp[i+1], sizeof(xfs_ext_irec_t));
1811         }
1812         /*
1813          * Manually free the last extent record from the indirection
1814          * array.  A call to xfs_iext_realloc_indirect() with a size
1815          * of zero would result in a call to xfs_iext_destroy() which
1816          * would in turn call this function again, creating a nasty
1817          * infinite loop.
1818          */
1819         if (--nlists) {
1820                 xfs_iext_realloc_indirect(ifp,
1821                         nlists * sizeof(xfs_ext_irec_t));
1822         } else {
1823                 kmem_free(ifp->if_u1.if_ext_irec);
1824         }
1825         ifp->if_real_bytes = nlists * XFS_IEXT_BUFSZ;
1826 }
1827
1828 /*
1829  * This is called to clean up large amounts of unused memory allocated
1830  * by the indirection array.  Before compacting anything though, verify
1831  * that the indirection array is still needed and switch back to the
1832  * linear extent list (or even the inline buffer) if possible.  The
1833  * compaction policy is as follows:
1834  *
1835  *    Full Compaction: Extents fit into a single page (or inline buffer)
1836  * Partial Compaction: Extents occupy less than 50% of allocated space
1837  *      No Compaction: Extents occupy at least 50% of allocated space
1838  */
1839 void
1840 xfs_iext_irec_compact(
1841         xfs_ifork_t     *ifp)           /* inode fork pointer */
1842 {
1843         xfs_extnum_t    nextents;       /* number of extents in file */
1844         int             nlists;         /* number of irec's (ex lists) */
1845
1846         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1847         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1848         nextents = ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t);
1849
1850         if (nextents == 0) {
1851                 xfs_iext_destroy(ifp);
1852         } else if (nextents <= XFS_INLINE_EXTS) {
1853                 xfs_iext_indirect_to_direct(ifp);
1854                 xfs_iext_direct_to_inline(ifp, nextents);
1855         } else if (nextents <= XFS_LINEAR_EXTS) {
1856                 xfs_iext_indirect_to_direct(ifp);
1857         } else if (nextents < (nlists * XFS_LINEAR_EXTS) >> 1) {
1858                 xfs_iext_irec_compact_pages(ifp);
1859         }
1860 }
1861
1862 /*
1863  * Combine extents from neighboring extent pages.
1864  */
1865 void
1866 xfs_iext_irec_compact_pages(
1867         xfs_ifork_t     *ifp)           /* inode fork pointer */
1868 {
1869         xfs_ext_irec_t  *erp, *erp_next;/* pointers to irec entries */
1870         int             erp_idx = 0;    /* indirection array index */
1871         int             nlists;         /* number of irec's (ex lists) */
1872
1873         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1874         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1875         while (erp_idx < nlists - 1) {
1876                 erp = &ifp->if_u1.if_ext_irec[erp_idx];
1877                 erp_next = erp + 1;
1878                 if (erp_next->er_extcount <=
1879                     (XFS_LINEAR_EXTS - erp->er_extcount)) {
1880                         memcpy(&erp->er_extbuf[erp->er_extcount],
1881                                 erp_next->er_extbuf, erp_next->er_extcount *
1882                                 sizeof(xfs_bmbt_rec_t));
1883                         erp->er_extcount += erp_next->er_extcount;
1884                         /*
1885                          * Free page before removing extent record
1886                          * so er_extoffs don't get modified in
1887                          * xfs_iext_irec_remove.
1888                          */
1889                         kmem_free(erp_next->er_extbuf);
1890                         erp_next->er_extbuf = NULL;
1891                         xfs_iext_irec_remove(ifp, erp_idx + 1);
1892                         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1893                 } else {
1894                         erp_idx++;
1895                 }
1896         }
1897 }
1898
1899 /*
1900  * This is called to update the er_extoff field in the indirection
1901  * array when extents have been added or removed from one of the
1902  * extent lists. erp_idx contains the irec index to begin updating
1903  * at and ext_diff contains the number of extents that were added
1904  * or removed.
1905  */
1906 void
1907 xfs_iext_irec_update_extoffs(
1908         xfs_ifork_t     *ifp,           /* inode fork pointer */
1909         int             erp_idx,        /* irec index to update */
1910         int             ext_diff)       /* number of new extents */
1911 {
1912         int             i;              /* loop counter */
1913         int             nlists;         /* number of irec's (ex lists */
1914
1915         ASSERT(ifp->if_flags & XFS_IFEXTIREC);
1916         nlists = ifp->if_real_bytes / XFS_IEXT_BUFSZ;
1917         for (i = erp_idx; i < nlists; i++) {
1918                 ifp->if_u1.if_ext_irec[i].er_extoff += ext_diff;
1919         }
1920 }