Re: [Xenomai-core] Re: [patch] static buffer for timer-bheap

[Jan Kiszka <jan.kiszka@domain.hid>]

[-- Attachment #1.1: Type: text/plain, Size: 1586 bytes --]

Jan Kiszka wrote:
> Gilles Chanteperdrix wrote:
>> Jan Kiszka wrote:
>>  > Gilles Chanteperdrix wrote:
>>  > > bheap_destroy allow
>>  > > setting the bheap_t structure to an invalid value which, in turn, allow
>>  > > helping upper layers in catching invalid uses of the bheap after its
>>  > > destruction.
>>  > 
>>  > Ok, we could make bheap_destroy pop up under XENO_OPT_DEBUG. We may then
>>  > also add assertions to the bheap functions themselves to check for
>>  > invalid usage.
>>
>> The checkings are already there, if you do not remove
>> bheap_destroy. They are unconditionnal, because I find such checkings way
>> too important to be optimized out.
> 
> Sorry, I might be blind, but how do bheap_gethead, bheap_insert, or
> bheap_delete detect that heap->last or heap->sz became 0 after
> bheap_destroy?
> 
> Given that this is code to be inlined and heavily used, we should really
> take care for size and efficiency on production systems, even if it's
> about a few bytes here. But I also agree that verbose(!) checking
> (XENO_ASSERT/XENO_BUGON) is very useful during development.

Ok, I understood that consistency checks can come for zero price when
fixing a tiny bug in bheap_destroy. This is done in the attached
revision of my patch, and I kept bheap_destroy therefore.

I also added XENO_BUGON to bheap_gethead, bheap_insert, and bheap_delete
in case CONFIG_XENO_OPT_DEBUG_BHEAP is set (which is the case now for
CONFIG_XENO_OPT_DEBUG - it's a cheap test).

Be warned, this patch is only compile-tested, I'm in a hurry.

Jan

[-- Attachment #1.2: bheap-init-v3.patch --]
[-- Type: text/plain, Size: 10002 bytes --]

Index: ksrc/nucleus/Kconfig
===================================================================
--- ksrc/nucleus/Kconfig	(revision 1144)
+++ ksrc/nucleus/Kconfig	(working copy)
@@ -145,6 +145,10 @@ config XENO_OPT_DEBUG_QUEUES
 	operations of the Xenomai core. It adds even more runtime
 	overhead then CONFIG_XENO_OPT_DEBUG, use with care.
 
+config XENO_OPT_DEBUG_BHEAP
+	bool
+	default y if XENO_OPT_DEBUG
+
 config XENO_OPT_WATCHDOG
 	bool "Watchdog support"
 	default n
Index: ksrc/nucleus/pod.c
===================================================================
--- ksrc/nucleus/pod.c	(revision 1144)
+++ ksrc/nucleus/pod.c	(working copy)
@@ -433,22 +433,11 @@ int xnpod_init(xnpod_t *pod, int minpri,
 #ifdef CONFIG_XENO_OPT_TIMING_PERIODIC
         unsigned n;
 
-        for (n = 0; n < XNTIMER_WHEELSIZE; n++) {
-            err = -xntlist_init(&pod->sched[cpu].timerwheel[n]);
-
-            if (err) {
-                xnheap_destroy(&kheap, &xnpod_flush_heap, NULL);
-                goto fail;
-            }
-        }
+        for (n = 0; n < XNTIMER_WHEELSIZE; n++)
+            xntlist_init(&pod->sched[cpu].timerwheel[n]);
 #endif /* CONFIG_XENO_OPT_TIMING_PERIODIC */
 
-        err = -xntimerq_init(&pod->sched[cpu].timerqueue);
-
-        if (err) {
-            xnheap_destroy(&kheap, &xnpod_flush_heap, NULL);
-            goto fail;
-        }
+        xntimerq_init(&pod->sched[cpu].timerqueue);
     }
 
     for (cpu = 0; cpu < nr_cpus; ++cpu) {
@@ -585,15 +574,8 @@ void xnpod_shutdown(int xtype)
 
     __setbits(nkpod->status, XNPIDLE);
 
-    for (cpu = 0; cpu < xnarch_num_online_cpus(); cpu++) {
-#ifdef CONFIG_XENO_OPT_TIMING_PERIODIC
-        unsigned n;
-
-        for (n = 0; n < XNTIMER_WHEELSIZE; n++)
-            xntlist_destroy(&nkpod->sched[cpu].timerwheel[n]);
-#endif /* CONFIG_XENO_OPT_TIMING_PERIODIC */
+    for (cpu = 0; cpu < xnarch_num_online_cpus(); cpu++)
         xntimerq_destroy(&nkpod->sched[cpu].timerqueue);
-    }
 
     xnlock_put_irqrestore(&nklock, s);
 
Index: ksrc/nucleus/Config.in
===================================================================
--- ksrc/nucleus/Config.in	(revision 1144)
+++ ksrc/nucleus/Config.in	(working copy)
@@ -32,6 +32,7 @@ if [ "$CONFIG_XENO_OPT_NUCLEUS" != "n" ]
 	bool 'Debug support' CONFIG_XENO_OPT_DEBUG
 	if [ "$CONFIG_XENO_OPT_DEBUG" = "y" ]; then
 		bool 'Queue Debugging support' CONFIG_XENO_OPT_DEBUG_QUEUES
+		define_bool CONFIG_XENO_OPT_DEBUG_BHEAP y
 	fi
 	bool 'Watchdog support' CONFIG_XENO_OPT_WATCHDOG
 
Index: include/nucleus/bheap.h
===================================================================
--- include/nucleus/bheap.h	(revision 1144)
+++ include/nucleus/bheap.h	(working copy)
@@ -21,6 +21,7 @@
 #define _XENO_NUCLEUS_BHEAP_H
 
 #include <nucleus/compiler.h>
+#include <nucleus/assert.h>
 
 /* Priority queue implementation, using a binary heap. */
 
@@ -43,10 +44,28 @@ typedef struct bheaph {
 typedef struct bheap {
     unsigned sz;
     unsigned last;
-    bheaph_t **elems;
+    bheaph_t *elems[1]; /* only padding, indexing starts at 1 */
 } bheap_t;
 
-static inline bheaph_t *bheap_gethead(bheap_t *heap)
+#define DECLARE_BHEAP_CONTAINER(name, sz) \
+    struct { \
+        bheap_t bheap; \
+        bheaph_t *elems[sz]; \
+    } name
+
+#ifdef CONFIG_XENO_OPT_DEBUG_BHEAP
+#define BHEAP_CHECK(heap)   XENO_BUGON(BHEAP, ((heap)->sz == 0))
+#else /* !CONFIG_XENO_OPT_DEBUG_BHEAP */
+#define BHEAP_CHECK(heap)   do { } while (0)
+#endif /* CONFIG_XENO_OPT_DEBUG_BHEAP */
+
+#define bheap_gethead(heap) \
+({ \
+    BHEAP_CHECK(heap); \
+    __internal_bheap_gethead(heap); \
+})
+
+static inline bheaph_t *__internal_bheap_gethead(bheap_t *heap)
 {
     if (heap->last == 1)
         return NULL;
@@ -68,26 +87,16 @@ static inline bheaph_t *bheaph_child(bhe
     return likely(pos < heap->last) ? heap->elems[pos] : NULL;
 }
 
-static inline int bheap_init(bheap_t *heap, unsigned sz)
+static inline void bheap_init(bheap_t *heap, unsigned sz)
 {
     heap->sz = sz;
     heap->last = 1;
-    heap->elems = (bheaph_t **) xnarch_sysalloc(sz * sizeof(void *));
-
-    if (!heap->elems)
-        return ENOMEM;
-
-    /* start indexing at 1. */
-    heap->elems -= 1;
-
-    return 0;
 }
 
 static inline void bheap_destroy(bheap_t *heap)
-{    
-    xnarch_sysfree(heap->elems + 1, heap->sz * sizeof(void *));
-    heap->last = 0;
+{
     heap->sz = 0;
+    heap->last = 1;
 }
 
 static inline void bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
@@ -115,7 +124,7 @@ static inline void bheap_down(bheap_t *h
     for (;;) {
         left = bheaph_child(heap, holder, 0);
         right = bheaph_child(heap, holder, 1);
-        
+
         if (left && right)
             minchild = bheaph_lt(left, right) ? left : right;
         else
@@ -128,7 +137,13 @@ static inline void bheap_down(bheap_t *h
     }
 }
 
-static inline int bheap_insert(bheap_t *heap, bheaph_t *holder)
+#define bheap_insert(heap, holder) \
+({ \
+    BHEAP_CHECK(heap); \
+    __internal_bheap_insert(heap, holder); \
+})
+
+static inline int __internal_bheap_insert(bheap_t *heap, bheaph_t *holder)
 {
     if (heap->last == heap->sz + 1)
         return EBUSY;
@@ -140,13 +155,16 @@ static inline int bheap_insert(bheap_t *
     return 0;
 }
 
-static inline int bheap_delete(bheap_t *heap, bheaph_t *holder)
+#define bheap_delete(heap, holder) \
+do { \
+    BHEAP_CHECK(heap); \
+    __internal_bheap_delete(heap, holder); \
+} while (0)
+
+static inline void __internal_bheap_delete(bheap_t *heap, bheaph_t *holder)
 {
     bheaph_t *lasth;
-    
-    if (heap->last == 1)
-        return EINVAL;
-    
+
     --heap->last;
     if (heap->last > 1) {
         lasth = heap->elems[heap->last];
@@ -154,8 +172,6 @@ static inline int bheap_delete(bheap_t *
         bheaph_pos(lasth) = bheaph_pos(holder);
         bheap_down(heap, lasth);
     }
-   
-    return 0;
 }
 
 static inline bheaph_t *bheap_get(bheap_t *heap)
Index: include/nucleus/timer.h
===================================================================
--- include/nucleus/timer.h	(revision 1144)
+++ include/nucleus/timer.h	(working copy)
@@ -58,11 +58,10 @@ typedef struct {
     ((xntlholder_t *)(((char *)laddr) - offsetof(xntlholder_t, link)))
 
 } xntlholder_t;
-#define xntlholder_date(h)       ((h)->key)
-#define xntlholder_prio(h)       ((h)->prio)
-#define xntlholder_init(h)       inith(&(h)->link)
-#define xntlist_init(q)       (initq(q),0)
-#define xntlist_destroy(q)    do { } while (0)
+#define xntlholder_date(h)      ((h)->key)
+#define xntlholder_prio(h)      ((h)->prio)
+#define xntlholder_init(h)      inith(&(h)->link)
+#define xntlist_init(q)         initq(q)
 #define xntlist_head(q)                         \
     ({ xnholder_t *_h = getheadq(q);            \
         !_h ? NULL : link2tlholder(_h);         \
@@ -71,7 +70,7 @@ typedef struct {
 static inline void xntlist_insert(xnqueue_t *q, xntlholder_t *holder)
 {
     xnholder_t *p;
-    
+
     /* Insert the new timer at the proper place in the single
        queue managed when running in aperiodic mode. O(N) here,
        but users of the aperiodic mode need to pay a price for
@@ -82,7 +81,7 @@ static inline void xntlist_insert(xnqueu
             (holder->key == link2tlholder(p)->key &&
              holder->prio <= link2tlholder(p)->prio))
             break;
-        
+
     insertq(q,p->next,&holder->link);
 }
 
@@ -94,12 +93,12 @@ typedef bheaph_t xntimerh_t;
 #define xntimerh_date(h)       bheaph_key(h)
 #define xntimerh_prio(h)       bheaph_prio(h)
 #define xntimerh_init(h)       bheaph_init(h)
-typedef bheap_t xntimerq_t;
-#define xntimerq_init(q)       bheap_init((q), CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY)
-#define xntimerq_destroy(q)    bheap_destroy(q)
-#define xntimerq_head(q)       bheap_gethead(q)
-#define xntimerq_insert(q, h)  bheap_insert((q),(h))
-#define xntimerq_remove(q, h)  bheap_delete((q),(h))
+typedef DECLARE_BHEAP_CONTAINER(xntimerq_t, CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY);
+#define xntimerq_init(q)       bheap_init(&(q)->bheap, CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY)
+#define xntimerq_destroy(q)    bheap_destroy(&(q)->bheap)
+#define xntimerq_head(q)       bheap_gethead(&(q)->bheap)
+#define xntimerq_insert(q, h)  bheap_insert(&(q)->bheap,(h))
+#define xntimerq_remove(q, h)  bheap_delete(&(q)->bheap,(h))
 
 #else /* CONFIG_XENO_OPT_TIMER_LIST */
 typedef xntlholder_t xntimerh_t;
@@ -108,7 +107,7 @@ typedef xntlholder_t xntimerh_t;
 #define xntimerh_init(h)       xntlholder_init(h)
 typedef xnqueue_t xntimerq_t;
 #define xntimerq_init(q)       xntlist_init(q)
-#define xntimerq_destroy(q)    xntlist_destroy(q)
+#define xntimerq_destroy(q)    do { } while (0)
 #define xntimerq_head(q)       xntlist_head(q)
 #define xntimerq_insert(q,h)   xntlist_insert((q),(h))
 #define xntimerq_remove(q, h)  xntlist_remove((q),(h))
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 1144)
+++ ChangeLog	(working copy)
@@ -1,3 +1,10 @@
+2006-06-02  Jan Kiszka  <jan.kiszka@domain.hid>
+
+	* include/nucleus/{bheap.h,timer.h}, ksrc/nucleus/pod.c:
+	Combine bheap head with element buffer, fix consistency checks
+	and additionally make use of XENO_BUGON. Simplify pod init and
+	cleanup of timer structures.
+
 2006-05-23  Gilles Chanteperdrix  <gilles.chanteperdrix@xenomai.org>
 
 	* ksrc/arch/i386/nmi.c: Fix alignement for gcc-4.1.
@@ -14,7 +21,7 @@
 
 	* ksrc/arch/arm/patches: Upgrade to 2.6.1{4,5}-1.3-04.
 
-2006-05-19  Jan Kiszka  <jan.kiszka@domain.hid>
+2006-05-19  Jan Kiszka  <jan.kiszka@domain.hid>
 
 	* src/testsuite/latency/latency.c: Add pid to registered names
 	allowing multiple instances of latency to run. Add -c switch to

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]