← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to storage/ndb/src/kernel/blocks/dbtup/DbtupPagMan.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/ndb/src/kernel/blocks/dbtup/DbtupPagMan.cpp
 
1
/* Copyright (C) 2003 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
#define DBTUP_C
 
17
#define DBTUP_PAG_MAN_CPP
 
18
#include "Dbtup.hpp"
 
19
#include <RefConvert.hpp>
 
20
#include <ndb_limits.h>
 
21
#include <pc.hpp>
 
22
 
 
23
/* ---------------------------------------------------------------- */
 
24
// 4) Page Memory Manager (buddy algorithm)
 
25
//
 
26
// The following data structures in Dbtup is used by the Page Memory
 
27
// Manager.
 
28
//
 
29
// cfreepageList[16]
 
30
// Pages with a header
 
31
//
 
32
// The cfreepageList is 16 free lists. Free list 0 contains chunks of
 
33
// pages with 2^0 (=1) pages in each chunk. Free list 1 chunks of 2^1
 
34
// (=2) pages in each chunk and so forth upto free list 15 which
 
35
// contains chunks of 2^15 (=32768) pages in each chunk.
 
36
// The cfreepageList array contains the pointer to the first chunk
 
37
// in each of those lists. The lists are doubly linked where the
 
38
// first page in each chunk contains the next and previous references
 
39
// in position ZPAGE_NEXT_CLUST_POS and ZPAGE_PREV_CLUST_POS in the
 
40
// page header.
 
41
// In addition the leading page and the last page in each chunk is marked
 
42
// with a state (=ZFREE_COMMON) in position ZPAGE_STATE_POS in page
 
43
// header. This state indicates that the page is the leading or last page
 
44
// in a chunk of free pages. Furthermore the leading and last page is
 
45
// also marked with a reference to the leading (=ZPAGE_FIRST_CLUST_POS)
 
46
// and the last page (=ZPAGE_LAST_CLUST_POS) in the chunk.
 
47
//
 
48
// The aim of these data structures is to enable a free area handling of
 
49
// free pages based on a buddy algorithm. When allocating pages it is
 
50
// performed in chunks of pages and the algorithm tries to make the
 
51
// chunks as large as possible.
 
52
// This manager is invoked when fragments lack internal page space to
 
53
// accomodate all the data they are requested to store. It is also
 
54
// invoked when fragments deallocate page space back to the free area.
 
55
//
 
56
// The following routines are part of the external interface:
 
57
// void
 
58
// allocConsPages(Uint32  noOfPagesToAllocate, #In
 
59
//                Uint32& noOfPagesAllocated,  #Out
 
60
//                Uint32& retPageRef)          #Out
 
61
// void
 
62
// returnCommonArea(Uint32 retPageRef,         #In
 
63
//                  Uint32 retNoPages)         #In
 
64
//
 
65
// allocConsPages tries to allocate noOfPagesToAllocate pages in one chunk.
 
66
// If this fails it delivers a chunk as large as possible. It returns the
 
67
// i-value of the first page in the chunk delivered, if zero pages returned
 
68
// this i-value is undefined. It also returns the size of the chunk actually
 
69
// delivered.
 
70
// 
 
71
// returnCommonArea is used when somebody is returning pages to the free area.
 
72
// It is used both from internal routines and external routines.
 
73
//
 
74
// The following routines are private routines used to support the
 
75
// above external interface:
 
76
// removeCommonArea()
 
77
// insertCommonArea()
 
78
// findFreeLeftNeighbours()
 
79
// findFreeRightNeighbours()
 
80
// Uint32
 
81
// nextHigherTwoLog(Uint32 input)
 
82
//
 
83
// nextHigherTwoLog is a support routine which is a mathematical function with
 
84
// an integer as input and an integer as output. It calculates the 2-log of
 
85
// (input + 1). If the 2-log of (input + 1) is larger than 15 then the routine
 
86
// will return 15. It is part of the external interface since it is also used
 
87
// by other similar memory management algorithms.
 
88
//
 
89
// External dependencies:
 
90
// None.
 
91
//
 
92
// Side Effects:
 
93
// Apart from the above mentioned data structures there are no more
 
94
// side effects other than through the subroutine parameters in the
 
95
// external interface.
 
96
//
 
97
/* ---------------------------------------------------------------- */
 
98
 
 
99
/* ---------------------------------------------------------------- */
 
100
/* CALCULATE THE 2-LOG + 1 OF TMP AND PUT RESULT INTO TBITS         */
 
101
/* ---------------------------------------------------------------- */
 
102
Uint32 Dbtup::nextHigherTwoLog(Uint32 input) 
 
