hfs.c

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

 */
TSK_OFF_T
hfs_get_bt_rec_off(HFS_INFO * hfs, TSK_OFF_T node_off,
    uint16_t nodesize, uint16_t rec)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);
    TSK_OFF_T off;
    char buf[2];

    tsk_error_reset();

    off = node_off + nodesize - 2 * (rec + 1);  /* location of record offset */
    if (hfs_checked_read_random(fs, buf, 2, off))       /* read record offset */
        return 0;
    off = node_off + tsk_getu16(fs->endian, buf);       /* go to record */

    if (tsk_verbose)
        tsk_fprintf(stderr,
            "hfs_get_bt_rec_off: record %" PRIu16 " @ %" PRIu64
            " (node @ %" PRIu64 ")\n", rec, off, node_off);

    return off;
}

/* Advances to the next record in the Extents B-tree, given information about
 * where you currently are in the B-tree.
 * Assumes that you are actually keeping track of these many fields. They
 * must correctly contain the current values. If the current node is changed,
 * they will be changed to their new values.
 * Returns cur_node. If you have reached the end of the node chain (no more
 * records), cur_node will be set to zero and returned.
 */
/** \internal
 * Takes current state variables as input and advances to next record.  If
 * the next record is in a different node, then it advances the node.  If a
 * new node needs to be loaded, the values passed as arguments are updated. 
 *
 * @param hfs [in] File system being analyzed
 * @param rec [in,out] Record number of the current record in the current node
 * @param num_rec [in,out] Number of records in current node
 * @param node [in,out] Node structure for current node
 * @param cur_node [in,out] Address of current node
 * @param cur_node_off [in,out] XXXX
 * @param header [in] Header of tree
 * @returns 0 on error */
static uint32_t
hfs_ext_next_record(HFS_INFO * hfs, uint16_t * rec, uint16_t * num_rec,
    hfs_btree_node * node, uint32_t * cur_node, TSK_OFF_T * cur_node_off,
    hfs_btree_header_record * header)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);

    tsk_error_reset();

    /* passing invalid pointers (or null) to this function is unchecked */

    (*rec)++;

    if (*rec >= *num_rec) {     /* ran out of records in this node */
        *cur_node = tsk_getu32(fs->endian, node->flink);
        if (*cur_node == 0)
            return *cur_node;
        *cur_node_off = hfs_ext_find_node_offset(hfs, header, *cur_node);
        if (*cur_node_off == 0) {
            snprintf(tsk_errstr2, TSK_ERRSTR_L,
                "hfs_ext_next_record: find next node offset (%" PRIu32 ")",
                *cur_node);
            return 0;
        }
        if (hfs_checked_read_random(fs, (char *) node,
                sizeof(hfs_btree_node), *cur_node_off)) {
            snprintf(tsk_errstr2, TSK_ERRSTR_L,
                "hfs_ext_next_record: read btree node %" PRIu32 " at %"
                PRIuDADDR, *cur_node, *cur_node_off);
            return 0;
        }
        *num_rec = tsk_getu16(fs->endian, node->num_rec);
        *rec = 0;
        if (tsk_verbose)
            tsk_fprintf(stderr,
                "hfs_ext_next_record: advanced to next node %" PRIu32
                "(@ %" PRIu64 ", has %" PRIu16 "records \n", *cur_node,
                *cur_node_off, *num_rec);
    }
    else {
        if (tsk_verbose)
            tsk_fprintf(stderr,
                "hfs_ext_next_record: advanced to record %" PRIu16 "\n",
                *rec);
    }

    return *cur_node;
}


// @@@ This could probably return TSK_FS_ATTR
/**  \internal
 * Returns the extents (data runs) for the data fork of a given file.  The
 * caller must free the returned array. 
 * 
 * @param hfs File system being analyzed
 * @param cnid CNID of the file to get data on
 * @param first_ext Pointer to 8 extents of file that have already been found 
 * (or NULL).  Note if it is not NULL, it must have 8 elements in the array. It
 * will be copied to start of returned array. 
 * @returns Array of extents (not guaranteed to be a multple of 8).  The final
 * entry will have 0,0 entries.  NULL on error.  
 * Note that if first_ext is NULL and no extents are
 * found, this function will also return NULL.
 * May set up to error string 2.  
 */
