/src/libfshfs/libfshfs/libfshfs_btree_node_vector.c

Source
/*
 * The B-tree file node vector functions
 *
 * Copyright (C) 2009-2024, Joachim Metz <joachim.metz@gmail.com>
 *
 * Refer to AUTHORS for acknowledgements.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

#include <common.h>
#include <memory.h>
#include <types.h>

#include "libfshfs_btree_node.h"
#include "libfshfs_btree_node_cache.h"
#include "libfshfs_btree_node_vector.h"
#include "libfshfs_definitions.h"
#include "libfshfs_extent.h"
#include "libfshfs_io_handle.h"
#include "libfshfs_libcdata.h"
#include "libfshfs_libcerror.h"
#include "libfshfs_libcnotify.h"
#include "libfshfs_libfcache.h"
#include "libfshfs_profiler.h"
#include "libfshfs_unused.h"

/* Creates a B-tree node vector
 * Make sure the value node_vector is referencing, is set to NULL
 * Returns 1 if successful or -1 on error
 */
int libfshfs_btree_node_vector_initialize(
     libfshfs_btree_node_vector_t **node_vector,
     libfshfs_io_handle_t *io_handle,
     uint64_t size,
     uint16_t node_size,
     libcdata_array_t *extents,
     libcerror_error_t **error )
{
  static char *function          = "libfshfs_btree_node_vector_initialize";
  uint64_t total_number_of_nodes = 0;

  if( node_vector == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid B-tree node vector.",
     function );

    return( -1 );
  }
  if( *node_vector != NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
     "%s: invalid B-tree node vector value already set.",
     function );

    return( -1 );
  }
  if( io_handle == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid IO handle.",
     function );

    return( -1 );
  }
  if( node_size == 0 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid node size value out of bounds.",
     function );

    return( -1 );
  }
  *node_vector = memory_allocate_structure(
                  libfshfs_btree_node_vector_t );

  if( *node_vector == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
     "%s: unable to create B-tree node vector.",
     function );

    goto on_error;
  }
  if( memory_set(
       *node_vector,
       0,
       sizeof( libfshfs_btree_node_vector_t ) ) == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_SET_FAILED,
     "%s: unable to clear B-tree node vector.",
     function );

    memory_free(
     *node_vector );

    *node_vector = NULL;

    return( -1 );
  }
  if( size > ( ( (uint64_t) UINT64_MAX / node_size ) - 1 ) )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid total number of blocks value out of bounds.",
     function );

    goto on_error;
  }
  total_number_of_nodes = size / node_size;

  if( ( size % node_size ) != 0 )
  {
    total_number_of_nodes += 1;
  }
  if( total_number_of_nodes > (uint64_t) UINT32_MAX )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid number of nodes value out of bounds.",
     function );

    goto on_error;
  }
  if( libfcache_date_time_get_timestamp(
       &( ( *node_vector )->cache_timestamp ),
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to retrieve cache timestamp.",
     function );

    goto on_error;
  }
  ( *node_vector )->number_of_nodes = (uint32_t) total_number_of_nodes;
  ( *node_vector )->io_handle       = io_handle;
  ( *node_vector )->node_size       = node_size;
  ( *node_vector )->extents         = extents;

  return( 1 );

on_error:
  if( *node_vector != NULL )
  {
    memory_free(
     *node_vector );

    *node_vector = NULL;
  }
  return( -1 );
}

/* Frees a B-tree node vector
 * Returns 1 if successful or -1 on error
 */
int libfshfs_btree_node_vector_free(
     libfshfs_btree_node_vector_t **node_vector,
     libcerror_error_t **error )
{
  static char *function = "libfshfs_btree_node_vector_free";
  int result            = 1;

  if( node_vector == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid B-tree node vector.",
     function );

    return( -1 );
  }
  if( *node_vector != NULL )
  {
    /* The extents reference is freed elsewhere
     */
    memory_free(
     *node_vector );

    *node_vector = NULL;
  }
  return( result );
}

