Книга: Linux программирование в примерах

8.5. Обход дерева файлов: GNU du

8.5. Обход дерева файлов: GNU du

GNU версия du в GNU Coreutils использует nftw() для обхода одной или более иерархии файлов, собирая и выводя сведения, касающиеся количества используемого дискового пространства. У нее большое число опций, которые управляют ее поведением но отношению к символическим ссылкам, форматом вывода чисел и т.д. Это делает разбор кода труднее, чем могло бы быть при более простой версии. (Однако, мы не собираемся позволить этому остановить нас.) Вот сводка опций du, которые вскоре будут полезны, когда мы рассмотрим код.

$ du --help
Usage: du [OPTION]... [FILE]...
  Дает сводку использования диска для каждого FILE,
  рекурсивно для каталогов.
  Обязательные для длинных опций аргументы являются обязательными
  также и для коротких опций.
-a,  --all              записать число всех файлов, а не только
                        каталогов
     --apparent-size    вывести видимые размеры, а не использование
                        диска; хотя видимый размер обычно меньше, он
                        может быть и больше из-за дыр в файлах,
                        внутренней фрагментации, косвенных блоков и т.п.
-В,  --block-size=SIZE  использовать блоки размером SIZE байтов
-b,  --bytes            эквивалентно '--apparent-size --block-size=1'
-с,  --total            выводит итоговую сумму
-D,  --dereference-args разыменовывать FILE, которые являются
                        символическими ссылками
-h,  --human-readable   вывести размеры в удобном для восприятия
                        формате (например, 1K 234М 2G)
-Н,  --si               так же, но использовать степени 1000, не 1024
-k                      подобно --block-size=1K
-l,  --count-links      считать размеры несколько раз при прямых
                        ссылках
-L,  --dereference      разыменовывать все символические ссылки
-S,  --separate-dirs    не включать размер подкаталогов
-s,  --summarize        отобразить для каждого аргумента лишь итоги
-х,  --one-file-system  пропускать каталоги на различных файловых
                        системах
-X   --exclude-         исключить файлы, подходящие под любой
FILE from=FILE          образец в FILE
     --exclude=PATTERN  исключить файлы, соответствующие PATTERN
     --max-depth=N      вывести итог для каталога (или файла, с --all)
                        только если он находится на N или менее уровней
                        глубже аргумента командной строки;
     --max-depth=0      то же самое, что и --summarize
     --help             отобразить экран справки и выйти
     --version          вывести сведения о версии и выйти
SIZE может быть (или может быть целым, за которым
может следовать это) одним из
следующих: kB 1000, K 1024, MB 1 000 000, M 1 048 576 и т.д.
для G, T, Р, E, Z, Y.

Чтобы еще больше усложнить дело, du использует частную версию nftw(), у которой есть несколько расширений. Сначала имеются дополнительные значения флагов для функции обратного вызова:

FTW_DCHP

Это значение означает, что nftw() не может выполнять 'chdir("..")'.

FTW_DCH

Это значение означает, что nftw() не может использовать chdir() для перехода в сам каталог.

FTW_DPRE

Частная nftw() вызывает для каталогов функцию обратного вызова дважды. Это значение используется при первой встрече с каталогом. После обработки всех нижележащих объектов каталога используется стандартное значение FTW_DP.

Частная nftw() добавляет также в struct FTW новый член, int skip. Если текущий объект является каталогом и функция обратного вызова устанавливает в поле skip ненулевое значение, nftw() не будет больше обрабатывать этот каталог. (Функция обратного вызова должна установить skip таким образом, когда flag равен FTW_DPRE; делать это для FTW_DP слишком поздно.)

С этим объяснением за поясом, вот функция process_file() из du.c. Номера строк приведены относительно начала функции:

