org.eclipse.linuxtools.lttng.core/src/org/eclipse/linuxtools/internal/lttng/core/latency/analyzer/EventMatcher.java

   1 /*******************************************************************************
   2  * Copyright (c) 2011 Ericsson
   3  *
   4  * All rights reserved. This program and the accompanying materials are made available under the terms of the Eclipse
   5  * Public License v1.0 which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/epl-v10.html
   7  *
   8  * Contributors:
   9  *   Philippe Sawicki (INF4990.A2010@gmail.com)   - Initial API and implementation
  10  *   Mathieu Denis    (mathieu.denis55@gmail.com) - Refactored code
  11  *******************************************************************************/
  12 package org.eclipse.linuxtools.internal.lttng.core.latency.analyzer;
  13
  14 import java.util.Collection;
  15 import java.util.Collections;
  16 import java.util.HashMap;
  17 import java.util.Iterator;
  18 import java.util.Map.Entry;
  19 import java.util.Set;
  20 import java.util.Stack;
  21 import java.util.Vector;
  22
  23 import org.eclipse.linuxtools.internal.lttng.core.event.LttngEvent;
  24 import org.eclipse.linuxtools.internal.lttng.core.util.EventsPair;
  25 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  26
  27 /**
  28  * <b><u>EventMatcher</u></b>
  29  * <p>
  30  * Event matching class. Saves events in a list and returns the previously saved event if the currently processed one is
  31  * its response, so that the latency can be computed by subtracting their respective timestamps.
  32  *
  33  * @author Philippe Sawicki
  34  */
  35 public class EventMatcher {
  36
  37     // ------------------------------------------------------------------------
  38     // Attributes
  39     // ------------------------------------------------------------------------
  40
  41     /**
  42      * Class instance (Singleton pattern).
  43      */
  44     private static EventMatcher fInstance = null;
  45
  46     /**
  47      * Stack abstraction, used to save the events in a list.
  48      */
  49     private final StackWrapper fStack;
  50
  51     /**
  52      * Match table, associates a request class to a response class.
  53      */
  54     private final HashMap<String, String> fMatch;
  55     /**
  56      * Inverse match table, associates a response class to a request class.
  57      */
  58     private final HashMap<String, String> fInverseMatch;
  59
  60     /**
  61      * The number of events processed.
  62      */
  63     private int fProcessedEvents;
  64     /**
  65      * The number of events matched.
  66      */
  67     private int fMatchedEvents;
  68
  69         /**
  70          * Event types identification Strings.
  71          */
  72         @SuppressWarnings("nls")
  73     public static final String
  74                 ADD_TO_PAGE_CACHE         = "add_to_page_cache",
  75                 BIO_BACKMERGE             = "bio_backmerge",
  76                 BIO_FRONTMERGE            = "bio_frontmerge",
  77                 BIO_QUEUE                 = "bio_queue",
  78                 BUFFER_WAIT_END           = "buffer_wait_end",
  79                 BUFFER_WAIT_START         = "buffer_wait_start",
  80                 CALL                      = "call",
  81                 CLOSE                     = "close",
  82                 CORE_MARKER_FORMAT        = "core_marker_format",
  83                 CORE_MARKER_ID            = "core_marker_id",
  84                 DEV_RECEIVE               = "dev_receive",
  85                 DEV_XMIT                  = "dev_xmit",
  86                 END_COMMIT                = "end_commit",
  87                 EXEC                      = "exec",
  88                 FILE_DESCRIPTOR           = "file_descriptor",
  89                 GETRQ                     = "getrq",
  90                 GETRQ_BIO                 = "getrq_bio",
  91                 IDT_TABLE                 = "idt_table",
  92                 INTERRUPT                 = "interrupt",
  93                 IOCTL                     = "ioctl",
  94                 IRQ_ENTRY                 = "irq_entry",
  95                 IRQ_EXIT                  = "irq_exit",
  96                 LIST_MODULE               = "list_module",
  97                 LLSEEK                    = "llseek",
  98                 LSEEK                     = "lseek",
  99                 NAPI_COMPLETE             = "napi_complete",
 100                 NAPI_POLL                 = "napi_poll",
 101                 NAPI_SCHEDULE             = "napi_schedule",
 102                 NETWORK_IPV4_INTERFACE    = "network_ipv4_interface",
 103                 NETWORK_IP_INTERFACE      = "network_ip_interface",
 104                 OPEN                      = "open",
 105                 PAGE_FAULT_ENTRY          = "page_fault_entry",
 106                 PAGE_FAULT_EXIT           = "page_fault_exit",
 107                 PAGE_FAULT_GET_USER_ENTRY = "page_fault_get_user_entry",
 108                 PAGE_FAULT_GET_USER_EXIT  = "page_fault_get_user_exit",
 109                 PAGE_FREE                 = "page_free",
 110                 PLUG                      = "plug",
 111                 POLLFD                    = "pollfd",
 112                 PREAD64                   = "pread64",
 113                 PRINTF                    = "printf",
 114                 PRINTK                    = "printk",
 115                 PROCESS_EXIT              = "process_exit",
 116                 PROCESS_FORK              = "process_fork",
 117                 PROCESS_FREE              = "process_free",
 118                 PROCESS_STATE             = "process_state",
 119                 PROCESS_WAIT              = "process_wait",
 120                 READ                      = "read",
 121                 REMAP                     = "remap",
 122                 REMOVE_FROM_PAGE_CACHE    = "remove_from_page_cache",
 123                 RQ_COMPLETE_FS            = "rq_complete_fs",
 124                 RQ_COMPLETE_PC            = "rq_complete_pc",
 125                 RQ_INSERT_FS              = "rq_insert_fs",
 126                 RQ_INSERT_PC              = "rq_insert_pc",
 127                 RQ_ISSUE_FS               = "rq_issue_fs",
 128                 RQ_ISSUE_PC               = "rq_issue_pc",
 129                 RQ_REQUEUE_PC             = "rq_requeue_pc",
 130                 SCHED_MIGRATE_TASK        = "sched_migrate_task",
 131                 SCHED_SCHEDULE            = "sched_schedule",
 132                 SCHED_TRY_WAKEUP          = "sched_try_wakeup",
 133                 SCHED_WAKEUP_NEW_TASK     = "sched_wakeup_new_task",
 134                 SELECT                    = "select",
 135                 SEM_CREATE                = "sem_create",
 136                 SEND_SIGNAL               = "send_signal",
 137                 SHM_CREATE                = "shm_create",
 138                 SLEEPRQ_BIO               = "sleeprq_bio",
 139                 SOCKET_ACCEPT             = "socket_accept",
 140                 SOCKET_BIND               = "socket_bind",
 141                 SOCKET_CALL               = "socket_call",
 142                 SOCKET_CONNECT            = "socket_connect",
 143                 SOCKET_CREATE             = "socket_create",
 144                 SOCKET_GETPEERNAME        = "socket_getpeername",
 145                 SOCKET_GETSOCKNAME        = "socket_getsockname",
 146                 SOCKET_GETSOCKOPT         = "socket_getsockopt",
 147                 SOCKET_LISTEN             = "socket_listen",
 148                 SOCKET_SETSOCKOPT         = "socket_setsockopt",
 149                 SOCKET_SHUTDOWN           = "socket_shutdown",
 150                 SOCKET_SOCKETPAIR         = "socket_socketpair",
 151                 SOFTIRQ_ENTRY             = "softirq_entry",
 152                 SOFTIRQ_EXIT              = "softirq_exit",
 153                 SOFTIRQ_RAISE             = "softirq_raise",
 154                 SOFTIRQ_VEC               = "softirq_vec",
 155                 START_COMMIT              = "start_commit",
 156                 STATEDUMP_END             = "statedump_end",
 157                 SYS_CALL_TABLE            = "sys_call_table",
 158             SYSCALL_ENTRY             = "syscall_entry",
 159             SYSCALL_EXIT              = "syscall_exit",
 160             TASKLET_LOW_ENTRY         = "tasklet_low_entry",
 161             TASKLET_LOW_EXIT          = "tasklet_low_exit",
 162             TCPV4_RCV                 = "tcpv4_rcv",
 163             TIMER_ITIMER_EXPIRED      = "timer_itimer_expired",
 164             TIMER_ITIMER_SET          = "timer_itimer_set",
 165             TIMER_SET                 = "timer_set",
 166             TIMER_TIMEOUT             = "timer_timeout",
 167             TIMER_UPDATE_TIME         = "timer_update_time",
 168             UDPV4_RCV                 = "udpv4_rcv",
 169             UNPLUG_IO                 = "unplug_io",
 170             UNPLUG_TIMER              = "unplug_timer",
 171             VM_MAP                    = "vm_map",
 172             VPRINTK                   = "vprintk",
 173             WAIT_ON_PAGE_END          = "wait_on_page_end",
 174             WAIT_ON_PAGE_START        = "wait_on_page_start",
 175             WRITE                     = "write",
 176             WRITEV                    = "writev";
 177
 178     // ------------------------------------------------------------------------
 179     // Constructor
 180     // ------------------------------------------------------------------------
 181
 182     /**
 183      * Private constructor to defeat instantiation (Singleton pattern).
 184      */
 185     private EventMatcher() {
 186         fStack = new StackWrapper();
 187         fMatch = new HashMap<String, String>();
 188         fInverseMatch = new HashMap<String, String>();
 189
 190         fProcessedEvents = 0;
 191         fMatchedEvents = 0;
 192
 193         createMatchTable();
 194     }
 195
 196     // ------------------------------------------------------------------------
 197     // Accessors
 198     // ------------------------------------------------------------------------
 199
 200     /**
 201      * Returns an instance to the EventMatcher class (Singleton pattern).
 202      * @return An instance to the EventMatcher class (Singleton pattern).
 203      */
 204     public static EventMatcher getInstance() {
 205         if (fInstance == null) {
 206             fInstance = new EventMatcher();
 207         }
 208         return fInstance;
 209     }
 210
 211     /**
 212      * Returns the number of events processed.
 213      * @return The number of events processed.
 214      */
 215     public int getNBProcessedEvents() {
 216         return fProcessedEvents;
 217     }
 218
 219     /**
 220      * Returns the number of events matched.
 221      * @return The number of events matched.
 222      */
 223     public int getNBMatchedEvents() {
 224         return fMatchedEvents;
 225     }
 226
 227     // ------------------------------------------------------------------------
 228     // Operations
 229     // ------------------------------------------------------------------------
 230
 231     /**
 232      * Releases the instance to the EventMatcher class.
 233      */
 234     public static void releaseInstance() {
 235         fInstance = null;
 236     }
 237
 238     /**
 239      * Creates the event matching table, linking a response class to a request class.
 240      */
 241     private void createMatchTable() {
 242         // Build the default matches
 243         fMatch.put(PAGE_FAULT_GET_USER_EXIT, PAGE_FAULT_GET_USER_ENTRY);
 244         fMatch.put(TASKLET_LOW_EXIT, TASKLET_LOW_ENTRY);
 245         fMatch.put(PAGE_FAULT_EXIT, PAGE_FAULT_ENTRY);
 246         fMatch.put(SYSCALL_EXIT, SYSCALL_ENTRY);
 247         fMatch.put(IRQ_EXIT, IRQ_ENTRY);
 248         fMatch.put(WRITE, READ);
 249         fMatch.put(CLOSE, OPEN);
 250         fMatch.put(BUFFER_WAIT_END, BUFFER_WAIT_START);
 251         fMatch.put(END_COMMIT, START_COMMIT);
 252         fMatch.put(WAIT_ON_PAGE_END, WAIT_ON_PAGE_START);
 253
 254         // Build the inverse matches based on the matches
 255         Set<Entry<String, String>> pairs = fMatch.entrySet();
 256         Iterator<Entry<String, String>> it = pairs.iterator();
 257         while (it.hasNext()) {
 258             Entry<String, String> pair = it.next();
 259             fInverseMatch.put(pair.getValue(), pair.getKey());
 260         }
 261     }
 262
 263     /**
 264      * Processes an event received: if it is identified as a response, try to get its request to remove it from the
 265      * list. If no request was saved, dismiss the current response. If it is a request, save it to the list of requests
 266      * waiting for a response.
 267      * @param event
 268      *            The event to identify, and maybe process if it is a response.
 269      * @return The request event associated with the current event (a response), or null if nothing was found (no
 270      *         request associated with this response, or the event to identify was a request that was added to the
 271      *         list).
 272      */
 273     public LttngEvent process(ITmfEvent ev) {
 274         LttngEvent event = (LttngEvent) ev;
 275         fProcessedEvents++;
 276
 277         String markerName = event.getMarkerName();
 278         if (fMatch.containsKey(markerName)) {
 279             String startEventType = fMatch.get(markerName);
 280             Stack<LttngEvent> events = fStack.getStackOf(startEventType);
 281
 282             if (events != null) {
 283                 for (int i = events.size() - 1; i >= 0; i--) {
 284                     LttngEvent request = events.get(i);
 285
 286                     if (request.getCpuId() == event.getCpuId() && event.getTimestamp().getValue() > request.getTimestamp().getValue()) {
 287                         fStack.removeEvent(startEventType, request);
 288                         fMatchedEvents++;
 289                         return request;
 290                     }
 291                 }
 292             }
 293             return null;
 294         } else {
 295             // Add only if there can later be a match for this request
 296             if (fMatch.containsValue(event.getMarkerName())) {
 297                 fStack.put(event.clone());
 298             }
 299             return null;
 300         }
 301     }
 302
 303     /**
 304      * Clears the stack content.
 305      */
 306     public void clearStack() {
 307         fStack.clear();
 308
 309         // Reset the processed and matched events counter
 310         fProcessedEvents = 0;
 311         fMatchedEvents = 0;
 312     }
 313
 314     /**
 315      * Resets all.
 316      */
 317     public void resetMatches() {
 318         fMatch.clear();
 319         fInverseMatch.clear();
 320
 321         fStack.clear();
 322
 323         // Reset the processed and matched events counter
 324         fProcessedEvents = 0;
 325         fMatchedEvents = 0;
 326     }
 327
 328     /**
 329      * Returns the list of start events.
 330      * @return The list of start events.
 331      */
 332     public Collection<String> getStartEvents() {
 333         return fMatch.values();
 334     }
 335
 336     /**
 337      * Returns the list of end events.
 338      * @return The list of end events.
 339      */
 340     public Set<String> getEndEvents() {
 341         return fMatch.keySet();
 342     }
 343
 344     /**
 345      * Returns the alphabetically-sorted list of start/end events pairs.
 346      * @return The alphabetically-sorted list of start/end events pairs.
 347      */
 348     public EventsPair getEvents() {
 349         Vector<String> start = new Vector<String>(getStartEvents());
 350         Vector<String> end = new Vector<String>(fMatch.size());
 351
 352         Collections.sort(start);
 353         for (int i = 0; i < start.size(); i++) {
 354             end.add(fInverseMatch.get(start.get(i)));
 355         }
 356         return new EventsPair(start, end);
 357     }
 358
 359     /**
 360      * Adds a match to the list of events pairs.
 361      * @param startType
 362      *            The start event type.
 363      * @param endType
 364      *            The end event type.
 365      */
 366     public void addMatch(String startType, String endType) {
 367         fMatch.put(endType, startType);
 368         fInverseMatch.put(startType, endType);
 369     }
 370
 371     /**
 372      * Removes a matched pair based on the their type.
 373      *
 374      * <b>Note :</b> For now, only the pair's end type is used, since a type can only be either one start or one end.
 375      * This function takes both types to account for the future, if a pairing process ever becomes more complex.
 376      *
 377      * @param startType
 378      *            The type of the pair's start type.
 379      * @param endType
 380      *            The type of the pair's end type.
 381      */
 382     public void removeMatch(String startType, String endType) {
 383         fMatch.remove(endType);
 384         fInverseMatch.remove(startType);
 385     }
 386
 387     /**
 388      * Returns the list of all event possible types.
 389      * @return The list of all event possible types.
 390      */
 391     public Vector<String> getTypeList() {
 392         // Reserve some space for the 103 default event types.
 393         Vector<String> eventsList = new Vector<String>(103);
 394
 395         eventsList.add(ADD_TO_PAGE_CACHE);
 396         eventsList.add(BIO_BACKMERGE);
 397         eventsList.add(BIO_FRONTMERGE);
 398         eventsList.add(BIO_QUEUE);
 399         eventsList.add(BUFFER_WAIT_END);
 400         eventsList.add(BUFFER_WAIT_START);
 401         eventsList.add(CALL);
 402         eventsList.add(CLOSE);
 403         eventsList.add(CORE_MARKER_FORMAT);
 404         eventsList.add(CORE_MARKER_ID);
 405         eventsList.add(DEV_RECEIVE);
 406         eventsList.add(DEV_XMIT);
 407         eventsList.add(END_COMMIT);
 408         eventsList.add(EXEC);
 409         eventsList.add(FILE_DESCRIPTOR);
 410         eventsList.add(GETRQ);
 411         eventsList.add(GETRQ_BIO);
 412         eventsList.add(IDT_TABLE);
 413         eventsList.add(INTERRUPT);
 414         eventsList.add(IOCTL);
 415         eventsList.add(IRQ_ENTRY);
 416         eventsList.add(IRQ_EXIT);
 417         eventsList.add(LIST_MODULE);
 418         eventsList.add(LLSEEK);
 419         eventsList.add(LSEEK);
 420         eventsList.add(NAPI_COMPLETE);
 421         eventsList.add(NAPI_POLL);
 422         eventsList.add(NAPI_SCHEDULE);
 423         eventsList.add(NETWORK_IPV4_INTERFACE);
 424         eventsList.add(NETWORK_IP_INTERFACE);
 425         eventsList.add(OPEN);
 426         eventsList.add(PAGE_FAULT_ENTRY);
 427         eventsList.add(PAGE_FAULT_EXIT);
 428         eventsList.add(PAGE_FAULT_GET_USER_ENTRY);
 429         eventsList.add(PAGE_FAULT_GET_USER_EXIT);
 430         eventsList.add(PAGE_FREE);
 431         eventsList.add(PLUG);
 432         eventsList.add(POLLFD);
 433         eventsList.add(PREAD64);
 434         eventsList.add(PRINTF);
 435         eventsList.add(PRINTK);
 436         eventsList.add(PROCESS_EXIT);
 437         eventsList.add(PROCESS_FORK);
 438         eventsList.add(PROCESS_FREE);
 439         eventsList.add(PROCESS_STATE);
 440         eventsList.add(PROCESS_WAIT);
 441         eventsList.add(READ);
 442         eventsList.add(REMAP);
 443         eventsList.add(REMOVE_FROM_PAGE_CACHE);
 444         eventsList.add(RQ_COMPLETE_FS);
 445         eventsList.add(RQ_COMPLETE_PC);
 446         eventsList.add(RQ_INSERT_FS);
 447         eventsList.add(RQ_INSERT_PC);
 448         eventsList.add(RQ_ISSUE_FS);
 449         eventsList.add(RQ_ISSUE_PC);
 450         eventsList.add(RQ_REQUEUE_PC);
 451         eventsList.add(SCHED_MIGRATE_TASK);
 452         eventsList.add(SCHED_SCHEDULE);
 453         eventsList.add(SCHED_TRY_WAKEUP);
 454         eventsList.add(SCHED_WAKEUP_NEW_TASK);
 455         eventsList.add(SELECT);
 456         eventsList.add(SEM_CREATE);
 457         eventsList.add(SEND_SIGNAL);
 458         eventsList.add(SHM_CREATE);
 459         eventsList.add(SLEEPRQ_BIO);
 460         eventsList.add(SOCKET_ACCEPT);
 461         eventsList.add(SOCKET_BIND);
 462         eventsList.add(SOCKET_CALL);
 463         eventsList.add(SOCKET_CONNECT);
 464         eventsList.add(SOCKET_CREATE);
 465         eventsList.add(SOCKET_GETPEERNAME);
 466         eventsList.add(SOCKET_GETSOCKNAME);
 467         eventsList.add(SOCKET_GETSOCKOPT);
 468         eventsList.add(SOCKET_LISTEN);
 469         eventsList.add(SOCKET_SETSOCKOPT);
 470         eventsList.add(SOCKET_SHUTDOWN);
 471         eventsList.add(SOCKET_SOCKETPAIR);
 472         eventsList.add(SOFTIRQ_ENTRY);
 473         eventsList.add(SOFTIRQ_EXIT);
 474         eventsList.add(SOFTIRQ_RAISE);
 475         eventsList.add(SOFTIRQ_VEC);
 476         eventsList.add(START_COMMIT);
 477         eventsList.add(STATEDUMP_END);
 478         eventsList.add(SYS_CALL_TABLE);
 479         eventsList.add(SYSCALL_ENTRY);
 480         eventsList.add(SYSCALL_EXIT);
 481         eventsList.add(TASKLET_LOW_ENTRY);
 482         eventsList.add(TASKLET_LOW_EXIT);
 483         eventsList.add(TCPV4_RCV);
 484         eventsList.add(TIMER_ITIMER_EXPIRED);
 485         eventsList.add(TIMER_ITIMER_SET);
 486         eventsList.add(TIMER_SET);
 487         eventsList.add(TIMER_TIMEOUT);
 488         eventsList.add(TIMER_UPDATE_TIME);
 489         eventsList.add(UDPV4_RCV);
 490         eventsList.add(UNPLUG_IO);
 491         eventsList.add(UNPLUG_TIMER);
 492         eventsList.add(VM_MAP);
 493         eventsList.add(VPRINTK);
 494         eventsList.add(WAIT_ON_PAGE_END);
 495         eventsList.add(WAIT_ON_PAGE_START);
 496         eventsList.add(WRITE);
 497         eventsList.add(WRITEV);
 498
 499         return eventsList;
 500     }
 501
 502     /**
 503      * Prints the stack content to the console.
 504      */
 505     public void print() {
 506         fStack.printContent();
 507     }
 508 }