Patent ID: 7949846

Claim:
A method of allocating storage space on a storage device to a requesting entity, the storage device including a set of extents, the method comprising: maintaining an allocation map in computer memory, the allocation map having a plurality of map blocks, the map blocks each having a plurality of map entries, the map entries including respective logical extent identifiers, physical extent information, and an obsolete flag, where a null logical extent identifier represents a free extent and a non-null extent identifier represents a prior allocated extent, and where the obsolete flag marks a map entry as either current or obsolete; receiving an extent allocation request from the requesting entity; selecting a first map block having a first map entry marked as obsolete; selecting a second map block having a second map entry representing a free extent and not marked as obsolete; copying the physical extent information from the second map entry to the first map entry; assigning a new logical extent identifier to the first map entry; marking the first map entry as current; and marking the second map entry as obsolete.