Implicitly assuming 64bit architecture in pqueue implementation

[erlingrj]

As I am turning on all warnings and treating them as errors I am seeing some odd things with the pqueue implementation. Basically, there is casting between unsigned long long which typically are 64 bit, and void * which are 32bit or 64bit depending on the architecture. I am specifically talking about the static functions at the top of pqueue_tag.c

/**
 * @brief Callback function to get the priority of an element.
 * Return the pointer argument cast to pqueue_pri_t because the
 * element is also the priority. This function is of type pqueue_get_pri_f.
 * @param element A pointer to a pqueue_tag_element_t, cast to void*.
 */
static pqueue_pri_t pqueue_tag_get_priority(void* element) { return (pqueue_pri_t)element; }

/**
 * @brief Callback comparison function for the tag-based priority queue.
 * Return 0 if the first argument is less than second and 1 otherwise.
 * This function is of type pqueue_cmp_pri_f.
 * @param priority1 A pointer to a pqueue_tag_element_t, cast to pqueue_pri_t.
 * @param priority2 A pointer to a pqueue_tag_element_t, cast to pqueue_pri_t.
 */
static int pqueue_tag_compare(pqueue_pri_t priority1, pqueue_pri_t priority2) {
  return (lf_tag_compare(((pqueue_tag_element_t*)priority1)->tag, ((pqueue_tag_element_t*)priority2)->tag) > 0);
}

E.g. in pqueue_tag_get_priority we assume that a void* can hold unsigned long long, this is not true on 32bit archs. Does anyone have a good handle on how the pqueue works?

In pqueue_init we can see that it allocates only memory for a void* for each element (i.e. 64bit or 32bit depending on arch).

  /* Need to allocate n+1 elements since element 0 isn't used. */
  if (!(q->d = (void**)malloc((n + 1) * sizeof(void*)))) {
    free(q);
    return NULL;
  }

It suggests that we either must explicitly have elements which have the desired size (64bit) or we must make do with 32bit priorities for the 32bit platforms.

Any thoughts @lhstrh @edwardalee @petervdonovan ?

[petervdonovan]

To me it looks like the priority queue is currently only ever used to hold pointers. I think it's safe to just assume that the element size in the queue is 32 bits or 64 bits according to the architecture. Maybe we should see if everything compiles without errors or warnings once we remove any casts to unsigned long long and any unsafe casts from unsigned long long.

[erlingrj]

Thanks, @petervdonovan, the priority queue data type is also used as the reaction index. And this hard-coded to be an unsigned long long. I think the intention is that the reaction index is a 64-bit combination of level and deadline and this is used, at least in the reaction pqueue to keep the reactions sorted. So we would need to update the reaction-index notion also to be an integer corresponding to the architecture width, not hard-coded to 64-bit (or actually ULL which is platform-dependent)

[petervdonovan]

the priority queue data type is also used as the reaction index.

Are you sure about that?

The reaction index is being accessed as a field of a reaction struct.

pqueue.c (an identical implementation also exists in pqueue_support.h):

pqueue_pri_t get_reaction_index(void *reaction) {
    return ((reaction_t*) reaction)->index;
}

This is being passed into the pqueue implementation as the pqueue_get_pri_f function (parameter name getpri) in environment.c (for the single-threaded case) and in GEDF_NP (which is the only scheduler that respects reaction priority using a pqueue).

environment.c:

    env->reaction_q = pqueue_init(INITIAL_REACT_QUEUE_SIZE, in_reverse_order, get_reaction_index,
                get_reaction_position, set_reaction_position, reaction_matches, print_reaction);

scheduler_GEDF_NP.c:

        // Initialize the reaction queues
        ((pqueue_t**)scheduler->triggered_reactions)[i] =
            pqueue_init(queue_size, in_reverse_order, get_reaction_index,
                        get_reaction_position, set_reaction_position,
                        reaction_matches, print_reaction);

So we would need to update the reaction-index notion also to be an integer corresponding to the architecture width, not hard-coded to 64-bit (or actually ULL which is platform-dependent)

I think we probably cannot fit the reaction data type into 32 bits because we are already doing some bit-cramming here.

environment.c:

    // Reaction queue ordered first by deadline, then by level.
    // The index of the reaction holds the deadline in the 48 most significant bits,
    // the level in the 16 least significant bits.