| 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 | } |