Browse Prior Art Database

Timed Stamped Handles as Limited Validity Tags

IP.com Disclosure Number: IPCOM000117353D
Original Publication Date: 1996-Feb-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 123K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+7]

Abstract

Short, fixed length, tags are frequently used to efficiently mark data for storage and/or transmission. When related to named items, like files, tags can be regarded as "convenience names" temporary by nature. One widespread technique for tag allocation is based on tables with one fixed-length entry per item, in which essential data for the item are recorded while the item is in use, and the entry position (or number) is used as tag. This tag is also called handle (it gives a handle to a table entry!).

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

Timed Stamped Handles as Limited Validity Tags

      Short, fixed length, tags are frequently used to efficiently
mark data for storage and/or transmission.  When related to named
items, like files, tags can be regarded as "convenience names"
temporary by nature.  One widespread technique for tag allocation is
based on tables with one fixed-length entry per item, in which
essential data for the item are recorded while the item is in use,
and the entry position (or number) is used as tag.  This tag is also
called handle (it gives a handle to a table entry!).

      Since this type of tables are of limited size by their nature,
mechanisms to allow entry reuse have to be devised.

      Handle use by more than one thread, and possibly by more than
one process means that whenever a tagged object is destroyed the
handle (name) cannot be reused since there might still exist handles
in use intending to name the "old" object.

      A cleaning process is required to allow reuse, and this process
is either too complicated or makes the machine unavailable for long
periods or both.

      This scheme assumes the existence of a method by which a
process can validate the entries it accesses.  Usually this
validation procedure is too expensive to be used for every access to
the information.  The main provision of our method is its ability to
issues a warning when the situation is not certain and only at that
case the process needs to go through the more expensive validation
procedure.  Following such a procedure the situation becomes certain
for another period.

The solution allows handle reuse without cleanup.

      It is based on recording on each handle table entry a creation
time stamp and "time limited validity" for handles (permit).

      The machine will maintain a "rough" clock - e.g., a 1-hour
increment clock such that a small permit will allow a reasonable
operating interval (over 7 years for 2 bytes and 1-hour clock).
Let's call this clock CK.

      A limited size handle table is used to support the mechanisms
and every entry in the table can be in one of the following states:
  o  free
  o  in-use
  o  expiring

      Every type of entry can be kept in a linked list for fast group
access.

      Whenever an object needed tagging is created an entry is
allocated.  The entry is time-stamped with the value of CK as
creation time-stamp.  Call this stamp OK.  The OK stamp is an
integral part of the object.

      Every thread using a handle will keep with the handle a
validation time stamp (permit).  Call it PK and consider it as and
integral part of the "user handle" (the threads own copy).

      All legitimate handle operations will copy PK.  Handle
creation, copy, and revalidation are examples of legitimate
operations.

      A handle can be validated or not-validated.  A not-validated
handle might be legitimate or illegitimate.  A not-validated
legitimate handle is transf...