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
45typedef
46   struct { UWord key_min; UWord key_max; UWord val; }
47   Range;
48
49
50struct _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 */
59static void preen (/*MOD*/RangeMap* rm);
60static Word find ( RangeMap* rm, UWord key );
61static void split_at ( /*MOD*/RangeMap* rm, UWord key );
62static void show ( RangeMap* rm );
63
64
65RangeMap* 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
92void 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
101void 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
118void 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
128Word VG_(sizeRangeMap) ( RangeMap* rm )
129{
130   vg_assert(rm && rm->ranges);
131   return VG_(sizeXA)(rm->ranges);
132}
133
134void 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
146static 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
163static 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
186static 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))
203static 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