//depot/main/Base/ntos/inc/hivedata.h#9 - integrate change 19035 (text)
/*++
Copyright (c) 1999 Microsoft Corporation
Module Name:
hivedata.h
Abstract:
This module contains data structures used by the
direct memory loaded hive manager.
Author:
Dragos C. Sambotin (dragoss) 13-Jan-99
Revision History:
--*/
#ifndef __HIVE_DATA__
#define __HIVE_DATA__
//
// ===== Arbitrary Limits Imposed For Sanity =====
//
#define HSANE_CELL_MAX (1024*1024) // 1 megabyte max size for
// a single cell
//
// ===== Tuning =====
#define HBIN_THRESHOLD (HBLOCK_SIZE-512) // If less than threshold
// bytes would be left in
// bin, add another page
#define HLOG_GROW HBLOCK_SIZE // Minimum size to grow log
// by. Can set this up
// if we think it thrashes.
#define HCELL_BIG_ROUND (HBLOCK_SIZE*3) //
// If someone tries to
// allocate a very large
// cell, round it up to
// HBLOCK_SIZE. This is
// the rather arbitrary
// define for "very large"
//
//
// Never shrink the log files smaller than this, this prevents people
// from taking up all the disk space and then being unable to do
// critical registry operations (like logging on to delete some files)
//
#define HLOG_MINSIZE(Hive) \
((Hive)->Cluster * HSECTOR_SIZE * 2)
//
// ===== Basic Structures and Definitions =====
//
// These are same whether on disk or in memory.
//
//
// NOTE: Volatile == storage goes away at reboot
// Stable == Persistent == Not Volatile
//
typedef enum {
Stable = 0,
Volatile = 1
} HSTORAGE_TYPE;
#define HTYPE_COUNT 2
//
// --- HCELL_INDEX ---
//
//
// Handle to a cell -> effectively the "virtual" address of the cell,
// HvMapCell converts this to a "real" address, that is, a memory
// address. Mapping scheme is very much like that standard two level
// page table. No mappings stored in file, they are built up when
// the file is read in. (The INDEX in HCELL_INDEX is historical)
//
// Bit 31 30-21 20-12 11-0
// +----------------------------+
// | T | Table | Block | Offset |
// +----------------------------+
//
// T = Type(1)= 0 for stable ("normal") storage
// 1 for volatile storage
//
// Table(10) = Index into directory of mapping tables, selects a table.
// Each mapping table is an array of HMAP_ENTRY structures.
//
// Block(9) = Index into Table, selects an HMAP_ENTRY. HMAP_ENTRY
// contains address of area in memory that this HCELL_INDEX
// maps to. (Base of memory copy of Block)
//
// Offset(12) = Offset within page, of the Cell header for the cell
// of interest.
//
typedef ULONG HCELL_INDEX;
typedef HCELL_INDEX *PHCELL_INDEX;
#ifdef DRAGOSS_PRIVATE_DEBUG
//#undef PAGE_SIZE
//#define PAGE_SIZE 0x2000
#endif //DRAGOSS_PRIVATE_DEBUG
#define HCELL_NIL ((HCELL_INDEX)(-1))
#define HCELL_TYPE_MASK 0x80000000
#define HCELL_TYPE_SHIFT 31
#define HCELL_TABLE_MASK 0x7fe00000
#define HCELL_TABLE_SHIFT 21
#define HCELL_BLOCK_MASK 0x001ff000
#define HCELL_BLOCK_SHIFT 12
#define HCELL_OFFSET_MASK 0x00000fff
#define HBLOCK_SIZE 0x1000 // LOGICAL block size
// This is the size of one of
// the registry's logical/virtual
// pages. It has no particular
// relationship to page size
// of the machine.
#define HSECTOR_SIZE 0x200 // LOGICAL sector size
#define HSECTOR_COUNT 8 // LOGICAL sectors / LOGICAL Block
#define HSECTOR_PER_PAGE_COUNT (PAGE_SIZE / HSECTOR_SIZE) // LOGICAL sectors / Physical page
#define HTABLE_SLOTS 512 // 9 bits of address
#define HDIRECTORY_SLOTS 1024 // 10 bits of address
#define HvGetCellType(Cell) ((ULONG)((Cell & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT))
//
// --- HCELL --- an object within the hive (A bin is filled with HCELLs)
//
// Any given item of user data must fit within a single HCELL.
// HCELLs cannot span Bins.
//
#define HCELL_PAD(Hive) ((Hive->Version>=2) ? 8 : 16)
// All cells must be at least this large,
// All allocations on this boundary
#define HCELL_ALLOCATE_FILL 0xb2 // bz -> buzz buzz (yeah, it's a stretch)
// must fill all newly allocated
// cells for security reasons
#define HCELL_FREE_FILL 0xfc // fc = HvFreeCell...
//
// Currently we support two cell formats, one with a Last backpointer (old version),
// and one without (new version)
//
// All cells in a hive must be of the same type. Version 1 hives use the old version,
// Version 2 or greater use the new version.
//
#define USE_OLD_CELL(Hive) (Hive->Version==1)
typedef struct _HCELL {
LONG Size;
union {
struct {
ULONG Last;
union {
ULONG UserData;
HCELL_INDEX Next; // offset of next element in freelist (not a FLink)
} u;
} OldCell;
struct {
union {
ULONG UserData;
HCELL_INDEX Next; // offset of next element in freelist (not a FLink)
} u;
} NewCell;
} u;
} HCELL, *PHCELL;
//
// --- HBIN --- is a contiguous set of HBLOCKs, filled with HCELLs.
//
#define HBIN_SIGNATURE 0x6e696268 // "hbin"
#define HBIN_NIL (-1)
#pragma pack(4)
typedef struct _HBIN {
ULONG Signature;
ULONG FileOffset; // Own file offset (used in checking)
ULONG Size; // Size of bin in bytes, all inclusive
ULONG Reserved1[2]; // Old FreeSpace and FreeList (from 1.0)
LARGE_INTEGER TimeStamp; // Old Link (from 1.0). Usually trash, but
// first bin has valid value used for .log
// correspondence testing, only meaningful
// on disk.
ULONG Spare; // this used to be MemAlloc. We don't use it anymore as we
// can't afford to touch the bin (it's not residing in paged-pool
// anymore, so touching it means modifying mnw pages).
// Spare is used for the ShiftFreeBins Stuff - in memory only!
//
// Cell data goes here
//
} HBIN, *PHBIN;
#pragma pack()
//
// ===== On Disk Structures =====
//
//
// NOTE: Hive storage is always allocated in units of 4K. This size
// must be used on all systems, regardless of page size, since
// the file format needs to be transportable amoung systems.
//
// NOTE: The integrity code depends on certain blocks (e.g., the
// BASE block) being at least as large as the size of a physical
// sector. (Otherwise data that should be left alone will
// be written because the FS has to block/deblock.) This means
// that the current code will not work with sectors > 4K.
//
// NOTE: A hive on disk always contains at least two blocks of storage.
// 1 block for the base block, and 1 for the minimum 1 bin.
//
// NOTE: Only modified parts of the hive get written to disk.
// This is not just for efficiency, but also to avoid risk
// of destruction of unlogged data. Dirty bits keep track
// of what has been modified, they reside in a simple
// bit map attached to the hive. One bit for each logical
// sector of 512 bytes.
//
// If the physical sector size of the machine is less than 512,
// no matter, we'll always write in clumps of 512. If the
// physical sector size is greater than 512, we'll always clump
// data together so that we log and write data
// in chunks of that size. Physical sector sizes > 4K will
// not work correctly (logging will not work right, so system
// crashes may lose data that would not otherwise be lost.)
//
//
// An on disk image of a hive looks like this:
//
// +---------------------------------------+
// | HBASE_BLOCK | 1 Hive Block == 4K
// | |
// +---------------------------------------+ <- HBLOCK_SIZE boundary
// | Bin - 1 to N 4K blocks |
// | Each contains a signature, size, and |
// | a boundary tag heap internal to |
// | itself. Once allocated lives forever |
// | and always at same file offset. |
// +---------------------------------------+ <- HBLOCK_SIZE boundary
// | Bin ... |
// +---------------------------------------+ <- HBLOCK_SIZE boundary
// ...
// +---------------------------------------+ <- HBLOCK_SIZE boundary
// | Last allocated Bin, new bins are put |
// | immediately after this one. |
// +---------------------------------------+ <- HBLOCK_SIZE boundary
//
// Hive files must allocate on HBLOCK_SIZE boundaries because they
// might be written on many different systems, and must therefore be
// set up for the largest cluster size we will support.
//
//
// The log file format is:
//
// +-------------------------------+
// | HBASE_BLOCK copy |
// +-------------------------------+ <- cluster (usually 512) bound
// | DirtyVector |
// | (length computed from length |
// | in the base block |
// | (with "DIRT" on front as a |
// | signature) |
// +-------------------------------+ <- cluster (usually 512) bound
// | Dirty Data |
// +-------------------------------+ <- cluster (usually 512) bound
// | Dirty Data |
// +-------------------------------+ <- cluster (usually 512) bound
// | ... |
// +-------------------------------+
//
// Recovery consists of reading the file in, computing which clusters
// of data are present from the dirtyvector, and where they belong in
// the hive address space. Position in file is by sequential count.
//
// Logs can allocate on cluster boundaries (physical sector size of
// host machine) because they will never be written on any machine other
// than the one that created them.
//
// For log to be valid:
//
// Signature, format, major.minor must match expected values.
// Sequence1 and Sequence2 must match.
// CheckSum must be correct.
// Signture on DirtyVector must be correct
//
// For log to be applicable:
//
// Sequence in log must match sequence in hive.
// TimeStamp in log must match TimeStamp in hive.
// Hive must be in mid-update state, or have bogus header.
//
//
// --- HBASE_BLOCK --- on disk description of the hive
//
//
// NOTE: HBASE_BLOCK must be >= the size of physical sector,
// or integrity assumptions will be violated, and crash
// recovery may not work.
//
#define HBASE_BLOCK_SIGNATURE 0x66676572 // "regf"
#define HSYS_MAJOR 1 // Must match to read at all
#define HSYS_MINOR 3
#define HSYS_WHISTLER_BETA1 4 // Whistler Beta1 hives
#define HSYS_WHISTLER 5 // normal Whistler hives
#define HSYS_MINOR_SUPPORTED HSYS_WHISTLER // Must be <= to write, always
// set up to writer's version.
#define HBASE_FORMAT_MEMORY 1 // Direct memory load case
#define HBASE_NAME_ALLOC 64 // 32 unicode chars
//
// Boot Type Loader <-> Kernel communication
//
#define HBOOT_NORMAL 0
#define HBOOT_REPAIR 1
#define HBOOT_BACKUP 2
#define HBOOT_SELFHEAL 4
#pragma pack(4)
typedef struct _HBASE_BLOCK {
ULONG Signature;
ULONG Sequence1;
ULONG Sequence2;
LARGE_INTEGER TimeStamp;
ULONG Major;
ULONG Minor;
ULONG Type; // HFILE_TYPE_[PRIMARY|LOG]
ULONG Format;
HCELL_INDEX RootCell;
ULONG Length; // Includes all but header
ULONG Cluster; // for logs only
UCHAR FileName[HBASE_NAME_ALLOC]; // filename tail
ULONG Reserved1[99];
ULONG CheckSum;
ULONG Reserved2[128*7-2]; // subtract 2 for the volatile info
ULONG BootType; // set by bootloader
ULONG BootRecover; // set to 1 by bootloader if it did hive recovery
// nobody else is using this
} HBASE_BLOCK, *PHBASE_BLOCK;
#pragma pack()
#define HLOG_HEADER_SIZE (FIELD_OFFSET(HBASE_BLOCK, Reserved2))
#define HLOG_DV_SIGNATURE 0x54524944 // "DIRT"
//
// ===== In Memory Structures =====
//
//
// In memory image of a Hive looks just like the on-disk image,
// EXCEPT that the HBIN structures can be spread throughout memory
// rather than packed together.
//
// To find an HCELL in memory, a mechanism that takes an HCELL_INDEX and
// derives a memory address from it is used. That mechanism is very
// similar to a two level hardware paging table.
//
// A bit map is used to remember which parts of the hive are dirty.
//
// An HBLOCK can be in three different states
// 1. Present in memory. BlockAddress and BinAddress are valid pointers.
// This is the normal state of an HBLOCK.
//
// 2. Discardable. The HBIN containing this HBLOCK is completely free, but
// the bin is dirty and needs to be written to the hive file before it
// can be free. This is the state we will be in if somebody frees a
// cell, causing the entire HBIN to become free. HvpEnlistFreeCell will
// transition all the HBLOCKs in the free HBIN to this state, but will
// not free their memory. After the dirty HBLOCKs are flushed to the
// file, the memory will be freed.
//
// Note that if we need to allocate more storage from an HBIN in this
// state, HvAllocateCell will simply change its state back to State 1
// and it will be usable.
//
// An HBLOCK in this state has a valid BlockAddress and BinAddress, but
// the HMAP_DISCARDABLE bit will be set.
//
// 3. Discarded. The HBIN containing this HBLOCK is completely free, and
// is not dirty (i.e. it is marked as free in the hive file as well).
// There is no memory allocated to contain this HBIN. After HvSyncHive
// writes out an HBIN that is in State 2, it frees its pool and the
// HBIN moves into this state.
//
// In order to use this HBIN, memory must be allocated to back it, and
// the HBIN and initial HCELL must be recreated. (we could re-read it
// from the hive file, but there's not much point in that since we know
// that it is entirely free, so we might as well just recreate it and
// save the disk i/o)
//
// An HBLOCK in this state has a NULL BlockAddress in the map.
// The BinAddress will contain the next HCELL in the free list, so
// we can reconstruct this when we need it.
// The HMAP_NEWALLOC bit will be set for the first HBLOCK in the HBIN.
//
//
// --- HMAP_ENTRY --- Holds memory location of HCELL
//
#define HMAP_FLAGS (0xf)
#define HMAP_BASE (~(HMAP_FLAGS))
#define HBIN_BASE(BinAddress) (BinAddress & HMAP_BASE)
#define HBIN_FLAGS(BinAddress) (BinAddress & HMAP_FLAGS)
#define HMAP_NEWALLOC 1 // the bin is the beginning of a new
// allocation. When bin is in view this
// doesn't really matter
#define HMAP_DISCARDABLE 2 // bin is discardable (i.e. is all free)
// first time when we get the chance we'll
// free it (if it is in paged pool)
#define HMAP_INVIEW 4 // bin is mapped in system cache
#define HMAP_INPAGEDPOOL 8 // bin is allocated from paged pool
#define BIN_MAP_ALLOCATION_TYPE(Me) (((Me)->BinAddress)&(HMAP_INPAGEDPOOL|HMAP_INVIEW))
#define ASSERT_BIN_INVIEW(Me) ASSERT( ((Me)->BinAddress & HMAP_INVIEW) != 0 )
#define ASSERT_BIN_INPAGEDPOOL(Me) ASSERT( ((Me)->BinAddress & HMAP_INPAGEDPOOL) != 0 )
#define ASSERT_BIN_INVALID(Me) ASSERT( ((Me)->BinAddress & (HMAP_INPAGEDPOOL|HMAP_INVIEW)) == 0 )
#define ASSERT_BIN_VALID(Me) ASSERT( ((Me)->BinAddress & (HMAP_INPAGEDPOOL|HMAP_INVIEW)) != 0 )
struct _CM_VIEW_OF_FILE; //forward
typedef struct _HMAP_ENTRY {
ULONG_PTR BlockAddress; // Low 2 bits always 0. High bits
// are memory address of HBLOCK that
// HCELL starts in, add Offset to this.
// (An HCELL can span several HBLOCKs)
//
ULONG_PTR BinAddress; // Low bit set TRUE to mark beginning
// of a new allocation.
// High bits are memory address of
// first HBLOCK in same bin.
// (A given HCELL is always contained
// in a single bin.)
// Dragos: From here start the changes!!!
struct _CM_VIEW_OF_FILE *CmView; // pointer to the view; NULL when bin is not mapped
ULONG MemAlloc; // we needed to move this from the bin header to the map, in
// order to prevent the bin from being touched
/*
We don't really need this. Left just as a comment
ULONG Flags; // tells if a bin is mapped through
// a view, is allocated from paged pool
// or is unmapped/unallocated
ULONG_PTR MappedAddress; // temporary address inside the mapped view.
*/
} HMAP_ENTRY, *PHMAP_ENTRY;
//
// --- HMAP_TABLE --- Array of MAP_ENTRYs that point to memory HBLOCKs
//
// Each HBLOCK worth of space in the Hive image has an entry in
// an HMAP_TABLE.
//
typedef struct _HMAP_TABLE {
HMAP_ENTRY Table[ HTABLE_SLOTS ];
} HMAP_TABLE, *PHMAP_TABLE;
//
// --- HMAP_DIRECTORY --- Array of pointers to HMAP_TABLEs
//
typedef struct _HMAP_DIRECTORY {
PHMAP_TABLE Directory[ HDIRECTORY_SLOTS ];
} HMAP_DIRECTORY, *PHMAP_DIRECTORY;
//
// ===== Hive Routines typedefs =====
//
struct _HHIVE; // forward
typedef
PVOID
(*PALLOCATE_ROUTINE) (
ULONG Length, // Size of new block wanted
BOOLEAN UseForIo, // TRUE if yes, FALSE if no
ULONG Tag
);
typedef
VOID
(*PFREE_ROUTINE) (
PVOID MemoryBlock,
ULONG GlobalQuotaSize
);
typedef
BOOLEAN
(*PFILE_SET_SIZE_ROUTINE) (
struct _HHIVE *Hive,
ULONG FileType,
ULONG FileSize,
ULONG OldFileSize
);
typedef struct {
ULONG FileOffset;
PVOID DataBuffer;
ULONG DataLength;
} CMP_OFFSET_ARRAY, * PCMP_OFFSET_ARRAY;
typedef
BOOLEAN
(*PFILE_WRITE_ROUTINE) (
struct _HHIVE *Hive,
ULONG FileType,
PCMP_OFFSET_ARRAY offsetArray,
ULONG offsetArrayCount,
PULONG FileOffset
);
typedef
BOOLEAN
(*PFILE_READ_ROUTINE) (
struct _HHIVE *Hive,
ULONG FileType,
PULONG FileOffset,
PVOID DataBuffer,
ULONG DataLength
);
typedef
BOOLEAN
(*PFILE_FLUSH_ROUTINE) (
struct _HHIVE *Hive,
ULONG FileType,
PLARGE_INTEGER FileOffset,
ULONG Length
);
typedef
struct _CELL_DATA *
(*PGET_CELL_ROUTINE)(
struct _HHIVE *Hive,
HCELL_INDEX Cell
);
typedef
VOID
(*PRELEASE_CELL_ROUTINE)(
struct _HHIVE *Hive,
HCELL_INDEX Cell
);
//
// --- HHIVE --- In memory descriptor for a hive.
//
//
// HHIVE contains pointers to service procedures, and pointers to
// map structure.
//
// NOTE: Optimization - If the size of a hive is less than what can
// be mapped with a single HMAP_TABLE (HTABLE_SLOTS * HBLOCK_SIZE,
// or 2 megabytes) there is no real HMAP_DIRECTORY. Instead,
// a single DWORD in the HHIVE acts as the 0th entry of the
// directory.
//
// NOTE: Free Storage Management - When a hive is loaded, we build up
// a display (vector) of lists of free cells. The first part
// of this vector contains lists that only hold one size cell.
// The size of cell on the list is HCELL_PAD * (ListIndex+1)
// There are 15 of these lists, so all free cells between 8 and
// 120 bytes are on these lists.
//
// The second part of this vector contains lists that hold more
// than one size cell. Each size bucket is twice the previous
// size. There are 8 of these lists, so all free cells between 136 and
// 32768 bytes are on these lists.
//
// The last list in this vector contains all cells too large to
// fit in any previous list.
//
// Example: All free cells of size 1 HCELL_PAD (8 bytes)
// are on the list at offset 0 in FreeDisplay.
//
// All free cells of size 15 HCELL_PAD (120 bytes)
// are on the list at offset 0xe.
//
// All free cells of size 16-31 HCELL_PAD (128-248 bytes)
// are on the list at offset 0xf
//
// All free cells of size 32-63 HCELL_PAD (256-506 bytes)
// are on the list at offset 0x10.
//
// All free cells of size 2048 HCELL_PAD (16384 bytes)
// OR greater, are on the list at offset 0x17.
//
// FreeSummary is a bit vector, with a bit set to true for each
// entry in FreeDisplay that is not empty.
//
#define HHIVE_SIGNATURE 0xBEE0BEE0
#define HFILE_TYPE_PRIMARY 0 // Base hive file
#define HFILE_TYPE_LOG 1 // Log (security.log)
#define HFILE_TYPE_EXTERNAL 2 // Target of savekey, etc.
#define HFILE_TYPE_MAX 3
#define HHIVE_LINEAR_INDEX 16 // All computed linear indices < HHIVE_LINEAR_INDEX are valid
#define HHIVE_EXPONENTIAL_INDEX 23 // All computed exponential indices < HHIVE_EXPONENTIAL_INDEX
// and >= HHIVE_LINEAR_INDEX are valid.
#define HHIVE_FREE_DISPLAY_SIZE 24
#define HHIVE_FREE_DISPLAY_SHIFT 3 // This must be log2 of HCELL_PAD!
#define HHIVE_FREE_DISPLAY_BIAS 7 // Add to first set bit left of cell size to get exponential index
#define FREE_HBIN_DISCARDABLE 1 // the BlockAddress in HBIN points to the real bin
typedef struct _FREE_HBIN {
LIST_ENTRY ListEntry;
ULONG Size;
ULONG FileOffset;
ULONG Flags;
} FREE_HBIN, *PFREE_HBIN;
typedef struct _HHIVE {
ULONG Signature;
PGET_CELL_ROUTINE GetCellRoutine;
PRELEASE_CELL_ROUTINE ReleaseCellRoutine;
PALLOCATE_ROUTINE Allocate;
PFREE_ROUTINE Free;
PFILE_SET_SIZE_ROUTINE FileSetSize;
PFILE_WRITE_ROUTINE FileWrite;
PFILE_READ_ROUTINE FileRead;
PFILE_FLUSH_ROUTINE FileFlush;
struct _HBASE_BLOCK *BaseBlock;
RTL_BITMAP DirtyVector; // only for Stable bins
ULONG DirtyCount;
ULONG DirtyAlloc; // allocated bytges for dirty vect
ULONG Cluster; // Usually 1 512 byte sector.
// Set up force writes to be
// done in larger units on
// machines with larger sectors.
// Is number of logical 512 sectors.
BOOLEAN Flat; // TRUE if FLAT
BOOLEAN ReadOnly; // TRUE if READONLY
BOOLEAN Log;
ULONG HiveFlags;
ULONG LogSize;
ULONG RefreshCount; // debugging aid
ULONG StorageTypeCount; // 1 > Number of largest valid
// type. (1 for Stable only,
// 2 for stable & volatile)
ULONG Version; // hive version, to allow supporting multiple
// formats simultaneously.
struct _DUAL {
ULONG Length;
#ifdef HV_TRACK_FREE_SPACE
ULONG FreeStorage; // how many free space.
#endif
PHMAP_DIRECTORY Map;
PHMAP_TABLE SmallDir;
ULONG Guard; // Always == -1
RTL_BITMAP FreeDisplay[HHIVE_FREE_DISPLAY_SIZE]; // bitmap of freecells of the corresponding size
// for every HBLOCK_SIZE - bin in the hive, a bit
// is set here if a free cell of the desired size
// lies in this block
ULONG FreeSummary;
LIST_ENTRY FreeBins; // list of freed HBINs (FREE_HBIN)
} Storage[ HTYPE_COUNT ];
//
// Caller defined data goes here
//
} HHIVE, *PHHIVE;
#endif // __HIVE_DATA__