/*
	This is a helper function for find_paths(). It is used to find all possible paths between h1 and h2 starting at ssw.
	The resulting path is a "scramble" meaning that the set of links is a unique set of links that are traversed by
	one or more paths. The list of links can be traversed without the need to dup check which is beneficial for
	increasing/decreasing the utilisaition on the link.  From a scramble, only end point queues can be set as the
	middle switches are NOT maintained.

	usr is the name of the user that the reservation is being processed for (project in openstack). The usr_max value
	is a percentage (1-100)  that defines the maximum of any link that the user may have reservations against or a hard
	limit if larger than 100.

*/
func (n *Network) find_all_paths(ssw *gizmos.Switch, h1 *gizmos.Host, h2 *gizmos.Host, usr *string, commence int64, conclude int64, inc_cap int64, usr_max int64) (path *gizmos.Path, err error) {

	net_sheep.Baa(1, "find_all: searching for all paths between %s  and  %s", *(h1.Get_mac()), *(h2.Get_mac()))

	links, epsw, err := ssw.All_paths_to(h2.Get_mac(), commence, conclude, inc_cap, usr, usr_max)
	if err != nil {
		return
	}

	path = gizmos.Mk_path(h1, h2)
	path.Set_scramble(true)
	path.Set_bandwidth(inc_cap)
	path.Add_switch(ssw)
	path.Add_switch(epsw)

	lnk := n.find_vlink(*(ssw.Get_id()), h1.Get_port(ssw), -1, nil, nil) // add endpoint -- a virtual link out from switch to h1
	lnk.Add_lbp(*(h1.Get_mac()))
	lnk.Set_forward(ssw)
	path.Add_endpoint(lnk)

	lnk = n.find_vlink(*(epsw.Get_id()), h2.Get_port(epsw), -1, nil, nil) // add endpoint -- a virtual link out from switch to h2
	lnk.Add_lbp(*(h2.Get_mac()))
	lnk.Set_forward(epsw)
	path.Add_endpoint(lnk)

	for i := range links {
		path.Add_link(links[i])
	}

	return
}

/*
	A helper function for find_paths() that is used when running in 'relaxed' mode. In relaxed mode we don't
	actually find a path between the endpoints as we aren't doign admission control, but need to simulate
	a path in order to set up the flow-mods on the endpoints correctly.
*/
func (n *Network) find_relaxed_path(sw1 *gizmos.Switch, h1 *gizmos.Host, sw2 *gizmos.Switch, h2 *gizmos.Host) (path *gizmos.Path, err error) {

	net_sheep.Baa(1, "find_lax: creating relaxed path between %s and %s", *(h1.Get_mac()), *(h2.Get_mac()))

	if sw1 == nil || sw2 == nil {
		return nil, fmt.Errorf("one endpoint switch was unknown; cannot create a virtual (relaxed) path")
	}

	path = gizmos.Mk_path(h1, h2)
	path.Set_bandwidth(0)
	path.Add_switch(sw1)
	path.Add_switch(sw2)

	lnk := n.find_vlink(*(sw1.Get_id()), h1.Get_port(sw1), -1, nil, nil) // add endpoint -- a virtual from sw1 out to the host h1
	lnk.Add_lbp(*(h1.Get_mac()))
	lnk.Set_forward(sw1)
	path.Add_endpoint(lnk)

	lnk = n.find_swvlink(*(sw1.Get_id()), *(sw2.Get_id())) // suss out or create a virtual link between the two
	lnk.Set_forward(sw2)
	lnk.Set_backward(sw1)
	path.Add_link(lnk)

	lnk = n.find_vlink(*(sw2.Get_id()), h2.Get_port(sw2), -1, nil, nil) // add endpoint -- a virtual link on sw2 out to the host h2
	lnk.Add_lbp(*(h2.Get_mac()))
	lnk.Set_forward(sw2)
	path.Add_endpoint(lnk)

	return
}

