P3 - Subnetting and Forwarding

Week 10 · 100 points · about 8 hours · submit in Canvas

Overview

You are going to implement the lookup a router performs on every packet it sees: given a destination address and a forwarding table, find the longest prefix that matches. Along the way you will write the address arithmetic that CIDR notation hides, which is the fastest way to stop finding subnet masks mysterious.

In A4 you worked out Onyx's subnet on paper and watched ip route get pick a route. In this project you build both of those yourself, and your program prints its answers the same way.

Fork the starter repository using the Use this template button and name your copy cs425-p3.

DANGER

Your code must compile on GitHub Codespaces and Onyx. If it compiles on only one of them you will receive a zero even if it works on the other.

Learning Outcomes

• 4.1 Describe the data plane: forwarding, the IP datagram, addressing, and NAT
• 4.4 Subnet an address block with CIDR and compute the resulting ranges
• 7.1 Build code with a build system and run it under a unit test framework
• 7.2 Produce code free of memory leaks and out-of-bounds accesses

Background

An IPv4 address is just a 32-bit number. 192.168.1.10 is the four bytes 192, 168, 1 and 10, which as one number is 0xC0A8010A. Writing it as a dotted quad is only for people.

A block in CIDR notation, like 192.168.1.0/24, is an address plus a prefix length. The prefix says how many of the leading bits name the network, and the rest name a host. So a /24 has 8 host bits and 256 addresses, and its subnet mask is 24 ones followed by 8 zeros, 255.255.255.0. Everything else is bit operations on that mask:

Value	How to get it	For 132.178.227.11/25
network	addr & mask	132.178.227.0
broadcast	addr | ~mask	132.178.227.127
usable hosts	network + 1 to broadcast - 1	132.178.227.1 to 132.178.227.126, 126 hosts
contains x?	(x & mask) == (addr & mask)	.50 yes, .200 no

Those are the numbers you found for Onyx in A4. Two prefixes break the pattern. A /31 is a point to point link between two routers (RFC 3021), so both of its addresses are hosts and neither is a network or broadcast address. A /32 is a single host.

A forwarding table is a list of blocks, each with a gateway and an outgoing interface. When a datagram arrives, every block that contains its destination is a candidate, and the router picks the one with the longest prefix, because that is the most specific. The default route is 0.0.0.0/0, which contains every address and therefore loses to anything more specific. That is why it is the route of last resort. It is not a special case, it is just the shortest prefix there is.

For example, with routes for 10.0.0.0/8, 10.1.0.0/16, 10.1.2.0/24 and 10.1.2.128/25 all in the table, the address 10.1.2.200 is inside all four. The /25 wins.

The interface

The grading tests call your functions directly, so the interface is fixed. Replace the starter's src/lab.h with the one below, exactly as written, and delete the starter's get_greeting() from src/lab.c and src/main.c. Your work goes in src/lab.c, src/main.c and tests/lab-test.c.

The comment on each function is its specification, so read them all before you start. The fwd_table_t struct is yours to design in src/lab.c.

src/lab.h

#ifndef LAB_H
#define LAB_H

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

/*
 * Every address in this file is a uint32_t in host byte order, so the first
 * octet of 192.168.1.10 is the most significant byte: 0xC0A8010A.
 */

/** Room for the longest dotted quad, "255.255.255.255", and its '\0'. */
#define IP_STR_LEN 16

/** Room for the longest CIDR string, "255.255.255.255/32", and its '\0'. */
#define CIDR_STR_LEN 19

/** Room for an interface name; IFNAMSIZ on Linux, including the '\0'. */
#define DEV_NAME_LEN 16

/** An address block in CIDR notation: an address and a prefix length. */
typedef struct {
  uint32_t addr;  /**< any address in the block, host byte order */
  uint8_t prefix; /**< 0 to 32 */
} cidr_t;

/** One entry in a forwarding table. */
typedef struct {
  cidr_t dest;            /**< destination block; host bits must be zero */
  uint32_t gateway;       /**< next hop, or 0 when the block is directly connected */
  char dev[DEV_NAME_LEN]; /**< outgoing interface, for example "eth0" */
} route_t;

/** A forwarding table. Its layout is private to lab.c. */
typedef struct fwd_table fwd_table_t;

/* ------------------------------------------------------------------------
 * Task 1 - Address parsing and formatting
 * --------------------------------------------------------------------- */

/**
 * @brief Parse a dotted quad such as "192.168.1.10".
 *
 * Exactly four decimal octets from 0 to 255 separated by single periods, with
 * nothing before, between or after them. An octet with a leading zero ("010")
 * is rejected, because inet_aton() reads it as octal and that is never what a
 * person typing it meant.
 *
 * @param text The string to parse.
 * @param addr Where the address is stored on success; untouched on failure.
 * @return true if text is a valid dotted quad, false otherwise (including NULL).
 */
