rt-g0_1fcd69d8-KnR_C-russian/chapters/chapter8.tex

\chapter{Интерфейс с системой UNIX}
\label{chapt:unix_system_interface}

\index{системный вызов}%
Свои услуги операционная система UNIX предлагает в виде набора \emph{системных
вызовов}, которые фактически являются её внутренними функциями и к которым можно
обращаться из программ пользователя. В настоящей главе описано, как в
Си-программах можно применять некоторые наиболее важные вызовы. Если вы
работаете в системе UNIX, то эти сведения будут вам полезны непосредственно и
позволят поднять эффективность работы или получить доступ к тем возможностям,
которых нет в библиотеке. Даже если вы используете Си в другой операционной
системе, изучение рассмотренных здесь примеров всё равно приблизит вас к
пониманию программирования на Си; аналогичные программы (отличающиеся лишь
деталями) вы встретите практически в любой операционной системе. Так как
библиотека Си-программ, утверждённая в качестве стандарта ANSI, в основном
отражает возможности системы UNIX, предлагаемые программы помогут вам лучше
понять и библиотеку.

Глава состоит из трёх основных частей, описывающих: ввод-вывод, файловую систему
и организацию управления памятью. В первых двух частях предполагается некоторое
знакомство читателя с внешними характеристиками системы UNIX.

В гл.~\ref{chapt:input-output} мы рассматривали единый для всех операционных
систем интерфейс ввода-вывода. В любой конкретной системе программы стандартной
библиотеки пишутся с использованием средств именно этой конкретной системы. В
следующих нескольких разделах мы опишем вызовы системы UNIX по вводу-выводу и
покажем, как с их помощью можно реализовать некоторые разделы стандартной
библиотеки.

\section{Дескрипторы файлов}

\index{дескриптор файла}%
\index{файл!дескриптор}%
\index{файл!доступ к}%
В системе UNIX любые операции ввода-вывода выполняются посредством чтения и
записи файлов, поскольку все внешние устройства, включая клавиатуру и экран,
рассматриваются как объекты файловой системы. Это значит, что все связи между
программой и внешними устройствами осуществляются в рамках единого однородного
интерфейса.

\index{файл!открытие}%
В самом общем случае, прежде чем читать или писать, вы должны информировать
систему о действиях, которые вы намереваетесь выполнять в отношении файла; эта
процедура называется \emph{открытием} файла.
\index{файл!создание}%
Если вы собираетесь писать в файл, то, возможно, его потребуется создать заново
или очистить от хранимой информации. Система проверяет ваши права на эти
действия (файл существует? вы имеете к нему доступ?), и, если всё в порядке,
возвращает программе небольшое неотрицательное целое, называемое
\emph{дескриптором файла}. Всякий раз, когда осуществляется ввод-вывод,
идентификация файла выполняется по его дескриптору, а не по имени. (Дескриптор
файла аналогичен файловому указателю, используемому в стандартной библиотеке,
или хэндлу в MS-DOS.) Вся информация об открытом файле хранится и обрабатывается
операционной системой; программа пользователя ссылается на файл только через его
дескриптор.

\index{ввод!с клавиатуры}%
Ввод с клавиатуры и
\index{вывод!на экран}%
вывод на экран применяются настолько часто, что для удобства работы с ними
предусмотрены специальные соглашения.
\index{стандартный!ввод}%
\index{стандартный!вывод}%
При запуске программы командный интерпретатор (shell) открывает три файла с
дескрипторами $0$, $1$ и $2$, которые называются соответственно стандартным
вводом, стандартным выводом и стандартным файлом ошибок. Если программа читает
из файла $0$, а пишет в файлы $1$ и $2$ (здесь цифры -- дескрипторы файлов), то
она может осуществлять ввод и вывод, не заботясь об их открытии.

Пользователь программы имеет возможность
\index{ввод-вывод!перенаправление}%
перенаправить ввод-вывод в файл или из файла при помощи значков \verb|<| и
\verb|>|, как, например, в

\begin{ShortCodePar}
prog <infile >outfile
\end{ShortCodePar}

\noindent В этом случае командный интерпретатор заменит стандартные установки
дескрипторов $0$ и $1$ на именованные файлы. Обычно дескриптор файла $2$
остаётся подсоединённым к экрану, чтобы на него шли сообщения об ошибках.
\index{трубопроводный механизм}%
Сказанное верно и для ввода-вывода, включённого в <<трубопровод>>. Во всех
случаях замену файла осуществляет командный интерпретатор, а не программа.
Программа, если она ссылается на файл $0$ (в случае ввода) и файлы $1$ и $2$ (в
случае вывода), не знает, ни откуда приходит её ввод, ни куда отправляется её вывод.


\section{Нижний уровень ввода-вывода (\texorpdfstring{\protect\Verb|read|}{read}
и \texorpdfstring{\protect\Verb|write|}{write})}

\index{системный вызов!read@\texttt{read}}%
\index{системный вызов!write@\texttt{write}}%
Ввод-вывод основан на системных вызовах \verb|read| и \verb|write|, к которым
Си-программа обращается с помощью функций с именами \verb|read| и \verb|write|.
Для обеих первым аргументом является дескриптор файла. Во втором аргументе
указывается массив литер программы, куда читаются или откуда пишутся данные.
Третий аргумент -- это количество пересылаемых байтов.

\begin{ShortCodePar}
int n_read = read(int fd, char *buf, int n);
int n_written = write(int fd, char *buf, int n);
\end{ShortCodePar}

\noindent Обе функции возвращают число переданных байтов. При чтении количество
прочитанных байтов может оказаться меньше числа, указанного в третьем аргументе.
Нуль означает конец файла, а $-1$ сигнализирует о какой-то ошибке. При записи
функция возвращает количество записанных байтов, и если это число не совпадает с
требуемым, следует считать, что запись не прошла.

За один вызов можно прочитать или записать любое число байтов. Обычно это число
равно или $1$, что означает
\index{ввод!без буферизации}%
политерную передачу <<без буферизации>>, или чему-нибудь вроде $1024$ или
$4096$, соответствующих размеру физического блока внешнего устройства.
Эффективнее обмениваться
\index{ввод!с буферизацией}%
б\'{o}льшим числом байтов, поскольку при этом требуется меньше системных
вызовов.
\index{программа!копирования файлов}%
Используя полученные сведения, мы можем написать простую программу,
копирующую свой ввод на свой вывод, эквивалентную программе копирования файла,
описанной в гл.~\ref{chapt:tutorial_intro}. При помощи этой программы можно
копировать откуда угодно и куда угодно, поскольку всегда существует возможность
перенаправить ввод-вывод на любой файл или устройство.

\begin{LongCodePar}
#include "syscalls.h"
main() /* копирование ввода на вывод */
{
    char buf[BUFSIZ];
    int n;
    while ((n = read(0, buf, BUFSIZ)) > 0)
        write(1, buf, n);
    return 0;
}
\end{LongCodePar}

\index{файл!включаемый!syscalls.h@\texttt{syscalls.h}}%
Прототипы функций, обеспечивающие системные вызовы, мы собрали в файле
\verb|syscalls.h|, что позволяет нам включать его в программы этой главы. Однако
имя данного файла не зафиксировано стандартом.

