001: /*
002:
003: Derby - Class org.apache.derby.impl.store.raw.data.AllocationCache
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.store.raw.data;
023:
024: import org.apache.derby.iapi.services.sanity.SanityManager;
025: import org.apache.derby.iapi.error.StandardException;
026: import org.apache.derby.iapi.store.raw.ContainerHandle;
027:
028: import org.apache.derby.impl.store.raw.data.BaseContainerHandle;
029:
030: /**
031: An auxiliary object to cache the allocation information for a file container.
032: <B>Only a FileContainer should use this object</B>
033: <P>
034: The allocation cache contains an array of AllocExtents and 3 arrays of longs:
035: <OL><LI>ExtentPageNums[i] is the page number of the i'th extent
036: <LI>lowRange[i] is the smallest page number managed by extent i
037: <LI>hiRange[i] is the largest page number managed by extent i
038: </OL>
039: <P>
040: Note thate extentPageNums and lowRange does not change once the extent has
041: been created, but hiRange will change for the last extent as more pages are
042: allocated.
043: <P>
044: Extents can be individually invalidated or the entire cache (all extends)
045: can be invalidated at once.
046: <P> MT - unsafe
047: Synrhonized access to all methods must be enforced by the caller of
048: AllocationCache
049: */
050: class AllocationCache {
051: private int numExtents;
052: private long[] lowRange; // lowRange[i] to hiRange[i] defines the
053: private long[] hiRange; // smallest and largest logical page number
054: // manages by extent i
055:
056: private boolean[] isDirty; // changes to the in memory allocation cache
057: private AllocExtent[] extents;
058: private long[] extentPageNums;
059: private boolean isValid;
060:
061: protected AllocationCache() {
062: numExtents = 0;
063: isValid = false;
064: }
065:
066: /* reset the allocation cache in case when filecontainer object is reused */
067: protected void reset() {
068: numExtents = 0;
069: isValid = false;
070:
071: if (lowRange != null) {
072: for (int i = 0; i < lowRange.length; i++) {
073: lowRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
074: hiRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
075: extentPageNums[i] = ContainerHandle.INVALID_PAGE_NUMBER;
076: extents[i] = null;
077: isDirty[i] = false;
078: }
079: }
080: }
081:
082: /**
083: Get the page number for the allocation page that is managing this page number
084: */
085: protected long getAllocPageNumber(BaseContainerHandle handle,
086: long pageNumber, long firstAllocPageNumber)
087: throws StandardException {
088: // try to see if we can figure this out without validating the cache
089: for (int i = 0; i < numExtents; i++) {
090: if (lowRange[i] <= pageNumber && pageNumber <= hiRange[i])
091: return extentPageNums[i];
092: }
093:
094: if (!isValid) {
095: /* can't find the page. Validate the cache first, then try to find it again */
096: validate(handle, firstAllocPageNumber);
097:
098: for (int i = 0; i < numExtents; i++) {
099: if (lowRange[i] <= pageNumber
100: && pageNumber <= hiRange[i])
101: return extentPageNums[i];
102: }
103: }
104: return ContainerHandle.INVALID_PAGE_NUMBER;
105: }
106:
107: /**
108: Get the last (allocated) page of the container
109: */
110: protected long getLastPageNumber(BaseContainerHandle handle,
111: long firstAllocPageNumber) throws StandardException {
112: if (!isValid)
113: validate(handle, firstAllocPageNumber);
114: return hiRange[numExtents - 1];
115: }
116:
117: /**
118: Set the page number to be unfilled
119: */
120: protected void trackUnfilledPage(long pagenumber, boolean unfilled) {
121: // do not validate the alloc cache just for the purpose of updating the
122: // unfilled bit
123: if (!isValid || numExtents <= 0) {
124: return;
125: }
126:
127: // we are calling this without getting the allocCache semaphore - be
128: // careful that extents[i] will go null at any time.
129: for (int i = 0; i < numExtents; i++) {
130: if (lowRange[i] <= pagenumber && pagenumber <= hiRange[i]) {
131: AllocExtent ext = extents[i];
132: if (ext != null
133: && ext.trackUnfilledPage(pagenumber, unfilled)
134: && extents[i] != null) {
135: isDirty[i] = true;
136: }
137:
138: break;
139: }
140: }
141: }
142:
143: protected long getUnfilledPageNumber(BaseContainerHandle handle,
144: long firstAllocPageNumber, long pagenum)
145: throws StandardException {
146: // get the next unfilled page number
147: if (!isValid) {
148: validate(handle, firstAllocPageNumber);
149: }
150:
151: if (pagenum == ContainerHandle.INVALID_PAGE_NUMBER) {
152: for (int i = 0; i < numExtents; i++) {
153: if (extents[i] != null)
154: return extents[i].getUnfilledPageNumber(pagenum);
155: }
156: } else {
157: for (int i = 0; i < numExtents; i++) {
158: if (pagenum <= hiRange[i]) {
159: if (extents[i] != null)
160: return extents[i]
161: .getUnfilledPageNumber(pagenum);
162: }
163: }
164: }
165:
166: return ContainerHandle.INVALID_PAGE_NUMBER;
167: }
168:
169: /**
170: returns estimated number of allocated pages
171: **/
172: protected long getEstimatedPageCount(BaseContainerHandle handle,
173: long firstAllocPageNumber) throws StandardException {
174: if (!isValid)
175: validate(handle, firstAllocPageNumber);
176:
177: long estPageCount = 0;
178:
179: for (int i = 0; i < numExtents; i++) {
180: if (extents[i] != null)
181: estPageCount += extents[i].getAllocatedPageCount();
182: }
183: return estPageCount;
184: }
185:
186: protected SpaceInformation getAllPageCounts(
187: BaseContainerHandle handle, long firstAllocPageNumber)
188: throws StandardException {
189: long currAllocPages = 0;
190: long numAllocatedPages = 0;
191: long numFreePages = 0;
192: long numUnfilledPages = 0;
193:
194: if (!isValid)
195: validate(handle, firstAllocPageNumber);
196:
197: for (int i = 0; i < numExtents; i++) {
198: if (extents[i] != null) {
199: currAllocPages = extents[i].getAllocatedPageCount();
200: numAllocatedPages += currAllocPages;
201: numUnfilledPages += extents[i].getUnfilledPageCount();
202: numFreePages += (extents[i].getTotalPageCount() - currAllocPages);
203: }
204:
205: if (SanityManager.DEBUG) {
206: SanityManager.ASSERT(
207: numUnfilledPages <= numAllocatedPages,
208: "more unfilled pages than allocated pages on extent["
209: + i + "], " + "numUnfilledPages = "
210: + numUnfilledPages
211: + ", numAllocatedPages = "
212: + numAllocatedPages
213: + ", numFreePages = " + numFreePages);
214: }
215: }
216: return new SpaceInformation(numAllocatedPages, numFreePages,
217: numUnfilledPages);
218: }
219:
220: /* invalidate all extents */
221: protected void invalidate() {
222: if (SanityManager.DEBUG) {
223: if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE)) {
224: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
225: "alloc cache invalidated");
226: }
227: }
228:
229: for (int i = 0; i < numExtents; i++) {
230: isDirty[i] = false;
231: extents[i] = null;
232: }
233:
234: isValid = false;
235:
236: }
237:
238: /* invalidate the extent that is managed by this alloc page */
239: protected void invalidate(AllocPage allocPage, long allocPagenum)
240: throws StandardException {
241: if (SanityManager.DEBUG) {
242: if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE)) {
243: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
244: "alloc cache for page " + allocPagenum
245: + " invalidated");
246: }
247: }
248:
249: isValid = false;
250:
251: if (numExtents == 0)
252: return;
253:
254: for (int i = 0; i < numExtents; i++) {
255: if (extentPageNums[i] == allocPagenum) {
256: // update unfilled page info
257: if (allocPage != null && extents[i] != null
258: && isDirty[i]) {
259: // replace unFilledPage bitmap with the one in the allocation
260: // cache, which has the more current information
261: // call this ONLY in invalidate, when the reference to the
262: // extent is about to be nulled out
263: allocPage.updateUnfilledPageInfo(extents[i]);
264: isDirty[i] = false;
265: }
266:
267: extents[i] = null;
268: return;
269: }
270: }
271:
272: // handle the case where a new alloc page that has never been entered
273: // into the cache is asked to be invalidated
274: if (allocPagenum > hiRange[numExtents - 1])
275: return;
276:
277: if (SanityManager.DEBUG)
278: SanityManager.THROWASSERT("cannot find extent managed by "
279: + allocPagenum);
280:
281: }
282:
283: /* invalidate the last extent */
284: protected void invalidateLastExtent() {
285: if (SanityManager.DEBUG) {
286: if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE)) {
287: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
288: "last extent ("
289: + extentPageNums[numExtents - 1]
290: + ") invalidated");
291: }
292: }
293:
294: isValid = false;
295:
296: if (numExtents > 0)
297: extents[numExtents - 1] = null;
298: }
299:
300: /**
301: Get the last valid page of the file container. A valid page is one that
302: is not deallocated or freed.
303: */
304: protected long getLastValidPage(BaseContainerHandle handle,
305: long firstAllocPageNumber) throws StandardException {
306: AllocExtent extent = null;
307: int extentNumber;
308: long lastValidPageNumber = ContainerHandle.INVALID_PAGE_NUMBER;
309:
310: if (!isValid)
311: validate(handle, firstAllocPageNumber);
312:
313: if (numExtents == 0) // no extent at all, no page in the container
314: return ContainerHandle.INVALID_PAGE_NUMBER;
315:
316: // start from the last extent, goes backward till a valid page is found
317:
318: for (extentNumber = numExtents - 1; extentNumber >= 0; extentNumber--) {
319: extent = extents[extentNumber];
320: lastValidPageNumber = extent.getLastValidPageNumber();
321: if (lastValidPageNumber != ContainerHandle.INVALID_PAGE_NUMBER)
322: break;
323: }
324: return lastValidPageNumber;
325: }
326:
327: /*
328: Get the next page (after pageNumber) that is valid
329: */
330: protected long getNextValidPage(BaseContainerHandle handle,
331: long pageNumber, long firstAllocPageNumber)
332: throws StandardException {
333: int extentNumber;
334:
335: if (!isValid)
336: validate(handle, firstAllocPageNumber);
337:
338: if (numExtents == 0) // no extent at all, no page in the container
339: return ContainerHandle.INVALID_PAGE_NUMBER;
340:
341: // find the extent whose hiRange is > pageNumber. Most of the time,
342: // this is the extent this pageNumber is in, but some times, when
343: // pageNumber == hiRange of extent i, extent i+1 is found.
344: AllocExtent extent = null;
345: for (extentNumber = 0; extentNumber < numExtents; extentNumber++) {
346: if (pageNumber < hiRange[extentNumber]) {
347: extent = extents[extentNumber];
348: break;
349: }
350: }
351:
352: if (extent == null) // extent has been invalidated or not there
353: {
354: // the cache is valid and up to date,
355: // the only reason why we cannot find an extent is if this is the
356: // last valid page of the container
357: return ContainerHandle.INVALID_PAGE_NUMBER;
358: }
359:
360: // extent == extents[extentNumber]
361: if (SanityManager.DEBUG)
362: SanityManager.ASSERT(extent == extents[extentNumber]);
363:
364: // we found an extent which may contain a valid page that is of higher
365: // pagenumber than the passed in page number. Still need to walk the
366: // extent array to make sure
367:
368: long nextValidPage = ContainerHandle.INVALID_PAGE_NUMBER;
369:
370: while (extentNumber < numExtents) {
371: extent = extents[extentNumber];
372: nextValidPage = extent.getNextValidPageNumber(pageNumber);
373: if (nextValidPage != ContainerHandle.INVALID_PAGE_NUMBER)
374: break;
375:
376: extentNumber++;
377: }
378: return nextValidPage;
379:
380: }
381:
382: /**
383: Get the page status of a page
384: */
385: protected int getPageStatus(BaseContainerHandle handle,
386: long pageNumber, long firstAllocPageNumber)
387: throws StandardException {
388: AllocExtent extent = null;
389:
390: for (int i = 0; i < numExtents; i++) {
391: if (lowRange[i] <= pageNumber && pageNumber <= hiRange[i]) {
392: extent = extents[i];
393: break;
394: }
395: }
396:
397: if (extent == null) {
398: if (SanityManager.DEBUG) {
399: if (isValid) {
400:
401: SanityManager.DEBUG_PRINT("trace",
402: "Allocation cache is "
403: + (isValid ? "Valid" : "Invalid"));
404:
405: for (int i = 0; i < numExtents; i++) {
406: SanityManager.DEBUG_PRINT("trace", "Extent "
407: + i + " at " + extentPageNums[i]
408: + " range is " + lowRange[i] + " to "
409: + hiRange[i]);
410: if (extents[i] == null)
411: SanityManager.DEBUG_PRINT("trace",
412: "extent is null");
413: else
414: SanityManager.DEBUG_PRINT("trace",
415: extents[i].toDebugString());
416:
417: }
418:
419: SanityManager
420: .THROWASSERT("valid cache cannot find page "
421: + pageNumber);
422: }
423: }
424:
425: if (!isValid)
426: validate(handle, firstAllocPageNumber);
427: // try again
428:
429: for (int i = 0; i < numExtents; i++) {
430: if (lowRange[i] <= pageNumber
431: && pageNumber <= hiRange[i]) {
432: extent = extents[i];
433: break;
434: }
435: }
436:
437: if (SanityManager.DEBUG)
438: if (extent == null)
439: SanityManager
440: .THROWASSERT("valid cache cannot find page "
441: + pageNumber);
442: }
443:
444: return extent.getPageStatus(pageNumber);
445: }
446:
447: /**
448: Validate the cache, find all alloc pages and fill in the arrays
449: */
450: private void validate(BaseContainerHandle handle,
451: long firstAllocPageNumber) throws StandardException {
452: if (numExtents == 0) // never been initialized, read it all in
453: {
454: long pagenum = firstAllocPageNumber;
455:
456: while (!isValid) {
457: growArrays(++numExtents);
458:
459: Object obj = handle.getAllocPage(pagenum);
460:
461: if (SanityManager.DEBUG) {
462: if (obj == null)
463: SanityManager.THROWASSERT("cannot find "
464: + numExtents + " alloc page at "
465: + pagenum);
466: if (!(obj instanceof AllocPage))
467: SanityManager.THROWASSERT("page at " + pagenum
468: + " is not an allocPage, is a "
469: + obj.getClass().getName());
470: }
471:
472: AllocPage allocPage = (AllocPage) obj;
473: setArrays(numExtents - 1, allocPage);
474:
475: if (allocPage.isLast())
476: isValid = true;
477: else
478: // get next alloc page
479: pagenum = allocPage.getNextAllocPageNumber();
480:
481: allocPage.unlatch();
482: }
483: } else // has been initialized before, but is now invalidated
484: {
485: for (int i = 0; i < numExtents - 1; i++) {
486: if (extents[i] == null) // reinitialize this extent
487: {
488: AllocPage allocPage = (AllocPage) handle
489: .getAllocPage(extentPageNums[i]);
490:
491: setArrays(i, allocPage);
492:
493: if (SanityManager.DEBUG) {
494: if (i < numExtents - 1) {
495: if (extentPageNums[i + 1] != allocPage
496: .getNextAllocPageNumber()) {
497: SanityManager
498: .THROWASSERT("bad alloc page - "
499: + ";extentPageNums[i+1] = "
500: + extentPageNums[i + 1]
501: + ";allocPage.getNextAllocPageNumber() = "
502: + allocPage
503: .getNextAllocPageNumber());
504: }
505: }
506: }
507:
508: allocPage.unlatch();
509: }
510: }
511: // always get the last alloc page to see if the number of alloc
512: // pages remain the same
513: long pagenum = extentPageNums[numExtents - 1];
514: while (!isValid) {
515: AllocPage allocPage = (AllocPage) handle
516: .getAllocPage(pagenum);
517:
518: if (extents[numExtents - 1] == null)
519: setArrays(numExtents - 1, allocPage);
520:
521: if (!allocPage.isLast()) {
522: growArrays(++numExtents);
523: pagenum = allocPage.getNextAllocPageNumber();
524: } else
525: isValid = true;
526:
527: allocPage.unlatch();
528: }
529: }
530: }
531:
532: /* shorthand to set the 4 array values */
533: private void setArrays(int i, AllocPage allocPage) {
534: if (SanityManager.DEBUG) {
535: if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE)) {
536: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
537: "Alloc page " + i + " at "
538: + allocPage.getPageNumber()
539: + " updated");
540: }
541: }
542:
543: AllocExtent extent = allocPage.getAllocExtent();
544: extents[i] = extent;
545: lowRange[i] = extent.getFirstPagenum();
546: hiRange[i] = extent.getLastPagenum();
547: extentPageNums[i] = allocPage.getPageNumber();
548: }
549:
550: /* shorthand to grow the 4 arrays to the desired size */
551: private void growArrays(int size) {
552: int oldLength;
553:
554: if (lowRange == null || lowRange.length == 0)
555: oldLength = 0;
556: else
557: oldLength = lowRange.length;
558:
559: if (oldLength >= size) // no need to grow
560: return;
561:
562: long[] saveLow = lowRange;
563: long[] saveHi = hiRange;
564: AllocExtent[] saveExtents = extents;
565: boolean[] saveDirty = isDirty;
566: long[] savePageNums = extentPageNums;
567:
568: lowRange = new long[size];
569: hiRange = new long[size];
570: isDirty = new boolean[size];
571: extents = new AllocExtent[size];
572: extentPageNums = new long[size];
573:
574: if (oldLength > 0) {
575: if (SanityManager.DEBUG) {
576: SanityManager.ASSERT(oldLength == saveHi.length);
577: SanityManager.ASSERT(oldLength == saveExtents.length);
578: SanityManager.ASSERT(oldLength == savePageNums.length);
579: }
580: System.arraycopy(saveLow, 0, lowRange, 0, saveLow.length);
581: System.arraycopy(saveHi, 0, hiRange, 0, saveHi.length);
582: System
583: .arraycopy(saveDirty, 0, isDirty, 0,
584: saveDirty.length);
585: System.arraycopy(saveExtents, 0, extents, 0,
586: saveExtents.length);
587: System.arraycopy(savePageNums, 0, extentPageNums, 0,
588: savePageNums.length);
589: }
590:
591: for (int i = oldLength; i < size; i++) {
592: lowRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
593: hiRange[i] = ContainerHandle.INVALID_PAGE_NUMBER;
594: isDirty[i] = false;
595: extentPageNums[i] = ContainerHandle.INVALID_PAGE_NUMBER;
596: extents[i] = null;
597: }
598: }
599:
600: /**
601: dump the allocation cache information
602: */
603: protected void dumpAllocationCache() {
604: if (SanityManager.DEBUG) {
605: if (SanityManager.DEBUG_ON(FileContainer.SPACE_TRACE)) {
606: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
607: "Allocation cache is "
608: + (isValid ? "Valid" : "Invalid"));
609: for (int i = 0; i < numExtents; i++) {
610: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
611: "Extent " + i + " at " + extentPageNums[i]
612: + " range is " + lowRange[i]
613: + " to " + hiRange[i]);
614:
615: if (extents[i] == null) {
616: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
617: "extent is null");
618: } else {
619: SanityManager.DEBUG(FileContainer.SPACE_TRACE,
620: extents[i].toDebugString());
621: }
622: }
623: }
624: }
625: }
626:
627: }
|