bool ip_parse(const char *text, uint32_t *addr);

/**
 * @brief Format an address as a dotted quad.
 * @param addr The address, host byte order.
 * @param out A buffer of at least IP_STR_LEN bytes.
 */
void ip_format(uint32_t addr, char out[IP_STR_LEN]);

/**
 * @brief Parse a block in CIDR notation such as "192.168.1.0/24".
 *
 * The address follows the rules of ip_parse() and the prefix is a decimal
 * number from 0 to 32 with no leading zero. The slash and the prefix are
 * required. Host bits may be set ("132.178.227.11/25" is an interface
 * address), so use cidr_is_network() when they must not be.
 *
 * @param text The string to parse.
 * @param block Where the block is stored on success; untouched on failure.
 * @return true if text is valid CIDR notation, false otherwise (including NULL).
 */
bool cidr_parse(const char *text, cidr_t *block);

/**
 * @brief Format a block as "a.b.c.d/p", using the address exactly as stored.
 *
 * A prefix over 32 is written as 32, the way cidr_mask() treats it.
 *
 * @param block The block.
 * @param out A buffer of at least CIDR_STR_LEN bytes.
 */
void cidr_format(cidr_t block, char out[CIDR_STR_LEN]);

/* ------------------------------------------------------------------------
 * Task 2 - Subnet arithmetic
 * --------------------------------------------------------------------- */

/**
 * @brief The subnet mask for a prefix length: /24 is 255.255.255.0.
 *
 * Careful with /0. Shifting a 32 bit value by 32 is undefined behavior in C.
 *
 * @param prefix 0 to 32; anything larger is treated as 32.
 * @return The mask, host byte order.
 */
uint32_t cidr_mask(uint8_t prefix);

/** @brief The lowest address in the block: the address with the host bits cleared. */
uint32_t cidr_network(cidr_t block);

/** @brief The highest address in the block: the address with the host bits set. */
uint32_t cidr_broadcast(cidr_t block);

/**
 * @brief The first address that can be given to a host.
 *
 * For /0 to /30 that is the network address plus one. A /31 is a point to
 * point link (RFC 3021) where both addresses are usable, and a /32 is a single
 * host, so for those two the first host is the network address.
 */
uint32_t cidr_first_host(cidr_t block);

/**
 * @brief The last address that can be given to a host.
 *
 * The broadcast address minus one for /0 to /30, and the broadcast address
 * itself for /31 and /32 (see cidr_first_host()).
 */
uint32_t cidr_last_host(cidr_t block);

/**
 * @brief How many addresses in the block can be given to hosts.
 *
 * 2^(32 - prefix) - 2 for /0 to /30, 2 for /31, and 1 for /32. For a /0 the
 * 2^32 in that formula needs 33 bits, more than a uint32_t holds, which is why
 * this returns a uint64_t.
 */
uint64_t cidr_host_count(cidr_t block);

/** @brief true if addr falls inside the block. */
bool cidr_contains(cidr_t block, uint32_t addr);

/** @brief true if the block's host bits are all zero, so it names a network. */
bool cidr_is_network(cidr_t block);

/**
 * @brief The i-th of n equally sized subnets of a block.
 *
 * Splitting a /24 into 4 gives four /26 blocks, and subnet 0 is the lowest.
 * Equal sizes are only possible when n is a power of two, and the new prefix
 * can not pass 32.
 *
 * @param block The block to split; it must be a network (cidr_is_network()).
 * @param n How many subnets, a power of two from 1 up.
 * @param i Which subnet, 0 to n - 1.
 * @param out Where the subnet is stored on success; untouched on failure.
 * @return false if out is NULL, the block is not a network, n is not a power
 *         of two, the split would need a prefix longer than 32, or i is out of
 *         range.
 */
bool cidr_subnet(cidr_t block, uint32_t n, uint32_t i, cidr_t *out);

/* ------------------------------------------------------------------------
 * Task 3 - Longest prefix match
 * --------------------------------------------------------------------- */

/**
 * @brief Parse one line of a forwarding table file.
 *
 * A line is three fields separated by spaces or tabs:
 *
 *     <destination> <gateway> <device>
 *
 * The destination is a block in CIDR notation with no host bits set, or the
 * word "default" for 0.0.0.0/0. The gateway is a dotted quad, or the word
 * "direct" for a directly connected block (stored as 0). The device is 1 to
 * DEV_NAME_LEN - 1 characters. Leading and trailing whitespace, including a
 * trailing newline, is ignored. Comments are not handled here.
 *
 * @param line The line.
 * @param route Where the route is stored on success; untouched on failure.
 * @return true if the line is a valid route, false otherwise (including NULL).
 */
