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.
===========================================================================