Всем доброго времени суток.

На девайсе под управлением STM32 есть процедура, которая создаёт сортированный по алфавиту список файлов FAT32 диска на флеш карточке.
Используется FatFs версии 0.08.
Количество файлов в списке может быть максимум 500.

На днях обратил внимание, что львиная доля времени (около 90%), затрачиваемого на сортировку, потребляется функцией файловой системы f_open().
Поковырявшись в её дебрях, обнаружил, что в свою очередь это вызвано подфункцией move_window(), которая подгружает по одному сектору из, вероятно, каталога фат.

То есть чтобы открыть файл, файловая система продирается через структуру фат до того, как найдёт запись с информацией по нужному файлу.
Считывание ведётся по одному сектору.
И так для каждого файла.

Вот и подумалось тут, а почему бы не ввести кеширование для секторов, запрашиваемых функцией move_window()?

Главный вопрос здесь - хватит ли для этого 10-20 килобайт оперативки?
К сожалению, приходится довольствоваться только внутренним ОЗУ контроллера.

Наверное, для FAT32 с большим количеством файлов кеширование 20 килобайт (40 секторов) не будет эффективным?

Ну почему же? Любой кэш лучше, чем его отсутствие. Особенно если использовать чтение группы блоков для заполнения строки.

Хм, спасибо, тогда попробую, когда будет время.

move_window() запрашивает по одному сектору, как тут организуешь мультисекторное чтение?
Если только запросы будут идти последовательно по порядку.

В любом случае, надо сначала посмотреть, как именно идёт чтение - организовать лог и писать туда номера запрашиваемых секторов.
Тогда будет видна общая картина

Читать сразу строку, получится своего рода упреждающее чтение. Если не увлекаться увеличением длины строки, то в мусор пойдет не так много данных.
Если интересно, могу описать систему кэширования, которую я применяю в своих проектах.

Конечно интересно, опишите пожалуйста

Я пока глубоко не копал в структуру FAT на диске, поэтому слабо понимаю механику работы файловой системы.

Тут ведь ещё есть нюанс с записью - надо ли будет перед выполнением записи на диск/в фат сбрасывать кеш?

Хорошо.

Используются две структуры:

Первая описывает строку кэша, из этих записей формируется односвязный список. Вторая - для буфера записи, сложены в виде массива. Отдельно вводим переменную, указывающую текущее заполнение буфера записи - sd_wbuff_level.
Данные отделены от списка для более эффективной работы кэша самого процессора, для STM32 можно буферы внести в структуру.
При инициализации диска формируется список из SD_CACHE_ENTRY, поля sec заполняются значением SD_CACHE_INVALID_SEC (0xffffffff); переменную sd_wbuff_level устанавливаем в 0.
Число секторов в строке у меня выбрано равным 8.

Чтение:
1. Последовательно проходим по списку, если запрашиваемый сектор находится внутри имеющейся в кэш строки:
1.1. Копируем данные из кэш
1.2. Переставляем строку в начало списка (это нужно для увеличения производительности - редко использующиеся строки будут постепенно падать в конец списка)
2. Если данные в кэш отсутствуют, то:
2.1. Сбрасываем на диск буфер записи (некоторое упрощение, чтобы не искать данные в буфере)
2.2. Читаем с карты строку, заполняя при этом последнюю из записей, по которым ходили в п.1
2.3. Переставляем заполненную строку в начало списка

Запись:
1. Проходим по списку. Если нужная строка найдена, заменяем в ней данные и запоминаем адрес
2. Проходим по буферу записи до уровня sd_wbuff_level, добавляем запись и увеличиваем sd_wbuff_level, если целевой сектор отсутствует
3. При заполнении структуры буфера записи заменяем адрес в SD_WRITE_BUFFER_ENTRY на адрес в кэше, если в п.1 строка была найдена (исключаем лишнее копирование)

Очистка буфера записи:
1. Сортируем записи в буфере по возрастанию номеров блоков
2. Пишем данные с использованием мультиблочной записи

Вот как-то так.

P.S. У меня, правда, файловая система написана в расчете на кэшируемый диск, поэтому не стесняется что-то прочитать или записать, когда надо. Если над этой системой будет надстроена еще одна, то производительность несколько снизится.

Спасибо!
Что-то вроде этого задумывал и я, только в условиях нехватки памяти кешировать нужно исключительно сектора каталогов фат (или как правильно называется область со структурами имён файлов?).

