Б. Керриган, Д. Ритчи Язык программирования C. Б. Керниган, Д. зык программирования и . Издание 3е, исправленное Перевод с английского под редакцией Вс. С. Штаркмана СанктПетербург 2003
 Скачать 31.48 Mb.
|
|
Глава 8. Интерфейс с системой UNIX name. Структура, описывающая возвращаемое функцией stat значение, находится в h> и выглядит примерно так: struct stat { dev ino short short short short time_t time_t st_dev; st_ino; st_uid; st_gid; st_rdev; st_size; /• / / / информация из возвращаемая stat */ устройство */ номер inode */ режимные биты */ число связей с файлом */ имя пользователя-собственника */ имя группы собственника */ для специальных файлов */ размер файла в символах */ время последнего использования */ время последней модификации */ время последнего изменения inode */ Большинство этих значений объясняется в комментариях. Типы, подоб- ные dev_t и ino_t, определены в файле h>, который тоже нуж- но включить посредством Элемент содержит набор флажков, составляющих дополнительную информацию о файле. Определения флажков также содержатся нам потребуется только та его часть, которая имеет дело с типом файла: S_IFMT 0160000 0040000 /* S_IFCHR 0020000 /* S_IFBLK 0060000 /* S_IFREG 0100000 тип файла */ каталог */ символьно-ориентированный */ */ обычный */ Теперь мы готовы приступить к написанию программы f size. Если ре- жимные биты полученные от stat, указывают, что файл не яв- ляется каталогом, то можно взять его размер (st_size) и напечатать. Од- нако если файл - каталог, то мы должны обработать все его файлы, каж- дый из которых в свою очередь может быть каталогом. Обработка катало- га - процесс рекурсивный. Программа m a i n просматривает параметры командной строки, переда- вая каждый аргумент функции f «include «include /* флажки чтения и записи */ /* определения типов */ 8.6. Пример. Печать каталогов /* структура, возвращаемая stat */ void fsize(char *); /* печатает размеры файлов */ main(int argc, char { if == 1) /* по умолчанию берется текущий каталог */ else while > 0) fsize(*++argv); return 0; > Функция f size печатает размер файла. Однако, если файл - каталог, она сначала вызывает di чтобы обработать все его файлы. Обрати- те внимание на то, как используются имена флажков S_IFMT и S_IFDIR из h> при проверке, является ли файл каталогом. Здесь нужны скобки, поскольку приоритет оператора & ниже приоритета оператора ==. int stat(char *, struct stat *); void dirwalk(char *, void *)); /* печатает размер файла "name" */ void { struct stat if -1) { fprintf(stderr, "fsize: нет доступа к name); return; } if & == S_IFDIR) fsize); } Функция di rwalk - это универсальная программа, применяющая не- которую функцию к каждому файлу каталога. Она открывает каталог, с помощью цикла перебирает содержащиеся в нем файлы, применяя к каж- дому из них указанную функцию, затем закрывает каталог и осуществля- ет возврат. Так как fsize вызывает rwalk на каждом каталоге, в этих двух функциях заложена косвенная рекурсия. 232 _ Глава 8. Интерфейс с системой UNIX MAX_PATH 1024 /* dirwalk: применяет ко всем файлам из dir */ void *dir, void (*fcn)(char *)) { char *dp; DIR if ((dfd = == NULL) { fprintf(stderr, "dirwalk: не могу открыть dir); return; } while = != NULL) { if == 0 == 0) continue; /* пропустить себя и родителя */ if > "dirwalk: слишком длинное имя dir, dp->name); else { dir, closedir(dfd); } Каждый вызов readdi возвращает указатель на информацию о следующем файле или NULL, если все файлы обработаны. Любой каталог всегда хра- нит в себе информацию о себе самом в файле под именем и о своем родителе в файле под именем их нужно пропустить, иначе программа зациклится. Обратите внимание: код программы этого уровня не зависит от того, как форматированы каталоги. Следующий шаг — представить ми- нимальные версии opendi r, readdi r и closedi r для некоторой конкретной системы. Здесь приведены программы для систем Version 7 и System V UNIX. Они используют информацию о каталоге, хранящуюся в за- головочном файле h>, который выглядит следующим образом: tfifndef DIRSIZ DIRSIZ 14 struct direct /* элемент каталога */ { ino_t /* номер inode */ 8.6. Пример. Печать каталогов 233 char /* длинное имя не имеет */ Некоторые версии системы допускают более длинные имена и имеют бо- лее сложную структуру каталога. Тип ino_t задан с помощью typedef и описывает индекс списка узлов mode. В системе, которой пользуемся мы, этот тип есть unsigned но в других системах он может быть иным, поэтому его лучше определять через Полный набор "системных" типов находится в h>. Функция opendir открывает каталог, проверяет, является ли он дей- ствительно каталогом (в данном случае это делается с помощью систем- ного вызова f stat, который аналогичен stat, но применяется к дескрип- тору файла), запрашивает пространство для структуры каталога и запи- сывает информацию. int fd, struct stat *); /* opendir: открывает каталог для вызовов */ DIR *opendir(char int fd; struct stat stbuf; DIR *dp; if = 0_RDONLY, == -1 fstat(fd, == -1 & (dp = (DIR == NULL) return NULL; dp->fd = fd; return dp; Функция closedi закрывает каталог и освобождает пространство. /* closedir: закрывает каталог, открытый opendir */ void *dp) if (dp) { 234 _ Глава 8. с системой UNIX Наконец, readdi г с помощью read читает каждый элемент каталога. Если некий элемент каталога в данный момент не используется (соответству- ющий ему файл был удален), то номер узла mode у него равен нулю, и дан- ная позиция пропускается. В противном случае номер mode и имя раз- мещаются в статической (static) структуре, и указатель на нее выдается в качестве результата. При каждом следующем обращении новая инфор- мация занимает место предыдущей. /* место расположения структуры каталога */ /* последовательно читает элементы каталога */ Dirent *readdir(DIR *dp) { struct direct /* структура каталога на данной системе */ static d; /* возвращает унифицированную структуру */ while (char *) == { if == 0) /* пустой элемент, не используется */ continue; d.ino = dirbuf DIRSIZ); = /* завершающий */ return &d; } return NULL; Хотя программа fsize - довольно специализированная, она иллюс- трирует два важных факта. Первый: многие программы не являются "си- стемными"; они просто используют информацию, которую хранит опера- ционная система. Для таких программ существенно то, что представле- ние информации сосредоточено исключительно в стандартных заголовоч- ных файлах. Программы включают эти а не держат объявления в себе. Второе наблюдение заключается в том, что при старании систем- но-зависимым объектам можно создать интерфейсы, которые сами не бу- дут системно-зависимыми. Хорошие тому примеры - функции стандарт- ной библиотеки. Упражнение 8.5. Модифицируйте таким образом, чтобы можно было печатать остальную информацию, содержащуюся в узле mode, 8.7. Пример. Распределитель памяти 235 8.7. Пример. Распределитель памяти В главе 5 был описан простой распределитель памяти, основанный на принципе стека. Версия, которую мы напишем здесь, не имеет ограни- чений: вызовы и могут выполняться в любом порядке; malloc делает запрос в операционную систему на выделение памяти тогда, когда она требуется. Эти программы иллюстрируют приемы, позволяющие по- лучать машинно-зависимый код сравнительно машинно-независимым способом, и, кроме того, они могут служить примером применения таких средств языка, как структуры, объединения И Никакого ранее скомпилированного массива фиксированного раз- мера, из которого выделяются куски памяти, не будет. Функция malloc запрашивает память у операционной системы по мере надобности. По- скольку и другие действия программы могут вызывать запросы памяти, которые удовлетворяются независимо от этого распределителя памяти, пространство, которым заведует malloc, не обязательно представляет со- бой связный кусок памяти. Поэтому свободная память хранится в виде списка блоков. Каждый блок содержит размер, указатель на следующий блок и само пространство. Блоки в списке хранятся в порядке возраста- ния адресов памяти, при этом последний блок (с самым большим адре- сом) указывает на первый. список ков X — Зс зан зан Ц зан свободное пространство, находящееся в распоряжении функции malloc выделенное функцией malloc пространство (занято) пространство, не находящееся в распоряжении функции malloc При возникновении запроса на память просматривается список сво- бодных блоков, пока не обнаружится достаточно большой блок. Такой алгоритм называется "поиском первого подходящего" в алгоритма "поиска наилучшего подходящего", который ищет наименьший блок из числа удовлетворяющих запросу. Если размер блока в точности 236 _ Глава 8. Интерфейс с системой UNIX соответствует требованиям, то такой блок исключается из списка и отда- ется в пользование. Если размер блока больше, чем требуется, от него от- резается нужная часть - она отдается пользователю, а ненужная оставля- ется в списке свободных блоков. Если блока достаточного размера не ока- залось, то у операционной системы запрашивается еще один большой ку- сок памяти, который присоединяется к списку свободных блоков. Процедура освобождения сопряжена с прохождением по списку сво- бодных блоков, поскольку нужно найти подходящее место для освобож- даемого блока. Если подлежащий освобождению блок примыкает с ка- кой-то стороны к одному из свободных блоков, то он объединяется с ним в один блок большего размера, чтобы по возможности уменьшить раздроб- ленность (фрагментацию) памяти. Выполнение проверки, примыкают ли блоки друг к другу, не составляет труда, поскольку список свободных блоков всегда упорядочен по возрастанию адресов. Существует проблема, о которой мы уже упоминали в главе 5, состоя- щая в том, что память, выдаваемая функцией должна быть соот- ветствующим образом выровнена с учетом объектов, которые будут в ней храниться. Хотя машины и отличаются друг от друга, но для каждой из них существует тип, предъявляющий самые большие требования на вы- равнивание, и, если по некоему адресу допускается размещение объекта этого типа, то по нему можно разместить и объекты всех других типов. На некоторых машинах таким самым "требовательным" типом является double, на других это может быть int или long. Свободный блок содержит указатель на следующий блок в списке, свой размер и собственно свободное пространство. Указатель и размер представ- ляют собой управляющую информацию и образуют так называемый "заго- ловок". Чтобы упростить выравнивание, все блоки создаются кратными размеру заголовка, а заголовок соответствующим образом выравнивается. Этого можно достичь, сконструировав объединение, которое будет со- держать соответствующую заголовку структуру и самый требовательный в отношении выравнивания тип. Для конкретности мы выбрали тип long. typedef long Align; /* для выравнивания по границе long */ union header { /* заголовок блока: */ struct { union header *ptr; /* в списке свободных */ unsigned size; /* размер этого блока */ } s; Align x; /* принудительное выравнивание блока */ typedef union header Header; 8.7. Пример. Распределитель памяти 237 Поле A l i g n нигде не используется; оно необходимо только для того, что- бы каждый заголовок был выровнен по самому "худшему" варианту гра- ницы. Затребованное число символов округляется в ос до целого числа единиц памяти размером в заголовок (именно это число и записывается в поле (размер) в заголовке); кроме того, в блок входит еще одна еди- ница памяти - сам заголовок. Указатель, возвращаемый функцией указывает на свободное а не на заголовок. Со свободным пространством пользователь может делать что угодно, но, если он будет писать что-либо за его пределами, то, вероятно, список разрушится. указатель на следующий свободный блок размер блок, возвращаемый функцией malloc Поскольку память, управляемая функцией malloc, не обладает связно- стью, размеры блоков нельзя вычислить по указателям, и поэтому без поля, хранящего размер, нам не обойтись. Для организации начала работы используется переменная base. Если f геер есть NULL (как это бывает при первом обращении к malloc), создает- ся "вырожденный" список свободного пространства; он содержит один блок нулевого размера с указателем на самого себя. Поиск свободного блока подходящего размера начинается с этого указателя (f т. е. с по- следнего найденного блока; такая стратегия помогает поддерживать спи- сок однородным. Если найденный блок окажется слишком большим, пользователю будет отдана его хвостовая часть; при этом потребуется только уточнить его размер в заголовке найденного свободного блока. В любом случае возвращаемый пользователю указатель является адре- сом свободного пространства, размещающегося в блоке непосредственно за заголовком. static Header base; /* пустой список для нач. запуска */ static Header = NULL; /* начало в списке своб. блоков */ /* malloc: универсальный распределитель памяти */ void nbytes) { Header *prevp; Header unsigned nunits; 238 _ Глава 8. Интерфейс с системой UNIX nunits = (nbytes + - 1) / + 1; if ((prevp = freep) == NULL) { /* списка памяти еще нет */ = freep = prevp = = 0; } for (p = ; prevp = p, p = p->s.ptr) { if >= nunits) { /* достаточно большой */ if == nunits) /* точно нужного размера */ prevp->s.ptr = else { /* отрезаем */ -= nunits; p += = nunits; . . freep = prevp; return (void } if (p == freep) /* прошли полный цикл по списку */ = raorecore(nunits)) == NULL) return NULL; /* больше памяти нет */ Функция mo reco re получает память от операционной системы. Детали того, как это делается, могут не совпадать в различных системах. Так как запрос памяти у системы - сравнительно дорогая операция, мы бы не хо- тели для этого каждый раз обращаться к Поэтому используется функция которая запрашивает не менее единиц памяти; этот больший кусок памяти будет "нарезаться" потом по мере надобнос- ти. После установки в поле размера соответствующего значения функ- ция mo reco re вызывает функцию f и тем самым включает полученный кусок в список свободных областей памяти. NALLOC 1024 /* миним. число единиц памяти для запроса */ /* morecore: запрашивает у системы дополнительную память */ static Header * nu) { char *cp, Header *up; if (nu < NALLOC) nu NALLOC; 8.7. Пример. Распределитель памяти 239 ср = * if (cp == (char *) -1) /* больше памяти нет */ return NULL; up = (Header *) cp; = nu; free((void return freep; > Системный вызов sbrk(n) в возвращает указатель на п байт па- мяти или если требуемого пространства не оказалось, хотя было бы лучше, если бы в последнем случае он возвращал NULL. Константу -1 не- обходимо привести ктипу char *, чтобы ее можно было сравнить с возвра- щаемым значением. Это еще один пример того, как операция приведения типа делает функцию относительно независимой от конкретного пред- ставления указателей на различных машинах. Есть, однако, одна "некор- ректность", состоящая в том, что сравниваются указатели на различные блоки, выдаваемые функцией sbrk. Такое сравнение не гарантировано стандартом, который позволяет сравнивать указатели лишь в пределах одного и того же массива. Таким образом, эта версия malloc только на тех машинах, в которых допускается сравнение любых указателей. В заключение рассмотрим функцию f Она просматривает список свободной памяти, начиная с f reep, чтобы подыскать место для вставля- емого блока. Искомое место может оказаться или между блоками, или в начале списка, или в его конце. В любом случае, если подлежащий ос- вобождению блок примыкает к соседнему блоку, он объединяется с ним в один блок. О чем еще осталось позаботиться, - так это о том, чтобы ука- затели указывали в нужные места и размеры блоков были правильными. /* free: включает блок в список свободной памяти */ void free(void *ap) { Header *bp, *p; bp = (Header *)ap -1; /* указатель на заголовок блока */ for > p && bp < p->s.ptr); p = if (p >= p->s.ptr (bp > p bp < break; /* освобождаем блок в начале или в конце */ if (bp + == p->s.ptr) { /* слить с верхним */ += /* соседом */ bp->s.ptr = } else 240 Глава 8. Интерфейс с системой UNIX bp->s. = p->s. if (p == bp) { /* слить с нижним соседом */ += p->s. = } else = bp; freep = p; } Хотя выделение памяти по своей сути - машинно-зависимая пробле- ма, с ней можно справиться, что и иллюстрирует приведенная програм- ма, в которой машинная зависимость упрятана в очень маленькой ее час- ти. Что касается проблемы мы разрешили ее с помощью typedef и union (предполагается, что дает подходящий в смысле вы- равнивания указатель). Операции приведения типов позволяют нам сде- лать явными преобразования типов и даже справиться с плохо спроекти- рованным интерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общий подход применим и в других ситуациях. Упражнение 8.6. Стандартная функция c a l l o c ( n , size) возвращает указатель на п элементов памяти размера size, заполненных нулями. Напишите свой вариант пользуясь функцией ос или модифицируя последнюю. Упражнение 8.7. Функция допускает любой размер, никак не про- веряя его на правдоподобие; f гее предполагает, что размер освобождаемого блока — правильный. Усовершенствуйте эти программы таким образом, чтобы они более тщательно контролировали ошибки. Упражнение 8.8. Напишите программу освобождающую произвольный блок р, состоящий из п символов, путем включения в список свободной памяти, поддерживаемый функциями malloc и С помощью bf пользователь должен иметь возможность в любое время добавить в список свободной памяти статический или внешний массив. |