Table of Contents
Software Persistent Memory
This project's initial motivation came from the need to adequately store and manage data structures that need to be persistent in the ABLE project.
Authors
- Leonardo Marmol
- Daniel Galano
- Mike Torchio
Project Meetings
- 04/24/12: Experiments update II
- 04/17/12: Experiments update
- 04/10/12: Final version experiments and writing plan
- 04/03/12: ATC'12 shepherd response – Versioning paper postponed …
- 03/29/12: SC'12 submission – initial plans
- 03/27/12: Plans for shepherding revision
- 01/12/12: Plans to address FAST review B
- 12/06/11: Analyzing FAST reviews; plans for ATC'12 submission
- 11/29/11: Future directions for SoftPM
- 11/08/11: Bugs and cleanup - Updates & Possible next steps
- 10/25/11: Bugs and cleanup
- 10/11/11: Next steps after FAST
- 09/20/11: Final writing plans
- 09/06/11: Related work finalized and evaluation structure and expts finalization
- 08/30/11: Related work, Evaluation plan, Motivation discussion
- 08/23/11: Considering various alternatives to improve evaluation
- 08/16/11: Plans for PDSW and FAST submissions
- 08/02/11: New optimization (stack allocations), new numbers, and more optimizations (path to memcpy, allocation signatures)
- 07/26/11: More on stack pointers
- 07/19/11: Stack pointer registration – partial optimization with better numbers!
- 07/12/11: Optimizing pointer and allocation management
- 06/07/11: excludeAt + offsetPointerAt, out-of-core completed; next steps – code cleanup, CIL, switch, etc.
- 05/31/11: Realloc bug fixed – related to excludeAt, Daniel potential LANL summer plans
- 05/23/11: The untractable realloc (or other) bug
- 05/17/11: Updates on debugging out-of-core (handling realloc to persistent allocation)
- 05/10/11: out-of-core restore works and initial performance data. Next steps - allocate after restore and chunk replacement
- 05/03/11: out-of-core updates: revising pointer list design
- 04/19/11: brief design overview for out-of-core
- 04/05/11: mmap updates and new applications for softpm
- 03/29/11: Out-of-Core Review and April plans
- 03/17/11: SOSP submission: Review
- 03/15/11: SOSP submission: Detailed review of eval section
- 03/11/11: Review of eval section and other eurosys comments
- 03/08/11: Reviewing SQLite performance numbers
- 03/03/11: Really short Versioning meeting
- 03/01/11: Updates on SOSP submission
- 02/22/11: Updates on SQLite (things looking up), ideas for memcached evaluation, other plans for eval section
- 02/14/11: Ideas for ferreting out non-registered allocations
- 02/10/11: Versioning meeting: updates on COW implementation and MPI app
- 02/08/11: Review of evaluation plans and current status
- 02/04/11: Out-of-core meeting: Review of status and plans to refresh the knowledge for everyone!
- 02/03/11: Versioning meeting: MPI usage update and plans for Async CP implementation
- 02/01/11: Addressing pointers into regions other than heap, 3 subsections of Evaluation
- 01/28/11: Specific Evaluation Plans for SOSP submission
- 01/27/11: Versioning tasks for this semester
- 01/25/11: SOSP submission tasks
- 12/06/10: Plans for the break (versioning et al.)
- 11/23/10: Out-of-core design discussion: initial full design
- 11/22/10: Versioning discussion - updates and next steps in implementation
- 11/16/10: Detailed procedural review for out-of-core SoftPM — Some problems identified
- 11/15/10: Initial versioning implementation updates and next steps
- 11/09/10: Detailed design review for out-of-core SoftPM
- 11/08/10: Versioning discussion
- 11/02/10: Very productive discussion on dynamic chunk loading – issues in virtual-address-space and LIMA virtual volume contiguity for allocation requests
- 11/01/10: Versioning design discussion dealing with chained chunk indirection maps
- 10/26/10: An initial approach to dynamic chunk loading based on chunk versions derived from container version
- 10/25/10: Versioning design discussion and initial implementation plans
- 10/19/10: Initial thoughts on dynamic chunk loading for out-of-core containers
- 10/18/10: Initial Versioning design
- 10/05/10: A New (much simpler) Approach to Pointer detection
- 10/04/10: Marathon brainstorming: Pointer detection
- 10/01/10: Update: HPC-CG successfully works with SoftPM
- 09/27/10: Pointer detection discussion and Eurosys tasks
- 09/13/10: Eurosys updates
- 09/07/10: Action items for Eurosys paper and task assignments
- 08/30/10: Updates, new issues to discuss in the next version of paper, and Java Persistence Library discussion
- 08/24/10: Continuation from yesterday: Plans for resubmission to Eurosys, reviewer comments and action items
- 08/23/10: First Fall'10 meeting: Plans for resubmission to Eurosys, reviewer comments and action items
- 05/06/10: Another pre-OSDI meeting
- 05/04/10: Pre-OSDI meeting
- 05/03/10: Evaluation section performance and overhead discussion
- 04/29/10: Reducing overhead with malloc interposition and evaluation update
- 04/27/10: On using LLVM and backup plans
- 04/26/10: Evaluation section updated graphs and Jinpeng's comments on paper
- 04/19/10: Evaluation section structure and experiments
- 04/13/10: Versioned containers discussion and Alternatives to C++ source translator (LLVM and EDG)
- 04/12/10: Feedback of OSDI draft
- 04/06/10: Sandia - OpenC++ template solutions, memory closure overhead
- 04/05/10: OSDI paper structure – detailed discussion
- 04/02/10: OSDI paper structure – initial discussion
- 04/01/10: HotStorage pre-submission discussion
- 03/30/10: Sandia plans
- 03/30/10: Hotstorage submission
- 03/29/10: C++ template issues, simplification of CIL translation
- 03/29/10: Plans for HotStorage submission
- 03/15/10: Casting detection in C, pointer deregistration in C++, VivaCore, Initial implementation of auto container discovery
- 03/09/10: HotStorage submission plan + OpenC++ issues with Prime
- 03/08/10: Detecting casting operations – is this the only way? and what about unregistering pointers at the right scope?
- 03/02/10: Initial plans for Sandia work
- 03/01/10: Updates and Feedback on SoftPM from FAST'10
- 02/22/10: Pointer detection for void* types via casting (invalid pointer recovery issues)
- 02/15/10: Refining algorithms of automatic container discovery
- 02/08/10: Automatic container discovery - detailed design discussion
- 02/01/10: Automatic container discovery - preliminary design discussion
- 01/28/10: Paper comments and async commits + comments on DTAC paper
- 01/25/10: Pointer detection in arrays and multiple levels of pointers
- 01/19/10: Rethinking pointer detection – arrays and pointer arrays
- 01/07/10: Debugging 32-bit softpm implementation
- 01/04/10: Updates after the break
- 12/21/09: Experiment details and evaluation task-list
- 12/14/09: Evaluation tasks for Leonardo and Daniel and update on OpenC++ implementation
- 12/11/09: Evaluation table for pointer detection and mat-mult, map-reduce, and updatedb-locate applications
- 12/08/09: Comments on introduction, motivation, and alternative storage mechanisms, online chained workflow case studies
- 12/04/09: ATC paper revision
- 12/01/09: ATC paper content and evaluation plan
- 11/30/09: More pointer complexities in C
- 11/25/09: CIL implementation done, evaluation plans + OpenC++ implementation changes
- 11/24/09: USENIX ATC paper discussion
- 11/17/09: USENIX ATC paper contributions and structure
- 11/16/09: Execution containers overview
- 11/10/09: Another checkpointing library
- 11/09/09: Updates on CIL/OpenC++ implementations
- 11/03/09: Debugging stack restore
- 11/02/09: CIL/OpenC++ implementation updates, and execution container v.s. full process checkpointing
- 10/27/09: State checkpointing implementation issues
- 10/26/09: CIL implementation progress and discussion of problems with OpenC++
- 10/12/09: State of CIL/OpenC++ and designs for automatic container population
- 10/06/09: Stack saving alternatives and Execution v.s. data containers
- 10/02/09: CIL/OpenC++ specific paper and various alternatives for generic solution
- 09/28/09: Handling recursion and other outstanding implementation items
- 09/21/09: Handling recursive applications with SoftPM
- 09/21/09: Lexer,OpenC++ transformer techniques and paper direction
- 09/16/09: OpenC++ and Yacc-based source transformation
- 09/16/09: Long-term project plans and PDSW paper(Ming, Jason, Jorge and Raju)
- 09/14/09: PDSW paper plans (Jorge and Raju)
- 09/10/09: CIL - input from Jinpeng
- 08/31/09: Design for source-to-source automatic pointer detection
- 08/24/09: Automatic pointer detection & New direction with restoring full process state
- 08/20/09: PDS initial discussion with Leonardo
- 04/28/09: Brief review of experiment results
- 04/16/09: Reviewing experiments and new design for LCW
- 03/20/09: Copy-on-write optimization
- 03/12/09: Debugging unwanted read behavior and next project directions
- 03/06/09: Discussion of irrelevance of non-crew experiments + Definition of LCW configuration
- 03/05/09: Refining experiments for SOSP
- 02/19/09: SSD CREW clarification and experiments for SOSP
- 02/17/09: SSD CREW design discussion
- 02/16/09: Discussing comments in LIMA section and CREW design
- 02/09/09: Pre-processing pPointerAt information
- 02/05/09: Reorganizing LIMA section comments, free semantics, fragmentation
- 02/02/09: CREW design change, writing tasks for SOSP
- 01/20/09: Planning for SOSP submission, new experiments, metrics, etc.
- 01/07/09: ABLE paper resubmission to UTC discussion
- 01/06/09: Experiments design discussion
- 01/05/09: Pointer restore and Paper planning
- 01/02/09: Pointer management and paper writing
- 12/29/08: Introduction layout comments, micro-benchmark design (linked lists, variable size structs), CREW write granularity
- 12/23/08: Micro-benchmarks design discussion
- 12/15/08: Modeling and Experiments discussion
- 12/08/08: More terminology discussion
- 12/05/08: Terminology discussion
- 12/04/08: Discussion on WASCR and its relation to PERMA
- 12/02/08: Architecture and control flow
- 12/01/08: Detailed operation of alloc, flush, and restore
- 11/26/08: Logging writes — Chunk-map to eliminate cleaning requirement
- 11/24/08: Metadata structures finalized and Layout discussion (including log-structuring block writes)
- 11/17/08: ext3/reiserfs layout review & Persistent Metadata structures discussion
- 11/13/08: Related work (Persistent object databases) & Brief layout discussion
- 10/20/08: Design Discussion - Metadata Management
- 10/16/08: Design Discussion - Restore Operation
- 10/13/08: Design Discussion - Container and API
- 10/09/08: Motivation and Design Discussion
Hecura Proposal Meetings
- 04/03/09: New API (with Jorge)
- 03/30/09: Proposal goals and detailed discussion on language,OS,interface,applications
- 03/30/09: PFS ideas for the proposal (morning with Ming)
- 03/23/09: Ideas for PFS and SOAP integration (afternoon with Ming)
- 03/23/09: Proposal scope expansion with versioning, staged simulations (towards the end) and restore semantics (beginning)
- 03/16/09: Proposal agenda will be based on Persistent Memory, Local Disk and Parallel FS backend options, requirements of the backend, possible evaluation component
- 03/11/09: Initial discussion about proposal possibilities
Project Goals
Design
Architecture
There are two mayor subsystems: the data manager and the layout manager. The data manager exports an API that allows applications handling of containers, it also manages all the metadata of the containers and sends reads and write requests to the layout manager assuming a logical linear block address. The layout manager provides a virtual address space to the data manager, it uses chunks as its basic allocation and operation unit, these can be later remapped to a different location in an effort to improve performance.
Persistent Copy Update Policy
- Always update
- Update on demand
- Time interval based
API
- pcalloc(magic, size): Create a new container, which consists of the following steps:
- Check if the magic (unique ID) is valid.
- Create a container_meta structure to hold the metadata for that container.
- Allocate a page (4KB) of memory and assign it to the container_meta.
- Populate the container_meta by setting the size of the pcontainer, setting the policy to default, set dirty bit and initializing the page table head.
- palloc(magic, size): Allocates the requested amount of persistent memory in the given container. This consists of the following steps:
- Check the page table and obtain a page that allows allocations of the size specified. If yes, proceed to step 2. If no, then allocate a new page (using container_add_page) and initialize it.
- For the selected page, mark the first slot available as used in the bitmap.
- Return the memory reference.
- pfree(magic, mem_ref): Frees a portion of persistent memory previously allocated. This consists of the following steps:
- Locate the page table entry referenced by mem_ref.
- Set the corresponding location as available in the free space bitmap.
- Check if corresponds to a pointer, or if there are pointers in the range that was allocated. If such pointer exists in the list of pointers delete them.
- (optional) set the freed space to zero.
- set_upd_pol(magic, policy): Sets the update policy for the given container. This consists of the following steps:
- Update the policy field for the given container.
- pstore(magic): Updates the persistent media copy of the container. This consists of the following steps:
- Identify all pages marked as dirty for the given container.
- For each dirty page, if it has a corresponding persistent page issue write. If no, then allocate persistent page issue write.
- Note that the update operation is synchronous, thus all application write I/O will need to wait for the storing to finish.
- prestore(magic): Restores a container from the persistent media. This consists of the following steps:
- Identify the metadata page for the container and load it.
- Load the page table, and for each loaded page, change the pointers to reflect the new memory page reference.
- Return pointer to pcontainer.
- pointerat(magic, mem_ref): Tells the container that at location mem_ref there is a memory reference (pointer). This consists of the following steps:
- Locate the page table entry referenced by mem_ref.
- Add an entry in the list of pointers.
Detailed Operations
- palloc:
- persistant_point:
- prestore:
Current Challenges and Open Questions
- How to transparently detect where pointers are located in memory.
A: During type analysis phase of the compilation this information is known.
Installation Instructions
These instructions will guide through the installation of SoftPM on a Ubuntu system. These instruction may not work on other distributions.
SoftPM depends on the following 3er party software and hardware
- GNU/Linux 64bits
- glib : GLib Software Utility Library [http://www.gtk.org/]
- svn : subversion [http://subversion.apache.org/]
- ocaml : Ocaml with OO extension [http://caml.inria.fr/]
- CIL : CIL Infrastructure for C Program Analysis and Transformation [http://www.cs.berkeley.edu/~necula/cil/]
- LLVM : Low Level Virtual Machine [http://llvm.org/]
Installing the dependencies
- SoftPM currently only works on 64bits GNU/Linux systems. Run the following command to check that you have the required architecture.
$ uname --all Linux maxwell 2.6.32-24-generic #42-Ubuntu SMP Fri Aug 20 14:21:58 UTC 2010 x86_64 GNU/Linux
- GLIB provides implementations of various data structures that are widely use in SoftPM. To install glib, run the following command:
$ sudo aptitude install libglib2.0-0-dev
- SoftPM uses subversion and its version control system. You need to install svn in order to get a copy of the source code. To install svn, run the following
command:
$ sudo aptitude install subversion
- Ocaml is needed by CIL, so we must install it before compiling CIL. To install ocaml run the following command:
$ sudo aptitude install ocaml-nox
- CIL is a C-to-C source transformer. SoftPM uses CIL to automatically detect pointer types and memory allocations in C source code. To install CIL, run the following command.
$ svn co https://doomsday.cs.fiu.edu/svn/pds/cil/
This will create a new folder called cil within the current folder. Now we need to compile CIL. To do so, run the following commands:
$ ./configure #this will setup the makefiles $ make #to compile cil and all its modules
At this point, you should have cil compiled. It is convenient to add the following folders to $PATH variable.
PATH_TO_FOLDER/cil/bin
PATH_TO_FOLDER/cil/obj/x86_LINUX
This can be done by adding the following line at the end of ~/.bashrc
export PATH=$PATH:/PATH_TO_FOLDER/cil/bin:/PATH_TO_FOLDER/cil/obj/x86_LINUX/
where PATH_TO_FOLDER is the path to the folder containing cil. Now we update $PATH by running the following command:
$ source ~/.bashrc
To check that CIL have been successfully installed, run the following command and make sure you get a similar output:
$ cilly | grep softpm /home/lmarmol/Projects/cil/cil-1.3.7/obj/x86_LINUX/cilly.asm.exe -help --dosoftpm Enable source transformations for softpm --dosoftpmcounter Enable softpmcounter: prints a message for avery SoftPM rule found --dosoftpmcpp Enable softpmcpp: pre-processor for LLVM generated c-code
- LLVM stands for Low Level Virtual Machines, and it is a full compiler (front-end and back-end). SoftPM uses LLVM to convert C++ code into C code. Then, CIL is used to parse the C code generated by LLVM and apply the necessary transformations. To install LLVM, run the following command:
$ sudo aptitude install llvm llvm-gcc
To see an example of how to convert C++ code in C code using LLVM, follow this link http://llvm.org/docs/FAQ.html#translatecxx
Installing and compiling the source code
Now that we have installed all the dependecies, we can check-out the SoftPM source code from the svn server. To do so, run the following command:
svn co https://doomsday.cs.fiu.edu/svn/pds/code/src/
This will create a new folder named src within the current folder. Change directories into that folder and run the following commands to compilie SoftPM:
$ source config.sh $ make
If everything worked out as planed, you should now have a working version of SoftPM. To make sure that everything is working, change directory to tests and run the following command:
$ ./run-cmp.sh btree_simple/ ... tree_node: 2142757034 tree_node: 2145174067 tree_node: 2145854098 tree_node: 2147469841 tree_node_cmp: 1
Notice that the last line is tree_node_cmp: 1, which is the expected output.