state.h

   1
   2 /*
   3  * fs/lafs/state.h
   4  * Copyright (C) 2005-2009
   5  * Neil Brown <neilb@suse.de>
   6  * Released under the GPL, version 2
   7  *
   8  * The stateblock and superblocks are copied into the
   9  * internal 'struct fs' at startup time, and are written
  10  * out based on information there-in.
  11  * The first stateblock read has sufficient information
  12  * to size all the components. These are only changed
  13  * in unusual circumstances (Adding devices, taking snapshots).
  14  */
  15
  16 #define HASHBITS 10
  17 #define HASHSIZE (1<<HASHBITS)
  18 #define HASHMASK (HASHSIZE-1)
  19
  20 /* for segment hash */
  21 #define SHASHBITS       8
  22 #define SHASHSIZE       (1<<SHASHBITS)
  23 #define SHASHMASK       (SHASHSIZE-1)
  24
  25 /* for quota hash */
  26 #define QHASHBITS 9
  27 #define QHASHSIZE (1<<QHASHBITS)
  28 #define QHASHMASK (QHASHSIZE-1)
  29
  30 /* skip points are used to accelerate sequential-order insert
  31  * in the list of blocks pending write
  32  */
  33 #define SKIP_MAX_HEIGHT 8
  34 struct skippoint {
  35         struct block *b;
  36         struct skippoint *next[SKIP_MAX_HEIGHT];
  37 };
  38
  39 #define WC_NUM 3        /* 3 active write-clusters: new, clean, and defrag */
  40 #define CLEANER_SEGS 4  /* Clean at most 4 segments at a time */
  41
  42 #define ACCOUNT_RESERVED  3 /* Reserve 3 segments of space for accounting and
  43                              * cleaning
  44                              */
  45 #define RELEASE_RESERVED 1 /* Reserve 1 segment of space for overhead required
  46                             * to release space (e.g. delete file)
  47                             */
  48 #define TOTAL_RESERVED (ACCOUNT_RESERVED + RELEASE_RESERVED)
  49 struct fs {
  50         struct  lafs_state      *state;
  51
  52         u32     seq;
  53         u32     levels;
  54         u32     devices;
  55         u32     statesize;
  56
  57         int     blocksize, blocksize_bits;
  58         int     devs_loaded;
  59
  60         atomic_t sb_writes_pending;
  61         wait_queue_head_t sb_writes_wait;
  62         wait_queue_head_t trunc_wait;
  63         wait_queue_head_t async_complete;
  64
  65         struct super_block *prime_sb;
  66
  67         u32     nonlog_segment;
  68         unsigned short  nonlog_dev;
  69         u16     nonlog_offset;
  70
  71         u32     maxsnapshot;
  72         u64     checkpointcluster;
  73         struct snapshot {
  74                 u64     root_addr;
  75                 struct inode    *root;
  76         } *ss;
  77         u32     current_ss;
  78
  79         /* general purpose lock. Protects:
  80          * - pending_orphans list
  81          * - phase_locked
  82          */
  83         spinlock_t lock;
  84         struct inode *orphans; /* the orphans file */
  85
  86         struct list_head pending_orphans;
  87
  88         int phase_locked;
  89         int     phase;  /* 0 or 1 */
  90         wait_queue_head_t phase_wait; /* Also use to wait for first_free_pass */
  91
  92         /* flags to set on next cluster. */
  93         int     checkpointing;
  94         int     rolled; /* set when rollforward has completed */
  95         unsigned long fsstate;
  96 #define CheckpointNeeded 0
  97 #define ThreadRunning   1
  98 #define ThreadNeeded    2
  99 #define FinalCheckpoint 3
 100 #define CleanerDisabled 4
 101 #define OrphansRunning 5
 102 #define CleanerBlocks 6 /* One or more threads is blocked waiting for the
 103                          * cleaner to progress - cleaner.need blocks are
 104                          * needed.
 105                          */
 106 #define EmergencyClean 7/* Cleaner is in emergency mode and will clean
 107                          * the segment with the most space no matter
 108                          * how young it is.   The fs is considered to
 109                          * be full and new allocation requests get
 110                          * -ENOSPC
 111                          */
 112 #define FlushNeeded 8  /* Need to flush the current cluster because
 113                         * someone is waiting on writeback
 114                         */
 115 #define SecondFlushNeeded 9 /* Need a second cluster to commit the blocks
 116                              * in the previous one
 117                              */
 118 #define EmergencyPending 10 /* Cleaner isn't quite in emergency mode, but
 119                              * should be after the next checkpoint unless that
 120                              * releases lots of space
 121                              */
 122 #define CheckpointOpen 11 /* Some data has been written since the last checkpoint,
 123                            * so 'next_checkpoint' is a valid timestamp
 124                            */
 125 #define DelayYouth 12  /* While set, don't update any youth blocks.  The update will
 126                         * happen either during seg_apply_all or in roll-forward
 127                         */
 128
 129         unsigned long next_checkpoint; /* Valid when CheckpointOpen is set, holds
 130                                         * jiffie time by when we need to do a checkpoint
 131                                         */
 132
 133         struct work_struct done_work;   /* used for handling
 134                                          * refile after write completes */
 135
 136         struct {
 137                 int active;             /* number of actively cleaned segments */
 138                 u32 cleaning;           /* amount of space that is being cleaned
 139                                          * this checkpoint
 140                                          */
 141                 u32 need;               /* Amount of space that is needed by
 142                                          * Some thread waiting on CleanerBlocks
 143                                          * flag.
 144                                          */
 145                 struct mutex lock;      /* protects list mani and refcnt of core
 146                                          * cleaner.
 147                                          */
 148                 struct toclean {
 149                         u16 dev;
 150                         u32 seg;
 151                         u64 haddr;      /* Address of this write-cluster-header */
 152                         u64 seq;        /* seq of most recent header loaded */
 153                         struct cluster_head *ch;
 154                         struct group_head *gh; /* current group head */
 155                         struct descriptor *desc;
 156                         struct async_complete {
 157                                 int state;      /* 0=ignore, 1=valid, 2=loading,
 158                                                    3=loaded, 4 = ioerror */
 159                                 struct fs *fs;
 160                         } ac;
 161                         int have_addr;  /* true if dev/seg are valid */
 162                         struct list_head cleaning;
 163                         struct page *chead;
 164                 } seg[CLEANER_SEGS];
 165         } cleaner;
 166         struct task_struct *thread;
 167
 168         unsigned long newsegments;      /* number of segments written since checkpoint */
 169         unsigned long max_newsegs;      /* max segments in a checkpoint (roughly) */
 170
 171         /* counters for (pre)allocating space. */
 172         spinlock_t alloc_lock;
 173         s64     free_blocks; /* initialised from free segment info */
 174         u64     allocated_blocks; /* Blocks that have been (pre)allocated */
 175         u64     clean_reserved; /* Blocks reserved for cleaner segments */
 176         u64     max_segment; /* largest segment size */
 177         u64     total_free;  /* free space found in all segments this scan */
 178         u64     total_free_prev; /* "  "   " in previous scan */
 179         int cluster_updates; /* DEBUGGING */
 180 #define NewSpace 0
 181 #define ReleaseSpace 1
 182 #define CleanSpace 2
 183 #define AccountSpace 3
 184
 185         struct list_head        inode_index; /* list of inode index_blocks,
 186                                               * largely so they can look hashed
 187                                               */
 188
 189         struct list_head        phase_leafs[2]; /* list of pinned blocks that
 190                                                  * have no pinned children,
 191                                                  * and are in phase p
 192                                                  */
 193
 194         struct list_head        clean_leafs;    /* list of pinned blocks that
 195                                                  * have no pinned children
 196                                                  * and are being cleaned
 197                                                  */
 198         struct list_head        account_leafs;  /* list of accounting block
 199                                                  * that we need to write after
 200                                                  * the checkpoint is done.
 201                                                  * They are now pinned to the
 202                                                  * next phase.
 203                                                  */
 204
 205         /* Youth management */
 206         int     youth_next;     /* number to assign to next segment */
 207         int     checkpoint_youth;
 208
 209 /* 10 heights: 0 to 9 */
 210 #define SEG_NUM_HEIGHTS (10)
 211         struct segtracker {
 212                 void *page[4];
 213                 int size[4]; /* entry size in page as "number of skip pointers" */
 214                 struct slist {
 215                         unsigned short first, last;
 216                         unsigned short cnt;
 217                 } unused, free, cleanable, clean;
 218                 unsigned short head[SEG_NUM_HEIGHTS]; /* head of skiplist */
 219                 int total;
 220                 int max_score;
 221                 int sorted_size;
 222         } segtrack[1];
 223
 224         /*
 225          * NOTE: there should probably be a free list for each 'level'
 226          */
 227
 228         /* For scan */
 229         struct {
 230                 int     free_dev, free_block, free_stage;
 231                 int     first_free_pass;        /* true the first time */
 232                 int     done, do_decay; /* cleared on each checkpoint */
 233                 struct  datablock *youth_db, *usage0_db;
 234                 u16     *free_usages; /* This is an allocated page */
 235                 int     trace;
 236         } scan;
 237
 238         /* quotas. */
 239         int     qphase; /* like phase, but switches later in qflush */
 240         struct list_head flush_list; /* list of qents that need flushing */
 241         struct list_head qhash[QHASHSIZE];
 242
 243         struct backing_dev_info bdi;
 244         struct fs_dev {
 245                 struct block_device *bdev;
 246                 struct lafs_dev *devblk;
 247
 248                 u64     start, size;
 249                 u64     devaddr[2];
 250                 u64     stateaddr[4];
 251
 252                 u32     width, stride;
 253                 u32     segment_size;
 254                 u32     segment_offset;
 255                 u32     segment_stride;
 256                 u32     segment_count;
 257                 u32     usage_inum;
 258                 u16     level;
 259
 260                 u32     rows_per_table, tables_per_seg;
 261
 262                 int     recent_dev, recent_state;
 263
 264                 int     tablesize; /* in segusage file, not in segments */
 265                 struct inode *segsum;
 266         } *devs;
 267
 268         struct wc {
 269                 /* A 'write-cluster' descriptor
 270                  * Any write-cluster that we are in the process of
 271                  * building has this structure to describe it.
 272                  * We gather dirty blocks and keep track of cluster-header usage
 273                  */
 274                 struct skippoint slhead;        /* skiplist of pending blocks */
 275                 struct list_head clhead;        /* list of pending blocks (linked
 276                                                  * on ->lru */
 277
 278                 struct mutex lock;
 279
 280                 struct page     *page[4];/* a page which the cluster-head is built
 281                                           * in - never in high-memory */
 282                 struct cluster_head *chead; /* the cluster head == page */
 283                 int             chead_blocks; /* blocks allocated for cluster head */
 284                 int             cluster_space; /* space remaining in cluster_head
 285                                                 * after current commitments
 286                                                 */
 287                 int             chead_size;     /* space used already in cluster_head
 288                                                  * new miniblock and allocation
 289                                                  * happen from here
 290                                                  */
 291                 int             remaining;      /* available space in segment */
 292
 293                 unsigned long long cluster_seq; /* seq number of next cluster*/
 294                 u64             prev_addr;      /* where previous cluster is */
 295
 296                 int             cnum; /* Which wc entry this is - needed for
 297                                        * finding the 'fs' from a 'wc' */
 298
 299                 /* We keep track of how many blocks are still in-flight
 300                  * for each cluster.  This allows us to know when data is
 301                  * safe on disk.
 302                  * The count included all blocks in the cluster - including
 303                  * those in the header - plus all those in the header of
 304                  * the next cluster, and possibly the one after (in the case
 305                  * of VerifyNext2).
 306                  * This implies that we need to track as many as 4 separate
 307                  * write cluster.  The one that is currently being built,
 308                  * and the previous 3.  We use a ring buffer with a pointer
 309                  * to the entry what is currently being built.
 310                  */
 311                 atomic_t        pending_cnt[4];
 312                 int             pending_vfy_type[4];
 313                 struct list_head pending_blocks[4];
 314                 int             pending_next;
 315                 wait_queue_head_t pending_wait;
 316
 317                 struct bio *bio; /* bio we are building */
 318                 u64 bio_virt;   /* next sector we can add to bio */
 319                 int bio_head;   /* True if current bio contains a header block */
 320                 int bio_which;  /* pending[X] entry for this bio */
 321                 struct request_queue *bio_queue; /* queue to unplug */
 322
 323                 struct segpos {
 324                         int             dev;
 325                         u32             num;
 326
 327                         u32 st_table, st_row;
 328                         u32 nxt_table, nxt_row;
 329                         u32 table, row, col;
 330
 331                 } seg;
 332         } wc[WC_NUM];
 333
 334         struct hlist_head stable[SHASHSIZE];
 335         spinlock_t stable_lock;
 336         int stable_changed; /* Flag so we can see if the table changed while
 337                              * we dropped a lock */
 338
 339         struct rename_roll {
 340                 struct rename_roll *next;
 341                 u32 key;
 342                 struct inode *dir, *inode;
 343                 int nlen;
 344                 char name[1];
 345         } *pending_renames;
 346
 347 };
 348
 349 static inline int test_phase_locked(struct fs *fs)
 350 {
 351         return fs->phase_locked > 0;
 352 }
 353
 354 /* There are two sorts of blocks, data blocks and index blocks.
 355  * Data blocks store the contents of files, including inode files.
 356  * So each inode is in a datablock.
 357  * Index blocks store index/indirect/extent blocks. As inodes often
 358  * contain index information, Inode will usually have an index block aswell.
 359  *
 360  * Data blocks are stored in an address space and are indexed by inode and offset.
 361  * Index blocks are indexed by inode, depth, and offset.  The "depth" is
 362  * distance from data, so indirect and extent blocks have depth of 1.
 363  * This index doesn't often change.
 364  *
 365  * All blocks have a pointer to their parent, which is an index block (except
 366  * for inodes?).
 367  * All index blocks have a linked list of children which is used to find children
 368  * to move when the block is split.
 369  * There are also lists of children with pending changes to incorporate.
 370  *
 371  * A datablock for an inode points to the struct inode.
 372  * The struct inode points to the index block for the inode
 373  * The index block points to the datablock through the "parent" pointer.
 374  */
 375
 376 struct block {
 377         unsigned long           flags;
 378         unsigned long           fileaddr;
 379         struct inode            *inode;
 380         atomic_t                refcnt;
 381         u64                     physaddr;
 382
 383         struct indexblock       *parent;
 384         struct list_head        siblings; /* Next unreachable block in the same
 385                                     * reachability-set as this block
 386                                     */
 387
 388         struct list_head        lru; /* phase_leafs, clean_leafs, account_leafs,
 389                                       * clhead, pending_blocks */
 390
 391         struct list_head        peers;  /* other blocks that use the same location
 392                                          * in storage (i.e. in another snapshot)
 393                                          */
 394
 395         struct block            *chain; /* on list of unincorporated changes, or list of blocks
 396                                          * being read in */
 397
 398 #if DEBUG_REF
 399         struct ref {int cnt; char *name; } holders[16];
 400 #endif
 401 #if DEBUG_IOLOCK
 402         /* More debugging */
 403         char *iolock_file;
 404         int iolock_line;
 405 #endif
 406 };
 407 struct datablock {
 408         struct block b;
 409         struct page             *page;
 410         u32     orphan_slot;    /* slot in orphan file to record that this
 411                                  * block is an orphan
 412                                  */
 413         union {
 414                 /* If a block is both an orphan and undergoing
 415                  * cleaning, it lives on the cleaning list until
 416                  * the cleaner has checked it.  It is then moved
 417                  * to the pending_orphans list.
 418                  */
 419                 struct list_head orphans; /* linked list of blocks needing orphan
 420                                            * processing.
 421                                            */
 422                 struct list_head cleaning; /* list of blocks being cleaned.
 423                                             */
 424         };
 425         union {
 426                 struct inode *my_inode; /* only valid for block holding an inode */
 427         };
 428 };
 429 struct indexblock {
 430         struct block            b;
 431         char *                  data;
 432         struct hlist_node       hash;
 433         int                     depth;
 434
 435         struct list_head        children;
 436
 437         /*
 438          * pincnt[p] is the number of pinned blocks in phase 'p' which
 439          * have us as their ->parent.
 440          */
 441         atomic_t                pincnt[2];
 442
 443         /* Addresses that need to be incorporated in the current
 444          * phase are stored in an extent table until incorporation
 445          * which gets scheduled when the table is full.
 446          * Index block are kept on an list.
 447          * Blocks in the next phase are kept on a list until
 448          * the phase moves past and incorporation can be considered.
 449          */
 450         struct uninc {
 451                 int credits;    /* Number of uninc credits still available */
 452                 int pending_cnt; /* number of valid entries in pending_addr */
 453                 /* The number of extents in pending_addr must be at most
 454                  * half the number of extents that can fit into an extent
 455                  * block.  At 512 bytes, 512/12 == 42.  So now more than
 456                  * 21.  See do_incorporate_leaf
 457                  */
 458                 struct addr {
 459                         u32 fileaddr;
 460                         u32 cnt;
 461                         u64 physaddr;
 462                 } pending_addr[8];
 463         } uninc_table;
 464         /* If this is internal (depth>1) the actual block are kept on this list*/
 465         struct block            *uninc;
 466
 467         /* these are all in the next phase.  On phase-change,
 468          * we copy all the addresses into the uninc_table
 469          * and free the blocks
 470          */
 471         struct block            *uninc_next;
 472 };
 473
 474 #define iblk(__bl) container_of(__bl, struct indexblock, b)
 475 #define dblk(__bl) container_of(__bl, struct datablock, b)
 476
 477 enum {
 478         /* NOTE: 32 flags in used.  Need to overlap 'data' with 'index' if
 479          * we need much more
 480          */
 481         /* First flags that are meaningful for both Data and Index blocks
 482          * Currently 22 */
 483         B_Phase1 = 0,   /* phase when pinned  - must be '1' - used for indexing */
 484         B_Dirty,        /* block has changes which haven't been committed */
 485         B_Index,        /* This is an index block, not a data block */
 486         B_Linked,       /* block is known to be linked with all peers */
 487
 488         B_Realloc,      /* If set on a B_Dirty block, it was only dirtied for
 489                          * cleaning purposes and so should be written to the
 490                          * cleaner segment.
 491                          */
 492         B_Valid,        /* block contains valid data */
 493         B_Uninc,        /* on ->unincorporated list for next phase, so we
 494                          * cannot free it just yet.*/
 495         B_InoIdx,       /* is the index block for an inode */
 496         B_Pinned,       /* B_Phase1 is meaningful and block must be written
 497                          * (if dirty) in this phase
 498                          */
 499         B_Async,          /* An async IO is pending on this block */
 500         B_Root,         /* data or index block for root. ->parent is NULL */
 501
 502         B_SegRef,       /* holds a reference on segment of physaddr */
 503         B_Credit,       /* data block with space preallocated */
 504         B_ICredit,      /* index space preallocated for data block */
 505         B_NCredit,      /* Credit for next phase */
 506
 507         B_NICredit,     /* ICredit for next phase */
 508         B_UnincCredit,  /* Uninc carries a credit */
 509         B_IOLock,       /* Block is undergoing IO */
 510         B_Writeback,    /* Block is in a cluster */
 511         B_IOLockLock,   /* lock while testing IOLock on a page */
 512
 513         B_WriteError,   /* Got a write error while writing (when else?) */
 514         B_PhysValid,    /* ->physaddr is correct */
 515
 516         /* Flags that are only relevant for Data Block
 517          * currently 7 */
 518
 519         B_PinPending,    /* set on data blocks while checkpoint_locked if we might
 520                            * want to mark them dirty
 521                            */
 522         B_Prealloc,     /* This data block has physaddr==0 and has been counted
 523                          * in various ablock counters.
 524                          */
 525         B_Orphan,       /* ->orphan_slot is valid */
 526
 527         B_HaveLock,     /* We own the page lock and when all blocks are unlocked,
 528                          * the page should be unlocked */
 529         B_HaveWriteback,/* We own the page writeback flag and when all blocks
 530                          * are unlocked we should clear it. */
 531         B_Claimed,      /* Used for exclusive allocation of inodes */
 532         B_Cleaning,     /* Used by cleaner to track which blocks it has a
 533                          * reference on already. */
 534
 535         /* Flags that are only relevant for Index Blocks
 536          * currently 3 */
 537         B_OnFree,       /* index block on the free list */
 538         B_PrimaryRef,   /* This indexblock has not been incorporated into the
 539                          * parent, and so can only be found by being a sibling
 540                          * of a 'primary' which is incorporated.  Consequently
 541                          * a counted reference is held on ->siblings.prev,
 542                          * which is either the primary or another block holding
 543                          * a PrimaryRef.
 544                          */
 545         B_EmptyIndex,   /* Index block is empty, has no (non-EmptyIndex) children,
 546                          * will be destroyed soon.  Indexing must avoid it
 547                          * unless if the first child of parent.
 548                          * Gets allocated to '0'.
 549                          * Flag only set under B_IOLock.
 550                          */
 551
 552         B_NUM_FLAGS
 553 };
 554 /* indexing info stays in the block, not in the inode */
 555 struct lafs_inode {
 556         struct inode    vfs_inode;
 557         struct indexblock       *iblock;
 558         struct datablock        *dblock;
 559         long    cblocks, /* data blocks which are commited to this file */
 560                 pblocks, /* extra data blocks that are commited in next phase */
 561                 ablocks, /* data blocks that are allocated */
 562
 563                 ciblocks, /* index blocks commited */
 564                 piblocks; /* index blocks in next phase */
 565         unsigned long   iflags;
 566 #define I_Phase1 1      /* set to 'this' phase when iblocks correct */
 567 #define I_Dirty 2
 568 #define I_Deleting 3    /* preserve the inode while truncate-on-delete happens */
 569 #define I_Destroyed 4   /* inode destroy has been delayed */
 570 #define I_Trunc 5       /* a truncation is in process */
 571 #define I_Pinned 6      /* InoIdx is pinned, i_nlink is non-zero, and consequently
 572                          * we own an extra ref to the inode and superblock.
 573                          */
 574 /* next three indicate if we hold a reference on the relevant qent */
 575 #define I_QUid  8
 576 #define I_QGid  9
 577 #define I_QTid  10
 578
 579         struct rw_semaphore ind_sem;
 580         unsigned long long update_cluster;
 581
 582 /*      int             generation; */
 583         int             trunc_gen;
 584         int             flags;
 585         int             type;
 586         int             metadata_size;
 587         int             depth;
 588
 589         struct list_head        free_index;
 590
 591         loff_t          trunc_next; /* next block to truncate from */
 592         union {
 593                 struct fs_md {
 594                         int     usagetable;   /* 0 and unused for subsets,
 595                                                * 1 for main fs, >1 for snapshots
 596                                                */
 597                         u64     cblocks_used; /* blocks commited */
 598                         u64     pblocks_used; /* extra blocks in next phase */
 599                         u64     ablocks_used; /* extra blocks allocated */
 600                         u64     blocks_allowed;
 601                         u64     blocks_unalloc; /* FIXME what is this for ?? */
 602
 603                         u64     creation_age;
 604                         u32     inodes_used;
 605                         u32     quota_inums[3];
 606                         struct inode *quota_inodes[3];
 607                         char    *name;
 608                 } fs;
 609                 struct inodemap_md {
 610                         u32     size;
 611                         /* These are state use to manage inum allocation */
 612                         u32     thisblock;
 613                         int     nextbit; /* bit in nextblock-1 to check next */
 614                 } inodemap;
 615                 struct su_md {
 616                         u32     table_size;     /* (blocks) */
 617                 } segmentusage;
 618                 struct file_md {
 619                         u16     flags;
 620 /*                      u16     mode; */
 621 /*                      u32     uid; */
 622 /*                      u32     gid; */
 623                         u32     treeid;
 624                         u64     creationtime;
 625 /*                      u64     modifytime; */
 626 /*                      u64     ctime; */
 627 /*                      u64     accesstime; */
 628                         struct timespec i_accesstime; /* as stored in inode */
 629 /*                      u64     size; */
 630                         u32     parent;
 631 /*                      u32     linkcount; */
 632                         /* for directories */
 633                         u32     seed;
 634                 } file;
 635                 struct orphan_md {
 636                         u32     nextfree;
 637                         u32     reserved;
 638                 } orphan;
 639                 struct quota_md {
 640                         u32     gracetime; /* multiplier for graceunits */
 641                         u32     graceunits; /* seconds per unit */
 642                 } quota;
 643
 644                 /* We free inodes using rcu, by which time any
 645                  * metadata is irrelevant and the type is zero
 646                  */
 647                 struct rcu_head rcu;
 648         } md;
 649 };
 650
 651 static inline struct lafs_inode *LAFSI(struct inode *in)
 652 {
 653         return container_of(in, struct lafs_inode, vfs_inode);
 654 }
 655