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