Memory stacks management

A method for managing a memory stack provides mapping a part of the memory stack to a span of fast memory and a part of the memory stack to a span of slow memory, wherein the fast memory provides access speed substantially higher than the access speed provided by the slow memory.

DESCRIPTION OF THE RELATED ART

Most computing systems employ the concept of a “stack” to hold memory variables associated with one or more active subroutine or process threads (collectively referred to herein as “subroutine”). When a new subroutine is called, a stack related thereto grows in order to provide space for the temporary variables of such subroutines. When execution control is transferred from a first subroutine to a second subroutine, the registers used by the first subroutine are pushed onto the stack as well. Subsequently, after the second subroutine is done executing, the register contents may be restored. As subroutine calls nest within one another, the stack continues to grow, such that the temporary variables associated with the active portion subroutine are at the top of the stack. A system designer needs to ensure that enough memory space is available for a stack to grow to its worst-case size, which is associated with the deepest level of subroutine nesting that may occur in the system. On the other hand, growth of stacks to worst-case size may result in inefficient utilization of stack allocation space and may slow the performance of a computing system in cases where the computing system runs out of available stack allocation space.

SUMMARY

Implementations described and claimed herein provide for the managing of memory stacks across different physical memories. A method for managing a memory stack provides mapping a part of the memory stack to a span of fast memory and a part of the memory stack to a span of slow memory, wherein the fast memory provides access speed substantially higher than the access speed provided by the slow memory. In an implementation, the fast memory is tightly integrated with a processor. This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. These and various other features and advantages will be apparent from a reading of the following detailed description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

DETAILED DESCRIPTION

FIG. 1illustrates an example computing system160including a motherboard162and a hard disc drive (HDD)164. The computing system160may be any server, desktop, laptop, or other computing system. The computing system160, for example, operatively couples various system components (e.g., HDD164) using at least the motherboard162. In one implementation, the motherboard162and the HDD164are connected together via a Serial ATA interface166, however, other connection schemes are contemplated. Through the motherboard162, the computer controls operation of the HDD164.

Both the motherboard162and the HDD164are powered by a power supply168that converts incoming AC power to DC power, step down an incoming voltage, step-up the incoming voltage, and/or limit current available to the motherboard162and the HDD164. In one implementation, power for the HDD164comes from the power supply168through the motherboard162.

The HDD164is equipped with a disc pack170, which is mounted on a spindle motor (not shown). The disk pack170includes one or more individual disks, which rotate in a direction indicated by arrow172about a central axis174. Each disk has an associated disc read/write head slider176for communication with the disk surface. The slider176is attached to one end of an actuator arm178that rotates about a pivot point179to position the slider176over a desired data track on a disk within the disk pack170.

The HDD164is also equipped with a disc controller180that controls operation of the HDD164. In one implementation, the disc controller180resides on a printed circuit board (PCB). The disc controller180may include a system-on-a-chip (SOC)182that combines some, many, or all functions of the PCB180on a single integrated circuit. Alternatively, the functions of the PCB180are spread out over a number of integrated circuits within one package (i.e., SIP). In an alternate implementation, the disc controller180includes controller firmware.

The computing system160also has internal memory such as random access memory (RAM)190and read only memory (ROM)192. Furthermore, the motherboard162has various registers or other form of memory. Such memory residing on the motherboard162is accessible by one or more processors on the motherboard162at a higher speed compared to the speed at which such processors can generally access RAM190, ROM192, etc. Therefore, such memory residing on the motherboard162is referred to as the tightly integrated memory (TIM), also referred to sometime as a tightly coupled memory (TCM) or high speed memory. However, in alternate implementation the term TIM may also be used to refer to other memory module that is accessible by one or more processor in a high speed manner.

One or more of the memory modules, such as the RAM190, the ROM192, various TIM resident on the motherboard, and the memory provided by the HDD164, are used to store one or more computer programs, such as the operating system, etc. Such computer programs use a number of functions, routines, subroutines, and other program structures to store instructions, wherein the instructions are processed using one or more processors of the computer. A subroutine may be called to process a number of instructions in an iterative manner and a computer program calling a subroutine generally provides a number of parameters to a called subroutine. At any point during execution of a computer program a number of subroutines may be active and in various stages of processing. Any time a subroutine calls another subroutine, or passes control to another subroutine, the calling subroutine stores the present values of various temporary parameters in a memory until the control is passed back from the called subroutine to the calling subroutine.

