/*
*         OpenPBS (Portable Batch System) v2.3 Software License
*
* Copyright (c) 1999-2000 Veridian Information Solutions, Inc.
* All rights reserved.
*
* ---------------------------------------------------------------------------
* For a license to use or redistribute the OpenPBS software under conditions
* other than those described below, or to purchase support for this software,
* please contact Veridian Systems, PBS Products Department ("Licensor") at:
*
*    www.OpenPBS.org  +1 650 967-4675                  sales@OpenPBS.org
*                        877 902-4PBS (US toll-free)
* ---------------------------------------------------------------------------
*
* This license covers use of the OpenPBS v2.3 software (the "Software") at
* your site or location, and, for certain users, redistribution of the
* Software to other sites and locations.  Use and redistribution of
* OpenPBS v2.3 in source and binary forms, with or without modification,
* are permitted provided that all of the following conditions are met.
* After December 31, 2001, only conditions 3-6 must be met:
*
* 1. Commercial and/or non-commercial use of the Software is permitted
*    provided a current software registration is on file at www.OpenPBS.org.
*    If use of this software contributes to a publication, product, or
*    service, proper attribution must be given; see www.OpenPBS.org/credit.html
*
* 2. Redistribution in any form is only permitted for non-commercial,
*    non-profit purposes.  There can be no charge for the Software or any
*    software incorporating the Software.  Further, there can be no
*    expectation of revenue generated as a consequence of redistributing
*    the Software.
*
* 3. Any Redistribution of source code must retain the above copyright notice
*    and the acknowledgment contained in paragraph 6, this list of conditions
*    and the disclaimer contained in paragraph 7.
*
* 4. Any Redistribution in binary form must reproduce the above copyright
*    notice and the acknowledgment contained in paragraph 6, this list of
*    conditions and the disclaimer contained in paragraph 7 in the
*    documentation and/or other materials provided with the distribution.
*
* 5. Redistributions in any form must be accompanied by information on how to
*    obtain complete source code for the OpenPBS software and any
*    modifications and/or additions to the OpenPBS software.  The source code
*    must either be included in the distribution or be available for no more
*    than the cost of distribution plus a nominal fee, and all modifications
*    and additions to the Software must be freely redistributable by any party
*    (including Licensor) without restriction.
*
* 6. All advertising materials mentioning features or use of the Software must
*    display the following acknowledgment:
*
*     "This product includes software developed by NASA Ames Research Center,
*     Lawrence Livermore National Laboratory, and Veridian Information
*     Solutions, Inc.
*     Visit www.OpenPBS.org for OpenPBS software support,
*     products, and information."
*
* 7. DISCLAIMER OF WARRANTY
*
* THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT
* ARE EXPRESSLY DISCLAIMED.
*
* IN NO EVENT SHALL VERIDIAN CORPORATION, ITS AFFILIATED COMPANIES, OR THE
* U.S. GOVERNMENT OR ANY OF ITS AGENCIES BE LIABLE FOR ANY DIRECT OR INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
* OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
* EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* This license will be governed by the laws of the Commonwealth of Virginia,
* without reference to its choice of law rules.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "job_info.h"
#include "constant.h"
#include "fairshare.h"
#include "globals.h"
#include "misc.h"
#include "constant.h"
#include "config.h"


/*
 *
 * add_child - add a group_info to the resource group tree
 *
 *   ginfo - ginfo to add to the tree
 *   parent - parent ginfo
 *
 * returns nothing
 *
 */
void add_child(group_info *ginfo, group_info *parent)
  {
  if (parent != NULL)
    {
    ginfo -> sibling = parent -> child;
    parent -> child = ginfo;
    ginfo -> parent = parent;
    ginfo -> resgroup = parent -> cresgroup;
    }
  }

/*
 *
 * add_unknown - add a ginfo to the "unknown" group
 *
 *   ginfo - ginfo to add
 *
 * returns nothing
 *
 */
void add_unknown(group_info *ginfo)
  {
  group_info *unknown;  /* ptr to the "unknown" group */

  unknown = find_group_info("unknown", conf.group_root);
  add_child(ginfo, unknown);
  calc_fair_share_perc(unknown -> child, UNSPECIFIED);
  }

/*
 *
 * find_group_info - recursive function to find a group_info in the
 *     resgroup tree
 *
 *   name - name of the ginfo to find
 *   root - the root of the current sub-tree
 *
 * returns the found group_info or NULL
 *
 */
