ctf/org.eclipse.tracecompass.tmf.ctf.core/src/org/eclipse/tracecompass/internal/tmf/ctf/core/trace/iterator/CtfIteratorManager.java

   1 /*******************************************************************************
   2  * Copyright (c) 2014 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  *   Alexandre Montplaisir - Renamed/extracted from CtfTraceManager
  11  *******************************************************************************/
  12
  13 package org.eclipse.tracecompass.internal.tmf.ctf.core.trace.iterator;
  14
  15 import java.util.ArrayList;
  16 import java.util.HashMap;
  17 import java.util.List;
  18 import java.util.Map;
  19 import java.util.Random;
  20 import java.util.concurrent.locks.Lock;
  21 import java.util.concurrent.locks.ReentrantLock;
  22
  23 import org.eclipse.tracecompass.internal.tmf.ctf.core.Activator;
  24 import org.eclipse.tracecompass.tmf.ctf.core.context.CtfLocationInfo;
  25 import org.eclipse.tracecompass.tmf.ctf.core.context.CtfTmfContext;
  26 import org.eclipse.tracecompass.tmf.ctf.core.trace.CtfTmfTrace;
  27
  28 /**
  29  * A CTF trace iterator manager.
  30  *
  31  * Each instance of {@link CtfTmfTrace} should possess one of these, which will
  32  * manage the iterators that are opened to read that trace. This will allow
  33  * controlling the number of opened file handles per trace.
  34  *
  35  * @author Matthew Khouzam
  36  */
  37 public class CtfIteratorManager {
  38     /*
  39      * Cache size. Under 1023 on linux32 systems. Number of file handles
  40      * created.
  41      */
  42     private static final int MAX_SIZE = 100;
  43
  44     /** The map of the cache */
  45     private final Map<CtfTmfContext, CtfIterator> fMap;
  46
  47     /** An array pointing to the same cache. this allows fast "random" accesses */
  48     private final List<CtfTmfContext> fRandomAccess;
  49
  50     /** Lock for when we access the two previous data structures */
  51     private final Lock fAccessLock = new ReentrantLock();
  52
  53     /** The parent trace */
  54     private final CtfTmfTrace fTrace;
  55
  56     /** Random number generator */
  57     private final Random fRnd;
  58
  59     /**
  60      * Constructor
  61      *
  62      * @param trace
  63      *            The trace whose iterators this manager will manage
  64      */
  65     public CtfIteratorManager(CtfTmfTrace trace) {
  66         fMap = new HashMap<>();
  67         fRandomAccess = new ArrayList<>();
  68         fRnd = new Random(System.nanoTime());
  69         fTrace = trace;
  70     }
  71
  72     /**
  73      * This needs explaining: the iterator table is effectively a cache.
  74      * Originally the contexts had a 1 to 1 structure with the file handles of a
  75      * trace. This failed since there is a limit to how many file handles we can
  76      * have opened simultaneously. Then a round-robin scheme was implemented,
  77      * this lead up to a two competing contexts syncing up and using the same
  78      * file handler, causing horrible slowdowns. Now a random replacement
  79      * algorithm is selected. This is the same as used by arm processors, and it
  80      * works quite well when many cores so this looks promising for very
  81      * multi-threaded systems.
  82      *
  83      * @param context
  84      *            the context to look up
  85      * @return the iterator referring to the context
  86      */
  87     public CtfIterator getIterator(final CtfTmfContext context) {
  88         /*
  89          * if the element is in the map, we don't need to do anything else.
  90          */
  91         CtfIterator iter = fMap.get(context);
  92         if (iter == null) {
  93
  94             fAccessLock.lock();
  95             try {
  96                 /*
  97                  * Assign an iterator to a context.
  98                  */
  99                 if (fRandomAccess.size() < MAX_SIZE) {
 100                     /*
 101                      * if we're not full yet, just add an element.
 102                      */
 103                     iter = (CtfIterator) fTrace.createIterator();
 104                     addElement(context, iter);
 105
 106                 } else {
 107                     /*
 108                      * if we're full, randomly replace an element
 109                      */
 110                     iter = replaceRandomElement(context);
 111                 }
 112                 if (context.getLocation() != null) {
 113                     final CtfLocationInfo location = (CtfLocationInfo) context.getLocation().getLocationInfo();
 114                     iter.seek(location);
 115                 }
 116             } finally {
 117                 fAccessLock.unlock();
 118             }
 119         }
 120         return iter;
 121     }
 122
 123     /**
 124      * Remove an iterator from this manager
 125      *
 126      * @param context
 127      *            The context of the iterator to remove
 128      */
 129     public void removeIterator(CtfTmfContext context) {
 130         fAccessLock.lock();
 131         try {
 132             /* The try below is only to auto-call CtfIterator.close() */
 133             try (CtfIterator removed = fMap.remove(context)) {
 134                 // try with resource
 135             }
 136             fRandomAccess.remove(context);
 137
 138         } finally {
 139             fAccessLock.unlock();
 140         }
 141     }
 142
 143     /**
 144      * Add a pair of context and element to the hashmap and the arraylist.
 145      *
 146      * @param context
 147      *            the context
 148      * @param elem
 149      *            the iterator
 150      */
 151     private void addElement(final CtfTmfContext context,
 152             final CtfIterator elem) {
 153         fAccessLock.lock();
 154         try {
 155             fMap.put(context, elem);
 156             fRandomAccess.add(context);
 157
 158         } finally {
 159             fAccessLock.unlock();
 160         }
 161     }
 162
 163     /**
 164      * Replace a random element
 165      *
 166      * @param context
 167      *            the context to swap in
 168      * @return the iterator of the removed elements.
 169      */
 170     private CtfIterator replaceRandomElement(final CtfTmfContext context) {
 171         /*
 172          * This needs some explanation too: We need to select a random victim
 173          * and remove it. The order of the elements is not important, so instead
 174          * of just calling arraylist.remove(element) which has an O(n)
 175          * complexity, we pick an random number. The element is swapped out of
 176          * the array and removed and replaced in the hashmap.
 177          */
 178         fAccessLock.lock(); // just in case, should only be called when already locked
 179         try {
 180             final int size = fRandomAccess.size();
 181             final int pos = fRnd.nextInt(size);
 182             final CtfTmfContext victim = fRandomAccess.get(pos);
 183             fRandomAccess.set(pos, context);
 184             CtfIterator elem = fMap.remove(victim);
 185             if (elem.isClosed()) {
 186                 /*
 187                  * In case the iterator streams have been closed, we need to
 188                  * replace it by a fresh new one to access the trace. We also
 189                  * report that as an error as it should not happen.
 190                  */
 191                 Activator.getDefault().logError("Found closed iterator in iterator manager for trace " + victim.getTrace()); //$NON-NLS-1$
 192
 193                 elem.dispose();
 194                 elem = (CtfIterator) fTrace.createIterator();
 195             }
 196             fMap.put(context, elem);
 197             victim.dispose();
 198             return elem;
 199
 200         } finally {
 201             fAccessLock.unlock();
 202         }
 203     }
 204
 205     /**
 206      * Dispose this iterator manager, which will close all the remaining
 207      * iterators.
 208      */
 209     public void dispose() {
 210         fAccessLock.lock();
 211         try {
 212             for (CtfIterator iterator : fMap.values()) {
 213                 iterator.dispose();
 214             }
 215             fMap.clear();
 216             fRandomAccess.clear();
 217
 218         } finally {
 219             fAccessLock.unlock();
 220         }
 221     }
 222 }