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 * The ATTACHED flag means that the data is not currently being written 50 * to disk. 51 * 52 * The UNDONE flag means that the data has been rolled back to a safe 53 * state for writing to the disk. When the I/O completes, the data is 54 * restored to its current form and the state reverts to ATTACHED. 55 * The data must be locked throughout the rollback, I/O, and roll 56 * forward so that the rolled back information is never visible to 57 * user processes. 58 * 59 * The COMPLETE flag indicates that the item has been written. For example, 60 * a dependency that requires that an inode be written will be marked 61 * COMPLETE after the inode has been written to disk. 62 * 63 * The DEPCOMPLETE flag indicates the completion of any other 64 * dependencies such as the writing of a cylinder group map has been 65 * completed. A dependency structure may be freed only when both it 66 * and its dependencies have completed and any rollbacks that are in 67 * progress have finished as indicated by the set of ALLCOMPLETE flags 68 * all being set. 69 * 70 * The two MKDIR flags indicate additional dependencies that must be done 71 * when creating a new directory. MKDIR_BODY is cleared when the directory 72 * data block containing the "." and ".." entries has been written. 73 * MKDIR_PARENT is cleared when the parent inode with the increased link 74 * count for ".." has been written. When both MKDIR flags have been 75 * cleared, the DEPCOMPLETE flag is set to indicate that the directory 76 * dependencies have been completed. The writing of the directory inode 77 * itself sets the COMPLETE flag which then allows the directory entry for 78 * the new directory to be written to disk. The RMDIR flag marks a dirrem 79 * structure as representing the removal of a directory rather than a 80 * file. When the removal dependencies are completed, additional work needs 81 * to be done* (an additional decrement of the associated inode, and a 82 * decrement of the parent inode). 83 * 84 * The DIRCHG flag marks a diradd structure as representing the changing 85 * of an existing entry rather than the addition of a new one. When 86 * the update is complete the dirrem associated with the inode for 87 * the old name must be added to the worklist to do the necessary 88 * reference count decrement. 89 * 90 * The GOINGAWAY flag indicates that the data structure is frozen from 91 * further change until its dependencies have been completed and its 92 * resources freed after which it will be discarded. 93 * 94 * The IOSTARTED flag prevents multiple calls to the I/O start routine from 95 * doing multiple rollbacks. 96 * 97 * The NEWBLOCK flag marks pagedep structures that have just been allocated, 98 * so must be claimed by the inode before all dependencies are complete. 99 * 100 * The INPROGRESS flag marks worklist structures that are still on the 101 * worklist, but are being considered for action by some process. 102 * 103 * The UFS1FMT flag indicates that the inode being processed is a ufs1 format. 104 * 105 * The EXTDATA flag indicates that the allocdirect describes an 106 * extended-attributes dependency. 107 * 108 * The ONWORKLIST flag shows whether the structure is currently linked 109 * onto a worklist. 110 */ 111 #define ATTACHED 0x000001 112 #define UNDONE 0x000002 113 #define COMPLETE 0x000004 114 #define DEPCOMPLETE 0x000008 115 #define MKDIR_PARENT 0x000010 /* diradd, mkdir, jaddref, jsegdep only */ 116 #define MKDIR_BODY 0x000020 /* diradd, mkdir, jaddref only */ 117 #define RMDIR 0x000040 /* dirrem only */ 118 #define DIRCHG 0x000080 /* diradd, dirrem only */ 119 #define GOINGAWAY 0x000100 /* indirdep, jremref only */ 120 #define IOSTARTED 0x000200 /* inodedep, pagedep, bmsafemap only */ 121 #define UNUSED400 0x000400 /* currently available. */ 122 #define NEWBLOCK 0x000800 /* pagedep, jaddref only */ 123 #define INPROGRESS 0x001000 /* dirrem, freeblks, freefrag, freefile only */ 124 #define UFS1FMT 0x002000 /* indirdep only */ 125 #define EXTDATA 0x004000 /* allocdirect only */ 126 #define ONWORKLIST 0x008000 127 #define IOWAITING 0x010000 /* Thread is waiting for IO to complete. */ 128 #define ONDEPLIST 0x020000 /* Structure is on a dependency list. */ 129 #define UNLINKED 0x040000 /* inodedep has been unlinked. */ 130 #define UNLINKNEXT 0x080000 /* inodedep has valid di_freelink */ 131 #define UNLINKPREV 0x100000 /* inodedep is pointed at in the unlink list */ 132 #define UNLINKONLIST 0x200000 /* inodedep is in the unlinked list on disk */ 133 #define UNLINKLINKS (UNLINKNEXT | UNLINKPREV) 134 135 #define ALLCOMPLETE (ATTACHED | COMPLETE | DEPCOMPLETE) 136 137 /* 138 * The workitem queue. 139 * 140 * It is sometimes useful and/or necessary to clean up certain dependencies 141 * in the background rather than during execution of an application process 142 * or interrupt service routine. To realize this, we append dependency 143 * structures corresponding to such tasks to a "workitem" queue. In a soft 144 * updates implementation, most pending workitems should not wait for more 145 * than a couple of seconds, so the filesystem syncer process awakens once 146 * per second to process the items on the queue. 147 */ 148 149 /* LIST_HEAD(workhead, worklist); -- declared in buf.h */ 150 151 /* 152 * Each request can be linked onto a work queue through its worklist structure. 153 * To avoid the need for a pointer to the structure itself, this structure 154 * MUST be declared FIRST in each type in which it appears! If more than one 155 * worklist is needed in the structure, then a wk_data field must be added 156 * and the macros below changed to use it. 157 */ 158 struct worklist { 159 LIST_ENTRY(worklist) wk_list; /* list of work requests */ 160 struct mount *wk_mp; /* Mount we live in */ 161 unsigned int wk_type:8, /* type of request */ 162 wk_state:24; /* state flags */ 163 }; 164 #define WK_DATA(wk) ((void *)(wk)) 165 #define WK_PAGEDEP(wk) ((struct pagedep *)(wk)) 166 #define WK_INODEDEP(wk) ((struct inodedep *)(wk)) 167 #define WK_BMSAFEMAP(wk) ((struct bmsafemap *)(wk)) 168 #define WK_NEWBLK(wk) ((struct newblk *)(wk)) 169 #define WK_ALLOCDIRECT(wk) ((struct allocdirect *)(wk)) 170 #define WK_INDIRDEP(wk) ((struct indirdep *)(wk)) 171 #define WK_ALLOCINDIR(wk) ((struct allocindir *)(wk)) 172 #define WK_FREEFRAG(wk) ((struct freefrag *)(wk)) 173 #define WK_FREEBLKS(wk) ((struct freeblks *)(wk)) 174 #define WK_FREEWORK(wk) ((struct freework *)(wk)) 175 #define WK_FREEFILE(wk) ((struct freefile *)(wk)) 176 #define WK_DIRADD(wk) ((struct diradd *)(wk)) 177 #define WK_MKDIR(wk) ((struct mkdir *)(wk)) 178 #define WK_DIRREM(wk) ((struct dirrem *)(wk)) 179 #define WK_NEWDIRBLK(wk) ((struct newdirblk *)(wk)) 180 #define WK_JADDREF(wk) ((struct jaddref *)(wk)) 181 #define WK_JREMREF(wk) ((struct jremref *)(wk)) 182 #define WK_JMVREF(wk) ((struct jmvref *)(wk)) 183 #define WK_JSEGDEP(wk) ((struct jsegdep *)(wk)) 184 #define WK_JSEG(wk) ((struct jseg *)(wk)) 185 #define WK_JNEWBLK(wk) ((struct jnewblk *)(wk)) 186 #define WK_JFREEBLK(wk) ((struct jfreeblk *)(wk)) 187 #define WK_FREEDEP(wk) ((struct freedep *)(wk)) 188 #define WK_JFREEFRAG(wk) ((struct jfreefrag *)(wk)) 189 #define WK_SBDEP(wk) ((struct sbdep *)wk) 190 #define WK_JTRUNC(wk) ((struct jtrunc *)(wk)) 191 192 /* 193 * Various types of lists 194 */ 195 LIST_HEAD(dirremhd, dirrem); 196 LIST_HEAD(diraddhd, diradd); 197 LIST_HEAD(newblkhd, newblk); 198 LIST_HEAD(inodedephd, inodedep); 199 LIST_HEAD(allocindirhd, allocindir); 200 LIST_HEAD(allocdirecthd, allocdirect); 201 TAILQ_HEAD(allocdirectlst, allocdirect); 202 LIST_HEAD(indirdephd, indirdep); 203 LIST_HEAD(jaddrefhd, jaddref); 204 LIST_HEAD(jremrefhd, jremref); 205 LIST_HEAD(jmvrefhd, jmvref); 206 LIST_HEAD(jnewblkhd, jnewblk); 207 LIST_HEAD(jfreeblkhd, jfreeblk); 208 LIST_HEAD(freeworkhd, freework); 209 TAILQ_HEAD(jseglst, jseg); 210 TAILQ_HEAD(inoreflst, inoref); 211 212 /* 213 * The "pagedep" structure tracks the various dependencies related to 214 * a particular directory page. If a directory page has any dependencies, 215 * it will have a pagedep linked to its associated buffer. The 216 * pd_dirremhd list holds the list of dirrem requests which decrement 217 * inode reference counts. These requests are processed after the 218 * directory page with the corresponding zero'ed entries has been 219 * written. The pd_diraddhd list maintains the list of diradd requests 220 * which cannot be committed until their corresponding inode has been 221 * written to disk. Because a directory may have many new entries 222 * being created, several lists are maintained hashed on bits of the 223 * offset of the entry into the directory page to keep the lists from 224 * getting too long. Once a new directory entry has been cleared to 225 * be written, it is moved to the pd_pendinghd list. After the new 226 * entry has been written to disk it is removed from the pd_pendinghd 227 * list, any removed operations are done, and the dependency structure 228 * is freed. 229 */ 230 #define DAHASHSZ 5 231 #define DIRADDHASH(offset) (((offset) >> 2) % DAHASHSZ) 232 struct pagedep { 233 struct worklist pd_list; /* page buffer */ 234 # define pd_state pd_list.wk_state /* check for multiple I/O starts */ 235 LIST_ENTRY(pagedep) pd_hash; /* hashed lookup */ 236 ino_t pd_ino; /* associated file */ 237 ufs_lbn_t pd_lbn; /* block within file */ 238 struct newdirblk *pd_newdirblk; /* associated newdirblk if NEWBLOCK */ 239 struct dirremhd pd_dirremhd; /* dirrem's waiting for page */ 240 struct diraddhd pd_diraddhd[DAHASHSZ]; /* diradd dir entry updates */ 241 struct diraddhd pd_pendinghd; /* directory entries awaiting write */ 242 struct jmvrefhd pd_jmvrefhd; /* Dependent journal writes. */ 243 }; 244 245 /* 246 * The "inodedep" structure tracks the set of dependencies associated 247 * with an inode. One task that it must manage is delayed operations 248 * (i.e., work requests that must be held until the inodedep's associated 249 * inode has been written to disk). Getting an inode from its incore 250 * state to the disk requires two steps to be taken by the filesystem 251 * in this order: first the inode must be copied to its disk buffer by 252 * the VOP_UPDATE operation; second the inode's buffer must be written 253 * to disk. To ensure that both operations have happened in the required 254 * order, the inodedep maintains two lists. Delayed operations are 255 * placed on the id_inowait list. When the VOP_UPDATE is done, all 256 * operations on the id_inowait list are moved to the id_bufwait list. 257 * When the buffer is written, the items on the id_bufwait list can be 258 * safely moved to the work queue to be processed. A second task of the 259 * inodedep structure is to track the status of block allocation within 260 * the inode. Each block that is allocated is represented by an 261 * "allocdirect" structure (see below). It is linked onto the id_newinoupdt 262 * list until both its contents and its allocation in the cylinder 263 * group map have been written to disk. Once these dependencies have been 264 * satisfied, it is removed from the id_newinoupdt list and any followup 265 * actions such as releasing the previous block or fragment are placed 266 * on the id_inowait list. When an inode is updated (a VOP_UPDATE is 267 * done), the "inodedep" structure is linked onto the buffer through 268 * its worklist. Thus, it will be notified when the buffer is about 269 * to be written and when it is done. At the update time, all the 270 * elements on the id_newinoupdt list are moved to the id_inoupdt list 271 * since those changes are now relevant to the copy of the inode in the 272 * buffer. Also at update time, the tasks on the id_inowait list are 273 * moved to the id_bufwait list so that they will be executed when 274 * the updated inode has been written to disk. When the buffer containing 275 * the inode is written to disk, any updates listed on the id_inoupdt 276 * list are rolled back as they are not yet safe. Following the write, 277 * the changes are once again rolled forward and any actions on the 278 * id_bufwait list are processed (since those actions are now safe). 279 * The entries on the id_inoupdt and id_newinoupdt lists must be kept 280 * sorted by logical block number to speed the calculation of the size 281 * of the rolled back inode (see explanation in initiate_write_inodeblock). 282 * When a directory entry is created, it is represented by a diradd. 283 * The diradd is added to the id_inowait list as it cannot be safely 284 * written to disk until the inode that it represents is on disk. After 285 * the inode is written, the id_bufwait list is processed and the diradd 286 * entries are moved to the id_pendinghd list where they remain until 287 * the directory block containing the name has been written to disk. 288 * The purpose of keeping the entries on the id_pendinghd list is so that 289 * the softdep_fsync function can find and push the inode's directory 290 * name(s) as part of the fsync operation for that file. 291 */ 292 struct inodedep { 293 struct worklist id_list; /* buffer holding inode block */ 294 # define id_state id_list.wk_state /* inode dependency state */ 295 LIST_ENTRY(inodedep) id_hash; /* hashed lookup */ 296 TAILQ_ENTRY(inodedep) id_unlinked; /* Unlinked but ref'd inodes */ 297 struct fs *id_fs; /* associated filesystem */ 298 ino_t id_ino; /* dependent inode */ 299 nlink_t id_nlinkdelta; /* saved effective link count */ 300 nlink_t id_savednlink; /* Link saved during rollback */ 301 LIST_ENTRY(inodedep) id_deps; /* bmsafemap's list of inodedep's */ 302 struct bmsafemap *id_bmsafemap; /* related bmsafemap (if pending) */ 303 struct diradd *id_mkdiradd; /* diradd for a mkdir. */ 304 struct inoreflst id_inoreflst; /* Inode reference adjustments. */ 305 long id_savedextsize; /* ext size saved during rollback */ 306 off_t id_savedsize; /* file size saved during rollback */ 307 struct dirremhd id_dirremhd; /* Removals pending. */ 308 struct workhead id_pendinghd; /* entries awaiting directory write */ 309 struct workhead id_bufwait; /* operations after inode written */ 310 struct workhead id_inowait; /* operations waiting inode update */ 311 struct allocdirectlst id_inoupdt; /* updates before inode written */ 312 struct allocdirectlst id_newinoupdt; /* updates when inode written */ 313 struct allocdirectlst id_extupdt; /* extdata updates pre-inode write */ 314 struct allocdirectlst id_newextupdt; /* extdata updates at ino write */ 315 union { 316 struct ufs1_dinode *idu_savedino1; /* saved ufs1_dinode contents */ 317 struct ufs2_dinode *idu_savedino2; /* saved ufs2_dinode contents */ 318 } id_un; 319 }; 320 #define id_savedino1 id_un.idu_savedino1 321 #define id_savedino2 id_un.idu_savedino2 322 323 /* 324 * A "bmsafemap" structure maintains a list of dependency structures 325 * that depend on the update of a particular cylinder group map. 326 * It has lists for newblks, allocdirects, allocindirs, and inodedeps. 327 * It is attached to the buffer of a cylinder group block when any of 328 * these things are allocated from the cylinder group. It is freed 329 * after the cylinder group map is written and the state of its 330 * dependencies are updated with DEPCOMPLETE to indicate that it has 331 * been processed. 332 */ 333 struct bmsafemap { 334 struct worklist sm_list; /* cylgrp buffer */ 335 # define sm_state sm_list.wk_state 336 int sm_cg; 337 LIST_ENTRY(bmsafemap) sm_hash; /* Hash links. */ 338 struct buf *sm_buf; /* associated buffer */ 339 struct allocdirecthd sm_allocdirecthd; /* allocdirect deps */ 340 struct allocdirecthd sm_allocdirectwr; /* writing allocdirect deps */ 341 struct allocindirhd sm_allocindirhd; /* allocindir deps */ 342 struct allocindirhd sm_allocindirwr; /* writing allocindir deps */ 343 struct inodedephd sm_inodedephd; /* inodedep deps */ 344 struct inodedephd sm_inodedepwr; /* writing inodedep deps */ 345 struct newblkhd sm_newblkhd; /* newblk deps */ 346 struct newblkhd sm_newblkwr; /* writing newblk deps */ 347 struct jaddrefhd sm_jaddrefhd; /* Pending inode allocations. */ 348 struct jnewblkhd sm_jnewblkhd; /* Pending block allocations. */ 349 }; 350 351 /* 352 * A "newblk" structure is attached to a bmsafemap structure when a block 353 * or fragment is allocated from a cylinder group. Its state is set to 354 * DEPCOMPLETE when its cylinder group map is written. It is converted to 355 * an allocdirect or allocindir allocation once the allocator calls the 356 * appropriate setup function. 357 */ 358 struct newblk { 359 struct worklist nb_list; 360 # define nb_state nb_list.wk_state 361 LIST_ENTRY(newblk) nb_hash; /* hashed lookup */ 362 LIST_ENTRY(newblk) nb_deps; /* bmsafemap's list of newblks */ 363 struct jnewblk *nb_jnewblk; /* New block journal entry. */ 364 struct bmsafemap *nb_bmsafemap;/* cylgrp dep (if pending) */ 365 struct freefrag *nb_freefrag; /* fragment to be freed (if any) */ 366 struct indirdephd nb_indirdeps; /* Children indirect blocks. */ 367 struct workhead nb_newdirblk; /* dir block to notify when written */ 368 struct workhead nb_jwork; /* Journal work pending. */ 369 ufs2_daddr_t nb_newblkno; /* new value of block pointer */ 370 }; 371 372 /* 373 * An "allocdirect" structure is attached to an "inodedep" when a new block 374 * or fragment is allocated and pointed to by the inode described by 375 * "inodedep". The worklist is linked to the buffer that holds the block. 376 * When the block is first allocated, it is linked to the bmsafemap 377 * structure associated with the buffer holding the cylinder group map 378 * from which it was allocated. When the cylinder group map is written 379 * to disk, ad_state has the DEPCOMPLETE flag set. When the block itself 380 * is written, the COMPLETE flag is set. Once both the cylinder group map 381 * and the data itself have been written, it is safe to write the inode 382 * that claims the block. If there was a previous fragment that had been 383 * allocated before the file was increased in size, the old fragment may 384 * be freed once the inode claiming the new block is written to disk. 385 * This ad_fragfree request is attached to the id_inowait list of the 386 * associated inodedep (pointed to by ad_inodedep) for processing after 387 * the inode is written. When a block is allocated to a directory, an 388 * fsync of a file whose name is within that block must ensure not only 389 * that the block containing the file name has been written, but also 390 * that the on-disk inode references that block. When a new directory 391 * block is created, we allocate a newdirblk structure which is linked 392 * to the associated allocdirect (on its ad_newdirblk list). When the 393 * allocdirect has been satisfied, the newdirblk structure is moved to 394 * the inodedep id_bufwait list of its directory to await the inode 395 * being written. When the inode is written, the directory entries are 396 * fully committed and can be deleted from their pagedep->id_pendinghd 397 * and inodedep->id_pendinghd lists. 398 */ 399 struct allocdirect { 400 struct newblk ad_block; /* Common block logic */ 401 # define ad_state ad_block.nb_list.wk_state /* block pointer state */ 402 TAILQ_ENTRY(allocdirect) ad_next; /* inodedep's list of allocdirect's */ 403 struct inodedep *ad_inodedep; /* associated inodedep */ 404 ufs2_daddr_t ad_oldblkno; /* old value of block pointer */ 405 int ad_offset; /* Pointer offset in parent. */ 406 long ad_newsize; /* size of new block */ 407 long ad_oldsize; /* size of old block */ 408 }; 409 #define ad_newblkno ad_block.nb_newblkno 410 #define ad_freefrag ad_block.nb_freefrag 411 #define ad_newdirblk ad_block.nb_newdirblk 412 413 /* 414 * A single "indirdep" structure manages all allocation dependencies for 415 * pointers in an indirect block. The up-to-date state of the indirect 416 * block is stored in ir_savedata. The set of pointers that may be safely 417 * written to the disk is stored in ir_safecopy. The state field is used 418 * only to track whether the buffer is currently being written (in which 419 * case it is not safe to update ir_safecopy). Ir_deplisthd contains the 420 * list of allocindir structures, one for each block that needs to be 421 * written to disk. Once the block and its bitmap allocation have been 422 * written the safecopy can be updated to reflect the allocation and the 423 * allocindir structure freed. If ir_state indicates that an I/O on the 424 * indirect block is in progress when ir_safecopy is to be updated, the 425 * update is deferred by placing the allocindir on the ir_donehd list. 426 * When the I/O on the indirect block completes, the entries on the 427 * ir_donehd list are processed by updating their corresponding ir_safecopy 428 * pointers and then freeing the allocindir structure. 429 */ 430 struct indirdep { 431 struct worklist ir_list; /* buffer holding indirect block */ 432 # define ir_state ir_list.wk_state /* indirect block pointer state */ 433 LIST_ENTRY(indirdep) ir_next; /* alloc{direct,indir} list */ 434 caddr_t ir_saveddata; /* buffer cache contents */ 435 struct buf *ir_savebp; /* buffer holding safe copy */ 436 struct allocindirhd ir_completehd; /* waiting for indirdep complete */ 437 struct allocindirhd ir_writehd; /* Waiting for the pointer write. */ 438 struct allocindirhd ir_donehd; /* done waiting to update safecopy */ 439 struct allocindirhd ir_deplisthd; /* allocindir deps for this block */ 440 struct workhead ir_jwork; /* Journal work pending. */ 441 }; 442 443 /* 444 * An "allocindir" structure is attached to an "indirdep" when a new block 445 * is allocated and pointed to by the indirect block described by the 446 * "indirdep". The worklist is linked to the buffer that holds the new block. 447 * When the block is first allocated, it is linked to the bmsafemap 448 * structure associated with the buffer holding the cylinder group map 449 * from which it was allocated. When the cylinder group map is written 450 * to disk, ai_state has the DEPCOMPLETE flag set. When the block itself 451 * is written, the COMPLETE flag is set. Once both the cylinder group map 452 * and the data itself have been written, it is safe to write the entry in 453 * the indirect block that claims the block; the "allocindir" dependency 454 * can then be freed as it is no longer applicable. 455 */ 456 struct allocindir { 457 struct newblk ai_block; /* Common block area */ 458 # define ai_state ai_block.nb_list.wk_state /* indirect pointer state */ 459 LIST_ENTRY(allocindir) ai_next; /* indirdep's list of allocindir's */ 460 struct indirdep *ai_indirdep; /* address of associated indirdep */ 461 ufs2_daddr_t ai_oldblkno; /* old value of block pointer */ 462 int ai_offset; /* Pointer offset in parent. */ 463 }; 464 #define ai_newblkno ai_block.nb_newblkno 465 #define ai_freefrag ai_block.nb_freefrag 466 #define ai_newdirblk ai_block.nb_newdirblk 467 468 /* 469 * The allblk union is used to size the newblk structure on allocation so 470 * that it may be any one of three types. 471 */ 472 union allblk { 473 struct allocindir ab_allocindir; 474 struct allocdirect ab_allocdirect; 475 struct newblk ab_newblk; 476 }; 477 478 /* 479 * A "freefrag" structure is attached to an "inodedep" when a previously 480 * allocated fragment is replaced with a larger fragment, rather than extended. 481 * The "freefrag" structure is constructed and attached when the replacement 482 * block is first allocated. It is processed after the inode claiming the 483 * bigger block that replaces it has been written to disk. 484 */ 485 struct freefrag { 486 struct worklist ff_list; /* id_inowait or delayed worklist */ 487 # define ff_state ff_list.wk_state 488 struct jfreefrag *ff_jfreefrag; /* Associated journal entry. */ 489 struct workhead ff_jwork; /* Journal work pending. */ 490 ufs2_daddr_t ff_blkno; /* fragment physical block number */ 491 long ff_fragsize; /* size of fragment being deleted */ 492 ino_t ff_inum; /* owning inode number */ 493 }; 494 495 /* 496 * A "freeblks" structure is attached to an "inodedep" when the 497 * corresponding file's length is reduced to zero. It records all 498 * the information needed to free the blocks of a file after its 499 * zero'ed inode has been written to disk. The actual work is done 500 * by child freework structures which are responsible for individual 501 * inode pointers while freeblks is responsible for retiring the 502 * entire operation when it is complete and holding common members. 503 */ 504 struct freeblks { 505 struct worklist fb_list; /* id_inowait or delayed worklist */ 506 # define fb_state fb_list.wk_state /* inode and dirty block state */ 507 struct jfreeblkhd fb_jfreeblkhd; /* Journal entries pending */ 508 struct workhead fb_freeworkhd; /* Work items pending */ 509 struct workhead fb_jwork; /* Journal work pending */ 510 ino_t fb_previousinum; /* inode of previous owner of blocks */ 511 uid_t fb_uid; /* uid of previous owner of blocks */ 512 struct vnode *fb_devvp; /* filesystem device vnode */ 513 ufs2_daddr_t fb_chkcnt; /* used to check cnt of blks released */ 514 int fb_ref; /* Children outstanding. */ 515 }; 516 517 /* 518 * A "freework" structure handles the release of a tree of blocks or a single 519 * block. Each indirect block in a tree is allocated its own freework 520 * structure so that the indrect block may be freed only when all of its 521 * children are freed. In this way we enforce the rule that an allocated 522 * block must have a valid path to a root that is journaled. Each child 523 * block acquires a reference and when the ref hits zero the parent ref 524 * is decremented. If there is no parent the freeblks ref is decremented. 525 */ 526 struct freework { 527 struct worklist fw_list; 528 # define fw_state fw_list.wk_state 529 LIST_ENTRY(freework) fw_next; /* Queue for freeblksk. */ 530 struct freeblks *fw_freeblks; /* Root of operation. */ 531 struct freework *fw_parent; /* Parent indirect. */ 532 ufs2_daddr_t fw_blkno; /* Our block #. */ 533 ufs_lbn_t fw_lbn; /* Original lbn before free. */ 534 int fw_frags; /* Number of frags. */ 535 int fw_ref; /* Number of children out. */ 536 int fw_off; /* Current working position. */ 537 struct workhead fw_jwork; /* Journal work pending. */ 538 }; 539 540 /* 541 * A "freedep" structure is allocated to track the completion of a bitmap 542 * write for a freework. One freedep may cover many freed blocks so long 543 * as they reside in the same cylinder group. When the cg is written 544 * the freedep decrements the ref on the freework which may permit it 545 * to be freed as well. 546 */ 547 struct freedep { 548 struct worklist fd_list; 549 struct freework *fd_freework; /* Parent freework. */ 550 }; 551 552 /* 553 * A "freefile" structure is attached to an inode when its 554 * link count is reduced to zero. It marks the inode as free in 555 * the cylinder group map after the zero'ed inode has been written 556 * to disk and any associated blocks and fragments have been freed. 557 */ 558 struct freefile { 559 struct worklist fx_list; /* id_inowait or delayed worklist */ 560 mode_t fx_mode; /* mode of inode */ 561 ino_t fx_oldinum; /* inum of the unlinked file */ 562 struct vnode *fx_devvp; /* filesystem device vnode */ 563 struct workhead fx_jwork; /* journal work pending. */ 564 }; 565 566 /* 567 * A "diradd" structure is linked to an "inodedep" id_inowait list when a 568 * new directory entry is allocated that references the inode described 569 * by "inodedep". When the inode itself is written (either the initial 570 * allocation for new inodes or with the increased link count for 571 * existing inodes), the COMPLETE flag is set in da_state. If the entry 572 * is for a newly allocated inode, the "inodedep" structure is associated 573 * with a bmsafemap which prevents the inode from being written to disk 574 * until the cylinder group has been updated. Thus the da_state COMPLETE 575 * flag cannot be set until the inode bitmap dependency has been removed. 576 * When creating a new file, it is safe to write the directory entry that 577 * claims the inode once the referenced inode has been written. Since 578 * writing the inode clears the bitmap dependencies, the DEPCOMPLETE flag 579 * in the diradd can be set unconditionally when creating a file. When 580 * creating a directory, there are two additional dependencies described by 581 * mkdir structures (see their description below). When these dependencies 582 * are resolved the DEPCOMPLETE flag is set in the diradd structure. 583 * If there are multiple links created to the same inode, there will be 584 * a separate diradd structure created for each link. The diradd is 585 * linked onto the pg_diraddhd list of the pagedep for the directory 586 * page that contains the entry. When a directory page is written, 587 * the pg_diraddhd list is traversed to rollback any entries that are 588 * not yet ready to be written to disk. If a directory entry is being 589 * changed (by rename) rather than added, the DIRCHG flag is set and 590 * the da_previous entry points to the entry that will be "removed" 591 * once the new entry has been committed. During rollback, entries 592 * with da_previous are replaced with the previous inode number rather 593 * than zero. 594 * 595 * The overlaying of da_pagedep and da_previous is done to keep the 596 * structure down. If a da_previous entry is present, the pointer to its 597 * pagedep is available in the associated dirrem entry. If the DIRCHG flag 598 * is set, the da_previous entry is valid; if not set the da_pagedep entry 599 * is valid. The DIRCHG flag never changes; it is set when the structure 600 * is created if appropriate and is never cleared. 601 */ 602 struct diradd { 603 struct worklist da_list; /* id_inowait or id_pendinghd list */ 604 # define da_state da_list.wk_state /* state of the new directory entry */ 605 LIST_ENTRY(diradd) da_pdlist; /* pagedep holding directory block */ 606 doff_t da_offset; /* offset of new dir entry in dir blk */ 607 ino_t da_newinum; /* inode number for the new dir entry */ 608 union { 609 struct dirrem *dau_previous; /* entry being replaced in dir change */ 610 struct pagedep *dau_pagedep; /* pagedep dependency for addition */ 611 } da_un; 612 struct workhead da_jwork; /* Journal work awaiting completion. */ 613 }; 614 #define da_previous da_un.dau_previous 615 #define da_pagedep da_un.dau_pagedep 616 617 /* 618 * Two "mkdir" structures are needed to track the additional dependencies 619 * associated with creating a new directory entry. Normally a directory 620 * addition can be committed as soon as the newly referenced inode has been 621 * written to disk with its increased link count. When a directory is 622 * created there are two additional dependencies: writing the directory 623 * data block containing the "." and ".." entries (MKDIR_BODY) and writing 624 * the parent inode with the increased link count for ".." (MKDIR_PARENT). 625 * These additional dependencies are tracked by two mkdir structures that 626 * reference the associated "diradd" structure. When they have completed, 627 * they set the DEPCOMPLETE flag on the diradd so that it knows that its 628 * extra dependencies have been completed. The md_state field is used only 629 * to identify which type of dependency the mkdir structure is tracking. 630 * It is not used in the mainline code for any purpose other than consistency 631 * checking. All the mkdir structures in the system are linked together on 632 * a list. This list is needed so that a diradd can find its associated 633 * mkdir structures and deallocate them if it is prematurely freed (as for 634 * example if a mkdir is immediately followed by a rmdir of the same directory). 635 * Here, the free of the diradd must traverse the list to find the associated 636 * mkdir structures that reference it. The deletion would be faster if the 637 * diradd structure were simply augmented to have two pointers that referenced 638 * the associated mkdir's. However, this would increase the size of the diradd 639 * structure to speed a very infrequent operation. 640 */ 641 struct mkdir { 642 struct worklist md_list; /* id_inowait or buffer holding dir */ 643 # define md_state md_list.wk_state /* type: MKDIR_PARENT or MKDIR_BODY */ 644 struct diradd *md_diradd; /* associated diradd */ 645 struct jaddref *md_jaddref; /* dependent jaddref. */ 646 struct buf *md_buf; /* MKDIR_BODY: buffer holding dir */ 647 LIST_ENTRY(mkdir) md_mkdirs; /* list of all mkdirs */ 648 }; 649 LIST_HEAD(mkdirlist, mkdir) mkdirlisthd; 650 651 /* 652 * A "dirrem" structure describes an operation to decrement the link 653 * count on an inode. The dirrem structure is attached to the pg_dirremhd 654 * list of the pagedep for the directory page that contains the entry. 655 * It is processed after the directory page with the deleted entry has 656 * been written to disk. 657 */ 658 struct dirrem { 659 struct worklist dm_list; /* delayed worklist */ 660 # define dm_state dm_list.wk_state /* state of the old directory entry */ 661 LIST_ENTRY(dirrem) dm_next; /* pagedep's list of dirrem's */ 662 LIST_ENTRY(dirrem) dm_inonext; /* inodedep's list of dirrem's */ 663 struct jremrefhd dm_jremrefhd; /* Pending remove reference deps. */ 664 ino_t dm_oldinum; /* inum of the removed dir entry */ 665 union { 666 struct pagedep *dmu_pagedep; /* pagedep dependency for remove */ 667 ino_t dmu_dirinum; /* parent inode number (for rmdir) */ 668 } dm_un; 669 struct workhead dm_jwork; /* Journal work awaiting completion. */ 670 }; 671 #define dm_pagedep dm_un.dmu_pagedep 672 #define dm_dirinum dm_un.dmu_dirinum 673 674 /* 675 * A "newdirblk" structure tracks the progress of a newly allocated 676 * directory block from its creation until it is claimed by its on-disk 677 * inode. When a block is allocated to a directory, an fsync of a file 678 * whose name is within that block must ensure not only that the block 679 * containing the file name has been written, but also that the on-disk 680 * inode references that block. When a new directory block is created, 681 * we allocate a newdirblk structure which is linked to the associated 682 * allocdirect (on its ad_newdirblk list). When the allocdirect has been 683 * satisfied, the newdirblk structure is moved to the inodedep id_bufwait 684 * list of its directory to await the inode being written. When the inode 685 * is written, the directory entries are fully committed and can be 686 * deleted from their pagedep->id_pendinghd and inodedep->id_pendinghd 687 * lists. Note that we could track directory blocks allocated to indirect 688 * blocks using a similar scheme with the allocindir structures. Rather 689 * than adding this level of complexity, we simply write those newly 690 * allocated indirect blocks synchronously as such allocations are rare. 691 * In the case of a new directory the . and .. links are tracked with 692 * a mkdir rather than a pagedep. In this case we track the mkdir 693 * so it can be released when it is written. A workhead is used 694 * to simplify canceling a mkdir that is removed by a subsequent dirrem. 695 */ 696 struct newdirblk { 697 struct worklist db_list; /* id_inowait or pg_newdirblk */ 698 # define db_state db_list.wk_state /* unused */ 699 struct pagedep *db_pagedep; /* associated pagedep */ 700 struct workhead db_mkdir; 701 }; 702 703 /* 704 * The inoref structure holds the elements common to jaddref and jremref 705 * so they may easily be queued in-order on the inodedep. 706 */ 707 struct inoref { 708 struct worklist if_list; 709 # define if_state if_list.wk_state 710 TAILQ_ENTRY(inoref) if_deps; /* Links for inodedep. */ 711 struct jsegdep *if_jsegdep; 712 off_t if_diroff; /* Directory offset. */ 713 ino_t if_ino; /* Inode number. */ 714 ino_t if_parent; /* Parent inode number. */ 715 nlink_t if_nlink; /* nlink before addition. */ 716 uint16_t if_mode; /* File mode, needed for IFMT. */ 717 }; 718 719 /* 720 * A "jaddref" structure tracks a new reference (link count) on an inode 721 * and prevents the link count increase and bitmap allocation until a 722 * journal entry can be written. Once the journal entry is written, 723 * the inode is put on the pendinghd of the bmsafemap and a diradd or 724 * mkdir entry is placed on the bufwait list of the inode. The DEPCOMPLETE 725 * flag is used to indicate that all of the required information for writing 726 * the journal entry is present. MKDIR_BODY and MKDIR_PARENT are used to 727 * differentiate . and .. links from regular file names. NEWBLOCK indicates 728 * a bitmap is still pending. If a new reference is canceled by a delete 729 * prior to writing the journal the jaddref write is canceled and the 730 * structure persists to prevent any disk-visible changes until it is 731 * ultimately released when the file is freed or the link is dropped again. 732 */ 733 struct jaddref { 734 struct inoref ja_ref; 735 # define ja_list ja_ref.if_list /* Journal pending or jseg entries. */ 736 # define ja_state ja_ref.if_list.wk_state 737 LIST_ENTRY(jaddref) ja_bmdeps; /* Links for bmsafemap. */ 738 union { 739 struct diradd *jau_diradd; /* Pending diradd. */ 740 struct mkdir *jau_mkdir; /* MKDIR_{PARENT,BODY} */ 741 } ja_un; 742 }; 743 #define ja_diradd ja_un.jau_diradd 744 #define ja_mkdir ja_un.jau_mkdir 745 #define ja_diroff ja_ref.if_diroff 746 #define ja_ino ja_ref.if_ino 747 #define ja_parent ja_ref.if_parent 748 #define ja_mode ja_ref.if_mode 749 750 /* 751 * A "jremref" structure tracks a removed reference (unlink) on an 752 * inode and prevents the directory remove from proceeding until the 753 * journal entry is written. Once the journal has been written the remove 754 * may proceed as normal. 755 */ 756 struct jremref { 757 struct inoref jr_ref; 758 # define jr_list jr_ref.if_list /* Journal pending or jseg entries. */ 759 # define jr_state jr_ref.if_list.wk_state 760 LIST_ENTRY(jremref) jr_deps; /* Links for pagdep. */ 761 struct dirrem *jr_dirrem; /* Back pointer to dirrem. */ 762 }; 763 764 struct jmvref { 765 struct worklist jm_list; 766 LIST_ENTRY(jmvref) jm_deps; 767 struct pagedep *jm_pagedep; 768 ino_t jm_parent; 769 ino_t jm_ino; 770 off_t jm_oldoff; 771 off_t jm_newoff; 772 }; 773 774 /* 775 * A "jnewblk" structure tracks a newly allocated block or fragment and 776 * prevents the direct or indirect block pointer as well as the cg bitmap 777 * from being written until it is logged. After it is logged the jsegdep 778 * is attached to the allocdirect or allocindir until the operation is 779 * completed or reverted. If the operation is reverted prior to the journal 780 * write the jnewblk structure is maintained to prevent the bitmaps from 781 * reaching the disk. Ultimately the jnewblk structure will be passed 782 * to the free routine as the in memory cg is modified back to the free 783 * state at which time it can be released. 784 */ 785 struct jnewblk { 786 struct worklist jn_list; 787 # define jn_state jn_list.wk_state 788 struct jsegdep *jn_jsegdep; 789 LIST_ENTRY(jnewblk) jn_deps; /* All jnewblks on bmsafemap */ 790 struct newblk *jn_newblk; 791 ino_t jn_ino; 792 ufs_lbn_t jn_lbn; 793 ufs2_daddr_t jn_blkno; 794 int jn_oldfrags; 795 int jn_frags; 796 }; 797 798 /* 799 * A "jfreeblk" structure tracks the journal write for freeing a block 800 * or tree of blocks. The block pointer must not be cleared in the inode 801 * or indirect prior to the jfreeblk being written. 802 */ 803 struct jfreeblk { 804 struct worklist jf_list; 805 # define jf_state jf_list.wk_state 806 struct jsegdep *jf_jsegdep; 807 struct freeblks *jf_freeblks; 808 LIST_ENTRY(jfreeblk) jf_deps; 809 ino_t jf_ino; 810 ufs_lbn_t jf_lbn; 811 ufs2_daddr_t jf_blkno; 812 int jf_frags; 813 }; 814 815 /* 816 * A "jfreefrag" tracks the freeing of a single block when a fragment is 817 * extended or an indirect page is replaced. It is not part of a larger 818 * freeblks operation. 819 */ 820 struct jfreefrag { 821 struct worklist fr_list; 822 # define fr_state fr_list.wk_state 823 struct jsegdep *fr_jsegdep; 824 struct freefrag *fr_freefrag; 825 ino_t fr_ino; 826 ufs_lbn_t fr_lbn; 827 ufs2_daddr_t fr_blkno; 828 int fr_frags; 829 }; 830 831 /* 832 * A "jtrunc" journals the intent to truncate an inode to a non-zero 833 * value. This is done synchronously prior to the synchronous partial 834 * truncation process. The jsegdep is not released until the truncation 835 * is complete and the truncated inode is fsync'd. 836 */ 837 struct jtrunc { 838 struct worklist jt_list; 839 struct jsegdep *jt_jsegdep; 840 ino_t jt_ino; 841 off_t jt_size; 842 int jt_extsize; 843 }; 844 845 /* 846 * A "jsegdep" structure tracks a single reference to a written journal 847 * segment so the journal space can be reclaimed when all dependencies 848 * have been written. 849 */ 850 struct jsegdep { 851 struct worklist jd_list; 852 # define jd_state jd_list.wk_state 853 struct jseg *jd_seg; 854 }; 855 856 /* 857 * A "jseg" structure contains all of the journal records written in a 858 * single disk write. jaddref and jremref structures are linked into 859 * js_entries so thay may be completed when the write completes. The 860 * js_deps array contains as many entries as there are ref counts to 861 * reduce the number of allocations required per journal write to one. 862 */ 863 struct jseg { 864 struct worklist js_list; /* b_deps link for journal */ 865 # define js_state js_list.wk_state 866 struct workhead js_entries; /* Entries awaiting write */ 867 TAILQ_ENTRY(jseg) js_next; 868 struct jblocks *js_jblocks; /* Back pointer to block/seg list */ 869 struct buf *js_buf; /* Buffer while unwritten */ 870 uint64_t js_seq; 871 int js_size; /* Allocated size in bytes */ 872 int js_cnt; /* Total items allocated */ 873 int js_refs; /* Count of items pending completion */ 874 }; 875 876 /* 877 * A 'sbdep' structure tracks the head of the free inode list and 878 * superblock writes. This makes sure the superblock is always pointing at 879 * the first possible unlinked inode for the suj recovery process. If a 880 * block write completes and we discover a new head is available the buf 881 * is dirtied and the dep is kept. 882 */ 883 struct sbdep { 884 struct worklist sb_list; /* b_dep linkage */ 885 struct fs *sb_fs; /* Filesystem pointer within buf. */ 886 struct ufsmount *sb_ump; 887 }; 888