/*

 * Copyright (c) 2004-2008 Voltaire, Inc. All rights reserved.

 * Copyright (c) 2002-2015 Mellanox Technologies LTD. All rights reserved.

 * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.

 * Copyright (c) 2009-2015 ZIH, TU Dresden, Federal Republic of Germany. All rights reserved.

 * Copyright (C) 2012-2017 Tokyo Institute of Technology. All rights reserved.

 *

 * This software is available to you under a choice of one of two

 * licenses.  You may choose to be licensed under the terms of the GNU

 * General Public License (GPL) Version 2, available from the file

 * COPYING in the main directory of this source tree, or the

 * OpenIB.org BSD license below:

 *

 *     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.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS

 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN

 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

 * SOFTWARE.

 *

 */

/*

 * Abstract:

 *    Implementation of OpenSM (deadlock-free) single-source-shortest-path routing

 *    (with dijkstra algorithm)

 */

#if HAVE_CONFIG_H

#  include <config.h>

#endif				/* HAVE_CONFIG_H */

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <complib/cl_heap.h>

#include <opensm/osm_file_ids.h>

#define FILE_ID OSM_FILE_UCAST_DFSSSP_C

#include <opensm/osm_ucast_mgr.h>

#include <opensm/osm_opensm.h>

#include <opensm/osm_node.h>

#include <opensm/osm_multicast.h>

#include <opensm/osm_mcast_mgr.h>

/* "infinity" for dijkstra */

#define INF      0x7FFFFFFF

enum {

	UNDISCOVERED = 0,

	DISCOVERED

};

enum {

	UNKNOWN = 0,

	GRAY,

	BLACK,

};

typedef struct link {

	uint64_t guid;		/* guid of the neighbor behind the link */

	uint32_t from;		/* base_index in the adjazenz list (start of the link) */

	uint8_t from_port;	/* port on the base_side (needed for weight update to identify the correct link for multigraphs) */

	uint32_t to;		/* index of the neighbor in the adjazenz list (end of the link) */

	uint8_t to_port;	/* port on the side of the neighbor (needed for the LFT) */

	uint64_t weight;	/* link weight */

	struct link *next;

} link_t;

typedef struct vertex {

	/* informations of the fabric */

	uint64_t guid;

	uint16_t lid;		/* for lft filling */

	uint32_t num_hca;	/* numbers of Hca/LIDs on the switch, for weight calculation */

	link_t *links;

	uint8_t hops;

	/* for dijkstra routing */

	link_t *used_link;	/* link between the vertex discovered before and this vertex */

	uint64_t distance;	/* distance from source to this vertex */

	uint8_t state;

	/* for the d-ary heap */

	size_t heap_index;

	/* for LFT writing and debug */

	osm_switch_t *sw;	/* selfpointer */

	boolean_t dropped;	/* indicate dropped switches (w/ ucast cache) */

} vertex_t;

typedef struct vltable {

	uint64_t num_lids;	/* size of the lids array */

	uint16_t *lids;		/* sorted array of all lids in the subnet */

	uint8_t *vls;		/* matrix form assignment lid X lid -> virtual lane */

} vltable_t;

typedef struct cdg_link {

	struct cdg_node *node;

	uint32_t num_pairs;	/* number of src->dest pairs incremented in path adding step */

	uint32_t max_len;	/* length of the srcdest array */

	uint32_t removed;	/* number of pairs removed in path deletion step */

	uint32_t *srcdest_pairs;

	struct cdg_link *next;

} cdg_link_t;

/* struct for a node of a binary tree with additional parent pointer */

typedef struct cdg_node {

	uint64_t channelID;	/* unique key consist of src lid + port + dest lid + port */

	cdg_link_t *linklist;	/* edges to adjazent nodes */

	uint8_t status;		/* node status in cycle search to avoid recursive function */

	uint8_t visited;	/* needed to traverse the binary tree */

	struct cdg_node *pre;	/* to save the path in cycle detection algorithm */

	struct cdg_node *left, *right, *parent;

} cdg_node_t;

typedef struct dfsssp_context {

	osm_routing_engine_type_t routing_type;

	osm_ucast_mgr_t *p_mgr;

	vertex_t *adj_list;

	uint32_t adj_list_size;

	vltable_t *srcdest2vl_table;

	uint8_t *vl_split_count;

} dfsssp_context_t;

/**************** set initial values for structs **********************

 **********************************************************************/

static inline void set_default_link(link_t * link)

