1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3 #ident "$Id$"
4 /*======
5 This file is part of PerconaFT.
6
7
8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22 ----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35
36 ----------------------------------------
37
38 Licensed under the Apache License, Version 2.0 (the "License");
39 you may not use this file except in compliance with the License.
40 You may obtain a copy of the License at
41
42 http://www.apache.org/licenses/LICENSE-2.0
43
44 Unless required by applicable law or agreed to in writing, software
45 distributed under the License is distributed on an "AS IS" BASIS,
46 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
47 See the License for the specific language governing permissions and
48 limitations under the License.
49 ======= */
50
51 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
52
53 #include <db.h>
54 #include <toku_assert.h>
55 #include <memory.h>
56 #include <string.h>
57
58 #include "txnid_set.h"
59 #include "wfg.h"
60
61 namespace toku {
62
63 // Create a lock request graph
create(void)64 void wfg::create(void) {
65 m_nodes.create();
66 }
67
68 // Destroy the internals of the lock request graph
destroy(void)69 void wfg::destroy(void) {
70 size_t n_nodes = m_nodes.size();
71 for (size_t i = 0; i < n_nodes; i++) {
72 node *n;
73 int r = m_nodes.fetch(i, &n);
74 invariant_zero(r);
75 invariant_notnull(n);
76 node::free(n);
77 }
78 m_nodes.destroy();
79 }
80
81 // Add an edge (a_id, b_id) to the graph
add_edge(TXNID a_txnid,TXNID b_txnid)82 void wfg::add_edge(TXNID a_txnid, TXNID b_txnid) {
83 node *a_node = find_create_node(a_txnid);
84 node *b_node = find_create_node(b_txnid);
85 a_node->edges.add(b_node->txnid);
86 }
87
88 // Return true if a node with the given transaction id exists in the graph.
89 // Return false otherwise.
node_exists(TXNID txnid)90 bool wfg::node_exists(TXNID txnid) {
91 node *n = find_node(txnid);
92 return n != NULL;
93 }
94
cycle_exists_from_node(node * target,node * head)95 bool wfg::cycle_exists_from_node(node *target, node *head) {
96 bool cycle_found = false;
97 head->visited = true;
98 size_t n_edges = head->edges.size();
99 for (size_t i = 0; i < n_edges && !cycle_found; i++) {
100 TXNID edge_id = head->edges.get(i);
101 if (target->txnid == edge_id) {
102 cycle_found = true;
103 } else {
104 node *new_head = find_node(edge_id);
105 if (new_head && !new_head->visited) {
106 cycle_found = cycle_exists_from_node(target, new_head);
107 }
108 }
109 }
110 head->visited = false;
111 return cycle_found;
112 }
113
114 // Return true if there exists a cycle from a given transaction id in the graph.
115 // Return false otherwise.
cycle_exists_from_txnid(TXNID txnid)116 bool wfg::cycle_exists_from_txnid(TXNID txnid) {
117 node *a_node = find_node(txnid);
118 bool cycles_found = false;
119 if (a_node) {
120 cycles_found = cycle_exists_from_node(a_node, a_node);
121 }
122 return cycles_found;
123 }
124
125 // Apply a given function f to all of the nodes in the graph. The apply function
126 // returns when the function f is called for all of the nodes in the graph, or the
127 // function f returns non-zero.
apply_nodes(int (* fn)(TXNID id,void * extra),void * extra)128 void wfg::apply_nodes(int (*fn)(TXNID id, void *extra), void *extra) {
129 int r = 0;
130 size_t n_nodes = m_nodes.size();
131 for (size_t i = 0; i < n_nodes && r == 0; i++) {
132 node *n;
133 r = m_nodes.fetch(i, &n);
134 invariant_zero(r);
135 r = fn(n->txnid, extra);
136 }
137 }
138
139 // Apply a given function f to all of the edges whose origin is a given node id.
140 // The apply function returns when the function f is called for all edges in the
141 // graph rooted at node id, or the function f returns non-zero.
apply_edges(TXNID txnid,int (* fn)(TXNID txnid,TXNID edge_txnid,void * extra),void * extra)142 void wfg::apply_edges(TXNID txnid,
143 int (*fn)(TXNID txnid, TXNID edge_txnid, void *extra), void *extra) {
144 node *n = find_node(txnid);
145 if (n) {
146 int r = 0;
147 size_t n_edges = n->edges.size();
148 for (size_t i = 0; i < n_edges && r == 0; i++) {
149 r = fn(txnid, n->edges.get(i), extra);
150 }
151 }
152 }
153
154 // find node by id
find_node(TXNID txnid)155 wfg::node *wfg::find_node(TXNID txnid) {
156 node *n = nullptr;
157 int r = m_nodes.find_zero<TXNID, find_by_txnid>(txnid, &n, nullptr);
158 invariant(r == 0 || r == DB_NOTFOUND);
159 return n;
160 }
161
162 // this is the omt comparison function
163 // nodes are compared by their txnid.
find_by_txnid(node * const & node_a,const TXNID & txnid_b)164 int wfg::find_by_txnid(node *const &node_a, const TXNID &txnid_b) {
165 TXNID txnid_a = node_a->txnid;
166 if (txnid_a < txnid_b) {
167 return -1;
168 } else if (txnid_a == txnid_b) {
169 return 0;
170 } else {
171 return 1;
172 }
173 }
174
175 // insert a new node
find_create_node(TXNID txnid)176 wfg::node *wfg::find_create_node(TXNID txnid) {
177 node *n;
178 uint32_t idx;
179 int r = m_nodes.find_zero<TXNID, find_by_txnid>(txnid, &n, &idx);
180 if (r == DB_NOTFOUND) {
181 n = node::alloc(txnid);
182 r = m_nodes.insert_at(n, idx);
183 invariant_zero(r);
184 }
185 invariant_notnull(n);
186 return n;
187 }
188
alloc(TXNID txnid)189 wfg::node *wfg::node::alloc(TXNID txnid) {
190 node *XCALLOC(n);
191 n->txnid = txnid;
192 n->visited = false;
193 n->edges.create();
194 return n;
195 }
196
free(wfg::node * n)197 void wfg::node::free(wfg::node *n) {
198 n->edges.destroy();
199 toku_free(n);
200 }
201
202 } /* namespace toku */
203