Memory management Algorithms and implementation in CC++ (Bill Blunden) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 4.0 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Memory Management Algorithms and Implementation in C/C++ by Bill Blunden Wordware Publishing, Inc.

📄 Page 3

Library of Congress Cataloging-in-Publication Data Blunden, Bill, 1969- Memory management: algorithms and implementation in C/C++ / by Bill Blunden. p. cm. Includes bibliographical references and index. ISBN 1-55622-347-1 1. Memory management (Computer science) 2. Computer algorithms. 3. C (Computer program language) 4. C++ (Computer program language) I. Title. QA76.9.M45 .B558 2002 005.4'35--dc21 2002012447 CIP © 2003, Wordware Publishing, Inc. All Rights Reserved 2320 Los Rios Boulevard Plano, Texas 75074 No part of this book may be reproduced in any form or by any means without permission in writing from Wordware Publishing, Inc. Printed in the United States of America ISBN 1-55622-347-1 10 9 8 7 6 5 4 3 2 1 0208 Product names mentioned are used for identification purposes only and may be trademarks of their respective companies. All inquiries for volume purchases of this book should be addressed to Wordware Publishing, Inc., at the above address. Telephone inquiries may be made by calling: (972) 423-0090

📄 Page 4

This book is dedicated to Rob, Julie, and Theo. And also to David M. Lee “I came to learn physics, and I got Jimmy Stewart” iii

📄 Page 5

(This page has no text content)

📄 Page 6

Table of Contents Acknowledgments . . . . . . . . . . . . . . . . . . . . . . xi Introduction . . . . . . . . . . . . . . . . . . . . . . . . . xiii Chapter 1 Memory Management Mechanisms. . . . . . . . . 1 Mechanism Versus Policy . . . . . . . . . . . . . . . . . . 1 Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . 3 Address Lines and Buses. . . . . . . . . . . . . . . . . . . 9 Intel Pentium Architecture . . . . . . . . . . . . . . . . . 11 Real Mode Operation. . . . . . . . . . . . . . . . . . . 14 Protected Mode Operation. . . . . . . . . . . . . . . . 18 Protected Mode Segmentation . . . . . . . . . . . . 19 Protected Mode Paging . . . . . . . . . . . . . . . . 26 Paging as Protection . . . . . . . . . . . . . . . . . . 31 Addresses: Logical, Linear, and Physical . . . . . . . 33 Page Frames and Pages . . . . . . . . . . . . . . . . 34 Case Study: Switching to Protected Mode . . . . . . . 35 Closing Thoughts . . . . . . . . . . . . . . . . . . . . . . 42 References . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Chapter 2 Memory Management Policies. . . . . . . . . . . 45 Case Study: MS-DOS . . . . . . . . . . . . . . . . . . . . 46 DOS Segmentation and Paging . . . . . . . . . . . . . 46 DOS Memory Map . . . . . . . . . . . . . . . . . . . . 47 Memory Usage . . . . . . . . . . . . . . . . . . . . . . 49 Example: A Simple Video Driver . . . . . . . . . . . . 50 Example: Usurping DOS . . . . . . . . . . . . . . . . . 52 Jumping the 640KB Hurdle . . . . . . . . . . . . . . . 56 Case Study: MMURTL . . . . . . . . . . . . . . . . . . . 59 Background and Design Goals . . . . . . . . . . . . . . 60 MMURTL and Segmentation . . . . . . . . . . . . . . 61 Paging Variations . . . . . . . . . . . . . . . . . . . . . 63 MMURTL and Paging . . . . . . . . . . . . . . . . . . 64 v

📄 Page 7