{

	link->guid = 0;

	link->from = 0;

	link->from_port = 0;

	link->to = 0;

	link->to_port = 0;

	link->weight = 0;

	link->next = NULL;

}

static inline void set_default_vertex(vertex_t * vertex)

{

	vertex->guid = 0;

	vertex->lid = 0;

	vertex->num_hca = 0;

	vertex->links = NULL;

	vertex->hops = 0;

	vertex->used_link = NULL;

	vertex->distance = 0;

	vertex->state = UNDISCOVERED;

	vertex->heap_index = 0;

	vertex->sw = NULL;

	vertex->dropped = FALSE;

}

static inline void set_default_cdg_node(cdg_node_t * node)

{

	node->channelID = 0;

	node->linklist = NULL;

	node->status = UNKNOWN;

	node->visited = 0;

	node->pre = NULL;

	node->left = NULL;

	node->right = NULL;

	node->parent = NULL;

}

/**********************************************************************

 **********************************************************************/

/************ helper functions to save src/dest X vl combination ******

 **********************************************************************/

/* compare function of two lids for stdlib qsort */

static int cmp_lids(const void *l1, const void *l2)

{

	ib_net16_t lid1 = *((ib_net16_t *) l1), lid2 = *((ib_net16_t *) l2);

	if (lid1 < lid2)

		return -1;

	else if (lid1 > lid2)

		return 1;

	else

		return 0;

}

/* use stdlib to sort the lid array */

static inline void vltable_sort_lids(vltable_t * vltable)

{

	qsort(vltable->lids, vltable->num_lids, sizeof(ib_net16_t), cmp_lids);

}

/* use stdlib to get index of key in lid array;

   return -1 if lid isn't found in lids array

*/

static inline int64_t vltable_get_lidindex(ib_net16_t * key, vltable_t * vltable)

{

	ib_net16_t *found_lid = NULL;

	found_lid =

	    (ib_net16_t *) bsearch(key, vltable->lids, vltable->num_lids,

				   sizeof(ib_net16_t), cmp_lids);

	if (found_lid)

		return found_lid - vltable->lids;

	else

		return -1;

}

/* get virtual lane from src lid X dest lid combination;

   return -1 for invalid lids

*/

static int32_t vltable_get_vl(vltable_t * vltable, ib_net16_t slid, ib_net16_t dlid)

{

	int64_t ind1 = vltable_get_lidindex(&slid, vltable);

	int64_t ind2 = vltable_get_lidindex(&dlid, vltable);

	if (ind1 > -1 && ind2 > -1)

		return (int32_t) (vltable->

				  vls[ind1 + ind2 * vltable->num_lids]);

	else

		return -1;

}

/* set a virtual lane in the matrix */

static inline void vltable_insert(vltable_t * vltable, ib_net16_t slid,

				  ib_net16_t dlid, uint8_t vl)

{

	int64_t ind1 = vltable_get_lidindex(&slid, vltable);

	int64_t ind2 = vltable_get_lidindex(&dlid, vltable);

	if (ind1 > -1 && ind2 > -1)

		vltable->vls[ind1 + ind2 * vltable->num_lids] = vl;

}

/* change a number of lanes from lane xy to lane yz */

static void vltable_change_vl(vltable_t * vltable, uint8_t from, uint8_t to,

			      uint64_t count)

{

	uint64_t set = 0, stop = 0;

	uint64_t ind1 = 0, ind2 = 0;

	for (ind1 = 0; ind1 < vltable->num_lids; ind1++) {

		for (ind2 = 0; ind2 < vltable->num_lids; ind2++) {

			if (set == count) {

				stop = 1;

				break;

			}

			if (ind1 != ind2) {

				if (vltable->

				    vls[ind1 + ind2 * vltable->num_lids] ==

				    from) {

					vltable->vls[ind1 +

						     ind2 * vltable->num_lids] =

					    to;

					set++;

				}

			}

		}

		if (stop)

			break;

	}

}

static void vltable_print(osm_ucast_mgr_t * p_mgr, vltable_t * vltable)

{

	uint64_t ind1 = 0, ind2 = 0;

	for (ind1 = 0; ind1 < vltable->num_lids; ind1++) {

		for (ind2 = 0; ind2 < vltable->num_lids; ind2++) {

			if (ind1 != ind2) {

				OSM_LOG(p_mgr->p_log, OSM_LOG_DEBUG,

					"   route from src_lid=%" PRIu16

					" to dest_lid=%" PRIu16 " on vl=%" PRIu8

					"\n", cl_ntoh16(vltable->lids[ind1]),

					cl_ntoh16(vltable->lids[ind2]),

					vltable->vls[ind1 +

						     ind2 * vltable->num_lids]);

			}

		}

	}

}

