exp-drd/drd_bitmap.h

/*
  This file is part of drd, a data race detector.

  Copyright (C) 2006-2008 Bart Van Assche
  bart.vanassche@gmail.com

  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.
*/


#ifndef __DRD_BITMAP3_H
#define __DRD_BITMAP3_H


#include "pub_tool_oset.h"


/*
  Bitmap representation. A bitmap is a data structure in which two bits are
  reserved per 32 bit address: one bit that indicates that the data at the
  specified address has been read, and one bit that indicates that the data has
  been written to.
*/


/* Macro definitions. */

#define ADDR0_BITS 12

#define ADDR0_COUNT ((UWord)1 << ADDR0_BITS)

#define ADDR0_MASK (ADDR0_COUNT - 1)

#define SPLIT_ADDRESS(a)            \
  UWord a##0 = ((a) & ADDR0_MASK);  \
  UWord a##1 = ((a) >> ADDR0_BITS);

// Assumption: sizeof(Addr) == sizeof(UWord).
#define MAKE_ADDRESS(a1, a0)  \
  (Addr)(((UWord)(a1) << (ADDR0_BITS)) | ((UWord)(a0)))

#define BITS_PER_UWORD (8UL*sizeof(UWord))
#if defined(VGA_x86) || defined(VGA_ppc32)
#define BITS_PER_BITS_PER_UWORD 5
#elif defined(VGA_amd64) || defined(VGA_ppc64)
#define BITS_PER_BITS_PER_UWORD 6
#else
#error Unknown platform.
#endif

#define BITMAP1_UWORD_COUNT (ADDR0_COUNT >> BITS_PER_BITS_PER_UWORD)

/* Highest bits of an address that fit into the same UWord of bm0[]. */
#define UWORD_MSB(a) ((a) & ~(BITS_PER_UWORD - 1))

/* Lowest bits of an address that fit into the same UWord of bm0[]. */
#define UWORD_LSB(a) ((a) & (BITS_PER_UWORD - 1))

/* Highest address that fits in the same UWord as a. */
#define UWORD_HIGHEST_ADDRESS(a) ((a) | (BITS_PER_UWORD - 1))


// Local constants.

static ULong s_bitmap2_creation_count;


/* Lowest level, corresponding to the lowest ADDR0_BITS of an address. */
struct bitmap1
{
  UWord bm0_r[BITMAP1_UWORD_COUNT];
  UWord bm0_w[BITMAP1_UWORD_COUNT];
};

static __inline__ UWord bm0_mask(const Addr a)
{
  return ((UWord)1 << UWORD_LSB(a));
}

static __inline__ void bm0_set(UWord* bm0, const Addr a)
{
  //tl_assert(a < ADDR0_COUNT);
  bm0[a >> BITS_PER_BITS_PER_UWORD] |= (UWord)1 << UWORD_LSB(a);
}

/** Set all of the addresses in range a1..a2 (inclusive) in bitmap bm0. */
static __inline__ void bm0_set_range(UWord* bm0, const Addr a1, const Addr a2)
{
#if 0
  tl_assert(a1 < ADDR0_COUNT);
  tl_assert(a2 < ADDR0_COUNT);
  tl_assert(a1 <= a2);
  tl_assert(UWORD_MSB(a1) == UWORD_MSB(a2));
#endif
  bm0[a1 >> BITS_PER_BITS_PER_UWORD]
    |= ((UWord)2 << UWORD_LSB(a2)) - ((UWord)1 << UWORD_LSB(a1));
}

static __inline__ void bm0_clear(UWord* bm0, const Addr a)
{
  //tl_assert(a < ADDR0_COUNT);
  bm0[a >> BITS_PER_BITS_PER_UWORD] &= ~((UWord)1 << UWORD_LSB(a));
}

static __inline__ UWord bm0_is_set(const UWord* bm0, const Addr a)
{
  //tl_assert(a < ADDR0_COUNT);
  return (bm0[a >> BITS_PER_BITS_PER_UWORD] & ((UWord)1 << UWORD_LSB(a)));
}

/** Return true if any of the bits a1..a2 (inclusive) are set in bm0. */
static __inline__ UWord bm0_is_any_set(const UWord* bm0,
                                       const Addr a1, const Addr a2)
{
#if 0
  tl_assert(a1 < ADDR0_COUNT);
  tl_assert(a2 < ADDR0_COUNT);
  tl_assert(a1 <= a2);
  tl_assert(UWORD_MSB(a1) == UWORD_MSB(a2));
#endif
  return (bm0[a1 >> BITS_PER_BITS_PER_UWORD]
          & (((UWord)2 << UWORD_LSB(a2)) - ((UWord)1 << UWORD_LSB(a1))));
}

struct bitmap2
{
  Addr           addr; ///< address >> ADDR0_BITS
  struct bitmap1 bm1;
};

/* Complete bitmap. */
struct bitmap
{
  Addr            last_lookup_a1;
  struct bitmap2* last_lookup_result;
  OSet*           oset;
};

static __inline__
struct bitmap2* bm_lookup(const struct bitmap* const bm, const Addr a)
{
  struct bitmap2* result;
  const UWord a1 = a >> ADDR0_BITS;
  if (a1 == bm->last_lookup_a1)
  {
    //tl_assert(bm->last_lookup_result == VG_(OSetGen_Lookup)(bm->oset, &a1));
    return bm->last_lookup_result;
  }
  result = VG_(OSetGen_Lookup)(bm->oset,&a1);
  if (result)
  {
    ((struct bitmap*)bm)->last_lookup_a1     = a1;
    ((struct bitmap*)bm)->last_lookup_result = result;
  }
  return result;
}

static __inline__
struct bitmap2* bm2_insert(const struct bitmap* const bm,
                           const UWord a1)
{
  struct bitmap2* const node = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*node));
  node->addr = a1;
  VG_(memset)(&node->bm1, 0, sizeof(node->bm1));
  VG_(OSetGen_Insert)(bm->oset, node);
  
  ((struct bitmap*)bm)->last_lookup_a1     = a1;
  ((struct bitmap*)bm)->last_lookup_result = node;
  
  s_bitmap2_creation_count++;
  
  return node;
}

static __inline__
struct bitmap2* bm2_lookup_or_insert(const struct bitmap* const bm,
                                     const UWord a1)
{
  struct bitmap2* p2;

  if (a1 == bm->last_lookup_a1)
  {
    //tl_assert(bm->last_lookup_result == VG_(OSetGen_Lookup)(bm->oset, &a1));
    return bm->last_lookup_result;
  }

  p2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
  if (p2 == 0)
  {
    p2 = bm2_insert(bm, a1);
  }
  ((struct bitmap*)bm)->last_lookup_a1     = a1;
  ((struct bitmap*)bm)->last_lookup_result = p2;
  return p2;
}


#endif /* __DRD_BITMAP3_H */