1 /*****************************************************************************
2 * rrd_hw_update.c Functions for updating a Holt-Winters RRA
3 ****************************************************************************/
5 #include "rrd_tool.h"
6 #include "rrd_format.h"
7 #include "rrd_hw_math.h"
8 #include "rrd_hw_update.h"
10 static void init_slope_intercept(
11 unival *coefs,
12 unsigned short CDP_scratch_idx)
13 {
14 #ifdef DEBUG
15 fprintf(stderr, "Initialization of slope/intercept\n");
16 #endif
17 coefs[CDP_hw_intercept].u_val = coefs[CDP_scratch_idx].u_val;
18 coefs[CDP_hw_last_intercept].u_val = coefs[CDP_scratch_idx].u_val;
19 /* initialize the slope to 0 */
20 coefs[CDP_hw_slope].u_val = 0.0;
21 coefs[CDP_hw_last_slope].u_val = 0.0;
22 /* initialize null count to 1 */
23 coefs[CDP_null_count].u_cnt = 1;
24 coefs[CDP_last_null_count].u_cnt = 1;
25 }
27 static int hw_is_violation(
28 rrd_value_t observed,
29 rrd_value_t prediction,
30 rrd_value_t deviation,
31 rrd_value_t delta_pos,
32 rrd_value_t delta_neg)
33 {
34 return (observed > prediction + delta_pos * deviation
35 || observed < prediction - delta_neg * deviation);
36 }
38 int update_hwpredict(
39 rrd_t *rrd,
40 unsigned long cdp_idx,
41 unsigned long rra_idx,
42 unsigned long ds_idx,
43 unsigned short CDP_scratch_idx,
44 hw_functions_t * functions)
45 {
46 rrd_value_t prediction;
47 unsigned long dependent_rra_idx, seasonal_cdp_idx;
48 unival *coefs = rrd->cdp_prep[cdp_idx].scratch;
49 rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
50 rrd_value_t seasonal_coef;
52 /* save coefficients from current prediction */
53 coefs[CDP_hw_last_intercept].u_val = coefs[CDP_hw_intercept].u_val;
54 coefs[CDP_hw_last_slope].u_val = coefs[CDP_hw_slope].u_val;
55 coefs[CDP_last_null_count].u_cnt = coefs[CDP_null_count].u_cnt;
57 /* retrieve the current seasonal coef */
58 dependent_rra_idx = current_rra->par[RRA_dependent_rra_idx].u_cnt;
59 seasonal_cdp_idx = dependent_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
61 seasonal_coef = (dependent_rra_idx < rra_idx)
62 ? rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_last_seasonal].u_val
63 : rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_seasonal].u_val;
65 /* compute the prediction */
66 if (isnan(coefs[CDP_hw_intercept].u_val)
67 || isnan(coefs[CDP_hw_slope].u_val)
68 || isnan(seasonal_coef)) {
69 prediction = DNAN;
71 /* bootstrap initialization of slope and intercept */
72 if (isnan(coefs[CDP_hw_intercept].u_val) &&
73 !isnan(coefs[CDP_scratch_idx].u_val)) {
74 init_slope_intercept(coefs, CDP_scratch_idx);
75 }
76 /* if seasonal coefficient is NA, then don't update intercept, slope */
77 } else {
78 prediction = functions->predict(coefs[CDP_hw_intercept].u_val,
79 coefs[CDP_hw_slope].u_val,
80 coefs[CDP_null_count].u_cnt,
81 seasonal_coef);
82 #ifdef DEBUG
83 fprintf(stderr,
84 "computed prediction: %f (intercept %f, slope %f, season %f)\n",
85 prediction, coefs[CDP_hw_intercept].u_val,
86 coefs[CDP_hw_slope].u_val, seasonal_coef);
87 #endif
88 if (isnan(coefs[CDP_scratch_idx].u_val)) {
89 /* NA value, no updates of intercept, slope;
90 * increment the null count */
91 (coefs[CDP_null_count].u_cnt)++;
92 } else {
93 /* update the intercept */
94 coefs[CDP_hw_intercept].u_val =
95 functions->intercept(current_rra->par[RRA_hw_alpha].u_val,
96 coefs[CDP_scratch_idx].u_val,
97 seasonal_coef, coefs);
99 /* update the slope */
100 coefs[CDP_hw_slope].u_val =
101 functions->slope(current_rra->par[RRA_hw_beta].u_val, coefs);
103 /* reset the null count */
104 coefs[CDP_null_count].u_cnt = 1;
105 #ifdef DEBUG
106 fprintf(stderr, "Updating intercept = %f, slope = %f\n",
107 coefs[CDP_hw_intercept].u_val, coefs[CDP_hw_slope].u_val);
108 #endif
109 }
110 }
112 /* store the prediction for writing */
113 coefs[CDP_scratch_idx].u_val = prediction;
114 return 0;
115 }
117 int update_seasonal(
118 rrd_t *rrd,
119 unsigned long cdp_idx,
120 unsigned long rra_idx,
121 unsigned long ds_idx,
122 unsigned short CDP_scratch_idx,
123 rrd_value_t *seasonal_coef,
124 hw_functions_t * functions)
125 {
126 /* TODO: extract common if subblocks in the wake of I/O optimization */
127 rrd_value_t intercept, seasonal;
128 rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
129 rra_def_t *hw_rra =
130 &(rrd->rra_def[current_rra->par[RRA_dependent_rra_idx].u_cnt]);
132 /* obtain cdp_prep index for HWPREDICT */
133 unsigned long hw_cdp_idx = (current_rra->par[RRA_dependent_rra_idx].u_cnt)
134 * (rrd->stat_head->ds_cnt) + ds_idx;
135 unival *coefs = rrd->cdp_prep[hw_cdp_idx].scratch;
137 /* update seasonal coefficient in cdp prep areas */
138 seasonal = rrd->cdp_prep[cdp_idx].scratch[CDP_hw_seasonal].u_val;
139 rrd->cdp_prep[cdp_idx].scratch[CDP_hw_last_seasonal].u_val = seasonal;
140 rrd->cdp_prep[cdp_idx].scratch[CDP_hw_seasonal].u_val =
141 seasonal_coef[ds_idx];
143 if (isnan(rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val)) {
144 /* no update, store the old value unchanged,
145 * doesn't matter if it is NA */
146 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = seasonal;
147 return 0;
148 }
150 /* update seasonal value for disk */
151 if (current_rra->par[RRA_dependent_rra_idx].u_cnt < rra_idx) {
152 /* associated HWPREDICT has already been updated */
153 /* check for possible NA values */
154 if (isnan(coefs[CDP_hw_last_intercept].u_val)
155 || isnan(coefs[CDP_hw_last_slope].u_val)) {
156 /* this should never happen, as HWPREDICT was already updated */
157 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = DNAN;
158 } else if (isnan(seasonal)) {
159 /* initialization: intercept is not currently being updated */
160 #ifdef DEBUG
161 fprintf(stderr, "Initialization of seasonal coef %lu\n",
162 rrd->rra_ptr[rra_idx].cur_row);
163 #endif
164 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
165 functions->init_seasonality(rrd->cdp_prep[cdp_idx].
166 scratch[CDP_scratch_idx].u_val,
167 coefs[CDP_hw_last_intercept].
168 u_val);
169 } else {
170 intercept = coefs[CDP_hw_intercept].u_val;
172 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
173 functions->seasonality(current_rra->par[RRA_seasonal_gamma].
174 u_val,
175 rrd->cdp_prep[cdp_idx].
176 scratch[CDP_scratch_idx].u_val,
177 intercept, seasonal);
178 #ifdef DEBUG
179 fprintf(stderr,
180 "Updating seasonal = %f (params: gamma %f, new intercept %f, old seasonal %f)\n",
181 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val,
182 current_rra->par[RRA_seasonal_gamma].u_val,
183 intercept, seasonal);
184 #endif
185 }
186 } else {
187 /* SEASONAL array is updated first, which means the new intercept
188 * hasn't be computed; so we compute it here. */
190 /* check for possible NA values */
191 if (isnan(coefs[CDP_hw_intercept].u_val)
192 || isnan(coefs[CDP_hw_slope].u_val)) {
193 /* Initialization of slope and intercept will occur.
194 * force seasonal coefficient to 0 or 1. */
195 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
196 functions->identity;
197 } else if (isnan(seasonal)) {
198 /* initialization: intercept will not be updated
199 * CDP_hw_intercept = CDP_hw_last_intercept; just need to
200 * subtract/divide by this baseline value. */
201 #ifdef DEBUG
202 fprintf(stderr, "Initialization of seasonal coef %lu\n",
203 rrd->rra_ptr[rra_idx].cur_row);
204 #endif
205 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
206 functions->init_seasonality(rrd->cdp_prep[cdp_idx].
207 scratch[CDP_scratch_idx].u_val,
208 coefs[CDP_hw_intercept].u_val);
209 } else {
210 /* Note that we must get CDP_scratch_idx from SEASONAL array, as CDP_scratch_idx
211 * for HWPREDICT array will be DNAN. */
212 intercept = functions->intercept(hw_rra->par[RRA_hw_alpha].u_val,
213 rrd->cdp_prep[cdp_idx].
214 scratch[CDP_scratch_idx].u_val,
215 seasonal, coefs);
217 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
218 functions->seasonality(current_rra->par[RRA_seasonal_gamma].
219 u_val,
220 rrd->cdp_prep[cdp_idx].
221 scratch[CDP_scratch_idx].u_val,
222 intercept, seasonal);
223 }
224 }
225 #ifdef DEBUG
226 fprintf(stderr, "seasonal coefficient set= %f\n",
227 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val);
228 #endif
229 return 0;
230 }
232 int update_devpredict(
233 rrd_t *rrd,
234 unsigned long cdp_idx,
235 unsigned long rra_idx,
236 unsigned long ds_idx,
237 unsigned short CDP_scratch_idx)
238 {
239 /* there really isn't any "update" here; the only reason this information
240 * is stored separately from DEVSEASONAL is to preserve deviation predictions
241 * for a longer duration than one seasonal cycle. */
242 unsigned long seasonal_cdp_idx =
243 (rrd->rra_def[rra_idx].par[RRA_dependent_rra_idx].u_cnt)
244 * (rrd->stat_head->ds_cnt) + ds_idx;
246 if (rrd->rra_def[rra_idx].par[RRA_dependent_rra_idx].u_cnt < rra_idx) {
247 /* associated DEVSEASONAL array already updated */
248 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val
249 =
250 rrd->cdp_prep[seasonal_cdp_idx].
251 scratch[CDP_last_seasonal_deviation].u_val;
252 } else {
253 /* associated DEVSEASONAL not yet updated */
254 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val
255 =
256 rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_seasonal_deviation].
257 u_val;
258 }
259 return 0;
260 }
262 int update_devseasonal(
263 rrd_t *rrd,
264 unsigned long cdp_idx,
265 unsigned long rra_idx,
266 unsigned long ds_idx,
267 unsigned short CDP_scratch_idx,
268 rrd_value_t *seasonal_dev,
269 hw_functions_t * functions)
270 {
271 rrd_value_t prediction = 0, seasonal_coef = DNAN;
272 rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
274 /* obtain cdp_prep index for HWPREDICT */
275 unsigned long hw_rra_idx = current_rra->par[RRA_dependent_rra_idx].u_cnt;
276 unsigned long hw_cdp_idx = hw_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
277 unsigned long seasonal_cdp_idx;
278 unival *coefs = rrd->cdp_prep[hw_cdp_idx].scratch;
280 rrd->cdp_prep[cdp_idx].scratch[CDP_last_seasonal_deviation].u_val =
281 rrd->cdp_prep[cdp_idx].scratch[CDP_seasonal_deviation].u_val;
282 /* retrieve the next seasonal deviation value, could be NA */
283 rrd->cdp_prep[cdp_idx].scratch[CDP_seasonal_deviation].u_val =
284 seasonal_dev[ds_idx];
286 /* retrieve the current seasonal_coef (not to be confused with the
287 * current seasonal deviation). Could make this more readable by introducing
288 * some wrapper functions. */
289 seasonal_cdp_idx =
290 (rrd->rra_def[hw_rra_idx].par[RRA_dependent_rra_idx].u_cnt)
291 * (rrd->stat_head->ds_cnt) + ds_idx;
292 if (rrd->rra_def[hw_rra_idx].par[RRA_dependent_rra_idx].u_cnt < rra_idx)
293 /* SEASONAL array already updated */
294 seasonal_coef =
295 rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_last_seasonal].
296 u_val;
297 else
298 /* SEASONAL array not yet updated */
299 seasonal_coef =
300 rrd->cdp_prep[seasonal_cdp_idx].scratch[CDP_hw_seasonal].u_val;
302 /* compute the abs value of the difference between the prediction and
303 * observed value */
304 if (hw_rra_idx < rra_idx) {
305 /* associated HWPREDICT has already been updated */
306 if (isnan(coefs[CDP_hw_last_intercept].u_val) ||
307 isnan(coefs[CDP_hw_last_slope].u_val) || isnan(seasonal_coef)) {
308 /* one of the prediction values is uinitialized */
309 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = DNAN;
310 return 0;
311 } else {
312 prediction =
313 functions->predict(coefs[CDP_hw_last_intercept].u_val,
314 coefs[CDP_hw_last_slope].u_val,
315 coefs[CDP_last_null_count].u_cnt,
316 seasonal_coef);
317 }
318 } else {
319 /* associated HWPREDICT has NOT been updated */
320 if (isnan(coefs[CDP_hw_intercept].u_val) ||
321 isnan(coefs[CDP_hw_slope].u_val) || isnan(seasonal_coef)) {
322 /* one of the prediction values is uinitialized */
323 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = DNAN;
324 return 0;
325 } else {
326 prediction = functions->predict(coefs[CDP_hw_intercept].u_val,
327 coefs[CDP_hw_slope].u_val,
328 coefs[CDP_null_count].u_cnt,
329 seasonal_coef);
330 }
331 }
333 if (isnan(rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val)) {
334 /* no update, store existing value unchanged, doesn't
335 * matter if it is NA */
336 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
337 rrd->cdp_prep[cdp_idx].scratch[CDP_last_seasonal_deviation].u_val;
338 } else
339 if (isnan
340 (rrd->cdp_prep[cdp_idx].scratch[CDP_last_seasonal_deviation].
341 u_val)) {
342 /* initialization */
343 #ifdef DEBUG
344 fprintf(stderr, "Initialization of seasonal deviation\n");
345 #endif
346 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
347 functions->init_seasonal_deviation(prediction,
348 rrd->cdp_prep[cdp_idx].
349 scratch[CDP_scratch_idx].
350 u_val);
351 } else {
352 /* exponential smoothing update */
353 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val =
354 functions->seasonal_deviation(rrd->rra_def[rra_idx].
355 par[RRA_seasonal_gamma].u_val,
356 prediction,
357 rrd->cdp_prep[cdp_idx].
358 scratch[CDP_scratch_idx].u_val,
359 rrd->cdp_prep[cdp_idx].
360 scratch
361 [CDP_last_seasonal_deviation].
362 u_val);
363 }
364 return 0;
365 }
367 /* Check for a failure based on a threshold # of violations within the specified
368 * window. */
369 int update_failures(
370 rrd_t *rrd,
371 unsigned long cdp_idx,
372 unsigned long rra_idx,
373 unsigned long ds_idx,
374 unsigned short CDP_scratch_idx,
375 hw_functions_t * functions)
376 {
377 /* detection of a violation depends on 3 RRAs:
378 * HWPREDICT, SEASONAL, and DEVSEASONAL */
379 rra_def_t *current_rra = &(rrd->rra_def[rra_idx]);
380 unsigned long dev_rra_idx = current_rra->par[RRA_dependent_rra_idx].u_cnt;
381 rra_def_t *dev_rra = &(rrd->rra_def[dev_rra_idx]);
382 unsigned long hw_rra_idx = dev_rra->par[RRA_dependent_rra_idx].u_cnt;
383 rra_def_t *hw_rra = &(rrd->rra_def[hw_rra_idx]);
384 unsigned long seasonal_rra_idx = hw_rra->par[RRA_dependent_rra_idx].u_cnt;
385 unsigned long temp_cdp_idx;
386 rrd_value_t deviation = DNAN;
387 rrd_value_t seasonal_coef = DNAN;
388 rrd_value_t prediction = DNAN;
389 char violation = 0;
390 unsigned short violation_cnt = 0, i;
391 char *violations_array;
393 /* usual checks to determine the order of the RRAs */
394 temp_cdp_idx = dev_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
395 if (rra_idx < seasonal_rra_idx) {
396 /* DEVSEASONAL not yet updated */
397 deviation =
398 rrd->cdp_prep[temp_cdp_idx].scratch[CDP_seasonal_deviation].u_val;
399 } else {
400 /* DEVSEASONAL already updated */
401 deviation =
402 rrd->cdp_prep[temp_cdp_idx].scratch[CDP_last_seasonal_deviation].
403 u_val;
404 }
405 if (!isnan(deviation)) {
407 temp_cdp_idx = seasonal_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
408 if (rra_idx < seasonal_rra_idx) {
409 /* SEASONAL not yet updated */
410 seasonal_coef =
411 rrd->cdp_prep[temp_cdp_idx].scratch[CDP_hw_seasonal].u_val;
412 } else {
413 /* SEASONAL already updated */
414 seasonal_coef =
415 rrd->cdp_prep[temp_cdp_idx].scratch[CDP_hw_last_seasonal].
416 u_val;
417 }
418 /* in this code block, we know seasonal coef is not DNAN, because deviation is not
419 * null */
421 temp_cdp_idx = hw_rra_idx * (rrd->stat_head->ds_cnt) + ds_idx;
422 if (rra_idx < hw_rra_idx) {
423 /* HWPREDICT not yet updated */
424 prediction =
425 functions->predict(rrd->cdp_prep[temp_cdp_idx].
426 scratch[CDP_hw_intercept].u_val,
427 rrd->cdp_prep[temp_cdp_idx].
428 scratch[CDP_hw_slope].u_val,
429 rrd->cdp_prep[temp_cdp_idx].
430 scratch[CDP_null_count].u_cnt,
431 seasonal_coef);
432 } else {
433 /* HWPREDICT already updated */
434 prediction =
435 functions->predict(rrd->cdp_prep[temp_cdp_idx].
436 scratch[CDP_hw_last_intercept].u_val,
437 rrd->cdp_prep[temp_cdp_idx].
438 scratch[CDP_hw_last_slope].u_val,
439 rrd->cdp_prep[temp_cdp_idx].
440 scratch[CDP_last_null_count].u_cnt,
441 seasonal_coef);
442 }
444 /* determine if the observed value is a violation */
445 if (!isnan(rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val)) {
446 if (hw_is_violation
447 (rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val,
448 prediction, deviation, current_rra->par[RRA_delta_pos].u_val,
449 current_rra->par[RRA_delta_neg].u_val)) {
450 violation = 1;
451 }
452 } else {
453 violation = 1; /* count DNAN values as violations */
454 }
456 }
458 /* determine if a failure has occurred and update the failure array */
459 violation_cnt = violation;
460 violations_array = (char *) ((void *) rrd->cdp_prep[cdp_idx].scratch);
461 for (i = current_rra->par[RRA_window_len].u_cnt; i > 1; i--) {
462 /* shift */
463 violations_array[i - 1] = violations_array[i - 2];
464 violation_cnt += violations_array[i - 1];
465 }
466 violations_array[0] = violation;
468 if (violation_cnt < current_rra->par[RRA_failure_threshold].u_cnt)
469 /* not a failure */
470 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = 0.0;
471 else
472 rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val = 1.0;
474 return (rrd->cdp_prep[cdp_idx].scratch[CDP_scratch_idx].u_val);
475 }