func (n *network) checkSubnetExistInRoutes() {
	routeList, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err == nil {
		for _, route := range n.rl {
			exist := false
			for _, r := range routeList {
				if r.Dst == nil {
					continue
				}
				if routeEqual(r, route) {
					exist = true
					break
				}
			}
			if !exist {
				if err := netlink.RouteAdd(&route); err != nil {
					if nerr, ok := err.(net.Error); !ok {
						log.Errorf("Error recovering route to %v: %v, %v", route.Dst, route.Gw, nerr)
					}
					continue
				} else {
					log.Infof("Route recovered %v : %v", route.Dst, route.Gw)
				}
			}
		}
	}
}

/* List routes belonging to interface name(s) @ifs */
func List(ifs ...string) {
	var ifmap = make(map[int]string)
	for _, iface := range ifs {
		link, err := netlink.LinkByName(iface)
		if err != nil {
			log.Fatalf("failed to look up interface %s: %s", iface, err)
		}
		ifmap[link.Attrs().Index] = iface
	}

	routes, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		log.Fatalf("failed to list routes: %s", err)
	}
	log.Printf("routes through %s:", strings.Join(ifs, ", "))
	for _, rt := range routes {
		/*
		 *  FIXME: netlink.RouteList() has a bug - the 'link' argument has no effect.
		 *         Hence filtering manually here; maybe open an issue on github.
		 */
		if dev, ok := ifmap[rt.LinkIndex]; ok {
			if rt.Src != nil {
				log.Printf("%-10s %s -> %s\n", dev+":", rt.Src, rt.Dst)
			} else {
				log.Printf("%-10s %s\n", dev+":", rt.Dst)
			}
		}
	}
}

// Wait for an interface to come up and have a route added to the multicast subnet.
// This matches the behaviour in 'weave attach', which is the only context in which
// we expect this to be called.  If you change one, change the other to match.
func EnsureInterfaceAndMcastRoute(ifaceName string) (*net.Interface, error) {
	iface, err := ensureInterface(ifaceName)
	if err != nil {
		return nil, err
	}
	ch := make(chan netlink.RouteUpdate)
	done := make(chan struct{})
	defer close(done)
	if err := netlink.RouteSubscribe(ch, done); err != nil {
		return nil, err
	}
	dest := net.IPv4(224, 0, 0, 0)
	check := func(route netlink.Route) bool {
		return route.LinkIndex == iface.Index && route.Dst != nil && route.Dst.IP.Equal(dest)
	}
	// check for currently-existing route after subscribing, to avoid race
	routes, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		return nil, err
	}
	for _, route := range routes {
		if check(route) {
			return iface, nil
		}
	}
	for update := range ch {
		if check(update.Route) {
			return iface, nil
		}
	}
	// should never get here
	return iface, nil
}

// Remove routes with netlink syscalls with a scope of:
// RT_SCOPE_LINK = 0xfd (253)
// RT_SCOPE_UNIVERSE = 0x0 (0)
func cleanExistingRoutes(ifaceStr string) error {
	iface, err := netlink.LinkByName(ifaceStr)
	ipvlanParentIface, err := netlink.LinkByName(ifaceStr)
	if err != nil {
		log.Errorf("Error occoured finding the linux link [ %s ] from netlink: %s", ipvlanParentIface.Attrs().Name, err)
		return err
	}
	routes, err := netlink.RouteList(iface, netlink.FAMILY_V4)
	if err != nil {
		log.Errorf("Unable to retreive netlink routes: %s", err)
		return err
	}
	ifaceIP, err := getIfaceIP(ifaceStr)
	if err != nil {
		log.Errorf("Unable to retreive a usable IP via ethernet interface: %s", ifaceStr)
		return err
	}
	for _, route := range routes {
		if netOverlaps(ifaceIP, route.Dst) == true {
			log.Warnf("Ignoring route [ %v ] as it is associated to the [ %s ] interface", ifaceIP, ifaceStr)
		} else if route.Scope == 0x0 || route.Scope == 0xfd {
			// Remove link and universal routes from the docker host ipvlan interface
			log.Infof("Cleaning static route cache for the destination: [ %s ]", route.Dst)
			err := delRoute(route, ipvlanParentIface)
			if err != nil {
				log.Errorf("Error deleting static route cache for Destination: [ %s ] and Nexthop [ %s ] Error: %s", route.Dst, route.Gw, err)
			}
		}
	}
	return nil
}

// Returns a list of routes
func RouteMap() *map[string]Route {
	links, _ := netlink.LinkList()
	linksMap := make(map[int]string)
	for _, l := range links {
		attrs := *l.Attrs()
		linksMap[attrs.Index] = attrs.Name
	}

	routes := make(map[string]Route)
	routeList, _ := netlink.RouteList(nil, netlink.FAMILY_V4)
	for _, r := range routeList {
		if_ := linksMap[r.LinkIndex]
		rdst := r.Dst
		var dst string
		if rdst != nil {
			dst = rdst.String()
		} else {
			dst = "default"
		}

		route := Route{
			Via: r.Gw,
			Dev: if_,
			Src: r.Src,
		}
		routes[dst] = route
	}
	return &routes
}

