Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

To:       Distribution

From:     Lindsey L. Spratt and Matthew C. Pierret

Date:     02/24/83

Subject:  Data Management: Collection Manager Design.

1 ABSTRACT

     This MTB presents some of the  major items of the design and
implementation  of  the collection_manager_  module.   The reader
should  be familiar  with MTB-551,  "Data Management:  Collection
Manager Functional Specification."

Comments should be sent to the author:

via Forum:
   >udd>m>lls>mtgs>DMS_Development.

via Multics Mail:
   Pierret.Multics on either MIT Multics or System M.

via telephone:
   (HVN) 261-9338 or (617) 492-9338

_________________________________________________________________

Multics  project  internal  working  documentation.   Not  to  be
reproduced or distributed outside the Multics project without the
consent of the author or the author's management.



                             CONTENTS

                                                         Page

                 1 Abstract . . . . . . . . . . . . . .     i
                 2 Introduction . . . . . . . . . . . .     1
                 3 Control interval structure . . . . .     1
                 4 Element storage management . . . . .     4
                    4.1 Storing elements as datums  . .     5
                    4.2 Allocating a new element  . . .     5
                    4.3 Modifying the value of an
                     existing element.  . . . . . . . .     6
                 5 Control interval storage management      7
                    5.1 Allocating a CI . . . . . . . .     8
                    5.2 Freeing a CI  . . . . . . . . .     8
                    5.3 Supporting control structures .     9
                 6 Datum structures . . . . . . . . . .    10
                 7 The header collection  . . . . . . .    11
                 8 collection_manager_ use of
                  collection_manager_ . . . . . . . . .    13

Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

2 INTRODUCTION

     The  collection_manager_  does low-level  storage management
within  a  Data  Management  file (hereafter  called  file).  The
primary clients  for its services  are the index  manager and the
record  manager.   Collection_manager_  implements  the following
model  of  storage:   Within  a  file  there  are  any  number of
"collections"  of "control  intervals".  The  unit of  storage of
data  for  the caller  of  collection_manager_ is  the "element".
Under  certain   circumstances,  an  element   may  span  control
intervals.   An  element  is  wholely contained  within  a single
collection, thus  for elements which span  control intervals, all
of the  control intervals which  an element spans  must belong to
the same  collection.  An element is  stored in control intervals
in units called  "datums".  If an element fits  entirely within a
single control interval, it is allocated in the control intervals
as  a  single  datum.   If  it  spans  control  intervals,  it is
allocated in a single datum per control interval.

     The storage  management provided by  collection_manager_ has
two levels  of organization, control  interval storage management
and element  storage management.  On the  coarser level, the file
as a whole is viewed as  being composed of units of storage which
are  control  intervals.   Collection_manager_  reserves  control
intervals in  the file for specific  collections, and manages the
allocation  and freeing  of reserved  control intervals  within a
collection.

     The finer level of storage  management is the allocation and
freeing of  elements.  Element storage management  deals with the
allocation and  freeing of space  inside of control  intervals in
which  to store  elements and  the organization  of elements into
datums.

3 CONTROL INTERVAL STRUCTURE

     Control   intervals   managed  by   collection_manager_  are
currently a Multics page formatted in a canonical "basic layout".
At some point in the  future, collection_manager_ will be able to
support a variety  of control interval sizes formatted  in one of
several layouts.  The entire contents of the control interval are
not accessible  to collection_manger_, as  file_manager_ reserves
some space at  the beginning and end.  The  portion in between is
referred to  as the addressable portion  of the control interval.
As  collection_manager_  is only  concerned with  the addressable
portion,  future references  to control  interval or  CI mean the
addressable portion only.

     Using the  basic control interval layout,  datums are stored


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