\index{BUFSIZ@\texttt{BUFSIZ}}%
Параметр \verb|BUFSIZ| также определён в \verb|<syscalls.h>|; в каждой
конкретной системе он имеет своё значение. Если размер файла не кратен
\verb|BUFSIZ|‚ то какая-то операция чтения вернёт значение меньшее, чем
\verb|BUFSIZ|‚ а следующее обращение к \verb|read| даст в качестве результата
нуль.

Полезно рассмотреть, как используются \verb|read| и \verb|write| при написании
программ более высокого уровня -- типа \verb|getchar|, \verb|putchar| и т.д.
\index{небуферизованный \texttt{getchar}}%
\index{getchar@\texttt{getchar}!без буферизации}%
Вот, к примеру, версия программы \verb|getchar|, которая осуществляет
\index{ввод!без буферизации}%
небуферизованный ввод, читая по одной литере из стандартного входного потока.

\begin{ShortCodePar}
#include "syscalls.h"
/* getchar: небуферизованный ввод одной литеры */
int getchar(void)
{
    char c;
    return (read(0, &c, 1) == 1) ? (unsigned char) c : EOF;
}
\end{ShortCodePar}

\index{unsigned char, тип@\texttt{unsigned char}, тип}%
Переменная \verb|c| должна быть описана как \verb|char|, поскольку \verb|read|
требует указатель на \verb|char|. Приведение \verb|c| к \verb|unsigned char|
перед тем, как вернуть её в качестве результата, исключает какие-либо проблемы,
связанные с размножением знака.

Вторая версия
\index{буферизованный \texttt{getchar}}%
\index{getchar@\texttt{getchar}!с буферизацией}%
\verb|getchar| осуществляет
\index{ввод!с буферизацией}%
ввод большими кусками, но при каждом обращении выдаёт только одну литеру.

\begin{LongCodePar}
#include "syscalls.h"
/* getchar: простая версия с буферизацией */
int getchar(void)
{
    static char buf[BUFSIZ];
    static char *bufp = buf;
    static int n = 0;
    if (n == 0) { /* буфер пуст */
        n = read(0, buf, sizeof buf);
        bufp = buf;
    }
    return (--n >= 0) ? (unsigned char) *bufp++ : EOF;
}
\end{LongCodePar}