group_info *find_group_info(const char *name, group_info *root)
  {
  group_info *ginfo;  /* the found group */

  if (root == NULL || !strcmp(name, root -> name))
    return root;

  ginfo = find_group_info(name, root -> sibling);

  if (ginfo == NULL)
    ginfo = find_group_info(name, root -> child);

  return ginfo;
  }

/*
 *
 * find_alloc_ginfo - trys to find a ginfo in the fair share tree.  If it
 *     can not find the ginfo, then allocate a new one and
 *     add it to the "unknown" group
 *
 *   name - name of the ginfo to find
 *
 * returns the found ginfo or the newly allocated ginfo
 *
 */
group_info *find_alloc_ginfo(char *name)
  {
  group_info *ginfo;  /* the found group or allocated group */

  ginfo = find_group_info(name, conf.group_root);

  if (ginfo == NULL)
    {
    if ((ginfo = new_group_info()) == NULL)
      return NULL;

    ginfo-> name = string_dup(name);

    ginfo -> shares = 1;

    add_unknown(ginfo);
    }

  return ginfo;
  }

/*
 *
 * new_group_info - allocate a new group_info struct and initalize it
 *
 * returns a ptr to the new group_info
 *
 */
group_info *new_group_info()
  {
  group_info *new_group_info;  /* the new group */

  if ((new_group_info = (group_info *)malloc(sizeof(group_info))) == NULL)
    {
    perror("Error allocating memory");
    return NULL ;
    }

  new_group_info -> name = NULL;

  new_group_info -> resgroup = UNSPECIFIED;
  new_group_info -> cresgroup = UNSPECIFIED;
  new_group_info -> shares = UNSPECIFIED;
  new_group_info -> percentage = 0.0;
  new_group_info -> usage = 1;
  new_group_info -> temp_usage = 1;
  new_group_info -> parent = NULL;
  new_group_info -> sibling = NULL;
  new_group_info -> child = NULL;

  return new_group_info;
  }

/*
 *
 * parse_group - parse the resource group file
 *
 *   fname - name of the file
 *
 * returns success/failure
 *
 *
 * FORMAT:   name cresgrp  grpname  shares
 *
 *   name    - name of user/grp
 *   cresgrp - resource group of the children of this group (if group)
 *   grpname - resource group of this user/group
 *   shares  - the amount of shares the user/group has in its resgroup
 *
 */
int parse_group(const char *fname)
  {
  group_info *ginfo;  /* ptr to parent group */
  group_info *new_ginfo; /* used to add each new group */
  char buf[256];  /* used to read each line from the file */
  char *nametok;  /* strtok: name of new group */
  char *grouptok;  /* strtok: parent group name */
  char *cgrouptok;  /* strtok: resgrp of the children of newgrp */
  char *sharestok;  /* strtok: the amount of shares for newgrp */
  FILE *fp;   /* file pointer to the resource group file */
  char error = 0;  /* boolean: is there an error ? */
  int shares;   /* number of shares for the new group */
  int cgroup;   /* resource group of the children of the grp */
  char *endp;   /* used for strtol() */
  int linenum = 0;  /* current line number in the file */

  if ((fp = fopen(fname, "r")) == NULL)
    {
    perror("Warning: resource group file error, fair share will not work");
    return 0;
    }

  while (fgets(buf, 256, fp) != NULL)
    {
    if (buf[strlen(buf)-1] == '\n')
      buf[strlen(buf)-1] = '\0';

    linenum++;

    if (!skip_line(buf))
      {
      nametok = strtok(buf, " \t");
      cgrouptok = strtok(NULL, " \t");
      grouptok = strtok(NULL, " \t");
      sharestok= strtok(NULL,  " \t");

      ginfo = find_alloc_ginfo(grouptok);

      if (ginfo != NULL)
        {
        shares = strtol(sharestok, &endp, 10);

        if (*endp == '\0')
          {
          cgroup = strtol(cgrouptok, &endp, 10);

          if (*endp == '\0')
            {
            if ((new_ginfo = new_group_info()) == NULL)
              return 0;

            new_ginfo -> name = string_dup(nametok);

            new_ginfo -> resgroup = ginfo -> cresgroup;

            new_ginfo -> cresgroup = cgroup;

            new_ginfo -> shares = shares;

            add_child(new_ginfo, ginfo);
            }
          else
            error = 1;
          }
        else
          error = 1;
        }
      else
        {
        error = 1;
        fprintf(stderr, "Parent ginfo of %s doesnt exist.\n", nametok);
        }

      if (error)
        fprintf(stderr, "resgroup: error on line %d.\n", linenum);

      error = 0;
      }
    }

  return 1;
  }

