src/libpspp/taint.c

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