src/libpspp/taint.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 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 "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 *
  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 *
  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
  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
 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
 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
 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
 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
 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 \f
 204 /* Initializes LIST as an empty list of taints. */
 205 static void
 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
 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
 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
 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
 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
 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 \f
 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
 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
 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