возвращает дескриптор файла, если оказалось возможным соз-
дать файл с именем NAME, и "-1" в противном случае. Если
файл с таким именем уже существует, CREAT усечет его до ну-
левой длины; создание файла, который уже существует, не яв-
ляется ошибкой.
Если файл является совершенно новым, то CREAT создает
его с определенным режимом защиты, специфицируемым аргумен-
том PMODE. В системе файлов на UNIX с файлом связываются де-
вять битов защиты информации, которые управляют разрешением
на чтение, запись и выполнение для владельца файла, для
группы владельцев и для всех остальных пользователей. Таким
образом, трехзначное восьмеричное число наиболее удобно для
спецификации разрешений. Например, число 0755 свидетельству-
ет о разрешении на чтение, запись и выполнение для владельца
и о разрешении на чтение и выполнение для группы и всех ос-
тальных.
Для иллюстрации ниже приводится программа копирования
одного файла в другой, являющаяся упрощенным вариантом ути-
литы CP системы UNIX. (Основное упрощение заключается в том,
что наш вариант копирует только один файл и что второй аргу-
мент не должен быть справочником).
#DEFINE NULL 0
#DEFINE BUFSIZE 512
#DEFINE PMODE 0644/*RW FOR OWNER,R FOR GROUP,OTHERS*/
MAIN(ARGC,ARGV) /*CP: COPY F1 TO F2*/
INT ARGC;
CHAR *ARGV[];
\(
INT F1, F2, N;
CHAR BUF[BUFSIZE];
IF (ARGC ! = 3)
ERROR("USAGE:CP FROM TO", NULL);
IF ((F1=OPEN(ARGV[1],0))== -1)
ERROR("CP:CAN'T OPEN %S", ARGV[1]);
IF ((F2=CREAT(ARGV[2],PMODE))== -1)
ERROR("CP: CAN'T CREATE %S", ARGV[2]);
WHILE ((N=READ(F1,BUF,BUFSIZE))>0)
IF (WRITE(F2,BUF,N) !=N)
ERROR("CP: WRITE ERROR", NULL);
EXIT(0);
\)
ERROR(S1,S2) /*PRINT ERROR MESSAGE AND DIE*/
CHAR *S1, S2;
\(
PRINTF(S1,S2);
PRINTF("\N");
EXIT(1);
\)
Существует ограничение (обычно 15 - 25) на количество
файлов, которые программа может иметь открытыми одновремен-
но. В соответствии с этим любая программа, собирающаяся ра-
ботать со многими файлами, должна быть подготовлена к пов-
торному использованию дескрипторов файлов. Процедура CLOSE
прерывает связь между дескриптором файла и открытым файлом и
освобождает дескриптор файла для использования с некоторым
другим файлом. Завершение выполнения программы через EXIT
или в результате возврата из ведущей программы приводит к
закрытию всех открытых файлов.
Функция расцепления UNLINK (FILENAME) удаляет из системы
файлов файл с именем FILENAME ( из данного справочного фай-
ла. Файл может быть сцеплен с другим справочником, возможно,
под другим именем - примеч.переводчика).
Упражнение 8-1
--------------
Перепишите программу CAT из главы 7, используя функции
READ, WRITE, OPEN и CLOSE вместо их эквивалентов из стандар-
тной библиотеки. Проведите эксперименты для определения от-
носительной скорости работы этих двух вариантов.
Нормально при работе с файлами ввод и вывод осуществля-
ется последовательно: при каждом обращении к функциям READ и
WRITE чтение или запись начинаются с позиции, непосредствен-
но следующей за предыдущей обработанной. Но при необходимос-
ти файл может читаться или записываться в любом произвольном
порядке. Обращение к системе с помощью функции LSEEK позво-
ляет передвигаться по файлу, не производя фактического чте-
ния или записи. В результате обращения
LSEEK(FD,OFFSET,ORIGIN);
текущая позиция в файле с дескриптором FD передвигается на
позицию OFFSET (смещение), которая отсчитывается от места,
указываемого аргументом ORIGIN (начало отсчета). Последующее
чтение или запись будут теперь начинаться с этой позиции.
Аргумент OFFSET имеет тип LONG; FD и ORIGIN имеют тип INT.
Аргумент ORIGIN может принимать значения 0,1 или 2, указывая
на то, что величина OFFSET должна отсчитываться соответст-
венно от начала файла, от текущей позиции или от конца фай-
ла. Например, чтобы дополнить файл, следует перед записью
найти его конец:
LSEEK(FD,0L,2);
чтобы вернуться к началу ("перемотать обратно"), можно напи-
сать:
LSEEK(FD,0L,0);
обратите внимание на аргумент 0L; его можно было бы записать
и в виде (LONG) 0.
Функция LSEEK позволяет обращаться с файлами примерно
так же, как с большими массивами, правда ценой более медлен-
ного доступа. следующая простая функция, например, считывает
любое количество байтов, начиная с произвольного места в
файле.
GET(FD,POS,BUF,N) /*READ N BYTES FROM POSITION POS*/
INT FD, N;
LONG POS;
CHAR *BUF;
\(
LSEEK(FD,POS,0); /*GET TO POS*/
RETURN(READ(FD,BUF,N));
\)
В более ранних редакциях, чем редакция 7 системы UNIX,
основная точка входа в систему ввода-вывода называется SEEK.
Функция SEEK идентична функции LSEEK, за исключением того,
что аргумент OFFSET имеет тип INT, а не LONG. в соответствии
с этим, поскольку на PDP-11 целые имеют только 16 битов, ар-
гумент OFFSET, указываемый функции SEEK, ограничен величиной
65535; по этой причине аргумент ORIGIN может иметь значения
3, 4, 5, которые заставляют функцию SEEK умножить заданное
значение OFFSET на 512 (количество байтов в одном физическом
блоке) и затем интерпретировать ORIGIN, как если это 0, 1
или 2 соответственно. Следовательно, чтобы достичь произ-
вольного места в большом файле, нужно два обращения к SEEK:
сначала одно, которое выделяет нужный блок, а затем второе,
где ORIGIN имеет значение 1 и которое осуществляет передви-
жение на желаемый байт внутри блока.
Упражнение 8-2
---------------
Очевидно, что SEEK может быть написана в терминалах
LSEEK и наоборот. напишите каждую функцию через другую.
Давайте теперь на примере реализации функций FOPEN и
GETC из стандартной библиотеки подпрограмм продемонстрируем,
как некоторые из описанных элементов объединяются вместе.
Напомним, что в стандартной библиотеке файлы описыватся
посредством указателей файлов, а не дескрипторов. Указатель
файла является указателем на структуру, которая содержит
несколько элементов информации о файле: указатель буфера,
чтобы файл мог читаться большими порциями; счетчик числа
символов, оставшихся в буфере; указатель следующей позиции
символа в буфере; некоторые признаки, указывающие режим чте-
ния или записи и т.д.; дескриптор файла.
Описывающая файл структура данных содержится в файле
STDIO.H, который должен включаться (посредством #INCLUDE) в
любой исходный файл, в котором используются функции из стан-
дартной библиотеки. Он также включается функциями этой биб-
лиотеки. В приводимой ниже выдержке из файла STDIO.H имена,
предназначаемые только для использования функциями библиоте-
ки, начинаются с подчеркивания, с тем чтобы уменьшить веро-
ятность совпадения с именами в программе пользователя.
DEFINE _BUFSIZE 512
DEFINE _NFILE 20 /*FILES THAT CAN BE HANDLED*/
TYPEDEF STRUCT _IOBUF \(
CHAR *_PTR; /*NEXT CHARACTER POSITION*/
INT _CNT; /*NUMBER OF CHARACTERS LEFT*/
CHAR *_BASE; /*LOCATION OF BUFFER*/
INT _FLAG; /*MODE OF FILE ACCESS*/
INT _FD; /*FILE DESCRIPTOR*/
) FILE;
XTERN FILE _IOB[_NFILE];
DEFINE STDIN (&_IOB[0])
DEFINE STDOUT (&_IOB[1])
DEFINE STDERR (&_IOB[2])
DEFINE _READ 01 /* FILE OPEN FOR READING */
DEFINE _WRITE 02 /* FILE OPEN FOR WRITING */
DEFINE _UNBUF 04 /* FILE IS UNBUFFERED */
DEFINE _BIGBUF 010 /* BIG BUFFER ALLOCATED */
DEFINE _EOF 020 /* EOF HAS OCCURRED ON THIS FILE */
DEFINE _ERR 040 /* ERROR HAS OCCURRED ON THIS FILE */
DEFINE NULL 0
DEFINE EOF (-1)
DEFINE GETC(P) (--(P)->_CNT >= 0 \
? *(P)->_PTR++ & 0377 : _FILEBUF(P))
DEFINE GETCHAR() GETC(STDIN)
DEFINE PUTC(X,P) (--(P)->_CNT >= 0 \
? *(P)->_PTR++ = (X) : _FLUSHBUF((X),P))
DEFINE PUTCHAR(X) PUTC(X,STDOUT)
В нормальном состоянии макрос GETC просто уменьшает
счетчик, передвигает указатель и возвращает символ. (Если
определение #DEFINE слишком длинное, то оно продолжается с
помощью обратной косой черты). Если однако счетчик становит-
ся отрицательным, то GETC вызывает функцию _FILEBUF, которая
снова заполняет буфер, реинициализирует содержимое структуры
и возвращает символ. Функция может предоставлять переносимый
интерфейс и в то же время содержать непереносимые конструк-
ции: GETC маскирует символ числом 0377, которое подавляет
знаковое расширение, осуществляемое на PDP-11, и тем самым
гарантирует положительность всех символов.
Хотя мы не собираемся обсуждать какие-либо детали, мы
все же включили сюда определение макроса PUTC, для того что-
бы показать, что она работает в основном точно также, как и
GETC, обращаясь при заполнении буфера к функции _FLUSHBUF.
Теперь может быть написана функция FOPEN. Большая часть
программы функции FOPEN связана с открыванием файла и распо-
ложением его в нужном месте, а также с установлением битов
признаков таким образом, чтобы они указывали нужное состоя-
ние. Функция FOPEN не выделяет какой-либо буферной памяти;
это делается функцией _FILEBUF при первом чтении из файла.
#INCLUDE <STDIO.H>
#DEFINE PMODE 0644 /*R/W FOR OWNER;R FOR OTHERS*/
FILE *FOPEN(NAME,MODE) /*OPEN FILE,RETURN FILE PTR*/
REGISTER CHAR *NAME, *MODE;
\(
REGISTER INT FD;
REGISTER FILE *FP;
IF(*MODE !='R'&&*MODE !='W'&&*MODE !='A') \(
FPRINTF(STDERR,"ILLEGAL MODE %S OPENING %S\N",
MODE,NAME);
EXIT(1);
\)
FOR (FP=_IOB;FP<_IOB+_NFILE;FP++)
IF((FP->_FLAG & (_READ \! _WRITE))==0)
BREAK; /*FOUND FREE SLOT*/
IF(FP>=_IOB+_NFILE) /*NO FREE SLOTS*/
RETURN(NULL);
IF(*MODE=='W') /*ACCESS FILE*/
FD=CREAT(NAME,PMODE);
ELSE IF(*MODE=='A') \(
IF((FD=OPEN(NAME,1))==-1)
FD=CREAT(NAME,PMODE);
LSEEK(FD,OL,2);
\) ELSE
FD=OPEN(NAME,0);
IF(FD==-1) /*COULDN'T ACCESS NAME*/
RETURN(NULL);
FP->_FD=FD;
FP->_CNT=0;
FP->_BASE=NULL;
FP->_FLAG &=(_READ \! _WRITE);
FP->_FLAG \!=(*MODE=='R') ? _READ : _WRITE;
RETURN(FP);
\)
Функция _FILEBUF несколько более сложная. Основная труд-
ность заключается в том, что _FILEBUF стремится разрешить
доступ к файлу и в том случае, когда может не оказаться дос-
таточно места в памяти для буферизации ввода или вывода. ес-
ли пространство для нового буфера может быть получено обра-
щением к функции CALLOC, то все отлично; если же нет, то
_FILEBUF осуществляет небуферизованный ввод/ вывод, исполь-
зуя отдельный символ, помещенный в локальном массиве.
#INCLUDE <STDIO.H>
_FILLBUF(FP) /*ALLOCATE AND FILL INPUT BUFFER*/
REGISTER FILE *FP;
(
STATIC CHAR SMALLBUF(NFILE);/*FOR UNBUFFERED 1/0*/
CHAR *CALLOC();
IF((FR->_FLAG&_READ)==0\!\!(FP->_FLAG&(EOF\!_ERR))\!=0
RETURN(EOF);
WHILE(FP->_BASE==NULL) /*FIND BUFFER SPACE*/
IF(FP->_FLAG & _UNBUF) /*UNBUFFERED*/
FP->_BASE=&SMALLBUF[FP->_FD];
ELSE IF((FP->_BASE=CALLOC(_BUFSIZE,1))==NULL)
FP->_FLAG \!=_UNBUF; /*CAN'T GET BIG BUF*/
ELSE
FP->_FLAG \!=_BIGBUF; /*GOT BIG ONE*/
FP->_PTR=FP->_BASE;
FP->_CNT=READ(FP->_FD, FP->_PTR,
FP->_FLAG & _UNBUF ? 1 : _BUFSIZE);
FF(--FP->_CNT<0) \(
IF(FP->_CNT== -1)
FP->_FLAG \! = _EOF;
ELSE
FP->_FLAG \! = _ ERR;
FP->_CNT = 0;
RETURN(EOF);
\)
RETURN(*FP->_PTR++ & 0377); /*MAKE CHAR POSITIVE*/
)
При первом обращении к GETC для конкретного файла счетчик
оказывается равным нулю, что приводит к обращению к
_FILEBUF. Если функция _FILEBUF найдет, что этот файл не от-
крыт для чтения, она немедленно возвращает EOF. В противном
случае она пытается выделить большой буфер, а если ей это не
удается, то буфер из одного символа. При этом она заносит в
_FLAG соответствующую информацию о буферизации.
Раз буфер уже создан, функция _FILEBUF просто вызывает
функцию READ для его заполнения, устанавливает счетчик и
указатели и возвращает символ из начала буфера.
Единственный оставшийся невыясненным вопрос состоит в
том, как все начинается. Массив _IOB должен быть определен и
инициализирован для STDIN, STDOUT и STDERR:
FILE _IOB[NFILE] = \(
(NULL,0,_READ,0), /*STDIN*/
(NULL,0,NULL,1), /*STDOUT*/
(NULL,0,NULL,_WRITE \! _UNBUF,2) /*STDERR*/
);
Из инициализации части _FLAG этого массива структур видно,
что файл STDIN предназначен для чтения, файл STDOUT - для
записи и файл STDERR - для записи без использования буфера.
Упражнение 8-3
--------------
Перепишите функции FOPEN и _FILEBUF, используя поля
вместо явных побитовых операций.
Упражнение 8-4
---------------
Разработайте и напишите функции _FLUSHBUF и FCLOSE.
Упражнение 8-5
---------------
Стандартная библиотека содержит функцию
FSEEK(FP, OFFSET, ORIGIN)
которая идентична функции LSEEK, исключая то, что FP являет-
ся указателем файла, а не дескриптором файла. Напишите
FSEEK. Убедитесь, что ваша FSEEK правильно согласуется с бу-
феризацией, сделанной для других функций библиотеки.
Иногда требуется другой вид взаимодействия с системой
файлов - определение информации о файле, а не того, что в
нем содержится. Примером может служить команда LS ("список
справочника") системы UNIX. По этой команде распечатываются
имена файлов из справочника и, необязательно, другая инфор-
мация, такая как размеры, разрешения и т.д.
Поскольку, по крайней мере, на системе UNIX справочник
является просто файлом, то в такой команде, как LS нет ниче-
го особенного; она читает файл и выделяет нужные части из
находящейся там информации. Однако формат информации опреде-
ляется системой, так что LS должна знать, в каком виде все
представляется в системе.
Мы это частично проиллюстрируем при написании программы
FSIZE. Программа FSIZE представляет собой специальную форму
LS, которая печатает размеры всех файлов, указанных в списке
ее аргументов. Если один из файлов является справочником, то
для обработки этого справочника программа FSIZE обращается
сама к себе рекурсивно. если же аргументы вообще отсутству-
ют, то обрабатывается текущий справочник.
Для начала дадим краткий обзор структуры системы файлов.
Справочник - это файл, который содержит список имен файлов и
некоторое указание о том, где они размещаются. Фактически
это указание является индексом для другой таблицы, которую
называют "I - узловой таблицей". Для файла I-узел - это то,
где содержится вся информация о файле, за исключением его
имени. Запись в справочнике состоит только из двух элемен-
тов: номера I-узла и имени файла. Точная спецификация посту-
пает при включении файла SYS/DIR.H, который содержит
#DEFINE DIRSIZ 14 /*MAX LENGTH OF FILE NAME*/
STRUCT DIRECT /*STRUCTURE OF DIRECTORY ENTRY*/
\(
INO_T&_INO; /*INODE NUMBER*/
CHAR &_NAME[DIRSIZ]; /*FILE NAME*/
\);
"Тип" INO_T - это определяемый посредством TYPEDEF тип,
который описывает индекс I-узловой таблицы. На PDP-11 UNIX
этим типом оказывается UNSIGNED, но это не тот сорт информа-
ции, который помещают внутрь программы: на разных системах
этот тип может быть различным. Поэтому и следует использо-
вать TYPEDEF. Полный набор "системных" типов находится в
файле SYS/TUPES.H.
Функция STAT берет имя файла и возвращает всю содержащу-
юся в I-ом узле информацию об этом файле (или -1, если име-
ется ошибка). Таким образом, в результате
STRUCT STAT STBUF;
CHAR *NAME;
STAT(NAME,&STBUF);
структура STBUF наполняется информацией из I-го узла о файле
с именем NAME. Структура, описывающая возвращаемую функцией
STAT информацию, находится в файле SYS/STAT.H и выглядит
следующим образом:
STRUCT STAT /*STRUCTURE RETURNED BY STAT*/
\(
DEV_T ST_DEV; /* DEVICE OF INODE */
INO_T ST_INO; /* INODE NUMBER */
SHORT ST_MODE /* MODE BITS */
SHORT ST_NLINK; / *NUMBER OF LINKS TO FILE */
SHORT ST_UID; /* OWNER'S USER ID */
SHORT ST_GID; /* OWNER'S GROUP ID */
DEV_T ST_RDEV; /* FOR SPECIAL FILES */
OFF_T ST_SIZE; /* FILE SIZE IN CHARACTERS */
TIME_T ST_ATIME; /* TIME LAST ACCESSED */
TIME_T ST_MTIME; /* TIME LAST MODIFIED */
TIME_T ST_CTIME; /* TIME ORIGINALLY CREATED */
\)
Большая часть этой информации объясняется в комментариях.
Элемент ST.MODE содержит набор флагов, описывающих файл; для
удобства определения флагов также находятся в файле
SYS/STAT.H.
#DEFINE S_IFMT 0160000 /* TYPE OF FILE */
#DEFINE S_IFDIR 0040000 /* DIRECTORY */
#DEFINE S_IFCHR 0020000 /* CHARACTER SPECIAL */
#DEFINE S_IFBLK 0060000 /* BLOCK SPECIAL */
#DEFINE S_IFREG 0100000 /* REGULAR */
#DEFINE S_ISUID 04000 /* SET USER ID ON EXECUTION */
#DEFINE S_ISGID 02000 /* SET GROUP ID ON EXECUTION */
#DEFINE S_ISVTX 01000 /*SAVE SWAPPED TEXT AFTER USE*/
#DEFINE S_IREAD 0400 /* READ PERMISSION */
#DEFINE S_IWRITE 0200 /* WRITE PERMISSION */
#DEFINE S_IEXEC 0100 /* EXECUTE PERMISSION */
Теперь мы в состоянии написать программу FSIZE. Если по-
лученный от функции STAT режим указывает, что файл не явля-
ется справочником, то его размер уже под рукой и может быть
напечатан непосредственно. Если же он оказывается справочни-
ком, то мы должны обрабатывать этот справочник отдельно для
каждого файла; так как справочник может в свою очередь со-
держать подсправочники, этот процесс обработки является ре-
курсивным.
Как обычно, ведущая программа главным образом имеет дело
с командной строкой аргументов; она передает каждый аргумент
функции FSIZE в большой буфер.
#INCLUDE <STDIO.H.>
#INCLUDE <SYS/TYPES.H> /*TYPEDEFS*/
#INCLUDE <SYS/DIR.H> /*DIRECTORY ENTRY STRUCTURE*/
#INCLUDE <SYS/STAT.H> /*STRUCTURE RETURNED BY STAT*/
#DEFINE BUFSIZE 256
MAIN(ARGC,ARGV) /*FSIZE:PRINT FILE SIZES*/
CHAR *ARGV[];
\(
CHAR BUF[BUFSIZE];
IF(ARGC==1) \( /*DEFAULT:CURRENT DIRECTORY*/
ATRCPY(BUF,".");
FSIZE(BUF);
\) ELSE
WHILE(--ARGC>0) \(
STRCPY(BUF,*++ARGV);
FSIZE(BUF);
\)
\)
Функция FSIZE печатает размер файла. Если однако файл
оказывается справочником, то FSIZE сначала вызывает функцию
DIRECTORY для обработки всех указанных в нем файлов. Обрати-
те внимание на использование имен флагов S_IFMT и _IFDIR из
файла STAT.H.
FSIZE(NAME) /*PRINT SIZE FOR NAME*/
CHAR *NAME;
\(
STRUCT STAT STBUF;
IF(STAT(NAME,&STBUF)== -1) \(
FPRINTF(STDERR,"FSIZE:CAN'T FIND %S\N",NAME);
RETURN;
\)
IF((STBUF.ST_MODE & S_IFMT)==S_IFDIR)
DIRECTORY(NAME);
PRINTF("%8LD %S\N",STBUF.ST_SIZE,NAME);
\)
Функция DIRECTORY является самой сложной. Однако значи-
тельная ее часть связана с созданием для обрабатываемого в
данный момент файла его полного имени, по которому можно
восстановить путь в дереве.
DIRECTORY(NAME) /*FSIZE FOR ALL FILES IN NAME*/
CHAR *NAME;
(
STRUCT DIRECT DIRBUF;
CHAR *NBP, *NEP;
INT I, FD;
NBP=NAME+STRLEN(NAME);
*NBP++='/'; /*ADD SLASH TO DIRECTORY NAME*/
IF(NBP+DIRSIZ+2>=NAME+BUFSIZE) /*NAME TOO LONG*/
RETURN;
IF((FD=OPEN(NAME,0))== -1)
RETURN;
WHILE(READ(FD,(CHAR *)&DIRBUF,SIZEOF(DIRBUF))>0) \(
IF(DIRBUF.D_INO==0) /*SLOT NOT IN USE*/
CONTINUE;
IF(STRCMP (DIRBUF.D_NAME,".")==0
\!\! STRCMP(DIRBUF.D_NAME,"..")==0
CONTINUE; /*SKIP SELF AND PARENT*/
FOR (I=0,NEP=NBP;I<DIRSIZ;I++)
*NEP++=DIRBUF.D_NAME[I];
*NEP++='\0';
FSIZE(NAME);
\)
CLOSE(FD);
*--NBP='\0'; /*RESTORE NAME*/
)
Если некоторая дыра в справочнике в настоящее время не
используется (потому что файл был удален), то в соответству-
ющее I-узловое число равно нулю, и эта позиция пропускается.
Каждый справочник также содержит запись в самом себе, назы-
ваемую ".", и о своем родителе, ".."; они, очевидно, также
должны быть пропущены, а то программа будет работать весьма
и весьма долго.
Хотя программа FSIZE довольно специализированна, она все
же демонстрирует пару важных идей. во-первых, многие прог-
раммы не являются "системными программами"; они только ис-
пользуют информацию, форма или содержание которой определя-
ется операционной системой. Во-вторых, для таких программ
существенно, что представление этой информации входит только
в стандартные "заголовочные файлы", такие как STAT.H и
DIR.H, и что программы включают эти файлы, а не помещают
фактические описания внутрь самих программ.
В главе 5 мы написали бесхитростный вариант функции
ALLOC. Вариант, который мы напишем теперь, не содержит огра-
ничений: обращения к функциям ALLOC и FREE могут перемежать-
ся в любом порядке; когда это необходимо, функция ALLOC об-
ращается к операционной системе за дополнительной памятью.
Кроме того, что эти процедуры полезны сами по себе, они так-
же иллюстрируют некоторые соображения, связанные с написани-
ем машинно-зависимых программ относительно машинно-независи-
мым образом, и показывают практическое применение структур,
объединений и конструкций TYPEDEF.
Вместо того, чтобы выделять память из скомпилированного
внутри массива фиксированного размера, функция ALLOC будет
по мере необходимости обращаться за памятью к операционной
системе. Поскольку различные события в программе могут тре-
бовать асинхронного выделения памяти, то память, управляемая
ALLOC, не может быть непрерывной. В силу этого свободная па-
мять хранится в виде цепочки свободных блоков. Каждый блок
включает размер, указатель следующего блока и саму свободную
память. Блоки упорядочиваются в порядке возрастания адресов
памяти, причем последний блок (с наибольшим адресом) указы-
вает на первый, так что цепочка фактически оказывается коль-
цом.
При поступлении запроса список свободных блоков просмат-
ривается до тех пор, пока не будет найден достаточно большой
блок. Если этот блок имеет в точности требуемый размер, то
он отцепляется от списка и передается пользователю. Если же
этот блок слишком велик, то он разделяется, нужное количест-
во передается пользователю, а остаток возвращается в свобод-
ный список. Если достаточно большого блока найти не удается,
то операционной системой выделяется новый блок, который
включается в список свободных блоков; затем поиск возобнов-
ляется.
Освобождение памяти также влечет за собой просмотр сво-
бодного списка в поиске подходящего места для введения осво-
божденного блока. Если этот освободившийся блок с какой-либо
стороны примыкает к блоку из списка свободных блоков, то они
объединяются в один блок большего размера, так что память не
становится слишком раздробленной. Обнаружить смежные блоки
просто, потому что свободный список содержится в порядке
возрастания адресов.
Одна из проблем, о которой мы упоминали в главе 5, зак-
лючается в обеспечении того, чтобы возвращаемая функцией
ALLOC память была выровнена подходящим образом для тех
объектов, которые будут в ней храниться. Хотя машины и раз-
личаются, для каждой машины существует тип, требующий наи-
больших ограничений по размещению памяти, если данные самого
ограничительного типа можно поместить в некоторый определен-
ный адрес, то это же возможно и для всех остальных типов.
Например, на IBM 360/370,HONEYWELL 6000 и многих других ма-
шинах любой объект может храниться в границах, соответствую-
щим переменным типа DOUBLE; на PDP-11 будут достаточны пере-
менные типа INT.
Свободный блок содержит указатель следующего блока в це-
почке, запись о размере блока и само свободное пространство;
управляющая информация в начале называется заголовком. Для
упрощения выравнивания все блоки кратны размеру заголовка, а
сам заголовок выровнен надлежащим образом. Это достигается с
помощью объединения, которое содержит желаемую структуру за-
головка и образец наиболее ограничительного по выравниванию
типа:
TYPEDEF INT ALIGN; /*FORCES ALIGNMENT ON PDP-11*/
UNION HEADER \( /*FREE BLOCK HEADER*/
STRUCT \(
UNION HEADER *PTR; /*NEXT FREE BLOCK*/
UNSIGNED SIZE; /*SIZE OF THIS FREE BLOCK*/
\) S;
ALIGN X; /*FORCE ALIGNMENT OF BLOCKS*/
\);
TYPEDEF UNION HEADER HEADER;
Функция ALLOC округляет требуемый размер в символах до
нужного числа единиц размера заголовка; фактический блок,
который будет выделен, содержит на одну единицу больше,
предназначаемую для самого заголовка, и это и есть значение,
которое записывается в поле SIZE заголовка. Указатель, возв-
ращаемый функцией ALLOC, указывает на свободное пространст-
во, а не на сам заголовок.
STATIC HEADER BASE; /*EMPTY LIST TO GET STARTED*/
STATIC HEADER *ALLOCP=NULL; /*LAST ALLOCATED BLOCK*/
CHAR *ALLOC(NBYTES)/*GENERAL-PURPOSE STORAGE ALLOCATOR*/
UNSIGNED NBYTES;
\(
HEADER *MORECORE();
REGISTER HEADER *P, *G;
REGISTER INT NUNITS;
NUNITS=1+(NBYTES+SIZEOF(HEADER)-1)/SIZEOF(HEADER);
IF ((G=ALLOCP)==NULL) \( /*NO FREE LIST YET*/
BASE.S PTR=ALLOCP=G=&BASE;
BASE.S.SIZE=0;
\)
FOR (P=G>S.PTR; ; G=P, P=P->S.PTR) \(
IF (P->S.SIZE>=NUNITS) \( /*BIG ENOUGH*/
IF (P->S.SIZE==NUNITS) /*EXACTLY*/
G->S.PTR=P->S.PTR;
ELSE \( /*ALLOCATE TAIL END*/
P->S.SIZE-=NUNITS;
P+=P->S.SIZE;
P->S.SIZE=NUNITS;
\)
ALLOCP=G;
RETURN((CHAR *)(P+1));
\)
IF(P==ALLOCP) /*WRAPPED AROUND FREE LIST*/
IF((P=MORECORE(NUNITS))==NULL)
RETURN(NULL); /*NONE LEFT*/
\)
\)
Переменная BASE используется для начала работы. Если
ALLOCP имеет значение NULL, как в случае первого обращения к
ALLOC, то создается вырожденный свободный список: он состоит
из свободного блока размера нуль и указателя на самого себя.
В любом случае затем исследуется свободный список. Поиск
свободного блока подходящего размера начинается с того места
(ALLOCP), где был найден последний блок; такая стратегия по-
могает сохранить однородность диска. Если найден слишком
большой блок, то пользователю предлагается его хвостовая
часть; это приводит к тому, что в заголовке исходного блока
нужно изменить только его размер. Во всех случаях возвращае-
мый пользователю указатель указывает на действительно сво-
бодную область, лежащую на единицу дальше заголовка. Обрати-
те внимание на то, что функция ALLOC перед возвращением "P"
преобразует его в указатель на символы.
Функция MORECORE получает память от операционной систе-
мы. Детали того, как это осуществляется, меняются, конечно,
от системы к системе. На системе UNIX точка входа SBRK(N)
возвращает указатель на "N" дополнительных байтов памя-
ти.(указатель удволетворяет всем ограничениям на выравнива-
ние). Так как запрос к системе на выделение памяти является
сравнительно дорогой операцией, мы не хотим делать это при
каждом обращении к функции ALLOC. Поэтому функция MORECORE
округляет затребованное число единиц до большего значения;
этот больший блок будет затем разделен так, как необходимо.
Масштабирующая величина является параметром, который может
быть подобран в соответствии с необходимостью.
#DEFINE NALLOC 128 /*#UNITS TO ALLOCATE AT ONCE*/
STATIC HEADER *MORECORE(NU) /*ASK SYSTEM FOR MEMORY*/
UNSIGNED NU;
\(
CHAR *SBRK();
REGISTER CHAR *CP;
REGISTER HEADER *UP;
REGISTER INT RNU;
RNU=NALLOC*((NU+NALLOC-1)/NALLOC);
CP=SBRK(RNU*SIZEOF(HEADER));
IF ((INT)CP==-1) /*NO SPACE AT ALL*/
RETURN(NULL);
UP=(HEADER *)CP;
UP->S.SIZE=RNU;
FREE((CHAR *)(UP+1));
RETURN(ALLOCP);
\)
Если больше не осталось свободного пространства, то фун-
кция SBRK возвращает "-1", хотя NULL был бы лучшим выбором.
Для надежности сравнения "-1" должна быть преобразована к
типу INT. Снова приходится многократно использовать явные
преобразования (перевод) типов, чтобы обеспечить определен-
ную независимость функций от деталей представления указате-
лей на различных машинах.
И последнее - сама функция FREE. Начиная с ALLOCP, она
просто просматривает свободный список в поиске места для
введения свободного блока. Это место находится либо между
двумя существующими блоками, либо в одном из концов списка.
В любом случае, если освободившийся блок примыкает к одному
из соседних, смежные блоки объединяются. Следить нужно толь-
ко затем, чтобы указатели указывали на то, что нужно, и что-
бы размеры были установлены правильно.
FREE(AP) /*PUT BLOCKE AP IN FREE LIST*/
CHAR *AP;
\(
REGISTER HEADER *P, *G;
P=(HEADER*)AP-1; /*POINT TO HEADER*/
FOR (G=ALLOCP; !(P>G && P>G->S.PTR);G=G->S.PTR)
IF (G>=G->S.PTR && (P>G \!\! P<G->S.PTR))
BREAK; /*AT ONE END OR OTHER*/
IF (P+P->S.SIZE==G->S.PTR)\(/*JOIN TO UPPER NBR*/
P->S.SIZE += G->S.PTR->S.SIZE;
P->S.PTR = G->S.PTR->S.PTR;
\) ELSE
P->S.PTR = G->S.PTR;
IF (G+G->S.SIZE==P) \( /*JOIN TO LOWER NBR*/
G->S.SIZE+=P->S.SIZE;
G->S.PTR=P->S.PTR;
\) ELSE
G->S.PTR=P;
ALLOCP = G;
\)
Хотя распределение памяти по своей сути зависит от ис-
пользуемой машины, приведенная выше программа показывает,
как эту зависимость можно регулировать и ограничить весьма
небольшой частью программы. Использование TYPEDEF и UNION
позволяет справиться с выравниванием (при условии, что функ-
ция SBRK обеспечивает подходящий указатель). Переводы типов
организуют выполнение явного преобразования типов и даже
справляются с неудачно разработанным системным интерфейсом.
И хотя рассмотренные здесь подробности связаны с распределе-
нием памяти, общий подход равным образом применим и к другим
ситуациям.
Упражнение 8-6
--------------
Функция из стандартной библиотеки CALLOC(N,SIZE) возвра-
щает указатель на "N" объектов размера SIZE, причем соответ-
ствующая память инициализируется на нуль. напишите программу
для CALLOC, используя функцию ALLOC либо в качестве образца,
либо как функцию, к которой происходит обращение.
Упражнение 8-7
---------------
Функция ALLOC принимает затребованный размер, не прове-
ряя его правдоподобности; функция FREE полагает, что тот
блок, который она должна освободить, содержит правильное
значение в поле размера. Усовершенствуйте эти процедуры,
затратив больше усилий на проверку ошибок.
Упражнение 8-8
---------------
Напишите функцию BFREE(P,N), которая включает произволь-
ный блок "P" из "N" символов в список свободных блоков, уп-
равляемый функциями ALLOC и FREE. С помощью функции BFREE
пользователь может в любое время добавлять в свободный спи-
сок статический или внешний массив.
дать файл с именем NAME, и "-1" в противном случае. Если
файл с таким именем уже существует, CREAT усечет его до ну-
левой длины; создание файла, который уже существует, не яв-
ляется ошибкой.
Если файл является совершенно новым, то CREAT создает
его с определенным режимом защиты, специфицируемым аргумен-
том PMODE. В системе файлов на UNIX с файлом связываются де-
вять битов защиты информации, которые управляют разрешением
на чтение, запись и выполнение для владельца файла, для
группы владельцев и для всех остальных пользователей. Таким
образом, трехзначное восьмеричное число наиболее удобно для
спецификации разрешений. Например, число 0755 свидетельству-
ет о разрешении на чтение, запись и выполнение для владельца
и о разрешении на чтение и выполнение для группы и всех ос-
тальных.
Для иллюстрации ниже приводится программа копирования
одного файла в другой, являющаяся упрощенным вариантом ути-
литы CP системы UNIX. (Основное упрощение заключается в том,
что наш вариант копирует только один файл и что второй аргу-
мент не должен быть справочником).
#DEFINE NULL 0
#DEFINE BUFSIZE 512
#DEFINE PMODE 0644/*RW FOR OWNER,R FOR GROUP,OTHERS*/
MAIN(ARGC,ARGV) /*CP: COPY F1 TO F2*/
INT ARGC;
CHAR *ARGV[];
\(
INT F1, F2, N;
CHAR BUF[BUFSIZE];
IF (ARGC ! = 3)
ERROR("USAGE:CP FROM TO", NULL);
IF ((F1=OPEN(ARGV[1],0))== -1)
ERROR("CP:CAN'T OPEN %S", ARGV[1]);
IF ((F2=CREAT(ARGV[2],PMODE))== -1)
ERROR("CP: CAN'T CREATE %S", ARGV[2]);
WHILE ((N=READ(F1,BUF,BUFSIZE))>0)
IF (WRITE(F2,BUF,N) !=N)
ERROR("CP: WRITE ERROR", NULL);
EXIT(0);
\)
ERROR(S1,S2) /*PRINT ERROR MESSAGE AND DIE*/
CHAR *S1, S2;
\(
PRINTF(S1,S2);
PRINTF("\N");
EXIT(1);
\)
Существует ограничение (обычно 15 - 25) на количество
файлов, которые программа может иметь открытыми одновремен-
но. В соответствии с этим любая программа, собирающаяся ра-
ботать со многими файлами, должна быть подготовлена к пов-
торному использованию дескрипторов файлов. Процедура CLOSE
прерывает связь между дескриптором файла и открытым файлом и
освобождает дескриптор файла для использования с некоторым
другим файлом. Завершение выполнения программы через EXIT
или в результате возврата из ведущей программы приводит к
закрытию всех открытых файлов.
Функция расцепления UNLINK (FILENAME) удаляет из системы
файлов файл с именем FILENAME ( из данного справочного фай-
ла. Файл может быть сцеплен с другим справочником, возможно,
под другим именем - примеч.переводчика).
Упражнение 8-1
--------------
Перепишите программу CAT из главы 7, используя функции
READ, WRITE, OPEN и CLOSE вместо их эквивалентов из стандар-
тной библиотеки. Проведите эксперименты для определения от-
носительной скорости работы этих двух вариантов.
Нормально при работе с файлами ввод и вывод осуществля-
ется последовательно: при каждом обращении к функциям READ и
WRITE чтение или запись начинаются с позиции, непосредствен-
но следующей за предыдущей обработанной. Но при необходимос-
ти файл может читаться или записываться в любом произвольном
порядке. Обращение к системе с помощью функции LSEEK позво-
ляет передвигаться по файлу, не производя фактического чте-
ния или записи. В результате обращения
LSEEK(FD,OFFSET,ORIGIN);
текущая позиция в файле с дескриптором FD передвигается на
позицию OFFSET (смещение), которая отсчитывается от места,
указываемого аргументом ORIGIN (начало отсчета). Последующее
чтение или запись будут теперь начинаться с этой позиции.
Аргумент OFFSET имеет тип LONG; FD и ORIGIN имеют тип INT.
Аргумент ORIGIN может принимать значения 0,1 или 2, указывая
на то, что величина OFFSET должна отсчитываться соответст-
венно от начала файла, от текущей позиции или от конца фай-
ла. Например, чтобы дополнить файл, следует перед записью
найти его конец:
LSEEK(FD,0L,2);
чтобы вернуться к началу ("перемотать обратно"), можно напи-
сать:
LSEEK(FD,0L,0);
обратите внимание на аргумент 0L; его можно было бы записать
и в виде (LONG) 0.
Функция LSEEK позволяет обращаться с файлами примерно
так же, как с большими массивами, правда ценой более медлен-
ного доступа. следующая простая функция, например, считывает
любое количество байтов, начиная с произвольного места в
файле.
GET(FD,POS,BUF,N) /*READ N BYTES FROM POSITION POS*/
INT FD, N;
LONG POS;
CHAR *BUF;
\(
LSEEK(FD,POS,0); /*GET TO POS*/
RETURN(READ(FD,BUF,N));
\)
В более ранних редакциях, чем редакция 7 системы UNIX,
основная точка входа в систему ввода-вывода называется SEEK.
Функция SEEK идентична функции LSEEK, за исключением того,
что аргумент OFFSET имеет тип INT, а не LONG. в соответствии
с этим, поскольку на PDP-11 целые имеют только 16 битов, ар-
гумент OFFSET, указываемый функции SEEK, ограничен величиной
65535; по этой причине аргумент ORIGIN может иметь значения
3, 4, 5, которые заставляют функцию SEEK умножить заданное
значение OFFSET на 512 (количество байтов в одном физическом
блоке) и затем интерпретировать ORIGIN, как если это 0, 1
или 2 соответственно. Следовательно, чтобы достичь произ-
вольного места в большом файле, нужно два обращения к SEEK:
сначала одно, которое выделяет нужный блок, а затем второе,
где ORIGIN имеет значение 1 и которое осуществляет передви-
жение на желаемый байт внутри блока.
Упражнение 8-2
---------------
Очевидно, что SEEK может быть написана в терминалах
LSEEK и наоборот. напишите каждую функцию через другую.
Давайте теперь на примере реализации функций FOPEN и
GETC из стандартной библиотеки подпрограмм продемонстрируем,
как некоторые из описанных элементов объединяются вместе.
Напомним, что в стандартной библиотеке файлы описыватся
посредством указателей файлов, а не дескрипторов. Указатель
файла является указателем на структуру, которая содержит
несколько элементов информации о файле: указатель буфера,
чтобы файл мог читаться большими порциями; счетчик числа
символов, оставшихся в буфере; указатель следующей позиции
символа в буфере; некоторые признаки, указывающие режим чте-
ния или записи и т.д.; дескриптор файла.
Описывающая файл структура данных содержится в файле
STDIO.H, который должен включаться (посредством #INCLUDE) в
любой исходный файл, в котором используются функции из стан-
дартной библиотеки. Он также включается функциями этой биб-
лиотеки. В приводимой ниже выдержке из файла STDIO.H имена,
предназначаемые только для использования функциями библиоте-
ки, начинаются с подчеркивания, с тем чтобы уменьшить веро-
ятность совпадения с именами в программе пользователя.
DEFINE _BUFSIZE 512
DEFINE _NFILE 20 /*FILES THAT CAN BE HANDLED*/
TYPEDEF STRUCT _IOBUF \(
CHAR *_PTR; /*NEXT CHARACTER POSITION*/
INT _CNT; /*NUMBER OF CHARACTERS LEFT*/
CHAR *_BASE; /*LOCATION OF BUFFER*/
INT _FLAG; /*MODE OF FILE ACCESS*/
INT _FD; /*FILE DESCRIPTOR*/
) FILE;
XTERN FILE _IOB[_NFILE];
DEFINE STDIN (&_IOB[0])
DEFINE STDOUT (&_IOB[1])
DEFINE STDERR (&_IOB[2])
DEFINE _READ 01 /* FILE OPEN FOR READING */
DEFINE _WRITE 02 /* FILE OPEN FOR WRITING */
DEFINE _UNBUF 04 /* FILE IS UNBUFFERED */
DEFINE _BIGBUF 010 /* BIG BUFFER ALLOCATED */
DEFINE _EOF 020 /* EOF HAS OCCURRED ON THIS FILE */
DEFINE _ERR 040 /* ERROR HAS OCCURRED ON THIS FILE */
DEFINE NULL 0
DEFINE EOF (-1)
DEFINE GETC(P) (--(P)->_CNT >= 0 \
? *(P)->_PTR++ & 0377 : _FILEBUF(P))
DEFINE GETCHAR() GETC(STDIN)
DEFINE PUTC(X,P) (--(P)->_CNT >= 0 \
? *(P)->_PTR++ = (X) : _FLUSHBUF((X),P))
DEFINE PUTCHAR(X) PUTC(X,STDOUT)
В нормальном состоянии макрос GETC просто уменьшает
счетчик, передвигает указатель и возвращает символ. (Если
определение #DEFINE слишком длинное, то оно продолжается с
помощью обратной косой черты). Если однако счетчик становит-
ся отрицательным, то GETC вызывает функцию _FILEBUF, которая
снова заполняет буфер, реинициализирует содержимое структуры
и возвращает символ. Функция может предоставлять переносимый
интерфейс и в то же время содержать непереносимые конструк-
ции: GETC маскирует символ числом 0377, которое подавляет
знаковое расширение, осуществляемое на PDP-11, и тем самым
гарантирует положительность всех символов.
Хотя мы не собираемся обсуждать какие-либо детали, мы
все же включили сюда определение макроса PUTC, для того что-
бы показать, что она работает в основном точно также, как и
GETC, обращаясь при заполнении буфера к функции _FLUSHBUF.
Теперь может быть написана функция FOPEN. Большая часть
программы функции FOPEN связана с открыванием файла и распо-
ложением его в нужном месте, а также с установлением битов
признаков таким образом, чтобы они указывали нужное состоя-
ние. Функция FOPEN не выделяет какой-либо буферной памяти;
это делается функцией _FILEBUF при первом чтении из файла.
#INCLUDE <STDIO.H>
#DEFINE PMODE 0644 /*R/W FOR OWNER;R FOR OTHERS*/
FILE *FOPEN(NAME,MODE) /*OPEN FILE,RETURN FILE PTR*/
REGISTER CHAR *NAME, *MODE;
\(
REGISTER INT FD;
REGISTER FILE *FP;
IF(*MODE !='R'&&*MODE !='W'&&*MODE !='A') \(
FPRINTF(STDERR,"ILLEGAL MODE %S OPENING %S\N",
MODE,NAME);
EXIT(1);
\)
FOR (FP=_IOB;FP<_IOB+_NFILE;FP++)
IF((FP->_FLAG & (_READ \! _WRITE))==0)
BREAK; /*FOUND FREE SLOT*/
IF(FP>=_IOB+_NFILE) /*NO FREE SLOTS*/
RETURN(NULL);
IF(*MODE=='W') /*ACCESS FILE*/
FD=CREAT(NAME,PMODE);
ELSE IF(*MODE=='A') \(
IF((FD=OPEN(NAME,1))==-1)
FD=CREAT(NAME,PMODE);
LSEEK(FD,OL,2);
\) ELSE
FD=OPEN(NAME,0);
IF(FD==-1) /*COULDN'T ACCESS NAME*/
RETURN(NULL);
FP->_FD=FD;
FP->_CNT=0;
FP->_BASE=NULL;
FP->_FLAG &=(_READ \! _WRITE);
FP->_FLAG \!=(*MODE=='R') ? _READ : _WRITE;
RETURN(FP);
\)
Функция _FILEBUF несколько более сложная. Основная труд-
ность заключается в том, что _FILEBUF стремится разрешить
доступ к файлу и в том случае, когда может не оказаться дос-
таточно места в памяти для буферизации ввода или вывода. ес-
ли пространство для нового буфера может быть получено обра-
щением к функции CALLOC, то все отлично; если же нет, то
_FILEBUF осуществляет небуферизованный ввод/ вывод, исполь-
зуя отдельный символ, помещенный в локальном массиве.
#INCLUDE <STDIO.H>
_FILLBUF(FP) /*ALLOCATE AND FILL INPUT BUFFER*/
REGISTER FILE *FP;
(
STATIC CHAR SMALLBUF(NFILE);/*FOR UNBUFFERED 1/0*/
CHAR *CALLOC();
IF((FR->_FLAG&_READ)==0\!\!(FP->_FLAG&(EOF\!_ERR))\!=0
RETURN(EOF);
WHILE(FP->_BASE==NULL) /*FIND BUFFER SPACE*/
IF(FP->_FLAG & _UNBUF) /*UNBUFFERED*/
FP->_BASE=&SMALLBUF[FP->_FD];
ELSE IF((FP->_BASE=CALLOC(_BUFSIZE,1))==NULL)
FP->_FLAG \!=_UNBUF; /*CAN'T GET BIG BUF*/
ELSE
FP->_FLAG \!=_BIGBUF; /*GOT BIG ONE*/
FP->_PTR=FP->_BASE;
FP->_CNT=READ(FP->_FD, FP->_PTR,
FP->_FLAG & _UNBUF ? 1 : _BUFSIZE);
FF(--FP->_CNT<0) \(
IF(FP->_CNT== -1)
FP->_FLAG \! = _EOF;
ELSE
FP->_FLAG \! = _ ERR;
FP->_CNT = 0;
RETURN(EOF);
\)
RETURN(*FP->_PTR++ & 0377); /*MAKE CHAR POSITIVE*/
)
При первом обращении к GETC для конкретного файла счетчик
оказывается равным нулю, что приводит к обращению к
_FILEBUF. Если функция _FILEBUF найдет, что этот файл не от-
крыт для чтения, она немедленно возвращает EOF. В противном
случае она пытается выделить большой буфер, а если ей это не
удается, то буфер из одного символа. При этом она заносит в
_FLAG соответствующую информацию о буферизации.
Раз буфер уже создан, функция _FILEBUF просто вызывает
функцию READ для его заполнения, устанавливает счетчик и
указатели и возвращает символ из начала буфера.
Единственный оставшийся невыясненным вопрос состоит в
том, как все начинается. Массив _IOB должен быть определен и
инициализирован для STDIN, STDOUT и STDERR:
FILE _IOB[NFILE] = \(
(NULL,0,_READ,0), /*STDIN*/
(NULL,0,NULL,1), /*STDOUT*/
(NULL,0,NULL,_WRITE \! _UNBUF,2) /*STDERR*/
);
Из инициализации части _FLAG этого массива структур видно,
что файл STDIN предназначен для чтения, файл STDOUT - для
записи и файл STDERR - для записи без использования буфера.
Упражнение 8-3
--------------
Перепишите функции FOPEN и _FILEBUF, используя поля
вместо явных побитовых операций.
Упражнение 8-4
---------------
Разработайте и напишите функции _FLUSHBUF и FCLOSE.
Упражнение 8-5
---------------
Стандартная библиотека содержит функцию
FSEEK(FP, OFFSET, ORIGIN)
которая идентична функции LSEEK, исключая то, что FP являет-
ся указателем файла, а не дескриптором файла. Напишите
FSEEK. Убедитесь, что ваша FSEEK правильно согласуется с бу-
феризацией, сделанной для других функций библиотеки.
Иногда требуется другой вид взаимодействия с системой
файлов - определение информации о файле, а не того, что в
нем содержится. Примером может служить команда LS ("список
справочника") системы UNIX. По этой команде распечатываются
имена файлов из справочника и, необязательно, другая инфор-
мация, такая как размеры, разрешения и т.д.
Поскольку, по крайней мере, на системе UNIX справочник
является просто файлом, то в такой команде, как LS нет ниче-
го особенного; она читает файл и выделяет нужные части из
находящейся там информации. Однако формат информации опреде-
ляется системой, так что LS должна знать, в каком виде все
представляется в системе.
Мы это частично проиллюстрируем при написании программы
FSIZE. Программа FSIZE представляет собой специальную форму
LS, которая печатает размеры всех файлов, указанных в списке
ее аргументов. Если один из файлов является справочником, то
для обработки этого справочника программа FSIZE обращается
сама к себе рекурсивно. если же аргументы вообще отсутству-
ют, то обрабатывается текущий справочник.
Для начала дадим краткий обзор структуры системы файлов.
Справочник - это файл, который содержит список имен файлов и
некоторое указание о том, где они размещаются. Фактически
это указание является индексом для другой таблицы, которую
называют "I - узловой таблицей". Для файла I-узел - это то,
где содержится вся информация о файле, за исключением его
имени. Запись в справочнике состоит только из двух элемен-
тов: номера I-узла и имени файла. Точная спецификация посту-
пает при включении файла SYS/DIR.H, который содержит
#DEFINE DIRSIZ 14 /*MAX LENGTH OF FILE NAME*/
STRUCT DIRECT /*STRUCTURE OF DIRECTORY ENTRY*/
\(
INO_T&_INO; /*INODE NUMBER*/
CHAR &_NAME[DIRSIZ]; /*FILE NAME*/
\);
"Тип" INO_T - это определяемый посредством TYPEDEF тип,
который описывает индекс I-узловой таблицы. На PDP-11 UNIX
этим типом оказывается UNSIGNED, но это не тот сорт информа-
ции, который помещают внутрь программы: на разных системах
этот тип может быть различным. Поэтому и следует использо-
вать TYPEDEF. Полный набор "системных" типов находится в
файле SYS/TUPES.H.
Функция STAT берет имя файла и возвращает всю содержащу-
юся в I-ом узле информацию об этом файле (или -1, если име-
ется ошибка). Таким образом, в результате
STRUCT STAT STBUF;
CHAR *NAME;
STAT(NAME,&STBUF);
структура STBUF наполняется информацией из I-го узла о файле
с именем NAME. Структура, описывающая возвращаемую функцией
STAT информацию, находится в файле SYS/STAT.H и выглядит
следующим образом:
STRUCT STAT /*STRUCTURE RETURNED BY STAT*/
\(
DEV_T ST_DEV; /* DEVICE OF INODE */
INO_T ST_INO; /* INODE NUMBER */
SHORT ST_MODE /* MODE BITS */
SHORT ST_NLINK; / *NUMBER OF LINKS TO FILE */
SHORT ST_UID; /* OWNER'S USER ID */
SHORT ST_GID; /* OWNER'S GROUP ID */
DEV_T ST_RDEV; /* FOR SPECIAL FILES */
OFF_T ST_SIZE; /* FILE SIZE IN CHARACTERS */
TIME_T ST_ATIME; /* TIME LAST ACCESSED */
TIME_T ST_MTIME; /* TIME LAST MODIFIED */
TIME_T ST_CTIME; /* TIME ORIGINALLY CREATED */
\)
Большая часть этой информации объясняется в комментариях.
Элемент ST.MODE содержит набор флагов, описывающих файл; для
удобства определения флагов также находятся в файле
SYS/STAT.H.
#DEFINE S_IFMT 0160000 /* TYPE OF FILE */
#DEFINE S_IFDIR 0040000 /* DIRECTORY */
#DEFINE S_IFCHR 0020000 /* CHARACTER SPECIAL */
#DEFINE S_IFBLK 0060000 /* BLOCK SPECIAL */
#DEFINE S_IFREG 0100000 /* REGULAR */
#DEFINE S_ISUID 04000 /* SET USER ID ON EXECUTION */
#DEFINE S_ISGID 02000 /* SET GROUP ID ON EXECUTION */
#DEFINE S_ISVTX 01000 /*SAVE SWAPPED TEXT AFTER USE*/
#DEFINE S_IREAD 0400 /* READ PERMISSION */
#DEFINE S_IWRITE 0200 /* WRITE PERMISSION */
#DEFINE S_IEXEC 0100 /* EXECUTE PERMISSION */
Теперь мы в состоянии написать программу FSIZE. Если по-
лученный от функции STAT режим указывает, что файл не явля-
ется справочником, то его размер уже под рукой и может быть
напечатан непосредственно. Если же он оказывается справочни-
ком, то мы должны обрабатывать этот справочник отдельно для
каждого файла; так как справочник может в свою очередь со-
держать подсправочники, этот процесс обработки является ре-
курсивным.
Как обычно, ведущая программа главным образом имеет дело
с командной строкой аргументов; она передает каждый аргумент
функции FSIZE в большой буфер.
#INCLUDE <STDIO.H.>
#INCLUDE <SYS/TYPES.H> /*TYPEDEFS*/
#INCLUDE <SYS/DIR.H> /*DIRECTORY ENTRY STRUCTURE*/
#INCLUDE <SYS/STAT.H> /*STRUCTURE RETURNED BY STAT*/
#DEFINE BUFSIZE 256
MAIN(ARGC,ARGV) /*FSIZE:PRINT FILE SIZES*/
CHAR *ARGV[];
\(
CHAR BUF[BUFSIZE];
IF(ARGC==1) \( /*DEFAULT:CURRENT DIRECTORY*/
ATRCPY(BUF,".");
FSIZE(BUF);
\) ELSE
WHILE(--ARGC>0) \(
STRCPY(BUF,*++ARGV);
FSIZE(BUF);
\)
\)
Функция FSIZE печатает размер файла. Если однако файл
оказывается справочником, то FSIZE сначала вызывает функцию
DIRECTORY для обработки всех указанных в нем файлов. Обрати-
те внимание на использование имен флагов S_IFMT и _IFDIR из
файла STAT.H.
FSIZE(NAME) /*PRINT SIZE FOR NAME*/
CHAR *NAME;
\(
STRUCT STAT STBUF;
IF(STAT(NAME,&STBUF)== -1) \(
FPRINTF(STDERR,"FSIZE:CAN'T FIND %S\N",NAME);
RETURN;
\)
IF((STBUF.ST_MODE & S_IFMT)==S_IFDIR)
DIRECTORY(NAME);
PRINTF("%8LD %S\N",STBUF.ST_SIZE,NAME);
\)
Функция DIRECTORY является самой сложной. Однако значи-
тельная ее часть связана с созданием для обрабатываемого в
данный момент файла его полного имени, по которому можно
восстановить путь в дереве.
DIRECTORY(NAME) /*FSIZE FOR ALL FILES IN NAME*/
CHAR *NAME;
(
STRUCT DIRECT DIRBUF;
CHAR *NBP, *NEP;
INT I, FD;
NBP=NAME+STRLEN(NAME);
*NBP++='/'; /*ADD SLASH TO DIRECTORY NAME*/
IF(NBP+DIRSIZ+2>=NAME+BUFSIZE) /*NAME TOO LONG*/
RETURN;
IF((FD=OPEN(NAME,0))== -1)
RETURN;
WHILE(READ(FD,(CHAR *)&DIRBUF,SIZEOF(DIRBUF))>0) \(
IF(DIRBUF.D_INO==0) /*SLOT NOT IN USE*/
CONTINUE;
IF(STRCMP (DIRBUF.D_NAME,".")==0
\!\! STRCMP(DIRBUF.D_NAME,"..")==0
CONTINUE; /*SKIP SELF AND PARENT*/
FOR (I=0,NEP=NBP;I<DIRSIZ;I++)
*NEP++=DIRBUF.D_NAME[I];
*NEP++='\0';
FSIZE(NAME);
\)
CLOSE(FD);
*--NBP='\0'; /*RESTORE NAME*/
)
Если некоторая дыра в справочнике в настоящее время не
используется (потому что файл был удален), то в соответству-
ющее I-узловое число равно нулю, и эта позиция пропускается.
Каждый справочник также содержит запись в самом себе, назы-
ваемую ".", и о своем родителе, ".."; они, очевидно, также
должны быть пропущены, а то программа будет работать весьма
и весьма долго.
Хотя программа FSIZE довольно специализированна, она все
же демонстрирует пару важных идей. во-первых, многие прог-
раммы не являются "системными программами"; они только ис-
пользуют информацию, форма или содержание которой определя-
ется операционной системой. Во-вторых, для таких программ
существенно, что представление этой информации входит только
в стандартные "заголовочные файлы", такие как STAT.H и
DIR.H, и что программы включают эти файлы, а не помещают
фактические описания внутрь самих программ.
В главе 5 мы написали бесхитростный вариант функции
ALLOC. Вариант, который мы напишем теперь, не содержит огра-
ничений: обращения к функциям ALLOC и FREE могут перемежать-
ся в любом порядке; когда это необходимо, функция ALLOC об-
ращается к операционной системе за дополнительной памятью.
Кроме того, что эти процедуры полезны сами по себе, они так-
же иллюстрируют некоторые соображения, связанные с написани-
ем машинно-зависимых программ относительно машинно-независи-
мым образом, и показывают практическое применение структур,
объединений и конструкций TYPEDEF.
Вместо того, чтобы выделять память из скомпилированного
внутри массива фиксированного размера, функция ALLOC будет
по мере необходимости обращаться за памятью к операционной
системе. Поскольку различные события в программе могут тре-
бовать асинхронного выделения памяти, то память, управляемая
ALLOC, не может быть непрерывной. В силу этого свободная па-
мять хранится в виде цепочки свободных блоков. Каждый блок
включает размер, указатель следующего блока и саму свободную
память. Блоки упорядочиваются в порядке возрастания адресов
памяти, причем последний блок (с наибольшим адресом) указы-
вает на первый, так что цепочка фактически оказывается коль-
цом.
При поступлении запроса список свободных блоков просмат-
ривается до тех пор, пока не будет найден достаточно большой
блок. Если этот блок имеет в точности требуемый размер, то
он отцепляется от списка и передается пользователю. Если же
этот блок слишком велик, то он разделяется, нужное количест-
во передается пользователю, а остаток возвращается в свобод-
ный список. Если достаточно большого блока найти не удается,
то операционной системой выделяется новый блок, который
включается в список свободных блоков; затем поиск возобнов-
ляется.
Освобождение памяти также влечет за собой просмотр сво-
бодного списка в поиске подходящего места для введения осво-
божденного блока. Если этот освободившийся блок с какой-либо
стороны примыкает к блоку из списка свободных блоков, то они
объединяются в один блок большего размера, так что память не
становится слишком раздробленной. Обнаружить смежные блоки
просто, потому что свободный список содержится в порядке
возрастания адресов.
Одна из проблем, о которой мы упоминали в главе 5, зак-
лючается в обеспечении того, чтобы возвращаемая функцией
ALLOC память была выровнена подходящим образом для тех
объектов, которые будут в ней храниться. Хотя машины и раз-
личаются, для каждой машины существует тип, требующий наи-
больших ограничений по размещению памяти, если данные самого
ограничительного типа можно поместить в некоторый определен-
ный адрес, то это же возможно и для всех остальных типов.
Например, на IBM 360/370,HONEYWELL 6000 и многих других ма-
шинах любой объект может храниться в границах, соответствую-
щим переменным типа DOUBLE; на PDP-11 будут достаточны пере-
менные типа INT.
Свободный блок содержит указатель следующего блока в це-
почке, запись о размере блока и само свободное пространство;
управляющая информация в начале называется заголовком. Для
упрощения выравнивания все блоки кратны размеру заголовка, а
сам заголовок выровнен надлежащим образом. Это достигается с
помощью объединения, которое содержит желаемую структуру за-
головка и образец наиболее ограничительного по выравниванию
типа:
TYPEDEF INT ALIGN; /*FORCES ALIGNMENT ON PDP-11*/
UNION HEADER \( /*FREE BLOCK HEADER*/
STRUCT \(
UNION HEADER *PTR; /*NEXT FREE BLOCK*/
UNSIGNED SIZE; /*SIZE OF THIS FREE BLOCK*/
\) S;
ALIGN X; /*FORCE ALIGNMENT OF BLOCKS*/
\);
TYPEDEF UNION HEADER HEADER;
Функция ALLOC округляет требуемый размер в символах до
нужного числа единиц размера заголовка; фактический блок,
который будет выделен, содержит на одну единицу больше,
предназначаемую для самого заголовка, и это и есть значение,
которое записывается в поле SIZE заголовка. Указатель, возв-
ращаемый функцией ALLOC, указывает на свободное пространст-
во, а не на сам заголовок.
STATIC HEADER BASE; /*EMPTY LIST TO GET STARTED*/
STATIC HEADER *ALLOCP=NULL; /*LAST ALLOCATED BLOCK*/
CHAR *ALLOC(NBYTES)/*GENERAL-PURPOSE STORAGE ALLOCATOR*/
UNSIGNED NBYTES;
\(
HEADER *MORECORE();
REGISTER HEADER *P, *G;
REGISTER INT NUNITS;
NUNITS=1+(NBYTES+SIZEOF(HEADER)-1)/SIZEOF(HEADER);
IF ((G=ALLOCP)==NULL) \( /*NO FREE LIST YET*/
BASE.S PTR=ALLOCP=G=&BASE;
BASE.S.SIZE=0;
\)
FOR (P=G>S.PTR; ; G=P, P=P->S.PTR) \(
IF (P->S.SIZE>=NUNITS) \( /*BIG ENOUGH*/
IF (P->S.SIZE==NUNITS) /*EXACTLY*/
G->S.PTR=P->S.PTR;
ELSE \( /*ALLOCATE TAIL END*/
P->S.SIZE-=NUNITS;
P+=P->S.SIZE;
P->S.SIZE=NUNITS;
\)
ALLOCP=G;
RETURN((CHAR *)(P+1));
\)
IF(P==ALLOCP) /*WRAPPED AROUND FREE LIST*/
IF((P=MORECORE(NUNITS))==NULL)
RETURN(NULL); /*NONE LEFT*/
\)
\)
Переменная BASE используется для начала работы. Если
ALLOCP имеет значение NULL, как в случае первого обращения к
ALLOC, то создается вырожденный свободный список: он состоит
из свободного блока размера нуль и указателя на самого себя.
В любом случае затем исследуется свободный список. Поиск
свободного блока подходящего размера начинается с того места
(ALLOCP), где был найден последний блок; такая стратегия по-
могает сохранить однородность диска. Если найден слишком
большой блок, то пользователю предлагается его хвостовая
часть; это приводит к тому, что в заголовке исходного блока
нужно изменить только его размер. Во всех случаях возвращае-
мый пользователю указатель указывает на действительно сво-
бодную область, лежащую на единицу дальше заголовка. Обрати-
те внимание на то, что функция ALLOC перед возвращением "P"
преобразует его в указатель на символы.
Функция MORECORE получает память от операционной систе-
мы. Детали того, как это осуществляется, меняются, конечно,
от системы к системе. На системе UNIX точка входа SBRK(N)
возвращает указатель на "N" дополнительных байтов памя-
ти.(указатель удволетворяет всем ограничениям на выравнива-
ние). Так как запрос к системе на выделение памяти является
сравнительно дорогой операцией, мы не хотим делать это при
каждом обращении к функции ALLOC. Поэтому функция MORECORE
округляет затребованное число единиц до большего значения;
этот больший блок будет затем разделен так, как необходимо.
Масштабирующая величина является параметром, который может
быть подобран в соответствии с необходимостью.
#DEFINE NALLOC 128 /*#UNITS TO ALLOCATE AT ONCE*/
STATIC HEADER *MORECORE(NU) /*ASK SYSTEM FOR MEMORY*/
UNSIGNED NU;
\(
CHAR *SBRK();
REGISTER CHAR *CP;
REGISTER HEADER *UP;
REGISTER INT RNU;
RNU=NALLOC*((NU+NALLOC-1)/NALLOC);
CP=SBRK(RNU*SIZEOF(HEADER));
IF ((INT)CP==-1) /*NO SPACE AT ALL*/
RETURN(NULL);
UP=(HEADER *)CP;
UP->S.SIZE=RNU;
FREE((CHAR *)(UP+1));
RETURN(ALLOCP);
\)
Если больше не осталось свободного пространства, то фун-
кция SBRK возвращает "-1", хотя NULL был бы лучшим выбором.
Для надежности сравнения "-1" должна быть преобразована к
типу INT. Снова приходится многократно использовать явные
преобразования (перевод) типов, чтобы обеспечить определен-
ную независимость функций от деталей представления указате-
лей на различных машинах.
И последнее - сама функция FREE. Начиная с ALLOCP, она
просто просматривает свободный список в поиске места для
введения свободного блока. Это место находится либо между
двумя существующими блоками, либо в одном из концов списка.
В любом случае, если освободившийся блок примыкает к одному
из соседних, смежные блоки объединяются. Следить нужно толь-
ко затем, чтобы указатели указывали на то, что нужно, и что-
бы размеры были установлены правильно.
FREE(AP) /*PUT BLOCKE AP IN FREE LIST*/
CHAR *AP;
\(
REGISTER HEADER *P, *G;
P=(HEADER*)AP-1; /*POINT TO HEADER*/
FOR (G=ALLOCP; !(P>G && P>G->S.PTR);G=G->S.PTR)
IF (G>=G->S.PTR && (P>G \!\! P<G->S.PTR))
BREAK; /*AT ONE END OR OTHER*/
IF (P+P->S.SIZE==G->S.PTR)\(/*JOIN TO UPPER NBR*/
P->S.SIZE += G->S.PTR->S.SIZE;
P->S.PTR = G->S.PTR->S.PTR;
\) ELSE
P->S.PTR = G->S.PTR;
IF (G+G->S.SIZE==P) \( /*JOIN TO LOWER NBR*/
G->S.SIZE+=P->S.SIZE;
G->S.PTR=P->S.PTR;
\) ELSE
G->S.PTR=P;
ALLOCP = G;
\)
Хотя распределение памяти по своей сути зависит от ис-
пользуемой машины, приведенная выше программа показывает,
как эту зависимость можно регулировать и ограничить весьма
небольшой частью программы. Использование TYPEDEF и UNION
позволяет справиться с выравниванием (при условии, что функ-
ция SBRK обеспечивает подходящий указатель). Переводы типов
организуют выполнение явного преобразования типов и даже
справляются с неудачно разработанным системным интерфейсом.
И хотя рассмотренные здесь подробности связаны с распределе-
нием памяти, общий подход равным образом применим и к другим
ситуациям.
Упражнение 8-6
--------------
Функция из стандартной библиотеки CALLOC(N,SIZE) возвра-
щает указатель на "N" объектов размера SIZE, причем соответ-
ствующая память инициализируется на нуль. напишите программу
для CALLOC, используя функцию ALLOC либо в качестве образца,
либо как функцию, к которой происходит обращение.
Упражнение 8-7
---------------
Функция ALLOC принимает затребованный размер, не прове-
ряя его правдоподобности; функция FREE полагает, что тот
блок, который она должна освободить, содержит правильное
значение в поле размера. Усовершенствуйте эти процедуры,
затратив больше усилий на проверку ошибок.
Упражнение 8-8
---------------
Напишите функцию BFREE(P,N), которая включает произволь-
ный блок "P" из "N" символов в список свободных блоков, уп-
равляемый функциями ALLOC и FREE. С помощью функции BFREE
пользователь может в любое время добавлять в свободный спи-
сок статический или внешний массив.