Function graph_add_edge

freebsd/kern/kern_lockf.c:2231–2366

}

static int
graph_add_edge(struct owner_graph *g, struct owner_vertex *x,
    struct owner_vertex *y)
{
	struct owner_edge *e;
	struct owner_vertex_list deltaF, deltaB;
	int nF, n, vi, i;
	int *indices;
	int nB __unused;

	sx_assert(&lf_owner_graph_lock, SX_XLOCKED);

	LIST_FOREACH(e, &x->v_outedges, e_outlink) {
		if (e->e_to == y) {
			e->e_refs++;
			return (0);
		}
	}

#ifdef LOCKF_DEBUG
	if (lockf_debug & 8) {
		printf("adding edge %d:", x->v_order);
		lf_print_owner(x->v_owner);
		printf(" -> %d:", y->v_order);
		lf_print_owner(y->v_owner);
		printf("\n");
	}
#endif
	if (y->v_order < x->v_order) {
		/*
		 * The new edge violates the order. First find the set
		 * of affected vertices reachable from y (deltaF) and
		 * the set of affect vertices affected that reach x
		 * (deltaB), using the graph generation number to
		 * detect whether we have visited a given vertex
		 * already. We re-order the graph so that each vertex
		 * in deltaB appears before each vertex in deltaF.
		 *
		 * If x is a member of deltaF, then the new edge would
		 * create a cycle. Otherwise, we may assume that
		 * deltaF and deltaB are disjoint.
		 */
		g->g_gen++;
		if (g->g_gen == 0) {
			/*
			 * Generation wrap.
			 */
			for (vi = 0; vi < g->g_size; vi++) {
				g->g_vertices[vi]->v_gen = 0;
			}
			g->g_gen++;
		}
		nF = graph_delta_forward(g, x, y, &deltaF);
		if (nF < 0) {
#ifdef LOCKF_DEBUG
			if (lockf_debug & 8) {
				struct owner_vertex_list path;
				printf("deadlock: ");