adjacently from the highest offset in the control interval toward
the lowest,  or bottom up.   The offset of the  beginning of each
datum is stored in an array  of slots which grows from the lowest
offset of the  control interval toward the highest,  or top down.
Between the end of the array and the beginning of the "uppermost"
datum  is  a pool  of free  space  in which  other datums  can be
allocated.   The  array of  slots is  at the  end of  the control
interval's header, which follows:

     dcl     1 basic_control_interval
                                    aligned based (
                                    basic_control_interval_ptr),
               2 header             unaligned,
                 3 layout_type      char (4) aligned,
                 3 collection_id    bit (36) aligned,
                 3 next_control_interval
                                    fixed bin (24) uns unal,
                 3 previous_control_interval
                                    fixed bin (24) uns unal,
                 3 flags            unaligned,
                   4 continuation_datum_is_present
                                    bit (1) unal,
                   4 free_slot_is_present
                                    bit (1) unal,
                   4 must_be_zero   bit (4) unal,
                 3 scattered_free_space
                                    fixed bin (17) unal,
                 3 start_of_used_space
                                    fixed bin (17) unal,
                 3 number_of_datums fixed bin (17) unal,
               2 datum_position_table
                                    (0 refer (
                                    basic_control_interval
                                    .number_of_datums)),
                 3 flags            unal,
                   4 special_format_datum
                                    bit (1) unal,
                   4 is_continued   bit (1) unal,
                   4 is_continuation
                                    bit (1) unal,
                   4 mbz            bit (1) unal,
                 3 offset_in_bytes  fixed bin (15) uns unal,
                 3 length_in_bits   fixed bin (17) uns unal;

where:

       version
            is   the    type   of   control    interval   layout,
            BASIC_CI_LAYOUT_1.


Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

       collection_id
            is  the identifier  of the  collection to  which this
            control interval belongs.

       next_control_interval
            is  the number  of the  next control  interval in the
            same collection.   A value of zero  means this is the
            last control interval.

       previous_control_interval
            is the number of the previous control interval in the
            same collection.   A value of zero  means this is the
            first control interval.

       flags.continuation_datum_is_present
            is  a flag  which, if on,  indicates that  there is a
            datum in the control interval  which is used to store
            part of an element which begins in another datum.

       flags.free_slot_is_present
            is a flag  which, if on, indicates that  at least one
            of the slots in the datum_position_table is free.  In
            this case, allocation of a  new element would use one
            of the free slots instead of extending the table.  If
            the flag is  off, the table need not  be searched for
            the free slot.

       flags.must_be_zero
            is a pad field containing all zeroes.

       scattered_free_space
            is the amount of free  space in the control interval,
            excluding    the   space    between   the    end   of
            datum_position_table     and     start_of_used_space.
            Scattered free space is  cause by freeing datums that
            do not start at start_of_used_space.  This free space
            can  only  be recovered  by "compacting"  the control
            interval;  basically,  doing  a logical  copy  of the
            allocated  datums into  a temporary  control interval
            then  copying  back  from   the  temporary  into  the
            original.

       start_of_used_space
            is the lowest offset used in the control interval for
            the  value  of  an  allocated datum.   All  values of
            datums are  allocated from the highest  offset in the
            control      interval,      down.       Since     the
            datum_position_table  grows from  the low  end of the
            control  interval  "up", the  pool of  available free


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

            space  in the  control interval  is between  the last
            datum_position_table   array   datum    up   to   the
            start_of_used_space.

       number_of_datums
            is  the   number  of  the  last   used  slot  in  the
            datum_position_table.

       datum_position_table.special_format_datum
            is not  currently used and  must be "0"b.   It can be
            used  in the  future if very  large control intervals
            are supported and the  offset_in_bytes fields must be
            extended.

       datum_position_table.is_continued
            is a flag indicating, if on, that this datum does not
            represent an entire element,  and that the element is
            continued  in  another   datum  (in  another  control
            interval).  Continued datums  have headers; this flag
            allows  collection_manager_  to get  directly  at the
            contents of the datum.

       datum_position_table.is_continuation
            is  a flag  which indicates,  if on,  that this datum
            does not  represent an entire element,  and that this
            datum  is  the  continuation  of  another  datum  (in
            another control interval).

       datum_position_table.offset_in_bytes
            is  the  offset of  the datum  in bytes.   Datums are
            stored on byte boundaries.

       datum_position_table.length_in_bits
            is the  length of the  datum in bits.   This includes
            any  header  information associated  with  the datum.
            Keeping the length in bits instead of bytes frees the
            caller from having to keep track of the actual length
            of her elements.

