blocktree.c

   1 #include <stdlib.h>
   2 #include <errno.h>
   3 #include <string.h>
   4
   5 #include "store.h"
   6 #include "blocktree.h"
   7
   8 #define min(a, b) (((b) < (a))?(b):(a))
   9
  10 ssize_t btget(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len)
  11 {
  12     int d;
  13     block_t c, sel;
  14     struct btnode indir[BT_INDSZ];
  15     ssize_t sz;
  16
  17     if(tree->d == 0) {
  18         errno = ERANGE;
  19         return(-1);
  20     }
  21     while(1) {
  22         d = tree->d & 0x7f;
  23         /* This check should really only be necessary on the first
  24          * iteration, but I felt it was easier to put it in the
  25          * loop. */
  26         if((bl >> (d * BT_INDBITS)) > 0) {
  27             errno = ERANGE;
  28             return(-1);
  29         }
  30
  31         if(d == 0)
  32             return(storeget(st, buf, len, &tree->a));
  33
  34         /* Luckily, this is tail recursive */
  35         if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
  36             return(-1);
  37         c = sz / sizeof(struct btnode);
  38         sel = bl >> ((d - 1) * BT_INDBITS);
  39         if(sel >= c) {
  40             errno = ERANGE;
  41             return(-1);
  42         }
  43         tree = &indir[sel];
  44         bl &= (1LL << ((d - 1) * BT_INDBITS)) - 1;
  45     }
  46     return(0);
  47 }
  48
  49 static int btputleaf(struct store *st, struct btnode *leaf, struct btop *op, block_t bloff)
  50 {
  51     void *buf;
  52     struct addr na;
  53     int ret;
  54
  55     buf = NULL;
  56     if(op->buf == NULL) {
  57         buf = op->buf = malloc(op->len);
  58         if(op->fillfn(buf, op->len, op->pdata))
  59             return(-1);
  60     }
  61     ret = storeput(st, op->buf, op->len, &na);
  62     if(buf != NULL)
  63         free(buf);
  64     if(ret)
  65         return(-1);
  66     leaf->d = 0x80;
  67     leaf->a = na;
  68     return(0);
  69 }
  70
  71 static int countops(struct btop *ops, int numops, block_t bloff, block_t maxbl)
  72 {
  73     int i;
  74
  75     for(i = 0; i < numops; i++) {
  76         if(ops[i].blk - bloff >= maxbl)
  77             break;
  78     }
  79     return(i);
  80 }
  81
  82 /*
  83  * blputmany() in many ways makes the code uglier, but it saves a
  84  * *lot* of space, since it doesn't need to store intermediary blocks.
  85  */
  86 static int btputmany2(struct store *st, struct btnode *tree, struct btop *ops, int numops, block_t bloff)
  87 {
  88     int i, subops, d, f, hasid;
  89     block_t c, sel, bl, nextsz;
  90     struct addr na;
  91     struct btnode indir[BT_INDSZ];
  92     ssize_t sz;
  93
  94     d = tree->d & 0x7f;
  95     f = tree->d & 0x80;
  96
  97     hasid = 0;
  98
  99     for(i = 0; i < numops; ) {
 100         bl = ops[i].blk - bloff;
 101
 102         if((d == 0) && (bl == 0)) {
 103             if(btputleaf(st, tree, ops, bloff))
 104                 return(-1);
 105             i++;
 106             continue;
 107         }
 108
 109         if(f && (bl == (1LL << (d * BT_INDBITS)))) {
 110             /* New level of indirection */
 111             if(hasid) {
 112                 if(storeput(st, indir, c * sizeof(struct btnode), &na))
 113                     return(-1);
 114                 tree->a = na;
 115             }
 116             indir[0] = *tree;
 117             tree->d = ++d;
 118             f = 0;
 119             c = 1;
 120             hasid = 1;
 121         } else if(d == 0) {
 122             /* New tree */
 123             if(bl != 0) {
 124                 errno = ERANGE;
 125                 return(-1);
 126             }
 127             /* Assume that numops == largest block number + 1 -- gaps
 128              * will be detected as errors later */
 129             for(bl = numops - 1; bl > 0; d++, bl <<= BT_INDBITS);
 130             tree->d = d;
 131             c = 0;
 132             hasid = 1;
 133         } else {
 134             /* Get indirect block */
 135             if(!hasid) {
 136                 if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
 137                     return(-1);
 138                 c = sz / sizeof(struct btnode);
 139                 hasid = 1;
 140             }
 141         }
 142
 143         sel = bl >> ((d - 1) * BT_INDBITS);
 144         if(sel > c) {
 145             errno = ERANGE;
 146             return(-1);
 147         }
 148
 149         if(sel == c) {
 150             /* Append new */
 151             if((c > 0) && (!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1)))) {
 152                 errno = ERANGE;
 153                 return(-1);
 154             }
 155             indir[c].d = 0;
 156             c++;
 157         }
 158         nextsz = 1LL << ((d - 1) * BT_INDBITS);
 159         subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
 160         if(btputmany2(st, &indir[sel], ops + i, subops, bloff + (sel * nextsz)))
 161             return(-1);
 162         i += subops;
 163
 164         if((sel == BT_INDSZ - 1) && (indir[sel].d == ((d - 1) | 0x80))) {
 165             tree->d |= 0x80;
 166             f = 1;
 167         }
 168     }
 169     if(hasid) {
 170         if(storeput(st, indir, c * sizeof(struct btnode), &na))
 171             return(-1);
 172         tree->a = na;
 173     }
 174     return(0);
 175 }
 176
 177 int btputmany(struct store *st, struct btnode *tree, struct btop *ops, int numops)
 178 {
 179     return(btputmany2(st, tree, ops, numops, 0));
 180 }
 181
 182 int btput(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len)
 183 {
 184     struct btop ops[1];
 185
 186     ops[0].blk = bl;
 187     ops[0].buf = buf;
 188     ops[0].len = len;
 189     return(btputmany(st, tree, ops, 1));
 190 }
 191
 192 void btmkop(struct btop *op, block_t bl, void *buf, size_t len)
 193 {
 194     memset(op, 0, sizeof(*op));
 195     op->blk = bl;
 196     op->buf = buf;
 197     op->len = len;
 198 }
 199
 200 static int opcmp(const struct btop **op1, const struct btop **op2)
 201 {
 202     return((*op1)->blk - (*op2)->blk);
 203 }
 204
 205 void btsortops(struct btop *ops, int numops)
 206 {
 207     qsort(ops, numops, sizeof(*ops), (int (*)(const void *, const void *))opcmp);
 208 }
 209
 210 /*
 211 Obsoleted
 212
 213 int btappend(struct store *st, struct btnode *tree, void *buf, size_t len)
 214 {
 215     int d, f;
 216     struct btnode indir[BT_INDSZ];
 217     struct addr na;
 218     block_t c;
 219     ssize_t sz;
 220
 221     d = tree->d & 0x7f;
 222     f = tree->d & 0x80;
 223
 224     if(f) {
 225         if(storeput(st, buf, len, &na))
 226             return(-1);
 227         indir[0] = *tree;
 228         indir[1].d = 0x80;
 229         indir[1].a = na;
 230         if(storeput(st, indir, 2 * sizeof(*indir), &na))
 231             return(-1);
 232         tree->d = d + 1;
 233         tree->a = na;
 234         return(0);
 235     }
 236
 237     if(d == 0) {
 238         if(storeput(st, buf, len, &na))
 239             return(-1);
 240         tree->d |= 0x80;
 241         tree->a = na;
 242         return(0);
 243     }
 244
 245     if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
 246         return(-1);
 247     c = sz / sizeof(struct btnode);
 248     if(!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1))) {
 249         if(btappend(st, &indir[c - 1], buf, len))
 250             return(-1);
 251         if(storeput(st, indir, sz, &na))
 252             return(-1);
 253         tree->a = na;
 254         if((indir[c - 1].d & 0x80) && ((indir[c - 1].d & 0x7f) == (d - 1)))
 255             tree->d |= 0x80;
 256         return(0);
 257     }
 258
 259     if(storeput(st, buf, len, &na))
 260         return(-1);
 261     indir[c].d = 0x80;
 262     indir[c].a = na;
 263     if(storeput(st, indir, sz + sizeof(struct btnode), &na))
 264         return(-1);
 265     tree->a = na;
 266     return(0);
 267 }
 268 */
 269
 270 block_t btcount(struct store *st, struct btnode *tree)
 271 {
 272     int d, f;
 273     struct btnode indir[BT_INDSZ];
 274     block_t c, ret;
 275     ssize_t sz;
 276
 277     d = tree->d & 0x7f;
 278     f = tree->d & 0x80;
 279
 280     if(f)
 281         return(1LL << (d * BT_INDBITS));
 282
 283     if(d == 0)
 284         return(0);
 285
 286     ret = 0;
 287     while(1) {
 288         if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
 289             return(-1);
 290         c = sz / sizeof(struct btnode);
 291         ret += (c - 1) * (1LL << ((d - 1) * BT_INDBITS));
 292         d = indir[c - 1].d & 0x7f;
 293         f = indir[c - 1].d & 0x80;
 294         if(f)
 295             return(ret + (1LL << (d * BT_INDBITS)));
 296         tree = &indir[c - 1];
 297     }
 298 }