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