/*
* Copyright (c) 2013, Coraid, Inc.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Coraid nor the
* names of its contributors may be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL CORAID BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <u.h>
#include <libc.h>
#include <thread.h>
#include <fcall.h>
#include <9p.h>
#include "dat.h"
enum {
GMperBlk = BlkSize / sizeof(GMeta),
};
static void freeblob(uvlong);
static uvlong nget;
static uvlong nrm;
static uvlong nset;
static uvlong nalloc;
static uvlong nfree;
static uvlong nmiss;
static QLock mlock;
static QLock alock;
static QLock block;
static GMeta *mbuf;
static uvlong mblk;
void
reammeta(int fd)
{
GMeta *mp;
Blob *bp;
char *p, *e;
int i, j, n;
/* First the GMeta structures */
p = θmalloc(16 * BlkSize);
e = p + 16 * BlkSize;
mp = (GMeta *)p;
mp->next = 0;
mp->type = MTistring;
strcpy(mp->name, "invalid");
strcpy(mp->m.str, "errnt");
for(++mp, j = 2; (char *)mp < e; ++mp, ++j)
mp->next = j;
pwrite(fd, p, 16 * BlkSize, super.firstmeta * BlkSize);
memset(p, 0, sizeof(GMeta));
for(i = 16; i < super.nmeta; i += 16) {
n = super.nmeta - i;
if(n > 16)
n = 16;
for(mp = (GMeta *)p; (char *)mp < e; ++mp, ++j)
mp->next = j;
if((i/16) % 10 == 0) fprint(2, ",");
pwrite(fd, p, n * BlkSize, (super.firstmeta + i) * BlkSize);
}
/* Now the string/blob pool */
for(i = 0; i < super.nblob; i += 16) {
n = super.nblob - i;
if(n > 16)
n = 16;
memset(p, 0, n * BlkSize);
for(j = 0; j < n; ++j) {
bp = (Blob *)(p + j * BlkSize);
bp->len = 0x8000 | (BlkSize/2 - sizeof(short));
bp->next = (super.firstblob + i + j) * BlkSize + BlkSize/2;
bp = (Blob *)(p + j * BlkSize + BlkSize/2);
bp->len = 0x8000 | (BlkSize/2 - sizeof(short));
if(i + j + 1 < super.nblob)
bp->next = (super.firstblob + i + j + 1) * BlkSize;
}
if((i/16) % 10 == 0) fprint(2, ";");
pwrite(fd, p, n * BlkSize, (super.firstblob + i) * BlkSize);
}
free(p);
}
void
resetmeta(void)
{
qlock(&mlock);
if(mbuf) {
brelease(mblk);
mbuf = nil;
mblk = 0;
}
qunlock(&mlock);
}
static int
getmstruct(int fd, GMeta *buf, uvlong idx)
{
uvlong off, blk;
if(idx > super.nmeta * (BlkSize / sizeof(GMeta))) {
fprint(2, "Invalid metadata index: %ulld\n", idx);
return -1;
}
if(fd != -1)
return spread(fd, buf, sizeof(GMeta), idx * sizeof(GMeta) + super.firstmeta * BlkSize);
blk = idx / GMperBlk + super.firstmeta;
off = idx % GMperBlk;
qlock(&mlock);
if(blk != mblk) {
++nmiss;
if(mbuf)
brelease(mblk);
mbuf = cbread(blk);
mblk = blk;
}
memmove(buf, mbuf + off, sizeof(GMeta));
qunlock(&mlock);
return sizeof(GMeta);
}
static int
savemstruct(GMeta *buf, uvlong idx)
{
uvlong off, blk;
if(idx > super.nmeta * (BlkSize / sizeof(GMeta))) {
fprint(2, "Invalid metadata index: %ulld\n", idx);
return -1;
}
blk = idx / GMperBlk + super.firstmeta;
off = idx % GMperBlk;
qlock(&mlock);
if(blk != mblk) {
++nmiss;
if(mbuf)
brelease(mblk);
mbuf = cbread(blk);
mblk = blk;
}
memmove(mbuf + off, buf, sizeof(GMeta));
cbwrite(blk);
qunlock(&mlock);
return sizeof(GMeta);
}
static uvlong
allocmeta(GMeta *buf)
{
uvlong nmeta;
qlock(&alock);
if(super.ffmeta == 0) {
fprint(2, "Out of metadata space!\n");
qunlock(&alock);
return 0;
}
if(getmstruct(-1, buf, super.ffmeta) < 0) {
qunlock(&alock);
return 0;
}
++nalloc;
nmeta = super.ffmeta;
super.ffmeta = buf->next;
savesuper();
qunlock(&alock);
return nmeta;
}
static void
freemeta(uvlong idx)
{
GMeta buf;
qlock(&alock);
if(getmstruct(-1, &buf, idx) < 0) {
qlock(&alock);
return;
}
if(buf.type == MTstring || buf.type == MTblob)
freeblob(buf.m.val);
++nfree;
memset(&buf, 0, sizeof(GMeta));
buf.next = super.ffmeta;
super.ffmeta = idx;
savesuper();
savemstruct(&buf, idx);
qunlock(&alock);
}
/*
static void
insmeta(GMeta *buf, uvlong idx, uvlong after)
{
GMeta abuf;
if(getmstruct(-1, &abuf, after) < 0)
return;
buf->next = abuf.next;
abuf.next = idx;
savemstruct(&abuf, after);
savemstruct(buf, idx);
}
*/
static Blob *
getbstruct(int fd, uvlong bp)
{
Blob *b;
void *a;
uvlong blk;
ulong off, m;
blk = bp / BlkSize;
if(blk < super.firstblob || blk >= super.firstblob + super.nblob)
return nil;
off = bp % BlkSize;
m = BlkSize - off;
if(m > 32768)
m = 32768;
if(fd == -1)
b = (Blob *)((char *)cbread(blk) + off);
else {
b = θmalloc(m);
spread(fd, b, m, bp);
}
m = b->len & 0x7fff;
a = θmalloc(m + sizeof(short));
memmove(a, b, m + sizeof(short));
if(fd == -1)
brelease(blk);
else
free(b);
return a;
}
static int
savebstruct(Blob *b, uvlong bp)
{
return cwrite(b, b->len & 0x7fff, bp);
}
static Blob *
allocblob(int n, uvlong *bp)
{
Blob *cb, *pb, *nb;
uvlong cur, prev;
int an;
an = (n + BlobQuan - 1) & ~(BlobQuan - 1);
prev = 0;
cb = nil;
pb = nil;
qlock(&block);
for(cur = super.ffblob; cur; ) {
cb = getbstruct(-1, cur);
if(cb == nil) {
qunlock(&block);
return nil;
}
if((cb->len & 0x7fff) >= an)
break;
pb = cb;
prev = cur;
cur = cb->next;
}
if(cur == 0) {
qunlock(&block);
free(cb);
fprint(2, "No free blobs\n");
return nil;
}
if((cb->len & 0x7fff) >= an + BlobQuan) {
if(prev != 0) {
pb->next = cur + an;
savebstruct(pb, prev);
}
else {
super.ffblob = cur + an;
savesuper();
}
nb = (Blob *)((char *)cb + an);
nb->len = cb->len - an;
nb->next = cb->next;
savebstruct(nb, cur + an);
cb->len = an - sizeof(short);
}
else {
if(prev != 0) {
pb->next = cb->next;
savebstruct(pb, prev);
}
else {
super.ffblob = cb->next;
savesuper();
}
cb->len &= 0x7fff;
}
qunlock(&block);
free(pb);
if(bp)
*bp = cur;
return cb;
}
/*
* This is a pretty gross hack, and probably oversimplified.
* However, I'm not real happy with this part and may redo
* it anyway. When freeing a blob (or long string) in the pool,
* we don't attempt to coalesce them, we just add it on to
* the end of the list. Until we've done enough allocations
* to use up all the pool space once, we don't really care.
* Because the most common use for the pool space is strings
* and the quantum is set to 64, I suspect nearly all requests
* will be satisfied with a single quantum and coalescing
* wouldn't have significant benefit anyway. So there's
* the excuse for taking what is probably too simple an
* approach.
*/
static void
freeblob(uvlong bp)
{
Blob *b, *b2;
qlock(&block);
b = getbstruct(-1, bp);
b->len |= 0x8000;
b->next = 0;
savebstruct(b, bp);
b2 = getbstruct(-1, super.lfblob);
if(b2) {
b2->next = bp;
savebstruct(b2, super.lfblob);
super.lfblob = bp;
savesuper();
}
else
fprint(2, "Unexpected failure to read super.lfblob\n");
qunlock(&block);
}
void *
getblob(int fd, uvlong bp, int *n)
{
Blob *b;
void *a;
b = getbstruct(fd, bp);
if(b == nil)
return nil;
if(b->len & 0x8000) {
free(b);
return nil;
}
if(n)
*n = b->len;
a = θmalloc(b->len);
memmove(a, b->data, b->len);
free(b);
return a;
}
uvlong
setblob(void *blob, int n, uvlong bp)
{
Blob *b;
uvlong nbp;
b = getbstruct(-1, bp);
if(b) {
if(b->len == n) {
memmove(b->data, blob, n);
savebstruct(b, bp);
return bp;
}
else {
b->len |= 0x8000;
savebstruct(b, bp);
}
}
b = allocblob(n, &nbp);
if(b == nil)
return 0;
memmove(b->data, blob, n);
savebstruct(b, nbp);
free(b);
return nbp;
}
int
getmeta(int fd, uvlong stidx, char *name, MVal *val)
{
GMeta buf;
uvlong next;
++nget;
for(next = stidx; next; ) {
if(getmstruct(fd, &buf, next) < 0)
return MTnone;
if(strcmp(name, buf.name) == 0)
break;
next = buf.next;
}
if(next == 0)
return MTnone;
*val = buf.m;
return buf.type;
}
int
getmetaint(int fd, uvlong stidx, char *name, uvlong *val)
{
MVal x;
int typ;
typ = getmeta(fd, stidx, name, &x);
switch(typ) {
case MTint:
*val = x.val;
return typ;
default:
return MTnone;
}
}
char *
getmetastr(int fd, uvlong stidx, char *name)
{
MVal x;
char *p;
int typ;
typ = getmeta(fd, stidx, name, &x);
switch(typ) {
case MTistring:
p = estrdup9p(x.str);
return p;
case MTstring:
return getblob(fd, x.val, nil);
default:
return nil;
}
}
uvlong
setmeta(uvlong stidx, char *name, char *newname, uvlong val, int type)
{
GMeta buf, nbuf;
uvlong next, last, nmeta;
++nset;
last = 0;
for(next = stidx; next; ) {
if(getmstruct(-1, &buf, next) < 0)
return 0;
last = next;
if(strcmp(name, buf.name) == 0) {
if(type == MTistring) {
if(buf.type == MTstring)
freeblob(buf.m.val);
strcpy(buf.m.str, (char *)val);
}
else
buf.m.val = val;
buf.type = type; /* in case we're changing the string length */
if(newname)
strcpy(buf.name, newname);
savemstruct(&buf, last);
return last;
}
next = buf.next;
}
nmeta = allocmeta(&nbuf);
if(nmeta == 0)
return 0;
if(last == 0)
nbuf.next = 0;
else {
nbuf.next = buf.next;
buf.next = nmeta;
savemstruct(&buf, last);
}
nbuf.type = type;
if(newname)
strcpy(nbuf.name, newname);
else
strcpy(nbuf.name, name);
if(type == MTistring)
strcpy(nbuf.m.str, (char *)val);
else
nbuf.m.val = val;
savemstruct(&nbuf, nmeta);
return nmeta;
}
uvlong
setmetaint(uvlong stidx, char *name, char *newname, uvlong val)
{
return setmeta(stidx, name, newname, val, MTint);
}
uvlong
setmetastr(uvlong stidx, char *name, char *newname, char *s, uvlong bp)
{
uvlong nbp;
int n;
n = strlen(s);
if(n <= 7) {
return setmeta(stidx, name, newname, (uvlong)s, MTistring);
}
nbp = setblob(s, n + 1, bp);
return setmeta(stidx, name, newname, nbp, MTstring);
}
void
setmstruct(uvlong idx, uvlong next, char *name, int type, uvlong val)
{
GMeta mb;
if(getmstruct(-1, &mb, idx) < 0)
return;
mb.next = next;
strcpy(mb.name, name);
mb.type = type;
mb.m.val = val;
savemstruct(&mb, idx);
}
uvlong
setmetablob(uvlong stidx, char *name, char *newname, uchar *blob, int n, uvlong bp)
{
uvlong nbp;
nbp = setblob(blob, n, bp);
return setmeta(stidx, name, newname, nbp, MTblob);
}
uvlong
rmmeta(uvlong midx, uvlong victim)
{
GMeta buf, vbuf;
uvlong next;
++nrm;
if(getmstruct(-1, &vbuf, victim) < 0)
return midx;
if(midx == victim) {
next = vbuf.next;
freemeta(victim);
return next;
}
for(next = midx; next; ) {
if(getmstruct(-1, &buf, next) < 0)
return midx;
if(buf.next == victim) {
buf.next = vbuf.next;
freemeta(victim);
savemstruct(&buf, next);
return midx;
}
next = vbuf.next;
}
return midx;
}
void
rmmlist(uvlong midx)
{
GMeta buf;
uvlong next;
++nrm;
next = midx;
while(next) {
if(getmstruct(-1, &buf, next) < 0)
return;
freemeta(next);
next = buf.next;
}
}
static uvlong
promote1(uvlong midx, uvlong dblk, int)
{
uvlong *p;
uvlong nblk;
nblk = allocblock();
if(nblk == 0)
return 0;
p = cbclean(nblk);
p[0] = dblk;
cbwrite(nblk);
setmetaint(midx, "dblock", "index", nblk);
brelease(nblk);
return nblk;
}
static uvlong
promote2(uvlong midx, uvlong iblk, int)
{
uvlong *p;
uvlong nblk;
nblk = allocblock();
if(nblk == 0)
return 0;
p = cbclean(nblk);
p[0] = iblk;
cbwrite(nblk);
setmetaint(midx, "index", "indirect", nblk);
brelease(nblk);
return nblk;
}
static uvlong
promote3(uvlong midx, uvlong iblk, int levels)
{
uvlong *p;
char *name;
uvlong nblk;
if(levels == 1) {
nblk = allocblock();
if(nblk == 0)
return 0;
p = cbclean(nblk);
p[0] = iblk;
cbwrite(nblk);
brelease(nblk);
iblk = nblk;
}
nblk = allocblock();
if(nblk == 0)
return 0;
p = cbclean(nblk);
p[0] = iblk;
cbwrite(nblk);
if(levels == 1)
name = "index";
else
name = "indirect";
setmetaint(midx, name, "dblindir", nblk);
brelease(nblk);
return nblk;
}
static uvlong
doindir(int fd, uvlong iblk, int off, int allocate)
{
uvlong *p;
uvlong pblk;
if(iblk < super.firstdat || iblk >= super.nblk)
return 0;
if(fd != -1)
spread(fd, &pblk, sizeof(uvlong), iblk * BlkSize + off * sizeof(uvlong));
else {
p = cbread(iblk);
pblk = p[off];
if(pblk == 0) {
if(allocate) {
pblk = allocblock();
if(pblk == 0)
return 0;
p[off] = pblk;
cbwrite(iblk);
cbclean(pblk);
cbwrite(pblk);
brelease(pblk);
}
}
brelease(iblk);
}
return pblk;
}
uvlong
locate(int fd, uvlong midx, uvlong vblk, int allocate)
{
uvlong *p;
uvlong iblk, pblk;
ulong pperb;
int levels, l1off, l2off, l3off;
if(getmetaint(fd, midx, "dblindir", &iblk) == MTint)
levels = 3;
else if(getmetaint(fd, midx, "indirect", &iblk) == MTint)
levels = 2;
else if(getmetaint(fd, midx, "index", &iblk) == MTint)
levels = 1;
else if(getmetaint(fd, midx, "dblock", &iblk) == MTint)
levels = 0;
else
return 0;
pperb = BlkSize / sizeof(uvlong);
l1off = vblk % pperb;
l2off = (vblk / pperb) % pperb;
l3off = vblk / (pperb * pperb);
if(levels < 3 && l3off != 0) {
iblk = promote3(midx, iblk, levels);
levels = 3;
}
else if(levels < 2 && l2off != 0) {
iblk = promote2(midx, iblk, levels);
levels = 2;
}
else if(levels < 1 && l1off > 0) {
iblk = promote1(midx, iblk, levels);
levels = 1;
}
pblk = 0;
switch(levels) {
case 3:
iblk = doindir(fd, iblk, l3off, allocate);
case 2:
iblk = doindir(fd, iblk, l2off, allocate);
case 1:
if(iblk == 0)
return 0;
p = cbread(iblk);
pblk = p[l1off];
if(pblk == 0 && allocate) {
pblk = allocblock();
cbclean(pblk);
p[l1off] = pblk;
cbwrite(pblk);
brelease(pblk);
cbwrite(iblk);
}
brelease(iblk);
break;
case 0:
pblk = iblk;
if(pblk == 0 && allocate) {
pblk = allocblock();
cbclean(pblk);
setmetaint(midx, "dblock", nil, pblk);
cbwrite(pblk);
brelease(pblk);
}
break;
}
if(pblk < super.firstdat || pblk >= super.nblk) {
fprint(2, "Bogus block number found in locate: index:%ulld\n", iblk);
return 0;
}
return pblk;
}
void
freedata(uvlong midx)
{
uvlong *index1, *index2, *index3;
uvlong iblk;
int i, j, k;
if(getmetaint(-1, midx, "dblindir", &iblk) == MTint) {
if(iblk == 0)
return;
if(iblk < super.firstdat) {
fprint(2,"Bogus dblindir block in freedat: %ulld\n", iblk);
return;
}
index3 = cbread(iblk);
for(i = 0; i < BlkSize / sizeof(uvlong); ++i) {
if(index3[i] >= super.firstdat && index3[i] < super.nblk) {
index2 = cbread(index3[i]);
for(j = 0; j < BlkSize / sizeof(uvlong); ++j) {
if(index2[j] >= super.firstdat && index2[j] < super.nblk) {
index1 = cbread(index2[j]);
for(k = 0; k < BlkSize / sizeof(uvlong); ++k)
if(index1[k] != 0)
freeblock(index1[k]);
brelease(index2[j]);
freeblock(index2[j]);
}
}
brelease(index3[i]);
freeblock(index3[i]);
}
}
brelease(iblk);
freeblock(iblk);
}
else if(getmetaint(-1, midx, "indirect", &iblk) == MTint) {
if(iblk == 0)
return;
if(iblk < super.firstdat) {
fprint(2, "Bogus indirect block in freedat: %ulld\n", iblk);
return;
}
index2 = cbread(iblk);
for(i = 0; i < BlkSize / sizeof(uvlong); ++i) {
if(index2[i] >= super.firstdat && index2[i] < super.nblk) {
index1 = cbread(index2[i]);
for(j = 0; j < BlkSize / sizeof(uvlong); ++j)
if(index1[j] != 0)
freeblock(index1[j]);
brelease(index2[i]);
freeblock(index2[i]);
}
}
brelease(iblk);
freeblock(iblk);
}
else if(getmetaint(-1, midx, "index", &iblk) == MTint) {
if(iblk == 0)
return;
if(iblk < super.firstdat) {
fprint(2, "Bogus index block in freedat: %ulld\n", iblk);
return;
}
index1 = cbread(iblk);
for(i = 0; i < BlkSize / sizeof(uvlong); ++i)
if(index1[i] != 0)
freeblock(index1[i]);
brelease(iblk);
freeblock(iblk);
}
}
void
prmeta(int fd, uvlong qpath)
{
GMeta buf;
char *p;
uvlong meta, next;
int i, n;
meta = q2m(-1, qpath, 0);
if(meta == 0) {
fprint(fd, "no metadata\n");
return;
}
for(next = meta; next; ) {
if(getmstruct(-1, &buf, next) < 0)
break;
switch(buf.type) {
case MTnone:
break;
case MTint:
fprint(fd, "%s: %ulld(%016ullx)\n", buf.name, buf.m.val, buf.m.val);
break;
case MTistring:
fprint(fd, "%s: %s\n", buf.name, buf.m.str);
break;
case MTstring:
p = getblob(-1, buf.m.val, nil);
fprint(fd, "%s: %s\n", buf.name, p);
free(p);
break;
case MTblob:
fprint(fd, "%s:", buf.name);
p = getblob(-1, buf.m.val, &n);
for(i = 0; i < n; ++i)
fprint(fd, " %02x", p[i]);
fprint(fd, "\n");
free(p);
break;
}
next = buf.next;
}
}
static char mstatbuf[1024];
char *
prmstat(void)
{
char *p, *e;
p = mstatbuf;
e = p + nelem(mstatbuf);
p = seprint(p, e, "Metadata stats:\n");
p = seprint(p, e, "getmeta calls: %ulld\n", nget);
p = seprint(p, e, "setmeta calls: %ulld\n", nset);
p = seprint(p, e, "rmmeta calls: %ulld\n", nrm);
p = seprint(p, e, "alloc calls: %ulld\n", nalloc);
p = seprint(p, e, "free calls: %ulld\n", nfree);
seprint(p, e, "misses: %ulld\n", nmiss);
return mstatbuf;
}
static uvlong
qoffset(ulong bucket)
{
return BlkSize * (super.nhashblk + 1) + bucket * sizeof(uvlong);
}
void
recovermeta(int fd)
{
GMeta mb;
uvlong midx1, midx2, qhnext, qb, n;
int saidit;
/* First set all the marker flags */
fprint(fd, "Setting flags\n");
for(midx1 = 1; midx1 < super.nmeta * GMperBlk; ++midx1) {
getmstruct(-1, &mb, midx1);
mb.type |= 0x80;
savemstruct(&mb, midx1);
}
/* Go through all the q2m hash table and mark referenced ones in use */
fprint(fd, "Marking ones referenced from QID hash table\n");
for(qb = 0; qb < super.nht; ++qb) {
cread(&midx1, sizeof(uvlong), qoffset(qb));
qhnext = 0;
n = 0;
saidit = 0;
while(midx1 != 0) {
++n;
getmstruct(-1, &mb, midx1);
mb.type &= 0x7f;
if(mb.type == MTnone && !saidit) {
fprint(fd, "Unexpected null metadatum at %ulld in bucket %ulld\n", midx1, qb);
saidit = 1;
}
midx2 = midx1;
midx1 = mb.next;
if(strcmp(mb.name, "qhnext") == 0 && mb.m.val != 0) {
qhnext = mb.m.val;
fprint(fd, "Warning, QID collision qb:%ulld midx:%ulld\n", qb, midx2);
}
savemstruct(&mb, midx2);
if(midx1 == 0) {
midx1 = qhnext;
qhnext = 0;
}
}
if(n > 128)
fprint(fd, "Unexpected large list at qb %ulld, size %ulld\n", qb, n);
}
fprint(fd, "Sizing old free list\n");
n = 0;
for(midx1 = super.ffmeta; midx1 != 0; ) {
++n;
if(n >= super.nmeta * GMperBlk) {
fprint(fd, "Cycle in old free list?\n");
break;
}
getmstruct(-1, &mb, midx1);
midx1 = mb.next;
}
fprint(fd, "Old free list has %ulld structures\n", n);
/* Reclaim the free ones */
fprint(fd, "Rebuilding free list\n");
n = 0;
super.ffmeta = 0;
for(midx1 = super.nmeta * GMperBlk - 1; midx1 != 0; --midx1) {
getmstruct(-1, &mb, midx1);
if(mb.type & 0x80) {
memset(&mb, 0, sizeof(GMeta));
mb.next = super.ffmeta;
super.ffmeta = midx1;
savemstruct(&mb, midx1);
++n;
}
}
savesuper();
fprint(fd, "Recovered %ulld free metadata structures\n", n);
}
static int
markinuse(char *shadow, uvlong blk)
{
long byt;
int bit, old;
if(blk < super.firstdat || blk >= super.nblk)
return -1;
byt = blk / 8;
bit = blk % 8;
old = shadow[byt] & (1 << bit);
shadow[byt] &= ~(1 << bit);
return old;
}
/* Dealing with humans always makes the code ugly. */
static char *idxnames[] = {"data", "index", "indirect", "dblindir"};
static void
chkidxalloc(int fd, char *shadow, uvlong blk, uvlong midx, int lev)
{
uvlong *iblk;
int i;
if(blk == 0)
return;
switch(markinuse(shadow, blk)) {
case -1:
fprint(fd, "Bogus %s block: %ulld metadataum %ulld\n", idxnames[lev+1], blk, midx);
return;
case 0:
fprint(fd, "Doubly allocated %s block: %ulld meta %ulld\n", idxnames[lev+1], blk, midx);
break;
}
iblk = cbread(blk);
if(iblk == nil) {
fprint(fd, "unexpected error reading block %ulld\n", blk);
return;
}
for(i = 0; i < BlkSize / sizeof(uvlong); ++i) {
if(iblk[i] == 0)
continue;
if(lev > 0)
chkidxalloc(fd, shadow, iblk[i], midx, lev - 1);
else {
switch(markinuse(shadow, iblk[i])) {
case -1:
fprint(fd, "Bogus %s block: %ulld in %s block %ulld meta %ulld\n",
idxnames[lev], iblk[i], idxnames[lev+1], blk, midx);
i = BlkSize / sizeof(uvlong);
break;
case 0:
fprint(fd, "Doubly allocated %s block: %ulld in %s block %ulld meta %ulld\n",
idxnames[lev], iblk[i], idxnames[lev+1], blk, midx);
break;
}
}
}
brelease(blk);
}
void
checkalloc(int fd)
{
GMeta mb;
uvlong *hblk;
char *shadow, *fb;
uvlong idx;
long i;
int j, k, l;
fprint(fd, "Initializing shadow free map\n");
shadow = θmalloc(super.nfreemap * BlkSize);
for(i = super.firstdat; i < super.nblk; ++i)
shadow[i/8] |= 1 << (i % 8);
for(i = 0, j = 0; j < super.nhashblk; ++j) {
hblk = cbread(j + 1);
for(k = 0; k < BlkSize / sizeof(uvlong) && i < super.nht; ++k, ++i) {
if(i % 100000 == 0)
fprint(fd, ".");
idx = hblk[k];
while(idx != 0) {
switch(markinuse(shadow, idx)) {
case -1:
fprint(fd, "Bogus block number in hash list for bucket %ld\n", i);
idx = 0;
break;
case 0:
fprint(fd, "Doubly allocated block in hash table: %ulld bucket %ld\n", idx, i);
default:
if(cread(&idx, sizeof(uvlong), idx * BlkSize + (BlkSize - sizeof(uvlong))) < 0) {
fprint(fd, "Error reading bucket next link: %ld %ulld\n", i, idx);
idx = 0;
}
if(idx != 0)
fprint(fd, ",");
break;
}
}
}
brelease(j + 1);
}
fprint(fd, "Scanning metadata\n");
for(idx = 1; idx < super.nmeta * GMperBlk; ++idx) {
if(idx % 100000 == 0)
fprint(fd, ".");
getmstruct(-1, &mb, idx);
if(mb.type != MTint)
continue;
if(strcmp(mb.name, "index") == 0)
chkidxalloc(fd, shadow, mb.m.val, idx, 0);
else if(strcmp(mb.name, "indirect") == 0)
chkidxalloc(fd, shadow, mb.m.val, idx, 1);
else if(strcmp(mb.name, "dblindir") == 0)
chkidxalloc(fd, shadow, mb.m.val, idx, 2);
}
fprint(fd, "Comparing to on-disk free map\n");
l = 0;
for(j = 0; j < super.nfreemap; ++j) {
fb = cbread(super.freemap + j);
for(k = 0; k < BlkSize; ++k) {
if(fb[k] != shadow[j*BlkSize+k]) {
if(++l < 10) /* don't flood the output with too many */
fprint(fd, "%d:%02ux-%02ux\n", j*BlkSize+k, fb[k], (uchar)shadow[j*BlkSize+k]);
if((fb[k] & shadow[j*BlkSize+k]) != fb[k]) {
fprint(fd, "Marking in use\n");
fb[k] &= shadow[j*BlkSize + k];
cbwrite(super.freemap + j);
}
}
}
brelease(super.freemap + j);
}
free(shadow);
}
void
mprint(int fd, uvlong idx)
{
GMeta mb;
char *p;
int i, n;
getmstruct(-1, &mb, idx);
switch(mb.type) {
case MTnone:
fprint(fd, "Meta:%ulld name:%s type:none next:%ulld val:%ulld\n", idx, mb.name, mb.next, mb.m.val);
break;
case MTint:
fprint(fd, "Meta:%ulld name:%s type:%d next:%ulld val:%ulld(%016ullx)\n", idx, mb.name, mb.type, mb.next, mb.m.val, mb.m.val);
break;
case MTistring:
fprint(fd, "Meta:%ulld name:%s type:%d next:%ulld val:%s\n", idx, mb.name, mb.type, mb.next, mb.m.str);
break;
case MTstring:
p = getblob(-1, mb.m.val, nil);
fprint(fd, "Meta:%ulld name:%s type:%d next:%ulld val:(%ulld)%s\n", idx, mb.name, mb.type, mb.next, mb.m.val, p);
free(p);
break;
case MTblob:
fprint(fd, "Meta:%ulld name:%s type:%d next:%ulld ", idx, mb.name, mb.type, mb.next);
p = getblob(-1, mb.m.val, &n);
for(i = 0; i < n; ++i)
fprint(fd, " %02x", p[i]);
fprint(fd, "\n");
free(p);
break;
default:
fprint(fd, "unknown Meta:%ulld type%d next%ulld\n", idx, mb.type, mb.next);
break;
}
}
void
mpred(int fd, uvlong idx)
{
GMeta mb;
uvlong i;
for(i = 1; i < super.nmeta * GMperBlk; ++i) {
getmstruct(-1, &mb, i);
if(mb.type != MTnone && mb.next == idx) {
fprint(fd, "Meta:%ulld predecessor:%ulld\n", idx, i);
mprint(fd, i);
return;
}
}
}
static void
idxuse(int fd, uvlong iblk, uvlong blk, uvlong midx, int lev)
{
uvlong *bp;
int i;
if(iblk == 0)
return;
if(iblk == blk)
fprint(fd, "%s entry meta: %ulld\n", idxnames[lev+1], midx);
bp = cbread(iblk);
if(bp == nil) {
fprint(fd, "error reading block %ulld\n", iblk);
return;
}
for(i = 0; i < BlkSize / sizeof(uvlong); ++i) {
if(bp[i] == blk)
fprint(fd, "%s block in %s block %ulld in meta %ulld\n", idxnames[lev], idxnames[lev+1], iblk, midx);
if(lev > 0)
idxuse(fd, bp[i], blk, midx, lev - 1);
}
brelease(iblk);
}
void
blockuse(int fd, uvlong blk)
{
GMeta mb;
// PQMap *pq, *pend;
// char *p;
uvlong /* hlist, */ midx;
// long i;
if(blk == 0) {
fprint(fd, "superblock\n");
return;
}
if(blk < super.nhashblk + 1) {
fprint(fd, "P2Q hash table\n");
return;
}
if(blk < 2 * super.nhashblk + 1) {
fprint(fd, "Q2M hash table\n");
return;
}
if(blk >= super.freemap && blk < super.freemap + super.nfreemap) {
fprint(fd, "free bitmap\n");
return;
}
if(blk >= super.firstmeta && blk < super.firstmeta + super.nmeta) {
fprint(fd, "metadata structure pool\n");
return;
}
if(blk >= super.firstblob && blk < super.firstblob + super.nblob) {
fprint(fd, "string/blob pool\n");
return;
}
#ifdef NOTDEF
for(i = 0; i < super.nht; ++i) {
if(i % 100000 == 0)
fprint(fd, ".");
if(cread(&hlist, sizeof(uvlong), BlkSize + i * sizeof(uvlong)) < 0) {
fprint(fd, "Error reading bucket %ld\n", i);
continue;
}
if(hlist == blk)
fprint(fd, "P2Q hash bucket %ld\n", i);
while(hlist != 0) {
p = cbread(hlist);
if(p == nil) {
fprint(fd, "Error reading hash list block %ulld\n", hlist);
break;
}
pend = (PQMap *)(p + BlkSize);
--pend;
// for(pq = (PQMap *)p; pq < pend && pq->qpath != 0; pq = nextpq(pq)) {
// }
}
}
#endif
for(midx = 1; midx < super.nmeta * GMperBlk; ++midx) {
getmstruct(-1, &mb, midx);
if(mb.type != MTint)
continue;
if(mb.m.val == 0)
continue;
if(strcmp(mb.name, "index") == 0)
idxuse(fd, mb.m.val, blk, midx, 0);
else if(strcmp(mb.name, "indirect") == 0)
idxuse(fd, mb.m.val, blk, midx, 1);
else if(strcmp(mb.name, "dblindir") == 0)
idxuse(fd, mb.m.val, blk, midx, 2);
}
}
void
fixfamilies(int fd)
{
GMeta mb;
uvlong midx;
for(midx = 1; midx < super.nmeta * GMperBlk; ++midx) {
if(getmstruct(-1, &mb, midx) < 0)
continue;
if(mb.type != MTint)
continue;
if(strcmp(mb.name, "child") != 0 && strcmp(mb.name, "sib") != 0)
continue;
if(mb.m.val == 0)
continue;
if(q2m(-1, mb.m.val, 0) == 0) {
fprint(fd, "clearing dangling %s:%ulld in meta struct %ulld\n", mb.name, mb.m.val, midx);
mb.m.val = 0;
savemstruct(&mb, midx);
}
}
}
|
