Browse Prior Art Database

Bit-Map Storage Validation Machine

IP.com Disclosure Number: IPCOM000112803D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 157K

Publishing Venue

IBM

Related People

Howe, TL: AUTHOR [+2]

Abstract

A method for mapping storage allocation requests via a hierarchical tree whose leaves are bit maps is disclosed. This method detects and avoids unintentional use of one program's storage by another. The method allows validation of starting address and length for storage release requests. The maps can also be used to produce reports of allocated storage in ascending or descending address order. The method provides tree optimization to reduce overhead. A bit-map storage validation machine will be described with four functions:

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

Bit-Map Storage Validation Machine

      A method for mapping storage allocation requests via a
hierarchical tree whose leaves are bit maps is disclosed.  This
method detects and avoids unintentional use of one program's storage
by another.  The method allows validation of starting address and
length for storage release requests.  The maps can also be used to
produce reports of allocated storage in ascending or descending
address order.  The method provides tree optimization to reduce
overhead.  A bit-map storage validation machine will be described
with four functions:

1.  OBTAIN - Validate and record in a bit map a user's request to get
    a range of storage.

2.  RELEASE - Validate and record in a bit map a user's request to
    free a range of storage.

3.  VERIFY - Validate from a bit map a user's storage allocation
    range.

4.  READOUT - Find the next allocated storage area.  The map can be
    used in ascending or descending order, for either allocated or
    available storage areas.

      These functions provide the ability to detect and prevent
storage data overlays due to accidentally attempting to free storage
using invalid address or length specification.

The component parts are pictured in the Figure.

o   The OBTAIN function

          Operation of OBTAIN Function starts when the main storage
    manager (3) sets the address register (4) to a numeric value of
    the main storage (2) to be mapped 'allocated'.  The main storage
    manager (3) also sets the length register (5) to a numeric value.
    The main storage manager (3) then sets the request register (6)
    to a unique non-zero numeric value meaning "obtain".

          The logic unit (10) creates or changes tables in its local
    storage (11) to indicate the main storage area that is allocated.
    The tables (12)-(17) are referenced to ensure that the main
    storage is not already allocated.  The tables (12)-(17) are built
    in a hierarchy in the storage validation machine's (1) local
    storage (11).

          Each table (12)-(16) except for the last (17) is an array
    of local addresses to lower level tables.  The arrays are built
    with the number of elements being a power of 2.  Thus the index

    to each level can be extracted from the corresponding sequence of
    bits in the address register (4).  A zero value indicates a lower
    level table is not in use.

          At each level of the tables (12)-(16), a local address can
    be replaced by one of two binary values to indicate that the
    entire area of main storage (2) mapped by the table entry is
    allocated.  A string with all bits set "on" is used to mean the
    entire sub-table range is allocated, and is not the last
    contiguous main storage in this allocation.  A string with all
    bits except the last one set "on" (and the last bit set to "off")...