func getDefaultGatewayIface() *net.Interface {
	log.Debug("Attempting to retrieve IP route info from netlink")

	routes, err := netlink.RouteList(nil, 0)
	if err != nil {
		log.Debugf("Unable to detect default interface: %v", err)
		return nil
	}

	if len(routes) == 0 {
		log.Debugf("Netlink returned zero routes")
		return nil
	}

	for _, route := range routes {
		// a nil Dst means that this is the default route.
		if route.Dst == nil {
			i, err := net.InterfaceByIndex(route.LinkIndex)
			if err != nil {
				log.Debugf("Found default route but could not determine interface")
				continue
			}
			log.Debugf("Found default route with interface %v", i)
			return i
		}
	}

	log.Debugf("Unable to find default route")
	return nil
}

func getSource(dest net.IP) (net.IP, error) {
	var source net.IP
	routes, err := netlink.RouteList(nil, netlink.FAMILY_ALL)
	if err != nil {
		return nil, fmt.Errorf("Failed to get routes")
	}
	var link netlink.Link
	for _, route := range routes {
		if route.Dst == nil {
			link = &netlink.Dummy{netlink.LinkAttrs{Index: route.LinkIndex}}
			source = route.Src

		} else if route.Dst.Contains(dest) {
			link = &netlink.Dummy{netlink.LinkAttrs{Index: route.LinkIndex}}
			source = route.Src
			break
		}
	}
	if link == nil {
		return nil, fmt.Errorf("Failed to find route to target: %s", dest)
	}
	if source == nil {
		// no source in route to target so use the first ip from interface
		addrs, err := netlink.AddrList(link, netlink.FAMILY_ALL)
		if err != nil || len(addrs) == 0 {
			return nil, fmt.Errorf("Failed to find source ip for interface: %s", link)
		}
		source = addrs[0].IP
	}
	return source, nil
}

// A network is considered free if it does not overlap any existing
// routes on this host. This is the same approach taken by Docker.
func CheckNetworkFree(subnet *net.IPNet) error {
	routes, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		return err
	}
	for _, route := range routes {
		if route.Dst != nil && overlaps(route.Dst, subnet) {
			return fmt.Errorf("network %s would overlap with route %s", subnet, route.Dst)
		}
	}
	return nil
}

// For a specific address, we only care if it is actually *inside* an
// existing route, because weave-local traffic never hits IP routing.
func CheckAddressOverlap(addr net.IP) error {
	routes, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		return err
	}
	for _, route := range routes {
		if route.Dst != nil && route.Dst.Contains(addr) {
			return fmt.Errorf("Address %s overlaps with existing route %s on host.", addr, route.Dst)
		}
	}
	return nil
}

// Adds a macvlan interface to a container for use with the egress router feature
func addMacvlan(netns string) error {
	var defIface netlink.Link
	var err error

	// Find interface with the default route
	routes, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		return fmt.Errorf("failed to read routes: %v", err)
	}

	for _, r := range routes {
		if r.Dst == nil {
			defIface, err = netlink.LinkByIndex(r.LinkIndex)
			if err != nil {
				return fmt.Errorf("failed to get default route interface: %v", err)
			}
		}
	}
	if defIface == nil {
		return fmt.Errorf("failed to find default route interface")
	}

	podNs, err := ns.GetNS(netns)
	if err != nil {
		return fmt.Errorf("could not open netns %q", netns)
	}
	defer podNs.Close()

	err = netlink.LinkAdd(&netlink.Macvlan{
		LinkAttrs: netlink.LinkAttrs{
			MTU:         defIface.Attrs().MTU,
			Name:        "macvlan0",
			ParentIndex: defIface.Attrs().Index,
			Namespace:   netlink.NsFd(podNs.Fd()),
		},
		Mode: netlink.MACVLAN_MODE_PRIVATE,
	})
	if err != nil {
		return fmt.Errorf("failed to create macvlan interface: %v", err)
	}
	return podNs.Do(func(netns ns.NetNS) error {
		l, err := netlink.LinkByName("macvlan0")
		if err != nil {
			return fmt.Errorf("failed to find macvlan interface: %v", err)
		}
		err = netlink.LinkSetUp(l)
		if err != nil {
			return fmt.Errorf("failed to set macvlan interface up: %v", err)
		}
		return nil
	})
}

func verifyRoute(bgpRoute *net.IPNet) {
	networks, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		return
	}
	for _, network := range networks {
		if network.Dst != nil && netOverlaps(bgpRoute, network.Dst) {
			log.Errorf("The network [ %v ] learned via BGP conflicts with an existing route on this host [ %v ]", bgpRoute, network.Dst)
			return
		}
	}
	return
}

