//returns true if an exact matching rule is found
func (g *GCEBackend) handleMatchingRoute(subnet string) (bool, error) {
	matchingRoute, err := g.getRoute(subnet)
	if err != nil {
		if apiError, ok := err.(*googleapi.Error); ok {
			if apiError.Code != 404 {
				return false, fmt.Errorf("error getting the route err: %v", err)
			}
			return false, nil
		}
		return false, fmt.Errorf("error getting googleapi: %v", err)
	}

	if matchingRoute.NextHopInstance == g.gceInstance.SelfLink {
		log.Info("Exact pre-existing route found")
		return true, nil
	}

	log.Info("Deleting conflicting route")
	operation, err := g.deleteRoute(subnet)
	if err != nil {
		return false, fmt.Errorf("error deleting conflicting route : %v", err)
	}

	err = g.pollOperationStatus(operation.Name)
	if err != nil {
		return false, fmt.Errorf("delete operation failed: %v", err)
	}

	return false, nil

}

func (be *AwsVpcBackend) detectRouteTableID(instanceID string, ec2c *ec2.EC2) (string, error) {
	instancesInput := &ec2.DescribeInstancesInput{
		InstanceIds: []*string{&instanceID},
	}

	resp, err := ec2c.DescribeInstances(instancesInput)
	if err != nil {
		return "", fmt.Errorf("error getting instance info: %v", err)
	}

	if len(resp.Reservations) == 0 {
		return "", fmt.Errorf("no reservations found")
	}

	if len(resp.Reservations[0].Instances) == 0 {
		return "", fmt.Errorf("no matching instance found with id: %v", instanceID)
	}

	subnetID := resp.Reservations[0].Instances[0].SubnetId
	vpcID := resp.Reservations[0].Instances[0].VpcId

	log.Info("Subnet-ID: ", *subnetID)
	log.Info("VPC-ID: ", *vpcID)

	filter := newFilter()
	filter.Add("association.subnet-id", *subnetID)

	routeTablesInput := &ec2.DescribeRouteTablesInput{
		Filters: filter,
	}

	res, err := ec2c.DescribeRouteTables(routeTablesInput)
	if err != nil {
		return "", fmt.Errorf("error describing routeTables for subnetID %s: %v", *subnetID, err)
	}

	if len(res.RouteTables) != 0 {
		return *res.RouteTables[0].RouteTableId, nil
	}

	filter = newFilter()
	filter.Add("association.main", "true")
	filter.Add("vpc-id", *vpcID)

	routeTablesInput = &ec2.DescribeRouteTablesInput{
		Filters: filter,
	}

	res, err = ec2c.DescribeRouteTables(routeTablesInput)
	if err != nil {
		log.Info("error describing route tables: ", err)
	}

	if len(res.RouteTables) == 0 {
		return "", fmt.Errorf("main route table not found")
	}

	return *res.RouteTables[0].RouteTableId, nil
}

func (m *AwsVpcBackend) detectRouteTableID(instanceID string, ec2c *ec2.EC2) error {
	resp, err := ec2c.Instances([]string{instanceID}, nil)
	if err != nil {
		return fmt.Errorf("error getting instance info: %v", err)
	}

	if len(resp.Reservations) == 0 {
		return fmt.Errorf("no reservations found")
	}

	if len(resp.Reservations[0].Instances) == 0 {
		return fmt.Errorf("no matching instance found with id: %v", instanceID)
	}

	subnetID := resp.Reservations[0].Instances[0].SubnetId
	vpcID := resp.Reservations[0].Instances[0].VpcId

	log.Info("Subnet-ID: ", subnetID)
	log.Info("VPC-ID: ", vpcID)

	filter := ec2.NewFilter()
	filter.Add("association.subnet-id", subnetID)

	res, err := ec2c.DescribeRouteTables(nil, filter)
	if err != nil {
		return fmt.Errorf("error describing routeTables for subnetID %s: %v", subnetID, err)
	}

	if len(res.RouteTables) != 0 {
		m.cfg.RouteTableID = res.RouteTables[0].RouteTableId
		return nil
	}

	filter = ec2.NewFilter()
	filter.Add("association.main", "true")
	filter.Add("vpc-id", vpcID)

	res, err = ec2c.DescribeRouteTables(nil, filter)
	if err != nil {
		log.Info("error describing route tables: ", err)
	}

	if len(res.RouteTables) == 0 {
		return fmt.Errorf("main route table not found")
	}

	m.cfg.RouteTableID = res.RouteTables[0].RouteTableId

	return nil
}

