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