Skip to content

Instantly share code, notes, and snippets.

@jwise

jwise/pbfsck.c

Created September 17, 2019 23:49
Show Gist options
  • Save jwise/18798275df57813d08a23dc7828ab7ce to your computer and use it in GitHub Desktop.
Save jwise/18798275df57813d08a23dc7828ab7ce to your computer and use it in GitHub Desktop.
Download ZIP
Raw
pbfsck.c
#include <stdint.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FLAG_CLR_P(val, flag) (((val) & (flag)) == 0)
struct hdr {
uint16_t v_0x5001; /* 01 50 */
/* This byte is read by a function "test_scan_for_last_written", which stops
* when it reads 0xFE. Similarly, update_last_written_page, which updates a
* static variable. prv_update_last_written_page's logic is to update the
* last written page with 0xFC, then mark the page that we'd like to mark as
* the next last-written-page as 0xFE. Finally, when we go to erase a sector, we put the last-written marker back where it came from (no kidding -- not at the beginning of the erase sector!). So this isn't a bitfield at all*/
uint8_t empty; /* 0xFF if empty, 0xFC if not empty, 0xFE if the first empty block before the rest of the device is empty? */
#define HDR_EMPTY_ALLOCATED 0x1
#define HDR_EMPTY_MOREBLOCKS 0x2
uint8_t status; /* bitfield; f4, f8, ... */
#define HDR_STATUS_VALID 0x1
#define HDR_STATUS_DEAD 0x2
#define HDR_STATUS_FILE_START 0x4
#define HDR_STATUS_FILE_CONT 0x8
uint32_t rsvd_0; /* ff ff ff ff */
uint32_t wear_level_counter;
uint32_t rsvd_1;
uint32_t rsvd_2;
uint8_t rsvd_3;
uint8_t next_page_crc;
uint16_t next_page;
uint32_t pagehdr_crc; /* random numbers? */
uint32_t file_size;
uint8_t flag_2; /* FF or FE; FE if there's a filename */
#define HDR_FLAG_2_HAS_FILENAME 0x1
uint8_t filename_len;
uint16_t rsvd_4; /* FF FF */
uint32_t rsvd_5;
uint32_t filehdr_crc;
uint16_t st_tmp_file; /* non-zero if temp file, zero if not temp file */
uint16_t st_create_complete; /* zero if create complete, non-zero if not */
uint16_t st_delete_complete; /* zero if delete complete, non-zero if not */
uint8_t v_full[26];
uint8_t filename[];
};
#define PGSZ 0x2000
#define PGSTART 0x400000
#define POLY 0x04C11DB7
uint32_t crc_table[256];
uint32_t update_crc_slow_1byte(uint32_t crc, uint32_t data) {
crc ^= data;
for (int i = 0; i < 8; i++) {
if (crc & 0x80000000) {
crc = (crc << 1) ^ POLY;
} else {
crc = (crc << 1);
}
}
return crc;
}
void mk_table() {
for (uint32_t i = 0; i < 256; i++) {
crc_table[i] = update_crc_slow_1byte(0, i << 24);
}
}
uint32_t update_crc_fast_byte(uint32_t crc, uint8_t data) {
uint32_t ent = (crc >> 24) ^ data;
return (crc << 8) ^ crc_table[ent];
}
uint32_t update_crc(uint32_t crc, uint32_t data) {
crc = update_crc_fast_byte(crc, (data >> 24) & 0xFF);
crc = update_crc_fast_byte(crc, (data >> 16) & 0xFF);
crc = update_crc_fast_byte(crc, (data >> 8) & 0xFF);
crc = update_crc_fast_byte(crc, (data ) & 0xFF);
return crc;
}
uint32_t pebble_crc(void *p, size_t len) {
uint32_t crc = 0xffffffff;
uint32_t *bufp = (uint32_t *)p;
while (len >= 4) {
crc = update_crc(crc, *bufp);
bufp++;
len -= 4;
}
/* The last word is kind of funky -- it's little-endian justified,
* big-endian. */
if (len > 0) {
uint32_t word = 0x0;
uint8_t *bufp8 = (uint8_t *)bufp;
for (int i = 0; i < len; i++) {
word |= bufp8[i] << ((len - i - 1) * 8);
}
crc = update_crc(crc, word);
len -= len;
}
return crc;
}
uint32_t pagehdr_crc(struct hdr *hdr) {
struct hdr hdr2 = *hdr;
hdr2.empty = 0xFF;
return pebble_crc(&hdr2, (uint64_t)&(hdr->pagehdr_crc) - (uint64_t)&(hdr->v_0x5001));
}
uint32_t filehdr_crc(struct hdr *hdr) {
struct hdr hdr2 = *hdr;
hdr2.empty = 0xFF;
return pebble_crc(&(hdr2.file_size), (uint64_t)&(hdr->filehdr_crc) - (uint64_t)&(hdr->file_size));
}
#define CRC8_POLY 0x2F
uint8_t crc8(uint8_t *buf, size_t len) {
uint8_t crc = 0x00;
while (len) {
crc ^= *buf;
for (int i = 0; i < 8; i++) {
if (crc & 0x80) {
crc = (crc << 1) ^ CRC8_POLY;
} else {
crc = (crc << 1);
}
}
buf++;
len--;
}
return crc;
}
uint8_t next_page_crc(uint16_t next_page) {
next_page = (next_page >> 8) | (next_page << 8); /* CRC is byte-swapped on Pebble. */
if (next_page == 0xFFFF)
return 0xFF;
return crc8((uint8_t *)&next_page, 2);
}
int main() {
unsigned char pgbuf[PGSZ];
int pg = 0;
int disconcerting = 0;
int nowrite = 0;
int noread = 0;
#define COMPLAIN(creepy, str, ...) do { creepy++; fprintf(stderr, str, ##__VA_ARGS__); } while(0)
mk_table();
printf("phase 1: verifying page allocations\n");
/* Basic allocator checks: make sure that there are no allocated
* blocks after the LASTBLOCK, make sure that every block is VALID,
* and make sure that every ALLOCATED block is used either as
* FILE_START or FILE_CONT. While we're at it, count up files.
*/
int npgs, nemptypgs, ndeadpgs, nfiles;
int isend;
lseek(0, PGSTART, SEEK_SET);
pg = nemptypgs = ndeadpgs = nfiles = 0;
isend = 0;
while (read(0, pgbuf, PGSZ) == PGSZ) {
struct hdr *hdr = (struct hdr *)pgbuf;
/* is the page really empty? */
int isempty = 1, ispghdrempty = 1;
for (int i = 0; i < 0x18; i++)
if (pgbuf[i] != 0xFF)
ispghdrempty = 0;
for (int i = 0x18; i < PGSZ; i++)
if (pgbuf[i] != 0xFF)
isempty = 0;
if (ispghdrempty && isempty) {
COMPLAIN(disconcerting, "ERROR: page %d appears to be erased\n", pg);
continue;
}
if (ispghdrempty && !isempty) {
COMPLAIN(nowrite, "ERROR: %d page header appears to be empty, but page isn't!\n", pg);
continue;
}
if (hdr->v_0x5001 != 0x5001)
COMPLAIN(nowrite, "ERROR: page %d has bad signature %04x?\n", pg, hdr->v_0x5001);
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_VALID))
COMPLAIN(disconcerting, "ERROR: page %d does not have valid flag set\n", pg);
if (isend && FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED))
COMPLAIN(nowrite, "ERROR: page %d (%08x) is beyond the last block\n", pg, pg * PGSZ + PGSTART);
/* XXX: why do we sometimes see blocks that are neither ALLOCATED nor MOREBLOCKS (i.e., empty = 0xFF)? */
if (FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED) && !FLAG_CLR_P(hdr->empty, HDR_EMPTY_MOREBLOCKS))
isend = 1;
if (FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED) && !(FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_START) || FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_CONT)))
COMPLAIN(disconcerting, "ERROR: page %d is allocated, but not a file start or end\n", pg);
if ((hdr->empty & 0xFC) != 0xFC)
COMPLAIN(nowrite, "ERROR: page %d has unknown bits clear in empty word (0x%02x)\n", pg, hdr->empty);
if ((hdr->status & 0xF0) != 0xF0)
COMPLAIN(nowrite, "ERROR: page %d has unknown bits clear in status word (0x%02x)\n", pg, hdr->status);
if (!FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED) && !isempty)
COMPLAIN(nowrite, "ERROR: page %d is not allocated, but also is not empty\n", pg);
if (hdr->rsvd_0 != 0xFFFFFFFF)
COMPLAIN(disconcerting, "ERROR: pg %d rsvd_0 = 0x%08x?\n", pg, hdr->rsvd_0);
if (hdr->rsvd_1 != 0xFFFFFFFF)
COMPLAIN(disconcerting, "ERROR: pg %d rsvd_1 = 0x%08x?\n", pg, hdr->rsvd_1);
if (hdr->rsvd_2 != 0xFFFFFFFF)
COMPLAIN(disconcerting, "ERROR: pg %d rsvd_2 = 0x%08x?\n", pg, hdr->rsvd_2);
if (hdr->rsvd_3 != 0xFF)
COMPLAIN(disconcerting, "ERROR: pg %d rsvd_3 = 0x%08x?\n", pg, hdr->rsvd_3);
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED) && (hdr->pagehdr_crc != pagehdr_crc(hdr)))
COMPLAIN(disconcerting, "ERROR: pg %d pagehdr crc is bad %08x expect %08x\n", pg, hdr->pagehdr_crc, pagehdr_crc(hdr));
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED) && (hdr->next_page_crc != next_page_crc(hdr->next_page)))
COMPLAIN(disconcerting, "ERROR: pg %d nextpage (%04x) crc is bad %02x expect %02x\n", pg, hdr->next_page, hdr->next_page_crc, next_page_crc(hdr->next_page));
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_START))
nfiles++;
if (!FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED))
nemptypgs++;
if (FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD))
ndeadpgs++;
pg++;
}
npgs = pg;
printf("phase 1: %d total pages (%d pages used, %d pages empty + %d pages dead = %d pages avail)\n", npgs, npgs - nemptypgs - ndeadpgs, nemptypgs, ndeadpgs, nemptypgs + ndeadpgs);
printf("phase 2: checking semantic structure\n");
/* Look for all the non-dead start of files, and create a file
* table. Validate file headers. While we're at it, build a table
* of non-dead leaf pages that we can use for orphan and crosslink
* checks later.
*/
struct file {
char *name;
uint16_t page;
uint32_t size;
};
int ndeadfiles = 0;
int file = 0;
struct file *files = malloc(sizeof(struct file) * nfiles);
uint8_t *links = malloc(npgs);
memset(links, 0, npgs);
for (pg = 0; pg < npgs; pg++) {
struct hdr *hdr = (struct hdr *)pgbuf;
char *name;
lseek(0, PGSTART + pg * PGSZ, SEEK_SET);
read(0, pgbuf, PGSZ); /* XXX: check */
if (!FLAG_CLR_P(hdr->empty, HDR_EMPTY_ALLOCATED))
continue;
if (FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_CONT) == FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_START)) {
COMPLAIN(noread, "ERROR: page %d has illegal status byte 0x%02x\n", pg, hdr->status);
continue;
}
if (FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_CONT) && !FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD))
links[pg] = 1;
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_FILE_START))
continue;
if (hdr->flag_2 == 0xFF) {
COMPLAIN(disconcerting, "ERROR: page %d has nameless file?\n", pg);
name = strdup("(unknown)");
} else if (hdr->flag_2 == 0xFE) {
name = malloc(hdr->filename_len + 1);
memcpy(name, hdr->filename, hdr->filename_len);
name[hdr->filename_len] = 0;
} else {
COMPLAIN(disconcerting, "ERROR: page %d has bad filename flag 0x%02x\n", pg, hdr->flag_2);
continue;
}
if (hdr->rsvd_4 != 0xFFFF)
COMPLAIN(disconcerting, "ERROR: page %d file header rsvd_4 = 0x%08x?\n", pg, hdr->rsvd_4);
if (hdr->rsvd_5 != 0xFFFFFFFF)
COMPLAIN(disconcerting, "ERROR: page %d file header rsvd_4 = 0x%08x?\n", pg, hdr->rsvd_4);
if (hdr->filehdr_crc != filehdr_crc(hdr))
COMPLAIN(disconcerting, "ERROR: page %d filehdr crc is bad %08x expect %08x\n", pg, hdr->filehdr_crc, filehdr_crc(hdr));
if (hdr->st_tmp_file)
COMPLAIN(disconcerting, "warning: %sfile %s at page %d is temp file\n", FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) ? "dead " : "", name, pg);
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && hdr->st_create_complete)
COMPLAIN(disconcerting, "warning: file %s at page %d creation not complete\n", name, pg);
if (FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && hdr->st_create_complete)
COMPLAIN(noread, "ERROR: file %s at page %d is dead enough for life, but not alive enough for death?\n", name, pg);
if (FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && hdr->st_delete_complete)
COMPLAIN(disconcerting, "warning: %sfile %s at page %d deletion not complete\n", FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) ? "dead " : "", name, pg);
if (!FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD) && !hdr->st_delete_complete)
COMPLAIN(noread, "ERROR: file %s at page %d is alive enough for death, but not dead enough for life?\n", name, pg);
if (FLAG_CLR_P(hdr->status, HDR_STATUS_DEAD)) {
printf("file: %s (dead)\n", name);
ndeadfiles++;
free(name);
continue;
}
files[file].name = name;
files[file].page = pg;
files[file].size = hdr->file_size;
file++;
}
/* Make sure that no two files have the same name. */
for (file = 0; file < nfiles; file++) {
int file2;
for (file2 = file + 1; file2 < nfiles; file2++) {
if (!strcmp(files[file].name, files[file2].name)) {
COMPLAIN(noread, "ERROR: file from page %d and %d have the same name, \"%s\"\n", files[file].page, files[file2].page, files[file].name);
break;
}
}
}
printf("phase 2: %d live files, %d dead files\n", nfiles, ndeadfiles);
/* If there's a GC file, we need to recover it. */
for (file = 0; file < nfiles; file++) {
if (!strcmp(files[file].name, "GC")) {
COMPLAIN(noread, "ERROR: there is a live garbage collection file; filesystem is likely in an inconsistent state\n");
}
}
/* Walk all live files, and make sure that each leaf page is
* referenced exactly once.
*/
printf("phase 3: checking for crosslinked or orphaned pages\n");
for (file = 0; file < nfiles; file++) {
int filepgs;
struct hdr *hdr = (struct hdr *)pgbuf;
lseek(0, PGSTART + files[file].page * PGSZ, SEEK_SET);
read(0, pgbuf, PGSZ); /* XXX: check */
filepgs = 1;
while (hdr->next_page != 0xFFFF) {
filepgs++;
if (hdr->next_page > npgs) {
COMPLAIN(noread, "ERROR: page %d (#%d) in file %s is outside flash\n", hdr->next_page, filepgs, files[file].name);
break;
}
if (links[hdr->next_page] == 0) {
COMPLAIN(noread, "ERROR: page %d (#%d) in file %s was unallocated\n", hdr->next_page, filepgs, files[file].name);
break;
}
if (links[hdr->next_page] == 0xFF) {
COMPLAIN(noread, "ERROR: page %d (#%d) in file %s was crosslinked\n", hdr->next_page, filepgs, files[file].name);
break;
}
links[hdr->next_page] = 0xFF;
lseek(0, PGSTART + hdr->next_page * PGSZ, SEEK_SET);
read(0, pgbuf, PGSZ); /* XXX: check */
}
printf("file: %s (%d bytes / %d page%s @ page %d)\n", files[file].name, files[file].size, filepgs, (filepgs > 1) ? "s" : "", files[file].page);
}
for (pg = 0; pg < npgs; pg++) {
if (links[pg] == 1)
COMPLAIN(disconcerting, "ERROR: orphan page %d\n", pg);
}
if (disconcerting)
printf("There were %d things that made me feel a little uncomfortable.\n", disconcerting);
if (nowrite)
printf("There were %d things that scared me enough that I wouldn't write to this filesystem.\n", nowrite);
if (noread)
printf("This filesystem is very spooky. %d things made me feel like I wouldn't even be able to reliably read this.\n", noread);
if (!disconcerting && !nowrite && !noread)
printf("This filesystem seems healthy enough to me.\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment