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