User control of multiple memory heaps6816956Abstract Control and administration of the supply of memory managed in multiple heaps by a library heap management facility. Control data used by the heap management facility is located in user-supplied memory. Heaps are created dynamically through calls from the application to a runtime library. Allocation within a heap is performed through calls to the runtime library that canvass the available heap memory for each allocation request. If no suitable block of heap memory is located, additional user supplied memory is requested for the application through a callback function. A second callback function notifies the user when a supplied unit of memory is no longer required by the heap and may be disposed of. The callback functions are specified separately for each heap. The user may also set the default heap in the runtime library by allocation requests from a vendor library that do not specify a heap. This can be done a per thread basis in multithreaded applications so that different executing threads can use different default heaps in a non-interfering manner. Claims The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows: Description FIELD OF THE INVENTION
Heap_t _ucreate(void *pool, size_t init_sz, int blockclean,
int mem_flags
void *(*exhausted) (size_t *sz, int *clean),
void (*release) (void *block,size_t sz))
As illustrated in FIG. 3 and in the C code fragment above, in a preferred embodiment, the invention provides _ucreate which creates a user heap. The function operates similarly whether or not another heap already exists. In the first step (block 1) the application initiates the _ucreate call and defines an initial chunk of memory needed, size, flags, exhausted function and release function. The _ucreate function returns the handle heap_t identifying the heap. The parameters passed by the user include pool, which is the memory address of the initial block available for use, of the size init_sz bytes, which must be at least _HEAP_MIN_SIZE (block 2). If the initial size init_sz of the block is smaller than HEAP_MIN_SIZE, the system returns a NULL (block 3). If the initial size is at least equal to _HEAP_MIN_SIZE bytes, the runtime will mark the first _HEAP_MIN_SIZE bytes as a reserved area for the heap which will be used to store information relative to the heap as described below with respect to the heap structure (block 4). NULL will also be returned if any other errors occur on the call. Sanity markers are placed at the start and end of the reserved area (block 5). A pointer to the release function is assigned with the value passed (block 6), and a pointer to the exhausted function is assigned with the value passed (block 7). A pointer to the list of all the chunks of memory inserted into the heap is cleared (block 8), all these pointers in blocks 6, 7 and 8 being in the reserved area. A flag in the reserved area is set if the heap will be using shared memory, and is cleared if the heap will not be using shared memory (blocks 9, 10, and 11). A structure containing all the necessary information for the heap management routines is initialized (block 12). This structure may contain the start of the free object list, a pointer to the used list, the minimum and maximum addresses inserted into the heap, and statistics indicating the amount of used memory. This is equivalent to placing all the global variables specific to the single heap implementation in a structure within this reserved area. In the case of a multithreaded environment, a semaphore specific to this particular heap is created (block 13 and 14) via a system call, and the structure for it is also stored with the reserved area. The remaining pool that was passed in, less the area marked as reserved, is inserted into the heap used to manage the memory (block 15 and 16). The operation of insertion onto the heap is specific to the base memory management algorithm used. A pointer to the start of the reserved area is returned to the user as a heap handle to the newly created heap (block 17). The user will reference this value as a heap handle in future heap specific calls. In void* (*exhausted) (size_t*sz, int*clean), exhausted is a pointer to a callback function that will be issued by the runtime library if it has insufficient memory available in the heap to satisfy an allocation request from the application. The sz points to an unsigned integer variable initialized to the minimal amount of memory that this routine must provide back to the heap routines. The returned value is a pointer to a chunk of memory supplied by the application to extend the heap, or is a null if the application declines to extend the heap. The user has the option to return a larger block than requested by modifying the size variable, *sz. The clean parameter will point to an integer variable that must be set by the exhausted function to the value _BLOCK_CLEAN to indicate that the block is all zeros or to !_BLOCK_CLEAN to indicate otherwise. void (*release) (void*block, size_t sz), the block will point to a memory block that was provided by the user by the exhausted routine or _uaddmem. This callback routine will be called from _udestroy for a user created (or assigned) memory pool that requires blocks to be returned back to the operating system mem_flags: can be defined as _HEAP_TILED, _HEAP_SHARED, or _HEAP_REGULAR exhausted: is the user callback function called when memory is required by the heap. release: is the user callback function called when memory is released by the heap. int_uopen(Heap_t heap) where heap is a valid heap handle identifying a heap that will be opened for usage. This function allows the current process to use the heap, and must be called in all processes where the heap will be access implicitly and explicitly. If successful, 0 [zero] is returned. In operation, the _uopen function called by the user application (FIG. 4, block 20) accepts a heap handle that points to the heap internal structure. The heap internal structure sanity marks are checked within the reserved area and an error reported if they are not the predetermined values (blocks 22, 24). Knowing that a valid internal heap structure exists, the system specific structure for the semaphore is passed on to the operating system to grant access to this semaphore to the current process that initiated the call (block 26). The return code received by the operating system is then returned to the user indicating the opening of the semaphore was performed successfully (block 28). Int_uclose(Heap_t heap) where: heap is a valid heap handle identifying a heap that will be closed for usage. This function notifies the runtime that the executing application will no longer require the usage of this heap. If successful, 0 is returned. The operation of this routine although opposite in purpose to the operation of the _uopen function, follows the same steps as those illustrated in FIG. 4. When called by the application (block 20), _uclose will accept a heap handle that points to the heap internal structure. The heap internal structure sanity marks will be checked within the reserved area and an error reported if it is not a predetermined value (block 22, 24). Knowing that a valid internal heap structure exists, the system specific structure for the semaphore will be passed on to the operating system to remove access of this semaphore by the current process that initiated the call (block 26). The return code received from the operating system is then returned to the user indicating if the opening of the semaphore was performed successfully (block 28). void*_umalloc(Heap_t heap, size_t size) void*_ucalloc(Heap_t heap, size_t size, size_t qty) These functions will behave exactly like the non-heap version except that allocations will be made from the supplied heap. NULL will be returned if the request cannot be satisfied by the exhausted function. _umalloc allocates memory from the supplied heap area of the size specified, as illustrated in FIG. 5. The routine is called by the application, and accepts a heap handle that points to the heap internal structure (block 30). The heap internal structure sanity marks will be checked within the reserved area and an error reported if they are not predetermined values (blocks 34, 36). The heap is serialized by methods known to those skilled in the art, for example by locking a system semaphore stored in the heap reserved area (block 38). Using this heap handle, a call to the memory allocation algorithm is made for a request of the provided size (block 38). If there is not enough memory available in the specified heap to satisfy the request (block 40), then the user's exhausted callback function (specified in _ucreate) is called with the size required (block 42). If the callback returns a NULL indicating that it could not satisfy the request, then NULL is returned back to the original caller (block 44, 46). Otherwise, the new object inserted is added to the linked list maintained within the heap reserved area for inserted user objects. The new block returned by the callback routine is inserted into the heap (block 48). The object of the required size is removed from the heap (block 50) and the size and handle are stored in the first eight bytes of the object (block 52). The user part of the object is returned to the application (block 54). In order to recognize the heap where an object was allocated from during deallocation, an internal area within the object returned must be set to mark the size and heap handle used as illustrated in FIG. 7. The portions of the heap allocated to size 70 and heap handle 72 making up the internal information of the allocated object, are returned by regular _umalloc function to the user. The remaining sz bytes constitutes the user area 74 in the object. The address returned to the user is the address of the user area 74 within the object. The heap is deserialized by methods known to those skilled in the art, for example by unlocking a system semaphore stored in the heap reserved area. The _ucalloc function is similar to that of _umalloc except the memory area is cleared with the null byte on return. void free(void*ptr) void*realloc(void*ptr, size_t size) The routines will determine the heap used during the initial allocation, and then perform the given operation based on that heap. If NULL is passed to realloc, then the default heap will be used for the allocation. The return values and expected arguments will be the same as in free and realloc calls known to those skilled in the art. Heap_t_uaddmem (Heap_t heap, void*block, size-t sz, int clean) This user function can be used to extend a heap by adding a chunk of memory to it. The parameter block here points to the chunk of memory that the application is providing to extend the heap. Int_udestroy(Heap_t heap, int force) where: heap is a handle identifying a valid heap that will be destroyed. _FORCE forces destruction if allocated objects still exist This function collapses the entire heap specified by calling the release function specified in _ucreate for every chunk of memory supplied by the user via _uaddmem, or via the exhausted callback function. Usage of the heap after _udestroy results in undefined behaviour. If successful, 0 is returned. The operation of this routine is illustrated in FIG. 6. The _udestroy function call issued by the application (block 61) accepts a heap handle that points to the heap internal structure. The heap internal structure sanity marks are checked within the reserved area (block 62) and an error reported if it is not a predetermined value (block 63). Access to the heap is serialized by locking a system semaphore stored in the heap reserved area (block 64). Next, the linked list of user-inserted extensions of the reserved heap area is scanned (block 65). Each of the extensions was inserted into the linked list following a call to the user's exhausted routine when an allocation request-could not be satisfied with the contents of the heap at that time. For each of these extensions within the linked list, the user's release routine is called so they can properly return the memory extensions from wherever they obtained it (block 66). The call to the callback function returns the memory pointer originally provided as well as the size. Access to the heap is deserialized by unlocking a system semaphore stored in the heap reserved area (block 67), and the semaphore specific to this heap is returned back to the operating system (block 68). The remaining original chunk of memory supplied by the user during the _ucreate, containing heap control data, is cleared to prevent further allocations from this heap (block 69). EXAMPLE The following example illustrates how the user heap routines are used to implement a separate allocation pool. In this example, a user heap is created with the minimum startup size. The example then allocates an object of 1000 bytes using the _umalloc function which causes the user get_fn to be called since the heap is empty at this point. The get_fn is called with a length of 1000 bytes plus some overhead which it modifies to 65536 since it is a much more practical increment to get from the operating system. The get_fn callback routine rounds up the requested length to a multiple of the system page size and attempts to obtain a block of memory of this size directly from the operating system. #define sys_page_size (4096*16) static void*get_fn(size_t*length, int*clean) { void*p; /*mark the block we are returning as clean*/ *clean=_BLOCK_CLEAN *length=(*length/sys_page_size)*sys_page_size+sys_page_size; /*Make a system call to acquire memory*/ p=GetMemFromSystem (*length); return(p); ( To collapse the heap, a call to _udestroy is made which would call the user's free_fn release function for every chunk that was provided, and then clear the original starting chunk provided during heap creation. The following free_fn callback routine will be called when the memory routines deem that a block of memory that was provided earlier is no longer needed and can be returned back to the operating system. static void free_fn(void*p, size_t sz) { ReturnMemToSystem(p,sz); return; } int main(void) ( Heap_t my_heap; char starting_chunk [_HEAP_MIN_SIZE]; void*p; /*create a user heap with the starting chunk being the minimum size*/ my_heap=_ucreate(starting_chunk, _HEAP_MIN_SIZE, !_BLOCK_CLEAN, _HEAP_REGULAR, get_fn, free_fn); if (my_heap==NULL) puts(_ucreate failed); p=_umalloc(my_heap,1000) if (p==NULL) puts(_umalloc failed); free(p); /*Now destroy the heap since it is no longer needed*/ _udestroy(my_heap); return(0); In the above examples, GetMemFromSystem and ReturnMemToSystem indicate standard system calls to obtain and release memory. For compiler and runtime library writers that wish to implement a multiple heap memory manager on top of a single heap implementation, the goal is to convert a single heap implementation into a multiple heap version that can process all memory types seamlessly. Therefore, the base memory allocator must be modified as follows: Create a heap structure to store all the global variables related to the memory routines. This information will be stored in the heap reserved area. Declare a heap structure inernally to contain the following: Sanity value Base memory allocator information pointers to free list, allocation lists, temporary variables and semaphore structures A function pointer to the exhausted routine A function pointer to the release routine A flag denoting the type of memory it is handling. This is only necessary if the base memory allocator needs to process different types of memory differently. For example, tiled memory is required in a segmented architecture to ensure a block of memory does not cross a segment boundary. A pointer to maintain a linked list of blocks of memory that the user's callback routine returned during an allocation request. Modify the routine that acquired memory from the operating system to use the exhausted callback routine specific for the heap call. Modify the routine that returned memory to the operating system on heap destruction or termination to use the release callback routine specific for the heap call. If the environment supports threads, then support should be added to synchronize code at the heap level rather than the function level. This will allow calls in separate threads to the same heap to execute concurrently. Modify the base memory allocator to encode the heap handle used for the allocation within the returned object. Modify the free and realloc routines to determine the heap used for the object to be released and perform the necessary operation on that specific heap only. Define the following macros: _BLOCK_CLEAN--Specify if inserted memory into the heap is all zeroes. _HEAP_MIN_SIZE--Minimum memory size required to create a heap. This value must be at least equal to the size of the heap structure previously declared in the runtime library. A further aspect of the present invention is illustrated in the flow diagram of FIG. 8. Multiple dynamic memory heaps give users flexibility in managing their storage use, and allow them to selectively allocate data in different types of memory. For example, an application may use one private heap of regular memory, and a second heap built with shared memory that is accessible to other applications and processes. However, a severe problem with allocations occurs in vendor supplied object code only (OCO) libraries that were not constructed with multiple heaps in mind, since the user is not in a position to make the source level modifications necessary to use multiple heaps. Accordingly, this aspect of the invention is directed to providing a mechanism whereby users can specify a heap to temporarily replace the standard default heap defined in the runtime library. This specified default heap will be used for all allocation requests that do not explicitly specify a heap, and allows for transparent migration from single to multiple heap strategies, particularly for using shared memory heaps in unmodified OCO libraries. As illustrated in FIG. 8, the application 80 first calls down to the runtime library 82 to set the default 84 to the required heap (88a, 88b or 88c). The application 80 then calls the vendor library 86, which in turn issues a malloc call that will use the default 84 set previously set by the application. New routines are written with the old names of the allocation routines that determine which heap is considered the default and call the multiple heap version with it as an argument. Functions Heap_t_udefault(Heap_t newHeap) This routine must be called within each thread that the default allocation routines are to be implicitly acquired from a private heap. Internally, all that is done is change an internal variable within the runtime library that denotes the current default heap to the value passed in by the user. The return value is the previous default heap prior to replacement. void*malloc(size_t sz) This allocation routine will acquire storage size sz from the current active default heap. The active default heap is set previously within the application by the user making a _udefault call. If such call was not made then the default runtime heap that the library determines will be used. void*calloc(size_t size, size_t qty) This function is similar to that of malloc except the memory area is cleared with the null byte on return. void*realloc (void*p, size_t newsize) This function reallocates the object pointed to by the p parameter, such that it will have size newsize. The object is reallocated in the same heap, except if pointer p is null, it will be reallocated in the current default heap. In a multithreaded environment, the default heap handle set by the_udefault call can be set on a per thread basis, and would be stored by the runtime library separately for each thread. The invention can be used with user libraries that are build to use only one heap, by defining the secondary library function with redefines the default shared memory heap prior to the calling of the secondary library function. Following the completion of the secondary library function, the default heap is redefined to the previous heap, and thus the secondary library function does not interfere with the operations performed with any other thread. An example of such function is below: Heap_t oldHeap; oldHeap=_udefault(sharedMemoryHeap); LibraryFunction; /*call OCO routine*/ void_udefault(oldHeap); /*restore previous heap*/ The library function and all functions it calls will use shared memory heap to satisfy all non-heap-specific allocation requests in a way that it does not interfere with later operations performed in the current thread. The foregoing invention has been described in association with specific embodiments. However, modifications to those skilled in the art are intended to be covered by the appended claims.
|
Same subclass Same class Consider this |
||||||||||