AllocExtent


1   /*
2   
3      Derby - Class org.apache.derby.impl.store.raw.data.AllocExtent
4   
5      Licensed to the Apache Software Foundation (ASF) under one or more
6      contributor license agreements.  See the NOTICE file distributed with
7      this work for additional information regarding copyright ownership.
8      The ASF licenses this file to you under the Apache License, Version 2.0
9      (the "License"); you may not use this file except in compliance with
10     the License.  You may obtain a copy of the License at
11  
12        http://www.apache.org/licenses/LICENSE-2.0
13  
14     Unless required by applicable law or agreed to in writing, software
15     distributed under the License is distributed on an "AS IS" BASIS,
16     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17     See the License for the specific language governing permissions and
18     limitations under the License.
19  
20   */
21  
22  package org.apache.derby.impl.store.raw.data;
23  
24  import org.apache.derby.iapi.services.sanity.SanityManager;
25  import org.apache.derby.iapi.error.StandardException;
26  import org.apache.derby.iapi.store.raw.ContainerHandle;
27  import org.apache.derby.iapi.store.raw.xact.RawTransaction; 
28  
29  import org.apache.derby.iapi.services.io.FormatableBitSet;
30  
31  import java.io.Externalizable  ;
32  import java.io.IOException  ;
33  
34  import java.io.ObjectOutput  ;
35  import java.io.ObjectInput  ;
36  
37  /**
38  
39      An allocation extent row manages the page status of page in the extent.
40      AllocExtent is externalizable and is written to the AllocPage directly,
41      without being converted to a row first.
42      <P>
43      <PRE>
44      @format_id  none, format implied by AllocPage's format
45      @purpose    manage page status of page in extent
46      @upgrade
47      @disk_layout
48          extentOffset(long) the begin physical byte offset of the first page of this extent
49          extentStart(long) the first logical page mananged by this extent.
50          extentEnd(long) the last page this extent can ever hope to manage 
51          extentLength(int) the number of pages allocated in this extent
52          extentStatus(int) status bits for the whole extent.
53                  HAS_DEALLOCATED - most likely, this extent has a deallocated 
54                          page somewhere
55                          If !HAD_DEALLOCATED, the extent has no deallocated page
56                  HAS_FREE - most likely, this extent has a free page somewhere
57                          If !HAS_FREE, there is no free page in the extent
58                  ALL_FREE - most likely, this extent only has free pages, good 
59                          candidate for shrinking the file.
60                          If !ALL_FREE, the extent is not all free
61                  HAS_UNFILLED_PAGES - most likely, this extent has unfilled pages.
62                          if !HAS_UNFILLED_PAGES, all pages are filled
63                  KEEP_UNFILLED_PAGES - this extent keeps track of unfilled pages
64                          (post v1.3).  If not set, this extent has no notion of
65                          unfilled page and has no unFilledPage bitmap.
66                  NO_DEALLOC_PAGE_MAP - this extents do not have a dealloc and a
67                          free page bit maps.  Prior to 2.0, there are 2 bit
68                          maps, a deallocate page bit map and a free page bit
69                          map.  Cloudscape 2.0 and later merged the dealloc page
70                          bit map into the free page bit map.
71                  RETIRED - this extent contains only 'retired' pages, never use 
72                          any page from this extent.  The pages don't actually 
73                          exist, i.e., it maps to nothing (physicalOffset is 
74                          garbage).  The purpose of this extent is to blot out a 
75                          range of logical page numbers that no longer exists 
76                          for this container.  Use this to reuse a physical page
77                          when a logical page has exhausted all recordId or for
78                          logical pages that has been shrunk out.
79          preAllocLength(int)  the number of pages that have been preallocated
80          reserved1(int)
81          reserved2(long) reserved for future use
82          reserved3(long) reserved for future use
83          FreePages(bit)  bitmap of free pages
84                  Bit[i] is ON iff page i is free for immediate (re)use.
85          [
86              on disk version before 2.0
87                  deAllocPages(bit) bitmap of deallocated pages
88                  Bit[i] is ON iff page i has been deallocated.
89          ]
90          unFilledPages(bit)  bitmap of pages that has free space
91                  Bit[i] is ON if page i is likely to be < 1/2 full
92  
93          org.apache.derby.iapi.services.io.FormatableBitSet is used to store the bit map.  
94              FormatableBitSet is an externalizable class.
95  
96      @end_format
97  
98      <PRE>
99      A page can have the following logical state:
100     <BR>Free - a page that is free to be used
101     <BR>Valid - a page that is currently in use
102     <P>
103     There is another type of transitional pages which pages that have been
104     allocated on disk but has not yet been used.  These pages are Free.
105     <P>
106     Bit[K] freePages
107         Bit[i] is ON iff page i maybe free for reuse.  User must get the
108         dealloc page lock on the free page to make sure the transaction.
109     <P>
110     K is the size of the bit array, it must be >= length.
111 
112     @see AllocPage
113 */
114 
115 
116 public class AllocExtent implements Externalizable  
117 {
118     private long extentOffset;  // begin physical offset
119     private long extentStart;   // first logical page number
120     private long extentEnd;     // last logical page number
121     // page[extentStart] to page[extentEnd] are the pages in the range of this
122     // alloc extent.
123     // page[exentStart] to page[extentStart+extentLength-1] are actually
124     // allocated in this extent
125     // when the extent is completely allocated,
126     // extentEnd == extentStart+extentLength -1
127 
128     private int extentLength;   // number of pages allocated in the extent
129 
130     int extentStatus;
131 
132     private int preAllocLength;
133 
134     private int reserved1;
135     private long reserved2;
136     private long reserved3;
137 
138     // extent Status bits
139     private static final int HAS_DEALLOCATED = 0x1;
140     private static final int HAS_FREE = 0x2;
141     private static final int ALL_FREE = 0x4;
142     private static final int HAS_UNFILLED_PAGES = 0x10;
143     private static final int KEEP_UNFILLED_PAGES = 0x10000000;
144     private static final int NO_DEALLOC_PAGE_MAP = 0x20000000;
145     private static final int RETIRED = 0x8;
146 
147     /**
148         public Per Page status
149     */
150     protected static final int ALLOCATED_PAGE = 0;
151     protected static final int DEALLOCATED_PAGE = 1;
152     protected static final int FREE_PAGE = 2;
153 
154 
155     // a page which is not a freePage is a regular old
156     // allocated page.  Only an allocated page can be unFilled.
157     FormatableBitSet freePages;
158     FormatableBitSet unFilledPages;
159 
160     /**
161         Statically calculates how many pages this extent can manage given the
162         availspace number of bytes to store this extent in
163 
164         if read/writeExternal changes, this must change too
165     */
166     protected static int MAX_RANGE(int availspace)
167     {
168         /* extent Offset, Start, End, Length, Status, preAllocLength, reserved1,2,3 */
169         int bookkeeping =   8 /* offset */ +
170                             8 /* start */ +
171                             8 /* end */ +
172                             4 /* length */ +
173                             4 /* status */ +
174                             4 /* preAllocLength */ +
175                             4 /* reserved1 */ +
176                             8 /* reserved2 */ +
177                             8 /* reserved3 */;
178         availspace -= bookkeeping;
179 
180         // each bit array is allowed to the 1/3 the remaining space
181         availspace /= 3;
182 
183         if (availspace <= 0)
184             return 0;
185 
186         // ask bit array how many bits it can store in this amount of space
187         return FormatableBitSet.maxBitsForSpace(availspace);
188     }
189 
190     /*
191      * methods
192      */
193 
194     /*
195      * ctors
196      */
197     protected AllocExtent(long offset, // physical offset
198                        long start,  // starting logical page number
199                        int length,  // how many pages are in this extent
200                        int pagesize, // size of all the pages in the extent
201                        int maxlength) // initial size of the bit map arrays
202     {
203         if (SanityManager.DEBUG)
204         {
205             if (length > maxlength)
206                 SanityManager.THROWASSERT(
207                             "length " + length + " > maxlength " + maxlength);
208         }
209 
210 
211         this.extentOffset = offset;
212         this.extentStart = start;
213         this.extentEnd = start+maxlength-1;
214 
215         this.extentLength = length;
216         preAllocLength = extentLength;
217 
218         if (length > 0)
219             extentStatus = HAS_FREE | ALL_FREE ;
220         else
221             extentStatus = 0;
222 
223         extentStatus |= KEEP_UNFILLED_PAGES; // v1.3 or beyond
224         extentStatus |= NO_DEALLOC_PAGE_MAP; // v2.0 or beyond
225 
226         int numbits = (1+(length/8))*8;
227         if (numbits > maxlength)
228             numbits = maxlength;
229 
230         freePages = new FormatableBitSet(numbits);
231         unFilledPages = new FormatableBitSet(numbits);
232 
233         // by definition, all pages are free to begin with, no pages are
234         // deallocated and no page is unfilled
235         for (int i = 0; i < length; i++)
236             freePages.set(i);
237     }
238 
239     /*
240       Copy constructor
241     */
242     protected AllocExtent(AllocExtent original)
243     {
244         extentOffset = original.extentOffset;
245         extentStart  = original.extentStart;
246         extentEnd    = original.extentEnd;
247         extentLength = original.extentLength;
248         extentStatus = original.extentStatus;
249         preAllocLength = original.preAllocLength;
250 
251         freePages = new FormatableBitSet(original.freePages);
252         unFilledPages = new FormatableBitSet(original.unFilledPages);
253     }
254 
255 
256     /*
257      * Methods of Externalizable
258      */
259     public AllocExtent()
260     {
261     }
262 
263 
264     public void writeExternal(ObjectOutput   out) throws IOException  
265     {
266 
267         // any change to this routine must change maxRange
268         out.writeLong(extentOffset);
269         out.writeLong(extentStart);
270         out.writeLong(extentEnd);
271         out.writeInt(extentLength);
272         out.writeInt(extentStatus);
273         out.writeInt(preAllocLength);
274         out.writeInt(0);        // reserved1
275         out.writeLong(0);       // reserved2
276         out.writeLong(0);       // reserved3
277 
278         freePages.writeExternal(out);
279         unFilledPages.writeExternal(out);
280     }
281 
282     public void readExternal(ObjectInput   in)
283          throws IOException  , ClassNotFoundException  
284     {
285         // any change to this routine must change maxRange
286         extentOffset = in.readLong();
287         extentStart = in.readLong();
288         extentEnd   = in.readLong();
289         extentLength = in.readInt();
290         extentStatus = in.readInt();
291         preAllocLength = in.readInt();
292         reserved1 = in.readInt();
293         reserved2 = in.readLong();
294         reserved3 = in.readLong();
295 
296         freePages = new FormatableBitSet(); // don't know how to point to it
297         freePages.readExternal(in);
298 
299         // this extent is created before 2.0
300         if ((extentStatus & NO_DEALLOC_PAGE_MAP) == 0)  
301         {
302             FormatableBitSet deAllocPages = new FormatableBitSet();
303             deAllocPages.readExternal(in);
304             // fold this into free page bit map
305             freePages.or(deAllocPages);
306             extentStatus |= NO_DEALLOC_PAGE_MAP; // dealloc page map has been merged
307         }
308 
309         if ((extentStatus & KEEP_UNFILLED_PAGES) == KEEP_UNFILLED_PAGES)
310         {
311             unFilledPages = new FormatableBitSet();
312             unFilledPages.readExternal(in);
313         }
314         else                    // before we keep track of unfilled pages pre 1.3
315         {
316             // make sure there are enough space
317             unFilledPages = new FormatableBitSet(freePages.getLength());
318             extentStatus |= KEEP_UNFILLED_PAGES; // now we keep track of them
319         }
320         
321     }
322 
323 
324     /*
325      * methods specific to allocExtent
326      */
327 
328 
329     /*
330      * write operation that is called underneath the log
331      *
332      * page goes thru the following transition:
333      * ALLOCATED_PAGE <-> deallocated page -> free page <-> ALLOCATED_PAGE
334      *
335      */
336 
337     /**
338         Allocate this page - this is called underneath the log record
339 
340         @exception StandardException Standard Cloudscape error policy
341     */
342     protected void allocPage(long pagenum) throws StandardException
343     {
344         if (SanityManager.DEBUG)
345         {
346             if (pagenum > getLastPagenum())
347             {
348                 // adding a brand new page, it should be at most one off from the last page
349                 if (pagenum > extentEnd)
350                     SanityManager.THROWASSERT("pagenum " + pagenum +
351                                      " is out of beyond my range (" +
352                                         extentStart + "," + extentEnd + ")");
353                 if (pagenum != getLastPagenum() + 1)
354                     SanityManager.THROWASSERT(
355                         "skipping pages, lastPageNumber = " + getLastPagenum() +
356                          " pageNumber = " + pagenum + "\n");
357             }
358             else
359             {
360                 // reuseing a page, make sure it is in range and is not already in use
361                 checkInRange(pagenum);
362 
363                 int bitnum = (int)(pagenum-extentStart);
364 
365                 // either the pagenum is now free (do) or deallocated (undo)
366                 if (!freePages.isSet(bitnum))
367                 {
368                     SanityManager.THROWASSERT(
369                         "trying to re-allocate a page ( " +
370                         pagenum + " ) that is already allocated ");
371                 }
372             }
373         }
374 
375         // don't know if we are redoing (from free -> valid)
376         // or undoing (from dealloc -> valid), reset them both
377         int bitnum = (int)(pagenum-extentStart);
378 
379         if (bitnum >= freePages.getLength())    // expand the bit map
380         {
381             int numbits = (1+(bitnum/8))*8;
382             if (numbits > (int)(extentEnd - extentStart + 1))
383                 numbits = (int)(extentEnd - extentStart + 1);
384 
385             freePages.grow(numbits);
386             unFilledPages.grow(numbits);
387         }
388 
389         // the first page to be allocated has pagenum == extentStart.
390         int numPageAlloced = (int)(pagenum-extentStart+1);
391 
392         if (numPageAlloced > extentLength)
393         {
394             extentLength = numPageAlloced;
395         }
396 
397         freePages.clear(bitnum);
398 
399         // do not set the unfilled bit on a newly allocated page because
400         // we only keep track of unfilled HEAD page, not unfilled overflow
401         // page. 
402     }
403 
404     /**
405         Deallocate logical page pagenum - this is called underneath the log record.
406         pagenum must be a page managed by this extent and it must be valid
407 
408         @exception StandardException Standard Cloudscape error policy
409     */
410     protected void deallocPage(long pagenum) throws StandardException
411     {
412         int bitnum = (int)(pagenum-extentStart);
413 
414         // the pagenum must now be either valid (do) or free (undo)
415         if (SanityManager.DEBUG)
416         {
417             if (freePages.isSet(bitnum))
418                 SanityManager.THROWASSERT(
419                         "trying to deallocate a deallocated page " + pagenum);
420         }
421 
422         freePages.set(bitnum);
423         unFilledPages.clear(bitnum); // deallocated page is never unfilled
424 
425         setExtentFreePageStatus(true);
426     }
427 
428     /**
429      * Compress free pages at end of this extent.
430      * <p>
431      * Search backward from end of extent and prepare data structures
432      * to return pages at end of extent to the OS. Returns the lowest
433      * page that can be returned to the OS.
434      * <p>
435      *
436      * @return Return bit of page where all pages that follow can
437      *         be returned to the OS.
438      **/
439     protected int compress(
440     BaseContainerHandle owner,
441     RawTransaction      ntt,
442     AllocPage           alloc_page)
443         throws StandardException
444     {
445         int compress_bitnum      = -1;
446         int num_pages_compressed = 0;
447 
448         for (int i = (extentLength - 1); i >= 0; i--)
449         {
450             if (freePages.isSet(i))
451             {
452                 compress_bitnum = i;
453                 num_pages_compressed++;
454             }
455             else
456             {
457                 break;
458             }
459         }
460 
461         // new_highest_page is the last page to remain in the file after 
462         // the truncate, the above loop set compress_bitnum to lowest 
463         // free page in the set of contiguous free pages at end of extent.
464         int new_highest_page = compress_bitnum - 1;
465 
466         if (num_pages_compressed > 0)
467         {
468             if (SanityManager.DEBUG)
469             {
470                 for (int i = new_highest_page + 1; i < extentLength; i++)
471                 {
472                     if (!freePages.isSet(i))
473                     {
474 
475                         SanityManager.THROWASSERT(
476                             "compressPages with nonfree pg to truncate," +
477                             "new_highest_page = " + new_highest_page +
478                             "num_pages_truncated = " + num_pages_compressed +
479                             ";extentLength = " + extentLength +
480                             ";extentStart = " + extentStart +
481                             ";freePages.isSet(" + i + ") = " + 
482                                 freePages.isSet(i) +
483                             "\nextent:\n" + toDebugString());
484                     }
485                 }
486 
487                 SanityManager.ASSERT(
488                     (new_highest_page + num_pages_compressed + 1) == 
489                         extentLength,
490                     "truncate page count did not match: " +
491                     ";new_highest_page = " + new_highest_page +
492                     ";num_pages_truncated = " + num_pages_compressed +
493                     ";extentLength = " + extentLength);
494 
495                 // the following assert could be made invalid by a new type of
496                 // access method, but currently page 1 of btree and heap contain
497                 // control rows, so will never become free and thus should never
498                 // be compressed.
499                 if (extentStart == 1)
500                 {
501                     SanityManager.ASSERT(new_highest_page >= 0);
502 
503                     if (num_pages_compressed >= extentLength)
504                     {
505                         SanityManager.THROWASSERT(
506                             "new_highest_page = "     + new_highest_page +
507                             "num_pages_compressed = " + num_pages_compressed +
508                             "; extentLength = "       + extentLength +
509                             "extent:\n"               + toDebugString());
510                     }
511                 }
512             }
513 
514             /*
515             SanityManager.DEBUG_PRINT("AllocExtent", 
516                 "calling actionCompressSpaceOperation:" +
517                 ";new_highest_page = " + new_highest_page +
518                 ";num_pages_compressed = " +  num_pages_compressed +
519                 ";extentLength = " +  extentLength +
520                 ";extent: \n" + toDebugString());
521             */
522 
523 
524             owner.getAllocationActionSet().actionCompressSpaceOperation(
525                 ntt, alloc_page, new_highest_page, num_pages_compressed); 
526             return(compress_bitnum);
527         }
528         else
529         {
530             return(-1);
531         }
532 
533     }
534 
535     protected void compressPages(
536     int        new_highest_page,
537     int        num_pages_truncated)
538     {
539         if (SanityManager.DEBUG)
540         {
541             if (new_highest_page >= 0)
542             {
543                 for (int i = new_highest_page + 1; i < extentLength; i++)
544                 {
545                     if (!freePages.isSet(i))
546                     {
547                         SanityManager.THROWASSERT(
548                             "compressPages with non free page to truncate," +
549                             "new_highest_page = " + new_highest_page +
550                             "num_pages_truncated = " + num_pages_truncated +
551                             ";extentLength = " + extentLength +
552                             ";extentStart = " + extentStart +
553                             ";freePages.isSet(" + i + ") = " + 
554                                 freePages.isSet(i) +
555                             "\nextent:\n" + toDebugString());
556                     }
557                 }
558             }
559 
560             SanityManager.ASSERT(
561                 (new_highest_page + num_pages_truncated + 1) == extentLength,
562                 "truncate page count did not match: " +
563                 ";new_highest_page = " + new_highest_page +
564                 ";num_pages_truncated = " + num_pages_truncated +
565                 ";extentLength = " + extentLength);
566 
567             // the following assert could be made invalid by a new type of
568             // access method, but currently page 1 of btree and heap contain
569             // control rows, so will never become free and thus should never
570             // be compressed.
571             if (extentStart == 1)
572             {
573                 SanityManager.ASSERT(new_highest_page >= 0);
574                 SanityManager.ASSERT(num_pages_truncated < extentLength);
575             }
576         }
577 
578         if (new_highest_page >= 0)
579         {
580             freePages.shrink(new_highest_page + 1);
581             unFilledPages.shrink(new_highest_page + 1);
582 
583             // This routine assumes the caller
584             // will be doing the truncate, and just updates the data structures.
585             preAllocLength = extentLength = (new_highest_page + 1);
586         }
587 
588         return;
589     }
590 
591     /**
592      * Undo the compress space operation.
593      * <p>
594      * Undo of this operation doesn't really "undo" the operation, it just
595      * makes sure the data structures are ok after the undo.  We are 
596      * guaranteed at the point of the transaction doing the 
597      * Undo of the compress space operation fixes up the bit maps to
598      * only point at pages within the new_highest_page range.
599      * <p>
600      * Prior to logging the compress space operation all pages greater 
601      * than 
602      * There are only 2 possibilities at this point:
603      * 1) the truncate of pages greater than new_highest_page happened before
604      *    the abort took place.  W
605      * 2) 
606      *
607      * @exception  StandardException  Standard exception policy.
608      **/
609     protected void undoCompressPages(
610     int        new_highest_page,
611     int        num_pages_truncated)
612     {
613         if (new_highest_page >= 0)
614         {
615             freePages.shrink(new_highest_page + 1);
616             unFilledPages.shrink(new_highest_page + 1);
617             preAllocLength = extentLength = (new_highest_page + 1);
618         }
619 
620         return;
621     }
622 
623     protected long getExtentEnd()
624     {
625         return extentEnd;
626     }
627 
628 
629     /*
630      * read operation that is called above the log
631      */
632 
633     /**
634         Get a page number that is free
635     */
636     protected long getFreePageNumber(long pnum)
637     {
638         // if we can reuse page, do so, otherwise add a brand new page
639         if (mayHaveFreePage())
640         {
641             // The last allocated page may be from a previous alloc extent, but
642             // if that extent is full and we are the first extent that can
643             // accomodate a new page, we may be picked.  In that case, pnum may
644             // be before the start of this extent.
645             int i = (pnum < extentStart) ? freePages.anySetBit() : 
646                 freePages.anySetBit((int)(pnum-extentStart));
647 
648             if (i != -1)
649             {
650                 if (SanityManager.DEBUG)
651                 {
652                     if (i >= extentLength)
653                         SanityManager.THROWASSERT("returned bit = " + i +
654                                          " extent length = " + extentLength);
655                 }
656 
657                 return i+extentStart;
658             }
659 
660             // the hint is wrong, no free page in the extent
661             // do this unlogged, it is just a hint, don't care if it is lost
662             if (pnum < extentStart)
663                 setExtentFreePageStatus(false);
664         }
665 
666         // maximally, we can have up to extendEnd page
667         if (SanityManager.DEBUG)
668             SanityManager.ASSERT(extentStart+extentLength <= extentEnd);
669 
670         // need to add a brand new page, current end of extent is at page
671         // extentStart+extentLength-1;
672         return extentStart+extentLength;
673     }
674 
675 
676     /**
677         Get the physical offset of pagenum.
678         If deallocOK is true, then even if pagenum is deallocated, it is OK.
679         If deallocOK is false, then an exception is thrown if pagenum is
680         deallocated.
681 
682         An exception is always thrown if pagenum is a free page
683 
684         @exception StandardException Standard Cloudscape error policy
685      */
686     protected long getPageOffset(long pagenum, int pagesize, boolean deallocOK) throws StandardException
687     {
688         return pagenum * pagesize;
689     }
690 
691     /**
692         Return the status of this extent
693     */
694     protected boolean isRetired()
695     {
696         return ((extentStatus & RETIRED) != 0);
697     }
698 
699     private boolean mayHaveFreePage()
700     {
701         return ((extentStatus & HAS_FREE) != 0);
702     }
703 
704     private void setExtentFreePageStatus(boolean hasFree)
705     {
706         if (hasFree)
707             extentStatus |= HAS_FREE;
708         else
709             extentStatus &= ~HAS_FREE;
710     }
711 
712     protected boolean canAddFreePage(long lastAllocatedPage)
713     {
714         // the last page to be allocated == extentEnd
715         if (extentStart + extentLength <= extentEnd)
716             return true;
717 
718         // else, check to see if this may have any free page
719         if (!mayHaveFreePage())
720             return false;
721 
722         // we may have a free page, but that is not certain, double check
723         if (lastAllocatedPage < extentStart)
724             return (freePages.anySetBit() != -1);
725         else
726             return ((freePages.anySetBit((int)(lastAllocatedPage-extentStart))) != -1);
727     }
728 
729     /**
730         Return the status of a particular page
731     */
732     protected int getPageStatus(long pagenum)
733     {
734         if (SanityManager.DEBUG)
735             checkInRange(pagenum);
736 
737         int status = 0;
738         int bitnum = (int)(pagenum-extentStart);
739 
740         if (freePages.isSet(bitnum))
741             status = FREE_PAGE;
742         else
743             status = ALLOCATED_PAGE;
744 
745         return status;
746     }
747 
748 
749     /**
750         Get the first logical page number managed by this extent.
751     */
752     protected long getFirstPagenum()
753     {
754         return extentStart;
755     }
756 
757     /**
758         Get the last logical page number managed by this extent.
759     */
760     protected long getLastPagenum()
761     {
762         return extentStart+extentLength-1;
763     }
764 
765     /**
766      * translate bit position in map to page number.
767      * <p>
768      *
769      * @return The page number of this "bit" in the extent map.
770      *
771      * @exception  StandardException  Standard exception policy.
772      **/
773     protected long getPagenum(int bit_pos)
774     {
775         return(extentStart + bit_pos);
776     }
777         
778 
779 
780     /*
781      * page preallocation 
782      */
783 
784     /**
785      * get the last preallocated pagenumber managed by this alloc page
786      */
787     protected long getLastPreallocPagenum()
788     {
789         if (extentLength > preAllocLength)
790             preAllocLength = extentLength;
791 
792         return extentStart + preAllocLength - 1 ;
793     }
794 
795     /**
796         preallocated N pages, passed in the last preallocated page number.
797     */
798     protected void setLastPreallocPagenum(long preAllocPagenum)
799     {
800         if (SanityManager.DEBUG)
801             SanityManager.ASSERT(preAllocPagenum >= getLastPreallocPagenum(),
802                 "setLastPreallocPagenum set to small prealloc length than before");
803 
804         // cannot prealloc more than this extent can handle
805         if (preAllocPagenum > extentEnd)
806             preAllocPagenum = extentEnd;
807 
808         preAllocLength = (int)(preAllocPagenum - extentStart + 1);
809     }
810 
811 
812     /*
813       Get the logical page number that is bigger than prevPageNumber
814       and is a valid page.  If no such page in this extent, return
815       ContainerHandle.INVALID_PAGE_HANDLE
816     */
817     protected long getNextValidPageNumber(long prevPageNumber)
818     {
819         long pageNum;
820         long lastpage = getLastPagenum();
821 
822         if (prevPageNumber < extentStart)
823             pageNum = extentStart;
824         else
825             pageNum = prevPageNumber +1;
826 
827         while(pageNum <= lastpage)
828         {
829             int status = getPageStatus(pageNum);
830             if (status == ALLOCATED_PAGE)
831                 break;
832             pageNum++;
833         }
834 
835         if (pageNum > lastpage)
836             pageNum = ContainerHandle.INVALID_PAGE_NUMBER;
837         return pageNum;
838     }
839 
840 
841     protected long getLastValidPageNumber()
842     {
843         long pageNum = getLastPagenum();
844         while(pageNum >= extentStart)
845         {
846             int status = getPageStatus(pageNum);
847             if (status == ALLOCATED_PAGE)
848                 break;
849             pageNum--;
850         }
851         if (pageNum < extentStart)
852             pageNum = ContainerHandle.INVALID_PAGE_NUMBER;
853         return pageNum;
854     }
855 
856     private void checkInRange(long pagenum)
857     {
858         if (SanityManager.DEBUG)
859             if (pagenum < extentStart || pagenum >= extentStart+extentLength)
860                 SanityManager.THROWASSERT(
861                     "pagenum " + pagenum + " out of range");
862     }
863 
864     protected void updateUnfilledPageInfo(AllocExtent inputExtent)
865     {
866         if (SanityManager.DEBUG)
867         {
868             if (inputExtent.unFilledPages.getLength() != 
869                     unFilledPages.getLength())
870             {
871                 SanityManager.THROWASSERT(
872                     "inputExtent's unfilled page length " +
873                     inputExtent.unFilledPages.getLength() + 
874                     " != extent's unfilled page length " + 
875                     unFilledPages.getLength());
876             }
877         }
878 
879         // just use the passed in inputExtent, we know (wink wink) that the
880         // unfilled page info is being updated just when the allocation cache
881         // is being invalidated.  Nobody is going to have a reference to the
882         // inputExtent after this so is it save to share the FormatableBitSet.
883 
884         // if we cannot guarentee that the inputExtent will be unchanged by the
885         // caller, we need to copy it       
886         //      unFilledPages = new FormatableBitSet(inputExtent.unFilledPages);
887         // Right now, just reference it directly
888         unFilledPages = inputExtent.unFilledPages;
889 
890         if (unFilledPages.anySetBit() >= 0)
891             extentStatus |= HAS_UNFILLED_PAGES;
892         else
893             extentStatus &= ~HAS_UNFILLED_PAGES;
894     }
895 
896     /*
897         Keep track of unfilled pages, if the extent changed, returns true.
898      */
899     protected boolean trackUnfilledPage(long pagenumber, boolean unfilled)
900     {
901         checkInRange(pagenumber);
902 
903         int bitnum = (int)(pagenumber-extentStart);
904 
905         boolean bitSet = unFilledPages.isSet(bitnum);
906         if (unfilled != bitSet)
907         {
908             if (unfilled)
909             {
910                 unFilledPages.set(bitnum);
911                 extentStatus |= HAS_UNFILLED_PAGES;
912             }
913             else
914                 unFilledPages.clear(bitnum);
915             return true;
916         }
917 
918         return false;
919     }
920 
921     /**
922         Get a page number that is unfilled, pagenum is the last page that was
923         rejected.
924      */
925     protected long getUnfilledPageNumber(long pagenum)
926     {
927         if ((extentStatus & HAS_UNFILLED_PAGES) == 0)
928             return ContainerHandle.INVALID_PAGE_NUMBER;
929 
930         int i = unFilledPages.anySetBit();
931 
932         if (i != -1)
933         {
934             if (i+extentStart != pagenum)
935                 return i+extentStart;
936             else
937             {
938                 // unfortunately, we found the same page number that
939                 // was rejected.  It would be unwise to unset bit
940                 // pagenum because just because it was rejected does not mean
941                 // the page is full, the row we are trying to insert may just
942                 // be too big.  If we unset it, we will never find that page
943                 // again even though it may be a perfectly good page for any
944                 // other row.  Just get the next set bit.
945                 i = unFilledPages.anySetBit(i);
946                 if (i != -1)
947                     return i+extentStart;
948             }
949         }
950 
951         return ContainerHandle.INVALID_PAGE_NUMBER;
952 
953     }
954 
955     /**
956         Get the number of used page in this extent
957      */
958     protected int getAllocatedPageCount()
959     {
960         // allocated page is one which is not free or deallocated.
961         int allocatedPageCount = extentLength;
962 
963         if (!mayHaveFreePage())
964             return allocatedPageCount;
965 
966 
967         byte[] free = freePages.getByteArray();
968         int numBytes = free.length;
969 
970         for (int i = 0; i < numBytes; i++)
971         {
972             if (free[i] != 0)
973             {
974                 for (int j = 0; j < 8; j++)
975                 {
976                     if (((1 << j) & free[i]) != 0)
977                     {
978                         allocatedPageCount--;
979                     }
980                 }
981             }
982         }
983 
984         if (SanityManager.DEBUG)
985         {
986             if (allocatedPageCount < 0)
987             {
988                 SanityManager.THROWASSERT(
989                     "number of allocated page < 0, val =" + allocatedPageCount +
990                     "\nextent = " + toDebugString());
991             }
992         }
993 
994         return allocatedPageCount;
995     }
996 
997 
998     /**
999         Get the number of unfilled pages in this extent
1000     */
1001    protected int getUnfilledPageCount()
1002    {
1003        int unfilledPageCount = 0;
1004        int freePagesSize = freePages.size();
1005
1006        for (int i = 0; i < unFilledPages.size(); i++)
1007        {
1008            if (unFilledPages.isSet(i) &&
1009                (i >= freePagesSize || !freePages.isSet(i)))
1010                unfilledPageCount++;
1011        }
1012
1013        if (SanityManager.DEBUG)
1014            SanityManager.ASSERT(unfilledPageCount >= 0,
1015                                 "number of unfilled pages < 0");
1016
1017        return unfilledPageCount;
1018    }
1019
1020
1021    /**
1022        Get the total number of pages in this extent
1023     */
1024    protected int getTotalPageCount()
1025    {
1026        return extentLength;
1027    }
1028
1029    protected String   toDebugString()
1030    {
1031        if (SanityManager.DEBUG)
1032        {
1033            String   str =
1034                "------------------------------------------------------------------------------\n" +
1035                "Extent map of from page " + extentStart + " to page " + extentEnd + "\n";
1036
1037            for (long i = extentStart; i < extentStart+extentLength; i++)
1038            {
1039                str += "\tpage " + i + ": ";
1040                switch(getPageStatus(i))
1041                {
1042                case FREE_PAGE: str += "free page\n"; break;
1043                case ALLOCATED_PAGE: str += "valid, in use page\n"; break;
1044                }
1045
1046                // int bitnum = (int)(i-extentStart);
1047                // if (unFilledPages.isSet(bitnum))
1048                //    str += "          page is estimated to be unfilled\n";
1049            }
1050
1051            if (getLastPagenum() < extentEnd)
1052                str += "\tFrom " + getLastPagenum() + " to " + extentEnd +
1053                    " are un-allocated pages\n";
1054
1055            str += "------------------------------------------------------------------------------\n";
1056
1057            return str;
1058        }
1059        else
1060            return null;
1061    }
1062
1063}
1064
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags