Task description

SPX (Systems Programming Exchange) is a marketplace that enables highly sought after computer components to be traded amongst seasoned computer programmers.   Traditionally, trading is in- person, however due to COVID- 19 restrictions trading must now be done remotely.

Your task is to implement a new system for SPX that allows trading to take place electronically. This consists of two parts, the exchange (handles orders) and an auto-trader (a program which trades based on predefined conditions).

You are encouraged to ask questions on Ed using the assignments category. As with any assignment, make sure that your work is your own, and you do not share your code or solutions with other students.

To complete this assignment, you should be familiar with:

• Dynamic memory allocation: malloc(), realloc(), free(), etc

• open(), read(), write() system calls

• Processes: fork(), exec(), waitpid(), etc

•  Signals: sigaction(), kill(), etc

• Named Pipes (FIFOs): mkfifo()

High Level Overview

Exchange

The purpose of the SPX is to allow trading to happen in an efficient and orderly manner. It receives orders from traders and matches them, allowing the buying and selling of computer components.

The exchange also tracks the cash balance of each trader (which starts at $0 for each trading session). For providing such trading avenue, SPX collects a 1% transaction fee on all successful orders.

IPC

The exchange communicates with trader processes using a combination of named pipes (FIFOs) and signals. All messages are followed by the delimiter ; and signal SIGUSR1.

All messages sent through FIFOs are highlighted in this document:

Traders

Traders carry out their buying and selling activities by placing orders on the exchange.

Commands

The following commands may be sent from traders to the exchange:

• BUY: An order to buy a product at or below the specified price, up to the specified quantity.

• SELL: An order to sell a product at the specified price, up to the specified quantity.

• AMEND: Update the quantity or price of an existing order, that has yet to be fully filled.

• CANCEL: Cancel an existing order, that has yet to be fully filled.

Data Types and Ranges

• ORDER_ID: integer, 0 - 999999 (incremental)

Order ID is unique per Trader (i.e. Trader 0 and 1 can both have their own Order ID 0). Order IDs are not reused (with the exception of Invalid orders, which can be fixed and re-sent with the same ID, given the next ID is not yet used).

• PRODUCT: string, alphanumeric, case sensitive, up to 16 characters

• QTY, PRICE: integer, 1 - 999999

Products

Products traded on the exchange are provided through a text file of the following structure:

Product 1

Product 2

...

Product  N

For example:

2

GPU

Motherboard

Basic Example

• Trader 0 places a SELL order for 15 CPUs at $300 each                                                          SELL  0  CPU  15  300;

• Trader 1 places a BUY order for 10 CPUs at $300 each                                                            BUY  0  CPU  10  300;

•  SPX matches these orders, Trader 1 buys 10 CPUs from Trader 0 for $3,000 and pays $30 transaction fee.

• Trader 1’s order is now fulfilled. Trader 0 has 5 CPUs remaining on the market for sale.

Implementation details

Write programs in C that implement SPX as shown in the examples.

You are guaranteed not to have NULL returned from malloc() or realloc() in this context.

Your submission must be contained in the following files and produce no errors when built and run on Ed C compiler.

• spx_common .h: Common constants and structures

• spx_exchange .c, spx_exchange .h: Part 1 (Exchange, compiles to spx_exchange)

• spx_trader .c, spx_trader .h: Part 2 (Trader, compiles to spx_trader)

• Test cases in tests directory

• README .md: Code Description

Read / write with FIFOs and/or write to stdout as instructed.

Your program output must match the exact output format shown in the examples and on Ed. You are encouraged to submit your assignment while you are working on it, so you can obtain feedback.

You may modify any of the existing scaffold files, or make your own.

No external code outside the standard C library functions should be required.

In order to obtain full marks, your program must free all of the dynamic memory it allocates.

Exchange: Start Up

The exchange accepts command line arguments as follows:

. /spx_exchange   [product  file]   [trader  0 ]   [trader  1 ]   ...   [trader  n]    The following example uses a product file named products.txt and trader binaries trader_a and trader_b: . /spx_exchange  products .txt   . /trader_a   . /trader_b

Upon start up, the exchange should read the product file to find out about what it will trade. It should then create two named pipes for each trader:

/tmp/spx_exchange_