In one implementation, the SOC182uses a stack to hold temporary variables associated with an active subroutine. In one implementation a number of subroutines related to a process thread shares a stack. In one implementation, an application that is written on one thread uses one stack. However, an application that is multi-threaded may use multiple stacks. Each time a new subroutine is called, the stack grows to provide enough space for the temporary variables of the new subroutine. Further, because subroutine calls “nest” within one another, the stack continues to grow with more subroutine calls. A stack is a last-in-first-out (LIFO) storage structure where new storage is allocated and de-allocated at one end, called the “top” of the stack.

FIG. 2illustrates an example of a stack200. For example, when a program begins executing its main( ) function202, space is allocated on the initial part of the stack for the variables declared within the main( ) function202. If the main( ) function202calls a function func1( )204, additional storage is allocated for the variables in the func1( ) at the top of the stack200as shown by stack200a. Note that at this point the parameters passed by main( ) function202are stored at the bottom of the stack200. If the function func1( )204were to call any additional functions, storage for such new function would be allocated at the top of the stack. When the function func1( )204returns, storage for its local variables in de-allocated, and the top of the stack200returns to the position as shown by stack200b. WhileFIG. 2illustrates operation of a stack with respect to a function, stacks operate in similar manner with respect to routines, subroutines, etc. As seen inFIG. 2, the temporary variables associated with the active portion of the subroutine/function are located at the “top” of the stack.

In an alternate arrangement of stacks, stacks are designed in a memory space so as to grow downwards in a given address space. In such an example, the initial part of the stack is at the top of the stack. An example is a reverse stack200cillustrated inFIG. 3. The reverse stack200cgrows towards lower memory addresses as shown by the arrow210. Thus the space for the main( ) function202is allocated at top of the stack202c. In such a reverse stack, the temporary variables associated with the active portion of the subroutine/function are located at the “bottom” of the reverse stack.

Computing systems generally allow for the stack to grow to the “worst-case” size of the stack. The “worst-case” size of the stack is associated with the deepest level of subroutine nesting that occurs in the system. Providing for sufficient tightly integrated memory (TIM) or high speed memory, such as data tightly-coupled memory (DTCM) to account for the “worst-case” size of the stack can be cost prohibitive. Further, multi-tasking computing systems have a different stack for each task (or thread) that is active. Providing for sufficient high speed memory, such as DTCM (used herein to refer to any high speed memory or tightly integrated memory) to account for the “worst-case” size of the each stack that is active can result in inefficient utilization of the DTCM.

Generally, stacks operate at or near empty condition. However, the nesting level increases significantly in error paths. As a result, stacks get substantially filled in error paths. This is especially true in controller firmware, where expensive DTCM is used to host stacks. Therefore, when a controller firmware enters an error path, expensive DTCM is used up to store the parameters resulting from the deep nesting resulting from controller firmware entering into an error path. Performance, however, is not crucial in error paths. Thus, providing for sufficient high speed memory, such as DTCM, to account for the “worst-case” size of error paths is unnecessary.

FIG. 3illustrates an example mapping300of stacks across different physical memories. The mapping300includes a DTCM addressable space302and a data direct buffer access (DDBA) addressable space304. The term DDBA is used herein to specify any memory that is generally not tightly coupled and as such it provides slower access speed compared to tightly coupled memory such as the DTCM. Generally, DDBA or similar memory is cheaper in terms of cost compared to the DTCM. The DTCM addressable space302is divided into a number of addressable pages of equal size. These DTCM addressable pages are denoted as DTCM0, DTCM1. . . DTCM14. In the illustrated mapping300, it is assumed that the first eight pages of the DTCM memory, DTCM0to DTCM7are shown to be used as providing stack space. For example, if 8 KB of the addressable DTCM space302is used for providing stacks, it may be divided into eight pages, each of eight pages DTCM0to DTCM7will be of 1 KB. The DDBA addressable space304is also divided into a number of addressable pages of equal size, denoted as DDBA0, DDBA1. . . DDBA7with each of the DDBA page being the same size as the DTCM page. In one implementation of the mapping300, the number of pages in the DDBA304is set to be equal to the number of pages in the DTCM302that are used for providing stacks.

FIG. 3also includes a virtual address space region A306and a virtual address space region B308. Each of the region A306and the region B308are also divided into a number of pages equal to the number of DTCM pages used for providing stacks. The size of the pages in the region A306and the region B308are the same as the size of the DTCM pages. Furthermore,FIG. 3also shows a memory management unit (MMU)310that would allow applicable firmware to alias particular pages of the DTCM addressable space302into one of the two virtual address space regions306and308. The number of bits in the MMU310is set to be equal to the number of pages in the DTCM addressable space302used for providing stacks. Therefore, in the example illustrated inFIG. 3, the MMU310has eight bits.

