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

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

[Jan Kiszka]

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

Hi,

this patch moves the heap for scalable timer queues into the xnpod_t
structure instead of allocating it dynamically. This simplifies the pod
initialisation and cleanup, which was not fully robust in this regard
anyway. If a pod is now considered too large (but we are discussion
kbytes here), allocating its buffer via xnarch_sysalloc would be an option.

In case this patch is acceptable, I would suggest merging it before 2.2
due to the contained (minor) fix.

Jan

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: bheap-init.patch --]
[-- Type: text/x-patch; name="bheap-init.patch", Size: 7251 bytes --]

Index: ksrc/nucleus/pod.c
===================================================================
--- ksrc/nucleus/pod.c	(Revision 1144)
+++ ksrc/nucleus/pod.c	(Arbeitskopie)
@@ -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) {
@@ -547,7 +536,6 @@ void xnpod_shutdown(int xtype)
 {
     xnholder_t *holder, *nholder;
     xnthread_t *thread;
-    unsigned cpu;
     spl_t s;
 
     xnlock_get_irqsave(&nklock, s);
@@ -585,16 +573,6 @@ 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 */
-        xntimerq_destroy(&nkpod->sched[cpu].timerqueue);
-    }
-
     xnlock_put_irqrestore(&nklock, s);
 
 #ifdef CONFIG_XENO_OPT_REGISTRY
Index: include/nucleus/bheap.h
===================================================================
--- include/nucleus/bheap.h	(Revision 1144)
+++ include/nucleus/bheap.h	(Arbeitskopie)
@@ -43,9 +43,15 @@ 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;
 
+#define DECLARE_BHEAP_CONTAINER(name, sz) \
+    struct { \
+        bheap_t bheap; \
+        bheaph_t elems[sz]; \
+    } name
+
 static inline bheaph_t *bheap_gethead(bheap_t *heap)
 {
     if (heap->last == 1)
@@ -68,26 +74,10 @@ 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;
 }
 
 static inline void bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
@@ -115,7 +105,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
@@ -143,10 +133,10 @@ static inline int bheap_insert(bheap_t *
 static inline int 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,7 +144,7 @@ static inline int bheap_delete(bheap_t *
         bheaph_pos(lasth) = bheaph_pos(holder);
         bheap_down(heap, lasth);
     }
-   
+
     return 0;
 }
 
Index: include/nucleus/timer.h
===================================================================
--- include/nucleus/timer.h	(Revision 1144)
+++ include/nucleus/timer.h	(Arbeitskopie)
@@ -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,14 @@ 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 struct {
+    bheap_t bheap;
+    bheaph_t __buffer[CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY];
+} xntimerq_t;
+#define xntimerq_init(q)       bheap_init(&(q)->bheap, CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY)
+#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;
Index: ChangeLog
===================================================================
--- ChangeLog	(Revision 1144)
+++ ChangeLog	(Arbeitskopie)
@@ -1,3 +1,9 @@
+2006-06-01  Jan Kiszka  <jan.kiszka@domain.hid>
+
+	* include/nucleus/{bheap.h,timer.h}, ksrc/nucleus/pod.c:
+	Move timer heap into xnpod_t structure, simplify pod init and
+	cleanup.
+
 2006-05-23  Gilles Chanteperdrix  <gilles.chanteperdrix@xenomai.org>
 
 	* ksrc/arch/i386/nmi.c: Fix alignement for gcc-4.1.
@@ -14,7 +20,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: 249 bytes --]

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

[Gilles Chanteperdrix]

Jan Kiszka wrote:
 > Hi,
 > 
 > this patch moves the heap for scalable timer queues into the xnpod_t
 > structure instead of allocating it dynamically. This simplifies the pod
 > initialisation and cleanup, which was not fully robust in this regard
 > anyway. If a pod is now considered too large (but we are discussion
 > kbytes here), allocating its buffer via xnarch_sysalloc would be an option.
 > 
 > In case this patch is acceptable, I would suggest merging it before 2.2
 > due to the contained (minor) fix.

Since this memory is specific to the data structure, its allocation
seems better by the data structure functions. It also make the binary
heap structure reusable for other purposes.

Could you explain why the current scheme is not robust ?

-- 


					    Gilles Chanteperdrix.

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

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1377 bytes --]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>  > Hi,
>  > 
>  > this patch moves the heap for scalable timer queues into the xnpod_t
>  > structure instead of allocating it dynamically. This simplifies the pod
>  > initialisation and cleanup, which was not fully robust in this regard
>  > anyway. If a pod is now considered too large (but we are discussion
>  > kbytes here), allocating its buffer via xnarch_sysalloc would be an option.
>  > 
>  > In case this patch is acceptable, I would suggest merging it before 2.2
>  > due to the contained (minor) fix.
> 
> Since this memory is specific to the data structure, its allocation
> seems better by the data structure functions. It also make the binary
> heap structure reusable for other purposes.

