Always Learning

Advanced Search

Linux Kernel Development

Linux Kernel Development

2nd Edition

Jan 2005, Paperback, 432 pages
ISBN13: 9780672327209
ISBN10: 0672327201
This title is no longer available.
  • Print pagePrint page
  • Email this pageEmail page
  • Write a reviewWrite a review
  • Share

The Linux kernel is one of the most important and far-reaching open-source projects. That is why Novell Press is excited to bring you the second edition of Linux Kernel Development, Robert Love's widely acclaimed insider's look at the Linux kernel. This authoritative, practical guide helps developers better understand the Linux kernel through updated coverage of all the major subsystems as well as new features associated with the Linux 2.6 kernel. You'll be able to take an in-depth look at Linux kernel from both a theoretical and an applied perspective as you cover a wide range of topics, including algorithms, system call interface, paging strategies and kernel synchronization. Get the top information right from the source in Linux Kernel Development.

1. Introduction to the Linux Kernel.

Along Came Linus: Introduction to Linux

Overview of Operating Systems and Kernels

Linux Versus Classic Unix Kernels

Linux Kernel Versions

The Linux Kernel Development Community

Before We Begin

2. Getting Started with the Kernel.

Obtaining the Kernel Source

Installing the Kernel Source

Using Patches

The Kernel Source Tree

Building the Kernel

Minimizing Build Noise

Spawning Multiple Build Jobs

Installing the Kernel

A Beast of a Different Nature

No libc

GNU C

No Memory Protection

No (Easy) Use of Floating Point

Small, Fixed-Size Stack

Synchronization and Concurrency

Portability Is Important

So Here We Are

3. Process Management.

Process Descriptor and the Task Structure

Allocating the Process Descriptor

Storing the Process Descriptor

Process State

Manipulating the Current Process State

Process Context

The Process Family Tree

Process Creation

Copy-on-Write

fork()

vfork()

The Linux Implementation of Threads

Kernel Threads

Process Termination

Removal of the Process Descriptor

The Dilemma of the Parentless Task

Process Wrap Up

4. Process Scheduling.

Policy

I/O-Bound Versus Processor-Bound Processes

Process Priority

Timeslice

Process Preemption

The Scheduling Policy in Action

The Linux Scheduling Algorithm

Runqueues

The Priority Arrays

Recalculating Timeslices

schedule()

Calculating Priority and Timeslice

Sleeping and Waking Up

The Load Balancer

Preemption and Context Switching

User Preemption

Kernel Preemption

Real-Time

Scheduler-Related System Calls

Scheduling Policy and Priority-Related System Calls

Processor Affinity System Calls

Yielding Processor Time

Scheduler Finale

5. System Calls.

APIs, POSIX, and the C Library

Syscalls

System Call Numbers

System Call Performance

System Call Handler

Denoting the Correct System Call

Parameter Passing

System Call Implementation

Verifying the Parameters

System Call Context

Final Steps in Binding a System Call

Accessing the System Call from User-Space

Why Not to Implement a System Call

System Calls in Conclusion

6. Interrupts and Interrupt Handlers.

Interrupts

Interrupt Handlers

Top Halves Versus Bottom Halves

Registering an Interrupt Handler

Freeing an Interrupt Handler

Writing an Interrupt Handler

Shared Handlers

A Real-Life Interrupt Handler

Interrupt Context

Implementation of Interrupt Handling

/proc/interrupts

Interrupt Control

Disabling and Enabling Interrupts

Disabling a Specific Interrupt Line

Status of the Interrupt System

Donít Interrupt Me; Weíre Almost Done!

7. Bottom Halves and Deferring Work.

Bottom Halves

Why Bottom Halves?

A World of Bottom Halves

Softirqs

Implementation of Softirqs

Using Softirqs

Tasklets

Implementation of Tasklets

Using Tasklets

ksoftirqd

The Old BH Mechanism

Work Queues

Implementation of Work Queues

Using Work Queues

The Old Task Queue Mechanism

Which Bottom Half Should I Use?

Locking Between the Bottom Halves

Disabling Bottom Halves

The Bottom of Bottom-Half Processing

8. Kernel Synchronization Introduction.

Critical Regions and Race Conditions

Why Do We Need Protection?

Locking g

What Causes Concurrency, Anyway?

So, How Do I Know What Needs Protecting?

Deadlocks

Contention and Scalability

Locking and Your Code

9. Kernel Synchronization Methods.

Atomic Operations

Atomic Integer Operations

Atomic Bitwise Operations

Spin Locks

Other Spin Lock Methods

Spin Locks and Bottom Halves

Reader-Writer Spin Locks

Semaphores

Creating and Initializing Semaphores

Using Semaphores

Reader-Writer Semaphores

Spin Locks Versus Semaphores

Completion Variables

BKL: The Big Kernel Lock

Seq Locks

Preemption Disabling

Ordering and Barriers

Synchronization Summarization

10. Timers and Time Management.

Kernel Notion of Time

The Tick Rate: HZ

The Ideal HZ Value

Jiffies

Internal Representation of Jiffies

Jiffies Wraparound

User-Space and HZ

Hardware Clocks and Timers

Real-Time Clock

System Timer

The Timer Interrupt Handler

The Time of Day

Timers

Using Timers

Timer Race Conditions

The Timer Implementation

Delaying Execution

Busy Looping

Small Delays

schedule_timeout()

Out of Time

11. Memory Management.

Pages

Zones

Getting Pages

Getting Zeroed Pages

Freeing pages

kmalloc()

gfp_mask Flags

kfree()

vmalloc()

Slab Layer

Design of the Slab Layer

