001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library is distributed in the hope that it will be useful,
012: but WITHOUT ANY WARRANTY; without even the implied warranty of
013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import java.util.*;
026: import java.io.*;
027: import com.go.trove.util.*;
028: import org.artsProject.mcop.*;
029: import drjava.util.*;
030: import drjava.gjutil.*;
031: import drjava.smyle.*;
032:
033: public class DefaultChunkManager extends MasterChunkManager {
034: static final int DEFAULT_NATURALFILESIZE = 64 * 1024,
035: MAXCACHESIZE = DEFAULT_NATURALFILESIZE;
036:
037: public static boolean debug = false, verbose = false,
038: COMPRESSION = false, fullStats = false,
039: localityOptimization = true;
040:
041: Disk disk;
042: int version;
043: ArrayList<Chunk> chunks0 = new ArrayList<Chunk>();
044: ArrayList<Chunk> newChunks0 = chunks0;
045: Disk.NewFile newFile[] = new Disk.NewFile[2];
046: Buffer newFileBuf[] = new Buffer[2];
047: boolean dirty = false;
048: ChunkRef masterChunk1 = NULLCHUNK;
049: int naturalFileSize = DEFAULT_NATURALFILESIZE;
050: boolean masterLoaded = false;
051: int firstEmptyChunk0 = 0;
052: Cache<Long, byte[]> fileCache = new Cache<Long, byte[]>(1);
053:
054: /** only needed during gc */
055: Set<FileRef> fileWhiteList = null;
056:
057: static final Chunk emptyChunk = new Chunk();
058: static final MarDemar<Chunk> chunkMarDemar = new TypeMarDemar<Chunk>(
059: Chunk.DEMARSHALLER);
060:
061: ChunkManager cm0 = new ChunkManager() {
062: public Buffer readChunk(int chunk) {
063: return decompress(readChunk0(chunk));
064: }
065:
066: public ChunkRef createChunk(Buffer data) {
067: return createChunk0(compress(data));
068: }
069: };
070:
071: ScalablePool<Chunk> chunks1 = new ScalablePool(chunkMarDemar, cm0,
072: null);
073: ChunkRef chunks1Ref;
074:
075: // stats
076: long[] lastAccessedFile = new long[2];
077: int[] chunksRead = new int[2], fileHops = new int[2];
078: Integer lastAccessedChunk = new Integer(0);
079: HashMap<Integer, Integer> accessSequence = new HashMap<Integer, Integer>();
080:
081: // full stats
082: TreeMap<Pair<Integer, Integer>, Integer> accessPairs;
083:
084: public DefaultChunkManager(Disk disk, int version) {
085: this .disk = disk;
086: this .version = version;
087: }
088:
089: public synchronized void setNaturalFileSize(int naturalFileSize) {
090: this .naturalFileSize = naturalFileSize;
091: }
092:
093: // accessors
094:
095: public synchronized Buffer readChunk(int index) {
096: return decompress(readChunk1(index));
097: }
098:
099: private Buffer readChunk1(int index) {
100: if (index <= 0)
101: throw new IllegalArgumentException(
102: "Invalid ChunkRef (index=" + index + ")");
103: Chunk chunk = chunks1.get(index - 1);
104: if (chunk == null)
105: throw new InternalSmyleError("Chunk " + index
106: + " doesn't exist anymore");
107:
108: if (localityOptimization
109: && index != lastAccessedChunk.intValue()) {
110: Integer c = new Integer(index);
111: accessSequence.put(lastAccessedChunk, c);
112:
113: if (fullStats) {
114: if (accessPairs == null)
115: accessPairs = new TreeMap<Pair<Integer, Integer>, Integer>();
116: Pair<Integer, Integer> p = new Pair(lastAccessedChunk,
117: c);
118: Integer I = accessPairs.get(p);
119: accessPairs.put(p, new Integer(I == null ? 1 : I
120: .intValue() + 1));
121: }
122:
123: lastAccessedChunk = c;
124: }
125:
126: return loadChunk(chunk, 1);
127: }
128:
129: private Buffer readChunk0(int index) {
130: return loadChunk(chunks0.get(index - 1), 0);
131: }
132:
133: private Buffer loadChunk(Chunk chunk, int i) {
134: chunksRead[i]++;
135: if (chunk.file != lastAccessedFile[i]) {
136: lastAccessedFile[i] = chunk.file;
137: fileHops[i]++;
138: }
139:
140: //System.out.println(chunk+", newFile="+(newFile != null ? newFile.getId() : 0));
141: try {
142: if (newFile[i] != null && chunk.file == newFile[i].getId())
143: // chunk is part of newFile
144: return new Buffer(newFileBuf[i], chunk.offset,
145: chunk.length);
146:
147: if (chunk.file == 0) {
148: throw new InternalSmyleError(
149: "Chunk doesn't exist anymore");
150: } else {
151: // look in cache
152: Long lFile = new Long(chunk.file);
153: byte[] data = fileCache.get(lFile);
154: if (data != null)
155: return new Buffer(data, chunk.offset, chunk.length);
156:
157: // read chunk from file
158: DataInputStream in = new DataInputStream(disk
159: .readFile(chunk.file));
160: //System.out.println("Reading file "+chunk.file);
161:
162: // store in cache if cacheable
163: int fileLen = disk.getFileLength(chunk.file);
164: if (fileLen <= MAXCACHESIZE) {
165: data = new byte[fileLen];
166: in.readFully(data);
167: in.close();
168: fileCache.put(lFile, data);
169: return new Buffer(data, chunk.offset, chunk.length);
170: } else {
171: // Not cacheable
172: in.skip(chunk.offset);
173: data = new byte[chunk.length];
174: in.readFully(data);
175: in.close();
176: return new Buffer(data, 0, chunk.length);
177: }
178: }
179: } catch (IOException e) {
180: throw new SmyleIOException(e);
181: }
182: }
183:
184: /** only needed for CompressionBench */
185: public synchronized Iterator<ChunkRef> chunks1() {
186: ArrayList<ChunkRef> l = new ArrayList<ChunkRef>();
187: for (int i = 1; i <= chunks1.size(); i++) {
188: if (chunks1.get(i - 1) != null)
189: l.add(new ChunkRef(i));
190: }
191: return l.iterator();
192: }
193:
194: public synchronized ChunkRef getMasterChunk() {
195: if (!masterLoaded) {
196: masterLoaded = true;
197: loadMaster();
198: }
199: return masterChunk1;
200: }
201:
202: // mutators
203:
204: private ChunkRef createChunk0(Buffer data) {
205: // reuse empty chunk index if possible
206: int index;
207: for (index = firstEmptyChunk0; index < newChunks0.size(); index++) {
208: if (newChunks0.get(index).file == 0) {
209: //System.out.println("Reusing chunk "+index);
210: break;
211: }
212: }
213:
214: firstEmptyChunk0 = index + 1;
215: saveChunk0(index + 1, data);
216: return new ChunkRef(index + 1);
217: }
218:
219: public synchronized ChunkRef createChunk(Buffer data) {
220: int index = chunks1.insert(new Chunk());
221: chunks1.replace(index, saveChunk(compress(data), 1));
222: return new ChunkRef(index + 1);
223: }
224:
225: void saveChunk0(int index, Buffer data) {
226: setOrAdd(newChunks0, index - 1, saveChunk(data, 0));
227: }
228:
229: void saveChunk1(int index, Buffer data) {
230: chunks1.replace(index - 1, saveChunk(data, 1));
231: }
232:
233: Chunk saveChunk(Buffer data, int i) {
234: dirty = true;
235: if (data.remaining() > naturalFileSize) {
236: // too large, needs a file of its own
237:
238: int len = data.remaining();
239: return new Chunk(DiskUtil.bufferToFile(disk, data).id, 0,
240: len);
241: } else {
242: // put in combined file
243:
244: if (newFile[i] != null
245: && newFileBuf[i].remaining() + data.remaining() > naturalFileSize) {
246: // need to flush newFile
247:
248: /*if (newFile != null)
249: System.out.println("Autosaving new file ("+newFile.remaining()+" bytes)");*/
250: saveNewFile(i);
251: }
252:
253: if (newFile[i] == null) {
254: newFile[i] = disk.createFile();
255: newFileBuf[i] = new Buffer();
256: }
257:
258: Chunk chunk = new Chunk(newFile[i].getId(), newFileBuf[i]
259: .remaining(), data.remaining());
260: newFileBuf[i].writeBuffer(data);
261: return chunk;
262: }
263: }
264:
265: static void setOrAdd(ArrayList<Chunk> v, int index, Chunk c) {
266: while (index > v.size())
267: v.add(emptyChunk);
268: if (index < v.size())
269: v.set(index, c);
270: else
271: v.add(c);
272: }
273:
274: Buffer compress(Buffer b) {
275: if (COMPRESSION) {
276: Buffer b2 = new Buffer();
277: Compression.compress(new Buffer(b), b2);
278: //System.out.println("Compressed "+b.remaining()+" "+b2.remaining());
279: return b2;
280: }
281: return b;
282: }
283:
284: Buffer decompress(Buffer b) {
285: if (version >= 293 && COMPRESSION) {
286: Buffer b2 = new Buffer();
287: Compression.decompress(new Buffer(b), b2);
288: //System.out.println("Decompressed "+b2.remaining()+" "+b.remaining());
289: return b2;
290: }
291: return b;
292: }
293:
294: void saveMaster() {
295: try {
296: Buffer b = new Buffer();
297: b.willWrite(chunks0.size() * 16 + 4 + 4);
298: /*System.out.println("Writing "+chunks0.size()+"-"+emptyChunks(chunks0)
299: +" chunks to master");*/
300: writeChunkSeq(b, chunks0);
301: chunks1Ref.marshal(b);
302: masterChunk1.writeType(b);
303:
304: if (debug) {
305: System.out.println("Size of master buffer: "
306: + b.remaining() + " (" + emptyChunks1()
307: + " empty chunks out of " + chunks1.size()
308: + ")");
309: }
310:
311: Buffer b2 = new Buffer();
312: b2.writeLong(version);
313: //Buffer bb = new Buffer(b);
314: if (COMPRESSION)
315: Compression.compress(b, b2);
316: else
317: b2.writeBuffer(b);
318: //System.out.println(bb+" -> "+b2);
319: disk.saveMaster(b2);
320: } catch (SmyleIOException e) {
321: // If master write failed, reload master to cleanly undo changes
322: loadMaster();
323: throw e;
324: }
325: }
326:
327: void loadMaster() {
328: long master = disk.getMasterFile();
329: if (master != 0) {
330: Buffer b = DiskUtil.fileToBuffer(disk, master);
331: b.readLong(); // version
332: //Buffer b2 = b;
333: b = decompress(b);
334: //System.out.println(b2+" -> "+b);
335: chunks0.clear();
336: firstEmptyChunk0 = 0;
337: readChunkSeq(b, chunks0);
338: chunks1 = new ScalablePool(chunkMarDemar, cm0,
339: new ChunkRef(b));
340: masterChunk1 = new ChunkRef(b);
341: accessSequence.clear();
342: }
343: }
344:
345: private void writeChunkSeq(Buffer b, List<Chunk> chunks) {
346: b.writeLong(chunks.size());
347: for (int i = 0; i < chunks.size(); i += 32) {
348: int val = 0;
349: for (int j = 0; j < 32 && i + j < chunks.size(); j++)
350: if (!chunks.get(i + j).equals(emptyChunk))
351: val |= 1 << j;
352: b.writeLong(val);
353: for (int j = 0; j < 32 && i + j < chunks.size(); j++)
354: if (!chunks.get(i + j).equals(emptyChunk))
355: chunks.get(i + j).marshal(b);
356: }
357: }
358:
359: private void readChunkSeq(Buffer b, List<Chunk> chunks) {
360: int n = b.readLong();
361: for (int i = 0; i < n; i += 32) {
362: int val = b.readLong();
363: for (int j = 0; j < 32 && i + j < n; j++)
364: if ((val & (1 << j)) != 0)
365: chunks.add(new Chunk(b));
366: else
367: chunks.add(emptyChunk);
368: }
369: }
370:
371: public synchronized ChunkRef createMasterChunk(Buffer data) {
372: masterChunk1 = createChunk(data);
373: flush();
374: return masterChunk1;
375: }
376:
377: void saveNewFile(int i) {
378: if (newFile[i] != null) {
379: DiskUtil.bufferToFile(newFile[i], newFileBuf[i]);
380: if (fileWhiteList != null)
381: fileWhiteList.add(new FileRef(newFile[i].getId()));
382:
383: newFile[i] = null;
384: newFileBuf[i] = null;
385: }
386: }
387:
388: public synchronized void flush() {
389: if (dirty) {
390: saveChunks1();
391: saveNewFile(0);
392: saveNewFile(1);
393: saveMaster();
394: dirty = false;
395: }
396: }
397:
398: private boolean chunkInSmallFile(HashSet<FileRef> fileWhiteList,
399: HashSet<FileRef> sizeChecked, Chunk chunk) {
400: if (chunk.file > 0) {
401: FileRef fr = new FileRef(chunk.file);
402: if (fileWhiteList.contains(fr) && !sizeChecked.contains(fr)) {
403: sizeChecked.add(fr);
404: if ((newFile[0] == null || fr.id != newFile[0].getId())
405: && (newFile[1] == null || fr.id != newFile[1]
406: .getId())
407: && disk.getFileLength(fr.id) <= naturalFileSize / 2)
408: return true;
409: }
410: }
411: return false;
412: }
413:
414: private void genNewChunks0() {
415: newChunks0 = new ArrayList<Chunk>();
416: firstEmptyChunk0 = 0;
417: BitSet chunks0WhiteList = new BitSet();
418: chunks1.collectChunks(chunks0WhiteList);
419: int len0 = chunks0.size() + 1, retained0 = 0, dropped0 = 0;
420: for (int index = 1; index < len0; index++) {
421: if (chunks0WhiteList.get(index)) {
422: Chunk chunk = chunks0.get(index - 1);
423: fileWhiteList.add(new FileRef(chunk.file));
424: setOrAdd(newChunks0, index - 1, chunk);
425: ++retained0;
426: } else if (chunks0.get(index - 1).file != 0)
427: ++dropped0;
428: }
429: /*System.out.println("0-chunks retained: "+retained0+"/"+(len0-1)
430: +", dropped: "+dropped0+", empty: "
431: +emptyChunks(chunks0)+"->"+emptyChunks(newChunks0));*/
432: }
433:
434: public synchronized void deleteEverythingBut(
435: final BitSet chunks1WhiteList) {
436: new Benchmark() {
437: protected void action() {
438: HashSet<FileRef> fileWhiteList = new HashSet<FileRef>();
439: // make sure newly created files are added to list
440: DefaultChunkManager.this .fileWhiteList = fileWhiteList;
441:
442: HashSet<FileRef> relocationList = new HashSet<FileRef>();
443: HashSet<FileRef> sizeChecked = new HashSet<FileRef>();
444:
445: // release obsolete 1-chunks, add application chunks to fileWhiteList
446:
447: int len1 = chunks1.size() + 1;
448: //System.out.println("whiteList: "+whiteList+", l="+len);
449: for (int index = 1; index < len1; index++) {
450: boolean relocate = false;
451: Chunk chunk = chunks1.get(index - 1);
452: if (chunk != null) {
453: fileWhiteList.add(new FileRef(chunk.file));
454: if (chunks1WhiteList.get(index)) {
455: if (chunkInSmallFile(fileWhiteList,
456: sizeChecked, chunk))
457: relocate = true;
458: } else {
459: chunks1.release(index - 1);
460: relocate = true;
461: }
462:
463: if (relocate) {
464: FileRef fr = new FileRef(chunk.file);
465: if (fileWhiteList.contains(fr)) {
466: relocationList.add(fr);
467: fileWhiteList.remove(fr);
468: }
469: }
470: }
471: }
472: done("chunks1");
473: dirty = true;
474: flush();
475: done("flush");
476:
477: // generate newChunks0 and add to fileWhiteList
478:
479: genNewChunks0();
480: done("genNewChunks0");
481:
482: // continue filling relocationList
483: // (files with obsolete chunks and small files)
484:
485: // 0-chunks
486: for (int i = 0; i < chunks0.size(); i++) {
487: Chunk chunk = chunks0.get(i);
488: if (i >= newChunks0.size()
489: || newChunks0.get(i).file == 0
490: || chunkInSmallFile(fileWhiteList,
491: sizeChecked, chunk)) {
492: FileRef fr = new FileRef(chunk.file);
493: if (fileWhiteList.contains(fr)) {
494: relocationList.add(fr);
495: fileWhiteList.remove(fr);
496: }
497: }
498: }
499: done("fill relocation list");
500:
501: // relocate chunks0 and chunks1
502:
503: if (!relocationList.isEmpty()) {
504:
505: for (int i = 0; i < newChunks0.size(); i++) {
506: Chunk chunk = newChunks0.get(i);
507: if (chunk.file != 0
508: && relocationList.contains(new FileRef(
509: chunk.file))) {
510: //System.out.println("Relocating chunk "+i+" of file "+chunk.file);
511: saveChunk0(i + 1, readChunk0(i + 1));
512: }
513: }
514:
515: chunks0 = newChunks0;
516: done("relocate chunks0");
517:
518: relocateChunks1(relocationList);
519: if (verbose)
520: System.out.println("Relocated "
521: + relocationList.size() + " files");
522:
523: done("relocate chunks1");
524: saveChunks1();
525: done("saveChunks1");
526: genNewChunks0();
527: done("genNewChunks0");
528: }
529:
530: chunks0 = newChunks0;
531:
532: // save master and add it to file list
533:
534: flushAndDeleteFiles();
535: done("disk.deleteEverythingBut");
536: }
537: }.run/*AndPrint*/();
538: }
539:
540: private void flushAndDeleteFiles() {
541: dirty = true;
542: flush();
543: fileWhiteList.add(new FileRef(disk.getMasterFile()));
544:
545: accessSequence.clear();
546:
547: // remove garbage files
548:
549: if (verbose)
550: System.out.println("Retaining " + fileWhiteList.size()
551: + " files");
552: disk.deleteEverythingBut(fileWhiteList);
553: fileWhiteList = null;
554: }
555:
556: private void relocateChunks1(HashSet<FileRef> relocationList) {
557: for (int i = 1; i <= chunks1.size(); i++) {
558: int j = i;
559: Chunk chunk;
560: while ((chunk = chunks1.get(j - 1)) != null
561: && relocationList.contains(new FileRef(chunk.file))) {
562: //System.out.println("Relocating chunk "+j+" of file "+chunk.file);
563: saveChunk1(j, readChunk1(j));
564: if (localityOptimization) {
565: Integer J = accessSequence.get(new Integer(j));
566: if (J != null)
567: j = J.intValue();
568: else
569: break;
570: } else
571: break;
572: }
573: }
574: }
575:
576: private void relocateChunks1() {
577: BitSet relocated = new BitSet();
578: for (int i = 1; i <= chunks1.size(); i++) {
579: int j = i;
580: Chunk chunk;
581: while ((chunk = chunks1.get(j - 1)) != null
582: && !relocated.get(j)) {
583: //System.out.println("Relocating chunk "+j+" of file "+chunk.file);
584: saveChunk1(j, readChunk1(j));
585: relocated.set(j);
586: Integer J = accessSequence.get(new Integer(j));
587: if (J != null)
588: j = J.intValue();
589: else
590: break;
591: }
592: }
593: }
594:
595: public synchronized void reorderAllChunks() {
596: fileWhiteList = new HashSet<FileRef>();
597: relocateChunks1();
598: saveChunks1();
599: genNewChunks0();
600: chunks0 = newChunks0;
601: flushAndDeleteFiles();
602: }
603:
604: public synchronized int numChunks() {
605: return chunks1.size() - emptyChunks1();
606: }
607:
608: private int emptyChunks(List<Chunk> l) {
609: int n = 0;
610: for (int i = 0; i < l.size(); i++)
611: if (l.get(i).equals(emptyChunk))
612: n++;
613: return n;
614: }
615:
616: private int emptyChunks1() {
617: int emptyChunks = 0;
618: for (int i = 0; i < chunks1.size(); i++)
619: if (chunks1.get(i) == null)
620: ++emptyChunks;
621: return emptyChunks;
622: }
623:
624: private void saveChunks1() {
625: chunks1Ref = chunks1.flush();
626: }
627:
628: public synchronized String getStats() {
629: long hard = 0, soft = 0;
630: hard += chunks0.size() * 4;
631: for (int i = 0; i < chunks0.size(); i++)
632: if (chunks0.get(i) != emptyChunk)
633: hard += 16;
634: if (newFileBuf[0] != null)
635: hard += newFileBuf[0].remaining();
636: if (newFileBuf[1] != null)
637: hard += newFileBuf[1].remaining();
638:
639: {
640: Iterator<byte[]> i = fileCache.values().iterator();
641: if (i.hasNext()) {
642: hard += i.next().length; // one of the values is hard referenced - just pretend it's this one
643: while (i.hasNext())
644: soft += i.next().length;
645: }
646: }
647:
648: String result = "Hard cached data: "
649: + hard
650: + ", soft cached data: "
651: + soft
652: + "\n0-chunks read: "
653: + chunksRead[0]
654: + ", file hops: "
655: + fileHops[0]
656: + (chunksRead[0] != 0 ? " ("
657: + (fileHops[0] * 100L / chunksRead[0]) + "%)"
658: : "")
659: + "\n1-chunks read: "
660: + chunksRead[1]
661: + ", file hops: "
662: + fileHops[1]
663: + (chunksRead[1] != 0 ? " ("
664: + (fileHops[1] * 100L / chunksRead[1]) + "%)"
665: : "") + ", access sequence pairs: "
666: + accessSequence.size();
667:
668: if (fullStats && accessPairs != null) {
669: StringBuffer buf = new StringBuffer();
670: for (Iterator<Map.Entry<Pair<Integer, Integer>, Integer>> i = accessPairs
671: .entrySet().iterator(); i.hasNext();) {
672: Map.Entry<Pair<Integer, Integer>, Integer> e = i.next();
673: buf.append('\n').append(e.getKey().a()).append('>')
674: .append(e.getKey().b()).append(": ").append(
675: e.getValue());
676: }
677: result += buf;
678: }
679:
680: return result;
681: }
682: }
|