Each bit of the MMU310is assigned a value of zero (0) or one (1) depending upon whether a corresponding page in the DTCM is to be aliased to the virtual address space region A306or to the region B308. The process of determining the values of each bit is described in further detail below. Note that because there are two virtual address space regions A306and B308, if a separate MMU were to be used for the virtual address space B, the values of the bits in such an MMU for the virtual address space B would be complement to their values in the MMU310. For example, if bit7had a value of 1 in MMU310, corresponding bit7in the MMU for the virtual address space B would have a value of 0, and vice versa.

FIG. 4illustrates a flowchart400of a process of assigning a virtual address space from one of the virtual address space region A306and the virtual address space region B308to a DTCM page. Generally, stacks are setup before starting execution of a program or a thread. In one implementation, the size of the stack is determined based on some logic that determines a stack size that is adapted for performance or functioning of the program. For example, in one implementation, an initialization logic determines that for a first stack 4K of high speed memory size is required so that first stack has 4K of high speed memory such as DTCM and after that the first stack spans low speed memory such as DDBA. In an alternate case, the initialization logic determines that for a second stack 4K of high speed memory size is required so that the second stack has 8K of high speed memory such as DTCM and after that the second stack spans low speed memory such as DDBA. At block402determines if there is any outstanding request for a new stack in the DTCM302. If no request is outstanding, control passes further down to a block410. If block402determines that there is a request for a new stack, control is transferred to a block404. Block404selects the lowest unused and unassigned DTCM page for creating such a stack. Thus, for example, if there are no other stacks in the DTCM addressable space, block404selects DTCM0page for creating the stack (referred to here as Stack1).

Subsequently, at block406the lowest unused virtual page of the virtual address space region A306is made addressable to the DTCM0. Thus, in the example disclosed herein, VA0is made addressable to DTCM0. The mapping of VA0to DTCM0is shown inFIG. 5at502. If this was a very first stack, either of the virtual address space region A306or the virtual address space region B308is used to initiate such assignment of a virtual page to the DTCM. A block408changes the value of a bit corresponding to the DTCM0page to 1, as shown inFIG. 5at504.

Subsequently, a block410determines if there is additional space required for any existing stack to grow. In the present case, with Stack1being open, block410determines is Stack1, based in DTCM0requires more memory. However, in an alternate situation, block410reviews more than one existing stacks to see if there is any growth in any of such stacks. Such additional space requirement is due to calls to new subroutines, functions, etc. Note that the size of DTCM0may be sufficient to save variables/parameters for function/subroutine calls up to a certain level of nesting. However, if the stack grows larger, it may need more space than just that provided by the DTCM0page. As discussed above, one example condition where this happens is in the case when one or more program enters into an error loop, in which case, it makes multiple calls to the same function/subroutine, causing the stack to grow.

In such a case, a block412maps the virtual page above the page which is mapped to the DTCM0, in this case VA1, to a page in the DDBA address space304. As a result, the values and parameters related to the later called functions/subroutines are mapped to a cheaper/slower memory. Given that empirically, stacks do not grow beyond certain size, except in cases when a program has entered into an error loop, allowing stacks to grow in slower/cheaper memory such as DDBA memory304allows more stacks to be mapped to the expensive DTCM memory302.

In the current case, for example, suppose that Stack1grows to require between two and three pages of memory. In this case, as shown inFIG. 5at506, VA1and VA2are both mapped to the DDBA memory space304, specifically to DDBA1and DDBA2, over next several iterations of the program400. Because the virtual address space region B308is complementary to the virtual address space region A306, as shown by508inFIG. 5, VB1and VB2will both be automatically mapped to DTCM, specifically to DTCM1and DTCM2. Subsequently, block414changes the value of a bit corresponding to the DTCM1and DTCM2page to 0, as shown inFIG. 5at510.

If during a next iteration, block402determines that a second stack, Stack2, needs to be opened, block404will select lowest unassigned DTCM space. In the present case, such as page is DTCM1. Note that DTCM1is already mapped to the virtual address space region B308at VB1. Therefore, at block406, Stack2will be assigned to DTCM1and mapped to VB1. In this case, because the MMU bit related to the pages DTCM1is already set at 0, block408does not need to change the MMU bit related to DTCM1.

