360 Project Help: HOW TO mkdir_creat
Reference: Chapter 11.8.1: mkdir. 11.8.2: creat, 11.8.3
WARNING: The project uses NEW ALGORITHMS. Your work MSUT comply with the new requirements. ELSE: NO credit
1. Base code: YOUR LAB6 program
ADD these C code:
int tst_bit(char *buf, int bit)
{
// in Chapter 11.3.1
}
int set_bit(char *buf, int bit)
{
// in Chapter 11.3.1
}
int decFreeInodes(int dev)
{
char buf[BLKSIZE];
// dec free inodes count by 1 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 ialloc(int dev) // allocate an inode number from imap block
{
int i;
char buf[BLKSIZE];
// read inode_bitmap block
get_block(dev, imap, buf);
for (i=0; i < ninodes; i++){
if (tst_bit(buf, i)==0){
set_bit(buf,i);
put_block(dev, imap, buf);
decFreeInodes();
printf("ialloc : ino=%d\n", i+1);
return i+1;
}
}
return 0;
}
// WRITE YOUR OWN balloc(dev) function, which returns a FREE disk block number
char *disk = "mydisk"; // work with an EMPTY mydisk by mkdisk
int main()
{
(1). open disk for RW; let dev = opened fd
(2). read SUPER block to verify it's an EXT2 FS
get ninodes, nblocks as globals
printf("ninodes = %d nblocks = %d\n", ninodes, nblocks);
(3). read Group Descriptor 0 to get bmap, imap and inode_start
printf("bmp=%d imap=%d inode_start=%d\n", bmap, imap, inode_start);
----------------------------------------------------------
(4). init(); // initialize FS data structures
root = iget(dev, 2);
running->cwd = iget(dev, 2);
YOUR ls, cd, pwd commands should be working by now
-----------------------------------------------------------
HOW TO mkdir
Assume: command line = "mkdir pathname"
Extract cmd, pathname from line and save them as globals.
int make_dir()
{
1. Let
parent = dirname(pathname); parent= "/a/b" OR "a/b"
child = basename(pathname); child = "c"
WARNING: strtok(), dirname(), basename() destroy pathname
2. Get minode of parent:
MINODE *pip = path2inode(parent);
(print message if pip NULL; return -1 for error)
Verify : (1). parent INODE is a DIR (HOW?) AND
(2). child does NOT exists in the parent directory (HOW?);
4. call mymkdir(pip, child);
5. inc parent inodes's links count by 1;
touch its atime, i.e. atime = time(0L), mark it modified
6. iput(pip);
}
int mymkdir(MINODE *pip, char *name)
{
1. pip points at the parent minode[] of "/a/b", name is a string "c"
2. allocate an inode and a disk block for the new directory;
ino = ialloc(dev);
bno = balloc(dev);
Don't WORK IN THE DARK: PRINT OUT THESE NUMBERS!!!
3. MINODE *mip = iget(dev, ino); //load inode into a minode[] (in order to
wirte contents to the INODE in memory.
4. Write contents to mip->INODE to make it a DIR INODE. Mark it modified;
5. iput(mip); which writes the new INODE out to disk.
// C CODE of (3), (4) and (5):
//**********************************************************************
MINDOE *mip = iget(dev,ino);
INODE *ip = &mip->INODE;
Use ip-> to acess the INODE fields:
i_mode = 0x41ED; // OR 040755: DIR type and permissions
i_uid = running->uid; // Owner uid
i_gid = running->gid; // Group Id
i_size = BLKSIZE; // Size in bytes
i_links_count = 2; // Links count=2 because of . and ..
i_atime = i_ctime = i_mtime = time(0L); // set to current time
i_blocks = 2; // LINUX: Blocks count in 512-byte chunks
i_block[0] = bno; // new DIR has one data block
i_block[1] to i_block[14] = 0;
mip->modified = 1; // mark minode MODIFIED
iput(mip); // write INODE to disk
//***** create data block for new DIR containing . and .. entries ******
6. Write . and .. entries to a buf[ ] of BLKSIZE
| entry . | entry .. | |
----------------------------------------------------------------------
|ino|12|1|. |pino|1012|2|.. |
----------------------------------------------------------------------
Then, write buf[ ] to the disk block bno;
7. Finally, enter name ENTRY into parent's directory by
enter_child(pip, ino, name);
8. int enter_child(MINODE *pip, int myino, char *myname)
{
(1). NEED_LEN = 4*[ (8 + strlen(myname) + 3)/4 ]; // a multiple of 4
(2). For each data block of parent DIR do { // assume: only 12 direct blocks
if (i_block[i]==0) BREAK;
get parent's data block into a buf[ ], which looks like the following
|-4---2----2--|----| | |
---------------------------------------------------------------------------
| . |.. |ino rlen nlen NAME|.......|ino rlen nlen|NAME |
---------------------------------------------------------------------------
Each DIR entry has rec_len, name_len. Each entry's ideal length is
IDEAL_LEN = 4*[ (8 + name_len + 3)/4 ] // multiple of 4
(3). Step through each DIR entry dp in parent data block:
compute REMAIN = dp->rec_len - IDEAL_LEN;
if (REMAIN >= NEED_LEN){ // found enough space for new entry
dp->rec_len = IDEAL_LEN; // trim dp's rec_len to its IDEAL_LEN
enter new_entry as [myino, REMIN, strlen(myname), myname]
==================== First-Fit-Algorithm ============================
Since we try to find the FISRT slot big enough for the new entry,
it is called the First-Fit-Algorithm. What's Best-Fit-Algorithm?
=====================================================================
EXAMPLEs:
1. Empty parent DIR: parent i_block[0]:
| entry . | entry .. |
------------------- rlen -------------------------------------------------
|ino|12|1|. |pino|1012|2|.. |
--------------------------------------------------------------------------
add entry abcde: NEED=5; IDEAL of .. = 12; REMAIN=1012-12=1000
--------------|---- rlen ------|------------------------------------------
|ino|12|1|. |pino| 12 |2|.. |ino, 1000,5,abcde |
--------------------------------------------------------------------------
add entry abcdefghij: NEED=10; IDEAL=16; REMAIN=1000-16=984
--------------|---- rlen ------|------------------------------------------
|ino|12|1|. |pino| 12 |2|.. |ino,16,5,abcde |ino,984,10,abcdefghij |
--------------------------------------------------------------------------
=====================================================================
So, If only add entries, always add as LAST entry in the data block.
However, things will be different and interesting if some entries are deleted.
=====================================================================
Example
----|----------|--------------------------------------|-------------------
| . |2,12,2,.. |ino,36,28,ABCDabcd12345678901234567890|ino,964,4,abcd |
--------------------------------------------------------------------------
delete ABCDabcd12345678901234567890 ===>
----|-rlen=40----------------------------------------|-------------------
| . |2,40,2,.. |ino,964,4,abcd |
--------------------------------------------------------------------------
Then, add entry ABC : NEED=12; 2nd entry: IDEAL=12, REMAIN=40-12=36 ===>
use space in the .. entry
----|----------|------- new enrty ABC----------------|-------------------
| . |2,12,2,.. |ino,36,3,ABC |ino,964,4,abcd |
--------------------------------------------------------------------------
write parent data back to disk;
return OK;
// try next DIR entry
}
(4).// Reach here means: NO space in existing data block(s)
Allocate a new data block; INC parent's isze by BLKSIZE;
Enter new entry as the first entry in the new data block with rec_len=BLKSIZE.
|-------------------- rlen = BLKSIZE -------------------------------------
|myino rlen nlen myname |
--------------------------------------------------------------------------
Write data block to disk;
}
creat_file()
{
This is ALMOST THE SAME AS mkdir() except :
(1). its inode's mode field is set to a REGULAR file,
set permission bits to (default) rw-r--r--,
i_mode=0x81A4 = b|1000|0001|1010|0100|
(2). No data block, so size = 0
(3). links_count = 1;
(4). Do NOT increment parent's links_count
}
int my_creat(MINODE *pip; char *name)
{
Same as mymkdir() except
INODE's file type = 0x81A4 OR 0100644
links_count = 1
NO data block, so size = 0
do NOT inc parent's link count.
}
====================================================================
================ development HEPS =============================
1. Your mkdir/creat may trash the disk iamge (by writing to wrong inode or data
blocks), which will cause problems later even if your program is correct.
So, it's better to use a FRESH disk image each time during development.
2. After running YOUR mkdir/creat commands, you should check the results
under LINUX. Write a sh script "s" containing
sudo mount disk /mnt
ls -l /mnt
sudo umount /mnt
to show the disk contents under LINUX.
==============================================================
Sample solutions:
samples/mkdir_creat