sm_mdes.c

Go to the documentation of this file.

/*****************************************************************************\
 *      File:   sm_mdes.c
 *      Author: John C. Gyllenhaal
 *      Creation Date:  March 1996
 *      Copyright (c) 1996 John C. Gyllenhaal, Wen-mei Hwu and
 *                         The Board of Trustees of the University of Illinois.
 *                         All rights reserved.
 *      The University of Illinois software License Agreement
 *      specifies the terms and conditions for redistribution.
\*****************************************************************************/

#ifndef lint
#define lint
static char copyright[] =
"@(#) Copyright (c) 1996 John C. Gyllenhaal, Wen-mei Hwu and The Board of \n\
 Trustees of the University of Illinois. All rights reserved.\n";
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sm_mdes.h"
#include "mdes2.h"
#include "l_alloc_new.h"
#include "l_punt.h"

#define DEBUG_MDES 0

static L_Alloc_Pool *SM_Mdes_pool = NULL;

int SM_add_ids_to_entries (MD_Section *section)
{
    MD_Entry *entry;
    MD_Field_Decl *id_field_decl;
    MD_Field *id_field;
    int id;

    /* Punt if there is already a field declared */
    if ((id_field_decl = MD_find_field_decl (section, "id")) != NULL)
        L_punt ("SM_add_ids_to_entries: Section '%s' already has id field!",
                section->name);

    /* Create required id field with one INT */
    id_field_decl = MD_new_field_decl (section, "id", MD_REQUIRED_FIELD);
    MD_require_int (id_field_decl, 0);

    /* Add ids to each field, starting with 0 */
    id = 0;
    for (entry = MD_first_entry (section); entry != NULL;
         entry = MD_next_entry (entry))
    {
        /* Create id field */
        id_field = MD_new_field (entry, id_field_decl, 1);
        MD_set_int (id_field, 0, id);

        id++;
    }

    /* Return the number of entries in this section */
    return (id);
}

void SM_build_resources (SM_Mdes *sm_mdes)
{
    SM_Resource *resource, *resource_array;
    MD_Section  *resource_section;
    MD_Entry    *resource_entry;
    MD_Field_Decl *map_location_field_decl;
    MD_Field    *map_location_field;
    int         num_resources, size, index, id;
    int         time_shift, max_offset;

    /* Get the resources section and the decl for map_location */
    resource_section = MD_find_section (sm_mdes->md_mdes, "Resource");
    map_location_field_decl = MD_find_field_decl (resource_section, 
                                                  "map_location");

    /* Add id's to each Resource entry (used to index array) 
     * and get the number of entries in the Resource section.
     */
    num_resources =  SM_add_ids_to_entries (resource_section);

    /* Malloc an array of resources to hold info about each resource */
    size = num_resources * sizeof (SM_Resource);
    if ((resource_array = (SM_Resource *) malloc (size)) == NULL)
        L_punt ("SM_build_resources: Out of memory");

    /* Copy contents of resource section into resource array,
     * array indexed by id of entry (numbered from 0 above)
     */
    id = 0;
    max_offset = -1;
    for (resource_entry = MD_first_entry (resource_section); 
         resource_entry != NULL;
         resource_entry = MD_next_entry (resource_entry))
    {
        /* Get pointer to resource we are building */
        resource = &resource_array[id];

        /* Copy the resource's name */
        resource->name = strdup (resource_entry->name);
        
        /* Copy the map location information to resource array */
        map_location_field = MD_find_field (resource_entry, 
                                            map_location_field_decl);

        /* Get the resource base offset into resource map */
        resource->offset = MD_get_int (map_location_field, 0);

        if (resource->offset > max_offset)
            max_offset = resource->offset;

        /* Place 1 at bit location specified by resource's index */
        index = MD_get_int (map_location_field, 0);
// ** mdj change, seems that correct mask is generated if 0 used
//      index = MD_get_int (map_location_field, 1);
        resource->mask = (1 << index);
        
#if DEBUG_MDES
        printf ("Resource %s: %i offset %x mask\n", resource->name,
                resource->offset, resource->mask);
#endif

        /* Increment the id */
        id++;
    }

    /* Sanity check */
    if (id != num_resources)
    {
        L_punt("SM_build_resources: id (%i) and # resources (%i) should agree",
               id, num_resources);
    }

    /* Calculate how many words/cycle is needed in the resource map
     * Always make a power of two so shifts can be used!
     * Store the amount to shift in sm_mdes->time_shift.
     */
    time_shift = 0;
    while ((max_offset + 1) > (1 << time_shift))
        time_shift++;
    
    sm_mdes->map_width = 1 << time_shift;
    sm_mdes->time_shift = time_shift;

#if 0
    sm_mdes->time_shift += 0;
    printf ("Increasing time shift to %i\n", sm_mdes->time_shift);
#endif
    

    /* Point sm_mdes at resource array */
    sm_mdes->resource = resource_array;
    sm_mdes->num_resources = num_resources;
}

