Моя функция C рекурсивно обращается к системным каталогам, а ошибки по большим входам. Как я могу это исправить?

Question

Я пытаюсь закодировать программу, которая просматривает данный каталог и все подкаталоги и файлы в нем (и подкаталоги и файлы подкаталогов и т. Д.) И распечатывает все файлы, которые имеют заданный набор разрешений (int target_perm).

Он отлично работает при меньших входных данных, но возвращает Segmentation fault (core dumped), когда приходится проходить по каталогам с большим количеством файлов. Valgrind показывает, что это связано с переполнением стека.

Можно ли как-то исправить мою функцию, чтобы она могла работать с произвольно большими каталогами?

void recurse_dir(struct stat *sb, struct dirent *de, DIR *dr, int target_perm, char* curr_path) {
    if ((strcmp(".", de->d_name) != 0) && (strcmp("..", de->d_name) != 0)) {

        char full_file_name[strlen(curr_path) + strlen(de->d_name)+1];
        strcpy(full_file_name, curr_path);
        strcpy(full_file_name + strlen(curr_path), de->d_name);
        full_file_name[strlen(curr_path) + strlen(de->d_name)] = '\0';

        if (stat(full_file_name, sb) < 0) {
            fprintf(stderr, "Error: Cannot stat '%s'. %s\n", full_file_name, strerror(errno));
        } else {
            char* curr_perm_str = permission_string(sb);
            int curr_perm = permission_string_to_bin(curr_perm_str);
            free(curr_perm_str);

            if ((curr_perm == target_perm )) {
                printf("%s\n", full_file_name);
            }

            if (S_ISDIR(sb->st_mode)) {
                DIR *dp;
                struct dirent *dent;
                struct stat b;
                dp = opendir(full_file_name);

                char new_path[PATH_MAX];
                strcpy(new_path, full_file_name);
                new_path[strlen(full_file_name)] ='/';
                new_path[strlen(full_file_name)+1] ='\0';

                if (dp != NULL) {
                    if ((dent = readdir(dp)) != NULL) {
                        recurse_dir(&b, dent, dp, target_perm, new_path);
                    }
                    closedir(dp);               
                } else {
                    fprintf(stderr, "Error: Cannot open directory '%s'. %s.\n", de->d_name, strerror(errno));
                }
            }           
        }
    }

    if ((de = readdir(dr)) != NULL) {
        recurse_dir(sb, de, dr, target_perm, curr_path);
    }
}

Answer 1

Проблема здесь на самом деле не в рекурсии, хотя я рассмотрел эту конкретную проблему ниже. Проблема в том, что ваша иерархия каталогов, вероятно, содержит символьные ссылки c, которые делают псевдонимы некоторых каталогов для одного из их родителей. Пример из установки Ubuntu:

$ ls -ld /usr/bin/X11
lrwxrwxrwx 1 root root 1 Jan 25  2018 /usr/bin/X11 -> .

$ # Just for clarity:
$ readlink -f /usr/bin/X11
usr/bin

Итак, когда вы встречаете /usr/bin/X11, вы входите в бесконечное число l oop. Это быстро исчерпает стек, но избавление от рекурсии не решит проблему, поскольку бесконечный l oop по-прежнему является бесконечным l oop.

. Вам нужно либо:

• Избегайте следующих символических ссылок, или

• (лучше) Избегайте следующих символических ссылок, которые разрешаются в каталогах, или

• Отслеживайте все каталоги, с которыми вы столкнулись во время рекурсивного сканирования, и проверяйте, чтобы убедиться, что новый каталог еще не проверен.

Первые два решения: проще (вам просто нужно проверить поле filetype в struct stat), но они не смогут перечислить некоторые файлы, которые могут вас заинтересовать (например, когда символическая ссылка преобразуется в каталог вне структуры каталогов, которую вы изучаете. )

Как только вы исправите вышеуказанную проблему, вы можете рассмотреть следующие предложения:

1. В рекурсивных функциях всегда полезно уменьшить размер стека Рамка до минимально возможного. Максимальная глубина рекурсии во время обхода каталога не должна превышать максимального количества сегментов пути в имени файла (но см. Пункт 3 ниже), которое не должно быть слишком большим числом. (В моей системе максимальная глубина файла в иерархии /usr составляет, например, 16). Но размер используемого стека является произведением размера кадра стека и максимальной глубины рекурсии, поэтому, если ваш стек кадры большие, тогда у вас будет меньше возможностей рекурсии.