/* Retrieves a specific B-tree node
 * Returns 1 if successful or -1 on error
 */
int libfshfs_btree_node_vector_get_node_by_number(
     libfshfs_btree_node_vector_t *node_vector,
     libbfio_handle_t *file_io_handle,
     libfshfs_btree_node_cache_t *node_cache,
     int depth,
     uint32_t node_number,
     libfshfs_btree_node_t **node,
     libcerror_error_t **error )
{
  libfcache_cache_value_t *cache_value = NULL;
  libfshfs_btree_node_t *safe_node     = NULL;
  libfshfs_extent_t *extent            = NULL;
  static char *function                = "libfshfs_btree_node_vector_get_node_by_number";
  size64_t extent_size                 = 0;
  off64_t file_offset                  = 0;
  off64_t node_offset                  = 0;
  int extent_index                     = 0;
  int number_of_extents                = 0;
  int result                           = 0;

#if defined( HAVE_PROFILER )
  int64_t profiler_start_timestamp     = 0;
  const char *cache_hit_or_miss        = NULL;
#endif

  if( node_vector == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid B-tree node vector.",
     function );

    return( -1 );
  }
  if( node_vector->io_handle == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
     "%s: invalid B-tree node vector - missing IO handle.",
     function );

    return( -1 );
  }
  if( node_vector->io_handle->block_size == 0 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid B-tree node vector - invalid IO handle - block size value out of bounds.",
     function );

    return( -1 );
  }
  if( node_vector->node_size == 0 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid B-tree node vector - node size value out of bounds.",
     function );

    return( -1 );
  }
  if( node_number >= node_vector->number_of_nodes )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid block number value out of bounds.",
     function );

    return( -1 );
  }
  if( node_cache == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid B-tree node cache.",
     function );

    return( -1 );
  }
#if defined( HAVE_PROFILER )
  if( node_vector->io_handle->profiler != NULL )
  {
    if( libfshfs_profiler_start_timing(
         node_vector->io_handle->profiler,
         &profiler_start_timestamp,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_SET_FAILED,
       "%s: unable to start timing.",
       function );

      goto on_error;
    }
  }
#endif /* defined( HAVE_PROFILER ) */

/* TODO move this into node_cache */
  result = libfcache_cache_get_value_by_identifier(
            node_cache->caches[ depth ],
            0,
            (off64_t) node_number,
            node_vector->cache_timestamp,
            &cache_value,
            error );

  if( result == -1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to retrieve value from cache.",
     function );

    goto on_error;
  }
  else if( result != 0 )
  {
    if( libfcache_cache_value_get_value(
         cache_value,
         (intptr_t **) node,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_GET_FAILED,
       "%s: unable to retrieve cache value.",
       function );

      goto on_error;
    }
  }
  else
  {
    if( libfshfs_btree_node_initialize(
         &safe_node,
         (size_t) node_vector->node_size,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
       "%s: unable to create B-tree node.",
       function );

      goto on_error;
    }
    if( libcdata_array_get_number_of_entries(
         node_vector->extents,
         &number_of_extents,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_GET_FAILED,
       "%s: unable to retrieve number of extents.",
       function );

      goto on_error;
    }
    if( (off64_t) node_number > ( (off64_t) INT64_MAX / node_vector->node_size ) )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
       "%s: invalid node number value out of bounds.",
       function );

      goto on_error;
    }
    node_offset = (off64_t) node_number * node_vector->node_size;

    for( extent_index = 0;
         extent_index < number_of_extents;
         extent_index++ )
    {
      if( libcdata_array_get_entry_by_index(
           node_vector->extents,
           extent_index,
           (intptr_t **) &extent,
           error ) != 1 )
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_RUNTIME,
         LIBCERROR_RUNTIME_ERROR_GET_FAILED,
         "%s: unable to retrieve extent: %d.",
         function,
         extent_index );

        goto on_error;
      }
      if( extent == NULL )
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_RUNTIME,
         LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
         "%s: missing extent: %d.",
         function,
         extent_index );

        goto on_error;
      }
      extent_size = (size64_t) extent->number_of_blocks * node_vector->io_handle->block_size;

      if( (size64_t) node_offset < extent_size )
      {
        if( (off64_t) extent->block_number > ( ( (off64_t) INT64_MAX - node_offset ) / node_vector->io_handle->block_size ) )
        {
          libcerror_error_set(
           error,
           LIBCERROR_ERROR_DOMAIN_RUNTIME,
           LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
           "%s: invalid extent - block number value out of bounds.",
           function );

          goto on_error;
        }
        file_offset  = ( (off64_t) extent->block_number * node_vector->io_handle->block_size ) + node_offset;
        extent_size -= node_offset;

        break;
      }
      node_offset -= extent_size;
    }
    if( extent_size < node_vector->node_size )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
       "%s: invalid extent size value out of bounds.",
       function );

      goto on_error;
    }
    if( libfshfs_btree_node_read_file_io_handle(
         safe_node,
         file_io_handle,
         file_offset,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_IO,
       LIBCERROR_IO_ERROR_READ_FAILED,
       "%s: unable to read element data at offset: %" PRIi64 " (0x%08" PRIx64 ").",
       function,
       file_offset,
       file_offset );

      goto on_error;
    }
    if( libfcache_cache_set_value_by_identifier(
         node_cache->caches[ depth ],
         0,
         (off64_t) node_number,
         node_vector->cache_timestamp,
         (intptr_t *) safe_node,
         (int (*)(intptr_t **, libcerror_error_t **)) &libfshfs_btree_node_free,
         LIBFCACHE_CACHE_VALUE_FLAG_MANAGED,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_SET_FAILED,
       "%s: unable to set value in cache.",
       function );

      goto on_error;
    }
    *node     = safe_node;
    safe_node = NULL;
  }