static void vltable_dealloc(vltable_t ** vltable)

{

	if (*vltable) {

		if ((*vltable)->lids)

			free((*vltable)->lids);

		if ((*vltable)->vls)

			free((*vltable)->vls);

		free(*vltable);

		*vltable = NULL;

	}

}

static int vltable_alloc(vltable_t ** vltable, uint64_t size)

{

	/* allocate VL table and indexing array */

	*vltable = (vltable_t *) malloc(sizeof(vltable_t));

	if (!(*vltable))

		goto ERROR;

	(*vltable)->num_lids = size;

	(*vltable)->lids = (ib_net16_t *) malloc(size * sizeof(ib_net16_t));

	if (!((*vltable)->lids))

		goto ERROR;

	(*vltable)->vls = (uint8_t *) malloc(size * size * sizeof(uint8_t));

	if (!((*vltable)->vls))

		goto ERROR;

	memset((*vltable)->vls, OSM_DEFAULT_SL, size * size);

	return 0;

ERROR:

	vltable_dealloc(vltable);

	return 1;

}

/**********************************************************************

 **********************************************************************/

/************ helper functions to save/manage the channel dep. graph **

 **********************************************************************/

/* update the srcdest array;

   realloc array (double the size) if size is not large enough

*/

static void set_next_srcdest_pair(cdg_link_t * link, uint32_t srcdest)

{

	uint32_t new_size = 0, start_size = 2;

	uint32_t *tmp = NULL, *tmp2 = NULL;

	if (link->num_pairs == 0) {

		link->srcdest_pairs =

		    (uint32_t *) malloc(start_size * sizeof(uint32_t));

		link->srcdest_pairs[link->num_pairs] = srcdest;

		link->max_len = start_size;

		link->removed = 0;

	} else if (link->num_pairs == link->max_len) {

		new_size = link->max_len << 1;

		tmp = (uint32_t *) malloc(new_size * sizeof(uint32_t));

		tmp =

		    memcpy(tmp, link->srcdest_pairs,

			   link->max_len * sizeof(uint32_t));

		tmp2 = link->srcdest_pairs;

		link->srcdest_pairs = tmp;

		link->srcdest_pairs[link->num_pairs] = srcdest;

		free(tmp2);

		link->max_len = new_size;

	} else {

		link->srcdest_pairs[link->num_pairs] = srcdest;

	}

	link->num_pairs++;

}

static inline uint32_t get_next_srcdest_pair(cdg_link_t * link, uint32_t index)

{

	return link->srcdest_pairs[index];

}

/* traverse binary tree to find a node */

static cdg_node_t *cdg_search(cdg_node_t * root, uint64_t channelID)

{

	while (root) {

		if (channelID < root->channelID)

			root = root->left;

		else if (channelID > root->channelID)

			root = root->right;

		else if (channelID == root->channelID)

			return root;

	}

	return NULL;

}

/* insert new node into the binary tree */

static void cdg_insert(cdg_node_t ** root, cdg_node_t * new_node)

{

	cdg_node_t *current = *root;

	if (!current) {

		current = new_node;

		*root = current;

		return;

	}

	while (current) {

		if (new_node->channelID < current->channelID) {

			if (current->left) {

				current = current->left;

			} else {

				current->left = new_node;

				new_node->parent = current;

				break;

			}

		} else if (new_node->channelID > current->channelID) {

			if (current->right) {

				current = current->right;

			} else {

				current->right = new_node;

				new_node->parent = current;

				break;

			}

		} else if (new_node->channelID == current->channelID) {

			/* not really possible, maybe programming error */

			break;

		}

	}

}

static void cdg_node_dealloc(cdg_node_t * node)

{

	cdg_link_t *link = node->linklist, *tmp = NULL;

	/* dealloc linklist */

	while (link) {

		tmp = link;

		link = link->next;

		if (tmp->num_pairs)

			free(tmp->srcdest_pairs);

		free(tmp);

	}

	/* dealloc node */

	free(node);

}

static void cdg_dealloc(cdg_node_t ** root)

{

	cdg_node_t *current = *root;

	while (current) {

		if (current->left) {

			current = current->left;

		} else if (current->right) {

			current = current->right;

		} else {

			if (current->parent == NULL) {

				cdg_node_dealloc(current);

				*root = NULL;

				break;

			}

			if (current->parent->left == current) {

				current = current->parent;

				cdg_node_dealloc(current->left);

				current->left = NULL;

			} else if (current->parent->right == current) {

				current = current->parent;

				cdg_node_dealloc(current->right);

				current->right = NULL;

			}

		}

	}

}

