/* libdhcp/dhcp_client.c - A DHCP client
 *
 * Copyright (C) 2024  Luke T. Shumaker <lukeshu@lukeshu.com>
 * SPDX-License-Identifier: AGPL-3.0-or-later
 *
 * -----------------------------------------------------------------------------
 * https://github.com/Wiznet/ioLibrary_Driver/blob/b981401e7f3d07015619adf44c13998e13e777f9/Internet/DHCP/dhcp.c
 *
 * Copyright (c)  2013, WIZnet Co., LTD.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <ORGANIZATION> nor the names of its
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * -----------------------------------------------------------------------------
 * https://github.com/Wiznet/ioLibrary_Driver/blob/b981401e7f3d07015619adf44c13998e13e777f9/license.txt
 *
 * Copyright (c) 2014 WIZnet Co.,Ltd.
 * Copyright (c) WIZnet ioLibrary Project.
 * All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 * SPDX-License-Identifier: MIT
 */

/* Implemented:
 *  - DHCPv4: https://datatracker.ietf.org/doc/html/rfc2131
 *  - DHCPv4 long options: https://datatracker.ietf.org/doc/html/rfc3396
 *  - DHCPv4 client identifiers in replies: https://datatracker.ietf.org/doc/html/rfc6842
 *
 * TODO:
 *  - AutoIPv4: https://datatracker.ietf.org/doc/html/rfc3927
 *  - mDNS responder: https://datatracker.ietf.org/doc/html/rfc6762
 *
 * Not implemented:
 *  - DHCPv4 node-specific client identifiers: https://datatracker.ietf.org/doc/html/rfc4361
 *  - DNAv4: https://datatracker.ietf.org/doc/html/rfc4436
 *  - LLMNR responder: https://datatracker.ietf.org/doc/html/rfc4795
 *
 * Not implemented, because the W5500 doesn't support IPv6:
 *  - SLAAC: https://datatracker.ietf.org/doc/html/rfc2462
 *  - DNAv6: https://datatracker.ietf.org/doc/html/rfc6059
 *  - DHCPv6: https://datatracker.ietf.org/doc/html/rfc8415
 */

#include <string.h> /* for strlen(), memcpy(), memset() */

#include <libmisc/rand.h>
#include <libmisc/vcall.h>
#include <libhw/generic/alarmclock.h>

#define LOG_NAME DHCP
#include <libmisc/log.h>

#include <libdhcp/client.h>

#include "dhcp_common.h"

/* Config *********************************************************************/

#include "config.h"

#ifndef CONFIG_DHCP_DEBUG
	#error config.h must define CONFIG_DHCP_DEBUG
#endif
#ifndef CONFIG_DHCP_SELECTING_NS
	#error config.h must define CONFIG_DHCP_SELECTING_NS
#endif
#ifndef CONFIG_DHCP_CAN_RECV_UNICAST_IP_WITHOUT_IP
	#error config.h must define CONFIG_DHCP_CAN_RECV_UNICAST_IP_WITHOUT_IP
#endif

/* Implementation *************************************************************/

enum requirement {
	MUST,
	MUST_NOT,
	SHOULD,
	SHOULD_NOT,
	MAY,

	_SHOULD_NOT_HAPPEN,
};

struct dhcp_client {
	/* Static.  */
	implements_net_iface            *iface;
	implements_net_packet_conn      *sock;
	struct net_eth_addr              self_eth_addr;
	char                            *self_hostname;
	size_t                           self_id_len;
	void                            *self_id_dat;

	/* Mutable.  */
	enum {
		STATE_INIT,
		STATE_SELECTING,
		STATE_REQUESTING,
		STATE_BOUND,
		STATE_RENEWING,
		STATE_REBINDING,

		STATE_INIT_REBOOT,
		STATE_REBOOTING,
	}                                state;
	uint8_t                          last_sent_msgtyp;
	uint16_t                         last_discover_secs;
	/* Lifetime of xid:
	 * 1. initial      : [INIT]->DHCPDISCOVER->DHCPOFFER->DHCPREQUEST-+->DHCPNAK-------------->[INIT]
	 *                                                                |->DHCPACK->DHCPDECLINE->[INIT]
	 *                                                                `->DHCPACK-------------->[BOUND]
	 * 2. renew/rebind : [RENEWING/REBINDING]->DHCPREQUEST-+->DHCPNAK->[INIT]
	 *                                                     `->DHCPACK->[BOUND]
	 */
	uint32_t                         xid;
	uint64_t                         time_ns_init;
	struct net_ip4_addr              lease_client_addr;  /* .yiaddr */
	struct net_ip4_addr              lease_server_id;    /* .options[DHCP_OPT_DHCP_SERVER_ID] */
	uint64_t                         lease_time_ns_t1;   /* .options[DHCP_OPT_RENEWAL_TIME] + time_ns_init */
	uint64_t                         lease_time_ns_t2;   /* .options[DHCP_OPT_REBINDING_TIME] + time_ns_init */
	uint64_t                         lease_time_ns_end;  /* .options[DHCP_OPT_ADDRESS_TIME] + time_ns_init */
	struct {
		struct net_ip4_addr              subnet_mask;  /* .options[DHCP_OPT_SUBNET_MASK] */
		struct net_ip4_addr              gateway_addr; /* .options[DHCP_OPT_ROUTER] */
	}                                lease_auxdata;

};

