1 /* 2 * Copyright 2008, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 #include <debug_paranoia.h> 7 8 #include <sys/param.h> 9 10 #include <new> 11 12 #include <OS.h> 13 14 #include <tracing.h> 15 #include <util/AutoLock.h> 16 17 18 #if ENABLE_PARANOIA_CHECKS 19 20 21 // #pragma mark - CRC-32 22 23 24 static const uint32 kCRC32Polynom = 0x04c11db7; 25 static uint32 sCRC32Table[256]; 26 27 28 static uint32 29 crc32_reflect(uint32 value, int32 bits) 30 { 31 uint32 result = 0; 32 for (int32 i = 1; i <= bits; i++) { 33 if (value & 1) 34 result |= 1 << (bits - i); 35 value >>= 1; 36 } 37 38 return result; 39 } 40 41 42 static void 43 init_crc32_table() 44 { 45 for (int32 i = 0; i < 256; i++) { 46 sCRC32Table[i] = crc32_reflect(i, 8) << 24; 47 for (int32 k = 0; k < 8; k++) { 48 sCRC32Table[i] = (sCRC32Table[i] << 1) 49 ^ (sCRC32Table[i] & (1 << 31) ? kCRC32Polynom : 0); 50 } 51 sCRC32Table[i] = crc32_reflect(sCRC32Table[i], 32); 52 } 53 } 54 55 56 static uint32 57 crc32(const void* _data, size_t size) 58 { 59 uint8* data = (uint8*)_data; 60 uint32 crc = 0xffffffff; 61 62 while (size-- > 0) { 63 crc = (crc >> 8) ^ sCRC32Table[(crc & 0xff) ^ *data]; 64 data++; 65 } 66 67 return crc; 68 } 69 70 71 // #pragma mark - ParanoiaCheck[Set] 72 73 74 class ParanoiaCheckSet; 75 76 class ParanoiaCheck { 77 public: 78 ParanoiaCheck(const void* address, size_t size) 79 : 80 fAddress(address), 81 fSize(size) 82 { 83 Update(); 84 } 85 86 const void* Address() const { return fAddress; } 87 size_t Size() const { return fSize; } 88 89 void Update() 90 { 91 fCheckSum = crc32(fAddress, fSize); 92 } 93 94 bool Check() const 95 { 96 return crc32(fAddress, fSize) == fCheckSum; 97 } 98 99 private: 100 const void* fAddress; 101 size_t fSize; 102 uint32 fCheckSum; 103 ParanoiaCheck* fNext; 104 105 friend class ParanoiaCheckSet; 106 }; 107 108 109 class ParanoiaCheckSet { 110 public: 111 ParanoiaCheckSet(const void* object, const char* description) 112 : 113 fObject(object), 114 fDescription(description), 115 fChecks(NULL) 116 { 117 } 118 119 const void* Object() const { return fObject; } 120 const char* Description() const { return fDescription; } 121 122 ParanoiaCheck* FirstCheck() const 123 { 124 return fChecks; 125 } 126 127 ParanoiaCheck* NextCheck(ParanoiaCheck* check) const 128 { 129 return check->fNext; 130 } 131 132 ParanoiaCheck* FindCheck(const void* address) const 133 { 134 ParanoiaCheck* check = fChecks; 135 while (check != NULL && check->Address() != address) 136 check = check->fNext; 137 return check; 138 } 139 140 void AddCheck(ParanoiaCheck* check) 141 { 142 check->fNext = fChecks; 143 fChecks = check; 144 } 145 146 void RemoveCheck(ParanoiaCheck* check) 147 { 148 if (check == fChecks) { 149 fChecks = check->fNext; 150 return; 151 } 152 153 ParanoiaCheck* previous = fChecks; 154 while (previous != NULL && previous->fNext != check) 155 previous = previous->fNext; 156 157 // if previous is NULL (which it shouldn't be), just crash here 158 previous->fNext = check->fNext; 159 } 160 161 ParanoiaCheck* RemoveFirstCheck() 162 { 163 ParanoiaCheck* check = fChecks; 164 if (check == NULL) 165 return NULL; 166 167 fChecks = check->fNext; 168 return check; 169 } 170 171 void SetHashNext(ParanoiaCheckSet* next) 172 { 173 fHashNext = next; 174 } 175 176 ParanoiaCheckSet* HashNext() const 177 { 178 return fHashNext; 179 } 180 181 private: 182 const void* fObject; 183 const char* fDescription; 184 ParanoiaCheck* fChecks; 185 ParanoiaCheckSet* fHashNext; 186 }; 187 188 189 union paranoia_slot { 190 uint8 check[sizeof(ParanoiaCheck)]; 191 uint8 checkSet[sizeof(ParanoiaCheckSet)]; 192 paranoia_slot* nextFree; 193 }; 194 195 196 // #pragma mark - Tracing 197 198 199 #if PARANOIA_TRACING 200 201 202 namespace ParanoiaTracing { 203 204 class ParanoiaTraceEntry : public AbstractTraceEntry { 205 public: 206 ParanoiaTraceEntry(const void* object) 207 : 208 fObject(object) 209 { 210 #if PARANOIA_TRACING_STACK_TRACE 211 fStackTrace = capture_tracing_stack_trace(PARANOIA_TRACING_STACK_TRACE, 212 1, false); 213 #endif 214 } 215 216 #if PARANOIA_TRACING_STACK_TRACE 217 virtual void DumpStackTrace(TraceOutput& out) 218 { 219 out.PrintStackTrace(fStackTrace); 220 } 221 #endif 222 223 protected: 224 const void* fObject; 225 #if PARANOIA_TRACING_STACK_TRACE 226 tracing_stack_trace* fStackTrace; 227 #endif 228 }; 229 230 231 class CreateCheckSet : public ParanoiaTraceEntry { 232 public: 233 CreateCheckSet(const void* object, const char* description) 234 : 235 ParanoiaTraceEntry(object) 236 { 237 fDescription = alloc_tracing_buffer_strcpy(description, 64, false); 238 Initialized(); 239 } 240 241 virtual void AddDump(TraceOutput& out) 242 { 243 out.Print("paranoia create check set: object: %p, " 244 "description: \"%s\"", fObject, fDescription); 245 } 246 247 private: 248 const char* fDescription; 249 }; 250 251 252 class DeleteCheckSet : public ParanoiaTraceEntry { 253 public: 254 DeleteCheckSet(const void* object) 255 : 256 ParanoiaTraceEntry(object) 257 { 258 Initialized(); 259 } 260 261 virtual void AddDump(TraceOutput& out) 262 { 263 out.Print("paranoia delete check set: object: %p", fObject); 264 } 265 }; 266 267 268 class SetCheck : public ParanoiaTraceEntry { 269 public: 270 SetCheck(const void* object, const void* address, size_t size, 271 paranoia_set_check_mode mode) 272 : 273 ParanoiaTraceEntry(object), 274 fAddress(address), 275 fSize(size), 276 fMode(mode) 277 { 278 Initialized(); 279 } 280 281 virtual void AddDump(TraceOutput& out) 282 { 283 const char* mode = "??? op:"; 284 switch (fMode) { 285 case PARANOIA_DONT_FAIL: 286 mode = "set: "; 287 break; 288 case PARANOIA_FAIL_IF_EXISTS: 289 mode = "add: "; 290 break; 291 case PARANOIA_FAIL_IF_MISSING: 292 mode = "update:"; 293 break; 294 } 295 out.Print("paranoia check %s object: %p, address: %p, size: %lu", 296 mode, fObject, fAddress, fSize); 297 } 298 299 private: 300 const void* fAddress; 301 size_t fSize; 302 paranoia_set_check_mode fMode; 303 }; 304 305 306 class RemoveCheck : public ParanoiaTraceEntry { 307 public: 308 RemoveCheck(const void* object, const void* address, size_t size) 309 : 310 ParanoiaTraceEntry(object), 311 fAddress(address), 312 fSize(size) 313 { 314 Initialized(); 315 } 316 317 virtual void AddDump(TraceOutput& out) 318 { 319 out.Print("paranoia check remove: object: %p, address: %p, size: " 320 "%lu", fObject, fAddress, fSize); 321 } 322 323 private: 324 const void* fAddress; 325 size_t fSize; 326 paranoia_set_check_mode fMode; 327 }; 328 329 330 } // namespace ParanoiaTracing 331 332 # define T(x) new(std::nothrow) ParanoiaTracing::x 333 334 #else 335 # define T(x) 336 #endif // PARANOIA_TRACING 337 338 339 // #pragma mark - 340 341 342 #define PARANOIA_HASH_SIZE PARANOIA_SLOT_COUNT 343 344 static paranoia_slot sSlots[PARANOIA_SLOT_COUNT]; 345 static paranoia_slot* sSlotFreeList; 346 static ParanoiaCheckSet* sCheckSetHash[PARANOIA_HASH_SIZE]; 347 static spinlock sParanoiaLock; 348 349 350 static paranoia_slot* 351 allocate_slot() 352 { 353 if (sSlotFreeList == NULL) 354 return NULL; 355 356 paranoia_slot* slot = sSlotFreeList; 357 sSlotFreeList = slot->nextFree; 358 return slot; 359 } 360 361 362 static void 363 free_slot(paranoia_slot* slot) 364 { 365 slot->nextFree = sSlotFreeList; 366 sSlotFreeList = slot; 367 } 368 369 370 static void 371 add_check_set(ParanoiaCheckSet* set) 372 { 373 int slot = (addr_t)set->Object() % PARANOIA_HASH_SIZE; 374 set->SetHashNext(sCheckSetHash[slot]); 375 sCheckSetHash[slot] = set; 376 } 377 378 379 static void 380 remove_check_set(ParanoiaCheckSet* set) 381 { 382 int slot = (addr_t)set->Object() % PARANOIA_HASH_SIZE; 383 if (set == sCheckSetHash[slot]) { 384 sCheckSetHash[slot] = set->HashNext(); 385 return; 386 } 387 388 ParanoiaCheckSet* previousSet = sCheckSetHash[slot]; 389 while (previousSet != NULL && previousSet->HashNext() != set) 390 previousSet = previousSet->HashNext(); 391 392 // if previousSet is NULL (which it shouldn't be), just crash here 393 previousSet->SetHashNext(set->HashNext()); 394 } 395 396 397 static ParanoiaCheckSet* 398 lookup_check_set(const void* object) 399 { 400 int slot = (addr_t)object % PARANOIA_HASH_SIZE; 401 ParanoiaCheckSet* set = sCheckSetHash[slot]; 402 while (set != NULL && set->Object() != object) 403 set = set->HashNext(); 404 405 return set; 406 } 407 408 // #pragma mark - public interface 409 410 411 status_t 412 create_paranoia_check_set(const void* object, const char* description) 413 { 414 T(CreateCheckSet(object, description)); 415 416 if (object == NULL) { 417 panic("create_paranoia_check_set(): NULL object"); 418 return B_BAD_VALUE; 419 } 420 421 InterruptsSpinLocker _(sParanoiaLock); 422 423 // check, if object is already registered 424 ParanoiaCheckSet* set = lookup_check_set(object); 425 if (set != NULL) { 426 panic("create_paranoia_check_set(): object %p already has a check set", 427 object); 428 return B_BAD_VALUE; 429 } 430 431 // allocate slot 432 paranoia_slot* slot = allocate_slot(); 433 if (slot == NULL) { 434 panic("create_paranoia_check_set(): out of free slots"); 435 return B_NO_MEMORY; 436 } 437 438 set = new(slot) ParanoiaCheckSet(object, description); 439 add_check_set(set); 440 441 return B_OK; 442 } 443 444 445 status_t 446 delete_paranoia_check_set(const void* object) 447 { 448 T(DeleteCheckSet(object)); 449 450 InterruptsSpinLocker _(sParanoiaLock); 451 452 // get check set 453 ParanoiaCheckSet* set = lookup_check_set(object); 454 if (set == NULL) { 455 panic("delete_paranoia_check_set(): object %p doesn't have a check set", 456 object); 457 return B_BAD_VALUE; 458 } 459 460 // free all checks 461 while (ParanoiaCheck* check = set->RemoveFirstCheck()) 462 free_slot((paranoia_slot*)check); 463 464 // free check set 465 remove_check_set(set); 466 free_slot((paranoia_slot*)set); 467 468 return B_OK; 469 } 470 471 472 status_t 473 run_paranoia_checks(const void* object) 474 { 475 InterruptsSpinLocker _(sParanoiaLock); 476 477 // get check set 478 ParanoiaCheckSet* set = lookup_check_set(object); 479 if (set == NULL) { 480 panic("run_paranoia_checks(): object %p doesn't have a check set", 481 object); 482 return B_BAD_VALUE; 483 } 484 485 status_t error = B_OK; 486 487 ParanoiaCheck* check = set->FirstCheck(); 488 while (check != NULL) { 489 if (!check->Check()) { 490 panic("paranoia check failed for object %p (%s), address: %p, " 491 "size: %lu", set->Object(), set->Description(), 492 check->Address(), check->Size()); 493 error = B_BAD_DATA; 494 } 495 496 check = set->NextCheck(check); 497 } 498 499 return error; 500 } 501 502 503 status_t 504 set_paranoia_check(const void* object, const void* address, size_t size, 505 paranoia_set_check_mode mode) 506 { 507 T(SetCheck(object, address, size, mode)); 508 509 InterruptsSpinLocker _(sParanoiaLock); 510 511 // get check set 512 ParanoiaCheckSet* set = lookup_check_set(object); 513 if (set == NULL) { 514 panic("set_paranoia_check(): object %p doesn't have a check set", 515 object); 516 return B_BAD_VALUE; 517 } 518 519 // update check, if already existing 520 ParanoiaCheck* check = set->FindCheck(address); 521 if (check != NULL) { 522 if (mode == PARANOIA_FAIL_IF_EXISTS) { 523 panic("set_paranoia_check(): object %p already has a check for " 524 "address %p", object, address); 525 return B_BAD_VALUE; 526 } 527 528 if (check->Size() != size) { 529 panic("set_paranoia_check(): changing check sizes not supported"); 530 return B_BAD_VALUE; 531 } 532 533 check->Update(); 534 return B_OK; 535 } 536 537 if (mode == PARANOIA_FAIL_IF_MISSING) { 538 panic("set_paranoia_check(): object %p doesn't have a check for " 539 "address %p yet", object, address); 540 return B_BAD_VALUE; 541 } 542 543 // allocate slot 544 paranoia_slot* slot = allocate_slot(); 545 if (slot == NULL) { 546 panic("set_paranoia_check(): out of free slots"); 547 return B_NO_MEMORY; 548 } 549 550 check = new(slot) ParanoiaCheck(address, size); 551 set->AddCheck(check); 552 553 return B_OK; 554 } 555 556 557 status_t 558 remove_paranoia_check(const void* object, const void* address, size_t size) 559 { 560 T(RemoveCheck(object, address, size)); 561 562 InterruptsSpinLocker _(sParanoiaLock); 563 564 // get check set 565 ParanoiaCheckSet* set = lookup_check_set(object); 566 if (set == NULL) { 567 panic("remove_paranoia_check(): object %p doesn't have a check set", 568 object); 569 return B_BAD_VALUE; 570 } 571 572 // get check 573 ParanoiaCheck* check = set->FindCheck(address); 574 if (check == NULL) { 575 panic("remove_paranoia_check(): no check for address %p " 576 "(object %p (%s))", address, object, set->Description()); 577 return B_BAD_VALUE; 578 } 579 580 if (check->Size() != size) { 581 panic("remove_paranoia_check(): changing check sizes not " 582 "supported"); 583 return B_BAD_VALUE; 584 } 585 586 set->RemoveCheck(check); 587 return B_OK; 588 } 589 590 591 #endif // ENABLE_PARANOIA_CHECKS 592 593 594 void 595 debug_paranoia_init() 596 { 597 #if ENABLE_PARANOIA_CHECKS 598 // init CRC-32 table 599 init_crc32_table(); 600 601 // init paranoia slot free list 602 for (int32 i = 0; i < PARANOIA_SLOT_COUNT; i++) 603 free_slot(&sSlots[i]); 604 #endif 605 } 606