/*
 *
 * free_group_tree - free the data used by a the fair share tree
 *
 *   root - root of subtree
 *
 */
void free_group_tree(group_info *root)
  {
  if (root == NULL)
    return;

  free_group_tree(root -> sibling);

  free_group_tree(root -> child);

  free(root);
  }

/*
 *
 * preload_tree -  load the "root" group into the fair share tree
 *   the "root" group is the entire machine.  Also load
 *   the "unknown" group.  This group is for any user that
 *   is not specified in the resource group file.
 *
 * returns success/failure
 *
 */
int
preload_tree(void)
  {
  group_info *unknown;  /* pointer to the "unknown" group */

  if ((conf.group_root = new_group_info()) == NULL)
    return 0;

  if ((unknown = new_group_info()) == NULL)
    return 0;

  if ((conf.group_root -> name = (char *)malloc(5 * sizeof(char))) == NULL)
    {
    perror("Memory allocation error");
    return 0;
    }

  if ((unknown -> name = (char *) malloc(8 * sizeof(char))) == NULL)
    {
    perror("Memory Allocation Error");
    return 0;
    }

  strcpy(conf.group_root -> name, "root");

  conf.group_root -> resgroup = -1;
  conf.group_root -> cresgroup = 0;
  conf.group_root -> percentage = 1.0;

  strcpy(unknown -> name, "unknown");
  unknown -> shares = conf.unknown_shares;
  unknown -> resgroup = 0;
  unknown -> cresgroup = 1;
  unknown -> parent = conf.group_root;
  conf.group_root -> child = unknown;
  return 1;
  }

/*
 *
 * count_shares - count the shares in a resource group
 *         a resource group is a group_info and all of its
 *         siblings
 *
 *  grp - The start of a sibling chain
 *
 * returns the number of shares
 *
 */
int count_shares(group_info *grp)
  {
  int shares = 0;  /* accumulator to count the shares */
  group_info *cur_grp;  /* the current group in a sibling chain */

  cur_grp = grp;

  while (cur_grp != NULL)
    {
    shares += cur_grp -> shares;
    cur_grp = cur_grp -> sibling;
    }

  return shares;
  }

/*
 *
 * calc_fair_share_perc - walk the fair share group tree and calculate
 *          the overall percentage of the machine a user/
 *          group gets if all usage is equal
 *
 *   root - the root of the current subtree
 *   shares - the number of total shares in the group
 *
 * returns success/failure
 *
 */
int calc_fair_share_perc(group_info *root, int shares)
  {
  int cur_shares;  /* total number of shares in the resgrp */

  if (root == NULL)
    return 0;

  if (shares == UNSPECIFIED)
    cur_shares = count_shares(root);
  else
    cur_shares = shares;

  root -> percentage = (float) root -> shares / (float) cur_shares *
                       root -> parent -> percentage;

  calc_fair_share_perc(root -> sibling, cur_shares);

  calc_fair_share_perc(root -> child, UNSPECIFIED);

  return 1;
  }

/*
 *
 * test_perc - a debugging function to check if the fair_share
 *      percentanges calculated add up to 100%
 *
 *   root - root of the current subtree
 *
 * returns total percentage (hopefully 1.0)
 *
 */
float test_perc(group_info *root)
  {
  if (root == NULL)
    return 0;

  return (root -> child == NULL ? root -> percentage : 0) + test_perc(root -> sibling) + test_perc(root -> child);
  }


/*
 *
 * update_usage_on_run - update a users usage information when a
 *         job is run
 *
 *   jinfo - the job which just started running
 *
 * returns nothing
 *
 */
void update_usage_on_run(job_info *jinfo)
  {
  jinfo -> ginfo -> temp_usage += calculate_usage_value(jinfo -> resreq);
  }

/*
 *
 * calculate_usage_value - calcualte a value that represents the usage
 *    information
 *
 *   resreq - a resource_req list that holds the resource info
 *
 * returns the calculated value
 *
 * NOTE: currently it will only return the number of cpu seconds used.
 *       This function can be more complicated
 *
 */
