sys/ufs/ext2fs/ext2fs_rename.c

   1 /*      $NetBSD: ext2fs_rename.c,v 1.8 2015/03/27 17:27:56 riastradh Exp $      */
   2
   3 /*-
   4  * Copyright (c) 2012 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Taylor R Campbell.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*
  33  * Ext2fs Rename
  34  */
  35
  36 #include <sys/cdefs.h>
  37 __KERNEL_RCSID(0, "$NetBSD: ext2fs_rename.c,v 1.8 2015/03/27 17:27:56 riastradh Exp $");
  38
  39 #include <sys/param.h>
  40 #include <sys/buf.h>
  41 #include <sys/errno.h>
  42 #include <sys/kauth.h>
  43 #include <sys/mount.h>
  44 #include <sys/namei.h>
  45 #include <sys/vnode.h>
  46 #include <sys/vnode_if.h>
  47
  48 #include <miscfs/genfs/genfs.h>
  49
  50 #include <ufs/ext2fs/ext2fs.h>
  51 #include <ufs/ext2fs/ext2fs_dir.h>
  52 #include <ufs/ext2fs/ext2fs_extern.h>
  53 #include <ufs/ufs/inode.h>
  54 #include <ufs/ufs/ufs_extern.h>
  55 #include <ufs/ufs/ufsmount.h>
  56
  57 /*
  58  * Forward declarations
  59  */
  60 static int ext2fs_sane_rename(struct vnode *, struct componentname *,
  61     struct vnode *, struct componentname *,
  62     kauth_cred_t, bool);
  63 static bool ext2fs_rename_ulr_overlap_p(const struct ufs_lookup_results *,
  64     const struct ufs_lookup_results *);
  65 static int ext2fs_rename_recalculate_fulr(struct vnode *,
  66     struct ufs_lookup_results *, const struct ufs_lookup_results *,
  67     const struct componentname *);
  68 static bool ext2fs_rmdired_p(struct vnode *);
  69 static int ext2fs_read_dotdot(struct vnode *, kauth_cred_t, ino_t *);
  70 static int ext2fs_rename_replace_dotdot(struct vnode *,
  71     struct vnode *, struct vnode *, kauth_cred_t);
  72 static int ext2fs_gro_lock_directory(struct mount *, struct vnode *);
  73
  74 static const struct genfs_rename_ops ext2fs_genfs_rename_ops;
  75
  76 /*
  77  * ext2fs_sane_rename: The hairiest vop, with the saner API.
  78  *
  79  * Arguments:
  80  *
  81  * . fdvp (from directory vnode),
  82  * . fcnp (from component name),
  83  * . tdvp (to directory vnode),
  84  * . tcnp (to component name),
  85  * . cred (credentials structure), and
  86  * . posixly_correct (flag for behaviour if target & source link same file).
  87  *
  88  * fdvp and tdvp may be the same, and must be referenced and unlocked.
  89  */
  90 static int
  91 ext2fs_sane_rename(
  92     struct vnode *fdvp, struct componentname *fcnp,
  93     struct vnode *tdvp, struct componentname *tcnp,
  94     kauth_cred_t cred, bool posixly_correct)
  95 {
  96         struct ufs_lookup_results fulr, tulr;
  97
  98         return genfs_sane_rename(&ext2fs_genfs_rename_ops,
  99             fdvp, fcnp, &fulr, tdvp, tcnp, &tulr,
 100             cred, posixly_correct);
 101 }
 102
 103 /*
 104  * ext2fs_rename: The hairiest vop, with the insanest API.  Defer to
 105  * genfs_insane_rename immediately.
 106  */
 107 int
 108 ext2fs_rename(void *v)
 109 {
 110
 111         return genfs_insane_rename(v, &ext2fs_sane_rename);
 112 }
 113
 114 /*
 115  * ext2fs_gro_directory_empty_p: Return true if the directory vp is
 116  * empty.  dvp is its parent.
 117  *
 118  * vp and dvp must be locked and referenced.
 119  */
 120 static bool
 121 ext2fs_gro_directory_empty_p(struct mount *mp, kauth_cred_t cred,
 122     struct vnode *vp, struct vnode *dvp)
 123 {
 124
 125         (void)mp;
 126         KASSERT(mp != NULL);
 127         KASSERT(vp != NULL);
 128         KASSERT(dvp != NULL);
 129         KASSERT(vp != dvp);
 130         KASSERT(vp->v_mount == mp);
 131         KASSERT(dvp->v_mount == mp);
 132         KASSERT(VOP_ISLOCKED(vp) == LK_EXCLUSIVE);
 133         KASSERT(VOP_ISLOCKED(dvp) == LK_EXCLUSIVE);
 134
 135         return ext2fs_dirempty(VTOI(vp), VTOI(dvp)->i_number, cred);
 136 }
 137
 138 /*
 139  * ext2fs_gro_rename_check_possible: Check whether a rename is possible
 140  * independent of credentials.
 141  */
 142 static int
 143 ext2fs_gro_rename_check_possible(struct mount *mp,
 144     struct vnode *fdvp, struct vnode *fvp,
 145     struct vnode *tdvp, struct vnode *tvp)
 146 {
 147
 148         (void)mp;
 149         KASSERT(mp != NULL);
 150         KASSERT(fdvp != NULL);
 151         KASSERT(fvp != NULL);
 152         KASSERT(tdvp != NULL);
 153         KASSERT(fdvp != fvp);
 154         KASSERT(fdvp != tvp);
 155         KASSERT(tdvp != fvp);
 156         KASSERT(tdvp != tvp);
 157         KASSERT(fvp != tvp);
 158         KASSERT(fdvp->v_type == VDIR);
 159         KASSERT(tdvp->v_type == VDIR);
 160         KASSERT(fdvp->v_mount == mp);
 161         KASSERT(fvp->v_mount == mp);
 162         KASSERT(tdvp->v_mount == mp);
 163         KASSERT((tvp == NULL) || (tvp->v_mount == mp));
 164         KASSERT(VOP_ISLOCKED(fdvp) == LK_EXCLUSIVE);
 165         KASSERT(VOP_ISLOCKED(fvp) == LK_EXCLUSIVE);
 166         KASSERT(VOP_ISLOCKED(tdvp) == LK_EXCLUSIVE);
 167         KASSERT((tvp == NULL) || (VOP_ISLOCKED(tvp) == LK_EXCLUSIVE));
 168
 169         return genfs_ufslike_rename_check_possible(
 170             VTOI(fdvp)->i_e2fs_flags, VTOI(fvp)->i_e2fs_flags,
 171             VTOI(tdvp)->i_e2fs_flags, (tvp? VTOI(tvp)->i_e2fs_flags : 0),
 172             (tvp != NULL),
 173             EXT2_IMMUTABLE, EXT2_APPEND);
 174 }
 175
 176 /*
 177  * ext2fs_gro_rename_check_permitted: Check whether a rename is
 178  * permitted given our credentials.
 179  */
 180 static int
 181 ext2fs_gro_rename_check_permitted(struct mount *mp, kauth_cred_t cred,
 182     struct vnode *fdvp, struct vnode *fvp,
 183     struct vnode *tdvp, struct vnode *tvp)
 184 {
 185
 186         (void)mp;
 187         KASSERT(mp != NULL);
 188         KASSERT(fdvp != NULL);
 189         KASSERT(fvp != NULL);
 190         KASSERT(tdvp != NULL);
 191         KASSERT(fdvp != fvp);
 192         KASSERT(fdvp != tvp);
 193         KASSERT(tdvp != fvp);
 194         KASSERT(tdvp != tvp);
 195         KASSERT(fvp != tvp);
 196         KASSERT(fdvp->v_type == VDIR);
 197         KASSERT(tdvp->v_type == VDIR);
 198         KASSERT(fdvp->v_mount == mp);
 199         KASSERT(fvp->v_mount == mp);
 200         KASSERT(tdvp->v_mount == mp);
 201         KASSERT((tvp == NULL) || (tvp->v_mount == mp));
 202         KASSERT(VOP_ISLOCKED(fdvp) == LK_EXCLUSIVE);
 203         KASSERT(VOP_ISLOCKED(fvp) == LK_EXCLUSIVE);
 204         KASSERT(VOP_ISLOCKED(tdvp) == LK_EXCLUSIVE);
 205         KASSERT((tvp == NULL) || (VOP_ISLOCKED(tvp) == LK_EXCLUSIVE));
 206
 207         return genfs_ufslike_rename_check_permitted(cred,
 208             fdvp, VTOI(fdvp)->i_e2fs_mode, VTOI(fdvp)->i_uid,
 209             fvp, VTOI(fvp)->i_uid,
 210             tdvp, VTOI(tdvp)->i_e2fs_mode, VTOI(tdvp)->i_uid,
 211             tvp, (tvp? VTOI(tvp)->i_uid : 0));
 212 }
 213
 214 /*
 215  * ext2fs_gro_remove_check_possible: Check whether a remove is possible
 216  * independent of credentials.
 217  */
 218 static int
 219 ext2fs_gro_remove_check_possible(struct mount *mp,
 220     struct vnode *dvp, struct vnode *vp)
 221 {
 222
 223         (void)mp;
 224         KASSERT(mp != NULL);
 225         KASSERT(dvp != NULL);
 226         KASSERT(vp != NULL);
 227         KASSERT(dvp != vp);
 228         KASSERT(dvp->v_type == VDIR);
 229         KASSERT(vp->v_type != VDIR);
 230         KASSERT(dvp->v_mount == mp);
 231         KASSERT(vp->v_mount == mp);
 232         KASSERT(VOP_ISLOCKED(dvp) == LK_EXCLUSIVE);
 233         KASSERT(VOP_ISLOCKED(vp) == LK_EXCLUSIVE);
 234
 235         return genfs_ufslike_remove_check_possible(
 236             VTOI(dvp)->i_e2fs_flags, VTOI(vp)->i_e2fs_flags,
 237             EXT2_IMMUTABLE, EXT2_APPEND);
 238 }
 239
 240 /*
 241  * ext2fs_gro_remove_check_permitted: Check whether a remove is
 242  * permitted given our credentials.
 243  */
 244 static int
 245 ext2fs_gro_remove_check_permitted(struct mount *mp, kauth_cred_t cred,
 246     struct vnode *dvp, struct vnode *vp)
 247 {
 248
 249         (void)mp;
 250         KASSERT(mp != NULL);
 251         KASSERT(dvp != NULL);
 252         KASSERT(vp != NULL);
 253         KASSERT(dvp != vp);
 254         KASSERT(dvp->v_type == VDIR);
 255         KASSERT(vp->v_type != VDIR);
 256         KASSERT(dvp->v_mount == mp);
 257         KASSERT(vp->v_mount == mp);
 258         KASSERT(VOP_ISLOCKED(dvp) == LK_EXCLUSIVE);
 259         KASSERT(VOP_ISLOCKED(vp) == LK_EXCLUSIVE);
 260
 261         return genfs_ufslike_remove_check_permitted(cred,
 262             dvp, VTOI(dvp)->i_e2fs_mode, VTOI(dvp)->i_uid,
 263             vp, VTOI(vp)->i_uid);
 264 }
 265
 266 /*
 267  * ext2fs_gro_rename: Actually perform the rename operation.
 268  */
 269 static int
 270 ext2fs_gro_rename(struct mount *mp, kauth_cred_t cred,
 271     struct vnode *fdvp, struct componentname *fcnp,
 272     void *fde, struct vnode *fvp,
 273     struct vnode *tdvp, struct componentname *tcnp,
 274     void *tde, struct vnode *tvp)
 275 {
 276         struct ufs_lookup_results *fulr = fde;
 277         struct ufs_lookup_results *tulr = tde;
 278         bool directory_p, reparent_p;
 279         int error;
 280
 281         (void)mp;
 282         KASSERT(mp != NULL);
 283         KASSERT(fdvp != NULL);
 284         KASSERT(fcnp != NULL);
 285         KASSERT(fulr != NULL);
 286         KASSERT(fvp != NULL);
 287         KASSERT(tdvp != NULL);
 288         KASSERT(tcnp != NULL);
 289         KASSERT(tulr != NULL);
 290         KASSERT(fulr != tulr);
 291         KASSERT(fdvp != fvp);
 292         KASSERT(fdvp != tvp);
 293         KASSERT(tdvp != fvp);
 294         KASSERT(tdvp != tvp);
 295         KASSERT(fvp != tvp);
 296         KASSERT(fdvp->v_mount == mp);
 297         KASSERT(fvp->v_mount == mp);
 298         KASSERT(tdvp->v_mount == mp);
 299         KASSERT((tvp == NULL) || (tvp->v_mount == mp));
 300         KASSERT(VOP_ISLOCKED(fdvp) == LK_EXCLUSIVE);
 301         KASSERT(VOP_ISLOCKED(fvp) == LK_EXCLUSIVE);
 302         KASSERT(VOP_ISLOCKED(tdvp) == LK_EXCLUSIVE);
 303         KASSERT((tvp == NULL) || (VOP_ISLOCKED(tvp) == LK_EXCLUSIVE));
 304
 305         /*
 306          * We shall need to temporarily bump the link count, so make
 307          * sure there is room to do so.
 308          */
 309         if ((nlink_t)VTOI(fvp)->i_e2fs_nlink >= LINK_MAX)
 310                 return EMLINK;
 311
 312         directory_p = (fvp->v_type == VDIR);
 313         KASSERT(directory_p == ((VTOI(fvp)->i_e2fs_mode & IFMT) == IFDIR));
 314         KASSERT((tvp == NULL) || (directory_p == (tvp->v_type == VDIR)));
 315         KASSERT((tvp == NULL) || (directory_p ==
 316                 ((VTOI(tvp)->i_e2fs_mode & IFMT) == IFDIR)));
 317
 318         reparent_p = (fdvp != tdvp);
 319         KASSERT(reparent_p == (VTOI(fdvp)->i_number != VTOI(tdvp)->i_number));
 320
 321         /*
 322          * Commence hacking of the data on disk.
 323          */
 324
 325         /*
 326          * 1) Bump link count while we're moving stuff
 327          *    around.  If we crash somewhere before
 328          *    completing our work, the link count
 329          *    may be wrong, but correctable.
 330          */
 331
 332         KASSERT((nlink_t)VTOI(fvp)->i_e2fs_nlink < LINK_MAX);
 333         VTOI(fvp)->i_e2fs_nlink++;
 334         VTOI(fvp)->i_flag |= IN_CHANGE;
 335         error = ext2fs_update(fvp, NULL, NULL, UPDATE_WAIT);
 336         if (error)
 337                 goto whymustithurtsomuch;
 338
 339         /*
 340          * 2) If target doesn't exist, link the target
 341          *    to the source and unlink the source.
 342          *    Otherwise, rewrite the target directory
 343          *    entry to reference the source inode and
 344          *    expunge the original entry's existence.
 345          */
 346
 347         if (tvp == NULL) {
 348                 /*
 349                  * Account for ".." in new directory.
 350                  * When source and destination have the same
 351                  * parent we don't fool with the link count.
 352                  */
 353                 if (directory_p && reparent_p) {
 354                         if ((nlink_t)VTOI(tdvp)->i_e2fs_nlink >= LINK_MAX) {
 355                                 error = EMLINK;
 356                                 goto whymustithurtsomuch;
 357                         }
 358                         KASSERT((nlink_t)VTOI(tdvp)->i_e2fs_nlink < LINK_MAX);
 359                         VTOI(tdvp)->i_e2fs_nlink++;
 360                         VTOI(tdvp)->i_flag |= IN_CHANGE;
 361                         error = ext2fs_update(tdvp, NULL, NULL, UPDATE_WAIT);
 362                         if (error) {
 363                                 /*
 364                                  * Link count update didn't take --
 365                                  * back out the in-memory link count.
 366                                  */
 367                                 KASSERT(0 < VTOI(tdvp)->i_e2fs_nlink);
 368                                 VTOI(tdvp)->i_e2fs_nlink--;
 369                                 VTOI(tdvp)->i_flag |= IN_CHANGE;
 370                                 goto whymustithurtsomuch;
 371                         }
 372                 }
 373
 374                 error = ext2fs_direnter(VTOI(fvp), tdvp, tulr, tcnp);
 375                 if (error) {
 376                         if (directory_p && reparent_p) {
 377                                 /*
 378                                  * Directory update didn't take, but
 379                                  * the link count update did -- back
 380                                  * out the in-memory link count and the
 381                                  * on-disk link count.
 382                                  */
 383                                 KASSERT(0 < VTOI(tdvp)->i_e2fs_nlink);
 384                                 VTOI(tdvp)->i_e2fs_nlink--;
 385                                 VTOI(tdvp)->i_flag |= IN_CHANGE;
 386                                 (void)ext2fs_update(tdvp, NULL, NULL,
 387                                     UPDATE_WAIT);
 388                         }
 389                         goto whymustithurtsomuch;
 390                 }
 391         } else {
 392                 if (directory_p)
 393                         /* XXX WTF?  Why purge here?  Why not purge others?  */
 394                         cache_purge(tdvp);
 395
 396                 /*
 397                  * Make the target directory's entry for tcnp point at
 398                  * the source node.
 399                  */
 400                 error = ext2fs_dirrewrite(VTOI(tdvp), tulr, VTOI(fvp), tcnp);
 401                 if (error)
 402                         goto whymustithurtsomuch;
 403
 404                 /*
 405                  * If the source and target are directories, and the
 406                  * target is in the same directory as the source,
 407                  * decrement the link count of the common parent
 408                  * directory, since we are removing the target from
 409                  * that directory.
 410                  */
 411                 if (directory_p && !reparent_p) {
 412                         KASSERT(fdvp == tdvp);
 413                         /* XXX check, don't kassert */
 414                         KASSERT(0 < VTOI(tdvp)->i_e2fs_nlink);
 415                         VTOI(tdvp)->i_e2fs_nlink--;
 416                         VTOI(tdvp)->i_flag |= IN_CHANGE;
 417                 }
 418
 419                 /*
 420                  * Adjust the link count of the target to
 421                  * reflect the dirrewrite above.  If this is
 422                  * a directory it is empty and there are
 423                  * no links to it, so we can squash the inode and
 424                  * any space associated with it.  We disallowed
 425                  * renaming over top of a directory with links to
 426                  * it above, as the remaining link would point to
 427                  * a directory without "." or ".." entries.
 428                  */
 429                 /* XXX check, don't kassert */
 430                 KASSERT(0 < VTOI(tvp)->i_e2fs_nlink);
 431                 VTOI(tvp)->i_e2fs_nlink--;
 432                 if (directory_p) {
 433                         /*
 434                          * XXX The ext2fs_dirempty call earlier does
 435                          * not guarantee anything about nlink.
 436                          */
 437                         if (VTOI(tvp)->i_e2fs_nlink != 1)
 438                                 ufs_dirbad(VTOI(tvp), (doff_t)0,
 439                                     "hard-linked directory");
 440                         VTOI(tvp)->i_e2fs_nlink = 0;
 441                         error = ext2fs_truncate(tvp, (off_t)0, IO_SYNC, cred);
 442 #if 0                   /* XXX This branch was not in ext2fs_rename!  */
 443                         if (error)
 444                                 goto whymustithurtsomuch;
 445 #endif
 446                 }
 447                 /*
 448                  * XXX Why is this here, and not above the preceding
 449                  * conditional?
 450                  */
 451                 VTOI(tvp)->i_flag |= IN_CHANGE;
 452         }
 453
 454         /*
 455          * If the source is a directory with a new parent, the link
 456          * count of the old parent directory must be decremented and
 457          * ".." set to point to the new parent.
 458          */
 459         if (directory_p && reparent_p) {
 460                 error = ext2fs_rename_replace_dotdot(fvp, fdvp, tdvp, cred);
 461                 if (error)
 462                         goto whymustithurtsomuch;
 463
 464                 /* XXX WTF?  Why purge here?  Why not purge others?  */
 465                 cache_purge(fdvp);
 466         }
 467
 468         /*
 469          * 3) Unlink the source.
 470          */
 471
 472         /*
 473          * ext2fs_direnter may compact the directory in the process of
 474          * inserting a new entry.  That may invalidate fulr, which we
 475          * need in order to remove the old entry.  In that case, we
 476          * need to recalculate what fulr should be.
 477          */
 478         if (!reparent_p && (tvp == NULL) &&
 479             ext2fs_rename_ulr_overlap_p(fulr, tulr)) {
 480                 error = ext2fs_rename_recalculate_fulr(fdvp, fulr, tulr, fcnp);
 481 #if 0                           /* XXX */
 482                 if (error)      /* XXX Try to back out changes?  */
 483                         goto whymustithurtsomuch;
 484 #endif
 485         }
 486
 487         error = ext2fs_dirremove(fdvp, fulr, fcnp);
 488         if (error)
 489                 goto whymustithurtsomuch;
 490
 491         /*
 492          * XXX Perhaps this should go at the top, in case the file
 493          * system is modified but incompletely so because of an
 494          * intermediate error.
 495          */
 496         genfs_rename_knote(fdvp, fvp, tdvp, tvp,
 497             ((tvp != NULL) && (VTOI(tvp)->i_e2fs_nlink == 0)));
 498 #if 0                           /* XXX */
 499         genfs_rename_cache_purge(fdvp, fvp, tdvp, tvp);
 500 #endif
 501
 502 whymustithurtsomuch:
 503         KASSERT(0 < VTOI(fvp)->i_e2fs_nlink);
 504         VTOI(fvp)->i_e2fs_nlink--;
 505         VTOI(fvp)->i_flag |= IN_CHANGE;
 506         return error;
 507 }
 508
 509 /*
 510  * ext2fs_rename_ulr_overlap_p: True iff tulr overlaps with fulr so
 511  * that entering a directory entry at tulr may move fulr.
 512  */
 513 static bool
 514 ext2fs_rename_ulr_overlap_p(const struct ufs_lookup_results *fulr,
 515     const struct ufs_lookup_results *tulr)
 516 {
 517         doff_t from_prev_start, from_prev_end, to_start, to_end;
 518
 519         KASSERT(fulr != NULL);
 520         KASSERT(tulr != NULL);
 521         KASSERT(fulr != tulr);
 522
 523         /*
 524          * fulr is from a DELETE lookup, so fulr->ulr_count is the size
 525          * of the preceding entry (d_reclen).
 526          */
 527         from_prev_end = fulr->ulr_offset;
 528         KASSERT(fulr->ulr_count <= from_prev_end);
 529         from_prev_start = (from_prev_end - fulr->ulr_count);
 530
 531         /*
 532          * tulr is from a RENAME lookup, so tulr->ulr_count is the size
 533          * of the free space for an entry that we are about to fill.
 534          */
 535         to_start = tulr->ulr_offset;
 536         KASSERT(tulr->ulr_count < (EXT2FS_MAXDIRSIZE - to_start));
 537         to_end = (to_start + tulr->ulr_count);
 538
 539         return
 540             (((to_start <= from_prev_start) && (from_prev_start < to_end)) ||
 541                 ((to_start <= from_prev_end) && (from_prev_end < to_end)));
 542 }
 543
 544 /*
 545  * ext2fs_rename_recalculate_fulr: If we have just entered a directory
 546  * into dvp at tulr, and we were about to remove one at fulr for an
 547  * entry named fcnp, fulr may be invalid.  So, if necessary,
 548  * recalculate it.
 549  */
 550 static int
 551 ext2fs_rename_recalculate_fulr(struct vnode *dvp,
 552     struct ufs_lookup_results *fulr, const struct ufs_lookup_results *tulr,
 553     const struct componentname *fcnp)
 554 {
 555         struct mount *mp;
 556         struct ufsmount *ump;
 557         /* XXX int is a silly type for this; blame ufsmount::um_dirblksiz.  */
 558         int dirblksiz;
 559         doff_t search_start, search_end;
 560         doff_t offset;          /* Offset of entry we're examining.  */
 561         struct buf *bp;         /* I/O block we're examining.  */
 562         char *dirbuf;           /* Pointer into directory at search_start.  */
 563         struct ext2fs_direct *ep; /* Pointer to the entry we're examining.  */
 564         /* XXX direct::d_reclen is 16-bit;
 565          * ufs_lookup_results::ulr_reclen is 32-bit.  Blah.  */
 566         uint32_t reclen;        /* Length of the entry we're examining.  */
 567         uint32_t prev_reclen;   /* Length of the preceding entry.  */
 568         int error;
 569
 570         KASSERT(dvp != NULL);
 571         KASSERT(dvp->v_mount != NULL);
 572         KASSERT(VTOI(dvp) != NULL);
 573         KASSERT(fulr != NULL);
 574         KASSERT(tulr != NULL);
 575         KASSERT(fulr != tulr);
 576         KASSERT(ext2fs_rename_ulr_overlap_p(fulr, tulr));
 577
 578         mp = dvp->v_mount;
 579         ump = VFSTOUFS(mp);
 580         KASSERT(ump != NULL);
 581         KASSERT(ump == VTOI(dvp)->i_ump);
 582
 583         dirblksiz = ump->um_dirblksiz;
 584         KASSERT(0 < dirblksiz);
 585         KASSERT((dirblksiz & (dirblksiz - 1)) == 0);
 586
 587         /* A directory block may not span across multiple I/O blocks.  */
 588         KASSERT(dirblksiz <= mp->mnt_stat.f_iosize);
 589
 590         /* Find the bounds of the search.  */
 591         search_start = tulr->ulr_offset;
 592         KASSERT(fulr->ulr_reclen < (EXT2FS_MAXDIRSIZE - fulr->ulr_offset));
 593         search_end = (fulr->ulr_offset + fulr->ulr_reclen);
 594
 595         /* Compaction must happen only within a directory block. (*)  */
 596         KASSERT(search_start <= search_end);
 597         KASSERT((search_end - (search_start &~ (dirblksiz - 1))) <= dirblksiz);
 598
 599         dirbuf = NULL;
 600         bp = NULL;
 601         error = ext2fs_blkatoff(dvp, (off_t)search_start, &dirbuf, &bp);
 602         if (error)
 603                 return error;
 604         KASSERT(dirbuf != NULL);
 605         KASSERT(bp != NULL);
 606
 607         /*
 608          * Guarantee we sha'n't go past the end of the buffer we got.
 609          * dirbuf is bp->b_data + (search_start & (iosize - 1)), and
 610          * the valid range is [bp->b_data, bp->b_data + bp->b_bcount).
 611          */
 612         KASSERT((search_end - search_start) <=
 613             (bp->b_bcount - (search_start & (mp->mnt_stat.f_iosize - 1))));
 614
 615         prev_reclen = fulr->ulr_count;
 616         offset = search_start;
 617
 618         /*
 619          * Search from search_start to search_end for the entry matching
 620          * fcnp, which must be there because we found it before and it
 621          * should only at most have moved earlier.
 622          */
 623         for (;;) {
 624                 KASSERT(search_start <= offset);
 625                 KASSERT(offset < search_end);
 626
 627                 /*
 628                  * Examine the directory entry at offset.
 629                  */
 630                 ep = (struct ext2fs_direct *)
 631                     (dirbuf + (offset - search_start));
 632                 reclen = fs2h16(ep->e2d_reclen);
 633
 634                 if (ep->e2d_ino == 0)
 635                         goto next;      /* Entry is unused.  */
 636
 637                 if (fs2h32(ep->e2d_ino) == UFS_WINO)
 638                         goto next;      /* Entry is whiteout.  */
 639
 640                 if (fcnp->cn_namelen != ep->e2d_namlen)
 641                         goto next;      /* Wrong name length.  */
 642
 643                 if (memcmp(ep->e2d_name, fcnp->cn_nameptr, fcnp->cn_namelen))
 644                         goto next;      /* Wrong name.  */
 645
 646                 /* Got it!  */
 647                 break;
 648
 649 next:
 650                 if (! ((reclen < search_end) &&
 651                         (offset < (search_end - reclen)))) {
 652                         brelse(bp, 0);
 653                         return EIO;     /* XXX Panic?  What?  */
 654                 }
 655
 656                 /* We may not move past the search end.  */
 657                 KASSERT(reclen < search_end);
 658                 KASSERT(offset < (search_end - reclen));
 659
 660                 /*
 661                  * We may not move across a directory block boundary;
 662                  * see (*) above.
 663                  */
 664                 KASSERT((offset &~ (dirblksiz - 1)) ==
 665                     ((offset + reclen) &~ (dirblksiz - 1)));
 666
 667                 prev_reclen = reclen;
 668                 offset += reclen;
 669         }
 670
 671         /*
 672          * Found the entry.  Record where.
 673          */
 674         fulr->ulr_offset = offset;
 675         fulr->ulr_reclen = reclen;
 676
 677         /*
 678          * Record the preceding record length, but not if we're at the
 679          * start of a directory block.
 680          */
 681         fulr->ulr_count = ((offset & (dirblksiz - 1))? prev_reclen : 0);
 682
 683         brelse(bp, 0);
 684         return 0;
 685 }
 686
 687 /*
 688  * ext2fs_gro_remove: Rename an object over another link to itself,
 689  * effectively removing just the original link.
 690  */
 691 static int
 692 ext2fs_gro_remove(struct mount *mp, kauth_cred_t cred,
 693     struct vnode *dvp, struct componentname *cnp, void *de, struct vnode *vp)
 694 {
 695         struct ufs_lookup_results *ulr = de;
 696         int error;
 697
 698         (void)mp;
 699         KASSERT(mp != NULL);
 700         KASSERT(dvp != NULL);
 701         KASSERT(cnp != NULL);
 702         KASSERT(ulr != NULL);
 703         KASSERT(vp != NULL);
 704         KASSERT(dvp != vp);
 705         KASSERT(dvp->v_mount == mp);
 706         KASSERT(vp->v_mount == mp);
 707         KASSERT(dvp->v_type == VDIR);
 708         KASSERT(vp->v_type != VDIR);
 709         KASSERT(VOP_ISLOCKED(dvp) == LK_EXCLUSIVE);
 710         KASSERT(VOP_ISLOCKED(vp) == LK_EXCLUSIVE);
 711
 712         error = ext2fs_dirremove(dvp, ulr, cnp);
 713         if (error)
 714                 return error;
 715
 716         KASSERT(0 < VTOI(vp)->i_e2fs_nlink);
 717         VTOI(vp)->i_e2fs_nlink--;
 718         VTOI(vp)->i_flag |= IN_CHANGE;
 719
 720         VN_KNOTE(dvp, NOTE_WRITE);
 721         VN_KNOTE(vp, (VTOI(vp)->i_e2fs_nlink? NOTE_LINK : NOTE_DELETE));
 722
 723         return 0;
 724 }
 725
 726 /*
 727  * ext2fs_gro_lookup: Look up and save the lookup results.
 728  */
 729 static int
 730 ext2fs_gro_lookup(struct mount *mp, struct vnode *dvp,
 731     struct componentname *cnp, void *de_ret, struct vnode **vp_ret)
 732 {
 733         struct ufs_lookup_results *ulr_ret = de_ret;
 734         struct vnode *vp;
 735         int error;
 736
 737         (void)mp;
 738         KASSERT(mp != NULL);
 739         KASSERT(dvp != NULL);
 740         KASSERT(cnp != NULL);
 741         KASSERT(ulr_ret != NULL);
 742         KASSERT(vp_ret != NULL);
 743         KASSERT(VOP_ISLOCKED(dvp) == LK_EXCLUSIVE);
 744
 745         /* Kludge cargo-culted from dholland's ufs_rename.  */
 746         cnp->cn_flags &=~ MODMASK;
 747         cnp->cn_flags |= (LOCKPARENT | LOCKLEAF);
 748
 749         error = relookup(dvp, &vp, cnp, 0 /* dummy */);
 750         if ((error == 0) && (vp == NULL)) {
 751                 error = ENOENT;
 752                 goto out;
 753         } else if (error) {
 754                 return error;
 755         }
 756
 757         /*
 758          * Thanks to VFS insanity, relookup locks vp, which screws us
 759          * in various ways.
 760          */
 761         KASSERT(vp != NULL);
 762         VOP_UNLOCK(vp);
 763
 764 out:    *ulr_ret = VTOI(dvp)->i_crap;
 765         *vp_ret = vp;
 766         return error;
 767 }
 768
 769 /*
 770  * ext2fs_rmdired_p: Check whether the directory vp has been rmdired.
 771  *
 772  * vp must be locked and referenced.
 773  */
 774 static bool
 775 ext2fs_rmdired_p(struct vnode *vp)
 776 {
 777
 778         KASSERT(vp != NULL);
 779         KASSERT(VOP_ISLOCKED(vp) == LK_EXCLUSIVE);
 780         KASSERT(vp->v_type == VDIR);
 781
 782         /* XXX Is this correct?  */
 783         return (ext2fs_size(VTOI(vp)) == 0);
 784 }
 785
 786 /*
 787  * ext2fs_gro_genealogy: Analyze the genealogy of the source and target
 788  * directories.
 789  */
 790 static int
 791 ext2fs_gro_genealogy(struct mount *mp, kauth_cred_t cred,
 792     struct vnode *fdvp, struct vnode *tdvp,
 793     struct vnode **intermediate_node_ret)
 794 {
 795         struct vnode *vp, *dvp;
 796         ino_t dotdot_ino = -1;  /* XXX gcc 4.8.3: maybe-uninitialized */
 797         int error;
 798
 799         KASSERT(mp != NULL);
 800         KASSERT(fdvp != NULL);
 801         KASSERT(tdvp != NULL);
 802         KASSERT(fdvp != tdvp);
 803         KASSERT(intermediate_node_ret != NULL);
 804         KASSERT(fdvp->v_mount == mp);
 805         KASSERT(tdvp->v_mount == mp);
 806         KASSERT(fdvp->v_type == VDIR);
 807         KASSERT(tdvp->v_type == VDIR);
 808
 809         /*
 810          * We need to provisionally lock tdvp to keep rmdir from
 811          * deleting it -- or any ancestor -- at an inopportune moment.
 812          */
 813         error = ext2fs_gro_lock_directory(mp, tdvp);
 814         if (error)
 815                 return error;
 816
 817         vp = tdvp;
 818         vref(vp);
 819
 820         for (;;) {
 821                 KASSERT(vp != NULL);
 822                 KASSERT(VOP_ISLOCKED(vp) == LK_EXCLUSIVE);
 823                 KASSERT(vp->v_mount == mp);
 824                 KASSERT(vp->v_type == VDIR);
 825                 KASSERT(!ext2fs_rmdired_p(vp));
 826
 827                 /* Did we hit the root without finding fdvp?  */
 828                 if (VTOI(vp)->i_number == UFS_ROOTINO) {
 829                         vput(vp);
 830                         *intermediate_node_ret = NULL;
 831                         return 0;
 832                 }
 833
 834                 error = ext2fs_read_dotdot(vp, cred, &dotdot_ino);
 835                 if (error) {
 836                         vput(vp);
 837                         return error;
 838                 }
 839
 840                 /* Did we find that fdvp is an ancestor of tdvp?  */
 841                 if (VTOI(fdvp)->i_number == dotdot_ino) {
 842                         /* Unlock vp, but keep it referenced.  */
 843                         VOP_UNLOCK(vp);
 844                         *intermediate_node_ret = vp;
 845                         return 0;
 846                 }
 847
 848                 /* Neither -- keep ascending the family tree.  */
 849                 error = vcache_get(mp, &dotdot_ino, sizeof(dotdot_ino), &dvp);
 850                 vput(vp);
 851                 if (error)
 852                         return error;
 853                 error = vn_lock(dvp, LK_EXCLUSIVE);
 854                 if (error) {
 855                         vrele(dvp);
 856                         return error;
 857                 }
 858
 859                 KASSERT(dvp != NULL);
 860                 KASSERT(VOP_ISLOCKED(dvp) == LK_EXCLUSIVE);
 861                 vp = dvp;
 862
 863                 if (vp->v_type != VDIR) {
 864                         /*
 865                          * XXX Panic?  Print a warning?  Can this
 866                          * happen if we lose the race I suspect to
 867                          * exist above, and the `..' inode number has
 868                          * been recycled?
 869                          */
 870                         vput(vp);
 871                         return ENOTDIR;
 872                 }
 873
 874                 if (ext2fs_rmdired_p(vp)) {
 875                         vput(vp);
 876                         return ENOENT;
 877                 }
 878         }
 879 }
 880
 881 /*
 882  * ext2fs_read_dotdot: Store in *ino_ret the inode number of the parent
 883  * of the directory vp.
 884  */
 885 static int
 886 ext2fs_read_dotdot(struct vnode *vp, kauth_cred_t cred, ino_t *ino_ret)
 887 {
 888         struct ext2fs_dirtemplate dirbuf;
 889         int error;
 890
 891         KASSERT(vp != NULL);
 892         KASSERT(ino_ret != NULL);
 893         KASSERT(vp->v_type == VDIR);
 894
 895         error = ufs_bufio(UIO_READ, vp, &dirbuf, sizeof dirbuf, (off_t)0,
 896             IO_NODELOCKED, cred, NULL, NULL);
 897         if (error)
 898                 return error;
 899
 900         if (dirbuf.dotdot_namlen != 2 ||
 901             dirbuf.dotdot_name[0] != '.' ||
 902             dirbuf.dotdot_name[1] != '.')
 903                 /* XXX Panic?  Print warning?  */
 904                 return ENOTDIR;
 905
 906         *ino_ret = fs2h32(dirbuf.dotdot_ino);
 907         return 0;
 908 }
 909
 910 /*
 911  * ext2fs_rename_replace_dotdot: Change the target of the `..' entry of
 912  * the directory vp from fdvp to tdvp.
 913  */
 914 static int
 915 ext2fs_rename_replace_dotdot(struct vnode *vp,
 916     struct vnode *fdvp, struct vnode *tdvp,
 917     kauth_cred_t cred)
 918 {
 919         struct ext2fs_dirtemplate dirbuf;
 920         int error;
 921
 922         /* XXX Does it make sense to do this before the sanity checks below?  */
 923         KASSERT(0 < VTOI(fdvp)->i_e2fs_nlink);
 924         VTOI(fdvp)->i_e2fs_nlink--;
 925         VTOI(fdvp)->i_flag |= IN_CHANGE;
 926
 927         error = ufs_bufio(UIO_READ, vp, &dirbuf, sizeof dirbuf, (off_t)0,
 928             IO_NODELOCKED, cred, NULL, NULL);
 929         if (error)
 930                 return error;
 931
 932         if (dirbuf.dotdot_namlen != 2 ||
 933             dirbuf.dotdot_name[0] != '.' ||
 934             dirbuf.dotdot_name[1] != '.') {
 935                 ufs_dirbad(VTOI(vp), (doff_t)12, "bad `..' entry");
 936                 return 0;
 937         }
 938
 939         if (fs2h32(dirbuf.dotdot_ino) != VTOI(fdvp)->i_number) {
 940                 ufs_dirbad(VTOI(vp), (doff_t)12,
 941                     "`..' does not point at parent");
 942                 return 0;
 943         }
 944
 945         dirbuf.dotdot_ino = h2fs32(VTOI(tdvp)->i_number);
 946         /* XXX WTF?  Why not check error?  */
 947         (void)ufs_bufio(UIO_WRITE, vp, &dirbuf, sizeof dirbuf, (off_t)0,
 948             (IO_NODELOCKED | IO_SYNC), cred, NULL, NULL);
 949
 950         return 0;
 951 }
 952
 953 /*
 954  * ext2fs_gro_lock_directory: Lock the directory vp, but fail if it has
 955  * been rmdir'd.
 956  */
 957 static int
 958 ext2fs_gro_lock_directory(struct mount *mp, struct vnode *vp)
 959 {
 960
 961         (void)mp;
 962         KASSERT(mp != NULL);
 963         KASSERT(vp != NULL);
 964         KASSERT(vp->v_mount == mp);
 965
 966         vn_lock(vp, LK_EXCLUSIVE | LK_RETRY);
 967
 968         if (ext2fs_rmdired_p(vp)) {
 969                 VOP_UNLOCK(vp);
 970                 return ENOENT;
 971         }
 972
 973         return 0;
 974 }
 975
 976 static const struct genfs_rename_ops ext2fs_genfs_rename_ops = {
 977         .gro_directory_empty_p          = ext2fs_gro_directory_empty_p,
 978         .gro_rename_check_possible      = ext2fs_gro_rename_check_possible,
 979         .gro_rename_check_permitted     = ext2fs_gro_rename_check_permitted,
 980         .gro_remove_check_possible      = ext2fs_gro_remove_check_possible,
 981         .gro_remove_check_permitted     = ext2fs_gro_remove_check_permitted,
 982         .gro_rename                     = ext2fs_gro_rename,
 983         .gro_remove                     = ext2fs_gro_remove,
 984         .gro_lookup                     = ext2fs_gro_lookup,
 985         .gro_genealogy                  = ext2fs_gro_genealogy,
 986         .gro_lock_directory             = ext2fs_gro_lock_directory,
 987 };