linux/fs/xfs/xfs_dir2_data.c
<<
>>
Prefs
   1/*
   2 * Copyright (c) 2000-2002,2005 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 "xfs.h"
  19#include "xfs_fs.h"
  20#include "xfs_types.h"
  21#include "xfs_log.h"
  22#include "xfs_trans.h"
  23#include "xfs_sb.h"
  24#include "xfs_ag.h"
  25#include "xfs_mount.h"
  26#include "xfs_da_btree.h"
  27#include "xfs_bmap_btree.h"
  28#include "xfs_dinode.h"
  29#include "xfs_inode.h"
  30#include "xfs_dir2_format.h"
  31#include "xfs_dir2_priv.h"
  32#include "xfs_error.h"
  33
  34STATIC xfs_dir2_data_free_t *
  35xfs_dir2_data_freefind(xfs_dir2_data_hdr_t *hdr, xfs_dir2_data_unused_t *dup);
  36
  37#ifdef DEBUG
  38/*
  39 * Check the consistency of the data block.
  40 * The input can also be a block-format directory.
  41 * Pop an assert if we find anything bad.
  42 */
  43void
  44xfs_dir2_data_check(
  45        struct xfs_inode        *dp,            /* incore inode pointer */
  46        struct xfs_buf          *bp)            /* data block's buffer */
  47{
  48        xfs_dir2_dataptr_t      addr;           /* addr for leaf lookup */
  49        xfs_dir2_data_free_t    *bf;            /* bestfree table */
  50        xfs_dir2_block_tail_t   *btp=NULL;      /* block tail */
  51        int                     count;          /* count of entries found */
  52        xfs_dir2_data_hdr_t     *hdr;           /* data block header */
  53        xfs_dir2_data_entry_t   *dep;           /* data entry */
  54        xfs_dir2_data_free_t    *dfp;           /* bestfree entry */
  55        xfs_dir2_data_unused_t  *dup;           /* unused entry */
  56        char                    *endp;          /* end of useful data */
  57        int                     freeseen;       /* mask of bestfrees seen */
  58        xfs_dahash_t            hash;           /* hash of current name */
  59        int                     i;              /* leaf index */
  60        int                     lastfree;       /* last entry was unused */
  61        xfs_dir2_leaf_entry_t   *lep=NULL;      /* block leaf entries */
  62        xfs_mount_t             *mp;            /* filesystem mount point */
  63        char                    *p;             /* current data position */
  64        int                     stale;          /* count of stale leaves */
  65        struct xfs_name         name;
  66
  67        mp = dp->i_mount;
  68        hdr = bp->b_addr;
  69        bf = hdr->bestfree;
  70        p = (char *)(hdr + 1);
  71
  72        if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
  73                btp = xfs_dir2_block_tail_p(mp, hdr);
  74                lep = xfs_dir2_block_leaf_p(btp);
  75                endp = (char *)lep;
  76        } else {
  77                ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC));
  78                endp = (char *)hdr + mp->m_dirblksize;
  79        }
  80
  81        count = lastfree = freeseen = 0;
  82        /*
  83         * Account for zero bestfree entries.
  84         */
  85        if (!bf[0].length) {
  86                ASSERT(!bf[0].offset);
  87                freeseen |= 1 << 0;
  88        }
  89        if (!bf[1].length) {
  90                ASSERT(!bf[1].offset);
  91                freeseen |= 1 << 1;
  92        }
  93        if (!bf[2].length) {
  94                ASSERT(!bf[2].offset);
  95                freeseen |= 1 << 2;
  96        }
  97        ASSERT(be16_to_cpu(bf[0].length) >= be16_to_cpu(bf[1].length));
  98        ASSERT(be16_to_cpu(bf[1].length) >= be16_to_cpu(bf[2].length));
  99        /*
 100         * Loop over the data/unused entries.
 101         */
 102        while (p < endp) {
 103                dup = (xfs_dir2_data_unused_t *)p;
 104                /*
 105                 * If it's unused, look for the space in the bestfree table.
 106                 * If we find it, account for that, else make sure it
 107                 * doesn't need to be there.
 108                 */
 109                if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
 110                        ASSERT(lastfree == 0);
 111                        ASSERT(be16_to_cpu(*xfs_dir2_data_unused_tag_p(dup)) ==
 112                               (char *)dup - (char *)hdr);
 113                        dfp = xfs_dir2_data_freefind(hdr, dup);
 114                        if (dfp) {
 115                                i = (int)(dfp - bf);
 116                                ASSERT((freeseen & (1 << i)) == 0);
 117                                freeseen |= 1 << i;
 118                        } else {
 119                                ASSERT(be16_to_cpu(dup->length) <=
 120                                       be16_to_cpu(bf[2].length));
 121                        }
 122                        p += be16_to_cpu(dup->length);
 123                        lastfree = 1;
 124                        continue;
 125                }
 126                /*
 127                 * It's a real entry.  Validate the fields.
 128                 * If this is a block directory then make sure it's
 129                 * in the leaf section of the block.
 130                 * The linear search is crude but this is DEBUG code.
 131                 */
 132                dep = (xfs_dir2_data_entry_t *)p;
 133                ASSERT(dep->namelen != 0);
 134                ASSERT(xfs_dir_ino_validate(mp, be64_to_cpu(dep->inumber)) == 0);
 135                ASSERT(be16_to_cpu(*xfs_dir2_data_entry_tag_p(dep)) ==
 136                       (char *)dep - (char *)hdr);
 137                count++;
 138                lastfree = 0;
 139                if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
 140                        addr = xfs_dir2_db_off_to_dataptr(mp, mp->m_dirdatablk,
 141                                (xfs_dir2_data_aoff_t)
 142                                ((char *)dep - (char *)hdr));
 143                        name.name = dep->name;
 144                        name.len = dep->namelen;
 145                        hash = mp->m_dirnameops->hashname(&name);
 146                        for (i = 0; i < be32_to_cpu(btp->count); i++) {
 147                                if (be32_to_cpu(lep[i].address) == addr &&
 148                                    be32_to_cpu(lep[i].hashval) == hash)
 149                                        break;
 150                        }
 151                        ASSERT(i < be32_to_cpu(btp->count));
 152                }
 153                p += xfs_dir2_data_entsize(dep->namelen);
 154        }
 155        /*
 156         * Need to have seen all the entries and all the bestfree slots.
 157         */
 158        ASSERT(freeseen == 7);
 159        if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
 160                for (i = stale = 0; i < be32_to_cpu(btp->count); i++) {
 161                        if (lep[i].address ==
 162                            cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 163                                stale++;
 164                        if (i > 0)
 165                                ASSERT(be32_to_cpu(lep[i].hashval) >= be32_to_cpu(lep[i - 1].hashval));
 166                }
 167                ASSERT(count == be32_to_cpu(btp->count) - be32_to_cpu(btp->stale));
 168                ASSERT(stale == be32_to_cpu(btp->stale));
 169        }
 170}
 171#endif
 172
 173/*
 174 * Given a data block and an unused entry from that block,
 175 * return the bestfree entry if any that corresponds to it.
 176 */
 177STATIC xfs_dir2_data_free_t *
 178xfs_dir2_data_freefind(
 179        xfs_dir2_data_hdr_t     *hdr,           /* data block */
 180        xfs_dir2_data_unused_t  *dup)           /* data unused entry */
 181{
 182        xfs_dir2_data_free_t    *dfp;           /* bestfree entry */
 183        xfs_dir2_data_aoff_t    off;            /* offset value needed */
 184#if defined(DEBUG) && defined(__KERNEL__)
 185        int                     matched;        /* matched the value */
 186        int                     seenzero;       /* saw a 0 bestfree entry */
 187#endif
 188
 189        off = (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr);
 190#if defined(DEBUG) && defined(__KERNEL__)
 191        /*
 192         * Validate some consistency in the bestfree table.
 193         * Check order, non-overlapping entries, and if we find the
 194         * one we're looking for it has to be exact.
 195         */
 196        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 197               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 198        for (dfp = &hdr->bestfree[0], seenzero = matched = 0;
 199             dfp < &hdr->bestfree[XFS_DIR2_DATA_FD_COUNT];
 200             dfp++) {
 201                if (!dfp->offset) {
 202                        ASSERT(!dfp->length);
 203                        seenzero = 1;
 204                        continue;
 205                }
 206                ASSERT(seenzero == 0);
 207                if (be16_to_cpu(dfp->offset) == off) {
 208                        matched = 1;
 209                        ASSERT(dfp->length == dup->length);
 210                } else if (off < be16_to_cpu(dfp->offset))
 211                        ASSERT(off + be16_to_cpu(dup->length) <= be16_to_cpu(dfp->offset));
 212                else
 213                        ASSERT(be16_to_cpu(dfp->offset) + be16_to_cpu(dfp->length) <= off);
 214                ASSERT(matched || be16_to_cpu(dfp->length) >= be16_to_cpu(dup->length));
 215                if (dfp > &hdr->bestfree[0])
 216                        ASSERT(be16_to_cpu(dfp[-1].length) >= be16_to_cpu(dfp[0].length));
 217        }
 218#endif
 219        /*
 220         * If this is smaller than the smallest bestfree entry,
 221         * it can't be there since they're sorted.
 222         */
 223        if (be16_to_cpu(dup->length) <
 224            be16_to_cpu(hdr->bestfree[XFS_DIR2_DATA_FD_COUNT - 1].length))
 225                return NULL;
 226        /*
 227         * Look at the three bestfree entries for our guy.
 228         */
 229        for (dfp = &hdr->bestfree[0];
 230             dfp < &hdr->bestfree[XFS_DIR2_DATA_FD_COUNT];
 231             dfp++) {
 232                if (!dfp->offset)
 233                        return NULL;
 234                if (be16_to_cpu(dfp->offset) == off)
 235                        return dfp;
 236        }
 237        /*
 238         * Didn't find it.  This only happens if there are duplicate lengths.
 239         */
 240        return NULL;
 241}
 242
 243/*
 244 * Insert an unused-space entry into the bestfree table.
 245 */
 246xfs_dir2_data_free_t *                          /* entry inserted */
 247xfs_dir2_data_freeinsert(
 248        xfs_dir2_data_hdr_t     *hdr,           /* data block pointer */
 249        xfs_dir2_data_unused_t  *dup,           /* unused space */
 250        int                     *loghead)       /* log the data header (out) */
 251{
 252        xfs_dir2_data_free_t    *dfp;           /* bestfree table pointer */
 253        xfs_dir2_data_free_t    new;            /* new bestfree entry */
 254
 255#ifdef __KERNEL__
 256        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 257               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 258#endif
 259        dfp = hdr->bestfree;
 260        new.length = dup->length;
 261        new.offset = cpu_to_be16((char *)dup - (char *)hdr);
 262
 263        /*
 264         * Insert at position 0, 1, or 2; or not at all.
 265         */
 266        if (be16_to_cpu(new.length) > be16_to_cpu(dfp[0].length)) {
 267                dfp[2] = dfp[1];
 268                dfp[1] = dfp[0];
 269                dfp[0] = new;
 270                *loghead = 1;
 271                return &dfp[0];
 272        }
 273        if (be16_to_cpu(new.length) > be16_to_cpu(dfp[1].length)) {
 274                dfp[2] = dfp[1];
 275                dfp[1] = new;
 276                *loghead = 1;
 277                return &dfp[1];
 278        }
 279        if (be16_to_cpu(new.length) > be16_to_cpu(dfp[2].length)) {
 280                dfp[2] = new;
 281                *loghead = 1;
 282                return &dfp[2];
 283        }
 284        return NULL;
 285}
 286
 287/*
 288 * Remove a bestfree entry from the table.
 289 */
 290STATIC void
 291xfs_dir2_data_freeremove(
 292        xfs_dir2_data_hdr_t     *hdr,           /* data block header */
 293        xfs_dir2_data_free_t    *dfp,           /* bestfree entry pointer */
 294        int                     *loghead)       /* out: log data header */
 295{
 296#ifdef __KERNEL__
 297        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 298               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 299#endif
 300        /*
 301         * It's the first entry, slide the next 2 up.
 302         */
 303        if (dfp == &hdr->bestfree[0]) {
 304                hdr->bestfree[0] = hdr->bestfree[1];
 305                hdr->bestfree[1] = hdr->bestfree[2];
 306        }
 307        /*
 308         * It's the second entry, slide the 3rd entry up.
 309         */
 310        else if (dfp == &hdr->bestfree[1])
 311                hdr->bestfree[1] = hdr->bestfree[2];
 312        /*
 313         * Must be the last entry.
 314         */
 315        else
 316                ASSERT(dfp == &hdr->bestfree[2]);
 317        /*
 318         * Clear the 3rd entry, must be zero now.
 319         */
 320        hdr->bestfree[2].length = 0;
 321        hdr->bestfree[2].offset = 0;
 322        *loghead = 1;
 323}
 324
 325/*
 326 * Given a data block, reconstruct its bestfree map.
 327 */
 328void
 329xfs_dir2_data_freescan(
 330        xfs_mount_t             *mp,            /* filesystem mount point */
 331        xfs_dir2_data_hdr_t     *hdr,           /* data block header */
 332        int                     *loghead)       /* out: log data header */
 333{
 334        xfs_dir2_block_tail_t   *btp;           /* block tail */
 335        xfs_dir2_data_entry_t   *dep;           /* active data entry */
 336        xfs_dir2_data_unused_t  *dup;           /* unused data entry */
 337        char                    *endp;          /* end of block's data */
 338        char                    *p;             /* current entry pointer */
 339
 340#ifdef __KERNEL__
 341        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 342               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 343#endif
 344        /*
 345         * Start by clearing the table.
 346         */
 347        memset(hdr->bestfree, 0, sizeof(hdr->bestfree));
 348        *loghead = 1;
 349        /*
 350         * Set up pointers.
 351         */
 352        p = (char *)(hdr + 1);
 353        if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) {
 354                btp = xfs_dir2_block_tail_p(mp, hdr);
 355                endp = (char *)xfs_dir2_block_leaf_p(btp);
 356        } else
 357                endp = (char *)hdr + mp->m_dirblksize;
 358        /*
 359         * Loop over the block's entries.
 360         */
 361        while (p < endp) {
 362                dup = (xfs_dir2_data_unused_t *)p;
 363                /*
 364                 * If it's a free entry, insert it.
 365                 */
 366                if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
 367                        ASSERT((char *)dup - (char *)hdr ==
 368                               be16_to_cpu(*xfs_dir2_data_unused_tag_p(dup)));
 369                        xfs_dir2_data_freeinsert(hdr, dup, loghead);
 370                        p += be16_to_cpu(dup->length);
 371                }
 372                /*
 373                 * For active entries, check their tags and skip them.
 374                 */
 375                else {
 376                        dep = (xfs_dir2_data_entry_t *)p;
 377                        ASSERT((char *)dep - (char *)hdr ==
 378                               be16_to_cpu(*xfs_dir2_data_entry_tag_p(dep)));
 379                        p += xfs_dir2_data_entsize(dep->namelen);
 380                }
 381        }
 382}
 383
 384/*
 385 * Initialize a data block at the given block number in the directory.
 386 * Give back the buffer for the created block.
 387 */
 388int                                             /* error */
 389xfs_dir2_data_init(
 390        xfs_da_args_t           *args,          /* directory operation args */
 391        xfs_dir2_db_t           blkno,          /* logical dir block number */
 392        struct xfs_buf          **bpp)          /* output block buffer */
 393{
 394        struct xfs_buf          *bp;            /* block buffer */
 395        xfs_dir2_data_hdr_t     *hdr;           /* data block header */
 396        xfs_inode_t             *dp;            /* incore directory inode */
 397        xfs_dir2_data_unused_t  *dup;           /* unused entry pointer */
 398        int                     error;          /* error return value */
 399        int                     i;              /* bestfree index */
 400        xfs_mount_t             *mp;            /* filesystem mount point */
 401        xfs_trans_t             *tp;            /* transaction pointer */
 402        int                     t;              /* temp */
 403
 404        dp = args->dp;
 405        mp = dp->i_mount;
 406        tp = args->trans;
 407        /*
 408         * Get the buffer set up for the block.
 409         */
 410        error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(mp, blkno), -1, &bp,
 411                XFS_DATA_FORK);
 412        if (error) {
 413                return error;
 414        }
 415        ASSERT(bp != NULL);
 416
 417        /*
 418         * Initialize the header.
 419         */
 420        hdr = bp->b_addr;
 421        hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
 422        hdr->bestfree[0].offset = cpu_to_be16(sizeof(*hdr));
 423        for (i = 1; i < XFS_DIR2_DATA_FD_COUNT; i++) {
 424                hdr->bestfree[i].length = 0;
 425                hdr->bestfree[i].offset = 0;
 426        }
 427
 428        /*
 429         * Set up an unused entry for the block's body.
 430         */
 431        dup = (xfs_dir2_data_unused_t *)(hdr + 1);
 432        dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
 433
 434        t = mp->m_dirblksize - (uint)sizeof(*hdr);
 435        hdr->bestfree[0].length = cpu_to_be16(t);
 436        dup->length = cpu_to_be16(t);
 437        *xfs_dir2_data_unused_tag_p(dup) = cpu_to_be16((char *)dup - (char *)hdr);
 438        /*
 439         * Log it and return it.
 440         */
 441        xfs_dir2_data_log_header(tp, bp);
 442        xfs_dir2_data_log_unused(tp, bp, dup);
 443        *bpp = bp;
 444        return 0;
 445}
 446
 447/*
 448 * Log an active data entry from the block.
 449 */
 450void
 451xfs_dir2_data_log_entry(
 452        struct xfs_trans        *tp,
 453        struct xfs_buf          *bp,
 454        xfs_dir2_data_entry_t   *dep)           /* data entry pointer */
 455{
 456        xfs_dir2_data_hdr_t     *hdr = bp->b_addr;
 457
 458        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 459               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 460
 461        xfs_trans_log_buf(tp, bp, (uint)((char *)dep - (char *)hdr),
 462                (uint)((char *)(xfs_dir2_data_entry_tag_p(dep) + 1) -
 463                       (char *)hdr - 1));
 464}
 465
 466/*
 467 * Log a data block header.
 468 */
 469void
 470xfs_dir2_data_log_header(
 471        struct xfs_trans        *tp,
 472        struct xfs_buf          *bp)
 473{
 474        xfs_dir2_data_hdr_t     *hdr = bp->b_addr;
 475
 476        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 477               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 478
 479        xfs_trans_log_buf(tp, bp, 0, sizeof(*hdr) - 1);
 480}
 481
 482/*
 483 * Log a data unused entry.
 484 */
 485void
 486xfs_dir2_data_log_unused(
 487        struct xfs_trans        *tp,
 488        struct xfs_buf          *bp,
 489        xfs_dir2_data_unused_t  *dup)           /* data unused pointer */
 490{
 491        xfs_dir2_data_hdr_t     *hdr = bp->b_addr;
 492
 493        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 494               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 495
 496        /*
 497         * Log the first part of the unused entry.
 498         */
 499        xfs_trans_log_buf(tp, bp, (uint)((char *)dup - (char *)hdr),
 500                (uint)((char *)&dup->length + sizeof(dup->length) -
 501                       1 - (char *)hdr));
 502        /*
 503         * Log the end (tag) of the unused entry.
 504         */
 505        xfs_trans_log_buf(tp, bp,
 506                (uint)((char *)xfs_dir2_data_unused_tag_p(dup) - (char *)hdr),
 507                (uint)((char *)xfs_dir2_data_unused_tag_p(dup) - (char *)hdr +
 508                       sizeof(xfs_dir2_data_off_t) - 1));
 509}
 510
 511/*
 512 * Make a byte range in the data block unused.
 513 * Its current contents are unimportant.
 514 */
 515void
 516xfs_dir2_data_make_free(
 517        struct xfs_trans        *tp,
 518        struct xfs_buf          *bp,
 519        xfs_dir2_data_aoff_t    offset,         /* starting byte offset */
 520        xfs_dir2_data_aoff_t    len,            /* length in bytes */
 521        int                     *needlogp,      /* out: log header */
 522        int                     *needscanp)     /* out: regen bestfree */
 523{
 524        xfs_dir2_data_hdr_t     *hdr;           /* data block pointer */
 525        xfs_dir2_data_free_t    *dfp;           /* bestfree pointer */
 526        char                    *endptr;        /* end of data area */
 527        xfs_mount_t             *mp;            /* filesystem mount point */
 528        int                     needscan;       /* need to regen bestfree */
 529        xfs_dir2_data_unused_t  *newdup;        /* new unused entry */
 530        xfs_dir2_data_unused_t  *postdup;       /* unused entry after us */
 531        xfs_dir2_data_unused_t  *prevdup;       /* unused entry before us */
 532
 533        mp = tp->t_mountp;
 534        hdr = bp->b_addr;
 535
 536        /*
 537         * Figure out where the end of the data area is.
 538         */
 539        if (hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC))
 540                endptr = (char *)hdr + mp->m_dirblksize;
 541        else {
 542                xfs_dir2_block_tail_t   *btp;   /* block tail */
 543
 544                ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 545                btp = xfs_dir2_block_tail_p(mp, hdr);
 546                endptr = (char *)xfs_dir2_block_leaf_p(btp);
 547        }
 548        /*
 549         * If this isn't the start of the block, then back up to
 550         * the previous entry and see if it's free.
 551         */
 552        if (offset > sizeof(*hdr)) {
 553                __be16                  *tagp;  /* tag just before us */
 554
 555                tagp = (__be16 *)((char *)hdr + offset) - 1;
 556                prevdup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
 557                if (be16_to_cpu(prevdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
 558                        prevdup = NULL;
 559        } else
 560                prevdup = NULL;
 561        /*
 562         * If this isn't the end of the block, see if the entry after
 563         * us is free.
 564         */
 565        if ((char *)hdr + offset + len < endptr) {
 566                postdup =
 567                        (xfs_dir2_data_unused_t *)((char *)hdr + offset + len);
 568                if (be16_to_cpu(postdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
 569                        postdup = NULL;
 570        } else
 571                postdup = NULL;
 572        ASSERT(*needscanp == 0);
 573        needscan = 0;
 574        /*
 575         * Previous and following entries are both free,
 576         * merge everything into a single free entry.
 577         */
 578        if (prevdup && postdup) {
 579                xfs_dir2_data_free_t    *dfp2;  /* another bestfree pointer */
 580
 581                /*
 582                 * See if prevdup and/or postdup are in bestfree table.
 583                 */
 584                dfp = xfs_dir2_data_freefind(hdr, prevdup);
 585                dfp2 = xfs_dir2_data_freefind(hdr, postdup);
 586                /*
 587                 * We need a rescan unless there are exactly 2 free entries
 588                 * namely our two.  Then we know what's happening, otherwise
 589                 * since the third bestfree is there, there might be more
 590                 * entries.
 591                 */
 592                needscan = (hdr->bestfree[2].length != 0);
 593                /*
 594                 * Fix up the new big freespace.
 595                 */
 596                be16_add_cpu(&prevdup->length, len + be16_to_cpu(postdup->length));
 597                *xfs_dir2_data_unused_tag_p(prevdup) =
 598                        cpu_to_be16((char *)prevdup - (char *)hdr);
 599                xfs_dir2_data_log_unused(tp, bp, prevdup);
 600                if (!needscan) {
 601                        /*
 602                         * Has to be the case that entries 0 and 1 are
 603                         * dfp and dfp2 (don't know which is which), and
 604                         * entry 2 is empty.
 605                         * Remove entry 1 first then entry 0.
 606                         */
 607                        ASSERT(dfp && dfp2);
 608                        if (dfp == &hdr->bestfree[1]) {
 609                                dfp = &hdr->bestfree[0];
 610                                ASSERT(dfp2 == dfp);
 611                                dfp2 = &hdr->bestfree[1];
 612                        }
 613                        xfs_dir2_data_freeremove(hdr, dfp2, needlogp);
 614                        xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 615                        /*
 616                         * Now insert the new entry.
 617                         */
 618                        dfp = xfs_dir2_data_freeinsert(hdr, prevdup, needlogp);
 619                        ASSERT(dfp == &hdr->bestfree[0]);
 620                        ASSERT(dfp->length == prevdup->length);
 621                        ASSERT(!dfp[1].length);
 622                        ASSERT(!dfp[2].length);
 623                }
 624        }
 625        /*
 626         * The entry before us is free, merge with it.
 627         */
 628        else if (prevdup) {
 629                dfp = xfs_dir2_data_freefind(hdr, prevdup);
 630                be16_add_cpu(&prevdup->length, len);
 631                *xfs_dir2_data_unused_tag_p(prevdup) =
 632                        cpu_to_be16((char *)prevdup - (char *)hdr);
 633                xfs_dir2_data_log_unused(tp, bp, prevdup);
 634                /*
 635                 * If the previous entry was in the table, the new entry
 636                 * is longer, so it will be in the table too.  Remove
 637                 * the old one and add the new one.
 638                 */
 639                if (dfp) {
 640                        xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 641                        xfs_dir2_data_freeinsert(hdr, prevdup, needlogp);
 642                }
 643                /*
 644                 * Otherwise we need a scan if the new entry is big enough.
 645                 */
 646                else {
 647                        needscan = be16_to_cpu(prevdup->length) >
 648                                   be16_to_cpu(hdr->bestfree[2].length);
 649                }
 650        }
 651        /*
 652         * The following entry is free, merge with it.
 653         */
 654        else if (postdup) {
 655                dfp = xfs_dir2_data_freefind(hdr, postdup);
 656                newdup = (xfs_dir2_data_unused_t *)((char *)hdr + offset);
 657                newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
 658                newdup->length = cpu_to_be16(len + be16_to_cpu(postdup->length));
 659                *xfs_dir2_data_unused_tag_p(newdup) =
 660                        cpu_to_be16((char *)newdup - (char *)hdr);
 661                xfs_dir2_data_log_unused(tp, bp, newdup);
 662                /*
 663                 * If the following entry was in the table, the new entry
 664                 * is longer, so it will be in the table too.  Remove
 665                 * the old one and add the new one.
 666                 */
 667                if (dfp) {
 668                        xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 669                        xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
 670                }
 671                /*
 672                 * Otherwise we need a scan if the new entry is big enough.
 673                 */
 674                else {
 675                        needscan = be16_to_cpu(newdup->length) >
 676                                   be16_to_cpu(hdr->bestfree[2].length);
 677                }
 678        }
 679        /*
 680         * Neither neighbor is free.  Make a new entry.
 681         */
 682        else {
 683                newdup = (xfs_dir2_data_unused_t *)((char *)hdr + offset);
 684                newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
 685                newdup->length = cpu_to_be16(len);
 686                *xfs_dir2_data_unused_tag_p(newdup) =
 687                        cpu_to_be16((char *)newdup - (char *)hdr);
 688                xfs_dir2_data_log_unused(tp, bp, newdup);
 689                xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
 690        }
 691        *needscanp = needscan;
 692}
 693
 694/*
 695 * Take a byte range out of an existing unused space and make it un-free.
 696 */
 697void
 698xfs_dir2_data_use_free(
 699        struct xfs_trans        *tp,
 700        struct xfs_buf          *bp,
 701        xfs_dir2_data_unused_t  *dup,           /* unused entry */
 702        xfs_dir2_data_aoff_t    offset,         /* starting offset to use */
 703        xfs_dir2_data_aoff_t    len,            /* length to use */
 704        int                     *needlogp,      /* out: need to log header */
 705        int                     *needscanp)     /* out: need regen bestfree */
 706{
 707        xfs_dir2_data_hdr_t     *hdr;           /* data block header */
 708        xfs_dir2_data_free_t    *dfp;           /* bestfree pointer */
 709        int                     matchback;      /* matches end of freespace */
 710        int                     matchfront;     /* matches start of freespace */
 711        int                     needscan;       /* need to regen bestfree */
 712        xfs_dir2_data_unused_t  *newdup;        /* new unused entry */
 713        xfs_dir2_data_unused_t  *newdup2;       /* another new unused entry */
 714        int                     oldlen;         /* old unused entry's length */
 715
 716        hdr = bp->b_addr;
 717        ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
 718               hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC));
 719        ASSERT(be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG);
 720        ASSERT(offset >= (char *)dup - (char *)hdr);
 721        ASSERT(offset + len <= (char *)dup + be16_to_cpu(dup->length) - (char *)hdr);
 722        ASSERT((char *)dup - (char *)hdr == be16_to_cpu(*xfs_dir2_data_unused_tag_p(dup)));
 723        /*
 724         * Look up the entry in the bestfree table.
 725         */
 726        dfp = xfs_dir2_data_freefind(hdr, dup);
 727        oldlen = be16_to_cpu(dup->length);
 728        ASSERT(dfp || oldlen <= be16_to_cpu(hdr->bestfree[2].length));
 729        /*
 730         * Check for alignment with front and back of the entry.
 731         */
 732        matchfront = (char *)dup - (char *)hdr == offset;
 733        matchback = (char *)dup + oldlen - (char *)hdr == offset + len;
 734        ASSERT(*needscanp == 0);
 735        needscan = 0;
 736        /*
 737         * If we matched it exactly we just need to get rid of it from
 738         * the bestfree table.
 739         */
 740        if (matchfront && matchback) {
 741                if (dfp) {
 742                        needscan = (hdr->bestfree[2].offset != 0);
 743                        if (!needscan)
 744                                xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 745                }
 746        }
 747        /*
 748         * We match the first part of the entry.
 749         * Make a new entry with the remaining freespace.
 750         */
 751        else if (matchfront) {
 752                newdup = (xfs_dir2_data_unused_t *)((char *)hdr + offset + len);
 753                newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
 754                newdup->length = cpu_to_be16(oldlen - len);
 755                *xfs_dir2_data_unused_tag_p(newdup) =
 756                        cpu_to_be16((char *)newdup - (char *)hdr);
 757                xfs_dir2_data_log_unused(tp, bp, newdup);
 758                /*
 759                 * If it was in the table, remove it and add the new one.
 760                 */
 761                if (dfp) {
 762                        xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 763                        dfp = xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
 764                        ASSERT(dfp != NULL);
 765                        ASSERT(dfp->length == newdup->length);
 766                        ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)hdr);
 767                        /*
 768                         * If we got inserted at the last slot,
 769                         * that means we don't know if there was a better
 770                         * choice for the last slot, or not.  Rescan.
 771                         */
 772                        needscan = dfp == &hdr->bestfree[2];
 773                }
 774        }
 775        /*
 776         * We match the last part of the entry.
 777         * Trim the allocated space off the tail of the entry.
 778         */
 779        else if (matchback) {
 780                newdup = dup;
 781                newdup->length = cpu_to_be16(((char *)hdr + offset) - (char *)newdup);
 782                *xfs_dir2_data_unused_tag_p(newdup) =
 783                        cpu_to_be16((char *)newdup - (char *)hdr);
 784                xfs_dir2_data_log_unused(tp, bp, newdup);
 785                /*
 786                 * If it was in the table, remove it and add the new one.
 787                 */
 788                if (dfp) {
 789                        xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 790                        dfp = xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
 791                        ASSERT(dfp != NULL);
 792                        ASSERT(dfp->length == newdup->length);
 793                        ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)hdr);
 794                        /*
 795                         * If we got inserted at the last slot,
 796                         * that means we don't know if there was a better
 797                         * choice for the last slot, or not.  Rescan.
 798                         */
 799                        needscan = dfp == &hdr->bestfree[2];
 800                }
 801        }
 802        /*
 803         * Poking out the middle of an entry.
 804         * Make two new entries.
 805         */
 806        else {
 807                newdup = dup;
 808                newdup->length = cpu_to_be16(((char *)hdr + offset) - (char *)newdup);
 809                *xfs_dir2_data_unused_tag_p(newdup) =
 810                        cpu_to_be16((char *)newdup - (char *)hdr);
 811                xfs_dir2_data_log_unused(tp, bp, newdup);
 812                newdup2 = (xfs_dir2_data_unused_t *)((char *)hdr + offset + len);
 813                newdup2->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
 814                newdup2->length = cpu_to_be16(oldlen - len - be16_to_cpu(newdup->length));
 815                *xfs_dir2_data_unused_tag_p(newdup2) =
 816                        cpu_to_be16((char *)newdup2 - (char *)hdr);
 817                xfs_dir2_data_log_unused(tp, bp, newdup2);
 818                /*
 819                 * If the old entry was in the table, we need to scan
 820                 * if the 3rd entry was valid, since these entries
 821                 * are smaller than the old one.
 822                 * If we don't need to scan that means there were 1 or 2
 823                 * entries in the table, and removing the old and adding
 824                 * the 2 new will work.
 825                 */
 826                if (dfp) {
 827                        needscan = (hdr->bestfree[2].length != 0);
 828                        if (!needscan) {
 829                                xfs_dir2_data_freeremove(hdr, dfp, needlogp);
 830                                xfs_dir2_data_freeinsert(hdr, newdup, needlogp);
 831                                xfs_dir2_data_freeinsert(hdr, newdup2,
 832                                                         needlogp);
 833                        }
 834                }
 835        }
 836        *needscanp = needscan;
 837}
 838
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.