Susmit Sarkar

Susmit Sarkar

Auto-generated profile, based on publicly available information

Susmit Sarkar

University of St. Andrews, St. Andrews, United Kingdom

Research Focus & Metrics

Academic Career Length

24Years (2003-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 July 2010 in Communications of the ACM
Verified
Journal Article
Open access
PSPeter Sewell
Peter Sewell
SSSusmit Sarkar
Susmit Sarkar
SOScott Owens
Scott Owens
FNFrancesco Zappa Nardelli
Francesco Zappa Nardelli
MMMagnus O. Myreen
Magnus O. Myreen
Exploiting the multiprocessors that have recently become ubiquitous requires high-performance and reliable concurrent systems code, for concurrent data structures, operating system kernels, synchronization libraries, compilers, and so on. However, concurrent programming, which is always challenging, is made much more so by two problems. First, real multiprocessors typically do not provide the sequentially consistent memory that is assumed by most work on semantics and verification. Instead, they have relaxed memory models, varying in subtle ways between processor families, in which different hardware threads may have only loosely consistent views of a shared memory. Second, the public vendor architectures, supposedly specifying what programmers can rely on, are often in ambiguous informal prose (a particularly poor medium for loose specifications), leading to widespread confusion. In this paper we focus on x86 processors. We review several recent Intel and AMD specifications, showing that all contain serious ambiguities, some are arguably too weak to program above, and some are simply unsound with respect to actual hardware. We present a new x86-TSO programmer's model that, to the best of our knowledge, suffers from none of these problems. It is mathematically precise (rigorously defined in HOL4) but can be presented as an intuitive abstract machine which should be widely accessible to working programmers. We illustrate how this can be used to reason about the correctness of a Linux spinlock implementation and describe a general theory of data-race freedom for x86-TSO. This should put x86 multiprocessor system building on a more solid foundation; it should also provide a basis for future work on verification of such systems.

1 January 2009
Verified
Book Chapter
Closed access
PDF file
SOScott Owens
Scott Owens
SSSusmit Sarkar
Susmit Sarkar
PSPeter Sewell
Peter Sewell

26 January 2011
Verified
Conference Paper
Open access
PDF file
MBMark Batty
Mark Batty
SOScott Owens
Scott Owens
SSSusmit Sarkar
Susmit Sarkar
PSPeter Sewell
Peter Sewell
TWTjark Weber
Tjark Weber
Shared-memory concurrency in C and C++ is pervasive in systems programming, but has long been poorly defined. This motivated an ongoing shared effort by the standards committees to specify concurrent behaviour in the next versions of both languages. They aim to provide strong guarantees for race-free programs, together with new (but subtle) relaxed-memory atomic primitives for high-performance concurrent code. However, the current draft standards, while the result of careful deliberation, are not yet clear and rigorous definitions, and harbour substantial problems in their details. In this paper we establish a mathematical (yet readable) semantics for C++ concurrency. We aim to capture the intent of the current (`Final Committee') Draft as closely as possible, but discuss changes that fix many of its problems. We prove that a proposed x86 implementation of the concurrency primitives is correct with respect to the x86-TSO model, and describe our Cppmem tool for exploring the semantics of examples, using code generated from our Isabelle/HOL definitions. Having already motivated changes to the draft standard, this work will aid discussion of any further changes, provide a correctness condition for compilers, and give a much-needed basis for analysis and verification of concurrent C and C++ programs.

4 June 2011
Verified
Conference Paper
Open access
PDF file
SSSusmit Sarkar
Susmit Sarkar
PSPeter Sewell
Peter Sewell
JAJade Alglave
Jade Alglave
LMLuc Maranget
Luc Maranget
DWDerek Williams
Derek Williams
International audienceExploiting today's multiprocessors requires high-performance and correct concurrent systems code (op-timising compilers, language runtimes, OS kernels, etc.), which in turn requires a good understanding of the observable processor behaviour that can be relied on. Unfortunately this Exploiting today’s multiprocessors requires high-performance and correct concurrent systems code (optimising compilers, language runtimes, OS kernels, etc.), which in turn requires a good understanding of the observable processor behaviour that can be relied on. Unfortunately this critical hardware/software interface is not at all clear for several current multiprocessors. In this paper we characterise the behaviour of IBM POWER multiprocessors, which have a subtle and highly relaxed memory model (ARM multiprocessors have a very similar architecture in this respect). We have conducted ex-tensive experiments on several generations of processors: POWER G5, 5, 6, and 7. Based on these, on published de-tails of the microarchitectures, and on discussions with IBM staff, we give an abstract-machine semantics that abstracts from most of the implementation detail but explains the be-haviour of a range of subtle examples. Our semantics is ex-plained in prose but defined in rigorous machine-processed mathematics; we also confirm that it captures the observ-able processor behaviour, or the architectural intent, for our examples with an executable checker. While not officially sanctioned by the vendor, we believe that this model gives a reasonable basis for reasoning about current POWER mul-tiprocessors. Our work should bring new clarity to concurrent systems programming for these architectures, and is a necessary precondition for any analysis or verification. It should also inform the design of languages such as C and C++, where the language memory model is constrained by what can be efficiently compiled to such multiprocessors

26 January 2010 in Journal of Functional Programming
Verified
Journal Article
Closed access
PDF file
PSPeter Sewell
Peter Sewell
FNFrancesco Zappa Nardelli
Francesco Zappa Nardelli
SOScott Owens
Scott Owens
GPGilles Peskine
Gilles Peskine
TRThomas Ridge
Thomas Ridge
RSRok Strniša
Rok Strniša
Semantic definitions of full-scale programming languages are rarely given, despite the many potential benefits. Partly this is because the available metalanguages for expressing semantics – usually either for informal mathematics or the formal mathematics of a proof assistant – make it much harder than necessary to work with large definitions. We present a metalanguage specifically designed for this problem, and a tool, Ott, that sanity-checks such definitions and compiles them into proof assistant code for Coq, HOL, and Isabelle/HOL, together with code for production-quality typesetting, and OCaml boilerplate. The main innovations are (1) metalanguage design to make definitions concise, and easy to read and edit; (2) an expressive but intuitive metalanguage for specifying binding structures; and (3) compilation to proof assistant code. This has been tested in substantial case studies, including modular specifications of calculi from the TAPL text, a Lightweight Java with Java JSR 277/294 module system proposals, and a large fragment of OCaml (OCaml light , 310 rules), with mechanised proofs of various soundness results. Our aim with this work is to enable a phase change: making it feasible to work routinely, without heroic effort, with rigorous semantic definitions of realistic languages.

1 January 2010
Verified
Book Chapter
Closed access
PDF file
JAJade Alglave
Jade Alglave
LMLuc Maranget
Luc Maranget
SSSusmit Sarkar
Susmit Sarkar
PSPeter Sewell
Peter Sewell