/src/libesedb/libesedb/libesedb_space_tree.c

Source
/*
 * Space tree 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 "libesedb_debug.h"
#include "libesedb_definitions.h"
#include "libesedb_libbfio.h"
#include "libesedb_libcerror.h"
#include "libesedb_libcnotify.h"
#include "libesedb_libfcache.h"
#include "libesedb_libfdata.h"
#include "libesedb_page.h"
#include "libesedb_page_value.h"
#include "libesedb_page_tree.h"
#include "libesedb_page_tree_value.h"
#include "libesedb_space_tree.h"
#include "libesedb_space_tree_value.h"

/* Creates a space tree
 * Make sure the value space_tree is referencing, is set to NULL
 * Returns 1 if successful or -1 on error
 */
int libesedb_space_tree_initialize(
     libesedb_space_tree_t **space_tree,
     libesedb_io_handle_t *io_handle,
     uint32_t object_identifier,
     uint32_t root_page_number,
     libfdata_vector_t *pages_vector,
     libfcache_cache_t *pages_cache,
     libcerror_error_t **error )
{
  static char *function = "libesedb_space_tree_initialize";

  if( space_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid space tree.",
     function );

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

    return( -1 );
  }
  *space_tree = memory_allocate_structure(
                 libesedb_space_tree_t );

  if( *space_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
     "%s: unable to create space tree.",
     function );

    goto on_error;
  }
  if( memory_set(
       ( *space_tree ),
       0,
       sizeof( libesedb_space_tree_t ) ) == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_SET_FAILED,
     "%s: unable to clear space tree.",
     function );

    memory_free(
     *space_tree );

    *space_tree = NULL;

    return( -1 );
  }
  if( libesedb_page_tree_initialize(
       &( ( *space_tree )->page_tree ),
       io_handle,
       pages_vector,
       pages_cache,
       object_identifier,
       root_page_number,
       NULL,
       NULL,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
     "%s: unable to create page tree.",
     function );

    goto on_error;
  }
  return( 1 );

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

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

/* Frees a space_tree
 * Returns 1 if successful or -1 on error
 */
int libesedb_space_tree_free(
     libesedb_space_tree_t **space_tree,
     libcerror_error_t **error )
{
  static char *function = "libesedb_space_tree_free";
  int result            = 1;

  if( space_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid space tree.",
     function );

    return( -1 );
  }
  if( *space_tree != NULL )
  {
    if( libesedb_page_tree_free(
         &( ( *space_tree )->page_tree ),
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
       "%s: unable to free page tree.",
       function );

      result = -1;
    }
    memory_free(
     *space_tree );

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

/* Reads the space_tree values from a page
 * Returns 1 if successful or -1 on error
 */
int libesedb_space_tree_read_values_from_page(
     libesedb_space_tree_t *space_tree,
     libbfio_handle_t *file_io_handle,
     libesedb_page_t *page,
     int *current_leaf_value_index,
     int recursion_depth,
     libcerror_error_t **error )
{
  libesedb_page_t *child_page                   = NULL;
  libesedb_page_tree_value_t *page_tree_value   = NULL;
  libesedb_page_value_t *page_value             = NULL;
  libesedb_space_tree_value_t *space_tree_value = NULL;
  libfcache_cache_t *child_page_cache           = NULL;
  static char *function                         = "libesedb_space_tree_read_values_from_page";
  uint32_t child_page_number                    = 0;
  uint32_t page_flags                           = 0;
  uint32_t total_number_of_pages                = 0;
  uint16_t number_of_page_values                = 0;
  uint16_t page_value_index                     = 0;

#if defined( HAVE_DEBUG_OUTPUT )
  uint32_t father_data_page_object_identifier   = 0;
#endif

  if( space_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid space tree.",
     function );

    return( -1 );
  }
  if( space_tree->page_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
     "%s: invalid space tree - missing page tree.",
     function );

    return( -1 );
  }
  if( space_tree->page_tree->io_handle == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
     "%s: invalid space tree - invalid page tree - missing IO handle.",
     function );

    return( -1 );
  }
  if( current_leaf_value_index == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid current leaf value index.",
     function );

    return( -1 );
  }
  if( ( recursion_depth < 0 )
   || ( recursion_depth > LIBESEDB_MAXIMUM_INDEX_NODE_RECURSION_DEPTH ) )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid recursion depth value out of bounds.",
     function );

    return( -1 );
  }
#if defined( HAVE_DEBUG_OUTPUT )
  if( libcnotify_verbose != 0 )
  {
    if( libesedb_page_get_father_data_page_object_identifier(
         page,
         &father_data_page_object_identifier,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_GET_FAILED,
       "%s: unable to retrieve father data page object identifier.",
       function );

      goto on_error;
    }
    if( space_tree->page_tree->object_identifier != father_data_page_object_identifier )
    {
      libcnotify_printf(
       "%s: mismatch in father data page object identifier (tree: %" PRIu32 " != page: %" PRIu32 ").\n",
       function,
       space_tree->page_tree->object_identifier,
       father_data_page_object_identifier );
    }
  }
