HOWTO rmdir

=====================================================================

tst_bit(), clr_bit(), set_bit() are given BEFORE

Write theses functions in a dalloc.c file

int incFreeInodes(int dev)
{
  char buf[BLKSIZE];

  // inc free inodes count in SUPER and GD
  get_block(dev, 1, buf);
  sp = (SUPER *)buf;
  sp->s_free_inodes_count++;
  put_block(dev, 1, buf);

  get_block(dev, 2, buf);
  gp = (GD *)buf;
  gp->bg_free_inodes_count++;
  put_block(dev, 2, buf);
}

int idalloc(int dev, int ino)  // deallocate an ino number
{
  int i;  
  char buf[BLKSIZE];

  // return 0 if ino < 0 OR > ninodes

  // get inode bitmap block
  get_block(dev, bmap, buf);
  clr_bit(buf, ino-1);

  // write buf back
  put_block(dev, imap, buf);

  // update free inode count in SUPER and GD
  incFreeInodes(dev);
}

int bdalloc(int dev, int blk) // deallocate a blk number
{
  // WRITE YOUR OWN CODE to deallocate a block number blk
}
========================================================================
  
Assume: command line = "rmdir pathname"

1. Extract cmd, pathname from line and save them as globals.

   Do NOT rmdir . or .. or /

int rmdir()
{
  1. get minode of pathname: 
     MINODE *mip = path2inode(pathname);

  2. check DIR type (HOW?), not BUSY (HOW?), is empty:

     WHY must be empty?

     HOW TO check whether a DIR is empty?
     ---------------------------------------------------------------------
     First, check link count (links_count > 2 means not empty);
     However, links_count = 2 may still have FILEs, so go through its data 
     block(s) to see whether it has any entries in addition to . and ..
     ---------------------------------------------------------------------
     THIS IS SAME as show_dir()
     
     if (NOT DIR || BUSY || not empty): iput(mip); retunr -1;

  3. ASSUME passed the above checks.

     get parent DIR pino (in mip->INODE.i_block[0])

     Deallocate its block and inode
     ---------------------------------------------
     for (i=0; i<12; i++){
         if (mip->INODE.i_block[i]==0)
             continue;
         bdalloc(mip->dev, mip->INODE.i_block[i]);
     }
     idalloc(mip->dev, mip->ino);
     iput(mip); (which clears mip->sharefCount to 0, still in cache);
     --------------------------------------------

  4. get parent minode: 
         MINDOE *pip = iget(dev, pino); 

  5. remove child's entry from parent directory by

        rm_child(MINODE *pip, char *name);
           
  6. decrement pip's link_count by 1; 
     touch pip's atime, mtime fields;
     mark pip MODIFIED
     iput(pip);       // this will write parent INODE out eventually
     return SUCCESS;
}

// rm_child(): remove the entry [INO Rlen nlen name] from parent's data block.

int rm_child(MINODE *parent, char *name)
{
   1. Search parent INODE's data block(s) for the entry of name

   2. Erase name entry from parent directory by
    
   2.1. if has a predecessor entry:  add Rlen to predecessor's rlen
  
               |    predecessor        | remove this entry  |
          --------------------------------------------------------------
          xxxxx|ino rlen nlen yyy      |INO Rlen nlen name  |  www 
          --------------------------------------------------------------

               |   becomes:                                 |  
          --------------------------------------------------------------
          xxxxx|INO rlen+Rlen nlen yyy   (   invisible    ) |  www
          --------------------------------------------------------------

      }
   
   2.2. First entry in data block:       // can't be i_block[0]
   (1). if (ONLY entry in data block){  
          -----------------------------------------------
          |INO Rlen Nlen NAME                           | 
          -----------------------------------------------
      Option 1: set ino=0; name_len=0

      Option 2:
          deallocate the data block; reduce parent's file size by BLKSIZE;
         
          Assume this is parent's i_block[i]:
          move parent's NONZERO blocks upward, i.e. 
               i_block[i+1] becomes i_block[i]
               etc.
          so that there is no HOLEs in parent's data block numbers
      }

   (2). // has trailing entries:{
      Option 1: set ino=0; name_len=0;  

      Option 2: add rec_len to LAST entry;
                shift all trailing entries LEFT to cover up the deleted entry
      }

  3. Write the parent's data block back to disk;
     mark parent minode MODIFIED for write-back
}

==================== Compaction/Defragmentation ===========================

NOTE that rm_child() will creat HOLEs in parent's data block
i.e. entries whose rec_len > its IDEAL_len.

Such HOLEs are NOT wasted since they may be used for new entries later by
the First-Fit-Algorithm

However, eventually it may create too many SMALL HOLEs, which is not good.

Compaction/Defragmentation: combines all the holes into a single HOLE at end.
===========================================================================