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 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 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 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
