drd_bitmap.c - Android社区 - https://www.androidos.net.cn/

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

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_basics.h"           /* DRD_() */
#include "drd_bitmap.h"
#include "drd_error.h"
#include "drd_suppression.h"
#include "pub_drd_bitmap.h"
#include "pub_tool_basics.h"      /* Addr, SizeT */
#include "pub_tool_debuginfo.h"   /* VG_(get_objname)() */
#include "pub_tool_libcassert.h"  /* tl_assert() */
#include "pub_tool_libcbase.h"    /* VG_(memset) */
#include "pub_tool_libcprint.h"   /* VG_(printf) */
#include "pub_tool_machine.h"     /* VG_(get_IP)() */
#include "pub_tool_mallocfree.h"  /* VG_(malloc), VG_(free) */

/* Local function declarations. */

static void bm2_merge(struct bitmap2* const bm2l,
                      const struct bitmap2* const bm2r);
static void bm2_print(const struct bitmap2* const bm2);

/* Local variables. */

static OSet* s_bm2_set_template;
static ULong s_bitmap_creation_count;
static ULong s_bitmap_merge_count;
static ULong s_bitmap2_merge_count;

/* Function definitions. */

void DRD_(bm_module_init)(void)
{
   tl_assert(!s_bm2_set_template);
   s_bm2_set_template
      = VG_(OSetGen_Create_With_Pool)(0, 0, VG_(malloc), "drd.bitmap.bn.2",
                                      VG_(free), 512, sizeof(struct bitmap2));
}

void DRD_(bm_module_cleanup)(void)
{
   tl_assert(s_bm2_set_template);
   VG_(OSetGen_Destroy)(s_bm2_set_template);
   s_bm2_set_template = NULL;
}

struct bitmap* DRD_(bm_new)()
{
   struct bitmap* bm;

/* If this assert fails, fix the definition of BITS_PER_BITS_PER_UWORD */
   /* in drd_bitmap.h.                                                    */
   tl_assert((1 << BITS_PER_BITS_PER_UWORD) == BITS_PER_UWORD);

bm = VG_(malloc)("drd.bitmap.bn.1", sizeof(*bm));
   DRD_(bm_init)(bm);

return bm;
}

void DRD_(bm_delete)(struct bitmap* const bm)
{
   tl_assert(bm);

DRD_(bm_cleanup)(bm);
   VG_(free)(bm);
}

/** Initialize *bm. */
void DRD_(bm_init)(struct bitmap* const bm)
{
   unsigned i;

tl_assert(bm);
   /*
    * Cache initialization. a1 is initialized with a value that never can
    * match any valid address: the upper (ADDR_LSB_BITS + ADDR_IGNORED_BITS)
    * bits of a1 are always zero for a valid cache entry.
    */
   for (i = 0; i < DRD_BITMAP_N_CACHE_ELEM; i++)
   {
      bm->cache[i].a1  = ~(UWord)1;
      bm->cache[i].bm2 = 0;
   }
   bm->oset = VG_(OSetGen_EmptyClone)(s_bm2_set_template);

s_bitmap_creation_count++;
}

/** Free the memory allocated by DRD_(bm_init)(). */
void DRD_(bm_cleanup)(struct bitmap* const bm)
{
   VG_(OSetGen_Destroy)(bm->oset);
}

/**
 * Record an access of type access_type at addresses a .. a + size - 1 in
 * bitmap bm.
 *
 * @note The current implementation of bm_access_range does not work for the
 * highest addresses in the address range. At least on Linux this is
 * not a problem since the upper part of the address space is reserved
 * for the kernel.
 */
void DRD_(bm_access_range)(struct bitmap* const bm,
                           const Addr a1, const Addr a2,
                           const BmAccessTypeT access_type)
{
   tl_assert(access_type == eLoad || access_type == eStore);

if (access_type == eLoad)
      return DRD_(bm_access_range_load)(bm, a1, a2);
   else
      return DRD_(bm_access_range_store)(bm, a1, a2);
}

void DRD_(bm_access_range_load)(struct bitmap* const bm, Addr a1, Addr a2)
{
   Addr b, b_next;

tl_assert(bm);
   tl_assert(a1 <= a2);
   tl_assert(a2 < first_address_with_higher_msb(a2));
   tl_assert(a1 == first_address_with_same_lsb(a1));
   tl_assert(a2 == first_address_with_same_lsb(a2));

for (b = a1; b < a2; b = b_next)
   {
      Addr b_start;
      Addr b_end;
      struct bitmap2* bm2;
      UWord b0;

b_next = first_address_with_higher_msb(b);
      if (b_next > a2)
      {
         b_next = a2;
      }

bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b));
      tl_assert(bm2);

if (make_address(bm2->addr, 0) < a1)
         b_start = a1;
      else
         if (make_address(bm2->addr, 0) < a2)
            b_start = make_address(bm2->addr, 0);
         else
            break;

if (make_address(bm2->addr + 1, 0) < a2)
         b_end = make_address(bm2->addr + 1, 0);
      else
         b_end = a2;

tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2);
      tl_assert(address_msb(b_start) == address_msb(b_end - 1));
      tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));

if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0)
      {
         unsigned k;

for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
         {
            bm2->bm1.bm0_r[k] = ~(UWord)0;
         }
      }
      else
      {
         for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
         {
            bm0_set(bm2->bm1.bm0_r, b0);
         }
      }
   }
}

void DRD_(bm_access_load_1)(struct bitmap* const bm, const Addr a1)
{
   bm_access_aligned_load(bm, a1, 1);
}

void DRD_(bm_access_load_2)(struct bitmap* const bm, const Addr a1)
{
   if ((a1 & 1) == 0)
      bm_access_aligned_load(bm, a1, 2);
   else
      DRD_(bm_access_range)(bm, a1, a1 + 2, eLoad);
}

void DRD_(bm_access_load_4)(struct bitmap* const bm, const Addr a1)
{
   if ((a1 & 3) == 0)
      bm_access_aligned_load(bm, a1, 4);
   else
      DRD_(bm_access_range)(bm, a1, a1 + 4, eLoad);
}

void DRD_(bm_access_load_8)(struct bitmap* const bm, const Addr a1)
{
   if ((a1 & 7) == 0)
      bm_access_aligned_load(bm, a1, 8);
   else if ((a1 & 3) == 0)
   {
      bm_access_aligned_load(bm, a1 + 0, 4);
      bm_access_aligned_load(bm, a1 + 4, 4);
   }
   else
      DRD_(bm_access_range)(bm, a1, a1 + 8, eLoad);
}

void DRD_(bm_access_range_store)(struct bitmap* const bm,
                                 const Addr a1, const Addr a2)
{
   Addr b, b_next;