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