/*
	This is a helper function for find_paths and is invoked when we are interested in just the shortest
	path between two switches. It will find the shortest path, and then build a path structure which
	represents it.  ssw is the starting switch and h2nm is the endpoint "name" (probably a mac that we
	are looking for.

	The usr_max value is the percentage (1-100) that indicates the maximum percentage of a link that the
	user may reserve.

	This function assumes that the switches have all been initialised with a reset of the visited flag,
	setting of inital cost, etc.
*/
func (n *Network) find_shortest_path(ssw *gizmos.Switch, h1 *gizmos.Host, h2 *gizmos.Host, usr *string, commence int64, conclude int64, inc_cap int64, usr_max int64) (path *gizmos.Path, cap_trip bool) {
	h1nm := h1.Get_mac()
	h2nm := h2.Get_mac()
	path = nil

	if usr_max <= 0 {
		i41, _ := h1.Get_addresses()
		i42, _ := h2.Get_addresses()
		net_sheep.Baa(1, "no path generated: user link capacity set to 0: attempt %s -> %s", *i41, *i42)
		return
	}

	ssw.Cost = 0                                                                  // seed the cost in the source switch
	tsw, cap_trip := ssw.Path_to(h2nm, commence, conclude, inc_cap, usr, usr_max) // discover the shortest path to terminating switch that has enough bandwidth
	if tsw != nil {                                                               // must walk from the term switch backwards collecting the links to set the path
		path = gizmos.Mk_path(h1, h2)
		path.Set_reverse(true) // indicate that the path is saved in reverse order
		path.Set_bandwidth(inc_cap)
		net_sheep.Baa(2, "find_spath: found target on %s", tsw.To_str())

		lnk := n.find_vlink(*(tsw.Get_id()), h2.Get_port(tsw), -1, nil, nil) // add endpoint -- a virtual link out from switch to h2
		lnk.Add_lbp(*h2nm)
		lnk.Set_forward(tsw) // endpoints have only a forward link
		path.Add_endpoint(lnk)

		for tsw != nil {
			if tsw.Prev != nil { // last node won't have a prev pointer so no link
				lnk = tsw.Prev.Get_link(tsw.Plink)
				path.Add_link(lnk)
			}
			path.Add_switch(tsw)

			net_sheep.Baa(3, "\t%s using link %d", tsw.Prev.To_str(), tsw.Plink)

			if tsw.Prev == nil { // last switch in the path, add endpoint
				lnk = n.find_vlink(*(tsw.Get_id()), h1.Get_port(tsw), -1, nil, nil) // endpoint is a virt link from switch to h1
				lnk.Add_lbp(*h1nm)
				lnk.Set_forward(tsw) // endpoints have only a forward link
				path.Add_endpoint(lnk)
			}
			tsw = tsw.Prev
		}

		path.Flip_endpoints() // path expects them to be in h1,h2 order; we added them backwards so must flip
	}

	return
}

/*
	Test some network pathfinding. Reads a topo from the static json file test_net.json and builds
	a network of hosts and links, then attempts to find all paths between them using the switch
	find all functions.
*/
func TestNet(t *testing.T) { // must use bloody camel case to be recognised by go testing

	var (
		fsw     *gizmos.Switch
		sw_list map[string]*gizmos.Switch
	)

	sw_list = make(map[string]*gizmos.Switch)
	fmt.Fprintf(os.Stderr, "\n------------- net test starts -----------------\n")
	links, err := gizmos.Read_json_links("test_net.json")
	if err == nil {
		fmt.Fprintf(os.Stderr, "read  %d links from the file\n", len(links))
	} else {
		fmt.Fprintf(os.Stderr, "failed to read links: %s  [FAIL]\n", err)
		t.Fail()
		return
	}

	last := ""
	fsw = nil
	for i := range links { // parse all links returned from the controller
		ssw := sw_list[links[i].Src_switch]
		if ssw == nil {
			ssw = gizmos.Mk_switch(&links[i].Src_switch) // source switch
			sw_list[links[i].Src_switch] = ssw
		}

		dsw := sw_list[links[i].Dst_switch]
		if dsw == nil {
			dsw = gizmos.Mk_switch(&links[i].Dst_switch) // dest switch
			sw_list[links[i].Dst_switch] = dsw
		}

		l := gizmos.Mk_link(ssw.Get_id(), dsw.Get_id(), 100000000, 95, nil) // link in forward direction
		l.Set_forward(dsw)
		l.Set_backward(ssw)
		ssw.Add_link(l)

		l = gizmos.Mk_link(dsw.Get_id(), ssw.Get_id(), 100000000, 95, nil) // link in backward direction
		l.Set_forward(ssw)
		l.Set_backward(dsw)
		dsw.Add_link(l)

		mac := fmt.Sprintf("00:00:00:00:00:%02d", i)
		ip := fmt.Sprintf("10.0.0.%02d", i)
		h := gizmos.Mk_host(mac, ip, "")
		h.Add_switch(ssw, i) // add a host to each src switch
		vmname := "foobar-name"
		ssw.Add_host(&ip, &vmname, i+200)
		fmt.Fprintf(os.Stderr, "adding host: %s\n", ip)

		if fsw == nil { // save first switch to use as start of search
			fsw = ssw
		}

		mac = fmt.Sprintf("%02d:00:00:00:00:00", i)
		ip = fmt.Sprintf("10.0.0.1%02d", i)
		h = gizmos.Mk_host(mac, ip, "")
		h.Add_switch(dsw, i) // add a host to each dest switch
		vmname2 := "foobar-name2"
		dsw.Add_host(&ip, &vmname2, i+200)

		fmt.Fprintf(os.Stderr, "adding host: %s\n", ip)
		last = ip
	}

	fmt.Fprintf(os.Stderr, ">>> searching for: %s\n", last)
	usrname := "username"
	fsw.All_paths_to(&last, 0, 0, 100, &usrname, 95)
}

