configurator: HAVE_SECTION_START_STOP
[ccan] / 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, 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 }