/* 
 * Copyright 2001 The Regents of the University of California 
 * All Rights Reserved 
 * 
 * Permission to use, copy, modify and distribute any part of this
 * iffinder software package for educational, research and non-profit
 * purposes, without fee, and without a written agreement is hereby
 * granted, provided that the above copyright notice, this paragraph
 * and the following paragraphs appear in all copies.
 * 
 * Those desiring to incorporate this into commercial products or use
 * for commercial purposes should contact the Technology Transfer
 * Office, University of California, San Diego, 9500 Gilman Drive, La
 * Jolla, CA 92093-0910, Ph: (858) 534-5815, FAX: (858) 534-7345.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY
 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
 * DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE SOFTWARE PROVIDED HEREIN IS ON AN "AS IS" BASIS, AND THE
 * UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
 * SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. THE UNIVERSITY
 * OF CALIFORNIA MAKES NO REPRESENTATIONS AND EXTENDS NO WARRANTIES
 * OF ANY KIND, EITHER IMPLIED OR EXPRESS, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
 * PARTICULAR PURPOSE, OR THAT THE USE OF THE SOFTWARE WILL NOT INFRINGE
 * ANY PATENT, TRADEMARK OR OTHER RIGHTS.
 * 
 * The iffinder software package is developed by Ken Keys at the
 * University of California, San Diego under the Cooperative Association
 * for Internet Data Analysis (CAIDA) Program.
 */

/* Note:  this only counts interfaces in the first column of input.
 * iffinder includes all new interfaces in the first column, so this works
 * the same as if it counted all interfaces.  But if you strip new interface
 * lines from iffinder's output, you can use this to count only previously
 * known (skitter) interfaces.
 */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include <signal.h>
#include <time.h>
#include <sys/types.h>
#include <sys/time.h>
#include <netinet/in.h>
/*#include <netinet/in_systm.h>*/
/*#include <netinet/ip.h>*/
#include <arpa/inet.h>
#include "hashtab.h"

#define INTERFACE_TABLE_SIZE	25013
#define HOST_TABLE_SIZE		10007

static int verbosity = 0;

typedef struct interface {
    struct in_addr addr;	/* IP address of interface */
    struct interface *node;	/* node to which this interface belongs */
    struct interface *next, *last;	/* next/last interface in node's list */
    int tcount;			/* # of ifaces on this node */
    int ocount;			/* # of ifaces on this node found by iffinder */
    char discover_how;		/* this interface was found by iffinder */
} interface_t;

static const char *argv0;
static hash_tab *interface_table;

typedef struct {
    int ifaces;
    int nodes;		/* includes single ifaces */
    int multinodes;	/* nodes with more than 1 interface */
    int multiifaces;	/* interfaces on nodes with more than 1 interface */
} stats_t;

static stats_t tstats, ostats;

static int eprintf(const char *fmt, ...)
{
    va_list ap;
    int result, err;

    err = errno;
    va_start(ap, fmt);
    result = vfprintf(stderr, fmt, ap);
    va_end(ap);
    errno = err;
    return result;
}

#define diag(level, args) \
	do { if (level <= verbosity) { eprintf args; } } while (0)


/*
 * functions for interface hash table
 */

static int cmp_if(const void *a, const void *b)
{
    return ((interface_t*)a)->addr.s_addr != ((interface_t*)b)->addr.s_addr;
}

static unsigned long key_if(const void *a)
{
    return ((interface_t*)a)->addr.s_addr;
}

static void sanity_check(interface_t *iface)
{
    if (iface->node == iface) {
	assert(iface->tcount > 0);
	assert(iface->ocount >= 0);
	assert((iface->tcount == 1) == !iface->next);
	assert((iface->tcount == 1) == !iface->last);
	assert(iface->tcount <= tstats.ifaces);
	assert(iface->ocount <= ostats.ifaces);
    } else {
	assert(iface->tcount == 0);
	assert(iface->ocount == 0);
	assert(!iface->last);
    }
    assert(ostats.multiifaces >= 0);
    assert(tstats.multiifaces >= 0);
    assert(ostats.multiifaces >= 2 * ostats.multinodes);
    assert(tstats.multiifaces >= 2 * tstats.multinodes);
    assert(ostats.multiifaces <= ostats.ifaces);
    assert(tstats.multiifaces <= tstats.ifaces);
}