/tmp/spx_trader_

The spx_exchange_* named pipes are for the exchange write to each trader and spx_trader_* named pipes are for each trader to write to the exchange.

After both pipes are created for a trader, the exchange shall launch that trader binary as a new child process, assigning it a trader ID starting from 0, in the Command Line Argument order. The trader

ID shall be passed to the trader binary as a command line argument.

For the example above, the trader binaries should be launched like so:

. /trader_a  0

. /trader_b  1

Upon launching each binary, the exchange and trader should attempt to connect to both named pipes.

After all binaries are launched and pipes are connected, the exchange should send each trader (lowest trader IDs first) the following message using the spx_exchange_* named pipes; afterwards, notify each trader using the SIGUSR1 signal.

Exchange: Placing Orders

Traders may place orders with the exchange by sending the appropriate commands through their spx_trader_ named pipe. Once the whole command is written to the pipe, it shall notify the exchange with the SIGUSR1 signal.

Once the exchange receives the SIGUSR1 signal from a trader, it would read the command from the spx_trader_ named pipe and process the order appropriately. Depending on whether the order was accepted (for new buy / sell orders), amended or cancelled, or if the command is invalid, it would write one of the following messages to the spx_exchange_ named pipe and notify the trader using the SIGUSR1 signal.

The exchange should also message all other traders (lowest trader IDs first) using the spx_exchange_* named pipes, and notify them using the SIGUSR1 signal, with the following message:

N.B.: In case of a cancelled order, QTY = 0 and PRICE = 0.

Sample order flow

1. Trader 0 writes to spx_trader_0:

2. Trader 0 sends SIGUSR1 signal to the Exchange

3. Exchange reads spx_trader_0 and adds the order to the order book

4. Exchange writes to spx_exchange_0:

ACCEPTED  20;

5. Exchange sends SIGUSR1 signal to Trader 0

6. Exchange writes to all other spx_exchange_* pipes:                                                                 MARKET  SELL  CPU  2  300;

7. Exchange sends SIGUSR1 signal to all other Traders.

8. All traders can read their own spx_exchange_* and places further orders if desired

Exchange: Matching Orders

The exchange should attempt to match orders once there is at least one BUY and one SELL order for any particular product. Orders match if the price of the BUY order is larger than or equal to the price of the SELL order. The matching price is the price of the older order. Of the two matched traders, the exchange charges 1% transaction fee to the trader who placed the order last, rounded to the nearest dollar (eg: $4.50 -> $5.00).

When there are multiple orders in the exchange, order matching should follow price-time priority:

• Match the highest-priced BUY order against lowest-priced SELL order

• If there are multiple orders at the same price level, match the earliest order first

As the order matches, the exchange shall write the following message to the appropriate spx_exchange_* pipes belonging to the matched traders, then send the SIGUSR1 signal:

It is possible for a single order with sufficient quantity to match against multiple existing orders in the market. Similarly, an order could be partially filled and remain in the market if there isn’t sufficient quantity available. Orders are removed from the market once their quantity reaches zero.

Example Scenarios

Exchange: Reporting

In addition to reading and writing to the named pipes, the exchange also needs to print a range of messages to standard out (stdout), as per the examples later in this document.  Please follow the examples for the outputs required.

Specifically, the order book and trader positions need to be printed after each successful order, for example:

[SPX]

[SPX]

[SPX]

[SPX]

[SPX]

[SPX]     

[SPX]

[SPX]     

Product:  GPU;  Buy  levels:  3;  Sell  levels: 1

SELL   99  @  $511   (1  order)

BUY  30  @  $502   (1  order)

BUY   60  @  $501   (2  orders)

BUY  30  @  $500   (1  order)

for  further  products>

--POSITIONS--

Trader  0:  GPU  0   ($0),  Router  0   ($0)

for  further  traders>

Here, all orders in the market are sorted from the highest to lowest price. Each unique price is called a level, and there may be multiple orders in the same level. Positions refer to the quantity of products

owned (or owed) by each trader, which may be positive or negative after each order. Note: Tabs (\t) are used for indentation.

Exchange: Teardown

As soon as a trader disconnects (closing their end of the pipes or process exits), your exchange should print out the following message:

[SPX]  Trader    disconnected

