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   if ( 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   return true;
 123 }
 124
 125 /* Adds a propagation relationship from FROM to TO.  This means
 126    that, should FROM ever become tainted, then TO will
 127    automatically be marked tainted as well.  This takes effect
 128    immediately: if FROM is currently tainted, then TO will be
 129    tainted after the call completes.
 130
 131    Taint propagation is transitive: if A propagates to B and B
 132    propagates to C, then tainting A taints both B and C.  Taint
 133    propagation is not commutative: propagation from A to B does
 134    not imply propagation from B to A.  Taint propagation is
 135    robust against loops, so that if A propagates to B and vice
 136    versa, whether directly or indirectly, then tainting either A
 137    or B will cause the other to be tainted, without producing an
 138    infinite loop. */
 139 void
 140 taint_propagate (const struct taint *from_, const struct taint *to_)
 141 {
 142   struct taint *from = (struct taint *) from_;
 143   struct taint *to = (struct taint *) to_;
 144
 145   if (from != to)
 146     {
 147       taint_list_add (&from->successors, to);
 148       taint_list_add (&to->predecessors, from);
 149       if (from->tainted && !to->tainted)
 150         recursively_set_taint (to);
 151       else if (to->tainted_successor && !from->tainted_successor)
 152         recursively_set_tainted_successor (from);
 153     }
 154 }
 155
 156 /* Returns true if TAINT is tainted, false otherwise. */
 157 bool
 158 taint_is_tainted (const struct taint *taint)
 159 {
 160   return taint->tainted;
 161 }
 162
 163 /* Marks TAINT tainted and propagates the taint to all of its
 164    successors. */
 165 void
 166 taint_set_taint (const struct taint *taint_)
 167 {
 168   struct taint *taint = (struct taint *) taint_;
 169   if (!taint->tainted)
 170     recursively_set_taint (taint);
 171 }
 172
 173 /* Returns true if TAINT is successor-tainted, that is, if it or
 174    any of its successors is or ever has been tainted.  (A
 175    "successor" of a taint object X is any taint object that can
 176    be reached by following propagation relationships starting
 177    from X.) */
 178 bool
 179 taint_has_tainted_successor (const struct taint *taint)
 180 {
 181   return taint->tainted_successor;
 182 }
 183
 184 /* Attempts to reset the successor-taint on TAINT.  This is
 185    successful only if TAINT currently has no tainted successor. */
 186 void
 187 taint_reset_successor_taint (const struct taint *taint_)
 188 {
 189   struct taint *taint = (struct taint *) taint_;
 190
 191   if (taint->tainted_successor)
 192     {
 193       size_t i;
 194
 195       for (i = 0; i < taint->successors.cnt; i++)
 196         if (taint->successors.taints[i]->tainted_successor)
 197           return;
 198
 199       taint->tainted_successor = false;
 200     }
 201 }
 202 \f
 203 /* Initializes LIST as an empty list of taints. */
 204 static void
 205 taint_list_init (struct taint_list *list)
 206 {
 207   list->cnt = 0;
 208   list->taints = NULL;
 209 }
 210
 211 /* Destroys LIST. */
 212 static void
 213 taint_list_destroy (struct taint_list *list)
 214 {
 215   free (list->taints);
 216 }
 217
 218 /* Returns true if TAINT is in LIST, false otherwise. */
 219 static bool
 220 taint_list_contains (const struct taint_list *list, const struct taint *taint)
 221 {
 222   size_t i;
 223
 224   for (i = 0; i < list->cnt; i++)
 225     if (list->taints[i] == taint)
 226       return true;
 227
 228   return false;
 229 }
 230
 231 /* Returns true if X is zero or a power of 2, false otherwise. */
 232 static bool
 233 is_zero_or_power_of_2 (size_t x)
 234 {
 235   return (x & (x - 1)) == 0;
 236 }
 237
 238 /* Adds TAINT to LIST, if it isn't already in the list. */
 239 static void
 240 taint_list_add (struct taint_list *list, struct taint *taint)
 241 {
 242   if (!taint_list_contains (list, taint))
 243     {
 244       /* To save a few bytes of memory per list, we don't store
 245          the list capacity as a separate member.  Instead, the
 246          list capacity is always zero or a power of 2.  Thus, if
 247          the list count is one of these threshold values, we need
 248          to allocate more memory. */
 249       if (is_zero_or_power_of_2 (list->cnt))
 250         list->taints = xnrealloc (list->taints,
 251                                   list->cnt == 0 ? 1 : 2 * list->cnt,
 252                                   sizeof *list->taints);
 253       list->taints[list->cnt++] = taint;
 254     }
 255 }
 256
 257 /* Removes TAINT from LIST (which must contain it). */
 258 static void
 259 taint_list_remove (struct taint_list *list, const struct taint *taint)
 260 {
 261   size_t i;
 262
 263   for (i = 0; i < list->cnt; i++)
 264     if (list->taints[i] == taint)
 265       {
 266         remove_element (list->taints, list->cnt, sizeof *list->taints, i);
 267         list->cnt--;
 268         return;
 269       }
 270
 271   NOT_REACHED ();
 272 }
 273 \f
 274 /* Marks TAINT as tainted, as well as all of its successors
 275    recursively.  Also marks TAINT's predecessors as
 276    successor-tainted, recursively. */
 277 static void
 278 recursively_set_taint (struct taint *taint)
 279 {
 280   size_t i;
 281
 282   taint->tainted = taint->tainted_successor = true;
 283    for (i = 0; i < taint->successors.cnt; i++)
 284     {
 285       struct taint *s = taint->successors.taints[i];
 286       if (!s->tainted)
 287         recursively_set_taint (s);
 288     }
 289   for (i = 0; i < taint->predecessors.cnt; i++)
 290     {
 291       struct taint *p = taint->predecessors.taints[i];
 292       if (!p->tainted_successor)
 293         recursively_set_tainted_successor (p);
 294     }
 295 }
 296
 297 /* Marks TAINT as successor-tainted, as well as all of its
 298    predecessors recursively. */
 299 static void
 300 recursively_set_tainted_successor (struct taint *taint)
 301 {
 302   size_t i;
 303
 304   taint->tainted_successor = true;
 305   for (i = 0; i < taint->predecessors.cnt; i++)
 306     {
 307       struct taint *p = taint->predecessors.taints[i];
 308       if (!p->tainted_successor)
 309         recursively_set_tainted_successor (p);
 310     }
 311 }
 312