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_sift_up(struct timer_list *tlist, size_t item_pos)
 106 {
 107         size_t parent_pos;
 108         struct timer_list_entry *parent_entry;
 109         struct timer_list_entry *item_entry;
 110
 111         item_entry = tlist->entries[item_pos];
 112
 113         parent_pos = timer_list_heap_index_parent(item_pos);
 114
 115         while (item_pos > 0 &&
 116             (parent_entry = tlist->entries[parent_pos],
 117             timer_list_entry_cmp(parent_entry, item_entry, item_entry->epoch) > 0)) {
 118                 /*
 119                  * Swap item and parent
 120                  */
 121                 tlist->entries[parent_pos] = item_entry;
 122                 tlist->entries[item_pos] = parent_entry;
 123
 124                 item_pos = parent_pos;
 125                 parent_pos = timer_list_heap_index_parent(item_pos);
 126         }
 127 }
 128
 129 static void
 130 timer_list_heap_sift_down(struct timer_list *tlist, size_t item_pos)
 131 {
 132         int cont;
 133         size_t left_pos, right_pos, smallest_pos;
 134         struct timer_list_entry *left_entry;
 135         struct timer_list_entry *right_entry;
 136         struct timer_list_entry *smallest_entry;
 137         struct timer_list_entry *tmp_entry;
 138
 139         cont = 1;
 140
 141         while (cont) {
 142                 smallest_pos = item_pos;
 143                 left_pos = timer_list_heap_index_left(item_pos);
 144                 right_pos = timer_list_heap_index_right(item_pos);
 145
 146                 smallest_entry = tlist->entries[smallest_pos];
 147
 148                 if (left_pos < tlist->size &&
 149                     (left_entry = tlist->entries[left_pos],
 150                     timer_list_entry_cmp(left_entry, smallest_entry, smallest_entry->epoch) < 0)) {
 151                         smallest_entry = left_entry;
 152                         smallest_pos = left_pos;
 153                 }
 154
 155                 if (right_pos < tlist->size &&
 156                     (right_entry = tlist->entries[right_pos],
 157                     timer_list_entry_cmp(right_entry, smallest_entry, smallest_entry->epoch) < 0)) {
 158                         smallest_entry = right_entry;
 159                         smallest_pos = right_pos;
 160                 }
 161
 162                 if (smallest_pos == item_pos) {
 163                         /*
 164                          * Item is smallest (or has no childs) -> heap property is restored
 165                          */
 166                         cont = 0;
 167                 } else {
 168                         /*
 169                          * Swap item with smallest child
 170                          */
 171                         tmp_entry = tlist->entries[item_pos];
 172                         tlist->entries[item_pos] = smallest_entry;
 173                         tlist->entries[smallest_pos] = tmp_entry;
 174
 175                         item_pos = smallest_pos;
 176                 }
 177         }
 178 }
 179
 180 static int
 181 timer_list_heap_delete(struct timer_list *tlist, struct timer_list_entry *entry)
 182 {
 183         size_t entry_pos;
 184         size_t i;
 185         struct timer_list_entry *replacement_entry;
 186         int cmp_entries;
 187
 188         entry_pos = tlist->size;
 189
 190         /*
 191          * Find the element index
 192          */
 193         for (i = 0; i < tlist->size; i++) {
 194                 if (tlist->entries[i] == entry) {
 195                         entry_pos = i;
 196                         break ;
 197                 }
 198         }
 199
 200         if (entry_pos == tlist->size) {
 201                 /*
 202                  * Item not found
 203                  */
 204                 return (-1);
 205         }
 206
 207         /*
 208          * Swap element with last element
 209          */
 210         replacement_entry = tlist->entries[tlist->size - 1];
 211         tlist->entries[entry_pos] = tlist->entries[tlist->size - 1];
 212
 213         /*
 214          * And "remove" last element (= entry)
 215          */
 216         tlist->size--;
 217
 218         /*
 219          * Up (or down) heapify based on replacement item size
 220          */
 221         cmp_entries = timer_list_entry_cmp(replacement_entry, entry, entry->epoch);
 222
 223         if (cmp_entries < 0) {
 224                 timer_list_heap_sift_up(tlist, entry_pos);
 225         } else if (cmp_entries > 0) {
 226                 timer_list_heap_sift_down(tlist, entry_pos);
 227         }
 228
 229         return (0);
 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 = tlist->entries[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 = tlist->entries[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 = tlist->entries[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->entries[tlist->size] = new_entry;
 296         tlist->size++;
 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
 337         if (timer_list_insert_into_list(tlist, new_entry) != 0) {
 338                 TAILQ_INSERT_HEAD(&tlist->free_list, new_entry, entries);
 339
 340                 return (NULL);
 341         }
 342
 343         return (new_entry);
 344 }
 345
 346 void
 347 timer_list_reschedule(struct timer_list *tlist, struct timer_list_entry *entry)
 348 {
 349         int res;
 350
 351         if (entry->is_active) {
 352                 res = timer_list_heap_delete(tlist, entry);
 353                 assert(res == 0);
 354
 355                 entry->epoch = PR_IntervalNow();
 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 = tlist->entries[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                         res = timer_list_heap_delete(tlist, entry);
 386                         assert(res == 0);
 387
 388                         entry->epoch = now;
 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 = tlist->entries[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 = tlist->entries[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         int res;
 428
 429         if (entry->is_active) {
 430                 /*
 431                  * Remove item from heap and move it to free list
 432                  */
 433                 res = timer_list_heap_delete(tlist, entry);
 434                 assert(res == 0);
 435
 436                 TAILQ_INSERT_HEAD(&tlist->free_list, entry, entries);
 437                 entry->is_active = 0;
 438         }
 439 }
 440
 441 void
 442 timer_list_free(struct timer_list *tlist)
 443 {
 444         struct timer_list_entry *entry;
 445         struct timer_list_entry *entry_next;
 446         size_t i;
 447
 448         for (i = 0; i < tlist->size; i++) {
 449                 free(tlist->entries[i]);
 450         }
 451
 452         free(tlist->entries);
 453
 454         entry = TAILQ_FIRST(&tlist->free_list);
 455
 456         while (entry != NULL) {
 457                 entry_next = TAILQ_NEXT(entry, entries);
 458
 459                 free(entry);
 460
 461                 entry = entry_next;
 462         }
 463
 464         timer_list_init(tlist);
 465 }