git.sesse.net Git - freerainbowtables/blob - BOINC software/BOINC server apps/distrrtgen_validator/validate_util.cpp

   1 // This file is part of BOINC.
   2 // http://boinc.berkeley.edu
   3 // Copyright (C) 2008 University of California
   4 //
   5 // BOINC is free software; you can redistribute it and/or modify it
   6 // under the terms of the GNU Lesser General Public License
   7 // as published by the Free Software Foundation,
   8 // either version 3 of the License, or (at your option) any later version.
   9 //
  10 // BOINC is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  13 // See the GNU Lesser General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU Lesser General Public License
  16 // along with BOINC.  If not, see <http://www.gnu.org/licenses/>.
  17
  18 // Code to facilitate writing validators.
  19 // Can be used as the basis for a validator that accepts everything
  20 // (see sample_trivial_validator.C),
  21 // or that requires strict equality (see sample_bitwise_validator.C)
  22 // or that uses fuzzy comparison.
  23
  24 #include <cstring>
  25 #include "config.h"
  26
  27 #include "error_numbers.h"
  28 #include "parse.h"
  29 #include "util.h"
  30 #include "filesys.h"
  31
  32 #include "sched_util.h"
  33 #include "sched_config.h"
  34 #include "sched_msgs.h"
  35 #include "validator.h"
  36 #include "validate_util.h"
  37
  38 using std::vector;
  39 using std::string;
  40
  41
  42 int FILE_INFO::parse(XML_PARSER& xp) {
  43     char tag[256];
  44     bool is_tag, found=false;
  45     optional = false;
  46     no_validate = false;
  47     while (!xp.get(tag, sizeof(tag), is_tag)) {
  48         if (!is_tag) continue;
  49         if (!strcmp(tag, "/file_ref")) {
  50             return found?0:ERR_XML_PARSE;
  51         }
  52         if (xp.parse_string(tag, "file_name", name)) {
  53             found = true;
  54             continue;
  55         }
  56         if (xp.parse_bool(tag, "optional", optional)) continue;
  57         if (xp.parse_bool(tag, "no_validate", no_validate)) continue;
  58     }
  59     return ERR_XML_PARSE;
  60 }
  61
  62 int get_output_file_info(RESULT& result, FILE_INFO& fi) {
  63     char tag[256], path[1024];
  64     bool is_tag;
  65     string name;
  66     MIOFILE mf;
  67     mf.init_buf_read(result.xml_doc_in);
  68     XML_PARSER xp(&mf);
  69     while (!xp.get(tag, sizeof(tag), is_tag)) {
  70         if (!is_tag) continue;
  71         if (!strcmp(tag, "file_ref")) {
  72             int retval = fi.parse(xp);
  73             if (retval) return retval;
  74             dir_hier_path(
  75                 fi.name.c_str(), config.upload_dir, config.uldl_dir_fanout, path
  76             );
  77             fi.path = path;
  78             return 0;
  79         }
  80     }
  81     return ERR_XML_PARSE;
  82 }
  83
  84 int get_output_file_infos(RESULT& result, vector<FILE_INFO>& fis) {
  85     char tag[256], path[1024];
  86     bool is_tag;
  87     MIOFILE mf;
  88     string name;
  89     mf.init_buf_read(result.xml_doc_in);
  90     XML_PARSER xp(&mf);
  91     fis.clear();
  92     while (!xp.get(tag, sizeof(tag), is_tag)) {
  93         if (!is_tag) continue;
  94         if (!strcmp(tag, "file_ref")) {
  95             FILE_INFO fi;
  96             int retval =  fi.parse(xp);
  97             if (retval) return retval;
  98             dir_hier_path(
  99                 fi.name.c_str(), config.upload_dir, config.uldl_dir_fanout, path
 100             );
 101             fi.path = path;
 102             fis.push_back(fi);
 103         }
 104     }
 105     return 0;
 106 }
 107
 108 int get_output_file_path(RESULT& result, string& path) {
 109     FILE_INFO fi;
 110     int retval = get_output_file_info(result, fi);
 111     if (retval) return retval;
 112     path = fi.path;
 113     return 0;
 114 }
 115
 116 int get_output_file_paths(RESULT& result, vector<string>& paths) {
 117     vector<FILE_INFO> fis;
 118     int retval = get_output_file_infos(result, fis);
 119     if (retval) return retval;
 120     paths.clear();
 121     for (unsigned int i=0; i<fis.size(); i++) {
 122         paths.push_back(fis[i].path);
 123     }
 124     return 0;
 125 }
 126
 127 struct FILE_REF {
 128     char file_name[256];
 129     char open_name[256];
 130     int parse(XML_PARSER& xp) {
 131         char tag[256];
 132         bool is_tag;
 133
 134         strcpy(file_name, "");
 135         strcpy(open_name, "");
 136         while (!xp.get(tag, sizeof(tag), is_tag)) {
 137             if (!is_tag) continue;
 138             if (!strcmp(tag, "/file_ref")) {
 139                 return 0;
 140             }
 141             if (xp.parse_str(tag, "file_name", file_name, sizeof(file_name))) continue;
 142             if (xp.parse_str(tag, "open_name", open_name, sizeof(open_name))) continue;
 143         }
 144         return ERR_XML_PARSE;
 145     }
 146 };
 147
 148 // given a path returned by the above, get the corresponding logical name
 149 //
 150 int get_logical_name(RESULT& result, string& path, string& name) {
 151     char phys_name[1024];
 152     char tag[256];
 153     bool is_tag;
 154     MIOFILE mf;
 155     int retval;
 156
 157     mf.init_buf_read(result.xml_doc_in);
 158     XML_PARSER xp(&mf);
 159
 160     strcpy(phys_name, path.c_str());
 161     char* p = strrchr(phys_name, '/');
 162     if (!p) return ERR_NOT_FOUND;
 163     strcpy(phys_name, p+1);
 164
 165     while (!xp.get(tag, sizeof(tag), is_tag)) {
 166         if (!is_tag) continue;
 167         if (!strcmp(tag, "result")) continue;
 168         if (!strcmp(tag, "file_ref")) {
 169             FILE_REF fr;
 170             retval = fr.parse(xp);
 171             if (retval) continue;
 172             if (!strcmp(phys_name, fr.file_name)) {
 173                 name = fr.open_name;
 174                 return 0;
 175             }
 176             continue;
 177         }
 178         xp.skip_unexpected(tag, false, 0);
 179     }
 180     return ERR_XML_PARSE;
 181 }
 182
 183 #define CREDIT_EPSILON .001
 184
 185 // If we have N correct results with nonzero claimed credit,
 186 // compute a canonical credit as follows:
 187 // - if N==0 (all claimed credits are infinitesmal), return CREDIT_EPSILON
 188 // - if N==1, return that credit
 189 // - if N==2, return min
 190 // - if N>2, toss out min and max, return average of rest
 191 //
 192 double median_mean_credit(WORKUNIT& /*wu*/, vector<RESULT>& results) {
 193     int ilow=-1, ihigh=-1;
 194     double credit_low = 0, credit_high = 0;
 195     int nvalid = 0;
 196     unsigned int i;
 197
 198     for (i=0; i<results.size(); i++) {
 199         RESULT& result = results[i];
 200         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 201         if (result.claimed_credit < CREDIT_EPSILON) continue;
 202         if (ilow < 0) {
 203             ilow = ihigh = i;
 204             credit_low = credit_high = result.claimed_credit;
 205         } else {
 206             if (result.claimed_credit < credit_low) {
 207                 ilow = i;
 208                 credit_low = result.claimed_credit;
 209             }
 210             if (result.claimed_credit > credit_high) {
 211                 ihigh = i;
 212                 credit_high = result.claimed_credit;
 213             }
 214         }
 215         nvalid++;
 216     }
 217
 218     switch(nvalid) {
 219     case 0:
 220         return CREDIT_EPSILON;
 221     case 1:
 222     case 2:
 223         return credit_low;
 224     default:
 225         double sum = 0;
 226         for (i=0; i<results.size(); i++) {
 227             if (i == (unsigned int) ilow) continue;
 228             if (i == (unsigned int) ihigh) continue;
 229             RESULT& result = results[i];
 230             if (result.validate_state != VALIDATE_STATE_VALID) continue;
 231
 232             sum += result.claimed_credit;
 233         }
 234         return sum/(nvalid-2);
 235     }
 236 }
 237
 238 int get_credit_from_wu(WORKUNIT& wu, vector<RESULT>&, double& credit) {
 239     double x;
 240     int retval;
 241     DB_WORKUNIT dbwu;
 242
 243     dbwu.id = wu.id;
 244     retval = dbwu.get_field_str("xml_doc", dbwu.xml_doc, sizeof(dbwu.xml_doc));
 245     if (!retval) {
 246         if (parse_double(dbwu.xml_doc, "<credit>", x)) {
 247             credit = x;
 248             return 0;
 249         }
 250     }
 251     return ERR_XML_PARSE;
 252 }
 253
 254 // This function should be called from the validator whenever credit
 255 // is granted to a host.  It's purpose is to track the average credit
 256 // per cpu time for that host.
 257 //
 258 // It updates an exponentially-decaying estimate of credit_per_cpu_sec
 259 // Note that this does NOT decay with time, but instead decays with
 260 // total credits earned.  If a host stops earning credits, then this
 261 // quantity stops decaying.  So credit_per_cpu_sec must NOT be
 262 // periodically decayed using the update_stats utility or similar
 263 // methods.
 264 //
 265 // The intended purpose is for cross-project credit comparisons on
 266 // BOINC statistics pages, for hosts attached to multiple machines.
 267 // One day people will write PhD theses on how to normalize credit
 268 // values to equalize them across projects.  I hope this will be done
 269 // according to "Allen's principle": "Credits granted by a project
 270 // should be normalized so that, averaged across all hosts attached to
 271 // multiple projects, projects grant equal credit per cpu second."
 272 // This principle ensures that (on average) participants will choose
 273 // projects based on merit, not based on credits.  It also ensures
 274 // that (on average) host machines migrate to the projects for which
 275 // they are best suited.
 276 //
 277 // For cross-project comparison the value of credit_per_cpu_sec should
 278 // be exported in the statistics file host_id.gz, which is written by
 279 // the code in db_dump.C.
 280 //
 281 // Algorithm: credits_per_cpu_second should be updated each time that
 282 // a host is granted credit, according to:
 283 //
 284 //     CREDIT_AVERAGE_CONST = 500           [see Note 5]
 285 //     MAX_CREDIT_PER_CPU_SEC = 0.1         [see Note 6]
 286 //
 287 //     e = tanh(granted_credit/CREDIT_AVERAGE_CONST)
 288 //     if (e < 0) then e = 0
 289 //     if (e > 1) then e = 1
 290 //     if (credit_per_cpu_sec <= 0) then e = 1
 291 //     if (cpu_time <= 0) then e = 0        [see Note 4]
 292 //     if (granted_credit <= 0) then e = 0  [see Note 3]
 293 //
 294 //     rate = granted_credit/cpu_time
 295 //     if (rate < 0) rate = 0
 296 //     if (rate > MAX_CREDIT_PER_CPU_SEC) rate = MAX_CREDIT_PER_CPU_SEC
 297 //
 298 //     credit_per_cpu_sec = e * rate + (1 - e) * credit_per_cpu_sec
 299
 300 // Note 0: all quantities above should be treated as real numbers
 301 // Note 1: cpu_time is measured in seconds
 302 // Note 2: When a host is created, the initial value of
 303 //         credit_per_cpu_sec, should be zero.
 304 // Note 3: If a host has done invalid work (granted_credit==0) we have
 305 //         chosen not to include it.  One might argue that the
 306 //         boundary case granted_credit==0 should be treated the same
 307 //         as granted_credit>0.  However the goal here is not to
 308 //         identify cpus whose host machines sometimes produce
 309 //         rubbish.  It is to get a measure of how effectively the cpu
 310 //         runs the application code.
 311 // Note 4: e==0 means 'DO NOT include the first term on the rhs of the
 312 //         equation defining credit_per_cpu_sec' which is equivalent
 313 //         to 'DO NOT update credit_per_cpu_sec'.
 314 // Note 5: CREDIT_AVERAGE_CONST determines the exponential decay
 315 //         credit used in averaging credit_per_cpu_sec.  It may be
 316 //         changed at any time, even if the project database has
 317 //         already been populated with non-zero values of
 318 //         credit_per_cpu_sec.
 319 // Note 6: Typical VERY FAST cpus have credit_per_cpu_sec of around
 320 //         0.02.  This is a safety mechanism designed to prevent
 321 //         trouble if a client or host has reported absurd values (due
 322 //         to a bug in client or server software or by cheating).  In
 323 //         five years when cpus are five time faster, please increase
 324 //         the value of R.  You may also want to increase the value of
 325 //         CREDIT_AVERAGE_CONST.
 326 //
 327 //         Nonzero return value: host exceeded the max allowed
 328 //         credit/cpu_sec.
 329 //
 330 int update_credit_per_cpu_sec(
 331     double  granted_credit,     // credit granted for this work
 332     double  cpu_time,           // cpu time (seconds) used for this work
 333     double& credit_per_cpu_sec  // (average) credit per cpu second
 334 ) {
 335     int retval = 0;
 336
 337     // Either of these values may be freely changed in the future.
 338     // When CPUs get much faster one must increase the 'sanity-check'
 339     // value of max_credit_per_cpu_sec.  At that time it would also
 340     // make sense to proportionally increase the credit_average_const.
 341     //
 342     const double credit_average_const = 500;
 343     const double max_credit_per_cpu_sec = 0.07;
 344
 345     double e = tanh(granted_credit/credit_average_const);
 346     if (e <= 0.0 || cpu_time == 0.0 || granted_credit == 0.0) return retval;
 347     if (e > 1.0 || credit_per_cpu_sec == 0.0) e = 1.0;
 348
 349     double rate =  granted_credit/cpu_time;
 350     if (rate < 0.0) rate = 0.0;
 351     if (rate > max_credit_per_cpu_sec) {
 352         rate = max_credit_per_cpu_sec;
 353         retval = 1;
 354     }
 355
 356     credit_per_cpu_sec = e * rate + (1.0 - e) * credit_per_cpu_sec;
 357
 358     return retval;
 359 }
 360
 361 double stddev_credit(WORKUNIT& wu, std::vector<RESULT>& results) {
 362     double credit_low_bound = 0, credit_high_bound = 0;
 363     double penalize_credit_high_bound = 0;
 364     double credit_avg = 0;
 365     double credit = 0;
 366     double old = 0;
 367     double std_dev = 0;
 368     int nvalid = 0;
 369     unsigned int i;
 370
 371     //calculate average
 372     for (i=0; i<results.size(); i++) {
 373         RESULT& result = results[i];
 374         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 375         credit = credit + result.claimed_credit;
 376         nvalid++;
 377     }
 378
 379     if (nvalid == 0) {
 380         return CREDIT_EPSILON;
 381     }
 382
 383     credit_avg = credit/nvalid;
 384
 385     nvalid = 0;
 386     //calculate stddev difference
 387     for (i=0; i<results.size(); i++) {
 388         RESULT& result = results[i];
 389         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 390         std_dev = pow(credit_avg - result.claimed_credit,2) + std_dev;
 391         nvalid++;
 392     }
 393
 394     std_dev = std_dev/ (double) nvalid;
 395     std_dev = sqrt(std_dev);
 396
 397     credit_low_bound = credit_avg-std_dev;
 398     if (credit_low_bound > credit_avg*.85) {
 399         credit_low_bound = credit_avg*.85;
 400     }
 401     credit_low_bound = credit_low_bound - 2.5;
 402     if (credit_low_bound < 1) credit_low_bound = 1;
 403
 404     credit_high_bound = credit_avg+std_dev;
 405     if (credit_high_bound < credit_avg*1.15) {
 406         credit_high_bound = credit_avg*1.15;
 407     }
 408     credit_high_bound = credit_high_bound + 5;
 409
 410
 411     nvalid=0;
 412     credit = 0;
 413     for (i=0; i<results.size(); i++) {
 414         RESULT& result = results[i];
 415         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 416         if (result.claimed_credit < credit_high_bound && result.claimed_credit > credit_low_bound) {
 417             credit = credit + result.claimed_credit;
 418             nvalid++;
 419         } else {
 420             log_messages.printf(MSG_NORMAL,
 421                 "[RESULT#%d %s] CREDIT_CALC_SD Discarding invalid credit %.1lf, avg %.1lf, low %.1lf, high %.1lf \n",
 422                 result.id, result.name, result.claimed_credit,
 423                 credit_avg, credit_low_bound, credit_high_bound
 424             );
 425         }
 426     }
 427
 428     double grant_credit;
 429     switch(nvalid) {
 430     case 0:
 431         grant_credit = median_mean_credit(wu, results);
 432         old = grant_credit;
 433         break;
 434     default:
 435         grant_credit = credit/nvalid;
 436         old = median_mean_credit(wu, results);
 437     }
 438
 439     // Log what happened
 440     if (old > grant_credit) {
 441         log_messages.printf(MSG_DEBUG,
 442             "CREDIT_CALC_VAL New Method grant: %.1lf  Old Method grant: %.1lf  Less awarded\n",
 443             grant_credit, old
 444         );
 445     } else if (old == grant_credit) {
 446         log_messages.printf(MSG_DEBUG,
 447             "CREDIT_CALC_VAL New Method grant: %.1lf  Old Method grant: %.1lf  Same awarded\n",
 448             grant_credit, old
 449         );
 450     } else {
 451         log_messages.printf(MSG_DEBUG,
 452             "CREDIT_CALC_VAL New Method grant: %.1lf  Old Method grant: %.1lf  More awarded\n",
 453             grant_credit, old
 454         );
 455     }
 456
 457     // penalize hosts that are claiming too much
 458     penalize_credit_high_bound = grant_credit+1.5*std_dev;
 459     if (penalize_credit_high_bound < grant_credit*1.65) {
 460         penalize_credit_high_bound = grant_credit*1.65;
 461     }
 462     penalize_credit_high_bound = penalize_credit_high_bound + 20;
 463
 464     for (i=0; i<results.size(); i++) {
 465         RESULT& result = results[i];
 466         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 467         if (result.claimed_credit > penalize_credit_high_bound) {
 468             result.granted_credit = grant_credit * 0.5;
 469             log_messages.printf(MSG_NORMAL,
 470                 "[RESULT#%d %s] CREDIT_CALC_PENALTY Penalizing host for too high credit %.1lf, grant %.1lf, penalize %.1lf, stddev %.1lf, avg %.1lf, low %.1lf, high %.1lf \n",
 471                 result.id, result.name, result.claimed_credit, grant_credit,
 472                 penalize_credit_high_bound, std_dev, credit_avg,
 473                 credit_low_bound, credit_high_bound
 474             );
 475         }
 476     }
 477
 478     return grant_credit;
 479 }
 480
 481 double two_credit(WORKUNIT& wu, std::vector<RESULT>& results) {
 482     unsigned int i;
 483     double credit = 0;
 484     double credit_avg = 0;
 485     double last_credit = 0;
 486     int nvalid = 0;
 487     double grant_credit;
 488
 489     //calculate average
 490     for (i=0; i<results.size(); i++) {
 491         RESULT& result = results[i];
 492         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 493         credit = credit + result.claimed_credit;
 494         last_credit = result.claimed_credit;
 495         nvalid++;
 496     }
 497
 498     if (nvalid == 0) {
 499         return CREDIT_EPSILON;
 500     }
 501
 502     credit_avg = credit/nvalid;
 503
 504     // If more then 2 valid results, compute via stddev method
 505     if (nvalid > 2) return stddev_credit(wu, results);
 506     log_messages.printf(MSG_DEBUG,
 507         "[WORKUNIT#%d %s] Only 2 results \n",wu.id, wu.name
 508     );
 509
 510     // If only 2, then check to see if range is reasonable
 511     if (fabs(last_credit - credit_avg) < 0.15*credit_avg) return credit_avg;
 512     log_messages.printf(MSG_DEBUG,
 513         "[WORKUNIT#%d %s] Average is more than 15 percent from each value \n",
 514         wu.id, wu.name
 515     );
 516
 517     // log data on large variance in runtime
 518     float cpu_time = 0.0;
 519     for (i=0; i<results.size(); i++) {
 520         RESULT& result = results[i];
 521         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 522         if (result.cpu_time < 30) continue;
 523         if (cpu_time == 0) {
 524             cpu_time = result.cpu_time*1.0;
 525         } else {
 526             if (cpu_time/result.cpu_time > 2 || cpu_time/result.cpu_time < 0.5) {
 527                 log_messages.printf(MSG_DEBUG,
 528                     "[WORKUNIT#%d %s] Large difference in runtime \n",
 529                     wu.id, wu.name
 530                 );
 531             }
 532         }
 533     }
 534
 535
 536     //find result with smallest deviation from historical credit and award that value
 537     DB_HOST host;
 538     double deviation = -1;
 539     grant_credit = credit_avg; // default award in case nobody matches the cases
 540     for (i=0; i<results.size(); i++) {
 541         RESULT& result = results[i];
 542         if (result.validate_state != VALIDATE_STATE_VALID) continue;
 543         host.lookup_id(result.hostid);
 544         log_messages.printf(MSG_DEBUG,
 545             "[RESULT#%d %s] Claimed Credit = %.2lf  Historical Credit = %.2lf \n",
 546             result.id, result.name, result.claimed_credit,
 547             result.cpu_time*host.credit_per_cpu_sec
 548         );
 549         if ((deviation < 0 || deviation > fabs(result.claimed_credit - result.cpu_time*host.credit_per_cpu_sec)) && result.cpu_time > 30) {
 550             deviation = fabs(result.claimed_credit - result.cpu_time*host.credit_per_cpu_sec);
 551             log_messages.printf(MSG_NORMAL,
 552                 "[RESULT#%d %s] Credit deviation = %.2lf \n",
 553                 result.id, result.name, deviation
 554             );
 555             grant_credit = result.claimed_credit;
 556         }
 557     }
 558     log_messages.printf(MSG_DEBUG,
 559         "[WORKUNIT#%d %s] Credit granted = %.2lf \n",
 560         wu.id, wu.name, grant_credit
 561     );
 562     return grant_credit;
 563 }
 564
 565 const char *BOINC_RCSID_07049e8a0e = "$Id: validate_util.cpp 16069 2008-09-26 18:20:24Z davea $";