key.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (C) 2018 Ernesto A. Fernández <ernesto.mnd.fernandez@gmail.com>
 */

#include<linux/crc32c.h>
#include"apfs.h"
#include"unicode.h"

/**
 * apfs_filename_cmp - Normalize and compare two APFS filenames
 * @sb: filesystem superblock
 * @name1: first name to compare
 * @len1: length of @name1
 * @name2: second name to compare
 * @len2: length of the @name2
 *
 * Returns 0 if @name1 and @name2 are equal, or non-zero otherwise.
 */
intapfs_filename_cmp(structsuper_block*sb,
constchar*name1, unsigned intlen1,
constchar*name2, unsigned intlen2)
{
structapfs_unicursorcursor1, cursor2;
boolcase_fold=apfs_is_case_insensitive(sb);

if (!apfs_is_normalization_insensitive(sb)) {
if (len1!=len2)
return-1;
returnmemcmp(name1, name2, len1);
 }

apfs_init_unicursor(&cursor1, name1, len1);
apfs_init_unicursor(&cursor2, name2, len2);

while (1) {
unicode_tuni1, uni2;

uni1=apfs_normalize_next(&cursor1, case_fold);
uni2=apfs_normalize_next(&cursor2, case_fold);

if (uni1!=uni2)
returnuni1<uni2 ? -1 : 1;
if (!uni1)
return0;
 }
}

/**
 * apfs_keycmp - Compare two keys
 * @k1: first key to compare
 * @k2: second key to compare
 *
 * returns 0 if @k1 and @k2 are equal
 * < 0 if @k1 comes before @k2 in the btree
 * > 0 if @k1 comes after @k2 in the btree
 */
intapfs_keycmp(structapfs_key*k1, structapfs_key*k2)
{
if (k1->id!=k2->id)
returnk1->id<k2->id ? -1 : 1;
if (k1->type!=k2->type)
returnk1->type<k2->type ? -1 : 1;
if (k1->number!=k2->number)
returnk1->number<k2->number ? -1 : 1;
if (!k1->name|| !k2->name)
return0;

/* Normalization seems to be ignored here, even for directory records */
returnstrcmp(k1->name, k2->name);
}

/**
 * apfs_read_cat_key - Parse an on-disk catalog key
 * @raw: pointer to the raw key
 * @size: size of the raw key
 * @key: apfs_key structure to store the result
 * @hashed: are the directory records hashed?
 *
 * Returns 0 on success, or a negative error code otherwise.
 */
