COMP2017 9017 Assignment 3
Due: 23:5919May2024
Thisassignmentisworth20%ofyourfinalassessment
Assignment 3 - ByteTide - 20%
You are tasked with constructing a P2P File-Transfer program that will allow sending, receiving and
detectionofanomalousdatachunks. Theactivitythatyourprogramwillparticipateinwillhandlethe
followingactivities:
• Loadingaconfiguration
• Loadingpackagefilesandparsingtheirformat
• Checkingtheintegrityofthefilematchingtotheconfigurationfile’spath
• Managingmanyfilesthatarecompletedandincomplete
• Complieswithanetworkprotocoltocommunicatewithpeers
• Informingaclientprogramofthelatestinformationofyourpeerandthefilesitmanages
• Finaliseandcheckthatdownloadedfilesmatchexpectedoutcome
• Elegantlyhandleshutdownanddisconnectionsfrompeers.
To reiterate, the program’s aim is to manage files, check integrity of chunks and files, share files
and chunks, handle peer connections and requests. Unlike other file-transfer programs, there are no
trackerorrelaysystemsinplace. APeerisanotherprogramcomplyingwiththisspecification. Itwill
needtoimplementtheconfiguration,integritychecking,networkprotocolandobjectmanagement.
It is advisable that while reading this document that you also refer to the glossary if you do not
understandcertaintermsoutlinedinthisdocument.
We strongly recommend reading this entire document at least twice. You are encouraged to ask
questions on Ed after you have first searched, and checked for updates of this document. If the
question has not been asked before, make sure your question post is of "Question" post type and is
under"Assignment"category→"A3" subcategory. Pleasefollowthestaffdirectionsforusingthe
question template. As with any assignment, make sure that your work is your own1, and that you do
notshareyourcodeorsolutionswithotherstudents.
It is important that you continually back up your assignment files onto your own machine, flash
drives, external hard drives and cloud storage providers (as private). You are encouraged to submit
yourassignmentregularlywhileyouareintheprocessofcompletingit.
1NotGPT-3/4’s,ChatGPT’sorcopilot’s,etc.
1
COMP20179017
1 Part 1 - ByteTide Package Loader & Merkle Tree
To get started, you will need to be able to parse a .bpkg file and load it. To assist you with writing
your code and complying with the test program, you are advised to complete the pkgchk.c file in
thesrcdirectory.
1.1 The Package and its File Format (.bpkg)
In this program, a file is composed of several anomalous data chunks. The chunks are organised in
a specific way such that when they are combined, the entire contents of the file can be constructed
and presented to the user. A package defines the necessary information and resources required to
constructthecontentsofafile. Packagesrepresentauniquefilegivenbyanidentifierstringident.
Thepackagefileformatisatextformatthatwillneedtobeparsedbyyourprogram. Thepackagefile
format has the following fields. Please refer to the hash and chunk parts of the glossary. To also
clarify, the package file, can be modelled as a binary tree, the term h, refers to the height of the tree
inthisinstance.
• ident, hexadecimal string (1024 characters max), the identifier is used within the network to
identifythesamepackages.
• filename, string (256 characters max), This is used to help save and locate the file to update
whendataissenttoit.
• size,uint32_t,specifiesthesizeinbytes
• nhashes, uint32_t, specifies the number of hashes that are pre-computed from the original
file. There must be only 2ˆ(h-1)-1 hashes which will correspond to the hashes of all non-leaf
node
• hashes, string[2ˆ(h-1) - 1] (64 characters for each string), these correspond to the number
hashesinthepreviousnhashesfield.
• nchunks, uint32_t, specifies the number of chunks. The number of chunks must be a 2ˆ(h-1)
value.
• chunks,struct[2ˆ(h-1)],eachchunkhavethefields: hash,offsetandsize.
– hashreferstoastring(64characters),correspondingtothedatablockhashvalue
– offset,uint32_t,istheoffsetwithinthefile
– size,uint32_t,isthesizeofthechunkinbytes
The format below gives an outline to the structure of a .bpkg file. Refer to the resources folder
inthescaffoldforarealexample.
SystemsProgramming Page2of18
COMP20179017
ident:
filename:
size:
nhashes:
hashes:
"hash value"
...
nchunks:
chunks:
"hash value",offset,size
...
1.2 Package Loading
The focus of this task is to load the .bpkg file and also store the details into a merkle tree. Please
refertoSection1.3forinformationonamerkletree.
• Readandload.bpkgfilesthatcomplywiththeformatoutlinedinSection1.1
• Once the .bpkg has been loaded successfully, it is advisable that your program also knows if
the file exists or not and has functionality to construct a file of the size outlined in the file.
Refertopkgchk.c:bpkg_file_checkfunction.
• Implement a merkle tree. Use the data from a .bpkg to construct a merkle-tree Refer to
pkgchk.c:bpkg_get_all_hashesand
pkgchk.c:bpkg_get_all_chunk_hashes_from_hash functions, as you should be able
tosatisfytheseoperationsafterimplementingamerkletreewithoutanyIOonthedatafile.
• Computing the merkle tree hashes, ensuring that combined hashes match the parents hashes
whencomputedandfindingminimumcompletedhashes. Referto
pkgchk.c:bpkg_get_completed_chunksand
pkgchk.c:bpkg_get_min_completed_hashes functions. You will need to perform vali-
dationonthechunksanddiscoverportionsofthefile.
Theaboveverifieschunksagainstpackagefilesandthedata’sintegrity.
1.3 What is a merkle tree?
Binary Tree A merkle tree is a variation on a binary tree. A binary tree is tree data structure,
whereanodeiscomposeofthefollowing.
• Itholdsavalue/data
• Usuallyimplementedtoholdakeyaswell(Key-Value/MapDataStructure)
• Connectedtotwoothernodesthatarereferredtoaschildren. Thesearereferredtoasleft
andrightnodes.
AcommonstructurewithinCforabinarytreenodeisasfollows.
SystemsProgramming Page3of18
COMP20179017
struct bt_node {
void* key;
void* value;
struct bt_node* left;
struct bt_node* right;
};
The above node, holds a key that will allow it to be searchable with the rule that it must be
unique. Italsoholdsavalue,whichcanbeassignedtoarbitrarydata.
Please Note: When building a tree with a key field that allows you to perform a search an efficient
tree search, you will need to ensure that your tree is using an appropriate function for the job. Hint,
if your tree is going to be multi-purpose, consider giving your tree a function pointer to compare the
key.
Tonavigateand/ortraverseatree,you’dbeadvisedtotraverseitinin-ordertraversal. Pleasemake
surerefertoyourtreetraversals. Pleaserefertothefollowingdocumentstoreviseontree-traversals:
• Tree-Traversal-Wikipedia
• Visualgo-BST
Qualitiesofamerkletree Amerkletreemustistypicallyaperfectorfull and complete
binary tree but it can also be represented as a just a complete binary tree (Refer to Errata,
Variations and Notes).
• Givenadepthofd,thetotalnumberofnodesinyourtreewillbe2ˆd - 1
• Alllevelsarefull(necessaryforaperfectbinarytree).
• Amerkletreewillhave2ˆ(d-1)nodesatdepthd,thesewillrefertoyourchunks.
• Amerkletreewillhave2ˆ(d-1) -1non-leaf-nodes.
• Allleaveshavethesamedepth(noskewing)
All nodes in a merkle tree have a hash value. Hashes of a leaf node corresponds to a hash value of a
datachunk. Thisvalueisderivedfromcomputinghashvalueofthedatachunkitself.
Allothernon-leafnodesderivetheirhashvaluebyhashingtheirchildren’shashvaluestogether.
Letsbreakdowntheabovediagram.
• L1-L4aredatablocks,theserefertochunksinafile.
• Your leaf nodes 0-0 to 1-1 use a hash function to compute the hash of those data blocks.
Giventhispartalready,wehaveenoughinformationtovalidateindividualblocks.
PseudocodeExample: self.hash = Hash(DataBlock[i])
• Your non-leaf nodes 0, 1 and root, compute their hashes by combining the hash of their chil-
dren into a long string and compute the hash of that (Refer: Errata, Variations and
Notes)
PseudocodeExample: self.hash = Hash(left.hash + right.hash)
SystemsProgramming Page4of18
COMP20179017
Figure1: MerkleTree-Wikipedia
The following is in relation to the .bpkg file and your merkle tree’s construction. You will have
an expected hash value stored by your nodes and a computed hash value that you can use to 1)
compute the hash on datablocks if it is a leaf node, or 2) compute the hash from the concatenation of
leftandrightnodehashesifitisanon-leafnode.
The following is an expansion of the operations. We are going through an example of computing the
hashofrootnodeofatreewith7nodes(similartothediagram):
ExpansionPseudocode,withsteps:
We need to compute the hash of the left and right child
1. Hash(root) = Hash(
Hash(root.left) + Hash(root.right)
)
Since left and right child are not leaf nodes, we need to do it again
2. Hash(root) = Hash(
Hash(
Hash(root.left.left) + Hash(root.left.right)
)
+
Hash(
Hash(root.right.left) + Hash(root.right.right)
)
)
SystemsProgramming Page5of18
COMP20179017
We have found the leaf nodes
Compute the hash of the data blocks, the size is the chunk size as
outlined in the .bpkg
3. Hash(root) = Hash(
Hash(
Hash(DataBlock[0]) + Hash(DataBlock[1])
)
+
Hash(
Hash(DataBlock[2]) + Hash(DataBlock[3])
)
)
We concatenate the leaf children hashes that is assigned to their
`computed` field
4. Hash(root) = Hash(
Hash(
root.left.left.computed + root.left.right.computed
)
+
Hash(
root.right.left.computed + root.right.right.computed
)
)
Once again, concatenate the children hashes and compute the hash
of that
5. Hash(root) = Hash(
root.left.computed + root.right.computed
)
Tohelpyougetstarted,youcanusethefollowingstructaswellassomehelpfulscaffolddata.
struct merkle_tree_node {
void* key;
void* value;
struct merkle_tree_node* left;
struct merkle_tree_node* right;
int is_leaf;
char expected_hash[64]; //Refer to SHA256 Hexadecimal size
char computed_hash[64];
};
struct merkle_tree {
struct merkle_tree_node* root;
size_t n_nodes;
};
Feelfreetoaddandmodifythestructabove.
SystemsProgramming Page6of18
COMP20179017
Do note You can construct a merkle tree that isn’t a perfect binary tree. However, this may make
managementofyourdatamoredifficult. RefertoErrata,VariationsandNotes.
Do note Please make sure when you compute the hash, you use the hexadecimal representation.
This is very important for non-leaf nodes that are computing the hash from an ordered concatenation
oftheirchildren(left+right)hashes.
1.4 Errata, Variations and Notes
• Implementations: It isn’t necessary for a merkle tree to be a full or complete binary tree. You
could potentially have a merkle tree with more than 2 children Or not all leaf nodes are on the
samelevel
However,wehavemadethisassumptiontohelpsimplifythedatastructure.
• Same-chunks, different positions: As through experimenting, you may have found that if you
have chunks that contain the same data, in this case. Your implementation will need to either
assumethiswillnothappenorcontainnecessarydatatodifferentiateit.
– PleaserefertoREQpacket,specificallyoffsetparttohelpresolvesearches.
– Youcanhaveabit-fieldkeyalongsidethissimilartothediagramintheprevioussections.
• More data than needed: For the most part, the file has been provided with more data than
required to help with implementing this data structure but also ensure that other parts aren’t
restrictedifitisinanincompletestate.
• Usinghexadecimalhashorbyte-hash: Thestaffimplementationusesthehexadecimalhashand
while computing with the byte-hash is not-incorrect, it will yield different results to the test
cases. Pleasemakesureyoucomplywiththis.
1.5 Checklist
• Parsevalid.bpkgfiles,ensureyoucanreadeachfieldofthem.
• Constructamerkle treefromthebpkgfilesafterparsing.
• Implementallthefunctionspkgchk.c.
• Run and compile make pkgchk.o and that will be able to compile pkgchk.c (Required
fortestcases)
• YouarefreetomodifytheMakefiletorefertoyourcfilesyouwilluseinyourbuildtargets.
• Run and compile make pkgchecker, and compile against pkgmain.c to test your pro-
gramlocally.
SystemsProgramming Page7of18
COMP20179017
2 Part 2 - Configuration, Networking and Program
You are now tasked with writing a program that will facilitate P2P file-transfer. Your program will
needtocompletethefollowingtasks:
• Load a basic configuration file, your program will need to maintain the directory path it will
store
• Implement and comply with the protocol to communicate with other peers within the network
itself.
• Implement the commands for your program, these will include connecting. Your program will
needtoconnect,disconnectandretrievepeerinformation. Handlepackageloadingandremov-
ing,retrievalofchunksfromotherpeers.
This part deviates a little from part 1 as it is not completely necessary to build a merkle tree to get
started on this part, let alone complete it. However It is necessary to be able to load a .bpkg file,
retrievetheident,filename,size,nchunksandchunksthemselvesforthispart.
Thescaffoldhasprovidedthefollowingfilesforthenextsectionsforyoutoimplement.
• src/peer.c,-Writepeermanagementcodehere
• src/package.c-Writeyourpackagemanagementlogichere
• src/config.c-Writeyourconfigurationlogichere
• src/btide.c,Containsthemainfunction,startingpointoftheprogram.
You are still free to change and alter the contents of the src folder how you see fit, however, your
Makefilestillneedstobuildtherequiredtargets.
Makesureyourprogramisabletobebuildwithmake btide,thisshouldproduceanexecutable.
2.1 Configuration File
Your program will need to parse and load a configuration file that will be used to setup folder that it
willeitherneedtocreateor,ifitexists,loadexistingpackagesfromandrefertoanexistingfile.
Yourconfigurationfilewillbepassedtoyourprogramviacommandlinearguments.
./btide config.cfg
Theprogram’sconfigurationfilewillusethefollowinginformation:
• directory, string, path local to the system that store .bpkg files and the files that are
mapped in there. If the directory does not exist, the program should attempt to create it. If the
programisunabletocreatethedirectoryoritisafile,theprogramshouldexitwithexitcode3.
SystemsProgramming Page8of18
COMP20179017
• max_peers, int, this field is the number of peers the program can be connected to. It is a
valuebetween[1,2048]
If the max_peers value is set to an invalid number, your program should exit, with exit with
exitcode4.
• port, uint16_t, this field specifies the port the client will be listening on. Acceptable port
range(1024,65535].
Iftheportvalueissettoaninvalidnumber,yourprogramshouldexit,withexitwithexitcode
5.
Exampleoftheconfigurationfile:
directory:downloads
max_peers:128
port:9000
Each field has an action if the constraints of that field are not met as above. If any fields are missing,
theconfigurationshouldberejected.
2.2 Network Protocol and Implementation Details
Thesectionbelowwilloutlinehowyourprogramwillcommunicatetootherprogramsonanetwork.
Itisadvisablethatyourprogramalsoholdsdatarelatedtopeersandpackages.
Network Protocol Your program can act as both a server and client to participants among the
network. You will need to be able to form a listening socket to accept incoming connections but also
havetheabilitytoformnewconnections.
The network protocol will use ‘TCP/IP’ data packets to form connections. Your program should use
thefollowingpacketstructurebelow.
union btide_payload {
uint8_t data[PAYLOAD_MAX];
};
struct btide_packet {
uint16_t msg_code;
uint16_t error;
union btide_payload pl;
};
Belowaretheonlymsg_codevaluesthatcanbeset
PKT_MSG_ACK 0x0c
PKT_MSG_ACP 0x02
SystemsProgramming Page9of18
COMP20179017
PKT_MSG_DSN 0x03
PKT_MSG_REQ 0x06
PKT_MSG_RES 0x07
PKT_MSG_PNG 0xFF
PKT_MSG_POG 0x00
Your program can send and receive the following packet types and their byte code value. All packets
shouldbe4096bytes,andtheirpayloaddata(ifnotempty)shouldfollowtheorderasspecifiedbelow
as the testing system expect data in this format. Padding is not required between different payload
parameters.
• ACP (0x02), when a peer connects to your program, you will need to acknowledge that you
haveacceptedtheconnectionsoitcanconfirmitcanaddittoitsownpeerlist. Ifyourprogram
connects to peer, you should wait for an ACP message back before you add the peer to your
ownpeerlist. Ifthepeerdoesnotrespond,yourprogramcankilltheconnection.
• ACK (0x0c), when your program receives an ACP packet after a connect, you will send a
messagebackwithanACK.Thisistosimplyacknowledgethatyouhavereceivedthemessage.
• DSN (0x03), when a peer wants to disconnect from another peer, it will send a message to the
peer,tellingthatitwillbedisconnecting. Thepeerthatoriginatedthemessagewillcloseoffits
socketandendtheconnection.
Your program should detect when a shutdown has occurred by a peer that may not sent DSN.
Pleasecheckman recvandman sendfordetectingthesecases.
• REQ (0x06), This packet is sent to a peer to request data for a particular chunk. The re-
quest packet will send the
ofdataback.
Theorderinthepacketisasfollows: file_offset,data_len,chunk_hashand
identifier.
If the peer sends you a REQ packet but you do not have the expected file or chunk available,
youwillneedtoinformtherequesterofanerrorintheRESpacket.
• RES(0x07),ThispacketissenttoanoriginatorofaREQpacket,itwillcontain:
(4 bytes, uint32_t), (2 bytes, uint16_t) and most importantly
(max2998bytes).
Theorderinthepacketisasfollows: file_offset,data,data_len,chunk_hashand
identifier.
Theresponsepacketwillsenddatafromthechunktotherequester,sincethefile
component may not match the
needtosendmultipleRESpacketstosatisfythelengthofdatarequested. Thisisnormalaspart
oftheREQ-RESflow.
SystemsProgramming Page10of18
COMP20179017
If the peer does not have the data available, a error byte fields should be set to a number > 0.
Thiswillnotifytherequesterthatthecurrentpeerdoesnothavethedatarequested.
Ifitisdetermined,afteraREQ-RESconversationhasfinished,thatthechunksentisinvalid,the
chunkshouldbesilentlyignored.
• PNG (0xFF), This packet is sent out with the intent to check if a peer is still alive. Nominally,
this is usually sent out periodically, however in this implementation we will send it out when
PEERScommandiscalled.
Noerrorhandlingisnecessaryforthisparticularpacket.
• POG (0x00), This is a pong message that will be sent to the originator of the PNG(0xFF)
message.
The SIGPIPE signal could be raised, in particular with multi-threaded solutions (commonly con-
nection perthread solutions) thatmay not know theconnection has beenterminated. Makesure your
programhandlesthissignalandalsodetectserrorswithyoursocketsastheyarise.
All packets are fixed 4096 byte packets. This results in simple packet handling code within your
program.
2.3 Building a CLI
To finish and to test your program, you will need to build a command line interface. There are
a handful of commands that need to be implemented which also imply a certain amount of book
keeping.
Commands Your program must be able to utilise the following commands. The commands are
providedviastandardinput. YourprogramwillstayaliveuntilQUITcommandisinputted.
Allcommandswillhavemaximumof5520characterswhichcanfitthecommand,identifierandpath
ifeverrequired.
Do note, it is intended that the commands are case sensitive. You can assume command arguments
aredelimitedbyexactlyonespace2 andshouldhavenoleadingandtrailingcharacters.
• CONNECT
This command will attempt to connect to a peer within the network itself. Your program will need to
constructasocketandattempttoconnecttoanotherpeeronthenetwork. man 2 socketformore
information. PleaserefertoACPandACKpacketsinthenetworkprotocolsection.
Iftheconnectcommandsucceeds,yourprogrammustoutput:
Connection established with peer.
Iftheconnectcommandfails,yourprogrammustoutput:
Unable to connect to request peer
2exceptforADDPACKAGEinwhichthefilenamemaycontainspaces
SystemsProgramming Page11of18
COMP20179017
If the ip and port given, have already been connected to and the connection is alive, your program
mustoutput: Already connected to peer
Ifatheiporporthasnotbeenspecified,yourprogramshouldoutput
Missing address and port argument.
• DISCONNECT
This command will disconnect from a peer and remove it from a peer list. Please refer to the DSN
packetinthenetworkprotocolsection.
If the peer is connected and in your program’s peer list, your program must disconnect with the peer
andoutputDisconnected from peer.
If the peer does not exist in your program’s peer list, your program must output: Unknown peer,
not connected
Ifatheiporporthasnotbeenspecified,yourprogramshouldoutputMissing address and
port argument.
• ADDPACKAGE
Thiscommandwilladdapackagetomanage.
Ifathefilehasnotbeenspecified,yourprogramshouldoutputMissing file argument.
If the file does not exist or you do not have permission to use it, Your program must output:
Cannot open file
Ifthefileisnotavalidbpkgfile,yourprogrammustoutputUnable to parse bpkg file.
• REMPACKAGE
whereidentisidentifierorpartialidentifier.
Thiscommandwillremoveapackagethatisbeingmaintainedbytheprogram.
Ifatheidenthasnotbeenspecified,yourprogramshouldoutput
Missing identifier argument, please specify whole 1024 character
or at least 20 characters.
Iftheidentisnotmanagedbyyourprogram,yourprogramshouldoutput:
Identifier provided does not match managed packages
Onsuccess,theprogramwilloutputPackage has been removed
• PACKAGES
Your program should report on the status of the packages loaded. Your program will have need to
maintainalistofpackagesthathavebeenaddedinworkingmemory.
Ifyourprogramisnotmanaginganypackages,yourprogramwilloutput
No packages managed.
Ifyourprogramismanaging1ormorepackages,yourprogramwilloutputinthefollowingformat:
SystemsProgramming Page12of18
COMP20179017
[1..N]. <32 char identifier>,
Example:
1. 0c4d036a2161aa6525743d44725e6212, song5.mp3 : INCOMPLETE
2. 13d608773eb8842426fddb8131d5c184, song6.ogg : COMPLETED
...
• PEERS
Listsallconnectedpeers. ThiswillalsotriggeraPNGpackettobesenttoallpeersyouareconnected
toonthenetwork.
Ifyourprogramisnotconnectedtoanypeers,itwilloutput: Not connected to any peers
Ifyourprogramisconnectedto1ormorepeers,yourprogramwilloutputinthefollowingformat:
Connected to:
[1..N].
Example:
Connected to:
1. 192.168.1.1:9001
2. 192.168.2.120:1723
...
• FETCH
Requests chunks related to the hash given. Please refer to REQ and RES packets in the network
protocol section. If an offset is specified, it will use this additional info to narrow down a hash at a
particularoffsetofthefile. Theoffsetwillneedtomatchthestartofthatchunkandmustbeanumber
greaterthanorequalto0.
Ifthenumberofargumentsprovideddoesnotmatch3,programwilloutput:
Missing arguments from command
If the ip and port is missing from the peer list, your program will output: Unable to request
chunk, peer not in list
Iftheidentifierismissingfromthepackagelist,yourprogramwilloutput: Unable to request
chunk, package is not managed
Ifthehashdoesnotexistinthepackage,yourprogramwilloutput
Unable to request chunk, chunk hash does not belong to package
Iftheargumentsspecifiedarecorrect,aREQpacketwillbesenttothepeer.
• QUIT
Theprogramquits,noerrorshouldbeoutputtedfromthiscommand.
AnyerroneouscommandswillrequiretheprogramtooutputInvalid Input.
SystemsProgramming Page13of18
COMP20179017
2.4 Checklist
• ImplementallthepackettypesintheNetworkProtocolSection
• Implementadatastructuretoadd,removeandretrievepeerinformation.
• Implement a data structure to add, remove and retrieve package information that your peer is
managing.
• Implementthecommandsforyourclientprogram.
• Ensure that your packets are compatible between clients, test your program in class or with
friendsatuni.
• ImplementatestsformerkletreebasedonA3testsandanynewtestsyouhavederivedsince.
• ImplementatestsfornetworkingbasedonA3testsandanynewtestsyouhavederivedsince.
2.5 Implementation Help
Thissectionhereistohelpgiveyouhintstoimplementyournetworkingapplication.
• A simple networking technique is to use thread-per-connection. This means that, when a con-
nectionisaccepted,itissplitoffintoanotherthread.
However, you will need to identify and manage when a connection has been terminated and
detectwhenathreadhasfinished.
• When managing peers, use a dynamic array or refer to the max_peers property. How-
ever,youwillneedtokeeptrackofthenumberofpeersthatarecurrentlyconnected
• Thestructpacketgivenprovidesagoodhintastowheretoaddspecificpacketdatainformation.
Considerwhyaunionwouldbebestsuitedthere. Inadditional,itmakesiteasytojustuseonly
asingletypetohandlepacketsthataresenttoyourprogram.
• Handling packets is similar to handling commands via standard input. As long as you got the
message,youjustneedtomakethedecisionsbasedonthetypeofpacket.
2.6 Resources
You have been supplied additional resources to help with your assessment. These resources will
include command line tools and utility functions that you will need to use during the development of
yourprogram. Usethemtohelpwithtestingdifferentcomponentsandconstructingfilestestcases.
• SHA256Implementation(crypt/sha256.c/.h),usedforhashingdataforthemerkletree,
Alsocomeswithsha256utilityprogram.
• PackageMake(./pkgmake --help),usedforconstructingapackagefile.
• Packet Validator (./pktval --help), used for checking basics of packets sent across the
network.
• Gettingstartedwithnetworking(./getting_started/),folderwithbasicnetworkingex-
amplecode.
SystemsProgramming Page14of18
COMP20179017
• Example Packages (/packages/), a folder with a variety of example packages and files to
test and inspect. You are encouraged to use xxd to inspect the files or even break up the files
toverifydifferentparts.
• split command (./split --help), use this command to break apart a file and run it
againstthesha256programincludedwiththeassessment.
3 Assumptions
This assessment makes a few reasonable assumptions around how packets and data will be encoded
without explicitly outlining it in each section. It is also reasonable to make it clear how communica-
tionistobeaffordedifbetweenallpeers.
Forsakeofsimplicity,fileandnetworkbinarydataissentorsavedaslittleendian. Forsingularbytes
this does not have any serious bearings however, for integers this is significant to outline as the order
ofbytesmaybedifferentbetweenaBEandLEsystemwiththissoftware.
4 High performance Merkle tree
For the high mark, you would have a working implementation for all parts. If you cannot pass most
testcases,thissectionwillnotbegraded.
You are to optimise your merkle tree implementation to improve one of the following areas of your
choosing:
• minimising the time required for the I/O bound problem of large volumes of data to load and
hashusingmultiplethreads
• minimisingthetimerequiredfortheCPUboundproblemofcalculatingallhashesofthemerkle
treeusingmultiplethreadsforinsertions
• buildingamerkletreefroma.bpkgfileinparallel
Forthismark,youwillneed:
• abenchmarkmethodthatcanbeexecutedbythegrader,
• testingdata(ideallyprocedurallygeneratedfromthebenchmark),
• a report of 500-1000 words describing which of the above optimisations you are aiming for,
andwhereyouappliedtheseinthecode.
Ideally,youachieveaspeedupproportionaltothenumberofthreadsand/orsizeofinput. Agraphof
thisbehaviourwouldcomplementyourreport.
SystemsProgramming Page15of18
COMP20179017
5 Marking and notes
This assignment will be subjected to manual marking and auto marking. The assessment has been
brokenupinto3parts,withoneexternalpartthatyouareabletoaccess.
• Part1-Automatictests8%
• Part1-Ownmerkletreetests-Manual2%
• Part2-Automatictests6%
• Part2-Ownnetworkingtests-Manual1%
• CodeStyle&Comments-Manual1%
• You are required to construct a README.md documentation to describe the organisation of
yoursoftware,wheretestdataislocatedandhowtheyarerun(300-1500words)-Manual1%
• Part1&4-Performancebenchmarkandreporting-Manual1%
Deductionsapplywhen:
• ThereexistsasignificantmismatchbetweenA3testsandsubmittedtests. Onlyinthecasewhere
the number of tests described in the A3tests report are far greater than what is being tested in
this final submission. For example, if there are 50 tests described in A3tests and only 10 are
implementedinthefinal,thiswouldbeaproblemanddeductionswouldapply.
Upto5/20A3marksmaybededucted.
• FinalgitrepositoryisUNCLEAN.
Upto2/20A3markswillbedeductedwhenthefinalgitrepositoryisunclean.
Essentially,youaresubmittingagitrepositorytoEdStem. Makesurethefinalgitrepository
(e.g.,allgit commitsofthisrepository)submittedcontainsONLYsourcefiles,headerfiles,
test files, documentation in text files. Ask on EdStem if you need to commit other files. Sug-
gestions: (1) Execute git status frequently, before each git add and git commit.
(2) Never git add . or git add -A. (3) Include a proper .gitignore file. (4) Read
previousguidesanddiscussionsonEdStem.
• Memoryerrorsandmemoryleaksoccur.
1/20 A3 marks will be deducted for EACH occurrence of memory errors or memory leaks.
This deduction will be capped at 5/20 A3 marks. Memory errors and leaks are determined by
Valgrind.
CanbedetectedwithValgrindandASAN.GuidesareavailableonEdStem. AskonEdStem
ifyoucannotfindtheguidesorneedhelp.
• Dynamic memory and shared memory are not utilised in implementations. E.g., When ONLY
fileIOisutilised,whilemmapandheapmemoryarenotused.
20/20A3marksmaybededucted.
• VLAs(Variable-lengtharray)areused. Add-Wall -Wvlatocompilationarguments.
1/20 A3 marks will be deducted for EACH VLA occurrence (VLA definition). This deduction
willbecappedat5/20A3marks.
• Thereexistsnon-Englishcomments,ornotes,presentedinanypartofthesubmission.
1/20 A3 marks will be deducted for EACH line. This deduction will be capped at 5/20 A3
marks.
• Thereexiststheuseanyexternallibraries,otherthanthoseinglibc.
20/20A3marksmaybededucted. AskonEdStembeforeusinganyexternallibraries.
Otherrestrictedfunctionsmaycomeatalaterdate.
SystemsProgramming Page16of18
COMP20179017
Academic Declaration
By submitting this assignment you declare the following: I declare that I have read and understood
the University of Sydney Student Plagiarism: Coursework Policy and Procedure, and except where
specifically acknowledged, the work contained in this assignment/project is my own work, and has
notbeencopiedfromothersourcesorbeenpreviouslysubmittedforawardorassessment.
I understand that failure to comply with the Student Plagiarism: Coursework Policy and Procedure
can lead to severe penalties as outlined under Chapter 8 of the University of Sydney By-Law 1999
(as amended). These penalties may be imposed in cases where any significant portion of my submit-
ted work has been copied without proper acknowledgement from other sources, including published
works, the Internet, existing programs, the work of other students, or work previously submitted for
otherawardsorassessments.
I realise that I may be asked to identify those portions of the work contributed by me and required to
demonstrate my knowledge of the relevant material by answering oral questions or by undertaking
supplementary work, either written or in the laboratory, in order to arrive at the final assessment
mark.
I acknowledge that the School of Computer Science, in assessing this assignment, may reproduce
it entirely, may provide a copy to another member of faculty, and/or communicate a copy of this
assignment to a plagiarism checking service or in-house computer program, and that a copy of the
assignment may be maintained by the service or the School of Computer Science for the purpose of
futureplagiarismchecking.
SystemsProgramming Page17of18
COMP20179017
Changes
• 2024-04-29
– Minortypographicalerrors
– DISCONNECTcontainednotionofnotremovingpeerfrompeerlist
– AddedoptionaloffsetparametertoFETCHcommandtohelpwithspecificity.
SystemsProgramming Page18of18
