1 /*
2 Copyright (c) 2003, 2021, Oracle and/or its affiliates.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is also distributed with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have included with MySQL.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25 #define DBTUP_C
26 #define DBTUP_PAG_MAN_CPP
27 #include "Dbtup.hpp"
28 #include <RefConvert.hpp>
29 #include <ndb_limits.h>
30 #include <pc.hpp>
31
32 #define JAM_FILE_ID 407
33
34
35 /* ---------------------------------------------------------------- */
36 // 4) Page Memory Manager (buddy algorithm)
37 //
38 // The following data structures in Dbtup is used by the Page Memory
39 // Manager.
40 //
41 // cfreepageList[16]
42 // Pages with a header
43 //
44 // The cfreepageList is 16 free lists. Free list 0 contains chunks of
45 // pages with 2^0 (=1) pages in each chunk. Free list 1 chunks of 2^1
46 // (=2) pages in each chunk and so forth upto free list 15 which
47 // contains chunks of 2^15 (=32768) pages in each chunk.
48 // The cfreepageList array contains the pointer to the first chunk
49 // in each of those lists. The lists are doubly linked where the
50 // first page in each chunk contains the next and previous references
51 // in position ZPAGE_NEXT_CLUST_POS and ZPAGE_PREV_CLUST_POS in the
52 // page header.
53 // In addition the leading page and the last page in each chunk is marked
54 // with a state (=ZFREE_COMMON) in position ZPAGE_STATE_POS in page
55 // header. This state indicates that the page is the leading or last page
56 // in a chunk of free pages. Furthermore the leading and last page is
57 // also marked with a reference to the leading (=ZPAGE_FIRST_CLUST_POS)
58 // and the last page (=ZPAGE_LAST_CLUST_POS) in the chunk.
59 //
60 // The aim of these data structures is to enable a free area handling of
61 // free pages based on a buddy algorithm. When allocating pages it is
62 // performed in chunks of pages and the algorithm tries to make the
63 // chunks as large as possible.
64 // This manager is invoked when fragments lack internal page space to
65 // accomodate all the data they are requested to store. It is also
66 // invoked when fragments deallocate page space back to the free area.
67 //
68 // The following routines are part of the external interface:
69 // void
70 // allocConsPages(EmulatedJamBuffer *jamBuff #In/out
71 // Uint32 noOfPagesToAllocate, #In
72 // Uint32& noOfPagesAllocated, #Out
73 // Uint32& retPageRef) #Out
74 // void
75 // returnCommonArea(Uint32 retPageRef, #In
76 // Uint32 retNoPages) #In
77 //
78 // allocConsPages tries to allocate noOfPagesToAllocate pages in one chunk.
79 // If this fails it delivers a chunk as large as possible. It returns the
80 // i-value of the first page in the chunk delivered, if zero pages returned
81 // this i-value is undefined. It also returns the size of the chunk actually
82 // delivered.
83 //
84 // returnCommonArea is used when somebody is returning pages to the free area.
85 // It is used both from internal routines and external routines.
86 //
87 // The following routines are private routines used to support the
88 // above external interface:
89 // removeCommonArea()
90 // insertCommonArea()
91 // findFreeLeftNeighbours()
92 // findFreeRightNeighbours()
93 // Uint32
94 // nextHigherTwoLog(Uint32 input)
95 //
96 // nextHigherTwoLog is a support routine which is a mathematical function with
97 // an integer as input and an integer as output. It calculates the 2-log of
98 // (input + 1). If the 2-log of (input + 1) is larger than 15 then the routine
99 // will return 15. It is part of the external interface since it is also used
100 // by other similar memory management algorithms.
101 //
102 // External dependencies:
103 // None.
104 //
105 // Side Effects:
106 // Apart from the above mentioned data structures there are no more
107 // side effects other than through the subroutine parameters in the
108 // external interface.
109 //
110 /* ---------------------------------------------------------------- */
111
112 /* ---------------------------------------------------------------- */
113 /* CALCULATE THE 2-LOG + 1 OF TMP AND PUT RESULT INTO TBITS */
114 /* ---------------------------------------------------------------- */
nextHigherTwoLog(Uint32 input)115 Uint32 Dbtup::nextHigherTwoLog(Uint32 input)
116 {
117 input = input | (input >> 8);
118 input = input | (input >> 4);
119 input = input | (input >> 2);
120 input = input | (input >> 1);
121 Uint32 output = (input & 0x5555) + ((input >> 1) & 0x5555);
122 output = (output & 0x3333) + ((output >> 2) & 0x3333);
123 output = output + (output >> 4);
124 output = (output & 0xf) + ((output >> 8) & 0xf);
125 return output;
126 }//nextHigherTwoLog()
127
initializePage()128 void Dbtup::initializePage()
129 {
130 }//Dbtup::initializePage()
131
allocConsPages(EmulatedJamBuffer * jamBuf,Uint32 noOfPagesToAllocate,Uint32 & noOfPagesAllocated,Uint32 & allocPageRef)132 void Dbtup::allocConsPages(EmulatedJamBuffer* jamBuf,
133 Uint32 noOfPagesToAllocate,
134 Uint32& noOfPagesAllocated,
135 Uint32& allocPageRef)
136 {
137 if (noOfPagesToAllocate == 0){
138 thrjam(jamBuf);
139 noOfPagesAllocated = 0;
140 return;
141 }//if
142
143 Resource_limit rl;
144 m_ctx.m_mm.get_resource_limit_nolock(RG_DATAMEM, rl);
145 if (rl.m_curr + m_minFreePages + noOfPagesToAllocate > rl.m_max)
146 {
147 thrjam(jamBuf);
148 noOfPagesAllocated = 0;
149 return;
150 }
151
152 m_ctx.m_mm.alloc_pages(RT_DBTUP_PAGE, &allocPageRef,
153 &noOfPagesToAllocate, 1);
154 noOfPagesAllocated = noOfPagesToAllocate;
155
156 // Count number of allocated pages
157 m_pages_allocated += noOfPagesAllocated;
158 if (m_pages_allocated > m_pages_allocated_max)
159 m_pages_allocated_max = m_pages_allocated;
160
161 return;
162 }//allocConsPages()
163
returnCommonArea(Uint32 retPageRef,Uint32 retNo)164 void Dbtup::returnCommonArea(Uint32 retPageRef, Uint32 retNo)
165 {
166 m_ctx.m_mm.release_pages(RT_DBTUP_PAGE, retPageRef, retNo);
167
168 // Count number of allocated pages
169 m_pages_allocated -= retNo;
170
171 }//Dbtup::returnCommonArea()
172
173