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