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
crc32_reflect(uint32 value,int32 bits)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
init_crc32_table()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
crc32(const void * _data,size_t size)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:
ParanoiaCheck(const void * address,size_t size)78 ParanoiaCheck(const void* address, size_t size)
79 :
80 fAddress(address),
81 fSize(size)
82 {
83 Update();
84 }
85
Address() const86 const void* Address() const { return fAddress; }
Size() const87 size_t Size() const { return fSize; }
88
Update()89 void Update()
90 {
91 fCheckSum = crc32(fAddress, fSize);
92 }
93
Check() const94 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:
ParanoiaCheckSet(const void * object,const char * description)111 ParanoiaCheckSet(const void* object, const char* description)
112 :
113 fObject(object),
114 fDescription(description),
115 fChecks(NULL)
116 {
117 }
118
Object() const119 const void* Object() const { return fObject; }
Description() const120 const char* Description() const { return fDescription; }
121
FirstCheck() const122 ParanoiaCheck* FirstCheck() const
123 {
124 return fChecks;
125 }
126
NextCheck(ParanoiaCheck * check) const127 ParanoiaCheck* NextCheck(ParanoiaCheck* check) const
128 {
129 return check->fNext;
130 }
131
FindCheck(const void * address) const132 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
AddCheck(ParanoiaCheck * check)140 void AddCheck(ParanoiaCheck* check)
141 {
142 check->fNext = fChecks;
143 fChecks = check;
144 }
145
RemoveCheck(ParanoiaCheck * check)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
RemoveFirstCheck()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
SetHashNext(ParanoiaCheckSet * next)171 void SetHashNext(ParanoiaCheckSet* next)
172 {
173 fHashNext = next;
174 }
175
HashNext() const176 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:
ParanoiaTraceEntry(const void * object)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
DumpStackTrace(TraceOutput & out)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:
CreateCheckSet(const void * object,const char * description)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
AddDump(TraceOutput & out)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:
DeleteCheckSet(const void * object)254 DeleteCheckSet(const void* object)
255 :
256 ParanoiaTraceEntry(object)
257 {
258 Initialized();
259 }
260
AddDump(TraceOutput & out)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:
SetCheck(const void * object,const void * address,size_t size,paranoia_set_check_mode mode)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
AddDump(TraceOutput & out)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:
RemoveCheck(const void * object,const void * address,size_t size)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
AddDump(TraceOutput & out)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*
allocate_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
free_slot(paranoia_slot * slot)363 free_slot(paranoia_slot* slot)
364 {
365 slot->nextFree = sSlotFreeList;
366 sSlotFreeList = slot;
367 }
368
369
370 static void
add_check_set(ParanoiaCheckSet * set)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
remove_check_set(ParanoiaCheckSet * set)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*
lookup_check_set(const void * object)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
create_paranoia_check_set(const void * object,const char * description)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
delete_paranoia_check_set(const void * object)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
run_paranoia_checks(const void * object)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
set_paranoia_check(const void * object,const void * address,size_t size,paranoia_set_check_mode mode)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
remove_paranoia_check(const void * object,const void * address,size_t size)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
debug_paranoia_init()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