4 ELEMENT STORAGE MANAGEMENT

     Elements  are  stored  as  one  or  more  datums  in control
intervals.  There  are two methods of  element storage, the Basic
Element  Storage Method  (BESM) and  the Ordered  Element Storage
Method (OESM).


Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

4.1 Storing elements as datums

     A datum is the unit of storage inside of a control interval.
A datum is a bit string of  any arbitrary size that will fit in a
single control interval.  An element is  made up of one datum for
each  control interval  in which the  element is  stored.  So, an
element which is  stored in a single control  interval is made up
of exactly one datum; in fact,  the element and the datum are the
same  string.   An  element  which  is  stored  in  five  control
intervals is divided up into five  pieces, each a datum stored in
a single control interval.

     A datum  can be one of  four types:  datum, continued_datum,
continuation_datum  and continued_continuation_datum.   The first
is used to  store an entire element in  a single control interval
and  is no  more than  a bit  string.  A  multi-datum element (an
element  composed   of  more  than  one   datum)  consists  of  a
continued_datum  which  holds  the  beginning of  the  element, a
continuation_datum which holds the end, and some number, possibly
zero, of continued_continuation_datums in  the middle.  The types
of datums are discussed in the section titled "DATUM STRUCTURES".

4.2 Allocating a new element

     Allocating  a  new  element  actually  entails  two  things,
allocating space for  the element and storing the  element in the
newly  found space.   Regardless of the  ESM, the  new element is
first checked to  see if it can be stored  in a single datum.  If
it cannot, meaning  that its length in bytes  is greater than the
value         of         MAXIMUM_DATUM_LENGTH_IN_BYTES         in
dm_cm_datum_constants.incl.pl1,  the  "overlength  tail"  of  the
element  is first  allocated.  The  element is  divided into some
number   of   maximum-sized   datums   and  no   more   than  one
less-than-maximum-sized datum.   The latter is  a continued_datum
holding  the  beginning  of  the   element;  the  former  is  the
overlength   tail   of    continued_continuation_datums   and   a
continuation_datum.   For  each datum  of  the overlength  tail a
control interval is allocated, and  the datum is allocated in the
new  control  interval.  The  remaining  datum is  then allocated
according to the rules of the ESM the collection employs.

     A BESM collection allocates a datum holding either an entire
element  or  the first  portion  of an  element by  searching the
following control intervals for sufficient space:
   o If the caller supplied the  identifier of a related element,
     the control interval in which the related element is stored;
   o The last control interval of the collection;
   o A newly allocated control interval.
These control intervals  are checked, in the given  order, to see


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

if   the  amount   of  space   in  the   free  pool   bounded  by
start_of_used_space and the end of the datum_position_table, plus
the  amount  of scattered_free_space  is  sufficient to  hold the
datum.  Note that the last alternative, a newly allocated control
interval,  will always  be able to  hold the datum.   When one is
found, the slot  number assigned to the datum  will be the lowest
numbered  unused  slot in  the  control interval.   The  datum is
stored in the free pool.  This may mean that the control interval
must  be compacted  to recover scattered  free space  if the free
pool is not large enough by itself to hold the datum.

     An OESM collection requires  the caller to explicitly supply
