1 /*
2 * Copyright (C) 2010 Jeroen Oortwijn <oortwijn@gmail.com>
3 *
4 * Partly based on the Haiku BFS driver by
5 * Axel Dörfler <axeld@pinc-software.de>
6 *
7 * Also inspired by the Linux BeFS driver by
8 * Will Dyson <will_dyson@pobox.com>, et al.
9 *
10 * This file may be redistributed under the terms of the
11 * GNU Lesser General Public License.
12 */
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <unistd.h>
16 #include <string.h>
17 #include <inttypes.h>
18
19 #include "superblocks.h"
20
21 #define B_OS_NAME_LENGTH 0x20
22 #define SUPER_BLOCK_MAGIC1 0x42465331 /* BFS1 */
23 #define SUPER_BLOCK_MAGIC2 0xdd121031
24 #define SUPER_BLOCK_MAGIC3 0x15b6830e
25 #define SUPER_BLOCK_FS_ENDIAN 0x42494745 /* BIGE */
26 #define INODE_MAGIC1 0x3bbe0ad9
27 #define BPLUSTREE_MAGIC 0x69f6c2e8
28 #define BPLUSTREE_NULL -1LL
29 #define NUM_DIRECT_BLOCKS 12
30 #define B_UINT64_TYPE 0x554c4c47 /* ULLG */
31 #define KEY_NAME "be:volume_id"
32 #define KEY_SIZE 8
33
34 #define FS16_TO_CPU(value, fs_is_le) (fs_is_le ? le16_to_cpu(value) \
35 : be16_to_cpu(value))
36 #define FS32_TO_CPU(value, fs_is_le) (fs_is_le ? le32_to_cpu(value) \
37 : be32_to_cpu(value))
38 #define FS64_TO_CPU(value, fs_is_le) (fs_is_le ? le64_to_cpu(value) \
39 : be64_to_cpu(value))
40
41 typedef struct block_run {
42 int32_t allocation_group;
43 uint16_t start;
44 uint16_t len;
45 } __attribute__((packed)) block_run, inode_addr;
46
47 struct befs_super_block {
48 char name[B_OS_NAME_LENGTH];
49 int32_t magic1;
50 int32_t fs_byte_order;
51 uint32_t block_size;
52 uint32_t block_shift;
53 int64_t num_blocks;
54 int64_t used_blocks;
55 int32_t inode_size;
56 int32_t magic2;
57 int32_t blocks_per_ag;
58 int32_t ag_shift;
59 int32_t num_ags;
60 int32_t flags;
61 block_run log_blocks;
62 int64_t log_start;
63 int64_t log_end;
64 int32_t magic3;
65 inode_addr root_dir;
66 inode_addr indices;
67 int32_t pad[8];
68 } __attribute__((packed));
69
70 typedef struct data_stream {
71 block_run direct[NUM_DIRECT_BLOCKS];
72 int64_t max_direct_range;
73 block_run indirect;
74 int64_t max_indirect_range;
75 block_run double_indirect;
76 int64_t max_double_indirect_range;
77 int64_t size;
78 } __attribute__((packed)) data_stream;
79
80 struct befs_inode {
81 int32_t magic1;
82 inode_addr inode_num;
83 int32_t uid;
84 int32_t gid;
85 int32_t mode;
86 int32_t flags;
87 int64_t create_time;
88 int64_t last_modified_time;
89 inode_addr parent;
90 inode_addr attributes;
91 uint32_t type;
92 int32_t inode_size;
93 uint32_t etc;
94 data_stream data;
95 int32_t pad[4];
96 int32_t small_data[0];
97 } __attribute__((packed));
98
99 struct small_data {
100 uint32_t type;
101 uint16_t name_size;
102 uint16_t data_size;
103 char name[0];
104 } __attribute__((packed));
105
106 struct bplustree_header {
107 uint32_t magic;
108 uint32_t node_size;
109 uint32_t max_number_of_levels;
110 uint32_t data_type;
111 int64_t root_node_pointer;
112 int64_t free_node_pointer;
113 int64_t maximum_size;
114 } __attribute__((packed));
115
116 struct bplustree_node {
117 int64_t left_link;
118 int64_t right_link;
119 int64_t overflow_link;
120 uint16_t all_key_count;
121 uint16_t all_key_length;
122 char name[0];
123 } __attribute__((packed));
124
125 static unsigned char *get_block_run(blkid_probe pr, const struct befs_super_block *bs,
126 const struct block_run *br, int fs_le)
127 {
128 return blkid_probe_get_buffer(pr,
129 ((uint64_t) FS32_TO_CPU(br->allocation_group, fs_le)
130 << FS32_TO_CPU(bs->ag_shift, fs_le)
131 << FS32_TO_CPU(bs->block_shift, fs_le))
132 + ((uint64_t) FS16_TO_CPU(br->start, fs_le)
133 << FS32_TO_CPU(bs->block_shift, fs_le)),
134 (uint64_t) FS16_TO_CPU(br->len, fs_le)
135 << FS32_TO_CPU(bs->block_shift, fs_le));
136 }
137
138 static unsigned char *get_custom_block_run(blkid_probe pr,
139 const struct befs_super_block *bs,
140 const struct block_run *br,
141 int64_t offset, uint32_t length, int fs_le)
142 {
143 if (offset + length > (int64_t) FS16_TO_CPU(br->len, fs_le)
144 << FS32_TO_CPU(bs->block_shift, fs_le))
145 return NULL;
146
147 return blkid_probe_get_buffer(pr,
148 ((uint64_t) FS32_TO_CPU(br->allocation_group, fs_le)
149 << FS32_TO_CPU(bs->ag_shift, fs_le)
150 << FS32_TO_CPU(bs->block_shift, fs_le))
151 + ((uint64_t) FS16_TO_CPU(br->start, fs_le)
152 << FS32_TO_CPU(bs->block_shift, fs_le))
153 + offset,
154 length);
155 }
156
157 static unsigned char *get_tree_node(blkid_probe pr, const struct befs_super_block *bs,
158 const struct data_stream *ds,
159 int64_t start, uint32_t length, int fs_le)
160 {
161 if (start < (int64_t) FS64_TO_CPU(ds->max_direct_range, fs_le)) {
162 int64_t br_len;
163 size_t i;
164
165 for (i = 0; i < NUM_DIRECT_BLOCKS; i++) {
166 br_len = (int64_t) FS16_TO_CPU(ds->direct[i].len, fs_le)
167 << FS32_TO_CPU(bs->block_shift, fs_le);
168 if (start < br_len)
169 return get_custom_block_run(pr, bs,
170 &ds->direct[i],
171 start, length, fs_le);
172 start -= br_len;
173 }
174 } else if (start < (int64_t) FS64_TO_CPU(ds->max_indirect_range, fs_le)) {
175 struct block_run *br;
176 int64_t max_br, br_len, i;
177
178 start -= FS64_TO_CPU(ds->max_direct_range, fs_le);
179 max_br = ((int64_t) FS16_TO_CPU(ds->indirect.len, fs_le)
180 << FS32_TO_CPU(bs->block_shift, fs_le))
181 / sizeof(struct block_run);
182
183 br = (struct block_run *) get_block_run(pr, bs, &ds->indirect,
184 fs_le);
185 if (!br)
186 return NULL;
187
188 for (i = 0; i < max_br; i++) {
189 br_len = (int64_t) FS16_TO_CPU(br[i].len, fs_le)
190 << FS32_TO_CPU(bs->block_shift, fs_le);
191 if (start < br_len)
192 return get_custom_block_run(pr, bs, &br[i],
193 start, length, fs_le);
194 start -= br_len;
195 }
196 } else if (start < (int64_t) FS64_TO_CPU(ds->max_double_indirect_range, fs_le)) {
197 struct block_run *br;
198 int64_t max_br, di_br_size, br_per_di_br, di_index, i_index;
199
200 start -= (int64_t) FS64_TO_CPU(ds->max_indirect_range, fs_le);
201
202 di_br_size = (int64_t) FS16_TO_CPU(ds->double_indirect.len,
203 fs_le) << FS32_TO_CPU(bs->block_shift, fs_le);
204 if (di_br_size == 0)
205 return NULL;
206
207 br_per_di_br = di_br_size / sizeof(struct block_run);
208 if (br_per_di_br == 0)
209 return NULL;
210
211 di_index = start / (br_per_di_br * di_br_size);
212 i_index = (start % (br_per_di_br * di_br_size)) / di_br_size;
213 start = (start % (br_per_di_br * di_br_size)) % di_br_size;
214
215 if (di_index >= br_per_di_br)
216 return NULL; /* Corrupt? */
217
218 br = (struct block_run *) get_block_run(pr, bs,
219 &ds->double_indirect, fs_le);
220 if (!br)
221 return NULL;
222
223 max_br = ((int64_t)FS16_TO_CPU(br[di_index].len, fs_le)
224 << FS32_TO_CPU(bs->block_shift, fs_le))
225 / sizeof(struct block_run);
226
227 if (i_index >= max_br)
228 return NULL; /* Corrupt? */
229
230 br = (struct block_run *) get_block_run(pr, bs, &br[di_index],
231 fs_le);
232 if (!br)
233 return NULL;
234
235 return get_custom_block_run(pr, bs, &br[i_index], start, length,
236 fs_le);
237 }
238 return NULL;
239 }
240
241 #define BAD_KEYS -2
242
243 static int32_t compare_keys(const char keys1[], uint16_t keylengths1[],
244 int32_t index, const char *key2,
245 uint16_t keylength2, uint16_t all_key_length,
246 int fs_le)
247 {
248 const char *key1;
249 uint16_t keylength1, keystart1;
250 int32_t result;
251
252 keystart1 = index == 0 ? 0 : FS16_TO_CPU(keylengths1[index - 1], fs_le);
253 keylength1 = FS16_TO_CPU(keylengths1[index], fs_le) - keystart1;
254
255 if (keystart1 + keylength1 > all_key_length)
256 return BAD_KEYS; /* Corrupt? */
257
258 key1 = &keys1[keystart1];
259
260 result = strncmp(key1, key2, min(keylength1, keylength2));
261
262 if (result == 0)
263 return keylength1 - keylength2;
264
265 if (result < 0) /* Don't clash with BAD_KEYS */
266 result = -1;
267
268 return result;
269 }
270
271 static int64_t get_key_value(blkid_probe pr, const struct befs_super_block *bs,
272 const struct befs_inode *bi, const char *key, int fs_le)
273 {
274 struct bplustree_header *bh;
275 struct bplustree_node *bn;
276 uint16_t *keylengths;
277 int64_t *values;
278 int64_t node_pointer;
279 uint32_t bn_size, all_key_count, all_key_length;
280 uint32_t keylengths_offset, values_offset;
281 int32_t first, last, mid, cmp;
282 int loop_detect = 0;
283
284 errno = 0;
285 bh = (struct bplustree_header *) get_tree_node(pr, bs, &bi->data, 0,
286 sizeof(struct bplustree_header), fs_le);
287 if (!bh)
288 return errno ? -errno : -ENOENT;
289
290 if ((int32_t) FS32_TO_CPU(bh->magic, fs_le) != BPLUSTREE_MAGIC)
291 return -ENOENT;
292
293 node_pointer = FS64_TO_CPU(bh->root_node_pointer, fs_le);
294 bn_size = FS32_TO_CPU(bh->node_size, fs_le);
295
296 if (bn_size < sizeof(struct bplustree_node))
297 return -ENOENT; /* Corrupt? */
298
299 do {
300 errno = 0;
301
302 bn = (struct bplustree_node *) get_tree_node(pr, bs, &bi->data,
303 node_pointer, bn_size, fs_le);
304 if (!bn)
305 return errno ? -errno : -ENOENT;
306
307 all_key_count = FS16_TO_CPU(bn->all_key_count, fs_le);
308 all_key_length = FS16_TO_CPU(bn->all_key_length, fs_le);
309 keylengths_offset =
310 (sizeof(struct bplustree_node) + all_key_length
311 + sizeof(int64_t) - 1) & ~(sizeof(int64_t) - 1);
312 values_offset = keylengths_offset +
313 all_key_count * sizeof(uint16_t);
314
315 if (values_offset + all_key_count * sizeof(uint64_t) > bn_size)
316 return -ENOENT; /* Corrupt? */
317
318 keylengths = (uint16_t *) ((uint8_t *) bn + keylengths_offset);
319 values = (int64_t *) ((uint8_t *) bn + values_offset);
320
321 first = 0;
322 mid = 0;
323 last = all_key_count - 1;
324
325 cmp = compare_keys(bn->name, keylengths, last, key,
326 strlen(key), all_key_length, fs_le);
327 if (cmp == BAD_KEYS)
328 return -ENOENT;
329
330 if (cmp == 0) {
331 if ((int64_t) FS64_TO_CPU(bn->overflow_link, fs_le)
332 == BPLUSTREE_NULL)
333 return FS64_TO_CPU(values[last], fs_le);
334
335 node_pointer = FS64_TO_CPU(values[last], fs_le);
336 } else if (cmp < 0)
337 node_pointer = FS64_TO_CPU(bn->overflow_link, fs_le);
338 else {
339 while (first <= last) {
340 mid = (first + last) / 2;
341
342 cmp = compare_keys(bn->name, keylengths, mid,
343 key, strlen(key),
344 all_key_length, fs_le);
345 if (cmp == BAD_KEYS)
346 return -ENOENT;
347
348 if (cmp == 0) {
349 if ((int64_t) FS64_TO_CPU(bn->overflow_link,
350 fs_le) == BPLUSTREE_NULL)
351 return FS64_TO_CPU(values[mid],
352 fs_le);
353 break;
354 }
355
356 if (cmp < 0)
357 first = mid + 1;
358 else
359 last = mid - 1;
360 }
361 if (cmp < 0)
362 node_pointer = FS64_TO_CPU(values[mid + 1],
363 fs_le);
364 else
365 node_pointer = FS64_TO_CPU(values[mid], fs_le);
366 }
367 } while (++loop_detect < 100 &&
368 (int64_t) FS64_TO_CPU(bn->overflow_link, fs_le)
369 != BPLUSTREE_NULL);
370 return 0;
371 }
372
373 static int get_uuid(blkid_probe pr, const struct befs_super_block *bs,
374 uint64_t * const uuid, int fs_le)
375 {
376 struct befs_inode *bi;
377 struct small_data *sd;
378 uint64_t bi_size, offset, sd_size, sd_total_size;
379
380 bi = (struct befs_inode *) get_block_run(pr, bs, &bs->root_dir, fs_le);
381 if (!bi)
382 return errno ? -errno : BLKID_PROBE_NONE;
383
384 if (FS32_TO_CPU(bi->magic1, fs_le) != INODE_MAGIC1)
385 return BLKID_PROBE_NONE;
386
387 bi_size = (uint64_t)FS16_TO_CPU(bs->root_dir.len, fs_le) <<
388 FS32_TO_CPU(bs->block_shift, fs_le);
389 sd_total_size = min(bi_size - sizeof(struct befs_inode),
390 (uint64_t)FS32_TO_CPU(bi->inode_size, fs_le));
391
392 offset = 0;
393
394 while (offset + sizeof(struct small_data) <= sd_total_size) {
395 sd = (struct small_data *) ((uint8_t *)bi->small_data + offset);
396 sd_size = sizeof(struct small_data)
397 + FS16_TO_CPU(sd->name_size, fs_le) + 3
398 + FS16_TO_CPU(sd->data_size, fs_le) + 1;
399
400 if (offset + sd_size > sd_total_size)
401 break;
402
403 if (FS32_TO_CPU(sd->type, fs_le) == B_UINT64_TYPE
404 && FS16_TO_CPU(sd->name_size, fs_le) == strlen(KEY_NAME)
405 && FS16_TO_CPU(sd->data_size, fs_le) == KEY_SIZE
406 && strcmp(sd->name, KEY_NAME) == 0) {
407
408 memcpy(uuid,
409 sd->name + FS16_TO_CPU(sd->name_size, fs_le) + 3,
410 sizeof(uint64_t));
411
412 break;
413 }
414
415 if (FS32_TO_CPU(sd->type, fs_le) == 0
416 && FS16_TO_CPU(sd->name_size, fs_le) == 0
417 && FS16_TO_CPU(sd->data_size, fs_le) == 0)
418 break;
419
420 offset += sd_size;
421 }
422
423 if (*uuid == 0
424 && (FS32_TO_CPU(bi->attributes.allocation_group, fs_le) != 0
425 || FS16_TO_CPU(bi->attributes.start, fs_le) != 0
426 || FS16_TO_CPU(bi->attributes.len, fs_le) != 0)) {
427 int64_t value;
428
429 bi = (struct befs_inode *) get_block_run(pr, bs,
430 &bi->attributes, fs_le);
431 if (!bi)
432 return errno ? -errno : BLKID_PROBE_NONE;
433
434 if (FS32_TO_CPU(bi->magic1, fs_le) != INODE_MAGIC1)
435 return BLKID_PROBE_NONE;
436
437 value = get_key_value(pr, bs, bi, KEY_NAME, fs_le);
438 if (value < 0)
439 return value == -ENOENT ? BLKID_PROBE_NONE : value;
440
441 if (value > 0) {
442 bi = (struct befs_inode *) blkid_probe_get_buffer(pr,
443 value << FS32_TO_CPU(bs->block_shift, fs_le),
444 FS32_TO_CPU(bs->block_size, fs_le));
445 if (!bi)
446 return errno ? -errno : BLKID_PROBE_NONE;
447
448 if (FS32_TO_CPU(bi->magic1, fs_le) != INODE_MAGIC1)
449 return 1;
450
451 if (FS32_TO_CPU(bi->type, fs_le) == B_UINT64_TYPE
452 && FS64_TO_CPU(bi->data.size, fs_le) == KEY_SIZE
453 && FS16_TO_CPU(bi->data.direct[0].len, fs_le)
454 == 1) {
455 uint64_t *attr_data;
456
457 attr_data = (uint64_t *) get_block_run(pr, bs,
458 &bi->data.direct[0], fs_le);
459 if (!attr_data)
460 return errno ? -errno : BLKID_PROBE_NONE;
461
462 *uuid = *attr_data;
463 }
464 }
465 }
466 return 0;
467 }
468
469 static int probe_befs(blkid_probe pr, const struct blkid_idmag *mag)
470 {
471 struct befs_super_block *bs;
472 const char *version = NULL;
473 uint64_t volume_id = 0;
474 uint32_t block_size, block_shift;
475 int fs_le, ret;
476
477 bs = (struct befs_super_block *) blkid_probe_get_buffer(pr,
478 mag->sboff - B_OS_NAME_LENGTH,
479 sizeof(struct befs_super_block));
480 if (!bs)
481 return errno ? -errno : BLKID_PROBE_NONE;
482
483 if (le32_to_cpu(bs->magic1) == SUPER_BLOCK_MAGIC1
484 && le32_to_cpu(bs->magic2) == SUPER_BLOCK_MAGIC2
485 && le32_to_cpu(bs->magic3) == SUPER_BLOCK_MAGIC3
486 && le32_to_cpu(bs->fs_byte_order) == SUPER_BLOCK_FS_ENDIAN) {
487 fs_le = 1;
488 version = "little-endian";
489 } else if (be32_to_cpu(bs->magic1) == SUPER_BLOCK_MAGIC1
490 && be32_to_cpu(bs->magic2) == SUPER_BLOCK_MAGIC2
491 && be32_to_cpu(bs->magic3) == SUPER_BLOCK_MAGIC3
492 && be32_to_cpu(bs->fs_byte_order) == SUPER_BLOCK_FS_ENDIAN) {
493 fs_le = 0;
494 version = "big-endian";
495 } else
496 return BLKID_PROBE_NONE;
497
498 block_size = FS32_TO_CPU(bs->block_size, fs_le);
499 block_shift = FS32_TO_CPU(bs->block_shift, fs_le);
500
501 if (block_shift < 10 || block_shift > 13 ||
502 block_size != 1U << block_shift)
503 return BLKID_PROBE_NONE;
504
505 if (FS32_TO_CPU(bs->ag_shift, fs_le) > 64)
506 return BLKID_PROBE_NONE;
507
508 ret = get_uuid(pr, bs, &volume_id, fs_le);
509
510 if (ret != 0)
511 return ret;
512
513 /*
514 * all checks pass, set LABEL, VERSION and UUID
515 */
516 if (*bs->name != '\0')
517 blkid_probe_set_label(pr, (unsigned char *) bs->name,
518 sizeof(bs->name));
519 if (version)
520 blkid_probe_set_version(pr, version);
521
522 if (volume_id)
523 blkid_probe_sprintf_uuid(pr, (unsigned char *) &volume_id,
524 sizeof(volume_id), "%016" PRIx64,
525 FS64_TO_CPU(volume_id, fs_le));
526
527 blkid_probe_set_fsblocksize(pr, block_size);
528 blkid_probe_set_block_size(pr, block_size);
529 blkid_probe_set_fsendianness(pr,
530 fs_le ? BLKID_ENDIANNESS_LITTLE : BLKID_ENDIANNESS_BIG);
531
532 return BLKID_PROBE_OK;
533 }
534
535 const struct blkid_idinfo befs_idinfo =
536 {
537 .name = "befs",
538 .usage = BLKID_USAGE_FILESYSTEM,
539 .probefunc = probe_befs,
540 .minsz = 1024 * 1440,
541 .magics = {
542 { .magic = "BFS1", .len = 4, .sboff = B_OS_NAME_LENGTH },
543 { .magic = "1SFB", .len = 4, .sboff = B_OS_NAME_LENGTH },
544 { .magic = "BFS1", .len = 4, .sboff = 0x200 +
545 B_OS_NAME_LENGTH },
546 { .magic = "1SFB", .len = 4, .sboff = 0x200 +
547 B_OS_NAME_LENGTH },
548 { NULL }
549 }
550 };