#endif /* defined( HAVE_DEBUG_OUTPUT ) */

  if( libesedb_page_get_number_of_values(
       page,
       &number_of_page_values,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to retrieve number of page values.",
     function );

    goto on_error;
  }
  if( number_of_page_values == 0 )
  {
    return( 1 );
  }
  if( libesedb_page_get_flags(
       page,
       &page_flags,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to retrieve page flags.",
     function );

    goto on_error;
  }
  if( libesedb_page_get_value_by_index(
       page,
       0,
       &page_value,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to retrieve page value: 0.",
     function );

    goto on_error;
  }
  if( page_value == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
     "%s: invalid page value.",
     function );

    goto on_error;
  }
#if defined( HAVE_DEBUG_OUTPUT )
  if( libcnotify_verbose != 0 )
  {
    libcnotify_printf(
     "%s: page value: 000 page tag flags\t: 0x%02" PRIx8 "",
     function,
     page_value->flags );
    libesedb_debug_print_page_tag_flags(
     page_value->flags );
    libcnotify_printf(
     "\n" );

    libcnotify_printf(
     "%s: page value: 000 data:\n",
     function );
    libcnotify_print_data(
     page_value->data,
     (size_t) page_value->size,
     LIBCNOTIFY_PRINT_DATA_FLAG_GROUP_DATA );
  }
#endif /* defined( HAVE_DEBUG_OUTPUT ) */

        /* Use a local cache to prevent cache invalidation of the page
         * when reading child pages.
         */
  if( libfcache_cache_initialize(
       &child_page_cache,
       1,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
     "%s: unable to create child page cache.",
     function );

    goto on_error;
  }
  for( page_value_index = 1;
       page_value_index < number_of_page_values;
       page_value_index++ )
  {
    if( libesedb_page_get_value_by_index(
         page,
         page_value_index,
         &page_value,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_GET_FAILED,
       "%s: unable to retrieve page value: %" PRIu16 ".",
       function,
       page_value_index );

      goto on_error;
    }
    if( page_value == NULL )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
       "%s: missing page value: %" PRIu16 ".",
       function,
       page_value_index );

      goto on_error;
    }
#if defined( HAVE_DEBUG_OUTPUT )
    if( libcnotify_verbose != 0 )
    {
      libcnotify_printf(
       "%s: page value: %03" PRIu16 " page tag flags\t: 0x%02" PRIx8 "",
       function,
       page_value_index,
       page_value->flags );
      libesedb_debug_print_page_tag_flags(
       page_value->flags );
      libcnotify_printf(
       "\n" );

      libcnotify_printf(
       "\n" );
    }
#endif
    if( ( page_value->flags & LIBESEDB_PAGE_TAG_FLAG_IS_DEFUNCT ) != 0 )
    {
      continue;
    }
    if( libesedb_page_tree_value_initialize(
         &page_tree_value,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
       "%s: unable to create page tree value.",
       function );

      goto on_error;
    }
    if( libesedb_page_tree_value_read_data(
         page_tree_value,
         page_value->data,
         (size_t) page_value->size,
         page_value->flags,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_IO,
       LIBCERROR_IO_ERROR_READ_FAILED,
       "%s: unable to read page tree value: %" PRIu16 ".",
       function,
       page_value_index );

      goto on_error;
    }
    if( ( page_flags & LIBESEDB_PAGE_FLAG_IS_LEAF ) != 0 )
    {
      if( libesedb_space_tree_value_initialize(
           &space_tree_value,
           error ) != 1 )
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_RUNTIME,
         LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
         "%s: unable to create space tree value.",
         function );

        goto on_error;
      }
      if( libesedb_space_tree_value_read_data(
           space_tree_value,
           page_tree_value->data,
           (size_t) page_tree_value->data_size,
           error ) != 1 )
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_IO,
         LIBCERROR_IO_ERROR_READ_FAILED,
         "%s: unable to read space tree value: %" PRIu16 ".",
         function,
         page_value_index );

        goto on_error;
      }
      total_number_of_pages += space_tree_value->number_of_pages;

      if( libesedb_space_tree_value_free(
           &space_tree_value,
           error ) != 1 )
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_RUNTIME,
         LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
         "%s: unable to free space tree value.",
         function );

        goto on_error;
      }
    }
    else
    {
      if( page_tree_value->data_size < 4 )
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_RUNTIME,
         LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
         "%s: invalid page tree value: %" PRIu16 " data size value out of bounds.",
         function,
         page_value_index );

        goto on_error;
      }
      byte_stream_copy_to_uint32_little_endian(
       page_tree_value->data,
       child_page_number );

#if defined( HAVE_DEBUG_OUTPUT )
      if( libcnotify_verbose != 0 )
      {
        libcnotify_printf(
         "%s: page value: %03" PRIu16 " child page number\t\t: %" PRIu32 "",
         function,
         page_value_index,
         child_page_number );

        if( child_page_number == 0 )
        {
          libcnotify_printf(
           " (invalid page number)\n" );
        }
        else if( child_page_number > space_tree->page_tree->io_handle->last_page_number )
        {
          libcnotify_printf(
           " (exceeds last page number: %" PRIu32 ")\n",
           space_tree->page_tree->io_handle->last_page_number );
        }
        libcnotify_printf(
         "\n" );
        libcnotify_printf(
         "\n" );
      }