the control  interval and slot  to be used in  allocating the new
element.   If the  control interval  is not  already reserved and
allocated  by this  collection, the call  is in  error.  Only the
given  control interval  is checked for  space.  If  there is not
sufficient free space to store  the datum containing the element,
or the  beginning of the element,  collection_manager_ returns an
error to the caller along with the amount of free space over what
the  control interval  already has  that would  have to  exist in
order  for  the allocation  to be  successful.  It  is up  to the
caller to move  datums out of the control  interval to make space
on a subsequent attempt.

     The slot used  is the one specified by  the caller.  If that
slot is already  in use, it and all higher  slots are shifted one
slot  up.   If  the  specified  slot is  beyond  the  end  of the
datum_position_table, all slots between the previous last slot of
the table  and the new slot  are initialized to be  free slots by
zeroing them out.   If the specified slot was a  free slot, it is
used and no slots are shifted.

4.3 Modifying the value of an existing element.

     An  element is  modified by  storing a  new value  in an old
element.   For a  BESM collection, if  the existing  element is a
single datum, the following steps are taken:

  1) Divide the  new value into  a datum the size  of modulo (new
     value length,  maximum datum size)  and, if this  is not the
     entire value, the remaining overlength tail;
  2) Allocate  each  datum in  the overlength  tail just  as when
     allocating a new element;
  3) Store the  remaining datum.  If  the remaining datum  is not
     larger than the old value, re-use the space in which the old
     value was stored  and free any excess space  by adding it to
     the scattered free space.  If  the remaining datum is larger
     than the old value, but there is enough space in the control
     interval for the remaining  datum (including the space taken


Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

     up by  the old datum),  free the space  taken up by  the old
     datum and allocate new space  for the remaining datum.  This
     may  require  compacting  the  control  interval  to recover
     scattered free  space.  If there  is not enough  room in the
     control interval to store  the remaining datum, allocate the
     remaining datum  in another control interval  and re-use the
     space taken up by the  old datum to store a continued_datum.
     This continued_datum  has a header pointing  to wherever the
     remaining datum was allocated and no contents.

     Using an OESM collection, there are a couple of differences.
After step 1, check to see if  the remaining datum can fit in the
control interval in which the old datum is stored.  If it cannot,
return immediately  with an error.   Step 3 is  simplified by the
fact that it is known that  the remaining datum will fit.  Either
it  re-uses the  space in  which the old  datum was  stored or it
frees that space and allocates  new space for the remaining datum
in that control interval.

     The  actions taken  when the  existing element  is already a
multi-datum  element  are only  slightly  different.  In  step 2,
instead of allocating a new  overlength tail, the storage held by
the  old  overlength  tail is  re-used.   Each datum  of  the old
overlength  tail  that  is  not re-used  is  freed.   If  the new
overlength  tail  requires more  space  than the  old,  then each
remaining datum  is stored in a  newly allocated control interval
in  the same  manner as  when allocating  a whole  new overlength
tail.  In a BESM collection, it  is possible for the second datum
of  the  element (the  first continued_continuation_datum)  to be
less  than maximum-sized.   If at  the time  of modification this
datum can  now fit in  the first datum's control  interval, it is
freed and stored as the first datum.

5 CONTROL INTERVAL STORAGE MANAGEMENT

     There are two levels  of control interval storge management:
managing the control  intervals (CIs) in a file  and managing the
CIs in  a collection.  File  CI management consists  of reserving
CIs  to  a  collection  from  a  pool  of  CIs  available  to all
collections of the  file, and releasing CIs back  into that pool.
Collection CI  management consists of allocating  CIs from a pool
of CIs reserved  by a collection, and freeing  CIs back into that
pool.

     CIs in a file can be in  one of three states:  reserved by a
collection  and  allocated  for   use  (in-use),  reserved  by  a
collection but not allocated for  use (un-used), and not reserved
by   any   collection.   Collection_manager_   maintains   a  map
(file_reservation_map)  which   indicates  whether  each   CI  is


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

