release/src/router/mysql/storage/ndb/src/kernel/blocks/dbtup/DbtupTabDesMan.cpp

   1 /* Copyright (c) 2003-2007 MySQL AB
   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 as published by
   5    the Free Software Foundation; version 2 of the License.
   6
   7    This program is distributed in the hope that it will be useful,
   8    but WITHOUT ANY WARRANTY; without even the implied warranty of
   9    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10    GNU General Public License for more details.
  11
  12    You should have received a copy of the GNU General Public License
  13    along with this program; if not, write to the Free Software
  14    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA */
  15
  16
  17 #define DBTUP_C
  18 #define DBTUP_TAB_DES_MAN_CPP
  19 #include "Dbtup.hpp"
  20 #include <RefConvert.hpp>
  21 #include <ndb_limits.h>
  22 #include <pc.hpp>
  23
  24 /*
  25  * TABLE DESCRIPTOR MEMORY MANAGER
  26  *
  27  * Each table has a descriptor which is a contiguous array of words.
  28  * The descriptor is allocated from a global array using a buddy
  29  * algorithm.  Free lists exist for each power of 2 words.  Freeing
  30  * a piece first merges with free right and left neighbours and then
  31  * divides itself up into free list chunks.
  32  */
  33
  34 Uint32
  35 Dbtup::getTabDescrOffsets(const Tablerec* regTabPtr, Uint32* offset)
  36 {
  37   // belongs to configure.in
  38   unsigned sizeOfPointer = sizeof(CHARSET_INFO*);
  39   ndbrequire((sizeOfPointer & 0x3) == 0);
  40   sizeOfPointer = (sizeOfPointer >> 2);
  41   // do in layout order and return offsets (see DbtupMeta.cpp)
  42   Uint32 allocSize = 0;
  43   // magically aligned to 8 bytes
  44   offset[0] = allocSize += ZTD_SIZE;
  45   offset[1] = allocSize += regTabPtr->m_no_of_attributes* sizeOfReadFunction();
  46   offset[2] = allocSize += regTabPtr->m_no_of_attributes* sizeOfReadFunction();
  47   offset[3] = allocSize += regTabPtr->noOfCharsets * sizeOfPointer;
  48   offset[4] = allocSize += regTabPtr->noOfKeyAttr;
  49   offset[5] = allocSize += regTabPtr->m_no_of_attributes * ZAD_SIZE;
  50   offset[6] = allocSize += (regTabPtr->m_no_of_attributes + 1) >> 1; // real order
  51   allocSize += ZTD_TRAILER_SIZE;
  52   // return number of words
  53   return allocSize;
  54 }
  55
  56 Uint32 Dbtup::allocTabDescr(const Tablerec* regTabPtr, Uint32* offset)
  57 {
  58   Uint32 reference = RNIL;
  59   Uint32 allocSize = getTabDescrOffsets(regTabPtr, offset);
  60 /* ---------------------------------------------------------------- */
  61 /*       ALWAYS ALLOCATE A MULTIPLE OF 16 WORDS                     */
  62 /* ---------------------------------------------------------------- */
  63   allocSize = (((allocSize - 1) >> 4) + 1) << 4;
  64   Uint32 list = nextHigherTwoLog(allocSize - 1);        /* CALCULATE WHICH LIST IT BELONGS TO     */
  65   for (Uint32 i = list; i < 16; i++) {
  66     jam();
  67     if (cfreeTdList[i] != RNIL) {
  68       jam();
  69       reference = cfreeTdList[i];
  70       removeTdArea(reference, i);                       /* REMOVE THE AREA FROM THE FREELIST      */
  71       Uint32 retNo = (1 << i) - allocSize;              /* CALCULATE THE DIFFERENCE               */
  72       if (retNo >= ZTD_FREE_SIZE) {
  73         jam();
  74         // return unused words, of course without attempting left merge
  75         Uint32 retRef = reference + allocSize;
  76         freeTabDescr(retRef, retNo, false);
  77       } else {
  78         jam();
  79         allocSize = 1 << i;
  80       }//if
  81       break;
  82     }//if
  83   }//for
  84   if (reference == RNIL) {
  85     jam();
  86     terrorCode = ZMEM_NOTABDESCR_ERROR;
  87     return RNIL;
  88   } else {
  89     jam();
  90     setTabDescrWord((reference + allocSize) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);
  91     setTabDescrWord(reference + ZTD_DATASIZE, allocSize);
  92
  93      /* INITIALIZE THE TRAILER RECORD WITH TYPE AND SIZE     */
  94      /* THE TRAILER IS USED TO SIMPLIFY MERGE OF FREE AREAS  */
  95
  96     setTabDescrWord(reference + ZTD_HEADER, ZTD_TYPE_NORMAL);
  97     setTabDescrWord((reference + allocSize) - ZTD_TR_SIZE, allocSize);
  98     return reference;
  99   }//if
 100 }//Dbtup::allocTabDescr()
 101
 102 void Dbtup::freeTabDescr(Uint32 retRef, Uint32 retNo, bool normal)
 103 {
 104   itdaMergeTabDescr(retRef, retNo, normal);       /* MERGE WITH POSSIBLE NEIGHBOURS   */
 105   while (retNo >= ZTD_FREE_SIZE) {
 106     jam();
 107     Uint32 list = nextHigherTwoLog(retNo);
 108     list--;     /* RETURN TO NEXT LOWER LIST    */
 109     Uint32 sizeOfChunk = 1 << list;
 110     insertTdArea(retRef, list);
 111     retRef += sizeOfChunk;
 112     retNo -= sizeOfChunk;
 113   }//while
 114   ndbassert(retNo == 0);
 115 }//Dbtup::freeTabDescr()
 116
 117 Uint32
 118 Dbtup::getTabDescrWord(Uint32 index)
 119 {
 120   ndbrequire(index < cnoOfTabDescrRec);
 121   return tableDescriptor[index].tabDescr;
 122 }//Dbtup::getTabDescrWord()
 123
 124 void
 125 Dbtup::setTabDescrWord(Uint32 index, Uint32 word)
 126 {
 127   ndbrequire(index < cnoOfTabDescrRec);
 128   tableDescriptor[index].tabDescr = word;
 129 }//Dbtup::setTabDescrWord()
 130
 131 void Dbtup::insertTdArea(Uint32 tabDesRef, Uint32 list)
 132 {
 133   ndbrequire(list < 16);
 134   setTabDescrWord(tabDesRef + ZTD_FL_HEADER, ZTD_TYPE_FREE);
 135   setTabDescrWord(tabDesRef + ZTD_FL_NEXT, cfreeTdList[list]);
 136   if (cfreeTdList[list] != RNIL) {
 137     jam();                                                /* PREVIOUSLY EMPTY SLOT     */
 138     setTabDescrWord(cfreeTdList[list] + ZTD_FL_PREV, tabDesRef);
 139   }//if
 140   cfreeTdList[list] = tabDesRef;        /* RELINK THE LIST           */
 141
 142   setTabDescrWord(tabDesRef + ZTD_FL_PREV, RNIL);
 143   setTabDescrWord(tabDesRef + ZTD_FL_SIZE, 1 << list);
 144   setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_FREE);
 145   setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_SIZE, 1 << list);
 146 }//Dbtup::insertTdArea()
 147
 148 /*
 149  * Merge to-be-removed chunk (which need not be initialized with header
 150  * and trailer) with left and right buddies.  The start point retRef
 151  * moves to left and the size retNo increases to match the new chunk.
 152  */
 153 void Dbtup::itdaMergeTabDescr(Uint32& retRef, Uint32& retNo, bool normal)
 154 {
 155   // merge right
 156   while ((retRef + retNo) < cnoOfTabDescrRec) {
 157     jam();
 158     Uint32 tabDesRef = retRef + retNo;
 159     Uint32 headerWord = getTabDescrWord(tabDesRef + ZTD_FL_HEADER);
 160     if (headerWord == ZTD_TYPE_FREE) {
 161       jam();
 162       Uint32 sizeOfMergedPart = getTabDescrWord(tabDesRef + ZTD_FL_SIZE);
 163
 164       retNo += sizeOfMergedPart;
 165       Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
 166       removeTdArea(tabDesRef, list);
 167     } else {
 168       jam();
 169       break;
 170     }
 171   }
 172   // merge left
 173   const bool mergeLeft = normal;
 174   while (mergeLeft && retRef > 0) {
 175     jam();
 176     Uint32 trailerWord = getTabDescrWord(retRef - ZTD_TR_TYPE);
 177     if (trailerWord == ZTD_TYPE_FREE) {
 178       jam();
 179       Uint32 sizeOfMergedPart = getTabDescrWord(retRef - ZTD_TR_SIZE);
 180       ndbrequire(retRef >= sizeOfMergedPart);
 181       retRef -= sizeOfMergedPart;
 182       retNo += sizeOfMergedPart;
 183       Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
 184       removeTdArea(retRef, list);
 185     } else {
 186       jam();
 187       break;
 188     }
 189   }
 190   ndbrequire((retRef + retNo) <= cnoOfTabDescrRec);
 191 }//Dbtup::itdaMergeTabDescr()
 192
 193 /* ---------------------------------------------------------------- */
 194 /* ------------------------ REMOVE_TD_AREA ------------------------ */
 195 /* ---------------------------------------------------------------- */
 196 /*                                                                  */
 197 /* THIS ROUTINE REMOVES A TD CHUNK FROM THE POOL OF TD RECORDS      */
 198 /*                                                                  */
 199 /* INPUT:  TLIST          LIST TO USE                               */
 200 /*         TAB_DESCR_PTR  POINTS TO THE CHUNK TO BE REMOVED         */
 201 /*                                                                  */
 202 /* SHORTNAME:   RMTA                                                */
 203 /* -----------------------------------------------------------------*/
 204 void Dbtup::removeTdArea(Uint32 tabDesRef, Uint32 list)
 205 {
 206   ndbrequire(list < 16);
 207   Uint32 tabDescrNextPtr = getTabDescrWord(tabDesRef + ZTD_FL_NEXT);
 208   Uint32 tabDescrPrevPtr = getTabDescrWord(tabDesRef + ZTD_FL_PREV);
 209
 210   setTabDescrWord(tabDesRef + ZTD_HEADER, ZTD_TYPE_NORMAL);
 211   setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);
 212
 213   if (tabDesRef == cfreeTdList[list]) {
 214     jam();
 215     cfreeTdList[list] = tabDescrNextPtr;        /* RELINK THE LIST           */
 216   }//if
 217   if (tabDescrNextPtr != RNIL) {
 218     jam();
 219     setTabDescrWord(tabDescrNextPtr + ZTD_FL_PREV, tabDescrPrevPtr);
 220   }//if
 221   if (tabDescrPrevPtr != RNIL) {
 222     jam();
 223     setTabDescrWord(tabDescrPrevPtr + ZTD_FL_NEXT, tabDescrNextPtr);
 224   }//if
 225 }//Dbtup::removeTdArea()
 226
 227 #ifdef VM_TRACE
 228 void
 229 Dbtup::verifytabdes()
 230 {
 231   struct WordType {
 232     short fl;   // free list 0-15
 233     short ti;   // table id
 234     WordType() : fl(-1), ti(-1) {}
 235   };
 236   WordType* wt = new WordType [cnoOfTabDescrRec];
 237   uint free_frags = 0;
 238   // free lists
 239   {
 240     for (uint i = 0; i < 16; i++) {
 241       Uint32 desc2 = RNIL;
 242       Uint32 desc = cfreeTdList[i];
 243       while (desc != RNIL) {
 244         const Uint32 size = (1 << i);
 245         ndbrequire(size >= ZTD_FREE_SIZE);
 246         ndbrequire(desc + size <= cnoOfTabDescrRec);
 247         { Uint32 index = desc + ZTD_FL_HEADER;
 248           ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
 249         }
 250         { Uint32 index = desc + ZTD_FL_SIZE;
 251           ndbrequire(tableDescriptor[index].tabDescr == size);
 252         }
 253         { Uint32 index = desc + size - ZTD_TR_TYPE;
 254           ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
 255         }
 256         { Uint32 index = desc + size - ZTD_TR_SIZE;
 257           ndbrequire(tableDescriptor[index].tabDescr == size);
 258         }
 259         { Uint32 index = desc + ZTD_FL_PREV;
 260           ndbrequire(tableDescriptor[index].tabDescr == desc2);
 261         }
 262         for (uint j = 0; j < size; j++) {
 263           ndbrequire(wt[desc + j].fl == -1);
 264           wt[desc + j].fl = i;
 265         }
 266         desc2 = desc;
 267         desc = tableDescriptor[desc + ZTD_FL_NEXT].tabDescr;
 268         free_frags++;
 269       }
 270     }
 271   }
 272   // tables
 273   {
 274     for (uint i = 0; i < cnoOfTablerec; i++) {
 275       TablerecPtr ptr;
 276       ptr.i = i;
 277       ptrAss(ptr, tablerec);
 278       if (ptr.p->tableStatus == DEFINED) {
 279         Uint32 offset[10];
 280         const Uint32 alloc = getTabDescrOffsets(ptr.p, offset);
 281         const Uint32 desc = ptr.p->readKeyArray - offset[3];
 282         Uint32 size = alloc;
 283         if (size % ZTD_FREE_SIZE != 0)
 284           size += ZTD_FREE_SIZE - size % ZTD_FREE_SIZE;
 285         ndbrequire(desc + size <= cnoOfTabDescrRec);
 286         { Uint32 index = desc + ZTD_FL_HEADER;
 287           ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
 288         }
 289         { Uint32 index = desc + ZTD_FL_SIZE;
 290           ndbrequire(tableDescriptor[index].tabDescr == size);
 291         }
 292         { Uint32 index = desc + size - ZTD_TR_TYPE;
 293           ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
 294         }
 295         { Uint32 index = desc + size - ZTD_TR_SIZE;
 296           ndbrequire(tableDescriptor[index].tabDescr == size);
 297         }
 298         for (uint j = 0; j < size; j++) {
 299           ndbrequire(wt[desc + j].ti == -1);
 300           wt[desc + j].ti = i;
 301         }
 302       }
 303     }
 304   }
 305   // all words
 306   {
 307     for (uint i = 0; i < cnoOfTabDescrRec; i++) {
 308       bool is_fl = wt[i].fl != -1;
 309       bool is_ti = wt[i].ti != -1;
 310       ndbrequire(is_fl != is_ti);
 311     }
 312   }
 313   delete [] wt;
 314   ndbout << "verifytabdes: frags=" << free_frags << endl;
 315 }
 316 #endif