Memory Allocation . . . . . . . . . . . . . . . . . . . . 66 Case Study: Linux . . . . . . . . . . . . . . . . . . . . . . 67 History and MINIX . . . . . . . . . . . . . . . . . . . . 67 Design Goals and Features. . . . . . . . . . . . . . . . 68 Linux and Segmentation . . . . . . . . . . . . . . . . . 69 Linux and Paging . . . . . . . . . . . . . . . . . . . . . 72 Three-Level Paging . . . . . . . . . . . . . . . . . . 72 Page Fault Handling . . . . . . . . . . . . . . . . . . 76 Memory Allocation . . . . . . . . . . . . . . . . . . . . 76 Memory Usage . . . . . . . . . . . . . . . . . . . . . . 81 Example: Siege Warfare . . . . . . . . . . . . . . . . . 82 Example: Siege Warfare, More Treachery . . . . . . . 87 Case Study: Windows . . . . . . . . . . . . . . . . . . . . 92 Historical Forces . . . . . . . . . . . . . . . . . . . . . 92 Memory Map Overview . . . . . . . . . . . . . . . . . 96 Windows and Segmentation . . . . . . . . . . . . . . . 99 Special Weapons and Tactics . . . . . . . . . . . . . 99 Crashing Windows with a Keystroke . . . . . . . . 102 Reverse Engineering the GDT . . . . . . . . . . . 102 Windows and Paging . . . . . . . . . . . . . . . . . . 105 Linear Address Space Taxonomy . . . . . . . . . . 105 Musical Chairs for Pages. . . . . . . . . . . . . . . 106 Memory Protection . . . . . . . . . . . . . . . . . 108 Demand Paging . . . . . . . . . . . . . . . . . . . . 109 Memory Allocation . . . . . . . . . . . . . . . . . . . 110 Memory Usage . . . . . . . . . . . . . . . . . . . . . 114 Turning Off Paging . . . . . . . . . . . . . . . . . . . 117 Example: Things That Go Thunk in the Night . . . . 118 Closing Thoughts . . . . . . . . . . . . . . . . . . . . . 122 References . . . . . . . . . . . . . . . . . . . . . . . . . 123 Books and Articles . . . . . . . . . . . . . . . . . . . 123 Web Sites . . . . . . . . . . . . . . . . . . . . . . . . 125 Chapter 3 High-Level Services. . . . . . . . . . . . . . . . 127 View from 10,000 Feet . . . . . . . . . . . . . . . . . . . 127 Compiler-Based Allocation . . . . . . . . . . . . . . . . 129 Data Section . . . . . . . . . . . . . . . . . . . . . . . 132 Code Section . . . . . . . . . . . . . . . . . . . . . . 134 Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Activation Records . . . . . . . . . . . . . . . . . . 138 Scope . . . . . . . . . . . . . . . . . . . . . . . . . 144 Table of Contents vi

📄 Page 8

Static or Dynamic? . . . . . . . . . . . . . . . . . . 150 Heap Allocation . . . . . . . . . . . . . . . . . . . . . . 151 System Call Interface . . . . . . . . . . . . . . . . . . 151 The Heap . . . . . . . . . . . . . . . . . . . . . . . . 156 Manual Memory Management. . . . . . . . . . . . 157 Example: C Standard Library Calls . . . . . . . . . 158 Automatic Memory Management . . . . . . . . . . 160 Example: The BDW Conservative Garbage Collector . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Manual Versus Automatic?. . . . . . . . . . . . . . 164 The Evolution of Languages. . . . . . . . . . . . . . . . 168 Case Study: COBOL . . . . . . . . . . . . . . . . . . 171 Case Study: FORTRAN. . . . . . . . . . . . . . . . . 177 Case Study: Pascal . . . . . . . . . . . . . . . . . . . 181 Case Study: C . . . . . . . . . . . . . . . . . . . . . . 184 Case Study: Java. . . . . . . . . . . . . . . . . . . . . 192 Language Features . . . . . . . . . . . . . . . . . . 192 Virtual Machine Architecture . . . . . . . . . . . . 194 Java Memory Management . . . . . . . . . . . . . 196 Memory Management: The Three-layer Cake . . . . . . 202 References . . . . . . . . . . . . . . . . . . . . . . . . . 204 Chapter 4 Manual Memory Management . . . . . . . . . . 207 Replacements for malloc() and free() . . . . . . . 207 System Call Interface and Porting Issues . . . . . . . . 208 Keep It Simple . . .Stupid! . . . . . . . . . . . . . . . . . 211 Measuring Performance . . . . . . . . . . . . . . . . . . 212 The Ultimate Measure: Time . . . . . . . . . . . . . 212 ANSI and Native Time Routines . . . . . . . . . . 213 The Data Distribution: Creating Random Variates . 215 Testing Methodology . . . . . . . . . . . . . . . . . . 219 Indexing: The General Approach . . . . . . . . . . . . . 224 malloc() Version 1: Bitmapped Allocation. . . . . . . 224 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Implementation . . . . . . . . . . . . . . . . . . . . . 226 tree.cpp . . . . . . . . . . . . . . . . . . . . . . . . 227 bitmap.cpp . . . . . . . . . . . . . . . . . . . . . . 232 memmgr.cpp . . . . . . . . . . . . . . . . . . . . . 236 mallocV1.cpp . . . . . . . . . . . . . . . . . . . . . 239 perform.cpp . . . . . . . . . . . . . . . . . . . . . . 241 driver.cpp . . . . . . . . . . . . . . . . . . . . . . . 241 Table of Contents vii

