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