cmcheck.c

Go to the documentation of this file.

/*
 * PROJECT:     ReactOS Kernel
 * LICENSE:     GPL-2.0-or-later (https://spdx.org/licenses/GPL-2.0-or-later)
 * PURPOSE:     Configuration Manager Library - Registry Validation
 * COPYRIGHT:   Copyright 2022 George Bișoc <george.bisoc@reactos.org>
 */
 
#include "cmlib.h"
#define NDEBUG
#include <debug.h>
 
/* STRUCTURES ****************************************************************/
 
typedef struct _CMP_REGISTRY_STACK_WORK_STATE
{
    ULONG ChildCellIndex;
    HCELL_INDEX Parent;
    HCELL_INDEX Current;
    HCELL_INDEX Sibling;
} CMP_REGISTRY_STACK_WORK_STATE, *PCMP_REGISTRY_STACK_WORK_STATE;
 
/* DEFINES  ******************************************************************/
 
#define GET_HHIVE(CmHive) (&((CmHive)->Hive))
#define GET_HHIVE_ROOT_CELL(Hive) ((Hive)->BaseBlock->RootCell)
#define GET_HHIVE_BIN(Hive, StorageIndex, BlockIndex) ((PHBIN)Hive->Storage[StorageIndex].BlockList[BlockIndex].BinAddress)
#define GET_CELL_BIN(Bin) ((PHCELL)((PUCHAR)Bin + sizeof(HBIN)))
 
#define IS_CELL_VOLATILE(Cell) (HvGetCellType(Cell) == Volatile)
 
#if !defined(CMLIB_HOST) && !defined(_BLDR_)
extern PCMHIVE CmiVolatileHive;
#endif
 
#define CMP_PRIOR_STACK 1
#define CMP_REGISTRY_MAX_LEVELS_TREE_DEPTH 512
 
#define CMP_KEY_SIZE_THRESHOLD 0x45C
#define CMP_VOLATILE_LIST_UNINTIALIZED 0xBAADF00D
 
/* PRIVATE FUNCTIONS **********************************************************/
 
static
BOOLEAN
CmpValidateLexicalOrder(
    _In_ PHHIVE Hive,
    _In_ HCELL_INDEX Child,
    _In_ HCELL_INDEX Sibling)
{
    LONG Result;
    UNICODE_STRING ChildString, SiblingString;
    PCM_KEY_NODE ChildNode, SiblingNode;
 
    PAGED_CODE();
 
    /* Obtain the child node */
    ChildNode = (PCM_KEY_NODE)HvGetCell(Hive, Child);
    if (!ChildNode)
    {
        /* Couldn't get the child node, bail out */
        DPRINT1("Failed to get the child node\n");
        return FALSE;
    }
 
    /* Obtain the sibling node */
    SiblingNode = (PCM_KEY_NODE)HvGetCell(Hive, Sibling);
    if (!SiblingNode)
    {
        /* Couldn't get the sibling node, bail out */
        DPRINT1("Failed to get the sibling node\n");
        return FALSE;
    }
 
    /* CASE 1: Two distinct non-compressed Unicode names */
    if ((ChildNode->Flags & KEY_COMP_NAME) == 0 &&
        (SiblingNode->Flags & KEY_COMP_NAME) == 0)
    {
        /* Build the sibling string */
        SiblingString.Buffer = &(SiblingNode->Name[0]);
        SiblingString.Length = SiblingNode->NameLength;
        SiblingString.MaximumLength = SiblingNode->NameLength;
 
        /* Build the child string */
        ChildString.Buffer = &(ChildNode->Name[0]);
        ChildString.Length = ChildNode->NameLength;
        ChildString.MaximumLength = ChildNode->NameLength;
 
        Result = RtlCompareUnicodeString(&SiblingString, &ChildString, TRUE);
        if (Result >= 0)
        {
            DPRINT1("The sibling node name is greater or equal to that of the child\n");
            return FALSE;
        }
    }
 
    /* CASE 2: Both compressed Unicode names */
    if ((ChildNode->Flags & KEY_COMP_NAME) &&
        (SiblingNode->Flags & KEY_COMP_NAME))
    {
        /* FIXME: Checks for two compressed names not implemented yet */
        DPRINT("Lexicographical order checks for two compressed names is UNIMPLEMENTED, assume the key is healthy...\n");
        return TRUE;
    }
 
    /* CASE 3: The child name is compressed but the sibling is not */
    if ((ChildNode->Flags & KEY_COMP_NAME) &&
        (SiblingNode->Flags & KEY_COMP_NAME) == 0)
    {
        SiblingString.Buffer = &(SiblingNode->Name[0]);
        SiblingString.Length = SiblingNode->NameLength;
        SiblingString.MaximumLength = SiblingNode->NameLength;
        Result = CmpCompareCompressedName(&SiblingString,
                                          ChildNode->Name,
                                          ChildNode->NameLength);
        if (Result >= 0)
        {
            DPRINT1("The sibling node name is greater or equal to that of the compressed child\n");
            return FALSE;
        }
    }
 
    /* CASE 4: The sibling name is compressed but the child is not */
    if ((SiblingNode->Flags & KEY_COMP_NAME) &&
        (ChildNode->Flags & KEY_COMP_NAME) == 0)
    {
        ChildString.Buffer = &(ChildNode->Name[0]);
        ChildString.Length = ChildNode->NameLength;
        ChildString.MaximumLength = ChildNode->NameLength;
        Result = CmpCompareCompressedName(&ChildString,
                                          SiblingNode->Name,
                                          SiblingNode->NameLength);
        if (Result <= 0)
        {
            DPRINT1("The compressed sibling node name is lesser or equal to that of the child\n");
            return FALSE;
        }
    }
 
    /*
     * One of the cases above has met the conditions
     * successfully, the lexicographical order is legal.
     */
    return TRUE;
}
 
