1 /*- 2 * Copyright 1998, 2000 Marshall Kirk McKusick. All Rights Reserved. 3 * 4 * The soft updates code is derived from the appendix of a University 5 * of Michigan technical report (Gregory R. Ganger and Yale N. Patt, 6 * "Soft Updates: A Solution to the Metadata Update Problem in File 7 * Systems", CSE-TR-254-95, August 1995). 8 * 9 * Further information about soft updates can be obtained from: 10 * 11 * Marshall Kirk McKusick http://www.mckusick.com/softdep/ 12 * 1614 Oxford Street mckusick@mckusick.com 13 * Berkeley, CA 94709-1608 +1-510-843-9542 14 * USA 15 * 16 * Redistribution and use in source and binary forms, with or without 17 * modification, are permitted provided that the following conditions 18 * are met: 19 * 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 26 * THIS SOFTWARE IS PROVIDED BY MARSHALL KIRK MCKUSICK ``AS IS'' AND ANY 27 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 28 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 29 * DISCLAIMED. IN NO EVENT SHALL MARSHALL KIRK MCKUSICK BE LIABLE FOR 30 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 * 38 * @(#)softdep.h 9.7 (McKusick) 6/21/00 39 * $FreeBSD$ 40 */ 41 42 #include <sys/queue.h> 43 44 /* 45 * Allocation dependencies are handled with undo/redo on the in-memory 46 * copy of the data. A particular data dependency is eliminated when 47 * it is ALLCOMPLETE: that is ATTACHED, DEPCOMPLETE, and COMPLETE. 48 * 49 * ATTACHED means that the data is not currently being written to 50 * disk. UNDONE means that the data has been rolled back to a safe 51 * state for writing to the disk. When the I/O completes, the data is 52 * restored to its current form and the state reverts to ATTACHED. 53 * The data must be locked throughout the rollback, I/O, and roll 54 * forward so that the rolled back information is never visible to 55 * user processes. The COMPLETE flag indicates that the item has been 56 * written. For example, a dependency that requires that an inode be 57 * written will be marked COMPLETE after the inode has been written 58 * to disk. The DEPCOMPLETE flag indicates the completion of any other 59 * dependencies such as the writing of a cylinder group map has been 60 * completed. A dependency structure may be freed only when both it 61 * and its dependencies have completed and any rollbacks that are in 62 * progress have finished as indicated by the set of ALLCOMPLETE flags 63 * all being set. The two MKDIR flags indicate additional dependencies 64 * that must be done when creating a new directory. MKDIR_BODY is 65 * cleared when the directory data block containing the "." and ".." 66 * entries has been written. MKDIR_PARENT is cleared when the parent 67 * inode with the increased link count for ".." has been written. When 68 * both MKDIR flags have been cleared, the DEPCOMPLETE flag is set to 69 * indicate that the directory dependencies have been completed. The 70 * writing of the directory inode itself sets the COMPLETE flag which 71 * then allows the directory entry for the new directory to be written 72 * to disk. The RMDIR flag marks a dirrem structure as representing 73 * the removal of a directory rather than a file. When the removal 74 * dependencies are completed, additional work needs to be done 75 * (truncation of the "." and ".." entries, an additional decrement 76 * of the associated inode, and a decrement of the parent inode). The 77 * DIRCHG flag marks a diradd structure as representing the changing 78 * of an existing entry rather than the addition of a new one. When 79 * the update is complete the dirrem associated with the inode for 80 * the old name must be added to the worklist to do the necessary 81 * reference count decrement. The GOINGAWAY flag indicates that the 82 * data structure is frozen from further change until its dependencies 83 * have been completed and its resources freed after which it will be 84 * discarded. The IOSTARTED flag prevents multiple calls to the I/O 85 * start routine from doing multiple rollbacks. The SPACECOUNTED flag 86 * says that the files space has been accounted to the pending free 87 * space count. The NEWBLOCK flag marks pagedep structures that have 88 * just been allocated, so must be claimed by the inode before all 89 * dependencies are complete. The INPROGRESS flag marks worklist 90 * structures that are still on the worklist, but are being considered 91 * for action by some process. The UFS1FMT flag indicates that the 92 * inode being processed is a ufs1 format. The EXTDATA flag indicates 93 * that the allocdirect describes an extended-attributes dependency. 94 * The ONWORKLIST flag shows whether the structure is currently linked 95 * onto a worklist. 96 */ 97 #define ATTACHED 0x0001 98 #define UNDONE 0x0002 99 #define COMPLETE 0x0004 100 #define DEPCOMPLETE 0x0008 101 #define MKDIR_PARENT 0x0010 /* diradd & mkdir only */ 102 #define MKDIR_BODY 0x0020 /* diradd & mkdir only */ 103 #define RMDIR 0x0040 /* dirrem only */ 104 #define DIRCHG 0x0080 /* diradd & dirrem only */ 105 #define GOINGAWAY 0x0100 /* indirdep only */ 106 #define IOSTARTED 0x0200 /* inodedep & pagedep only */ 107 #define SPACECOUNTED 0x0400 /* inodedep only */ 108 #define NEWBLOCK 0x0800 /* pagedep only */ 109 #define INPROGRESS 0x1000 /* dirrem, freeblks, freefrag, freefile only */ 110 #define UFS1FMT 0x2000 /* indirdep only */ 111 #define EXTDATA 0x4000 /* allocdirect only */ 112 #define ONWORKLIST 0x8000 113 114 #define ALLCOMPLETE (ATTACHED | COMPLETE | DEPCOMPLETE) 115 116 /* 117 * The workitem queue. 118 * 119 * It is sometimes useful and/or necessary to clean up certain dependencies 120 * in the background rather than during execution of an application process 121 * or interrupt service routine. To realize this, we append dependency 122 * structures corresponding to such tasks to a "workitem" queue. In a soft 123 * updates implementation, most pending workitems should not wait for more 124 * than a couple of seconds, so the filesystem syncer process awakens once 125 * per second to process the items on the queue. 126 */ 127 128 /* LIST_HEAD(workhead, worklist); -- declared in buf.h */ 129 130 /* 131 * Each request can be linked onto a work queue through its worklist structure. 132 * To avoid the need for a pointer to the structure itself, this structure 133 * MUST be declared FIRST in each type in which it appears! If more than one 134 * worklist is needed in the structure, then a wk_data field must be added 135 * and the macros below changed to use it. 136 */ 137 struct worklist { 138 struct mount *wk_mp; /* Mount we live in */ 139 LIST_ENTRY(worklist) wk_list; /* list of work requests */ 140 unsigned short wk_type; /* type of request */ 141 unsigned short wk_state; /* state flags */ 142 }; 143 #define WK_DATA(wk) ((void *)(wk)) 144 #define WK_PAGEDEP(wk) ((struct pagedep *)(wk)) 145 #define WK_INODEDEP(wk) ((struct inodedep *)(wk)) 146 #define WK_BMSAFEMAP(wk) ((struct bmsafemap *)(wk)) 147 #define WK_ALLOCDIRECT(wk) ((struct allocdirect *)(wk)) 148 #define WK_INDIRDEP(wk) ((struct indirdep *)(wk)) 149 #define WK_ALLOCINDIR(wk) ((struct allocindir *)(wk)) 150 #define WK_FREEFRAG(wk) ((struct freefrag *)(wk)) 151 #define WK_FREEBLKS(wk) ((struct freeblks *)(wk)) 152 #define WK_FREEFILE(wk) ((struct freefile *)(wk)) 153 #define WK_DIRADD(wk) ((struct diradd *)(wk)) 154 #define WK_MKDIR(wk) ((struct mkdir *)(wk)) 155 #define WK_DIRREM(wk) ((struct dirrem *)(wk)) 156 #define WK_NEWDIRBLK(wk) ((struct newdirblk *)(wk)) 157 158 /* 159 * Various types of lists 160 */ 161 LIST_HEAD(dirremhd, dirrem); 162 LIST_HEAD(diraddhd, diradd); 163 LIST_HEAD(newblkhd, newblk); 164 LIST_HEAD(inodedephd, inodedep); 165 LIST_HEAD(allocindirhd, allocindir); 166 LIST_HEAD(allocdirecthd, allocdirect); 167 TAILQ_HEAD(allocdirectlst, allocdirect); 168 169 /* 170 * The "pagedep" structure tracks the various dependencies related to 171 * a particular directory page. If a directory page has any dependencies, 172 * it will have a pagedep linked to its associated buffer. The 173 * pd_dirremhd list holds the list of dirrem requests which decrement 174 * inode reference counts. These requests are processed after the 175 * directory page with the corresponding zero'ed entries has been 176 * written. The pd_diraddhd list maintains the list of diradd requests 177 * which cannot be committed until their corresponding inode has been 178 * written to disk. Because a directory may have many new entries 179 * being created, several lists are maintained hashed on bits of the 180 * offset of the entry into the directory page to keep the lists from 181 * getting too long. Once a new directory entry has been cleared to 182 * be written, it is moved to the pd_pendinghd list. After the new 183 * entry has been written to disk it is removed from the pd_pendinghd 184 * list, any removed operations are done, and the dependency structure 185 * is freed. 186 */ 187 #define DAHASHSZ 5 188 #define DIRADDHASH(offset) (((offset) >> 2) % DAHASHSZ) 189 struct pagedep { 190 struct worklist pd_list; /* page buffer */ 191 # define pd_state pd_list.wk_state /* check for multiple I/O starts */ 192 LIST_ENTRY(pagedep) pd_hash; /* hashed lookup */ 193 ino_t pd_ino; /* associated file */ 194 ufs_lbn_t pd_lbn; /* block within file */ 195 struct dirremhd pd_dirremhd; /* dirrem's waiting for page */ 196 struct diraddhd pd_diraddhd[DAHASHSZ]; /* diradd dir entry updates */ 197 struct diraddhd pd_pendinghd; /* directory entries awaiting write */ 198 }; 199 200 /* 201 * The "inodedep" structure tracks the set of dependencies associated 202 * with an inode. One task that it must manage is delayed operations 203 * (i.e., work requests that must be held until the inodedep's associated 204 * inode has been written to disk). Getting an inode from its incore 205 * state to the disk requires two steps to be taken by the filesystem 206 * in this order: first the inode must be copied to its disk buffer by 207 * the VOP_UPDATE operation; second the inode's buffer must be written 208 * to disk. To ensure that both operations have happened in the required 209 * order, the inodedep maintains two lists. Delayed operations are 210 * placed on the id_inowait list. When the VOP_UPDATE is done, all 211 * operations on the id_inowait list are moved to the id_bufwait list. 212 * When the buffer is written, the items on the id_bufwait list can be 213 * safely moved to the work queue to be processed. A second task of the 214 * inodedep structure is to track the status of block allocation within 215 * the inode. Each block that is allocated is represented by an 216 * "allocdirect" structure (see below). It is linked onto the id_newinoupdt 217 * list until both its contents and its allocation in the cylinder 218 * group map have been written to disk. Once these dependencies have been 219 * satisfied, it is removed from the id_newinoupdt list and any followup 220 * actions such as releasing the previous block or fragment are placed 221 * on the id_inowait list. When an inode is updated (a VOP_UPDATE is 222 * done), the "inodedep" structure is linked onto the buffer through 223 * its worklist. Thus, it will be notified when the buffer is about 224 * to be written and when it is done. At the update time, all the 225 * elements on the id_newinoupdt list are moved to the id_inoupdt list 226 * since those changes are now relevant to the copy of the inode in the 227 * buffer. Also at update time, the tasks on the id_inowait list are 228 * moved to the id_bufwait list so that they will be executed when 229 * the updated inode has been written to disk. When the buffer containing 230 * the inode is written to disk, any updates listed on the id_inoupdt 231 * list are rolled back as they are not yet safe. Following the write, 232 * the changes are once again rolled forward and any actions on the 233 * id_bufwait list are processed (since those actions are now safe). 234 * The entries on the id_inoupdt and id_newinoupdt lists must be kept 235 * sorted by logical block number to speed the calculation of the size 236 * of the rolled back inode (see explanation in initiate_write_inodeblock). 237 * When a directory entry is created, it is represented by a diradd. 238 * The diradd is added to the id_inowait list as it cannot be safely 239 * written to disk until the inode that it represents is on disk. After 240 * the inode is written, the id_bufwait list is processed and the diradd 241 * entries are moved to the id_pendinghd list where they remain until 242 * the directory block containing the name has been written to disk. 243 * The purpose of keeping the entries on the id_pendinghd list is so that 244 * the softdep_fsync function can find and push the inode's directory 245 * name(s) as part of the fsync operation for that file. 246 */ 247 struct inodedep { 248 struct worklist id_list; /* buffer holding inode block */ 249 # define id_state id_list.wk_state /* inode dependency state */ 250 LIST_ENTRY(inodedep) id_hash; /* hashed lookup */ 251 struct fs *id_fs; /* associated filesystem */ 252 ino_t id_ino; /* dependent inode */ 253 nlink_t id_nlinkdelta; /* saved effective link count */ 254 LIST_ENTRY(inodedep) id_deps; /* bmsafemap's list of inodedep's */ 255 struct buf *id_buf; /* related bmsafemap (if pending) */ 256 long id_savedextsize; /* ext size saved during rollback */ 257 off_t id_savedsize; /* file size saved during rollback */ 258 struct workhead id_pendinghd; /* entries awaiting directory write */ 259 struct workhead id_bufwait; /* operations after inode written */ 260 struct workhead id_inowait; /* operations waiting inode update */ 261 struct allocdirectlst id_inoupdt; /* updates before inode written */ 262 struct allocdirectlst id_newinoupdt; /* updates when inode written */ 263 struct allocdirectlst id_extupdt; /* extdata updates pre-inode write */ 264 struct allocdirectlst id_newextupdt; /* extdata updates at ino write */ 265 union { 266 struct ufs1_dinode *idu_savedino1; /* saved ufs1_dinode contents */ 267 struct ufs2_dinode *idu_savedino2; /* saved ufs2_dinode contents */ 268 } id_un; 269 }; 270 #define id_savedino1 id_un.idu_savedino1 271 #define id_savedino2 id_un.idu_savedino2 272 273 /* 274 * A "newblk" structure is attached to a bmsafemap structure when a block 275 * or fragment is allocated from a cylinder group. Its state is set to 276 * DEPCOMPLETE when its cylinder group map is written. It is consumed by 277 * an associated allocdirect or allocindir allocation which will attach 278 * themselves to the bmsafemap structure if the newblk's DEPCOMPLETE flag 279 * is not set (i.e., its cylinder group map has not been written). 280 */ 281 struct newblk { 282 LIST_ENTRY(newblk) nb_hash; /* hashed lookup */ 283 struct fs *nb_fs; /* associated filesystem */ 284 int nb_state; /* state of bitmap dependency */ 285 ufs2_daddr_t nb_newblkno; /* allocated block number */ 286 LIST_ENTRY(newblk) nb_deps; /* bmsafemap's list of newblk's */ 287 struct bmsafemap *nb_bmsafemap; /* associated bmsafemap */ 288 }; 289 290 /* 291 * A "bmsafemap" structure maintains a list of dependency structures 292 * that depend on the update of a particular cylinder group map. 293 * It has lists for newblks, allocdirects, allocindirs, and inodedeps. 294 * It is attached to the buffer of a cylinder group block when any of 295 * these things are allocated from the cylinder group. It is freed 296 * after the cylinder group map is written and the state of its 297 * dependencies are updated with DEPCOMPLETE to indicate that it has 298 * been processed. 299 */ 300 struct bmsafemap { 301 struct worklist sm_list; /* cylgrp buffer */ 302 struct buf *sm_buf; /* associated buffer */ 303 struct allocdirecthd sm_allocdirecthd; /* allocdirect deps */ 304 struct allocindirhd sm_allocindirhd; /* allocindir deps */ 305 struct inodedephd sm_inodedephd; /* inodedep deps */ 306 struct newblkhd sm_newblkhd; /* newblk deps */ 307 }; 308 309 /* 310 * An "allocdirect" structure is attached to an "inodedep" when a new block 311 * or fragment is allocated and pointed to by the inode described by 312 * "inodedep". The worklist is linked to the buffer that holds the block. 313 * When the block is first allocated, it is linked to the bmsafemap 314 * structure associated with the buffer holding the cylinder group map 315 * from which it was allocated. When the cylinder group map is written 316 * to disk, ad_state has the DEPCOMPLETE flag set. When the block itself 317 * is written, the COMPLETE flag is set. Once both the cylinder group map 318 * and the data itself have been written, it is safe to write the inode 319 * that claims the block. If there was a previous fragment that had been 320 * allocated before the file was increased in size, the old fragment may 321 * be freed once the inode claiming the new block is written to disk. 322 * This ad_fragfree request is attached to the id_inowait list of the 323 * associated inodedep (pointed to by ad_inodedep) for processing after 324 * the inode is written. When a block is allocated to a directory, an 325 * fsync of a file whose name is within that block must ensure not only 326 * that the block containing the file name has been written, but also 327 * that the on-disk inode references that block. When a new directory 328 * block is created, we allocate a newdirblk structure which is linked 329 * to the associated allocdirect (on its ad_newdirblk list). When the 330 * allocdirect has been satisfied, the newdirblk structure is moved to 331 * the inodedep id_bufwait list of its directory to await the inode 332 * being written. When the inode is written, the directory entries are 333 * fully committed and can be deleted from their pagedep->id_pendinghd 334 * and inodedep->id_pendinghd lists. 335 */ 336 struct allocdirect { 337 struct worklist ad_list; /* buffer holding block */ 338 # define ad_state ad_list.wk_state /* block pointer state */ 339 TAILQ_ENTRY(allocdirect) ad_next; /* inodedep's list of allocdirect's */ 340 ufs_lbn_t ad_lbn; /* block within file */ 341 ufs2_daddr_t ad_newblkno; /* new value of block pointer */ 342 ufs2_daddr_t ad_oldblkno; /* old value of block pointer */ 343 long ad_newsize; /* size of new block */ 344 long ad_oldsize; /* size of old block */ 345 LIST_ENTRY(allocdirect) ad_deps; /* bmsafemap's list of allocdirect's */ 346 struct buf *ad_buf; /* cylgrp buffer (if pending) */ 347 struct inodedep *ad_inodedep; /* associated inodedep */ 348 struct freefrag *ad_freefrag; /* fragment to be freed (if any) */ 349 struct workhead ad_newdirblk; /* dir block to notify when written */ 350 }; 351 352 /* 353 * A single "indirdep" structure manages all allocation dependencies for 354 * pointers in an indirect block. The up-to-date state of the indirect 355 * block is stored in ir_savedata. The set of pointers that may be safely 356 * written to the disk is stored in ir_safecopy. The state field is used 357 * only to track whether the buffer is currently being written (in which 358 * case it is not safe to update ir_safecopy). Ir_deplisthd contains the 359 * list of allocindir structures, one for each block that needs to be 360 * written to disk. Once the block and its bitmap allocation have been 361 * written the safecopy can be updated to reflect the allocation and the 362 * allocindir structure freed. If ir_state indicates that an I/O on the 363 * indirect block is in progress when ir_safecopy is to be updated, the 364 * update is deferred by placing the allocindir on the ir_donehd list. 365 * When the I/O on the indirect block completes, the entries on the 366 * ir_donehd list are processed by updating their corresponding ir_safecopy 367 * pointers and then freeing the allocindir structure. 368 */ 369 struct indirdep { 370 struct worklist ir_list; /* buffer holding indirect block */ 371 # define ir_state ir_list.wk_state /* indirect block pointer state */ 372 caddr_t ir_saveddata; /* buffer cache contents */ 373 struct buf *ir_savebp; /* buffer holding safe copy */ 374 struct allocindirhd ir_donehd; /* done waiting to update safecopy */ 375 struct allocindirhd ir_deplisthd; /* allocindir deps for this block */ 376 }; 377 378 /* 379 * An "allocindir" structure is attached to an "indirdep" when a new block 380 * is allocated and pointed to by the indirect block described by the 381 * "indirdep". The worklist is linked to the buffer that holds the new block. 382 * When the block is first allocated, it is linked to the bmsafemap 383 * structure associated with the buffer holding the cylinder group map 384 * from which it was allocated. When the cylinder group map is written 385 * to disk, ai_state has the DEPCOMPLETE flag set. When the block itself 386 * is written, the COMPLETE flag is set. Once both the cylinder group map 387 * and the data itself have been written, it is safe to write the entry in 388 * the indirect block that claims the block; the "allocindir" dependency 389 * can then be freed as it is no longer applicable. 390 */ 391 struct allocindir { 392 struct worklist ai_list; /* buffer holding indirect block */ 393 # define ai_state ai_list.wk_state /* indirect block pointer state */ 394 LIST_ENTRY(allocindir) ai_next; /* indirdep's list of allocindir's */ 395 int ai_offset; /* pointer offset in indirect block */ 396 ufs2_daddr_t ai_newblkno; /* new block pointer value */ 397 ufs2_daddr_t ai_oldblkno; /* old block pointer value */ 398 struct freefrag *ai_freefrag; /* block to be freed when complete */ 399 struct indirdep *ai_indirdep; /* address of associated indirdep */ 400 LIST_ENTRY(allocindir) ai_deps; /* bmsafemap's list of allocindir's */ 401 struct buf *ai_buf; /* cylgrp buffer (if pending) */ 402 }; 403 404 /* 405 * A "freefrag" structure is attached to an "inodedep" when a previously 406 * allocated fragment is replaced with a larger fragment, rather than extended. 407 * The "freefrag" structure is constructed and attached when the replacement 408 * block is first allocated. It is processed after the inode claiming the 409 * bigger block that replaces it has been written to disk. Note that the 410 * ff_state field is is used to store the uid, so may lose data. However, 411 * the uid is used only in printing an error message, so is not critical. 412 * Keeping it in a short keeps the data structure down to 32 bytes. 413 */ 414 struct freefrag { 415 struct worklist ff_list; /* id_inowait or delayed worklist */ 416 # define ff_state ff_list.wk_state /* owning user; should be uid_t */ 417 ufs2_daddr_t ff_blkno; /* fragment physical block number */ 418 long ff_fragsize; /* size of fragment being deleted */ 419 ino_t ff_inum; /* owning inode number */ 420 }; 421 422 /* 423 * A "freeblks" structure is attached to an "inodedep" when the 424 * corresponding file's length is reduced to zero. It records all 425 * the information needed to free the blocks of a file after its 426 * zero'ed inode has been written to disk. 427 */ 428 struct freeblks { 429 struct worklist fb_list; /* id_inowait or delayed worklist */ 430 # define fb_state fb_list.wk_state /* inode and dirty block state */ 431 ino_t fb_previousinum; /* inode of previous owner of blocks */ 432 uid_t fb_uid; /* uid of previous owner of blocks */ 433 struct vnode *fb_devvp; /* filesystem device vnode */ 434 long fb_oldextsize; /* previous ext data size */ 435 off_t fb_oldsize; /* previous file size */ 436 ufs2_daddr_t fb_chkcnt; /* used to check cnt of blks released */ 437 ufs2_daddr_t fb_dblks[NDADDR]; /* direct blk ptrs to deallocate */ 438 ufs2_daddr_t fb_iblks[NIADDR]; /* indirect blk ptrs to deallocate */ 439 ufs2_daddr_t fb_eblks[NXADDR]; /* indirect blk ptrs to deallocate */ 440 }; 441 442 /* 443 * A "freefile" structure is attached to an inode when its 444 * link count is reduced to zero. It marks the inode as free in 445 * the cylinder group map after the zero'ed inode has been written 446 * to disk and any associated blocks and fragments have been freed. 447 */ 448 struct freefile { 449 struct worklist fx_list; /* id_inowait or delayed worklist */ 450 mode_t fx_mode; /* mode of inode */ 451 ino_t fx_oldinum; /* inum of the unlinked file */ 452 struct vnode *fx_devvp; /* filesystem device vnode */ 453 }; 454 455 /* 456 * A "diradd" structure is linked to an "inodedep" id_inowait list when a 457 * new directory entry is allocated that references the inode described 458 * by "inodedep". When the inode itself is written (either the initial 459 * allocation for new inodes or with the increased link count for 460 * existing inodes), the COMPLETE flag is set in da_state. If the entry 461 * is for a newly allocated inode, the "inodedep" structure is associated 462 * with a bmsafemap which prevents the inode from being written to disk 463 * until the cylinder group has been updated. Thus the da_state COMPLETE 464 * flag cannot be set until the inode bitmap dependency has been removed. 465 * When creating a new file, it is safe to write the directory entry that 466 * claims the inode once the referenced inode has been written. Since 467 * writing the inode clears the bitmap dependencies, the DEPCOMPLETE flag 468 * in the diradd can be set unconditionally when creating a file. When 469 * creating a directory, there are two additional dependencies described by 470 * mkdir structures (see their description below). When these dependencies 471 * are resolved the DEPCOMPLETE flag is set in the diradd structure. 472 * If there are multiple links created to the same inode, there will be 473 * a separate diradd structure created for each link. The diradd is 474 * linked onto the pg_diraddhd list of the pagedep for the directory 475 * page that contains the entry. When a directory page is written, 476 * the pg_diraddhd list is traversed to rollback any entries that are 477 * not yet ready to be written to disk. If a directory entry is being 478 * changed (by rename) rather than added, the DIRCHG flag is set and 479 * the da_previous entry points to the entry that will be "removed" 480 * once the new entry has been committed. During rollback, entries 481 * with da_previous are replaced with the previous inode number rather 482 * than zero. 483 * 484 * The overlaying of da_pagedep and da_previous is done to keep the 485 * structure down to 32 bytes in size on a 32-bit machine. If a 486 * da_previous entry is present, the pointer to its pagedep is available 487 * in the associated dirrem entry. If the DIRCHG flag is set, the 488 * da_previous entry is valid; if not set the da_pagedep entry is valid. 489 * The DIRCHG flag never changes; it is set when the structure is created 490 * if appropriate and is never cleared. 491 */ 492 struct diradd { 493 struct worklist da_list; /* id_inowait or id_pendinghd list */ 494 # define da_state da_list.wk_state /* state of the new directory entry */ 495 LIST_ENTRY(diradd) da_pdlist; /* pagedep holding directory block */ 496 doff_t da_offset; /* offset of new dir entry in dir blk */ 497 ino_t da_newinum; /* inode number for the new dir entry */ 498 union { 499 struct dirrem *dau_previous; /* entry being replaced in dir change */ 500 struct pagedep *dau_pagedep; /* pagedep dependency for addition */ 501 } da_un; 502 }; 503 #define da_previous da_un.dau_previous 504 #define da_pagedep da_un.dau_pagedep 505 506 /* 507 * Two "mkdir" structures are needed to track the additional dependencies 508 * associated with creating a new directory entry. Normally a directory 509 * addition can be committed as soon as the newly referenced inode has been 510 * written to disk with its increased link count. When a directory is 511 * created there are two additional dependencies: writing the directory 512 * data block containing the "." and ".." entries (MKDIR_BODY) and writing 513 * the parent inode with the increased link count for ".." (MKDIR_PARENT). 514 * These additional dependencies are tracked by two mkdir structures that 515 * reference the associated "diradd" structure. When they have completed, 516 * they set the DEPCOMPLETE flag on the diradd so that it knows that its 517 * extra dependencies have been completed. The md_state field is used only 518 * to identify which type of dependency the mkdir structure is tracking. 519 * It is not used in the mainline code for any purpose other than consistency 520 * checking. All the mkdir structures in the system are linked together on 521 * a list. This list is needed so that a diradd can find its associated 522 * mkdir structures and deallocate them if it is prematurely freed (as for 523 * example if a mkdir is immediately followed by a rmdir of the same directory). 524 * Here, the free of the diradd must traverse the list to find the associated 525 * mkdir structures that reference it. The deletion would be faster if the 526 * diradd structure were simply augmented to have two pointers that referenced 527 * the associated mkdir's. However, this would increase the size of the diradd 528 * structure from 32 to 64-bits to speed a very infrequent operation. 529 */ 530 struct mkdir { 531 struct worklist md_list; /* id_inowait or buffer holding dir */ 532 # define md_state md_list.wk_state /* type: MKDIR_PARENT or MKDIR_BODY */ 533 struct diradd *md_diradd; /* associated diradd */ 534 struct buf *md_buf; /* MKDIR_BODY: buffer holding dir */ 535 LIST_ENTRY(mkdir) md_mkdirs; /* list of all mkdirs */ 536 }; 537 LIST_HEAD(mkdirlist, mkdir) mkdirlisthd; 538 539 /* 540 * A "dirrem" structure describes an operation to decrement the link 541 * count on an inode. The dirrem structure is attached to the pg_dirremhd 542 * list of the pagedep for the directory page that contains the entry. 543 * It is processed after the directory page with the deleted entry has 544 * been written to disk. 545 * 546 * The overlaying of dm_pagedep and dm_dirinum is done to keep the 547 * structure down to 32 bytes in size on a 32-bit machine. It works 548 * because they are never used concurrently. 549 */ 550 struct dirrem { 551 struct worklist dm_list; /* delayed worklist */ 552 # define dm_state dm_list.wk_state /* state of the old directory entry */ 553 LIST_ENTRY(dirrem) dm_next; /* pagedep's list of dirrem's */ 554 ino_t dm_oldinum; /* inum of the removed dir entry */ 555 union { 556 struct pagedep *dmu_pagedep; /* pagedep dependency for remove */ 557 ino_t dmu_dirinum; /* parent inode number (for rmdir) */ 558 } dm_un; 559 }; 560 #define dm_pagedep dm_un.dmu_pagedep 561 #define dm_dirinum dm_un.dmu_dirinum 562 563 /* 564 * A "newdirblk" structure tracks the progress of a newly allocated 565 * directory block from its creation until it is claimed by its on-disk 566 * inode. When a block is allocated to a directory, an fsync of a file 567 * whose name is within that block must ensure not only that the block 568 * containing the file name has been written, but also that the on-disk 569 * inode references that block. When a new directory block is created, 570 * we allocate a newdirblk structure which is linked to the associated 571 * allocdirect (on its ad_newdirblk list). When the allocdirect has been 572 * satisfied, the newdirblk structure is moved to the inodedep id_bufwait 573 * list of its directory to await the inode being written. When the inode 574 * is written, the directory entries are fully committed and can be 575 * deleted from their pagedep->id_pendinghd and inodedep->id_pendinghd 576 * lists. Note that we could track directory blocks allocated to indirect 577 * blocks using a similar scheme with the allocindir structures. Rather 578 * than adding this level of complexity, we simply write those newly 579 * allocated indirect blocks synchronously as such allocations are rare. 580 */ 581 struct newdirblk { 582 struct worklist db_list; /* id_inowait or pg_newdirblk */ 583 # define db_state db_list.wk_state /* unused */ 584 struct pagedep *db_pagedep; /* associated pagedep */ 585 }; 586