/* search for a edge in the cdg which should be removed to break a cycle */

static cdg_link_t *get_weakest_link_in_cycle(cdg_node_t * cycle)

{

	cdg_node_t *current = cycle, *node_with_weakest_link = NULL;

	cdg_link_t *link = NULL, *weakest_link = NULL;

	link = current->linklist;

	while (link) {

		if (link->node->status == GRAY) {

			weakest_link = link;

			node_with_weakest_link = current;

			current = link->node;

			break;

		}

		link = link->next;

	}

	while (1) {

		current->status = UNKNOWN;

		link = current->linklist;

		while (link) {

			if (link->node->status == GRAY) {

				if ((link->num_pairs - link->removed) <

				    (weakest_link->num_pairs -

				     weakest_link->removed)) {

					weakest_link = link;

					node_with_weakest_link = current;

				}

				current = link->node;

				break;

			}

			link = link->next;

		}

		/* if complete cycle is traversed */

		if (current == cycle) {

			current->status = UNKNOWN;

			break;

		}

	}

	if (node_with_weakest_link->linklist == weakest_link) {

		node_with_weakest_link->linklist = weakest_link->next;

	} else {

		link = node_with_weakest_link->linklist;

		while (link) {

			if (link->next == weakest_link) {

				link->next = weakest_link->next;

				break;

			}

			link = link->next;

		}

	}

	return weakest_link;

}

/* search for nodes in the cdg not yet reached in the cycle search process;

   (some nodes are unreachable, e.g. a node is a source or the cdg has not connected parts)

*/

static cdg_node_t *get_next_cdg_node(cdg_node_t * root)

{

	cdg_node_t *current = root, *res = NULL;

	while (current) {

		current->visited = 1;

		if (current->status == UNKNOWN) {

			res = current;

			break;

		}

		if (current->left && !current->left->visited) {

			current = current->left;

		} else if (current->right && !current->right->visited) {

			current = current->right;

		} else {

			if (current->left)

				current->left->visited = 0;

			if (current->right)

				current->right->visited = 0;

			if (current->parent == NULL)

				break;

			else

				current = current->parent;

		}

	}

	/* Clean up */

	while (current) {

		current->visited = 0;

		if (current->left)

			current->left->visited = 0;

		if (current->right)

			current->right->visited = 0;

		current = current->parent;

	}

	return res;

}

/* make a DFS on the cdg to check for a cycle */

static cdg_node_t *search_cycle_in_channel_dep_graph(cdg_node_t * cdg,

						     cdg_node_t * start_node)

{

	cdg_node_t *cycle = NULL;

	cdg_node_t *current = start_node, *next_node = NULL, *tmp = NULL;

	cdg_link_t *link = NULL;

	while (current) {

		current->status = GRAY;

		link = current->linklist;

		next_node = NULL;

		while (link) {

			if (link->node->status == UNKNOWN) {

				next_node = link->node;

				break;

			}

			if (link->node->status == GRAY) {

				cycle = link->node;

				goto Exit;

			}

			link = link->next;

		}

		if (next_node) {

			next_node->pre = current;

			current = next_node;

		} else {

			/* found a sink in the graph, go to last node */

			current->status = BLACK;

			/* srcdest_pairs of this node aren't relevant, free the allocated memory */

			link = current->linklist;

			while (link) {

				if (link->num_pairs)

					free(link->srcdest_pairs);

				link->srcdest_pairs = NULL;

				link->num_pairs = 0;

				link->removed = 0;

				link = link->next;

			}

			if (current->pre) {

				tmp = current;

				current = current->pre;

				tmp->pre = NULL;

			} else {

				/* search for other subgraphs in cdg */

				current = get_next_cdg_node(cdg);

				if (!current)

					break;	/* all relevant nodes traversed, no more cycles found */

			}

		}

	}

Exit:

	return cycle;

}

/* calculate the path from source to destination port;

   new channels are added directly to the cdg

*/

static int update_channel_dep_graph(cdg_node_t ** cdg_root,

				    osm_port_t * src_port, uint16_t slid,

				    osm_port_t * dest_port, uint16_t dlid)