static
CM_CHECK_REGISTRY_STATUS
CmpValidateClass(
    _In_ PHHIVE Hive,
    _In_ HCELL_INDEX CurrentCell,
    _Inout_ PCELL_DATA CellData)
{
    ULONG ClassLength;
    HCELL_INDEX ClassCell;
 
    PAGED_CODE();
 
    ASSERT(CurrentCell != HCELL_NIL);
    ASSERT(CellData);
 
    /* Cache the class cell and validate it (if any) */
    ClassCell = CellData->u.KeyNode.Class;
    ClassLength = CellData->u.KeyNode.ClassLength;
    if (ClassLength > 0)
    {
        if (ClassCell == HCELL_NIL)
        {
            /*
             * Somebody has freed the class but left the
             * length as is, reset it.
             */
            DPRINT1("The key node class is NIL but the class length is not 0, resetting it\n");
            HvMarkCellDirty(Hive, CurrentCell, FALSE);
            CellData->u.KeyNode.ClassLength = 0;
            return CM_CHECK_REGISTRY_GOOD;
        }
 
        if (!HvIsCellAllocated(Hive, ClassCell))
        {
            DPRINT1("The key class is not allocated\n");
            return CM_CHECK_REGISTRY_KEY_CLASS_UNALLOCATED;
        }
    }
 
    return CM_CHECK_REGISTRY_GOOD;
}
 
static
CM_CHECK_REGISTRY_STATUS
CmpValidateValueListByCount(
    _In_ PHHIVE Hive,
    _In_ HCELL_INDEX CurrentCell,
    _In_ ULONG ListCount,
    _In_ PCELL_DATA ValueListData,
    _Out_ PULONG ValuesRemoved,
    _In_ BOOLEAN FixHive)
{
    ULONG ValueDataSize;
    ULONG ListCountIndex;
    ULONG DataSize;
    HCELL_INDEX DataCell;
    HCELL_INDEX ValueCell;
    PCELL_DATA ValueData;
    ULONG ValueNameLength, TotalValueNameLength;
 
    PAGED_CODE();
 
    ASSERT(ValueListData);
    ASSERT(ListCount != 0);
 
    /* Assume we haven't removed any value counts for now */
    *ValuesRemoved = 0;
 
    /*
     * Begin looping each value in the list and
     * validate it accordingly.
     */
    ListCountIndex = 0;
    while (ListCountIndex < ListCount)
    {
        ValueCell = ValueListData->u.KeyList[ListCountIndex];
        if (ValueCell == HCELL_NIL)
        {
            if (!CmpRepairValueListCount(Hive,
                                         CurrentCell,
                                         ListCountIndex,
                                         ValueListData,
                                         FixHive))
            {
                DPRINT1("The value cell is NIL (at index %u, list count %u)\n",
                        ListCountIndex, ListCount);
                return CM_CHECK_REGISTRY_VALUE_CELL_NIL;
            }
 
            /* Decrease the list count and go to the next value */
            ListCount--;
            *ValuesRemoved++;
            DPRINT1("Damaged value removed, continuing with the next value...\n");
            continue;
        }
 
        if (!HvIsCellAllocated(Hive, ValueCell))
        {
            if (!CmpRepairValueListCount(Hive,
                                         CurrentCell,
                                         ListCountIndex,
                                         ValueListData,
                                         FixHive))
            {
                DPRINT1("The value cell is not allocated (at index %u, list count %u)\n",
                        ListCountIndex, ListCount);
                return CM_CHECK_REGISTRY_VALUE_CELL_UNALLOCATED;
            }
 
            /* Decrease the list count and go to the next value */
            ListCount--;
            *ValuesRemoved++;
            DPRINT1("Damaged value removed, continuing with the next value...\n");
            continue;
        }
 
        /* Obtain a cell data from this value */
        ValueData = (PCELL_DATA)HvGetCell(Hive, ValueCell);
        if (!ValueData)
        {
            DPRINT1("Cell data of the value cell not found (at index %u, value count %u)\n",
                    ListCountIndex, ListCount);
            return CM_CHECK_REGISTRY_VALUE_CELL_DATA_NOT_FOUND;
        }
 
        /* Check that the value size is sane */
        ValueDataSize = HvGetCellSize(Hive, ValueData);
        ValueNameLength = ValueData->u.KeyValue.NameLength;
        TotalValueNameLength = ValueNameLength + FIELD_OFFSET(CM_KEY_VALUE, Name);
        if (TotalValueNameLength > ValueDataSize)
        {
            if (!CmpRepairValueListCount(Hive,
                                         CurrentCell,
                                         ListCountIndex,
                                         ValueListData,
                                         FixHive))
            {
                DPRINT1("The total size is bigger than the actual cell size (total size %u, cell size %u, at index %u)\n",
                        TotalValueNameLength, ValueDataSize, ListCountIndex);
                return CM_CHECK_REGISTRY_VALUE_CELL_SIZE_NOT_SANE;
            }
 
            /* Decrease the list count and go to the next value */
            ListCount--;
            *ValuesRemoved++;
            DPRINT1("Damaged value removed, continuing with the next value...\n");
            continue;
        }
 
        /*
         * The value cell has a sane size. The last thing
         * to validate is the actual data of the value cell.
         * That is, we want that the data itself and length
         * are consistent. Technically speaking, value keys
         * that are small are directly located in the value
         * cell and it's built-in, in other words, the data
         * is immediately present in the cell so we don't have
         * to bother validating them since they're alright on
         * their own. This can't be said the same about normal
         * values though.
         */
        DataCell = ValueData->u.KeyValue.Data;
        if (!CmpIsKeyValueSmall(&DataSize, ValueData->u.KeyValue.DataLength))
        {
            /* Validate the actual data based on size */
            if (DataSize == 0)
            {
                if (DataCell != HCELL_NIL)
                {
                    if (!CmpRepairValueListCount(Hive,
                                                 CurrentCell,
                                                 ListCountIndex,
                                                 ValueListData,
                                                 FixHive))
                    {
                        DPRINT1("The data is not NIL on a 0 length, data is corrupt\n");
                        return CM_CHECK_REGISTRY_CORRUPT_VALUE_DATA;
                    }
 
                    /* Decrease the list count and go to the next value */
                    ListCount--;
                    *ValuesRemoved++;
                    DPRINT1("Damaged value removed, continuing with the next value...\n");
                    continue;
                }
            }
            else
            {
                if (!HvIsCellAllocated(Hive, DataCell))
                {
                    if (!CmpRepairValueListCount(Hive,
                                                 CurrentCell,
                                                 ListCountIndex,
                                                 ValueListData,
                                                 FixHive))
                    {
                        DPRINT1("The data is not NIL on a 0 length, data is corrupt\n");
                        return CM_CHECK_REGISTRY_DATA_CELL_NOT_ALLOCATED;
                    }
 
                    /* Decrease the list count and go to the next value */
                    ListCount--;
                    *ValuesRemoved++;
                    DPRINT1("Damaged value removed, continuing with the next value...\n");
                    continue;
                }
            }
 
            /* FIXME: Big values not supported yet */
            ASSERT_VALUE_BIG(Hive, DataSize);
        }
 
        /* Is the signature valid? */
        if (ValueData->u.KeyValue.Signature != CM_KEY_VALUE_SIGNATURE)
        {
            if (!CmpRepairValueListCount(Hive,
                                         CurrentCell,
                                         ListCountIndex,
                                         ValueListData,
                                         FixHive))
            {
                DPRINT1("The key value signature is invalid\n");
                return CM_CHECK_REGISTRY_BAD_KEY_VALUE_SIGNATURE;
            }
 
            /* Decrease the list count and go to the next value */
            ListCount--;
            *ValuesRemoved++;
            DPRINT1("Damaged value removed, continuing with the next value...\n");
            continue;
        }
 
        /* Advance to the next value */
        ListCountIndex++;
    }
 
    return CM_CHECK_REGISTRY_GOOD;
}
 
