Kernighan, B. W. and Ritchie, D. M. "The 'C' Programming Language"; Chapter 8
Интерфейс системы UNIX
Материал этой главы относится к интерфейсу между с-программамии операционной системой UNIX. Так как большинство пользователейязыка "Си" работают на системе UNIX, эта глава окажется полезнойдля большинства читателей. Даже если вы используете с-компилятор надругой машине, изучение приводимых здесь примеров должно помочьвам глубже проникнуть в методы программирования на языке "C".
Эта глава делится на три основные части: ввод/вывод, системафайлов и распределение памяти. Первые две части предполагаютнебольшое знакомство с внешними характеристиками системы UNIX.
В главе 7мы имели дело с системным интерфейсом, который одинаковдля всего многообразия операционных систем. На каждой конкретнойсистеме функции стандартной библиотеки должны быть написаны в терминахввода-вывода, доступных на данной машине. В следующих несколькихразделах мы опишем основную систему связанных с вводом и выводомточек входа операционной системы UNIX и проиллюстрируем, как с ихпомощью могут быть реализованы различные части стандартнойбиблиотеки.
Содержание
- 8.1. Дескрипторы файлов.
- 8.2. Низкоуровневый ввод/вывод - операторы read и write.
- 8.3. Открытие, создание, закрытие и расцепление (unlink).
- 8.4. Произвольный доступ - seek и lseek.
- 8.5. Пример - реализация функций fopen и getc.
- 8.6. Пример - распечатка справочников
- 8.7. Пример - распределитель памяти.
- 8.2. Низкоуровневый ввод/вывод - операторы read и write.
Дескрипторы файлов.
В операционной системе UNIX весь ввод и вывод осуществляется посредствомчтения файлов или их записи, потому что все периферийные устройства,включая даже терминал пользователя, являются файлами определеннойфайловой системы. Это означает, что один однородный интерфейс управляетвсеми связями между программой и периферийными устройствами.
В наиболее общем случае перед чтением из файла или записью в файлнеобходимо сообщить системе о вашем намерении; этот процесс называется"открытием" файла. Система выясняет,имеете ли вы право поступать такимобразом (существует ли этот файл? Имеется ли у вас разрешение наобращение к нему?), и если все в порядке, возвращает в программунебольшое положительное целое число, называемое дескриптором файла.Всякий раз, когда этот файл используется для ввода или вывода, дляидентификации файла употребляется дескриптор файла, а не его имя. (здесьсуществует примерная аналогия с использованием read (5,...) и write(6,...) в фортране). Вся информация об открытом файле содержится всистеме; программа пользователя обращается к файлу только черездескриптор файла.
Для удобства выполнения обычных операций ввода и вывода с помощьютерминала пользователя существуют специальные соглашения. Когдаинтерпретатор команд ("shell") прогоняет программу, он открывает трифайла, называемые стандартным вводом, стандартным выводом истандартным выводом ошибок, которые имеют соответственно числа 0, 1 и2 в качестве дескрипторов этих файлов. В нормальном состоянии все онисвязаны с терминалом, так что если программа читает с дескрипторомфайла 0 и пишет с дескрипторами файлов 1 и 2, то она может осуществлятьввод и вывод с помощью терминала, не заботясь об открытиисоответствующих файлов.
Пользователь программы может перенаправлять ввод и вывод на файлы,используя операции командного интерпретатора shell "<" и ">" :
prog < infile > outfileВ этом случае интерпретатор команд shell изменит присваивание поумолчанию дескрипторов файлов 0 и 1 с терминала на указанные файлы.Нормально дескриптор файла 2 остается связанным с терминалом, так чтосообщения об ошибках могут поступать туда. Подобные замечаниясправедливы и тогда, когда ввод и вывод связан с каналом. Следуетотметить, что во всех случаях прикрепления файлов изменяютсяинтерпретатором shell, а не программой. Сама программа, пока онаиспользует файл 0 для ввода и файлы 1 и 2 для вывода, не знает ниоткуда приходит ее ввод, ни куда поступает ее выдача.
Низкоуровневый ввод/вывод - операторы read и write.
Самый низкий уровень ввода/вывода в системе UNIX не предусматриваетни какой-либо буферизации, ни какого-либо другого сервиса; он посуществу является непосредственным входом в операционную систему.Весь ввод и вывод осуществляется двумя функциями: read и write.Первым аргументом обеих функций является дескриптор файла. Вторымаргументом является буфер в вашей программе, откуда или куда должныпоступать данные. Третий аргумент - это число подлежащих пересылкебайтов. Обращения к этим функциям имеют вид:
n_read=read(fd,buf,n); n_written=write(fd,buf,n);При каждом обращении возвращается счетчик байтов, указывающийфактическое число переданных байтов. При чтении возвращенное числобайтов может оказаться меньше, чем запрошенное число. Возвращенноенулевое число байтов означает конец файла, а "-1" указывает на наличиекакой-либо ошибки. При записи возвращенное значение равно числуфактически записанных байтов; несовпадение этого числа с числомбайтов, которое предполагалось записать, обычно свидетельствует обошибке.
Количество байтов, подлежащих чтению или записи, может быть совершеннопроизвольным. Двумя самыми распространенными величинами являются "1",которая означает передачу одного символа за обращение (т.е. безиспользования буфера), и "512", которая соответствует физическомуразмеру блока на многих периферийных устройствах. Этот последнийразмер будет наиболее эффективным, но даже ввод или вывод по одномусимволу за обращение не будет необыкновенно дорогим.
Об'единив все эти факты, мы написали простую программу длякопирования ввода на вывод, эквивалентную программе копировки файлов,написанной в главе 1.На системе UNIX эта программа будет копироватьчто угодно куда угодно, потому что ввод и вывод могут бытьперенаправлены на любой файл или устройство.
#define BUFSIZE 512 /*best size for pdp-11 UNIX*/ main() /*copy input to Dutput*/ { char buf[BUFSIZE]; int n; while( (n = read( 0, buf, BUFSIZE)) > 0 ) write( 1, buf, n); }Если размер файла не будет кратен BUFSIZE, то при некотором обращениик read будет возвращено меньшее число байтов, которые затем записываютсяс помощью write; при следующем после этого обращении к read будетвозвращен нуль.Поучительно разобраться, как можно использовать функции read и writeдля построения процедур более высокого уровня, таких как getchar,putchar и т.д. вот, например, вариант функции getchar, осуществляющийввод без использования буфера.
#define cmask 0377 /*for making char's > 0*/ getchar() /*unbuffered single character input*/ { char c; return((read(0,&c,1)>0 7 & cmask : EOF); }Переменная "c" должна быть описана как char, потому что функцияread принимает указатель на символы. Возвращаемый символ должен бытьмаскирован числом 0377 для гарантии его положительности; в противномслучае знаковый разряд может сделать его значение отрицательным.(Константа 0377 подходит для эвм pdp-11, но не обязательно для другихмашин).Второй вариант функции getchar осуществляет ввод большими порциями, авыдает символы по одному за обращение.
#define cmask 0377 /*for making char's>0*/ #define BUFSIZE 512 getchar() /*buffered version*/ { static char buf[BUFSIZE]; static char *bufp = buf; static int n = 0; if (n==0) { /*buffer is empty*/ n=read(0,buf,BUFSIZE); bufp = buf; } return((--n>=0) ? *bufp++ & cmask : EOF); }Открытие, создание, закрытие и расцепление (unlink).
Кроме случая, когда по умолчанию определены стандартные файлы ввода,вывода и ошибок, вы должны явно открывать файлы, чтобы затем читатьиз них или писать в них. Для этой цели существуют две точки входа:open и creat.
Функция open весьма сходна с функцией fopen, рассмотренной вглаве 7,за исключением того, что вместо возвращения указателя файла онавозвращает дескриптор файла, который является просто целым типа int.
int fd; fd=open(name,rwmode);Как и в случае fopen, аргумент name является символьной строкой,соответствующей внешнему имени файла. Однако аргумент, определяющийрежим доступа, отличен: rwmode равно: 0 - для чтения, 1 - длязаписи, 2 - для чтения и записи. Если происходит какая-то ошибка,функция open возвращает "-1"; в противном случае она возвращаетдействительный дескриптор файла.
Попытка открыть файл, который не существует, является ошибкой. Точкавхода creat предоставляет возможность создания новых файлов илиперезаписи старых. В результате обращения
fd=creat(name,pmode);возвращает дескриптор файла, если оказалось возможным создать файл сименем name, и "-1" в противном случае. Если файл с таким именем ужесуществует, creat усечет его до нулевой длины; создание файла, которыйуже существует, не является ошибкой.
Если файл является совершенно новым, то creat создает его с определеннымрежимом защиты, специфицируемым аргументом pmode. В системе файлов наUNIX с файлом связываются девять битов защиты информации, которыеуправляют разрешением на чтение, запись и выполнение для владельцафайла, для группы владельцев и для всех остальных пользователей.Таким образом, трехзначное восьмеричное число наиболее удобно дляспецификации разрешений. Например, число 0755 свидетельствует оразрешении на чтение, запись и выполнение для владельца и оразрешении на чтение и выполнение для группы и всех остальных.
Для иллюстрации ниже приводится программа копирования одного файлав другой, являющаяся упрощенным вариантом утилиты ср системы 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 ( из данного справочного файла. Файл может быть сцепленс другим справочником, возможно,под другим именем - примеч.переводчика).
Произвольный доступ - seek и lseek.
Нормально при работе с файлами ввод и вывод осуществляетсяпоследовательно: при каждом обращении к функциям 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 и которое осуществляет передвижение на желаемыйбайт внутри блока.
Пример - реализация функций fopen и getc.
Давайте теперь на примере реализации функций 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;extern 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, и тем самым гарантирует положительность всехсимволов.
Хотя мы не собираемся обсуждать какиe-либо детали, мы все же включилисюда определение макроса 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); if(--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, _write, 1 }, /* stdout */ { NULL, 0, _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/types.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 техт 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 256main(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 обеспечивает подходящий указатель).Переводы типов организуют выполнение явного преобразования типов идаже справляются с неудачно разработанным системным интерфейсом.И хотя рассмотренные здесь подробности связаны с распределениемпамяти, общий подход равным образом применим и к другим ситуациям.