sys/fs/nandfs/bmap.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2012 Semihalf
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30
  31 #include <sys/param.h>
  32 #include <sys/systm.h>
  33 #include <sys/namei.h>
  34 #include <sys/kernel.h>
  35 #include <sys/stat.h>
  36 #include <sys/buf.h>
  37 #include <sys/bio.h>
  38 #include <sys/proc.h>
  39 #include <sys/mount.h>
  40 #include <sys/vnode.h>
  41 #include <sys/signalvar.h>
  42 #include <sys/malloc.h>
  43 #include <sys/dirent.h>
  44 #include <sys/lockf.h>
  45 #include <sys/ktr.h>
  46 #include <sys/kdb.h>
  47
  48 #include <vm/vm.h>
  49 #include <vm/vm_extern.h>
  50 #include <vm/vm_object.h>
  51 #include <vm/vnode_pager.h>
  52
  53 #include <machine/_inttypes.h>
  54
  55 #include <vm/vm.h>
  56 #include <vm/vm_extern.h>
  57 #include <vm/vm_object.h>
  58 #include <vm/vnode_pager.h>
  59
  60 #include "nandfs_mount.h"
  61 #include "nandfs.h"
  62 #include "nandfs_subr.h"
  63 #include "bmap.h"
  64
  65 static int bmap_getlbns(struct nandfs_node *, nandfs_lbn_t,
  66     struct nandfs_indir *, int *);
  67
  68 int
  69 bmap_lookup(struct nandfs_node *node, nandfs_lbn_t lblk, nandfs_daddr_t *vblk)
  70 {
  71         struct nandfs_inode *ip;
  72         struct nandfs_indir a[NANDFS_NIADDR + 1], *ap;
  73         nandfs_daddr_t daddr;
  74         struct buf *bp;
  75         int error;
  76         int num, *nump;
  77
  78         DPRINTF(BMAP, ("%s: node %p lblk %jx enter\n", __func__, node, lblk));
  79         ip = &node->nn_inode;
  80
  81         ap = a;
  82         nump = &num;
  83
  84         error = bmap_getlbns(node, lblk, ap, nump);
  85         if (error)
  86                 return (error);
  87
  88         if (num == 0) {
  89                 *vblk = ip->i_db[lblk];
  90                 return (0);
  91         }
  92
  93         DPRINTF(BMAP, ("%s: node %p lblk=%jx trying ip->i_ib[%x]\n", __func__,
  94             node, lblk, ap->in_off));
  95         daddr = ip->i_ib[ap->in_off];
  96         for (bp = NULL, ++ap; --num; ap++) {
  97                 if (daddr == 0) {
  98                         DPRINTF(BMAP, ("%s: node %p lblk=%jx returning with "
  99                             "vblk 0\n", __func__, node, lblk));
 100                         *vblk = 0;
 101                         return (0);
 102                 }
 103                 if (ap->in_lbn == lblk) {
 104                         DPRINTF(BMAP, ("%s: node %p lblk=%jx ap->in_lbn=%jx "
 105                             "returning address of indirect block (%jx)\n",
 106                             __func__, node, lblk, ap->in_lbn, daddr));
 107                         *vblk = daddr;
 108                         return (0);
 109                 }
 110
 111                 DPRINTF(BMAP, ("%s: node %p lblk=%jx reading block "
 112                     "ap->in_lbn=%jx\n", __func__, node, lblk, ap->in_lbn));
 113
 114                 error = nandfs_bread_meta(node, ap->in_lbn, NOCRED, 0, &bp);
 115                 if (error) {
 116                         brelse(bp);
 117                         return (error);
 118                 }
 119
 120                 daddr = ((nandfs_daddr_t *)bp->b_data)[ap->in_off];
 121                 brelse(bp);
 122         }
 123
 124         DPRINTF(BMAP, ("%s: node %p lblk=%jx returning with %jx\n", __func__,
 125             node, lblk, daddr));
 126         *vblk = daddr;
 127
 128         return (0);
 129 }
 130
 131 int
 132 bmap_dirty_meta(struct nandfs_node *node, nandfs_lbn_t lblk, int force)
 133 {
 134         struct nandfs_indir a[NANDFS_NIADDR+1], *ap;
 135 #ifdef DEBUG
 136         nandfs_daddr_t daddr;
 137 #endif
 138         struct buf *bp;
 139         int error;
 140         int num, *nump;
 141
 142         DPRINTF(BMAP, ("%s: node %p lblk=%jx\n", __func__, node, lblk));
 143
 144         ap = a;
 145         nump = &num;
 146
 147         error = bmap_getlbns(node, lblk, ap, nump);
 148         if (error)
 149                 return (error);
 150
 151         /*
 152          * Direct block, nothing to do
 153          */
 154         if (num == 0)
 155                 return (0);
 156
 157         DPRINTF(BMAP, ("%s: node %p reading blocks\n", __func__, node));
 158
 159         for (bp = NULL, ++ap; --num; ap++) {
 160                 error = nandfs_bread_meta(node, ap->in_lbn, NOCRED, 0, &bp);
 161                 if (error) {
 162                         brelse(bp);
 163                         return (error);
 164                 }
 165
 166 #ifdef DEBUG
 167                 daddr = ((nandfs_daddr_t *)bp->b_data)[ap->in_off];
 168                 MPASS(daddr != 0 || node->nn_ino == 3);
 169 #endif
 170
 171                 error = nandfs_dirty_buf_meta(bp, force);
 172                 if (error)
 173                         return (error);
 174         }
 175
 176         return (0);
 177 }
 178
 179 int
 180 bmap_insert_block(struct nandfs_node *node, nandfs_lbn_t lblk,
 181     nandfs_daddr_t vblk)
 182 {
 183         struct nandfs_inode *ip;
 184         struct nandfs_indir a[NANDFS_NIADDR+1], *ap;
 185         struct buf *bp;
 186         nandfs_daddr_t daddr;
 187         int error;
 188         int num, *nump, i;
 189
 190         DPRINTF(BMAP, ("%s: node %p lblk=%jx vblk=%jx\n", __func__, node, lblk,
 191             vblk));
 192
 193         ip = &node->nn_inode;
 194
 195         ap = a;
 196         nump = &num;
 197
 198         error = bmap_getlbns(node, lblk, ap, nump);
 199         if (error)
 200                 return (error);
 201
 202         DPRINTF(BMAP, ("%s: node %p lblk=%jx vblk=%jx got num=%d\n", __func__,
 203             node, lblk, vblk, num));
 204
 205         if (num == 0) {
 206                 DPRINTF(BMAP, ("%s: node %p lblk=%jx direct block\n", __func__,
 207                     node, lblk));
 208                 ip->i_db[lblk] = vblk;
 209                 return (0);
 210         }
 211
 212         DPRINTF(BMAP, ("%s: node %p lblk=%jx indirect block level %d\n",
 213             __func__, node, lblk, ap->in_off));
 214
 215         if (num == 1) {
 216                 DPRINTF(BMAP, ("%s: node %p lblk=%jx indirect block: inserting "
 217                     "%jx as vblk for indirect block %d\n", __func__, node,
 218                     lblk, vblk, ap->in_off));
 219                 ip->i_ib[ap->in_off] = vblk;
 220                 return (0);
 221         }
 222
 223         bp = NULL;
 224         daddr = ip->i_ib[a[0].in_off];
 225         for (i = 1; i < num; i++) {
 226                 if (bp)
 227                         brelse(bp);
 228                 if (daddr == 0) {
 229                         DPRINTF(BMAP, ("%s: node %p lblk=%jx vblk=%jx create "
 230                             "block %jx %d\n", __func__, node, lblk, vblk,
 231                             a[i].in_lbn, a[i].in_off));
 232                         error = nandfs_bcreate_meta(node, a[i].in_lbn, NOCRED,
 233                             0, &bp);
 234                         if (error)
 235                                 return (error);
 236                 } else {
 237                         DPRINTF(BMAP, ("%s: node %p lblk=%jx vblk=%jx read "
 238                             "block %jx %d\n", __func__, node, daddr, vblk,
 239                             a[i].in_lbn, a[i].in_off));
 240                         error = nandfs_bread_meta(node, a[i].in_lbn, NOCRED, 0, &bp);
 241                         if (error) {
 242                                 brelse(bp);
 243                                 return (error);
 244                         }
 245                 }
 246                 daddr = ((nandfs_daddr_t *)bp->b_data)[a[i].in_off];
 247         }
 248         i--;
 249
 250         DPRINTF(BMAP,
 251             ("%s: bmap node %p lblk=%jx vblk=%jx inserting vblk level %d at "
 252             "offset %d at %jx\n", __func__, node, lblk, vblk, i, a[i].in_off,
 253             daddr));
 254
 255         if (!bp) {
 256                 nandfs_error("%s: cannot find indirect block\n", __func__);
 257                 return (-1);
 258         }
 259         ((nandfs_daddr_t *)bp->b_data)[a[i].in_off] = vblk;
 260
 261         error = nandfs_dirty_buf_meta(bp, 0);
 262         if (error) {
 263                 nandfs_warning("%s: dirty failed buf: %p\n", __func__, bp);
 264                 return (error);
 265         }
 266         DPRINTF(BMAP, ("%s: exiting node %p lblk=%jx vblk=%jx\n", __func__,
 267             node, lblk, vblk));
 268
 269         return (error);
 270 }
 271
 272 CTASSERT(NANDFS_NIADDR <= 3);
 273 #define SINGLE  0       /* index of single indirect block */
 274 #define DOUBLE  1       /* index of double indirect block */
 275 #define TRIPLE  2       /* index of triple indirect block */
 276
 277 static __inline nandfs_lbn_t
 278 lbn_offset(struct nandfs_device *fsdev, int level)
 279 {
 280         nandfs_lbn_t res;
 281
 282         for (res = 1; level > 0; level--)
 283                 res *= MNINDIR(fsdev);
 284         return (res);
 285 }
 286
 287 static nandfs_lbn_t
 288 blocks_inside(struct nandfs_device *fsdev, int level, struct nandfs_indir *nip)
 289 {
 290         nandfs_lbn_t blocks;
 291
 292         for (blocks = 1; level >= SINGLE; level--, nip++) {
 293                 MPASS(nip->in_off >= 0 && nip->in_off < MNINDIR(fsdev));
 294                 blocks += nip->in_off * lbn_offset(fsdev, level);
 295         }
 296
 297         return (blocks);
 298 }
 299
 300 static int
 301 bmap_truncate_indirect(struct nandfs_node *node, int level, nandfs_lbn_t *left,
 302     int *cleaned, struct nandfs_indir *ap, struct nandfs_indir *fp,
 303     nandfs_daddr_t *copy)
 304 {
 305         struct buf *bp;
 306         nandfs_lbn_t i, lbn, nlbn, factor, tosub;
 307         struct nandfs_device *fsdev;
 308         int error, lcleaned, modified;
 309
 310         DPRINTF(BMAP, ("%s: node %p level %d left %jx\n", __func__,
 311             node, level, *left));
 312
 313         fsdev = node->nn_nandfsdev;
 314
 315         MPASS(ap->in_off >= 0 && ap->in_off < MNINDIR(fsdev));
 316
 317         factor = lbn_offset(fsdev, level);
 318         lbn = ap->in_lbn;
 319
 320         error = nandfs_bread_meta(node, lbn, NOCRED, 0, &bp);
 321         if (error) {
 322                 if (bp != NULL)
 323                         brelse(bp);
 324                 return (error);
 325         }
 326
 327         bcopy(bp->b_data, copy, fsdev->nd_blocksize);
 328         bqrelse(bp);
 329
 330         modified = 0;
 331
 332         i = ap->in_off;
 333
 334         if (ap != fp)
 335                 ap++;
 336         for (nlbn = lbn + 1 - i * factor; i >= 0 && *left > 0; i--,
 337             nlbn += factor) {
 338                 lcleaned = 0;
 339
 340                 DPRINTF(BMAP,
 341                     ("%s: node %p i=%jx nlbn=%jx left=%jx ap=%p vblk %jx\n",
 342                     __func__, node, i, nlbn, *left, ap, copy[i]));
 343
 344                 if (copy[i] == 0) {
 345                         tosub = blocks_inside(fsdev, level - 1, ap);
 346                         if (tosub > *left)
 347                                 tosub = 0;
 348
 349                         *left -= tosub;
 350                 } else {
 351                         if (level > SINGLE) {
 352                                 if (ap == fp)
 353                                         ap->in_lbn = nlbn;
 354
 355                                 error = bmap_truncate_indirect(node, level - 1,
 356                                     left, &lcleaned, ap, fp,
 357                                     copy + MNINDIR(fsdev));
 358                                 if (error)
 359                                         return (error);
 360                         } else {
 361                                 error = nandfs_bdestroy(node, copy[i]);
 362                                 if (error)
 363                                         return (error);
 364                                 lcleaned = 1;
 365                                 *left -= 1;
 366                         }
 367                 }
 368
 369                 if (lcleaned) {
 370                         if (level > SINGLE) {
 371                                 error = nandfs_vblock_end(fsdev, copy[i]);
 372                                 if (error)
 373                                         return (error);
 374                         }
 375                         copy[i] = 0;
 376                         modified++;
 377                 }
 378
 379                 ap = fp;
 380         }
 381
 382         if (i == -1)
 383                 *cleaned = 1;
 384
 385         error = nandfs_bread_meta(node, lbn, NOCRED, 0, &bp);
 386         if (error) {
 387                 brelse(bp);
 388                 return (error);
 389         }
 390         if (modified)
 391                 bcopy(copy, bp->b_data, fsdev->nd_blocksize);
 392
 393         /* Force success even if we can't dirty the buffer metadata when freeing space */
 394         nandfs_dirty_buf_meta(bp, 1);
 395
 396         return (0);
 397 }
 398
 399 int
 400 bmap_truncate_mapping(struct nandfs_node *node, nandfs_lbn_t lastblk,
 401     nandfs_lbn_t todo)
 402 {
 403         struct nandfs_inode *ip;
 404         struct nandfs_indir a[NANDFS_NIADDR + 1], f[NANDFS_NIADDR], *ap;
 405         nandfs_daddr_t indir_lbn[NANDFS_NIADDR];
 406         nandfs_daddr_t *copy;
 407         int error, level;
 408         nandfs_lbn_t left, tosub;
 409         struct nandfs_device *fsdev;
 410         int cleaned, i;
 411         int num, *nump;
 412
 413         DPRINTF(BMAP, ("%s: node %p lastblk %jx truncating by %jx\n", __func__,
 414             node, lastblk, todo));
 415
 416         ip = &node->nn_inode;
 417         fsdev = node->nn_nandfsdev;
 418
 419         ap = a;
 420         nump = &num;
 421
 422         error = bmap_getlbns(node, lastblk, ap, nump);
 423         if (error)
 424                 return (error);
 425
 426         indir_lbn[SINGLE] = -NANDFS_NDADDR;
 427         indir_lbn[DOUBLE] = indir_lbn[SINGLE] - MNINDIR(fsdev) - 1;
 428         indir_lbn[TRIPLE] = indir_lbn[DOUBLE] - MNINDIR(fsdev)
 429             * MNINDIR(fsdev) - 1;
 430
 431         for (i = 0; i < NANDFS_NIADDR; i++) {
 432                 f[i].in_off = MNINDIR(fsdev) - 1;
 433                 f[i].in_lbn = 0xdeadbeef;
 434         }
 435
 436         left = todo;
 437
 438 #ifdef DEBUG
 439         a[num].in_off = -1;
 440 #endif
 441
 442         ap++;
 443         num -= 2;
 444
 445         if (num < 0)
 446                 goto direct;
 447
 448         copy = malloc(MNINDIR(fsdev) * sizeof(nandfs_daddr_t) * (num + 1),
 449             M_NANDFSTEMP, M_WAITOK);
 450
 451         for (level = num; level >= SINGLE && left > 0; level--) {
 452                 cleaned = 0;
 453
 454                 if (ip->i_ib[level] == 0) {
 455                         tosub = blocks_inside(fsdev, level, ap);
 456                         if (tosub > left)
 457                                 left = 0;
 458                         else
 459                                 left -= tosub;
 460                 } else {
 461                         if (ap == f)
 462                                 ap->in_lbn = indir_lbn[level];
 463                         error = bmap_truncate_indirect(node, level, &left,
 464                             &cleaned, ap, f, copy);
 465                         if (error) {
 466                                 free(copy, M_NANDFSTEMP);
 467                                 nandfs_error("%s: error %d when truncate "
 468                                     "at level %d\n", __func__, error, level);
 469                                 return (error);
 470                         }
 471                 }
 472
 473                 if (cleaned) {
 474                         nandfs_vblock_end(fsdev, ip->i_ib[level]);
 475                         ip->i_ib[level] = 0;
 476                 }
 477
 478                 ap = f;
 479         }
 480
 481         free(copy, M_NANDFSTEMP);
 482
 483 direct:
 484         if (num < 0)
 485                 i = lastblk;
 486         else
 487                 i = NANDFS_NDADDR - 1;
 488
 489         for (; i >= 0 && left > 0; i--) {
 490                 if (ip->i_db[i] != 0) {
 491                         error = nandfs_bdestroy(node, ip->i_db[i]);
 492                         if (error) {
 493                                 nandfs_error("%s: cannot destroy "
 494                                     "block %jx, error %d\n", __func__,
 495                                     (uintmax_t)ip->i_db[i], error);
 496                                 return (error);
 497                         }
 498                         ip->i_db[i] = 0;
 499                 }
 500
 501                 left--;
 502         }
 503
 504         KASSERT(left == 0,
 505             ("truncated wrong number of blocks (%jd should be 0)", left));
 506
 507         return (error);
 508 }
 509
 510 nandfs_lbn_t
 511 get_maxfilesize(struct nandfs_device *fsdev)
 512 {
 513         struct nandfs_indir f[NANDFS_NIADDR];
 514         nandfs_lbn_t max;
 515         int i;
 516
 517         max = NANDFS_NDADDR;
 518
 519         for (i = 0; i < NANDFS_NIADDR; i++) {
 520                 f[i].in_off = MNINDIR(fsdev) - 1;
 521                 max += blocks_inside(fsdev, i, f);
 522         }
 523
 524         max *= fsdev->nd_blocksize;
 525
 526         return (max);
 527 }
 528
 529 /*
 530  * This is ufs_getlbns with minor modifications.
 531  */
 532 /*
 533  * Create an array of logical block number/offset pairs which represent the
 534  * path of indirect blocks required to access a data block.  The first "pair"
 535  * contains the logical block number of the appropriate single, double or
 536  * triple indirect block and the offset into the inode indirect block array.
 537  * Note, the logical block number of the inode single/double/triple indirect
 538  * block appears twice in the array, once with the offset into the i_ib and
 539  * once with the offset into the page itself.
 540  */
 541 static int
 542 bmap_getlbns(struct nandfs_node *node, nandfs_lbn_t bn, struct nandfs_indir *ap, int *nump)
 543 {
 544         nandfs_daddr_t blockcnt;
 545         nandfs_lbn_t metalbn, realbn;
 546         struct nandfs_device *fsdev;
 547         int i, numlevels, off;
 548
 549         fsdev = node->nn_nandfsdev;
 550
 551         DPRINTF(BMAP, ("%s: node %p bn=%jx mnindir=%zd enter\n", __func__,
 552             node, bn, MNINDIR(fsdev)));
 553
 554         if (nump)
 555                 *nump = 0;
 556         numlevels = 0;
 557         realbn = bn;
 558
 559         if (bn < 0)
 560                 bn = -bn;
 561
 562         /* The first NANDFS_NDADDR blocks are direct blocks. */
 563         if (bn < NANDFS_NDADDR)
 564                 return (0);
 565
 566         /*
 567          * Determine the number of levels of indirection.  After this loop
 568          * is done, blockcnt indicates the number of data blocks possible
 569          * at the previous level of indirection, and NANDFS_NIADDR - i is the
 570          * number of levels of indirection needed to locate the requested block.
 571          */
 572         for (blockcnt = 1, i = NANDFS_NIADDR, bn -= NANDFS_NDADDR;; i--, bn -= blockcnt) {
 573                 DPRINTF(BMAP, ("%s: blockcnt=%jd i=%d bn=%jd\n", __func__,
 574                     blockcnt, i, bn));
 575                 if (i == 0)
 576                         return (EFBIG);
 577                 blockcnt *= MNINDIR(fsdev);
 578                 if (bn < blockcnt)
 579                         break;
 580         }
 581
 582         /* Calculate the address of the first meta-block. */
 583         if (realbn >= 0)
 584                 metalbn = -(realbn - bn + NANDFS_NIADDR - i);
 585         else
 586                 metalbn = -(-realbn - bn + NANDFS_NIADDR - i);
 587
 588         /*
 589          * At each iteration, off is the offset into the bap array which is
 590          * an array of disk addresses at the current level of indirection.
 591          * The logical block number and the offset in that block are stored
 592          * into the argument array.
 593          */
 594         ap->in_lbn = metalbn;
 595         ap->in_off = off = NANDFS_NIADDR - i;
 596
 597         DPRINTF(BMAP, ("%s: initial: ap->in_lbn=%jx ap->in_off=%d\n", __func__,
 598             metalbn, off));
 599
 600         ap++;
 601         for (++numlevels; i <= NANDFS_NIADDR; i++) {
 602                 /* If searching for a meta-data block, quit when found. */
 603                 if (metalbn == realbn)
 604                         break;
 605
 606                 blockcnt /= MNINDIR(fsdev);
 607                 off = (bn / blockcnt) % MNINDIR(fsdev);
 608
 609                 ++numlevels;
 610                 ap->in_lbn = metalbn;
 611                 ap->in_off = off;
 612
 613                 DPRINTF(BMAP, ("%s: in_lbn=%jx in_off=%d\n", __func__,
 614                     ap->in_lbn, ap->in_off));
 615                 ++ap;
 616
 617                 metalbn -= -1 + off * blockcnt;
 618         }
 619         if (nump)
 620                 *nump = numlevels;
 621
 622         DPRINTF(BMAP, ("%s: numlevels=%d\n", __func__, numlevels));
 623
 624         return (0);
 625 }