snapshot.cc

   1 #include <inttypes.h>
   2 #include <sys/mman.h>
   3 #include <unistd.h>
   4 #include <signal.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <errno.h>
   8 #include <sys/wait.h>
   9
  10 #include "hashtable.h"
  11 #include "snapshot.h"
  12 #include "mymemory.h"
  13 #include "common.h"
  14 #include "context.h"
  15 #include "model.h"
  16
  17 /** PageAlignedAdressUpdate return a page aligned address for the
  18  * address being added as a side effect the numBytes are also changed.
  19  */
  20 static void * PageAlignAddressUpward(void *addr)
  21 {
  22         return (void *)((((uintptr_t)addr) + PAGESIZE - 1) & ~(PAGESIZE - 1));
  23 }
  24
  25 #if USE_MPROTECT_SNAPSHOT
  26
  27 /* Each SnapShotRecord lists the firstbackingpage that must be written to
  28  * revert to that snapshot */
  29 struct SnapShotRecord {
  30         unsigned int firstBackingPage;
  31 };
  32
  33 /** @brief Backing store page */
  34 typedef unsigned char snapshot_page_t[PAGESIZE];
  35
  36 /* List the base address of the corresponding page in the backing store so we
  37  * know where to copy it to */
  38 struct BackingPageRecord {
  39         void *basePtrOfPage;
  40 };
  41
  42 /* Struct for each memory region */
  43 struct MemoryRegion {
  44         void *basePtr;  // base of memory region
  45         int sizeInPages;        // size of memory region in pages
  46 };
  47
  48 /** ReturnPageAlignedAddress returns a page aligned address for the
  49  * address being added as a side effect the numBytes are also changed.
  50  */
  51 static void * ReturnPageAlignedAddress(void *addr)
  52 {
  53         return (void *)(((uintptr_t)addr) & ~(PAGESIZE - 1));
  54 }
  55
  56 /* Primary struct for snapshotting system */
  57 struct mprot_snapshotter {
  58         mprot_snapshotter(unsigned int numbackingpages, unsigned int numsnapshots, unsigned int nummemoryregions);
  59         ~mprot_snapshotter();
  60
  61         struct MemoryRegion *regionsToSnapShot; //This pointer references an array of memory regions to snapshot
  62         snapshot_page_t *backingStore;  //This pointer references an array of snapshotpage's that form the backing store
  63         void *backingStoreBasePtr;      //This pointer references an array of snapshotpage's that form the backing store
  64         struct BackingPageRecord *backingRecords;       //This pointer references an array of backingpagerecord's (same number of elements as backingstore
  65         struct SnapShotRecord *snapShots;       //This pointer references the snapshot array
  66
  67         unsigned int lastSnapShot;      //Stores the next snapshot record we should use
  68         unsigned int lastBackingPage;   //Stores the next backingpage we should use
  69         unsigned int lastRegion;        //Stores the next memory region to be used
  70
  71         unsigned int maxRegions;        //Stores the max number of memory regions we support
  72         unsigned int maxBackingPages;   //Stores the total number of backing pages
  73         unsigned int maxSnapShots;      //Stores the total number of snapshots we allow
  74
  75         MEMALLOC
  76 };
  77
  78 static struct mprot_snapshotter *mprot_snap = NULL;
  79
  80 mprot_snapshotter::mprot_snapshotter(unsigned int backing_pages, unsigned int snapshots, unsigned int regions) :
  81         lastSnapShot(0),
  82         lastBackingPage(0),
  83         lastRegion(0),
  84         maxRegions(regions),
  85         maxBackingPages(backing_pages),
  86         maxSnapShots(snapshots)
  87 {
  88         regionsToSnapShot = (struct MemoryRegion *)model_malloc(sizeof(struct MemoryRegion) * regions);
  89         backingStoreBasePtr = (void *)model_malloc(sizeof(snapshot_page_t) * (backing_pages + 1));
  90         //Page align the backingstorepages
  91         backingStore = (snapshot_page_t *)PageAlignAddressUpward(backingStoreBasePtr);
  92         backingRecords = (struct BackingPageRecord *)model_malloc(sizeof(struct BackingPageRecord) * backing_pages);
  93         snapShots = (struct SnapShotRecord *)model_malloc(sizeof(struct SnapShotRecord) * snapshots);
  94 }
  95
  96 mprot_snapshotter::~mprot_snapshotter()
  97 {
  98         model_free(regionsToSnapShot);
  99         model_free(backingStoreBasePtr);
 100         model_free(backingRecords);
 101         model_free(snapShots);
 102 }
 103
 104 /** mprot_handle_pf is the page fault handler for mprotect based snapshotting
 105  * algorithm.
 106  */
 107 static void mprot_handle_pf(int sig, siginfo_t *si, void *unused)
 108 {
 109         if (si->si_code == SEGV_MAPERR) {
 110                 model_print("Segmentation fault at %p\n", si->si_addr);
 111                 model_print("For debugging, place breakpoint at: %s:%d\n",
 112                                                                 __FILE__, __LINE__);
 113                 // print_trace(); // Trace printing may cause dynamic memory allocation
 114                 exit(EXIT_FAILURE);
 115         }
 116         void* addr = ReturnPageAlignedAddress(si->si_addr);
 117
 118         unsigned int backingpage = mprot_snap->lastBackingPage++;       //Could run out of pages...
 119         if (backingpage == mprot_snap->maxBackingPages) {
 120                 model_print("Out of backing pages at %p\n", si->si_addr);
 121                 exit(EXIT_FAILURE);
 122         }
 123
 124         //copy page
 125         memcpy(&(mprot_snap->backingStore[backingpage]), addr, sizeof(snapshot_page_t));
 126         //remember where to copy page back to
 127         mprot_snap->backingRecords[backingpage].basePtrOfPage = addr;
 128         //set protection to read/write
 129         if (mprotect(addr, sizeof(snapshot_page_t), PROT_READ | PROT_WRITE)) {
 130                 perror("mprotect");
 131                 // Handle error by quitting?
 132         }
 133 }
 134
 135 static void mprot_snapshot_init(unsigned int numbackingpages,
 136                                                                                                                                 unsigned int numsnapshots, unsigned int nummemoryregions,
 137                                                                                                                                 unsigned int numheappages, VoidFuncPtr entryPoint)
 138 {
 139         /* Setup a stack for our signal handler....  */
 140         stack_t ss;
 141         ss.ss_sp = PageAlignAddressUpward(model_malloc(SIGSTACKSIZE + PAGESIZE - 1));
 142         ss.ss_size = SIGSTACKSIZE;
 143         ss.ss_flags = 0;
 144         sigaltstack(&ss, NULL);
 145
 146         struct sigaction sa;
 147         sa.sa_flags = SA_SIGINFO | SA_NODEFER | SA_RESTART | SA_ONSTACK;
 148         sigemptyset(&sa.sa_mask);
 149         sa.sa_sigaction = mprot_handle_pf;
 150 #ifdef MAC
 151         if (sigaction(SIGBUS, &sa, NULL) == -1) {
 152                 perror("sigaction(SIGBUS)");
 153                 exit(EXIT_FAILURE);
 154         }
 155 #endif
 156         if (sigaction(SIGSEGV, &sa, NULL) == -1) {
 157                 perror("sigaction(SIGSEGV)");
 158                 exit(EXIT_FAILURE);
 159         }
 160
 161         mprot_snap = new mprot_snapshotter(numbackingpages, numsnapshots, nummemoryregions);
 162
 163         // EVIL HACK: We need to make sure that calls into the mprot_handle_pf method don't cause dynamic links
 164         // The problem is that we end up protecting state in the dynamic linker...
 165         // Solution is to call our signal handler before we start protecting stuff...
 166
 167         siginfo_t si;
 168         memset(&si, 0, sizeof(si));
 169         si.si_addr = ss.ss_sp;
 170         mprot_handle_pf(SIGSEGV, &si, NULL);
 171         mprot_snap->lastBackingPage--;  //remove the fake page we copied
 172
 173         void *basemySpace = model_malloc((numheappages + 1) * PAGESIZE);
 174         void *pagealignedbase = PageAlignAddressUpward(basemySpace);
 175         user_snapshot_space = create_mspace_with_base(pagealignedbase, numheappages * PAGESIZE, 1);
 176         snapshot_add_memory_region(pagealignedbase, numheappages);
 177
 178         void *base_model_snapshot_space = model_malloc((numheappages + 1) * PAGESIZE);
 179         pagealignedbase = PageAlignAddressUpward(base_model_snapshot_space);
 180         model_snapshot_space = create_mspace_with_base(pagealignedbase, numheappages * PAGESIZE, 1);
 181         snapshot_add_memory_region(pagealignedbase, numheappages);
 182
 183         entryPoint();
 184 }
 185
 186 static void mprot_add_to_snapshot(void *addr, unsigned int numPages)
 187 {
 188         unsigned int memoryregion = mprot_snap->lastRegion++;
 189         if (memoryregion == mprot_snap->maxRegions) {
 190                 model_print("Exceeded supported number of memory regions!\n");
 191                 exit(EXIT_FAILURE);
 192         }
 193
 194         DEBUG("snapshot region %p-%p (%u page%s)\n",
 195                                 addr, (char *)addr + numPages * PAGESIZE, numPages,
 196                                 numPages > 1 ? "s" : "");
 197         mprot_snap->regionsToSnapShot[memoryregion].basePtr = addr;
 198         mprot_snap->regionsToSnapShot[memoryregion].sizeInPages = numPages;
 199 }
 200
 201 static snapshot_id mprot_take_snapshot()
 202 {
 203         for (unsigned int region = 0;region < mprot_snap->lastRegion;region++) {
 204                 if (mprotect(mprot_snap->regionsToSnapShot[region].basePtr, mprot_snap->regionsToSnapShot[region].sizeInPages * sizeof(snapshot_page_t), PROT_READ) == -1) {
 205                         perror("mprotect");
 206                         model_print("Failed to mprotect inside of takeSnapShot\n");
 207                         exit(EXIT_FAILURE);
 208                 }
 209         }
 210         unsigned int snapshot = mprot_snap->lastSnapShot++;
 211         if (snapshot == mprot_snap->maxSnapShots) {
 212                 model_print("Out of snapshots\n");
 213                 exit(EXIT_FAILURE);
 214         }
 215         mprot_snap->snapShots[snapshot].firstBackingPage = mprot_snap->lastBackingPage;
 216
 217         return snapshot;
 218 }
 219
 220 static void mprot_roll_back(snapshot_id theID)
 221 {
 222 #if USE_MPROTECT_SNAPSHOT == 2
 223         if (mprot_snap->lastSnapShot == (theID + 1)) {
 224                 for (unsigned int page = mprot_snap->snapShots[theID].firstBackingPage;page < mprot_snap->lastBackingPage;page++) {
 225                         memcpy(mprot_snap->backingRecords[page].basePtrOfPage, &mprot_snap->backingStore[page], sizeof(snapshot_page_t));
 226                 }
 227                 return;
 228         }
 229 #endif
 230
 231         HashTable< void *, bool, uintptr_t, 4, model_malloc, model_calloc, model_free> duplicateMap;
 232         for (unsigned int region = 0;region < mprot_snap->lastRegion;region++) {
 233                 if (mprotect(mprot_snap->regionsToSnapShot[region].basePtr, mprot_snap->regionsToSnapShot[region].sizeInPages * sizeof(snapshot_page_t), PROT_READ | PROT_WRITE) == -1) {
 234                         perror("mprotect");
 235                         model_print("Failed to mprotect inside of takeSnapShot\n");
 236                         exit(EXIT_FAILURE);
 237                 }
 238         }
 239         for (unsigned int page = mprot_snap->snapShots[theID].firstBackingPage;page < mprot_snap->lastBackingPage;page++) {
 240                 if (!duplicateMap.contains(mprot_snap->backingRecords[page].basePtrOfPage)) {
 241                         duplicateMap.put(mprot_snap->backingRecords[page].basePtrOfPage, true);
 242                         memcpy(mprot_snap->backingRecords[page].basePtrOfPage, &mprot_snap->backingStore[page], sizeof(snapshot_page_t));
 243                 }
 244         }
 245         mprot_snap->lastSnapShot = theID;
 246         mprot_snap->lastBackingPage = mprot_snap->snapShots[theID].firstBackingPage;
 247         mprot_take_snapshot();  //Make sure current snapshot is still good...All later ones are cleared
 248 }
 249
 250 #else   /* !USE_MPROTECT_SNAPSHOT */
 251
 252 #define SHARED_MEMORY_DEFAULT  (200 * ((size_t)1 << 20))        // 100mb for the shared memory
 253 #define STACK_SIZE_DEFAULT      (((size_t)1 << 20) * 20)        // 20 mb out of the above 100 mb for my stack
 254
 255 struct fork_snapshotter {
 256         /** @brief Pointer to the shared (non-snapshot) memory heap base
 257          * (NOTE: this has size SHARED_MEMORY_DEFAULT - sizeof(*fork_snap)) */
 258         void *mSharedMemoryBase;
 259
 260         /** @brief Pointer to the shared (non-snapshot) stack region */
 261         void *mStackBase;
 262
 263         /** @brief Size of the shared stack */
 264         size_t mStackSize;
 265
 266         /**
 267          * @brief Stores the ID that we are attempting to roll back to
 268          *
 269          * Used in inter-process communication so that each process can
 270          * determine whether or not to take over execution (w/ matching ID) or
 271          * exit (we're rolling back even further). Dubiously marked 'volatile'
 272          * to prevent compiler optimizations from messing with the
 273          * inter-process behavior.
 274          */
 275         volatile snapshot_id mIDToRollback;
 276
 277         /**
 278          * @brief The context for the shared (non-snapshot) stack
 279          *
 280          * This context is passed between the various processes which represent
 281          * various snapshot states. It should be used primarily for the
 282          * "client-side" code, not the main snapshot loop.
 283          */
 284         ucontext_t shared_ctxt;
 285
 286         /** @brief Inter-process tracking of the next snapshot ID */
 287         snapshot_id currSnapShotID;
 288 };
 289
 290 static struct fork_snapshotter *fork_snap = NULL;
 291
 292 /** @statics
 293  *   These variables are necessary because the stack is shared region and
 294  *   there exists a race between all processes executing the same function.
 295  *   To avoid the problem above, we require variables allocated in 'safe' regions.
 296  *   The bug was actually observed with the forkID, these variables below are
 297  *   used to indicate the various contexts to which to switch to.
 298  *
 299  *   @private_ctxt: the context which is internal to the current process. Used
 300  *   for running the internal snapshot/rollback loop.
 301  *   @exit_ctxt: a special context used just for exiting from a process (so we
 302  *   can use swapcontext() instead of setcontext() + hacks)
 303  *   @snapshotid: it is a running counter for the various forked processes
 304  *   snapshotid. it is incremented and set in a persistently shared record
 305  */
 306 static ucontext_t private_ctxt;
 307 static ucontext_t exit_ctxt;
 308 static snapshot_id snapshotid = 0;
 309
 310 /**
 311  * @brief Create a new context, with a given stack and entry function
 312  * @param ctxt The context structure to fill
 313  * @param stack The stack to run the new context in
 314  * @param stacksize The size of the stack
 315  * @param func The entry point function for the context
 316  */
 317 static void create_context(ucontext_t *ctxt, void *stack, size_t stacksize,
 318                                                                                                          void (*func)(void))
 319 {
 320         getcontext(ctxt);
 321         ctxt->uc_stack.ss_sp = stack;
 322         ctxt->uc_stack.ss_size = stacksize;
 323         makecontext(ctxt, func, 0);
 324 }
 325
 326 /** @brief An empty function, used for an "empty" context which just exits a
 327  *  process */
 328 static void fork_exit()
 329 {
 330         /* Intentionally empty */
 331 }
 332
 333 static void createSharedMemory()
 334 {
 335         //step 1. create shared memory.
 336         void *memMapBase = mmap(0, SHARED_MEMORY_DEFAULT + STACK_SIZE_DEFAULT, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANON, -1, 0);
 337         if (memMapBase == MAP_FAILED) {
 338                 perror("mmap");
 339                 exit(EXIT_FAILURE);
 340         }
 341
 342         //Setup snapshot record at top of free region
 343         fork_snap = (struct fork_snapshotter *)memMapBase;
 344         fork_snap->mSharedMemoryBase = (void *)((uintptr_t)memMapBase + sizeof(*fork_snap));
 345         fork_snap->mStackBase = (void *)((uintptr_t)memMapBase + SHARED_MEMORY_DEFAULT);
 346         fork_snap->mStackSize = STACK_SIZE_DEFAULT;
 347         fork_snap->mIDToRollback = -1;
 348         fork_snap->currSnapShotID = 0;
 349 }
 350
 351 /**
 352  * Create a new mspace pointer for the non-snapshotting (i.e., inter-process
 353  * shared) memory region. Only for fork-based snapshotting.
 354  *
 355  * @return The shared memory mspace
 356  */
 357 mspace create_shared_mspace()
 358 {
 359         if (!fork_snap)
 360                 createSharedMemory();
 361         return create_mspace_with_base((void *)(fork_snap->mSharedMemoryBase), SHARED_MEMORY_DEFAULT - sizeof(*fork_snap), 1);
 362 }
 363
 364 static void fork_snapshot_init(unsigned int numbackingpages,
 365                                                                                                                          unsigned int numsnapshots, unsigned int nummemoryregions,
 366                                                                                                                          unsigned int numheappages, VoidFuncPtr entryPoint)
 367 {
 368         if (!fork_snap)
 369                 createSharedMemory();
 370
 371         void *base_model_snapshot_space = malloc((numheappages + 1) * PAGESIZE);
 372         void *pagealignedbase = PageAlignAddressUpward(base_model_snapshot_space);
 373         model_snapshot_space = create_mspace_with_base(pagealignedbase, numheappages * PAGESIZE, 1);
 374
 375         /* setup an "exiting" context */
 376         char stack[128];
 377         create_context(&exit_ctxt, stack, sizeof(stack), fork_exit);
 378
 379         /* setup the shared-stack context */
 380         create_context(&fork_snap->shared_ctxt, fork_snap->mStackBase,
 381                                                                  STACK_SIZE_DEFAULT, entryPoint);
 382         /* switch to a new entryPoint context, on a new stack */
 383         model_swapcontext(&private_ctxt, &fork_snap->shared_ctxt);
 384
 385         /* switch back here when takesnapshot is called */
 386         snapshotid = fork_snap->currSnapShotID;
 387         if (model->params.nofork) {
 388                 setcontext(&fork_snap->shared_ctxt);
 389                 exit(EXIT_SUCCESS);
 390         }
 391
 392         while (true) {
 393                 pid_t forkedID;
 394                 fork_snap->currSnapShotID = snapshotid + 1;
 395                 forkedID = fork();
 396
 397                 if (0 == forkedID) {
 398                         setcontext(&fork_snap->shared_ctxt);
 399                 } else {
 400                         DEBUG("parent PID: %d, child PID: %d, snapshot ID: %d\n",
 401                                                 getpid(), forkedID, snapshotid);
 402
 403                         while (waitpid(forkedID, NULL, 0) < 0) {
 404                                 /* waitpid() may be interrupted */
 405                                 if (errno != EINTR) {
 406                                         perror("waitpid");
 407                                         exit(EXIT_FAILURE);
 408                                 }
 409                         }
 410
 411                         if (fork_snap->mIDToRollback != snapshotid)
 412                                 exit(EXIT_SUCCESS);
 413                 }
 414         }
 415 }
 416
 417 static snapshot_id fork_take_snapshot()
 418 {
 419         model_swapcontext(&fork_snap->shared_ctxt, &private_ctxt);
 420         DEBUG("TAKESNAPSHOT RETURN\n");
 421         return snapshotid;
 422 }
 423
 424 static void fork_roll_back(snapshot_id theID)
 425 {
 426         DEBUG("Rollback\n");
 427         fork_snap->mIDToRollback = theID;
 428         model_swapcontext(&fork_snap->shared_ctxt, &exit_ctxt);
 429         fork_snap->mIDToRollback = -1;
 430 }
 431
 432 #endif  /* !USE_MPROTECT_SNAPSHOT */
 433
 434 /**
 435  * @brief Initializes the snapshot system
 436  * @param entryPoint the function that should run the program.
 437  */
 438 void snapshot_system_init(unsigned int numbackingpages,
 439                                                                                                         unsigned int numsnapshots, unsigned int nummemoryregions,
 440                                                                                                         unsigned int numheappages, VoidFuncPtr entryPoint)
 441 {
 442 #if USE_MPROTECT_SNAPSHOT
 443         mprot_snapshot_init(numbackingpages, numsnapshots, nummemoryregions, numheappages, entryPoint);
 444 #else
 445         fork_snapshot_init(numbackingpages, numsnapshots, nummemoryregions, numheappages, entryPoint);
 446 #endif
 447 }
 448
 449 /** Assumes that addr is page aligned. */
 450 void snapshot_add_memory_region(void *addr, unsigned int numPages)
 451 {
 452 #if USE_MPROTECT_SNAPSHOT
 453         mprot_add_to_snapshot(addr, numPages);
 454 #else
 455         /* not needed for fork-based snapshotting */
 456 #endif
 457 }
 458
 459 /** Takes a snapshot of memory.
 460  * @return The snapshot identifier.
 461  */
 462 snapshot_id take_snapshot()
 463 {
 464 #if USE_MPROTECT_SNAPSHOT
 465         return mprot_take_snapshot();
 466 #else
 467         return fork_take_snapshot();
 468 #endif
 469 }
 470
 471 /** Rolls the memory state back to the given snapshot identifier.
 472  *  @param theID is the snapshot identifier to rollback to.
 473  */
 474 void snapshot_roll_back(snapshot_id theID)
 475 {
 476 #if USE_MPROTECT_SNAPSHOT
 477         mprot_roll_back(theID);
 478 #else
 479         fork_roll_back(theID);
 480 #endif
 481 }