xen/timers: Document and improve the representation of the timer heap metadata
diff mbox series

Message ID 1553875336-17009-1-git-send-email-andrew.cooper3@citrix.com
State New, archived
Headers show
Series
  • xen/timers: Document and improve the representation of the timer heap metadata
Related show

Commit Message

Andrew Cooper March 29, 2019, 4:02 p.m. UTC
The {GET,SET}_HEAP_{SIZE,LIMIT}() macros implement some completely
undocumented pointer misuse to store the size and limit information.  In
practice, heap[0] is never a timer pointer, and used to stash the metadata
instead.

Extend the HEAP OPERATIONS comment to include this detail.  Introduce a
structure representing the heap metadata, and a static inline function to
perfom the type punning.

Replace all of the above macros with an equivelent expression involving the
heap_metadata() helper.  Note that I deliberately haven't rearranged the
surrounding code - this allows the correctness of the transformation to be
checked by confirming that the compiled binary is identical.

This also removes two cases of a macro argument with side effects, which only
worked correctly because the arguments were only evaluated once.

Finally, fix up the type of dummy_heap.  The old code functioned correctly,
but only by virtue of confusing a discrete object and a single-entry array.
Change its type to match the intended semantics, and drop the redundant
initialisation in timer_init().

No functional change.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
CC: George Dunlap <George.Dunlap@eu.citrix.com>
CC: Ian Jackson <ian.jackson@citrix.com>
CC: Jan Beulich <JBeulich@suse.com>
CC: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
CC: Stefano Stabellini <sstabellini@kernel.org>
CC: Tim Deegan <tim@xen.org>
CC: Wei Liu <wei.liu2@citrix.com>
CC: Julien Grall <julien.grall@arm.com>
---
 xen/common/timer.c | 59 ++++++++++++++++++++++++++++++------------------------
 1 file changed, 33 insertions(+), 26 deletions(-)

Comments