available for reservation.   Collection_manager_ also maintains a
map  (collection_allocation_map) for  each collection  which uses
collection CI management.   which holds a bit for  each CI in the
collection indicating whether the CI is un-used or in-use.

     There  are  two  control interval  storage  methods (CISMs):
Blocked  and Unblocked.   BCISM collections employ  both file and
collection  CI management.   UCISM collections  only use  file CI
management.

5.1 Allocating a CI

     A UCISM  collection couples reservation  and allocation CIs.
CIs   are   reserved/allocated   one   at   a   time   using  the
file_reservation_map.   CIs in  the collection are  threaded in a
chronological   list   based   on   time   of   allocation.   The
reservation/allocation of a CI consists of the following steps:
  1) Find a free CI in the file_reservation_map;
  2) Initialize a CI header;
  3) Add a  backward pointer to  the CI that is  currently at the
     end of the list of CIs;
  4) Write the header and pointer into the file;
  5) Update the last  CI of the list to point  forward to the new
     CI;
  6) Update the  collection's header to indicate  that the new CI
     is now at the end of the collection.

     BCISM  collections consist  of blocks  of reserved  CIs from
which  individual  CIs  are  allocated.   Each  BCISM  collection
maintains  a collection_allocation_map,  divided into  a block of
map for each block of reserved  CIs.  Allocating a CI consists of
the  following  steps,  where  steps 1-5  allocate  a  CI  from a
collection and steps 6-9 reserve a block of CIs:
  1) Find a free CI in the collection_allocation_map.  If no free
     CI is found, skip to step 6;
  2) Initialize a local CI header;
  3) Write the header into the file;
  4) Update the collection_allocation_map;
  5) Quit.
  6) Find a block of free CIs in the file_reservation_map;
  7) Update the file_reservation_map, reserving the CIs;
  8) Create  a new  block in  the collection_allocation_map which
     indicates that all of its CIs are free;
  9) Go to step 1.


Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

5.2 Freeing a CI

     Freeing a CI in a UCISM collection consists of the following
steps:
  1) Re-thread the previous and next CIs;
  2) Update  the file_reservation_map  to indicate the  CI is now
     free;
  3) Zero out the CI.;
  4) If the CI was the first or last CI of the collection, update
     the collection's  header to indicate  the new first  or last
     CI.

     Freeing a  CI in a  BCISM collection consists  the following
steps:
  1) Update the collection_allocation_map;
  2) Zero out the CI;
  3) If the block now contains  no in-use CIs and this collection
     holds another block containing no in-use CIs, release all of
     the  CIs  in the  block  back to  the  file by  updating the
     file_reservation_map to indicate that  they are now free and
     delete   the   block  from   the  collection_allocation_map.
     Holding    on   to    one   free   block    cuts   down   on
     reservation/release  overhead  and  prevents  a  scenario in
     which a collection  wavering between N and N+1  CIs long can
     cause a block to be reserved/released on each allocate/free.

5.3 Supporting control structures

The file_reservation_map is divided into fixed sized fragments to
increase concurrent access to the  map.  Each fragment of the map
is simply  a string of  bits stored as  an element in  the Header
Collection.  The location of each fragment is recorded in another
element  containing  the  file_reservation_map  structure,  which
follows:

     dcl 1 file_reservation_map  (frm_number_of_fragments) aligned
                                 based (file_reservation_map_ptr),
         2 flags                 unaligned,
           3 no_control_intervals_are_available
                                 bit (1),
           3 must_be_zero        bit (11),
         2 lowest_numbered_control_interval
                                 fixed bin (24) uns unal,
         2 element_id            bit (36) aligned;

where  each entry  in the  file_reservtion_map array  describes a
fragment    located     at    element_id.     The     value    of
frm_number_of_fragments  is  obtained   from  the  cm_file_header
described in the section titled "THE HEADER COLLECTION".


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

     The  collection_allocation_map,  identical  in  structure to
