Method and Apparatus for Implementing Virtual Memory Having Multiple Selected Page Sizes

The present invention relates to a method and apparatus for implementing virtual memory having multiple selected page sizes, and more particularly to a memory management system and method for implementing virtual memory which uses pools of multiple size buffers to store statistically predictable variable but bounded length data buffers for communications, multimedia or other systems that benefit from efficient utilization of memory.

FIG. 1 illustrates a prior art virtual memory arrangement where pages are mapped by a mapping mechanism from a virtual address to a physical address. FIG. 2 illustrates a traditional form of the mapping mechanism. The virtual address includes a page identifier and an offset in page. The virtual address page identifier is indexed with a page table. The page table includes a physical page address and a valid bit indicating whether the mapping is valid. If a valid bit is on, the page table supplies the physical page number or starting address of the page in memory. If the valid bit is off, then the page is not present in memory. The physical address includes the physical page base address concatenated with the virtual address offset in page. FIG. 3 illustrates the traditional form of segmented virtual address mapping for a variable-size data block. In the segmented virtual memory, the virtual address also includes a segment identifier that is indexed to a segment table including a valid bit, a page table address, and page table size. The virtual address page identification and the segment table page table size are supplied to a size check function. The size check function output and the segment table base page address is indexed to a page table. The offset in page is concatenated with the physical base page address to produce the physical address.

Typically, virtual memory implementations, including segmented virtual memory, are based on fixed size buffers or pages. In some communications systems and in a multimedia environment, the use of fixed size buffers or pages leads to sub-optimal use of memory. Having many small pages induces an excess amount of memory management overhead. Having a smaller number of large pages decrease memory utilization. Using an intermediate page size can result in extra management overhead with decreased memory utilization.

In some communication systems, data frames are received from the network in small units called cells with arrival times interleaved with cells from other data frames. Asynchronous transfer mode (ATM) is an example of such a communications network. The cells are assembled to form larger data structures called frames. Until the last cell of a frame is received, the size of the final data structure (the frame) is not known. If the frame is to be managed as a contiguous memory object, this means that memory must be allocated for the largest size frame that will be received from the network. This can be very wasteful of memory.

It is possible to use linked lists and other structures to provide better granularity of memory utilization. Using these data structures in software carries with it the penalty of having to traverse lists, and to perform other address resolution operations to access the right area of memory. This is not an efficient operation when the data must be accessed randomly. Managing the data structures also increases processor workload. Doing a copy to a contiguous area of memory is not appealing, from either a performance or a memory utilization viewpoint.

Important objects of the present invention are to provide an improved method and system for implementing virtual memory; to provide such method and system having multiple selected page sizes; to provide such method and system which provides the appearance that the frame resides in a contiguous address space, without requiring the overhead of allocating a maximum sized buffer for each frame; and to provide such method and system overcoming disadvantages of prior art arrangements.

In brief, a method and apparatus for implementing virtual memory having multiple selected page sizes are provided. A virtual address includes a map index and a frame offset. A selector mechanism receives the virtual address frame offset and generates an offset and index. A frame map table indexes the virtual address map index and the selector generated index and generates a base address. The frame map table generated base address and the selector generated offset are combined to provide a physical address.

The present invention, together with the above and other objects and advantages may best be understood from the following detailed description of the preferred embodiments of the invention illustrated in the drawings, wherein:

FIG. 1 is a block diagram illustrating a prior art virtual address arrangement;

FIG. 2 is a block diagram illustrating a prior art traditional form of virtual address mapping;

FIG. 3 is a block diagram illustrating a prior art traditional form of segmented virtual address mapping;

FIG. 4 is a chart illustrating a probability distribution of frame lengths for a virtual memory system of the invention;

FIG. 5 is a logical block and data flow diagram illustrating a virtual memory management method and system of the invention;

FIG. 6 is a block diagram illustrating a virtual address system of the invention;

FIG. 7 is a block diagram illustrating a preferred embodiment of a virtual address system of the invention;

