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@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 Word VG_(sizeRangeMap) ( const RangeMap* rm )
127 {
128 vg_assert(rm && rm->ranges);
129 return VG_(sizeXA)(rm->ranges);
130 }
131
VG_(indexRangeMap)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
preen(RangeMap * rm)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
find(const RangeMap * rm,UWord key)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
split_at(RangeMap * rm,UWord key)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))
show(const RangeMap * rm)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