📄 Page 9

Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . . 247 malloc() Version 2: Sequential Fit . . . . . . . . . . . 248 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Implementation . . . . . . . . . . . . . . . . . . . . . 251 memmgr.cpp . . . . . . . . . . . . . . . . . . . . . 251 mallocV2.cpp . . . . . . . . . . . . . . . . . . . . . 260 driver.cpp . . . . . . . . . . . . . . . . . . . . . . . 261 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . . 264 malloc() Version 3: Segregated Lists . . . . . . . . . 265 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 265 Implementation . . . . . . . . . . . . . . . . . . . . . 266 memmgr.cpp . . . . . . . . . . . . . . . . . . . . . 267 mallocV3.cpp . . . . . . . . . . . . . . . . . . . . . 274 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . . 279 Performance Comparison . . . . . . . . . . . . . . . . . 279 Chapter 5 Automatic Memory Management . . . . . . . . 281 Garbage Collection Taxonomy . . . . . . . . . . . . . . 281 malloc() Version 4: Reference Counting . . . . . . . 283 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Implementation . . . . . . . . . . . . . . . . . . . . . 284 driver.cpp . . . . . . . . . . . . . . . . . . . . . . . 285 mallocV4.cpp . . . . . . . . . . . . . . . . . . . . . 287 perform.cpp . . . . . . . . . . . . . . . . . . . . . . 288 memmgr.cpp . . . . . . . . . . . . . . . . . . . . . 289 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . . 302 malloc() Version 5: Mark-Sweep . . . . . . . . . . . 304 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 304 Implementation . . . . . . . . . . . . . . . . . . . . . 307 driver.cpp . . . . . . . . . . . . . . . . . . . . . . . 307 mallocV5.cpp . . . . . . . . . . . . . . . . . . . . . 309 perform.cpp . . . . . . . . . . . . . . . . . . . . . . 311 memmgr.cpp . . . . . . . . . . . . . . . . . . . . . 312 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . . 330 Performance Comparison . . . . . . . . . . . . . . . . . 332 Potential Additions . . . . . . . . . . . . . . . . . . . . . 332 Table of Contents viii

📄 Page 10

Object Format Assumptions . . . . . . . . . . . . . . 333 Variable Heap Size . . . . . . . . . . . . . . . . . . . 335 Indirect Addressing . . . . . . . . . . . . . . . . . . . 335 Real-Time Behavior . . . . . . . . . . . . . . . . . . . 337 Life Span Characteristics . . . . . . . . . . . . . . . . 338 Multithreaded Support . . . . . . . . . . . . . . . . . 339 Chapter 6 Miscellaneous Topics . . . . . . . . . . . . . . . 343 Suballocators . . . . . . . . . . . . . . . . . . . . . . . . 343 Monolithic Versus Microkernel Architectures . . . . . . 348 Closing Thoughts . . . . . . . . . . . . . . . . . . . . . 351 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 Table of Contents ix

📄 Page 11

(This page has no text content)

📄 Page 12

Acknowledgments Publishing a book is an extended process that involves a number of people. Writing the final manuscript is just a small part of the big picture. This section is dedicated to all the people who directly, and indirectly, lent me their help. First and foremost, I would like to thank Jim Hill of Wordware Publishing for giving me the opportunity to write a book and believ- ing in me. I would also like to extend thanks to Wes Beckwith and Beth Kohler. Wes, in addition to offering constant encouragement, does a great job of putting up with my e-mails and handling the vari- ous packages that I send. Beth Kohler, who performed the incredible task of reading my first book for Wordware in a matter of days, has also been invaluable. I first spoke with Barry Brey back in the mid-1990s when I became interested in protected mode programming. He has always taken the time to answer my questions and offer his insight. Barry wrote the first book on the Intel chip set back in 1984. Since then, he has written well over 20 books. His current textbook on Intel’s IA32 processors is in its sixth edition. This is why I knew I had to ask Barry to be the technical editor for this book. Thanks, Barry. “Look, our middleware even runs on that little Windows NT piece of crap.” — George Matkovitz “Hey, who was the %&^$ son of a &*$# who wrote this optimized load of . . . oh, it was me.” — Mike Adler Mike Adler and George Matkovitz are two old fogeys who worked at Control Data back when Seymour Cray kicked the tar out of IBM. George helped to implement the world’s first message-passing operating system at Control Data. Mike also worked on a number of groundbreaking system software projects. I met these two codgers while performing R&D for an ERP vendor in the Midwest. I hadn’t noticed how much these engineers had influenced me until I left xi