file_reservation_map, keeps  track of the blocks  of a collection
allocation map.

6 DATUM STRUCTURES

     Datums are the storage units in which elements are stored in
control intervals.  If the element is too long to fit in a single
control interval, it is continued  in another control interval by
dividing element  into multiple datums.  There  can be any number
of continuation datums for a single element.

     Datums are stored in 4 kinds of structures, depending on the
use   of  continuations:    datum  (D),   continued_datum  (CdD),
continuation_datum  (CnD),  continued_continuation_datum (CdCnD).
If an element  fits within a single control  interval of the page
file, it is allocated within a single datum, or D, structure.  If
it does not  fit within a single control  interval, the first (or
left-most)   portion   of   the   element  is   allocated   in  a
continued_datum (CdD)  structure, succeeding portions  except for
the  final  one  are  allocated  in  continued_continuation_datum
(CdCnD)  structures,  and the  final  portion is  allocated  in a
continuation_datum (CnD) structure.  If  an element requires only
one continuation to  be allocated, then it is  allocated with the
first portion in a CdD structure  and the second portion in a CnD
structure.
     These structures are as follows:

     dcl       datum                bit (d_length_in_bits)
                                    aligned based (datum_ptr),

     dcl     1 continued_datum    aligned based (datum_ptr),
               2 full_length        fixed bin (35),
               2 continuation       like datum_id,
               2 contents           bit (cdd_length_in_bits);

     dcl       continuation_datum   bit (cnd_length_in_bits)
                                    aligned
                                    based (
                                    continuation_datum_ptr),

     dcl     1 continued_continuation_datum
                                    aligned
                                    based (
                                    continuation_datum_ptr),
               2 continuation       like datum_id,
               2 contents           bit (
                                    cdcnd_length_in_bits);


Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

     dcl     1 datum_id             aligned
                                    based (datum_id_ptr),
               2 control_interval_id
                                    fixed bin (24) unal unsigned,
               2 index              fixed bin (12) unal unsigned;

7 THE HEADER COLLECTION

     The  collection_manager_  module maintains  a  collection in
which it stores control information called the Header Collection.
It's  collection  identifier  is  HEADER_COLLECTION_ID,  found in
dm_cm_hdr_collection_id.incl.pl1.  The Header  Collection is used
to  keep internal  per-file information,  internal per-collection
information and  caller-defined information.  The  information is
stored in  elements and accessed  via the same  mechanisms as for
other collections, using the Basic Element Storage Method and the
Unblocked Control Interval Method.   The Header Collection always
includes CI 0 and CI 1, but may include more CIs.

     The  major structures  kept in  the Header  Collection which
describe the file are the cm_file_header, the collection_id_table
and the file_reservation_map.   The cm_file_header contains basic
per-file information and its declaration follows:

  dcl  1 cm_file_header     aligned based (cm_file_header_ptr),
       2 version            char (8),
       2 highest_numbered_ci
                            fixed bin (24) unsigned,
       2 number_of_collections
                            fixed bin (17) unal,
       2 number_of_blocks   fixed bin (17) unal,
       2 number_of_control_intervals_per_block
                            fixed bin (17),
       2 allocation_map_element_id
                            bit (36) aligned,
       2 collection_id_table_element_id
                            bit (36) aligned;

where allocation_map_element_id is the  identifier of the element
holding the  file_reservation_map; collection_id_table_element_id
is the identifier of  the element holding the collection_id_table
and  number_of_blocks  and  number_of_control_intervals_per_block
describe  the  shape  of the  file_reservation_map.   The element
identifier  of  the cm_file_header  is CM_FILE_HEADER_ELEMENT_ID,
found in dm_cm_file_header.incl.pl1.

     The  collection_id_table contains  the collection identifier
of each collection in the  file, excluding the Header Collection.
The collection_id_table follows:


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

  dcl collection_id_table    (cit_number_of_collections)
                             bit (36) aligned
                             based (collection_id_table_ptr);