intapfs_read_cat_key(void*raw, intsize, structapfs_key*key, boolhashed)
{
if (size<sizeof(structapfs_key_header)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
key->id=apfs_cat_cnid((structapfs_key_header*)raw);
key->type=apfs_cat_type((structapfs_key_header*)raw);

switch (key->type) {
caseAPFS_TYPE_DIR_REC:
if (hashed) {
if (size<sizeof(structapfs_drec_hashed_key) +1||
*((char*)raw+size-1) !=0) {
/* Filename must have NULL-termination */
apfs_err(NULL, "invalid drec key (%d)", size);
return-EFSCORRUPTED;
 }
/* Name length is not used in key comparisons, only the hash */
key->number=le32_to_cpu(
 ((structapfs_drec_hashed_key*)raw)->name_len_and_hash) &
APFS_DREC_HASH_MASK;
key->name= ((structapfs_drec_hashed_key*)raw)->name;
 } else {
if (size<sizeof(structapfs_drec_key) +1||
*((char*)raw+size-1) !=0) {
/* Filename must have NULL-termination */
apfs_err(NULL, "invalid drec key (%d)", size);
return-EFSCORRUPTED;
 }
/* There's no hash */
key->number=0;
key->name= ((structapfs_drec_key*)raw)->name;
 }
break;
caseAPFS_TYPE_XATTR:
if (size<sizeof(structapfs_xattr_key) +1||
*((char*)raw+size-1) !=0) {
/* xattr name must have NULL-termination */
apfs_err(NULL, "invalid xattr key (%d)", size);
return-EFSCORRUPTED;
 }
key->number=0;
key->name= ((structapfs_xattr_key*)raw)->name;
break;
caseAPFS_TYPE_FILE_EXTENT:
if (size!=sizeof(structapfs_file_extent_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
key->number=le64_to_cpu(
 ((structapfs_file_extent_key*)raw)->logical_addr);
key->name=NULL;
break;
caseAPFS_TYPE_SIBLING_LINK:
if (size!=sizeof(structapfs_sibling_link_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
key->number=le64_to_cpu(
 ((structapfs_sibling_link_key*)raw)->sibling_id);
key->name=NULL;
break;
default:
key->number=0;
key->name=NULL;
break;
 }

return0;
}

intapfs_read_fext_key(void*raw, intsize, structapfs_key*key)
{
structapfs_fext_tree_key*raw_key;

if (size!=sizeof(*raw_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
raw_key=raw;

key->id=le64_to_cpu(raw_key->private_id);
key->type=0;
key->number=le64_to_cpu(raw_key->logical_addr);
key->name=NULL;
return0;
}

/**
 * apfs_read_free_queue_key - Parse an on-disk free queue key
 * @raw: pointer to the raw key
 * @size: size of the raw key
 * @key: apfs_key structure to store the result
 *
 * Returns 0 on success, or a negative error code otherwise.
 */
intapfs_read_free_queue_key(void*raw, intsize, structapfs_key*key)
{
structapfs_spaceman_free_queue_key*raw_key;

if (size!=sizeof(*raw_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
raw_key=raw;

key->id=le64_to_cpu(raw_key->sfqk_xid);
key->type=0;
key->number=le64_to_cpu(raw_key->sfqk_paddr);
key->name=NULL;

return0;
}

/**
 * apfs_read_omap_key - Parse an on-disk object map key
 * @raw: pointer to the raw key
 * @size: size of the raw key
 * @key: apfs_key structure to store the result
 *
 * Returns 0 on success, or a negative error code otherwise.
 */
intapfs_read_omap_key(void*raw, intsize, structapfs_key*key)
{
structapfs_omap_key*raw_key;

if (size!=sizeof(*raw_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
raw_key=raw;

key->id=le64_to_cpu(raw_key->ok_oid);
key->type=0;
key->number=le64_to_cpu(raw_key->ok_xid);
key->name=NULL;

return0;
}

/**
 * apfs_read_extentref_key - Parse an on-disk extent reference tree key
 * @raw: pointer to the raw key
 * @size: size of the raw key
 * @key: apfs_key structure to store the result
 *
 * Returns 0 on success, or a negative error code otherwise.
 */
intapfs_read_extentref_key(void*raw, intsize, structapfs_key*key)
{
if (size!=sizeof(structapfs_phys_ext_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
key->id=apfs_cat_cnid((structapfs_key_header*)raw);
key->type=apfs_cat_type((structapfs_key_header*)raw);
key->number=0;
key->name=NULL;
return0;
}

intapfs_read_snap_meta_key(void*raw, intsize, structapfs_key*key)
{
if (size<sizeof(structapfs_key_header)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
key->id=apfs_cat_cnid((structapfs_key_header*)raw);
key->type=apfs_cat_type((structapfs_key_header*)raw);
key->number=0;

switch (key->type) {
caseAPFS_TYPE_SNAP_METADATA:
if (size!=sizeof(structapfs_snap_metadata_key)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
key->name=NULL;
return0;
caseAPFS_TYPE_SNAP_NAME:
if (size<sizeof(structapfs_snap_name_key) +1||*((char*)raw+size-1) !=0) {
/* snapshot name must have NULL-termination */
apfs_err(NULL, "invalid snap name key (%d)", size);
return-EFSCORRUPTED;
 }
key->name= ((structapfs_snap_name_key*)raw)->name;
return0;
default:
return-EFSCORRUPTED;
 }
}

intapfs_read_omap_snap_key(void*raw, intsize, structapfs_key*key)
{
__le64*xid=NULL;

if (size!=sizeof(*xid)) {
apfs_err(NULL, "bad key length (%d)", size);
return-EFSCORRUPTED;
 }
xid=raw;

key->id=le64_to_cpup(xid);
key->number=0;
key->name=NULL;
key->type=0;
return0;
}

/**
 * apfs_init_drec_key - Initialize an in-memory key for a dentry query
 * @sb: filesystem superblock
 * @ino: inode number of the parent directory
 * @name: filename (NULL for a multiple query)
 * @name_len: filename length (0 if NULL)
 * @key: apfs_key structure to initialize
 */
voidapfs_init_drec_key(structsuper_block*sb, u64ino, constchar*name,
unsigned intname_len, structapfs_key*key)
{
structapfs_unicursorcursor;
boolcase_fold=apfs_is_case_insensitive(sb);
u32hash=0xFFFFFFFF;

key->id=ino;
key->type=APFS_TYPE_DIR_REC;
if (!apfs_is_normalization_insensitive(sb)) {
key->name=name;
key->number=0;
return;
 }

/* To respect normalization, queries can only consider the hash */
key->name=NULL;

if (!name) {
key->number=0;
return;
 }

apfs_init_unicursor(&cursor, name, name_len);

while (1) {
unicode_tutf32;

utf32=apfs_normalize_next(&cursor, case_fold);
if (!utf32)
break;

hash=crc32c(hash, &utf32, sizeof(utf32));
 }

/* The filename length doesn't matter, so it's left as zero */
key->number=hash << APFS_DREC_HASH_SHIFT;
}