void SM_build_units (SM_Mdes *sm_mdes)
{
    SM_Resource *resource_array, *resource;
    SM_Option   *unit_array, *unit;
    SM_Usage    *usage_array, *usage;
    MD_Section *unit_section, *usage_section, *resource_section;
    MD_Entry   *unit_entry, *ru_entry, *resource_entry;
    MD_Field_Decl *unit_use_field_decl, *resource_id_field_decl;
    MD_Field_Decl *ru_use_field_decl, *ru_time_field_decl;
    MD_Field   *unit_use_field, *ru_use_field, *ru_time_field;
    MD_Field *resource_id_field;
    int num_units, array_size, num_usages;
    int index1, index2, id;
    int resources_used, map_offset, resource_offset;
    int usage_time, resource_id, time_shift;

    /* Get resource array for speed and ease of use */
    resource_array = sm_mdes->resource;

    /* Get the amount to shift the time of usage for ease of use */
    time_shift = sm_mdes->time_shift;

    /* Get the unit section and the use decl for use */
    unit_section = MD_find_section (sm_mdes->md_mdes, "Resource_Unit");
    unit_use_field_decl = MD_find_field_decl (unit_section, "use");

    /* Get the usage section and decls for ease of use */
    usage_section = MD_find_section (sm_mdes->md_mdes, "Resource_Usage");
    ru_use_field_decl = MD_find_field_decl (usage_section, "use");
    ru_time_field_decl = MD_find_field_decl (usage_section, "time");

    /* Get the resource section and id decl for ease of use */
    resource_section = MD_find_section (sm_mdes->md_mdes, "Resource");
    resource_id_field_decl = MD_find_field_decl (resource_section, "id");

    /* Add id's to each unit entry (used to index array) 
     * and get the number of entries in the Resource_Unit section.
     */
    num_units =  SM_add_ids_to_entries (unit_section);

    /* Malloc an array of units to hold info about each resource unit */
    array_size = num_units * sizeof (SM_Option);
    if ((unit_array = (SM_Option *) malloc (array_size)) == NULL)
        L_punt ("SM_build_units: Out of memory");

    /* Use contents of the resource unit section (with Resource_Usage
     * and Resource links used) to the unit array.
     * Index array by id (numbered from 0 by SM_add_ids_to_entries)
     */
    id = 0;
    for (unit_entry = MD_first_entry (unit_section); 
         unit_entry != NULL;
         unit_entry = MD_next_entry (unit_entry))
    {
        /* Get pointer to unit we are building */
        unit = &unit_array[id];

#if DEBUG_MDES
        printf ("Building %s:\n", unit_entry->name);
#endif

        /* Get the unit's use field */
        unit_use_field = MD_find_field (unit_entry, unit_use_field_decl);
        
        /* Create an array to hold all the usages in the use field */
        num_usages = unit_use_field->max_element_index + 1;
        array_size = num_usages * sizeof (SM_Usage);
        if ((usage_array = (SM_Usage *) malloc (array_size)) == NULL)
            L_punt ("SM_build_units: Out of memory");

        /* Build each usage in the array */
        for (index1 = 0; index1 < num_usages; index1++)
        {
            /* Get pointer to usage we are building */
            usage = &usage_array[index1];

            /* Get the ru_entry for this usage */
            ru_entry = MD_get_link (unit_use_field, index1);

            /* Get the time of this usage */
            ru_time_field = MD_find_field (ru_entry, ru_time_field_decl);
            usage_time = MD_get_int (ru_time_field, 0);

            /* Build the bit mask for the resource(s) used by this usage */
            resources_used = 0;
            resource_offset = -1;
            ru_use_field = MD_find_field (ru_entry, ru_use_field_decl);
            for (index2 = 0; index2 <= ru_use_field->max_element_index;
                 index2++)
            {
                /* Get the resource entry at this index */
                resource_entry = MD_get_link (ru_use_field, index2);
                
                /* Get the id of this resource entry */
                resource_id_field = MD_find_field (resource_entry, 
                                                   resource_id_field_decl);
                resource_id = MD_get_int (resource_id_field, 0);

                /* Get the resource from this id */
                resource = &resource_array[resource_id];

                /* Or in the bit for this resource */
                resources_used |= resource->mask;

                /* If this is the first resource added, get resource offset 
                 * from it, otherwise check for consistency
                 */
                if (index2 == 0)
                    resource_offset = resource->offset;
                else if (resource_offset != resource->offset)
                {
                    L_punt ("SM_build_units: Offset mismatch (%i != %i)",
                            resource_offset, resource->offset);
                }
            }

            /* Calculate the map offset, uses the width of the map 
             * (encoded into the map shift) and the offset of the usage.
             */
            map_offset = (usage_time << time_shift) + resource_offset;

            /* Save into to usage */
            usage->resources_used = resources_used;
            usage->map_offset = map_offset;

#if DEBUG_MDES
            printf ("  %x at offset %i\n", resources_used, map_offset);
#endif
        }

        /* Point unit at begining and end of usage */
        unit->first_usage = usage_array;
        unit->last_usage = &usage_array[num_usages - 1];

        /* Increment the id */
        id++;
    }

    /* Sanity check */
    if (id != num_units)
        L_punt ("SM_build_units: id (%i) and num_units (%i) should agree!",
                id, num_units);

    
    /* Point sm_mdes at unit array and set its size*/
    sm_mdes->unit_array = unit_array;
    sm_mdes->unit_array_size = num_units;
}

