Elyze: enabling safe parallelism in event-driven servers

ABSTRACT

It is increasingly necessary for applications to take advantage of concurrency in order to increase performance. Unfortunately, it is notoriously difficult to write correct concurrent applications as they are subject to a variety of subtle bugs that can be difficult to reproduce. We advocate an approach to developing these applications, particularly servers, in which a conservative static analysis determines when code segments may safely run in parallel, and a runtime scheduler respects these constraints, an approach that is safe by default.

We have built an analyzer for event-driven servers written in C that detects unsafe data sharing between event handlers. When the analysis determines that two event handlers might access the same data, whether through a global variable or through the request-specific data structure passed to the handlers, it produces a constraint on the concurrent execution of those handlers. We are building a complementary runtime system that will use these constraints to safely run event handlers concurrently.

We have analyzed thttpd, an event-driven web server, and show that our analyzer finds safe parallelism in this server, enabling increased performance without the hazards of threads and locks.

REFERENCES

• 1: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen (DIKU report 94/19), May 1994.
• 2: Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277678]
• 3: Kostas Bousias , Nabil Hasasneh , Chris Jesshope, Instruction Level Parallelism through Microthreading---A Scalable Approach to Chip Multiprocessors, The Computer Journal, v.49 n.2, p.211-233, March 2006 [doi>10.1093/comjnl/bxh157]
• 4: Edouard Bugnion , Jennifer M. Anderson , Todd C. Mowry , Mendel Rosenblum , Monica S. Lam, Compiler-directed page coloring for multiprocessors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.244-255, October 01-04, 1996, Cambridge, Massachusetts, United States
• 5: Bryan Chan , Tarek S. Abdelrahman, Run-Time Support for the Automatic Parallelization of Java Programs, The Journal of Supercomputing, v.28 n.1, p.91-117, April 2004 [doi>10.1023/B:SUPE.0000014804.20789.21]
• 6: Sigmund Cherem , Trishul Chilimbi , Sumit Gulwani, Inferring locks for atomic sections, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 7: Manuvir Das, Unification-based pointer analysis with directional assignments, ACM SIGPLAN Notices, v.35 n.5, p.35-46, May 2000
• 8: Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.230-241, June 20-24, 1994, Orlando, Florida, United States
• 9: H. K. E. M. Nystrom and W. Hwu. Bottom-up and top-down context-sensitive summary-based pointer analysis. In Proc. 11th Static Analysis Symposium, Aug. 2004.
• 10: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 11: Michael Emmi , Jeffrey S. Fischer , Ranjit Jhala , Rupak Majumdar, Lock allocation, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 12: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 13: Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.219-232, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: Cormac Flanagan , Shaz Qadeer, A type and effect system for atomicity, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 15: C. Jesshope. Scalable instruction-level parallelism. Lecture Notes in Computer Science, 3133, 2004.
• 16: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
• 17: Bill McCloskey , Feng Zhou , David Gay , Eric Brewer, Autolocker: synchronization inference for atomic sections, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.346-358, January 11-13, 2006, Charleston, South Carolina, USA
• 18: Armand Navabi , Xiangyu Zhang , Suresh Jagannathan, Quasi-static scheduling for safe futures, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345212]
• 19: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 20: David J. Pearce , Paul H.J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis of C, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.4-es, November 2007 [doi>10.1145/1290520.1290524]
• 21: Constantine D. Polychronopoulos , Milind B. Girkar , Mohammad Reza Haghighat , Chia Ling Lee , Bruce Leung , Dale Schouten, Parafrase-2: an environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors, International Journal of High Speed Computing, v.1 n.1, p.45-72, May 1989 [doi>10.1142/S0129053389000044]
• 22: N. Provos. Libevent -- an asynchronous event notification library, 2000. http://www.monkey.org/~provos/libevent/.
• 23: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 24: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 25: thttpd -- tiny/turbo/throttling http server. http://www.acme.com/software/thttpd.
• 26: Tor: anonymity online. http://www.torproject.org/.
• 27: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• 28: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
• 29: John Zahorjan , Cathy McCann, Processor scheduling in shared memory multiprocessors, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.214-225, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 30: N. Zeldovich, A. Yip, F. Dabek, R. Morris, D. Mazières, and F. Kaashoek. Multiprocessor support for event-driven programs. In Proc. USENIX 2003 Annual Technical Conference, June 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Threads; Synchronization

General Terms:
Performance, Reliability

Keywords:
concurrency scheduling, static analysis