University of Limerick - The Linux Kernel …

University of Limerick

Department of Computer Science and Information Systems

An Investigation into the Theoretical Foundations and Implementation of the

Linux Virtual Memory Manager

by

Mel Gorman

Prepared under the direction of Dr. Patrick Healy

A thesis presented to the University of Limerick

in fulllment of the requirements for the degree of

Master of Science

April, 2003

Limerick

University of Limerick

Department of Computer Science and Information Systems

Abstract

An Investigation into the Theoretical Foundations and Implementation of the

Linux Virtual Memory Manager

by Mel Gorman

Adviser: Dr. Patrick Healy

April, 2003

Limerick

The development of Linux is unusual in that it was built with a practical rather

than a theoretical emphasis.

While many of the algorithms in the Virtual Mem-

ory (VM) system were designed by theorists, the implementations have diverged

considerably.

Instead of following the traditional development cycle of design to

implementation, changes are made based on real world behavior and intuitive decisions by developers.

This has resulted in a poorly documented VM understood only by a small core

group of developers and is addressed only by overviews in a small number of books

or web sites.

This requires that even a casual observer invest a large amount of

time to study code and the eld of Memory Management to understand the VM

implementation. The problem is compounded by the fact that code only states what

occurs in a very small instance making it dicult to see how the overall system

functions. This is analogous to using a microscope to identify a piece of furniture.

As Linux gains in popularity in the business and academic worlds, more developers are expressing an interest in the Linux Kernel and the lack of detailed

documentation is a signicant barrier to entry.

The objective of this thesis is to

document fully how the VM in kernel 2.4.20 is implemented including its structure,

the algorithms used, the implementations thereof and the Linux specic features.

Combined with the companion document Code Commentary on the Linux Virtual

Memory Manager these documents represents a detailed tour of the VM explaining

line by line how the it operates, its theoretical basis and approaches to studying and

understanding the VM.

It is envisioned that this will drastically reduce the amount of time a developer

or researcher needs to invest to understand what is happening inside the Linux VM.

To my family, especially my parents who kept me in college long after I should

have got a job. To my girlfriend, who listened to more tech talk than any geek. To

my rst supervisor Dr. John O'Gorman, who encouraged and guided me through

the bulk of the work, may he rest in peace. Finally, to the thousands of people

who have contributed to the Linux kernel whose dedication has produced such a

high quality system.

Contents

List of Figures

v

List of Tables

viii

1 Introduction

1

1.1

Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Managing the Source . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3

Browsing the Code

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4

Reading the Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

1.5

Submitting Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2 Describing Physical Memory

17

2.1

Nodes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2

Zones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.3

Zone Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.4

Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.5

High Memory

32

2.6

What's New In 2.6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Page Table Management

33

37

3.1

Describing the Page Directory . . . . . . . . . . . . . . . . . . . . . .

38

3.2

Describing a Page Table Entry . . . . . . . . . . . . . . . . . . . . . .

40

3.3

Using Page Table Entries . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.4

Translating and Setting Page Table Entries . . . . . . . . . . . . . . .

44

3.5

Allocating and Freeing Page Tables . . . . . . . . . . . . . . . . . . .

44

3.6

Kernel Page Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.7

Mapping addresses to a

. . . . . . . . . . . . . . . . . .

47

3.8

Translation Lookaside Buer (TLB) . . . . . . . . . . . . . . . . . . .

49

3.9

Level 1 CPU Cache Management

. . . . . . . . . . . . . . . . . . . .

50

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.10 What's New In 2.6

struct page

i

CONTENTS

ii

4 Process Address Space

61

4.1

Linear Address Space . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

4.2

Managing the Address Space . . . . . . . . . . . . . . . . . . . . . . .

63

4.3

Process Address Space Descriptor . . . . . . . . . . . . . . . . . . . .

64

4.4

Memory Regions

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

4.5

Exception Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

4.6

Page Faulting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

4.7

Copying To/From Userspace . . . . . . . . . . . . . . . . . . . . . . .

93

4.8

What's New in 2.6

95

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Boot Memory Allocator

104

5.1

Representing the Boot Map

. . . . . . . . . . . . . . . . . . . . . . . 105

5.2

Initialising the Boot Memory Allocator . . . . . . . . . . . . . . . . . 106

5.3

Allocating Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.4

Freeing Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.5

Retiring the Boot Memory Allocator

5.6

What's New in 2.6

. . . . . . . . . . . . . . . . . . 109

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6 Physical Page Allocation

115

6.1

Managing Free Blocks

. . . . . . . . . . . . . . . . . . . . . . . . . . 115

6.2

Allocating Pages

6.3

Free Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

6.4

Get Free Page (GFP) Flags

6.5

Avoiding Fragmentation

6.6

What's New In 2.6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

. . . . . . . . . . . . . . . . . . . . . . . 121

. . . . . . . . . . . . . . . . . . . . . . . . . 123

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

7 Non-Contiguous Memory Allocation

128

7.1

Describing Virtual Memory Areas . . . . . . . . . . . . . . . . . . . . 128

7.2

Allocating A Non-Contiguous Area

7.3

Freeing A Non-Contiguous Area . . . . . . . . . . . . . . . . . . . . . 131

7.4

Whats New in 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

8 Slab Allocator

. . . . . . . . . . . . . . . . . . . 130

134

8.1

Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

8.2

Slabs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

8.3

Objects

8.4

Sizes Cache

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download