Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1996-06-20
2001-06-12
Oberley, Alvin E. (Department: 2755)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S209000
Reexamination Certificate
active
06247105
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method and apparatus for information processing, particularly to a memory allocation system.
2. Background Art
In the prior art, information relating to memory allocation is not stored in a manner that allows it to be examined by processes external to the allocator. The ability to examine this information is desirable since an understanding of the overall configuration of allocated memory space and free memory space is useful for evaluating and optimizing performance of a computer system especially when concerned with applications that exist for long periods of time (e.g. greater than five minutes). Desktop applications often exist for periods of time measured in months. To examine how memory is being allocated for particular code in the prior art, it is necessary to modify that code before it is executed. Thus, the code being executed is not identical to the code for which the information relating to memory allocation is sought.
3. Prior Art Techniques
Computers are used to process information. Computers execute programs that specify steps to be used to process the information. A computer operating system controls execution of the programs. Some computer operating systems allow multiple programs to be executed concurrently. In such operating systems, multiple processes are established that allow execution of the multiple programs. The operating system allocates the processing time of a processor to the processes. Program information and data processed by the programs are stored in memory devices of the computer. When the execution of a program begins, memory space in the memory devices is allocated to the corresponding process. If an inadequate amount of memory space is allocated to a process, the process may encounter a fatal out-of-space condition when running. When the execution of a program ends, the memory space allocated to the process is freed to allow the memory space to be reused.
Techniques are needed to allocate memory space to a process and to free or deallocate the memory space after the process no longer needs it. In the past, in the C programming language, standardized C library routines were provided to allow memory space to be allocated and freed. The standard C library routine to allocate memory space is referred to as the “malloc” function. The standard C library routine to free memory space if referred to as the “free” function.
The “malloc” function is executed with a parameter specifying the size of the memory block to be allocated. The “malloc” function finds a block of memory space of adequate size and returns a pointer to the beginning of the memory block.
The “free” function is executed with a parameter specifying a pointer pointing to a memory block previously allocated by the “malloc” function. The “free” function frees the specified memory block to be used again by the same process.
The “malloc” function maintains multiple lists of free blocks according to size and allocates space from the appropriate list. If “malloc” is unable to locate an unallocated memory block of sufficient size, it invokes an “sbrk” function to have the operating system provide more memory space from which allocations may be made.
If it is desired to change the size of a memory block that has already been allocated, the “realloc” function may be invoked. The “realloc” function is executed with a parameter specifying the pointer that points to a memory block that has already been allocated and another parameter specifying the new size desired for that memory block. The “realloc” function allocates a memory block of sufficient size and returns a pointer to the new memory block. The pointer may point to a memory block having the same beginning location as the memory block that existed at the time the “realloc” function was called, or the pointer may point to a memory block having a different beginning location if inadequate memory space existed in the memory block previously allocated and free memory space contiguous with that memory block.
While the “malloc” and “free” functions are adequate for obtaining and freeing blocks of memory, they do not provide the ability to examine the current status of free and allocated memory space. This ability is desirable since an understanding of the overall configuration of allocated memory space and free memory space would be useful for evaluating and optimizing performance of a computer system, especially in long-lived processes. In particular, it would be useful to be able to specify a process and be provided with information indicating the blocks of memory space allocated to the process and their locations in the overall memory space of the computer system.
In the past, a program could be rewritten to include calls to a “mallinfo” function. The “mallinfo” function provides information describing memory space allocation. Typical information provided by the “mallinfo” function includes the total space in the arena, the number of ordinary blocks, the number of small blocks, the number of holding blocks, the space in holding block headers, the space in small blocks in use, the space in free small blocks, the space in ordinary blocks in use, the space in free ordinary blocks, cost of enabling the keep option, the maximum size of small blocks, the number of small blocks in a holding block, the small block rounding factor, the space (including overhead) allocated in ordinary blocks, the number of ordinary blocks allocated, and the number of bytes used in maintaining the free tree. While this information is useful for analyzing performance, the calls to the “mallinfo” function must be added to the program being analyzed. Thus, use of the “mallinfo” function is an invasive procedure that does not permit analysis of a program in the form in which the program is intended to be used.
The inclusion of the “mallinfo” function adds complexity to the code which increases development and maintenance costs. Further, the memory space allocation information associated with a process that includes the “mallinfo” functionality may be skewed by the inclusion of the “mallinfo” function. That is, the “mallinfo” functionality may alter the memory allocation information. This alteration may result in difficulty in making a memory allocation assessment by an application developer.
To include the “mallinfo” functionality in a process executing code that does not include this functionality, it is necessary to terminate the process and initiate a new process executing code that contains calls to the “mallinfo” function. Thus, it is cumbersome to add this functionality to code that is already executing.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus for noninvasively providing information relating to memory space allocation. The invention allows memory space allocation to be examined by processes external to the memory space allocator without the need to modify the code for processes to which memory space is being allocated.
An embodiment of the invention provides a method and apparatus for maintaining memory allocation information comprising the steps of reserving a memory space arena, defining a data structure to store the memory allocation information, and storing the memory allocation information.
The memory allocation information comprises a first value representative of a quantity of pages of a first bucket size instantiated in the memory space arena. The memory allocation information also comprises a second value representative of a quantity of buckets allocated in one of the quantity of pages of the first bucket size instantiated in the memory space arena. The memory allocation information further comprises a pointer to a linked list identifying unallocated buckets in one of the quantity of pages of the first bucket size instantiated in the memory space arena.
One embodiment of the invention also provides a method and apparatus to modify the memory allocation information when a change in memory allocation occurs. The invention allows the memory allocation
Goldstein Richard
Zittin David
Courtenay III St. John
Oberley Alvin E.
Sun Microsystems Inc.
The Hecker Law Group
LandOfFree
Externally identifiable descriptor for standard memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Externally identifiable descriptor for standard memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Externally identifiable descriptor for standard memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460555