2. Для достижения вышеуказанной цели следует избегать использования локальных массивов. Например, объявление

   char new_path[PATH_MAX];
   

   добавляет PATH_MAX байтов к каждому кадру стека (в моей системе это 4k). И это в дополнение к VLA full_file_name. Что бы это ни стоило, я скомпилировал вашу функцию в 64-битной системе Linux и обнаружил, что размер кадра стека составляет 4280 байт плюс размер VLA (округленный до кратного 16 для выравнивания). Это, вероятно, не будет использовать более 150 КБ стека, при условии разумной файловой иерархии, которая находится в пределах. Но это может значительно увеличиться, если ваша система имеет большее значение PATH_MAX (на которое в любом случае нельзя полагаться как на максимальный размер пути к файлу).

   Хороший стиль диктует использование динамически распределяемого память для переменных, подобных этим. Но еще лучшим подходом было бы избегать использования такого большого количества разных буферов.

3. В скобках, вам также нужно знать о стоимости strlen. Чтобы вычислить длину строки, функция strlen должна просканировать все свои байты в поисках терминатора NUL. Строки C, в отличие от строковых объектов в языках более высокого уровня, не содержат указаний на их длину. Поэтому, когда вы делаете это:

   char full_file_name[strlen(curr_path) + strlen(de->d_name)+1];
   strcpy(full_file_name, curr_path);
   strcpy(full_file_name + strlen(curr_path), de->d_name);
   full_file_name[strlen(curr_path) + strlen(de->d_name)] = '\0';
   

   вы в конечном итоге сканируете curr_path три раза и de->d_name дважды, даже если длина этих строк не изменится. Вместо того, чтобы делать это, вы должны сохранить длины в локальных переменных, чтобы их можно было использовать повторно.

   В качестве альтернативы, вы можете найти другой способ объединения строк. Одна простая возможность, которая также динамически распределяет память, это:

   char* full_file_name;
   asprintf(&full_file_name, "%s%s", curr_path, de->d_name);
   

   • Примечание: Вы должны проверить возвращаемое значение asprintf, оба, чтобы убедиться, что не было проблемы с выделением памяти, а также для сохранения длины full_file_name на случай, если она понадобится вам позже. asprintf доступно для Linux и производных BSD, включая OS X. Но это легко реализовать с помощью стандарта Posix snprintf, и есть короткие, свободно повторяющиеся реализации.)

   • Вы также можете использовать asprintf для вычисления new_path, также снова удаляя выделение стека для возможно большого массива (и избегая переполнения буфера, если PATH_MAX недостаточно велик, чтобы содержать новый путь к файлу что, безусловно, возможно):

     char* newpath;
     asprintf("%s/", full_file_path);
     

     Но это глупо. Вы копируете весь путь к файлу только для того, чтобы добавить один символ в конце. Лучше было бы оставить место для sla sh, когда вы вначале создаете full_file_path, и заполнить его, когда вам это нужно:

     char* full_file_name;
     int full_file_name_len = asprintf(&full_file_name, "%s%s\0",
                                          curr_path, de->d_name);
     if (full_file_name_len < 0) { /* handle error */ }
     --full_file_name_len; /* Bytes written includes the \0 in the format */
     
     /* Much later, instead of creating new_path: */
     
     if (dp != NULL) {
         full_file_name[full_file_name_len - 1] = '/';
     
         if ((dent = readdir(dp)) != NULL) {
             recurse_dir(&b, dent, dp, target_perm, full_file_name);
         }
     
         full_file_name[full_file_name_len - 1] = '\0';
     
         closedir(dp);               
     } 
     

     Есть другие способы сделать это. На самом деле вам нужен только один буфер пути к файлу, который вы можете передать через рекурсию. Рекурсия добавляется только в путь к файлу, поэтому необходимо только восстановить байт NUL в конце каждого рекурсивного вызова. Однако в рабочем коде вы не захотите использовать буфер фиксированной длины, который может оказаться слишком маленьким, поэтому вам нужно будет реализовать какую-то стратегию перераспределения.

4. Пока я пытался выяснить фактический размер кадра стека для вашей функции, которая требовала его компиляции, я наткнулся на этот код, который опирается на некоторые необъявленные функции:

       char* curr_perm_str = permission_string(sb);
       int curr_perm = permission_string_to_bin(curr_perm_str);
       free(curr_perm_str);
   

   Делая догадки о что эти две функции делают, я думаю, вы могли бы смело заменить вышеприведенное на

       int curr_perm = sb->st_mode & (S_IRWXU|S_IRWXG|S_IRWXO);
   

   или, возможно,

       int curr_perm = sb->st_mode
                       & (S_ISUID|S_ISGID|S_ISVTX|S_IRWXU|S_IRWXG|S_IRWXO);
   

   , если вы хотите включить setuid и sticky-биты.