📄 Page 13

Minnesota for California. It was almost as though I had learned through osmosis. A lot of my core understanding of software and the computer industry in general is based on the bits of hard-won advice and lore that these gentlemen passed on to me. I distinctly remember walking into Mike’s office and asking him, “Hey Mike, how do you build an operating system?” I would also like to thank Frank Merat, a senior professor at Case Western Reserve University. Frank has consistently shown interest in my work and has offered his support whenever he could. There is no better proving ground for a book than an established research university. Finally, I would like to thank SonicWALL, Inc. for laying me off and giving me the opportunity to sit around and think. The days I spent huddled with my computers were very productive. Acknowledgments xii

📄 Page 14

Introduction “Pay no attention to the man behind the curtain.” — The Wizard of Oz There are a multitude of academic computer science texts that dis- cuss memory management. They typically devote a chapter or less to the subject and then move on. Rarely are concrete, machine-level details provided, and actual source code is even scarcer. When the author is done with his whirlwind tour, the reader tends to have a very limited idea about what is happening behind the curtain. This is no surprise, given that the nature of the discussion is rampantly ambiguous. Imagine trying to appreciate Beethoven by having someone read the sheet music to you or experience the Mona Lisa by reading a description in a guidebook. This book is different. Very different. In this book, I am going to pull the curtain back and let you see the little man operating the switches and pulleys. You may be excited by what you see, or you may feel sorry that you decided to look. But as Enrico Fermi would agree, knowledge is always better than ignorance. This book provides an in-depth look at memory subsystems and offers extensive source code examples. In cases where I do not have access to source code (i.e., Windows), I offer advice on how to gather forensic evidence, which will nurture insight. While some books only give readers a peak under the hood, this book will give readers a power drill and allow them to rip out the transmission. The idea behind this is to allow readers to step into the garage and get their hands dirty. My own experience with memory managers began back in the late 1980s when Borland’s nifty Turbo C 1.0 compiler was released. This was my first taste of the C language. I can remember using a disassembler to reverse engineer library code in an attempt to see how the malloc() and free() standard library functions xiii

📄 Page 15

operated. I don’t know how many school nights I spent staring at an 80x25 monochrome screen, deciphering hex dumps. It was tough going and not horribly rewarding (but I was curious, and I couldn’t help myself). Fortunately, I have done most of the dirty work for you. You will conveniently be able to sidestep all of the hurdles and tedious manual labor that confronted me. If you were like me and enjoyed taking your toys apart when you were a child to see how they worked, then this is the book for you. So lay your computer on a tarpaulin, break out your compilers, and grab an oil rag. We’re going to take apart memory management sub- systems and put them back together. Let the dust fly where it may! Historical Setting In the late 1930s, a group of scholars arrived at Bletchley Park in an attempt to break the Nazis’ famous Enigma cipher. This group of codebreakers included a number of notable thinkers, like Tommy Flowers and Alan Turing. As a result of the effort to crack Enigma, the first electronic computer was constructed in 1943. It was named Colossus and used thermionic valves (known today as vacuum tubes) for storing data. Other vacuum tube computers followed. For exam- ple, ENIAC (electronic numerical integrator and computer) was built by the U.S. Army in 1945 to compute ballistic firing tables. NOTE Science fiction aficionados might enjoy a movie called Colos- sus: The Forbin Project. It was made in 1969 and centers around Colossus, a supercomputer designed by a scientist named Charles Forbin. Forbin convinces the military that they should give control of the U.S. nuclear arsenal to Colossus in order to eliminate the potential of human error accidentally starting World War III. The movie is similar in spirit to Stanley Kubrick’s 2001: A Space Odyssey, but without the happy ending: Robot is built, robot becomes sentient, robot runs amok. I was told that everyone who has ever worked at Control Data has seen this movie. The next earth-shaking development arrived in 1949 when ferrite (iron) core memory was invented. Each bit of memory was made of a small, circular iron magnet. The value of the bit switched from “1” to “0” by using electrical wires to magnetize the circular loops in one of two possible directions. The first computer to utilize ferrite core memory was IBM’s 705, which was put into production in 1955. Back in those days, 8KB of memory was considered a huge piece of real estate. Introduction xiv

