Transcript Final Project Explanation

Final Project:
ThreadOS File System
Joe McCarthy
CSS 430: Operating Systems - ThreadOS File System
1
ThreadOS Superblock & Inodes
Block #0
Superblock
int totalBlocks;
int totalInodes;
int freeList;
Inode #0
Block #1
Free
Block #y
Free
Block #z
32bytes
Inode #1
Inode #15
Block #2
Free
Block #x
/ root
directory
Inode #inodeBlocks -1
Block #(totalBlocks – 1)
CSS 430: Operating Systems - ThreadOS File System
2
ThreadOS Root Directory (“/”)
Entry[]
(iNumber)
0
1
2
3
4
5
6
7
8
9
10
inodeBlock-1
fsizes
fnames
1
4
4
4
4
5
5
6
6
9
6
6
5
/
init
fsck
clri
motd
mount
mknod
passwd
umount
checklist
fsdblb
config
getty
•
•
•
•
•
•
Directory()
– Initialize “/” directory
bytes2directory( byte[] data )
– Populate directory with byte[]
retrieved from disk
directory2bytes()
– Converts directory information into
byte[]
ialloc( String filename )
– Allocate an iNumber for filename
ifree( short iNumber )
– Deallocate the iNumber
namei( String filename )
– Return filename’s iNumber
CSS 430: Operating Systems - ThreadOS File System
3
CSS430 ThreadOS File System
Thread
int fd = SysLib.open(“fileA”, mode);
SysLib.read(fd, …);
A simplified structure of Unix file system
TCB
0
1
2
3
31
stdin
stdout
stderr
ftEnt[32]
per-thread
file table
struct file:
count 1
inode
Inode:
length
count 1
direct[11]
indirect
FileTable
CSS 430: Operating Systems - ThreadOS File System
Inode
Disk
4
FileSystem
public class FileSystem {
private SuperBlock superblock;
private Directory directory;
private FileTable filetable;
SuperBlock
public FileSystem( int diskBlocks ) {
superblock = new SuperBlock( diskBlocks );
SysLib.rawread( 0, byte[] )
directory = new Directory( superblock.inodeBlocks );
filetable = new FileTable( directory );
FileTableEntry dirEnt = open( "/", "r" );
int dirSize = fsize( dirEnt );
Directory
if ( dirSize > 0 ) {
byte[] dirData = new byte[dirSize];
read( dirEnt, dirData );
directory.bytes2directory( dirData );
SysLib.rawread( 1, byte[] )
}
close( dirEnt );
}
...
Disk
CSS 430: Operating Systems - ThreadOS File System
FileTable
5
FileSystem
public class FileSystem {
private SuperBlock superblock;
private Directory directory;
SuperBlock
private FileTable filetable;
...
void sync()
boolean format( int files )
SysLib.rawread( 0, byte[] )
FileTableEntry open( String filename, String mode )
boolean close( FileTableEntry ftEnt )
int fsize( FileTableEntry ftEnt )
int read( FileTableEntry ftEnt, byte[] buffer )
Directory
int write( FileTableEntry ftEnt, byte[] buffer )
boolean delete( String filename )
int seek( FileTableEntry ftEnt,
int offset, int whence )
SysLib.rawread( 1, byte[] )
}
Disk
CSS 430: Operating Systems - ThreadOS File System
FileTable
6
SuperBlock
public class SuperBlock {
private final int defaultInodeBlocks = 64;
public int totalBlocks;
Block
public int inodeBlocks;
public int freeList;
#0
public SuperBlock( int diskSize ) {
byte[] superBlock = new byte[Disk.blockSize];
SysLib.rawread( 0, superBlock );
totalBlocks = SysLib.bytes2int( superBlock, 0 );
inodeBlocks = SysLib.bytes2int( superBlock, 4 );
freeList
= SysLib.bytes2int( superBlock, 8 );
if ( totalBlocks == diskSize
&& inodeBlocks > 0
&& freeList >= 2 )
return;
else {
totalBlocks = diskSize;
SysLib.cerr( "Formatting\n" );
format();
}
}
...
CSS 430: Operating Systems - ThreadOS File System
DISK
Superblock
int totalBlocks;
int inodeBlocks;
int freeList;
Inode blocks
Data blocks
7
SuperBlock
public class SuperBlock {
private final int defaultInodeBlocks = 64;
public int totalBlocks;
Block
public int inodeBlocks;
public int freeList;
...
void sync()
/* write totalBlocks, inodeBlocks, freelist
to disk */
#0
Block #1
void format()
void format( int numBlocks )
public int getFreeBlock()
/* dequeue top block
in freelist */
Block #
(inodeBlocks
/ 16) + 1
Superblock
int totalBlocks;
int inodeBlocks;
int freeList;
Inode #0
…
32bytes
Inode #15
… …
…
public boolean returnBlock( int oldBlockNumber )
/* enqueue oldBlockNumber
to top of freelist */
}
DISK
Data blocks:
CSS 430: Operating Systems - ThreadOS File System
Inode #inodeBlocks-1
…
…
8
SuperBlock.format(16)
DISK
public class SuperBlock {
private final int defaultInodeBlocks = 64;
public int totalBlocks;
Block
public int inodeBlocks;
public int freeList;
...
#0
Block #1
void format()
void format( int numBlocks )
/* initialize Inodes, free blocks */
Superblock
totalBlocks = 1000
inodeBlocks = 16
freeList = 2
Inode #0
…
32bytes
Inode #15
3
Block #2
...
}
4
Block #3
…
Block #999
CSS 430: Operating Systems - ThreadOS File System
…
…
-1
9
Directory
public class Directory {
private static int maxChars = 30; // the max characters of each file name
private int fsizes[];
// the actual size of each file name
private char fnames[][];
// file names in characters
public Directory ( int maxInumber ) {
// a default constructor
fsizes = new int[maxInumber];
// maxInumber = max # files
for ( int i = 0; i < maxInumber; i++ ) // all file sizes set to 0
fsizes[i] = 0;
fnames = new char[maxInumber][maxChars];
String root = "/";
// entry (inode) 0 is "/"
fsizes[0] = root.length();
root.getChars( 0, fsizes[0], fnames[0], 0 );
}
...
}
CSS 430: Operating Systems - ThreadOS File System
10
Directory
public class Directory {
private static int maxChars = 30; // the max characters of each file name
private int fsizes[];
// the actual size of each file name
private char fnames[][];
// file names in characters
...
public void bytes2directory( byte[] data ) {
int offset = 0;
for ( int i = 0; i < fsizes.length; i++, offset += 4 )
fsizes[i] = SysLib.bytes2int( data, offset );
for ( int i = 0; i < fnames.length; i++, offset += maxChars * 2 ) {
String fname = new String( data, offset, maxChars * 2 );
fname.getChars( 0, fsizes[i], fnames[i], 0 );
}
}
public byte[] directory2bytes()
public short ialloc ( String filename )
/* allocate Inode for filename (-1 if none) */
public boolean ifree ( short iNumber )
/* deallocate Inode # iNumber */
public short namei( String filename )
/* find Inode for filename (-1 if none) */
}
CSS 430: Operating Systems - ThreadOS File System
11
FileTable
public class FileTable {
// File Structure Table
private Vector table;
// the actual entity of File Structure Table
private Directory dir;
// the root directory
public FileTable ( Directory directory ) { // a default constructor
table = new Vector();
// instantiate a file table
dir = directory;
// instantiate the root directory
}
public synchronized FileTableEntry falloc( String fname, String mode )
// allocate a new file table entry for this file name
// allocate/retrieve and register the corresponding inode using dir
// increment this inode's count
// immediately write back this inode to the disk
// return a reference to this file table entry
public synchronized boolean ffree( FileTableEntry e ) {
// receive a file table entry reference
// save the corresponding inode to the disk
// free this file table entry.
// return true if this file table entry found in table
public synchronized boolean fempty() {
return table.isEmpty();
// return if table is empty
}
// should be called before a format
}
CSS 430: Operating Systems - ThreadOS File System
12
FileTable
public synchronized FileTableEntry falloc( String fname, String mode )
short iNumber = -1;
Inode inode = null;
while ( true ) {
iNumber = ( fname.equals( "/" ) ? 0 : dir.namei( fname ) );
if ( iNumber < 0 ) {
// file does not exist
// create a new Inode (nothing to retrieve from disk)
} else {
// file exists
inode = new Inode( iNumber );
//
retrieve inode from disk
if ( mode.compareTo( "r" ) == 0 ) { //
mode is "r”
// if inode.flag indicates file is not already open for writing
//
break
// else wait until writing is done
} else { /* ... */ }
//
mode is "w", "w+" or "a”
}
}
inode.count++;
// a new FileTableEntry points to it
inode.toDisk( iNumber );
// reflect this inode to disk
FileTableEntry e = new FileTableEntry( inode, iNumber, mode );
table.addElement( e );
// add entry to system-wide FileTable
return e;
// return this new file table entry
}
CSS 430: Operating Systems - ThreadOS File System
13
Inode
public class Inode {
public final static int iNodeSize = 32;
public final static int directSize = 11;
public
public
public
public
public
// fixed to 32 bytes
// # direct pointers
int length;
// file size in bytes
short count;
// # file-table entries pointing to this
short flag;
// how is this file (inode) being used?
short direct[] = new short[directSize]; // direct pointers
short indirect;
// an indirect pointer
Inode () {
// a default constructor (new file)
length = 0;
count = 0;
flag = 1;
for ( int i = 0; i < directSize; i++ )
direct[i] = -1;
indirect = -1;
}
CSS 430: Operating Systems - ThreadOS File System
14
Inode
public class Inode {
...
Inode ( short iNumber ) {
int blkNumber = iNumber / 16 + 1;
byte[] data = new byte[Disk.blockSize];
SysLib.rawread( blkNumber, data );
int offset = ( iNumber % 16 ) * iNodeSize;
length = SysLib.bytes2int( data, offset );
offset += 4;
count = SysLib.bytes2short( data, offset );
offset += 2;
flag = SysLib.bytes2short( data, offset );
offset += 2;
for ( int i = 0; i < directSize; i++ ) {
direct[i] = SysLib.bytes2short( data, offset );
offset += 2;
}
indirect = SysLib.bytes2short( data, offset );
}
...
CSS 430: Operating Systems - ThreadOS File System
DISK
Superblock
int totalBlocks;
int inodeBlocks;
int freeList;
Inode #0
…
32bytes
Inode #15
…
…
Inode #inodeBlocks-1
…
…
15
Inode
public class Inode {
...
void toDisk( short iNumber )
int findIndexBlock()
boolean registerIndexBlock( short indexBlockNumber )
int findTargetBlock( int offset )
int registerTargetBlock( int offset,
short targetBlockNumber )
byte[] unregisterIndexBlock()
}
DISK
Superblock
int totalBlocks;
int inodeBlocks;
int freeList;
Inode #0
…
32bytes
Inode #15
…
…
Inode #inodeBlocks-1
…
…
CSS 430: Operating Systems - ThreadOS File System
16
Opening a File
Test5.java:
int fd = SysLib.open( "css430", "w+" );
SysLib.java:
public static int open( String filename, String mode ) {
String[] args = new String[2];
args[0] = filename;
args[1] = mode;
return Kernel.interrupt( Kernel.INTERRUPT_SOFTWARE, Kernel.OPEN, 0, args );
};
Kernel.java:
case OPEN:
if ( ( myTcb = scheduler.getMyTcb() ) == null )
return ERROR;
else {
String[] s = (String[]) args;
FileTableEntry ftEnt = fs.open( s[0], s[1] );
int fd = myTcb.getFd( ftEnt );
return fd;
}
CSS 430: Operating Systems - ThreadOS File System
17
Opening a File
Kernel.java:
case OPEN:
if ( ( myTcb = scheduler.getMyTcb() ) == null )
return ERROR;
else {
String[] s = (String[]) args;
FileTableEntry ftEnt = fs.open( s[0], s[1] );
int fd = myTcb.getFd( ftEnt );
return fd;
}
FileSystem.java:
FileTableEntry open( String filename, String mode ) {
FileTableEntry ftEnt = filetable.falloc( filename, mode );
if ( mode == "w" )
// release all blocks belonging to this file
if ( deallocAllBlocks( ftEnt ) == false )
return null;
return ftEnt;
}
CSS 430: Operating Systems - ThreadOS File System
18