static void merge_nodes(interface_t *node1, interface_t *node2)
{
    interface_t *iface;
    int tcount, ocount;

    if (node1 == node2)
	return;
    sanity_check(node1);
    sanity_check(node2);

    ocount = node1->ocount + node2->ocount;
    tcount = node1->tcount + node2->tcount;

    ostats.multinodes += (ocount >1) - (node1->ocount >1) - (node2->ocount >1);
    tstats.multinodes += (tcount >1) - (node1->tcount >1) - (node2->tcount >1);

    ostats.multiifaces += ocount > 1 ? ocount : 0
	- (node1->ocount > 1) ? node1->ocount : 0
	- (node2->ocount > 1) ? node2->ocount : 0;
    assert(ostats.multiifaces >= 0);
    tstats.multiifaces += tcount > 1 ? tcount : 0
	- (node1->tcount > 1) ? node1->tcount : 0
	- (node2->tcount > 1) ? node2->tcount : 0;
    assert(tstats.multiifaces >= 0);

    if (node1->ocount > 0 && node2->ocount > 0) ostats.nodes--;
    if (node1->tcount > 0 && node2->tcount > 0) tstats.nodes--;

    if (node1->tcount < node2->tcount) {
	iface = node1; iface = node2; node2 = iface;
    }
    for (iface = node2; iface; iface = iface->next) {
	assert(iface->node == node2);
	iface->node = node1;
    }
    *(node1->last ? &node1->last->next : &node1->next) = node2;
    node1->last = node2->last ? node2->last : node2;
    node2->last = NULL;
    node1->ocount = ocount;
    node1->tcount = tcount;
    node2->ocount = 0;
    node2->tcount = 0;

    sanity_check(node1);
    sanity_check(node2);
}

static interface_t *new_interface(struct in_addr addr, char discover_how)
{
    interface_t *interface;

    interface = malloc(sizeof(interface_t));
    if (!interface) return NULL;
    interface->addr = addr;
    interface->node = interface;
    interface->next = NULL;
    interface->last = NULL;
    interface->tcount = 1;
    interface->ocount = !discover_how;
    interface->discover_how = discover_how;
    ostats.nodes += !discover_how;
    tstats.nodes += 1;
    ostats.ifaces += !discover_how;
    tstats.ifaces += 1;
    add_hash_entry(interface_table, interface);
    return interface;
}

static interface_t *find_interface(struct in_addr addr)
{
    interface_t match;
    match.addr = addr;
    return find_hash_entry(interface_table, &match);
}

static interface_t *find_or_create_interface(struct in_addr addr, char discover_how,
    const char *filename, int linenum)
{
    interface_t *iface;
    if ((iface = find_interface(addr))) {
	if (!discover_how && iface->discover_how) {
	    iface->discover_how = 0;
	    ostats.ifaces++;
	    if (iface->ocount == 1) {
		ostats.multiifaces++;
		ostats.multinodes++;
	    }
	    ostats.multiifaces++;
	    iface->ocount++;
	}
    } else if (!(iface = new_interface(addr, discover_how))) {
	fprintf(stderr, "%s: %s, line %d: %s\n",
	    argv0, filename, linenum, strerror(errno));
    }
    return iface;
}