#endif
#if ( SIZEOF_INT <= 4 )
      if( ( child_page_number < 1 )
       || ( child_page_number > (uint32_t) INT_MAX ) )
#else
      if( ( child_page_number < 1 )
       || ( (int) child_page_number > INT_MAX ) )
#endif
      {
        libcerror_error_set(
         error,
         LIBCERROR_ERROR_DOMAIN_RUNTIME,
         LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
         "%s: invalid child page number value out of bounds.",
         function );

        goto on_error;
      }
#if defined( HAVE_DEBUG_OUTPUT )
      if( libcnotify_verbose != 0 )
      {
        if( page_tree_value->data_size > 4 )
        {
          libcnotify_printf(
           "%s: page value: %03" PRIu16 " trailing data:\n",
           function,
           page_value_index );
          libcnotify_print_data(
           &( page_tree_value->data[ 4 ] ),
           page_tree_value->data_size - 4,
           LIBCNOTIFY_PRINT_DATA_FLAG_GROUP_DATA );
        }
      }
#endif
      if( ( child_page_number > 0 )
       && ( child_page_number <= space_tree->page_tree->io_handle->last_page_number ) )
      {
        if( libfdata_vector_get_element_value_by_index(
             space_tree->page_tree->pages_vector,
             (intptr_t *) file_io_handle,
             (libfdata_cache_t *) child_page_cache,
             (int) child_page_number - 1,
             (intptr_t **) &child_page,
             0,
             error ) != 1 )
        {
          libcerror_error_set(
           error,
           LIBCERROR_ERROR_DOMAIN_RUNTIME,
           LIBCERROR_RUNTIME_ERROR_GET_FAILED,
           "%s: unable to retrieve page: %" PRIu32 ".",
           function,
           child_page_number );

          goto on_error;
        }
        if( libesedb_page_validate_space_tree_page(
             child_page,
             error ) != 1 )
        {
          libcerror_error_set(
           error,
           LIBCERROR_ERROR_DOMAIN_RUNTIME,
           LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
           "%s: unsupported page.",
           function );

          goto on_error;
        }
        if( libesedb_space_tree_read_values_from_page(
             space_tree,
             file_io_handle,
             child_page,
             current_leaf_value_index,
             recursion_depth + 1,
             error ) != 1 )
        {
          libcerror_error_set(
           error,
           LIBCERROR_ERROR_DOMAIN_RUNTIME,
           LIBCERROR_RUNTIME_ERROR_GET_FAILED,
           "%s: unable to read values from page: %" PRIu32 ".",
           function,
           child_page_number );

          goto on_error;
        }
      }
    }
    if( libesedb_page_tree_value_free(
         &page_tree_value,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
       "%s: unable to free page tree value.",
       function );

      goto on_error;
    }
  }
  if( libfcache_cache_free(
       &child_page_cache,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
     "%s: unable to free child page cache.",
     function );

    goto on_error;
  }
#if defined( HAVE_DEBUG_OUTPUT )
  if( libcnotify_verbose != 0 )
  {
    libcnotify_printf(
     "%s: total number of pages\t\t: %" PRIu32 "\n",
     function,
     total_number_of_pages );

    libcnotify_printf(
     "\n" );
  }
#endif
  return( 1 );

on_error:
  if( page_tree_value != NULL )
  {
    libesedb_page_tree_value_free(
     &page_tree_value,
     NULL );
  }
  if( space_tree_value != NULL )
  {
    libesedb_space_tree_value_free(
     &space_tree_value,
     NULL );
  }
  if( child_page_cache != NULL )
  {
    libfcache_cache_free(
     &child_page_cache,
     NULL );
  }
  return( -1 );
}

/* Reads the space tree
 * Returns 1 if successful or -1 on error
 */
int libesedb_space_tree_read_file_io_handle(
     libesedb_space_tree_t *space_tree,
     libbfio_handle_t *file_io_handle,
     libcerror_error_t **error )
{
  libesedb_page_t *root_page         = NULL;
  libfcache_cache_t *root_page_cache = NULL;
  static char *function              = "libesedb_space_tree_read_file_io_handle";
  int current_leaf_value_index       = 0;

  if( space_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid space tree.",
     function );

    return( -1 );
  }
  if( space_tree->page_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
     "%s: invalid space tree - missing page tree.",
     function );

    return( -1 );
  }
        /* Use a local cache to prevent cache invalidation of the root page
         * when reading child pages.
         */
  if( libfcache_cache_initialize(
       &root_page_cache,
       1,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
     "%s: unable to create root page cache.",
     function );

    goto on_error;
  }
  if( libfdata_vector_get_element_value_by_index(
       space_tree->page_tree->pages_vector,
       (intptr_t *) file_io_handle,
       (libfdata_cache_t *) root_page_cache,
       (int) space_tree->page_tree->root_page_number - 1,
       (intptr_t **) &root_page,
       0,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to retrieve page: %" PRIu32 ".",
     function,
     space_tree->page_tree->root_page_number );

    goto on_error;
  }
  if( libesedb_page_validate_root_page(
       root_page,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
     "%s: unsupported root page.",
     function );

    goto on_error;
  }