103
{
 
104
  input = input | (input >> 8);
 
105
  input = input | (input >> 4);
 
106
  input = input | (input >> 2);
 
107
  input = input | (input >> 1);
 
108
  Uint32 output = (input & 0x5555) + ((input >> 1) & 0x5555);
 
109
  output = (output & 0x3333) + ((output >> 2) & 0x3333);
 
110
  output = output + (output >> 4);
 
111
  output = (output & 0xf) + ((output >> 8) & 0xf);
 
112
  return output;
 
113
}//nextHigherTwoLog()
 
114
 
 
115
void Dbtup::initializePage() 
 
116
{
 
117
  for (Uint32 i = 0; i < 16; i++) {
 
118
    cfreepageList[i] = RNIL;
 
119
  }//for
 
120
  PagePtr pagePtr;
 
121
  for (pagePtr.i = 0; pagePtr.i < c_page_pool.getSize(); pagePtr.i++) {
 
122
    jam();
 
123
    refresh_watch_dog();
 
124
    c_page_pool.getPtr(pagePtr);
 
125
    pagePtr.p->physical_page_id= RNIL;
 
126
    pagePtr.p->next_page = pagePtr.i + 1;
 
127
    pagePtr.p->first_cluster_page = RNIL;
 
128
    pagePtr.p->next_cluster_page = RNIL;
 
129
    pagePtr.p->last_cluster_page = RNIL;
 
130
    pagePtr.p->prev_page = RNIL;
 
131
    pagePtr.p->page_state = ZFREE_COMMON;
 
132
  }//for
 
133
  pagePtr.p->next_page = RNIL;
 
134
  
 
135
  /**
 
136
   * Page 0 cant be part of buddy as 
 
137
   *   it will scan left right when searching for bigger blocks,
 
138
   *   if 0 is part of arrat, it can search to -1...which is not good
 
139
   */
 
140
  pagePtr.i = 0;
 
141
  c_page_pool.getPtr(pagePtr);
 
142
  pagePtr.p->page_state = ~ZFREE_COMMON;
 
143
 
 
144
  Uint32 tmp = 1;
 
145
  returnCommonArea(tmp, c_page_pool.getSize() - tmp);
 
146
  cnoOfAllocatedPages = tmp; // Is updated by returnCommonArea
 
147
}//Dbtup::initializePage()
 
148
 
 
149
#ifdef VM_TRACE
 
150
Uint32 fc_left, fc_right, fc_remove;
 
151
#endif
 
152
 
 
153
void Dbtup::allocConsPages(Uint32 noOfPagesToAllocate,
 
154
                           Uint32& noOfPagesAllocated,
 
155
                           Uint32& allocPageRef)
 
156
{
 
157
#ifdef VM_TRACE
 
158
  fc_left = fc_right = fc_remove = 0;
 
159
#endif
 
160
  if (noOfPagesToAllocate == 0){ 
 
161
    jam();
 
162
    noOfPagesAllocated = 0;
 
163
    return;
 
164
  }//if
 
165
 
 
166
  Uint32 firstListToCheck = nextHigherTwoLog(noOfPagesToAllocate - 1);
 
167
  for (Uint32 i = firstListToCheck; i < 16; i++) {
 
168
    jam();
 
169
    if (cfreepageList[i] != RNIL) {
 
170
      jam();
 
171
/* ---------------------------------------------------------------- */
 
172
/*       PROPER AMOUNT OF PAGES WERE FOUND. NOW SPLIT THE FOUND     */
 
173
/*       AREA AND RETURN THE PART NOT NEEDED.                       */
 
174
/* ---------------------------------------------------------------- */
 
175
      noOfPagesAllocated = noOfPagesToAllocate;
 
176
      allocPageRef = cfreepageList[i];
 
177
      removeCommonArea(allocPageRef, i);
 
178
      Uint32 retNo = (1 << i) - noOfPagesToAllocate;
 
179
      Uint32 retPageRef = allocPageRef + noOfPagesToAllocate;
 
180
      returnCommonArea(retPageRef, retNo);
 
181
      return;
 
182
    }//if
 
183
  }//for
 
184
/* ---------------------------------------------------------------- */
 
185
/*       PROPER AMOUNT OF PAGES WERE NOT FOUND. FIND AS MUCH AS     */
 
186
/*       POSSIBLE.                                                  */
 
187
/* ---------------------------------------------------------------- */
 
188
  if (firstListToCheck)
 
189
  {
 
190
    jam();
 
191
    for (Uint32 j = firstListToCheck - 1; (Uint32)~j; j--) {
 
192
      jam();
 
193
      if (cfreepageList[j] != RNIL) {
 
194
        jam();
 
195
/* ---------------------------------------------------------------- */
 
196
/*       SOME AREA WAS FOUND, ALLOCATE ALL OF IT.                   */
 
197
/* ---------------------------------------------------------------- */
 
198
        allocPageRef = cfreepageList[j];
 
199
        removeCommonArea(allocPageRef, j);
 
200
        noOfPagesAllocated = 1 << j;
 
201
        findFreeLeftNeighbours(allocPageRef, noOfPagesAllocated, 
 
202
                               noOfPagesToAllocate);
 
203
        findFreeRightNeighbours(allocPageRef, noOfPagesAllocated, 
 
204
                                noOfPagesToAllocate);
 
205
        
 
206
        return;
 
207
      }//if
 
208
    }//for
 
209
  }
 
210
/* ---------------------------------------------------------------- */
 
211
/*       NO FREE AREA AT ALL EXISTED. RETURN ZERO PAGES             */
 
212
/* ---------------------------------------------------------------- */
 
213
  noOfPagesAllocated = 0;
 
214
  return;
 
215
}//allocConsPages()
 