static hfs_ext_desc *
hfs_ext_find_extent_record(HFS_INFO * hfs, uint32_t cnid,
    hfs_ext_desc * first_ext)
{
    TSK_FS_INFO *fs = (TSK_FS_INFO *) & (hfs->fs_info);

    hfs_btree_header_record header;     /* header for the Extents btree */
    uint16_t leafsize;          /* size of nodes (all, regardless of the name) */

    uint32_t cur_node;          /* node id of the current node */

    hfs_ext_desc *out_ext;
    int num_out_ext;

    TSK_OFF_T off;

    char buf[4];
    int i;

    tsk_error_reset();

    /* initialize the output extents */
    if (first_ext == NULL) {
        num_out_ext = 0;
        out_ext = NULL;
    }
    else {
        num_out_ext = 8;
        out_ext = (hfs_ext_desc *)
            tsk_malloc(9 * sizeof(hfs_ext_desc));
        if (out_ext == NULL)
            return NULL;
        memcpy(out_ext, first_ext, 8 * sizeof(hfs_ext_desc));
        memset(out_ext + 8, 0, sizeof(hfs_ext_desc));
        /* we make 9 output extents so that if these are all the extents,
           there's a guaranteed terminating (0,0); we only set num_out_ext
           to 8 so that we overwrite our 9th extent if we don't need it */
    }

    /* Get the starting address of the extents file to read header record */
    // @@@@ ERROR: header is 0 here, which doesn't help to find the node size, which is why it is passe to find_....
    off = hfs_ext_find_node_offset(hfs, &header, 0);
    if (off == 0) {
        snprintf(tsk_errstr2, TSK_ERRSTR_L,
            "hfs_ext_find_extent_record: finding extents header node");
        if (out_ext != NULL)
            free(out_ext);
        return NULL;
    }
    off += 14;                  // sizeof(hfs_btree_node) 
    if (hfs_checked_read_random(fs, (char *) &header, sizeof(header), off)) {
        snprintf(tsk_errstr2, TSK_ERRSTR_L,
            "hfs_ext_find_extent_record: reading extents header node at %"
            PRIuDADDR, off);
        if (out_ext != NULL)
            free(out_ext);
        return NULL;
    }
    leafsize = tsk_getu16(fs->endian, header.nodesize);

    /* start at root node */
    cur_node = tsk_getu32(fs->endian, header.root);

    /* if the root node is zero, then the extents btree is empty */
    /* if no files have overflow extents, the Extents B-tree still
       exists on disk, but is an empty B-tree containing only
       the header node */
    if (cur_node == 0) {
        if (tsk_verbose)
            tsk_fprintf(stderr, "hfs_ext_find_extent_record: "
                "empty extents btree\n");
        return out_ext;
    }

    if (tsk_verbose)
        tsk_fprintf(stderr, "hfs_ext_find_extent_record: starting at "
            "root node %" PRIu32 "; header @ %" PRIuOFF "; leafsize = %"
            PRIu16 "\n", cur_node, off, leafsize);

    while (1) {
        TSK_OFF_T cur_off;      /* start address of cur_node */
        hfs_btree_node node;    /* data of the current node */
        uint16_t num_rec;       /* number of records in this node */
        hfs_ext_key key;        /* current key */
        TSK_DADDR_T addr, recaddr;
        uint16_t rec, recno;

        /* load node header */
        cur_off = hfs_ext_find_node_offset(hfs, &header, cur_node);
        if (cur_off == 0) {
            snprintf(tsk_errstr2, TSK_ERRSTR_L,
                "hfs_ext_find_extent_record: finding extents node (%"
                PRIu32 ")", cur_node);
            if (out_ext != NULL)
                free(out_ext);
            return NULL;
        }

        // @@@ We could probably make this faster by reading the entire node

        if (hfs_checked_read_random(fs, (char *) &node, sizeof(node),
                cur_off)) {
            snprintf(tsk_errstr2, TSK_ERRSTR_L,
                "hfs_ext_find_extent_record: reading extents node (%"
                PRIu32 " at %" PRIuDADDR ")", cur_node, cur_off);
            if (out_ext != NULL)
                free(out_ext);
            return NULL;
        }

        num_rec = tsk_getu16(fs->endian, node.num_rec);

        if (tsk_verbose)
            tsk_fprintf(stderr, "hfs_ext_find_extent_record: node %" PRIu32
                " @ %" PRIu64 " has %" PRIu16 " records\n",
                cur_node, cur_off, num_rec);

        if (num_rec == 0) {
            tsk_errno = TSK_ERR_FS_GENFS;
            snprintf(tsk_errstr, TSK_ERRSTR_L,
                "hfs_ext_find_extent_record: zero records in node %"
                PRIu32, cur_node);
            if (out_ext != NULL)
                free(out_ext);
            return NULL;
        }

        /* find largest key smaller than or equal to cnid */
        recno = 0;
        recaddr = 0;
        for (rec = 0; rec < num_rec; rec++) {
            int cmp;

            // get the record offset
            addr = hfs_get_bt_rec_off(hfs, cur_off, leafsize, rec);
            if (addr == 0) {
                snprintf(tsk_errstr2, TSK_ERRSTR_L,
                    "hfs_ext_find_extent_record: finding record %" PRIu16
                    " in node %" PRIu32, rec, cur_node);
                if (out_ext != NULL)
                    free(out_ext);
                return NULL;
            }

            // get the content offet and read the key
            addr =
                hfs_read_key(hfs, &header, addr, (char *) &key,
                sizeof(hfs_ext_key), 1);
            if (addr == 0) {
                snprintf(tsk_errstr2, TSK_ERRSTR_L,
                    "hfs_ext_find_extent_record: reading key for record %"
                    PRIu16 " in node %" PRIu32, rec, cur_node);
                if (out_ext != NULL)
                    free(out_ext);
                return NULL;
            }
            cmp = hfs_compare_extent_keys(hfs, cnid, &key);

            if (tsk_verbose)
                tsk_fprintf(stderr,
                    "hfs_ext_find_extent_record: record %" PRIu16 " @ %"
                    PRIu64 "; keylen %" PRIu16 " (%" PRIu32 ", %" PRIu8
                    ", %" PRIu32 "); compare: %d\n", rec, addr,
                    tsk_getu16(fs->endian, key.key_len),
                    tsk_getu32(fs->endian, key.file_id), key.fork_type[0],
                    tsk_getu32(fs->endian, key.start_block), cmp);

            /* find the largest key less than or equal to our key */
            /* if all keys are larger than our key, select the leftmost key */
            if ((cmp <= 0) || (recaddr == 0)) {
                recaddr = addr;
                recno = rec;
            }
            if (cmp >= 0)
                break;
        }

        if (node.kind == HFS_BTREE_INDEX_NODE) {
            /* replace cur node number with the node number referenced
             * by the found key, continue until we hit a leaf. */
            if (hfs_checked_read_random(fs, buf, 4, recaddr)) {
                snprintf(tsk_errstr2, TSK_ERRSTR_L,
                    "hfs_ext_find_extent_record: reading pointer in record %"
                    PRIu16 " in node %" PRIu32, rec, cur_node);
                if (out_ext != NULL)
                    free(out_ext);
                return NULL;
            }
            cur_node = tsk_getu32(fs->endian, buf);
        }
        else if (node.kind == HFS_BTREE_LEAF_NODE) {
            rec = recno;        /* using rec as our counting variable again, for kicks */

            /* reget key */
            addr = hfs_get_bt_rec_off(hfs, cur_off, leafsize, rec);
            if (addr == 0) {
                snprintf(tsk_errstr2, TSK_ERRSTR_L,
                    "hfs_ext_find_extent_record: finding record %" PRIu16
                    " in node %" PRIu32, rec, cur_node);
                if (out_ext != NULL)
                    free(out_ext);
                return NULL;
            }
            addr =
                hfs_read_key(hfs, &header, addr, (char *) &key,
                sizeof(hfs_ext_key), 1);
            if (addr == 0) {
                snprintf(tsk_errstr2, TSK_ERRSTR_L,
                    "hfs_ext_find_extent_record: reading key for record %"
                    PRIu16 " in node %" PRIu32, rec, cur_node);
                if (out_ext != NULL)
                    free(out_ext);
                return NULL;
            }

            /* we've been searching for a start block of zero, and we're
             * essentially guaranteed it won't have a start block of zero;
             * as a result, we may very well be one left of our target --
             * but since we alternately take the leftmost record, we might *not*
             * be one left of our target */

            /* we don't check for it, but note that the current record would have
             * to be less than the record we're looking for -- if it's greater,
             * there's no record in the btree for us */

            /* correct this, first */

            /* if associated with the wrong file */
            if (tsk_getu32(fs->endian, key.file_id) != cnid) {

                /* go to the next record */
                if ((hfs_ext_next_record(hfs, &rec, &num_rec, &node,
                            &cur_node, &cur_off, &header)) == 0) {
                    if (cur_node != 0) {
                        snprintf(tsk_errstr2, TSK_ERRSTR_L,
                            "hfs_ext_find_extent_record: advancing to next record (record %"
                            PRIu16 " node %" PRIu32 ")", rec, cur_node);
                        if (out_ext != NULL)
                            free(out_ext);
                        return NULL;
                    }

                    /* here, means that our file is not in the overflow extents tree */
                    if (tsk_verbose)
                        tsk_fprintf(stderr, "hfs_ext_find_extent_record: "
                            "end of extents btree before finding any extents\n");
                    return out_ext;
                }

                /* load new key data, since I'm about to use it */
                addr = hfs_get_bt_rec_off(hfs, cur_off, leafsize, rec);
                if (addr == 0) {
                    snprintf(tsk_errstr2, TSK_ERRSTR_L,
                        "hfs_ext_find_extent_record: finding record %"
                        PRIu16 " in node %" PRIu32, rec, cur_node);
                    if (out_ext != NULL)
                        free(out_ext);
                    return NULL;
                }
                addr =
                    hfs_read_key(hfs, &header, addr, (char *) &key,
                    sizeof(hfs_ext_key), 1);
                if (addr == 0) {
                    snprintf(tsk_errstr2, TSK_ERRSTR_L,
                        "hfs_ext_find_extent_record: reading key for record %"
                        PRIu16 " in node %" PRIu32, rec, cur_node);