Patent Document

CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]    Central Linked List Data Structure and Methods of Use; Filed Jul. 9, 2002, Attorney Docket No. 0299-0001; Inventor: Jonathan Vu.  
         [0002]    Memory-Resident Database Management System and Implementation Thereof; Ser. No. 10/347,678; Filed on Jan. 22, 2003; Attorney Docket Number 0299-0005; Inventors: Tianlong Chen, Jonathan Vu.  
         [0003]    Distributed Memory Computing Environment and Implementation Thereof; Ser. No. 10/347,677; Filed Jan. 22, 2003; Attorney Docket Number 0299-0006; Inventors: Tianlong Chen, Jonathan Vu, Yingbin Wang.  
         [0004]    Single Computer Distributed Memory Computing Environment and Implementation Thereof; Filed on Apr. 30, 2003; Attorney Docket Number 0299-0017; Inventors: Tianlong Chen, Yingbin Wang, and Yinong Wei.  
         [0005]    The above cross-referenced related applications are all hereby incorporated by reference herein in their entirety. 
     
    
     
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT  
         [0006]    Not applicable.  
         BACKGROUND OF THE INVENTION  
         [0007]    1. Field of the Invention  
           [0008]    The present invention relates broadly to computer memory, and more specifically to a memory page pool architecture and method of use.  
           [0009]    2. Description of the Related Art  
           [0010]    In a computer, an Operating System (OS) manages the computer&#39;s hardware and software resources. When a computer is first turned on, a bootstrap loader is run which loads the operating system into memory, and allows it to run. The bootstrap loader runs various smaller programs, which set up the computer to run. One of the bootstrap loader&#39;s tasks at start up is to set up divisions of memory that hold the operating system and other applications. When the Operating System (OS) is run, the memory set up is done anew each time. It is never guaranteed that any application running with the operating system will access the same set of memory pages each time the computer is restarted or run on a different computer, even if the different computer has the same Operating System (OS). The bootstrap system also establishes data structures for flags, signals, and semaphores, for communicating between the computer&#39;s subsystems and applications.  
           [0011]    In prior systems, if an application uses memory pages to build sophisticated data structures, the building process took a long amount of time. Further, rebuilding the data structure each subsequent time the application started took almost the same amount of time. What is needed is a way to rebuild these data structures in a time-saving and efficient manner.  
         SUMMARY OF THE INVENTION  
         [0012]    The present invention has been made in view of the above circumstances and has as an aspect providing a method to configure and manage a pool of memory pages with a snapshot capability. The present invention has a further aspect of providing a snapshot with not only the data but also the structure in which data is constructed and managed. Still another aspect of the present invention is to provide a system and method of taking a snapshot of the memory pages after a data structure has been built and re-mapping the memory pages from the snapshot at the restarting time of the application instead of rebuilding the data structure.  
           [0013]    Another aspect of the present invention is to provide a method and system for constructing and managing a multi-sized memory page pool. Still another aspect of the present invention is to provide a method of tracking memory mapping information. Yet another aspect of the present invention is to track and synchronize changed memory pages.  
           [0014]    Still another aspect of the present invention is to provide a system and method of tracking security information on memory pages. Another aspect of the present invention is to provide a method of access control using security information tracked on memory pages.  
           [0015]    In still another aspect of the present invention is a method of taking a snapshot of memory pages at a particular time.  
           [0016]    A distributed memory computing environment is structured with an invariant memory page pool. The environment includes a device, a memory, a hard disk, and an operating system running on the device. A device ID lookup table and a Memory Block ID Lookup Table are stored in memory. Copies of memory pages and their look up tables are stored on the hard disk or other rewritable non-volatile storage media. If the operating system is shut down, at subsequent system start-up, memory is divided according to the same divisions seen on the memory page copies saved in configuration files.  
           [0017]    Still other aspects, features, and advantages of the present invention are readily apparent from the following detailed description, simply by illustrating preferable embodiments and implementations. The present invention is also capable of other and different embodiments, and its several details can be modified in various respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and descriptions are to be regarded as illustration in nature, and not as restrictive. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]    The accompanying drawings, which are incorporated in and constitute a part of this specification illustrate some embodiments of the invention and, together with the description, serve to explain the objects, advantages, and principles of the invention. In the drawings,  
         [0019]    [0019]FIG. 1 illustrates a Distributed Memory Computing Environment (DMCE) in accordance with the present invention. The overall memory management may be referred to as DMCE Extended Memory Management Unit (EMMU).  
         [0020]    [0020]FIG. 2 illustrates a DMCE Virtual Address and conceptual block diagram of how a Memory Server ID and Memory Block ID are used in memory address mapping, in accordance with the present invention.  
         [0021]    [0021]FIG. 3 illustrates a conceptual block diagram of a multiple-sized memory page pool with a disk-based backup file system in accordance with the present invention.  
         [0022]    [0022]FIG. 4 illustrates a conceptual block diagram of a linked-list memory page pool structure, in accordance with the present invention.  
         [0023]    [0023]FIG. 5 illustrates a conceptual block diagram of a preferred embodiment of tracking transferring states for memory pages in accordance with the present invention.  
         [0024]    [0024]FIG. 6 illustrates an embodiment of tracking transferring states for memory pages in accordance with the present invention.  
         [0025]    [0025]FIG. 7 illustrates a conceptual block diagram of a memory block of same-sized memory pages in accordance with the present invention.  
         [0026]    [0026]FIG. 8 illustrates a conceptual block diagram of a preferred embodiment of Memory Block ID Lookup Table in accordance with the present invention.  
         [0027]    [0027]FIG. 9 illustrates a conceptual block diagram of a preferred embodiment of Memory Page handling structure in accordance with the present invention.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0028]    The present invention relates to application Ser. No. 10/347,677; for “Distributed Memory Computing Environment and Implementation Thereof”; Filed Jan. 22, 2003; Attorney Docket Number 0299-0006; Inventors: Tianlong Chen, Jonathan Vu, Yingbin Wang, and, more specifically, to the DMCE Virtual Address, which is used with the present invention. The DMCE Virtual Address is illustrated in FIG. 2. Referring to FIG. 2, the 64-bit DMCE Virtual Address includes a Memory Server ID  601 , a Memory Block ID  603  and Memory Cell ID (also called Memory Offset ID)  604 . The Memory Server ID is used to map to Server information  606  (including IP address, port, authentication etc.) from a Memory Server ID Lookup Table  605 . The Memory Block ID  603  is used to map to Memory Block information  602  (including at least the starting address of the Memory Block) from a Memory Block ID Lookup Table  600 . The actual address of a memory page in a memory block is the sum of the Memory Offset ID  604  and the starting address  602  of the memory block in which the memory page is located.  
         [0029]    A memory page pool in accordance with the present invention is built upon the DMCE Virtual Address described above, to provide a transparent, snapshot of memory and diminish the time needed to re-build complex data structures. Since the information stored in a DMCE Virtual Address is relative information, one relies on two lookup tables  600 ,  605  and a summation to find the real address. If the DMCE Virtual Address is embedded as part of content in memory pages copied from server to server, the address can still be accessible providing that such two lookup tables, namely the Memory Block ID Lookup Table  600 , and the Memory Server ID Lookup Table  605 , are set accordingly.  
         [0030]    Referring to FIG. 2, there is illustrated a conceptual block diagram of memory page pool. Memory has been separated into memory blocks  703 ,  704 . Each memory block  703 ,  704  is further separated into memory pages  707 ,  708 , each with a desired, configurable page size. The memory page size of each page is the same within one memory block. Memory Page Pool Management (abbreviated as MPPM) manages data stored in two types of memory. One type of memory is volatile memory, referred to as memory side  700 , which allows for fast data access. The second type of memory managed by MPPM is disk-based memory  715 , referred to as disk side  715 , which provides a reliable backup and recovery file system. The memory side  700  of MPPM includes Memory Server ID Lookup Table  701 , Memory Block ID Lookup Table  702 , Memory Mapping Translation Logic  716 , and Memory Security Control Logic  717 .  
         [0031]    Still referring to FIG. 2, the disk side  715  of MPPM includes an optional memory mirror block file  705 ,  706 , a configure file  711 ,  713  and a log file  712 ,  714 , for each memory block  703 ,  704  on the memory side. Memory Mirror block file  705 , configure file  711 , and log file  712  correspond to memory block  703 , and memory mirror block file  706 , configure file  713 , and log file  714  correspond to memory block  704 . The disk side  715  of MPPM also includes a Server Configure File (not shown). It is possible to construct the present invention such that one memory-block-configure file is used for all memory blocks, i.e.,  711  and  713  maybe the same file. And it is also possible to configure the present invention such that one memory-block-log file is used for all memory blocks, i.e.,  712  and  714  may be the same file.  
         [0032]    Still referring to FIG. 2, the Server Configure File  718  is a disk-based copy of the Memory Server ID Lookup Table  701 , in which each table entry relates to one server including the information of Server ID, server IP address, communication port, authentication information and the directories where memory block configuration files  711 ,  713  and memory block files  705 ,  706  are located. It is possible for multiple table entries to refer to the same server.  
         [0033]    Still referring to FIG. 2, the Memory Block ID Lookup Table  702  has every table entry referring to one memory block. It is possible for multiple entries to refer to the same one memory block. Each table entry at least has Memory Block ID and the memory starting address of the corresponding memory block used for DMCE Virtual Address. Memory Page Pool Management adds more information, as described below, to each entry to achieve a snapshot, security, and other functionality.  
         [0034]    Referring to FIGS. 2 and 7, each table entry  730  in Memory Block ID Lookup Table  702  includes all information of a memory block, such as Memory Block ID  731 , starting address of memory block  732 , the size of the memory pages in this memory block  734 , the file name  735  of associated backup file  705 ,  706 , the file name  736  of associated configure file  711 ,  713 , and optional security access control bits  733  for this memory block if security control is desired on the memory block level, the file name  737  of associated log file  712 ,  714 , and the number of total memory pages (not shown in FIG. 7) may be included in a table entry  730 . The memory-based Memory Block ID Lookup Table  702  also includes necessary run-time information (which is not kept in disk-based configure files  711 ,  713 ), such as the number of used pages, the number of unused pages, and, optionally, the memory pointers to memory blocks in order for fast access.  
         [0035]    Still referring to FIG. 2, each memory block has one configure file  711 ,  713  that keeps the same information as in the memory-based Memory Block ID Lookup Table  702  for the corresponding memory block  703 ,  704 . Such configure files  711 ,  713  are used with the Server Configure file (not shown) and existing log files to re-build an exact memory page pool as it was at the time of system restart or recovery. The log files  712 ,  714  are optional, as keeping and maintaining them can slow system performance. However, when kept and maintained, log files  712 ,  714  can be used at the system restarting or recovery time to find out whether system is previously shutdown normally or abnormally, and can be used to fix any inconsistency for abnormal shutdown, if any exists. For certain applications, especially high-performance applications, the log file option can be configured to off, or to log only low-volume critical information.  
         [0036]    Another option for the logging  712 ,  714  is a memory-based option, further, described below.  
         [0037]    Other information may be included in the Memory Block ID Lookup Table and its associated file-based configure files, such as Memory slave process ID in the application titled “Single Computer Distributed Memory Computing Environment and Implementation Thereof”; filed [date]; Attorney Docket Number 0299-0017; Inventors: Tianlong Chen, Yingbin Wang, and Yinong Wei; hereby incorporated by reference, in its entirety, herein.  
         [0038]    Still referring to FIG. 2, each memory block  703 ,  704  has its own disk-based backup file  705 ,  706 . The backup file  705  is associated with the memory block  703 , and the backup file  706  is associated with the memory block  704 . One memory block, may be the back up of another memory block, as long as they are configured with the same block size and same page size. The backup to memory is configurable, and may optionally be file-based or memory-based. The system may optionally be configured with no backup.  
         [0039]    Referring to FIGS. 2 and 7, the “backup file” field  735  stores the backup option information for a memory block. If a backup file option is used, the “backup file” field  735  records a Server ID (which is looked up from Memory Server ID Table) and an absolute file name in that server with the given Server ID. If it is a memory block backup option, the “backup file” field  735  records a Server ID and a Memory Block ID to identify a memory block from a specified server. If the “backup file” field  735  is left blank, the option is no-backup.  
         [0040]    Still referring to FIG. 2, each memory block has continuous, same-sized memory pages in order for easy memory management, e.g., of memory pages  707  in memory block  703  and memory pages  708  in memory block  704 . Each memory page is identified within a memory block by a Memory Offset ID, which is its offset to the starting address of the memory block. Referring to FIG. 7, if memory page is, for example, size S, then the memory page  741  closest to the starting address  740  is of Memory Offset ID equal to  0 , the memory page  742  next closest to the starting address is of Memory Offset ID equal to value S, the memory page  743  next to next closest to the starting address is of Memory Offset ID equal to value 2×S (2 times S), and so on and on. Therefore, the nth memory page is has a Memory Offset ID equal to the value n×S, i.e., n multiplied by S.  
         [0041]    Still referring to FIG. 2, the configure files  711 ,  713  are the disk-based record of Memory Block ID Lookup Table, which is used for the purpose of backup and recovery. The Memory Server Configure file  718  and Memory Block configure files  711 ,  713  may be kept in one file. The information kept in the configure files  711 ,  713 ,  718  is normally not changed at system running time. When restarting the system, the configure files  711 ,  713 ,  718  are used to re-build the whole memory page pool exactly the same as it was at its previous running stage.  
         [0042]    Still referring to FIG. 2, when backup file is used as backup option, backup files  705 ,  706  will keep exact record of their corresponding memory blocks  703 ,  704 . One embodiment is to binary copy bit-by-bit from memory blocks  703 ,  704  to their corresponding backup files  705 ,  706 . Alternatively, one can use certain compression algorithms to compress and copy from memory block to backup file in order to save disk space. However, compression algorithms tend to be computing intensive, and may slow down system performance. Regardless of how the back up file is made, each memory page  707  in a memory block  703  has one mirror copy  709  in the corresponding backup file  705 . The relative offset of a memory page  707  in a memory block  703  is the same offset of its mirror copy  709  in its backup file  705 . This mirroring scheme is also used in the process of mirror-copying from memory block to memory block, when the memory block backup option is used.  
         [0043]    In order to keep the information stored in memory pages synchronized with the backup option (file or memory block), only changed memory pages are copied to their corresponding mirror copies in the backup option (file or memory block). Necessarily, though, when the backup options (files or memory blocks) are first created, all memory pages are mirror-copied.  
         [0044]    Still referring to FIG. 2, in order to snapshot and remap the Memory Page Pool, some construction information for Memory Blocks and Memory Servers is kept in the configure files  711 ,  713 ,  718 . The Memory Page Pool can have different sized page blocks. They are normally used for two purposes, one for client applications, and the other for internal use in Memory Page Pool. For easy description, the pages used for client applications are called Client Pages, and the pages used internally are called Management Pages. As expected, the majority of memory pages in the Memory Page Pool are Client Pages, and Client Pages are normally larger than Management Pages.  
         [0045]    All the per-Client-Page construction links (between page to page, etc.) and information (such as security control bits) are kept in one or more memory blocks of Management Pages. All the construction links use the DMCE Virtual Address. Therefore by using the backup options (files or memory blocks) of those Management-Page Memory Blocks, the internal structure of Memory Page Pool is remembered, and backed-up like a snapshot, e.g., an exact replica of the Memory Page Pool at the time of shut down. Thus, memory can be restored whenever needed.  
         [0046]    Client Page mirroring is similar to the Management Page mirroring. Client Pages are used by client applications to store data and data structures. All data and data structure links and pointers on Client Pages use the DMCE Virtual Address. Therefore, by using the backup options (files or memory blocks) of those Client-Page Memory Blocks, the data and data structures of client applications are copied and stored in their exact form at the time of shut down, like a snapshot. Thus, they are quickly retrieved and restored whenever necessary.  
         [0047]    An Application Programming Interface (API) as part of overall DMCE Extended Memory Management is provided for a client application to access the mapped data and data structures stored on Client Pages, when the Memory Page Pool is linked with client application directly. If the DMCE Extended Memory Management is embedded into the underlying Operating System, then accessing those pages may be handled transparently by a modified memory management unit of the underlying Operating System. These systems and methods of adapting the operating system to work with DMCE are described in application Ser. No. 10/347,677; for “Distributed Memory Computing Environment and Implementation Thereof;” Filed Jan. 22, 2003; Attorney Docket Number 0299-0006; Inventors: Tianlong Chen, Jonathan Vu, Yingbin Wang.  
         [0048]    Referring to FIGS. 3 and 4, a conceptual block diagram of an embodiment of a memory page handling structure inside a Memory Page Pool is illustrated. The diagram and description of FIG. 3 is disclosed in patent application Ser. No. 10/347,678; for “Memory-Resident Database Management System and Implementation Thereof” Filed on Jan. 22, 2003; Attorney Docket Number 0299-0005; Inventors: Tianlong Chen, Jonathan Vu.  
         [0049]    The double-linked structure shown in FIGS. 3 and 4 is intended to handle fast, re-usable client pages without experiencing memory fragmentation problems often found in regular memory management systems. It will be appreciated by one skilled in the art that re-usable client pages may be handled in a variety of ways. A preferred method of handling re-useable client pages is further described below.  
         [0050]    Referring to FIGS. 3 and 4, MEM Pages  136  are made from Client Pages. Link nodes  130  are made from Management Pages, where each MEM Page  136  has an associated link node. The starting point of this construction is shown on FIG. 8 in which one Client-Page Memory Block and one Management-Page Memory Block are allocated, and so are their associated Memory Block ID entries in Memory Block ID Lookup Table configure files and log files, as described above. Both Memory Blocks have the same number of memory pages. However, the size of the Client Page  750  may be different than that of Management Page  751 . The 1 st  memory page in Client-Page Memory Block is associated with the 1 st  memory page in Management-Page Memory Block, and so on.  
         [0051]    Referring to FIG. 3, MEM Page  136  keeps  132  a pointer  135  to its associated link node  130 , and the link node  130  keeps  133  a pointer  134  to its associated MEM Page  136 . Therefore, MEM Page  136  and its associated link node  130  can cross reference to each other. The link nodes  130  are double-linked  131  together. One double-linked list keeps tracks all used pages  140 . The other double-linked list tracks all unused pages  150 . At the fresh beginning of system (system start up), all MEM Pages are linked under the Unused List  150 . When MEM Pages are allocated by client applications, the allocated pages are moved from the Unused List  150  to Used List  140 . And when application frees allocated memory pages, the freed pages are moved from Used List  140  to Unused List  150 .  
         [0052]    There are several ways to track changed pages for back-up. One is to create a third double-linked list as shown in FIG. 4. With the third double-linked list, Client Pages may be in three stages, Unused  805 , Used  806  (with no change, or change has been updated) and Changed  804 . When an application requests new pages, allocated pages are moved  810  from the Unused List  805  to the Used List  806 . When pages are changed, the changed pages are moved  809  from the Used List  806  to the Changed List  804 . After changed pages are backed-up, they are moved  807  from the Changed List  804  to the Used List  806 , if the change is not freeing the pages. Pages are moved  808  from the Changed List  804  to the Unused List  805  if the change is made to free the pages. One or more threads (called backup threads), normally running as background threads and at low priority (configurable), run in the system to check Changed Lists  804  and to do the backup work.  
         [0053]    Referring to FIG. 5, another way to track changed pages for back-up is to keep a record for each page indicating whether it is changed, where pages  851  are not changed, and pages  852  are changed. When tracking changes in this manner, the backup threads will loop through memory pages for changed pages and synchronize them with backup options (file or memory blocks).  
         [0054]    The above two changed-page tracking methods are more preferable in different circumstances. Note that only memory blocks with memory pages that can be changed at run time are constantly checked by the backup threads. Both Client-Page Memory Block and Management-Page Memory Block can be marked as no change. The memory blocks with no-change mark are backed-up only once and will not be checked any more by the backup threads.  
         [0055]    In order to provide fast logging capability for backup and recovery, the Memory pages with disk-based or memory-block backup in the Memory Page Pool can be used. First, one or more Management-Page Memory Blocks with disk-based file backup are allocated. Then, log information is put in the memory pages, relying on the Memory Blocks&#39; backup option to reliably log the memory page transactions.  
         [0056]    Referring to FIG. 3 and  7 , if per-memory-page security control is desired, security control bits are either stored in MEM pages  136  or their associated link nodes  130 . The number of bits depends on how complicated a security control is needed. Then, each request for accessing the memory pages with security control requires security bits from the requesting applications.  
         [0057]    Another system and method of handling memory pages is a variation of double-linked list of FIG. 3. The variation is done by removing the link  135  from MEM Page  136  to its associated link node  130 , and not storing management information is stored in MEM Pages  136 . Security bits and, optionally, a page-changed mark are all stored in the link nodes. This way, there are no cross-references between MEM Pages  136  and their associated link nodes  130 . Thus, each MEM Page  136  and its link node  130  are always handled together. This increases the complexity of other parts of EMMU, such as the DMCE Memory Cache which is disclosed in Patent Application “Single Computer Distributed Memory Computing Environment and Implementation Thereof” mentioned in the CROSS-REFERENCE section above. The merit of this handling structure is that the application can write continuous memory pages at one time, whereas the system and method of handling memory pages as shown in FIG. 3, does not allow for continuous page writing. Otherwise, the link pointer from MEM Page  136  to its associated link node  130  would be corrupted. Removing the link is preferable for those applications in which data is loaded at the beginning, and seldom or never updated.  
         [0058]    In various Distributed Memory Computing Environment architectures, the Memory Server ID may be called a Device ID. In such cases, the Memory Server ID Lookup Table is also referred to as a Memory Device ID Lookup Table.  
         [0059]    The foregoing description of the preferred embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. The embodiment was chosen and described in order to explain the principles of the invention and its practical application to enable one skilled in the art to utilize the invention in various embodiments as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto, and their equivalents. The entirety of each of the aforementioned documents is incorporated by reference herein.

Technology Category: 3