ref: 26a4fed09d56d1c8c2f46feb8fbec4c9a46adbb7
dir: /check.c/
#include <u.h>
#include <libc.h>
#include <fcall.h>
#include <avl.h>
#include "dat.h"
#include "fns.h"
static int
isfree(vlong bp)
{
Arange *r, q;
Arena *a;
q.off = bp;
q.len = Blksz;
a = getarena(bp);
r = (Arange*)avllookup(a->free, &q, -1);
if(r == nil)
return 0;
return bp < (r->off + r->len);
}
static int
badtree(int fd, Blk *b, int h, Kvp *lo, Kvp *hi)
{
Kvp x, y;
Msg mx, my;
int i, r, fill;
Blk *c;
int fail;
Bptr bp;
fail = 0;
if(h < 0){
fprint(fd, "node too deep (loop?\n");
fail++;
return fail;
}
if(b->type == Tleaf){
if(h != 0){
fprint(fd, "unbalanced leaf\n");
fail++;
}
if(h != 0 && b->nval < 2){
fprint(fd, "warning: underfilled leaf %B\n", b->bp);
fail++;
}
}
if(b->type == Tpivot && b->nval < 2){
fprint(fd, "warning: underfilled pivot %B\n", b->bp);
fail++;
}
getval(b, 0, &x);
if(lo && keycmp(lo, &x) > 0){
fprint(fd, "out of range keys %P != %P\n", lo, &x);
showblk(fd, b, "out of range", 1);
fail++;
}
for(i = 1; i < b->nval; i++){
getval(b, i, &y);
if(hi && keycmp(&y, hi) >= 0){
fprint(fd, "out of range keys %P >= %P\n", &y, hi);
fail++;
}
if(b->type == Tpivot){
bp = getptr(&x, &fill);
if(isfree(bp.addr)){
fprint(fd, "freed block in use: %llx\n", bp.addr);
fail++;
}
if((c = getblk(bp, 0)) == nil){
fprint(fd, "corrupt block: %r\n");
fail++;
continue;
}
if(blkfill(c) != fill){
fprint(fd, "mismatched block fill\n");
fail++;
}
if(badtree(fd, c, h - 1, &x, &y))
fail++;
dropblk(c);
}
r = keycmp(&x, &y);
switch(r){
case -1:
break;
case 0:
fprint(fd, "duplicate keys %P, %P\n", &x, &y);
fail++;
break;
case 1:
fprint(fd, "misordered keys %P, %P\n", &x, &y);
fail++;
break;
}
x = y;
}
if(b->type == Tpivot){
getval(b, b->nval-1, &y);
bp = getptr(&x, &fill);
if((c = getblk(bp, 0)) == nil){
fprint(fd, "corrupt block: %r\n");
fail++;
}
if(c != nil && badtree(fd, c, h - 1, &y, nil))
fail++;
dropblk(c);
}
if(b->type == Tpivot){
if(b->nbuf > 0){
getmsg(b, 0, &mx);
if(hi && keycmp(&mx, hi) >= 0){
fprint(fd, "out of range messages %P != %M\n", hi, &mx);
fail++;
}
}
for(i = 1; i < b->nbuf; i++){
getmsg(b, i, &my);
switch(my.op){
case Oinsert: /* new kvp */
case Odelete: /* delete kvp */
case Oclearb: /* delete kvp if exists */
break;
case Owstat: /* kvp dirent */
if((my.v[0] & ~(Owsize|Owmode|Owmtime|Owatime|Owuid|Owgid|Owmuid)) != 0){
fprint(fd, "invalid stat op %x\n", my.v[0]);
fail++;
}
break;
default:
fprint(fd, "invalid message op %d\n", my.op);
fail++;
break;
}
if(hi && keycmp(&y, hi) > 0){
fprint(fd, "out of range keys %P >= %P\n", &y, hi);
fail++;
}
if(keycmp(&mx, &my) == 1){
fprint(fd, "misordered keys %P, %P\n", &x, &y);
fail++;
break;
}
mx = my;
}
}
return fail;
}
static int
badfree(void)
{
Arange *r, *n;
int i, fail;
fail = 0;
for(i = 0; i < fs->narena; i++){
r = (Arange*)avlmin(fs->arenas[i].free);
for(n = (Arange*)avlnext(r); n != nil; n = (Arange*)avlnext(n)){
if(r->off >= n->off){
fprint(2, "misordered length %llx >= %llx\n", r->off, n->off);
fail++;
}
if(r->off+r->len >= n->off){
fprint(2, "overlaping range %llx+%llx >= %llx\n", r->off, r->len, n->off);
abort();
fail++;
}
r = n;
}
}
return fail;
}
int
checkfs(int fd)
{
int ok, height;
char *e, pfx[1], name[Keymax+1];
Tree *t;
Scan s;
Blk *b;
ok = 1;
if(badfree())
ok = 0;
if((b = getroot(&fs->snap, &height)) != nil){
if(badtree(fd, b, height-1, nil, 0))
ok = 0;
dropblk(b);
}
pfx[0] = Klabel;
btnewscan(&s, pfx, 1);
if((e = btenter(&fs->snap, &s)) != nil){
fprint(fd, "scanning snapshots: %s\n", e);
return 0;
}
while(1){
if((e = btnext(&fs->snap, &s, &s.kv)) != nil){
fprint(fd, "invalid snapshot tree: %s\n", e);
ok = 0;
break;
}
if(s.done)
break;
memcpy(name, s.kv.k+1, s.kv.nk-1);
name[s.kv.nk-1] = 0;
if((t = opensnap(name)) == nil){
fprint(2, "invalid snap label %s\n", name);
ok = 0;
break;
}
if((b = getroot(t, &height)) == nil){
fprint(fd, "unable to get root %B\n", t->bp);
ok = 0;
if((b = getblk(t->bp, GBnochk)) != nil){
showblk(fd, b, "corrupt", 0);
dropblk(b);
}
continue;
}
if(badtree(fd, b, height-1, nil, 0))
ok = 0;
dropblk(b);
}
return ok;
}