Protohackers Challenge in Racket Part 1
Someone on the Racket Discord recently mentioned the Protohackers project and I figured it’d be fun to write about Racket solutions to the challenges available on the website.
0: Smoke Test
The 0th challenge is a basic echo server.
|
|
All we have to do is start a TCP listener, then accept new connections
in a loop. For every new connection, we open a thread to handle it
and a thread to close the connection and shut down the client
custodian after the handling thread is done. Wrapping every client in
a custodian ensures the handlers cannot leak resources (other threads,
ports, etc.) after they exit. We disable breaks during connection
setup so that an ill-timed break won’t leave connections in a
half-set-up state. On break (SIGINT
, SIGTERM
, or other signals),
we terminate all running handler threads and their associated
resources then close the TCP listener.
The handle
procedure reads data in up to 4096 byte chunks and writes
it back to the client. On EOF
, read-bytes
returns a special EOF
value and, in that case, we simply exit the loop.
One notable thing about this server is we have no limit on the number
of concurrent clients, so it is easy to flood. We also have no limit
on connection duration, though that would be easy to add to the
handler-supervising thread by using sync/timeout
instead of sync
.
1: Prime Time
This challenge requires us to do some JSON parsing and primality checking.
|
|
The TCP listening bits haven’t changed from the first challenge, so
I’ve elided them here. The handle
proc now reads one line at a time
from the client and attempts to parse it as a JSON value. Any parsing
error, as well as any validation error causes the handler to exit the
loop and close the connection after writing a message to the client.
Well-formed messages are validated in the first match clause and every
valid request is followed by a valid response and a newline.
Note that read-line
will happily buffer data in memory until it sees
a linefeed character, meaning an adversarial client could easily crash
this server by sending it a very long stream of non-linefeed
characters1. Also note how the error handlers are set up outside
the loop. The body of the with-handlers
form is not in tail
position, so if we’d have set up the handlers inside the loop, we’d be
creating unnecessary frames on every iteration, increasing memory
consumption.
2: Means to an End
This challenge requires us to parse a custom binary format and store a little bit of state for each client.
|
|
Just like with challenge 1, the listener bits have not changed. However, I did decide to overengineer this solution a little by using binfmt to parse the binary format. The contents of “0002.bnf” are:
|
|
The handler
proc reads 9 bytes from the client at a time and tries
to parse a Message
out of them. When it receives an insert message,
it updates the price slot for that timestamp and when it receives a
query message, it computes an average price and responds to the
client.
Like the previous challange, this server is susceptible to an attack where an adversarial client could send it enough prices to exhaust available memory and cause it to crash.
3: Budget Chat
This challenge requires us to implement a chat room.
|
|
The implementation for this challenge is more complex since it
involves keeping track of shared state and broadcasting messages to
multiple clients. I opted to make a shared thread to keep track of
user sessions. The contents of the loop inside room-thd
is a common
pattern I use when implementing stateful actors in Racket, stolen from
this paper.
The room is itself a sort of server. It receives messages via the
room-ch
where each message is expected to have a channel on which
responses can be sent, and a negative acknowledgement evt
. For
every message it receives, it updates its internal state and responds
to whatever requests it can, or removes any requests whose negative
acknowledgement event is ready for synchronization (i.e. requests that
have been abandoned ). The make-room-evt
procedure generates a
synchronizable event that sends a request to the room and receives a
response when synchronized.
The handler follows the initialization sequence by asking the client for a nickname, validating it and then entering the messaging loop. When a client joins the room, it sends its nick along with its output port to the room. The room then writes to the client’s output port whenever new information is broadcast.
This server is susceptible to the same attacks as the ones before it:
it uses read-line
to read messages and it doesn’t limit the number
of concurrent users. The former we can fix by writing a custom
read-line*
function that rejects lines longer than 1024 bytes (eg,
by using peek-bytes
) and the latter we can fix by making the room
reject join
requests when the number of users exceeds some limit.
That’s all for today. You can find these servers in full on GitHub.
-
Ryan Culpepper pointed out on the Racket Discord that we could combine
read-line
withmake-limited-input-port
in order to limit the amount of dataread-line
will buffer in memory. ↩︎