Table of Contents
Введение
Статья описывает формат файлов, хранящих базы PalmOS на NVFS-диске.
С введением энергонезависимого хранилища разработчикам PalmOS досталась новая проблема: теперь хранилище - это обычный диск с файловой системой. Как хранить на нем базы классического Data Manager?
Поскольку Data Manager - это список файлов, то первый шаг простой. Положим все файлы с базами в каталог /PALM_DM. Дальше встает вопрос о формате файла с базой.
Очевидное, казалось бы, решение: использовать классический формат prc/pdb файлов, в которых базы хранятся на десктопе. Но у этого решения есть огромный минус: формат хорош для хранения неизменных файлов, и при любом изменении ресурса придется перезаписывать весь хвост файла? все его записи, располагающиеся после изменяемой. Вообщем-то понятно, что реализовывать на плоском одномерном файле список изменящихся записей переменной длины - это задача неблагодарная, так как приходится реализовывать списки блоков для ресурса, отслеживать список свободных блоков. Вообщем, реализовывать мини-файловую систему внутри файла.
Дальнейшее описание получено путем изучения файлов от Treo 650 unlocked gsm с последней прошивкой. У других моделей формат может отличаться. Описывается база ресурсов, отличия с базой записей даны ниже, но основные структуры совпадают.
Экстенты
Сначала опишем общие идеи, лежащие в основе хранения базы. Единица хранения - сектор, размером 512 байт. Всё распределение памяти в файле работает посекторно. Начиная с PalmOS 5.4.7 реализована субаллокация, при которой ресурс может занимает меньше места. В этом случае сектор разбивается на 16 субблоков по 32 байта, каждый из которых можно занимать независимый ресурс. Ресурс длины X занимает (X / 512) полных секторов, остаток длиной (X % 512) помещается в субблок минимальной длины, вмещающей его. Далее мы будем задавать сектора их смещениями он начала файла. Сразу заметим, что ресурс может располагаться в несмежных секторах.
Большая единица распределения называется экстентом. Файл разбивается на экстенты длиной 0xF600 (62976) байт. Экстент состоит из заголовка и блоков с данными. Заголовок занимает один сектор, в начале экстента отводится место под два заголовка из которых валиден только один (по смещениям от начала экстента 0x000-0x1ff и 0x200-0x3ff). Так сделано скорее всего для сохранения предыдушего заголовка в случае сбоя при записи нового. Валидный заголовок определяется по первым двум байтам, где хранится 0x6904 для валидного заголовка и 0x6903 или мусор для невалидного. У самого первого заголовка экстента может быть и третье местоположение по адресу 0x400. Со смещения 0x600 начинаются сектора с данными, там же хранится и каталог ресурсов базы.
Длина файла может быть некратной размеру экстента. Это может произойти в том случае, если остаток секторов экстента свободен. При необходимости файл будет “добит” до нужной длины.
Ниже приведена структура заголовка экстента.
struct ExtentHeader
{
UINT16 magic;
UINT8 freeListStartBlock;
UINT8 blackMagic;
UINT8 lastBlockMask[16];
UINT32 fat[MAX_BLOCKS_IN_EXTENT];
};
Поле magic определяет валидность заголовка. Поле freeListStartBlock указывает на первый свободный сектор. Назначение поля blackMagic неизвестно. Поле lastBlockMask содержит битовую маску последних секторов (подробности см. ниже). Оставшееся место в секторе заголовка занимает таблица fat ( file allocation table).
Анализ имеющихся баз не позволил уверенно понять как происходит выбор “правильной” версии заголовка экстента. Понятно, что заголовки с мусором в поле magic ( не 0x6904) изначально некорректны. Значение 0x6903 скорее всего означает некую временную незавершенную копию. Но у некоторого количества баз оба сектора (или два из трех) содержали правильное значение magic. Попытка анализа по полю blackMagic не очень удалась, вроде бы чем меньше это поле, тем “правильнее” заголовок, но встречаются базы с одинаковыми значениями поля в соседних заголовках.
FAT
Как и в “самой ужасной, но наиболее распространенной” файловой системе хранилище баз использует fat: таблицу распределения секторов в экстенте. Каждый сектор экстента имеет свои 32 бита в таблице fat. Отсюда, кстати, и некруглый размер экстента: в таблицу fat помещается информация о
(512 - 2 - 1 - 17) / 4 = 123
секторах. Соответственно размер экстента
123 * 512 = 0xF600
.
Что хранится в данных fat? Можно выделить три типа значений. Во-первых, для длинных записей там хранится смещение следующего сектора с данными записи, что логично совпадает со смыслом значений таблицы в FAT16. Во-вторых, для коротких ресурсов и хвостов длинных ресурсов там хранится битовая маска занятых субблоков. В-третьих для свободных блоков там хранится номер следующего свободного блока в этом экстенте. Рассмотрим эти типы поподробнее.
Смещение следующего сектора. С этим типом значений все просто, это смещение начала сектора относительно начала файла. Обращаю внимание: не от начала экстента, но от начала файла. Как поле используется - понятно, при seek по записи OS считывает это значение и определяет следующий сектор. Еще один нюанс: ресурс может быть размазан по нескольким экстентам, так что процесс прохода по ресурсу может вызвать прыгания между экстентами.
Битовая маска занятых субблоков. Этот тип значений применяется для ресурсов с размером меньше сектора и для “хвостов” длинных записей. Значение интерпретируется как 16-битовая маска, где каждый бит отвечает за свой субблок. так, маска 0xff00 для сектора 0x800 указывает на свободные адреса 0x800-0x8ff и занятые адреса 0x900-0x9ff.
Номер следующего свободного блока. Все свободные блоки в экстенте объединяются в список. Первый блок указывается в поле freeListStartBlock заголовка. Поскольку все блоки относятся к одному экстенту, то значение номера лежит в диапазоне 0-122 и является индексом в массиве fat. В последнем свободном блоке лежит значение 0xf0.
Самый интересный вопрос - как определить тип считанного значения из таблицы fat. Смещения и номера свободных секторов не пересекаются по значениям, так как одни кратны 512, а другие не могут быть больше 255. С масками сложнее, точный критерий отличия маски от смещения неизвестен, но по изученным базам, реализация не позволяет делать маски кратными 512. То есть сектор 0x800, в котором адреса 0x800-0x90f свободны, а 0x910-0x9ff заняты не должен существовать. Но это всего лишь догадка, возможно, что такие сектора являются причиной известных ошибок PalmOS.
Другой возможный способ отличия типов секторов заключается в том, что каждый тип сектора должен появляться на своем месте. То есть номера блоков появляются только в списке свободных блоков, смещения появляются только в целиком занятых секторах файлов, а битовые маски могут встречаться только в последних секторах файлов.
В заголовке экстента есть поле lastBlockMask в котором хранится битовая маска из расчета один бит на сектор экстента. Бит выставляется для тех секторов, которые являются последними или единственными секторами ресурсов. Правда по наблюдениям, сушествуют последние сектора у которых этот бит не выставлен. С другой стороны бит выставляется даже у тех последних секторов, у которых отсутствуют свободные субблоки.
Следующий интересный вопрос - как PalmOS находит свободные субблоки. Со свободными секторами проблем нет - они объединены в список, а вот с субблоками так не получается, из-за того, что не существует объединяющей их структуры. То есть PalmOS либо сканирует fat в поисках подходящего субблока (тогда встает вопрос отличия маски от смещения), либо использует субблоки в ограниченном числе мест, например, запоминает последний использовавшийся субблок и будет выделять только в нем. Возможно, что свободные субблоки ищутся с помощью поля lastBlockMask.
Мы знаем, что первые два сектора используются под заголовок, а третий сектор зарезервирован. Поэтому первые три записи в fat являются специальными. Запись с индексом 0 хранит номер сектора с каталогом, а назначение двух других неизвестно.
Каталог ресурсов
В нулевом элементе таблицы fat хранится номер сектора с каталогом. Если заголовки экстента относятся к распределению секторов внутри файла, то каталог отвечает за распределение информации об элементах базы в файле.
Есть два вида секторов с каталогом - главный и дополнительный. Первый сектор из цепочки секторов каталога является главным, а остальный - дополнительные. В главном секторе находится заголовок базы и информация о первых ресурсах базы. Дополнительные сектора содержат только информацию о ресурсах.
struct DBResourceHeader
{
UINT16 magic; // 0x6902
UINT16 dbHdrCount;
UINT16 x2;
UINT16 x3;
UINT16 recNum;
char dbName[32];
UINT16 flags;
UINT16 version;
PTIME crTime;
PTIME modTime;
PTIME bkTime;
UINT32 type;
UINT32 creator;
UINT8 entryCount;
UINT8 modNum1;
UINT32 modNum;
UINT8 uniqIdSeed[3];
ResourceEntry appInfo;
ResourceEntry sortInfo;
ResourceEntry recs[1];
};
Рассмотрим содержимое главного сектора. Поле magic содержит 0x6902. Дальше идет dbHdrCount - число секторов в каталоге. Далее два неизвестных поля x2 и x3. recNum - число записей в базе. Следующие поля скопированы из заголовка prc-файла и понятны: dbName, flags, version, crTime, modTime, bkTime, type и creator. Поля базы appInfo и sortInfo задаются как ResourceEntry с двумя валидными полями: смещением блока в файле и длиной. Смещение 0xffffffff означает отсутствие поля. Уникальный идентификатор для хотсинка хранится как 3 байта ( это и есть трехбайтовое число). Поле entryCount задает число ресурсов, описываемых в этом секторе, включая appInfo и sortInfo. Поле modNum модифицируется при каждом изменении базы. Также есть однобайтовый modNum1, который тоже увеличивается. Возможно, что modNum глобальный и относится ко всей базе, а modNum1 относится только к модификациям основного сектора каталога. Также не исключено, что modNum отдан на откуп Data Managerу, а modNum1 изменяется кодом, работающим с файлом базы. Оставшееся место занимает описание 31 ресурса базы.
Дополнительный сектор каталога проще.
struct extraDBHeader
{
UINT16 magic;
UINT8 entryCount;
UINT8 modNum1;
UINT32 modNum;
UINT8 uniqIdSeed[3];
ResourceEntry recs[1];
};
struct ResourceEntry
{
UINT32 offset;
UINT16 size;
UINT8 hiSize;
UINT32 type;
UINT16 id;
};
Опять встречается поле magic ( 0x6901). Поле entryCount задает число ресурсов, описываемых в этом секторе. uniqIdSeed совпадает с одноименным полем основного заголовка. Поля modNum и modNum1 тоже совпадают с одноименными полями основного заголовка, но могут и отличаться. Скорее всего эти поля обновляются только в случае изменения параметров ресурсов, хранящихся в секторе.
Информация о ресурсе проста. Хранится смещение первого сектора ресурса, длина ресурса, тип и индекс. Длина хранится в трех байтах. Для “легальных” баз поле hiSize нулевое.
Мелкие замечания: массив информации о ресурсах не всегда забивается полностью. При удалении записи сдвигаются оставшиеся ResourceEntry в секторе, но ResourceEntry из последующих секторов остаются на месте.
Каталог записей
База с записями построена аналогично. Изменения касаются только информации о записях. Вместо типа и индекса там хранятся атрибуты записи и ее идентификатор для хотсинка.
struct DBRecordHeader
{
UINT16 magic;
UINT16 dbHdrCount;
UINT16 x2;
UINT16 x3;
UINT16 recNum;
char dbName[32];
UINT16 flags;
UINT16 version;
PTIME crTime;
PTIME modTime;
PTIME bkTime;
UINT32 type;
UINT32 creator;
UINT8 entryCount;
UINT8 modNum1;
UINT32 modNum;
UINT8 uniqIdSeed[3];
RecordEntry appInfo;
RecordEntry sortInfo;
RecordEntry recs[1];
};
struct RecordEntry
{
UINT32 offset;
UINT16 size;
UINT8 hiSize;
UINT8 attr;
UINT8 recID[3];
};