MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DbtupTabDesMan.cpp
1 /*
2  Copyright (C) 2003-2008 MySQL AB, 2009 Sun Microsystems, Inc.
3  All rights reserved. Use is subject to license terms.
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; version 2 of the License.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program; if not, write to the Free Software
16  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 
19 
20 #define DBTUP_C
21 #define DBTUP_TAB_DES_MAN_CPP
22 #include "Dbtup.hpp"
23 #include <RefConvert.hpp>
24 #include <ndb_limits.h>
25 #include <pc.hpp>
26 
27 /*
28  * TABLE DESCRIPTOR MEMORY MANAGER
29  *
30  * Each table has a descriptor which is a contiguous array of words.
31  * Newer NDB versions also have additional "dynamic descriptors"
32  * which are allocated separately using the same method.
33  *
34  * The descriptor is allocated from a global array using a buddy
35  * algorithm. Free lists exist for each power of 2 words. Freeing
36  * a piece first merges with free right and left neighbours and then
37  * divides itself up into free list chunks.
38  */
39 
40 Uint32
41 Dbtup::getTabDescrOffsets(Uint32 noOfAttrs,
42  Uint32 noOfCharsets,
43  Uint32 noOfKeyAttr,
44  Uint32 extraColumns,
45  Uint32* offset)
46 {
47  // belongs to configure.in
48  unsigned sizeOfPointer = sizeof(CHARSET_INFO*);
49  ndbrequire((sizeOfPointer & 0x3) == 0);
50  sizeOfPointer = (sizeOfPointer >> 2);
51  // do in layout order and return offsets (see DbtupMeta.cpp)
52  Uint32 allocSize = 0;
53  // magically aligned to 8 bytes
54  offset[0] = allocSize += ZTD_SIZE;
55  offset[1] = allocSize += noOfAttrs * sizeOfReadFunction();
56  offset[2] = allocSize += noOfAttrs * sizeOfReadFunction();
57  offset[3] = allocSize += noOfCharsets * sizeOfPointer;
58  offset[4] = allocSize += noOfKeyAttr;
59  offset[5] = allocSize += (noOfAttrs + extraColumns) * ZAD_SIZE;
60  offset[6] = allocSize += (noOfAttrs+1) >> 1; // real order
61  allocSize += ZTD_TRAILER_SIZE;
62  // return number of words
63  return allocSize;
64 }
65 
66 Uint32
67 Dbtup::getDynTabDescrOffsets(Uint32 MaskSize, Uint32* offset)
68 {
69  // do in layout order and return offsets (see DbtupMeta.cpp)
70  Uint32 allocSize= 0;
71  offset[0]= allocSize += ZTD_SIZE;
72  offset[1]= allocSize += MaskSize;
73  offset[2]= allocSize += MaskSize;
74  allocSize+= ZTD_TRAILER_SIZE;
75  // return number of words
76  return allocSize;
77 }
78 
79 void
80 Dbtup::releaseTabDescr(Uint32 descriptor)
81 {
82  if (descriptor != RNIL)
83  {
84  Uint32 retNo= getTabDescrWord(descriptor + ZTD_DATASIZE);
85  ndbrequire(getTabDescrWord(descriptor + ZTD_HEADER) == ZTD_TYPE_NORMAL);
86  ndbrequire(retNo == getTabDescrWord((descriptor + retNo) - ZTD_TR_SIZE));
87  ndbrequire(ZTD_TYPE_NORMAL ==
88  getTabDescrWord((descriptor + retNo) - ZTD_TR_TYPE));
89  freeTabDescr(descriptor, retNo);
90  }
91 }
92 
93 Uint32 Dbtup::allocTabDescr(Uint32 allocSize)
94 {
95  Uint32 reference = RNIL;
96 /* ---------------------------------------------------------------- */
97 /* ALWAYS ALLOCATE A MULTIPLE OF 16 WORDS */
98 /* ---------------------------------------------------------------- */
99  allocSize = (((allocSize - 1) >> 4) + 1) << 4;
100  Uint32 list = nextHigherTwoLog(allocSize - 1); /* CALCULATE WHICH LIST IT BELONGS TO */
101  for (Uint32 i = list; i < 16; i++) {
102  jam();
103  if (cfreeTdList[i] != RNIL) {
104  jam();
105  reference = cfreeTdList[i];
106  removeTdArea(reference, i); /* REMOVE THE AREA FROM THE FREELIST */
107  Uint32 retNo = (1 << i) - allocSize; /* CALCULATE THE DIFFERENCE */
108  if (retNo >= ZTD_FREE_SIZE) {
109  jam();
110  // return unused words, of course without attempting left merge
111  Uint32 retRef = reference + allocSize;
112  freeTabDescr(retRef, retNo, false);
113  } else {
114  jam();
115  allocSize = 1 << i;
116  }//if
117  break;
118  }//if
119  }//for
120  if (reference == RNIL) {
121  jam();
122  terrorCode = ZMEM_NOTABDESCR_ERROR;
123  return RNIL;
124  } else {
125  jam();
126  setTabDescrWord((reference + allocSize) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);
127  setTabDescrWord(reference + ZTD_DATASIZE, allocSize);
128 
129  /* INITIALIZE THE TRAILER RECORD WITH TYPE AND SIZE */
130  /* THE TRAILER IS USED TO SIMPLIFY MERGE OF FREE AREAS */
131 
132  setTabDescrWord(reference + ZTD_HEADER, ZTD_TYPE_NORMAL);
133  setTabDescrWord((reference + allocSize) - ZTD_TR_SIZE, allocSize);
134  return reference;
135  }//if
136 }//Dbtup::allocTabDescr()
137 
138 void Dbtup::freeTabDescr(Uint32 retRef, Uint32 retNo, bool normal)
139 {
140  itdaMergeTabDescr(retRef, retNo, normal); /* MERGE WITH POSSIBLE NEIGHBOURS */
141  while (retNo >= ZTD_FREE_SIZE) {
142  jam();
143  Uint32 list = nextHigherTwoLog(retNo);
144  list--; /* RETURN TO NEXT LOWER LIST */
145  Uint32 sizeOfChunk = 1 << list;
146  insertTdArea(retRef, list);
147  retRef += sizeOfChunk;
148  retNo -= sizeOfChunk;
149  }//while
150  ndbassert(retNo == 0);
151 }//Dbtup::freeTabDescr()
152 
153 Uint32
154 Dbtup::getTabDescrWord(Uint32 index)
155 {
156  ndbrequire(index < cnoOfTabDescrRec);
157  return tableDescriptor[index].tabDescr;
158 }//Dbtup::getTabDescrWord()
159 
160 void
161 Dbtup::setTabDescrWord(Uint32 index, Uint32 word)
162 {
163  ndbrequire(index < cnoOfTabDescrRec);
164  tableDescriptor[index].tabDescr = word;
165 }//Dbtup::setTabDescrWord()
166 
167 void Dbtup::insertTdArea(Uint32 tabDesRef, Uint32 list)
168 {
169  ndbrequire(list < 16);
170  RSS_OP_FREE_X(cnoOfFreeTabDescrRec, 1 << list);
171  setTabDescrWord(tabDesRef + ZTD_FL_HEADER, ZTD_TYPE_FREE);
172  setTabDescrWord(tabDesRef + ZTD_FL_NEXT, cfreeTdList[list]);
173  if (cfreeTdList[list] != RNIL) {
174  jam(); /* PREVIOUSLY EMPTY SLOT */
175  setTabDescrWord(cfreeTdList[list] + ZTD_FL_PREV, tabDesRef);
176  }//if
177  cfreeTdList[list] = tabDesRef; /* RELINK THE LIST */
178 
179  setTabDescrWord(tabDesRef + ZTD_FL_PREV, RNIL);
180  setTabDescrWord(tabDesRef + ZTD_FL_SIZE, 1 << list);
181  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_FREE);
182  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_SIZE, 1 << list);
183 }//Dbtup::insertTdArea()
184 
185 /*
186  * Merge to-be-removed chunk (which need not be initialized with header
187  * and trailer) with left and right buddies. The start point retRef
188  * moves to left and the size retNo increases to match the new chunk.
189  */
190 void Dbtup::itdaMergeTabDescr(Uint32& retRef, Uint32& retNo, bool normal)
191 {
192  // merge right
193  while ((retRef + retNo) < cnoOfTabDescrRec) {
194  jam();
195  Uint32 tabDesRef = retRef + retNo;
196  Uint32 headerWord = getTabDescrWord(tabDesRef + ZTD_FL_HEADER);
197  if (headerWord == ZTD_TYPE_FREE) {
198  jam();
199  Uint32 sizeOfMergedPart = getTabDescrWord(tabDesRef + ZTD_FL_SIZE);
200 
201  retNo += sizeOfMergedPart;
202  Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
203  removeTdArea(tabDesRef, list);
204  } else {
205  jam();
206  break;
207  }
208  }
209  // merge left
210  const bool mergeLeft = normal;
211  while (mergeLeft && retRef > 0) {
212  jam();
213  Uint32 trailerWord = getTabDescrWord(retRef - ZTD_TR_TYPE);
214  if (trailerWord == ZTD_TYPE_FREE) {
215  jam();
216  Uint32 sizeOfMergedPart = getTabDescrWord(retRef - ZTD_TR_SIZE);
217  ndbrequire(retRef >= sizeOfMergedPart);
218  retRef -= sizeOfMergedPart;
219  retNo += sizeOfMergedPart;
220  Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
221  removeTdArea(retRef, list);
222  } else {
223  jam();
224  break;
225  }
226  }
227  ndbrequire((retRef + retNo) <= cnoOfTabDescrRec);
228 }//Dbtup::itdaMergeTabDescr()
229 
230 /* ---------------------------------------------------------------- */
231 /* ------------------------ REMOVE_TD_AREA ------------------------ */
232 /* ---------------------------------------------------------------- */
233 /* */
234 /* THIS ROUTINE REMOVES A TD CHUNK FROM THE POOL OF TD RECORDS */
235 /* */
236 /* INPUT: TLIST LIST TO USE */
237 /* TAB_DESCR_PTR POINTS TO THE CHUNK TO BE REMOVED */
238 /* */
239 /* SHORTNAME: RMTA */
240 /* -----------------------------------------------------------------*/
241 void Dbtup::removeTdArea(Uint32 tabDesRef, Uint32 list)
242 {
243  ndbrequire(list < 16);
244  RSS_OP_ALLOC_X(cnoOfFreeTabDescrRec, 1 << list);
245 
246  Uint32 tabDescrNextPtr = getTabDescrWord(tabDesRef + ZTD_FL_NEXT);
247  Uint32 tabDescrPrevPtr = getTabDescrWord(tabDesRef + ZTD_FL_PREV);
248 
249  setTabDescrWord(tabDesRef + ZTD_HEADER, ZTD_TYPE_NORMAL);
250  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);
251 
252  if (tabDesRef == cfreeTdList[list]) {
253  jam();
254  cfreeTdList[list] = tabDescrNextPtr; /* RELINK THE LIST */
255  }//if
256  if (tabDescrNextPtr != RNIL) {
257  jam();
258  setTabDescrWord(tabDescrNextPtr + ZTD_FL_PREV, tabDescrPrevPtr);
259  }//if
260  if (tabDescrPrevPtr != RNIL) {
261  jam();
262  setTabDescrWord(tabDescrPrevPtr + ZTD_FL_NEXT, tabDescrNextPtr);
263  }//if
264 }//Dbtup::removeTdArea()
265 
266 #if defined VM_TRACE || defined ERROR_INSERT
267 void
268 Dbtup::verifytabdes()
269 {
270  struct WordType {
271  short fl; // free list 0-15
272  short ti; // table id
273  short td; // table descriptor area 0 or >0 for dynamic
274  WordType() : fl(-1), ti(-1), td(-1) {}
275  };
276  WordType* wt = new WordType [cnoOfTabDescrRec];
277  uint free_words = 0;
278  uint free_frags = 0;
279  uint used_words = 0;
280  // free lists
281  {
282  for (uint i = 0; i < 16; i++) {
283  Uint32 desc2 = RNIL;
284  Uint32 desc = cfreeTdList[i];
285  while (desc != RNIL) {
286  const Uint32 size = (1 << i);
287  ndbrequire(size >= ZTD_FREE_SIZE);
288  ndbrequire(desc + size <= cnoOfTabDescrRec);
289  { Uint32 index = desc + ZTD_FL_HEADER;
290  ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
291  }
292  { Uint32 index = desc + ZTD_FL_SIZE;
293  ndbrequire(tableDescriptor[index].tabDescr == size);
294  }
295  { Uint32 index = desc + size - ZTD_TR_TYPE;
296  ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
297  }
298  { Uint32 index = desc + size - ZTD_TR_SIZE;
299  ndbrequire(tableDescriptor[index].tabDescr == size);
300  }
301  { Uint32 index = desc + ZTD_FL_PREV;
302  ndbrequire(tableDescriptor[index].tabDescr == desc2);
303  }
304  for (uint j = 0; j < size; j++) {
305  ndbrequire(wt[desc + j].fl == -1);
306  wt[desc + j].fl = i;
307  }
308  desc2 = desc;
309  desc = tableDescriptor[desc + ZTD_FL_NEXT].tabDescr;
310  free_words += (1 << i);
311  free_frags++;
312  }
313  }
314  }
315  // tables
316  {
317  for (uint i = 0; i < cnoOfTablerec; i++) {
318  TablerecPtr ptr;
319  ptr.i = i;
320  ptrAss(ptr, tablerec);
321  if (ptr.p->tableStatus != DEFINED)
322  continue;
323  {
324  Uint32 offset[10];
325  const Uint32 alloc = getTabDescrOffsets(ptr.p->m_no_of_attributes,
326  ptr.p->noOfCharsets,
327  ptr.p->noOfKeyAttr,
328  ptr.p->m_no_of_extra_columns,
329  offset);
330  const Uint32 desc = ptr.p->readKeyArray - offset[3];
331  Uint32 size = alloc;
332  if (size % ZTD_FREE_SIZE != 0)
333  size += ZTD_FREE_SIZE - size % ZTD_FREE_SIZE;
334  ndbrequire(desc + size <= cnoOfTabDescrRec);
335  { Uint32 index = desc + ZTD_FL_HEADER;
336  ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
337  }
338  { Uint32 index = desc + ZTD_FL_SIZE;
339  ndbrequire(tableDescriptor[index].tabDescr == size);
340  }
341  { Uint32 index = desc + size - ZTD_TR_TYPE;
342  ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
343  }
344  { Uint32 index = desc + size - ZTD_TR_SIZE;
345  ndbrequire(tableDescriptor[index].tabDescr == size);
346  }
347  for (uint j = 0; j < size; j++) {
348  ndbrequire(wt[desc + j].ti == -1);
349  wt[desc + j].ti = i;
350  wt[desc + j].td = 0;
351  }
352  used_words += size;
353  }
354  for (uint k = 0; k < NO_DYNAMICS; k++)
355  {
356  Uint32 offset[3];
357  Uint32 MaskSize = (ptr.p->m_dyn_null_bits[k] + 31) >> 5;
358  const Uint32 alloc = getDynTabDescrOffsets(MaskSize, offset);
359  const Uint32 desc = ptr.p->dynTabDescriptor[k];
360  Uint32 size = alloc;
361  if (size % ZTD_FREE_SIZE != 0)
362  size += ZTD_FREE_SIZE - size % ZTD_FREE_SIZE;
363  ndbrequire(desc + size <= cnoOfTabDescrRec);
364  { Uint32 index = desc + ZTD_FL_HEADER;
365  ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
366  }
367  { Uint32 index = desc + ZTD_FL_SIZE;
368  ndbrequire(tableDescriptor[index].tabDescr == size);
369  }
370  { Uint32 index = desc + size - ZTD_TR_TYPE;
371  ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
372  }
373  { Uint32 index = desc + size - ZTD_TR_SIZE;
374  ndbrequire(tableDescriptor[index].tabDescr == size);
375  }
376  for (uint j = 0; j < size; j++) {
377  ndbrequire(wt[desc + j].ti == -1);
378  wt[desc + j].ti = i;
379  wt[desc + j].td = 1 + k;
380  }
381  used_words += size;
382  }
383  }
384  }
385  // all words
386  {
387  for (uint i = 0; i < cnoOfTabDescrRec; i++) {
388  bool is_fl = wt[i].fl != -1;
389  bool is_ti = wt[i].ti != -1;
390  ndbrequire(is_fl != is_ti);
391  }
392  }
393  delete [] wt;
394  ndbrequire(used_words + free_words == cnoOfTabDescrRec);
395  ndbout << "verifytabdes:"
396  << " total: " << cnoOfTabDescrRec
397  << " used: " << used_words
398  << " free: " << free_words
399  << " frags: " << free_frags
400  << endl;
401 }
402 #endif