{

	osm_node_t *local_node = NULL, *remote_node = NULL;

	uint16_t local_lid = 0, remote_lid = 0;

	uint32_t srcdest = 0;

	uint8_t local_port = 0, remote_port = 0;

	uint64_t channelID = 0;

	cdg_node_t *channel_head = NULL, *channel = NULL, *last_channel = NULL;

	cdg_link_t *linklist = NULL;

	/* set the identifier for the src/dest pair to save this on each edge of the cdg */

	srcdest = (((uint32_t) slid) << 16) + ((uint32_t) dlid);

	channel_head = (cdg_node_t *) malloc(sizeof(cdg_node_t));

	if (!channel_head)

		goto ERROR;

	set_default_cdg_node(channel_head);

	last_channel = channel_head;

	/* if src is a Hca, then the channel from Hca to switch would be a source in the graph

	   sources can't be part of a cycle -> skip this channel

	 */

	remote_node =

	    osm_node_get_remote_node(src_port->p_node,

				     src_port->p_physp->port_num, &remote_port);

	while (remote_node && remote_node->sw) {

		local_node = remote_node;

		local_port = local_node->sw->new_lft[dlid];

		/* sanity check: local_port must be set or routing is broken */

		if (local_port == OSM_NO_PATH)

			goto ERROR;

		local_lid = cl_ntoh16(osm_node_get_base_lid(local_node, 0));

		/* each port belonging to a switch has lmc==0 -> get_base_lid is fine

		   (local/remote port in this function are always part of a switch)

		 */

		remote_node =

		    osm_node_get_remote_node(local_node, local_port,

					     &remote_port);

		/* if remote_node is a Hca, then the last channel from switch to Hca would be a sink in the cdg -> skip */

		if (!remote_node || !remote_node->sw)

			break;

		remote_lid = cl_ntoh16(osm_node_get_base_lid(remote_node, 0));

		channelID =

		    (((uint64_t) local_lid) << 48) +

		    (((uint64_t) local_port) << 32) +

		    (((uint64_t) remote_lid) << 16) + ((uint64_t) remote_port);

		channel = cdg_search(*cdg_root, channelID);

		if (channel) {

			/* check whether last channel has connection to this channel, i.e. subpath already exists in cdg */

			linklist = last_channel->linklist;

			while (linklist && linklist->node != channel

			       && linklist->next)

				linklist = linklist->next;

			/* if there is no connection, add one */

			if (linklist) {

				if (linklist->node == channel) {

					set_next_srcdest_pair(linklist,

							      srcdest);

				} else {

					linklist->next =

					    (cdg_link_t *)

					    malloc(sizeof(cdg_link_t));

					if (!linklist->next)

						goto ERROR;

					linklist = linklist->next;

					linklist->node = channel;

					linklist->num_pairs = 0;

					linklist->srcdest_pairs = NULL;

					set_next_srcdest_pair(linklist,

							      srcdest);

					linklist->next = NULL;

				}

			} else {

				/* either this is the first channel of the path, or the last channel was a new channel, or last channel was a sink */

				last_channel->linklist =

				    (cdg_link_t *) malloc(sizeof(cdg_link_t));

				if (!last_channel->linklist)

					goto ERROR;

				last_channel->linklist->node = channel;

				last_channel->linklist->num_pairs = 0;

				last_channel->linklist->srcdest_pairs = NULL;

				set_next_srcdest_pair(last_channel->linklist,

						      srcdest);

				last_channel->linklist->next = NULL;

			}

		} else {

			/* create new channel */

			channel = (cdg_node_t *) malloc(sizeof(cdg_node_t));

			if (!channel)

				goto ERROR;

			set_default_cdg_node(channel);

			channel->channelID = channelID;

			cdg_insert(cdg_root, channel);

			/* go to end of link list of last channel */

			linklist = last_channel->linklist;

			while (linklist && linklist->next)

				linklist = linklist->next;

			if (linklist) {

				/* update last link of an existing channel */

				linklist->next =

				    (cdg_link_t *) malloc(sizeof(cdg_link_t));

				if (!linklist->next)

					goto ERROR;

				linklist = linklist->next;

				linklist->node = channel;

				linklist->num_pairs = 0;

				linklist->srcdest_pairs = NULL;

				set_next_srcdest_pair(linklist, srcdest);

				linklist->next = NULL;

			} else {

				/* either this is the first channel of the path, or the last channel was a new channel, or last channel was a sink */

				last_channel->linklist =

				    (cdg_link_t *) malloc(sizeof(cdg_link_t));

				if (!last_channel->linklist)

					goto ERROR;

				last_channel->linklist->node = channel;

				last_channel->linklist->num_pairs = 0;

				last_channel->linklist->srcdest_pairs = NULL;

				set_next_srcdest_pair(last_channel->linklist,

						      srcdest);

				last_channel->linklist->next = NULL;

			}

		}

		last_channel = channel;

	}

	if (channel_head->linklist) {

		if (channel_head->linklist->srcdest_pairs)

			free(channel_head->linklist->srcdest_pairs);

		free(channel_head->linklist);

	}

	free(channel_head);

	return 0;

ERROR:

	/* cleanup data and exit */

	if (channel_head) {

		if (channel_head->linklist)

			free(channel_head->linklist);

		free(channel_head);

	}

	return 1;

}

