Patent Description:
Main memory of computing devices is going to be non-volatile in future machines, which means that program data stored in it will not be lost on power failures. However, data stored in volatile memory will be lost on power failures. Some parts of main memory will be volatile. All updates to main memory are performed through central processing unit (CPU) caches, which are volatile. In the event of a power failure, data structures in non-volatile memory could be left in an inconsistent state if data is changed in a cache, but the data changed in the cache is not written back to the non-volatile memory before a power failure.

Memory allocators can suffer from such data inconsistency due to power failures. If there is a power failure before data in a volatile memory, such as a CPU cache, is written to a non-volatile memory, program data might be in an inconsistent state after the power comes back. The memory occupied by an object could be marked allocated in allocator metadata stored in a cache, but the object may not yet be linked in program data structures, which means the memory is permanently leaked and will not be used in the future. Alternatively, a portion of non-volatile memory may be allocated for an object, but the memory allocator state in the non-volatile memory is not updated, which means that the memory could be allocated for a different object in the future, leading to memory corruption. A similar problem can occur when a program frees a previously allocated object and removes a pointer to it. If there is a power failure that prevents all the updates from reaching main memory, the object could either be leaked or memory could be allocated twice, leading to memory corruption.

To prevent such scenarios, CPUs support instructions to write back ("flush") cache lines from a CPU cache to non-volatile memory. For instance, Intel (trade mark) supports the clwb instruction that guarantees that the target cache line is stored in main memory at the next memory store fence. The store fence acts as a "wait" for the data to reach memory to prevent power failures from causing memory allocator state (and other data) inconsistencies in non-volatile memory.

Non-volatile user mode memory allocators use allocation logs to facilitate recovery of allocator states after power failures. They rely on logging allocator states in the allocation logs in non-volatile memory and using the allocation logs for recovery after failures.

Waiting for writes to memory to complete during memory allocation and deallocation degrades performance of the program as such waiting typically takes hundreds of cycles on modern CPUs.

The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known user mode memory allocators.

<CIT> discloses memory management and data recovery for systems that operate using storage class memory, such as non-volatile RAM. The disclosure has application to production database systems, where reducing database downtime in the event of a system crash is desirable. The disclosed technology can address a variety of problems that exist during a system crash. The disclosed technology can be used to address the loss of the physical memory mapping and/or the loss of the CPU cache that typically occurs in the event of a system crash. The disclosed technology can be used to prevent data inconsistency and/or memory leak problems that may arise in the event of a system crash.

<CIT> discloses that according to an example, persistent memory garbage collection may include determining whether termination of a program is based on a specified termination of the program during execution of the program or an unspecified termination of the program during the execution of the program. In response to a determination that the termination of the program is based on the specified termination of the program during the execution of the program, persistent metadata stored in a persistent memory may be used to restart the program. In response to a determination that the termination of the program is based on the unspecified termination of the program during the execution of the program, the persistent metadata stored in the persistent memory may be used to collect garbage from the persistent memory and to restart the program.

The detailed description provided below in connection with the appended drawings is intended as a description of the present examples and is not intended to represent the only forms in which the present example are constructed or utilized. The description sets forth the functions of the example and the sequence of operations for constructing and operating the example. However, the same or equivalent functions and sequences may be accomplished by different examples.

A typical approach for using an allocation log in user mode memory allocation and deallocation in single-thread programs is described below.

