Starting from:
$30
Assignment #2 - Tagline Device Driver (version 1.0) Solution
In this assignment you will write a device driver for the tagline device, as described in the specification here. At the highest level, you will translate tagline operations into low-level disk operations. This will require you to figure out how to store data on the disk in a way that allows later reads to be successfully completed. Read the instructions carefully and follow the instructions to create and tests your implementation. Note these instructions should be read in the context of the class presentation and slides provided here.
System Overview
You are to write a basic device driver that will sit between a virtual application and virtualized hardware. The application makes use of the abstraction you will provide called tagline storage. The design of the system is shown in the figure to the right:
Described in detail below, we can see three layers. The tagline application is provided to you and will call the tagline device driver functions with "tagline operations". these operations create and read/write data to special data abstractions called taglines. You are to write the device driver code to implement this abstraction. Your code will create taglines by sending "RAID operations" to a virtual RAID disk array using a virtual I/O bus.
All of the code for tagline application and virtual RAID array is given to you. Numerous utility functions are also provided to help debug and test your program, as well as simply the creation of readable output. Sample workloads have been generated and will be used to extensively test the program. Students that make use of all of these tools (which take a bit of time up front to figure out) will find that the later assignments will become much easier to complete.
Tagline Abstraction
A tagline is storage abstraction somewhat similar to a data file, with several key differences. The basic idea is that the application will create, read, and write to a tagline. Almost all of the important details of the tagline interface are defined in the tagline_driver.h header file.
The "name" of a tagline is a 16-bit unsigned integer. Note that this is assigned by the application and managed by your device driver.
The tagline consists of a zero-indexed set of blocks that are read from and written to the storage. A file will initially have zero blocks. All reads and writes will be performed on one or more blocks.
The size of tagline blocks is defined as TAGLINE_BLOCK_SIZE in the tagline_driver.h file.
taglines are monotonically increasing, meaning that they are never deleted and they never shrink. Blocks can be overwritten however.
For this assignment, you are to implement 4 functions in tagline_driver.c:
int tagline_driver_init(uint32_t maxlines);
// Initialize the driver with a number of maximum lines to process
This function will initialize and disk interfaces, create local data structures, or any other startup bookkeeping it needs to do to start accepting reads and writes. You will need to format each of the disks before you can use them, so you need to do that in this function.
int tagline_read(TagLineNumber tag, TagLineBlockNumber bnum, uint8_t blks, char *buf);
// Read a number of blocks from the tagline driver
This function reads blks blocks from tagline tag starting from block number bnum and place the contents into the memory region buf. Note that any attempt to read beyond the end of the tagline should result in an error (and nothing copied into the buffer).
int tagline_write(TagLineNumber tag, TagLineBlockNumber bnum, uint8_t blks, char *buf);
// Write a number of blocks from the tagline driver
This function writes blks blocks from memory region buf to tagline tag starting from block number bnum. Writes beyond the end of the tagline should increase the size of the tagline. Note that any attempt to write starting beyond the end of the tagline should result in an error (and nothing written to the tagline).
int tagline_close(void);
// Close the tagline interface
This function closes the taglines and frees up any memory and closes the RAID device interface.
Note that for this assignment we make two restrictions that vastly reduce the complexity of the implementation. First the device driver will only receive requests for a single tagline (you only have to worry about one tagline). Thus,a any request for a tagline other than the first one seen can be rejected by your code with an error. Second, all tagline reads and writes will be for a single block. Thus, you can return an error when any request asks for more or less than a single block.
RAID Abstraction
The raid array is a collection of disks each with a set of fixed sized blocks that are written and read. You are to build a software layer that implements the tagline interface on top of the raid array system (e.g., translate the tagline operations into disk operations).
Each block is of size RAID_BLOCK_SIZE (defined in raid_bus.h).
For this assignment, you can assume that there are RAID_DISKS disks, each with RAID_DISKBLOCKS blocks.
The blocks are indexed 0 to RAID_DISKBLOCK-1
The RAID array is controlled by sending commands through the bus interface. You can send commands on the bus using the following function:
RAIDOpCode raid_bus_request(RAIDOpCode request, void *buf);Where the fields of the 64-bit opcodes are defined as follows:
Bits Description
----- -------------------------------------------
0-7 request type
8-15 number of blocks
16-23 disk number
24-30 unused (for now, always set to zero)
31 - status this is the result bit (0 success)
32-63 block ID
The following commands are available to manipulate the RAID array:
Field
Request Value
Response Value
RAID_INIT - Initialize the RAID interface
Type
RAID_INIT
RAID_INIT
# Blocks
this is the number of tracks to create. The disk will have this times RAID_TRACK_BLOCKS addressable blocks when done.
tracks created
Disk Number
The number of disks to created
disks created
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
0
0
buf
NULL
N/A
RAID_FORMAT - Format a disk in the array. This will zero the disk contents and prepare it for use.
Type
RAID_FORMAT
RAID_FORMAT
# Blocks
0
0
Disk Number
The number of the disk to format
The disk formatted
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
0
0
buf
NULL
N/A
RAID_READ - Read consecutive blocks in the disk array
Type
RAID_READ
RAID_READ
# Blocks
The number of blocks to write to
Blocks written
Disk Number
The disk to read from
The disk read from
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
The starting block number to read from
The starting block number read from
buf
Pointer to buffer containing blocks to read
Pointer to the buffer passed in
RAID_WRITE - Write consecutive blocks to the disk array
Type
RAID_WRITE
RAID_WRITE
# Blocks
The number of disk blocks to write
Blocks written
Disk Number
The disk to write to
The disk written to
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
The starting disk block number to write to
The starting disk block number written to
buf
Pointer to buffer containing blocks to write from
Pointer to the buffer passed in
RAID_CLOSE - shuts down the RAID interface
Type
RAID_CLOSE
RAID_CLOSE
# Blocks
0
0
Disk Number
0
0
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
0
0
buf
NULL
N/A
Summary
To summarize, your code will receive commands from the vritual application. It will do the following functions to implement the device driver.
Initialize the disk array by calling the init & format functions
On writes for "new" blocks, find a location on the disk to put it, then call the RAID commands to get it to store the data
On writes for old blocks, figure out where you put it, then call the RAID commands to get it to overwrite the data
On reads, return the previously stored data in those blocks
Close the array when you are done
Honors Option
The tagline device driver should implement three different block allocation strategies. They should be defined by adding an enumerated type and associated variable that is used to tell the driver which allocation to use for which run. The allocation strategies include:
TAGLINE_LINEAR - this allocation strategy should allocate blocks on the first disk until full, then second, then third, and so on. The blocks on each disk should be allocated from lowest to highest, in order.
TAGLINE_BALANCED - this allocation strategy should allocate blocks evenly across the disks (round-robin). The blocks on each disk should be allocated from highest to lowest.
TAGLINE_RANDOM - this allocation strategy should allocate blocks randomly across the disks. The blocks on each disk should be allocated randmonly as well.
You need to modify the main program to accept run-time parameters "--linear", "--balanced, and "--random". The program should fail if more than one of these is provided, and the driver should be configured with the appropriate value if the parameter is provided. The driver should default to random.
Assignment Details
Below are the step by step details of how to implement, test, and submit your device drivers as part of the class assignment. As always, the instructor and TAs are available to answer questions and help you make progress. Note that this assignment is deceptively complicated and will likely take even the best students a substantial amount of time. Please plan to allocate your time accordingly.
From your virtual machine, download the starter source code provided for this assignment. To do this, use the wget utility to download the file off the main course website:
http://www.cse.psu.edu/~mcdaniel/cmpsc311-f15/docs/assign2-starter.tgz
Copy the downloaded file into your development directory and unpack it.
% cd cmpsc311
% tar xvfz assign1-starter.tgz
Once unpacked, you will have the following starter files in the assign1 directory. All of your work should be done in this directory.
You are to complete the tagline_sim program but implementing the four tagline abstraction functions described above. All of this code will be implemented in the source code file tagline_driver.c. You are free to create any additional functions that you see a need for, so long as they are all in the same code file.
Add comments to all of your files stating what the code is doing. Fill out the comment function header for each function you are defining in the code. A sample header you can copy for this purpose is provided for the main function in the code.
To test your program, you will run it with sample data I provide. To do this, run the program from the command line with sample input sample-workload.dat and sample-workload2.dat. E.g.,
./tagline_sim -v sample-workload.dat
./tagline_sim -v sample-workload2.dat
You must use the "-v" option before the workload filename when running the simulation to get meaningful output. Once you have your program running correctly, you see the following message at the end of the output:
[INFO] Tagline simulation completed successfully.
System Overview
You are to write a basic device driver that will sit between a virtual application and virtualized hardware. The application makes use of the abstraction you will provide called tagline storage. The design of the system is shown in the figure to the right:
Described in detail below, we can see three layers. The tagline application is provided to you and will call the tagline device driver functions with "tagline operations". these operations create and read/write data to special data abstractions called taglines. You are to write the device driver code to implement this abstraction. Your code will create taglines by sending "RAID operations" to a virtual RAID disk array using a virtual I/O bus.
All of the code for tagline application and virtual RAID array is given to you. Numerous utility functions are also provided to help debug and test your program, as well as simply the creation of readable output. Sample workloads have been generated and will be used to extensively test the program. Students that make use of all of these tools (which take a bit of time up front to figure out) will find that the later assignments will become much easier to complete.
Tagline Abstraction
A tagline is storage abstraction somewhat similar to a data file, with several key differences. The basic idea is that the application will create, read, and write to a tagline. Almost all of the important details of the tagline interface are defined in the tagline_driver.h header file.
The "name" of a tagline is a 16-bit unsigned integer. Note that this is assigned by the application and managed by your device driver.
The tagline consists of a zero-indexed set of blocks that are read from and written to the storage. A file will initially have zero blocks. All reads and writes will be performed on one or more blocks.
The size of tagline blocks is defined as TAGLINE_BLOCK_SIZE in the tagline_driver.h file.
taglines are monotonically increasing, meaning that they are never deleted and they never shrink. Blocks can be overwritten however.
For this assignment, you are to implement 4 functions in tagline_driver.c:
int tagline_driver_init(uint32_t maxlines);
// Initialize the driver with a number of maximum lines to process
This function will initialize and disk interfaces, create local data structures, or any other startup bookkeeping it needs to do to start accepting reads and writes. You will need to format each of the disks before you can use them, so you need to do that in this function.
int tagline_read(TagLineNumber tag, TagLineBlockNumber bnum, uint8_t blks, char *buf);
// Read a number of blocks from the tagline driver
This function reads blks blocks from tagline tag starting from block number bnum and place the contents into the memory region buf. Note that any attempt to read beyond the end of the tagline should result in an error (and nothing copied into the buffer).
int tagline_write(TagLineNumber tag, TagLineBlockNumber bnum, uint8_t blks, char *buf);
// Write a number of blocks from the tagline driver
This function writes blks blocks from memory region buf to tagline tag starting from block number bnum. Writes beyond the end of the tagline should increase the size of the tagline. Note that any attempt to write starting beyond the end of the tagline should result in an error (and nothing written to the tagline).
int tagline_close(void);
// Close the tagline interface
This function closes the taglines and frees up any memory and closes the RAID device interface.
Note that for this assignment we make two restrictions that vastly reduce the complexity of the implementation. First the device driver will only receive requests for a single tagline (you only have to worry about one tagline). Thus,a any request for a tagline other than the first one seen can be rejected by your code with an error. Second, all tagline reads and writes will be for a single block. Thus, you can return an error when any request asks for more or less than a single block.
RAID Abstraction
The raid array is a collection of disks each with a set of fixed sized blocks that are written and read. You are to build a software layer that implements the tagline interface on top of the raid array system (e.g., translate the tagline operations into disk operations).
Each block is of size RAID_BLOCK_SIZE (defined in raid_bus.h).
For this assignment, you can assume that there are RAID_DISKS disks, each with RAID_DISKBLOCKS blocks.
The blocks are indexed 0 to RAID_DISKBLOCK-1
The RAID array is controlled by sending commands through the bus interface. You can send commands on the bus using the following function:
RAIDOpCode raid_bus_request(RAIDOpCode request, void *buf);Where the fields of the 64-bit opcodes are defined as follows:
Bits Description
----- -------------------------------------------
0-7 request type
8-15 number of blocks
16-23 disk number
24-30 unused (for now, always set to zero)
31 - status this is the result bit (0 success)
32-63 block ID
The following commands are available to manipulate the RAID array:
Field
Request Value
Response Value
RAID_INIT - Initialize the RAID interface
Type
RAID_INIT
RAID_INIT
# Blocks
this is the number of tracks to create. The disk will have this times RAID_TRACK_BLOCKS addressable blocks when done.
tracks created
Disk Number
The number of disks to created
disks created
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
0
0
buf
NULL
N/A
RAID_FORMAT - Format a disk in the array. This will zero the disk contents and prepare it for use.
Type
RAID_FORMAT
RAID_FORMAT
# Blocks
0
0
Disk Number
The number of the disk to format
The disk formatted
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
0
0
buf
NULL
N/A
RAID_READ - Read consecutive blocks in the disk array
Type
RAID_READ
RAID_READ
# Blocks
The number of blocks to write to
Blocks written
Disk Number
The disk to read from
The disk read from
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
The starting block number to read from
The starting block number read from
buf
Pointer to buffer containing blocks to read
Pointer to the buffer passed in
RAID_WRITE - Write consecutive blocks to the disk array
Type
RAID_WRITE
RAID_WRITE
# Blocks
The number of disk blocks to write
Blocks written
Disk Number
The disk to write to
The disk written to
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
The starting disk block number to write to
The starting disk block number written to
buf
Pointer to buffer containing blocks to write from
Pointer to the buffer passed in
RAID_CLOSE - shuts down the RAID interface
Type
RAID_CLOSE
RAID_CLOSE
# Blocks
0
0
Disk Number
0
0
Status
0
0 if successful, 1 if failure (see log for details)
Block ID
0
0
buf
NULL
N/A
Summary
To summarize, your code will receive commands from the vritual application. It will do the following functions to implement the device driver.
Initialize the disk array by calling the init & format functions
On writes for "new" blocks, find a location on the disk to put it, then call the RAID commands to get it to store the data
On writes for old blocks, figure out where you put it, then call the RAID commands to get it to overwrite the data
On reads, return the previously stored data in those blocks
Close the array when you are done
Honors Option
The tagline device driver should implement three different block allocation strategies. They should be defined by adding an enumerated type and associated variable that is used to tell the driver which allocation to use for which run. The allocation strategies include:
TAGLINE_LINEAR - this allocation strategy should allocate blocks on the first disk until full, then second, then third, and so on. The blocks on each disk should be allocated from lowest to highest, in order.
TAGLINE_BALANCED - this allocation strategy should allocate blocks evenly across the disks (round-robin). The blocks on each disk should be allocated from highest to lowest.
TAGLINE_RANDOM - this allocation strategy should allocate blocks randomly across the disks. The blocks on each disk should be allocated randmonly as well.
You need to modify the main program to accept run-time parameters "--linear", "--balanced, and "--random". The program should fail if more than one of these is provided, and the driver should be configured with the appropriate value if the parameter is provided. The driver should default to random.
Assignment Details
Below are the step by step details of how to implement, test, and submit your device drivers as part of the class assignment. As always, the instructor and TAs are available to answer questions and help you make progress. Note that this assignment is deceptively complicated and will likely take even the best students a substantial amount of time. Please plan to allocate your time accordingly.
From your virtual machine, download the starter source code provided for this assignment. To do this, use the wget utility to download the file off the main course website:
http://www.cse.psu.edu/~mcdaniel/cmpsc311-f15/docs/assign2-starter.tgz
Copy the downloaded file into your development directory and unpack it.
% cd cmpsc311
% tar xvfz assign1-starter.tgz
Once unpacked, you will have the following starter files in the assign1 directory. All of your work should be done in this directory.
You are to complete the tagline_sim program but implementing the four tagline abstraction functions described above. All of this code will be implemented in the source code file tagline_driver.c. You are free to create any additional functions that you see a need for, so long as they are all in the same code file.
Add comments to all of your files stating what the code is doing. Fill out the comment function header for each function you are defining in the code. A sample header you can copy for this purpose is provided for the main function in the code.
To test your program, you will run it with sample data I provide. To do this, run the program from the command line with sample input sample-workload.dat and sample-workload2.dat. E.g.,
./tagline_sim -v sample-workload.dat
./tagline_sim -v sample-workload2.dat
You must use the "-v" option before the workload filename when running the simulation to get meaningful output. Once you have your program running correctly, you see the following message at the end of the output:
[INFO] Tagline simulation completed successfully.
1 file (416.0KB)
