Complex datastore with bitmap checking
AssigneeMicrosoft Corporation
InventorDragos C. Sambotin
Life of this patent
Estimating the term…
Abstract
A datastore, such as a registry or file system having a defined data structure with a logical layer, may be analyzed using a bitmap corresponding to equally sized blocks of data in the datastore. The bitmap is created by traversing the datastore and setting a bit at the beginning of each cell of data, where one cell may have multiple blocks. The datastore is traversed again at a logical layer to verify that each cell is used only one time. The second traverse may unset the beginning bit of each cell as the cell is used. An inconsistency is detected in the datastore when a bit is already unset during the second traverse and when set bits exist after the second traverse.
Claims15
A method comprising:
- reading a datastore having cells of data, each cell comprising at least one block of data, said datastore having metadata comprising pointers into said datastore, said pointers comprising a reference to one beginning block;
- using a bitmap having a bit corresponding to each of said blocks of data, said bitmap having each bit set to an initial value;
- for each cell, changing a bit in said bitmap corresponding to a first block for said cell to a second condition;
- validating said datastore when the number of said bits in a second condition is equal to the number of said cells of data;
- for each of said pointers, flipping a bit corresponding to said one beginning block;
- and
- validating said datastore when the number of said bits in said second condition is zero.
A method comprising:
- storing data in a datastore, said datastore comprising a plurality of blocks of data, said data being stored in a cell comprising at least one of said plurality of blocks of data;
- defining metadata comprising pointers to said data in said datastore, said pointers comprising a starting block for one of said cells;
- defining a bitmap having a bit for every one of said plurality of blocks of data, each of said bits in said bitmap being set to an initial value;
- validating said datastore by a method comprising:
- for each cell, changing a bit in said bitmap corresponding to said first block in said cell, said changing comprising setting said bit to a second value;
- determining a first validity for said datastore using said bitmap by comparing the number of cells to the number of bits in said bitmap set to said second value;
- for each of said pointers, flipping a bit corresponding to said first block said defined in said metadata;
- and
- determining a second validity for said datastore when the number of said bits in said second condition is zero.
A system comprising:
- a datastore comprising a plurality of blocks and adapted to store data, said data being stored in a cell comprising at least one block of data;
- a metadata store defining a data structure and comprising pointers to a first block of data in said cell;
- a bitmap having at least one bit allocated for each of said blocks of data;
- a verification engine adapted to:
- for each cell, change a bit in said bitmap, said changing comprising setting said bit to a second value from an initial value;
- determine a first validity for said datastore using said bitmap;
- for each of said pointers in said metadata store, flipping a bit corresponding to said one beginning block;
- and
- determining a second validity for said datastore when the number of said bits in said second condition is zero.
Dependencies are inferred from the claim text.