[dns] Support DNS search lists

Update the DNS resolver to support DNS search lists (as provided by
DHCP option 119, DHCPv6 option 24, or NDP option 31).

Add validation code to ensure that parsing of DNS packets does not
overrun the input, get stuck in infinite loops, or (worse) write
beyond the end of allocated buffers.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

3 files changed, 713 insertions, 265 deletions

diff --git a/src/net/udp/dhcp.c b/src/net/udp/dhcp.c
index 4625d1de..e6d3eddf 100644
--- a/src/net/udp/dhcp.c
+++ b/src/net/udp/dhcp.c
@@ -86,6 +86,7 @@ static uint8_t dhcp_request_options_data[] = {
 		      DHCP_LOG_SERVERS, DHCP_HOST_NAME, DHCP_DOMAIN_NAME,
 		      DHCP_ROOT_PATH, DHCP_VENDOR_ENCAP, DHCP_VENDOR_CLASS_ID,
 		      DHCP_TFTP_SERVER_NAME, DHCP_BOOTFILE_NAME,
+		      DHCP_DOMAIN_SEARCH,
 		      128, 129, 130, 131, 132, 133, 134, 135, /* for PXE */
 		      DHCP_EB_ENCAP, DHCP_ISCSI_INITIATOR_IQN ),
 	DHCP_END
diff --git a/src/net/udp/dhcpv6.c b/src/net/udp/dhcpv6.c
index b86b8337..cbc8d794 100644
--- a/src/net/udp/dhcpv6.c
+++ b/src/net/udp/dhcpv6.c
@@ -979,3 +979,12 @@ const struct setting filename6_setting __setting ( SETTING_BOOT, filename ) = {
 	.type = &setting_type_string,
 	.scope = &ipv6_scope,
 };
+
+/** DNS search list setting */
+const struct setting dnssl6_setting __setting ( SETTING_IP_EXTRA, dnssl ) = {
+	.name = "dnssl",
+	.description = "DNS search list",
+	.tag = DHCPV6_DOMAIN_LIST,
+	.type = &setting_type_dnssl,
+	.scope = &ipv6_scope,
+};
diff --git a/src/net/udp/dns.c b/src/net/udp/dns.c
index a93eb916..73af943d 100644
--- a/src/net/udp/dns.c
+++ b/src/net/udp/dns.c
@@ -26,6 +26,7 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
+#include <ctype.h>
 #include <errno.h>
 #include <byteswap.h>
 #include <ipxe/refcnt.h>
@@ -69,8 +70,366 @@ static union {
 	},
 };
 
