#include "config.h"
#include "util/data/msgencode.h"
#include "util/data/msgreply.h"
#include "util/data/msgparse.h"
#include "util/data/dname.h"
#include "util/log.h"
#include "util/regional.h"
#include "util/net_help.h"
#include "ldns/sbuffer.h"
#define RETVAL_OUTMEM -2
#define RETVAL_TRUNC -4
#define RETVAL_OK 0
struct compress_tree_node {
struct compress_tree_node* left;
struct compress_tree_node* right;
struct compress_tree_node* parent;
uint8_t* dname;
int labs;
size_t offset;
};
static int
compress_tree_search(struct compress_tree_node** tree, uint8_t* dname,
int labs, struct compress_tree_node** match, int* matchlabels,
struct compress_tree_node*** insertpt)
{
int c, n, closen=0;
struct compress_tree_node* p = *tree;
struct compress_tree_node* close = 0;
struct compress_tree_node** prev = tree;
while(p) {
if((c = dname_lab_cmp(dname, labs, p->dname, p->labs, &n))
== 0) {
*matchlabels = n;
*match = p;
return 1;
}
if(c<0) {
prev = &p->left;
p = p->left;
} else {
closen = n;
close = p;
prev = &p->right;
p = p->right;
}
}
*insertpt = prev;
*matchlabels = closen;
*match = close;
return 0;
}
static struct compress_tree_node*
compress_tree_lookup(struct compress_tree_node** tree, uint8_t* dname,
int labs, struct compress_tree_node*** insertpt)
{
struct compress_tree_node* p;
int m;
if(labs <= 1)
return 0;
if(compress_tree_search(tree, dname, labs, &p, &m, insertpt)) {
return p;
}
if(m>1) {
while(p && p->labs > m)
p = p->parent;
return p;
}
return 0;
}
static struct compress_tree_node*
compress_tree_newnode(uint8_t* dname, int labs, size_t offset,
struct regional* region)
{
struct compress_tree_node* n = (struct compress_tree_node*)
regional_alloc(region, sizeof(struct compress_tree_node));
if(!n) return 0;
n->left = 0;
n->right = 0;
n->parent = 0;
n->dname = dname;
n->labs = labs;
n->offset = offset;
return n;
}
static int
compress_tree_store(uint8_t* dname, int labs, size_t offset,
struct regional* region, struct compress_tree_node* closest,
struct compress_tree_node** insertpt)
{
uint8_t lablen;
struct compress_tree_node* newnode;
struct compress_tree_node* prevnode = NULL;
int uplabs = labs-1;
if(closest) uplabs = labs - closest->labs;
log_assert(uplabs >= 0);
while(uplabs--) {
if(offset > PTR_MAX_OFFSET) {
return 1;
}
if(!(newnode = compress_tree_newnode(dname, labs, offset,
region))) {
return 0;
}
if(prevnode) {
newnode->right = prevnode;
prevnode->parent = newnode;
}
lablen = *dname++;
dname += lablen;
offset += lablen+1;
prevnode = newnode;
labs--;
}
if(prevnode) {
*insertpt = prevnode;
prevnode->parent = closest;
}
return 1;
}
static int
write_compressed_dname(sldns_buffer* pkt, uint8_t* dname, int labs,
struct compress_tree_node* p)
{
int labcopy = labs - p->labs;
uint8_t lablen;
uint16_t ptr;
if(labs == 1) {
if(sldns_buffer_remaining(pkt) < 1)
return 0;
sldns_buffer_write_u8(pkt, 0);
return 1;
}
while(labcopy--) {
lablen = *dname++;
if(sldns_buffer_remaining(pkt) < (size_t)lablen+1)
return 0;
sldns_buffer_write_u8(pkt, lablen);
sldns_buffer_write(pkt, dname, lablen);
dname += lablen;
}
if(sldns_buffer_remaining(pkt) < 2)
return 0;
ptr = PTR_CREATE(p->offset);
sldns_buffer_write_u16(pkt, ptr);
return 1;
}
static int
compress_owner(struct ub_packed_rrset_key* key, sldns_buffer* pkt,
struct regional* region, struct compress_tree_node** tree,
size_t owner_pos, uint16_t* owner_ptr, int owner_labs)
{
struct compress_tree_node* p;
struct compress_tree_node** insertpt;
if(!*owner_ptr) {
if((p = compress_tree_lookup(tree, key->rk.dname,
owner_labs, &insertpt))) {
if(p->labs == owner_labs)
*owner_ptr = htons(PTR_CREATE(p->offset));
if(!write_compressed_dname(pkt, key->rk.dname,
owner_labs, p))
return RETVAL_TRUNC;
if(sldns_buffer_remaining(pkt) < 4+4+2)
return RETVAL_TRUNC;
} else {
if(sldns_buffer_remaining(pkt) < key->rk.dname_len+4+4+2)
return RETVAL_TRUNC;
sldns_buffer_write(pkt, key->rk.dname,
key->rk.dname_len);
if(owner_pos <= PTR_MAX_OFFSET)
*owner_ptr = htons(PTR_CREATE(owner_pos));
}
if(!compress_tree_store(key->rk.dname, owner_labs,
owner_pos, region, p, insertpt))
return RETVAL_OUTMEM;
} else {
if(owner_labs == 1) {
if(sldns_buffer_remaining(pkt) < 1+4+4+2)
return RETVAL_TRUNC;
sldns_buffer_write_u8(pkt, 0);
} else {
if(sldns_buffer_remaining(pkt) < 2+4+4+2)
return RETVAL_TRUNC;
sldns_buffer_write(pkt, owner_ptr, 2);
}
}
return RETVAL_OK;
}
static int
compress_any_dname(uint8_t* dname, sldns_buffer* pkt, int labs,
struct regional* region, struct compress_tree_node** tree)
{
struct compress_tree_node* p;
struct compress_tree_node** insertpt = NULL;
size_t pos = sldns_buffer_position(pkt);
if((p = compress_tree_lookup(tree, dname, labs, &insertpt))) {
if(!write_compressed_dname(pkt, dname, labs, p))
return RETVAL_TRUNC;
} else {
if(!dname_buffer_write(pkt, dname))
return RETVAL_TRUNC;
}
if(!compress_tree_store(dname, labs, pos, region, p, insertpt))
return RETVAL_OUTMEM;
return RETVAL_OK;
}
static const sldns_rr_descriptor*
type_rdata_compressable(struct ub_packed_rrset_key* key)
{
uint16_t t = ntohs(key->rk.type);
if(sldns_rr_descript(t) &&
sldns_rr_descript(t)->_compress == LDNS_RR_COMPRESS)
return sldns_rr_descript(t);
return 0;
}
static int
compress_rdata(sldns_buffer* pkt, uint8_t* rdata, size_t todolen,
struct regional* region, struct compress_tree_node** tree,
const sldns_rr_descriptor* desc)
{
int labs, r, rdf = 0;
size_t dname_len, len, pos = sldns_buffer_position(pkt);
uint8_t count = desc->_dname_count;
sldns_buffer_skip(pkt, 2);
rdata += 2;
todolen -= 2;
while(todolen > 0 && count) {
switch(desc->_wireformat[rdf]) {
case LDNS_RDF_TYPE_DNAME:
labs = dname_count_size_labels(rdata, &dname_len);
if((r=compress_any_dname(rdata, pkt, labs, region,
tree)) != RETVAL_OK)
return r;
rdata += dname_len;
todolen -= dname_len;
count--;
len = 0;
break;
case LDNS_RDF_TYPE_STR:
len = *rdata + 1;
break;
default:
len = get_rdf_size(desc->_wireformat[rdf]);
}
if(len) {
if(sldns_buffer_remaining(pkt) < len)
return RETVAL_TRUNC;
sldns_buffer_write(pkt, rdata, len);
todolen -= len;
rdata += len;
}
rdf++;
}
if(todolen > 0) {
if(sldns_buffer_remaining(pkt) < todolen)
return RETVAL_TRUNC;
sldns_buffer_write(pkt, rdata, todolen);
}
sldns_buffer_write_u16_at(pkt, pos, sldns_buffer_position(pkt)-pos-2);
return RETVAL_OK;
}
static int
rrset_belongs_in_reply(sldns_pkt_section s, uint16_t rrtype, uint16_t qtype,
int dnssec)
{
if(dnssec)
return 1;
if(s == LDNS_SECTION_ANSWER) {
if(qtype == LDNS_RR_TYPE_ANY || qtype == rrtype)
return 1;
}
switch(rrtype) {
case LDNS_RR_TYPE_SIG:
case LDNS_RR_TYPE_KEY:
case LDNS_RR_TYPE_NXT:
case LDNS_RR_TYPE_DS:
case LDNS_RR_TYPE_RRSIG:
case LDNS_RR_TYPE_NSEC:
case LDNS_RR_TYPE_DNSKEY:
case LDNS_RR_TYPE_NSEC3:
case LDNS_RR_TYPE_NSEC3PARAMS:
return 0;
}
return 1;
}
static int
packed_rrset_encode(struct ub_packed_rrset_key* key, sldns_buffer* pkt,
uint16_t* num_rrs, time_t timenow, struct regional* region,
int do_data, int do_sig, struct compress_tree_node** tree,
sldns_pkt_section s, uint16_t qtype, int dnssec, size_t rr_offset)
{
size_t i, j, owner_pos;
int r, owner_labs;
uint16_t owner_ptr = 0;
struct packed_rrset_data* data = (struct packed_rrset_data*)
key->entry.data;
if(!rrset_belongs_in_reply(s, ntohs(key->rk.type), qtype, dnssec))
return RETVAL_OK;
owner_labs = dname_count_labels(key->rk.dname);
owner_pos = sldns_buffer_position(pkt);
if(do_data) {
const sldns_rr_descriptor* c = type_rdata_compressable(key);
for(i=0; i<data->count; i++) {
j = (i + rr_offset) % data->count;
if((r=compress_owner(key, pkt, region, tree,
owner_pos, &owner_ptr, owner_labs))
!= RETVAL_OK)
return r;
sldns_buffer_write(pkt, &key->rk.type, 2);
sldns_buffer_write(pkt, &key->rk.rrset_class, 2);
if(data->rr_ttl[j] < timenow)
sldns_buffer_write_u32(pkt, 0);
else sldns_buffer_write_u32(pkt,
data->rr_ttl[j]-timenow);
if(c) {
if((r=compress_rdata(pkt, data->rr_data[j],
data->rr_len[j], region, tree, c))
!= RETVAL_OK)
return r;
} else {
if(sldns_buffer_remaining(pkt) < data->rr_len[j])
return RETVAL_TRUNC;
sldns_buffer_write(pkt, data->rr_data[j],
data->rr_len[j]);
}
}
}
if(do_sig && dnssec) {
size_t total = data->count+data->rrsig_count;
for(i=data->count; i<total; i++) {
if(owner_ptr && owner_labs != 1) {
if(sldns_buffer_remaining(pkt) <
2+4+4+data->rr_len[i])
return RETVAL_TRUNC;
sldns_buffer_write(pkt, &owner_ptr, 2);
} else {
if((r=compress_any_dname(key->rk.dname,
pkt, owner_labs, region, tree))
!= RETVAL_OK)
return r;
if(sldns_buffer_remaining(pkt) <
4+4+data->rr_len[i])
return RETVAL_TRUNC;
}
sldns_buffer_write_u16(pkt, LDNS_RR_TYPE_RRSIG);
sldns_buffer_write(pkt, &key->rk.rrset_class, 2);
if(data->rr_ttl[i] < timenow)
sldns_buffer_write_u32(pkt, 0);
else sldns_buffer_write_u32(pkt,
data->rr_ttl[i]-timenow);
sldns_buffer_write(pkt, data->rr_data[i],
data->rr_len[i]);
}
}
if(do_data)
*num_rrs += data->count;
if(do_sig && dnssec)
*num_rrs += data->rrsig_count;
return RETVAL_OK;
}
static int
insert_section(struct reply_info* rep, size_t num_rrsets, uint16_t* num_rrs,
sldns_buffer* pkt, size_t rrsets_before, time_t timenow,
struct regional* region, struct compress_tree_node** tree,
sldns_pkt_section s, uint16_t qtype, int dnssec, size_t rr_offset)
{
int r;
size_t i, setstart;
*num_rrs = 0;
if(s != LDNS_SECTION_ADDITIONAL) {
if(s == LDNS_SECTION_ANSWER && qtype == LDNS_RR_TYPE_ANY)
dnssec = 1;
for(i=0; i<num_rrsets; i++) {
setstart = sldns_buffer_position(pkt);
if((r=packed_rrset_encode(rep->rrsets[rrsets_before+i],
pkt, num_rrs, timenow, region, 1, 1, tree,
s, qtype, dnssec, rr_offset))
!= RETVAL_OK) {
sldns_buffer_set_position(pkt, setstart);
return r;
}
}
} else {
for(i=0; i<num_rrsets; i++) {
setstart = sldns_buffer_position(pkt);
if((r=packed_rrset_encode(rep->rrsets[rrsets_before+i],
pkt, num_rrs, timenow, region, 1, 0, tree,
s, qtype, dnssec, rr_offset))
!= RETVAL_OK) {
sldns_buffer_set_position(pkt, setstart);
return r;
}
}
if(dnssec)
for(i=0; i<num_rrsets; i++) {
setstart = sldns_buffer_position(pkt);
if((r=packed_rrset_encode(rep->rrsets[rrsets_before+i],
pkt, num_rrs, timenow, region, 0, 1, tree,
s, qtype, dnssec, rr_offset))
!= RETVAL_OK) {
sldns_buffer_set_position(pkt, setstart);
return r;
}
}
}
return RETVAL_OK;
}
static int
insert_query(struct query_info* qinfo, struct compress_tree_node** tree,
sldns_buffer* buffer, struct regional* region)
{
if(sldns_buffer_remaining(buffer) <
qinfo->qname_len+sizeof(uint16_t)*2)
return RETVAL_TRUNC;
if(!compress_tree_store(qinfo->qname,
dname_count_labels(qinfo->qname),
sldns_buffer_position(buffer), region, NULL, tree))
return RETVAL_OUTMEM;
if(sldns_buffer_current(buffer) == qinfo->qname)
sldns_buffer_skip(buffer, (ssize_t)qinfo->qname_len);
else sldns_buffer_write(buffer, qinfo->qname, qinfo->qname_len);
sldns_buffer_write_u16(buffer, qinfo->qtype);
sldns_buffer_write_u16(buffer, qinfo->qclass);
return RETVAL_OK;
}
static int
positive_answer(struct reply_info* rep, uint16_t qtype) {
size_t i;
if (FLAGS_GET_RCODE(rep->flags) != LDNS_RCODE_NOERROR)
return 0;
for(i=0;i<rep->an_numrrsets; i++) {
if(ntohs(rep->rrsets[i]->rk.type) == qtype) {
for(i=rep->an_numrrsets; i<rep->an_numrrsets+
rep->ns_numrrsets; i++) {
if(ntohs(rep->rrsets[i]->rk.type) ==
LDNS_RR_TYPE_NSEC ||
ntohs(rep->rrsets[i]->rk.type) ==
LDNS_RR_TYPE_NSEC3)
return 0;
}
return 1;
}
}
return 0;
}
int
reply_info_encode(struct query_info* qinfo, struct reply_info* rep,
uint16_t id, uint16_t flags, sldns_buffer* buffer, time_t timenow,
struct regional* region, uint16_t udpsize, int dnssec)
{
uint16_t ancount=0, nscount=0, arcount=0;
struct compress_tree_node* tree = 0;
int r;
size_t rr_offset;
sldns_buffer_clear(buffer);
if(udpsize < sldns_buffer_limit(buffer))
sldns_buffer_set_limit(buffer, udpsize);
if(sldns_buffer_remaining(buffer) < LDNS_HEADER_SIZE)
return 0;
sldns_buffer_write(buffer, &id, sizeof(uint16_t));
sldns_buffer_write_u16(buffer, flags);
sldns_buffer_write_u16(buffer, rep->qdcount);
sldns_buffer_write(buffer, "\000\000\000\000\000\000", 6);
if(rep->qdcount) {
if((r=insert_query(qinfo, &tree, buffer, region)) !=
RETVAL_OK) {
if(r == RETVAL_TRUNC) {
sldns_buffer_write_u16_at(buffer, 4, 0);
LDNS_TC_SET(sldns_buffer_begin(buffer));
sldns_buffer_flip(buffer);
return 1;
}
return 0;
}
}
rr_offset = RRSET_ROUNDROBIN?ntohs(id):0;
if((r=insert_section(rep, rep->an_numrrsets, &ancount, buffer,
0, timenow, region, &tree, LDNS_SECTION_ANSWER, qinfo->qtype,
dnssec, rr_offset)) != RETVAL_OK) {
if(r == RETVAL_TRUNC) {
sldns_buffer_write_u16_at(buffer, 6, ancount);
LDNS_TC_SET(sldns_buffer_begin(buffer));
sldns_buffer_flip(buffer);
return 1;
}
return 0;
}
sldns_buffer_write_u16_at(buffer, 6, ancount);
if( ! (MINIMAL_RESPONSES && positive_answer(rep, qinfo->qtype)) ) {
if((r=insert_section(rep, rep->ns_numrrsets, &nscount, buffer,
rep->an_numrrsets, timenow, region, &tree,
LDNS_SECTION_AUTHORITY, qinfo->qtype,
dnssec, rr_offset)) != RETVAL_OK) {
if(r == RETVAL_TRUNC) {
sldns_buffer_write_u16_at(buffer, 8, nscount);
LDNS_TC_SET(sldns_buffer_begin(buffer));
sldns_buffer_flip(buffer);
return 1;
}
return 0;
}
sldns_buffer_write_u16_at(buffer, 8, nscount);
if((r=insert_section(rep, rep->ar_numrrsets, &arcount, buffer,
rep->an_numrrsets + rep->ns_numrrsets, timenow, region,
&tree, LDNS_SECTION_ADDITIONAL, qinfo->qtype,
dnssec, rr_offset)) != RETVAL_OK) {
if(r == RETVAL_TRUNC) {
sldns_buffer_write_u16_at(buffer, 10, arcount);
sldns_buffer_flip(buffer);
return 1;
}
return 0;
}
sldns_buffer_write_u16_at(buffer, 10, arcount);
}
sldns_buffer_flip(buffer);
return 1;
}
uint16_t
calc_edns_field_size(struct edns_data* edns)
{
if(!edns || !edns->edns_present)
return 0;
return 1 + 2 + 2 + 4 + 2;
}
void
attach_edns_record(sldns_buffer* pkt, struct edns_data* edns)
{
size_t len;
if(!edns || !edns->edns_present)
return;
sldns_buffer_write_u16_at(pkt, 10,
sldns_buffer_read_u16_at(pkt, 10) + 1);
len = sldns_buffer_limit(pkt);
sldns_buffer_clear(pkt);
sldns_buffer_set_position(pkt, len);
sldns_buffer_write_u8(pkt, 0);
sldns_buffer_write_u16(pkt, LDNS_RR_TYPE_OPT);
sldns_buffer_write_u16(pkt, edns->udp_size);
sldns_buffer_write_u8(pkt, edns->ext_rcode);
sldns_buffer_write_u8(pkt, edns->edns_version);
sldns_buffer_write_u16(pkt, edns->bits);
sldns_buffer_write_u16(pkt, 0);
sldns_buffer_flip(pkt);
}
int
reply_info_answer_encode(struct query_info* qinf, struct reply_info* rep,
uint16_t id, uint16_t qflags, sldns_buffer* pkt, time_t timenow,
int cached, struct regional* region, uint16_t udpsize,
struct edns_data* edns, int dnssec, int secure)
{
uint16_t flags;
int attach_edns = 1;
if(!cached || rep->authoritative) {
flags = rep->flags | (qflags & (BIT_RD|BIT_CD));
} else {
flags = (rep->flags & ~BIT_AA) | (qflags & (BIT_RD|BIT_CD));
}
if(secure && (dnssec || (qflags&BIT_AD)))
flags |= BIT_AD;
log_assert(flags & BIT_QR);
if(udpsize < LDNS_HEADER_SIZE)
return 0;
if(udpsize < LDNS_HEADER_SIZE + calc_edns_field_size(edns)) {
attach_edns = 0;
} else {
udpsize -= calc_edns_field_size(edns);
}
if(!reply_info_encode(qinf, rep, id, flags, pkt, timenow, region,
udpsize, dnssec)) {
log_err("reply encode: out of memory");
return 0;
}
if(attach_edns)
attach_edns_record(pkt, edns);
return 1;
}
void
qinfo_query_encode(sldns_buffer* pkt, struct query_info* qinfo)
{
uint16_t flags = 0;
sldns_buffer_clear(pkt);
log_assert(sldns_buffer_remaining(pkt) >= 12+255+4);
sldns_buffer_skip(pkt, 2);
sldns_buffer_write_u16(pkt, flags);
sldns_buffer_write_u16(pkt, 1);
sldns_buffer_write(pkt, "\000\000\000\000\000\000", 6);
sldns_buffer_write(pkt, qinfo->qname, qinfo->qname_len);
sldns_buffer_write_u16(pkt, qinfo->qtype);
sldns_buffer_write_u16(pkt, qinfo->qclass);
sldns_buffer_flip(pkt);
}
void
error_encode(sldns_buffer* buf, int r, struct query_info* qinfo,
uint16_t qid, uint16_t qflags, struct edns_data* edns)
{
uint16_t flags;
sldns_buffer_clear(buf);
sldns_buffer_write(buf, &qid, sizeof(uint16_t));
flags = (uint16_t)(BIT_QR | BIT_RA | r);
flags |= (qflags & (BIT_RD|BIT_CD));
sldns_buffer_write_u16(buf, flags);
if(qinfo) flags = 1;
else flags = 0;
sldns_buffer_write_u16(buf, flags);
flags = 0;
sldns_buffer_write(buf, &flags, sizeof(uint16_t));
sldns_buffer_write(buf, &flags, sizeof(uint16_t));
sldns_buffer_write(buf, &flags, sizeof(uint16_t));
if(qinfo) {
if(sldns_buffer_current(buf) == qinfo->qname)
sldns_buffer_skip(buf, (ssize_t)qinfo->qname_len);
else sldns_buffer_write(buf, qinfo->qname, qinfo->qname_len);
sldns_buffer_write_u16(buf, qinfo->qtype);
sldns_buffer_write_u16(buf, qinfo->qclass);
}
sldns_buffer_flip(buf);
if(edns) {
struct edns_data es = *edns;
es.edns_version = EDNS_ADVERTISED_VERSION;
es.udp_size = EDNS_ADVERTISED_SIZE;
es.ext_rcode = 0;
es.bits &= EDNS_DO;
if(sldns_buffer_limit(buf) + calc_edns_field_size(&es) >
edns->udp_size)
return;
attach_edns_record(buf, &es);
}
}