#if defined( HAVE_PROFILER )
  if( node_vector->io_handle->profiler != NULL )
  {
    node_offset = (off64_t) node_number * node_vector->node_size;

    if( result == 0 )
    {
      cache_hit_or_miss = "miss";
    }
    else
    {
      cache_hit_or_miss = "hit";
    }
    if( libfshfs_profiler_stop_timing(
         node_vector->io_handle->profiler,
         profiler_start_timestamp,
         function,
         node_offset,
         node_vector->node_size,
         cache_hit_or_miss,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_SET_FAILED,
       "%s: unable to stop timing.",
       function );

      goto on_error;
    }
  }
#endif /* defined( HAVE_PROFILER ) */

  return( 1 );

on_error:
  if( safe_node != NULL )
  {
    libfshfs_btree_node_free(
     &safe_node,
     NULL );
  }
  return( -1 );
}


Coverage Report

Created: 2025-10-14 07:00

Line	Count	Source
1		/*
2		* The B-tree file node vector functions
3		*
4		* Copyright (C) 2009-2024, 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 <memory.h>
24		#include <types.h>
25
26		#include "libfshfs_btree_node.h"
27		#include "libfshfs_btree_node_cache.h"
28		#include "libfshfs_btree_node_vector.h"
29		#include "libfshfs_definitions.h"
30		#include "libfshfs_extent.h"
31		#include "libfshfs_io_handle.h"
32		#include "libfshfs_libcdata.h"
33		#include "libfshfs_libcerror.h"
34		#include "libfshfs_libcnotify.h"
35		#include "libfshfs_libfcache.h"
36		#include "libfshfs_profiler.h"
37		#include "libfshfs_unused.h"
38
39		/* Creates a B-tree node vector
40		* Make sure the value node_vector is referencing, is set to NULL
41		* Returns 1 if successful or -1 on error
42		*/
43		int libfshfs_btree_node_vector_initialize(
44		libfshfs_btree_node_vector_t **node_vector,
45		libfshfs_io_handle_t *io_handle,
46		uint64_t size,
47		uint16_t node_size,
48		libcdata_array_t *extents,
49		libcerror_error_t **error )
50	11.2k	{
51	11.2k	static char *function = "libfshfs_btree_node_vector_initialize";
52	11.2k	uint64_t total_number_of_nodes = 0;
53
54	11.2k	if( node_vector == NULL )
55	0	{
56	0	libcerror_error_set(
57	0	error,
58	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
59	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
60	0	"%s: invalid B-tree node vector.",
61	0	function );
62
63	0	return( -1 );
64	0	}
65	11.2k	if( *node_vector != NULL )
66	0	{
67	0	libcerror_error_set(
68	0	error,
69	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
70	0	LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
71	0	"%s: invalid B-tree node vector value already set.",
72	0	function );
73
74	0	return( -1 );
75	0	}
76	11.2k	if( io_handle == NULL )
77	0	{
78	0	libcerror_error_set(
79	0	error,
80	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
81	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
82	0	"%s: invalid IO handle.",
83	0	function );
84
85	0	return( -1 );
86	0	}
87	11.2k	if( node_size == 0 )
88	3	{
89	3	libcerror_error_set(
90	3	error,
91	3	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
92	3	LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
93	3	"%s: invalid node size value out of bounds.",
94	3	function );
95
96	3	return( -1 );
97	3	}
98	11.2k	*node_vector = memory_allocate_structure(
99	11.2k	libfshfs_btree_node_vector_t );
100
101	11.2k	if( *node_vector == NULL )
102	0	{
103	0	libcerror_error_set(
104	0	error,
105	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
106	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
107	0	"%s: unable to create B-tree node vector.",
108	0	function );
109
110	0	goto on_error;
111	0	}
112	11.2k	if( memory_set(
113	11.2k	*node_vector,
114	11.2k	0,
115	11.2k	sizeof( libfshfs_btree_node_vector_t ) ) == NULL )
116	0	{
117	0	libcerror_error_set(
118	0	error,
119	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
120	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
121	0	"%s: unable to clear B-tree node vector.",
122	0	function );
123
124	0	memory_free(
125	0	*node_vector );
126
127	0	*node_vector = NULL;
128
129	0	return( -1 );
130	0	}
131	11.2k	if( size > ( ( (uint64_t) UINT64_MAX / node_size ) - 1 ) )
132	48	{
133	48	libcerror_error_set(
134	48	error,
135	48	LIBCERROR_ERROR_DOMAIN_RUNTIME,
136	48	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
137	48	"%s: invalid total number of blocks value out of bounds.",
138	48	function );
139
140	48	goto on_error;
141	48	}
142	11.1k	total_number_of_nodes = size / node_size;
143
144	11.1k	if( ( size % node_size ) != 0 )
145	7.24k	{
146	7.24k	total_number_of_nodes += 1;
147	7.24k	}
148	11.1k	if( total_number_of_nodes > (uint64_t) UINT32_MAX )
149	173	{
150	173	libcerror_error_set(
151	173	error,
152	173	LIBCERROR_ERROR_DOMAIN_RUNTIME,
153	173	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
154	173	"%s: invalid number of nodes value out of bounds.",
155	173	function );
156
157	173	goto on_error;
158	173	}
159	11.0k	if( libfcache_date_time_get_timestamp(
160	11.0k	&( ( *node_vector )->cache_timestamp ),
161	11.0k	error ) != 1 )
162	0	{
163	0	libcerror_error_set(
164	0	error,
165	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
166	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
167	0	"%s: unable to retrieve cache timestamp.",
168	0	function );
169
170	0	goto on_error;
171	0	}
172	11.0k	( *node_vector )->number_of_nodes = (uint32_t) total_number_of_nodes;
173	11.0k	( *node_vector )->io_handle = io_handle;
174	11.0k	( *node_vector )->node_size = node_size;
175	11.0k	( *node_vector )->extents = extents;
176
177	11.0k	return( 1 );
178
179	221	on_error:
180	221	if( *node_vector != NULL )
181	221	{
182	221	memory_free(
183	221	*node_vector );
184
185	221	*node_vector = NULL;
186	221	}
187	221	return( -1 );
188	11.0k	}
189
190		/* Frees a B-tree node vector
191		* Returns 1 if successful or -1 on error
192		*/
193		int libfshfs_btree_node_vector_free(
194		libfshfs_btree_node_vector_t **node_vector,
195		libcerror_error_t **error )
196	11.0k	{
197	11.0k	static char *function = "libfshfs_btree_node_vector_free";
198	11.0k	int result = 1;
199
200	11.0k	if( node_vector == NULL )
201	0	{
202	0	libcerror_error_set(
203	0	error,
204	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
205	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
206	0	"%s: invalid B-tree node vector.",
207	0	function );
208
209	0	return( -1 );
210	0	}
211	11.0k	if( *node_vector != NULL )
212	11.0k	{
213		/* The extents reference is freed elsewhere
214		*/
215	11.0k	memory_free(
216	11.0k	*node_vector );
217
218	11.0k	*node_vector = NULL;
219	11.0k	}
220	11.0k	return( result );
221	11.0k	}
222
223		/* Retrieves a specific B-tree node
224		* Returns 1 if successful or -1 on error
225		*/
226		int libfshfs_btree_node_vector_get_node_by_number(
227		libfshfs_btree_node_vector_t *node_vector,
228		libbfio_handle_t *file_io_handle,
229		libfshfs_btree_node_cache_t *node_cache,
230		int depth,
231		uint32_t node_number,
232		libfshfs_btree_node_t **node,
233		libcerror_error_t **error )
234	71.6k	{
235	71.6k	libfcache_cache_value_t *cache_value = NULL;
236	71.6k	libfshfs_btree_node_t *safe_node = NULL;
237	71.6k	libfshfs_extent_t *extent = NULL;
238	71.6k	static char *function = "libfshfs_btree_node_vector_get_node_by_number";
239	71.6k	size64_t extent_size = 0;
240	71.6k	off64_t file_offset = 0;
241	71.6k	off64_t node_offset = 0;
242	71.6k	int extent_index = 0;
243	71.6k	int number_of_extents = 0;
244	71.6k	int result = 0;
245
246		#if defined( HAVE_PROFILER )
247		int64_t profiler_start_timestamp = 0;
248		const char *cache_hit_or_miss = NULL;
249		#endif
250
251	71.6k	if( node_vector == NULL )
252	0	{
253	0	libcerror_error_set(
254	0	error,
255	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
256	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
257	0	"%s: invalid B-tree node vector.",
258	0	function );
259
260	0	return( -1 );
261	0	}
262	71.6k	if( node_vector->io_handle == NULL )
263	0	{
264	0	libcerror_error_set(
265	0	error,
266	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
267	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
268	0	"%s: invalid B-tree node vector - missing IO handle.",
269	0	function );
270
271	0	return( -1 );
272	0	}
273	71.6k	if( node_vector->io_handle->block_size == 0 )
274	0	{
275	0	libcerror_error_set(
276	0	error,
277	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
278	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
279	0	"%s: invalid B-tree node vector - invalid IO handle - block size value out of bounds.",
280	0	function );
281
282	0	return( -1 );
283	0	}
284	71.6k	if( node_vector->node_size == 0 )
285	0	{
286	0	libcerror_error_set(
287	0	error,
288	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
289	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
290	0	"%s: invalid B-tree node vector - node size value out of bounds.",
291	0	function );
292
293	0	return( -1 );
294	0	}
295	71.6k	if( node_number >= node_vector->number_of_nodes )
296	104	{
297	104	libcerror_error_set(
298	104	error,
299	104	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
300	104	LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
301	104	"%s: invalid block number value out of bounds.",
302	104	function );
303
304	104	return( -1 );
305	104	}
306	71.5k	if( node_cache == NULL )
307	0	{
308	0	libcerror_error_set(
309	0	error,
310	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
311	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
312	0	"%s: invalid B-tree node cache.",
313	0	function );
314
315	0	return( -1 );
316	0	}
317		#if defined( HAVE_PROFILER )
318		if( node_vector->io_handle->profiler != NULL )
319		{
320		if( libfshfs_profiler_start_timing(
321		node_vector->io_handle->profiler,
322		&profiler_start_timestamp,
323		error ) != 1 )
324		{
325		libcerror_error_set(
326		error,
327		LIBCERROR_ERROR_DOMAIN_RUNTIME,
328		LIBCERROR_RUNTIME_ERROR_SET_FAILED,
329		"%s: unable to start timing.",
330		function );
331
332		goto on_error;
333		}
334		}
335		#endif /* defined( HAVE_PROFILER ) */
336
337		/* TODO move this into node_cache */
338	71.5k	result = libfcache_cache_get_value_by_identifier(
339	71.5k	node_cache->caches[ depth ],
340	71.5k	0,
341	71.5k	(off64_t) node_number,
342	71.5k	node_vector->cache_timestamp,
343	71.5k	&cache_value,
344	71.5k	error );
345
346	71.5k	if( result == -1 )
347	0	{
348	0	libcerror_error_set(
349	0	error,
350	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
351	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
352	0	"%s: unable to retrieve value from cache.",
353	0	function );
354
355	0	goto on_error;
356	0	}
357	71.5k	else if( result != 0 )
358	45.6k	{
359	45.6k	if( libfcache_cache_value_get_value(
360	45.6k	cache_value,
361	45.6k	(intptr_t **) node,
362	45.6k	error ) != 1 )
363	0	{
364	0	libcerror_error_set(
365	0	error,
366	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
367	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
368	0	"%s: unable to retrieve cache value.",
369	0	function );
370
371	0	goto on_error;
372	0	}
373	45.6k	}
374	25.9k	else
375	25.9k	{
376	25.9k	if( libfshfs_btree_node_initialize(
377	25.9k	&safe_node,
378	25.9k	(size_t) node_vector->node_size,
379	25.9k	error ) != 1 )
380	0	{
381	0	libcerror_error_set(
382	0	error,
383	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
384	0	LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
385	0	"%s: unable to create B-tree node.",
386	0	function );
387
388	0	goto on_error;
389	0	}
390	25.9k	if( libcdata_array_get_number_of_entries(
391	25.9k	node_vector->extents,
392	25.9k	&number_of_extents,
393	25.9k	error ) != 1 )
394	0	{
395	0	libcerror_error_set(
396	0	error,
397	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
398	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
399	0	"%s: unable to retrieve number of extents.",
400	0	function );
401
402	0	goto on_error;
403	0	}
404	25.9k	if( (off64_t) node_number > ( (off64_t) INT64_MAX / node_vector->node_size ) )
405	0	{
406	0	libcerror_error_set(
407	0	error,
408	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
409	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
410	0	"%s: invalid node number value out of bounds.",
411	0	function );
412
413	0	goto on_error;
414	0	}
415	25.9k	node_offset = (off64_t) node_number * node_vector->node_size;
416
417	25.9k	for( extent_index = 0;
418	58.9k	extent_index < number_of_extents;
419	32.9k	extent_index++ )
420	48.2k	{
421	48.2k	if( libcdata_array_get_entry_by_index(
422	48.2k	node_vector->extents,
423	48.2k	extent_index,
424	48.2k	(intptr_t **) &extent,
425	48.2k	error ) != 1 )
426	0	{
427	0	libcerror_error_set(
428	0	error,
429	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
430	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
431	0	"%s: unable to retrieve extent: %d.",
432	0	function,
433	0	extent_index );
434
435	0	goto on_error;
436	0	}
437	48.2k	if( extent == NULL )
438	0	{
439	0	libcerror_error_set(
440	0	error,
441	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
442	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
443	0	"%s: missing extent: %d.",
444	0	function,
445	0	extent_index );
446
447	0	goto on_error;
448	0	}
449	48.2k	extent_size = (size64_t) extent->number_of_blocks * node_vector->io_handle->block_size;
450
451	48.2k	if( (size64_t) node_offset < extent_size )
452	15.2k	{
453	15.2k	if( (off64_t) extent->block_number > ( ( (off64_t) INT64_MAX - node_offset ) / node_vector->io_handle->block_size ) )
454	19	{
455	19	libcerror_error_set(
456	19	error,
457	19	LIBCERROR_ERROR_DOMAIN_RUNTIME,
458	19	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
459	19	"%s: invalid extent - block number value out of bounds.",
460	19	function );
461
462	19	goto on_error;
463	19	}
464	15.2k	file_offset = ( (off64_t) extent->block_number * node_vector->io_handle->block_size ) + node_offset;
465	15.2k	extent_size -= node_offset;
466
467	15.2k	break;
468	15.2k	}
469	32.9k	node_offset -= extent_size;
470	32.9k	}
471	25.9k	if( extent_size < node_vector->node_size )
472	45	{
473	45	libcerror_error_set(
474	45	error,
475	45	LIBCERROR_ERROR_DOMAIN_RUNTIME,
476	45	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
477	45	"%s: invalid extent size value out of bounds.",
478	45	function );
479
480	45	goto on_error;
481	45	}
482	25.8k	if( libfshfs_btree_node_read_file_io_handle(
483	25.8k	safe_node,
484	25.8k	file_io_handle,
485	25.8k	file_offset,
486	25.8k	error ) != 1 )
487	1.06k	{
488	1.06k	libcerror_error_set(
489	1.06k	error,
490	1.06k	LIBCERROR_ERROR_DOMAIN_IO,
491	1.06k	LIBCERROR_IO_ERROR_READ_FAILED,
492	1.06k	"%s: unable to read element data at offset: %" PRIi64 " (0x%08" PRIx64 ").",
493	1.06k	function,
494	1.06k	file_offset,
495	1.06k	file_offset );
496
497	1.06k	goto on_error;
498	1.06k	}
499	24.7k	if( libfcache_cache_set_value_by_identifier(
500	24.7k	node_cache->caches[ depth ],
501	24.7k	0,
502	24.7k	(off64_t) node_number,
503	24.7k	node_vector->cache_timestamp,
504	24.7k	(intptr_t *) safe_node,
505	24.7k	(int ()(intptr_t , libcerror_error_t *)) &libfshfs_btree_node_free,
506	24.7k	LIBFCACHE_CACHE_VALUE_FLAG_MANAGED,
507	24.7k	error ) != 1 )
508	0	{
509	0	libcerror_error_set(
510	0	error,
511	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
512	0	LIBCERROR_RUNTIME_ERROR_SET_FAILED,
513	0	"%s: unable to set value in cache.",
514	0	function );
515
516	0	goto on_error;
517	0	}
518	24.7k	*node = safe_node;
519	24.7k	safe_node = NULL;
520	24.7k	}
521		#if defined( HAVE_PROFILER )
522		if( node_vector->io_handle->profiler != NULL )
523		{
524		node_offset = (off64_t) node_number * node_vector->node_size;
525
526		if( result == 0 )
527		{
528		cache_hit_or_miss = "miss";
529		}
530		else
531		{
532		cache_hit_or_miss = "hit";
533		}
534		if( libfshfs_profiler_stop_timing(
535		node_vector->io_handle->profiler,
536		profiler_start_timestamp,
537		function,
538		node_offset,
539		node_vector->node_size,
540		cache_hit_or_miss,
541		error ) != 1 )
542		{
543		libcerror_error_set(
544		error,
545		LIBCERROR_ERROR_DOMAIN_RUNTIME,
546		LIBCERROR_RUNTIME_ERROR_SET_FAILED,
547		"%s: unable to stop timing.",
548		function );
549
550		goto on_error;
551		}
552		}
553		#endif /* defined( HAVE_PROFILER ) */
554
555	70.4k	return( 1 );
556
557	1.13k	on_error:
558	1.13k	if( safe_node != NULL )
559	1.13k	{
560	1.13k	libfshfs_btree_node_free(
561	1.13k	&safe_node,
562		NULL );
563	1.13k	}
564	1.13k	return( -1 );
565	71.5k	}
566