/*
 * iterator/iter_fwd.c - iterative resolver module forward zones.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * 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 NLNET LABS 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
 * HOLDER 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.
 */

/**
 * \file
 *
 * This file contains functions to assist the iterator module.
 * Keep track of forward zones and config settings.
 */
#include "config.h"
#include "iterator/iter_fwd.h"
#include "iterator/iter_delegpt.h"
#include "util/log.h"
#include "util/config_file.h"
#include "util/net_help.h"
#include "util/data/dname.h"
#include "sldns/rrdef.h"
#include "sldns/str2wire.h"

int
fwd_cmp(const void* k1, const void* k2)
{
        int m;
        struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1;
        struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2;
        if(n1->dclass != n2->dclass) {
                if(n1->dclass < n2->dclass)
                        return -1;
                return 1;
        }
        return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 
                &m);
}

struct iter_forwards* 
forwards_create(void)
{
        struct iter_forwards* fwd = (struct iter_forwards*)calloc(1,
                sizeof(struct iter_forwards));
        if(!fwd)
                return NULL;
        lock_rw_init(&fwd->lock);
        return fwd;
}

static void fwd_zone_free(struct iter_forward_zone* n)
{
        if(!n) return;
        delegpt_free_mlc(n->dp);
        free(n->name);
        free(n);
}

static void delfwdnode(rbnode_type* n, void* ATTR_UNUSED(arg))
{
        struct iter_forward_zone* node = (struct iter_forward_zone*)n;
        fwd_zone_free(node);
}

static void fwd_del_tree(struct iter_forwards* fwd)
{
        if(fwd->tree)
                traverse_postorder(fwd->tree, &delfwdnode, NULL);
        free(fwd->tree);
}

void 
forwards_delete(struct iter_forwards* fwd)
{
        if(!fwd) 
                return;
        lock_rw_destroy(&fwd->lock);
        fwd_del_tree(fwd);
        free(fwd);
}

/** insert info into forward structure */
static int
forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 
        size_t nmlen, int nmlabs, struct delegpt* dp)
{
        struct iter_forward_zone* node = (struct iter_forward_zone*)malloc(
                sizeof(struct iter_forward_zone));
        if(!node) {
                delegpt_free_mlc(dp);
                return 0;
        }
        node->node.key = node;
        node->dclass = c;
        node->name = memdup(nm, nmlen);
        if(!node->name) {
                delegpt_free_mlc(dp);
                free(node);
                return 0;
        }
        node->namelen = nmlen;
        node->namelabs = nmlabs;
        node->dp = dp;
        if(!rbtree_insert(fwd->tree, &node->node)) {
                char buf[LDNS_MAX_DOMAINLEN];
                dname_str(nm, buf);
                log_err("duplicate forward zone %s ignored.", buf);
                delegpt_free_mlc(dp);
                free(node->name);
                free(node);
        }
        return 1;
}

static struct iter_forward_zone*
fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
{
        struct iter_forward_zone key;
        key.node.key = &key;
        key.dclass = c;
        key.name = nm;
        key.namelabs = dname_count_size_labels(nm, &key.namelen);
        return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
}

/** insert new info into forward structure given dp */
static int
forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
{
        return forwards_insert_data(fwd, c, dp->name, dp->namelen,
                dp->namelabs, dp);
}

/** initialise parent pointers in the tree */
static void
fwd_init_parents(struct iter_forwards* fwd)
{
        struct iter_forward_zone* node, *prev = NULL, *p;
        int m;
        RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
                node->parent = NULL;
                if(!prev || prev->dclass != node->dclass) {
                        prev = node;
                        continue;
                }
                (void)dname_lab_cmp(prev->name, prev->namelabs, node->name,
                        node->namelabs, &m); /* we know prev is smaller */
                /* sort order like: . com. bla.com. zwb.com. net. */
                /* find the previous, or parent-parent-parent */
                for(p = prev; p; p = p->parent)
                        /* looking for name with few labels, a parent */
                        if(p->namelabs <= m) {
                                /* ==: since prev matched m, this is closest*/
                                /* <: prev matches more, but is not a parent,
                                 * this one is a (grand)parent */
                                node->parent = p;
                                break;
                        }
                prev = node;
        }
}