FIG. 8 illustrates an arrangement for a selector mechanism of the virtual address system of FIG. 6;

FIG. 9 illustrates a boundary logic function of the selector mechanism of FIG. 8;

FIGS. 10, 11 and 12 provide examples of the results provided by the boundary logic function of FIG. 9;

FIG. 13 provides an example of a memory map of the invention;

FIG. 14 is a logical block diagram illustrating a shifted page index generation function of the invention;

FIG. 15 is a logical block diagram illustrating an alternative shifted page index generation function of the invention;

FIG. 16 is a diagram illustrating a base address storage structure with a chain pointer and free lists organized as chains in accordance with the invention;

FIG. 16A is a diagram illustrating a base address storage structure with a stack organization of free lists in accordance with the invention; and

FIG. 17 is a flow chart illustrating sequential steps for generating an Index, Offset and Limit of the invention.

FIG. 4 shows a typical probability distribution of frame lengths for a virtual memory (VM) system. Relative frequency of the distribution of data frame sizes, packet sizes, object sizes, or the used portion of an allocated data segment is shown. In FIG. 4, the peaks of length frequency are approximately evenly spaced along the log scale. Vertical lines labeled 1-9 represent index numbers representing boundary values used in accordance with the invention for selecting one of the multiple selected page sizes. Even though FIG. 4 shows an approximately, evenly spaced distribution, the method of the invention can be used to store various statistically predictable variable but bounded length data buffers.

To support a VM system for the illustrated probability distribution of FIG. 4, using a fixed page size of very large pages results in significant internal fragmentation and memory wastage on small frames. Alternately, when using small fixed page sizes, a large page table is required to support the large frames. This large page table would be used for the small frames as well. This also results in memory wastage.

In accordance with the invention, multiple selected page sizes are used to provide effective memory utilization and effective memory management. The virtual memory (VM) management system of the invention uses pools of multiple selected size buffers to store statistically predictable variable but bounded length data buffers for communications, multimedia and other systems that would benefit from efficient utilization of memory. Like traditional virtual memory, the multiple selected page size virtual memory system of the invention presents a contiguous address space. Also like the traditional VM, not all of the virtual memory address space that is available has actual physical memory currently attached to it. The physical memory is allocated as the address space is used and recovered when the address segment or frame is deallocated or freed.

FIG. 6 is a block diagram illustrating the virtual address system of the invention generally designated by 10. The virtual address includes the Map Index and the Frame Offset. A selector mechanism 12 generates an Offset and the Index which represent boundaries of the Index Number of FIG. 4. The Offset from the selector mechanism 12 represents the distance from an Index Number 1-9 of FIG. 4. The address space between each boundary pair in FIG. 4 either has no memory associated with it or behind it or has a page of selected size providing physical storage because a multiplicity of sizes are used in this invention. The boundaries can be placed right after the probability peaks. This results in efficient memory utilization and a small map table. The Map Index 502 is indexed together with the Index from selector mechanism 12 with a frame map table 14 that provides a page base address. The frame map table 14 includes a map data and a valid bit indicating whether the mapping is valid. The page base address from the map table data and the Offset from the selector mechanism 12 are applied to an adder 16 providing a physical address 18.

FIG. 5 is a logical block and data flow diagram illustrating the virtual memory management method of the invention with data parsed from the virtual address and how that data is used during a memory access cycle. A virtual address is shown at a block 500. Virtual address 500 contains a Map Index derived at a block 502 and a Frame Offset derived at a block 504. The upper order bits of the virtual address contain the Map Index 502 which is also used as the Implicit Page Index at a block 506. The first page of the segment is addressed implicitly by the segment index with a one-to-one correspondence between the segment and the implicit first page. All frame address ranges have this implicit page index 506 which is a minimum amount of memory storage space allocated for each frame without additional address manipulation.

A check for a Map on chip is provided at a block 508. If the map is available, the data access is indexed from the map at a block 510. Otherwise, the map address is generated at a block 512 and the map is fetched from memory at a block 514.