Вероятно, move_window() читает/пишет только такие сектора, поэтому попробую привязать кеш именно к ней...

Хм, вот все же странно как то у Чена сделан подход к кешированию.
То есть кешировать абсолютно весь диск - нет проблем, делается это просто через функции ReadSectors() и WriteSectors().
Но это не сильно умно в условиях ограниченного количества оперативки.

Логичнее было бы закешировать только корневой каталог и FAT (при интенсивной работе с большим кол-вом файлов).

Но как это сделать, не модифицируя исходники Чена?
Почему он не предусмотрел такой возможности?

Нет, move_window() универсальная, вызывается во всех случаях.

А может и нет Логичнее сделать кеширование как написал aaarrr, и тогда в кеше автоматически будут храниться наиболее востребованные данные. Чаще идёт обращение к FAT - значит в кеше FAT. К данным (многократный парсинг одного файла) - в кеше данные. И не надо будет гадать ничего

А во всех - это в каких?
Я пока глубоко не вникал, но показалось, что эта функция с чтением/записью единственного сектора годится только для работы с каталогом.


Это смотря какие условия.
К примеру - открыли мы файл (при этом кеш заполнился секторами корневого каталога), затем считали большой кусок этого файла.
В кеше будет содержимое считанного файла, которое и без него читается быстро.
Затем открываем другой файл - так как в кеше уже нет секторов каталога - снова идёт обращение к диску.

Зачем мне это надо?

Мне бы просто ускорить работу с каталогом

Увы, в условиях дефицита оперативки, придется так или иначе выкручиваться - добавлять в функцию чтения флаг запрета кэширования, например. Или встроить в FatFS отдельный кэш для каталогов и FAT. Просто прикрутить что-то снаружи не выйдет.
Хотя даже с ограниченным объемом памяти приведенный мной вариант может несколько облегчить жизнь за счет наличия своего рода упреждающего чтения.

Ну вообще во всех. Эта функция грузит сектор в единственный буфер объекта-файловой системы. Нужен сектор FAT - грузит его. Читаем данные - грузит их (и FAT конечно выгружен)


Если файл больше чем кэш, то да, придётся предпринять дополнительные шаги. Первый из возможных - кешировать только сектора из FAT. Кстати, в другой известной имплементации FAT - чтение данных и чтение FAT изначально разделены.
Хотя можно и с кешированием похимичить. Например, оставлять в кэше сектор лишь на второй раз.

Оптимальный способ для меня - использовать флаг разрешения кеширования.
Тогда в исходники FatFs достаточно встроить пару строк (к примеру, в функцию f_open() или в move_window()), остальным займётся драйвер.

Однако, это имеет смысл только в случае, когда все требуемые сектора каталога смогут поместиться в кеш.
Иначе пользы будет ноль


А как же мультисекторные чтение/запись?

Нет, конечно-же, не пугайте так
Эта функция используется только в конфигурации _FS_TINY.
В остальных случаях идёт прямое обращение к disk_read() - к драйверу.

Привыкли, наверное, к AVR?


Да, именно это мне и требуется.

Хотя, даже в случае наличия 20 килобайт памяти их для этого не хватает
Нужны "метры"!

Если используется именно FAT32 (или не корневой каталог FAT16), то смысл будет иметь любой кэш объемом более одного кластера - так по крайней мере активный сектор FAT'а будет всегда "на плаву". Словом, некоторый выигрыш получите практически в любом случае.
Конечно, чем больше объем - тем лучше. Можно сделать "как у больших", отдав всю не выделенную приложениям память под нужды дискового кэша. Правда, в случае STM32 без внешней ОЗУ это уже излишества.

Вот именно.
Мне просто стало интересно, почему основное время процедура сортировки теряет не на собственно сортировке, а на банальном открытии файла , вот и полез разбираться.
Особых проблем не будет и без кеша, конечно.

ЗЫ: Правильно ли я рассуждаю: к примеру, выделяем на кеш 40 секторов.
Вызываем f_open() - она начинает двигаться по корневому каталогу в поисках целевого файла, последовательно считывая сектора.
Скажем, находит его после считывания пятидесяти секторов, то есть в кеше находятся сектора 10 - 50.

Вызываем f_open() снова - другой файл - чтение корневого каталога повторяется опять с первого сектора... которого в кеше нет.
Соответственно, снова последовательно считываются все сектора заново, так как первый сектор замещает 10, второй - 11 и т.д.

В этой ситуации пользы от кеша - ровно ноль.

Но это теория. Надо проверить на практике.