1 /* Copyright (c) 2000, 2021, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
22
23 /* Check that heap-structure is ok */
24
25 #include "heapdef.h"
26
27 static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
28 ulong blength, my_bool print_status);
29 static int check_one_rb_key(HP_INFO *info, uint keynr, ulong records,
30 my_bool print_status);
31
32
33 /*
34 Check if keys and rows are ok in a heap table
35
36 SYNOPSIS
37 heap_check_heap()
38 info Table handler
39 print_status Prints some extra status
40
41 NOTES
42 Doesn't change the state of the table handler
43
44 RETURN VALUES
45 0 ok
46 1 error
47 */
48
heap_check_heap(HP_INFO * info,my_bool print_status)49 int heap_check_heap(HP_INFO *info, my_bool print_status)
50 {
51 int error;
52 uint key;
53 ulong records= 0, deleted= 0, chunk_count= 0, pos, next_block;
54 HP_SHARE *share=info->s;
55 HP_INFO save_info= *info; /* Needed because scan_init */
56 DBUG_ENTER("heap_check_heap");
57
58 for (error=key= 0 ; key < share->keys ; key++)
59 {
60 if (share->keydef[key].algorithm == HA_KEY_ALG_BTREE)
61 error|= check_one_rb_key(info, key, share->records, print_status);
62 else
63 error|= check_one_key(share->keydef + key, key, share->records,
64 share->blength, print_status);
65 }
66 /*
67 This is basicly the same code as in hp_scan, but we repeat it here to
68 get shorter DBUG log file.
69 */
70 for (pos=next_block= 0 ; ; pos++)
71 {
72 if (pos < next_block)
73 {
74 info->current_ptr+= share->recordspace.block.recbuffer;
75 }
76 else
77 {
78 next_block+= share->recordspace.block.records_in_block;
79 if (next_block >= share->recordspace.chunk_count)
80 {
81 next_block= share->recordspace.chunk_count;
82 if (pos >= next_block)
83 break; /* End of file */
84 }
85 }
86 hp_find_record(info,pos);
87
88 switch (get_chunk_status(&share->recordspace, info->current_ptr)) {
89 case CHUNK_STATUS_DELETED:
90 deleted++;
91 chunk_count++;
92 break;
93 case CHUNK_STATUS_ACTIVE:
94 records++;
95 chunk_count++;
96 break;
97 case CHUNK_STATUS_LINKED:
98 chunk_count++;
99 break;
100 default:
101 DBUG_PRINT("error",
102 ("Unknown record status: Record: 0x%lx Status %lu",
103 (long) info->current_ptr,
104 (ulong) get_chunk_status(&share->recordspace,
105 info->current_ptr)));
106 error|= 1;
107 break;
108 }
109 }
110
111 /* TODO: verify linked chunks (no orphans, no cycles, no bad links) */
112
113 if (records != share->records ||
114 chunk_count != share->recordspace.chunk_count ||
115 deleted != share->recordspace.del_chunk_count)
116 {
117 DBUG_PRINT("error",
118 ("Found rows: %lu (%lu) total chunks %lu (%lu) deleted chunks "
119 "%lu (%lu)",
120 records, (ulong) share->records,
121 chunk_count, (ulong) share->recordspace.chunk_count,
122 deleted, (ulong) share->recordspace.del_chunk_count));
123 error= 1;
124 }
125 *info= save_info;
126 DBUG_RETURN(error);
127 }
128
129
check_one_key(HP_KEYDEF * keydef,uint keynr,ulong records,ulong blength,my_bool print_status)130 static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
131 ulong blength, my_bool print_status)
132 {
133 int error;
134 ulong i,found,max_links,seek,links;
135 ulong rec_link; /* Only used with debugging */
136 ulong hash_buckets_found;
137 HASH_INFO *hash_info;
138
139 error=0;
140 hash_buckets_found= 0;
141 for (i=found=max_links=seek=0 ; i < records ; i++)
142 {
143 hash_info=hp_find_hash(&keydef->block,i);
144 if (hp_mask(hash_info->hash, blength,records) == i)
145 {
146 found++;
147 seek++;
148 links=1;
149 while ((hash_info=hash_info->next_key) && found < records + 1)
150 {
151 seek+= ++links;
152 if (i != (rec_link= hp_mask(hash_info->hash, blength, records)))
153 {
154 DBUG_PRINT("error",
155 ("Record in wrong link: Link %lu Record: 0x%lx Record-link %lu",
156 i, (long) hash_info->ptr_to_rec, rec_link));
157 error=1;
158 }
159 else
160 found++;
161 }
162 if (links > max_links) max_links=links;
163 hash_buckets_found++;
164 }
165 }
166 if (found != records)
167 {
168 DBUG_PRINT("error",("Found %ld of %ld records", found, records));
169 error=1;
170 }
171 if (keydef->hash_buckets != hash_buckets_found)
172 {
173 DBUG_PRINT("error",("Found %ld buckets, stats shows %ld buckets",
174 hash_buckets_found, (long) keydef->hash_buckets));
175 error=1;
176 }
177 DBUG_PRINT("info",
178 ("records: %ld seeks: %lu max links: %lu hitrate: %.2f "
179 "buckets: %lu",
180 records,seek,max_links,
181 (float) seek / (float) (records ? records : 1),
182 hash_buckets_found));
183 if (print_status)
184 printf("Key: %d records: %ld seeks: %lu max links: %lu "
185 "hitrate: %.2f buckets: %lu\n",
186 keynr, records, seek, max_links,
187 (float) seek / (float) (records ? records : 1),
188 hash_buckets_found);
189 return error;
190 }
191
check_one_rb_key(HP_INFO * info,uint keynr,ulong records,my_bool print_status)192 static int check_one_rb_key(HP_INFO *info, uint keynr, ulong records,
193 my_bool print_status)
194 {
195 HP_KEYDEF *keydef= info->s->keydef + keynr;
196 int error= 0;
197 ulong found= 0;
198 uchar *key, *recpos;
199 uint key_length;
200 uint not_used[2];
201
202 if ((key= tree_search_edge(&keydef->rb_tree, info->parents,
203 &info->last_pos, offsetof(TREE_ELEMENT, left))))
204 {
205 do
206 {
207 memcpy(&recpos, key + (*keydef->get_key_length)(keydef,key), sizeof(uchar*));
208 key_length= hp_rb_make_key(keydef, info->recbuf, recpos, 0, TRUE);
209 if (ha_key_cmp(keydef->seg, (uchar*) info->recbuf, (uchar*) key,
210 key_length, SEARCH_FIND | SEARCH_SAME, not_used))
211 {
212 error= 1;
213 DBUG_PRINT("error",("Record in wrong link: key: %u Record: 0x%lx\n",
214 keynr, (long) recpos));
215 }
216 else
217 found++;
218 key= tree_search_next(&keydef->rb_tree, &info->last_pos,
219 offsetof(TREE_ELEMENT, left),
220 offsetof(TREE_ELEMENT, right));
221 } while (key);
222 }
223 if (found != records)
224 {
225 DBUG_PRINT("error",("Found %lu of %lu records", found, records));
226 error= 1;
227 }
228 if (print_status)
229 printf("Key: %d records: %ld\n", keynr, records);
230 return error;
231 }
232