func main() {
	// glog will log to tmp files by default. override so all entries
	// can flow into journald (if running under systemd)
	flag.Set("logtostderr", "true")

	// now parse command line args
	flag.Parse()

	if opts.help {
		fmt.Fprintf(os.Stderr, "Usage: %s [OPTION]...\n", os.Args[0])
		flag.PrintDefaults()
		os.Exit(0)
	}

	if opts.version {
		fmt.Fprintln(os.Stderr, Version)
		os.Exit(0)
	}

	be, err := newBackend()
	if err != nil {
		log.Info(err)
		os.Exit(1)
	}

	// Register for SIGINT and SIGTERM and wait for one of them to arrive
	log.Info("Installing signal handlers")
	sigs := make(chan os.Signal, 1)
	signal.Notify(sigs, os.Interrupt, syscall.SIGTERM)

	exit := make(chan int)
	go run(be, exit)

	for {
		select {
		case <-sigs:
			// unregister to get default OS nuke behaviour in case we don't exit cleanly
			signal.Stop(sigs)

			log.Info("Exiting...")
			be.Stop()

		case code := <-exit:
			log.Infof("%s mode exited", be.Name())
			os.Exit(code)
		}
	}
}

func (m *EtcdManager) AcquireLease(ctx context.Context, network string, attrs *LeaseAttrs) (*Lease, error) {
	config, err := m.GetNetworkConfig(ctx, network)
	if err != nil {
		return nil, err
	}

	for {
		l, err := m.acquireLeaseOnce(ctx, network, config, attrs)
		switch {
		case err == nil:
			log.Info("Subnet lease acquired: ", l.Subnet)
			return l, nil

		case err == context.Canceled, err == context.DeadlineExceeded:
			return nil, err

		default:
			log.Error("Failed to acquire subnet: ", err)
		}

		select {
		case <-time.After(time.Second):

		case <-ctx.Done():
			return nil, ctx.Err()
		}
	}
}

func setupIpMasq(ipn ip.IP4Net, iface string) error {
	ipt, err := ip.NewIPTables()
	if err != nil {
		return fmt.Errorf("failed to setup IP Masquerade. iptables was not found")
	}

	err = ipt.ClearChain("nat", "FLANNEL")
	if err != nil {
		return fmt.Errorf("Failed to create/clear FLANNEL chain in NAT table: %v", err)
	}

	rules := [][]string{
		// This rule makes sure we don't NAT traffic within overlay network (e.g. coming out of docker0)
		[]string{"FLANNEL", "-d", ipn.String(), "-j", "ACCEPT"},
		// This rule makes sure we don't NAT multicast traffic within overlay network
		[]string{"FLANNEL", "-d", "224.0.0.0/4", "-j", "ACCEPT"},
		// This rule will NAT everything originating from our overlay network and
		[]string{"FLANNEL", "!", "-o", iface, "-j", "MASQUERADE"},
		// This rule will take everything coming from overlay and sent it to FLANNEL chain
		[]string{"POSTROUTING", "-s", ipn.String(), "-j", "FLANNEL"},
	}

	for _, args := range rules {
		log.Info("Adding iptables rule: ", strings.Join(args, " "))

		err = ipt.AppendUnique("nat", args...)
		if err != nil {
			return fmt.Errorf("Failed to insert IP masquerade rule: %v", err)
		}
	}

	return nil
}

func (m *UdpBackend) Run(ctx context.Context) {
	// one for each goroutine below
	wg := sync.WaitGroup{}

	wg.Add(1)
	go func() {
		runCProxy(m.tun, m.conn, m.ctl2, m.tunNet.IP, m.mtu)
		wg.Done()
	}()

	log.Info("Watching for new subnet leases")

	evts := make(chan []subnet.Event)

	wg.Add(1)
	go func() {
		subnet.WatchLeases(ctx, m.sm, m.network, m.lease, evts)
		wg.Done()
	}()

	for {
		select {
		case evtBatch := <-evts:
			m.processSubnetEvents(evtBatch)

		case <-ctx.Done():
			stopProxy(m.ctl)
			break
		}
	}

	wg.Wait()
}