/**
 * For convenience in switch blocks, a list of the states that, when
 * msgtyp==DHCP_MSGTYP_REQUEST, dhcp_client_send() has assert()ed the state is
 * not.
 */
#define IMPOSSIBLE_REQUEST_STATES \
		     STATE_INIT: \
		case STATE_REQUESTING: \
		case STATE_REBINDING: \
		case STATE_REBOOTING

static inline enum requirement dhcp_table5(typeof((struct dhcp_client){}.state) state,
                               uint8_t msgtyp,
                               uint8_t opt) {
	/* Encode "Table 5: Fields and options used by DHCP clients"
	 * from
	 * https://datatracker.ietf.org/doc/html/rfc2131#page-38.  */
#define INC_ADDR ({                                                                             \
			enum requirement req;                                                   \
			switch (state) {                                                        \
			case STATE_SELECTING: case STATE_INIT_REBOOT: req = MUST;     break;    \
			case STATE_BOUND: case STATE_RENEWING:        req = MUST_NOT; break;    \
			case IMPOSSIBLE_REQUEST_STATES: default:      req = _SHOULD_NOT_HAPPEN; \
			}                                                                       \
			req;                                                                    \
		})
#define INC_SERVER ({                                                                                            \
			enum requirement req;                                                                    \
			switch (state) {                                                                         \
			case STATE_SELECTING:                                          req = MUST;     break;    \
			case STATE_INIT_REBOOT: case STATE_BOUND: case STATE_RENEWING: req = MUST_NOT; break;    \
			case IMPOSSIBLE_REQUEST_STATES: default:                       req = _SHOULD_NOT_HAPPEN; \
			}                                                                                        \
			req;                                                                                     \
		})
	struct { enum requirement cols[5]; } row;
#define ROW(...) row = (typeof(row)){{ __VA_ARGS__ }}
	switch (opt) {
	/* Option                            DISCOVER    INFORM      REQUEST     DECLINE   RELEASE  */
	/* ------                            ----------  ----------  ----------  --------  -------- */
	case DHCP_OPT_ADDRESS_REQUEST:   ROW(MAY,        MUST_NOT,   INC_ADDR,   MUST,     MUST_NOT); break;
	case DHCP_OPT_ADDRESS_TIME:      ROW(MAY,        MUST_NOT,   MAY,        MUST_NOT, MUST_NOT); break;
	case DHCP_OPT_OVERLOAD:          ROW(MAY,        MAY,        MAY,        MAY,      MAY     ); break;
	case DHCP_OPT_DHCP_MSG_TYPE:     ROW(MUST,       MUST,       MUST,       MUST,     MUST    ); break;
	case DHCP_OPT_CLIENT_ID:         ROW(MAY,        MAY,        MAY,        MAY,      MAY     ); break;
	case DHCP_OPT_CLASS_ID:          ROW(MAY,        MAY,        MAY,        MUST_NOT, MUST_NOT); break;
	case DHCP_OPT_DHCP_SERVER_ID:    ROW(MUST_NOT,   MUST_NOT,   INC_SERVER, MUST,     MUST    ); break;
	case DHCP_OPT_PARAMETER_LIST:    ROW(MAY,        MAY,        MAY,        MUST_NOT, MUST_NOT); break;
	case DHCP_OPT_DHCP_MAX_MSG_SIZE: ROW(MAY,        MAY,        MAY,        MUST_NOT, MUST_NOT); break;
	case DHCP_OPT_DHCP_MESSAGE:      ROW(SHOULD_NOT, SHOULD_NOT, SHOULD_NOT, SHOULD,   SHOULD  ); break;
	default:                         ROW(MAY,        MAY,        MAY,        MUST_NOT, MUST_NOT);
	}
#undef ROW
#undef INC_SERVER
#undef INC_ADDR
	switch (msgtyp) {
	case DHCP_MSGTYP_DISCOVER: return row.cols[0];
	case DHCP_MSGTYP_INFORM:   return row.cols[1];
	case DHCP_MSGTYP_REQUEST:  return row.cols[2];
	case DHCP_MSGTYP_DECLINE:  return row.cols[3];
	case DHCP_MSGTYP_RELEASE:  return row.cols[4];
	default:                   return _SHOULD_NOT_HAPPEN;
	}
}

/**
 * @param client->state
 * @param client->self_eth_addr
 * @param client->xid
 * @param client->time_ns_init
 * @param client->lease_client_addr (sometimes)
 * @param client->lease_server_id (sometimes)
 * @param client->sock
 *
 * @return client->last_sent_msgtyp
 * @return whether there was an error
 */
