Commit | Line | Data |
---|---|---|
a52fde77 AM |
1 | /******************************************************************************* |
2 | * Copyright (c) 2012 Ericsson | |
3 | * Copyright (c) 2010, 2011 École Polytechnique de Montréal | |
4 | * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> | |
6f4e8ec0 | 5 | * |
a52fde77 AM |
6 | * All rights reserved. This program and the accompanying materials are |
7 | * made available under the terms of the Eclipse Public License v1.0 which | |
8 | * accompanies this distribution, and is available at | |
9 | * http://www.eclipse.org/legal/epl-v10.html | |
6f4e8ec0 | 10 | * |
a52fde77 AM |
11 | *******************************************************************************/ |
12 | ||
2ab9afbc | 13 | package org.eclipse.linuxtools.internal.tmf.core.statesystem.historytree; |
a52fde77 AM |
14 | |
15 | import java.io.IOException; | |
16 | import java.io.PrintWriter; | |
17 | import java.nio.ByteBuffer; | |
18 | import java.nio.ByteOrder; | |
19 | import java.nio.channels.FileChannel; | |
20 | import java.util.ArrayList; | |
21 | import java.util.Collections; | |
22 | import java.util.List; | |
23 | ||
6d08acca | 24 | import org.eclipse.linuxtools.tmf.core.exceptions.TimeRangeException; |
a52fde77 | 25 | import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; |
a52fde77 AM |
26 | import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; |
27 | ||
28 | /** | |
29 | * The base class for all the types of nodes that go in the History Tree. | |
6f4e8ec0 | 30 | * |
a52fde77 | 31 | * @author alexmont |
6f4e8ec0 | 32 | * |
a52fde77 AM |
33 | */ |
34 | abstract class HTNode { | |
35 | ||
36 | /* Reference to the History Tree to whom this node belongs */ | |
37 | protected final HistoryTree ownerTree; | |
38 | ||
39 | /* Time range of this node */ | |
40 | private final long nodeStart; | |
41 | private long nodeEnd; | |
42 | ||
43 | /* Sequence number = position in the node section of the file */ | |
44 | private final int sequenceNumber; | |
45 | private int parentSequenceNumber; /* = -1 if this node is the root node */ | |
46 | ||
47 | /* Where the Strings section begins (from the start of the node */ | |
48 | private int stringSectionOffset; | |
49 | ||
50 | /* True if this node is closed (and to be committed to disk) */ | |
51 | private boolean isDone; | |
52 | ||
53 | /* Vector containing all the intervals contained in this node */ | |
54 | private final ArrayList<HTInterval> intervals; | |
55 | ||
56 | HTNode(HistoryTree tree, int seqNumber, int parentSeqNumber, long start) { | |
57 | this.ownerTree = tree; | |
58 | this.nodeStart = start; | |
59 | this.sequenceNumber = seqNumber; | |
60 | this.parentSequenceNumber = parentSeqNumber; | |
61 | ||
62 | this.stringSectionOffset = ownerTree.config.blockSize; | |
63 | this.isDone = false; | |
64 | this.intervals = new ArrayList<HTInterval>(); | |
65 | } | |
66 | ||
67 | /** | |
68 | * Reader factory constructor. Build a Node object (of the right type) by | |
69 | * reading a block in the file. | |
6f4e8ec0 | 70 | * |
a52fde77 AM |
71 | * @param tree |
72 | * Reference to the HT which will own this node | |
73 | * @param fc | |
74 | * FileChannel to the history file, ALREADY SEEKED at the start | |
75 | * of the node. | |
76 | * @throws IOException | |
77 | */ | |
78 | final static HTNode readNode(HistoryTree tree, FileChannel fc) | |
79 | throws IOException { | |
80 | HTNode newNode = null; | |
81 | int res, i; | |
82 | ||
83 | ByteBuffer buffer = ByteBuffer.allocate(tree.config.blockSize); | |
84 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
85 | buffer.clear(); | |
86 | res = fc.read(buffer); | |
87 | assert (res == tree.config.blockSize); | |
88 | // This often breaks, so might as well keep this code not too far... | |
89 | // if ( res != tree.config.blockSize ) { | |
90 | // tree.debugPrintFullTree(new PrintWriter(System.out, true), null, | |
91 | // false); | |
92 | // assert ( false ); | |
93 | // } | |
94 | buffer.flip(); | |
95 | ||
96 | /* Read the common header part */ | |
97 | byte type = buffer.get(); | |
98 | long start = buffer.getLong(); | |
99 | long end = buffer.getLong(); | |
100 | int seqNb = buffer.getInt(); | |
101 | int parentSeqNb = buffer.getInt(); | |
102 | int intervalCount = buffer.getInt(); | |
103 | int stringSectionOffset = buffer.getInt(); | |
104 | boolean done = byteToBool(buffer.get()); | |
105 | ||
106 | /* Now the rest of the header depends on the node type */ | |
107 | switch (type) { | |
108 | case 1: | |
109 | /* Core nodes */ | |
110 | newNode = new CoreNode(tree, seqNb, parentSeqNb, start); | |
111 | newNode.readSpecificHeader(buffer); | |
112 | break; | |
113 | ||
114 | // TODO implement other node types | |
115 | // case 2: | |
116 | // /* Leaf nodes */ | |
117 | // | |
118 | // break; | |
119 | // | |
120 | // | |
121 | // case 3: | |
122 | // /* "Claudette" (extended) nodes */ | |
123 | // | |
124 | // break; | |
125 | ||
126 | default: | |
127 | /* Unrecognized node type */ | |
128 | throw new IOException(); | |
129 | } | |
130 | ||
131 | /* | |
132 | * At this point, we should be done reading the header and 'buffer' | |
133 | * should only have the intervals left | |
134 | */ | |
135 | for (i = 0; i < intervalCount; i++) { | |
136 | newNode.intervals.add(HTInterval.readFrom(buffer)); | |
137 | } | |
138 | ||
139 | /* Assign the node's other information we have read previously */ | |
140 | newNode.nodeEnd = end; | |
141 | newNode.stringSectionOffset = stringSectionOffset; | |
142 | newNode.isDone = done; | |
143 | ||
144 | return newNode; | |
145 | } | |
146 | ||
147 | final void writeSelf(FileChannel fc) throws IOException { | |
148 | int res, size; | |
149 | int curStringsEntryEndPos = ownerTree.config.blockSize; | |
150 | ||
151 | ByteBuffer buffer = ByteBuffer.allocate(ownerTree.config.blockSize); | |
152 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
153 | buffer.clear(); | |
154 | ||
155 | /* Write the common header part */ | |
156 | buffer.put(this.getNodeType()); | |
157 | buffer.putLong(nodeStart); | |
158 | buffer.putLong(nodeEnd); | |
159 | buffer.putInt(sequenceNumber); | |
160 | buffer.putInt(parentSequenceNumber); | |
161 | buffer.putInt(intervals.size()); | |
162 | buffer.putInt(stringSectionOffset); | |
163 | buffer.put(boolToByte(isDone)); | |
164 | ||
165 | /* Now call the inner method to write the specific header part */ | |
166 | this.writeSpecificHeader(buffer); | |
167 | ||
168 | /* Back to us, we write the intervals */ | |
169 | for (HTInterval interval : intervals) { | |
170 | size = interval.writeInterval(buffer, curStringsEntryEndPos); | |
171 | curStringsEntryEndPos -= size; | |
172 | } | |
173 | ||
174 | /* | |
175 | * Write padding between the end of the Data section and the start of | |
176 | * the Strings section (needed to fill the node in case there is no | |
177 | * Strings section) | |
178 | */ | |
179 | while (buffer.position() < stringSectionOffset) { | |
180 | buffer.put((byte) 0); | |
181 | } | |
182 | ||
183 | /* | |
184 | * If the offsets were right, the size of the Strings section should be | |
185 | * == to the expected size | |
186 | */ | |
187 | assert (curStringsEntryEndPos == stringSectionOffset); | |
188 | ||
189 | /* Finally, write everything in the Buffer to disk */ | |
190 | ||
191 | // if we don't do this, flip() will lose what's after. | |
192 | buffer.position(ownerTree.config.blockSize); | |
193 | ||
194 | buffer.flip(); | |
195 | res = fc.write(buffer); | |
196 | assert (res == ownerTree.config.blockSize); | |
197 | } | |
198 | ||
199 | /** | |
200 | * Accessors | |
201 | */ | |
202 | long getNodeStart() { | |
203 | return nodeStart; | |
204 | } | |
205 | ||
206 | long getNodeEnd() { | |
207 | if (this.isDone) { | |
208 | return nodeEnd; | |
209 | } | |
210 | return 0; | |
211 | } | |
212 | ||
213 | int getSequenceNumber() { | |
214 | return sequenceNumber; | |
215 | } | |
216 | ||
217 | int getParentSequenceNumber() { | |
218 | return parentSequenceNumber; | |
219 | } | |
220 | ||
221 | /** | |
222 | * Change this node's parent. Used when we create a new root node for | |
223 | * example. | |
224 | */ | |
225 | void setParentSequenceNumber(int newParent) { | |
226 | parentSequenceNumber = newParent; | |
227 | } | |
228 | ||
229 | boolean isDone() { | |
230 | return isDone; | |
231 | } | |
232 | ||
233 | /** | |
234 | * Add an interval to this node | |
6f4e8ec0 | 235 | * |
a52fde77 AM |
236 | * @param newInterval |
237 | */ | |
238 | void addInterval(HTInterval newInterval) { | |
239 | /* Just in case, but should be checked before even calling this function */ | |
240 | assert (newInterval.getIntervalSize() <= this.getNodeFreeSpace()); | |
241 | ||
242 | intervals.add(newInterval); | |
243 | ||
244 | /* Update the in-node offset "pointer" */ | |
245 | stringSectionOffset -= (newInterval.getStringsEntrySize()); | |
246 | } | |
247 | ||
248 | /** | |
249 | * We've received word from the containerTree that newest nodes now exist to | |
250 | * our right. (Puts isDone = true and sets the endtime) | |
6f4e8ec0 | 251 | * |
a52fde77 AM |
252 | * @param endtime |
253 | * The nodeEnd time that the node will have | |
254 | * @throws TimeRangeException | |
255 | */ | |
256 | void closeThisNode(long endtime) { | |
257 | assert (endtime >= this.nodeStart); | |
258 | // /* This also breaks often too */ | |
259 | // if ( endtime.getValue() <= this.nodeStart.getValue() ) { | |
260 | // ownerTree.debugPrintFullTree(new PrintWriter(System.out, true), null, | |
261 | // false); | |
262 | // assert ( false ); | |
263 | // } | |
264 | ||
265 | if (intervals.size() > 0) { | |
266 | /* | |
267 | * Sort the intervals by ascending order of their end time. This | |
268 | * speeds up lookups a bit | |
269 | */ | |
270 | Collections.sort(intervals); | |
271 | ||
272 | /* | |
273 | * Make sure there are no intervals in this node with their EndTime | |
274 | * > the one requested. Only need to check the last one since they | |
275 | * are now sorted | |
276 | */ | |
277 | assert (endtime >= intervals.get(intervals.size() - 1).getEndTime()); | |
278 | } | |
279 | ||
280 | this.isDone = true; | |
281 | this.nodeEnd = endtime; | |
282 | return; | |
283 | } | |
284 | ||
285 | /** | |
286 | * The method to fill up the stateInfo (passed on from the Current State | |
287 | * Tree when it does a query on the SHT). We'll replace the data in that | |
288 | * vector with whatever relevant we can find from this node | |
6f4e8ec0 | 289 | * |
a52fde77 AM |
290 | * @param stateInfo |
291 | * The same stateInfo that comes from SHT's doQuery() | |
292 | * @param t | |
293 | * The timestamp for which the query is for. Only return | |
294 | * intervals that intersect t. | |
295 | * @throws TimeRangeException | |
296 | */ | |
297 | void writeInfoFromNode(List<ITmfStateInterval> stateInfo, long t) | |
298 | throws TimeRangeException { | |
299 | assert (this.isDone); // not sure this will always be the case... | |
300 | int startIndex; | |
301 | ||
302 | if (intervals.size() == 0) { | |
303 | return; | |
304 | } | |
305 | startIndex = getStartIndexFor(t); | |
306 | ||
307 | for (int i = startIndex; i < intervals.size(); i++) { | |
308 | /* | |
309 | * Now we only have to compare the Start times, since we now the End | |
310 | * times necessarily fit | |
311 | */ | |
312 | if (intervals.get(i).getStartTime() <= t) { | |
313 | stateInfo.set(intervals.get(i).getAttribute(), intervals.get(i)); | |
314 | } | |
315 | } | |
316 | return; | |
317 | } | |
318 | ||
319 | /** | |
320 | * Get a single Interval from the information in this node If the | |
321 | * key/timestamp pair cannot be found, we return null. | |
6f4e8ec0 | 322 | * |
a52fde77 AM |
323 | * @param key |
324 | * @param t | |
325 | * @return The Interval containing the information we want, or null if it | |
326 | * wasn't found | |
327 | * @throws TimeRangeException | |
328 | */ | |
329 | HTInterval getRelevantInterval(int key, long t) throws TimeRangeException { | |
330 | assert (this.isDone); | |
331 | int startIndex; | |
1d3d1293 | 332 | HTInterval curInterval; |
a52fde77 AM |
333 | |
334 | if (intervals.size() == 0) { | |
335 | return null; | |
336 | } | |
337 | ||
338 | startIndex = getStartIndexFor(t); | |
339 | ||
340 | for (int i = startIndex; i < intervals.size(); i++) { | |
1d3d1293 AM |
341 | curInterval = intervals.get(i); |
342 | if (curInterval.getAttribute() == key | |
343 | && curInterval.getStartTime() <= t | |
344 | && curInterval.getEndTime() >= t) { | |
345 | return curInterval; | |
a52fde77 AM |
346 | } |
347 | } | |
348 | /* We didn't find the relevant information in this node */ | |
349 | return null; | |
350 | } | |
351 | ||
352 | private int getStartIndexFor(long t) throws TimeRangeException { | |
353 | HTInterval dummy; | |
354 | int index; | |
355 | ||
356 | /* | |
357 | * Since the intervals are sorted by end time, we can skip all the ones | |
358 | * at the beginning whose end times are smaller than 't'. Java does | |
359 | * provides a .binarySearch method, but its API is quite weird... | |
360 | */ | |
361 | dummy = new HTInterval(0, t, 0, TmfStateValue.nullValue()); | |
362 | index = Collections.binarySearch(intervals, dummy); | |
363 | ||
364 | if (index < 0) { | |
365 | /* | |
366 | * .binarySearch returns a negative number if the exact value was | |
367 | * not found. Here we just want to know where to start searching, we | |
368 | * don't care if the value is exact or not. | |
369 | */ | |
370 | index = -index - 1; | |
371 | ||
372 | } | |
373 | ||
374 | /* Sometimes binarySearch yields weird stuff... */ | |
375 | if (index < 0) { | |
376 | index = 0; | |
377 | } | |
378 | if (index >= intervals.size()) { | |
379 | index = intervals.size() - 1; | |
380 | } | |
381 | ||
382 | /* | |
383 | * Another API quirkiness, the returned index is the one of the *last* | |
384 | * element of a series of equal endtimes, which happens sometimes. We | |
385 | * want the *first* element of such a series, to read through them | |
386 | * again. | |
387 | */ | |
388 | while (index > 0 | |
389 | && intervals.get(index - 1).compareTo(intervals.get(index)) == 0) { | |
390 | index--; | |
391 | } | |
392 | // FIXME F*ck all this, just do our own binary search in a saner way... | |
393 | ||
394 | // //checks to make sure startIndex works how I think it does | |
395 | // if ( startIndex > 0 ) { assert ( intervals.get(startIndex-1).getEnd() | |
396 | // < t ); } | |
397 | // assert ( intervals.get(startIndex).getEnd() >= t ); | |
398 | // if ( startIndex < intervals.size()-1 ) { assert ( | |
399 | // intervals.get(startIndex+1).getEnd() >= t ); } | |
400 | ||
401 | return index; | |
402 | } | |
403 | ||
404 | /** | |
405 | * @return The offset, within the node, where the Data section ends | |
406 | */ | |
407 | private int getDataSectionEndOffset() { | |
408 | return this.getTotalHeaderSize() + HTNode.getDataEntrySize() | |
409 | * intervals.size(); | |
410 | } | |
411 | ||
412 | /** | |
413 | * Returns the free space in the node, which is simply put, the | |
414 | * stringSectionOffset - dataSectionOffset | |
415 | */ | |
416 | int getNodeFreeSpace() { | |
417 | return stringSectionOffset - this.getDataSectionEndOffset(); | |
418 | } | |
419 | ||
420 | /** | |
421 | * Returns the current space utilisation of this node, as a percentage. | |
422 | * (used space / total usable space, which excludes the header) | |
423 | */ | |
424 | long getNodeUsagePRC() { | |
425 | float freePercent = (float) this.getNodeFreeSpace() | |
426 | / (float) (ownerTree.config.blockSize - this.getTotalHeaderSize()) | |
427 | * 100f; | |
428 | return (long) (100L - freePercent); | |
429 | } | |
430 | ||
431 | protected final static int getDataEntrySize() { | |
432 | return 16 /* 2 x Timevalue/long (interval start + end) */ | |
433 | + 4 /* int (key) */ | |
434 | + 1 /* byte (type) */ | |
435 | + 4; /* int (valueOffset) */ | |
436 | /* = 25 */ | |
437 | } | |
438 | ||
439 | protected final static byte boolToByte(boolean thebool) { | |
440 | if (thebool) { | |
441 | return (byte) 1; | |
442 | } | |
443 | return (byte) 0; | |
444 | } | |
445 | ||
446 | final static boolean byteToBool(byte thebyte) { | |
447 | return (thebyte == (byte) 1); | |
448 | } | |
449 | ||
450 | /** | |
451 | * @name Debugging functions | |
452 | */ | |
453 | ||
454 | @SuppressWarnings("nls") | |
455 | @Override | |
456 | public String toString() { | |
457 | /* Only used for debugging, shouldn't be externalized */ | |
458 | StringBuffer buf = new StringBuffer("Node #" + sequenceNumber + ", "); | |
459 | buf.append(this.toStringSpecific()); | |
460 | buf.append(intervals.size() + " intervals (" + this.getNodeUsagePRC() | |
461 | + "% used), "); | |
462 | ||
463 | buf.append("[" + this.nodeStart + " - "); | |
464 | if (this.isDone) { | |
465 | buf = buf.append("" + this.nodeEnd + "]"); | |
466 | } else { | |
467 | buf = buf.append("...]"); | |
468 | } | |
469 | return buf.toString(); | |
470 | } | |
471 | ||
472 | /** | |
473 | * Debugging function that prints out the contents of this node | |
6f4e8ec0 | 474 | * |
a52fde77 AM |
475 | * @param writer |
476 | * PrintWriter in which we will print the debug output | |
477 | */ | |
478 | @SuppressWarnings("nls") | |
479 | void debugPrintIntervals(PrintWriter writer) { | |
480 | /* Only used for debugging, shouldn't be externalized */ | |
481 | writer.println("Node #" + sequenceNumber + ":"); | |
482 | ||
483 | /* Array of children */ | |
484 | if (this.getNodeType() == 1) { /* Only Core Nodes can have children */ | |
485 | CoreNode thisNode = (CoreNode) this; | |
486 | writer.print(" " + thisNode.getNbChildren() + " children"); | |
487 | if (thisNode.getNbChildren() >= 1) { | |
488 | writer.print(": [ " + thisNode.getChild(0)); | |
489 | for (int i = 1; i < thisNode.getNbChildren(); i++) { | |
490 | writer.print(", " + thisNode.getChild(i)); | |
491 | } | |
492 | writer.print(']'); | |
493 | } | |
494 | writer.print('\n'); | |
495 | } | |
496 | ||
497 | /* List of intervals in the node */ | |
498 | writer.println(" Intervals contained:"); | |
499 | for (int i = 0; i < intervals.size(); i++) { | |
500 | writer.println(intervals.get(i).toString()); | |
501 | } | |
502 | writer.println('\n'); | |
503 | } | |
504 | ||
505 | final static int getCommonHeaderSize() { | |
506 | /* | |
507 | * 1 - byte (type) | |
6f4e8ec0 | 508 | * |
a52fde77 | 509 | * 16 - 2x long (start time, end time) |
6f4e8ec0 | 510 | * |
a52fde77 AM |
511 | * 16 - 4x int (seq number, parent seq number, intervalcount, strings |
512 | * section pos.) | |
6f4e8ec0 | 513 | * |
a52fde77 AM |
514 | * 1 - byte (done or not) |
515 | */ | |
516 | return 34; | |
517 | } | |
518 | ||
6f4e8ec0 AM |
519 | // ------------------------------------------------------------------------ |
520 | // Abstract methods | |
521 | // ------------------------------------------------------------------------ | |
a52fde77 AM |
522 | |
523 | protected abstract byte getNodeType(); | |
524 | ||
525 | protected abstract int getTotalHeaderSize(); | |
526 | ||
527 | protected abstract void readSpecificHeader(ByteBuffer buffer); | |
528 | ||
529 | protected abstract void writeSpecificHeader(ByteBuffer buffer); | |
530 | ||
531 | protected abstract String toStringSpecific(); | |
532 | } |