hfs.c

linux下开发的针对所有磁盘的数据恢复的源码

/*
** The Sleuth Kit
**
** This software is subject to the IBM Public License ver. 1.0,
** which was displayed prior to download and is included in the readme.txt
** file accompanying the Sleuth Kit files.  It may also be requested from:
** Crucial Security Inc.
** 14900 Conference Center Drive
** Chantilly, VA 20151
**
** Judson Powers [[e-mail]]
** Copyright (c) 2008 ATC-NY.  All rights reserved.
** This file contains data developed with support from the National
** Institute of Justice, Office of Justice Programs, U.S. Department of Justice.
** 
** Wyatt Banks [[e-mail]]
** Copyright (c) 2005 Crucial Security Inc.  All rights reserved.
**
** Brian Carrier [[e-mail]]
** Copyright (c) 2003-2005 Brian Carrier.  All rights reserved
**
** Copyright (c) 1997,1998,1999, International Business Machines
** Corporation and others. All Rights Reserved.
*/

/* TCT
 * LICENSE
 *      This software is distributed under the IBM Public License.
 * AUTHOR(S)
 *      Wietse Venema
 *      IBM T.J. Watson Research
 *      P.O. Box 704
 *      Yorktown Heights, NY 10598, USA
 --*/

/*
** You may distribute the Sleuth Kit, or other software that incorporates
** part of all of the Sleuth Kit, in object code form under a license agreement,
** provided that:
** a) you comply with the terms and conditions of the IBM Public License
**    ver 1.0; and
** b) the license agreement
**     i) effectively disclaims on behalf of all Contributors all warranties
**        and conditions, express and implied, including warranties or
**        conditions of title and non-infringement, and implied warranties
**        or conditions of merchantability and fitness for a particular
**        purpose.
**    ii) effectively excludes on behalf of all Contributors liability for
**        damages, including direct, indirect, special, incidental and
**        consequential damages such as lost profits.
**   iii) states that any provisions which differ from IBM Public License
**        ver. 1.0 are offered by that Contributor alone and not by any
**        other party; and
**    iv) states that the source code for the program is available from you,
**        and informs licensees how to obtain it in a reasonable manner on or
**        through a medium customarily used for software exchange.
**
** When the Sleuth Kit or other software that incorporates part or all of
** the Sleuth Kit is made available in source code form:
**     a) it must be made available under IBM Public License ver. 1.0; and
**     b) a copy of the IBM Public License ver. 1.0 must be included with
**        each copy of the program.
*/

/** \file hfs.c
 * Contains the general internal TSK HFS metadata and data unit code -- Not included in code by default.
 */

#include "tsk_fs_i.h"
#include "tsk_hfs.h"

#define XSWAP(a,b) { a ^= b; b ^= a; a ^= b; }

/* may set error up to string 1
 * returns 0 on success, 1 on failure */
uint8_t
hfs_checked_read_random(TSK_FS_INFO * fs, char *buf, size_t len,
    TSK_OFF_T offs)
{
    ssize_t r;

    r = tsk_fs_read(fs, offs, buf, len);
    if (r != len) {
        if (r >= 0) {
            tsk_error_reset();
            tsk_errno = TSK_ERR_FS_READ;
        }
        return 1;
    }
    return 0;
}

/**********************************************************************
 *
 *  MISC FUNCS
 *
 **********************************************************************/

/* convert the HFS Time (seconds from 1/1/1904)
 * to UNIX (UTC seconds from 1/1/1970)
 * The number is borrowed from linux HFS driver source
 */
uint32_t
hfs2unixtime(uint32_t hfsdate)
{
    return (uint32_t) (hfsdate - NSEC_BTWN_1904_1970);
}


/**********************************************************************
 *
 * Lookup Functions
 *
 **********************************************************************/

static int hfs_load_blockmap(HFS_INFO *);

/** \internal
 * Get allocation status of file system block.
 * adapted from IsAllocationBlockUsed from:
 * http://developer.apple.com/technotes/tn/tn1150.html
 *
 * @param hfs File system being analyzed
 * @param b Block address 
 * @returns 1 if allocated, 0 if not, -1 on error
 */