static bool dhcp_client_send(struct dhcp_client *client, uint8_t msgtyp, const char *errstr, struct dhcp_msg *scratch_msg) {
	/**********************************************************************\
	 * Preconditions                                                      *
	\**********************************************************************/

	assert(client);
	assert(msgtyp == DHCP_MSGTYP_DISCOVER ||
	       msgtyp == DHCP_MSGTYP_INFORM   ||
	       msgtyp == DHCP_MSGTYP_REQUEST  ||
	       msgtyp == DHCP_MSGTYP_DECLINE  ||
	       msgtyp == DHCP_MSGTYP_RELEASE  );
	if (msgtyp == DHCP_MSGTYP_REQUEST)
		assert(client->state == STATE_SELECTING   || /* initial selection */
		       client->state == STATE_INIT_REBOOT || /* variant initial selection */
		       client->state == STATE_BOUND       || /* T1 expired, start renew */
		       client->state == STATE_RENEWING    ); /* T2 expired, start rebind */

	/**********************************************************************\
	 * Setup                                                              *
	\**********************************************************************/

	bool server_broadcasts, client_broadcasts;

	server_broadcasts = !CONFIG_DHCP_CAN_RECV_UNICAST_IP_WITHOUT_IP;
	if (msgtyp == DHCP_MSGTYP_REQUEST &&
	    (client->state == STATE_BOUND || client->state == STATE_RENEWING))
		server_broadcasts = false;

	/* https://datatracker.ietf.org/doc/html/rfc2131#section-4.4.4 */
	switch (msgtyp) {
	case DHCP_MSGTYP_DISCOVER: client_broadcasts = true; break;
	case DHCP_MSGTYP_INFORM:   client_broadcasts = true; break; /* may unicast if it knows the server */
	case DHCP_MSGTYP_REQUEST:  client_broadcasts = client->state != STATE_BOUND; break;
	case DHCP_MSGTYP_DECLINE:  client_broadcasts = true; break;
	case DHCP_MSGTYP_RELEASE:  client_broadcasts = false; break;
	default: assert_notreached("invalid message type for client to send");
	}

	/**********************************************************************\
	 * Build the message                                                  *
	\**********************************************************************/

	*scratch_msg = (struct dhcp_msg){0};
	size_t optlen = 0;

	/* Base structure.
	 * https://datatracker.ietf.org/doc/html/rfc2131#page-37 */
	scratch_msg->op     = DHCP_OP_BOOTREQUEST;
	scratch_msg->htype  = DHCP_HTYPE_ETHERNET;
	scratch_msg->hlen   = sizeof(client->self_eth_addr);
	scratch_msg->hops   = 0; /* relays increment this when they forward it along */
	scratch_msg->xid    = uint32be_marshal(client->xid);
	scratch_msg->secs   = uint16be_marshal( ({
		uint16_t secs;
		switch (msgtyp) {
		case DHCP_MSGTYP_DISCOVER: case DHCP_MSGTYP_INFORM:
		case DHCP_MSGTYP_REQUEST:
			secs = (VCALL(bootclock, get_time_ns) - client->time_ns_init)/NS_PER_S;
			if (!secs)
				/* systemd's sd-dhcp-client.c asserts that some
				 * servers are broken and require .secs to be
				 * non-zero, even though RFC 2131 explicitly
				 * says that zero is valid.  */
				secs = 1;
			if (msgtyp == DHCP_MSGTYP_REQUEST &&
			    client->state == STATE_SELECTING)
				/* "The DHCPREQUEST message MUST use the same
				 * value in the DHCP message header's 'secs'
				 * field ... as the original DHCPDISCOVER
				 * message" -- RFC 2131
				 */
				secs = client->last_discover_secs;
			if (msgtyp == DHCP_MSGTYP_DISCOVER)
				/* Record the value to make the above
				 * possible.  */
				client->last_discover_secs = secs;
			break;
		case DHCP_MSGTYP_DECLINE: case DHCP_MSGTYP_RELEASE:
			secs = 0;
			break;
		default:
			assert_notreached("invalid message type for client to send");
		}
		secs;
	}) );
	switch (msgtyp) {
	case DHCP_MSGTYP_DISCOVER: case DHCP_MSGTYP_INFORM: case DHCP_MSGTYP_REQUEST:
		scratch_msg->flags = uint16be_marshal(server_broadcasts ? DHCP_FLAG_BROADCAST : 0);
		break;
	case DHCP_MSGTYP_DECLINE: case DHCP_MSGTYP_RELEASE:
		scratch_msg->flags = uint16be_marshal(0);
		break;
	}
	switch (msgtyp) {
	case DHCP_MSGTYP_DISCOVER: scratch_msg->ciaddr = net_ip4_addr_zero;         break;
	case DHCP_MSGTYP_INFORM:   scratch_msg->ciaddr = client->lease_client_addr; break;
	case DHCP_MSGTYP_REQUEST: switch (client->state) {
		case STATE_SELECTING: case STATE_INIT_REBOOT:
		                   scratch_msg->ciaddr = net_ip4_addr_zero;         break;
		case STATE_BOUND: case STATE_RENEWING: /* case STATE_REBINDING: */
			/* RFC 2131 includes "REBINDING" here, but a
			 * DHCPREQUEST is never sent in the REBINDING
			 * state.  */
		                   scratch_msg->ciaddr = client->lease_client_addr; break;
		case IMPOSSIBLE_REQUEST_STATES:
			assert_notreached("invalid client state for sending DHCPREQUEST");
		}                                                                   break;
	case DHCP_MSGTYP_DECLINE:  scratch_msg->ciaddr = net_ip4_addr_zero;         break;
	case DHCP_MSGTYP_RELEASE:  scratch_msg->ciaddr = client->lease_client_addr; break;
	}
	scratch_msg->yiaddr = net_ip4_addr_zero; /* only set by servers */
	scratch_msg->siaddr = net_ip4_addr_zero; /* only set by servers */
	scratch_msg->giaddr = net_ip4_addr_zero; /* only set by relays */
	memcpy(scratch_msg->chaddr, client->self_eth_addr.octets, sizeof(client->self_eth_addr));
	/* scratch_msg->sname = "options, if indicated in 'sname/file' option'; otherwise unused"; */
	/* scratch_msg->file  = "options, if indicated in 'sname/file' option'; otherwise unused"; */

	/* Magic cookie.
	 * https://datatracker.ietf.org/doc/html/rfc2131#section-4.1 */
	scratch_msg->options[optlen++] = dhcp_magic_cookie[0];
	scratch_msg->options[optlen++] = dhcp_magic_cookie[1];
	scratch_msg->options[optlen++] = dhcp_magic_cookie[2];
	scratch_msg->options[optlen++] = dhcp_magic_cookie[3];

	/* Options.  */
	for (uint8_t opt = 1; opt < 255; opt++) {
		enum requirement req = dhcp_table5(client->state, msgtyp, opt);
		switch (req) {
		case MUST_NOT:
			/* Do nothing.  */
			break;
		case MUST:
		case SHOULD:
		case SHOULD_NOT:
		case MAY:
			struct { size_t len; const void *ptr; } val;
			uint8_t _val_prl[] = {
				DHCP_OPT_SUBNET_MASK,
				DHCP_OPT_ROUTER,
				DHCP_OPT_RENEWAL_TIME,
				DHCP_OPT_REBINDING_TIME,
			};
			uint16be_t _val16 ;
#define V_RAW(len, ptr) val = (typeof(val)){ len, ptr }
#define V_OBJ(x)        V_RAW(sizeof(x), &x)
#define V_STR(x)        V_RAW(x ? strlen(x) : 0, x)
#define V_NONE()        V_RAW(0, NULL)
			switch (opt) {
			/* For clarity, list all options mentioned in "Table 5:
			 * Fields and options used by DHCP clients" from
			 * https://datatracker.ietf.org/doc/html/rfc2131#page-38,
			 * even if we don't have a value for them.  */
			case DHCP_OPT_ADDRESS_REQUEST:    V_OBJ(client->lease_client_addr); break;
			case DHCP_OPT_ADDRESS_TIME:       V_NONE(); break;
			case DHCP_OPT_OVERLOAD:           V_NONE(); break;
			case DHCP_OPT_DHCP_MSG_TYPE:      V_OBJ(msgtyp); break;
			case DHCP_OPT_CLIENT_ID:          V_RAW(client->self_id_len, client->self_id_dat); break;
			case DHCP_OPT_CLASS_ID:           V_NONE(); break;
			case DHCP_OPT_DHCP_SERVER_ID:     V_OBJ(client->lease_server_id); break;
			case DHCP_OPT_PARAMETER_LIST:     V_OBJ(_val_prl); break;
			case DHCP_OPT_DHCP_MAX_MSG_SIZE:
				if (CONFIG_DHCP_OPT_SIZE <= DHCP_MSG_MIN_MAX_OPT_SIZE)
					V_NONE();
				else {
					_val16 = uint16be_marshal(20 /* IP header */ +
					                          8  /* UDP header */ +
					                          sizeof(*scratch_msg));
					V_OBJ(_val16);
				}
				break;
			case DHCP_OPT_DHCP_MESSAGE:      V_STR(errstr); break;
			/* "Site-specific" and "All others".  */
			case DHCP_OPT_HOSTNAME:          V_STR(client->self_hostname); break;
			default:                         V_NONE();
			};
#undef V_NONE
#undef V_STR
#undef V_OBJ
#undef V_RAW
			if (req == MUST)
				assert(val.len);
			if (val.len) {
				assert(val.len <= UINT16_MAX);
				for (size_t done = 0; done < val.len;) {
					uint8_t len = val.len - done > UINT8_MAX
						? UINT8_MAX
						: val.len - done;
					scratch_msg->options[optlen++] = opt;
					scratch_msg->options[optlen++] = len;
					memcpy(&scratch_msg->options[optlen], &((char*)val.ptr)[done], len);
					optlen += len;
					done += len;
				}
			}
			break;
		case _SHOULD_NOT_HAPPEN:
			assert_notreached("bad table");
		}
	}
	scratch_msg->options[optlen++] = DHCP_OPT_END;
	assert(optlen <= CONFIG_DHCP_OPT_SIZE);

	/**********************************************************************\
	 * Send                                                               *
	\**********************************************************************/
	ssize_t r = VCALL(client->sock, sendto, scratch_msg, DHCP_MSG_BASE_SIZE + optlen,
	                  client_broadcasts ? net_ip4_addr_broadcast : client->lease_server_id, DHCP_PORT_SERVER);
	if (r < 0) {
		debugf("error: sendto: %zd", r);
		return true;
	}
	client->last_sent_msgtyp = msgtyp;
	return false;
}

