src/mc/mc_private.h

   1 /* Copyright (c) 2007-2015. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #ifndef SIMGRID_MC_PRIVATE_H
   8 #define SIMGRID_MC_PRIVATE_H
   9
  10 #include "simgrid_config.h"
  11
  12 #include <sys/types.h>
  13
  14 #include <stdio.h>
  15 #ifndef WIN32
  16 #include <sys/mman.h>
  17 #endif
  18
  19 #include <elfutils/libdw.h>
  20
  21 #include <simgrid/msg.h>
  22 #include <xbt/fifo.h>
  23 #include <xbt/config.h>
  24 #include <xbt/base.h>
  25
  26 #include "mc/mc.h"
  27 #include "mc/datatypes.h"
  28 #include "src/mc/mc_base.h"
  29
  30 #include "src/simix/smx_private.h"
  31 #include "src/xbt/mmalloc/mmprivate.h"
  32
  33 #ifdef __cplusplus
  34 #include "src/mc/mc_forward.hpp"
  35 #include "src/xbt/memory_map.hpp"
  36 #endif
  37
  38 #include "src/mc/mc_protocol.h"
  39
  40 SG_BEGIN_DECL()
  41
  42 /********************************* MC Global **********************************/
  43
  44 XBT_PRIVATE void MC_init_dot_output();
  45
  46 XBT_PRIVATE extern FILE *dot_output;
  47
  48 XBT_PRIVATE extern int user_max_depth_reached;
  49
  50 XBT_PRIVATE void MC_replay(xbt_fifo_t stack);
  51 XBT_PRIVATE void MC_show_deadlock(smx_simcall_t req);
  52 XBT_PRIVATE void MC_show_stack_safety(xbt_fifo_t stack);
  53 XBT_PRIVATE void MC_dump_stack_safety(xbt_fifo_t stack);
  54 XBT_PRIVATE void MC_show_non_termination(void);
  55
  56 /** Stack (of `mc_state_t`) representing the current position of the
  57  *  the MC in the exploration graph
  58  *
  59  *  It is managed by its head (`xbt_fifo_shift` and `xbt_fifo_unshift`).
  60  */
  61 XBT_PRIVATE extern xbt_fifo_t mc_stack;
  62
  63 #ifdef __cplusplus
  64
  65 SG_END_DECL()
  66
  67 namespace simgrid {
  68 namespace mc {
  69
  70 /**
  71  *  \brief Find a suitable subrange of candidate duplicates for a given state
  72  *  \param list dynamic array of states/pairs with candidate duplicates of the current state;
  73  *  \param ref current state/pair;
  74  *  \param min (output) index of the beginning of the the subrange
  75  *  \param max (output) index of the enf of the subrange
  76  *
  77  *  Given a suitably ordered array of states/pairs, this function extracts a subrange
  78  *  (with index *min <= i <= *max) with candidate duplicates of the given state/pair.
  79  *  This function uses only fast discriminating criterions and does not use the
  80  *  full state/pair comparison algorithms.
  81  *
  82  *  The states/pairs in list MUST be ordered using a (given) weak order
  83  *  (based on nb_processes and heap_bytes_used).
  84  *  The subrange is the subrange of "equivalence" of the given state/pair.
  85  */
  86 // TODO, it would make sense to use std::set instead
  87 // U = some pointer of T (T*, unique_ptr<T>, shared_ptr<T>)
  88 template<class U, class T>
  89 int get_search_interval(
  90   U* list, std::size_t count, T *ref, int *min, int *max)
  91 {
  92   int nb_processes = ref->nb_processes;
  93   int heap_bytes_used = ref->heap_bytes_used;
  94
  95   int cursor = 0;
  96   int start = 0;
  97   int end = count - 1;
  98   while (start <= end) {
  99     cursor = (start + end) / 2;
 100     int nb_processes_test = list[cursor]->nb_processes;
 101     int heap_bytes_used_test = list[cursor]->heap_bytes_used;
 102
 103     if (nb_processes_test < nb_processes)
 104       start = cursor + 1;
 105     else if (nb_processes_test > nb_processes)
 106       end = cursor - 1;
 107     else if (heap_bytes_used_test < heap_bytes_used)
 108       start = cursor + 1;
 109     else if (heap_bytes_used_test > heap_bytes_used)
 110       end = cursor - 1;
 111     else {
 112         *min = *max = cursor;
 113         int previous_cursor = cursor - 1;
 114         while (previous_cursor >= 0) {
 115           nb_processes_test = list[previous_cursor]->nb_processes;
 116           heap_bytes_used_test = list[previous_cursor]->heap_bytes_used;
 117           if (nb_processes_test != nb_processes || heap_bytes_used_test != heap_bytes_used)
 118             break;
 119           *min = previous_cursor;
 120           previous_cursor--;
 121         }
 122         size_t next_cursor = cursor + 1;
 123         while (next_cursor < count) {
 124           nb_processes_test = list[next_cursor]->nb_processes;
 125           heap_bytes_used_test = list[next_cursor]->heap_bytes_used;
 126           if (nb_processes_test != nb_processes || heap_bytes_used_test != heap_bytes_used)
 127             break;
 128           *max = next_cursor;
 129           next_cursor++;
 130         }
 131         return -1;
 132     }
 133   }
 134   return cursor;
 135 }
 136
 137 }
 138 }
 139
 140 #endif
 141
 142 SG_BEGIN_DECL()
 143
 144 /****************************** Statistics ************************************/
 145
 146 typedef struct mc_stats {
 147   unsigned long state_size;
 148   unsigned long visited_states;
 149   unsigned long visited_pairs;
 150   unsigned long expanded_states;
 151   unsigned long expanded_pairs;
 152   unsigned long executed_transitions;
 153 } s_mc_stats_t, *mc_stats_t;
 154
 155 XBT_PRIVATE extern mc_stats_t mc_stats;
 156
 157 XBT_PRIVATE void MC_print_statistics(mc_stats_t stats);
 158
 159 /********************************** Snapshot comparison **********************************/
 160
 161 //#define MC_DEBUG 1
 162 #define MC_VERBOSE 1
 163
 164 /********************************** Miscellaneous **********************************/
 165
 166 XBT_PRIVATE void MC_report_assertion_error(void);
 167 XBT_PRIVATE void MC_report_crash(int status);
 168
 169 SG_END_DECL()
 170
 171 #ifdef __cplusplus
 172
 173 namespace simgrid {
 174 namespace mc {
 175
 176 XBT_PRIVATE void find_object_address(
 177   std::vector<simgrid::xbt::VmMap> const& maps, simgrid::mc::ObjectInformation* result);
 178
 179 XBT_PRIVATE
 180 int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc::Snapshot* s2);
 181
 182 }
 183 }
 184
 185 #endif
 186
 187 #endif