void SM_build_choices (SM_Mdes *sm_mdes)
{
    SM_Choice   *choice_array, *choice;
    SM_Option   *option_array, *option, *unit;
    MD_Section  *option_section, *unit_section;
    MD_Entry    *option_entry, *unit_entry;
    MD_Field_Decl *one_of_field_decl, *unit_id_field_decl;
    MD_Field    *one_of_field, *unit_id_field;
    int         num_choices, num_options, unit_id;
    int         id, array_size, index1;

    /* Get the unit section and id field decl for ease of use */
    unit_section = MD_find_section (sm_mdes->md_mdes, "Resource_Unit");
    unit_id_field_decl = MD_find_field_decl (unit_section, "id");

    /* Get the option section and one_of field decl for ease of use 
     * Used to build SM_Choice array.
     */
    option_section = MD_find_section (sm_mdes->md_mdes, "Table_Option");
    one_of_field_decl = MD_find_field_decl (option_section, "one_of");

    /* Add id's to each Option entry (used to index array)
     * and get the number of entries in the Option section.
     */
    num_choices =  SM_add_ids_to_entries (option_section);

    /* Malloc an array to hold choice info */
    array_size = num_choices * sizeof (SM_Choice);
    if ((choice_array = (SM_Choice *)malloc (array_size)) == NULL)
        L_punt ("SM_build_choices: Out of memory");

    /* Build choice array using option_section entry info */
    id = 0;
    for (option_entry = MD_first_entry (option_section); option_entry != NULL;
         option_entry = MD_next_entry (option_entry))
    {
        /* Get pointer to the choice we are building */
        choice = &choice_array[id];

#if DEBUG_MDES
        printf ("Building choice %s:\n", option_entry->name);
#endif
        
        /* Get the option's one_of field */
        one_of_field = MD_find_field (option_entry, one_of_field_decl);

        /* Create an array to hold all the units in the one_of field */
        num_options = one_of_field->max_element_index + 1;
        array_size = num_options * sizeof (SM_Option);
        if ((option_array = (SM_Option *) malloc (array_size)) == NULL)
            L_punt ("SM_build_choices: Out of memory");

        /* Build the options in the array */
        for (index1 = 0; index1 < num_options; index1 ++)
        {
            /* Get pointer to the option we are building */
            option = &option_array[index1];

            /* Get pointer to this option's unit */
            unit_entry = MD_get_link (one_of_field, index1);
            unit_id_field = MD_find_field (unit_entry, unit_id_field_decl);
            unit_id = MD_get_int (unit_id_field, 0);
            unit = &sm_mdes->unit_array[unit_id];

            /* Point the option at the unit's usages */
            option->first_usage = unit->first_usage;
            option->last_usage = unit->last_usage;
#if DEBUG_MDES
            printf ("  Option %i: unit %s,  offset %i to %i\n",
                    index1,
                    unit_entry->name,
                    option->first_usage->map_offset, 
                    option->last_usage->map_offset);
#endif
        }

        /* Set the bounds of the option array in this choice */
        choice->first_option = option_array;
        choice->last_option = &option_array[num_options -1];

        /* Update id */
        id++;
    }

    /* Sanity check */
    if (id != num_choices)
        L_punt ("SM_build_choices: id (%i) and num_choices (%i) should agree!",
                id, num_choices);


    /* Point sm_mdes at choice array and set its size */
    sm_mdes->choice_array = choice_array;
    sm_mdes->choice_array_size = num_choices;
}