That's what I added the DECLARE_BHEAP_CONTAINER macro for. Sorry, did
not mention this.

The idea is to leave the allocation policy up to the user instead of
enforcing it in the bheap layer. The current approach also implicitly
excludes its usage from RT contexts, BTW.

> 
> Could you explain why the current scheme is not robust ?
> 

Given a SMP system where the allocation fails right in the middle of the
per-CPU loop [1], cleanup will not be performed for already allocated heaps.

Jan


[1]http://www.rts.uni-hannover.de/xenomai/lxr/source/ksrc/nucleus/pod.c?v=SVN-trunk#L432


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

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

[Gilles Chanteperdrix]

Jan Kiszka wrote:
 > Gilles Chanteperdrix wrote:
 > > Jan Kiszka wrote:
 > >  > Hi,
 > >  > 
 > >  > this patch moves the heap for scalable timer queues into the xnpod_t
 > >  > structure instead of allocating it dynamically. This simplifies the pod
 > >  > initialisation and cleanup, which was not fully robust in this regard
 > >  > anyway. If a pod is now considered too large (but we are discussion
 > >  > kbytes here), allocating its buffer via xnarch_sysalloc would be an option.
 > >  > 
 > >  > In case this patch is acceptable, I would suggest merging it before 2.2
 > >  > due to the contained (minor) fix.
 > > 
 > > Since this memory is specific to the data structure, its allocation
 > > seems better by the data structure functions. It also make the binary
 > > heap structure reusable for other purposes.
 > 
 > That's what I added the DECLARE_BHEAP_CONTAINER macro for. Sorry, did
 > not mention this.
 > 
 > The idea is to leave the allocation policy up to the user instead of
 > enforcing it in the bheap layer. The current approach also implicitly
 > excludes its usage from RT contexts, BTW.
 > 
 > > 
 > > Could you explain why the current scheme is not robust ?
 > > 
 > 
 > Given a SMP system where the allocation fails right in the middle of the
 > per-CPU loop [1], cleanup will not be performed for already allocated heaps.

You are right.

-- 


					    Gilles Chanteperdrix.

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

[Gilles Chanteperdrix]

Jan Kiszka wrote:
 > (...)
 > +#define DECLARE_BHEAP_CONTAINER(name, sz) \
 > +    struct { \
 > +        bheap_t bheap; \
 > +        bheaph_t elems[sz]; \
 > +    } name
 > +

Don't you mean bheaph_t *elems[sz] ?

 > (...)
 > +typedef struct {
 > +    bheap_t bheap;
 > +    bheaph_t __buffer[CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY];
 > +} xntimerq_t;

Same remark. And why not using the macro here ?

I would also prefer passing the bheaph_t** storage to bheap_init, and
conserve bheap_destroy (with a callback called with the bheap_t**
storage) in case the storage was dynamically allocated by the caller.

-- 


					    Gilles Chanteperdrix.

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

[Jan Kiszka]

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

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>  > (...)
>  > +#define DECLARE_BHEAP_CONTAINER(name, sz) \
>  > +    struct { \
>  > +        bheap_t bheap; \
>  > +        bheaph_t elems[sz]; \
>  > +    } name
>  > +
> 
> Don't you mean bheaph_t *elems[sz] ?

Yep.

> 
>  > (...)
>  > +typedef struct {
>  > +    bheap_t bheap;
>  > +    bheaph_t __buffer[CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY];
>  > +} xntimerq_t;
> 
> Same remark. And why not using the macro here ?

Indeed. Ugly late-night hack, improved version attached.

> 
> I would also prefer passing the bheaph_t** storage to bheap_init, and
> conserve bheap_destroy (with a callback called with the bheap_t**
> storage) in case the storage was dynamically allocated by the caller.

Do you have a concrete usage scenario in mind where this would be
required? I would rather bet that potential callers of bheap_destroy
know very well when some buffer is to be released. Looks at bit like
overkill unless someone has the real need to mix dynamically with
statically allocated bheaps.

