1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 #include "libpspp/taint.h"
20
21 #include <stddef.h>
22
23 #include "libpspp/array.h"
24 #include "libpspp/assertion.h"
25 #include "libpspp/cast.h"
26
27 #include "gl/xalloc.h"
28
29 /* This code maintains two invariants:
30
31 1. If a node is tainted, then all of its successors are
32 tainted.
33
34 2. If a node is tainted, then it and all of its predecessors are
35 successor-tainted. */
36
37 /* A list of pointers to taint structures. */
38 struct taint_list
39 {
40 size_t cnt;
41 struct taint **taints;
42 };
43
44 static void taint_list_init (struct taint_list *);
45 static void taint_list_destroy (struct taint_list *);
46 static void taint_list_add (struct taint_list *, struct taint *);
47 static void taint_list_remove (struct taint_list *, const struct taint *);
48
49 /* A taint. */
50 struct taint
51 {
52 size_t ref_cnt; /* Number of owners. */
53 struct taint_list successors; /* Successors in graph. */
54 struct taint_list predecessors; /* Predecessors in graph. */
55 bool tainted; /* Is this node tainted? */
56 bool tainted_successor; /* Is/was any derived taint tainted? */
57 };
58
59 static void recursively_set_taint (struct taint *);
60 static void recursively_set_tainted_successor (struct taint *);
61
62 /* Creates and returns a new taint object. */
63 struct taint *
taint_create(void)64 taint_create (void)
65 {
66 struct taint *taint = xmalloc (sizeof *taint);
67 taint->ref_cnt = 1;
68 taint_list_init (&taint->successors);
69 taint_list_init (&taint->predecessors);
70 taint->tainted = false;
71 taint->tainted_successor = false;
72 return taint;
73 }
74
75 /* Returns a clone of the given TAINT.
76 The new and old taint objects are logically indistinguishable,
77 as if they were the same object. (In this implementation,
78 they are in fact the same object, but this is not a guarantee
79 made by the interface.) */
80 struct taint *
taint_clone(const struct taint * taint_)81 taint_clone (const struct taint *taint_)
82 {
83 struct taint *taint = CONST_CAST (struct taint *, taint_);
84
85 assert (taint->ref_cnt > 0);
86 taint->ref_cnt++;
87 return taint;
88 }
89
90 /* Destroys the given TAINT.
91 Returns false if TAINT was tainted, true otherwise.
92 Any propagation relationships through TAINT are preserved.
93 That is, if A taints B and B taints C, then destroying B will
94 preserve the transitive relationship, so that tainting A will
95 still taint C. */
96 bool
taint_destroy(struct taint * taint)97 taint_destroy (struct taint *taint)
98 {
99 if (taint)
100 {
101 bool was_tainted = taint_is_tainted (taint);
102 if (--taint->ref_cnt == 0)
103 {
104 size_t i, j;
105
106 for (i = 0; i < taint->predecessors.cnt; i++)
107 for (j = 0; j < taint->successors.cnt; j++)
108 taint_propagate (taint->predecessors.taints[i],
109 taint->successors.taints[j]);
110
111 for (i = 0; i < taint->predecessors.cnt; i++)
112 taint_list_remove (&taint->predecessors.taints[i]->successors, taint);
113 for (i = 0; i < taint->successors.cnt; i++)
114 taint_list_remove (&taint->successors.taints[i]->predecessors, taint);
115
116 taint_list_destroy (&taint->successors);
117 taint_list_destroy (&taint->predecessors);
118 free (taint);
119 }
120 return !was_tainted;
121 }
122
123 return true;
124 }
125
126 /* Adds a propagation relationship from FROM to TO. This means
127 that, should FROM ever become tainted, then TO will
128 automatically be marked tainted as well. This takes effect
129 immediately: if FROM is currently tainted, then TO will be
130 tainted after the call completes.
131
132 Taint propagation is transitive: if A propagates to B and B
133 propagates to C, then tainting A taints both B and C. Taint
134 propagation is not commutative: propagation from A to B does
135 not imply propagation from B to A. Taint propagation is
136 robust against loops, so that if A propagates to B and vice
137 versa, whether directly or indirectly, then tainting either A
138 or B will cause the other to be tainted, without producing an
139 infinite loop. */
140 void
taint_propagate(const struct taint * from_,const struct taint * to_)141 taint_propagate (const struct taint *from_, const struct taint *to_)
142 {
143 struct taint *from = CONST_CAST (struct taint *, from_);
144 struct taint *to = CONST_CAST (struct taint *, to_);
145
146 if (from != to)
147 {
148 taint_list_add (&from->successors, to);
149 taint_list_add (&to->predecessors, from);
150 if (from->tainted && !to->tainted)
151 recursively_set_taint (to);
152 else if (to->tainted_successor && !from->tainted_successor)
153 recursively_set_tainted_successor (from);
154 }
155 }
156
157 /* Returns true if TAINT is tainted, false otherwise. */
158 bool
taint_is_tainted(const struct taint * taint)159 taint_is_tainted (const struct taint *taint)
160 {
161 return taint->tainted;
162 }
163
164 /* Marks TAINT tainted and propagates the taint to all of its
165 successors. */
166 void
taint_set_taint(const struct taint * taint_)167 taint_set_taint (const struct taint *taint_)
168 {
169 struct taint *taint = CONST_CAST (struct taint *, taint_);
170 if (!taint->tainted)
171 recursively_set_taint (taint);
172 }
173
174 /* Returns true if TAINT is successor-tainted, that is, if it or
175 any of its successors is or ever has been tainted. (A
176 "successor" of a taint object X is any taint object that can
177 be reached by following propagation relationships starting
178 from X.) */
179 bool
taint_has_tainted_successor(const struct taint * taint)180 taint_has_tainted_successor (const struct taint *taint)
181 {
182 return taint->tainted_successor;
183 }
184
185 /* Attempts to reset the successor-taint on TAINT. This is
186 successful only if TAINT currently has no tainted successor. */
187 void
taint_reset_successor_taint(const struct taint * taint_)188 taint_reset_successor_taint (const struct taint *taint_)
189 {
190 struct taint *taint = CONST_CAST (struct taint *, taint_);
191
192 if (taint->tainted_successor)
193 {
194 size_t i;
195
196 for (i = 0; i < taint->successors.cnt; i++)
197 if (taint->successors.taints[i]->tainted_successor)
198 return;
199
200 taint->tainted_successor = false;
201 }
202 }
203
204 /* Initializes LIST as an empty list of taints. */
205 static void
taint_list_init(struct taint_list * list)206 taint_list_init (struct taint_list *list)
207 {
208 list->cnt = 0;
209 list->taints = NULL;
210 }
211
212 /* Destroys LIST. */
213 static void
taint_list_destroy(struct taint_list * list)214 taint_list_destroy (struct taint_list *list)
215 {
216 free (list->taints);
217 }
218
219 /* Returns true if TAINT is in LIST, false otherwise. */
220 static bool
taint_list_contains(const struct taint_list * list,const struct taint * taint)221 taint_list_contains (const struct taint_list *list, const struct taint *taint)
222 {
223 size_t i;
224
225 for (i = 0; i < list->cnt; i++)
226 if (list->taints[i] == taint)
227 return true;
228
229 return false;
230 }
231
232 /* Returns true if X is zero or a power of 2, false otherwise. */
233 static bool
is_zero_or_power_of_2(size_t x)234 is_zero_or_power_of_2 (size_t x)
235 {
236 return (x & (x - 1)) == 0;
237 }
238
239 /* Adds TAINT to LIST, if it isn't already in the list. */
240 static void
taint_list_add(struct taint_list * list,struct taint * taint)241 taint_list_add (struct taint_list *list, struct taint *taint)
242 {
243 if (!taint_list_contains (list, taint))
244 {
245 /* To save a few bytes of memory per list, we don't store
246 the list capacity as a separate member. Instead, the
247 list capacity is always zero or a power of 2. Thus, if
248 the list count is one of these threshold values, we need
249 to allocate more memory. */
250 if (is_zero_or_power_of_2 (list->cnt))
251 list->taints = xnrealloc (list->taints,
252 list->cnt == 0 ? 1 : 2 * list->cnt,
253 sizeof *list->taints);
254 list->taints[list->cnt++] = taint;
255 }
256 }
257
258 /* Removes TAINT from LIST (which must contain it). */
259 static void
taint_list_remove(struct taint_list * list,const struct taint * taint)260 taint_list_remove (struct taint_list *list, const struct taint *taint)
261 {
262 size_t i;
263
264 for (i = 0; i < list->cnt; i++)
265 if (list->taints[i] == taint)
266 {
267 remove_element (list->taints, list->cnt, sizeof *list->taints, i);
268 list->cnt--;
269 return;
270 }
271
272 NOT_REACHED ();
273 }
274
275 /* Marks TAINT as tainted, as well as all of its successors
276 recursively. Also marks TAINT's predecessors as
277 successor-tainted, recursively. */
278 static void
recursively_set_taint(struct taint * taint)279 recursively_set_taint (struct taint *taint)
280 {
281 size_t i;
282
283 taint->tainted = taint->tainted_successor = true;
284 for (i = 0; i < taint->successors.cnt; i++)
285 {
286 struct taint *s = taint->successors.taints[i];
287 if (!s->tainted)
288 recursively_set_taint (s);
289 }
290 for (i = 0; i < taint->predecessors.cnt; i++)
291 {
292 struct taint *p = taint->predecessors.taints[i];
293 if (!p->tainted_successor)
294 recursively_set_tainted_successor (p);
295 }
296 }
297
298 /* Marks TAINT as successor-tainted, as well as all of its
299 predecessors recursively. */
300 static void
recursively_set_tainted_successor(struct taint * taint)301 recursively_set_tainted_successor (struct taint *taint)
302 {
303 size_t i;
304
305 taint->tainted_successor = true;
306 for (i = 0; i < taint->predecessors.cnt; i++)
307 {
308 struct taint *p = taint->predecessors.taints[i];
309 if (!p->tainted_successor)
310 recursively_set_tainted_successor (p);
311 }
312 }
313
314