libevent: Protect integer multiplications (min_heap)

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

libevent: Protect integer multiplications (min_heap)

Tobias Stoeckmann-5
I would like to protect min_heap_push against integer overflows,
which could either be triggered on a 64 bit system with massive
amounts of RAM (to overflow s->n) or on a 32 bit system with tight
memory layout (overflowing a * sizeof *p).

Both cases are basically not possible to be triggered, but I prefer
to have reallocarray in place to be sure about it.

Okay?

Index: min_heap.h
===================================================================
RCS file: /cvs/src/lib/libevent/min_heap.h,v
retrieving revision 1.3
diff -u -p -u -p -r1.3 min_heap.h
--- min_heap.h 29 Oct 2014 22:47:29 -0000 1.3
+++ min_heap.h 16 Apr 2019 18:26:11 -0000
@@ -65,7 +65,7 @@ struct event* min_heap_top(min_heap_t* s
 
 int min_heap_push(min_heap_t* s, struct event* e)
 {
-    if(min_heap_reserve(s, s->n + 1))
+    if(s->n == UINT32_MAX || min_heap_reserve(s, s->n + 1))
         return -1;
     min_heap_shift_up_(s, s->n++, e);
     return 0;
@@ -112,7 +112,7 @@ int min_heap_reserve(min_heap_t* s, unsi
         unsigned a = s->a ? s->a * 2 : 8;
         if(a < n)
             a = n;
-        if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
+        if((p = reallocarray(s->p, a, sizeof *p)) == NULL)
             return -1;
         s->p = p;
         s->a = a;

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Theo de Raadt-2
Reading this min_heap.h code for the first time, I shuddered because it
reminded me of the exploit mitigation mechanism in openssl which prevent
heartbleed from being exploitable in the presence of our fine otto
malloc.

It is a deferred deallocation mechanism *precisely* what prevents bugs
from being detected.

This code should be largely deleted, it shold properly allocate a new
randomly-placed object with protection for every transation, and when
completed free it into the void.

Yes malloc may not be cheap on all systems.  But rolling through this
code to reuse a previously used object *after memory damage* is partly
the fault of the author of this layer.

So the diff presented falls short of what should be done here;
insufficient lines deleted.

> I would like to protect min_heap_push against integer overflows,
> which could either be triggered on a 64 bit system with massive
> amounts of RAM (to overflow s->n) or on a 32 bit system with tight
> memory layout (overflowing a * sizeof *p).
>
> Both cases are basically not possible to be triggered, but I prefer
> to have reallocarray in place to be sure about it.
>
> Okay?
>
> Index: min_heap.h
> ===================================================================
> RCS file: /cvs/src/lib/libevent/min_heap.h,v
> retrieving revision 1.3
> diff -u -p -u -p -r1.3 min_heap.h
> --- min_heap.h 29 Oct 2014 22:47:29 -0000 1.3
> +++ min_heap.h 16 Apr 2019 18:26:11 -0000
> @@ -65,7 +65,7 @@ struct event* min_heap_top(min_heap_t* s
>  
>  int min_heap_push(min_heap_t* s, struct event* e)
>  {
> -    if(min_heap_reserve(s, s->n + 1))
> +    if(s->n == UINT32_MAX || min_heap_reserve(s, s->n + 1))
>          return -1;
>      min_heap_shift_up_(s, s->n++, e);
>      return 0;
> @@ -112,7 +112,7 @@ int min_heap_reserve(min_heap_t* s, unsi
>          unsigned a = s->a ? s->a * 2 : 8;
>          if(a < n)
>              a = n;
> -        if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
> +        if((p = reallocarray(s->p, a, sizeof *p)) == NULL)
>              return -1;
>          s->p = p;
>          s->a = a;
>

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Theo de Raadt-2
Theo de Raadt <[hidden email]> wrote:

> Reading this min_heap.h code for the first time, I shuddered because it
> reminded me of the exploit mitigation mechanism in openssl which prevent
> heartbleed from being exploitable in the presence of our fine otto
> malloc.

Oops, this is more correct:

Reading this min_heap.h code for the first time, I shuddered because it
reminded me of the exploit mitigation mechanism in openssl which
prevented our fine otto malloc from defending against the memory-cache
in openssl which heartbleed attacks depended upon.


Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Ted Unangst-6
In reply to this post by Theo de Raadt-2
Theo de Raadt wrote:
> So the diff presented falls short of what should be done here;
> insufficient lines deleted.

we're not getting to the fun part yet, but this unfold some complex operations
to assist human readers.

-        min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
+ if (min_child == s->n ||
+    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
+         min_child -= 1;

that one really stands out as kinda not the normal way of doing things.

(and then reformat to be knf, but after changes that require review.)

Index: min_heap.h
===================================================================
RCS file: /home/cvs/src/lib/libevent/min_heap.h,v
retrieving revision 1.3
diff -u -p -r1.3 min_heap.h
--- min_heap.h 29 Oct 2014 22:47:29 -0000 1.3
+++ min_heap.h 17 Apr 2019 15:30:02 -0000
@@ -112,7 +112,7 @@ int min_heap_reserve(min_heap_t* s, unsi
         unsigned a = s->a ? s->a * 2 : 8;
         if(a < n)
             a = n;
-        if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
+        if(!(p = realloc(s->p, a * sizeof *p)))
             return -1;
         s->p = p;
         s->a = a;
@@ -125,11 +125,13 @@ void min_heap_shift_up_(min_heap_t* s, u
     unsigned parent = (hole_index - 1) / 2;
     while(hole_index && min_heap_elem_greater(s->p[parent], e))
     {
-        (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
+        s->p[hole_index] = s->p[parent];
+        s->p[hole_index]->min_heap_idx = hole_index;
         hole_index = parent;
         parent = (hole_index - 1) / 2;
     }
-    (s->p[hole_index] = e)->min_heap_idx = hole_index;
+    e->min_heap_idx = hole_index;
+    s->p[hole_index] = e;
 }
 
 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
@@ -137,10 +139,13 @@ void min_heap_shift_down_(min_heap_t* s,
     unsigned min_child = 2 * (hole_index + 1);
     while(min_child <= s->n)
  {
-        min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
+ if (min_child == s->n ||
+    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
+         min_child -= 1;
         if(!(min_heap_elem_greater(e, s->p[min_child])))
             break;
-        (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
+        s->p[hole_index] = s->p[min_child];
+        s->p[hole_index]->min_heap_idx = hole_index;
         hole_index = min_child;
         min_child = 2 * (hole_index + 1);
  }

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Otto Moerbeek
On Wed, Apr 17, 2019 at 11:34:36AM -0400, Ted Unangst wrote:

> Theo de Raadt wrote:
> > So the diff presented falls short of what should be done here;
> > insufficient lines deleted.
>
> we're not getting to the fun part yet, but this unfold some complex operations
> to assist human readers.
>
> -        min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
> + if (min_child == s->n ||
> +    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
> +         min_child -= 1;
>
> that one really stands out as kinda not the normal way of doing things.
>
> (and then reformat to be knf, but after changes that require review.)

Looks good to me.

If the regress tests agree, ok,

        -Otto

>
> Index: min_heap.h
> ===================================================================
> RCS file: /home/cvs/src/lib/libevent/min_heap.h,v
> retrieving revision 1.3
> diff -u -p -r1.3 min_heap.h
> --- min_heap.h 29 Oct 2014 22:47:29 -0000 1.3
> +++ min_heap.h 17 Apr 2019 15:30:02 -0000
> @@ -112,7 +112,7 @@ int min_heap_reserve(min_heap_t* s, unsi
>          unsigned a = s->a ? s->a * 2 : 8;
>          if(a < n)
>              a = n;
> -        if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
> +        if(!(p = realloc(s->p, a * sizeof *p)))
>              return -1;
>          s->p = p;
>          s->a = a;
> @@ -125,11 +125,13 @@ void min_heap_shift_up_(min_heap_t* s, u
>      unsigned parent = (hole_index - 1) / 2;
>      while(hole_index && min_heap_elem_greater(s->p[parent], e))
>      {
> -        (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
> +        s->p[hole_index] = s->p[parent];
> +        s->p[hole_index]->min_heap_idx = hole_index;
>          hole_index = parent;
>          parent = (hole_index - 1) / 2;
>      }
> -    (s->p[hole_index] = e)->min_heap_idx = hole_index;
> +    e->min_heap_idx = hole_index;
> +    s->p[hole_index] = e;
>  }
>  
>  void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
> @@ -137,10 +139,13 @@ void min_heap_shift_down_(min_heap_t* s,
>      unsigned min_child = 2 * (hole_index + 1);
>      while(min_child <= s->n)
>   {
> -        min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
> + if (min_child == s->n ||
> +    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
> +         min_child -= 1;
>          if(!(min_heap_elem_greater(e, s->p[min_child])))
>              break;
> -        (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
> +        s->p[hole_index] = s->p[min_child];
> +        s->p[hole_index]->min_heap_idx = hole_index;
>          hole_index = min_child;
>          min_child = 2 * (hole_index + 1);
>   }
>

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Tobias Stoeckmann-5
In reply to this post by Ted Unangst-6
On Wed, Apr 17, 2019 at 11:34:36AM -0400, Ted Unangst wrote:
> (and then reformat to be knf, but after changes that require review.)

Totally agree here. That will help with further changes to this file!

>
> Index: min_heap.h
> ===================================================================
> RCS file: /home/cvs/src/lib/libevent/min_heap.h,v
> retrieving revision 1.3
> diff -u -p -r1.3 min_heap.h
> --- min_heap.h 29 Oct 2014 22:47:29 -0000 1.3
> +++ min_heap.h 17 Apr 2019 15:30:02 -0000
> @@ -112,7 +112,7 @@ int min_heap_reserve(min_heap_t* s, unsi
>          unsigned a = s->a ? s->a * 2 : 8;
>          if(a < n)
>              a = n;
> -        if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
> +        if(!(p = realloc(s->p, a * sizeof *p)))
>              return -1;
>          s->p = p;
>          s->a = a;
> @@ -125,11 +125,13 @@ void min_heap_shift_up_(min_heap_t* s, u
>      unsigned parent = (hole_index - 1) / 2;
>      while(hole_index && min_heap_elem_greater(s->p[parent], e))
>      {
> -        (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
> +        s->p[hole_index] = s->p[parent];
> +        s->p[hole_index]->min_heap_idx = hole_index;
>          hole_index = parent;
>          parent = (hole_index - 1) / 2;
>      }
> -    (s->p[hole_index] = e)->min_heap_idx = hole_index;
> +    e->min_heap_idx = hole_index;
> +    s->p[hole_index] = e;
>  }
>  
>  void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
> @@ -137,10 +139,13 @@ void min_heap_shift_down_(min_heap_t* s,
>      unsigned min_child = 2 * (hole_index + 1);
>      while(min_child <= s->n)
>   {
> -        min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
> + if (min_child == s->n ||
> +    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
> +         min_child -= 1;
>          if(!(min_heap_elem_greater(e, s->p[min_child])))
>              break;
> -        (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
> +        s->p[hole_index] = s->p[min_child];
> +        s->p[hole_index]->min_heap_idx = hole_index;
>          hole_index = min_child;
>          min_child = 2 * (hole_index + 1);
>   }

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Ted Unangst-6
In reply to this post by Ted Unangst-6
Ted Unangst wrote:
> (and then reformat to be knf, but after changes that require review.)

mostly mechanical..

we'll get to real changes eventually :)


Index: min_heap.h
===================================================================
RCS file: /cvs/src/lib/libevent/min_heap.h,v
retrieving revision 1.4
diff -u -p -r1.4 min_heap.h
--- min_heap.h 18 Apr 2019 23:44:21 -0000 1.4
+++ min_heap.h 18 Apr 2019 23:48:36 -0000
@@ -31,125 +31,152 @@
 
 #include "event.h"
 
-typedef struct min_heap
-{
-    struct event** p;
-    unsigned n, a;
+typedef struct min_heap {
+ struct event **p;
+ unsigned n, a;
 } min_heap_t;
 
-static inline void           min_heap_ctor(min_heap_t* s);
-static inline void           min_heap_dtor(min_heap_t* s);
-static inline void           min_heap_elem_init(struct event* e);
-static inline int            min_heap_elem_greater(struct event *a, struct event *b);
-static inline int            min_heap_empty(min_heap_t* s);
-static inline unsigned       min_heap_size(min_heap_t* s);
-static inline struct event*  min_heap_top(min_heap_t* s);
-static inline int            min_heap_reserve(min_heap_t* s, unsigned n);
-static inline int            min_heap_push(min_heap_t* s, struct event* e);
-static inline struct event*  min_heap_pop(min_heap_t* s);
-static inline int            min_heap_erase(min_heap_t* s, struct event* e);
-static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
-static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
-
-int min_heap_elem_greater(struct event *a, struct event *b)
-{
-    return timercmp(&a->ev_timeout, &b->ev_timeout, >);
-}
-
-void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
-void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
-void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
-int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
-unsigned min_heap_size(min_heap_t* s) { return s->n; }
-struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
-
-int min_heap_push(min_heap_t* s, struct event* e)
-{
-    if(min_heap_reserve(s, s->n + 1))
-        return -1;
-    min_heap_shift_up_(s, s->n++, e);
-    return 0;
-}
-
-struct event* min_heap_pop(min_heap_t* s)
-{
-    if(s->n)
-    {
-        struct event* e = *s->p;
-        min_heap_shift_down_(s, 0u, s->p[--s->n]);
-        e->min_heap_idx = -1;
-        return e;
-    }
-    return 0;
-}
-
-int min_heap_erase(min_heap_t* s, struct event* e)
-{
-    if(((unsigned int)-1) != e->min_heap_idx)
-    {
-        struct event *last = s->p[--s->n];
-        unsigned parent = (e->min_heap_idx - 1) / 2;
- /* we replace e with the last element in the heap.  We might need to
-   shift it upward if it is less than its parent, or downward if it is
-   greater than one or both its children. Since the children are known
-   to be less than the parent, it can't need to shift both up and
-   down. */
-        if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
-             min_heap_shift_up_(s, e->min_heap_idx, last);
-        else
-             min_heap_shift_down_(s, e->min_heap_idx, last);
-        e->min_heap_idx = -1;
-        return 0;
-    }
-    return -1;
-}
-
-int min_heap_reserve(min_heap_t* s, unsigned n)
-{
-    if(s->a < n)
-    {
-        struct event** p;
-        unsigned a = s->a ? s->a * 2 : 8;
-        if(a < n)
-            a = n;
-        if(!(p = realloc(s->p, a * sizeof *p)))
-            return -1;
-        s->p = p;
-        s->a = a;
-    }
-    return 0;
-}
-
-void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
-{
-    unsigned parent = (hole_index - 1) / 2;
-    while(hole_index && min_heap_elem_greater(s->p[parent], e))
-    {
-        s->p[hole_index] = s->p[parent];
-        s->p[hole_index]->min_heap_idx = hole_index;
-        hole_index = parent;
-        parent = (hole_index - 1) / 2;
-    }
-    e->min_heap_idx = hole_index;
-    s->p[hole_index] = e;
-}
-
-void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
-{
-    unsigned min_child = 2 * (hole_index + 1);
-    while(min_child <= s->n)
- {
- if (min_child == s->n ||
-    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
-         min_child -= 1;
-        if(!(min_heap_elem_greater(e, s->p[min_child])))
-            break;
-        s->p[hole_index] = s->p[min_child];
-        s->p[hole_index]->min_heap_idx = hole_index;
-        hole_index = min_child;
-        min_child = 2 * (hole_index + 1);
+static inline void min_heap_ctor(min_heap_t * s);
+static inline void min_heap_dtor(min_heap_t * s);
+static inline void min_heap_elem_init(struct event * e);
+static inline int min_heap_elem_greater(struct event * a, struct event * b);
+static inline int min_heap_empty(min_heap_t * s);
+static inline unsigned min_heap_size(min_heap_t * s);
+static inline struct event *min_heap_top(min_heap_t * s);
+static inline int min_heap_reserve(min_heap_t * s, unsigned n);
+static inline int min_heap_push(min_heap_t * s, struct event * e);
+static inline struct event *min_heap_pop(min_heap_t * s);
+static inline int min_heap_erase(min_heap_t * s, struct event * e);
+static inline void min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e);
+static inline void min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e);
+
+int
+min_heap_elem_greater(struct event * a, struct event * b)
+{
+ return timercmp(&a->ev_timeout, &b->ev_timeout, >);
+}
+
+void
+min_heap_ctor(min_heap_t * s)
+{
+ s->p = 0;
+ s->n = 0;
+ s->a = 0;
+}
+void min_heap_dtor(min_heap_t * s) {
+ if (s->p)
+ free(s->p);
+}
+void
+min_heap_elem_init(struct event * e)
+{
+ e->min_heap_idx = -1;
+}
+int
+min_heap_empty(min_heap_t * s)
+{
+ return 0u == s->n;
+}
+unsigned
+min_heap_size(min_heap_t * s)
+{
+ return s->n;
+}
+struct event *
+min_heap_top(min_heap_t * s)
+{
+ return s->n ? *s->p : 0;
+}
+
+int
+min_heap_push(min_heap_t * s, struct event * e)
+{
+ if (min_heap_reserve(s, s->n + 1))
+ return -1;
+ min_heap_shift_up_(s, s->n++, e);
+ return 0;
+}
+
+struct event *
+min_heap_pop(min_heap_t * s)
+{
+ if (s->n) {
+ struct event *e = *s->p;
+ min_heap_shift_down_(s, 0u, s->p[--s->n]);
+ e->min_heap_idx = -1;
+ return e;
+ }
+ return 0;
+}
+
+int
+min_heap_erase(min_heap_t * s, struct event * e)
+{
+ if (((unsigned int)-1) != e->min_heap_idx) {
+ struct event *last = s->p[--s->n];
+ unsigned parent = (e->min_heap_idx - 1) / 2;
+ /*
+ * we replace e with the last element in the heap.  We might
+ * need to shift it upward if it is less than its parent, or
+ * downward if it is greater than one or both its children.
+ * Since the children are known to be less than the parent,
+ * it can't need to shift both up and down.
+ */
+ if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
+ min_heap_shift_up_(s, e->min_heap_idx, last);
+ else
+ min_heap_shift_down_(s, e->min_heap_idx, last);
+ e->min_heap_idx = -1;
+ return 0;
+ }
+ return -1;
+}
+
+int
+min_heap_reserve(min_heap_t * s, unsigned n)
+{
+ if (s->a < n) {
+ struct event **p;
+ unsigned a = s->a ? s->a * 2 : 8;
+ if (a < n)
+ a = n;
+ if (!(p = realloc(s->p, a * sizeof *p)))
+ return -1;
+ s->p = p;
+ s->a = a;
  }
-    min_heap_shift_up_(s, hole_index,  e);
+ return 0;
 }
 
-#endif /* _MIN_HEAP_H_ */
+void
+min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
+{
+ unsigned parent = (hole_index - 1) / 2;
+ while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
+ s->p[hole_index] = s->p[parent];
+ s->p[hole_index]->min_heap_idx = hole_index;
+ hole_index = parent;
+ parent = (hole_index - 1) / 2;
+ }
+ e->min_heap_idx = hole_index;
+ s->p[hole_index] = e;
+}
+
+void
+min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e)
+{
+ unsigned min_child = 2 * (hole_index + 1);
+ while (min_child <= s->n) {
+ if (min_child == s->n ||
+    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
+ min_child -= 1;
+ if (!(min_heap_elem_greater(e, s->p[min_child])))
+ break;
+ s->p[hole_index] = s->p[min_child];
+ s->p[hole_index]->min_heap_idx = hole_index;
+ hole_index = min_child;
+ min_child = 2 * (hole_index + 1);
+ }
+ min_heap_shift_up_(s, hole_index, e);
+}
+#endif /* _MIN_HEAP_H_ */

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Alexander Bluhm
On Thu, Apr 18, 2019 at 07:49:29PM -0400, Ted Unangst wrote:
> Ted Unangst wrote:
> > (and then reformat to be knf, but after changes that require review.)
>
> mostly mechanical..

OK bluhm@

>
> we'll get to real changes eventually :)
>
>
> Index: min_heap.h
> ===================================================================
> RCS file: /cvs/src/lib/libevent/min_heap.h,v
> retrieving revision 1.4
> diff -u -p -r1.4 min_heap.h
> --- min_heap.h 18 Apr 2019 23:44:21 -0000 1.4
> +++ min_heap.h 18 Apr 2019 23:48:36 -0000
> @@ -31,125 +31,152 @@
>
>  #include "event.h"
>
> -typedef struct min_heap
> -{
> -    struct event** p;
> -    unsigned n, a;
> +typedef struct min_heap {
> + struct event **p;
> + unsigned n, a;
>  } min_heap_t;
>
> -static inline void           min_heap_ctor(min_heap_t* s);
> -static inline void           min_heap_dtor(min_heap_t* s);
> -static inline void           min_heap_elem_init(struct event* e);
> -static inline int            min_heap_elem_greater(struct event *a, struct event *b);
> -static inline int            min_heap_empty(min_heap_t* s);
> -static inline unsigned       min_heap_size(min_heap_t* s);
> -static inline struct event*  min_heap_top(min_heap_t* s);
> -static inline int            min_heap_reserve(min_heap_t* s, unsigned n);
> -static inline int            min_heap_push(min_heap_t* s, struct event* e);
> -static inline struct event*  min_heap_pop(min_heap_t* s);
> -static inline int            min_heap_erase(min_heap_t* s, struct event* e);
> -static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
> -static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
> -
> -int min_heap_elem_greater(struct event *a, struct event *b)
> -{
> -    return timercmp(&a->ev_timeout, &b->ev_timeout, >);
> -}
> -
> -void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
> -void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
> -void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
> -int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
> -unsigned min_heap_size(min_heap_t* s) { return s->n; }
> -struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
> -
> -int min_heap_push(min_heap_t* s, struct event* e)
> -{
> -    if(min_heap_reserve(s, s->n + 1))
> -        return -1;
> -    min_heap_shift_up_(s, s->n++, e);
> -    return 0;
> -}
> -
> -struct event* min_heap_pop(min_heap_t* s)
> -{
> -    if(s->n)
> -    {
> -        struct event* e = *s->p;
> -        min_heap_shift_down_(s, 0u, s->p[--s->n]);
> -        e->min_heap_idx = -1;
> -        return e;
> -    }
> -    return 0;
> -}
> -
> -int min_heap_erase(min_heap_t* s, struct event* e)
> -{
> -    if(((unsigned int)-1) != e->min_heap_idx)
> -    {
> -        struct event *last = s->p[--s->n];
> -        unsigned parent = (e->min_heap_idx - 1) / 2;
> - /* we replace e with the last element in the heap.  We might need to
> -   shift it upward if it is less than its parent, or downward if it is
> -   greater than one or both its children. Since the children are known
> -   to be less than the parent, it can't need to shift both up and
> -   down. */
> -        if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
> -             min_heap_shift_up_(s, e->min_heap_idx, last);
> -        else
> -             min_heap_shift_down_(s, e->min_heap_idx, last);
> -        e->min_heap_idx = -1;
> -        return 0;
> -    }
> -    return -1;
> -}
> -
> -int min_heap_reserve(min_heap_t* s, unsigned n)
> -{
> -    if(s->a < n)
> -    {
> -        struct event** p;
> -        unsigned a = s->a ? s->a * 2 : 8;
> -        if(a < n)
> -            a = n;
> -        if(!(p = realloc(s->p, a * sizeof *p)))
> -            return -1;
> -        s->p = p;
> -        s->a = a;
> -    }
> -    return 0;
> -}
> -
> -void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
> -{
> -    unsigned parent = (hole_index - 1) / 2;
> -    while(hole_index && min_heap_elem_greater(s->p[parent], e))
> -    {
> -        s->p[hole_index] = s->p[parent];
> -        s->p[hole_index]->min_heap_idx = hole_index;
> -        hole_index = parent;
> -        parent = (hole_index - 1) / 2;
> -    }
> -    e->min_heap_idx = hole_index;
> -    s->p[hole_index] = e;
> -}
> -
> -void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
> -{
> -    unsigned min_child = 2 * (hole_index + 1);
> -    while(min_child <= s->n)
> - {
> - if (min_child == s->n ||
> -    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
> -         min_child -= 1;
> -        if(!(min_heap_elem_greater(e, s->p[min_child])))
> -            break;
> -        s->p[hole_index] = s->p[min_child];
> -        s->p[hole_index]->min_heap_idx = hole_index;
> -        hole_index = min_child;
> -        min_child = 2 * (hole_index + 1);
> +static inline void min_heap_ctor(min_heap_t * s);
> +static inline void min_heap_dtor(min_heap_t * s);
> +static inline void min_heap_elem_init(struct event * e);
> +static inline int min_heap_elem_greater(struct event * a, struct event * b);
> +static inline int min_heap_empty(min_heap_t * s);
> +static inline unsigned min_heap_size(min_heap_t * s);
> +static inline struct event *min_heap_top(min_heap_t * s);
> +static inline int min_heap_reserve(min_heap_t * s, unsigned n);
> +static inline int min_heap_push(min_heap_t * s, struct event * e);
> +static inline struct event *min_heap_pop(min_heap_t * s);
> +static inline int min_heap_erase(min_heap_t * s, struct event * e);
> +static inline void min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e);
> +static inline void min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e);
> +
> +int
> +min_heap_elem_greater(struct event * a, struct event * b)
> +{
> + return timercmp(&a->ev_timeout, &b->ev_timeout, >);
> +}
> +
> +void
> +min_heap_ctor(min_heap_t * s)
> +{
> + s->p = 0;
> + s->n = 0;
> + s->a = 0;
> +}
> +void min_heap_dtor(min_heap_t * s) {
> + if (s->p)
> + free(s->p);
> +}
> +void
> +min_heap_elem_init(struct event * e)
> +{
> + e->min_heap_idx = -1;
> +}
> +int
> +min_heap_empty(min_heap_t * s)
> +{
> + return 0u == s->n;
> +}
> +unsigned
> +min_heap_size(min_heap_t * s)
> +{
> + return s->n;
> +}
> +struct event *
> +min_heap_top(min_heap_t * s)
> +{
> + return s->n ? *s->p : 0;
> +}
> +
> +int
> +min_heap_push(min_heap_t * s, struct event * e)
> +{
> + if (min_heap_reserve(s, s->n + 1))
> + return -1;
> + min_heap_shift_up_(s, s->n++, e);
> + return 0;
> +}
> +
> +struct event *
> +min_heap_pop(min_heap_t * s)
> +{
> + if (s->n) {
> + struct event *e = *s->p;
> + min_heap_shift_down_(s, 0u, s->p[--s->n]);
> + e->min_heap_idx = -1;
> + return e;
> + }
> + return 0;
> +}
> +
> +int
> +min_heap_erase(min_heap_t * s, struct event * e)
> +{
> + if (((unsigned int)-1) != e->min_heap_idx) {
> + struct event *last = s->p[--s->n];
> + unsigned parent = (e->min_heap_idx - 1) / 2;
> + /*
> + * we replace e with the last element in the heap.  We might
> + * need to shift it upward if it is less than its parent, or
> + * downward if it is greater than one or both its children.
> + * Since the children are known to be less than the parent,
> + * it can't need to shift both up and down.
> + */
> + if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
> + min_heap_shift_up_(s, e->min_heap_idx, last);
> + else
> + min_heap_shift_down_(s, e->min_heap_idx, last);
> + e->min_heap_idx = -1;
> + return 0;
> + }
> + return -1;
> +}
> +
> +int
> +min_heap_reserve(min_heap_t * s, unsigned n)
> +{
> + if (s->a < n) {
> + struct event **p;
> + unsigned a = s->a ? s->a * 2 : 8;
> + if (a < n)
> + a = n;
> + if (!(p = realloc(s->p, a * sizeof *p)))
> + return -1;
> + s->p = p;
> + s->a = a;
>   }
> -    min_heap_shift_up_(s, hole_index,  e);
> + return 0;
>  }
>
> -#endif /* _MIN_HEAP_H_ */
> +void
> +min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
> +{
> + unsigned parent = (hole_index - 1) / 2;
> + while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
> + s->p[hole_index] = s->p[parent];
> + s->p[hole_index]->min_heap_idx = hole_index;
> + hole_index = parent;
> + parent = (hole_index - 1) / 2;
> + }
> + e->min_heap_idx = hole_index;
> + s->p[hole_index] = e;
> +}
> +
> +void
> +min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e)
> +{
> + unsigned min_child = 2 * (hole_index + 1);
> + while (min_child <= s->n) {
> + if (min_child == s->n ||
> +    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
> + min_child -= 1;
> + if (!(min_heap_elem_greater(e, s->p[min_child])))
> + break;
> + s->p[hole_index] = s->p[min_child];
> + s->p[hole_index]->min_heap_idx = hole_index;
> + hole_index = min_child;
> + min_child = 2 * (hole_index + 1);
> + }
> + min_heap_shift_up_(s, hole_index, e);
> +}
> +#endif /* _MIN_HEAP_H_ */

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Ted Unangst-6
In reply to this post by Tobias Stoeckmann-5
Tobias Stoeckmann wrote:
> I would like to protect min_heap_push against integer overflows,
> which could either be triggered on a 64 bit system with massive
> amounts of RAM (to overflow s->n) or on a 32 bit system with tight
> memory layout (overflowing a * sizeof *p).
>
> Both cases are basically not possible to be triggered, but I prefer
> to have reallocarray in place to be sure about it.

ok, so back to this. here's a diff which solves this by using appropriate
size_t types.

Note the first chunk changes the size of struct event, so this is a library
ABI change. (Maybe it's padded? I don't feel like digging that deep.)

Index: event.h
===================================================================
RCS file: /cvs/src/lib/libevent/event.h,v
retrieving revision 1.30
diff -u -p -r1.30 event.h
--- event.h 5 Jan 2015 23:14:36 -0000 1.30
+++ event.h 20 Apr 2019 23:28:09 -0000
@@ -196,7 +196,7 @@ struct event {
  TAILQ_ENTRY (event) ev_next;
  TAILQ_ENTRY (event) ev_active_next;
  TAILQ_ENTRY (event) ev_signal_next;
- unsigned int min_heap_idx; /* for managing timeouts */
+ size_t min_heap_idx; /* for managing timeouts */
 
  struct event_base *ev_base;
 
Index: min_heap.h
===================================================================
RCS file: /cvs/src/lib/libevent/min_heap.h,v
retrieving revision 1.5
diff -u -p -r1.5 min_heap.h
--- min_heap.h 20 Apr 2019 23:22:28 -0000 1.5
+++ min_heap.h 20 Apr 2019 23:28:09 -0000
@@ -33,7 +33,7 @@
 
 typedef struct min_heap {
  struct event **p;
- unsigned n, a;
+ size_t n, a;
 } min_heap_t;
 
 static inline void min_heap_ctor(min_heap_t * s);
@@ -41,14 +41,14 @@ static inline void min_heap_dtor(min_hea
 static inline void min_heap_elem_init(struct event * e);
 static inline int min_heap_elem_greater(struct event * a, struct event * b);
 static inline int min_heap_empty(min_heap_t * s);
-static inline unsigned min_heap_size(min_heap_t * s);
+static inline size_t min_heap_size(min_heap_t * s);
 static inline struct event *min_heap_top(min_heap_t * s);
-static inline int min_heap_reserve(min_heap_t * s, unsigned n);
+static inline int min_heap_reserve(min_heap_t * s, size_t n);
 static inline int min_heap_push(min_heap_t * s, struct event * e);
 static inline struct event *min_heap_pop(min_heap_t * s);
 static inline int min_heap_erase(min_heap_t * s, struct event * e);
-static inline void min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e);
-static inline void min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e);
+static inline void min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e);
+static inline void min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e);
 
 int
 min_heap_elem_greater(struct event * a, struct event * b)
@@ -77,7 +77,7 @@ min_heap_empty(min_heap_t * s)
 {
  return 0u == s->n;
 }
-unsigned
+size_t
 min_heap_size(min_heap_t * s)
 {
  return s->n;
@@ -112,9 +112,9 @@ min_heap_pop(min_heap_t * s)
 int
 min_heap_erase(min_heap_t * s, struct event * e)
 {
- if (((unsigned int)-1) != e->min_heap_idx) {
+ if (e->min_heap_idx != -1) {
  struct event *last = s->p[--s->n];
- unsigned parent = (e->min_heap_idx - 1) / 2;
+ size_t parent = (e->min_heap_idx - 1) / 2;
  /*
  * we replace e with the last element in the heap.  We might
  * need to shift it upward if it is less than its parent, or
@@ -133,14 +133,14 @@ min_heap_erase(min_heap_t * s, struct ev
 }
 
 int
-min_heap_reserve(min_heap_t * s, unsigned n)
+min_heap_reserve(min_heap_t * s, size_t n)
 {
  if (s->a < n) {
  struct event **p;
- unsigned a = s->a ? s->a * 2 : 8;
+ size_t a = s->a ? s->a * 2 : 8;
  if (a < n)
  a = n;
- if (!(p = realloc(s->p, a * sizeof *p)))
+ if (!(p = reallocarray(s->p, a, sizeof *p)))
  return -1;
  s->p = p;
  s->a = a;
@@ -149,9 +149,9 @@ min_heap_reserve(min_heap_t * s, unsigne
 }
 
 void
-min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
+min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e)
 {
- unsigned parent = (hole_index - 1) / 2;
+ size_t parent = (hole_index - 1) / 2;
  while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
  s->p[hole_index] = s->p[parent];
  s->p[hole_index]->min_heap_idx = hole_index;
@@ -163,9 +163,9 @@ min_heap_shift_up_(min_heap_t * s, unsig
 }
 
 void
-min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e)
+min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e)
 {
- unsigned min_child = 2 * (hole_index + 1);
+ size_t min_child = 2 * (hole_index + 1);
  while (min_child <= s->n) {
  if (min_child == s->n ||
     min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Alexander Bluhm
On Sat, Apr 20, 2019 at 07:30:50PM -0400, Ted Unangst wrote:
> ok, so back to this. here's a diff which solves this by using appropriate
> size_t types.

There are two 0u which are size_t now.  Just use 0.

I wonder whether SIZE_T_MAX would be better than -1.  But they seem
to be equivalent.

OK bluhm@

> Note the first chunk changes the size of struct event, so this is a library
> ABI change. (Maybe it's padded? I don't feel like digging that deep.)
>
> Index: event.h
> ===================================================================
> RCS file: /cvs/src/lib/libevent/event.h,v
> retrieving revision 1.30
> diff -u -p -r1.30 event.h
> --- event.h 5 Jan 2015 23:14:36 -0000 1.30
> +++ event.h 20 Apr 2019 23:28:09 -0000
> @@ -196,7 +196,7 @@ struct event {
>   TAILQ_ENTRY (event) ev_next;
>   TAILQ_ENTRY (event) ev_active_next;
>   TAILQ_ENTRY (event) ev_signal_next;
> - unsigned int min_heap_idx; /* for managing timeouts */
> + size_t min_heap_idx; /* for managing timeouts */
>
>   struct event_base *ev_base;
>
> Index: min_heap.h
> ===================================================================
> RCS file: /cvs/src/lib/libevent/min_heap.h,v
> retrieving revision 1.5
> diff -u -p -r1.5 min_heap.h
> --- min_heap.h 20 Apr 2019 23:22:28 -0000 1.5
> +++ min_heap.h 20 Apr 2019 23:28:09 -0000
> @@ -33,7 +33,7 @@
>
>  typedef struct min_heap {
>   struct event **p;
> - unsigned n, a;
> + size_t n, a;
>  } min_heap_t;
>
>  static inline void min_heap_ctor(min_heap_t * s);
> @@ -41,14 +41,14 @@ static inline void min_heap_dtor(min_hea
>  static inline void min_heap_elem_init(struct event * e);
>  static inline int min_heap_elem_greater(struct event * a, struct event * b);
>  static inline int min_heap_empty(min_heap_t * s);
> -static inline unsigned min_heap_size(min_heap_t * s);
> +static inline size_t min_heap_size(min_heap_t * s);
>  static inline struct event *min_heap_top(min_heap_t * s);
> -static inline int min_heap_reserve(min_heap_t * s, unsigned n);
> +static inline int min_heap_reserve(min_heap_t * s, size_t n);
>  static inline int min_heap_push(min_heap_t * s, struct event * e);
>  static inline struct event *min_heap_pop(min_heap_t * s);
>  static inline int min_heap_erase(min_heap_t * s, struct event * e);
> -static inline void min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e);
> -static inline void min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e);
> +static inline void min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e);
> +static inline void min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e);
>
>  int
>  min_heap_elem_greater(struct event * a, struct event * b)
> @@ -77,7 +77,7 @@ min_heap_empty(min_heap_t * s)
>  {
>   return 0u == s->n;
>  }
> -unsigned
> +size_t
>  min_heap_size(min_heap_t * s)
>  {
>   return s->n;
> @@ -112,9 +112,9 @@ min_heap_pop(min_heap_t * s)
>  int
>  min_heap_erase(min_heap_t * s, struct event * e)
>  {
> - if (((unsigned int)-1) != e->min_heap_idx) {
> + if (e->min_heap_idx != -1) {
>   struct event *last = s->p[--s->n];
> - unsigned parent = (e->min_heap_idx - 1) / 2;
> + size_t parent = (e->min_heap_idx - 1) / 2;
>   /*
>   * we replace e with the last element in the heap.  We might
>   * need to shift it upward if it is less than its parent, or
> @@ -133,14 +133,14 @@ min_heap_erase(min_heap_t * s, struct ev
>  }
>
>  int
> -min_heap_reserve(min_heap_t * s, unsigned n)
> +min_heap_reserve(min_heap_t * s, size_t n)
>  {
>   if (s->a < n) {
>   struct event **p;
> - unsigned a = s->a ? s->a * 2 : 8;
> + size_t a = s->a ? s->a * 2 : 8;
>   if (a < n)
>   a = n;
> - if (!(p = realloc(s->p, a * sizeof *p)))
> + if (!(p = reallocarray(s->p, a, sizeof *p)))
>   return -1;
>   s->p = p;
>   s->a = a;
> @@ -149,9 +149,9 @@ min_heap_reserve(min_heap_t * s, unsigne
>  }
>
>  void
> -min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
> +min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e)
>  {
> - unsigned parent = (hole_index - 1) / 2;
> + size_t parent = (hole_index - 1) / 2;
>   while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
>   s->p[hole_index] = s->p[parent];
>   s->p[hole_index]->min_heap_idx = hole_index;
> @@ -163,9 +163,9 @@ min_heap_shift_up_(min_heap_t * s, unsig
>  }
>
>  void
> -min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e)
> +min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e)
>  {
> - unsigned min_child = 2 * (hole_index + 1);
> + size_t min_child = 2 * (hole_index + 1);
>   while (min_child <= s->n) {
>   if (min_child == s->n ||
>      min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Tobias Stoeckmann-5
On Sun, Apr 21, 2019 at 08:53:11PM +0200, Alexander Bluhm wrote:
> I wonder whether SIZE_T_MAX would be better than -1.  But they seem
> to be equivalent.

I prefer SIZE_T_MAX as well.

> > Index: min_heap.h
> > ===================================================================
> > RCS file: /cvs/src/lib/libevent/min_heap.h,v
> > retrieving revision 1.5
> > diff -u -p -r1.5 min_heap.h
> > --- min_heap.h 20 Apr 2019 23:22:28 -0000 1.5
> > +++ min_heap.h 20 Apr 2019 23:28:09 -0000
> > @@ -33,7 +33,7 @@
> >
> >  typedef struct min_heap {
> >   struct event **p;
> > - unsigned n, a;
> > + size_t n, a;
> >  } min_heap_t;

Changing n means that at least timeout_correct in event.c must be
adjusted as well, because it is used as an unsigned:

static void
timeout_correct(struct event_base *base, struct timeval *tv)
{
        unsigned int size;
...
        size = base->timeheap.n;
        for (; size-- > 0; ++pev) {
                struct timeval *ev_tv = &(**pev).ev_timeout;
                timersub(ev_tv, &off, ev_tv);
        }
...
}

Looking only at min_heap.h it is okay, but takes a bit polishing to be
applicable for all files in libevent.



Tobias

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Tobias Stoeckmann-5
In reply to this post by Alexander Bluhm
On Sun, Apr 21, 2019 at 08:53:11PM +0200, Alexander Bluhm wrote:
> I wonder whether SIZE_T_MAX would be better than -1.  But they seem
> to be equivalent.

I prefer SIZE_T_MAX as well.

> > Index: min_heap.h
> > ===================================================================
> > RCS file: /cvs/src/lib/libevent/min_heap.h,v
> > retrieving revision 1.5
> > diff -u -p -r1.5 min_heap.h
> > --- min_heap.h 20 Apr 2019 23:22:28 -0000 1.5
> > +++ min_heap.h 20 Apr 2019 23:28:09 -0000
> > @@ -33,7 +33,7 @@
> >
> >  typedef struct min_heap {
> >   struct event **p;
> > - unsigned n, a;
> > + size_t n, a;
> >  } min_heap_t;

Changing n means that at least timeout_correct in event.c must be
adjusted as well, because it is used as an unsigned:

static void
timeout_correct(struct event_base *base, struct timeval *tv)
{
        unsigned int size;
...
        size = base->timeheap.n;
        for (; size-- > 0; ++pev) {
                struct timeval *ev_tv = &(**pev).ev_timeout;
                timersub(ev_tv, &off, ev_tv);
        }
...
}

Looking only at min_heap.h it is okay, but takes a bit polishing to be
applicable for all files in libevent.

I haven't inspected all occurrences, so no updated patch yet.


Tobias

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Ted Unangst-6
In reply to this post by Tobias Stoeckmann-5
Tobias Stoeckmann wrote:
> Changing n means that at least timeout_correct in event.c must be
> adjusted as well, because it is used as an unsigned:

ah, good catch. I don't think it's wrong (until it overflows) but needs to be
fixed. Needs some more review then. Thanks.

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Tobias Stoeckmann-5
On Mon, Apr 22, 2019 at 01:24:13PM -0400, Ted Unangst wrote:
> ah, good catch. I don't think it's wrong (until it overflows) but needs to be
> fixed. Needs some more review then. Thanks.

I have added following changes:

- converted 0u to 0 as bluhm pointed out
- converted -1 to SIZE_MAX whereever it was used as "illegal index"
  as bluhm mentioned as well
- converted timemap's size usages in event.c from (u)int to size_t

Passes regress tests.

I'll discuss this with libevent maintainers to get these changes into
upstream as well.


Index: event.c
===================================================================
RCS file: /cvs/src/lib/libevent/event.c,v
retrieving revision 1.38
diff -u -p -u -p -r1.38 event.c
--- event.c 6 Jan 2015 23:11:23 -0000 1.38
+++ event.c 22 Apr 2019 17:44:17 -0000
@@ -163,7 +163,8 @@ event_base_new(void)
 void
 event_base_free(struct event_base *base)
 {
- int i, n_deleted=0;
+ int i;
+ size_t n_deleted=0;
  struct event *ev;
 
  if (base == NULL && current_base)
@@ -199,7 +200,7 @@ event_base_free(struct event_base *base)
  }
 
  if (n_deleted)
- event_debug(("%s: %d events were still set in base",
+ event_debug(("%s: %z events were still set in base",
  __func__, n_deleted));
 
  if (base->evsel->dealloc != NULL)
@@ -846,7 +847,7 @@ static void
 timeout_correct(struct event_base *base, struct timeval *tv)
 {
  struct event **pev;
- unsigned int size;
+ size_t size;
  struct timeval off;
 
  if (use_monotonic)
Index: event.h
===================================================================
RCS file: /cvs/src/lib/libevent/event.h,v
retrieving revision 1.30
diff -u -p -u -p -r1.30 event.h
--- event.h 5 Jan 2015 23:14:36 -0000 1.30
+++ event.h 22 Apr 2019 17:44:17 -0000
@@ -196,7 +196,7 @@ struct event {
  TAILQ_ENTRY (event) ev_next;
  TAILQ_ENTRY (event) ev_active_next;
  TAILQ_ENTRY (event) ev_signal_next;
- unsigned int min_heap_idx; /* for managing timeouts */
+ size_t min_heap_idx; /* for managing timeouts */
 
  struct event_base *ev_base;
 
Index: min_heap.h
===================================================================
RCS file: /cvs/src/lib/libevent/min_heap.h,v
retrieving revision 1.5
diff -u -p -u -p -r1.5 min_heap.h
--- min_heap.h 20 Apr 2019 23:22:28 -0000 1.5
+++ min_heap.h 22 Apr 2019 17:44:17 -0000
@@ -33,7 +33,7 @@
 
 typedef struct min_heap {
  struct event **p;
- unsigned n, a;
+ size_t n, a;
 } min_heap_t;
 
 static inline void min_heap_ctor(min_heap_t * s);
@@ -41,14 +41,14 @@ static inline void min_heap_dtor(min_hea
 static inline void min_heap_elem_init(struct event * e);
 static inline int min_heap_elem_greater(struct event * a, struct event * b);
 static inline int min_heap_empty(min_heap_t * s);
-static inline unsigned min_heap_size(min_heap_t * s);
+static inline size_t min_heap_size(min_heap_t * s);
 static inline struct event *min_heap_top(min_heap_t * s);
-static inline int min_heap_reserve(min_heap_t * s, unsigned n);
+static inline int min_heap_reserve(min_heap_t * s, size_t n);
 static inline int min_heap_push(min_heap_t * s, struct event * e);
 static inline struct event *min_heap_pop(min_heap_t * s);
 static inline int min_heap_erase(min_heap_t * s, struct event * e);
-static inline void min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e);
-static inline void min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e);
+static inline void min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e);
+static inline void min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e);
 
 int
 min_heap_elem_greater(struct event * a, struct event * b)
@@ -70,14 +70,14 @@ void min_heap_dtor(min_heap_t * s) {
 void
 min_heap_elem_init(struct event * e)
 {
- e->min_heap_idx = -1;
+ e->min_heap_idx = SIZE_MAX;
 }
 int
 min_heap_empty(min_heap_t * s)
 {
- return 0u == s->n;
+ return 0 == s->n;
 }
-unsigned
+size_t
 min_heap_size(min_heap_t * s)
 {
  return s->n;
@@ -102,8 +102,8 @@ min_heap_pop(min_heap_t * s)
 {
  if (s->n) {
  struct event *e = *s->p;
- min_heap_shift_down_(s, 0u, s->p[--s->n]);
- e->min_heap_idx = -1;
+ min_heap_shift_down_(s, 0, s->p[--s->n]);
+ e->min_heap_idx = SIZE_MAX;
  return e;
  }
  return 0;
@@ -112,9 +112,9 @@ min_heap_pop(min_heap_t * s)
 int
 min_heap_erase(min_heap_t * s, struct event * e)
 {
- if (((unsigned int)-1) != e->min_heap_idx) {
+ if (e->min_heap_idx != SIZE_MAX) {
  struct event *last = s->p[--s->n];
- unsigned parent = (e->min_heap_idx - 1) / 2;
+ size_t parent = (e->min_heap_idx - 1) / 2;
  /*
  * we replace e with the last element in the heap.  We might
  * need to shift it upward if it is less than its parent, or
@@ -126,21 +126,21 @@ min_heap_erase(min_heap_t * s, struct ev
  min_heap_shift_up_(s, e->min_heap_idx, last);
  else
  min_heap_shift_down_(s, e->min_heap_idx, last);
- e->min_heap_idx = -1;
+ e->min_heap_idx = SIZE_MAX;
  return 0;
  }
  return -1;
 }
 
 int
-min_heap_reserve(min_heap_t * s, unsigned n)
+min_heap_reserve(min_heap_t * s, size_t n)
 {
  if (s->a < n) {
  struct event **p;
- unsigned a = s->a ? s->a * 2 : 8;
+ size_t a = s->a ? s->a * 2 : 8;
  if (a < n)
  a = n;
- if (!(p = realloc(s->p, a * sizeof *p)))
+ if (!(p = reallocarray(s->p, a, sizeof *p)))
  return -1;
  s->p = p;
  s->a = a;
@@ -149,9 +149,9 @@ min_heap_reserve(min_heap_t * s, unsigne
 }
 
 void
-min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
+min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e)
 {
- unsigned parent = (hole_index - 1) / 2;
+ size_t parent = (hole_index - 1) / 2;
  while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
  s->p[hole_index] = s->p[parent];
  s->p[hole_index]->min_heap_idx = hole_index;
@@ -163,9 +163,9 @@ min_heap_shift_up_(min_heap_t * s, unsig
 }
 
 void
-min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e)
+min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e)
 {
- unsigned min_child = 2 * (hole_index + 1);
+ size_t min_child = 2 * (hole_index + 1);
  while (min_child <= s->n) {
  if (min_child == s->n ||
     min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Ted Unangst-6
Tobias Stoeckmann wrote:

> On Mon, Apr 22, 2019 at 01:24:13PM -0400, Ted Unangst wrote:
> > ah, good catch. I don't think it's wrong (until it overflows) but needs to be
> > fixed. Needs some more review then. Thanks.
>
> I have added following changes:
>
> - converted 0u to 0 as bluhm pointed out
> - converted -1 to SIZE_MAX whereever it was used as "illegal index"
>   as bluhm mentioned as well
> - converted timemap's size usages in event.c from (u)int to size_t
>
> Passes regress tests.
>
> I'll discuss this with libevent maintainers to get these changes into
> upstream as well.

looks pretty good to me.

Reply | Threaded
Open this post in threaded view
|

Re: libevent: Protect integer multiplications (min_heap)

Jeremie Courreges-Anglas-2
In reply to this post by Tobias Stoeckmann-5

Tobias Stoeckmann wrote:

> On Mon, Apr 22, 2019 at 01:24:13PM -0400, Ted Unangst wrote:
> > ah, good catch. I don't think it's wrong (until it overflows) but needs to be
> > fixed. Needs some more review then. Thanks.
>
> I have added following changes:
>
> - converted 0u to 0 as bluhm pointed out
> - converted -1 to SIZE_MAX whereever it was used as "illegal index"
>   as bluhm mentioned as well
> - converted timemap's size usages in event.c from (u)int to size_t
>
> Passes regress tests.
>
> I'll discuss this with libevent maintainers to get these changes into
> upstream as well.

I'm not sure just switching to size_t and reallocarray are enough to
prevent all theoretical overflows.  eg in min_heap_reserve:

                size_t a = s->a ? s->a * 2 : 8;

but it's clearly going in the right direction.

I was concerned by the possible ABI break mentioned by Ted.
min_heap_idx appears purely internal, the ecosystem doesn't seem to
meddle with it.  Also the size of the structure doesn't change, neither
on 32 bits and 64 bits.

ok jca@ except for one problem, please see below,

> Index: event.c
> ===================================================================
> RCS file: /cvs/src/lib/libevent/event.c,v
> retrieving revision 1.38
> diff -u -p -u -p -r1.38 event.c
> --- event.c 6 Jan 2015 23:11:23 -0000 1.38
> +++ event.c 22 Apr 2019 17:44:17 -0000
> @@ -163,7 +163,8 @@ event_base_new(void)
>  void
>  event_base_free(struct event_base *base)
>  {
> - int i, n_deleted=0;
> + int i;
> + size_t n_deleted=0;
>   struct event *ev;
>  
>   if (base == NULL && current_base)
> @@ -199,7 +200,7 @@ event_base_free(struct event_base *base)
>   }
>  
>   if (n_deleted)
> - event_debug(("%s: %d events were still set in base",
> + event_debug(("%s: %z events were still set in base",

Should be %zu, as exposed by -DUSE_DEBUG.

>   __func__, n_deleted));
>  
>   if (base->evsel->dealloc != NULL)
> @@ -846,7 +847,7 @@ static void
>  timeout_correct(struct event_base *base, struct timeval *tv)
>  {
>   struct event **pev;
> - unsigned int size;
> + size_t size;
>   struct timeval off;
>  
>   if (use_monotonic)
> Index: event.h
> ===================================================================
> RCS file: /cvs/src/lib/libevent/event.h,v
> retrieving revision 1.30
> diff -u -p -u -p -r1.30 event.h
> --- event.h 5 Jan 2015 23:14:36 -0000 1.30
> +++ event.h 22 Apr 2019 17:44:17 -0000
> @@ -196,7 +196,7 @@ struct event {
>   TAILQ_ENTRY (event) ev_next;
>   TAILQ_ENTRY (event) ev_active_next;
>   TAILQ_ENTRY (event) ev_signal_next;
> - unsigned int min_heap_idx; /* for managing timeouts */
> + size_t min_heap_idx; /* for managing timeouts */
>  
>   struct event_base *ev_base;
>  
> Index: min_heap.h
> ===================================================================
> RCS file: /cvs/src/lib/libevent/min_heap.h,v
> retrieving revision 1.5
> diff -u -p -u -p -r1.5 min_heap.h
> --- min_heap.h 20 Apr 2019 23:22:28 -0000 1.5
> +++ min_heap.h 22 Apr 2019 17:44:17 -0000
> @@ -33,7 +33,7 @@
>  
>  typedef struct min_heap {
>   struct event **p;
> - unsigned n, a;
> + size_t n, a;
>  } min_heap_t;
>  
>  static inline void min_heap_ctor(min_heap_t * s);
> @@ -41,14 +41,14 @@ static inline void min_heap_dtor(min_hea
>  static inline void min_heap_elem_init(struct event * e);
>  static inline int min_heap_elem_greater(struct event * a, struct event * b);
>  static inline int min_heap_empty(min_heap_t * s);
> -static inline unsigned min_heap_size(min_heap_t * s);
> +static inline size_t min_heap_size(min_heap_t * s);
>  static inline struct event *min_heap_top(min_heap_t * s);
> -static inline int min_heap_reserve(min_heap_t * s, unsigned n);
> +static inline int min_heap_reserve(min_heap_t * s, size_t n);
>  static inline int min_heap_push(min_heap_t * s, struct event * e);
>  static inline struct event *min_heap_pop(min_heap_t * s);
>  static inline int min_heap_erase(min_heap_t * s, struct event * e);
> -static inline void min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e);
> -static inline void min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e);
> +static inline void min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e);
> +static inline void min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e);
>  
>  int
>  min_heap_elem_greater(struct event * a, struct event * b)
> @@ -70,14 +70,14 @@ void min_heap_dtor(min_heap_t * s) {
>  void
>  min_heap_elem_init(struct event * e)
>  {
> - e->min_heap_idx = -1;
> + e->min_heap_idx = SIZE_MAX;
>  }
>  int
>  min_heap_empty(min_heap_t * s)
>  {
> - return 0u == s->n;
> + return 0 == s->n;
>  }
> -unsigned
> +size_t
>  min_heap_size(min_heap_t * s)
>  {
>   return s->n;
> @@ -102,8 +102,8 @@ min_heap_pop(min_heap_t * s)
>  {
>   if (s->n) {
>   struct event *e = *s->p;
> - min_heap_shift_down_(s, 0u, s->p[--s->n]);
> - e->min_heap_idx = -1;
> + min_heap_shift_down_(s, 0, s->p[--s->n]);
> + e->min_heap_idx = SIZE_MAX;
>   return e;
>   }
>   return 0;
> @@ -112,9 +112,9 @@ min_heap_pop(min_heap_t * s)
>  int
>  min_heap_erase(min_heap_t * s, struct event * e)
>  {
> - if (((unsigned int)-1) != e->min_heap_idx) {
> + if (e->min_heap_idx != SIZE_MAX) {
>   struct event *last = s->p[--s->n];
> - unsigned parent = (e->min_heap_idx - 1) / 2;
> + size_t parent = (e->min_heap_idx - 1) / 2;
>   /*
>   * we replace e with the last element in the heap.  We might
>   * need to shift it upward if it is less than its parent, or
> @@ -126,21 +126,21 @@ min_heap_erase(min_heap_t * s, struct ev
>   min_heap_shift_up_(s, e->min_heap_idx, last);
>   else
>   min_heap_shift_down_(s, e->min_heap_idx, last);
> - e->min_heap_idx = -1;
> + e->min_heap_idx = SIZE_MAX;
>   return 0;
>   }
>   return -1;
>  }
>  
>  int
> -min_heap_reserve(min_heap_t * s, unsigned n)
> +min_heap_reserve(min_heap_t * s, size_t n)
>  {
>   if (s->a < n) {
>   struct event **p;
> - unsigned a = s->a ? s->a * 2 : 8;
> + size_t a = s->a ? s->a * 2 : 8;
>   if (a < n)
>   a = n;
> - if (!(p = realloc(s->p, a * sizeof *p)))
> + if (!(p = reallocarray(s->p, a, sizeof *p)))
>   return -1;
>   s->p = p;
>   s->a = a;
> @@ -149,9 +149,9 @@ min_heap_reserve(min_heap_t * s, unsigne
>  }
>  
>  void
> -min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
> +min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e)
>  {
> - unsigned parent = (hole_index - 1) / 2;
> + size_t parent = (hole_index - 1) / 2;
>   while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
>   s->p[hole_index] = s->p[parent];
>   s->p[hole_index]->min_heap_idx = hole_index;
> @@ -163,9 +163,9 @@ min_heap_shift_up_(min_heap_t * s, unsig
>  }
>  
>  void
> -min_heap_shift_down_(min_heap_t * s, unsigned hole_index, struct event * e)
> +min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e)
>  {
> - unsigned min_child = 2 * (hole_index + 1);
> + size_t min_child = 2 * (hole_index + 1);
>   while (min_child <= s->n) {
>   if (min_child == s->n ||
>      min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
>
>

--
jca | PGP : 0x1524E7EE / 5135 92C1 AD36 5293 2BDF  DDCC 0DFA 74AE 1524 E7EE