📄 Page 16

Everything changed once transistors became the standard way to store bits. The transistor was presented to the world in 1948 when Bell Labs decided to go public with its new device. In 1954, Bell Labs constructed the first transistor-based computer. It was named TRADIC (TRAnsistorized DIgital Computer). TRADIC was much smaller and more efficient than vacuum tube computers. For exam- ple, ENIAC required 1,000 square feet and caused power outages in Philadelphia when it was turned on. TRADIC, on the other hand, was roughly three cubic feet in size and ran on 100 watts of electricity. NOTE Before electronic computers became a feasible alternative, heavy mathematical computation relied on human computers. Large groups of people would be assembled to carry out massive numerical algorithms. Each person would do a part of a computation and pass it on to someone else. This accounts for the prevalance of logarithm tables in mathematical references like the one published by the Chem- ical Rubber Company (CRC). Slide rules and math tables were standard fare before the rise of the digital calculator. ASIDE “After 45 minutes or so, we’ll see that the results are obvious.” — David M. Lee I have heard Nobel laureates in physics, like Dave Lee, complain that students who rely too heavily on calculators lose their mathematical intuition. To an extent, Dave is cor- rect. Before the dawn of calculators, errors were more com- mon, and developing a feel for numeric techniques was a useful way to help catch errors when they occurred. During the Los Alamos project, a scientist named Dick Feynman ran a massive human computer. He once mentioned that the performance and accuracy of his group’s computa- tions were often more a function of his ability to motivate people. He would sometimes assemble people into teams and have them compete against each other. Not only was this a good idea from the standpoint of making things more interesting, but it was also an effective technique for catching discrepancies. Introduction xv

📄 Page 17

In 1958, the first integrated circuit was invented. The inventor was a fellow named Jack Kilby, who was hanging out in the basement of Texas Instruments one summer while everyone else was on vaca- tion. A little over a decade later, in 1969, Intel came out with a 1 kilobit memory chip. After that, things really took off. By 1999, I was working on a Windows NT 4.0 workstation (service pack 3) that had 2GB of SDRAM memory. The general trend you should be able to glean from the previous discussion is that memory components have solved performance requirements by getting smaller, faster, and cheaper. The hardware people have been able to have their cake and eat it too. However, the laws of physics place a limit on how small and how fast we can actually make electronic components. Eventually, nature itself will stand in the way of advancement. Heisenberg’s Uncertainty Princi- ple, shown below, is what prevents us from building infinitely small components. x p (h/4 ) For those who are math-phobic, I will use Heinsenberg’s own words to describe what this equation means: “The more precisely the position is determined, the less pre- cisely the momentum is known in this instant, and vice versa.” In other words, if you know exactly where a particle is, then you will not be able to contain it because its momentum will be huge. Think of this like trying to catch a tomato seed. Every time you try to squeeze down and catch it, the seed shoots out of your hands and flies across the dinner table into Uncle Don’s face. Einstein’s General Theory of Relativity is what keeps us from building infinitely fast components. With the exception of black holes, the speed limit in this universe is 3x108 meters per second. Eventually, these two physical limits are going to creep up on us. When this happens, the hardware industry will have to either make larger chips (in an effort to fit more transistors in a given area) or use more efficient algorithms so that they can make better use of existing space. My guess is that relying on better algorithms will be the cheaper option. This is particularly true with regard to memory management. Memory manipulation is so frequent and crucial to performance that designing better memory management subsys- tems will take center stage in the future. This will make the time spent reading this book a good investment. Introduction xvi

📄 Page 18