To enable recovery, the allocator writes log, allocator metadata, object contents, and pointer to the non-volatile memory. It has to wait for the writes (e.g. using clwb and a store fence on Intel's (trade mark) CPUs) to reach the non-volatile memory after steps <NUM> and <NUM>. This allows the recovery code that runs after a power failure to recover the state of the allocator. After a power failure, the recovery code examines the log, and rolls back the allocation for each entry in the log that was not marked as completed.

Similar steps and waiting for writes to memory are required for memory deallocations, which also require two memory write operations per deallocation.

According to various embodiments, a user mode memory allocator divides a non-volatile memory into memory "pages", i.e. blocks of memories. Portions of memory on a page may be allocated to objects of the same size. In addition, a plurality of pages may also be allocated to objects of the same size. For instance, a memory allocator may allocate pages of <NUM> kB to objects of <NUM>-byte and may allocate pages of <NUM> kB to objects of <NUM> kB.

The allocator may keep the following pieces of meta-data in non-volatile memory: a table ("full page table") of all pages it has used for allocation or will use for potential allocation, an active page table of pages that may require recovery in case of a power failure, and meta-data for each page that contains information about whether each potential memory portion in the respective page is allocated or free. The active page table may maintain a subset of the pages of the full page table. Recent updates to the allocator metadata is first kept in volatile CPU caches before being written into the non-volatile memory. In the event of a power failure, the recent updates to the allocator metadata may be lost in the cache before being written into the non-volatile memory.

An "active page table" is a table of a selection of memory pages ("active pages"), the information of which may need recovery in event of a power failure. The active page table may contain addresses of the pages which need recovery. The active page table is kept in the non-volatile main memory. The active page table may keep memory pages which have portions of memory recently allocated or freed. The metadata of the pages in the active page table is stored in the non-volatile memory. The metadata of the pages may include any information associated with the pages. However, recent updates to the metadata of the pages in the active page table may temporarily be stored in a non-volatile memory, such as a cache, as described above. The recent updates to the metadata will be lost in the event of a power failure. The metadata of the active pages can be recovered using program-specific recovery procedures as will be described below.

According to various embodiments, there is provided a method for allocating memory in a computing device. According to the method, a memory allocator, receives a request for non-volatile memory allocation of an object from a program executing on the computing device. The request comprises a requested memory size and registration data from the program. In response to the request, the memory allocator finds an available address of a portion of a page of the non-volatile memory. The memory allocator then searches an active page table in the non-volatile main memory to find the page and if the page is not found in the active page table, it inserts the page into the active page table; and waits for a memory write for inserting the page into the active page table to complete before carrying out any further processing. Then the memory allocator may update the metadata of the page to indicate that the object has been allocated with a memory portion, wherein update to the metadata of the page is first stored in a volatile memory, such as a cache, before being written into the non-volatile main memory. The memory allocator then issues a write to the non-volatile main memory to update the metadata of the page in the non-volatile main memory for marking the memory portion as being allocated to the object, but does not wait for the write to complete before carrying out further processing.

According to various embodiments, there is also provided a method for deallocating memory in a computing device having a non-volatile main memory. The method comprises receiving a request from a program executing at the computing device for deallocating a portion of the non-volatile main memory allocated to an object; finding, a page containing the memory portion; searching an active page table in the non-volatile main memory to find the page, and if the page is not found in the active page table: inserting the page into the active page table; and waiting for a memory write for inserting the page into the active page table to complete. The program may then perform unlinking of the object at the portion of memory from its data structures. The method for deallocating memory may further comprise updating metadata of the page to indicate the object as free, wherein update to the metadata is first stored in a volatile memory before being written into the non-volatile memory. The method further comprises issuing a write to the non-volatile main memory to update the metadata of the page in the non-volatile main memory for marking the memory portion as being deallocated, but not waiting for the write to complete before carrying out further processing. The write from the volatile memory to the non-volatile main memory may be implemented using the clwb instruction.

According to the memory allocation or deallocation method of the various embodiments, waiting for writes to memory is only needed in the event that the memory page used by the memory allocation or deallocation is not currently in the active page table. To improve locality of access and efficiency, the memory allocator may allocate memory from recently used pages.

According to various embodiments, there is also provided a method for data recovery in a computing device having a non-volatile main memory and a volatile memory, the method comprising: i) receiving, from a program, a request for recovering metadata of pages in an active page table, ii) identifying a memory page in a plurality of memory pages in the active page table, iii) identifying a memory portion in a plurality of memory portions in the memory page, iv) accessing registration data stored in the non-volatile main memory to invoke a recovery function for the program, v) producing, by the recovery function, a result indicating whether the memory portion has been allocated to an object or has been freed, and vi) marking, by the recovery function, the metadata of the page in the non-volatile memory to indicate whether the memory portion has been allocated to the object or has been freed using the result. The method for data recovery may further comprise vii) repeating processes iv)-vi) for each remaining memory portion in the plurality of memory portions of the memory page, until all memory portions of the memory page have been marked as free or allocated in the meta-data of the active page table, and viii) repeating processes iii)-vii) for each remaining memory page in the plurality of memory pages in the active page table, until all memory portions of the memory pages in the active page table have been marked as freed or allocated in the meta-data of the active page table.

<FIG> is a flow diagram of a method <NUM> for user mode memory allocation of a memory portion of a non-volatile main memory in a computing device to an object of a computer program according to a first embodiment of the present invention.

