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