\index{undef@\texttt{{\#}undef}}%
Если приведённые версии функции \verb|getchar| компилируются с включением
головного файла \verb|<stdio.h>| и в этом головном файле \verb|getchar|
определена как макрос, то нужно задать строку \verb|#undef| с именем
\verb|getchar|.

\section{Системные вызовы
\texorpdfstring{\protect\Verb|open|}{open},
\texorpdfstring{\protect\Verb|creat|}{creat},
\texorpdfstring{\protect\Verb|close|}{close},
\texorpdfstring{\protect\Verb|unlink|}{unlink}}

\index{файл!открытие}%
В отличие от стандартных файлов ввода, вывода и ошибок, которые открыты по
умолчанию, остальные файлы нужно открывать явно. Для этого есть два системных
вызова: \verb|open| и \verb|creat|.

\index{системный вызов!open@\texttt{open}}%
Функция \verb|open| почти совпадает с \verb|fopen|, рассмотренной в
гл.~\ref{chapt:input-output}. Разница между ними в том, что первая возвращает не
файловый указатель, а дескриптор файла типа \verb|int|. При любой ошибке
\verb|open| возвращает $-1$.

\begin{ShortCodePar}
#include <fcntl.h>
int fd;
int open(char *name, int flags, int perms);
fd = open(name, flags, perms);
\end{ShortCodePar}

\noindent Как и в \verb|fopen|, аргумент \verb|name| -- это стринг, содержащий
имя файла.
\index{файл!режим доступа}%
\index{O{\_}RDONLY, O{\_}RDWR, O{\_}WRONLY@\texttt{O{\_}RDONLY}, \texttt{O{\_}RDWR}, \texttt{O{\_}WRONLY}}%
Второй аргумент, \verb|flags|, имеет целый тип и специфицирует, каким образом
должен быть открыт файл. Его основными значениями являются:

\begin{LongRtAlTab2cols}{\codeIndent}{0pt}{\Verb|O{\_}RDONLY|}
\verb|O_RDONLY|&открыть только на чтение \\
\verb|O_WRONLY|&открыть только на запись \\
\verb|O_RDWR|&открыть и на чтение, и на запись
\end{LongRtAlTab2cols}

\noindent%
\index{файл!включаемый!fcntl.h@\texttt{fcntl.h}}%
В системах System V UNIX эти константы определены в \verb|<fcntl.h>|‚ а в
версиях Berkeley (BSD) -- в \verb|<sys/file.h>|.
%
% исправлены опечатки
% в оригинале было ``Berkley'' и ``BCD''
%

Чтобы открыть существующий файл на чтение, можно написать

\begin{ShortCodePar}
fd = open(name, O_RDONLY, 0);
\end{ShortCodePar}

\noindent Далее везде, где мы пользуемся функцией \verb|open|, её аргумент
\verb|perms| равен нулю.

Попытка открыть несуществующий файл считается ошибкой.
\index{системный вызов!creat@\texttt{creat}}%
\index{файл!создание}%
Создание нового файла или перезапись старого обеспечивает системный вызов
\verb|creat|. Например,

\begin{ShortCodePar}
int creat(char *name, int perms);
fd = creat(name, perms);
\end{ShortCodePar}

\noindent Функция \verb|creat| возвращает дескриптор файла, если файл создан, и
$-1$, если по каким-либо причинам файл создать не удалось. Если файл уже
существует, \verb|creat| <<обрежет>> его до нулевой длины, что равносильно
выбрасыванию предыдущего содержимого данного файла; создание уже существующего
файла не является ошибкой.

Если строится действительно новый файл, то \verb|creat| его создаст с правами
доступа, специфицированными в аргументе \verb|perms|.
\index{файл!права доступа}%
В системе UNIX с каждым файлом ассоциированы девять бит, содержащие информацию о
правах пользоваться этим файлом для чтения, записи и исполнения лицам трёх
категорий: собственнику файла, определённой им группе лиц, и всем остальным.
Таким образом, права доступа удобно специфицировать с помощью трёх восьмеричных
цифр. Например, 0755 специфицирует чтение, запись и право исполнения
собственнику файла, а также чтение и право исполнения группе и всем остальным.

\index{программа!копирования файлов}%
Для иллюстрации приведём упрощённую версию программы \verb|cp| системы UNIX‚
которая копирует один файл в другой. В нашей версии копируется только один файл,
не позволяется во втором аргументе указывать директорий (каталог) и права
доступа не копируются, а задаются константой.

\begin{LongCodePar}
#include <stdio.h>
#include <fcntl.h>
#include "syscalls.h"
#define PERMS 0666  /* RW для собственника, группы и ост-х */
void error(char *, ...);

/* cp: копирование f1 в f2 */
main(int argc, char *argv[])
{
    int f1, f2, n;
    char buf[BUFSIZ];
    if (argc != 3)
        error("Обращение: cp откуда куда");
    if ((f1 = open(argv[1], O_RDONLY, 0)) == -1)
        error("cp: не могу открыть файл %s", argv[1]);
    if ((f2 = creat(argv[2], PERMS)) == -1)
        error("cp: не могу создать файл %s, режим %03o",
            argv[2], PERMS);
    while ((n = read(f1, buf, BUFSIZ)) > 0)
        if (write(f2, buf, n) != n)
            error(”cp: ошибка при записи в файл %s", argv[2]);
    return 0;
}
\end{LongCodePar}

\noindent Данная программа создаёт файл вывода с фиксированными правами доступа,
определяемыми кодом 0666. При помощи системного вызова \verb|stat|, который
будет описан в разд.~\ref{chapter:unix_system_interface:sec:directory_print}, мы
можем определить режим использования существующего файла и задать тот же режим
для копии.

\index{функция!error@\texttt{error}}%
Заметим, что функция \verb|error|, вызываемая с различным числом аргументов, во
многом похожа на \verb|printf|. Реализация \verb|error| иллюстрирует, как
пользоваться другими программами семейства \verb|printf|. Библиотечная функция
\index{библиотечная функция!vprintf@\texttt{vprintf}}%
\index{список!аргументов переменной длины}%
\index{файл!головной!<stdarg.h>@\texttt{<stdarg.h>}}%
\verb|vprintf| аналогична \verb|printf|, с той лишь оговоркой‚ что переменная
часть списка аргументов заменена в ней одним аргументом, инициализируемым
\index{va{\_}list, va{\_}start, va{\_}arg, va{\_}end@\texttt{va{\_}list}, \texttt{va{\_}start}, \texttt{va{\_}arg}, \texttt{va{\_}end}}%
макросом \verb|va_start|. Подобным же образом соотносятся функции
\index{библиотечная функция!vfprintf@\texttt{vfprintf}}%
\verb|vfprintf| с \verb|fprintf| и
\index{библиотечная функция!vsprintf@\texttt{vsprintf}}%
\verb|vsprintf| с \verb|sprintf|.

\begin{LongCodePar}
#include <stdio.h>
#include <stdarg.h>

/* error: печатает сообщение об ошибке и умирает */
void error(char *fmt, ...)
{
    va_list args;
    va_start(args, fmt);
    fprintf(stderr, "ошибка: ");
    vfprintf(stderr, fmt, args);
    fprintf(stderr, "\n");
    va_end(args);
    exit(1);
}
\end{LongCodePar}

\index{дескриптор файла}%
\index{файл!дескриптор}%
\index{файл!добавляемый}%
Имеется ограничение на количество одновременно открытых в программе файлов.
(Обычно их число колеблется около 20.) Поэтому любая программа, которая
намеревается работать с большим количеством файлов, должна быть готова повторно
использовать их дескрипторы.
\index{системный вызов!close@\texttt{close}}%
Функция \verb|close(int fd)| разрывает связь между файловым дескриптором и
открытым файлом и освобождает дескриптор для его применения с другим файлом. Она
аналогична библиотечной функции \verb|fclose| с тем лишь различием, что никакого
выталкивания буфера не делает. Завершение программы при помощи \verb|exit| или
\verb|return| в главной программе закрывает все открытые файлы.

\index{системный вызов!unlink@\texttt{unlink}}%
Функция \verb|unlink(char *name)| удаляет имя файла из файловой системы. Она
соответствует функции \verb|remove| стандартной библиотеки.

\paragraph{Упражнение 8.1.} Перепишите программу \verb|cat| из
гл.~\ref{chapt:input-output}, используя функции \verb|read|, \verb|write|,
\verb|open| и \verb|close|. Замените ими соответствующие функции стандартной
библиотеки. Поэкспериментируйте, чтобы сравнить быстродействие двух версий.

\section{Случайный доступ
(\texorpdfstring{\protect\Verb|lseek|}{lseek})}

\index{системный вызов!lseek@\texttt{lseek}}%
Ввод-вывод обычно бывает последовательным, т.е. каждая новая операция
чтения-записи обрабатывает позицию файла, следующую за обработанной в предыдущей
операции (чтения-записи). При желании, однако, файл можно читать в произвольном
порядке. Системный вызов \verb|lseek| предоставляет способ передвигаться по
файлу, не читая и не записывая данные. Так, функция с прототипом

\begin{ShortCodePar}
long lseek(int fd, long offset, int origin);
\end{ShortCodePar}

\noindent в файле с дескриптором \verb|fd| устанавливает текущую позицию, смещая
её на величину \verb|offset| относительно места, задаваемого значением
\verb|origin|. Значения параметра \verb|origin| $0$, $1$ или $2$ означают, что
на величину \verb|offset| отступают соответственно от начала, текущей позиции
или конца файла. Если требуется добавить что-либо в файл (когда, например, в
командном интерпретаторе shell системы UNIX ввод перенаправлен оператором
\verb|>>| в файл или когда в \verb|fopen| задан аргумент \verb|"a"|), то прежде
чем что-либо записывать при помощи вызова функции

\begin{ShortCodePar}
lseek(fd, 0L, 2);
\end{ShortCodePar}

\noindent необходимо найти конец файла. Чтобы вернуться назад, в начало файла,
надо выполнить

\begin{ShortCodePar}
lseek(fd, 0L, 0);
\end{ShortCodePar}

\noindent Следует обратить внимание на аргумент \verb|0L|: вместо \verb|0L|
можно было бы написать \verb|(long) 0| или, если функция \verb|lseek| должным
образом декларирована, просто \verb|0|.

Благодаря \verb|lseek| с файлами можно работать так, как будто это большие
массивы, правда, с замедленным доступом. Например, следующая функция читает
любое число байтов из любого места файла. Она возвращает число прочитанных
байтов или $-1$, в случае ошибки.

\begin{LongCodePar}
#include "syscalls.h"

/* get: читает n байт из позиции pos */
int get(int fd, long pos, char *buf, int n)
{
    if (lseek(fd, pos, 0) >= 0) /* установка позиции */
        return read(fd, buf, n);
    else
        return -1;
}
\end{LongCodePar}

\noindent Возвращаемое функцией \verb|lseek| значение имеет тип \verb|long| и
является новой позицией в файле или, в случае ошибки, равно $-1$. Функция
\verb|fseek| из стандартной библиотеки аналогична \verb|lseek|; от последней она
отличается тем, что в случае ошибки возвращает некоторое ненулевое значение, а
её первый аргумент имеет тип \verb|FILE *|.

\section{Пример. Реализация функций
\texorpdfstring{\protect\Verb|fopen|}{fopen} и
\texorpdfstring{\protect\Verb|getc|}{getc}}
\label{sec:fopen_and_getc}

\index{файл!доступ к}%
Теперь на примере функций \verb|fopen| и \verb|getc| из стандартной библиотеки
покажем, как описанные выше части согласуются друг с другом.

\index{указатель!файла}%
\index{файл!указатель}%
Напомним, что файлы в стандартной библиотеке описываются файловыми указателями,
а не дескрипторами. Указатель файла -- это указатель на структуру,
содержащую информацию о файле: указатель на буфер, позволяющий читать файл
большими кусками; число незанятых байтов буфера; указатель на следующую позицию
в буфере; дескриптор файла; флажки, описывающие режим (чтение/запись), ошибочные
состояния и т.д.

\index{файл!головной!<stdio.h>@\texttt{<stdio.h>}|(}%
\index{stdio.h@\texttt{<stdio.h>}|(}%
Структура данных, описывающая файл, содержится в \verb|<stdio.h>|‚ который
необходимо включать (при помощи \verb|#include|) в любой исходный файл, если в
нём осуществляется стандартный ввод-вывод. Этот же головной файл включён и в
исходные тексты библиотеки ввода-вывода.

В следующем фрагменте, типичном для файла \verb|<stdio.h>|, имена, используемые
только в библиотечных функциях, начинаются с подчёркивания. Это сделано для
того, чтобы они случайно не совпали с именами, фигурирующими в программе
пользователя. Такое соглашение соблюдается во всех программах стандартной
библиотеки.

\index{макрос!feof@\texttt{feof}}%
\index{макрос!ferror@\texttt{ferror}}%
\index{макрос!getc@\texttt{getc}}%
\index{макрос!putc@\texttt{putc}}%
\index{функция!fillbuf@\texttt{{\_}fillbuf}}%
\index{функция!flushbuf@\texttt{{\_}flushbuf}}%
\begin{LongCodePar}
#define NULL      0
#define EOF       (-1)
#define BUFSIZ    1024
#define OPEN_MAX  20   /* макс.число одновр.открытых файлов */
typedef struct _iobuf {
    int  cnt;          /* колич.оставшихся литер */
    char *ptr;         /* позиция следующей литеры */
    char *base;        /* адрес буфера */
    int  flag;         /* режим доступа */
    int fd;            /* дескриптор файла */
} FILE;
extern FILE _iob[OPEN_MAX];
#define stdin  (&_iob[0])
#define stdout (&_iob[1])
#define stderr (&_iob[2])
enum _flag {
    _READ  = 01,       /* файл открыт на чтение */
    _WRITE = 02,       /* файл открыт на запись */
    _UNBUF = 04,       /* файл не буферизуется */
    _EOF   = 010,      /* в данном файле встретился EOF */
    _ERR   = 020       /* в данном файле встретилась ошибка */
};
int _fillbuf(FILE *);
int _flushbuf(int, FILE *);
#define feof(p)     (((p)->flag & _EOF) != 0)
#define ferror(p)   (((p)->flag & _ERR) != 0)
#define fileno(p)   ((p)->fd)
#define getc(p)   (--(p)->cnt >= 0 \
               ? (unsigned char) *(p)->ptr++ : _fillbuf(p))
#define putc(x,p) (--(p)->cnt == 0 \
               ? *(p)->ptr++ = (x) : _flushbuf((x),p))
#define getchar()   getc(stdin)
#define putchar(x)  putc((x), stdout)
\end{LongCodePar}
\index{stdio.h@\texttt{<stdio.h>}|)}%
\index{файл!головной!<stdio.h>@\texttt{<stdio.h>}|)}%

Макрос \verb|getc| обычно уменьшает счётчик числа литер, находящихся на буфере,
и возвращает литеру с последующим продвижением указателя. (Напомним, что длинные
\verb|#define| при помощи обратной наклонной черты можно продолжить на
следующих строках.)
\index{функция!fillbuf@\texttt{{\_}fillbuf}}%
Когда значение счётчика становится отрицательным,
\verb|getc| вызывает \verb|_fillbuf|, чтобы снова заполнить буфер,
инициализировать содержимое структуры и выдать литеру. Типы возвращаемых литер
приводятся к \verb|unsigned|; это гарантирует‚ что все они будут положительными.

Хотя в деталях ввод-вывод здесь не рассматривается, мы всё же привели полное
определение \verb|putc|. Сделано это, чтобы показать, что она действует во
многом так же, как и \verb|getc|, вызывая функцию \verb|_flushbuf|, когда буфер
полон. В тексте имеются макросы, позволяющие получать доступ к флажкам ошибки и
конца файла, а также к его дескриптору.

\index{функция!fopen@\texttt{fopen}}%
Теперь можно написать функцию \verb|fopen|. Б\'{o}льшая часть инструкций
\verb|fopen| относится к открытию файла, соответствующему его позиционированию и
установке флажковых битов, предназначенных для индикации текущего состояния.
Сама \verb|fopen| не отводит места для буфера; это делает \verb|_fillbuf| при
первом чтении файла.

\begin{LongCodePar}
#include <fcntl.h>
#include "syscalls.h"
#define PERMS 0666  /* RW для собственника, группы и ост-х */
/* fopen: открывает файл, возвращает файловый указатель */
FILE *fopen(char *name, char *mode)
{
    int fd;
    FILE *fp;
    if (*mode != 'r' && *mode != 'w' && *mode != 'a')
        return NULL;
    for (fp = _iob; fp < _iob + OPEN_MAX; fp++)
        if ((fp->flag & (_READ | _WRITE)) == 0)
            break;     /* найдено своб.место для описателя */
    if (fp >= _iob + OPEN_MAX)  /* нет места для описателя */
        return NULL;
    if (*mode == 'w')
        fd = creat(name, PERMS);
    else if (*mode == 'a') {
        if ((fd = open(name, O_RDONLY, 0)) == -1)
            fd = creat(name, PERMS);
        lseek(fd, 0L, 2);
    } else
        fd = open(name, O_RDONLY, 0);
    if (fd == -1)   /* не возможен доступ по имени name */
        return NULL;
    fp->fd = fd;
    fp->cnt = 0;
    fp->base = NULL;
    fp->flag = (*mode == 'r') ? _READ : _WRITE;
    return fp;
}
\end{LongCodePar}

\noindent%
\index{файл!режим доступа}%
Приведённая версия \verb|fopen| не реализует все режимы доступа, оговорённые
стандартом; но, мы думаем, их реализация в полном объёме не намного увеличит
длину программы. Наша \verb|fopen| не распознает буквы <<\verb|b|>>,
сигнализирующей о бинарном вводе-выводе (поскольку в системах UNIX это не имеет
смысла), и знака <<\verb|+|>>, указывающего на возможность одновременно читать и
писать.

Для любого файла в момент первого обращения к нему с помощью макровызова
\verb|getc| счётчик \verb|cnt| равен нулю. Следствием этого будет вызов
\verb|_fillbuf|. Если выяснится, что файл на чтение не открыт, то функция
\verb|_fillbuf| немедленно возвратит \verb|EOF|. В противном случае она
попытается запросить память для буфера (если чтение должно быть с буферизацией).

После получения области памяти для буфера \verb|_fillbuf| обращается к
\verb|read|, чтобы его наполнить, устанавливает счётчик и указатели и возвращает
первую литеру буфера. В следующих обращениях \verb|_fillbuf| обнаружит, что
память для буфера уже выделена.

\begin{LongCodePar}
#include "syscalls.h"
/* _fillbuf: запрос памяти и заполнение буфера */
int _fillbuf(FILE *fp)
{
    int bufsize;
    if ((fp->flag&(_READ|_EOF|_ERR)) != _READ)
        return EOF;
    bufsize = (fp->flag & _UNBUF) ? 1 : BUFSIZ;
    if (fp->base == NULL)   /* буфера ещё нет */
        if ((fp->base = (char *) malloc(bufsize)) == NULL)
            return EOF;     /* нельзя получить буфер */
    fp->ptr = fp->base;
    fp->cnt = read(fp->fd, fp->ptr, bufsize);
    if (--fp->cnt < 0) {
        if (fp->cnt == -1)
            fp->flag |= _EOF;
        else
            fp->flag |= _ERR;
        fp->cnt = 0;
        return EOF;
    }
    return (unsigned char) *fp->ptr++;
}
\end{LongCodePar}

Единственное, что осталось невыясненным, -- это каким образом организовать
начало счёта. Следует так определить и инициализировать массив \verb|_iob|,
чтобы в нём, перед тем как программа начнёт работать, уже была информация о
файлах \verb|stdin|, \verb|stdout| и \verb|stderr|.

\begin{ShortCodePar}
FILE _iob[OPEN_MAX] = {     /* stdin, stdout, stderr: */
    { 0, (char *) 0, (char *) 0, _READ, 0 },
    { 0, (char *) 0, (char *) 0, _WRITE, 1 },
    { 0, (char *) 0, (char *) 0, _WRITE | _UNBUF, 2 }
};
\end{ShortCodePar}

Инициализация \verb|flag| как части структуры показывает‚ что \verb|stdin|
открыт на чтение, \verb|stdout| -- на запись, а \verb|stderr| -- на запись без
буферизации.

\paragraph{Упражнение 8.2.} Перепишите функции \verb|fopen| и
\verb|_fillbuf|, работая с флажками как с полями, а не при помощи явных
побитовых операций. Сравните размеры и скорости двух вариантов программ.

\paragraph{Упражнение 8.3.} Разработайте и напишите функции \verb|_flushbuf|,
\verb|fflush| и \verb|fclose|.

\paragraph{Упражнение 8.4.} Функция стандартной библиотеки

\begin{ShortCodePar}
int fseek(FILE *fp, long offset, int origin)
\end{ShortCodePar}

\noindent идентична функции \verb|lseek| с теми, однако, отличиями, что
\verb|fp| -- это файловый указатель, а не дескриптор, и возвращает она значение
\verb|int|, указывающее на состояние файла, а не позицию в нём. Напишите свою
версию \verb|fseek|. Обеспечьте, чтобы работа вашей \verb|fseek| по буферизации
была согласована с буферизацией, используемой другими функциями библиотеки.

\section{Пример. Печать каталогов}
\label{chapter:unix_system_interface:sec:directory_print}

\index{программа!печати!каталога}%
\index{ls@\texttt{ls}}%
При разного рода взаимодействиях с файловой системой иногда требуется получить
\emph{только} информацию о файле, а не его содержимое. Такая потребность
возникает, например, в программе печати каталога файлов, работающей по типу
команды \verb|ls| системы UNIX. Она печатает имена файлов каталога и по желанию
пользователя другую дополнительную информацию (размеры, права доступа и т.д.).
Аналогичной командой в MS-DOS является \verb|dir|.

Так как в системе UNIX каталог -- это тоже файл, функции \verb|ls|, чтобы
добраться до имён файлов, нужно только его прочитать. Но, чтобы получить другую
информацию о файле (например, узнать его размер), необходимо выполнить системный
вызов. В других системах (в MS-DOS, например) системным вызовом приходится
пользоваться даже для получения доступа к именам файлов. Наша цель -- обеспечить
доступ к информации по возможности системно-независимым способом несмотря на то,
что реализация может быть существенно системно-зависима.

\index{программа!fsize@\texttt{fsize}}%
Проиллюстрируем сказанное написанием программы \verb|fsize|. Функция
\verb|fsize| -- частный случай программы \verb|ls|; она печатает размеры всех
файлов, перечисленных в командной строке. Если какой-либо из файлов сам является
каталогом, то, чтобы получить информацию о нём, \verb|fsize| обращается сама к
себе. Если аргументов в командной строке нет, то обрабатывается текущий каталог.

\index{inode}%
\index{UNIX, файловая система}%
Для начала вспомним структуру файловой системы в UNIXе. \emph{Каталог} -- это
файл, содержащий список имён файлов и некоторую информацию о том, где они
расположены. <<Место расположения>> -- это индекс, обеспечивающий доступ в
другую таблицу, называемую <<списком узлов inode>>. Для каждого файла имеется
свой \emph{inode}, где собрана вся информация о файле, за исключением его имени.
Каждый элемент каталога состоит из двух частей: из имени файла и номера
inode.

К сожалению, формат и точное содержимое каталога не одинаковы во всех версиях
системы. Поэтому, чтобы переносимую компоненту отделить от непереносимой,
разобьём нашу задачу на две. Внешний уровень определяет структуру, названную
\verb|Dirent|, и три подпрограммы -- \verb|opendir|, \verb|readdir| и
\verb|closedir|; в результате обеспечивается системно-независимый доступ к имени
и номеру узла inode каждого элемента каталога. Мы будем писать программу
\verb|fsize|, рассчитывая на такой интерфейс, а затем покажем, как реализовать
указанные функции для систем, использующих ту же структуру каталога, что и
системы Version 7 и System V UNIX. Другие варианты оставим для упражнений.


\index{Dirent-структура@\texttt{Dirent}-структура}%
Структура \verb|Dirent| содержит номер inode и имя. Максимальная длина имени
файла есть \verb|NAME_MAX| -- значение, являющееся системно-зависимым.
\index{DIR-структура@\texttt{DIR}-структура}%
Функция \verb|opendir| возвращает указатель на структуру, названную \verb|DIR|
(по аналогии с \verb|FILE|), которая используется функциями \verb|readdir| и
\verb|closedir|. Эта информация сосредоточена в головном файле \verb|dirent.h|.

\begin{LongCodePar}
#define NAME_MAX  14   /* максимальная длина имени файла; */
                       /* системно-зависимая величина     */
typedef struct { /* универс. структура элемента каталога: */
    long ino;               /* номер inode */
    char name[NAME_MAX+1];  /* имя + '\0' */
} Dirent;
typedef struct { /* минимальный DIR: без буфер-ции и т.д. */
    int fd;         /* файловый дескриптор каталога */
    Dirent d;       /* элемент каталога */
} DIR;
DIR *opendir(char *dirname);
Dirent *readdir(DIR *dfd);
void closedir(DIR *dfd);
\end{LongCodePar}

\index{системный вызов!stat@\texttt{stat}}%
Системный вызов \verb|stat| получает имя файла и возвращает полную о нём
информацию, содержащуюся в inode, или $-1$, в случае ошибки. Так,

\begin{ShortCodePar}
char *name;
struct stat stbuf;
int stat(char *, struct stat *);
stat(name, &stbuf);
\end{ShortCodePar}

\noindent заполняет структуру \verb|stbuf| информацией из inode о файле с именем
\verb|name|.
\index{файл!включаемый!stat.h@\texttt{stat.h}|(}%
\index{stat-структура@\texttt{stat}-структура}%
Структура, описывающая возвращаемое функцией \verb|stat| значение, находится в
\verb|<sys/stat.h>| и выглядит примерно так:

\begin{LongCodePar}
struct stat {  /* информация из inode, возвращаемая stat */
    dev_t   st_dev;    /* устройство */
    ino_t   st_ino;    /* номер inode */
    short   st_mode;   /* режимные биты */
    short   st_nlink;  /* число связей с файлом */
    short   st_uid;    /* имя пользователя-собственника */
    short   st_gid;    /* имя группы собственника */
    dev_t   st_rdev;   /* для специальных файлов */
    off_t   st_size;   /* размер файла в литерах */
    time_t  st_atime;  /* время последнего использования */
    time_t  st_mtime;  /* время последней модификации */
    time_t  st_ctime;  /* время последнего изменения inode */
};
\end{LongCodePar}

\noindent%
\index{файл!включаемый!types.h@\texttt{types.h}}%
Большинство этих значений объясняется в комментариях. Типы, подобные
\verb|dev_t| и \verb|ino_t|, определены в файле \verb|<sys/types.h>|.

Элемент \verb|st_mode| содержит набор флажков, составляющих дополнительную
информацию о файле. Определения флажков также содержатся в \verb|<sys/stat.h>|;
нам потребуется только та его часть, которая имеет дело с типом файла:

\begin{ShortCodePar}
#define S_IFMT    0160000        /* тип файла */
#define S_IFDIR   0040000        /* каталог */
#define S_IFCHR   0020000        /* символьно-ориентир. */
#define S_IFBLK   0060000        /* блочно-ориентир. */
#define S_IFREG   0100000        /* обычный */
\end{ShortCodePar}

Теперь мы готовы приступить к написанию программы \verb|fsize|. Если режимные
биты (\verb|st_mode|)‚ полученные от \verb|stat|, указывают, что файл не
является каталогом, то можно взять его размер (\verb|st_size|) и напечатать.
Однако если файл -- каталог, то мы должны обработать все его файлы, каждый из
которых в свою очередь может быть каталогом.
\index{рекурсия}%
Обработка каталога -- процесс рекурсивный.

Программа \verb|main| просматривает параметры командной строки, передавая каждый
аргумент функции \verb|fsize|.

\begin{LongCodePar}
#include <stdio.h>
#include <string.h>
#include "syscalls.h"
#include <fcntl.h>         /* флажки чтения и записи */
#include <sys/types.h>     /* определения типов */
#include <sys/stat.h>      /* структура, возвращаемая stat */
#include "dirent.h"
void fsize(char *);

/* печатает размеры файлов */
main(int argc, char **argv)
{
    if (argc == 1) /* по умолчанию берётся текущий каталог */
        fsize(".");
    else
        while (--argc > 0)
            fsize(*++argv);
    return 0;
}
\end{LongCodePar}

\index{функция!fsize@\texttt{fsize}}%
Функция \verb|fsize| печатает размер файла.
\index{функция!dirwalk@\texttt{dirwalk}}%
Однако, если файл -- каталог, она сначала вызывает \verb|dirwalk|, чтобы
обработать все его файлы. Обратите внимание на то, как используются имена
флажков \verb|S_IFMT| и \verb|S_IFDIR| из \verb|<sys/stat.h>| при проверке,
является ли файл каталогом. Здесь нужны скобки, поскольку приоритет оператора
\verb|&| ниже приоритета оператора \verb|==|.

\begin{LongCodePar}
int stat(char *, struct stat *);
void dirwalk(char *, void (*fcn)(char *));

/* fsize: печатает размер файла с именем "name" */
void fsize(char *name)
{
    struct stat stbuf;
    if (stat(name, &stbuf) == -1) {
        fprintf(stderr, "fsize: нет доступа к %s\n", name);
        return;
    }
    if ((stbuf.st_mode & S_IFMT) == S_IFDIR)
        dirwalk(name, fsize);
    printf("%8ld %s\n", stbuf.st_size, name);
}
\end{LongCodePar}
\index{файл!включаемый!stat.h@\texttt{stat.h}|)}%
%
% исправлена опечатка
% в оригинале не хватает закрывающей кавычки в
% "printf("%8ld %s\n, stbuf.st_size, name);"
%

Функция \verb|dirwalk| -- это универсальная программа, применяющая некоторую
функцию к каждому файлу каталога. Она открывает каталог, с помощью цикла
перебирает содержащиеся в нём файлы, применяя к каждому из них указанную
функцию, затем закрывает каталог и осуществляет возврат.
\index{рекурсия}%
Так как \verb|fsize| вызывает \verb|dirwalk| на каждом каталоге, в этих двух
функциях заложена косвенная рекурсия.

\begin{LongCodePar}
#define MAX_PATH 1024

/* dirwalk: применяет fcn ко всем файлам из dir */
void dirwalk(char *dir, void (*fcn)(char *))
{
    char name[MAX_PATH];
    Dirent *dp;
    DIR *dfd;
    if ((dfd = opendir(dir)) == NULL) {
        fprintf(stderr, "dirwalk: не могу откр.%s\n", dir);
        return;
    }
    while ((dp = readdir(dfd)) != NULL) {
        if (strcmp(dp->name, ".") == 0
         || strcmp(dp->name, "..") == 0)
            continue;  /* пропустить себя и родителя */
        if (strlen(dir)+strlen(dp->name)+2 > sizeof(name))
            fprintf(stderr,"dirwalk: слишк.длин.имя %s/%s\n",
                dir, dp->name);
        else {
            sprintf(name, "%s/%s", dir, dp->name);
            (*fcn)(name);
        }
    }
    closedir(dfd);
}
\end{LongCodePar}

\noindent Каждый вызов \verb|readdir| даёт в результате указатель на информацию
о следующем файле или \verb|NULL|, если все файлы обработаны. Любой каталог
всегда хранит в себе информацию о себе самом под именем <<\verb|.|>> и о своём
родителе под именем <<\verb|..|>>; их нужно пропустить, иначе программа
зациклится. Обратите внимание: код программы этого уровня не зависит от того,
как форматированы каталоги. Следующий шаг -- представить минимальные версии
\verb|opendir|, \verb|readdir| и \verb|closedir| для некоторой конкретной
системы. Здесь приведены программы для систем Version 7 и System V UNIX.
\index{файл!включаемый!dir.h@\texttt{dir.h}}%
Они используют информацию о каталоге, хранящуюся в головном файле
\verb|<sys/dir.h>|, который выглядит следующим образом:

\begin{LongCodePar}
#ifndef DIRSIZ
#define DIRSIZ  14
#endif

struct direct   /* элемент каталога */
{
    ino_t d_ino;            /* номер inode */
    char d_name[DIRSIZ];    /* длинное имя не имеет '\0' */
};
\end{LongCodePar}

\noindent Некоторые версии системы допускают более длинные имена и имеют более
сложную структуру каталога.

Тип \verb|ino_t| задан при помощи \verb|typedef| и описывает индекс списка
inode. В системе, которой пользуемся мы, этот тип есть \verb|unsigned short|, но
на других системах он может быть иным, поэтому его лучше определять через
\verb|typedef|.
\index{файл!включаемый!types.h@\texttt{types.h}}%
Полный набор <<системных>> типов находится в \verb|<sys/types.h>|.

\index{функция!opendir@\texttt{opendir}}%
Функция \verb|opendir| открывает каталог, проверяет, является ли он
действительно каталогом
\index{системный вызов!fstat@\texttt{fstat}}%
(в данном случае это делается при помощи системного вызова \verb|fstat|, который
аналогичен \verb|stat|, но применяется к дескриптору файла), запрашивает
пространство для структуры каталога и записывает информацию.

\begin{LongCodePar}
int fstat(int fd, struct stat *);

/* opendir: открывает каталог для вызовов readdir */
DIR *opendir(char *dirname)
{
    int fd;
    struct stat stbuf;
    DIR *dp;
    if ((fd = open(dirname, O_RDONLY, 0)) == -1
     || fstat(fd, &stbuf) == -1
     || (stbuf.st_mode & S_IFMT) != S_IFDIR
     || (dp = (DIR *) malloc(sizeof(DIR))) == NULL)
        return NULL;
    dp->fd = fd;
    return dp;
}
\end{LongCodePar}

\index{функция!closedir@\texttt{closedir}}%
Функция \verb|closedir| закрывает каталог и освобождает пространство.

\begin{LongCodePar}
/* closedir: закрывает каталог, открытый opendir */
void closedir(DIR *dp)
{
    if (dp) {
        close(dp->fd);
        free(dp);
    }
}
\end{LongCodePar}

\index{функция!readdir@\texttt{readdir}}%
Наконец, \verb|readdir| с помощью \verb|read| читает каждый элемент каталога.
Если некий элемент каталога в данный момент не используется (соответствующий ему
файл был удалён), то номер inode у него равен нулю, и данная позиция
пропускается. В противном случае номер inode и имя размещаются в
\verb|static|-структуре, и указатель на неё выдаётся в качестве результата. При
каждом следующем обращении новая информация занимает место предыдущей.

\begin{LongCodePar}
#include <sys/dir.h>  /* место располож.структуры каталога */

/*readdir: читает последовательно элементы каталога */
Dirent *readdir(DIR *dp)
{
    struct direct dirbuf; /* структура каталога на
                                           данной системе */
    static Dirent d;      /* возвращает унифицированную
                                                структуру */
    while (read(dp->fd, (char *) &dirbuf, sizeof(dirbuf))
                    == sizeof(dirbuf)) {
        if (dirbuf.d_ino == 0)   /* пустой эл-т не использ.*/
            continue;
        d.ino = dirbuf.d_ino;
        strncpy(d.name, dirbuf.d_name, DIRSIZ);
        d.name[DIRSIZ] = '\0';  /* завершающая литера '\0' */
        return &d;
    }
    return NULL;
}
\end{LongCodePar}

Хотя программа \verb|fsize| -- довольно специализированная, она иллюстрирует два
важных факта. Первый, многие программы не являются <<системными>>; они просто
используют информацию, которую поддерживает операционная система. Для таких
программ существенно то, что представление информации сосредоточено
исключительно в стандартных головных файлах. Они включают эти файлы, а не держат
декларации при себе.
\index{переносимость}%
Второе наблюдение заключается в том, что при старании системно-зависимым
объектам можно создать интерфейсы, которые сами не будут системно-зависимыми.
Хорошие тому примеры -- функции стандартной библиотеки.

\paragraph{Упражнение 8.5.} Модифицируйте \verb|fsize| таким образом, чтобы
можно было печатать остальную информацию, содержащуюся в inode.

\section{Пример. Распределитель памяти}
\label{sec:memory_allocator}

\index{память!распределитель|(}%
\index{распределитель памяти|(}%
\index{функция!malloc@\texttt{malloc}}%
В гл.~\ref{chapt:pointers_and_arrays} был описан простой распределитель памяти,
основанный на принципе стека. Версия, которую мы напишем здесь, не имеет
ограничений: вызовы \verb|malloc| и \verb|free| могут выполняться в любом
порядке; \verb|malloc| делает запрос в операционную систему на выделение памяти
тогда, когда она требуется.
\index{переносимость}%
Эти программы иллюстрируют приёмы, позволяющие получать машинно-зависимый код
сравнительно машинно-независимым способом, и, кроме того, они могут служить
реальным примером применения таких средств языка, как структуры, объединения и
\verb|typedef|.

Никакого ранее скомпилированного массива фиксированного размера, из которого
выделяются куски памяти, не будет. Функция \verb|malloc| запрашивает память у
операционной системы по мере надобности. Поскольку и другие действия программы
могут вызывать запросы памяти, которые удовлетворяются независимо от этого
распределителя памяти, пространство, которым заведует \verb|malloc|, не
обязательно представляет собой связный кусок памяти. Поэтому свободная память
хранится в виде списка блоков. Каждый блок содержит размер, указатель на
следующий блок и само пространство. Блоки в списке хранятся в порядке
возрастания адресов памяти, при этом последний блок (с самым большим адресом)
ссылается на первый.

\begin{figure}[H]
\center{\includegraphics[width=0.8681319\linewidth]{chapt8_sec7_img0.eps}}
\end{figure}

При возникновении запроса на память просматривается список свободных блоков,
пока не обнаружится достаточно большой блок. Такой алгоритм называется <<поиском
первого подходящего>> в отличие от алгоритма <<поиска наилучшего подходящего>>,
который ищет наименьший блок из числа удовлетворяющих запросу. Если блок
оказался в точности требуемого размера, то он отцепляется от списка и отдаётся в
пользование. Если размер блока больше, чем требуется, от него отрезается нужная
часть -- она отдаётся пользователю, а ненужная оставляется в списке свободных
блоков. Если блока достаточного размера не оказалось, то у операционной системы
запрашивается ещё один большой кусок памяти, который присоединяется к списку
свободных блоков.

Процедура освобождения сопряжена с хождением по списку свободных блоков,
поскольку нужно найти подходящее место для освобождаемого блока. Если подлежащий
освобождению блок примыкает с какой-то стороны к одному из свободных блоков, то
он объединяется с ним в один блок б\'{o}льшего размера, чтобы по возможности
уменьшить раздробленность памяти. Выполнение проверки, примыкают ли блоки друг к
другу, не составляет труда, поскольку список свободных блоков всегда упорядочен
по возрастанию адресов.

Существует проблема, о которой мы уже упоминали в
гл.~\ref{chapt:pointers_and_arrays}, состоящая в том, что
\index{выравнивание!ограничения по}%
память, выдаваемая функцией \verb|malloc|‚ должна быть соответствующим образом
выровнена с учётом объектов, которые в ней будут храниться. Хотя машины и
отличаются друг от друга, но для каждой из них существует тип, предъявляющий
самые большие требования на выравнивание, и, если по некоему адресу допускается
размещение объекта этого типа, то по нему можно разместить и объекты всех других
типов. На некоторых машинах таким самым <<требовательным>> типом является
\verb|double|, на других -- это может быть \verb|int| или \verb|long|.

Свободный блок содержит указатель на следующий блок в списке, свой размер и
собственно свободное пространство.

\begin{figure}[H]
\center{\includegraphics[width=0.7569061\linewidth]{chapt8_sec7_img1.eps}}
\end{figure}

\noindent Указатель и размер представляют собой управляющую информацию и
образуют так называемый <<заголовок>>.
\index{выравнивание!при помощи \texttt{union}}%
\index{union@\texttt{union}!выравнивание при помощи}%
Чтобы упростить выравнивание, все блоки создаются кратными размеру заголовка, а
заголовок соответствующим образом выравнивается. Этого можно достичь,
сконструировав объединение, которое будет содержать соответствующую заголовку
структуру и самый требовательный в отношении выравнивания тип. Для конкретности
мы выбрали тип \verb|long|.

\begin{LongCodePar}
typedef long Align;    /* для выравнивания по границе long */

union header {         /* заголовок блока: */
    struct {
        union header *ptr;  /* на след.блок в списке своб. */
        unsigned size;      /* размер этого блока */
    } s;
    Align x;           /* для принудит. выравнивания блока */
};
typedef union header Header;
\end{LongCodePar}

\noindent Поле \verb|Align| нигде не используется; оно необходимо только для
того, чтобы каждый заголовок был выровнен по самому <<худшему>> варианту
границы.

Затребованное число литер округляется в \verb|malloc| до целого числа единиц
памяти размером в заголовок (именно это число и записывается в поле \verb|size|
(размер) в заголовке); кроме того, в блок входит ещё одна единица памяти -- сам
заголовок. Указатель, возвращаемый функцией \verb|malloc|, указывает на
свободное пространство, а не на заголовок. Со свободным пространством
пользователь может делать что угодно, но, если он будет писать что-либо за его
пределами, то, вероятно, список будет разрушен. Поскольку память, управляемая
функцией \verb|malloc|, не обладает связностью, размеры блоков нельзя вычислить
по указателям, и поэтому без поля, хранящего размер, нам не обойтись.

Для организации начала работы используется переменная \verb|base|. Если
\verb|freep| есть \verb|NULL| (как это бывает при первом обращении к
\verb|malloc|), создаётся <<вырожденный>> список свободного пространства; он
содержит один блок нулевого размера с указателем на самого себя. Поиск
свободного блока подходящего размера начинается с этого указателя
(\verb|freep|), т.е. с последнего найденного блока; такая стратегия помогает
поддерживать список однородным. Если найденный блок окажется слишком большим,
пользователю будет отдана его хвостовая часть; при этом потребуется только в
заголовке найденного свободного блока уточнить его размер. В любом случае
возвращаемый пользователю указатель является адресом свободного пространства,
размещающегося в блоке непосредственно за заголовком.

\begin{LongCodePar}
static Header base;    /* пустой список для нач. запуска */
static Header *freep = NULL;     /* начало в спис.своб.бл. */

/* malloc: универсальный распределитель памяти */
void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;
    
    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
    if ((prevp = freep) == NULL) { /* спис.своб.пам.ещё нет*/
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) { /* достаточно большой */
            if (p->s.size == nunits) /* точно такого разм. */
                prevp->s.ptr = p->s.ptr;
            else {             /* отрезаем хвостовую часть */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p+1);
        }
        if (p == freep)   /* прошли полный цикл по списку*/
            if ((p = morecore(nunits)) == NULL)
                return NULL;     /* нет больше памяти */
    }
}
\end{LongCodePar}

\index{функция!morecore@\texttt{morecore}}%
Функция \verb|morecore| получает память от операционной системы. Детали того,
как это делается, могут не совпадать в различных системах.
\index{эффективность}%
Так как запрос памяти у системы -- сравнительно дорогая операция, мы бы не
хотели для этого каждый раз обращаться к \verb|malloc|. Поэтому используется
функция \verb|morecore|, которая запрашивает не менее \verb|NALLOC| единиц
памяти; этот б\'{o}льший кусок памяти будет <<нарезаться>> потом по мере
надобности. После установки в поле размера соответствующего значения функция
\verb|morecore| вызывает функцию \verb|free| и тем самым включает полученный
кусок в список свободных областей памяти.

\begin{LongCodePar}
#define NALLOC  1024   /* миним.число ед.памяти для запроса*/

/* morecore: запрашивает у системы дополнительную память */
static Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;
    
    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)  /* нет больше памяти */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    free((void *)(up+1));
    return freep;
}
\end{LongCodePar}

