METHOD AND APPARATUS FOR ALLOCATING AND FREEING STORAGE UTILIZING MULTIPLE TIERS OF STORAGE ORGANIZATION

A method and system for allocating and freeing storage are provided. The method can be built on top of any existing storage management algorithm. The method is described as being built upon the heap storage algorithm most often associated with the C programming environment. The method operates by breaking all storage requests into a fixed number of pools. Each pool is then managed by three tiers of management. The first tier is a so-called quick pool consisting of storage blocks which have already been used and freed and are managed on a LIFO queue. The second tier is made up of cell pool extents that are carved from the heap and then further subdivided into blocks of the appropriate size for each pool. The third tier is made up of the existing heap management algorithms or any other storage management algorithm. The method relies on atomic hardware instructions for removing blocks from the quick pools and cell extents. The lack of blocking serialization allows this method to provide a high performing storage manager, even in multithreaded applications with a high degree of concurrency in malloc( ) and free( ) requests from the threads. Any storage request of a size beyond the largest pool size is satisfied by use of the old malloc( ) interface.