1 /*
2 * The object map B-tree functions
3 *
4 * Copyright (C) 2018-2021, Joachim Metz <joachim.metz@gmail.com>
5 *
6 * Refer to AUTHORS for acknowledgements.
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22 #include <common.h>
23 #include <byte_stream.h>
24 #include <memory.h>
25 #include <types.h>
26
27 #include "libfsapfs_btree_entry.h"
28 #include "libfsapfs_btree_node.h"
29 #include "libfsapfs_data_block.h"
30 #include "libfsapfs_definitions.h"
31 #include "libfsapfs_io_handle.h"
32 #include "libfsapfs_libbfio.h"
33 #include "libfsapfs_libcerror.h"
34 #include "libfsapfs_libcnotify.h"
35 #include "libfsapfs_libfcache.h"
36 #include "libfsapfs_libfdata.h"
37 #include "libfsapfs_object_map_btree.h"
38 #include "libfsapfs_object_map_descriptor.h"
39
40 #include "fsapfs_object.h"
41 #include "fsapfs_object_map.h"
42
43 /* Creates a object map B-tree
44 * Make sure the value object_map_btree is referencing, is set to NULL
45 * Returns 1 if successful or -1 on error
46 */
libfsapfs_object_map_btree_initialize(libfsapfs_object_map_btree_t ** object_map_btree,libfsapfs_io_handle_t * io_handle,libfdata_vector_t * data_block_vector,uint64_t root_node_block_number,libcerror_error_t ** error)47 int libfsapfs_object_map_btree_initialize(
48 libfsapfs_object_map_btree_t **object_map_btree,
49 libfsapfs_io_handle_t *io_handle,
50 libfdata_vector_t *data_block_vector,
51 uint64_t root_node_block_number,
52 libcerror_error_t **error )
53 {
54 static char *function = "libfsapfs_object_map_btree_initialize";
55
56 if( object_map_btree == NULL )
57 {
58 libcerror_error_set(
59 error,
60 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
61 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
62 "%s: invalid object map B-tree.",
63 function );
64
65 return( -1 );
66 }
67 if( *object_map_btree != NULL )
68 {
69 libcerror_error_set(
70 error,
71 LIBCERROR_ERROR_DOMAIN_RUNTIME,
72 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
73 "%s: invalid object map B-tree value already set.",
74 function );
75
76 return( -1 );
77 }
78 *object_map_btree = memory_allocate_structure(
79 libfsapfs_object_map_btree_t );
80
81 if( *object_map_btree == NULL )
82 {
83 libcerror_error_set(
84 error,
85 LIBCERROR_ERROR_DOMAIN_MEMORY,
86 LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
87 "%s: unable to create object map B-tree.",
88 function );
89
90 goto on_error;
91 }
92 if( memory_set(
93 *object_map_btree,
94 0,
95 sizeof( libfsapfs_object_map_btree_t ) ) == NULL )
96 {
97 libcerror_error_set(
98 error,
99 LIBCERROR_ERROR_DOMAIN_MEMORY,
100 LIBCERROR_MEMORY_ERROR_SET_FAILED,
101 "%s: unable to clear object map B-tree.",
102 function );
103
104 memory_free(
105 *object_map_btree );
106
107 *object_map_btree = NULL;
108
109 return( -1 );
110 }
111 if( libfcache_cache_initialize(
112 &( ( *object_map_btree )->data_block_cache ),
113 LIBFSAPFS_MAXIMUM_CACHE_ENTRIES_DATA_BLOCKS,
114 error ) != 1 )
115 {
116 libcerror_error_set(
117 error,
118 LIBCERROR_ERROR_DOMAIN_RUNTIME,
119 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
120 "%s: unable to create data block cache.",
121 function );
122
123 goto on_error;
124 }
125 if( libfcache_cache_initialize(
126 &( ( *object_map_btree )->node_cache ),
127 LIBFSAPFS_MAXIMUM_CACHE_ENTRIES_BTREE_NODES,
128 error ) != 1 )
129 {
130 libcerror_error_set(
131 error,
132 LIBCERROR_ERROR_DOMAIN_RUNTIME,
133 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
134 "%s: unable to create node cache.",
135 function );
136
137 goto on_error;
138 }
139 ( *object_map_btree )->io_handle = io_handle;
140 ( *object_map_btree )->data_block_vector = data_block_vector;
141 ( *object_map_btree )->root_node_block_number = root_node_block_number;
142
143 return( 1 );
144
145 on_error:
146 if( *object_map_btree != NULL )
147 {
148 memory_free(
149 *object_map_btree );
150
151 *object_map_btree = NULL;
152 }
153 return( -1 );
154 }
155
156 /* Frees a object map B-tree
157 * Returns 1 if successful or -1 on error
158 */
libfsapfs_object_map_btree_free(libfsapfs_object_map_btree_t ** object_map_btree,libcerror_error_t ** error)159 int libfsapfs_object_map_btree_free(
160 libfsapfs_object_map_btree_t **object_map_btree,
161 libcerror_error_t **error )
162 {
163 static char *function = "libfsapfs_object_map_btree_free";
164 int result = 1;
165
166 if( object_map_btree == NULL )
167 {
168 libcerror_error_set(
169 error,
170 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
171 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
172 "%s: invalid object map B-tree.",
173 function );
174
175 return( -1 );
176 }
177 if( *object_map_btree != NULL )
178 {
179 /* The data_block_vector is referenced and freed elsewhere
180 */
181 if( libfcache_cache_free(
182 &( ( *object_map_btree )->node_cache ),
183 error ) != 1 )
184 {
185 libcerror_error_set(
186 error,
187 LIBCERROR_ERROR_DOMAIN_RUNTIME,
188 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
189 "%s: unable to free node cache.",
190 function );
191
192 result = -1;
193 }
194 if( libfcache_cache_free(
195 &( ( *object_map_btree )->data_block_cache ),
196 error ) != 1 )
197 {
198 libcerror_error_set(
199 error,
200 LIBCERROR_ERROR_DOMAIN_RUNTIME,
201 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
202 "%s: unable to free data block cache.",
203 function );
204
205 result = -1;
206 }
207 memory_free(
208 *object_map_btree );
209
210 *object_map_btree = NULL;
211 }
212 return( result );
213 }
214
215 /* Retrieves the object map B-tree root node
216 * Returns 1 if successful or -1 on error
217 */
libfsapfs_object_map_btree_get_root_node(libfsapfs_object_map_btree_t * object_map_btree,libbfio_handle_t * file_io_handle,uint64_t root_node_block_number,libfsapfs_btree_node_t ** root_node,libcerror_error_t ** error)218 int libfsapfs_object_map_btree_get_root_node(
219 libfsapfs_object_map_btree_t *object_map_btree,
220 libbfio_handle_t *file_io_handle,
221 uint64_t root_node_block_number,
222 libfsapfs_btree_node_t **root_node,
223 libcerror_error_t **error )
224 {
225 libfcache_cache_value_t *cache_value = NULL;
226 libfsapfs_btree_node_t *node = NULL;
227 libfsapfs_data_block_t *data_block = NULL;
228 static char *function = "libfsapfs_object_map_btree_get_root_node";
229 int result = 0;
230
231 #if defined( HAVE_PROFILER )
232 int64_t profiler_start_timestamp = 0;
233 #endif
234
235 if( object_map_btree == NULL )
236 {
237 libcerror_error_set(
238 error,
239 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
240 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
241 "%s: invalid object map B-tree.",
242 function );
243
244 return( -1 );
245 }
246 if( root_node_block_number > (uint64_t) INT_MAX )
247 {
248 libcerror_error_set(
249 error,
250 LIBCERROR_ERROR_DOMAIN_RUNTIME,
251 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
252 "%s: invalid root node block number value out of bounds.",
253 function );
254
255 return( -1 );
256 }
257 if( root_node == NULL )
258 {
259 libcerror_error_set(
260 error,
261 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
262 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
263 "%s: invalid root node.",
264 function );
265
266 return( -1 );
267 }
268 #if defined( HAVE_PROFILER )
269 if( object_map_btree->io_handle->profiler != NULL )
270 {
271 if( libfsapfs_profiler_start_timing(
272 object_map_btree->io_handle->profiler,
273 &profiler_start_timestamp,
274 error ) != 1 )
275 {
276 libcerror_error_set(
277 error,
278 LIBCERROR_ERROR_DOMAIN_RUNTIME,
279 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
280 "%s: unable to start timing.",
281 function );
282
283 goto on_error;
284 }
285 }
286 #endif /* defined( HAVE_PROFILER ) */
287
288 result = libfcache_cache_get_value_by_identifier(
289 object_map_btree->node_cache,
290 0,
291 (off64_t) root_node_block_number,
292 0,
293 &cache_value,
294 error );
295
296 if( result == -1 )
297 {
298 libcerror_error_set(
299 error,
300 LIBCERROR_ERROR_DOMAIN_RUNTIME,
301 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
302 "%s: unable to retrieve value from cache.",
303 function );
304
305 goto on_error;
306 }
307 else if( result == 0 )
308 {
309 if( libfdata_vector_get_element_value_by_index(
310 object_map_btree->data_block_vector,
311 (intptr_t *) file_io_handle,
312 (libfdata_cache_t *) object_map_btree->data_block_cache,
313 (int) root_node_block_number,
314 (intptr_t **) &data_block,
315 0,
316 error ) != 1 )
317 {
318 libcerror_error_set(
319 error,
320 LIBCERROR_ERROR_DOMAIN_RUNTIME,
321 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
322 "%s: unable to retrieve data block: %" PRIu64 ".",
323 function,
324 root_node_block_number );
325
326 goto on_error;
327 }
328 if( data_block == NULL )
329 {
330 libcerror_error_set(
331 error,
332 LIBCERROR_ERROR_DOMAIN_RUNTIME,
333 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
334 "%s: invalid data block: %" PRIu64 ".",
335 function,
336 root_node_block_number );
337
338 goto on_error;
339 }
340 if( libfsapfs_btree_node_initialize(
341 &node,
342 error ) != 1 )
343 {
344 libcerror_error_set(
345 error,
346 LIBCERROR_ERROR_DOMAIN_RUNTIME,
347 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
348 "%s: unable to create B-tree node.",
349 function );
350
351 goto on_error;
352 }
353 if( libfsapfs_btree_node_read_data(
354 node,
355 data_block->data,
356 data_block->data_size,
357 error ) != 1 )
358 {
359 libcerror_error_set(
360 error,
361 LIBCERROR_ERROR_DOMAIN_IO,
362 LIBCERROR_IO_ERROR_READ_FAILED,
363 "%s: unable to read B-tree node.",
364 function );
365
366 goto on_error;
367 }
368 if( node->object_type != 0x40000002UL )
369 {
370 libcerror_error_set(
371 error,
372 LIBCERROR_ERROR_DOMAIN_RUNTIME,
373 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
374 "%s: invalid object type: 0x%08" PRIx32 ".",
375 function,
376 node->object_type );
377
378 goto on_error;
379 }
380 if( node->object_subtype != 0x0000000bUL )
381 {
382 libcerror_error_set(
383 error,
384 LIBCERROR_ERROR_DOMAIN_RUNTIME,
385 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
386 "%s: invalid object subtype: 0x%08" PRIx32 ".",
387 function,
388 node->object_subtype );
389
390 goto on_error;
391 }
392 if( ( ( node->node_header->flags & 0x0001 ) == 0 )
393 || ( ( node->node_header->flags & 0x0004 ) == 0 ) )
394 {
395 libcerror_error_set(
396 error,
397 LIBCERROR_ERROR_DOMAIN_RUNTIME,
398 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
399 "%s: unsupported flags: 0x%04" PRIx16 ".",
400 function,
401 node->node_header->flags );
402
403 goto on_error;
404 }
405 if( node->footer->node_size != 4096 )
406 {
407 libcerror_error_set(
408 error,
409 LIBCERROR_ERROR_DOMAIN_RUNTIME,
410 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
411 "%s: invalid node size value out of bounds.",
412 function );
413
414 goto on_error;
415 }
416 if( node->footer->key_size != sizeof( fsapfs_object_map_btree_key_t ) )
417 {
418 libcerror_error_set(
419 error,
420 LIBCERROR_ERROR_DOMAIN_RUNTIME,
421 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
422 "%s: invalid key size value out of bounds.",
423 function );
424
425 goto on_error;
426 }
427 if( node->footer->value_size != sizeof( fsapfs_object_map_btree_value_t ) )
428 {
429 libcerror_error_set(
430 error,
431 LIBCERROR_ERROR_DOMAIN_RUNTIME,
432 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
433 "%s: invalid value size value out of bounds.",
434 function );
435
436 goto on_error;
437 }
438 if( libfcache_cache_set_value_by_identifier(
439 object_map_btree->node_cache,
440 0,
441 (off64_t) root_node_block_number,
442 0,
443 (intptr_t *) node,
444 (int (*)(intptr_t **, libcerror_error_t **)) &libfsapfs_btree_node_free,
445 LIBFCACHE_CACHE_VALUE_FLAG_MANAGED,
446 error ) != 1 )
447 {
448 libcerror_error_set(
449 error,
450 LIBCERROR_ERROR_DOMAIN_RUNTIME,
451 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
452 "%s: unable to set value in cache.",
453 function );
454
455 goto on_error;
456 }
457 node = NULL;
458
459 if( libfcache_cache_get_value_by_identifier(
460 object_map_btree->node_cache,
461 0,
462 (off64_t) root_node_block_number,
463 0,
464 &cache_value,
465 error ) != 1 )
466 {
467 libcerror_error_set(
468 error,
469 LIBCERROR_ERROR_DOMAIN_RUNTIME,
470 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
471 "%s: unable to retrieve value from cache.",
472 function );
473
474 goto on_error;
475 }
476 }
477 #if defined( HAVE_PROFILER )
478 if( object_map_btree->io_handle->profiler != NULL )
479 {
480 if( libfsapfs_profiler_stop_timing(
481 object_map_btree->io_handle->profiler,
482 profiler_start_timestamp,
483 function,
484 root_node_block_number * object_map_btree->io_handle->block_size,
485 object_map_btree->io_handle->block_size,
486 error ) != 1 )
487 {
488 libcerror_error_set(
489 error,
490 LIBCERROR_ERROR_DOMAIN_RUNTIME,
491 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
492 "%s: unable to stop timing.",
493 function );
494
495 goto on_error;
496 }
497 }
498 #endif /* defined( HAVE_PROFILER ) */
499
500 if( libfcache_cache_value_get_value(
501 cache_value,
502 (intptr_t **) root_node,
503 error ) != 1 )
504 {
505 libcerror_error_set(
506 error,
507 LIBCERROR_ERROR_DOMAIN_RUNTIME,
508 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
509 "%s: unable to retrieve root node.",
510 function );
511
512 goto on_error;
513 }
514 return( 1 );
515
516 on_error:
517 if( node != NULL )
518 {
519 libfsapfs_btree_node_free(
520 &node,
521 NULL );
522 }
523 return( -1 );
524 }
525
526 /* Retrieves a object map B-tree sub node
527 * Returns 1 if successful or -1 on error
528 */
libfsapfs_object_map_btree_get_sub_node(libfsapfs_object_map_btree_t * object_map_btree,libbfio_handle_t * file_io_handle,uint64_t sub_node_block_number,libfsapfs_btree_node_t ** sub_node,libcerror_error_t ** error)529 int libfsapfs_object_map_btree_get_sub_node(
530 libfsapfs_object_map_btree_t *object_map_btree,
531 libbfio_handle_t *file_io_handle,
532 uint64_t sub_node_block_number,
533 libfsapfs_btree_node_t **sub_node,
534 libcerror_error_t **error )
535 {
536 libfcache_cache_value_t *cache_value = NULL;
537 libfsapfs_btree_node_t *node = NULL;
538 libfsapfs_data_block_t *data_block = NULL;
539 static char *function = "libfsapfs_object_map_btree_get_sub_node";
540 int result = 0;
541
542 #if defined( HAVE_PROFILER )
543 int64_t profiler_start_timestamp = 0;
544 #endif
545
546 if( object_map_btree == NULL )
547 {
548 libcerror_error_set(
549 error,
550 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
551 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
552 "%s: invalid object map B-tree.",
553 function );
554
555 return( -1 );
556 }
557 if( sub_node_block_number > (uint64_t) INT_MAX )
558 {
559 libcerror_error_set(
560 error,
561 LIBCERROR_ERROR_DOMAIN_RUNTIME,
562 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
563 "%s: invalid sub node block number value out of bounds.",
564 function );
565
566 return( -1 );
567 }
568 if( sub_node == NULL )
569 {
570 libcerror_error_set(
571 error,
572 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
573 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
574 "%s: invalid sub node.",
575 function );
576
577 return( -1 );
578 }
579 #if defined( HAVE_PROFILER )
580 if( object_map_btree->io_handle->profiler != NULL )
581 {
582 if( libfsapfs_profiler_start_timing(
583 object_map_btree->io_handle->profiler,
584 &profiler_start_timestamp,
585 error ) != 1 )
586 {
587 libcerror_error_set(
588 error,
589 LIBCERROR_ERROR_DOMAIN_RUNTIME,
590 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
591 "%s: unable to start timing.",
592 function );
593
594 goto on_error;
595 }
596 }
597 #endif /* defined( HAVE_PROFILER ) */
598
599 result = libfcache_cache_get_value_by_identifier(
600 object_map_btree->node_cache,
601 0,
602 (off64_t) sub_node_block_number,
603 0,
604 &cache_value,
605 error );
606
607 if( result == -1 )
608 {
609 libcerror_error_set(
610 error,
611 LIBCERROR_ERROR_DOMAIN_RUNTIME,
612 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
613 "%s: unable to retrieve value from cache.",
614 function );
615
616 goto on_error;
617 }
618 else if( result == 0 )
619 {
620 if( libfdata_vector_get_element_value_by_index(
621 object_map_btree->data_block_vector,
622 (intptr_t *) file_io_handle,
623 (libfdata_cache_t *) object_map_btree->data_block_cache,
624 (int) sub_node_block_number,
625 (intptr_t **) &data_block,
626 0,
627 error ) != 1 )
628 {
629 libcerror_error_set(
630 error,
631 LIBCERROR_ERROR_DOMAIN_RUNTIME,
632 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
633 "%s: unable to retrieve data block: %" PRIu64 ".",
634 function,
635 sub_node_block_number );
636
637 goto on_error;
638 }
639 if( data_block == NULL )
640 {
641 libcerror_error_set(
642 error,
643 LIBCERROR_ERROR_DOMAIN_RUNTIME,
644 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
645 "%s: invalid data block: %" PRIu64 ".",
646 function,
647 sub_node_block_number );
648
649 goto on_error;
650 }
651 if( libfsapfs_btree_node_initialize(
652 &node,
653 error ) != 1 )
654 {
655 libcerror_error_set(
656 error,
657 LIBCERROR_ERROR_DOMAIN_RUNTIME,
658 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
659 "%s: unable to create B-tree node.",
660 function );
661
662 goto on_error;
663 }
664 if( libfsapfs_btree_node_read_data(
665 node,
666 data_block->data,
667 data_block->data_size,
668 error ) != 1 )
669 {
670 libcerror_error_set(
671 error,
672 LIBCERROR_ERROR_DOMAIN_IO,
673 LIBCERROR_IO_ERROR_READ_FAILED,
674 "%s: unable to read B-tree node.",
675 function );
676
677 goto on_error;
678 }
679 if( node->object_type != 0x40000003UL )
680 {
681 libcerror_error_set(
682 error,
683 LIBCERROR_ERROR_DOMAIN_RUNTIME,
684 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
685 "%s: invalid object type: 0x%08" PRIx32 ".",
686 function,
687 node->object_type );
688
689 goto on_error;
690 }
691 if( node->object_subtype != 0x0000000bUL )
692 {
693 libcerror_error_set(
694 error,
695 LIBCERROR_ERROR_DOMAIN_RUNTIME,
696 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
697 "%s: invalid object subtype: 0x%08" PRIx32 ".",
698 function,
699 node->object_subtype );
700
701 goto on_error;
702 }
703 if( ( ( node->node_header->flags & 0x0001 ) != 0 )
704 || ( ( node->node_header->flags & 0x0004 ) == 0 ) )
705 {
706 libcerror_error_set(
707 error,
708 LIBCERROR_ERROR_DOMAIN_RUNTIME,
709 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
710 "%s: unsupported flags: 0x%04" PRIx16 ".",
711 function,
712 node->node_header->flags );
713
714 goto on_error;
715 }
716 if( libfcache_cache_set_value_by_identifier(
717 object_map_btree->node_cache,
718 0,
719 (off64_t) sub_node_block_number,
720 0,
721 (intptr_t *) node,
722 (int (*)(intptr_t **, libcerror_error_t **)) &libfsapfs_btree_node_free,
723 LIBFCACHE_CACHE_VALUE_FLAG_MANAGED,
724 error ) != 1 )
725 {
726 libcerror_error_set(
727 error,
728 LIBCERROR_ERROR_DOMAIN_RUNTIME,
729 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
730 "%s: unable to set value in cache.",
731 function );
732
733 goto on_error;
734 }
735 node = NULL;
736
737 if( libfcache_cache_get_value_by_identifier(
738 object_map_btree->node_cache,
739 0,
740 (off64_t) sub_node_block_number,
741 0,
742 &cache_value,
743 error ) != 1 )
744 {
745 libcerror_error_set(
746 error,
747 LIBCERROR_ERROR_DOMAIN_RUNTIME,
748 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
749 "%s: unable to retrieve value from cache.",
750 function );
751
752 goto on_error;
753 }
754 }
755 #if defined( HAVE_PROFILER )
756 if( object_map_btree->io_handle->profiler != NULL )
757 {
758 if( libfsapfs_profiler_stop_timing(
759 object_map_btree->io_handle->profiler,
760 profiler_start_timestamp,
761 function,
762 sub_node_block_number * object_map_btree->io_handle->block_size,
763 object_map_btree->io_handle->block_size,
764 error ) != 1 )
765 {
766 libcerror_error_set(
767 error,
768 LIBCERROR_ERROR_DOMAIN_RUNTIME,
769 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
770 "%s: unable to stop timing.",
771 function );
772
773 goto on_error;
774 }
775 }
776 #endif /* defined( HAVE_PROFILER ) */
777
778 if( libfcache_cache_value_get_value(
779 cache_value,
780 (intptr_t **) sub_node,
781 error ) != 1 )
782 {
783 libcerror_error_set(
784 error,
785 LIBCERROR_ERROR_DOMAIN_RUNTIME,
786 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
787 "%s: unable to retrieve sub node.",
788 function );
789
790 goto on_error;
791 }
792 return( 1 );
793
794 on_error:
795 if( node != NULL )
796 {
797 libfsapfs_btree_node_free(
798 &node,
799 NULL );
800 }
801 return( -1 );
802 }
803
804 /* Retrieves an entry for a specific identifier from the object map B-tree node
805 * Returns 1 if successful, 0 if not found or -1 on error
806 */
libfsapfs_object_map_btree_get_entry_from_node_by_identifier(libfsapfs_object_map_btree_t * object_map_btree,libfsapfs_btree_node_t * node,uint64_t object_identifier,libfsapfs_btree_entry_t ** btree_entry,libcerror_error_t ** error)807 int libfsapfs_object_map_btree_get_entry_from_node_by_identifier(
808 libfsapfs_object_map_btree_t *object_map_btree,
809 libfsapfs_btree_node_t *node,
810 uint64_t object_identifier,
811 libfsapfs_btree_entry_t **btree_entry,
812 libcerror_error_t **error )
813 {
814 libfsapfs_btree_entry_t *entry = NULL;
815 libfsapfs_btree_entry_t *previous_entry = NULL;
816 static char *function = "libfsapfs_object_map_btree_get_entry_from_node_by_identifier";
817 uint64_t object_map_identifier = 0;
818 int btree_entry_index = 0;
819 int is_leaf_node = 0;
820 int number_of_entries = 0;
821
822 if( object_map_btree == NULL )
823 {
824 libcerror_error_set(
825 error,
826 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
827 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
828 "%s: invalid object map B-tree.",
829 function );
830
831 return( -1 );
832 }
833 if( btree_entry == NULL )
834 {
835 libcerror_error_set(
836 error,
837 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
838 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
839 "%s: invalid B-tree entry.",
840 function );
841
842 return( -1 );
843 }
844 #if defined( HAVE_DEBUG_OUTPUT )
845 if( libcnotify_verbose != 0 )
846 {
847 libcnotify_printf(
848 "%s: retrieving B-tree entry identifier: %" PRIu64 ".\n",
849 function,
850 object_identifier );
851 }
852 #endif
853 is_leaf_node = libfsapfs_btree_node_is_leaf_node(
854 node,
855 error );
856
857 if( is_leaf_node == -1 )
858 {
859 libcerror_error_set(
860 error,
861 LIBCERROR_ERROR_DOMAIN_RUNTIME,
862 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
863 "%s: unable to determine if B-tree node is a leaf node.",
864 function );
865
866 return( -1 );
867 }
868 if( libfsapfs_btree_node_get_number_of_entries(
869 node,
870 &number_of_entries,
871 error ) != 1 )
872 {
873 libcerror_error_set(
874 error,
875 LIBCERROR_ERROR_DOMAIN_RUNTIME,
876 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
877 "%s: unable to retrieve number of entries from B-tree node.",
878 function );
879
880 return( -1 );
881 }
882 for( btree_entry_index = 0;
883 btree_entry_index < number_of_entries;
884 btree_entry_index++ )
885 {
886 if( libfsapfs_btree_node_get_entry_by_index(
887 node,
888 btree_entry_index,
889 &entry,
890 error ) != 1 )
891 {
892 libcerror_error_set(
893 error,
894 LIBCERROR_ERROR_DOMAIN_RUNTIME,
895 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
896 "%s: unable to retrieve number of entries from B-tree node.",
897 function );
898
899 return( -1 );
900 }
901 if( entry == NULL )
902 {
903 libcerror_error_set(
904 error,
905 LIBCERROR_ERROR_DOMAIN_RUNTIME,
906 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
907 "%s: invalid B-tree entry: %d.",
908 function,
909 btree_entry_index );
910
911 return( -1 );
912 }
913 if( entry->key_data == NULL )
914 {
915 libcerror_error_set(
916 error,
917 LIBCERROR_ERROR_DOMAIN_RUNTIME,
918 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
919 "%s: invalid B-tree entry: %d - missing key data.",
920 function,
921 btree_entry_index );
922
923 return( -1 );
924 }
925 if( entry->key_data_size < 8 )
926 {
927 libcerror_error_set(
928 error,
929 LIBCERROR_ERROR_DOMAIN_RUNTIME,
930 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
931 "%s: invalid B-tree entry: %d - key data size value out of bounds.",
932 function,
933 btree_entry_index );
934
935 return( -1 );
936 }
937 byte_stream_copy_to_uint64_little_endian(
938 entry->key_data,
939 object_map_identifier );
940
941 #if defined( HAVE_DEBUG_OUTPUT )
942 if( libcnotify_verbose != 0 )
943 {
944 libcnotify_printf(
945 "%s: B-tree entry: %d, identifier: %" PRIu64 "\n",
946 function,
947 btree_entry_index,
948 object_map_identifier );
949 }
950 #endif
951 if( object_map_identifier > object_identifier )
952 {
953 break;
954 }
955 if( is_leaf_node != 0 )
956 {
957 if( object_map_identifier == object_identifier )
958 {
959 *btree_entry = entry;
960
961 return( 1 );
962 }
963 }
964 else
965 {
966 if( object_map_identifier >= object_identifier )
967 {
968 if( ( previous_entry == NULL )
969 || ( object_map_identifier == object_identifier ) )
970 {
971 previous_entry = entry;
972 }
973 *btree_entry = previous_entry;
974
975 return( 1 );
976 }
977 previous_entry = entry;
978 }
979 }
980 if( is_leaf_node == 0 )
981 {
982 *btree_entry = previous_entry;
983
984 return( 1 );
985 }
986 return( 0 );
987 }
988
989 /* Retrieves an entry for a specific identifier from the object map B-tree
990 * Returns 1 if successful, 0 if not found or -1 on error
991 */
libfsapfs_object_map_btree_get_entry_by_identifier(libfsapfs_object_map_btree_t * object_map_btree,libbfio_handle_t * file_io_handle,uint64_t object_identifier,libfsapfs_btree_node_t ** btree_node,libfsapfs_btree_entry_t ** btree_entry,libcerror_error_t ** error)992 int libfsapfs_object_map_btree_get_entry_by_identifier(
993 libfsapfs_object_map_btree_t *object_map_btree,
994 libbfio_handle_t *file_io_handle,
995 uint64_t object_identifier,
996 libfsapfs_btree_node_t **btree_node,
997 libfsapfs_btree_entry_t **btree_entry,
998 libcerror_error_t **error )
999 {
1000 libfsapfs_btree_entry_t *entry = NULL;
1001 libfsapfs_btree_node_t *node = NULL;
1002 static char *function = "libfsapfs_object_map_btree_get_entry_by_identifier";
1003 uint64_t sub_node_block_number = 0;
1004 int is_leaf_node = 0;
1005 int recursion_depth = 0;
1006 int result = 0;
1007
1008 if( object_map_btree == NULL )
1009 {
1010 libcerror_error_set(
1011 error,
1012 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1013 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1014 "%s: invalid object map B-tree.",
1015 function );
1016
1017 return( -1 );
1018 }
1019 if( btree_node == NULL )
1020 {
1021 libcerror_error_set(
1022 error,
1023 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1024 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1025 "%s: invalid B-tree node.",
1026 function );
1027
1028 return( -1 );
1029 }
1030 if( btree_entry == NULL )
1031 {
1032 libcerror_error_set(
1033 error,
1034 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1035 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1036 "%s: invalid B-tree entry.",
1037 function );
1038
1039 return( -1 );
1040 }
1041 if( libfsapfs_object_map_btree_get_root_node(
1042 object_map_btree,
1043 file_io_handle,
1044 object_map_btree->root_node_block_number,
1045 &node,
1046 error ) != 1 )
1047 {
1048 libcerror_error_set(
1049 error,
1050 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1051 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1052 "%s: unable to retrieve B-tree root node.",
1053 function );
1054
1055 return( -1 );
1056 }
1057 do
1058 {
1059 if( ( recursion_depth < 0 )
1060 || ( recursion_depth > LIBFSAPFS_MAXIMUM_BTREE_NODE_RECURSION_DEPTH ) )
1061 {
1062 libcerror_error_set(
1063 error,
1064 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1065 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
1066 "%s: invalid recursion depth value out of bounds.",
1067 function );
1068
1069 return( -1 );
1070 }
1071 is_leaf_node = libfsapfs_btree_node_is_leaf_node(
1072 node,
1073 error );
1074
1075 if( is_leaf_node == -1 )
1076 {
1077 libcerror_error_set(
1078 error,
1079 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1080 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1081 "%s: unable to determine if B-tree node is a leaf node.",
1082 function );
1083
1084 return( -1 );
1085 }
1086 result = libfsapfs_object_map_btree_get_entry_from_node_by_identifier(
1087 object_map_btree,
1088 node,
1089 object_identifier,
1090 &entry,
1091 error );
1092
1093 if( result == -1 )
1094 {
1095 libcerror_error_set(
1096 error,
1097 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1098 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1099 "%s: unable to retrieve entry from B-tree node.",
1100 function );
1101
1102 return( -1 );
1103 }
1104 else if( result == 0 )
1105 {
1106 break;
1107 }
1108 if( is_leaf_node != 0 )
1109 {
1110 *btree_node = node;
1111 *btree_entry = entry;
1112
1113 return( 1 );
1114 }
1115 if( entry == NULL )
1116 {
1117 libcerror_error_set(
1118 error,
1119 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1120 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1121 "%s: invalid B-tree entry.",
1122 function );
1123
1124 return( -1 );
1125 }
1126 if( entry->value_data == NULL )
1127 {
1128 libcerror_error_set(
1129 error,
1130 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1131 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1132 "%s: invalid B-tree entry - missing value data.",
1133 function );
1134
1135 return( -1 );
1136 }
1137 if( entry->value_data_size != 8 )
1138 {
1139 libcerror_error_set(
1140 error,
1141 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1142 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
1143 "%s: invalid B-tree entry - unsupported value data size.",
1144 function );
1145
1146 return( -1 );
1147 }
1148 byte_stream_copy_to_uint64_little_endian(
1149 entry->value_data,
1150 sub_node_block_number );
1151
1152 #if defined( HAVE_DEBUG_OUTPUT )
1153 if( libcnotify_verbose != 0 )
1154 {
1155 libcnotify_printf(
1156 "%s: B-tree sub node block number: %" PRIu64 "\n",
1157 function,
1158 sub_node_block_number );
1159 }
1160 #endif
1161 node = NULL;
1162
1163 if( libfsapfs_object_map_btree_get_sub_node(
1164 object_map_btree,
1165 file_io_handle,
1166 sub_node_block_number,
1167 &node,
1168 error ) != 1 )
1169 {
1170 libcerror_error_set(
1171 error,
1172 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1173 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1174 "%s: unable to retrieve B-tree sub node from block: %" PRIu64 ".",
1175 function,
1176 sub_node_block_number );
1177
1178 return( -1 );
1179 }
1180 recursion_depth++;
1181 }
1182 while( is_leaf_node == 0 );
1183
1184 return( 0 );
1185 }
1186
1187 /* Retrieves the object map descriptor of a specific object identifier
1188 * Returns 1 if successful, 0 if no such value or -1 on error
1189 */
libfsapfs_object_map_btree_get_descriptor_by_object_identifier(libfsapfs_object_map_btree_t * object_map_btree,libbfio_handle_t * file_io_handle,uint64_t object_identifier,libfsapfs_object_map_descriptor_t ** descriptor,libcerror_error_t ** error)1190 int libfsapfs_object_map_btree_get_descriptor_by_object_identifier(
1191 libfsapfs_object_map_btree_t *object_map_btree,
1192 libbfio_handle_t *file_io_handle,
1193 uint64_t object_identifier,
1194 libfsapfs_object_map_descriptor_t **descriptor,
1195 libcerror_error_t **error )
1196 {
1197 libfsapfs_btree_entry_t *entry = NULL;
1198 libfsapfs_btree_node_t *node = NULL;
1199 static char *function = "libfsapfs_object_map_btree_get_descriptor_by_object_identifier";
1200 int result = 0;
1201
1202 if( object_map_btree == NULL )
1203 {
1204 libcerror_error_set(
1205 error,
1206 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1207 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1208 "%s: invalid object map B-tree.",
1209 function );
1210
1211 return( -1 );
1212 }
1213 if( descriptor == NULL )
1214 {
1215 libcerror_error_set(
1216 error,
1217 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1218 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1219 "%s: invalid descriptor.",
1220 function );
1221
1222 return( -1 );
1223 }
1224 if( *descriptor != NULL )
1225 {
1226 libcerror_error_set(
1227 error,
1228 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1229 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
1230 "%s: invalid descriptor value already set.",
1231 function );
1232
1233 return( -1 );
1234 }
1235 result = libfsapfs_object_map_btree_get_entry_by_identifier(
1236 object_map_btree,
1237 file_io_handle,
1238 object_identifier,
1239 &node,
1240 &entry,
1241 error );
1242
1243 if( result == -1 )
1244 {
1245 libcerror_error_set(
1246 error,
1247 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1248 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1249 "%s: unable to retrieve entry from B-tree.",
1250 function );
1251
1252 goto on_error;
1253 }
1254 else if( result != 0 )
1255 {
1256 if( node == NULL )
1257 {
1258 libcerror_error_set(
1259 error,
1260 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1261 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1262 "%s: invalid B-tree node.",
1263 function );
1264
1265 goto on_error;
1266 }
1267 if( entry == NULL )
1268 {
1269 libcerror_error_set(
1270 error,
1271 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1272 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1273 "%s: invalid B-tree entry.",
1274 function );
1275
1276 goto on_error;
1277 }
1278 if( libfsapfs_object_map_descriptor_initialize(
1279 descriptor,
1280 error ) != 1 )
1281 {
1282 libcerror_error_set(
1283 error,
1284 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1285 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
1286 "%s: unable to create object map descriptor.",
1287 function );
1288
1289 goto on_error;
1290 }
1291 if( libfsapfs_object_map_descriptor_read_key_data(
1292 *descriptor,
1293 entry->key_data,
1294 (size_t) entry->key_data_size,
1295 error ) != 1 )
1296 {
1297 libcerror_error_set(
1298 error,
1299 LIBCERROR_ERROR_DOMAIN_IO,
1300 LIBCERROR_IO_ERROR_READ_FAILED,
1301 "%s: unable to read object map descriptor key data.",
1302 function );
1303
1304 goto on_error;
1305 }
1306 if( libfsapfs_object_map_descriptor_read_value_data(
1307 *descriptor,
1308 entry->value_data,
1309 (size_t) entry->value_data_size,
1310 error ) != 1 )
1311 {
1312 libcerror_error_set(
1313 error,
1314 LIBCERROR_ERROR_DOMAIN_IO,
1315 LIBCERROR_IO_ERROR_READ_FAILED,
1316 "%s: unable to read object map descriptor value data.",
1317 function );
1318
1319 goto on_error;
1320 }
1321 node = NULL;
1322 }
1323 return( result );
1324
1325 on_error:
1326 if( *descriptor != NULL )
1327 {
1328 libfsapfs_object_map_descriptor_free(
1329 descriptor,
1330 NULL );
1331 }
1332 return( -1 );
1333 }
1334
1335