It shall reject any pending or further orders from the trader but keep existing orders in the orderbook (if any).

After all traders disconnect, the exchange should print out the following message:

[SPX]  Trading  completed

[SPX]  Exchange  fees  collected:  $

Make sure to clean up any remaining child processes, close and delete FIFOs, and free memory before exiting.

Auto-Trader

The second part of this assignment is to implement an auto-trader in spx_trader .c and spx_trader .h.

The logic of the auto-trader is very simple: as soon as a SELL order is available in the exchange, it will place an opposite BUY order to attempt to buy the item.

As an example, as soon as the auto-trader receives the following message (and signal) from the ex- change:

It would place the following order:

The auto-trader should gracefully disconnect and shut down if there is a BUY order with quantity greater than or equal to 1000.

You may assume that for the purposes of this auto-trader, there are no other competing traders placing

BUY orders.

However, signals are inherently unreliable, that is, multiple signals (perhaps from multiple auto- traders) may overwrite one another and cause a race condition.

You should design your auto-trader in such way that it is fault-tolerant, while conforming to the Exchange messaging protocol (first write to the pipe, then signal SIGUSR1), and does not place unreasonable load on the exchange.

Code Description

To support your implementation, you need to provide a succinct answer to each of the questions in the file README .md. The word limit is 150 for each question.

1. Describe how your exchange works, using diagram(s) if necessary.

2. Describe your design decisions for the trader and how it’s fault-tolerant and efficient.

3. Describe your tests and how to run them.

Exchange: Example Outputs

#  cat  products .txt

2

GPU

Router

1 trader, 1 order

Command:

. /spx_exchange  products .txt   . /trader_a

Orders:

Trader  0:  BUY  0  GPU  30  500

Standard out:

[SPX]  Starting

[SPX]  Trading  2  products:  GPU  Router

[SPX]  Created  FIFO  /tmp/spx_exchange_ 0

[SPX]  Created  FIFO  /tmp/spx_trader_ 0

[SPX]  Starting  trader  0   ( . /trader_a)

[SPX]  Connected  to  /tmp/spx_exchange_ 0

[SPX]  Connected  to  /tmp/spx_trader_ 0

[SPX]   [T0]  Parsing  command:  

[SPX]       --ORDERBOOK--

[SPX]       Product:  GPU;  Buy  levels:  1;  Sell  levels:  0

[SPX]                           BUY  30  @  $500   (1  order)

[SPX]       Product:  Router;  Buy  levels:  0;  Sell  levels:  0 [SPX]       --POSITIONS--

[SPX]       Trader  0:  GPU  0   ($0),  Router  0   ($0)

[SPX]  Trader  0  disconnected

[SPX]  Trading  completed

[SPX]  Exchange  fees  collected:  $0

2 traders, 6 orders

Command:

. /spx_exchange  products .txt   . /trader_a   . /trader_b

Orders:

Trader  0:  BUY  0  GPU  30  500

Trader  0:  BUY  1  GPU  30  501

Trader  0:  BUY  2  GPU  30  501

Trader  0:  BUY  3  GPU  30  502

Trader  1:  SELL  0  GPU   99  511

Trader  1:  SELL  1  GPU   99  402

Standard out:

[SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX]

Starting

Trading  2  products:  GPU  Router

Created  FIFO  /tmp/spx_exchange_ 0

Created  FIFO  /tmp/spx_trader_ 0

Starting  trader  0   ( . /trader_a)

Connected  to  /tmp/spx_exchange_ 0

Connected  to  /tmp/spx_trader_ 0

Created  FIFO  /tmp/spx_exchange_ 1

Created  FIFO  /tmp/spx_trader_ 1

Starting  trader  1   ( . /trader_b)

Connected  to  /tmp/spx_exchange_ 1

Connected  to  /tmp/spx_trader_ 1

ORDERBOOK--

Product:  GPU;  Buy  levels:  1;  Sell  levels: 0

BUY  30  @  $500   (1  order)

Product:  Router;  Buy  levels:  0;  Sell  levels:  0

--POSITIONS--

Trader  0:  GPU  0   ($0),  Router  0   ($0)

Trader  1:  GPU  0   ($0),  Router  0   ($0)

[T0]  Parsing  command:  