1  /* Эта функция вызывается один раз для каждого объекта файловой
2     системы, с которой сталкивается nftw. nftw осуществляет сначала
3     поиск вглубь. Эта функция знает это и собирает итоги для каталогов
4     на основе изменений в глубине текущего элемента. */
5
6  static int
7  process_file(const char *file, const struct stat *sb,
8   int file_type, struct FTW *info)
9  {
10  uintmax_t size;
11  uintmax_t size_to_print;
12  static int first_call = 1;
13  static size_t prev_level;
14  static size_t n_alloc;
15  static uintmax_t *sum_ent;
16  static uintmax_t *sum_subdir;
17  int print = 1;
18
19  /* Всегда определяйте info->skip перед возвратом. */
20  info->skip = excluded_filename(exclude, file + info->base);
    /* Для --exclude */

Эта функция делает многое, поскольку ей приходится реализовать все опции du. Строка 17 устанавливает print в true (1); по умолчанию выводятся сведения о каждом файле. Дальнейший код устанавливает ее при необходимости в false (0).

Строка 20 устанавливает info->skip на основе опции --exclude. Обратите внимание, что это исключает подкаталоги, если каталог совпадает с шаблоном для --exclude.

22 switch (file_type)
23 {
24 case FTW_NS:
25  error (0, errno, _("cannot access %s"), quote(file));
26  G_fail = 1; /* Установить глобальную переменную для дальнейшего */
27  return 0; /* Вернуть 0 для продолжения */
28
29 case FTW_DCHP:
30  error(0, errno, _("cannot change to parent of directory %s"),
31  quote(file));
32  G_fail = 1;
33  return 0;
34
35 case FTW_DCH:
36  /* Нельзя просто вернуться, поскольку, хотя nftw не может войти в
37     каталог, она может использовать stat, постольку у нас есть размер */
38  error(0, errno, _("cannot change to directory %s"), quote(file));
39  G_fail = 1;
40  break;
41
42 case FTW_DNR:
43  /* Нельзя просто вернуться, поскольку, хотя nftw не может прочесть
44     каталог, она может вызвать stat, постольку у нас есть размер. */
45  error(0, errno, _("cannot read directory %s"), quote(file));
46  G_fail = 1;
47  break;
48
49 default:
50  break;
51 }
52
53 /* Если это первая (предварительная) встреча с каталогом,
54    сразу вернуться. */
55 if (file_type == FTW_DPRE)
56  return 0;

Строки 22–51 являются стандартным оператором switch. Ошибки, для которых нет информации о размере, устанавливают глобальную переменную G_fail в 1 и возвращают 0, чтобы продолжить обработку (см строки 24–27 и 29–33). Ошибки, для которых есть размер, также устанавливают G_fail, но затем прерывают switch для того, чтобы обработать статистику (см. строки 35–40 и 42–47).

Строки 55–56 сразу завершают функцию, если это первая встреча с каталогом

58 /* Если файл исключается или если он уже учитывался
59    через прямую ссылку, не включать его в сумму. */
60 if (info->skip,
61  || (!opt_count_all
62  && 1 < sb->st_nlink
63  && hash_ins(sb->st_ino, sb->st_dev)))
64 {
65  /* Заметьте, мы не должны здесь просто возвращаться.
66     Нам все еще нужно обновить prev_level и, возможно, передать
67     некоторые суммы выше по иерархии. */
68  size = 0;
69  print = 0;
70 }
71 else
72 {
73  size = (apparent_size
74    ? sb->st_size
75    : ST_NBLOCKS (*sb) * ST_NBLOCKSIZE);
76  }

Теперь становится интересно. По умолчанию du подсчитывает пространство, занимаемое прямыми ссылками, лишь одни раз. Опция --count-links заставляет ее подсчитывать пространство для каждой ссылки; переменная opt_count_all равна true, когда указана --count-links. Для отслеживания ссылок du содержит хэш-таблицу[87] уже встречавшихся пар (устройство, индекс).

Строки 60–63 проверяют, следует ли не включать файл в подсчет, либо из-за того, что он был исключен (info->skip равно true, строка 60), либо потому что не была указана --count-links (строка 61) и у файла несколько ссылок (строка 62) и файл уже находится в хеш-таблице (строка 63). В этом случае размер устанавливается в 0, поэтому он не входит в конечную сумму, a print также устанавливается в false (строки 68–69).

Если ни одно из этих условий не отмечается, размер вычисляется либо в соответствии с размером в struct stat, либо в соответствии с числом блоков диска (строки 73–75) Это решение основывается на переменной apparent_size, которая установлена при использовании опции --apparent-size.

78 if (first_call)
79 {
80  n_alloc = info->level + 10; /* Allocate arrays */
81  sum_ent = XCALLOC(uintmax_t, n_alloc); /* to hold sums */
82  sum_subdir = XCALLOC(uintmax_t, n_alloc);
83 }
84 else
85 {
86  /* FIXME: Стыдно, что нам нужно приводить к типу size_t для избежания
87     предупреждений gcc о 'сравнении между знаковым и беззнаковым'.
88     Возможно, неизбежно, при условии, что члены структуры FTW
89     имеют тип 'int' (исторически), так как мне нужно, чтобы переменные
90     вроде n_alloc и prev_level имели осмысленные типы. */
91  if (n_alloc <= (size_t)info->level)
92  {
93   n_alloc = info->level * 2; /* Удвоить сумму */
94   sum_ent = XREALLOC(sum_ent, uintmax_t, realloc); /* И выделить повторно */
95   sum_subdir = XREALLOC(sum_subdir, uintmax_t, n_alloc);
96  }
97 }
98
99 size_to_print = size;

Строки 78–97 управляют динамической памятью, используемой для хранения статистики о размере файла, first_call является статической переменной (строка 12), которая равна true при первом вызове process_file(). В этом случае вызывается calloc() (через упаковывающий макрос в строках 81–82; это обсуждалось в разделе 3.2.1.8 «Пример чтение строк произвольной длины»). Остальную часть времени first_call равно false, и используется realloc() (снова через упаковывающий макрос, строки 91–96).

Строка 99 заносит значение size в size_to_print; эта переменная может обновляться в зависимости от того, должна ли она включать размеры дочерних элементов. Хотя size могла бы использоваться повторно, отдельная переменная упрощает чтение кода.

101 if (!first_call)
102 {
103  if ((size_t)info->level == prev_level)
104  {
105   /* Обычно самый частый случай. Ничего не делать. */
106  }
107  else if ((size_t)info->level > prev_level)
108  {
109   /* Нисхождение по иерархии.
110      Очистить аккумуляторы для *всех* уровней между prev_level
111      и текущим. Глубина может значительно меняться,
112      например, от 1 до 10. */
113   int i;
114   for (i = prev_level +1; i <= info->level; i++)
115    sum_ent[i] = sum_subdir[i] = 0;
116  }
117  else /* info->level < prev_level */
118  {
119   /* Восхождение по иерархии.
120      nftw обрабатывает каталог лишь после всех элементов,
121      в которых был обработан каталог. Когда глубина уменьшается,
122      передать суммы от детей (prev_level) родителям.
123      Здесь текущий уровень всегда меньше, чем
124      предыдущий. */
125   assert (<size_t) info->level == prev_level - 1);
126   size_to_print += sum_ent[prev_level];
127   if (!opt_separate_dirs)
128    size_to_print += sum_subdir[prev_level];
129   sum_subdir[info->level] += (sum_ent[prev_level]
130    + sum_subdir[prev_level]);
131  }
132 }