Jan

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

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) {
@@ -547,7 +536,6 @@ void xnpod_shutdown(int xtype)
 {
     xnholder_t *holder, *nholder;
     xnthread_t *thread;
-    unsigned cpu;
     spl_t s;
 
     xnlock_get_irqsave(&nklock, s);
@@ -585,16 +573,6 @@ 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 */
-        xntimerq_destroy(&nkpod->sched[cpu].timerqueue);
-    }
-
     xnlock_put_irqrestore(&nklock, s);
 
 #ifdef CONFIG_XENO_OPT_REGISTRY
Index: include/nucleus/bheap.h
===================================================================
--- include/nucleus/bheap.h	(revision 1144)
+++ include/nucleus/bheap.h	(working copy)
@@ -43,9 +43,15 @@ 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;
 
+#define DECLARE_BHEAP_CONTAINER(name, sz) \
+    struct { \
+        bheap_t bheap; \
+        bheaph_t *elems[sz]; \
+    } name
+
 static inline bheaph_t *bheap_gethead(bheap_t *heap)
 {
     if (heap->last == 1)
@@ -68,26 +74,10 @@ 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;
 }
 
 static inline void bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
@@ -115,7 +105,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
@@ -143,10 +133,10 @@ static inline int bheap_insert(bheap_t *
 static inline int 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,7 +144,7 @@ static inline int bheap_delete(bheap_t *
         bheaph_pos(lasth) = bheaph_pos(holder);
         bheap_down(heap, lasth);
     }
-   
+
     return 0;
 }
 
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,11 @@ 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_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;
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 1144)
+++ ChangeLog	(working copy)
@@ -1,3 +1,9 @@
+2006-06-02  Jan Kiszka  <jan.kiszka@domain.hid>
+
+	* include/nucleus/{bheap.h,timer.h}, ksrc/nucleus/pod.c:
+	Move timer heap into xnpod_t structure, simplify pod init and
+	cleanup.
+
 2006-05-23  Gilles Chanteperdrix  <gilles.chanteperdrix@xenomai.org>
 
 	* ksrc/arch/i386/nmi.c: Fix alignement for gcc-4.1.
@@ -14,7 +20,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 --]

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

[Gilles Chanteperdrix]

Jan Kiszka wrote:
 > Gilles Chanteperdrix wrote:
 > > I would also prefer passing the bheaph_t** storage to bheap_init, and
 > > conserve bheap_destroy (with a callback called with the bheap_t**
 > > storage) in case the storage was dynamically allocated by the caller.
 > 
 > Do you have a concrete usage scenario in mind where this would be
 > required? I would rather bet that potential callers of bheap_destroy
 > know very well when some buffer is to be released. Looks at bit like
 > overkill unless someone has the real need to mix dynamically with
 > statically allocated bheaps.

Requesting a bheaph_t ** to be passed to bheap_init is type-safe and
would have caught the kind of mistake you have done. 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.

It is a low price to pay to make the interface a bit safer.

-- 


					    Gilles Chanteperdrix.

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

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1474 bytes --]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>  > Gilles Chanteperdrix wrote:
>  > > I would also prefer passing the bheaph_t** storage to bheap_init, and
>  > > conserve bheap_destroy (with a callback called with the bheap_t**
>  > > storage) in case the storage was dynamically allocated by the caller.
>  > 
>  > Do you have a concrete usage scenario in mind where this would be
>  > required? I would rather bet that potential callers of bheap_destroy
>  > know very well when some buffer is to be released. Looks at bit like
>  > overkill unless someone has the real need to mix dynamically with
>  > statically allocated bheaps.
> 
> Requesting a bheaph_t ** to be passed to bheap_init is type-safe and
> would have caught the kind of mistake you have done.

But I also did not use the macro, which avoids such mistakes now.

> 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.

> 
> It is a low price to pay to make the interface a bit safer.
> 

The price is also larger code in every heap runtime function due to the
additional indirection. I still vote for the combined structure and to
give its allocation completely in user hand.

Jan


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

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

[Gilles Chanteperdrix]

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.

-- 


					    Gilles Chanteperdrix.

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

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1081 bytes --]

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.

Jan


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

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

[Jan Kiszka]

[-- 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 --]

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

[Gilles Chanteperdrix]

[-- Attachment #1: message body and .signature --]
[-- Type: text/plain, Size: 214 bytes --]

Jan Kiszka wrote:
 > Be warned, this patch is only compile-tested, I'm in a hurry.

I tested the lightly modified version attached and it works. Do you
agree with my changes ?

-- 


					    Gilles Chanteperdrix.

[-- Attachment #2: xeno-bheap-init-v4.diff --]
[-- Type: text/plain, Size: 10097 bytes --]

Index: ksrc/nucleus/Kconfig
===================================================================
--- ksrc/nucleus/Kconfig	(revision 1146)
+++ ksrc/nucleus/Kconfig	(working copy)
@@ -145,6 +145,10 @@
 	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 1146)
+++ ksrc/nucleus/pod.c	(working copy)
@@ -433,22 +433,11 @@
 #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 @@
 
     __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 1146)
