DbtupTabDesMan.cpp 10.9 KB
Newer Older
1 2 3 4
/* Copyright (C) 2003 MySQL AB

   This program is free software; you can redistribute it and/or modify
   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 8 9 10 11 12 13 14 15 16 17

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


#define DBTUP_C
18
#define DBTUP_TAB_DES_MAN_CPP
19 20 21 22 23
#include "Dbtup.hpp"
#include <RefConvert.hpp>
#include <ndb_limits.h>
#include <pc.hpp>

24 25 26 27 28 29 30 31 32
/*
 * TABLE DESCRIPTOR MEMORY MANAGER
 *
 * Each table has a descriptor which is a contiguous array of words.
 * The descriptor is allocated from a global array using a buddy
 * algorithm.  Free lists exist for each power of 2 words.  Freeing
 * a piece first merges with free right and left neighbours and then
 * divides itself up into free list chunks.
 */
33 34 35 36 37 38 39 40 41 42 43 44

Uint32
Dbtup::getTabDescrOffsets(const Tablerec* regTabPtr, Uint32* offset)
{
  // belongs to configure.in
  unsigned sizeOfPointer = sizeof(CHARSET_INFO*);
  ndbrequire((sizeOfPointer & 0x3) == 0);
  sizeOfPointer = (sizeOfPointer >> 2);
  // do in layout order and return offsets (see DbtupMeta.cpp)
  Uint32 allocSize = 0;
  // magically aligned to 8 bytes
  offset[0] = allocSize += ZTD_SIZE;
45 46
  offset[1] = allocSize += regTabPtr->m_no_of_attributes* sizeOfReadFunction();
  offset[2] = allocSize += regTabPtr->m_no_of_attributes* sizeOfReadFunction();
47 48
  offset[3] = allocSize += regTabPtr->noOfCharsets * sizeOfPointer;
  offset[4] = allocSize += regTabPtr->noOfKeyAttr;
49 50
  offset[5] = allocSize += regTabPtr->m_no_of_attributes * ZAD_SIZE;
  offset[6] = allocSize += (regTabPtr->m_no_of_attributes + 1) >> 1; // real order
51 52 53 54 55 56
  allocSize += ZTD_TRAILER_SIZE;
  // return number of words
  return allocSize;
}

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 64 65
/* ---------------------------------------------------------------- */
  allocSize = (((allocSize - 1) >> 4) + 1) << 4;
  Uint32 list = nextHigherTwoLog(allocSize - 1);	/* CALCULATE WHICH LIST IT BELONGS TO     */
  for (Uint32 i = list; i < 16; i++) {
66
    jam();
67
    if (cfreeTdList[i] != RNIL) {
68
      jam();
69 70 71 72
      reference = cfreeTdList[i];
      removeTdArea(reference, i);	                /* REMOVE THE AREA FROM THE FREELIST      */
      Uint32 retNo = (1 << i) - allocSize;	        /* CALCULATE THE DIFFERENCE               */
      if (retNo >= ZTD_FREE_SIZE) {
73
        jam();
74 75 76
        // return unused words, of course without attempting left merge
        Uint32 retRef = reference + allocSize;
        freeTabDescr(retRef, retNo, false);
77
      } else {
78
        jam();
79 80 81 82 83 84
        allocSize = 1 << i;
      }//if
      break;
    }//if
  }//for
  if (reference == RNIL) {
85
    jam();
86 87 88
    terrorCode = ZMEM_NOTABDESCR_ERROR;
    return RNIL;
  } else {
89
    jam();
90 91 92 93 94 95 96 97 98 99 100 101
    setTabDescrWord((reference + allocSize) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);
    setTabDescrWord(reference + ZTD_DATASIZE, allocSize);

     /* INITIALIZE THE TRAILER RECORD WITH TYPE AND SIZE     */
     /* THE TRAILER IS USED TO SIMPLIFY MERGE OF FREE AREAS  */

    setTabDescrWord(reference + ZTD_HEADER, ZTD_TYPE_NORMAL);
    setTabDescrWord((reference + allocSize) - ZTD_TR_SIZE, allocSize);
    return reference;
  }//if
}//Dbtup::allocTabDescr()

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 108 109
    Uint32 list = nextHigherTwoLog(retNo);
    list--;	/* RETURN TO NEXT LOWER LIST    */
    Uint32 sizeOfChunk = 1 << list;
