• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2   This file is part of drd, a thread error detector.
3 
4   Copyright (C) 2006-2012 Bart Van Assche <bvanassche@acm.org>.
5 
6   This program is free software; you can redistribute it and/or
7   modify it under the terms of the GNU General Public License as
8   published by the Free Software Foundation; either version 2 of the
9   License, or (at your option) any later version.
10 
11   This program is distributed in the hope that it will be useful, but
12   WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   General Public License for more details.
15 
16   You should have received a copy of the GNU General Public License
17   along with this program; if not, write to the Free Software
18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19   02111-1307, USA.
20 
21   The GNU General Public License is contained in the file COPYING.
22 */
23 
24 
25 #include "drd_basics.h"           /* DRD_() */
26 #include "drd_bitmap.h"
27 #include "drd_error.h"
28 #include "drd_suppression.h"
29 #include "pub_drd_bitmap.h"
30 #include "pub_tool_basics.h"      /* Addr, SizeT */
31 #include "pub_tool_debuginfo.h"   /* VG_(get_objname)() */
32 #include "pub_tool_libcassert.h"  /* tl_assert() */
33 #include "pub_tool_libcbase.h"    /* VG_(memset) */
34 #include "pub_tool_libcprint.h"   /* VG_(printf) */
35 #include "pub_tool_machine.h"     /* VG_(get_IP)() */
36 #include "pub_tool_mallocfree.h"  /* VG_(malloc), VG_(free) */
37 
38 
39 /* Local function declarations. */
40 
41 static void bm2_merge(struct bitmap2* const bm2l,
42                       const struct bitmap2* const bm2r);
43 static void bm2_print(const struct bitmap2* const bm2);
44 
45 
46 /* Local variables. */
47 
48 static OSet* s_bm2_set_template;
49 static ULong s_bitmap_creation_count;
50 static ULong s_bitmap_merge_count;
51 static ULong s_bitmap2_merge_count;
52 
53 
54 /* Function definitions. */
55 
DRD_(bm_module_init)56 void DRD_(bm_module_init)(void)
57 {
58    tl_assert(!s_bm2_set_template);
59    s_bm2_set_template
60       = VG_(OSetGen_Create_With_Pool)(0, 0, VG_(malloc), "drd.bitmap.bn.2",
61                                       VG_(free), 512, sizeof(struct bitmap2));
62 }
63 
DRD_(bm_module_cleanup)64 void DRD_(bm_module_cleanup)(void)
65 {
66    tl_assert(s_bm2_set_template);
67    VG_(OSetGen_Destroy)(s_bm2_set_template);
68    s_bm2_set_template = NULL;
69 }
70 
DRD_(bm_new)71 struct bitmap* DRD_(bm_new)()
72 {
73    struct bitmap* bm;
74 
75    /* If this assert fails, fix the definition of BITS_PER_BITS_PER_UWORD */
76    /* in drd_bitmap.h.                                                    */
77    tl_assert((1 << BITS_PER_BITS_PER_UWORD) == BITS_PER_UWORD);
78 
79    bm = VG_(malloc)("drd.bitmap.bn.1", sizeof(*bm));
80    DRD_(bm_init)(bm);
81 
82    return bm;
83 }
84 
DRD_(bm_delete)85 void DRD_(bm_delete)(struct bitmap* const bm)
86 {
87    tl_assert(bm);
88 
89    DRD_(bm_cleanup)(bm);
90    VG_(free)(bm);
91 }
92 
93 /** Initialize *bm. */
DRD_(bm_init)94 void DRD_(bm_init)(struct bitmap* const bm)
95 {
96    unsigned i;
97 
98    tl_assert(bm);
99    /*
100     * Cache initialization. a1 is initialized with a value that never can
101     * match any valid address: the upper (ADDR_LSB_BITS + ADDR_IGNORED_BITS)
102     * bits of a1 are always zero for a valid cache entry.
103     */
104    for (i = 0; i < DRD_BITMAP_N_CACHE_ELEM; i++)
105    {
106       bm->cache[i].a1  = ~(UWord)1;
107       bm->cache[i].bm2 = 0;
108    }
109    bm->oset = VG_(OSetGen_EmptyClone)(s_bm2_set_template);
110 
111    s_bitmap_creation_count++;
112 }
113 
114 /** Free the memory allocated by DRD_(bm_init)(). */
DRD_(bm_cleanup)115 void DRD_(bm_cleanup)(struct bitmap* const bm)
116 {
117    VG_(OSetGen_Destroy)(bm->oset);
118 }
119 
120 /**
121  * Record an access of type access_type at addresses a .. a + size - 1 in
122  * bitmap bm.
123  *
124  * @note The current implementation of bm_access_range does not work for the
125  * highest addresses in the address range. At least on Linux this is
126  * not a problem since the upper part of the address space is reserved
127  * for the kernel.
128  */
DRD_(bm_access_range)129 void DRD_(bm_access_range)(struct bitmap* const bm,
130                            const Addr a1, const Addr a2,
131                            const BmAccessTypeT access_type)
132 {
133    tl_assert(access_type == eLoad || access_type == eStore);
134 
135    if (access_type == eLoad)
136       return DRD_(bm_access_range_load)(bm, a1, a2);
137    else
138       return DRD_(bm_access_range_store)(bm, a1, a2);
139 }
140 
DRD_(bm_access_range_load)141 void DRD_(bm_access_range_load)(struct bitmap* const bm, Addr a1, Addr a2)
142 {
143    Addr b, b_next;
144 
145    tl_assert(bm);
146    tl_assert(a1 <= a2);
147    tl_assert(a2 < first_address_with_higher_msb(a2));
148    tl_assert(a1 == first_address_with_same_lsb(a1));
149    tl_assert(a2 == first_address_with_same_lsb(a2));
150 
151    for (b = a1; b < a2; b = b_next)
152    {
153       Addr b_start;
154       Addr b_end;
155       struct bitmap2* bm2;
156       UWord b0;
157 
158       b_next = first_address_with_higher_msb(b);
159       if (b_next > a2)
160       {
161          b_next = a2;
162       }
163 
164       bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b));
165       tl_assert(bm2);
166 
167       if (make_address(bm2->addr, 0) < a1)
168          b_start = a1;
169       else
170          if (make_address(bm2->addr, 0) < a2)
171             b_start = make_address(bm2->addr, 0);
172          else
173             break;
174 
175       if (make_address(bm2->addr + 1, 0) < a2)
176          b_end = make_address(bm2->addr + 1, 0);
177       else
178          b_end = a2;
179 
180       tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2);
181       tl_assert(address_msb(b_start) == address_msb(b_end - 1));
182       tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
183 
184       if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0)
185       {
186          unsigned k;
187 
188          for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
189          {
190             bm2->bm1.bm0_r[k] = ~(UWord)0;
191          }
192       }
193       else
194       {
195          for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
196          {
197             bm0_set(bm2->bm1.bm0_r, b0);
198          }
199       }
200    }
201 }
202 
DRD_(bm_access_load_1)203 void DRD_(bm_access_load_1)(struct bitmap* const bm, const Addr a1)
204 {
205    bm_access_aligned_load(bm, a1, 1);
206 }
207 
DRD_(bm_access_load_2)208 void DRD_(bm_access_load_2)(struct bitmap* const bm, const Addr a1)
209 {
210    if ((a1 & 1) == 0)
211       bm_access_aligned_load(bm, a1, 2);
212    else
213       DRD_(bm_access_range)(bm, a1, a1 + 2, eLoad);
214 }
215 
DRD_(bm_access_load_4)216 void DRD_(bm_access_load_4)(struct bitmap* const bm, const Addr a1)
217 {
218    if ((a1 & 3) == 0)
219       bm_access_aligned_load(bm, a1, 4);
220    else
221       DRD_(bm_access_range)(bm, a1, a1 + 4, eLoad);
222 }
223 
DRD_(bm_access_load_8)224 void DRD_(bm_access_load_8)(struct bitmap* const bm, const Addr a1)
225 {
226    if ((a1 & 7) == 0)
227       bm_access_aligned_load(bm, a1, 8);
228    else if ((a1 & 3) == 0)
229    {
230       bm_access_aligned_load(bm, a1 + 0, 4);
231       bm_access_aligned_load(bm, a1 + 4, 4);
232    }
233    else
234       DRD_(bm_access_range)(bm, a1, a1 + 8, eLoad);
235 }
236 
DRD_(bm_access_range_store)237 void DRD_(bm_access_range_store)(struct bitmap* const bm,
238                                  const Addr a1, const Addr a2)
239 {
240    Addr b, b_next;
241 
242    tl_assert(bm);
243    tl_assert(a1 <= a2);
244    tl_assert(a2 < first_address_with_higher_msb(a2));
245    tl_assert(a1 == first_address_with_same_lsb(a1));
246    tl_assert(a2 == first_address_with_same_lsb(a2));
247 
248    for (b = a1; b < a2; b = b_next)
249    {
250       Addr b_start;
251       Addr b_end;
252       struct bitmap2* bm2;
253       UWord b0;
254 
255       b_next = first_address_with_higher_msb(b);
256       if (b_next > a2)
257       {
258          b_next = a2;
259       }
260 
261       bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b));
262       tl_assert(bm2);
263 
264       if (make_address(bm2->addr, 0) < a1)
265          b_start = a1;
266       else
267          if (make_address(bm2->addr, 0) < a2)
268             b_start = make_address(bm2->addr, 0);
269          else
270             break;
271 
272       if (make_address(bm2->addr + 1, 0) < a2)
273          b_end = make_address(bm2->addr + 1, 0);
274       else
275          b_end = a2;
276 
277       tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2);
278       tl_assert(address_msb(b_start) == address_msb(b_end - 1));
279       tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
280 
281       if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0)
282       {
283          unsigned k;
284 
285          for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
286          {
287             bm2->bm1.bm0_w[k] = ~(UWord)0;
288          }
289       }
290       else
291       {
292          for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
293          {
294             bm0_set(bm2->bm1.bm0_w, b0);
295          }
296       }
297    }
298 }
299 
DRD_(bm_access_store_1)300 void DRD_(bm_access_store_1)(struct bitmap* const bm, const Addr a1)
301 {
302    bm_access_aligned_store(bm, a1, 1);
303 }
304 
DRD_(bm_access_store_2)305 void DRD_(bm_access_store_2)(struct bitmap* const bm, const Addr a1)
306 {
307    if ((a1 & 1) == 0)
308       bm_access_aligned_store(bm, a1, 2);
309    else
310       DRD_(bm_access_range)(bm, a1, a1 + 2, eStore);
311 }
312 
DRD_(bm_access_store_4)313 void DRD_(bm_access_store_4)(struct bitmap* const bm, const Addr a1)
314 {
315    if ((a1 & 3) == 0)
316       bm_access_aligned_store(bm, a1, 4);
317    else
318       DRD_(bm_access_range)(bm, a1, a1 + 4, eStore);
319 }
320 
DRD_(bm_access_store_8)321 void DRD_(bm_access_store_8)(struct bitmap* const bm, const Addr a1)
322 {
323    if ((a1 & 7) == 0)
324       bm_access_aligned_store(bm, a1, 8);
325    else if ((a1 & 3) == 0)
326    {
327       bm_access_aligned_store(bm, a1 + 0, 4);
328       bm_access_aligned_store(bm, a1 + 4, 4);
329    }
330    else
331       DRD_(bm_access_range)(bm, a1, a1 + 8, eStore);
332 }
333 
DRD_(bm_has)334 Bool DRD_(bm_has)(struct bitmap* const bm, const Addr a1, const Addr a2,
335                   const BmAccessTypeT access_type)
336 {
337    tl_assert(access_type == eLoad || access_type == eStore);
338 
339    if (access_type == eLoad)
340       return DRD_(bm_has_any_load)(bm, a1, a2);
341    else
342       return DRD_(bm_has_any_store)(bm, a1, a2);
343 }
344 
DRD_(bm_has_any_load_g)345 Bool DRD_(bm_has_any_load_g)(struct bitmap* const bm)
346 {
347    struct bitmap2* bm2;
348 
349    tl_assert(bm);
350 
351    VG_(OSetGen_ResetIter)(bm->oset);
352    for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != NULL; ) {
353       Addr b_start;
354       Addr b_end;
355       UWord b0;
356       const struct bitmap1* const p1 = &bm2->bm1;
357 
358       b_start = make_address(bm2->addr, 0);
359       b_end = make_address(bm2->addr + 1, 0);
360 
361       for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
362          if (bm0_is_set(p1->bm0_r, b0))
363             return True;
364    }
365    return False;
366 }
367 
368 Bool
DRD_(bm_has_any_load)369 DRD_(bm_has_any_load)(struct bitmap* const bm, const Addr a1, const Addr a2)
370 {
371    Addr b, b_next;
372 
373    tl_assert(bm);
374 
375    for (b = a1; b < a2; b = b_next)
376    {
377       const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
378 
379       b_next = first_address_with_higher_msb(b);
380       if (b_next > a2)
381       {
382          b_next = a2;
383       }
384 
385       if (bm2)
386       {
387          Addr b_start;
388          Addr b_end;
389          UWord b0;
390          const struct bitmap1* const p1 = &bm2->bm1;
391 
392          if (make_address(bm2->addr, 0) < a1)
393             b_start = a1;
394          else
395             if (make_address(bm2->addr, 0) < a2)
396                b_start = make_address(bm2->addr, 0);
397             else
398                break;
399          tl_assert(a1 <= b_start && b_start <= a2);
400 
401          if (make_address(bm2->addr + 1, 0) < a2)
402             b_end = make_address(bm2->addr + 1, 0);
403          else
404             b_end = a2;
405          tl_assert(a1 <= b_end && b_end <= a2);
406          tl_assert(b_start < b_end);
407          tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
408 
409          for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
410          {
411             if (bm0_is_set(p1->bm0_r, b0))
412             {
413                return True;
414             }
415          }
416       }
417    }
418    return 0;
419 }
420 
DRD_(bm_has_any_store)421 Bool DRD_(bm_has_any_store)(struct bitmap* const bm,
422                             const Addr a1, const Addr a2)
423 {
424    Addr b, b_next;
425 
426    tl_assert(bm);
427 
428    for (b = a1; b < a2; b = b_next)
429    {
430       const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
431 
432       b_next = first_address_with_higher_msb(b);
433       if (b_next > a2)
434       {
435          b_next = a2;
436       }
437 
438       if (bm2)
439       {
440          Addr b_start;
441          Addr b_end;
442          UWord b0;
443          const struct bitmap1* const p1 = &bm2->bm1;
444 
445          if (make_address(bm2->addr, 0) < a1)
446             b_start = a1;
447          else
448             if (make_address(bm2->addr, 0) < a2)
449                b_start = make_address(bm2->addr, 0);
450             else
451                break;
452          tl_assert(a1 <= b_start && b_start <= a2);
453 
454          if (make_address(bm2->addr + 1, 0) < a2)
455             b_end = make_address(bm2->addr + 1, 0);
456          else
457             b_end = a2;
458          tl_assert(a1 <= b_end && b_end <= a2);
459          tl_assert(b_start < b_end);
460          tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
461 
462          for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
463          {
464             if (bm0_is_set(p1->bm0_w, b0))
465             {
466                return True;
467             }
468          }
469       }
470    }
471    return 0;
472 }
473 
474 /* Return True if there is a read access, write access or both   */
475 /* to any of the addresses in the range [ a1, a2 [ in bitmap bm. */
DRD_(bm_has_any_access)476 Bool DRD_(bm_has_any_access)(struct bitmap* const bm,
477                              const Addr a1, const Addr a2)
478 {
479    Addr b, b_next;
480 
481    tl_assert(bm);
482 
483    for (b = a1; b < a2; b = b_next)
484    {
485       const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
486 
487       b_next = first_address_with_higher_msb(b);
488       if (b_next > a2)
489       {
490          b_next = a2;
491       }
492 
493       if (bm2)
494       {
495          Addr b_start;
496          Addr b_end;
497          UWord b0;
498          const struct bitmap1* const p1 = &bm2->bm1;
499 
500          if (make_address(bm2->addr, 0) < a1)
501             b_start = a1;
502          else
503             if (make_address(bm2->addr, 0) < a2)
504                b_start = make_address(bm2->addr, 0);
505             else
506                break;
507          tl_assert(a1 <= b_start && b_start <= a2);
508 
509          if (make_address(bm2->addr + 1, 0) < a2)
510             b_end = make_address(bm2->addr + 1, 0);
511          else
512             b_end = a2;
513          tl_assert(a1 <= b_end && b_end <= a2);
514          tl_assert(b_start < b_end);
515          tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
516 
517          for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
518          {
519             /*
520              * Note: the statement below uses a binary or instead of a logical
521              * or on purpose.
522              */
523             if (bm0_is_set(p1->bm0_r, b0) | bm0_is_set(p1->bm0_w, b0))
524             {
525                return True;
526             }
527          }
528       }
529    }
530    return False;
531 }
532 
533 /**
534  * Report whether an access of type access_type at address a is recorded in
535  * bitmap bm.
536  */
DRD_(bm_has_1)537 Bool DRD_(bm_has_1)(struct bitmap* const bm,
538                     const Addr a, const BmAccessTypeT access_type)
539 {
540    const struct bitmap2* p2;
541    const struct bitmap1* p1;
542    const UWord* p0;
543    const UWord a0 = address_lsb(a);
544 
545    tl_assert(bm);
546 
547    p2 = bm2_lookup(bm, address_msb(a));
548    if (p2)
549    {
550       p1 = &p2->bm1;
551       p0 = (access_type == eLoad) ? p1->bm0_r : p1->bm0_w;
552       return bm0_is_set(p0, a0) ? True : False;
553    }
554    return False;
555 }
556 
DRD_(bm_clear)557 void DRD_(bm_clear)(struct bitmap* const bm, Addr a1, Addr a2)
558 {
559    Addr b, b_next;
560 
561    tl_assert(bm);
562    tl_assert(a1);
563    tl_assert(a1 <= a2);
564    tl_assert(a1 == first_address_with_same_lsb(a1));
565    tl_assert(a2 == first_address_with_same_lsb(a2));
566 
567    for (b = a1; b < a2; b = b_next)
568    {
569       struct bitmap2* p2;
570       Addr c;
571 
572 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
573       tl_assert(a1 <= b && b < a2);
574 #endif
575 
576       p2 = bm2_lookup_exclusive(bm, address_msb(b));
577 
578       b_next = first_address_with_higher_msb(b);
579       if (b_next > a2)
580       {
581          b_next = a2;
582       }
583 
584       if (p2 == 0)
585          continue;
586 
587       c = b;
588       /* If the first address in the bitmap that must be cleared does not */
589       /* start on an UWord boundary, start clearing the first addresses.  */
590       if (uword_lsb(address_lsb(c)))
591       {
592          Addr c_next = first_address_with_higher_uword_msb(c);
593          if (c_next > b_next)
594             c_next = b_next;
595 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
596          tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next
597                    && b_next <= a2);
598 #endif
599          bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c));
600          bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c));
601          c = c_next;
602       }
603       /* If some UWords have to be cleared entirely, do this now. */
604       if (uword_lsb(address_lsb(c)) == 0)
605       {
606          Addr c_next = first_address_with_same_uword_lsb(b_next);
607 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
608          tl_assert(uword_lsb(address_lsb(c)) == 0);
609          tl_assert(uword_lsb(address_lsb(c_next)) == 0);
610          tl_assert(c_next <= b_next);
611 #endif
612          if (c_next > c)
613          {
614             UWord idx = uword_msb(address_lsb(c));
615             VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8));
616             VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8));
617             c = c_next;
618          }
619       }
620       /* If the last address in the bitmap that must be cleared does not */
621       /* fall on an UWord boundary, clear the last addresses.            */
622 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
623       tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
624 #endif
625       bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c));
626       bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c));
627    }
628 }
629 
630 /**
631  * Clear all references to loads in bitmap bm starting at address a1 and
632  * up to but not including address a2.
633  */
DRD_(bm_clear_load)634 void DRD_(bm_clear_load)(struct bitmap* const bm, Addr a1, Addr a2)
635 {
636    Addr b, b_next;
637 
638    tl_assert(bm);
639    tl_assert(a1);
640    tl_assert(a1 <= a2);
641    tl_assert(a1 == first_address_with_same_lsb(a1));
642    tl_assert(a2 == first_address_with_same_lsb(a2));
643 
644    for (b = a1; b < a2; b = b_next)
645    {
646       struct bitmap2* p2;
647       Addr c;
648 
649 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
650       tl_assert(a1 <= b && b < a2);
651 #endif
652 
653       p2 = bm2_lookup_exclusive(bm, address_msb(b));
654 
655       b_next = first_address_with_higher_msb(b);
656       if (b_next > a2)
657       {
658          b_next = a2;
659       }
660 
661       if (p2 == 0)
662          continue;
663 
664       c = b;
665       /* If the first address in the bitmap that must be cleared does not */
666       /* start on an UWord boundary, start clearing the first addresses.  */
667 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
668       tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2);
669 #endif
670       if (uword_lsb(address_lsb(c)))
671       {
672          Addr c_next = first_address_with_higher_uword_msb(c);
673          if (c_next > b_next)
674             c_next = b_next;
675 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
676          tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next
677                    && b_next <= a2);
678 #endif
679          bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c));
680          c = c_next;
681       }
682       /* If some UWords have to be cleared entirely, do this now. */
683 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
684       tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
685 #endif
686       if (uword_lsb(address_lsb(c)) == 0)
687       {
688          Addr c_next = first_address_with_same_uword_lsb(b_next);
689 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
690          tl_assert(uword_lsb(address_lsb(c)) == 0);
691          tl_assert(uword_lsb(address_lsb(c_next)) == 0);
692          tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next
693                    && b_next <= a2);
694 #endif
695          if (c_next > c)
696          {
697             UWord idx = uword_msb(address_lsb(c));
698             VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8));
699             c = c_next;
700          }
701       }
702       /* If the last address in the bitmap that must be cleared does not */
703       /* fall on an UWord boundary, clear the last addresses.            */
704 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
705       tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
706 #endif
707       bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c));
708    }
709 }
710 
711 /**
712  * Clear all references to stores in bitmap bm starting at address a1 and
713  * up to but not including address a2.
714  */
DRD_(bm_clear_store)715 void DRD_(bm_clear_store)(struct bitmap* const bm,
716                           const Addr a1, const Addr a2)
717 {
718    Addr b, b_next;
719 
720    tl_assert(bm);
721    tl_assert(a1);
722    tl_assert(a1 <= a2);
723    tl_assert(a1 == first_address_with_same_lsb(a1));
724    tl_assert(a2 == first_address_with_same_lsb(a2));
725 
726    for (b = a1; b < a2; b = b_next)
727    {
728       struct bitmap2* p2;
729       Addr c;
730 
731 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
732       tl_assert(a1 <= b && b < a2);
733 #endif
734 
735       p2 = bm2_lookup_exclusive(bm, address_msb(b));
736 
737       b_next = first_address_with_higher_msb(b);
738       if (b_next > a2)
739       {
740          b_next = a2;
741       }
742 
743       if (p2 == 0)
744          continue;
745 
746       c = b;
747       /* If the first address in the bitmap that must be cleared does not */
748       /* start on an UWord boundary, start clearing the first addresses.  */
749 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
750       tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2);
751 #endif
752       if (uword_lsb(address_lsb(c)))
753       {
754          Addr c_next = first_address_with_higher_uword_msb(c);
755          if (c_next > b_next)
756             c_next = b_next;
757 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
758          tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next
759                    && b_next <= a2);
760 #endif
761          bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c));
762          c = c_next;
763       }
764       /* If some UWords have to be cleared entirely, do this now. */
765 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
766       tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
767 #endif
768       if (uword_lsb(address_lsb(c)) == 0)
769       {
770          Addr c_next = first_address_with_same_uword_lsb(b_next);
771 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
772          tl_assert(uword_lsb(address_lsb(c)) == 0);
773          tl_assert(uword_lsb(address_lsb(c_next)) == 0);
774          tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next
775                    && b_next <= a2);
776 #endif
777          if (c_next > c)
778          {
779             UWord idx = uword_msb(address_lsb(c));
780             VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8));
781             c = c_next;
782          }
783       }
784       /* If the last address in the bitmap that must be cleared does not */
785       /* fall on an UWord boundary, clear the last addresses.            */
786 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
787       tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
788 #endif
789       bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c));
790    }
791 }
792 
793 /**
794  * Clear bitmap bm starting at address a1 and up to but not including address
795  * a2. Return True if and only if any of the addresses was set before
796  * clearing.
797  */
DRD_(bm_test_and_clear)798 Bool DRD_(bm_test_and_clear)(struct bitmap* const bm,
799                              const Addr a1, const Addr a2)
800 {
801    Bool result;
802 
803    result = DRD_(bm_has_any_access)(bm, a1, a2) != 0;
804    DRD_(bm_clear)(bm, a1, a2);
805    return result;
806 }
807 
DRD_(bm_has_conflict_with)808 Bool DRD_(bm_has_conflict_with)(struct bitmap* const bm,
809                                 const Addr a1, const Addr a2,
810                                 const BmAccessTypeT access_type)
811 {
812    Addr b, b_next;
813 
814    tl_assert(bm);
815 
816    for (b = a1; b < a2; b = b_next)
817    {
818       const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
819 
820       b_next = first_address_with_higher_msb(b);
821       if (b_next > a2)
822       {
823          b_next = a2;
824       }
825 
826       if (bm2)
827       {
828          Addr b_start;
829          Addr b_end;
830          UWord b0;
831          const struct bitmap1* const p1 = &bm2->bm1;
832 
833          if (make_address(bm2->addr, 0) < a1)
834             b_start = a1;
835          else
836             if (make_address(bm2->addr, 0) < a2)
837                b_start = make_address(bm2->addr, 0);
838             else
839                break;
840          tl_assert(a1 <= b_start && b_start <= a2);
841 
842          if (make_address(bm2->addr + 1, 0) < a2)
843             b_end = make_address(bm2->addr + 1, 0);
844          else
845             b_end = a2;
846          tl_assert(a1 <= b_end && b_end <= a2);
847          tl_assert(b_start < b_end);
848          tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
849 
850          for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
851          {
852             if (access_type == eLoad)
853             {
854                if (bm0_is_set(p1->bm0_w, b0))
855                {
856                   return True;
857                }
858             }
859             else
860             {
861                tl_assert(access_type == eStore);
862                if (bm0_is_set(p1->bm0_r, b0)
863                    | bm0_is_set(p1->bm0_w, b0))
864                {
865                   return True;
866                }
867             }
868          }
869       }
870    }
871    return False;
872 }
873 
DRD_(bm_load_has_conflict_with)874 Bool DRD_(bm_load_has_conflict_with)(struct bitmap* const bm,
875                                      const Addr a1, const Addr a2)
876 {
877    return DRD_(bm_has_conflict_with)(bm, a1, a2, eLoad);
878 }
879 
DRD_(bm_load_1_has_conflict_with)880 Bool DRD_(bm_load_1_has_conflict_with)(struct bitmap* const bm, const Addr a1)
881 {
882    return bm_aligned_load_has_conflict_with(bm, a1, 1);
883 }
884 
DRD_(bm_load_2_has_conflict_with)885 Bool DRD_(bm_load_2_has_conflict_with)(struct bitmap* const bm, const Addr a1)
886 {
887    if ((a1 & 1) == 0)
888       return bm_aligned_load_has_conflict_with(bm, a1, 2);
889    else
890       return DRD_(bm_has_conflict_with)(bm, a1, a1 + 2, eLoad);
891 }
892 
DRD_(bm_load_4_has_conflict_with)893 Bool DRD_(bm_load_4_has_conflict_with)(struct bitmap* const bm, const Addr a1)
894 {
895    if ((a1 & 3) == 0)
896       return bm_aligned_load_has_conflict_with(bm, a1, 4);
897    else
898       return DRD_(bm_has_conflict_with)(bm, a1, a1 + 4, eLoad);
899 }
900 
DRD_(bm_load_8_has_conflict_with)901 Bool DRD_(bm_load_8_has_conflict_with)(struct bitmap* const bm, const Addr a1)
902 {
903    if ((a1 & 7) == 0)
904       return bm_aligned_load_has_conflict_with(bm, a1, 8);
905    else
906       return DRD_(bm_has_conflict_with)(bm, a1, a1 + 8, eLoad);
907 }
908 
DRD_(bm_store_1_has_conflict_with)909 Bool DRD_(bm_store_1_has_conflict_with)(struct bitmap* const bm, const Addr a1)
910 {
911    return bm_aligned_store_has_conflict_with(bm, a1, 1);
912 }
913 
DRD_(bm_store_2_has_conflict_with)914 Bool DRD_(bm_store_2_has_conflict_with)(struct bitmap* const bm, const Addr a1)
915 {
916    if ((a1 & 1) == 0)
917       return bm_aligned_store_has_conflict_with(bm, a1, 2);
918    else
919       return DRD_(bm_has_conflict_with)(bm, a1, a1 + 2, eStore);
920 }
921 
DRD_(bm_store_4_has_conflict_with)922 Bool DRD_(bm_store_4_has_conflict_with)(struct bitmap* const bm, const Addr a1)
923 {
924    if ((a1 & 3) == 0)
925       return bm_aligned_store_has_conflict_with(bm, a1, 4);
926    else
927       return DRD_(bm_has_conflict_with)(bm, a1, a1 + 4, eStore);
928 }
929 
DRD_(bm_store_8_has_conflict_with)930 Bool DRD_(bm_store_8_has_conflict_with)(struct bitmap* const bm, const Addr a1)
931 {
932    if ((a1 & 7) == 0)
933       return bm_aligned_store_has_conflict_with(bm, a1, 8);
934    else
935       return DRD_(bm_has_conflict_with)(bm, a1, a1 + 8, eStore);
936 }
937 
DRD_(bm_store_has_conflict_with)938 Bool DRD_(bm_store_has_conflict_with)(struct bitmap* const bm,
939                                       const Addr a1, const Addr a2)
940 {
941    return DRD_(bm_has_conflict_with)(bm, a1, a2, eStore);
942 }
943 
944 /**
945  * Return True if the two bitmaps *lhs and *rhs are identical, and false
946  * if not.
947  */
DRD_(bm_equal)948 Bool DRD_(bm_equal)(struct bitmap* const lhs, struct bitmap* const rhs)
949 {
950    struct bitmap2* bm2l;
951    struct bitmap2* bm2r;
952 
953    /* It's not possible to have two independent iterators over the same OSet, */
954    /* so complain if lhs == rhs.                                              */
955    tl_assert(lhs != rhs);
956 
957    VG_(OSetGen_ResetIter)(lhs->oset);
958    VG_(OSetGen_ResetIter)(rhs->oset);
959 
960    for ( ; (bm2l = VG_(OSetGen_Next)(lhs->oset)) != 0; )
961    {
962       while (bm2l
963              && ! DRD_(bm_has_any_access)(lhs,
964                                           make_address(bm2l->addr, 0),
965                                           make_address(bm2l->addr + 1, 0)))
966       {
967          bm2l = VG_(OSetGen_Next)(lhs->oset);
968       }
969       if (bm2l == 0)
970          break;
971       tl_assert(bm2l);
972 
973       do
974       {
975          bm2r = VG_(OSetGen_Next)(rhs->oset);
976          if (bm2r == 0)
977             return False;
978       }
979       while (! DRD_(bm_has_any_access)(rhs,
980                                        make_address(bm2r->addr, 0),
981                                        make_address(bm2r->addr + 1, 0)));
982 
983       tl_assert(bm2r);
984       tl_assert(DRD_(bm_has_any_access)(rhs,
985                                         make_address(bm2r->addr, 0),
986                                         make_address(bm2r->addr + 1, 0)));
987 
988       if (bm2l != bm2r
989           && (bm2l->addr != bm2r->addr
990               || VG_(memcmp)(&bm2l->bm1, &bm2r->bm1, sizeof(bm2l->bm1)) != 0))
991       {
992          return False;
993       }
994    }
995 
996    do
997    {
998       bm2r = VG_(OSetGen_Next)(rhs->oset);
999    } while (bm2r && ! DRD_(bm_has_any_access)(rhs,
1000                                               make_address(bm2r->addr, 0),
1001                                               make_address(bm2r->addr + 1, 0)));
1002    if (bm2r)
1003    {
1004       tl_assert(DRD_(bm_has_any_access)(rhs,
1005                                         make_address(bm2r->addr, 0),
1006                                         make_address(bm2r->addr + 1, 0)));
1007       return False;
1008    }
1009    return True;
1010 }
1011 
DRD_(bm_swap)1012 void DRD_(bm_swap)(struct bitmap* const bm1, struct bitmap* const bm2)
1013 {
1014    OSet* const tmp = bm1->oset;
1015    bm1->oset = bm2->oset;
1016    bm2->oset = tmp;
1017 }
1018 
1019 /** Merge bitmaps *lhs and *rhs into *lhs. */
DRD_(bm_merge2)1020 void DRD_(bm_merge2)(struct bitmap* const lhs, struct bitmap* const rhs)
1021 {
1022    struct bitmap2* bm2l;
1023    struct bitmap2* bm2r;
1024 
1025    /*
1026     * It's not possible to have two independent iterators over the same OSet,
1027     * so complain if lhs == rhs.
1028     */
1029    tl_assert(lhs != rhs);
1030 
1031    s_bitmap_merge_count++;
1032 
1033    VG_(OSetGen_ResetIter)(rhs->oset);
1034 
1035    for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
1036    {
1037       bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
1038       if (bm2l)
1039       {
1040          tl_assert(bm2l != bm2r);
1041          bm2_merge(bm2l, bm2r);
1042       }
1043       else
1044       {
1045          bm2_insert_copy(lhs, bm2r);
1046       }
1047    }
1048 }
1049 
1050 /** Clear bitmap2::recalc. */
DRD_(bm_unmark)1051 void DRD_(bm_unmark)(struct bitmap* bm)
1052 {
1053    struct bitmap2* bm2;
1054 
1055    for (VG_(OSetGen_ResetIter)(bm->oset);
1056         (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
1057         )
1058    {
1059       bm2->recalc = False;
1060    }
1061 }
1062 
1063 /**
1064  * Report whether bitmap2::recalc has been set for the second level bitmap
1065  * corresponding to address a.
1066  */
DRD_(bm_is_marked)1067 Bool DRD_(bm_is_marked)(struct bitmap* bm, const Addr a)
1068 {
1069    const struct bitmap2* bm2;
1070 
1071    bm2 = bm2_lookup(bm, a);
1072    return bm2 && bm2->recalc;
1073 }
1074 
1075 /**
1076  * Set bitmap2::recalc in bml for each second level bitmap in bmr that contains
1077  * at least one access.
1078  *
1079  * @note Any new second-level bitmaps inserted in bml by this function are
1080  *       uninitialized.
1081  */
DRD_(bm_mark)1082 void DRD_(bm_mark)(struct bitmap* bml, struct bitmap* bmr)
1083 {
1084    struct bitmap2* bm2l;
1085    struct bitmap2* bm2r;
1086 
1087    for (VG_(OSetGen_ResetIter)(bmr->oset);
1088         (bm2r = VG_(OSetGen_Next)(bmr->oset)) != 0;
1089         )
1090    {
1091       bm2l = bm2_lookup_or_insert(bml, bm2r->addr);
1092       bm2l->recalc = True;
1093    }
1094 }
1095 
1096 /** Clear all second-level bitmaps for which bitmap2::recalc == True. */
DRD_(bm_clear_marked)1097 void DRD_(bm_clear_marked)(struct bitmap* bm)
1098 {
1099    struct bitmap2* bm2;
1100 
1101    for (VG_(OSetGen_ResetIter)(bm->oset);
1102         (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
1103         )
1104    {
1105       if (bm2->recalc)
1106          bm2_clear(bm2);
1107    }
1108 }
1109 
1110 /** Merge the second level bitmaps from *rhs into *lhs for which recalc == True. */
DRD_(bm_merge2_marked)1111 void DRD_(bm_merge2_marked)(struct bitmap* const lhs, struct bitmap* const rhs)
1112 {
1113    struct bitmap2* bm2l;
1114    struct bitmap2* bm2r;
1115 
1116    /*
1117     * It's not possible to have two independent iterators over the same OSet,
1118     * so complain if lhs == rhs.
1119     */
1120    tl_assert(lhs != rhs);
1121 
1122    s_bitmap_merge_count++;
1123 
1124    VG_(OSetGen_ResetIter)(rhs->oset);
1125 
1126    for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
1127    {
1128       bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
1129       if (bm2l && bm2l->recalc)
1130       {
1131          tl_assert(bm2l != bm2r);
1132          bm2_merge(bm2l, bm2r);
1133       }
1134    }
1135 }
1136 
1137 /** Remove all marked second-level bitmaps that do not contain any access. */
DRD_(bm_remove_cleared_marked)1138 void DRD_(bm_remove_cleared_marked)(struct bitmap* bm)
1139 {
1140    struct bitmap2* bm2;
1141 
1142    VG_(OSetGen_ResetIter)(bm->oset);
1143    for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; )
1144    {
1145       const UWord a1 = bm2->addr;
1146       if (bm2->recalc
1147           && ! DRD_(bm_has_any_access(bm, make_address(a1, 0),
1148                                       make_address(a1 + 1, 0))))
1149       {
1150          bm2_remove(bm, a1);
1151          VG_(OSetGen_ResetIterAt)(bm->oset, &a1);
1152       }
1153    }
1154 }
1155 
1156 /**
1157  * Report whether there are any RW / WR / WW patterns in lhs and rhs.
1158  * @param lhs First bitmap.
1159  * @param rhs Bitmap to be compared with lhs.
1160  * @return !=0 if there are data races, == 0 if there are none.
1161  */
DRD_(bm_has_races)1162 int DRD_(bm_has_races)(struct bitmap* const lhs, struct bitmap* const rhs)
1163 {
1164    VG_(OSetGen_ResetIter)(lhs->oset);
1165    VG_(OSetGen_ResetIter)(rhs->oset);
1166 
1167    for (;;)
1168    {
1169       const struct bitmap2* bm2l;
1170       const struct bitmap2* bm2r;
1171       const struct bitmap1* bm1l;
1172       const struct bitmap1* bm1r;
1173       unsigned k;
1174 
1175       bm2l = VG_(OSetGen_Next)(lhs->oset);
1176       bm2r = VG_(OSetGen_Next)(rhs->oset);
1177       while (bm2l && bm2r && bm2l->addr != bm2r->addr)
1178       {
1179          if (bm2l->addr < bm2r->addr)
1180             bm2l = VG_(OSetGen_Next)(lhs->oset);
1181          else
1182             bm2r = VG_(OSetGen_Next)(rhs->oset);
1183       }
1184       if (bm2l == 0 || bm2r == 0)
1185          break;
1186 
1187       bm1l = &bm2l->bm1;
1188       bm1r = &bm2r->bm1;
1189 
1190       for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
1191       {
1192          unsigned b;
1193          for (b = 0; b < BITS_PER_UWORD; b++)
1194          {
1195             UWord const access_mask
1196                = ((bm1l->bm0_r[k] & bm0_mask(b)) ? LHS_R : 0)
1197                | ((bm1l->bm0_w[k] & bm0_mask(b)) ? LHS_W : 0)
1198                | ((bm1r->bm0_r[k] & bm0_mask(b)) ? RHS_R : 0)
1199                | ((bm1r->bm0_w[k] & bm0_mask(b)) ? RHS_W : 0);
1200             Addr const a = make_address(bm2l->addr, k * BITS_PER_UWORD | b);
1201             if (HAS_RACE(access_mask) && ! DRD_(is_suppressed)(a, a + 1))
1202             {
1203                return 1;
1204             }
1205          }
1206       }
1207    }
1208    return 0;
1209 }
1210 
DRD_(bm_print)1211 void DRD_(bm_print)(struct bitmap* const bm)
1212 {
1213    struct bitmap2* bm2;
1214 
1215    for (VG_(OSetGen_ResetIter)(bm->oset);
1216         (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
1217         )
1218    {
1219       bm2_print(bm2);
1220    }
1221 }
1222 
bm2_print(const struct bitmap2 * const bm2)1223 static void bm2_print(const struct bitmap2* const bm2)
1224 {
1225    const struct bitmap1* bm1;
1226    Addr a;
1227 
1228    tl_assert(bm2);
1229 
1230    bm1 = &bm2->bm1;
1231    for (a = make_address(bm2->addr, 0);
1232         a <= make_address(bm2->addr + 1, 0) - 1;
1233         a++)
1234    {
1235       const Bool r = bm0_is_set(bm1->bm0_r, address_lsb(a)) != 0;
1236       const Bool w = bm0_is_set(bm1->bm0_w, address_lsb(a)) != 0;
1237       if (r || w)
1238       {
1239          VG_(printf)("0x%08lx %c %c\n",
1240                      a,
1241                      w ? 'W' : ' ',
1242                      r ? 'R' : ' ');
1243       }
1244    }
1245 }
1246 
DRD_(bm_get_bitmap_creation_count)1247 ULong DRD_(bm_get_bitmap_creation_count)(void)
1248 {
1249    return s_bitmap_creation_count;
1250 }
1251 
DRD_(bm_get_bitmap2_creation_count)1252 ULong DRD_(bm_get_bitmap2_creation_count)(void)
1253 {
1254    return s_bitmap2_creation_count;
1255 }
1256 
DRD_(bm_get_bitmap2_merge_count)1257 ULong DRD_(bm_get_bitmap2_merge_count)(void)
1258 {
1259    return s_bitmap2_merge_count;
1260 }
1261 
1262 /** Compute *bm2l |= *bm2r. */
1263 static
bm2_merge(struct bitmap2 * const bm2l,const struct bitmap2 * const bm2r)1264 void bm2_merge(struct bitmap2* const bm2l, const struct bitmap2* const bm2r)
1265 {
1266    unsigned k;
1267 
1268    tl_assert(bm2l);
1269    tl_assert(bm2r);
1270    tl_assert(bm2l->addr == bm2r->addr);
1271 
1272    s_bitmap2_merge_count++;
1273 
1274    for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
1275    {
1276       bm2l->bm1.bm0_r[k] |= bm2r->bm1.bm0_r[k];
1277    }
1278    for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
1279    {
1280       bm2l->bm1.bm0_w[k] |= bm2r->bm1.bm0_w[k];
1281    }
1282 }
1283