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