void SM_build_tables (SM_Mdes *sm_mdes)
{
    SM_Table    *table_array, *table;
    SM_Choice   *choice_array, *choice, *target_choice;
    MD_Section  *table_section, *option_section, *unit_section;
    MD_Entry    *table_entry, *option_entry, *unit_entry, *slot_specifier;
    MD_Field_Decl *one_of_field_decl, *option_id_field_decl;
    MD_Field_Decl *table_use_field_decl, *slot_specifier_field_decl;
    MD_Field_Decl *slot_field_decl, *max_time_field_decl;
    MD_Field    *one_of_field, *option_id_field;
    MD_Field    *table_use_field, *slot_specifier_field, *max_time_field;
    MD_Field    *slot_field;
    unsigned short *slot_options;
    int         num_tables, num_choices, num_options, option_id;
    int         id, array_size, index1, slot_index;
    unsigned int max_usage_time, time_shift;
    int         max_num_choices;


    /* Get the table section and use field decl for ease of use 
     * Used to build SM_Table array.
     */
    table_section = MD_find_section (sm_mdes->md_mdes, "Reservation_Table");
    table_use_field_decl = MD_find_field_decl (table_section, "use");
    slot_specifier_field_decl = MD_find_field_decl (table_section, 
                                                    "slot_specifier");
    max_time_field_decl = MD_find_field_decl (table_section, 
                                              "max_usage_time");

    /* Get the option section and id and one_of field decl for ease of use */
    option_section = MD_find_section (sm_mdes->md_mdes, "Table_Option");
    option_id_field_decl = MD_find_field_decl (option_section, "id");
    one_of_field_decl = MD_find_field_decl (option_section, "one_of");

    /* Get the unit section and the slot field for ease of use */
    unit_section = MD_find_section (sm_mdes->md_mdes, "Resource_Unit");
    slot_field_decl = MD_find_field_decl (unit_section, "slot");

    /* Get the time shift for max_usage_times's */
    time_shift = sm_mdes->time_shift;

    /* Add id's to each Reservation Table entry (used to index array)
     * and get the number of entries in the Reservation Table section.
     */
    num_tables =  SM_add_ids_to_entries (table_section);

    /* Malloc an array to hold table info */
    array_size = num_tables * sizeof (SM_Table);
    if ((table_array = (SM_Table *) malloc (array_size)) == NULL)
        L_punt ("SM_build_tables: Out of memory");

    /* Calculate the max number of choices, so the schedule manager
     * can always create a choice array big enough for any table.
     */
    max_num_choices = 0;

    /* Build table array using table_section entry info */
    id = 0;
    for (table_entry = MD_first_entry (table_section); table_entry != NULL;
         table_entry = MD_next_entry (table_entry))
    {
        /* Get pointer to the table we are building */
        table = &table_array[id];

#if DEBUG_MDES
        printf ("Building table %s:\n", table_entry->name);
#endif
        
        /* Get the table's use field */
        table_use_field = MD_find_field (table_entry, table_use_field_decl);

        /* Get the slot specifier (option entry pointer) */
        slot_specifier_field = MD_find_field (table_entry, 
                                              slot_specifier_field_decl);
        slot_specifier = MD_get_link (slot_specifier_field, 0);

        /* Create an array to hold all the choices in the use field */
        num_choices = table_use_field->max_element_index + 1;
        array_size = num_choices * sizeof (SM_Choice);
        if ((choice_array = (SM_Choice *) malloc (array_size)) == NULL)
          L_punt ("SM_build_tables: Out of memory");

        /* Update max_num_choices */
        if (num_choices > max_num_choices)
            max_num_choices = num_choices;

        /* Point each choice at the appropriate array.  Also identify
         * choice that specifies the slot
         */
        slot_index = -1;
        for (index1 = 0; index1 < num_choices; index1 ++)
        {
            /* Get pointer to the choice we are building */
            choice = &choice_array[index1];

            /* Get pointer to this choice's option entry */
            option_entry = MD_get_link (table_use_field, index1);
            option_id_field = MD_find_field (option_entry, 
                                             option_id_field_decl);
            option_id = MD_get_int (option_id_field, 0);
            target_choice = &sm_mdes->choice_array[option_id];

            /* Point the option at the unit's usages */
            choice->first_option = target_choice->first_option;
            choice->last_option = target_choice->last_option;

#if DEBUG_MDES
            printf ("  Choice %i: option %s id %i %x to %x (%i options)\n", 
                    index1, 
                    option_entry->name, option_id,
                    choice->first_option, choice->last_option, 
                    (choice->last_option - choice->first_option) + 1);
#endif

            /* Is this the choice that specifies the slot */
            if (option_entry == slot_specifier)
            {
                slot_index = index1;
#if DEBUG_MDES
                printf ("    Slot specifier %s found.\n", 
                        slot_specifier->name);
#endif
            }

        }
        table->first_choice = choice_array;
        table->last_choice = &choice_array[num_choices -1];
        table->num_choices = num_choices;

        /* Make sure a slot was specified */
        if (slot_index == -1)
        {
            L_punt ("SM_build_tables: slot specifier %s not found in %s!\n",
                    slot_specifier->name, table_entry->name);
        }
        table->slot_choice = &choice_array[slot_index];

        /* Build the slot_options array (specifies slot used based on
         * the option chosen in slot_choice.
         */
        one_of_field = MD_find_field (slot_specifier, one_of_field_decl);
        num_options = one_of_field->max_element_index + 1;
        array_size = num_options * sizeof (unsigned short);
        if ((slot_options = (unsigned short *) malloc (array_size)) == NULL)
            L_punt ("SM_build_tables: Out of memory");

#if DEBUG_MDES
        printf ("    Slot options:");
#endif
        /* Get the slot from each option's unit entry */
        for (index1 = 0; index1 <= one_of_field->max_element_index; index1++)
        {
            unit_entry = MD_get_link (one_of_field, index1);
            slot_field = MD_find_field (unit_entry, slot_field_decl);
            slot_options[index1] = 
                (unsigned short) MD_get_int (slot_field, 0);
#if DEBUG_MDES
            printf (" %i", slot_options[index1]);
#endif
        }
#if DEBUG_MDES
        printf ("\n");
#endif
        
        /* Point table at slot option array */
        table->slot_options = slot_options;
        
        /* Get the max_usage_time for this table */
        max_time_field = MD_find_field (table_entry, max_time_field_decl);
        max_usage_time = MD_get_int (max_time_field, 0);

        /* Calculate the max usage offset using the resource time_shift.
         * Want to get the offset for the last element at that time.
         * To do this, find the first element of time + 1, and subtract 1.
         * This turns 3 with time shift 1, into ((3 + 1) << 1) -1 = 7
         */
        table->max_usage_offset = ((max_usage_time + 1) << time_shift) - 1;

#if DEBUG_OPTI
        printf (" %s max_usage_time = %i\n", table_entry->name, 
                table->max_usage_time);
#endif

        /* Update id */
        id++;
    }

    /* Sanity check */
    if (id != num_tables)
        L_punt ("SM_build_tables: id (%i) and num_tables (%i) should agree!",
                id, num_tables);

    /* Point sm_mdes at table array and set its size */
    sm_mdes->table_array = table_array;
    sm_mdes->table_array_size = num_tables;

    /* Write the maximumn number of choices across all tables to sm_mdes */
    sm_mdes->max_num_choices = max_num_choices;
}

SM_Mdes *SM_build_mdes (Mdes2 *mdes2)
{
    SM_Mdes *sm_mdes;


    /* Create alloc pool if necessary */
    if (SM_Mdes_pool == NULL)
        SM_Mdes_pool = L_create_alloc_pool ("SM_Mdes", sizeof (SM_Mdes), 1);

    /* Alloc sm_mdes data structure */
    sm_mdes = (SM_Mdes *) L_alloc (SM_Mdes_pool);

    /* Point at the mdes2 this sm_mdes is being built from */
    sm_mdes->mdes2 = mdes2;
    sm_mdes->md_mdes = mdes2->md_mdes;

    /* Build the resource array, set num_resources, map_width, 
     * and time_shift.
     */
    SM_build_resources (sm_mdes);

    /* Build the unit array and set num_units */
    SM_build_units (sm_mdes);

    /* Build the choice array and set num_choices */
    SM_build_choices (sm_mdes);

    /* Build the table array and set num_tables */
    SM_build_tables (sm_mdes);

    /* Return the newly created sm_mdes data structure */
    return (sm_mdes);
}

---