Computer Systems A Programmers Perspective(second edition)

This page intentionally left blank Computer Systems A Programmer's Perspective Randal e. Bryant Carnegie Mellon Universit David. ohallaron Carnegie mellon University and Intel Labs Prentice hall Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London madrid Milan Munich Paris Montreal Toronto Delhi mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo Editorial director: marcia horton Editor-in-Chief: michael hirsch Acquisitions Editor: Matt Goldstein Editorial Assistant: Chelsea bell Director of Marketing Margaret Waples Marketing Coordinator: Kathryn Ferranti Managing editor: Jeff Holcomb Senior Manufacturing Buycr: Carol Melville Art Director: Linda knowles Cover desi Elena sido Image Interior Permission Coordinator: Richard rodrigues Cover Art: C RandalE Bryant and David R. OHallaron Media Producer Katelyn Boller Project Management and Interior Design: Paul C Anagnostopoulos, Windfall Software Composition: Joe Snowden, Coventry Composition Printer/Binder: Edwards brothers Cover Printer: Lehigh-Phoenix Color/Hagerstown Copyright C 2011, 2003 by Randal E. Bryant and David r. O Hallaron. All rights reserved Manufactured in the United States of America. This publication is protected by Copyright and permission should be obtained from the publisher prior to any prohibited reproduction storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116 Many of the designations by manufacturers and seller to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps. Library of Congress Cataloging-in-Publication Data Bryant, Randal Computer systems: a programmers perspective /Randal F. Bryant, David R O'Hallaron --2nd ed p. cm Includes bibliographical references and index. ISBN-13:978-0-13-610804-7( alk. paper) ISBN-10:0-13-610804-0(alk. paper) 1. Computcr systcms. 2. Computers. 3. Tclccommunication. 4. Uscr interfaces Computer systems) I O'Hallaron, David Richard. II. Title QA76.5B7952010 004dc22 2009053083 10987654321EB—1413121110 PEARSON ISBN10:0-13-610804-0 ISBN13:978-0-13-610804-7 To the students and instructors of the 1 5-213 course at Carnegie Mellon University, for inspiring us to develop and refine the material for this book This page intentionally left blank Contents Preface xix about the authors xxxiii A Tour of Computer Systems 1 1.1 Information is bits Context 1.2 Programs Arc Translated by Other Programs into Diffcrcnt Forms 4 1.3 It Pays to Understand How Compilation Systems Work 6 1.4 Proccssors Rcad and Intcrprct Instructions Stored in Memory 7 1.4.1 Hardware Organization of a system 7 1.4.2 Running the hello Program 10 1.5 Caches matter 12 1.6 Storage Devices Form a Hierarchy 13 1.7 The Operating System Manages the Hardware 14 1.7.1 Processes 16 1.7.2 Threads 17 1.7.3 Virtual Memory 17 1.7.4 Files 19 1.8 Systems Communicate with Other Systems Using Networks 20 1.9 Important Themes 21 1.9.1 Concurrency and parallelism 21 1.9.2 The Importance of Abstractions in Computer Systems 24 1.10 Summary 25 Bibliographic Notes 26 PartI Program Structure and Execution 2 Representing and manipulating Information 29 2.1 Information Storage 33 2.1.1 Hexadecimal Notation 34 2.1.2 Words 38 2.1.3 Data sizes 38 VIl viii Contents 2.1.4 Addressing and Byte Ordering 39 2.1.5 Representing Strings 46 2.1.6 Representing Code 47 2.1.7 Introduction to Boolcan Algcbra 48 2. 1. 8 Bit-Level Operations in C 51 2. 1.9 Logical Opcrations in C 54 2.1.10 Shift Operations in C 54 nteger Representations 56 2.2.1 Integral Data Types 57 2.2.2 Unsigned Encodings 58 2.2.3 Two's-Complement Encodings 60 2.2. 4 Conversions Between Signed and Unsigned 65 2.2.5 Signed VS Unsigned in C 69 2.2.6 Expanding the Bit Representation of a Number 71 2.2.7 Truncating Numbers 75 2.2.8 Advice on Signed vs Unsigned 76 2.3 Integer Arithmetic 79 2.3.1 Unsigned Addition 79 2.3.2 Twos-Complement Addition 83 2.3.3 Two's-Complement Negation 87 23. 4 Unsigned Multiplication 88 2.3.5 Twos-Complement multiplication 89 2.3.6 Multiplying by Constants 92 2.3.7 Dividing by powers of two 95 2.3.8 Final Thoughts on Integer Arithmetic 98 2.4 Floating Point 99 2. 4.1 Fractional binary Numbers 100 2.4.2 IEEE Floating-Point Representation 103 2.4.3 Example Numbers 10.5 2.4.4 Rounding 110 2.4.5 Floating-Point Operations 113 2.4.6 Floating point in C 114 2.5 Summary 118 Bibliographic Notes 119 Homework problems 119 Solutions to practice problems 134 Machine-Level Representation of Programs 153 3.1 A Historical Perspective 156 3.2 Program Encodings 159 Contents ix 3.2.1 Machine-Level Code 160 3.2.2 Codc Examples 162 3.2.3 Notes on Formatting 165 3.3 Data Formats 167 3.4 Accessing Information 168 3.4.1 Operand Specifiers 169 3.4.2 Data movement Instructions 171 3.4.3 Data Movement Example 174 3.5 Arithmetic and Logical Operations 177 3.5.1 Load effective address 177 3.5.2 Unary and Binary Operations 178 3.5.3 Shift Operalions 179 3.5.4 Discussion 180 3.5.5 Special Arithmetic Operations 182 3.6 Control 185 3.6.1 Condition codes 185 3.6.2 Accessing the Condition codes 187 3.6.3 Jump Instructions and Their Encodings 189 3.6.4 Translating Conditional Branches 193 3.6.5 Loops197 3.6.6 Conditional move instructions 206 3.6.7 Switch Statements 213 3.7 Procedures 219 3.7.1 Stack Frame Structure 219 3.7.2 Transferring Control 221 3.7.3 Register Usage Conventions 223 3.7. Procedure Example 224 3.7.5 Recursive Procedures 229 3.8 Array Allocation and Access 232 3.8.1 Basic Principles 232 3.8.2 Pointer arithmetic 233 3.8.3 Nested arrays 235 3.8. Fixed-Size Arrays 237 3.8.5 Variable-Size arrays 238 3.9 Hctcrogcncous Data Structurcs 241 3.9.1 Structures 241 3.9.2 Unions 244 3.9.3 Data Alignment 248 3.10 Putting It Together: Understanding Pointers 252 3.11 Life in the Real World: Using the GDB Debugger 254 3.12.1 Thwarting Buffer Overflow Attacks 25/ terflow 256 3.12 Out-of-Bounds memory references and buffer o