ADDING OPERATING SYSTEM STRUCTURE TO LANGUAGE-BASED PROTECTION

 

 

 

 

 

 

 

A Dissertation

Presented to the Faculty of the Graduate School

of Cornell University

in Partial Fulfillment of the Requirements for the Degree of

Doctor of Philosophy

 

 

 

 

 

 

 

 

by

Chris topher K.irk Hawblitzel

August 2000

 

 

 

 

 

 

 

 

 

 

 

 

© 2000 Chris topher K irk. Hawblitzel

 

ADDING OPERATING SYSTEM STRUCTURE TO LANGUAGE-BASED PROTECTION

Chris topher K.irk Hawblitzel, Ph.D.

Cornell University 2000

 

The abstract starts hereExtensible Internet applications increasingly rely on language safety for protection, rather than using protection mechanisms based on virtual memory.  For example, the Java language now provides protection for applets, servlets, agents and active networks.  Unfortunately, typical safe language systems do not have the support for resource control, revocation, and on-demand program termination present in traditional operating systems.  Naive attempts to add these features to a language can easily backfire:  Sun recently deprecated Java's thread termination methods because of subtle interactions with Java's synchronization and abstraction mechanisms.

In this thesis, I argue that these problems arise from a lack of clear structure in safe language systems.  Often, these systems allow objects, threads, and code to pass freely from one program to another, blurring the boundaries between programs.  To restore the boundaries, I introduce the idea of a safe language task that encapsulates a program's objects, threads, and code, and I argue that a system based on the task model can provide strong and simple guarantees about resource control, thread management, termination, revocation, and whole-program optimization.  I present two implementations of the task model:  the J-Kernel, which uses Java remote method invocation for inter-task communication, and Luna, which extends Java's type system to express the task model directly.

BIOGRAPHICAL SKETCH

 

Biographical sketch starts hereChris Hawblitzel was born in Kansas City, Missouri in 1973.  He started college at UC-Berkeley in 1989 and received a bachelor's degree in physics there in 1993.  He began graduate school at Cornell studying computational physics, and switched to computer science in Spring of 1996.

ACKNOWLEDGMENTS

 

There are so many people to whom I owe thanks that I cannot hope to repay them all here.  Most of all I would like to thankAcknowledgments start here my parents, who introduced me to computers in the first place, fortheir boundless supportand encouragement, their warm sense of humor, and theirunfailing integrity.  My mother and father are lifelong teachers and lifelong learners—it was they who taught me how to learn and from them I learned how to teach.

Many thanks go to Thorsten von Eicken and Greg Morrisett for opening up entire new worlds to explore, and for straightening every crooked path that I traveled on.  Their ideas formed the basis for this thesis, and their advice molded my own shakyproposalsinto something solid and practical.  Working with them was both an honor and a pleasure.

I am greatly indebted toGreg Czajkowski, Chi-Chao Chang, Deyu Hu, and Dan Spoonhower for transformingthe J-Kernel from anisolatedprototype into a real working environment.  Without them, the J-Kernelwould never have hatched from its shell.

Thanks to Lidong Zhou, Ulfar Erlingsson, Fred Schneider, Andrew Myers, Brian Smith, Hal Perkins, Jay Lepreau, Wilson Hsieh, and Pat Tullmann,whose insights and commentssignificantly influenced the content of this thesis.

Thanks to the Marmot group for sharing a stellar compiler with us.

Thanks for moral and practicalsupport toeveryone in Greg Morrisett's group, including Fred Smith, Dave Walker, Neal Glew, Dan Grossman, Stephanie Weirich, Steve Zdancewic, and Karl Crary, as our own group was slowly decimated by graduation and employment.  Thanks to Greg Czajkowski, Chi-Chao Chang, Deyu Hu, Soam Acharya, Sugata Mukhopadhyay, Wei Tsang Ooi, Eva Luther, and Dan Spoonhower for such an intellectually stimulating and enjoyable work environment, particularly when the work consisted of discussing weighty topics like the future of electronic commerce or the virtues of Polish Hip-hop.  Finally, thanks to my officemates, Tibor Janosi and Matt Fleming;Ishould probably dropby someday.  Matt, of course, knows what's in the black bag, but others can savor the mystery.

