]> git.proxmox.com Git - grub2.git/blob - grub-core/fs/btrfs.c
projects / grub2.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
bump version to 2.06-13+pmx2
[grub2.git] / grub-core / fs / btrfs.c
1 /* btrfs.c - B-tree file system. */
2 /*
3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2010,2011,2012,2013 Free Software Foundation, Inc.
5 *
6 * GRUB is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * GRUB is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with GRUB. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 /*
21 * Tell zstd to expose functions that aren't part of the stable API, which
22 * aren't safe to use when linking against a dynamic library. We vendor in a
23 * specific zstd version, so we know what we're getting. We need these unstable
24 * functions to provide our own allocator, which uses grub_malloc(), to zstd.
25 */
26 #define ZSTD_STATIC_LINKING_ONLY
27
28 #include <grub/err.h>
29 #include <grub/file.h>
30 #include <grub/mm.h>
31 #include <grub/misc.h>
32 #include <grub/disk.h>
33 #include <grub/dl.h>
34 #include <grub/types.h>
35 #include <grub/lib/crc.h>
36 #include <grub/deflate.h>
37 #include <minilzo.h>
38 #include <zstd.h>
39 #include <grub/i18n.h>
40 #include <grub/btrfs.h>
41 #include <grub/crypto.h>
42 #include <grub/diskfilter.h>
43 #include <grub/safemath.h>
44
45 GRUB_MOD_LICENSE ("GPLv3+");
46
47 #define GRUB_BTRFS_SIGNATURE "_BHRfS_M"
48
49 /* From http://www.oberhumer.com/opensource/lzo/lzofaq.php
50 * LZO will expand incompressible data by a little amount. I still haven't
51 * computed the exact values, but I suggest using these formulas for
52 * a worst-case expansion calculation:
53 *
54 * output_block_size = input_block_size + (input_block_size / 16) + 64 + 3
55 * */
56 #define GRUB_BTRFS_LZO_BLOCK_SIZE 4096
57 #define GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE (GRUB_BTRFS_LZO_BLOCK_SIZE + \
58 (GRUB_BTRFS_LZO_BLOCK_SIZE / 16) + 64 + 3)
59
60 #define ZSTD_BTRFS_MAX_WINDOWLOG 17
61 #define ZSTD_BTRFS_MAX_INPUT (1 << ZSTD_BTRFS_MAX_WINDOWLOG)
62
63 typedef grub_uint8_t grub_btrfs_checksum_t[0x20];
64 typedef grub_uint16_t grub_btrfs_uuid_t[8];
65
66 struct grub_btrfs_device
67 {
68 grub_uint64_t device_id;
69 grub_uint64_t size;
70 grub_uint8_t dummy[0x62 - 0x10];
71 } GRUB_PACKED;
72
73 struct grub_btrfs_superblock
74 {
75 grub_btrfs_checksum_t checksum;
76 grub_btrfs_uuid_t uuid;
77 grub_uint8_t dummy[0x10];
78 grub_uint8_t signature[sizeof (GRUB_BTRFS_SIGNATURE) - 1];
79 grub_uint64_t generation;
80 grub_uint64_t root_tree;
81 grub_uint64_t chunk_tree;
82 grub_uint8_t dummy2[0x20];
83 grub_uint64_t root_dir_objectid;
84 grub_uint8_t dummy3[0x41];
85 struct grub_btrfs_device this_device;
86 char label[0x100];
87 grub_uint8_t dummy4[0x100];
88 grub_uint8_t bootstrap_mapping[0x800];
89 } GRUB_PACKED;
90
91 struct btrfs_header
92 {
93 grub_btrfs_checksum_t checksum;
94 grub_btrfs_uuid_t uuid;
95 grub_uint64_t bytenr;
96 grub_uint8_t dummy[0x28];
97 grub_uint32_t nitems;
98 grub_uint8_t level;
99 } GRUB_PACKED;
100
101 struct grub_btrfs_device_desc
102 {
103 grub_device_t dev;
104 grub_uint64_t id;
105 };
106
107 struct grub_btrfs_data
108 {
109 struct grub_btrfs_superblock sblock;
110 grub_uint64_t tree;
111 grub_uint64_t inode;
112
113 struct grub_btrfs_device_desc *devices_attached;
114 unsigned n_devices_attached;
115 unsigned n_devices_allocated;
116
117 /* Cached extent data. */
118 grub_uint64_t extstart;
119 grub_uint64_t extend;
120 grub_uint64_t extino;
121 grub_uint64_t exttree;
122 grub_size_t extsize;
123 struct grub_btrfs_extent_data *extent;
124 };
125
126 struct grub_btrfs_chunk_item
127 {
128 grub_uint64_t size;
129 grub_uint64_t dummy;
130 grub_uint64_t stripe_length;
131 grub_uint64_t type;
132 #define GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE 0x07
133 #define GRUB_BTRFS_CHUNK_TYPE_SINGLE 0x00
134 #define GRUB_BTRFS_CHUNK_TYPE_RAID0 0x08
135 #define GRUB_BTRFS_CHUNK_TYPE_RAID1 0x10
136 #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED 0x20
137 #define GRUB_BTRFS_CHUNK_TYPE_RAID10 0x40
138 #define GRUB_BTRFS_CHUNK_TYPE_RAID5 0x80
139 #define GRUB_BTRFS_CHUNK_TYPE_RAID6 0x100
140 #define GRUB_BTRFS_CHUNK_TYPE_RAID1C3 0x200
141 #define GRUB_BTRFS_CHUNK_TYPE_RAID1C4 0x400
142 grub_uint8_t dummy2[0xc];
143 grub_uint16_t nstripes;
144 grub_uint16_t nsubstripes;
145 } GRUB_PACKED;
146
147 struct grub_btrfs_chunk_stripe
148 {
149 grub_uint64_t device_id;
150 grub_uint64_t offset;
151 grub_btrfs_uuid_t device_uuid;
152 } GRUB_PACKED;
153
154 struct grub_btrfs_leaf_node
155 {
156 struct grub_btrfs_key key;
157 grub_uint32_t offset;
158 grub_uint32_t size;
159 } GRUB_PACKED;
160
161 struct grub_btrfs_internal_node
162 {
163 struct grub_btrfs_key key;
164 grub_uint64_t addr;
165 grub_uint64_t dummy;
166 } GRUB_PACKED;
167
168 struct grub_btrfs_dir_item
169 {
170 struct grub_btrfs_key key;
171 grub_uint8_t dummy[8];
172 grub_uint16_t m;
173 grub_uint16_t n;
174 #define GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR 1
175 #define GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY 2
176 #define GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK 7
177 grub_uint8_t type;
178 char name[0];
179 } GRUB_PACKED;
180
181 struct grub_btrfs_leaf_descriptor
182 {
183 unsigned depth;
184 unsigned allocated;
185 struct
186 {
187 grub_disk_addr_t addr;
188 unsigned iter;
189 unsigned maxiter;
190 int leaf;
191 } *data;
192 };
193
194 struct grub_btrfs_time
195 {
196 grub_int64_t sec;
197 grub_uint32_t nanosec;
198 } GRUB_PACKED;
199
200 struct grub_btrfs_inode
201 {
202 grub_uint8_t dummy1[0x10];
203 grub_uint64_t size;
204 grub_uint8_t dummy2[0x70];
205 struct grub_btrfs_time mtime;
206 } GRUB_PACKED;
207
208 struct grub_btrfs_extent_data
209 {
210 grub_uint64_t dummy;
211 grub_uint64_t size;
212 grub_uint8_t compression;
213 grub_uint8_t encryption;
214 grub_uint16_t encoding;
215 grub_uint8_t type;
216 union
217 {
218 char inl[0];
219 struct
220 {
221 grub_uint64_t laddr;
222 grub_uint64_t compressed_size;
223 grub_uint64_t offset;
224 grub_uint64_t filled;
225 };
226 };
227 } GRUB_PACKED;
228
229 #define GRUB_BTRFS_EXTENT_INLINE 0
230 #define GRUB_BTRFS_EXTENT_REGULAR 1
231
232 #define GRUB_BTRFS_COMPRESSION_NONE 0
233 #define GRUB_BTRFS_COMPRESSION_ZLIB 1
234 #define GRUB_BTRFS_COMPRESSION_LZO 2
235 #define GRUB_BTRFS_COMPRESSION_ZSTD 3
236
237 #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100
238
239 static grub_disk_addr_t superblock_sectors[] = { 64 * 2, 64 * 1024 * 2,
240 256 * 1048576 * 2, 1048576ULL * 1048576ULL * 2
241 };
242
243 static grub_err_t
244 grub_btrfs_read_logical (struct grub_btrfs_data *data,
245 grub_disk_addr_t addr, void *buf, grub_size_t size,
246 int recursion_depth);
247
248 static grub_err_t
249 read_sblock (grub_disk_t disk, struct grub_btrfs_superblock *sb)
250 {
251 struct grub_btrfs_superblock sblock;
252 unsigned i;
253 grub_err_t err = GRUB_ERR_NONE;
254 for (i = 0; i < ARRAY_SIZE (superblock_sectors); i++)
255 {
256 /* Don't try additional superblocks beyond device size. */
257 if (i && (grub_le_to_cpu64 (sblock.this_device.size)
258 >> GRUB_DISK_SECTOR_BITS) <= superblock_sectors[i])
259 break;
260 err = grub_disk_read (disk, superblock_sectors[i], 0,
261 sizeof (sblock), &sblock);
262 if (err == GRUB_ERR_OUT_OF_RANGE)
263 break;
264
265 if (grub_memcmp ((char *) sblock.signature, GRUB_BTRFS_SIGNATURE,
266 sizeof (GRUB_BTRFS_SIGNATURE) - 1) != 0)
267 break;
268 if (i == 0 || grub_le_to_cpu64 (sblock.generation)
269 > grub_le_to_cpu64 (sb->generation))
270 grub_memcpy (sb, &sblock, sizeof (sblock));
271 }
272
273 if ((err == GRUB_ERR_OUT_OF_RANGE || !err) && i == 0)
274 return grub_error (GRUB_ERR_BAD_FS, "not a Btrfs filesystem");
275
276 if (err == GRUB_ERR_OUT_OF_RANGE)
277 grub_errno = err = GRUB_ERR_NONE;
278
279 return err;
280 }
281
282 static int
283 key_cmp (const struct grub_btrfs_key *a, const struct grub_btrfs_key *b)
284 {
285 if (grub_le_to_cpu64 (a->object_id) < grub_le_to_cpu64 (b->object_id))
286 return -1;
287 if (grub_le_to_cpu64 (a->object_id) > grub_le_to_cpu64 (b->object_id))
288 return +1;
289
290 if (a->type < b->type)
291 return -1;
292 if (a->type > b->type)
293 return +1;
294
295 if (grub_le_to_cpu64 (a->offset) < grub_le_to_cpu64 (b->offset))
296 return -1;
297 if (grub_le_to_cpu64 (a->offset) > grub_le_to_cpu64 (b->offset))
298 return +1;
299 return 0;
300 }
301
302 static void
303 free_iterator (struct grub_btrfs_leaf_descriptor *desc)
304 {
305 grub_free (desc->data);
306 }
307
308 static grub_err_t
309 check_btrfs_header (struct grub_btrfs_data *data, struct btrfs_header *header,
310 grub_disk_addr_t addr)
311 {
312 if (grub_le_to_cpu64 (header->bytenr) != addr)
313 {
314 grub_dprintf ("btrfs", "btrfs_header.bytenr is not equal node addr\n");
315 return grub_error (GRUB_ERR_BAD_FS,
316 "header bytenr is not equal node addr");
317 }
318 if (grub_memcmp (data->sblock.uuid, header->uuid, sizeof(grub_btrfs_uuid_t)))
319 {
320 grub_dprintf ("btrfs", "btrfs_header.uuid doesn't match sblock uuid\n");
321 return grub_error (GRUB_ERR_BAD_FS,
322 "header uuid doesn't match sblock uuid");
323 }
324 return GRUB_ERR_NONE;
325 }
326
327 static grub_err_t
328 save_ref (struct grub_btrfs_leaf_descriptor *desc,
329 grub_disk_addr_t addr, unsigned i, unsigned m, int l)
330 {
331 desc->depth++;
332 if (desc->allocated < desc->depth)
333 {
334 void *newdata;
335 grub_size_t sz;
336
337 if (grub_mul (desc->allocated, 2, &desc->allocated) ||
338 grub_mul (desc->allocated, sizeof (desc->data[0]), &sz))
339 return GRUB_ERR_OUT_OF_RANGE;
340
341 newdata = grub_realloc (desc->data, sz);
342 if (!newdata)
343 return grub_errno;
344 desc->data = newdata;
345 }
346 desc->data[desc->depth - 1].addr = addr;
347 desc->data[desc->depth - 1].iter = i;
348 desc->data[desc->depth - 1].maxiter = m;
349 desc->data[desc->depth - 1].leaf = l;
350 return GRUB_ERR_NONE;
351 }
352
353 static int
354 next (struct grub_btrfs_data *data,
355 struct grub_btrfs_leaf_descriptor *desc,
356 grub_disk_addr_t * outaddr, grub_size_t * outsize,
357 struct grub_btrfs_key *key_out)
358 {
359 grub_err_t err;
360 struct grub_btrfs_leaf_node leaf;
361
362 for (; desc->depth > 0; desc->depth--)
363 {
364 desc->data[desc->depth - 1].iter++;
365 if (desc->data[desc->depth - 1].iter
366 < desc->data[desc->depth - 1].maxiter)
367 break;
368 }
369 if (desc->depth == 0)
370 return 0;
371 while (!desc->data[desc->depth - 1].leaf)
372 {
373 struct grub_btrfs_internal_node node;
374 struct btrfs_header head;
375
376 err = grub_btrfs_read_logical (data, desc->data[desc->depth - 1].iter
377 * sizeof (node)
378 + sizeof (struct btrfs_header)
379 + desc->data[desc->depth - 1].addr,
380 &node, sizeof (node), 0);
381 if (err)
382 return -err;
383
384 err = grub_btrfs_read_logical (data, grub_le_to_cpu64 (node.addr),
385 &head, sizeof (head), 0);
386 if (err)
387 return -err;
388 check_btrfs_header (data, &head, grub_le_to_cpu64 (node.addr));
389
390 save_ref (desc, grub_le_to_cpu64 (node.addr), 0,
391 grub_le_to_cpu32 (head.nitems), !head.level);
392 }
393 err = grub_btrfs_read_logical (data, desc->data[desc->depth - 1].iter
394 * sizeof (leaf)
395 + sizeof (struct btrfs_header)
396 + desc->data[desc->depth - 1].addr, &leaf,
397 sizeof (leaf), 0);
398 if (err)
399 return -err;
400 *outsize = grub_le_to_cpu32 (leaf.size);
401 *outaddr = desc->data[desc->depth - 1].addr + sizeof (struct btrfs_header)
402 + grub_le_to_cpu32 (leaf.offset);
403 *key_out = leaf.key;
404 return 1;
405 }
406
407 static grub_err_t
408 lower_bound (struct grub_btrfs_data *data,
409 const struct grub_btrfs_key *key_in,
410 struct grub_btrfs_key *key_out,
411 grub_uint64_t root,
412 grub_disk_addr_t *outaddr, grub_size_t *outsize,
413 struct grub_btrfs_leaf_descriptor *desc,
414 int recursion_depth)
415 {
416 grub_disk_addr_t addr = grub_le_to_cpu64 (root);
417 int depth = -1;
418
419 if (desc)
420 {
421 desc->allocated = 16;
422 desc->depth = 0;
423 desc->data = grub_calloc (desc->allocated, sizeof (desc->data[0]));
424 if (!desc->data)
425 return grub_errno;
426 }
427
428 /* > 2 would work as well but be robust and allow a bit more just in case.
429 */
430 if (recursion_depth > 10)
431 return grub_error (GRUB_ERR_BAD_FS, "too deep btrfs virtual nesting");
432
433 grub_dprintf ("btrfs",
434 "retrieving %" PRIxGRUB_UINT64_T
435 " %x %" PRIxGRUB_UINT64_T "\n",
436 key_in->object_id, key_in->type, key_in->offset);
437
438 while (1)
439 {
440 grub_err_t err;
441 struct btrfs_header head;
442
443 reiter:
444 depth++;
445 /* FIXME: preread few nodes into buffer. */
446 err = grub_btrfs_read_logical (data, addr, &head, sizeof (head),
447 recursion_depth + 1);
448 if (err)
449 return err;
450 check_btrfs_header (data, &head, addr);
451 addr += sizeof (head);
452 if (head.level)
453 {
454 unsigned i;
455 struct grub_btrfs_internal_node node, node_last;
456 int have_last = 0;
457 grub_memset (&node_last, 0, sizeof (node_last));
458 for (i = 0; i < grub_le_to_cpu32 (head.nitems); i++)
459 {
460 err = grub_btrfs_read_logical (data, addr + i * sizeof (node),
461 &node, sizeof (node),
462 recursion_depth + 1);
463 if (err)
464 return err;
465
466 grub_dprintf ("btrfs",
467 "internal node (depth %d) %" PRIxGRUB_UINT64_T
468 " %x %" PRIxGRUB_UINT64_T "\n", depth,
469 node.key.object_id, node.key.type,
470 node.key.offset);
471
472 if (key_cmp (&node.key, key_in) == 0)
473 {
474 err = GRUB_ERR_NONE;
475 if (desc)
476 err = save_ref (desc, addr - sizeof (head), i,
477 grub_le_to_cpu32 (head.nitems), 0);
478 if (err)
479 return err;
480 addr = grub_le_to_cpu64 (node.addr);
481 goto reiter;
482 }
483 if (key_cmp (&node.key, key_in) > 0)
484 break;
485 node_last = node;
486 have_last = 1;
487 }
488 if (have_last)
489 {
490 err = GRUB_ERR_NONE;
491 if (desc)
492 err = save_ref (desc, addr - sizeof (head), i - 1,
493 grub_le_to_cpu32 (head.nitems), 0);
494 if (err)
495 return err;
496 addr = grub_le_to_cpu64 (node_last.addr);
497 goto reiter;
498 }
499 *outsize = 0;
500 *outaddr = 0;
501 grub_memset (key_out, 0, sizeof (*key_out));
502 if (desc)
503 return save_ref (desc, addr - sizeof (head), -1,
504 grub_le_to_cpu32 (head.nitems), 0);
505 return GRUB_ERR_NONE;
506 }
507 {
508 unsigned i;
509 struct grub_btrfs_leaf_node leaf, leaf_last;
510 int have_last = 0;
511 for (i = 0; i < grub_le_to_cpu32 (head.nitems); i++)
512 {
513 err = grub_btrfs_read_logical (data, addr + i * sizeof (leaf),
514 &leaf, sizeof (leaf),
515 recursion_depth + 1);
516 if (err)
517 return err;
518
519 grub_dprintf ("btrfs",
520 "leaf (depth %d) %" PRIxGRUB_UINT64_T
521 " %x %" PRIxGRUB_UINT64_T "\n", depth,
522 leaf.key.object_id, leaf.key.type, leaf.key.offset);
523
524 if (key_cmp (&leaf.key, key_in) == 0)
525 {
526 grub_memcpy (key_out, &leaf.key, sizeof (*key_out));
527 *outsize = grub_le_to_cpu32 (leaf.size);
528 *outaddr = addr + grub_le_to_cpu32 (leaf.offset);
529 if (desc)
530 return save_ref (desc, addr - sizeof (head), i,
531 grub_le_to_cpu32 (head.nitems), 1);
532 return GRUB_ERR_NONE;
533 }
534
535 if (key_cmp (&leaf.key, key_in) > 0)
536 break;
537
538 have_last = 1;
539 leaf_last = leaf;
540 }
541
542 if (have_last)
543 {
544 grub_memcpy (key_out, &leaf_last.key, sizeof (*key_out));
545 *outsize = grub_le_to_cpu32 (leaf_last.size);
546 *outaddr = addr + grub_le_to_cpu32 (leaf_last.offset);
547 if (desc)
548 return save_ref (desc, addr - sizeof (head), i - 1,
549 grub_le_to_cpu32 (head.nitems), 1);
550 return GRUB_ERR_NONE;
551 }
552 *outsize = 0;
553 *outaddr = 0;
554 grub_memset (key_out, 0, sizeof (*key_out));
555 if (desc)
556 return save_ref (desc, addr - sizeof (head), -1,
557 grub_le_to_cpu32 (head.nitems), 1);
558 return GRUB_ERR_NONE;
559 }
560 }
561 }
562
563 /* Context for find_device. */
564 struct find_device_ctx
565 {
566 struct grub_btrfs_data *data;
567 grub_uint64_t id;
568 grub_device_t dev_found;
569 };
570
571 /* Helper for find_device. */
572 static int
573 find_device_iter (const char *name, void *data)
574 {
575 struct find_device_ctx *ctx = data;
576 grub_device_t dev;
577 grub_err_t err;
578 struct grub_btrfs_superblock sb;
579
580 dev = grub_device_open (name);
581 if (!dev)
582 return 0;
583 if (!dev->disk)
584 {
585 grub_device_close (dev);
586 return 0;
587 }
588 err = read_sblock (dev->disk, &sb);
589 if (err == GRUB_ERR_BAD_FS)
590 {
591 grub_device_close (dev);
592 grub_errno = GRUB_ERR_NONE;
593 return 0;
594 }
595 if (err)
596 {
597 grub_device_close (dev);
598 grub_print_error ();
599 return 0;
600 }
601 if (grub_memcmp (ctx->data->sblock.uuid, sb.uuid, sizeof (sb.uuid)) != 0
602 || sb.this_device.device_id != ctx->id)
603 {
604 grub_device_close (dev);
605 return 0;
606 }
607
608 ctx->dev_found = dev;
609 return 1;
610 }
611
612 static grub_device_t
613 find_device (struct grub_btrfs_data *data, grub_uint64_t id)
614 {
615 struct find_device_ctx ctx = {
616 .data = data,
617 .id = id,
618 .dev_found = NULL
619 };
620 unsigned i;
621
622 for (i = 0; i < data->n_devices_attached; i++)
623 if (id == data->devices_attached[i].id)
624 return data->devices_attached[i].dev;
625
626 grub_device_iterate (find_device_iter, &ctx);
627
628 data->n_devices_attached++;
629 if (data->n_devices_attached > data->n_devices_allocated)
630 {
631 void *tmp;
632 grub_size_t sz;
633
634 if (grub_mul (data->n_devices_attached, 2, &data->n_devices_allocated) ||
635 grub_add (data->n_devices_allocated, 1, &data->n_devices_allocated) ||
636 grub_mul (data->n_devices_allocated, sizeof (data->devices_attached[0]), &sz))
637 goto fail;
638
639 data->devices_attached = grub_realloc (tmp = data->devices_attached, sz);
640 if (!data->devices_attached)
641 {
642 data->devices_attached = tmp;
643
644 fail:
645 if (ctx.dev_found)
646 grub_device_close (ctx.dev_found);
647 return NULL;
648 }
649 }
650 data->devices_attached[data->n_devices_attached - 1].id = id;
651 data->devices_attached[data->n_devices_attached - 1].dev = ctx.dev_found;
652 return ctx.dev_found;
653 }
654
655 static grub_err_t
656 btrfs_read_from_chunk (struct grub_btrfs_data *data,
657 struct grub_btrfs_chunk_item *chunk,
658 grub_uint64_t stripen, grub_uint64_t stripe_offset,
659 int redundancy, grub_uint64_t csize,
660 void *buf)
661 {
662 struct grub_btrfs_chunk_stripe *stripe;
663 grub_disk_addr_t paddr;
664 grub_device_t dev;
665 grub_err_t err;
666
667 stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
668 /* Right now the redundancy handling is easy.
669 With RAID5-like it will be more difficult. */
670 stripe += stripen + redundancy;
671
672 paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
673
674 grub_dprintf ("btrfs", "stripe %" PRIxGRUB_UINT64_T
675 " maps to 0x%" PRIxGRUB_UINT64_T "\n"
676 "reading paddr 0x%" PRIxGRUB_UINT64_T "\n",
677 stripen, stripe->offset, paddr);
678
679 dev = find_device (data, stripe->device_id);
680 if (!dev)
681 {
682 grub_dprintf ("btrfs",
683 "couldn't find a necessary member device "
684 "of multi-device filesystem\n");
685 grub_errno = GRUB_ERR_NONE;
686 return GRUB_ERR_READ_ERROR;
687 }
688
689 err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
690 paddr & (GRUB_DISK_SECTOR_SIZE - 1),
691 csize, buf);
692 return err;
693 }
694
695 struct raid56_buffer {
696 void *buf;
697 int data_is_valid;
698 };
699
700 static void
701 rebuild_raid5 (char *dest, struct raid56_buffer *buffers,
702 grub_uint64_t nstripes, grub_uint64_t csize)
703 {
704 grub_uint64_t i;
705 int first;
706
707 for(i = 0; buffers[i].data_is_valid && i < nstripes; i++);
708
709 if (i == nstripes)
710 {
711 grub_dprintf ("btrfs", "called rebuild_raid5(), but all disks are OK\n");
712 return;
713 }
714
715 grub_dprintf ("btrfs", "rebuilding RAID 5 stripe #%" PRIuGRUB_UINT64_T "\n", i);
716
717 for (i = 0, first = 1; i < nstripes; i++)
718 {
719 if (!buffers[i].data_is_valid)
720 continue;
721
722 if (first) {
723 grub_memcpy(dest, buffers[i].buf, csize);
724 first = 0;
725 } else
726 grub_crypto_xor (dest, dest, buffers[i].buf, csize);
727 }
728 }
729
730 static grub_err_t
731 raid6_recover_read_buffer (void *data, int disk_nr,
732 grub_uint64_t addr __attribute__ ((unused)),
733 void *dest, grub_size_t size)
734 {
735 struct raid56_buffer *buffers = data;
736
737 if (!buffers[disk_nr].data_is_valid)
738 return grub_errno = GRUB_ERR_READ_ERROR;
739
740 grub_memcpy(dest, buffers[disk_nr].buf, size);
741
742 return grub_errno = GRUB_ERR_NONE;
743 }
744
745 static void
746 rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes,
747 grub_uint64_t csize, grub_uint64_t parities_pos, void *dest,
748 grub_uint64_t stripen)
749
750 {
751 grub_raid6_recover_gen (buffers, nstripes, stripen, parities_pos,
752 dest, 0, csize, 0, raid6_recover_read_buffer);
753 }
754
755 static grub_err_t
756 raid56_read_retry (struct grub_btrfs_data *data,
757 struct grub_btrfs_chunk_item *chunk,
758 grub_uint64_t stripe_offset, grub_uint64_t stripen,
759 grub_uint64_t csize, void *buf, grub_uint64_t parities_pos)
760 {
761 struct raid56_buffer *buffers;
762 grub_uint64_t nstripes = grub_le_to_cpu16 (chunk->nstripes);
763 grub_uint64_t chunk_type = grub_le_to_cpu64 (chunk->type);
764 grub_err_t ret = GRUB_ERR_OUT_OF_MEMORY;
765 grub_uint64_t i, failed_devices;
766
767 buffers = grub_calloc (nstripes, sizeof (*buffers));
768 if (!buffers)
769 goto cleanup;
770
771 for (i = 0; i < nstripes; i++)
772 {
773 buffers[i].buf = grub_zalloc (csize);
774 if (!buffers[i].buf)
775 goto cleanup;
776 }
777
778 for (failed_devices = 0, i = 0; i < nstripes; i++)
779 {
780 struct grub_btrfs_chunk_stripe *stripe;
781 grub_disk_addr_t paddr;
782 grub_device_t dev;
783 grub_err_t err;
784
785 /*
786 * The struct grub_btrfs_chunk_stripe array lives
787 * behind struct grub_btrfs_chunk_item.
788 */
789 stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1) + i;
790
791 paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
792 grub_dprintf ("btrfs", "reading paddr %" PRIxGRUB_UINT64_T
793 " from stripe ID %" PRIxGRUB_UINT64_T "\n",
794 paddr, stripe->device_id);
795
796 dev = find_device (data, stripe->device_id);
797 if (!dev)
798 {
799 grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " FAILED (dev ID %"
800 PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
801 failed_devices++;
802 continue;
803 }
804
805 err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
806 paddr & (GRUB_DISK_SECTOR_SIZE - 1),
807 csize, buffers[i].buf);
808 if (err == GRUB_ERR_NONE)
809 {
810 buffers[i].data_is_valid = 1;
811 grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " OK (dev ID %"
812 PRIxGRUB_UINT64_T ")\n", i, stripe->device_id);
813 }
814 else
815 {
816 grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T
817 " READ FAILED (dev ID %" PRIxGRUB_UINT64_T ")\n",
818 i, stripe->device_id);
819 failed_devices++;
820 }
821 }
822
823 if (failed_devices > 1 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5))
824 {
825 grub_dprintf ("btrfs", "not enough disks for RAID 5: total %" PRIuGRUB_UINT64_T
826 ", missing %" PRIuGRUB_UINT64_T "\n",
827 nstripes, failed_devices);
828 ret = GRUB_ERR_READ_ERROR;
829 goto cleanup;
830 }
831 else if (failed_devices > 2 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID6))
832 {
833 grub_dprintf ("btrfs", "not enough disks for RAID 6: total %" PRIuGRUB_UINT64_T
834 ", missing %" PRIuGRUB_UINT64_T "\n",
835 nstripes, failed_devices);
836 ret = GRUB_ERR_READ_ERROR;
837 goto cleanup;
838 }
839 else
840 grub_dprintf ("btrfs", "enough disks for RAID 5: total %"
841 PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n",
842 nstripes, failed_devices);
843
844 /* We have enough disks. So, rebuild the data. */
845 if (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5)
846 rebuild_raid5 (buf, buffers, nstripes, csize);
847 else
848 rebuild_raid6 (buffers, nstripes, csize, parities_pos, buf, stripen);
849
850 ret = GRUB_ERR_NONE;
851 cleanup:
852 if (buffers)
853 for (i = 0; i < nstripes; i++)
854 grub_free (buffers[i].buf);
855 grub_free (buffers);
856
857 return ret;
858 }
859
860 static grub_err_t
861 grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
862 void *buf, grub_size_t size, int recursion_depth)
863 {
864 while (size > 0)
865 {
866 grub_uint8_t *ptr;
867 struct grub_btrfs_key *key;
868 struct grub_btrfs_chunk_item *chunk;
869 grub_uint64_t csize;
870 grub_err_t err = 0;
871 struct grub_btrfs_key key_out;
872 int challoc = 0;
873 struct grub_btrfs_key key_in;
874 grub_size_t chsize;
875 grub_disk_addr_t chaddr;
876
877 grub_dprintf ("btrfs", "searching for laddr %" PRIxGRUB_UINT64_T "\n",
878 addr);
879 for (ptr = data->sblock.bootstrap_mapping;
880 ptr < data->sblock.bootstrap_mapping
881 + sizeof (data->sblock.bootstrap_mapping)
882 - sizeof (struct grub_btrfs_key);)
883 {
884 key = (struct grub_btrfs_key *) ptr;
885 if (key->type != GRUB_BTRFS_ITEM_TYPE_CHUNK)
886 break;
887 chunk = (struct grub_btrfs_chunk_item *) (key + 1);
888 grub_dprintf ("btrfs",
889 "%" PRIxGRUB_UINT64_T " %" PRIxGRUB_UINT64_T " \n",
890 grub_le_to_cpu64 (key->offset),
891 grub_le_to_cpu64 (chunk->size));
892 if (grub_le_to_cpu64 (key->offset) <= addr
893 && addr < grub_le_to_cpu64 (key->offset)
894 + grub_le_to_cpu64 (chunk->size))
895 goto chunk_found;
896 ptr += sizeof (*key) + sizeof (*chunk)
897 + sizeof (struct grub_btrfs_chunk_stripe)
898 * grub_le_to_cpu16 (chunk->nstripes);
899 }
900
901 key_in.object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK);
902 key_in.type = GRUB_BTRFS_ITEM_TYPE_CHUNK;
903 key_in.offset = grub_cpu_to_le64 (addr);
904 err = lower_bound (data, &key_in, &key_out,
905 data->sblock.chunk_tree,
906 &chaddr, &chsize, NULL, recursion_depth);
907 if (err)
908 return err;
909 key = &key_out;
910 if (key->type != GRUB_BTRFS_ITEM_TYPE_CHUNK
911 || !(grub_le_to_cpu64 (key->offset) <= addr))
912 return grub_error (GRUB_ERR_BAD_FS,
913 "couldn't find the chunk descriptor");
914
915 chunk = grub_malloc (chsize);
916 if (!chunk)
917 return grub_errno;
918
919 challoc = 1;
920 err = grub_btrfs_read_logical (data, chaddr, chunk, chsize,
921 recursion_depth);
922 if (err)
923 {
924 grub_free (chunk);
925 return err;
926 }
927
928 chunk_found:
929 {
930 grub_uint64_t stripen;
931 grub_uint64_t stripe_offset;
932 grub_uint64_t off = addr - grub_le_to_cpu64 (key->offset);
933 grub_uint64_t chunk_stripe_length;
934 grub_uint16_t nstripes;
935 unsigned redundancy = 1;
936 unsigned i, j;
937 int is_raid56;
938 grub_uint64_t parities_pos = 0;
939
940 is_raid56 = !!(grub_le_to_cpu64 (chunk->type) &
941 (GRUB_BTRFS_CHUNK_TYPE_RAID5 |
942 GRUB_BTRFS_CHUNK_TYPE_RAID6));
943
944 if (grub_le_to_cpu64 (chunk->size) <= off)
945 {
946 grub_dprintf ("btrfs", "no chunk\n");
947 return grub_error (GRUB_ERR_BAD_FS,
948 "couldn't find the chunk descriptor");
949 }
950
951 nstripes = grub_le_to_cpu16 (chunk->nstripes) ? : 1;
952 chunk_stripe_length = grub_le_to_cpu64 (chunk->stripe_length) ? : 512;
953 grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
954 "+0x%" PRIxGRUB_UINT64_T
955 " (%d stripes (%d substripes) of %"
956 PRIxGRUB_UINT64_T ")\n",
957 grub_le_to_cpu64 (key->offset),
958 grub_le_to_cpu64 (chunk->size),
959 nstripes,
960 grub_le_to_cpu16 (chunk->nsubstripes),
961 chunk_stripe_length);
962
963 switch (grub_le_to_cpu64 (chunk->type)
964 & ~GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE)
965 {
966 case GRUB_BTRFS_CHUNK_TYPE_SINGLE:
967 {
968 grub_uint64_t stripe_length;
969 grub_dprintf ("btrfs", "single\n");
970 stripe_length = grub_divmod64 (grub_le_to_cpu64 (chunk->size),
971 nstripes,
972 NULL);
973 if (stripe_length == 0)
974 stripe_length = 512;
975 stripen = grub_divmod64 (off, stripe_length, &stripe_offset);
976 csize = (stripen + 1) * stripe_length - off;
977 break;
978 }
979 case GRUB_BTRFS_CHUNK_TYPE_RAID1C4:
980 redundancy++;
981 /* fall through */
982 case GRUB_BTRFS_CHUNK_TYPE_RAID1C3:
983 redundancy++;
984 /* fall through */
985 case GRUB_BTRFS_CHUNK_TYPE_DUPLICATED:
986 case GRUB_BTRFS_CHUNK_TYPE_RAID1:
987 {
988 grub_dprintf ("btrfs", "RAID1 (copies: %d)\n", ++redundancy);
989 stripen = 0;
990 stripe_offset = off;
991 csize = grub_le_to_cpu64 (chunk->size) - off;
992 break;
993 }
994 case GRUB_BTRFS_CHUNK_TYPE_RAID0:
995 {
996 grub_uint64_t middle, high;
997 grub_uint64_t low;
998 grub_dprintf ("btrfs", "RAID0\n");
999 middle = grub_divmod64 (off,
1000 chunk_stripe_length,
1001 &low);
1002
1003 high = grub_divmod64 (middle, nstripes,
1004 &stripen);
1005 stripe_offset =
1006 low + chunk_stripe_length * high;
1007 csize = chunk_stripe_length - low;
1008 break;
1009 }
1010 case GRUB_BTRFS_CHUNK_TYPE_RAID10:
1011 {
1012 grub_uint64_t middle, high;
1013 grub_uint64_t low;
1014 grub_uint16_t nsubstripes;
1015 nsubstripes = grub_le_to_cpu16 (chunk->nsubstripes) ? : 1;
1016 middle = grub_divmod64 (off,
1017 chunk_stripe_length,
1018 &low);
1019
1020 high = grub_divmod64 (middle,
1021 nstripes / nsubstripes ? : 1,
1022 &stripen);
1023 stripen *= nsubstripes;
1024 redundancy = nsubstripes;
1025 stripe_offset = low + chunk_stripe_length
1026 * high;
1027 csize = chunk_stripe_length - low;
1028 break;
1029 }
1030 case GRUB_BTRFS_CHUNK_TYPE_RAID5:
1031 case GRUB_BTRFS_CHUNK_TYPE_RAID6:
1032 {
1033 grub_uint64_t nparities, stripe_nr, high, low;
1034
1035 redundancy = 1; /* no redundancy for now */
1036
1037 if (grub_le_to_cpu64 (chunk->type) & GRUB_BTRFS_CHUNK_TYPE_RAID5)
1038 {
1039 grub_dprintf ("btrfs", "RAID5\n");
1040 nparities = 1;
1041 }
1042 else
1043 {
1044 grub_dprintf ("btrfs", "RAID6\n");
1045 nparities = 2;
1046 }
1047
1048 /*
1049 * RAID 6 layout consists of several stripes spread over
1050 * the disks, e.g.:
1051 *
1052 * Disk_0 Disk_1 Disk_2 Disk_3
1053 * A0 B0 P0 Q0
1054 * Q1 A1 B1 P1
1055 * P2 Q2 A2 B2
1056 *
1057 * Note: placement of the parities depend on row number.
1058 *
1059 * Pay attention that the btrfs terminology may differ from
1060 * terminology used in other RAID implementations, e.g. LVM,
1061 * dm or md. The main difference is that btrfs calls contiguous
1062 * block of data on a given disk, e.g. A0, stripe instead of chunk.
1063 *
1064 * The variables listed below have following meaning:
1065 * - stripe_nr is the stripe number excluding the parities
1066 * (A0 = 0, B0 = 1, A1 = 2, B1 = 3, etc.),
1067 * - high is the row number (0 for A0...Q0, 1 for Q1...P1, etc.),
1068 * - stripen is the disk number in a row (0 for A0, Q1, P2,
1069 * 1 for B0, A1, Q2, etc.),
1070 * - off is the logical address to read,
1071 * - chunk_stripe_length is the size of a stripe (typically 64 KiB),
1072 * - nstripes is the number of disks in a row,
1073 * - low is the offset of the data inside a stripe,
1074 * - stripe_offset is the data offset in an array,
1075 * - csize is the "potential" data to read; it will be reduced
1076 * to size if the latter is smaller,
1077 * - nparities is the number of parities (1 for RAID 5, 2 for
1078 * RAID 6); used only in RAID 5/6 code.
1079 */
1080 stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low);
1081
1082 /*
1083 * stripen is computed without the parities
1084 * (0 for A0, A1, A2, 1 for B0, B1, B2, etc.).
1085 */
1086 if (nparities >= nstripes)
1087 return grub_error (GRUB_ERR_BAD_FS,
1088 "invalid RAID5/6: nparities >= nstripes");
1089 high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen);
1090
1091 /*
1092 * The stripes are spread over the disks. Every each row their
1093 * positions are shifted by 1 place. So, the real disks number
1094 * change. Hence, we have to take into account current row number
1095 * modulo nstripes (0 for A0, 1 for A1, 2 for A2, etc.).
1096 */
1097 grub_divmod64 (high + stripen, nstripes, &stripen);
1098
1099 /*
1100 * parities_pos is equal to ((high - nparities) % nstripes)
1101 * (see the diagram above). However, (high - nparities) can
1102 * be negative, e.g. when high == 0, leading to an incorrect
1103 * results. (high + nstripes - nparities) is always positive and
1104 * modulo nstripes is equal to ((high - nparities) % nstripes).
1105 */
1106 grub_divmod64 (high + nstripes - nparities, nstripes, &parities_pos);
1107
1108 stripe_offset = chunk_stripe_length * high + low;
1109 csize = chunk_stripe_length - low;
1110
1111 break;
1112 }
1113 default:
1114 grub_dprintf ("btrfs", "unsupported RAID\n");
1115 return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1116 "unsupported RAID flags %" PRIxGRUB_UINT64_T,
1117 grub_le_to_cpu64 (chunk->type));
1118 }
1119 if (csize == 0)
1120 return grub_error (GRUB_ERR_BUG,
1121 "couldn't find the chunk descriptor");
1122 if (csize > (grub_uint64_t) size)
1123 csize = size;
1124
1125 for (j = 0; j < 2; j++)
1126 {
1127 grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
1128 "+0x%" PRIxGRUB_UINT64_T
1129 " (%d stripes (%d substripes) of %"
1130 PRIxGRUB_UINT64_T ")\n",
1131 grub_le_to_cpu64 (key->offset),
1132 grub_le_to_cpu64 (chunk->size),
1133 grub_le_to_cpu16 (chunk->nstripes),
1134 grub_le_to_cpu16 (chunk->nsubstripes),
1135 grub_le_to_cpu64 (chunk->stripe_length));
1136 grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n",
1137 addr);
1138
1139 if (is_raid56)
1140 {
1141 err = btrfs_read_from_chunk (data, chunk, stripen,
1142 stripe_offset,
1143 0, /* no mirror */
1144 csize, buf);
1145 grub_errno = GRUB_ERR_NONE;
1146 if (err)
1147 err = raid56_read_retry (data, chunk, stripe_offset,
1148 stripen, csize, buf, parities_pos);
1149 }
1150 else
1151 for (i = 0; i < redundancy; i++)
1152 {
1153 err = btrfs_read_from_chunk (data, chunk, stripen,
1154 stripe_offset,
1155 i, /* redundancy */
1156 csize, buf);
1157 if (!err)
1158 break;
1159 grub_errno = GRUB_ERR_NONE;
1160 }
1161 if (!err)
1162 break;
1163 }
1164 if (err)
1165 return grub_errno = err;
1166 }
1167 size -= csize;
1168 buf = (grub_uint8_t *) buf + csize;
1169 addr += csize;
1170 if (challoc)
1171 grub_free (chunk);
1172 }
1173 return GRUB_ERR_NONE;
1174 }
1175
1176 static struct grub_btrfs_data *
1177 grub_btrfs_mount (grub_device_t dev)
1178 {
1179 struct grub_btrfs_data *data;
1180 grub_err_t err;
1181
1182 if (!dev->disk)
1183 {
1184 grub_error (GRUB_ERR_BAD_FS, "not BtrFS");
1185 return NULL;
1186 }
1187
1188 data = grub_zalloc (sizeof (*data));
1189 if (!data)
1190 return NULL;
1191
1192 err = read_sblock (dev->disk, &data->sblock);
1193 if (err)
1194 {
1195 grub_free (data);
1196 return NULL;
1197 }
1198
1199 data->n_devices_allocated = 16;
1200 data->devices_attached = grub_malloc (sizeof (data->devices_attached[0])
1201 * data->n_devices_allocated);
1202 if (!data->devices_attached)
1203 {
1204 grub_free (data);
1205 return NULL;
1206 }
1207 data->n_devices_attached = 1;
1208 data->devices_attached[0].dev = dev;
1209 data->devices_attached[0].id = data->sblock.this_device.device_id;
1210
1211 return data;
1212 }
1213
1214 static void
1215 grub_btrfs_unmount (struct grub_btrfs_data *data)
1216 {
1217 unsigned i;
1218 /* The device 0 is closed one layer upper. */
1219 for (i = 1; i < data->n_devices_attached; i++)
1220 if (data->devices_attached[i].dev)
1221 grub_device_close (data->devices_attached[i].dev);
1222 grub_free (data->devices_attached);
1223 grub_free (data->extent);
1224 grub_free (data);
1225 }
1226
1227 static grub_err_t
1228 grub_btrfs_read_inode (struct grub_btrfs_data *data,
1229 struct grub_btrfs_inode *inode, grub_uint64_t num,
1230 grub_uint64_t tree)
1231 {
1232 struct grub_btrfs_key key_in, key_out;
1233 grub_disk_addr_t elemaddr;
1234 grub_size_t elemsize;
1235 grub_err_t err;
1236
1237 key_in.object_id = num;
1238 key_in.type = GRUB_BTRFS_ITEM_TYPE_INODE_ITEM;
1239 key_in.offset = 0;
1240
1241 err = lower_bound (data, &key_in, &key_out, tree, &elemaddr, &elemsize, NULL,
1242 0);
1243 if (err)
1244 return err;
1245 if (num != key_out.object_id
1246 || key_out.type != GRUB_BTRFS_ITEM_TYPE_INODE_ITEM)
1247 return grub_error (GRUB_ERR_BAD_FS, "inode not found");
1248
1249 return grub_btrfs_read_logical (data, elemaddr, inode, sizeof (*inode), 0);
1250 }
1251
1252 static void *grub_zstd_malloc (void *state __attribute__((unused)), size_t size)
1253 {
1254 return grub_malloc (size);
1255 }
1256
1257 static void grub_zstd_free (void *state __attribute__((unused)), void *address)
1258 {
1259 return grub_free (address);
1260 }
1261
1262 static ZSTD_customMem grub_zstd_allocator (void)
1263 {
1264 ZSTD_customMem allocator;
1265
1266 allocator.customAlloc = &grub_zstd_malloc;
1267 allocator.customFree = &grub_zstd_free;
1268 allocator.opaque = NULL;
1269
1270 return allocator;
1271 }
1272
1273 static grub_ssize_t
1274 grub_btrfs_zstd_decompress (char *ibuf, grub_size_t isize, grub_off_t off,
1275 char *obuf, grub_size_t osize)
1276 {
1277 void *allocated = NULL;
1278 char *otmpbuf = obuf;
1279 grub_size_t otmpsize = osize;
1280 ZSTD_DCtx *dctx = NULL;
1281 grub_size_t zstd_ret;
1282 grub_ssize_t ret = -1;
1283
1284 /*
1285 * Zstd will fail if it can't fit the entire output in the destination
1286 * buffer, so if osize isn't large enough, allocate a temporary buffer.
1287 */
1288 if (otmpsize < ZSTD_BTRFS_MAX_INPUT)
1289 {
1290 allocated = grub_malloc (ZSTD_BTRFS_MAX_INPUT);
1291 if (!allocated)
1292 {
1293 grub_error (GRUB_ERR_OUT_OF_MEMORY, "failed allocate a zstd buffer");
1294 goto err;
1295 }
1296 otmpbuf = (char *) allocated;
1297 otmpsize = ZSTD_BTRFS_MAX_INPUT;
1298 }
1299
1300 /* Create the ZSTD_DCtx. */
1301 dctx = ZSTD_createDCtx_advanced (grub_zstd_allocator ());
1302 if (!dctx)
1303 {
1304 /* ZSTD_createDCtx_advanced() only fails if it is out of memory. */
1305 grub_error (GRUB_ERR_OUT_OF_MEMORY, "failed to create a zstd context");
1306 goto err;
1307 }
1308
1309 /*
1310 * Get the real input size, there may be junk at the
1311 * end of the frame.
1312 */
1313 isize = ZSTD_findFrameCompressedSize (ibuf, isize);
1314 if (ZSTD_isError (isize))
1315 {
1316 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "zstd data corrupted");
1317 goto err;
1318 }
1319
1320 /* Decompress and check for errors. */
1321 zstd_ret = ZSTD_decompressDCtx (dctx, otmpbuf, otmpsize, ibuf, isize);
1322 if (ZSTD_isError (zstd_ret))
1323 {
1324 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "zstd data corrupted");
1325 goto err;
1326 }
1327
1328 /*
1329 * Move the requested data into the obuf. obuf may be equal
1330 * to otmpbuf, which is why grub_memmove() is required.
1331 */
1332 grub_memmove (obuf, otmpbuf + off, osize);
1333 ret = osize;
1334
1335 err:
1336 grub_free (allocated);
1337 ZSTD_freeDCtx (dctx);
1338
1339 return ret;
1340 }
1341
1342 static grub_ssize_t
1343 grub_btrfs_lzo_decompress(char *ibuf, grub_size_t isize, grub_off_t off,
1344 char *obuf, grub_size_t osize)
1345 {
1346 grub_uint32_t total_size, cblock_size;
1347 grub_size_t ret = 0;
1348 char *ibuf0 = ibuf;
1349
1350 total_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
1351 ibuf += sizeof (total_size);
1352
1353 if (isize < total_size)
1354 return -1;
1355
1356 /* Jump forward to first block with requested data. */
1357 while (off >= GRUB_BTRFS_LZO_BLOCK_SIZE)
1358 {
1359 /* Don't let following uint32_t cross the page boundary. */
1360 if (((ibuf - ibuf0) & 0xffc) == 0xffc)
1361 ibuf = ((ibuf - ibuf0 + 3) & ~3) + ibuf0;
1362
1363 cblock_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
1364 ibuf += sizeof (cblock_size);
1365
1366 if (cblock_size > GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE)
1367 return -1;
1368
1369 off -= GRUB_BTRFS_LZO_BLOCK_SIZE;
1370 ibuf += cblock_size;
1371 }
1372
1373 while (osize > 0)
1374 {
1375 lzo_uint usize = GRUB_BTRFS_LZO_BLOCK_SIZE;
1376
1377 /* Don't let following uint32_t cross the page boundary. */
1378 if (((ibuf - ibuf0) & 0xffc) == 0xffc)
1379 ibuf = ((ibuf - ibuf0 + 3) & ~3) + ibuf0;
1380
1381 cblock_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
1382 ibuf += sizeof (cblock_size);
1383
1384 if (cblock_size > GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE)
1385 return -1;
1386
1387 /* Block partially filled with requested data. */
1388 if (off > 0 || osize < GRUB_BTRFS_LZO_BLOCK_SIZE)
1389 {
1390 grub_size_t to_copy = GRUB_BTRFS_LZO_BLOCK_SIZE - off;
1391 grub_uint8_t *buf;
1392
1393 if (to_copy > osize)
1394 to_copy = osize;
1395
1396 buf = grub_malloc (GRUB_BTRFS_LZO_BLOCK_SIZE);
1397 if (!buf)
1398 return -1;
1399
1400 if (lzo1x_decompress_safe ((lzo_bytep)ibuf, cblock_size, buf, &usize,
1401 NULL) != LZO_E_OK)
1402 {
1403 grub_free (buf);
1404 return -1;
1405 }
1406
1407 if (to_copy > usize)
1408 to_copy = usize;
1409 grub_memcpy(obuf, buf + off, to_copy);
1410
1411 osize -= to_copy;
1412 ret += to_copy;
1413 obuf += to_copy;
1414 ibuf += cblock_size;
1415 off = 0;
1416
1417 grub_free (buf);
1418 continue;
1419 }
1420
1421 /* Decompress whole block directly to output buffer. */
1422 if (lzo1x_decompress_safe ((lzo_bytep)ibuf, cblock_size, (lzo_bytep)obuf,
1423 &usize, NULL) != LZO_E_OK)
1424 return -1;
1425
1426 osize -= usize;
1427 ret += usize;
1428 obuf += usize;
1429 ibuf += cblock_size;
1430 }
1431
1432 return ret;
1433 }
1434
1435 static grub_ssize_t
1436 grub_btrfs_extent_read (struct grub_btrfs_data *data,
1437 grub_uint64_t ino, grub_uint64_t tree,
1438 grub_off_t pos0, char *buf, grub_size_t len)
1439 {
1440 grub_off_t pos = pos0;
1441 while (len)
1442 {
1443 grub_size_t csize;
1444 grub_err_t err;
1445 grub_off_t extoff;
1446 if (!data->extent || data->extstart > pos || data->extino != ino
1447 || data->exttree != tree || data->extend <= pos)
1448 {
1449 struct grub_btrfs_key key_in, key_out;
1450 grub_disk_addr_t elemaddr;
1451 grub_size_t elemsize;
1452
1453 grub_free (data->extent);
1454 key_in.object_id = ino;
1455 key_in.type = GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM;
1456 key_in.offset = grub_cpu_to_le64 (pos);
1457 err = lower_bound (data, &key_in, &key_out, tree,
1458 &elemaddr, &elemsize, NULL, 0);
1459 if (err)
1460 return -1;
1461 if (key_out.object_id != ino
1462 || key_out.type != GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM)
1463 {
1464 grub_error (GRUB_ERR_BAD_FS, "extent not found");
1465 return -1;
1466 }
1467 if ((grub_ssize_t) elemsize < ((char *) &data->extent->inl
1468 - (char *) data->extent))
1469 {
1470 grub_error (GRUB_ERR_BAD_FS, "extent descriptor is too short");
1471 return -1;
1472 }
1473 data->extstart = grub_le_to_cpu64 (key_out.offset);
1474 data->extsize = elemsize;
1475 data->extent = grub_malloc (elemsize);
1476 data->extino = ino;
1477 data->exttree = tree;
1478 if (!data->extent)
1479 return grub_errno;
1480
1481 err = grub_btrfs_read_logical (data, elemaddr, data->extent,
1482 elemsize, 0);
1483 if (err)
1484 return err;
1485
1486 data->extend = data->extstart + grub_le_to_cpu64 (data->extent->size);
1487 if (data->extent->type == GRUB_BTRFS_EXTENT_REGULAR
1488 && (char *) data->extent + elemsize
1489 >= (char *) &data->extent->filled + sizeof (data->extent->filled))
1490 data->extend =
1491 data->extstart + grub_le_to_cpu64 (data->extent->filled);
1492
1493 grub_dprintf ("btrfs", "regular extent 0x%" PRIxGRUB_UINT64_T "+0x%"
1494 PRIxGRUB_UINT64_T "\n",
1495 grub_le_to_cpu64 (key_out.offset),
1496 grub_le_to_cpu64 (data->extent->size));
1497 if (data->extend <= pos)
1498 {
1499 grub_error (GRUB_ERR_BAD_FS, "extent not found");
1500 return -1;
1501 }
1502 }
1503 csize = data->extend - pos;
1504 extoff = pos - data->extstart;
1505 if (csize > len)
1506 csize = len;
1507
1508 if (data->extent->encryption)
1509 {
1510 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1511 "encryption not supported");
1512 return -1;
1513 }
1514
1515 if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE
1516 && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZLIB
1517 && data->extent->compression != GRUB_BTRFS_COMPRESSION_LZO
1518 && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZSTD)
1519 {
1520 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1521 "compression type 0x%x not supported",
1522 data->extent->compression);
1523 return -1;
1524 }
1525
1526 if (data->extent->encoding)
1527 {
1528 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "encoding not supported");
1529 return -1;
1530 }
1531
1532 switch (data->extent->type)
1533 {
1534 case GRUB_BTRFS_EXTENT_INLINE:
1535 if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZLIB)
1536 {
1537 if (grub_zlib_decompress (data->extent->inl, data->extsize -
1538 ((grub_uint8_t *) data->extent->inl
1539 - (grub_uint8_t *) data->extent),
1540 extoff, buf, csize)
1541 != (grub_ssize_t) csize)
1542 {
1543 if (!grub_errno)
1544 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
1545 "premature end of compressed");
1546 return -1;
1547 }
1548 }
1549 else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_LZO)
1550 {
1551 if (grub_btrfs_lzo_decompress(data->extent->inl, data->extsize -
1552 ((grub_uint8_t *) data->extent->inl
1553 - (grub_uint8_t *) data->extent),
1554 extoff, buf, csize)
1555 != (grub_ssize_t) csize)
1556 return -1;
1557 }
1558 else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZSTD)
1559 {
1560 if (grub_btrfs_zstd_decompress (data->extent->inl, data->extsize -
1561 ((grub_uint8_t *) data->extent->inl
1562 - (grub_uint8_t *) data->extent),
1563 extoff, buf, csize)
1564 != (grub_ssize_t) csize)
1565 return -1;
1566 }
1567 else
1568 grub_memcpy (buf, data->extent->inl + extoff, csize);
1569 break;
1570 case GRUB_BTRFS_EXTENT_REGULAR:
1571 if (!data->extent->laddr)
1572 {
1573 grub_memset (buf, 0, csize);
1574 break;
1575 }
1576
1577 if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE)
1578 {
1579 char *tmp;
1580 grub_uint64_t zsize;
1581 grub_ssize_t ret;
1582
1583 zsize = grub_le_to_cpu64 (data->extent->compressed_size);
1584 tmp = grub_malloc (zsize);
1585 if (!tmp)
1586 return -1;
1587 err = grub_btrfs_read_logical (data,
1588 grub_le_to_cpu64 (data->extent->laddr),
1589 tmp, zsize, 0);
1590 if (err)
1591 {
1592 grub_free (tmp);
1593 return -1;
1594 }
1595
1596 if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZLIB)
1597 ret = grub_zlib_decompress (tmp, zsize, extoff
1598 + grub_le_to_cpu64 (data->extent->offset),
1599 buf, csize);
1600 else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_LZO)
1601 ret = grub_btrfs_lzo_decompress (tmp, zsize, extoff
1602 + grub_le_to_cpu64 (data->extent->offset),
1603 buf, csize);
1604 else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZSTD)
1605 ret = grub_btrfs_zstd_decompress (tmp, zsize, extoff
1606 + grub_le_to_cpu64 (data->extent->offset),
1607 buf, csize);
1608 else
1609 ret = -1;
1610
1611 grub_free (tmp);
1612
1613 if (ret != (grub_ssize_t) csize)
1614 {
1615 if (!grub_errno)
1616 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
1617 "premature end of compressed");
1618 return -1;
1619 }
1620
1621 break;
1622 }
1623 err = grub_btrfs_read_logical (data,
1624 grub_le_to_cpu64 (data->extent->laddr)
1625 + grub_le_to_cpu64 (data->extent->offset)
1626 + extoff, buf, csize, 0);
1627 if (err)
1628 return -1;
1629 break;
1630 default:
1631 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1632 "unsupported extent type 0x%x", data->extent->type);
1633 return -1;
1634 }
1635 buf += csize;
1636 pos += csize;
1637 len -= csize;
1638 }
1639 return pos - pos0;
1640 }
1641
1642 static grub_err_t
1643 get_root (struct grub_btrfs_data *data, struct grub_btrfs_key *key,
1644 grub_uint64_t *tree, grub_uint8_t *type)
1645 {
1646 grub_err_t err;
1647 grub_disk_addr_t elemaddr;
1648 grub_size_t elemsize;
1649 struct grub_btrfs_key key_out, key_in;
1650 struct grub_btrfs_root_item ri;
1651
1652 key_in.object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_ROOT_VOL_OBJECTID);
1653 key_in.offset = 0;
1654 key_in.type = GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM;
1655 err = lower_bound (data, &key_in, &key_out,
1656 data->sblock.root_tree,
1657 &elemaddr, &elemsize, NULL, 0);
1658 if (err)
1659 return err;
1660 if (key_in.object_id != key_out.object_id
1661 || key_in.type != key_out.type
1662 || key_in.offset != key_out.offset)
1663 return grub_error (GRUB_ERR_BAD_FS, "no root");
1664 err = grub_btrfs_read_logical (data, elemaddr, &ri,
1665 sizeof (ri), 0);
1666 if (err)
1667 return err;
1668 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1669 key->offset = 0;
1670 key->object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK);
1671 *tree = ri.tree;
1672 *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY;
1673 return GRUB_ERR_NONE;
1674 }
1675
1676 static grub_err_t
1677 find_path (struct grub_btrfs_data *data,
1678 const char *path, struct grub_btrfs_key *key,
1679 grub_uint64_t *tree, grub_uint8_t *type)
1680 {
1681 const char *slash = path;
1682 grub_err_t err;
1683 grub_disk_addr_t elemaddr;
1684 grub_size_t elemsize;
1685 grub_size_t allocated = 0;
1686 struct grub_btrfs_dir_item *direl = NULL;
1687 struct grub_btrfs_key key_out;
1688 const char *ctoken;
1689 grub_size_t ctokenlen;
1690 char *path_alloc = NULL;
1691 char *origpath = NULL;
1692 unsigned symlinks_max = 32;
1693
1694 err = get_root (data, key, tree, type);
1695 if (err)
1696 return err;
1697
1698 origpath = grub_strdup (path);
1699 if (!origpath)
1700 return grub_errno;
1701
1702 while (1)
1703 {
1704 while (path[0] == '/')
1705 path++;
1706 if (!path[0])
1707 break;
1708 slash = grub_strchr (path, '/');
1709 if (!slash)
1710 slash = path + grub_strlen (path);
1711 ctoken = path;
1712 ctokenlen = slash - path;
1713
1714 if (*type != GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY)
1715 {
1716 grub_free (path_alloc);
1717 grub_free (origpath);
1718 return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a directory"));
1719 }
1720
1721 if (ctokenlen == 1 && ctoken[0] == '.')
1722 {
1723 path = slash;
1724 continue;
1725 }
1726 if (ctokenlen == 2 && ctoken[0] == '.' && ctoken[1] == '.')
1727 {
1728 key->type = GRUB_BTRFS_ITEM_TYPE_INODE_REF;
1729 key->offset = -1;
1730
1731 err = lower_bound (data, key, &key_out, *tree, &elemaddr, &elemsize,
1732 NULL, 0);
1733 if (err)
1734 {
1735 grub_free (direl);
1736 grub_free (path_alloc);
1737 grub_free (origpath);
1738 return err;
1739 }
1740
1741 if (key_out.type != key->type
1742 || key->object_id != key_out.object_id)
1743 {
1744 grub_free (direl);
1745 grub_free (path_alloc);
1746 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1747 grub_free (origpath);
1748 return err;
1749 }
1750
1751 *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY;
1752 key->object_id = key_out.offset;
1753
1754 path = slash;
1755
1756 continue;
1757 }
1758
1759 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1760 key->offset = grub_cpu_to_le64 (~grub_getcrc32c (1, ctoken, ctokenlen));
1761
1762 err = lower_bound (data, key, &key_out, *tree, &elemaddr, &elemsize,
1763 NULL, 0);
1764 if (err)
1765 {
1766 grub_free (direl);
1767 grub_free (path_alloc);
1768 grub_free (origpath);
1769 return err;
1770 }
1771 if (key_cmp (key, &key_out) != 0)
1772 {
1773 grub_free (direl);
1774 grub_free (path_alloc);
1775 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1776 grub_free (origpath);
1777 return err;
1778 }
1779
1780 struct grub_btrfs_dir_item *cdirel;
1781 if (elemsize > allocated)
1782 {
1783 allocated = 2 * elemsize;
1784 grub_free (direl);
1785 direl = grub_malloc (allocated + 1);
1786 if (!direl)
1787 {
1788 grub_free (path_alloc);
1789 grub_free (origpath);
1790 return grub_errno;
1791 }
1792 }
1793
1794 err = grub_btrfs_read_logical (data, elemaddr, direl, elemsize, 0);
1795 if (err)
1796 {
1797 grub_free (direl);
1798 grub_free (path_alloc);
1799 grub_free (origpath);
1800 return err;
1801 }
1802
1803 for (cdirel = direl;
1804 (grub_uint8_t *) cdirel - (grub_uint8_t *) direl
1805 < (grub_ssize_t) elemsize;
1806 cdirel = (void *) ((grub_uint8_t *) (direl + 1)
1807 + grub_le_to_cpu16 (cdirel->n)
1808 + grub_le_to_cpu16 (cdirel->m)))
1809 {
1810 if (ctokenlen == grub_le_to_cpu16 (cdirel->n)
1811 && grub_memcmp (cdirel->name, ctoken, ctokenlen) == 0)
1812 break;
1813 }
1814 if ((grub_uint8_t *) cdirel - (grub_uint8_t *) direl
1815 >= (grub_ssize_t) elemsize)
1816 {
1817 grub_free (direl);
1818 grub_free (path_alloc);
1819 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1820 grub_free (origpath);
1821 return err;
1822 }
1823
1824 path = slash;
1825 if (cdirel->type == GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK)
1826 {
1827 struct grub_btrfs_inode inode;
1828 char *tmp;
1829 if (--symlinks_max == 0)
1830 {
1831 grub_free (direl);
1832 grub_free (path_alloc);
1833 grub_free (origpath);
1834 return grub_error (GRUB_ERR_SYMLINK_LOOP,
1835 N_("too deep nesting of symlinks"));
1836 }
1837
1838 err = grub_btrfs_read_inode (data, &inode,
1839 cdirel->key.object_id, *tree);
1840 if (err)
1841 {
1842 grub_free (direl);
1843 grub_free (path_alloc);
1844 grub_free (origpath);
1845 return err;
1846 }
1847 tmp = grub_malloc (grub_le_to_cpu64 (inode.size)
1848 + grub_strlen (path) + 1);
1849 if (!tmp)
1850 {
1851 grub_free (direl);
1852 grub_free (path_alloc);
1853 grub_free (origpath);
1854 return grub_errno;
1855 }
1856
1857 if (grub_btrfs_extent_read (data, cdirel->key.object_id,
1858 *tree, 0, tmp,
1859 grub_le_to_cpu64 (inode.size))
1860 != (grub_ssize_t) grub_le_to_cpu64 (inode.size))
1861 {
1862 grub_free (direl);
1863 grub_free (path_alloc);
1864 grub_free (origpath);
1865 grub_free (tmp);
1866 return grub_errno;
1867 }
1868 grub_memcpy (tmp + grub_le_to_cpu64 (inode.size), path,
1869 grub_strlen (path) + 1);
1870 grub_free (path_alloc);
1871 path = path_alloc = tmp;
1872 if (path[0] == '/')
1873 {
1874 err = get_root (data, key, tree, type);
1875 if (err)
1876 return err;
1877 }
1878 continue;
1879 }
1880 *type = cdirel->type;
1881
1882 switch (cdirel->key.type)
1883 {
1884 case GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM:
1885 {
1886 struct grub_btrfs_root_item ri;
1887 err = lower_bound (data, &cdirel->key, &key_out,
1888 data->sblock.root_tree,
1889 &elemaddr, &elemsize, NULL, 0);
1890 if (err)
1891 {
1892 grub_free (direl);
1893 grub_free (path_alloc);
1894 grub_free (origpath);
1895 return err;
1896 }
1897 if (cdirel->key.object_id != key_out.object_id
1898 || cdirel->key.type != key_out.type)
1899 {
1900 grub_free (direl);
1901 grub_free (path_alloc);
1902 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1903 grub_free (origpath);
1904 return err;
1905 }
1906 err = grub_btrfs_read_logical (data, elemaddr, &ri,
1907 sizeof (ri), 0);
1908 if (err)
1909 {
1910 grub_free (direl);
1911 grub_free (path_alloc);
1912 grub_free (origpath);
1913 return err;
1914 }
1915 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1916 key->offset = 0;
1917 key->object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK);
1918 *tree = ri.tree;
1919 break;
1920 }
1921 case GRUB_BTRFS_ITEM_TYPE_INODE_ITEM:
1922 if (*slash && *type == GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR)
1923 {
1924 grub_free (direl);
1925 grub_free (path_alloc);
1926 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1927 grub_free (origpath);
1928 return err;
1929 }
1930 *key = cdirel->key;
1931 if (*type == GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY)
1932 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1933 break;
1934 default:
1935 grub_free (path_alloc);
1936 grub_free (origpath);
1937 grub_free (direl);
1938 return grub_error (GRUB_ERR_BAD_FS, "unrecognised object type 0x%x",
1939 cdirel->key.type);
1940 }
1941 }
1942
1943 grub_free (direl);
1944 grub_free (origpath);
1945 grub_free (path_alloc);
1946 return GRUB_ERR_NONE;
1947 }
1948
1949 static grub_err_t
1950 grub_btrfs_dir (grub_device_t device, const char *path,
1951 grub_fs_dir_hook_t hook, void *hook_data)
1952 {
1953 struct grub_btrfs_data *data = grub_btrfs_mount (device);
1954 struct grub_btrfs_key key_in, key_out;
1955 grub_err_t err;
1956 grub_disk_addr_t elemaddr;
1957 grub_size_t elemsize;
1958 grub_size_t allocated = 0;
1959 struct grub_btrfs_dir_item *direl = NULL;
1960 struct grub_btrfs_leaf_descriptor desc;
1961 int r = 0;
1962 grub_uint64_t tree;
1963 grub_uint8_t type;
1964
1965 if (!data)
1966 return grub_errno;
1967
1968 err = find_path (data, path, &key_in, &tree, &type);
1969 if (err)
1970 {
1971 grub_btrfs_unmount (data);
1972 return err;
1973 }
1974 if (type != GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY)
1975 {
1976 grub_btrfs_unmount (data);
1977 return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a directory"));
1978 }
1979
1980 err = lower_bound (data, &key_in, &key_out, tree,
1981 &elemaddr, &elemsize, &desc, 0);
1982 if (err)
1983 {
1984 grub_btrfs_unmount (data);
1985 return err;
1986 }
1987 if (key_out.type != GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
1988 || key_out.object_id != key_in.object_id)
1989 {
1990 r = next (data, &desc, &elemaddr, &elemsize, &key_out);
1991 if (r <= 0)
1992 goto out;
1993 }
1994 do
1995 {
1996 struct grub_btrfs_dir_item *cdirel;
1997 if (key_out.type != GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
1998 || key_out.object_id != key_in.object_id)
1999 {
2000 r = 0;
2001 break;
2002 }
2003 if (elemsize > allocated)
2004 {
2005 allocated = 2 * elemsize;
2006 grub_free (direl);
2007 direl = grub_malloc (allocated + 1);
2008 if (!direl)
2009 {
2010 r = -grub_errno;
2011 break;
2012 }
2013 }
2014
2015 err = grub_btrfs_read_logical (data, elemaddr, direl, elemsize, 0);
2016 if (err)
2017 {
2018 r = -err;
2019 break;
2020 }
2021
2022 for (cdirel = direl;
2023 (grub_uint8_t *) cdirel - (grub_uint8_t *) direl
2024 < (grub_ssize_t) elemsize;
2025 cdirel = (void *) ((grub_uint8_t *) (direl + 1)
2026 + grub_le_to_cpu16 (cdirel->n)
2027 + grub_le_to_cpu16 (cdirel->m)))
2028 {
2029 char c;
2030 struct grub_btrfs_inode inode;
2031 struct grub_dirhook_info info;
2032 err = grub_btrfs_read_inode (data, &inode, cdirel->key.object_id,
2033 tree);
2034 grub_memset (&info, 0, sizeof (info));
2035 if (err)
2036 grub_errno = GRUB_ERR_NONE;
2037 else
2038 {
2039 info.mtime = grub_le_to_cpu64 (inode.mtime.sec);
2040 info.mtimeset = 1;
2041 }
2042 c = cdirel->name[grub_le_to_cpu16 (cdirel->n)];
2043 cdirel->name[grub_le_to_cpu16 (cdirel->n)] = 0;
2044 info.dir = (cdirel->type == GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY);
2045 if (hook (cdirel->name, &info, hook_data))
2046 goto out;
2047 cdirel->name[grub_le_to_cpu16 (cdirel->n)] = c;
2048 }
2049 r = next (data, &desc, &elemaddr, &elemsize, &key_out);
2050 }
2051 while (r > 0);
2052
2053 out:
2054 grub_free (direl);
2055
2056 free_iterator (&desc);
2057 grub_btrfs_unmount (data);
2058
2059 return -r;
2060 }
2061
2062 static grub_err_t
2063 grub_btrfs_open (struct grub_file *file, const char *name)
2064 {
2065 struct grub_btrfs_data *data = grub_btrfs_mount (file->device);
2066 grub_err_t err;
2067 struct grub_btrfs_inode inode;
2068 grub_uint8_t type;
2069 struct grub_btrfs_key key_in;
2070
2071 if (!data)
2072 return grub_errno;
2073
2074 err = find_path (data, name, &key_in, &data->tree, &type);
2075 if (err)
2076 {
2077 grub_btrfs_unmount (data);
2078 return err;
2079 }
2080 if (type != GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR)
2081 {
2082 grub_btrfs_unmount (data);
2083 return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a regular file"));
2084 }
2085
2086 data->inode = key_in.object_id;
2087 err = grub_btrfs_read_inode (data, &inode, data->inode, data->tree);
2088 if (err)
2089 {
2090 grub_btrfs_unmount (data);
2091 return err;
2092 }
2093
2094 file->data = data;
2095 file->size = grub_le_to_cpu64 (inode.size);
2096
2097 return err;
2098 }
2099
2100 static grub_err_t
2101 grub_btrfs_close (grub_file_t file)
2102 {
2103 grub_btrfs_unmount (file->data);
2104
2105 return GRUB_ERR_NONE;
2106 }
2107
2108 static grub_ssize_t
2109 grub_btrfs_read (grub_file_t file, char *buf, grub_size_t len)
2110 {
2111 struct grub_btrfs_data *data = file->data;
2112
2113 return grub_btrfs_extent_read (data, data->inode,
2114 data->tree, file->offset, buf, len);
2115 }
2116
2117 static grub_err_t
2118 grub_btrfs_uuid (grub_device_t device, char **uuid)
2119 {
2120 struct grub_btrfs_data *data;
2121
2122 *uuid = NULL;
2123
2124 data = grub_btrfs_mount (device);
2125 if (!data)
2126 return grub_errno;
2127
2128 *uuid = grub_xasprintf ("%04x%04x-%04x-%04x-%04x-%04x%04x%04x",
2129 grub_be_to_cpu16 (data->sblock.uuid[0]),
2130 grub_be_to_cpu16 (data->sblock.uuid[1]),
2131 grub_be_to_cpu16 (data->sblock.uuid[2]),
2132 grub_be_to_cpu16 (data->sblock.uuid[3]),
2133 grub_be_to_cpu16 (data->sblock.uuid[4]),
2134 grub_be_to_cpu16 (data->sblock.uuid[5]),
2135 grub_be_to_cpu16 (data->sblock.uuid[6]),
2136 grub_be_to_cpu16 (data->sblock.uuid[7]));
2137
2138 grub_btrfs_unmount (data);
2139
2140 return grub_errno;
2141 }
2142
2143 static grub_err_t
2144 grub_btrfs_label (grub_device_t device, char **label)
2145 {
2146 struct grub_btrfs_data *data;
2147
2148 *label = NULL;
2149
2150 data = grub_btrfs_mount (device);
2151 if (!data)
2152 return grub_errno;
2153
2154 *label = grub_strndup (data->sblock.label, sizeof (data->sblock.label));
2155
2156 grub_btrfs_unmount (data);
2157
2158 return grub_errno;
2159 }
2160
2161 #ifdef GRUB_UTIL
2162 static grub_err_t
2163 grub_btrfs_embed (grub_device_t device __attribute__ ((unused)),
2164 unsigned int *nsectors,
2165 unsigned int max_nsectors,
2166 grub_embed_type_t embed_type,
2167 grub_disk_addr_t **sectors)
2168 {
2169 unsigned i;
2170
2171 if (embed_type != GRUB_EMBED_PCBIOS)
2172 return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
2173 "BtrFS currently supports only PC-BIOS embedding");
2174
2175 if (64 * 2 - 1 < *nsectors)
2176 return grub_error (GRUB_ERR_OUT_OF_RANGE,
2177 N_("your core.img is unusually large. "
2178 "It won't fit in the embedding area"));
2179
2180 *nsectors = 64 * 2 - 1;
2181 if (*nsectors > max_nsectors)
2182 *nsectors = max_nsectors;
2183 *sectors = grub_calloc (*nsectors, sizeof (**sectors));
2184 if (!*sectors)
2185 return grub_errno;
2186 for (i = 0; i < *nsectors; i++)
2187 (*sectors)[i] = i + 1;
2188
2189 return GRUB_ERR_NONE;
2190 }
2191 #endif
2192
2193 static struct grub_fs grub_btrfs_fs = {
2194 .name = "btrfs",
2195 .fs_dir = grub_btrfs_dir,
2196 .fs_open = grub_btrfs_open,
2197 .fs_read = grub_btrfs_read,
2198 .fs_close = grub_btrfs_close,
2199 .fs_uuid = grub_btrfs_uuid,
2200 .fs_label = grub_btrfs_label,
2201 #ifdef GRUB_UTIL
2202 .fs_embed = grub_btrfs_embed,
2203 .reserved_first_sector = 1,
2204 .blocklist_install = 0,
2205 #endif
2206 };
2207
2208 GRUB_MOD_INIT (btrfs)
2209 {
2210 grub_fs_register (&grub_btrfs_fs);
2211 }
2212
2213 GRUB_MOD_FINI (btrfs)
2214 {
2215 grub_fs_unregister (&grub_btrfs_fs);
2216 }
The GNU GRand Unified Bootloader for Proxmox projects