In block <NUM>, a user mode memory allocator of the computing device receives a request for non-volatile memory allocation of an object from a program executing on the computing device. The request comprises a requested memory size and registration data from the program. The registration data may be registration data for a page, which comprises at least one memory portion with a size suitable for allocation to the object.

The registration data may comprise a name of a recovery function stored in the non-volatile memory, a pointer to the recovery function, or any other identifier for identifying or invoking the recovery function. It may also comprise additional information to be passed to the recovery function, typically in a form of a pointer to the information. The memory allocator may store the registration data for a page in the metadata for the page in the non-volatile main memory, and use the registration data to invoke the recovery function for recovering metadata of the page in the event of a power failure.

The recovery function may be specific to the program. An example of the program-specific recovery function is a function for recovery of linked list nodes. In this example, if the object being recovered is reachable from the linked list, then it should be marked as allocated in allocator metadata. If it is not reachable, it should be marked as free.

In block <NUM>, the memory allocator finds, an address of an available memory portion in a plurality of memory portions of a page of the non-volatile memory. The available memory portion is a memory portion available and has a size suitable for allocation to the object.

In block <NUM>, the memory allocator searches an active page table in the non-volatile main memory to look for the page. The active page table is a table of memory pages of the non-volatile memory that need allocator metadata recovery in case of a power failure. As explained above, recent updates to the metadata of pages of the active page table may be stored in a volatile memory temporarily, such as a CPU cache, and may be lost in the event of a power failure.

If the page is not found in the active page table, the method proceeds to block <NUM>, in which the memory allocator inserts the page into the active page table in the non-volatile main memory. Then, in block <NUM>, the memory allocator waits for a memory write for inserting the page into the active page table to complete. Waiting for the memory write to complete means the memory allocator does not carry out any further steps until the memory write is completed. Then the method proceeds to block <NUM>.

Alternatively, if the page is found in the active page table, the method proceeds from block <NUM> to block <NUM> straightaway. In this case, the allocation of a memory portion, which is already in the active page table, does not require writes to the main memory, and avoids latencies associated with the writes to the main memory.

In block <NUM>, the memory allocator then issues a write to the non-volatile main memory to mark the memory portion as being allocated to the object in the page in the main memory. The write comprises temporarily storing an update to the metadata of the page in a volatile memory, such as a cache, to indicate the object as being allocated with a memory portion, before writing the update from the volatile memory to the non-volatile memory. Then the update to the metadata stored in the cache for the page is used to update the metadata stored in the non-volatile memory for the page. However, in this block, the memory allocator does not need to wait for the write to complete, i.e. does not need to wait for the update to the metadata stored in the cache to reach the non-volatile memory, before proceeding to the next block.

In block <NUM>, the allocator returns the memory address of the memory portion allocated to the object back to the program.

According to the above user mode memory allocation method, allocation requires at most one wait for a memory write (block <NUM>). The wait is not required frequently, as typically memory portions to be allocated are already in the active page table.

<FIG> is a flow diagram of a method <NUM> for deallocating a memory portion of a non-volatile main memory in a computing device according to the first embodiment of the present invention.

In block <NUM>, the memory allocator receives, from a program executing on the computing device, a request for deallocating a memory portion which has been allocated to an object. In block <NUM>, the memory allocator finds the memory page containing the memory portion to deallocate. In block <NUM>, the memory allocator searches the active page table in the non-volatile main memory for the page which contains the memory portion to deallocate.

If the page is not found in the active page table, the method proceeds to block <NUM>, in which the allocator inserts the page into the active page table in the non-volatile main memory. Then, in block <NUM>, the memory allocator waits for a memory write for inserting the page into the active page table to complete.

Then in block <NUM> the program removes the object in the memory portion from its data structures.

Then in block <NUM>, the memory allocator issues a write to the non-volatile main memory to mark the memory portion as free. The write comprises temporarily storing an update to the metadata of the page in a volatile memory, such as a cache, to indicate the object as being allocated with a memory portion, before writing the update from the volatile memory to the non-volatile memory. Then the update to the metadata stored in the cache for the page is used to update the metadata stored in the non-volatile memory for the page. However, in this block, the memory allocator does not need to wait for the write to complete, i.e. does not need to wait for the update to the metadata stored in the cache to reach the non-volatile memory, before proceeding to the next block. Alternatively, if the page is found in the active page table immediately after block <NUM>, the method proceeds from block <NUM> to block <NUM> straightaway.

