QMCS 360 Class Notes # 20	Dr. Rick Smith Quantitative Methods and Computer Science
Dr. Smith Home | Research | Classes | Blackboard | Cryptosmith | QMCS Home | UST A-Z | UST Home last update: Tuesday, November 29, 2005

Rest of Class

Today, Thursday, Next Tuesday

NO CLASS on the last day: Thursday, Dec 8

I'll be chairing a conference session

Thursday - Outlines Due -

Next Tuesday -

Today

"Orthogonality" at the interface

Windows NT

File System Comparisons

Orthogonality and I/O

An old computing term - means that the same set of functions applies to all similar objects

In object oriented design this is usually handled through inheritance

In CPUs it means you have instructions to add, subtract, clear, invert, etc. for data in all sizes and formats (8, 16, 32, float)

In I/O systems, it means you use the same system function to "read" and "write" all devices and files

Orthogonality in Unix

All user functions are mapped to a "read" and "write" function

Read and write work on files as well as all kinds of "raw" devices

"Open" and "close" work on both files and on all raw devices

Raw devices, like files, have directory entries

Directories are files, and use standard file calls to access them

Orthogonality and the NT File System

EVERYTHING is a file, even the on-disk data structures that manage the NT file system - allocation maps, etc.

Every byte on the hard drive is defined as existing within some sort of file

NT File System

General Features

Cluster based

Bitmap to track allocated and free blocks

Hierarchical directory structure

"B-Tree" structure within directories

MFT - Master File Table - the fundamental data structure

1 entry for every file in the system

Each entry is addressed by its index into the table (48 bit index)

Each entry is 1KB, but it's an adjustable parameter (never adjusted)

Each entry consists of 1 or more fields

First field is "signature" - 4-byte string indicating the type of entry

"FILE" is a typical entry

"BAAD" indicates a corrupt entry

Next field has flags: entry used/free, entry is directory, ...

Also has 16-bit sequence number, incremented each time it points to a new file

A file is defined by its MFT index plus its sequence number (64 bits)

Distinguishes between older and newer files that share the same MFT entry - detects "stale" file pointers

Has other standard items (link count, space used in this MFT entry, pointer and size of attribute list...)

Rest is variable length attributes

More about the MFT

Surprise: it's a file!

It is defined in MFT entry #0

File system structures like the MFT reside in "metadata files"

Metadata files defined in the first 16 MFT entries

Examples: allocation bitmaps, the boot sector, volume label, root directory

MFT entry Attributes

Common attributes

"Standard info" - flags, access dates/times, owner ID

File name - obvious

Data - the file's data

Bitmap - used in index files and in the MFT to manage space

Format of an attribute

Attribute type identifier

Length of this attribute

Length of name

Pointer to name within attribute structure

Nonresident flag - is the data here in the attribute, or not?

Resident: header contains data size and offset pointer

Nonresident: header describes a "run list" to identify disk blocks that contain the attribute's data

Run List

Tells how to find any logical block in the file, from offset 0 to the end of the file.

Built of "cluster run" descriptions

Cluster run = starting cluster number & number of clusters in a row

If file is "sparse" (internal blocks not allocated), use a "sparse cluster run" that only indicates the number of clusters

Directories - organized as B-trees

B-tree = a tree structure that stores sorted data

Similar concept to a binary search, but implemented in a tree graph

Binary tree nodes

Contain 1 entry of the sorted data

"Upper" pointer points to subtree of data with values greater than node's value

"Lower" pointer points to subtree of data with values less than node's value

NTFS B-tree generalizes this to up to 3 entries per node, with pointers between each one

Filename entry points to the file's MFT entry

"Hard" link = multiple directories point to same file in MFT

"Soft" link = an entry has an NTFS path name.

Properties of File Systems

Tracking free space - how

Directory organization

How do we address a file's contents

File properties reside where?

Redundancy and recovery?