1 /*
2 This file is part of drd, a thread error detector.
3
4 Copyright (C) 2006-2013 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