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