--------------
Перепишите функции 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 обеспечивает подходящий указатель). Переводы типов
организуют выполнение явного преобразования типов и даже
справляются с неудачно разработанным системным интерфейсом.
И хотя рассмотренные здесь подробности связаны с распределе-
нием памяти, общий подход равным образом применим и к другим
ситуациям.