static
CM_CHECK_REGISTRY_STATUS
CmpValidateValueList(
    _In_ PHHIVE Hive,
    _In_ HCELL_INDEX CurrentCell,
    _Inout_ PCELL_DATA CellData,
    _In_ BOOLEAN FixHive)
{
    CM_CHECK_REGISTRY_STATUS CmStatusCode;
    ULONG TotalValueLength, ValueSize;
    ULONG ValueListCount;
    ULONG ValuesRemoved;
    HCELL_INDEX ValueListCell;
    PCELL_DATA ValueListData;
 
    PAGED_CODE();
 
    ASSERT(CurrentCell != HCELL_NIL);
    ASSERT(CellData);
 
    /* Cache the value list and validate it */
    ValueListCell = CellData->u.KeyNode.ValueList.List;
    ValueListCount = CellData->u.KeyNode.ValueList.Count;
    if (ValueListCount > 0)
    {
        if (!HvIsCellAllocated(Hive, ValueListCell))
        {
            DPRINT1("The value list is not allocated\n");
            return CM_CHECK_REGISTRY_VALUE_LIST_UNALLOCATED;
        }
 
        /* Obtain cell data from the value list cell */
        ValueListData = (PCELL_DATA)HvGetCell(Hive, ValueListCell);
        if (!ValueListData)
        {
            DPRINT1("Could not get cell data from the value list\n");
            return CM_CHECK_REGISTRY_VALUE_LIST_DATA_NOT_FOUND;
        }
 
        /*
         * Cache the value size and total length and
         * assert ourselves this is a sane value list
         * to begin with.
         */
        ValueSize = HvGetCellSize(Hive, ValueListData);
        TotalValueLength = ValueListCount * sizeof(HCELL_INDEX);
        if (TotalValueLength > ValueSize)
        {
            DPRINT1("The value list is bigger than the cell (value list size %u, cell size %u)\n",
                    TotalValueLength, ValueSize);
            return CM_CHECK_REGISTRY_VALUE_LIST_SIZE_NOT_SANE;
        }
 
        /*
         * The value list is sane, now we would
         * need to validate the actual list
         * by its count.
         */
        CmStatusCode = CmpValidateValueListByCount(Hive,
                                                   CurrentCell,
                                                   ValueListCount,
                                                   ValueListData,
                                                   &ValuesRemoved,
                                                   FixHive);
        if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
        {
            DPRINT1("One of the values is corrupt and couldn't be repaired\n");
            return CmStatusCode;
        }
 
        /* Log how much values have been removed */
        if (ValuesRemoved > 0)
        {
            DPRINT1("%u values removed in the list\n", ValuesRemoved);
        }
    }
 
    return CM_CHECK_REGISTRY_GOOD;
}
 
