1 /* Licensed under GPLv3+ - see LICENSE file for details */
2 #include <ccan/lbalance/lbalance.h>
3 #include <ccan/tlist2/tlist2.h>
5 #include <sys/resource.h>
12 /* How many stats of for this value do we have? */
13 unsigned int num_stats;
14 /* What was our total work rate? */
20 struct lbalance_task {
22 struct list_node list;
24 /* The time this task started */
26 float tasks_sum_start;
30 TLIST2(struct lbalance_task, list) tasks;
31 unsigned int num_tasks;
33 /* We figured out how many we want to run. */
35 /* We need to recalc once a report comes in via lbalance_task_free. */
38 /* Integral of how many tasks were running so far */
39 struct timeval prev_tasks_time;
42 /* For differential rusage. */
43 struct rusage prev_usage;
45 /* How many stats we have collected (we invalidate old ones). */
46 unsigned int total_stats;
48 /* Array of stats, indexed by number of tasks we were running. */
49 unsigned int max_stats;
53 struct lbalance *lbalance_new(void)
55 struct lbalance *lb = malloc(sizeof *lb);
59 tlist2_init(&lb->tasks);
61 gettimeofday(&lb->prev_tasks_time, NULL);
64 getrusage(RUSAGE_CHILDREN, &lb->prev_usage);
67 lb->stats = malloc(sizeof(lb->stats[0]) * lb->max_stats);
72 lb->stats[0].num_stats = 0;
73 lb->stats[0].work_rate = 0.0;
76 /* Start with # CPUS as a guess. */
78 #ifdef _SC_NPROCESSORS_ONLN
79 lb->target = sysconf(_SC_NPROCESSORS_ONLN);
80 #elif defined(_SC_NPROCESSORS_CONF)
81 if (lb->target == (unsigned int)-1L)
82 lb->target = sysconf(_SC_NPROCESSORS_CONF);
84 /* Otherwise, two is a good number. */
85 if (lb->target == (unsigned int)-1L || lb->target < 2)
87 lb->target_uptodate = true;
92 /* Return time differences in usec */
93 static float timeval_sub(struct timeval recent, struct timeval old)
97 if (old.tv_usec > recent.tv_usec) {
98 diff = 1000000 + recent.tv_usec - old.tv_usec;
101 diff = recent.tv_usec - old.tv_usec;
103 diff += (float)(recent.tv_sec - old.tv_sec) * 1000000;
107 /* There were num_tasks running between prev_tasks_time and now. */
108 static void update_tasks_sum(struct lbalance *lb,
109 const struct timeval *now)
111 lb->tasks_sum += timeval_sub(*now, lb->prev_tasks_time)
113 lb->prev_tasks_time = *now;
116 struct lbalance_task *lbalance_task_new(struct lbalance *lb)
118 struct lbalance_task *task = malloc(sizeof *task);
122 if (lb->num_tasks + 1 == lb->max_stats) {
123 struct stats *s = realloc(lb->stats,
124 sizeof(*s) * (lb->max_stats + 1));
130 lb->stats[lb->max_stats].num_stats = 0;
131 lb->stats[lb->max_stats].work_rate = 0.0;
136 gettimeofday(&task->start, NULL);
138 /* Record that we ran num_tasks up until now. */
139 update_tasks_sum(lb, &task->start);
141 task->tasks_sum_start = lb->tasks_sum;
142 tlist2_add_tail(&lb->tasks, task);
148 /* We slowly erase old stats, once we have enough. */
149 static void degrade_stats(struct lbalance *lb)
153 if (lb->total_stats < lb->max_stats * 16)
157 fprintf(stderr, ".");
159 for (i = 0; i < lb->max_stats; i++) {
160 struct stats *s = &lb->stats[i];
161 unsigned int stats_lost = (s->num_stats + 1) / 2;
162 s->work_rate *= (float)(s->num_stats - stats_lost)
164 s->num_stats -= stats_lost;
165 lb->total_stats -= stats_lost;
166 if (s->num_stats == 0)
171 static void add_to_stats(struct lbalance *lb,
172 unsigned int num_tasks,
176 fprintf(stderr, "With %.2f running, work rate was %.5f\n",
177 num_tasks, work_rate);
179 assert(num_tasks >= 1);
180 assert(num_tasks < lb->max_stats);
182 lb->stats[num_tasks].num_stats++;
183 lb->stats[num_tasks].work_rate += work_rate;
185 lb->target_uptodate = false;
188 void lbalance_task_free(struct lbalance_task *task,
189 const struct rusage *usage)
191 float work_done, duration;
192 unsigned int num_tasks;
196 gettimeofday(&now, NULL);
197 duration = timeval_sub(now, task->start);
199 getrusage(RUSAGE_CHILDREN, &ru);
201 work_done = usage->ru_utime.tv_usec + usage->ru_stime.tv_usec
202 + (usage->ru_utime.tv_sec + usage->ru_stime.tv_sec)
205 /* Take difference in rusage as rusage of that task. */
206 work_done = timeval_sub(ru.ru_utime,
207 task->lb->prev_usage.ru_utime)
208 + timeval_sub(ru.ru_stime,
209 task->lb->prev_usage.ru_utime);
211 /* Update previous usage. */
212 task->lb->prev_usage = ru;
214 /* Record that we ran num_tasks up until now. */
215 update_tasks_sum(task->lb, &now);
217 /* So, on average, how many tasks were running during this time? */
218 num_tasks = (task->lb->tasks_sum - task->tasks_sum_start)
221 /* Record the work rate for that many tasks. */
222 add_to_stats(task->lb, num_tasks, work_done / duration);
224 /* We throw away old stats. */
225 degrade_stats(task->lb);
227 /* We need to recalculate the target. */
228 task->lb->target_uptodate = false;
230 /* Remove this task. */
231 tlist2_del_from(&task->lb->tasks, task);
232 task->lb->num_tasks--;
236 /* We look for the point where the work rate starts to drop. Say you have
237 * 4 cpus, we'd expect the work rate for 5 processes to drop 20%.
239 * If we're within 1/4 of that ideal ratio, we assume it's still
240 * optimal. Any drop of more than 1/2 is interpreted as the point we
242 static unsigned int best_target(const struct lbalance *lb)
244 unsigned int i, found_drop = 0;
245 float best_f_max = -1.0, cliff = -1.0;
248 for (i = 1; i < lb->max_stats; i++) {
249 printf("%u: %f (%u)\n", i,
250 lb->stats[i].work_rate / lb->stats[i].num_stats,
251 lb->stats[i].num_stats);
255 for (i = 1; i < lb->max_stats; i++) {
258 if (!lb->stats[i].num_stats)
261 f = lb->stats[i].work_rate / lb->stats[i].num_stats;
263 if (f > best_f_max) {
265 printf("Best is %i\n", i);
267 best_f_max = f - (f / (i + 1)) / 4;
268 cliff = f - (f / (i + 1)) / 2;
270 } else if (!found_drop && f < cliff) {
272 printf("Found drop at %i\n", i);
279 return found_drop - 1;
284 static unsigned int calculate_target(struct lbalance *lb)
288 target = best_target(lb);
290 /* Jitter if the adjacent ones are unknown. */
291 if (target >= lb->max_stats || lb->stats[target].num_stats == 0)
294 if (target + 1 == lb->max_stats || lb->stats[target+1].num_stats == 0)
297 if (target > 1 && lb->stats[target-1].num_stats == 0)
303 unsigned lbalance_target(struct lbalance *lb)
305 if (!lb->target_uptodate) {
306 lb->target = calculate_target(lb);
307 lb->target_uptodate = true;
312 void lbalance_free(struct lbalance *lb)
314 struct lbalance_task *task;
316 while ((task = tlist2_top(&lb->tasks))) {
317 assert(task->lb == lb);
318 tlist2_del_from(&lb->tasks, task);
322 assert(lb->num_tasks == 0);