bool route_parse(const char *line, route_t *route);

/**
 * @brief Create an empty forwarding table.
 * @return The table, which the caller frees with table_destroy(), or NULL if
 *         memory could not be allocated.
 */
fwd_table_t *table_create(void);

/** @brief Free a table and everything in it. NULL is allowed and does nothing. */
void table_destroy(fwd_table_t *table);

/** @brief The number of routes in the table; 0 for NULL. */
size_t table_count(const fwd_table_t *table);

/**
 * @brief Add a copy of a route to the table, growing it as needed.
 * @return false if either argument is NULL, the destination has host bits
 *         set, the table already holds a route to the same block, or memory
 *         could not be allocated. The table is unchanged on failure.
 */
bool table_add(fwd_table_t *table, const route_t *route);

/**
 * @brief Read a forwarding table file and add every route in it.
 *
 * Everything from a '#' to the end of a line is a comment, and a line that is
 * blank once the comment is removed is skipped. Every other line must be a
 * valid route (route_parse()) that table_add() accepts.
 *
 * @param table The table to add to.
 * @param in The open file to read.
 * @param bad_line If not NULL, set to the 1-based number of the first line
 *        that failed, or 0 if the arguments were NULL or the file could not
 *        be read.
 * @return true if every line loaded. On false, routes from the lines before
 *         the bad one stay in the table.
 */
bool table_load(fwd_table_t *table, FILE *in, size_t *bad_line);

/**
 * @brief Longest prefix match: the route whose block contains dest and has the
 *        longest prefix.
 *
 * A default route (0.0.0.0/0) matches everything, so it is chosen only when
 * nothing more specific does. The order the routes were added in does not
 * matter.
 *
 * @return The matching route, which stays owned by the table, or NULL if no
 *         route matches (or table is NULL).
 */
const route_t *table_lookup(const fwd_table_t *table, uint32_t dest);

#endif // LAB_H

Task 1 - Address parsing and formatting

Implement ip_parse(), ip_format(), cidr_parse() and cidr_format().

Write the parser yourself. inet_aton() is out because it accepts 010.0.0.1 and reads it as 8.0.0.1, and sscanf("%u.%u.%u.%u") is out because it happily accepts 1.2.3.4, +1.2.3.4 and 1.2.3.4junk. A parser for a router has to reject malformed input rather than guessing at it, because a guess turns into a route to the wrong place.

Every one of these must be rejected:

1.2.3        1.2.3.4.5    1..2.3       256.1.1.1    010.0.0.1
1.2.3.4x     1.2.3.4/33   1.2.3.4/024  1.2.3.4/     1.2.3/24

Task 2 - Subnet arithmetic

Implement cidr_mask(), cidr_network(), cidr_broadcast(), cidr_first_host(), cidr_last_host(), cidr_host_count(), cidr_contains(), cidr_is_network() and cidr_subnet().

Each of these is a line or two of bit operations once the mask is right, so most of the work is in the edge cases:

• cidr_mask(0) must be 0. The obvious 0xFFFFFFFF << (32 - prefix) shifts by 32 when the prefix is 0, which is undefined behavior in C. On x86 the processor only looks at the low 5 bits of the shift count, so it shifts by 0 and hands you back 0xFFFFFFFF. That bug makes the default route match only 0.0.0.0, so in practice it never matches.
• The host count of a /0 is 2^32 - 2. The answer fits in a uint32_t, but the 2^32 on the way there does not, so do that arithmetic in 64 bits.
• /31 and /32 follow the rules in the Background section, not the formula.

cidr_subnet() splits a block into n equal pieces. Equal pieces only work when n is a power of two, since splitting borrows that many bits from the host part: 4 subnets borrows 2 bits, so a /24 becomes four /26 blocks. It hands back one subnet at a time instead of filling an array, because splitting 0.0.0.0/0 into 2^31 pieces is a perfectly legal request and the array would be 16 GB.

Task 3 - Longest prefix match

Implement route_parse(), table_create(), table_destroy(), table_count(), table_add(), table_load() and table_lookup().

A forwarding table file is one route per line: the destination, the gateway, and the outgoing device. Here is the one the grading uses. Save it as tables/example.txt in your repository.

# destination      gateway          device
default            132.178.227.1    eno1
132.178.227.0/25   direct           eno1
10.0.0.0/8         10.1.0.1         eth1
10.1.0.0/16        direct           eth1
10.1.2.0/24        direct           eth2
10.1.2.128/25      10.1.2.1         eth2   # a router behind eth2
192.168.0.0/16     10.1.0.1         eth1

