1 /* Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
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 St, Fifth Floor, Boston, MA 02110-1301  USA */
22 
23 /* Check that heap-structure is ok */
24 
25 #include <sys/types.h>
26 
27 #include "my_dbug.h"
28 #include "my_inttypes.h"
29 #include "storage/heap/heapdef.h"
30 
31 static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
32                          ulong blength, bool print_status);
33 static int check_one_rb_key(HP_INFO *info, uint keynr, ulong records,
34                             bool print_status);
35 
36 /*
37   Check if keys and rows are ok in a heap table
38 
39   SYNOPSIS
40     heap_check_heap()
41     info		Table handler
42     print_status	Prints some extra status
43 
44   NOTES
45     Doesn't change the state of the table handler
46 
47   RETURN VALUES
48     0	ok
49     1 error
50 */
51 
heap_check_heap(HP_INFO * info,bool print_status)52 int heap_check_heap(HP_INFO *info, bool print_status) {
53   int error;
54   uint key;
55   ulong records = 0, deleted = 0, pos, next_block;
56   HP_SHARE *share = info->s;
57   HP_INFO save_info = *info; /* Needed because scan_init */
58   DBUG_TRACE;
59 
60   for (error = key = 0; key < share->keys; key++) {
61     if (share->keydef[key].algorithm == HA_KEY_ALG_BTREE)
62       error |= check_one_rb_key(info, key, share->records, print_status);
63     else
64       error |= check_one_key(share->keydef + key, key, share->records,
65                              share->blength, print_status);
66   }
67   /*
68     This is basicly the same code as in hp_scan, but we repeat it here to
69     get shorter DBUG log file.
70   */
71   for (pos = next_block = 0;; pos++) {
72     if (pos < next_block) {
73       info->current_ptr += share->block.recbuffer;
74     } else {
75       next_block += share->block.records_in_block;
76       if (next_block >= share->records + share->deleted) {
77         next_block = share->records + share->deleted;
78         if (pos >= next_block) break; /* End of file */
79       }
80     }
81     hp_find_record(info, pos);
82 
83     if (!info->current_ptr[share->reclength])
84       deleted++;
85     else
86       records++;
87   }
88 
89   if (records != share->records || deleted != share->deleted) {
90     DBUG_PRINT("error",
91                ("Found rows: %lu (%lu)  deleted %lu (%lu)", records,
92                 (ulong)share->records, deleted, (ulong)share->deleted));
93     error = 1;
94   }
95   *info = save_info;
96   return error;
97 }
98 
check_one_key(HP_KEYDEF * keydef,uint keynr,ulong records,ulong blength,bool print_status)99 static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
100                          ulong blength, bool print_status) {
101   int error;
102   ulong i, found, max_links, seek, links;
103   ulong rec_link; /* Only used with debugging */
104   ulong hash_buckets_found;
105   HASH_INFO *hash_info;
106 
107   error = 0;
108   hash_buckets_found = 0;
109   for (i = found = max_links = seek = 0; i < records; i++) {
110     hash_info = hp_find_hash(&keydef->block, i);
111     if (hp_mask(hash_info->hash, blength, records) == i) {
112       found++;
113       seek++;
114       links = 1;
115       while ((hash_info = hash_info->next_key) && found < records + 1) {
116         seek += ++links;
117         if (i != (rec_link = hp_mask(hash_info->hash, blength, records))) {
118           DBUG_PRINT(
119               "error",
120               ("Record in wrong link: Link %lu  Record: %p  Record-link %lu", i,
121                hash_info->ptr_to_rec, rec_link));
122           error = 1;
123         } else
124           found++;
125       }
126       if (links > max_links) max_links = links;
127       hash_buckets_found++;
128     }
129   }
130   if (found != records) {
131     DBUG_PRINT("error", ("Found %ld of %ld records", found, records));
132     error = 1;
133   }
134   if (keydef->hash_buckets != hash_buckets_found) {
135     DBUG_PRINT("error", ("Found %ld buckets, stats shows %ld buckets",
136                          hash_buckets_found, (long)keydef->hash_buckets));
137     error = 1;
138   }
139   DBUG_PRINT(
140       "info",
141       ("records: %ld   seeks: %lu   max links: %lu   hitrate: %.2f   "
142        "buckets: %lu",
143        records, seek, max_links, (float)seek / (float)(records ? records : 1),
144        hash_buckets_found));
145   if (print_status)
146     printf(
147         "Key: %d  records: %ld   seeks: %lu   max links: %lu   "
148         "hitrate: %.2f   buckets: %lu\n",
149         keynr, records, seek, max_links,
150         (float)seek / (float)(records ? records : 1), hash_buckets_found);
151   return error;
152 }
153 
check_one_rb_key(HP_INFO * info,uint keynr,ulong records,bool print_status)154 static int check_one_rb_key(HP_INFO *info, uint keynr, ulong records,
155                             bool print_status) {
156   HP_KEYDEF *keydef = info->s->keydef + keynr;
157   int error = 0;
158   ulong found = 0;
159   uchar *key, *recpos;
160   uint key_length;
161   uint not_used[2];
162 
163   if ((key = (uchar *)tree_search_edge(&keydef->rb_tree, info->parents,
164                                        &info->last_pos,
165                                        offsetof(TREE_ELEMENT, left)))) {
166     do {
167       memcpy(&recpos, key + (*keydef->get_key_length)(keydef, key),
168              sizeof(uchar *));
169       key_length = hp_rb_make_key(keydef, info->recbuf, recpos, nullptr);
170       if (ha_key_cmp(keydef->seg, (uchar *)info->recbuf, (uchar *)key,
171                      key_length, SEARCH_FIND | SEARCH_SAME, not_used)) {
172         error = 1;
173         DBUG_PRINT("error", ("Record in wrong link:  key: %u  Record: %p\n",
174                              keynr, recpos));
175       } else
176         found++;
177       key = (uchar *)tree_search_next(&keydef->rb_tree, &info->last_pos,
178                                       offsetof(TREE_ELEMENT, left),
179                                       offsetof(TREE_ELEMENT, right));
180     } while (key);
181   }
182   if (found != records) {
183     DBUG_PRINT("error", ("Found %lu of %lu records", found, records));
184     error = 1;
185   }
186   if (print_status) printf("Key: %d  records: %ld\n", keynr, records);
187   return error;
188 }
189