Product:  GPU;  Buy  levels:  2;  Sell  levels: 0

BUY  30  @  $501   (1  order)

BUY  30  @  $500   (1  order)

Product:  Router;  Buy  levels:  0;  Sell  levels:  0

--POSITIONS--

Trader  0:  GPU  0   ($0),  Router  0   ($0)

Trader  1:  GPU  0   ($0),  Router  0   ($0)

[T0]  Parsing  command:  

Product:  GPU;  Buy  levels:  2;  Sell  levels: 0

BUY   60  @  $501   (2  orders)

BUY  30  @  $500   (1  order)

Product:  Router;  Buy  levels:  0;  Sell  levels:  0

--POSITIONS--

Trader  0:  GPU  0   ($0),  Router  0   ($0)

Trader  1:  GPU  0   ($0),  Router  0   ($0)

[SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX] [SPX]

ORDERBOOK--

Product:  GPU;  Buy  levels:  3;  Sell  levels: 0

BUY  30  @  $502   (1  order)

BUY   60  @  $501   (2  orders)

BUY  30  @  $500   (1  order)

Product:  Router;  Buy  levels:  0;  Sell  levels:  0

--POSITIONS--

Trader  0:  GPU  0   ($0),  Router  0   ($0)

Trader  1:  GPU  0   ($0),  Router  0   ($0)

[T1]  Parsing  command:  

Product:  GPU;  Buy  levels:  3;  Sell  levels: 1

SELL   99  @  $511   (1  order)

BUY  30  @  $502   (1  order)

BUY   60  @  $501   (2  orders)

BUY  30  @  $500   (1  order)

Product:  Router;  Buy  levels:  0;  Sell  levels:  0

--POSITIONS--

Trader  0:  GPU  0   ($0),  Router  0   ($0)

Trader  1:  GPU  0   ($0),  Router  0   ($0)

[T1]  Parsing  command:  

Match:  Order  3   [T0],  New  Order  1   [T1],  value:  $15060,  fee:  $151 . Match:  Order  1   [T0],  New  Order  1   [T1],  value:  $15030,  fee:  $150 . Match:  Order  2   [T0],  New  Order  1   [T1],  value:  $15030,  fee:  $150 . Match:  Order  0   [T0],  New  Order  1   [T1],  value:  $4500,  fee:  $45 .

Product:  GPU;  Buy  levels:  1;  Sell  levels: 1

SELL   99  @  $511   (1  order)

BUY  21  @  $500   (1  order)

Product:  Router;  Buy  levels:  0;  Sell  levels:  0

--POSITIONS--

Trader  0:  GPU   99   ($- 49620),  Router  0   ($0)

Trader  1:  GPU  - 99   ($49124),  Router  0   ($0)

Trader  0  disconnected

Trader  1  disconnected

Trading  completed

Exchange  fees  collected:  $496

Submission details

You are encouraged to submit multiple times, but only your last submission will be marked.

Writing your own test cases

We have provided you with some test cases but these do not test all the functionality described in the assignment.  It is important that you thoroughly test your code by writing your own test cases, including both end-to-end (input / output) tests and unit tests using cmocka.

You should place all of your end-to-end test cases in the tests/E2E directory. Ensure that each test case has a .out output file and optionally an .in file. We recommend that the names of your test cases are descriptive so that you know what each is testing, e.g. buy-order.out and amend-order.out.

You should place all of your unit tests in the tests directory, under unit-tests .c (and more files, if necessary). All unit tests must be constructed with the cmocka unit testing framework.

You should have a brief description of your tests, and how they can be run, in README .md.

Error handling

Your code should have appropriate mechanisms in place to detect and handle errors, including but not limited to:

• NULL pointers

• Buffer overflows and underflows

• Unable to open FIFOs

• Unable to launch child processes

• Invalid or malformed commands

Oral examination

You will need to answer questions from a COMP2017 teaching staff member regarding your imple- mentation. You will be required to attend a Zoom session with COMP2017 teaching staff member after the code submission deadline. A reasonable attempt will need to be made, otherwise you will

receive zero for the assessment.

In this session, you will be asked:

• General questions about your understanding of the concepts needed for this assignment,

• How you have arranged your memory, data structures and types

• How you managed IPC (Inter Process Communication)