kern/src/ext2fs.c

   1 /* Copyright (c) 2010 The Regents of the University of California
   2  * Barret Rhoden <brho@cs.berkeley.edu>
   3  * See LICENSE for details.
   4  *
   5  * Ext2, VFS required functions, internal functions, life, the universe, and
   6  * everything! */
   7
   8 #include <vfs.h>
   9 #include <ext2fs.h>
  10 #include <blockdev.h>
  11 #include <kmalloc.h>
  12 #include <assert.h>
  13 #include <kref.h>
  14 #include <endian.h>
  15 #include <error.h>
  16 #include <pmap.h>
  17 #include <bitmask.h>
  18
  19 /* These structs are declared again and initialized farther down */
  20 struct page_map_operations ext2_pm_op;
  21 struct super_operations ext2_s_op;
  22 struct inode_operations ext2_i_op;
  23 struct dentry_operations ext2_d_op;
  24 struct file_operations ext2_f_op_file;
  25 struct file_operations ext2_f_op_dir;
  26 struct file_operations ext2_f_op_sym;
  27
  28 /* EXT2 Internal Functions */
  29
  30 /* Useful helper functions. */
  31
  32 /* Returns the block group ID of the BG containing the inode.  BGs start with 0,
  33  * inodes are indexed starting at 1. */
  34 static struct ext2_block_group *ext2_inode2bg(struct inode *inode)
  35 {
  36         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)inode->i_sb->s_fs_info;
  37         unsigned int bg_num = (inode->i_ino - 1) /
  38                               le32_to_cpu(e2sbi->e2sb->s_inodes_per_group);
  39         return &e2sbi->e2bg[bg_num];
  40 }
  41
  42 /* This returns the inode's 0-index within a block group */
  43 static unsigned int ext2_inode2bgidx(struct inode *inode)
  44 {
  45         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)inode->i_sb->s_fs_info;
  46         return (inode->i_ino - 1) % le32_to_cpu(e2sbi->e2sb->s_inodes_per_group);
  47 }
  48
  49 /* Returns the inode number given a 0-index of an inode within a block group */
  50 static unsigned long ext2_bgidx2ino(struct super_block *sb,
  51                                     struct ext2_block_group *bg,
  52                                     unsigned int ino_idx)
  53 {
  54         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)sb->s_fs_info;
  55         struct ext2_sb *e2sb = e2sbi->e2sb;
  56         struct ext2_block_group *e2bg = e2sbi->e2bg;
  57         return (bg - e2bg) * le32_to_cpu(e2sb->s_inodes_per_group) + ino_idx + 1;
  58 }
  59
  60 /* Returns an uncounted reference to the BG in the BG table, which is pinned,
  61  * hanging off the sb.  Note, the BGs cover the blocks starting from the first
  62  * data block, not from 0.  So if the FDB is 1, BG 0 covers 1 through 1024, and
  63  * not 0 through 1023. */
  64 static struct ext2_block_group *ext2_block2bg(struct super_block *sb,
  65                                               uint32_t blk_num)
  66 {
  67         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)sb->s_fs_info;
  68         unsigned int bg_num;
  69         bg_num = (blk_num - le32_to_cpu(e2sbi->e2sb->s_first_data_block)) /
  70                  le32_to_cpu(e2sbi->e2sb->s_blocks_per_group);
  71         return &e2sbi->e2bg[bg_num];
  72 }
  73
  74 /* This returns the block's 0-index within a block group.  Note all blocks are
  75  * offset by FDB when dealing with BG membership. */
  76 static unsigned int ext2_block2bgidx(struct super_block *sb, uint32_t blk_num)
  77 {
  78         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)sb->s_fs_info;
  79         return (blk_num - le32_to_cpu(e2sbi->e2sb->s_first_data_block)) %
  80                le32_to_cpu(e2sbi->e2sb->s_blocks_per_group);
  81 }
  82
  83 /* Returns the FS block for the given BG's idx block */
  84 static uint32_t ext2_bgidx2block(struct super_block *sb,
  85                                  struct ext2_block_group *bg,
  86                                  unsigned int blk_idx)
  87 {
  88         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)sb->s_fs_info;
  89         struct ext2_sb *e2sb = e2sbi->e2sb;
  90         struct ext2_block_group *e2bg = e2sbi->e2bg;
  91         return (bg - e2bg) * le32_to_cpu(e2sb->s_blocks_per_group) + blk_idx +
  92                le32_to_cpu(e2sb->s_first_data_block);
  93 }
  94
  95 /* Slabs for ext2 specific info chunks */
  96 struct kmem_cache *ext2_i_kcache;
  97
  98 /* One-time init for all ext2 instances */
  99 void ext2_init(void)
 100 {
 101         ext2_i_kcache = kmem_cache_create("ext2_i_info", sizeof(struct ext2_i_info),
 102                                           __alignof__(struct ext2_i_info), 0, 0, 0);
 103 }
 104
 105 /* Block management */
 106
 107 /* TODO: pull these metablock functions out of ext2 */
 108 /* Makes sure the FS block of metadata is in memory.  This returns a pointer to
 109  * the beginning of the requested block.  Release it with put_metablock().
 110  * Internally, the kreffing is done on the page. */
 111 void *__ext2_get_metablock(struct block_device *bdev, unsigned long blk_num,
 112                            unsigned int blk_sz)
 113 {
 114         return bdev_get_buffer(bdev, blk_num, blk_sz)->bh_buffer;
 115 }
 116
 117 /* Convenience wrapper */
 118 void *ext2_get_metablock(struct super_block *sb, unsigned long block_num)
 119 {
 120         return __ext2_get_metablock(sb->s_bdev, block_num, sb->s_blocksize);
 121 }
 122
 123 /* Helper to figure out the BH for any address within it's buffer */
 124 static struct buffer_head *ext2_my_bh(struct super_block *sb, void *addr)
 125 {
 126         struct page *page = kva2page(addr);
 127         struct buffer_head *bh = (struct buffer_head*)page->pg_private;
 128         /* This case is for when we try do decref a non-BH'd 'metablock'.  It's tied
 129          * to e2ii->i_block[]. */
 130         if (!bh)
 131                 return 0;
 132         void *my_buf = (void*)ROUNDDOWN((uintptr_t)addr, sb->s_blocksize);
 133         while (bh) {
 134                 if (bh->bh_buffer == my_buf)
 135                         break;
 136                 bh = bh->bh_next;
 137         }
 138         assert(bh && bh->bh_buffer == my_buf);
 139         return bh;
 140 }
 141
 142 /* Decrefs the buffer from get_metablock().  Call this when you no longer
 143  * reference your metadata block/buffer.  Yes, we could just decref the page,
 144  * but this will work if we end up changing how bdev_put_buffer() works. */
 145 void ext2_put_metablock(struct super_block *sb, void *buffer)
 146 {
 147         struct buffer_head *bh = ext2_my_bh(sb, buffer);
 148         if (bh)
 149                 bdev_put_buffer(bh);
 150 }
 151
 152 /* Will dirty the block/BH/page for the given metadata block/buffer. */
 153 void ext2_dirty_metablock(struct super_block *sb, void *buffer)
 154 {
 155         struct buffer_head *bh = ext2_my_bh(sb, buffer);
 156         if (bh)
 157                 bdev_dirty_buffer(bh);
 158 }
 159
 160 /* Helper for alloc_block.  It will try to alloc a block from the BG, starting
 161  * with blk_idx (relative number within the BG).   If successful, it will return
 162  * the FS block number via *block_num.  TODO: concurrency protection */
 163 static bool ext2_tryalloc(struct super_block *sb, struct ext2_block_group *bg,
 164                           unsigned int blk_idx, uint32_t *block_num)
 165 {
 166         uint8_t *blk_bitmap;
 167         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)sb->s_fs_info;
 168         unsigned int blks_per_bg = le32_to_cpu(e2sbi->e2sb->s_blocks_per_group);
 169         bool found = FALSE;
 170
 171         /* Check to see if there are any free blocks */
 172         if (!le32_to_cpu(bg->bg_free_blocks_cnt))
 173                 return FALSE;
 174         /* Check the bitmap for your desired block.  We'll loop through the whole
 175          * BG, starting with the one we want first. */
 176         blk_bitmap = ext2_get_metablock(sb, bg->bg_block_bitmap);
 177         for (int i = 0; i < blks_per_bg; i++) {
 178                 if (!(GET_BITMASK_BIT(blk_bitmap, blk_idx))) {
 179                         SET_BITMASK_BIT(blk_bitmap, blk_idx);
 180                         bg->bg_free_blocks_cnt--;
 181                         ext2_dirty_metablock(sb, blk_bitmap);
 182                         found = TRUE;
 183                         break;
 184                 }
 185                 /* Note: the wrap-around hasn't been tested yet */
 186                 blk_idx = (blk_idx + 1) % blks_per_bg;
 187         }
 188         ext2_put_metablock(sb, blk_bitmap);
 189         if (found)
 190                 *block_num = ext2_bgidx2block(sb, bg, blk_idx);
 191         return found;
 192 }
 193
 194 /* This allocates a fresh block for the inode, preferably 'fetish' (name
 195  * courtesy of L.F.), returning the FS block number that's been allocated.
 196  * Note, Linux does some block preallocation here.  Consider doing the same (off
 197  * the in-memory inode).  Note the lack of concurrency protections here. */
 198 uint32_t ext2_alloc_block(struct inode *inode, uint32_t fetish)
 199 {
 200         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)inode->i_sb->s_fs_info;
 201         struct ext2_block_group *fetish_bg, *bg_i = e2sbi->e2bg;
 202         unsigned int blk_idx;
 203         bool found = FALSE;
 204         uint32_t retval = 0;
 205
 206         /* Get our ideal starting point */
 207         fetish_bg = ext2_block2bg(inode->i_sb, fetish);
 208         blk_idx = ext2_block2bgidx(inode->i_sb, fetish);
 209         /* Try to find a free block in the BG of the one we desire */
 210         found = ext2_tryalloc(inode->i_sb, fetish_bg, blk_idx, &retval);
 211         if (found)
 212                 return retval;
 213
 214         warn("This part hasn't been tested yet.");
 215         /* Find a block anywhere else (perhaps using the log trick, but for now just
 216          * linearly scanning). */
 217         for (int i = 0; i < e2sbi->nr_bgs; i++, bg_i++) {
 218                 if (bg_i == fetish_bg)
 219                         continue;
 220                 found = ext2_tryalloc(inode->i_sb, bg_i, 0, &retval);
 221                 if (found)
 222                         break;
 223         }
 224         if (!found)
 225                 panic("Ran out of blocks! (probably a bug)");
 226         return retval;
 227 }
 228
 229 /* Inode Management */
 230
 231 /* Helper for alloc_diskinode.  It will try to alloc a disk inode from the BG.
 232  * If successful, it will return the inode number in *ino_num.  TODO:
 233  * concurrency protection */
 234 static bool ext2_tryalloc_diskinode(struct super_block *sb,
 235                                     struct ext2_block_group *bg,
 236                                     unsigned long *ino_num)
 237 {
 238         uint8_t *ino_bitmap;
 239         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)sb->s_fs_info;
 240         unsigned int i, ino_per_bg = le32_to_cpu(e2sbi->e2sb->s_inodes_per_group);
 241         bool found = FALSE;
 242
 243         /* Check to see if there are any free inodes */
 244         if (!le32_to_cpu(bg->bg_free_inodes_cnt))
 245                 return FALSE;
 246         /* Check the bitmap for the free inode */
 247         ino_bitmap = ext2_get_metablock(sb, bg->bg_inode_bitmap);
 248         for (i = 0; i < ino_per_bg; i++) {
 249                 if (!(GET_BITMASK_BIT(ino_bitmap, i))) {
 250                         SET_BITMASK_BIT(ino_bitmap, i);
 251                         bg->bg_free_inodes_cnt--;
 252                         ext2_dirty_metablock(sb, ino_bitmap);
 253                         found = TRUE;
 254                         break;
 255                 }
 256         }
 257         ext2_put_metablock(sb, ino_bitmap);
 258         /* Convert the i (a 0-index bit)  within the BG to a real inode number. */
 259         if (found)
 260                 *ino_num = ext2_bgidx2ino(sb, bg, i);
 261         return found;
 262 }
 263
 264 /* This allocates a fresh ino number for inode, given the parent's BG.  Make
 265  * sure you set the inode's type before calling this, since it matters if we a
 266  * making a directory or not.  This disk inode is reserved on disk in the bitmap
 267  * (at least the bitmap is changed and dirtied).  Note the lack of concurrency
 268  * protections here.  Consider returning the BG too. */
 269 unsigned long ext2_alloc_diskinode(struct inode *inode,
 270                                    struct ext2_block_group *dir_bg)
 271 {
 272         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)inode->i_sb->s_fs_info;
 273         struct ext2_block_group *bg = dir_bg;
 274         struct ext2_block_group *bg_i = e2sbi->e2bg;
 275         bool found = FALSE;
 276         unsigned long retval = 0;
 277
 278         if (S_ISDIR(inode->i_mode)) {
 279                 /* TODO: intelligently pick a different bg to use than the current one.
 280                  * Right now, we just jump to the next one, though you should do things
 281                  * like take into account the ratio of directories to files. */
 282                 bg += 1;
 283         }
 284         /* Try to find a free inode in the chosen BG */
 285         found = ext2_tryalloc_diskinode(inode->i_sb, bg, &retval);
 286         if (found)
 287                 return retval;
 288
 289         warn("This part hasn't been tested yet.");
 290         /* Find an inode anywhere else (perhaps using the log trick, but for now just
 291          * linearly scanning). */
 292         for (int i = 0; i < e2sbi->nr_bgs; i++, bg_i++) {
 293                 if (bg_i == bg)
 294                         continue;
 295                 found = ext2_tryalloc_diskinode(inode->i_sb, bg_i, &retval);
 296                 if (found)
 297                         break;
 298         }
 299         if (!found)
 300                 panic("Ran out of inodes! (probably a bug)");
 301         return retval;
 302 }
 303
 304 /* Helper for ino table management.  blkid is the inode table block we are
 305  * looking in, rel_blkid is the block we want, relative to the current
 306  * threshhold for a level of indirection, and reach is how many items a given
 307  * slot indexes.  Returns a pointer to the slot for the given block. */
 308 static uint32_t *ext2_find_inotable_slot(struct inode *inode, uint32_t blkid,
 309                                          uint32_t rel_blkid,
 310                                          unsigned int reach)
 311 {
 312         uint32_t *blk_buf = ext2_get_metablock(inode->i_sb, blkid);
 313         assert(blk_buf);
 314         return &blk_buf[rel_blkid / reach];
 315 }
 316
 317 /* If blk_slot is empty (no block mapped there) it will alloc and link a new
 318  * block.  This is only used for allocating a block to be an indirect table
 319  * (it's grabbing a metablock, we have no hint, and it handles the buffer
 320  * differently than for a file page/buffer). */
 321 static void ext2_fill_inotable_slot(struct inode *inode, uint32_t *blk_slot)
 322 {
 323         uint32_t new_blkid, hint_blk;
 324         void *new_blk;
 325
 326         if (le32_to_cpu(*blk_slot))
 327                 return;
 328         /* Use any block in our inode's BG as a hint for the indirect block */
 329         hint_blk = ext2_bgidx2block(inode->i_sb, ext2_inode2bg(inode), 0);
 330         new_blkid = ext2_alloc_block(inode, hint_blk);
 331         /* Actually read in the block we alloc'd */
 332         new_blk = ext2_get_metablock(inode->i_sb, new_blkid);
 333         memset(new_blk, 0, inode->i_sb->s_blocksize);
 334         ext2_dirty_metablock(inode->i_sb, new_blk);
 335         /* We put it, despite it getting relooked up in the next walk */
 336         ext2_put_metablock(inode->i_sb, new_blk);
 337         /* Now write the new block into its slot */
 338         *blk_slot = cpu_to_le32(new_blkid);
 339         ext2_dirty_metablock(inode->i_sb, blk_slot);
 340 }
 341
 342 /* This walks a table stored at block 'blkid', returning which block you should
 343  * walk next in 'blkid'.  rel_inoblk is where you are given the current level of
 344  * indirection tables, and returns where you should be for the next one.  Reach
 345  * is how many items the current table's *items* can index (so if we're on a
 346  * 3x indir block, reach should be for the doubly-indirect entries, and
 347  * rel_inoblk will tell you where within that double block you want).
 348  *
 349  * This will also alloc intermediate tables if there isn't one already (TODO:
 350  * concurrency protection on modifying the table). */
 351 static void ext2_walk_inotable(struct inode *inode, uint32_t *blkid,
 352                                uint32_t *rel_inoblk, unsigned int reach)
 353 {
 354         uint32_t *blk_slot;
 355         blk_slot = ext2_find_inotable_slot(inode, *blkid, *rel_inoblk, reach);
 356         /* We could only do this based on a bool, but if we're trying to walk it,
 357          * we ought to want to alloc if there is no block. */
 358         ext2_fill_inotable_slot(inode, blk_slot);
 359         *blkid = le32_to_cpu(*blk_slot);
 360         *rel_inoblk = *rel_inoblk % reach;
 361         ext2_put_metablock(inode->i_sb, blk_slot);      /* ref for the one looked in */
 362 }
 363
 364 /* Finds the slot of the FS block corresponding to a specific block number of an
 365  * inode.  It does this by walking the inode's tables.  The general idea is that
 366  * if the ino_block num is above a threshold, we'll need to go into indirect
 367  * tables (1x, 2x, or 3x (triply indirect) tables).  Block numbers start at 0.
 368  *
 369  * This returns a pointer within a metablock, which needs to be decref'd (and
 370  * possibly dirtied) when you are done.  Note, it can return a pointer to
 371  * something that is NOT in a metablock (e2ii->i_block[]), but put_metablock can
 372  * handle it for now.
 373  *
 374  * Horrendously untested, btw. */
 375 uint32_t *ext2_lookup_inotable_slot(struct inode *inode, uint32_t ino_block)
 376 {
 377         struct ext2_i_info *e2ii = (struct ext2_i_info*)inode->i_fs_info;
 378
 379         uint32_t blkid, *blk_slot;
 380         /* The 'reach' is how many blocks a given table can 'address' */
 381         int ptrs_per_blk = inode->i_sb->s_blocksize / sizeof(uint32_t);
 382         int reach_1xblk = ptrs_per_blk;
 383         int reach_2xblk = ptrs_per_blk * ptrs_per_blk;
 384         /* thresholds are the first blocks that require a level of indirection */
 385         int single_threshold = 12;
 386         int double_threshold = single_threshold + reach_1xblk;
 387         int triple_threshold = double_threshold + reach_2xblk;
 388         /* this is the desired block num lookup within a level of indirection.  It
 389          * will need to be offset based on what level of lookups we want (try it in
 390          * your head with 12 first). */
 391         uint32_t rel_inoblk;
 392
 393         if (ino_block >= triple_threshold) {
 394                 /* ino_block requires a triply-indirect lookup */
 395                 rel_inoblk = ino_block - triple_threshold;
 396                 /* Make sure a 14 block (3x indirect) is there */
 397                 ext2_fill_inotable_slot(inode, &e2ii->i_block[14]);
 398                 blkid = e2ii->i_block[14];
 399                 ext2_walk_inotable(inode, &blkid, &rel_inoblk, reach_2xblk);
 400                 ext2_walk_inotable(inode, &blkid, &rel_inoblk, reach_1xblk);
 401                 blk_slot = ext2_find_inotable_slot(inode, blkid, rel_inoblk, 1);
 402         } else if (ino_block >= double_threshold) {
 403                 /* ino_block requires a doubly-indirect lookup  */
 404                 rel_inoblk = ino_block - double_threshold;
 405                 ext2_fill_inotable_slot(inode, &e2ii->i_block[13]);
 406                 blkid = e2ii->i_block[13];
 407                 ext2_walk_inotable(inode, &blkid, &rel_inoblk, reach_1xblk);
 408                 blk_slot = ext2_find_inotable_slot(inode, blkid, rel_inoblk, 1);
 409         } else if (ino_block >= single_threshold) {
 410                 /* ino_block requires a singly-indirect lookup */
 411                 rel_inoblk = ino_block - single_threshold;
 412                 ext2_fill_inotable_slot(inode, &e2ii->i_block[12]);
 413                 blkid = e2ii->i_block[12];
 414                 blk_slot = ext2_find_inotable_slot(inode, blkid, rel_inoblk, 1);
 415         } else {
 416                 /* Direct block, straight out of the inode */
 417                 blk_slot = &e2ii->i_block[ino_block];
 418         }
 419         return blk_slot;
 420 }
 421
 422 /* Determines the FS block id for a given inode block id.  Convenience wrapper
 423  * that may go away soon. */
 424 uint32_t ext2_find_inoblock(struct inode *inode, unsigned int ino_block)
 425 {
 426         uint32_t retval, *buf = ext2_lookup_inotable_slot(inode, ino_block);
 427         retval = *buf;
 428         ext2_put_metablock(inode->i_sb, buf);
 429         return retval;
 430 }
 431
 432 /* Returns an incref'd metadata block for the contents of the ino block.  Don't
 433  * use this for regular files - use their inode's page cache instead (used for
 434  * directories for now).  If there isn't a block allocated yet, it will provide
 435  * a zeroed one. */
 436 void *ext2_get_ino_metablock(struct inode *inode, unsigned long ino_block)
 437 {
 438         uint32_t blkid, *retval, *blk_slot;
 439         blk_slot = ext2_lookup_inotable_slot(inode, ino_block);
 440         blkid = le32_to_cpu(*blk_slot);
 441         if (blkid) {
 442                 ext2_put_metablock(inode->i_sb, blk_slot);
 443                 return ext2_get_metablock(inode->i_sb, blkid);
 444         }
 445         /* If there isn't a block there, alloc and insert one.  This block will be
 446          * the next big chunk of "file" data for this inode. */
 447         blkid = ext2_alloc_block(inode, ext2_bgidx2block(inode->i_sb,
 448                                                          ext2_inode2bg(inode),
 449                                                          0));
 450         *blk_slot = cpu_to_le32(blkid);
 451         ext2_dirty_metablock(inode->i_sb, blk_slot);
 452         ext2_put_metablock(inode->i_sb, blk_slot);
 453         inode->i_blocks += inode->i_sb->s_blocksize >> 9;       /* inc by 1 FS block */
 454         inode->i_size += inode->i_sb->s_blocksize;
 455         retval = ext2_get_metablock(inode->i_sb, blkid);
 456         memset(retval, 0, inode->i_sb->s_blocksize);            /* 0 the new block */
 457         return retval;
 458 }
 459
 460 /* This should help with degubbing.  In read_inode(), print out the i_block, and
 461  * consider manually (via memory inspection) examining those blocks.  Odds are,
 462  * the 2x and 3x walks are jacked up. */
 463 void ext2_print_ino_blocks(struct inode *inode)
 464 {
 465         printk("Inode %08p, Size: %d, 512B 'blocks': %d\n-------------\n", inode,
 466                inode->i_size, inode->i_blocks);
 467         for (int i = 0; i < inode->i_blocks * (inode->i_sb->s_blocksize / 512); i++)
 468                 printk("# %03d, Block %03d\n", i, ext2_find_inoblock(inode, i));
 469 }
 470
 471 /* Misc Functions */
 472
 473 /* This checks an ext2 disc SB for consistency, optionally printing out its
 474  * stats.  It also will also read in a copy of the block group descriptor table
 475  * from its first location (right after the primary SB copy) */
 476 void ext2_check_sb(struct ext2_sb *e2sb, struct ext2_block_group *bg,
 477                    bool print)
 478 {
 479         int retval;
 480         unsigned int blksize, blks_per_group, num_blk_group, num_blks;
 481         unsigned int inodes_per_grp, inode_size;
 482         unsigned int sum_blks = 0, sum_inodes = 0;
 483
 484         assert(le16_to_cpu(e2sb->s_magic) == EXT2_SUPER_MAGIC);
 485         num_blks = le32_to_cpu(e2sb->s_blocks_cnt);
 486         blksize = 1024 << le32_to_cpu(e2sb->s_log_block_size);
 487         blks_per_group = le32_to_cpu(e2sb->s_blocks_per_group);
 488         num_blk_group = num_blks / blks_per_group + (num_blks % blks_per_group ? 1 : 0);
 489
 490         if (print) {
 491                 printk("EXT2 info:\n-------------------------\n");
 492                 printk("Total Inodes:     %8d\n", le32_to_cpu(e2sb->s_inodes_cnt));
 493                 printk("Total Blocks:     %8d\n", le32_to_cpu(e2sb->s_blocks_cnt));
 494                 printk("Num R-Blocks:     %8d\n", le32_to_cpu(e2sb->s_rblocks_cnt));
 495                 printk("Num Free Blocks:  %8d\n", le32_to_cpu(e2sb->s_free_blocks_cnt));
 496                 printk("Num Free Inodes:  %8d\n", le32_to_cpu(e2sb->s_free_inodes_cnt));
 497                 printk("First Data Block: %8d\n",
 498                        le32_to_cpu(e2sb->s_first_data_block));
 499                 printk("Block Size:       %8d\n",
 500                        1024 << le32_to_cpu(e2sb->s_log_block_size));
 501                 printk("Fragment Size:    %8d\n",
 502                        1024 << le32_to_cpu(e2sb->s_log_frag_size));
 503                 printk("Blocks per group: %8d\n",
 504                        le32_to_cpu(e2sb->s_blocks_per_group));
 505                 printk("Inodes per group: %8d\n",
 506                        le32_to_cpu(e2sb->s_inodes_per_group));
 507                 printk("Block groups:     %8d\n", num_blk_group);
 508                 printk("Mount state:      %8d\n", le16_to_cpu(e2sb->s_state));
 509                 printk("Rev Level:        %8d\n", le32_to_cpu(e2sb->s_minor_rev_level));
 510                 printk("Minor Rev Level:  %8d\n", le16_to_cpu(e2sb->s_minor_rev_level));
 511                 printk("Creator OS:       %8d\n", le32_to_cpu(e2sb->s_creator_os));
 512                 printk("First Inode:      %8d\n", le32_to_cpu(e2sb->s_first_ino));
 513                 printk("Inode size:       %8d\n", le16_to_cpu(e2sb->s_inode_size));
 514                 printk("This block group: %8d\n", le16_to_cpu(e2sb->s_block_group_nr));
 515                 printk("BG ID of 1st meta:%8d\n", le16_to_cpu(e2sb->s_first_meta_bg));
 516                 printk("Volume name:      %s\n", e2sb->s_volume_name);
 517                 printk("\nBlock Group Info:\n----------------------\n");
 518         }
 519
 520         for (int i = 0; i < num_blk_group; i++) {
 521                 sum_blks += le16_to_cpu(bg[i].bg_free_blocks_cnt);
 522                 sum_inodes += le16_to_cpu(bg[i].bg_free_inodes_cnt);
 523                 if (print) {
 524                         printk("*** BG %d at %08p\n", i, &bg[i]);
 525                         printk("Block bitmap:%8d\n", le32_to_cpu(bg[i].bg_block_bitmap));
 526                         printk("Inode bitmap:%8d\n", le32_to_cpu(bg[i].bg_inode_bitmap));
 527                         printk("Inode table: %8d\n", le32_to_cpu(bg[i].bg_inode_table));
 528                         printk("Free blocks: %8d\n", le16_to_cpu(bg[i].bg_free_blocks_cnt));
 529                         printk("Free inodes: %8d\n", le16_to_cpu(bg[i].bg_free_inodes_cnt));
 530                         printk("Used Dirs:   %8d\n", le16_to_cpu(bg[i].bg_used_dirs_cnt));
 531                 }
 532         }
 533
 534         /* Sanity Assertions.  A good ext2 will always pass these. */
 535         inodes_per_grp = le32_to_cpu(e2sb->s_inodes_per_group);
 536         blks_per_group = le32_to_cpu(e2sb->s_blocks_per_group);
 537         inode_size = le32_to_cpu(e2sb->s_inode_size);
 538         assert(le32_to_cpu(e2sb->s_inodes_cnt) <= inodes_per_grp * num_blk_group);
 539         assert(le32_to_cpu(e2sb->s_free_inodes_cnt) == sum_inodes);
 540         assert(le32_to_cpu(e2sb->s_blocks_cnt) <= blks_per_group * num_blk_group);
 541         assert(le32_to_cpu(e2sb->s_free_blocks_cnt) == sum_blks);
 542         if (blksize == 1024)
 543                 assert(le32_to_cpu(e2sb->s_first_data_block) == 1);
 544         else
 545                 assert(le32_to_cpu(e2sb->s_first_data_block) == 0);
 546         assert(inode_size <= blksize);
 547         assert(inode_size == 1 << LOG2_UP(inode_size));
 548         assert(blksize * 8 >= inodes_per_grp);
 549         assert(inodes_per_grp % (blksize / inode_size) == 0);
 550         if (print)
 551                 printk("Passed EXT2 Checks\n");
 552 }
 553
 554 /* VFS required Misc Functions */
 555
 556 /* Creates the SB.  Like with Ext2's, we should consider pulling out the
 557  * FS-independent stuff, if possible. */
 558 struct super_block *ext2_get_sb(struct fs_type *fs, int flags,
 559                                char *dev_name, struct vfsmount *vmnt)
 560 {
 561         struct block_device *bdev;
 562         struct ext2_sb *e2sb;
 563         struct ext2_block_group *e2bg;
 564         unsigned int blks_per_group, num_blk_group, num_blks;
 565
 566         static bool ran_once = FALSE;
 567         if (!ran_once) {
 568                 ran_once = TRUE;
 569                 ext2_init();
 570         }
 571         bdev = get_bdev(dev_name);
 572         assert(bdev);
 573         /* Read the SB.  It's always at byte 1024 and 1024 bytes long.  Note we do
 574          * not put the metablock (we pin it off the sb later).  Same with e2bg. */
 575         e2sb = (struct ext2_sb*)__ext2_get_metablock(bdev, 1, 1024);
 576         if (!(le16_to_cpu(e2sb->s_magic) == EXT2_SUPER_MAGIC)) {
 577                 warn("EXT2 Not detected when it was expected!");
 578                 return 0;
 579         }
 580         /* Read in the block group descriptor table.  Which block the BG table is on
 581          * depends on the blocksize */
 582         unsigned int blksize = 1024 << le32_to_cpu(e2sb->s_log_block_size);
 583         e2bg = __ext2_get_metablock(bdev, blksize == 1024 ? 2 : 1, blksize);
 584         assert(e2bg);
 585         ext2_check_sb(e2sb, e2bg, FALSE);
 586
 587         /* Now we build and init the VFS SB */
 588         struct super_block *sb = get_sb();
 589         sb->s_dev = 0;                  /* what do we really want here? */
 590         sb->s_blocksize = blksize;
 591         /* max file size for a 1024 blocksize FS.  good enough for now (TODO) */
 592         sb->s_maxbytes = 17247252480;
 593         sb->s_type = &ext2_fs_type;
 594         sb->s_op = &ext2_s_op;
 595         sb->s_flags = flags;    /* from the disc too?  which flags are these? */
 596         sb->s_magic = EXT2_SUPER_MAGIC;
 597         sb->s_mount = vmnt;     /* Kref?  also in KFS */
 598         sb->s_syncing = FALSE;
 599         kref_get(&bdev->b_kref, 1);
 600         sb->s_bdev = bdev;
 601         strlcpy(sb->s_name, "EXT2", 32);
 602         sb->s_fs_info = kmalloc(sizeof(struct ext2_sb_info), 0);
 603         assert(sb->s_fs_info);
 604         /* store the in-memory copy of the disk SB and bg desc table */
 605         ((struct ext2_sb_info*)sb->s_fs_info)->e2sb = e2sb;
 606         ((struct ext2_sb_info*)sb->s_fs_info)->e2bg = e2bg;
 607         /* Precompute the number of BGs */
 608         num_blks = le32_to_cpu(e2sb->s_blocks_cnt);
 609         blks_per_group = le32_to_cpu(e2sb->s_blocks_per_group);
 610         ((struct ext2_sb_info*)sb->s_fs_info)->nr_bgs = num_blks / blks_per_group +
 611                                                (num_blks % blks_per_group ? 1 : 0);
 612
 613         /* Final stages of initializing the sb, mostly FS-independent */
 614         init_sb(sb, vmnt, &ext2_d_op, EXT2_ROOT_INO, 0);
 615
 616         printk("EXT2 superblock loaded\n");
 617         kref_put(&bdev->b_kref);
 618         return sb;
 619 }
 620
 621 void ext2_kill_sb(struct super_block *sb)
 622 {
 623         /* don't forget to kfree the s_fs_info and its two members */
 624         panic("Killing an EXT2 SB is not supported!");
 625 }
 626
 627 /* Every FS must have a static FS Type, with which the VFS code can bootstrap */
 628 struct fs_type ext2_fs_type = {"EXT2", 0, ext2_get_sb, ext2_kill_sb, {0, 0},
 629                                TAILQ_HEAD_INITIALIZER(ext2_fs_type.fs_supers)};
 630
 631 /* Page Map Operations */
 632
 633 /* Sets up the bidirectional mapping between the page and its buffer heads.  As
 634  * a future optimization, we could try and detect if all of the blocks are
 635  * contiguous (either before or after making them) and compact them to one BH.
 636  * Note there is an assumption that the file has at least one block in it. */
 637 int ext2_mappage(struct page_map *pm, struct page *page)
 638 {
 639         struct buffer_head *bh;
 640         struct inode *inode = (struct inode*)pm->pm_host;
 641         assert(!page->pg_private);              /* double check that we aren't bh-mapped */
 642         assert(inode->i_mapping == pm); /* double check we are the inode for pm */
 643         struct block_device *bdev = inode->i_sb->s_bdev;
 644         unsigned int blk_per_pg = PGSIZE / inode->i_sb->s_blocksize;
 645         unsigned int sct_per_blk = inode->i_sb->s_blocksize / bdev->b_sector_sz;
 646         uint32_t ino_blk_num, fs_blk_num = 0, *fs_blk_slot;
 647
 648         bh = kmem_cache_alloc(bh_kcache, 0);
 649         page->pg_private = bh;
 650         for (int i = 0; i < blk_per_pg; i++) {
 651                 /* free_bh() can handle having a halfway aborted mappage() */
 652                 if (!bh)
 653                         return -ENOMEM;
 654                 bh->bh_page = page;                                                     /* weak ref */
 655                 bh->bh_buffer = page2kva(page) + i * inode->i_sb->s_blocksize;
 656                 bh->bh_flags = 0;                                                       /* whatever... */
 657                 bh->bh_bdev = bdev;                                                     /* uncounted ref */
 658                 /* compute the first sector of the FS block for the ith buf in the pg */
 659                 ino_blk_num = page->pg_index * blk_per_pg + i;
 660                 fs_blk_slot = ext2_lookup_inotable_slot(inode, ino_blk_num);
 661                 /* If there isn't a block there, lets get one.  The previous fs_blk_num
 662                  * is our hint (or we have to compute one). */
 663                 if (!*fs_blk_slot) {
 664                         if (!fs_blk_num) {
 665                                 fs_blk_num = ext2_bgidx2block(inode->i_sb,
 666                                                               ext2_inode2bg(inode), 0);
 667                         }
 668                         fs_blk_num = ext2_alloc_block(inode, fs_blk_num + 1);
 669                         /* Link it, and dirty the inode indirect block */
 670                         *fs_blk_slot = cpu_to_le32(fs_blk_num);
 671                         ext2_dirty_metablock(inode->i_sb, fs_blk_slot);
 672                         /* the block is still on disk, and we don't want its contents */
 673                         bh->bh_flags = BH_NEEDS_ZEROED;                 /* talking to readpage */
 674                         /* update our num blocks, with 512B each "block" (ext2-style) */
 675                         inode->i_blocks += inode->i_sb->s_blocksize >> 9;
 676                 } else {        /* there is a block there already */
 677                         fs_blk_num = *fs_blk_slot;
 678                 }
 679                 ext2_put_metablock(inode->i_sb, fs_blk_slot);
 680                 bh->bh_sector = fs_blk_num * sct_per_blk;
 681                 bh->bh_nr_sector = sct_per_blk;
 682                 /* Stop if we're the last block in the page.  We could be going beyond
 683                  * the end of the file, in which case the next BHs will be zeroed. */
 684                 if (i == blk_per_pg - 1) {
 685                         bh->bh_next = 0;
 686                         break;
 687                 } else {
 688                         /* get and link to the next BH. */
 689                         bh->bh_next = kmem_cache_alloc(bh_kcache, 0);
 690                         bh = bh->bh_next;
 691                 }
 692         }
 693         return 0;
 694 }
 695
 696 /* Fills page with its contents from its backing store file.  Note that we do
 697  * the zero padding here, instead of higher in the VFS.  Might change in the
 698  * future.  TODO: make this a block FS generic call. */
 699 int ext2_readpage(struct page_map *pm, struct page *page)
 700 {
 701         int retval;
 702         struct block_device *bdev = pm->pm_host->i_sb->s_bdev;
 703         struct buffer_head *bh;
 704         struct block_request *breq;
 705         void *eobh;
 706
 707         assert(page->pg_flags & PG_BUFFER);
 708         retval = ext2_mappage(pm, page);
 709         if (retval)
 710                 return retval;
 711         /* Build and submit the request */
 712         breq = kmem_cache_alloc(breq_kcache, 0);
 713         if (!breq)
 714                 return -ENOMEM;
 715         breq->flags = BREQ_READ;
 716         breq->callback = generic_breq_done;
 717         breq->data = 0;
 718         sem_init_irqsave(&breq->sem, 0);
 719         breq->bhs = breq->local_bhs;
 720         breq->nr_bhs = 0;
 721         /* Pack the BH pointers in the block request */
 722         bh = (struct buffer_head*)page->pg_private;
 723         assert(bh);
 724         /* Either read the block in, or zero the buffer.  If we wanted to ensure no
 725          * data is leaked after a crash, we'd write a 0 block too. */
 726         for (int i = 0; bh; bh = bh->bh_next) {
 727                 if (!(bh->bh_flags & BH_NEEDS_ZEROED)) {
 728                         breq->bhs[i] = bh;
 729                         breq->nr_bhs++;
 730                         i++;
 731                 } else {
 732                         memset(bh->bh_buffer, 0, pm->pm_host->i_sb->s_blocksize);
 733                         bh->bh_flags |= BH_DIRTY;
 734                         bh->bh_page->pg_flags |= PG_DIRTY;
 735                 }
 736         }
 737         retval = bdev_submit_request(bdev, breq);
 738         assert(!retval);
 739         sleep_on_breq(breq);
 740         kmem_cache_free(breq_kcache, breq);
 741         /* zero out whatever is beyond the EOF.  we could do this by figuring out
 742          * where the BHs end and zeroing from there, but I'd rather zero from where
 743          * the file ends (which could be in the middle of an FS block */
 744         uintptr_t eof_off;
 745         eof_off = (pm->pm_host->i_size - page->pg_index * PGSIZE);
 746         eof_off = MIN(eof_off, PGSIZE) % PGSIZE;
 747         /* at this point, eof_off is the offset into the page of the EOF, or 0 */
 748         if (eof_off)
 749                 memset(eof_off + page2kva(page), 0, PGSIZE - eof_off);
 750         /* Now the page is up to date */
 751         page->pg_flags |= PG_UPTODATE;
 752         /* Useful debugging.  Put one higher up if the page is not getting mapped */
 753         //print_pageinfo(page);
 754         return 0;
 755 }
 756
 757 /* Super Operations */
 758
 759 /* Creates and initializes a new inode.  FS specific, yet inode-generic fields
 760  * are filled in.  inode-specific fields are filled in in read_inode() based on
 761  * what's on the disk for a given i_no.  i_no and i_fop are set by the caller.
 762  *
 763  * Note that this means this inode can be for an inode that is already on disk,
 764  * or it can be used when creating.  The i_fop depends on the type of file
 765  * (file, directory, symlink, etc). */
 766 struct inode *ext2_alloc_inode(struct super_block *sb)
 767 {
 768         struct inode *inode = kmem_cache_alloc(inode_kcache, 0);
 769         memset(inode, 0, sizeof(struct inode));
 770         inode->i_op = &ext2_i_op;
 771         inode->i_pm.pm_op = &ext2_pm_op;
 772         return inode;
 773 }
 774
 775 /* FS-specific clean up when an inode is dealloced.  this is just cleaning up
 776  * the in-memory version, and only the FS-specific parts.  whether or not the
 777  * inode is still on disc is irrelevant. */
 778 void ext2_dealloc_inode(struct inode *inode)
 779 {
 780         kmem_cache_free(ext2_i_kcache, inode->i_fs_info);
 781 }
 782
 783 /* Returns a pointer within a metablock for the disk inode specified by inode.
 784  * Be sure to 'put' your reference (and/or dirty it). */
 785 struct ext2_inode *ext2_get_diskinode(struct inode *inode)
 786 {
 787         uint32_t my_bg_idx, ino_per_blk, my_ino_blk;
 788         struct ext2_sb_info *e2sbi = (struct ext2_sb_info*)inode->i_sb->s_fs_info;
 789         struct ext2_block_group *my_bg;
 790         struct ext2_inode *ino_tbl_chunk;
 791
 792         assert(inode->i_ino);                                   /* ino == 0 is a bug */
 793         /* Need to compute the blockgroup and index of the requested inode */
 794         ino_per_blk = inode->i_sb->s_blocksize /
 795                       le16_to_cpu(e2sbi->e2sb->s_inode_size);
 796         my_bg_idx = ext2_inode2bgidx(inode);
 797         my_bg = ext2_inode2bg(inode);
 798         /* Figure out which FS block of the inode table we want and read in that
 799          * chunk */
 800         my_ino_blk = le32_to_cpu(my_bg->bg_inode_table) + my_bg_idx / ino_per_blk;
 801         ino_tbl_chunk = ext2_get_metablock(inode->i_sb, my_ino_blk);
 802         return &ino_tbl_chunk[my_bg_idx % ino_per_blk];
 803 }
 804
 805 /* reads the inode data on disk specified by inode->i_ino into the inode.
 806  * basically, it's a "make this inode the one for i_ino (i number)" */
 807 void ext2_read_inode(struct inode *inode)
 808 {
 809         struct ext2_inode *my_ino;
 810         my_ino = ext2_get_diskinode(inode);
 811
 812         /* Have the disk inode now, let's put its info into the VFS inode: */
 813         inode->i_mode = le16_to_cpu(my_ino->i_mode);
 814         switch (inode->i_mode & __S_IFMT) {
 815                 case (__S_IFDIR):
 816                         inode->i_fop = &ext2_f_op_dir;
 817                         break;
 818                 case (__S_IFREG):
 819                         inode->i_fop = &ext2_f_op_file;
 820                         break;
 821                 case (__S_IFLNK):
 822                         inode->i_fop = &ext2_f_op_sym;
 823                         break;
 824                 case (__S_IFCHR):
 825                 case (__S_IFBLK):
 826                 default:
 827                         inode->i_fop = &ext2_f_op_file;
 828                         warn("[Calm British Accent] Look around you.  Unhandled filetype.");
 829         }
 830         inode->i_nlink = le16_to_cpu(my_ino->i_links_cnt);
 831         inode->i_uid = le16_to_cpu(my_ino->i_uid);
 832         inode->i_gid = le16_to_cpu(my_ino->i_gid);
 833         /* technically, for large F_REG, we should | with i_dir_acl */
 834         inode->i_size = le32_to_cpu(my_ino->i_size);
 835         inode->i_atime.tv_sec = le32_to_cpu(my_ino->i_atime);
 836         inode->i_atime.tv_nsec = 0;
 837         inode->i_mtime.tv_sec = le32_to_cpu(my_ino->i_mtime);
 838         inode->i_mtime.tv_nsec = 0;
 839         inode->i_ctime.tv_sec = le32_to_cpu(my_ino->i_ctime);
 840         inode->i_ctime.tv_nsec = 0;
 841         inode->i_blocks = le32_to_cpu(my_ino->i_blocks);
 842         inode->i_flags = le32_to_cpu(my_ino->i_flags);
 843         inode->i_socket = FALSE;                /* for now */
 844         /* Copy over the other inode stuff that isn't in the VFS inode.  For now,
 845          * it's just the block pointers */
 846         inode->i_fs_info = kmem_cache_alloc(ext2_i_kcache, 0);
 847         struct ext2_i_info *e2ii = (struct ext2_i_info*)inode->i_fs_info;
 848         for (int i = 0; i < 15; i++)
 849                 e2ii->i_block[i] = le32_to_cpu(my_ino->i_block[i]);
 850         /* TODO: (HASH) unused: inode->i_hash add to hash (saves on disc reading) */
 851         /* TODO: we could consider saving a pointer to the disk inode and pinning
 852          * its buffer in memory, but for now we'll just free it. */
 853         ext2_put_metablock(inode->i_sb, my_ino);
 854 }
 855
 856 /* called when an inode in memory is modified (journalling FS's care) */
 857 void ext2_dirty_inode(struct inode *inode)
 858 {
 859         // presumably we'll ext2_dirty_metablock(void *buffer) here
 860 }
 861
 862 /* write the inode to disk (specifically, to inode inode->i_ino), synchronously
 863  * if we're asked to wait */
 864 void ext2_write_inode(struct inode *inode, bool wait)
 865 {
 866 I_AM_HERE;
 867 }
 868
 869 /* called when an inode is decref'd, to do any FS specific work */
 870 void ext2_put_inode(struct inode *inode)
 871 {
 872 I_AM_HERE;
 873 }
 874
 875 /* Unused for now, will get rid of this if inode_release is sufficient */
 876 void ext2_drop_inode(struct inode *inode)
 877 {
 878 I_AM_HERE;
 879 }
 880
 881 /* delete the inode from disk (all data) */
 882 void ext2_delete_inode(struct inode *inode)
 883 {
 884 I_AM_HERE;
 885         // would remove from "disk" here
 886         /* TODO: give up our i_ino */
 887 }
 888
 889 /* unmount and release the super block */
 890 void ext2_put_super(struct super_block *sb)
 891 {
 892         panic("Shazbot! Ext2 can't be unmounted yet!");
 893 }
 894
 895 /* updates the on-disk SB with the in-memory SB */
 896 void ext2_write_super(struct super_block *sb)
 897 {
 898 I_AM_HERE;
 899 }
 900
 901 /* syncs FS metadata with the disc, synchronously if we're waiting.  this info
 902  * also includes anything pointed to by s_fs_info. */
 903 int ext2_sync_fs(struct super_block *sb, bool wait)
 904 {
 905 I_AM_HERE;
 906         return 0;
 907 }
 908
 909 /* remount the FS with the new flags */
 910 int ext2_remount_fs(struct super_block *sb, int flags, char *data)
 911 {
 912         warn("Ext2 will not remount.");
 913         return -1; // can't remount
 914 }
 915
 916 /* interrupts a mount operation - used by NFS and friends */
 917 void ext2_umount_begin(struct super_block *sb)
 918 {
 919         panic("Cannot abort a Ext2 mount, and why would you?");
 920 }
 921
 922 /* inode_operations */
 923
 924 /* Little helper, used for initializing new inodes for file-like objects (files,
 925  * symlinks, etc).  We pass the dentry, since we need to up it. */
 926 static void ext2_init_inode(struct inode *dir, struct dentry *dentry)
 927 {
 928 #if 0
 929         struct inode *inode = dentry->d_inode;
 930         inode->i_ino = ext2_get_free_ino();
 931 #endif
 932 }
 933
 934 /* Initializes a new/empty disk inode, according to inode.  If you end up not
 935  * zeroing this stuff, be careful of endianness. */
 936 static void ext2_init_diskinode(struct ext2_inode *e2i, struct inode *inode)
 937 {
 938         assert(inode->i_size == 0);
 939         e2i->i_mode = cpu_to_le16(inode->i_mode);
 940         e2i->i_uid = cpu_to_le16(inode->i_uid);
 941         e2i->i_size = 0;
 942         e2i->i_atime = cpu_to_le32(inode->i_atime.tv_sec);
 943         e2i->i_ctime = cpu_to_le32(inode->i_ctime.tv_sec);
 944         e2i->i_mtime = cpu_to_le32(inode->i_mtime.tv_sec);
 945         e2i->i_dtime = 0;
 946         e2i->i_gid = cpu_to_le16(inode->i_gid);
 947         e2i->i_links_cnt = cpu_to_le16(inode->i_nlink);
 948         e2i->i_blocks = 0;
 949         e2i->i_flags = cpu_to_le32(inode->i_flags);
 950         e2i->i_osd1 = 0;
 951         e2i->i_generation = 0;
 952         e2i->i_file_acl = 0;
 953         e2i->i_dir_acl = 0;
 954         e2i->i_faddr = 0;
 955         for (int i = 0; i < 15; i++)
 956                 e2i->i_block[i] = 0;
 957         for (int i = 0; i < 12; i++)
 958                 e2i->i_osd2[i] = 0;
 959 }
 960
 961 /* These should return true if foreach_dirent should stop working on the
 962  * dirents. */
 963 typedef bool (*each_func_t) (struct ext2_dirent *dir_i, long a1, long a2,
 964                              long a3);
 965
 966 /* Loads the buffer and performs my_work on each dirent, stopping and returning
 967  * 0 if one of the calls succeeded, or returning the dir block num of what would
 968  * be the next dir block otherwise (aka, how many blocks we went through). */
 969 static uint32_t ext2_foreach_dirent(struct inode *dir, each_func_t my_work,
 970                                     long a1, long a2, long a3)
 971 {
 972         struct ext2_dirent *dir_buf, *dir_i;
 973         uint32_t dir_block = 0;
 974         dir_buf = ext2_get_ino_metablock(dir, dir_block++);
 975         dir_i = dir_buf;
 976         /* now we have the first block worth of dirents.  We'll get another block if
 977          * dir_i hits a block boundary */
 978         for (unsigned int bytes = 0; bytes < dir->i_size; ) {
 979                 /* On subsequent loops, we might need to advance to the next block.
 980                  * This is where a file abstraction for a dir might be easier. */
 981                 if ((void*)dir_i >= (void*)dir_buf + dir->i_sb->s_blocksize) {
 982                         ext2_put_metablock(dir->i_sb, dir_buf);
 983                         dir_buf = ext2_get_ino_metablock(dir, dir_block++);
 984                         dir_i = dir_buf;
 985                         assert(dir_buf);
 986                 }
 987                 if (my_work(dir_i, a1, a2, a3)) {
 988                         ext2_put_metablock(dir->i_sb, dir_buf);
 989                         return 0;
 990                 }
 991                 /* Get ready for the next loop */
 992                 bytes += dir_i->dir_reclen;
 993                 dir_i = (void*)dir_i + dir_i->dir_reclen;
 994         }
 995         ext2_put_metablock(dir->i_sb, dir_buf);
 996         return dir_block;
 997 }
 998
 999 /* Returns the actual length of a dirent, not just how far to the next entry.
1000  * If there is no inode, the entry is unused, and it has no length (as far as
1001  * users of this should care). */
1002 static unsigned int ext2_dirent_len(struct ext2_dirent *e2dir)
1003 {
1004         /* arguably, we don't need the le32_to_cpu */
1005         if (le32_to_cpu(e2dir->dir_inode))
1006                 return ROUNDUP(e2dir->dir_namelen + 8, 4);              /* no such le8_to_cpu */
1007         else
1008                 return 0;
1009 }
1010
1011 /* Helper for writing the contents of a dentry to a disk dirent */
1012 static void ext2_write_dirent(struct ext2_dirent *e2dir, struct dentry *dentry,
1013                               unsigned int rec_len)
1014 {
1015         e2dir->dir_inode = cpu_to_le32(dentry->d_inode->i_ino);
1016         e2dir->dir_reclen = cpu_to_le16(rec_len);
1017         e2dir->dir_namelen = dentry->d_name.len;
1018         switch (dentry->d_inode->i_mode & __S_IFMT) {
1019                 case (__S_IFDIR):
1020                         e2dir->dir_filetype = EXT2_FT_DIR;
1021                         break;
1022                 case (__S_IFREG):
1023                         e2dir->dir_filetype = EXT2_FT_REG_FILE;
1024                         break;
1025                 case (__S_IFLNK):
1026                         e2dir->dir_filetype = EXT2_FT_SYMLINK;
1027                         break;
1028                 case (__S_IFCHR):
1029                         e2dir->dir_filetype = EXT2_FT_CHRDEV;
1030                         break;
1031                 case (__S_IFBLK):
1032                         e2dir->dir_filetype = EXT2_FT_BLKDEV;
1033                         break;
1034                 case (__S_IFSOCK):
1035                         e2dir->dir_filetype = EXT2_FT_SOCK;
1036                         break;
1037                 default:
1038                         warn("[Calm British Accent] Look around you: Unknown filetype.");
1039                         e2dir->dir_filetype = EXT2_FT_UNKNOWN;
1040         }
1041         assert(dentry->d_name.len <= 255);
1042         strncpy((char*)e2dir->dir_name, dentry->d_name.name, dentry->d_name.len);
1043 }
1044
1045 /* Helper for ext2_create().  This tries to squeeze a dirent in the slack space
1046  * after an existing dirent, returning TRUE if it succeeded (to break out). */
1047 static bool create_each_func(struct ext2_dirent *dir_i, long a1, long a2,
1048                              long a3)
1049 {
1050         struct dentry *dentry = (struct dentry*)a1;
1051         unsigned int our_rec_len = (unsigned int)a2;
1052         unsigned int mode = (unsigned int)a3;
1053         struct ext2_dirent *dir_new;
1054         unsigned int real_len = ext2_dirent_len(dir_i);
1055         /* How much room is available after this dir_i before the next one */
1056         unsigned int record_slack = le16_to_cpu(dir_i->dir_reclen) - real_len;
1057         /* TODO: Note that this technique will clobber any directory indexing.  They
1058          * exist after the .. entry with an inode of 0.  Check the docs for
1059          * specifics and think up a nice way to tell the diff between a reserved
1060          * entry and an unused one, when inode == 0. */
1061         if (record_slack < our_rec_len)
1062                 return FALSE;
1063         /* At this point, there is enough room for us.  Stick our new one in right
1064          * after the real len, making sure our reclen goes to the old end.  Note
1065          * that it is possible to have a real_len of 0 (an unused entry).  In this
1066          * case, we just end up taking over the spot in the dir_blk.  Be sure to set
1067          * dir_i's reclen before dir_new's (in case they are the same). */
1068         dir_new = ((void*)dir_i + real_len);
1069         dir_i->dir_reclen = cpu_to_le16(real_len);
1070         ext2_write_dirent(dir_new, dentry, record_slack);
1071         ext2_dirty_metablock(dentry->d_sb, dir_new);
1072         return TRUE;
1073 }
1074
1075 /* Called when creating a new disk inode in dir associated with dentry.  We need
1076  * to fill out the i_ino, set the type, and do whatever else we need */
1077 int ext2_create(struct inode *dir, struct dentry *dentry, int mode,
1078                struct nameidata *nd)
1079 {
1080         struct inode *inode = dentry->d_inode;
1081         struct ext2_block_group *dir_bg = ext2_inode2bg(dir);
1082         struct ext2_inode *disk_inode;
1083         struct ext2_i_info *e2ii;
1084         uint32_t dir_block;
1085         unsigned int our_rec_len;
1086         /* TODO: figure out the real time!  (Nanwan's birthday, bitches!) */
1087         time_t now = 1242129600;
1088         struct ext2_dirent *new_dirent;
1089         /* Set basic inode stuff for files, get a disk inode, etc */
1090         SET_FTYPE(inode->i_mode, __S_IFREG);
1091         inode->i_fop = &ext2_f_op_file;
1092         inode->i_ino = ext2_alloc_diskinode(inode, dir_bg);
1093         inode->i_atime.tv_sec = now;
1094         inode->i_atime.tv_nsec = 0;
1095         inode->i_ctime.tv_sec = now;
1096         inode->i_ctime.tv_nsec = 0;
1097         inode->i_mtime.tv_sec = now;
1098         inode->i_mtime.tv_nsec = 0;
1099         /* Initialize disk inode (this will be different for short symlinks) */
1100         disk_inode = ext2_get_diskinode(inode);
1101         ext2_init_diskinode(disk_inode, inode);
1102         /* Initialize the e2ii (might get rid of this cache of block info) */
1103         inode->i_fs_info = kmem_cache_alloc(ext2_i_kcache, 0);
1104         e2ii = (struct ext2_i_info*)inode->i_fs_info;
1105         for (int i = 0; i < 15; i++)
1106                 e2ii->i_block[i] = le32_to_cpu(disk_inode->i_block[i]);
1107         /* Dirty and put the disk inode */
1108         ext2_dirty_metablock(dentry->d_sb, disk_inode);
1109         ext2_put_metablock(dentry->d_sb, disk_inode);
1110         /* Insert it in the directory (make a dirent, might expand the dir too) */
1111         /* Note the disk dir_name is not null terminated */
1112         our_rec_len = ROUNDUP(8 + dentry->d_name.len, 4);
1113         assert(our_rec_len <= 8 + 256);
1114         /* Consider caching the start point for future dirent ops.  Or even using
1115          * the indexed directory.... */
1116         dir_block = ext2_foreach_dirent(dir, create_each_func, (long)dentry,
1117                                         (long)our_rec_len, (long)mode);
1118         /* If this returned a block number, we didn't find room in any of the
1119          * existing directory blocks, so we need to make a new one, stick it in the
1120          * dir inode, and stick our dirent at the beginning.  The reclen is the
1121          * whole blocksize (since it's the last entry in this block) */
1122         if (dir_block) {
1123                 new_dirent = ext2_get_ino_metablock(dir, dir_block);
1124                 ext2_write_dirent(new_dirent, dentry, dentry->d_sb->s_blocksize);
1125                 ext2_dirty_metablock(dentry->d_sb, new_dirent);
1126                 ext2_put_metablock(dentry->d_sb, new_dirent);
1127         }
1128         return 0;
1129 }
1130
1131 /* If we match, this loads the inode for the dentry and returns true (so we
1132  * break out) */
1133 static bool lookup_each_func(struct ext2_dirent *dir_i, long a1, long a2,
1134                              long a3)
1135 {
1136         struct dentry *dentry = (struct dentry*)a1;
1137         /* Test if we're the one (TODO: use d_compare).  Note, dir_name is not
1138          * null terminated, hence the && test. */
1139         if (!strncmp((char*)dir_i->dir_name, dentry->d_name.name,
1140                      dir_i->dir_namelen) &&
1141                     (dentry->d_name.name[dir_i->dir_namelen] == '\0')) {
1142                 load_inode(dentry, (long)le32_to_cpu(dir_i->dir_inode));
1143                 /* TODO: (HASH) add dentry to dcache (maybe the caller should) */
1144                 return TRUE;
1145         }
1146         return FALSE;
1147 }
1148
1149 /* Searches the directory for the filename in the dentry, filling in the dentry
1150  * with the FS specific info of this file.  If it succeeds, it will pass back
1151  * the *dentry you should use (which might be the same as the one you passed in).
1152  * If this fails, it will return 0, but not free the memory of "dentry."
1153  *
1154  * Callers, make sure you alloc and fill out the name parts of the dentry.  We
1155  * don't currently use the ND.  Might remove it in the future.  */
1156 struct dentry *ext2_lookup(struct inode *dir, struct dentry *dentry,
1157                            struct nameidata *nd)
1158 {
1159         assert(S_ISDIR(dir->i_mode));
1160         struct ext2_dirent *dir_buf, *dir_i;
1161         if (!ext2_foreach_dirent(dir, lookup_each_func, (long)dentry, 0, 0))
1162                 return dentry;
1163         printd("EXT2: Not Found, %s\n", dentry->d_name.name);
1164         return 0;
1165 }
1166
1167 /* Hard link to old_dentry in directory dir with a name specified by new_dentry.
1168  * At the very least, set the new_dentry's FS-specific fields. */
1169 int ext2_link(struct dentry *old_dentry, struct inode *dir,
1170              struct dentry *new_dentry)
1171 {
1172 I_AM_HERE;
1173         assert(new_dentry->d_op = &ext2_d_op);
1174         return 0;
1175 }
1176
1177 /* Removes the link from the dentry in the directory */
1178 int ext2_unlink(struct inode *dir, struct dentry *dentry)
1179 {
1180 I_AM_HERE;
1181         return 0;
1182 }
1183
1184 /* Creates a new inode for a symlink dir, linking to / containing the name
1185  * symname.  dentry is the controlling dentry of the inode. */
1186 int ext2_symlink(struct inode *dir, struct dentry *dentry, const char *symname)
1187 {
1188 I_AM_HERE;
1189         #if 0
1190         struct inode *inode = dentry->d_inode;
1191         SET_FTYPE(inode->i_mode, __S_IFLNK);
1192         inode->i_fop = &ext2_f_op_sym;
1193         strncpy(string, symname, len);
1194         string[len] = '\0';             /* symname should be \0d anyway, but just in case */
1195         #endif
1196         return 0;
1197 }
1198
1199 /* Called when creating a new inode for a directory associated with dentry in
1200  * dir with the given mode.  Note, we might (later) need to track subdirs within
1201  * the parent inode, like we do with regular files.  I'd rather not, so we'll
1202  * see if we need it. */
1203 int ext2_mkdir(struct inode *dir, struct dentry *dentry, int mode)
1204 {
1205 I_AM_HERE;
1206         #if 0
1207         struct inode *inode = dentry->d_inode;
1208         inode->i_ino = ext2_get_free_ino();
1209         SET_FTYPE(inode->i_mode, __S_IFDIR);
1210         inode->i_fop = &ext2_f_op_dir;
1211         #endif
1212         return 0;
1213 }
1214
1215 /* Removes from dir the directory 'dentry.'  Ext2 doesn't store anything in the
1216  * inode for which children it has.  It probably should, but since everything is
1217  * pinned, it just relies on the dentry connections. */
1218 int ext2_rmdir(struct inode *dir, struct dentry *dentry)
1219 {
1220 I_AM_HERE;
1221         return 0;
1222 }
1223
1224 /* Used to make a generic file, based on the type and the major/minor numbers
1225  * (in rdev), with the given mode.  As with others, this creates a new disk
1226  * inode for the file */
1227 int ext2_mknod(struct inode *dir, struct dentry *dentry, int mode, dev_t rdev)
1228 {
1229 I_AM_HERE;
1230         return -1;
1231 }
1232
1233 /* Moves old_dentry from old_dir to new_dentry in new_dir */
1234 int ext2_rename(struct inode *old_dir, struct dentry *old_dentry,
1235                struct inode *new_dir, struct dentry *new_dentry)
1236 {
1237 I_AM_HERE;
1238         return -1;
1239 }
1240
1241 /* Returns the char* for the symname for the given dentry.  The VFS code that
1242  * calls this for real FS's might assume it's already read in, so if the char *
1243  * isn't already in memory, we'd need to read it in here.  Regarding the char*
1244  * storage, the char* only will last as long as the dentry and inode are in
1245  * memory. */
1246 char *ext2_readlink(struct dentry *dentry)
1247 {
1248 I_AM_HERE;
1249         struct inode *inode = dentry->d_inode;
1250         if (!S_ISLNK(inode->i_mode))
1251                 return 0;
1252         return 0;
1253 }
1254
1255 /* Modifies the size of the file of inode to whatever its i_size is set to */
1256 void ext2_truncate(struct inode *inode)
1257 {
1258 }
1259
1260 /* Checks whether the the access mode is allowed for the file belonging to the
1261  * inode.  Implies that the permissions are on the file, and not the hardlink */
1262 int ext2_permission(struct inode *inode, int mode, struct nameidata *nd)
1263 {
1264         return -1;
1265 }
1266
1267
1268 /* dentry_operations */
1269 /* Determines if the dentry is still valid before using it to translate a path.
1270  * Network FS's need to deal with this. */
1271 int ext2_d_revalidate(struct dentry *dir, struct nameidata *nd)
1272 { // default, nothing
1273         return -1;
1274 }
1275
1276 /* Produces the hash to lookup this dentry from the dcache */
1277 int ext2_d_hash(struct dentry *dentry, struct qstr *name)
1278 {
1279         return -1;
1280 }
1281
1282 /* Compares name1 and name2.  name1 should be a member of dir. */
1283 int ext2_d_compare(struct dentry *dir, struct qstr *name1, struct qstr *name2)
1284 { // default, string comp (case sensitive)
1285         return -1;
1286 }
1287
1288 /* Called when the last ref is deleted (refcnt == 0) */
1289 int ext2_d_delete(struct dentry *dentry)
1290 { // default, nothin
1291         return -1;
1292 }
1293
1294 /* Called when it's about to be slab-freed */
1295 int ext2_d_release(struct dentry *dentry)
1296 {
1297         return -1;
1298 }
1299
1300 /* Called when the dentry loses it's inode (becomes "negative") */
1301 void ext2_d_iput(struct dentry *dentry, struct inode *inode)
1302 { // default, call i_put to release the inode object
1303 }
1304
1305
1306 /* file_operations */
1307
1308 /* Updates the file pointer.  TODO: think about locking, and putting this in the
1309  * VFS. */
1310 #include <syscall.h>    /* just for set_errno, may go away later */
1311 int ext2_llseek(struct file *file, off64_t offset, off64_t *ret, int whence)
1312 {
1313         off64_t temp_off = 0;
1314         switch (whence) {
1315                 case SEEK_SET:
1316                         temp_off = offset;
1317                         break;
1318                 case SEEK_CUR:
1319                         temp_off = file->f_pos + offset;
1320                         break;
1321                 case SEEK_END:
1322                         temp_off = file->f_dentry->d_inode->i_size + offset;
1323                         break;
1324                 default:
1325                         set_errno(EINVAL);
1326                         warn("Unknown 'whence' in llseek()!\n");
1327                         return -1;
1328         }
1329         file->f_pos = temp_off;
1330         *ret = temp_off;
1331         return 0;
1332 }
1333
1334 /* Fills in the next directory entry (dirent), starting with d_off.  Like with
1335  * read and write, there will be issues with userspace and the *dirent buf.
1336  * TODO: (UMEM) */
1337 int ext2_readdir(struct file *dir, struct dirent *dirent)
1338 {
1339         void *blk_buf;
1340         /* Not enough data at the end of the directory */
1341         if (dir->f_dentry->d_inode->i_size < dirent->d_off + 8)
1342                 return -ENOENT;
1343         /* Figure out which block we need to read in for dirent->d_off */
1344         int block = dirent->d_off / dir->f_dentry->d_sb->s_blocksize;
1345         blk_buf = ext2_get_ino_metablock(dir->f_dentry->d_inode, block);
1346         assert(blk_buf);
1347         off64_t f_off = dirent->d_off % dir->f_dentry->d_sb->s_blocksize;
1348         /* Copy out the dirent info */
1349         struct ext2_dirent *e2dir = (struct ext2_dirent*)(blk_buf + f_off);
1350         dirent->d_ino = le32_to_cpu(e2dir->dir_inode);
1351         dirent->d_off += le16_to_cpu(e2dir->dir_reclen);
1352         if (dir->f_dentry->d_inode->i_size < dirent->d_off)
1353                 panic("Something is jacked with the dirent going beyond the dir/file");
1354         /* note, dir_namelen doesn't include the \0 */
1355         dirent->d_reclen = e2dir->dir_namelen;
1356         strncpy(dirent->d_name, (char*)e2dir->dir_name, e2dir->dir_namelen);
1357         assert(e2dir->dir_namelen <= MAX_FILENAME_SZ);
1358         dirent->d_name[e2dir->dir_namelen] = '\0';
1359         ext2_put_metablock(dir->f_dentry->d_sb, blk_buf);
1360
1361         /* At the end of the directory, sort of.  ext2 often preallocates blocks, so
1362          * this will cause us to walk along til the end, which isn't quite right. */
1363         if (dir->f_dentry->d_inode->i_size == dirent->d_off)
1364                 return 0;
1365         if (dir->f_dentry->d_inode->i_size < dirent->d_off) {
1366                 warn("Issues reaching the end of an ext2 directory!");
1367                 return 0;
1368         }
1369         return 1;                                                       /* normal success for readdir */
1370 }
1371
1372 /* This is called when a VMR is mapping a particular file.  The FS needs to do
1373  * whatever it needs so that faults can be handled by read_page(), and handle all
1374  * of the cases of MAP_SHARED, MAP_PRIVATE, whatever.  It also needs to ensure
1375  * the file is not being mmaped in a way that conflicts with the manner in which
1376  * the file was opened or the file type. */
1377 int ext2_mmap(struct file *file, struct vm_region *vmr)
1378 {
1379         if (S_ISREG(file->f_dentry->d_inode->i_mode))
1380                 return 0;
1381         return -1;
1382 }
1383
1384 /* Called by the VFS while opening the file, which corresponds to inode,  for
1385  * the FS to do whatever it needs. */
1386 int ext2_open(struct inode *inode, struct file *file)
1387 {
1388         /* TODO: check to make sure the file is openable, and maybe do some checks
1389          * for the open mode (like did we want to truncate, append, etc) */
1390         return 0;
1391 }
1392
1393 /* Called when a file descriptor is closed. */
1394 int ext2_flush(struct file *file)
1395 {
1396 I_AM_HERE;
1397         return -1;
1398 }
1399
1400 /* Called when the file is about to be closed (file obj freed) */
1401 int ext2_release(struct inode *inode, struct file *file)
1402 {
1403         return 0;
1404 }
1405
1406 /* Flushes the file's dirty contents to disc */
1407 int ext2_fsync(struct file *file, struct dentry *dentry, int datasync)
1408 {
1409         return -1;
1410 }
1411
1412 /* Traditionally, sleeps until there is file activity.  We probably won't
1413  * support this, or we'll handle it differently. */
1414 unsigned int ext2_poll(struct file *file, struct poll_table_struct *poll_table)
1415 {
1416         return -1;
1417 }
1418
1419 /* Reads count bytes from a file, starting from (and modifiying) offset, and
1420  * putting the bytes into buffers described by vector */
1421 ssize_t ext2_readv(struct file *file, const struct iovec *vector,
1422                   unsigned long count, off64_t *offset)
1423 {
1424         return -1;
1425 }
1426
1427 /* Writes count bytes to a file, starting from (and modifiying) offset, and
1428  * taking the bytes from buffers described by vector */
1429 ssize_t ext2_writev(struct file *file, const struct iovec *vector,
1430                   unsigned long count, off64_t *offset)
1431 {
1432         return -1;
1433 }
1434
1435 /* Write the contents of file to the page.  Will sort the params later */
1436 ssize_t ext2_sendpage(struct file *file, struct page *page, int offset,
1437                      size_t size, off64_t pos, int more)
1438 {
1439         return -1;
1440 }
1441
1442 /* Checks random FS flags.  Used by NFS. */
1443 int ext2_check_flags(int flags)
1444 { // default, nothing
1445         return -1;
1446 }
1447
1448 /* Redeclaration and initialization of the FS ops structures */
1449 struct page_map_operations ext2_pm_op = {
1450         ext2_readpage,
1451 };
1452
1453 struct super_operations ext2_s_op = {
1454         ext2_alloc_inode,
1455         ext2_dealloc_inode,
1456         ext2_read_inode,
1457         ext2_dirty_inode,
1458         ext2_write_inode,
1459         ext2_put_inode,
1460         ext2_drop_inode,
1461         ext2_delete_inode,
1462         ext2_put_super,
1463         ext2_write_super,
1464         ext2_sync_fs,
1465         ext2_remount_fs,
1466         ext2_umount_begin,
1467 };
1468
1469 struct inode_operations ext2_i_op = {
1470         ext2_create,
1471         ext2_lookup,
1472         ext2_link,
1473         ext2_unlink,
1474         ext2_symlink,
1475         ext2_mkdir,
1476         ext2_rmdir,
1477         ext2_mknod,
1478         ext2_rename,
1479         ext2_readlink,
1480         ext2_truncate,
1481         ext2_permission,
1482 };
1483
1484 struct dentry_operations ext2_d_op = {
1485         ext2_d_revalidate,
1486         ext2_d_hash,
1487         ext2_d_compare,
1488         ext2_d_delete,
1489         ext2_d_release,
1490         ext2_d_iput,
1491 };
1492
1493 struct file_operations ext2_f_op_file = {
1494         ext2_llseek,
1495         generic_file_read,
1496         generic_file_write,
1497         ext2_readdir,
1498         ext2_mmap,
1499         ext2_open,
1500         ext2_flush,
1501         ext2_release,
1502         ext2_fsync,
1503         ext2_poll,
1504         ext2_readv,
1505         ext2_writev,
1506         ext2_sendpage,
1507         ext2_check_flags,
1508 };
1509
1510 struct file_operations ext2_f_op_dir = {
1511         ext2_llseek,
1512         generic_dir_read,
1513         0,
1514         ext2_readdir,
1515         ext2_mmap,
1516         ext2_open,
1517         ext2_flush,
1518         ext2_release,
1519         ext2_fsync,
1520         ext2_poll,
1521         ext2_readv,
1522         ext2_writev,
1523         ext2_sendpage,
1524         ext2_check_flags,
1525 };
1526
1527 struct file_operations ext2_f_op_sym = {
1528         ext2_llseek,
1529         generic_file_read,
1530         generic_file_write,
1531         ext2_readdir,
1532         ext2_mmap,
1533         ext2_open,
1534         ext2_flush,
1535         ext2_release,
1536         ext2_fsync,
1537         ext2_poll,
1538         ext2_readv,
1539         ext2_writev,
1540         ext2_sendpage,
1541         ext2_check_flags,
1542 };