• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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-2015 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@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 
VG_(newRangeMap)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 
VG_(deleteRangeMap)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 
VG_(bindRangeMap)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 
VG_(lookupRangeMap)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 
VG_(sizeRangeMap)126 UInt VG_(sizeRangeMap) ( const RangeMap* rm )
127 {
128    vg_assert(rm && rm->ranges);
129    Word size = VG_(sizeXA)(rm->ranges);
130    vg_assert(size >= 0);
131    return size;
132 }
133 
VG_(indexRangeMap)134 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
135                           /*OUT*/UWord* val, const 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 
preen(RangeMap * rm)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 
find(const RangeMap * rm,UWord key)163 static Word find ( const 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 
split_at(RangeMap * rm,UWord key)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))
show(const RangeMap * rm)203 static void show ( const 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