The first two routes are Onyx's real routing table from A4, with its interface name eno12399np0 shortened to eno1. direct means the block is on the link itself, so the packet goes straight to the destination with no gateway.

The table has to grow as routes are added, so you will need realloc(), and table_destroy() has to give all of it back. table_add() refuses a second route to the same block, which is what ip route add does, and table_load() reports the number of the first bad line so your error message can point at it.

A linear scan of the table is fine for the lookup. Make sure it does not depend on the order the routes were added in, since a lookup that returns the first match instead of the longest one passes any test whose table happens to be sorted longest first.

TIP

A real router holding the full Internet table, about a million prefixes, does not scan a list. It walks a binary trie, one bit of the address per level, so a lookup costs at most 32 steps no matter how big the table gets. A trie is welcome here if you want the challenge, but it is not required.

Task 4 - The command line

Your program is built as ./build/release/myapp and must take this command line:

Usage: myapp info <address>/<prefix>
       myapp split <network>/<prefix> <count>
       myapp lookup <table-file> <address>...

The output format is fixed because it is what is checked when your project is graded, so match it exactly. info prints what you worked out for Onyx in A4:

./build/release/myapp info 132.178.227.11/25

address    132.178.227.11
prefix     /25
netmask    255.255.255.128
network    132.178.227.0
broadcast  132.178.227.127
first host 132.178.227.1
last host  132.178.227.126
hosts      126

split prints one subnet per line, lowest first:

./build/release/myapp split 192.168.1.0/24 4

192.168.1.0/26
192.168.1.64/26
192.168.1.128/26
192.168.1.192/26

lookup loads the table and prints one line per address in the same form as ip route get: via and the gateway when there is one, then dev and the device. An address with no matching route prints unreachable.

./build/release/myapp lookup tables/example.txt 132.178.227.50 8.8.8.8 10.1.2.5 10.1.2.200

132.178.227.50 dev eno1
8.8.8.8 via 132.178.227.1 dev eno1
10.1.2.5 dev eth2
10.1.2.200 via 10.1.2.1 dev eth2

The program must:

• Exit 0 on success, 1 for a bad command line or a malformed address, 2 when the table file cannot be opened or has a bad line, and 3 when an address matches no route. If one lookup run hits more than one of these, report every address and exit with 1 if any address was malformed, otherwise 3.
• Print errors to stderr, and say what was wrong. myapp: tables/bad.txt:4: not a valid route is useful, "error" is not.
• Refuse to split a block with host bits set, or a count that is not a power of two, and exit 1, since 192.168.1.5/24 is an interface address and not a network.
• Print the usage message and exit 0 when run with no arguments at all. This is what make leak runs, so it has to be a clean, successful path.

Task 5 - Testing and coverage

Add Unity tests for every function in src/lab.h.

make check

Bit manipulation is exactly the kind of code where an off-by-one survives casual testing, so test the boundaries: /0, /31, /32, 0.0.0.0 and 255.255.255.255. Beyond those, make sure you have tests for each kind of malformed input in Task 1, a lookup where several routes match and only the longest one is right, the same table added in a different order, a table with no default route, and a table file with a bad line in the middle.

tmpfile() gives you a real FILE * to hand table_load() without leaving files lying around.

Then check your coverage:

make clean
make all
make report

Fix your tests until you have 100% coverage with everything passing. As in P0, you may only exclude branches originating from system or library calls, such as a realloc() that returns NULL.

Task 6 - Leak and crash check

• Run make leak, then make leak-test.
• Fix every leak and every crash. Watch the error paths in particular: a table file with a bad line on line 4 still has to free the three routes before it, and the line buffer from getline().

Task 7 - Replace README.md

Replace README.md following this example. Your Design section should explain how you handled /0, /31 and /32, and how your table finds the longest prefix.

Task 8 - Continuous integration

• Push everything to GitHub and confirm the CI run is green.
• Run the Create Submission Report Via GitHub Action workflow.
• Download submission-report.docx once it completes.

Submitting

1. Download submission-report.docx from GitHub and submit it to Canvas.
2. Check your submission in Canvas so you know it arrived intact.

Rubric

#	Criterion	Points
1	CIDR addresses parse and format correctly, with malformed input rejected	15
2	Network, broadcast, host range, and host count computed correctly	15
3	Block subdivision into equally sized subnets is correct	10
4	Forwarding table loads and longest prefix match returns the right entry	25
5	Boundary prefixes (/0, /31, /32) handled correctly	10
6	info, split and lookup match the required output and exit codes	10
7	100% coverage, no leaks, README.md replaced, CI green	15