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
24static const uint32 kCRC32Polynom = 0x04c11db7;
25static uint32 sCRC32Table[256];
26
27
28static uint32
29crc32_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
42static void
43init_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
56static uint32
57crc32(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
74class ParanoiaCheckSet;
75
76class ParanoiaCheck {
77public:
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
99private:
100	const void*		fAddress;
101	size_t			fSize;
102	uint32			fCheckSum;
103	ParanoiaCheck*	fNext;
104
105	friend class ParanoiaCheckSet;
106};
107
108
109class ParanoiaCheckSet {
110public:
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
181private:
182	const void*			fObject;
183	const char*			fDescription;
184	ParanoiaCheck*		fChecks;
185	ParanoiaCheckSet*	fHashNext;
186};
187
188
189union 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
202namespace ParanoiaTracing {
203
204class 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
231class 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
252class 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
268class 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
306class 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
344static paranoia_slot		sSlots[PARANOIA_SLOT_COUNT];
345static paranoia_slot*		sSlotFreeList;
346static ParanoiaCheckSet*	sCheckSetHash[PARANOIA_HASH_SIZE];
347static spinlock				sParanoiaLock;
348
349
350static paranoia_slot*
351allocate_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
362static void
363free_slot(paranoia_slot* slot)
364{
365	slot->nextFree = sSlotFreeList;
366	sSlotFreeList = slot;
367}
368
369
370static void
371add_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
379static void
380remove_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
397static ParanoiaCheckSet*
398lookup_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
411status_t
412create_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
445status_t
446delete_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
472status_t
473run_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
503status_t
504set_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
557status_t
558remove_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
594void
595debug_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