Home | History | Annotate | Download | only in coregrind 
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- A mapping where the keys exactly cover the address space.    ---*/
      4 /*---                                                 m_rangemap.c ---*/
      5 /*--------------------------------------------------------------------*/
      6 
      7 /*
      8    This file is part of Valgrind, a dynamic binary instrumentation
      9    framework.
     10 
     11    Copyright (C) 2014-2014 Mozilla Foundation
     12 
     13    This program is free software; you can redistribute it and/or
     14    modify it under the terms of the GNU General Public License as
     15    published by the Free Software Foundation; either version 2 of the
     16    License, or (at your option) any later version.
     17 
     18    This program is distributed in the hope that it will be useful, but
     19    WITHOUT ANY WARRANTY; without even the implied warranty of
     20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     21    General Public License for more details.
     22 
     23    You should have received a copy of the GNU General Public License
     24    along with this program; if not, write to the Free Software
     25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     26    02111-1307, USA.
     27 
     28    The GNU General Public License is contained in the file COPYING.
     29 */
     30 
     31 /* Contributed by Julian Seward <jseward (at) acm.org> */
     32 
     33 #include "pub_core_basics.h"
     34 #include "pub_core_libcassert.h"
     35 #include "pub_core_libcprint.h"
     36 #include "pub_core_xarray.h"
     37 #include "pub_core_rangemap.h"    /* self */
     38 
     39 
     40 /* See pub_tool_rangemap.h for details of what this is all about. */
     41 
     42 #define UWORD_MIN ((UWord)0)
     43 #define UWORD_MAX (~(UWord)0)
     44 
     45 typedef
     46    struct { UWord key_min; UWord key_max; UWord val; }
     47    Range;
     48 
     49 
     50 struct _RangeMap {
     51    void* (*alloc_fn) ( const HChar*, SizeT ); /* alloc fn (nofail) */
     52    const HChar* cc;                    /* cost centre for alloc */
     53    void  (*free_fn) ( void* );         /* free fn */
     54    XArray* ranges;
     55 };
     56 
     57 
     58 /* fwds */
     59 static void preen (/*MOD*/RangeMap* rm);
     60 static Word find ( const RangeMap* rm, UWord key );
     61 static void split_at ( /*MOD*/RangeMap* rm, UWord key );
     62 static void show ( const RangeMap* rm );
     63 
     64 
     65 RangeMap* VG_(newRangeMap) ( void*(*alloc_fn)(const HChar*,SizeT),
     66                              const HChar* cc,
     67                              void(*free_fn)(void*),
     68                              UWord initialVal )
     69 {
     70    /* check user-supplied info .. */
     71    vg_assert(alloc_fn);
     72    vg_assert(free_fn);
     73    RangeMap* rm = alloc_fn(cc, sizeof(RangeMap));
     74    rm->alloc_fn = alloc_fn;
     75    rm->cc       = cc;
     76    rm->free_fn  = free_fn;
     77    rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) );
     78    /* Add the initial range */
     79    Range r;
     80    r.key_min = UWORD_MIN;
     81    r.key_max = UWORD_MAX;
     82    r.val     = initialVal;
     83    Word i = VG_(addToXA)(rm->ranges, &r);
     84    vg_assert(i == 0);
     85    vg_assert(VG_(sizeXA)(rm->ranges) == 1);
     86    /* */
     87    return rm;
     88 }
     89 
     90 void VG_(deleteRangeMap) ( RangeMap* rm )
     91 {
     92    vg_assert(rm);
     93    vg_assert(rm->free_fn);
     94    vg_assert(rm->ranges);
     95    VG_(deleteXA)(rm->ranges);
     96    rm->free_fn(rm);
     97 }
     98 
     99 void VG_(bindRangeMap) ( RangeMap* rm,
    100                          UWord key_min, UWord key_max, UWord val )
    101 {
    102    vg_assert(key_min <= key_max);
    103    split_at(rm, key_min);
    104    if (key_max < UWORD_MAX)
    105       split_at(rm, key_max + 1);
    106    Word iMin, iMax, i;
    107    iMin = find(rm, key_min);
    108    iMax = find(rm, key_max);
    109    for (i = iMin; i <= iMax; i++) {
    110       Range* rng = VG_(indexXA)(rm->ranges, i);
    111       rng->val = val;
    112    }
    113    preen(rm);
    114 }
    115 
    116 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
    117                            /*OUT*/UWord* val, const RangeMap* rm, UWord key )
    118 {
    119    Word   i   = find(rm, key);
    120    Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
    121    *key_min = rng->key_min;
    122    *key_max = rng->key_max;
    123    *val     = rng->val;
    124 }
    125 
    126 Word VG_(sizeRangeMap) ( const RangeMap* rm )
    127 {
    128    vg_assert(rm && rm->ranges);
    129    return VG_(sizeXA)(rm->ranges);
    130 }
    131 
    132 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
    133                           /*OUT*/UWord* val, const RangeMap* rm, Word ix )
    134 {
    135    vg_assert(rm && rm->ranges);
    136    Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix);
    137    *key_min = rng->key_min;
    138    *key_max = rng->key_max;
    139    *val     = rng->val;
    140 }
    141 
    142 /* Helper functions, not externally visible. */
    143 
    144 static void preen (/*MOD*/RangeMap* rm)
    145 {
    146    Word    i;
    147    XArray* ranges = rm->ranges;
    148    for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) {
    149       Range* rng0 = VG_(indexXA)(ranges, i+0);
    150       Range* rng1 = VG_(indexXA)(ranges, i+1);
    151       if (rng0->val != rng1->val)
    152          continue;
    153       rng0->key_max = rng1->key_max;
    154       VG_(removeIndexXA)(ranges, i+1);
    155       /* Back up one, so as not to miss an opportunity to merge with
    156          the entry after this one. */
    157       i--;
    158    }
    159 }
    160 
    161 static Word find ( const RangeMap* rm, UWord key )
    162 {
    163    XArray* ranges = rm->ranges;
    164    Word    lo     = 0;
    165    Word    hi     = VG_(sizeXA)(ranges);
    166    while (True) {
    167       /* The unsearched space is lo .. hi inclusive */
    168       if (lo > hi) {
    169          /* Not found.  This can't happen. */
    170          VG_(core_panic)("RangeMap::find: not found");
    171          /*NOTREACHED*/
    172          return -1;
    173       }
    174       Word   mid         = (lo + hi) / 2;
    175       Range* mid_rng     = (Range*)VG_(indexXA)(ranges, mid);
    176       UWord  key_mid_min = mid_rng->key_min;
    177       UWord  key_mid_max = mid_rng->key_max;
    178       if (key < key_mid_min) { hi = mid-1; continue; }
    179       if (key > key_mid_max) { lo = mid+1; continue; }
    180       return mid;
    181    }
    182 }
    183 
    184 static void split_at ( /*MOD*/RangeMap* rm, UWord key )
    185 {
    186    XArray* ranges = rm->ranges;
    187    Word    i      = find(rm, key);
    188    Range   rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 );
    189    if (rng_i0.key_min == key)
    190       return;
    191    VG_(insertIndexXA)( ranges, i+1, &rng_i0 );
    192    /* The insert could have relocated the payload, hence the
    193       re-indexing of i+0 here. */
    194    Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 );
    195    Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 );
    196    rng_i0p->key_max = key-1;
    197    rng_i1p->key_min = key;
    198 }
    199 
    200 __attribute__((unused))
    201 static void show ( const RangeMap* rm )
    202 {
    203    Word i;
    204    VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) );
    205    for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) {
    206       Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
    207       VG_(printf)("  %016llx  %016llx  --> 0x%llx\n",
    208                   (ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val);
    209    }
    210    VG_(printf)(">>\n");
    211 }
    212 
    213 
    214 /*--------------------------------------------------------------------*/
    215 /*--- end                                             m_rangemap.c ---*/
    216 /*--------------------------------------------------------------------*/
    217