d5cf5351 |
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)) |
2a9c9b15 |
9 | #define ISDELOP(op) (((op).buf == NULL) && ((op).fillfn == NULL)) |
d5cf5351 |
10 | |
34b0b353 |
11 | ssize_t btget(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len, size_t blsize) |
d5cf5351 |
12 | { |
13 | int d; |
14 | block_t c, sel; |
34b0b353 |
15 | struct btnode indir[1 << blsize]; |
d5cf5351 |
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. */ |
34b0b353 |
27 | if((bl >> (d * blsize)) > 0) { |
d5cf5351 |
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 */ |
34b0b353 |
36 | if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0) |
d5cf5351 |
37 | return(-1); |
38 | c = sz / sizeof(struct btnode); |
34b0b353 |
39 | sel = bl >> ((d - 1) * blsize); |
d5cf5351 |
40 | if(sel >= c) { |
41 | errno = ERANGE; |
42 | return(-1); |
43 | } |
44 | tree = &indir[sel]; |
34b0b353 |
45 | bl &= (1LL << ((d - 1) * blsize)) - 1; |
d5cf5351 |
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 | |
2a9c9b15 |
56 | if(ISDELOP(*op)) { |
57 | leaf->d = 0; |
58 | return(0); |
59 | } |
d5cf5351 |
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 | */ |
34b0b353 |
91 | static int btputmany2(struct store *st, struct btnode *tree, struct btop *ops, int numops, size_t blsize, block_t bloff) |
d5cf5351 |
92 | { |
93 | int i, subops, d, f, hasid; |
94 | block_t c, sel, bl, nextsz; |
95 | struct addr na; |
34b0b353 |
96 | struct btnode indir[1 << blsize]; |
d5cf5351 |
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; ) { |
2a9c9b15 |
105 | if(ops[i].blk < bloff) { |
106 | errno = ERANGE; |
107 | return(-1); |
108 | } |
d5cf5351 |
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 | |
34b0b353 |
118 | if(f && (bl == (1LL << (d * blsize)))) { |
d5cf5351 |
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 */ |
34b0b353 |
138 | for(bl = numops - 1; bl > 0; d++, bl <<= blsize); |
d5cf5351 |
139 | tree->d = d; |
140 | c = 0; |
141 | hasid = 1; |
142 | } else { |
143 | /* Get indirect block */ |
144 | if(!hasid) { |
34b0b353 |
145 | if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0) |
d5cf5351 |
146 | return(-1); |
147 | c = sz / sizeof(struct btnode); |
148 | hasid = 1; |
149 | } |
150 | } |
151 | |
34b0b353 |
152 | sel = bl >> ((d - 1) * blsize); |
d5cf5351 |
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 | } |
34b0b353 |
167 | nextsz = 1LL << ((d - 1) * blsize); |
d5cf5351 |
168 | subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz); |
34b0b353 |
169 | if(btputmany2(st, &indir[sel], ops + i, subops, blsize, bloff + (sel * nextsz))) |
d5cf5351 |
170 | return(-1); |
171 | i += subops; |
172 | |
34b0b353 |
173 | if((sel == (1 << blsize) - 1) && (indir[sel].d == ((d - 1) | 0x80))) { |
2a9c9b15 |
174 | /* Filled up */ |
d5cf5351 |
175 | tree->d |= 0x80; |
176 | f = 1; |
2a9c9b15 |
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 | } |
d5cf5351 |
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 | |
34b0b353 |
193 | int btputmany(struct store *st, struct btnode *tree, struct btop *ops, int numops, size_t blsize) |
d5cf5351 |
194 | { |
34b0b353 |
195 | return(btputmany2(st, tree, ops, numops, blsize, 0)); |
d5cf5351 |
196 | } |
197 | |
34b0b353 |
198 | int btput(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len, size_t blsize) |
d5cf5351 |
199 | { |
34b0b353 |
200 | struct btop ops; |
d5cf5351 |
201 | |
34b0b353 |
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)); |
d5cf5351 |
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 | { |
2a9c9b15 |
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); |
d5cf5351 |
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 | |
34b0b353 |
234 | block_t btcount(struct store *st, struct btnode *tree, size_t blsize) |
d5cf5351 |
235 | { |
236 | int d, f; |
34b0b353 |
237 | struct btnode indir[1 << blsize]; |
d5cf5351 |
238 | block_t c, ret; |
239 | ssize_t sz; |
240 | |
241 | d = tree->d & 0x7f; |
242 | f = tree->d & 0x80; |
243 | |
244 | if(f) |
34b0b353 |
245 | return(1LL << (d * blsize)); |
d5cf5351 |
246 | |
247 | if(d == 0) |
248 | return(0); |
249 | |
250 | ret = 0; |
251 | while(1) { |
34b0b353 |
252 | if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0) |
d5cf5351 |
253 | return(-1); |
254 | c = sz / sizeof(struct btnode); |
34b0b353 |
255 | ret += (c - 1) * (1LL << ((d - 1) * blsize)); |
d5cf5351 |
256 | d = indir[c - 1].d & 0x7f; |
257 | f = indir[c - 1].d & 0x80; |
258 | if(f) |
34b0b353 |
259 | return(ret + (1LL << (d * blsize))); |
d5cf5351 |
260 | tree = &indir[c - 1]; |
261 | } |
262 | } |