According to the memory deallocation method <NUM>, deallocation requires at most one wait for a memory write (block <NUM>). In many cases the page containing the memory portion to be freed will be in the active page table due to program access patterns, such that the deallocation method <NUM> does not require any wait for memory writes. For instance, allocating a lot of data at the beginning of a computation and then deallocating it at the end of the computation would result in having the page in the active page table most of the time.

The memory allocator does not unlink an object, and the application program unlinks the object just before requesting it to be freed. This is a more modular approach than the one used by conventional non-volatile memory allocators.

<FIG> is a flow diagram of a method <NUM> for recovering metadata of pages in an active page table in a computing device according to the first embodiment of the present invention. The metadata to be recovered was previously stored in a volatile memory and has not been stored the non-volatile memory due to events such as a power failure.

In block <NUM>, the memory allocator receives a request for recovering metadata of pages in an active page table from a program executing on the computing device. Such a request may be received after a reboot of the computing device following a power failure.

In block <NUM>, the memory allocator identifies a memory page in the active page table. In block <NUM>, the memory allocator identifies a memory portion, which may possibly be allocated to an object, in the memory page. In block <NUM>, the memory allocator accesses the registration data stored in the non-volatile main memory to invoke the recovery function for the program. The memory allocator invokes the recovery function for the page and passes the registration data for the page and the address of the memory portion to the recovery function. The registration data for a page is typically a pointer to a root of the data structure for the page, e.g. head of the linked list for the page. Allocations and deallocation of nodes in the linked list may pass the address of the head as the registration data for the page to the recovery function of the program. The registration data is stored in the full page table in the non-volatile memory. In block <NUM>, the recovery function returns a result indicating whether or not the memory portion has been allocated to an object based on the received registration data for the page.

In block <NUM>, the recovery function then updates data in the non-volatile memory to indicate whether the memory portion has been allocated to the object, flushes the update from the cache to the non-volatile memory to update the metadata of the page in the non-volatile memory, and waits for the write to reach the non-volatile memory.

In block <NUM>, blocks <NUM>-<NUM> are repeated for each remaining memory portion, which may possibly be allocated to an object, of the memory page, until all possible memory portions have been marked as free or allocated in the meta-data of the page. Then in block <NUM>, blocks <NUM>-<NUM> are repeated for each remaining page in the active page table, until all pages in the active page table have been processed.

At the end of the method <NUM>, the page metadata of the pages in the active page table is recovered in the non-volatile memory to indicate which objects have been allocated with a portion of the non-volatile main memory and which objects have not been allocated with a memory portion. The active page table may be cleared at this point.

The recovery function uses the registration data and program logic to recover metadata for the active pages stored in the non-volatile memory. The process effectively reconciles what is in the allocator metadata and what is in the program's data structures.

In one example, the program uses a linked list as its data structure. A linked list consists of nodes. Each node has a pointer (link) to the next node in the list. A pointer can be a memory address. The head of the linked list is a pointer to the first node in the list, or a null pointer if the list is empty. The head of the list is stored at a statically known address H.

When a program allocates a node for this linked list, it requests a memory portion with a size equal to a size required by the node and it provides address of the list recovery function and the address of the list. The registration data for the list may contain the address H of the head. A different list can use the same recovery function, but it provides a different address H' for its head.

In this example, the list consists of four nodes, which are linked as follows:
H->N1->N2->N3->N4.

The program allocates a new node N5 from the allocator. This puts page P5, to which the nodes in the linked list are allocated, in the active page table. The address of the recovery function and the registration data (which contains the address of head H) are in the full page table in the non-volatile memory. The program then inserts the new node N5 into the linked list between N2 and N3 and the list now looks like this:
H-> N1->N2->N5->N3->N4.

Assume that the linked list algorithm makes it possible not to flush any of the updates from the CPU cache to the non-volatile memory. Next the program allocates node N6 from the same page P5 and puts it at the end of the list:
H-> N1->N2->N5->N3->N4->N6.

Again there is no flushing here from the program. The updates to nodes N2 and N4 (updates to their links) are in CPU cache. The updates to the page metadata are also in the cache. Depending on what happens in the system, some subset of these updates might be flushed to non-volatile memory. CPU cache evictions happen, for instance, when the CPU needs to put a new piece of data into the cache but the cache is full.