/** set zone name */
static struct delegpt* 
read_fwds_name(struct config_stub* s)
{
        struct delegpt* dp;
        uint8_t* dname;
        size_t dname_len;
        if(!s->name) {
                log_err("forward zone without a name (use name \".\" to forward everything)");
                return NULL;
        }
        dname = sldns_str2wire_dname(s->name, &dname_len);
        if(!dname) {
                log_err("cannot parse forward zone name %s", s->name);
                return NULL;
        }
        if(!(dp=delegpt_create_mlc(dname))) {
                free(dname);
                log_err("out of memory");
                return NULL;
        }
        free(dname);
        return dp;
}

/** set fwd host names */
static int
read_fwds_host(struct config_stub* s, struct delegpt* dp)
{
        struct config_strlist* p;
        uint8_t* dname;
        char* tls_auth_name;
        int port;
        for(p = s->hosts; p; p = p->next) {
                log_assert(p->str);
                dname = authextstrtodname(p->str, &port, &tls_auth_name);
                if(!dname) {
                        log_err("cannot parse forward %s server name: '%s'", 
                                s->name, p->str);
                        return 0;
                }
#if ! defined(HAVE_SSL_SET1_HOST) && ! defined(HAVE_X509_VERIFY_PARAM_SET1_HOST)
                if(tls_auth_name)
                        log_err("no name verification functionality in "
                                "ssl library, ignored name for %s", p->str);
#endif
                if(!delegpt_add_ns_mlc(dp, dname, 0, tls_auth_name, port)) {
                        free(dname);
                        log_err("out of memory");
                        return 0;
                }
                free(dname);
        }
        return 1;
}

/** set fwd server addresses */
static int 
read_fwds_addr(struct config_stub* s, struct delegpt* dp)
{
        struct config_strlist* p;
        struct sockaddr_storage addr;
        socklen_t addrlen;
        char* tls_auth_name;
        for(p = s->addrs; p; p = p->next) {
                log_assert(p->str);
                if(!authextstrtoaddr(p->str, &addr, &addrlen, &tls_auth_name)) {
                        log_err("cannot parse forward %s ip address: '%s'", 
                                s->name, p->str);
                        return 0;
                }
#if ! defined(HAVE_SSL_SET1_HOST) && ! defined(HAVE_X509_VERIFY_PARAM_SET1_HOST)
                if(tls_auth_name)
                        log_err("no name verification functionality in "
                                "ssl library, ignored name for %s", p->str);
#endif
                if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0,
                        tls_auth_name, -1)) {
                        log_err("out of memory");
                        return 0;
                }
        }
        return 1;
}

/** read forwards config */
static int 
read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
{
        struct config_stub* s;
        for(s = cfg->forwards; s; s = s->next) {
                struct delegpt* dp;
                if(!(dp=read_fwds_name(s)))
                        return 0;
                if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) {
                        delegpt_free_mlc(dp);
                        return 0;
                }
                /* set flag that parent side NS information is included.
                 * Asking a (higher up) server on the internet is not useful */
                /* the flag is turned off for 'forward-first' so that the
                 * last resort will ask for parent-side NS record and thus
                 * fallback to the internet name servers on a failure */
                dp->has_parent_side_NS = (uint8_t)!s->isfirst;
                /* Do not cache if set. */
                dp->no_cache = s->no_cache;
                /* use SSL for queries to this forwarder */
                dp->ssl_upstream = (uint8_t)s->ssl_upstream;
                /* use TCP for queries to this forwarder */
                dp->tcp_upstream = (uint8_t)s->tcp_upstream;
                verbose(VERB_QUERY, "Forward zone server list:");
                delegpt_log(VERB_QUERY, dp);
                if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
                        return 0;
        }
        return 1;
}

/** insert a stub hole (if necessary) for stub name */
static int
fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
{
        struct iter_forward_zone key;
        key.node.key = &key;
        key.dclass = c;
        key.name = nm;
        key.namelabs = dname_count_size_labels(key.name, &key.namelen);
        return forwards_insert_data(fwd, key.dclass, key.name,
                key.namelen, key.namelabs, NULL);
}

/** make NULL entries for stubs */
static int
make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
{
        struct config_stub* s;
        uint8_t* dname;
        size_t dname_len;
        for(s = cfg->stubs; s; s = s->next) {
                if(!s->name) continue;
                dname = sldns_str2wire_dname(s->name, &dname_len);
                if(!dname) {
                        log_err("cannot parse stub name '%s'", s->name);
                        return 0;
                }
                if(fwd_zone_find(fwd, LDNS_RR_CLASS_IN, dname) != NULL) {
                        /* Already a forward zone there. */
                        free(dname);
                        continue;
                }
                if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
                        free(dname);
                        log_err("out of memory");
                        return 0;
                }
                free(dname);
        }
        return 1;
}