struct dhcp_recv_msg {
	struct dhcp_msg         raw;
	struct {
		uint16_t                off;
		uint16_t                len;
	}                       options[0xff];
	uint8_t                 option_dat[sizeof((struct dhcp_msg){}.options)+
	                                   sizeof((struct dhcp_msg){}.file)+
	                                   sizeof((struct dhcp_msg){}.sname)];
};

/** @return whether there is an error */
static inline bool _dhcp_client_recv_measure_opts(struct dhcp_recv_msg *ret, uint8_t *optoverload, uint8_t *dat, size_t len, bool require_pad) {
	for (size_t pos = 0, opt_len; pos < len; pos += opt_len) {
		uint8_t opt_typ = dat[pos++];
		switch (opt_typ) {
		case DHCP_OPT_END:
			if (require_pad)
				while (pos < len)
					if (dat[pos++] != DHCP_OPT_PAD)
						return true;
			return false;
		case DHCP_OPT_PAD:
			opt_len = 0;
			break;
		default:
			if (pos == len)
				return true;
			opt_len = dat[pos++];
			if (pos+opt_len > len)
				return true;
			ret->options[opt_typ].len += opt_len;
			if (opt_typ == DHCP_OPT_OVERLOAD && opt_len == 1)
				*optoverload = *optoverload | dat[pos];
		}
	}
	return true;
}