Then if there is a power failure, after power comes back the memory allocator invokes the recovery function. It invokes the linked list recovery function with the head H (as stored in the full page table) for every memory portion in the page P5, as page P5 is in the active table. The linked list recovery function follows the links from the head. If it finds the address of a memory portion for a node in the list, it returns true. Otherwise, it returns false.

In this example, depending on what cache evictions happened before the power failure, the linked list may be in one of the four states after power comes back:.

Independently, metadata for page P5 may have portions of N5 and N6 in one of the four states, which respectively correspond to states <NUM>)-<NUM>) above:.

The linked list state indicates the how various nodes / objects are linked. It also indicates that the nodes / objects currently in the list should be allocated with a memory portion and the nodes / objects removed from the list should have their respective memory portions freed. The allocator metadata state indicates whether each node / object has been allocated with a memory portion or freed. The recovery function brings the allocator metadata state to match the corresponding program linked list state, to ensure that there are no memory leaks or corruptions. For instance, if the allocator is in state a) and the list is in state <NUM>), the recovery procedure correctly marks N6 as allocated to avoid memory corruption. In other words, the recovery procedure changes allocator metadata state from a) to d), which corresponds to linked list state <NUM>), to avoid memory corruption. As another example, if the linked list is in state <NUM>) and allocator in state c), it correctly marks N6 as freed as per state b) to avoid a memory leak. The Skilled Person would appreciate that the above is merely a non-limiting example of a procedure carried out by the recovery function, and various modifications are made to this procedure without departing from the scope of the subject matter described herein.

The program may register the recovery function for each object type at its start. It is stored in non-volatile memory to allow invoking after a power failure. The function may be stored in a form that does not depend on address layout after recovery. An alternative approach is to have the program register the type and the recovery function before the first allocation of that type. This mapping between function and type can be stored in the recovery function table in the non-volatile memory. The recovery procedure invokes the right function for the type during recovery.

Instead of invoking a function per object, the recovery procedure may group all objects of the same type and invoke the recovery function for the whole group. This allows more efficient memory recovery in some cases. For instance, in the example of recovery of linked list nodes described above, the program could store all the objects that need recovery in a temporary hash table, traverse the linked list once marking all the objects reachable in the list in the hash table. When the traversal is finished, all objects marked reachable in the table are marked as allocated in the allocator metadata and the remaining objects are marked free.

Active page table are preferably kept as small as possible to reduce time for recovery. When the memory allocator attempts to add a page to the active page table and finds the active page table full, it may remove some pages from the table to make room for the new entry. To do this, it may wait for all memory writes to reach the non-volatile memory. Then it can mark some entries in the table free and write the updates to the active page table into allocator metadata in the non-volatile memory. It does not have to wait for the write to complete. This may happen whenever a page is added to the active page table on memory allocations and/or deallocations.

In a second embodiment, a memory allocator is integrated with an epoch-based memory reclamation for concurrent program threads. Epoch-based memory reclamation is based on the principle that if an object is unlinked and freed by a first thread, then no references to the object should be held after the operations in other threads, which are concurrent with the operation for unlinking and freeing the object in the first thread, have finished.

In the second embodiment, each of a plurality of concurrently executing threads is provided with a local counter for keeping track of the operation of the respective thread. The counter for a thread is incremented when the thread starts an operation and when the thread completes the operation. Therefore, an odd counter number for the thread may indicate that the thread is executing an operation, and an even counter number for the thread may indicate that the thread has completed the operation. The vector of all threads' counters is called an "epoch". Epoch A is greater than epoch B when each of A's counters has a value that is greater than the value of a corresponding counter in B if the value of the corresponding counter in B is odd, and equal or greater than the value of a corresponding counter in B if the value of the corresponding counter in B is even. An object can be freed when the current epoch is greater than the epoch in which it was unlinked. A power failure leads to expiry of all epochs.

To optimize deallocation, multiple objects can be collected and freed together. The set of deleted objects which are freed together are referred to as a "generation". The generation's epoch is the epoch at which the last object in the generation is deleted. When the current epoch is greater than the generation's epoch, the generation can be freed, which means the memory portions allocated to all objects in the generation can be deallocated.

When integrated with epoch-based memory reclamation, each of the plurality of concurrently executing threads maintains its own active page table in the non-volatile memory. In addition, it maintains metadata of each active page in the volatile memory. The metadata of each active page for each thread comprises <NUM>) the greatest epoch at which the thread has unlinked an object from the page, which is named the "last freed epoch" and <NUM>) the greatest epoch at which the thread has allocated memory from the page, which is named the "last allocated epoch".