Impartial Analysis In this book, I try very hard to offer memory management solutions without taking sides. I have gone to great lengths to present an unbiased discussion. This is important because it is extremely tempting to champion a certain memory management algorithm (especially if you invented it). There are some journal authors who would have you believe that their new algorithm is a panacea to cure the ills of the world. I do not have the ulterior motives of a col- lege professor. I am here to offer you a set of tools and then let you decide how best to use them. In this book, I will present you with different techniques and try to point out the circumstances in which they perform well. The question “Which is the best memory management algo- rithm?” is very similar in spirit to any of the following questions: “Which operating system is the best?” “Which programming language is the best?” “Which data structure is the best?” “Which type of screwdriver is the best?” I can recall asking a program manager at Eaton Corp., John Schindler, what the best operating system was. John was managing at least a dozen different high-end platforms for Eaton, and I thought he would know. I was expecting him to come right back with a quick answer like: “Oh, OpenBSD is the best.” What actually happened was something that surprised me. He looked at me for a minute, as if the question was absurd. Then he smiled and said, “Well, it really depends on what you’re going to use the machine for. I use Solaris for networking, HP-UX for app servers, AIX to talk to our mainframe, NT for mail, . . . ” The truth is there is no “best” solution. Most solutions merely offer certain trade-offs. In the end, the best tool to use will depend upon the peculiarities of the problem you are trying to solve. This is a central theme that appears throughout the domain of computer science. Keep it in the back of your mind, like some sort of Buddhist mantra: “There is no best solution, Grasshopper, only trade-offs.” For example, linked lists and arrays can both represent a linear set of items. With a linked list, you get easy manipulation at the expense of speed. Adding an element to a linked list is as easy as modifying a couple of pointers. However, to find a given list Introduction xvii

📄 Page 19

element, you may have to traverse the entire list manually until you find it. Conversely, with an array, you get access speed at the expense of flexibility. Accessing an array element is as easy as add- ing an integer to a base address, but adding and deleting array elements requires a lot of costly shifting. If your code is not going to do a lot of list modification, an array is the best choice. If your code will routinely add and delete list members, a linked list is the better choice. It all depends upon the context of the problem. Audience This book is directed toward professional developers and students who are interested in discovering how memory is managed on pro- duction systems. Specifically, engineers working on PC or embedded operating systems may want to refresh their memory or take a look at alternative approaches. If this is the case, then this book will serve as a repository of algorithms and software compo- nents that you can apply to your day-to-day issues. Professionals who design and construct development tools will also find this book useful. In general, development tools fall into the class of online transaction processing (OLTP) programs. When it comes to OLTP apps, pure speed is the name of the game. As such, programming language tools, like compilers, often make use of suballocators to speed up the performance of the code that manipu- lates their symbol table. With regard to compiling large software programs consisting of millions of lines of code, this type of suballocator-based optimization can mean the difference between waiting for a few minutes and waiting for a few hours. Anyone who mucks around with suballocators will find this book indispensable. Software engineers who work with virtual machines will also be interested in the topics that I cover. The Java virtual machine is famous for its garbage collection facilities. In this book I explore several automatic memory management techniques and also pro- vide a couple of concrete garbage collection implementations in C++. Finally, this book also targets the curious. There is absolutely nothing wrong with being curious. In fact, I would encourage it. You may be an application developer who has used memory manage- ment facilities countless times in the past without taking the time to Introduction xviii

📄 Page 20

determine how they really work. You may also have nurtured an interest that you have had to repress due to deadlines and other pri- orities. This book will offer such engineers an opportunity to indulge their desire to see what is going on under the hood. Organization This book is divided into six chapters. I will start from the ground up and try to provide a comprehensive, but detailed, view of mem- ory management fundamentals. Because of this, each chapter builds on what has been presented in the previous one. Unless you are a memory management expert, the best way to read this book is straight through. Chapter 1 – Memory Management Mechanisms The first chapter presents a detailed look at the machinery that allows memory management to take place. Almost every operating system in production takes advantage of facilities that are provided by the native processor. This is done primarily for speed, since pushing repetitive bookkeeping down to the hardware benefits over- all performance. There have been attempts by some engineers to track and protect memory strictly outside of the hardware. But speed is key to the hardware realm, and this fact always forces such attempts off of the playing field. The end result is that understand- ing how memory management is performed means taking a good look at how memory hardware functions. Chapter 2 – Memory Management Policies Computer hardware provides the mechanism for managing memory, but the policy decisions that control how this mechanism is applied are dictated by the operating system and its system call interface to user programs. In this chapter, the memory management compo- nents provided by the operating system are analyzed and dissected. This will necessarily involve taking a good, hard look at the inter- nals of production operating systems like Linux and Windows. In general, hardware always provides features that are ahead of the software that uses it. For example, Intel’s Pentium provides four distinct layers of memory protection. Yet, I could not find a single Introduction xix