static inline void _dhcp_client_recv_consolidate_opts(struct dhcp_recv_msg *ret, uint8_t *dat, size_t len) {
	for (size_t pos = 0, opt_len; pos < len; pos += opt_len) {
		uint8_t opt_typ = dat[pos++];
		switch (opt_typ) {
		case DHCP_OPT_END:
			return;
		case DHCP_OPT_PAD:
			opt_len = 0;
			break;
		default:
			opt_len = dat[pos++];
			memcpy(&ret->option_dat[ret->options[opt_typ].off+ret->options[opt_typ].len], &dat[pos], opt_len);
			ret->options[opt_typ].len += opt_len;
		}
	}
}

static inline enum requirement dhcp_table3(uint8_t req_msgtyp, uint8_t resp_msgtyp, uint8_t resp_opt) {
	/* Encode "Table 3: Fields and options used by DHCP servers"
	 * from https://datatracker.ietf.org/doc/html/rfc2131#page-29,
	 * with modifications from
	 * https://datatracker.ietf.org/doc/html/rfc6842#page-4.  */
	struct { enum requirement cols[3]; } row;
#define ROW(...) row = (typeof(row)){{ __VA_ARGS__ }}
	switch (resp_opt) {
	/*   Option                          DHCPOFFER DHCPACK     DHCPNAK  */
	/*   --------------------------      --------  ----------  -------- */
	case DHCP_OPT_ADDRESS_REQUEST:   ROW(MUST_NOT, MUST_NOT,   MUST_NOT); break;
	case DHCP_OPT_ADDRESS_TIME:      ROW(MUST,     req_msgtyp == DHCP_MSGTYP_REQUEST ? MUST : MUST_NOT,
	                                                           MUST_NOT); break;
	case DHCP_OPT_OVERLOAD:          ROW(MAY,      MAY,        MUST_NOT); break;
	case DHCP_OPT_DHCP_MSG_TYPE:     ROW(MUST,     MUST,       MUST    ); break;
	case DHCP_OPT_PARAMETER_LIST:    ROW(MUST_NOT, MUST_NOT,   MUST_NOT); break;
	case DHCP_OPT_DHCP_MESSAGE:      ROW(SHOULD,   SHOULD,     SHOULD  ); break;
	case DHCP_OPT_CLIENT_ID:         ROW(MAY,      MAY,        MAY     ); /* MUST_NOTs changed to MAY, per RFC 6842 */ break;
	case DHCP_OPT_CLASS_ID:          ROW(MAY,      MAY,        MAY     ); break;
	case DHCP_OPT_DHCP_SERVER_ID:    ROW(MUST,     MUST,       MUST    ); break;
	case DHCP_OPT_DHCP_MAX_MSG_SIZE: ROW(MUST_NOT, MUST_NOT,   MUST_NOT); break;
	default:                         ROW(MAY,      MAY,        MUST_NOT);
	}
#undef ROW
	switch (resp_msgtyp) {
	case DHCP_MSGTYP_OFFER: return row.cols[0];
	case DHCP_MSGTYP_ACK:   return row.cols[1];
	case DHCP_MSGTYP_NAK:   return row.cols[2];
	default:                return _SHOULD_NOT_HAPPEN;
	}
}

/**
 * @param client->sock
 * @param client->self_eth_addr
 * @param client->xid
 * @param client->lease_server_id
 *
 * @return
 *   - <0: -errno
 *   -  0: success
 *   - >0: should not happen
 */
