The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/storage/ndb/src/kernel/blocks/dbtup/tuppage.cpp Source File
mysql/src/5.1-dbg/storage/ndb/src/kernel/blocks/dbtup/tuppage.cpp

00001 /* Copyright (C) 2003 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; either version 2 of the License, or
00006    (at your option) any later version.
00007 
00008    This program is distributed in the hope that it will be useful,
00009    but WITHOUT ANY WARRANTY; without even the implied warranty of
00010    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011    GNU General Public License for more details.
00012 
00013    You should have received a copy of the GNU General Public License
00014    along with this program; if not, write to the Free Software
00015    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
00016 
00017 #include <ndb_global.h>
00018 #include "tuppage.hpp"
00019 #include "Dbtup.hpp"
00020 
00035 Uint32
00036 Tup_fixsize_page::alloc_record()
00037 {
00038   assert(free_space);
00039   Uint32 page_idx = next_free_index;
00040   assert(page_idx + 1 < DATA_WORDS);
00041 
00042   Uint32 prev = m_data[page_idx] >> 16;
00043   Uint32 next = m_data[page_idx] & 0xFFFF;
00044 
00045   assert(prev == 0xFFFF);
00046   assert(m_data[page_idx + 1] == FREE_RECORD);
00047   
00048   m_data[page_idx + 1] = 0;
00049   if (next != 0xFFFF)
00050   {
00051     assert(free_space > 1);
00052     Uint32 nextP = m_data[next];
00053     assert((nextP >> 16) == page_idx);
00054     m_data[next] = 0xFFFF0000 | (nextP & 0xFFFF);
00055   }
00056   else
00057   {
00058     assert(free_space == 1);
00059   }
00060   
00061   next_free_index = next;
00062   free_space--;
00063   return page_idx;
00064 }
00065 
00066 Uint32
00067 Tup_fixsize_page::alloc_record(Uint32 page_idx)
00068 {
00069   assert(page_idx + 1 < DATA_WORDS);
00070   if (likely(free_space && m_data[page_idx + 1] == FREE_RECORD))
00071   {
00072     Uint32 prev = m_data[page_idx] >> 16;
00073     Uint32 next = m_data[page_idx] & 0xFFFF;
00074     
00075     assert(prev != 0xFFFF || (next_free_index == page_idx));
00076     if (prev == 0xFFFF)
00077     {
00078       next_free_index = next;
00079     }
00080     else
00081     {
00082       Uint32 prevP = m_data[prev];
00083       m_data[prev] = (prevP & 0xFFFF0000) | next;
00084     }
00085 
00086     if (next != 0xFFFF)
00087     {
00088       Uint32 nextP = m_data[next];
00089       m_data[next] = (prev << 16) | (nextP & 0xFFFF);
00090     }
00091     free_space --;
00092     m_data[page_idx + 1] = 0;
00093     return page_idx;
00094   }
00095   return ~0;
00096 }
00097 
00098 Uint32
00099 Tup_fixsize_page::free_record(Uint32 page_idx)
00100 {
00101   Uint32 next = next_free_index;
00102   
00103   assert(page_idx + 1 < DATA_WORDS);
00104   assert(m_data[page_idx + 1] != FREE_RECORD);
00105 
00106   if (next == 0xFFFF)
00107   {
00108     assert(free_space == 0);
00109   }
00110   else
00111   {
00112     assert(free_space);
00113     assert(next + 1 < DATA_WORDS);
00114     Uint32 nextP = m_data[next];
00115     assert((nextP >> 16) == 0xFFFF);
00116     m_data[next] = (page_idx << 16) | (nextP & 0xFFFF);
00117     assert(m_data[next + 1] == FREE_RECORD);
00118   }
00119 
00120   next_free_index = page_idx;
00121   m_data[page_idx] = 0xFFFF0000 | next;
00122   m_data[page_idx + 1] = FREE_RECORD;
00123   
00124   return ++free_space;
00125 }
00126 
00127 void
00128 Tup_varsize_page::init()
00129 {
00130   free_space= DATA_WORDS - 1;
00131   high_index= 1;
00132   insert_pos= 0;
00133   next_free_index= END_OF_FREE_LIST;
00134   m_page_header.m_page_type = File_formats::PT_Tup_varsize_page;
00135 }
00136 
00137 Uint32
00138 Tup_varsize_page::alloc_record(Uint32 page_idx, Uint32 alloc_size, 
00139                                Tup_varsize_page* temp)
00140 {
00141   assert(page_idx); // 0 is not allowed
00142   Uint32 free = free_space;
00143   Uint32 largest_size= DATA_WORDS - (insert_pos + high_index);
00144   Uint32 free_list = next_free_index;
00145   
00146   if (page_idx < high_index)
00147   {
00148     Uint32 *ptr = get_index_ptr(page_idx);
00149     Uint32 word = *ptr;
00150     
00151     if (unlikely((free < alloc_size) || ! (word & FREE)))
00152     {
00153       return ~0;
00154     }
00155     
00156     if (alloc_size >= largest_size)
00157     {
00158       /*
00159         We can't fit this segment between the insert position and the end of
00160         the index entries. We will pack the page so that all free space
00161         exists between the insert position and the end of the index entries.
00162       */
00163       reorg(temp);
00164     }
00165 
00166     Uint32 next = (word & NEXT_MASK) >> NEXT_SHIFT;
00167     Uint32 prev = (word & PREV_MASK) >> PREV_SHIFT;
00168     
00169     if (next != END_OF_FREE_LIST)
00170     {
00171       Uint32 * next_ptr = get_index_ptr(next);
00172       Uint32 next_word = * next_ptr;
00173       * next_ptr = (next_word & ~PREV_MASK) | (prev << PREV_SHIFT);
00174     }
00175 
00176     if (prev != END_OF_FREE_LIST)
00177     {
00178       Uint32 * prev_ptr = get_index_ptr(prev);
00179       Uint32 prev_word = * prev_ptr;
00180       * prev_ptr = (prev_word & ~NEXT_MASK) | (next << NEXT_SHIFT);
00181     }
00182     else
00183     {
00184       assert(next_free_index == page_idx);
00185       next_free_index = next;
00186     }
00187     
00188     * ptr = insert_pos + (alloc_size << LEN_SHIFT);
00189     free -= alloc_size;
00190   }
00191   else
00192   {
00196     Uint32 hi = high_index;
00197     Uint32 expand = (page_idx + 1 - hi);
00198     Uint32 size = alloc_size + expand;
00199     if (unlikely(size > free))
00200     {
00201       return ~0;
00202     } 
00203 
00204     if (size >= largest_size)
00205     {
00206       /*
00207         We can't fit this segment between the insert position and the end of
00208         the index entries. We will pack the page so that all free space
00209         exists between the insert position and the end of the index entries.
00210       */
00211       reorg(temp);
00212     }
00213 
00214     Uint32 *ptr = m_data + DATA_WORDS - hi;
00215     if (page_idx == hi)
00216     {
00217       * ptr = insert_pos + (alloc_size << LEN_SHIFT);
00218     }
00219     else
00220     {
00221       if (free_list != END_OF_FREE_LIST)
00222       {
00223         Uint32 * prev_ptr = get_index_ptr(free_list);
00224         Uint32 prev_word = * prev_ptr;
00225         * prev_ptr = (prev_word & ~PREV_MASK) | (hi << PREV_SHIFT);
00226       }
00227 
00228       for (; hi < page_idx;)
00229       {
00230         * ptr-- = FREE | (free_list << NEXT_SHIFT) | ((hi+1) << PREV_SHIFT);
00231         free_list = hi++;
00232       }
00233       
00234       * ptr++ = insert_pos + (alloc_size << LEN_SHIFT);
00235       * ptr = ((* ptr) & ~PREV_MASK) | (END_OF_FREE_LIST << PREV_SHIFT);
00236       
00237       next_free_index = hi - 1;
00238     }
00239     high_index = hi + 1;
00240     free -= size;
00241   }
00242   
00243   free_space = free;
00244   insert_pos += alloc_size;
00245   
00246   return page_idx;
00247 }
00248 
00249 Uint32
00250 Tup_varsize_page::alloc_record(Uint32 alloc_size, 
00251                                Tup_varsize_page* temp, Uint32 chain)
00252 {
00253   assert(free_space >= alloc_size);
00254   Uint32 largest_size= DATA_WORDS - (insert_pos + high_index);
00255   if (alloc_size >= largest_size) {
00256     /*
00257       We can't fit this segment between the insert position and the end of
00258       the index entries. We will pack the page so that all free space
00259       exists between the insert position and the end of the index entries.
00260     */
00261     reorg(temp);
00262     largest_size= DATA_WORDS - (insert_pos + high_index);
00263   }
00264   assert(largest_size > alloc_size);
00265 
00266   Uint32 page_idx;
00267   if (next_free_index == END_OF_FREE_LIST) {
00268     /*
00269       We are out of free index slots. We will extend the array of free
00270       slots
00271     */
00272     page_idx= high_index++;
00273     free_space--;
00274   } else {
00275     // Pick an empty slot among the index entries
00276     page_idx= next_free_index;
00277     assert((get_index_word(page_idx) & FREE) == FREE);
00278     assert(((get_index_word(page_idx) & PREV_MASK) >> PREV_SHIFT) == 
00279            END_OF_FREE_LIST);
00280     next_free_index= (get_index_word(page_idx) & NEXT_MASK) >> NEXT_SHIFT;
00281     assert(next_free_index);
00282     if (next_free_index != END_OF_FREE_LIST)
00283     {
00284       Uint32 *ptr = get_index_ptr(next_free_index);
00285       Uint32 word = *ptr;
00286       * ptr = (word & ~PREV_MASK) | (END_OF_FREE_LIST << PREV_SHIFT);
00287     }
00288   }
00289 
00290   assert(chain == 0 || chain == CHAIN);
00291   * get_index_ptr(page_idx) = insert_pos + chain + (alloc_size << LEN_SHIFT);
00292   
00293   insert_pos += alloc_size;
00294   free_space -= alloc_size;
00295   //ndbout_c("%p->alloc_record(%d%s) -> %d", this,alloc_size, (chain ? " CHAIN" : ""),page_idx);
00296   return page_idx;
00297 }
00298   
00299 Uint32
00300 Tup_varsize_page::free_record(Uint32 page_idx, Uint32 chain)
00301 {
00302   //ndbout_c("%p->free_record(%d%s)", this, page_idx, (chain ? " CHAIN": ""));
00303   Uint32 *index_ptr= get_index_ptr(page_idx);
00304   Uint32 index_word= * index_ptr;
00305   Uint32 entry_pos= (index_word & POS_MASK) >> POS_SHIFT;
00306   Uint32 entry_len= (index_word & LEN_MASK) >> LEN_SHIFT;
00307   assert(chain == 0 || chain == CHAIN);
00308   assert((index_word & CHAIN) == chain);
00309 #ifdef VM_TRACE
00310   memset(m_data + entry_pos, 0xF2, 4*entry_len);
00311 #endif
00312   if (page_idx + 1 == high_index) {
00313     /*
00314       We are removing the last in the entry list. We could potentially
00315       have several free entries also before this. To take that into account
00316       we will rebuild the free list and thus compress it and update the
00317       free space accordingly.
00318     */
00319     rebuild_index(index_ptr);
00320   } else {
00321     if (next_free_index != END_OF_FREE_LIST)
00322     {
00323       Uint32 *ptr = get_index_ptr(next_free_index);
00324       Uint32 word = *ptr;
00325       assert(((word & PREV_MASK) >> PREV_SHIFT) == END_OF_FREE_LIST);
00326       * ptr = (word & ~PREV_MASK) | (page_idx << PREV_SHIFT);
00327     }
00328     * index_ptr= FREE | next_free_index | (END_OF_FREE_LIST << PREV_SHIFT);
00329     next_free_index= page_idx;
00330     assert(next_free_index);
00331   }
00332   
00333   free_space+= entry_len;
00334   // If we're the "last" entry, decrease insert_pos
00335   insert_pos -= (entry_pos + entry_len == insert_pos ? entry_len : 0);
00336   
00337   return free_space;
00338 }
00339 
00340 void
00341 Tup_varsize_page::rebuild_index(Uint32* index_ptr)
00342 {
00343   Uint32 empty= 1;
00344   Uint32 *end= m_data + DATA_WORDS;
00345 
00349   for(index_ptr++; index_ptr < end; index_ptr++)
00350     if((* index_ptr) & FREE)
00351       empty++;
00352     else
00353       break;
00354   
00355   if(index_ptr == end)
00356   {
00357     // Totally free page
00358     high_index = 1;
00359     free_space += empty;
00360     next_free_index = END_OF_FREE_LIST;
00361     return;
00362   }
00363   
00364   Uint32 next= END_OF_FREE_LIST;
00365   Uint32 dummy;
00366   Uint32 *prev_ptr = &dummy;
00367   for(index_ptr++; index_ptr < end; index_ptr++)
00368   {
00369     if ((* index_ptr) & FREE)
00370     {
00371       * index_ptr= FREE | next;
00372       next= (end - index_ptr);
00373       * prev_ptr |= (next << PREV_SHIFT);
00374       prev_ptr = index_ptr;
00375     }
00376   }
00377   
00378   * prev_ptr |= (END_OF_FREE_LIST << PREV_SHIFT);
00379   
00380   high_index -= empty;
00381   free_space += empty;
00382   next_free_index= next;
00383   assert(next_free_index);
00384 }
00385 
00386 void
00387 Tup_varsize_page::reorg(Tup_varsize_page* copy_page)
00388 {
00389   Uint32 new_insert_pos= 0;
00390   Uint32 old_insert_pos= insert_pos;
00391 
00392   // Copy key data part of page to a temporary page.
00393   memcpy(copy_page->m_data, m_data, 4*old_insert_pos);
00394   assert(high_index > 0);
00395   Uint32* index_ptr= get_index_ptr(high_index-1);
00396   Uint32 *end_of_page= m_data + DATA_WORDS;
00397   for (; index_ptr < end_of_page; index_ptr++)
00398   {
00399     Uint32 index_word= * index_ptr;
00400     Uint32 entry_len= (index_word & LEN_MASK) >> LEN_SHIFT;
00401     if (!(index_word & FREE) && entry_len) 
00402     {
00403       /*
00404         We found an index item that needs to be packed. 
00405         We will update the index entry and copy the data to the page.
00406       */
00407       Uint32 entry_pos= (index_word & POS_MASK) >> POS_SHIFT;
00408       assert(entry_pos + entry_len <= old_insert_pos);
00409       assert(new_insert_pos + entry_len <= old_insert_pos);
00410       * index_ptr= (new_insert_pos << POS_SHIFT) + (index_word & ~POS_MASK);
00411       memcpy(m_data+new_insert_pos, copy_page->m_data+entry_pos, 4*entry_len);
00412       
00413       new_insert_pos += entry_len;
00414     }
00415   }
00416   insert_pos= new_insert_pos;
00417 }
00418 
00419 NdbOut&
00420 operator<< (NdbOut& out, const Tup_varsize_page& page)
00421 {
00422   out << "[ Varpage " << &page << ": free: " << page.free_space
00423       << " (" << (page.DATA_WORDS - (page.insert_pos + page.high_index + 1)) << ")"
00424       << " insert_pos: " << page.insert_pos 
00425       << " high_index: " << page.high_index
00426       << " index: " << flush;
00427   
00428   const Uint32 *index_ptr= page.m_data+page.DATA_WORDS-1;
00429   for(Uint32 i = 1; i<page.high_index; i++, index_ptr--)
00430   {
00431     out << " [ " << i;
00432     if(! (*index_ptr & page.FREE))
00433       out << " pos: " << ((* index_ptr & page.POS_MASK) >> page.POS_SHIFT)
00434           << " len: " << ((* index_ptr & page.LEN_MASK) >> page.LEN_SHIFT)
00435           << ((* index_ptr & page.CHAIN) ? " CHAIN " : " ") 
00436           << "]" << flush;
00437     else
00438       out << " FREE ]" << flush;
00439   }
00440   
00441   out << " free list: " << flush;
00442   Uint32 next= page.next_free_index;
00443   while(next != page.END_OF_FREE_LIST)
00444   {
00445     out << next << " " << flush;
00446     next= ((* (page.m_data+page.DATA_WORDS-next)) & page.NEXT_MASK) >> page.NEXT_SHIFT;
00447   }
00448   out << "]";
00449   return out;
00450 }
00451 
00452 NdbOut&
00453 operator<< (NdbOut& out, const Tup_fixsize_page& page)
00454 {
00455   out << "[ Fixpage " << &page 
00456       << ": frag_page: " << page.frag_page_id 
00457       << " page_no: " << page.m_page_no 
00458       << " file_no: " << page.m_file_no
00459       << " table: " << page.m_table_id
00460       << " fragment: " << page.m_fragment_id 
00461       << " uncommitted_used_space: " << page.uncommitted_used_space 
00462       << " free: " << page.free_space;
00463   
00464   out << " free list: " << hex << page.next_free_index << " " << flush;
00465   Uint32 startTuple = page.next_free_index >> 16;
00466   
00467 #if 0
00468   Uint32 cnt = 0;
00469   Uint32 next= startTuple;
00470   while((next & 0xFFFF) != 0xFFFF)
00471   {
00472     cnt++;
00473     out << dec << "(" << (next & 0xFFFF) << " " << hex << next << ") " << flush;
00474     assert(page.m_data[(next & 0xFFFF) + 1] == Dbtup::Tuple_header::FREE);
00475     next= * (page.m_data + ( next & 0xFFFF ));
00476   }
00477   assert(cnt == page.free_space);
00478 #endif
00479   out << "]";
00480   return out;
00481 }
Generated on Sat Sep 9 00:50:49 2006 for MySQL 5.1 by
1.4.7