KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > raw > data > AllocationCache


1 /*
2
3    Derby - Class org.apache.derby.impl.store.raw.data.AllocationCache
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
28 import org.apache.derby.impl.store.raw.data.BaseContainerHandle;
29 /**
30     An auxiliary object to cache the allocation information for a file container.
31     <B>Only a FileContainer should use this object</B>
32     <P>
33     The allocation cache contains an array of AllocExtents and 3 arrays of longs:
34     <OL><LI>ExtentPageNums[i] is the page number of the i'th extent
35     <LI>lowRange[i] is the smallest page number managed by extent i
36     <LI>hiRange[i] is the largest page number managed by extent i
37     </OL>
38     <P>
39     Note thate extentPageNums and lowRange does not change once the extent has
40     been created, but hiRange will change for the last extent as more pages are
41     allocated.
42     <P>
43     Extents can be individually invalidated or the entire cache (all extends)
44     can be invalidated at once.
45     <P> MT - unsafe
46     Synrhonized access to all methods must be enforced by the caller of
47     AllocationCache
48 */
49 class AllocationCache
50 {
51     private int numExtents;
52     private long[] lowRange; // lowRange[i] to hiRange[i] defines the
53 private long[] hiRange; // smallest and largest logical page number
54 // manages by extent i
55
56     private boolean[] isDirty; // changes to the in memory allocation cache
57 private AllocExtent[] extents;
58     private long[] extentPageNums;
59     private boolean isValid;
60
61     protected AllocationCache()
62     {
63         numExtents = 0;
64         isValid = false;
65     }
66
67     /* reset the allocation cache in case when filecontainer object is reused */
68     protected void reset()
69     {
70         numExtents = 0;
71         isValid = false;
72
73         if (lowRange != null)
74         {
75             for (int i = 0; i < lowRange.length; i++)
76             {
77                 lowRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
78                 hiRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
79                 extentPageNums[i] = ContainerHandle.INVALID_PAGE_NUMBER;
80                 extents[i] = null;
81                 isDirty[i] = false;
82             }
83         }
84     }
85
86     /**
87       Get the page number for the allocation page that is managing this page number
88     */
89     protected long getAllocPageNumber(BaseContainerHandle handle,
90                                    long pageNumber,
91                                    long firstAllocPageNumber)
92          throws StandardException
93     {
94         // try to see if we can figure this out without validating the cache
95 for (int i = 0; i < numExtents; i++)
96         {
97             if (lowRange[i] <= pageNumber && pageNumber <= hiRange[i])
98                 return extentPageNums[i];
99         }
100
101         if (!isValid)
102         {
103             /* can't find the page. Validate the cache first, then try to find it again */
104             validate(handle, firstAllocPageNumber);
105             
106             for (int i = 0; i < numExtents; i++)
107             {
108                 if (lowRange[i] <= pageNumber && pageNumber <= hiRange[i])
109                     return extentPageNums[i];
110             }
111         }
112         return ContainerHandle.INVALID_PAGE_NUMBER;
113     }
114
115     /**
116       Get the last (allocated) page of the container
117       */
118     protected long getLastPageNumber(BaseContainerHandle handle, long firstAllocPageNumber)
119          throws StandardException
120     {
121         if (!isValid)
122             validate(handle, firstAllocPageNumber);
123         return hiRange[numExtents-1];
124     }
125
126     /**
127       Set the page number to be unfilled
128      */
129     protected void trackUnfilledPage(long pagenumber, boolean unfilled)
130     {
131         // do not validate the alloc cache just for the purpose of updating the
132 // unfilled bit
133 if (!isValid || numExtents <= 0)
134         {
135             return;
136         }
137
138         // we are calling this without getting the allocCache semaphore - be
139 // careful that extents[i] will go null at any time.
140 for (int i = 0; i < numExtents; i++)
141         {
142             if (lowRange[i] <= pagenumber && pagenumber <= hiRange[i])
143             {
144                 AllocExtent ext = extents[i];
145                 if (ext != null &&
146                     ext.trackUnfilledPage(pagenumber, unfilled) &&
147                     extents[i] != null)
148                 {
149                     isDirty[i] = true;
150                 }
151                     
152                 break;
153             }
154         }
155     }
156
157     protected long getUnfilledPageNumber(BaseContainerHandle handle,
158                                          long firstAllocPageNumber,
159                                          long pagenum)
160          throws StandardException
161     {
162         // get the next unfilled page number
163 if (!isValid)
164         {
165             validate(handle, firstAllocPageNumber);
166         }
167
168         if (pagenum == ContainerHandle.INVALID_PAGE_NUMBER)
169         {
170             for (int i = 0; i < numExtents; i++)
171             {
172                 if (extents[i] != null)
173                     return extents[i].getUnfilledPageNumber(pagenum);
174             }
175         }
176         else
177         {
178             for (int i = 0; i < numExtents; i++)
179             {
180                 if (pagenum <= hiRange[i])
181                 {
182                     if (extents[i] != null)
183                         return extents[i].getUnfilledPageNumber(pagenum);
184                 }
185             }
186         }
187
188         return ContainerHandle.INVALID_PAGE_NUMBER;
189     }
190
191     /**
192     returns estimated number of allocated pages
193     **/
194     protected long getEstimatedPageCount(BaseContainerHandle handle,
195                                          long firstAllocPageNumber)
196          throws StandardException
197     {
198         if (!isValid)
199             validate(handle, firstAllocPageNumber);
200
201         long estPageCount = 0;
202
203         for (int i = 0; i < numExtents; i++)
204         {
205             if (extents[i] != null)
206                 estPageCount += extents[i].getAllocatedPageCount();
207         }
208         return estPageCount;
209     }
210
211
212     protected SpaceInformation getAllPageCounts(
213         BaseContainerHandle handle,
214         long firstAllocPageNumber)
215             throws StandardException
216     {
217         long currAllocPages = 0;
218         long numAllocatedPages = 0;
219         long numFreePages = 0;
220         long numUnfilledPages = 0;
221
222         if (!isValid)
223             validate(handle, firstAllocPageNumber);
224
225         for (int i = 0; i < numExtents; i++)
226         {
227             if (extents[i] != null)
228             {
229                 currAllocPages = extents[i].getAllocatedPageCount();
230                 numAllocatedPages += currAllocPages;
231                 numUnfilledPages += extents[i].getUnfilledPageCount();
232                 numFreePages +=
233                     (extents[i].getTotalPageCount() - currAllocPages);
234             }
235
236             if (SanityManager.DEBUG)
237             {
238                 SanityManager.ASSERT(numUnfilledPages <= numAllocatedPages,
239                     "more unfilled pages than allocated pages on extent[" + i +
240                     "], " +
241                     "numUnfilledPages = " + numUnfilledPages +
242                     ", numAllocatedPages = " + numAllocatedPages +
243                     ", numFreePages = " + numFreePages);
244             }
245         }
246         return new SpaceInformation(
247             numAllocatedPages,
248             numFreePages,
249             numUnfilledPages);
250     }
251
252
253     /* invalidate all extents */
254     protected void invalidate()
255     {
256         if (SanityManager.DEBUG)
257         {
258             if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE))
259             {
260                 SanityManager.DEBUG(
261                     FileContainer.SPACE_TRACE, "alloc cache invalidated");
262             }
263         }
264
265
266         for (int i = 0; i < numExtents; i++)
267         {
268             isDirty[i] = false;
269             extents[i] = null;
270         }
271
272         isValid = false;
273
274     }
275
276     /* invalidate the extent that is managed by this alloc page */
277     protected void invalidate(AllocPage allocPage, long allocPagenum)
278          throws StandardException
279     {
280         if (SanityManager.DEBUG)
281         {
282             if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE))
283             {
284                 SanityManager.DEBUG(
285                     FileContainer.SPACE_TRACE, "alloc cache for page " +
286                     allocPagenum + " invalidated");
287             }
288         }
289
290         isValid = false;
291
292         if (numExtents == 0)
293             return;
294
295         for (int i = 0; i < numExtents; i++)
296         {
297             if (extentPageNums[i] == allocPagenum)
298             {
299                 // update unfilled page info
300 if (allocPage != null && extents[i] != null &&
301                     isDirty[i])
302                 {
303                     // replace unFilledPage bitmap with the one in the allocation
304 // cache, which has the more current information
305 // call this ONLY in invalidate, when the reference to the
306 // extent is about to be nulled out
307 allocPage.updateUnfilledPageInfo(extents[i]);
308                     isDirty[i] = false;
309                 }
310
311                 extents[i] = null;
312                 return;
313             }
314         }
315
316         // handle the case where a new alloc page that has never been entered
317 // into the cache is asked to be invalidated
318 if (allocPagenum > hiRange[numExtents-1])
319             return;
320
321         if (SanityManager.DEBUG)
322             SanityManager.THROWASSERT("cannot find extent managed by " +
323                                       allocPagenum);
324
325
326     }
327
328     /* invalidate the last extent */
329     protected void invalidateLastExtent()
330     {
331         if (SanityManager.DEBUG)
332         {
333             if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE))
334             {
335                 SanityManager.DEBUG(
336                     FileContainer.SPACE_TRACE,
337                         "last extent (" + extentPageNums[numExtents-1] +
338                             ") invalidated");
339             }
340         }
341
342         isValid = false;
343
344         if (numExtents > 0)
345             extents[numExtents - 1] = null;
346     }
347
348     /**
349       Get the last valid page of the file container. A valid page is one that
350       is not deallocated or freed.
351     */
352     protected long getLastValidPage(BaseContainerHandle handle,
353                                     long firstAllocPageNumber)
354          throws StandardException
355     {
356         AllocExtent extent = null;
357         int extentNumber;
358         long lastValidPageNumber = ContainerHandle.INVALID_PAGE_NUMBER;
359
360         if (!isValid)
361             validate(handle, firstAllocPageNumber);
362
363         if (numExtents == 0) // no extent at all, no page in the container
364 return ContainerHandle.INVALID_PAGE_NUMBER;
365
366         // start from the last extent, goes backward till a valid page is found
367
368         for (extentNumber = numExtents-1;
369              extentNumber >= 0;
370              extentNumber--)
371         {
372             extent = extents[extentNumber];
373             lastValidPageNumber = extent.getLastValidPageNumber();
374             if (lastValidPageNumber != ContainerHandle.INVALID_PAGE_NUMBER)
375                 break;
376         }
377         return lastValidPageNumber;
378     }
379
380     /*
381       Get the next page (after pageNumber) that is valid
382       */
383     protected long getNextValidPage(BaseContainerHandle handle,
384                                     long pageNumber,
385                                     long firstAllocPageNumber)
386          throws StandardException
387     {
388         int extentNumber;
389
390         if (!isValid)
391             validate(handle, firstAllocPageNumber);
392
393         if (numExtents == 0) // no extent at all, no page in the container
394 return ContainerHandle.INVALID_PAGE_NUMBER;
395
396         // find the extent whose hiRange is > pageNumber. Most of the time,
397 // this is the extent this pageNumber is in, but some times, when
398 // pageNumber == hiRange of extent i, extent i+1 is found.
399 AllocExtent extent = null;
400         for (extentNumber = 0; extentNumber < numExtents; extentNumber++)
401         {
402             if (pageNumber < hiRange[extentNumber])
403             {
404                 extent = extents[extentNumber];
405                 break;
406             }
407         }
408
409         if (extent == null) // extent has been invalidated or not there
410 {
411             // the cache is valid and up to date,
412 // the only reason why we cannot find an extent is if this is the
413 // last valid page of the container
414 return ContainerHandle.INVALID_PAGE_NUMBER;
415         }
416
417         // extent == extents[extentNumber]
418 if (SanityManager.DEBUG)
419             SanityManager.ASSERT(extent == extents[extentNumber]);
420
421         // we found an extent which may contain a valid page that is of higher
422 // pagenumber than the passed in page number. Still need to walk the
423 // extent array to make sure
424
425         long nextValidPage = ContainerHandle.INVALID_PAGE_NUMBER;
426
427         while(extentNumber < numExtents)
428         {
429             extent = extents[extentNumber] ;
430             nextValidPage = extent.getNextValidPageNumber(pageNumber);
431             if (nextValidPage != ContainerHandle.INVALID_PAGE_NUMBER)
432                 break;
433
434             extentNumber++;
435         }
436         return nextValidPage;
437
438     }
439
440     /**
441       Get the page status of a page
442     */
443     protected int getPageStatus(BaseContainerHandle handle, long pageNumber,
444                                 long firstAllocPageNumber)
445          throws StandardException
446     {
447         AllocExtent extent = null;
448
449         for (int i = 0; i < numExtents; i++)
450         {
451             if (lowRange[i] <= pageNumber && pageNumber <= hiRange[i])
452             {
453                 extent = extents[i];
454                 break;
455             }
456         }
457
458         if (extent == null)
459         {
460             if (SanityManager.DEBUG) {
461                 if (isValid) {
462
463                     SanityManager.DEBUG_PRINT("trace", "Allocation cache is " +
464                                 (isValid ? "Valid" : "Invalid"));
465                     
466                     for (int i = 0; i < numExtents; i++) {
467                         SanityManager.DEBUG_PRINT("trace", "Extent " + i + " at " + extentPageNums[i] +
468                                         " range is " + lowRange[i] + " to " + hiRange[i]);
469                         if (extents[i] == null)
470                             SanityManager.DEBUG_PRINT("trace", "extent is null");
471                         else
472                             SanityManager.DEBUG_PRINT("trace", extents[i].toDebugString());
473
474                     }
475
476                     SanityManager.THROWASSERT("valid cache cannot find page "+pageNumber);
477                 }
478             }
479
480             if (!isValid)
481                 validate(handle, firstAllocPageNumber);
482             // try again
483
484             for (int i = 0; i < numExtents; i++)
485             {
486                 if (lowRange[i] <= pageNumber && pageNumber <= hiRange[i])
487                 {
488                     extent = extents[i];
489                     break;
490                 }
491             }
492
493             if (SanityManager.DEBUG)
494                 if (extent == null)
495                     SanityManager.THROWASSERT("valid cache cannot find page " +
496                                                 pageNumber);
497         }
498
499         return extent.getPageStatus(pageNumber);
500     }
501
502     /**
503       Validate the cache, find all alloc pages and fill in the arrays
504       */
505     private void validate(BaseContainerHandle handle, long firstAllocPageNumber)
506          throws StandardException
507     {
508         if (numExtents == 0) // never been initialized, read it all in
509 {
510             long pagenum = firstAllocPageNumber;
511
512             while(!isValid)
513             {
514                 growArrays(++numExtents);
515
516                 Object JavaDoc obj = handle.getAllocPage(pagenum);
517
518                 if (SanityManager.DEBUG)
519                 {
520                     if (obj == null)
521                         SanityManager.THROWASSERT(
522                             "cannot find " + numExtents +
523                             " alloc page at " + pagenum);
524                     if ( ! (obj instanceof AllocPage))
525                         SanityManager.THROWASSERT(
526                             "page at " + pagenum +
527                             " is not an allocPage, is a " +
528                             obj.getClass().getName());
529                 }
530
531                 AllocPage allocPage = (AllocPage)obj;
532                 setArrays(numExtents-1, allocPage);
533
534                 if (allocPage.isLast())
535                     isValid = true;
536                 else
537                     // get next alloc page
538 pagenum = allocPage.getNextAllocPageNumber();
539
540                 allocPage.unlatch();
541             }
542         }
543         else // has been initialized before, but is now invalidated
544 {
545             for (int i = 0; i < numExtents-1; i++)
546             {
547                 if (extents[i] == null) // reinitialize this extent
548 {
549                     AllocPage allocPage =
550                         (AllocPage)handle.getAllocPage(extentPageNums[i]);
551
552                     setArrays(i, allocPage);
553
554                     if (SanityManager.DEBUG)
555                     {
556                         if (i < numExtents-1)
557                         {
558                             if (extentPageNums[i+1] !=
559                                     allocPage.getNextAllocPageNumber())
560                             {
561                                 SanityManager.THROWASSERT(
562                                     "bad alloc page - " +
563                                     ";extentPageNums[i+1] = " +
564                                         extentPageNums[i+1] +
565                                     ";allocPage.getNextAllocPageNumber() = " +
566                                         allocPage.getNextAllocPageNumber());
567                             }
568                         }
569                     }
570
571                     allocPage.unlatch();
572                 }
573             }
574             // always get the last alloc page to see if the number of alloc
575 // pages remain the same
576 long pagenum = extentPageNums[numExtents-1];
577             while (!isValid)
578             {
579                 AllocPage allocPage = (AllocPage)handle.getAllocPage(pagenum);
580
581                 if (extents[numExtents-1] == null)
582                     setArrays(numExtents-1, allocPage);
583
584                 if (!allocPage.isLast())
585                 {
586                     growArrays(++numExtents);
587                     pagenum = allocPage.getNextAllocPageNumber();
588                 }
589                 else
590                     isValid = true;
591
592                 allocPage.unlatch();
593             }
594         }
595     }
596
597     /* shorthand to set the 4 array values */
598     private void setArrays(int i, AllocPage allocPage)
599     {
600         if (SanityManager.DEBUG)
601         {
602             if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE))
603             {
604                 SanityManager.DEBUG(
605                     FileContainer.SPACE_TRACE,
606                     "Alloc page " + i + " at " + allocPage.getPageNumber() +
607                     " updated");
608             }
609         }
610
611         AllocExtent extent = allocPage.getAllocExtent();
612         extents[i] = extent;
613         lowRange[i] = extent.getFirstPagenum();
614         hiRange[i] = extent.getLastPagenum();
615         extentPageNums[i] = allocPage.getPageNumber();
616     }
617
618     /* shorthand to grow the 4 arrays to the desired size */
619     private void growArrays(int size)
620     {
621         int oldLength;
622
623         if (lowRange == null || lowRange.length == 0)
624             oldLength = 0;
625         else
626             oldLength = lowRange.length;
627
628         if (oldLength >= size) // no need to grow
629 return;
630
631         long[] saveLow = lowRange;
632         long[] saveHi = hiRange;
633         AllocExtent[] saveExtents = extents;
634         boolean[] saveDirty = isDirty;
635         long[] savePageNums = extentPageNums;
636
637         lowRange = new long[size];
638         hiRange = new long[size];
639         isDirty = new boolean[size];
640         extents = new AllocExtent[size];
641         extentPageNums = new long[size];
642
643         if (oldLength > 0)
644         {
645             if (SanityManager.DEBUG)
646             {
647                 SanityManager.ASSERT(oldLength == saveHi.length);
648                 SanityManager.ASSERT(oldLength == saveExtents.length);
649                 SanityManager.ASSERT(oldLength == savePageNums.length);
650             }
651             System.arraycopy(saveLow, 0, lowRange, 0, saveLow.length);
652             System.arraycopy(saveHi, 0, hiRange, 0, saveHi.length);
653             System.arraycopy(saveDirty, 0, isDirty, 0, saveDirty.length);
654             System.arraycopy(saveExtents, 0, extents, 0, saveExtents.length);
655             System.arraycopy(savePageNums,0,extentPageNums,0, savePageNums.length);
656         }
657
658         for (int i = oldLength; i < size; i++)
659         {
660             lowRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
661             hiRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
662             isDirty[i] = false;
663             extentPageNums[i] = ContainerHandle.INVALID_PAGE_NUMBER;
664             extents[i] = null;
665         }
666     }
667
668     /**
669       dump the allocation cache information
670     */
671     protected void dumpAllocationCache()
672     {
673         if (SanityManager.DEBUG)
674         {
675             if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE))
676             {
677                 SanityManager.DEBUG(FileContainer.SPACE_TRACE,
678                                     "Allocation cache is " +
679                                     (isValid ? "Valid" : "Invalid"));
680                 for (int i = 0; i < numExtents; i++)
681                 {
682                     SanityManager.DEBUG(
683                         FileContainer.SPACE_TRACE,
684                         "Extent " + i + " at " + extentPageNums[i] +
685                         " range is " + lowRange[i] + " to " + hiRange[i]);
686
687                     if (extents[i] == null)
688                     {
689                         SanityManager.DEBUG(
690                             FileContainer.SPACE_TRACE, "extent is null");
691                     }
692                     else
693                     {
694                         SanityManager.DEBUG(
695                             FileContainer.SPACE_TRACE,
696                             extents[i].toDebugString());
697                     }
698                 }
699             }
700         }
701     }
702
703 }
704
705
Popular Tags