216
 
 
217
void Dbtup::returnCommonArea(Uint32 retPageRef, Uint32 retNo) 
 
218
{
 
219
  do {
 
220
    jam();
 
221
    if (retNo == 0) {
 
222
      jam();
 
223
      return;
 
224
    }//if
 
225
    Uint32 list = nextHigherTwoLog(retNo) - 1;
 
226
    retNo -= (1 << list);
 
227
    insertCommonArea(retPageRef, list);
 
228
    retPageRef += (1 << list);
 
229
  } while (1);
 
230
}//Dbtup::returnCommonArea()
 
231
 
 
232
void Dbtup::findFreeLeftNeighbours(Uint32& allocPageRef,
 
233
                                   Uint32& noPagesAllocated,
 
234
                                   Uint32  noOfPagesToAllocate)
 
235
{
 
236
  PagePtr pageFirstPtr, pageLastPtr;
 
237
  Uint32 remainAllocate = noOfPagesToAllocate - noPagesAllocated;
 
238
  Uint32 loop = 0;
 
239
  while (allocPageRef > 0 && 
 
240
         ++loop < 16) 
 
241
  {
 
242
    jam();
 
243
    pageLastPtr.i = allocPageRef - 1;
 
244
    c_page_pool.getPtr(pageLastPtr);
 
245
    if (pageLastPtr.p->page_state != ZFREE_COMMON) {
 
246
      jam();
 
247
      return;
 
248
    } else {
 
249
      jam();
 
250
      pageFirstPtr.i = pageLastPtr.p->first_cluster_page;
 
251
      ndbrequire(pageFirstPtr.i != RNIL);
 
252
      Uint32 list = nextHigherTwoLog(pageLastPtr.i - pageFirstPtr.i);
 
253
      removeCommonArea(pageFirstPtr.i, list);
 
254
      Uint32 listSize = 1 << list;
 
255
      if (listSize > remainAllocate) {
 
256
        jam();
 
257
        Uint32 retNo = listSize - remainAllocate;
 
258
        returnCommonArea(pageFirstPtr.i, retNo);
 
259
        allocPageRef = pageFirstPtr.i + retNo;
 
260
        noPagesAllocated = noOfPagesToAllocate;
 
261
        return;
 
262
      } else {
 
263
        jam();
 
264
        allocPageRef = pageFirstPtr.i;
 
265
        noPagesAllocated += listSize;
 
266
        remainAllocate -= listSize;
 
267
      }//if
 
268
    }//if
 
269
#ifdef VM_TRACE
 
270
    fc_left++;
 
271
#endif
 
272
  }//while
 
273
}//Dbtup::findFreeLeftNeighbours()
 
274
 
 
275
void Dbtup::findFreeRightNeighbours(Uint32& allocPageRef,
 
276
                                    Uint32& noPagesAllocated,
 
277
                                    Uint32  noOfPagesToAllocate)
 
278
{
 
279
  PagePtr pageFirstPtr, pageLastPtr;
 
280
  Uint32 remainAllocate = noOfPagesToAllocate - noPagesAllocated;
 
281
  if (remainAllocate == 0) {
 
282
    jam();
 
283
    return;
 
284
  }//if
 
285
  Uint32 loop = 0;
 
286
  while ((allocPageRef + noPagesAllocated) < c_page_pool.getSize() &&
 
287
         ++loop < 16) 
 
288
  {
 
289
    jam();
 
290
    pageFirstPtr.i = allocPageRef + noPagesAllocated;
 
291
    c_page_pool.getPtr(pageFirstPtr);
 
292
    if (pageFirstPtr.p->page_state != ZFREE_COMMON) {
 
293
      jam();
 
294
      return;
 
295
    } else {
 
296
      jam();
 
297
      pageLastPtr.i = pageFirstPtr.p->last_cluster_page;
 
298
      ndbrequire(pageLastPtr.i != RNIL);
 
299
      Uint32 list = nextHigherTwoLog(pageLastPtr.i - pageFirstPtr.i);
 
300
      removeCommonArea(pageFirstPtr.i, list);
 
301
      Uint32 listSize = 1 << list;
 
302
      if (listSize > remainAllocate) {
 
303
        jam();
 
304
        Uint32 retPageRef = pageFirstPtr.i + remainAllocate;
 
305
        Uint32 retNo = listSize - remainAllocate;
 
306
        returnCommonArea(retPageRef, retNo);
 
307
        noPagesAllocated += remainAllocate;
 
308
        return;
 
309
      } else {
 
310
        jam();
 
311
        noPagesAllocated += listSize;
 
312
        remainAllocate -= listSize;
 
313
      }//if
 
314
    }//if
 
315
#ifdef VM_TRACE
 
316
    fc_right++;
 
317
#endif
 
318
  }//while
 
319
}//Dbtup::findFreeRightNeighbours()
 
320
 
 
321
void Dbtup::insertCommonArea(Uint32 insPageRef, Uint32 insList) 
 
322
{
 
323
  cnoOfAllocatedPages -= (1 << insList);
 
324
  PagePtr pageLastPtr, pageInsPtr, pageHeadPtr;
 
325
 
 
326
  pageHeadPtr.i = cfreepageList[insList];
 
327
  c_page_pool.getPtr(pageInsPtr, insPageRef);
 
328
  ndbrequire(insList < 16);
 
329
  pageLastPtr.i = (pageInsPtr.i + (1 << insList)) - 1;
 
330
 
 
331
  pageInsPtr.p->page_state = ZFREE_COMMON;
 
332
  pageInsPtr.p->next_cluster_page = pageHeadPtr.i;
 
333
  pageInsPtr.p->prev_cluster_page = RNIL;
 
334
  pageInsPtr.p->last_cluster_page = pageLastPtr.i;
 
335
  cfreepageList[insList] = pageInsPtr.i;
 
336
 
 
337
  if (pageHeadPtr.i != RNIL)
 
338
  {
 
339
    jam();
 
340
    c_page_pool.getPtr(pageHeadPtr);
 
341
    pageHeadPtr.p->prev_cluster_page = pageInsPtr.i;
 
342
  }
 
343
  
 
344
  c_page_pool.getPtr(pageLastPtr);
 
345
  pageLastPtr.p->page_state = ZFREE_COMMON;
 
346
  pageLastPtr.p->first_cluster_page = pageInsPtr.i;
 
347
  pageLastPtr.p->next_page = RNIL;
 
348
}//Dbtup::insertCommonArea()
 
349
 
 
350
void Dbtup::removeCommonArea(Uint32 remPageRef, Uint32 list) 
 
351
{
 
352
  cnoOfAllocatedPages += (1 << list);  
 
353
  PagePtr pagePrevPtr, pageNextPtr, pageLastPtr, remPagePtr;
 
354
 
 
355
  c_page_pool.getPtr(remPagePtr, remPageRef);
 
356
  ndbrequire(list < 16);
 
357
  if (cfreepageList[list] == remPagePtr.i) {
 
358
    jam();
 
359
    ndbassert(remPagePtr.p->prev_cluster_page == RNIL);
 
360
    cfreepageList[list] = remPagePtr.p->next_cluster_page;
 
361
    pageNextPtr.i = cfreepageList[list];
 
362
    if (pageNextPtr.i != RNIL) {
 
363
      jam();
 
364
      c_page_pool.getPtr(pageNextPtr);
 
365
      pageNextPtr.p->prev_cluster_page = RNIL;
 
366
    }//if
 
367
  } else {
 
368
    pagePrevPtr.i = remPagePtr.p->prev_cluster_page;
 
369
    pageNextPtr.i = remPagePtr.p->next_cluster_page;
 
370
    c_page_pool.getPtr(pagePrevPtr);
 
371
    pagePrevPtr.p->next_cluster_page = pageNextPtr.i;
 
372
    if (pageNextPtr.i != RNIL)
 
373
    {
 
374
      jam();
 
375
      c_page_pool.getPtr(pageNextPtr);
 
376
      pageNextPtr.p->prev_cluster_page = pagePrevPtr.i;
 
377
    }
 
378
  }//if
 
379
  remPagePtr.p->next_cluster_page= RNIL;
 
380
  remPagePtr.p->last_cluster_page= RNIL;
 
381
  remPagePtr.p->prev_cluster_page= RNIL;
 
382
  remPagePtr.p->page_state = ~ZFREE_COMMON;
 
383
 
 
384
  pageLastPtr.i = (remPagePtr.i + (1 << list)) - 1;
 
385
  c_page_pool.getPtr(pageLastPtr);
 
386
  pageLastPtr.p->first_cluster_page= RNIL;
 
387
  pageLastPtr.p->page_state = ~ZFREE_COMMON;
 
388
 
 
389
}//Dbtup::removeCommonArea()