The  file_reservation_map is  described under  the section titled
"CONTROL INTERVAL STORAGE MANAGEMENT".

     Associated  with  each  collection  is  a  collection_header
structure, a  header supplied by  the user and  a storage record.
The collection_header structure contains stable information about
a   collection.   The   collection  identifier   is  the  element
identifier of the element in which this structure is stored.

    dcl      1 collection_header    aligned based
                                    (collection_header_ptr),
               2 version            char (8),
               2 flags              unaligned,
                 3 fixed_size_elements
                                    bit (1),
                 3 thread_elements  bit (1),
                 3 thread_control_intervals
                                    bit (1),
                 3 must_be_zero1    bit (15),
               2 control_interval_storage_method
                                    fixed bin (17) unaligned,
               2 element_storage_method
                                    fixed bin (17),
               2 maximum_element_size
                                    fixed bin (35),
               2 header_record_element_id
                                    bit (36) aligned,
               2 storage_record_element_id
                                    bit (36) aligned;

The storage_record_element_id  refers to an  element containing a
storage record.  The storage  record contains dynamic information
about the collection, such as the first and last CI numbers.  The
storage  record  is  separated  from  collection_header  for  two
reasons:   different  types   of  collections  require  different
control  information  and  separating   the  stable  and  dynamic
portions increases concurrent access  to header information.  The
header_record_element_id  refers to  a caller-supplied collection
header accessed via the $put_header and $get_header entries.

     The caller may store any  elements in the Header Collection,
but  the  location  of  the   elements,  and  hence  the  element
identifier cannot be guaranteed.  For  this reason, an element is
reserved in  the third slot of  CI 0 for use  by the caller.  The


Multics Technical Bulletin                                MTB-552
DM: collection_manager_ design

element    identifier    is    CALLER_FILE_HEADER_ELEMENT_ID   in
dm_cm_caller_hdr_id.incl.pl1.

8 COLLECTION_MANAGER_ USE OF COLLECTION_MANAGER_

     The  collection_manager_  module makes  considerable  use of
itself to  manage the Header  Collection.  For example,  to add a
collection to a file:

     call collection_manager_$allocate_element
                    (         /* Allocate new storage_record. */
                    file_opening_id, HEADER_COLLECTION_ID,
                    storage_record_ptr, storage_record_length,
                    collection_header.storage_record_element_id,
                    (0), code
                    );
     call collection_manager_$allocate_element
                    (         /* Allocate new collection_header. */
                    file_opening_id, HEADER_COLLECTION_ID,
                    collection_header_ptr, collection_header_length,
                    collection_id, (0), code
                    );

And to get the first fragment of the file_reservation_map:

     call collection_manager_$get_element
                    (      /* Get cm_file_header. */
                    file_opening_id, HEADER_COLLECTION_ID,
                    CM_FILE_HEADER_ELEMENT_ID, 0,
                    buffer_ptr, buffer_length, work_area_ptr, ("0"b),
                    cm_file_header_ptr, cm_file_header_length,
                    code
                    );
     call collection_manager_$get_element
                    (      /* Get file_reservation_map. */
                    file_opening_id, HEADER_COLLECTION_ID,
                    cm_file_header.allocation_map_element_id, 0
                    buffer_ptr, buffer_length, area_ptr, ("0"b),
                    file_reservation_map_ptr,
                    file_reservtion_map_length, code
                    );
     call collection_manager_$get_element
                    (      /* Get first file_reservtion_map_fragment. */
                    file_opening_id, HEADER_COLLECTION_ID,
                    (file_reservation_map.element_id (1)), 0,
                    buffer_ptr, buffer_length, area_ptr, ("0"b),
                    file_reservation_map_fragment_ptr,
                    file_reservtion_map_fragment_length,


MTB-552                                Multics Technical Bulletin
                                   DM: collection_manager_ design

                    code
                    );