static ssize_t dhcp_client_recv(struct dhcp_client *client, struct dhcp_recv_msg *ret) {
	struct net_ip4_addr srv_addr;
	uint16_t            srv_port;
	ssize_t             msg_len;

	assert(client);

 ignore:
	msg_len = VCALL(client->sock, recvfrom, &ret->raw, sizeof(ret->raw), &srv_addr, &srv_port);
	if (msg_len < 0)
		/* msg_len is -errno */
		return msg_len;

	/* Validate L3: IP  */
	/* Don't validate that srv_addr matches client->server_id
	 * because there may be a relay between us and the server, and
	 * don't bother to track the relay IP either, because it may
	 * change.  */

	/* Validate L4: UDP.  */
	if (srv_port != DHCP_PORT_SERVER)
		goto ignore;

	/* Validate L5: DHCP.  */
	if ((size_t)msg_len < DHCP_MSG_BASE_SIZE + sizeof(dhcp_magic_cookie))
		/* ignore impossibly short message */
		goto ignore;
	if ((size_t)msg_len > sizeof(ret->raw))
		/* ignore message that is larger than the specified
		 * DHCP_OPT_DHCP_MAX_MSG_SIZE */
		goto ignore;
	if (ret->raw.op != DHCP_OP_BOOTREPLY)
		/* ignore non-replies */
		goto ignore;
	if (memcmp(ret->raw.chaddr, client->self_eth_addr.octets, sizeof(client->self_eth_addr)))
		/* ignore messages that aren't to us */
		goto ignore;
	if (uint32be_unmarshal(ret->raw.xid) != client->xid)
		/* ignore messages that aren't in response to what we've said */
		goto ignore;
	if (memcmp(client->lease_server_id.octets, net_ip4_addr_zero.octets, 4))
		if (memcmp(srv_addr.octets, client->lease_server_id.octets, 4))
			/* ignore messages from the wrong server */
			goto ignore;
	if (memcmp(ret->raw.options, dhcp_magic_cookie, sizeof(dhcp_magic_cookie)))
		/* ignore messages without options */
		goto ignore;

	/* Consolidate split options into contiguous buffers.
	 *
	 * RFC 2131 and RFC 2132 specify this behavior, but are a bit
	 * ambiguous about it; RFC 3396 provides clarification.
	 *
	 * "The aggregate option buffer is made up of the optional
	 * parameters field, the file field, and the sname field, in
	 * that order." -- RFC 3396
	 */
	uint8_t optoverload = 0;
	memset(&ret->options, 0, sizeof(ret->options));
	/* Size the buffers.  */
	if (_dhcp_client_recv_measure_opts(ret, &optoverload,
	                                   &ret->raw.options[sizeof(dhcp_magic_cookie)],
	                                   msg_len - (DHCP_MSG_BASE_SIZE + sizeof(dhcp_magic_cookie)),
	                                   false))
		goto ignore;
	if (optoverload & 1u)
		if (_dhcp_client_recv_measure_opts(ret, &optoverload,
		                                   ret->raw.file, sizeof(ret->raw.file),
		                                   true))
			goto ignore;
	if (optoverload & 2u)
		if (_dhcp_client_recv_measure_opts(ret, &optoverload,
		                                   ret->raw.sname, sizeof(ret->raw.sname),
		                                   true))
			goto ignore;
	/* Validate sizes, allocate buffers.  */
	for (uint8_t opt = 1, allocated = 0; opt < 255; opt++) {
		if (!ret->options[opt].len)
			continue;
		if (!dhcp_opt_length_is_valid(opt, ret->options[opt].len))
			goto ignore;
		ret->options[opt].off = allocated;
		allocated += ret->options[opt].len;
		ret->options[opt].len = 0;
	}
	/* Fill the buffers.  */
	_dhcp_client_recv_consolidate_opts(ret,
	                                   &ret->raw.options[sizeof(dhcp_magic_cookie)],
	                                   msg_len - (DHCP_MSG_BASE_SIZE + sizeof(dhcp_magic_cookie)));
	if (optoverload & 1u)
		_dhcp_client_recv_consolidate_opts(ret, ret->raw.file, sizeof(ret->raw.file));
	if (optoverload & 2u)
		_dhcp_client_recv_consolidate_opts(ret, ret->raw.sname, sizeof(ret->raw.sname));
	/* Validate presence of options.  */
	if (!ret->options[DHCP_OPT_DHCP_MSG_TYPE].len)
		goto ignore;
	for (uint8_t opt = 1; opt < 255; opt++) {
		enum requirement req = dhcp_table3(client->last_sent_msgtyp,
		                                   ret->option_dat[ret->options[DHCP_OPT_DHCP_MSG_TYPE].off],
		                                   opt);
		switch (req) {
		case MUST:
			if (!ret->options[opt].len)
				goto ignore;
			break;
		case MUST_NOT:
			if (ret->options[opt].len)
				goto ignore;
			break;
		case SHOULD:
		case SHOULD_NOT:
		case MAY:
			/* Do nothing.  */
			break;
		case _SHOULD_NOT_HAPPEN:
			goto ignore;
		}
	}
	/* Validate values of options.  */
	if (ret->options[DHCP_OPT_CLASS_ID].len) {
		/* https://datatracker.ietf.org/doc/html/rfc6842#page-4 */
		if (ret->options[DHCP_OPT_CLASS_ID].len != client->self_id_len ||
		    memcmp(&ret->option_dat[ret->options[DHCP_OPT_CLASS_ID].off], client->self_id_dat, client->self_id_len))
			/* ignore messages that aren't to us */
			goto ignore;
	}

	return 0;
}