\index{системный вызов!sbrk@\texttt{sbrk}}%
Системный вызов \verb|sbrk(n)| в UNIXе возвращает указатель на \verb|n| байт
памяти или $-1$, если требуемого пространства не оказалось, хотя было бы лучше,
если бы в последнем случае он возвращал \verb|NULL|.
\index{сравнение указателей}%
\index{указатели!сравнение}%
Константу $-1$ необходимо привести к типу \verb|char *|, чтобы её можно было
сравнить с возвращаемым значением. Это ещё один пример того, что операция
приведения типа делает функцию относительно независимой от конкретного
представления указателей на различных машинах. Есть, однако, одна
<<некорректность>>, состоящая в том, что сравниваются указатели на различные
блоки, выдаваемые функцией \verb|sbrk|. Такое сравнение не гарантировано
стандартом, который позволяет сравнивать указатели лишь в пределах массива.
Таким образом, эта версия \verb|malloc| верна только на тех машинах, в которых
допускается сравнение любых указателей.

\index{функция!free@\texttt{free}}%
В заключение рассмотрим функцию \verb|free|. Она просматривает список свободной
памяти, начиная с \verb|freep|, чтобы подыскать место для вставляемого блока.
Искомое место может оказаться или между блоками, или в начале списка, или в его
конце. В любом случае, если подлежащий освобождению блок примыкает к соседнему
блоку, он объединяется с ним в один блок. О чём ещё осталось позаботиться, --
так это о том, чтобы ссылки указывали в нужные места и размеры блоков были
правильными.