func getDefaultGW(family int) (string, error) {
	l, err := netlink.LinkByName("lo")
	if err != nil {
		return "", err
	}

	routes, err := netlink.RouteList(l, family)
	if err != nil {
		return "", err
	}

	return routes[0].Gw.String(), nil
}

//delete default routes
//FIXME all default routes will be erased
func delDefaultRoute() error {
	routes, _ := netlink.RouteList(nil, netlink.FAMILY_V4)

	for _, route := range routes {
		if route.Dst != nil || route.Src != nil {
			continue
		}
		if err := netlink.RouteDel(&route); err != nil {
			return err
		}
	}
	return nil
}

func checkOverlaps(toCheck *net.IPNet) {
	networks, err := netlink.RouteList(nil, netlink.FAMILY_V4)
	if err != nil {
		return
	}

	for _, network := range networks {
		if network.Dst != nil && netOverlaps(toCheck, network.Dst) {
			log.Errorf("todo: do something with this")
			return
		}
	}
	return
}

func getDefaultGW(family int) (string, error) {
	routes, err := netlink.RouteList(nil, family)
	if err != nil {
		return "", err
	}

	for _, route := range routes {
		if route.Src == nil && route.Dst == nil {
			return route.Gw.String(), nil
		}
	}

	return "", fmt.Errorf("Default route is not set")
}

func removeAllRoutesOnLink(link netlink.Link) error {
	routes, err := netlink.RouteList(link, netlink.FAMILY_V4)
	if err != nil {
		return errwrap.Wrap(fmt.Errorf("cannot list routes on link %q", link.Attrs().Name), err)
	}

	for _, route := range routes {
		if err := netlink.RouteDel(&route); err != nil {
			return errwrap.Wrap(fmt.Errorf("error in time of route removal for route %q", route), err)
		}
	}

	return nil
}

func NewDriver(config *Config) (*driver, error) {
	link, err := netlink.LinkByName(config.Interface)
	if err != nil {
		return nil, err
	}

	addrs, err := netlink.AddrList(link, netlink.FAMILY_ALL)
	if err != nil {
		return nil, err
	}

	// If no subnet was configured on the command line, take the first one
	// from the host interface
	if len(config.Subnet) == 0 {
		config.Subnet = addrs[0].IPNet.String()
		Debug.Printf("using interface subnet %s\n", config.Subnet)

		if len(config.Gateway) == 0 {
			routes, err := netlink.RouteList(link, netlink.FAMILY_ALL)
			if err != nil {
				return nil, err
			}
			for _, route := range routes {
				if route.Dst == nil {
					config.Gateway = route.Gw.String()
					Debug.Printf("using gateway %s\n", config.Gateway)
				}
			}
			if len(config.Gateway) == 0 {
				return nil, fmt.Errorf("cannot autoselect default gateway")
			}
		}
	}

	ip, ipnet, err := net.ParseCIDR(config.Subnet)
	if err != nil {
		return nil, err
	}

	d := &driver{
		config:     config,
		ip:         ip,
		ipnet:      ipnet,
		hostLink:   link,
		interfaces: make(map[string][]net.IP),
	}

	return d, nil
}

func delAllRoutesVia(s net.Addr) error {
	src := s.(*net.TCPAddr).IP

	routes, err := netlink.RouteList(nil, netlink.FAMILY_ALL)
	if err != nil {
		log.Error("Failed to get routes")
		log.Error(err)
		return err
	}
	for _, r := range routes {
		if r.Gw.Equal(src) {
			netlink.RouteDel(&r)
		}
	}
	return nil
}

// getDefaultRouteMtu returns the MTU for the default route's interface.
func getDefaultRouteMtu() (int, error) {
	routes, err := netlink.RouteList(nil, 0)
	if err != nil {
		return 0, err
	}
	for _, r := range routes {
		// a nil Dst means that this is the default route.
		if r.Dst == nil {
			i, err := net.InterfaceByIndex(r.LinkIndex)
			if err != nil {
				continue
			}
			return i.MTU, nil
		}
	}
	return 0, errNoDefaultRoute
}

/* Check if route @src -> @dst exists with the same destination netmask as @r */
func Exists(r *netlink.Route) bool {
	/* FIXME: see bug of RouteList mentioned in above List() command */
	routes, err := netlink.RouteList(nil, 0)
	if err != nil {
		log.Fatalf("failed to list routes: %s", err)
	}
	for _, rt := range routes {
		if rt.Src.Equal(r.Src) && rt.Dst.IP.Equal(r.Dst.IP) {
			sizea, _ := rt.Dst.Mask.Size()
			sizeb, _ := r.Dst.Mask.Size()
			if sizea == sizeb {
				return true
			}
		}
	}
	return false
}