/** @return true if there's a conflict, false if the addr appears to be unused */
static bool dhcp_check_conflict(implements_net_packet_conn *sock, struct net_ip4_addr addr) {
	assert(sock);
	ssize_t v = VCALL(sock, sendto, "CHECK_IP_CONFLICT", 17, addr, 5000);
	return v != -NET_EARP_TIMEOUT;
}

static void dhcp_client_take_lease(struct dhcp_client *client, struct dhcp_recv_msg *msg, bool ifup) {
	assert(client);
	assert(msg);

	client->lease_client_addr = msg->raw.yiaddr;
	client->lease_auxdata.subnet_mask = msg->options[DHCP_OPT_SUBNET_MASK].len
		? *((struct net_ip4_addr *)&msg->option_dat[msg->options[DHCP_OPT_SUBNET_MASK].off])
		: net_ip4_addr_zero;
	client->lease_auxdata.gateway_addr = msg->options[DHCP_OPT_ROUTER].len
		? *((struct net_ip4_addr *)&msg->option_dat[msg->options[DHCP_OPT_SUBNET_MASK].off])
		: net_ip4_addr_zero;
	client->lease_server_id   =
		*((struct net_ip4_addr *)&msg->option_dat[msg->options[DHCP_OPT_DHCP_SERVER_ID].off]);

	uint64_t dur_ns_end =
		((uint64_t)uint32be_decode(&msg->option_dat[msg->options[DHCP_OPT_ADDRESS_TIME].off]))*NS_PER_S;
	uint64_t dur_ns_t1 = msg->options[DHCP_OPT_RENEWAL_TIME].len
		? ((uint64_t)uint32be_decode(&msg->option_dat[msg->options[DHCP_OPT_RENEWAL_TIME].off]))*NS_PER_S
		: (dur_ns_end == DHCP_INFINITY * NS_PER_S)
		  ? DHCP_INFINITY * NS_PER_S
		  : dur_ns_end/2;
	uint64_t dur_ns_t2 =  msg->options[DHCP_OPT_REBINDING_TIME].len
		? ((uint64_t)uint32be_decode(&msg->option_dat[msg->options[DHCP_OPT_RENEWAL_TIME].off]))*NS_PER_S
		: (dur_ns_end == DHCP_INFINITY * NS_PER_S)
		  ? DHCP_INFINITY * NS_PER_S
		  : (dur_ns_end*7)/8; /* 0.875 = 7/8 */

	client->lease_time_ns_t1  = (dur_ns_t1  == DHCP_INFINITY * NS_PER_S) ? 0 : client->time_ns_init + dur_ns_t1;
	client->lease_time_ns_t2  = (dur_ns_t2  == DHCP_INFINITY * NS_PER_S) ? 0 : client->time_ns_init + dur_ns_t2;
	client->lease_time_ns_end = (dur_ns_end == DHCP_INFINITY * NS_PER_S) ? 0 : client->time_ns_init + dur_ns_end;

	if (ifup)
		VCALL(client->iface, ifup, (struct net_iface_config){
				.addr         = client->lease_client_addr,
				.gateway_addr = client->lease_auxdata.gateway_addr,
				.subnet_mask  = client->lease_auxdata.subnet_mask,
			});
}

static void dhcp_client_setstate(struct dhcp_client *client,
                                 typeof((struct dhcp_client){}.state) newstate,
                                 uint8_t send_msgtyp, const char *errstr, struct dhcp_recv_msg *scratch_msg) {
	if (send_msgtyp)
		(void)dhcp_client_send(client, send_msgtyp, errstr, &scratch_msg->raw);
	client->state = newstate;
}