+++ ksrc/nucleus/Config.in	(working copy)
@@ -32,6 +32,7 @@
 	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 1146)
+++ 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,29 @@
 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_t *_bheap = &(heap)->bheap;           \
+    BHEAP_CHECK(_bheap);                        \
+    __internal_bheap_gethead(_bheap);           \
+})
+
+static inline bheaph_t *__internal_bheap_gethead(bheap_t *heap)
 {
     if (heap->last == 1)
         return NULL;
@@ -68,26 +88,20 @@
     return likely(pos < heap->last) ? heap->elems[pos] : NULL;
 }
 
-static inline int bheap_init(bheap_t *heap, unsigned sz)
+#define bheap_init(heap, sz) __internal_bheap_init(&(heap)->bheap, sz)
+
+static inline void __internal_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;
+#define bheap_destroy(heap) __internal_bheap_destroy(&(heap)->bheap)
 
-    /* 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;
+static inline void __internal_bheap_destroy(bheap_t *heap)
+{
     heap->sz = 0;
+    heap->last = 1;
 }
 
 static inline void bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
@@ -115,7 +129,7 @@
     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 +142,14 @@
     }
 }
 
-static inline int bheap_insert(bheap_t *heap, bheaph_t *holder)
+#define bheap_insert(heap, holder)              \
+({                                              \
+    bheap_t *_bheap = &(heap)->bheap;           \
+    BHEAP_CHECK(_bheap);                        \
+    __internal_bheap_insert(_bheap, holder);    \
+})
+
+static inline int __internal_bheap_insert(bheap_t *heap, bheaph_t *holder)
 {
     if (heap->last == heap->sz + 1)
         return EBUSY;
@@ -140,32 +161,46 @@
     return 0;
 }
 
-static inline int bheap_delete(bheap_t *heap, bheaph_t *holder)
+#define bheap_delete(heap, holder)              \
+({                                              \
+    bheap_t *_bheap = &(heap)->bheap;           \
+    BHEAP_CHECK(_bheap);                        \
+    __internal_bheap_delete(_bheap, holder);    \
+})
+
+static inline int __internal_bheap_delete(bheap_t *heap, bheaph_t *holder)
 {
     bheaph_t *lasth;
-    
-    if (heap->last == 1)
+
+    if (bheaph_pos(holder) >= heap->last)
         return EINVAL;
-    
+
     --heap->last;
-    if (heap->last > 1) {
+    if (heap->last != bheaph_pos(holder)) {
         lasth = heap->elems[heap->last];
         heap->elems[bheaph_pos(holder)] = lasth;
         bheaph_pos(lasth) = bheaph_pos(holder);
         bheap_down(heap, lasth);
     }
-   
+
     return 0;
 }
 
-static inline bheaph_t *bheap_get(bheap_t *heap)
+#define bheap_get(heap)                         \
+({                                              \
+    bheap_t *_bheap = &(heap)->bheap;           \
+    BHEAP_CHECK(_bheap);                        \
+    __internal_bheap_get(_bheap, holder);       \
+})
+
+static inline bheaph_t *__internal_bheap_get(bheap_t *heap)
 {
-    bheaph_t *holder = bheap_gethead(heap);
+    bheaph_t *holder = __internal_bheap_gethead(heap);
 
     if (!holder)
         return NULL;
 
-    bheap_delete(heap, holder);
+    __internal_bheap_delete(heap, holder);
 
     return holder;
 }
Index: include/nucleus/timer.h
===================================================================
--- include/nucleus/timer.h	(revision 1146)
+++ include/nucleus/timer.h	(working copy)
@@ -58,11 +58,10 @@
     ((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 @@
 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 @@
             (holder->key == link2tlholder(p)->key &&
              holder->prio <= link2tlholder(p)->prio))
             break;
-        
+
     insertq(q,p->next,&holder->link);
 }
 
@@ -94,7 +93,7 @@
 #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;
+typedef DECLARE_BHEAP_CONTAINER(xntimerq_t, CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY);
 #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)
@@ -108,7 +107,7 @@
 #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 1146)
+++ 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

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

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 294 bytes --]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>  > Be warned, this patch is only compile-tested, I'm in a hurry.
> 
> I tested the lightly modified version attached and it works. Do you
> agree with my changes ?

Yes, good point. Makes the container concept more consistent.

Jan


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