Оглавление
Об авторах 19
Предисловие 21
Наша читательская аудитория 21
Организация материала 22
Уровень описания 23
Обзор книги 24
На кого рассчитана эта книга 26
Соглашения, принятые в книге 26
Благодарности 26
Глава 1. Введение 29
Сравнение Linux с другими Unix-подобными ядрами 30
Монолитное ядро 31
Откомпилированные и статически скомпонованные традиционные ядра Unix 32
Потоки ядра 32
Поддержка многопоточных приложений 32
Вытеснение в ядре 32
Поддержка многопроцессорной обработки 33
Файловая система 33
STREAMS 33
Зависимость от оборудования 35
Версии Linux 36
Основные понятия операционных систем 37
Многопользовательские системы 39
Пользователи и группы 39
Процессы 40
Архитектура ядра 42
Обзор файловой системы Unix 43
Файлы 43
Жесткие и гибкие ссылки 45
Типы файлов 45
Дескриптор файла и индексный дескриптор 46
Права доступа и режим файла 47
Системные вызовы для работы с файлами 48
Обзор ядер Unix 51
Модель процесс/ядро 51
Реализация процесса 53
Реентерабельные ядра 53
Адресное пространство процесса 55
Синхронизация и критические области 56
Сигналы и взаимодействие между процессами 60
Управление процессами 61
Управление памятью 63
Драйверы устройств 67
Глава 2. Адресация памяти 71
Адреса памяти 71
Сегментация в аппаратной части 73
Селектор сегментов и сегментные регистры 73
Дескрипторы сегментов 74
Быстрый доступ к дескрипторам сегментов 76
Блок сегментации 77
Сегментация в Linux 78
Глобальная таблица дескрипторов Linux 80
Локальные таблицы дескрипторов Linux 82
Управление страницами на аппаратном уровне 83
Обычное управление страницами 84
Расширенное управление страницами 87
Аппаратная схема защиты 88
Пример обычного управления страницами 88
Механизм расширения физических адресов (PAE) 90
Управление страницами в 64-разрядных архитектурах 92
Аппаратный кэш 93
Буферы быстрого преобразования адреса (TLB) 96
Управление страницами в Linux 96
Поля линейного адреса 99
Работа с Таблицей Страниц 100
Схема разбивки физической памяти 107
Таблицы страниц процесса 111
Таблицы страниц ядра 111
Фиксированно отображенные линейные адреса 116
Работа с аппаратным кэшем и TLB-буфером 118
Глава 3. Процессы 123
Процессы, облегченные процессы и потоки 123
Дескриптор процесса 125
Состояние процесса 126
Идентификация процесса 128
Взаимоотношения между процессами 136
Магическая константа 139
Как организованы процессы 143
Ограничения на ресурсы процесса 149
Переключение процессов 151
Аппаратный контекст 151
Сегмент состояния задачи 152
Выполнение переключения процессов 154
Сохранение и загрузка регистров FPU, MMX и XMM 161
Создание процессов 166
Системные вызовы clone(), fork() и vfork() 166
Потоки ядра 177
Уничтожение процессов 180
Завершение процесса 180
Удаление процессов 183
Глава 4. Прерывания и исключения 187
Роль сигналов прерываний 188
Прерывания и исключения 189
Прерывания 189
Исключения 189
IRQ и прерывания 191
Исключения 195
Таблица дескрипторов прерываний 198
Аппаратная обработка прерываний и исключений 199
Вложенное выполнение обработчиков исключений и прерываний 202
Инициализация таблицы дескрипторов прерываний 204
Шлюзы прерываний, ловушек и системы 204
Предварительная инициализация таблицы IDT 206
Обработка исключений 207
Сохранение регистров для обработчика исключений 209
Вход и выход из обработчика исключений 210
Обработка прерываний 211
Обработка прерываний ввода/вывода 212
Обработка межпроцессорных прерываний 235
Softirq-функции и тасклеты 236
Softirq-функции 238
Тасклеты 245
Рабочие очереди 247
Структуры данных для рабочих очередей 248
Возврат из прерываний и исключений 251
Точки входа 254
Возобновление управляющего тракта ядра 255
Проверка вытеснения в ядре 255
Возобновление программы режима пользователя 256
Проверка необходимости перепланирования 256
Обработка висящих сигналов, режима virtual-8086 и пошагового режима 257
Глава 5. Синхронизация в ядре 259
Как ядро обслуживает запросы 259
Вытеснение в ядре 260
Когда синхронизация необходима 263
Когда в синхронизации нет необходимости 264
Примитивы синхронизации 265
Процессорные переменные 266
Атомарные операции 267
Барьеры оптимизации и барьеры памяти 270
Спин-блокировки 272
Спин-блокировки чтения/записи 277
Seqlock-блокировки 280
Обновление копии для чтения (RCU) 282
Семафоры 284
Семафоры чтения/записи 289
Completion-блокировки 290
Отключение локальных прерываний 291
Запрет и разрешение функций отложенного выполнения 292
Синхронизация обращений к структурам данных ядра 293
Выбор между спин-блокировками, семафорами и отключением прерываний 295
Примеры предотвращения конфликтов 301
Счетчики ссылок 301
Глобальная блокировка ядра 301
Семафор чтения/записи для дескриптора памяти 304
Семафор для списка slab-кэшей 304
Семафор для индексного дескриптора 304
Глава 6. Хронометраж 307
Микросхемы часов и таймеров 308
Часы реального времени 308
Счетчик отметок времени 309
Программируемый таймер интервалов 309
Локальный таймер процессора 311
Высокоточный таймер событий 312
ACPI-таймер управления питанием 313
Архитектура хронометрирования в Linux 313
Структуры данных в архитектуре хронометрирования 314
Архитектура хронометрирования в однопроцессорных системах 318
Архитектура хронометрирования в многопроцессорных системах 321
Обновление времени и даты 323
Обновление системной статистики 324
Обновление статистики локального процессора 324
Отслеживание нагрузки на систему 325
Профилирование кода ядра 326
Проверка сторожей NMI Watchdog 327
Программные таймеры и функции задержки 327
Динамические таймеры 328
Применение динамических таймеров: системный вызов nanosleep() 335
Функции задержки 337
Системные вызовы, относящиеся к хронометрированию 338
Системные вызовы time() и gettimeofday() 338
Системный вызов adjtimex() 340
Системные вызовы setitimer() и alarm() 341
Системные вызовы для таймеров POSIX 342
Глава 7. Планирование процессов 345
Политика планирования 345
Вытеснение процессов 348
Сколько должен длиться квант времени? 349
Алгоритм планирования 350
Планирование обычных процессов 351
Планирование процессов реального времени 355
Структуры данных, используемые планировщиком 356
Структура runqueue 356
Дескриптор процесса 359
Функции, вызываемые планировщиком 361
Функция scheduler_tick() 361
Функция try_to_wake_up() 365
Функция recalc_task_prio() 367
Функция schedule() 369
Балансирование очередей на выполнение в многопроцессорных системах 378
Области планирования 380
Функция rebalance_tick() 382
Функция load_balance() 383
Функция move_tasks() 384
Системные вызовы, относящиеся к планированию 385
Системный вызов nice() 385
Системные вызовы getpriority() и setpriority() 386
Системные вызовы sched_getaffinity() и sched_setaffinity() 387
Системные вызовы, относящиеся к процессам реального времени 388
Глава 8. Управление памятью 391
Управление страничными кадрами 391
Дескрипторы страниц 392
Доступ к неоднородной памяти (NUMA) 395
Зоны памяти 397
Пул зарезервированных страничных кадров 401
Зонный аллокатор страничных кадров 402
Отображение ядром страничных кадров верхней памяти 405
Алгоритм "buddy-система" 413
Кэш страничных кадров процессора 419
Аллокатор зон 422
Управление областями памяти 427
Slab-аллокатор 427
Дескриптор кэша 429
Дескриптор участка памяти 431
Общие и специальные кэши 432
Интерфейс между slab-аллокатором и зонным аллокатором страничных
кадров 434
Выделение участка памяти кэшу 436
Освобождение участка памяти из кэша 437
Дескриптор объекта 438
Выравнивание объектов в памяти 439
Окрашивание участков памяти 439
Локальные кэши свободных объектов-участков памяти 441
Выделение объекта в участке 443
Освобождение объекта в участке 445
Объекты общего назначения 447
Пулы памяти 448
Управление несмежными областями памяти 450
Линейные адреса несмежных областей памяти 451
Дескрипторы несмежных областей памяти 451
Выделение несмежной области памяти 453
Освобождение несмежной области памяти 457
Глава 9. Адресное пространство процесса 461
Адресное пространство процесса 462
Дескриптор памяти 464
Дескриптор памяти для потоков ядра 468
Области памяти 470
Структуры данных для областей памяти 472
Права доступа к области памяти 475
Работа с областями памяти 479
Выделение интервала линейных адресов 484
Освобождение интервала линейных адресов 488
Обработчик исключения "ошибка обращения к странице" 493
Обработка ошибочного адреса, не входящего в адресное пространство 499
Обработка ошибочного адреса, входящего в адресное пространство 500
Выделение страниц по требованию 503
Копирование при записи 507
Обработка обращений к несмежным областям памяти 510
Создание и удаление адресного пространства процесса 512
Создание адресного пространства процесса 512
Удаление адресного пространства процесса 514
Управление кучей 515
Глава 10. Системные вызовы 519
API-интерфейсы стандарта POSIX и системные вызовы 519
Обработчик системного вызова и служебные процедуры 521
Вход в системный вызов и выход из него 523
Выполнение системного вызова с помощью инструкции int $0x80 523
Выполнение системного вызова с помощью инструкции sysenter 526
Передача параметров 532
Проверка параметров 534
Доступ к адресному пространству процесса 536
Динамическая проверка адресов: код обработки исключения 538
Таблицы исключений 539
Генерирование таблицы исключений и кода обработки 540
Интерфейсные процедуры ядра 543
Глава 11. Сигналы 545
Роль сигналов 545
Действия, выполняемые при доставке сигнала 550
Сигналы POSIX и многопоточные приложения 551
Структуры данных, ассоциированные с сигналами 552
Операции над сигнальными структурами 558
Генерирование сигнала 560
Функция specific_send_sig_info() 561
Функция send_signal() 562
Функция group_send_sig_info() 564
Доставка сигнала 567
Выполнение действия по умолчанию по обработке сигнала 569
Обработка сигнала 571
Повторное выполнение системных вызовов 576
Системные вызовы, связанные с обработкой сигналов 580
Системный вызов kill() 580
Системные вызовы tkill() и tgkill() 581
Изменение действия сигнала 582
Просмотр висящих заблокированных сигналов 583
Модификация набора заблокированных сигналов 584
Приостановка выполнения процесса 585
Системные вызовы для сигналов реального времени 586
Глава 12. Виртуальная файловая система 587
Роль виртуальной файловой системы (VFS) 587
Общая файловая модель 590
Системные вызовы, обрабатываемые VFS 593
Структуры данных VFS 594
Суперблоки 595
Индексный дескриптор 600
Файловые объекты 605
Элемент каталога 610
Кэш элементов каталога 613
Файлы, связанные с процессом 615
Типы файловых систем 618
Специальные файловые системы 618
Регистрация типа файловой системы 620
Работа с файловой системой 622
Пространства имен 622
Монтирование файловых систем 623
Монтирование типичной файловой системы 627
Монтирование корневой файловой системы 632
Размонтирование файловой системы 635
Анализ пути 636
Стандартный анализ пути 640
Анализ пути к родительскому каталогу 645
Анализ символьных ссылок 647
Реализация системных вызовов VFS 649
Системный вызов open() 649
Системные вызовы read() и write() 652
Системный вызов close() 654
Блокировка файлов 654
Блокировка файлов в Linux 656
Структуры данных для блокировок файлов 657
Блокировки FL_FLOCK 659
Блокировки FL_POSIX 662
Глава 13. Архитектура ввода/вывода и драйверы устройств 667
Архитектура ввода/вывода 667
Порты ввода/вывода 669
Интерфейсы ввода/вывода 672
Контроллеры устройств 674
Модель драйвера устройства 675
Файловая система sysfs 676
Объекты kobject 677
Компоненты модели драйвера устройства 681
Файлы устройств 687
Работа с файлами устройств в режиме пользователя 689
Работа с файлами устройств в VFS 691
Драйверы устройств 692
Регистрация драйвера устройства 693
Инициализация драйвера устройства 694
Мониторинг операций ввода/вывода 694
Обращение к совместно используемой памяти ввода/вывода 698
Прямой доступ к памяти (DMA) 700
Уровни поддержки ядра 705
Драйверы символьных устройств 707
Присваивание номеров устройств 709
Обращение к драйверу символьного устройства 712
Стратегии буферизации для символьных устройств 713
Глава 14. Драйверы блочных устройств 715
Управление блочными устройствами 716
Секторы 719
Блоки 720
Сегменты 721
Общий слой работы с блочными устройствами 722
Структура bio 723
Представление дисков и разделов на диске 725
Выдача запроса 728
Планировщик ввода/вывода 730
Дескрипторы очередей запросов 731
Дескриптор запросов 734
Активизация драйвера блочного устройства 739
Алгоритмы планирования ввода/вывода 740
Выдача запроса планировщику ввода/вывода 744
Драйверы блочных устройств 747
Блочные устройства 747
Регистрация и инициализация драйвера устройства 751
Процедура-стратег 755
Обработчик прерываний 758
Открытие файла блочного устройства 759
Глава 15. Кэш страниц 763
Кэш страниц 764
Объект address_space 765
Базисное дерево 769
Функции для работы с кэшем страниц 772
Теги базисного дерева 776
Хранение блоков в кэше страниц 778
Буферы блоков и головы буферов 779
Работа с головами буферов 780
Страницы буферов 781
Выделение страниц буферов блочных устройств 783
Освобождение страниц буферов блочных устройств 785
Поиск блоков в кэше страниц 785
Передача голов буферов общему слою работы с блочными устройствами 788
Запись грязных страниц на диск 791
Потоки ядра pdflush 792
Поиск грязных страниц для записи на диск 794
Запись старых грязных страниц на диск 799
Системные вызовы sync(), fsync() и fdatasync() 800
Системный вызов sync() 800
Системные вызовы fsync() и fdatasync() 801
Глава 16. Работа с файлами 803
Чтение и запись файла 804
Чтение из файла 805
Опережающее чтение файлов 817
Запись в файл 824
Запись грязных страниц на диск 831
Отображение в память 834
Структуры отображения в память 835
Создание отображения в память 837
Уничтожение отображения в память 840
Выделение страниц по требованию для отображения в память 840
Принудительная запись на диск грязных страниц отображения в память 844
Нелинейные отображения в память 845
Прямой ввод/вывод 847
Асинхронный ввод/вывод 850
Асинхронный ввод/вывод в Linux 2.6 852
Глава 17. Утилизация страничных кадров 857
Алгоритм утилизации страничных кадров 857
Выбор целевой страницы 858
Описание алгоритма PFRA 861
Обратное отображение 863
Обратное отображение для анонимных страниц 865
Обратное отображение для отображающих страниц 870
Реализация алгоритма PFRA 874
Списки давно неиспользуемых страниц (LRU) 876
Утилизация при дефиците памяти 884
Утилизация страниц сокращаемых кэшей диска 893
Периодическая утилизация 896
Уничтожение процессов из-за нехватки памяти 899
Жетон защиты от выгрузки 901
Подкачка 902
Область подкачки 904
Дескриптор области подкачки 906
Идентификатор выгруженной страницы 909
Перевод области подкачки в активное и неактивное состояние 911
Выделение и освобождение страничного слота 919
Кэш подкачки 922
Выгрузка страниц 926
Загрузка выгруженных страниц 929
Глава 18. Файловые системы Ext2 и Ext3 935
Общие характеристики файловой системы Ext2 936
Структуры Ext2 на диске 939
Суперблок 940
Дескриптор группы и битовая карта 943
Таблица индексных дескрипторов 944
Расширенные атрибуты индексного дескриптора 946
Списки управления доступом 947
Как файлы разных типов используют блоки на диске 948
Структуры Ext2 в памяти 950
Объект-суперблок Ext2 951
Индексный дескриптор Ext2 953
Создание файловой системы Ext2 954
Методы Ext2 956
Операции суперблока Ext2 956
Операции индексного дескриптора Ext2 956
Файловые операции Ext2 958
Управление пространством на диске в Ext2 959
Создание индексных дескрипторов 960
Удаление индексных дескрипторов 963
Адресация блоков данных 964
Дыры в файлах 967
Выделение блоков данных 968
Освобождение блока данных 969
Файловая система Ext3 970
Журналируемые файловые системы 971
Ext3 — журналируемая файловая система 971
Слой журналирующего блочного устройства 973
Как ведется журнал 977
Глава 19. Взаимодействие процессов 981
Каналы 982
Работа с каналом 983
Структуры данных для канала 985
Создание и уничтожение канала 989
Чтение из канала 990
Запись в канал 993
FIFO-файлы 995
Создание и открытие FIFO-файлов 996
Схема межпроцессного взаимодействия System V IPC 999
Работа с ресурсом IPC 999
Системный вызов ipc() 1003
Семафоры IPC 1004
Сообщения IPC 1009
Совместно используемая память IPC 1013
Очереди сообщений POSIX 1018
Глава 20. Выполнение программ 1021
Исполняемые файлы 1022
Права и способности процесса 1023
Аргументы командной строки и окружение оболочки 1030
Библиотеки 1031
Сегменты программы и области памяти процесса 1033
Отслеживание выполнения 1038
Форматы исполняемых файлов 1041
Области выполнения 1043
Функции exec 1045
Приложение 1. Запуск системы 1053
Доисторические времена: BIOS 1053
Античность: загрузчик 1055
Загрузка Linux с диска 1056
Средние века: функция setup() 1057
Эпоха Возрождения: функции startup_32() 1058
Новейшее время: функция start_kernel() 1060
Приложение 2. Модули 1061
Быть (модулем) или не быть? 1061
Лицензии на модули 1062
Реализация модулей 1063
Счетчики обращений 1066
Экспортирование символов 1067
Зависимости модулей 1067
Подключение и выгрузка модулей 1068
Подключение модулей по требованию 1071
Программа modprobe 1071
Функция request_module() 1072
Предметный указатель 1073
16
Оглавление
17
Оглавление