usage_t calculate_usage_value(resource_req *resreq)
  {
  resource_req *tmp;

  if (resreq != NULL)
    {
    tmp = find_resource_req(resreq, "cput");

    if (tmp != NULL)
      return tmp -> amount;
    }

  return 0L;
  }

/*
 *
 * decay_fairshare_tree - decay the usage information kept in the fair
 *          share tree
 *
 *   root - the root of the fairshare tree
 *
 * returns nothing
 *
 */
void decay_fairshare_tree(group_info *root)
  {
  if (root == NULL)
    return;

  decay_fairshare_tree(root -> sibling);

  decay_fairshare_tree(root -> child);

  root -> usage /= 2;

  if (root -> usage == 0)
    root -> usage = 1;
  }

/*
 *
 * extract_fairshare - extract the first job from the user with the
 *       least percentage / usage ratio
 *
 *   jobs - array of jobs to search through
 *
 * return the found job or NULL on error
 *
 */
job_info *extract_fairshare(job_info **jobs)
  {
  job_info *max = NULL;  /* job with the max shares / percentage */
  float max_value;  /* max shares / percentage */
  float cur_value;  /* the current shares / percentage value */
  int i;

  if (jobs != NULL)
    {
    max_value = -1;

    for (i = 0; jobs[i] != NULL; i++)
      {
      cur_value = jobs[i] -> ginfo -> percentage / jobs[i] -> ginfo -> temp_usage;

      if (max_value < cur_value && !jobs[i] -> is_running &&
          !jobs[i] -> can_not_run)
        {
        max = jobs[i];
        max_value = cur_value;
        }
      }
    }

  return max;
  }

/*
 *
 * print_fairshare - print out the fair share tree
 *
 *   root - root of subtree
 *
 * returns nothing
 *
 */
void print_fairshare(group_info *root)
  {
  if (root == NULL)
    return;

  if (root -> child == NULL)
    printf("User: %-10s Grp: %d cgrp: %d Usage %ld Perc: %f\n", root -> name,
           root -> resgroup, root -> cresgroup, root -> usage, root -> percentage);

  print_fairshare(root -> sibling);

  print_fairshare(root -> child);
  }

/*
 *
 * write_usage - write the usage information to the usage file
 *        This fuction uses a recursive helper function
 *
 *
 * returns success/failure
 *
 */
int
write_usage(void)
  {
  FILE *fp;  /* file pointer to usage file */

  if ((fp = fopen(USAGE_FILE, "wb")) == NULL)
    {
    perror("Error opening file " USAGE_FILE);
    return 0;
    }

  rec_write_usage(conf.group_root, fp);

  fclose(fp);
  return 1;
  }

/*
 *
 * rec_write_usage - recursive helper function which will write out all
 *     the group_info structs of the resgroup tree
 *
 *   root - the root of the current subtree
 *   fp   - the file to write the ginfo out to
 *
 * returns nothing
 *
 */
void rec_write_usage(group_info *root, FILE *fp)
  {

  struct group_node_usage grp;  /* used to write out usage info */

  if (root == NULL)
    return;

  if (root -> usage != 1)   /* usage defaults to 1 */
    {
    strcpy(grp.name, root -> name);
    grp.usage = root -> usage;

    if (!fwrite(&grp, sizeof(struct group_node_usage), 1, fp))
      return;
    }

  rec_write_usage(root -> sibling, fp);

  rec_write_usage(root -> child, fp);
  }

/*
 *
 * read_usage - read the usage information and load it into the
 *       resgroup tree.
 *
 * returns success/failure
 *
 */
int
read_usage(void)
  {
  FILE *fp;    /* file pointer to usage file */

  struct group_node_usage grp;  /* struct used to read in usage info */
  group_info *ginfo;   /* ptr to current group usage */


  if ((fp = fopen(USAGE_FILE, "r")) == NULL)
    {
    perror("Can not open file " USAGE_FILE);
    return 0;
    }

  while (fread(&grp, sizeof(struct group_node_usage), 1, fp))
    {
    ginfo = find_alloc_ginfo(grp.name);

    if (ginfo != NULL)
      ginfo -> usage = grp.usage;
    }

  fclose(fp);

  return 1;
  }