/** make NULL entries for auths */
static int
make_auth_holes(struct iter_forwards* fwd, struct config_file* cfg)
{
        struct config_auth* a;
        uint8_t* dname;
        size_t dname_len;
        for(a = cfg->auths; a; a = a->next) {
                if(!a->name) continue;
                dname = sldns_str2wire_dname(a->name, &dname_len);
                if(!dname) {
                        log_err("cannot parse auth name '%s'", a->name);
                        return 0;
                }
                if(fwd_zone_find(fwd, LDNS_RR_CLASS_IN, dname) != NULL) {
                        /* Already a forward zone there. */
                        free(dname);
                        continue;
                }
                if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
                        free(dname);
                        log_err("out of memory");
                        return 0;
                }
                free(dname);
        }
        return 1;
}

int 
forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
{
        if(fwd->tree) {
                lock_unprotect(&fwd->lock, fwd->tree);
        }
        fwd_del_tree(fwd);
        fwd->tree = rbtree_create(fwd_cmp);
        if(!fwd->tree)
                return 0;
        lock_protect(&fwd->lock, fwd->tree, sizeof(*fwd->tree));

        lock_rw_wrlock(&fwd->lock);
        /* read forward zones */
        if(!read_forwards(fwd, cfg)) {
                lock_rw_unlock(&fwd->lock);
                return 0;
        }
        if(!make_stub_holes(fwd, cfg)) {
                lock_rw_unlock(&fwd->lock);
                return 0;
        }
        /* TODO: Now we punch holes for auth zones as well so that in
         *       iterator:forward_request() we see the configured
         *       delegation point, but code flow/naming is hard to follow.
         *       Consider having a single tree with configured
         *       delegation points for all categories
         *       (stubs, forwards, auths). */
        if(!make_auth_holes(fwd, cfg)) {
                lock_rw_unlock(&fwd->lock);
                return 0;
        }
        fwd_init_parents(fwd);
        lock_rw_unlock(&fwd->lock);
        return 1;
}

struct delegpt* 
forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass,
        int nolock)
{
        struct iter_forward_zone* res;
        struct iter_forward_zone key;
        int has_dp;
        key.node.key = &key;
        key.dclass = qclass;
        key.name = qname;
        key.namelabs = dname_count_size_labels(qname, &key.namelen);
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_rdlock(&fwd->lock); }
        res = (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
        has_dp = res && res->dp;
        if(!has_dp && !nolock) { lock_rw_unlock(&fwd->lock); }
        return has_dp?res->dp:NULL;
}

struct delegpt* 
forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass,
        int nolock)
{
        /* lookup the forward zone in the tree */
        rbnode_type* res = NULL;
        struct iter_forward_zone *result;
        struct iter_forward_zone key;
        int has_dp;
        key.node.key = &key;
        key.dclass = qclass;
        key.name = qname;
        key.namelabs = dname_count_size_labels(qname, &key.namelen);
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_rdlock(&fwd->lock); }
        if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
                /* exact */
                result = (struct iter_forward_zone*)res;
        } else {
                /* smaller element (or no element) */
                int m;
                result = (struct iter_forward_zone*)res;
                if(!result || result->dclass != qclass) {
                        if(!nolock) { lock_rw_unlock(&fwd->lock); }
                        return NULL;
                }
                /* count number of labels matched */
                (void)dname_lab_cmp(result->name, result->namelabs, key.name,
                        key.namelabs, &m);
                while(result) { /* go up until qname is subdomain of stub */
                        if(result->namelabs <= m)
                                break;
                        result = result->parent;
                }
        }
        has_dp = result && result->dp;
        if(!has_dp && !nolock) { lock_rw_unlock(&fwd->lock); }
        return has_dp?result->dp:NULL;
}

struct delegpt* 
forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass, int nolock)
{
        uint8_t root = 0;
        return forwards_lookup(fwd, &root, qclass, nolock);
}

/* Finds next root item in forwards lookup tree.
 * Caller needs to handle locking of the forwards structure. */
