· 177 -
где содержится вся информация о файле, за исключением его
имени. Запись в справочнике состоит только из двух элемен-
тов: номера 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.
·
178 -
#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.
· 179 -
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-узловое число равно нулю, и эта позиция пропускается.
Каждый справочник также содержит запись в самом себе, назы-
ваемую “.”, и о своем родителе, “..”; они, очевидно, также
должны быть пропущены, а то программа будет работать весьма
и весьма долго.
· 180 -
Хотя программа FSIZE довольно специализированна, она все
же демонстрирует пару важных идей. во-первых, многие прог-
раммы не являются “системными программами”; они только ис-
пользуют информацию, форма или содержание которой определя-
ется операционной системой. Во-вторых, для таких программ
существенно, что представление этой информации входит только
в стандартные “заголовочные файлы”, такие как STAT.H и
DIR.H, и что программы включают эти файлы, а не помещают
фактические описания внутрь самих программ.
8.7. Пример - распределитель памяти.
В главе 5 мы написали бесхитростный вариант функции
ALLOC. Вариант, который мы напишем теперь, не содержит огра-
ничений: обращения к функциям ALLOC и FREE могут перемежать-
ся в любом порядке; когда это необходимо, функция ALLOC об-
ращается к операционной системе за дополнительной памятью.
Кроме того, что эти процедуры полезны сами по себе, они так-
же иллюстрируют некоторые соображения, связанные с написани-
ем машинно-зависимых программ относительно машинно-независи-
мым образом, и показывают практическое применение структур,
объединений и конструкций TYPEDEF.
Вместо того, чтобы выделять память из скомпилированного
внутри массива фиксированного размера, функция ALLOC будет
по мере необходимости обращаться за памятью к операционной
системе. Поскольку различные события в программе могут тре-
бовать асинхронного выделения памяти, то память, управляемая
ALLOC, не может быть непрерывной. В силу этого свободная па-
мять хранится в виде цепочки свободных блоков. Каждый блок
включает размер, указатель следующего блока и саму свободную
память. Блоки упорядочиваются в порядке возрастания адресов
памяти, причем последний блок (с наибольшим адресом) указы-
вает на первый, так что цепочка фактически оказывается коль-
цом.
При поступлении запроса список свободных блоков просмат-
ривается до тех пор, пока не будет найден достаточно большой
блок. Если этот блок имеет в точности требуемый размер, то
он отцепляется от списка и передается пользователю. Если же
этот блок слишком велик, то он разделяется, нужное количест-
во передается пользователю, а остаток возвращается в свобод-
ный список. Если достаточно большого блока найти не удается,
то операционной системой выделяется новый блок, который
включается в список свободных блоков; затем поиск возобнов-
ляется.
Освобождение памяти также влечет за собой просмотр сво-
бодного списка в поиске подходящего места для введения осво-
божденного блока. Если этот освободившийся блок с какой-либо
стороны примыкает к блоку из списка свободных блоков, то они
объединяются в один блок большего размера, так что память не
становится слишком раздробленной. Обнаружить смежные блоки
просто, потому что свободный список содержится в порядке
возрастания адресов.
· 181 -
Одна из проблем, о которой мы упоминали в главе 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;
\)
· 182 -
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, то создается вырожденный свободный список: он состоит