The low order bits of the virtual address contain the Frame Offset 504. The Frame Offset 504 is used to determine which segment the access falls in and the location within that segment of the addressed memory location at a block 516. The Frame Offset 504 is illustrated and described in greater detail in FIG. 8. If determined that the memory location falls in the Implicit Page (or Segment One) at a decision block 518, no map reference is necessary and the index is selected at a block 520. However, if the Frame Offset is beyond the Implicit Page, the Page Map must be accessed to determine if a page has already been allocated for this space at a decision block 522. If it has not yet been assigned, a free page is taken from the free page list at a block 524. If no pages are available, the cycle terminates with errors posted at a block 526. Otherwise, the page index is stored in the Page Map at a decision block 528. If determined that the page Map for this virtual address has been changed at block 528, it must be marked for writing back to memory at some point. The map is written at block 530 with map processing completed at a block 532.

The Page Index is then used to generate the physical address at a block 534. The physical address is then used to access memory at a block 536. When the access is complete the cycle terminates normally at a block 538.

FIG. 7 is a block diagram illustrating a preferred embodiment of a virtual memory system generally designated by 20. VM system 20 includes a selector 22 that provides a Segment Index, Offset and an optional Limit. The Limit may be used to represent the number of additional addresses for this translation, so that the physical address can be incremented corresponding to the limit without doing an additional translation. The limit is useful for calculating burst limits in and out of memory. The Map Index is indexed together with the Segment Index from selector mechanism 22 with a frame map table 24 that provides a frame map table base address. The Segment Index is indexed to a page base table 26 and a segment size table 28. The page index 25 from the frame map data 24 is multiplied by a segment size from arbitrary boundary from the segment size table 28 by a multiplier 30. The base address size 1-K of page base table 26, the Offset of selector mechanism 22 and the multiplier output are applied to an adder 32 providing a physical address 34.

It is not necessary for each index to have its own additional size. Indexes may share both size and memory pools.

FIG. 8 illustrates an arrangement for the selector mechanism 12. Selector 12 includes a plurality of predefined page boundary blocks 40 (l through N) used in conjunction with an array of subtractors 42. The frame offset 504 is applied to the subtractors 42 to determine the particular segment in the page map should be used. The outputs of subtractors 42 are applied to a corresponding boundary logic block 44 (A) coupled to a multiplexor 46. The structure of the boundary logic block 44 is illustrated and described with respect to FIG. 9. Multiplexor 46 provides the Offset, Index and optional Implicit Page, Limit and Error outputs.

Referring to FIG. 9, the boundary logic function 44 receives inputs of sign bit X+1, sign bit X, sign bit X-1 and data, where sign bit X is true if Frame Offset--Boundary X is greater than or equal to zero. The outputs selected include if X+1 and Not X is true, then this data is selected for the Limit; if X and Not X-1 is true, then select this data for the Offset and X for the index; and the data. If the page selected is page 1, then the implicit page is selected.

FIGS. 10, 11 and 12 provide examples of the Offset, Limit, Index and Error results provided by selector 12 including the subtractors 42, boundary logic function 44. In FIG. 10, an Offset of 5, a Limit of 123, and an Index of 0 are provided with a Frame Offset of 5. In FIG. 11, an Offset of 860, a Limit of 164, and an Index of 2 are provided with a Frame Offset of 1500. In FIG. 12, an error is generated from the frame Frame Offset of 66177.

FIG. 13 provides an example of a memory map 50 that includes a first data buffer 52 for storing an interleaved map and implicit page and a plurality of data buffers 54, 56, 58 and 60 of the multiple selected page sizes 1, 2, 3 and 4 for storing data. The implicit page is not required to be included or interleaved but the preferred embodiment benefits from both.