static
CM_CHECK_REGISTRY_STATUS
CmpValidateSubKeyList(
    _In_ PHHIVE Hive,
    _In_ HCELL_INDEX CurrentCell,
    _Inout_ PCELL_DATA CellData,
    _In_ BOOLEAN FixHive,
    _Out_ PBOOLEAN DoRepair)
{
    ULONG SubKeyCounts;
    HCELL_INDEX KeyIndexCell, SubKeysListCell;
    PCM_KEY_INDEX RootKeyIndex, LeafKeyIndex;
    ULONG RootIndex;
    ULONG TotalLeafCount;
 
    PAGED_CODE();
 
    ASSERT(CurrentCell != HCELL_NIL);
    ASSERT(CellData);
 
    RootKeyIndex = NULL;
    LeafKeyIndex = NULL;
    TotalLeafCount = 0;
 
    /*
     * Assume for now that the caller should not
     * do any kind of repairs on the subkeys list,
     * unless explicitly given the consent by us.
     */
    *DoRepair = FALSE;
 
    /*
     * For volatile keys they have data that can
     * fluctuate and change on the fly so there's
     * pretty much nothing that we can validate those.
     * But still, we would want that the volatile key
     * is not damaged by external factors, like e.g.,
     * having stable keys on a volatile space.
     */
    if (IS_CELL_VOLATILE(CurrentCell))
    {
        if (CellData->u.KeyNode.SubKeyCounts[Stable] != 0)
        {
            DPRINT1("The volatile key has stable subkeys\n");
            return CM_CHECK_REGISTRY_STABLE_KEYS_ON_VOLATILE;
        }
 
        return CM_CHECK_REGISTRY_GOOD;
    }
 
    /*
     * This is not a volatile key, cache the subkeys list
     * and validate it.
     */
    SubKeysListCell = CellData->u.KeyNode.SubKeyLists[Stable];
    SubKeyCounts = CellData->u.KeyNode.SubKeyCounts[Stable];
    if (SubKeyCounts > 0)
    {
        if (!HvIsCellAllocated(Hive, SubKeysListCell))
        {
            DPRINT1("The subkeys list cell is not allocated\n");
            *DoRepair = TRUE;
            return CM_CHECK_REGISTRY_SUBKEYS_LIST_UNALLOCATED;
        }
 
        /* Obtain a root index and validate it */
        RootKeyIndex = (PCM_KEY_INDEX)HvGetCell(Hive, SubKeysListCell);
        if (!RootKeyIndex)
        {
            DPRINT1("Could not get the root key index of the subkeys list cell\n");
            return CM_CHECK_REGISTRY_CORRUPT_SUBKEYS_INDEX;
        }
 
        /*
         * For simple, fast and hashed leaves we would want
         * that the corresponding root index count matches with
         * that of the subkey counts itself. If this is not the
         * case we can isolate this problem and fix the count.
         */
        if (RootKeyIndex->Signature == CM_KEY_INDEX_LEAF ||
            RootKeyIndex->Signature == CM_KEY_FAST_LEAF ||
            RootKeyIndex->Signature == CM_KEY_HASH_LEAF)
        {
            if (SubKeyCounts != RootKeyIndex->Count)
            {
                if (!CmpRepairSubKeyCounts(Hive,
                                           CurrentCell,
                                           RootKeyIndex->Count,
                                           CellData,
                                           FixHive))
                {
                    DPRINT1("The subkeys list has invalid count (subkeys count %u, root key index count %u)\n",
                            SubKeyCounts, RootKeyIndex->Count);
                    return CM_CHECK_REGISTRY_BAD_SUBKEY_COUNT;
                }
            }
 
            return CM_CHECK_REGISTRY_GOOD;
        }
 
        /*
         * The root index is not a leaf, check if the index
         * is an actual root then.
         */
        if (RootKeyIndex->Signature == CM_KEY_INDEX_ROOT)
        {
            /*
             * For the root we have to loop each leaf
             * from it and increase the total leaf count
             * in the root after we determined the validity
             * of a leaf. This way we can see if the subcount
             * matches with that of the subkeys list count.
             */
            for (RootIndex = 0; RootIndex < RootKeyIndex->Count; RootIndex++)
            {
                KeyIndexCell = RootKeyIndex->List[RootIndex];
                if (!HvIsCellAllocated(Hive, KeyIndexCell))
                {
                    DPRINT1("The key index cell is not allocated at index %u\n", RootIndex);
                    *DoRepair = TRUE;
                    return CM_CHECK_REGISTRY_KEY_INDEX_CELL_UNALLOCATED;
                }
 
                /* Obtain a leaf from the root */
                LeafKeyIndex = (PCM_KEY_INDEX)HvGetCell(Hive, KeyIndexCell);
                if (!LeafKeyIndex)
                {
                    DPRINT1("The root key index's signature is invalid!\n");
                    return CM_CHECK_REGISTRY_CORRUPT_LEAF_ON_ROOT;
                }
 
                /* Check that the leaf has valid signature */
                if (LeafKeyIndex->Signature != CM_KEY_INDEX_LEAF &&
                    LeafKeyIndex->Signature != CM_KEY_FAST_LEAF &&
                    LeafKeyIndex->Signature != CM_KEY_HASH_LEAF)
                {
                    DPRINT1("The leaf's signature is invalid!\n");
                    *DoRepair = TRUE;
                    return CM_CHECK_REGISTRY_CORRUPT_LEAF_SIGNATURE;
                }
 
                /* Add up the count of the leaf */
                TotalLeafCount += LeafKeyIndex->Count;
            }
 
            /*
             * We have built up the total leaf count,
             * we have to determine this count is exactly
             * the same as the subkeys list count. Otherwise
             * just fix it.
             */
            if (SubKeyCounts != TotalLeafCount)
            {
                if (!CmpRepairSubKeyCounts(Hive,
                                           CurrentCell,
                                           TotalLeafCount,
                                           CellData,
                                           FixHive))
                {
                    DPRINT1("The subkeys list has invalid count (subkeys count %u, total leaf count %u)\n",
                            SubKeyCounts, TotalLeafCount);
                    return CM_CHECK_REGISTRY_BAD_SUBKEY_COUNT;
                }
            }
 
            return CM_CHECK_REGISTRY_GOOD;
        }
 
        /*
         * None of the valid signatures match with that of
         * the root key index. By definition, the whole subkey
         * list is total toast.
         */
        DPRINT1("The root key index's signature is invalid\n");
        *DoRepair = TRUE;
        return CM_CHECK_REGISTRY_CORRUPT_KEY_INDEX_SIGNATURE;
    }
 
    /* If we reach here then this key has no subkeys */
    return CM_CHECK_REGISTRY_GOOD;
}
 
