Method for managing buffers pool and a system using the method

Method and system for managing a buffers pool. The system may include a first processor coupled to a general memory having allocation ring and de-allocation ring portions; and a second processor to perform internal accounting of pointer(s) buffer(s). The second processor has an internal storage array logically divided into first and second storage spaces. The second processor releases temporarily un-required buffer(s) pointer(s) to the first storage space, or to the second storage space if the first storage space is full. The second processor utilizes allocated buffer(s) pointer(s) accumulated in the first storage space. The second processor is to cause a DMA engine to move a bulk of two or more buffer(s) pointer(s) from the allocation ring to the first storage space, and to move a bulk of two or more buffer(s) pointer(s) from the second storage space to the de-allocation ring.

FIELD OF THE DISCLOSURE

The present disclosure relates generally to the field of computers. More specifically, the present disclosure relates to a method for managing buffers pools.

BACKGROUND

Memory units, or elements, in which data and execution code words are stored, have long been playing a major role in computer systems. This is even more so with the ongoing increase in the number of information to be processed and the growth in the amount of, and the rate at which, data is exchanged between computer systems. A typical computer application involves insertion and retrieval of data into/from a memory of a computer. Since, in many cases, computers are required to process data at very high speeds, fast and efficient insertions/retrievals of data to/from memories are a must.

Typically, a computer system has a memory unit with fixed size, and managing the content of the memory is relatively easy if the computer system is based on a single processor, or controller. However, in many cases, computer systems include two or more processors, generally referred to as “multi processor environment”, for enabling them to process, or handle, several tasks simultaneously. For example, one processor of a computer system may handle tasks relating to a display screen, whereas a second processor may handle tasks relating to multimedia data. A third processor may handle communications between the computer system and another computer system, and so on. Managing a physical memory that is shared by several processors is harder than managing a memory that is used by a single processor, because each processor has its own memory requirements. That is, each processor has to be able to store and fetch data from the shared physical memory without being interfered by, or interfering with, normal operation of other processors. A memory sharing methodology has to be applied in order to enable fast and efficient usage of a memory in a multi-processor environment.

A popular memory sharing methodology involves using a number of independent memory buffer pools while allocating the available memory space of a computer system among the memory buffer pools. Memory buffer pools may then be allocated to each processor according to its memory requirements. If a processor no longer needs (for a certain amount of time) a buffer pool allocated to it, the buffer pool may be de-allocated from it for the sake of another processor that might need it. The process of, and the considerations (or policy used) for, allocating and de-allocating memory buffer pools is generally termed “management of buffer pools”. De-allocating a memory buffer pool is also termed “freeing a memory buffer pool”.