#if defined( HAVE_DEBUG_OUTPUT )
  if( libesedb_page_tree_read_root_page_header(
       space_tree->page_tree,
       root_page,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_IO,
     LIBCERROR_IO_ERROR_READ_FAILED,
     "%s: unable to read root page header.",
     function );

    goto on_error;
  }
#endif
  if( libesedb_space_tree_read_values_from_page(
       space_tree,
       file_io_handle,
       root_page,
       &current_leaf_value_index,
       0,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_GET_FAILED,
     "%s: unable to read values from root page.",
     function );

    goto on_error;
  }
  if( libfcache_cache_free(
       &root_page_cache,
       error ) != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
     "%s: unable to free root page cache.",
     function );

    goto on_error;
  }
  return( 1 );

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


Coverage Report

Created: 2025-10-14 07:00

Line	Count	Source
1		/*
2		* Space tree 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 "libesedb_debug.h"
27		#include "libesedb_definitions.h"
28		#include "libesedb_libbfio.h"
29		#include "libesedb_libcerror.h"
30		#include "libesedb_libcnotify.h"
31		#include "libesedb_libfcache.h"
32		#include "libesedb_libfdata.h"
33		#include "libesedb_page.h"
34		#include "libesedb_page_value.h"
35		#include "libesedb_page_tree.h"
36		#include "libesedb_page_tree_value.h"
37		#include "libesedb_space_tree.h"
38		#include "libesedb_space_tree_value.h"
39
40		/* Creates a space tree
41		* Make sure the value space_tree is referencing, is set to NULL
42		* Returns 1 if successful or -1 on error
43		*/
44		int libesedb_space_tree_initialize(
45		libesedb_space_tree_t **space_tree,
46		libesedb_io_handle_t *io_handle,
47		uint32_t object_identifier,
48		uint32_t root_page_number,
49		libfdata_vector_t *pages_vector,
50		libfcache_cache_t *pages_cache,
51		libcerror_error_t **error )
52	0	{
53	0	static char *function = "libesedb_space_tree_initialize";
54
55	0	if( space_tree == NULL )
56	0	{
57	0	libcerror_error_set(
58	0	error,
59	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
60	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
61	0	"%s: invalid space tree.",
62	0	function );
63
64	0	return( -1 );
65	0	}
66	0	if( *space_tree != NULL )
67	0	{
68	0	libcerror_error_set(
69	0	error,
70	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
71	0	LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
72	0	"%s: invalid space tree value already set.",
73	0	function );
74
75	0	return( -1 );
76	0	}
77	0	*space_tree = memory_allocate_structure(
78	0	libesedb_space_tree_t );
79
80	0	if( *space_tree == NULL )
81	0	{
82	0	libcerror_error_set(
83	0	error,
84	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
85	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
86	0	"%s: unable to create space tree.",
87	0	function );
88
89	0	goto on_error;
90	0	}
91	0	if( memory_set(
92	0	( *space_tree ),
93	0	0,
94	0	sizeof( libesedb_space_tree_t ) ) == NULL )
95	0	{
96	0	libcerror_error_set(
97	0	error,
98	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
99	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
100	0	"%s: unable to clear space tree.",
101	0	function );
102
103	0	memory_free(
104	0	*space_tree );
105
106	0	*space_tree = NULL;
107
108	0	return( -1 );
109	0	}
110	0	if( libesedb_page_tree_initialize(
111	0	&( ( *space_tree )->page_tree ),
112	0	io_handle,
113	0	pages_vector,
114	0	pages_cache,
115	0	object_identifier,
116	0	root_page_number,
117	0	NULL,
118	0	NULL,
119	0	error ) != 1 )
120	0	{
121	0	libcerror_error_set(
122	0	error,
123	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
124	0	LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
125	0	"%s: unable to create page tree.",
126	0	function );
127
128	0	goto on_error;
129	0	}
130	0	return( 1 );
131
132	0	on_error:
133	0	if( *space_tree != NULL )
134	0	{
135	0	memory_free(
136	0	*space_tree );
137
138	0	*space_tree = NULL;
139	0	}
140	0	return( -1 );
141	0	}
142
143		/* Frees a space_tree
144		* Returns 1 if successful or -1 on error
145		*/
146		int libesedb_space_tree_free(
147		libesedb_space_tree_t **space_tree,
148		libcerror_error_t **error )
149	0	{
150	0	static char *function = "libesedb_space_tree_free";
151	0	int result = 1;
152
153	0	if( space_tree == NULL )
154	0	{
155	0	libcerror_error_set(
156	0	error,
157	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
158	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
159	0	"%s: invalid space tree.",
160	0	function );
161
162	0	return( -1 );
163	0	}
164	0	if( *space_tree != NULL )
165	0	{
166	0	if( libesedb_page_tree_free(
167	0	&( ( *space_tree )->page_tree ),
168	0	error ) != 1 )
169	0	{
170	0	libcerror_error_set(
171	0	error,
172	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
173	0	LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
174	0	"%s: unable to free page tree.",
175	0	function );
176
177	0	result = -1;
178	0	}
179	0	memory_free(
180	0	*space_tree );
181
182	0	*space_tree = NULL;
183	0	}
184	0	return( result );
185	0	}
186
187		/* Reads the space_tree values from a page
188		* Returns 1 if successful or -1 on error
189		*/
190		int libesedb_space_tree_read_values_from_page(
191		libesedb_space_tree_t *space_tree,
192		libbfio_handle_t *file_io_handle,
193		libesedb_page_t *page,
194		int *current_leaf_value_index,
195		int recursion_depth,
196		libcerror_error_t **error )
197	0	{
198	0	libesedb_page_t *child_page = NULL;
199	0	libesedb_page_tree_value_t *page_tree_value = NULL;
200	0	libesedb_page_value_t *page_value = NULL;
201	0	libesedb_space_tree_value_t *space_tree_value = NULL;
202	0	libfcache_cache_t *child_page_cache = NULL;
203	0	static char *function = "libesedb_space_tree_read_values_from_page";
204	0	uint32_t child_page_number = 0;
205	0	uint32_t page_flags = 0;
206	0	uint32_t total_number_of_pages = 0;
207	0	uint16_t number_of_page_values = 0;
208	0	uint16_t page_value_index = 0;
209
210		#if defined( HAVE_DEBUG_OUTPUT )
211		uint32_t father_data_page_object_identifier = 0;
212		#endif
213
214	0	if( space_tree == NULL )
215	0	{
216	0	libcerror_error_set(
217	0	error,
218	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
219	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
220	0	"%s: invalid space tree.",
221	0	function );
222
223	0	return( -1 );
224	0	}
225	0	if( space_tree->page_tree == NULL )
226	0	{
227	0	libcerror_error_set(
228	0	error,
229	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
230	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
231	0	"%s: invalid space tree - missing page tree.",
232	0	function );
233
234	0	return( -1 );
235	0	}
236	0	if( space_tree->page_tree->io_handle == NULL )
237	0	{
238	0	libcerror_error_set(
239	0	error,
240	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
241	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
242	0	"%s: invalid space tree - invalid page tree - missing IO handle.",
243	0	function );
244
245	0	return( -1 );
246	0	}
247	0	if( current_leaf_value_index == NULL )
248	0	{
249	0	libcerror_error_set(
250	0	error,
251	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
252	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
253	0	"%s: invalid current leaf value index.",
254	0	function );
255
256	0	return( -1 );
257	0	}
258	0	if( ( recursion_depth < 0 )
259	0	\|\| ( recursion_depth > LIBESEDB_MAXIMUM_INDEX_NODE_RECURSION_DEPTH ) )
260	0	{
261	0	libcerror_error_set(
262	0	error,
263	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
264	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
265	0	"%s: invalid recursion depth value out of bounds.",
266	0	function );
267
268	0	return( -1 );
269	0	}
270		#if defined( HAVE_DEBUG_OUTPUT )
271		if( libcnotify_verbose != 0 )
272		{
273		if( libesedb_page_get_father_data_page_object_identifier(
274		page,
275		&father_data_page_object_identifier,
276		error ) != 1 )
277		{
278		libcerror_error_set(
279		error,
280		LIBCERROR_ERROR_DOMAIN_RUNTIME,
281		LIBCERROR_RUNTIME_ERROR_GET_FAILED,
282		"%s: unable to retrieve father data page object identifier.",
283		function );
284
285		goto on_error;
286		}
287		if( space_tree->page_tree->object_identifier != father_data_page_object_identifier )
288		{
289		libcnotify_printf(
290		"%s: mismatch in father data page object identifier (tree: %" PRIu32 " != page: %" PRIu32 ").\n",
291		function,
292		space_tree->page_tree->object_identifier,
293		father_data_page_object_identifier );
294		}
295		}
296		#endif /* defined( HAVE_DEBUG_OUTPUT ) */
297
298	0	if( libesedb_page_get_number_of_values(
299	0	page,
300	0	&number_of_page_values,
301	0	error ) != 1 )
302	0	{
303	0	libcerror_error_set(
304	0	error,
305	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
306	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
307	0	"%s: unable to retrieve number of page values.",
308	0	function );
309
310	0	goto on_error;
311	0	}
312	0	if( number_of_page_values == 0 )
313	0	{
314	0	return( 1 );
315	0	}
316	0	if( libesedb_page_get_flags(
317	0	page,
318	0	&page_flags,
319	0	error ) != 1 )
320	0	{
321	0	libcerror_error_set(
322	0	error,
323	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
324	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
325	0	"%s: unable to retrieve page flags.",
326	0	function );
327
328	0	goto on_error;
329	0	}
330	0	if( libesedb_page_get_value_by_index(
331	0	page,
332	0	0,
333	0	&page_value,
334	0	error ) != 1 )
335	0	{
336	0	libcerror_error_set(
337	0	error,
338	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
339	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
340	0	"%s: unable to retrieve page value: 0.",
341	0	function );
342
343	0	goto on_error;
344	0	}
345	0	if( page_value == NULL )
346	0	{
347	0	libcerror_error_set(
348	0	error,
349	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
350	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
351	0	"%s: invalid page value.",
352	0	function );
353
354	0	goto on_error;
355	0	}
356		#if defined( HAVE_DEBUG_OUTPUT )
357		if( libcnotify_verbose != 0 )
358		{
359		libcnotify_printf(
360		"%s: page value: 000 page tag flags\t: 0x%02" PRIx8 "",
361		function,
362		page_value->flags );
363		libesedb_debug_print_page_tag_flags(
364		page_value->flags );
365		libcnotify_printf(
366		"\n" );
367
368		libcnotify_printf(
369		"%s: page value: 000 data:\n",
370		function );
371		libcnotify_print_data(
372		page_value->data,
373		(size_t) page_value->size,
374		LIBCNOTIFY_PRINT_DATA_FLAG_GROUP_DATA );
375		}
376		#endif /* defined( HAVE_DEBUG_OUTPUT ) */
377
378		/* Use a local cache to prevent cache invalidation of the page
379		* when reading child pages.
380		*/
381	0	if( libfcache_cache_initialize(
382	0	&child_page_cache,
383	0	1,
384	0	error ) != 1 )
385	0	{
386	0	libcerror_error_set(
387	0	error,
388	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
389	0	LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
390	0	"%s: unable to create child page cache.",
391	0	function );
392
393	0	goto on_error;
394	0	}
395	0	for( page_value_index = 1;
396	0	page_value_index < number_of_page_values;
397	0	page_value_index++ )
398	0	{
399	0	if( libesedb_page_get_value_by_index(
400	0	page,
401	0	page_value_index,
402	0	&page_value,
403	0	error ) != 1 )
404	0	{
405	0	libcerror_error_set(
406	0	error,
407	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
408	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
409	0	"%s: unable to retrieve page value: %" PRIu16 ".",
410	0	function,
411	0	page_value_index );
412
413	0	goto on_error;
414	0	}
415	0	if( page_value == NULL )
416	0	{
417	0	libcerror_error_set(
418	0	error,
419	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
420	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
421	0	"%s: missing page value: %" PRIu16 ".",
422	0	function,
423	0	page_value_index );
424
425	0	goto on_error;
426	0	}
427		#if defined( HAVE_DEBUG_OUTPUT )
428		if( libcnotify_verbose != 0 )
429		{
430		libcnotify_printf(
431		"%s: page value: %03" PRIu16 " page tag flags\t: 0x%02" PRIx8 "",
432		function,
433		page_value_index,
434		page_value->flags );
435		libesedb_debug_print_page_tag_flags(
436		page_value->flags );
437		libcnotify_printf(
438		"\n" );
439
440		libcnotify_printf(
441		"\n" );
442		}
443		#endif
444	0	if( ( page_value->flags & LIBESEDB_PAGE_TAG_FLAG_IS_DEFUNCT ) != 0 )
445	0	{
446	0	continue;
447	0	}
448	0	if( libesedb_page_tree_value_initialize(
449	0	&page_tree_value,
450	0	error ) != 1 )
451	0	{
452	0	libcerror_error_set(
453	0	error,
454	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
455	0	LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
456	0	"%s: unable to create page tree value.",
457	0	function );
458
459	0	goto on_error;
460	0	}
461	0	if( libesedb_page_tree_value_read_data(
462	0	page_tree_value,
463	0	page_value->data,
464	0	(size_t) page_value->size,
465	0	page_value->flags,
466	0	error ) != 1 )
467	0	{
468	0	libcerror_error_set(
469	0	error,
470	0	LIBCERROR_ERROR_DOMAIN_IO,
471	0	LIBCERROR_IO_ERROR_READ_FAILED,
472	0	"%s: unable to read page tree value: %" PRIu16 ".",
473	0	function,
474	0	page_value_index );
475
476	0	goto on_error;
477	0	}
478	0	if( ( page_flags & LIBESEDB_PAGE_FLAG_IS_LEAF ) != 0 )
479	0	{
480	0	if( libesedb_space_tree_value_initialize(
481	0	&space_tree_value,
482	0	error ) != 1 )
483	0	{
484	0	libcerror_error_set(
485	0	error,
486	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
487	0	LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
488	0	"%s: unable to create space tree value.",
489	0	function );
490
491	0	goto on_error;
492	0	}
493	0	if( libesedb_space_tree_value_read_data(
494	0	space_tree_value,
495	0	page_tree_value->data,
496	0	(size_t) page_tree_value->data_size,
497	0	error ) != 1 )
498	0	{
499	0	libcerror_error_set(
500	0	error,
501	0	LIBCERROR_ERROR_DOMAIN_IO,
502	0	LIBCERROR_IO_ERROR_READ_FAILED,
503	0	"%s: unable to read space tree value: %" PRIu16 ".",
504	0	function,
505	0	page_value_index );
506
507	0	goto on_error;
508	0	}
509	0	total_number_of_pages += space_tree_value->number_of_pages;
510
511	0	if( libesedb_space_tree_value_free(
512	0	&space_tree_value,
513	0	error ) != 1 )
514	0	{
515	0	libcerror_error_set(
516	0	error,
517	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
518	0	LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
519	0	"%s: unable to free space tree value.",
520	0	function );
521
522	0	goto on_error;
523	0	}
524	0	}
525	0	else
526	0	{
527	0	if( page_tree_value->data_size < 4 )
528	0	{
529	0	libcerror_error_set(
530	0	error,
531	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
532	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
533	0	"%s: invalid page tree value: %" PRIu16 " data size value out of bounds.",
534	0	function,
535	0	page_value_index );
536
537	0	goto on_error;
538	0	}
539	0	byte_stream_copy_to_uint32_little_endian(
540	0	page_tree_value->data,
541	0	child_page_number );
542
543		#if defined( HAVE_DEBUG_OUTPUT )
544		if( libcnotify_verbose != 0 )
545		{
546		libcnotify_printf(
547		"%s: page value: %03" PRIu16 " child page number\t\t: %" PRIu32 "",
548		function,
549		page_value_index,
550		child_page_number );
551
552		if( child_page_number == 0 )
553		{
554		libcnotify_printf(
555		" (invalid page number)\n" );
556		}
557		else if( child_page_number > space_tree->page_tree->io_handle->last_page_number )
558		{
559		libcnotify_printf(
560		" (exceeds last page number: %" PRIu32 ")\n",
561		space_tree->page_tree->io_handle->last_page_number );
562		}
563		libcnotify_printf(
564		"\n" );
565		libcnotify_printf(
566		"\n" );
567		}
568		#endif
569	0	#if ( SIZEOF_INT <= 4 )
570	0	if( ( child_page_number < 1 )
571	0	\|\| ( child_page_number > (uint32_t) INT_MAX ) )
572		#else
573		if( ( child_page_number < 1 )
574		\|\| ( (int) child_page_number > INT_MAX ) )
575		#endif
576	0	{
577	0	libcerror_error_set(
578	0	error,
579	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
580	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
581	0	"%s: invalid child page number value out of bounds.",
582	0	function );
583
584	0	goto on_error;
585	0	}
586		#if defined( HAVE_DEBUG_OUTPUT )
587		if( libcnotify_verbose != 0 )
588		{
589		if( page_tree_value->data_size > 4 )
590		{
591		libcnotify_printf(
592		"%s: page value: %03" PRIu16 " trailing data:\n",
593		function,
594		page_value_index );
595		libcnotify_print_data(
596		&( page_tree_value->data[ 4 ] ),
597		page_tree_value->data_size - 4,
598		LIBCNOTIFY_PRINT_DATA_FLAG_GROUP_DATA );
599		}
600		}
601		#endif
602	0	if( ( child_page_number > 0 )
603	0	&& ( child_page_number <= space_tree->page_tree->io_handle->last_page_number ) )
604	0	{
605	0	if( libfdata_vector_get_element_value_by_index(
606	0	space_tree->page_tree->pages_vector,
607	0	(intptr_t *) file_io_handle,
608	0	(libfdata_cache_t *) child_page_cache,
609	0	(int) child_page_number - 1,
610	0	(intptr_t **) &child_page,
611	0	0,
612	0	error ) != 1 )
613	0	{
614	0	libcerror_error_set(
615	0	error,
616	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
617	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
618	0	"%s: unable to retrieve page: %" PRIu32 ".",
619	0	function,
620	0	child_page_number );
621
622	0	goto on_error;
623	0	}
624	0	if( libesedb_page_validate_space_tree_page(
625	0	child_page,
626	0	error ) != 1 )
627	0	{
628	0	libcerror_error_set(
629	0	error,
630	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
631	0	LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
632	0	"%s: unsupported page.",
633	0	function );
634
635	0	goto on_error;
636	0	}
637	0	if( libesedb_space_tree_read_values_from_page(
638	0	space_tree,
639	0	file_io_handle,
640	0	child_page,
641	0	current_leaf_value_index,
642	0	recursion_depth + 1,
643	0	error ) != 1 )
644	0	{
645	0	libcerror_error_set(
646	0	error,
647	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
648	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
649	0	"%s: unable to read values from page: %" PRIu32 ".",
650	0	function,
651	0	child_page_number );
652
653	0	goto on_error;
654	0	}
655	0	}
656	0	}
657	0	if( libesedb_page_tree_value_free(
658	0	&page_tree_value,
659	0	error ) != 1 )
660	0	{
661	0	libcerror_error_set(
662	0	error,
663	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
664	0	LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
665	0	"%s: unable to free page tree value.",
666	0	function );
667
668	0	goto on_error;
669	0	}
670	0	}
671	0	if( libfcache_cache_free(
672	0	&child_page_cache,
673	0	error ) != 1 )
674	0	{
675	0	libcerror_error_set(
676	0	error,
677	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
678	0	LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
679	0	"%s: unable to free child page cache.",
680	0	function );
681
682	0	goto on_error;
683	0	}
684		#if defined( HAVE_DEBUG_OUTPUT )
685		if( libcnotify_verbose != 0 )
686		{
687		libcnotify_printf(
688		"%s: total number of pages\t\t: %" PRIu32 "\n",
689		function,
690		total_number_of_pages );
691
692		libcnotify_printf(
693		"\n" );
694		}
695		#endif
696	0	return( 1 );
697
698	0	on_error:
699	0	if( page_tree_value != NULL )
700	0	{
701	0	libesedb_page_tree_value_free(
702	0	&page_tree_value,
703	0	NULL );
704	0	}
705	0	if( space_tree_value != NULL )
706	0	{
707	0	libesedb_space_tree_value_free(
708	0	&space_tree_value,
709	0	NULL );
710	0	}
711	0	if( child_page_cache != NULL )
712	0	{
713	0	libfcache_cache_free(
714	0	&child_page_cache,
715	0	NULL );
716	0	}
717	0	return( -1 );
718	0	}
719
720		/* Reads the space tree
721		* Returns 1 if successful or -1 on error
722		*/
723		int libesedb_space_tree_read_file_io_handle(
724		libesedb_space_tree_t *space_tree,
725		libbfio_handle_t *file_io_handle,
726		libcerror_error_t **error )
727	0	{
728	0	libesedb_page_t *root_page = NULL;
729	0	libfcache_cache_t *root_page_cache = NULL;
730	0	static char *function = "libesedb_space_tree_read_file_io_handle";
731	0	int current_leaf_value_index = 0;
732
733	0	if( space_tree == NULL )
734	0	{
735	0	libcerror_error_set(
736	0	error,
737	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
738	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
739	0	"%s: invalid space tree.",
740	0	function );
741
742	0	return( -1 );
743	0	}
744	0	if( space_tree->page_tree == NULL )
745	0	{
746	0	libcerror_error_set(
747	0	error,
748	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
749	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
750	0	"%s: invalid space tree - missing page tree.",
751	0	function );
752
753	0	return( -1 );
754	0	}
755		/* Use a local cache to prevent cache invalidation of the root page
756		* when reading child pages.
757		*/
758	0	if( libfcache_cache_initialize(
759	0	&root_page_cache,
760	0	1,
761	0	error ) != 1 )
762	0	{
763	0	libcerror_error_set(
764	0	error,
765	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
766	0	LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
767	0	"%s: unable to create root page cache.",
768	0	function );
769
770	0	goto on_error;
771	0	}
772	0	if( libfdata_vector_get_element_value_by_index(
773	0	space_tree->page_tree->pages_vector,
774	0	(intptr_t *) file_io_handle,
775	0	(libfdata_cache_t *) root_page_cache,
776	0	(int) space_tree->page_tree->root_page_number - 1,
777	0	(intptr_t **) &root_page,
778	0	0,
779	0	error ) != 1 )
780	0	{
781	0	libcerror_error_set(
782	0	error,
783	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
784	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
785	0	"%s: unable to retrieve page: %" PRIu32 ".",
786	0	function,
787	0	space_tree->page_tree->root_page_number );
788
789	0	goto on_error;
790	0	}
791	0	if( libesedb_page_validate_root_page(
792	0	root_page,
793	0	error ) != 1 )
794	0	{
795	0	libcerror_error_set(
796	0	error,
797	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
798	0	LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
799	0	"%s: unsupported root page.",
800	0	function );
801
802	0	goto on_error;
803	0	}
804		#if defined( HAVE_DEBUG_OUTPUT )
805		if( libesedb_page_tree_read_root_page_header(
806		space_tree->page_tree,
807		root_page,
808		error ) != 1 )
809		{
810		libcerror_error_set(
811		error,
812		LIBCERROR_ERROR_DOMAIN_IO,
813		LIBCERROR_IO_ERROR_READ_FAILED,
814		"%s: unable to read root page header.",
815		function );
816
817		goto on_error;
818		}
819		#endif
820	0	if( libesedb_space_tree_read_values_from_page(
821	0	space_tree,
822	0	file_io_handle,
823	0	root_page,
824	0	&current_leaf_value_index,
825	0	0,
826	0	error ) != 1 )
827	0	{
828	0	libcerror_error_set(
829	0	error,
830	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
831	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
832	0	"%s: unable to read values from root page.",
833	0	function );
834
835	0	goto on_error;
836	0	}
837	0	if( libfcache_cache_free(
838	0	&root_page_cache,
839	0	error ) != 1 )
840	0	{
841	0	libcerror_error_set(
842	0	error,
843	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
844	0	LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
845	0	"%s: unable to free root page cache.",
846	0	function );
847
848	0	goto on_error;
849	0	}
850	0	return( 1 );
851
852	0	on_error:
853	0	if( root_page_cache != NULL )
854	0	{
855	0	libfcache_cache_free(
856	0	&root_page_cache,
857		NULL );
858	0	}
859	0	return( -1 );
860	0	}
861