Created
September 17, 2019 23:49
-
-
Save jwise/18798275df57813d08a23dc7828ab7ce to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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