static
VOID
CmpPurgeVolatiles(
    _In_ PHHIVE Hive,
    _In_ HCELL_INDEX CurrentCell,
    _Inout_ PCELL_DATA CellData,
    _In_ ULONG Flags)
{
    PAGED_CODE();
 
    ASSERT(CellData);
 
    /* Did the caller ask to purge volatiles? */
    if (((Flags & CM_CHECK_REGISTRY_PURGE_VOLATILES) ||
         (Flags & CM_CHECK_REGISTRY_BOOTLOADER_PURGE_VOLATILES)) &&
        (CellData->u.KeyNode.SubKeyCounts[Volatile] != 0))
    {
        /*
         * OK, the caller wants them cleaned from this
         * hive. For XP Beta 1 or newer hives, we unintialize
         * the whole volatile subkeys list. For older hives,
         * we just do a cleanup.
         */
#if !defined(_BLDR_)
        HvMarkCellDirty(Hive, CurrentCell, FALSE);
#endif
        if ((Flags & CM_CHECK_REGISTRY_BOOTLOADER_PURGE_VOLATILES) &&
            (Hive->Version >= HSYS_WHISTLER_BETA1))
        {
            CellData->u.KeyNode.SubKeyLists[Volatile] = CMP_VOLATILE_LIST_UNINTIALIZED;
        }
        else
        {
            CellData->u.KeyNode.SubKeyLists[Volatile] = HCELL_NIL;
        }
 
        /* Clear the count */
        CellData->u.KeyNode.SubKeyCounts[Volatile] = 0;
    }
}
 
static
CM_CHECK_REGISTRY_STATUS
CmpValidateKey(
    _In_ PHHIVE Hive,
    _In_ BOOLEAN SecurityDefaulted,
    _In_ HCELL_INDEX ParentCell,
    _In_ HCELL_INDEX CurrentCell,
    _In_ ULONG Flags,
    _In_ BOOLEAN FixHive)
{
    CM_CHECK_REGISTRY_STATUS CmStatusCode;
    PCELL_DATA CellData;
    ULONG CellSize;
    BOOLEAN DoSubkeysRepair;
    ULONG TotalKeyNameLength, NameLength;
 
    PAGED_CODE();
 
    /* The current key cell mustn't be NIL here! */
    ASSERT(CurrentCell != HCELL_NIL);
 
    /* TODO: To be removed once we support security caching in Cm */
    UNREFERENCED_PARAMETER(SecurityDefaulted);
 
    /*
     * We must ensure that the key cell is
     * allocated in the first place before
     * we go further.
     */
    if (!HvIsCellAllocated(Hive, CurrentCell))
    {
        DPRINT1("The key cell is not allocated\n");
        return CM_CHECK_REGISTRY_KEY_CELL_NOT_ALLOCATED;
    }
 
    /* Obtain cell data from it */
    CellData = (PCELL_DATA)HvGetCell(Hive, CurrentCell);
    if (!CellData)
    {
        DPRINT1("Could not get cell data from the cell\n");
        return CM_CHECK_REGISTRY_CELL_DATA_NOT_FOUND;
    }
 
    /* Get the size of this cell and validate its size */
    CellSize = HvGetCellSize(Hive, CellData);
    if (CellSize > CMP_KEY_SIZE_THRESHOLD)
    {
        DPRINT1("The cell size is above the threshold size (size %u)\n", CellSize);
        return CM_CHECK_REGISTRY_CELL_SIZE_NOT_SANE;
    }
 
    /*
     * The cell size is OK but we must ensure
     * the key is not bigger than the container
     * of the cell.
     */
    NameLength = CellData->u.KeyNode.NameLength;
    if (NameLength == 0)
    {
        DPRINT1("The key node name length is 0!\n");
        return CM_CHECK_REGISTRY_KEY_NAME_LENGTH_ZERO;
    }
 
    TotalKeyNameLength = NameLength + FIELD_OFFSET(CM_KEY_NODE, Name);
    if (TotalKeyNameLength > CellSize)
    {
        DPRINT1("The key is too big than the cell (key size %u, cell size %u)\n",
                TotalKeyNameLength, CellSize);
        return CM_CHECK_REGISTRY_KEY_TOO_BIG_THAN_CELL;
    }
 
    /* Is the parent cell consistent? */
    if (ParentCell != HCELL_NIL &&
        ParentCell != CellData->u.KeyNode.Parent)
    {
        if (!CmpRepairParentNode(Hive,
                                 CurrentCell,
                                 ParentCell,
                                 CellData,
                                 FixHive))
        {
            DPRINT1("The parent key node doesn't point to the actual parent\n");
            return CM_CHECK_REGISTRY_BAD_KEY_NODE_PARENT;
        }
    }
 
    /* Is the key node signature valid? */
    if (CellData->u.KeyNode.Signature != CM_KEY_NODE_SIGNATURE)
    {
        if (!CmpRepairKeyNodeSignature(Hive,
                                       CurrentCell,
                                       CellData,
                                       FixHive))
        {
            DPRINT1("The parent key node signature is not valid\n");
            return CM_CHECK_REGISTRY_BAD_KEY_NODE_SIGNATURE;
        }
    }
 
    /*
     * FIXME: Security cell checks have to be implemented here
     * once we properly and reliably implement security caching
     * in the kernel.
     */
 
    /* Validate the class */
    CmStatusCode = CmpValidateClass(Hive, CurrentCell, CellData);
    if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
    {
        if (!CmpRepairClassOfNodeKey(Hive,
                                     CurrentCell,
                                     CellData,
                                     FixHive))
        {
            DPRINT1("Failed to repair the hive, the cell class is not valid\n");
            return CmStatusCode;
        }
    }
 
    /* Validate the value list */
    CmStatusCode = CmpValidateValueList(Hive, CurrentCell, CellData, FixHive);
    if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
    {
        /*
         * It happens that a certain value in the list
         * is so bad like we couldn't map a cell data from it
         * or the list itself is toast. In such cases what we
         * can do here is to do a "value list sacrifice", aka
         * purge the whole list.
         */
        if (!CmpRepairValueList(Hive, CurrentCell, FixHive))
        {
            DPRINT1("Failed to repair the hive, the value list is corrupt\n");
            return CmStatusCode;
        }
    }
 
    /* Validate the subkeys list */
    CmStatusCode = CmpValidateSubKeyList(Hive, CurrentCell, CellData, FixHive, &DoSubkeysRepair);
    if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
    {
        /*
         * The subkeys list is in trouble. Worse when the actual
         * subkey list is so severed this key is also kaput on itself.
         */
        if (!DoSubkeysRepair)
        {
            DPRINT1("The subkeys list is totally corrupt, can't repair\n");
            return CmStatusCode;
        }
 
        /*
         * OK, there's still some salvation for this key.
         * Purge the whole subkeys list in order to fix it.
         */
        if (!CmpRepairSubKeyList(Hive,
                                 CurrentCell,
                                 CellData,
                                 FixHive))
        {
            DPRINT1("Failed to repair the hive, the subkeys list is corrupt!\n");
            return CmStatusCode;
        }
    }
 
    /* Purge volatile data if needed */
    CmpPurgeVolatiles(Hive, CurrentCell, CellData, Flags);
    return CM_CHECK_REGISTRY_GOOD;
}
 
static
CM_CHECK_REGISTRY_STATUS
CmpValidateRegistryInternal(
    _In_ PHHIVE Hive,
    _In_ ULONG Flags,
    _In_ BOOLEAN SecurityDefaulted,
    _In_ BOOLEAN FixHive)
{
    CM_CHECK_REGISTRY_STATUS CmStatusCode;
    PCMP_REGISTRY_STACK_WORK_STATE WorkState;
    HCELL_INDEX RootCell, ParentCell, CurrentCell;
    HCELL_INDEX ChildSubKeyCell;
    PCM_KEY_NODE KeyNode;
    ULONG WorkStateLength;
    LONG StackDepth;
    BOOLEAN AllChildrenChecked;
 
    PAGED_CODE();
 
    ASSERT(Hive);
 
    /*
     * Allocate some memory blocks for the stack
     * state structure. We'll be using it to walk
     * down the registry hive tree in a recursive
     * way without worrying that we explode the
     * kernel stack in the most gruesome and gross
     * ways.
     */
    WorkStateLength = CMP_REGISTRY_MAX_LEVELS_TREE_DEPTH * sizeof(CMP_REGISTRY_STACK_WORK_STATE);
    WorkState = CmpAllocate(WorkStateLength,
                            TRUE,
                            TAG_REGISTRY_STACK);
    if (!WorkState)
    {
        DPRINT1("Couldn't allocate memory for registry stack work state\n");
        return CM_CHECK_REGISTRY_ALLOCATE_MEM_STACK_FAIL;
    }
 
    /* Obtain the root cell of the hive */
    RootCell = GET_HHIVE_ROOT_CELL(Hive);
    if (RootCell == HCELL_NIL)
    {
        DPRINT1("Couldn't get the root cell of the hive\n");
        CmpFree(WorkState, WorkStateLength);
        return CM_CHECK_REGISTRY_ROOT_CELL_NOT_FOUND;
    }
 
RestartValidation:
    /*
     * Prepare the stack state and start from
     * the root cell. Ensure that the root cell
     * itself is OK before we go forward.
     */
    StackDepth = 0;
    WorkState[StackDepth].ChildCellIndex = 0;
    WorkState[StackDepth].Current = RootCell;
    WorkState[StackDepth].Parent = HCELL_NIL;
    WorkState[StackDepth].Sibling = HCELL_NIL;
 
    /*
     * As we start checking the root cell which
     * is the top element of a registry hive,
     * we'll be going to look for child keys
     * in the course of walking down the tree.
     */
    AllChildrenChecked = FALSE;
 
    while (StackDepth >= 0)
    {
        /* Cache the current and parent cells */
        CurrentCell = WorkState[StackDepth].Current;
        ParentCell = WorkState[StackDepth].Parent;
 
        /* Do we have still have children to validate? */
        if (!AllChildrenChecked)
        {
            /* Check that the key is OK */
            CmStatusCode = CmpValidateKey(Hive,
                                          SecurityDefaulted,
                                          ParentCell,
                                          CurrentCell,
                                          Flags,
                                          FixHive);
            if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
            {
                /*
                 * The key cell is damaged. We have to pray and
                 * hope that this is not the root cell as any
                 * damage done to the root is catastrophically
                 * fatal.
                 */
                if (CurrentCell == RootCell)
                {
                    DPRINT1("THE ROOT CELL IS BROKEN\n");
                    CmpFree(WorkState, WorkStateLength);
                    return CmStatusCode;
                }
 
                /*
                 * It is not the root, remove the faulting
                 * damaged cell from the parent so that we
                 * can heal the hive.
                 */
                if (!CmpRepairParentKey(Hive, CurrentCell, ParentCell, FixHive))
                {
                    DPRINT1("The key is corrupt (current cell 0x%x, parent cell 0x%x)\n",
                            CurrentCell, ParentCell);
                    CmpFree(WorkState, WorkStateLength);
                    return CmStatusCode;
                }
 
                /* Damaged cell removed, restart the loop */
                DPRINT1("Hive repaired, restarting the validation loop...\n");
                goto RestartValidation;
            }
 
            /*
             * The key is in perfect shape. If we have advanced
             * the stack depth then check the lexicographical
             * order of the keys as well.
             */
            if (StackDepth > 0 &&
                CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
            {
                if (WorkState[StackDepth - CMP_PRIOR_STACK].Sibling != HCELL_NIL)
                {
                    if (!CmpValidateLexicalOrder(Hive,
                                                 CurrentCell,
                                                 WorkState[StackDepth - CMP_PRIOR_STACK].Sibling))
                    {
                        /*
                         * The lexicographical order is bad,
                         * attempt to heal the hive.
                         */
                        if (!CmpRepairParentKey(Hive, CurrentCell, ParentCell, FixHive))
                        {
                            DPRINT1("The lexicographical order is invalid (sibling 0x%x, current cell 0x%x)\n",
                                    CurrentCell, WorkState[StackDepth - CMP_PRIOR_STACK].Sibling);
                            CmpFree(WorkState, WorkStateLength);
                            return CM_CHECK_REGISTRY_BAD_LEXICOGRAPHICAL_ORDER;
                        }
 
                        /* Damaged cell removed, restart the loop */
                        DPRINT1("Hive repaired, restarting the validation loop...\n");
                        goto RestartValidation;
                    }
                }
 
                /* Assign the prior sibling for upcoming iteration */
                WorkState[StackDepth - CMP_PRIOR_STACK].Sibling = CurrentCell;
            }
        }
 
        /* Obtain a node for this key */
        KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, CurrentCell);
        if (!KeyNode)
        {
            DPRINT1("Couldn't get the node of key (current cell 0x%x)\n", CurrentCell);
            CmpFree(WorkState, WorkStateLength);
            return CM_CHECK_REGISTRY_NODE_NOT_FOUND;
        }
 
        /*
         * If we have processed all the children from this
         * node then adjust the stack depth work state by
         * going back and restart the loop to lookup for
         * the rest of the tree. Acknowledge the code path
         * above that we checked all the children so that
         * we don't have to validate the same subkey again.
         */
        if (WorkState[StackDepth].ChildCellIndex < KeyNode->SubKeyCounts[Stable])
        {
            /*
             * We have children to process, obtain the
             * child subkey in question so that we can
             * cache it later for the next key validation.
             */
            ChildSubKeyCell = CmpFindSubKeyByNumber(Hive, KeyNode, WorkState[StackDepth].ChildCellIndex);
            if (ChildSubKeyCell == HCELL_NIL)
            {
                DPRINT1("Couldn't get the child subkey cell (at stack index %d)\n", StackDepth);
                CmpFree(WorkState, WorkStateLength);
                return CM_CHECK_REGISTRY_SUBKEY_NOT_FOUND;
            }
 
            /*
             * As we got the subkey advance the child index as
             * well as the stack depth work state for the next
             * key validation. However we must ensure since
             * we're advancing the stack depth that we don't
             * go over the maximum tree level depth. A registry
             * tree can be at maximum 512 levels deep.
             *
             * For more information see https://docs.microsoft.com/en-us/windows/win32/sysinfo/registry-element-size-limits.
             */
            WorkState[StackDepth].ChildCellIndex++;
            StackDepth++;
            if (StackDepth >= CMP_REGISTRY_MAX_LEVELS_TREE_DEPTH - 1)
            {
                /*
                 * This registry has so many levels it's
                 * so fat. We don't want to explode our
                 * kernel stack, so just simply bail out...
                 */
                DPRINT1("The registry tree has so many levels!\n");
                CmpFree(WorkState, WorkStateLength);
                return CM_CHECK_REGISTRY_TREE_TOO_MANY_LEVELS;
            }
 
            /* Prepare the work state for the next key */
            WorkState[StackDepth].ChildCellIndex = 0;
            WorkState[StackDepth].Current = ChildSubKeyCell;
            WorkState[StackDepth].Parent = WorkState[StackDepth - CMP_PRIOR_STACK].Current;
            WorkState[StackDepth].Sibling = HCELL_NIL;
 
            /*
             * As we prepared the work state, acknowledge the
             * code path at the top of the loop that we need
             * to process and validate the next child subkey.
             */
            AllChildrenChecked = FALSE;
            continue;
        }
 
        /*
         * We have validated all the child subkeys
         * of the node. Decrease the stack depth
         * and tell the above code we looked for all
         * children so that we don't need to validate
         * the same children again but go for the next
         * node.
         */
        AllChildrenChecked = TRUE;
        StackDepth--;
        continue;
    }
 
    CmpFree(WorkState, WorkStateLength);
    return CM_CHECK_REGISTRY_GOOD;
}
 
