Browse Prior Art Database

Low Overhead Tombstone Storage

IP.com Disclosure Number: IPCOM000110011D
Original Publication Date: 1992-Oct-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 3 page(s) / 91K

Publishing Venue

IBM

Related People

Godtland, PL: AUTHOR [+3]

Abstract

Disclosed is an approach for limiting tombstone storage consumption over time, using only existing memory management functions.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Low Overhead Tombstone Storage

       Disclosed is an approach for limiting tombstone storage
consumption over time, using only existing memory management
functions.

      Tombstones are non-reusable storage locations used to provide
unique identification of reusable or delete-able entities.  They add
a level of indirection to references to these entities, increasing
storage needs.  The storage for the tombstones cannot be reused
during the time pointers addressing them are valid.  This time
duration can be very long:  for temporary addresses, it is the time
between IPLs (initial program loads); for permanent addresses, it is
the time between auxiliary storage initializations.  Thus, it is
imperative to prevent tombstone storage from continually increasing
in size over time.

      The basic notion in our approach is to manage small subsets of
the overall tombstone storage as individual groups.  These groups can
be removed from both main and secondary storage when the tombstones
they contain have all been invalidated.  With appropriately sized
groups, little management overhead is added and storage needs are
reduced over time.

      The basic address range unit, known as a segment, is allocated
to secondary storage in one or more extents.  There is currently no
capability to de-allocate "interior" portions of a segment, so the
amount of secondary storage consumed depends upon the "highest"
address referenced within the segment.  Thus, if a byte is stored at
offset 0 within the segment, and another byte is stored at offset
16,000,000, the segment requires 16,000,000 bytes of secondary
storage.  A tombstone segment would continue to grow, even when
individual tombstones have been invalidated (on our system, using a
known reserved address value).

      For systems with the capability to de-allocate any particular
portio...