func lookupIface() (*net.Interface, net.IP, error) {
	var iface *net.Interface
	var ipaddr net.IP
	var err error

	if len(opts.iface) > 0 {
		if ipaddr = net.ParseIP(opts.iface); ipaddr != nil {
			iface, err = ip.GetInterfaceByIP(ipaddr)
			if err != nil {
				return nil, nil, fmt.Errorf("Error looking up interface %s: %s", opts.iface, err)
			}
		} else {
			iface, err = net.InterfaceByName(opts.iface)
			if err != nil {
				return nil, nil, fmt.Errorf("Error looking up interface %s: %s", opts.iface, err)
			}
		}
	} else {
		log.Info("Determining IP address of default interface")
		if iface, err = ip.GetDefaultGatewayIface(); err != nil {
			return nil, nil, fmt.Errorf("Failed to get default interface: %s", err)
		}
	}

	if ipaddr == nil {
		ipaddr, err = ip.GetIfaceIP4Addr(iface)
		if err != nil {
			return nil, nil, fmt.Errorf("Failed to find IPv4 address for interface %s", iface.Name)
		}
	}

	return iface, ipaddr, nil
}

func (sm *SubnetManager) AcquireLease(extIP ip.IP4, data interface{}, cancel chan bool) (ip.IP4Net, error) {
	dataBytes, err := json.Marshal(data)
	if err != nil {
		return ip.IP4Net{}, err
	}

	var sn ip.IP4Net
	for {
		sn, err = sm.acquireLeaseOnce(extIP, string(dataBytes), cancel)
		switch {
		case err == nil:
			log.Info("Subnet lease acquired: ", sn)
			return sn, nil

		case err == task.ErrCanceled:
			return ip.IP4Net{}, err

		default:
			log.Error("Failed to acquire subnet: ", err)
		}

		select {
		case <-time.After(time.Second):

		case <-cancel:
			return ip.IP4Net{}, task.ErrCanceled
		}
	}
}

func (rb *HostgwBackend) Run() {
	rb.wg.Add(1)
	go func() {
		subnet.LeaseRenewer(rb.ctx, rb.sm, rb.network, rb.lease)
		rb.wg.Done()
	}()

	log.Info("Watching for new subnet leases")
	evts := make(chan []subnet.Event)
	rb.wg.Add(1)
	go func() {
		subnet.WatchLeases(rb.ctx, rb.sm, rb.network, rb.lease, evts)
		rb.wg.Done()
	}()

	rb.rl = make([]netlink.Route, 0, 10)
	rb.wg.Add(1)
	go func() {
		rb.routeCheck(rb.ctx)
		rb.wg.Done()
	}()

	defer rb.wg.Wait()

	for {
		select {
		case evtBatch := <-evts:
			rb.handleSubnetEvents(evtBatch)

		case <-rb.ctx.Done():
			return
		}
	}
}

func (n *network) Run(ctx context.Context) {
	wg := sync.WaitGroup{}

	log.Info("Watching for new subnet leases")
	evts := make(chan []subnet.Event)
	wg.Add(1)
	go func() {
		subnet.WatchLeases(ctx, n.sm, n.name, n.lease, evts)
		wg.Done()
	}()

	n.rl = make([]netlink.Route, 0, 10)
	wg.Add(1)
	go func() {
		n.routeCheck(ctx)
		wg.Done()
	}()

	defer wg.Wait()

	for {
		select {
		case evtBatch := <-evts:
			n.handleSubnetEvents(evtBatch)

		case <-ctx.Done():
			return
		}
	}
}

func setupIPMasq(ipn ip.IP4Net) error {
	ipt, err := iptables.New()
	if err != nil {
		return fmt.Errorf("failed to setup IP Masquerade. iptables was not found")
	}

	err = ipt.ClearChain("nat", "FLANNEL")
	if err != nil {
		return fmt.Errorf("Failed to create/clear FLANNEL chain in NAT table: %v", err)
	}

	rules := [][]string{
		// This rule makes sure we don't NAT traffic within overlay network (e.g. coming out of docker0)
		{"FLANNEL", "-d", ipn.String(), "-j", "ACCEPT"},
		// NAT if it's not multicast traffic
		{"FLANNEL", "!", "-d", "224.0.0.0/4", "-j", "MASQUERADE"},
		// This rule will take everything coming from overlay and send it to FLANNEL chain
		{"POSTROUTING", "-s", ipn.String(), "-j", "FLANNEL"},
		// Masquerade anything headed towards flannel from the host
		{"POSTROUTING", "!", "-s", ipn.String(), "-d", ipn.String(), "-j", "MASQUERADE"},
	}

	for _, rule := range rules {
		log.Info("Adding iptables rule: ", strings.Join(rule, " "))
		chain := rule[0]
		args := rule[1:len(rule)]

		err = ipt.AppendUnique("nat", chain, args...)
		if err != nil {
			return fmt.Errorf("Failed to insert IP masquerade rule: %v", err)
		}
	}

	return nil
}