[[noreturn]] static void dhcp_client_run(struct dhcp_client *client, struct dhcp_recv_msg *scratch_msg) {
	assert(client);

	ssize_t r;

	/* State transition diagram: https://datatracker.ietf.org/doc/html/rfc2131#page-35 */
	for (;;) {
		switch (client->state) {
		case STATE_INIT:
			client->xid = rand_uint63n(UINT32_MAX);
			client->time_ns_init = VCALL(bootclock, get_time_ns);
			dhcp_client_setstate(client, STATE_SELECTING, DHCP_MSGTYP_DISCOVER, NULL, scratch_msg);
			break;
		case STATE_SELECTING:
			VCALL(client->sock, set_read_deadline, client->time_ns_init+CONFIG_DHCP_SELECTING_NS);
			switch ((r = dhcp_client_recv(client, scratch_msg))) {
			case 0:
				switch (scratch_msg->option_dat[scratch_msg->options[DHCP_OPT_DHCP_MSG_TYPE].off]) {
				case DHCP_MSGTYP_OFFER:
					/* Accept the first offer.  */
					dhcp_client_take_lease(client, scratch_msg, false);
					dhcp_client_setstate(client, STATE_REQUESTING, DHCP_MSGTYP_REQUEST, NULL, scratch_msg);
					break;
				default:
					/* ignore */
				}
				break;
			case -NET_ERECV_TIMEOUT:
				dhcp_client_setstate(client, STATE_INIT, 0, NULL, scratch_msg);
				break;
			default:
				assert(r < 0);
				debugf("error: recvfrom: %d", r);
			}
			break;
		case STATE_REQUESTING:
			VCALL(client->sock, set_read_deadline, 0);
			switch ((r = dhcp_client_recv(client, scratch_msg))) {
			case 0:
				switch (scratch_msg->option_dat[scratch_msg->options[DHCP_OPT_DHCP_MSG_TYPE].off]) {
				case DHCP_MSGTYP_NAK:
					dhcp_client_setstate(client, STATE_INIT, 0, NULL, scratch_msg);
					break;
				case DHCP_MSGTYP_ACK:
					if (dhcp_check_conflict(client->sock, client->lease_client_addr)) {
						dhcp_client_setstate(client, STATE_INIT, DHCP_MSGTYP_DECLINE, "IP is already in use", scratch_msg);
					} else {
						dhcp_client_take_lease(client, scratch_msg, true);
						dhcp_client_setstate(client, STATE_BOUND, 0, NULL, scratch_msg);
					}
					break;
				default:
					/* ignore */
				}
				break;
			default:
				assert(r < 0);
				debugf("error: recvfrom: %d", r);
			}
			break;
		case STATE_BOUND:
			VCALL(client->sock, set_read_deadline, client->lease_time_ns_t1);
			switch ((r = dhcp_client_recv(client, scratch_msg))) {
			case 0:
				/* discard */
				break;
			case -NET_ERECV_TIMEOUT:
				dhcp_client_setstate(client, STATE_RENEWING, DHCP_MSGTYP_REQUEST, NULL, scratch_msg);
				break;
			default:
				assert(r < 0);
				debugf("error: recvfrom: %d", r);
			}
			break;
		case STATE_RENEWING:
			client->xid = rand_uint63n(UINT32_MAX);
			client->time_ns_init = VCALL(bootclock, get_time_ns);

			VCALL(client->sock, set_read_deadline, client->lease_time_ns_t2);
			switch ((r = dhcp_client_recv(client, scratch_msg))) {
			case 0:
				switch (scratch_msg->option_dat[scratch_msg->options[DHCP_OPT_DHCP_MSG_TYPE].off]) {
				case DHCP_MSGTYP_NAK:
					VCALL(client->iface, ifdown);
					dhcp_client_setstate(client, STATE_INIT, 0, NULL, scratch_msg);
					break;
				case DHCP_MSGTYP_ACK:
					dhcp_client_take_lease(client, scratch_msg, true);
					dhcp_client_setstate(client, STATE_BOUND, 0, NULL, scratch_msg);
					break;
				default:
					/* ignore */
				}
				break;
			case -NET_ERECV_TIMEOUT:
				client->lease_server_id = net_ip4_addr_zero;
				dhcp_client_setstate(client, STATE_REBINDING, DHCP_MSGTYP_REQUEST, NULL, scratch_msg);
				break;
			default:
				assert(r < 0);
				debugf("error: recvfrom: %d", r);
			}
			break;
		case STATE_REBINDING:
			VCALL(client->sock, set_read_deadline, client->lease_time_ns_end);
			switch ((r = dhcp_client_recv(client, scratch_msg))) {
			case 0:
				switch (scratch_msg->option_dat[scratch_msg->options[DHCP_OPT_DHCP_MSG_TYPE].off]) {
				case DHCP_MSGTYP_NAK:
					VCALL(client->iface, ifdown);
					dhcp_client_setstate(client, STATE_BOUND, 0, NULL, scratch_msg);
					break;
				case DHCP_MSGTYP_ACK:
					dhcp_client_take_lease(client, scratch_msg, true);
					dhcp_client_setstate(client, STATE_BOUND, 0, NULL, scratch_msg);
					break;
				default:
					/* ignore */
				}
				break;
			case -NET_ERECV_TIMEOUT:
				VCALL(client->iface, ifdown);
				dhcp_client_setstate(client, STATE_BOUND, 0, NULL, scratch_msg);
				break;
			default:
				assert(r < 0);
				debugf("error: recvfrom: %d", r);
			}
			break;
		case STATE_INIT_REBOOT:
		case STATE_REBOOTING:
			assert_notreached("initialization with known network address is not supported");
		default:
			assert_notreached("invalid client state");
		}
	}
}

[[noreturn]] void dhcp_client_main(implements_net_iface *iface,
                                   char *self_hostname) {
	assert(iface);

	/* Even though a client ID is optional and not meaningful for
	 * us (the best we can do is to duplicate .chaddr), systemd's
	 * sd-dhcp-client.c asserts that some servers are broken and
	 * require it to be set.  */
	struct {uint8_t typ; struct net_eth_addr dat;} client_id = {
		DHCP_HTYPE_ETHERNET,
		VCALL(iface, hwaddr),
	};

	struct dhcp_client client = {
		/* Static.  */
		.iface = iface,
		.sock = VCALL(iface, udp_conn, DHCP_PORT_CLIENT),
		.self_eth_addr = VCALL(iface, hwaddr),
		.self_hostname = self_hostname,
		.self_id_len = sizeof(client_id),
		.self_id_dat = &client_id,

		/* Mutable.  */
		.state = STATE_INIT,
	};
	assert(client.sock);

	struct dhcp_recv_msg scratch;

	dhcp_client_run(&client, &scratch);
}