TABLE OF CONTENTS

Chapter One: INTRODUCTION                                                                          1

1.1       Motivation: the challenges of a programmable internet                     3

1.2       Protection mechanisms                                                                            5

1.2.1     Address-based protection mechanisms                                    5

1.2.2     Type-based protection mechanisms                                          7

1.3       Where does language-based protection fall short?                           10

1.3.1     Termination                                                                                 11

1.3.2     Revocation                                                                                   13

1.3.3     Inter-program dependencies and side effects                        14

1.3.4     Resource Accounting                                                                 15

1.3.5     Dynamic loading limits optimizations                                    16

1.4       The task                                                                                                    17

1.4.1     Distinguishing local and remote objects                                 19

Chapter Two: The J-Kernel                                                                           22

2.1       Java Remote Method Invocation                                                          24

2.2       J-Kernel capabilities                                                                               27

2.3       Capability implementation                                                                   30

2.3.1     Revocation                                                                                   31

2.3.2     Thread segments                                                                         32

2.3.3     Copying arguments                                                                    34

2.4       Creating and terminating tasks                                                             36

2.5       Task linking                                                                                             39

2.5.1     Creating resolvers                                                                       41

2.6       J-Kernel micro-benchmarks                                                                   43

2.6.1     Null LRMI                                                                                    43

2.6.2     Threads                                                                                         44

2.6.3     Argument Copying                                                                     45

2.7       Application benchmarks                                                                        46

2.8       Conclusions                                                                                             48

Chapter Three: Luna design                                                                        49

3.1       Remote pointers and revocation                                                          50

3.2       Sharing data with remote pointers                                                       52

3.3       Method invocations on remote pointers                                             55

3.3.1     Copying remote objects                                                             56

3.3.2     Combining copies and method invocation                             59

3.4       Type system design                                                                                60

Chapter Four: Luna Implementation and performance         64

4.1       Extended bytecode format                                                                    64

4.2       Implementing remote pointers                                                             65

4.2.1     Special Java pointer operations: equality, instanceof, checkcast, synchronization       68

4.2.2     Synchronization                                                                           69

4.3       Method invocations and threads                                                          71

4.3.1     Terminating threads                                                                   83

4.4       Garbage collection and safe points                                                      89

4.5       Tasks and dynamic loading                                                                  93

4.6       Micro-benchmarks and optimizations                                               101

4.6.1     Caching permit information                                                    112

4.7       Luna web server                                                                                    165

Chapter Five: Alternate ApProaches to the Task Model      174

5.1       Termination, task boundaries                                                             188

5.1.1     Terminating threads                                                                 192

5.1.2     Terminating code                                                                      196

5.1.3     Terminating threads and code                                                205

5.2       Sharing                                                                                                    207

5.2.1     Sharing in non-object-oriented languages                            214

5.2.2     Revocation                                                                                 218

5.3       Enforcing the task model, symmetric vs. asymmetric communication  221

5.3.1     Symmetric and asymmetric communication                        230

5.3.2     Server-centric vs. client-centric design                                  232

5.4       Resource accounting policy                                                                239

5.5       Garbage collection                                                                                246

5.5.1     Accounting for collection time                                                251

5.6       Conclusions                                                                                           255

Chapter Six: conclusions                                                                            257

bibliography                                                                                                       265

Chapter One: INTRODUCTION                                                                                              1

1.1                                                                                              Motivation: the challenges of a programmable internet                                                                                              3

1.2                                                                                              Protection mechanisms                                                                                              5

1.2.1                                                                                              Address-based protection mechanisms                                                                                              6

1.2.2                                                                                              Type-based protection mechanisms                                                                                              7

1.3                                                                                              Where does language-based protection fall short?                                                                                              12

1.3.1                                                                                              Termination                                                                                              12

1.3.2                                                                                              Revocation                                                                                              15

1.3.3                                                                                              Inter-program dependencies and side effects                                                                                              16

1.3.4                                                                                              Resource Accounting                                                                                              17

1.3.5                                                                                              Dynamic loading limits optimizations                                                                                              18

1.4                                                                                              The task                                                                                              19

1.4.1                                                                                              Distinguishing local and remote objects                                                                                              21

Chapter Two: The J-Kernel                                                                                              24

2.1                                 &