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