qdevices/timer-list.c

   1 /*
   2  * Copyright (c) 2015-2020 Red Hat, Inc.
   3  *
   4  * All rights reserved.
   5  *
   6  * Author: Jan Friesse (jfriesse@redhat.com)
   7  *
   8  * This software licensed under BSD license, the text of which follows:
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions are met:
  12  *
  13  * - Redistributions of source code must retain the above copyright notice,
  14  *   this list of conditions and the following disclaimer.
  15  * - Redistributions in binary form must reproduce the above copyright notice,
  16  *   this list of conditions and the following disclaimer in the documentation
  17  *   and/or other materials provided with the distribution.
  18  * - Neither the name of the Red Hat, Inc. nor the names of its
  19  *   contributors may be used to endorse or promote products derived from this
  20  *   software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  23  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  26  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  27  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  28  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  29  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  30  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  31  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  32  * THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #include <assert.h>
  36 #include <string.h>
  37
  38 #include "timer-list.h"
  39
  40 void
  41 timer_list_init(struct timer_list *tlist)
  42 {
  43
  44         memset(tlist, 0, sizeof(*tlist));
  45
  46         TAILQ_INIT(&tlist->free_list);
  47 }
  48
  49 static PRIntervalTime
  50 timer_list_entry_time_to_expire(const struct timer_list_entry *entry, PRIntervalTime current_time)
  51 {
  52         PRIntervalTime diff, half_interval;
  53
  54         diff = entry->expire_time - current_time;
  55         half_interval = ~0;
  56         half_interval /= 2;
  57
  58         if (diff > half_interval) {
  59                 return (0);
  60         }
  61
  62         return (diff);
  63 }
  64
  65 static int
  66 timer_list_entry_cmp(const struct timer_list_entry *entry1,
  67     const struct timer_list_entry *entry2, PRIntervalTime current_time)
  68 {
  69         PRIntervalTime diff1, diff2;
  70         int res;
  71
  72         diff1 = timer_list_entry_time_to_expire(entry1, current_time);
  73         diff2 = timer_list_entry_time_to_expire(entry2, current_time);
  74
  75         res = 0;
  76
  77         if (diff1 < diff2) res = -1;
  78         if (diff1 > diff2) res = 1;
  79
  80         return (res);
  81 }
  82
  83 static size_t
  84 timer_list_heap_index_left(size_t index)
  85 {
  86
  87         return (2 * index + 1);
  88 }
  89
  90 static size_t
  91 timer_list_heap_index_right(size_t index)
  92 {
  93
  94         return (2 * index + 2);
  95 }
  96
  97 static size_t
  98 timer_list_heap_index_parent(size_t index)
  99 {
 100
 101         return ((index - 1) / 2);
 102 }
 103
 104 static void
 105 timer_list_heap_entry_set(struct timer_list *tlist, size_t item_pos, struct timer_list_entry *entry)
 106 {
 107
 108         assert(item_pos < tlist->size);
 109
 110         tlist->entries[item_pos] = entry;
 111         tlist->entries[item_pos]->heap_pos = item_pos;
 112 }
 113
 114 static struct timer_list_entry *
 115 timer_list_heap_entry_get(struct timer_list *tlist, size_t item_pos)
 116 {
 117
 118         assert(item_pos < tlist->size);
 119
 120         return (tlist->entries[item_pos]);
 121 }
 122
 123 static void
 124 timer_list_heap_sift_up(struct timer_list *tlist, size_t item_pos)
 125 {
 126         size_t parent_pos;
 127         struct timer_list_entry *parent_entry;
 128         struct timer_list_entry *item_entry;
 129
 130         item_entry = timer_list_heap_entry_get(tlist, item_pos);
 131
 132         parent_pos = timer_list_heap_index_parent(item_pos);
 133
 134         while (item_pos > 0 &&
 135             (parent_entry = timer_list_heap_entry_get(tlist, parent_pos),
 136             timer_list_entry_cmp(parent_entry, item_entry, item_entry->epoch) > 0)) {
 137                 /*
 138                  * Swap item and parent
 139                  */
 140                 timer_list_heap_entry_set(tlist, parent_pos, item_entry);
 141                 timer_list_heap_entry_set(tlist, item_pos, parent_entry);
 142
 143                 item_pos = parent_pos;
 144                 parent_pos = timer_list_heap_index_parent(item_pos);
 145         }
 146 }
 147
 148 static void
 149 timer_list_heap_sift_down(struct timer_list *tlist, size_t item_pos)
 150 {
 151         int cont;
 152         size_t left_pos, right_pos, smallest_pos;
 153         struct timer_list_entry *left_entry;
 154         struct timer_list_entry *right_entry;
 155         struct timer_list_entry *smallest_entry;
 156         struct timer_list_entry *tmp_entry;
 157
 158         cont = 1;
 159
 160         while (cont) {
 161                 smallest_pos = item_pos;
 162                 left_pos = timer_list_heap_index_left(item_pos);
 163                 right_pos = timer_list_heap_index_right(item_pos);
 164
 165                 smallest_entry = timer_list_heap_entry_get(tlist, smallest_pos);
 166
 167                 if (left_pos < tlist->size &&
 168                     (left_entry = timer_list_heap_entry_get(tlist, left_pos),
 169                     timer_list_entry_cmp(left_entry, smallest_entry, smallest_entry->epoch) < 0)) {
 170                         smallest_entry = left_entry;
 171                         smallest_pos = left_pos;
 172                 }
 173
 174                 if (right_pos < tlist->size &&
 175                     (right_entry = timer_list_heap_entry_get(tlist, right_pos),
 176                     timer_list_entry_cmp(right_entry, smallest_entry, smallest_entry->epoch) < 0)) {
 177                         smallest_entry = right_entry;
 178                         smallest_pos = right_pos;
 179                 }
 180
 181                 if (smallest_pos == item_pos) {
 182                         /*
 183                          * Item is smallest (or has no childs) -> heap property is restored
 184                          */
 185                         cont = 0;
 186                 } else {
 187                         /*
 188                          * Swap item with smallest child
 189                          */
 190                         tmp_entry = timer_list_heap_entry_get(tlist, item_pos);
 191                         timer_list_heap_entry_set(tlist, item_pos, smallest_entry);
 192                         timer_list_heap_entry_set(tlist, smallest_pos, tmp_entry);
 193
 194                         item_pos = smallest_pos;
 195                 }
 196         }
 197 }
 198
 199 static void
 200 timer_list_heap_delete(struct timer_list *tlist, struct timer_list_entry *entry)
 201 {
 202         size_t entry_pos;
 203         struct timer_list_entry *replacement_entry;
 204         int cmp_entries;
 205
 206         entry_pos = entry->heap_pos;
 207         entry->heap_pos = (~(size_t)0);
 208
 209         /*
 210          * Swap element with last element
 211          */
 212         replacement_entry = timer_list_heap_entry_get(tlist, tlist->size - 1);
 213         timer_list_heap_entry_set(tlist, entry_pos, replacement_entry);
 214
 215         /*
 216          * And "remove" last element (= entry)
 217          */
 218         tlist->size--;
 219
 220         /*
 221          * Up (or down) heapify based on replacement item size
 222          */
 223         cmp_entries = timer_list_entry_cmp(replacement_entry, entry, entry->epoch);
 224
 225         if (cmp_entries < 0) {
 226                 timer_list_heap_sift_up(tlist, entry_pos);
 227         } else if (cmp_entries > 0) {
 228                 timer_list_heap_sift_down(tlist, entry_pos);
 229         }
 230 }
 231
 232 /*
 233  * Check if heap is valid.
 234  * - Shape property is always fullfiled because of storage in array
 235  * - Check heap property
 236  */
 237 int
 238 timer_list_debug_is_valid_heap(struct timer_list *tlist)
 239 {
 240         size_t i;
 241         size_t left_pos, right_pos;
 242         struct timer_list_entry *left_entry;
 243         struct timer_list_entry *right_entry;
 244         struct timer_list_entry *cur_entry;
 245
 246         for (i = 0; i < tlist->size; i++) {
 247                 cur_entry = timer_list_heap_entry_get(tlist, i);
 248
 249                 left_pos = timer_list_heap_index_left(i);
 250                 right_pos = timer_list_heap_index_right(i);
 251
 252                 if (left_pos < tlist->size &&
 253                     (left_entry = timer_list_heap_entry_get(tlist, left_pos),
 254                     timer_list_entry_cmp(left_entry, cur_entry, cur_entry->epoch) < 0)) {
 255                         return (0);
 256                 }
 257
 258                 if (right_pos < tlist->size &&
 259                     (right_entry = timer_list_heap_entry_get(tlist, right_pos),
 260                     timer_list_entry_cmp(right_entry, cur_entry, cur_entry->epoch) < 0)) {
 261                         return (0);
 262                 }
 263         }
 264
 265         return (1);
 266 }
 267
 268 static int
 269 timer_list_insert_into_list(struct timer_list *tlist, struct timer_list_entry *new_entry)
 270 {
 271         size_t new_size;
 272         struct timer_list_entry **new_entries;
 273
 274         /*
 275          * This can overflow and it's not a problem
 276          */
 277         new_entry->expire_time = new_entry->epoch + PR_MillisecondsToInterval(new_entry->interval);
 278
 279         /*
 280          * Heap insert
 281          */
 282         if (tlist->size + 1 > tlist->allocated) {
 283                 new_size = (tlist->allocated + 1) * 2;
 284
 285                 new_entries = realloc(tlist->entries, new_size * sizeof(tlist->entries[0]));
 286
 287                 if (new_entries == NULL) {
 288                         return (-1);
 289                 }
 290
 291                 tlist->allocated = new_size;
 292                 tlist->entries = new_entries;
 293         }
 294
 295         tlist->size++;
 296         timer_list_heap_entry_set(tlist, tlist->size - 1, new_entry);
 297
 298         timer_list_heap_sift_up(tlist, tlist->size - 1);
 299
 300         return (0);
 301 }
 302
 303 struct timer_list_entry *
 304 timer_list_add(struct timer_list *tlist, PRUint32 interval, timer_list_cb_fn func, void *data1,
 305     void *data2)
 306 {
 307         struct timer_list_entry *new_entry;
 308
 309         if (interval < 1 || interval > TIMER_LIST_MAX_INTERVAL || func == NULL) {
 310                 return (NULL);
 311         }
 312
 313         if (!TAILQ_EMPTY(&tlist->free_list)) {
 314                 /*
 315                  * Use free list entry
 316                  */
 317                 new_entry = TAILQ_FIRST(&tlist->free_list);
 318                 TAILQ_REMOVE(&tlist->free_list, new_entry, entries);
 319         } else {
 320                 /*
 321                  * Alloc new entry
 322                  */
 323                 new_entry = malloc(sizeof(*new_entry));
 324                 if (new_entry == NULL) {
 325                         return (NULL);
 326                 }
 327         }
 328
 329         memset(new_entry, 0, sizeof(*new_entry));
 330         new_entry->epoch = PR_IntervalNow();
 331         new_entry->interval = interval;
 332         new_entry->func = func;
 333         new_entry->user_data1 = data1;
 334         new_entry->user_data2 = data2;
 335         new_entry->is_active = 1;
 336         new_entry->heap_pos = (~(size_t)0);
 337
 338         if (timer_list_insert_into_list(tlist, new_entry) != 0) {
 339                 TAILQ_INSERT_HEAD(&tlist->free_list, new_entry, entries);
 340
 341                 return (NULL);
 342         }
 343
 344         return (new_entry);
 345 }
 346
 347 void
 348 timer_list_reschedule(struct timer_list *tlist, struct timer_list_entry *entry)
 349 {
 350
 351         if (entry->is_active) {
 352                 timer_list_heap_delete(tlist, entry);
 353
 354                 entry->epoch = PR_IntervalNow();
 355
 356                 timer_list_insert_into_list(tlist, entry);
 357         }
 358 }
 359
 360 void
 361 timer_list_expire(struct timer_list *tlist)
 362 {
 363         PRIntervalTime now;
 364         struct timer_list_entry *entry;
 365         int res;
 366
 367         now = PR_IntervalNow();
 368
 369         while (tlist->size > 0 &&
 370             (entry = timer_list_heap_entry_get(tlist, 0),
 371             timer_list_entry_time_to_expire(entry, now) == 0)) {
 372                 /*
 373                  * Expired
 374                  */
 375                 res = entry->func(entry->user_data1, entry->user_data2);
 376                 if (res == 0) {
 377                         /*
 378                          * Move item to free list
 379                          */
 380                         timer_list_delete(tlist, entry);
 381                 } else if (entry->is_active) {
 382                         /*
 383                          * Schedule again
 384                          */
 385                         timer_list_heap_delete(tlist, entry);
 386
 387                         entry->epoch = now;
 388
 389                         timer_list_insert_into_list(tlist, entry);
 390                 }
 391         }
 392 }
 393
 394 PRIntervalTime
 395 timer_list_time_to_expire(struct timer_list *tlist)
 396 {
 397         struct timer_list_entry *entry;
 398
 399         if (tlist->size == 0) {
 400                 return (PR_INTERVAL_NO_TIMEOUT);
 401         }
 402
 403         entry = timer_list_heap_entry_get(tlist, 0);
 404
 405         return (timer_list_entry_time_to_expire(entry, PR_IntervalNow()));
 406 }
 407
 408 uint32_t
 409 timer_list_time_to_expire_ms(struct timer_list *tlist)
 410 {
 411         struct timer_list_entry *entry;
 412         uint32_t u32;
 413
 414         if (tlist->size == 0) {
 415                 u32 = ~((uint32_t)0);
 416                 return (u32);
 417         }
 418
 419         entry = timer_list_heap_entry_get(tlist, 0);
 420
 421         return (PR_IntervalToMilliseconds(timer_list_entry_time_to_expire(entry, PR_IntervalNow())));
 422 }
 423
 424 void
 425 timer_list_delete(struct timer_list *tlist, struct timer_list_entry *entry)
 426 {
 427
 428         if (entry->is_active) {
 429                 /*
 430                  * Remove item from heap and move it to free list
 431                  */
 432                 timer_list_heap_delete(tlist, entry);
 433
 434                 TAILQ_INSERT_HEAD(&tlist->free_list, entry, entries);
 435                 entry->is_active = 0;
 436         }
 437 }
 438
 439 void
 440 timer_list_free(struct timer_list *tlist)
 441 {
 442         struct timer_list_entry *entry;
 443         struct timer_list_entry *entry_next;
 444         size_t i;
 445
 446         for (i = 0; i < tlist->size; i++) {
 447                 free(timer_list_heap_entry_get(tlist, i));
 448         }
 449
 450         free(tlist->entries);
 451
 452         entry = TAILQ_FIRST(&tlist->free_list);
 453
 454         while (entry != NULL) {
 455                 entry_next = TAILQ_NEXT(entry, entries);
 456
 457                 free(entry);
 458
 459                 entry = entry_next;
 460         }
 461
 462         timer_list_init(tlist);
 463 }