-/** The local domain */
-static char *localdomain;
+/** The DNS search list */
+static struct dns_name dns_search;
+
+/**
+ * Encode a DNS name using RFC1035 encoding
+ *
+ * @v string		DNS name as a string
+ * @v name		DNS name to fill in
+ * @ret len		Length of DNS name, or negative error
+ */
+int dns_encode ( const char *string, struct dns_name *name ) {
+	uint8_t *start = ( name->data + name->offset );
+	uint8_t *end = ( name->data + name->len );
+	uint8_t *dst = start;
+	size_t len = 0;
+	char c;
+
+	/* Encode name */
+	while ( ( c = *(string++) ) ) {
+
+		/* Handle '.' separators */
+		if ( c == '.' ) {
+
+			/* Reject consecutive '.' */
+			if ( ( len == 0 ) && ( dst != start ) )
+				return -EINVAL;
+
+			/* Terminate if this is the trailing '.' */
+			if ( *string == '\0' )
+				break;
+
+			/* Reject initial non-terminating '.' */
+			if ( len == 0 )
+				return -EINVAL;
+
+			/* Reset length */
+			len = 0;
+
+		} else {
+
+			/* Increment length */
+			len++;
+
+			/* Check for overflow */
+			if ( len > DNS_MAX_LABEL_LEN )
+				return -EINVAL;
+		}
+
+		/* Copy byte, update length */
+		if ( ++dst < end ) {
+			*dst = c;
+			dst[-len] = len;
+		}
+	}
+
+	/* Add terminating root marker */
+	if ( len )
+		dst++;
+	if ( dst < end )
+		*dst = '\0';
+	dst++;
+
+	return ( dst - start );
+}
+
+/**
+ * Find start of valid label within an RFC1035-encoded DNS name
+ *
+ * @v name		DNS name
+ * @v offset		Current offset
+ * @ret offset		Offset of label, or negative error
+ */
+static int dns_label ( struct dns_name *name, size_t offset ) {
+	const uint8_t *byte;
+	const uint16_t *word;
+	size_t len;
+	size_t ptr;
+
+	while ( 1 ) {
+
+		/* Fail if we have overrun the DNS name */
+		if ( ( offset + sizeof ( *byte) ) > name->len )
+			return -EINVAL;
+		byte = ( name->data + offset );
+
+		/* Follow compression pointer, if applicable */
+		if ( DNS_IS_COMPRESSED ( *byte ) ) {
+
+			/* Fail if we have overrun the DNS name */
+			if ( ( offset + sizeof ( *word ) ) > name->len )
+				return -EINVAL;
+			word = ( name->data + offset );
+
+			/* Extract pointer to new offset */
+			ptr = DNS_COMPRESSED_OFFSET ( ntohs ( *word ) );
+
+			/* Fail if pointer does not point backwards.
+			 * (This guarantees termination of the
+			 * function.)
+			 */
+			if ( ptr >= offset )
+				return -EINVAL;
+
+			/* Continue from new offset */
+			offset = ptr;
+			continue;
+		}
+
+		/* Fail if we have overrun the DNS name */
+		len = *byte;
+		if ( ( offset + sizeof ( *byte ) + len ) > name->len )
+			return -EINVAL;
+
+		/* We have a valid label */
+		return offset;
+	}
+}
+
+/**
+ * Decode RFC1035-encoded DNS name
+ *
+ * @v name		DNS name
+ * @v data		Output buffer
+ * @v len		Length of output buffer
+ * @ret len		Length of decoded DNS name, or negative error
+ */
+int dns_decode ( struct dns_name *name, char *data, size_t len ) {
+	unsigned int recursion_limit = name->len; /* Generous upper bound */
+	int offset = name->offset;
+	const uint8_t *label;
+	size_t decoded_len = 0;
+	size_t label_len;
+	size_t copy_len;
+
+	while ( recursion_limit-- ) {
+
+		/* Find valid DNS label */
+		offset = dns_label ( name, offset );
+		if ( offset < 0 )
+			return offset;
+
+		/* Terminate if we have reached the root */
+		label = ( name->data + offset );
+		label_len = *(label++);
+		if ( label_len == 0 ) {
+			if ( decoded_len < len )
+				*data = '\0';
+			return decoded_len;
+		}
+
+		/* Prepend '.' if applicable */
+		if ( decoded_len && ( decoded_len++ < len ) )
+			*(data++) = '.';
+
+		/* Copy label to output buffer */
+		copy_len = ( ( decoded_len < len ) ? ( len - decoded_len ) : 0);
+		if ( copy_len > label_len )
+			copy_len = label_len;
+		memcpy ( data, label, copy_len );
+		data += copy_len;
+		decoded_len += label_len;
+
+		/* Move to next label */
+		offset += ( sizeof ( *label ) + label_len );
+	}
+
+	/* Recursion limit exceeded */
+	return -EINVAL;
+}
+
+/**
+ * Compare DNS names for equality
+ *
+ * @v first		First DNS name
+ * @v second		Second DNS name
+ * @ret rc		Return status code
+ */
+int dns_compare ( struct dns_name *first, struct dns_name *second ) {
+	unsigned int recursion_limit = first->len; /* Generous upper bound */
+	int first_offset = first->offset;
+	int second_offset = second->offset;
+	const uint8_t *first_label;
+	const uint8_t *second_label;
+	size_t label_len;
+	size_t len;
+
+	while ( recursion_limit-- ) {
+
+		/* Find valid DNS labels */
+		first_offset = dns_label ( first, first_offset );
+		if ( first_offset < 0 )
+			return first_offset;
+		second_offset = dns_label ( second, second_offset );
+		if ( second_offset < 0 )
+			return second_offset;
+
+		/* Compare label lengths */
+		first_label = ( first->data + first_offset );
+		second_label = ( second->data + second_offset );
+		label_len = *(first_label++);
+		if ( label_len != *(second_label++) )
+			return -ENOENT;
+		len = ( sizeof ( *first_label ) + label_len );
+
+		/* Terminate if we have reached the root */
+		if ( label_len == 0 )
+			return 0;
+
+		/* Compare label contents (case-insensitively) */
+		while ( label_len-- ) {
+			if ( tolower ( *(first_label++) ) !=
+			     tolower ( *(second_label++) ) )
+				return -ENOENT;
+		}
+
+		/* Move to next labels */
+		first_offset += len;
+		second_offset += len;
+	}
+
+	/* Recursion limit exceeded */
+	return -EINVAL;
+}
+
+/**
+ * Copy a DNS name
+ *
+ * @v src		Source DNS name
+ * @v dst		Destination DNS name
+ * @ret len		Length of copied DNS name, or negative error
+ */
+int dns_copy ( struct dns_name *src, struct dns_name *dst ) {
+	unsigned int recursion_limit = src->len; /* Generous upper bound */
+	int src_offset = src->offset;
+	size_t dst_offset = dst->offset;
+	const uint8_t *label;
+	size_t label_len;
+	size_t copy_len;
+	size_t len;
+
+	while ( recursion_limit-- ) {
+
+		/* Find valid DNS label */
+		src_offset = dns_label ( src, src_offset );
+		if ( src_offset < 0 )
+			return src_offset;
+
+		/* Copy as an uncompressed label */
+		label = ( src->data + src_offset );
+		label_len = *label;
+		len = ( sizeof ( *label ) + label_len );
+		copy_len = ( ( dst_offset < dst->len ) ?
+			     ( dst->len - dst_offset ) : 0 );
+		if ( copy_len > len )
+			copy_len = len;
+		memcpy ( ( dst->data + dst_offset ), label, copy_len );
+		src_offset += len;
+		dst_offset += len;
+
+		/* Terminate if we have reached the root */
+		if ( label_len == 0 )
+			return ( dst_offset - dst->offset );
+	}
+
+	/* Recursion limit exceeded */
+	return -EINVAL;
+}
+
+/**
+ * Skip RFC1035-encoded DNS name
+ *
+ * @v name		DNS name
+ * @ret offset		Offset to next name, or negative error
+ */
+int dns_skip ( struct dns_name *name ) {
+	unsigned int recursion_limit = name->len; /* Generous upper bound */
+	int offset = name->offset;
+	int prev_offset;
+	const uint8_t *label;
+	size_t label_len;
+
+	while ( recursion_limit-- ) {
+
+		/* Find valid DNS label */
+		prev_offset = offset;
+		offset = dns_label ( name, prev_offset );
+		if ( offset < 0 )
+			return offset;
+
+		/* Terminate if we have reached a compression pointer */
+		if ( offset != prev_offset )
+			return ( prev_offset + sizeof ( uint16_t ) );
+
+		/* Skip this label */
+		label = ( name->data + offset );
+		label_len = *label;
+		offset += ( sizeof ( *label ) + label_len );
+
+		/* Terminate if we have reached the root */
+		if ( label_len == 0 )
+			return offset;
+	}
+
+	/* Recursion limit exceeded */
+	return -EINVAL;
+}
+
+/**
+ * Skip RFC1035-encoded DNS name in search list
+ *
+ * @v name		DNS name
+ * @ret offset		Offset to next non-empty name, or negative error
+ */
+static int dns_skip_search ( struct dns_name *name ) {
+	int offset;
+
+	/* Find next name */
+	offset = dns_skip ( name );
+	if ( offset < 0 )
+		return offset;
+
+	/* Skip over any subsequent empty names (e.g. due to padding
+	 * bytes used in the NDP DNSSL option).
+	 */
+	while ( ( offset < ( ( int ) name->len ) ) &&
+		( *( ( uint8_t * ) ( name->data + offset ) ) == 0 ) ) {
+		offset++;
+	}
+
+	return offset;
+}
+
+/**
+ * Transcribe DNS name (for debugging)
+ *
+ * @v name		DNS name
+ * @ret string		Transcribed DNS name
+ */
+static const char * dns_name ( struct dns_name *name ) {
+	static char buf[256];
+	int len;
+
+	len = dns_decode ( name, buf, sizeof ( buf ) );
+	return ( ( len < 0 ) ? "<INVALID>" : buf );
+}
+
+/**
+ * Name a DNS query type (for debugging)
+ *
+ * @v type		Query type (in network byte order)
+ * @ret name		Type name
+ */
+static const char * dns_type ( uint16_t type ) {
+	switch ( type ) {
+	case htons ( DNS_TYPE_A ):	return "A";
+	case htons ( DNS_TYPE_AAAA ):	return "AAAA";
+	case htons ( DNS_TYPE_CNAME ):	return "CNAME";
+	default:			return "<UNKNOWN>";
+	}
+}
 
 /** A DNS request */
 struct dns_request {
@@ -91,14 +450,25 @@ struct dns_request {
 	} address;
 	/** Initial query type */
 	uint16_t qtype;
-	/** Current query packet */
-	struct dns_query query;
-	/** Location of query info structure within current packet
-	 *
-	 * The query info structure is located immediately after the
-	 * compressed name.
-	 */
-	struct dns_query_info *qinfo;
+	/** Buffer for current query */
+	struct {
+		/** Query header */
+		struct dns_header query;
+		/** Name buffer */
+		char name[DNS_MAX_NAME_LEN];
+		/** Space for question */
+		struct dns_question padding;
+	} __attribute__ (( packed )) buf;
+	/** Current query name */
+	struct dns_name name;
+	/** Question within current query */
+	struct dns_question *question;
+	/** Length of current query */
+	size_t len;
+	/** Offset of search suffix within current query */
+	size_t offset;
+	/** Search list */
+	struct dns_name search;
 	/** Recursion counter */
 	unsigned int recursion;
 };