Строки 101–132 сравнивают текущий уровень с предыдущим. Возможны три случая.

Уровни те же самые

В этом случае нет необходимости беспокоиться о статистике дочерних элементов. (Строки 103–106.)

Текущий уровень выше предыдущего

В этом случае мы спустились по иерархии, и статистику нужно восстановить (строки 107–116). Термин «аккумулятор» в комментарии подходящий: каждый элемент аккумулирует общее дисковое пространство, использованное на этом уровне. (На заре вычислительной техники регистры центрального процессора часто назывались «аккумуляторами».)

Текущий уровень ниже предыдущего

В этом случае мы завершили обработку всех дочерних элементов каталога и только что вернулись обратно в родительский каталог (строки 117–131). Код обновляет суммы, включая size_to_print.

134 prev_level = info->level; /* Установить статические переменные */
135 first_call = 0;
136
137 /* Включить элемент каталога в общую сумму для содержащего
138    каталога, если не указана --separate-dirs (-S). */
139 if (!(opt_separate_dirs && IS_FTW_DIR_TYPE(file_type)))
140  sum_ent[info->level] += size;
141
142 /* Даже если каталог нельзя прочесть или перейти в него,
143    включить его размер в общую сумму, ... */
144 tot_size += size;
145
146 /* ...но не выводить для него итог, поскольку без размера(-ов)
147    потенциальных элементов, это может сильно запутывать. */
148 if (file_type == FTW_DNR || file_type == FTW_DCH)
149  return 0;
150
151 /* Если мы не считаем элемент, например, потому что это прямая
152    ссылка на файл, который уже посчитан (и --count-links), не
153    выводить для него строку. */
154 if (!print)
155  return 0;

