1 /*
2 * B-tree file functions
3 *
4 * Copyright (C) 2009-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 "libfshfs_btree_file.h"
28 #include "libfshfs_btree_header.h"
29 #include "libfshfs_btree_node.h"
30 #include "libfshfs_btree_node_descriptor.h"
31 #include "libfshfs_btree_node_vector.h"
32 #include "libfshfs_debug.h"
33 #include "libfshfs_definitions.h"
34 #include "libfshfs_extent.h"
35 #include "libfshfs_libcdata.h"
36 #include "libfshfs_libcerror.h"
37 #include "libfshfs_libcnotify.h"
38 #include "libfshfs_libfcache.h"
39 #include "libfshfs_libfdata.h"
40
41 #include "fshfs_btree.h"
42
43 /* Creates a B-tree file
44 * Make sure the value btree_file is referencing, is set to NULL
45 * Returns 1 if successful or -1 on error
46 */
libfshfs_btree_file_initialize(libfshfs_btree_file_t ** btree_file,libcerror_error_t ** error)47 int libfshfs_btree_file_initialize(
48 libfshfs_btree_file_t **btree_file,
49 libcerror_error_t **error )
50 {
51 static char *function = "libfshfs_btree_file_initialize";
52
53 if( btree_file == NULL )
54 {
55 libcerror_error_set(
56 error,
57 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
58 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
59 "%s: invalid B-tree file.",
60 function );
61
62 return( -1 );
63 }
64 if( *btree_file != NULL )
65 {
66 libcerror_error_set(
67 error,
68 LIBCERROR_ERROR_DOMAIN_RUNTIME,
69 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
70 "%s: invalid B-tree file value already set.",
71 function );
72
73 return( -1 );
74 }
75 *btree_file = memory_allocate_structure(
76 libfshfs_btree_file_t );
77
78 if( *btree_file == NULL )
79 {
80 libcerror_error_set(
81 error,
82 LIBCERROR_ERROR_DOMAIN_MEMORY,
83 LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
84 "%s: unable to create B-tree file.",
85 function );
86
87 goto on_error;
88 }
89 if( memory_set(
90 *btree_file,
91 0,
92 sizeof( libfshfs_btree_file_t ) ) == NULL )
93 {
94 libcerror_error_set(
95 error,
96 LIBCERROR_ERROR_DOMAIN_MEMORY,
97 LIBCERROR_MEMORY_ERROR_SET_FAILED,
98 "%s: unable to clear B-tree file.",
99 function );
100
101 memory_free(
102 *btree_file );
103
104 *btree_file = NULL;
105
106 return( -1 );
107 }
108 if( libcdata_array_initialize(
109 &( ( *btree_file )->extents ),
110 0,
111 error ) != 1 )
112 {
113 libcerror_error_set(
114 error,
115 LIBCERROR_ERROR_DOMAIN_RUNTIME,
116 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
117 "%s: unable to create extents array.",
118 function );
119
120 goto on_error;
121 }
122 if( libfshfs_btree_header_initialize(
123 &( ( *btree_file )->header ),
124 error ) != 1 )
125 {
126 libcerror_error_set(
127 error,
128 LIBCERROR_ERROR_DOMAIN_RUNTIME,
129 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
130 "%s: unable to create header.",
131 function );
132
133 goto on_error;
134 }
135 return( 1 );
136
137 on_error:
138 if( *btree_file != NULL )
139 {
140 if( ( *btree_file )->extents != NULL )
141 {
142 libcdata_array_free(
143 &( ( *btree_file )->extents ),
144 NULL,
145 NULL );
146 }
147 memory_free(
148 *btree_file );
149
150 *btree_file = NULL;
151 }
152 return( -1 );
153 }
154
155 /* Frees B-tree file
156 * Returns 1 if successful or -1 on error
157 */
libfshfs_btree_file_free(libfshfs_btree_file_t ** btree_file,libcerror_error_t ** error)158 int libfshfs_btree_file_free(
159 libfshfs_btree_file_t **btree_file,
160 libcerror_error_t **error )
161 {
162 static char *function = "libfshfs_btree_file_free";
163 int result = 1;
164
165 if( btree_file == NULL )
166 {
167 libcerror_error_set(
168 error,
169 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
170 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
171 "%s: invalid B-tree file.",
172 function );
173
174 return( -1 );
175 }
176 if( *btree_file != NULL )
177 {
178 if( libcdata_array_free(
179 &( ( *btree_file )->extents ),
180 (int (*)(intptr_t **, libcerror_error_t **)) &libfshfs_extent_free,
181 error ) != 1 )
182 {
183 libcerror_error_set(
184 error,
185 LIBCERROR_ERROR_DOMAIN_RUNTIME,
186 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
187 "%s: unable to free extents array.",
188 function );
189
190 result = -1;
191 }
192 if( libfshfs_btree_header_free(
193 &( ( *btree_file )->header ),
194 error ) != 1 )
195 {
196 libcerror_error_set(
197 error,
198 LIBCERROR_ERROR_DOMAIN_RUNTIME,
199 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
200 "%s: unable to free header.",
201 function );
202
203 result = -1;
204 }
205 if( ( *btree_file )->nodes_vector != NULL )
206 {
207 if( libfshfs_btree_node_vector_free(
208 &( ( *btree_file )->nodes_vector ),
209 error ) != 1 )
210 {
211 libcerror_error_set(
212 error,
213 LIBCERROR_ERROR_DOMAIN_RUNTIME,
214 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
215 "%s: unable to free B-tree nodes vector.",
216 function );
217
218 result = -1;
219 }
220 }
221 if( ( *btree_file )->nodes_cache != NULL )
222 {
223 if( libfcache_cache_free(
224 &( ( *btree_file )->nodes_cache ),
225 error ) != 1 )
226 {
227 libcerror_error_set(
228 error,
229 LIBCERROR_ERROR_DOMAIN_RUNTIME,
230 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
231 "%s: unable to free B-tree nodes cache.",
232 function );
233
234 result = -1;
235 }
236 }
237 memory_free(
238 *btree_file );
239
240 *btree_file = NULL;
241 }
242 return( result );
243 }
244
245 /* Reads the B-tree file
246 * Returns 1 if successful or -1 on error
247 */
libfshfs_btree_file_read_file_io_handle(libfshfs_btree_file_t * btree_file,libfshfs_io_handle_t * io_handle,libbfio_handle_t * file_io_handle,libcerror_error_t ** error)248 int libfshfs_btree_file_read_file_io_handle(
249 libfshfs_btree_file_t *btree_file,
250 libfshfs_io_handle_t *io_handle,
251 libbfio_handle_t *file_io_handle,
252 libcerror_error_t **error )
253 {
254 uint8_t header_node_data[ 512 ];
255
256 libfshfs_btree_node_descriptor_t *header_node_descriptor = NULL;
257 libfshfs_extent_t *extent = NULL;
258 static char *function = "libfshfs_btree_file_read_file_io_handle";
259 ssize_t read_count = 0;
260 off64_t file_offset = 0;
261
262 if( btree_file == NULL )
263 {
264 libcerror_error_set(
265 error,
266 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
267 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
268 "%s: invalid B-tree file.",
269 function );
270
271 return( -1 );
272 }
273 if( btree_file->nodes_vector != NULL )
274 {
275 libcerror_error_set(
276 error,
277 LIBCERROR_ERROR_DOMAIN_RUNTIME,
278 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
279 "%s: invalid B-tree file - nodes vector already set.",
280 function );
281
282 return( -1 );
283 }
284 if( btree_file->nodes_cache != NULL )
285 {
286 libcerror_error_set(
287 error,
288 LIBCERROR_ERROR_DOMAIN_RUNTIME,
289 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
290 "%s: invalid B-tree file - nodes cache already set.",
291 function );
292
293 return( -1 );
294 }
295 if( io_handle == NULL )
296 {
297 libcerror_error_set(
298 error,
299 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
300 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
301 "%s: invalid IO handle.",
302 function );
303
304 return( -1 );
305 }
306 if( io_handle->block_size == 0 )
307 {
308 libcerror_error_set(
309 error,
310 LIBCERROR_ERROR_DOMAIN_RUNTIME,
311 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
312 "%s: invalid IO handle - block size value out of bounds.",
313 function );
314
315 return( -1 );
316 }
317 /* Read the header record first to determine the B-tree node size.
318 */
319 if( libcdata_array_get_entry_by_index(
320 btree_file->extents,
321 0,
322 (intptr_t **) &extent,
323 error ) != 1 )
324 {
325 libcerror_error_set(
326 error,
327 LIBCERROR_ERROR_DOMAIN_RUNTIME,
328 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
329 "%s: unable to retrieve extent: 0.",
330 function );
331
332 goto on_error;
333 }
334 if( extent == NULL )
335 {
336 libcerror_error_set(
337 error,
338 LIBCERROR_ERROR_DOMAIN_RUNTIME,
339 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
340 "%s: missing extent: 0.",
341 function );
342
343 goto on_error;
344 }
345 file_offset = extent->block_number * io_handle->block_size;
346
347 #if defined( HAVE_DEBUG_OUTPUT )
348 if( libcnotify_verbose != 0 )
349 {
350 libcnotify_printf(
351 "%s: reading B-tree header node at offset: %" PRIi64 " (0x%08" PRIx64 ")\n",
352 function,
353 file_offset,
354 file_offset );
355 }
356 #endif
357 read_count = libbfio_handle_read_buffer_at_offset(
358 file_io_handle,
359 header_node_data,
360 512,
361 file_offset,
362 error );
363
364 if( read_count != (ssize_t) 512 )
365 {
366 libcerror_error_set(
367 error,
368 LIBCERROR_ERROR_DOMAIN_IO,
369 LIBCERROR_IO_ERROR_READ_FAILED,
370 "%s: unable to read B-tree header node data at offset: %" PRIi64 " (0x%08" PRIx64 ").",
371 function,
372 file_offset,
373 file_offset );
374
375 goto on_error;
376 }
377 if( libfshfs_btree_node_descriptor_initialize(
378 &header_node_descriptor,
379 error ) != 1 )
380 {
381 libcerror_error_set(
382 error,
383 LIBCERROR_ERROR_DOMAIN_RUNTIME,
384 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
385 "%s: unable to create B-tree header node descriptor.",
386 function );
387
388 goto on_error;
389 }
390 if( libfshfs_btree_node_descriptor_read_data(
391 header_node_descriptor,
392 header_node_data,
393 512,
394 error ) != 1 )
395 {
396 libcerror_error_set(
397 error,
398 LIBCERROR_ERROR_DOMAIN_IO,
399 LIBCERROR_IO_ERROR_READ_FAILED,
400 "%s: unable to read B-tree header node descriptor.",
401 function );
402
403 goto on_error;
404 }
405 if( header_node_descriptor->type != LIBFSHFS_BTREE_NODE_TYPE_HEADER_NODE )
406 {
407 libcerror_error_set(
408 error,
409 LIBCERROR_ERROR_DOMAIN_RUNTIME,
410 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
411 "%s: unuspported B-tree header node type.",
412 function );
413
414 goto on_error;
415 }
416 if( libfshfs_btree_node_descriptor_free(
417 &header_node_descriptor,
418 error ) != 1 )
419 {
420 libcerror_error_set(
421 error,
422 LIBCERROR_ERROR_DOMAIN_RUNTIME,
423 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
424 "%s: unable to free B-tree header node descriptor.",
425 function );
426
427 goto on_error;
428 }
429 if( libfshfs_btree_header_read_data(
430 btree_file->header,
431 &( header_node_data[ sizeof( fshfs_btree_node_descriptor_t ) ] ),
432 512 - sizeof( fshfs_btree_node_descriptor_t ),
433 error ) != 1 )
434 {
435 libcerror_error_set(
436 error,
437 LIBCERROR_ERROR_DOMAIN_IO,
438 LIBCERROR_IO_ERROR_READ_FAILED,
439 "%s: unable to read B-tree header.",
440 function );
441
442 goto on_error;
443 }
444 /* Read the root node using the nodes vector
445 */
446 if( libfshfs_btree_node_vector_initialize(
447 &( btree_file->nodes_vector ),
448 io_handle,
449 btree_file->size,
450 btree_file->header->node_size,
451 btree_file->extents,
452 error ) != 1 )
453 {
454 libcerror_error_set(
455 error,
456 LIBCERROR_ERROR_DOMAIN_RUNTIME,
457 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
458 "%s: unable to create B-tree nodes vector.",
459 function );
460
461 goto on_error;
462 }
463 if( libfcache_cache_initialize(
464 &( btree_file->nodes_cache ),
465 LIBFSHFS_MAXIMUM_CACHE_ENTRIES_BTREE_FILE_BLOCKS,
466 error ) != 1 )
467 {
468 libcerror_error_set(
469 error,
470 LIBCERROR_ERROR_DOMAIN_RUNTIME,
471 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
472 "%s: unable to create B-tree nodes cache.",
473 function );
474
475 goto on_error;
476 }
477 return( 1 );
478
479 on_error:
480 if( btree_file->nodes_cache != NULL )
481 {
482 libfcache_cache_free(
483 &( btree_file->nodes_cache ),
484 NULL );
485 }
486 if( btree_file->nodes_vector != NULL )
487 {
488 libfshfs_btree_node_vector_free(
489 &( btree_file->nodes_vector ),
490 NULL );
491 }
492 if( header_node_descriptor != NULL )
493 {
494 libfshfs_btree_node_descriptor_free(
495 &header_node_descriptor,
496 NULL );
497 }
498 return( -1 );
499 }
500
501 /* Retrieves a specific B-tree node
502 * Returns 1 if successful or -1 on error
503 */
libfshfs_btree_file_get_node_by_number(libfshfs_btree_file_t * btree_file,libbfio_handle_t * file_io_handle,uint32_t node_number,libfshfs_btree_node_t ** node,int recursion_depth,libcerror_error_t ** error)504 int libfshfs_btree_file_get_node_by_number(
505 libfshfs_btree_file_t *btree_file,
506 libbfio_handle_t *file_io_handle,
507 uint32_t node_number,
508 libfshfs_btree_node_t **node,
509 int recursion_depth,
510 libcerror_error_t **error )
511 {
512 static char *function = "libfshfs_btree_file_get_node_by_number";
513
514 if( btree_file == NULL )
515 {
516 libcerror_error_set(
517 error,
518 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
519 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
520 "%s: invalid B-tree file.",
521 function );
522
523 return( -1 );
524 }
525 if( libfshfs_btree_node_vector_get_node_by_number(
526 btree_file->nodes_vector,
527 file_io_handle,
528 btree_file->nodes_cache,
529 node_number,
530 node,
531 recursion_depth,
532 error ) != 1 )
533 {
534 libcerror_error_set(
535 error,
536 LIBCERROR_ERROR_DOMAIN_RUNTIME,
537 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
538 "%s: unable to retrieve B-tree node: %" PRIu32 ".",
539 function,
540 node_number );
541
542 return( -1 );
543 }
544 return( 1 );
545 }
546
547 /* Retrieves the B-tree root node
548 * Returns 1 if successful or -1 on error
549 */
libfshfs_btree_file_get_root_node(libfshfs_btree_file_t * btree_file,libbfio_handle_t * file_io_handle,libfshfs_btree_node_t ** root_node,int recursion_depth,libcerror_error_t ** error)550 int libfshfs_btree_file_get_root_node(
551 libfshfs_btree_file_t *btree_file,
552 libbfio_handle_t *file_io_handle,
553 libfshfs_btree_node_t **root_node,
554 int recursion_depth,
555 libcerror_error_t **error )
556 {
557 static char *function = "libfshfs_btree_file_get_root_node";
558
559 if( btree_file == NULL )
560 {
561 libcerror_error_set(
562 error,
563 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
564 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
565 "%s: invalid B-tree file.",
566 function );
567
568 return( -1 );
569 }
570 if( libfshfs_btree_node_vector_get_node_by_number(
571 btree_file->nodes_vector,
572 file_io_handle,
573 btree_file->nodes_cache,
574 btree_file->header->root_node_number,
575 root_node,
576 recursion_depth,
577 error ) != 1 )
578 {
579 libcerror_error_set(
580 error,
581 LIBCERROR_ERROR_DOMAIN_RUNTIME,
582 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
583 "%s: unable to retrieve B-tree root node: %" PRIu32 ".",
584 function,
585 btree_file->header->root_node_number );
586
587 return( -1 );
588 }
589 return( 1 );
590 }
591
592