Skip to content

Commit 5b6e13b

Browse files
knizhnikknizhnik
committed
Multimaster first sign of life
1 parent cbdf8bb commit 5b6e13b

File tree

3 files changed

+202
-0
lines changed

3 files changed

+202
-0
lines changed

‎contrib/multimaster/dtmd/include/ddd.h

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
#ifndef DDD_H
2+
3+
#include <stdbool.h>
4+
#include "transaction.h"
5+
6+
typedef struct Node {
7+
struct Node* collision;
8+
struct Edge* edges; /* local subgraph */
9+
nodeid_t node_id;
10+
} Node;
11+
12+
typedef struct Edge {
13+
L2List node; /* node of list of outgoing eedges */
14+
struct Edge* next; /* list of edges of local subgraph */
15+
struct Vertex* dst;
16+
struct Vertex* src;
17+
} Edge;
18+
19+
typedef struct Vertex
20+
{
21+
L2List outgoingEdges;
22+
struct Vertex* next;
23+
xid_t xid;
24+
int nIncomingEdges;
25+
int visited;
26+
int deadlock_duration;
27+
} Vertex;
28+
29+
typedef struct Graph
30+
{
31+
Vertex* hashtable[MAX_TRANSACTIONS];
32+
Edge* freeEdges;
33+
Vertex* freeVertexes;
34+
int marker;
35+
int min_deadlock_duration;
36+
} Graph;
37+
38+
typedef struct Cluster
39+
{
40+
Node* hashtable[MAX_STREAMS];
41+
} Cluster;
42+
43+
extern void initGraph(Graph* graph);
44+
extern void addSubgraph(Graph* graph, nodeid_t node_id, xid_t* xids, int n_xids);
45+
extern bool detectDeadLock(Graph* graph, xid_t root);
46+
47+
#endif

‎contrib/multimaster/dtmd/src/ddd.c

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
#include <stddef.h>
2+
#include <stdlib.h>
3+
#include <string.h>
4+
#include "ddd.h"
5+
6+
static bool recursiveTraverseGraph(Vertex* root, Vertex* v, int marker);
7+
8+
static Cluster cluster;
9+
10+
void initGraph(Graph* graph)
11+
{
12+
memset(graph->hashtable, 0, sizeof(graph->hashtable));
13+
graph->freeEdges = NULL;
14+
graph->freeVertexes = NULL;
15+
graph->marker = 0;
16+
}
17+
18+
static inline Edge* newEdge(Graph* graph)
19+
{
20+
Edge* edge = graph->freeEdges;
21+
if (edge == NULL) {
22+
edge = (Edge*)malloc(sizeof(Edge));
23+
} else {
24+
graph->freeEdges = edge->next;
25+
}
26+
return edge;
27+
}
28+
29+
static inline void freeVertex(Graph* graph, Vertex* vertex)
30+
{
31+
int h = vertex->xid % MAX_TRANSACTIONS;
32+
Vertex** vpp = &graph->hashtable[h];
33+
while (*vpp != vertex) {
34+
vpp = &(*vpp)->next;
35+
}
36+
*vpp = vertex->next;
37+
vertex->next = graph->freeVertexes;
38+
graph->freeVertexes = vertex;
39+
40+
}
41+
42+
static inline void freeEdge(Graph* graph, Edge* edge)
43+
{
44+
edge->next = graph->freeEdges;
45+
graph->freeEdges = edge;
46+
}
47+
48+
static inline Vertex* newVertex(Graph* graph)
49+
{
50+
Vertex* v = graph->freeVertexes;
51+
if (v == NULL) {
52+
v = (Vertex*)malloc(sizeof(Vertex));
53+
} else {
54+
graph->freeVertexes = v->next;
55+
}
56+
return v;
57+
}
58+
59+
static inline Vertex* findVertex(Graph* graph, xid_t xid)
60+
{
61+
xid_t h = xid % MAX_TRANSACTIONS;
62+
Vertex* v;
63+
for (v = graph->hashtable[h]; v != NULL; v = v->next) {
64+
if (v->xid == xid) {
65+
return v;
66+
}
67+
}
68+
v = newVertex(graph);
69+
l2_list_init(&v->outgoingEdges);
70+
v->xid = xid;
71+
v->nIncomingEdges = 0;
72+
v->next = graph->hashtable[h];
73+
graph->hashtable[h] = v;
74+
return v;
75+
}
76+
77+
static inline Node* findNode(Cluster* cluster, nodeid_t node_id)
78+
{
79+
size_t h = node_id % MAX_STREAMS;
80+
Node* node;
81+
for (node = cluster->hashtable[h]; node != NULL; node = node->collision) {
82+
if (node->node_id == node_id) {
83+
return node;
84+
}
85+
}
86+
node = (Node*)malloc(sizeof(Node));
87+
node->node_id = node_id;
88+
node->edges = NULL;
89+
node->collision = cluster->hashtable[h];
90+
cluster->hashtable[h] = node;
91+
return node;
92+
}
93+
94+
void addSubgraph(Graph* graph, nodeid_t node_id, xid_t* xids, int n_xids)
95+
{
96+
xid_t *last = xids + n_xids;
97+
Edge *e, *next, *edges = NULL;
98+
Node* node = findNode(&cluster, node_id);
99+
while (xids != last) {
100+
Vertex* src = findVertex(graph, *xids++);
101+
xid_t xid;
102+
while ((xid = *xids++) != 0) {
103+
Vertex* dst = findVertex(graph, xid);
104+
e = newEdge(graph);
105+
dst->nIncomingEdges += 1;
106+
e->dst = dst;
107+
e->src = src;
108+
e->next = edges;
109+
edges = e;
110+
l2_list_link(&src->outgoingEdges, &e->node);
111+
}
112+
}
113+
for (e = node->edges; e != NULL; e = next) {
114+
next = e->next;
115+
l2_list_unlink(&e->node);
116+
if (--e->dst->nIncomingEdges == 0 && l2_list_is_empty(&e->dst->outgoingEdges)) {
117+
freeVertex(graph, e->dst);
118+
}
119+
if (e->src->nIncomingEdges == 0 && l2_list_is_empty(&e->src->outgoingEdges)) {
120+
freeVertex(graph, e->src);
121+
}
122+
freeEdge(graph, e);
123+
}
124+
node->edges = edges;
125+
}
126+
127+
static bool recursiveTraverseGraph(Vertex* root, Vertex* v, int marker)
128+
{
129+
L2List* l;
130+
Edge* e;
131+
v->visited = marker;
132+
for (l = v->outgoingEdges.next; l != &v->outgoingEdges; l = e->node.next) {
133+
e = (Edge*)l;
134+
if (e->dst == root) {
135+
return true;
136+
} else if (e->dst->visited != marker && recursiveTraverseGraph(root, e->dst, marker)) { /* loop */
137+
return true;
138+
}
139+
}
140+
return false;
141+
}
142+
143+
bool detectDeadLock(Graph* graph, xid_t root)
144+
{
145+
Vertex* v;
146+
for (v = graph->hashtable[root % MAX_TRANSACTIONS]; v != NULL; v = v->next) {
147+
if (v->xid == root) {
148+
if (recursiveTraverseGraph(v, v, ++graph->marker)) {
149+
return true;
150+
}
151+
break;
152+
}
153+
}
154+
return false;
155+
}

‎contrib/multimaster/sockhub/sockhub

34 KB
Binary file not shown.

0 commit comments

Comments
 (0)