The way memory buffer pools are managed greatly influences the performance of the computer system. In general, when adopting a particular memory buffers pools managing methodology, one has to factor in workload and system properties that may vary over time. Another major factor is response time, which is the time required, for example, for allocating (for or during a task being processed) a single buffer from the buffer pool or to release a buffer back to the free buffer pool. More about memory buffers pools may be found, for example, in “Autonomic Buffer Pool Configuration in PostgresSQL” by Wendy Powley et al. (School of Computing, Queen's University, Kingston, ON, Canada).

U.S. Pat. No. 6,931,497, by Clayton et al. (Aug. 16, 2005), discloses shared memory management utilizing a free list of buffers indices. U.S. Pat. No. 6,931,497 teaches “receiving a first buffer allocation command from a first processor, the allocation command including a register address associated with a pool of buffers in a shared memory, determining whether a buffer is available in the buffer pool based upon a buffer index corresponding to a free buffer, and if a buffer is determined available allocating the buffer to the first processor”. The solution disclosed by U.S. Pat. No. 6,931,497 includes using a cenfralized hardware implementation of a buffer manager, and a dedicated memory is used for the buffer pools management, which resides within the buffer manager.

U.S. Pat. No. 5,432,908, by Heddes et al. (Jul. 11, 1995), discloses high speed buffer management of share memory using linked lists and plural buffer managers for processing multiple requests concurrently. U.S. Pat. No. 5,432,908 teaches a buffer control memory having as many sections for buffer-control records as buffers which is employed together with a buffer manager, which is problematic because this solution necessitates a dedicated memory and buffer manager.

In a typical computer system, the processor(s) accesses the physical memory by using a direct memory access (“DMA”) engine. In general, whenever a processor needs to read (fetch) or to write (store) data from/to the physical memory, the processor forwards to the DMA engine a corresponding DMA-read or DMA-write request, whichever the case may be. If a processor issues a DMA-read request, the DMA seeks the requested data in the memory and fetches a copy thereof to the requesting processor. Likewise, if a processor issues a DMA-write request, the DMA seeks a free space in the memory and stores the data in the free space. However, using a DMA engine is costly in terms of processing time because a DMA request typically consumes several clock cycles. Therefore, an aspect of “good” management of memory buffer pools is associated with reducing the number of DMA requests that are issued by the processor(s).

SUMMARY

As part of the present disclosure a multi processor data processing system is provided, which includes a first processor (HOST processor) functionally coupled to a general (usually the system's) memory having allocation ring and de-allocation ring portions for allocating and de-allocating buffer(s) pointer(s), respectively, and a second (network) processor having an internal storage array logically divided into first storage space and second storage space. The first storage space may be used for holding buffer(s) pointer(s) allocated for (and optionally buffer(s) pointer(s) released by) the second processor, and the second storage space may used for holding buffer(s) pointer(s) de-allocated by the second processor.

According to some embodiments of the present disclosure the second processor may be adapted to cause a direct memory access (DMA) engine to move a bulk of buffer(s) pointer(s) from the allocation ring to the first storage space (IN_CACHE) responsive to excessive usage of (or consuming all the) buffers by the second processor, and a bulk of buffer(s) pointer(s) from the second storage space (OUT_CACE) to the de-allocation ring responsive to excessive de-allocation (releasing) of buffers by the second processor. A logic boundary may divide the first storage space into the first storage part, for holding for use one or more allocated buffer(s) pointer(s), and a second storage part, for holding in standby one or more buffer(s) pointer(s) moved (using the DMA) from the allocation ring to the second processor. The second processor may utilize allocated buffer(s) pointer(s) stored in the first storage part or temporarily release un-required buffer(s) pointer(s) to the first storage part, or, if it is full, to the second storage space.

DETAILED DESCRIPTION

Unless specifically stated otherwise, as apparent from the following discussions, it is appreciated that throughout the specification terms such as “processing”, “computing”, “calculating”, “determining”, or the like, refer to the action and/or processes which may be performed by or on a computer or computing system, or similar electronic computing device, that manipulates and/or transforms data represented as physical, such as electronic, quantities within the computing system's registers and/or memories into other data similarly represented as physical quantities within the computing system's memories, registers or other such information storage, transmission or display devices.

The disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the disclosure is implemented in software, which includes but is not limited to firmware, resident software, microcode, or the like, which may be processed on a microprocessor or microcontroller.

Embodiments of the present disclosure may include apparatuses for performing the operations described herein. This apparatus may be specially constructed for the desired purposes, or it may comprise a general purpose computer selectively activated or reconfigured by a computer program stored in the computer.

The medium may be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium or the like. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, magnetic-optical disks, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, an optical disk, electrically programmable read-only memories (EPROMs), electrically erasable and programmable read only memories (EEPROMs), magnetic or optical cards, or any other type of media suitable for storing electronic instructions, and capable of being coupled to a computer system bus.

Referring now toFIG. 1, a general layout and functionality of a memory buffers pool management system (generally shown at100) is schematically illustrtated. Memory buffers pool management system100is a multi processor environment because it includes, according to this example, a first (control) processor (HOST)101and a second (network) processor (CPM)102. HOST101(the first processor) and CPM102(the second processor) may exchange data over data bus103. In some embodiments, an additional CPM similar to CPM102may coexist with HOST101.

In order to eschew lengthy DMA latency times, CPM102(the second processor) may maintain and manage several cache memory areas from/to which CPM102may try to allocate or free (release) buffers, if possible; that is, to allocate buffer(s) if there is a buffer pointer available in the cache, and to release buffer(s) if there is space available in the cache to accommodate the released buffer pointer(s). These cache areas are intended to temporarily hold buffer(s) pointer(s) pre-fetched from allocation ring (AR)122(for example) or to serve as an intermediator storage area for buffer(s) pointer(s) that are about to be returned to de-allocation (DAR)123, through DMA130(for example). By first accumulating buffers' pointers in these cache areas and then DMA'ing bulk buffers' pointers, CPM102may both reduce the number of DMA operations (requests) and eschew DMA waits. Using cache memory areas, as disclosed herein, has another advantage: CPM102may perform buffers allocation and buffers de-allocation substantially without interruptions, while DMA130may be reading or writing a bulk of handles. Put differently, the internal process (the process occurring inside CPM102) of buffers allocation and buffers de-allocation and the external process (the process occurring outside CPM102) of buffers allocation and buffers de-allocation may coexist without having a first process (for example the internal process) interfering with the other (the external) process. Yet another advantage is that during periods when the demand rate for buffers on the CPM102is of the same order as the release rate of buffers, buffers allocations and buffers de-allocations demands will be satisfied very efficiently using the cache memory inside CPM102, and without using DMA130at all. Accordingly, CPM102may include a local (an internal) memory (storage array) (shown at104) that may include two distinct areas: a first storage space (a buffer allocation (A) area, shown at105), called hereinafter an allocation cache or IN_CACHE and a second storage array (buffer de-allocation (D) area, shown at106), called hereinafter de-allocation cache or OUT_CACHE.

Memory buffers pool management system100may also include a general memory (generally shown at120), also sometimes called hereinafter the system's memory. HOST101may directly read data from and write data to (shown at107) system memory120. According to some embodiments of the present disclosure, a first memory area, or portion, (shown at121) of system memory120, hereinafeter referred to as Free Buffers Pool (“FBP”), may be dedicated to, or reserved for, buffer(s) pointer(s) associated with a free buffers pool; a second memory area, or portion, (shown at122) of system memory120, hereinafeter referred to as Allocation Ring (“AR”), may be dedicated to, or reserved for, buffer(s) pointer(s) associated with allocation of buffers to CPM102; and a third memory area, or portion, (shown at123) of system memory120, hereinafter referred to as De-Allocation Ring (“DAR”), may be dedicated to, or reserved for, buffer(s) pointer(s) associated with de-allocation of memory buffers that are no longer used, or required, by CPM102, at least not currently.

Host101may keep an external pointers accounting (“EPA”), which means that whenever the number of pointers contained in AR122gets below some threshold level, because CPM102already fetched many pointers from AR122, Host101may cause additional pointers to be moved (shown at161) from FBP121, which is the primary pointers reservoir in the system, to AR122, which is a secondary reservoir in the system for pointers that are yet to be allocated for CPM102(that is, should the need arise). In addition, Host101may cause de-allocated pointers (pointers that were released by CPM102) to be moved (shown at162) from DAR123to FBP121. By “external pointers accounting” is meant external to CPM102, as CPM102maintains an internal pointers accounting, as is fully described in connection withFIGS. 2 through 4.

System memory120may include, in addition to memory portions FBP121, AR122and DAR123, other memory areas (hereinafter collectively called data area, not shown), which may consist of empty and non-empty entries (entries that contain some data). According to some embodiments of the present disclosure, FBP121, AR122and DAR123may each contain a plurality of pointers, each of which may point at a different entry of the data area in system memory120. For example, pointer P1stored in entry124of FBP121may point at a first entry of the data area (not shown), whereas pointer P20in entry125of FBP121may point at another entry of the data area (not shown). Likewise, pointer P100stored in entry126of AR122may point at a third entry of the data area (not shown) and pointer P115in entry127of AR122may point at still another entry of the data area (not shown). Likewise, pointer P5stored in entry128of DAR123may point at yet another entry of the data area (not shown) and pointer P110in entry129of DAR123may point at still another entry of the data area (not shown).

In general, HOST101and CPM102manage the content of, or the pointers in, the entries of FBP121, AR122and DAR123, as described hereinafter, to allocate memory buffers to CPM102, and to de-allocate (free or release) therefrom memory buffers, according to actual needs of CPM102.

Being a network processor, a task of CPM102is to receive (generally shown at140) data from other devices over a data communication network, such as a packet switched network (“PSN”) and the like. CPM102may receive data in the form of data packets (for example). After receiving a data packet (shown at140) from the PSN (not shown), CPM102temporarily stores and processes the packet and then sends the packet as is, or (depending on the type of the packet) a modified version thereof to the PSN.

As part of an initialization step, HOST101may allocate for CPM102some memory buffers. By “allocate” is meant storing in IN_CACHE105at least one pointer that points at a specific memory buffer. Therefore, CPM102may choose a pointer (the pointer, if there is only one pointer in TN_CACHE105) to point at a memory buffer/space in which CPM102may temporarily store the received data packet (shown at140). Once the packet has been processed and sent to the PSN (not shown) by CPM102, CPM102may de-allocate (release) the memory buffer by inserting the (now unused, released or unrequired) buffer(s) pointer into IN_CACHE105, or to OUT_CACHE106if IN_CACHE105is full. Pointers released into OUT_CACHE106will be forwarded (moved or returned) by DMA130to DAR123, as is more fully described in connection withFIGS. 2 through 4. Unlike HOST101, CPM102cannot directly read (shown at163) data (fetch pointers) from AR122, nor can it directly write (shown at164) data (release pointers) to DAR123, but, rather, it can read from AR122and write to DAR123only through DMA130, by utilizing a GET pointer (get_ptr) (shown at151) to indicate to DMA130the location in AR122from which a requested pointers bulk can be obtained, and a PUT pointer (put_ptr) (shown at152) to indicate to DMA130the location in DAR123to which released pointers can be moved. As an example, get_ptr151is shown pointing (at153) at an entry155in AR122, and put_ptr152is shown pointing (at156) at an entry159of DAR123.

Referring now toFIG. 2, an exemplary IN_CACHE space (a first storage space) and OUT_CACHE space (a second storage space) are schematically shown. IN_CACHE200and OUT_CACHE250may be similar to IN_CACHE105and OUT_CACHE106, respectively, ofFIG. 1, and their functionality will be described in association withFIG. 1. CPM102may utilize IN_CACHE200and OUT_CACHE250to perform an internal pointers accounting. Performing an internal pointers accounting by CPM102means that, so long as demand (by CPM102) for pointers is substantially steady, CPM102takes pointers from, releases currently unrequired pointers to and reuses temporarily released pointers that are all contained within cache memory104(CPM102internal storage array). IN_CACHE200and OUT_CACHE250facilitate the internal pointers accounting in the way described hereinafter. However, if the internal pointers account gets out of balance, which situation may occur when IN_CACHE200can no longer provide CPM102with required pointers or when CPM102releases too many pointers, then CPM102may refresh IN_CACHE200and OUT_CACHE250by causing DMA130to fetch additional pointers from AR122to IN_CACHE200or to move pointers from OUT_CACHE250to DAR123, whichever the case may be.

According to some embodiments of the present disclosure IN_CACHE200may be used for both pointer(s)/buffer(s) allocation and pointers/buffer(s) de-allocation (buffer(s) releasing). OUT_CACHE250may be used as a second layer cache area in which empty data buffers pointers, which cannot be returned to IN_CACHE200(due to lacking space in IN_CACHE200), wait until they can be sent, through DMA130, back to DAR123. IN_CACHE200is typically used by CPM102more frequently than OUT_CACHE250because CPM102utilizes allocated buffer pointers in IN_CACHE200for its normal operation, which typically includes receiving, processing and transmitting packets, whereas OUT_CACHE250is only utilized by CPM102once in a while, for returning (de-allocating) unused, or unrequited, buffer(s) pointer(s) to DAR123in system memory120.

CPM102(the second processor) may be adapted to cause DMA130(shown atFIG. 1) to move a bulk of buffer(s) pointer(s) from AR122(shown atFIG. 1) to IN_CACHE200(the first storage space) responsive to excessive usage of buffers by CPM102, and a bulk of buffer(s) pointer(s) from OUT_CACHE250(the second storage space) to de-allocation ring DAR123(shown atFIG. 1) responsive to excessive de-allocation of buffers by CPM102(shown atFIG. 1).

According to some embodiments of the present disclosure IN_CACHE200may contain up to 16 pointers, indexed 0 through 15 (shown as cache index210), including pointers associated with (allocated) data buffers used by CPM102, and pointers associated with data buffers which are not used (de-allocated) by CPM102. That is, whenever a new empty data buffer is to be allocated to CPM102, a pointer to that data buffer may be taken from IN_CACHE200and whenever a data buffer is no longer used by CPM102, that data buffer is de-allocated by CPM102by returning the pointer associated with that data buffer to IN_CACHE200for later use, assuming that there is space for that pointer in IN_CACHE200. IN_CACHE200may periodically, or at times, become depleted of data buffers and, in such cases, a new batch of empty data buffers may have to be allocated to CPM102, by forwarding to IN_CACHE200(through DMA130) a corresponding set of pointers from AR122.

In order to allow CPM102to normally operate without interuptions while DMA130writes new data buffer(s) pointer(s) to IN_CACHE200IN_CACHE200(the first storage space in the internal storage array104) may be logically divided, about or in respect of a logic boundary203, into two, substantially independent, storage parts: a first storage part (shown at201) and a second storage part (shown at202). First storage part201may sometimes be used for, or be engaged in, normal CPM operations (and therefore will be called a “CPM part”), whereas second storage part202of IN_CACHE200may be used (during times when first storage part201is used as a CPM part) for, or may be engaged in, DMA operations (and therefore will be called a “DMA part”). The first and second storage parts are preferably equal in size so that DMA operation(s) will be substantially similar regardless of whichever part in IN_CACHE200(the first storage space) is used, at any given time, as a DMA part. This way, DMA operation(s) will be more efficient. Though the first and second storage parts may be initially set as CPM part and DMA part, respectively, the roles of the two parts (for example of CPM part201and DMA part202) of IN_CACHE200may change at other times, as is explained hereinafter. CPM102may independently utilize the CPM part (the part currently dedicated to CPM operations, for example part201) and the DMA part (the part currently dedicated to DMA operations, for example part202).

As is explained earlier, IN_CACHE200may periodically, or at times, become depleted of data buffer(s) pointer(s) and, in such cases, a new batch of empty data buffer(s) pointer(s) may have to be allocated to CPM102. By “become depleted of data buffer(s) pointer(s)” is meant using (by CPM102) more than the pointers (8 pointers in this example) contained in CPM part201. For example, it is assumed that CPM102has consumed pointers P1(shown at211) through P8(shown at212) which reside within the dedicated, or allowed, cache part (CPM part201), and that CPM102has started using pointers from the other cache part (DMA part202), for example pointer P9(shown at213). When pointers in DMA part202are started to be used by CPM102, it may be said that the logic boundary (shown at203) between DMA part202and CPM part201has been crossed, or violated.

When the logical boundary (shown at203) is crossed, and assuming that the previously, or last, issued DMA read operation (which reads pointers stored in AR122to IN_CACHE200) has completed, DMA part202and CPM part201change roles: part201of IN_CACHE200becomes dedicated now to DMA operations (rather than to CPM operations), until another boundary crossing occurs, and part202of IN_CACHE200becomes dedicated now to CPM operations (rather than to DMA operations), until another boundary crossing occurs. Once a change of roles occurs, CPM102may request a new DMA operation (for fetching a new set of pointers), which will result in the newly fetched pointers being stored in the newly dedicated DMA part201, previously the CPM part201. During a data buffer release (de-allocation), the pointer associated with the released data buffer may be released (inserted) into the currently active CPM part of IN_CACHE200if there is space for it. However, if there is no space available in the currently active CPM part of IN_CACHE200, the pointer (for example pointer P33, shown at251) may be temporarily stored in OUT_CACHE250, which may contain other pointers (for example pointers P30, shown at252, P31, shown at253, and P32, shown at254) that are not expected (at least not in the near future) to be used by CPM102and, therefore, these pointers (P30through P33) can be returned to DAR123. CPM102may move to DAR123(through DMA130) a predetermined number of pointers at a time. For example, CPM102may move two pointers at a time from OUT_CACHE250to DAR123, whereby to facilitate the reduction of DMA operations number. Regarding roles changes, the assumption that the previously, or last, issued DMA read operation (which reads pointers stored in AR122to IN_CACHE200) has completed is generally based on the system's overall timing aspects: allocating 8 buffers usually takes time that is long enough to enable the DMA to complete the reading of the next 8 pointers. A special signature can be written to a DMA area before issuing DMA read operation(s) and checked before switching roles to ensure that DMA operation(s) are completed.

It is noted that if logical boundary203is never crossed in the sense explained earlier (which is only theoretical), it means that CPM102does not require pointers other than the limited group of pointers already residing within the CPM part (for example CPM part201) in IN_CACHE200. In other words it means that CPM102may (theoretically) continue to use the same limited group of pointers by allocating pointers from that group, and if some pointers were de-allocated, by reallocating them. In such a case, CPM102may use different pointers in the CPM part (for example pointers P1(shown at211) and P2(shown at214) in CPM part201) and return (de-allocate) other pointers to the CPM part. As is explained earlier, if CPM102wants to de-allocate a pointer but the CPM part is full, CPM102may instead return the de-allocated pointer to the OUT_CACHE.

FIG. 3Ais a flow chart showing an exemplary method of how pointers may be allocated for a CPM such as CPM102ofFIG. 1.FIG. 3Bshows IN_CACHE200ofFIG. 2, but with a different exemplary content.FIG. 3Awill be now described in association withFIGS. 1 and 3B. When CPM102needs a pointer to a free buffer, allocate_buffer routine is called (shown at301). If the CPM part201is not empty (shown as No at step302), it means that CPM part201includes at least one more pointer that CPM102can use. Exemplary IN_CACHE200is shown inFIG. 3Bcontaining three more pointers (P1, P2and P3, collectively designated as320) that can be used by CPM102. Accordingly, at step303, the pointer to be used by CPM102may be found, or obtained, by decrementmg cache index210(cache index) and extracting the pointer residing within the entry associated with the decremented cache index. Referring again toFIG. 3B, if the current value of the cache_index is 11 (shown at321), then, in accordance with step303, the cache_index is decremented and the resulting cache_index value (10 in this example) points at, or is associated with (shown at322) pointer P3(shown at323), which is returned (at step304) as the resulting next pointer that will be used by CPM102.

If, however, CPM part201is empty (shown as Yes at step302), it means that CPM102already depleted, or exhausted, all of the pointers resources allocated for it in the current CPM part (part201for example) and, therefore, new pointers have to be fetched, or imported, from AR122. In order to facilitate the fetching of new pointers to IN_CACHE200, CPM102swaps, at step310, between CPM part201and DMA part202, which means that CPM part201and DMA part202change roles: CPM part201, which was found empty (shown as Yes at step302) and therefore failed to provide another pointer to CPM102, will be dedicated now to DMA operations (and therefore it may be called, until the next swap, DMA part201), and DMA part202, which can provide at least one pointer to CPM102, will be dedicated now to CPM operations (and therefore it may be called, until the next swap, CPM part202).

Swapping between CPM part201and DMA part202makes room in IN_CACHE200for new pointers and, therefore, at step311, it is checked whether new pointers can be fetched from the allocation ring (AR)122. If the allocation ring (AR122) in the system memory is empty (shown as Yes at step311), routine allocate_buffer returns a zero value (at step312). However, if the allocation ring in the system memory is not empty (shown as No at step311), then, in accordance with step313CPM102requests DMA130to fetch from the allocation ring (from AR122, for example) eight 4 byte blocks (a total of 32 bytes block), for example, where each pointer has a size of 4 bytes. A GET pointer (shown as GET151inFIG. 1and as “get_ptr” at step313) may be used to point at the relevant 32-byte block for allowing DMA130to fetch and to forward them to the part in IN_CACHE200which is currently used (that is, after performing the swap at step310) as the DMA part.

After DMA130forwards (at step313) the 32 bytes block associated with new pointers to the DMA part in IN_CACHE200, get_ptr (which points to the current bulk, or block, of pointers in Allocation Ring122) may be cyclically incremented, at step314, for getting ready to fetch (for IN_CACHE200) additional (the next) 32 bytes that are associated with the next available pointers bulk. By “cyclically incremented” is meant monotonically incrementing the value of get_ptr153until it points at the last entry (shown at155) of AR122, after which (when the next increment is to occur) get_ptr153will be set to point (shown at154) at the first entry (shown at126) of AR122.

It is assumed that, while CPM102allocates (draws) buffer(s) pointer(s) from AR122(using DMA130), control processor (HOST101) replenishes AR122so that AR122will not run out of buffer pointers. Valid buffer pointers may reside in a single contiguous area in AR122, which area may be cyclic; that is, this area might begin at one location in AR122, then it may reach the physical end of AR122and, thereafter, continue from the physical beginning of the AR122.

DMA130may be requested several times by CPM102to fetch pointers bulks, which may result in a shortage of available pointers bulks in AR122. In order to ensure that there will be substantially always available pointers bulks in AR122for CPM102, a DMA count may be used to alert HOST101that a certain predetermined number of pointers bulks are already used by CPM102. That is, according to some embodiments of the present disclosure CPM102may increment (at step315) the value of DMA count every time CPM102requests DMA130to fetch a pointers bulk. When the value of the DMA count reaches a predetermined value (for example when the DMA count equals 5), CPM102may generate and forward an interrupt (an allocation) signal to HOST101and, thereafter (or concurrently), set DMA count to zero value. Responsive to, or based on, the allocation signal forwarded to it from CPM102, HOST101may decide whether it (HOST101) should move pointers bulks from the free buffer pool121to AR122, to allow AR122to cope with future demand(s) (by CPM102) for buffer(s) pointer(s).

It is assumed that after step313is perfonned the DMA operation will be completed before the eight buffers pointers in the CPM part of IN_CACHE200are used by CPM102, and the two cache parts are swapped again. At step316, the cache_index (generally shown at210) is cyclically decremented, and the pointer residing in, or associated with, the decremented value (the resulting pointer, or the result at step316) is returned, at step317, as the next pointer that will be utilized by CPM102to point at a corresponding memory space within system memory120that will serve as data buffers.

FIG. 4is a flow chart showing an exemplary method of how pointers may be de-allocated (released) from a CPM such as CPM102ofFIG. 1.FIG. 4will be described in association withFIGS. 1 and 2. If CPM102does not require any more a memory space in system memory120, CPM102may call (shown at401) a procedure called release_buffer for deallocating the pointer(s) associated with the unrequired memory space (buffers). In order to deallocate a pointer that is not currently required by CPM102, it is first checked whether the unrequired pointer can be put in the CPM part (for example CPM part201) IN_CACHE200, and, as is explained earlier, an unrequited pointer can be put in CPM part201(in this example) if CPM part201is not full (shown as No at step402. Regarding the expression ((cache_index+1)&7=0) used at step402, ‘&’ designates bitwise (logic) AND. Further, cache_index can have values 0, 1, 2, . . . , 15. For values 0 and 8, after incrementing the cache_index the logic boundary between the two cache parts (the CPM part and the DMA part) is about to be crossed. Therefore, the expression ‘((cache_index+1)&7=0)’ checks whether the expected value of the cache_index (after it is incremented) is going to be either 0 or 8 (in which cases the 3 least significant bits will be 0). If the expected value of the cache_index (after it is incremented) is expected to be 0 or 8, it means that the logic boundary is about to be crossed. The expression checks for values of 8 and 16. A value of 16 will become zero during the actual increment.

At step403a buffer pointer buf_ptr, which is the pointer pointing at the buffer to be (released) deallocated by CPM102, is put in an entry in the current CPM part (in this example in CPM part201) which is addressed by the current value of cache_index. Still at step403, after, or concurrently with, putting the deallocated pointer in CPM part201, the value of cache_index is incremented in preparation for storing in CPM part201the next unrequired pointer (if there will be such a pointer).

Referring again toFIG. 2, if the last (current) value of cache_index is, for example, 10 (shown at222), then, in accordance with step403, the deallocated pointer is stored in entry223and cache_index is incremented to equal 11 (shown at221). After putting the pointer in CPM part201and incrementing cache_index, control may return (shown at404) to the calling application.

If, however, the current CPM part (CPM part201, for example) is full (shown as Yes at402), it means that the deallocated pointer cannot be stored in IN_CACHE200because there is no available space in CPM part201for the deallocated pointer. In addition, the DMA part of IN_CACHE200(DMA part202in this example) is dedicated to pointers that are fetched from AR122by DMA130and, therefore, DMA part202is not intended to store deallocated pointers. Therefore, at step405, the deallocated pointer is put in the OUT_CACHE250and the OUT_CACHE_(generally shown at255) is cyclically incremented. OUT_CACHE_index points at the next free place in OUT_CACHE250(shown inFIG. 2) and it is a cyclic pointer, which means that when OUT_CACHE_reaches the last value9, the (next) value after incrementing OUT_CACHE_will be0instead of10. Each time OUT_CACHE_becomes even, the DMA engine is activated to move the last two pointers, which were put thus far in OUT_CACHE250, into DAR123. If, after being incremented, the value of OUT_CACHE index equals to10(for example), then OUT_CACHE_is initialized, such as by setting its value to zero. It is noted that although deallocated (released) pointers are intended to return to DAR123in system memory120, there is no need to check whether DAR123has room for the released pointers, because DAR123is substantially as large as the free buffers pool (FBP121) and, therefore, DAR123cannot be full.

At step406CPM102instructs DMA130to move pointers already stored in OUT CACHE250to DAR123. CPM102may forward to DMA130a move instruction (to perform a write operation) every time OUT_CACHE250contains a predetermined number of released (de-allocated) pointers. For example, CPM102may forward to DMA130a move instruction every time OUT_CACHE250contains two released pointers. Released pointers, which temporarily reside in OUT_CACHE250, may be moved (by DMA130) to available place(s) in DAR123, which are pointed at by a PUT pointer (put_ptr or PUT, as shown at152inFIG. 1). Put_ptr156is shown at156pointing at an exemplary empty space (entry) in DAR123.

The value of put_ptr156may be cyclically incremented, at step407, for getting ready to move additional released pointers (from OUT_CACHE250to DAR123). By “cyclically incremented” is meant monotonically incrementing the value of put_ptr156until it points at the last entry (shown at157) of DAR123, after which (when the next increment is to occur) put_ptr156will be set to point (shown at158) at the first entry (shown at128) of DAR123. Put_ptr156is allowed to cyclically return to the first entry128because DAR123can contain all buffer pointers in the system, so that it cannot get full, and the next location in DAR123is always free of buffer(s) pointer(s).

DMA130may be requested several times by CPM102to move buffer pointers from OUT_CACHE250to DAR123. If the content of DAR123is not properly handled, there might be a situation where too many buffers pointers accumulate in DAR123, which may cause HOST101CPU to starve for buffers pointers. In order to eschew the latter problem a DMA count may be used to alert HOST101that a certain predetermined number of released pointers were moved (by DMA130) back to DAR123. That is, according to some embodiments of the present disclosure CPM102may increment (at step408) the value of the DMA count every time a bulk of released pointers is/was moved by DMA130to DAR123. When the value of the DMA count reaches a predetermined value (for example when the DMA count equals 5), CPM102may generate and forward an interrupt (a de-allocation) signal to HOST101and, thereafter (or concurrently), set the DMA count value to zero. Responsive to, or based on, the de-allocation signal forwarded to it from CPM102, HOST101may decide whether it should move buffer(s) pointer(s) bulk(s) from DAR123to the free buffer pool (FBP)121. At step409control is returned to the calling application.