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

   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 }