job.c

   1 /* job.c - a job in the queue */
   2
   3 /* Copyright (C) 2007 Keith Rarick and Philotic Inc.
   4
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include "tube.h"
  23 #include "job.h"
  24 #include "primes.h"
  25 #include "util.h"
  26
  27 static unsigned long long int next_id = 1;
  28
  29 static int cur_prime = 0;
  30
  31 static job *all_jobs = NULL;
  32 static size_t all_jobs_cap = 12289; /* == primes[0] */
  33 static size_t all_jobs_used = 0;
  34
  35 static int hash_table_was_oom = 0;
  36
  37 static void rehash();
  38
  39 static int
  40 _get_job_hash_index(unsigned long long int job_id)
  41 {
  42     return job_id % all_jobs_cap;
  43 }
  44
  45 static void
  46 store_job(job j)
  47 {
  48     int index = 0;
  49
  50     index = _get_job_hash_index(j->id);
  51
  52     j->ht_next = all_jobs[index];
  53     all_jobs[index] = j;
  54     all_jobs_used++;
  55
  56     /* accept a load factor of 4 */
  57     if (all_jobs_used > (all_jobs_cap << 2)) rehash();
  58 }
  59
  60 static void
  61 rehash()
  62 {
  63     job *old = all_jobs;
  64     size_t old_cap = all_jobs_cap, old_used = all_jobs_used, i;
  65
  66     if (cur_prime >= NUM_PRIMES) return;
  67     if (hash_table_was_oom) return;
  68
  69     all_jobs_cap = primes[++cur_prime];
  70     all_jobs = calloc(all_jobs_cap, sizeof(job));
  71     if (!all_jobs) {
  72         twarnx("Failed to allocate %d new hash buckets", all_jobs_cap);
  73         hash_table_was_oom = 1;
  74         --cur_prime;
  75         all_jobs = old;
  76         all_jobs_cap = old_cap;
  77         all_jobs_used = old_used;
  78         return;
  79     }
  80     all_jobs_used = 0;
  81
  82     for (i = 0; i < old_cap; i++) {
  83         while (old[i]) {
  84             job j = old[i];
  85             old[i] = j->ht_next;
  86             j->ht_next = NULL;
  87             store_job(j);
  88         }
  89     }
  90 }
  91
  92 job
  93 job_find(unsigned long long int job_id)
  94 {
  95     job jh = NULL;
  96     int index = _get_job_hash_index(job_id);
  97
  98     for (jh = all_jobs[index]; jh && jh->id != job_id; jh = jh->ht_next);
  99
 100     return jh;
 101 }
 102
 103 job
 104 allocate_job(int body_size)
 105 {
 106     job j;
 107
 108     j = malloc(sizeof(struct job) + body_size);
 109     if (!j) return twarnx("OOM"), NULL;
 110
 111     j->id = 0;
 112     j->state = JOB_STATE_INVALID;
 113     j->creation = time(NULL);
 114     j->timeout_ct = j->release_ct = j->bury_ct = j->kick_ct = 0;
 115     j->body_size = body_size;
 116     j->next = j->prev = j; /* not in a linked list */
 117     j->ht_next = NULL;
 118     j->tube = NULL;
 119     j->binlog = NULL;
 120     j->heap_index = 0;
 121
 122     return j;
 123 }
 124
 125 job
 126 make_job_with_id(unsigned int pri, unsigned int delay, unsigned int ttr,
 127                  int body_size, tube tube, unsigned long long id)
 128 {
 129     job j;
 130
 131     j = allocate_job(body_size);
 132     if (!j) return twarnx("OOM"), NULL;
 133
 134     if (id) {
 135         j->id = id;
 136         if (id >= next_id) next_id = id + 1;
 137     } else {
 138         j->id = next_id++;
 139     }
 140     j->pri = pri;
 141     j->delay = delay;
 142     j->ttr = ttr;
 143
 144     store_job(j);
 145
 146     TUBE_ASSIGN(j->tube, tube);
 147
 148     return j;
 149 }
 150
 151 static void
 152 job_hash_free(job j)
 153 {
 154     int index = _get_job_hash_index(j->id);
 155     job jh = all_jobs ? all_jobs[index] : NULL;
 156
 157     if (jh) {
 158         if (jh == j) {
 159             /* Special case the first */
 160             all_jobs[index] = jh->ht_next;
 161         } else {
 162             job tmp;
 163             while (jh->ht_next && jh->ht_next != j) jh = jh->ht_next;
 164             if (jh->ht_next) {
 165                 tmp = jh->ht_next;
 166                 jh->ht_next = jh->ht_next->ht_next;
 167             }
 168         }
 169     }
 170
 171     all_jobs_used--;
 172 }
 173
 174 void
 175 job_free(job j)
 176 {
 177     if (j) {
 178         TUBE_ASSIGN(j->tube, NULL);
 179         job_hash_free(j);
 180     }
 181
 182     free(j);
 183 }
 184
 185 /* We can't substrct any of these values because there are too many bits */
 186 int
 187 job_pri_cmp(job a, job b)
 188 {
 189     if (a->pri > b->pri) return 1;
 190     if (a->pri < b->pri) return -1;
 191     if (a->id > b->id) return 1;
 192     if (a->id < b->id) return -1;
 193     return 0;
 194 }
 195
 196 /* We can't substrct any of these values because there are too many bits */
 197 int
 198 job_delay_cmp(job a, job b)
 199 {
 200     if (a->deadline > b->deadline) return 1;
 201     if (a->deadline < b->deadline) return -1;
 202     if (a->id > b->id) return 1;
 203     if (a->id < b->id) return -1;
 204     return 0;
 205 }
 206
 207 job
 208 job_copy(job j)
 209 {
 210     job n;
 211
 212     if (!j) return NULL;
 213
 214     n = malloc(sizeof(struct job) + j->body_size);
 215     if (!n) return twarnx("OOM"), NULL;
 216
 217     memcpy(n, j, sizeof(struct job) + j->body_size);
 218     n->next = n->prev = n; /* not in a linked list */
 219
 220     n->tube = 0; /* Don't use memcpy for the tube, which we must refcount. */
 221     TUBE_ASSIGN(n->tube, j->tube);
 222
 223     return n;
 224 }
 225
 226 const char *
 227 job_state(job j)
 228 {
 229     if (j->state == JOB_STATE_READY) return "ready";
 230     if (j->state == JOB_STATE_RESERVED) return "reserved";
 231     if (j->state == JOB_STATE_BURIED) return "buried";
 232     if (j->state == JOB_STATE_DELAYED) return "delayed";
 233     return "invalid";
 234 }
 235
 236 int
 237 job_list_any_p(job head)
 238 {
 239     return head->next != head || head->prev != head;
 240 }
 241
 242 job
 243 job_remove(job j)
 244 {
 245     if (!j) return NULL;
 246     if (!job_list_any_p(j)) return NULL; /* not in a doubly-linked list */
 247
 248     j->next->prev = j->prev;
 249     j->prev->next = j->next;
 250
 251     j->prev = j->next = j;
 252
 253     return j;
 254 }
 255
 256 void
 257 job_insert(job head, job j)
 258 {
 259     if (job_list_any_p(j)) return; /* already in a linked list */
 260
 261     j->prev = head->prev;
 262     j->next = head;
 263     head->prev->next = j;
 264     head->prev = j;
 265 }
 266
 267 unsigned long long int
 268 total_jobs()
 269 {
 270     return next_id - 1;
 271 }
 272
 273 void
 274 job_init()
 275 {
 276     all_jobs = calloc(all_jobs_cap, sizeof(job));
 277     if (!all_jobs) {
 278         twarnx("Failed to allocate %d hash buckets", all_jobs_cap);
 279     }
 280 }