org.eclipse.linuxtools.tmf.ctf.core/src/org/eclipse/linuxtools/tmf/ctf/core/CtfIteratorManager.java

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