Patent ID: 7107396

Claim:
A method for managing variable sized pages of possibly non contiguous blocks in a Non-Volatile-Storage (NVS) for attaining a consistent NVS image that survives malfunction events; each page includes a self describing block or a linked list of self describing blocks, the method comprising: (a) providing auxiliary modules stored in Volatile Storage, wherein said auxiliary modules comprise free block database indicative of free blocks and association database representing replica of linked lists and partial linked lists, if any, of blocks in the NVS; (b) providing an atomic “create a new page” procedure; (c) providing an atomic “add block” procedure for adding a possibly non contiguous block to a page; the newly added block has a back pointer to a previous block in the page; (d) providing a “delete page” procedure for deleting all blocks in a page, wherein said “delete page” procedure comprises: while there are blocks in the page: moving from a first block to last through forward pointers in the association database and deleting a corresponding block in the NVS; a block in the NVS is returned to the free list only after there is no block pointing to it; (e) providing at least one recovery procedure for rolling backward said add block procedure and rolling forward the delete page procedure, in case of malfunction event, thereby attaining consistent NVS; and (f) managing said variable sized pages in accordance with any of steps (a) through (e).