• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**
2  * @file db_debug.c
3  * Debug routines for libdb
4  *
5  * @remark Copyright 2002 OProfile authors
6  * @remark Read the file COPYING
7  *
8  * @author Philippe Elie
9  */
10 
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14 
15 #include "odb.h"
16 
check_circular_list(odb_data_t const * data)17 static int check_circular_list(odb_data_t const * data)
18 {
19 	odb_node_nr_t pos;
20 	int do_abort = 0;
21 	unsigned char * bitmap = malloc(data->descr->current_size);
22 	memset(bitmap, '\0', data->descr->current_size);
23 
24 	for (pos = 0 ; pos < data->descr->size * BUCKET_FACTOR ; ++pos) {
25 
26 		odb_index_t index = data->hash_base[pos];
27 		if (index && !do_abort) {
28 			while (index) {
29 				if (bitmap[index])
30 					do_abort = 1;
31 
32 				bitmap[index] = 1;
33 				index = data->node_base[index].next;
34 			}
35 		}
36 
37 		if (do_abort) {
38 			printf("circular list detected size: %d\n",
39 			       data->descr->current_size);
40 
41 			memset(bitmap, '\0', data->descr->current_size);
42 
43 			index = data->hash_base[pos];
44 			while (index) {
45 				printf("%d ", index);
46 				if (bitmap[index])
47 					exit(1);
48 
49 				bitmap[index] = 1;
50 				index = data->node_base[index].next;
51 			}
52 		}
53 
54 		/* purely an optimization: intead of memset the map reset only
55 		 * the needed part: not my use to optimize test but here the
56 		 * test was so slow it was useless */
57 		index = data->hash_base[pos];
58 		while (index) {
59 			bitmap[index] = 1;
60 			index = data->node_base[index].next;
61 		}
62 	}
63 
64 	free(bitmap);
65 
66 	return do_abort;
67 }
68 
check_redundant_key(odb_data_t const * data,odb_key_t max)69 static int check_redundant_key(odb_data_t const * data, odb_key_t max)
70 {
71 	odb_node_nr_t pos;
72 
73 	unsigned char * bitmap = malloc(max + 1);
74 	memset(bitmap, '\0', max + 1);
75 
76 	for (pos = 1 ; pos < data->descr->current_size ; ++pos) {
77 		if (bitmap[data->node_base[pos].key]) {
78 			printf("redundant key found %lld\n",
79 			       (unsigned long long)data->node_base[pos].key);
80 			return 1;
81 		}
82 		bitmap[data->node_base[pos].key] = 1;
83 	}
84 	free(bitmap);
85 
86 	return 0;
87 }
88 
odb_check_hash(odb_t const * odb)89 int odb_check_hash(odb_t const * odb)
90 {
91 	odb_node_nr_t pos;
92 	odb_node_nr_t nr_node = 0;
93 	odb_node_nr_t nr_node_out_of_bound = 0;
94 	int ret = 0;
95 	odb_key_t max = 0;
96 	odb_data_t * data = odb->data;
97 
98 	for (pos = 0 ; pos < data->descr->size * BUCKET_FACTOR ; ++pos) {
99 		odb_index_t index = data->hash_base[pos];
100 		while (index) {
101 			if (index >= data->descr->current_size) {
102 				nr_node_out_of_bound++;
103 				break;
104 			}
105 			++nr_node;
106 
107 			if (data->node_base[index].key > max)
108 				max = data->node_base[index].key;
109 
110 			index = data->node_base[index].next;
111 		}
112 	}
113 
114 	if (nr_node != data->descr->current_size - 1) {
115 		printf("hash table walk found %d node expect %d node\n",
116 		       nr_node, data->descr->current_size - 1);
117 		ret = 1;
118 	}
119 
120 	if (nr_node_out_of_bound) {
121 		printf("out of bound node index: %d\n", nr_node_out_of_bound);
122 		ret = 1;
123 	}
124 
125 	if (ret == 0)
126 		ret = check_circular_list(data);
127 
128 	if (ret == 0)
129 		ret = check_redundant_key(data, max);
130 
131 	return ret;
132 }
133