static int8_t
hfs_is_block_alloc(HFS_INFO * hfs, TSK_DADDR_T b)
{
    TSK_DADDR_T a;
    uint8_t this_byte;

    // lazy loading of block map
    if (hfs->block_map == NULL) {
        if (hfs_load_blockmap(hfs)) {
            // @@@ FIX error
            tsk_fprintf(stderr,
                "ERROR hfs_is_block_alloc: failed to load block map\n");
            return -1;
        }
    }

    a = b / 8;
    if (a > hfs->block_map_size) {
        // @@@ FIX error
        tsk_fprintf(stderr,
            "WARNING hfs_is_block_alloc: block %" PRIuDADDR
            " is past the end of the allocation file\n", b);
        return -1;
    }

    this_byte = hfs->block_map[a];
    return (this_byte & (1 << (7 - (b % 8)))) != 0;
}

/* Compares the given HFS+ Extents B-tree key to key constructed
 * for finding the beginning of the data fork extents for the given
 * CNID. (That is, the search key uses the given CNID and has
 * fork = 0 and start_block = 0.)
 */
static int
hfs_compare_extent_keys(HFS_INFO * hfs, uint32_t cnid, hfs_ext_key * key)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);
    uint32_t key_cnid;

    key_cnid = tsk_getu32(fs->endian, key->file_id);
    if (key_cnid < cnid)
        return -1;
    if (key_cnid > cnid)
        return 1;

    /* referring to the same cnids */

    /* we are always looking for the data fork (0);
       a nonzero fork (e.g., the resource fork 0xff) is higher */
    if (key->fork_type[0] != 0)
        return 1;

    /* we are always looking for a start_block of zero
       (interested in the beginning of the extents, regardless
       of what the start_block is); all files except the bad
       blocks file should have a start_block greater than
       zero */
    if (tsk_getu32(fs->endian, key->start_block) == 0)
        return 0;
    return 1;
}

/** \internal
 * Returns the length of an HFS+ B-tree key based on the tree header
 * structure and the length claimed in the record.  With some trees,
 * the length given in the record is not used. 
 * Note that this neither detects nor correctly handles 8-bit keys
 * (which should not be present in HFS+).
 * @param hfs File System
 * @param keylen Length of key as given in record
 * @param header Tree header
 * @returns Length of key
 */
static uint16_t
hfs_get_keylen(HFS_INFO * hfs, uint16_t keylen,
    hfs_btree_header_record * header)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);

    // if the flag is set, use the length given in the record
    if (tsk_getu32(fs->endian, header->attr) & HFS_BT_VARKEYS)
        return keylen;
    else
        return tsk_getu16(fs->endian, header->max_len);
}

/** \internal
 * Returns the byte offset on disk of the given node (nodenum) in the Extents B-tree.
 * Unlike the other files on disk, the Extents B-tree never occupies more than 8
 * extents, so we can simply use the in-volume-header extents to get its layout.
 * @param hfs File system
 * @param hdr Header record (to get node size)
 * @param nodenum Node number in B-Tree to find
 * @returns byte offset or 0 on failure. 
 */