Slab Allocator Interface

Statically Allocating on the Stack

Playing Fair on the Stack

High Memory Mappings

Permanent Mappings

Temporary Mappings

Per-CPU Allocations

The New percpu Interface

Per-CPU Data at Compile-Time

Per-CPU Data at Runtime

Reasons for Using Per-CPU Data

Which Allocation Method Should I Use?

12. The Virtual Filesystem.

Common Filesystem Interface

Filesystem Abstraction Layer

Unix Filesystems

VFS Objects and Their Data Structures

Other VFS Objects

The Superblock Object

Superblock Operations

The Inode Object

Inode Operations

The Dentry Object

Dentry State

The Dentry Cache

Dentry Operations

The File Object

File Operations

Data Structures Associated with Filesystems

Data Structures Associated with a Process

Filesystems in Linux

13. The Block I/O Layer.

Anatomy of a Block Device

Buffers and Buffer Heads

The bio structure

The Old Versus the New

Request Queues

Requests

I/O Schedulers

The Job of an I/O Scheduler

The Linus Elevator

The Deadline I/O Scheduler

The Anticipatory I/O Scheduler

The Complete Fair Queuing I/O Scheduler

The Noop I/O Scheduler

I/O Scheduler Selection

Summary

14. The Process Address Space.

The Memory Descriptor

Allocating a Memory Descriptor

Destroying a Memory Descriptor

The mm_struct and Kernel Threads

Memory Areas

VMA Flags

VMA Operations

Lists and Trees of Memory Areas

Memory Areas in Real Life

Manipulating Memory Areas

find_vma()

find_vma_prev()

find_vma_intersection()

mmap() and do_mmap(): Creating an Address Interval

The mmap() System Call

munmap() and do_munmap(): Removing an Address Interval

The munmap() System Call

Page Tables

Conclusion

15. The Page Cache and Page Writeback.

Page Cache

The address_space Object

Radix Tree

The Old Page Hash Table

The Buffer Cache

The pdflush Daemon

Laptop Mode

bdflush and kupdated

Congestion Avoidance: Why We Have Multiple Threads

To Make a Long Story Short

16. Modules.

Hello, World!

Building Modules

At Home in the Source Tree

Living Externally

Installing Modules

Generating Module Dependencies

Loading Modules

Managing Configuration Options

Module Parameters

Exported Symbols

Wrapping Up Modules

17. kobjects and sysfs.

kobjects

ktypes

ksets

Subsystems

Structure Confusion

Managing and Manipulating kobjects

Reference Counts

krefs

sysfs

Adding and Removing kobjects from sysfs

Adding Files to sysfs

The Kernel Events Layer

kobjects and sysfs in a Nutshell

18. Debugging.

What You Need to Start

Bugs in the Kernel

printk()

The Robustness of printk()

Loglevels

The Log Buffer

syslogd and klogd

A Note About printk() and Kernel Hacking

Oops

ksymoops

kallsyms

Kernel Debugging Options

Atomicity Debugging

Asserting Bugs and Dumping Information

Magic SysRq Key

The Saga of a Kernel Debugger

gdb

kgdb

kdb

Poking and Probing the System

Using UID as a Conditional

Using Condition Variables

Using Statistics

Rate Limiting Your Debugging

Binary Searching to Find the Culprit Change

When All Else Fails: The Community

19. Portability.

History of Portability in Linux

Word Size and Data Types

Opaque Types

Special Types

Explicitly Sized Types

Signedness of Chars

Data Alignment

Avoiding Alignment Issues

Alignment of Nonstandard Types

Structure Padding

Byte Order

History of Big- and Little-Endian

Byte Ordering in the Kernel

Time

Page Size

Processor Ordering

SMP, Kernel Preemption, and High Memory

Portability Is Fun

20. Patches, Hacking, and the Community.

The Community

Linux Coding Style

Indention

Braces

Line Size

Naming

Functions

Comments

Typedefs

Using What Is Already Provided

No ifdefs in the Source

Structure Initializers

Fixing Code Up Ex Post Facto

Chain of Command

Submitting Bug Reports

Generating Patches

Submitting Patches

Conclusion

Appendix A. Linked Lists.

Circular Linked Lists

Moving Through a Linked List

The Linux Kernelís Implementation

The Linked-List Structure

Manipulating Linked Lists

Traversing Linked Lists

Appendix B. Kernel Random Number Generator.

Design and Implementation

The Dilemma of System Startup

Interfaces to Input Entropy

Interfaces to Output Entropy

Appendix C. Algorithmic Complexity.

Algorithms

Big-O Notation

Big Theta Notation

Putting It All Together

Perils of Time Complexity

Bibliography and Reading List.

Books on Operating System Design

Books on Unix Kernels

Books on Linux Kernels

Books on Other Kernels

Books on the Unix API

Books on the C Programming Language

Other Works

Websites

Index.

Robert Love is an open source hacker who has used Linux since the early days. Robert is active in and passionate about both the Linux kernel and the GNOME communities. Robert currently works as Senior Kernel Engineer in the Ximian Desktop Group at Novell. Before that, he was a kernel engineer at MontaVista Software.

Robert's kernel projects include the preemptive kernel, the process scheduler, the kernel events layer, VM enhancements, and multiprocessing improvements. He is the author and maintainer of schedutils and GNOME Volume Manager.

Robert has given numerous talks on and has written multiple articles about the Linux kernel. He is a Contributing Editor for Linux Journal.

Robert received a B.A. in Mathematics and a B.S. in Computer Science from the University of Florida. Born in South Florida, Robert currently calls Cambridge, Massachusetts home. He enjoys college football, photography, and cooking.