static int read_ip_file(const char *filename)
{
    FILE *file;
    char line[80], *p, *token;
    int linenum = 0, result = 0;
    char discover_how;
    struct in_addr addr, alias_id;
    interface_t *iface;

    if (!(file = fopen(filename, "r"))) {
	fprintf(stderr, "%s: %s: %s\n", argv0, filename, strerror(errno));
	return 0;
    }

    while (fgets(line, sizeof(line), file)) {
	linenum++;
	if (line[0] == '#') /* comment */
	    continue;
	p = line;
	token = strsep(&p, " \t\n");
	if (!*token) /* empty line */
	    continue;
	if (!inet_aton(token, &addr)) {
	    fprintf(stderr, "%s: %s, line %d: bad IP address '%s'\n",
		argv0, filename, linenum, token);
	    goto error;
	}

	while ((token = strsep(&p, " \t\n")) && !*token);
	if (token && isdigit(*token)) {
	    if (!inet_aton(token, &alias_id)) {
		fprintf(stderr, "%s: %s, line %d: bad node id '%s'\n",
		    argv0, filename, linenum, token);
		goto error;
	    }
	} else {
	    alias_id.s_addr = 0;
	}

	discover_how = 0;
	if (token) while ((token = strsep(&p, " \t\n")) && !*token);
	if (token) while ((token = strsep(&p, " \t\n")) && !*token);
	if (token) while ((token = strsep(&p, " \t\n")) && !*token);
	if (token) {
	    discover_how = (*token == '-') ? 0 : *token;
	}

	iface = find_or_create_interface(addr, discover_how, filename, linenum);
	if (!iface) goto error;

	if (alias_id.s_addr) {
	    interface_t *alias;
	    alias = find_or_create_interface(alias_id, 1, filename, linenum);
	    if (!alias) goto error;
	    merge_nodes(alias->node, iface->node);
	}
    }

    result = 1;
    fclose(file);
    return result;

error:
    exit(1);
}

static void dump_iface(interface_t *iface)
{
    printf("%-15s ", inet_ntoa(iface->addr));
    printf("%-15s ", iface->node->tcount > 1 ?
	inet_ntoa(iface->node->addr) : "-");
    printf("%c", iface->discover_how ? iface->discover_how : '-');
    putchar('\n');
}

static void dump_table(void)
{
    interface_t *node, *iface;

    printf("# %-13s %-15s %s\n", "address", "node_id", "discovr");

    init_hash_walk(interface_table);
    while ((node = next_hash_walk(interface_table))) {
	if (node->tcount <= 1) continue;
	assert (node->node == node);
	for (iface = node; iface; iface = iface->next) {
	    assert(iface->node == node);
	    dump_iface(iface);
	}
    }
    init_hash_walk(interface_table);
    while ((iface = next_hash_walk(interface_table))) {
	if (iface->node->tcount > 1) continue;
	assert(iface->node->tcount > 0);
	dump_iface(iface);
    }
}

static void usage_exit(const char *msg)
{
    if (msg) eprintf("%s\n", msg);
    eprintf("Usage:  %s [options] <ip_file>\n",
	argv0);
    eprintf("Options (with defaults in brackets):\n");
    eprintf("-v<V>   verbosity <V> [1]\n");
    exit(1);
}

static void dump_stats(const char *label, stats_t *s)
{
    printf("# Statistics for %s interfaces\n", label);
    printf("#   interfaces:             %8d\n", s->ifaces);
    printf("#     on nodes w/ >1 iface: %8d\n", s->multiifaces);
    printf("#     single:               %8d\n", s->ifaces - s->multiifaces);
    printf("#   nodes:                  %8d\n", s->nodes);
    printf("#     with >1 iface:        %8d\n", s->multinodes);
}

int main(int argc, char *argv[])
{
    int opt;

    argv0 = argv[0];

    /* command line options */
    while ((opt = getopt(argc, argv, "v:")) != -1) {
	switch (opt) {
	case 'v':
	    verbosity = atoi(optarg);
	    break;
	default:
	    usage_exit(NULL);
	}
    }
    if (optind >= argc) {
	usage_exit(NULL);
    }

    interface_table = init_hash_table("interface table", cmp_if, key_if,
	NULL, INTERFACE_TABLE_SIZE);

    while (optind < argc)
	read_ip_file(argv[optind++]);

    printf("# ifclosure revision:     %s\n", "$Revision: 1.5 $");
    printf("#\n");
    dump_stats("original", &ostats);
    printf("#\n");
    dump_stats("all", &tstats);
    printf("\n");

    dump_table();

    return 0;
}