Subsequently block410monitors for growth of both Stack1and Stack2. If during any iteration, if Stack2grows, it is allowed to grow further in the virtual address space region B308. At the same time, if there is growth in Stack1, it is allowed to continue growing in the virtual address space region A306. In the present example, suppose that over a number of iterations, Stack2grows to occupy more than two but less than three pages worth of memory. In this case, Stack2takes up three consecutive pages in the virtual address space region B308, as shown by512inFIG. 5. During an iteration when block406determines that Stack2needs to grow beyond VB2to VB3, it maps the VB3to DDBA304. This is due to the fact that the top part of the stack, when possible, should be allocated to slow memory. Because VB3is mapped to DDBA304, VA3, being complementary to VB3, will be mapped to the DTCM302. Therefore, subsequently, block408will change the MMU corresponding to DTCM3to1, as shown by514inFIG. 5. Again this is consistent with the structure of the virtual address space region A306and the virtual address space region B308in that mapping of each page in these regions are complementary to each other.

The system disclosed inFIG. 3, with two virtual address space regions306and308, allows two active stacks to be allocated at the same time. As such, if at any time block402determines that a third new stack, Stack3, needs to be allocated, such a new stack will be allocated at the lowest unused and unassigned DTCM page. In the present case, as discussed above, due to the growth of Stack1and Stack2, DTCM0to DTCM2are already used and assigned to one of the virtual address space region A306and the virtual address space region B308. Therefore, block404will select DTCM3to start Stack3. Because in the previous iteration when VB3was mapped to DDBA, VA3was mapped to DTCM3, block406does not need to assign DTCM3to VA3. Furthermore, because the MMU control bit related to DTCM3is already set to 1, block408does not need to change the control bit.

Subsequently, Stack3is allowed to grow in the virtual address space region A306with any subsequent pages assigned to Stack3being mapped to DDBA304. Note that once Stack3is initiated at DTCM3and assigned to initiate at VA3, it would not be possible to allow further growth in Stack1. To avoid this problem, in one implementation, the number of stacks supported by the implementation is two. Alternatively, Stack1is assigned non-contiguous pages of the virtual address space region A306. Thus, if Stack3was initiated at DTCM3and assigned to VA3, if there is a need for Stack1to grow, it is allowed to grow with the next available page of the virtual address space region A306providing further growth opportunity. In this case, VA4may be used for further growth of Stack1or Stack3, whichever needs additional pages. Furthermore, because these are additional pages towards the top of the stack, they would be, when possible, mapped to DDBA304. However, in certain cases it is possible that the growth of Stack2has already caused the next available pages in the virtual address space region A306to be mapped to the DTCM302.

While the above implementation provides two virtual address space regions, in an alternate implementation, more than two virtual address space regions are provided.FIG. 6illustrates such an alternate implementation of a stack management system600, with eight virtual address space regions.

Note that in the above implementation eight virtual address space regions, each virtual address space region corresponding to one pageable space of the DTCM address space602is provided. In an alternate implementation, any other number of virtual address space regions may also be provided. Specifically, the implementation of the stack management system600illustrated inFIG. 6illustrates a DTCM address space602and a DDBA address space604that is used for supporting one or more stacks.

The stack management system600also includes eight virtual address space regions, namely virtual address space region A606to virtual address space region H610(not all virtual address space regions shown here). Because there are eight DTCM pages and eight virtual address space regions in this implementation, each DTCM page can be mapped to one of the eight virtual address space regions. Specifically, each of the DTCM pages that supports a stack is mapped to a bottom page of one of the eight virtual address space regions606-610. For example, if at any given time, the first three DTCM pages DTCM0to DTCM2are used to support stacks, these three pages are mapped to VA0, VB0, and VC0, respectively.

The remaining pages of the virtual address space regions606-610are mapped to specific regions of the DDBA address space604. For example, VA1to VA7are mapped to DDBA1to DDBA7, whereas VB1to VB7are mapped to DDBA65to DDBA71(not shown herein).

In one example implementation, the allocation of a DTCM page is controlled by an MMU620. Each bit of the MMU620designates whether the corresponding page of the DTCM address space602is used for supporting a stack or not. Thus, for example, before the allocation of stacks is initiated, each of the MMU control bits will be assigned a value of 0. In the example discussed above, if the first three DTCM pages DTCM0to DTCM2are used to support stacks, the MMU control bits for these three pages will be changes to 1, as shown by622inFIG. 6.

