@@ -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);
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(-)