Fill st_ino in stat replies.
[vcfs.git] / blocktree.c
CommitLineData
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 11ssize_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
50static 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
76static 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 91static 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 193int 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 198int 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
209void 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
217static 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
229void btsortops(struct btop *ops, int numops)
230{
231 qsort(ops, numops, sizeof(*ops), (int (*)(const void *, const void *))opcmp);
232}
233
34b0b353 234block_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}