001: package com.quadcap.sql.file;
002:
003: /* Copyright 1997 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.io.IOException;
042: import java.io.InputStream;
043: import java.io.OutputStream;
044:
045: import com.quadcap.util.ConfigNumber;
046: import com.quadcap.util.Debug;
047: import com.quadcap.util.Util;
048:
049: /**
050: * This class implements a sub-page manager which operates by allocating
051: * pages as needed from the main file and chopping them up into smaller
052: * pages of the appropriate size.
053: *
054: * @author Stan Bailes
055: */
056: public class SubPageManager implements PageManager {
057: BlockFile file;
058: /**
059: * rootBlock is the root block of the entire block file, and will
060: * always be zero in this implementation.
061: */
062: long rootBlock;
063:
064: /** The size of a subpage */
065: int pageSize;
066:
067: /** The page shift (file.pageSize >> pageShift == pageSize) */
068: int pageShift;
069:
070: /** The offset into the root block of our freelist head */
071: int offset;
072:
073: /** (1 << pageShift) */
074: int pagesPerBlock;
075:
076: // kinda unique.
077: static final long PAGE_FREE = 0xabcddbca5438182fL;
078:
079: /**
080: * Construct a new sub-page manager bound to the specified block file
081: */
082: public SubPageManager(BlockFile file, int pageShift, long rootBlock)
083: throws IOException {
084: this .file = file;
085: this .pageShift = pageShift;
086: this .rootBlock = rootBlock;
087: this .offset = BlockFile.oSUBPAGE_ROOT + pageShift
088: * BlockFile.REF_SIZE;
089: this .pageSize = file.getPageSize() >> pageShift;
090: this .pagesPerBlock = 1 << pageShift;
091: if (pageSize < BlockFile.REF_SIZE * 2) {
092: throw new IOException("Sub page too small: " + pageSize);
093: }
094: }
095:
096: /**
097: * Allocate a new block.
098: */
099: public long newPage() throws IOException {
100: long ret = -1;
101: synchronized (file.fileLock) {
102: Block root = file.getBlock(rootBlock);
103: Page page = null;
104: try {
105: ret = root.readLong(offset);
106: if (ret == 0) {
107: ret = allocateNewBlock();
108: }
109: page = getPage(ret);
110: long next = page.readLong(0);
111: if (page.readLong(BlockFile.REF_SIZE) != PAGE_FREE) {
112: //#ifdef DEBUG
113: byte[] ff = new byte[pageSize];
114: page.read(0, ff, 0, pageSize);
115: Debug.println("Page: " + Util.strBytes(ff));
116: Debug.println("" + toString() + ".newPage() "
117: + toString(ret) + ", freelist corrupted: ");
118: //#endif
119: throw new DatafileException("" + toString()
120: + ".newPage() " + toString(ret)
121: + ", freelist corrupted: ");
122:
123: }
124: root.writeLong(offset, next);
125: page.clear(); // Can we let caller do this?
126: } finally {
127: if (page != null)
128: page.decrRefCount();
129: root.decrRefCount();
130: }
131: //#ifdef DEBUG
132: if (Trace.bit(11)) {
133: Debug.println("" + toString() + ".newPage() = "
134: + toString(ret));
135: }
136: if (pageShift(ret) != pageShift) {
137: throw new DatafileException("" + toString()
138: + ".newPage(), " + toString(ret)
139: + ", freelist corrupted");
140: }
141: //#endif
142: }
143: return ret;
144: }
145:
146: /**
147: * Free a block.
148: *
149: * @param block a previously allocated block
150: */
151: public void freePage(long block) throws IOException {
152: //- //#ifdef PARANOID
153: //- checkPage(block);
154: //#endif
155: //#ifdef DEBUG
156: if (Trace.bit(11)) {
157: Debug.println("" + toString() + ".freePage("
158: + toString(block) + ")");
159: }
160: //#endif
161: if (pageShift(block) != pageShift) {
162: throw new DatafileException("" + toString() + ".freePage("
163: + toString(block) + "), bad page");
164: }
165: synchronized (file.fileLock) {
166: Block root = file.getBlock(rootBlock);
167: try {
168: long head = root.readLong(offset);
169: if (head == block) {
170: throw new DatafileException("" + toString()
171: + ",freePage(" + toString(block)
172: + "), already" + " free");
173: }
174: Page page = getPage(block);
175: page.writeLong(0, head);
176: if (page.readLong(BlockFile.REF_SIZE) == PAGE_FREE) {
177: throw new DatafileException("" + toString()
178: + ",freePage(" + toString(block)
179: + "), already" + " free");
180: }
181: page.writeLong(BlockFile.REF_SIZE, PAGE_FREE);
182: root.writeLong(offset, block);
183: page.decrRefCount();
184: } finally {
185: root.decrRefCount();
186: }
187: }
188: }
189:
190: /**
191: * Allocate new block and slice it up into sub-pages. Link the sub-pages
192: * together and return the head of the list. Lock must be held!
193: */
194: private final long allocateNewBlock() throws IOException {
195: long blk = file.newPage();
196: //#ifdef DEBUG
197: if (Trace.bit(11)) {
198: Debug
199: .println("" + toString() + ".allocateNewBlock: "
200: + blk);
201: }
202: //#endif
203: Block b = file.getBlock(blk);
204: b.writeLong(0, 0);
205: b.writeLong(BlockFile.REF_SIZE, PAGE_FREE);
206: try {
207: long p = makePageNo(blk, 0);
208: for (int i = 1; i < pagesPerBlock; i++) {
209: long np = makePageNo(blk, i);
210: Page page = getPage(np);
211: try {
212: page.writeLong(0, p);
213: page.writeLong(BlockFile.REF_SIZE, PAGE_FREE);
214: p = np;
215: } finally {
216: page.decrRefCount();
217: }
218: }
219: return p;
220: } finally {
221: b.decrRefCount();
222: }
223: }
224:
225: /**
226: * Sub-page numbers are encoded as follows:<p>
227: * <pre>
228: * sub_page {
229: * pageShift bit4
230: * pageNum bit16
231: * blockNum bit44
232: * }
233: * </pre><p>
234: *
235: * This has the desirable property of being backward compatible with the
236: * pre-sub-page block numbers, which will have pageShift and pageNum
237: * equal to zero.
238: */
239:
240: static int[] PAGE_SHIFT = { 63, 4 };
241: static int[] PAGE_NUM = { 59, 16 };
242: //- //#ifdef PARANOID
243: //- static int[] MAGIC = {43,4};
244: //- static int[] BLOCK_NUM = {39,40};
245: //#else
246: static int[] BLOCK_NUM = { 43, 44 };
247:
248: //#endif
249:
250: static final long fIns(long v, int[] f) {
251: return (v & fMask(f)) << fEnd(f);
252: }
253:
254: static final long fMask(int[] f) {
255: return (1L << f[1]) - 1;
256: }
257:
258: static final long fEnd(int[] f) {
259: return f[0] - f[1] + 1;
260: }
261:
262: static final long fExt(long v, int[] f) {
263: return (v >> fEnd(f)) & fMask(f);
264: }
265:
266: final long makePageNo(long blk, long page) {
267: // we could mask here to "prevent" errors, but that really doesnt'
268: // help. We could range check 'blk' and 'page' but we want this
269: // fn to be fast, and hope we can be assured that the rest of the
270: // code ensures the invariants.
271: long ret = fIns(pageShift, PAGE_SHIFT)
272: //- //#ifdef PARANOID
273: //- | fIns(0xc, MAGIC)
274: //#endif
275: | fIns(page, PAGE_NUM) | fIns(blk, BLOCK_NUM);
276: //- //#ifdef PARANOID
277: //- if (fExt(ret, BLOCK_NUM) != blk) {
278: //- Debug.println("pageShift: " + pageShift + ": " +
279: //- fIns(pageShift, PAGE_SHIFT));
280: //- Debug.println("page: " + page + ": " +
281: //- fIns(page, PAGE_NUM));
282: //- Debug.println("block: " + blk + ": " +
283: //- fIns(blk, BLOCK_NUM));
284: //- Debug.println("============Bad blk: " + blk + ", " + page +
285: //- ", " + toString(ret));
286: //- }
287: //#endif
288: return ret;
289: }
290:
291: /**
292: * Return the number of the block that contains this page.
293: */
294: public static final long pageBlock(long page) {
295: //- //#ifdef PARANOID
296: //- checkPage(page);
297: //#endif
298: return fExt(page, BLOCK_NUM);
299: }
300:
301: //- //#ifdef PARANOID
302: //- static public void checkPage(long page) {
303: //- if (fExt(page, PAGE_SHIFT) != 0 &&
304: //- (fExt(page, MAGIC) != 0xc ||
305: //- (fExt(page, PAGE_NUM) >= (1 << fExt(page, PAGE_SHIFT))))) {
306: //- String s = "Page[ps:" + fExt(page, PAGE_SHIFT) +
307: //- " blk:" + fExt(page, BLOCK_NUM) +
308: //- " off:" + fExt(page, PAGE_NUM) + ']';
309: //- throw new RuntimeException("Bad page: " + s);
310: //- }
311: //- }
312: //#endif
313:
314: /**
315: * Return the byte offset of this page in the base block.
316: */
317: public final int pageOffset(long page) {
318: //- //#ifdef PARANOID
319: //- checkPage(page);
320: //#endif
321: return (int) (fExt(page, PAGE_NUM) * pageSize);
322: }
323:
324: /**
325: * Return the page shift for this page.
326: */
327: static final int pageShift(long page) {
328: //- //#ifdef PARANOID
329: //- checkPage(page);
330: //#endif
331: return (int) (fExt(page, PAGE_SHIFT));
332: }
333:
334: /**
335: * Return the specified page
336: */
337: public Page getPage(long block) throws IOException {
338: //- //#ifdef PARANOID
339: //- checkPage(block);
340: //#endif
341: return new SubPage(this , block);
342: }
343:
344: /**
345: * Return the (file) lock
346: */
347: public Object getLock() {
348: return file.getLock();
349: }
350:
351: /**
352: * Return this manager's block size
353: */
354: public final int getPageSize() {
355: return pageSize;
356: }
357:
358: /**
359: * Return a new input stream, reading from the region with the specified
360: * root block.
361: *
362: * @param block the root block of the region
363: * @return an InputStream bound to the region.
364: * @exception IOException if the block number isn't valid, or if another
365: * error is detected trying to access the region.
366: */
367: public RandomAccessInputStream getInputStream(long block)
368: throws IOException {
369: return new RandomAccessInputStream(getStream(block));
370: }
371:
372: /**
373: * Return a new output stream, writing to the region with the specified
374: * root block.
375: *
376: * @param block the root block of the region
377: * @return an OutputStream bound to the region.
378: * @exception IOException if the block number isn't valid, or if another
379: * error is detected trying to access the region.
380: */
381: public RandomAccessOutputStream getOutputStream(long block)
382: throws IOException {
383: return new RandomAccessOutputStream(getStream(block));
384: }
385:
386: public RandomAccess getStream(long blockRef) throws IOException {
387: return new BlockAccess(this , blockRef);
388: }
389:
390: /**
391: * Destroy the stream with the specified root page and free up the
392: * storage it was using.
393: *
394: * @param page the root page of the region
395: *
396: * @exception IOException if the page number isn't valid, or if another
397: * error is detected trying to access the region.
398: */
399: public void freeStream(long page) throws IOException {
400: synchronized (file.fileLock) {
401: getStream(page).resize(0);
402: freePage(page);
403: }
404: }
405:
406: //#ifdef DEBUG
407: /**
408: * Return a displayable representation for this object.
409: */
410: public String toString() {
411: return "PM" + pageSize + ":[" + rootBlock + "," + offset + "]";
412: }
413:
414: //#endif
415:
416: public static String toString(long page) {
417: int psize = 8192 >> pageShift(page);
418: long pnum = fExt(page, PAGE_NUM);
419: return "Page(" + psize + ")[" + pageBlock(page) + ":" + pnum
420: + " (" + (pnum * psize) + ")" + ']';
421: }
422: }
|