<FIG> is a flow diagram of a method <NUM> for allocating a memory portion of a non-volatile main memory to an object during concurrent execution of a plurality of program threads according to the second embodiment of the present invention.

In block <NUM>, a memory allocator of the computing device receives a request for non-volatile memory allocation of an object from one of a plurality of program threads concurrently executing on the computing device. The request comprises a requested memory size and registration data as explained with reference to <FIG>.

Blocks <NUM>-<NUM> are substantially the same as blocks <NUM>-<NUM> of method <NUM> and therefore their details are omitted for conciseness. However, block <NUM> differs from block <NUM> in that block <NUM> additionally requires the memory allocator to update the last allocated epoch in the metadata of the page in the non-volatile memory.

In block <NUM>, the memory allocator issues a write to the non-volatile main memory to mark the memory portion as being allocated to the object in the active page table for the program thread in the main memory and to update the last allocated epoch in the metadata of the page in the non-volatile memory. Similar to block <NUM>, in block <NUM>, the write comprises temporarily storing an update to the metadata of the page in a volatile memory, such as a cache, to indicate the object as being allocated with a memory portion and to update the last allocated epoch in the metadata of the page, before writing the update from the volatile memory to the non-volatile memory. However, in this block, the memory allocator does not need to wait for the write to complete, i.e. does not need to wait for the update to the metadata stored in the cache to reach the non-volatile memory, before proceeding further.

In block <NUM>, the allocator returns the memory address for the memory portion allocated to the object back to the program thread.

<FIG> is a flow diagram of a method <NUM> for deallocating a memory portion allocated to an object in a non-volatile main memory during concurrent execution of a plurality of program threads according to the second embodiment of the present invention.

In block <NUM>, the memory allocator receives, from one of a plurality of program threads concurrently executing on the computing device, a request for deallocating a memory portion of a non-volatile main memory which has been allocated to an object. In block <NUM>, the memory allocator inserts the object in the current generation of objects which are to be freed together.

Blocks <NUM>-<NUM> are substantially the same as blocks <NUM>-<NUM> of method <NUM> and therefore their details are omitted for conciseness. In block <NUM> the program removes the object from its data structures. Block <NUM> differs from block <NUM> in that block <NUM> additionally requires the memory allocator to free memory portions allocated to all objects in the generation together, and requires the memory allocator to update the last freed epoch in the metadata of the page in the non-volatile memory.

More specifically, in block <NUM>, the memory allocator issues a write to the non-volatile memory to mark the memory portion for the object and memory portions allocated to all objects in the generation as freed in the metadata for the page, and update the last freed epoch in the metadata. Similar to block <NUM>, in block <NUM>, the write comprises temporarily storing an update to the metadata of the page in a volatile memory, such as a cache, before writing the update from the volatile memory to the non-volatile memory. In this block, the memory allocator does not need to wait for the write to complete, i.e. does not need to wait for the update to the metadata stored in the cache to reach the non-volatile memory, before proceeding further.

When removing pages from the active table, the allocator is allowed to remove pages for which the current epoch is greater than both last allocated and last freed epoch stored in volatile metadata. A page can be removed from the active page table after all operations that were in progress in epochs when objects were allocated and deallocated from the page are completed. This happens when the epoch mechanism determines that all operations have been performed, or when there is a power outage.

<FIG> illustrates various components of an exemplary computing-based device <NUM> which are implemented as any form of a computing and/or electronic device, and in which the various embodiments described above are implemented.

Computing-based device <NUM> comprises one or more processors <NUM> which are microprocessors, controllers or any other suitable type of processors for processing computer executable instructions to control the operation of the device in order to perform the methods according to the various embodiments. In some examples, for example where a system on a chip architecture is used, the processors <NUM> include one or more fixed function blocks (also referred to as accelerators) which implement a part of the methods of the various embodiments in hardware (rather than software or firmware). Platform software comprising an operating system <NUM> or any other suitable platform software is provided at the computing-based device to enable application software <NUM> to be executed on the device.

