drd/drd_vc.c

/*
  This file is part of drd, a thread error detector.

  Copyright (C) 2006-2013 Bart Van Assche <bvanassche@acm.org>.

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  02111-1307, USA.

  The GNU General Public License is contained in the file COPYING.
*/


#include "drd_vc.h"
#include "pub_tool_basics.h"      // Addr, SizeT
#include "pub_tool_libcassert.h"  // tl_assert()
#include "pub_tool_libcbase.h"    // VG_(memcpy)
#include "pub_tool_libcprint.h"   // VG_(printf)
#include "pub_tool_mallocfree.h"  // VG_(malloc), VG_(free)


/* Local function declarations. */

static
void DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity);


/* Function definitions. */

/**
 * Initialize the memory 'vc' points at as a vector clock with size 'size'.
 * If the pointer 'vcelem' is not null, it is assumed to be an array with
 * 'size' elements and it becomes the initial value of the vector clock.
 */
void DRD_(vc_init)(VectorClock* const vc,
                   const VCElem* const vcelem,
                   const unsigned size)
{
   tl_assert(vc);
   vc->size = 0;
   vc->capacity = 0;
   vc->vc = 0;
   DRD_(vc_reserve)(vc, size);
   tl_assert(size == 0 || vc->vc != 0);
   if (vcelem)
   {
      VG_(memcpy)(vc->vc, vcelem, size * sizeof(vcelem[0]));
      vc->size = size;
   }
}

/** Reset vc to the empty vector clock. */
void DRD_(vc_cleanup)(VectorClock* const vc)
{
   DRD_(vc_reserve)(vc, 0);
}

/** Copy constructor -- initializes *new. */
void DRD_(vc_copy)(VectorClock* const new, const VectorClock* const rhs)
{
   DRD_(vc_init)(new, rhs->vc, rhs->size);
}

/** Assignment operator -- *lhs is already a valid vector clock. */
void DRD_(vc_assign)(VectorClock* const lhs, const VectorClock* const rhs)
{
   DRD_(vc_cleanup)(lhs);
   DRD_(vc_copy)(lhs, rhs);
}

/** Increment the clock of thread 'tid' in vector clock 'vc'. */
void DRD_(vc_increment)(VectorClock* const vc, DrdThreadId const tid)
{
   unsigned i;
   for (i = 0; i < vc->size; i++)
   {
      if (vc->vc[i].threadid == tid)
      {
         typeof(vc->vc[i].count) const oldcount = vc->vc[i].count;
         vc->vc[i].count++;
         // Check for integer overflow.
         tl_assert(oldcount < vc->vc[i].count);
         return;
      }
   }

   /*
    * The specified thread ID does not yet exist in the vector clock
    * -- insert it.
    */
   {
      const VCElem vcelem = { tid, 1 };
      VectorClock vc2;
      DRD_(vc_init)(&vc2, &vcelem, 1);
      DRD_(vc_combine)(vc, &vc2);
      DRD_(vc_cleanup)(&vc2);
   }
}

/**
 * @return True if vector clocks vc1 and vc2 are ordered, and false otherwise.
 * Order is as imposed by thread synchronization actions ("happens before").
 */
Bool DRD_(vc_ordered)(const VectorClock* const vc1,
                      const VectorClock* const vc2)
{
   return DRD_(vc_lte)(vc1, vc2) || DRD_(vc_lte)(vc2, vc1);
}

/** Compute elementwise minimum. */
void DRD_(vc_min)(VectorClock* const result, const VectorClock* const rhs)
{
   unsigned i;
   unsigned j;

   tl_assert(result);
   tl_assert(rhs);

   DRD_(vc_check)(result);

   /* Next, combine both vector clocks into one. */
   i = 0;
   for (j = 0; j < rhs->size; j++)
   {
      while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid)
      {
         /* Thread ID is missing in second vector clock. Clear the count. */
         result->vc[i].count = 0;
         i++;
      }
      if (i >= result->size)
      {
         break;
      }
      if (result->vc[i].threadid <= rhs->vc[j].threadid)
      {
         /* The thread ID is present in both vector clocks. Compute the */
         /* minimum of vc[i].count and vc[j].count. */
         tl_assert(result->vc[i].threadid == rhs->vc[j].threadid);
         if (rhs->vc[j].count < result->vc[i].count)
         {
            result->vc[i].count = rhs->vc[j].count;
         }
      }
   }
   DRD_(vc_check)(result);
}

/**
 * Compute elementwise maximum.
 */
void DRD_(vc_combine)(VectorClock* const result, const VectorClock* const rhs)
{
   unsigned i;
   unsigned j;
   unsigned shared;
   unsigned new_size;

   tl_assert(result);
   tl_assert(rhs);

   // First count the number of shared thread id's.
   j = 0;
   shared = 0;
   for (i = 0; i < result->size; i++)
   {
      while (j < rhs->size && rhs->vc[j].threadid < result->vc[i].threadid)
         j++;
      if (j >= rhs->size)
         break;
      if (result->vc[i].threadid == rhs->vc[j].threadid)
         shared++;
   }

   DRD_(vc_check)(result);

   new_size = result->size + rhs->size - shared;
   if (new_size > result->capacity)
      DRD_(vc_reserve)(result, new_size);

   DRD_(vc_check)(result);

   // Next, combine both vector clocks into one.
   i = 0;
   for (j = 0; j < rhs->size; j++)
   {
      /* First of all, skip those clocks in result->vc[] for which there */
      /* is no corresponding clock in rhs->vc[].                         */
      while (i < result->size && result->vc[i].threadid < rhs->vc[j].threadid)
      {
         i++;
      }
      /* If the end of *result is met, append rhs->vc[j] to *result. */
      if (i >= result->size)
      {
         result->size++;
         result->vc[i] = rhs->vc[j];
      }
      /* If clock rhs->vc[j] is not in *result, insert it. */
      else if (result->vc[i].threadid > rhs->vc[j].threadid)
      {
         unsigned k;
         for (k = result->size; k > i; k--)
         {
            result->vc[k] = result->vc[k - 1];
         }
         result->size++;
         result->vc[i] = rhs->vc[j];
      }
      /* Otherwise, both *result and *rhs have a clock for thread            */
      /* result->vc[i].threadid == rhs->vc[j].threadid. Compute the maximum. */
      else
      {
         tl_assert(result->vc[i].threadid == rhs->vc[j].threadid);
         if (rhs->vc[j].count > result->vc[i].count)
         {
            result->vc[i].count = rhs->vc[j].count;
         }
      }
   }
   DRD_(vc_check)(result);
   tl_assert(result->size == new_size);
}

