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