static int
next_root_locked(struct iter_forwards* fwd, uint16_t* dclass)
{
        struct iter_forward_zone key;
        rbnode_type* n;
        struct iter_forward_zone* p;
        if(*dclass == 0) {
                /* first root item is first item in tree */
                n = rbtree_first(fwd->tree);
                if(n == RBTREE_NULL)
                        return 0;
                p = (struct iter_forward_zone*)n;
                if(dname_is_root(p->name)) {
                        *dclass = p->dclass;
                        return 1;
                }
                /* root not first item? search for higher items */
                *dclass = p->dclass + 1;
                return next_root_locked(fwd, dclass);
        }
        /* find class n in tree, we may get a direct hit, or if we don't
         * this is the last item of the previous class so rbtree_next() takes
         * us to the next root (if any) */
        key.node.key = &key;
        key.name = (uint8_t*)"\000";
        key.namelen = 1;
        key.namelabs = 0;
        key.dclass = *dclass;
        n = NULL;
        if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
                /* exact */
                return 1;
        } else {
                /* smaller element */
                if(!n || n == RBTREE_NULL)
                        return 0; /* nothing found */
                n = rbtree_next(n);
                if(n == RBTREE_NULL)
                        return 0; /* no higher */
                p = (struct iter_forward_zone*)n;
                if(dname_is_root(p->name)) {
                        *dclass = p->dclass;
                        return 1;
                }
                /* not a root node, return next higher item */
                *dclass = p->dclass+1;
                return next_root_locked(fwd, dclass);
        }
}

int
forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass, int nolock)
{
        int ret;
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_rdlock(&fwd->lock); }
        ret = next_root_locked(fwd, dclass);
        if(!nolock) { lock_rw_unlock(&fwd->lock); }
        return ret;
}

size_t 
forwards_get_mem(struct iter_forwards* fwd)
{
        struct iter_forward_zone* p;
        size_t s;
        if(!fwd)
                return 0;
        lock_rw_rdlock(&fwd->lock);
        s = sizeof(*fwd) + sizeof(*fwd->tree);
        RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
                s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
        }
        lock_rw_unlock(&fwd->lock);
        return s;
}

int 
forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp,
        int nolock)
{
        struct iter_forward_zone *z;
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_wrlock(&fwd->lock); }
        if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
                (void)rbtree_delete(fwd->tree, &z->node);
                fwd_zone_free(z);
        }
        if(!forwards_insert(fwd, c, dp)) {
                if(!nolock) { lock_rw_unlock(&fwd->lock); }
                return 0;
        }
        fwd_init_parents(fwd);
        if(!nolock) { lock_rw_unlock(&fwd->lock); }
        return 1;
}

void 
forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
        int nolock)
{
        struct iter_forward_zone *z;
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_wrlock(&fwd->lock); }
        if(!(z=fwd_zone_find(fwd, c, nm))) {
                if(!nolock) { lock_rw_unlock(&fwd->lock); }
                return; /* nothing to do */
        }
        (void)rbtree_delete(fwd->tree, &z->node);
        fwd_zone_free(z);
        fwd_init_parents(fwd);
        if(!nolock) { lock_rw_unlock(&fwd->lock); }
}

int
forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
        int nolock)
{
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_wrlock(&fwd->lock); }
        if(fwd_zone_find(fwd, c, nm) != NULL) {
                if(!nolock) { lock_rw_unlock(&fwd->lock); }
                return 1; /* already a stub zone there */
        }
        if(!fwd_add_stub_hole(fwd, c, nm)) {
                if(!nolock) { lock_rw_unlock(&fwd->lock); }
                return 0;
        }
        fwd_init_parents(fwd);
        if(!nolock) { lock_rw_unlock(&fwd->lock); }
        return 1;
}

void
forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c,
        uint8_t* nm, int nolock)
{
        struct iter_forward_zone *z;
        /* lock_() calls are macros that could be nothing, surround in {} */
        if(!nolock) { lock_rw_wrlock(&fwd->lock); }
        if(!(z=fwd_zone_find(fwd, c, nm))) {
                if(!nolock) { lock_rw_unlock(&fwd->lock); }
                return; /* nothing to do */
        }
        if(z->dp != NULL) {
                if(!nolock) { lock_rw_unlock(&fwd->lock); }
                return; /* not a stub hole */
        }
        (void)rbtree_delete(fwd->tree, &z->node);
        fwd_zone_free(z);
        fwd_init_parents(fwd);
        if(!nolock) { lock_rw_unlock(&fwd->lock); }
}

void
forwards_swap_tree(struct iter_forwards* fwd, struct iter_forwards* data)
{
        rbtree_type* oldtree = fwd->tree;
        if(oldtree) {
                lock_unprotect(&fwd->lock, oldtree);
        }
        if(data->tree) {
                lock_unprotect(&data->lock, data->tree);
        }
        fwd->tree = data->tree;
        data->tree = oldtree;
        lock_protect(&fwd->lock, fwd->tree, sizeof(*fwd->tree));
        lock_protect(&data->lock, data->tree, sizeof(*data->tree));
}