| 1 | /******************************************************************************* |
| 2 | * Copyright (c) 2012 Ericsson |
| 3 | * |
| 4 | * All rights reserved. This program and the accompanying materials are made |
| 5 | * available under the terms of the Eclipse Public License v1.0 which |
| 6 | * accompanies this distribution, and is available at |
| 7 | * http://www.eclipse.org/legal/epl-v10.html |
| 8 | * |
| 9 | * Contributors: Matthew Khouzam - Initial API and implementation |
| 10 | *******************************************************************************/ |
| 11 | package org.eclipse.linuxtools.tmf.core.ctfadaptor; |
| 12 | |
| 13 | import java.util.ArrayList; |
| 14 | import java.util.HashMap; |
| 15 | import java.util.Random; |
| 16 | |
| 17 | /** |
| 18 | * Ctf Iterator Manager, allows mapping of iterators (a limited resource) to |
| 19 | * contexts (many many resources). |
| 20 | * |
| 21 | * @author Matthew Khouzam |
| 22 | * @version 1.0 |
| 23 | * @since 1.1 |
| 24 | */ |
| 25 | public abstract class CtfIteratorManager { |
| 26 | /* |
| 27 | * A side note synchronized works on the whole object, Therefore add and |
| 28 | * remove will be thread safe. |
| 29 | */ |
| 30 | |
| 31 | /* |
| 32 | * The map of traces to trace managers. |
| 33 | */ |
| 34 | private static HashMap<CtfTmfTrace, CtfTraceManager> map = new HashMap<CtfTmfTrace, CtfTraceManager>(); |
| 35 | |
| 36 | /** |
| 37 | * Registers a trace to the iterator manager, the trace can now get |
| 38 | * iterators. |
| 39 | * |
| 40 | * @param trace |
| 41 | * the trace to register. |
| 42 | */ |
| 43 | public static synchronized void addTrace(final CtfTmfTrace trace) { |
| 44 | map.put(trace, new CtfTraceManager(trace)); |
| 45 | } |
| 46 | |
| 47 | /** |
| 48 | * Removes a trace to the iterator manager. |
| 49 | * |
| 50 | * @param trace |
| 51 | * the trace to register. |
| 52 | */ |
| 53 | public static synchronized void removeTrace(final CtfTmfTrace trace) { |
| 54 | CtfTraceManager mgr = map.remove(trace); |
| 55 | if (mgr != null) { |
| 56 | mgr.clear(); |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | /** |
| 61 | * Get an iterator for a given trace and context. |
| 62 | * |
| 63 | * @param trace |
| 64 | * the trace |
| 65 | * @param ctx |
| 66 | * the context |
| 67 | * @return the iterator |
| 68 | */ |
| 69 | public static synchronized CtfIterator getIterator(final CtfTmfTrace trace, |
| 70 | final CtfTmfLightweightContext ctx) { |
| 71 | return map.get(trace).getIterator(ctx); |
| 72 | } |
| 73 | } |
| 74 | |
| 75 | /** |
| 76 | * A trace manager |
| 77 | * |
| 78 | * @author Matthew Khouzam |
| 79 | */ |
| 80 | class CtfTraceManager { |
| 81 | /* |
| 82 | * Cache size. Under 1023 on linux32 systems. Number of file handles |
| 83 | * created. |
| 84 | */ |
| 85 | private final static int MAX_SIZE = 100; |
| 86 | /* |
| 87 | * The map of the cache. |
| 88 | */ |
| 89 | private final HashMap<CtfTmfLightweightContext, CtfIterator> fMap; |
| 90 | /* |
| 91 | * An array pointing to the same cache. this allows fast "random" accesses. |
| 92 | */ |
| 93 | private final ArrayList<CtfTmfLightweightContext> fRandomAccess; |
| 94 | /* |
| 95 | * The parent trace |
| 96 | */ |
| 97 | private final CtfTmfTrace fTrace; |
| 98 | /* |
| 99 | * Random number generator |
| 100 | */ |
| 101 | private final Random fRnd; |
| 102 | |
| 103 | public CtfTraceManager(CtfTmfTrace trace) { |
| 104 | fMap = new HashMap<CtfTmfLightweightContext, CtfIterator>(); |
| 105 | fRandomAccess = new ArrayList<CtfTmfLightweightContext>(); |
| 106 | fRnd = new Random(System.nanoTime()); |
| 107 | fTrace = trace; |
| 108 | } |
| 109 | |
| 110 | /** |
| 111 | * This needs explaining: the iterator table is effectively a cache. |
| 112 | * Originally the contexts had a 1 to 1 structure with the file handles of a |
| 113 | * trace. This failed since there is a limit to how many file handles we can |
| 114 | * have opened simultaneously. Then a round-robin scheme was implemented, |
| 115 | * this lead up to a two competing contexts syncing up and using the same |
| 116 | * file handler, causing horrible slowdowns. Now a random replacement |
| 117 | * algorithm is selected. This is the same as used by arm processors, and it |
| 118 | * works quite well when many cores so this looks promising for very |
| 119 | * multi-threaded systems. |
| 120 | * |
| 121 | * @param context |
| 122 | * the context to look up |
| 123 | * @return the iterator refering to the context |
| 124 | */ |
| 125 | public CtfIterator getIterator(final CtfTmfLightweightContext context) { |
| 126 | /* |
| 127 | * if the element is in the map, we don't need to do anything else. |
| 128 | */ |
| 129 | CtfIterator retVal = fMap.get(context); |
| 130 | if (retVal == null) { |
| 131 | /* |
| 132 | * Assign an iterator to a context, this means we will need to seek |
| 133 | * at the end. |
| 134 | */ |
| 135 | if (fRandomAccess.size() < MAX_SIZE) { |
| 136 | /* |
| 137 | * if we're not full yet, just add an element. |
| 138 | */ |
| 139 | retVal = fTrace.createIterator(); |
| 140 | addElement(context, retVal); |
| 141 | |
| 142 | } else { |
| 143 | /* |
| 144 | * if we're full, randomly replace an element |
| 145 | */ |
| 146 | retVal = replaceRandomElement(context); |
| 147 | } |
| 148 | if (context.getLocation() != null) { |
| 149 | final CtfLocationData location = (CtfLocationData) context.getLocation().getLocationInfo(); |
| 150 | retVal.seek(location); |
| 151 | } |
| 152 | } |
| 153 | return retVal; |
| 154 | } |
| 155 | |
| 156 | /** |
| 157 | * Add a pair of context and element to the hashmap and the arraylist. |
| 158 | * |
| 159 | * @param context |
| 160 | * the context |
| 161 | * @param elem |
| 162 | * the iterator |
| 163 | */ |
| 164 | private void addElement(final CtfTmfLightweightContext context, |
| 165 | final CtfIterator elem) { |
| 166 | fMap.put(context, elem); |
| 167 | fRandomAccess.add(context); |
| 168 | } |
| 169 | |
| 170 | /** |
| 171 | * Replace a random element |
| 172 | * |
| 173 | * @param context |
| 174 | * the context to swap in |
| 175 | * @return the iterator of the removed elements. |
| 176 | */ |
| 177 | private CtfIterator replaceRandomElement( |
| 178 | final CtfTmfLightweightContext context) { |
| 179 | /* |
| 180 | * This needs some explanation too: We need to select a random victim |
| 181 | * and remove it. The order of the elements is not important, so instead |
| 182 | * of just calling arraylist.remove(element) which has an O(n) |
| 183 | * complexity, we pick an random number. The element is swapped out of |
| 184 | * the array and removed and replaced in the hashmap. |
| 185 | */ |
| 186 | final int size = fRandomAccess.size(); |
| 187 | final int pos = fRnd.nextInt(size); |
| 188 | final CtfTmfLightweightContext victim = fRandomAccess.get(pos); |
| 189 | fRandomAccess.set(pos, context); |
| 190 | final CtfIterator elem = fMap.remove(victim); |
| 191 | fMap.put(context, elem); |
| 192 | return elem; |
| 193 | } |
| 194 | |
| 195 | void clear() { |
| 196 | for (CtfIterator iterator : fMap.values()) { |
| 197 | iterator.dispose(); |
| 198 | } |
| 199 | fMap.clear(); |
| 200 | fRandomAccess.clear(); |
| 201 | } |
| 202 | } |