FIG. 14 is a block diagram illustrating a shifted page index generation function of the invention generally designated by 68. Page index generation function 68 allows page sizes which are powers of 2, in which the page index is multiplied by the power of 2 by shifting the page index the amount which corresponds to the power of two. A segment size table 28 that stored the powers of 2 and a page index designated by 25 are coupled to a shifter 74 that provides a shifted page index. Shifter 74 can provide sequential shifting using a counter, or it may provide a fixed set of shift increments using a multiplexor. The shifted page index generation function 68 can be used instead of the multiplier 30.

FIG. 15 is a block diagram illustrating an alternative shifted page index generation function 76. A segment size table 28 stores a power of 2 shift data 80 and an adder bit 82. The page index 25 and power of 2 shift data 80 are coupled to a shifter 84. An adder 86 at the output of shifter 84, under control of the segment size table entry adder bit 82, adds the result of the shifter output to itself shifted back by one place. Function 76 has the effect of providing a sequence of size possibilities at relative factors of 1.5 rather than 2. If the shifter alone is used, 3 bits can encode the shifting of 8 different amounts. An example is provided in the following Table 1.

With the addition of the shift/adder enable bit 82, 4 bits provide the capabability for encoding 16 sizes which are closer together in size. This may allow a closer match to the usage statistics. Table 2 provides an example that includes results of the adder bit 82. This implementation will often be considerably smaller than a full multiplier.

FIG. 16 is a diagram illustrating a base address storage structure 92 including a chain pointer 94, a size or pool index region 94. A free list chain structure 98 includes a plurality of free lists 524 organized as chains. Storage free blocks are designated by SF and storage in use blocks are designated by SIU. A free list pointer 100 is used to point to the free list providing the chain organization.

U.S. patent application Ser. No. 08/221,140, filed Mar. 30, 1994, entitled SYSTEM AND METHOD FOR MANAGEMENT OF A PREDICTIVE SPLIT CACHE FOR SUPPORTING FIFO QUEUES (Docket No. RO993-051) discloses a cache technique for maintaining first-in first-out (FIFO) queues. The above-identified United States patent application is incorporated herein by reference.

In FIG. 16A, the free list 524 is organized as a stack in a memory 110 with the top of the stack cached in the memory controller. Elements of the free list 524 are stored in the stack in memory 110. Three pointers are used to create the stack data structure in memory, a stack base pointer 116, a stack limit pointer 112, and a stack entry pointer 114. Optionally, the top of the stack may be cached in a memory controller cache 118. Entries are added to the free list by adding them to the cache 118. When a free list 524 entry is needed, it is removed from the cache. When adding entries to the free list cache 118, if the cache is full, then the free list entry will be stored in the location of memory pointed to by the stack pointer 114 and the stack pointer will be incremented.

When a free list entry is needed it will be taken from the cache 118. If the cache 118 is empty, the stack pointer 114 will be decremented and the entry will be taken from memory location pointed to by the stack pointer. When the stack pointer is manipulated, the stack base pointer 116 and the stack limit pointer 112 will be checked to make sure that there is room in the stack to store the entry, and that there are entries on the stack.

It is also possible to store the free lists in a FIFO memory organization. The predictive split cache described in the above-identified patent application can be used in support of a first-in first-out (FIFO) organization of the various free lists 524 used in this invention. While the stack cached technique requires slightly less storage in the memory controller, the FIFO technique of free list management provides for more even memory usage and for much simpler debugging of system problems.

FIG. 17 is a flow chart illustrating sequential selector steps for generating an Index, Offset and Limit receiving inputs of the virtual address offset portion and a page size array. The sequential operations begin at a block 170 with setting Index to zero and the Offset to the virtual address offset portion. The Limit is set to Offset minus a page size array (index) at a block 172. Then it is determined if the Limit is greater than zero. If so, then the limit is set to -Limit at a block 176 to complete the selector steps. Otherwise, when the Limit less than or equal to zero, then the Index is incremented by one and the Offset is set to the Limit at a block 178. Then the sequential steps are repeated by returning to block 172.

While the present invention has been described with reference to details of the embodiments of the invention shown in the drawing, these details are not intended to limit the scope of the invention as claimed in the appended claims.