\begin{LongCodePar}
/* free: включает блок в список свободной памяти */
void free(void *ap)
{
    Header *bp, *p;
    
    bp = (Header *)ap - 1;  /* указ. на заголовок блока */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break; /* освобожд.блок в начале или в конце */
    if (bp + bp->s.size == p->s.ptr) {  /* слить с верхним */
        bp->s.size += p->s.ptr->s.size; /*         соседом */
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;
    if (p + p->s.size == bp) {   /* слить с нижним соседом */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}
\end{LongCodePar}

Хотя распределение памяти по своей сути -- машинно-зависимая проблема, с ней
можно справиться, что и иллюстрирует приведённая программа, в которой машинная
зависимость упрятана в очень маленькой её части. Что касается проблемы
выравнивания, то мы разрешили её при помощи \verb|typedef| и \verb|union|
(предполагается, что \verb|sbrk| даёт нормальный в смысле выравнивания
указатель). Операции приведения типов позволяют нам сделать явными
преобразования типов и даже справиться с плохо спроектированным интерфейсом
системы. Несмотря на то что наши рассуждения касались распределения памяти, этот
общий подход применим и в других ситуациях.
\index{распределитель памяти|)}%
\index{память!распределитель|)}%


\paragraph{Упражнение 8.6.} Стандартная функция \verb|calloc(n, size)|
возвращает указатель на \verb|n| элементов памяти размера \verb|size|,
заполненных нулями. Напишите свой вариант \verb|calloc|, пользуясь функцией
\verb|malloc| или модифицируя последнюю.

\paragraph{Упражнение 8.7.} Функция \verb|malloc| допускает любой размер, никак
не проверяя его на правдоподобие; \verb|free| предполагает, что размер
освобождаемого блока -- правильный. Усовершенствуйте эти программы таким
образом, чтобы они более тщательно контролировали ошибки.

\paragraph{Упражнение 8.8.} Напишите программу \verb|bfree(p,n)|‚ освобождающую
произвольный блок \verb|p|, состоящий из \verb|n| литер, путём включения его в
список свободной памяти, поддерживаемый функциями \verb|malloc| и \verb|free|.
При помощи \verb|bfree| пользователь должен иметь возможность в любое время
добавить статический или внешний массив в список свободной памяти.