A data storage system provides generalized record caching through a control unit adapted to support track caching in the upper level store of a two level memory. Dynamic reallocation of space between each type of caching in the upper store follows operating patterns of host computer systems using the data storage system. A storage controller cache has a plurality of segments. A directory data entry data structure is allocated each segment. Such allocated directory entries are used to identify tracks as cached. A plurality of unallocated directory entries are also provided. As a record is cached in a segment outside of a track slot, an unallocated directory entry is used to identify a virtual track in cache corresponding to the track of the record in the lower level store. Records from one track can thus appear in several segments outside track slots. Tracking of records to locate records least recently used is done globally over all track slots and record caching segments and locally within individual record caching segments. A mechanism is provided for identifying record slots, as they become least recently used, and dropping them from the upper level store in the face of competing demands for the space. A second mechanism identifies least recently used segments for dropping from the upper level store.