func (vb *VXLANBackend) Run() {
	vb.wg.Add(1)
	go func() {
		subnet.LeaseRenewer(vb.ctx, vb.sm, vb.network, vb.lease)
		log.Info("LeaseRenewer exited")
		vb.wg.Done()
	}()

	log.Info("Watching for L3 misses")
	misses := make(chan *netlink.Neigh, 100)
	// Unfrtunately MonitorMisses does not take a cancel channel
	// as there's no wait to interrupt netlink socket recv
	go vb.dev.MonitorMisses(misses)

	log.Info("Watching for new subnet leases")
	evts := make(chan []subnet.Event)
	vb.wg.Add(1)
	go func() {
		subnet.WatchLeases(vb.ctx, vb.sm, vb.network, vb.lease, evts)
		log.Info("WatchLeases exited")
		vb.wg.Done()
	}()

	defer vb.wg.Wait()
	initialEvtsBatch := <-evts
	for {
		err := vb.handleInitialSubnetEvents(initialEvtsBatch)
		if err == nil {
			break
		}
		log.Error(err, " About to retry")
		time.Sleep(time.Second)
	}

	for {
		select {
		case miss := <-misses:
			vb.handleMiss(miss)

		case evtBatch := <-evts:
			vb.handleSubnetEvents(evtBatch)

		case <-vb.ctx.Done():
			return
		}
	}
}

func ensureExpiration(resp *etcd.Response, ttl uint64) {
	if resp.Node.Expiration == nil {
		// should not be but calc it ourselves in this case
		log.Info("Expiration field missing on etcd response, calculating locally")
		exp := time.Now().Add(time.Duration(ttl) * time.Second)
		resp.Node.Expiration = &exp
	}
}

func lookupExtIface(ifname string) (*backend.ExternalInterface, error) {
	var iface *net.Interface
	var iaddr net.IP
	var err error

	if len(ifname) > 0 {
		if iaddr = net.ParseIP(ifname); iaddr != nil {
			iface, err = ip.GetInterfaceByIP(iaddr)
			if err != nil {
				return nil, fmt.Errorf("error looking up interface %s: %s", ifname, err)
			}
		} else {
			iface, err = net.InterfaceByName(ifname)
			if err != nil {
				return nil, fmt.Errorf("error looking up interface %s: %s", ifname, err)
			}
		}
	} else {
		log.Info("Determining IP address of default interface")
		if iface, err = ip.GetDefaultGatewayIface(); err != nil {
			return nil, fmt.Errorf("failed to get default interface: %s", err)
		}
	}

	if iaddr == nil {
		iaddr, err = ip.GetIfaceIP4Addr(iface)
		if err != nil {
			return nil, fmt.Errorf("failed to find IPv4 address for interface %s", iface.Name)
		}
	}

	if iface.MTU == 0 {
		return nil, fmt.Errorf("failed to determine MTU for %s interface", iaddr)
	}

	var eaddr net.IP

	if len(opts.publicIP) > 0 {
		eaddr = net.ParseIP(opts.publicIP)
		if eaddr == nil {
			return nil, fmt.Errorf("invalid public IP address", opts.publicIP)
		}
	}

	if eaddr == nil {
		eaddr = iaddr
	}

	log.Infof("Using %s as external interface", iaddr)
	log.Infof("Using %s as external endpoint", eaddr)

	return &backend.ExternalInterface{
		Iface:     iface,
		IfaceAddr: iaddr,
		ExtAddr:   eaddr,
	}, nil
}

func (m *UdpBackend) processSubnetEvents(batch []subnet.Event) {
	for _, evt := range batch {
		switch evt.Type {
		case subnet.EventAdded:
			log.Info("Subnet added: ", evt.Lease.Subnet)

			setRoute(m.ctl, evt.Lease.Subnet, evt.Lease.Attrs.PublicIP, m.cfg.Port)

		case subnet.EventRemoved:
			log.Info("Subnet removed: ", evt.Lease.Subnet)

			removeRoute(m.ctl, evt.Lease.Subnet)

		default:
			log.Error("Internal error: unknown event type: ", int(evt.Type))
		}
	}
}