@@ -138,214 +508,73 @@ static void dns_resolved ( struct dns_request *dns ) {
 }
 
 /**
- * Compare DNS reply name against the query name from the original request
- *
- * @v dns		DNS request
- * @v reply		DNS reply
- * @v rname		Reply name
- * @ret	zero		Names match
- * @ret non-zero	Names do not match
- */
-static int dns_name_cmp ( struct dns_request *dns,
-			  const struct dns_header *reply, 
-			  const char *rname ) {
-	const char *qname = dns->query.payload;
-	int i;
-
-	while ( 1 ) {
-		/* Obtain next section of rname */
-		while ( ( *rname ) & 0xc0 ) {
-			rname = ( ( ( char * ) reply ) +
-				  ( ntohs( *((uint16_t *)rname) ) & ~0xc000 ));
-		}
-		/* Check that lengths match */
-		if ( *rname != *qname )
-			return -1;
-		/* If length is zero, we have reached the end */
-		if ( ! *qname )
-			return 0;
-		/* Check that data matches */
-		for ( i = *qname + 1; i > 0 ; i-- ) {
-			if ( *(rname++) != *(qname++) )
-				return -1;
-		}
-	}
-}
-
-/**
- * Skip over a (possibly compressed) DNS name
- *
- * @v name		DNS name
- * @ret name		Next DNS name
- */
-static const char * dns_skip_name ( const char *name ) {
-	while ( 1 ) {
-		if ( ! *name ) {
-			/* End of name */
-			return ( name + 1);
-		}
-		if ( *name & 0xc0 ) {
-			/* Start of a compressed name */
-			return ( name + 2 );
-		}
-		/* Uncompressed name portion */
-		name += *name + 1;
-	}
-}
-
-/**
- * Find an RR in a reply packet corresponding to our query
+ * Construct DNS question
  *
  * @v dns		DNS request
- * @v reply		DNS reply
- * @ret rr		DNS RR, or NULL if not found
+ * @ret rc		Return status code
  */
