2019/10/6 CITS2002 Systems Programming : The University of Western Australia
teaching.csse.uwa.edu.au/units/CITS2002/projects/project2.php 1/4
Department of Computer Science and Software Engineering
CITS2002 Systems Programming
Project 2 2019. See also: Project 2 clarifications
Project Description
Modern operating systems support programs to archive the contents of file-systems. These programs typically support their own specific file-
formats (examples include the tar and zip formats), or store a whole file-system image inside a single file on your operating system (examples
include the ISO and Apple's dmg disk-image formats).
Whereas the zip archive format attempts to reduce its space requirements by compressing its contents, an alternate approach termed single-
instance storage attempts to reduce space requirements by identifying multiple copies of the same content, and replacing it by a single shared
copy. Thus, if multiple copies of the same file are archived, possibly from different directories, then only a single instance of the files' content will
appear in the archive. Storing files' contents only once, can also reduce internal-fragmentation.
The goal of this project is to write a user-level library in C99, named libsifs, which supports the archiving of files within a simple file-system
contained within a single fixed-size file, termed a volume.
The file-system is notable in that it stores each file (its contents) only once - if multiple copies of the same file are stored within the file-system,
each file's contents will be stored only once. This provides the potential to seemingly store more data in the file-system than what appears
possible.
Successful completion of the project will develop your understanding of some advanced features of the C99 programming language, and your
understanding of how an operating system can support a file-system.
Download, understand, and then extend these starting files: sifs-files.zip
Try the web-based volume viewer: sifs-viewer
The Single Instance File System (SIFS) volume format
Our SIFS volumes are of a fixed size - once created they can neither grow nor shrink. Similarly, files on a volume are immutable - once a file has
been added to a volume it can neither grow nor shrink, though it may be deleted. Volumes consist of three sections, whose concrete
implementation is defined in the provided C99 header file sifs-internal.h :
1. The volume header, consisting of two non-negative integers. The first integer stores the number of blocks in the volume that may be used to
store directory information, file information, or the contents of files. The second integer stores the size, in bytes, of each block, typically 1KB or
4KB.
2. The volume bitmap, records how each block on the volume is being used. While the name volume bitmap suggests that each element
occupies only a single bit, the frequently-used name is only historic. A single 1-byte character is used to record each block's use, represented
as one of four distinct values.
3. Each block stores either a directory-block, a file-block, a data-block (holding files' contents), or is unused.
Directory-blocks have a fixed format.
Each includes the name of the directory and its modification time; the number of entries in the directory (either subdirectories or files);
and, for each entry, the block number (blockID) of each subdirectory or file.
File-blocks have a fixed format.
Each includes an array of characters storing the MD5 cryptographic digest (a summary) of the files' contents; the common length (in
bytes) of every file represented by that file-block; the block number (blockID) of the files' first data-block; the number of files having the
same contents; and an array of each such file's name and its modification time.
Data-blocks have no fixed format.
They hold only files' contents, and no characters in a data-block have any special significance. A first-fit, contiguous data-block
allocation scheme is employed - see Lecture-18. A new file can only be added to the volume if there are sufficient contiguous unused
blocks to support the file's length, or if other file(s) with the same contents have already been stored.
The SIFS Application Programming Interface (API)
User-level programs do not directly interact with the contents of a SIFS volume. Instead, they call functions from your SIFS library to make and
initialise new volumes; make or remove directories; list the contents of directories; and add, read, or remove files from directories. Without
exposing the concrete implementation of the file-system, the library provides an Application Programming Interface (API) to the file-system.
2019/10/6 CITS2002 Systems Programming : The University of Western Australia
teaching.csse.uwa.edu.au/units/CITS2002/projects/project2.php 2/4
Although the functions in your SIFS library execute in the same address space as your own programs, you can consider the functions as if they are
new system-calls provided to support a new type of file-system on an existing operating system. Many of the library's functions need to perform the
same actions, such as opening a volume, and so additional ''hidden'' functions within the library will be necessary.
The prototypes of the required library functions, declared in the provided C99 header file sifs.h, are:
// make a new volume
int SIFS_mkvolume(const char *volumename, size_t blocksize, uint32_t nblocks);

// make a new directory within an existing volume
int SIFS_mkdir(const char *volumename, const char *pathname);

// remove an existing directory from an existing volume
int SIFS_rmdir(const char *volumename, const char *pathname);

// add a copy of a new file to an existing volume
int SIFS_writefile(const char *volumename, const char *pathname, void *data, size_t nbytes);

// read the contents of an existing file from an existing volume
int SIFS_readfile(const char *volumename, const char *pathname, void **data, size_t *nbytes);

// remove an existing file from an existing volume
int SIFS_rmfile(const char *volumename, const char *pathname);

// get information about a requested directory
int SIFS_dirinfo(const char *volumename, const char *pathname, char ***entrynames, uint32_t *nentries, time_t *modtime);

// get information about a requested file
int SIFS_fileinfo(const char *volumename, const char *pathname, size_t *length, time_t *modtime);
Each of the library's functions returns 0 on success, and 1 on failure. Each failed library call also sets the global integer variable SIFS_errno to
describe the cause of the error. All possible values of SIFS_errno are defined in provided C99 header file sifs.h.
Examples of use
This project requires a library of functions, named libsifs.a , to be developed. The library does not contain a main() function and so, by itelf, it is not
an executable program. Instead, other programs requiring access to a SIFS volume and its contents will be linked with the libsifs.a library and,
when executed, will call the SIFS API functions and check their return value(s).
For example, imagine we have a simple program, named sifs_put to copy a file from the current directory to a SIFS volume. We could compile and
link such a program with:
prompt> cc -std=c99 -Wall -Werror -pedantic -o sifs_put sifs_put.c -lsifs -lm
and then execute the program with:
prompt> ./sifs_put myvolumename myfilename
where the program's argument myvolumename provides the name of the SIFS volume (a large single file holding the archive) and myfilename
provides the name of the (local) file to be stored on the volume. As a convenience, the sifs_put program could obtain the desired SIFS volume
name from an environment variable, and then not require it on the command-line:
prompt> export SIFS_VOLUME=/Users/chris/sifs-1
prompt> ./sifs_put myfilename
Remembering that, once created, a SIFS volume has a fixed size, and that its role is to store only a single copy of duplicate file content, then the
following commands will store two (identical) files but not require any additional space:
prompt> ./sifs_put myfilename
prompt> cp myfilename myfilename-today
prompt> ./sifs_put myfilename-today
Notes
To develop a portable file-system format, a number of data-types are used that may be new to some students:
uint32_t - a non-negative 32-bit integer, used to count things.
size_t - a non-negative 64-bit integer, representing the size (in bytes) of things, as returned by the strlen() function.
time_t - a 64-bit integer, representing the number of seconds since Jan 1st 1970, as returned by the time() function.
API functions that receive character strings as parameters define those parameters with const char *
const is a C99 keyword, short for constant, and is used here when a function promises not to modify what its parameter points to.
2019/10/6 CITS2002 Systems Programming : The University of Western Australia
teaching.csse.uwa.edu.au/units/CITS2002/projects/project2.php 3/4
API functions do not print anything - even if they detect an error.
A volume's root directory is always identified by the first bitmap entry; occupies the first directory-block; has the empty-string as its directory
name; and cannot be deleted.
Each directory or file name may be up to 32 bytes long, including its terminating NULL-byte. No other character has any significance in a
name. The directory separator character, '/', is not stored in any directory or file name.
Unlike traditional Unix-style directories, directories on a SIFS volume do not contain entries for "." or ".."
(because processes can never 'cd' into a SIFS volume, or traverse 'up' a filetree).
Each modification time is stored in an integer (a data-type named time_t), as returned by Unix's time() function. Even though files (their
contents) cannot be modified, we still refer to their modification time rather than their creation time to be consistent with the modification time
of each directory-block.
The MD5digest() function returns a pointer to a fixed-size block of 16 bytes, termed a message-digest. Two files are deemed to be identical if
the MD5digest() function returns identical digests for each file. Your project must employ MD5 digests to determine and record if two files are
identical. While all file names will be stored on the volume, the data-blocks of identical files should only be stored once per volume. A
message-digest is not a traditional C string and, so, is not guaranteed to be end in a NULL-byte. However, the provided MD5_format()
function assists by formatting an MD5 digest as a 32 character string.
It is anticipated that a successful project will need to use (at least) the standard C99 and POSIX functions:
stat(), fopen(), fread(), fwrite(), fseek(), fclose(),
time(), ctime(),
memset(), memcmp(), memcpy(),
strlen(), strcpy(), strcmp(),
malloc(), and free(),
Project requirements
1. Your library must be named libsifs.a
2. The functions in your library must be developed in multiple source files and must be compiled and linked using a Makefile, containing
approriate variable definitions and automatic variables.
3. Your library must provide all of the API functions listed above. The source-code for the SIFS_mkvolume(), SIFS_perror() and MD5 functions
are provided for you.
4. Your library must use the provided values of SIFS_errno to report its own errors. For example, if requested to delete a file that does not
exist on a volume, your library should set SIFS_errno = SIFS_ENOENT; and the function should return 1.
5. Your project must employ sound programming practices, including the use of meaningful comments, well chosen identifier names;
appropriate choice of basic data-structures, data-types, and functions; and appropriate choice of control-flow constructs.
6. While it is possible for all students to gain full marks (40/40) by completing all of the standard requirements, those wishing a challenge
may wish to develop an additional API function named SIFS_defrag(). The function will attempt to coalesce all unused blocks into a single
contiguous area at the end of the volume's third section. This will possibly enable new large files to be added to a volume that previously
suffered from much external-fragmentation. Completing this additional task will not push your final mark beyond 40/40, but you may reclaim
up to 8 marks that you lost in the other stages of the marking.
Assessment
The project is due 11:59PM Fri 18th October, and is worth 20% of your final mark for CITS2002.
It will be marked out of 40. The project may be completed individually or in teams of two (but not teams of three).
You are strongly encouraged to work with someone else - this will enable you to discuss your initial design, and to assist each other to develop
and debug your joint solution. Work together - do not attempt to split the project into two equal parts, and then plan to meet near the deadline to
join your parts together.
20 of the possible 40 marks will come from the correctness of your solution. The remaining 20 marks will come from your programming style,
including your use of meaningful comments; well chosen identifier names; appropriate choice of basic data-structures, data-types and functions;
and appropriate choice of control-flow constructs.
During the marking, attention will obviously be given to the correctness of your solution. However, a correct and efficient solution should not be
considered as the perfect, nor necessarily desirable, form of solution. Preference will be given to well presented, well documented solutions that
use the appropriate features of the language to complete tasks in an easy to understand and easy to follow manner. That is, do not expect to
receive full marks for your project simply because it works correctly. Remember, a computer program should not only convey a message to the
computer, but also to other human programmers.
Your project will be marked on the computers in CSSE Lab 2.03, using the macOS environment. No allowance will be made for a program that
"works at home" but not on CSSE Lab 2.03 computers, so be sure that your code compiles and executes correctly on these machines before
you submit it.
2019/10/6 CITS2002 Systems Programming : The University of Western Australia
teaching.csse.uwa.edu.au/units/CITS2002/projects/project2.php 4/4
Submission requirements
1. The deadline for the project is 11:59PM Friday 18th October (end of week 11).
2. Your submission will be compiled, run, and examined using the macOS platform on computers in CSSE Lab 2.03. Your submission must
work as expected on this platform. While you may develop your project on other computers, excuses such as "it worked at home, just not in
the lab!" will not be accepted.
3. Your submission's C99 source file should each begin with the C99 block comment:

/* CITS2002 Project 2 2019
Name(s): student-name1 (, student-name2)
Student number(s): student-number-1 (, student-number-2)
*/
If working as a team, only one team member should make the team's submission.
4. You must submit your project electronically using cssubmit. You should submit all C99 source-code (*.c) and header (*.h) files and a
Makefile that specify the steps required to compile and link your library. You can submit multiple files in one submission by first archiving
them with zip or tar. The cssubmit facility will give you a receipt of your submission. You should print and retain this receipt in case of any
dispute. Note also that the cssubmit facility does not archive submissions and will simply overwrite any previous submission with your latest
submission.
5. You do not need to submit any additional application programs or testing scripts that you used while developing your project.
6. This project is subject to UWA's Policy on Assessment - particularly §10.2 Principles of submission and penalty for late submission. In
accordance with this policy, you may discuss with other students the general principles required to understand this project, but the work you
submit must be the result of your own efforts. All projects will be compared using software that detects significant similarities between
source code files. Students suspected of plagiarism will be interviewed and will be required to demonstrate their full understanding of their
project submission.
Good luck!
Chris McDonald.