/* PUBLIC FUNCTIONS ***********************************************************/
 
CM_CHECK_REGISTRY_STATUS
NTAPI
HvValidateBin(
    _In_ PHHIVE Hive,
    _In_ PHBIN Bin)
{
    PHCELL Cell, Basket;
 
    PAGED_CODE();
 
    ASSERT(Bin);
    ASSERT(Hive);
 
    /* Ensure that this bin we got has valid signature header */
    if (Bin->Signature != HV_HBIN_SIGNATURE)
    {
        DPRINT1("The bin's signature header is corrupt\n");
        return CM_CHECK_REGISTRY_BIN_SIGNATURE_HEADER_CORRUPT;
    }
 
    /*
     * Walk over all the cells from this bin and
     * validate that they're consistent with the bin.
     * Namely we want that each cell from this bin doesn't
     * have a bogus size.
     */
    Basket = (PHCELL)((PUCHAR)Bin + Bin->Size);
    for (Cell = GET_CELL_BIN(Bin);
         Cell < Basket;
         Cell = (PHCELL)((PUCHAR)Cell + abs(Cell->Size)))
    {
        if (IsFreeCell(Cell))
        {
            /*
             * This cell is free, check that
             * the size of this cell is not bogus.
             */
            if (Cell->Size > Bin->Size ||
                Cell->Size == 0)
            {
                /*
                 * This cell has too much free space that
                 * exceeds the boundary of the bin size.
                 * Otherwise the cell doesn't have actual
                 * free space (aka Size == 0) which is a
                 * no go for a bin.
                 */
                DPRINT1("The free cell exceeds the bin size or cell size equal to 0 (cell 0x%p, cell size %d, bin size %u)\n",
                        Cell, Cell->Size, Bin->Size);
                return CM_CHECK_REGISTRY_BAD_FREE_CELL;
            }
        }
        else
        {
            /*
             * This cell is allocated, make sure that
             * the size of this cell is not bogus.
             */
            if (abs(Cell->Size) > Bin->Size)
            {
                /*
                 * This cell allocated too much space
                 * that exceeds the boundary of the
                 * bin size.
                 */
                DPRINT1("The allocated cell exceeds the bin size (cell 0x%p, cell size %d, bin size %u)\n",
                        Cell, abs(Cell->Size), Bin->Size);
                return CM_CHECK_REGISTRY_BAD_ALLOC_CELL;
            }
        }
    }
 
    return CM_CHECK_REGISTRY_GOOD;
}
 