The stack management system600allows each addressable page of the DTCM address space602to be used to initiate a new stack and then allowing the stack to grow in one of the eight virtual address space regions606to610. A method of allocating stacks to one of the various virtual address spaces is disclosed in further detail by a flowchart700illustrated inFIG. 7. Specifically, the flowchart700illustrates a method of allowing more than one stacks that are initiated in DTCM602, or in a similar fast memory, to grow in the DDBA604, or similar slow memory. Thus, the method provided by the flowchart700provides for an efficient allocation of DTCM602to the bottom (or initial) part of various stacks. Given the empirical evidence that generally stacks do not grow too large and that they grow to large size in case when a program enters an error loop, etc., such method allows optimizing use of expensive memory such as DTCM602.

Now referring toFIG. 7, it is assumed that the first eight pages of the DTCM address space602are used for providing stacks. However, in an alternate implementation, a larger or smaller number of pages are used to allocate stacks. The flowchart700provides for continuous monitoring of whether a new stack needs to be allocated or not, whether there is a request for growth in one of the existing stacks, and whether one or more previously allocated stack has been released.

Specifically, a block702determines if a new stack needs to be allocated. If a new stack needs to be allocated, a block704selects the lowest unused DTCM page to initiate the requested stack. The block704also changes the value of an MMU bit related to that particular DTCM page to 1 to indicate that the particular DTCM page is being used to support a stack. Subsequently a block706assigns the new stack to one of the unused virtual address space region A606—virtual address space region H610. In an implementation of stack management system600wherein the number of addressable pages in the DTCM602is same as the number of virtual address space regions (in this implementation, each is equal to eight), an MMU control unit is not provided for each of the virtual address space regions. Specifically, in such an implementation, each of the virtual address space regions606-610will have its lowest addressable page, namely VA0, VB0, . . . VH0mapped to the DTCM address space602whereas each of the higher addressable pages, VA1-VA7, . . . VH1-VH7, mapped to the DDBA address space604.

After assigning one of the virtual address space regions to a stack, a block708monitors growth in that stack. Upon detecting growth in a given stack, block710maps subsequent pages of the virtual address space that is mapped to the given stack to the DDBA address space604. Note that in the present case, because each DTCM page of the DTCM address space602is mapped to the bottom page of the virtual address space regions A606-H610, respectively and as necessary, there is no need for using an MMU bit in a manner described above inFIG. 3, where two virtual address space regions were used.

However, in the system illustrated byFIGS. 6 and 7, the MMU620is used to indicate whether a given DTCM page is in use or not. For example, often during the operation of a program, a subroutines called from a program is completed and in such a case, there is no need to keep the stack that was generated as a result of call to that subroutine. In such a case, a DTCM page that was used to initiate a stack upon call to that particular subroutine becomes available for generating future stacks.

A block712determines if any DTCM page that was earlier assigned a stack has become available. If so, a block714changes an MMU bit related to that DTCM page to 0. However, if it is determined that no new DTCM pages have become available, no change to any MMU bit is made. Even though in the implementation described herein, the program700provides the appropriate monitoring of DTCM pages being used for stack allocation, in an alternate implementation, a microprocessor or other unit that is responsible for allocating stacks monitors and changes MMU bits as necessary.

The implementations described herein may be implemented as logical steps in one or more computer systems. The logical operations of the various implementations described herein are implemented (1) as a sequence of processor-implemented steps executing in one or more computer systems and (2) as interconnected machine or circuit modules within one or more computer systems. The implementation is a matter of choice, dependent on the performance requirements of the computer system implementing the method and system described herein. Accordingly, the logical operations making up the implementations described herein are referred to variously as operations, blocks, objects, or modules. Furthermore, it should be understood that logical operations may be performed in any order, unless explicitly claimed otherwise or a specific order is inherently necessitated by the claim language.

In the interest of clarity, not all of the routine functions of the implementations described herein are shown and described. It will be appreciated that in the development of any such actual implementation, numerous implementation-specific decisions are made in order to achieve the developer's specific goals, such as compliance with application—and business-related constraints, and that those specific goals will vary from one implementation to another and from one developer to another.

The above specification, examples, and data provide a complete description of the structure and use of example implementations. Because many alternate implementations can be made without departing from the spirit and scope of the invention, the invention resides in the claims hereinafter appended. Furthermore, structural features of the different implementations may be combined in yet another implementation without departing from the recited claims.