func (vb *VXLANBackend) handleSubnetEvents(batch []subnet.Event) {
	for _, evt := range batch {
		switch evt.Type {
		case subnet.EventAdded:
			log.Info("Subnet added: ", evt.Lease.Subnet)

			if evt.Lease.Attrs.BackendType != "vxlan" {
				log.Warningf("Ignoring non-vxlan subnet: type=%v", evt.Lease.Attrs.BackendType)
				continue
			}

			var attrs vxlanLeaseAttrs
			if err := json.Unmarshal(evt.Lease.Attrs.BackendData, &attrs); err != nil {
				log.Error("Error decoding subnet lease JSON: ", err)
				continue
			}
			vb.rts.set(evt.Lease.Subnet, net.HardwareAddr(attrs.VtepMAC))
			vb.dev.AddL2(neigh{IP: evt.Lease.Attrs.PublicIP, MAC: net.HardwareAddr(attrs.VtepMAC)})

		case subnet.EventRemoved:
			log.Info("Subnet removed: ", evt.Lease.Subnet)

			if evt.Lease.Attrs.BackendType != "vxlan" {
				log.Warningf("Ignoring non-vxlan subnet: type=%v", evt.Lease.Attrs.BackendType)
				continue
			}

			var attrs vxlanLeaseAttrs
			if err := json.Unmarshal(evt.Lease.Attrs.BackendData, &attrs); err != nil {
				log.Error("Error decoding subnet lease JSON: ", err)
				continue
			}

			if len(attrs.VtepMAC) > 0 {
				vb.dev.DelL2(neigh{IP: evt.Lease.Attrs.PublicIP, MAC: net.HardwareAddr(attrs.VtepMAC)})
			}
			vb.rts.remove(evt.Lease.Subnet)

		default:
			log.Error("Internal error: unknown event type: ", int(evt.Type))
		}
	}
}

func (vb *VXLANBackend) handleMiss(miss *netlink.Neigh) {
	switch {
	case len(miss.IP) == 0 && len(miss.HardwareAddr) == 0:
		log.Info("Ignoring nil miss")

	case len(miss.HardwareAddr) == 0:
		vb.handleL3Miss(miss)

	default:
		log.Infof("Ignoring not a miss: %v, %v", miss.HardwareAddr, miss.IP)
	}
}

func (rb *HostgwBackend) handleSubnetEvents(batch []subnet.Event) {
	for _, evt := range batch {
		switch evt.Type {
		case subnet.SubnetAdded:
			log.Infof("Subnet added: %v via %v", evt.Lease.Subnet, evt.Lease.Attrs.PublicIP)

			if evt.Lease.Attrs.BackendType != "host-gw" {
				log.Warningf("Ignoring non-host-gw subnet: type=%v", evt.Lease.Attrs.BackendType)
				continue
			}

			route := netlink.Route{
				Dst:       evt.Lease.Subnet.ToIPNet(),
				Gw:        evt.Lease.Attrs.PublicIP.ToIP(),
				LinkIndex: rb.extIface.Index,
			}
			if rb.extIaddr.Equal(route.Gw) {
				continue
			}
			if err := netlink.RouteAdd(&route); err != nil {
				log.Errorf("Error adding route to %v via %v: %v", evt.Lease.Subnet, evt.Lease.Attrs.PublicIP, err)
				continue
			}
			rb.addToRouteList(route)

		case subnet.SubnetRemoved:
			log.Info("Subnet removed: ", evt.Lease.Subnet)

			if evt.Lease.Attrs.BackendType != "host-gw" {
				log.Warningf("Ignoring non-host-gw subnet: type=%v", evt.Lease.Attrs.BackendType)
				continue
			}

			route := netlink.Route{
				Dst:       evt.Lease.Subnet.ToIPNet(),
				Gw:        evt.Lease.Attrs.PublicIP.ToIP(),
				LinkIndex: rb.extIface.Index,
			}
			if err := netlink.RouteDel(&route); err != nil {
				log.Errorf("Error deleting route to %v: %v", evt.Lease.Subnet, err)
				continue
			}
			rb.removeFromRouteList(route)

		default:
			log.Error("Internal error: unknown event type: ", int(evt.Type))
		}
	}
}

func (vb *VXLANBackend) handleL3Miss(miss *netlink.Neigh) {
	log.Infof("L3 miss: %v", miss.IP)

	rt := vb.rts.findByNetwork(ip.FromIP(miss.IP))
	if rt == nil {
		log.Infof("Route for %v not found", miss.IP)
		return
	}

	if err := vb.dev.AddL3(neigh{IP: ip.FromIP(miss.IP), MAC: rt.vtepMAC}); err != nil {
		log.Errorf("AddL3 failed: %v", err)
	} else {
		log.Info("AddL3 succeeded")
	}
}