1 /* Licensed under GPLv3+ - see LICENSE file for details */
2 #include <ccan/lbalance/lbalance.h>
3 #include <ccan/tlist/tlist.h>
5 #include <sys/resource.h>
11 /* Define tlist_lbalance_task */
12 TLIST_TYPE(lbalance_task, struct lbalance_task);
15 /* How many stats of for this value do we have? */
16 unsigned int num_stats;
17 /* What was our total work rate? */
22 struct tlist_lbalance_task tasks;
23 unsigned int num_tasks;
25 /* We figured out how many we want to run. */
27 /* We need to recalc once a report comes in via lbalance_task_free. */
30 /* Integral of how many tasks were running so far */
31 struct timeval prev_tasks_time;
34 /* For differential rusage. */
35 struct rusage prev_usage;
37 /* How many stats we have collected (we invalidate old ones). */
38 unsigned int total_stats;
40 /* Array of stats, indexed by number of tasks we were running. */
41 unsigned int max_stats;
45 struct lbalance_task {
47 struct list_node list;
49 /* The time this task started */
51 float tasks_sum_start;
54 struct lbalance *lbalance_new(void)
56 struct lbalance *lb = malloc(sizeof *lb);
60 tlist_init(&lb->tasks);
62 gettimeofday(&lb->prev_tasks_time, NULL);
65 getrusage(RUSAGE_CHILDREN, &lb->prev_usage);
68 lb->stats = malloc(sizeof(lb->stats[0]) * lb->max_stats);
73 lb->stats[0].num_stats = 0;
74 lb->stats[0].work_rate = 0.0;
77 /* Start with # CPUS as a guess. */
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);
85 /* Otherwise, two is a good number. */
86 if (lb->target == (unsigned int)-1L || lb->target < 2)
88 lb->target_uptodate = true;
93 /* Return time differences in usec */
94 static float timeval_sub(struct timeval recent, struct timeval old)
98 if (old.tv_usec > recent.tv_usec) {
99 diff = 1000000 + recent.tv_usec - old.tv_usec;
102 diff = recent.tv_usec - old.tv_usec;
104 diff += (float)(recent.tv_sec - old.tv_sec) * 1000000;
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)
112 lb->tasks_sum += timeval_sub(*now, lb->prev_tasks_time)
114 lb->prev_tasks_time = *now;
117 struct lbalance_task *lbalance_task_new(struct lbalance *lb)
119 struct lbalance_task *task = malloc(sizeof *task);
123 if (lb->num_tasks + 1 == lb->max_stats) {
124 struct stats *s = realloc(lb->stats,
125 sizeof(*s) * (lb->max_stats + 1));
131 lb->stats[lb->max_stats].num_stats = 0;
132 lb->stats[lb->max_stats].work_rate = 0.0;
137 gettimeofday(&task->start, NULL);
139 /* Record that we ran num_tasks up until now. */
140 update_tasks_sum(lb, &task->start);
142 task->tasks_sum_start = lb->tasks_sum;
143 tlist_add_tail(&lb->tasks, task, list);
149 /* We slowly erase old stats, once we have enough. */
150 static void degrade_stats(struct lbalance *lb)
154 if (lb->total_stats < lb->max_stats * 16)
158 fprintf(stderr, ".");
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)
165 s->num_stats -= stats_lost;
166 lb->total_stats -= stats_lost;
167 if (s->num_stats == 0)
172 static void add_to_stats(struct lbalance *lb,
173 unsigned int num_tasks,
177 fprintf(stderr, "With %.2f running, work rate was %.5f\n",
178 num_tasks, work_rate);
180 assert(num_tasks >= 1);
181 assert(num_tasks < lb->max_stats);
183 lb->stats[num_tasks].num_stats++;
184 lb->stats[num_tasks].work_rate += work_rate;
186 lb->target_uptodate = false;
189 void lbalance_task_free(struct lbalance_task *task,
190 const struct rusage *usage)
192 float work_done, duration;
193 unsigned int num_tasks;
197 gettimeofday(&now, NULL);
198 duration = timeval_sub(now, task->start);
200 getrusage(RUSAGE_CHILDREN, &ru);
202 work_done = usage->ru_utime.tv_usec + usage->ru_stime.tv_usec
203 + (usage->ru_utime.tv_sec + usage->ru_stime.tv_sec)
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);
212 /* Update previous usage. */
213 task->lb->prev_usage = ru;
215 /* Record that we ran num_tasks up until now. */
216 update_tasks_sum(task->lb, &now);
218 /* So, on average, how many tasks were running during this time? */
219 num_tasks = (task->lb->tasks_sum - task->tasks_sum_start)
222 /* Record the work rate for that many tasks. */
223 add_to_stats(task->lb, num_tasks, work_done / duration);
225 /* We throw away old stats. */
226 degrade_stats(task->lb);
228 /* We need to recalculate the target. */
229 task->lb->target_uptodate = false;
231 /* Remove this task. */
232 tlist_del_from(&task->lb->tasks, task, list);
233 task->lb->num_tasks--;
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%.
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
243 static unsigned int best_target(const struct lbalance *lb)
245 unsigned int i, found_drop = 0;
246 float best_f_max = -1.0, cliff = -1.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);
256 for (i = 1; i < lb->max_stats; i++) {
259 if (!lb->stats[i].num_stats)
262 f = lb->stats[i].work_rate / lb->stats[i].num_stats;
264 if (f > best_f_max) {
266 printf("Best is %i\n", i);
268 best_f_max = f - (f / (i + 1)) / 4;
269 cliff = f - (f / (i + 1)) / 2;
271 } else if (!found_drop && f < cliff) {
273 printf("Found drop at %i\n", i);
280 return found_drop - 1;
285 static unsigned int calculate_target(struct lbalance *lb)
289 target = best_target(lb);
291 /* Jitter if the adjacent ones are unknown. */
292 if (target >= lb->max_stats || lb->stats[target].num_stats == 0)
295 if (target + 1 == lb->max_stats || lb->stats[target+1].num_stats == 0)
298 if (target > 1 && lb->stats[target-1].num_stats == 0)
304 unsigned lbalance_target(struct lbalance *lb)
306 if (!lb->target_uptodate) {
307 lb->target = calculate_target(lb);
308 lb->target_uptodate = true;
313 void lbalance_free(struct lbalance *lb)
315 struct lbalance_task *task;
317 while ((task = tlist_top(&lb->tasks, list))) {
318 assert(task->lb == lb);
319 tlist_del_from(&lb->tasks, task, list);
323 assert(lb->num_tasks == 0);