110
    insertTdArea(retRef, list);
111 112 113
    retRef += sizeOfChunk;
    retNo -= sizeOfChunk;
  }//while
114
  ndbassert(retNo == 0);
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
}//Dbtup::freeTabDescr()

Uint32
Dbtup::getTabDescrWord(Uint32 index)
{
  ndbrequire(index < cnoOfTabDescrRec);
  return tableDescriptor[index].tabDescr;
}//Dbtup::getTabDescrWord()

void
Dbtup::setTabDescrWord(Uint32 index, Uint32 word)
{
  ndbrequire(index < cnoOfTabDescrRec);
  tableDescriptor[index].tabDescr = word;
}//Dbtup::setTabDescrWord()

131
void Dbtup::insertTdArea(Uint32 tabDesRef, Uint32 list) 
132 133 134 135 136
{
  ndbrequire(list < 16);
  setTabDescrWord(tabDesRef + ZTD_FL_HEADER, ZTD_TYPE_FREE);
  setTabDescrWord(tabDesRef + ZTD_FL_NEXT, cfreeTdList[list]);
  if (cfreeTdList[list] != RNIL) {
137
    jam();                                                /* PREVIOUSLY EMPTY SLOT     */
138 139 140 141 142 143 144 145 146 147
    setTabDescrWord(cfreeTdList[list] + ZTD_FL_PREV, tabDesRef);
  }//if
  cfreeTdList[list] = tabDesRef;	/* RELINK THE LIST           */

  setTabDescrWord(tabDesRef + ZTD_FL_PREV, RNIL);
  setTabDescrWord(tabDesRef + ZTD_FL_SIZE, 1 << list);
  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_FREE);
  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_SIZE, 1 << list);
}//Dbtup::insertTdArea()

148 149 150 151 152 153
/*
 * Merge to-be-removed chunk (which need not be initialized with header
 * and trailer) with left and right buddies.  The start point retRef
 * moves to left and the size retNo increases to match the new chunk.
 */
void Dbtup::itdaMergeTabDescr(Uint32& retRef, Uint32& retNo, bool normal)
154
{
155
  // merge right
156
  while ((retRef + retNo) < cnoOfTabDescrRec) {
157
    jam();
158 159 160
    Uint32 tabDesRef = retRef + retNo;
    Uint32 headerWord = getTabDescrWord(tabDesRef + ZTD_FL_HEADER);
    if (headerWord == ZTD_TYPE_FREE) {
161
      jam();
162 163 164 165 166 167
      Uint32 sizeOfMergedPart = getTabDescrWord(tabDesRef + ZTD_FL_SIZE);

      retNo += sizeOfMergedPart;
      Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
      removeTdArea(tabDesRef, list);
    } else {
168
      jam();
169 170 171 172 173 174
      break;
    }
  }
  // merge left
  const bool mergeLeft = normal;
  while (mergeLeft && retRef > 0) {
175
    jam();
176 177
    Uint32 trailerWord = getTabDescrWord(retRef - ZTD_TR_TYPE);
    if (trailerWord == ZTD_TYPE_FREE) {
178
      jam();
179 180 181 182 183 184 185
      Uint32 sizeOfMergedPart = getTabDescrWord(retRef - ZTD_TR_SIZE);
      ndbrequire(retRef >= sizeOfMergedPart);
      retRef -= sizeOfMergedPart;
      retNo += sizeOfMergedPart;
      Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
      removeTdArea(retRef, list);
    } else {
186
      jam();
187 188 189 190
      break;
    }
  }
  ndbrequire((retRef + retNo) <= cnoOfTabDescrRec);
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
}//Dbtup::itdaMergeTabDescr()

