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