The computer executable instructions are provided using any computer-readable media that is accessible by computing based device <NUM>. Computer-readable media includes, for example, computer storage media such as memory <NUM> and communications media. Computer storage media, such as memory <NUM>, includes volatile (<NUM>) and non-volatile (<NUM>), removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or the like. Computer storage media includes, but is not limited to, random access memory (RAM), read only memory (ROM), erasable programmable read only memory (EPROM), electronic erasable programmable read only memory (EEPROM), flash memory or other memory technology, compact disc read only memory (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that is used to store information for access by a computing device. In contrast, communication media embody computer readable instructions, data structures, program modules, or the like in a modulated data signal, such as a carrier wave, or other transport mechanism. As defined herein, computer storage media does not include communication media. Therefore, a computer storage medium should not be interpreted to be a propagating signal per se. Although the computer storage media (memory <NUM>) is shown within the computing-based device <NUM> it will be appreciated that the storage is, in some examples, distributed or located remotely and accessed via a network or other communication link (e.g. using communication interface <NUM>).

The computing-based device <NUM> also comprises an input/output controller <NUM> arranged to output display information via an output interface <NUM> to a display device <NUM> which may be separate from or integral to the computing-based device <NUM>. The display information may provide a graphical user interface. The input/output controller <NUM> is also arranged to receive and process input from one or more devices, such as a user input device <NUM> (e.g. a mouse, keyboard, camera, microphone or other sensor). In some examples the user input device <NUM> detects voice input, user gestures or other user actions and provides a natural user interface (NUI). In an embodiment the display device <NUM> also acts as the user input device <NUM> if it is a touch sensitive display device. The input/output controller <NUM> outputs data to devices other than the display device in some examples, e.g. a locally connected printing device (not shown in <FIG>).

Any of the input/output controller <NUM>, display device <NUM> and the user input device <NUM> may comprise NUI technology which enables a user to interact with the computing-based device in a natural manner, free from artificial constraints imposed by input devices such as mice, keyboards, remote controls and the like. Examples of NUI technology that are provided in some examples include but are not limited to those relying on voice and/or speech recognition, touch and/or stylus recognition (touch sensitive displays), gesture recognition both on screen and adjacent to the screen, air gestures, head and eye tracking, voice and speech, vision, touch, gestures, and machine intelligence. Other examples of NUI technology that are used in some examples include intention and goal understanding systems, motion gesture detection systems using depth cameras (such as stereoscopic camera systems, infrared camera systems, red green blue (rgb) camera systems and combinations of these), motion gesture detection using accelerometers/gyroscopes, facial recognition, three dimensional (3D) displays, head, eye and gaze tracking, immersive augmented reality and virtual reality systems and technologies for sensing brain activity using electric field sensing electrodes (electro encephalogram (EEG) and related methods).

Alternatively, or in addition, the functionality described herein is performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that are optionally used include Fieldprogrammable Gate Arrays (FPGAs), Application-specific Integrated Circuits (ASICs), Application-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), Graphics Processing Units (GPUs).

One or more device-readable media with device-executable instructions that, when executed by a computing system, direct the computing system to perform the methods described above.

The term 'computer' or 'computing device' is used herein to refer to any device with processing capability such that it executes instructions. Those skilled in the art will realize that such processing capabilities are incorporated into many different devices and therefore the terms 'computer' and 'computing device' each include personal computers (PCs), servers, mobile telephones (including smart phones), tablet computers, set-top boxes, media players, games consoles, personal digital assistants, wearable computers, and many other devices.

It will be understood that the above description is given by way of example only and that various modifications may be made by those skilled in the art. The above specification, examples and data provide a complete description of the structure and use of exemplary embodiments. Although various embodiments have been described above with a certain degree of particularity, or with reference to one or more individual embodiments, those skilled in the art could make numerous alterations to the disclosed embodiments without departing from the scope of this specification.

Claim 1:
A method (<NUM>) for data recovery in a computing device having a non-volatile main memory and a volatile memory, the method comprising:
i) receiving, from a program, a request for recovering metadata of a plurality of pages in an active page table,
ii) identifying (<NUM>) a memory page in the plurality of memory pages in the active page table,
iii) identifying (<NUM>) a memory portion in a plurality of memory portions in the memory page, the method being characterized in that it comprises
iv) accessing (<NUM>) registration data stored in the non-volatile main memory to invoke a recovery function for the program,
v) producing (<NUM>), by the recovery function, a result indicating whether the memory portion has been allocated to an object or has been freed, and
vi) marking (<NUM>), by the recovery function, metadata of the page in the non-volatile memory to indicate whether the memory portion has been allocated to the object or has been freed using the result.