[Xen-changelog] [xen staging] xen/timers: Document and improve the representation of the timer heap metadata

[patchbot@xxxxxxx]

commit 12381e20b5c2cb2f54601bef47c4f6e43acf3833
Author:     Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
AuthorDate: Fri Mar 29 13:32:09 2019 +0000
Commit:     Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
CommitDate: Fri Mar 29 18:28:21 2019 +0000

    xen/timers: Document and improve the representation of the timer heap 
metadata
    
    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@xxxxxxxxxx>
    Reviewed-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/timer.c | 59 ++++++++++++++++++++++++++++++------------------------
 1 file changed, 33 insertions(+), 26 deletions(-)

diff --git a/xen/common/timer.c b/xen/common/timer.c
index 376581bd54..98f2c4800c 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_UP_CANCELED:
     case CPU_DEAD:
@@ -636,13 +650,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);
 
--
generated by git-patchbot for /home/xen/git/xen.git#staging

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/xen-changelog