git.ozlabs.org Git - ccan/blob - ccan/lbalance/lbalance.c

   1 /* Licensed under GPLv3+ - see LICENSE file for details */
   2 #include <ccan/lbalance/lbalance.h>
   3 #include <ccan/tlist/tlist.h>
   4 #include <sys/time.h>
   5 #include <sys/resource.h>
   6 #include <unistd.h>
   7 #include <errno.h>
   8 #include <assert.h>
   9 #include <stdlib.h>
  10
  11 /* Define tlist_lbalance_task */
  12 TLIST_TYPE(lbalance_task, struct lbalance_task);
  13
  14 struct stats {
  15         /* How many stats of for this value do we have? */
  16         unsigned int num_stats;
  17         /* What was our total work rate? */
  18         float work_rate;
  19 };
  20
  21 struct lbalance {
  22         struct tlist_lbalance_task tasks;
  23         unsigned int num_tasks;
  24
  25         /* We figured out how many we want to run. */
  26         unsigned int target;
  27         /* We need to recalc once a report comes in via lbalance_task_free. */
  28         bool target_uptodate;
  29
  30         /* Integral of how many tasks were running so far */
  31         struct timeval prev_tasks_time;
  32         float tasks_sum;
  33
  34         /* For differential rusage. */
  35         struct rusage prev_usage;
  36
  37         /* How many stats we have collected (we invalidate old ones). */
  38         unsigned int total_stats;
  39
  40         /* Array of stats, indexed by number of tasks we were running. */
  41         unsigned int max_stats;
  42         struct stats *stats;
  43 };
  44
  45 struct lbalance_task {
  46         struct lbalance *lb;
  47         struct list_node list;
  48
  49         /* The time this task started */
  50         struct timeval start;
  51         float tasks_sum_start;
  52 };
  53
  54 struct lbalance *lbalance_new(void)
  55 {
  56         struct lbalance *lb = malloc(sizeof *lb);
  57         if (!lb)
  58                 return NULL;
  59
  60         tlist_init(&lb->tasks);
  61         lb->num_tasks = 0;
  62         gettimeofday(&lb->prev_tasks_time, NULL);
  63         lb->tasks_sum = 0.0;
  64
  65         getrusage(RUSAGE_CHILDREN, &lb->prev_usage);
  66
  67         lb->max_stats = 1;
  68         lb->stats = malloc(sizeof(lb->stats[0]) * lb->max_stats);
  69         if (!lb->stats) {
  70                 free(lb);
  71                 return NULL;
  72         }
  73         lb->stats[0].num_stats = 0;
  74         lb->stats[0].work_rate = 0.0;
  75         lb->total_stats = 0;
  76
  77         /* Start with # CPUS as a guess. */
  78         lb->target = -1L;
  79 #ifdef _SC_NPROCESSORS_ONLN
  80         lb->target = sysconf(_SC_NPROCESSORS_ONLN);
  81 #elif defined(_SC_NPROCESSORS_CONF)
  82         if (lb->target == (unsigned int)-1L)
  83                 lb->target = sysconf(_SC_NPROCESSORS_CONF);
  84 #endif
  85         /* Otherwise, two is a good number. */
  86         if (lb->target == (unsigned int)-1L || lb->target < 2)
  87                 lb->target = 2;
  88         lb->target_uptodate = true;
  89
  90         return lb;
  91 }
  92
  93 /* Return time differences in usec */
  94 static float timeval_sub(struct timeval recent, struct timeval old)
  95 {
  96         float diff;
  97
  98         if (old.tv_usec > recent.tv_usec) {
  99                 diff = 1000000 + recent.tv_usec - old.tv_usec;
 100                 recent.tv_sec--;
 101         } else
 102                 diff = recent.tv_usec - old.tv_usec;
 103
 104         diff += (float)(recent.tv_sec - old.tv_sec) * 1000000;
 105         return diff;
 106 }
 107
 108 /* There were num_tasks running between prev_tasks_time and now. */
 109 static void update_tasks_sum(struct lbalance *lb,
 110                              const struct timeval *now)
 111 {
 112         lb->tasks_sum += timeval_sub(*now, lb->prev_tasks_time)
 113                 * lb->num_tasks;
 114         lb->prev_tasks_time = *now;
 115 }
 116
 117 struct lbalance_task *lbalance_task_new(struct lbalance *lb)
 118 {
 119         struct lbalance_task *task = malloc(sizeof *task);
 120         if (!task)
 121                 return NULL;
 122
 123         if (lb->num_tasks + 1 == lb->max_stats) {
 124                 struct stats *s = realloc(lb->stats,
 125                                           sizeof(*s) * (lb->max_stats + 1));
 126                 if (!s) {
 127                         free(task);
 128                         return NULL;
 129                 }
 130                 lb->stats = s;
 131                 lb->stats[lb->max_stats].num_stats = 0;
 132                 lb->stats[lb->max_stats].work_rate = 0.0;
 133                 lb->max_stats++;
 134         }
 135
 136         task->lb = lb;
 137         gettimeofday(&task->start, NULL);
 138
 139         /* Record that we ran num_tasks up until now. */
 140         update_tasks_sum(lb, &task->start);
 141
 142         task->tasks_sum_start = lb->tasks_sum;
 143         tlist_add_tail(&lb->tasks, task, list);
 144         lb->num_tasks++;
 145
 146         return task;
 147 }
 148
 149 /* We slowly erase old stats, once we have enough. */
 150 static void degrade_stats(struct lbalance *lb)
 151 {
 152         unsigned int i;
 153
 154         if (lb->total_stats < lb->max_stats * 16)
 155                 return;
 156
 157 #if 0
 158         fprintf(stderr, ".");
 159 #endif
 160         for (i = 0; i < lb->max_stats; i++) {
 161                 struct stats *s = &lb->stats[i];
 162                 unsigned int stats_lost = (s->num_stats + 1) / 2;
 163                 s->work_rate *= (float)(s->num_stats - stats_lost)
 164                         / s->num_stats;
 165                 s->num_stats -= stats_lost;
 166                 lb->total_stats -= stats_lost;
 167                 if (s->num_stats == 0)
 168                         s->work_rate = 0.0;
 169         }
 170 }
 171
 172 static void add_to_stats(struct lbalance *lb,
 173                          unsigned int num_tasks,
 174                          float work_rate)
 175 {
 176 #if 0
 177         fprintf(stderr, "With %.2f running, work rate was %.5f\n",
 178                 num_tasks, work_rate);
 179 #endif
 180         assert(num_tasks >= 1);
 181         assert(num_tasks < lb->max_stats);
 182
 183         lb->stats[num_tasks].num_stats++;
 184         lb->stats[num_tasks].work_rate += work_rate;
 185         lb->total_stats++;
 186         lb->target_uptodate = false;
 187 }
 188
 189 void lbalance_task_free(struct lbalance_task *task,
 190                         const struct rusage *usage)
 191 {
 192         float work_done, duration;
 193         unsigned int num_tasks;
 194         struct timeval now;
 195         struct rusage ru;
 196
 197         gettimeofday(&now, NULL);
 198         duration = timeval_sub(now, task->start);
 199
 200         getrusage(RUSAGE_CHILDREN, &ru);
 201         if (usage) {
 202                 work_done = usage->ru_utime.tv_usec + usage->ru_stime.tv_usec
 203                         + (usage->ru_utime.tv_sec + usage->ru_stime.tv_sec)
 204                         * 1000000;
 205         } else {
 206                 /* Take difference in rusage as rusage of that task. */
 207                 work_done = timeval_sub(ru.ru_utime,
 208                                         task->lb->prev_usage.ru_utime)
 209                         + timeval_sub(ru.ru_stime,
 210                                       task->lb->prev_usage.ru_utime);
 211         }
 212         /* Update previous usage. */
 213         task->lb->prev_usage = ru;
 214
 215         /* Record that we ran num_tasks up until now. */
 216         update_tasks_sum(task->lb, &now);
 217
 218         /* So, on average, how many tasks were running during this time? */
 219         num_tasks = (task->lb->tasks_sum - task->tasks_sum_start)
 220                 / duration + 0.5;
 221
 222         /* Record the work rate for that many tasks. */
 223         add_to_stats(task->lb, num_tasks, work_done / duration);
 224
 225         /* We throw away old stats. */
 226         degrade_stats(task->lb);
 227
 228         /* We need to recalculate the target. */
 229         task->lb->target_uptodate = false;
 230
 231         /* Remove this task. */
 232         tlist_del_from(&task->lb->tasks, task, list);
 233         task->lb->num_tasks--;
 234         free(task);
 235 }
 236
 237 /* We look for the point where the work rate starts to drop.  Say you have
 238  * 4 cpus, we'd expect the work rate for 5 processes to drop 20%.
 239  *
 240  * If we're within 1/4 of that ideal ratio, we assume it's still
 241  * optimal.  Any drop of more than 1/2 is interpreted as the point we
 242  * are overloaded. */
 243 static unsigned int best_target(const struct lbalance *lb)
 244 {
 245         unsigned int i, best = 0, found_drop = 0;
 246         float best_f_max = -1.0, cliff = -1.0;
 247
 248 #if 0
 249         for (i = 1; i < lb->max_stats; i++) {
 250                 printf("%u: %f (%u)\n", i,
 251                        lb->stats[i].work_rate / lb->stats[i].num_stats,
 252                        lb->stats[i].num_stats);
 253         }
 254 #endif
 255
 256         for (i = 1; i < lb->max_stats; i++) {
 257                 float f;
 258
 259                 if (!lb->stats[i].num_stats)
 260                         f = 0;
 261                 else
 262                         f = lb->stats[i].work_rate / lb->stats[i].num_stats;
 263
 264                 if (f > best_f_max) {
 265 #if 0
 266                         printf("Best is %i\n", i);
 267 #endif
 268                         best_f_max = f - (f / (i + 1)) / 4;
 269                         cliff = f - (f / (i + 1)) / 2;
 270                         best = i;
 271                         found_drop = 0;
 272                 } else if (!found_drop && f < cliff) {
 273 #if 0
 274                         printf("Found drop at %i\n", i);
 275 #endif
 276                         found_drop = i;
 277                 }
 278         }
 279
 280         if (found_drop) {
 281                 return found_drop - 1;
 282         }
 283         return i - 1;
 284 }
 285
 286 static unsigned int calculate_target(struct lbalance *lb)
 287 {
 288         unsigned int target;
 289
 290         target = best_target(lb);
 291
 292         /* Jitter if the adjacent ones are unknown. */
 293         if (target >= lb->max_stats || lb->stats[target].num_stats == 0)
 294                 return target;
 295
 296         if (target + 1 == lb->max_stats || lb->stats[target+1].num_stats == 0)
 297                 return target + 1;
 298
 299         if (target > 1 && lb->stats[target-1].num_stats == 0)
 300                 return target - 1;
 301
 302         return target;
 303 }
 304
 305 unsigned lbalance_target(struct lbalance *lb)
 306 {
 307         if (!lb->target_uptodate) {
 308                 lb->target = calculate_target(lb);
 309                 lb->target_uptodate = true;
 310         }
 311         return lb->target;
 312 }
 313
 314 void lbalance_free(struct lbalance *lb)
 315 {
 316         struct lbalance_task *task;
 317
 318         while ((task = tlist_top(&lb->tasks, struct lbalance_task, list))) {
 319                 assert(task->lb == lb);
 320                 tlist_del_from(&lb->tasks, task, list);
 321                 lb->num_tasks--;
 322                 free(task);
 323         }
 324         assert(lb->num_tasks == 0);
 325         free(lb->stats);
 326         free(lb);
 327 }