/* ---------------------------------------------------------------- */
/* ------------------------ REMOVE_TD_AREA ------------------------ */
/* ---------------------------------------------------------------- */
/*                                                                  */
/* THIS ROUTINE REMOVES A TD CHUNK FROM THE POOL OF TD RECORDS      */
/*                                                                  */
/* INPUT:  TLIST          LIST TO USE                               */
/*         TAB_DESCR_PTR  POINTS TO THE CHUNK TO BE REMOVED         */
/*                                                                  */
/* SHORTNAME:   RMTA                                                */
/* -----------------------------------------------------------------*/
void Dbtup::removeTdArea(Uint32 tabDesRef, Uint32 list) 
{
  ndbrequire(list < 16);
  Uint32 tabDescrNextPtr = getTabDescrWord(tabDesRef + ZTD_FL_NEXT);
  Uint32 tabDescrPrevPtr = getTabDescrWord(tabDesRef + ZTD_FL_PREV);

  setTabDescrWord(tabDesRef + ZTD_HEADER, ZTD_TYPE_NORMAL);
  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);

  if (tabDesRef == cfreeTdList[list]) {
214
    jam();
215 216 217
    cfreeTdList[list] = tabDescrNextPtr;	/* RELINK THE LIST           */
  }//if
  if (tabDescrNextPtr != RNIL) {
218
    jam();
219 220 221
    setTabDescrWord(tabDescrNextPtr + ZTD_FL_PREV, tabDescrPrevPtr);
  }//if
  if (tabDescrPrevPtr != RNIL) {
222
    jam();
223 224 225
    setTabDescrWord(tabDescrPrevPtr + ZTD_FL_NEXT, tabDescrNextPtr);
  }//if
}//Dbtup::removeTdArea()
226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316

#ifdef VM_TRACE
void
Dbtup::verifytabdes()
{
  struct WordType {
    short fl;   // free list 0-15
    short ti;   // table id
    WordType() : fl(-1), ti(-1) {}
  };
  WordType* wt = new WordType [cnoOfTabDescrRec];
  uint free_frags = 0;
  // free lists
  {
    for (uint i = 0; i < 16; i++) {
      Uint32 desc2 = RNIL;
      Uint32 desc = cfreeTdList[i];
      while (desc != RNIL) {
        const Uint32 size = (1 << i);
        ndbrequire(size >= ZTD_FREE_SIZE);
        ndbrequire(desc + size <= cnoOfTabDescrRec);
        { Uint32 index = desc + ZTD_FL_HEADER;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
        }
        { Uint32 index = desc + ZTD_FL_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        { Uint32 index = desc + size - ZTD_TR_TYPE;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
        }
        { Uint32 index = desc + size - ZTD_TR_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        { Uint32 index = desc + ZTD_FL_PREV;
          ndbrequire(tableDescriptor[index].tabDescr == desc2);
        }
        for (uint j = 0; j < size; j++) {
          ndbrequire(wt[desc + j].fl == -1);
          wt[desc + j].fl = i;
        }
        desc2 = desc;
        desc = tableDescriptor[desc + ZTD_FL_NEXT].tabDescr;
        free_frags++;
      }
    }
  }
  // tables
  {
    for (uint i = 0; i < cnoOfTablerec; i++) {
      TablerecPtr ptr;
      ptr.i = i;
      ptrAss(ptr, tablerec);
      if (ptr.p->tableStatus == DEFINED) {
        Uint32 offset[10];
        const Uint32 alloc = getTabDescrOffsets(ptr.p, offset);
        const Uint32 desc = ptr.p->readKeyArray - offset[3];
        Uint32 size = alloc;
        if (size % ZTD_FREE_SIZE != 0)
          size += ZTD_FREE_SIZE - size % ZTD_FREE_SIZE;
        ndbrequire(desc + size <= cnoOfTabDescrRec);
        { Uint32 index = desc + ZTD_FL_HEADER;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
        }
        { Uint32 index = desc + ZTD_FL_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        { Uint32 index = desc + size - ZTD_TR_TYPE;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
        }
        { Uint32 index = desc + size - ZTD_TR_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        for (uint j = 0; j < size; j++) {
          ndbrequire(wt[desc + j].ti == -1);
          wt[desc + j].ti = i;
        }
      }
    }
  }
  // all words
  {
    for (uint i = 0; i < cnoOfTabDescrRec; i++) {
      bool is_fl = wt[i].fl != -1;
      bool is_ti = wt[i].ti != -1;
      ndbrequire(is_fl != is_ti);
    }
  }
  delete [] wt;
  ndbout << "verifytabdes: frags=" << free_frags << endl;
}
#endif