/*
	Find a set of connected switches that can be used as a path beteeen
	hosts 1 and 2 (given by name; mac or ip).  Further, all links between from and the final switch must be able to
	support the additional capacity indicated by inc_cap during the time window between
	commence and conclude (unix timestamps).

	If the network is 'split' a host may appear to be attached to multiple switches; one with a real connection and
	the others are edge switches were we see an 'entry' point for the host from the portion of the network that we
	cannot visualise.  We must attempt to find a path between h1 using all of it's attached switches, and thus the
	return is an array of paths rather than a single path.


	h1nm and h2nm are likely going to be ip addresses as the main function translates any names that would have
	come in from the requestor.

	Extip is an external IP address that will need to be associated with the flow-mods and thus needs to be
	added to any path we generate.

	If mlag_paths is true, then we will find shortest path but add usage to all related mlag links in the path.

	If find_all is set, and mlog_paths is false, then we will suss out all possible paths between h1 and h2 and not
	just the shortest path.
*/
func (n *Network) find_paths(h1nm *string, h2nm *string, usr *string, commence int64, conclude int64, inc_cap int64, extip *string, ext_flag *string, find_all bool) (pcount int, path_list []*gizmos.Path, cap_trip bool) {
	var (
		path      *gizmos.Path
		ssw       *gizmos.Switch // starting switch
		h1        *gizmos.Host
		h2        *gizmos.Host
		lnk       *gizmos.Link
		plidx     int = 0
		swidx     int = 0 // index into host's switch list
		err       error
		lcap_trip bool = false // local capacity trip flag; indicates one or more paths blocked by capacity limits
	)

	if h1nm == nil || h2nm == nil {
		net_sheep.Baa(1, "IER:	find_paths: one/both names is/are nil  h1 nil=%v  h2 nil=%v", h1nm == nil, h2nm == nil)
		return 0, nil, false
	}

	h1 = n.hosts[*h1nm]
	if h1 == nil {
		path_list = nil
		net_sheep.Baa(1, "find-path: cannot find host(1) in network -- not reported by SDNC? %s", *h1nm)
		return
	}
	h1nm = h1.Get_mac() // must have the host's mac as our flowmods are at that level

	h2 = n.hosts[*h2nm] // do the same for the second host
	if h2 == nil {
		path_list = nil
		net_sheep.Baa(1, "find-path: cannot find host(2) in network -- not reported by the SDNC? %s", *h2nm)
		return
	}
	h2nm = h2.Get_mac()

	if h1nm == nil || h2nm == nil { // this has never happened, but be parinoid
		pcount = 0
		path_list = nil
		net_sheep.Baa(0, "CRI: find-path: internal error: either h1nm or h2nm was nil after get mac  [TGUNET005]")
		return
	}

	path_list = make([]*gizmos.Path, len(n.links)) // we cannot have more in our path than the number of links (needs to be changed as this isn't good in the long run)
	pcount = 0

	for { // we'll break after we've looked at all of the connection points for h1
		if plidx >= len(path_list) {
			net_sheep.Baa(0, "CRI: find-path: internal error -- path size > num of links.  [TGUNET006]")
			return
		}

		ssw, _ = h1.Get_switch_port(swidx) // get next switch that lists h1 as attached; we'll work 'out' from it toward h2
		if ssw == nil {                    // no more source switches which h1 thinks it's attached to
			pcount = plidx
			if pcount <= 0 || swidx == 0 {
				net_sheep.Baa(1, "find-path: early exit? no switch/port returned for h1 (%s) at index %d captrip=%v", *h1nm, swidx, lcap_trip)
			}
			path_list = path_list[0:pcount] // slice it down to size
			cap_trip = lcap_trip            // set with overall state
			return
		}

		fence := n.get_fence(usr)
		if ssw.Has_host(h1nm) && ssw.Has_host(h2nm) { // if both hosts are on the same switch, there's no path if they both have the same port (both external to our view)
			p1 := h1.Get_port(ssw)
			p2 := h2.Get_port(ssw)
			if p1 < 0 || p1 != p2 { // when ports differ we'll create/find the vlink between them	(in Tegu-lite port == -128 is legit and will dup)
				m1 := h1.Get_mac()
				m2 := h2.Get_mac()

				lnk = n.find_vlink(*(ssw.Get_id()), p1, p2, m1, m2)
				has_room := true // always room if relaxed mode, so start this way
				if n.relaxed {
					has_room = ssw.Has_capacity_out(commence, conclude, inc_cap, fence.Name, fence.Get_limit_max()) // ensure cap on all outbound links from switch
				}

				if has_room { // room for the reservation
					lnk.Add_lbp(*h1nm)
//.........这里部分代码省略.........