Строки 134–135 устанавливают статические переменные prev_level и first_call таким образом, что они содержат правильные значения для последующего вызова process_file(), гарантируя, что весь предыдущий код работает правильно.

Строки 137–144 выверяют статистику на основе опций и типа файла. Комментарии и код достаточно просты. Строки 146–155 сразу завершают функцию, если сведения не должны выводиться.

157  /* FIXME: Это выглядит подозрительно годным для упрощения. */
158  if ((IS_FTW_DIR_TYPE(file_type) &&
159   (info->level <= max_depth || info->level == 0))
160   || <(opt_all && info->level <= max_depth) || info->level == 0))
161  {
162   print_only_size(size_to_print);
163   fputc('t', stdout);
164   if (arg_length)
165   {
166    /* Вывести имя файла, но без суффикса каталога '.' или '/.'
167       который мы, возможно, добавили в main. */
168    /* Вывести все до добавленной нами части. */
169    fwrite(file, arg_length, 1, stdout);
170    /* Вывести все после добавленного нами. */
171    fputs(file + arg_length + suffix_length
172     + (file[arg_length + suffix_length] == '/'), stdout);
173   }
174   else
175   {
176    fputs(file, stdout);
177   }
178   fputc('n', stdout);
179   fflush(stdout);
180  }
181
182  return 0;
183 }

Условие в строках 158–160 сбивает с толку, и комментарий в строке 157 указывает на это. Условие утверждает: «Если (1a) файл является каталогом и (1b) уровень меньше максимального для вывода (переменные — -max-depth и max_depth) или нулевой, или (2a) должны быть выведены все файлы и уровень меньше, чем максимальный для вывода, или (2b) уровень нулевой», тогда вывести файл. (Версия du после 5.0 использует в этом случае несколько менее запутанное условие.)

Строки 162–179 осуществляют вывод. Строки 162–163 выводят размер и символ TAB Строки 164–173 обрабатывают специальный случай. Это объяснено далее в du.c, в строках файла 524–529:

524 /* При разыменовании лишь аргументов командной строки мы
525    используем флаг nftw FTW_PHYS, поэтому символическая ссылка
526    на каталог, указанная в командной строке, в норме не
527    разыменовывается. Для решения этого мы идем на издержки,
528    сначала добавляя '/.' (или '.'), а затем удаляем их каждый раз
529    при выводе имени производного файла или каталога. */

В этом случае arg_length равен true, поэтому строки 164–173 должны вывести первоначальное имя, а не измененное В противном случае строки 174–177 могут вывести имя как есть.

Фу! Куча кода. Мы находим, что это верхний уровень спектра сложности, по крайней мере, насколько это может быть просто представлено в книге данного содержания. Однако, он демонстрирует, что код из реальной жизни часто бывает сложным. Лучшим способом справиться с этой сложностью является ясное именование переменных и подробные комментарии du.с в этом отношении хорош; мы довольно легко смогли извлечь и изучить код без необходимости показывать все 735 строк программы!

Оглавление книги