static TSK_OFF_T
hfs_ext_find_node_offset(HFS_INFO * hfs, hfs_btree_header_record * hdr,
    uint32_t nodenum)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);
    uint16_t nodesize;          /* size of each node */
    int i;
    uint64_t bytes;             /* bytes left this extent */
    TSK_OFF_T r_offs;           /* offset we are reading from */
    TSK_OFF_T f_offs;           /* offset into the extents file */
    TSK_OFF_T n_offs;           /* offset of the node we are looking for */
    hfs_sb *sb = hfs->fs;

    tsk_error_reset();

    if (tsk_verbose)
        tsk_fprintf(stderr, "hfs_ext_find_node_offset: finding offset of "
            "btree node: %" PRIu32 "\n", nodenum);

    /* find first extent with data in it */
    /* included from previous code -- are there cases where
       the initial extents will appear empty? */
    i = 0;
    while ((i < 8)
        && !(tsk_getu32(fs->endian, sb->ext_file.extents[i].blk_cnt)))
        i++;

    if (i > 7) {
        tsk_errno = TSK_ERR_FS_GENFS;
        snprintf(tsk_errstr, TSK_ERRSTR_L,
            "hfs_ext_find_node_offset: no data found in extents file extents");
        return 0;
    }

    bytes =
        tsk_getu32(fs->endian,
        sb->ext_file.extents[i].blk_cnt) * (TSK_OFF_T) fs->block_size;
    r_offs =
        tsk_getu32(fs->endian,
        sb->ext_file.extents[i].start_blk) * (TSK_OFF_T) fs->block_size;
    f_offs = 0;

    nodesize = tsk_getu16(fs->endian, hdr->nodesize);

    /* calculate where we will find the 'nodenum' node */
    n_offs = nodesize * nodenum;

    while (f_offs < n_offs) {

        if (n_offs <= (f_offs + (TSK_OFF_T)bytes)) {

            r_offs += n_offs - f_offs;
            f_offs = n_offs;

        }
        else {

            i++;

            if (i > 7) {
                tsk_errno = TSK_ERR_FS_GENFS;
                snprintf(tsk_errstr, TSK_ERRSTR_L,
                    "hfs_ext_find_node_offset: file seek error while searching for node %"
                    PRIu32 "\n", nodenum);
                return 0;
            }

            r_offs =
                tsk_getu32(fs->endian,
                sb->ext_file.extents[i].start_blk) *
                (TSK_OFF_T) fs->block_size;
            f_offs += bytes;
            bytes =
                tsk_getu32(fs->endian,
                sb->ext_file.extents[i].blk_cnt) *
                (TSK_OFF_T) fs->block_size;

        }
    }

    return r_offs;

}

/** \internal
 * Process a B-Tree node record and return the record contents and the 
 * offset of the data content in the record. 
 * Note that this neither detects nor correctly handles odd-length keys
 * or 8-bit keys (neither should be present in HFS+).
 * @param hfs File system being analyzed
 * @param header Header of B-Tree record is in.  If NULL, then 
 * only the keylength in the record is used (i.e. flag settings ignored).
 * @param rec_off Byte offset in disk where record starts
 * @param [out] a_buf Pointer to buffer to store record in (or NULL).  
 * Must be at least 2 bytes long if it is not NULL.
 * @param a_buf_len Length of buf (amount of record to read)
 * @param clear If 1,  clear the key value before reading into it. 
 * @returns Offset of data content in record or 0 on error
 */
TSK_OFF_T
hfs_read_key(HFS_INFO * hfs, hfs_btree_header_record * header,
    TSK_OFF_T rec_off, char *a_buf, int a_buf_len, uint8_t clear)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);
    char buf[2];
    char *dest = a_buf ? a_buf : buf;
    uint16_t keylen;

    tsk_error_reset();

    if (a_buf && clear)         /* zero a_buf */
        memset(a_buf + 2, 0, a_buf_len - 2);

    // get the key length as reported in the record
    if (hfs_checked_read_random(fs, dest, 2, rec_off))  /* read size */
        return 0;

    keylen = tsk_getu16(fs->endian, dest);
    // use the header to figure out if we should be ignoring this length or not
    if (header)
        keylen = hfs_get_keylen(hfs, keylen, header);

    if ((header && (keylen > tsk_getu16(fs->endian, header->max_len)))
        || (!header && (keylen > 516))) {       /* sanity check key length */
        tsk_errno = TSK_ERR_FS_GENFS;
        snprintf(tsk_errstr, TSK_ERRSTR_L,
            "hfs_read_key: key length out of range (%" PRIu16 ")", keylen);
        return 0;
    }

    // read the key and other data into the buffer if they asked for it
    if (a_buf) {                /* read key */
        if (hfs_checked_read_random(fs, a_buf + 2,
                (keylen + 2 <= a_buf_len) ?
                keylen : a_buf_len - 2, rec_off + 2))
            return 0;
    }

    if (tsk_verbose)
        tsk_fprintf(stderr,
            "hfs_read_key: read key of length %" PRIu16 "\n", keylen);

    return rec_off + 2 + keylen;        /* return record data address */
}

/** \internal
 * Return the disk byte offset of a record in a btree node.
 * Note that this points to start of the record (hfs_read_key
 * can be used to determine the content offset).
 *
 * @param hfs File system node is in
 * @param node_off Byte offset in disk of start of node. 
 * @param nodesize Size, in bytes, of each node
 * @param rec Record number to return offset of
 * @returns 0 on error or offset.