-static union dns_rr_info * dns_find_rr ( struct dns_request *dns,
-					 const struct dns_header *reply ) {
-	int i, cmp;
-	const char *p = ( ( char * ) reply ) + sizeof ( struct dns_header );
-	union dns_rr_info *rr_info;
-
-	/* Skip over the questions section */
-	for ( i = ntohs ( reply->qdcount ) ; i > 0 ; i-- ) {
-		p = dns_skip_name ( p ) + sizeof ( struct dns_query_info );
-	}
+static int dns_question ( struct dns_request *dns ) {
+	static struct dns_name search_root = {
+		.data = "",
+		.len = 1,
+	};
+	struct dns_name *search = &dns->search;
+	int len;
+	size_t offset;
+
+	/* Use root suffix if search list is empty */
+	if ( search->offset == search->len )
+		search = &search_root;
+
+	/* Overwrite current suffix */
+	dns->name.offset = dns->offset;
+	len = dns_copy ( search, &dns->name );
+	if ( len < 0 )
+		return len;
 
-	/* Process the answers section */
-	for ( i = ntohs ( reply->ancount ) ; i > 0 ; i-- ) {
-		cmp = dns_name_cmp ( dns, reply, p );
-		p = dns_skip_name ( p );
-		rr_info = ( ( union dns_rr_info * ) p );
-		if ( cmp == 0 )
-			return rr_info;
-		p += ( sizeof ( rr_info->common ) +
-		       ntohs ( rr_info->common.rdlength ) );
+	/* Sanity check */
+	offset = ( dns->name.offset + len );
+	if ( offset > dns->name.len ) {
+		DBGC ( dns, "DNS %p name is too long\n", dns );
+		return -EINVAL;
 	}
 
-	return NULL;
-}
-
-/**
- * Append DHCP domain name if available and name is not fully qualified
- *
- * @v string		Name as a NUL-terminated string
- * @ret fqdn		Fully-qualified domain name, malloc'd copy
- *
- * The caller must free fqdn which is allocated even if the name is already
- * fully qualified.
- */
-static char * dns_qualify_name ( const char *string ) {
-	char *fqdn;
+	/* Construct question */
+	dns->question = ( ( ( void * ) &dns->buf ) + offset );
+	dns->question->qtype = dns->qtype;
+	dns->question->qclass = htons ( DNS_CLASS_IN );
 
-	/* Leave unchanged if already fully-qualified or no local domain */
-	if ( ( ! localdomain ) || ( strchr ( string, '.' ) != NULL ) )
-		return strdup ( string );
-
-	/* Append local domain to name */
-	asprintf ( &fqdn, "%s.%s", string, localdomain );
-	return fqdn;
-}
-
-/**
- * Convert a standard NUL-terminated string to a DNS name
- *
- * @v string		Name as a NUL-terminated string
- * @v buf		Buffer in which to place DNS name
- * @ret next		Byte following constructed DNS name
- *
- * DNS names consist of "<length>element" pairs.
- */
-static char * dns_make_name ( const char *string, char *buf ) {
-	char *length_byte;
-	char c;
-
-	length_byte = buf++;
-	*length_byte = 0;
-	do {
-		c = *(string++);
-		if ( ( c == '.' ) || ( c == '\0' ) ) {
-			if ( *length_byte ) {
-				length_byte = buf++;
-				*length_byte = 0;
-			}
-		} else {
-			*(buf++) = c;
-			(*length_byte)++;
-		}
-	} while ( c );
-
-	return buf;
-}
-
-/**
- * Convert an uncompressed DNS name to a NUL-terminated string
- *
- * @v name		DNS name
- * @ret string		NUL-terminated string
- *
- * Produce a printable version of a DNS name.  Used only for debugging.
- */
-static inline char * dns_unmake_name ( char *name ) {
-	char *p;
-	unsigned int len;
-
-	p = name;
-	while ( ( len = *p ) ) {
-		*(p++) = '.';
-		p += len;
-	}
+	/* Store length */
+	dns->len = ( offset + sizeof ( *(dns->question) ) );
 
-	return name + 1;
-}
+	/* Restore name */
+	dns->name.offset = offsetof ( typeof ( dns->buf ), name );
 
-/**
- * Decompress a DNS name
- *
- * @v reply		DNS replay
- * @v name		DNS name
- * @v buf		Buffer into which to decompress DNS name
- * @ret next		Byte following decompressed DNS name
- */
-static char * dns_decompress_name ( const struct dns_header *reply,
-				    const char *name, char *buf ) {
-	int i, len;
-
-	do {
-		/* Obtain next section of name */
-		while ( ( *name ) & 0xc0 ) {
-			name = ( ( char * ) reply +
-				 ( ntohs ( *((uint16_t *)name) ) & ~0xc000 ) );
-		}
-		/* Copy data */
-		len = *name;
-		for ( i = len + 1 ; i > 0 ; i-- ) {
-			*(buf++) = *(name++);
-		}
-	} while ( len );
-	return buf;
+	return 0;
 }
 
 /**
- * Send next packet in DNS request
+ * Send DNS query
  *
  * @v dns		DNS request
+ * @ret rc		Return status code
  */
 static int dns_send_packet ( struct dns_request *dns ) {
-	static unsigned int qid = 0;
-	size_t qlen;
-
-	/* Increment query ID */
-	dns->query.dns.id = htons ( ++qid );
-
-	DBGC ( dns, "DNS %p sending query ID %d\n", dns, qid );
+	struct dns_header *query = &dns->buf.query;
 
 	/* Start retransmission timer */
 	start_timer ( &dns->timer );
 
+	/* Generate query identifier */
+	query->id = random();
+
+	/* Send query */
+	DBGC ( dns, "DNS %p sending query ID %#04x for %s type %s\n", dns,
+	       ntohs ( query->id ), dns_name ( &dns->name ),
+	       dns_type ( dns->question->qtype ) );
+
 	/* Send the data */
-	qlen = ( ( ( void * ) dns->qinfo ) - ( ( void * ) &dns->query )
-		 + sizeof ( dns->qinfo ) );
-	return xfer_deliver_raw ( &dns->socket, &dns->query, qlen );
+	return xfer_deliver_raw ( &dns->socket, query, dns->len );
 }
 
 /**
@@ -376,51 +605,110 @@ static void dns_timer_expired ( struct retry_timer *timer, int fail ) {
 static int dns_xfer_deliver ( struct dns_request *dns,
 			      struct io_buffer *iobuf,
 			      struct xfer_metadata *meta __unused ) {
-	const struct dns_header *reply = iobuf->data;
-	union dns_rr_info *rr_info;
-	unsigned int qtype = dns->qinfo->qtype;
+	struct dns_header *response = iobuf->data;
+	struct dns_header *query = &dns->buf.query;
+	unsigned int qtype = dns->question->qtype;
+	struct dns_name buf;
+	union dns_rr *rr;
+	int offset;
+	size_t answer_offset;
+	size_t next_offset;
+	size_t rdlength;
 	int rc;
 
 	/* Sanity check */
-	if ( iob_len ( iobuf ) < sizeof ( *reply ) ) {
+	if ( iob_len ( iobuf ) < sizeof ( *response ) ) {
 		DBGC ( dns, "DNS %p received underlength packet length %zd\n",
 		       dns, iob_len ( iobuf ) );
 		rc = -EINVAL;
 		goto done;
 	}
 
-	/* Check reply ID matches query ID */
-	if ( reply->id != dns->query.dns.id ) {
-		DBGC ( dns, "DNS %p received unexpected reply ID %d "
-		       "(wanted %d)\n", dns, ntohs ( reply->id ),
-		       ntohs ( dns->query.dns.id ) );
+	/* Check response ID matches query ID */
+	if ( response->id != query->id ) {
+		DBGC ( dns, "DNS %p received unexpected response ID %#04x "
+		       "(wanted %d)\n", dns, ntohs ( response->id ),
+		       ntohs ( query->id ) );
 		rc = -EINVAL;
 		goto done;
 	}
+	DBGC ( dns, "DNS %p received response ID %#04x\n",
+	       dns, ntohs ( response->id ) );
 
-	DBGC ( dns, "DNS %p received reply ID %d\n", dns, ntohs ( reply->id ));
+	/* Check that we have exactly one question */
+	if ( response->qdcount != htons ( 1 ) ) {
+		DBGC ( dns, "DNS %p received response with %d questions\n",
+		       dns, ntohs ( response->qdcount ) );
+		rc = -EINVAL;
+		goto done;
+	}
 
-	/* Stop the retry timer.  After this point, each code path
-	 * must either restart the timer by calling dns_send_packet(),
-	 * or mark the DNS operation as complete by calling
-	 * dns_done()
-	 */
-	stop_timer ( &dns->timer );
+	/* Skip question section */
+	buf.data = iobuf->data;
+	buf.offset = sizeof ( *response );
+	buf.len = iob_len ( iobuf );
+	offset = dns_skip ( &buf );
+	if ( offset < 0 ) {
+		rc = offset;
+		DBGC ( dns, "DNS %p received response with malformed "
+		       "question: %s\n", dns, strerror ( rc ) );
+		goto done;
+	}
+	answer_offset = ( offset + sizeof ( struct dns_question ) );
 
 	/* Search through response for useful answers.  Do this
 	 * multiple times, to take advantage of useful nameservers
 	 * which send us e.g. the CNAME *and* the A record for the
 	 * pointed-to name.
 	 */
-	while ( ( rr_info = dns_find_rr ( dns, reply ) ) ) {
-		switch ( rr_info->common.type ) {
+	for ( buf.offset = answer_offset ; buf.offset != buf.len ;
+	      buf.offset = next_offset ) {
+
+		/* Check for valid name */
+		offset = dns_skip ( &buf );
+		if ( offset < 0 ) {
+			rc = offset;
+			DBGC ( dns, "DNS %p received response with malformed "
+			       "answer: %s\n", dns, strerror ( rc ) );
+			goto done;
+		}
+
+		/* Check for sufficient space for resource record */
+		rr = ( buf.data + offset );
+		if ( ( offset + sizeof ( rr->common ) ) > buf.len ) {
+			DBGC ( dns, "DNS %p received response with underlength "
+			       "RR\n", dns );
+			rc = -EINVAL;
+			goto done;
+		}
+		rdlength = ntohs ( rr->common.rdlength );
+		next_offset = ( offset + sizeof ( rr->common ) + rdlength );
+		if ( next_offset > buf.len ) {
+			DBGC ( dns, "DNS %p received response with underlength "
+			       "RR\n", dns );
+			rc = -EINVAL;
+			goto done;
+		}
+
+		/* Skip non-matching names */
+		if ( dns_compare ( &buf, &dns->name ) != 0 )
+			continue;
+
+		/* Handle answer */
+		switch ( rr->common.type ) {
 
 		case htons ( DNS_TYPE_AAAA ):
 
 			/* Found the target AAAA record */
+			if ( rdlength < sizeof ( dns->address.sin6.sin6_addr )){
+				DBGC ( dns, "DNS %p received response with "
+				       "underlength AAAA\n", dns );
+				rc = -EINVAL;
+				goto done;
+			}
 			dns->address.sin6.sin6_family = AF_INET6;
 			memcpy ( &dns->address.sin6.sin6_addr,
-				 &rr_info->aaaa.in6_addr,
+				 &rr->aaaa.in6_addr,
 				 sizeof ( dns->address.sin6.sin6_addr ) );
 			dns_resolved ( dns );
 			rc = 0;
@@ -429,39 +717,56 @@ static int dns_xfer_deliver ( struct dns_request *dns,
 		case htons ( DNS_TYPE_A ):
 
 			/* Found the target A record */
+			if ( rdlength < sizeof ( dns->address.sin.sin_addr ) ) {
+				DBGC ( dns, "DNS %p received response with "
+				       "underlength A\n", dns );
+				rc = -EINVAL;
+				goto done;
+			}
 			dns->address.sin.sin_family = AF_INET;
-			dns->address.sin.sin_addr = rr_info->a.in_addr;
+			dns->address.sin.sin_addr = rr->a.in_addr;
 			dns_resolved ( dns );
 			rc = 0;
 			goto done;
 
 		case htons ( DNS_TYPE_CNAME ):
 
-			/* Found a CNAME record; update query and recurse */
-			DBGC ( dns, "DNS %p found CNAME\n", dns );
-			dns->qinfo = ( void * ) dns_decompress_name ( reply,
-							 rr_info->cname.cname,
-							 dns->query.payload );
-			dns->qinfo->qtype = dns->qtype;
-			dns->qinfo->qclass = htons ( DNS_CLASS_IN );
-			
 			/* Terminate the operation if we recurse too far */
 			if ( ++dns->recursion > DNS_MAX_CNAME_RECURSION ) {
 				DBGC ( dns, "DNS %p recursion exceeded\n",
 				       dns );
-				dns_done ( dns, -ELOOP );
-				rc = 0;
+				rc = -ELOOP;
+				dns_done ( dns, rc );
+				goto done;
+			}
+
+			/* Found a CNAME record; update query and recurse */
+			buf.offset = ( offset + sizeof ( rr->cname ) );
+			DBGC ( dns, "DNS %p found CNAME %s\n",
+			       dns, dns_name ( &buf ) );
+			dns->search.offset = dns->search.len;
+			dns_copy ( &buf, &dns->name );
+			if ( ( rc = dns_question ( dns ) ) != 0 ) {
+				dns_done ( dns, rc );
 				goto done;
 			}
+			next_offset = answer_offset;
 			break;
 
 		default:
 			DBGC ( dns, "DNS %p got unknown record type %d\n",
-			       dns, ntohs ( rr_info->common.type ) );
+			       dns, ntohs ( rr->common.type ) );
 			break;
 		}
 	}
-	
+
+	/* Stop the retry timer.  After this point, each code path
+	 * must either restart the timer by calling dns_send_packet(),
+	 * or mark the DNS operation as complete by calling
+	 * dns_done()
+	 */
+	stop_timer ( &dns->timer );
+
 	/* Determine what to do next based on the type of query we
 	 * issued and the response we received
 	 */
@@ -472,7 +777,7 @@ static int dns_xfer_deliver ( struct dns_request *dns,
 		 * the A.
 		 */
 		DBGC ( dns, "DNS %p found no AAAA record; trying A\n", dns );
-		dns->qinfo->qtype = htons ( DNS_TYPE_A );
+		dns->question->qtype = htons ( DNS_TYPE_A );
 		dns_send_packet ( dns );
 		rc = 0;
 		goto done;
@@ -482,31 +787,49 @@ static int dns_xfer_deliver ( struct dns_request *dns,
 		 * try the CNAME.
 		 */
 		DBGC ( dns, "DNS %p found no A record; trying CNAME\n", dns );
-		dns->qinfo->qtype = htons ( DNS_TYPE_CNAME );
+		dns->question->qtype = htons ( DNS_TYPE_CNAME );
 		dns_send_packet ( dns );
 		rc = 0;
 		goto done;
 
 	case htons ( DNS_TYPE_CNAME ):
 		/* We asked for a CNAME record.  If we got a response
-		 * (i.e. if the next A query is already set up), then
-		 * issue it, otherwise abort.
+		 * (i.e. if the next AAAA/A query is already set up),
+		 * then issue it.
 		 */
-		if ( dns->qinfo->qtype == dns->qtype ) {
+		if ( qtype == dns->qtype ) {
 			dns_send_packet ( dns );
 			rc = 0;
 			goto done;
-		} else {
+		}
+
+		/* If we have already reached the end of the search list,
+		 * then terminate lookup.
+		 */
+		if ( dns->search.offset == dns->search.len ) {
 			DBGC ( dns, "DNS %p found no CNAME record\n", dns );
-			dns_done ( dns, -ENXIO_NO_RECORD );
-			rc = 0;
+			rc = -ENXIO_NO_RECORD;
+			dns_done ( dns, rc );
 			goto done;
 		}
 
+		/* Move to next entry in search list.  This can never fail,
+		 * since we have already used this entry.
+		 */
+		DBGC ( dns, "DNS %p found no CNAME record; trying next "
+		       "suffix\n", dns );
+		dns->search.offset = dns_skip_search ( &dns->search );
+		if ( ( rc = dns_question ( dns ) ) != 0 ) {
+			dns_done ( dns, rc );
+			goto done;
+		}
+		dns_send_packet ( dns );
+		goto done;
+
 	default:
 		assert ( 0 );
-		dns_done ( dns, -EINVAL );
 		rc = -EINVAL;
+		dns_done ( dns, rc );
 		goto done;
 	}
 
@@ -560,7 +883,9 @@ static struct interface_descriptor dns_resolv_desc =
 static int dns_resolv ( struct interface *resolv,
 			const char *name, struct sockaddr *sa ) {
 	struct dns_request *dns;
-	char *fqdn;
+	struct dns_header *query;
+	size_t search_len;
+	int name_len;
 	int rc;
 
 	/* Fail immediately if no DNS servers */
@@ -571,15 +896,11 @@ static int dns_resolv ( struct interface *resolv,
 		goto err_no_nameserver;
 	}
 
-	/* Ensure fully-qualified domain name if DHCP option was given */
-	fqdn = dns_qualify_name ( name );
-	if ( ! fqdn ) {
-		rc = -ENOMEM;
-		goto err_qualify_name;
-	}
+	/* Determine whether or not to use search list */
+	search_len = ( strchr ( name, '.' ) ? 0 : dns_search.len );
 
 	/* Allocate DNS structure */
-	dns = zalloc ( sizeof ( *dns ) );
+	dns = zalloc ( sizeof ( *dns ) + search_len );
 	if ( ! dns ) {
 		rc = -ENOMEM;
 		goto err_alloc_dns;
@@ -589,6 +910,9 @@ static int dns_resolv ( struct interface *resolv,
 	intf_init ( &dns->socket, &dns_socket_desc, &dns->refcnt );
 	timer_init ( &dns->timer, dns_timer_expired, &dns->refcnt );
 	memcpy ( &dns->address.sa, sa, sizeof ( dns->address.sa ) );
+	dns->search.data = ( ( ( void * ) dns ) + sizeof ( *dns ) );
+	dns->search.len = search_len;
+	memcpy ( dns->search.data, dns_search.data, search_len );
 
 	/* Determine initial query type */
 	switch ( nameserver.sa.sa_family ) {
@@ -600,16 +924,25 @@ static int dns_resolv ( struct interface *resolv,
 		break;
 	default:
 		rc = -ENOTSUP;
-		goto err_qtype;
+		goto err_type;
 	}
 
-	/* Create query */
-	dns->query.dns.flags = htons ( DNS_FLAG_QUERY | DNS_FLAG_OPCODE_QUERY |
-				       DNS_FLAG_RD );
-	dns->query.dns.qdcount = htons ( 1 );
-	dns->qinfo = ( void * ) dns_make_name ( fqdn, dns->query.payload );
-	dns->qinfo->qtype = dns->qtype;
-	dns->qinfo->qclass = htons ( DNS_CLASS_IN );
+	/* Construct query */
+	query = &dns->buf.query;
+	query->flags = htons ( DNS_FLAG_RD );
+	query->qdcount = htons ( 1 );
+	dns->name.data = &dns->buf;
+	dns->name.offset = offsetof ( typeof ( dns->buf ), name );
+	dns->name.len = offsetof ( typeof ( dns->buf ), padding );
+	name_len = dns_encode ( name, &dns->name );
+	if ( name_len < 0 ) {
+		rc = name_len;
+		goto err_encode;
+	}
+	dns->offset = ( offsetof ( typeof ( dns->buf ), name ) +
+			name_len - 1 /* Strip root label */ );
+	if ( ( rc = dns_question ( dns ) ) != 0 )
+		goto err_question;
 
 	/* Open UDP connection */
 	if ( ( rc = xfer_open_socket ( &dns->socket, SOCK_DGRAM,
@@ -619,21 +952,20 @@ static int dns_resolv ( struct interface *resolv,
 		goto err_open_socket;
 	}
 
-	/* Send first DNS packet */
-	dns_send_packet ( dns );
+	/* Start timer to trigger first packet */
+	start_timer_nodelay ( &dns->timer );
 
 	/* Attach parent interface, mortalise self, and return */
 	intf_plug_plug ( &dns->resolv, resolv );
 	ref_put ( &dns->refcnt );
-	free ( fqdn );
 	return 0;	
 
  err_open_socket:
- err_qtype:
+ err_question:
+ err_encode:
+ err_type:
 	ref_put ( &dns->refcnt );
  err_alloc_dns:
-	free ( fqdn );
- err_qualify_name:
  err_no_nameserver:
 	return rc;
 }
@@ -651,6 +983,56 @@ struct resolver dns_resolver __resolver ( RESOLV_NORMAL ) = {
  ******************************************************************************
  */
 
+/**
+ * Format DNS search list setting
+ *
+ * @v type		Setting type
+ * @v raw		Raw setting value
+ * @v raw_len		Length of raw setting value
+ * @v buf		Buffer to contain formatted value
+ * @v len		Length of buffer
+ * @ret len		Length of formatted value, or negative error
+ */
+static int format_dnssl_setting ( const struct setting_type *type __unused,
+				  const void *raw, size_t raw_len,
+				  char *buf, size_t len ) {
+	struct dns_name name = {
+		.data = ( ( void * ) raw ),
+		.len = raw_len,
+	};
+	size_t remaining = len;
+	size_t total = 0;
+	int name_len;
+
+	while ( name.offset < raw_len ) {
+
+		/* Decode name */
+		remaining = ( ( total < len ) ? ( len - total ) : 0 );
+		name_len = dns_decode ( &name, ( buf + total ), remaining );
+		if ( name_len < 0 )
+			return name_len;
+		total += name_len;
+
+		/* Move to next name */
+		name.offset = dns_skip_search ( &name );
+
+		/* Add separator if applicable */
+		if ( name.offset != raw_len ) {
+			if ( total < len )
+				buf[total] = ' ';
+			total++;
+		}
+	}
+
+	return total;
+}
+
+/** A DNS search list setting type */
+const struct setting_type setting_type_dnssl __setting_type = {
+	.name = "dnssl",
+	.format = format_dnssl_setting,
+};
+
 /** IPv4 DNS server setting */
 const struct setting dns_setting __setting ( SETTING_IP_EXTRA, dns ) = {
 	.name = "dns",
@@ -668,6 +1050,50 @@ const struct setting dns6_setting __setting ( SETTING_IP_EXTRA, dns6 ) = {
 	.scope = &ipv6_scope,
 };
 
+/** DNS search list */
+const struct setting dnssl_setting __setting ( SETTING_IP_EXTRA, dnssl ) = {
+	.name = "dnssl",
+	.description = "DNS search list",
+	.tag = DHCP_DOMAIN_SEARCH,
+	.type = &setting_type_dnssl,
+};
+
+/**
+ * Apply DNS search list
+ *
+ */
+static void apply_dns_search ( void ) {
+	char *localdomain;
+	int len;
+
+	/* Free existing search list */
+	free ( dns_search.data );
+	memset ( &dns_search, 0, sizeof ( dns_search ) );
+
+	/* Fetch DNS search list */
+	len = fetch_setting_copy ( NULL, &dnssl_setting, NULL, NULL,
+				   &dns_search.data );
+	if ( len >= 0 ) {
+		dns_search.len = len;
+		return;
+	}
+
+	/* If no DNS search list exists, try to fetch the local domain */
+	fetch_string_setting_copy ( NULL, &domain_setting, &localdomain );
+	if ( localdomain ) {
+		len = dns_encode ( localdomain, &dns_search );
+		if ( len >= 0 ) {
+			dns_search.data = malloc ( len );
+			if ( dns_search.data ) {
+				dns_search.len = len;
+				dns_encode ( localdomain, &dns_search );
+			}
+		}
+		free ( localdomain );
+		return;
+	}
+}
+
 /**
  * Apply DNS settings
  *
@@ -689,11 +1115,23 @@ static int apply_dns_settings ( void ) {
 		      sock_ntoa ( &nameserver.sa ) );
 	}
 
-	/* Get local domain DHCP option */
-	free ( localdomain );
-	fetch_string_setting_copy ( NULL, &domain_setting, &localdomain );
-	if ( localdomain )
-		DBG ( "DNS local domain %s\n", localdomain );
+	/* Fetch DNS search list */
+	apply_dns_search();
+	if ( DBG_LOG && ( dns_search.len != 0 ) ) {
+		struct dns_name name;
+		int offset;
+
+		DBG ( "DNS search list:" );
+		memcpy ( &name, &dns_search, sizeof ( name ) );
+		while ( name.offset != name.len ) {
+			DBG ( " %s", dns_name ( &name ) );
+			offset = dns_skip_search ( &name );
+			if ( offset < 0 )
+				break;
+			name.offset = offset;
+		}
+		DBG ( "\n" );
+	}
 
 	return 0;
 }