/** Print the contents of vector clock 'vc'. */
void DRD_(vc_print)(const VectorClock* const vc)
{
   HChar* str;

   if ((str = DRD_(vc_aprint)(vc)) != NULL)
   {
      VG_(printf)("%s", str);
      VG_(free)(str);
   }
}

/**
 * Print the contents of vector clock 'vc' to a newly allocated string.
 * The caller must call VG_(free)() on the return value of this function.
 */
HChar* DRD_(vc_aprint)(const VectorClock* const vc)
{
   unsigned i;
   unsigned reserved;
   unsigned size;
   HChar* str = 0;

   tl_assert(vc);
   reserved = 64;
   size = 0;
   str = VG_(realloc)("drd.vc.aprint.1", str, reserved);
   if (! str)
      return str;
   size += VG_(snprintf)(str, reserved, "[");
   for (i = 0; i < vc->size; i++)
   {
      tl_assert(vc->vc);
      if (VG_(strlen)(str) + 32 > reserved)
      {
         reserved *= 2;
         str = VG_(realloc)("drd.vc.aprint.2", str, reserved);
         if (! str)
            return str;
      }
      size += VG_(snprintf)(str + size, reserved - size,
                            "%s %d: %d", i > 0 ? "," : "",
                            vc->vc[i].threadid, vc->vc[i].count);
   }
   size += VG_(snprintf)(str + size, reserved - size, " ]");

   return str;
}

/**
 * Invariant test.
 *
 * The function below tests whether the following two conditions are
 * satisfied:
 * - size <= capacity.
 * - Vector clock elements are stored in thread ID order.
 *
 * If one of these conditions is not met, an assertion failure is triggered.
 */
void DRD_(vc_check)(const VectorClock* const vc)
{
   unsigned i;
   tl_assert(vc->size <= vc->capacity);
   for (i = 1; i < vc->size; i++)
   {
      tl_assert(vc->vc[i-1].threadid < vc->vc[i].threadid);
   }
}

/**
 * Change the size of the memory block pointed at by vc->vc.
 * Changes capacity, but does not change size. If the size of the memory
 * block is increased, the newly allocated memory is not initialized.
 */
static
void DRD_(vc_reserve)(VectorClock* const vc, const unsigned new_capacity)
{
   tl_assert(vc);
   tl_assert(vc->capacity > VC_PREALLOCATED
             || vc->vc == 0
             || vc->vc == vc->preallocated);

   if (new_capacity > vc->capacity)
   {
      if (vc->vc && vc->capacity > VC_PREALLOCATED)
      {
         tl_assert(vc->vc
                   && vc->vc != vc->preallocated
                   && vc->capacity > VC_PREALLOCATED);
         vc->vc = VG_(realloc)("drd.vc.vr.1",
                               vc->vc, new_capacity * sizeof(vc->vc[0]));
      }
      else if (vc->vc && new_capacity > VC_PREALLOCATED)
      {
         tl_assert((vc->vc == 0 || vc->vc == vc->preallocated)
                   && new_capacity > VC_PREALLOCATED
                   && vc->capacity <= VC_PREALLOCATED);
         vc->vc = VG_(malloc)("drd.vc.vr.2",
                              new_capacity * sizeof(vc->vc[0]));
         VG_(memcpy)(vc->vc, vc->preallocated,
                     vc->capacity * sizeof(vc->vc[0]));
      }
      else if (vc->vc)
      {
         tl_assert(vc->vc == vc->preallocated
                   && new_capacity <= VC_PREALLOCATED
                   && vc->capacity <= VC_PREALLOCATED);
      }
      else if (new_capacity > VC_PREALLOCATED)
      {
         tl_assert(vc->vc == 0
                   && new_capacity > VC_PREALLOCATED
                   && vc->capacity == 0);
         vc->vc = VG_(malloc)("drd.vc.vr.3",
                              new_capacity * sizeof(vc->vc[0]));
      }
      else
      {
         tl_assert(vc->vc == 0
                   && new_capacity <= VC_PREALLOCATED
                   && vc->capacity == 0);
         vc->vc = vc->preallocated;
      }
      vc->capacity = new_capacity;
   }
   else if (new_capacity == 0 && vc->vc)
   {
      if (vc->capacity > VC_PREALLOCATED)
         VG_(free)(vc->vc);
      vc->vc = 0;
      vc->capacity = 0;
   }

   tl_assert(new_capacity == 0 || vc->vc != 0);
   tl_assert(vc->capacity > VC_PREALLOCATED
             || vc->vc == 0
             || vc->vc == vc->preallocated);
}