/* calculate the path from source to destination port;

   the links in the cdg representing this path are decremented to simulate the removal

*/

static int remove_path_from_cdg(cdg_node_t ** cdg_root, osm_port_t * src_port,

				uint16_t slid, osm_port_t * dest_port,

				uint16_t dlid)

{

	osm_node_t *local_node = NULL, *remote_node = NULL;

	uint16_t local_lid = 0, remote_lid = 0;

	uint8_t local_port = 0, remote_port = 0;

	uint64_t channelID = 0;

	cdg_node_t *channel_head = NULL, *channel = NULL, *last_channel = NULL;

	cdg_link_t *linklist = NULL;

	channel_head = (cdg_node_t *) malloc(sizeof(cdg_node_t));

	if (!channel_head)

		goto ERROR;

	set_default_cdg_node(channel_head);

	last_channel = channel_head;

	/* if src is a Hca, then the channel from Hca to switch would be a source in the graph

	   sources can't be part of a cycle -> skip this channel

	 */

	remote_node =

	    osm_node_get_remote_node(src_port->p_node,

				     src_port->p_physp->port_num, &remote_port);

	while (remote_node && remote_node->sw) {

		local_node = remote_node;

		local_port = local_node->sw->new_lft[dlid];

		/* sanity check: local_port must be set or routing is broken */

		if (local_port == OSM_NO_PATH)

			goto ERROR;

		local_lid = cl_ntoh16(osm_node_get_base_lid(local_node, 0));

		remote_node =

		    osm_node_get_remote_node(local_node, local_port,

					     &remote_port);

		/* if remote_node is a Hca, then the last channel from switch to Hca would be a sink in the cdg -> skip */

		if (!remote_node || !remote_node->sw)

			break;

		remote_lid = cl_ntoh16(osm_node_get_base_lid(remote_node, 0));

		channelID =

		    (((uint64_t) local_lid) << 48) +

		    (((uint64_t) local_port) << 32) +

		    (((uint64_t) remote_lid) << 16) + ((uint64_t) remote_port);

		channel = cdg_search(*cdg_root, channelID);

		if (channel) {

			/* check whether last channel has connection to this channel, i.e. subpath already exists in cdg */

			linklist = last_channel->linklist;

			while (linklist && linklist->node != channel

			       && linklist->next)

				linklist = linklist->next;

			/* remove the srcdest from the link */

			if (linklist) {

				if (linklist->node == channel) {

					linklist->removed++;

				} else {

					/* may happen if the link is missing (thru cycle detect algorithm) */

				}

			} else {

				/* may happen if the link is missing (thru cycle detect algorithm or last_channel==channel_head (dummy channel)) */

			}

		} else {

			/* must be an error, channels for the path are added before, so a missing channel would be a corrupt data structure */

			goto ERROR;

		}

		last_channel = channel;

	}

	if (channel_head->linklist)

		free(channel_head->linklist);

	free(channel_head);

	return 0;

ERROR:

	/* cleanup data and exit */

	if (channel_head) {

		if (channel_head->linklist)

			free(channel_head->linklist);

		free(channel_head);

	}

	return 1;

}

/**********************************************************************

 **********************************************************************/

/************ helper functions to generate an ordered list of ports ***

 ************ (functions copied from osm_ucast_mgr.c and modified) ****

 **********************************************************************/

static void add_sw_endports_to_order_list(osm_switch_t * sw,

					  osm_ucast_mgr_t * m,

					  cl_qmap_t * guid_tbl,

					  boolean_t add_guids)

{

	osm_port_t *port;

	ib_net64_t port_guid;

	uint64_t sw_guid;

	osm_physp_t *p;

	int i;

	boolean_t found;

	for (i = 1; i < sw->num_ports; i++) {

		p = osm_node_get_physp_ptr(sw->p_node, i);