John O’Gorman0470847719, 9780470847718
synchronisation, including locks and semaphores
interrupts (hardware and software)
signal handling Complete in every way, this book describes every function and macro. All data structures used by the process manager are dealt with and their role in the overall picture explained along with the accompanying raw code.
This indispensable guide to the kernel subset is aimed at readers with some previous knowledge of operating system structure and terminology, as well as a minimum knowledge of the C programming language. The comprehensive index which lists every identifier, makes in-depth information instantly available to programmers, software engineers, system administrators and anyone who wants to modify the kernel, or wants to know about the implications of kernel configuration variables.
Table of contents :
The Linux Process
Manager……Page 2
1 Introduction……Page 16
1.1 Overview of the process manager……Page 17
1.1.2 Multiprocessors……Page 18
1.1.3 Threads……Page 19
1.2.1 C language features……Page 20
1.2.2 Assembly language features……Page 22
1.3.1 Starting the kernel……Page 24
1.3.2 Scheduler initialisation……Page 25
1.3.3 Starting and the idle process……Page 26
2.1 Important fields hard coded at the beginning……Page 27
2.1.1 Line 285:……Page 28
2.1.2 Line 286:……Page 29
2.1.3 Line 296:……Page 31
2.2 Scheduling fields……Page 32
2.3 General process information……Page 36
2.5 Credentials and limits……Page 41
2.6 Miscellaneous information……Page 44
2.7 Volatile environment and input ¨C output……Page 45
2.8 Signal handlers……Page 51
2.10 Conclusions……Page 53
3.1 Manipulating the linked list of task structures……Page 55
3.1.1 Removing a……Page 56
3.3.2 Inserting a……Page 57
3.1.3 Searching the process list……Page 59
3.2.1 The process hash table……Page 60
3.2.3 Insert a into the hash table……Page 61
3.2.4 Remove a from the hash table……Page 63
3.3.1 The of the initial process……Page 64
3.3.2 The of the initial process……Page 66
3.3.3 Resource limits for the initial process……Page 69
3.4.1 Setting up the idle thread…….Page 70
3.4.2 Initialise the idle thread……Page 71
3.4.3 The default idle function……Page 72
4.1.1 Declaring and initialising wait queue entries……Page 75
4.1.2 Wait queue headers……Page 77
4.1.3 Debugging code……Page 80
4.2.1 Adding an entry to a wait queue……Page 83
4.2.2 Removing an entry from a wait queue……Page 85
4.3.1 Declaring and initialising list entries……Page 87
4.3.2 Inserting entries……Page 88
4.3.3 Deleting entries……Page 89
4.3.4 Miscellaneous functions……Page 90
4.4 Wait queue locks……Page 93
4.5.1 Common code……Page 94
4.5.2 Putting a process to sleep interruptibly……Page 95
4.5.3 Sleeping interruptibly with a timeout……Page 96
4.6 Conditionally waiting on an event……Page 97
4.6.1 Conditional uninterruptible sleep……Page 98
4.6.2 Conditional interruptible sleep……Page 100
4.7.1 Wake- up macros……Page 102
4.7.2 Locking the wait queue and wake up……Page 103
4.7.3 Finding a process to wake up……Page 104
4.7.4 Trying to wake up a specific process……Page 106
4.8.1 Add a to the runqueue……Page 107
4.8.3 Removing a from the runqueue……Page 108
4.8.4 Checking if a is on the runqueue……Page 109
5.1.1 Setting a bit……Page 111
5.1.2 Clearing a bit……Page 112
5.1.4 Testing and setting a bit……Page 113
5.1.6 Finding the first bit clear……Page 115
5.2.1 Basic definitions……Page 116
5.2.3 Atomic subtraction……Page 117
5.2.5 Atomic increment……Page 118
5.2.7 Atomic decrement and test for zero……Page 119
5.2.9 Atomically add and test for negative result……Page 120
5.2.10 Atomically exchanging a value……Page 121
5.3.1 Spinlocks with no debugging……Page 123
5.3.3 Spinlocks with full debugging……Page 125
5.4.2 Initialising a spinlock……Page 128
5.4.3 Operations on spinlocks……Page 129
5.5.2 Multiprocessor implementation……Page 134
5.6 Single- processor version of read ¨C write locks……Page 137
5.7.1 Data structures and initialisation……Page 138
5.7.2 Operations on read ¨C write locks……Page 139
5.7.3 Macros to operate on read locks……Page 142
5.7.4 Macros to operate on write locks……Page 145
5.7.5 Assembly language helper routines for read ¨C write locks……Page 146
6.1 Kernel semaphores……Page 149
6.1.1 Semaphore data structures and macros……Page 150
6.1.2 Operations on semaphores……Page 152
6.1.3 Intermediate- level routines……Page 156
6.1.4 Semaphore worker functions……Page 160
6.2.1 Data structures……Page 166
6.2.2 High- level manipulation of read ¨C write semaphores……Page 170
6.2.3 Acquiring and releasing a read ¨C write semaphore……Page 171
6.2.4 Interaction with the scheduler……Page 177
6.2.5 Atomic operations on read ¨C write semaphore values……Page 185
6.3 Completions……Page 186
6.3.2 Signalling a completion……Page 187
6.3.3 Waiting for completion……Page 188
7.1.1 Scheduling policies in Linux……Page 191
7.1.2 The Linux scheduler……Page 192
7.2.1 Scheduler- related data structures and macros……Page 193
7.2.2 Global scheduler structures……Page 195
7.2.3 Task state segment……Page 196
7.2.4 Kernel statistics……Page 199
7.3.1 Eliminating exceptions……Page 201
7.3.2 Scheduling preliminaries……Page 203
7.3.3 Selecting the next process to run……Page 204
7.3.4 Recording a scheduling decision……Page 206
7.3.5 Context switching……Page 207
7.4.1 Scheduling macros……Page 209
7.4.2 Calculating the of a process……Page 210
7.4.3 Determining the quantum for a process……Page 212
7.5 Context switching……Page 213
7.5.1 Preparing to context switch……Page 214
7.5.2 Switching the computer processing unit context……Page 216
7.5.3 Loading a debug register……Page 217
7.5.4 Cleaning up after the context switch……Page 218
7.5.5 Releasing a computer processing unit……Page 220
7.6.1 Trying the computer processing unit on which the process last ran……Page 221
7.6.2 Finding another computer processing unit……Page 222
7.6.3 The uniprocessor case……Page 225
7.6.4 Comparing suitabilities of two processes……Page 226
8.1.1 Process manager variables……Page 227
8.1.2 Initialisation routine……Page 228
8.2.1 Checking permissions and allocating data structure……Page 229
8.2.2 Initialising fields in the new……Page 230
8.2.3 Initialising time- related fields……Page 233
8.2.4 Copying external process information……Page 234
8.2.5 Linking into process structure……Page 235
8.2.6 Error handling……Page 237
8.3.1 Clone flags……Page 240
8.3.3 Allocating a process identification number……Page 241
8.3.4 Copying signal handlers……Page 245
8.3.5 Setting up the structure for a child process……Page 246
8.3.6 The child¡¯s return path……Page 249
8.4.1 User identification structures……Page 250
8.4.2 The user hash structure……Page 251
8.4.3 Allocating a user structure……Page 252
8.4.4 Deallocating a user structure……Page 255
8.5 Creating a kernel thread……Page 257
9.1 Terminating a process……Page 259
9.2.1 Notifying other processes of termination……Page 262
9.2.2 Notifying child processes of the death of the parent……Page 265
9.2.3 Determining if a process group is orphaned……Page 267
9.2.4 Checking if there is a stopped process in a group……Page 268
9.3 Waiting for a child process to exit……Page 269
9.3.1 Parameter checking and initial setup……Page 270
9.3.2 Searching for a zombie child……Page 271
9.3.3 Waiting for a child to exit……Page 275
9.4.2 Removing the……Page 277
9.4.3 Usage statistics……Page 280
10 Interrupting Linux……Page 285
10.1.1 Data structures……Page 286
10.1.2 Initialising the interrupt descriptor table……Page 288
10.1.3 The default interrupt handler……Page 289
10.2.1 Setting up gates……Page 290
10.2.2 System entries in the interrupt descriptor table……Page 293
10.3.1 Format of saved registers on the stack……Page 295
10.3.2 Saving registers……Page 298
10.3.4 Finding the current……Page 299
10.3.5 Offsets into the……Page 300
10.4.1 The Intel binary specification entry point……Page 301
10.4.3 The Linux system call entry……Page 303
10.5.1 Divide error……Page 307
10.5.2 Co- processor errors……Page 310
10.5.4 The nonmaskable interrupt……Page 312
10.5.5 Exceptions requiring trivial handling……Page 313
10.5.6 Exceptions with error code provided by the computer processing unit……Page 315
10.6 Returning from an interrupt……Page 316
10.6.2 Returning from exceptions and interrupts……Page 317
10.6.3 Detecting a pending signal……Page 319
10.6.5 Summary……Page 321
11.1.1 Generating the handlers……Page 323
11.1.2 The generating macros……Page 324
11.1.3 The generic handler function……Page 326
11.2.1 Debug registers……Page 328
11.2.2 The debug exception handler……Page 329
11.3.1 Second- level handler for the nonmaskable interrupt……Page 332
11.3.2 Checking if the computer processing unit is locked up……Page 334
11.3.4 Parity error on an expansion card……Page 337
11.3.5 Unidentifiable reason for nonmaskable interrupt……Page 338
11.4 General protection……Page 339
11.6.1 Wrapper for machine check handler……Page 341
11.6.2 Second- level handler for machine check……Page 342
11.6.3 Machine- specific registers……Page 345
11.6.4 Reading and writing machine- specific registers……Page 346
11.7.1 No floating point unit present……Page 347
11.7.2 Floating point unit registers not valid……Page 348
11.8.2 The main handler for a co- processor error……Page 349
11.9.1 Error in a non- SIMD co- processor……Page 352
11.9.2 SIMD co- processor errors……Page 354
11.10.1 Checking for additional features……Page 356
11.10.2 Manipulating floating point unit registers……Page 357
11.10.3 Retrieving values from structure……Page 361
11.10.4 Terminating a process……Page 362
12.1 Programmable interrupt controller……Page 365
12.2.2 Status bits……Page 367
12.2.3 Descriptor for an interrupt handler……Page 368
12.2.4 Table of hardware interrupt line descriptors……Page 369
12.2.5 Default functions for an interrupt controller…….Page 370
12.3 First- level handlers for hardware interrupts……Page 371
12.3.1 Table of first- level handlers……Page 372
12.3.2 Generating first- level interrupt handlers……Page 373
12.4.1 Generic second- level interrupt handling……Page 376
12.4.2 Running the handlers for a hardware interrupt……Page 379
12.5.1 Initialising hardware interrupts……Page 381
12.5.2 Initialising the array for a programmable interrupt controller……Page 384
12.5.4 Initialising irq13 and irq2……Page 386
12.5.5 Handler for irq13……Page 387
12.6.1 Requesting an interrupt line……Page 388
12.6.2 Freeing an interrupt line……Page 393
12.6.3 Disabling an irq……Page 395
12.6.4 Enabling an irq line……Page 397
12.7 The 8259A programmable interrupt controller……Page 398
12.7.1 Programming the programmable interrupt controller……Page 399
12.7.2 Data structures……Page 400
12.7.3 Initialising the programmable interrupt controller……Page 402
12.7.5 Enable……Page 404
12.7.6 Disable……Page 405
12.7.7 Acknowledge……Page 406
12.7.9 Determining if an interrupt is pending……Page 410
12.8 Interrupt- safe locks……Page 411
12.8.1 Macros for interrupt- safe locks……Page 412
12.8.2 Generic interrupt macros……Page 413
12.9 Functions for reading and writing input ¨C output ports……Page 414
12.9.1 Single input ¨C output functions……Page 415
12.9.2 String input ¨C ouput functions……Page 418
12.9.3 Pausing an input ¨C output operation……Page 420
13 Advanced programmable interrupt controllers……Page 423
13.1.1 Identification and priority……Page 424
13.1.2 Interrupt handling registers……Page 425
13.1.3 Interrupt command register……Page 427
13.1.4 The local vector table……Page 429
13.2.1 Sanity checks and APIC identification……Page 432
13.2.2 Enabling the APIC……Page 433
13.2.3 The local interrupt pins……Page 434
13.2.4 Error handling on a local APIC……Page 436
13.2.5 Setup virtual wire mode……Page 437
13.3.1 Interface functions for a local APIC……Page 438
13.3.2 Generic functions for manipulating a local APIC……Page 440
13.4.1 Basic functions for accessing APICs……Page 443
13.4.2 An APIC needing read before write……Page 444
13.5.2 The call function interrupt……Page 445
13.5.3 Shortcut addressing for sending interprocessor interrupts……Page 448
13.5.4 Low- level functions to send an interprocessor interrupt……Page 450
13.6.1 Instantiating first- level handlers for APIC interrupts……Page 455
13.6.2 Macros to build first- level handlers for APIC interrupts……Page 456
13.7.1 The reschedule interrupt……Page 458
13.7.2 The call function interrupt……Page 459
13.7.3 Local APIC timer interrupt……Page 460
13.7.4 The local error interrupt……Page 464
13.7.6 Resending an irq……Page 465
14.1 Interrupt configuration tables in Linux……Page 467
14.1.1 Data structures……Page 468
14.1.2 Reading the interrupt configuration tables……Page 471
14.1.3 Getting the polarity and trigger type of an irq line……Page 475
14.1.4 The array……Page 482
14.2.1 General APIC registers……Page 484
14.2.2 Routing registers……Page 485
14.2.3 Initialising the IO APIC……Page 489
14.2.4 Disabling an IO APIC before rebooting……Page 495
14.3.1 Edge triggered interrupts on an IO APIC……Page 498
14.3.2 Level triggered interrupts on an IO APIC……Page 500
14.4.1 Masking and unmasking irqs on an IO APIC……Page 503
14.4.2 Macros to generate masking and unmasking functions……Page 504
14.4.3 Macro to manipulate an IO APIC register……Page 505
14.4.4 Setting affinity for an IO APIC……Page 506
14.4.5 Reading and writing IO APICs……Page 507
14.5.1 The global interrupt request lock……Page 508
14.5.2 Enabling and disabling interrupts globally……Page 513
14.5.3 Global flags……Page 515
15.1.1 Variables used by timer interrupt handler……Page 519
15.1.3 Subsidiary functions……Page 520
15.1.4 Second- level timer interrupt handling……Page 525
15.2.1 Delayed timer processing……Page 526
15.2.2 Maintaining the time of day……Page 527
15.2.3 Updating the time- of- day clock by one tick……Page 528
15.2.4 Refining the accuracy of the clock……Page 532
15.2.5 Generating load statistics……Page 541
15.3 Event timers……Page 544
15.3.1 Event timer data structures……Page 545
15.3.2 Timer management……Page 548
15.3.3 Sleeping for a fixed length of time……Page 554
15.3.4 Handling expired timers……Page 557
16 Software interrupts……Page 563
16.1.1 Data structures……Page 564
16.1.2 Initialising software interrupts……Page 565
16.1.3 Running a software interrupt……Page 566
16.1.4 The software interrupt kernel thread……Page 569
16.1.5 Raising a software interrupt……Page 572
16.2.1 Data structures……Page 574
16.2.3 Scheduling standard- priority tasklets……Page 576
16.2.4 Scheduling high- priority tasklets……Page 578
16.2.5 Enabling and disabling tasklets……Page 579
16.2.6 The standard priority tasklet software interrupt……Page 581
16.2.7 The high- priority tasklet software interrupt……Page 583
16.2.8 Tasklet locking……Page 585
16.3.1 Data structures……Page 586
16.3.2 Executing bottom halves……Page 588
16.4 Task queues……Page 589
16.4.2 Inserting a task on a queue……Page 590
16.4.3 Run queued tasks……Page 591
16.4.4 Predefined task queues……Page 593
16.5.1 Data structures and macros……Page 594
16.5.2 Nesting software interrupts……Page 596
16.5.3 Manipulating interrupt counters……Page 598
17.1.1 Basic definitions……Page 601
17.1.2 Signal definitions……Page 602
17.1.3 Process- specific signal handling information……Page 605
17.1.4 Queue of pending signals……Page 608
17.1.5 Extended information about a signal……Page 609
17.2.1 Manipulating a specific bit in a bitmap……Page 617
17.2.2 Manipulating whole bitmaps……Page 619
17.2.3 Manipulating subsets of a bitmap……Page 623
17.3 Installing a signal handler……Page 625
17.4.1 Deallocating handler and queue head structures……Page 627
17.4.2 Deallocating all queued signals……Page 628
17.4.3 Flushing all pending signals for a process……Page 629
17.4.4 Flushing all handlers for a process……Page 630
17.5.2 Deactivating the callback function……Page 631
17.6.1 Alternate signal stack……Page 632
17.6.2 Setting or getting an alternate stack context……Page 633
17.6.3 Checking for an alternate signal stack……Page 636
18.1.1 Sending a signal, with extra information……Page 637
18.1.2 Subsidiary functions……Page 639
18.1.3 Posting a signal to the target process……Page 644
18.2.1 Forcing the delivery of a signal……Page 649
18.2.2 Sending a signal to all processes in a group……Page 650
18.2.3 Sending a signal to a session leader……Page 651
18.2.4 Sending a signal to a specific process identification number……Page 652
18.2.5 Sending a signal to a range of processes……Page 653
18.2.6 Sending signals to a parent……Page 655
18.2.7 Backward compatibility functions for sending signals……Page 658
18.3.1 Checking the field……Page 659
18.3.3 Recalculating the signal state……Page 660
18.4 Delivering a pending signal……Page 661
18.4.1 Identifing the pending signal……Page 662
18.4.2 Signal pending to a traced process……Page 663
18.4.3 Ignoring a signal……Page 664
18.4.4 Default handling for a signal……Page 665
18.4.5 Signal with a user- defined handler……Page 667
18.4.6 Restarting an interrupted system call……Page 668
18.5.1 Dequeue a signal……Page 669
18.5.2 Subsidiary functions……Page 671
19.1 Handling a signal……Page 677
19.2.1 Structure of a stack frame……Page 680
19.2.2 Registering context for handling a signal……Page 681
19.2.3 Extended context information for a signal handler……Page 682
19.2.4 Floating point state……Page 683
19.3.1 Setting up a standard stack frame……Page 685
19.3.2 Setting up an extended stack frame……Page 688
19.3.3 Getting a pointer to the stack frame in user space……Page 691
19.4.1 Copying extra signal information to user space……Page 693
19.4.2 Copying the register state to user stack……Page 694
19.4.3 Copying the floating point unit state to the user stack……Page 696
19.5.1 Returning from a standard stack frame……Page 703
19.5.2 Returning from an extended stack frame……Page 705
19.6.1 Restoring signal context from user space……Page 707
19.6.3 Restoring the floating point unit state from the user stack……Page 710
20.1.1 Defined capabilities……Page 717
20.1.2 Capability bitmaps……Page 720
20.2.1 Converting between capability types……Page 721
20.2.3 Combining two capability sets……Page 722
20.2.5 Removing specified bits from a capability bitmap……Page 723
20.2.7 Miscellaneous macros……Page 724
20.3.1 Setting capabilities for all processes……Page 725
20.4.1 Checking for a particular capability……Page 726
20.4.2 Checking for root privileges……Page 727
20.4.4 Checking a security setting……Page 728
21.1.1 Personality types……Page 731
21.1.3 Manipulating personalities……Page 733
21.2.1 The structure……Page 734
21.2.2 The execution domain list……Page 735
21.2.3 The default system service handler……Page 736
21.3 Registering and unregistering execution domains……Page 737
21.3.1 Registering a new execution domain……Page 738
21.3.2 Unregistering an execution domain……Page 739
21.3.3 Adjusting execution domain module usecounts……Page 740
21.4.2 Changing personality……Page 741
21.4.3 Finding the execution domain corresponding to a personality……Page 743
22.1 Setting up a process to be traced……Page 747
22.2.1 Architecture- independent disabling of tracing……Page 750
22.3 Accessing the memory space of a traced process……Page 751
22.3.1 Reading data from a traced process……Page 752
22.3.2 Writing data to a traced process……Page 753
22.4.1 Writing to a register……Page 754
22.4.2 Reading from a register……Page 756
22.4.3 Manipulating the stack of the traced process……Page 758
22.5 Traced process handling a system call……Page 760
22.6.1 Displaying interrupt and bottom- half state……Page 761
22.6.2 Displaying stack values……Page 763
22.6.3 Displaying call frames on the stack……Page 764
22.6.4 Displaying register contents……Page 765
23.1.1 Variables used by the accounting subsystem……Page 769
23.1.2 The format of an accounting record……Page 770
23.2.1 Marking that free space needs checking……Page 772
23.2.2 Checking free space……Page 773
23.3.1 Checking that there is an accounting file……Page 775
23.3.2 Writing an accounting record……Page 776
23.4 Encoding an unsigned long……Page 779
24.1.1 Information supplied by user……Page 781
24.1.2 Stack layout……Page 785
24.1.3 Information in the structure……Page 788
24.2.1 Bits in the register……Page 789
24.2.3 Getting the virtual flags……Page 791
24.2.4 Setting values in the virtual flags register……Page 792
24.2.5 Manipulating bits in the virtual flags register……Page 793
24.3.1 Emulating instructions……Page 794
24.3.2 Reading values from memory……Page 797
24.4.1 The system call……Page 799
24.4.2 Internal processing……Page 800
24.5 Trap handling in vm86 mode……Page 803
24.6 Handling faults in vm86 mode……Page 805
24.6.1 Macros and local variables……Page 806
24.6.2 Two- byte instructions……Page 807
24.6.3 Single- byte instructions……Page 809
24.7.1 Handling a vectored interrupt in vm86 mode……Page 813
24.7.2 Checking the revectored bitmap……Page 815
24.8.1 Returning to protected mode……Page 816
24.8.2 Writing vm86 state to user space……Page 817
24.8.3 Returning values from vm86 mode……Page 819
Index……Page 821
Reviews
There are no reviews yet.