The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/ufs/ffs/softdep.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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: releng/8.0/sys/ufs/ffs/softdep.h 156203 2006-03-02 05:50:23Z jeff $
   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 };

Cache object: 184767d1b25bae220506ff65ceecc13b


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.