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) ( const HChar*, SizeT ); /* alloc fn (nofail) */
     52    const HChar* cc;                 /* cost centre for alloc */
     53    void  (*free) ( void* );         /* free fn */
     54    XArray* ranges;
     55 };
     56 
     57 
     58 /* fwds */
     59 static void preen (/*MOD*/RangeMap* rm);
     60 static Word find ( RangeMap* rm, UWord key );
     61 static void split_at ( /*MOD*/RangeMap* rm, UWord key );
     62 static void show ( 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    vg_assert(rm);
     75    rm->alloc  = alloc_fn;
     76    rm->cc     = cc;
     77    rm->free   = free_fn;
     78    rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) );
     79    vg_assert(rm->ranges);
     80    /* Add the initial range */
     81    Range r;
     82    r.key_min = UWORD_MIN;
     83    r.key_max = UWORD_MAX;
     84    r.val     = initialVal;
     85    Word i = VG_(addToXA)(rm->ranges, &r);
     86    vg_assert(i == 0);
     87    vg_assert(VG_(sizeXA)(rm->ranges) == 1);
     88    /* */
     89    return rm;
     90 }
     91 
     92 void VG_(deleteRangeMap) ( RangeMap* rm )
     93 {
     94    vg_assert(rm);
     95    vg_assert(rm->free);
     96    vg_assert(rm->ranges);
     97    VG_(deleteXA)(rm->ranges);
     98    rm->free(rm);
     99 }
    100 
    101 void VG_(bindRangeMap) ( RangeMap* rm,
    102                          UWord key_min, UWord key_max, UWord val )
    103 {
    104    vg_assert(key_min <= key_max);
    105    split_at(rm, key_min);
    106    if (key_max < UWORD_MAX)
    107       split_at(rm, key_max + 1);
    108    Word iMin, iMax, i;
    109    iMin = find(rm, key_min);
    110    iMax = find(rm, key_max);
    111    for (i = iMin; i <= iMax; i++) {
    112       Range* rng = VG_(indexXA)(rm->ranges, i);
    113       rng->val = val;
    114    }
    115    preen(rm);
    116 }
    117 
    118 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
    119                            /*OUT*/UWord* val, RangeMap* rm, UWord key )
    120 {
    121    Word   i   = find(rm, key);
    122    Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
    123    *key_min = rng->key_min;
    124    *key_max = rng->key_max;
    125    *val     = rng->val;
    126 }
    127 
    128 Word VG_(sizeRangeMap) ( RangeMap* rm )
    129 {
    130    vg_assert(rm && rm->ranges);
    131    return VG_(sizeXA)(rm->ranges);
    132 }
    133 
    134 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
    135                           /*OUT*/UWord* val, RangeMap* rm, Word ix )
    136 {
    137    vg_assert(rm && rm->ranges);
    138    Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix);
    139    *key_min = rng->key_min;
    140    *key_max = rng->key_max;
    141    *val     = rng->val;
    142 }
    143 
    144 /* Helper functions, not externally visible. */
    145 
    146 static void preen (/*MOD*/RangeMap* rm)
    147 {
    148    Word    i;
    149    XArray* ranges = rm->ranges;
    150    for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) {
    151       Range* rng0 = VG_(indexXA)(ranges, i+0);
    152       Range* rng1 = VG_(indexXA)(ranges, i+1);
    153       if (rng0->val != rng1->val)
    154          continue;
    155       rng0->key_max = rng1->key_max;
    156       VG_(removeIndexXA)(ranges, i+1);
    157       /* Back up one, so as not to miss an opportunity to merge with
    158          the entry after this one. */
    159       i--;
    160    }
    161 }
    162 
    163 static Word find ( RangeMap* rm, UWord key )
    164 {
    165    XArray* ranges = rm->ranges;
    166    Word    lo     = 0;
    167    Word    hi     = VG_(sizeXA)(ranges);
    168    while (True) {
    169       /* The unsearched space is lo .. hi inclusive */
    170       if (lo > hi) {
    171          /* Not found.  This can't happen. */
    172          VG_(core_panic)("RangeMap::find: not found");
    173          /*NOTREACHED*/
    174          return -1;
    175       }
    176       Word   mid         = (lo + hi) / 2;
    177       Range* mid_rng     = (Range*)VG_(indexXA)(ranges, mid);
    178       UWord  key_mid_min = mid_rng->key_min;
    179       UWord  key_mid_max = mid_rng->key_max;
    180       if (key < key_mid_min) { hi = mid-1; continue; }
    181       if (key > key_mid_max) { lo = mid+1; continue; }
    182       return mid;
    183    }
    184 }
    185 
    186 static void split_at ( /*MOD*/RangeMap* rm, UWord key )
    187 {
    188    XArray* ranges = rm->ranges;
    189    Word    i      = find(rm, key);
    190    Range   rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 );
    191    if (rng_i0.key_min == key)
    192       return;
    193    VG_(insertIndexXA)( ranges, i+1, &rng_i0 );
    194    /* The insert could have relocated the payload, hence the
    195       re-indexing of i+0 here. */
    196    Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 );
    197    Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 );
    198    rng_i0p->key_max = key-1;
    199    rng_i1p->key_min = key;
    200 }
    201 
    202 __attribute__((unused))
    203 static void show ( RangeMap* rm )
    204 {
    205    Word i;
    206    VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) );
    207    for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) {
    208       Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
    209       VG_(printf)("  %016llx  %016llx  --> 0x%llx\n",
    210                   (ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val);
    211    }
    212    VG_(printf)(">>\n");
    213 }
    214 
    215 
    216 /*--------------------------------------------------------------------*/
    217 /*--- end                                             m_rangemap.c ---*/
    218 /*--------------------------------------------------------------------*/
    219