CM_CHECK_REGISTRY_STATUS
NTAPI
HvValidateHive(
    _In_ PHHIVE Hive)
{
    CM_CHECK_REGISTRY_STATUS CmStatusCode;
    ULONG StorageIndex;
    ULONG BlockIndex;
    ULONG StorageLength;
    PHBIN Bin;
 
    PAGED_CODE();
 
    ASSERT(Hive);
 
    /* Is the hive signature valid? */
    if (Hive->Signature != HV_HHIVE_SIGNATURE)
    {
        DPRINT1("Hive's signature corrupted (signature %u)\n", Hive->Signature);
        return CM_CHECK_REGISTRY_HIVE_CORRUPT_SIGNATURE;
    }
 
    /*
     * Now loop each bin in the storage of this
     * hive.
     */
    for (StorageIndex = 0; StorageIndex < Hive->StorageTypeCount; StorageIndex++)
    {
        /* Get the storage length at this index */
        StorageLength = Hive->Storage[StorageIndex].Length;
 
        for (BlockIndex = 0; BlockIndex < StorageLength;)
        {
            /* Go to the next if this bin does not exist */
            if (Hive->Storage[StorageIndex].BlockList[BlockIndex].BinAddress == (ULONG_PTR)NULL)
            {
                continue;
            }
 
            /*
             * Capture this bin and ensure that such
             * bin is within the offset and the size
             * is not bogus.
             */
            Bin = GET_HHIVE_BIN(Hive, StorageIndex, BlockIndex);
            if (Bin->Size > (StorageLength * HBLOCK_SIZE) ||
                (Bin->FileOffset / HBLOCK_SIZE) != BlockIndex)
            {
                DPRINT1("Bin size or offset is corrupt (bin size %u, file offset %u, storage length %u)\n",
                        Bin->Size, Bin->FileOffset, StorageLength);
                return CM_CHECK_REGISTRY_BIN_SIZE_OR_OFFSET_CORRUPT;
            }
 
            /* Validate the rest of the bin */
            CmStatusCode = HvValidateBin(Hive, Bin);
            if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
            {
                DPRINT1("This bin is not valid (bin 0x%p)\n", Bin);
                return CmStatusCode;
            }
 
            /* Go to the next block */
            BlockIndex += Bin->Size / HBLOCK_SIZE;
        }
    }
 
    return CM_CHECK_REGISTRY_GOOD;
}
 
CM_CHECK_REGISTRY_STATUS
NTAPI
CmCheckRegistry(
    _In_ PCMHIVE RegistryHive,
    _In_ ULONG Flags)
{
    CM_CHECK_REGISTRY_STATUS CmStatusCode;
    PHHIVE Hive;
    BOOLEAN ShouldFixHive = FALSE;
 
    PAGED_CODE();
 
    /* Bail out if the caller did not give a hive */
    if (!RegistryHive)
    {
        DPRINT1("No registry hive given for check\n");
        return CM_CHECK_REGISTRY_INVALID_PARAMETER;
    }
 
#if !defined(CMLIB_HOST) && !defined(_BLDR_)
    /*
     * The master hive is the root of the registry,
     * it holds all other hives together. So do not
     * do any validation checks.
     */
    if (RegistryHive == CmiVolatileHive)
    {
        DPRINT("This is master registry hive, don't do anything\n");
        return CM_CHECK_REGISTRY_GOOD;
    }
#endif
 
    /* Bail out if no valid flag is given */
    if (Flags & ~(CM_CHECK_REGISTRY_DONT_PURGE_VOLATILES       |
                  CM_CHECK_REGISTRY_PURGE_VOLATILES            |
                  CM_CHECK_REGISTRY_BOOTLOADER_PURGE_VOLATILES |
                  CM_CHECK_REGISTRY_VALIDATE_HIVE              |
                  CM_CHECK_REGISTRY_FIX_HIVE))
    {
        DPRINT1("Invalid flag for registry check given (flag %u)\n", Flags);
        return CM_CHECK_REGISTRY_INVALID_PARAMETER;
    }
 
    /*
     * Obtain the hive and check if the caller wants
     * that the hive to be validated.
     */
    Hive = GET_HHIVE(RegistryHive);
    if (Flags & CM_CHECK_REGISTRY_VALIDATE_HIVE)
    {
        CmStatusCode = HvValidateHive(Hive);
        if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
        {
            DPRINT1("The hive is not valid (hive 0x%p, check status code %u)\n",
                    Hive, CmStatusCode);
            return CmStatusCode;
        }
    }
 
    /*
     * A registry repair tool such as the ReactOS Check Registry
     * Utility wants the damaged hive to be fixed as we check the
     * target hive.
     */
    if (Flags & CM_CHECK_REGISTRY_FIX_HIVE)
    {
        ShouldFixHive = TRUE;
    }
 
    /*
     * FIXME: Currently ReactOS does not implement security
     * caching algorithms so it's pretty pointless to implement
     * security descriptors validation checks at this moment.
     * When the time comes to implement these, we would need
     * to implement security checks here as well.
     */
 
    /* Call the internal API to do the rest of the work bulk */
    CmStatusCode = CmpValidateRegistryInternal(Hive, Flags, FALSE, ShouldFixHive);
    if (!CM_CHECK_REGISTRY_SUCCESS(CmStatusCode))
    {
        DPRINT1("The hive is not valid (hive 0x%p, check status code %u)\n",
                Hive, CmStatusCode);
        return CmStatusCode;
    }
 
    return CmStatusCode;
}
 
/* EOF */