Jan Beulich March 29, 2019, 4:23 p.m. UTC | #1
>>> On 29.03.19 at 17:02, <andrew.cooper3@citrix.com> wrote:
> --- a/xen/common/timer.c
> +++ b/xen/common/timer.c
> @@ -45,18 +45,27 @@ DEFINE_PER_CPU(s_time_t, timer_deadline);
>  
>  
> /****************************************************************************
>   * HEAP OPERATIONS.
> + *
> + * Slot 0 of the heap is never a valid timer pointer, and instead holds the
> + * heap metadata.
>   */
>  
> -#define GET_HEAP_SIZE(_h)     ((int)(((u16 *)(_h))[0]))
> -#define SET_HEAP_SIZE(_h,_v)  (((u16 *)(_h))[0] = (u16)(_v))
> +struct heap_metadata {
> +    uint16_t size, limit;
> +};
> +
> +static struct heap_metadata *heap_metadata(struct timer **heap)
> +{
> +    /* Check that our type-punning doesn't overflow into heap[1] */
> +    BUILD_BUG_ON(sizeof(struct heap_metadata) > sizeof(struct timer *));
>  
> -#define GET_HEAP_LIMIT(_h)    ((int)(((u16 *)(_h))[1]))
> -#define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))
> +    return (struct heap_metadata *)&heap[0];
> +}
>  
>  /* Sink down element @pos of @heap. */
>  static void down_heap(struct timer **heap, int pos)
>  {
> -    int sz = GET_HEAP_SIZE(heap), nxt;
> +    int sz = heap_metadata(heap)->size, nxt;

While I realize that it'll alter generated code, I think this would be
a very good opportunity to convert various local variables to
unsigned int. But I won't insist, so with or without the extra change
Reviewed-by: Jan Beulich <jbeulich@suse.com>

Jan
Andrew Cooper March 29, 2019, 4:26 p.m. UTC | #2
On 29/03/2019 16:23, Jan Beulich wrote:
>>>> On 29.03.19 at 17:02, <andrew.cooper3@citrix.com> wrote:
>> --- a/xen/common/timer.c
>> +++ b/xen/common/timer.c
>> @@ -45,18 +45,27 @@ DEFINE_PER_CPU(s_time_t, timer_deadline);
>>  
>>  
>> /****************************************************************************
>>   * HEAP OPERATIONS.
>> + *
>> + * Slot 0 of the heap is never a valid timer pointer, and instead holds the
>> + * heap metadata.
>>   */
>>  
>> -#define GET_HEAP_SIZE(_h)     ((int)(((u16 *)(_h))[0]))
>> -#define SET_HEAP_SIZE(_h,_v)  (((u16 *)(_h))[0] = (u16)(_v))
>> +struct heap_metadata {
>> +    uint16_t size, limit;
>> +};
>> +
>> +static struct heap_metadata *heap_metadata(struct timer **heap)
>> +{
>> +    /* Check that our type-punning doesn't overflow into heap[1] */
>> +    BUILD_BUG_ON(sizeof(struct heap_metadata) > sizeof(struct timer *));
>>  
>> -#define GET_HEAP_LIMIT(_h)    ((int)(((u16 *)(_h))[1]))
>> -#define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))
>> +    return (struct heap_metadata *)&heap[0];
>> +}
>>  
>>  /* Sink down element @pos of @heap. */
>>  static void down_heap(struct timer **heap, int pos)
>>  {
>> -    int sz = GET_HEAP_SIZE(heap), nxt;
>> +    int sz = heap_metadata(heap)->size, nxt;
> While I realize that it'll alter generated code, I think this would be
> a very good opportunity to convert various local variables to
> unsigned int. But I won't insist, so with or without the extra change
> Reviewed-by: Jan Beulich <jbeulich@suse.com>

I know you were going to ask, but I'm not sufficiently confident with
being able to do that without error.  That is why I specifically called
out the check of no difference in the compiled binary.

Other changes are likely to happen at a future date.

~Andrew

Patch
diff mbox series

diff --git a/xen/common/timer.c b/xen/common/timer.c
index a6967c0..4ba010c 100644
--- a/xen/common/timer.c
+++ b/xen/common/timer.c
@@ -45,18 +45,27 @@  DEFINE_PER_CPU(s_time_t, timer_deadline);
 
 /****************************************************************************
  * HEAP OPERATIONS.
+ *
+ * Slot 0 of the heap is never a valid timer pointer, and instead holds the
+ * heap metadata.
  */
 
-#define GET_HEAP_SIZE(_h)     ((int)(((u16 *)(_h))[0]))
-#define SET_HEAP_SIZE(_h,_v)  (((u16 *)(_h))[0] = (u16)(_v))
+struct heap_metadata {
+    uint16_t size, limit;
+};
+
+static struct heap_metadata *heap_metadata(struct timer **heap)
+{
+    /* Check that our type-punning doesn't overflow into heap[1] */
+    BUILD_BUG_ON(sizeof(struct heap_metadata) > sizeof(struct timer *));
 
-#define GET_HEAP_LIMIT(_h)    ((int)(((u16 *)(_h))[1]))
-#define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))
+    return (struct heap_metadata *)&heap[0];
+}
 
 /* Sink down element @pos of @heap. */
 static void down_heap(struct timer **heap, int pos)
 {
-    int sz = GET_HEAP_SIZE(heap), nxt;
+    int sz = heap_metadata(heap)->size, nxt;
     struct timer *t = heap[pos];
 
     while ( (nxt = (pos << 1)) <= sz )
@@ -94,19 +103,19 @@  static void up_heap(struct timer **heap, int pos)
 /* Delete @t from @heap. Return TRUE if new top of heap. */
 static int remove_from_heap(struct timer **heap, struct timer *t)
 {
-    int sz = GET_HEAP_SIZE(heap);
+    int sz = heap_metadata(heap)->size;
     int pos = t->heap_offset;
 
     if ( unlikely(pos == sz) )
     {
-        SET_HEAP_SIZE(heap, sz-1);
+        heap_metadata(heap)->size = sz - 1;
         goto out;
     }
 
     heap[pos] = heap[sz];
     heap[pos]->heap_offset = pos;
 
-    SET_HEAP_SIZE(heap, --sz);
+    heap_metadata(heap)->size = --sz;
 
     if ( (pos > 1) && (heap[pos]->expires < heap[pos>>1]->expires) )
         up_heap(heap, pos);
@@ -121,13 +130,13 @@  static int remove_from_heap(struct timer **heap, struct timer *t)
 /* Add new entry @t to @heap. Return TRUE if new top of heap. */
 static int add_to_heap(struct timer **heap, struct timer *t)
 {
-    int sz = GET_HEAP_SIZE(heap);
+    int sz = heap_metadata(heap)->size;
 
     /* Fail if the heap is full. */
-    if ( unlikely(sz == GET_HEAP_LIMIT(heap)) )
+    if ( unlikely(sz == heap_metadata(heap)->limit) )
         return 0;
 
-    SET_HEAP_SIZE(heap, ++sz);
+    heap_metadata(heap)->size = ++sz;
     heap[sz] = t;
     t->heap_offset = sz;
     up_heap(heap, sz);
@@ -454,14 +463,14 @@  static void timer_softirq_action(void)
     if ( unlikely(ts->list != NULL) )
     {
         /* old_limit == (2^n)-1; new_limit == (2^(n+4))-1 */
-        int old_limit = GET_HEAP_LIMIT(heap);
+        int old_limit = heap_metadata(heap)->limit;
         int new_limit = ((old_limit + 1) << 4) - 1;
         struct timer **newheap = xmalloc_array(struct timer *, new_limit + 1);
         if ( newheap != NULL )
         {
             spin_lock_irq(&ts->lock);
             memcpy(newheap, heap, (old_limit + 1) * sizeof(*heap));
-            SET_HEAP_LIMIT(newheap, new_limit);
+            heap_metadata(newheap)->limit = new_limit;
             ts->heap = newheap;
             spin_unlock_irq(&ts->lock);
             if ( old_limit != 0 )
@@ -475,7 +484,7 @@  static void timer_softirq_action(void)
     now = NOW();
 
     /* Execute ready heap timers. */
-    while ( (GET_HEAP_SIZE(heap) != 0) &&
+    while ( (heap_metadata(heap)->size != 0) &&
             ((t = heap[1])->expires < now) )
     {
         remove_from_heap(heap, t);
@@ -501,7 +510,7 @@  static void timer_softirq_action(void)
 
     /* Find earliest deadline from head of linked list and top of heap. */
     deadline = STIME_MAX;
-    if ( GET_HEAP_SIZE(heap) != 0 )
+    if ( heap_metadata(heap)->size != 0 )
         deadline = heap[1]->expires;
     if ( (ts->list != NULL) && (ts->list->expires < deadline) )
         deadline = ts->list->expires;
@@ -545,7 +554,7 @@  static void dump_timerq(unsigned char key)
 
         printk("CPU%02d:\n", i);
         spin_lock_irqsave(&ts->lock, flags);
-        for ( j = 1; j <= GET_HEAP_SIZE(ts->heap); j++ )
+        for ( j = 1; j <= heap_metadata(ts->heap)->size; j++ )
             dump_timer(ts->heap[j], now);
         for ( t = ts->list, j = 0; t != NULL; t = t->list_next, j++ )
             dump_timer(t, now);
@@ -576,7 +585,7 @@  static void migrate_timers_from_cpu(unsigned int old_cpu)
         spin_lock(&old_ts->lock);
     }
 
-    while ( (t = GET_HEAP_SIZE(old_ts->heap)
+    while ( (t = heap_metadata(old_ts->heap)->size
              ? old_ts->heap[1] : old_ts->list) != NULL )
     {
         remove_entry(t);
@@ -599,7 +608,12 @@  static void migrate_timers_from_cpu(unsigned int old_cpu)
         cpu_raise_softirq(new_cpu, TIMER_SOFTIRQ);
 }
 
-static struct timer *dummy_heap;
+/*
+ * All CPUs initially share an empty dummy heap. Only those CPUs that
+ * are brought online will be dynamically allocated their own heap.
+ * The size/limit metadata are both 0 by being in .bss
+ */
+static struct timer *dummy_heap[1];
 
 static int cpu_callback(
     struct notifier_block *nfb, unsigned long action, void *hcpu)
@@ -612,7 +626,7 @@  static int cpu_callback(
     case CPU_UP_PREPARE:
         INIT_LIST_HEAD(&ts->inactive);
         spin_lock_init(&ts->lock);
-        ts->heap = &dummy_heap;
+        ts->heap = dummy_heap;
         break;
 
     case CPU_DOWN_PREPARE:
@@ -640,13 +654,6 @@  void __init timer_init(void)
 
     open_softirq(TIMER_SOFTIRQ, timer_softirq_action);
 
-    /*
-     * All CPUs initially share an empty dummy heap. Only those CPUs that
-     * are brought online will be dynamically allocated their own heap.
-     */
-    SET_HEAP_SIZE(&dummy_heap, 0);
-    SET_HEAP_LIMIT(&dummy_heap, 0);
-
     cpu_callback(&cpu_nfb, CPU_UP_PREPARE, cpu);
     register_cpu_notifier(&cpu_nfb);