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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- the university of scranton address
- the university of hong kong
- wharton school of the university of pennsylvania
- the university of scranton tuition
- the education university of hong kong
- the university of scranton
- the university of hk
- the university of scranton jobs
- the university of north texas
- the university of philosophical research
- the university of scranton players
- linux kernel virtual memory